Re: [nwcrg] Sliding window draft and coding schemes (e.g. RLNC)

["Morten V. Pedersen" <[e-mail]>]

Hi everybody,
I've just finished reading RFC 6363, and I agree with Vincent's 
assessment that the general concepts and architecture looks okay. As 
Vincent points out in draft-roca-nwcrg-fecframev2-problem-position-00 it 
is mostly a question of removing the limitation of fixed size blocks.

Below are my comments to draft-roca-nwcrg-fecframev2-problem-position-00:

Section 1.

   However, it is REQUIRED in [RFC6363] that the FEC scheme operate in a
   block manner, i.e., the input flow(s) MUST be segmented into a
   sequence of blocks, and FEC encoding (at a sender/coding node) and
   decoding (at a receiver/decoding node MUST be performed
   independently on a per-block basis. This approach has a major impact
   on coding and decoding delays.

I don't think the fact that we operate in a block manner impacts the 
delay significantly. It is possible with most blocked RLNC codes to code 
only over the symbols currently available (and for the decoder to 
"detect" full rank of a sub-matrix). The crux of the problem is however 
captured in the next statement.

   Encoding requires that all the source symbols be known at the encoder.

This is the real problem causing delay. Mapping this back to RFC 6363 
(Section 4.1 p.12 top) I would say that the following statement :

   The FEC Framework then performs two operations. First, it appends
   the Source FEC Payload IDs, if provided, to each of the ADUs, and
   sends the resulting packets, known as "FEC source packets", to the
   receiver. Second, it places the provided FEC repair packet payloads
   and corresponding Repair FEC Payload IDs appropriately to to construct
   FEC repair packets and send them to the receiver.

Which specifically defines an order in which source and repair symbols 
should be sent should be softened. Such that we are allowed to 
dynamically generate repair according to some rate defined in the CDP.

Section 2.2

   A Code Rate close to 1 indicates that a small number of Output
   Symbols have been produced during the encoding process.

I think Output Symbols should be replaced with Repair Symbols to match 
the definitions?

Section 4.2

   The question of having multiple in-network re-coding operations
   is not considered in [RFC6363]. The question whether this is feasible
   and appropriate, given the typical FECFRAME use-cases, is an open
   question that remains to be discussed.

I think it worth including, but maybe not in this first iteration. 
If/when we decide to do it. I think most of the logic for this could 
reside in the CDP. The additional functionality needed by the FEC scheme 
would (I think) be minimal. Also the FEC payload ID for encoded and 
recoded packets would probably be the same for most FEC schemes.

Section 4.5

   The question of having FECFRAME used in lower protocol layers is not
   considered in [RFC6363]. Whether this is feasible and appropriate,
   given the typical FECFRAME use-cases, is an open question that
   remains to be discussed.

It is a good question. I would probably just say that it is a bridge we 
will cross should it ever become relevant. I would probably not try to 
include anything on that into the document.

Section 5.1

In the description of the interaction between the FEC Framework v2 and 
the FEC Scheme. I think it would be nice to describe it in terms of a 
"pull model" where the FEC Framework v2 or the CDP "pulls" repair 
symbols from the FEC Scheme at a suitable rate (defined by the CDP). The 
way it is formulated now it is not clear whether it is the FEC Scheme 
that defines how many repair symbols are created or the FEC Framework v2 
/ CDP. But I think that is also unclear in RFC6363, perhaps it is just me ;)

Section 5.2

   with FECFRAMEv2 in window mode, can be dynamic and chosen on a
   per-window basis. In that case the length of repair symbols will
   dynamically evolve as well in order to be equal to the maximum
   ADUI size in the encoding window at the time of encoding.

I would say we can even "loosen" this a bit more and way that the length 
will be "equal to the maximum ADUI size included in a repair symbol". So 
even though we have a very long symbol in the window, if it isn't 
included in a specific encoding it will not impact the length of that 
repair symbol. This will not have much impact on high field codes - but 
for binary/sparse codes it may.

For Figure 2 the definition of the F and L fields should be given. I did 
not find it - but perhaps I missed it.


Section 5.3

   at the FECFRAME instance level

Should be "at the FECFRAMEv2 instance level"

   if the sender knows that a particular ADU has been correctly
   received by the receiver(s), the corresponding source symbol(s)
   is(are) removed. Of course this mechanism requires that an
   acknowledgement mechanism be setup to inform the FECFRAMEv2 sender
   of good ADU reception, which is out of the scope of FECFRAMEv2.
   Whether or not this is desirable is an open question;

