Subject: Re: [nwcrg] Management of network/erasure coding schemes to carry and protect data application flows

From: Kuhn Nicolas <[email-masked]>
Date: Mon, 16 Jan 2017 09:35:08 +0000

Dear all, 

1- tunneling an aggregate: 

IMHO since application level protocols such as HTTP/2 and QUIC multiplexes flows, it is important to assess the management of erasure coding on multiplexed data.  
There is an interesting on-going discussion on that topic for QUIC [1]. 
Being at the application level, 
" The sender may decide whether to send FEC packets to optimize
   specific scenarios (e.g., beginning and end of a request)." [2]

Depending on whether the traffic is (1) QUIC and HTTP/2 over QUIC or (2) HTTP/2 over TCP, the management of erasure coding is not the same. 

2- managing single data flows:

For the single flows management, there are multiple initiatives to deal with application-limited traffic or tail losses. 
Using erasure coding is one of them. 
Following the NEAT project initiative[3], a middleware could adapt the coding rate as a function of the size of the file to transmit and make erasure coding an interesting way of dealing with tail losses. 

Kind regards, 

Nico 

[1] https://docs.google.com/document/d/1Hg1SaLEl6T4rEU9j-isovCo8VEjjnuCPTcLNJewj7Nk/edit# 
[2] https://tools.ietf.org/html/draft-tsvwg-quic-protocol-00 
[3] https://www.neat-project.org/ 

-------- Message original --------
Sujet: [nwcrg] Management of network/erasure coding schemes to carry and protect data application flows
Date: Vendredi, Janvier 13, 2017 17:43 CET
De: "LOCHIN Emmanuel" <[email-masked]> Répondre à: [email-masked]
Pour: [email-masked] 

Hello everybody,

I wish to start a discussion concerning the management of network/erasure coding schemes to carry and protect data application flows.
We are all users/developers of such schemes and we certainly use different ways to benefit/demonstrate their capabilities.
One common option is to use a tunnel or a proxy to encapsulate the data flow (this could be either a single flow or an aggregate).
Such context of use raises several questions from both transport and coding areas and I would be interested in exchanging views and discussing on the following items:

1. tunneling an aggregate:
Let's consider a tunnel that protects an aggregate of several flows. One possibility is to not distinguish flows between them and to protect the whole traffic as a single flow with a network coding scheme. As a matter of fact, this could have an impact at the microflow level depending on the rate of each encapsulated flow and each application type. For instance, combining indifferently bulk data traffic with VoIP traffic might not be the best way to perform. Obviously, there is an overhead cost to analyze the semantic of each flows;

2. managing single data flows :
For instance, let's consider either a connexion establishment or the termination of a connexion. There are cases where the application source does not have any more data to send. So, the transfer might stall because the decoder (from an erasure coding scheme) at the destination is still waiting for repair packets to rebuild missing packets and deliver them to the application. Without "seeing" the FIN flag, and thus analyzing packets, the decoder is not aware that no more packets will be sent by the source. So what to do during silence? Of course, some protocols (such as TCP) would recover by a retransmission timeout (considering that the retransmitted packet won't be lost... crossing fingers) but this won't be the case for several others protocols such as UDP reliable, DCCP, ...

In brief, the use of network coding scheme as a transport scheme raises several questions that I feel, are worth to debate.

Emmanuel

--
Emmanuel LOCHIN
Professeur ISAE
ISAE SUPAERO - Institut Supérieur de l'Aéronautique et de l'Espace
10 avenue Edouard Belin - BP 54032
31055 TOULOUSE CEDEX 4 FRANCE
http://www.isae-supaero.fr
Tel +33 5 61 33 84 85 - Fax (+33) 5 61 33 83 30

_______________________________________________
nwcrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/nwcrg

--
Emmanuel LOCHIN
Professeur ISAE
ISAE SUPAERO - Institut Supérieur de l'Aéronautique et de l'Espace
10 avenue Edouard Belin - BP 54032
31055 TOULOUSE CEDEX 4 FRANCE
http://www.isae-supaero.fr
Tel +33 5 61 33 84 85 - Fax (+33) 5 61 33 83 30

