NWCRG V. Roca, Ed.
Internet-Draft INRIA
Intended status: Informational V. Firoiu, Ed.
Expires: September 11, 2017 BAE Systems
March 10, 2017

Network Coding Taxonomy


This document summarizes a recommended terminology for Network Coding concepts and constructs. It provides a comprehensive set of terms in order to avoid ambiguities in future Network Coding IRTF and IETF documents. This document is intended to be in-line with the terminology used by the RFCs produced by the Reliable Multicast Transport (RMT) and FEC Framework (FECFRAME) IETF working groups.

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at http://datatracker.ietf.org/drafts/current/.

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."

This Internet-Draft will expire on September 11, 2017.

Copyright Notice

Copyright (c) 2017 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Table of Contents

1. Introduction

The literature on Network Coding research and system design, IETF included, led to a rich set of concepts and constructs. This document collects terminology used in the domain, both outside and inside IETF, provides concise definitions, and introduces a high level taxonomy. Its primary goal is to be useful to IETF and IRTF activities. It is also intended to be in-line with the terminology already used by the RFCs produced by the Reliable Multicast Transport (RMT) and FEC Framework (FECFRAME) IETF working groups, in particular [RFC5052] [RFC6726] [RFC5775] [RFC5740] [RFC6363].

This document only focuses on packet transmissions and packet losses, for instance because of congested routers, routing issues, intermittent connectivity (e.g., a mobile terminal can suddenly go behind an obstacle) and wireless communication issues. Communications may happen in various types of networks, physical links, UDP services, overlay networks or even virtual networks. The notion of packet itself is multiform, depending on the target use-case and the way network layer is applied (e.g., in which layer of the protocol stack). For instance, a packet may be a UDP datagram because coding happens within a dedicated transport protocol on top of UDP.

This document does not try to achieve exhaustiveness. It is voluntarily kept as simple as possible.

This document does not consider physical layer transmission issues, nor physical layer coding/codes, nor error detection: if low layer error codes detect but fail to correct bit errors, or if an upper layer checksum (IP or UDP for instance) identify a corrupted packet, then this packet is supposed to be dropped.

This document IS NOT restricted to constructs that perform re-coding within intermediate coding forwarding nodes. If network coding (i.e., re-coding within the network) is in scope, this document has a broader scope.

In the following definitions, the "(IETF)" tag indicates that the associated term is already used in IETF documents.

1.1. Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].

2. General definitions and concepts

This section gathers general definitions and concepts that are used throughout this document.

Packet Erasure Channel:
A communication path where packets are either dropped or received without any error. This type of packet drop is referred to as an "erasure" or "loss". The term "channel" must be understood as a generic term for any type of communication facility. The "Erasure" channels are opposed to "Error" channels that are out of scope.
Erasure Correcting Code (ECC), or (IETF) Forward Erasure Code (FEC):
A code for the Packet Erasure Channel (only). These codes are also called "Application-Level FEC" to highlight that they have been designed to be used within the higher layers of the protocol stack, to protect against packet losses. These codes are opposed to "Error" correction codes that address errors and are out of scope.
Original Payload, or Uncoded Payload, or Systematic Symbol, or (IETF) Source Symbol:
A unit of data originating from the source that is used as input to encoding operations. When there is a single source symbol per source packet, an Original Payload corresponds to a Source packet.
Coded Payload, Coded Symbol, or (IETF) Repair Symbol:
A unit of data that is the result of a coding operation, applied either to source symbols or (in case of recoding) source and/or repair symbols. When there is a single repair symbol per repair packet, a Coded Payload corresponds to a Repair Packet.
Input Symbol and Output Symbol:
A unit of data that is used as input to an encoding operation or that is generated as output of an encoding operation. At a re-coding node, Repair Symbols are also part of the Input Symbols. With Systematic Coding, Source Symbols are also part of the Output Symbols.
(IETF) Encoding Symbol:
A source or a repair symbol.
(IETF) Source Packet:
A packet originating from the source which contributes to one or more Source Symbols. For instance, an RTP packet as a whole can constitute a Source Symbol. In other situations (e.g, to address variable size packets) a single RTP packet may contribute to various Source Symbols.
(IETF) Repair Packet:
A packet containing one or more Repair Symbols.
        source packet
              | source packet to source symbols transform
              | (one or more symbols per packet)
        source symbols
              v input symbols
   |     FEC encoding     | 
      | output symbols |
      v                v
source symbols   repair symbols
      |                |
      |                | symbol to packet transform
      |                | (one or more symbols per packet)
      v                v
source packet    repair packet

Figure 1: Packet and symbol relationships at a Coding Node.

