idnits 2.17.1 draft-ietf-rmt-bb-fec-rs-04.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 1164. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1175. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1182. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1188. 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 (October 10, 2007) is 6043 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) == Outdated reference: A later version (-06) exists of draft-ietf-rmt-bb-fec-basic-schemes-revised-03 == Outdated reference: A later version (-08) exists of draft-ietf-rmt-bb-fec-ldpc-06 == Outdated reference: A later version (-10) exists of draft-ietf-rmt-pi-alc-revised-04 == Outdated reference: A later version (-14) exists of draft-ietf-rmt-pi-norm-revised-05 == Outdated reference: A later version (-16) exists of draft-ietf-rmt-flute-revised-04 -- Obsolete informational reference (is this intentional?): RFC 3447 (ref. '13') (Obsoleted by RFC 8017) Summary: 1 error (**), 0 flaws (~~), 6 warnings (==), 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 4 Intended status: Standards Track V. Roca 5 Expires: April 12, 2008 INRIA 6 J. Peltotalo 7 S. Peltotalo 8 Tampere University of Technology 9 October 10, 2007 11 Reed-Solomon Forward Error Correction (FEC) Schemes 12 draft-ietf-rmt-bb-fec-rs-04.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 April 12, 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. 50 This document also describes a Fully-Specified FEC Scheme for the 51 special case of Reed-Solomon codes over GF(2^^8) when there is no 52 encoding symbol group. 54 Finally, in the context of the Under-Specified Small Block Systematic 55 FEC Scheme (FEC Encoding ID 129), this document assigns an FEC 56 Instance ID to the special case of Reed-Solomon codes over GF(2^^8). 58 Reed-Solomon codes belong to the class of Maximum Distance Separable 59 (MDS) codes, i.e., they enable a receiver to recover the k source 60 symbols from any set of k received symbols. The schemes described 61 here are compatible with the implementation from Luigi Rizzo. 63 Table of Contents 65 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 66 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 67 3. Definitions Notations and Abbreviations . . . . . . . . . . . 6 68 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 6 69 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 6 70 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 7 71 4. Formats and Codes with FEC Encoding ID 2 . . . . . . . . . . . 8 72 4.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 8 73 4.2. FEC Object Transmission Information . . . . . . . . . . . 9 74 4.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 9 75 4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 9 76 4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 9 77 4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 10 78 5. Formats and Codes with FEC Encoding ID 5 . . . . . . . . . . . 12 79 5.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 12 80 5.2. FEC Object Transmission Information . . . . . . . . . . . 12 81 5.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 12 82 5.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 12 83 5.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 13 84 5.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 13 85 6. Procedures with FEC Encoding IDs 2 and 5 . . . . . . . . . . . 14 86 6.1. Determining the Maximum Source Block Length (B) . . . . . 14 87 6.2. Determining the Number of Encoding Symbols of a Block . . 14 88 7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) 89 and Reed-Solomon Codes over GF(2^^8) . . . . . . . . . . . . . 16 90 8. Reed-Solomon Codes Specification for the Erasure Channel . . . 17 91 8.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 17 92 8.2. Reed-Solomon Encoding Algorithm . . . . . . . . . . . . . 18 93 8.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 18 94 8.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 19 95 8.3. Reed-Solomon Decoding Algorithm . . . . . . . . . . . . . 19 96 8.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 19 97 8.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 20 98 8.4. Implementation for the Packet Erasure Channel . . . . . . 20 99 9. Security Considerations . . . . . . . . . . . . . . . . . . . 23 100 9.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 23 101 9.2. Attacks Against the Data Flow . . . . . . . . . . . . . . 23 102 9.3. Attacks against the FEC parameters . . . . . . . . . . . . 25 103 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 104 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27 105 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28 106 12.1. Normative References . . . . . . . . . . . . . . . . . . . 28 107 12.2. Informative References . . . . . . . . . . . . . . . . . . 28 108 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 30 109 Intellectual Property and Copyright Statements . . . . . . . . . . 31 111 1. Introduction 113 The use of Forward Error Correction (FEC) codes is a classical 114 solution to improve the reliability of multicast and broadcast 115 transmissions. The [2] document describes a general framework to use 116 FEC in Content Delivery Protocols (CDP). The companion document [4] 117 describes some applications of FEC codes for content delivery. 119 Recent FEC schemes like [9] and [8] proposed erasure codes based on 120 sparse graphs/matrices. These codes are efficient in terms of 121 processing but not optimal in terms of correction capabilities when 122 dealing with "small" objects. 124 The FEC scheme described in this document belongs to the class of 125 Maximum Distance Separable codes that are optimal in terms of erasure 126 correction capability. In others words, it enables a receiver to 127 recover the k source symbols from any set of exactly k encoding 128 symbols. Even if the encoding/decoding complexity is larger than 129 that of [9] or [8], this family of codes is very useful. 131 Many applications dealing with content transmission or content 132 storage already rely on packet-based Reed-Solomon codes. In 133 particular, many of them use the Reed-Solomon codec of Luigi Rizzo 134 [5]. The goal of the present document to specify an implementation 135 of Reed-Solomon codes that is compatible with this codec. 137 The present document: 139 o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 2 140 that specifies the use of Reed-Solomon codes over GF(2^^m), with m 141 in {2..16}, 143 o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 5 144 that focuses on the special case of Reed-Solomon codes over 145 GF(2^^8) and no encoding symbol group (i.e., exactly one symbol 146 per packet), and 148 o in the context of the Under-Specified Small Block Systematic FEC 149 Scheme (FEC Encoding ID 129) [3], assigns the FEC Instance ID 0 to 150 the special case of Reed-Solomon codes over GF(2^^8) and no 151 encoding symbol group. 153 2. Terminology 155 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 156 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 157 document are to be interpreted as described in RFC 2119 [1]. 159 3. Definitions Notations and Abbreviations 161 3.1. Definitions 163 This document uses the same terms and definitions as those specified 164 in [2]. Additionally, it uses the following definitions: 166 Source symbol: unit of data used during the encoding process. 168 Encoding symbol: unit of data generated by the encoding process. 170 Repair symbol: encoding symbol that is not a source symbol. 172 Systematic code: FEC code in which the source symbols are part of 173 the encoding symbols. 175 Source block: a block of k source symbols that are considered 176 together for the encoding. 178 Encoding Symbol Group: a group of encoding symbols that are sent 179 together within the same packet, and whose relationships to the 180 source block can be derived from a single Encoding Symbol ID. 182 Source Packet: a data packet containing only source symbols. 184 Repair Packet: a data packet containing only repair symbols. 186 3.2. Notations 188 This document uses the following notations: 190 L denotes the object transfer length in bytes. 192 k denotes the number of source symbols in a source block. 194 n_r denotes the number of repair symbols generated for a source 195 block. 197 n denotes the encoding block length, i.e., the number of encoding 198 symbols generated for a source block. Therefore: n = k + n_r. 200 max_n denotes the maximum number of encoding symbols generated for 201 any source block. 203 B denotes the maximum source block length in symbols, i.e., the 204 maximum number of source symbols per source block. 206 N denotes the number of source blocks into which the object shall 207 be partitioned. 209 E denotes the encoding symbol length in bytes. 211 S denotes the symbol size in units of m-bit elements. When m = 8, 212 then S and E are equal. 214 m defines the length of the elements in the finite field, in bits. 215 In this document, m belongs to {2..16}. 217 q defines the number of elements in the finite field. We have: q 218 = 2^^m in this specification. 220 G denotes the number of encoding symbols per group, i.e. the 221 number of symbols sent in the same packet. 223 GM denotes the Generator Matrix of a Reed-Solomon code. 225 rate denotes the "code rate", i.e., the k/n ratio. 227 a^^b denotes a raised to the power b. 229 a^^-1 denotes the inverse of a. 231 I_k denotes the k*k identity matrix. 233 3.3. Abbreviations 235 This document uses the following abbreviations: 237 ESI stands for Encoding Symbol ID. 239 FEC OTI stands for FEC Object Transmission Information. 241 RS stands for Reed-Solomon. 243 MDS stands for Maximum Distance Separable code. 245 GF(q) denotes a finite field (also known as Galois Field) with q 246 elements. We assume that q = 2^^m in this document. 248 4. Formats and Codes with FEC Encoding ID 2 250 This section introduces the formats and codes associated to the 251 Fully-Specified FEC Scheme with FEC Encoding ID 2 that specifies the 252 use of Reed-Solomon codes over GF(2^^m). 254 4.1. FEC Payload ID 256 The FEC Payload ID is composed of the Source Block Number and the 257 Encoding Symbol ID. The length of these two fields depends on the 258 parameter m (which is transmitted in the FEC OTI) as follows: 260 o The Source Block Number (field of size 32-m bits) identifies from 261 which source block of the object the encoding symbol(s) in the 262 payload is(are) generated. There is a maximum of 2^^(32-m) blocks 263 per object. 265 o The Encoding Symbol ID (field of size m bits) identifies which 266 specific encoding symbol(s) generated from the source block 267 is(are) carried in the packet payload. There is a maximum of 2^^m 268 encoding symbols per block. The first k values (0 to k - 1) 269 identify source symbols, the remaining n-k values identify repair 270 symbols. 272 There MUST be exactly one FEC Payload ID per source or repair packet. 273 In case of an Encoding Symbol Group, when multiple encoding symbols 274 are sent in the same packet, the FEC Payload ID refers to the first 275 symbol of the packet. The other symbols can be deduced from the ESI 276 of the first symbol by incrementing sequentially the ESI. 278 0 1 2 3 279 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 280 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 281 | Source Block Number (32-8=24 bits) | Enc. Symb. ID | 282 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 284 Figure 1: FEC Payload ID encoding format for m = 8 (default) 286 0 1 2 3 287 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 288 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 289 | Src Block Nb (32-16=16 bits) | Enc. Symbol ID (m=16 bits) | 290 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 292 Figure 2: FEC Payload ID encoding format for m = 16 294 The format of the FEC Payload ID for m = 8 and m = 16 is illustrated 295 in Figure 1 and Figure 2 respectively. 297 4.2. FEC Object Transmission Information 299 4.2.1. Mandatory Elements 301 o FEC Encoding ID: the Fully-Specified FEC Scheme described in this 302 section uses FEC Encoding ID 2. 304 4.2.2. Common Elements 306 The following elements MUST be defined with the present FEC scheme: 308 o Transfer-Length (L): a non-negative integer indicating the length 309 of the object in bytes. There are some restrictions on the 310 maximum Transfer-Length that can be supported: 312 max_transfer_length = 2^^(32-m) * B * E 314 For instance, for m = 8, for B = 2^^8 - 1 (because the codec 315 operates on a finite field with 2^^8 elements) and if E = 1024 316 bytes, then the maximum transfer length is approximately equal to 317 2^^42 bytes (i.e., 4 Tera Bytes). Similarly, for m = 16, for B = 318 2^^16 - 1 and if E = 1024 bytes, then the maximum transfer length 319 is also approximately equal to 2^^42 bytes. For larger objects, 320 another FEC scheme, with a larger Source Block Number field in the 321 FEC Payload ID, could be defined. Another solution consists in 322 fragmenting large objects into smaller objects, each of them 323 complying with the above limits. 325 o Encoding-Symbol-Length (E): a non-negative integer indicating the 326 length of each encoding symbol in bytes. 328 o Maximum-Source-Block-Length (B): a non-negative integer indicating 329 the maximum number of source symbols in a source block. 331 o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer 332 indicating the maximum number of encoding symbols generated for 333 any source block. 335 Section 6 explains how to derive the values of each of these 336 elements. 338 4.2.3. Scheme-Specific Elements 340 The following element MUST be defined with the present FEC Scheme. 341 It contains two distinct pieces of information: 343 o G: a non-negative integer indicating the number of encoding 344 symbols per group used for the object. The default value is 1, 345 meaning that each packet contains exactly one symbol. When no G 346 parameter is communicated to the decoder, then this latter MUST 347 assume that G = 1. 349 o m: The m parameter is the length of the finite field elements, in 350 bits. It also characterizes the number of elements in the finite 351 field: q = 2^^m elements. The default value is m = 8. When no 352 finite field size parameter is communicated to the decoder, then 353 this latter MUST assume that m = 8. 355 4.2.4. Encoding Format 357 This section shows the two possible encoding formats of the above FEC 358 OTI. The present document does not specify when one encoding format 359 or the other should be used. 361 4.2.4.1. Using the General EXT_FTI Format 363 The FEC OTI binary format is the following, when the EXT_FTI 364 mechanism is used (e.g., within the ALC [10] or NORM [11] protocols). 366 0 1 2 3 367 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 368 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 369 | HET = 64 | HEL = 4 | | 370 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 371 | Transfer-Length (L) | 372 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 373 | m | G | Encoding Symbol Length (E) | 374 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 375 | Max Source Block Length (B) | Max Nb Enc. Symbols (max_n) | 376 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 378 Figure 3: EXT_FTI Header Format 380 4.2.4.2. Using the FDT Instance (FLUTE specific) 382 When it is desired that the FEC OTI be carried in the FDT (File 383 Delivery Table) Instance of a FLUTE session [12], the following XML 384 attributes must be described for the associated object: 386 o FEC-OTI-FEC-Encoding-ID 388 o FEC-OTI-Transfer-Length (L) 389 o FEC-OTI-Encoding-Symbol-Length (E) 391 o FEC-OTI-Maximum-Source-Block-Length (B) 393 o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) 395 o FEC-OTI-Scheme-Specific-Info 397 The FEC-OTI-Scheme-Specific-Info contains the string resulting from 398 the Base64 encoding (in the XML Schema xs:base64Binary sense) of the 399 following value: 401 0 1 402 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 403 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 404 | m | G | 405 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 407 Figure 4: FEC OTI Scheme Specific Information to be included in the 408 FDT Instance 410 When no m parameter is to be carried in the FEC OTI, the m field is 411 set to 0 (which is not a valid seed value). Otherwise the m field 412 contains a valid value as explained in Section 4.2.3. Similarly, 413 when no G parameter is to be carried in the FEC OTI, the G field is 414 set to 0 (which is not a valid seed value). Otherwise the G field 415 contains a valid value as explained in Section 4.2.3. When neither m 416 nor G are to be carried in the FEC OTI, then the sender simply omits 417 the FEC-OTI-Scheme-Specific-Info attribute. 419 After Base64 encoding, the 2 bytes of the FEC OTI Scheme Specific 420 Information are transformed into a string of 4 printable characters 421 (in the 64-character alphabet) and added to the FEC-OTI-Scheme- 422 Specific-Info attribute. 424 5. Formats and Codes with FEC Encoding ID 5 426 This section introduces the formats and codes associated to the 427 Fully-Specified FEC Scheme with FEC Encoding ID 5 that focuses on the 428 special case of Reed-Solomon codes over GF(2^^8) and no encoding 429 symbol group. 431 5.1. FEC Payload ID 433 The FEC Payload ID is composed of the Source Block Number and the 434 Encoding Symbol ID: 436 o The Source Block Number (24 bit field) identifies from which 437 source block of the object the encoding symbol in the payload is 438 generated. There is a maximum of 2^^24 blocks per object. 440 o The Encoding Symbol ID (8 bit field) identifies which specific 441 encoding symbol generated from the source block is carried in the 442 packet payload. There is a maximum of 2^^8 encoding symbols per 443 block. The first k values (0 to k - 1) identify source symbols, 444 the remaining n-k values identify repair symbols. 446 There MUST be exactly one FEC Payload ID per source or repair packet. 447 This FEC Payload ID refer to the one and only symbol of the packet. 449 0 1 2 3 450 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 451 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 452 | Source Block Number (24 bits) | Enc. Symb. ID | 453 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 455 Figure 5: FEC Payload ID encoding format with FEC Encoding ID 5 457 5.2. FEC Object Transmission Information 459 5.2.1. Mandatory Elements 461 o FEC Encoding ID: the Fully-Specified FEC Scheme described in this 462 section uses FEC Encoding ID 5. 464 5.2.2. Common Elements 466 The Common Elements are the same as those specified in Section 4.2.2 467 when m = 8 and G = 1. 469 5.2.3. Scheme-Specific Elements 471 No Scheme-Specific elements are defined by this FEC Scheme. 473 5.2.4. Encoding Format 475 This section shows the two possible encoding formats of the above FEC 476 OTI. The present document does not specify when one encoding format 477 or the other should be used. 479 5.2.4.1. Using the General EXT_FTI Format 481 The FEC OTI binary format is the following, when the EXT_FTI 482 mechanism is used (e.g., within the ALC [10] or NORM [11] protocols). 484 0 1 2 3 485 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 486 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 487 | HET = 64 | HEL = 3 | | 488 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 489 | Transfer-Length (L) | 490 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 491 | Encoding Symbol Length (E) | MaxBlkLen (B) | max_n | 492 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 494 Figure 6: EXT_FTI Header Format with FEC Encoding ID 5 496 5.2.4.2. Using the FDT Instance (FLUTE specific) 498 When it is desired that the FEC OTI be carried in the FDT Instance of 499 a FLUTE session [12], the following XML attributes must be described 500 for the associated object: 502 o FEC-OTI-FEC-Encoding-ID 504 o FEC-OTI-Transfer-Length (L) 506 o FEC-OTI-Encoding-Symbol-Length (E) 508 o FEC-OTI-Maximum-Source-Block-Length (B) 510 o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) 512 6. Procedures with FEC Encoding IDs 2 and 5 514 This section defines procedures that are common to FEC Encoding IDs 2 515 and 5. In case of FEC Encoding ID 5, m = 8 and G = 1. Note that the 516 block partitioning algorithm is defined in [2]. 518 6.1. Determining the Maximum Source Block Length (B) 520 The finite field size parameter, m, defines the number of non zero 521 elements in this field which is equal to: q - 1 = 2^^m - 1. Note 522 that q - 1 is also the theoretical maximum number of encoding symbols 523 that can be produced for a source block. For instance, when m = 8 524 (default) there is a maximum of 2^^8 - 1 = 255 encoding symbols. 526 Given the target FEC code rate (e.g., provided by the user when 527 starting a FLUTE sending application), the sender calculates: 529 max1_B = floor((2^^m - 1) * rate) 531 This max1_B value leaves enough room for the sender to produce the 532 desired number of parity symbols. 534 Additionally, a codec MAY impose other limitations on the maximum 535 block size. Yet it is not expected that such limits exist when using 536 the default m = 8 value. This decision MUST be clarified at 537 implementation time, when the target use case is known. This results 538 in a max2_B limitation. 540 Then, B is given by: 542 B = min(max1_B, max2_B) 544 Note that this calculation is only required at the coder, since the B 545 parameter is communicated to the decoder through the FEC OTI. 547 6.2. Determining the Number of Encoding Symbols of a Block 549 The following algorithm, also called "n-algorithm", explains how to 550 determine the actual number of encoding symbols for a given block. 552 AT A SENDER: 554 Input: 556 B: Maximum source block length, for any source block. Section 6.1 557 explains how to determine its value. 559 k: Current source block length. This parameter is given by the 560 block partitioning algorithm. 562 rate: FEC code rate, which is given by the user (e.g., when 563 starting a FLUTE sending application). It is expressed as a 564 floating point value. 566 Output: 568 max_n: Maximum number of encoding symbols generated for any source 569 block. 571 n: Number of encoding symbols generated for this source block. 573 Algorithm: 575 max_n = ceil(B / rate); 577 if (max_n > 2^^m - 1) then return an error ("invalid code rate"); 579 n = floor(k * max_n / B); 581 AT A RECEIVER: 583 Input: 585 B: Extracted from the received FEC OTI. 587 max_n: Extracted from the received FEC OTI. 589 k: Given by the block partitioning algorithm. 591 Output: 593 n 595 Algorithm: 597 n = floor(k * max_n / B); 599 Note that a Reed-Solomon decoder does not need to know the n value. 600 Therefore the receiver part of the "n-algorithm" is not necessary 601 from the Reed-Solomon decoder point of view. Yet a receiving 602 application using the Reed-Solomon FEC scheme will sometimes need to 603 know the n value used by the sender, for instance for memory 604 management optimizations. To that purpose, the FEC OTI carries all 605 the parameters needed for a receiver to execute the above algorithm. 607 7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) and Reed- 608 Solomon Codes over GF(2^^8) 610 In the context of the Under-Specified Small Block Systematic FEC 611 Scheme (FEC Encoding ID 129) [3], this document assigns the FEC 612 Instance ID 0 to the special case of Reed-Solomon codes over GF(2^^8) 613 and no encoding symbol group. 615 The FEC Instance ID 0 uses the Formats and Codes specified in [3]. 617 The FEC Scheme with FEC Instance ID 0 MAY use the algorithm defined 618 in Section 9.1. of [2] to partition the file into source blocks. 619 This FEC Scheme MAY also use another algorithm. For instance the CDP 620 sender may change the length of each source block dynamically, 621 depending on some external criteria (e.g., to adjust the FEC coding 622 rate to the current loss rate experienced by NORM receivers) and 623 inform the CDP receivers of the current block length by means of the 624 EXT_FTI mechanism. This choice is out of the scope of the current 625 document. 627 8. Reed-Solomon Codes Specification for the Erasure Channel 629 Reed-Solomon (RS) codes are linear block codes. They also belong to 630 the class of MDS codes. A [n,k]-RS code encodes a sequence of k 631 source elements defined over a finite field GF(q) into a sequence of 632 n encoding elements, where n is upper bounded by q - 1. The 633 implementation described in this document is based on a generator 634 matrix built from a Vandermonde matrix put into systematic form. 636 Section 8.1 to Section 8.3 specify the [n,k]-RS codes when applied to 637 m-bit elements, and Section 8.4 the use of [n,k]-RS codes when 638 applied to symbols composed of several m-bit elements, which is the 639 target of this specification. 641 8.1. Finite Field 643 A finite field GF(q) is defined as a finite set of q elements which 644 has a structure of field. It contains necessarily q = p^^m elements, 645 where p is a prime number. With packet erasure channels, p is always 646 set to 2. The elements of the field GF(2^^m) can be represented by 647 polynomials with binary coefficients (i.e., over GF(2)) of degree 648 lower or equal than m-1. The polynomials can be associated to binary 649 vectors of length m. For example, the vector (11001) represents the 650 polynomial 1 + x + x^^4. This representation is often called 651 polynomial representation. The addition between two elements is 652 defined as the addition of binary polynomials in GF(2) and the 653 multiplication is the multiplication modulo a given irreducible 654 polynomial over GF(2) of degree m with coefficients in GF(2). Note 655 that all the roots of this polynomial are in GF(2^^m) but not in 656 GF(2). 658 A finite field GF(2^^m) is completely characterized by the 659 irreducible polynomial. The following polynomials are chosen to 660 represent the field GF(2^^m), for m varying from 2 to 16: 662 m = 2, "111" (1+x+x^^2) 664 m = 3, "1101", (1+x+x^^3) 666 m = 4, "11001", (1+x+x^^4) 668 m = 5, "101001", (1+x^^2+x^^5) 670 m = 6, "1100001", (1+x+x^^6) 672 m = 7, "10010001", (1+x^^3+x^^7) 673 m = 8, "101110001", (1+x^^2+x^^3+x^^4+x^^8) 675 m = 9, "1000100001", (1+x^^4+x^^9) 677 m = 10, "10010000001", (1+x^^3+x^^10) 679 m = 11, "101000000001", (1+x^^2+x^^11) 681 m = 12, "1100101000001", (1+x+x^^4+x^^6+x^^12) 683 m = 13, "11011000000001", (1+x+x^^3+x^^4+x^^13) 685 m = 14, "110000100010001", (1+x+x^^6+x^^10+x^^14) 687 m = 15, "1100000000000001", (1+x+x^^15) 689 m = 16, "11010000000010001", (1+x+x^^3+x^^12+x^^16) 691 In order to facilitate the implementation, these polynomials are also 692 primitive. This means that any element of GF(2^^m) can be expressed 693 as a power of a given root of this polynomial. These polynomials are 694 also chosen so that they contain the minimum number of monomials. 696 8.2. Reed-Solomon Encoding Algorithm 698 8.2.1. Encoding Principles 700 Let s = (s_0, ..., s_{k-1}) be a source vector of k elements over 701 GF(2^^m). Let e = (e_0, ..., e_{n-1}) be the corresponding encoding 702 vector of n elements over GF(2^^m). Being a linear code, encoding is 703 performed by multiplying the source vector by a generator matrix, GM, 704 of k rows and n columns over GF(2^^m). Thus: 706 e = s * GM. 708 The definition of the generator matrix completely characterizes the 709 RS code. 711 Let us consider that: n = 2^^m - 1 and: 0 < k <= n. Let us denote by 712 alpha the root of the primitive polynomial of degree m chosen in the 713 list of Section 8.1 for the corresponding value of m. Let us 714 consider a Vandermonde matrix of k rows and n columns, denoted by 715 V_{k,n}, and built as follows: the {i, j} entry of V_{k,n} is v_{i,j} 716 = alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This 717 matrix generates a MDS code. However, this MDS code is not 718 systematic, which is a problem for many networking applications. To 719 obtain a systematic matrix (and code), the simplest solution consists 720 in considering the matrix V_{k,k} formed by the first k columns of 721 V_{k,n}, then to invert it and to multiply this inverse by V_{k,n}. 722 Clearly, the product V_{k,k}^^-1 * V_{k,n} contains the identity 723 matrix I_k on its first k columns, meaning that the first k encoding 724 elements are equal to source elements. Besides the associated code 725 keeps the MDS property. 727 Therefore, the generator matrix of the code considered in this 728 document is: 730 GM = (V_{k,k}^^-1) * V_{k,n} 732 Note that, in practice, the [n,k]-RS code can be shortened to a 733 [n',k]-RS code, where k <= n' < n, by considering the sub-matrix 734 formed by the n' first columns of GM. 736 8.2.2. Encoding Complexity 738 Encoding can be performed by first pre-computing GM and by 739 multiplying the source vector (k elements) by GM (k rows and n 740 columns). The complexity of the pre-computation of the generator 741 matrix can be estimated as the complexity of the multiplication of 742 the inverse of a Vandermonde matrix by n-k vectors (i.e., the last 743 n-k columns of V_{k,n}). Since the complexity of the inverse of a 744 k*k-Vandermonde matrix by a vector is O(k * log^^2(k)), the generator 745 matrix can be computed in 0((n-k)* k * log^^2(k)) operations. When 746 the generator matrix is pre-computed, the encoding needs k operations 747 per repair element (vector-matrix multiplication). 749 Encoding can also be performed by first computing the product s * 750 V_{k,k}^^-1 and then by multiplying the result with V_{k,n}. The 751 multiplication by the inverse of a square Vandermonde matrix is known 752 as the interpolation problem and its complexity is O(k * log^^2 (k)). 753 The multiplication by a Vandermonde matrix, known as the multipoint 754 evaluation problem, requires O((n-k) * log(k)) by using Fast Fourier 755 Transform, as explained in [7]. The total complexity of this 756 encoding algorithm is then O((k/(n-k)) * log^^2(k) + log(k)) 757 operations per repair element. 759 8.3. Reed-Solomon Decoding Algorithm 761 8.3.1. Decoding Principles 763 The Reed-Solomon decoding algorithm for the erasure channel allows 764 the recovery of the k source elements from any set of k received 765 elements. It is based on the fundamental property of the generator 766 matrix which is such that any k*k-submatrix is invertible (see [6]). 767 The first step of the decoding consists in extracting the k*k 768 submatrix of the generator matrix obtained by considering the columns 769 corresponding to the received elements. Indeed, since any encoding 770 element is obtained by multiplying the source vector by one column of 771 the generator matrix, the received vector of k encoding elements can 772 be considered as the result of the multiplication of the source 773 vector by a k*k submatrix of the generator matrix. Since this 774 submatrix is invertible, the second step of the algorithm is to 775 invert this matrix and to multiply the received vector by the 776 obtained matrix to recover the source vector. 778 8.3.2. Decoding Complexity 780 The decoding algorithm described previously includes the matrix 781 inversion and the vector-matrix multiplication. With the classical 782 Gauss-Jordan algorithm, the matrix inversion requires O(k^^3) 783 operations and the vector-matrix multiplication is performed in 784 O(k^^2) operations. 786 This complexity can be improved by considering that the received 787 submatrix of GM is the product between the inverse of a Vandermonde 788 matrix (V_(k,k)^^-1) and another Vandermonde matrix (denoted by V' 789 which is a submatrix of V_(k,n)). The decoding can be done by 790 multiplying the received vector by V'^^-1 (interpolation problem with 791 complexity O( k * log^^2(k)) ) then by V_{k,k} (multipoint evaluation 792 with complexity O(k * log(k))). The global decoding complexity is 793 then O(log^^2(k)) operations per source element. 795 8.4. Implementation for the Packet Erasure Channel 797 In a packet erasure channel, each packet (and symbol(s) since packets 798 contain G >= 1 symbols) is either correctly received or erased. The 799 location of the erased symbols in the sequence of symbols MUST be 800 known. The following specification describes the use of Reed-Solomon 801 codes for generating redundant symbols from the k source symbols and 802 for recovering the source symbols from any set of k received symbols. 804 The k source symbols of a source block are assumed to be composed of 805 S m-bit elements. Each m-bit element corresponds to an element of 806 the finite field GF(2^^m) through the polynomial representation 807 (Section 8.1). If some of the source symbols contain less than S 808 elements, they MUST be virtually padded with zero elements (it can be 809 the case for the last symbol of the last block of the object). 810 However, this padding does not need to be actually sent with the data 811 to the receivers. 813 The encoding process produces n encoding symbols of size S m-bit 814 elements, of which k are source symbols (this is a systematic code) 815 and n-k are repair symbols (Figure 7). The m-bit elements of the 816 repair symbols are calculated using the corresponding m-bit elements 817 of the source symbol set. A logical j-th source vector, comprised of 818 the j-th elements from the set of source symbols, is used to 819 calculate a j-th encoding vector. This j-th encoding vector then 820 provides the j-th elements for the set encoding symbols calculated 821 for the block. As a systematic code, the first k encoding symbols 822 are the same as the k source symbols and the last n-k repair symbols 823 are the result of the Reed-Solomon encoding. 825 Input: k source symbols 827 0 j S-1 828 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 829 | |X| | source symbol 0 830 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 831 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 832 | |X| | source symbol 1 833 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 834 . . . 835 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 836 | |X| | source symbol k-1 837 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 839 * 841 +--------------------+ 842 | generator matrix | 843 | GM | 844 | (k x n) | 845 +--------------------+ 847 | 848 V 850 Output: n encoding symbols (source + repair) 852 0 j S-1 853 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 854 | |X| | enc. symbol 0 855 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 856 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 857 | |X| | enc. symbol 1 858 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 859 . . . 860 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 861 | |Y| | enc. symbol n-1 862 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 864 Figure 7: Packet encoding scheme 866 An asset of this scheme is that the loss of some encoding symbols 867 produces the same erasure pattern for each of the S encoding vectors. 868 It follows that the matrix inversion must be done only once and will 869 be used by all the S encoding vectors. For large S, this matrix 870 inversion cost becomes negligible in front of the S matrix-vector 871 multiplications. 873 Another asset is that the n-k repair symbols can be produced on 874 demand. For instance, a sender can start by producing a limited 875 number of repair symbols and later on, depending on the observed 876 erasures on the channel, decide to produce additional repair symbols, 877 up to the n-k upper limit. Indeed, to produce the repair symbol e_j, 878 where k <= j < n, it is sufficient to multiply the S source vectors 879 with column j of GM. 881 9. Security Considerations 883 9.1. Problem Statement 885 A content delivery system is potentially subject to many attacks: 886 some of them target the network (e.g., to compromise the routing 887 infrastructure, by compromising the congestion control component), 888 others target the Content Delivery Protocol (CDP) (e.g., to 889 compromise its normal behavior), and finally some attacks target the 890 content itself. Since this document focuses on a FEC building block 891 independently of any particular CDP (even if ALC and NORM are two 892 natural candidates), this section only discusses the additional 893 threats that an arbitrary CDP may be exposed to when using this 894 building block. 896 More specifically, several kinds of attacks exist: 898 o those that are meant to give access to a confidential content 899 (e.g., in case of a non-free content), 901 o those that try to corrupt the object being transmitted (e.g., to 902 inject malicious code within an object, or to prevent a receiver 903 from using an object), 905 o and those that try to compromise the receiver's behavior (e.g., by 906 making the decoding of an object computationally expensive). 908 These attacks can be launched either against the data flow itself 909 (e.g. by sending forged symbols) or against the FEC parameters that 910 are sent either in-band (e.g., in an EXT_FTI or FDT Instance) or out- 911 of-band (e.g., in a session description). 913 9.2. Attacks Against the Data Flow 915 First of all, let us consider the attacks against the data flow. 916 Access control is typically provided by means of encryption. This 917 encryption can be done over the whole object (e.g., by the content 918 provider, before the FEC encoding process), or be done on a packet 919 per packet basis (e.g., when IPSec/ESP is used [14]). If access 920 control is a concern, it is RECOMMENDED that one of these solutions 921 be used. Even if we mention these attacks here, they are not related 922 nor facilitated by the use of FEC. 924 Protection against corruptions (forged packets) is achieved by means 925 of a content integrity verification/sender authentication scheme. 926 This service can be provided at the object level, but in that case a 927 receiver has no way to identify which symbol(s) is(are) corrupted if 928 the object is detected as corrupted. This service can also be 929 provided at the packet level, and after having removed all forged 930 packets, the object can be recovered if the number of symbols 931 remaining is sufficient. Several techniques can provide this source 932 authentication/content integrity service: 934 o at the object level, the object MAY be digitally signed (with 935 public key cryptography) (e.g., using RSASSA-PKCS1-v1_5 [13]). 936 This signature enables a receiver to check the object, once this 937 latter has been fully decoded. Even if digital signatures are 938 computationally expensive, this calculation occurs only once per 939 object, which is usually acceptable; 941 o at the packet level, each packet can be digitally signed. A major 942 limitation is the high computational and transmission overheads 943 that this solution incurs (unless ECC is used, but ECC is 944 protected by IPR). To avoid this problem, the signature may span 945 a set of symbols in order to amortize the signature calculation, 946 but if a single symbol is missing, the integrity of the whole set 947 cannot be checked; 949 o at the packet level, a Group Message Authentication Code (MAC) 950 [15] (e.g., using HMAC-SHA-1 with a secret key shared by all the 951 group members, senders and receivers) scheme can be used. This 952 technique creates a cryptographically secured (thanks to the 953 secret key) digest of a packet that is sent along with the packet. 954 The Group MAC scheme does not incur prohibitive processing load 955 nor transmission overhead, but it has a major limitation: it only 956 provides a group authentication/integrity service since all group 957 members share the same secret group key, which means that each 958 member can send a forged packet. It is therefore restricted to 959 situations where group members are fully trusted (or in 960 association with another technique as a pre-check); 962 o at the packet level, TESLA [16] is a very attractive and efficient 963 solution that is robust to losses, provides a true authentication/ 964 integrity service, and does not incur any prohibitive processing 965 load or transmission overhead. 967 It is up to the developer, who knows the security requirements of the 968 target use-case, to define which solution is the most appropriate. 969 Nonetheless, it is RECOMMENDED that at least one of these techniques 970 be used. 972 Techniques relying on public key cryptography (digital signatures and 973 TESLA during the bootstrap process) require that public keys be 974 securely associated to the entities. This can be achieved by a 975 Public Key Infrastructure (PKI), or by a PGP Web of Trust, or by pre- 976 distributing the public keys of each group member. It is up to the 977 developer, who knows the features of the target use-case, to define 978 which solution to use. 980 Techniques relying on symmetric key cryptography (group MAC) require 981 that a secret key be shared by all group members. This can be 982 achieved by means of a group key management protocol, or simply by 983 pre-distributing the secret key (but this manual solution has many 984 limitations). Here also, it is up to the developer to define which 985 solution to use, taking into account the target use-case features. 987 9.3. Attacks against the FEC parameters 989 Let us now consider attacks against the FEC parameters (or FEC OTI). 990 The FEC OTI can either be sent in-band (i.e., in an EXT_FTI or in an 991 FDT Instance containing FEC OTI for the object) or out-of-band (e.g., 992 in a session description). Attacks on these FEC parameters can 993 prevent the decoding of the associated object: for instance modifying 994 the B parameter will lead to a different block partitioning at a 995 receiver thereby compromising decoding; or setting the m parameter to 996 16 instead of 8 with FEC Encoding ID 2 will increase the processing 997 load while compromising decoding. 999 It is therefore RECOMMENDED that security measures be taken to 1000 guarantee the FEC OTI integrity. To that purpose, the packets 1001 carrying the FEC parameters sent in-band (i.e., in an EXT_FTI header 1002 extension or in an FDT Instance) may be protected by one of the per- 1003 packet techniques described above: TESLA, digital signature, or a 1004 group MAC. Alternatively, when FEC OTI is contained in an FDT 1005 Instance, this object may be digitally signed. Finally, when FEC OTI 1006 is sent out-of-band for instance in a session description, this 1007 latter may be protected by a digital signature. 1009 The same considerations concerning the key management aspects apply 1010 here also. 1012 10. IANA Considerations 1014 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA 1015 registration. For general guidelines on IANA considerations as they 1016 apply to this document, see [2]. 1018 This document assigns the Fully-Specified FEC Encoding ID 2 under the 1019 "ietf:rmt:fec:encoding" name-space to "Reed-Solomon Codes over 1020 GF(2^^m)". 1022 This document assigns the Fully-Specified FEC Encoding ID 5 under the 1023 "ietf:rmt:fec:encoding" name-space to "Reed-Solomon Codes over 1024 GF(2^^8)". 1026 This document assigns the FEC Instance ID 0 scoped by the Under- 1027 Specified FEC Encoding ID 129 to "Reed-Solomon Codes over GF(2^^8)". 1028 More specifically, under the "ietf:rmt:fec:encoding:instance" sub- 1029 name-space that is scoped by the "ietf:rmt:fec:encoding" called 1030 "Small Block Systematic FEC Codes", this document assigns FEC 1031 Instance ID 0 to "Reed-Solomon Codes over GF(2^^8)". 1033 11. Acknowledgments 1035 The authors want to thank Brian Adamson, Igor Slepchin, Stephen Kent, 1036 and Francis Dupont for their valuable comments. The authors also 1037 want to thank Luigi Rizzo for his comments and for the design of the 1038 reference Reed-Solomon codec. 1040 12. References 1042 12.1. Normative References 1044 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 1045 Levels", RFC 2119. 1047 [2] Watson, M., Luby, M., and L. Vicisano, "Forward Error 1048 Correction (FEC) Building Block", RFC 5052, August 2007. 1050 [3] Watson, M., "Basic Forward Error Correction (FEC) Schemes", 1051 draft-ietf-rmt-bb-fec-basic-schemes-revised-03.txt (work in 1052 progress), February 2007. 1054 12.2. Informative References 1056 [4] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., 1057 and J. Crowcroft, "The Use of Forward Error Correction (FEC) in 1058 Reliable Multicast", RFC 3453, December 2002. 1060 [5] Rizzo, L., "Reed-Solomon FEC codec (revised version of July 1061 2nd, 1998), available at 1062 http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz and 1063 mirrored at http://planete-bcast.inrialpes.fr/", July 1998. 1065 [6] Mac Williams, F. and N. Sloane, "The Theory of Error Correcting 1066 Codes", North Holland, 1977. 1068 [7] Gohberg, I. and V. Olshevsky, "Fast algorithms with 1069 preprocessing for matrix-vector multiplication problems", 1070 Journal of Complexity, pp. 411-427, vol. 10, 1994. 1072 [8] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity 1073 Check (LDPC) Forward Error Correction", 1074 draft-ietf-rmt-bb-fec-ldpc-06.txt (work in progress), 1075 May 2007. 1077 [9] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, 1078 "Raptor Forward Error Correction Scheme", 1079 draft-ietf-rmt-bb-fec-raptor-object-09 (work in progress), 1080 June 2007. 1082 [10] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered 1083 Coding (ALC) Protocol Instantiation", 1084 draft-ietf-rmt-pi-alc-revised-04.txt (work in progress), 1085 February 2007. 1087 [11] Adamson, B., Bormann, C., Handley, M., and J. Macker, 1088 "Negative-acknowledgment (NACK)-Oriented Reliable Multicast 1089 (NORM) Protocol", draft-ietf-rmt-pi-norm-revised-05.txt (work 1090 in progress), March 2007. 1092 [12] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, 1093 "FLUTE - File Delivery over Unidirectional Transport", 1094 draft-ietf-rmt-flute-revised-04.txt (work in progress), 1095 October 2007. 1097 [13] Jonsson, J. and B. Kaliski, "Public-Key Cryptography Standards 1098 (PKCS) #1: RSA Cryptography Specifications Version 2.1", 1099 RFC 3447, February 2003. 1101 [14] Kent, S., "IP Encapsulating Security Payload (ESP)", RFC 4303, 1102 December 2005. 1104 [15] "HMAC: Keyed-Hashing for Message Authentication", RFC 2104, 1105 February 1997. 1107 [16] "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): 1108 Multicast Source Authentication Transform Introduction", 1109 RFC 4082, June 2005. 1111 Authors' Addresses 1113 Jerome Lacan 1114 ISAE 1115 1, place Emile Blouin 1116 Toulouse 31056 1117 France 1119 Email: jerome.lacan@isae.fr 1120 URI: http://dmi.ensica.fr/auteur.php3?id_auteur=5 1122 Vincent Roca 1123 INRIA 1124 655, av. de l'Europe 1125 Inovallee; Montbonnot 1126 ST ISMIER cedex 38334 1127 France 1129 Email: vincent.roca@inrialpes.fr 1130 URI: http://planete.inrialpes.fr/~roca/ 1132 Jani Peltotalo 1133 Tampere University of Technology 1134 P.O. Box 553 (Korkeakoulunkatu 1) 1135 Tampere FIN-33101 1136 Finland 1138 Email: jani.peltotalo@tut.fi 1139 URI: http://atm.tut.fi/mad 1141 Sami Peltotalo 1142 Tampere University of Technology 1143 P.O. Box 553 (Korkeakoulunkatu 1) 1144 Tampere FIN-33101 1145 Finland 1147 Email: sami.peltotalo@tut.fi 1148 URI: http://atm.tut.fi/mad 1150 Full Copyright Statement 1152 Copyright (C) The IETF Trust (2007). 1154 This document is subject to the rights, licenses and restrictions 1155 contained in BCP 78, and except as set forth therein, the authors 1156 retain all their rights. 1158 This document and the information contained herein are provided on an 1159 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1160 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1161 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1162 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1163 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1164 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1166 Intellectual Property 1168 The IETF takes no position regarding the validity or scope of any 1169 Intellectual Property Rights or other rights that might be claimed to 1170 pertain to the implementation or use of the technology described in 1171 this document or the extent to which any license under such rights 1172 might or might not be available; nor does it represent that it has 1173 made any independent effort to identify any such rights. Information 1174 on the procedures with respect to rights in RFC documents can be 1175 found in BCP 78 and BCP 79. 1177 Copies of IPR disclosures made to the IETF Secretariat and any 1178 assurances of licenses to be made available, or the result of an 1179 attempt made to obtain a general license or permission for the use of 1180 such proprietary rights by implementers or users of this 1181 specification can be obtained from the IETF on-line IPR repository at 1182 http://www.ietf.org/ipr. 1184 The IETF invites any interested party to bring to its attention any 1185 copyrights, patents or patent applications, or other proprietary 1186 rights that may cover technology that may be required to implement 1187 this standard. Please address the information to the IETF at 1188 ietf-ipr@ietf.org. 1190 Acknowledgment 1192 Funding for the RFC Editor function is provided by the IETF 1193 Administrative Support Activity (IASA).