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, . 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, . [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, . [RFC5775] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered Coding (ALC) Protocol Instantiation", RFC 5775, DOI 10.17487/RFC5775, April 2010, . 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, . [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]