Figure 1 illustrates the relationships between packets (what is sent in the Packet Erasure Channel) and symbols (what is manipulated during encoding and decoding operations) in case of FEC encoding, at a Coding Node. A similar figure could be done for FEC decoding.

Source node:
A node that generates one or more Source Flows.
Coding node:
A node that performs FEC encoding operations. It may be an end-host, a middlebox, or a forwarding node.
(IETF) Flow:
A stream of packets logically grouped.
(IETF) Source flow:
A flow coming from an application on a given host, and to which FEC encoding is to be applied, potentially along with other source flows. Depending on the use case, source flows may come from the same application, from different applications on the same host, or from different applications on different hosts.
(IETF) Repair flow:
A flow containing Repair Symbols, after FEC encoding.

3. Taxonomy of Code Uses

raw data flow from camera      ^                video flow display
            |                  |                        ^
            v                  | upper                  |
+-----------------------+      |            +-----------------------+
|     source coding     |      | applica-   |  source (de)coding    |
| (eg. mpeg compression)|      | tion       |(eg. mpg decompression)|
+-----------------------+      v            +-----------------------+
            |                                           ^
            v                                           |
+-----------------------+      ^            +-----------------------+
| network/AL-FEC coding |      | middle-    | network/AL-FEC coding |
|  (eg. RLC encoding)   |      | ware       |  (eg. RLC decoding)   |
+-----------------------+      v            +-----------------------+
            |                                           ^
            v                                           |
+-----------------------+      ^            +-----------------------+
|     packetization     |      |            |    depacketization    |
|     (eg. UDP/IP)      |      | communi-   |     (eg. UDP/IP)      |
+-----------------------+      | cation     +-----------------------+
            |                  |                        ^
            v                  | layers                 |
+-----------------------+      |            +-----------------------+
|       PHY layer       |      |            |       PHY layer       |
|    (channel coding)   |      |            |   (channel decoding)  |
+-----------------------+      v            +-----------------------+
            |                                           ^
            |          source + repair traffic          |

Figure 2: Example of end-to-end flow manipulation with Network Coding between the application and UDP layers (as with RMT or FECFRAME architectures). Other architectures are possible, for instance with network coding below the transport layer in order to allow re-coding within the network.

This section discusses the various ways of using coding, without going into coding details.

Source Coding versus Channel Coding:
(see Fig. Figure 2) When both terms are opposed, "Source Coding" usually refers to compression techniques (e.g., audio and video compression) within the upper application that generates the source flow. On the opposite, "Channel Coding" refers to FEC encoding in order to improve transmission robustness, initially within the lower physical layer, potentially also encompassing the upper layers. These terms should not be confused with respectively "FEC coding within the Source Node" and "FEC re-coding within an intermediate Coding Node".
End-to-End Coding:
A system where coding is performed at the source or (coding) middlebox, and decoding at the destination(s) or (decoding) middlebox. There is no re-coding operation at intermediate nodes. This is the approach followed in the FLUTE/ALC [RFC6726][RFC5775], NORM [RFC5740] and FECFRAME [RFC6363] protocols.
Network Coding:
A system where coding can be performed at the source as well as at intermediate forwarding nodes (all or a subset of them). End-to-End Coding can be regarded as a special case of Network Coding. Depending on the use case, additional assumptions can be made: for instance the knowledge by the destination of the coding node topology and coding operations can help during decoding operations.
Intra-Flow Coding, or Single Source Network Coding:
Process where incoming packets to the Coding Node belong to the same flow.
Inter-Flow Coding, or Multi-Source Network Coding:
Process where incoming packets to the Coding Node belong to different flows.
Single-Path Coding:
Network Coding over a route that has a single path from the source to each destination(s). In case of multicast or broadcast traffic, this route is a tree. Coding may be done end-to-end and/or at intermediate forwarding nodes.
Multi-Path Coding:
Network Coding over a route that has multiple (at least partially) disjoint paths from the source to each given destination. Coding may be done end-to-end and/or at intermediate forwarding nodes.

4. Coding Details

4.1. Coding Types

This section provides a high level taxonomy of coding techniques, . Technical details are left for the following sections.

