From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp80.iad3a.emailsrvr.com (smtp80.iad3a.emailsrvr.com [173.203.187.80]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 7E1293B2A4 for ; Sun, 12 Dec 2021 16:12:01 -0500 (EST) Received: from app23.wa-webapps.iad3a (relay-webapps.rsapps.net [172.27.255.140]) by smtp27.relay.iad3a.emailsrvr.com (SMTP Server) with ESMTP id CDDF0210F2; Sun, 12 Dec 2021 16:12:00 -0500 (EST) Received: from deepplum.com (localhost.localdomain [127.0.0.1]) by app23.wa-webapps.iad3a (Postfix) with ESMTP id B9D59618E3; Sun, 12 Dec 2021 16:12:00 -0500 (EST) Received: by apps.rackspace.com (Authenticated sender: dpreed@deepplum.com, from: dpreed@deepplum.com) with HTTP; Sun, 12 Dec 2021 16:12:00 -0500 (EST) X-Auth-ID: dpreed@deepplum.com Date: Sun, 12 Dec 2021 16:12:00 -0500 (EST) From: "David P. Reed" To: "Vint Cerf" Cc: starlink@lists.bufferbloat.net MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_20211212161200000000_18043" Importance: Normal X-Priority: 3 (Normal) X-Type: html In-Reply-To: References: <1639341564.906916211@apps.rackspace.com> X-Client-IP: 209.6.168.128 Message-ID: <1639343520.758213978@apps.rackspace.com> X-Mailer: webmail/19.0.13-RC X-Classification-ID: 9cf595f1-e162-4300-bbc9-213bfaa06811-1-1 Subject: Re: [Starlink] some details on the DTN, bundle protocol, and a capacity question X-BeenThere: starlink@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: "Starlink has bufferbloat. Bad." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 12 Dec 2021 21:12:01 -0000 ------=_20211212161200000000_18043 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable =0AActually, there are rateless erasure codes that don't require you have a= ll the data in advance for the code.=0A =0ABut before you get to that requi= rement, just number all the messages in a flow in a monotonic numbering sch= eme (source ID, destination ID, sequence number), and treat each message as= a digital fountain.=0AThat's not an optimal code (it's a hybrid). =0A =0AW= hat's key about this hybrid is that if you think about it, discarding messa= ges at the ultimate receiver works fine, and thus the buffer at the receive= r can be arbitrarily reduced - all it needs is, at minimum, the space to de= code one message.=0A =0AThe key idea in TCP is that every bit sent by the s= ource 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 retra= nsmissions of the same bits). You know this, but I'm stating it in the form= of an invariant.=0A =0AThis "source keeps it all until positive acknowledg= ement" by itself is inefficient when packets get lost, because the retransm= issions are stabs in the dark, and may be redundant.=0A =0ARateless 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 reconstruct= able from any sufficiently long sequence of these combined packets.=0A =0AT= he 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.=0A =0AIn fact, yo= u 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 spac= e on the channel for extra packets, you can start sending combinations of t= he bits already sent, even if you don't know all of the original source bit= s. This is a bit farther from "optimal", because those packets may not have= been necessary.=0A =0AAnyway, I'm not proposing a particular solution here= - I'm just saying that the conceptual framing of the issue in terms of rat= eless erasure coding on the intermediate mesh creates the opportunity to ge= t much closer to what one might want if one were trying to deal with very l= ong end-to-end delays in a store and forward routing network.=0A =0A =0A = =0AOn Sunday, December 12, 2021 3:47pm, "Vint Cerf" said:= =0A=0A=0A=0AI am a fan of Fountain codes - however, it only works if you ha= ve all the data you are going to send in hand before encoding. =0ADavid, if= there is a way to do this with data that is being generated on the fly wit= h sensors, that would be of interest.=0AOf course, one can "chunk" the data= , fountain-code it, and reconstruct "chunks" on receipt. =0Av=0A=0A=0AOn Su= n, Dec 12, 2021 at 3:39 PM David P. Reed <[ dpreed@deepplum.com ]( mailto:d= preed@deepplum.com )> wrote:=0AIt's worth noting that the patents on Bill L= uby's digital fountain codes, etc. have pretty much inhibited one of the be= st 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 ap= parently negotiated a license for that very specific use in that specific p= rotocol, as long as it is never used in "wide area wireless" (see the detai= ls of the narrow license here) networking. [ https://datatracker.ietf.org/i= pr/2554/ ]( https://datatracker.ietf.org/ipr/2554/ )=0A =0ARateless erasure= codes of ANY kind appear to be covered by the claims in the early Digital = Fountain patents.=0A =0ANow why are rateless erasure codes important for DT= N? Well, essentially such codes have a *unique* property that is pretty sur= prising:=0A =0AThe coded form of any N-bit message (composed of segments th= at 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 re= ceiver receives a subset of distinct segments, totalling N or more bits, th= e entire N-bit message can be reconstructed.=0A =0AThat's what makes the co= de "rateless" - it works for ANY error rate, and is optimal for that error = rate.=0A =0ATo solve the DTN problem, you simply send each message as a seq= uence of coded segments. No windowing is required, no retransmission of pac= kets that are lost on one hop is required. Eventually, the message gets del= ivered, and it will take no more time than the error rate on the path requi= res.=0A =0AThat's remarkable. =0A =0AThere are of course some issues to res= olve - when should a message source assume that its message has been reliab= ly and completely received by the intended destination?=0AThis is the "end-= to-end" problem. If there is a reverse channel, once a message has been rec= eived, the receiver should, at least each time it receives a segment of som= e already completed message, send a single ACK for that message. =0A =0ANow= this is great for talking to a spacecraft that has a very low speed and no= isy reverse channel.=0A =0AAny number of messages can be concurrently sent = from any number of sources (the requirement is that each message has a glob= al unique ID).=0A =0AFair sharing of a multiplexed deep-space network's res= ources among many concurrent messages is a bit more tricky. That's where "e= arly ACks" might be used in an advanced erasure code (one I doubt has been = patented fully, at least I've never seen that).=0A-------------------------= ----------=0ANow, my personal view about *patents* on communications protoc= ols is very severe: since interoperability is the *essence* of communicatio= ns protocols, the idea of patents is antithetical to the utiliity of protoc= ols. Just as mathematical algorithms should not be patentable subject matte= r, neither should communications protocols (which are just algorithms on a = different abstract machine).=0A =0AUnfortunately, Luby, et al. have threate= ned litigation over and over, stymieing attempts to get usage of their rema= rkable invention, outside a few monopolistic or oligopolistic licensees.=0A= =0AIt looks like, even though the original patents are due to expire soon,= lots of effort is being made to insure that all possible derivable techniq= ues are being patented to extend this monopoly.=0A =0AConsequently, I'd sug= gest that someone might find a way to "buy out" the inventors of these pate= nts and their assignees. It's a cancerous growth.=0A =0AImagine if we who b= uilt 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).= =0A =0ABill Luby, his advisors, etc. did a remarkable thing here. And like = other inventors, he ought to be rewarded for his invention. I have no probl= em with that. What I have a problem with is the structure of patent law as = it exists today. It is socially counterproductive, and economically counter= productive, when used in the way it is being used here.=0A =0ABut that's ju= st my opinion.=0A =0APS: I am co-inventor of a fair number of patented inve= ntions. I live in this broken system. But, in the case of communications pr= otocols specifically, I think this stuff shouldn't be protected by patent r= ights.=0A =0A _______________________________________________=0A Starlink m= ailing list=0A[ Starlink@lists.bufferbloat.net ]( mailto:Starlink@lists.buf= ferbloat.net )=0A[ https://lists.bufferbloat.net/listinfo/starlink ]( https= ://lists.bufferbloat.net/listinfo/starlink )=0A-- =0A=0A=0A=0APlease send a= ny postal/overnight deliveries to:=0AVint Cerf=0A1435 Woodhurst Blvd =0AMcL= ean, VA 22102=0A703-448-0965=0Auntil further notice ------=_20211212161200000000_18043 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

Actually, there are ra= teless erasure codes that don't require you have all the data in advance fo= r the code.

=0A

 

=0A

Bu= t before you get to that requirement, just number all the messages in a flo= w in a monotonic numbering scheme (source ID, destination ID, sequence numb= er), and treat each message as a digital fountain.

=0A

That's not an optimal code (it's a hybrid). 

