Achieving Scalable and Efficient Routing in LEO Constellations

Mega Walker Delta constellations, such as Starlink and One Web, can offer economic seamless ubiquitous coverage solutions. However, its highly topological dynamics bring about serious challenges to network routing. Existing solutions either suffer from continuous convergences with poor scalability, or do not take into account the effects of the polar region on the Inter-Satellite Links. In this paper, we explore the unique characteristics of Walker Delta constellation, and present SER, a scalable and efficient routing algorithm based on the topology features. SER only uses orbit numbers and satellite numbers of source and destination to calculate the shortest path, therefore, flooding link state information is not required. SER has
$O(1)$
computational complexity. Furthermore, SER only needs to be executed once at the source node, who writes the routing decision into packets, and subsequent nodes along the path adopt source routing to forward packets. Evaluation results show that the execution time of SER is always kept at about
$40us$
, regardless of the network scale, and 94.03 % of the paths output by SER are no more than 10% longer than those output by OSPF.