Subject: Re: [dtn-interest] Question

From: William Immerman <[email-masked]>
Date: Fri, 1 Feb 2013 06:44:54 -0500

Sitaraman--

Wouldn't "NACK sooner" require a response from the recipient of the protocol unit (bundle), and therefore take RTT?

I understand your breakdown of the distinct losses that are addressed at the link level vs the protocol level. We've proposed to employ the protocol to repair some longer transient losses in some existing comms links that already use some form of FEC/reliable multicast but are unreliable due to errors that don't fit the model that are being corrected at that level. I've had some frustration, too, trying to explain to some of the existing users why they have error correction but are still failing due to uncorrected errors. My best understanding of the solution so far is that in the DTN setting you need to be careful of what properties you assign to the convergence layer and which you get at the bundle level. If you're not getting adequate feedback between the two, that may be fixable, but if the system can't give feedback to the sender it doesn't yet have because of the limitations of information propagation due to the speed of light, that's (currently) a fundamental limitation of physics that's inherent in relativity theory.

Scott: I'd appreciate feedback if I'm wrong...

Bill

On Jan 31, 2013, at 11:42 PM, [email-masked] wrote:

> Therefore, i was wondering if we can consider adding support in the
> protocol a low bandwidth liveness streaming (which could carry data too,
> such as a form of green data in LTP), that can potentially NACK sooner
> than that required by RTT based acks.

---

From: William Immerman <[email-masked]>
Date: Fri, 1 Feb 2013 06:57:11 -0500

Sitaraman--

I guess I omitted one point: "NACK" sooner would require response from recipient if there are no "intermediates". In the deep space case, there may not be suitable intermediates, but I think you're correct that IF there are points in the topology close to the sender that are likely to detect losses much sooner than the recipient, and they aren't employed, that would be a fixable problem. I think, though, that's a problem of network design, not a protocol problem. If there are no intermediate points with this characteristic (e.g., that significant loss would occur between the sender and themselves), then I believe you're back to the physics problem...

Bill

On Feb 1, 2013, at 6:44 AM, William Immerman wrote:

> I understand your breakdown of the distinct losses that are addressed at the link level vs the protocol level. We've proposed to employ the protocol to repair some longer transient losses in some existing comms links that already use some form of FEC/reliable multicast but are unreliable due to errors that don't fit the model that are being corrected at that level. I've had some frustration, too, trying to explain to some of the existing users why they have error correction but are still failing due to uncorrected errors. My best understanding of the solution so far is that in the DTN setting you need to be careful of what properties you assign to the convergence layer and which you get at the bundle level. If you're not getting adequate feedback between the two, that may be fixable, but if the system can't give feedback to the sender it doesn't yet have because of the limitations of information propagation due to the speed of light, that's (currently) a fundamental limitatio
> n of physics that's inherent in relativity theory.
> 
> _______________________________________________
> dtn-interest mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/dtn-interest

---

From: [email-masked]
Date: Fri, 1 Feb 2013 17:30:13 +0530 (IST)

Thanks William for your patience...Could you please point me to the doc
that will help me understand convergence layer and bundle layer...after
reading that i will get back...thanks
Sitaraman
> Sitaraman--
>
> Wouldn't "NACK sooner" require a response from the recipient of the
> protocol unit (bundle), and therefore take RTT?
>
> I understand your breakdown of the distinct losses that are addressed at
> the link level vs the protocol level. We've proposed to employ the
> protocol to repair some longer transient losses in some existing comms
> links that already use some form of FEC/reliable multicast but are
> unreliable due to errors that don't fit the model that are being corrected
> at that level. I've had some frustration, too, trying to explain to some
> of the existing users why they have error correction but are still failing
> due to uncorrected errors. My best understanding of the solution so far is
> that in the DTN setting you need to be careful of what properties you
> assign to the convergence layer and which you get at the bundle level. If
> you're not getting adequate feedback between the two, that may be fixable,
> but if the system can't give feedback to the sender it doesn't yet have
> because of the limitations of information propagation due to the speed of
> light, that's (currently) a fundamental limitation of physics that's
> inherent in relativity theory.
>
> --
> This message has been scanned for viruses and
> dangerous content by MailScanner, and is
> believed to be clean.
>
>

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.

---

From: William Immerman <[email-masked]>
Date: Fri, 1 Feb 2013 07:22:41 -0500

I think start with RFCs 4838 and 5050.

Bill

---

