Subject: [nwcrg] Network Coding Taxonomy

From: Antonia Masucci <[email-masked]>
Date: Mon, 3 Feb 2014 18:54:20 +0100 (CET)

Dear all, 

I send you here some additional definitions that you could take into account in the Network Coding Taxonomy slides. I took them essentially in the surveys cited by Cedric in the email below. 

- FAMILY OF CODING OPERATIONS: 
Source Coding: compressing the information at the source to increase the efficiency in the transmission; 
Channel Coding: introducing redundant bits in the information sequence to make more reliable the communication; 
Network Coding: coding operation realized at payload-level to allow intermediate nodes to combine payloads before forward them. 
(reference [1] pag.1950) 

- In slide 6 "Payload-level Operations" additional definitions: 
Linear Coding ... 
Coding Vector ... 
Coding Matrix: The matrix of coding vectors needed for generating coded payloads from the originals ones.(ref.[2] pag.699) 
Vector Network Coding: the source multicasts information by transmitting vectors of a certain length, while intermediate nodes process and combine the incoming payloads by multiplying them with a 
coding matrix. (ref [6]) 
Random Linear Coding ... 
Non-Linear Coding: Payloads are coded by non-linear functions.(ref.[2] pag.699) 

- In slide 7 "Basics of Coding" additional definitions: 
Coding Field ... 
Coding Symbols ... 
Native Payload: Payload generated at source nodes. (ref.[2] pag.699) 
Coded Payload: Payload encoded at source and intermediate nodes. (ref.[2] pag.699) 
Coding Node: Intermediate node with multiple input links that codes payloads.(ref.[2] pag.699) 

- In slide 10 "Routing and Forwarding" additional definitions: 
Single-Path Route ... 
Multi-path Route ... 
Subgraph ... 
Forwarding ... 
Store-Carry-Forward: a node which receives a payload store it in its buffer, carrying it while moving, and forwards it when encounters other nodes. (ref.[2] pag.709) 
Throughput benefit of Network Coding w.r.t. Routing: Ratio between the achievable rate of network coding and the one of routing. (ref.[2] pag. 702) 

- ROBUSTNESS 
Coding techniques to improve reliability in communication: 
Network Error Correcting Code: method correcting errors in network communications by extending the classical error-correcting codes from a point-to-point model to networks. (ref.[3]) 
Network Erasure Correcting Codes:method using spatial redundancy of network coding to recover lost payloads. (ref.[4]) 

- COHERENT/NONCOHERENT NETWORK CODING (ref [2] pag.708) 
Coherent Network Coding: Source and destination nodes knows network topology and coding operations at intermediate nodes. 
Noncoherent Network Coding: Source and destination nodes do not know network topology and coding operations. In this case, random network coding can be applied. 

- Convolutional Network Coding: alternative solution to classical block network coding for cyclic networks where the results of propagation and coding of sequential payloads are similar to convolutional coding. (ref [5]) 
Achievable Coding Rate Region: region represented by the points of the space in which it is achievable an arbitrarily small decoding error probability with block codes. (ref [1] pag.1952) 
. 

- Network Coding Intra-Layer: Network Coding is performed within each layer. (ref[5] pag 705) 
Network Coding Inter-Layer: Network Coding is performed across layers. (ref[5] pag 705) 

- NC-aware routing (inter-flow or inter-session coding) protocols: (ref [7] pag.1963) 
COPE, ROCK, MMR, LPF, COAR, ANCHOR, CAMP, RCR, OCR, ICM, NCAR, DCAR, NJCAR, BRONC, CORMEN, CORE, OCAR 

- NC-based routing (intra-flow or intra-session coding) protocols: (ref [7] pag.1960) 
MORE, NC_RMR, CCACK, PipelineOR, OMNC 

- Following techniques can be found for instance in COPE: (ref [7] pag 1961) 
Opportunistic Listening:each node in promiscuous mode overhears the transmissions of its multiple neighboring nodes. 
Opportunistic Coding: transferring within a single transmission the maximum number of native payloads. 
Learning Neighbor State: a node lets other neighbors become aware of the payloads it currently contains. 

