Subject: [nwcrg] Taxonomy draft

From: "Firoiu, Victor (US SSA)" <[email-masked]>
Date: Wed, 6 Nov 2013 05:52:57 +0000

Dear NetCoders,

We assembled a first draft of Network Coding terminology that would help our future discussions on research and protocol architecture. It is not intended to propose some specific solutions, but to have a common definition of the constructs many of us have been using in the various systems we developed or analyzed.

Please propose additions and edits with the purpose of converging to a Taxonomy document.
While we started in a slide format for the upcoming meeting, we will transform it into a text document on which to comment and edit.

Best,

Victor

---

From: Marie-Jose Montpetit <[email-masked]>
Date: Wed, 6 Nov 2013 01:54:48 -0800

Nice work. Just a few comments:

1. How about deterministic codes?

2. On the link between NC and Content Centric/Information Centric Networking there is a paper from last year from Cedric Westphal, Dirk Trossen and myself that eventually could be contributed

3. This document seems to emphasize multicast. It's probably not the case but maybe somewhere unicast and P2P should be clearly listed.

4. Maybe more is needed on applications research?

See you Thursday.

Marie-José Montpetit
[email-masked]
[email-masked]

> On Nov 5, 2013, at 21:52, "Firoiu, Victor (US SSA)" <[email-masked]> wrote:
> 
> Dear NetCoders,
>  
> <Network_Coding_Taxonomy.pdf>
> _______________________________________________
> nwcrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/nwcrg

---

From: "Firoiu, Victor (US SSA)" <[email-masked]>
Date: Wed, 6 Nov 2013 16:23:19 +0000

Marie-José,

Thank you very much.  My comments are below.

Yes, it is missing, and looking for proposals to cover taxonomy in that area.

Thank you. We would like to gather theoretical research and practical advances in separate document or wiki page.

We tried to be agnostic to the number of destinations in a session. Please suggest if you know terminologies particular to unicast that are missing.

Definitely, please suggest. We will gather them, along with the use cases list we had in July, into a wiki page, and possibly a document.

Thank you again,

Victor

---

From: Frank Fitzek <[email-masked]>
Date: Thu, 7 Nov 2013 10:19:58 +0100

Dear all,