From: Emmanuel Lochin <[email-masked]>
Date: Fri, 01 Feb 2013 15:14:58 +0100

On 01/02/2013 05:42, [email-masked] wrote:
> a)Erasure Coding addresses the fundamental distance and delay problem for
> disruptions (not loss of coverage but unfortunate events either due to
> interference or due to physical blockage). This it does by redudancy in
> the packets (essentially a form of a more continuous and granular
> retransmission). However due to the continuous retransmission nature,
> while it works well for low intensity  losses even if it is spread over a
> long time, it becomes inefficient (and costly perhaps) to extend this for
> relatively medium-time-length spikes in losses.
Hi Sitaraman

Agree for FEC block codes (concerning the spike in losses) but not for 
on-the-fly coding schemes (Tetrys or Muriel Medard's CodedTCP schemes).
As there is no block to size with these coding schemes because a burst 
of losses can always be recovered later.

Regards

EL

-- 
Emmanuel Lochin
Professeur ISAE - OSSI
Institut Supérieur de l'Aéronautique et de l'Espace (ISAE)
Issu du rapprochement SUPAERO et ENSICA
10 avenue Edouard Belin - BP 54032 - 31055 Toulouse cedex 4
Tel : 05 61 33 91 85 - Fax : 05 61 33 91 88
Web : http://personnel.isae.fr/emmanuel-lochin/
---
"This email and any attachments are confidential. They may contain legally privileged information or copyright material. You should not read, copy, use or disclose them without authorisation. If you are not an intended recipient, please contact us at once by return email and then delete both messages. We do not accept liability in connection with computer virus, data corruption, delay, interruption, unauthorised access or unauthorised amendment. This notice should not be removed"

---

From: [email-masked]
Date: Fri, 1 Feb 2013 20:01:17 +0530 (IST)

Hi Emmanuel,
 I see your point, but need to read a) along with b) and c) (which is why
i mentioned these are complementary limitations...)
  I presume that it would be inefficient to have the default block size
for the worst possible case. Now, for a severe loss, currently you would
need round trip time or close (to get the bad news) to refactor the
dynamic adjustment of the block size at the sender isnt it?
Sitaraman
> "This email and any attachments are confidential. They may contain legally
> privileged information or copyright material. You should not read, copy,
> use or disclose them without authorisation. If you are not an intended
> recipient, please contact us at once by return email and then delete both
> messages. We do not accept liability in connection with computer virus,
> data corruption, delay, interruption, unauthorised access or unauthorised
> amendment. This notice should not be removed"
>

---

From: "Burleigh, Scott C (313B)" <[email-masked]>
Date: Fri, 1 Feb 2013 16:29:28 +0000

Bill, I think you may have narrowed in on our disconnect here: we can do forward error correction and/or retransmission at the bundle protocol layer, and we can also do forward error correction and/or retransmission at the "convergence" layer of protocols underlying the bundle protocol -- and these mechanisms can be complementary, particularly when the end-to-end path comprises multiple "hops" of transmission between neighboring BP nodes, implemented by multiple concatenated instances of possibly heterogeneous convergence-layer protocols.

Sitaraman, "...an immediate transmission of that bad news back to the sender so that the sender can retransmit the entire chunk" is possible if and only if there is some communicating entity that is in a position to (a) detect the "severe loss" event and (b) transmit the responsive NAK(s) to trigger retransmission of the lost chunk(s).  That communicating entity may be either the final destination node or some other entity along the end-to-end path, such as an intermediate forwarding node.  If you've got such supplementary entities along the path then you can indeed initiate retransmission of lost data in single-hop RTT that is much less than an end-to-end RTT; this is exactly the advantage of using "reliable" convergence-layer protocols (such as LTP) between neighboring BP nodes.  You characterize the use of such supplementary entities as a "workaround", so I suspect this isn't the answer you're looking for.  But absent an entity that can detect a loss and respond to it by transmitting a NAK, where would the NAK come from?

Maybe this is the sort of thing you're thinking of:  suppose we have some sort of continuous beacon signal emanating from the point in the network where the severe loss event occurs.  If the loss event not only causes DTN traffic chunks to be lost but also interrupts the beacon signal, then a node that has transmitted bundles that are routed through that point could detect that beacon signal lapse as an indication of data loss and immediately retransmit whatever chunks it judges would have reached that point at the moment when the inferred data loss occurred.  But that leaves open a few questions: for starters, where would you place those beacon signal sources, how many of them would you have (to be sure there's one at every point in the network where a severe data loss can occur), how would you ensure that beacon signal interruptions correspond to the loss of data flowing in the opposite direction, and how would you accurately map the moment of signal interruption to a particular data chunk for retransmission?  And you're still never going to retransmit earlier than one RTT (the RTT between the bundle source and the beacon signal source) following original transmission, and again your beacon signal sources are supplementary communicating entities, a workaround.

