Internet Research Task Force V. Firoiu, Ed. Internet-Draft BAE Systems Intended status: Informational B. Adamson, Ed. Expires: May 15, 2015 Naval Research Laboratory V. Roca, Ed. C. Adjih INRIA J. Bilbao IK4-IKERLAN F. Fitzek Aalborg University A. Masucci INRIA M. Montpetit MIT November 11, 2014 Network Coding Taxonomy draft-irtf-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. 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 15, 2015. Firoiu, et al. Expires May 15, 2015 [Page 1] Internet-Draft Network Coding Taxonomy November 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 May 15, 2015 [Page 2] Internet-Draft Network Coding Taxonomy November 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 May 15, 2015 [Page 3] Internet-Draft Network Coding Taxonomy November 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 May 15, 2015 [Page 4] Internet-Draft Network Coding Taxonomy November 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 May 15, 2015 [Page 5] Internet-Draft Network Coding Taxonomy November 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 May 15, 2015 [Page 6] Internet-Draft Network Coding Taxonomy November 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 May 15, 2015 [Page 7] Internet-Draft Network Coding Taxonomy November 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 May 15, 2015 [Page 8] Internet-Draft Network Coding Taxonomy November 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 May 15, 2015 [Page 9] Internet-Draft Network Coding Taxonomy November 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 May 15, 2015 [Page 10]