Routing in LEO Mega-Constellations with Dynamic Inter-Satellite Link Delays

This paper addresses the routing problem in a Low Earth Orbit (LEO) satellite constellation considering known delays on inter-satellite links. Two novel routing algorithms are proposed to minimize latency between any pair of satellites: a modified Dijkstra algorithm and a dynamic programming-based algorithm. Experiments have shown that the dynamic programming-based algorithm is optimal in terms of computational complexity.