Multigraph-based Routing in Delay Tolerant Networks: An Alternative to Contact Graph Routing

Satellites are leaving the realms of niche use, extending our day-to-day networked infrastructure to space – thereby forcing a generalization of network architectures. The Delay Tolerant Networking (DTN) protocol is being developed to give rise to this new Solar System Internet.

Predominantly, DTNs in space use globally-distributed contact tables to compute routes. In this paper, we propose and analyze a novel optimized approach for route computations that improves
upon traditional approaches. As the general DTN will always include some scheduled links, our new algorithm enables greater scalability and practicality of DTN routing.

These contact tables include windows when two nodes can communicate and were classically organized into a contact graph, where the vertices represent contact opportunities. Because the
complexity of a contact graph grows with the number of contacts, pathfinding on it does not scale. A new structure using multigraphs with the same data is proposed. We show that a
multigraph-based approach, which we call contact multigraph routing, exhibits performance superior to routing based on contact graphs, allowing greater scaling to schedule-based routing.

In this paper, the multigraph-based algorithm is detailed and a proof is included showing it outperforms the previous algorithm given the same input. Pseudocode is included, as are simulation results. We conclude with suggested future work.