idnits 2.17.1 draft-detchart-nwcrg-tetrys-05.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 (February 27, 2020) is 1520 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'REFS' is mentioned on line 267, but not defined -- Looks like a reference, but probably isn't: '3' on line 651 -- Looks like a reference, but probably isn't: '5' on line 651 -- Looks like a reference, but probably isn't: '6' on line 651 -- Looks like a reference, but probably isn't: '8' on line 651 -- Looks like a reference, but probably isn't: '10' on line 651 -- Looks like a reference, but probably isn't: '2' on line 647 -- Looks like a reference, but probably isn't: '1' on line 651 -- Obsolete informational reference (is this intentional?): RFC 7540 (ref. 'HTTP2') (Obsoleted by RFC 9113) -- Obsolete informational reference (is this intentional?): RFC 3452 (ref. 'RMT') (Obsoleted by RFC 5052, RFC 5445) Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 NWCRG J. Detchart 3 Internet-Draft E. Lochin 4 Intended status: Experimental J. Lacan 5 Expires: August 30, 2020 ISAE-SUPAERO 6 V. Roca 7 INRIA 8 February 27, 2020 10 Tetrys, an On-the-Fly Network Coding protocol 11 draft-detchart-nwcrg-tetrys-05 13 Abstract 15 This document describes Tetrys, an On-The-Fly Network Coding (NC) 16 protocol that can be used to transport delay and loss sensitive data 17 over a lossy network. Tetrys can recover from erasures within a RTT- 18 independent delay, thanks to the transmission of coded packets. It 19 can be used for both unicast, multicast and anycast communications. 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 https://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 August 30, 2020. 38 Copyright Notice 40 Copyright (c) 2020 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 (https://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 1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 3 57 2. Definitions, Notations and Abbreviations . . . . . . . . . . 3 58 3. Architecture . . . . . . . . . . . . . . . . . . . . . . . . 4 59 3.1. Use Cases . . . . . . . . . . . . . . . . . . . . . . . . 4 60 3.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . 5 61 4. Packet Format . . . . . . . . . . . . . . . . . . . . . . . . 6 62 4.1. Common Header Format . . . . . . . . . . . . . . . . . . 6 63 4.1.1. Header Extensions . . . . . . . . . . . . . . . . . . 8 64 4.2. Source Packet Format . . . . . . . . . . . . . . . . . . 9 65 4.3. Coded Packet Format . . . . . . . . . . . . . . . . . . . 10 66 4.4. Acknowledgement Packet Format . . . . . . . . . . . . . . 11 67 5. The Coding Coefficient Generator Identifiers . . . . . . . . 13 68 5.1. Definition . . . . . . . . . . . . . . . . . . . . . . . 13 69 5.2. Table of Identifiers . . . . . . . . . . . . . . . . . . 13 70 6. Tetrys Basic Functions . . . . . . . . . . . . . . . . . . . 13 71 6.1. Encoding . . . . . . . . . . . . . . . . . . . . . . . . 13 72 6.1.1. Encoding Vector Formats . . . . . . . . . . . . . . . 14 73 6.2. The Elastic Encoding Window . . . . . . . . . . . . . . . 17 74 6.3. Recoding . . . . . . . . . . . . . . . . . . . . . . . . 18 75 6.3.1. Principle . . . . . . . . . . . . . . . . . . . . . . 18 76 6.3.2. Generating a coded symbol at an intermediate node . . 18 77 6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . 18 78 7. Security Considerations . . . . . . . . . . . . . . . . . . . 18 79 8. Privacy Considerations . . . . . . . . . . . . . . . . . . . 19 80 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 81 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 19 82 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 83 11.1. Normative References . . . . . . . . . . . . . . . . . . 19 84 11.2. Informative References . . . . . . . . . . . . . . . . . 19 85 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 87 1. Introduction 89 This document describes Tetrys, a novel network coding protocol. 90 Network codes were introduced in the early 2000s [AHL-00] to address 91 the limitations of transmission over the Internet (delay, capacity 92 and packet loss). While the use of network codes is fairly recent in 93 the Internet community, the use of application layer erasure codes in 94 the IETF has already been standardized in the RMT [RMT] and the 95 FECFRAME [FECFRAME] working groups. The protocol presented here can 96 be seen as a network coding extension to standards solutions. The 97 current proposal can be considered as a combination of network 98 erasure coding and feedback mechanisms [Tetrys]. 100 The main innovation of the Tetrys protocol is in the generation of 101 coded packets from an elastic encoding window periodically updated 102 with the receiver's feedbacks. This update is done in such a way 103 that any source packets coming from an input flow is included in the 104 encoding window as long as it is not acknowledged or the encoding 105 window did not reach a size limit. This mechanism allows for losses 106 on both the forward and return paths and in particular is resilient 107 to acknowledgement losses. 109 With Tetrys, a coded packet is a linear combination over a finite 110 field of the data source packets belonging to the coding window. The 111 choice of the finite field of the coefficients is a trade-off between 112 the best performance (with non-binary coefficients) and the system 113 constraints (binary codes in an energy constrained environment) and 114 is driven by the application. 116 Thanks to the elastic encoding window, the coded packets are built 117 on-the-fly, by using an algorithm or a function to choose the 118 coefficients. The redundancy ratio can be dynamically adjusted, and 119 the coefficients can be generated in different ways along a 120 transmission. Compared to FEC block codes, this allows to reduce the 121 bandwidth use and the decoding delay. 123 1.1. Requirements Notation 125 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 126 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 127 document are to be interpreted as described in [RFC2119]. 129 2. Definitions, Notations and Abbreviations 131 The terminology used in this document is presented below. It is 132 aligned with the FECFRAME terminology as well as with recent 133 activities in the Network Coding Research Group. 135 Source symbol: a symbol that has to be transmitted between the 136 ingress and egress of the network. 138 Coded symbol: a linear combination over a finite field of a set of 139 source symbols. 141 Source symbol ID: a sequence number to identify the source 142 symbols. 144 Coded symbol ID: a sequence number to identify the coded symbols. 146 Encoding coefficients: elements of the finite field characterizing 147 the linear combination used to generate a coded symbols. 149 Encoding vector: set of the encoding coefficients and input source 150 symbol IDs. 152 Source packet: a source packet contains a source symbol with its 153 associated IDs. 155 Coded packet: a coded packet contains a coded symbol, the coded 156 symbol's ID and encoding vector. 158 Input symbol: a symbol at the input of the Tetrys Encoding 159 Building Block. 161 Output symbol: a symbol generated by the Tetrys Encoding Building 162 Block. For a non systematic mode, all output symbols are coded 163 symbols. For a systematic mode, output symbols can be the input 164 symbols and a number of coded symbols that are linear combinations 165 of the input symbols + the encoding vectors. 167 Feedback packet: a feedback packet is a packet containing 168 information about the decoded or received source symbols. It can 169 also bring additional information about the Packet Error Rate or 170 the number of various packets in the receiver decoding window 172 Elastic Encoding Window: an encoder-side buffer that stores all 173 the non-acknowledged source packets of the input flow that are 174 involved in the coding process. 176 Coding Coefficient Generator Identifier: a unique identifier that 177 define a function or an algorithm allowing to generate the 178 encoding vector. 180 Code rate: Define the rate between the number of input symbols and 181 the number of output symbols. 183 3. Architecture 185 -- Editor's note: The architecture used in this document should be 186 aligned with the future NC Architecture document [NWCRG-ARCH]. -- 188 3.1. Use Cases 190 Tetrys is well suited, but not limited to the use case where there is 191 a single flow originated by a single source, with intra stream coding 192 that takes place at a single encoding node. Note that the input 193 stream can be a multiplex of several upper layer streams. 195 Transmission can be over a single path or multiple paths. In 196 addition, the flow can be sent in unicast, multicast, or anycast 197 mode. This is the simplest use-case, that is very much inline with 198 currently proposed scenarios for end-to-end streaming. 200 3.2. Overview 202 +----------+ +----------+ 203 | | | | 204 | App | | App | 205 | | | | 206 +----------+ +----------+ 207 | ^ 208 | source source | 209 | symbols symbols | 210 | | 211 v | 212 +----------+ +----------+ +----------+ 213 | | output packets | | output packets | | 214 | Tetrys |--------------->| Tetrys |--------------->| Tetrys | 215 | Encoder |feedback packets| Recoder |feedback packets| Decoder | 216 | |<---------------| |<---------------| | 217 +----------+ +----------+ +----------+ 219 Figure 1: Tetrys Architecture 221 The Tetrys protocol features several key functionalities: 223 o On-the-fly encoding; 225 o Recoding; 227 o Decoding; 229 o Signaling, to carry in particular the symbol identifiers in the 230 encoding window and the associated coding coefficients when 231 meaningful, in a manner that was previously used in FEC; 233 o Feedback management; 235 o Elastic window management; 237 o Channel estimation; 239 o Dynamic adjustment of the code rate and flow control; 241 o Congestion control management (if appropriate); 242 -- Editor's note: must be discussed -- 244 o Tetrys packet header creation and processing; 246 o -- Editor's note: something else? -- 248 These functionalities are provided by several building blocks: 250 o The Tetrys Building Block: this BB is used during encoding, 251 recoding and decoding processes. It must be noted that Tetrys 252 does not mandate a specific building block. Instead any building 253 block compatible with the elastic encoding window feature of 254 Tetrys can be used. 256 o The Window Management Building Block: this building block is in 257 charge of managing the encoding encoding window at a Tetrys 258 sender. 260 -- Editor's note: Is it worth moving it in a dedicated BB? To 261 be discussed -- 263 o Other ? 265 In order to enable future components and services to be added 266 dynamically, Tetrys adds a header extension mechanism, compatible 267 with that of LCT, NORM, FECFRAME [REFS]. 269 4. Packet Format 271 4.1. Common Header Format 273 All types of Tetrys packets share the same common header format (see 274 Figure 2). 276 0 1 2 3 277 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 278 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 279 | V | C |S| Reserved | HDR_LEN | Packet Type | 280 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 281 | Congestion Control Information (CCI, length = 32*C bits) | 282 | ... | 283 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 284 | Transport Session Identifier (TSI, length = 32*S bits) | 285 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 286 | Header Extensions (if applicable) | 287 | ... | 288 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 290 Figure 2: Common Header Format 292 -- Editor's note: this format inherits from the LCT header format 293 (RFC 5651) with slight modifications. -- 295 o Tetrys version number (V): 4 bits. Indicates the Tetrys version 296 number. The Tetrys version number for this specification is 1. 298 o Congestion control flag (C): 2 bits. C=0 indicates the Congestion 299 Control Information (CCI) field is 0 bits in length. C=1 300 indicates the CCI field is 32 bits in length. C=2 indicates the 301 CCI field is 64 bits in length. C=3 indicates the CCI field is 96 302 bits in length. 304 -- Editor's note: version number and congestion control to be 305 discussed -- 307 o Transport Session Identifier flag (S): 1 bit. This is the number 308 of full 32-bit words in the TSI field. The TSI field is 32*S bits 309 in length, i.e., the length is either 0 bits or 32 bits. 311 o Reserved (Resv): 9 bits. These bits are reserved. In this 312 version of the specification, they MUST be set to zero by senders 313 and MUST be ignored by receivers. 315 o Header length (HDR_LEN): 8 bits. Total length of the Tetrys 316 header in units of 32-bit words. The length of the Tetrys header 317 MUST be a multiple of 32 bits. This field can be used to directly 318 access the portion of the packet beyond the Tetrys header, i.e., 319 to the first other header if it exists, or to the packet payload 320 if it exists and there is no other header, or to the end of the 321 packet if there are no other headers or packet payload. 323 o Packet Type: 8 bits. Type of packet. 325 o Congestion Control Information (CCI): 0, 32, 64, or 96 bits Used 326 to carry congestion control information. For example, the 327 congestion control information could include layer numbers, 328 logical channel numbers, and sequence numbers. This field is 329 opaque for the purpose of this specification. This field MUST be 330 0 bits (absent) if C=0. This field MUST be 32 bits if C=1. This 331 field MUST be 64 bits if C=2. This field MUST be 96 bits if C=3. 333 o Transport Session Identifier (TSI): 0 or 32 bits The TSI uniquely 334 identifies a session among all sessions from a particular sender. 335 The TSI is scoped by the IP address of the sender, and thus the IP 336 address of the sender and the TSI together uniquely identify the 337 session. Although a TSI in conjunction with the IP address of the 338 sender always uniquely identifies a session, whether or not the 339 TSI is included in the Tetrys header depends on what is used as 340 the TSI value. If the underlying transport is UDP, then the 341 16-bit UDP source port number MAY serve as the TSI for the 342 session. If there is no underlying TSI provided by the network, 343 transport or any other layer, then the TSI MUST be included in the 344 Tetrys header. 346 4.1.1. Header Extensions 348 Header Extensions are used in Tetrys to accommodate optional header 349 fields that are not always used or have variable size. The presence 350 of Header Extensions can be inferred by the Tetrys header length 351 (HDR_LEN). If HDR_LEN is larger than the length of the standard 352 header, then the remaining header space is taken by Header 353 Extensions. 355 If present, Header Extensions MUST be processed to ensure that they 356 are recognized before performing any congestion control procedure or 357 otherwise accepting a packet. The default action for unrecognized 358 Header Extensions is to ignore them. This allows the future 359 introduction of backward-compatible enhancements to Tetrys without 360 changing the Tetrys version number. Non-backward-compatible Header 361 Extensions CANNOT be introduced without changing the Tetrys version 362 number. 364 There are two formats for Header Extensions, as depicted in Figure 3. 365 The first format is used for variable-length extensions, with Header 366 Extension Type (HET) values between 0 and 127. The second format is 367 used for fixed-length (one 32-bit word) extensions, using HET values 368 from 128 to 255. 370 0 1 2 3 371 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 372 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 373 | HET (<=127) | HEL | | 374 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 375 . . 376 . Header Extension Content (HEC) . 377 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 379 0 1 2 3 380 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 381 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 382 | HET (>=128) | Header Extension Content (HEC) | 383 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 385 Figure 3: Header Extension Format 387 o Header Extension Type (HET): 8 bits The type of the Header 388 Extension. This document defines a number of possible types. 389 Additional types may be defined in future versions of this 390 specification. HET values from 0 to 127 are used for variable- 391 length Header Extensions. HET values from 128 to 255 are used for 392 fixed-length 32-bit Header Extensions. 394 o Header Extension Length (HEL): 8 bits The length of the whole 395 Header Extension field, expressed in multiples of 32-bit words. 396 This field MUST be present for variable-length extensions (HETs 397 between 0 and 127) and MUST NOT be present for fixed-length 398 extensions (HETs between 128 and 255). 400 o Header Extension Content (HEC): variable length The content of the 401 Header Extension. The format of this sub-field depends on the 402 Header Extension Type. For fixed-length Header Extensions, the 403 HEC is 24 bits. For variable-length Header Extensions, the HEC 404 field has variable size, as specified by the HEL field. Note that 405 the length of each Header Extension MUST be a multiple of 32 bits. 406 Also note that the total size of the Tetrys header, including all 407 Header Extensions and all optional header fields, cannot exceed 408 255 32-bit words. 410 4.2. Source Packet Format 412 A source packet is the encapsulation of a Common Packet Header, a 413 Source Symbol ID and a source symbol (payload). The source symbols 414 can have variable sizes. 416 0 1 2 3 417 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 418 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 419 | | 420 / Common Packet Header / 421 | | 422 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 423 | Source Symbol ID | 424 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 425 | | 426 / Payload / 427 | | 428 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 430 Figure 4: Source Packet Format 432 Common Packet Header: a common packet header (as common header 433 format) where Packet Type=0. 435 Source Symbol ID: the sequence number to identify a source symbol. 437 Payload: the payload (source symbol) 439 4.3. Coded Packet Format 441 A coded packet is the encapsulation of a Common Packet Header, a 442 Coded Symbol ID, the associated Encoding Vector and a coded symbol 443 (payload). As the source symbols CAN have variable sizes, each 444 source symbol size need to be encoded, and the result must be stored 445 in the coded packet as the Encoded Payload Size (16 bits): as it is 446 an optional field, the encoding vector MUST signal the use of 447 variable source symbol sizes with the field V (see Section 6.1.1.2). 449 0 1 2 3 450 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 451 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 452 | | 453 / Common Packet Header / 454 | | 455 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 456 | Coded Symbol ID | 457 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 458 | | 459 / Encoding Vector / 460 | | 461 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 462 | Encoded Payload Size | | 463 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 464 | | 465 / Payload / 466 | | 467 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 469 Figure 5: Coded Packet Format 471 Common Packet Header: a common packet header (as common header 472 format) where Packet Type=1. 474 Coded Symbol ID: the sequence number to identify a coded symbol. 476 Encoding Vector: an encoding vector to define the linear combination 477 used (coefficients, and source symbols). 479 Encoded Payload Size: the coded payload size used if the source 480 symbols have variable size (optional, Section 6.1.1.2)). 482 Payload: the coded symbol. 484 4.4. Acknowledgement Packet Format 486 A Tetrys Decoding Building Block or Tetrys Recoding Building Block 487 MAY send back to another building block some Acknowledgement packets. 488 They contain information about what it has received and/or decoded, 489 and other information such as a packet loss rate or the size of the 490 decoding buffers. The acknowledgement packets are OPTIONAL hence 491 they could be omitted or lost in transmission without impacting the 492 protocol behavior. 494 0 1 2 3 495 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 496 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 497 | | 498 / Common Packet Header / 499 | | 500 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 501 | Nb of missing source symbols | 502 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 503 | Nb of not already used coded symbols | 504 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 505 | First Source Symbol ID | 506 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 507 | PLR | SACK size | | 508 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 509 | | 510 / SACK Vector / 511 | | 512 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 514 Figure 6: Acknowledgement Packet Format 516 Common Packet Header: a common packet header (as common header 517 format) where Packet Type=2. 519 Nb missing source symbols: the number of missing source symbols in 520 the receiver since the beginning of the session. 522 Nb of not already used coded symbols: the number coded symbols at the 523 receiver that have not already been used for decoding (e.g., the 524 linear combinations contains at least 2 unknown source symbols). 526 First Source Symbol ID: ID of the first source symbol to consider for 527 acknowledgement. 529 PLR: packet loss ratio expressed as a percentage. 531 SACK size: the size of the SACK vector in 32-bit words. For 532 instance, with value 2, the SACK vector is 64 bits long. 534 SACK vector: bit vector indicating the acknowledged symbols from the 535 first source symbol ID. The "First Source Symbol" is included in 536 this bit vector. A bit equal to 1 at position i means that the 537 source symbol of ID equal to "First Source Symbol ID" + i is 538 acknowledged by this acknowledgment packet. 540 5. The Coding Coefficient Generator Identifiers 542 5.1. Definition 544 The Coding Coefficient Generator Identifiers define a function or an 545 algorithm to build the coding coefficients used to generate the coded 546 symbols. They MUST be known by all the Tetrys encoders, recoders or 547 decoders. 549 5.2. Table of Identifiers 551 0000: GF2 (or GF(2**1)) Vandermonde based coefficients. Each 552 coefficient is built as alpha^( (source_symbol_id*coded-symbol_id) % 553 2). 555 0001: GF16 (or GF(2**4)) Vandermonde based coefficients. Each 556 coefficient is built as alpha^( (source_symbol_id*coded-symbol_id) % 557 16). 559 0010: GF256 (or GF(2**8)) Vandermonde based coefficients. Each 560 coefficient is built as alpha^( (source_symbol_id*coded_symbol_id) % 561 256). 563 0011: SRLC. 565 Others: To be discussed. 567 6. Tetrys Basic Functions 569 6.1. Encoding 571 At the beginning of a transmission, a Tetrys Encoding Building Block 572 or MUST choose an initial code rate (added redundancy) as it doesn't 573 know the packet loss rate of the channel. In steady state, depending 574 on the code-rate, the Tetrys Encoding Building Block CAN generate 575 coded symbols when it receives a source symbol from the application 576 or some feedback from the decoding or recoding blocks. 578 When a Tetrys Encoding Building Block needs to generate a coded 579 symbol, it considers the set of source symbols stored in the Elastic 580 Encoding Window. These source symbols are the set of source symbols 581 which are not yet acknowledged by the receiver. 583 A Tetrys Encoding Building Block SHOULD set a limit to the Elastic 584 Encoding Window maximum size. This allows to control the algorithmic 585 complexity at the encoder and decoder by limiting the size of linear 586 combinations. It is also needed in situations where acknowledgment 587 packets are all lost or absent. 589 At the generation of a coded symbol, the Tetrys Encoding Building 590 Block generates an encoding vector containing the IDs of the source 591 symbols stored in the Elastic Encoding Window. For each source 592 symbol, a finite field coefficient is determined using a Coding 593 Coefficient Generator. This generator CAN take as input the source 594 symbol ID and the coded symbol ID and CAN determine a coefficient in 595 a deterministic way. A classical example of such deterministic 596 function is a generator matrix where the rows are indexed by the 597 source symbol IDs and the columns by the coded symbol IDs. For 598 example, the entries of this matrix can be built from a Vandermonde 599 structure, like Reed-Solomon codes, or from a sparse binary matrix, 600 like Low-Density Generator Matrix codes. Finally, the coded symbol 601 is the sum of the source symbols multiplied by their corresponding 602 coefficients. 604 6.1.1. Encoding Vector Formats 606 Each coded packet contains an encoding vector. The encoding vectors 607 CAN contain the ID and/or coefficient of each source symbol contained 608 in the coded symbol. 610 6.1.1.1. Transmitting the source symbol IDs 612 The source symbol IDs are organized as a sorted list of 32-bit 613 unsigned integers. Depending on the feedback, the source symbol IDs 614 can be successive or not in the list. 616 If they are successive, the boundaries are stored in the encoding 617 vector: it just needs 2*32-bit of information. 619 If not, the edge blocks CAN be stored directly, or a differential 620 transform to reduce the number of bits needed to represent an ID CAN 621 be used. 623 6.1.1.1.1. Compressed list of Source symbol IDs 625 Assume the symbol IDs used in the combination are: 626 [1..3],[5..6],[8..10]. 628 1. Keep the first element in the packet as the first_source_id: 1. 630 2. Apply a differential transform to the others elements 631 ([3,5,6,8,10]) which removes the element i-1 to the element i, 632 starting with the first_source_id as i0, and get the list L => 633 [2,2,1,2,2] 635 3. Compute b, the number of bits needed to store all the elements, 636 which is ceil(log2(max(L))): here, 2 bits. 638 4. Write b in the corresponding field, and write all the b * [(2 * 639 NB blocks) - 1] elements in a bit vector, here: 10 10 01 10 10. 641 6.1.1.1.2. Decompressing the Source symbol IDs 643 When a Tetrys Decoding Building Block wants to reverse the 644 operations, this algorithm is used: 646 1. Rebuild the list of the transmitted elements by reading the bit 647 vector and b: [10 10 01 10 10] => [2,2,1,2,2] 649 2. Apply the reverse transform by adding successively the elements, 650 starting with first_source_id: [1,1+2,(1+2)+2,(1+2+2)+1,...] => 651 [1,3,5,6,8,10] 653 3. Rebuild the blocks using the list and first_source_id: 654 [1..3],[5..6],[8..10]. 656 6.1.1.2. Encoding Vector Format 658 The encoding vector CAN be used to store the source symbol IDs 659 included in the associated coded symbol, the coefficients used in the 660 combination, or both. It CAN be used to send only the number of 661 source symbols included in the coded symbol. 663 If the source IDs are stored, the number of blocks MUST be different 664 from 0. 666 The encoding vector format uses a 4-bit Coding Coefficient Generator 667 Identifier to identity the algorithm to generate the coefficients, 668 and contains a set of blocks for the source symbol IDs used in the 669 combination. In this format, the number of blocks is stored as a 670 8-bit unsigned integer. To reduce the overhead, a compressed way to 671 store the symbol IDs is used: the IDs are not stored as themselves, 672 but stored as the difference between the previous. 674 0 1 2 3 675 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 676 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 677 | EV_LEN | CCGI | I |C|V| NB_IDS | NB_COEFS | 678 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 679 | FIRST_SOURCE_ID | 680 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 681 | b_id | | 682 +-+-+-+-+-+-+-+-+ id_bit_vector +-+-+-+-+-+-+-+ 683 | | Padding | 684 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 685 | b_coef | | 686 +-+-+-+-+-+-+-+-+ coef_bit_vector +-+-+-+-+-+-+-+ 687 | | Padding | 688 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 690 Figure 7: Encoding Vector Format 692 o Encoding Vector Length (EV_LEN) (8-bits): size in units of 32-bit 693 words. 695 o Coding Coefficient Generator Identifier (CCGI): 4-bit ID to 696 identify the algorithm or the function used to generate the 697 coefficients (see Section 5). As a CCGI is included in each 698 encoded vector, it can dynamically change between the generation 699 of 2 coded symbols. 701 o Store the Source symbol IDs (I) (2 bits): 703 * 00 means there is no source symbol ID information. 705 * 01 means the encoding vector contains the edge blocks of the 706 source symbol IDs without compression. 708 * 10 means the encoding vector contains the compressed list of 709 the source symbol IDs. 711 * 11 means the encoding vector contains the compressed edge 712 blocks of the source symbol IDs. 714 o Store the coefficients (C): 1 bit to know if an encoding vector 715 contains information about the coefficients used. 717 o Having source symbols with variable size (V): set V to 1 if the 718 combination which refers the encoding vector is a combination of 719 source symbols with variable sizes. In this case, the coded 720 packets MUST have the 'Encoded Payload Size' field. 722 o Number of IDs used to store the source symbol IDs (NB_IDS): the 723 number of IDs stored (depending on I). 725 o Number of coefficients (NB_COEFS): The number of the coefficients 726 used to generate the associated coded symbol. 728 o The first source Identifier (FIRST_SOURCE_ID): the first source 729 symbol ID used in the combination. 731 o Number of bits for each edge block (b_id): the number of bits 732 needed to store the edge (see Section 6.1.1.1). 734 o Information about the source symbol IDs (id_bit_vector): if I=01, 735 store the edge blocks as b_id * (NB_IDS * 2 - 1). If I=10, store 736 in a compressed way the edge blocks. 738 o Number of bits needed to store each coefficient (b_coef): the 739 number of bits used to store the coefficients. 741 o The coefficients (coef_bit_vector): The coefficients stored (as a 742 vector of b_coef * NB_COEFS). 744 o Padding: padding to have an Encoding Vector size multiple of 745 32-bit (for the id and coefficient part). 747 6.2. The Elastic Encoding Window 749 When an input source symbol is passed to a Tetrys Encoding Building 750 Block, it is added to the Elastic Encoding Window. This window MUST 751 have a limit set by the encoding building Block (depending of the use 752 case: unicast, multicast, file transfer, real-time transfer, ...). 753 If the Elastic Encoding Window reached its limit, the window slides 754 over the symbols: the first (oldest) symbols are removed. Then, a 755 packet containing this symbol can be sent onto the network. As an 756 element of the coding window, this symbol is included in the next 757 linear combinations created to generate the coded symbols. 759 As explained below, the receiver or the recoder sends periodic 760 feedback indicating the received or decoded source symbols. In the 761 case of a unicast transmission, when the sender receives the 762 information that a source symbol was received and/or decoded by the 763 receiver, it removes this symbol from the coding window. 765 In a multicast transmission: 767 o If the acknowledgement packets are not enabled, the coding window 768 grows up to a limit. When the limit is reached, the oldest 769 symbols are removed from the coding window. 771 o If the acknowledgement packets are enabled, a source symbol is 772 removed from the coding window when all the receivers have 773 received or decoded it or when the coding window reaches its 774 limit. 776 6.3. Recoding 778 6.3.1. Principle 780 A Tetrys Recoding Block maintains a list of the ID of the source 781 symbols included in the Elastic Coding Window of the sender. It also 782 stores a set of received source and coded symbols able to regenerate 783 the set or a subset of the symbols of the Elastic Coding Window. In 784 other words, if R1, ..., Rt represent t received symbols and S1, ..., 785 Sk represent the set or a subset of the source symbols of the Elastic 786 Coding Window, there exists a t*k-matrix M such that (R1, ..., Rt).M 787 = (S1, ..., Sk). 789 6.3.2. Generating a coded symbol at an intermediate node 791 At the generation of a coded symbol, the Tetrys Recoding Building 792 Block generates an encoding vector containing the IDs of the source 793 symbols stored in the Elastic Encoding Window or in the subset of the 794 Elastic Encoding Window that it is able to regenerate. The Tetrys 795 Recoding Building Block then generates a new coded symbol ID 796 different from the received coded symbol IDs. From this coded symbol 797 ID and the source symbol IDs of (S1, ..., Sk), a finite field 798 coefficient is determined using a Coding Coefficient Generator. Let 799 (a1, ...,ak) denote the obtained coefficients. To compute the linear 800 combination (s1, ..., Sk).transpose(a1, ..., ak) the Tetrys Recoding 801 Building block computes the vector v = (a1, ...,ak).transpose(M) and 802 then computes the coded symbol R = (R1, ..., Rt).transpose(v). It 803 can be verified that the new coded symbol is obtained without any 804 decoding operation. 806 6.4. Decoding 808 A classical matrix inversion is sufficient to recover the source 809 symbols. 811 7. Security Considerations 813 Tetrys inherits a subset of the security issues described as those 814 described in FECFRAME [FECFRAME] and in particular in sections 815 "9.2.2. Content Corruption" and "9.3. Attacks against the FEC 816 Parameters". As an application layer end-to-end protocol, security 817 considerations of Tetrys should also be comparable to those of HTTP/2 818 with TLS. ; the considerations from Section 10 of HTTP2 [HTTP2] 819 apply in addition to those listed here. 821 8. Privacy Considerations 823 N/A 825 9. IANA Considerations 827 N/A 829 10. Acknowledgments 831 N/A 833 11. References 835 11.1. Normative References 837 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 838 Requirement Levels", BCP 14, RFC 2119, 839 DOI 10.17487/RFC2119, March 1997, 840 . 842 11.2. Informative References 844 [AHL-00] Ahlswede, R., Ning Cai, Li, S., and R. Yeung, "Network 845 information flow", IEEE Transactions on Information 846 Theory vol.46, no.4, pp.1204,1216, July 2000. 848 [FECFRAME] 849 Watson, M., Begen, A., and V. Roca, "Forward Error 850 Correction (FEC) Framework", Request for Comments 6363, 851 October 2011. 853 [HTTP2] Belshe, M., Peon, R., and M. Thomson, "Hypertext Transfer 854 Protocol Version 2 (HTTP/2)", Request for Comments 7540, 855 October 2015. 857 [NWCRG-ARCH] 858 NWCRG, "Network Coding Architecture", TBD TBD. 860 [RMT] Vicisano, L., Gemmel, J., Rizzo, L., Handley, M., and J. 861 Crowcroft, "Forward Error Correction (FEC) Building 862 Block", Request for Comments 3452, December 2002. 864 [Tetrys] Lacan, J. and E. Lochin, "Rethinking reliability for long- 865 delay networks", International Workshop on Satellite and 866 Space Communications 2008 (IWSSC08), October 2008. 868 Authors' Addresses 870 Jonathan Detchart 871 ISAE-SUPAERO 872 10, avenue Edouard-Belin 873 BP 54032 874 Toulouse CEDEX 4 31055 875 France 877 Email: jonathan.detchart@isae-supaero.fr 879 Emmanuel Lochin 880 ISAE-SUPAERO 881 10, avenue Edouard-Belin 882 BP 54032 883 Toulouse CEDEX 4 31055 884 France 886 Email: emmanuel.lochin@isae-supaero.fr 888 Jerome Lacan 889 ISAE-SUPAERO 890 10, avenue Edouard-Belin 891 BP 54032 892 Toulouse CEDEX 4 31055 893 France 895 Email: jerome.lacan@isae-supaero.fr 897 Vincent Roca 898 INRIA 899 655, av. de l'Europe 900 Inovallee; Montbonnot 901 ST ISMIER cedex 38334 902 France 904 Email: vincent.roca@inria.fr