Huang, TzuhengTzuhengHuangChiang, ShenghaoShenghaoChiangLiu, PeifanPeifanLiuLiao, WanjiunWanjiunLiao2026-03-192026-03-192026-01-19https://www.scopus.com/record/display.uri?eid=2-s2.0-105028411110&origin=resultslisthttps://scholars.lib.ntu.edu.tw/handle/123456789/736440Future 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.falseBidirectional path searchefficient routinglow Earth orbit (LEO) satellitesmulti-layer mega constellationsjournal article10.1109/ton.2026.36554902-s2.0-105028411110