Network Coding Taxonomy
draft-irtf-nwcrg-network-coding-taxonomy-01

Abstract

This document summarizes a recommended terminology for Network Coding concepts and constructs. It provides a comprehensive set of terms with unique names 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 May 4, 2017.

Copyright Notice

Copyright (c) 2016 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
• 1.1. Requirements Language
• 2. Channel and Coding Types
• 3. Basics of Finite Fields
• 4. Payload-level Operations
• 5. Coding Methods
• 6. Payload-level Operations in Block Coding Method
• 7. Node-local Processing in Block Coding Method
• 8. Node-local Processing in Sliding Window Coding Method
• 9. Network Coding Transport
• 10. Routing and Forwarding
• 11. Acknowledgements
• 12. IANA Considerations
• 13. Security Considerations
• 14. References
• 14.1. Normative References
• 14.2. Informative References
• Authors' Addresses

1. Introduction

The literature on Network Coding research and system design has a large set of concepts and contructs with origins in several research fields including Coding and Information Theory, Data Networks and Storage. In many cases, same or similar concepts have received multiple names, or the same name may be used for different concepts in different contexts. This document attempts to collect a comprehensive set of concepts and constructs, and for each, provide a concise definition along with a unique name that is most used and most descriptive. This terminology will help avoid ambiguities in future Network Coding IRTF and 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. Channel and Coding Types

Packet Erasure Channel

A communication path where packets are either dropped (e.g., by a congested router, or because the number of transmission errors exceeds the correction capabilities of the physical layer codes) or received. When a packet is received, it is assumed that this packet is not corrupted.

Packet Error Channel

A communication path where packets are potentially subject to bit corruptions (that may not be corrected by the physical layer codes).

Source Coding

Compressing the information at the source (i.e., within the application) to improve transmission efficiency (NB: this aspect is mostly out of scope).

Channel Coding

Introducing redundant information in the transmission stream to increase transmission robustness. This

End-to-End Coding

Coding operation realized at payload level and performed at the source or in a middlebox, without re-coding operation at intermediate nodes. Similarly, decoding is performed at the destination(s) or in a middlebox. This is the approach used in the ALC [RFC5775], NORM [RFC5740] and FECFRAME [RFC6363] protocols.

Network Coding

Coding operation realized at payload level and performed at the source as well as possibly at some intermediate nodes. This coding strategy can result in more efficient and more reliable communication.

Error Correcting (Network) Codes

Codes (resp. network codes) for the Packet Error Channel.

Erasure Correcting (Network) Codes, A.K.A. Forward Erasure Codes (FEC)

Codes (resp. network codes) for the Packet Erasure Channel.

3. Basics of Finite Fields

Coding Field

A pre-defined finite field used in a Network Coding algorithm or protocol. Coding fields have the desired property of having all elements invertible for + and * and all operations over any elements do not result in overflow/ underflow. Examples of finite fields are Galois fields, including prime fields {0..p^m-1}, where p is prime. Most used fields are binary fields {0..2^m-1}, where m equals 1, 4 or 8 for practical reasons.

(Coding) Field size

The number of elements in a field. For example the binary field {0..2^m-1} has size q=2^m.

(Coding) Elements

Elements of a pre-defined coding field. [RFC5510], section 8.4, details the relationships between source and repair symbols and elements of the finite field.

4. Payload-level Operations

Original (Uncoded) Payload, A.K.A. (IETF) Source Symbol

A set of application-level data with defined byte sequence bounds, generated at the source of a flow. Original payloads are inputs to coding operations.

Coded Payload, A.K.A. (IETF) Repair Symbol

The result of a coding operation applied to original or coded payloads.

Linear Coding

Linear combination of a set of payloads using a given set of coefficients resulting in a coded payload. Payloads are divided in elements over a Coding Field. Elements at a given position from each payload are linearly combined. Resulting coded elements are assembled in a coded payload, respecting the original in-payload order. All linear combinations on any element position use the same given set of coefficients. The input payloads may be original (not coded) or coded. [COMMENT: Suggestion is to have a terse definition here and refer to a later section that will have more explanation of the algorithm and some diagrams.]

Non-linear Coding

Combining a set of payloads using non-linear functions.

(Coding) Coefficient

A coding element used as a coefficien t in linear coding of payloads.

Coding Vector

A set of coding elements representing coefficients needed for generating a given coded payload through linear coding of original (non-coded) payloads.

Coding (or Generator) Matrix (of a set of coded payloads)

A matrix G that transforms the set of source (uncoded) symbols X into a set of coded payloads Y = X * G.

Density of a coding vector

Number of non-zero coefficents in the coding vector.

Random Linear Coding

Linear coding using a set of random elements as coefficients.

5. Coding Methods

Block coding

Original payload sequence is divided in blocks, and coding is performed only over payloads within a block.

Sliding Window coding

Given a stream of uncoded payloads, coding blocks are selected based on a sliding window. Coding blocks may be partially overlapping, and, over time, moving to higher original payload sequence numbers.

Elastic Sliding Window coding

