Contact Multigraph Routing: Overview and Implementation

In 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.