StableRoute: When Dijkstra's Algorithm Meets Topology-Varying Satellite Networks

Abstract

Low Earth Orbit (LEO) satellite constellations are becoming a viable means for Internet access. However, their topology changes as satellites move towards or away from orbital intersection points, leading to constant link down or up. This may cause routing table entry updates and thus path changes between satellites. A path change during transmission may lead to out-of-order packet delivery and invalidate the current TCP congestion window. While some path changes are inevitable, some are avoidable. Dijkstra's algorithm is a popular choice among the routing protocols proposed for LEO satellite networks. We observe that many next-hop route updates by Dijkstra's algorithm are avoidable. Motivated by this, we propose StableR-oute, which stabilizes routing paths from different perspectives. StableRoute Local (SR_L) leverages equal-cost shortest paths and stays with the current one if it is still valid. StableRoute K-Short (SR_K) allows a path longer than the shortest path. StableRoute Global (SR_G) leverages the predictable satellite trajectories and topology variations, and thus works out a next-hop route selection sequence that minimizes the number of route updates over a time period. The evaluation shows that SR_L, SR_K and SR_G outperform Dijkstra's algorithm, substantially reducing the number of route updates in changing topologies.