Analysis of the Contact Graph Routing Algorithm: Bounding Interplanetary Paths
- Paper number
IAC-10.B2.5.8
- Author
Mr. Edward Birrane, The John Hopkins University Applied Physics Laboratory, United States
- Coauthor
Mr. Scott Burleigh, National Aeronautics and Space Administration (NASA)/Jet Propulsion Laboratory, United States
- Year
2010
- Abstract
Interplanetary communications networks comprise orbiters, deep-space relays, and stations on planetary surfaces. These networks are characterized by mobile nodes and significant propagation delays. Opportunities for contact are based on wireless transmission and, therefore, lines of sight. The diameter of these networks are large enough that signal propagation delay becomes the dominant delay in the network. In fact, propagation delay may be larger than the line-of-sight contact between nodes. For example, Mars and Earth orbiters may be separated by up to 40 minutes of signal propagation time. These spacecraft may never share a line-of-sight, and yet they may uni-directionally communicate if one orbiter knows where the other one will be in the future. This constraint precludes effective negotiation or discovery within the network. The Contact Graph Routing (CGR) algorithm solves the messaging problem of interplanetary communications. This algorithm exploits networks where nodes exhibit deterministic mobility. In the CGR, mobility and bandwidth information is pre-configured across the network and a graph of contact opportunities is constructed. Once the contact graph has been established, the routing algorithm determines the optimal path through the network for various messages. While the optimal path may be knowable, it is likely not practical to compute, especially using flight hardware. Therefore, the interpretation of the contact graph, and the construction of a bounded approximate path, is critically important for adoption in operational systems. Brute force approaches to path calculation, while effective in small networks, are computationally expensive and will not scale. Methods of inferring cycles or other librations within the graph are difficult to detect and will guide the practical implementation of any routing algorithm. This paper presents preliminary mathematical analysis of the CGR algorithm, demonstrates that the problem is NP complete in the general case, and proposes realistic constraints making the problem solvable in polynomial time. Weighting functions are examined, and a trade-off between hop-by-hop forwarding versus path construction is examined in the context of a dynamic programming solution. Results are extrapolated to the presence of dynamic changes to the network, as produced by congestion, link disruption, and errors in the contact graph. Finally we address the issue of varying the contact graph analysis based on message type and priority. We conclude that CGR is an efficient method of routing in a multi-node, multi-path interplanetary network and that algorithmic analysis is key to its implementation in operational systems.
- Abstract document
- Manuscript document
IAC-10.B2.5.8.pdf (🔒 authorized access only).
To get the manuscript, please contact IAF Secretariat.