TRACE: A Graph-Constrained Transformer for Communication-Efficient Distributed Routing in LEO Constellations

Large-scale Low Earth Orbit (LEO) constellations often experience high node failure rates caused by dynamic environmental factors (random failures), such as satellite maneuvers, or by cyber or physical attacks on critical nodes (targeted attacks), which pose unique challenges for routing optimization. Traditional algorithms such as Dijkstra suffer from limited parallel scalability on GPUs due to irregular neighbor distributions, while deep learning methods lack generalization ability. To address these challenges, we propose TRACE (Topology-aware Routing via Adjacent-Constraint Encoding), a graph-constrained Transformer architecture equipped with a cascaded multi-head attention decoder for distributed dynamic routing in LEO domains. To improve algorithm throughput and resilience against random failures and targeted attacks, we further design NFD (Navigator–Follower Distillation), a self-distillation framework which enables each agent to learn routing policies from Monte Carlo episodes. Furthermore, a hierarchical distributed routing architecture is developed to extend the proposed method to multi-domain scenarios. Simulation results demonstrate that TRACE with NFD achieves near-optimal routing accuracy with controllable inter-domain errors, while significantly improving throughput compared with mainstream routing algorithms.