ASTRA: ADMM-Accelerated Topology Reconfiguration for Dynamic Satellite Constellations

Dynamic topology reconfiguration is central to the reliability and efficiency of large satellite constellations, yet many existing approaches rely on idealized assumptions such as full constellation deployment or uniform orbital spacing. We present Adaptive Satellite Topology via Regret-Aware learning (ASTRA), a theoretically-grounded framework for dynamic satellite topology reconfiguration that builds on an online learning formulation and makes it computationally practical. ASTRA combines an ADMM-based offline solver with efficient online updates for both online gradient descent and online conditional gradient, yielding markedly cheaper constrained updates than generic optimization pipelines. On the theory side, we show that for a relevant class of entry-wise nonzero utility matrices, the objective is strongly convex, which yields logarithmic static regret for online gradient descent, and we further instantiate known dynamic-regret guarantees under inexact ADMM inner loops. Empirically, ASTRA matches or improves topology quality, presenting a good trade-off with computational time on synthetic constellations, and it remains effective on real Starlink data under partial deployment and non-uniform spacing, where idealized structural assumptions break down. These results position ASTRA as an efficient and theoretically grounded approach to topology reconfiguration in realistic Low Earth Orbit networks.

Considered Metrics

We compare our method with the state-of-the-art on both synthetic and real-world data and present metrics for the graphs generated, viz, total number of edges in the graph, ``E''; average degree of a satellite, ``A-Deg''; number of connected components, ``CC''; average shortest path, ``A-SP''; and the wall clock time in seconds, ``Time (s)''. Wall clock time experiments were executed on an M5 Pro MacBook Pro CPU, with Starlink metric experiments executed in 1 core of an Intel(R) Xeon(R) Gold 6330. Our synthetic dataset consists of an Iridium-like constellation with six elliptical orbital planes, each one with eleven satellites per plane. For real-world data, we consider a constellation with 1591 Starlink satellites, distributed across 50 orbital planes, containing between 14 and 64 satellites, whose state was retrieved every five minutes, during a period of 24 hours.

Iridium-like Constellation

In the following table we summarize the results of ASTRA and the different methods we compare it with in an Iridium-like constellation. We see that +Grid and ×Grid are the fastest methods, although the latter presents the lowest connectivity metrics and the highest shortest path. Both Motif and DoTD achieve the best network connectivity out of all the methods, although Motif takes a much longer time to achieve it. Both GUTO and ASTRA achieve smaller average shortest path length and comparable connectivity with DoTD and Motif. Furthermore, GUTO and ASTRA are equivalent, with ASTRA requiring approximately 22% less execution time.

Metrics	E ↑	A-Deg ↑	CC ↓	A-SP ↓	Time (s) ↓
+Grid	130	3.94	1	4.036	0.001
×Grid	124	3.76	1	4.978	0.001
DoTD	131	3.97	1	4.412	0.023
Motif	132	4.00	1	4.292	1.326
GUTO	128	3.88	1	3.767	0.091
ASTRA	128	3.88	1	3.767	0.071

Real-world Starlink Constellation

We evaluate our method and compare it to the state-of-the-art on Starlink data. At each time step, the algorithms are applied to generate a candidate topology. The metrics reported in each table correspond to the mean values and their respective standard deviations across all time steps. Since the average shortest path is defined only for topologies consisting of a single connected component, we report this metric exclusively for the topologies that satisfy this condition, thus denoting it as “A-SP*”. In this scenario, we do not evaluate Motif, as its implementation is not designed to support constellations with orbital planes containing a varying number of satellites. A key qualitative distinction in the Starlink setting is connectivity. While several baselines are faster or competitive on some local graph statistics, only GUTO and ASTRA attain fully connected topologies in at least some runs. This is important because the average shortest path is only meaningful as a full-network connectivity metric in that regime. Accordingly, the most relevant comparison is between GUTO and ASTRA: ASTRA preserves the connectivity quality of GUTO while reducing computational cost. By contrast, the remaining baselines often yield fragmented topologies, which limits direct comparison in terms of end-to-end path efficiency.

		Metrics
Method	Approximation	E ↑	A-Deg ↑	CC ↓	A-SP* ↓
+Grid	---	2869.14 ± 14.123	3.608 ± 0.017	9.038 ± 2.019	---
×Grid		2468.77 ± 19.325	3.205 ± 0.026	3.346 ± 1.314	---
DoTD		3183.16 ± 0.586	3.998 ± 0.001	4.211 ± 1.436	---
GUTO	H	2900.95 ± 13.033	3.650 ± 0.015	1.233 ± 0.491	15.742 ± 0.388
ASTRA		2900.24 ± 13.058	3.649 ± 0.015	1.264 ± 0.533	15.760 ± 0.381
GUTO	H+C	2797.16 ± 23.664	3.544 ± 0.025	1.642 ± 0.878	11.771 ± 0.226
ASTRA		2795.63 ± 23.506	3.542 ± 0.025	1.646 ± 0.878	11.817 ± 0.224

Wall-clock time

In terms of wall-clock time (over 10 runs), ASTRA achieves 83% faster execution time on average when compared with DoTD and 15% when compared with GUTO. Hence, ASTRA should be viewed as an efficient solver that retains the desirable connectivity behavior of GUTO under realistic partial-deployment and non-uniform-spacing conditions. Both +Grid and ×Grid are significantly faster than other methods, due to the trade-off between computational cost and how dynamic an approach is.

Algorithm	+Grid	×Grid	DoTD	GUTO	ASTRA
Time (s)	0.021 ± 0.001	0.026 ± 0.001	3262.927 ± 48.097	665.027 ± 2.093	567.949 ± 5.615