idnits 2.17.1 draft-ietf-tsvwg-rlc-fec-scheme-02.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 == Line 556 has weird spacing: '...air_key key...' -- The document date (March 4, 2018) is 2244 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) No issues found here. Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 TSVWG V. Roca 3 Internet-Draft B. Teibi 4 Intended status: Standards Track INRIA 5 Expires: September 5, 2018 March 4, 2018 7 Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC) 8 Schemes for FECFRAME 9 draft-ietf-tsvwg-rlc-fec-scheme-02 11 Abstract 13 This document describes two fully-specified FEC Schemes for Sliding 14 Window Random Linear Codes (RLC), one for RLC over GF(2) (binary 15 case), a second one for RLC over GF(2^^8), both of them with the 16 possibility of controlling the code density. They are meant to 17 protect arbitrary media streams along the lines defined by FECFRAME 18 extended to sliding window FEC codes. These sliding window FEC codes 19 rely on an encoding window that slides over the source symbols, 20 generating new repair symbols whenever needed. Compared to block FEC 21 codes, these sliding window FEC codes offer key advantages with real- 22 time flows in terms of reduced FEC-related latency while often 23 providing improved erasure recovery capabilities. 25 Status of This Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF). Note that other groups may also distribute 32 working documents as Internet-Drafts. The list of current Internet- 33 Drafts is at https://datatracker.ietf.org/drafts/current/. 35 Internet-Drafts are draft documents valid for a maximum of six months 36 and may be updated, replaced, or obsoleted by other documents at any 37 time. It is inappropriate to use Internet-Drafts as reference 38 material or to cite them other than as "work in progress." 40 This Internet-Draft will expire on September 5, 2018. 42 Copyright Notice 44 Copyright (c) 2018 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (https://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 Table of Contents 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 60 1.1. Limits of Block Codes with Real-Time Flows . . . . . . . 3 61 1.2. Lower Latency and Better Protection of Real-Time Flows 62 with the Sliding Window RLC Codes . . . . . . . . . . . . 4 63 1.3. Small Transmission Overheads with the Sliding Window RLC 64 FEC Scheme . . . . . . . . . . . . . . . . . . . . . . . 5 65 1.4. Document Organization . . . . . . . . . . . . . . . . . . 5 66 2. Definitions and Abbreviations . . . . . . . . . . . . . . . . 6 67 3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . 6 68 3.1. Parameters Derivation . . . . . . . . . . . . . . . . . . 7 69 3.2. ADU, ADUI and Source Symbols Mappings . . . . . . . . . . 9 70 3.3. Encoding Window Management . . . . . . . . . . . . . . . 10 71 3.4. Pseudo-Random Number Generator . . . . . . . . . . . . . 11 72 3.5. Coding Coefficients Generation Function . . . . . . . . . 12 73 4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary ADU 74 Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 75 4.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 14 76 4.1.1. FEC Framework Configuration Information . . . . . . . 14 77 4.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 15 78 4.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 16 79 4.1.4. Additional Procedures . . . . . . . . . . . . . . . . 17 80 5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary ADU 81 Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 82 5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 18 83 5.1.1. FEC Framework Configuration Information . . . . . . . 18 84 5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . 18 85 5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 18 86 5.1.4. Additional Procedures . . . . . . . . . . . . . . . . 18 87 6. FEC Code Specification . . . . . . . . . . . . . . . . . . . 18 88 6.1. Encoding Side . . . . . . . . . . . . . . . . . . . . . . 18 89 6.2. Decoding Side . . . . . . . . . . . . . . . . . . . . . . 19 90 7. Implementation Status . . . . . . . . . . . . . . . . . . . . 20 91 8. Security Considerations . . . . . . . . . . . . . . . . . . . 20 92 8.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 20 93 8.1.1. Access to Confidential Content . . . . . . . . . . . 20 94 8.1.2. Content Corruption . . . . . . . . . . . . . . . . . 21 95 8.2. Attacks Against the FEC Parameters . . . . . . . . . . . 21 96 8.3. When Several Source Flows are to be Protected Together . 21 97 8.4. Baseline Secure FEC Framework Operation . . . . . . . . . 21 98 9. Operations and Management Considerations . . . . . . . . . . 22 99 9.1. Operational Recommendations: Finite Field GF(2) Versus 100 GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 22 101 9.2. Operational Recommendations: Coding Coefficients Density 102 Threshold . . . . . . . . . . . . . . . . . . . . . . . . 22 103 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 104 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 23 105 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 23 106 12.1. Normative References . . . . . . . . . . . . . . . . . . 23 107 12.2. Informative References . . . . . . . . . . . . . . . . . 24 108 Appendix A. Decoding Beyond Maximum Latency Optimization . . . . 26 109 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 26 111 1. Introduction 113 Application-Level Forward Erasure Correction (AL-FEC) codes, or 114 simply FEC codes, are a key element of communication systems. They 115 are used to recover from packet losses (or erasures) during content 116 delivery sessions to a large number of receivers (multicast/broadcast 117 transmissions). This is the case with the FLUTE/ALC protocol 118 [RFC6726] in case of reliable file transfers over lossy networks, and 119 the FECFRAME protocol for reliable continuous media transfers over 120 lossy networks. 122 The present document only focusses on the FECFRAME protocol, used in 123 multicast/broadcast delivery mode, with contents that feature 124 stringent real-time constraints: each source packet has a maximum 125 validity period after which it will not be considered by the 126 destination application. 128 1.1. Limits of Block Codes with Real-Time Flows 130 With FECFRAME, there is a single FEC encoding point (either a end- 131 host/server (source) or a middlebox) and a single FEC decoding point 132 (either a end-host (receiver) or middlebox). In this context, 133 currently standardized AL-FEC codes for FECFRAME like Reed-Solomon 134 [RFC6865], LDPC-Staircase [RFC6816], or Raptor/RaptorQ, are all 135 linear block codes: they require the data flow to be segmented into 136 blocks of a predefined maximum size. 138 Defining this block size requires to find an appropriate balance 139 between robustness and decoding latency: the larger the block size, 140 the higher the robustness (e.g., in front of long packet erasure 141 bursts), but also the higher the maximum decoding latency (i.e., the 142 maximum time required to recover an lost (erased) packet thanks to 143 FEC protection). Therefore, with a multicast/broadcast session where 144 different receivers experience different packet loss rates, the block 145 size should be chosen by considering the worst communication 146 conditions one wants to support, but without exceeding the desired 147 maximum decoding latency. This choice will impact all receivers. 149 1.2. Lower Latency and Better Protection of Real-Time Flows with the 150 Sliding Window RLC Codes 152 This document introduces two fully-specified FEC Schemes that follow 153 a totally different approach: the Sliding Window Random Linear Codes 154 (RLC) over either Finite Field GF(2) or GF(8). These FEC Schemes are 155 used to protect arbitrary media streams along the lines defined by 156 FECFRAME extended to sliding window FEC codes [fecframe-ext]. These 157 FEC Schemes are extremely efficient for instance with media that 158 feature real-time constraints sent within a multicast/broadcast 159 session. 161 The RLC codes belong to the broad class of sliding window AL-FEC 162 codes (A.K.A. convolutional codes). The encoding process is based on 163 an encoding window that slides over the set of source packets (in 164 fact source symbols as we will see in Section 3.2), and which is 165 either of fixed or variable size (elastic window). Repair packets 166 (symbols) are generated and sent on-the-fly, after computing a random 167 linear combination of the source symbols present in the current 168 encoding window. 170 At the receiver, a linear system is managed from the set of received 171 source and repair packets. New variables (representing source 172 symbols) and equations (representing the linear combination of each 173 repair symbol received) are added upon receiving new packets. 174 Variables are removed when they are too old with respect to their 175 validity period (real-time constraints), as well as the associated 176 equations they are involved in (Appendix A introduces an optimization 177 that extends the time a variable is considered in the system). Lost 178 source symbols are then recovered thanks to this linear system 179 whenever its rank permits it. 181 With RLC codes (more generally with sliding window codes), the 182 protection of a multicast/broadcast session also needs to be 183 dimensioned by considering the worst communication conditions one 184 wants to support. However the receivers experiencing a good to 185 medium communication quality will observe a FEC-related latency close 186 to zero [Roca17] since an isolated lost source packet is quickly 187 recovered with the following repair packet. On the opposite, with a 188 block code, recovering an isolated lost source packet always requires 189 waiting the end of the block for the first repair packet to arrive. 190 Additionally, under certain situations (e.g., with a limited FEC- 191 related latency budget and with constant bit rate transmissions after 192 FECFRAME encoding), sliding window codes achieve more easily a target 193 transmission quality (e.g., measured by the residual loss after FEC 194 decoding) by sending fewer repair packets (i.e., higher code rate) 195 than block codes. 197 1.3. Small Transmission Overheads with the Sliding Window RLC FEC 198 Scheme 200 The Sliding Window RLC FEC Scheme is designed so as to reduce the 201 transmission overhead. The main requirement is that each repair 202 packet header must enable a receiver to reconstruct the set of source 203 symbols plus the associated coefficients used during the encoding 204 process. In order to minimize packet overhead, the set of source 205 symbols in the encoding window as well as the set of coefficients 206 over GF(2^^m) (where m is 1 or 8, depending on the FEC Scheme) used 207 in the linear combination are not individually listed in the repair 208 packet header. Instead, each FEC Repair Packet header contains: 210 o the Encoding Symbol Identifier (ESI) of the first source symbol in 211 the encoding window as well as the number of symbols (since this 212 number may vary with a variable size, elastic window). These two 213 pieces of information enable each receiver to easily reconstruct 214 the set of source symbols considered during encoding, the only 215 constraint being that there cannot be any gap; 216 o the seed used by a coding coefficients generation function 217 (Section 3.5). This information enables each receiver to generate 218 the same set of coding coefficients over GF(2^^m) as the sender; 220 Therefore, no matter the number of source symbols present in the 221 encoding window, each FEC Repair Packet features a fixed 64-bit long 222 header, called Repair FEC Payload ID (Figure 7). Similarly, each FEC 223 Source Packet features a fixed 32-bit long trailer, called Explicit 224 Source FEC Payload ID (Figure 5), that contains the ESI of the first 225 source symbol (see the ADUI and source symbol mapping, Section 3.2). 227 1.4. Document Organization 229 This fully-specified FEC Scheme follows the structure required by 230 [RFC6363], section 5.6. "FEC Scheme Requirements", namely: 232 3. Procedures: This section describes procedures specific to this 233 FEC Scheme, namely: RLC parameters derivation, ADUI and source 234 symbols mapping, pseudo-random number generator, and coding 235 coefficients generation function; 236 4. Formats and Codes: This section defines the Source FEC Payload 237 ID and Repair FEC Payload ID formats, carrying the signalling 238 information associated to each source or repair symbol. It also 239 defines the FEC Framework Configuration Information (FFCI) 240 carrying signalling information for the session; 242 5. FEC Code Specification: Finally this section provides the code 243 specification. 245 2. Definitions and Abbreviations 247 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 248 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 249 document are to be interpreted as described in [RFC2119]. 251 This document uses the following definitions and abbreviations: 253 GF(q) denotes a finite field (also known as the Galois Field) with q 254 elements. We assume that q = 2^^m in this document 255 m defines the length of the elements in the finite field, in bits. 256 In this document, m is equal to 1 or 8 257 ADU: Application Data Unit 258 ADUI: Application Data Unit Information (includes the F, L and 259 padding fields in addition to the ADU) 260 E: size of an encoding symbol (i.e., source or repair symbol), 261 assumed fixed (in bytes) 262 br_in: transmission bitrate at the input of the FECFRAME sender, 263 assumed fixed (in bits/s) 264 br_out: transmission bitrate at the output of the FECFRAME sender, 265 assumed fixed (in bits/s) 266 max_lat: maximum FEC-related latency within FECFRAME (in seconds) 267 cr: RLC coding rate, ratio between the total number of source 268 symbols and the total number of source plus repair symbols 269 plr: packet loss rate on the packet erasure channel 270 ew_size: encoding window current size at a sender (in symbols) 271 ew_max_size: encoding window maximum size at a sender (in symbols) 272 dw_max_size: decoding window maximum size at a receiver (in symbols) 273 ls_max_size: linear system maximum size (or width) at a receiver (in 274 symbols) 275 PRNG: pseudo-random number generator 276 pmms_rand(maxv): PRNG defined in Section 3.4 and used in this 277 specification, that returns a new random integer in [0; maxv-1] 278 DT: coding coefficients density threshold, an integer between 0 and 279 15 (inclusive) the controls the fraction of coefficients that are 280 non zero 282 3. Procedures 284 This section introduces the procedures that are used by this FEC 285 Scheme. 287 3.1. Parameters Derivation 289 The Sliding Window RLC FEC Scheme relies on several key parameters: 291 Maximum FEC-related latency budget, max_lat (in seconds) A source 292 ADU flow can have real-time constraints, and therefore any 293 FECFRAME related operation must take place within the validity 294 period of each ADU. When there are multiple flows with different 295 real-time constraints, we consider the most stringent constraints 296 (see [RFC6363], Section 10.2, item 6, for recommendations when 297 several flows are globally protected). The maximum FEC-related 298 latency budget, max_lat, accounts for all sources of latency added 299 by FEC encoding (at a sender) and FEC decoding (at a receiver). 300 Other sources of latency (e.g., added by network communications) 301 are out of scope and must be considered separately (said 302 differently, they have already been deducted from max_lat). 303 max_lat can be regarded as the latency budget permitted for all 304 FEC-related operations. This is an input parameter that enables 305 to derive other internal parameters as explained below; 306 Encoding window current (resp. maximum) size, ew_size (resp. 307 ew_max_size) (in symbols): 308 these parameters are used by a sender during FEC encoding. More 309 precisely, each repair symbol is a linear combination of the 310 ew_size source symbols present in the encoding window when RLC 311 encoding took place. In all situations, we MUST have: 313 ew_size <= ew_max_size 314 Decoding window maximum size, dw_max_size (in symbols): at a 315 receiver, this parameter determines the maximum size of the 316 decoding window. Said differently, this is the maximum number of 317 received or lost source symbols in the linear system (i.e., the 318 variables) that are still within their latency budget. In 319 situations where packets are sent with a fixed period, the 320 dw_max_size parameter directly determines the maximum decoding 321 latency experienced by the receiver, which necessarily needs to be 322 in line with the maximum FEC-related latency budget. Note also 323 that the optimization detailed in Appendix A can extend the linear 324 system with additional old source symbols (that timed-out) beyond 325 dw_max_size; 326 Symbol size, E (in bytes) and RLC code rate (cr): the E parameter 327 determines the (source or repair) symbol sizes. The cr parameter 328 determines the code rate, i.e., the amount of redundancy added to 329 the flow (it is the ratio between the total number of source 330 symbols and the total number of source plus repair symbols). 331 These two parameters are input parameters that enable to derive 332 other internal parameters as explained below. In practice they 333 will usually be fixed, especially with multicast/broadcast 334 transmissions. In specific use-cases, in particular with unicast 335 transmissions in presence of a feedback mechanism that estimates 336 the communication quality (out-of-scope of FECFRAME), the code 337 rate may be adjusted dynamically. 339 Let us assume that the encoding symbol size (E, in bytes) and code 340 rate (cr) are constant. Let us also assume a constant transmission 341 bitrate (br_out, in bits/s) at the output of the FECFRAME sender (as 342 in [Roca17]). It means that the source flow bitrate needs to be 343 adjusted according to the added repair flow overhead in order to keep 344 the total transmission bitrate fixed and equal to br_out. In order 345 to comply with the maximum FEC-related latency budget we need: 347 dw_max_size = (max_lat * br_out * cr) / (8 * E) 349 Sometimes the opposite can happen: the source flow bitrate at the 350 input of the FECFRAME sender is fixed (br_in, in bits/s). It means 351 that the transmission bitrate at the output of the FECFRAME sender 352 will be higher, depending on the added repair flow overhead. In 353 order to comply with the maximum FEC-related latency budget we need: 355 dw_max_size = (max_lat * br_in) / (8 * E) 357 Finally, there are situations where no such assumption can be made 358 (e.g., with a variable bit rate input flow). In that case the 359 encoding and decoding window maximum sizes may be initialized, based 360 on the input flow features (e.g., the peak bitrate if it is known) 361 and great care must be taken on timing aspects at a sender (see 362 Section 3.3) and receiver. The details of how to manage these 363 situations are use-case dependent and out of scope of this document. 365 Then, once the dw_max_size has been determined, the ew_max_size can 366 be defined. For decoding to be possible, it is required that the 367 encoding window maximum size be at most equal to the decoding window 368 maximum size. It is often good practice to choose [Roca17]: 370 ew_max_size = dw_max_size * 0.75 372 However any value ew_max_size < dw_max_size can be used without 373 impact on the FEC-related latency budget. Finding the optimal value 374 will depend on the use-case details and should be determined after 375 simulations or field trials. This is of course out of scope of this 376 document. 378 Note that the decoding beyond maximum latency optimization 379 (Appendix A) enables an old source symbol to be kept in the linear 380 system beyond the FEC-related latency budget, but not delivered to 381 the receiving application. In any case, the linear system maximum 382 size is greater than (with the decoding optimization) or equal to 383 (without) the decoding window maximum size: 385 ls_max_size >= dw_max_size 387 3.2. ADU, ADUI and Source Symbols Mappings 389 An ADU, coming from the application, cannot be mapped to source 390 symbols directly. Indeed, a lost ADU recovered at a receiver must 391 contain enough information to be assigned to the right application 392 flow (UDP port numbers and IP addresses cannot be used to that 393 purpose as they are not protected by FEC encoding). This requires 394 adding the flow identifier to each ADU before doing FEC encoding. 396 Additionally, since ADUs are of variable size, padding is needed so 397 that each ADU (with its flow identifier) contribute to an integral 398 number of source symbols. This requires adding the original ADU 399 length to each ADU before doing FEC encoding. Because of these 400 requirements, an intermediate format, the ADUI, or ADU Information, 401 is considered [RFC6363]. 403 For each incoming ADU, an ADUI is created as follows. First of all, 404 3 bytes are prepended (Figure 1): 406 Flow ID (F) (8-bit field): this unsigned byte contains the integer 407 identifier associated to the source ADU flow to which this ADU 408 belongs. It is assumed that a single byte is sufficient, which 409 implies that no more than 256 flows will be protected by a single 410 FECFRAME instance. 411 Length (L) (16-bit field): this unsigned integer contains the length 412 of this ADU, in network byte order (i.e., big endian). This 413 length is for the ADU itself and does not include the F, L, or Pad 414 fields. 416 Then, zero padding is added to the ADU if needed: 418 Padding (Pad) (variable size field): this field contains zero 419 padding to align the F, L, ADU and padding up to a size that is 420 multiple of E bytes (i.e., the source and repair symbol length). 422 The data unit resulting from the ADU and the F, L, and Pad fields is 423 called ADUI. Since ADUs can have different sizes, this is also the 424 case for ADUIs. However an ADUI always contributes to an integral 425 number of source symbols. 427 symbol length, E E E 428 < ------------------ >< ------------------ >< ------------------ > 429 +-+--+---------------------------------------------+-------------+ 430 |F| L| ADU | Pad | 431 +-+--+---------------------------------------------+-------------+ 433 Figure 1: ADUI Creation example (here 3 source symbols are created 434 for this ADUI). 436 Note that neither the initial 3 bytes nor the optional padding are 437 sent over the network. However, they are considered during FEC 438 encoding, and a receiver who lost a certain FEC Source Packet (e.g., 439 the UDP datagram containing this FEC Source Packet) will be able to 440 recover the ADUI if FEC decoding succeeds. Thanks to the initial 3 441 bytes, this receiver will get rid of the padding (if any) and 442 identify the corresponding ADU flow. 444 3.3. Encoding Window Management 446 Source symbols and the corresponding ADUs are removed from the 447 encoding window: 449 o when the sliding encoding window has reached its maximum size, 450 ew_max_size. In that case the oldest symbol MUST be removed 451 before adding a new symbol, so that the current encoding window 452 size always remains inferior or equal to the maximum size: ew_size 453 <= ew_max_size; 454 o when an ADU has reached its maximum validity duration in case of a 455 real-time flow. When this happens, all source symbols 456 corresponding to the ADUI that expired SHOULD be removed from the 457 encoding window; 459 Source symbols are added to the sliding encoding window each time a 460 new ADU arrives, once the ADU to source symbols mapping has been 461 performed (Section 3.2). The current size of the encoding window, 462 ew_size, is updated after adding new source symbols. This process 463 may require to remove old source symbols so that: ew_size <= 464 ew_max_size. 466 Note that a FEC codec may feature practical limits in the number of 467 source symbols in the encoding window (e.g., for computational 468 complexity reasons). This factor may further limit the ew_max_size 469 value, in addition to the maximum FEC-related latency budget 470 (Section 3.1). 472 3.4. Pseudo-Random Number Generator 474 The RLC codes rely on the following Pseudo-Random Number Generator 475 (PRNG), identical to the PRNG used with LDPC-Staircase codes 476 ([RFC5170], section 5.7). 478 The Park-Miler "minimal standard" PRNG [PM88] MUST be used. It 479 defines a simple multiplicative congruential algorithm: Ij+1 = A * Ij 480 (modulo M), with the following choices: A = 7^^5 = 16807 and M = 481 2^^31 - 1 = 2147483647. A validation criteria of such a PRNG is the 482 following: if seed = 1, then the 10,000th value returned MUST be 483 equal to 1043618065. 485 Several implementations of this PRNG are known and discussed in the 486 literature. An optimized implementation of this algorithm, using 487 only 32-bit mathematics, and which does not require any division, can 488 be found in [rand31pmc]. It uses the Park and Miller algorithm 489 [PM88] with the optimization suggested by D. Carta in [CA90]. The 490 history behind this algorithm is detailed in [WI08]. Yet, any other 491 implementation of the PRNG algorithm that matches the above 492 validation criteria, like the ones detailed in [PM88], is 493 appropriate. 495 This PRNG produces, natively, a 31-bit value between 1 and 0x7FFFFFFE 496 (2^^31-2) inclusive. Since it is desired to scale the pseudo-random 497 number between 0 and maxv-1 inclusive, one must keep the most 498 significant bits of the value returned by the PRNG (the least 499 significant bits are known to be less random, and modulo-based 500 solutions should be avoided [PTVF92]). The following algorithm MUST 501 be used: 503 Input: 505 raw_value: random integer generated by the inner PRNG algorithm, 506 between 1 and 0x7FFFFFFE (2^^31-2) inclusive. 507 maxv: upper bound used during the scaling operation. 509 Output: 511 scaled_value: random integer between 0 and maxv-1 inclusive. 513 Algorithm: 515 scaled_value = (unsigned long) ((double)maxv * (double)raw_value / 516 (double)0x7FFFFFFF); 517 (NB: the above C type casting to unsigned long is equivalent to 518 using floor() with positive floating point values.) 520 In this document, pmms_rand(maxv) denotes the PRNG function that 521 implements the Park-Miller "minimal standard" algorithm, defined 522 above, and that scales the raw value between 0 and maxv-1 inclusive, 523 using the above scaling algorithm. 525 Additionally, the pmms_srand(seed) function must be provided to 526 enable the initialization of the PRNG with a seed before calling 527 pmms_rand(maxv) the first time. The seed is a 31-bit integer between 528 1 and 0x7FFFFFFE inclusive. In this specification, the seed is 529 restricted to a value between 1 and 0xFFFF inclusive, as this is the 530 Repair_Key 16-bit field value of the Repair FEC Payload ID 531 (Section 4.1.3). 533 3.5. Coding Coefficients Generation Function 535 The coding coefficients, used during the encoding process, are 536 generated at the RLC encoder by the generate_coding_coefficients() 537 function each time a new repair symbol needs to be produced. The 538 fraction of coefficients that are non zero (i.e., the density) is 539 controlled by the DT (Density Threshold) parameter. When DT equals 540 15, the maximum value, the function guaranties that all coefficients 541 are non zero (i.e., maximum density). When DT is between 0 (minimum 542 value) and strictly inferior to 15, the average probability of having 543 a non zero coefficient equals (DT +1) / 16. 545 These considerations apply both the RLC over GF(2) and RLC over 546 GF(2^^8), the only difference being the value of the m parameter. 547 With the RLC over GF(2) FEC Scheme (Section 5), m MUST be equal to 1. 548 With RLC over GF(2^^8) FEC Scheme (Section 4), m MUST be equal to 8. 550 551 /* 552 * Fills in the table of coding coefficients (of the right size) 553 * provided with the appropriate number of coding coefficients to 554 * use for the repair symbol key provided. 555 * 556 * (in) repair_key key associated to this repair symbol. This 557 * parameter is ignored (useless) if m=2 and dt=15 558 * (in) cc_tab[] pointer to a table of the right size to store 559 * coding coefficients. All coefficients are 560 * stored as bytes, regardless of the m parameter, 561 * upon return of this function. 562 * (in) cc_nb number of entries in the table. This value is 563 * equal to the current encoding window size. 564 * (in) dt integer between 0 and 15 (inclusive) that 565 * controls the density. With value 15, all 566 * coefficients are guaranteed to be non zero 567 * (i.e. equal to 1 with GF(2) and equal to a 568 * value in {1,... 255} with GF(2^^8)), otherwise 569 * a fraction of them will be 0. 570 * (in) m Finite Field GF(2^^m) parameter. In this 571 * document only values 1 and 8 are considered. 572 * (out) returns an error code 573 */ 574 int generate_coding_coefficients (UINT16 repair_key, 575 UINT8 cc_tab[], 576 UINT16 cc_nb, 577 UINT8 dt, 578 UINT8 m) 579 { 580 UINT32 i; 582 if (dt > 15) { 583 return SOMETHING_WENT_WRONG; /* bad dt parameter */ 584 } 585 if (repair_key == 0 && dt != 15 && m != 2) { 586 return SOMETHING_WENT_WRONG; /* bad repair_key parameter */ 587 } 588 switch (m) { 589 case 1: 590 if (dt == 15) { 591 /* all coefficients are 1 */ 592 memset(cc_tab, 1, cc_nb); 593 } else { 594 /* here coefficients are either 0 or 1 */ 595 pmms_srand(repair_key); 596 for (i = 0 ; i < cc_nb ; i++) { 597 if (pmms_rand(16) <= dt) { 598 cc_tab[i] = (UINT8) 1; 599 } else { 600 cc_tab[i] = (UINT8) 0; 601 } 602 } 603 } 604 break; 606 case 8: 607 pmms_srand(repair_key); 608 if (dt == 15) { 609 /* coefficient 0 is avoided here in order to include 610 * all the source symbols */ 611 for (i = 0 ; i < cc_nb ; i++) { 612 do { 613 cc_tab[i] = (UINT8) pmms_rand(256); 614 } while (cc_tab[i] == 0); 615 } 617 } else { 618 /* here a certain fraction of coefficients should be 0 */ 619 for (i = 0 ; i < cc_nb ; i++) { 620 if (pmms_rand(16) <= dt) { 621 do { 622 cc_tab[i] = (UINT8) pmms_rand(256); 623 } while (cc_tab[i] == 0); 624 } else { 625 cc_tab[i] = 0; 626 } 627 } 628 } 629 break; 631 default: 632 /* bad parameter m */ 633 return SOMETHING_WENT_WRONG; 634 } 635 return EVERYTHING_IS_OKAY; 636 } 637 639 Figure 2: Coding Coefficients Generation Function pseudo-code 641 4. Sliding Window RLC FEC Scheme over GF(2^^8) for Arbitrary ADU Flows 643 This fully-specified FEC Scheme defines the Sliding Window Random 644 Linear Codes (RLC) over GF(2^^8). 646 4.1. Formats and Codes 648 4.1.1. FEC Framework Configuration Information 650 The FEC Framework Configuration Information (or FFCI) includes 651 information that MUST be communicated between the sender and 652 receiver(s). More specifically, it enables the synchronization of 653 the FECFRAME sender and receiver instances. It includes both 654 mandatory elements and scheme-specific elements, as detailed below. 656 4.1.1.1. Mandatory Information 658 o FEC Encoding ID: the value assigned to this fully specified FEC 659 Scheme MUST be XXXX, as assigned by IANA (Section 10). 661 When SDP is used to communicate the FFCI, this FEC Encoding ID is 662 carried in the 'encoding-id' parameter. 664 4.1.1.2. FEC Scheme-Specific Information 666 The FEC Scheme-Specific Information (FSSI) includes elements that are 667 specific to the present FEC Scheme. More precisely: 669 Encoding symbol size (E): a non-negative integer that indicates the 670 size of each encoding symbol in bytes; 672 This element is required both by the sender (RLC encoder) and the 673 receiver(s) (RLC decoder). 675 When SDP is used to communicate the FFCI, this FEC Scheme-specific 676 information is carried in the 'fssi' parameter in textual 677 representation as specified in [RFC6364]. For instance: 679 fssi=E:1400 681 If another mechanism requires the FSSI to be carried as an opaque 682 octet string (for instance, after a Base64 encoding), the encoding 683 format consists of the following 2 octets: 685 Encoding symbol length (E): 16-bit field. 687 0 1 688 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 689 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 690 | Encoding Symbol Length (E) | 691 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 693 Figure 3: FSSI Encoding Format 695 4.1.2. Explicit Source FEC Payload ID 697 A FEC Source Packet MUST contain an Explicit Source FEC Payload ID 698 that is appended to the end of the packet as illustrated in Figure 4. 700 +--------------------------------+ 701 | IP Header | 702 +--------------------------------+ 703 | Transport Header | 704 +--------------------------------+ 705 | ADU | 706 +--------------------------------+ 707 | Explicit Source FEC Payload ID | 708 +--------------------------------+ 710 Figure 4: Structure of an FEC Source Packet with the Explicit Source 711 FEC Payload ID 713 More precisely, the Explicit Source FEC Payload ID is composed of the 714 following field (Figure 5): 716 Encoding Symbol ID (ESI) (32-bit field): this unsigned integer 717 identifies the first source symbol of the ADUI corresponding to 718 this FEC Source Packet. The ESI is incremented for each new 719 source symbol, and after reaching the maximum value (2^32-1), 720 wrapping to zero occurs. 722 0 1 2 3 723 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 724 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 725 | Encoding Symbol ID (ESI) | 726 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 728 Figure 5: Source FEC Payload ID Encoding Format 730 4.1.3. Repair FEC Payload ID 732 A FEC Repair Packet can contain one or more repair symbols. When 733 there are several repair symbols, all of them MUST have been 734 generated from the same encoding window, using Repair_Key values that 735 are managed as explained below. A receiver can easily deduce the 736 number of repair symbols within a FEC Repair Packet by comparing the 737 received FEC Repair Packet size (equal to the UDP payload size when 738 UDP is the underlying transport protocol) and the symbol size, E, 739 communicated in the FFCI. 741 A FEC Repair Packet MUST contain a Repair FEC Payload ID that is 742 prepended to the repair symbol as illustrated in Figure 6. 744 +--------------------------------+ 745 | IP Header | 746 +--------------------------------+ 747 | Transport Header | 748 +--------------------------------+ 749 | Repair FEC Payload ID | 750 +--------------------------------+ 751 | Repair Symbol | 752 +--------------------------------+ 754 Figure 6: Structure of an FEC Repair Packet with the Repair FEC 755 Payload ID 757 More precisely, the Repair FEC Payload ID is composed of the 758 following fields (Figure 7): 760 Repair_Key (16-bit field): this unsigned integer is used as a seed 761 by the coefficient generation function (Section 3.5) in order to 762 generate the desired number of coding coefficients. Value 0 MUST 763 NOT be used. When a FEC Repair Packet contains several repair 764 symbols, this repair key value is that of the first repair symbol. 765 The remaining repair keys can be deduced by incrementing by 1 this 766 value, up to a maximum value of 65535 after which it loops back to 767 1 (note that 0 is not a valid value). 768 Density Threshold for the coding coefficients, DT (4-bit field): 769 this unsigned integer carried the Density Threshold (DT) used by 770 the coding coefficient generation function Section 3.5. More 771 precisely, it controls the probability of having a non zero coding 772 coefficient, which equals (DT+1) / 16. When a FEC Repair Packet 773 contains several repair symbols, the DT value applies to all of 774 them; 775 Number of Source Symbols in the encoding window, NSS (12-bit field): 777 this unsigned integer indicates the number of source symbols in 778 the encoding window when this repair symbol was generated. When a 779 FEC Repair Packet contains several repair symbols, this NSS value 780 applies to all of them; 781 ESI of First Source Symbol in the encoding window, FSS_ESI (32-bit 782 field): 783 this unsigned integer indicates the ESI of the first source symbol 784 in the encoding window when this repair symbol was generated. 785 When a FEC Repair Packet contains several repair symbols, this 786 FSS_ESI value applies to all of them; 788 0 1 2 3 789 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 790 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 791 | Repair_Key | DT |NSS (# src symb in ew) | 792 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 793 | FSS_ESI | 794 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 796 Figure 7: Repair FEC Payload ID Encoding Format 798 4.1.4. Additional Procedures 800 The following procedure applies: 802 o The ESI of source symbols MUST start with value 0 for the first 803 source symbol and MUST be managed sequentially. Wrapping to zero 804 happens after reaching the maximum 32-bit value. 806 5. Sliding Window RLC FEC Scheme over GF(2) for Arbitrary ADU Flows 808 This fully-specified FEC Scheme defines the Sliding Window Random 809 Linear Codes (RLC) over GF(2) (binary case). 811 5.1. Formats and Codes 813 5.1.1. FEC Framework Configuration Information 815 5.1.1.1. Mandatory Information 817 o FEC Encoding ID: the value assigned to this fully specified FEC 818 Scheme MUST be YYYY, as assigned by IANA (Section 10). 820 When SDP is used to communicate the FFCI, this FEC Encoding ID is 821 carried in the 'encoding-id' parameter. 823 5.1.1.2. FEC Scheme-Specific Information 825 All the considerations of Section 4.1.1.2 apply here. 827 5.1.2. Explicit Source FEC Payload ID 829 All the considerations of Section 4.1.1.2 apply here. 831 5.1.3. Repair FEC Payload ID 833 All the considerations of Section 4.1.1.2 apply here, with the only 834 exception that the Repair_Key field is useless if DT = 15 (indeed, in 835 that case all the coefficients are necessarily equal to 1 and the 836 coefficient generation function does not use any PRNG). When DT = 15 837 it is RECOMMENDED that the sender use value 0 for the Repair_Key 838 field, but a receiver SHALL ignore this field. 840 5.1.4. Additional Procedures 842 All the considerations of Section 4.1.1.2 apply here. 844 6. FEC Code Specification 846 6.1. Encoding Side 848 This section provides a high level description of a Sliding Window 849 RLC encoder. 851 Whenever a new FEC Repair Packet is needed, the RLC encoder instance 852 first gathers the ew_size source symbols currently in the sliding 853 encoding window. Then it chooses a repair key, which can be a non 854 zero monotonically increasing integer value, incremented for each 855 repair symbol up to a maximum value of 65535 (as it is carried within 856 a 16-bit field) after which it loops back to 1 (indeed, being used as 857 a PRNG seed, value 0 is prohibited). This repair key is communicated 858 to the coefficient generation function (Section Section 3.5) in order 859 to generate ew_size coding coefficients. Finally, the FECFRAME 860 sender computes the repair symbol as a linear combination of the 861 ew_size source symbols using the ew_size coding coefficients. When E 862 is small and when there is an incentive to pack several repair 863 symbols within the same FEC Repair Packet, the appropriate number of 864 repair symbols are computed. The only constraint is to increment by 865 1 the repair key for each of them, keeping the same ew_size source 866 symbols, since only the first repair key will be carried in the 867 Repair FEC Payload ID. The FEC Repair Packet can then be sent. The 868 source versus repair FEC packet transmission order is out of scope of 869 this document and several approaches exist that are implementation 870 specific. 872 Other solutions are possible to select a repair key value when a new 873 FEC Repair Packet is needed, for instance by choosing a random 874 integer between 1 and 65535. However, selecting the same repair key 875 as before (which may happen in case of a random process) is only 876 meaningful if the encoding window has changed, otherwise the same FEC 877 Repair Packet will be generated. 879 6.2. Decoding Side 881 This section provides a high level description of a Sliding Window 882 RLC decoder. 884 A FECFRAME receiver needs to maintain a linear system whose variables 885 are the received and lost source symbols. Upon receiving a FEC 886 Repair Packet, a receiver first extracts all the repair symbols it 887 contains (in case several repair symbols are packed together). For 888 each repair symbol, when at least one of the corresponding source 889 symbols it protects has been lost, the receiver adds an equation to 890 the linear system (or no equation if this repair packet does not 891 change the linear system rank). This equation of course re-uses the 892 ew_size coding coefficients that are computed by the same coefficient 893 generation function (Section Section 3.5), using the repair key and 894 encoding window descriptions carried in the Repair FEC Payload ID. 895 Whenever possible (i.e., when a sub-system covering one or more lost 896 source symbols is of full rank), decoding is performed in order to 897 recover lost source symbols. Each time an ADUI can be totally 898 recovered, padding is removed (thanks to the Length field, L, of the 899 ADUI) and the ADU is assigned to the corresponding application flow 900 (thanks to the Flow ID field, F, of the ADUI). This ADU is finally 901 passed to the corresponding upper application. Received FEC Source 902 Packets, containing an ADU, can be passed to the application either 903 immediately or after some time to guaranty an ordered delivery to the 904 application. This document does not mandate any approach as this is 905 an operational and management decision. 907 With real-time flows, a lost ADU that is decoded after the maximum 908 latency or an ADU received after this delay should not be passed to 909 the application. Instead the associated source symbols should be 910 removed from the linear system maintained by the receiver(s). 911 Appendix A discusses a backward compatible optimization whereby those 912 late source symbols may still be used in order to improve the global 913 robustness. 915 7. Implementation Status 917 Editor's notes: RFC Editor, please remove this section motivated by 918 RFC 6982 before publishing the RFC. Thanks. 920 An implementation of the Sliding Window RLC FEC Scheme for FECFRAME 921 exists: 923 o Organisation: Inria 924 o Description: This is an implementation of the Sliding Window RLC 925 FEC Scheme limited to GF(2^^8). It relies on a modified version 926 of our OpenFEC (http://openfec.org) FEC code library. It is 927 integrated in our FECFRAME software (see [fecframe-ext]). 928 o Maturity: prototype. 929 o Coverage: this software complies with the Sliding Window RLC FEC 930 Scheme. 931 o Lincensing: proprietary. 932 o Contact: vincent.roca@inria.fr 934 8. Security Considerations 936 The FEC Framework document [RFC6363] provides a comprehensive 937 analysis of security considerations applicable to FEC Schemes. 938 Therefore, the present section follows the security considerations 939 section of [RFC6363] and only discusses specific topics. 941 8.1. Attacks Against the Data Flow 943 8.1.1. Access to Confidential Content 945 The Sliding Window RLC FEC Scheme specified in this document does not 946 change the recommendations of [RFC6363]. To summarize, if 947 confidentiality is a concern, it is RECOMMENDED that one of the 948 solutions mentioned in [RFC6363] is used with special considerations 949 to the way this solution is applied (e.g., is encryption applied 950 before or after FEC protection, within the end-system or in a 951 middlebox) to the operational constraints (e.g., performing FEC 952 decoding in a protected environment may be complicated or even 953 impossible) and to the threat model. 955 8.1.2. Content Corruption 957 The Sliding Window RLC FEC Scheme specified in this document does not 958 change the recommendations of [RFC6363]. To summarize, it is 959 RECOMMENDED that one of the solutions mentioned in [RFC6363] is used 960 on both the FEC Source and Repair Packets. 962 8.2. Attacks Against the FEC Parameters 964 The FEC Scheme specified in this document defines parameters that can 965 be the basis of attacks. More specifically, the following parameters 966 of the FFCI may be modified by an attacker who targets receivers 967 (Section 4.1.1.2): 969 o FEC Encoding ID: changing this parameter leads the receivers to 970 consider a different FEC Scheme, which enables an attacker to 971 create a Denial of Service (DoS); 972 o Encoding symbol length (E): setting this E parameter to a 973 different value will confuse the receivers and create a DoS. More 974 precisely, the FEC Repair Packets received will probably no longer 975 be multiple of E, leading receivers to reject them; 977 It is therefore RECOMMENDED that security measures are taken to 978 guarantee the FFCI integrity, as specified in [RFC6363]. How to 979 achieve this depends on the way the FFCI is communicated from the 980 sender to the receiver, which is not specified in this document. 982 Similarly, attacks are possible against the Explicit Source FEC 983 Payload ID and Repair FEC Payload ID: by modifying the Encoding 984 Symbol ID (ESI), or the repair key, NSS or FSS_ESI. It is therefore 985 RECOMMENDED that security measures are taken to guarantee the FEC 986 Source and Repair Packets as stated in [RFC6363]. 988 8.3. When Several Source Flows are to be Protected Together 990 The Sliding Window RLC FEC Scheme specified in this document does not 991 change the recommendations of [RFC6363]. 993 8.4. Baseline Secure FEC Framework Operation 995 The Sliding Window RLC FEC Scheme specified in this document does not 996 change the recommendations of [RFC6363] concerning the use of the 997 IPsec/ESP security protocol as a mandatory to implement (but not 998 mandatory to use) security scheme. This is well suited to situations 999 where the only insecure domain is the one over which the FEC 1000 Framework operates. 1002 9. Operations and Management Considerations 1004 The FEC Framework document [RFC6363] provides a comprehensive 1005 analysis of operations and management considerations applicable to 1006 FEC Schemes. Therefore, the present section only discusses specific 1007 topics. 1009 9.1. Operational Recommendations: Finite Field GF(2) Versus GF(2^^8) 1011 The present document specifies two FEC Schemes that differ on the 1012 Finite Field used for the coding coefficients. It is expected that 1013 the RLC over GF(2^^8) FEC Scheme will be mostly used since it 1014 warrants a higher packet loss protection. In case of small encoding 1015 windows, the associated processing overhead is not an issue (e.g., we 1016 measured decoding speeds between 745 Mbps and 2.8 Gbps on an ARM 1017 Cortex-A15 embedded board in [Roca17]). Of course the CPU overhead 1018 will increase with the encoding window size, because more operations 1019 in the GF(2^^8) finite field will be needed. 1021 The RLC over GF(2) FEC Scheme offers an alternative. In that case 1022 operations symbols can be directly XOR-ed together which warrants 1023 high bitrate encoding and decoding operations, and can be an 1024 advantage with large encoding windows. However packet loss 1025 protection is significantly reduced by using this FEC Scheme. 1027 9.2. Operational Recommendations: Coding Coefficients Density Threshold 1029 In addition to the choice of the Finite Field, the two FEC Schemes 1030 define a coding coefficient density threshold (DT) parameter. This 1031 parameter enables a sender to control the code density, i.e., the 1032 proportion of coefficients that are non zero on average. With RLC 1033 over GF(2^^8), it is usually appropriate that small encoding windows 1034 be associated to a density threshold equal to 15, the maximum value, 1035 in order to warrant a high loss protection. 1037 On the opposite, with larger encoding windows, it is usually 1038 appropriate that the density threshold be reduced. With large 1039 encoding windows, an alternative can be to use RLC over GF(2) and a 1040 density threshold equal to 7 (i.e., an average density equal to 1/2) 1041 or smaller. 1043 Note that using a density threshold equal to 15 with RLC over GF(2) 1044 is equivalent to using an XOR code that compute the XOR sum of all 1045 the source symbols in the encoding window. In that case: (1) a 1046 single repair symbol can be produced for any encoding window, and (2) 1047 the repair_key parameter becomes useless (the coding coefficients 1048 generation function does not rely on the PRNG). 1050 10. IANA Considerations 1052 This document registers two values in the "FEC Framework (FECFRAME) 1053 FEC Encoding IDs" registry [RFC6363] as follows: 1055 o YYYY refers to the Sliding Window Random Linear Codes (RLC) over 1056 GF(2) FEC Scheme for Arbitrary Packet Flows, as defined in 1057 Section 5 of this document. 1058 o XXXX refers to the Sliding Window Random Linear Codes (RLC) over 1059 GF(2^^8) FEC Scheme for Arbitrary Packet Flows, as defined in 1060 Section 4 of this document. 1062 11. Acknowledgments 1064 The authors would like to thank Marie-Jose Montpetit for her valuable 1065 feedbacks on this document. 1067 12. References 1069 12.1. Normative References 1071 [fecframe-ext] 1072 Roca, V. and A. Begen, "Forward Error Correction (FEC) 1073 Framework Extension to Sliding Window Codes", Transport 1074 Area Working Group (TSVWG) draft-ietf-tsvwg-fecframe-ext 1075 (Work in Progress), March 2018, 1076 . 1079 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1080 Requirement Levels", BCP 14, RFC 2119, 1081 DOI 10.17487/RFC2119, March 1997, 1082 . 1084 [RFC6363] Watson, M., Begen, A., and V. Roca, "Forward Error 1085 Correction (FEC) Framework", RFC 6363, 1086 DOI 10.17487/RFC6363, October 2011, 1087 . 1089 [RFC6364] Begen, A., "Session Description Protocol Elements for the 1090 Forward Error Correction (FEC) Framework", RFC 6364, 1091 DOI 10.17487/RFC6364, October 2011, 1092 . 1094 12.2. Informative References 1096 [CA90] Carta, D., "Two Fast Implementations of the Minimal 1097 Standard Random Number Generator", Communications of the 1098 ACM, Vol. 33, No. 1, pp.87-88, January 1990. 1100 [PM88] Park, S. and K. Miller, "Random Number Generators: Good 1101 Ones are Hard to Find", Communications of the ACM, Vol. 1102 31, No. 10, pp.1192-1201, 1988. 1104 [PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery, 1105 "Numerical Recipies in C; Second Edition", Cambridge 1106 University Press, ISBN: 0-521-43108-5, 1992. 1108 [rand31pmc] 1109 Whittle, R., "31 bit pseudo-random number generator", 1110 September 2005, . 1113 [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity 1114 Check (LDPC) Staircase and Triangle Forward Error 1115 Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170, 1116 June 2008, . 1118 [RFC6726] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen, 1119 "FLUTE - File Delivery over Unidirectional Transport", 1120 RFC 6726, DOI 10.17487/RFC6726, November 2012, 1121 . 1123 [RFC6816] Roca, V., Cunche, M., and J. Lacan, "Simple Low-Density 1124 Parity Check (LDPC) Staircase Forward Error Correction 1125 (FEC) Scheme for FECFRAME", RFC 6816, 1126 DOI 10.17487/RFC6816, December 2012, 1127 . 1129 [RFC6865] Roca, V., Cunche, M., Lacan, J., Bouabdallah, A., and K. 1130 Matsuzono, "Simple Reed-Solomon Forward Error Correction 1131 (FEC) Scheme for FECFRAME", RFC 6865, 1132 DOI 10.17487/RFC6865, February 2013, 1133 . 1135 [Roca16] Roca, V., Teibi, B., Burdinat, C., Tran, T., and C. 1136 Thienot, "Block or Convolutional AL-FEC Codes? A 1137 Performance Comparison for Robust Low-Latency 1138 Communications", HAL open-archive document,hal-01395937 1139 https://hal.inria.fr/hal-01395937/en/, November 2016, 1140 . 1142 [Roca17] Roca, V., Teibi, B., Burdinat, C., Tran, T., and C. 1143 Thienot, "Less Latency and Better Protection with AL-FEC 1144 Sliding Window Codes: a Robust Multimedia CBR Broadcast 1145 Case Study", 13th IEEE International Conference on 1146 Wireless and Mobile Computing, Networking and 1147 Communications (WiMob17), October 1148 2017 https://hal.inria.fr/hal-01571609v1/en/, October 1149 2017, . 1151 [WI08] Whittle, R., "Park-Miller-Carta Pseudo-Random Number 1152 Generator", http://www.firstpr.com.au/dsp/rand31/, 1153 January 2008, . 1155 Appendix A. Decoding Beyond Maximum Latency Optimization 1157 This annex introduces non normative considerations. They are 1158 provided as suggestions, without any impact on interoperability. For 1159 more information see [Roca16]. 1161 It is possible to improve the decoding performance of sliding window 1162 codes without impacting maximum latency, at the cost of extra CPU 1163 overhead. The optimization consists, for a receiver, to extend the 1164 linear system beyond the decoding window, by keeping a certain number 1165 of old source symbols: 1167 ls_max_size > dw_max_size 1169 Usually the following choice is a good trade-off between decoding 1170 performance and extra CPU overhead: 1172 ls_max_size = 2 * dw_max_size 1174 ls_max_size 1175 /---------------------------------^-------------------------------\ 1177 late source symbols 1178 (pot. decoded but not delivered) dw_max_size 1179 /--------------^-----------------\ /--------------^---------------\ 1180 src0 src1 src2 src3 src4 src5 src6 src7 src8 src9 src10 src11 src12 1182 Figure 8: Relationship between parameters to decode beyond maximum 1183 latency. 1185 It means that source symbols, and therefore ADUs, may be decoded even 1186 if the added latency exceeds the maximum value permitted by the 1187 application. It follows that the corresponding ADUs SHOULD NOT be 1188 delivered to the application and SHOULD be dropped once they are no 1189 longer needed. However, decoding these "late symbols" significantly 1190 improves the global robustness in bad reception conditions and is 1191 therefore recommended for receivers experiencing bad communication 1192 conditions [Roca16]. In any case whether or not to use this 1193 optimization and what exact value to use for the ls_max_size 1194 parameter are decisions made by each receiver independently, without 1195 any impact on the other receivers nor on the source. 1197 Authors' Addresses 1198 Vincent Roca 1199 INRIA 1200 Grenoble 1201 France 1203 EMail: vincent.roca@inria.fr 1205 Belkacem Teibi 1206 INRIA 1207 Grenoble 1208 France 1210 EMail: belkacem.teibi@inria.fr