idnits 2.17.1 draft-detchart-nwcrg-tetrys-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 9, 2015) is 3336 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'REFS' is mentioned on line 248, but not defined -- Looks like a reference, but probably isn't: '3' on line 618 -- Looks like a reference, but probably isn't: '5' on line 618 -- Looks like a reference, but probably isn't: '6' on line 618 -- Looks like a reference, but probably isn't: '8' on line 618 -- Looks like a reference, but probably isn't: '10' on line 618 -- Looks like a reference, but probably isn't: '2' on line 614 -- Looks like a reference, but probably isn't: '1' on line 618 -- Obsolete informational reference (is this intentional?): RFC 3452 (ref. 'RMT') (Obsoleted by RFC 5052, RFC 5445) Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 9 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: September 10, 2015 ISAE 6 V. Roca 7 INRIA 8 March 9, 2015 10 Tetrys, an On-the-Fly Network Coding protocol 11 draft-detchart-nwcrg-tetrys-01 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 19 (redundancy). It can be used for both unicast, multicast and anycast 20 communications. 22 Status of This Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at http://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on September 10, 2015. 39 Copyright Notice 41 Copyright (c) 2015 IETF Trust and the persons identified as the 42 document authors. All rights reserved. 44 This document is subject to BCP 78 and the IETF Trust's Legal 45 Provisions Relating to IETF Documents 46 (http://trustee.ietf.org/license-info) in effect on the date of 47 publication of this document. Please review these documents 48 carefully, as they describe your rights and restrictions with respect 49 to this document. Code Components extracted from this document must 50 include Simplified BSD License text as described in Section 4.e of 51 the Trust Legal Provisions and are provided without warranty as 52 described in the Simplified BSD License. 54 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 57 1.1. Requirements Notation . . . . . . . . . . . . . . . . . . 3 58 2. Definitions, Notations and Abbreviations . . . . . . . . . . 3 59 3. Architecture . . . . . . . . . . . . . . . . . . . . . . . . 4 60 3.1. Use Cases . . . . . . . . . . . . . . . . . . . . . . . . 4 61 3.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . 5 62 4. Packet Format . . . . . . . . . . . . . . . . . . . . . . . . 6 63 4.1. Common Header Format . . . . . . . . . . . . . . . . . . 6 64 4.1.1. Header Extensions . . . . . . . . . . . . . . . . . . 7 65 4.2. Source Packet Format . . . . . . . . . . . . . . . . . . 9 66 4.3. Coded Packet Format . . . . . . . . . . . . . . . . . . . 9 67 4.4. Acknowledgement Packet Format . . . . . . . . . . . . . . 10 68 5. The Coding Coefficient Generator Identifiers . . . . . . . . 12 69 5.1. Definition . . . . . . . . . . . . . . . . . . . . . . . 12 70 5.2. Table of Identifiers . . . . . . . . . . . . . . . . . . 12 71 6. Tetrys Basic Functions . . . . . . . . . . . . . . . . . . . 12 72 6.1. Encoding . . . . . . . . . . . . . . . . . . . . . . . . 12 73 6.1.1. Encoding Vector Formats . . . . . . . . . . . . . . . 13 74 6.1.2. The Elastic Encoding Window . . . . . . . . . . . . . 15 75 6.2. Decoding . . . . . . . . . . . . . . . . . . . . . . . . 16 76 7. Security Considerations . . . . . . . . . . . . . . . . . . . 16 77 8. Privacy Considerations . . . . . . . . . . . . . . . . . . . 16 78 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16 79 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16 80 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 16 81 11.1. Normative References . . . . . . . . . . . . . . . . . . 16 82 11.2. Informative References . . . . . . . . . . . . . . . . . 16 83 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 17 85 1. Introduction 87 This document describes Tetrys, a novel network coding protocol. 88 Network codes were introduced in the early 2000s [AHL-00] to address 89 the limitations of transmission over the Internet (delay, capacity 90 and packet loss). While the use of network codes is fairly recent in 91 the Internet community, the use of application layer erasure codes in 92 the IETF has already been standardized in the RMT [RMT] and the 93 FECFRAME [FECFRAME] working groups. The protocol presented here can 94 be seen as a network coding extension to standards solutions. The 95 current proposal can be considered as a combination of network 96 erasure coding and feedback mechanisms [Tetrys]. 98 The main innovation of the Tetrys protocol is in the generation of 99 coded packets from an elastic encoding window, the size of which is 100 periodically updated with the receiver's feedback. This update is 101 done in such a way that any source packets coming from an input flow 102 is included in the encoding window as long as it is not acknowledged 103 or the encoding window did not reach a limit. This mechanism allows 104 for losses on both the forward and return paths and in particular is 105 resilient to acknowledgement losses. 107 With Tetrys, a coded packet is a linear combination of the data 108 source packets belonging to the coding window over a finite field. 109 The choice of the finite field of the coefficients is a trade-off 110 between the best performance (with non-binary coefficients) and the 111 system constraints (binary codes in an energy constrained 112 environment) and is driven by the application. 114 Thanks to the elastic encoding window, the coded packets are built 115 on-the-fly, by using an algorithm or a function to choose the 116 coefficients. The redundancy ratio can be dynamically adjusted, and 117 the coefficients can be generated in different ways along a 118 transmission. This allows to reduce the bandwidth used, compared to 119 FEC block codes, and the decoding delay. 121 1.1. Requirements Notation 123 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 124 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 125 document are to be interpreted as described in [RFC2119]. 127 2. Definitions, Notations and Abbreviations 129 The terminology used in this document is presented below. It is 130 aligned with the FECFRAME terminology as well as with recent 131 activities in the Network Coding Research Group. 133 Source symbol: a symbol that has to be transmitted between the 134 ingress and egress of the network. 136 Coded symbol: a linear combination over a finite field of a set of 137 source symbols. 139 Source symbol ID: a sequence number to identify the source 140 symbols. 142 Coded symbol ID: a sequence number to identify the coded symbols. 144 Encoding vector: a set of the encoding coefficients and input 145 symbol IDs. One or both sets can be null. 147 Source packet: a source packet contains a source symbol with its 148 associated IDs. 150 Coded packet: a coded packet contains a coded symbol, the coded 151 symbol's ID and encoding vector. 153 Input symbol: a symbol at the input of the Tetrys Encoding 154 Building Block. 156 Output symbol: a symbol generated by the Tetrys Encoding Building 157 Block. For a non systematic mode, all output symbols are coded 158 symbols. For a systematic mode, output symbols can be the input 159 symbols and a number of coded symbols that are linear combinations 160 of the input symbols + the encoding vectors. 162 Feedback packet: a feedback packet is a packet containing 163 information about the decoded or received source symbols. It can 164 also bring additional information about the Packet Error Rate or 165 the number of various packets in the receiver decoding window 167 Elastic Encoding Window: an encoder-side buffer that stores all 168 the non-acknowledged source packets of the input flow that are 169 part of the coding process. 171 Coding Coefficient Generator Identifier: a unique identifier to 172 define a function or an algorithm allowing to generate the 173 coefficients used to compute the coded packets. 175 Code rate: Define the rate of generating and sending the 176 redundancy. 178 3. Architecture 180 -- Editor's note: The architecture used in this document should be 181 aligned with the future NC Architecture document [NWCRG-ARCH]. -- 183 3.1. Use Cases 185 Tetrys is well suited, but not limited to the use case where there is 186 a single flow originated by a single source, with intra stream coding 187 that takes place at a single encoding node. Transmission can be over 188 a single path or multiple paths. In addition, the flow can be sent 189 in unicast, multicast, or anycast mode. This is the simplest use- 190 case, that is very much inline with currently proposed scenarios for 191 end-to-end streaming. 193 3.2. Overview 195 +-----------+ +-----------+ 196 | Tetrys | output packets | Tetrys | 197 source | Sender |----------------->| Receiver | source 198 ---------->| | feedback packets | |----------> 199 symbols | |<-----------------| | symbols 200 +-----------+ +-----------+ 202 Figure 1: Tetrys Architecture. 204 The Tetrys protocol features several key functionalities: 206 o On-the-fly encoding; 208 o Decoding; 210 o Signaling, to carry in particular the symbol identifiers in the 211 encoding window and the associated coding coefficients when 212 meaningful, in a manner that was previously used in FEC; 214 o Feedback management; 216 o Elastic window management; 218 o Channel estimation; 220 o Dynamic adjustment of the code rate and flow control; 222 o Congestion control management (if appropriate); 224 -- Editor's note: must be discussed -- 226 o Tetrys packet header creation and processing; 228 o -- Editor's note: something else? -- 230 These functionalities are provided by several building blocks: 232 o The Tetrys Building Block: this BB is used during encoding and 233 decoding processes. It must be noted that Tetrys does not mandate 234 a specific building block. Instead any building block compatible 235 with the elastic encoding window feature of Tetrys can be used. 237 o The Window Management Building Block: this building block is in 238 charge of managing the encoding encoding window at a Tetrys 239 sender. 241 -- Editor's note: Is it worth moving it in a dedicated BB? To 242 be discussed -- 244 o Other ? 246 In order to enable future components and services to be added 247 dynamically, Tetrys adds a header extension mechanism, compatible 248 with that of LCT, NORM, FECFRAME [REFS]. 250 4. Packet Format 252 4.1. Common Header Format 254 All types of Tetrys packets share the same common header format (see 255 Figure 2). 257 0 1 2 3 258 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 259 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 260 | V | Reserved | C |S| HDR_LEN | Packet Type | 261 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 262 | Congestion Control Information (CCI, length = 32*C bits) | 263 | ... | 264 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 265 | Transport Session Identifier (TSI, length = 32*S bits) | 266 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 267 | Header Extensions (if applicable) | 268 | ... | 269 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 271 Figure 2: Common Header Format 273 -- Editor's note: this format inherits from the LCT header format 274 (RFC 5651) with slight modifications. -- 276 o Tetrys version number (V): 4 bits. Indicates the Tetrys version 277 number. The Tetrys version number for this specification is 1. 279 o Reserved (Resv): 9 bits. These bits are reserved. In this 280 version of the specification, they MUST be set to zero by senders 281 and MUST be ignored by receivers. 283 o Congestion control flag (C): 2 bits. C=0 indicates the Congestion 284 Control Information (CCI) field is 0 bits in length. C=1 285 indicates the CCI field is 32 bits in length. C=2 indicates the 286 CCI field is 64 bits in length. C=3 indicates the CCI field is 96 287 bits in length. 289 -- Editor's note: version number and congestion control to be 290 discussed -- 292 o Transport Session Identifier flag (S): 1 bit. This is the number 293 of full 32-bit words in the TSI field. The TSI field is 32*S bits 294 in length, i.e., the length is either 0 bits or 32 bits. 296 o Header length (HDR_LEN): 8 bits. Total length of the Tetrys 297 header in units of 32-bit words. The length of the Tetrys header 298 MUST be a multiple of 32 bits. This field can be used to directly 299 access the portion of the packet beyond the Tetrys header, i.e., 300 to the first other header if it exists, or to the packet payload 301 if it exists and there is no other header, or to the end of the 302 packet if there are no other headers or packet payload. 304 o Packet Type: 8 bits. Type of packet. 306 o Congestion Control Information (CCI): 0, 32, 64, or 96 128 bits 307 Used to carry congestion control information. For example, the 308 congestion control information could include layer numbers, 309 logical channel numbers, and sequence numbers. This field is 310 opaque for the purpose of this specification. This field MUST be 311 0 bits (absent) if C=0. This field MUST be 32 bits if C=1. This 312 field MUST be 64 bits if C=2. This field MUST be 96 bits if C=3. 314 o Transport Session Identifier (TSI): 0, 16, 32, or 48 bits The TSI 315 uniquely identifies a session among all sessions from a particular 316 sender. The TSI is scoped by the IP address of the sender, and 317 thus the IP address of the sender and the TSI together uniquely 318 identify the session. Although a TSI in conjunction with the IP 319 address of the sender always uniquely identifies a session, 320 whether or not the TSI is included in the Tetrys header depends on 321 what is used as the TSI value. If the underlying transport is 322 UDP, then the 16-bit UDP source port number MAY serve as the TSI 323 for the session. If the TSI value appears multiple times in a 324 packet, then all occurrences MUST be the same value. If there is 325 no underlying TSI provided by the network, transport or any other 326 layer, then the TSI MUST be included in the Tetrys header. 328 4.1.1. Header Extensions 330 Header Extensions are used in Tetrys to accommodate optional header 331 fields that are not always used or have variable size. The presence 332 of Header Extensions can be inferred by the Tetrys header length 333 (HDR_LEN). If HDR_LEN is larger than the length of the standard 334 header, then the remaining header space is taken by Header Extension 335 fields. 337 If present, Header Extensions MUST be processed to ensure that they 338 are recognized before performing any congestion control procedure or 339 otherwise accepting a packet. The default action for unrecognized 340 Header Extensions is to ignore them. This allows the future 341 introduction of backward-compatible enhancements to Tetrys without 342 changing the Tetrys version number. Non-backward-compatible Header 343 Extensions CANNOT be introduced without changing the Tetrys version 344 number. 346 There are two formats for Header Extension fields, as depicted in 347 Figure Figure 3. The first format is used for variable-length 348 extensions, with Header Extension Type (HET) values between 0 and 349 127. The second format is used for fixed-length (one 32-bit word) 350 extensions, using HET values from 127 to 255. 352 0 1 2 3 353 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 354 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 355 | HET (<=127) | HEL | | 356 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 357 . . 358 . Header Extension Content (HEC) . 359 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 361 0 1 2 3 362 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 363 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 364 | HET (>=128) | Header Extension Content (HEC) | 365 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 367 Figure 3: Header Extension Format 369 o Header Extension Type (HET): 8 bits The type of the Header 370 Extension. This document defines a number of possible types. 371 Additional types may be defined in future versions of this 372 specification. HET values from 0 to 127 are used for variable- 373 length Header Extensions. HET values from 128 to 255 are used for 374 fixed-length 32-bit Header Extensions. 376 o Header Extension Length (HEL): 8 bits The length of the whole 377 Header Extension field, expressed in multiples of 32-bit words. 378 This field MUST be present for variable-length extensions (HETs 379 between 0 and 127) and MUST NOT be present for fixed-length 380 extensions (HETs between 128 and 255). 382 o Header Extension Content (HEC): variable length The content of the 383 Header Extension. The format of this sub-field depends on the 384 Header Extension Type. For fixed-length Header Extensions, the 385 HEC is 24 bits. For variable-length Header Extensions, the HEC 386 field has variable size, as specified by the HEL field. Note that 387 the length of each Header Extension field MUST be a multiple of 32 388 bits. Also note that the total size of the Tetrys header, 389 including all Header Extensions and all optional header fields, 390 cannot exceed 255 32-bit words. 392 4.2. Source Packet Format 394 A source packet is the encapsulation of a source symbol, a source 395 symbol ID and a Common Packet Header. The source symbols can have 396 variable sizes. 398 0 1 2 3 399 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 400 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 401 | | 402 / Common Packet Header / 403 | | 404 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 405 | Source Symbol ID | 406 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 407 | | 408 / Payload / 409 | | 410 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 412 Figure 4: Source Packet Format 414 Common Packet Header: a common packet header where Packet Type=0. 416 Source Symbol ID: the sequence number to identify a source symbol. 418 Payload: the payload (source symbol) 420 4.3. Coded Packet Format 422 A coded packet is the encapsulation of a coded symbol, a coded symbol 423 ID, the associated encoding vector and the Common Packet Header. As 424 the source symbols can have variable sizes, each source symbol size 425 need to be encoded, and the result must be stored in the coded 426 packet. The Encoded Payload Size is 16 bits. 428 0 1 2 3 429 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 430 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 431 | | 432 / Common Packet Header / 433 | | 434 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 435 | Coded Symbol ID | 436 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 437 | | 438 / Encoding Vector / 439 | | 440 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 441 | Encoded Payload Size | | 442 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 443 | | 444 / Payload / 445 | | 446 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 448 Figure 5: Coded Packet Format 450 Common Packet Header: a common packet header where Packet Type=1. 452 Coded Symbol ID: the sequence number to identify a coded symbol. 454 Encoding Vector: an encoding vector to define the linear combination 455 used (coefficients, and source symbols). 457 Encoded Payload Size: the coded payload size used if the source 458 symbols are of variable size. 460 Payload: the coded symbol. 462 4.4. Acknowledgement Packet Format 464 A Tetrys Decoding Building Block MAY send back to a Tetrys Encoding 465 Building Block some Acknowledgement packets. They contain 466 information about what it is received and/or decoded, and other 467 information such as a packet loss rate or the size of the decoding 468 buffers. The acknowledgement packets are OPTIONAL hence they could 469 be omitted or lost in transmission without impacting the basic 470 protocol performance. 472 0 1 2 3 473 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 474 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 475 | | 476 / Common Packet Header / 477 | | 478 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 479 | Nb of missing source symbols | 480 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 481 | Nb of not already used coded symbols | 482 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 483 | Transport Session Identifier | 484 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 485 | First Source Symbol ID | 486 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 487 | SACK size | | 488 +-+-+-+-+-+-+-+-+ + 489 | | 490 / SACK Vector / 491 | | 492 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 494 Figure 6: Acknowledgement Packet Format 496 Common Packet Header: a common packet header where Packet Type=2. 498 Nb missing source symbols: the number of missing source symbols in 499 the receiver. 501 Nb of not already used coded symnbols: the number of not already used 502 coded symbols in the receiver that have not already been used for 503 decoding. Meaning the number of linear combinations containing at 504 least 2 unknown source symbols. 506 Transport Session Identifier (TSI): the unique identifier for the 507 session (CAN be 0bit, depending of the Common Packet Header's field 508 S) 510 First Source Symbol ID: ID of the first source symbol to acknowledge. 512 SACK size: the size of the SACK vector in 32-bit words. For 513 instance, with value 2, the SACK vector is 64 bits long. 515 SACK vector: bit vector indicating the acknowledged symbols following 516 the first source symbol ID. The "First Source Symbol" is not 517 included in this bit vector. A bit equal to 1 at position i means 518 that the source symbol of ID equal to "First Source Symbol ID" + i + 519 1 is acknowledged by this acknowledgment packet. 521 5. The Coding Coefficient Generator Identifiers 523 5.1. Definition 525 The Coding Coefficient Generator Identifiers define a function or an 526 algorithm to build the coding coefficients used to generate the coded 527 symbols. They MUST be known by all the Building Blocks. 529 5.2. Table of Identifiers 531 0000: GF256 Vandermonde based coefficients. Each coefficient is 532 build as alpha^( (source_id*repair_id) % 255). 534 0001: GF16 Vandermonde based coefficients. Each coefficient is build 535 as alpha^( (source_id*repair_id) % 15). 537 0010: SRLC. 539 Others: To be discussed. 541 6. Tetrys Basic Functions 543 6.1. Encoding 545 At the beginning of a transmission, a Tetrys Encoding Building Block 546 MUST choose an initial code rate (added redundancy) as it doesn't 547 know the packet loss rate of the channel. In steady state, the 548 Tetrys Encoding Building Block generates coded symbols when it 549 receives some information from the decoding blocks. 551 When a Tetrys Encoding Building Block needs to generate a coded 552 symbol, it considers the set of source symbols stored in the Elastic 553 Encoding Window. These source symbols are the set of source symbols 554 which are not yet acknowledged by the receiver. 556 A Tetrys Encoding Building Block SHOULD set a limit of the Elastic 557 Encoding Window size. This allows to reduce the complexity by 558 considering less source symbols. It also provides a coping mechanism 559 if all the acknowledgment packets are lost. 561 At the generation of a coded symbol, the Tetrys Encoding Building 562 Block generates an encoding vector containing the IDs of the source 563 symbols stored in the Elastic Encoding Window. For each source 564 symbol, a finite field coefficient is determined using a Coding 565 Coefficient Generator. This generator CAN take as input the source 566 symbol ID and the coded symbol ID and CAN determine a coefficient in 567 a deterministic way. A classical example of such deterministic 568 function is a generator matrix where the rows are indexed by the 569 source symbol IDs and the columns by the coded symbol IDs. For 570 example, the entries of this matrix can be built from a Vandermonde 571 structure, like Reed-Solomon codes, or from a sparse binary matrix, 572 like Low-Density Generator Matrix codes. Finally, the coded symbol 573 is the sum of the source symbols multiplied by their corresponding 574 coefficients. 576 6.1.1. Encoding Vector Formats 578 The encoding vectors are sent in each coded symbols. They contain 579 the source symbol IDs and/or the coefficients. 581 To avoid the overhead of transmitting all the source symbol IDs, the 582 following algorithm is used to compress them. 584 6.1.1.1. Transmitting the source symbol IDs 586 The source symbol IDs are organized as a sorted list of 32-bit 587 integers. Instead of sending the full list, a differential transform 588 to reduce the number of bits needed to represent an ID is used. 590 6.1.1.1.1. Compressing the Source symbol IDs 592 Assume the symbol IDs used in the combination are: 593 [1..3],[5..6],[8..10]. 595 1. Keep the first element in the packet as the first_source_id: 1. 597 2. Apply a differential transform to the others elements 598 ([3,5,6,8,10]) which removes the element i-1 to the element i, 599 starting with the first_source_id as i0, and get the list L => 600 [2,2,1,2,2] 602 3. Compute b, the number of bits needed to store all the elements, 603 which is ceil(log2(max(L))): here, 2 bits. 605 4. Write b in the corresponding field, and write all the b * [(2 * 606 NB blocks) - 1] elements in a bit vector, here: 10 10 01 10 10. 608 6.1.1.1.2. Decompressing the Source symbol IDs 610 When a Tetrys Decoding Building Block wants to reverse the 611 operations, this algorithm is used: 613 1. Rebuild the list of the transmitted elements by reading the bit 614 vector and b: [10 10 01 10 10] => [2,2,1,2,2] 616 2. Apply the reverse transform by adding successively the elements, 617 starting with first_source_id: [1,1+2,(1+2)+2,(1+2+2)+1,...] => 618 [1,3,5,6,8,10] 620 3. Rebuild the blocks using the list and first_source_id: 621 [1..3],[5..6],[8..10]. 623 6.1.1.2. Encoding Vector Format 625 The encoding vector CAN be used to store the source symbol IDs 626 included in the associated coded symbol, the coefficients used in the 627 combination, or both. It CAN be used to send only the number of 628 source symbols included in the coded symbol. 630 If the source IDs are stored, the nb of blocks MUST be different from 631 0. 633 The encoding vector format uses a 4-bit Coding Coefficient Generator 634 Identifier to identity the algorithm to generate the coefficients, 635 and contains a set of blocks for the source symbol IDs used in the 636 combination. In this format, the number of blocks is stored as a 637 8-bit unsigned integer. To reduce the overhead, a compressed way to 638 store the symbol IDs is used: the IDs are not stored as themselves, 639 but stored as the difference between the previous. 641 0 1 2 3 642 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 643 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 644 | EV_LEN | CCGI |I|C| | NB_BLOCKS | NB_COEFS | 645 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 646 | FIRST_SOURCE_ID | 647 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 648 | b_id | | 649 +-+-+-+-+-+-+-+ id_bit_vector +-+-+-+-+-+-+-+ 650 | | Padding | 651 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 652 | b_coef | | 653 +-+-+-+-+-+-+-+ coef_bit_vector +-+-+-+-+-+-+-+ 654 | | Padding | 655 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 657 Figure 7: Encoding Vector Format 659 o Encoding Vector Length (EV_LEN): size in units of 32-bit words. 661 o Coding Coefficient Generator Identifier (CCGI): 8-bit ID to 662 identify the algorithm or the function used to generate the 663 coefficients (see Section 5). As a CCGI is included in each 664 encoded vector, it can dynamically change between the generation 665 of 2 coded symbols. 667 o Store the IDs flag (I): 1 bit to know if an encoding vector 668 contains the list of the IDs used. MUST be 1 if the Encoding 669 Vector stores the source symbol IDs. 671 o Number of blocks used to store the source symbol IDs (NB_BLOCKS): 672 the number of blocks used to store all the source symbol IDs. 674 o Number of coefficients (NB_COEFS): The number of the coefficients 675 used to generate the associated coded symbol. 677 o The first source Identifier (FIRST_SOURCE_ID): the first source 678 symbol ID used in the combination. 680 o Number of bits for each edge block (b_id): the number of bits 681 needed to store the edge (see Section 6.1.1.1). 683 o The compressed edge blocks (id_bit_vector): equal to b_id * 684 (NB_BLOCKS * 2 - 1). 686 o Number of bits needed to store each coefficient (b_coef): the 687 number of bits used to store the coefficients. 689 o The coefficients (coef_bit_vector): The coefficients stored (as a 690 vector of b_coef * NB_COEFS). 692 o Padding: padding to have an Encoding Vector size multiple of 693 32-bit (for the id and coefficient part). 695 6.1.2. The Elastic Encoding Window 697 When an input source symbol is passed to a Tetrys Encoding Building 698 Block, it is added to the Elastic Encoding Window. This window MUST 699 have a limit set by the encoding building Block (depending of the use 700 case: unicast, multicast, file transfer, real-time transfer, ...). 701 If the Elastic Encoding Window reached its limit, the window slides 702 over the symbols: the first (oldest) symbols are removed. Then, a 703 packet containing this symbol can be sent onto the network. As an 704 element of the coding window, this symbol is included in the next 705 linear combinations created to generate the coded symbols. 707 As explained below, the receiver sends periodic feedback indicating 708 the received or decoded source symbols. In the case of a unicast 709 transmission, when the sender receives the information that a source 710 symbol was received and/or decoded by the receiver, it removes this 711 symbol from the coding window. In a multicast transmission, a source 712 symbol is removed from the coding window only when all the receivers 713 have received or decoded it. 715 6.2. Decoding 717 A classical matrix inversion is sufficient to recover the source 718 symbols. 720 7. Security Considerations 722 N/A 724 8. Privacy Considerations 726 N/A 728 9. IANA Considerations 730 N/A 732 10. Acknowledgments 734 N/A 736 11. References 738 11.1. Normative References 740 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 741 Requirement Levels", BCP 14, RFC 2119, March 1997. 743 11.2. Informative References 745 [AHL-00] Ahlswede, R., Ning Cai, , Li, S., and R. Yeung, "Network 746 information flow", IEEE Transactions on Information Theory 747 vol.46, no.4, pp.1204,1216, July 2000. 749 [FECFRAME] 750 Watson, M., Begen, A., and V. Roca, "Forward Error 751 Correction (FEC) Framework", Request for Comments 6363, 752 October 2011. 754 [NWCRG-ARCH] 755 NWCRG, , "Network Coding Architecture", TBD TBD. 757 [RMT] Vicisano, L., Gemmel, J., Rizzo, L., Handley, M., and J. 758 Crowcroft, "Forward Error Correction (FEC) Building 759 Block", Request for Comments 3452, December 2002. 761 [Tetrys] Lacan, J. and E. Lochin, "Rethinking reliability for long- 762 delay networks", International Workshop on Satellite and 763 Space Communications 2008 (IWSSC08), October 2008. 765 Authors' Addresses 767 Jonathan Detchart 768 ISAE 769 10, avenue Edouard-Belin 770 BP 54032 771 Toulouse CEDEX 4 31055 772 France 774 Email: jonathan.detchart@isae.fr 776 Emmanuel Lochin 777 ISAE 778 10, avenue Edouard-Belin 779 BP 54032 780 Toulouse CEDEX 4 31055 781 France 783 Email: emmanuel.lochin@isae.fr 785 Jerome Lacan 786 ISAE 787 10, avenue Edouard-Belin 788 BP 54032 789 Toulouse CEDEX 4 31055 790 France 792 Email: jerome.lacan@isae.fr 794 Vincent Roca 795 INRIA 796 655, av. de l'Europe 797 Inovallee; Montbonnot 798 ST ISMIER cedex 38334 799 France 801 Email: vincent.roca@inria.fr 802 URI: http://privatics.inrialpes.fr/people/roca/