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

Sun Dec 12 17:11:24 EST 2021

There's this, too:

Sundararajan, J.K., Shah, D., Médard, M., Jakubczak, S., Mitzenmacher, 
M., Barros, J.O.: Network coding meets TCP: Theory and implementation. 
Proceedings of the IEEE, 99(3), 490-512 (2011)

Moreover, you can also use these codes to protect limited sets of N 
packets, and you don't have to have all N of them in hand to start 
encoding. If you encode the first N packets with an identity matrix and 
then push M coded redundancy packets down the line afterwards, then any 
subset of N of these N+M coded packets can be used for complete recovery 
of all N packets, but the use of the identity matrix also allows you to 
encode packets as soon as their content becomes available at the sender, 
and decode them as soon as a packet arrives at the far end.

We've used these with some success to tunnel TCP/IP on shared MEO and 
GEO satellite links. But yes, that's experimental, as the codes are 
patented, too.

Note also that protecting packets against bit errors and protecting 
packets against drops are two wholly different applications. A code that 
protects against bit errors can be accommodated self-contained in a 
single packet, whereas a code that protects against entire packet 
erasures is necessarily one that has to span multiple packets. Engineers 
tend to learn predominantly about the former packet loss mechanism 
whereas networking folk predominantly get to learn about queue drops.

Striking a balance between an inventor's interests and the interests of 
the invention to see the light of day can be tricky, obviously. I guess 
it depends to a good degree on what one, and one's employer, considers 
to be a just reward, and how much foresight goes into it. I've certainly 
seen more than one case where gifting an invention to the world in an 
open source fashion would have resulted in more kudos and - dare I say 
it - monetary rewards than the patent route that was chosen and that led 
to the idea being more or less shelved for good. But I guess it takes a 
bit of courage to put your ideas out there, and not everyone has that. I 
laud those who do.

On 13/12/2021 9:47 am, Vint Cerf wrote:
>
> 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> 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
>     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
>
>
>
>
> _______________________________________________
> Starlink mailing list
> Starlink at lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/starlink
>
-- 
****************************************************************
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/
****************************************************************

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.bufferbloat.net/pipermail/starlink/attachments/20211213/e7505941/attachment-0001.html>