CS Paper Radar

Lightweight Onboard Routing and Topology Co-Construction for Autonomous GNSSs

Huan Yan, Juan A. Fraire, Rongqin Yang, Wenfeng Li, Kanglian Zhao

eess.SY ·submitted 2026-09-07 05:21 UTC · v2

Abstract

Global navigation satellite systems (GNSSs) can already plan their inter-satellite link (ISL) topology onboard, leaving routing as the last step toward autonomous networking. In GNSS ISLs, each satellite links to at most one peer per time slot. We exploit this structure to replace end-to-end path search with a single backward sweep over the slots. The proposed method, DS-SMFP, propagates earliest-arrival times backward from each destination and outputs a STORE/FORWARD decision for every slot, satellite, and destination, in time linear in the number of slots and with working memory independent of the planning horizon. Because each slot needs only its own topology and the delivery state of the next one, routing can steer link selection while the topology is built. This slotwise dependency enables Master-Oriented Topology--Routing Co-Construction (MTRCC), which favors traffic to and from a master satellite performing onboard orbit determination. In a 24-h, 30-satellite BeiDou scenario, DS-SMFP matches the delays of Contact Graph Routing (CGR) and shortest path tree (SPT) routing while running over 180 times faster and using over 36 times less peak routing working memory. Compared with fair contact plan (FCP) topology, MTRCC reduces mean master-related traffic delays by over 10\%, with an approximately 3\% increase in mean PDOP. This paper provides a methodological foundation for efficient autonomous GNSS networking.

Comment
15 pages, 6 figs

Closest papers

Nearest neighbours by meaning across the whole index.

Hierarchical Traffic Engineering for Scalable Software-Defined Satellite Networks

eess.SY ·2026-11-18 ·Mohamed Khiari, Wiem Abderrahim, Olfa Ben Yahia, Fatma Abdelkefi, Wessam Ajib +1 more
similarity 0.64
Abstract

Future satellite systems are shifting toward regenerative payloads that interconnect many modem banks into a reconfigurable on-board network. However, conventional constellation-level routing overlooks intra-payload congestion and load imbalance, which can limit the traffic each satellite can accommodate. This paper proposes a hierarchical software-defined networking (SDN)framework for traffic engineering (TE) across both the constellation and payload levels. The system is represented by a two-level graph, where each satellite node in the constellation graph is expanded into an internal network of interconnected modem banks. The proposed hierarchical payload-aware allocation (HPAA) algorithm coordinates the two levels through the exchange of assigned traffic demand and advertised capacity budgets. Simulation results show that, under heavy load, HPAA delivers about 9 times the throughput of shortest-path routing, with 17% lower end-to-end delay and no packet loss. These findings highlight that hierarchical control accounting for the on-board network constraints of regenerative payloads is a key lever to improve the performance of satellite constellations.

0.23

Computing All-Pairs Shortest Communication Time Paths for Periodically Varying Satellite Networks

cs.NI cs.DC ·2026-10-12 ·Koushik Sinha, Dibakar Saha, Sai Puppala, Bhabani P. Sinha
similarity 0.63
Abstract

We address the problem of designing an efficient algorithm for computing the all-pairs shortest-time paths in time-varying networks, specifically targeting the dynamic topological characteristics of low earth orbit (LEO) satellite constellations. We model such temporal graphs as $G = (V, E_t)$, where $V=\{1, 2,\ldots , n\}$ is the set of $n$ vertices in the graph, and $E_t$ is the set of $M$ time-varying edges considered over a total time window of size $T = Mτ$, $τ$ being the duration of each interval in that time window. For such a network, our algorithm finds the all-pair shortest paths in $O(M^2n^3)$-time. A key advantage of our approach is its computational structure, which mirrors two matrix multiplication steps, first in the forward direction and then in the backward direction. This structure of the algorithm makes it exceptionally suitable for parallelization on SIMD architectures like GPUs, thereby offering a significant speedup over traditional shortest-path algorithms and enabling efficient, network-wide message routing in rapidly changing LEO satellite constellations.

0.23

Resource Slicing for Time-Sensitive Data Traffic in Non-Terrestrial Networks with FSO ISLs

eess.SP ·2026-10-22 ·Abid Afridi, Alexis A. Dowhuszko, Risto Wichman, Jyri Hämäläinen
published similarity 0.62
Abstract · 6 pages, 7 figures, 1 table. Accepted for presentation at IEEE GLOBECOM 2026 Workshops

