idnits 2.17.1 draft-ietf-rmt-bb-fec-ldpc-08.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 19. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 1443. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1454. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1461. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1467. 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 Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (January 23, 2008) is 5931 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '0' on line 739 ** Downref: Normative reference to an Informational RFC: RFC 3453 -- Obsolete informational reference (is this intentional?): RFC 3447 (Obsoleted by RFC 8017) -- Obsolete informational reference (is this intentional?): RFC 3852 (Obsoleted by RFC 5652) Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 RMT V. Roca 3 Internet-Draft INRIA 4 Intended status: Standards Track C. Neumann 5 Expires: July 26, 2008 Thomson 6 D. Furodet 7 STMicroelectronics 8 January 23, 2008 10 Low Density Parity Check (LDPC) Staircase and Triangle Forward Error 11 Correction (FEC) Schemes 12 draft-ietf-rmt-bb-fec-ldpc-08.txt 14 Status of this Memo 16 By submitting this Internet-Draft, each author represents that any 17 applicable patent or other IPR claims of which he or she is aware 18 have been or will be disclosed, and any of which he or she becomes 19 aware will be disclosed, in accordance with Section 6 of BCP 79. 21 Internet-Drafts are working documents of the Internet Engineering 22 Task Force (IETF), its areas, and its working groups. Note that 23 other groups may also distribute working documents as Internet- 24 Drafts. 26 Internet-Drafts are draft documents valid for a maximum of six months 27 and may be updated, replaced, or obsoleted by other documents at any 28 time. It is inappropriate to use Internet-Drafts as reference 29 material or to cite them other than as "work in progress." 31 The list of current Internet-Drafts can be accessed at 32 http://www.ietf.org/ietf/1id-abstracts.txt. 34 The list of Internet-Draft Shadow Directories can be accessed at 35 http://www.ietf.org/shadow.html. 37 This Internet-Draft will expire on July 26, 2008. 39 Copyright Notice 41 Copyright (C) The IETF Trust (2008). 43 Abstract 45 This document describes two Fully-Specified FEC Schemes, LDPC- 46 Staircase and LDPC-Triangle, and their application to the reliable 47 delivery of data objects on the packet erasure channel (i.e., a 48 communication path where packets are either received without any 49 corruption or discarded during transmission). These systematic FEC 50 codes belong to the well known class of ``Low Density Parity Check'' 51 (LDPC) codes, and are large block FEC codes in the sense of RFC3453. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 56 2. Requirements notation . . . . . . . . . . . . . . . . . . . . 6 57 3. Definitions, Notations and Abbreviations . . . . . . . . . . . 7 58 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 7 59 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 7 60 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 8 61 4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 9 62 4.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 9 63 4.2. FEC Object Transmission Information . . . . . . . . . . . 9 64 4.2.1. Mandatory Element . . . . . . . . . . . . . . . . . . 9 65 4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 9 66 4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 10 67 4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 10 68 5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 13 69 5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 13 70 5.2. Determining the Maximum Source Block Length (B) . . . . . 14 71 5.3. Determining the Encoding Symbol Length (E) and Number 72 of Encoding Symbols per Group (G) . . . . . . . . . . . . 15 73 5.4. Determining the Maximum Number of Encoding Symbols 74 Generated for Any Source Block (max_n) . . . . . . . . . . 16 75 5.5. Determining the Number of Encoding Symbols of a Block 76 (n) . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 77 5.6. Identifying the G Symbols of an Encoding Symbol Group . . 17 78 5.7. Pseudo Random Number Generator . . . . . . . . . . . . . . 21 79 6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 23 80 6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 23 81 6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 23 82 6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 25 83 6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 25 84 7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 27 85 7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 27 86 7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 27 87 7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 28 88 7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 28 89 8. Security Considerations . . . . . . . . . . . . . . . . . . . 29 90 8.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 29 91 8.2. Attacks Against the Data Flow . . . . . . . . . . . . . . 29 92 8.2.1. Access to Confidential Objects . . . . . . . . . . . . 29 93 8.2.2. Content Corruption . . . . . . . . . . . . . . . . . . 30 94 8.3. Attacks Against the FEC Parameters . . . . . . . . . . . . 31 95 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 32 96 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 33 97 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 34 98 11.1. Normative References . . . . . . . . . . . . . . . . . . . 34 99 11.2. Informative References . . . . . . . . . . . . . . . . . . 34 100 Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 37 101 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 39 102 Intellectual Property and Copyright Statements . . . . . . . . . . 40 104 1. Introduction 106 [RFC3453] introduces large block FEC codes as an alternative to small 107 block FEC codes like Reed-Solomon. The main advantage of such large 108 block codes is the possibility to operate efficiently on source 109 blocks of size several tens of thousands (or more) source symbols. 110 The present document introduces the Fully-Specified FEC Encoding ID 3 111 that is intended to be used with the LDPC-Staircase FEC codes, and 112 the Fully-Specified FEC Encoding ID 4 that is intended to be used 113 with the LDPC-Triangle FEC codes [RN04][MK03]. Both schemes belong 114 to the broad class of large block codes. For a definition of the 115 term Fully-Specified Scheme, see [RFC5052], section 4. 117 LDPC codes rely on a dedicated matrix, called a "Parity Check 118 Matrix", at the encoding and decoding ends. The parity check matrix 119 defines relationships (or constraints) between the various encoding 120 symbols (i.e., source symbols and repair symbols), that are later 121 used by the decoder to reconstruct the original k source symbols if 122 some of them are missing. These codes are systematic, in the sense 123 that the encoding symbols include the source symbols in addition to 124 the repair symbols. 126 Since the encoder and decoder must operate on the same parity check 127 matrix, information must be communicated between them as part of the 128 FEC Object Transmission Information. 130 A publicly available reference implementation of these codes is 131 available and distributed under a GNU/LGPL license [LDPC-codec]. 132 Besides, the code extracts included in this document are directly 133 contributed to the IETF process by the authors of this document and 134 by Radford M. Neal. 136 2. Requirements notation 138 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 139 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 140 document are to be interpreted as described in [RFC2119]. 142 3. Definitions, Notations and Abbreviations 144 3.1. Definitions 146 This document uses the same terms and definitions as those specified 147 in [RFC5052]. Additionally, it uses the following definitions: 149 Source symbol: unit of data used during the encoding process 151 Encoding symbol: unit of data generated by the encoding process 153 Repair symbol: encoding symbol that is not a source symbol 155 Code rate: the k/n ratio, i.e., the ratio between the number of 156 source symbols and the number of encoding symbols. The code rate 157 belongs to a ]0; 1] interval. A code rate close to 1 indicates 158 that a small number of repair symbols have been produced during 159 the encoding process 161 Systematic code: FEC code in which the source symbols are part of 162 the encoding symbols 164 Source block: a block of k source symbols that are considered 165 together for the encoding 167 Encoding Symbol Group: a group of encoding symbols that are sent 168 together, within the same packet, and whose relationships to the 169 source object can be derived from a single Encoding Symbol ID 171 Source Packet: a data packet containing only source symbols 173 Repair Packet: a data packet containing only repair symbols 175 Packet Erasure Channel: a communication path where packets are 176 either dropped (e.g., by a congested router, or because the number 177 of transmission errors exceeds the correction capabilities of the 178 physical layer codes) or received. When a packet is received, it 179 is assumed that this packet is not corrupted 181 3.2. Notations 183 This document uses the following notations: 185 L denotes the object transfer length in bytes 187 k denotes the source block length in symbols, i.e., the number of 188 source symbols of a source block 189 n denotes the encoding block length, i.e., the number of encoding 190 symbols generated for a source block 192 E denotes the encoding symbol length in bytes 194 B denotes the maximum source block length in symbols, i.e., the 195 maximum number of source symbols per source block 197 N denotes the number of source blocks into which the object shall 198 be partitioned 200 G denotes the number of encoding symbols per group, i.e., the 201 number of symbols sent in the same packet 203 CR denotes the "code rate", i.e., the k/n ratio 205 max_n denotes the maximum number of encoding symbols generated for 206 any source block. This is in particular the number of encoding 207 symbols generated for a source block of size B 209 H denotes the parity check matrix 211 pmms_rand(m) denotes the pseudo-random number generator defined in 212 Section 5.7 that returns a new random integer in [0; m-1] each 213 time it is called 215 3.3. Abbreviations 217 This document uses the following abbreviations: 219 ESI: Encoding Symbol ID 221 FEC OTI: FEC Object Transmission Information 223 FPI: FEC Payload ID 225 LDPC: Low Density Parity Check 227 PRNG: Pseudo Random Number Generator 229 4. Formats and Codes 231 4.1. FEC Payload IDs 233 The FEC Payload ID is composed of the Source Block Number and the 234 Encoding Symbol ID: 236 The Source Block Number (12 bit field) identifies from which 237 source block of the object the encoding symbol(s) in the packet 238 payload is(are) generated. There are a maximum of 2^^12 blocks 239 per object. Source block numbering starts at 0. 241 The Encoding Symbol ID (20 bit field) identifies which encoding 242 symbol(s) generated from the source block is(are) carried in the 243 packet payload. There are a maximum of 2^^20 encoding symbols per 244 block. The first k values (0 to k-1) identify source symbols, the 245 remaining n-k values (k to n-k-1) identify repair symbols. 247 There MUST be exactly one FEC Payload ID per packet. In case of an 248 Encoding Symbol Group, when multiple encoding symbols are sent in the 249 same packet, the FEC Payload ID refers to the first symbol of the 250 packet. The other symbols can be deduced from the ESI of the first 251 symbol thanks to a dedicated function, as explained in Section 5.6 253 0 1 2 3 254 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 255 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 256 | Source Block Number | Encoding Symbol ID (20 bits) | 257 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 259 Figure 1: FEC Payload ID encoding format for FEC Encoding ID 3 and 4 261 4.2. FEC Object Transmission Information 263 4.2.1. Mandatory Element 265 o FEC Encoding ID: the LDPC-Staircase and LDPC-Triangle Fully- 266 Specified FEC Schemes use respectively the FEC Encoding ID 3 267 (Staircase) and 4 (Triangle). 269 4.2.2. Common Elements 271 The following elements MUST be defined with the present FEC Schemes: 273 o Transfer-Length (L): a non-negative integer indicating the length 274 of the object in bytes. There are some restrictions on the 275 maximum Transfer-Length that can be supported: 277 maximum transfer length = 2^^12 * B * E 279 For instance, if B=2^^19 (because of a code rate of 1/2, 280 Section 5.2), and if E=1024 bytes, then the maximum transfer 281 length is 2^^41 bytes (or 2 TB). The upper limit, with symbols of 282 size 2^^16-1 bytes and a code rate larger or equal to 1/2, amounts 283 to 2^^47 bytes (or 128 TB). 285 o Encoding-Symbol-Length (E): a non-negative integer indicating the 286 length of each encoding symbol in bytes. 288 o Maximum-Source-Block-Length (B): a non-negative integer indicating 289 the maximum number of source symbols in a source block. There are 290 some restrictions on the maximum B value, as explained in 291 Section 5.2. 293 o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer 294 indicating the maximum number of encoding symbols generated for 295 any source block. There are some restrictions on the maximum 296 max_n value. In particular max_n is at most equal to 2^^20. 298 Section 5 explains how to define the values of each of these 299 elements. 301 4.2.3. Scheme-Specific Elements 303 The following elements MUST be defined with the present FEC Scheme: 305 o G: a non-negative integer indicating the number of encoding 306 symbols per group (i.e., per packet). The default value is 1, 307 meaning that each packet contains exactly one symbol. Values 308 greater than 1 can also be defined, as explained in Section 5.3. 310 o PRNG seed: the seed is a 32 bit unsigned integer between 1 and 311 0x7FFFFFFE (i.e., 2^^31-2) inclusive. This value is used to 312 initialize the Pseudo Random Number Generator (Section 5.7). 314 4.2.4. Encoding Format 316 This section shows two possible encoding formats of the above FEC 317 OTI. The present document does not specify when or how these 318 encoding formats should be used. 320 4.2.4.1. Using the General EXT_FTI Format 322 The FEC OTI binary format is the following, when the EXT_FTI 323 mechanism is used (e.g., within the ALC 324 [draft-ietf-rmt-pi-alc-revised] or NORM 326 [draft-ietf-rmt-pi-norm-revised] protocols). 328 0 1 2 3 329 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 330 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 331 | HET = 64 | HEL = 5 | | 332 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 333 | Transfer-Length (L) | 334 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 335 | Encoding Symbol Length (E) | G | B (MSB) | 336 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 337 | B (LSB) | Max Nb of Enc. Symbols (max_n) | 338 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 339 | PRNG seed | 340 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 342 Figure 2: EXT_FTI Header for FEC Encoding ID 3 and 4. 344 In particular: 346 o The Transfer-Length (L) field size (48 bits) is larger than the 347 size required to store the maximum transfer length (Section 4.2.2) 348 for field alignment purposes. 350 o The Maximum-Source-Block-Length (B) field (20 bits) is split into 351 two parts: the 8 most significant bits (MSB) are in the third 32- 352 bit word of the EXT_FTI, and the remaining 12 least significant 353 bits (LSB) are in the fourth 32-bit word. 355 4.2.4.2. Using the FDT Instance (FLUTE specific) 357 When it is desired that the FEC OTI be carried in the FDT Instance of 358 a FLUTE session [draft-ietf-rmt-flute-revised], the following XML 359 attributes must be described for the associated object: 361 o FEC-OTI-FEC-Encoding-ID 363 o FEC-OTI-Transfer-length 365 o FEC-OTI-Encoding-Symbol-Length 367 o FEC-OTI-Maximum-Source-Block-Length 369 o FEC-OTI-Max-Number-of-Encoding-Symbols 371 o FEC-OTI-Scheme-Specific-Info 373 The FEC-OTI-Scheme-Specific-Info contains the string resulting from 374 the Base64 encoding (in the XML Schema xs:base64Binary sense) 375 [RFC4648] of the following value: 377 0 1 2 3 378 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 379 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 380 | PRNG seed | 381 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 382 | G | 383 +-+-+-+-+-+-+-+-+ 385 Figure 3: FEC OTI Scheme Specific Information to be Included in the 386 FDT Instance for FEC Encoding ID 3 and 4. 388 During Base64 encoding, the 5 bytes of the FEC OTI Scheme Specific 389 Information are transformed into a string of 8 printable characters 390 (in the 64-character alphabet) that is added to the FEC-OTI-Scheme- 391 Specific-Info attribute. 393 5. Procedures 395 This section defines procedures that are common to FEC Encoding IDs 3 396 and 4. 398 5.1. General 400 The B (maximum source block length in symbols), E (encoding symbol 401 length in bytes) and G (number of encoding symbols per group) 402 parameters are first determined. The algorithms of Section 5.2 and 403 Section 5.3 MAY be used to that purpose. Using other algorithms is 404 possible without compromising interoperability since the B, E and G 405 parameters are communicated to the receiver by means of the FEC OTI. 407 Then, the source object MUST be partitioned using the block 408 partitioning algorithm specified in [RFC5052]. To that purpose, the 409 B, L (object transfer length in bytes), and E arguments are provided. 410 As a result, the object is partitioned into N source blocks. These 411 blocks are numbered consecutively from 0 to N-1. The first I source 412 blocks consist of A_large source symbols, the remaining N-I source 413 blocks consist of A_small source symbols. Each source symbol is E 414 bytes in length, except perhaps the last symbol which may be shorter. 416 Then, the max_n (maximum number of encoding symbols generated for any 417 source block) parameter is determined. The algorithm of Section 5.4 418 MAY be used to that purpose. Using another algorithm is possible 419 without compromising interoperability since the max_n parameter is 420 communicated to the receiver by means of the FEC OTI. 422 For each block, the actual number of encoding symbols, n, MUST then 423 be determined using the "n-algorithm" detailed in Section 5.5. 425 Then, FEC encoding and decoding can be done block per block, 426 independently. To that purpose, a parity check matrix is created, 427 that forms a system of linear equations between the source and repair 428 symbols of a given block, where the basic operator is XOR. 430 This parity check matrix is logically divided into two parts: the 431 left side (from column 0 to k-1) describes the occurrences of each 432 source symbol in the system of linear equations; the right side (from 433 column k to n-1) describes the occurrences of each repair symbol in 434 the system of linear equations. The only difference between the 435 LDPC-Staircase and LDPC-Triangle schemes is the construction of this 436 right sub-matrix. An entry (a "1") in the matrix at position (i,j) 437 (i.e., at row i and column j) means that the symbol with ESI j 438 appears in equation i of the system. 440 When the parity symbols have been created, the sender transmits 441 source and parity symbols. The way this transmission occurs can 442 largely impact the erasure recovery capabilities of the LDPC-* FEC. 443 In particular, sending parity symbols in sequence is suboptimal. 444 Instead it is usually recommended the shuffle these symbols. The 445 interested reader will find more details in [NRFF05]. 447 The following sections detail how the B, E, G, max_nand n parameters 448 are determined (respectively in Section 5.2, Section 5.3, Section 5.4 449 and Section 5.5), how encoding symbol groups are created 450 (Section 5.6), and finally Section 5.7 details the PRNG. 452 5.2. Determining the Maximum Source Block Length (B) 454 The B parameter (maximum source block length in symbols) depends on 455 several parameters: the code rate (CR), the Encoding Symbol ID field 456 length of the FEC Payload ID (20 bits), as well as possible internal 457 codec limitations. 459 The B parameter cannot be larger than the following values, derived 460 from the FEC Payload ID limitations, for a given code rate: 462 max1_B = 2^^(20 - ceil(Log2(1/CR))) 464 Some common max1_B values are: 466 o CR == 1 (no repair symbol): max1_B = 2^^20 = 1,048,576 468 o 1/2 <= CR < 1: max1_B = 2^^19 = 524,288 symbols 470 o 1/4 <= CR < 1/2: max1_B = 2^^18 = 262,144 symbols 472 o 1/8 <= CR < 1/4: max1_B = 2^^17 = 131,072 symbols 474 Additionally, a codec MAY impose other limitations on the maximum 475 block size. For instance, this is the case when the codec uses 476 internally 16 bit unsigned integers to store the Encoding Symbol ID, 477 since it does not enable to store all the possible values of a 20 bit 478 field. In that case, if for instance 1/2 <= CR < 1, then the maximum 479 source block length is 2^^15. Other limitations may also apply, for 480 instance because of a limited working memory size. This decision 481 MUST be clarified at implementation time, when the target use case is 482 known. This results in a max2_B limitation. 484 Then, B is given by: 486 B = min(max1_B, max2_B) 488 Note that this calculation is only required at the coder, since the B 489 parameter is communicated to the decoder through the FEC OTI. 491 5.3. Determining the Encoding Symbol Length (E) and Number of Encoding 492 Symbols per Group (G) 494 The E parameter usually depends on the maximum transmission unit on 495 the path (PMTU) from the source to each receiver. In order to 496 minimize the protocol header overhead (e.g., the LCT/UDP/IPv4 or IPv6 497 headers in case of ALC), E is chosen as large as possible. In that 498 case, E is chosen so that the size of a packet composed of a single 499 symbol (G=1) remains below but close to the PMTU. 501 However other considerations can exist. For instance, the E 502 parameter can be made a function of the object transfer length. 503 Indeed, LDPC codes are known to offer better protection for large 504 blocks. In case of small objects, it can be advantageous to reduce 505 the encoding symbol length (E) in order to artificially increase the 506 number of symbols, and therefore the block size. 508 In order to minimize the protocol header overhead, several symbols 509 can be grouped in the same Encoding Symbol Group (i.e., G > 1). 510 Depending on how many symbols are grouped (G) and on the packet loss 511 rate (G symbols are lost for each packet erasure), this strategy 512 might or might not be appropriate. A balance must therefore be 513 found. 515 The current specification does not mandate any value for either E or 516 G. The current specification only provides an example of possible 517 choices for E and G. Note that this choice is done by the sender, and 518 the E and G parameters are then communicated to the receiver thanks 519 to the FEC OTI. Note also that the decoding algorithm used 520 influences the choice of the E and G parameters. Indeed, increasing 521 the number of symbols will negatively impact the processing load when 522 decoding is based (in part or totally) on Gaussian elimination, 523 whereas the impacts will be rather low when decoding is based on the 524 trivial algorithm sketched in Section 6.4. 526 Example: 528 Let us assume that the trivial decoding algorithm sketched in 529 Section 6.4 is used. First define the target packet payload size, 530 pkt_sz (at most equal to the PMTU minus the size of the various 531 protocol headers). The pkt_sz must be chosen in such a way that the 532 symbol size is an integer. This can require that pkt_sz be a 533 multiple of 4, 8 or 16 (see the table below). Then calculate the 534 number of packets in the object: nb_pkts = ceil(L / pkt_sz). 535 Finally, thanks to nb_pkts, use the following table to find a 536 possible G value. 538 +------------------------+----+-------------+-------------------+ 539 | Number of packets | G | Symbol size | k | 540 +------------------------+----+-------------+-------------------+ 541 | 4000 <= nb_pkts | 1 | pkt_sz | 4000 <= k | 542 | | | | | 543 | 1000 <= nb_pkts < 4000 | 4 | pkt_sz / 4 | 4000 <= k < 16000 | 544 | | | | | 545 | 500 <= nb_pkts < 1000 | 8 | pkt_sz / 8 | 4000 <= k < 8000 | 546 | | | | | 547 | 1 <= nb_pkts < 500 | 16 | pkt_sz / 16 | 16 <= k < 8000 | 548 +------------------------+----+-------------+-------------------+ 550 5.4. Determining the Maximum Number of Encoding Symbols Generated for 551 Any Source Block (max_n) 553 The following algorithm MAY be used by a sender to determine the 554 maximum number of encoding symbols generated for any source block 555 (max_n) as a function of B and the target code rate. Since the max_n 556 parameter is communicated to the decoder by means of the FEC OTI, 557 another method MAY be used to determine max_n. 559 Input: 561 B: Maximum source block length, for any source block. Section 5.2 562 MAY be used to determine its value. 564 CR: FEC code rate, which is provided by the user (e.g., when 565 starting a FLUTE sending application). It is expressed as a 566 floating point value. The CR value must be such that the 567 resulting number of encoding symbols per block is at most equal to 568 2^^20 (Section 4.1). 570 Output: 572 max_n: Maximum number of encoding symbols generated for any source 573 block. 575 Algorithm: 577 max_n = ceil(B / CR); 579 if (max_n > 2^^20) then return an error ("invalid code rate"); 581 (NB: if B has been defined as explained in Section 5.2, this error 582 should never happen) 584 5.5. Determining the Number of Encoding Symbols of a Block (n) 586 The following algorithm, also called "n-algorithm", MUST be used by 587 the sender and the receiver to determine the number of encoding 588 symbols for a given block (n) as a function of B, k, and max_n. 590 Input: 592 B: Maximum source block length, for any source block. At a 593 sender, Section 5.2 MAY be used to determine its value. At a 594 receiver, this value MUST be extracted from the received FEC OTI. 596 k: Current source block length. At a sender or receiver, the 597 block partitioning algorithm MUST be used to determine its value. 599 max_n: Maximum number of encoding symbols generated for any source 600 block. At a sender, Section 5.4 MAY be used to determine its 601 value. At a receiver, this value MUST be extracted from the 602 received FEC OTI. 604 Output: 606 n: Number of encoding symbols generated for this source block. 608 Algorithm: 610 n = floor(k * max_n / B); 612 5.6. Identifying the G Symbols of an Encoding Symbol Group 614 When multiple encoding symbols are sent in the same packet, the FEC 615 Payload ID information of the packet MUST refer to the first encoding 616 symbol. It MUST then be possible to identify each symbol from this 617 single FEC Payload ID. To that purpose, the symbols of an Encoding 618 Symbol Group (i.e., packet): 620 o MUST all be either source symbols, or repair symbols. Therefore 621 only source packets and repair packets are permitted, not mixed 622 ones. 624 o are identified by a function, sender(resp. 625 receiver)_find_ESIs_of_group(), that takes as argument: 627 * for a sender, the index of the Encoding Symbol Group (i.e., 628 packet) that the application wants to create, 630 * for a receiver, the ESI information contained in the FEC 631 Payload ID. 633 and returns a list of G Encoding Symbol IDs. In case of a source 634 packet, the G Encoding Symbol IDs are chosen consecutively, by 635 incrementing the ESI. In case of a repair packet, the G repair 636 symbols are chosen randomly, as explained below. 638 o are stored in sequence in the packet, without any padding. In 639 other words, the last byte of the i-th symbol is immediately 640 followed by the first byte of (i+1)-th symbol. 642 The system must first be initialized by creating a random permutation 643 of the n-k indexes. This initialization function MUST be called 644 immediately after creating the parity check matrix. More precisely, 645 since the PRNG seed is not re-initialized, no call to the PRNG 646 function must have happened between the time the parity check matrix 647 has been initialized and the time the following initialization 648 function is called. This is true both at a sender and at a receiver. 650 int *txseqToID; 651 int *IDtoTxseq; 653 /* 654 * Initialization function. 655 * Warning: use only when G > 1. 656 */ 657 void 658 initialize_tables () 659 { 660 int i; 661 int randInd; 662 int backup; 664 txseqToID = malloc((n-k) * sizeof(int)); 665 IDtoTxseq = malloc((n-k) * sizeof(int)); 666 if (txseqToID == NULL || IDtoTxseq == NULL) 667 handle the malloc failures as appropriate... 668 /* initialize the two tables that map ID 669 * (i.e., ESI-k) to/from TxSequence. */ 670 for (i = 0; i < n - k; i++) { 671 IDtoTxseq[i] = i; 672 txseqToID[i] = i; 673 } 674 /* now randomize everything */ 675 for (i = 0; i < n - k; i++) { 676 randInd = pmms_rand(n - k); 677 backup = IDtoTxseq[i]; 678 IDtoTxseq[i] = IDtoTxseq[randInd]; 679 IDtoTxseq[randInd] = backup; 680 txseqToID[IDtoTxseq[i]] = i; 681 txseqToID[IDtoTxseq[randInd]] = randInd; 682 } 683 return; 684 } 686 It is then possible, at the sender, to determine the sequence of G 687 Encoding Symbol IDs that will be part of the group. 689 /* 690 * Determine the sequence of ESIs for the packet under construction 691 * at a sender. 692 * Warning: use only when G > 1. 693 * PktIdx (IN): index of the packet, in 694 * {0..ceil(k/G)+ceil((n-k)/G)} range 695 * ESIs[] (OUT): list of ESIs for the packet 696 */ 697 void 698 sender_find_ESIs_of_group (int PktIdx, 699 ESI_t ESIs[]) 700 { 701 int i; 703 if (PktIdx < nbSourcePkts) { 704 /* this is a source packet */ 705 ESIs[0] = PktIdx * G; 706 for (i = 1; i < G; i++) { 707 ESIs[i] = (ESIs[0] + i) % k; 708 } 709 } else { 710 /* this is a repair packet */ 711 for (i = 0; i < G; i++) { 712 ESIs[i] = 713 k + 714 txseqToID[(i + (PktIdx - nbSourcePkts) * G) 715 % (n - k)]; 716 } 717 } 718 return; 719 } 721 Similarly, upon receiving an Encoding Symbol Group (i.e., packet), a 722 receiver can determine the sequence of G Encoding Symbol IDs from the 723 first ESI, esi0, that is contained in the FEC Payload ID. 725 /* 726 * Determine the sequence of ESIs for the packet received. 727 * Warning: use only when G > 1. 728 * esi0 (IN): : ESI contained in the FEC Payload ID 729 * ESIs[] (OUT): list of ESIs for the packet 730 */ 731 void 732 receiver_find_ESIs_of_group (ESI_t esi0, 733 ESI_t ESIs[]) 734 { 735 int i; 737 if (esi0 < k) { 738 /* this is a source packet */ 739 ESIs[0] = esi0; 740 for (i = 1; i < G; i++) { 741 ESIs[i] = (esi0 + i) % k; 742 } 743 } else { 744 /* this is a repair packet */ 745 for (i = 0; i < G; i++) { 746 ESIs[i] = 747 k + 748 txseqToID[(i + IDtoTxseq[esi0 - k]) 749 % (n - k)]; 750 } 751 } 752 } 754 5.7. Pseudo Random Number Generator 756 The FEC Encoding IDs 3 and 4 rely on a pseudo-random number generator 757 (PRNG) that must be fully specified, in particular in order to enable 758 the receivers and the senders to build the same parity check matrix. 760 The Park-Miler "minimal standard" PRNG [PM88] MUST be used. It 761 defines a simple multiplicative congruential algorithm: Ij+1 = A * Ij 762 (modulo M), with the following choices: A = 7^^5 = 16807 and M = 763 2^^31 - 1 = 2147483647. A validation criteria of such a PRNG is the 764 following: if seed = 1, then the 10,000th value returned MUST be 765 equal to 1043618065. 767 Several implementations of this PRNG are known and discussed in the 768 literature. An optimized implementation of this algorithm, using 769 only 32 bit mathematics and which does not require any division, can 770 be found in [rand31pmc]. It uses the Park and Miller algorithm 771 [PM88] with the optimization suggested by D. Carta in [CA90]. The 772 history behind this algorithm is detailed in [WI08]. Yet any other 773 implementation of the PRNG algorithm that matches the above 774 validation criteria, like the ones detailed in [PM88], is 775 appropriate. 777 This PRNG produces natively a 31 bit value between 1 and 0x7FFFFFFE 778 (2^^31-2) inclusive. Since it is desired to scale the pseudo random 779 number between 0 and maxv-1 inclusive, one must keep the most 780 significant bits of the value returned by the PRNG (the least 781 significant bits are known to be less random and modulo based 782 solutions should be avoided [PTVF92]). The following algorithm MUST 783 be used: 785 Input: 787 raw_value: random integer generated by the inner PRNG algorithm, 788 between 1 and 0x7FFFFFFE (2^^31-2) inclusive. 790 maxv: upper bound used during the scaling operation. 792 Output: 794 scaled_value: random integer between 0 and maxv-1 inclusive. 796 Algorithm: 798 scaled_value = (unsigned long) ((double)maxv * (double)raw_value / 799 (double)0x7FFFFFFF); 801 (NB: the above C type casting to unsigned long is equivalent to 802 using floor() with positive floating point values) 804 In this document, pmms_rand(maxv) denotes the PRNG function that 805 implements the Park-Miller "minimal standard" algorithm defined above 806 and that scales the raw value between 1 and maxv-1 inclusive, using 807 the above scaling algorithm. Additionally, a function should be 808 provided to enable the initialization of the PRNG with a seed (i.e., 809 a 31 bit interger between 1 and 0x7FFFFFFE inclusive) before calling 810 pmms_rand(maxv) the first time. 812 6. Full Specification of the LDPC-Staircase Scheme 814 6.1. General 816 The LDPC-Staircase scheme is identified by the Fully-Specified FEC 817 Encoding ID 3. 819 The PRNG used by the LDPC-Staircase scheme must be initialized by a 820 seed. This PRNG seed is an instance-specific FEC OTI attribute 821 (Section 4.2.3). 823 6.2. Parity Check Matrix Creation 825 The LDPC-Staircase matrix can be divided into two parts: the left 826 side of the matrix defines in which equations the source symbols are 827 involved; the right side of the matrix defines in which equations the 828 repair symbols are involved. 830 The left side MUST be generated by using the following function: 832 /* 833 * Initialize the left side of the parity check matrix. 834 * This function assumes that an empty matrix of size n-k * k has 835 * previously been allocated/reset and that the matrix_has_entry(), 836 * matrix_insert_entry() and degree_of_row() functions can access it. 837 * (IN): the k and n parameters. 838 */ 839 void left_matrix_init (int k, int n) 840 { 841 int i; /* row index or temporary variable */ 842 int j; /* column index */ 843 int h; 844 int t; /* left limit within the list of possible choices u[] */ 845 int u[3*MAX_K]; /* table used to have a homogeneous 1 distrib. */ 847 /* Initialize a list of all possible choices in order to 848 * guarantee a homogeneous "1" distribution */ 849 for (h = 3*k-1; h >= 0; h--) { 850 u[h] = h % (n-k); 851 } 853 /* Initialize the matrix with 3 "1s" per column, homogeneously */ 854 t = 0; 855 for (j = 0; j < k; j++) { /* for each source symbol column */ 856 for (h = 0; h < 3; h++) { /* add 3 "1s" */ 857 /* check that valid available choices remain */ 858 for (i = t; i < 3*k && matrix_has_entry(u[i], j); i++); 859 if (i < 3*k) { 860 /* choose one index within the list of possible 861 * choices */ 862 do { 863 i = t + pmms_rand(3*k-t); 864 } while (matrix_has_entry(u[i], j)); 865 matrix_insert_entry(u[i], j); 867 /* replace with u[t] which has never been chosen */ 868 u[i] = u[t]; 869 t++; 870 } else { 871 /* no choice left, choose one randomly */ 872 do { 873 i = pmms_rand(n-k); 874 } while (matrix_has_entry(i, j)); 875 matrix_insert_entry(i, j); 876 } 877 } 878 } 880 /* Add extra bits to avoid rows with less than two "1s". 881 * This is needed when the code rate is smaller than 2/5. */ 882 for (i = 0; i < n-k; i++) { /* for each row */ 883 if (degree_of_row(i) == 0) { 884 j = pmms_rand(k); 885 matrix_insert_entry(i, j); 886 } 887 if (degree_of_row(i) == 1) { 888 do { 889 j = pmms_rand(k); 890 } while (matrix_has_entry(i, j)); 891 matrix_insert_entry(i, j); 892 } 893 } 894 } 896 The right side (the staircase) MUST be generated by using the 897 following function: 899 /* 900 * Initialize the right side of the parity check matrix with a 901 * staircase structure. 902 * (IN): the k and n parameters. 903 */ 904 void right_matrix_staircase_init (int k, int n) 905 { 906 int i; /* row index */ 908 matrix_insert_entry(0, k); /* first row */ 909 for (i = 1; i < n-k; i++) { /* for the following rows */ 910 matrix_insert_entry(i, k+i); /* identity */ 911 matrix_insert_entry(i, k+i-1); /* staircase */ 912 } 913 } 915 Note that just after creating this parity check matrix, when encoding 916 symbol groups are used (i.e., G > 1), the function initializing the 917 two random permutation tables (Section 5.6) MUST be called. This is 918 true both at a sender and at a receiver. 920 6.3. Encoding 922 Thanks to the staircase matrix, repair symbol creation is 923 straightforward: each repair symbol is equal to the sum of all source 924 symbols in the associated equation, plus the previous repair symbol 925 (except for the first repair symbol). Therefore encoding MUST follow 926 the natural repair symbol order: start with the first repair symbol, 927 and generate repair symbol with ESI i before symbol with ESI i+1. 929 6.4. Decoding 931 Decoding basically consists in solving a system of n-k linear 932 equations whose variables are the n source and repair symbols. Of 933 course, the final goal is to recover the value of the k source 934 symbols only. 936 To that purpose, many techniques are possible. One of them is the 937 following trivial algorithm [ZP74]: given a set of linear equations, 938 if one of them has only one remaining unknown variable, then the 939 value of this variable is that of the constant term. So, replace 940 this variable by its value in all the remaining linear equations and 941 reiterate. The value of several variables can therefore be found 942 recursively. Applied to LDPC FEC codes working over an erasure 943 channel, the parity check matrix defines a set of linear equations 944 whose variables are the source symbols and repair symbols. Receiving 945 or decoding a symbol is equivalent to having the value of a variable. 946 Appendix A sketches a possible implementation of this algorithm. 948 A Gaussian elimination (or any optimized derivative) is another 949 possible decoding technique. Hybrid solutions that start by using 950 the trivial algorithm above and finish with a Gaussian elimination 951 are also possible. 953 Because interoperability does not depend on the decoding algorithm 954 used, the current document does not recommend any particular 955 technique. This choice is left to the codec developer. 957 However choosing a decoding technique will have great practical 958 impacts. It will impact the erasure capabilities: a Gaussian 959 elimination enables to solve the system with a smaller number of 960 known symbols compared to the trivial technique. It will also impact 961 the CPU load: a Gaussian elimination requires more processing than 962 the above trivial algorithm. Depending on the target use case, the 963 codec developer will favor one feature or the other. 965 7. Full Specification of the LDPC-Triangle Scheme 967 7.1. General 969 LDPC-Triangle is identified by the Fully-Specified FEC Encoding ID 4. 971 The PRNG used by the LDPC-Triangle scheme must be initialized by a 972 seed. This PRNG seed is an instance-specific FEC OTI attribute 973 (Section 4.2.3). 975 7.2. Parity Check Matrix Creation 977 The LDPC-Triangle matrix can be divided into two parts: the left side 978 of the matrix defines in which equations the source symbols are 979 involved; the right side of the matrix defines in which equations the 980 repair symbols are involved. 982 The left side MUST be generated by using the same left_matrix_init() 983 function as with LDPC-Staircase (Section 6.2). 985 The right side (the triangle) MUST be generated by using the 986 following function: 988 /* 989 * Initialize the right side of the parity check matrix with a 990 * triangle structure. 991 * (IN): the k and n parameters. 992 */ 993 void right_matrix_staircase_init (int k, int n) 994 { 995 int i; /* row index */ 996 int j; /* randomly chosen column indexes in 0..n-k-2 */ 997 int l; /* limitation of the # of "1s" added per row */ 999 matrix_insert_entry(0, k); /* first row */ 1000 for (i = 1; i < n-k; i++) { /* for the following rows */ 1001 matrix_insert_entry(i, k+i); /* identity */ 1002 matrix_insert_entry(i, k+i-1); /* staircase */ 1003 /* now fill the triangle */ 1004 j = i-1; 1005 for (l = 0; l < j; l++) { /* limit the # of "1s" added */ 1006 j = pmms_rand(j); 1007 matrix_insert_entry(i, k+j); 1008 } 1009 } 1010 } 1012 Note that just after creating this parity check matrix, when encoding 1013 symbol groups are used (i.e., G > 1), the function initializing the 1014 two random permutation tables (Section 5.6) MUST be called. This is 1015 true both at a sender and at a receiver. 1017 7.3. Encoding 1019 Here also repair symbol creation is straightforward: each repair 1020 symbol of ESI i is equal to the sum of all source and repair symbols 1021 (with ESI lower than i) in the associated equation. Therefore 1022 encoding MUST follow the natural repair symbol order: start with the 1023 first repair symbol, and generate repair symbol with ESI i before 1024 symbol with ESI i+1. 1026 7.4. Decoding 1028 Decoding basically consists in solving a system of n-k linear 1029 equations, whose variables are the n source and repair symbols. Of 1030 course, the final goal is to recover the value of the k source 1031 symbols only. To that purpose, many techniques are possible, as 1032 explained in Section 6.4. 1034 Because interoperability does not depend on the decoding algorithm 1035 used, the current document does not recommend any particular 1036 technique. This choice is left to the codec implementer. 1038 8. Security Considerations 1040 8.1. Problem Statement 1042 A content delivery system is potentially subject to many attacks: 1043 some of them target the network (e.g., to compromise the routing 1044 infrastructure, by compromising the congestion control component), 1045 others target the Content Delivery Protocol (CDP) (e.g., to 1046 compromise its normal behavior), and finally some attacks target the 1047 content itself. Since this document focuses on a FEC building block 1048 independently of any particular CDP (even if ALC and NORM are two 1049 natural candidates), this section only discusses the additional 1050 threats that an arbitrary CDP may be exposed to when using this 1051 building block. 1053 More specifically, several kinds of attacks exist: 1055 o those that are meant to give access to a confidential content 1056 (e.g., in case of a non-free content), 1058 o those that try to corrupt the object being transmitted (e.g., to 1059 inject malicious code within an object, or to prevent a receiver 1060 from using an object), 1062 o and those that try to compromise the receiver's behavior (e.g., by 1063 making the decoding of an object computationally expensive). 1065 These attacks can be launched either against the data flow itself 1066 (e.g., by sending forged symbols) or against the FEC parameters that 1067 are sent either in-band (e.g., in an EXT_FTI or FDT Instance) or out- 1068 of-band (e.g., in a session description). 1070 8.2. Attacks Against the Data Flow 1072 First of all, let us consider the attacks against the data flow. 1074 8.2.1. Access to Confidential Objects 1076 Access control to a confidential object being transmitted is 1077 typically provided by means of encryption. This encryption can be 1078 done over the whole object (e.g., by the content provider, before the 1079 FEC encoding process), or be done on a packet per packet basis (e.g., 1080 when IPsec/ESP is used [RFC4303]). If confidentiality is a concern, 1081 it is RECOMMENDED that one of these solutions be used. Even if we 1082 mention these attacks here, they are not related nor facilitated by 1083 the use of FEC. 1085 8.2.2. Content Corruption 1087 Protection against corruptions (e.g., after sending forged packets) 1088 is achieved by means of a content integrity verification/sender 1089 authentication scheme. This service can be provided at the object 1090 level, but in that case a receiver has no way to identify which 1091 symbol(s) is(are) corrupted if the object is detected as corrupted. 1092 This service can also be provided at the packet level. In this case, 1093 after removing all forged packets, the object may be in some case 1094 recovered. Several techniques can provide this source 1095 authentication/content integrity service: 1097 o at the object level, the object MAY be digitally signed (with 1098 public key cryptography), for instance by using RSASSA-PKCS1-v1_5 1099 [RFC3447]. This signature enables a receiver to check the object 1100 integrity, once this latter has been fully decoded. Even if 1101 digital signatures are computationally expensive, this calculation 1102 occurs only once per object, which is usually acceptable; 1104 o at the packet level, each packet can be digitally signed. A major 1105 limitation is the high computational and transmission overheads 1106 that this solution requires (unless perhaps if Elliptic Curve 1107 Cryptography (ECC) is used). To avoid this problem, the signature 1108 may span a set of symbols (instead of a single one) in order to 1109 amortize the signature calculation. But if a single symbol is 1110 missing, the integrity of the whole set cannot be checked; 1112 o at the packet level, a Group Message Authentication Code (MAC) 1113 [RFC2104] scheme can be used, for instance by using HMAC-SHA-1 1114 with a secret key shared by all the group members, senders and 1115 receivers. This technique creates a cryptographically secured 1116 (thanks to the secret key) digest of a packet that is sent along 1117 with the packet. The Group MAC scheme does not create prohibitive 1118 processing load nor transmission overhead, but it has a major 1119 limitation: it only provides a group authentication/integrity 1120 service since all group members share the same secret group key, 1121 which means that each member can send a forged packet. It is 1122 therefore restricted to situations where group members are fully 1123 trusted (or in association with another technique as a pre-check); 1125 o at the packet level, TESLA [RFC4082] is an attractive solution 1126 that is robust to losses, provides a true authentication/integrity 1127 service, and does not create any prohibitive processing load or 1128 transmission overhead. Yet checking a packet requires a small 1129 delay (a second or more) after its reception; 1131 Techniques relying on public key cryptography (digital signatures and 1132 TESLA during the bootstrap process, when used) require that public 1133 keys be securely associated to the entities. This can be achieved by 1134 a Public Key Infrastructure (PKI), or by a PGP Web of Trust, or by 1135 pre-distributing the public keys of each group member. 1137 Techniques relying on symmetric key cryptography (group MAC) require 1138 that a secret key be shared by all group members. This can be 1139 achieved by means of a group key management protocol, or simply by 1140 pre-distributing the secret key (but this manual solution has many 1141 limitations). 1143 It is up to the CDP developer, who knows the security requirements 1144 and features of the target application area, to define which solution 1145 is the most appropriate. Nonetheless, in case there is any concern 1146 of the threat of object corruption, it is RECOMMENDED that at least 1147 one of these techniques be used. 1149 8.3. Attacks Against the FEC Parameters 1151 Let us now consider attacks against the FEC parameters (or FEC OTI). 1152 The FEC OTI can either be sent in-band (i.e., in an EXT_FTI or in an 1153 FDT Instance containing FEC OTI for the object) or out-of-band (e.g., 1154 in a session description). Attacks on these FEC parameters can 1155 prevent the decoding of the associated object: for instance modifying 1156 the B parameter will lead to a different block partitioning. 1158 It is therefore RECOMMENDED that security measures be taken to 1159 guarantee the FEC OTI integrity. To that purpose, the packets 1160 carrying the FEC parameters sent in-band in an EXT_FTI header 1161 extension SHOULD be protected by one of the per-packet techniques 1162 described above: digital signature, group MAC, or TESLA. When FEC 1163 OTI is contained in an FDT Instance, this object SHOULD be protected, 1164 for instance by digitally signing it with XML digital signatures 1165 [RFC3275]. Finally, when FEC OTI is sent out-of-band (e.g., in a 1166 session description) this latter SHOULD be protected, for instance by 1167 digitally signing it with [RFC3852]. 1169 The same considerations concerning the key management aspects apply 1170 here also. 1172 9. IANA Considerations 1174 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA 1175 registration. For general guidelines on IANA considerations as they 1176 apply to this document, see [RFC5052]. 1178 This document assigns the Fully-Specified FEC Encoding ID 3 under the 1179 "ietf:rmt:fec:encoding" name-space to "LDPC Staircase Codes". 1181 This document assigns the Fully-Specified FEC Encoding ID 4 under the 1182 "ietf:rmt:fec:encoding" name-space to "LDPC Triangle Codes". 1184 10. Acknowledgments 1186 Section 5.5 is derived from a previous Internet-Draft, and we would 1187 like to thank S. Peltotalo and J. Peltotalo for their contribution. 1188 We would also like to thank Pascal Moniot, Laurent Fazio, Aurelien 1189 Francillon, Shao Wenjian, Magnus Westerlund, Brian Carpenter, Tim 1190 Polk, Jari Arkko, Chris Newman, Robin Whittle and Alfred Hoenes for 1191 their comments. 1193 Last but not least, the authors are grateful to Radford M. Neal 1194 (University of Toronto) whose LDPC software 1195 (http://www.cs.toronto.edu/~radford/ldpc.software.html) inspired this 1196 work. 1198 11. References 1200 11.1. Normative References 1202 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1203 Requirement Levels", RFC 2119, BCP 14, March 1997. 1205 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 1206 Correction (FEC) Building Block", RFC 5052, August 2007. 1208 [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, 1209 M., and J. Crowcroft, "The Use of Forward Error Correction 1210 (FEC) in Reliable Multicast", RFC 3453, December 2002. 1212 11.2. Informative References 1214 [ZP74] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low- 1215 Density Codes for Transmission in a Channel with 1216 Erasures", Translated from Problemy Peredachi 1217 Informatsii, Vol.10, No. 1, pp.15-28, January-March 1974. 1219 [RN04] Roca, V. and C. Neumann, "Design, Evaluation and 1220 Comparison of Four Large Block FEC Codecs: LDPC, LDGM, 1221 LDGM-Staircase and LDGM-Triangle, Plus a Reed-Solomon 1222 Small Block FEC Codec", INRIA Research Report RR-5225, 1223 June 2004. 1225 [NRFF05] Neumann, C., Roca, V., Francillon, A., and D. Furodet, 1226 "Impacts of Packet Scheduling and Packet Loss Distribution 1227 on FEC Performances: Observations and Recommendations", 1228 ACM CoNEXT'05 Conference, Toulouse, France (an extended 1229 version is available as INRIA Research Report RR-5578), 1230 October 2005. 1232 [LDPC-codec] 1233 Roca, V., Neumann, C., Cunche, M., and J. Laboure, "LDPC- 1234 Staircase/LDPC-Triangle Codec Reference Implementation", 1235 INRIA Rhone-Alpes and STMicroelectronics, 1236 http://planete-bcast.inrialpes.fr/. 1238 [MK03] MacKay, D., "Information Theory, Inference and Learning 1239 Algorithms", Cambridge University Press, ISBN: 0-521- 1240 64298-1, 2003. 1242 [PM88] Park, S. and K. Miller, "Random Number Generators: Good 1243 Ones are Hard to Find", Communications of the ACM, Vol. 1244 31, No. 10, pp.1192-1201, 1988. 1246 [CA90] Carta, D., "Two Fast Implementations of the Minimal 1247 Standard Random Number Generator", Communications of the 1248 ACM, Vol. 33, No. 1, pp.87-88, January 1990. 1250 [WI08] Whittle, R., "Park-Miller-Carta Pseudo-Random Number 1251 Generator", http://www.firstpr.com.au/dsp/rand31/, 1252 January 2008. 1254 [rand31pmc] 1255 Whittle, R., "31 bit pseudo-random number generator", htt 1256 p://www.firstpr.com.au/dsp/rand31/ 1257 rand31-park-miller-carta.cc.txt, September 2005. 1259 [PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery, 1260 "Numerical Recipies in C; Second Edition", Cambridge 1261 University Press, ISBN: 0-521-43108-5, 1992. 1263 [draft-ietf-rmt-pi-alc-revised] 1264 Luby, M., Watson, M., and L. Vicisano, "Asynchronous 1265 Layered Coding (ALC) Protocol Instantiation", 1266 draft-ietf-rmt-pi-alc-revised-04.txt (work in progress), 1267 February 2007. 1269 [draft-ietf-rmt-pi-norm-revised] 1270 Adamson, B., Bormann, C., Handley, M., and J. Macker, 1271 "Negative-acknowledgment (NACK)-Oriented Reliable 1272 Multicast (NORM) Protocol", 1273 draft-ietf-rmt-pi-norm-revised-05.txt (work in progress), 1274 March 2007. 1276 [draft-ietf-rmt-flute-revised] 1277 Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, 1278 "FLUTE - File Delivery over Unidirectional Transport", 1279 draft-ietf-rmt-flute-revised-05.txt (work in progress), 1280 October 2007. 1282 [RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography 1283 Standards (PKCS) #1: RSA Cryptography Specifications 1284 Version 2.1", RFC 3447, February 2003. 1286 [RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)", 1287 RFC 4303, December 2005. 1289 [RFC2104] "HMAC: Keyed-Hashing for Message Authentication", 1290 RFC 2104, February 1997. 1292 [RFC4082] "Timed Efficient Stream Loss-Tolerant Authentication 1293 (TESLA): Multicast Source Authentication Transform 1294 Introduction", RFC 4082, June 2005. 1296 [RFC3275] Eastlake, D., Reagle, J., and D. Solo, "(Extensible Markup 1297 Language) XML-Signature Syntax and Processing", RFC 3275, 1298 March 2002. 1300 [RFC3852] Housley, R., "Cryptographic Message Syntax (CMS)", 1301 RFC 3852, July 2004. 1303 [RFC4648] Josefsson, S., "The Base16, Base32, and Base64 Data 1304 Encodings", RFC 4648, October 2006. 1306 Appendix A. Trivial Decoding Algorithm (Informative Only) 1308 A trivial decoding algorithm is sketched below (please see 1309 [LDPC-codec] for the details omitted here): 1311 Initialization: allocate a table partial_sum[n-k] of buffers, each 1312 buffer being of size the symbol size. There's one 1313 entry per equation since the buffers are meant to 1314 store the partial sum of each equation; Reset all 1315 the buffers to zero; 1317 /* 1318 * For each newly received or decoded symbol, try to make progress 1319 * in the decoding of the associated source block. 1320 * NB: in case of a symbol group (G>1), this function is called for 1321 * each symbol of the received packet. 1322 * NB: a callback function indicates to the caller that new symbol(s) 1323 * has(have) been decoded. 1324 * new_esi (IN): ESI of the new symbol received or decoded 1325 * new_symb (IN): Buffer of the new symbol received or decoded 1326 */ 1327 void 1328 decoding_step(ESI_t new_esi, 1329 symbol_t *new_symb) 1330 { 1331 If (new_symb is an already decoded or received symbol) { 1332 Return; /* don't waste time with this symbol */ 1333 } 1335 If (new_symb is the last missing source symbol) { 1336 Remember that decoding is finished; 1337 Return; /* work is over now... */ 1338 } 1340 Create an empty list of equations having symbols decoded 1341 during this decoding step; 1343 /* 1344 * First add this new symbol to the partial sum of all the 1345 * equations where the symbol appears. 1346 */ 1347 For (each equation eq in which new_symb is a variable and 1348 having more than one unknown variable) { 1350 Add new_symb to partial_sum[eq]; 1352 Remove entry(eq, new_esi) from the H matrix; 1353 If (the new degree of equation eq == 1) { 1354 /* a new symbol can be decoded, remember the 1355 * equation */ 1356 Append eq to the list of equations having symbols 1357 decoded during this decoding step; 1358 } 1359 } 1361 /* 1362 * Then finish with recursive calls to decoding_step() for each 1363 * newly decoded symbol. 1364 */ 1365 For (each equation eq in the list of equations having symbols 1366 decoded during this decoding step) { 1368 /* 1369 * Because of the recursion below, we need to check that 1370 * decoding is not finished, and that the equation is 1371 * __still__ of degree 1 1372 */ 1373 If (decoding is finished) { 1374 break; /* exit from the loop */ 1375 } 1377 If ((degree of equation eq == 1) { 1378 Let dec_esi be the ESI of the newly decoded symbol in 1379 equation eq; 1381 Remove entry(eq, dec_esi); 1383 Allocate a buffer, dec_symb, for this symbol and 1384 copy partial_sum[eq] to dec_symb; 1386 Inform the caller that a new symbol has been 1387 decoded via a callback function; 1389 /* finally, call this function recursively */ 1390 decoding_step(dec_esi, dec_symb); 1391 } 1392 } 1394 Free the list of equations having symbols decoded; 1395 Return; 1396 } 1398 Authors' Addresses 1400 Vincent Roca 1401 INRIA 1402 655, av. de l'Europe 1403 Inovallee; Montbonnot 1404 ST ISMIER cedex 38334 1405 France 1407 Email: vincent.roca@inria.fr 1408 URI: http://planete.inrialpes.fr/people/roca/ 1410 Christoph Neumann 1411 Thomson 1412 12, bd de Metz 1413 Rennes 35700 1414 France 1416 Email: christoph.neumann@thomson.net 1417 URI: http://planete.inrialpes.fr/people/chneuman/ 1419 David Furodet 1420 STMicroelectronics 1421 12, Rue Jules Horowitz 1422 BP217 1423 Grenoble Cedex 38019 1424 France 1426 Email: david.furodet@st.com 1427 URI: http://www.st.com/ 1429 Full Copyright Statement 1431 Copyright (C) The IETF Trust (2008). 1433 This document is subject to the rights, licenses and restrictions 1434 contained in BCP 78, and except as set forth therein, the authors 1435 retain all their rights. 1437 This document and the information contained herein are provided on an 1438 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1439 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1440 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1441 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1442 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1443 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1445 Intellectual Property 1447 The IETF takes no position regarding the validity or scope of any 1448 Intellectual Property Rights or other rights that might be claimed to 1449 pertain to the implementation or use of the technology described in 1450 this document or the extent to which any license under such rights 1451 might or might not be available; nor does it represent that it has 1452 made any independent effort to identify any such rights. Information 1453 on the procedures with respect to rights in RFC documents can be 1454 found in BCP 78 and BCP 79. 1456 Copies of IPR disclosures made to the IETF Secretariat and any 1457 assurances of licenses to be made available, or the result of an 1458 attempt made to obtain a general license or permission for the use of 1459 such proprietary rights by implementers or users of this 1460 specification can be obtained from the IETF on-line IPR repository at 1461 http://www.ietf.org/ipr. 1463 The IETF invites any interested party to bring to its attention any 1464 copyrights, patents or patent applications, or other proprietary 1465 rights that may cover technology that may be required to implement 1466 this standard. Please address the information to the IETF at 1467 ietf-ipr@ietf.org. 1469 Acknowledgment 1471 Funding for the RFC Editor function is provided by the IETF 1472 Administrative Support Activity (IASA).