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

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

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
>>>>>>
>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> 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
>>>>
>>>
>>
>> _______________________________________________
>> nwcrg mailing list
>> [e-mail] <mailto:[e-mail]>
>> https://www.irtf.org/mailman/listinfo/nwcrg
>