In multi-hop Low Earth Orbit (LEO) satellite networks, time-sensitive packets experience queueing across multiple satellite hops, causing per-hop waiting times that accumulate and make the maximum end-to-end (E2E) delay difficult to guarantee. This paper presents a novel multi-hop slicing framework that reserves time-frequency resources for each time-sensitive flow of data originating at each satellite, aiming to maintain the reservation of communication resources along every inter-satellite link (ISL) on its route to the ground station (GS). The number of time-frequency resource blocks (RBs) reserved per-hop is determined from the data packet arrival statistics, E2E delay budget, and target level of reliability. Reservations on consecutive links are temporally aligned to enable pipelined forwarding of the time-sensitive data flows aggregated from terrestrial user terminals on the different LEO satellites. We evaluate the proposed framework against conventional scheduling and resource-allocation baselines, including pure time-division multiple access (Pure-TDMA), first-in-first-out (FIFO), and farthest-satellite-first (FSF), over the same multi-hop LEO satellite path. Under light traffic conditions, the baseline schemes provide comparable delay performance; however, their high-percentile delays increase sharply as data traffic load grows, whereas the proposed framework exhibits substantially slower delay growth. At the high arrival rate and high reliability target considered, the proposed scheme requires about 31 ms, a factor of 2.5-6.8 lower than the 76, 180, and 210 ms required by FIFO, FSF, and Pure-TDMA.

0.43

Joint Geometric and QoS-Aware Routing in Optical LEO Satellite Networks via DRL

eess.SP ·2026-10-01 ·Abdulrahman Al-Hababi, Meysam Ghanbari, Mohammad Taghi Dabiri, Rula Ammuri, Mazen Hasna +1 more
similarity 0.61
Abstract

Optical inter satellite links ISLs are becoming the backbone of modern LEO constellations offering high capacity and low latency but introducing stringent geometric and physical layer constraints Routing in such networks must therefore account for time varying topology jitter induced outage and the heterogeneous reliability of intra and inter plane optical links aspects that classical shortest path or existing learning based schemes do not fully capture This paper develops a joint geometric and QoS aware routing framework for optical LEO networks We derive a closed form outage expression under Gaussian beam propagation with pointing errors and obtain analytical maximum feasible link ranges for different ISL classes These relations remove beam divergence from the optimization variables and embed optical feasibility directly into the routing layer leading to a latency reliability capacity constrained routing formulation that is proved to be NP hard To enable scalable decision making we cast snapshot routing as a Markov decision process and introduce an angle constrained masked deep Q network AC MDQN that integrates optical feasibility masks potential based latency shaping and a geometry aware corridor filter around the source destination great circle path This design significantly reduces the effective action space complexity while preserving near optimal routing choices Simulations on a Starlink like constellation demonstrate that AC MDQN achieves end to end latency within 1 to 2 percent of constrained shortest path solutions remains robust under varying pointing jitter and supports controllable hop latency trade offs through reward design The results confirm that the proposed framework provides an efficient and physically consistent routing solution for large scale optical LEO networks

0.24

Scalable Full-Horizon SFC Deployment over Predictable SAGIN Topologies via Configurable Column Generation Framework

cs.NI ·2026-11-06 ·Hang Li, Hao Huang, Yihu Xu, Zixuan Kong, Yanling Jin
similarity 0.61
Abstract · 18 pages, 10 figures, 4 tables

Space-air-ground integrated networks (SAGINs) integrate heterogeneous communication and computing resources to support ubiquitous services. Service function chains (SFCs) enable complex services to be composed of ordered functions and executed collaboratively across these resources. Mobility continuously reshapes connectivity throughout service execution, yet much of the resulting topology evolution is predictable. Decisions based only on isolated topology snapshots may therefore overlook valuable future connectivity. We formulate an admission-first, cost-aware model on a time-expanded graph for SFC deployment. Our key observation is that temporal feasibility is request-specific, whereas global coupling arises mainly from shared-resource competition. We therefore develop a configurable column-generation framework in which complete request deployments form columns and a restricted master problem coordinates admission and resources. SAGINFE, a fast constructive heuristic built on per-flow embedding (PFE), supplies a standalone feasible solution and initial columns. Configurable pricing schedules combine early-terminated and stricter searches, supplemented by selective PFE candidates. Candidates undergo feasibility and exact reduced-cost checks. Request-wise pricing can run in parallel, followed by finite-pool integer selection. The default configuration improves the admission-first objective over initialization on all 120 main instances. Four pricing workers achieve up to a 2.69-fold median pricing-stage speedup while preserving admitted request counts in the tested cases.

