From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wm1-x333.google.com (mail-wm1-x333.google.com [IPv6:2a00:1450:4864:20::333]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 1A37F3B2A4 for ; Sun, 12 Dec 2021 16:18:57 -0500 (EST) Received: by mail-wm1-x333.google.com with SMTP id 137so10664505wma.1 for ; Sun, 12 Dec 2021 13:18:57 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=N9/ASYNk/RzV/1WIgANdBGnD7kxZWstwrh8upVCOCFk=; b=NcSD2KrIeusJyKr0YadMtOVHFC/ec/Gz3rSFNeqXcSRRvYZrqMv1aFUdJHG4zIA30Y lPAJIck8QZPX6nMPoDmxH/tbJ9Dzlew9O6HbNjbXlpgbtrfiWN5wgIL18f3y5ahuHIg+ D1ahmt9cchfFB/TKL0Ffqjpfk6ZpplU63AACL/yGNGehz8PxqUvNwS+QkT+GEJ2le8Q0 6J+epzGO76YDWe5FGHKXWgb1Q1ShUpyvMBaCw+p8ionb3LXrJ81Kzqf49ZmmMHJFrmLG j/yaeLZvCibekfiMmHWDJQxsAQWHpWASHpCmFGt40I1+3oUdP44KH5KLVsQjKI0ozed+ xzfQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=N9/ASYNk/RzV/1WIgANdBGnD7kxZWstwrh8upVCOCFk=; b=ebq+fDoOrfX47cjXn/BAG4IX3iXoUnOmDUdTFsV2spNsbzAAt8ohmhU66qHD59Nvgu vFut7Ba8YiDUcT3ftHMDvTxU6XX71Kj3vemneNhNTB6yFoxazGk7LpR8+wnSnHpASDf1 mJdUQ+g06UzAFFf8YK1UQJgf4K/6Lg5TLB6vfzcON52LSgAAaFMKDK/hkXj+0bY1WJVV hnh4tULU+Ej6pqGCe6oetTmOlURLxttrA34+OsI0uSnAl8t/5FOWKKRF+zlqWkfXIB1r vxeRW3SEam22UfTAdjfiHcvbjPfzQaXP2ktNCbU3LJLGeBw4g2XH3s9OZpz0ckCIF4mL zcZA== X-Gm-Message-State: AOAM533B7HOJjDh/Pa3vsvyAIc/5XCpQBAJ05LCjbP5k5O3QdlGux2TW y+STOhmv2MXML8BdLmZ6u6Yh3d1Sb3bm3PRwWF6VaBjkWvk= X-Google-Smtp-Source: ABdhPJwxU7rINBVW325fUm42HcvjSd3AwZVZU077OBjyMQhMCR1z8CxitTb68Y702DE7L+heHiY/cgaw9WXn5U8742o= X-Received: by 2002:a05:600c:4149:: with SMTP id h9mr33478676wmm.100.1639343935286; Sun, 12 Dec 2021 13:18:55 -0800 (PST) MIME-Version: 1.0 References: <1639341564.906916211@apps.rackspace.com> <1639343520.758213978@apps.rackspace.com> In-Reply-To: <1639343520.758213978@apps.rackspace.com> From: Vint Cerf Date: Sun, 12 Dec 2021 16:18:43 -0500 Message-ID: To: "David P. Reed" Cc: starlink@lists.bufferbloat.net Content-Type: multipart/alternative; boundary="000000000000edc2c005d2f980a2" 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:18:57 -0000 --000000000000edc2c005d2f980a2 Content-Type: text/plain; charset="UTF-8" definitely like this element of added robustness, David. v On Sun, Dec 12, 2021 at 4:12 PM David P. Reed 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" 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 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 --000000000000edc2c005d2f980a2 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
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.

=C2=A0=

But be= fore 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&#= 39;s not an optimal code (it's a hybrid).=C2=A0

=C2=A0=

What&#= 39;s key about this hybrid is that if you think about it, discarding messag= es 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 dec= ode one message.

=C2=A0=

The ke= y idea in TCP is that every bit sent by the source is retained by the sourc= e until it is positively acknowledged to have been received. All of those r= etained 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.

=C2=A0=

This &= quot;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.

=C2=A0=

Ratele= ss 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 a= re reconstructable from any sufficiently long sequence of these combined pa= ckets.

=C2=A0=

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

=C2=A0=

In fac= t, you only need to know (in that original form) the full length of the mes= sage 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 s= ource bits. This is a bit farther from "optimal", because those p= ackets may not have been necessary.

=C2=A0=

Anyway= , I'm not proposing a particular solution here - I'm just saying th= at 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.

=C2=A0=

=C2=A0=

=C2=A0=

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

I am a fan of Fountain codes - however, it only works if y= ou have all the data you are going to send in hand before encoding.=C2=A0
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 r= econstruct "chunks" on receipt.=C2=A0
v

On Sun, Dec 12, 2021 at 3:39 PM David= P. Reed <dpree= d@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 ther= e. There's one exception - RFC 6330, which has a very, very specific us= e of the RaptorQ code specified in it. Qualcomm apparently negotiated a lic= ense 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 narro= w license here) networking.=C2=A0https://datatracker.ietf.org/ipr/2554/

=C2=A0=

Ratele= ss erasure codes of ANY kind appear to be covered by the claims in the earl= y Digital Fountain patents.

=C2=A0=

Now wh= y are rateless erasure codes important for DTN? Well, essentially such code= s have a *unique* property that is pretty surprising:

=C2=A0=

The co= ded 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 a= n infinite sequence of non-identical segments. If a receiver receives a sub= set of distinct segments, totalling N or more bits, the entire N-bit messag= e can be reconstructed.

=C2=A0=

That&#= 39;s what makes the code "rateless" - it works for ANY error rate= , and is optimal for that error rate.

=C2=A0=

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

=C2=A0=

That&#= 39;s remarkable.=C2=A0

=C2=A0=

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 i= s 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 rece= ives a segment of some already completed message, send a single ACK for tha= t message.=C2=A0

=C2=A0=

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

=C2=A0=

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

=C2=A0=

Fair s= haring of a multiplexed deep-space network's resources among many concu= rrent 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, m= y personal view about *patents* on communications protocols is very severe:= since interoperability is the *essence* of communications protocols, the i= dea of patents is antithetical to the utiliity of protocols. Just as mathem= atical algorithms should not be patentable subject matter, neither should c= ommunications protocols (which are just algorithms on a different abstract = machine).

=C2=A0=

Unfort= unately, Luby, et al. have threatened litigation over and over, stymieing a= ttempts to get usage of their remarkable invention, outside a few monopolis= tic or oligopolistic licensees.

=C2=A0=

It loo= ks like, even though the original patents are due to expire soon, lots of e= ffort is being made to insure that all possible derivable techniques are be= ing patented to extend this monopoly.

=C2=A0=

Conseq= uently, 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.

=C2=A0=

Imagin= e if we who built the Internet Protocols had filed patents on all the techn= iques used in the Internet? Would Vint be sitting there counting his royalt= ies, 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).

=C2=A0=

Bill L= uby, his advisors, etc. did a remarkable thing here. And like other invento= rs, 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 tod= ay. It is socially counterproductive, and economically counterproductive, w= hen used in the way it is being used here.

=C2=A0=

But th= at's just my opinion.

=C2=A0=

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

=C2=A0=

=C2=A0=

_______________________________________________
Starlink mailing listStarl= ink@lists.bufferbloat.net
https://lists.buffer= bloat.net/listinfo/starlink

--
Please send any postal/overnight deliveries to:
Vint Cerf
1435 Woodhurst Blvd=C2=A0
McLean, VA 22102
until further notice


--
Please send a= ny postal/overnight deliveries to:
Vint Cerf
1435 Woodh= urst Blvd=C2=A0
McLean, VA 22102
703-448-0965

until further notice



--000000000000edc2c005d2f980a2--