1
Capacity Scalability of LEO Constellations With Dynamic Link Failures Wei Li∗ ,
Min Sheng∗ , Fellow, IEEE
∗ State Key Laboratory of Integrated Service Networks, Xidian University, Xi’an, Shaanxi, 710071, China
arXiv:2605.12146v1 [cs.IT] 12 May 2026
Email: [email protected], [email protected]
Abstract—Dynamic link failures disrupt the connectivity and geometric symmetry of the constellation structure, thereby increasing protocol overhead and degrading the effective capacity for traffic transport. The fundamental relationship between constellation size and effective capacity under protocol overhead constraints remains unclear. To this end, we define capacity scalability as the ratio of constellation capacity under non-failure conditions to protocol overhead. Specifically, if ISL states follow a two-state discrete Markov chain and the maintenance period is k ≥ 1, the upper bound of capacity scalability under the uniform traffic pattern is O(1/n), where n is the number of satellites. With perfect information about the constellation topology, the upper bound can be achieved via shortest-path routing. For any given protocol, there exists an optimal constellation deployment scale in terms of capacity scalability. When the constellation size is below this optimum scale, capacity scalability increases with constellation size, thereby improving effective capacity. Increasing the maintenance period k can improve capacity scalability, but it does not change the fact that the capacity scalability converges to zero when the constellation size exceeds the optimal scale. Index Terms—Capacity Scalability, LEO constellations, overhead, dynamic link failure.
I. I NTRODUCTION S more satellites are deployed in low Earth orbit, the available orbital space resources have decreased rapidly, leading to an exponential increase in the frequency of collision avoidance maneuvers [1], [2]. Frequent maneuvers and unpredictable space weather (e.g., solar radiation, micro-space debris and single-event upsets) inevitably cause variations in inter-satellite link (ISL) states, thereby disrupting the connectivity and symmetry of the constellation [3]–[5]. However, the data transport capacity of the constellation is closely dependent on the stability of the constellation structure and the efficiency of the protocols [6], [7]. The main function of the protocols is to maintain ISLs with low overhead and to quickly plan multihop routing paths for data packets in the dynamic constellation structure. The operation of the protocols essentially consumes the capacity provided by the dynamic constellation structure. Therefore, there exists a fundamental trade-off between protocol overhead and constellation capacity, especially in large-scale constellations. This directly determines whether the capacity gain from increasing the number of satellites can be effectively used for transporting data packets in a constellation with dynamic link failures. Existing studies on capacity and protocol overhead are usually done separately. Research on constellation capacity mainly focuses on improving capacity and analyzing its influencing factors, such as traffic distribution [8]–[11], ISL
A
failures [12]–[14] and ISL establishment rules [15]–[18]. In contrast, research on protocol overhead mainly focuses on designing specific strategies, such as distributed or centralized routing [19]–[23], load balancing strategies [24]–[27] and ISL maintenance strategies [28], [29]. This makes existing results unable to explain how protocol overhead constrains capacity as the constellation scale increases, as well as how ISL evolution behavior affects protocol overhead. To fill this gap, we define capacity scalability as the ratio of constellation capacity under non-failure conditions to protocol overhead. Based on this definition, we analyze the fundamental behavior of capacity scalability under dynamic link failures. The total overhead includes contention overhead (σ), incurred during data packet routing and determined by the number of hops and the number of source–destination pairs, as well as consensus overhead (ω), incurred for ISL maintenance and determined by ISL evolution the maintenance period and the number of ISLs. Overall, the main contributions are summarized as follows: •
We use a two-state discrete-time Markov chain to describe the dynamic evolution and memory behavior of ISLs. The lower bound of the consensus overhead required to maintain each ISL is derived in terms of information entropy. Based on this result, the upper bound of capacity scalability under the uniform traffic model is obtained as √ 16 n = O(1/n), τ ≤ τ (n, k) = 1 + σn1.5 + 4nH̄k (α, β) (1) where α and β are the failure probability and the recovery probability, respectively. σ denotes the overhead incurred for transmitting a data packet over each hop. H̄k (α, β) = k −1 h(π1 ) + (k − 1) π1 h(α) + π0 h(β) is the lower bound of the consensus overhead required to maintain each ISL every k time slots, h(x) = −x log2 x− (1 − x) log2 (1 − x), x > 0. π1 and π0 are the steadystate probabilities of the ISL evolution. The overhead grows much faster,√at a rate of Θ(n1.5 ), than the capacity growth rate of Θ( n)1 . This indicates that there exists an optimal constellation size n∗ that maximizes capacity scalability. n∗ is determined by solving the equation 2σn1.5 + 4nH̄k (α, β) = 1. When n < n∗ , the capacity scalability increases as n increases, so increasing the
1 f (n) = O(g(n)) if there exist c > 0 and n > 0 such that f (n) < cg(n) 0 for n > n0 . f (n) = Ω(g(n)) if g(n) = O(f (n)). f (n) = Θ(g(n)) if f (n) = O(g(n)) and g(n) = O(f (n)).
2
constellation size is beneficial. In contrast, when n > n∗ , the capacity scalability converges to zero as n increases, so the gain from further increasing the constellation size converges to zero. As the contention overhead (consensus overhead) approaches zero, the optimal constellation size −2/3 is given by n∗ ≈ H̄k−1 (α, β) ((2σ) ). The results further indicate that, for the same reduction in overhead, the optimal constellation size is more sensitive to consensus overhead than to contention overhead. In particular, when the total contention overhead is constant (σ = c), the upper bound √ of capacity scalability increases from O(1/n) to O(1/ n), which merely reduces the convergence rate of capacity scalability to zero. To maintain the capacity scalability, therefore, it is necessary to reduce the number of source-destination pairs, the average hop count and the consensus overhead. • For any ISL failure evolution behavior, increasing the ISL maintenance period (k) can only improve capacity scalability but cannot change the inherent trend that capacity scalability converges to zero when n > n∗ . This is because the lower bound of the consensus overhead required to maintain each ISL is non-zero, i.e., α β h(α) + h(β) > 0. α+β α+β Furthermore, the capacity scalability is analyzed under different ISL failure behaviors. When the ISL state exhibits stronger memory, i.e., |µ| = |1 − α − β| is large, increasing the maintenance period k yields little improvement in capacity scalability. This is due to the high predictability of ISL evolution behavior. If an ISL is in a failed (non-failed) state at time slot t, it remains in the failed (non-failed) state at time slot t + k with high probability. We also observe that optimal capacity scalability is achieved when the ISL failure probability is low while the recovery probability is high. Simulation experiments are performed to validate the theoretical observations. The rest of this paper is organized as follows. The related work on existing studies is reviewed in Section II. The system model and ISL failure model are presented in Section III. In Section IV, the lower bound of consensus overhead, the upper bound of capacity scalability and the optimal constellation size in terms of scalability are derived. We discuss the impact of the maintenance period and ISL evolution behavior on the capacity scaling law separately in Section V. Based on the shortest-path routing strategy, in Section VI, we simulate the ISL evolution behavior and verify the upper bound of capacity scalability. ω ≥ H̄∞ (α, β) =
II. RELATED WORKS A LEO constellation with a one-satellite, four-link configuration is equivalent to a 2-Torus structure, except for polar constellations [8], [9], [18]. Under uniform traffic pattern, the capacity upper bound of a symmetric 2D-torus structure √ is 8 n, by applying bisection arguments [8]. This result shows that the capacity growth rate √achieved by increasing the constellation size is at most O(1/ n). Under this framework,
the lower bound on spare capacity for recovering from a link or node failure is derived, together with routing and restoration schemes that achieve this bound [9]. The results show that the spare capacity requirement for a link-based restoration scheme is nearly n times that for a path-based scheme. In [15]–[18], the effects of ISL establishment rules and ISL number on constellation performance under uniform traffic are studied, aiming to achieve the capacity upper bound under failure cases. In [15], a dynamic ISL reconfiguration method is proposed to mitigate failure effects by reinforcing bottleneck cuts. In [16], a topology design method is proposed that maximizes capacity by twisting edge ISLs in a 2D-torus structure. In [17], a topology design algorithm is proposed to minimize redundant ISLs caused by constellation asymmetry while maintaining constellation capacity. These works focus on specific ISL establishment rules to maintain or improve constellation capacity and lack generality. To address this theoretical limitation, the lower bounds of the average shortest path length in vertex-symmetric constellations are derived, and it is shown that alternative topologies can outperform the standard mesh grid in both diameter and efficiency [18]. In [12]–[14], by modeling complex dynamic cascading failure processes of nodes and ISLs in LEO constellations, the impacts of buffer limits, processing constraints, and real-time routing on network-wide outages are analyzed through simulations. Although these studies provide theoretical results on capacity and valuable insights, they all neglect the overhead required to implement these algorithms, which is especially important in large-scale constellations. Fortunately, the effective capacity incorporating protocol overhead has been explored in largescale grid-based wireless ad hoc networks. A framework is developed to evaluate the capacity and scalability of finite grid-based wireless networks under different node degrees. It captures protocol overhead, congestion bottlenecks, traffic heterogeneity and other real-world concerns [10], [11]. These studies on wireless ad hoc networks provide useful insights for analyzing the capacity scalability of LEO constellations under dynamic link failures. In addition to routing overhead, the main difference is that LEO constellations focus on ISL maintenance overhead rather than interference avoidance overhead. Therefore, these results cannot be directly used to explain capacity scalability in LEO constellations. The consensus among the aforementioned theoretical studies on constellation capacity is that the design of intelligent routing and ISL establishment algorithms plays a key role in enhancing and maintaining the constellation capacity. Although routing design in wireless ad hoc networks is not a new topic, recent studies have extensively investigated routing design and evaluation in LEO constellations from multiple perspectives. In [19], the trade-off between centralized and distributed routing in faulty constellations is studied. It shows that in highly dynamic bufferless networks, the distributed scheme achieves higher throughput than the centralized scheme, while in buffered networks it yields lower delay. To reduce packet loss and improve path reliability, distributed routing algorithms have been designed based on the predictable geometric structure of the constellation, achieving significant improvements in path success ratio, delay and average hop count [20]–[23].
3
ISL establishment rules [23], satellite-to-ground reliable communication [21] and hybrid centralized/distributed strategies [21]–[23] are also considered in the routing design. Essentially, these studies utilize the distributed routing design paradigm to improve adaptability to dynamic topologies. Due to the limited transport capacity of individual satellites and ISLs, after partial route reconfiguration, packet congestion is highly likely to occur at certain satellites or ISLs, thereby increasing end-toend latency and packet loss rate [24], [25]. This phenomenon is referred to as cascading failures. The spatial non-uniformity of traffic carried by the LEO constellation, resulting from differences in population density, further intensifies these cascading effects. To suppress cascading failures and balance traffic load, a virtual node model is used for load balancing in [24] by integrating ground station deployment into the network model. In contrast, cascading failures are analyzed by combining complex network and hypernetwork theories in [25], where corresponding strategies are developed for different types of failures and attack scenarios. An intelligent elastic routing framework based on graph neural networks and deep reinforcement learning is also proposed in [26]. The load balancing problem under sparse traffic is modeled as a linear programming problem, establishing the lower bound on the worst-case link load for any oblivious routing scheme and presenting a scheme that achieves this bound [27]. The effects of unpredictable space weather (such as single-event upsets and solar storms) on the fundamental performance of satellite constellations are also assessed in [28], [29]. These studies offer important insights into the performance of satellite constellations under failures. However, they generally neglect the relationship between protocol overhead and capacity as the constellation size increases. III. S YSTEM M ODELS A LEO constellation consists of P orbital planes, with M satellites evenly distributed in each orbital plane. The position of each satellite is represented as (x, y), where x ∈ {0, 1, . . . , P − 1} denotes the index of the orbital plane, and y ∈ {0, 1, . . . , M − 1} denotes the index of the satellite within orbital plane x. Each satellite establishes two co-plane links and two inter-plane links. In the ideal case, the number of operational satellites is n = M P . For describing the geometric of the LEO constellation, it is represented as θ : n/P/F . θ ∈ (0◦ , 90◦ ) is the inclination angle of the orbital planes with respect to the equator, determining the areas on Earth covered by the satellites. Larger θ means more coverage of the polar regions. F ∈ {0, 1, . . . , P − 1} is a phasing parameter, an integer value that expresses the relative degree separation between neighboring satellites across adjacent planes, given by F × 360◦ /P . Essentially, a constellation topology is represented as a graph G(V, E), where V is the set of satellites in the constellation and E is the total number of ISLs. In practice, satellites and inter-satellite links may fail due to unpredictable factors such as space debris, solar radiation, and deliberate attacks. Therefore, at time t, the number of operational satellites and ISLs in the constellation are |V (t)| ≤ n and |E(t)| ≤ 2n, respectively.
Uniform traffic pattern: each satellite transmits data packets to all other satellites in the constellation with probability 1/(n−1). Compared with localized traffic patterns, this traffic model injects the maximum number of data packets into the constellation per time slot and exhibits global dependence on the connectivity of the constellation, which helps provide a deeper understanding of constellation capacity. A. Memory-Aware ISL Failure Model Assume time is slotted, each ISL can be either in the OFF state or the ON state during each time slot. The state of ISL i evolves independently according to a discrete-time Markov process {Xi (t), t > 0}, as illustrated in Fig. 1 [19]. When an ISL is in the ON state (Xi (t)=1), data packets are successfully transmitted; otherwise, the transmission fails. The steady-state probabilities of the i-th ISL being in states “0” and “1” are given by α β (i) (i) , π0 = , (2) π1 = α+β α+β where α and β are the failure probability and the recovery probability, respectively. 1−β
1−α β
0
1 α
Fig. 1: Two-state discrete Markov chain describing the ISL state evolution. State 0 corresponds to an OFF, while state 1 corresponds to an ON. Some ISLs may experience failures, they remain in either state 0 or state 1 over multiple consecutive time slots, indicating that the evolution of ISL states exhibits memory. In other words, the state at time slot t is correlated with the state at time slot t − k, where t < k. To capture the correlation, we define the belief of an ISL as the probability that the ISL is ON at time slot t given its historical state at time slot t − k. Based on the aforementioned Markov process, the belief of ISL i is given by γi (t) = P(ISL i is ON| History state at time slot t − k) = P Xi (t) = 1 Xi (t − k) = si , si ∈ {0, 1}. (3) The k-step transition probabilities of the Markov process depicted in Fig. 1 are given by α + βµk , α+β α − αµk (i) , p10 (k) = α+β (i)
p00 (k) =
β − βµk , α+β β + αµk (i) p11 (k) = . α+β (i)
p01 (k) =
(4) (5)
where µ = 1 − α − β is the memory parameter of ISLs. The larger |µ|, the higher the predictability of the ISLz state; conversely, the smaller |µ|, the lower the predictability. When the memory parameter µ = 0, the ISLs have no memory
4
(i.i.d. in time), and when µ → 1, the ISLs remain static once realized. For analytical simplicity, we assume that the evolution of all ISLs is homogeneous. Given a fixed k, a larger µ results in lower overhead for maintaining ISLs. This failure model has been used to describe the state evolution of wireless channels in opportunistic communication systems [30]. IV. M AIN R ESULTS We make the following (nearly) minimal set of assumptions: (A.1) The transmission rate of each ISL is 1 Gbps. (A.2) In the packet multi-hop routing process, the overhead of a single-hop transmission is σ < ∞ Gbps. The sources of overhead include establishing/maintaining routing paths, sharing ISLs, queuing, and avoiding/handling congestion, etc. σ is called as the contention overhead. (A.3) The overhead of establishing and maintaining each ISL is ω < ∞ Gbps. This overhead depends on the behavior of ISL failures and the memory of the ISL state evolution. ω is called as the consensus overhead. (A.4) The contention overhead and consensus overhead are mutually independent. When the global constellation state information is perfectly known, all protocols and strategies incur zero overhead. Under this condition, the upper bound of the constellation capacity is achievable. Applying the bisection argument, the constellation capacity under a uniform traffic pattern is given as follows. Lemma 1: Under the uniform traffic √ pattern, the upper bound of the constellation capacity is 8 n Gbps. This upper bound can be achieved by employing shortest-hop routing. Proof: The proof can be found in [8], [9].
where h(x) = −x log2 x − (1 − x) log2 (1 − x) and π0 and π1 are given in (2). Proof: To maintain the constellation structure, it is essentially necessary to eliminate the state uncertainty accumulated over k time slots for each ISL. Therefore, the joint entropy can be used to measure the total consensus overhead for maintaining each ISL i over k time slots. Applying the chain rule for entropy, we have H(X1 , X2 , . . . , Xk ) = H(X1 ) + H(X2 | X1 ) + H(X3 | X1 , X2 ) + . . . + H(Xk | X1 , X2 , . . . , Xk−1 )
Using the Markov property of ISL state evolution, (7) is simplified to H(X1 , . . . , Xk ) = H(X1 ) + (k − 1)H(X2 |X1 ).
A. Lower Bound on Consensus Overhead Proposition 1: Assuming that the ISL state evolution follows the two-state discrete-time Markov chain, the average consensus overhead over k time slots is lower bounded by ω ≥ H̄k (α, β) =
h (π1 ) + (k − 1) (π1 h(α) + π0 h(β)) , (6) k
(8)
By incorporating the steady-state probabilities of ISL state evolution (see (2)), we obtain X H(X2 | X1 ) = πj H(X2 | X1 = j) j∈{0,1}
= π1 h(α) + π0 h(β),
(9)
where h(x) = −x log2 x − (1 − x) log2 (1 − x), x > 0. The prior uncertainty H(X1 ) associated with each ISL is given by H(X1 ) = h π1 . (10) Based on equations (8), (9) and (10), the average consensus overhead is lower bounded by ω≥
Remark 1: Apart from the shortest-hop routing, in order to achieve the capacity upper bound, the constellation topology must satisfy a symmetric geometric condition: |M − P | < ϵ, where ϵ > 0. In other words, the difference between the number of orbital planes and the number of satellites per plane should not be too large. From Lemma 1, the capacity gain √ from increasing the number of satellites scales as O(1/ n). This implies that if the overhead grows√ with the number of satellites at a rate greater than Ω(1/ n), the constellation capacity will be exhausted. In particular, in failure scenarios, the consensus overhead associated with maintaining ISLs increases significantly. Therefore, we use the ratio of constellation capacity to total overhead as a metric to quantify the change in effective constellation capacity as the number of satellites increases. Next, we derive a lower bound on the consensus overhead from an information-theoretic perspective.
(7)
h (π1 ) + (k − 1) (π1 h(α) + π0 h(β)) . k
Proposition 1 derives an information-theoretic lower bound on the consensus overhead required for maintaining each ISL. This bound is jointly determined by the link-state evolution behavior and the maintenance period k. Next, we investigate the impact of different parameters on H̄k (α, β). Corollary 1: Given the link-state evolution dynamics, i.e., fixed α and β, the following results hold: • When k = 1, ω ≥ h (π1 ). • When k → +∞, ω ≥ H̄∞ (α, β) =
β α h(α) + h(β) > 0. α+β α+β
β where π1 = α+β . Proof: Two cases are considered separately: setting k = 1 and k → +∞ in (6). This completes the proof of Corollary 1.
When k = 1, the ISL is maintained in each time slot, without exploiting the prior state information of the ISL. In this case, the minimum consensus overhead equals the entropy of ISL in the “on” state. In contrast, as k → +∞, the fixed overhead associated with the initial confirmation of the ISL state becomes negligible. In this case, the consensus overhead depends solely on the ISL state changes frequently.
5
(a) β = 0.25
(b) β = 0.5
(c) β = 0.75
Fig. 2: Lower bound of consensus overhead as a function of failure probability α under different recovery probabilities β.
Furthermore, it can be observed that when the ISL experiences failures, we have
h (π1 ) ≥ H̄∞ (α, β),
(11)
where 0 < α + β ≤ 1. The equality holds if and only if α + β = 1. Increasing the ISL maintenance period k can reduce the consensus overhead, but it cannot fall below H̄∞ (α, β). Fig. 2 shows the lower bound of the consensus overhead as a function of the failure probability α for β = 0.25, 0.5, and 0.75. When the failure-recovery probability β > 0.5 and the memory parameter of the ISL µ = 1 − α − β > 0, the consensus overhead required under the k = 1 and k → +∞ strategies becomes nearly identical. In other words, maintaining the ISL in each time slot (i.e., k = 1) is the optimal strategy, since h (π1 ) ≈ H̄∞ (α, β). In contrast, when α + β > 1, increasing the maintenance period k can reduce the consensus overhead compared with k = 1, since the predictability of the ISL state increases, even though the ISL state changes frequently.
Fig. 3: Classification of ISL state evolution behaviors for 0 < ϵ1 < ϵ2 ≪ ϵ3 < ϵ4 < 1. The lower bound of the consensus overhead is maximized when α = β = 0.5. Each region can be represented as: A1 = {(α, β) | ϵ1 ≤ α ≤ ϵ2 , ϵ1 ≤ β ≤ ϵ2 },
When k = c < +∞, the relative magnitudes of the failure probability α and the recovery probability β affect the lower bound of the consensus overhead. The evolutionary behavior of ISLs is classified into five regions. Next, we focus on analyzing the lower bounds of consensus overhead in regions I–IV, as shown in Fig.3. The evolutionary behavior of ISL in each region is as follows: Region I: The failure probability and recovery probability of ISL are both far below 1. The probability of ISL transitioning from the ON (OFF) state to the OFF (ON) state is low, indicating that the state of ISL is stable. Region II: The failure probability of ISL is low, while the recovery probability is high. The probability of ISL transitioning from the OFF state to the ON state is high. Region III: Both the failure probability and recovery probability of ISL are high. The state of ISL transitions frequently. Region IV: The failure probability of ISL is high, while the recovery probability is low. Once a failure occurs, the ISL is difficult to recover.
A2 = {(α, β) | ϵ1 ≤ α ≤ ϵ2 , ϵ2 < β ≤ ϵ4 }, A3 = {(α, β) | ϵ3 ≤ α ≤ ϵ4 , ϵ3 ≤ β ≤ ϵ4 }, A4 = {(α, β) | ϵ2 < α ≤ ϵ4 , ϵ1 < β < ϵ2 }, A5 = A −
4 [
Ai ,
i=1
where A = {(α, β) | 0 < ϵ1 ≤ α, β ≤ ϵ4 < 1}. Corollary 2: Given the maintenance period of ISLs , i.e., k = c > 1, the following results hold: Region ID
I & III
II
IV
H̄k
1 k
k−1 h(α) k
k−1 h(β) k
Proof: When α ≈ β, we have h(π1 ) ≈ 1. Based on this fact, we derive the lower bound on the consensus overhead for each region. For Region I, when α ≈ β ≪ 1, we obtain h(α) ≈ 0
and
h(β) ≈ 0.
(12)
6
Substituting (12) into (6) yields ω ≥ k1 . Using the same approach, the lower bound on the consensus overhead for Region III is also k1 . For Region II, when 0 < α ≪ 1, we have π0 ≈ 0
and
h(β) ≈ 0.
i∈V j∈V
(13)
Substituting (12) into (6) yields ω ≥ k−1 k h(α). By using the similar approach as in Regions II, we can complete the proof for Regions IV. It can be observed that when the ISL state evolution lies in Regions I and III, selecting a larger maintenance period k can reduce the consensus overhead. In other words, the ISL states in these regions exhibit strong memory, i.e., the memory parameter |µ| is large. In contrast, when the ISL state evolution lies in Region II, increasing k can hardly reduce the consensus overhead. In this region, the recovery probability is relatively high and the consensus overhead is mainly incurred to address the ISL uncertainty caused by failures. Similarly, when the ISL state evolution lies in Region IV, increasing k yields only limited reductions in consensus overhead. In this case, once an ISL failure occurs, the recovery probability is very low, and the overhead is mainly incurred to eliminate the uncertainty regarding whether the ISL has recovered. B. Upper Bound of Capacity Scalability We integrate the overhead into the constellation capacity analysis and use it to quantify how ISL state evolution and routing affect the capacity scalability. From the overhead perspective, the capacity scalability is defined as follows. Definition 1: The capacity scalability is defined as the ratio of the constellation capacity under non-failure conditions to the total overhead, which is denoted by τ . Using Lemma 1 and Proposition 1, the upper bound of the capacity scalability is derived. Theorem 1: Under the uniform traffic pattern, if the ISLs follow the two-state discrete Markov chain and the maintenance period is k ≥ 1, the upper bound of capacity scalability is given by √ 16 n , (14) τ ≤ τ (n, k) = 1 + σn1.5 + 4nH̄k (α, β) where α and β are the failure probability and the recovery probability, respectively. When the total overhead converges to 0, (14) degenerates to Lemma 1. Proof: From Lemma 1, it can be seen that under ideal conditions, the upper bound of the constellation capacity is √ 8 n. The total overhead of the constellation is denoted by ϕ(n) = ϕ1 (n) + ϕ2 (n),
where δx = |xi − xj | and δy = |yi − yj |. Combining (16), the average hop count is given as follows 1 XX L(n) = Pr(i, j)d(i, j). (17) n
(15)
where ϕ1 (n) is the contention overhead and ϕ2 (n) is the consensus overhead. Contention Overhead ϕ1 (n): we first prove the average hop count under the uniform traffic pattern. For any satellites i and j with j ̸= i, the minimum hop count between them is given as follows: √ √ d(i, j) = min{δx , n − δx } + min{δy , n − δy}, (16)
where the probability Pr(i, j) that satellite i is matched with satellite j to form a source–destination pair is ( 1 , i ̸= j, Pr(i, j) = n−1 0, i = j. Substituting (16) into (17), we obtain (√ √ √ n √ n odd n 2 √, L(n) = = + O(1/ n). √ n n 2 n even 2(n−1) ,
(18)
According to the construction rules of the uniform traffic pattern, the total number of source–destination pairs in the constellation is n. The total number of hops required to successfully deliver all packets generated by the source satellites to their corresponding destination satellites is nL(n). Combining Assumption (A.2), the total contention overhead is σn1.5 ϕ1 (n) ≥ σnL(n) ≈ . (19) 2 Consensus Overhead ϕ2 (n): For a constellation of size n, the total number of ISLs is at most 2n. Combining Proposition 1, we have ϕ2 (n) = 2nω ≥ 2nH̄k (α, β). (20) Substituting (19) and (20) into (15), we obtain σn1.5 + 2nH̄k (α, β). 2 Based on Definition 1, Theorem 1 is proved. ϕ(n) ≥
(21)
Remark 2: When the total contention overhead is constant (σ = c), the upper√bound of capacity scalability increases from O(1/n) to O(1/ n). This merely reduces the convergence rate of capacity scalability to zero. When the constellation size grows, the total overhead increases much faster than the constellation capacity, i.e., when ISLs are unstable, the constellation does not have scalability. This shows that building large constellations depends on reducing overhead rather than on designing the constellation structure. This is √ because, for any topology, the upper bound of capacity is O( n). Routing strategies with low overhead should be used, and the link maintenance period k should be chosen properly according to the ISL evolution behavior. If this is not possible, the frequency of using multi-hop transmission should be reduced. To ensure that the capacity √ of the constellation for carrying data packets remains at Θ( n), the contention overhead and the consensus overhead should satisfy the following conditions: σ = o(n−1.5 ) and ω = o(n−1 ), where ϵ is an arbitrarily small positive real number. This condition is extremely stringent. As the constellation size increases, the capacity available for ISL maintenance and routing becomes lower.
7
By fitting the simulation data from small-scale constellations, the competitive overhead (σ) and consensus overhead (ω) in (14) can be obtained. This enables the prediction of the scalability of constellations using specific routing algorithms and ISL maintenance strategies. This is particularly important for the design of network protocols in large-scale constellations, especially under limited computational resources for simulations. C. Maximum Capacity Scalability Based on the above analysis, for a given routing algorithm and ISL maintenance strategy, there exists an optimal constellation size n∗ , at which the capacity scalability reaches √ n . By its maximum. Let Q(n, k, α, β) ≜ 1+σn1.516 +4nH̄k (α,β) solving ∂Q = 0, (22) ∂n the optimal constellation size n∗ is obtained. Theorem 2: Given the ISL evolution behavior and the routing algorithm, the optimal constellation size n∗ satisfies 2σn1.5 (23) ∗ + 4n∗ H̄k (α, β) = 1 √ The maximum scalability is 8 n∗ . Proof: By taking the partial derivative, (22) is simplified to 8 1 − 2σn1.5 − 4H̄k (α, β)n (24) 2 = 0. √ n 1 + σn1.5 + 4nH̄k (α, β) 2 √ Since n 1 + σn1.5 + 4nH̄k (α, β) > 0, n∗ satisfies 2σn1.5 + 4nH̄k (α, β) = 1
(25)
Substituting (25) into Q(n, k, α, β) yields the maximum 2 capacity scalability. This is because ∂∂nQ2 < 0, i.e., ∂2Q ∂n2
=√ n=n∗
√ −8 3σ n∗ + 4H̄k (α, β) n∗ 1 + σ(n∗ )1.5 + 4n∗ H̄k (α, β)
2 < 0.
The capacity scalability first increases and then decreases with the number of satellites. This implies that, for a given routing algorithm and link maintenance strategy, there exists an optimal number of satellites that maximizes capacity scalability. This maximum is extremely sensitive to the state of the ISLs. Specifically, when the recovery probability is given, increasing the failure probability reduces the maximum capacity scalability τ and shifts the optimal number of deployed satellites to the left. A numerical example is shown in Fig. 4. Corollary 3 provides the optimal n∗ in two extreme scenarios: when σ → 0 and when H̄k (α, β) → 0. Corollary 3: The optimal constellation sizes under the two extreme scenarios are given as follows: Scenario I: When the contention overhead is zero, i.e., σ → 0, 1 n1∗ ≈ . (26) H̄k (α, β) Scenario II: When the coherency overhead is zero, i.e., H̄k (α, β) → 0,
Fig. 4: Scalability vs. n under different ISL evolution behaviors.
n2∗ ≈
1 2σ
2/3 .
(27)
Proof: This proof is completed by analyzing equation (23). It can be easily observed that, for the same reduction in overhead, the optimal constellation size is more sensitive to consensus overhead than to contention overhead. This implies that reducing the ISL maintenance consensus overhead yields the greatest improvement in capacity scalability. In Table I, when the overheads in both scenarios are reduced by 10 times, the optimal constellation size in Scenario I increases by 10 times, which is far larger than the 4.6 times increase observed in Scenario II. TABLE I: Optimal size n∗ under 10× overhead reduction. Scenario
Overhead
I
10−6 → 10−7
II
n∗ (Initial)
n∗ (Optimized)
2.5 × 105
2.5 × 106
10 times
6.3 × 103
2.9 × 104
4.6 times
Gain
V. F URTHER D ISCUSSION As shown in Section IV-B, the ISL evolution behavior and the maintenance period affect both the consensus overhead and the optimal constellation size. In this section, a detailed analysis is presented. A. Capacity Scalability vs. Maintenance Period From Corollary 1, the choice of the maintenance period (k) influences the lower bound of the consensus overhead under a given ISL evolution behavior. In this subsection, we analyze the impact of the maintenance period on scalability. Based on Corollary 1, the following conclusion can be drawn.
8
Corollary 4: When the ISL evolution behavior is given (i.e., α and β are fixed), for any k ∈ [1, +∞), the upper bound of capacity scalability satisfies the following inequality: τ1 (n) ≤ τ (n, k) < τ∞ (n), where
√ 16 n 1 + σn1.5 + 4nh (π1 )
(29)
√ 16 n 1 + σn1.5 + 4n [π1 h(α) + π0 h(β)]
(30)
τ1 (n) = and τ∞ (n) =
(28)
π1 and π0 are given in (2). Proof: Substituting the lower bound of the consensus overhead in Corollary 1 into (14), the proof is completed. (a) τ (n) vs. n
Increasing the maintenance period k cannot change the inherent trend that scalability first increases and then decreases with n. This is because the denominator terms in both τ1 (n) and τ∞ (n) still follow f (n) = 1 + an1.5 + cn, where a, c > 0. Although increasing k cannot change the fact that scalability converges to zero as n increases, it can shift the optimal constellation size to a larger value, at which the scalability is maximized. Note that this gain does not continue to increase with k. In practice, it is sufficient to choose a relatively large maintenance period. A numerical example is given in Fig. 5. The maximum gain of scalability with respect to n also follows the pattern of first increasing and then decreasing (see Fig. 5b). When n → ∞, we have lim ∆τ (n) = 0,
n→∞
(31)
where ∆τ (n) = τ∞ (n) − τ1 (n). This implies that, as the constellation size increases, the scalability gain obtained by increasing k converges to 0. B. Capacity Scalability vs. ISL Evolution Behavior In practice, ISL states vary with the space environment, resulting in differing consensus overheads. The lower bound on the consensus overhead varies across different regions (see Corollary 2). Based on Corollary 2, we derive the upper bounds on the scalability of Regions I-IV. This result provides insight into the variation of the scalability upper bound when ISLs undergo extreme evolution behavior. Corollary 5: When the maintenance period is given, i.e., k = c ≥ 1, the upper bounds on the capacity scalability in Regions I-IV are as follows: Region ID I&III II IV
Upper Bound √ 16k n 1.5 k(1 + σn ) + 4n √ 16k n k(1 + σn1.5 ) + 4n(k − 1)h(α) √ 16k n k(1 + σn1.5 ) + 4n(k − 1)h(β)
Proof: Substituting the lower bound of the consensus overhead in Corollary 2 into (14), the proof is completed.
(b) ∆τ (n) vs. n
Fig. 5: Scalability versus n for maintenance periods k = 1 and k → ∞. The contention overhead, failure probability and recovery probability are σ = 10−10 , α = 10−6 and β = 0.5, respectively.
The evolution behaviors of ISLs in Regions I and III exhibit a stark contrast in their microscopic dynamics. In Region I, both the failure probability and the recovery probability are low. This means that once an ISL fails, it remains in the OFF state for a long time. In contrast, in Region III, both the failure and recovery probabilities are high, so the ISL remains in the ON state for only a short time. Interestingly, despite these differences, the ISL state evolution is highly predictable in Regions I and III, as the memory parameter |µ| = |1−α−β| → 1. The capacity scalability of Regions I and III is identical in the information-theoretic sense. In practice, increasing ISL link resilience and reducing the number of satellites should be used to prevent ISL evolution behavior from entering Regions I and III. Moreover, when ISL evolution behavior is in Regions I and III, increasing the maintenance period is not a good strategy because the ISL state memory parameter µ → 1. However, in Region II, the failure probability is low and the recovery probability is high, meaning that ISLs rarely fail. In this case, the scalability is optimal because h(α) → 0.
9
Compared to Region II, in Region IV, the failure probability is high and the recovery probability is low, making it nearly impossible for ISLs to recover after failure. As the number of satellites increases, the number of failed ISLs in the constellation increases because h(β) → 0. Therefore, maintaining ISL evolution behavior in Region II is the optimal for achieving the highly capacity scalability. A numerical example is shown in Fig. 6. When k = 10, using the same routing strategy — σ = 10−11 , the scalability in different ISL evolution regions satisfies τ2 (n) > τ4 (n) > τ1 (n) = τ3 (n).
Fig. 6: Capacity Scalability vs. n under different regions. ϵ1 = 10−6 , ϵ2 = 10−4 , ϵ3 = 0.7, ϵ4 = 0.9.
VI. S IMULATION E XAMPLES : C APACITY S CALABILITY WITH S HORTEST- HOP ROUTING Assuming that the shortest-hop routing strategy is employed, we will simulate and verify the capacity scalability of the constellation under different regions of ISL evolution behavior. A. Simulation of the Evolutionary Behavior of Constellation Structures To facilitate better understanding, the evolution of the number of ISLs in the ON state and the constellation connectivity under different parameters is presented in Fig. 7. The connectivity is defined as the ratio of the number of satellites in the largest connected component to the total number of satellites, denoted as ξ(t). The number of ISLs in the ON state characterizes local behavior, while connectivity reflects the global behavior of the constellation topology. In Region I, both α and β are very small, making the ISL states difficult to change. As a result, the constellation connectivity may suddenly collapse or recover after remaining at a certain level for a period of time (see Fig. 7a). In Region II, the repair probability is high and the failure probability is low. Eon (t) stays at a high level. The constellation connectivity is 1 with high probability (see Fig. 7b). Region II is also the optimal operating region. In Region III, both the failure
probability and the repair probability are high. This means that the ISL states change much more frequently compared to Region I. The constellation connectivity is extremely unstable and changes almost every time slot. Therefore, when the ISL states evolve in Region III, protocol parameters must be adjusted in every time slot. Moreover, when the ISLs evolve in Region V, the parameters are set as α = β = 0.5 because the entropy of each ISL reaches its maximum. In this case, the ISL states are almost impossible to predict because both Eon (t) and ξ(t) fluctuate violently (see Fig.7c). In the simulation examples of Regions I, III and V, the average number of ISLs in the ON state is 10000, but the variances are significantly different. Comparing Figs. 7b and 7d, although the number of ISLs in the ON state fluctuates greatly in both cases, the connectivity behavior shows significant differences. This indicates that the number of ISLs in the ON state determines the constellation connectivity. B. Simulation of Capacity Scalability The simulation procedure for capacity scalability under dynamic link failures is as follows: For a constellation of size n, n source-destination pairs are generated through random permutation. The constellation topology is constructed, where each satellite initially establishes four ISLs. Each ISL evolves for t0 time slots according to the given failure and recovery probabilities until reaching a steady state. Starting from time slot t0 + 1, the shortest hop count for each source-destination pair is computed using Dijkstra’s algorithm. If no path is found, it is recorded as 0. This process is repeated for t1 time slots. The state transition probabilities of the ISLs and the average hop count are then evaluated and substituted into τ (n, k) in (14) to obtain the simulation results. In computing the shortest paths between source–destination pairs, we use the perfect constellation topology information. The shortest hop count for successfully establishing a source–destination routing path is minimized. Given σ = 10−12 , t0 = 100, t1 = 800, and k = 10, we set (α, β) = (10−5 , 0.8) ∈ Region II. The capacity scalability is simulated for n = 100, 400, 900, 1600, 2500, 3600, 6400 and 8100. Each data point is obtained by averaging over 1000 simulation runs. The simulation results are shown in Fig. 8. Under perfect constellation topology information, the simulated capacity scalability can attain the theoretical upper bound. This implies that shortest-hop routing is one of the strategies for achieving the upper bound of capacity scalability, with consensus overhead minimized. The capacity scalability is extremely sensitive to fluctuations in the evolutionary state of ISLs. When capacity scalability reaches its maximum, the simulation results exhibit greater variability. The overhead for maintaining the constellation structure and discovering routing paths becomes unstable. Under imperfect constellation topology information, the capacity scalability is further reduced. This is because the overhead required for establishing routing paths and maintaining ISLs increases with the scale of the satellite constellation. If the constellation structure is used to support local traffic rather than all-to-all traffic, capacity scalability can be further improved because the minimum hop count between source–destination pairs is reduced.
10
(a) Region I: β = α = .05
(b) Region II: β = .9, α = .05
(c) Region III: β = α = .9
(d) Region V: β = α = .5
Fig. 7: Evolution trajectories of the number of ISLs in the ON state and the constellation connectivity when the ISLs are located in different regions. The total number of satellites is 10,000.
From Theorem 1, the functional form of capacity scalability under the all-to-all traffic model is given as follows: √ 16 n f (n) = , 1 + anL̄ + 4bnH̄k (α, β) a and b are determined by the routing strategy and the ISL maintenance protocol, respectively. For any given set of protocols, the average hop count L̄ and the state transition probabilities of the ISLs can be obtained through simulations on a small scale constellation. The parameters â and b̂ are then fitted from the simulation data. Based on the empirical formula, we predict whether the constellation scalability reaches its maximum. For example, under minimal consensus overhead, the shortest-hop routing strategy yields â = 5.44e−7 and b̂ = 0.965. VII. CONCLUSIONS The upper bound on capacity scalability under uniform traffic patterns is derived by incorporating the failure evolution behavior of ISLs. For any protocol, the capacity scalability converges to zero as the constellation size approaches infinity.
Fig. 8: Capacity scalability vs. n.
11
The optimal constellation size is identified. When the constellation size is below this optimal value, the capacity scalability increases with constellation size, implying that scaling up the network can achieve higher effective capacity for data packet transport. In the future, quantifying capacity scalability under non-uniform traffic patterns remains an important research direction. It can be anticipated that capacity scalability under non-uniform traffic is higher than that under uniform traffic, while the asymptotic convergence to zero still holds. This is because, under dynamic failures, the consensus overhead scales as Θ(n). R EFERENCES [1] F. Letizia, C. Colombo, H. Lewis, and H. Krag, “Extending the ecob space debris index with fragmentation risk estimation,” 2017. [2] N. Reiland, A. J. Rosengren, R. Malhotra, and C. Bombardelli, “Assessing and minimizing collisions in satellite mega-constellations,” Advances in Space Research, vol. 67, no. 11, pp. 3755–3774, 2021. [3] L. Olivieri and A. Francesconi, “Large constellations assessment and optimization in leo space debris environment,” Advances in Space Research, vol. 65, no. 1, pp. 351–363, 2020. [4] M. Sheng, D. Zhou, S. Ji, W. Bai, Y. Zhu, J. Liu, and J. Li, “Effects of space environment on satellite mega-constellations: From nodes and links to network performance,” Engineering, 2025. [5] A. Ramanathan and S. A. Jyothi, “Weathering a solar superstorm: Starlink performance during the may 2024 storm,” in Proceedings of the 2nd International Workshop on LEO Networking and Communication, 2024, pp. 31–36. [6] V. W. S. Chan, “Free space optical communication and network architecture - fundamentals, history and looking forward,” IEEE J. Sel. Top. Quantum Electron., vol. 32, no. 1: Advances in Free Space Laser Communications, pp. 1–20, 2026. [7] M. Sheng, D. Zhou, W. Bai, J. Liu, H. Li, Y. Shi, and J. Li, “Coverage enhancement for 6g satellite-terrestrial integrated networks: performance metrics, constellation configuration and resource allocation,” Science China Information Sciences, vol. 66, no. 3, p. 130303, 2023. [8] G. Barrenetxea, B. Berefull-Lozano, and M. Vetterli, “Lattice networks: capacity limits, optimal routing, and queueing behavior,” IEEE/ACM Trans. Netw., vol. 14, no. 3, pp. 492–505, 2006. [9] J. Sun and E. Modiano, “Capacity provisioning and failure recovery for low earth orbit satellite constellation,” International journal of satellite communications and networking, vol. 21, no. 3, pp. 259–284, 2003. [10] R. Urgaonkar, V. Manfredi, and R. Ramanathan, “Scalability analysis of grid-based multi-hop wireless networks,” in 2013 Fifth International Conference on Communication Systems and Networks (COMSNETS), 2013, pp. 1–10. [11] R. Ramanathan, E. Ciftcioglu, A. Samanta, R. Urgaonkar, and T. La Porta, “Symptotics: a framework for estimating the scalability of real-world wireless networks,” Wireless Networks, vol. 23, no. 4, pp. 1063–1083, 2017. [12] L. Zhang, Y. Du, and Z. Sun, “Modeling and analysis of cascading failures in leo satellite networks,” IEEE Trans. Netw. Sci. Eng., vol. 11, no. 1, pp. 807–822, 2024. [13] L. Zhang and Y. Du, “A dynamic cascading failure model for leo satellite networks,” IEEE Trans. Netw. Serv. Manag., vol. 21, no. 2, pp. 1672– 1689, 2024. [14] T. Shake, J. Sun, T. Royster, and A. Narula-Tam, “Failure resilience in proliferated low earth orbit satellite network topologies,” in MILCOM 2022, 2022, pp. 828–834. [15] L. Guo, J. Liu, M. Sheng, Y. Li, and J. Li, “Capacity analysis and robust topology design of leo satellite constellation with node/link failure,” IEEE Trans. Commun., vol. 74, pp. 7420–7433, 2026. [16] L. Guo, M. Sheng, J. Liu, and J. Li, “Exploring the throughput capacity limits of leo satellite constellation networks: Mathematical models and analysis,” in 2024 16th International Conference on Wireless Communications and Signal Processing (WCSP), 2024, pp. 1019–1024. [17] T. Lan, D. Zhou, M. Sheng, and J. Li, “Inter-satellite link planning for high capacity in leo mega-constellations,” in ICC 2024, 2024, pp. 4451–4456. [18] C. Rao and E. Modiano, “Minimum-hop constellation design for low earth orbit satellite networks,” in IEEE INFOCOM 2025, 2025, pp. 1– 10.
[19] R. V. Ramakanth and E. Modiano, “Centralized versus distributed routing for large-scale satellite networks,” 2025. [Online]. Available: https://arxiv.org/abs/2501.13744 [20] C. Brady, J. Sun, M. Yuksel, and T. Shake, “Prabr: Integrating primary and backup routing in pleo satellite networks,” in 2025 IEEE Aerospace Conference, 2025, pp. 1–10. [21] J. Sun, T. Shake, A. Narula-Tam, and T. Royster, “Multicast communications with uplink broadcast in a proliferated low earth orbit satellite network,” in 2025 IEEE Aerospace Conference, 2025, pp. 1–8. [22] M. Yuksel, C. Brady, J. Sun, and T. Shake, “Low-overhead gpsfree geometric routing for leo satellite networks,” in 2025 IEEE 26th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), 2025, pp. 21–30. [23] T. Shake, “Hybrid geometric/shortest-path routing in proliferated lowearth-orbit satellite networks,” in MILCOM 2023, 2023, pp. 357–364. [24] S. Li, C. Zhang, C. Zhao, and C. Xia, “Analyzing the robustness of leo satellite networks based on two different attacks and load distribution methods,” Chaos: An Interdisciplinary Journal of Nonlinear Science, vol. 34, no. 3, 2024. [25] ——, “Robustness of leo satellite hypernetworks under different network topologies and attack strategies,” Physics Letters A, vol. 526, p. 129952, 2024. [26] L. Bai, H. Ma, Y. Jiang, Z. Yin, H. Wan, and H. Wang, “Grl-rr: A graph reinforcement learning-based resilient routing framework for software-defined leo mega-constellations,” Computer Networks, vol. 259, p. 111089, 2025. [27] R. V. Ramakanth and E. Modiano, “Optimal oblivious load-balancing for sparse traffic in large-scale satellite networks,” arXiv preprint arXiv:2601.02537, 2026. [28] Y. Nie, D. Zhou, M. Sheng, J. Liu, W. Bai, and J. Li, “A networklevel 3-layer single event upset risk assessment model for satellite mega constellations,” in 2025 IEEE/CIC International Conference on Communications in China (ICCC), 2025, pp. 1–6. [29] X. Liu, W. Bai, M. Sheng, D. Zhou, J. Liu, S. Ji, and Y. Zhu, “Impact analysis of solar background noise on leo mega-constellations,” in ICC 2025, 2025, pp. 6916–6921. [30] M. Johnston, I. Keslassy, and E. Modiano, “Channel probing in opportunistic communication systems,” IEEE Trans. Inf. Theory, vol. 63, no. 11, pp. 7535–7552, 2017.