[1] R.Bassoli, H.Marques, J.Rodriguez, K.W.Shum and R.Tafazolli, "Network Conding Theory: A Survey," IEEE Communications Surveys & Tutorials, Volume 15, Issue 4, pp.1950 - 1978, 2013. 
[2] T.Matsuda, T.Noguchi and T.Takine, "Survey on Network Coding and its Applications", IEICE Transactions on Communication, Volume E94-B, No.3, pp.698-717, March 2011. 
[3] R.W.Yeung, and N.Cai, "Network error correction, part I: basic concepts and upper bounds," Communications in Information and Systems, Volume 6, No.1, pp. 19-36, 2006. 
[4] R.Koetter and M.Medard, "An algebraic approach to Network Coding," IEEE/ACM Transactions on Networking, Volume 11, No.5, pp.782-795, October 2003. 
[5] E. Erez and M. Feder, “Convolutional network codes,” IEEE International Symposium on Information Theory 2004, Chicago, IL, Jun. 27–Jul. 2, 2004. 
[6] B.J.Ebrahimi and C. Fragouli,"Vector network coding algorithms," IEEE International Symposium on Information Theory (ISIT) 2010, page 2408-2412, Austin, Texas, U.S.A., June 13 - 18, 2010. 
[7] Iqbal, Muhammad Azhar, Dai, Bin, Huang, Benxiong, Hassan, A. and Yu, S. 2011, "Survey of network coding-aware routing protocols in wireless networks", Journal of network and computer applications, Volume 34, 
No.6, pp.1956-1970, 2011. 
[8] A.G.Dimakis, K.Ramchandran, Y.Wu, and C.Suh, "A Survey on Network Codes for Distributed Storage", Proceedings of the IEEE, Volume 99, No.3, March 2011. 

Best regards, 
Antonia Masucci 

From: Cedric Adjih < cedric.adjih at inria.fr > 
To: nwcrg at irtf.org 
Sent: Thu, 7 Nov 2013 18:00:35 +0100 (CET) 
Subject: Re:[nwcrg] NWCRG agenda and presentations for tomorrow's meeting 

Dear all,

  Here is a few comments on the charter (sorry for the late reaction),
as it will be one main topic of discussion for the NWCRG:

. The charter ( http://trac.tools.ietf.org/group/irtf/trac/wiki/nwcrg ) proposes to 
  - collect information on wiki page, related to NWC architecture
  - creating a document with taxonomy [of terminology, of applications]
and one candidate activity is: 
  - research architectures for network coding protocols.

  I like this approach where the first step is to collect information:
and also wonder if the plan is to recharter the group later
with additional items (sorry for not being so familiar with IETF/IRTF process) ?

  Also maybe it would be nice to already have a strategy about how to collect 
and structure all the information that would be summarised on the wiki
pages and in the taxonomy document ?
I tried to think how, but the huge amount of network coding publications
(for instance, 700+ listed on http://www.networkcoding.info/bibliography.php , 
 5000+ citations of "Network Information Flow" Ahlswede et al. 2000)
is a bit intimidating :). There are several books, and even surveys for
applications of network coding in specific areas (for instance [1-5]).

I guess there are many angles of how to approach network coding:
- why use NC ?
  . improved capacity/throughput, reliability, coupon collector problem, energy-efficiency, 
    FEC, . . .
- where to use NC ? 
  . use cases: MANET, video on demand, reliable TCP, CCN/ICN, DTN, ...
    (as also in the list of Marie-Jose' Montpetit, and the ones from Muriel Medard post)
- how to use NC ? 
  . architectures [for instance end-to-end Tetrys/Coded-TCP, or ICN/CCN, or wireless NC routing, ...] 
  . ... based on building blocks (RLC, AL-FEC, sliding windows, congestion control, subgraph
    selection, NC theory, ...) 
and other angles (and these are already in the charter in the part "NWCRG Interest Areas").

But do you think these could be used to structure the wiki information ?
And practically, how would people contribute ? :)

++ a few surveys

