Abstract: Upstart space companies are actively developing massive constellations of low-flying satellites to provide global Internet service. We examine the problem of designing the inter-satellite network for low latency and high capacity. We posit that the high density of these new constellations and the high-velocity nature of such systems render traditional approaches for network design ineffective, motivating new methods specialized for this problem setting.

We propose one such method, explicitly aimed at tackling the high temporal dynamism inherent to low-Earth orbit satellites. We exploit repetitive patterns in the network topology such that we avoid expensive link changes over time, while still providing near-minimal latencies at nearly 2x the throughput of standard past methods. Further, we observe that the geometry of satellite constellations admits more efficient designs, if a small, controlled amount of dynamism in links is permissible. For the leading Starlink constellation, our approach enables an efficiency improvement of 54%.

SpaceX Starlink Phase 1: Starlink's first phase will have 1,584 satellites, in 24 orbits (53°, 550 km), each with 66 satellites. We evaluate our motif-based approach using both (a) the maximum ISL range, with only the visibility constraint, which is 5,014 km; and (b) the minimum range necessitated by +Grid, 2,006 km. The latter represents worst-case power-limited ISLs.

Traffic matrix: 1,000 most populous cities (2025 population estimates) as ground sites, with city-city traffic volume scaled ∈ [0, 1] in proportion to the population products of the city pairs. (We also examine a different workload based on economic activity in the paper.)

Software dependencies: Experiments in this paper were run on Ubuntu 16.04 with Python 3.6.8. The Python packages used are ephem and networkx. The scripts use gnuplot 5.0 or higher (for the pdfcairo/pngcairo terminal). But if you don't have it, you can still get the result files and plot them using other software.

A can connect to any satellites within its view (circle). If A chooses B and C, repeating this pattern across all satellites fully specifies the constellation's ISLs. Then any satellite A′ has the same local view of its connectivity, as shown. We call such local views motifs.

For the 40² constellation, the above figure shows the topology's average stretch and hop-count for each motif at one arbitrarily chosen system snapshot in time. The metrics are computed using the population-product traffic matrix across popular cities. For clarity, we trim the plot to leave out motifs with overly large stretch or hop count. Key take-aways: (a) Different motifs differ widely in their performance; (b) motifs expose a trade-off between stretch and hop count, with several motifs at the Pareto frontier.

+Grid provides low stretch (1.25), but with very high hop count (10.57).

The above table shows improvements in the M₁ (median of sum of average weighted stretch and hop count across city-pairs) and Φ₁ (weighted M₁ sum) for Starlink, Kuiper, and a 40² constellation. The largest reductions in the metrics are for Starlink, where even with worst-case assumptions about ISL range, improvements of 37% (median M₁) and 40% (Φ₁) are achievable. This is due to Starlink's structure with fewer orbits and more satellites in each orbit. Fewer orbits imply that satellites in adjacent orbits are farther from each other, necessitating a higher minimum ISL range for +Grid, while a larger number of satellites per orbit imply an increased number of candidates for longer ISLs.