---

From: Vincent Roca <[email-masked]>
Date: Wed, 18 Jan 2017 08:00:33 +0100

Hello everybody,

You've raised good points.

1- tunnelling an aggregate:

This can be seen as  an "Operational and Management" topic. Concerning FECFRAME,
in the OAM section 10.2, we say:

   6.  Protecting a Single Flow vs. Several Flows Globally: In the
       general case, the various ADU flows that are globally protected
       can have different features, and in particular different real-
       time requirements (in the case of real-time flows).  The process
       of globally protecting these flows SHOULD take into account the
       requirements of each individual flow.  In particular, it would be
       counterproductive to add repair traffic to a real-time flow for
       which the FEC decoding delay at a receiver makes decoded ADUs for
       this flow useless because they do not satisfy the associated
       real-time constraints.  From a practical point of view, this
       means that the source block creation process at the sending FEC
       Framework instance SHOULD consider the most stringent real-time
       requirements of the ADU flows being globally protected.

Here the burden of doing intelligent things is transferred to the administrator in charge of
the tunnel. Can/should we do that dynamically and automatically? 

2- managing single data flow and situations with traffic interrupts and tail losses:

Looking at the traffic semantic to decide what to do seems complex and limited
(what to do with unknown transports, and the NEAT example is fine with this
perspective).

I have the feeling that such a situation should be addressed at the coding level.
In absence of incoming traffic, the left side of a sliding encoding window will
continue to slide as is the case when new incoming packets arrive, but here on a
timing decision. In case of block codes, this block will be shorter than expected
(this was considered in the block creation procedure for FECFRAME FEC schemes).
In both cases new repair packets will be produced and sent. 
And in fact, this applies regardless of whether there is a single or multiple flows
in the tunnel.

Cheers,

   Vincent

---

From: Kuhn Nicolas <[email-masked]>
Date: Mon, 23 Jan 2017 09:00:00 +0000

Dear all, 

Please see inline. 

Kind regards, 

Nico

-----Message d'origine-----
De : Vincent Roca [mailto:[email-masked]] 
Envoyé : mercredi 18 janvier 2017 08:01
À : Kuhn Nicolas; [email-masked]
Cc : Vincent Roca
Objet : Re: [nwcrg] Management of network/erasure coding schemes to carry and protect data application flows

Hello everybody,

This can be seen as  an "Operational and Management" topic. Concerning FECFRAME, in the OAM section 10.2, we say:

Here the burden of doing intelligent things is transferred to the administrator in charge of the tunnel. Can/should we do that dynamically and automatically? 

[NK] I think that the relevance of such dynamism highly  depends on the layer at which the tunnel is set up. 
In the case of HTTP/2.0 traffic, the management of the priorities between the streams could indeed consider the most stringent real-time requirements of specific applications. 
In the case of a tunnel that interconnects two sites, going up to the application characteristics is quite complex: the identification of the application may require DPI techniques or other flow identification techniques, that may not identify the exact real-time requirements. 
IMHO, the dynamic or automatic intelligent things could be imagined with approaches such as NEAT project.   

Looking at the traffic semantic to decide what to do seems complex and limited (what to do with unknown transports, and the NEAT example is fine with this perspective).

[NK] +1

I have the feeling that such a situation should be addressed at the coding level.
In absence of incoming traffic, the left side of a sliding encoding window will continue to slide as is the case when new incoming packets arrive, but here on a timing decision. In case of block codes, this block will be shorter than expected (this was considered in the block creation procedure for FECFRAME FEC schemes).
In both cases new repair packets will be produced and sent. 
And in fact, this applies regardless of whether there is a single or multiple flows in the tunnel.

[NK] I do not know to what extent this coding to prevent tail losses from occuring is efficient as opposed to other techniques (RTO restart, by example).
I would be very interested in seeing some results on that topic. 

Cheers,

   Vincent

---

From: Emmanuel Lochin <[email-masked]>
Date: Mon, 23 Jan 2017 11:46:47 +0100

Dear all,

