⚡ electrical engineering

Duality-Guided Graph Learning for Real-Time Joint Connectivity and Routing in LEO Mega-Constellations

This paper proposes DeepLaDu, a Lagrangian duality-guided deep learning framework that utilizes a graph neural network to instantly infer congestion prices for jointly optimizing laser inter-satellite link connectivity, routing, and flow allocation in dynamic LEO mega-constellations, achieving near-optimal throughput with real-time computational efficiency.

Original authors: Zhouyou Gu, Jinho Choi, Tony Q. S. Quek, Jihong Park

Published 2026-01-30

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zhouyou Gu, Jinho Choi, Tony Q. S. Quek, Jihong Park

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive, high-speed internet network floating in space, made up of thousands of satellites circling the Earth like a swarm of bees. This is a LEO (Low Earth Orbit) mega-constellation, similar to the Starlink system. To make this network work, these satellites need to talk to each other using invisible "laser beams" (like high-tech flashlights) instead of radio waves.

However, managing this space internet is incredibly hard for three reasons:

Limited Flashlights: Each satellite only has a few laser terminals (flashlights). It can't shine a beam in every direction at once; it has to choose its neighbors carefully.
Moving Targets: The satellites are zooming around the Earth at 17,000 mph. The "neighbors" they can see change every second.
Traffic Jams: Some parts of the world (like big cities) need way more internet than others (like the ocean). If the satellites don't route traffic smartly, some laser beams get clogged while others sit idle.

The Problem: The "Traffic Cop" Dilemma

Traditionally, to figure out which satellites should connect and how to route data, computers have to run complex math problems over and over again. It's like trying to solve a giant, shifting puzzle while the pieces are still moving. By the time the computer figures out the best solution, the satellites have already moved, and the puzzle has changed. This takes too long for real-time internet.

The Solution: DeepLaDu (The "Intuitive Traffic Cop")

The authors of this paper created a new system called DeepLaDu. Instead of solving the puzzle from scratch every time, they trained a Graph Neural Network (GNN)—a type of AI that is really good at understanding maps and connections—to act like an experienced traffic cop who can "feel" the traffic instantly.

Here is how it works, using a simple analogy:

1. The "Congestion Price" Metaphor

Imagine every possible laser link between two satellites has a "price tag" attached to it.

If a link is free and empty, the price is $0.
If a link is crowded and about to get jammed, the price goes up to $100.

In the old way, the computer would slowly adjust these prices over many rounds of calculation to find the perfect balance. This is too slow.

DeepLaDu's trick: The AI looks at the whole map of satellites and the current traffic demand, and in a single split-second glance, it predicts exactly what those "price tags" should be. It doesn't guess randomly; it learned from thousands of practice runs what a "good" price looks like for a specific traffic jam.

2. The Three-Step Decision Process

Once the AI predicts these "congestion prices," the system makes three quick decisions:

Who connects? Satellites connect to neighbors where the "price" is low (meaning the link is needed and not too crowded).
Where does the data go? Data takes the path with the lowest total "price" (the cheapest route), avoiding the expensive, jammed links.
How much data? The system calculates exactly how much data to send on each path to maximize the total speed without breaking anything.

Why This is a Big Deal

The paper claims that DeepLaDu is a game-changer for two main reasons:

Speed: The old method (iterative math) takes a long time to calculate. DeepLaDu does it in a fraction of a second (milliseconds). This is fast enough to keep up with the satellites as they zoom around the Earth.
Performance: In their simulations, DeepLaDu moved 20% more data through the network than older, simpler methods. In scenarios where satellites had very few laser terminals (making the job very hard), it performed up to 50% better.

The Bottom Line

Think of the old method as a driver trying to navigate a city by checking a paper map, calculating the route, driving a block, realizing the map is outdated, and recalculating.

DeepLaDu is like a driver with a super-intelligent GPS that instantly knows the traffic conditions, predicts the best route, and tells you exactly where to go before you even turn the key. It allows the space internet to run faster, smoother, and handle more traffic without getting stuck in space jams.

The authors tested this on a realistic model of a Starlink-like network and proved that their AI can make these complex decisions fast enough to work in the real, moving world of space.

Technical Summary: Duality-Guided Graph Learning for Real-Time Joint Connectivity and Routing in LEO Mega-Constellations

Problem Statement
Low Earth Orbit (LEO) mega-constellations utilize Laser Inter-Satellite Links (LISLs) to form high-capacity, non-terrestrial network backbones. However, managing these networks presents a significant challenge due to three primary factors:

