idnits 2.17.1 draft-firoiu-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 (March 5, 2014) is 3705 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: September 6, 2014 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 March 5, 2014 19 Network Coding Taxonomy 20 draft-firoiu-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 September 6, 2014. 49 Copyright Notice 51 Copyright (c) 2014 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. The context of coding strategies . . . . . . . . . . . . . . 3 69 3. Channel and error correction types . . . . . . . . . . . . . 3 70 4. Basics of Coding . . . . . . . . . . . . . . . . . . . . . . 3 71 5. Payload-level Operations . . . . . . . . . . . . . . . . . . 4 72 6. Network Coding Methods . . . . . . . . . . . . . . . . . . . 5 73 7. Payload-level Operations in Block Coding Method . . . . . . . 5 74 8. Node-local Processing in Block Coding Method . . . . . . . . 6 75 9. Node-local Processing in Sliding Window Coding Method . . . . 6 76 10. Network Coding Transport . . . . . . . . . . . . . . . . . . 7 77 11. Routing and Forwarding . . . . . . . . . . . . . . . . . . . 8 78 12. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 8 79 13. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 80 14. Security Considerations . . . . . . . . . . . . . . . . . . . 8 81 15. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 82 15.1. Normative References . . . . . . . . . . . . . . . . . . 8 83 15.2. Informative References . . . . . . . . . . . . . . . . . 8 84 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 86 1. Introduction 88 The literature on Network Coding research and system design has a 89 large set of concepts and contructs with origins in several research 90 fields including Coding and Information Theory, Data Networks and 91 Storage. In many cases, same or similar concepts have received 92 multiple names, or the same name may be used for different concepts 93 in different contexts. This document attempts to collect a 94 comprehensive set of concepts and constructs, and for each, provide a 95 concise definition along with a unique name that is most used and 96 most descriptive. This terminology will help avoid ambiguities in 97 future Network Coding IRTF and IETF documents. 99 1.1. Requirements Language 101 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 102 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 103 document are to be interpreted as described in RFC 2119 [RFC2119]. 105 2. The context of coding strategies 107 Source Coding Compressing the information at the source to increase 108 the transmission efficiency by reducing redundant information 109 [COMMENT: do we need this?] 111 Channel Coding Introducing redundant information in the transmission 112 stream to increase reliability of communication. 114 Network Coding Coding operation realized at payload level and 115 performed at the source as well as possibly at some 116 intermediate nodes. This coding strategy can result in more 117 efficient and more reliable communication. 119 3. Channel and error correction types 121 Packet Erasure Channel A communication path where packets are either 122 dropped (e.g., by a congested router, or because the number 123 of transmission errors exceeds the correction capabilities of 124 the physical layer codes) or received. When a packet is 125 received, it is assumed that this packet is not corrupted. 127 Packet Error Channel A communication path where packets are 128 potentially subject to bit corruptions (that may not be 129 corrected by the physical layer codes). 131 Network Error Correcting Code Method for correcting errors in 132 communication networks by extending the classical error- 133 correcting codes from a point-to-point model to networks. 135 Network Erasure Correcting Codes Method of using spatial redundancy 136 of network coding to recover lost payloads. 138 4. Basics of Coding 140 Coding Field A pre-defined finite field used in a Network Coding 141 algorithm or protocol. Coding fields have the desired 142 property of having all elements invertible for + and * and 143 all operations over any elements do not result in overflow/ 144 underflow. Examples of finite fields are Galois fields, 145 including prime fields {0..p^m-1}, where p is prime. Most 146 used fields are binary fields {0..2^m-1}. 148 (Coding) Field size The number of elements in a field. For example 149 the binary field {0..2^m-1} has size q=2^m. 151 (Coding) Elements Elements of a pre-defined coding field. 153 5. Payload-level Operations 155 Original (Uncoded) Payload A set of application-level data with 156 defined byte sequence bounds, generated at the source of a 157 flow. Original payloads are inputs to coding operations. 159 Alternative definition to Payload: Symbol A unit of data processed 160 by a Network Coding operation. [COMMENT: we need to decide 161 which to adopt or if we keep both] 163 Coded Payload The result of a coding operation applied to original 164 or coded payloads. 166 Linear Coding Linear combination of a set of payloads using a given 167 set of coefficients resulting in a coded payload. Payloads 168 are divided in elements over a Coding Field. Elements at a 169 given position from each payload are linearly combined. 170 Resulting coded elements are assembled in a coded payload, 171 respecting the original in-payload order. All linear 172 combinations on any element position use the same given set 173 of coefficients. The input payloads may be original (not 174 coded) or coded. [COMMENT: Suggestion is to have a terse 175 definition here and refer to a later section that will have 176 more explanation of the algorithm and some diagrams.] 178 Non-linear Coding Combining a set of payloads using non-linear 179 functions. 181 (Coding) Coefficient A coding element used as a coefficien t in 182 linear coding of payloads. 184 Coding Vector A set of coding elements representing coefficients 185 needed for generating a given coded payload through linear 186 coding of original (non-coded) payloads. 188 Coding (or Generator) Matrix (of a set of coded payloads) A matrix G 189 that transforms the set of source (uncoded) symbols X into a 190 set of coded payloads Y = X * G. 192 Density of a coding vector Number of non-zero coefficents in the 193 coding vector. 195 Random Linear Coding Linear coding using a set of random elements as 196 coefficients 198 6. Network Coding Methods 200 Block coding Original payload sequence is divided in blocks, and 201 coding is performed only over payloads within a block. 203 Sliding Window coding Given a stream of uncoded payloads, coding 204 blocks are selected based on a sliding window. Coding blocks 205 may be partially overlapping, and, over time, moving to 206 higher original payload sequence numbers. 208 Elastic Window coding [Need definition] 210 Convolutional network coding Alternative solution to block network 211 coding for cyclic networks where the results of propagation 212 and coding of sequential payloads are similar to 213 convolutional coding. [COMMENT: need a better definition.] 215 Coding node Node performing coding operations. 217 7. Payload-level Operations in Block Coding Method 219 (Coding) Block a.k.a. Generation A set of (usually consecutive) 220 original (uncoded) payloads defined by the sender-side of an 221 NC transport protocol. Coding is only performed over 222 payloads belonging to the same block. Payloads resulting 223 from coding over payloads of a block, also belong to the same 224 block. 226 (Coding) Block size a.k.a. Code dimension The number of original 227 payloads belonging to a coding block 229 Code rate The ratio k/n between the number of source symbols k and 230 the number of encoding symbols n. By definition, the code 231 rate is such that: 0 < code rate <= 1. A code rate close to 232 1 indicates that a small number of repair symbols have been 233 produced during the encoding process. 235 (Coded) Payload Set A set of payloads belonging to the same block, 236 usually received at a node. 238 Rank of a Payload Set The number of linearly independent members of 239 a Payload Set received at a node. Also known as "Degrees of 240 Freedom". [COMMENT: May need to revise and refer to an 241 associated linear system.] 243 Full Rank The condition that a Payload Set received at a node has 244 rank equal to the block's size. A Payload Set can be fully 245 decoded into original packets iff it has full rank. 247 Partial Rank Any rank that is less than full rank and not zero. 249 8. Node-local Processing in Block Coding Method 251 NACK A message from a node that the linear system associated to 252 the received Payload Set does not have full rank, and 253 additional source or repair symbol(s) is(are) needed. 255 Range Space of a Payload Set The linear space defined by the coding 256 vectors of a Payload Set. 258 Null Space The linear space that represents the complement of the 259 Range Space of a Payload Set. 261 Null Space Sample A coding vector that is included in the Null 262 Space. 264 Solvable Payload Set The set of original payloads that can be 265 decoded from a given set of coded payloads. 267 9. Node-local Processing in Sliding Window Coding Method 269 Payload Indices The original payloads are numbered with indices 1,2, 270 . . . N 272 Sliding (encoding) window [Sun08] [Lac08] A set of consecutive 273 indices of original payloads: a node generates coded payloads 274 that are linear combinations of original payloads with 275 indices in its current sliding window. 277 Sliding window size [Lin10] [Cho08] [Sun09] The number of 278 consecutive payload indices of the window 280 Seen payload (original payload seen at a receiver) [Sun08] [Sun09] 281 [Lin10] [Bao12] An original payload is "seen", when the 282 receiver can compute a linear combination with this payload 283 and original payloads with only higher indices. Otherwise 284 the payload is unseen. 286 Sensed payload (original payload sensed at a receiver) [Bao12] At a 287 receiver, an original payload is "sensed" when it is present 288 in at least in one of the received coded payloads. Otherwise 289 it is unsensed. 291 Lowest/ highest index of coded payloads [Cho08] The minimum (resp. 292 maximum) index of original payloads involved in a coded 293 payload. 295 10. Network Coding Transport 297 Coherent Network Coding Source and destination nodes know network 298 topology and coding operations at intermediate nodes. 299 [COMMENT: Need to clairify what "know" means.] 301 Noncoherent Network Coding Source and destination nodes do not know 302 network topology and intermediate coding operations. In this 303 case, random network coding can be applied. 305 Flow A stream of packets logically grouped from the network coding 306 perspective. These packets may come from the same 307 application (in that case they are identified by the five- 308 tuple: source and destination IP address, transport protocol 309 ID, and source and destination port of the transport 310 protocol), or come from the same source host (in which case 311 they are identified by the 3-tuple source and destination IP 312 address, Type of Service (TOS) or Diffserv code point 313 (DSCP)). This distinction depends on the use-case where 314 network coding is applied. 316 Intra-flow coding Network coding over payloads belonging to the same 317 flow. 319 Inter-flow coding Network coding over payloads belonging to multiple 320 flows. 322 End-to-end coding Transport stream is coded and decoded at end- 323 points. 325 Intermediate coding Packet coding can occur at endpoints and any 326 intermediate nodes on the route. 328 Coding node Node performing coding operations. 330 Forwarding factor The rate of transmission from a node relative to 331 the rate of information received at the same node. 333 11. Routing and Forwarding 335 Single-Path route A route that has a single path from source to 336 destination(s). In case of multicast, this is a tree. 338 Multi-Path route A route containing multiple disjoint paths from 339 source to a destination. 341 Subgraph A generalized multi-path route from a sender to one or 342 multiple receivers where paths can intersect and diverge any 343 number of times. 345 Forwarding The process of conveying a flow from the current node or 346 previous hop(s) to the next hop(s) along single- or multi- 347 path routes. Coding operations may be performed during the 348 forwarding process when network coding is applied within 349 intermediate nodes. 351 12. Acknowledgements 353 This document is based on inputs from Brian Adamson, Cedric Adjih, 354 Josu Bilbao, Victor Firoiu, Frank Fitzek, Antonia Masucci, Marie-Jose 355 Montpetit, Vincent Roca, Senthil Sivakumar, and other participants of 356 the Network Coding Research Group. 358 13. IANA Considerations 360 This memo includes no request to IANA. 362 14. Security Considerations 364 This memo includes no Network Coding - specific security definitions 365 yet. 367 15. References 369 15.1. Normative References 371 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 372 Requirement Levels", BCP 14, RFC 2119, March 1997. 374 15.2. Informative References 376 [Bao12] Bao, W., Shah-Mansour, V., and V. Wong, ""TCP VON: Joint 377 congestion control and online network coding for wireless 378 networks." In IEEE Global Communications Conference 379 (GLOBECOM)", 2012. 381 [Cho08] Cho, S. and C. Adjih, ""Wireless Broadcast with Network 382 Coding: DRAGONCAST", Inria Research Report RR-6569", 2008. 384 [Lac08] Lacan, J. and E. Lochin, ""Rethinking reliability for 385 long-delay networks." In IEEE International Workshop on 386 Satellite and Space Communications.", 2008. 388 [Lin10] Lin, Y., Liang, B., and B. Li, ""SlideOR: Online 389 opportunistic network coding in wireless mesh networks." 390 In Proceedings of IEEE INFOCOM.", 2010. 392 [Sun08] Sundararajan, J., Shah, D., and M. Medard, ""ARQ for 393 network coding." In IEEE International Symposium on 394 Information Theory.", 2008. 396 [Sun09] Sundararajan, J., Devavrat, S., Medard, M., Mitzenmacher, 397 M., and J. Barros, ""Network coding meets TCP." In IEEE 398 INFOCOM 2009", 2009. 400 Authors' Addresses 402 Victor Firoiu (editor) 403 BAE Systems 404 Burlington, MA 01803 405 USA 407 Email: victor.firoiu@baesystems.com 409 Brian Adamson (editor) 410 Naval Research Laboratory 411 Washington, DC 20375 412 USA 414 Email: brian.adamson@nrl.navy.mil 416 Vincent Roca (editor) 417 INRIA 418 655, av. de l'Europe 419 Inovallee; Montbonnot 420 ST ISMIER cedex 38334 421 France 423 Email: vincent.roca@inria.fr 424 URI: http://planete.inrialpes.fr/people/roca/ 425 Cedric Adjih 426 INRIA 427 France 429 Email: Cedric.Adjih@inria.fr 431 Josu Bilbao 432 IK4-IKERLAN 433 J. M. Arizmendiarrieta, 2 434 Arrasate-Mondragon, Gipuzkoa 20500 435 Spain 437 Email: jbilbao@ikerlan.es 439 Frank Fitzek 440 Aalborg University 441 Aalborg 442 Denmark 444 Email: ff@es.aau.dk 446 Antonia Masucci 447 INRIA 448 Rocquencourt - B.P. 105 449 Le Chesnay 78153 450 France 452 Email: antonia.masucci@inria.fr 454 Marie-Jose Montpetit 455 MIT 456 77 Massachusetts Avenue 457 Cambridge, Massachusetts 02138 458 USA 460 Email: mariejo@mit.edu