That is, I'm pretty sure there isn't really a solution to "the distance problem" short of revising some physical laws on the nature of distance.

Scott 

-----Original Message-----
From: William Immerman [mailto:[email-masked]] 
Sent: Friday, February 01, 2013 3:45 AM
To: [email-masked]
Cc: Burleigh, Scott C (313B); [email-masked]
Subject: Re: [dtn-interest] Question

Sitaraman--

Bill

On Jan 31, 2013, at 11:42 PM, [email-masked] wrote:

> protocol a low bandwidth liveness streaming (which could carry data 
> too, such as a form of green data in LTP), that can potentially NACK 
> sooner than that required by RTT based acks.

---

From: [email-masked]
Date: Sat, 2 Feb 2013 09:34:39 +0530 (IST)

Hi Scott,
 Thanks for this discussion...You are correct,  what you point to below as
what i am thinking is what i had in mind...the beacon...we indeed seem to
be converging.....Please see below ....do you really need a beacon source
at the point of disturbance?

 Thanks so much Keith...Let us consider the Mars favorable ratio case. In
this scenario, if during the coverage period NASA sends a continous stream
in both direction (with possible time stamped) "channel liveness"
lightweight (meaning consuming less bandwidth) packets, or bundles of
them) by reading the timestamped series of liveness packets the sender may
able to guess a packet loss much before a round trip  time...say it occurs
in the first minute after sending...then it could save some time (RTT-1+)
in making a decision to resend.
Extending further by reading the streams and timestamps it can get "bad
weather reports much farther away and delay sending packets...
Sitaraman

> Bill, I think you may have narrowed in on our disconnect here: we can do
> forward error correction and/or retransmission at the bundle protocol
> layer, and we can also do forward error correction and/or retransmission
> at the "convergence" layer of protocols underlying the bundle protocol --
> and these mechanisms can be complementary, particularly when the
> end-to-end path comprises multiple "hops" of transmission between
> neighboring BP nodes, implemented by multiple concatenated instances of
> possibly heterogeneous convergence-layer protocols.
>
> Sitaraman, "...an immediate transmission of that bad news back to the
> sender so that the sender can retransmit the entire chunk" is possible if
> and only if there is some communicating entity that is in a position to
> (a) detect the "severe loss" event and (b) transmit the responsive NAK(s)
> to trigger retransmission of the lost chunk(s).  That communicating entity
> may be either the final destination node or some other entity along the
> end-to-end path, such as an intermediate forwarding node.  If you've got
> such supplementary entities along the path then you can indeed initiate
> retransmission of lost data in single-hop RTT that is much less than an
> end-to-end RTT; this is exactly the advantage of using "reliable"
> convergence-layer protocols (such as LTP) between neighboring BP nodes.
> You characterize the use of such supplementary entities as a "workaround",
> so I suspect this isn't the answer you're looking for.  But absent an
> entity that can detect a loss and respond to it by transmitting a NAK,
> where would the NAK come from?
>
> Maybe this is the sort of thing you're thinking of:  suppose we have some
> sort of continuous beacon signal emanating from the point in the network
> where the severe loss event occurs.  If the loss event not only causes DTN
> traffic chunks to be lost but also interrupts the beacon signal, then a
> node that has transmitted bundles that are routed through that point could
> detect that beacon signal lapse as an indication of data loss and
> immediately retransmit whatever chunks it judges would have reached that
> point at the moment when the inferred data loss occurred.  But that leaves
> open a few questions: for starters, where would you place those beacon
> signal sources, how many of them would you have (to be sure there's one at
> every point in the network where a severe data loss can occur), how would
> you ensure that beacon signal interruptions correspond to the loss of data
> flowing in the opposite direction, and how would you accurately map the
> moment of signal interruption to a particular data chunk for
> retransmission?  And you're still never going to retransmit earlier than
> one RTT (the RTT between the bundle source and the beacon signal source)
> following original transmission, and again your beacon signal sources are
> supplementary communicating entities, a workaround.
>
> That is, I'm pretty sure there isn't really a solution to "the distance
> problem" short of revising some physical laws on the nature of distance.
>
> Scott
>