I think we should consider including it. One way of doing it is to let 
the FEC Scheme decoder (receiver) be queried, whether it has feedback 
for the encoder (sender) or not. If it has feedback to send and the CDP 
has a method of getting that feedback to the sender then it can take 
advantage of it. However, no FEC scheme should rely on the feedback e.g. 
to move the window, but simply utilize it for performance reasons. I 
think this is also in-line with what is already in RFC 6363 Section 6. 
However, we many want to explicitly generate some working around that 
and define a container for it FEC Feedback Information.

Section 5.4

I don't this the symbol identifiers should be specified by the 
FECFRAMEv2, but rather left up the specific FEC Scheme. I might have 
missed something here but to me the symbol identifiers specified by RFC 
6363 see adequate for our purpose here as well.

That was it, let me know your thoughts.

Best regards,
Morten


On 04/12/2015 10:35 AM, Vincent Roca wrote:
> Hello Brian and everybody,
>
> In order to move forward and enrich the end-to-end transport use-case 
> discussions, I have
> worked on an update to FECFRAME in order to support the sliding window 
> approach (see
> my other email). The general architecture and concepts seem okay to me 
> at first glance.
>
> Here also the next step is now to specify a first convolutional FEC 
> Scheme… This I-D will be,
> for some parts, FECFRAME specific, but the rest will be common with 
> other NC proposals.
>
> And we need a public repository to work collaboratively on this and 
> other documents
> (e.g., taxonomy)…
>
> Cheers,
>
>   Vincent
>
>
>> Le 6 avr. 2015 à 18:44, Brian Adamson <[e-mail] 
>> <mailto:[e-mail]>> a écrit :
>>
>> As a result of some discussion with Marie, I thought it would be a 
>> good idea to share a few of my thoughts on some of the near term 
>> activities we seem to have identified and making some progress on. 
>>  One of the nearer-term “products” of our NWCRG discussion is the 
>> end-to-end transport use case with the developing sliding window 
>> approach being documented in Jonathan, et al’s draft.
>>
>> To support that work, it could be good to consider trying to document 
>> an accompanying “FEC Scheme or two (e.g. RLNC, etc) that could be 
>> applied with the sliding window protocol.  That may help us get the 
>> framework right.  It would perhaps even be an interesting thought 
>> exercise to see if something like RLNC could documented in the form 
>> of an RMT or FecFrame “FEC Scheme”?.  One thing to note here is the 
>> the main value proposition for _unicast_ end to end use of coding 
>> lies somewhat with the delay improvements and that the sliding window 
>> type approach helps maximize the gains here as compared to the 
>> transport efficiencies coding yields for multicast (it also gets some 
>> delay benefits too under certain use cases).  While some of the 
>> formats / semantics of RMT/FecFrame may be reused, they may be too 
>> "block code oriented” as they are currently specified?
>>
>> So I think we are sort of on a good course to get some consensus for 
>> defining a sliding window framework that one could then “plug in” 
>> RLNC and some of the other coding algorithms discussed (all the IPR 
>> issues notwithstanding).  It may be necessary to have the sliding 
>> window document to provide a reference for how to specify RLNC.  We 
>> did that in RMT where we wrote the “FEC Building Block” document that 
>> established some core packet formats (and IANA registries) so we 
>> could go on to document specific FEC coding algorithms (we called 
>> them FEC Schemes) including non-proprietary stuff like Reed Solomon, 
>> LDPC as well as the proprietary Raptor codes, etc.
>>
>> I haven’t been too explicitly vocal on this aspect because it seemed 
>> we were getting some progress on this with Jonathan’s draft and more 
>> recently Morten’s constructive comments on that.  This may be one of 
>> the pieces that can transition more early to IETF working group 
>> activities for end-to-end transport purposes while we continue in 
>> NWCRG to work on the more “researchy” items. I think having this 
>> initiated in NWCRG is OK since we’ve assembled a set of people that 
>> may be able to work the problem?  And if we establish a basis of 
>> components (e.g. packet formats, coding scheme definitions) from this 
>> that may also be useful for other applications of network coding 
>> (i.e. more “in network” things like your DNC concept, ideas like 
>> Cedric described, SDN applications of coding, etc), then it is also 
>> beneficial to ongoing NWCRG work, too.  Then, when it’s sufficiently 
>> mature it might find a (transport area) working group home for the 
>> longer term?
>>
>> Again I personally haven’t explicitly articulated this like I’ve done 
>> here since we seemed (to me) to be sort of proceeding (perhaps 
>> lurching) along this path anyway, but (with Marie’s help) have 
>> realized these might thoughts worth sharing.
>>
>> best regards,
>>
>> Brian
>> _______________________________________________
>> nwcrg mailing list
>> [e-mail] <mailto:[e-mail]>
>> https://www.irtf.org/mailman/listinfo/nwcrg
>
>
>
> _______________________________________________
> nwcrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/nwcrg