Skip to main content

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

The information below is for an old version of the document.
Document Type
This is an older version of an Internet-Draft that was ultimately published as RFC 8406.
Authors Victor Firoiu , Brian Adamson , Vincent Roca , Cédric Adjih , Josu Bilbao , Frank Fitzek , Antonia Masucci , Marie-Jose Montpetit
Last updated 2016-10-31
RFC stream Internet Research Task Force (IRTF)
Formats
IETF conflict review conflict-review-irtf-nwcrg-network-coding-taxonomy, conflict-review-irtf-nwcrg-network-coding-taxonomy, conflict-review-irtf-nwcrg-network-coding-taxonomy, conflict-review-irtf-nwcrg-network-coding-taxonomy, conflict-review-irtf-nwcrg-network-coding-taxonomy, conflict-review-irtf-nwcrg-network-coding-taxonomy, conflict-review-irtf-nwcrg-network-coding-taxonomy, conflict-review-irtf-nwcrg-network-coding-taxonomy, conflict-review-irtf-nwcrg-network-coding-taxonomy
Additional resources Mailing list discussion
Stream IRTF state (None)
Consensus boilerplate Unknown
Document shepherd (None)
IESG IESG state Became RFC 8406 (Informational)
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-irtf-nwcrg-network-coding-taxonomy-01
Internet Research Task Force                              V. Firoiu, Ed.
Internet-Draft                                               BAE Systems
Intended status: Informational                           B. Adamson, Ed.
Expires: May 4, 2017                           Naval Research Laboratory
                                                            V. Roca, Ed.
                                                                C. Adjih
                                                                   INRIA
                                                               J. Bilbao
                                                             IK4-IKERLAN
                                                               F. Fitzek
                                                      Aalborg University
                                                              A. Masucci
                                                                   INRIA
                                                            M. Montpetit
                                                                     MIT
                                                        October 31, 2016

                        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.

Firoiu, et al.             Expires May 4, 2017                  [Page 1]
Internet-Draft           Network Coding Taxonomy            October 2016

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

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.

Firoiu, et al.             Expires May 4, 2017                  [Page 2]
Internet-Draft           Network Coding Taxonomy            October 2016

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.

Firoiu, et al.             Expires May 4, 2017                  [Page 3]
Internet-Draft           Network Coding Taxonomy            October 2016

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 ap
           plication-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.

Firoiu, et al.             Expires May 4, 2017                  [Page 4]
Internet-Draft           Network Coding Taxonomy            October 2016

   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.

Firoiu, et al.             Expires May 4, 2017                  [Page 5]
Internet-Draft           Network Coding Taxonomy            October 2016

   (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.

Firoiu, et al.             Expires May 4, 2017                  [Page 6]
Internet-Draft           Network Coding Taxonomy            October 2016

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.

Firoiu, et al.             Expires May 4, 2017                  [Page 7]
Internet-Draft           Network Coding Taxonomy            October 2016

   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.

Firoiu, et al.             Expires May 4, 2017                  [Page 8]
Internet-Draft           Network Coding Taxonomy            October 2016

13.  Security Considerations

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

14.  References

14.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>.

14.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.

   [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.

   [RFC5510]  Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo,
              "Reed-Solomon Forward Error Correction (FEC) Schemes",
              RFC 5510, DOI 10.17487/RFC5510, April 2009,
              <http://www.rfc-editor.org/info/rfc5510>.

   [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>.

Firoiu, et al.             Expires May 4, 2017                  [Page 9]
Internet-Draft           Network Coding Taxonomy            October 2016

   [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>.

   [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/

   Cedric Adjih
   INRIA
   France

   Email: Cedric.Adjih@inria.fr

Firoiu, et al.             Expires May 4, 2017                 [Page 10]
Internet-Draft           Network Coding Taxonomy            October 2016

   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 May 4, 2017                 [Page 11]