0.20

OrbitWeaver: LLM Agent Planning with Simulation Feedback for Optically Interconnected Orbital GPU Clusters

cs.DC eess.SY ·2026-11-13 ·Pengcheng Luo, Bowen Zhang
similarity 0.60
Abstract

Space-based data-center designs increasingly consider GPU computing formations connected by inter-satellite optical links. With limited neighboring connections, jobs assigned disjoint GPUs can still contend on shared relay paths. Rank placement and communication priorities jointly affect this contention and the readiness of downstream computation. We present OrbitWeaver, an offline large language model (LLM) agent planner that jointly optimizes rank placement and communication order. Guided by communication structure, execution dependencies, and simulation feedback, the agent constructs and refines plans that coordinate shared-link access with computation progress. This coordination reduces contention and dependency blocking, shortening mean job completion time (JCT). Simulation experiments on optically interconnected orbital GPU clusters show that OrbitWeaver reduces aggregate mean JCT by 6.2-33.5% relative to the state-of-the-art baselines CASSINI, Crux, and Symphony. These results demonstrate the value of LLM-guided planning for efficient concurrent computing in orbital GPU clusters.

0.23

Half-Slot Link Scheduling for Open GNSS with $x$-Tx $y$-Rx Multibeam Phased Array Antennas

eess.SY ·2026-10-22 ·Huan Yan, Kanglian Zhao, Wenfeng Li, Jinjun Zheng, Ziyu Wang +1 more
similarity 0.60
Abstract · 20 pages and 10 figs

Global Navigation Satellite Systems (GNSSs) are evolving from closed navigation constellations toward open space infrastructure capable of serving extensive spacecraft users. This evolution requires the constellation to support navigation ranging, telemetry (TM) return, and telecommand (TC) delivery for users while preserving its own ranging and communication functions.Existing phased-array payloads onboard BeiDou satellites provide one transmit (Tx) beam and one receive (Rx) beam. Such a configuration was designed mainly for intra-constellation operation, and can become a resource bottleneck when a large number of users share the same link opportunities. Upgrading GNSS satellites to phased-array terminals with $x$-Tx and $y$-Rx beams is therefore a natural enhancement. This paper develops a staged dynamic half-slot link scheduling framework (SDHSS) for open GNSS with $x$-Tx $y$-Rx multibeam phased-array antennas. The framework models navigation, TM, and TC as three different services, reserves the essential ranging and ground-access opportunities required by the GNSS constellation, and then allocates the remaining half-slot beam resources according to current service demand. To support multibeam concurrency, feasible links are selected through dynamic service-layer ordering and beam-copy matching. Simulations based on a BeiDou constellation show that the proposed method protects GNSS baseline operation and provides stronger external navigation, TM, and TC performance than fair contact planning. The results further show that additional Tx and Rx beams can be effectively converted into multi-service capability. This work establishes a link-scheduling approach for extending GNSS from constellation-internal operation to large-scale spacecraft service support.

0.30

Continuum: Boundary-State-Aware Deterministic Scheduling in Dynamic LEO Networks

cs.NI ·2026-11-18 ·Siqi Yang, Zonghui Li, Chaoqun You, Yue Gao
similarity 0.59
Abstract

Low Earth Orbit (LEO) constellations support mission-critical services requiring bounded latency and predictable delivery. However, conventional snapshot-based schedulers discard the forwarding progress of unfinished time-triggered traffic across topology transitions, degrading schedulability and timing consistency. We present Continuum, aboundary-state-aware rolling-horizon scheduling framework. Continuum inherits buffered-node and arrival-time information, jointly optimizing remaining routes and transmission slots, and refines latency to improve timing consistency while preserving original timing constraints. Ablations show up to 16.6 percentage points higher schedulability from boundary-state inheritance and a 10.9-37.7 times reduction in mean jitter from joint alignment. Scalability experiments evaluate synthesis performance for workloads of up to 10K flows.

0.18