Publications Journal article · Delay-tolerant networks · 2020

A shortest-path tree approach for routing in space networks

Olivier De Jonckère and Juan A. Fraire

China Communications, vol. 17, no. 7, pp. 52–66, 2020

Abstract

A new space era is bringing deployments of thousands of networked assets in near-Earth and deep-space. Delay-Tolerant Networking (DTN) protocols and algorithms such as Contact Graph Routing (CGR) are state-of-the-art technologies certainly capable of achieving this ambitious objective. Nevertheless, in this paper, we highlight and analyze the roots of current scalability limits of CGR, to then propose more efficient alternatives. In particular, we leverage a different graph modeling approach that enables optimizations such as priority queues and spanning-tree searches in the core route determination process. While such abstract data types are difficult to adapt to CGR, we incorporate them into a novel Shortest-Path Tree Approach for Routing in Space Networks (SPSN), which is presented as a compute-efficient alternative. This paper thoroughly describes the SPSN approach including route object modeling, capacity-oriented search, and potential route management techniques. Prototype evaluations analyzed in this paper present significant evidence that SPSN outperforms legacy CGR in more than an order of magnitude in contact plans comprising thousands of contacts.

Cite

DOI 10.23919/j.cc.2020.07.005

BibTeX

@article{de2020shortest,
  author    = {De Jonck{\`e}re, Olivier and Fraire, Juan A.},
  title     = {A shortest-path tree approach for routing in space networks},
  journal   = {China Communications},
  volume    = {17},
  number    = {7},
  pages     = {52--66},
  publisher = {IEEE},
  year      = {2020},
  doi       = {10.23919/j.cc.2020.07.005}
}

More on delay-tolerant networks

Routing in the Space Internet: A contact graph routing tutorial Juan A. Fraire, Olivier De Jonckère, and Scott C. Burleigh Elsevier Journal of Network and Computer Applications, 2021
Abstract
A Space Internet is possible, as long as the delay and disruption challenges imposed by the space environment are properly tackled. Because these conditions are not well addressed by terrestrial Internet, more capable Delay-Tolerant Networking (DTN) protocols and algorithms are being developed. In particular, the principles and techniques for routing among ground elements and spacecraft in near-Earth orbit and deep-space are enacted in the Contact Graph Routing (CGR) framework. CGR blends a set of non-trivial algorithm adaptations, space operations concepts, time-dynamic scheduling, and specific graph models. The complexity of that framework suggests a need for a focused discussion to facilitate its direct and correct apprehension. To this end, we present an in-depth tutorial that collects and organizes first-hand experience on researching, developing, implementing, and standardizing CGR. Content is laid out in a structure that considers the planning, route search and management, and forwarding phases bridging ground and space domains. We rely on intuitive graphical examples, supporting code material, and references to flight-grade CGR implementations details where pertinent. We hope this tutorial will serve as a valuable resource for engineers and that researchers can also apply the insights presented here to topics in DTN research.

HAL Publisher
Ring Road Networks: Access for Anyone Marius Feldmann, Juan A. Fraire, Felix Walter, and Scott C. Burleigh IEEE Communications Magazine, 2022
Abstract
Several billion people currently lack reliable access to the Internet and thus to a tremendous source of knowledge. In this article, we describe a field-tested communication approach combining CubeSat platforms and delay-tolerant networking (DTN) solutions to provide asynchronous connectivity to populations and regions that are underserved by the Internet. The resulting class of networks is known as ring road networks (RRNs), a networking approach that is built on technology developed for the construction of a solar system Internet. The necessary self-sufficiency of DTN nodes enables network access to be deployed incrementally at low cost, supporting communities that cannot be profitably served by Internet satellite constellations. We present the RRN architecture and evaluate the expected performance by means of simulations. Based on the latter, we discuss µD3TN: a lightweight and open source DTN protocol stack for RRNs and other DTN classes. µD3TN has been flight-tested in ESA's OPS-SAT in low Earth orbit during December 2020 and May 2021. This work discusses the experiment results as we validated the RRN approach in concrete application use cases. The reported outcomes motivate a new application domain.

HAL Publisher
Assessing Contact Graph Routing Performance and Reliability in Distributed Satellite Constellations Juan A. Fraire, Pablo G. Madoery, Scott C. Burleigh, Marius Feldmann, Jorge M. Finochietto, Amir Charif, Nacer-Eddine Zergainoh, and Raoul Velazco Journal of Computer Networks and Communications, 2017
Abstract
Existing Internet protocols assume persistent end-to-end connectivity, which cannot be guaranteed in disruptive and high-latency space environments. To operate over these challenging networks, a store-carry-and-forward communication architecture called Delay/Disruption Tolerant Networking (DTN) has been proposed. This work provides the first examination of the performance and robustness of Contact Graph Routing (CGR) algorithm, the state-of-the-art routing scheme for space-based DTNs. To this end, after a thorough description of CGR, two appealing satellite constellations are proposed and evaluated by means of simulations. Indeed, the DtnSim simulator is introduced as another relevant contribution of this work. Results enabled the authors to identify existing CGR weaknesses and enhancement opportunities.

Publisher

Delay-tolerant networks: the topic page All 84 papers on this topic