idnits 2.17.1 draft-detchart-nwcrg-tetrys-06.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 (December 5, 2020) is 1237 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'REFS' is mentioned on line 268, but not defined -- Looks like a reference, but probably isn't: '3' on line 652 -- Looks like a reference, but probably isn't: '5' on line 652 -- Looks like a reference, but probably isn't: '6' on line 652 -- Looks like a reference, but probably isn't: '8' on line 652 -- Looks like a reference, but probably isn't: '10' on line 652 -- Looks like a reference, but probably isn't: '2' on line 648 -- Looks like a reference, but probably isn't: '1' on line 652 -- 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 ISAE-SUPAERO 4 Intended status: Experimental E. Lochin 5 Expires: June 8, 2021 ENAC 6 J. Lacan 7 ISAE-SUPAERO 8 V. Roca 9 INRIA 10 December 5, 2020 12 Tetrys, an On-the-Fly Network Coding protocol 13 draft-detchart-nwcrg-tetrys-06 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 June 8, 2021. 41 Copyright Notice 43 Copyright (c) 2020 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 . . . . . . . . . . . . . . . . . . . . . . . . 2 59 1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 3 60 2. Definitions, Notations and Abbreviations . . . . . . . . . . 3 61 3. Architecture . . . . . . . . . . . . . . . . . . . . . . . . 4 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. Security Considerations . . . . . . . . . . . . . . . . . . . 18 82 8. Privacy Considerations . . . . . . . . . . . . . . . . . . . 19 83 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 84 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 19 85 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 86 11.1. Normative References . . . . . . . . . . . . . . . . . . 19 87 11.2. Informative References . . . . . . . . . . . . . . . . . 19 88 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 20 90 1. Introduction 92 This document describes Tetrys, a novel network coding protocol. 93 Network codes were introduced in the early 2000s [AHL-00] to address 94 the limitations of transmission over the Internet (delay, capacity 95 and packet loss). While the use of network codes is fairly recent in 96 the Internet community, the use of application layer erasure codes in 97 the IETF has already been standardized in the RMT [RMT] and the 98 FECFRAME [FECFRAME] working groups. The protocol presented here can 99 be seen as a network coding extension to standards solutions. The 100 current proposal can be considered a combination of network erasure 101 coding and feedback mechanisms [Tetrys]. 103 The main innovation of the Tetrys protocol is in the generation of 104 coded packets from an elastic encoding window periodically updated 105 with the receiver's feedbacks. This update is done in so that any 106 source packets coming from an input flow are included in the encoding 107 window as long as it is not acknowledged or the encoding window did 108 not reach a size limit. This mechanism allows for losses on both the 109 forward and return paths and in particular, is resilient to 110 acknowledgment losses. 112 With Tetrys, a coded packet is a linear combination over a finite 113 field of the data source packets belonging to the coding window. The 114 coefficients finite field's choice is a trade-off between the best 115 performance (with non-binary coefficients) and the system constraints 116 (binary codes in an energy-constrained environment) and is driven by 117 the application. 119 Thanks to the elastic encoding window, the coded packets are built 120 on-the-fly, by using an algorithm or a function to choose the 121 coefficients. The redundancy ratio can be dynamically adjusted, and 122 the coefficients can be generated in different ways along with a 123 transmission. Compared to FEC block codes, this allows reducing the 124 bandwidth use and the decoding delay. 126 1.1. Requirements Notation 128 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 129 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 130 document are to be interpreted as described in [RFC2119]. 132 2. Definitions, Notations and Abbreviations 134 The terminology used in this document is presented below. It is 135 aligned with the FECFRAME terminology conjointly with recent 136 activities in the Network Coding Research Group. 138 Source symbol: a symbol that has to be transmitted between the 139 ingress and egress of the network. 141 Coded symbol: a linear combination over a finite field of a set of 142 source symbols. 144 Source symbol ID: a sequence number to identify the source 145 symbols. 147 Coded symbol ID: a sequence number to identify the coded symbols. 149 Encoding coefficients: elements of the finite field characterizing 150 the linear combination used to generate coded symbols. 152 Encoding vector: a set of the encoding coefficients and input 153 source symbol IDs. 155 Source packet: a source packet contains a source symbol with its 156 associated IDs. 158 Coded packet: a coded packet contains a coded symbol, the coded 159 symbol's ID, and encoding vector. 161 Input symbol: a symbol at the input of the Tetrys Encoding 162 Building Block. 164 Output symbol: a symbol generated by the Tetrys Encoding Building 165 Block. For a non-systematic mode, all output symbols are coded 166 symbols. For a systematic mode, output symbols can be the input 167 symbols and a number of coded symbols that are linear combinations 168 of the input symbols + the encoding vectors. 170 Feedback packet: a feedback packet is a packet containing 171 information about the decoded or received source symbols. It can 172 also bring additional information about the Packet Error Rate or 173 the number of various packets in the receiver decoding window. 175 Elastic Encoding Window: an encoder-side buffer that stores all 176 the non-acknowledged source packets of the input flow involved in 177 the coding process. 179 Coding Coefficient Generator Identifier: a unique identifier that 180 defines a function or an algorithm allowing to generate the 181 encoding vector. 183 Code rate: Define the rate between the number of input symbols and 184 the number of output symbols. 186 3. Architecture 188 -- Editor's note: The architecture used in this document should be 189 aligned with the future NC Architecture document [NWCRG-ARCH]. -- 191 3.1. Use Cases 193 Tetrys is well suited, but not limited to the use case where there is 194 a single flow originated by a single source, with intra stream coding 195 at a single encoding node. Note that the input stream can be a 196 multiplex of several upper layer streams. Transmission can be over a 197 single path or multiple paths. Besides, the flow can be sent in 198 unicast, multicast, or anycast mode. This is the simplest use-case, 199 that is very much aligned with currently proposed scenarios for end- 200 to-end streaming. 202 3.2. Overview 204 +----------+ +----------+ 205 | | | | 206 | App | | App | 207 | | | | 208 +----------+ +----------+ 209 | ^ 210 | source source | 211 | symbols symbols | 212 | | 213 v | 214 +----------+ +----------+ +----------+ 215 | | output packets | | output packets | | 216 | Tetrys |--------------->| Tetrys |--------------->| Tetrys | 217 | Encoder |feedback packets| Recoder |feedback packets| Decoder | 218 | |<---------------| |<---------------| | 219 +----------+ +----------+ +----------+ 221 Figure 1: Tetrys Architecture 223 The Tetrys protocol features several key functionalities: 225 o On-the-fly encoding; 227 o Recoding; 229 o Decoding; 231 o Signaling, to carry in particular the symbol identifiers in the 232 encoding window and the associated coding coefficients when 233 meaningful, in a manner that was previously used in FEC; 235 o Feedback management; 237 o Elastic window management; 238 o Channel estimation; 240 o Dynamic adjustment of the code rate and flow control; 242 o Congestion control management (if appropriate); 244 -- Editor's note: must be discussed -- 246 o Tetrys packet header creation and processing; 248 o -- Editor's note: something else? -- 250 Several building blocks provide these functionalities: 252 o The Tetrys Building Block: this BB is used during encoding, 253 recoding, and decoding processes. It must be noted that Tetrys 254 does not mandate a specific building block. Instead, any building 255 block compatible with the elastic encoding window feature of 256 Tetrys can be used. 258 o The Window Management Building Block: this building block is in 259 charge of managing the encoding window at a Tetrys sender. 261 -- Editor's note: Is it worth moving it in a dedicated BB? To 262 be discussed -- 264 o Other ? 266 To ease the addition of future components and services, Tetrys adds a 267 header extension mechanism, compatible with that of LCT, NORM, 268 FECFRAME [REFS]. 270 4. Packet Format 272 4.1. Common Header Format 274 All types of Tetrys packets share the same common header format (see 275 Figure 2). 277 0 1 2 3 278 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 279 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 280 | V | C |S| Reserved | HDR_LEN | Packet Type | 281 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 282 | Congestion Control Information (CCI, length = 32*C bits) | 283 | ... | 284 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 285 | Transport Session Identifier (TSI, length = 32*S bits) | 286 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 287 | Header Extensions (if applicable) | 288 | ... | 289 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 291 Figure 2: Common Header Format 293 -- Editor's note: this format inherits from the LCT header format 294 (RFC 5651) with slight modifications. -- 296 o Tetrys version number (V): 4 bits. Indicates the Tetrys version 297 number. The Tetrys version number for this specification is 1. 299 o Congestion control flag (C): 2 bits. C=0 indicates the Congestion 300 Control Information (CCI) field is 0 bits in length. C=1 301 indicates the CCI field is 32 bits in length. C=2 indicates the 302 CCI field is 64 bits in length. C=3 indicates the CCI field is 96 303 bits in length. 305 -- Editor's note: version number and congestion control to be 306 discussed -- 308 o Transport Session Identifier flag (S): 1 bit. This is the number 309 of full 32-bit words in the TSI field. The TSI field is 32*S bits 310 in length, i.e., the length is either 0 bits or 32 bits. 312 o Reserved (Resv): 9 bits. These bits are reserved. In this 313 version of the specification, they MUST be set to zero by senders 314 and MUST be ignored by receivers. 316 o Header length (HDR_LEN): 8 bits. The total length of the Tetrys 317 header in units of 32-bit words. The length of the Tetrys header 318 MUST be a multiple of 32 bits. This field can be used to directly 319 access the portion of the packet beyond the Tetrys header, i.e., 320 to the first next header if it exists, or to the packet payload if 321 it exists and there is no other header, or to the end of the 322 packet if there are no other headers or packet payload. 324 o Packet Type: 8 bits. Type of packet. 326 o Congestion Control Information (CCI): 0, 32, 64, or 96 bits Used 327 to carry congestion control information. For example, the 328 congestion control information could include layer numbers, 329 logical channel numbers, and sequence numbers. This field is 330 opaque for this specification. This field MUST be 0 bits (absent) 331 if C=0. This field MUST be 32 bits if C=1. This field MUST be 64 332 bits if C=2. This field MUST be 96 bits if C=3. 334 o Transport Session Identifier (TSI): 0 or 32 bits The TSI uniquely 335 identifies a session among all sessions from a particular sender. 336 The TSI is scoped by the IP address of the sender, and thus the IP 337 address of the sender and the TSI together uniquely identify the 338 session. Although a TSI in conjunction with the IP address of the 339 sender always uniquely identifies a session, whether or not the 340 TSI is included in the Tetrys header depends on what is used as 341 the TSI value. If the underlying transport is UDP, then the 342 16-bit UDP source port number MAY serve as the TSI for the 343 session. If there is no underlying TSI provided by the network, 344 transport or any other layer, then the TSI MUST be included in the 345 Tetrys header. 347 4.1.1. Header Extensions 349 Header Extensions are used in Tetrys to accommodate optional header 350 fields that are not always used or have variable size. The presence 351 of Header Extensions can be inferred by the Tetrys header length 352 (HDR_LEN). If HDR_LEN is larger than the length of the standard 353 header, then the remaining header space is taken by Header 354 Extensions. 356 If present, Header Extensions MUST be processed to ensure that they 357 are recognized before performing any congestion control procedure or 358 otherwise accepting a packet. The default action for unrecognized 359 Header Extensions is to ignore them. This allows the future 360 introduction of backward-compatible enhancements to Tetrys without 361 changing the Tetrys version number. Non-backward-compatible Header 362 Extensions CANNOT be introduced without changing the Tetrys version 363 number. 365 There are two formats for Header Extensions, as depicted in Figure 3. 366 The first format is used for variable-length extensions, with Header 367 Extension Type (HET) values between 0 and 127. The second format is 368 used for fixed-length (one 32-bit word) extensions, using HET values 369 from 128 to 255. 371 0 1 2 3 372 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 373 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 374 | HET (<=127) | HEL | | 375 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 376 . . 377 . Header Extension Content (HEC) . 378 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 380 0 1 2 3 381 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 382 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 383 | HET (>=128) | Header Extension Content (HEC) | 384 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 386 Figure 3: Header Extension Format 388 o Header Extension Type (HET): 8 bits The type of the Header 389 Extension. This document defines several possible types. 390 Additional types may be defined in future versions of this 391 specification. HET values from 0 to 127 are used for variable- 392 length Header Extensions. HET values from 128 to 255 are used for 393 fixed-length 32-bit Header Extensions. 395 o Header Extension Length (HEL): 8 bits The length of the whole 396 Header Extension field, expressed in multiples of 32-bit words. 397 This field MUST be present for variable-length extensions (HETs 398 between 0 and 127) and MUST NOT be present for fixed-length 399 extensions (HETs between 128 and 255). 401 o Header Extension Content (HEC): variable length The content of the 402 Header Extension. The format of this sub-field depends on the 403 Header Extension Type. For fixed-length Header Extensions, the 404 HEC is 24 bits. For variable-length Header Extensions, the HEC 405 field has variable size, as specified by the HEL field. Note that 406 the length of each Header Extension MUST be a multiple of 32 bits. 407 Also, note that the total size of the Tetrys header, including all 408 Header Extensions and all optional header fields, cannot exceed 409 255 32-bit words. 411 4.2. Source Packet Format 413 A source packet is a Common Packet Header encapsulation, a Source 414 Symbol ID and a source symbol (payload). The source symbols can have 415 variable sizes. 417 0 1 2 3 418 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 419 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 420 | | 421 / Common Packet Header / 422 | | 423 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 424 | Source Symbol ID | 425 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 426 | | 427 / Payload / 428 | | 429 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 431 Figure 4: Source Packet Format 433 Common Packet Header: a common packet header (as common header 434 format) where Packet Type=0. 436 Source Symbol ID: the sequence number to identify a source symbol. 438 Payload: the payload (source symbol) 440 4.3. Coded Packet Format 442 A coded packet is the encapsulation of a Common Packet Header, a 443 Coded Symbol ID, the associated Encoding Vector, and a coded symbol 444 (payload). As the source symbols CAN have variable sizes, each 445 source symbol size need to be encoded. The result must be stored in 446 the coded packet as the Encoded Payload Size (16 bits): as it is an 447 optional field, the encoding vector MUST signal the use of variable 448 source symbol sizes with the field V (see Section 6.1.1.2). 450 0 1 2 3 451 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 452 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 453 | | 454 / Common Packet Header / 455 | | 456 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 457 | Coded Symbol ID | 458 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 459 | | 460 / Encoding Vector / 461 | | 462 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 463 | Encoded Payload Size | | 464 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 465 | | 466 / Payload / 467 | | 468 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 470 Figure 5: Coded Packet Format 472 Common Packet Header: a common packet header (as common header 473 format) where Packet Type=1. 475 Coded Symbol ID: the sequence number to identify a coded symbol. 477 Encoding Vector: an encoding vector to define the linear combination 478 used (coefficients and source symbols). 480 Encoded Payload Size: the coded payload size used if the source 481 symbols have a variable size (optional, Section 6.1.1.2)). 483 Payload: the coded symbol. 485 4.4. Acknowledgement Packet Format 487 A Tetrys Decoding Building Block or Tetrys Recoding Building Block 488 MAY send back to another building block some Acknowledgement packets. 489 They contain information about what it has received and/or decoded, 490 and other information such as a packet loss rate or the size of the 491 decoding buffers. The acknowledgment packets are OPTIONAL hence they 492 could be omitted or lost in transmission without impacting the 493 protocol behavior. 495 0 1 2 3 496 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 497 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 498 | | 499 / Common Packet Header / 500 | | 501 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 502 | Nb of missing source symbols | 503 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 504 | Nb of not already used coded symbols | 505 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 506 | First Source Symbol ID | 507 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 508 | PLR | SACK size | | 509 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 510 | | 511 / SACK Vector / 512 | | 513 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 515 Figure 6: Acknowledgement Packet Format 517 Common Packet Header: a common packet header (as common header 518 format) where Packet Type=2. 520 Nb missing source symbols: the number of missing source symbols in 521 the receiver since the beginning of the session. 523 Nb of not already used coded symbols: the number of coded symbols at 524 the receiver that have not already been used for decoding (e.g., the 525 linear combinations contain at least 2 unknown source symbols). 527 First Source Symbol ID: ID of the first source symbol to consider for 528 acknowledgment. 530 PLR: packet loss ratio expressed as a percentage. 532 SACK size: the size of the SACK vector in 32-bit words. For 533 instance, with value 2, the SACK vector is 64 bits long. 535 SACK vector: bit vector indicating the acknowledged symbols from the 536 first source symbol ID. The "First Source Symbol" is included in 537 this bit vector. A bit equal to 1 at the i-th position means that 538 this acknowledgment packet acknowledges the source symbol of ID equal 539 to "First Source Symbol ID" + i. 541 5. The Coding Coefficient Generator Identifiers 543 5.1. Definition 545 The Coding Coefficient Generator Identifiers define a function or an 546 algorithm to build the coding coefficients used to generate the coded 547 symbols. They MUST be known by all the Tetrys encoders, recoders or 548 decoders. 550 5.2. Table of Identifiers 552 0000: GF2 (or GF(2**1)) Vandermonde based coefficients. Each 553 coefficient is built as alpha^( (source_symbol_id*coded-symbol_id) % 554 2). 556 0001: GF16 (or GF(2**4)) Vandermonde based coefficients. Each 557 coefficient is built as alpha^( (source_symbol_id*coded-symbol_id) % 558 16). 560 0010: GF256 (or GF(2**8)) Vandermonde based coefficients. Each 561 coefficient is built as alpha^( (source_symbol_id*coded_symbol_id) % 562 256). 564 0011: SRLC. 566 Others: To be discussed. 568 6. Tetrys Basic Functions 570 6.1. Encoding 572 At the beginning of a transmission, a Tetrys Encoding Building Block 573 or MUST choose an initial code rate (added redundancy) as it doesn't 574 know the packet loss rate of the channel. In the steady state, 575 depending on the code-rate, the Tetrys Encoding Building Block CAN 576 generate coded symbols when it receives a source symbol from the 577 application or some feedback from the decoding or recoding blocks. 579 When a Tetrys Encoding Building Block needs to generate a coded 580 symbol, it considers the set of source symbols stored in the Elastic 581 Encoding Window. These source symbols are the set of source symbols 582 that are not yet acknowledged by the receiver. 584 A Tetrys Encoding Building Block SHOULD set a limit to the Elastic 585 Encoding Window maximum size. This controls the algorithmic 586 complexity at the encoder and decoder by limiting the size of linear 587 combinations. It is also needed in situations where acknowledgment 588 packets are all lost or absent. 590 At the generation of a coded symbol, the Tetrys Encoding Building 591 Block generates an encoding vector containing the IDs of the source 592 symbols stored in the Elastic Encoding Window. For each source 593 symbol, a finite field coefficient is determined using a Coding 594 Coefficient Generator. This generator CAN take as input the source 595 symbol ID and the coded symbol ID and CAN determine a coefficient in 596 a deterministic way. A typical example of such a deterministic 597 function is a generator matrix where the rows are indexed by the 598 source symbol IDs and the columns by the coded symbol IDs. For 599 example, the entries of this matrix can be built from a Vandermonde 600 structure, like Reed-Solomon codes, or a sparse binary matrix, like 601 Low-Density Generator Matrix codes. Finally, the coded symbol is the 602 sum of the source symbols multiplied by their corresponding 603 coefficients. 605 6.1.1. Encoding Vector Formats 607 Each coded packet contains an encoding vector. The encoding vectors 608 CAN contain the ID and/or coefficient of each source symbol contained 609 in the coded symbol. 611 6.1.1.1. Transmitting the source symbol IDs 613 The source symbol IDs are organized as a sorted list of 32-bit 614 unsigned integers. Depending on the feedback, the source symbol IDs 615 can be successive or not in the list. 617 If they are successive, the boundaries are stored in the encoding 618 vector: it just needs 2*32-bit of information. 620 If not, the edge blocks CAN be stored directly, or a differential 621 transform to reduce the number of bits needed to represent an ID CAN 622 be used. 624 6.1.1.1.1. Compressed list of Source symbol IDs 626 Assume the symbol IDs used in the combination are: 627 [1..3],[5..6],[8..10]. 629 1. Keep the first element in the packet as the first_source_id: 1. 631 2. Apply a differential transform to the others elements 632 ([3,5,6,8,10]) which removes the element i-1 to the element i, 633 starting with the first_source_id as i0, and get the list L => 634 [2,2,1,2,2] 636 3. Compute b, the number of bits needed to store all the elements, 637 which is ceil(log2(max(L))): here, 2 bits. 639 4. Write b in the corresponding field, and write all the b * [(2 * 640 NB blocks) - 1] elements in a bit vector, here: 10 10 01 10 10. 642 6.1.1.1.2. Decompressing the Source symbol IDs 644 When a Tetrys Decoding Building Block wants to reverse the 645 operations, this algorithm is used: 647 1. Rebuild the list of the transmitted elements by reading the bit 648 vector and b: [10 10 01 10 10] => [2,2,1,2,2] 650 2. Apply the reverse transform by adding successively the elements, 651 starting with first_source_id: [1,1+2,(1+2)+2,(1+2+2)+1,...] => 652 [1,3,5,6,8,10] 654 3. Rebuild the blocks using the list and first_source_id: 655 [1..3],[5..6],[8..10]. 657 6.1.1.2. Encoding Vector Format 659 The encoding vector CAN be used to store the source symbol IDs 660 included in the associated coded symbol, the coefficients used in the 661 combination, or both. It CAN be used to send only the number of 662 source symbols included in the coded symbol. 664 If the source IDs are stored, the number of blocks MUST be different 665 from 0. 667 The encoding vector format uses a 4-bit Coding Coefficient Generator 668 Identifier to identify the algorithm to generate the coefficients. 669 It contains a set of blocks for the source symbol IDs used in the 670 combination. In this format, the number of blocks is stored as a 671 8-bit unsigned integer. To reduce the overhead, a compressed way to 672 store the symbol IDs is used: the IDs are not stored as themselves 673 but stored as the difference between the previous. 675 0 1 2 3 676 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 677 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 678 | EV_LEN | CCGI | I |C|V| NB_IDS | NB_COEFS | 679 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 680 | FIRST_SOURCE_ID | 681 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 682 | b_id | | 683 +-+-+-+-+-+-+-+-+ id_bit_vector +-+-+-+-+-+-+-+ 684 | | Padding | 685 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 686 | b_coef | | 687 +-+-+-+-+-+-+-+-+ coef_bit_vector +-+-+-+-+-+-+-+ 688 | | Padding | 689 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 691 Figure 7: Encoding Vector Format 693 o Encoding Vector Length (EV_LEN) (8-bits): size in units of 32-bit 694 words. 696 o Coding Coefficient Generator Identifier (CCGI): 4-bit ID to 697 identify the algorithm or the function used to generate the 698 coefficients (see Section 5). As a CCGI is included in each 699 encoded vector, it can dynamically change between the generation 700 of 2 coded symbols. 702 o Store the Source symbol IDs (I) (2 bits): 704 * 00 means there is no source symbol ID information. 706 * 01 means the encoding vector contains the edge blocks of the 707 source symbol IDs without compression. 709 * 10 means the encoding vector contains the compressed list of 710 the source symbol IDs. 712 * 11 means the encoding vector contains the compressed edge 713 blocks of the source symbol IDs. 715 o Store the coefficients (C): 1 bit to know if an encoding vector 716 contains information about the coefficients used. 718 o Having source symbols with variable size (V): set V to 1 if the 719 combination which refers to the encoding vector is a combination 720 of source symbols with variable sizes. In this case, the coded 721 packets MUST have the 'Encoded Payload Size' field. 723 o Number of IDs used to store the source symbol IDs (NB_IDS): the 724 number of IDs stored (depending on I). 726 o Number of coefficients (NB_COEFS): The number of the coefficients 727 used to generate the associated coded symbol. 729 o The first source Identifier (FIRST_SOURCE_ID): the first source 730 symbol ID used in the combination. 732 o Number of bits for each edge block (b_id): the number of bits 733 needed to store the edge (see Section 6.1.1.1). 735 o Information about the source symbol IDs (id_bit_vector): if I=01, 736 store the edge blocks as b_id * (NB_IDS * 2 - 1). If I=10, store 737 in a compressed way the edge blocks. 739 o Number of bits needed to store each coefficient (b_coef): the 740 number of bits used to store the coefficients. 742 o The coefficients (coef_bit_vector): The coefficients stored (as a 743 vector of b_coef * NB_COEFS). 745 o Padding: padding to have an Encoding Vector size multiple of 746 32-bit (for the id and coefficient part). 748 6.2. The Elastic Encoding Window 750 When an input source symbol is passed to a Tetrys Encoding Building 751 Block, it is added to the Elastic Encoding Window. This window MUST 752 have a limit set by the encoding building Block (depending on the use 753 case: unicast, multicast, file transfer, real-time transfer, ...). 754 If the Elastic Encoding Window reached its limit, the window slides 755 over the symbols: the first (oldest) symbols are removed. Then, a 756 packet containing this symbol can be sent onto the network. As an 757 element of the coding window, this symbol is included in the next 758 linear combinations created to generate the coded symbols. 760 As explained below, the receiver or the recoder sends periodic 761 feedback indicating the received or decoded source symbols. In the 762 case of unicast transmission, when the sender receives the 763 information that a source symbol was received and/or decoded by the 764 receiver, it removes this symbol from the coding window. 766 In a multicast transmission: 768 o If the acknowledgment packets are not enabled, the coding window 769 grows up to a limit. When the limit is reached, the oldest 770 symbols are removed from the coding window. 772 o If the acknowledgment packets are enabled, a source symbol is 773 removed from the coding window when all the receivers have 774 received or decoded it or when the coding window reaches its 775 limit. 777 6.3. Recoding 779 6.3.1. Principle 781 A Tetrys Recoding Block maintains a list of the ID of the source 782 symbols included in the Elastic Coding Window of the sender. It also 783 stores a set of received source and coded symbols able to regenerate 784 the set or a subset of the Elastic Coding Window symbols. In other 785 words, if R1, ..., Rt represent t received symbols and S1, ..., Sk 786 represent the set or a subset of the source symbols of the Elastic 787 Coding Window, there exists a t*k-matrix M such that (R1, ..., Rt).M 788 = (S1, ..., Sk). 790 6.3.2. Generating a coded symbol at an intermediate node 792 At the generation of a coded symbol, the Tetrys Recoding Building 793 Block generates an encoding vector containing the IDs of the source 794 symbols stored in the Elastic Encoding Window or in the subset of the 795 Elastic Encoding Window that it can regenerate. The Tetrys Recoding 796 Building Block then generates a new coded symbol ID different from 797 the received coded symbol IDs. From this coded symbol ID and the 798 source symbol IDs of (S1, ..., Sk), a finite field coefficient is 799 determined using a Coding Coefficient Generator. Let (a1, ...,ak) 800 denote the obtained coefficients. To compute the linear combination 801 (s1, ..., Sk).transpose(a1, ..., ak) the Tetrys Recoding Building 802 block computes the vector v = (a1, ...,ak).transpose(M) and then 803 computes the coded symbol R = (R1, ..., Rt).transpose(v). It can be 804 verified that the new coded symbol is obtained without any decoding 805 operation. 807 6.4. Decoding 809 A classical matrix inversion is sufficient to recover the source 810 symbols. 812 7. Security Considerations 814 Tetrys inherits a subset of the security issues described as those 815 described in FECFRAME [FECFRAME] and in particular in sections 816 "9.2.2. Content Corruption" and "9.3. Attacks against the FEC 817 Parameters". As an application layer end-to-end protocol, security 818 considerations of Tetrys should also be comparable to those of HTTP/2 819 with TLS. The considerations from Section 10 of HTTP2 [HTTP2] also 820 apply in addition to those listed here. 822 8. Privacy Considerations 824 N/A 826 9. IANA Considerations 828 N/A 830 10. Acknowledgments 832 N/A 834 11. References 836 11.1. Normative References 838 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 839 Requirement Levels", BCP 14, RFC 2119, 840 DOI 10.17487/RFC2119, March 1997, 841 . 843 11.2. Informative References 845 [AHL-00] Ahlswede, R., Ning Cai, Li, S., and R. Yeung, "Network 846 information flow", IEEE Transactions on Information 847 Theory vol.46, no.4, pp.1204,1216, July 2000. 849 [FECFRAME] 850 Watson, M., Begen, A., and V. Roca, "Forward Error 851 Correction (FEC) Framework", Request for Comments 6363, 852 October 2011. 854 [HTTP2] Belshe, M., Peon, R., and M. Thomson, "Hypertext Transfer 855 Protocol Version 2 (HTTP/2)", Request for Comments 7540, 856 October 2015. 858 [NWCRG-ARCH] 859 NWCRG, "Network Coding Architecture", TBD TBD. 861 [RMT] Vicisano, L., Gemmel, J., Rizzo, L., Handley, M., and J. 862 Crowcroft, "Forward Error Correction (FEC) Building 863 Block", Request for Comments 3452, December 2002. 865 [Tetrys] Lacan, J. and E. Lochin, "Rethinking reliability for long- 866 delay networks", International Workshop on Satellite and 867 Space Communications 2008 (IWSSC08), October 2008. 869 Authors' Addresses 871 Jonathan Detchart 872 ISAE-SUPAERO 873 10, avenue Edouard Belin 874 BP 54032 875 Toulouse CEDEX 4 31055 876 France 878 Email: jonathan.detchart@isae-supaero.fr 880 Emmanuel Lochin 881 ENAC 882 7, avenue Edouard Belin 883 Toulouse 31400 884 France 886 Email: emmanuel.lochin@enac.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, avenue de l'Europe 900 Inovallee; Montbonnot 901 ST ISMIER cedex 38334 902 France 904 Email: vincent.roca@inria.fr