Thanks for your useful answers. My comments [EL] inline.

Le 23/01/2017 à 10:00, Kuhn Nicolas a écrit :
> This can be seen as  an "Operational and Management" topic. Concerning 
> FECFRAME, in the OAM section 10.2, we say:
>
> Here the burden of doing intelligent things is transferred to the 
> administrator in charge of the tunnel. Can/should we do that 
> dynamically and automatically?
>
> In the case of HTTP/2.0 traffic, the management of the priorities 
> between the streams could indeed consider the most stringent real-time 
> requirements of specific applications.
> In the case of a tunnel that interconnects two sites, going up to the 
> application characteristics is quite complex: the identification of 
> the application may require DPI techniques or other flow 
> identification techniques, that may not identify the exact real-time 
> requirements.

[EL] I agree that DPI techniques might not be the answer and is not 
applicable when https (http over ssl) carries out a flow. I reckon a 
fair solution would be to mark the traffic with DSCP (as explained in 
RFC5865) to differentiate flows between them and then to apply the right 
scheduling at the entry of the tunnel. If not marked, a default 
scheduling depending on the packet size or any other criteria could be set.

> Looking at the traffic semantic to decide what to do seems complex and 
> limited (what to do with unknown transports, and the NEAT example is 
> fine with this perspective).
>
> [NK] +1
>
> In absence of incoming traffic, the left side of a sliding encoding 
> window will continue to slide as is the case when new incoming packets 
> arrive, but here on a timing decision. In case of block codes, this 
> block will be shorter than expected (this was considered in the block 
> creation procedure for FECFRAME FEC schemes).

[EL] This means that repair packets should be produced in a timely 
manner without depending on the source packet frequency? This is fine 
for me.

>
> [NK] I do not know to what extent this coding to prevent tail losses 
> from occuring is efficient as opposed to other techniques (RTO 
> restart, by example).

[EL] The objective is to finally prevent RTO retransmission by the upper 
layer (either at the transport layer or application layer depending 
where the coding scheme is set).
Over long delay path, RTO remains the worse recovery mechanism for a 
"real-time" application.

Emmanuel

-- 
Emmanuel LOCHIN
Professeur ISAE
ISAE SUPAERO - Institut Supérieur de l'Aéronautique et de l'Espace
10 avenue Edouard Belin - BP 54032 - 31055 TOULOUSE CEDEX 4 FRANCE -
http://www.isae-supaero.fr
Tel +33 5 61 33 84 85 - Fax (+33) 5 61 33 83 45
Web : http://personnel.isae.fr/emmanuel-lochin/

En 2017, donnez du sens Ã  la taxe d'apprentissage, soutenez l'ISAE-SUPAERO !
https://www.isae.fr/fr/actualites/versez-la-taxe-d-apprentissage-a-l-isae-supaero-c-est-facile

---

From: Vincent Roca <[email-masked]>
Date: Mon, 23 Jan 2017 17:20:09 +0100

Hi Emmanuel and Nicolas,

Two small comments.

> [EL] I agree that DPI techniques might not be the answer and is not applicable when https (http over ssl) carries out a flow. I reckon a fair solution would be to mark the traffic with DSCP (as explained in RFC5865) to differentiate flows between them and then to apply the right scheduling at the entry of the tunnel. If not marked, a default scheduling depending on the packet size or any other criteria could be set. 

[VR] The FECFRAME use-case is not representative of all situations... The multiplex is often static, described
in an SDP file, and therefore is well suited to the managed approach as I reminded.
A dynamic tunnel between two remote sites for instance raises totally different questions as you explained, sure.

> [EL] This means that repair packets should be produced in a timely manner without depending on the source packet frequency? This is fine for me. 

[VR] This is what we are already doing in our FECFRAME implementation. Timing does matter when building the source block (block FEC case) and encoding
window (convolutional FEC case). 

> [EL] The objective is to finally prevent RTO retransmission by the upper layer (either at the transport layer or application layer depending where the coding scheme is set). 
> Over long delay path, RTO remains the worse recovery mechanism for a "real-time" application. 

