NWCRG B. Adamson
Internet-Draft NRL
Intended status: Informational C. Adjih
Expires: December 31, 2017 INRIA
J. Bilbao
Ikerlan
V. Firoiu
BAE Systems
F. Fitzek
TU Dresden
S. Ghanem
Independant
E. Lochin
ISAE - Supaero
A. Masucci
Orange
M-J. Montpetit
Independant
M. Pedersen
Aalborg University
G. Peralta
Ikerlan
V. Roca, Ed.
INRIA
P. Saxena
AnsuR Technologies
S. Sivakumar
Cisco
June 29, 2017
Network Coding Taxonomy
draft-irtf-nwcrg-network-coding-taxonomy-03
Abstract
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.
Adamson, et al. Expires December 31, 2017 [Page 1]
Internet-Draft Network Coding Taxonomy June 2017
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 December 31, 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 . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3
2. General definitions and concepts . . . . . . . . . . . . . . 4
3. Taxonomy of Code Uses . . . . . . . . . . . . . . . . . . . . 6
4. Coding Details . . . . . . . . . . . . . . . . . . . . . . . 8
4.1. Coding Types . . . . . . . . . . . . . . . . . . . . . . 8
4.2. Coding Basics . . . . . . . . . . . . . . . . . . . . . . 9
4.3. Coding In Practice . . . . . . . . . . . . . . . . . . . 11
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 12
6. Security Considerations . . . . . . . . . . . . . . . . . . . 12
7. References . . . . . . . . . . . . . . . . . . . . . . . . . 12
7.1. Normative References . . . . . . . . . . . . . . . . . . 12
7.2. Informative References . . . . . . . . . . . . . . . . . 13
Appendix A. Additional references . . . . . . . . . . . . . . . 13
Appendix B. Authors and Contributors . . . . . . . . . . . . . . 13
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13
Adamson, et al. Expires December 31, 2017 [Page 2]
Internet-Draft Network Coding Taxonomy June 2017
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 notion of network (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 be exhaustive: it is voluntarily kept
as simple as possible.
This document does not consider physical layer transmission issues,
nor physical layer codes, nor error detection: if low layer error
codes detect but fail to correct bit errors, or if an upper layer
checksum (e.g., within IP or UDP) identifies 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 of course considered, 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 keywords "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].
Adamson, et al. Expires December 31, 2017 [Page 3]
Internet-Draft Network Coding Taxonomy June 2017
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
Adamson, et al. Expires December 31, 2017 [Page 4]
Internet-Draft Network Coding Taxonomy June 2017
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.
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 packet
|
| source packet to source symbols transform
| (one or more symbols per packet)
v
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.
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 of Source Packets 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.
Adamson, et al. Expires December 31, 2017 [Page 5]
Internet-Draft Network Coding Taxonomy June 2017
(IETF) Repair flow: A flow containing Repair Packets, after FEC
encoding.
3. Taxonomy of Code Uses
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".
Adamson, et al. Expires December 31, 2017 [Page 6]
Internet-Draft Network Coding Taxonomy June 2017
raw data flow from camera ^ video flow display
| | ^
v | upper |
+-----------------------+ | +-----------------------+
| source coding | | applica- | source (de)coding |
|(e.g. mpeg compression)| | tion |(eg. mpg decompression)|
+-----------------------+ v +-----------------------+
| ^
v |
+-----------------------+ ^ +-----------------------+
| network/AL-FEC coding | | middle- | network/AL-FEC coding |
| (e.g. RLC encoding) | | ware | (e.g. RLC decoding) |
+-----------------------+ v +-----------------------+
| ^
v |
+-----------------------+ ^ +-----------------------+
| packetization | | | depacketization |
| (e.g. UDP/IP) | | communi- | (e.g. 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.
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
Adamson, et al. Expires December 31, 2017 [Page 7]
Internet-Draft Network Coding Taxonomy June 2017
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.
Adamson, et al. Expires December 31, 2017 [Page 8]
Internet-Draft Network Coding Taxonomy June 2017
Sliding Window Coding, or Convolutional Coding: General class of
coding techniques that rely on a sliding encoding window.
This 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 only 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 Sliding Window Code,
the Code Rate is defined similarly over a certain time
interval, since the Code Rate may change 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.
Adamson, et al. Expires December 31, 2017 [Page 9]
Internet-Draft Network Coding Taxonomy June 2017
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 rec
eiver, 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 can consist of 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.
Adamson, et al. Expires December 31, 2017 [Page 10]
Internet-Draft Network Coding Taxonomy June 2017
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, or 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: 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 the list of
available Source Packets received or decoded
(acknowledgement), or the list of 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 (signaling).
(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., information
contained in Source and Repair Packet header or trailers) and
out of band (e.g., information contained in an SDP
description) signaling needed to synchronize encoders and
decoders.
Payload Indices, or (IETF) Encoding Symbol Identifiers (ESI): An ide
ntifier of a Source or Repair Symbol. If conceptually, each
symbol is identified by a unique ESI value, in practice, with
Adamson, et al. Expires December 31, 2017 [Page 11]
Internet-Draft Network Coding Taxonomy June 2017
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). The FEC
Payload ID typically contains at least an ESI.
Coding Vector and Encoding Window Signaling: With Sliding Window
Codes, the FEC Payload ID of a Repair Packet contains
information needed and sufficient to identify the Coding
Vector and Coding Window. Concerning the Coding Vector, 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 Pseudo Random Number
Generator, or PRNG), or an ESI that points to a given entry
in a Generator Matrix in case of a Block Code. Concerning
the Coding Window, this may 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,
<http://www.rfc-editor.org/info/rfc2119>.
Adamson, et al. Expires December 31, 2017 [Page 12]
Internet-Draft Network Coding Taxonomy June 2017
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,
<http://www.rfc-editor.org/info/rfc5052>.
[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,
<http://www.rfc-editor.org/info/rfc5740>.
[RFC5775] Luby, M., Watson, M., and L. Vicisano, "Asynchronous
Layered Coding (ALC) Protocol Instantiation", RFC 5775,
DOI 10.17487/RFC5775, April 2010,
<http://www.rfc-editor.org/info/rfc5775>.
[RFC6363] Watson, M., Begen, A., and V. Roca, "Forward Error
Correction (FEC) Framework", RFC 6363,
DOI 10.17487/RFC6363, October 2011,
<http://www.rfc-editor.org/info/rfc6363>.
[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,
<http://www.rfc-editor.org/info/rfc6726>.
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 in this document.
Authors' Addresses
Brian Adamson
NRL
USA
Email: brian.adamson@nrl.navy.mil
Adamson, et al. Expires December 31, 2017 [Page 13]
Internet-Draft Network Coding Taxonomy June 2017
Cedric Adjih
INRIA
France
Email: cedric.adjih@inria.fr
Josu Bilbao
Ikerlan
Spain
Email: jbilbao@ikerlan.es
Victor Firoiu
BAE Systems
USA
Email: victor.firoiu@baesystems.com
Frank Fitzek
TU Dresden
Germany
Email: frank.fitzek@tu-dresden.de
Samah A. M. Ghanem
Independant
Email: samah.ghanem@gmail.com
Emmanuel Lochin
ISAE - Supaero
France
Email: emmanuel.lochin@isae-supaero.fr
Antonia Masucci
Orange
France
Adamson, et al. Expires December 31, 2017 [Page 14]
Internet-Draft Network Coding Taxonomy June 2017
Marie-Jose Montpetit
Independant
USA
Email: marie@mjmontpetit.com
Morten V. Pedersen
Aalborg University
Denmark
Email: mvp@es.aau.dk
Goiuri Peralta
Ikerlan
Spain
Email: gperalta@ikerlan.es
Vincent Roca (editor)
INRIA
France
Email: vincent.roca@inria.fr
Paresh Saxena
AnsuR Technologies
Norway
Email: paresh.saxena@ansur.es
Senthil Sivakumar
Cisco
USA
Email: ssenthil@cisco.com
Adamson, et al. Expires December 31, 2017 [Page 15]