Re: [Starlink] some details on the DTN, bundle protocol, and a capacity question

Re: [Starlink] some details on the DTN, bundle protocol, and a capacity question

[David P. Reed]

[-- Attachment #1: Type: text/plain, Size: 4369 bytes --]


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/ ]( 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.
 
 

[-- Attachment #2: Type: text/html, Size: 8439 bytes --]

Re: [Starlink] some details on the DTN, bundle protocol, and a capacity question

[Vint Cerf]

[-- Attachment #1: Type: text/plain, Size: 5210 bytes --]

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 Cerf
1435 Woodhurst Blvd
McLean, VA 22102
703-448-0965

until further notice

[-- Attachment #2: Type: text/html, Size: 8873 bytes --]

Re: [Starlink] some details on the DTN, bundle protocol, and a capacity question

[David P. Reed]

[-- Attachment #1: Type: text/plain, Size: 7762 bytes --]


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" <vint@google.com> 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 <[ dpreed@deepplum.com ]( mailto: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/ ]( 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 ]( mailto:Starlink@lists.bufferbloat.net )
[ https://lists.bufferbloat.net/listinfo/starlink ]( https://lists.bufferbloat.net/listinfo/starlink )
-- 



Please send any postal/overnight deliveries to:
Vint Cerf
1435 Woodhurst Blvd 
McLean, VA 22102
703-448-0965
until further notice

[-- Attachment #2: Type: text/html, Size: 14641 bytes --]

Re: [Starlink] some details on the DTN, bundle protocol, and a capacity question

[Vint Cerf]

[-- Attachment #1: Type: text/plain, Size: 8283 bytes --]

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.
>
>
>
> 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" <vint@google.com> 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 <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 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

[-- Attachment #2: Type: text/html, Size: 13933 bytes --]

Re: [Starlink] some details on the DTN, bundle protocol, and a capacity question

[Ulrich Speidel]

[-- Attachment #1: Type: text/plain, Size: 8443 bytes --]

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.

On 13/12/2021 9:47 am, Vint Cerf wrote:
>
> 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/
>     <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
>     <https://lists.bufferbloat.net/listinfo/starlink>
>
>
>
> -- 
> Please send any postal/overnight deliveries to:
> Vint Cerf
> 1435 Woodhurst Blvd
> McLean, VA 22102
> 703-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/
****************************************************************



[-- Attachment #2: Type: text/html, Size: 15129 bytes --]

Re: [Starlink] some details on the DTN, bundle protocol, and a capacity question

[Vint Cerf]

[-- Attachment #1: Type: text/plain, Size: 4756 bytes --]

we have the most experience with the ION version of BPv7

v


On Sun, Dec 12, 2021 at 7:06 PM Dave Taht <dave.taht@gmail.com> wrote:

> On Sat, Dec 11, 2021 at 7:15 PM Vint Cerf <vint@google.com> wrote:
> >
> > I haven't pushed to much further until we get some real data from
> running implementations. I also hope we can develop a simulator from which
> we might derive measurements to compare with actual data and modeled
> (queueing theoretic) data.
>
> I am just going to ignore the way this thread went for now. What I was
> mostly asking was what version of dtn was the most promising for an
> embedded (e.g. cerowrt  II) implementation?
>
> https://dtn7.github.io/ looks very promising, especially the rust
> bits. Rust lets me sleep better and we are moving some support for it
> into openwrt's next release.
>
>  https://github.com/morgenroth/ibrdtn  is undermaintained but was
> already ported to openwrt, and is lighter weight. There's another one
> targetted at microcontrollers (  https://upcn.eu/ ), but not the FRAM
> one we used on a previous space-related project... really liked those
> FRAMs....
>
> As for the simulator side, what/where are the requirements? I confess
> to wanting to feed forward the asterank, or celestia, or nasa's new
> https://eyes.nasa.gov/apps/asteroids/#/asteroids into it another 10
> years and plunk 28k nodes into it....
>
>
>
>
>
> > v
> >
> >
> > On Sat, Dec 11, 2021 at 9:58 PM Dave Taht <dave.taht@gmail.com> wrote:
> >>
> >> A good deep dive into DTN with vint cerf is here:
> >>
> https://www.datacenterdynamics.com/en/analysis/vint-cerfs-interplanetary-ambitions/
> >>
> >>  I went looking for existing source code for it, some here:
> >> https://projet.liris.cnrs.fr/riot/dtn_implementations_survey.html
> >>
> >> From the interview...
> >>
> >> Q: "So for store and forward to work, what is the level of storage
> >> each node needs to the speed of the network?"
> >>
> >> VC: That's such a good question. So guess what, I have the same
> >> question. And I said, 'Okay, where do I go to get an answer to that?'
> >> And that is the capacity question: What capacity of this DTN network,
> >> given if I know where the nodes are, and I know what the physics are.
> >> And I know what the data rates could be. I have a traffic matrix. Do I
> >> have a network which is capable of supporting the demand?
> >>
> >> That's the formulation of the question you're asking. So I went to the
> >> best possible source for this question, Leonard Kleinrock at UCLA. He
> >> is the father of the use of queueing theory to analyze store and
> >> forward networks way back in 1961/62, doing his dissertation at MIT on
> >> this topic, not in aid of the interplanetary network, but more general
> >> question on store and forward networking.
> >>
> >> And so he did some fantastic work, he broke the back of the problem
> >> with what was called the independence principle. But he left MIT and
> >> came to UCLA in the '60s, he was on my thesis committee. And he's
> >> still very, very active. He's 87, still blasting on.
> >>
> >> So I sent him a note saying, look, here's the problem. I've got this
> >> collection of notes, and I've got a traffic matrix, and I have this
> >> DTN environment, how do I calculate the capacity of the system so I
> >> know, I'm not gonna overwhelm it.
> >>
> >> And, you know, I figured it would take him a while and maybe find a
> >> graduate student. So *two days later*, I get back two pages of dense
> >> math saying, okay, here's how you formulate this problem. Now, I
> >> didn't get all of the answer. I still don't have all of the answer.
> >> But I know I have one of the best minds in the business looking at the
> >> problem."
> >>
> >> That was back in august of this year, made any progress?
> >>
> >> --
> >> I tried to build a better future, a few times:
> >> https://wayforward.archive.org/?site=https%3A%2F%2Fwww.icei.org
> >>
> >> Dave Täht CEO, TekLibre, LLC
> >> _______________________________________________
> >> 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
> >
> >
> >
>
>
> --
> I tried to build a better future, a few times:
> https://wayforward.archive.org/?site=https%3A%2F%2Fwww.icei.org
>
> Dave Täht CEO, TekLibre, LLC
>


-- 
Please send any postal/overnight deliveries to:
Vint Cerf
1435 Woodhurst Blvd
McLean, VA 22102
703-448-0965

until further notice

[-- Attachment #2: Type: text/html, Size: 7084 bytes --]

Re: [Starlink] some details on the DTN, bundle protocol, and a capacity question

[Dave Taht]

On Sat, Dec 11, 2021 at 7:15 PM Vint Cerf <vint@google.com> wrote:
>
> I haven't pushed to much further until we get some real data from running implementations. I also hope we can develop a simulator from which we might derive measurements to compare with actual data and modeled (queueing theoretic) data.

I am just going to ignore the way this thread went for now. What I was
mostly asking was what version of dtn was the most promising for an
embedded (e.g. cerowrt  II) implementation?

https://dtn7.github.io/ looks very promising, especially the rust
bits. Rust lets me sleep better and we are moving some support for it
into openwrt's next release.

 https://github.com/morgenroth/ibrdtn  is undermaintained but was
already ported to openwrt, and is lighter weight. There's another one
targetted at microcontrollers (  https://upcn.eu/ ), but not the FRAM
one we used on a previous space-related project... really liked those
FRAMs....

As for the simulator side, what/where are the requirements? I confess
to wanting to feed forward the asterank, or celestia, or nasa's new
https://eyes.nasa.gov/apps/asteroids/#/asteroids into it another 10
years and plunk 28k nodes into it....





> v
>
>
> On Sat, Dec 11, 2021 at 9:58 PM Dave Taht <dave.taht@gmail.com> wrote:
>>
>> A good deep dive into DTN with vint cerf is here:
>> https://www.datacenterdynamics.com/en/analysis/vint-cerfs-interplanetary-ambitions/
>>
>>  I went looking for existing source code for it, some here:
>> https://projet.liris.cnrs.fr/riot/dtn_implementations_survey.html
>>
>> From the interview...
>>
>> Q: "So for store and forward to work, what is the level of storage
>> each node needs to the speed of the network?"
>>
>> VC: That's such a good question. So guess what, I have the same
>> question. And I said, 'Okay, where do I go to get an answer to that?'
>> And that is the capacity question: What capacity of this DTN network,
>> given if I know where the nodes are, and I know what the physics are.
>> And I know what the data rates could be. I have a traffic matrix. Do I
>> have a network which is capable of supporting the demand?
>>
>> That's the formulation of the question you're asking. So I went to the
>> best possible source for this question, Leonard Kleinrock at UCLA. He
>> is the father of the use of queueing theory to analyze store and
>> forward networks way back in 1961/62, doing his dissertation at MIT on
>> this topic, not in aid of the interplanetary network, but more general
>> question on store and forward networking.
>>
>> And so he did some fantastic work, he broke the back of the problem
>> with what was called the independence principle. But he left MIT and
>> came to UCLA in the '60s, he was on my thesis committee. And he's
>> still very, very active. He's 87, still blasting on.
>>
>> So I sent him a note saying, look, here's the problem. I've got this
>> collection of notes, and I've got a traffic matrix, and I have this
>> DTN environment, how do I calculate the capacity of the system so I
>> know, I'm not gonna overwhelm it.
>>
>> And, you know, I figured it would take him a while and maybe find a
>> graduate student. So *two days later*, I get back two pages of dense
>> math saying, okay, here's how you formulate this problem. Now, I
>> didn't get all of the answer. I still don't have all of the answer.
>> But I know I have one of the best minds in the business looking at the
>> problem."
>>
>> That was back in august of this year, made any progress?
>>
>> --
>> I tried to build a better future, a few times:
>> https://wayforward.archive.org/?site=https%3A%2F%2Fwww.icei.org
>>
>> Dave Täht CEO, TekLibre, LLC
>> _______________________________________________
>> 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
>
> until further notice
>
>
>


-- 
I tried to build a better future, a few times:
https://wayforward.archive.org/?site=https%3A%2F%2Fwww.icei.org

Dave Täht CEO, TekLibre, LLC

Re: [Starlink] some details on the DTN, bundle protocol, and a capacity question

[Vint Cerf]

[-- Attachment #1: Type: text/plain, Size: 3019 bytes --]

I haven't pushed to much further until we get some real data from running
implementations. I also hope we can develop a simulator from which we might
derive measurements to compare with actual data and modeled (queueing
theoretic) data.

v


On Sat, Dec 11, 2021 at 9:58 PM Dave Taht <dave.taht@gmail.com> wrote:

> A good deep dive into DTN with vint cerf is here:
>
> https://www.datacenterdynamics.com/en/analysis/vint-cerfs-interplanetary-ambitions/
>
>  I went looking for existing source code for it, some here:
> https://projet.liris.cnrs.fr/riot/dtn_implementations_survey.html
>
> From the interview...
>
> Q: "So for store and forward to work, what is the level of storage
> each node needs to the speed of the network?"
>
> VC: That's such a good question. So guess what, I have the same
> question. And I said, 'Okay, where do I go to get an answer to that?'
> And that is the capacity question: What capacity of this DTN network,
> given if I know where the nodes are, and I know what the physics are.
> And I know what the data rates could be. I have a traffic matrix. Do I
> have a network which is capable of supporting the demand?
>
> That's the formulation of the question you're asking. So I went to the
> best possible source for this question, Leonard Kleinrock at UCLA. He
> is the father of the use of queueing theory to analyze store and
> forward networks way back in 1961/62, doing his dissertation at MIT on
> this topic, not in aid of the interplanetary network, but more general
> question on store and forward networking.
>
> And so he did some fantastic work, he broke the back of the problem
> with what was called the independence principle. But he left MIT and
> came to UCLA in the '60s, he was on my thesis committee. And he's
> still very, very active. He's 87, still blasting on.
>
> So I sent him a note saying, look, here's the problem. I've got this
> collection of notes, and I've got a traffic matrix, and I have this
> DTN environment, how do I calculate the capacity of the system so I
> know, I'm not gonna overwhelm it.
>
> And, you know, I figured it would take him a while and maybe find a
> graduate student. So *two days later*, I get back two pages of dense
> math saying, okay, here's how you formulate this problem. Now, I
> didn't get all of the answer. I still don't have all of the answer.
> But I know I have one of the best minds in the business looking at the
> problem."
>
> That was back in august of this year, made any progress?
>
> --
> I tried to build a better future, a few times:
> https://wayforward.archive.org/?site=https%3A%2F%2Fwww.icei.org
>
> Dave Täht CEO, TekLibre, LLC
> _______________________________________________
> 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

until further notice

[-- Attachment #2: Type: text/html, Size: 4248 bytes --]

[Starlink] some details on the DTN, bundle protocol, and a capacity question

[Dave Taht]

A good deep dive into DTN with vint cerf is here:
https://www.datacenterdynamics.com/en/analysis/vint-cerfs-interplanetary-ambitions/

 I went looking for existing source code for it, some here:
https://projet.liris.cnrs.fr/riot/dtn_implementations_survey.html

From the interview...

Q: "So for store and forward to work, what is the level of storage
each node needs to the speed of the network?"

VC: That's such a good question. So guess what, I have the same
question. And I said, 'Okay, where do I go to get an answer to that?'
And that is the capacity question: What capacity of this DTN network,
given if I know where the nodes are, and I know what the physics are.
And I know what the data rates could be. I have a traffic matrix. Do I
have a network which is capable of supporting the demand?

That's the formulation of the question you're asking. So I went to the
best possible source for this question, Leonard Kleinrock at UCLA. He
is the father of the use of queueing theory to analyze store and
forward networks way back in 1961/62, doing his dissertation at MIT on
this topic, not in aid of the interplanetary network, but more general
question on store and forward networking.

And so he did some fantastic work, he broke the back of the problem
with what was called the independence principle. But he left MIT and
came to UCLA in the '60s, he was on my thesis committee. And he's
still very, very active. He's 87, still blasting on.

So I sent him a note saying, look, here's the problem. I've got this
collection of notes, and I've got a traffic matrix, and I have this
DTN environment, how do I calculate the capacity of the system so I
know, I'm not gonna overwhelm it.

And, you know, I figured it would take him a while and maybe find a
graduate student. So *two days later*, I get back two pages of dense
math saying, okay, here's how you formulate this problem. Now, I
didn't get all of the answer. I still don't have all of the answer.
But I know I have one of the best minds in the business looking at the
problem."

That was back in august of this year, made any progress?

-- 
I tried to build a better future, a few times:
https://wayforward.archive.org/?site=https%3A%2F%2Fwww.icei.org

Dave Täht CEO, TekLibre, LLC