[1] Takahiro MATSUDA, Taku NOGUCHI, Tetsuya TAKINE, "Survey of Network Coding and Its Applications", IEICE TRANSACTIONS on Communications, Vol.E94-B, No.3, pp.698-717.
[2] Iqbal, Muhammad Azhar, Dai, Bin, Huang, Benxiong, Hassan, A. and Yu, S. 2011, "Survey of network coding-aware routing protocols in wireless networks", Journal of network and computer applications, vol. 34, no. 6, pp. 1956-1970.
[3] Alexandros G. Dimakis, Kannan Ramchandran, Yunnan Wu, and Changho Suh, "A Survey on Network Codes for Distributed Storage", Proceedings of the IEEE | Vol. 99, No. 3, March 2011.
[4] Riccardo Bassoli, Hugo Marques, Jonathan Rodriguez, Kenneth W. Shum and Rahim Tafazolli, "Network Coding Theory: A Survey", IEEE Communications Surveys & Tutorial, Issue 99, 
[5] Michele Sanna and Ebroul Izquierdo "A Survey of Linear Network Coding and Network Error Correction Code Constructions and Algorithms", International Journal of Digital Multimedia Broadcasting 2011.

Regards,
-- Cedric

----- Original Message -----
From: "Victor Firoiu (US SSA)" <victor.firoiu at baesystems.com>
To: nwcrg at irtf.org
Sent: Thursday, November 7, 2013 3:37:08 AM
Subject: [nwcrg] NWCRG agenda and presentations for tomorrow's meeting

Dear NetCoders, 

We uploaded an updated Agenda and all your presentations at https://datatracker.ietf.org/meeting/88/materials.html (look for the NWCRG section). 

Our meeting will be in the Plaza C room at 1pm. Please arrive early so we can start on time and be able to go through all items we scheduled, including discussing and approving our Charter. 

If we find that we need more time for discussion, especially on Taxonomy and Architecture, we have the Constable room reserved until 5:20pm. 

See you all tomorrow, 

Victor Firoiu and Brian Adamson

---

From: Victor Firoiu <[email-masked]>
Date: Tue, 4 Feb 2014 14:17:14 -0500

Antonia,

Thank you very much for your inputs, they are very good potential
additions to our Taxonomy document. Let's see what other comments we
get.

I have a few comments and questions:
1. The definition of Vector Network Coding is not clear. Maybe rephrase?
2. Achievable Coding Rate Region: I'm not sure what you mean by
"points in space". Are you referring to an interval of rate values ?
3. Can you elaborate on the connection between NC-aware routing and
inter-flow coding, and NC-based routing and intra-flow coding?

Thanks again,
Victor