Hardware Constraints: Laser Communication Terminals (LCTs) are scarce, and each terminal can sustain only one active link at a time due to mechanical pointing constraints and limited Field-of-Regard (FOR).
Dynamic Topology: The constellation graph is time-varying due to orbital dynamics, causing link feasibility and traffic hotspots to change rapidly.
Joint Optimization Complexity: The problem requires simultaneously establishing LISL connections, routing traffic, and allocating flow rates under heterogeneous global traffic demands and gateway availability. This is formulated as a Mixed-Integer Program (MIP), which is NP-hard and computationally prohibitive for large-scale, real-time operation. Traditional iterative optimization methods (e.g., subgradient descent) are too slow to adapt within the "coherent time" of the constellation graph (the duration the topology remains largely unchanged, typically ~1 second for Starlink-like systems).

Methodology: DeepLaDu
The paper proposes DeepLaDu, a Lagrangian duality-guided deep learning framework that replaces iterative optimization with a single-pass inference. The core methodology involves:

Lagrangian Dual Decomposition: The joint optimization problem (P1) is relaxed by moving the per-link capacity constraints into the objective function using Lagrange multipliers ( $\lambda$ ). These multipliers are interpreted as edge-wise congestion prices.
- High prices indicate tight capacity constraints, discouraging traffic routing over those links while prioritizing the establishment of those links to increase capacity.
- This decomposition separates the problem into three independent subproblems solvable via Maximum Weight Matching (MWM) for connections, Shortest Path First (SPF) for routing, and Linear Programming (LP) for rate allocation.
Graph Neural Network (GNN) Inference: Instead of iteratively updating $\lambda$ via subgradient descent, a Graph Attention Network (GATv2) is trained to directly infer the optimal congestion prices from the constellation state in a single forward pass.
- Input: The satellite adjacency graph ( $G_{SAT}$ ) where nodes represent satellites (features: traffic serving/demand rates) and edges represent connectable LISL pairs (features: aggregate link capacity).
- Output: Lagrange multipliers ( $\lambda$ ) for all neighboring satellite pairs, bounded between [0, 1].
Subgradient-Based Training: Since the dual function is non-differentiable due to the underlying MIP structure, the GNN is trained using a loss function derived from the subgradient of the dual function. The training loop samples constellation states, computes the GNN's predicted prices, solves the decomposed subproblems to obtain the subgradient, and updates the GNN weights. This provides direct, edge-level feedback on congestion prices, unlike prior works that rely on coarse graph-level or node-level metrics.

Key Contributions

Formulation: The joint LISL connection, routing, and rate allocation problem is formulated as a mixed-integer optimization over time-varying graphs and decomposed via Lagrangian duality.
DeepLaDu Framework: A novel framework that trains a GNN to predict edge-wise congestion prices in one step, eliminating the latency of iterative dual updates.
Training Mechanism: Introduction of a subgradient-based edge-level loss function that enables scalable and stable training by providing direct feedback on link-level decisions.
Theoretical Analysis: Proof of convergence to a stationary point under mild assumptions and a complexity analysis showing that the approach scales polynomially with constellation size, making it suitable for real-time operation.
Performance Evaluation: Extensive simulations on realistic Starlink-like constellations with optical and traffic constraints.

Results
Simulations demonstrate that DeepLaDu achieves the following:

Throughput Gains: Up to 20% higher network throughput compared to non-joint or heuristic baselines (e.g., grid-based matching, random matching, or separate optimization). In scenarios with extreme LCT scarcity, the gain reaches up to 50%.
Computational Efficiency: DeepLaDu matches the performance of iterative dual optimization (LaDu) but with orders-of-magnitude lower computation time. It operates well within the constellation's coherent time (approx. 1 second), whereas iterative methods often exceed this limit.
Scalability: The method maintains performance across varying constellation sizes (500 to 1500 satellites) and different constellation types (Starlink vs. OneWeb).
Ablation Studies: The method consistently outperforms baselines across varying LCT configurations, pointing jitter, and beam angular spreading.

Significance and Claims
The paper claims that DeepLaDu provides a scalable and interpretable solution for real-time resource coordination in non-terrestrial network backbones. By embedding the principled optimization structure of Lagrangian duality into the learning process, the method ensures that the learned congestion prices retain their economic interpretation as link-level signals. The approach effectively transforms an iterative, latency-intensive optimization problem into a computationally efficient, one-shot inference procedure, addressing the critical need for rapid reconfiguration in dynamic LEO mega-constellations. The authors note that while the current work focuses on deterministic settings, future extensions could incorporate traffic prediction uncertainty and online learning.