Subject: Re: [dtn-interest] some comments on draft-zinky-dtnrg-erasure-coding-extension

From: John Zinky <[email-masked]>
Date: Tue, 4 Dec 2012 17:57:35 -0500

Kevin,

Thanks for reviewing the Erasure Coding drafts. You bring up several issues which I would like to split into four threads, Comments about the Erasure Coding internet-drafts, DTN architecture issues to handle Huge Bundles, Bundle Forwarding issues for groups of bundles, and Typed Data

This first email deals with specific comments, subsequent emails deal with the other issues, hopefully, prompting some discussion. 

1) What about ALC (RFC5775) and LCT (RFC5651)? ALC combines Layered Coding Transport (LCT) building block [RFC5651] FEC building block [RFC5052] multiple rate congestion control building block [RFC2357] and File Delivery over Unidirectional Transport (FLUTE) (RFC6726). While those are sort of IP-specific, can't their frameworks be re-used here?

The intent of the ALC protocol suite is also trying to send large data objects, but many of the details are different. ALC really is designed for IP multicast, with reasonable error-rates. The DTN Erasure Coding has to deal with the case of extreme bundle loss, when contact times are short relative to the transmission time of the object. The way DTN Erasure coding deals with this problem is to basically make every bundle a "repair symbol" and to flood redundant, but not duplicate, repair symbols into the DTN in hopes that a enough get through in time. The key to this case is that no Encoding Bundle carries unique information, all the bundles have to be completely interchangeable. 

Note that Erasure Coding spec can also be configured for the case of a stream of source symbol bundles, with a few block parity bundles added in for redundancy.

I think the EC drafts could use some of the higher level features of the ALC suite, such as using the "File Delivery Table" entry format for metadata (or MIME) instead of the arbitrary file header format described in the Eraser Coding Object internet draft.

2) Why change the name of source symbol to Chunk?
Why change FEC Payload ID to "Encoding Vector"?
Saying the encoding data is the "same length as the chunks": same as they ARE the chunks?

During development, we found this terminology more intuitive for those not immersed in Forward Error Correcting Code literature. We could replace these terms with the FEC terms if that is desirable.

3) Encoding set: why does it have to be a set of LINEAR equations?  What if you have some other type of code?

Other FEC kinds of code are easily handled by changing the code FEC Scheme Type field.
The Erasure Coding Random Binary FEC Scheme draft deals with a specific linear code.

4)I find 3.1 sort of backward.  It says you have:
   data object -> encodings -> bundles
I'd have expected this framework as a CL as thus:
   data object -> bundles -> encoded bundles

The Erasure Coding suite is an end-to-end FEC scheme and not a CLA Link layer FEC. For FEC at the CLA layer, MITRE developed a NORM-CLA based on Negative-ACKnowledgment (NACK) Oriented Reliable Multicast (NORM) (RFC 5740) protocol.

5) Requirements in 3.1: divide into equal sized blocks, and assign UUID
   (ordering is required! -> what does this really imply)

All this says is that a source data object is an order string of bits and 
the data object has a UUID. Note that the UUID is universal and not relative to the source. This is necessary because intermediate recoders need to use their own source EID in order to generate a signature. At decode time, Encoding Bundles from many sources maybe merged based on the UUID.

6) Feedback messages - are these more general?

Feedback messages are out of scope of these internet drafts. This section just tries to enumerate the different types. We are still experimenting with the usefulness of each type, but the usefulness is highly dependent on the end-to-end channel characteristics.

7) "Early research suggests" (sect 6.4) - reference?

Angela Hennessy, Alex Gladd, and Brenton Walker "Nullspace-based Stopping Conditions for Network-Coded Transmissions in DTNs" CHANTS, 2012. 

8) The document needs a layering diagram.

Which diagrams do you recommend based on the limitation of ascii art.
Example diagrams can be found in the EC slideshow. 
https://dist-systems.bbn.com/papers/2011/Zinky/ErasureCodingExtBlockSpec-IRTF-2011-07-25-Rev1-2-2.pdf

Will Ivancic suggests:
Slide 8 for section 3.3.3
Slide 13 for section 4.2
Slide 30 for the Bundle Data Object description.

---

From: "Ivancic, William D. (GRC-RHN0)" <[email-masked]>
Date: Wed, 5 Dec 2012 07:51:25 -0600

> The intent of the ALC protocol suite is also trying to send large data
> objects, but many of the details are different. ALC really is designed for IP
> multicast, with reasonable error-rates.

Agreed.

