Bidirectional Path Search for Efficient Routing in LISL-Enabled Multi-Layer LEO Mega-Constellations

Future low Earth orbit (LEO) mega-constellations will feature large-scale, dynamic, and multi-layer network topologies, posing new challenges for efficient routing. Traditional shortest-path algorithms, originally designed for two-dimensional planar networks, are inadequate for the three-dimensional, time-varying structure of LEO networks. The deployment of laser inter-satellite links (LISLs), while extending communication reach, significantly increases node density and exacerbates computational complexity. To address these issues, we propose Dynamic topology and Bidirectional Search (DBS), a novel algorithm tailored for routing in LISL-enabled multi-layer LEO mega-constellations. DBS integrates a bidirectional search strategy with customized cost functions for effective search-space pruning, substantially reducing computational overhead while preserving path optimality. We develop three DBS variants: DBS-OP for optimal routing, DBS-FS for fast routing, and DBS-RC for rapid path recovery. Theoretical analysis and extensive simulations demonstrate that DBS-OP achieves optimal paths with a significantly smaller search space than conventional methods, DBS-FS delivers near-optimal performance with accelerated execution, and DBS-RC ensures robust recovery under diverse failure scenarios. Overall, DBS provides an efficient, scalable, and adaptable routing solution for future large-scale LEO networks.