Linear Coding:
Linear combination of a set of input symbols (i.e., source and/or repair symbols) using a given set of coefficients and resulting in a Repair Symbol. Many linear codes exist that differ from the way coding coefficients are drawn from a Finite Field of a given size.
Random Linear Coding (RLC):
Particular case of Linear Coding using a set of random coding coefficients.
Adaptive Linear Coding:
Linear Coding that utilizes cross layer adaptation. For instance, an adaptive coding scheme may adapt the generation and transmission of Repair Packets according to the channel variations over time, accounting for the predictive loss of degrees of freedom due to erasures.
Block Coding:
Coding technique where the input Flow(s) must be first segmented into a sequence of blocks, FEC encoding and decoding being performed independently on a per-block basis. The term "Chunk Coding" is sometimes used, where a "Chunk" denotes a block.
Sliding Window Coding, or Convolutional Coding:
General class of coding techniques that rely on a sliding encoding window. Convolutional Coding is an alternative solution to Block Coding.
Fixed or Elastic Sliding Window Coding:
Coding technique that generates repair symbol(s) on-the-fly, from the set of source symbols present in the sliding encoding window at that time, usually by using Linear Coding. The sliding window may be either of fixed size or of variable size over the time (also known as "elastic sliding window"). For instance this size may depend on acknowledgments sent by the receiver(s) for a particular source symbol or source packet (received, decoded, or decodable).
Systematic Coding:
A coding technique where Source Symbols are part of the output flow generated by a Coding Node.
Rateless and non-rateless Coding:
Rateless coding can potentially generate an infinite number of Repair Symbols (in practice this number is extremely large) from a given set of Source Symbols (meaning that their code rate is null). RLC codes are an example of rateless codes. Non-rateless Coding usually have a predefined maximum number of Repair Symbols that can be generated from a given set of Source Symbols.

4.2. Coding Basics

This section discusses and defines low level coding aspects.

Code Rate:
In case of a Block Code, the Code Rate is the k/n ratio between the number of Source Symbols, k, and the number of Source plus Repair Symbols, n. With a convolutional code, the code rate is defined similarly over a certain time interval (in case it evolves dynamically). By definition, the code rate is such that: 0 < code rate ≤ 1. A code rate close to 1 indicates that a small number of repair symbols have been produced during the encoding process and vice-versa.
(En)coding Window:
A set of Source (and Repair in the case of re-coding) Symbols used as input to the coding operations. The set of symbols will typically change over the time, as the Coding Window slides over the input Flow(s).
(En)coding Window Size:
The number of Source (and Repair in case of re-coding) Symbols in the current Encoding Window. This size may change over the time.
Payload Set:
The set of Source and Repair Symbols available (i.e., received or previously decoded) at the receiver and used during FEC decoding operations.
Decoding window:
The set of Source Symbols (only) that are considered in the current linear system of a receiver, independently of the fact these Source Symbols have been received, decoded, or lost. The Decoding Window will typically change over the time, as transmissions and decoding progress, and may be different for different receivers of a session where content is multicast or broadcast.
Decoding Window Size:
The number of Source Symbols (only) in the current Decoding Window. This size may change over the time.
Rank of a Payload Set, or (IETF) Rank of the Linear System:
At a receiver, number of linearly independent members of a Payload Set, or equivalently the number of linearly independent equations of the linear system. It is also known as "Degrees of Freedom". The system may be of "full rank" and decoding is possible, or "partial rank", and only partial decoding is possible.
Seen Payload, or Seen Symbol:
A Source Symbol is Seen when the receiver can compute a linear combination with this symbol and Source Symbols that are strictly more recent (i.e., with logically higher Encoding Symbol Identifiers). Otherwise the Source Symbol is considered as "unseen".
Generation, or (IETF) Block:
With Block Codes, the set of Source Symbols of the input Flow(s) that are logically grouped into a block, before doing encoding.
Generation Size, or Code Dimension, or (IETF) Block Size:
With Block Codes, the number k of Source Symbols belonging to a Block.
Coding Matrix, or Generator Matrix:
A matrix G that transforms the set of Input Symbols X into a set of Repair Symbols: Y = X * G. Defining a Generator Matrix is usual with Block Codes. The set of Input Symbols X can consist only of Source Symbols (e.g., with End-to-End Coding) or Source and Repair Symbols (e.g., with re-coding in an intermediate node).
Coding Coefficient:
With Linear Coding, this is a coefficient in a certain Finite Field. This coefficient may be chosen in different ways: randomly, or in a pre-defined table, or using a pre-defined algorithm plus a seed.
Coding Vector:
A set of Coding Coefficients used to generate a certain Repair Symbol through Linear Coding. The number of nonzero coefficients in the Coding Vector defines its density.
Finite Field, or Galois Field, or Coding Field:
Finite fields, used in Linear Codes, have the desired property of having all elements (except zero) invertible for + and * and all operations over any elements do not result in an overflow or underflow. Examples of Finite Fields are prime fields {0..p^m-1}, where p is prime. Most used fields use p=2 and are called binary extension fields {0..2^m-1}, where m often equals 1, 4 or 8 for practical reasons.
Finite Field size Coding Field size:
The number of elements in a finite field. For example the binary extension field {0..2^m-1} has size q=2^m.
Feedback information sent by a decoding node to a Coding Node (or from a receiver to a source in case of End-to-End Coding). The nature of information contained in a feedback packet varies, depending on the use-case. It can provide reception and/or FEC decoding statistics, or available Source Packets received and/or decoded (acknowledgement), or lost Source Packets that should be retransmitted (negative acknowledgement), or a number of additional Repair Symbols needed to have a Full Rank Linear System.