=0A

 

=0A

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.

=0A

 

=0A

The key idea in TCP is that eve= ry 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 retran= smitted at any time (the rest of the TCP design is about how to avoid exces= s and wasteful retransmissions of the same bits). You know this, but I'm st= ating it in the form of an invariant.

=0A

 

= =0A

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

=0A

 

=0A

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 tr= ansmitted yet, so that the lost packets are reconstructable from any suffic= iently long sequence of these combined packets.

=0A

=  

=0A

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

=0A

 

=0A

In fact, you only need to know (in that original form) the full le= ngth of the message when you have transmitted the full message (not to star= t). If there is space on the channel for extra packets, you can start sendi= ng 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.

=0A

 

= =0A

Anyway, I'm not proposing a particular solution her= e - I'm just saying that the conceptual framing of the issue in terms of ra= teless erasure coding on the intermediate mesh creates the opportunity to g= et 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.

=0A

 

=0A

 

=0A

 

=0A

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

=0A
=0A
I am a fan of Fountain codes - ho= wever, it only works if you have all the data you are going to send in hand= before encoding. =0A
David, if there is a way to do this with dat= a that is being generated on the fly with sensors, that would be of interes= t.
=0A
Of course, one can "chunk" the data, fountain-code it, and = reconstruct "chunks" on receipt. 
=0A
v
=0A
=0A
=0A
=0A
On= Sun, Dec 12, 2021 at 3:39 PM David P. Reed <dpreed@deepplum.com> wrote:
=0A
=0A

