Welcome to my talk on how to design a network's
topology
when its components are moving at speeds of 27,000
km/h.
Let me start by touching upon three fantastic
recent advances in space technology.
Reusable boosters which come back to Earth after
launching rockets, thus reducing launch costs.
Significant reduction in size and weight of
satellites,
thereby packing more satellites per launch,
reducing costs.
And automated link tracking which enables inter-satellite
laser communication.
Products offering laser inter-satellite
connectivity at 10 to 20 G
at distances up to 8,000 km are already available.
One caveat is that it takes a few seconds to tens
of seconds to establish these laser ISLs.
This will later be important when we discuss the
various topology design challenges.
But what are all these developments leading up to?
The primary goal is to build mega constellations
consisting of thousands of low-flying satellites
which provide global low-latency internet
coverage.
SpaceX is leading the front.
Their project is named Starlink and they have
already deployed more than 800 satellites in
orbit.
During the first phase, they plan to deploy 1,600
satellites and start providing internet coverage.
Their long-term plan is to deploy tens of
thousands of very low-flying satellites.
Amazon is working on a similar project named Kuiper
and plans to deploy more than 3,000 satellites in
three phases
with each phase having slightly differing
configurations.
Various companies and startups have joined this
race and have their projects at different levels
of maturity.
We here explore how to connect satellites with
each other in order to build such networks and
deliver traffic effectively.
But before we discuss topology design, we'll go
through a primer on constellation design
followed by discussions on the challenges of LEO
networks and the utility of ISLs.
First, a brief primer on the proposed satellite
constellations is necessary to set the context.
How do we describe a constellation and what
features distinguish this setting from
traditional terrestrial networks?
The first descriptive parameter I'll mention is
altitude.
A geosynchronous or geosatellite has a height of
36,000 kilometers
and the minimum round-trip times or RTTs are
nearly 240 milliseconds.
Lower-Earth orbit or LEO satellites, on the other
hand, fly at heights between 300 and 2,000
kilometers,
thus reducing RTTs by more than 60x.
Another descriptor is orbital inclination.
Each orbit here has several satellites.
While polar orbits travels over the poles, orbits
can also be inclined.
Inclination is the angle between the orbit and
the equator.
Here, the inclination is 53 degrees.
Inclined orbits restrict satellites over densely
populated lower latitudes.
For polar orbits, the inclination is 90 degrees.
Laser or radio links can be used between
satellites, with laser offering higher data rates.
Typically, there is a north-south-east-west
connectivity pattern, which I will refer to
throughout as plus grid.
To the best of our knowledge, all publicly
available scientific papers, patents, and visualizations
assume the same plus grid connectivity.
A key feature of this constellation's promised
connectivity is lower latency over distances
beyond a few thousand kilometers.
In this example, we are seeing a path between Zurich
and Mumbai over satellites,
which is quite close to the geodesic compared to
fiber, which is roughly 2x longer.
The speed of light being two-third in fiber
compared to free space means that the fiber path
will be 3x higher latency.
We will refer to this inflation over geodesic, in
this case 3x for fiber, as stretch.
We compared the RTTs between the eight most
popular cities over today's internet to the
estimated RTTs over a plus grid constellation
consisting of 1600 satellites.
The estimated RTTs are 70% lower than today's
internet at the median.
So, if the current RTT is 100 milliseconds, the
estimated RTT is 30 milliseconds.
The estimates for the satellite network are a bit
optimistic as we did not consider latency
inflation due to encoding, error correction, and
other factors.
But even a 20% increase in the estimate would
result in an RTT of 36 milliseconds, which is
still significantly lower than today's internet.
We could also see from the plot that the latencies
over satellite paths are very close to the geodesic
latencies at the speed of light in vacuum.
Let us now explore the system dynamics of these
constellations.
Satellites move very fast related to the Earth
and with respect to each other.
If a satellite is now over eastern Brazil, in 6
minutes it will already reach Africa, crossing
the entire Atlantic, traveling more than 500 km/min.
Such highly dynamic behavior translates to links
becoming infeasible in minutes.
We should keep this in mind while exploring topology
design and prioritize links which are available
for longer periods.
Having gone through the primer, let us now look
at some of the challenges that arise due to the
scale and extreme dynamicity of these mega-constellation
networks.
Our work at ACM HotNets 2018 discusses the
opportunities and challenges of these networks in
further details.
Of course, topology design is a challenge.
How do we define the trajectories of the
satellites and set up inter-satellite links in
order to serve the geographically distributed
population?
The various objectives, constraints, and
challenges and geographically varying demands
make topology design a high-dimensional
optimization problem.
We do not yet know whether the Starlink
constellation is the optimal solution to this.
Let us now see an interesting implication of a
satellite autonomous system or ACE on BGP routing.
Each of the 4 terrestrial ACEs, AS1 through AS4,
pair with the satellite ACE, which is ASAT.
AS1 has two equal ACE length paths to AS3,
through AS2 and ASAT.
The geographic distances could mean that where
ACE is choosing routes based on latency, AS1
should prefer the terrestrial route to AS3.
Likewise, AS2 has two similar paths to AS4.
AS2 should ideally prefer the satellite route to
AS4 in order to lower the latency.
While it is already the case that ACE path
lengths in today's internet are poor proxies for
performance, these satellite networks may make
this discrepancy larger in magnitude and more
commonplace.
Let us now see how routing can be made weather-aware
and what can be the implications.
Imagine this is the path through which data is
delivered to the destination.
Cloud cover can introduce significantly higher
loss rates based on operating frequencies.
One approach to deal with this problem is to reroute
network traffic around such cloud cover.
This results in lower loss rates but can increase
the aggregate stretch of the network due to
higher latencies.
Let us now look at congestion control challenges.
This graph plots the time-varying latency between
the two locations for a period of 2000 seconds at
a granularity of 1 second.
Even recently proposed congestion control schemes
like PCC Vivace, VBR, or COPA do not account for
such variations in latency.
They either assume end-to-end latency to be fixed
or try to estimate the minimum latency to be the
smallest seen over the last few round trips.
Any additional delay is considered as a mark of
congestion.
Note that such delay due to path latency and path
changes is highly predictable in satellite
networks.
Also, frequent path changes result in packet reordering,
thus affecting even loss-based congestion control
schemes.
Having gone through the general challenges, let
us quickly touch upon the utility of laser ISLs
before we start discussing topology design.
Our work at ACM HotNets 2020 discusses the
benefits of having ISLs in further details.
Despite the high-bandwidth, low-latency ISL
promise, there is substantial uncertainty about
whether or not LEO constellations will
successfully incorporate ISLs.
One hurdle may be the burn-on-reentry requirement
that regulators are asking operators to satisfy,
thus not risking injury and damage from deorbiting
satellites.
In response, Starlink's filings were amended to
exclude mention of these components.
None of the hundreds of already deployed Starlink
satellites feature ISLs.
Luckily, LEO networks do not need ISLs to provide
service.
One might think how to achieve long-distance end-to-end
connectivity when there are no ISLs.
Remember, as the constellations are being rolled
out, ground terminals would also be rolled out.
These terminals include user terminals on land
and those mounted on airplanes and ships, and
also more powerful ground stations.
Without ISLs, connections between far-separated
ground terminals bounce up and down between
satellites and on-path terminals, yielding a bent
pipe or BP connectivity.
Latency lower than terrestrial Internet can be
often achieved over long distances even with this
restricted BP connectivity.
A paper in HotNets 2019 focuses primarily on such
latency benefits.
However, in our work, we quantitatively show that
even with dense ground station deployments, there
are three very significant downsides to foregoing
ISLs.
Although LEO networks without ISLs still provide
low latency between many ground locations, the
temporal variation in latencies increases
substantially.
The network-wide throughput decreases heavily,
and the network becomes more vulnerable to
weather disruption because of transit through
satellite ground links.
In-depth quantitative analyses of these downsides
are in the paper in case you are interested, but
to give some brief insight, let us touch upon
temporal latency variations and impact of weather.
With BP, the path between Maceo in Brazil and Durban
in South Africa, for example, sees an inflation
of 100 milliseconds over time.
This is because the density of weather traffic is
much sparser over the South Atlantic than the
North.
Hence, the path often ends up using aircraft
flying over the North Atlantic as intermediate hauls.
Note that this behavior not only inflates the RTT
of this path significantly, but also makes the
heavily used paths over the North Atlantic even
more congested.
By virtue of inter-satellite links in a dense
deployment of satellites, such latency variations
get reduced by as much as 80%.
The impact of weather would be significantly
higher on BP connectivity than on ISL
connectivity.
For paths consisting of ISLs, this value is
either the first or last hop attenuation,
whichever is worse.
But for BP paths, this is the worst attenuation
seen across all links of the zigzag path bouncing
between the satellites and GT.
In this example, the heat map depicts the 99.5th
percentile attenuation across Southeast Asia.
Although both endpoints, Delhi and Sydney, are in
low attenuation areas, BP ends up using
intermediate hops in regions with higher attenuation.
In contrast, the ISL path avoids this entire high
attenuation region.
There are various other benefits of ISLs which BP
struggles with, which I briefly touch upon.
BP connectivity between certain sources and
destinations is bound to require GTs in countries
and regions that an operator would like to avoid,
either because of challenging topography or due
to political reasons.
Car and Ku-band radio spectrum for the up and
down links needs licensing.
In contrast, thanks to the narrow beams and
negligible interference issues, inter-satellite
laser connectivity is unlicensed.
GSO satellites fly above the equator and operate
in the same frequency bands sought for LEO
communication.
Thus, LEO satellites when crossing the lower latitudes
near the equator must avoid interference with GSO
satellites.
While GT field of view is already restricted by
the minimum angle of elevation, GSO arc avoidance
makes this field of view even more restricted.
The impact of this will be much higher on BP than
on ISL connectivity for traffic between the
northern and southern hemispheres.
Here is the latest update on the status of ISLs.
In their September 3 launch video, a SpaceX
personnel announced the testing of laser ISLs in
LEO.
But a lot of uncertainties regarding ISLs still
exist.
What would be the link capacities in practice?
Link setup is constrained by the fact that it
takes a few seconds to tens of seconds to
establish laser ISLs.
How do we connect satellites using ISLs keeping
in mind these constraints?
This is what we discuss next.
Such analysis is also relevant for constellations
like OneWave which do not plan to incorporate
laser ISLs.
Okay, having gone through general challenges and
the utility of having ISLs, we come back to the
problem at hand.
So how can we connect satellites in order to
offer higher aggregate bandwidth keeping in mind
the dynamics of the system?
This work was published at ACM CONIX 2019 and is
the main focus of this talk.
I will now discuss what are the constraints we
consider and assumptions we make.
The key constraint of this system is system
dynamics.
Satellites flying fast relative to the Earth and
to each other.
But we have other constraints as follows.
Setting up links can take a few seconds to tens
of seconds, during which time the involved
communication units cannot transfer data.
Hence, it's important to minimize changes in
which links are connected.
Also, the maximum number of ISLs per satellite is
limited.
In our work, we consider 4 ISLs per satellite
following all recent FCC filings, but we believe
our methods can be extended for other numbers.
I'll also lay out the assumptions we are making
in solving the inter-satellite topology design
problem.
We assume that the satellite trajectories are
given.
We rely on FCC filings by SpaceX and Amazon that
describe their trajectories.
While trajectory design in itself is an
interesting question, we have not explored it in
this work.
Knowing what precise traffic will be served on
these constellations is difficult.
Our evaluation uses traffic matrices drawn from
intuition, but the same approach can be used for
arbitrary input traffic.
Our focus is on the satellite-to-satellite
connectivity, so we assume that the ground
satellite connectivity follows a simple range-bounded
model.
We treat plus-grid connectivity, which I already
touched upon earlier, as our baseline.
On the last point, plus-grid being the baseline,
what are we trying to improve?
One drawback of these very local links to
adjacent satellites is that one requires large
number of hops to reach distant destinations.
On each hop, the end-to-end communication
consumes resources, limiting the network's
throughput.
We would thus like to build networks that give
short paths but also admit high capacity.
We don't need to stick to plus-grid's very local
links.
The key constraint on ISLs is for them to not dip
into the mesosphere.
This is the atmospheric layer that extends to
about 80 km above the Earth's surface, beyond
which there is no water vapor present.
Given the altitude of satellites, in this example
550 km, using simple geometry, we can calculate
the maximum permissible ISL length, that is about
5000 km here.
This observation opens up a large design space.
While at small scale, with few tens of satellites,
only simple connectivity was possible, in the
large proposed constellations, each satellite can
now reach many more satellites.
We are still restricted to being able to connect
to only a few though, limited by the maximum
number of ISLs per satellite.
In picking the particular subset of links to
connect, what should we optimize for?
We use simple intuitive traffic matrices for our
evaluation.
We pick the 1000 most popular cities and use a
population-product traffic matrix.
Let city1, city2, and city3 be 3 cities with
different populations.
The traffic between city pairs is proportional to
their population product.
We also tested a variant which relies on GDP
instead of population.
Recall that I earlier mentioned stretch and hop
count.
Stretch is the inflation in latency over the
minimum possible, that is traveling the geodesic
at the speed of light in vacuum.
Hop count accounts for resource consumption and
hence congestion.
In our paper, we show that lower hop count
actually translates to less congestion in these
networks.
We also define an aggregate metric as a linear
combination of stretch and hop count, with alpha
being the weight or importance of stretch.
Superficially, this seems like a traditional
network topology design problem.
These are known to be hard even in static
settings, but a variety of heuristics are used in
practice.
One key contribution of this work is showing why
traditional techniques don't work here.
We tried integer programming, but it suffers from
two major shortcomings.
It is limited in scalability.
Runtime is greater than 2 days even for 25 cities
on a beefy machine, and the estimate is roughly
10^29 days for 1000 cities.
But even if we manage to speed up the ILP by a
large factor or use appropriate approximation
techniques, there is a more fundamental issue
here.
The set of ISLs minutes apart are more than 90%
different.
We should remember that ISL setup times are few
seconds to tens of seconds.
So even if we could solve the problem optimally
for a snapshot, the set of optimal links varies
significantly minute to minute.
Hence, to maintain optimality, the system would
need to break and make a lot of links continually,
resulting in significant disruption of
connectivity.
We also tried random graphs as they are shown to
be useful in other settings like data centers.
Although such random graph generation is faster,
it also suffers from large number of links
becoming infeasible within a few minutes.
Regaining lost connectivity is not
straightforward, and one would have to break and
make many links.
Additionally, random graphs are very inflexible
and do not allow the operator to decide on the
operating point.
They simply yield one combination of stretch and
hop count without any control over which
dimension to optimize for.
So where do we go from here?
This, this, and this picture have something in
common.
They illustrate the use of structure and
repetition for design, in this case visual design.
We apply the same idea of repetitive geometric
structure to network topology design.
Consider this 1600 satellite constellation.
This is the field of view or connectivity for one
satellite, which goes beyond plus grid.
A motif consists of two links with two other
satellites, and this pattern can be repeated
throughout to build the network.
Note that in this case two linked motifs are
sufficient, as remaining two would be filled by
other satellites connecting to this satellite.
One obvious benefit of using motifs is the fact
that they have minimum link churn.
Nearby satellites in adjacent orbits move
together and are always in the field of
connectivity of each other and can remain
connected continually.
We have analyzed three different constellations.
A uniform constellation consisting of 40 orbits
and 40 satellites per orbit, operating at an inclination
of 53 degrees and an altitude of 550 kilometers.
SpaceX Starlink Phase 1, which consists of 24
orbits with 66 satellites per orbit, operating at
an inclination of 53 degrees and an altitude of
550 kilometers.
And Amazon Kuiper Phase 1, which is again a
uniform 34-square constellation, operating at 51.9
degrees and 630 kilometers.
Here we plot the average hop count along x-axis
and average stretch along y-axis for the
different motifs.
Note that both stretch and hop count are weighted
by the traffic matrix, in this case population
products for city pairs.
Different motifs offer different trade-offs in
stretch and hop count, and we can see a Pareto
frontier of motifs superior to the rest in both
hop count and stretch.
Not only do motifs offer performance better than
random graphs, they also provide higher
flexibility to an operator.
Note also that the random graph solution also
suffers from link churn.
So where is our baseline plus grid in all of this?
This is where plus grid operates, with the best
available stretch, but very high hop count, thus
being a low efficiency motif.
Note that the slope of this frontier is small
enough on the right side, such that by
sacrificing 2% stretch, one can improve hop count
by as much as 32%.
This is one of the resulting motifs for the 40-square
constellation, that provides much higher
efficiency than plus grid, using a combination of
long and short links of different orientations.
I am showing the two links in the motif in
different colors here for clarity.
So the motifs perform well, but can we do even
better?
Yes, by exploring the geometry of these constellations.
Compare the field of view of a satellite at the
equator to one at a higher latitude.
We see the constellation is denser at higher latitudes.
This translates to more options for connectivity
as we go higher up from the equator.
This plot quantifies the number of motif
possibilities at different latitudes.
For polar as well as inclined constellations, the
number increases significantly with latitude.
For example, for the inclined constellation,
there are around 1000 options at the equator
versus around 3500 at higher latitudes.
So how do we exploit this characteristic?
Consider a single orbital plane.
A quadrant of this orbit consists of 10
satellites out of the 40 in total in this orbit.
We split the quadrant into multiple zones, 3 in
this case.
First, we find the optimal motif for the entire
constellation, considering only the motif choices
available at zone 1.
Then, keeping zone 1 links fixed, we remove the
rest of the links.
We repeat the same process for zone 2 and then
for zone 3 and arrive at the 3 zone multimotif.
This is the final 3 zone multimotif scheme for
the 40 squared constellation we are looking at.
As you can see in the plot, the multimotifs offer
a higher performance beyond the single motif
frontier.
Different alpha values result in different multimotifs,
and as we give higher priority to stretch, the
schemes move towards plus grid.
Putting all of this together, these are the
performance improvements above the baseline plus
grid connectivity.
Starling sees more than 2x improvement over
baseline, while Kuiper also has similar benefits.
We also considered settings where the links need
to be shorter due to power constraints instead of
just the visibility constraint we considered thus
far.
In the most pessimistic case, a constellation
must at least allow link lengths that suffice for
plus grid connectivity.
Even in this worst case scenario, Starling sees a
40% improvement over plus grid.
I'll briefly note that this work is just one of
several satellite networking problems we are
exploring in our lab.
So now I touch upon some of the open questions we
are trying to attack.
How do we design satellite trajectories in order
to improve network performance?
There are various dimensions to explore,
including the number of shells, orbits,
satellites per orbit, inclination, and elevation.
We are working on routing and congestion control
challenges, as I briefly touched upon earlier in
this talk.
To help bootstrap research in this area, we are
actively developing packet-level and flow-level
simulators that capture the necessary system
dynamics.
With that, I thank you for your attention, and
now I'm open to questions.