<html><head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<p>There's this, too:</p>
<p>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)</p>
<p>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. <br>
</p>
<p>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.<br>
</p>
<p>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.<br>
</p>
<p>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.<br>
</p>
<div class="moz-cite-prefix">On 13/12/2021 9:47 am, Vint Cerf wrote:<br>
</div>
<blockquote type="cite" cite="mid:CAHxHggcJh0HD16ypz3FoGx8Jm5rw-_+3cO8kCpH5sftrrNZtMg@mail.gmail.com">
<span style="color: #ff0000;">
</span><br>
<div dir="ltr">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.
<div>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.</div>
<div><br>
</div>
<div>Of course, one can "chunk" the data, fountain-code it, and
reconstruct "chunks" on receipt. </div>
<div><br>
</div>
<div>v</div>
<div><br>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Sun, Dec 12, 2021 at 3:39
PM David P. Reed <<a href="mailto:dpreed@deepplum.com" moz-do-not-send="true" class="moz-txt-link-freetext">dpreed@deepplum.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><font size="2" face="arial">
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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. <a href="https://datatracker.ietf.org/ipr/2554/" target="_blank" moz-do-not-send="true">https://datatracker.ietf.org/ipr/2554/</a></p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">Rateless
erasure codes of ANY kind appear to be covered by the
claims in the early Digital Fountain patents.</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">Now
why are rateless erasure codes important for DTN? Well,
essentially such codes have a *unique* property that is
pretty surprising:</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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.</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">That's
what makes the code "rateless" - it works for ANY error
rate, and is optimal for that error rate.</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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.</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">That's
remarkable. </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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?</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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. </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">Now
this is great for talking to a spacecraft that has a very
low speed and noisy reverse channel.</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">Any
number of messages can be concurrently sent from any
number of sources (the requirement is that each message
has a global unique ID).</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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).</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">-----------------------------------</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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).</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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.</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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.</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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.</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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).</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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.</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">But
that's just my opinion.</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt">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.</p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
<p style="margin:0px;padding:0px;font-family:arial;font-size:10pt"> </p>
</font>_______________________________________________<br>
Starlink mailing list<br>
<a href="mailto:Starlink@lists.bufferbloat.net" target="_blank" moz-do-not-send="true" class="moz-txt-link-freetext">Starlink@lists.bufferbloat.net</a><br>
<a href="https://lists.bufferbloat.net/listinfo/starlink" rel="noreferrer" target="_blank" moz-do-not-send="true">https://lists.bufferbloat.net/listinfo/starlink</a><br>
</blockquote>
</div>
<br clear="all">
<div><br>
</div>
-- <br>
<div dir="ltr" class="gmail_signature">
<div dir="ltr">
<div>Please send any postal/overnight deliveries to:</div>
<div>Vint Cerf</div>
<div>1435 Woodhurst Blvd </div>
<div>McLean, VA 22102</div>
<div>703-448-0965</div>
<div><br>
</div>
<div>until further notice</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
</div>
</div>
<br>
<fieldset class="moz-mime-attachment-header"></fieldset>
<pre class="moz-quote-pre" wrap="">_______________________________________________
Starlink mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Starlink@lists.bufferbloat.net">Starlink@lists.bufferbloat.net</a>
<a class="moz-txt-link-freetext" href="https://lists.bufferbloat.net/listinfo/starlink">https://lists.bufferbloat.net/listinfo/starlink</a>
</pre>
</blockquote>
<pre class="moz-signature" cols="72">--
****************************************************************
Dr. Ulrich Speidel
School of Computer Science
Room 303S.594 (City Campus)
Ph: (+64-9)-373-7599 ext. 85282
The University of Auckland
<a class="moz-txt-link-abbreviated" href="mailto:ulrich@cs.auckland.ac.nz">ulrich@cs.auckland.ac.nz</a>
<a class="moz-txt-link-freetext" href="http://www.cs.auckland.ac.nz/~ulrich/">http://www.cs.auckland.ac.nz/~ulrich/</a>
****************************************************************
</pre>
</body>
</html>