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

From: Janus Heide <[email-masked]>
Date: Thu, 2 Aug 2018 08:56:55 +0200

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