>The DTN Erasure Coding has to deal
> with the case of extreme bundle loss, when contact times are short relative to
> the transmission time of the object. The way DTN Erasure coding deals with
> this problem is to basically make every bundle a "repair symbol" and to flood
> redundant, but not duplicate, repair symbols into the DTN in hopes that a
> enough get through in time. The key to this case is that no Encoding Bundle
> carries unique information, all the bundles have to be completely
> interchangeable. 

The main concern I have with breaking large bundles into small bundles is
forwarding table bloat.  What happens if I take a 1Gbyte bundle and break it
into a bunch of 64Kbyte Erasure code bundles?   This is of particularly
concern with the current specification that has all these time-stamps that
have to be managed.

If we got rid of creation and expiration times and just had a few QoS queues
with different storage times, this may simplify things greatly.

Everything really is deployment specific.

> Feedback messages are out of scope of these internet drafts. This section just
> tries to enumerate the different types. We are still experimenting with the
> usefulness of each type, but the usefulness is highly dependent on the
> end-to-end channel characteristics.

I would suspect for different deployment environments, one would use
different redundancies rather than feedback.  Feedback characteristics will
also be deployment specific.  Thus, the ability to not assume anything about
feedback is highly desirable.

> Slide 30 for the Bundle Data Object description.

 JAVE  is a nice ASCII Art Utility.
www.jave.de/
Note, I have no financial stake here.  I just find it useful.  In theory, I
cannot endorse anything (being a US Govt employee) so consider this just a
statement that I have used the  program and it has worked well for me.  :-)

- Will

---

From: John Zinky <[email-masked]>
Date: Thu, 6 Dec 2012 15:22:24 -0500

On Nov 9, 2012, at 12:33 PM, "Fall, Kevin" <[email-masked]> wrote:
> I have concerns about the idea of typed data transfer (requiring IANA)

Erasure Coding adds one SDNV field to store a format type number in the extension block. A field is necessary to distinguish a "File" Data Object, from a "Big Bundle" Data Object

RFC 5050 does not have a next protocol field like IP.
 
Alternative solutions to a Data Object format type field would be:
1) Append a Object format type in the Destination EID. This would take a least one byte, which is the same overhead as an SDNV. Hairing up the EID has no advantage.

2) Gleam format from the Data Object itself. But the Erasure Coding does not require the whole Data Object be delivered, e.g. a layer video stream encoding or situation awareness updates. The Data object could have gaps, there is no place in the data object that is guaranteed to be delivered, hence no place to actually define the format.

3) Add a payload header to every payload, hence every bundle. But if we ignore layering, then this payload header becomes an extension block.

So in the case of the Data Object being spread over multiple bundles, the easiest mechanism is to add a "Next Encapsulated Protocol" field. Having this field in the EC header, means that it does not have overhead for small (non grouped) bundles.

---

From: John Zinky <[email-masked]>
Date: Tue, 18 Dec 2012 11:11:40 -0500

Vint,
There are two questions that need to be addressed concerning a next protocol field in DTN.

1) Is a "next protocol" or "Data Object format" field needed in the bundle protocol suite?
Erasure Coding needs such a field

2) Where should the next protocol field be located?
The right place seems to be an extension block, but which extension block?

At the heart of the "Erasure Coding as an example End-to-End service discussion" is a more fundamental question about the architecture for a DTN protocol suite. 

The Erasure Coding has its own private extension block, some would call this a stove pipe. But looking in detail, the EC extension block contains fields that are needed in other contexts, such as
 1) Handling Specs: which addresses Forwarding Policies as the ECOS draft
http://tools.ietf.org/html/draft-irtf-dtnrg-ecos-03

 2) Group ID: which is similar to the Content ID in the BPQ draft
http://tools.ietf.org/html/draft-farrell-dtnrg-bpq-00

It is easy to imagine an end-to-end application that needs all three services, Erasure Coding, Forwarding policies, Content Query.

Imagine a large content object that is Erasure Encoded and  pieces disseminated throughout the DTN network. A Query based on the Content Object ID is sent out into the network and Erasure coded bundles are sent back to the requester. But the default First-Come-First-Serve Forwarding Policy will not work because duplicate encodings (the one that was sent first) will be returned first which are guaranteed to be redundant. 

Currently all three services have their own stovepipe internet draft.
If we start to design a non-layered DTN protocol suite, how do we partition functionality to the extension blocks?  And how do the services, such as Erasure Coding, Forwarding policies, Content Query use these extension blocks and not step on each other?

On Dec 6, 2012, at 7:50 PM, Vint Cerf <[email-masked]> wrote:

> is there some reason that extension header would not work?
> 
> v
> 
> 
> On Thu, Dec 6, 2012 at 3:22 PM, John Zinky <[email-masked]> wrote:
> 
> _______________________________________________
> dtn-interest mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/dtn-interest
>