4.3. Coding In Practice

This section discusses practical aspects. Indeed, a practical solution must specify the exact manner encoding and decoding is performed but also all the peripheral aspects, for instance how an encoder informs a decoder about the parameters used to generate a certain Repair Packet (signalling).

(IETF) FEC Scheme:
A specification that defines the additional protocol aspects required to use a particular FEC code. In particular the FEC Scheme defines in band (e.g., in source and repair packet header or trailers) and out of band (e.g., in SDP description) signalling needed to synchronize encoders and decoders.
Payload Indices, or (IETF) Encoding Symbol Identifiers (ESI):
An identifier of a Source or Repair Symbol. If conceptually, each symbol is identified by a unique ESI value, in practice, with a continuous flow and a limited field size to hold the ESI, wrapping to zero in unavoidable and the same integer value will be re-used several times.
(IETF) FEC Payload ID:
Information that identifies the contents of a packet with respect to the FEC scheme. The FEC Payload ID of a packet containing Source Symbol(s) is usually different from that of a packet containing Repair Symbol(s). An ESI is typically part of the FEC Payload ID.
Coding Vector and Encoding Window Signalling:
With Sliding Window Coding, the FEC Payload ID of a repair packet necessarily contains information needed and sufficient to identify the Coding Vector and Coding Window. This may consist of a full list of Coding Coefficients (that may be compressed or not), or a piece of information (e.g., a seed) that can be used to generate the list of Coding Coefficients thanks to a predefined algorithm known by encoders and decoders (e.g., a PRNG), or an ESI that points to a given entry in a Generator Matrix in case of a block code. It may also consist of the full list of ESI of symbols in the Coding Window (that may be compressed or not), or the ESI of the first Source Symbol along with their number (assuming there is no gap).

5. IANA Considerations

This document is not subject to IANA registration.

6. Security Considerations

This document introduces a recommended terminology for network coding and therefore does not contain any security consideration. This does not mean that network coding systems do not have any security implication.

7. References

7.1. Normative References

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997.

7.2. Informative References

[RFC5052] Watson, M., Luby, M. and L. Vicisano, "Forward Error Correction (FEC) Building Block", RFC 5052, DOI 10.17487/RFC5052, August 2007.
[RFC5740] Adamson, B., Bormann, C., Handley, M. and J. Macker, "NACK-Oriented Reliable Multicast (NORM) Transport Protocol", RFC 5740, DOI 10.17487/RFC5740, November 2009.
[RFC5775] Luby, M., Watson, M. and L. Vicisano, "Asynchronous Layered Coding (ALC) Protocol Instantiation", RFC 5775, DOI 10.17487/RFC5775, April 2010.
[RFC6363] Watson, M., Begen, A. and V. Roca, "Forward Error Correction (FEC) Framework", RFC 6363, DOI 10.17487/RFC6363, October 2011.
[RFC6726] Paila, T., Walsh, R., Luby, M., Roca, V. and R. Lehtonen, "FLUTE - File Delivery over Unidirectional Transport", RFC 6726, DOI 10.17487/RFC6726, November 2012.

Appendix A. Additional references

Additional references on network coding are available in the NWCRG research web site: https://irtf.org/nwcrg

Appendix B. Authors and Contributors

This document is the result of a collaborative work that involved may authors and contributors from the NWCRG IRTF research group. They are listed below in alphabetical order:

  • Brian Adamson
  • Cedric Adjih
  • Josu Bilbao
  • Victor Firoiu
  • Frank Fitzek
  • Samah A. M. Ghanem
  • Emmanuel Lochin
  • Antonia Masucci
  • Marie-Jose Montpetit
  • Morten V. Pedersen
  • Goiuri Peralta
  • Vincent Roca
  • Paresh Saxena
  • Senthil Sivakumar

Authors' Addresses

Vincent Roca (editor) INRIA 655, av. de l'Europe Inovallee; Montbonnot ST ISMIER cedex, 38334 France EMail: vincent.roca@inria.fr
Victor Firoiu (editor) BAE Systems Burlington, MA 01803 USA EMail: victor.firoiu@baesystems.com