[Starlink] thinking about the laser links again

[Ulrich Speidel]

On 27/10/2021 8:03 pm, David Lang wrote:
> On Wed, 27 Oct 2021, Ulrich Speidel wrote:
>
>> - Get the satellites to work out where stuff needs to be sent. If 
>> they were to use something like Bellman-Ford here, that would require 
>> an enormous amount of update traffic. Dijkstra would require complete 
>> topology information, which should in principle be computable from an 
>> almanach on the satellites. But it's still a lot of number crunching 
>> on a bird. Another option would be for each satellite to compute a 
>> great circle direction to the target cell and then forward to 
>> whichever neighbour satellite comes closest to being along that route.
>
> Remember, IP routing doesn't require anybody have a global view of the 
> network, just knowlege of nearby nodes.

Reality check.

IP forwarding (as opposed to routing) checks the destination IP address 
against a set of routes in your routing table, which are essentially 
destination networks identified by network IP address and netmask. That 
decides which interface the routers forwards out through (i.e., to which 
neighbour). At a local level, one can often supply these routes manually 
as static routes, but at a global level, it still takes the likes of BGP 
to help with routing, chiefly because the Internet doesn't have a tree 
structure at the global level.

This update with BGP works nicely in a network whose structure never 
changes, or changes very slowly, so that set of routes can be updated 
manually or automatically in a cyclic fashion. But in the case of 
Starlink, much of the network changes continuously.

Things that change for you if you are a Starlink satellite:

- Cells you can service (and therefore hosts attached to Dishys you can 
reach). You may be over Brazil now, the Atlantic next, then over the UK, 
and then over Germany, and so on... So your on-board routing table would 
need to reflect that. You never spend more than a minutes or so over the 
same cell.
- Ground station gateways you can attach to - similar timing here.
- Satellites on neighbouring orbital planes in the same shell that are 
in the northbound part of their orbit while you're heading south (and 
vice versa) come within range and disappear again.
- Neighbouring satellites in different shells.

Things that don't change:

- The satellite in front and behind you in the same orbit.
- Neighbouring satellites orbiting in the same direction in adjacent 
orbital planes. These require tracking but are always in range.

So, if we're a satellite, part of our routing table changes every few 
seconds because some node that was a neighbour no longer is, and a node 
that wasn't now becomes a neighbour. And because nothing in our 
constellation-spawned network resembles a tree structure, we'd need 
something like BGP to propagate that routing information through the 
network. Because we may be the only satellite that can currently serve a 
particular destination host, that information needs to propagate through 
the network, so other nodes in the network need to know that they need 
to send traffic to that destination to us. I say "something like BGP" 
here as the network is proprietary, so doesn't have to stick to any open 
standards.

