Re: [dtn-interest] Question

[LOCHIN Emmanuel <[e-mail]>]

Le 25.02.2013 00:57, jzinky a écrit :
> Emmanuel,

Hi John,

> I think that the Tetrys algorithm could be implemented on top of the
> 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.

> 
> 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.

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).

> 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?

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

> 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, [e-mail] 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