Network topology design at 27,000 km/hr

By on 25 Feb 2020

Category: Tech matters

Tags: , , ,

Blog home

How do you design a network with constituent hardware zooming around in space at 27,000 km/hr?

It seems like a question for science fiction, however, such networks will soon be a reality: for instance, SpaceX’s Starlink and Amazon’s Kuiper both plan to build mega-constellations with thousands of low-flying satellites offering broadband Internet.

Starlink has already deployed more than 200 satellites, with a goal of adding 120 per month in 2020, targeting partial service availability this very year!

Figure 1 — An example constellation consisting of uniformly spread orbital planes and satellites.

Its phase-I satellites will be inclined at 53 degrees to the equator, thus spending more time over densely populated latitudes compared to orbits that traverse over the poles. Satellites will be deployed in different orbital planes spread uniformly around the globe, with each plane having the same number of satellites, as shown in the adjacent figure.

While satellite networking has existed for decades, most satellite Internet services use geostationary satellites (GEO, 35,786 km altitude). In contrast, the new constellations will operate in low-earth orbit (LEO, 300-2000 km altitude), reducing latency by more than 60x. In fact, for far-separated communicating entities (beyond a few thousand kilometres), such constellations will be faster than today’s fibre connectivity.

While the new constellations hold great promise in terms of global connectivity and latency, their scale and dynamicity pose new networking challenges.

One such problem, which we are exploring, is that of inter-satellite connectivity: how should the thousands of satellites be connected to each other to maximize network capacity and minimize the end-end latency of paths traversing through several satellites? Each satellite must connect to only a few others, limited by the equipment it carries. For Starlink, based on recent regulatory filings, this limit on inter-satellite links (ISLs) per satellite is four (although phase-I may forego ISLs entirely.)

For small-scale networks of the past, made up of tens of satellites, only simple inter-satellite connectivity was possible, with each satellite connecting to fore- and aft- neighbours in its own orbital plane, and two neighbours in adjacent planes — a pattern we refer to as +Grid, due to its shape. However, in the new mega-constellations, each satellite will be able to choose its four peers from hundreds of nearby satellites.

Achieving higher capacity using fewer satellite-satellite hops 

The problem of choosing ISLs is already computationally hard as described, and becomes more complex still when one considers the system’s dynamics: satellites travel fast relative to each other and the Earth, covering large distances such as the Atlantic crossing in minutes. This implies that ISLs that are feasible now will become infeasible minutes later. Given that ISL setups can take from a few seconds to tens of seconds, continually changing ISLs wastes resources. Thus, we must use ISLs that survive for longer periods.

For our work on efficient inter-satellite interconnects, we at the Department of Computer Science, ETH Zürich, assumed that the trajectories of satellites are given (for example, per Starlink’s regulatory filings), and focus on picking the ISLs.

A key observation is that +Grid uses a large number of satellite-satellite hops between distant destinations. On each hop, the end-end communication consumes resources, limiting throughput. We would thus like to build networks that minimize hop-count, while also not compromising on end-end latency.

Although similar problems have long been tackled in topology design for fixed infrastructure, using integer programming, random regular graphs, and ant-colony optimization, we find these methods are inadequate for the mega-constellation context, being too computationally expensive, and/or incapable of coping with the ISL-dynamics.

Figure 2 — A multi-motif scheme, where one motif (green) is used near the equator, and different motifs (in blue and red) are used farther away.

To address these challenges, we exploit structure and repetition. We frame motifs consisting of two links from one satellite to two other satellites and construct the network by repeating such motifs network-wide. (Specifying two links for a satellite in a motif is enough, as its other two links are connected to by other satellites.)

By constructing motifs only across satellites that travel together, we ensure that ISLs are continually feasible. Further, by exhaustively searching the set of possible motifs, we can pick the one that meets an operator’s objectives in terms of hop-count and latency for a given traffic model.

We can further build on this idea by exploiting the geometry of the proposed constellations, whereby satellite density increases away from the Equator, translating to more motif possibilities. If we allow a few ISL changes per orbit (~100 minutes), we can use different motifs at different latitudes (see Figure 2).

Will networking research keep pace with the hectic satellite launch cadence?

Putting all this together, for Starlink’s phase-I, our approach would improve performance (as a linear combination of hop-count and latency) by more than 2x compared to +Grid for intuitive traffic models. Similar benefits are realizable for Kuiper.

These results are nevertheless only scratching the surface: there is a broad swath of networking problems, including further work on topologies, satellite trajectory design, routing within the constellation and to the terrestrial Internet, and congestion control, that will all need rethinking in this new and exciting context.

Computer scientists at ETH Zürich are proposing a novel network design that could double the network capacity of low-flying satellite Internet systems.

Debopam Bhattacherjee is a fourth-year PhD candidate at ETH Zürich. His research interests include satellite networking, network design, and Internet architecture.

Rate this article

The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.

Leave a Reply

Your email address will not be published. Required fields are marked *