idnits 2.17.1 draft-detchart-nwcrg-tetrys-07.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 (August 11, 2021) is 989 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'REFS' is mentioned on line 274, but not defined -- Looks like a reference, but probably isn't: '3' on line 658 -- Looks like a reference, but probably isn't: '5' on line 658 -- Looks like a reference, but probably isn't: '6' on line 658 -- Looks like a reference, but probably isn't: '8' on line 658 -- Looks like a reference, but probably isn't: '10' on line 658 -- Looks like a reference, but probably isn't: '2' on line 654 -- Looks like a reference, but probably isn't: '1' on line 658 -- Obsolete informational reference (is this intentional?): RFC 7540 (ref. 'HTTP2') (Obsoleted by RFC 9113) == Outdated reference: A later version (-12) exists of draft-irtf-nwcrg-coding-and-congestion-09 -- Obsolete informational reference (is this intentional?): RFC 3452 (ref. 'RMT') (Obsoleted by RFC 5052, RFC 5445) Summary: 0 errors (**), 0 flaws (~~), 3 warnings (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 NWCRG J. Detchart 3 Internet-Draft ISAE-SUPAERO 4 Intended status: Experimental E. Lochin 5 Expires: February 12, 2022 ENAC 6 J. Lacan 7 ISAE-SUPAERO 8 V. Roca 9 INRIA 10 August 11, 2021 12 Tetrys, an On-the-Fly Network Coding protocol 13 draft-detchart-nwcrg-tetrys-07 15 Abstract 17 This document describes Tetrys, an On-The-Fly Network Coding (NC) 18 protocol that can be used to transport delay and loss-sensitive data 19 over a lossy network. Tetrys can recover from erasures within an 20 RTT-independent delay, thanks to the transmission of coded packets. 21 It can be used for both unicast, multicast and anycast 22 communications. 24 Status of This Memo 26 This Internet-Draft is submitted in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at https://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on February 12, 2022. 41 Copyright Notice 43 Copyright (c) 2021 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (https://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 59 1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 3 60 2. Definitions, Notations and Abbreviations . . . . . . . . . . 3 61 3. Architecture . . . . . . . . . . . . . . . . . . . . . . . . 5 62 3.1. Use Cases . . . . . . . . . . . . . . . . . . . . . . . . 5 63 3.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . 5 64 4. Packet Format . . . . . . . . . . . . . . . . . . . . . . . . 6 65 4.1. Common Header Format . . . . . . . . . . . . . . . . . . 6 66 4.1.1. Header Extensions . . . . . . . . . . . . . . . . . . 8 67 4.2. Source Packet Format . . . . . . . . . . . . . . . . . . 9 68 4.3. Coded Packet Format . . . . . . . . . . . . . . . . . . . 10 69 4.4. Acknowledgement Packet Format . . . . . . . . . . . . . . 11 70 5. The Coding Coefficient Generator Identifiers . . . . . . . . 13 71 5.1. Definition . . . . . . . . . . . . . . . . . . . . . . . 13 72 5.2. Table of Identifiers . . . . . . . . . . . . . . . . . . 13 73 6. Tetrys Basic Functions . . . . . . . . . . . . . . . . . . . 13 74 6.1. Encoding . . . . . . . . . . . . . . . . . . . . . . . . 13 75 6.1.1. Encoding Vector Formats . . . . . . . . . . . . . . . 14 76 6.2. The Elastic Encoding Window . . . . . . . . . . . . . . . 17 77 6.3. Recoding . . . . . . . . . . . . . . . . . . . . . . . . 18 78 6.3.1. Principle . . . . . . . . . . . . . . . . . . . . . . 18 79 6.3.2. Generating a coded symbol at an intermediate node . . 18 80 6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . 18 81 7. Research Issues . . . . . . . . . . . . . . . . . . . . . . . 18 82 7.1. Interaction with Existing Congestion-Controlled Transport 83 Protocol . . . . . . . . . . . . . . . . . . . . . . . . 19 84 7.2. Adaptive Coding Rate . . . . . . . . . . . . . . . . . . 19 85 7.3. Using Tetrys Above The IP Layer For Tunneling . . . . . . 19 86 8. Security Considerations . . . . . . . . . . . . . . . . . . . 20 87 9. Privacy Considerations . . . . . . . . . . . . . . . . . . . 20 88 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 89 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 20 90 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 20 91 12.1. Normative References . . . . . . . . . . . . . . . . . . 20 92 12.2. Informative References . . . . . . . . . . . . . . . . . 20 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 95 1. Introduction 97 This document describes Tetrys, a novel network coding protocol. 98 Network codes were introduced in the early 2000s [AHL-00] to address 99 the limitations of transmission over the Internet (delay, capacity 100 and packet loss). While the use of network codes is fairly recent in 101 the Internet community, the use of application layer erasure codes in 102 the IETF has already been standardized in the RMT [RMT] and the 103 FECFRAME [FECFRAME] working groups. The protocol presented here can 104 be seen as a network coding extension to standards solutions. The 105 current proposal can be considered a combination of network erasure 106 coding and feedback mechanisms [Tetrys]. 108 The main innovation of the Tetrys protocol is in the generation of 109 coded packets from an elastic encoding window periodically updated 110 with the receiver's feedbacks. This update is done in so that any 111 source packets coming from an input flow are included in the encoding 112 window as long as it is not acknowledged or the encoding window did 113 not reach a size limit. This mechanism allows for losses on both the 114 forward and return paths and in particular, is resilient to 115 acknowledgment losses. 117 With Tetrys, a coded packet is a linear combination over a finite 118 field of the data source packets belonging to the coding window. The 119 coefficients finite field's choice is a trade-off between the best 120 performance (with non-binary coefficients) and the system constraints 121 (binary codes in an energy-constrained environment) and is driven by 122 the application. 124 Thanks to the elastic encoding window, the coded packets are built 125 on-the-fly, by using an algorithm or a function to choose the 126 coefficients. The redundancy ratio can be dynamically adjusted, and 127 the coefficients can be generated in different ways along with a 128 transmission. Compared to FEC block codes, this allows reducing the 129 bandwidth use and the decoding delay. 131 1.1. Requirements Notation 133 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 134 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 135 document are to be interpreted as described in [RFC2119]. 137 2. Definitions, Notations and Abbreviations 139 The terminology used in this document is presented below. It is 140 aligned with the FECFRAME terminology conjointly with recent 141 activities in the Network Coding Research Group. 143 Source symbol: a symbol that has to be transmitted between the 144 ingress and egress of the network. 146 Coded symbol: a linear combination over a finite field of a set of 147 source symbols. 149 Source symbol ID: a sequence number to identify the source 150 symbols. 152 Coded symbol ID: a sequence number to identify the coded symbols. 154 Encoding coefficients: elements of the finite field characterizing 155 the linear combination used to generate coded symbols. 157 Encoding vector: a set of the encoding coefficients and input 158 source symbol IDs. 160 Source packet: a source packet contains a source symbol with its 161 associated IDs. 163 Coded packet: a coded packet contains a coded symbol, the coded 164 symbol's ID, and encoding vector. 166 Input symbol: a symbol at the input of the Tetrys Encoding 167 Building Block. 169 Output symbol: a symbol generated by the Tetrys Encoding Building 170 Block. For a non-systematic mode, all output symbols are coded 171 symbols. For a systematic mode, output symbols can be the input 172 symbols and a number of coded symbols that are linear combinations 173 of the input symbols + the encoding vectors. 175 Feedback packet: a feedback packet is a packet containing 176 information about the decoded or received source symbols. It can 177 also bring additional information about the Packet Error Rate or 178 the number of various packets in the receiver decoding window. 180 Elastic Encoding Window: an encoder-side buffer that stores all 181 the non-acknowledged source packets of the input flow involved in 182 the coding process. 184 Coding Coefficient Generator Identifier: a unique identifier that 185 defines a function or an algorithm allowing to generate the 186 encoding vector. 188 Code rate: Define the rate between the number of input symbols and 189 the number of output symbols. 191 3. Architecture 193 -- Editor's note: The architecture used in this document should be 194 aligned with the future NC Architecture document [NWCRG-ARCH]. -- 196 3.1. Use Cases 198 Tetrys is well suited, but not limited to the use case where there is 199 a single flow originated by a single source, with intra stream coding 200 at a single encoding node. Note that the input stream can be a 201 multiplex of several upper layer streams. Transmission can be over a 202 single path or multiple paths. Besides, the flow can be sent in 203 unicast, multicast, or anycast mode. This is the simplest use-case, 204 that is very much aligned with currently proposed scenarios for end- 205 to-end streaming. 207 3.2. Overview 209 +----------+ +----------+ 210 | | | | 211 | App | | App | 212 | | | | 213 +----------+ +----------+ 214 | ^ 215 | source source | 216 | symbols symbols | 217 | | 218 v | 219 +----------+ +----------+ +----------+ 220 | | output packets | | output packets | | 221 | Tetrys |--------------->| Tetrys |--------------->| Tetrys | 222 | Encoder |feedback packets| Recoder |feedback packets| Decoder | 223 | |<---------------| |<---------------| | 224 +----------+ +----------+ +----------+ 226 Figure 1: Tetrys Architecture 228 The Tetrys protocol features several key functionalities: 230 o On-the-fly encoding; 232 o Recoding; 234 o Decoding; 236 o Signaling, to carry in particular the symbol identifiers in the 237 encoding window and the associated coding coefficients when 238 meaningful, in a manner that was previously used in FEC; 240 o Feedback management; 242 o Elastic window management; 244 o Channel estimation; 246 o Dynamic adjustment of the code rate and flow control; 248 o Congestion control management (if appropriate); 250 -- Editor's note: must be discussed -- 252 o Tetrys packet header creation and processing; 254 o -- Editor's note: something else? -- 256 Several building blocks provide these functionalities: 258 o The Tetrys Building Block: this BB is used during encoding, 259 recoding, and decoding processes. It must be noted that Tetrys 260 does not mandate a specific building block. Instead, any building 261 block compatible with the elastic encoding window feature of 262 Tetrys can be used. 264 o The Window Management Building Block: this building block is in 265 charge of managing the encoding window at a Tetrys sender. 267 -- Editor's note: Is it worth moving it in a dedicated BB? To 268 be discussed -- 270 o Other ? 272 To ease the addition of future components and services, Tetrys adds a 273 header extension mechanism, compatible with that of LCT, NORM, 274 FECFRAME [REFS]. 276 4. Packet Format 278 4.1. Common Header Format 280 All types of Tetrys packets share the same common header format (see 281 Figure 2). 283 0 1 2 3 284 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 285 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 286 | V | C |S| Reserved | HDR_LEN | Packet Type | 287 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 288 | Congestion Control Information (CCI, length = 32*C bits) | 289 | ... | 290 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 291 | Transport Session Identifier (TSI, length = 32*S bits) | 292 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 293 | Header Extensions (if applicable) | 294 | ... | 295 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 297 Figure 2: Common Header Format 299 -- Editor's note: this format inherits from the LCT header format 300 (RFC 5651) with slight modifications. -- 302 o Tetrys version number (V): 4 bits. Indicates the Tetrys version 303 number. The Tetrys version number for this specification is 1. 305 o Congestion control flag (C): 2 bits. C=0 indicates the Congestion 306 Control Information (CCI) field is 0 bits in length. C=1 307 indicates the CCI field is 32 bits in length. C=2 indicates the 308 CCI field is 64 bits in length. C=3 indicates the CCI field is 96 309 bits in length. 311 -- Editor's note: version number and congestion control to be 312 discussed -- 314 o Transport Session Identifier flag (S): 1 bit. This is the number 315 of full 32-bit words in the TSI field. The TSI field is 32*S bits 316 in length, i.e., the length is either 0 bits or 32 bits. 318 o Reserved (Resv): 9 bits. These bits are reserved. In this 319 version of the specification, they MUST be set to zero by senders 320 and MUST be ignored by receivers. 322 o Header length (HDR_LEN): 8 bits. The total length of the Tetrys 323 header in units of 32-bit words. The length of the Tetrys header 324 MUST be a multiple of 32 bits. This field can be used to directly 325 access the portion of the packet beyond the Tetrys header, i.e., 326 to the first next header if it exists, or to the packet payload if 327 it exists and there is no other header, or to the end of the 328 packet if there are no other headers or packet payload. 330 o Packet Type: 8 bits. Type of packet. 332 o Congestion Control Information (CCI): 0, 32, 64, or 96 bits Used 333 to carry congestion control information. For example, the 334 congestion control information could include layer numbers, 335 logical channel numbers, and sequence numbers. This field is 336 opaque for this specification. This field MUST be 0 bits (absent) 337 if C=0. This field MUST be 32 bits if C=1. This field MUST be 64 338 bits if C=2. This field MUST be 96 bits if C=3. 340 o Transport Session Identifier (TSI): 0 or 32 bits The TSI uniquely 341 identifies a session among all sessions from a particular sender. 342 The TSI is scoped by the IP address of the sender, and thus the IP 343 address of the sender and the TSI together uniquely identify the 344 session. Although a TSI in conjunction with the IP address of the 345 sender always uniquely identifies a session, whether or not the 346 TSI is included in the Tetrys header depends on what is used as 347 the TSI value. If the underlying transport is UDP, then the 348 16-bit UDP source port number MAY serve as the TSI for the 349 session. If there is no underlying TSI provided by the network, 350 transport or any other layer, then the TSI MUST be included in the 351 Tetrys header. 353 4.1.1. Header Extensions 355 Header Extensions are used in Tetrys to accommodate optional header 356 fields that are not always used or have variable size. The presence 357 of Header Extensions can be inferred by the Tetrys header length 358 (HDR_LEN). If HDR_LEN is larger than the length of the standard 359 header, then the remaining header space is taken by Header 360 Extensions. 362 If present, Header Extensions MUST be processed to ensure that they 363 are recognized before performing any congestion control procedure or 364 otherwise accepting a packet. The default action for unrecognized 365 Header Extensions is to ignore them. This allows the future 366 introduction of backward-compatible enhancements to Tetrys without 367 changing the Tetrys version number. Non-backward-compatible Header 368 Extensions CANNOT be introduced without changing the Tetrys version 369 number. 371 There are two formats for Header Extensions, as depicted in Figure 3. 372 The first format is used for variable-length extensions, with Header 373 Extension Type (HET) values between 0 and 127. The second format is 374 used for fixed-length (one 32-bit word) extensions, using HET values 375 from 128 to 255. 377 0 1 2 3 378 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 379 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 380 | HET (<=127) | HEL | | 381 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 382 . . 383 . Header Extension Content (HEC) . 384 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 386 0 1 2 3 387 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 388 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 389 | HET (>=128) | Header Extension Content (HEC) | 390 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 392 Figure 3: Header Extension Format 394 o Header Extension Type (HET): 8 bits The type of the Header 395 Extension. This document defines several possible types. 396 Additional types may be defined in future versions of this 397 specification. HET values from 0 to 127 are used for variable- 398 length Header Extensions. HET values from 128 to 255 are used for 399 fixed-length 32-bit Header Extensions. 401 o Header Extension Length (HEL): 8 bits The length of the whole 402 Header Extension field, expressed in multiples of 32-bit words. 403 This field MUST be present for variable-length extensions (HETs 404 between 0 and 127) and MUST NOT be present for fixed-length 405 extensions (HETs between 128 and 255). 407 o Header Extension Content (HEC): variable length The content of the 408 Header Extension. The format of this sub-field depends on the 409 Header Extension Type. For fixed-length Header Extensions, the 410 HEC is 24 bits. For variable-length Header Extensions, the HEC 411 field has variable size, as specified by the HEL field. Note that 412 the length of each Header Extension MUST be a multiple of 32 bits. 413 Also, note that the total size of the Tetrys header, including all 414 Header Extensions and all optional header fields, cannot exceed 415 255 32-bit words. 417 4.2. Source Packet Format 419 A source packet is a Common Packet Header encapsulation, a Source 420 Symbol ID and a source symbol (payload). The source symbols can have 421 variable sizes. 423 0 1 2 3 424 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 425 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 426 | | 427 / Common Packet Header / 428 | | 429 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 430 | Source Symbol ID | 431 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 432 | | 433 / Payload / 434 | | 435 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 437 Figure 4: Source Packet Format 439 Common Packet Header: a common packet header (as common header 440 format) where Packet Type=0. 442 Source Symbol ID: the sequence number to identify a source symbol. 444 Payload: the payload (source symbol) 446 4.3. Coded Packet Format 448 A coded packet is the encapsulation of a Common Packet Header, a 449 Coded Symbol ID, the associated Encoding Vector, and a coded symbol 450 (payload). As the source symbols CAN have variable sizes, each 451 source symbol size need to be encoded. The result must be stored in 452 the coded packet as the Encoded Payload Size (16 bits): as it is an 453 optional field, the encoding vector MUST signal the use of variable 454 source symbol sizes with the field V (see Section 6.1.1.2). 456 0 1 2 3 457 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 458 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 459 | | 460 / Common Packet Header / 461 | | 462 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 463 | Coded Symbol ID | 464 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 465 | | 466 / Encoding Vector / 467 | | 468 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 469 | Encoded Payload Size | | 470 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 471 | | 472 / Payload / 473 | | 474 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 476 Figure 5: Coded Packet Format 478 Common Packet Header: a common packet header (as common header 479 format) where Packet Type=1. 481 Coded Symbol ID: the sequence number to identify a coded symbol. 483 Encoding Vector: an encoding vector to define the linear combination 484 used (coefficients and source symbols). 486 Encoded Payload Size: the coded payload size used if the source 487 symbols have a variable size (optional, Section 6.1.1.2)). 489 Payload: the coded symbol. 491 4.4. Acknowledgement Packet Format 493 A Tetrys Decoding Building Block or Tetrys Recoding Building Block 494 MAY send back to another building block some Acknowledgement packets. 495 They contain information about what it has received and/or decoded, 496 and other information such as a packet loss rate or the size of the 497 decoding buffers. The acknowledgment packets are OPTIONAL hence they 498 could be omitted or lost in transmission without impacting the 499 protocol behavior. 501 0 1 2 3 502 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 503 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 504 | | 505 / Common Packet Header / 506 | | 507 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 508 | Nb of missing source symbols | 509 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 510 | Nb of not already used coded symbols | 511 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 512 | First Source Symbol ID | 513 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 514 | PLR | SACK size | | 515 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 516 | | 517 / SACK Vector / 518 | | 519 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 521 Figure 6: Acknowledgement Packet Format 523 Common Packet Header: a common packet header (as common header 524 format) where Packet Type=2. 526 Nb missing source symbols: the number of missing source symbols in 527 the receiver since the beginning of the session. 529 Nb of not already used coded symbols: the number of coded symbols at 530 the receiver that have not already been used for decoding (e.g., the 531 linear combinations contain at least 2 unknown source symbols). 533 First Source Symbol ID: ID of the first source symbol to consider for 534 acknowledgment. 536 PLR: packet loss ratio expressed as a percentage. 538 SACK size: the size of the SACK vector in 32-bit words. For 539 instance, with value 2, the SACK vector is 64 bits long. 541 SACK vector: bit vector indicating the acknowledged symbols from the 542 first source symbol ID. The "First Source Symbol" is included in 543 this bit vector. A bit equal to 1 at the i-th position means that 544 this acknowledgment packet acknowledges the source symbol of ID equal 545 to "First Source Symbol ID" + i. 547 5. The Coding Coefficient Generator Identifiers 549 5.1. Definition 551 The Coding Coefficient Generator Identifiers define a function or an 552 algorithm to build the coding coefficients used to generate the coded 553 symbols. They MUST be known by all the Tetrys encoders, recoders or 554 decoders. 556 5.2. Table of Identifiers 558 0000: GF2 (or GF(2**1)) Vandermonde based coefficients. Each 559 coefficient is built as alpha^( (source_symbol_id*coded-symbol_id) % 560 2). 562 0001: GF16 (or GF(2**4)) Vandermonde based coefficients. Each 563 coefficient is built as alpha^( (source_symbol_id*coded-symbol_id) % 564 16). 566 0010: GF256 (or GF(2**8)) Vandermonde based coefficients. Each 567 coefficient is built as alpha^( (source_symbol_id*coded_symbol_id) % 568 256). 570 0011: SRLC. 572 Others: To be discussed. 574 6. Tetrys Basic Functions 576 6.1. Encoding 578 At the beginning of a transmission, a Tetrys Encoding Building Block 579 or MUST choose an initial code rate (added redundancy) as it doesn't 580 know the packet loss rate of the channel. In the steady state, 581 depending on the code-rate, the Tetrys Encoding Building Block CAN 582 generate coded symbols when it receives a source symbol from the 583 application or some feedback from the decoding or recoding blocks. 585 When a Tetrys Encoding Building Block needs to generate a coded 586 symbol, it considers the set of source symbols stored in the Elastic 587 Encoding Window. These source symbols are the set of source symbols 588 that are not yet acknowledged by the receiver. 590 A Tetrys Encoding Building Block SHOULD set a limit to the Elastic 591 Encoding Window maximum size. This controls the algorithmic 592 complexity at the encoder and decoder by limiting the size of linear 593 combinations. It is also needed in situations where acknowledgment 594 packets are all lost or absent. 596 At the generation of a coded symbol, the Tetrys Encoding Building 597 Block generates an encoding vector containing the IDs of the source 598 symbols stored in the Elastic Encoding Window. For each source 599 symbol, a finite field coefficient is determined using a Coding 600 Coefficient Generator. This generator CAN take as input the source 601 symbol ID and the coded symbol ID and CAN determine a coefficient in 602 a deterministic way. A typical example of such a deterministic 603 function is a generator matrix where the rows are indexed by the 604 source symbol IDs and the columns by the coded symbol IDs. For 605 example, the entries of this matrix can be built from a Vandermonde 606 structure, like Reed-Solomon codes, or a sparse binary matrix, like 607 Low-Density Generator Matrix codes. Finally, the coded symbol is the 608 sum of the source symbols multiplied by their corresponding 609 coefficients. 611 6.1.1. Encoding Vector Formats 613 Each coded packet contains an encoding vector. The encoding vectors 614 CAN contain the ID and/or coefficient of each source symbol contained 615 in the coded symbol. 617 6.1.1.1. Transmitting the source symbol IDs 619 The source symbol IDs are organized as a sorted list of 32-bit 620 unsigned integers. Depending on the feedback, the source symbol IDs 621 can be successive or not in the list. 623 If they are successive, the boundaries are stored in the encoding 624 vector: it just needs 2*32-bit of information. 626 If not, the edge blocks CAN be stored directly, or a differential 627 transform to reduce the number of bits needed to represent an ID CAN 628 be used. 630 6.1.1.1.1. Compressed list of Source symbol IDs 632 Assume the symbol IDs used in the combination are: 633 [1..3],[5..6],[8..10]. 635 1. Keep the first element in the packet as the first_source_id: 1. 637 2. Apply a differential transform to the others elements 638 ([3,5,6,8,10]) which removes the element i-1 to the element i, 639 starting with the first_source_id as i0, and get the list L => 640 [2,2,1,2,2] 642 3. Compute b, the number of bits needed to store all the elements, 643 which is ceil(log2(max(L))): here, 2 bits. 645 4. Write b in the corresponding field, and write all the b * [(2 * 646 NB blocks) - 1] elements in a bit vector, here: 10 10 01 10 10. 648 6.1.1.1.2. Decompressing the Source symbol IDs 650 When a Tetrys Decoding Building Block wants to reverse the 651 operations, this algorithm is used: 653 1. Rebuild the list of the transmitted elements by reading the bit 654 vector and b: [10 10 01 10 10] => [2,2,1,2,2] 656 2. Apply the reverse transform by adding successively the elements, 657 starting with first_source_id: [1,1+2,(1+2)+2,(1+2+2)+1,...] => 658 [1,3,5,6,8,10] 660 3. Rebuild the blocks using the list and first_source_id: 661 [1..3],[5..6],[8..10]. 663 6.1.1.2. Encoding Vector Format 665 The encoding vector CAN be used to store the source symbol IDs 666 included in the associated coded symbol, the coefficients used in the 667 combination, or both. It CAN be used to send only the number of 668 source symbols included in the coded symbol. 670 If the source IDs are stored, the number of blocks MUST be different 671 from 0. 673 The encoding vector format uses a 4-bit Coding Coefficient Generator 674 Identifier to identify the algorithm to generate the coefficients. 675 It contains a set of blocks for the source symbol IDs used in the 676 combination. In this format, the number of blocks is stored as a 677 8-bit unsigned integer. To reduce the overhead, a compressed way to 678 store the symbol IDs is used: the IDs are not stored as themselves 679 but stored as the difference between the previous. 681 0 1 2 3 682 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 683 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 684 | EV_LEN | CCGI | I |C|V| NB_IDS | NB_COEFS | 685 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 686 | FIRST_SOURCE_ID | 687 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 688 | b_id | | 689 +-+-+-+-+-+-+-+-+ id_bit_vector +-+-+-+-+-+-+-+ 690 | | Padding | 691 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 692 | b_coef | | 693 +-+-+-+-+-+-+-+-+ coef_bit_vector +-+-+-+-+-+-+-+ 694 | | Padding | 695 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 697 Figure 7: Encoding Vector Format 699 o Encoding Vector Length (EV_LEN) (8-bits): size in units of 32-bit 700 words. 702 o Coding Coefficient Generator Identifier (CCGI): 4-bit ID to 703 identify the algorithm or the function used to generate the 704 coefficients (see Section 5). As a CCGI is included in each 705 encoded vector, it can dynamically change between the generation 706 of 2 coded symbols. 708 o Store the Source symbol IDs (I) (2 bits): 710 * 00 means there is no source symbol ID information. 712 * 01 means the encoding vector contains the edge blocks of the 713 source symbol IDs without compression. 715 * 10 means the encoding vector contains the compressed list of 716 the source symbol IDs. 718 * 11 means the encoding vector contains the compressed edge 719 blocks of the source symbol IDs. 721 o Store the coefficients (C): 1 bit to know if an encoding vector 722 contains information about the coefficients used. 724 o Having source symbols with variable size (V): set V to 1 if the 725 combination which refers to the encoding vector is a combination 726 of source symbols with variable sizes. In this case, the coded 727 packets MUST have the 'Encoded Payload Size' field. 729 o Number of IDs used to store the source symbol IDs (NB_IDS): the 730 number of IDs stored (depending on I). 732 o Number of coefficients (NB_COEFS): The number of the coefficients 733 used to generate the associated coded symbol. 735 o The first source Identifier (FIRST_SOURCE_ID): the first source 736 symbol ID used in the combination. 738 o Number of bits for each edge block (b_id): the number of bits 739 needed to store the edge (see Section 6.1.1.1). 741 o Information about the source symbol IDs (id_bit_vector): if I=01, 742 store the edge blocks as b_id * (NB_IDS * 2 - 1). If I=10, store 743 in a compressed way the edge blocks. 745 o Number of bits needed to store each coefficient (b_coef): the 746 number of bits used to store the coefficients. 748 o The coefficients (coef_bit_vector): The coefficients stored (as a 749 vector of b_coef * NB_COEFS). 751 o Padding: padding to have an Encoding Vector size multiple of 752 32-bit (for the id and coefficient part). 754 6.2. The Elastic Encoding Window 756 When an input source symbol is passed to a Tetrys Encoding Building 757 Block, it is added to the Elastic Encoding Window. This window MUST 758 have a limit set by the encoding building Block (depending on the use 759 case: unicast, multicast, file transfer, real-time transfer, ...). 760 If the Elastic Encoding Window reached its limit, the window slides 761 over the symbols: the first (oldest) symbols are removed. Then, a 762 packet containing this symbol can be sent onto the network. As an 763 element of the coding window, this symbol is included in the next 764 linear combinations created to generate the coded symbols. 766 As explained below, the receiver or the recoder sends periodic 767 feedback indicating the received or decoded source symbols. In the 768 case of unicast transmission, when the sender receives the 769 information that a source symbol was received and/or decoded by the 770 receiver, it removes this symbol from the coding window. 772 In a multicast transmission: 774 o If the acknowledgment packets are not enabled, the coding window 775 grows up to a limit. When the limit is reached, the oldest 776 symbols are removed from the coding window. 778 o If the acknowledgment packets are enabled, a source symbol is 779 removed from the coding window when all the receivers have 780 received or decoded it or when the coding window reaches its 781 limit. 783 6.3. Recoding 785 6.3.1. Principle 787 A Tetrys Recoding Block maintains a list of the ID of the source 788 symbols included in the Elastic Coding Window of the sender. It also 789 stores a set of received source and coded symbols able to regenerate 790 the set or a subset of the Elastic Coding Window symbols. In other 791 words, if R1, ..., Rt represent t received symbols and S1, ..., Sk 792 represent the set or a subset of the source symbols of the Elastic 793 Coding Window, there exists a t*k-matrix M such that (R1, ..., Rt).M 794 = (S1, ..., Sk). 796 6.3.2. Generating a coded symbol at an intermediate node 798 At the generation of a coded symbol, the Tetrys Recoding Building 799 Block generates an encoding vector containing the IDs of the source 800 symbols stored in the Elastic Encoding Window or in the subset of the 801 Elastic Encoding Window that it can regenerate. The Tetrys Recoding 802 Building Block then generates a new coded symbol ID different from 803 the received coded symbol IDs. From this coded symbol ID and the 804 source symbol IDs of (S1, ..., Sk), a finite field coefficient is 805 determined using a Coding Coefficient Generator. Let (a1, ...,ak) 806 denote the obtained coefficients. To compute the linear combination 807 (s1, ..., Sk).transpose(a1, ..., ak) the Tetrys Recoding Building 808 block computes the vector v = (a1, ...,ak).transpose(M) and then 809 computes the coded symbol R = (R1, ..., Rt).transpose(v). It can be 810 verified that the new coded symbol is obtained without any decoding 811 operation. 813 6.4. Decoding 815 A classical matrix inversion is sufficient to recover the source 816 symbols. 818 7. Research Issues 820 The design of Tetrys protocol presented in this document provides the 821 baseline allowing communication between a Tetrys encoder and a Tetrys 822 decoder. At this stage, the detailed specifications only focus on 823 the coding and decoding aspects. The objective of this document is 824 first to provide guidelines to implement Tetrys as a standalone 825 protocol or to embed Tetrys inside an existing protocol at the 826 application layer or the IP layer. However, both cases raise 827 manifold research efforts to come up with a complete protocol 828 specification. Despite mandatory communication protocol operations 829 such as opening/closing procedures and timeout/reset, we identified 830 the following research issues that would need further discussion. 832 7.1. Interaction with Existing Congestion-Controlled Transport Protocol 834 Tetrys coding and congestion control can be seen as two separate 835 channels. In practice, implementations may mix the signals exchanged 836 on these channels. This raises several concerns that must be tackled 837 when considering using Tetrys conjointly with a congestion-controlled 838 transport protocol. All these numerous research issues are discussed 839 in a separate document [I-D.irtf-nwcrg-coding-and-congestion]. In 840 particular, this document investigates end-to-end unicast data 841 transfer with FEC coding in the application (above the transport), 842 within the transport, or directly below the transport; the 843 relationship between transport layer and application requirements; 844 and the case of transport multipath and multi-streams applications. 846 7.2. Adaptive Coding Rate 848 In a particular context, a redundancy adaptation algorithm might be 849 considered helpful or mandatory when the network condition (e.g., 850 delay, loss rate) strongly varies over time. Hence, it requires an 851 enhanced mechanism for erasure codes to adapt to network dynamics 852 similarly to [A-FEC]. However, the dynamic adaptation of an on-the- 853 fly coding rate is slightly more complex than a block code. 854 Furthermore, this adaptation can be done conjointly with the network 855 as proposed in [RED-FEC]. In this paper, the authors propose a 856 Random Early Detection FEC mechanism in the context of video 857 transmission over wireless networks. In brief, the idea is to add 858 more redundancy packets if the queue at the access point is less 859 occupied and vice versa. A first theoretical attempt for video 860 delivery has been proposed [THAI] with Tetrys. However, this kind of 861 algorithms should deserve more research to be deployed in practice. 863 7.3. Using Tetrys Above The IP Layer For Tunneling 865 The use of Tetrys to protect from losses an aggregate of flows raise 866 various issues. This occurs when an encoding mechanism is enabled 867 below the IP layer and builds redundancy without flows 868 differentiation. This is typically the case in a tunnel. The main 869 problem relates to head-of-line blocking when decoding multiple 870 flows. The number of source packets might vary following their own 871 loss probability and lead to decoding blocking in waiting for source 872 data packets to be suppressed from a given repair packet. This kind 873 of issue could lead to a decrease of the decoding performance and 874 should be further investigated. Note this research issue joins the 875 topics discussed in the IRTF LOOPS working group 876 [I-D.li-tsvwg-loops-problem-opportunities]. 878 8. Security Considerations 880 Tetrys inherits a subset of the security issues described as those 881 described in FECFRAME [FECFRAME] and in particular in sections 882 "9.2.2. Content Corruption" and "9.3. Attacks against the FEC 883 Parameters". As an application layer end-to-end protocol, security 884 considerations of Tetrys should also be comparable to those of HTTP/2 885 with TLS. The considerations from Section 10 of HTTP2 [HTTP2] also 886 apply in addition to those listed here. 888 9. Privacy Considerations 890 N/A 892 10. IANA Considerations 894 N/A 896 11. Acknowledgments 898 First, the authors want to sincerely thank Marie-Jose Montpetit for 899 continuous help and support on Tetrys. Marie-Jo, many thanks! 901 The authors also wish to thank NWCRG group members for numerous 902 discussions on on-the-fly coding that helped finalize this document. 904 12. References 906 12.1. Normative References 908 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 909 Requirement Levels", BCP 14, RFC 2119, 910 DOI 10.17487/RFC2119, March 1997, 911 . 913 12.2. Informative References 915 [A-FEC] Bolot, J., Fosse-Parisis, S., and D. Towsley, "Adaptive 916 FEC-based error control for Internet telephony", IEEE 917 INFOCOM 99, pp. 1453-1460 vol. 3 DOI 918 10.1109/INFCOM.1999.752166, 1999. 920 [AHL-00] Ahlswede, R., Ning Cai, Li, S., and R. Yeung, "Network 921 information flow", IEEE Transactions on Information 922 Theory vol.46, no.4, pp.1204,1216, July 2000. 924 [FECFRAME] 925 Watson, M., Begen, A., and V. Roca, "Forward Error 926 Correction (FEC) Framework", Request for Comments 6363, 927 October 2011. 929 [HTTP2] Belshe, M., Peon, R., and M. Thomson, "Hypertext Transfer 930 Protocol Version 2 (HTTP/2)", Request for Comments 7540, 931 October 2015. 933 [I-D.irtf-nwcrg-coding-and-congestion] 934 Kuhn, N., Lochin, E., Michel, F., and M. Welzl, "Coding 935 and congestion control in transport", draft-irtf-nwcrg- 936 coding-and-congestion-09 (work in progress), June 2021. 938 [I-D.li-tsvwg-loops-problem-opportunities] 939 Li, Y., Zhou, X., Boucadair, M., Wang, J., and F. Qin, 940 "LOOPS (Localized Optimizations on Path Segments) Problem 941 Statement and Opportunities for Network-Assisted 942 Performance Enhancement", draft-li-tsvwg-loops-problem- 943 opportunities-06 (work in progress), July 2020. 945 [NWCRG-ARCH] 946 NWCRG, "Network Coding Architecture", TBD TBD. 948 [RED-FEC] Lin, C., Shieh, C., Chilamkurti, N., Ke, C., and H. Hwang, 949 "A RED-FEC Mechanism for Video Transmission Over WLANs", 950 IEEE Transactions on Broadcasting, vol. 54, no. 3, pp. 951 517-524 DOI 10.1109/TBC.2008.2001713, September 2008. 953 [RMT] Vicisano, L., Gemmel, J., Rizzo, L., Handley, M., and J. 954 Crowcroft, "Forward Error Correction (FEC) Building 955 Block", Request for Comments 3452, December 2002. 957 [Tetrys] Lacan, J. and E. Lochin, "Rethinking reliability for long- 958 delay networks", International Workshop on Satellite and 959 Space Communications 2008 (IWSSC08), October 2008. 961 [THAI] Tran-Thai, T., Lacan, J., and E. Lochin, "Joint on-the-fly 962 network coding/video quality adaptation for real-time 963 delivery", Signal Processing: Image Communication, vol. 29 964 (no. 4), pp. 449-461 ISSN 0923-5965, 2014. 966 Authors' Addresses 968 Jonathan Detchart 969 ISAE-SUPAERO 970 10, avenue Edouard Belin 971 BP 54032 972 Toulouse CEDEX 4 31055 973 France 975 Email: jonathan.detchart@isae-supaero.fr 977 Emmanuel Lochin 978 ENAC 979 7, avenue Edouard Belin 980 Toulouse 31400 981 France 983 Email: emmanuel.lochin@enac.fr 985 Jerome Lacan 986 ISAE-SUPAERO 987 10, avenue Edouard Belin 988 BP 54032 989 Toulouse CEDEX 4 31055 990 France 992 Email: jerome.lacan@isae-supaero.fr 994 Vincent Roca 995 INRIA 996 655, avenue de l'Europe 997 Inovallee; Montbonnot 998 ST ISMIER cedex 38334 999 France 1001 Email: vincent.roca@inria.fr