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]