Scoping Routing Scalability in Space Delay- and Disruption-Tolerant Networks

Extending the terrestrial Internet beyond Earth introduces challenges bigger than what traditional Internet protocols can handle. A network spanning nodes on and orbiting around celestial bodies is characterized by potentially long delays and frequent disruptions, as distances become astronomical and nodes start to move. To manage these extreme conditions, the Delayand Disruption-Tolerant Networking (DTN) architecture defines the deployment of persistent storage within the network, managed by the Bundle Protocol (BP). By doing so, nodes can store data until the connection with the intended next hop is (re-)established. On Earth, routing protocols depend on instantaneous and stable end-to-end connectivity - if a node is not reachable, data cannot be forwarded to it. Within a DTN, a node being unreachable now does not mean it is not reachable then. In space networks, such episodes of connectivity are termed contacts. Given the constellation of a space DTN, including the trajectory of nodes such as satellites or rockets, future contacts can be determined beforehand. Despite unstable connectivity, Contact Graph Routing (CGR) manages to compute routes and forward data by leveraging the predictability of contacts, determining not only the next hop but also when to send data to it. In order to do so, DTN nodes executing CGR need to be supplied with a contact plan, a list of all upcoming contacts. However, the algorithms involved in CGR are complex and it performance depends on the size of the contact plan as well as the network traffic, as it is executed at forwarding time. Space-grade computers deployed on spacecraft have limited compute and memory resources - the larger the space network and the longer the duration encoded in the contact plan, the more likely CGR exhausts these limited resources. In order to manage the scalability of CGR, a similar approach as defined by the Border Gateway Protocol (BGP) can be applied. Region-based techniques reduce the routing computation domain of CGR, significantly constraining is computational complexity. In this work, we examine the performance of CGR in order to understand all factors contributing to its complexity. To do so, we implement a modification of the most recent specification of CGR in DtnSim (OMNeT++) and define a space network based on recent studies on lunar communications architectures. Furthermore, we compare existing region-based proposals, selecting two methods applicable to the network. After defining an appropriate network partition, we evaluate the selected methods and compare them with the performance of CGR. The findings of our work show that the complexity of CGR depends not only on the contact plan, but also the network topology and network traffic. We show that for longer contact plans, larger networks and heavier traffic, both selected region-based methods manage to considerably decrease the average per-packet processing time and the average routing table size, while increasing the average packet delay by an amount that is reasonable for a space DTN