Cheers,

  Vincent

---

From: "LOCHIN Emmanuel" <[email-masked]>
Date: Tue, 24 Jan 2017 07:31:06 +0100

Hi Vincent,

> window (convolutional FEC case). 

If I undestrand correctly: when the source application does not produce data to send during a laps of time (i.e. pause in the transmission), the source encoding window still produces repair packets at a given frequency (built with different encoding coefficients I assume).
This allows the receiver decoding window to flush all remaining packets to decode. At last, when the source application does not produce data to send anymore (i.e. end of the transmission) and the receiver decoding window is already flushed, the decoding receiver just need to stop this
repair packets traffic by feedback to the source encoder. How the decoding receiver assesses the transmission is over ? By checking the FIN flag ? Setting a timeout ? Adding a secondary signaling transmission management path ?
The price for the network is the overhead of this repair traffic. A smart window management signaling during the whole transmission is mandatory to decrease this overhead.

Emmanuel

En 2017, donnez du sens à la taxe d'apprentissage, soutenez l'ISAE-SUPAERO !
https://www.isae.fr/fr/actualites/versez-la-taxe-d-apprentissage-a-l-isae-supaero-c-est-facile

---

From: Pierre Ugo Tournoux <[email-masked]>
Date: Tue, 24 Jan 2017 12:49:28 +0400

Hello everybody,

See my comment inline :

1- tunnelling an aggregate:

> administrator in charge of
[PU]> While I agree that coding rate and scheme should fit the requirement
of each flow, there is probably room for improvement in grouping flows with
similar requirement together AS WELL AS flows that have slighly lower
requirements (to some extent at least).

Let a flow 1 have a bandwidth B1 and delay requirement D1 and the
associated code rate is C1. First let assume another flow 2 has bandwidth
B2=B1, delay requirement D2=D1 and code rate C2<C1. Encoding the two flows
separatly would induce an overhead of D1*C1+D2*C2. Encoding the two flows
together with the same coding rate would induce the same other overhead but
the decoding delay would be much lower. As a consequence the coding rate
can be reduced to a value C12<C1 and save ressources while still satisfying
the decoding delay D1.

Now let assume the flow 2 is such as B2=B1, D2>D1 and C2<C1. If the
difference between D1 and D2 is small enough it will still be possible to
encode C1 and C2 together while reducing the overhead compared to the case
where they are encoded separatly.

I am not aware of any reference that would study the overhead gain
achievable by encoding flows with different characteristics together but
from my experience working with scheme such as [Tetrys] this is something
worth investigating.

[Tetrys] On-the-fly erasure coding for real-time video applications
<https://scholar.google.fr/scholar?oi=bibs&cluster=2252700756504273361&btnI=1&hl=fr>

> limited

[PU]> Regarding the RTO issues I agree. In [tournoux10] we dealt with RTO
issues by seding repair packets periodicaly in addition to the code rate of
the Tetrys scheme. It solved a lots of our problem at the cost of a
negligible overhead.

[tournoux10] A packet error recovery scheme for vertical handovers mobility
management protocols
<https://scholar.google.fr/scholar?oi=bibs&cluster=13697344477412239056&btnI=1&hl=fr>

---

From: Vincent Roca <[email-masked]>
Date: Fri, 27 Jan 2017 15:08:31 +0100

Hello Emmanuel,

> If I undestrand correctly: when the source application does not produce data to send during a laps of time (i.e. pause in the transmission), the source encoding window still produces repair packets…

