Network Coding Taxonomy
draft-firoiu-nwcrg-network-coding-taxonomy-00

Internet Research Task Force                              V. Firoiu, Ed.
Internet-Draft                                               BAE Systems
Intended status: Informational                           B. Adamson, Ed.
Expires: September 2, 2014                     Naval Research Laboratory
                                                           March 1, 2014

                        Network Coding Taxonomy
             draft-firoiu-nwcrg-network-coding-taxonomy-00

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.

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 2, 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.

Firoiu & Adamson        Expires September 2, 2014               [Page 1]
Internet-Draft           Network Coding Taxonomy              March 2014

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Requirements Language . . . . . . . . . . . . . . . . . .   2
   2.  The context of coding strategies  . . . . . . . . . . . . . .   2
   3.  Basics of Coding  . . . . . . . . . . . . . . . . . . . . . .   3
   4.  Payload-level Operations  . . . . . . . . . . . . . . . . . .   3
   5.  Network Coding Methods  . . . . . . . . . . . . . . . . . . .   4
   6.  Payload-level Operations in Block Coding Method . . . . . . .   4
   7.  Node-local Processing in Block Coding Method  . . . . . . . .   5
   8.  Network Coding Transport  . . . . . . . . . . . . . . . . . .   5
   9.  Routing and Forwarding  . . . . . . . . . . . . . . . . . . .   6
   10. Error control . . . . . . . . . . . . . . . . . . . . . . . .   6
   11. Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .   6
   12. IANA Considerations . . . . . . . . . . . . . . . . . . . . .   6
   13. Security Considerations . . . . . . . . . . . . . . . . . . .   6
   14. Normative References  . . . . . . . . . . . . . . . . . . . .   7
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   7

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 Information Theory, Coding and Data Networks.  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.  The context of coding strategies

   Source Coding  Compressing the information at the source to increase
           the transmission efficiency.

   Channel Coding  Introducing redundant bits in the information
           sequence to increase reliability of communication.

   Network Coding  Coding operation realized at payload level and
           performed at the source as well as possibly at some

Firoiu & Adamson        Expires September 2, 2014               [Page 2]
Internet-Draft           Network Coding Taxonomy              March 2014

           intermediate nodes.  This coding strategy can result in more
           efficient and more reliable communication.

3.  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/
           uderflow.  Examples of finite fields are Galois fields,
           including prime fields {0..p^n-1}, where p is prime.  Most
           used fields are binary {0..2^n-1}.

   (Coding) Field size  The number of elements in a field.  For example
           the binary field {0..2^n-1} has size 2^n.

   (Coding) Symbols  Elements of a pre-defined coding field.

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

   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 symbols over a Coding Field.  Symbols at a
           given position from each payload are linearly combined.
           Resulting coded symbols are assembled in a coded payload,
           respecting the original in-payload order.  All linear
           combinations on any symbol position use the same given set of
           coefficients.  The input payloads may be original (not coded)
           or coded.

   Non-linear Coding  Combining a set of payloads using non-linear
           functions.

   (Coding) Coefficient  A coding symbol used as a coefficien t in
           linear coding of payloads.

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

Firoiu & Adamson        Expires September 2, 2014               [Page 3]
Internet-Draft           Network Coding Taxonomy              March 2014

   Coding Matrix of a set of coded payloads  The set of coding vectors
           used in transforming a set of original (uncoded) payloads
           into the given set of coded payloads.

   Density of a coding vector  Number of non-zero coefficents in the
           coding vector.

   Random Linear Coding  Linear coding using a set of random symbols as
           coefficients

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

   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.

6.  Payload-level Operations in Block Coding Method

   (Coding) Block a.k.a. Generation (less preferred term)  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  The number of original payloads belonging to a
           coding block

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

   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.

Firoiu & Adamson        Expires September 2, 2014               [Page 4]
Internet-Draft           Network Coding Taxonomy              March 2014

7.  Node-local Processing in Block Coding Method

   Full Rank NACK  A message from a node that a given Payload Set does
           not have full rank.

   Range Space a 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.  Network Coding Transport

   Coherent Network Coding  Source and destination nodes know network
           topology and coding operations at intermediate nodes.

   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    An application-level data stream usually defined by a five-
           tuple (source and destination IP address, Type of Service
           (TOS) or Diffserv code point (DSCP), and source and
           destination port of the transport protocol).  This definition
           includes both unicast and multicast flows.  Packets belonging
           to the same flow can travel (and may be coded) on multiple
           paths.

   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.

Firoiu & Adamson        Expires September 2, 2014               [Page 5]
Internet-Draft           Network Coding Taxonomy              March 2014

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

9.  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  Process of conveying a flow from the current node or
           previous hop(s) to the next hop(s) along single- or multi-
           path routes.

10.  Error control

   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.

11.  Acknowledgements

   This document is based on inputs from Cedric Adjih, Josu Bilbao,
   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.

Firoiu & Adamson        Expires September 2, 2014               [Page 6]
Internet-Draft           Network Coding Taxonomy              March 2014

14.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

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

Firoiu & Adamson        Expires September 2, 2014               [Page 7]