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

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

Ok, I see what you mean. I was thinking about it from a 
computational/algorithmic point of view - in which case re-coding is 
very practical and easy to implement. But, of course as Muriel also 
points out, if you don't have access to the data then there is only so 
much you can do.

Anyways, I'm pretty sure that for every example where we cannot use 
recoding there are others where we can - like p2p, mesh, etc. Not 
considering recoding would be an unnecessary limitation in my opinion.

- M


On 05/05/2015 11:10 AM, jonathan detchart wrote:
> 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
>>>
>>
>