BiCayley: Traffic-Aware 3-ISL Topology Optimization via Bipartite Cayley Graph

Abstract

Low Earth Orbit (LEO) satellite constellations utilize Inter-Satellite Links (ISLs) to ensure global network connectivity. While the 4-ISL grid is a common academic assumption, operational reports from industry leaders like Starlink reveal a shift toward hardware-constrained 3-ISL configurations to optimize the trade-off between networking performance and deployment costs. However, existing 3-ISL designs, such as the Honeycomb topology, remain predominantly traffic-agnostic, leading to severe path inflation under non-uniform global traffic demands. In this paper, we propose BiCayley, a traffic-aware optimization framework that constructs 3-ISL topologies using Bipartite Cayley graph. By leveraging the structural homogeneity and vertex transitivity of Walker-Delta constellations, BiCayley collapses the NP-hard adjacency matrix optimization problem into a low-dimensional search over global generator offsets. Guided by a global Gravity-model traffic matrix, we employ Parallel Simulated Annealing (PSA) to identify optimal offsets that minimize propagation delay and nodal processing delay. Evaluations on Starlink configurations demonstrate that BiCayley significantly outperforms the state-of-the-art Honeycomb topology and Grid topology. In asymmetric Shell, BiCayley reduces Average Shortest Path Length (ASPL) and Average Hop Count (AHC) by 80.0% and 63.4% compared to Honeycomb, and 46.0% and 42.8% compared to the Grid. In symmetric Shell, BiCayley achieves a 23.4% reduction in ASPL over Honeycomb, delivering performance within 4.5% of the Grid. Our results demonstrate that BiCayley provides a robust, zero-handover architecture that aligns logical connectivity with real-world terrestrial demands.