[Starlink] some details on the DTN, bundle protocol, and a capacity question

Sun Dec 12 16:12:00 EST 2021

Actually, there are rateless erasure codes that don't require you have all the data in advance for the code.

But before you get to that requirement, just number all the messages in a flow in a monotonic numbering scheme (source ID, destination ID, sequence number), and treat each message as a digital fountain.
That's not an optimal code (it's a hybrid). 

What's key about this hybrid is that if you think about it, discarding messages at the ultimate receiver works fine, and thus the buffer at the receiver can be arbitrarily reduced - all it needs is, at minimum, the space to decode one message.

The key idea in TCP is that every bit sent by the source is retained by the source until it is positively acknowledged to have been received. All of those retained bit can be retransmitted at any time (the rest of the TCP design is about how to avoid excess and wasteful retransmissions of the same bits). You know this, but I'm stating it in the form of an invariant.

This "source keeps it all until positive acknowledgement" by itself is inefficient when packets get lost, because the retransmissions are stabs in the dark, and may be redundant.

Rateless erasure codes use the fact that there are infinitely many ways to encode *some* of the bits that have been already transmitted, in combination with new bits that haven't been transmitted yet, so that the lost packets are reconstructable from any sufficiently long sequence of these combined packets.

The basic fountain code starts by sending all of the original segments first, then starts to send various mixed up packets.  That's the only reason why you need all of the packets to be known before starting.

In fact, you only need to know (in that original form) the full length of the message when you have transmitted the full message (not to start). If there is space on the channel for extra packets, you can start sending combinations of the bits already sent, even if you don't know all of the original source bits. This is a bit farther from "optimal", because those packets may not have been necessary.

Anyway, I'm not proposing a particular solution here - I'm just saying that the conceptual framing of the issue in terms of rateless erasure coding on the intermediate mesh creates the opportunity to get much closer to what one might want if one were trying to deal with very long end-to-end delays in a store and forward routing network.

On Sunday, December 12, 2021 3:47pm, "Vint Cerf" <vint at google.com> said:

I am a fan of Fountain codes - however, it only works if you have all the data you are going to send in hand before encoding. 
David, if there is a way to do this with data that is being generated on the fly with sensors, that would be of interest.
Of course, one can "chunk" the data, fountain-code it, and reconstruct "chunks" on receipt. 
v

On Sun, Dec 12, 2021 at 3:39 PM David P. Reed <[ dpreed at deepplum.com ]( mailto:dpreed at deepplum.com )> wrote:
It's worth noting that the patents on Bill Luby's digital fountain codes, etc. have pretty much inhibited one of the best solutions for DTN out there. There's one exception - RFC 6330, which has a very, very specific use of the RaptorQ code specified in it. Qualcomm apparently negotiated a license for that very specific use in that specific protocol, as long as it is never used in "wide area wireless" (see the details of the narrow license here) networking. [ https://datatracker.ietf.org/ipr/2554/ ]( https://datatracker.ietf.org/ipr/2554/ )

Rateless erasure codes of ANY kind appear to be covered by the claims in the early Digital Fountain patents.

Now why are rateless erasure codes important for DTN? Well, essentially such codes have a *unique* property that is pretty surprising:

The coded form of any N-bit message (composed of segments that can be lost, e.g. checksummed frames that are deemed lost/erased if the checksum fails), is an infinite sequence of non-identical segments. If a receiver receives a subset of distinct segments, totalling N or more bits, the entire N-bit message can be reconstructed.

That's what makes the code "rateless" - it works for ANY error rate, and is optimal for that error rate.

To solve the DTN problem, you simply send each message as a sequence of coded segments. No windowing is required, no retransmission of packets that are lost on one hop is required. Eventually, the message gets delivered, and it will take no more time than the error rate on the path requires.

That's remarkable. 

There are of course some issues to resolve - when should a message source assume that its message has been reliably and completely received by the intended destination?
This is the "end-to-end" problem. If there is a reverse channel, once a message has been received, the receiver should, at least each time it receives a segment of some already completed message, send a single ACK for that message. 

Now this is great for talking to a spacecraft that has a very low speed and noisy reverse channel.

Any number of messages can be concurrently sent from any number of sources (the requirement is that each message has a global unique ID).

Fair sharing of a multiplexed deep-space network's resources among many concurrent messages is a bit more tricky. That's where "early ACks" might be used in an advanced erasure code (one I doubt has been patented fully, at least I've never seen that).
-----------------------------------
Now, my personal view about *patents* on communications protocols is very severe: since interoperability is the *essence* of communications protocols, the idea of patents is antithetical to the utiliity of protocols. Just as mathematical algorithms should not be patentable subject matter, neither should communications protocols (which are just algorithms on a different abstract machine).

Unfortunately, Luby, et al. have threatened litigation over and over, stymieing attempts to get usage of their remarkable invention, outside a few monopolistic or oligopolistic licensees.

It looks like, even though the original patents are due to expire soon, lots of effort is being made to insure that all possible derivable techniques are being patented to extend this monopoly.

Consequently, I'd suggest that someone might find a way to "buy out" the inventors of these patents and their assignees. It's a cancerous growth.

Imagine if we who built the Internet Protocols had filed patents on all the techniques used in the Internet? Would Vint be sitting there counting his royalties, and with a team of lawyers negotiating license agreements? (I have an oar in this - I'd be there with Vint in the countinghouse, probably, as a coinventor).

Bill Luby, his advisors, etc. did a remarkable thing here. And like other inventors, he ought to be rewarded for his invention. I have no problem with that. What I have a problem with is the structure of patent law as it exists today. It is socially counterproductive, and economically counterproductive, when used in the way it is being used here.

But that's just my opinion.

PS: I am co-inventor of a fair number of patented inventions. I live in this broken system. But, in the case of communications protocols specifically, I think this stuff shouldn't be protected by patent rights.

 _______________________________________________
 Starlink mailing list
[ Starlink at lists.bufferbloat.net ]( mailto:Starlink at lists.bufferbloat.net )
[ https://lists.bufferbloat.net/listinfo/starlink ]( https://lists.bufferbloat.net/listinfo/starlink )
-- 

Please send any postal/overnight deliveries to:
Vint Cerf
1435 Woodhurst Blvd 
McLean, VA 22102
703-448-0965
until further notice
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.bufferbloat.net/pipermail/starlink/attachments/20211212/10fdb415/attachment.html>