Rethinking LEO Constellations Routing

Paul Grislain (1, 2) , Alexia Auddino (3) , Anna Barraqué (3) , François Lamothe (4) , Oana Hotescu (4) , Jérôme Lacan (3) , José Radzik (3) , Emmanuel Lochin (5)

1 ENAC-LAB - Laboratoire de recherche ENAC
2 TESA - Laboratoire de recherche coopératif dans les télécommunications spatiales et aéronautiques
3 ISAE-SUPAERO - Institut Supérieur de l'Aéronautique et de l'Espace
4 ISAE-ENSMA - École Nationale Supérieure de Mécanique et d’Aérotechnique [Poitiers]
5 ENAC - Ecole Nationale de l'Aviation Civile

This study investigates the Unsplittable Multi-Commodity Flow (UMCF) as a routing algorithm for LEO constellations. Usually, LEO routing schemes enable the Floyd-Warshall algorithm (Shortest Path) to minimize the end-to-end latency of the flows crossing the constellation. We propose to solve the UMCF problem associated with the system as a solution for routing over LEO. We use a heuristic algorithm based on randomized rounding known in the optimization literature to efficiently solve the UMCF problem. Furthermore, we explore the impact of choosing the first/last hop before entering/exiting the constellation. Using network simulation over Telesat constellation, we show that UMCF maximizes the end-to-end links usage, providing better routing while minimizing the delay and the congestion level, which is an issue today over new megaconstellations. Keywords:LEO constellations, routing, Floyd-Warshall, UMCF, Hypatia, ns3 simulator

Mots clés: LEO constellations; routing; Floyd-Warshall; UMCF; Hypatia; ns3 simulator

Domaines: Réseaux et télécommunications [cs.NI]

Paul Grislain, Alexia Auddino, Anna Barraqué, François Lamothe, Oana Hotescu, et al.. Rethinking LEO Constellations Routing. International Journal of Satellite Communications and Networking, inPress, Special Issue ASMS/SPSC 2022. ⟨hal-04505620⟩