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 email address is being protected from spambots. You need JavaScript enabled to view it.. NPO-45488

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? Sign up here.

NASA Tech Briefs Magazine

This article first appeared in the October, 2011 issue of NASA Tech Briefs Magazine.

Read more articles from this issue here.

Read more articles from the archives here.