Sliding Window Coding with an encoding window of variable size over the time. For instance this size may depend on acknowledgments sent by the receiver(s) for a particular original payload (received, decoded, or decodable).

Convolutional network coding

Coding that relies on a sliding encoding window, of fixed or elastic size. Convolutional coding is an alternative solution to block coding.

Coding node

Node performing coding operations.

6. Payload-level Operations in Block Coding Method

[COMMENT: Below definitions are very far from those used in RMT/FECFRAME. Need to decide how to harmonize.

(Coding) Block a.k.a. Generation

A set of (usually consecutive) original (uncoded) payloads defined by the sender-side of an NC transport protocol. Coding is only performed over payloads belonging to the same block. Payloads resulting from coding over payloads of a block, also belong to the same block.

(Coding) Block size a.k.a. Code dimension

The number k of original payloads belonging to a coding block

Code rate

The ratio k/n between the number of source symbols k and the number of encoding symbols n. 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.

(Coded) Payload Set

A set of payloads belonging to the same block, usually received at a node.

Rank of a Payload Set

The number of linearly independent members of a Payload Set received at a node. Also known as "Degrees of Freedom". [COMMENT: May need to revise and refer to an associated linear system.]

Full Rank

The condition that a Payload Set received at a node has rank equal to the block's size. A Payload Set can be fully decoded into original packets iff it has full rank.

Partial Rank

Any rank that is less than full rank and not zero.

7. Node-local Processing in Block Coding Method

[COMMENT: None of the definitions below are defined in RMT/FECFRAME whereas block FEC codes were used. Need to decide how to harmonize.]

NACK

A message from a node that the linear system associated to the received Payload Set does not have full rank, and additional source or repair symbol(s) is(are) needed.

Range Space of a Payload Set

The linear space defined by the coding vectors of a Payload Set.

Null Space

The linear space that represents the complement of the Range Space of a Payload Set.

Null Space Sample

A coding vector that is included in the Null Space.

Solvable Payload Set

The set of original payloads that can be decoded from a given set of coded payloads.

8. Node-local Processing in Sliding Window Coding Method

Payload Indices

The original payloads are numbered with indices 1,2, . . . N [COMMENT: wrong definition.]

Sliding (encoding) window

[Sun08] [Lac08] A set of consecutive indices of original payloads: a node generates coded payloads that are linear combinations of original payloads with indices in its current sliding window.

Sliding window size

[Lin10] [Cho08] [Sun09] The number of consecutive payload indices of the window.

Seen payload (original payload seen at a receiver)

[Sun08] [Sun09] [Lin10] [Bao12] An original payload is “seen”, when the receiver can compute a linear combination with this payload and original payloads with only higher indices. Otherwise the payload is unseen.

Sensed payload (original payload sensed at a receiver)

[Bao12] At a receiver, an original payload is “sensed” when it is present in at least in one of the received coded payloads. Otherwise it is unsensed.

Lowest/ highest index of coded payloads

[Cho08] The minimum (resp. maximum) index of original payloads involved in a coded payload.

9. Network Coding Transport

Coherent Network Coding

Source and destination nodes know network topology and coding operations at intermediate nodes. [COMMENT: Need to clairify what "know" means.]

Noncoherent Network Coding

Source and destination nodes do not know network topology and intermediate coding operations. In this case, random network coding can be applied.

Flow

A stream of packets logically grouped from the network coding perspective. These packets may come from the same application (in that case they are identified by the five-tuple: source and destination IP address, transport protocol ID, and source and destination port of the transport protocol), or come from the same source host (in which case they are identified by the 3-tuple source and destination IP address, Type of Service (TOS) or Diffserv code point (DSCP)). This distinction depends on the use-case where network coding is applied.

Intra-flow coding

Network coding over payloads belonging to the same flow.

Inter-flow coding

Network coding over payloads belonging to multiple flows.

End-to-end coding

Transport stream is coded and decoded at end-points.

Intermediate coding

Packet coding can occur at endpoints and any intermediate nodes on the route.

Coding node

Node performing coding operations.

Forwarding factor

The rate of transmission from a node relative to the rate of information received at the same node.

10. Routing and Forwarding

Single-Path route

A route that has a single path from source to destination(s). In case of multicast, this is a tree.

Multi-Path route

A route containing multiple disjoint paths from source to a destination.

Subgraph

A generalized multi-path route from a sender to one or multiple receivers where paths can intersect and diverge any number of times.

Forwarding

The process of conveying a flow from the current node or previous hop(s) to the next hop(s) along single- or multi-path routes. Coding operations may be performed during the forwarding process when network coding is applied within intermediate nodes.

11. Acknowledgements

This document is based on inputs from Brian Adamson, Cedric Adjih, Josu Bilbao, Victor Firoiu, Frank Fitzek, Antonia Masucci, Marie-Jose Montpetit, Vincent Roca, Senthil Sivakumar, and other participants of the Network Coding Research Group.

12. IANA Considerations

This memo includes no request to IANA.

13. Security Considerations

This memo includes no Network Coding - specific security definitions yet.

14. References

14.1. Normative References

14.2. Informative References

Authors' Addresses