idnits 2.17.1 draft-montpetit-dynamic-nc-00.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 date (March 9, 2015) is 3334 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 394 -- Looks like a reference, but probably isn't: '1' on line 395 == Outdated reference: A later version (-08) exists of draft-detchart-nwcrg-tetrys-00 Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 IRTF Network Coding Working Group M. Montpetit 3 Internet-Draft MIT 4 Intended status: Experimental V. Roca 5 Expires: September 10, 2015 INRIA 6 J. Detchart 7 ISAE 8 March 9, 2015 10 Dynamic Network Coding 11 draft-montpetit-dynamic-nc-00 13 Abstract 15 This document presents a network coding approach that allows coding 16 decisions to be based on the instantaneous conditions at the network 17 nodes. It uses dynamic rates and coefficients to constantly adapt to 18 local conditions and to allow for provider and application 19 differentiation. 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at http://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on September 10, 2015. 38 Copyright Notice 40 Copyright (c) 2015 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (http://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 56 2. Requirements Language . . . . . . . . . . . . . . . . . . . . 3 57 3. Definitions, Notations and Abbreviations . . . . . . . . . . 3 58 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 3 59 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 4 60 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 4 61 4. Dynamic Network Coding (DNC) Principles . . . . . . . . . . . 5 62 4.1. About the Use of Timestamps in DNC . . . . . . . . . . . 5 63 4.2. About the FEC Encoding ID, Codepoint and Coding Decisions 6 64 5. Dynamic Network Coding (DNC) Procedures . . . . . . . . . . . 6 65 5.1. Input Symbol Creation . . . . . . . . . . . . . . . . . . 6 66 5.2. Other Procedures TBD . . . . . . . . . . . . . . . . . . 7 67 6. Application of Dynamic Network Coding to Various Use-cases . 7 68 6.1. Single Flow, Single Source, End-to-end, Single Path or 69 Multi Paths Use-Case . . . . . . . . . . . . . . . . . . 8 70 6.1.1. Example of DNC Implementation for this Use-Case . . . 8 71 6.2. Single Flow with In-network Re-Coding . . . . . . . . . . 10 72 6.3. Other Use Cases . . . . . . . . . . . . . . . . . . . . . 11 73 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11 74 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 75 9. Security Considerations . . . . . . . . . . . . . . . . . . . 11 76 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 77 10.1. Normative References . . . . . . . . . . . . . . . . . . 11 78 10.2. Informative References . . . . . . . . . . . . . . . . . 11 79 Appendix A. Appendix: IPR aspects . . . . . . . . . . . . . . . 12 80 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12 82 1. Introduction 84 Network Coding has proven to be an efficient mechanism to provide 85 increased quality of experience for applications depending on 86 Internet Protocols. Current implementations, be them end-to-end or 87 hop-by-hop, depend on a global decision on the type and applicability 88 of the code. However, the heterogeneous nature of IP networks, the 89 differences between transported traffics and the rise of Information 90 Centric Networks (ICN) and multiple in network caches require to 91 define alternatives to current solutions. 93 Dynamic Network Coding (DNC) intends to use the characteristics of 94 the rising Internet traffic (Internet of Things, streaming, 95 progressive downloads etc.), the use of in-network caching 96 opportunities, customer and policy management and the changing 97 dynamics on wireless links. These characteristics will be used to 98 adapt the network coding scheme, rate and coefficients to provide 99 adaptive behavior, differentiation and varying quality of experience. 100 In addition, it will also allow to support emerging Internet 101 Architectures such as the ICN that are considering network coding 102 solutions [ICN]. 104 This draft provides the basic elements of such a dynamic code. 106 2. Requirements Language 108 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 109 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 110 document are to be interpreted as described in RFC 2119 [RFC2119]. 112 3. Definitions, Notations and Abbreviations 114 3.1. Definitions 116 This document uses the following definitions, that are mostly 117 inspired from from [RFC5052], [RFC6363]. 119 -- Editor's note: most of the definitions should be moved to the 120 future NC Architectural document. -- 122 Input Symbol: a unit of data that is provided as an input to the 123 coding process, in a given coding node. It may be a source symbol 124 or an already encoded repair symbol 126 Output Symbol: a unit of data that is produced as an output of the 127 coding process, in a given coding node 129 Source Symbol: an original unit of data, before any coding process 130 is applied 132 Repair Symbol: an Output Symbol that is not a Source Symbol 134 Code Rate: the ratio between the number of Input Symbols and the 135 number of Output Symbols at given coding node. The Code Rate 136 belongs to a ]0; 1] interval. A Code Rate close to 1 indicates 137 that a small number of Output Symbols have been produced during 138 the encoding process 140 Systematic Code: NC code in which the Source Symbols are part of 141 the Output Symbols 142 DNC Packet: a packet (e.g., carried as the payload of a UDP 143 datagram) containing a given Output Symbol plus its associated DNC 144 header. 146 Packet Erasure Channel: a communication path where packets are 147 either dropped (e.g., by a congested router or because the number 148 of transmission errors exceeds the correction capabilities of the 149 physical layer codes) or received. When a packet is received, it 150 is assumed that this packet is not corrupted 152 To Be Completed 154 -- Editor's note: Should we consider the possibility of having 155 several symbols per packet? The DNC packet should be updated 156 accordingly in that case. -- 158 3.2. Notations 160 This document uses the following notations: 162 CR denotes the Code Rate 164 To Be Completed 166 3.3. Abbreviations 168 This document uses the following abbreviations: 170 The following definitions are compatible with the FECFRAME 171 framework [RFC6363] and the NC architecture (COMMENT: reference to 172 be added when available). 174 NC: Network Coding 176 DNC: Dynamic Network Coding 178 PRNG: Pseudo-Random Number Generator 180 TS: Time Stamp 182 ESI: Encoding Symbol ID 184 To Be Completed 186 4. Dynamic Network Coding (DNC) Principles 188 Network Coding is based on the linear combination of a number of 189 input symbols (at least 1) into a number of output symbols (at least 190 1), between the ingress and egress of the network. Several such 191 encoding operations can happen in case of in-network re-coding, or 192 there can be a single encoding operation, especially when it is 193 applied end-to-end. In the RLNC [RLNC], Tetrys 194 [I-D.detchart-nwcrg-tetrys], and Dragoncast [I-D.adjih-dragoncast] 195 instances of Network Coding, the linear combination consists in 196 applying a set of coding coefficients to each input symbol of the 197 current encoding window. Here the coding vectors are chosen in a 198 deterministic manner at each encoding node, for instance based on 199 local criteria, or are generated using a PRNG seed chosen locally and 200 carried along with the output symbol. 202 The DNC proposal extends this process as follows: the set of coding 203 coefficients is determined based on the FEC_Encoding ID, Codepoint, 204 and TS header fields of the various input packets present in the 205 encoding window, plus the local time. The coding decision therefore 206 depends on time, among other pieces of information. 208 4.1. About the Use of Timestamps in DNC 210 Each DNC Packet contains timing information: this can be the TS field 211 of the DNC header, or the timestamp field of an NTP header if already 212 present in the packet. This timing information (noted TS hereafter, 213 no matter its origin) is used to determine the coding coefficients in 214 a coding node. When several DNC packets are present in the encoding 215 window, originating from one or several sources, a decision on which 216 TS will be sent downstream in the network must be taken. Options 217 include keeping the oldest TS value, the newest TS value, or 218 generating a local TS value. It is assumed that the granularity of 219 the TS in choosing the coding coefficients would be to the second tin 220 order to react to instantaneous condition. 222 It is also possible to use the TS in a wider sense, to link to 223 network operations and coding based police management. This includes 224 the determination of the coding window, Code Rate, Galois field, etc. 226 -- Editor's note: This extension is left for future specifications 227 as it requires closer coordination between network management. 228 policy and coding. -- 230 4.2. About the FEC Encoding ID, Codepoint and Coding Decisions 232 The FEC Encoding ID is used to identify the type of code (i.e., FEC 233 Scheme) to use at each coding node. This is an integer identifier 234 assigned by IANA. The value of the FEC Encoding ID MAY vary over the 235 time, within the same flow, and/or across the same path between 236 several coding nodes. Different coding decisions can be made by 237 different management entities with different operating constraints 238 (for instance content provider versus network operator). 240 -- Editor's note: Having the possibility to change the coding 241 decisions can have major practical technical implications that are 242 not considered for the moment. -- 244 The Codepoint is an opaque value to be used along with the FEC 245 Encoding ID and TS. The {FEC Encoding ID, Codepoint, TS} tuple 246 identifies uniquely the FEC Scheme used and the set of coding 247 coefficients. Examples are provided below on how to do that. 249 5. Dynamic Network Coding (DNC) Procedures 251 5.1. Input Symbol Creation 253 Incoming DNC packets at a coding node are not necessarily of the same 254 fixed size. This size may largely vary over the time, up to a 255 maximum size that is related to the Link MTU and/or Path MTU. This 256 is a problem when Repair Symbols need to be produced by a coding 257 node. 259 Let us consider the simple case where the FEC Scheme is such that a 260 Repair Symbol necessarily spans the payload of the largest Incoming 261 DNC Packet at the encoding window of the coding node. Let L be equal 262 to the maximum size of the DNC packets in the encoding window plus 2 263 bytes. The 2 bytes are used to store the original size of the 264 packets. Any DNC packet of size inferior to L-2 bytes MUST be zero 265 padded to achieve the desired length of L bytes. Then any Repair 266 Symbol within the set of Output Symbols is L bytes long. When a 267 Source Symbol is erased and later decoded, the first two bytes of the 268 decoded symbol, that contain the symbol_len field, allows to drop the 269 potential padding. 271 +------------+-----------------------+------------------------------+ 272 | symbol_len | symbol value | optional padding | 273 +------------+-----------------------+------------------------------+ 274 2 bytes symbol_len bytes L - 2 - symbol_len bytes 275 <------------------------------- L bytes ---------------------------> 277 Figure 1: Symbol Format, Case of a Single Flow 279 -- Editor's note: in presence of multiple flows, an additional 280 FlowID field may be prepended in order to identify the flow this 281 Input Symbol belongs to. The details are TBD. -- 283 5.2. Other Procedures TBD 285 TBD 287 For instance it may be interesting to have a feedback flow to enable 288 a receiver to adjust its encoding window according to the received or 289 decoded Source Symbols. 291 6. Application of Dynamic Network Coding to Various Use-cases 293 -- Editor's note: This section contains material that may be more 294 appropriate in a future NC Architecture document. -- 296 Several technical aspects need to be considered: 298 o Intra-flow encoding: (single flow) here all the Source Symbols 299 belong to the same and unique flow; 301 o Inter-flow encoding: (multiple flows) here the Source Symbols 302 belong to two or more flows. This situation is more complex, in 303 particular because it requires to remember the flow a given source 304 symbol belongs to in case this latter gets lost and is recovered 305 by a decoding node; 307 o End to end: (single coding node) here there is a single coding 308 node and a single decoding node. However the coding and/or 309 decoding nodes are not necessarily the source and destination 310 nodes. For instance these operations can be performed by middle 311 boxes, or coding may be done in a middle box while decoding is 312 performed at the destination node, or vice-versa. The nature of 313 the coding and decoding nodes should not significantly impact the 314 way DNC operates; 316 -- Editor's note: This claim is TBC. -- 318 o In network re-coding: (composability) here several coding nodes 319 exist along the path. This situation significantly impacts the 320 way DNC operates, in particular in terms of signaling. Indeed a 321 decoding node MUST be able to identify the exact manner in which a 322 given Repair Symbol has been generated, recursively since this 323 Repair Symbol MAY be the result of several coding operations, at 324 different coding nodes; 326 o Multi-source: here several traffic sources exist. They either 327 jointly contribute to the same data flow, all sources sending 328 traffic related to the same content, or they contribute to 329 multiple data flows, sources sending traffic for different 330 contents; 332 o Multi-paths: here the traffic follows multiple paths. This 333 traffic can be originated from a unique source (e.g., with multi- 334 path TCP, MPTCP), or with multiple sources which is the more 335 general case; 337 The above taxonomy can be used to identify several types of use- 338 cases. In the following we consider some of the potential use-cases 339 and explain how DNC can be applied. This is in no case an exhaustive 340 list and will be adapted in the future as we get more insights on the 341 code usage. 343 6.1. Single Flow, Single Source, End-to-end, Single Path or Multi Paths 344 Use-Case 346 In this use-case, there is a single flow originated by a single 347 source, with intra stream coding that takes place at a single coding 348 node. There can be either a single path or multiple paths, since 349 this situation does not impact the way DNC operates. 351 This is the simplest use-case, that is very much inline with 352 currently proposed scenarios for end to end streaming. 354 6.1.1. Example of DNC Implementation for this Use-Case 356 The following DNC approach / FEC Scheme is appropriate for this 357 simple use-case. However this is only an example and other 358 approaches may be considered, for instance differing in the way the 359 {FEC Encoding ID, Codepoint, TS} tuple is used. 361 Let us consider a FEC Scheme that defines the G table containing NL 362 lists, each list being populated with NC coefficients over a given 363 Finite Field, say GF(2^^4). This table, G, is contained in the FEC 364 Scheme specification. Each coding and decoding node supports this 365 FEC Scheme (and potentially a certain number of additional FEC 366 Schemes), this latter being identified by an IANA FEC Encoding ID 367 value. 369 o Encoding process: Let W be the encoding window, containing K Input 370 Symbols (constructed as specified in Section 5.1). It is required 371 that K be at most equal to the number of coefficients in each row 372 of G. If this is not the case, an appropriate number of symbols 373 are removed from window W until this property holds. Let TS be 374 the timestamp corresponding to the current time at the coding 375 node. Let Codepoint be the current integer value of a counter 376 that is managed sequentially, starting a 0 upon initializing the 377 DNC coding node instance, and wrapping to 0 upon reaching the 378 maximum counter value. 380 -- Editor's note: The counter field size, in bits, is not 381 specified in this version of the document. 32 bits or 16 bits 382 are two possible values. -- 384 Let r be an integer calculated as r=f(Codepoint, TS, K); where f 385 is a deterministic function that produces an integer in the {0; 386 K-1} range. This function is for instance the result of a hash 387 over {Codepoint, TS} modulo K. 389 -- Editor's note: The FEC Scheme specification fully specifies 390 this f function. -- 392 The output Repair Symbol is computed as the XOR sum of each Input 393 Symbol in W multiplied by the corresponding coefficient in row r 394 of G (i.e., the first symbol is multiplied by G[r][0], the second 395 symbol is multiplied by G[r][1], etc. til the last symbol of W). 397 o Transmitted Output Symbol: The FEC Encoding ID is communicated in 398 the DNC packet header. The {Codepoint, TS} tuple can be used to 399 uniquely identify the Repair Symbol produced by the coding 400 process. This tuple is communicated in the DNC packet header. 401 The ESI of each packet currently in W is communicated in the DNC 402 packet header. This information can consist of a list of ESIs, or 403 in the simple case where they are all in sequence, the {first ESI, 404 K} tuple can be communicated, or a sequence of such tuples can be 405 sent in the case where ESIs are mostly in sequence with a limited 406 number of gaps, of the first ESI along with a bit field (e.g., of 407 size 64 bits if K is at most 64) can be communicated. 409 -- Editor's note: Many other pieces of information will be 410 transmitted for other features. The DNC header format also 411 remains TBD. -- 413 o Processing at the decoding node: Upon receiving this Repair 414 Symbol, an additional equation is added to the current linear 415 system. The FEC Encoding ID enables the decoding node to identify 416 the FEC Scheme used by the coding node, as well as the G matrix. 417 The {Codepoint, TS} tuple enables the decoding node to identify 418 the set of coding coefficients used by the coding node. 420 o Decoding process: If the linear system enables it, a decoding 421 process is used to recover an erased Source Symbol. The first two 422 bytes of the decoded symbol is read and used to identify the 423 initial length of the Source Symbol and to remove padding if 424 needed. The decoded Source Symbol is then communicated to the 425 receiving node (or receiving application). 427 6.2. Single Flow with In-network Re-Coding 429 In this use-case, there is a single flow, originated either by a 430 single source or by multiple source for the same content, with in- 431 network re-coding capabilities. There can be either a single path or 432 multiple paths (e.g., if there are multiple sources). There are 433 multiple sub use-cases, among which the following three ones. 435 S ==> CN_1 ==> Router ==> D_1 436 | | source symbols 437 erasures | v 438 +======> CN_2 ==> D_2 440 Figure 2 442 In this first scenario CN_1 et CN_2 are two NC encoders. The flow 443 arriving in CN_2 from the router is impacted by erasures. However 444 this is not the case of the links to destination D_1, that has 445 decoded the packets and this node retransmits the source symbols 446 received or recovered towards D_2. In CN_2 all symbols are 447 recombined and sent to D_2. This could be a scenario that combines 448 wired and wireless paths. 450 Another scenario is the following, where two sources generate some 451 traffic for the same content: 453 S_1 ==> CN_1 ==> CN_3 ==> D_1 454 ^ 455 | 456 S_2 ==> CN_2 =====+ 458 Figure 3 460 Here S_1 and S_2 are transmitting the same content. The flow coming 461 from S_1 (resp. S_2) is encoded at CN_1 (resp. CN_2), and the two 462 encoded flows are later re-encoded in CN_3, a third NC encoder, on 463 their way to D_1. 465 Finally, with a single flow passing through wired and wireless paths, 466 the following scenario is likely. 468 S ==> CN_1 ==> low losses ==> CN_2 ==> high losses ==> D_1 470 Figure 4 472 Between CN_1 and CN_2, the network is a wired internet and a high 473 rate code (i.e., adding a limited number of encoded packets) can be 474 used (e.g., it may be a simple XOR of packets as in QUIC [QUIC]). 475 Between CN_2 et D_1 the link can be a WIFI or LTE wireless network, 476 potentially experiencing higher losses. Consequently a higher number 477 of Repair Symbols (i.e., lower code rate) can be needed, with 478 potentially a local feedback loop that enables to adapt the code rate 479 based on the instantaneous conditions observed over that lossy link. 481 6.3. Other Use Cases 483 Many use-cases remain TBD, for instance to cover the Peer to peer, 484 complex multipath, or storage use-cases. 486 7. Acknowledgements 488 M-J. Montpetit would like to thank Huawei and in particular Shucheng 489 Liu for supporting the work leading to this draft. 491 8. IANA Considerations 493 TBD 495 9. Security Considerations 497 TBD, see RFC 3552 [RFC3552]. 499 10. References 501 10.1. Normative References 503 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 504 Requirement Levels", BCP 14, RFC 2119, March 1997. 506 10.2. Informative References 508 [I-D.adjih-dragoncast] 509 Adjih, C., Cho, S., and E. Baccelli, "Broadcast With 510 Network Coding: DRAGONCAST", draft-adjih-dragoncast-00 511 (work in progress), July 2013. 513 [I-D.detchart-nwcrg-tetrys] 514 jonathan.detchart@isae.fr, j., Lochin, E., Lacan, J., and 515 V. Roca, "Tetrys, an On-the-Fly Network Coding protocol", 516 draft-detchart-nwcrg-tetrys-00 (work in progress), October 517 2014. 519 [ICN] Montpetit, M., Wesphal, C., and D. Trossen, "Network 520 coding meets information-centric networking: an 521 architectural case for information dispersion through 522 native network coding", Proceedings of the 1st ACM 523 workshop on Emerging Name-Oriented Mobile Networking 524 Design - Architecture, Algorithms, and Applications 525 (NOM'2012), June 2012. 527 [QUIC] Roskind, JR., "QUIC: Quick UDP Internet Connections 528 Multiplexed Stream Transport", IETF-88 TSV Area 529 Presentation, November 2013. 531 [RFC3552] Rescorla, E. and B. Korver, "Guidelines for Writing RFC 532 Text on Security Considerations", BCP 72, RFC 3552, July 533 2003. 535 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 536 Correction (FEC) Building Block", RFC 5052, August 2007. 538 [RFC6363] Watson, M., Begen, A., and V. Roca, "Forward Error 539 Correction (FEC) Framework", RFC 6363, October 2011. 541 [RLNC] Ho, T., Koetter, R., Medard, M., Karger, D., Effros, M., 542 Shi, J., and B. Leung, "A Random Linear Network Coding 543 Approach to Multicast", IEEE Transactions on Information 544 Theory Vol. 52 No. 10, October 2006. 546 Appendix A. Appendix: IPR aspects 548 IPR aspects if any to be provided later 550 Authors' Addresses 552 Marie-Jose Montpetit 553 MIT 554 Cambridge, MA 02138 555 USA 557 Email: mariejo@mit.edu 558 Vincent Roca 559 INRIA 560 655, av. de l'Europe 561 Inovallee; Montbonnot 562 ST ISMIER cedex 38334 563 France 565 Email: vincent.roca@inria.fr 566 URI: http://privatics.inrialpes.fr/people/roca/ 568 Jonathan Detchart 569 ISAE 570 10, avenue Edouard-Belin 571 BP 54032 572 Toulouse CEDEX 4 31055 573 France 575 Email: jonathan.detchart@isae.fr