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.
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 Cerf1435 Woodhurst BlvdMcLean, VA 22102703-448-0965
until further notice
_______________________________________________ Starlink mailing list Starlink@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@cs.auckland.ac.nz http://www.cs.auckland.ac.nz/~ulrich/ ****************************************************************