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

[Marie-Jose Montpetit <[e-mail]>]

I think we all agree :-)

Marie-Jose Montpetit, Ph.D.
[e-mail]
@SocialTVMIT

> On May 5, 2015, at 7:58 PM, Muriel Medard <[e-mail]> wrote:
> 
> Dear all,
> 
> I agree with Morten. 
> 
> A network code might not be used as a network code, and simply in a point to point fashion, but it should be able to be used as A network cide. A code that can only be used in a point to point fashion is not a network code. A point to point RS, even if implemented inside a network, does not become a network code.
> 
> Best, 
> 
> Muriel. 
> 
> 
> 
> Sent from my Verizon Wireless 4G LTE smartphone
> 
> 
> -------- Original message --------
> From: "Morten V. Pedersen" <[e-mail]> 
> Date: 05/05/2015 18:42 (GMT-05:00) 
> To: Vincent Roca <[e-mail]> 
> Cc: Jonathan Detchart <[e-mail]>, [e-mail], Muriel Medard <[e-mail]> 
> Subject: Re: [nwcrg] Sliding window draft and coding schemes (e.g. RLNC) 
> 
> Hi Vincent,
> I think it all depends on your scenario. We have built networks where we use recoding at WiFi repeaters for broadcast. Recoding does not require feedback to be useful.
> 
> Anyways I think we all agree that the are places in existing systems where recoding will not work and will not be practical. On the other hand as a research group I think we should also consider the future use of the technology - and in that spirit recoding is important. 
> 
> - M
>  
> On 05/05/2015 12:52 PM, Vincent Roca wrote:
>> Hello Morten,
>> 
>> I would add to the list of use-cases broadcast networks where you have no backward channel or don’t want to use it
>> (i.e. don’t want to have feedbacks) in order to remain as scalable as possible.
>> 
>> I don’t think we have problems finding use-cases where re-coding is not desirable/feasible. That’s probably a « degenerated »
>> version of NC, but I think we’re still in the scope of the NWCRG and in-line with Brian’s initial message.
>> 
>> Cheers,
>> 
>>   Vincent
>> 
>> 
>>> Le 5 mai 2015 à 17:10, jonathan detchart <[e-mail] <mailto:[e-mail]>> a écrit :
>>> 
>>> Hi Morten,
>>> 
>>> For example, if you don’t control the intermediate nodes, or if you have a single hop, re-encoding is not feasible or practical.
>>> 
>>> Some use cases : 
>>> - a coded tunnel (as we introduced at IETF86)
>>> - a transmission over the internet (assume you don’t control the route and the intermediate nodes)
>>> 
>>> Jonathan DETCHART
>>>> On 05 May 2015, at 05:13, Morten V. Pedersen <[e-mail] <mailto:[e-mail]>> wrote:
>>>> 
>>>> 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 <https://www.irtf.org/mailman/listinfo/nwcrg>
>>>>>>> 
>>>>>>> 
>>>>>>> 
>>>>>>> _______________________________________________
>>>>>>> nwcrg mailing list
>>>>>>> [e-mail] <mailto:[e-mail]>
>>>>>>> https://www.irtf.org/mailman/listinfo/nwcrg <https://www.irtf.org/mailman/listinfo/nwcrg>
>>>>>> 
>>>>>> _______________________________________________
>>>>>> nwcrg mailing list
>>>>>> [e-mail] <mailto:[e-mail]>
>>>>>> https://www.irtf.org/mailman/listinfo/nwcrg <https://www.irtf.org/mailman/listinfo/nwcrg>
>>>>> 
>>>> 
>>> 
>>> _______________________________________________
>>> nwcrg mailing list
>>> [e-mail] <mailto:[e-mail]>
>>> https://www.irtf.org/mailman/listinfo/nwcrg <https://www.irtf.org/mailman/listinfo/nwcrg>
>> 
> 
> _______________________________________________
> nwcrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/nwcrg