NTRS - NASA Technical Reports Server

As of October 27, 2023, NASA STI Services will no longer have an embargo for accepted manuscripts. For more information visit NTRS News.

Back to Results
Contact Multigraph Routing: Overview and ImplementationIn Delay Tolerant Networking (DTN), the standard
routing algorithm used to navigate time-varying networks has
been Contact Graph Routing (CGR). In CGR, a globally distributed
list of contacts, periods during which two DTN nodes
may communicate, is used to construct a contact graph, in which
contacts are vertices. A version of Dijkstra’s algorithm can
then be used to find paths through this model of the timevarying
network. However, since contact graphs may be large
compared to the network, potentially growing with the square of
the number of network nodes and linearly with the time interval
represented, the resulting algorithm does not scale well with the
size of the network or time. Any improvement to the routing
algorithm will bring significant returns to scale.

In a previous paper, we briefly introduced an alternative to the
contact graph model for routing. This alternative model is based
on a multigraph (a graph in which there may be multiple edges
between a pair of vertices) where vertices represent network
nodes instead of contacts. A version of Dijkstra’s algorithm in
these multigraph models reduces the time needed to perform the
same routing computations done in the existing CGR algorithm.
Moreover, a modified version of Yen’s algorithm for multigraphs
is included. Our variation of CGR, which we call Contact Multigraph
Routing (CMR), provides an in-line replacement for the
previously used pathfinding algorithms. This paper describes
an implementation created based on the CMR approach, and
experimental comparisons to traditional CGR are given.

In addition, we explore some additional modifications to the
routing pipeline traditionally assumed in CGR. These modifications
range from the theoretical to the practical in terms of
size and scope. We step forward our understanding of sheaftheoretic
networking and describe how to model the routing
pipeline using sheaves. We detail some enhanced route selection
criteria that addresses some of the added complexity of DTNbased
systems. We also include a future works section on future
improvements and implementations that would be of service to
the broader DTN community.
Document ID
Document Type
Conference Paper
Michael Moy
(Colorado State University Fort Collins, Colorado, United States)
Robert Kassouf-Short
(Glenn Research Center Cleveland, Ohio, United States)
Nadia Kortas
(Glenn Research Center Cleveland, Ohio, United States)
Jacob Cleveland
(Glenn Research Center Cleveland, Ohio, United States)
Brian Tomko
(Glenn Research Center Cleveland, Ohio, United States)
Dominic Conricode
(University of California, Berkeley Berkeley, California, United States)
Yael Kirkpatrick
(Massachusetts Institute of Technology Cambridge, Massachusetts, United States)
Robert Cardona
(University at Albany, State University of New York Albany, New York, United States)
Brian Heller
(University at Albany, State University of New York Albany, New York, United States)
Justin Curry ORCID
(University at Albany, State University of New York Albany, New York, United States)
Date Acquired
February 27, 2023
Subject Category
Mathematical and Computer Sciences (General)
Space Communications, Spacecraft Communications, Command and Tracking
Communications and Radar
Meeting Information
Meeting: IEEE Aerospace Conference 2023
Location: Big Sky, MT
Country: US
Start Date: March 4, 2023
End Date: March 11, 2023
Sponsors: Institute of Electrical and Electronics Engineers
Funding Number(s)
WBS: 278371.01.06
Distribution Limits
Use by or on behalf of the US Gov. Permitted.
Technical Review
Single Expert
contact graph routing
computational complexity
graph theory
No Preview Available