Rethinking LEO Constellations Routing with the Unsplittable Multi-Commodity Flows Problem

This study investigates the performance of an innovative routing protocol inspired by the Unsplittable Multi-Commodity Flow (UMCF) problem. LEO routing schemes are often based on Shortest Path (SP) algorithms, the Floyd-Warshall algorithm is usually chosen to compute these network paths within the constellation and their end-to-end latency. Instead of considering latency as a criterion, we seek to optimize the overall amount of IP traffic crossing the constellation. This criterion can be optimized by considering the Unsplittable Multi Commodity Flow problem associated with the system. To solve this problem, we use a heuristic algorithm based on randomized rounding that was shown to return solutions of good quality of the Unsplittable Multi Commodity Flow problem in the optimization literature. Using network simulation over Telesat constellation, we show this proposal significantly reduces the overall congestion level compared to the standard SP routing schemes.