On Mon, Feb 3, 2014 at 12:54 PM, Antonia Masucci
<[email-masked]> wrote:
> Dear all,
>
> I send you here some additional definitions that you could take into account
> in the Network Coding Taxonomy slides. I took them essentially in the
> surveys cited by Cedric in the email below.
>
>
>   Network Coding: coding operation realized at payload-level to allow
> intermediate nodes to combine payloads before forward them.
>   (reference [1] pag.1950)
>
>
>   Coding Matrix: The matrix of coding vectors needed for generating coded
> payloads from the originals ones.(ref.[2] pag.699)
>   Vector Network Coding: the source multicasts information by transmitting
> vectors of a certain length, while intermediate nodes process and combine
> the incoming payloads by multiplying them with a
>   coding matrix. (ref [6])
>   Random Linear Coding ...
>   Store-Carry-Forward: a node which receives a payload store it in its
> buffer, carrying it while moving, and forwards it when encounters other
> nodes. (ref.[2] pag.709)
>   Throughput benefit of Network Coding w.r.t. Routing: Ratio between the
> achievable rate of network coding and the one of routing. (ref.[2] pag. 702)
>
>
> - ROBUSTNESS
>   Network Error Correcting Code: method correcting errors in network
> communications by extending the  classical error-correcting codes from a
> point-to-point model to networks. (ref.[3])
>   Network Erasure Correcting Codes:method using spatial redundancy of
> network coding to recover lost payloads. (ref.[4])
>
>
>   Coherent Network Coding: Source and destination nodes knows network
> topology and coding operations at intermediate nodes.
>   Noncoherent Network Coding: Source and destination nodes do not know
> network topology and coding operations. In this case, random network coding
> can be applied.
>
>
> - Convolutional Network Coding: alternative solution to classical block
> network coding for cyclic networks where the results of propagation and
> coding of sequential payloads are similar to convolutional coding. (ref [5])
>   Achievable Coding Rate Region: region represented by the points of the
> space in which it is achievable an arbitrarily small decoding error
> probability with block codes. (ref [1] pag.1952)
>      .
>
>   Opportunistic Listening:each node in promiscuous mode overhears the
> transmissions of its multiple neighboring nodes.
> [1] R.Bassoli, H.Marques, J.Rodriguez, K.W.Shum and R.Tafazolli, "Network
> Conding Theory: A Survey," IEEE Communications Surveys & Tutorials, Volume
> 15, Issue 4, pp.1950 - 1978, 2013.
> [2] T.Matsuda, T.Noguchi and T.Takine, "Survey on Network Coding and its
> Applications", IEICE Transactions on Communication, Volume E94-B, No.3,
> pp.698-717, March 2011.
> [3] R.W.Yeung, and N.Cai, "Network error correction, part I: basic concepts
> and upper bounds," Communications in Information and Systems, Volume 6,
> No.1, pp. 19-36, 2006.
> [4] R.Koetter and M.Medard, "An algebraic approach to Network Coding,"
> IEEE/ACM Transactions on Networking, Volume 11, No.5, pp.782-795, October
> 2003.
> [5] E. Erez and M. Feder, "Convolutional network codes," IEEE International
> Symposium on Information Theory 2004, Chicago, IL, Jun. 27-Jul. 2, 2004.
> [6] B.J.Ebrahimi and C. Fragouli,"Vector network coding algorithms," IEEE
> International Symposium on Information Theory (ISIT) 2010, page 2408-2412,
> Austin, Texas, U.S.A., June 13 - 18, 2010.
> [7] Iqbal, Muhammad Azhar, Dai, Bin, Huang, Benxiong, Hassan, A. and Yu, S.
> 2011, "Survey of network coding-aware routing protocols in wireless
> networks", Journal of network and computer applications, Volume 34,
> [8] A.G.Dimakis, K.Ramchandran, Y.Wu, and C.Suh, "A Survey on Network Codes
> for Distributed Storage", Proceedings of the IEEE, Volume 99, No.3, March
> 2011.
>
>
>
> Best regards,
> Antonia Masucci
>
>
>
>

---

From: Antonia Masucci <[email-masked]>
Date: Mon, 10 Feb 2014 10:44:44 +0100 (CET)

Dear all,

Here there are some corrections

Vector Network Coding: The source transmit vectors (whose elements are on a given field),
which are combined at intermediate nodes by using matrices instead of scalar coefficients.

Admissible Coding Rate region: region represented by the points which have rates as coordinates
in which it is achievable an arbitrarily small error probability with block codes.

NC-aware routing combines data packets from different flows
along routes with more coding opportunities further improves
network throughput.

NC-based routing deals with the coding of packets belonging to the
same flow and is also known as intra-flow or intra-session coding.

Thank you very much

Best,
Antonia

----- Mail original -----
> De: "Victor Firoiu" <[email-masked]>
> À: "Antonia Masucci" <[email-masked]>, [email-masked]
> Envoyé: Mardi 4 Février 2014 20:17:14
> Objet: Re: [nwcrg] Network Coding Taxonomy
> 
> Antonia,
> 
> >   Source Coding: compressing the information at the source to
> >   increase the
> > efficiency in the transmission;
> >   Channel Coding: introducing redundant bits in the information
> >   sequence to
> > make more reliable the communication;
> >   Non-Linear Coding: Payloads are coded by non-linear
> >   functions.(ref.[2]
> > pag.699)
> >
> >
> >   Coded Payload: Payload encoded at source and intermediate nodes.
> >   (ref.[2]
> > pag.699)
> >   Coding Node: Intermediate node with multiple input links that
> >   codes
> > payloads.(ref.[2] pag.699)
> >
> >
> > - Network Coding Intra-Layer: Network Coding is performed within
> > each layer.
> > (ref[5] pag 705)
> >   Network Coding Inter-Layer: Network Coding is performed across
> >   layers.
> > (ref[5] pag 705)
> >
> >
> > -  NC-aware routing (inter-flow or inter-session coding) protocols:
> > (ref [7]
> > pag.1963)
> >    COPE, ROCK, MMR, LPF, COAR, ANCHOR, CAMP, RCR, OCR, ICM, NCAR,
> >    DCAR,
> > NJCAR, BRONC, CORMEN, CORE, OCAR
> >
> >
> > -  NC-based routing (intra-flow or intra-session coding) protocols:
> > (ref [7]
> > pag.1960)
> > - Following techniques can be found for instance in COPE:  (ref [7]
> > pag
> > 1961)
> >   Opportunistic Coding: transferring within a single transmission
> >   the
> > maximum number of native payloads.
> >   Learning Neighbor State:  a node lets other neighbors become
> >   aware of the
> > payloads it currently contains.
> >
> >
> >
> >