here some terms that we might want to add.

  * density of the coding coefficients = number of non zero coefficients
  * generation = number of uncoded packets to be considered in a block
  * field type = binary, binary extension, optimal prime field, etc
  * field size
  * sliding window = "tunnel" through the coding matrix by non zero
    elements (requires feedback or optimistic assumptions)
  * online en/re/de-coding = part of sliding window with no feedback
    (number of non zero elements increases over time
  * coding options: encoding, decoding, and RECODING
  * systematic coding

Just my 2 cents

Have fun today , we will be online ..

On 06.11.2013 17:23, Firoiu, Victor (US SSA) wrote:
> 2. On the link between NC and Content Centric/Information Centric 
> Networking there is a paper from last year from Cedric Westphal, Dirk 
> Trossen and myself that eventually could be contributed
>
> Thank you. We would like to gather theoretical research and practical 
> advances in separate document or wiki page.
>
> 3. This document seems to emphasize multicast. It's probably not the 
> case but maybe somewhere unicast and P2P should be clearly listed.
>
> We tried to be agnostic to the number of destinations in a session. 
> Please suggest if you know terminologies particular to unicast that 
> are missing.
>
> Definitely, please suggest. We will gather them, along with the use 
> cases list we had in July, into a wiki page, and possibly a document.
>
> Thank you again,
>
> Victor
>
>
>
>
>

---

From: "Senthil Sivakumar (ssenthil)" <[email-masked]>
Date: Thu, 7 Nov 2013 14:56:01 +0000

We would want to add

  *   On the fly network coding
  *   Redundant coded information

Senthil

From: Frank Fitzek <[email-masked]<mailto:[email-masked]>>
Date: Thursday, November 7, 2013 5:19 AM
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: Re: [nwcrg] Taxonomy draft

Dear all,

  *   density of the coding coefficients = number of non zero coefficients
  *   generation = number of uncoded packets to be considered in a block
  *   field type = binary, binary extension, optimal prime field, etc
  *   field size
  *   sliding window = "tunnel" through the coding matrix by non zero elements (requires feedback or optimistic assumptions)
  *   online en/re/de-coding = part of sliding window with no feedback (number of non zero elements increases over time
  *   coding options: encoding, decoding, and RECODING
  *   systematic coding

Just my 2 cents

Marie-José,

Thank you again,

Victor

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

---

From: Cedric Adjih <[email-masked]>
Date: Thu, 7 Nov 2013 16:26:14 +0100 (CET)

Dear Victor, dear all,

  This first draft of taxonomy is already in very good shape.
I can attend only remotely and will not be able to participate in 
the discussion, but here is one general comment:

  The text document will describe terminology and applicability of 
network coding: I really like the fact that the content of the slides 
is nicely structured starting from one notional architecture (slides 4+5); 
this provides a framework to divide the terminology in different areas.

  And then, do you think that the taxonomy document or another document,
could include more than terminology, and also collect the 
how different elements (such as flow control) could be combined ?

  In the spirit of what Brian Adamson/Vincent Roca will present
(http://www.ietf.org/proceedings/88/slides/slides-88-nwcrg-1.pdf),
that would be exactly: identifying "building blocks" of existing 
network coding architectures (many of them are already in slides 4-5)
and then their related terminology.

  In any case, I'd also volunteer to give a go at reviewing some
network coding surveys (/books), and identifying more terminology 
defined there.

Regards,
-- Cedric

----- Original Message -----
From: "Victor Firoiu (US SSA)" <[email-masked]>
To: [email-masked]
Sent: Wednesday, November 6, 2013 6:52:57 AM
Subject: [nwcrg] Taxonomy draft

Dear NetCoders, 

Best, 

Victor

---

From: "Bilbao, Josu" <[email-masked]>
Date: Thu, 7 Nov 2013 17:06:08 +0000

Good morning to everyone in Vancouver!
A few comments added related with the taxonomy:

-          I would separate Generation from Generation size:

o   Generation: The set of packets/symbols used in the combination process. The generation is characterized by its size (known generation size).

o   Generation Size: the number of packets involved in the combination of a generation of packets/symbols. If Generation size =1 its known as systematic coding.

-          Coding Density/sparsity: As the number of packets used in the combination process

-          Reception Matrix: The matrix compounded of the coefficients received.

-          Rank of reception Matrix: Rank of the received coefficients matrix.

-          Transmission Matrix (or Encoding Matrix): The matrix compounded of the linear combinations generated by multiplying the incoming packets and randomly chosen coefficients in the Galois finite field of size Fq.

-          Solvable: indicates the number of original information variables that can be decoded from a given generation set.

This time, as I could not travel to Vancouver, I will assist to the meeting remotely. Hope everything goes right!
Best regards,
Josu Bilbao

De: Senthil Sivakumar (ssenthil) [mailto:[email-masked]]
Enviado el: jueves, 07 de noviembre de 2013 15:56
Para: [email-masked]
Asunto: Re: [nwcrg] Taxonomy draft

We would want to add

Dear all,

Just my 2 cents

Marie-José,

Thank you again,

Victor

nwcrg mailing list

---

From: "Firoiu, Victor (US SSA)" <[email-masked]>
Date: Thu, 7 Nov 2013 17:52:41 +0000

Thank you all for your inputs to the Taxonomy document. When you propose a term, please also give the associated definition you are thinking of. For example, we need definitions from Frank and Senthil. Josu's definitions are close, may need a bit more details to remove any ambiguity.

We will also filter overlapping definitions. For example, I think that Josu's Rank is probably the same as the Rank we already defined in the draft we've sent.

Thanks again,

Victor

From: [email-masked] [mailto:[email-masked]] On Behalf Of Bilbao, Josu
Sent: Thursday, November 07, 2013 12:06 PM
To: [email-masked]
Subject: Re: [nwcrg] Taxonomy draft

De: Senthil Sivakumar (ssenthil) [mailto:[email-masked]]
Enviado el: jueves, 07 de noviembre de 2013 15:56
Para: [email-masked]<mailto:[email-masked]>
Asunto: Re: [nwcrg] Taxonomy draft

We would want to add

Dear all,

Just my 2 cents

Marie-José,

Thank you again,

Victor

nwcrg mailing list

---

From: "Firoiu, Victor (US SSA)" <[email-masked]>
Date: Thu, 7 Nov 2013 17:56:30 +0000

Cedric,

Thank you for your input.

Describing usage and building block is the natural continuation of the taxonomy. I would prefer to be in a separate document, to both limit the length and have a logical separation between definitions and usage. A building blocks doc as used for FEC/NORM is a good example we can follow.

Thanks,
Victor

-----Original Message-----
From: Cedric Adjih [mailto:[email-masked]] 
Sent: Thursday, November 07, 2013 10:26 AM
To: [email-masked]
Cc: Firoiu, Victor (US SSA)
Subject: Re: [nwcrg] Taxonomy draft

  Dear Victor, dear all,

  This first draft of taxonomy is already in very good shape.
I can attend only remotely and will not be able to participate in the discussion, but here is one general comment:

  The text document will describe terminology and applicability of network coding: I really like the fact that the content of the slides is nicely structured starting from one notional architecture (slides 4+5); this provides a framework to divide the terminology in different areas.

  And then, do you think that the taxonomy document or another document, could include more than terminology, and also collect the how different elements (such as flow control) could be combined ?

  In the spirit of what Brian Adamson/Vincent Roca will present (http://www.ietf.org/proceedings/88/slides/slides-88-nwcrg-1.pdf),
that would be exactly: identifying "building blocks" of existing network coding architectures (many of them are already in slides 4-5) and then their related terminology.

  In any case, I'd also volunteer to give a go at reviewing some network coding surveys (/books), and identifying more terminology defined there.

Regards,
-- Cedric

----- Original Message -----
From: "Victor Firoiu (US SSA)" <[email-masked]>
To: [email-masked]
Sent: Wednesday, November 6, 2013 6:52:57 AM
Subject: [nwcrg] Taxonomy draft

Dear NetCoders, 

Best, 

Victor

---

From: Vincent Roca <[email-masked]>
Date: Thu, 7 Nov 2013 12:35:08 -0800

Victor, all,

Good start.
My main comment is the following:

1- we have to decide to what level it makes sense to align definitions here with that of RMT/FECFRAME WGs.
	Even if some use cases differ, even if the community differ a little bit, there are clear links (my presentation).
	A few examples:
	- payload vs. symbol
	- application-level payloads (or original payloads, it's not consistent) vs. source symbols
	- codec payloads vs. encoding symbols and (particular case) repair symbols
	- symbols (slide Payload level operations) vs. elements of a GF
	- coding block vs. source block	
	- coding vector in fig 2 vs. FEC Payload Information

A few additional comments:

2- I don't think that opposing RLC and "deterministic codes" is fine, as all FEC codes I know, RLC included, are
	deterministic. I'd rather speak of FEC or AL-FEC codes, RLC being an important particular case.

3- sliding window can be further refined in "regular sliding encoding window" and "elastic sliding encoding window"
	depending on the way the window slides: in a regular, known way, as with convolutional codes (1st case), or
	in an unpredictable way (2nd case, as with Tetrys or similar on-the-fly encoding schemes with feedbacks.

4- Block NACK: a bit obscur definition.

5- Flow definition: if a set of packets is sent across several paths, with the same {src; dest}, is it considered
	the same flow (suggested here by the definition) or as multiple flows (which also makes sense)?

6- Intermediate coding or re-coding? 

etc.  We'll see during the meeting for the rest.

I can also gather some IETF accepted definitions (e.g. of the above terms) as a potential input to this doc.

Cheers,

   Vincent

NB: please add slide numbers to facilitate cross references. Thanks.