It's worth noting that t= he patents on Bill Luby's digital fountain codes, etc. have pretty much inh= ibited 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 specifie= d in it. Qualcomm apparently negotiated a license for that very specific us= e in that specific protocol, as long as it is never used in "wide area wire= less" (see the details of the narrow license here) networking. https://datat= racker.ietf.org/ipr/2554/

=0A

 

=0A

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

=0A

Now why are rateless erasure codes impo= rtant for DTN? Well, essentially such codes have a *unique* property that i= s pretty surprising:

=0A

 

=0A

The coded form of any N-bit message (composed of segments that can b= e 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 r= eceives a subset of distinct segments, totalling N or more bits, the entire= N-bit message can be reconstructed.

=0A

 

= =0A

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

=0A

 

=0A

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

=0A

 

=0AThat's remarkable. 

=0A

&nbs= p;

=0A

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?

=0A

This is the "end-to-end" problem. If there is a reverse channel, once a me= ssage has been received, the receiver should, at least each time it receive= s a segment of some already completed message, send a single ACK for that m= essage. 

=0A

 

=0A

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

=0A

 

=0A

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

 

=0A

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 advanc= ed erasure code (one I doubt has been patented fully, at least I've never s= een that).

=0A

-----------------------------------=0A

Now, my personal view about *patents* on communic= ations protocols is very severe: since interoperability is the *essence* of= communications protocols, the idea of patents is antithetical to the utili= ity of protocols. Just as mathematical algorithms should not be patentable = subject matter, neither should communications protocols (which are just alg= orithms on a different abstract machine).

=0A

 =

=0A

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

=0A

 

=0A

It looks like, even tho= ugh the original patents are due to expire soon, lots of effort is being ma= de to insure that all possible derivable techniques are being patented to e= xtend this monopoly.

=0A

 

=0A

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 growt= h.

=0A

 

=0A

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 i= n this - I'd be there with Vint in the countinghouse, probably, as a coinve= ntor).

=0A

 

=0A

Bill Lu= by, his advisors, etc. did a remarkable thing here. And like other inventor= s, 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 toda= y. It is socially counterproductive, and economically counterproductive, wh= en used in the way it is being used here.

=0A

 =

=0A

But that's just my opinion.

=0A

 

=0A

PS: I am co-inventor of a fair nu= mber 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.

=0A

 

=0A

 

=0A_______________________________________________<= br /> Starlink mailing list
Starlink@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/starlink=0A
=0A
--
=0A
= =0A
=0A
Please send any postal/overnight deliveries to:=
=0A
Vint Cerf
=0A
1435 Woodhurst Blvd 
=0AMcLean, VA 22102
=0A
703-448-0965
=0A
until further noti= ce
=0A
=0A
=0A ------=_20211212161200000000_18043--