Contact Graph Routing (CGR) is a dynamic routing system that computes routes through a time-varying topology of scheduled communication contacts in a network based on the DTN (Delay-Tolerant Networking) architecture. It is designed to enable dynamic selection of data transmission routes in a space network based on DTN. This dynamic responsiveness in route computation should be significantly more effective and less expensive than static routing, increasing total data return while at the same time reducing mission operations cost and risk.
The basic strategy of CGR is to take advantage of the fact that, since flight mission communication operations are planned in detail, the communication routes between any pair of “bundle agents” in a population of nodes that have all been informed of one another’s plans can be inferred from those plans rather than discovered via dialogue (which is impractical over long one-waylight-time space links). Messages that convey this planning information are used to construct “contact graphs” (time-varying models of network connectivity) from which CGR automatically computes efficient routes for bundles. Automatic route selection increases the flexibility and resilience of the space network, simplifying cross-support and reducing mission management costs.
Note that there are no “routing tables” in Contact Graph Routing. The best route for a bundle destined for a given node may routinely be different from the best route for a different bundle destined for the same node, depending on bundle priority, bundle expiration time, and changes in the current lengths of transmission queues for neighboring nodes; routes must be computed individually for each bundle, from the Bundle Protocol agent’s current network connectivity model for the bundle’s destination node (the contact graph). Clearly this places a premium on optimizing the implementation of the route computation algorithm. The scalability of CGR to very large networks remains a research topic.
The information carried by CGR contact plan messages is useful not only for dynamic route computation, but also for the implementation of rate control, congestion forecasting, transmission episode initiation and termination, timeout interval computation, and retransmission timer suspension and resumption.
This work was done by Scott C. Burleigh of Caltech for NASA’s Jet Propulsion Laboratory.
This software is available for commercial licensing. Please contact Daniel Broderick of the California Institute of Technology at
This Brief includes a Technical Support Package (TSP).
Contact Graph Routing
(reference NPO-45488) is currently available for download from the TSP library.
Don't have an account?
Overview
The document is a Technical Support Package from NASA's Jet Propulsion Laboratory (JPL) concerning Contact Graph Routing (CGR), a system designed to improve communication in dynamic and time-varying networks, particularly in the context of space exploration and Delay-Tolerant Networking (DTN). The research is conducted under a contract with the National Aeronautics and Space Administration (NASA) and aims to make advancements in aerospace-related technologies accessible for broader technological, scientific, and commercial applications.
CGR addresses the challenges of communication in environments where traditional networking protocols may fail due to intermittent connectivity and long delays. The document outlines the principles of CGR, which utilizes a contact graph to represent the potential communication opportunities between nodes in a network. This approach allows for more efficient routing of data packets, or "bundles," by taking into account the varying availability of connections over time.
Key technical details include the estimation of data transmission times, which considers the maximum rate of change in distance between nodes. For instance, the document mentions that at speeds comparable to the Helios spacecraft (approximately 150,000 miles per hour), the distance between nodes can change significantly during data transmission. This necessitates a calculation of the expected time of arrival for transmitted bundles, factoring in both the initial distance and the rate of change.
The document also discusses the structure of data frames used in transmission, highlighting the importance of the maximum transmission unit size and the overhead associated with the convergence layer protocol. This information is crucial for estimating the number of frames required to transmit a given bundle size effectively.
Additionally, the document emphasizes the collaborative nature of the research, acknowledging the support from NASA and the California Institute of Technology. It provides contact information for further inquiries and assistance related to the technology, indicating a commitment to fostering innovative partnerships.
Overall, the Technical Support Package serves as a comprehensive overview of CGR, detailing its significance in enhancing communication capabilities in challenging environments, particularly for space missions, while also offering insights into its potential applications on Earth.
