Subject: Re: [nwcrg] Review of draft-heide-nwcrg-rlnc-00

From: "Kerim Fouli" <[email-masked]>
Date: Mon, 11 Feb 2019 16:32:55 -0500

Dear all,

Thanks to Janus and Vincent for the comments and responses below. We have decided to follow Vincent’s recommendation at Montreal and separate the draft into an informational draft (RLNC Background) and the symbol representation itself. I have just submitted the RLNC Background part as an informational – see link below. This ID corresponds to the RLNC tutorial Marie-José has been recommending for a while. 

Link to new informational on RLNC background:

https://datatracker.ietf.org/doc/draft-heide-nwcrg-rlnc-background

Section 2 is meant to be an open section listing practical considerations related to the standardization and deployment of RLNC. It currently has a sub-section with technical arguments on symbol representation as a valuable standardization target – a follow-up to our discussion in Montreal. Other contributions are welcome!

I plan on presenting a few slides on the updates to the RLNC ID in Prague (most likely online), if there is time and interest. We will be re-submitting the symbol representation part as a second version of the RLNC ID soon. In the meantime, we would appreciate comments and recommendations. 

Best,

Kerim

-- 
Kerim Fouli 

 <tel:781-414-0541> 781.414.0541

 <http://www.codeontechnologies.com/> 

From: nwcrg <[email-masked]> On Behalf Of Janus Heide
Sent: Thursday, August 2, 2018 2:57 AM
To: Vincent Roca <[email-masked]>
Cc: [email-masked]
Subject: Re: [nwcrg] Review of draft-heide-nwcrg-rlnc-00

Vincent,

Once again thanks for your extensive comments. 

>From their nature, and as stated in the Montreal meeting, it seems that your understanding of the objective of the document is different from the intention. Rereading it now it is not entirely surprising to me, since the first couple of pages provide too much information that should not be a part  of this document, and it should instead have a short and concise intro and mission statement - You also made a remark along these lines in London.

Below some input to your questions.

1 The behaviour in a upper layer protocol could be as you describe, the intention is not to mandate such an approach but let that be up to the protocol to determine. The protocol could do something else as long as it provides all the necessary header parameter for a symbol representation and the data. 

2 This is up to the higher layer protocol.

3 If you want to finish a generation, you can simply start a new one, the main limitation is that you have to provide full symbols and that the symbol size of a generation is fixed once it is started, hence you potentially have to zero pad the last symbol that you insert into a generation. Note that the generation id is not carried with the symbol representation, so it is up to a higher layer protocol to ensure that received symbols are put into the correct generation decoder. 

4 That is an interesting question, but I am not sure that this is relevant in this context. The main argument for supporting this type of code atm. Is that it is the most commonly used (afaik) approach. 
To provide a bit of input to your point anyway, some benefits are that you have inbuilt places (when a new generation is started) in your symbol stream where a joining decoder more quickly synchronize, similarly for a node that comes out of a deep fade. It might also be easier to schedule repair symbols that can efficiently be decoded, sure with a sliding window code you just combine a lot of old data, but if you do that the receivers need to work hard on the decoding. I am not sure that anyone have a good general answer to your question at this time, but to me a sliding window approach seems natural for streaming type data transfer and a block code more natural for a object type data transfer.

5 The scope of the document was aimed at only being a symbol presentation format, so both the code and protocol that uses the code and this header format would be specified somewhere else. Not sure if this answers your question?

5b For this document we tried to make as few assumptions about what the protocol need to communicate, so these are just examples not mandatory information.

6 I would not say that it was an objective of this work to support inter session coding, maybe it just should not have been mentioned.

7 So here essentially there is a finite number of seeds which is the lower bound of the number of different coding vectors, since this representation allow multiple symbols to be generated from a single seed - by generating a series of vectors without setting the seed. So I think this is why this sentence is a bit ambiguous.

8.  Multiple symbols in a single atom packet can share a header, which is what is done in this document, I dont see how that can cause a problem, since a packet is either completely received or not received.

So in my opinion this is not a very ambitious document, it tries to address a small but relevant problem which every protocol that uses Network Coding will have to address.

Best Janus

On 07/15/18 22:06, Vincent Roca wrote:

Hi Janus et al. 

Here is a review of draft-heide-nwcrg-rlnc-00.

My goal is to better understand your point and find ways to move forward,

in a constructive manner, even if there are many points.