---

From: Emmanuel Lochin <[email-masked]>
Date: Mon, 04 Feb 2013 15:45:57 +0100

Hi Sitaraman

> for the worst possible case.

Fully agree

> Now, for a severe loss, currently you would

Yes, if you talk about Tetrys, this is what it does following a feedback 
message.
The feedback messages allow to reduce the encoding dynamic window 
because it contains the sequence number of the received packets (we are 
systematic).
However, these feedback messages are not mandatory as their lost do not 
impact on the sending, they only reduce the encoding complexity.

Speaking about FEC, it could be possible to build an adaptive FEC 
scheme, however this adjustement can be only done between two blocks.
As a result, these two blocks will have different code rate but it is 
not possible to adapt the number of redundancy packets sent for the 
current block.

Emmanuel

---

From: [email-masked]
Date: Mon, 4 Feb 2013 20:57:13 +0530 (IST)

Hi Emmanuel,
 Thanks for those clarifications. Yes, adaptive feedback control sounds to
me like a good idea to take care of sustained "bad weather" scenarios in
the path.
 It would be good to complement this with a scheme that would handle
bursts of disruptions such as a large physical block, without needing  a
complete RTT for it.
Sitaraman
>>>> while it works well for low intensity  losses even if it is spread
>>>> over
>>>> a

---

From: jzinky <[email-masked]>
Date: Sun, 24 Feb 2013 18:57:35 -0500

Emmanuel,
I think that the Tetrys algorithm could be implemented on top of the Erasure Coding Extension internet draft. 
  http://tools.ietf.org/id/draft-irtf-dtnrg-zinky-erasure-coding-extension-00.txt

I would be interested to see what parameters Tetrys needs to add to the Bundle header for sending source bundles and repair bundles. Also, the headers for the Selective acknowledgement (SACK) bundles.

If  Tetrys can use the GF(2) field, then the Random Binary FEC scheme can be used to encode the coefficients using the Windowed Binary Array: FEC Scheme Type = 3.

If Tetrys uses a higher field you would need to define a new FEC Scheme Type and Parameters. It looks like these parameters would include the pseudo-random number generator seed and the range of coefficient indexes. 

It is interesting that Tetyrs needs SACK feedback messages. These have not been defined in the Erasure Coding Extension. Did you use administrative bundles and store the SACK parameters in an extension block or did you just create a new new bundle type and store the parameters in the payload?

Do you see any fields that are missing in the Erasure Coding Extension.
For example, how to you signal that the stream is terminated?  
and how do you pad the last bundle?

On Jan 31, 2013, at 5:55 AM, Emmanuel Lochin wrote:

> Hi Sitaraman
> 
> Thanks for your interest. We are currently working on these aspects for deep space communication on top of a DTN architecture with CNES (the French space agency).
> In particular, we seek to integrate erasure coding inside the DTN architecture.
> Note that there is also an IETF draft on this subject : http://www.ietf.org/id/draft-zinky-dtnrg-erasure-coding-objects-00.txt
> 
> Emmanuel
> 
> On 31/01/2013 02:34, [email-masked] wrote:
>> I should rather say "in addition to" instead of "as opposed to" in the below
>>> Hi Emmanuel,
>>>  This looks great to me, thanks for this pointer. Only one scenario comes
>>> to mind, if it so happens that the expected bundle loss rate, even if for
>>> brief periods, is underestimated. Such scenarios could perhaps be
>>> relevant in space as intense disturbances for brief period is more likely
>>> than a steady noise, and with Tetrys, it would be inefficient to have the
>>> expected bundle loss rate set at its peak.
>>>  I am tending to think while Tetrys could be a default scheme running in
>>> the DTN, DSN, there is needed a scheme that can put out fires
>>> occasionally?
>>> Sitaraman
>>>> Hi Sitaraman
>>>> 
>>>>> Thanks much for this pointer, it will help me learn this aspect.
>>>>> In general a question remains that i have, for the group as  whole.
>>>>> A lot seems to have already been done  and literature and code
>>>>> available
>>>>> in FEC and Erasure Codes as has been made available from  the
>>>>> discussion
>>>>> on this group  Do these complement or can they replace loss (chunks
>>>>> of
>>>>> data compeletely lost so that there is not anything to decode from)
>>>>> handling mechansims?
>>>> Concerning this point, you'll find a study that uses such scheme to
>>>> rebuild lost chunks in "Robust streaming in delay tolerant networks":
>>>> see http://oatao.univ-toulouse.fr/4111/
>>>> The erasure coding scheme is a specific elastic-window encoding scheme
>>>> named Tetrys: see http://websites.isae.fr/tetrys/
>>>> 
>>>> Emmanuel