---

From: "Senthil Sivakumar (ssenthil)" <[email-masked]>
Date: Tue, 11 Feb 2014 00:34:39 +0000

>along routes with more coding opportunities further improves

Are there any details on how routing is made aware of coded data packets?
Is that as simple as packets arriving from a specific source/interface are
coded packets 
Or more complex in that there is dynamic control information exchanged
prior to the arrival of the packets?

>same flow and is also known as intra-flow or intra-session coding.

Routing normally doesn¹t deal with flows, I am wondering what the
definition of a flow here
And how routing is made of the flow. Same question as above.

Thanks
Senthil

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

---

From: Frank Fitzek <[email-masked]>
Date: Tue, 11 Feb 2014 11:24:53 +0100

Dear all,
some views inline.

> prior to the arrival of the packets?
That is an intersting question. So far routing protocols are coding 
agnostic. In the wireless mesh arena there are different solutions a la 
AODV, OLSR, and BATMAN, but all of them are using a single route through 
the network (which is not using the full potential of NC). In one of the 
last BATTLEMESH events (meeting of implementers for wireless mesh 
networks), the potential of multi path solution has been discussed.

Another question is whether the coding should be applied across the full 
network or certain "hot spots". In our recent research we preferred to 
apply the coding in the hot spots to help to increase the throughput 
where it is needed.
> And how routing is made of the flow. Same question as above.
The definition of a flow is not end to end oriented anymore. As coding 
can be enabled at every node the definition per flow will also change.

---

From: Marie-Jose Montpetit <[email-masked]>
Date: Tue, 11 Feb 2014 07:06:57 -0500

More inline.
Marie-Jose Montpetit
[email-masked]
[email-masked]

On Feb 11, 2014, at 5:24 AM, Frank Fitzek <[email-masked]> wrote:

> That is an intersting question. So far routing protocols are coding agnostic. In the wireless mesh arena there are different solutions a la AODV, OLSR, and BATMAN, but all of them are using a single route through the network (which is not using the full potential of NC). In one of the last BATTLEMESH events (meeting of implementers for wireless mesh networks), the potential of multi path solution has been discussed.

Yes and this being a research group it maybe interesting to think about the combination of routing and coding for the future. Also could think of adding "coding" as another QoS level or being added to policy decisions.
> 
> Another question is whether the coding should be applied across the full network or certain "hot spots". In our recent research we preferred to apply the coding in the hot spots to help to increase the throughput where it is needed.

Well I guess then it depends who your customer is. You may not control the hotspots. 

> The definition of a flow is not end to end oriented anymore. As coding can be enabled at every node the definition per flow will also change.
We should agree on one definition and go from that.

/mjm

---

From: "Senthil Sivakumar (ssenthil)" <[email-masked]>
Date: Wed, 12 Feb 2014 01:31:14 +0000

>apply the coding in the hot spots to help to increase the throughput

[Senthil] I tend to agree that you want to have coding only on "hot spots".
I guess the question was how the nc aware routing would work in those "hot
spots".
What gets steered to these hot spots and what doesn't. May be this is all
still evolving,
But since the terminology is thrown out, we need to know what is and isnt
in scope for
NC aware routing, and what precisely it means.

>can be enabled at every node the definition per flow will also change.

But then how is NC based routing ties flows to routing decisions?

Thanks
Senthil