Section 1.2. Evil is always in the details. You say:

  "In generation-based RLNC, input data as received from an upper layer

   in the protocol stack is segmented into equal-sized blocks, denoted

   as generations, and each generation is further segmented into equal-

   sized data symbols for encoding, with paddings added when necessary. »

This immediately raises many questions:

1- From this sentence, I understand that: (1) you append input data until you reach 

  the desired size, i.e., the desired number of bytes. Then as you know how

  many symbols you want, you compute the required symbol size to have this

  number. I think this is what you mean, but your text is pretty ambiguous.

Hence a few additional questions:

2- how do you determine the desired size of blocks? It typically depends on the

  input flow features.

3- what about situations where the input flow is of VBR? Do you wait to have received

   enough data before declaring the block as full? Do you pad? How do you manage

   real-time requirements?

More fundamentally:

4- I understand that Generation-Based RLNC, midway between traditional block

  codes and sliding window codes, is feasible. If I’m not wrong, this has long been

  the way Kodo was working.

  I understand it avoids the initial coding delay of traditional block codes, which is fine.

  But what’s the benefit of such codes WRT sliding window codes? The last source

  symbol of a generation is less protected than those received before since it is

  encoded in a fewer number of repairs. Where’s the gain? That’s something I don’t

  understand.

Later in section 3.1 it is said:

  "Such coding parameters

   can include one or more of field size, code specifications, index of

   the current generation being encoded at the sender, generation size,

   code rate, and desired feedback frequency or probability. »

5- Coding or protocol? Feedback parameters refer to protocol aspects, i.e.,

  the whole machinery that makes all the stuff provide the desired service.

  We are not talking about a code or FEC scheme specification. I don’t understand

  what's the intended I-D scope. Or do you mention it to highlight that the FEC scheme

  will be a little bit different when used in a protocol that includes feedback?

5b- BTW, I don’t think the code rate is needed by the receiver, at least from a coding

  perspective. It's different from fixed-rate traditional block codes. Same comment for

  Section 1.3.

Regarding section 1.4, you’re saying:

   "Recoding 

   is typically performed at intermediate network nodes, in either an

   intra-session or an inter-session fashion.  Intra-session coding

   refers to coding between packets of the same flow or session, while

   inter-session coding refers to combination of packets from different

   flows or sessions in a network."

6- Do you really want to consider inter-session coding?

  That’s ambitious, since it requires symbols of each session to be uniquely

  identified. How do you intend to do that? Do you assume a certain form

  of synchronisation between the sessions? It’s feasible if they come from

  the same host, otherwise it may quick become complex. And this identification

  needs to be compact as it is necessarily conveyed in the packet headers.

End of section 2: 

  "For example, if coding vectors are

   constructed using a pseudo-random generator, the maximum number of

   redundant symbols that can be transmitted is limited by the number of

   available generator states."

7- I think you can remove this sentence. I don’t know what PRNG you have in

  mind but that’s not the type of issue we have, even if you don’t re-seed the

  PRNG but transmit the current state. As far as I’m concerned, I always 

  re-seed, since some PRNG have a state that does not consist of a single

  word. I’ll talk a little bit about PRNG during IETF102...

In section 3:

 "Adding a header to each symbol may

   result in a high overhead when the symbol size is small or when

   generation or sliding window size is large. Adding a joint header to

   the beginning of each generation may also cause synchronization to be

   re-initiated only at the beginning of each generation instead of

   every symbol."

8- the above approach is not robust and cannot be recommended.

  If data (source or repair) packets are not auto-sufficient, you’ll have to send

  this signalling packet a certain number of times.

I won’t comment on the following header proposals (it’s too premature I think

to go into such considerations). BTW, current practice is to have 32-bit drawings

as in:

    0                   1                   2                   3

    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

       |     …                                                                                                                                 |

Globally, the current I-D should clarify assumptions and is IMHO too ambitious.

So from the above questions/comments, I notice that several aspects are worth to be

discussed/explored first.

E1- parameter derivations

E2- dynamic parameter adaptation

E3- inter-session re-coding: what are the exact scenario we want to address?

  What’s the associated signalling we need?

  Being too ambitious may quickly turn the proposal into something impractical IMHO.

May I suggest that you have a careful look at:

                https://tools.ietf.org/html/draft-ietf-tsvwg-rlc-fec-scheme-05

because we already discuss/detail several of the above items. In particular 

parameter derivation.

Cheers,

     Vincent