Internet DRAFT - draft-firoiu-nwcrg-network-coding-taxonomy
draft-firoiu-nwcrg-network-coding-taxonomy
Internet Research Task Force V. Firoiu, Ed.
Internet-Draft BAE Systems
Intended status: Informational B. Adamson, Ed.
Expires: September 6, 2014 Naval Research Laboratory
V. Roca, Ed.
C. Adjih
INRIA
J. Bilbao
IK4-IKERLAN
F. Fitzek
Aalborg University
A. Masucci
INRIA
M. Montpetit
MIT
March 5, 2014
Network Coding Taxonomy
draft-firoiu-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 September 6, 2014.
Firoiu, et al. Expires September 6, 2014 [Page 1]
Internet-Draft Network Coding Taxonomy March 2014
Copyright Notice
Copyright (c) 2014 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 . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3
2. The context of coding strategies . . . . . . . . . . . . . . 3
3. Channel and error correction types . . . . . . . . . . . . . 3
4. Basics of Coding . . . . . . . . . . . . . . . . . . . . . . 3
5. Payload-level Operations . . . . . . . . . . . . . . . . . . 4
6. Network Coding Methods . . . . . . . . . . . . . . . . . . . 5
7. Payload-level Operations in Block Coding Method . . . . . . . 5
8. Node-local Processing in Block Coding Method . . . . . . . . 6
9. Node-local Processing in Sliding Window Coding Method . . . . 6
10. Network Coding Transport . . . . . . . . . . . . . . . . . . 7
11. Routing and Forwarding . . . . . . . . . . . . . . . . . . . 8
12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8
13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8
14. Security Considerations . . . . . . . . . . . . . . . . . . . 8
15. References . . . . . . . . . . . . . . . . . . . . . . . . . 8
15.1. Normative References . . . . . . . . . . . . . . . . . . 8
15.2. Informative References . . . . . . . . . . . . . . . . . 8
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9
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
Firoiu, et al. Expires September 6, 2014 [Page 2]
Internet-Draft Network Coding Taxonomy March 2014
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. The context of coding strategies
Source Coding Compressing the information at the source to increase
the transmission efficiency by reducing redundant information
[COMMENT: do we need this?]
Channel Coding Introducing redundant information in the transmission
stream to increase reliability of communication.
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.
3. Channel and error correction 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).
Network Error Correcting Code Method for correcting errors in
communication networks by extending the classical error-
correcting codes from a point-to-point model to networks.
Network Erasure Correcting Codes Method of using spatial redundancy
of network coding to recover lost payloads.
4. Basics of Coding
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/
Firoiu, et al. Expires September 6, 2014 [Page 3]
Internet-Draft Network Coding Taxonomy March 2014
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}.
(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.
5. Payload-level Operations
Original (Uncoded) Payload 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.
Alternative definition to Payload: Symbol A unit of data processed
by a Network Coding operation. [COMMENT: we need to decide
which to adopt or if we keep both]
Coded Payload 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.
Firoiu, et al. Expires September 6, 2014 [Page 4]
Internet-Draft Network Coding Taxonomy March 2014
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
6. Network 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 Window coding [Need definition]
Convolutional network coding Alternative solution to block network
coding for cyclic networks where the results of propagation
and coding of sequential payloads are similar to
convolutional coding. [COMMENT: need a better definition.]
Coding node Node performing coding operations.
7. Payload-level Operations in Block Coding Method
(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 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
Firoiu, et al. Expires September 6, 2014 [Page 5]
Internet-Draft Network Coding Taxonomy March 2014
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.
8. Node-local Processing in Block Coding Method
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.
9. Node-local Processing in Sliding Window Coding Method
Payload Indices The original payloads are numbered with indices 1,2,
. . . N
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
Firoiu, et al. Expires September 6, 2014 [Page 6]
Internet-Draft Network Coding Taxonomy March 2014
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.
10. 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.
Firoiu, et al. Expires September 6, 2014 [Page 7]
Internet-Draft Network Coding Taxonomy March 2014
11. 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.
12. 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.
13. IANA Considerations
This memo includes no request to IANA.
14. Security Considerations
This memo includes no Network Coding - specific security definitions
yet.
15. References
15.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
15.2. Informative References
[Bao12] Bao, W., Shah-Mansour, V., and V. Wong, ""TCP VON: Joint
congestion control and online network coding for wireless
networks." In IEEE Global Communications Conference
(GLOBECOM)", 2012.
Firoiu, et al. Expires September 6, 2014 [Page 8]
Internet-Draft Network Coding Taxonomy March 2014
[Cho08] Cho, S. and C. Adjih, ""Wireless Broadcast with Network
Coding: DRAGONCAST", Inria Research Report RR-6569", 2008.
[Lac08] Lacan, J. and E. Lochin, ""Rethinking reliability for
long-delay networks." In IEEE International Workshop on
Satellite and Space Communications.", 2008.
[Lin10] Lin, Y., Liang, B., and B. Li, ""SlideOR: Online
opportunistic network coding in wireless mesh networks."
In Proceedings of IEEE INFOCOM.", 2010.
[Sun08] Sundararajan, J., Shah, D., and M. Medard, ""ARQ for
network coding." In IEEE International Symposium on
Information Theory.", 2008.
[Sun09] Sundararajan, J., Devavrat, S., Medard, M., Mitzenmacher,
M., and J. Barros, ""Network coding meets TCP." In IEEE
INFOCOM 2009", 2009.
Authors' Addresses
Victor Firoiu (editor)
BAE Systems
Burlington, MA 01803
USA
Email: victor.firoiu@baesystems.com
Brian Adamson (editor)
Naval Research Laboratory
Washington, DC 20375
USA
Email: brian.adamson@nrl.navy.mil
Vincent Roca (editor)
INRIA
655, av. de l'Europe
Inovallee; Montbonnot
ST ISMIER cedex 38334
France
Email: vincent.roca@inria.fr
URI: http://planete.inrialpes.fr/people/roca/
Firoiu, et al. Expires September 6, 2014 [Page 9]
Internet-Draft Network Coding Taxonomy March 2014
Cedric Adjih
INRIA
France
Email: Cedric.Adjih@inria.fr
Josu Bilbao
IK4-IKERLAN
J. M. Arizmendiarrieta, 2
Arrasate-Mondragon, Gipuzkoa 20500
Spain
Email: jbilbao@ikerlan.es
Frank Fitzek
Aalborg University
Aalborg
Denmark
Email: ff@es.aau.dk
Antonia Masucci
INRIA
Rocquencourt - B.P. 105
Le Chesnay 78153
France
Email: antonia.masucci@inria.fr
Marie-Jose Montpetit
MIT
77 Massachusetts Avenue
Cambridge, Massachusetts 02138
USA
Email: mariejo@mit.edu
Firoiu, et al. Expires September 6, 2014 [Page 10]
