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

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

Hi Jonathan,
I'm a bit puzzled by your statement "many use cases where re-encoding is 
not feasible or practical". Do you have any specific scenarios in mind?

- M


On 05/04/2015 09:29 AM, jonathan detchart wrote:
> Morten,
> I re-read your email. We fully agree on the use of windows since this 
> is what Tetrys has been doing from the start.
>
> Muriel,
> On the re-encoding :
> while this should be a valued feature we all know of many use cases 
> where re-encoding is not feasible or practical.
>
> So our modified FECFRAME (NCFRAME ?) should be use-case driven to 
> allow maximum flexibility and even in some cases the use of network 
> codes as simple (AL-)FEC (block codes, or not).
>
> Jonathan DETCHART
>> On 04 May 2015, at 03:58, Muriel Medard <[e-mail] 
>> <mailto:[e-mail]>> wrote:
>>
>>
>> Dear all,
>>
>> Thank you. I think it is important that coding not be restricted to 
>> blocks, which can be highly limiting and incompatible with sliding 
>> windows. Recoding is crucial. Otherwise,  it is just a code, like RS 
>> or Fountain,  not a network code.
>>
>> Best, Muriel.
>>
>>
>> Sent from my Verizon Wireless 4G LTE smartphone
>>
>>
>> -------- Original message --------
>> From: "Morten V. Pedersen" <[e-mail] <mailto:[e-mail]>>
>> Date: 05/03/2015 20:28 (GMT-05:00)
>> To: [e-mail] <mailto:[e-mail]>
>> Subject: Re: [nwcrg] Sliding window draft and coding schemes (e.g. RLNC)
>>
>> 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
>>
>> _______________________________________________
>> nwcrg mailing list
>> [e-mail] <mailto:[e-mail]>
>> https://www.irtf.org/mailman/listinfo/nwcrg
>