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