Satellites in low Earth orbit move at about 7.5 km/s, so the links between them form and break every few seconds to minutes. Routing traffic across such a network while keeping any one satellite's battery from running flat, especially during eclipse when solar charging stops, is a moving optimization problem. Second-order methods are the natural tool for it. These are Newton-type methods that rescale each step by the problem's curvature, and they track moving optima far faster than gradient methods. The decentralized versions compute the Newton step by passing messages along the network's own links. That same design is also why they fail here: the step is only valid if the links stay fixed while the messages circulate, and in orbit they do not.
We propose a way to keep the Newton step valid under link churn. Satellite motion is predictable from published orbit parameters, so every node knows ahead of time which of its links will disappear during the next few message rounds. Before computing the step, we take the curvature that a soon-to-vanish link would have carried and fold its absolute value into the diagonal at both endpoints. This is a regularizer set by the topology, with no free parameter. It produces a curvature estimate that uses only links that will actually exist, and it is provably an upper bound on the true curvature, so every step remains a safe descent step. Adding a logarithmic barrier on each node's projected battery charge makes nearly depleted relays show up as high-curvature nodes. The Newton step then moves traffic away from them without any separate energy heuristic.
Core Claim
Decentralized second-order methods approximate the inverse Hessian with a truncated Neumann (Taylor) series. The Hessian is split into a diagonal part $D$ and an off-diagonal part $B$ whose nonzeros match the communication graph, and $K$ terms of the series cost exactly $K$ neighbor-to-neighbor message rounds. This is the method behind Dynamic ESOM, the Newton prediction-correction method of Simonetto et al., ESOM-K, and the network-utility Newton method of Wei, Ozdaglar and Jadbabaie. All four let the objective move over time but keep the graph static. If an edge drops out between hop 1 and hop $K$, the series is no longer computing what it claims to compute.
Our fix works as follows. Let $H$ be the symmetric Hessian of the routing problem and $\mathcal{E}_{\text{lost}}$ the set of edges that the ephemeris predicts will break before the $K$-round exchange finishes. For each such edge with coupling $h_{ij}$ and sign $s_{ij}=\mathrm{sign}(h_{ij})$, we replace $H$ with
$$\hat H \;=\; H + \sum_{(i,j)\in\mathcal{E}_{\text{lost}}} |h_{ij}|\,(e_i - s_{ij}e_j)(e_i - s_{ij}e_j)^\top ,$$
where $e_i$ is the $i$-th unit vector. Each added term cancels the off-diagonal entry $h_{ij}$ and adds $|h_{ij}|$ to the diagonal entries $i$ and $j$. So $\hat H$ has exactly the sparsity of the surviving graph, and $\hat H - H$ is a sum of positive semidefinite rank-one matrices, which gives $\hat H \succeq H$. This has three consequences. First, the Neumann series on $\hat H$ uses only links that will exist. Second, the resulting step minimizes a model that upper-bounds the true local quadratic, so it cannot overshoot. Third, the diagonal only grows, so the spectral radius of $D^{-1/2}BD^{-1/2}$ shrinks and the truncated series converges faster rather than slower.
This belongs to the same family as the absolute-value eigenvalue filtering used in Sassha and in projected Newton solvers (Chen et al.). Those methods filter the spectrum of the curvature; we apply the absolute value edge by edge, and the topology decides which edges.
The closest conceptual relative is Lazy Hessians, which compensates for deliberately stale curvature by inflating a scalar cubic regularizer in proportion to staleness times the Lipschitz constant. We compensate for staleness that happens involuntarily, because links die. The compensation is exactly the curvature that is lost, placed exactly where it is lost, rather than a global scalar.
Research Program
Routing problem. The optimization problem is multi-commodity flow over the inter-satellite and ground links in a short horizon window. Each link has a strictly convex congestion cost $\phi_l$ in its flow $x_l$, standing in for queueing delay. Each node has a battery barrier. We minimize
$$\sum_{l}\phi_l(x_l)\;-\;\mu\sum_{i}\log\!\big(E_i(t)-E_{\min}-\textstyle\sum_{l\in\text{out}(i)}\epsilon_l x_l\big)$$
subject to flow conservation. Here $E_i(t)$ is node $i$'s predicted charge at the end of the window, $E_{\min}$ is the safe floor, $\epsilon_l$ is the transmit energy per bit on link $l$, and $\mu$ is the barrier weight.
Decentralized Newton step. We work in the dual, as Wei et al. do, with one price per node for flow conservation. The dual Hessian is a weighted graph Laplacian whose weights come from link curvatures, plus barrier terms that are local to each node. Its nonzeros therefore follow the physical link graph, and $K$-term Neumann products reduce to $K$ rounds of local messages.
The barrier supplies the energy awareness. As a node's charge slack shrinks, its barrier curvature grows like $\mu/\text{slack}^2$. That large diagonal entry has two effects: the node's dual price for relaying rises, and the node's own Neumann terms decay quickly. We use the second effect to allow a per-node truncation order. A depleted node can stop after fewer terms with a computable error bound, which saves its radio energy. This turns the "uniform $K$ regardless of battery" limitation noted for ESOM-type methods into a rule derived from the curvature.
Theory. We will prove descent and tracking bounds for the lumped step under a bounded churn rate. We expect the proof to extend the prediction-correction analysis of Simonetto et al.. The expected price is a tracking error that grows with the curvature mass lumped per window, since that mass is how far $\hat H$ is from $H$.
Robustness to wrong predictions. Ephemeris prediction is not perfect. Ground stations fail, and Tiansuan documents hardware anomalies that simulators idealize. For an edge that breaks without warning mid-exchange, we add a fallback: the receiving node treats the missing message as zero and lumps that edge's coupling into its own diagonal locally. This keeps $\hat H\succeq H$ one-sidedly at that node. We will measure how much tracking degrades as the fraction of unpredicted breaks rises.
Simulation setup. We will build the evaluation on the setup used by SkyLink: Starlink and OneWeb orbits propagated from two-line elements, with traffic demand drawn from population density (GPWv4). To this we add an eclipse-aware battery and solar-charging model of the kind SusCO uses to motivate its offloading. Before moving to orbit, we will check that the method reduces to known behavior on static benchmarks: the 50-network random topology suite of Wei et al. and the ill-conditioned quadratic with condition number 100 used for D-BFGS.
Baselines
Naive reference. Minimum-delay shortest-path routing, recomputed each time slot on the current graph, with no energy term. SkyLink reports that this is very poor: its own drop rate is 99% lower than Dijkstra and 95% lower than k-shortest paths. We include it only as the floor.
Strongest routing competitor: SkyLink with an energy term. SkyLink is a decentralized bandit that ranks each satellite's outgoing links by an upper-confidence score and splits traffic across the top links by water-filling. It is the strongest decentralized router reported on this benchmark: a 29% lower weighted sum of delay and drop rate than bent-pipe routing for 25.4 million users, and a cost increase under 10% when ground stations fail. Because SkyLink ignores battery state, we will give it a fair energy-aware version. We reimplement it and add a residual-energy penalty to the bandit reward, shaped like the WDM route weight (WDM). Both methods get the same orbits, the same traffic, the same battery model, and the same tuning budget for their free parameters (the penalty weight and exploration constant for SkyLink, the barrier weight and $K$ for ours). No reported result was found on Lacuna for SkyLink's battery lifetime. For energy, the only reported comparison point is SusCO's 11.36% to 26.07% reduction in satellite energy and up to 26.75% longer battery life. That result is against its own baselines and uses ground-station offloading rather than routing, so we cite it for scale, not as a head-to-head number. Beating SkyLink means extending time to first node below $E_{\min}$ at matched or lower drop rate and delay. If lifetime improves only at the cost of more drops, that does not count.
Strongest second-order competitor: Dynamic ESOM and the Wei et al. Newton method, run as published. Both use the $K$-hop series on whatever links the node believes exist when the exchange starts. We give them the same barrier objective. This comparison isolates what happens when a second-order method ignores churn. Beating them means fewer diverged or rejected steps, a lower optimality gap, and no loss on static graphs. On the static suite, Wei et al. report a mean of 924 iterations against 29,315 for dual subgradient, and our method must roughly match that.
Ablations that isolate the key ingredient. First, dropping predicted-lost edges without lumping: the sparsity is correct but there is no upper-bound guarantee. Second, a uniform diagonal damping $\lambda I$ in the style of Lin et al. and Huang, with $\lambda$ tuned per constellation on held-out orbits. Third, a scalar staleness-scaled regularizer in the spirit of Lazy Hessians. The upper bound is a centralized oracle that solves the same convex program with perfect foresight. It is not deployable, but it defines the optimality gap.
Why not just…?
Why not just use uniform damping $\lambda I$ with the current graph? This is the real threat. A single well-tuned $\lambda$ may match lumping on average. Where lumping should win is in the tails. The damping it adds is concentrated at the endpoints of links that are dying and is zero elsewhere, whereas uniform damping large enough to cover the worst churn event slows the whole network toward gradient descent. This is the same argument the spectral-filtering literature makes against large uniform shifts. We will sweep $\lambda$ with a generous tuning budget and report the full Pareto curve of tracking error against churn rate. If tuned uniform damping matches lumping across churn regimes and across constellations it was not tuned on, we will say so. In that case the contribution shrinks to a parameter-free way of choosing $\lambda$ plus the descent guarantee.
Why not just use a first-order method such as ADMM or dual subgradient, which exchanges fewer messages per step? The file's evidence points against it on conditioning. On a problem with condition number 100, D-BFGS reached $3\times10^{-4}$ error in 200 iterations while ADMM sat at 0.06, using about 10x fewer exchanges. On random network-utility problems, Newton needed 924 iterations against 29,315 for subgradient. A satellite network with near-depleted nodes is exactly an ill-conditioned problem, because barrier curvatures span orders of magnitude. Still, per-step message cost matters when links live only seconds. We will therefore compare in total radio Joules and in wall-clock time within a link's lifetime, not in iterations.
Why not just add battery state to a learned or bandit router such as SkyLink or a DDQN over time-expanded graphs? The energy-weighted SkyLink variant is our main baseline for exactly this reason. Its expected weakness is that its choices are local and give no guarantee: nothing stops two neighbors from both routing through the same weakening relay. The barrier formulation prevents this by construction. The DDQN approach of Jia et al. additionally needs offline training and was shown on 30 UAVs and 2 satellites, not a mega-constellation. If energy-weighted SkyLink matches our lifetime at equal drops, the Newton machinery is not justified for routing, and we would report that.
Why not just solve centrally on the ground? SkyLink's ground-station failure experiment shows bent-pipe cost rising over 67% when only 3% of the constellation is affected. Round trips to the ground also exceed short link lifetimes. We use the centralized solve only as the oracle for measuring the optimality gap.
Decisive Checks
The first check is a churn sweep on Starlink orbits. We compare lumped, dropped-edge, tuned uniform, and churn-unaware ESOM steps, measuring the fraction of non-descent steps and the optimality gap against the oracle. Lumping should keep non-descent steps at zero under predicted churn and degrade gracefully as unpredicted breaks are injected, from 0% up to beyond SkyLink's 3% failure setting.
The second check is a multi-orbit eclipse run against energy-weighted SkyLink. Metrics are time to first node below the charge floor, time to network partition, drop rate, delay, throughput, and control-plane Joules.
The third check is the static reduction: our method should roughly reproduce Wei et al.'s iteration counts on their 50-network suite.
The idea fails if the second check shows no lifetime gain at matched drops, or if the first check shows tuned uniform damping matching lumping out of distribution.
References
- A decentralized Second-Order Method for Dynamic Optimization
- A Quasi-newton prediction-correction method for decentralized dynamic convex optimization
- A Decentralized Second-Order Method with Exact Linear Convergence Rate for Consensus Optimization
- A Distributed Newton Method for Network Utility Maximization-I: Algorithm
- Sassha: Sharpness-aware Adaptive Second-order Optimization with Stable Hessian Approximation
- Stabler Neo-Hookean Simulation: Absolute Eigenvalue Filtering for Projected Newton
- Second-Order Optimization with Lazy Hessians
- Tiansuan Constellation: An Open Research Platform
- SkyLink: Scalable and Resilient Link Management in LEO Satellite Networks
- Commercial Dishes Can Be My Ladder: Sustainable and Collaborative Data Offloading in LEO Satellite Networks
- Decentralized Quasi-Newton Methods
- WDM: An Energy-Efficient Multi-hop Routing Algorithm for Wireless Sensor Networks
- A note on Platt's probabilistic outputs for support vector machines
- SPAN: A Stochastic Projected Approximate Newton Method
- Service Function Chain Dynamic Scheduling in Space-Air-Ground Integrated Networks