idnits 2.17.1 draft-irtf-nwcrg-network-coding-taxonomy-02.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 == Line 191 has weird spacing: '...symbols repa...' == Line 196 has weird spacing: '... packet rep...' == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (March 10, 2017) is 2598 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 NWCRG V. Roca, Ed. 3 Internet-Draft INRIA 4 Intended status: Informational V. Firoiu, Ed. 5 Expires: September 11, 2017 BAE Systems 6 March 10, 2017 8 Network Coding Taxonomy 9 draft-irtf-nwcrg-network-coding-taxonomy-02 11 Abstract 13 This document summarizes a recommended terminology for Network Coding 14 concepts and constructs. It provides a comprehensive set of terms in 15 order to avoid ambiguities in future Network Coding IRTF and IETF 16 documents. This document is intended to be in-line with the 17 terminology used by the RFCs produced by the Reliable Multicast 18 Transport (RMT) and FEC Framework (FECFRAME) IETF working groups. 20 Status of This Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at http://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on September 11, 2017. 37 Copyright Notice 39 Copyright (c) 2017 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 55 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 56 2. General definitions and concepts . . . . . . . . . . . . . . 3 57 3. Taxonomy of Code Uses . . . . . . . . . . . . . . . . . . . . 5 58 4. Coding Details . . . . . . . . . . . . . . . . . . . . . . . 7 59 4.1. Coding Types . . . . . . . . . . . . . . . . . . . . . . 7 60 4.2. Coding Basics . . . . . . . . . . . . . . . . . . . . . . 8 61 4.3. Coding In Practice . . . . . . . . . . . . . . . . . . . 10 62 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 63 6. Security Considerations . . . . . . . . . . . . . . . . . . . 11 64 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 65 7.1. Normative References . . . . . . . . . . . . . . . . . . 11 66 7.2. Informative References . . . . . . . . . . . . . . . . . 12 67 Appendix A. Additional references . . . . . . . . . . . . . . . 12 68 Appendix B. Authors and Contributors . . . . . . . . . . . . . . 12 69 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 71 1. Introduction 73 The literature on Network Coding research and system design, IETF 74 included, led to a rich set of concepts and constructs. This 75 document collects terminology used in the domain, both outside and 76 inside IETF, provides concise definitions, and introduces a high 77 level taxonomy. Its primary goal is to be useful to IETF and IRTF 78 activities. It is also intended to be in-line with the terminology 79 already used by the RFCs produced by the Reliable Multicast Transport 80 (RMT) and FEC Framework (FECFRAME) IETF working groups, in particular 81 [RFC5052] [RFC6726] [RFC5775] [RFC5740] [RFC6363]. 83 This document only focuses on packet transmissions and packet losses, 84 for instance because of congested routers, routing issues, 85 intermittent connectivity (e.g., a mobile terminal can suddenly go 86 behind an obstacle) and wireless communication issues. 87 Communications may happen in various types of networks, physical 88 links, UDP services, overlay networks or even virtual networks. The 89 notion of packet itself is multiform, depending on the target use- 90 case and the way network layer is applied (e.g., in which layer of 91 the protocol stack). For instance, a packet may be a UDP datagram 92 because coding happens within a dedicated transport protocol on top 93 of UDP. 95 This document does not try to achieve exhaustiveness. It is 96 voluntarily kept as simple as possible. 98 This document does not consider physical layer transmission issues, 99 nor physical layer coding/codes, nor error detection: if low layer 100 error codes detect but fail to correct bit errors, or if an upper 101 layer checksum (IP or UDP for instance) identify a corrupted packet, 102 then this packet is supposed to be dropped. 104 This document IS NOT restricted to constructs that perform re-coding 105 within intermediate coding forwarding nodes. If network coding 106 (i.e., re-coding within the network) is in scope, this document has a 107 broader scope. 109 In the following definitions, the "(IETF)" tag indicates that the 110 associated term is already used in IETF documents. 112 1.1. Requirements Language 114 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 115 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 116 document are to be interpreted as described in RFC 2119 [RFC2119]. 118 2. General definitions and concepts 120 This section gathers general definitions and concepts that are used 121 throughout this document. 123 Packet Erasure Channel: A communication path where packets are 124 either dropped or received without any error. This type of 125 packet drop is referred to as an "erasure" or "loss". The 126 term "channel" must be understood as a generic term for any 127 type of communication facility. The "Erasure" channels are 128 opposed to "Error" channels that are out of scope. 130 Erasure Correcting Code (ECC), or (IETF) Forward Erasure Code (FEC): 132 A code for the Packet Erasure Channel (only). These 133 codes are also called "Application-Level FEC" to 134 highlight that they have been designed to be used within 135 the higher layers of the protocol stack, to protect 136 against packet losses. These codes are opposed to 137 "Error" correction codes that address errors and are out 138 of scope. 140 Original Payload, or Uncoded Payload, or Systematic Symbol, or 141 (IETF) Source Symbol: 142 A unit of data originating from the source that is used 143 as input to encoding operations. When there is a single 144 source symbol per source packet, an Original Payload 145 corresponds to a Source packet. 147 Coded Payload, Coded Symbol, or (IETF) Repair Symbol: A unit of 148 data that is the result of a coding operation, applied 149 either to source symbols or (in case of recoding) source 150 and/or repair symbols. When there is a single repair 151 symbol per repair packet, a Coded Payload corresponds to 152 a Repair Packet. 154 Input Symbol and Output Symbol: A unit of data that is used as 155 input to an encoding operation or that is generated as 156 output of an encoding operation. At a re-coding node, 157 Repair Symbols are also part of the Input Symbols. With 158 Systematic Coding, Source Symbols are also part of the 159 Output Symbols. 161 (IETF) Encoding Symbol: A source or a repair symbol. 163 (IETF) Source Packet: A packet originating from the source 164 which contributes to one or more Source Symbols. For 165 instance, an RTP packet as a whole can constitute a 166 Source Symbol. In other situations (e.g, to address 167 variable size packets) a single RTP packet may 168 contribute to various Source Symbols. 170 (IETF) Repair Packet: A packet containing one or more Repair 171 Symbols. 173 Figure 1 illustrates the relationships between packets (what is sent 174 in the Packet Erasure Channel) and symbols (what is manipulated 175 during encoding and decoding operations) in case of FEC encoding, at 176 a Coding Node. A similar figure could be done for FEC decoding. 178 source packet 179 | 180 | source packet to source symbols transform 181 | (one or more symbols per packet) 182 v 183 source symbols 184 | 185 v input symbols 186 +----------------------+ 187 | FEC encoding | 188 +----------------------+ 189 | output symbols | 190 v v 191 source symbols repair symbols 192 | | 193 | | symbol to packet transform 194 | | (one or more symbols per packet) 195 v v 196 source packet repair packet 198 Figure 1: Packet and symbol relationships at a Coding Node. 200 Source node: A node that generates one or more Source Flows. 202 Coding node: A node that performs FEC encoding operations. It may 203 be an end-host, a middlebox, or a forwarding node. 205 (IETF) Flow: A stream of packets logically grouped. 207 (IETF) Source flow: A flow coming from an application on a given 208 host, and to which FEC encoding is to be applied, potentially 209 along with other source flows. Depending on the use case, 210 source flows may come from the same application, from 211 different applications on the same host, or from different 212 applications on different hosts. 214 (IETF) Repair flow: A flow containing Repair Symbols, after FEC 215 encoding. 217 3. Taxonomy of Code Uses 219 This section discusses the various ways of using coding, without 220 going into coding details. 222 Source Coding versus Channel Coding: (see Fig. Figure 2) When both 223 terms are opposed, "Source Coding" usually refers to 224 compression techniques (e.g., audio and video compression) 225 within the upper application that generates the source flow. 227 On the opposite, "Channel Coding" refers to FEC encoding in 228 order to improve transmission robustness, initially within 229 the lower physical layer, potentially also encompassing the 230 upper layers. These terms should not be confused with 231 respectively "FEC coding within the Source Node" and "FEC re- 232 coding within an intermediate Coding Node". 234 raw data flow from camera ^ video flow display 235 | | ^ 236 v | upper | 237 +-----------------------+ | +-----------------------+ 238 | source coding | | applica- | source (de)coding | 239 | (eg. mpeg compression)| | tion |(eg. mpg decompression)| 240 +-----------------------+ v +-----------------------+ 241 | ^ 242 v | 243 +-----------------------+ ^ +-----------------------+ 244 | network/AL-FEC coding | | middle- | network/AL-FEC coding | 245 | (eg. RLC encoding) | | ware | (eg. RLC decoding) | 246 +-----------------------+ v +-----------------------+ 247 | ^ 248 v | 249 +-----------------------+ ^ +-----------------------+ 250 | packetization | | | depacketization | 251 | (eg. UDP/IP) | | communi- | (eg. UDP/IP) | 252 +-----------------------+ | cation +-----------------------+ 253 | | ^ 254 v | layers | 255 +-----------------------+ | +-----------------------+ 256 | PHY layer | | | PHY layer | 257 | (channel coding) | | | (channel decoding) | 258 +-----------------------+ v +-----------------------+ 259 | ^ 260 | source + repair traffic | 261 +-------------------------------------------+ 263 Figure 2: Example of end-to-end flow manipulation with Network Coding 264 between the application and UDP layers (as with RMT or FECFRAME 265 architectures). Other architectures are possible, for instance with 266 network coding below the transport layer in order to allow re-coding 267 within the network. 269 End-to-End Coding: A system where coding is performed at the source 270 or (coding) middlebox, and decoding at the destination(s) or 271 (decoding) middlebox. There is no re-coding operation at 272 intermediate nodes. This is the approach followed in the 273 FLUTE/ALC [RFC6726][RFC5775], NORM [RFC5740] and FECFRAME 274 [RFC6363] protocols. 276 Network Coding: A system where coding can be performed at the source 277 as well as at intermediate forwarding nodes (all or a subset 278 of them). End-to-End Coding can be regarded as a special 279 case of Network Coding. Depending on the use case, 280 additional assumptions can be made: for instance the 281 knowledge by the destination of the coding node topology and 282 coding operations can help during decoding operations. 284 Intra-Flow Coding, or Single Source Network Coding: Process where 285 incoming packets to the Coding Node belong to the same flow. 287 Inter-Flow Coding, or Multi-Source Network Coding: Process where 288 incoming packets to the Coding Node belong to different 289 flows. 291 Single-Path Coding: Network Coding over a route that has a single 292 path from the source to each destination(s). In case of 293 multicast or broadcast traffic, this route is a tree. Coding 294 may be done end-to-end and/or at intermediate forwarding 295 nodes. 297 Multi-Path Coding: Network Coding over a route that has multiple (at 298 least partially) disjoint paths from the source to each given 299 destination. Coding may be done end-to-end and/or at 300 intermediate forwarding nodes. 302 4. Coding Details 304 4.1. Coding Types 306 This section provides a high level taxonomy of coding techniques, . 307 Technical details are left for the following sections. 309 Linear Coding: Linear combination of a set of input symbols (i.e., 310 source and/or repair symbols) using a given set of 311 coefficients and resulting in a Repair Symbol. Many linear 312 codes exist that differ from the way coding coefficients are 313 drawn from a Finite Field of a given size. 315 Random Linear Coding (RLC): Particular case of Linear Coding using a 316 set of random coding coefficients. 318 Adaptive Linear Coding: Linear Coding that utilizes cross layer 319 adaptation. For instance, an adaptive coding scheme may 320 adapt the generation and transmission of Repair Packets 321 according to the channel variations over time, accounting for 322 the predictive loss of degrees of freedom due to erasures. 324 Block Coding: Coding technique where the input Flow(s) must be first 325 segmented into a sequence of blocks, FEC encoding and 326 decoding being performed independently on a per-block basis. 327 The term "Chunk Coding" is sometimes used, where a "Chunk" 328 denotes a block. 330 Sliding Window Coding, or Convolutional Coding: General class of 331 coding techniques that rely on a sliding encoding window. 332 Convolutional Coding is an alternative solution to Block 333 Coding. 335 Fixed or Elastic Sliding Window Coding: Coding technique that 336 generates repair symbol(s) on-the-fly, from the set of source 337 symbols present in the sliding encoding window at that time, 338 usually by using Linear Coding. The sliding window may be 339 either of fixed size or of variable size over the time (also 340 known as "elastic sliding window"). For instance this size 341 may depend on acknowledgments sent by the receiver(s) for a 342 particular source symbol or source packet (received, decoded, 343 or decodable). 345 Systematic Coding: A coding technique where Source Symbols are part 346 of the output flow generated by a Coding Node. 348 Rateless and non-rateless Coding: Rateless coding can potentially 349 generate an infinite number of Repair Symbols (in practice 350 this number is extremely large) from a given set of Source 351 Symbols (meaning that their code rate is null). RLC codes 352 are an example of rateless codes. Non-rateless Coding 353 usually have a predefined maximum number of Repair Symbols 354 that can be generated from a given set of Source Symbols. 356 4.2. Coding Basics 358 This section discusses and defines low level coding aspects. 360 Code Rate: In case of a Block Code, the Code Rate is the k/n ratio 361 between the number of Source Symbols, k, and the number of 362 Source plus Repair Symbols, n. With a convolutional code, 363 the code rate is defined similarly over a certain time 364 interval (in case it evolves dynamically). By definition, 365 the code rate is such that: 0 < code rate <= 1. A code rate 366 close to 1 indicates that a small number of repair symbols 367 have been produced during the encoding process and vice- 368 versa. 370 (En)coding Window: A set of Source (and Repair in the case of re- 371 coding) Symbols used as input to the coding operations. The 372 set of symbols will typically change over the time, as the 373 Coding Window slides over the input Flow(s). 375 (En)coding Window Size: The number of Source (and Repair in case of 376 re-coding) Symbols in the current Encoding Window. This size 377 may change over the time. 379 Payload Set: The set of Source and Repair Symbols available (i.e., 380 received or previously decoded) at the receiver and used 381 during FEC decoding operations. 383 Decoding window: The set of Source Symbols (only) that are 384 considered in the current linear system of a receiver, 385 independently of the fact these Source Symbols have been 386 received, decoded, or lost. The Decoding Window will 387 typically change over the time, as transmissions and decoding 388 progress, and may be different for different receivers of a 389 session where content is multicast or broadcast. 391 Decoding Window Size: The number of Source Symbols (only) in the 392 current Decoding Window. This size may change over the time. 394 Rank of a Payload Set, or (IETF) Rank of the Linear System: At a rec 395 eiver, number of linearly independent members of a Payload 396 Set, or equivalently the number of linearly independent 397 equations of the linear system. It is also known as "Degrees 398 of Freedom". The system may be of "full rank" and decoding 399 is possible, or "partial rank", and only partial decoding is 400 possible. 402 Seen Payload, or Seen Symbol: A Source Symbol is Seen when the 403 receiver can compute a linear combination with this symbol 404 and Source Symbols that are strictly more recent (i.e., with 405 logically higher Encoding Symbol Identifiers). Otherwise the 406 Source Symbol is considered as "unseen". 408 Generation, or (IETF) Block: With Block Codes, the set of Source 409 Symbols of the input Flow(s) that are logically grouped into 410 a block, before doing encoding. 412 Generation Size, or Code Dimension, or (IETF) Block Size: With Block 413 Codes, the number k of Source Symbols belonging to a Block. 415 Coding Matrix, or Generator Matrix: A matrix G that transforms the 416 set of Input Symbols X into a set of Repair Symbols: Y = X * 417 G. Defining a Generator Matrix is usual with Block Codes. 418 The set of Input Symbols X can consist only of Source Symbols 419 (e.g., with End-to-End Coding) or Source and Repair Symbols 420 (e.g., with re-coding in an intermediate node). 422 Coding Coefficient: With Linear Coding, this is a coefficient in a 423 certain Finite Field. This coefficient may be chosen in 424 different ways: randomly, or in a pre-defined table, or using 425 a pre-defined algorithm plus a seed. 427 Coding Vector: A set of Coding Coefficients used to generate a 428 certain Repair Symbol through Linear Coding. The number of 429 nonzero coefficients in the Coding Vector defines its 430 density. 432 Finite Field, or Galois Field, or Coding Field: Finite fields, used 433 in Linear Codes, have the desired property of having all 434 elements (except zero) invertible for + and * and all 435 operations over any elements do not result in an overflow or 436 underflow. Examples of Finite Fields are prime fields 437 {0..p^m-1}, where p is prime. Most used fields use p=2 and 438 are called binary extension fields {0..2^m-1}, where m often 439 equals 1, 4 or 8 for practical reasons. 441 Finite Field size Coding Field size: The number of elements in a 442 finite field. For example the binary extension field 443 {0..2^m-1} has size q=2^m. 445 Feedback: Feedback information sent by a decoding node to a Coding 446 Node (or from a receiver to a source in case of End-to-End 447 Coding). The nature of information contained in a feedback 448 packet varies, depending on the use-case. It can provide 449 reception and/or FEC decoding statistics, or available Source 450 Packets received and/or decoded (acknowledgement), or lost 451 Source Packets that should be retransmitted (negative 452 acknowledgement), or a number of additional Repair Symbols 453 needed to have a Full Rank Linear System. 455 4.3. Coding In Practice 457 This section discusses practical aspects. Indeed, a practical 458 solution must specify the exact manner encoding and decoding is 459 performed but also all the peripheral aspects, for instance how an 460 encoder informs a decoder about the parameters used to generate a 461 certain Repair Packet (signalling). 463 (IETF) FEC Scheme: A specification that defines the additional 464 protocol aspects required to use a particular FEC code. In 465 particular the FEC Scheme defines in band (e.g., in source 466 and repair packet header or trailers) and out of band (e.g., 467 in SDP description) signalling needed to synchronize encoders 468 and decoders. 470 Payload Indices, or (IETF) Encoding Symbol Identifiers (ESI): An ide 471 ntifier of a Source or Repair Symbol. If conceptually, each 472 symbol is identified by a unique ESI value, in practice, with 473 a continuous flow and a limited field size to hold the ESI, 474 wrapping to zero in unavoidable and the same integer value 475 will be re-used several times. 477 (IETF) FEC Payload ID: Information that identifies the contents of a 478 packet with respect to the FEC scheme. The FEC Payload ID of 479 a packet containing Source Symbol(s) is usually different 480 from that of a packet containing Repair Symbol(s). An ESI is 481 typically part of the FEC Payload ID. 483 Coding Vector and Encoding Window Signalling: With Sliding Window 484 Coding, the FEC Payload ID of a repair packet necessarily 485 contains information needed and sufficient to identify the 486 Coding Vector and Coding Window. This may consist of a full 487 list of Coding Coefficients (that may be compressed or not), 488 or a piece of information (e.g., a seed) that can be used to 489 generate the list of Coding Coefficients thanks to a 490 predefined algorithm known by encoders and decoders (e.g., a 491 PRNG), or an ESI that points to a given entry in a Generator 492 Matrix in case of a block code. It may also consist of the 493 full list of ESI of symbols in the Coding Window (that may be 494 compressed or not), or the ESI of the first Source Symbol 495 along with their number (assuming there is no gap). 497 5. IANA Considerations 499 This document is not subject to IANA registration. 501 6. Security Considerations 503 This document introduces a recommended terminology for network coding 504 and therefore does not contain any security consideration. This does 505 not mean that network coding systems do not have any security 506 implication. 508 7. References 510 7.1. Normative References 512 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 513 Requirement Levels", BCP 14, RFC 2119, 514 DOI 10.17487/RFC2119, March 1997, 515 . 517 7.2. Informative References 519 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 520 Correction (FEC) Building Block", RFC 5052, 521 DOI 10.17487/RFC5052, August 2007, 522 . 524 [RFC5740] Adamson, B., Bormann, C., Handley, M., and J. Macker, 525 "NACK-Oriented Reliable Multicast (NORM) Transport 526 Protocol", RFC 5740, DOI 10.17487/RFC5740, November 2009, 527 . 529 [RFC5775] Luby, M., Watson, M., and L. Vicisano, "Asynchronous 530 Layered Coding (ALC) Protocol Instantiation", RFC 5775, 531 DOI 10.17487/RFC5775, April 2010, 532 . 534 [RFC6363] Watson, M., Begen, A., and V. Roca, "Forward Error 535 Correction (FEC) Framework", RFC 6363, 536 DOI 10.17487/RFC6363, October 2011, 537 . 539 [RFC6726] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen, 540 "FLUTE - File Delivery over Unidirectional Transport", 541 RFC 6726, DOI 10.17487/RFC6726, November 2012, 542 . 544 Appendix A. Additional references 546 Additional references on network coding are available in the NWCRG 547 research web site: https://irtf.org/nwcrg 549 Appendix B. Authors and Contributors 551 This document is the result of a collaborative work that involved may 552 authors and contributors from the NWCRG IRTF research group. They 553 are listed below in alphabetical order: 555 Brian Adamson 557 Cedric Adjih 559 Josu Bilbao 560 Victor Firoiu 562 Frank Fitzek 564 Samah A. M. Ghanem 566 Emmanuel Lochin 568 Antonia Masucci 570 Marie-Jose Montpetit 572 Morten V. Pedersen 574 Goiuri Peralta 576 Vincent Roca 578 Paresh Saxena 580 Senthil Sivakumar 582 Authors' Addresses 584 Vincent Roca (editor) 585 INRIA 586 655, av. de l'Europe 587 Inovallee; Montbonnot 588 ST ISMIER cedex 38334 589 France 591 Email: vincent.roca@inria.fr 593 Victor Firoiu (editor) 594 BAE Systems 595 Burlington, MA 01803 596 USA 598 Email: victor.firoiu@baesystems.com