idnits 2.17.1 draft-ietf-rmt-bb-fec-rs-05.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 1236. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1247. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1254. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1260. 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 (November 12, 2007) is 6007 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) -- Obsolete informational reference (is this intentional?): RFC 3447 (Obsoleted by RFC 8017) Summary: 1 error (**), 0 flaws (~~), 1 warning (==), 8 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Reliable Multicast Transport J. Lacan 3 Internet-Draft ISAE/LAAS-CNRS 4 Intended status: Standards Track V. Roca 5 Expires: May 15, 2008 INRIA 6 J. Peltotalo 7 S. Peltotalo 8 Tampere University of Technology 9 November 12, 2007 11 Reed-Solomon Forward Error Correction (FEC) Schemes 12 draft-ietf-rmt-bb-fec-rs-05.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 May 15, 2008. 39 Copyright Notice 41 Copyright (C) The IETF Trust (2007). 43 Abstract 45 This document describes a Fully-Specified Forward Error Correction 46 (FEC) Scheme for the Reed-Solomon FEC codes over GF(2^^m), with m in 47 {2..16}, and its application to the reliable delivery of data objects 48 on the packet erasure channel (i.e., a communication path where 49 packets are either received without any corruption or discarded 50 during transmission). 52 This document also describes a Fully-Specified FEC Scheme for the 53 special case of Reed-Solomon codes over GF(2^^8) when there is no 54 encoding symbol group. 56 Finally, in the context of the Under-Specified Small Block Systematic 57 FEC Scheme (FEC Encoding ID 129), this document assigns an FEC 58 Instance ID to the special case of Reed-Solomon codes over GF(2^^8). 60 Reed-Solomon codes belong to the class of Maximum Distance Separable 61 (MDS) codes, i.e., they enable a receiver to recover the k source 62 symbols from any set of k received symbols. The schemes described 63 here are compatible with the implementation from Luigi Rizzo. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 68 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 69 3. Definitions Notations and Abbreviations . . . . . . . . . . . 7 70 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 7 71 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 7 72 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 8 73 4. Formats and Codes with FEC Encoding ID 2 . . . . . . . . . . . 10 74 4.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 10 75 4.2. FEC Object Transmission Information . . . . . . . . . . . 11 76 4.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 11 77 4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 11 78 4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 11 79 4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 12 80 5. Formats and Codes with FEC Encoding ID 5 . . . . . . . . . . . 14 81 5.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 14 82 5.2. FEC Object Transmission Information . . . . . . . . . . . 14 83 5.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 14 84 5.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 14 85 5.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 15 86 5.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 15 87 6. Procedures with FEC Encoding IDs 2 and 5 . . . . . . . . . . . 16 88 6.1. Determining the Maximum Source Block Length (B) . . . . . 16 89 6.2. Determining the Number of Encoding Symbols of a Block . . 16 90 7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) 91 and Reed-Solomon Codes over GF(2^^8) . . . . . . . . . . . . . 19 92 8. Reed-Solomon Codes Specification for the Erasure Channel . . . 20 93 8.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 20 94 8.2. Reed-Solomon Encoding Algorithm . . . . . . . . . . . . . 21 95 8.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 21 96 8.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 22 97 8.3. Reed-Solomon Decoding Algorithm . . . . . . . . . . . . . 22 98 8.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 22 99 8.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 23 100 8.4. Implementation for the Packet Erasure Channel . . . . . . 23 101 9. Security Considerations . . . . . . . . . . . . . . . . . . . 27 102 9.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 27 103 9.2. Attacks Against the Data Flow . . . . . . . . . . . . . . 27 104 9.2.1. Access to Confidential Objects . . . . . . . . . . . . 27 105 9.2.2. Content Corruption . . . . . . . . . . . . . . . . . . 28 106 9.3. Attacks Against the FEC Parameters . . . . . . . . . . . . 29 107 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 30 108 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 31 109 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 32 110 12.1. Normative References . . . . . . . . . . . . . . . . . . . 32 111 12.2. Informative References . . . . . . . . . . . . . . . . . . 32 112 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 34 113 Intellectual Property and Copyright Statements . . . . . . . . . . 35 115 1. Introduction 117 The use of Forward Error Correction (FEC) codes is a classical 118 solution to improve the reliability of multicast and broadcast 119 transmissions. The [RFC5052] document describes a general framework 120 to use FEC in Content Delivery Protocols (CDP). The companion 121 document [RFC3453] describes some applications of FEC codes for 122 content delivery. 124 Recent FEC schemes like [RFC5053] and [draft-ietf-rmt-bb-fec-ldpc] 125 proposed erasure codes based on sparse graphs/matrices. These codes 126 are efficient in terms of processing but not optimal in terms of 127 correction capabilities when dealing with "small" objects. 129 The FEC scheme described in this document belongs to the class of 130 Maximum Distance Separable codes that are optimal in terms of erasure 131 correction capability. In others words, it enables a receiver to 132 recover the k source symbols from any set of exactly k encoding 133 symbols. Even if the encoding/decoding complexity is larger than 134 that of [RFC5053] or [draft-ietf-rmt-bb-fec-ldpc], this family of 135 codes is very useful. 137 Many applications dealing with content transmission or content 138 storage already rely on packet-based Reed-Solomon codes. In 139 particular, many of them use the Reed-Solomon codec of Luigi Rizzo 140 [RS-codec] [Rizzo97]. The goal of the present document is to specify 141 an implementation of Reed-Solomon codes that is compatible with this 142 codec. 144 The present document: 146 o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 2 147 that specifies the use of Reed-Solomon codes over GF(2^^m), with m 148 in {2..16}, 150 o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 5 151 that focuses on the special case of Reed-Solomon codes over 152 GF(2^^8) and no encoding symbol group (i.e., exactly one symbol 153 per packet), and 155 o in the context of the Under-Specified Small Block Systematic FEC 156 Scheme (FEC Encoding ID 129) 157 [draft-ietf-rmt-bb-fec-basic-schemes-revised], assigns the FEC 158 Instance ID 0 to the special case of Reed-Solomon codes over 159 GF(2^^8) and no encoding symbol group. 161 For a definition of the terms Fully-Specified and Under-Specified FEC 162 Schemes, see [RFC5052], section 4. 164 2. Terminology 166 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 167 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 168 document are to be interpreted as described in RFC 2119 [RFC2119]. 170 3. Definitions Notations and Abbreviations 172 3.1. Definitions 174 This document uses the same terms and definitions as those specified 175 in [RFC5052]. Additionally, it uses the following definitions: 177 Source symbol: unit of data used during the encoding process. 179 Encoding symbol: unit of data generated by the encoding process. 181 Repair symbol: encoding symbol that is not a source symbol. 183 Code rate: the k/n ratio, i.e., the ratio between the number of 184 source symbols and the number of encoding symbols. The code rate 185 belongs to a ]0; 1] interval. A code rate close to 1 indicates 186 that a small number of repair symbols have been produced during 187 the encoding process. 189 Systematic code: FEC code in which the source symbols are part of 190 the encoding symbols. 192 Source block: a block of k source symbols that are considered 193 together for the encoding. 195 Encoding Symbol Group: a group of encoding symbols that are sent 196 together within the same packet, and whose relationships to the 197 source block can be derived from a single Encoding Symbol ID. 199 Source Packet: a data packet containing only source symbols. 201 Repair Packet: a data packet containing only repair symbols. 203 Packet Erasure Channel: a communication path where packets are 204 either dropped (e.g., by a congested router, or because the number 205 of transmission errors exceeds the correction capabilities of the 206 physical layer codes) or received. When a packet is received, it 207 is assumed that this packet is not corrupted. 209 3.2. Notations 211 This document uses the following notations: 213 L denotes the object transfer length in bytes. 215 k denotes the number of source symbols in a source block. 217 n_r denotes the number of repair symbols generated for a source 218 block. 220 n denotes the encoding block length, i.e., the number of encoding 221 symbols generated for a source block. Therefore: n = k + n_r. 223 max_n denotes the maximum number of encoding symbols generated for 224 any source block. 226 B denotes the maximum source block length in symbols, i.e., the 227 maximum number of source symbols per source block. 229 N denotes the number of source blocks into which the object shall 230 be partitioned. 232 E denotes the encoding symbol length in bytes. 234 S denotes the symbol size in units of m-bit elements. When m = 8, 235 then S and E are equal. 237 m defines the length of the elements in the finite field, in bits. 238 In this document, m belongs to {2..16}. 240 q defines the number of elements in the finite field. We have: q 241 = 2^^m in this specification. 243 G denotes the number of encoding symbols per group, i.e., the 244 number of symbols sent in the same packet. 246 GM denotes the Generator Matrix of a Reed-Solomon code. 248 CR denotes the "code rate", i.e., the k/n ratio. 250 a^^b denotes a raised to the power b. 252 a^^-1 denotes the inverse of a. 254 I_k denotes the k*k identity matrix. 256 3.3. Abbreviations 258 This document uses the following abbreviations: 260 ESI stands for Encoding Symbol ID. 262 FEC OTI stands for FEC Object Transmission Information. 264 RS stands for Reed-Solomon. 266 MDS stands for Maximum Distance Separable code. 268 GF(q) denotes a finite field (also known as Galois Field) with q 269 elements. We assume that q = 2^^m in this document. 271 4. Formats and Codes with FEC Encoding ID 2 273 This section introduces the formats and codes associated with the 274 Fully-Specified FEC Scheme with FEC Encoding ID 2 that specifies the 275 use of Reed-Solomon codes over GF(2^^m). 277 4.1. FEC Payload ID 279 The FEC Payload ID is composed of the Source Block Number and the 280 Encoding Symbol ID. The length of these two fields depends on the 281 parameter m (which is transmitted in the FEC OTI) as follows: 283 o The Source Block Number (field of size 32-m bits) identifies from 284 which source block of the object the encoding symbol(s) in the 285 payload is(are) generated. There is a maximum of 2^^(32-m) blocks 286 per object. 288 o The Encoding Symbol ID (field of size m bits) identifies which 289 specific encoding symbol(s) generated from the source block 290 is(are) carried in the packet payload. There is a maximum of 2^^m 291 encoding symbols per block. The first k values (0 to k - 1) 292 identify source symbols, the remaining n-k values identify repair 293 symbols. 295 There MUST be exactly one FEC Payload ID per source or repair packet. 296 In case of an Encoding Symbol Group, when multiple encoding symbols 297 are sent in the same packet, the FEC Payload ID refers to the first 298 symbol of the packet. The other symbols can be deduced from the ESI 299 of the first symbol by incrementing sequentially the ESI. 301 0 1 2 3 302 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 303 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 304 | Source Block Number (32-8=24 bits) | Enc. Symb. ID | 305 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 307 Figure 1: FEC Payload ID encoding format for m = 8 (default) 309 0 1 2 3 310 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 311 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 312 | Src Block Nb (32-16=16 bits) | Enc. Symbol ID (m=16 bits) | 313 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 315 Figure 2: FEC Payload ID encoding format for m = 16 317 The format of the FEC Payload ID for m = 8 and m = 16 is illustrated 318 in Figure 1 and Figure 2 respectively. 320 4.2. FEC Object Transmission Information 322 4.2.1. Mandatory Elements 324 o FEC Encoding ID: the Fully-Specified FEC Scheme described in this 325 section uses FEC Encoding ID 2. 327 4.2.2. Common Elements 329 The following elements MUST be defined with the present FEC scheme: 331 o Transfer-Length (L): a non-negative integer indicating the length 332 of the object in bytes. There are some restrictions on the 333 maximum Transfer-Length that can be supported: 335 max_transfer_length = 2^^(32-m) * B * E 337 For instance, for m = 8, for B = 2^^8 - 1 (because the codec 338 operates on a finite field with 2^^8 elements) and if E = 1024 339 bytes, then the maximum transfer length is approximately equal to 340 2^^42 bytes (i.e., 4 Tera Bytes). Similarly, for m = 16, for B = 341 2^^16 - 1 and if E = 1024 bytes, then the maximum transfer length 342 is also approximately equal to 2^^42 bytes. For larger objects, 343 another FEC scheme, with a larger Source Block Number field in the 344 FEC Payload ID, could be defined. Another solution consists in 345 fragmenting large objects into smaller objects, each of them 346 complying with the above limits. 348 o Encoding-Symbol-Length (E): a non-negative integer indicating the 349 length of each encoding symbol in bytes. 351 o Maximum-Source-Block-Length (B): a non-negative integer indicating 352 the maximum number of source symbols in a source block. 354 o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer 355 indicating the maximum number of encoding symbols generated for 356 any source block. 358 Section 6 explains how to derive the values of each of these 359 elements. 361 4.2.3. Scheme-Specific Elements 363 The following element MUST be defined with the present FEC Scheme. 364 It contains two distinct pieces of information: 366 o G: a non-negative integer indicating the number of encoding 367 symbols per group used for the object. The default value is 1, 368 meaning that each packet contains exactly one symbol. When no G 369 parameter is communicated to the decoder, then this latter MUST 370 assume that G = 1. 372 o m: The m parameter is the length of the finite field elements, in 373 bits. It also characterizes the number of elements in the finite 374 field: q = 2^^m elements. The default value is m = 8. When no 375 finite field size parameter is communicated to the decoder, then 376 this latter MUST assume that m = 8. 378 4.2.4. Encoding Format 380 This section shows the two possible encoding formats of the above FEC 381 OTI. The present document does not specify when one encoding format 382 or the other should be used. 384 4.2.4.1. Using the General EXT_FTI Format 386 The FEC OTI binary format is the following, when the EXT_FTI 387 mechanism is used (e.g., within the ALC 388 [draft-ietf-rmt-pi-alc-revised] or NORM 389 [draft-ietf-rmt-pi-norm-revised] protocols). 391 0 1 2 3 392 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 393 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 394 | HET = 64 | HEL = 4 | | 395 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 396 | Transfer-Length (L) | 397 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 398 | m | G | Encoding Symbol Length (E) | 399 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 400 | Max Source Block Length (B) | Max Nb Enc. Symbols (max_n) | 401 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 403 Figure 3: EXT_FTI Header Format 405 4.2.4.2. Using the FDT Instance (FLUTE specific) 407 When it is desired that the FEC OTI be carried in the FDT (File 408 Delivery Table) Instance of a FLUTE session 409 [draft-ietf-rmt-flute-revised], the following XML attributes must be 410 described for the associated object: 412 o FEC-OTI-FEC-Encoding-ID 413 o FEC-OTI-Transfer-Length (L) 415 o FEC-OTI-Encoding-Symbol-Length (E) 417 o FEC-OTI-Maximum-Source-Block-Length (B) 419 o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) 421 o FEC-OTI-Scheme-Specific-Info 423 The FEC-OTI-Scheme-Specific-Info contains the string resulting from 424 the Base64 encoding (in the XML Schema xs:base64Binary sense) of the 425 following value: 427 0 1 428 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 429 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 430 | m | G | 431 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 433 Figure 4: FEC OTI Scheme Specific Information to be included in the 434 FDT Instance 436 When no m parameter is to be carried in the FEC OTI, the m field is 437 set to 0 (which is not a valid seed value). Otherwise the m field 438 contains a valid value as explained in Section 4.2.3. Similarly, 439 when no G parameter is to be carried in the FEC OTI, the G field is 440 set to 0 (which is not a valid seed value). Otherwise the G field 441 contains a valid value as explained in Section 4.2.3. When neither m 442 nor G are to be carried in the FEC OTI, then the sender simply omits 443 the FEC-OTI-Scheme-Specific-Info attribute. 445 During Base64 encoding, the 2 bytes of the FEC OTI Scheme Specific 446 Information are transformed into a string of 4 printable characters 447 (in the 64-character alphabet) that is added to the FEC-OTI-Scheme- 448 Specific-Info attribute. 450 5. Formats and Codes with FEC Encoding ID 5 452 This section introduces the formats and codes associated with the 453 Fully-Specified FEC Scheme with FEC Encoding ID 5 that focuses on the 454 special case of Reed-Solomon codes over GF(2^^8) and no encoding 455 symbol group. 457 5.1. FEC Payload ID 459 The FEC Payload ID is composed of the Source Block Number and the 460 Encoding Symbol ID: 462 o The Source Block Number (24 bit field) identifies from which 463 source block of the object the encoding symbol in the payload is 464 generated. There is a maximum of 2^^24 blocks per object. 466 o The Encoding Symbol ID (8 bit field) identifies which specific 467 encoding symbol generated from the source block is carried in the 468 packet payload. There is a maximum of 2^^8 encoding symbols per 469 block. The first k values (0 to k - 1) identify source symbols, 470 the remaining n-k values identify repair symbols. 472 There MUST be exactly one FEC Payload ID per source or repair packet. 473 This FEC Payload ID refers to the one and only symbol of the packet. 475 0 1 2 3 476 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 477 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 478 | Source Block Number (24 bits) | Enc. Symb. ID | 479 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 481 Figure 5: FEC Payload ID encoding format with FEC Encoding ID 5 483 5.2. FEC Object Transmission Information 485 5.2.1. Mandatory Elements 487 o FEC Encoding ID: the Fully-Specified FEC Scheme described in this 488 section uses FEC Encoding ID 5. 490 5.2.2. Common Elements 492 The Common Elements are the same as those specified in Section 4.2.2 493 when m = 8 and G = 1. 495 5.2.3. Scheme-Specific Elements 497 No Scheme-Specific elements are defined by this FEC Scheme. 499 5.2.4. Encoding Format 501 This section shows the two possible encoding formats of the above FEC 502 OTI. The present document does not specify when one encoding format 503 or the other should be used. 505 5.2.4.1. Using the General EXT_FTI Format 507 The FEC OTI binary format is the following, when the EXT_FTI 508 mechanism is used (e.g., within the ALC 509 [draft-ietf-rmt-pi-alc-revised] or NORM 510 [draft-ietf-rmt-pi-norm-revised] protocols). 512 0 1 2 3 513 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 514 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 515 | HET = 64 | HEL = 3 | | 516 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 517 | Transfer-Length (L) | 518 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 519 | Encoding Symbol Length (E) | MaxBlkLen (B) | max_n | 520 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 522 Figure 6: EXT_FTI Header Format with FEC Encoding ID 5 524 5.2.4.2. Using the FDT Instance (FLUTE specific) 526 When it is desired that the FEC OTI be carried in the FDT Instance of 527 a FLUTE session [draft-ietf-rmt-flute-revised], the following XML 528 attributes must be described for the associated object: 530 o FEC-OTI-FEC-Encoding-ID 532 o FEC-OTI-Transfer-Length (L) 534 o FEC-OTI-Encoding-Symbol-Length (E) 536 o FEC-OTI-Maximum-Source-Block-Length (B) 538 o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) 540 6. Procedures with FEC Encoding IDs 2 and 5 542 This section defines procedures that are common to FEC Encoding IDs 2 543 and 5. In case of FEC Encoding ID 5, m = 8 and G = 1. The block 544 partitioning algorithm that is defined in section 9.1 of [RFC5052] 545 MUST be used with FEC Encoding IDs 2 and 5. 547 6.1. Determining the Maximum Source Block Length (B) 549 The finite field size parameter, m, defines the number of non zero 550 elements in this field which is equal to: q - 1 = 2^^m - 1. Note 551 that q - 1 is also the theoretical maximum number of encoding symbols 552 that can be produced for a source block. For instance, when m = 8 553 (default) there is a maximum of 2^^8 - 1 = 255 encoding symbols. 555 Given the target FEC code rate (e.g., provided by the user when 556 starting a FLUTE sending application), the sender calculates: 558 max1_B = floor((2^^m - 1) * CR) 560 This max1_B value leaves enough room for the sender to produce the 561 desired number of parity symbols. 563 Additionally, a codec MAY impose other limitations on the maximum 564 block size. Yet it is not expected that such limits exist when using 565 the default m = 8 value. This decision MUST be clarified at 566 implementation time, when the target use case is known. This results 567 in a max2_B limitation. 569 Then, B is given by: 571 B = min(max1_B, max2_B) 573 Note that this calculation is only required at the coder, since the B 574 parameter is communicated to the decoder through the FEC OTI. 576 6.2. Determining the Number of Encoding Symbols of a Block 578 The following algorithm, also called "n-algorithm", explains how to 579 determine the maximum number of encoding symbols generated for any 580 source block (max_n) and the number of encoding symbols for a given 581 block (n) as a function of the target code rate. 583 AT A SENDER: 585 Input: 587 B: Maximum source block length, for any source block. Section 6.1 588 explains how to determine its value. 590 k: Current source block length. This parameter is given by the 591 block partitioning algorithm. 593 CR: FEC code rate, which is given by the user (e.g., when starting 594 a FLUTE sending application). It is expressed as a floating point 595 value. 597 Output: 599 max_n: Maximum number of encoding symbols generated for any source 600 block. 602 n: Number of encoding symbols generated for this source block. 604 Algorithm: 606 max_n = ceil(B / CR); 608 if (max_n > 2^^m - 1) then return an error ("invalid code rate"); 610 n = floor(k * max_n / B); 612 AT A RECEIVER: 614 Input: 616 B: Extracted from the received FEC OTI. 618 max_n: Extracted from the received FEC OTI. 620 k: Given by the block partitioning algorithm. 622 Output: 624 n 626 Algorithm: 628 n = floor(k * max_n / B); 630 It is RECOMMENDED that the "n-algorithm" be used by a sender, but 631 other algorithms remain possible to determine max_n and/or n. 633 At a receiver, the max_n value is extracted from the received FEC 634 OTI. Since the Reed-Solomon decoder does not need to know the actual 635 n value, using the receiver part of the "n-algorithm" is not 636 necessary from a decoding point of view. 638 However a receiver may want to have an estimate of n for other 639 reasons (e.g., for memory management purposes). In that case, a 640 receiver knows that the number of encoding symbols of a block cannot 641 exceed max_n. Additionally, if a receiver believes that a sender 642 uses the "n-algorithm", this receiver MAY use the receiver part of 643 the "n-algorithm" to get a better estimate of n. When this is the 644 case, a receiver MUST be prepared to handle symbols with an Encoding 645 Symbol ID superior or equal to the computed n value (e.g., it can 646 choose to simply drop them). 648 7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) and Reed- 649 Solomon Codes over GF(2^^8) 651 In the context of the Under-Specified Small Block Systematic FEC 652 Scheme (FEC Encoding ID 129) 653 [draft-ietf-rmt-bb-fec-basic-schemes-revised], this document assigns 654 the FEC Instance ID 0 to the special case of Reed-Solomon codes over 655 GF(2^^8) and no encoding symbol group. 657 The FEC Instance ID 0 uses the Formats and Codes specified in 658 [draft-ietf-rmt-bb-fec-basic-schemes-revised]. 660 The FEC Scheme with FEC Instance ID 0 MAY use the block partitioning 661 algorithm defined in Section 9.1. of [RFC5052] to partition the 662 object into source blocks. This FEC Scheme MAY also use another 663 algorithm. For instance the CDP sender may change the length of each 664 source block dynamically, depending on some external criteria (e.g., 665 to adjust the FEC coding rate to the current loss rate experienced by 666 NORM receivers) and inform the CDP receivers of the current block 667 length by means of the EXT_FTI mechanism. This choice is out of the 668 scope of the current document. 670 8. Reed-Solomon Codes Specification for the Erasure Channel 672 Reed-Solomon (RS) codes are linear block codes. They also belong to 673 the class of MDS codes. A [n,k]-RS code encodes a sequence of k 674 source elements defined over a finite field GF(q) into a sequence of 675 n encoding elements, where n is upper bounded by q - 1. The 676 implementation described in this document is based on a generator 677 matrix built from a Vandermonde matrix put into systematic form. 679 Section 8.1 to Section 8.3 specify the [n,k]-RS codes when applied to 680 m-bit elements, and Section 8.4 the use of [n,k]-RS codes when 681 applied to symbols composed of several m-bit elements, which is the 682 target of this specification. 684 A reader who wants to understand the underlying theory is invited to 685 refer to references [Rizzo97] and [MWS77]. 687 8.1. Finite Field 689 A finite field GF(q) is defined as a finite set of q elements which 690 has a structure of field. It contains necessarily q = p^^m elements, 691 where p is a prime number. With packet erasure channels, p is always 692 set to 2. The elements of the field GF(2^^m) can be represented by 693 polynomials with binary coefficients (i.e., over GF(2)) of degree 694 lower or equal to m-1. The polynomials can be associated with binary 695 vectors of length m. For example, the vector (11001) represents the 696 polynomial 1 + x + x^^4. This representation is often called 697 polynomial representation. The addition between two elements is 698 defined as the addition of binary polynomials in GF(2) and the 699 multiplication is the multiplication modulo a given irreducible 700 polynomial over GF(2) of degree m. Note that all the roots of this 701 polynomial are in GF(2^^m) but not in GF(2). 703 The chosen polynomial representation of the finite field GF(2^^m) is 704 completely characterized by the irreducible polynomial. The 705 following polynomials are chosen to represent the field GF(2^^m), for 706 m varying from 2 to 16: 708 m = 2, "111" (1+x+x^^2) 710 m = 3, "1101", (1+x+x^^3) 712 m = 4, "11001", (1+x+x^^4) 714 m = 5, "101001", (1+x^^2+x^^5) 716 m = 6, "1100001", (1+x+x^^6) 717 m = 7, "10010001", (1+x^^3+x^^7) 719 m = 8, "101110001", (1+x^^2+x^^3+x^^4+x^^8) 721 m = 9, "1000100001", (1+x^^4+x^^9) 723 m = 10, "10010000001", (1+x^^3+x^^10) 725 m = 11, "101000000001", (1+x^^2+x^^11) 727 m = 12, "1100101000001", (1+x+x^^4+x^^6+x^^12) 729 m = 13, "11011000000001", (1+x+x^^3+x^^4+x^^13) 731 m = 14, "110000100010001", (1+x+x^^6+x^^10+x^^14) 733 m = 15, "1100000000000001", (1+x+x^^15) 735 m = 16, "11010000000010001", (1+x+x^^3+x^^12+x^^16) 737 In order to facilitate the implementation, these polynomials are also 738 primitive. This means that any element of GF(2^^m) can be expressed 739 as a power of a given root of this polynomial. These polynomials are 740 also chosen so that they contain the minimum number of monomials. 742 8.2. Reed-Solomon Encoding Algorithm 744 8.2.1. Encoding Principles 746 Let s = (s_0, ..., s_{k-1}) be a source vector of k elements over 747 GF(2^^m). Let e = (e_0, ..., e_{n-1}) be the corresponding encoding 748 vector of n elements over GF(2^^m). Being a linear code, encoding is 749 performed by multiplying the source vector by a generator matrix, GM, 750 of k rows and n columns over GF(2^^m). Thus: 752 e = s * GM. 754 The definition of the generator matrix completely characterizes the 755 RS code. 757 Let us consider that: n = 2^^m - 1 and: 0 < k <= n. Let us denote by 758 alpha the root of the primitive polynomial of degree m chosen in the 759 list of Section 8.1 for the corresponding value of m. Let us 760 consider a Vandermonde matrix of k rows and n columns, denoted by 761 V_{k,n}, and built as follows: the {i, j} entry of V_{k,n} is v_{i,j} 762 = alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This 763 matrix generates a MDS code. However, this MDS code is not 764 systematic, which is a problem for many networking applications. To 765 obtain a systematic matrix (and code), the simplest solution consists 766 in considering the matrix V_{k,k} formed by the first k columns of 767 V_{k,n}, then to invert it and to multiply this inverse by V_{k,n}. 768 Clearly, the product V_{k,k}^^-1 * V_{k,n} contains the identity 769 matrix I_k on its first k columns, meaning that the first k encoding 770 elements are equal to source elements. Besides the associated code 771 keeps the MDS property. 773 Therefore, the generator matrix of the code considered in this 774 document is: 776 GM = (V_{k,k}^^-1) * V_{k,n} 778 Note that, in practice, the [n,k]-RS code can be shortened to a 779 [n',k]-RS code, where k <= n' < n, by considering the sub-matrix 780 formed by the n' first columns of GM. 782 8.2.2. Encoding Complexity 784 Encoding can be performed by first pre-computing GM and by 785 multiplying the source vector (k elements) by GM (k rows and n 786 columns). The complexity of the pre-computation of the generator 787 matrix can be estimated as the complexity of the multiplication of 788 the inverse of a Vandermonde matrix by n-k vectors (i.e., the last 789 n-k columns of V_{k,n}). Since the complexity of the inverse of a 790 k*k-Vandermonde matrix by a vector is O(k * (log(k))^^2), the 791 generator matrix can be computed in 0((n-k)* k * (log(k))^^2)) 792 operations. When the generator matrix is pre-computed, the encoding 793 needs k operations per repair element (vector-matrix multiplication). 795 Encoding can also be performed by first computing the product s * 796 V_{k,k}^^-1 and then by multiplying the result with V_{k,n}. The 797 multiplication by the inverse of a square Vandermonde matrix is known 798 as the interpolation problem and its complexity is O(k * 799 (log(k))^^2). The multiplication by a Vandermonde matrix, known as 800 the multipoint evaluation problem, requires O((n-k) * log(k)) by 801 using Fast Fourier Transform, as explained in [GO94]. The total 802 complexity of this encoding algorithm is then O((k/(n-k)) * 803 (log(k))^^2 + log(k)) operations per repair element. 805 8.3. Reed-Solomon Decoding Algorithm 807 8.3.1. Decoding Principles 809 The Reed-Solomon decoding algorithm for the erasure channel allows 810 the recovery of the k source elements from any set of k received 811 elements. It is based on the fundamental property of the generator 812 matrix which is such that any k*k-submatrix is invertible (see 814 [MWS77]). The first step of the decoding consists in extracting the 815 k*k submatrix of the generator matrix obtained by considering the 816 columns corresponding to the received elements. Indeed, since any 817 encoding element is obtained by multiplying the source vector by one 818 column of the generator matrix, the received vector of k encoding 819 elements can be considered as the result of the multiplication of the 820 source vector by a k*k submatrix of the generator matrix. Since this 821 submatrix is invertible, the second step of the algorithm is to 822 invert this matrix and to multiply the received vector by the 823 obtained matrix to recover the source vector. 825 8.3.2. Decoding Complexity 827 The decoding algorithm described previously includes the matrix 828 inversion and the vector-matrix multiplication. With the classical 829 Gauss-Jordan algorithm, the matrix inversion requires O(k^^3) 830 operations and the vector-matrix multiplication is performed in 831 O(k^^2) operations. 833 This complexity can be improved by considering that the received 834 submatrix of GM is the product between the inverse of a Vandermonde 835 matrix (V_(k,k)^^-1) and another Vandermonde matrix (denoted by V' 836 which is a submatrix of V_(k,n)). The decoding can be done by 837 multiplying the received vector by V'^^-1 (interpolation problem with 838 complexity O( k * (log(k))^^2) ) then by V_{k,k} (multipoint 839 evaluation with complexity O(k * log(k))). The global decoding 840 complexity is then O((log(k))^^2) operations per source element. 842 8.4. Implementation for the Packet Erasure Channel 844 In a packet erasure channel, each packet (and symbol(s) since packets 845 contain G >= 1 symbols) is either correctly received or erased. The 846 location of the erased symbols in the sequence of symbols MUST be 847 known. The following specification describes the use of Reed-Solomon 848 codes for generating redundant symbols from the k source symbols and 849 for recovering the source symbols from any set of k received symbols. 851 The k source symbols of a source block are assumed to be composed of 852 S m-bit elements. Each m-bit element corresponds to an element of 853 the finite field GF(2^^m) through the polynomial representation 854 (Section 8.1). If some of the source symbols contain less than S 855 elements, they MUST be virtually padded with zero elements (this can 856 be the case for the last symbol of the last block of the object). 857 However, this padding does not need to be actually sent with the data 858 to the receivers. 860 The encoding process produces n encoding symbols of size S m-bit 861 elements, of which k are source symbols (this is a systematic code) 862 and n-k are repair symbols (Figure 7). The m-bit elements of the 863 repair symbols are calculated using the corresponding m-bit elements 864 of the source symbol set. A logical u-th source vector, comprised of 865 the u-th elements from the set of source symbols, is used to 866 calculate a u-th encoding vector. This u-th encoding vector then 867 provides the u-th elements for the set encoding symbols calculated 868 for the block. As a systematic code, the first k encoding symbols 869 are the same as the k source symbols and the last n-k repair symbols 870 are the result of the Reed-Solomon encoding. 872 Input: k source symbols 874 0 u S-1 875 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 876 | |X| | source symbol 0 877 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 878 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 879 | |X| | source symbol 1 880 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 881 . . . 882 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 883 | |X| | source symbol k-1 884 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 886 * 888 +--------------------+ 889 | generator matrix | 890 | GM | 891 | (k x n) | 892 +--------------------+ 894 | 895 V 897 Output: n encoding symbols (source + repair) 899 0 u S-1 900 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 901 | |X| | enc. symbol 0 902 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 903 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 904 | |X| | enc. symbol 1 905 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 906 . . . 907 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 908 | |Y| | enc. symbol n-1 909 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 911 Figure 7: Packet encoding scheme 913 An asset of this scheme is that the loss of some encoding symbols 914 produces the same erasure pattern for each of the S encoding vectors. 915 It follows that the matrix inversion must be done only once and will 916 be used by all the S encoding vectors. For large S, this matrix 917 inversion cost becomes negligible in front of the S matrix-vector 918 multiplications. 920 Another asset is that the n-k repair symbols can be produced on 921 demand. For instance, a sender can start by producing a limited 922 number of repair symbols and later on, depending on the observed 923 erasures on the channel, decide to produce additional repair symbols, 924 up to the n-k upper limit. Indeed, to produce the repair symbol e_j, 925 where k <= j < n, it is sufficient to multiply the S source vectors 926 with column j of GM. 928 9. Security Considerations 930 9.1. Problem Statement 932 A content delivery system is potentially subject to many attacks: 933 some of them target the network (e.g., to compromise the routing 934 infrastructure, by compromising the congestion control component), 935 others target the Content Delivery Protocol (CDP) (e.g., to 936 compromise its normal behavior), and finally some attacks target the 937 content itself. Since this document focuses on a FEC building block 938 independently of any particular CDP (even if ALC and NORM are two 939 natural candidates), this section only discusses the additional 940 threats that an arbitrary CDP may be exposed to when using this 941 building block. 943 More specifically, several kinds of attacks exist: 945 o those that are meant to give access to a confidential content 946 (e.g., in case of a non-free content), 948 o those that try to corrupt the object being transmitted (e.g., to 949 inject malicious code within an object, or to prevent a receiver 950 from using an object), 952 o and those that try to compromise the receiver's behavior (e.g., by 953 making the decoding of an object computationally expensive). 955 These attacks can be launched either against the data flow itself 956 (e.g. by sending forged symbols) or against the FEC parameters that 957 are sent either in-band (e.g., in an EXT_FTI or FDT Instance) or out- 958 of-band (e.g., in a session description). 960 9.2. Attacks Against the Data Flow 962 First of all, let us consider the attacks against the data flow. 964 9.2.1. Access to Confidential Objects 966 Access control to the object being transmitted is typically provided 967 by means of encryption. This encryption can be done over the whole 968 object (e.g., by the content provider, before the FEC encoding 969 process), or be done on a packet per packet basis (e.g., when IPSec/ 970 ESP is used [RFC4303]). If access control is a concern, it is 971 RECOMMENDED that one of these solutions be used. Even if we mention 972 these attacks here, they are not related nor facilitated by the use 973 of FEC. 975 9.2.2. Content Corruption 977 Protection against corruptions (e.g., after sending forged packets) 978 is achieved by means of a content integrity verification/sender 979 authentication scheme. This service can be provided at the object 980 level, but in that case a receiver has no way to identify which 981 symbol(s) is(are) corrupted if the object is detected as corrupted. 982 This service can also be provided at the packet level. In this case, 983 after removing all forged packets, the object may be in some case 984 recovered. Several techniques can provide this source 985 authentication/content integrity service: 987 o at the object level, the object MAY be digitally signed (with 988 public key cryptography), for instance by using RSASSA-PKCS1-v1_5 989 [RFC3447]. This signature enables a receiver to check the object 990 integrity, once this latter has been fully decoded. Even if 991 digital signatures are computationally expensive, this calculation 992 occurs only once per object, which is usually acceptable; 994 o at the packet level, each packet can be digitally signed. A major 995 limitation is the high computational and transmission overheads 996 that this solution requires (unless Elliptic Curve Cryptography 997 (ECC) is used, but ECC is the subject of proprietary patents). To 998 avoid this problem, the signature may span a set of symbols 999 (instead of a single one) in order to amortize the signature 1000 calculation. But if a single symbol is missing, the integrity of 1001 the whole set cannot be checked; 1003 o at the packet level, a Group Message Authentication Code (MAC) 1004 [RFC2104] scheme can be used, for instance by using HMAC-SHA-1 1005 with a secret key shared by all the group members, senders and 1006 receivers. This technique creates a cryptographically secured 1007 (thanks to the secret key) digest of a packet that is sent along 1008 with the packet. The Group MAC scheme does not create prohibitive 1009 processing load nor transmission overhead, but it has a major 1010 limitation: it only provides a group authentication/integrity 1011 service since all group members share the same secret group key, 1012 which means that each member can send a forged packet. It is 1013 therefore restricted to situations where group members are fully 1014 trusted (or in association with another technique as a pre-check); 1016 o at the packet level, TESLA [RFC4082] is a very attractive and 1017 efficient solution that is robust to losses, provides a true 1018 authentication/integrity service, and does not create any 1019 prohibitive processing load or transmission overhead. Yet 1020 checking a packet requires a small delay (a second or more) after 1021 its reception; 1023 Techniques relying on public key cryptography (digital signatures and 1024 TESLA during the bootstrap process, when used) require that public 1025 keys be securely associated to the entities. This can be achieved by 1026 a Public Key Infrastructure (PKI), or by a PGP Web of Trust, or by 1027 pre-distributing the public keys of each group member. 1029 Techniques relying on symmetric key cryptography (group MAC) require 1030 that a secret key be shared by all group members. This can be 1031 achieved by means of a group key management protocol, or simply by 1032 pre-distributing the secret key (but this manual solution has many 1033 limitations). 1035 It is up to the developer and deployer, who know the security 1036 requirements and features of the target application area, to define 1037 which solution is the most appropriate. Nonetheless, in case there 1038 is any concern of the threat of object corruption, it is RECOMMENDED 1039 that at least one of these techniques be used. 1041 9.3. Attacks Against the FEC Parameters 1043 Let us now consider attacks against the FEC parameters (or FEC OTI). 1044 The FEC OTI can either be sent in-band (i.e., in an EXT_FTI or in an 1045 FDT Instance containing FEC OTI for the object) or out-of-band (e.g., 1046 in a session description). Attacks on these FEC parameters can 1047 prevent the decoding of the associated object: for instance modifying 1048 the B parameter will lead to a different block partitioning at a 1049 receiver thereby compromising decoding; or setting the m parameter to 1050 16 instead of 8 with FEC Encoding ID 2 will increase the processing 1051 load while compromising decoding. 1053 It is therefore RECOMMENDED that security measures be taken to 1054 guarantee the FEC OTI integrity. To that purpose, the packets 1055 carrying the FEC parameters sent in-band in an EXT_FTI header 1056 extension SHOULD be protected by one of the per-packet techniques 1057 described above: digital signature, group MAC, or TESLA. When FEC 1058 OTI is contained in an FDT Instance, this object SHOULD be protected, 1059 for instance by digitally signing it with XML digital signatures 1060 [RFC3275]. Finally, when FEC OTI is sent out-of-band (e.g., in a 1061 session description) this latter SHOULD be protected, for instance by 1062 digitally signing it. 1064 The same considerations concerning the key management aspects apply 1065 here also. 1067 10. IANA Considerations 1069 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA 1070 registration. For general guidelines on IANA considerations as they 1071 apply to this document, see [RFC5052]. 1073 This document assigns the Fully-Specified FEC Encoding ID 2 under the 1074 "ietf:rmt:fec:encoding" name-space to "Reed-Solomon Codes over 1075 GF(2^^m)". 1077 This document assigns the Fully-Specified FEC Encoding ID 5 under the 1078 "ietf:rmt:fec:encoding" name-space to "Reed-Solomon Codes over 1079 GF(2^^8)". 1081 This document assigns the FEC Instance ID 0 scoped by the Under- 1082 Specified FEC Encoding ID 129 to "Reed-Solomon Codes over GF(2^^8)". 1083 More specifically, under the "ietf:rmt:fec:encoding:instance" sub- 1084 name-space that is scoped by the "ietf:rmt:fec:encoding" called 1085 "Small Block Systematic FEC Codes", this document assigns FEC 1086 Instance ID 0 to "Reed-Solomon Codes over GF(2^^8)". 1088 11. Acknowledgments 1090 The authors want to thank Brian Adamson, Igor Slepchin, Stephen Kent, 1091 Francis Dupont, Elwyn Davies, Magnus Westerlund and Alfred Hoenes for 1092 their valuable comments. The authors also want to thank Luigi Rizzo 1093 for his comments and for the design of the reference Reed-Solomon 1094 codec. 1096 12. References 1098 12.1. Normative References 1100 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1101 Requirement Levels", RFC 2119. 1103 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 1104 Correction (FEC) Building Block", RFC 5052, August 2007. 1106 [draft-ietf-rmt-bb-fec-basic-schemes-revised] 1107 Watson, M., "Basic Forward Error Correction (FEC) 1108 Schemes", 1109 draft-ietf-rmt-bb-fec-basic-schemes-revised-03.txt (work 1110 in progress), February 2007. 1112 12.2. Informative References 1114 [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, 1115 M., and J. Crowcroft, "The Use of Forward Error Correction 1116 (FEC) in Reliable Multicast", RFC 3453, December 2002. 1118 [RS-codec] 1119 Rizzo, L., "Reed-Solomon FEC codec (revised version of 1120 July 2nd, 1998), available at 1121 http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz and 1122 mirrored at http://planete-bcast.inrialpes.fr/", 1123 July 1998. 1125 [Rizzo97] Rizzo, L., "Effective Erasure Codes for Reliable Computer 1126 Communication Protocols", ACM SIGCOMM Computer 1127 Communication Review Vol.27, No.2, pp.24-36, April 1997. 1129 [MWS77] Mac Williams, F. and N. Sloane, "The Theory of Error 1130 Correcting Codes", North Holland, 1977. 1132 [GO94] Gohberg, I. and V. Olshevsky, "Fast algorithms with 1133 preprocessing for matrix-vector multiplication problems", 1134 Journal of Complexity, pp. 411-427, vol. 10, 1994. 1136 [draft-ietf-rmt-bb-fec-ldpc] 1137 Roca, V., Neumann, C., and D. Furodet, "Low Density Parity 1138 Check (LDPC) Forward Error Correction", 1139 draft-ietf-rmt-bb-fec-ldpc-07.txt (work in progress), 1140 November 2007. 1142 [RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, 1143 "Raptor Forward Error Correction Scheme", RFC 5053, 1144 June 2007. 1146 [draft-ietf-rmt-pi-alc-revised] 1147 Luby, M., Watson, M., and L. Vicisano, "Asynchronous 1148 Layered Coding (ALC) Protocol Instantiation", 1149 draft-ietf-rmt-pi-alc-revised-04.txt (work in progress), 1150 February 2007. 1152 [draft-ietf-rmt-pi-norm-revised] 1153 Adamson, B., Bormann, C., Handley, M., and J. Macker, 1154 "Negative-acknowledgment (NACK)-Oriented Reliable 1155 Multicast (NORM) Protocol", 1156 draft-ietf-rmt-pi-norm-revised-05.txt (work in progress), 1157 March 2007. 1159 [draft-ietf-rmt-flute-revised] 1160 Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, 1161 "FLUTE - File Delivery over Unidirectional Transport", 1162 draft-ietf-rmt-flute-revised-05.txt (work in progress), 1163 October 2007. 1165 [RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography 1166 Standards (PKCS) #1: RSA Cryptography Specifications 1167 Version 2.1", RFC 3447, February 2003. 1169 [RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)", 1170 RFC 4303, December 2005. 1172 [RFC2104] "HMAC: Keyed-Hashing for Message Authentication", 1173 RFC 2104, February 1997. 1175 [RFC4082] "Timed Efficient Stream Loss-Tolerant Authentication 1176 (TESLA): Multicast Source Authentication Transform 1177 Introduction", RFC 4082, June 2005. 1179 [RFC3275] Eastlake, D., Reagle, J., and D. Solo, "(Extensible Markup 1180 Language) XML-Signature Syntax and Processing", RFC 3275, 1181 March 2002. 1183 Authors' Addresses 1185 Jerome Lacan 1186 ISAE/LAAS-CNRS 1187 1, place Emile Blouin 1188 Toulouse 31056 1189 France 1191 Email: jerome.lacan@isae.fr 1192 URI: http://dmi.ensica.fr/auteur.php3?id_auteur=5 1194 Vincent Roca 1195 INRIA 1196 655, av. de l'Europe 1197 Inovallee; Montbonnot 1198 ST ISMIER cedex 38334 1199 France 1201 Email: vincent.roca@inria.fr 1202 URI: http://planete.inrialpes.fr/people/roca/ 1204 Jani Peltotalo 1205 Tampere University of Technology 1206 P.O. Box 553 (Korkeakoulunkatu 1) 1207 Tampere FIN-33101 1208 Finland 1210 Email: jani.peltotalo@tut.fi 1211 URI: http://atm.tut.fi/mad 1213 Sami Peltotalo 1214 Tampere University of Technology 1215 P.O. Box 553 (Korkeakoulunkatu 1) 1216 Tampere FIN-33101 1217 Finland 1219 Email: sami.peltotalo@tut.fi 1220 URI: http://atm.tut.fi/mad 1222 Full Copyright Statement 1224 Copyright (C) The IETF Trust (2007). 1226 This document is subject to the rights, licenses and restrictions 1227 contained in BCP 78, and except as set forth therein, the authors 1228 retain all their rights. 1230 This document and the information contained herein are provided on an 1231 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1232 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1233 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1234 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1235 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1236 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1238 Intellectual Property 1240 The IETF takes no position regarding the validity or scope of any 1241 Intellectual Property Rights or other rights that might be claimed to 1242 pertain to the implementation or use of the technology described in 1243 this document or the extent to which any license under such rights 1244 might or might not be available; nor does it represent that it has 1245 made any independent effort to identify any such rights. Information 1246 on the procedures with respect to rights in RFC documents can be 1247 found in BCP 78 and BCP 79. 1249 Copies of IPR disclosures made to the IETF Secretariat and any 1250 assurances of licenses to be made available, or the result of an 1251 attempt made to obtain a general license or permission for the use of 1252 such proprietary rights by implementers or users of this 1253 specification can be obtained from the IETF on-line IPR repository at 1254 http://www.ietf.org/ipr. 1256 The IETF invites any interested party to bring to its attention any 1257 copyrights, patents or patent applications, or other proprietary 1258 rights that may cover technology that may be required to implement 1259 this standard. Please address the information to the IETF at 1260 ietf-ipr@ietf.org. 1262 Acknowledgment 1264 Funding for the RFC Editor function is provided by the IETF 1265 Administrative Support Activity (IASA).