Let me explain the way it works with FECFRAME / block codes, in a purely unidirectional use-case (there's no feedback with FECFRAME).

Each time a FECFRAME sender receives a new fresh source packet (I skip details), it is accumulated in the block under construction.
If the current size of this block reaches maximum, the FECFRAME sender performs FEC encoding and next source packet will be for a new block to create.

In addition to this, periodically, the FECFRAME sender checks if the maximum delay allocated to the creation of the current block under
construction has been reached. 
If this is the case, the FECFRAME sender performs FEC encoding and next source packet will be for a new block to create.

This technique addresses the problem of a pause in the source flow arriving at the FECFRAME sender.
If this pause is very long, no repair packet will be sent past the last block. The sender needs fresh source packets to resume the process.

With FECFRAME / convolutional codes, this is pretty much the same, replacing "block" by "encoding window". This latter will keep on sliding
when packets on the left of this window get too old to be kept in the window, until there's no packet any more in the window.

> The price for the network is the overhead of this repair traffic. A smart window management signaling during the whole transmission is mandatory to decrease this overhead.

There is no repair traffic past the last block or when the encoding window has slid past the last source packet in the above FECFRAME example.

Signalling the end of session (if this is the case) can be done with a dedicated signalling flag in the header. There is no such facility with FECFRAME,
but you'll find the "A flag" in LCT header (used with FLUTE/ALC).

        "The sender MAY set A to 1 when
         termination of transmission of packets for the session is
         imminent.  A MAY be set to 1 in just the last packet
         transmitted for the session, or A MAY be set to 1 in the last
         few seconds of packets transmitted for the session."

Here also we are on a purely unidirectional channel. This is pretty easy, although not fully reliable if there's no feedback; think about a receiver behind
an obstacle for a long time, missing all the packets with A set to 1... 

Of course if your use-case assumes there's a feedback flow (as with Tetrys most of the time), one can do more smart things. It all depends on your
assumptions.

Cheers,

   Vincent

---

From: Vincent Roca <[email-masked]>
Date: Fri, 27 Jan 2017 15:24:35 +0100

Hello Pierre Ugo,

> [PU]> While I agree that coding rate and scheme should fit the requirement of each flow, there is probably room for improvement in grouping flows with similar requirement together AS WELL AS flows that have slighly lower requirements (to some extent at least).

[VR] You've raised a good point and existing recommendations can be improved (with Ali were working on an extension of FECFRAME
so there's an opportunity to do that). However I need to better understand your point.

> Let a flow 1 have a bandwidth B1 and delay requirement D1 and the associated code rate is C1. First let assume another flow 2 has bandwidth B2=B1, delay requirement D2=D1 and code rate C2<C1. Encoding the two flows separatly would induce an overhead of D1*C1+D2*C2. Encoding the two flows together with the same coding rate would induce the same other overhead but the decoding delay would be much lower. As a consequence the coding rate can be reduced to a value C12<C1 and save ressources while still satisfying the decoding delay D1.

[VR] Above, the overhead introduced is more probably D1/C1 + D2/C2 when encoding flows independently
(unless we have different definition of coding rate: cr = k / n with a block code).
With the two flows encoded together, it becomes: (D1+D2)/C12.
How to assign C12? 
Why should it be the same overhead (it's not the case)?
Why should the decoding delay be much lower?
The only thing that seems obvious to me is the improved protection as we are working with larger blocks or encoding windows,
and therefore can accommodate longer erasure bursts while keeping the same overhead (code rate).

> Now let assume the flow 2 is such as B2=B1, D2>D1 and C2<C1. If the difference between D1 and D2 is small enough it will still be possible to encode C1 and C2 together while reducing the overhead compared to the case where they are encoded separatly.

[VR] Sorry, but I didn't catch the logic.

> I am not aware of any reference that would study the overhead gain achievable by encoding flows with different characteristics together but from my experience working with scheme such as [Tetrys] this is something worth investigating.
> 
> [Tetrys] On-the-fly erasure coding for real-time video applications <https://scholar.google.fr/scholar?oi=bibs&cluster=2252700756504273361&btnI=1&hl=fr>
> 
> 
> 
> [PU]> Regarding the RTO issues I agree. In [tournoux10] we dealt with RTO issues by seding repair packets periodicaly in addition to the code rate of the Tetrys scheme. It solved a lots of our problem at the cost of a negligible overhead.
> 
> [tournoux10] A packet error recovery scheme for vertical handovers mobility management protocols <https://scholar.google.fr/scholar?oi=bibs&cluster=13697344477412239056&btnI=1&hl=fr>

[VR] Why not if it helps. I need to have a look to your paper though.

Thanks,

    Vincent