---

From: LOCHIN Emmanuel <[email-masked]>
Date: Wed, 27 Feb 2013 15:07:38 +0100

> Emmanuel,

Hi John,

> Erasure Coding Extension internet draft.

Thank you for your interest, we just finished to read your drafts in 
detail (Jerome Lacan, Jonathan Detchart and myself).
Please see our answers inline.

> I would be interested to see what parameters Tetrys needs to add to
> the Bundle header for sending source bundles and repair bundles. 
> Also,
> the headers for the Selective acknowledgement (SACK) bundles.

Indeed, the basic Tetrys example provided here enables a systematic 
encoding: http://websites.isae.fr/tetrys/
However, we can use it as a non-systematic scheme and in that case, we 
do not need to distinguish source from repair bundles. Of course, if a 
general mechanism applied to all erasure coding schemes is defined in 
this architecture, Tetrys would take use it. (See further below 
concerning SACK)

> If  Tetrys can use the GF(2) field, then the Random Binary FEC scheme
> can be used to encode the coefficients using the Windowed Binary
> Array: FEC Scheme Type = 3.

This seems to be a good idea, we fully agree.

> If Tetrys uses a higher field you would need to define a new FEC
> Scheme Type and Parameters. It looks like these parameters would
> include the pseudo-random number generator seed and the range of
> coefficient indexes.

As you suggest, including the pseudo-random number generator seed and 
the range could be a possibility. However, thiskind of signaling is not 
well adapted to re-encoding at intermediate recoders.

Another solution could be to include the finite field; the range and an 
octet array possibly as follows:

+--------------+--------+-------------------------------------------+
| Field        |  Type  | Description                               |
+--------------+--------+-------------------------------------------+
| Finite Field |  SDNV  | Specifies the finite field of the form    |
| Degree (m)   |        | GF(2^m), where m is the Finite Field      |
|              |        | Degree.                                   |
|              |        |                                           |
| Lowest Index | SDNV   | The lowest index value with a coefficient |
|              |        | of one. Bit index for zero of the Packed  |
|              |        | Octet Array will be offset by this index. |
|              |        |                                           |
| Length Octet | SDNV   | octet_array_length = ceiling(             |
| Array        |        | (highest_index - lowest_index) * m / 8 )  |
|              |        |                                           |
| Packed       | Octets | Encoding Vector packed into an octet      |
| Coefficients |        | array, with each coefficient is           |
| Array        |        | represented as a binary number of length  |
|              |        | m.                                        |
+--------------+--------+-------------------------------------------+

> It is interesting that Tetyrs needs SACK feedback messages. These
> have not been defined in the Erasure Coding Extension. Did you use
> administrative bundles and store the SACK parameters in an extension
> block or did you just create a new new bundle type and store the
> parameters in the payload?

To the best of our understanding, we feel that the Data Object Status 
feedback messages (defined section 6.3 from DTN-EC-Arch) could be used 
to carry a SACK vector or simply the lowest index of the first missing 
chunk (to enable a simple ACK scheme).

> and how do you pad the last bundle?

Just to be on the same thread, a stream can be either sized or not.
In the various IETF documents of the DTNRG group, it seems that the 
size of the whole stream is always known by the encoder at the beginning 
of the transmission. In this case, the stream can be managed as a usual 
Data Object.
If the size is not known, then several Data Objects can be created and 
Tetrys can be applied inside each of them.

FYI, Jonathan Detchart is going to present a Tetrys demo at the next 
IETF meeting in Orlando the 11th of March, 13:00 in the NWCRG (Network 
Coding) session. If you expect to be present during the week, Jonathan 
will be happy to demonstrate our prototype.

Emmanuel

>> Thanks for your interest. We are currently working on these aspects 
>> for deep space communication on top of a DTN architecture with CNES 
>> (the French space agency).
>> Note that there is also an IETF draft on this subject : 
>> http://www.ietf.org/id/draft-zinky-dtnrg-erasure-coding-objects-00.txt
>>
>> Emmanuel
>>