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

[Vint Cerf <vint@google.com>]

[-- Attachment #1: Type: text/plain, Size: 8283 bytes --]

definitely like this element of added robustness, David.
v


On Sun, Dec 12, 2021 at 4:12 PM David P. Reed <dpreed@deepplum.com> wrote:

> 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@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@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/
>>
>>
>>
>> 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@lists.bufferbloat.net
>> https://lists.bufferbloat.net/listinfo/starlink
>
>
> --
> Please send any postal/overnight deliveries to:
> Vint Cerf
> 1435 Woodhurst Blvd
> McLean, VA 22102
> 703-448-0965 <(703)%20448-0965>
> until further notice
>


-- 
Please send any postal/overnight deliveries to:
Vint Cerf
1435 Woodhurst Blvd
McLean, VA 22102
703-448-0965

until further notice

[-- Attachment #2: Type: text/html, Size: 13933 bytes --]