Now our neighbours are the first that need to know that we're the new 
kid on the block to talk directly to Dave's Dishy, and sending them an 
update every few seconds wouldn't be too onerous. But the problem is 
that our neighbours, too, are on the move, so we're basically forced to 
propagate our update (and everyone else's) throughout the entire network 
of thousands of satellites. Moreover, if we consider the fact that along 
a forwarding path of a dozen satellites or more between, say Tokyo and 
New York, all satellites are on the move, then losing only one link on 
that path can render a route completely infeasible. And while our 
individual satellite's neighbourhood changes every few seconds, a path 
like this might change on a sub-second scale.

So suppose we ignore anything we know about the constellation geometry 
and we have N satellites. Say we want to use IP routing still with BGP. 
Then each satellite needs to be its own Autonomous System. That boils 
down to telling each satellite in the constellation about the 
connectivity state of essentially every other satellite (or plane). 
That's an O(N^2) problem, so not very scaleable, especially if we need 
to do this every few milliseconds (with the required intervals also 
decreasing with N). So conventional IP routing doesn't work here, basically.

>
> So the satellite needs to know what are good next hops to send traffic 
> to that's headed in different directions, not global knowledge of the 
> entire constellation.

True, but that requires a knowledge of direction and a (tunnel) comms 
layer below the Internet-wide IP routing. And the question is how that's 
best designed.

>
> This doesn't require that all satellites be able to send in all 
> directions. with lots of satellites in range, they could cycle between 
> the first sending north, the second east, the third south, the fourth 
> west...
>
Yes. That's what I was hinting at with the "great circle" option.
> A key question to me is how many lasers, how fast they can be 
> redirected to different satellites, and how many different satellites 
> the detectors can receive from at one time.
>
> I'd hope that there are at least two lasers, so that they can transmit 
> to the next hop and ack to the receiver without having to spin a laser 
> 180.
That's an interesting question indeed. What I would add in here is also 
the possibility of using optical switching, where one laser beam may be 
able to be switched rapidly between different targets.
>
> It also doesn't require that the satellite send to the nearst node in 
> that direction (if longer distance traffic can be detected, you would 
> want to send to a further away next hop to reduce the number of hops)
In principle, yes, which would be good for both latency and satellite 
power budget, but satellites further away will be harder to target with 
the same data rate, so there's a trade-off here.
> They could even have a satellite varient that has more 
> lasers/detectors and fewer RF antennas to connect to the ground to be 
> dedicated to routing (especially as they launch satellites to 
> different altitudes, nodes at higher altitudes could be optimized for 
> long-distance hops)
I'd consider this not so likely - the system is complex enough as it is, 
and I doubt they'll want to add that complexity.
>
> With only 'nearby' node knowledge needed, I could see low-power 
> omnidirectional RF beacons being used for nodes to advertise their 
> existance and routing config to the network. I expect that if they 
> were doing this, that it would show up in their FCC filings and 
> everyone would be talking about it, but it's a thought for future 
> versions.
I'm speculating here, but from an engineering point of view it makes 
most sense to go with an almanach approach to constellation 
configuration, i.e., let each bird know where all other birds are at any 
one time by providing their orbital parameters to every satellite (slow 
rate of change and easy O(N) computation on the satellite). Dishys have 
a built-in GPS receiver, so can basically figure out which cell they're 
in (once movement between cells is allowed). Currently, I suspect that 
Starlink run a protocol where each bird knows which cell it's 
responsible for at any one time, and where the bird beacons to Dishys 
"Cell X, it's me, bird Y" and where the Dishys then get orbital 
parameters either from the bird or an almanach to align their phased 
arrays to the bird.
>
> All of this requies some way to tell from the packet where on earth 
> (or in space) the destination is. If you tunnel over IPv6, you can 
> have enough IPs to allocate them based on lat/long/ground/orbit so 
> that the routing nodes (which know where they are) can know what 
> direction to send things. 
That's indeed an option, although you'd still need a way of reverse 
mapping: If I have an IPv6 address I know to be in cell X in Ontario, 
which of my peers has a route to there?
> Given the existance of mobile endpoints (vehicles, aircraft, 
> spacecraft) this starts sounding like the mobile IP problem (how can 
> you continue a persistant connection when moving from network to 
> network), but since all the entry/exit points are under their control, 
> you can tunnel around and have a protocol to reconfigure the tunnels 
> as endpoints move.

Indeed, and that tunnel configuration protocol is where the challenge 
lies ;-)

For mobile networks, this task is a little easier as the network between 
the entry & exit points is more or less static. Plus, mobile nodes move 
at most at hundreds of miles per hour, not tens of thousands.

BTW: Starlink will probably want to avoid ground relays like the plague. 
The bulk of their customers won't be stock brokers, and their need will 
be for bandwidth rather than minimal latency. The bottlenecks here are 
between ground and birds, and between birds. Basically, the nominal 
capacity of each Starlink bird is purportedly somewhere around the 20 
Gb/s mark in the currently deployed generation. Now, as a rule of thumb, 
the average Internet user in the world last year used a continuous 
average of 1 Mb/s of data. If we ignore for a moment that connections 
are bi-directional and that there is such a thing as peak time, then 
that means that under the current bent pipe model, each Starlink 
satellite is restricted to at most 20k users. If they want to beat 
existing providers on the ground that already offer a few Mb/s, they 
need to slash that by at least a factor of 5, again being really 
conservative here.

Now those ground providers do have one competitive advantage, and that 
is that while their lines are long and low bandwidth, they're not 
shared, at least not to the closest CDN server farms, where 70% or so of 
today's traffic originates. If two Starlink customers want to watch the 
same cat video on FB, the video has to traverse the satellite medium 
twice, whereas if two farmers in the Midwest want to do the same on 
Verizon, they get two copies off their local CDN and you don't get as 
much as a blip on regional or international fibre cables (which 
generally run at rates > 20 Gb/s these days).

So if Starlink want to keep customers happy with dozens of Mb/s on 
demand, each bird will at most be able to handle a few hundred active 
customers at a time. Any use of multiple ground relays along a path 
would cut that number substantially.


-- 
****************************************************************
Dr. Ulrich Speidel

School of Computer Science

Room 303S.594 (City Campus)
Ph: (+64-9)-373-7599 ext. 85282

The University of Auckland
ulrich at cs.auckland.ac.nz
http://www.cs.auckland.ac.nz/~ulrich/
****************************************************************