idnits 2.17.1 draft-irtf-nwcrg-network-coding-taxonomy-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (October 31, 2016) is 2734 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Research Task Force V. Firoiu, Ed. 3 Internet-Draft BAE Systems 4 Intended status: Informational B. Adamson, Ed. 5 Expires: May 4, 2017 Naval Research Laboratory 6 V. Roca, Ed. 7 C. Adjih 8 INRIA 9 J. Bilbao 10 IK4-IKERLAN 11 F. Fitzek 12 Aalborg University 13 A. Masucci 14 INRIA 15 M. Montpetit 16 MIT 17 October 31, 2016 19 Network Coding Taxonomy 20 draft-irtf-nwcrg-network-coding-taxonomy-01 22 Abstract 24 This document summarizes a recommended terminology for Network Coding 25 concepts and constructs. It provides a comprehensive set of terms 26 with unique names in order to avoid ambiguities in future Network 27 Coding IRTF and IETF documents. This document is intended to be in- 28 line with the terminology used by the RFCs produced by the Reliable 29 Multicast Transport (RMT) and FEC Framework (FECFRAME) IETF working 30 groups. 32 Status of This Memo 34 This Internet-Draft is submitted in full conformance with the 35 provisions of BCP 78 and BCP 79. 37 Internet-Drafts are working documents of the Internet Engineering 38 Task Force (IETF). Note that other groups may also distribute 39 working documents as Internet-Drafts. The list of current Internet- 40 Drafts is at http://datatracker.ietf.org/drafts/current/. 42 Internet-Drafts are draft documents valid for a maximum of six months 43 and may be updated, replaced, or obsoleted by other documents at any 44 time. It is inappropriate to use Internet-Drafts as reference 45 material or to cite them other than as "work in progress." 47 This Internet-Draft will expire on May 4, 2017. 49 Copyright Notice 51 Copyright (c) 2016 IETF Trust and the persons identified as the 52 document authors. All rights reserved. 54 This document is subject to BCP 78 and the IETF Trust's Legal 55 Provisions Relating to IETF Documents 56 (http://trustee.ietf.org/license-info) in effect on the date of 57 publication of this document. Please review these documents 58 carefully, as they describe your rights and restrictions with respect 59 to this document. Code Components extracted from this document must 60 include Simplified BSD License text as described in Section 4.e of 61 the Trust Legal Provisions and are provided without warranty as 62 described in the Simplified BSD License. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 67 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 68 2. Channel and Coding Types . . . . . . . . . . . . . . . . . . 3 69 3. Basics of Finite Fields . . . . . . . . . . . . . . . . . . . 4 70 4. Payload-level Operations . . . . . . . . . . . . . . . . . . 4 71 5. Coding Methods . . . . . . . . . . . . . . . . . . . . . . . 5 72 6. Payload-level Operations in Block Coding Method . . . . . . . 5 73 7. Node-local Processing in Block Coding Method . . . . . . . . 6 74 8. Node-local Processing in Sliding Window Coding Method . . . . 7 75 9. Network Coding Transport . . . . . . . . . . . . . . . . . . 7 76 10. Routing and Forwarding . . . . . . . . . . . . . . . . . . . 8 77 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8 78 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 79 13. Security Considerations . . . . . . . . . . . . . . . . . . . 9 80 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 81 14.1. Normative References . . . . . . . . . . . . . . . . . . 9 82 14.2. Informative References . . . . . . . . . . . . . . . . . 9 83 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 85 1. Introduction 87 The literature on Network Coding research and system design has a 88 large set of concepts and contructs with origins in several research 89 fields including Coding and Information Theory, Data Networks and 90 Storage. In many cases, same or similar concepts have received 91 multiple names, or the same name may be used for different concepts 92 in different contexts. This document attempts to collect a 93 comprehensive set of concepts and constructs, and for each, provide a 94 concise definition along with a unique name that is most used and 95 most descriptive. This terminology will help avoid ambiguities in 96 future Network Coding IRTF and IETF documents. 98 1.1. Requirements Language 100 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 101 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 102 document are to be interpreted as described in RFC 2119 [RFC2119]. 104 2. Channel and Coding Types 106 Packet Erasure Channel A communication path where packets are either 107 dropped (e.g., by a congested router, or because the number 108 of transmission errors exceeds the correction capabilities of 109 the physical layer codes) or received. When a packet is 110 received, it is assumed that this packet is not corrupted. 112 Packet Error Channel A communication path where packets are 113 potentially subject to bit corruptions (that may not be 114 corrected by the physical layer codes). 116 Source Coding Compressing the information at the source (i.e., 117 within the application) to improve transmission efficiency 118 (NB: this aspect is mostly out of scope). 120 Channel Coding Introducing redundant information in the transmission 121 stream to increase transmission robustness. This 123 End-to-End Coding Coding operation realized at payload level and 124 performed at the source or in a middlebox, without re-coding 125 operation at intermediate nodes. Similarly, decoding is 126 performed at the destination(s) or in a middlebox. This is 127 the approach used in the ALC [RFC5775], NORM [RFC5740] and 128 FECFRAME [RFC6363] protocols. 130 Network Coding Coding operation realized at payload level and 131 performed at the source as well as possibly at some 132 intermediate nodes. This coding strategy can result in more 133 efficient and more reliable communication. 135 Error Correcting (Network) Codes Codes (resp. network codes) for the 136 Packet Error Channel. 138 Erasure Correcting (Network) Codes, A.K.A. Forward Erasure Codes 139 (FEC) 140 Codes (resp. network codes) for the Packet Erasure 141 Channel. 143 3. Basics of Finite Fields 145 Coding Field A pre-defined finite field used in a Network Coding 146 algorithm or protocol. Coding fields have the desired 147 property of having all elements invertible for + and * and 148 all operations over any elements do not result in overflow/ 149 underflow. Examples of finite fields are Galois fields, 150 including prime fields {0..p^m-1}, where p is prime. Most 151 used fields are binary fields {0..2^m-1}, where m equals 1, 4 152 or 8 for practical reasons. 154 (Coding) Field size The number of elements in a field. For example 155 the binary field {0..2^m-1} has size q=2^m. 157 (Coding) Elements Elements of a pre-defined coding field. 158 [RFC5510], section 8.4, details the relationships between 159 source and repair symbols and elements of the finite field. 161 4. Payload-level Operations 163 Original (Uncoded) Payload, A.K.A. (IETF) Source Symbol A set of ap 164 plication-level data with defined byte sequence bounds, 165 generated at the source of a flow. Original payloads are 166 inputs to coding operations. 168 Coded Payload, A.K.A. (IETF) Repair Symbol The result of a coding 169 operation applied to original or coded payloads. 171 Linear Coding Linear combination of a set of payloads using a given 172 set of coefficients resulting in a coded payload. Payloads 173 are divided in elements over a Coding Field. Elements at a 174 given position from each payload are linearly combined. 175 Resulting coded elements are assembled in a coded payload, 176 respecting the original in-payload order. All linear 177 combinations on any element position use the same given set 178 of coefficients. The input payloads may be original (not 179 coded) or coded. [COMMENT: Suggestion is to have a terse 180 definition here and refer to a later section that will have 181 more explanation of the algorithm and some diagrams.] 183 Non-linear Coding Combining a set of payloads using non-linear 184 functions. 186 (Coding) Coefficient A coding element used as a coefficien t in 187 linear coding of payloads. 189 Coding Vector A set of coding elements representing coefficients 190 needed for generating a given coded payload through linear 191 coding of original (non-coded) payloads. 193 Coding (or Generator) Matrix (of a set of coded payloads) A matrix G 194 that transforms the set of source (uncoded) symbols X into a 195 set of coded payloads Y = X * G. 197 Density of a coding vector Number of non-zero coefficents in the 198 coding vector. 200 Random Linear Coding Linear coding using a set of random elements as 201 coefficients. 203 5. Coding Methods 205 Block coding Original payload sequence is divided in blocks, and 206 coding is performed only over payloads within a block. 208 Sliding Window coding Given a stream of uncoded payloads, coding 209 blocks are selected based on a sliding window. Coding blocks 210 may be partially overlapping, and, over time, moving to 211 higher original payload sequence numbers. 213 Elastic Sliding Window coding Sliding Window Coding with an encoding 214 window of variable size over the time. For instance this 215 size may depend on acknowledgments sent by the receiver(s) 216 for a particular original payload (received, decoded, or 217 decodable). 219 Convolutional network coding Coding that relies on a sliding 220 encoding window, of fixed or elastic size. Convolutional 221 coding is an alternative solution to block coding. 223 Coding node Node performing coding operations. 225 6. Payload-level Operations in Block Coding Method 227 [COMMENT: Below definitions are very far from those used in 228 RMT/FECFRAME. Need to decide how to harmonize. 230 (Coding) Block a.k.a. Generation A set of (usually consecutive) 231 original (uncoded) payloads defined by the sender-side of an 232 NC transport protocol. Coding is only performed over 233 payloads belonging to the same block. Payloads resulting 234 from coding over payloads of a block, also belong to the same 235 block. 237 (Coding) Block size a.k.a. Code dimension The number k of original 238 payloads belonging to a coding block 240 Code rate The ratio k/n between the number of source symbols k and 241 the number of encoding symbols n. By definition, the code 242 rate is such that: 0 < code rate <= 1. A code rate close to 243 1 indicates that a small number of repair symbols have been 244 produced during the encoding process. 246 (Coded) Payload Set A set of payloads belonging to the same block, 247 usually received at a node. 249 Rank of a Payload Set The number of linearly independent members of 250 a Payload Set received at a node. Also known as "Degrees of 251 Freedom". [COMMENT: May need to revise and refer to an 252 associated linear system.] 254 Full Rank The condition that a Payload Set received at a node has 255 rank equal to the block's size. A Payload Set can be fully 256 decoded into original packets iff it has full rank. 258 Partial Rank Any rank that is less than full rank and not zero. 260 7. Node-local Processing in Block Coding Method 262 [COMMENT: None of the definitions below are defined in RMT/FECFRAME 263 whereas block FEC codes were used. Need to decide how to harmonize.] 265 NACK A message from a node that the linear system associated to 266 the received Payload Set does not have full rank, and 267 additional source or repair symbol(s) is(are) needed. 269 Range Space of a Payload Set The linear space defined by the coding 270 vectors of a Payload Set. 272 Null Space The linear space that represents the complement of the 273 Range Space of a Payload Set. 275 Null Space Sample A coding vector that is included in the Null 276 Space. 278 Solvable Payload Set The set of original payloads that can be 279 decoded from a given set of coded payloads. 281 8. Node-local Processing in Sliding Window Coding Method 283 Payload Indices The original payloads are numbered with indices 1,2, 284 . . . N [COMMENT: wrong definition.] 286 Sliding (encoding) window [Sun08] [Lac08] A set of consecutive 287 indices of original payloads: a node generates coded payloads 288 that are linear combinations of original payloads with 289 indices in its current sliding window. 291 Sliding window size [Lin10] [Cho08] [Sun09] The number of 292 consecutive payload indices of the window. 294 Seen payload (original payload seen at a receiver) [Sun08] [Sun09] 295 [Lin10] [Bao12] An original payload is "seen", when the 296 receiver can compute a linear combination with this payload 297 and original payloads with only higher indices. Otherwise 298 the payload is unseen. 300 Sensed payload (original payload sensed at a receiver) [Bao12] At a 301 receiver, an original payload is "sensed" when it is present 302 in at least in one of the received coded payloads. Otherwise 303 it is unsensed. 305 Lowest/ highest index of coded payloads [Cho08] The minimum (resp. 306 maximum) index of original payloads involved in a coded 307 payload. 309 9. Network Coding Transport 311 Coherent Network Coding Source and destination nodes know network 312 topology and coding operations at intermediate nodes. 313 [COMMENT: Need to clairify what "know" means.] 315 Noncoherent Network Coding Source and destination nodes do not know 316 network topology and intermediate coding operations. In this 317 case, random network coding can be applied. 319 Flow A stream of packets logically grouped from the network coding 320 perspective. These packets may come from the same 321 application (in that case they are identified by the five- 322 tuple: source and destination IP address, transport protocol 323 ID, and source and destination port of the transport 324 protocol), or come from the same source host (in which case 325 they are identified by the 3-tuple source and destination IP 326 address, Type of Service (TOS) or Diffserv code point 327 (DSCP)). This distinction depends on the use-case where 328 network coding is applied. 330 Intra-flow coding Network coding over payloads belonging to the same 331 flow. 333 Inter-flow coding Network coding over payloads belonging to multiple 334 flows. 336 End-to-end coding Transport stream is coded and decoded at end- 337 points. 339 Intermediate coding Packet coding can occur at endpoints and any 340 intermediate nodes on the route. 342 Coding node Node performing coding operations. 344 Forwarding factor The rate of transmission from a node relative to 345 the rate of information received at the same node. 347 10. Routing and Forwarding 349 Single-Path route A route that has a single path from source to 350 destination(s). In case of multicast, this is a tree. 352 Multi-Path route A route containing multiple disjoint paths from 353 source to a destination. 355 Subgraph A generalized multi-path route from a sender to one or 356 multiple receivers where paths can intersect and diverge any 357 number of times. 359 Forwarding The process of conveying a flow from the current node or 360 previous hop(s) to the next hop(s) along single- or multi- 361 path routes. Coding operations may be performed during the 362 forwarding process when network coding is applied within 363 intermediate nodes. 365 11. Acknowledgements 367 This document is based on inputs from Brian Adamson, Cedric Adjih, 368 Josu Bilbao, Victor Firoiu, Frank Fitzek, Antonia Masucci, Marie-Jose 369 Montpetit, Vincent Roca, Senthil Sivakumar, and other participants of 370 the Network Coding Research Group. 372 12. IANA Considerations 374 This memo includes no request to IANA. 376 13. Security Considerations 378 This memo includes no Network Coding - specific security definitions 379 yet. 381 14. References 383 14.1. Normative References 385 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 386 Requirement Levels", BCP 14, RFC 2119, 387 DOI 10.17487/RFC2119, March 1997, 388 . 390 14.2. Informative References 392 [Bao12] Bao, W., Shah-Mansour, V., and V. Wong, ""TCP VON: Joint 393 congestion control and online network coding for wireless 394 networks." In IEEE Global Communications Conference 395 (GLOBECOM)", 2012. 397 [Cho08] Cho, S. and C. Adjih, ""Wireless Broadcast with Network 398 Coding: DRAGONCAST", Inria Research Report RR-6569", 2008. 400 [Lac08] Lacan, J. and E. Lochin, ""Rethinking reliability for 401 long-delay networks." In IEEE International Workshop on 402 Satellite and Space Communications.", 2008. 404 [Lin10] Lin, Y., Liang, B., and B. Li, ""SlideOR: Online 405 opportunistic network coding in wireless mesh networks." 406 In Proceedings of IEEE INFOCOM.", 2010. 408 [RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, 409 "Reed-Solomon Forward Error Correction (FEC) Schemes", 410 RFC 5510, DOI 10.17487/RFC5510, April 2009, 411 . 413 [RFC5740] Adamson, B., Bormann, C., Handley, M., and J. Macker, 414 "NACK-Oriented Reliable Multicast (NORM) Transport 415 Protocol", RFC 5740, DOI 10.17487/RFC5740, November 2009, 416 . 418 [RFC5775] Luby, M., Watson, M., and L. Vicisano, "Asynchronous 419 Layered Coding (ALC) Protocol Instantiation", RFC 5775, 420 DOI 10.17487/RFC5775, April 2010, 421 . 423 [RFC6363] Watson, M., Begen, A., and V. Roca, "Forward Error 424 Correction (FEC) Framework", RFC 6363, 425 DOI 10.17487/RFC6363, October 2011, 426 . 428 [Sun08] Sundararajan, J., Shah, D., and M. Medard, ""ARQ for 429 network coding." In IEEE International Symposium on 430 Information Theory.", 2008. 432 [Sun09] Sundararajan, J., Devavrat, S., Medard, M., Mitzenmacher, 433 M., and J. Barros, ""Network coding meets TCP." In IEEE 434 INFOCOM 2009", 2009. 436 Authors' Addresses 438 Victor Firoiu (editor) 439 BAE Systems 440 Burlington, MA 01803 441 USA 443 Email: victor.firoiu@baesystems.com 445 Brian Adamson (editor) 446 Naval Research Laboratory 447 Washington, DC 20375 448 USA 450 Email: brian.adamson@nrl.navy.mil 452 Vincent Roca (editor) 453 INRIA 454 655, av. de l'Europe 455 Inovallee; Montbonnot 456 ST ISMIER cedex 38334 457 France 459 Email: vincent.roca@inria.fr 460 URI: http://planete.inrialpes.fr/people/roca/ 462 Cedric Adjih 463 INRIA 464 France 466 Email: Cedric.Adjih@inria.fr 467 Josu Bilbao 468 IK4-IKERLAN 469 J. M. Arizmendiarrieta, 2 470 Arrasate-Mondragon, Gipuzkoa 20500 471 Spain 473 Email: jbilbao@ikerlan.es 475 Frank Fitzek 476 Aalborg University 477 Aalborg 478 Denmark 480 Email: ff@es.aau.dk 482 Antonia Masucci 483 INRIA 484 Rocquencourt - B.P. 105 485 Le Chesnay 78153 486 France 488 Email: antonia.masucci@inria.fr 490 Marie-Jose Montpetit 491 MIT 492 77 Massachusetts Avenue 493 Cambridge, Massachusetts 02138 494 USA 496 Email: mariejo@mit.edu