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

[Muriel Medard <[e-mail]>]

Dear all,

re-encoding is only infeasible, I believe, if non network (end-to-end) codes are used. The scaling gains of NC do not hold without re-encoding, so I think it is critical. I shall look forward to talking about it at the tutorial.

Best,

Muriel.

On May 4, 2015, at 9:29 AM, jonathan detchart <[e-mail]<mailto:[e-mail]>> 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]<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