idnits 2.17.1 draft-ietf-rmt-bb-fec-rs-03.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 1053. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1064. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1071. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1077. 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 (May 7, 2007) is 6197 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Outdated reference: A later version (-06) exists of draft-ietf-rmt-bb-fec-basic-schemes-revised-03 == Outdated reference: A later version (-09) exists of draft-ietf-rmt-bb-fec-raptor-object-08 == 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-04 == Outdated reference: A later version (-16) exists of draft-ietf-rmt-flute-revised-03 Summary: 1 error (**), 0 flaws (~~), 7 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Reliable Multicast Transport J. Lacan 3 Internet-Draft ENSICA/LAAS-CNRS 4 Intended status: Experimental V. Roca 5 Expires: November 8, 2007 INRIA 6 J. Peltotalo 7 S. Peltotalo 8 Tampere University of Technology 9 May 7, 2007 11 Reed-Solomon Forward Error Correction (FEC) Schemes 12 draft-ietf-rmt-bb-fec-rs-03.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 November 8, 2007. 39 Copyright Notice 41 Copyright (C) The IETF Trust (2007). 43 Abstract 45 This document describes a Fully-Specified FEC Scheme for the Reed- 46 Solomon forward error correction 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 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 101 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 25 102 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26 103 12.1. Normative References . . . . . . . . . . . . . . . . . . . 26 104 12.2. Informative References . . . . . . . . . . . . . . . . . . 26 105 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 28 106 Intellectual Property and Copyright Statements . . . . . . . . . . 29 108 1. Introduction 110 The use of Forward Error Correction (FEC) codes is a classical 111 solution to improve the reliability of multicast and broadcast 112 transmissions. The [2] document describes a general framework to use 113 FEC in Content Delivery Protocols (CDP). The companion document [4] 114 describes some applications of FEC codes for content delivery. 116 Recent FEC schemes like [9] and [10] proposed erasure codes based on 117 sparse graphs/matrices. These codes are efficient in terms of 118 processing but not optimal in terms of correction capabilities when 119 dealing with "small" objects. 121 The FEC scheme described in this document belongs to the class of 122 Maximum Distance Separable codes that are optimal in terms of erasure 123 correction capability. In others words, it enables a receiver to 124 recover the k source symbols from any set of exactly k encoding 125 symbols. Even if the encoding/decoding complexity is larger than 126 that of [9] or [10], this family of codes is very useful. 128 Many applications dealing with content transmission or content 129 storage already rely on packet-based Reed-Solomon codes. In 130 particular, many of them use the Reed-Solomon codec of Luigi Rizzo 131 [7]. The goal of the present document to specify an implementation 132 of Reed-Solomon codes that is compatible with this codec. 134 The present document: 136 o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 2 137 that specifies the use of Reed-Solomon codes over GF(2^^m), with m 138 in {2..16}, 140 o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 5 141 that focuses on the special case of Reed-Solomon codes over 142 GF(2^^8) and no encoding symbol group (i.e. exactly one symbol per 143 packet), and 145 o in the context of the Under-Specified Small Block Systematic FEC 146 Scheme (FEC Encoding ID 129) [3], assigns the FEC Instance ID 0 to 147 the special case of Reed-Solomon codes over GF(2^^8) and no 148 encoding symbol group. 150 2. Terminology 152 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 153 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 154 document are to be interpreted as described in RFC 2119 [1]. 156 3. Definitions Notations and Abbreviations 158 3.1. Definitions 160 This document uses the same terms and definitions as those specified 161 in [2]. Additionally, it uses the following definitions: 163 Source symbol: unit of data used during the encoding process. 165 Encoding symbol: unit of data generated by the encoding process. 167 Repair symbol: encoding symbol that is not a source symbol. 169 Systematic code: FEC code in which the source symbols are part of 170 the encoding symbols. 172 Source block: a block of k source symbols that are considered 173 together for the encoding. 175 Encoding Symbol Group: a group of encoding symbols that are sent 176 together within the same packet, and whose relationships to the 177 source block can be derived from a single Encoding Symbol ID. 179 Source Packet: a data packet containing only source symbols. 181 Repair Packet: a data packet containing only repair symbols. 183 3.2. Notations 185 This document uses the following notations: 187 L denotes the object transfer length in bytes. 189 k denotes the number of source symbols in a source block. 191 n_r denotes the number of repair symbols generated for a source 192 block. 194 n denotes the encoding block length, i.e. the number of encoding 195 symbols generated for a source block. Therefore: n = k + n_r. 197 max_n denotes the maximum number of encoding symbols generated for 198 any source block. 200 B denotes the maximum source block length in symbols, i.e. the 201 maximum number of source symbols per source block. 203 N denotes the number of source blocks into which the object shall 204 be partitioned. 206 E denotes the encoding symbol length in bytes. 208 S denotes the symbol size in units of m-bit elements. When m = 8, 209 then S and E are equal. 211 m defines the length of the elements in the finite field, in bits. 212 In this document, m belongs to {2..16}. 214 q defines the number of elements in the finite field. We have: q 215 = 2^^m in this specification. 217 G denotes the number of encoding symbols per group, i.e. the 218 number of symbols sent in the same packet. 220 GM denotes the Generator Matrix of a Reed-Solomon code. 222 rate denotes the "code rate", i.e. the k/n ratio. 224 a^^b denotes a raised to the power b. 226 a^^-1 denotes the inverse of a. 228 I_k denotes the k*k identity matrix. 230 3.3. Abbreviations 232 This document uses the following abbreviations: 234 ESI stands for Encoding Symbol ID. 236 FEC OTI stands for FEC Object Transmission Information. 238 RS stands for Reed-Solomon. 240 MDS stands for Maximum Distance Separable code. 242 GF(q) denotes a finite field (A.K.A. Galois Field) with q 243 elements. We assume that q = 2^^m in this document. 245 4. Formats and Codes with FEC Encoding ID 2 247 This section introduces the formats and codes associated to the 248 Fully-Specified FEC Scheme with FEC Encoding ID 2 that specifies the 249 use of Reed-Solomon codes over GF(2^^m). 251 4.1. FEC Payload ID 253 The FEC Payload ID is composed of the Source Block Number and the 254 Encoding Symbol ID. The length of these two fields depends on the 255 parameter m (which is transmitted in the FEC OTI) as follows: 257 o The Source Block Number (field of size 32-m bits) identifies from 258 which source block of the object the encoding symbol(s) in the 259 payload is(are) generated. There are a maximum of 2^^(32-m) 260 blocks per object. 262 o The Encoding Symbol ID (field of size m bits) identifies which 263 specific encoding symbol(s) generated from the source block 264 is(are) carried in the packet payload. There are a maximum of 265 2^^m encoding symbols per block. The first k values (0 to k - 1) 266 identify source symbols, the remaining n-k values identify repair 267 symbols. 269 There MUST be exactly one FEC Payload ID per source or repair packet. 270 In case of an Encoding Symbol Group, when multiple encoding symbols 271 are sent in the same packet, the FEC Payload ID refers to the first 272 symbol of the packet. The other symbols can be deduced from the ESI 273 of the first symbol by incrementing sequentially the ESI. 275 The format of the FEC Payload ID for m = 8 and m = 16 is illustrated 276 in Figure 1 and Figure 2 respectively. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 291 Figure 2: FEC Payload ID encoding format for m = 16 293 4.2. FEC Object Transmission Information 295 4.2.1. Mandatory Elements 297 o FEC Encoding ID: the Fully-Specified FEC Scheme described in this 298 section uses FEC Encoding ID 2. 300 4.2.2. Common Elements 302 The following elements MUST be defined with the present FEC scheme: 304 o Transfer-Length (L): a non-negative integer indicating the length 305 of the object in bytes. There are some restrictions on the 306 maximum Transfer-Length that can be supported: 308 max_transfer_length = 2^^(32-m) * B * E 310 For instance, for m = 8, for B = 2^^8 - 1 (because the codec 311 operates on a finite field with 2^^8 elements) and if E = 1024 312 bytes, then the maximum transfer length is approximately equal to 313 2^^42 bytes (i.e. 4 Tera Bytes). Similarly, for m = 16, for B = 314 2^^16 - 1 and if E = 1024 bytes, then the maximum transfer length 315 is also approximately equal to 2^^42 bytes. For larger objects, 316 another FEC scheme, with a larger Source Block Number field in the 317 FEC Payload ID, could be defined. Another solution consists in 318 fragmenting large objects into smaller objects, each of them 319 complying with the above limits. 321 o Encoding-Symbol-Length (E): a non-negative integer indicating the 322 length of each encoding symbol in bytes. 324 o Maximum-Source-Block-Length (B): a non-negative integer indicating 325 the maximum number of source symbols in a source block. 327 o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer 328 indicating the maximum number of encoding symbols generated for 329 any source block. 331 Section 6 explains how to derive the values of each of these 332 elements. 334 4.2.3. Scheme-Specific Elements 336 The following element MUST be defined with the present FEC Scheme. 337 It contains two distinct pieces of information: 339 o G: a non-negative integer indicating the number of encoding 340 symbols per group used for the object. The default value is 1, 341 meaning that each packet contains exactly one symbol. When no G 342 parameter is communicated to the decoder, then this latter MUST 343 assume that G = 1. 345 o Finite Field parameter, m: The m parameter is the length of the 346 finite field elements, in bits. It also characterizes the number 347 of elements in the finite field: q = 2^^m elements. The default 348 value is m = 8. When no finite field size parameter is 349 communicated to the decoder, then this latter MUST assume that m = 350 8. 352 4.2.4. Encoding Format 354 This section shows the two possible encoding formats of the above FEC 355 OTI. The present document does not specify when one encoding format 356 or the other should be used. 358 4.2.4.1. Using the General EXT_FTI Format 360 The FEC OTI binary format is the following, when the EXT_FTI 361 mechanism is used (e.g. within the ALC [11] or NORM [12] protocols). 363 0 1 2 3 364 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 365 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 366 | HET = 64 | HEL = 4 | | 367 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 368 | Transfer-Length (L) | 369 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 370 | m | G | Encoding Symbol Length (E) | 371 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 372 | Max Source Block Length (B) | Max Nb Enc. Symbols (max_n) | 373 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 375 Figure 3: EXT_FTI Header Format 377 4.2.4.2. Using the FDT Instance (FLUTE specific) 379 When it is desired that the FEC OTI be carried in the FDT Instance of 380 a FLUTE session [13], the following XML attributes must be described 381 for the associated object: 383 o FEC-OTI-FEC-Encoding-ID 385 o FEC-OTI-Transfer-Length (L) 386 o FEC-OTI-Encoding-Symbol-Length (E) 388 o FEC-OTI-Maximum-Source-Block-Length (B) 390 o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) 392 o FEC-OTI-Scheme-Specific-Info 394 The FEC-OTI-Scheme-Specific-Info contains the string resulting from 395 the Base64 encoding (in the XML Schema xs:base64Binary sense) of the 396 following value: 398 0 1 399 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 400 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 401 | m | G | 402 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 404 Figure 4: FEC OTI Scheme Specific Information to be included in the 405 FDT Instance 407 When no m parameter is to be carried in the FEC OTI, the m field is 408 set to 0 (which is not a valid seed value). Otherwise the m field 409 contains a valid value as explained in Section 4.2.3. Similarly, 410 when no G parameter is to be carried in the FEC OTI, the G field is 411 set to 0 (which is not a valid seed value). Otherwise the G field 412 contains a valid value as explained in Section 4.2.3. When neither m 413 nor G are to be carried in the FEC OTI, then the sender simply omits 414 the FEC-OTI-Scheme-Specific-Info attribute. 416 After Base64 encoding, the 2 bytes of the FEC OTI Scheme Specific 417 Information are transformed into a string of 4 printable characters 418 (in the 64-character alphabet) and added to the FEC-OTI-Scheme- 419 Specific-Info attribute. 421 5. Formats and Codes with FEC Encoding ID 5 423 This section introduces the formats and codes associated to the 424 Fully-Specified FEC Scheme with FEC Encoding ID 5 that focuses on the 425 special case of Reed-Solomon codes over GF(2^^8) and no encoding 426 symbol group. 428 5.1. FEC Payload ID 430 The FEC Payload ID is composed of the Source Block Number and the 431 Encoding Symbol ID: 433 o The Source Block Number (24 bit field) identifies from which 434 source block of the object the encoding symbol in the payload is 435 generated. There are a maximum of 2^^24 blocks per object. 437 o The Encoding Symbol ID (8 bit field) identifies which specific 438 encoding symbol generated from the source block is carried in the 439 packet payload. There are a maximum of 2^^8 encoding symbols per 440 block. The first k values (0 to k - 1) identify source symbols, 441 the remaining n-k values identify repair symbols. 443 There MUST be exactly one FEC Payload ID per source or repair packet. 444 This FEC Payload ID refer to the one and only symbol of the packet. 446 0 1 2 3 447 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 448 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 449 | Source Block Number (24 bits) | Enc. Symb. ID | 450 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 452 Figure 5: FEC Payload ID encoding format with FEC Encoding ID 5 454 5.2. FEC Object Transmission Information 456 5.2.1. Mandatory Elements 458 o FEC Encoding ID: the Fully-Specified FEC Scheme described in this 459 section uses FEC Encoding ID 5. 461 5.2.2. Common Elements 463 The Common Elements are the same as those specified in Section 4.2.2 464 when m = 8 and G = 1. 466 5.2.3. Scheme-Specific Elements 468 No Scheme-Specific elements are defined by this FEC Scheme. 470 5.2.4. Encoding Format 472 This section shows the two possible encoding formats of the above FEC 473 OTI. The present document does not specify when one encoding format 474 or the other should be used. 476 5.2.4.1. Using the General EXT_FTI Format 478 The FEC OTI binary format is the following, when the EXT_FTI 479 mechanism is used (e.g. within the ALC [11] or NORM [12] protocols). 481 0 1 2 3 482 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 483 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 484 | HET = 64 | HEL = 3 | | 485 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 486 | Transfer-Length (L) | 487 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 488 | Encoding Symbol Length (E) | MaxBlkLen (B) | max_n | 489 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 491 Figure 6: EXT_FTI Header Format with FEC Encoding ID 5 493 5.2.4.2. Using the FDT Instance (FLUTE specific) 495 When it is desired that the FEC OTI be carried in the FDT Instance of 496 a FLUTE session [13], the following XML attributes must be described 497 for the associated object: 499 o FEC-OTI-FEC-Encoding-ID 501 o FEC-OTI-Transfer-Length (L) 503 o FEC-OTI-Encoding-Symbol-Length (E) 505 o FEC-OTI-Maximum-Source-Block-Length (B) 507 o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) 509 6. Procedures with FEC Encoding IDs 2 and 5 511 This section defines procedures that are common to FEC Encoding IDs 2 512 and 5. In case of FEC Encoding ID 5, m = 8 and G = 1. Note that the 513 block partitioning algorithm is defined in [2]. 515 6.1. Determining the Maximum Source Block Length (B) 517 The finite field size parameter, m, defines the number of non zero 518 elements in this field which is equal to: q - 1 = 2^^m - 1. Note 519 that q - 1 is also the theoretical maximum number of encoding symbols 520 that can be produced for a source block. For instance, when m = 8 521 (default): 523 max1_B = 2^^8 - 1 = 255 525 Additionally, a codec MAY impose other limitations on the maximum 526 block size. Yet it is not expected that such limits exist when using 527 the default m = 8 value. This decision MUST be clarified at 528 implementation time, when the target use case is known. This results 529 in a max2_B limitation. 531 Then, B is given by: 533 B = min(max1_B, max2_B) 535 Note that this calculation is only required at the coder, since the B 536 parameter is communicated to the decoder through the FEC OTI. 538 6.2. Determining the Number of Encoding Symbols of a Block 540 The following algorithm, also called "n-algorithm", explains how to 541 determine the actual number of encoding symbols for a given block. 543 AT A SENDER: 545 Input: 547 B: Maximum source block length, for any source block. Section 6.1 548 explains how to determine its value. 550 k: Current source block length. This parameter is given by the 551 block partitioning algorithm. 553 rate: FEC code rate, which is given by the user (e.g. when 554 starting a FLUTE sending application). It is expressed as a 555 floating point value. 557 Output: 559 max_n: Maximum number of encoding symbols generated for any source 560 block 562 n: Number of encoding symbols generated for this source block 564 Algorithm: 566 max_n = floor(B / rate); 568 if (max_n > 2^^m - 1) then return an error ("invalid code rate"); 570 n = floor(k * max_n / B); 572 AT A RECEIVER: 574 Input: 576 B: Extracted from the received FEC OTI 578 max_n: Extracted from the received FEC OTI 580 k: Given by the block partitioning algorithm 582 Output: 584 n 586 Algorithm: 588 n = floor(k * max_n / B); 590 Note that a Reed-Solomon decoder does not need to know the n value. 591 Therefore the receiver part of the "n-algorithm" is not necessary 592 from the Reed-Solomon decoder point of view. Yet a receiving 593 application using the Reed-Solomon FEC scheme will sometimes need to 594 know the n value used by the sender, for instance for memory 595 management optimizations. To that purpose, the FEC OTI carries all 596 the parameters needed for a receiver to execute the above algorithm. 598 7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) and Reed- 599 Solomon Codes over GF(2^^8) 601 In the context of the Under-Specified Small Block Systematic FEC 602 Scheme (FEC Encoding ID 129) [3], this document assigns the FEC 603 Instance ID 0 to the special case of Reed-Solomon codes over GF(2^^8) 604 and no encoding symbol group. 606 The FEC Instance ID 0 uses the Formats and Codes specified in [3]. 608 The FEC Scheme with FEC Instance ID 0 MAY use the algorithm defined 609 in Section 9.1. of [3] to partition the file into source blocks. 610 This FEC Scheme MAY also use another algorithm. For instance the CDP 611 sender may change the length of each source block dynamically, 612 depending on some external criteria (e.g. to adjust the FEC coding 613 rate to the current loss rate experienced by NORM receivers) and 614 inform the CDP receivers of the current block length by means of the 615 EXT_FTI mechanism. This choice is out of the scope of the current 616 document. 618 8. Reed-Solomon Codes Specification for the Erasure Channel 620 Reed-Solomon (RS) codes are linear block codes. They also belong to 621 the class of MDS codes. A [n,k]-RS code encodes a sequence of k 622 source elements defined over a finite field GF(q) into a sequence of 623 n encoding elements, where n is upper bounded by q - 1. The 624 implementation described in this document is based on a generator 625 matrix built from a Vandermonde matrix put into systematic form. 627 Section 8.1 to Section 8.3 specify the [n,k]-RS codes when applied to 628 m-bit elements, and Section 8.4 the use of [n,k]-RS codes when 629 applied to symbols composed of several m-bit elements, which is the 630 target of this specification. 632 8.1. Finite Field 634 A finite field GF(q) is defined as a finite set of q elements which 635 has a structure of field. It contains necessarily q = p^^m elements, 636 where p is a prime number. With packet erasure channels, p is always 637 set to 2. The elements of the field GF(2^^m) can be represented by 638 polynomials with binary coefficients (i.e. over GF(2)) of degree 639 lower or equal than m-1. The polynomials can be associated to binary 640 vectors of length m. For example, the vector (11001) represents the 641 polynomial 1 + x + x^^4. This representation is often called 642 polynomial representation. The addition between two elements is 643 defined as the addition of binary polynomials in GF(2) and the 644 multiplication is the multiplication modulo a given irreducible 645 polynomial over GF(2) of degree m with coefficients in GF(2). Note 646 that all the roots of this polynomial are in GF(2^^m) but not in 647 GF(2). 649 A finite field GF(2^^m) is completely characterized by the 650 irreducible polynomial. The following polynomials are chosen to 651 represent the field GF(2^^m), for m varying from 2 to 16: 653 m = 2, "111" (1+x+x^^2) 655 m = 3, "1101", (1+x+x^^3) 657 m = 4, "11001", (1+x+x^^4) 659 m = 5, "101001", (1+x^^2+x^^5) 661 m = 6, "1100001", (1+x+x^^6) 663 m = 7, "10010001", (1+x^^3+x^^7) 664 m = 8, "101110001", (1+x^^2+x^^3+x^^4+x^^8) 666 m = 9, "1000100001", (1+x^^4+x^^9) 668 m = 10, "10010000001", (1+x^^3+x^^10) 670 m = 11, "101000000001", (1+x^^2+x^^11) 672 m = 12, "1100101000001", (1+x+x^^4+x^^6+x^^12) 674 m = 13, "11011000000001", (1+x+x^^3+x^^4+x^^13) 676 m = 14, "110000100010001", (1+x+x^^6+x^^10+x^^14) 678 m = 15, "1100000000000001", (1+x+x^^15) 680 m = 16, "11010000000010001", (1+x+x^^3+x^^12+x^^16) 682 In order to facilitate the implementation, these polynomials are also 683 primitive. This means that any element of GF(2^^m) can be expressed 684 as a power of a given root of this polynomial. These polynomials are 685 also chosen so that they contain the minimum number of monomials. 687 8.2. Reed-Solomon Encoding Algorithm 689 8.2.1. Encoding Principles 691 Let s = (s_0, ..., s_{k-1}) be a source vector of k elements over 692 GF(2^^m). Let e = (e_0, ..., e_{n-1}) be the corresponding encoding 693 vector of n elements over GF(2^^m). Being a linear code, encoding is 694 performed by multiplying the source vector by a generator matrix, GM, 695 of k rows and n columns over GF(2^^m). Thus: 697 e = s * GM. 699 The definition of the generator matrix completely characterizes the 700 RS code. 702 Let us consider that: n = 2^^m - 1 and: 0 < k <= n. Let us denote by 703 alpha the root of the primitive polynomial of degree m chosen in the 704 list of Section 8.1 for the corresponding value of m. Let us 705 consider a Vandermonde matrix of k rows and n columns, denoted by 706 V_{k,n}, and built as follows: the {i, j} entry of V_{k,n} is v_{i,j} 707 = alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This 708 matrix generates a MDS code. However, this MDS code is not 709 systematic, which is a problem for many networking applications. To 710 obtain a systematic matrix (and code), the simplest solution consists 711 in considering the matrix V_{k,k} formed by the first k columns of 712 V_{k,n}, then to invert it and to multiply this inverse by V_{k,n}. 713 Clearly, the product V_{k,k}^^-1 * V_{k,n} contains the identity 714 matrix I_k on its first k columns, meaning that the first k encoding 715 elements are equal to source elements. Besides the associated code 716 keeps the MDS property. 718 Therefore, the generator matrix of the code considered in this 719 document is: 721 GM = (V_{k,k}^^-1) * V_{k,n} 723 Note that, in practice, the [n,k]-RS code can be shortened to a 724 [n',k]-RS code, where k <= n' < n, by considering the sub-matrix 725 formed by the n' first columns of GM. 727 8.2.2. Encoding Complexity 729 Encoding can be performed by first pre-computing GM and by 730 multiplying the source vector (k elements) by GM (k rows and n 731 columns). The complexity of the pre-computation of the generator 732 matrix can be estimated as the complexity of the multiplication of 733 the inverse of a Vandermonde matrix by n-k vectors (i.e. the last n-k 734 columns of V_{k,n}). Since the complexity of the inverse of a k*k- 735 Vandermonde matrix by a vector is O(k * log^^2(k)), the generator 736 matrix can be computed in 0((n-k)* k * log^^2(k)) operations. When 737 the generator matrix is pre-computed, the encoding needs k operations 738 per repair element (vector-matrix multiplication). 740 Encoding can also be performed by first computing the product s * 741 V_{k,k}^^-1 and then by multiplying the result with V_{k,n}. The 742 multiplication by the inverse of a square Vandermonde matrix is known 743 as the interpolation problem and its complexity is O(k * log^^2 (k)). 744 The multiplication by a Vandermonde matrix, known as the multipoint 745 evaluation problem, requires O((n-k) * log(k)) by using Fast Fourier 746 Transform, as explained in [14]. The total complexity of this 747 encoding algorithm is then O((k/(n-k)) * log^^2(k) + log(k)) 748 operations per repair element. 750 8.3. Reed-Solomon Decoding Algorithm 752 8.3.1. Decoding Principles 754 The Reed-Solomon decoding algorithm for the erasure channel allows 755 the recovery of the k source elements from any set of k received 756 elements. It is based on the fundamental property of the generator 757 matrix which is such that any k*k-submatrix is invertible (see [8]). 758 The first step of the decoding consists in extracting the k*k 759 submatrix of the generator matrix obtained by considering the columns 760 corresponding to the received elements. Indeed, since any encoding 761 element is obtained by multiplying the source vector by one column of 762 the generator matrix, the received vector of k encoding elements can 763 be considered as the result of the multiplication of the source 764 vector by a k*k submatrix of the generator matrix. Since this 765 submatrix is invertible, the second step of the algorithm is to 766 invert this matrix and to multiply the received vector by the 767 obtained matrix to recover the source vector. 769 8.3.2. Decoding Complexity 771 The decoding algorithm described previously includes the matrix 772 inversion and the vector-matrix multiplication. With the classical 773 Gauss-Jordan algorithm, the matrix inversion requires O(k^^3) 774 operations and the vector-matrix multiplication is performed in 775 O(k^^2) operations. 777 This complexity can be improved by considering that the received 778 submatrix of GM is the product between the inverse of a Vandermonde 779 matrix (V_(k,k)^^-1) and another Vandermonde matrix (denoted by V' 780 which is a submatrix of V_(k,n)). The decoding can be done by 781 multiplying the received vector by V'^^-1 (interpolation problem with 782 complexity O( k * log^^2(k)) ) then by V_{k,k} (multipoint evaluation 783 with complexity O(k * log(k))). The global decoding complexity is 784 then O(log^^2(k)) operations per source element. 786 8.4. Implementation for the Packet Erasure Channel 788 In a packet erasure channel, each packet (and symbol(s) since packets 789 contain G >= 1 symbols) is either correctly received or erased. The 790 location of the erased symbols in the sequence of symbols MUST be 791 known. The following specification describes the use of Reed-Solomon 792 codes for generating redundant symbols from the k source symbols and 793 for recovering the source symbols from any set of k received symbols. 795 The k source symbols of a source block are assumed to be composed of 796 S m-bit elements. Each m-bit element corresponds to an element of 797 the finite field GF(2^^m) through the polynomial representation 798 (Section 8.1). If some of the source symbols contain less than S 799 elements, they MUST be virtually padded with zero elements (it can be 800 the case for the last symbol of the last block of the object). 801 However, this padding need not be actually sent with the data to the 802 receivers. 804 The encoding process produces n encoding symbols of size S m-bit 805 elements, of which k are source symbols (this is a systematic code) 806 and n-k are repair symbols (Figure 7). The m-bit elements of the 807 repair symbols are calculated using the corresponding m-bit elements 808 of the source symbol set. A logical j-th source vector, comprised of 809 the j-th elements from the set of source symbols, is used to 810 calculate a j-th encoding vector. This j-th encoding vector then 811 provides the j-th elements for the set encoding symbols calculated 812 for the block. As a systematic code, the first k encoding symbols 813 are the same as the k source symbols and the last n-k repair symbols 814 are the result of the Reed Solomon encoding. 816 Input: k source symbols 818 0 j S-1 819 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 820 | |X| | source symbol 0 821 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 822 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 823 | |X| | source symbol 1 824 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 825 . . . 826 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 827 | |X| | source symbol k-1 828 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 830 * 832 +----------------+ 833 | generator | 834 | matrix | 835 | GM | 836 | (k x n) | 837 +----------------+ 839 | 840 V 842 Output: n encoding symbols (source + repair) 844 0 j S-1 845 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 846 | |X| | enc. symbol 0 847 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 848 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 849 | |X| | enc. symbol 1 850 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 851 . . . 852 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 853 | |Y| | enc. symbol n-1 854 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 855 Figure 7: Packet encoding scheme 857 An asset of this scheme is that the loss of some encoding symbols 858 produces the same erasure pattern for each of the S encoding vectors. 859 It follows that the matrix inversion must be done only once and will 860 be used by all the S encoding vectors. For large S, this matrix 861 inversion cost becomes negligible in front of the S matrix-vector 862 multiplications. 864 Another asset is that the n-k repair symbols can be produced on 865 demand. For instance, a sender can start by producing a limited 866 number of repair symbols and later on, depending on the observed 867 erasures on the channel, decide to produce additional repair symbols, 868 up to the n-k upper limit. Indeed, to produce the repair symbol e_j, 869 where k <= j < n, it is sufficient to multiply the S source vectors 870 with column j of GM. 872 9. Security Considerations 874 Data delivery can be subject to denial-of-service attacks by 875 attackers which send corrupted packets that are accepted as 876 legitimate by receivers. This is particularly a concern for 877 multicast delivery because a corrupted packet may be injected into 878 the session close to the root of the multicast tree, in which case 879 the corrupted packet will arrive at many receivers. This is 880 particularly a concern for the FEC building block because the use of 881 even one corrupted packet containing encoding data may result in the 882 decoding of an object that is completely corrupted and unusable. It 883 is thus RECOMMENDED that source authentication and integrity checking 884 are applied to decoded objects before delivering objects to an 885 application. For example, a SHA-1 hash [5] of an object may be 886 appended before transmission, and the SHA-1 hash is computed and 887 checked after the object is decoded but before it is delivered to an 888 application. Source authentication SHOULD be provided, for example 889 by including a digital signature verifiable by the receiver computed 890 on top of the hash value. It is also RECOMMENDED that a packet 891 authentication protocol such as TESLA [6] be used to detect and 892 discard corrupted packets upon arrival. Furthermore, it is 893 RECOMMENDED that Reverse Path Forwarding checks be enabled in all 894 network routers and switches along the path from the sender to 895 receivers to limit the possibility of a bad agent successfully 896 injecting a corrupted packet into the multicast tree data path. 898 Another security concern is that some FEC information may be obtained 899 by receivers out-of-band in a session description, and if the session 900 description is forged or corrupted then the receivers will not use 901 the correct protocol for decoding content from received packets. To 902 avoid these problems, it is RECOMMENDED that measures be taken to 903 prevent receivers from accepting incorrect session descriptions, 904 e.g., by using source authentication to ensure that receivers only 905 accept legitimate session descriptions from authorized senders. 907 10. IANA Considerations 909 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA 910 registration. For general guidelines on IANA considerations as they 911 apply to this document, see [2]. 913 This document assigns the Fully-Specified FEC Encoding ID 2 under the 914 "ietf:rmt:fec:encoding" name-space to "Reed-Solomon Codes over 915 GF(2^^m)". 917 This document assigns the Fully-Specified FEC Encoding ID 5 under the 918 "ietf:rmt:fec:encoding" name-space to "Reed-Solomon Codes over 919 GF(2^^8)". 921 This document assigns the FEC Instance ID 0 scoped by the Under- 922 Specified FEC Encoding ID 129 to "Reed-Solomon Codes over GF(2^^8)". 923 More specifically, under the "ietf:rmt:fec:encoding:instance" sub- 924 name-space that is scoped by the "ietf:rmt:fec:encoding" called 925 "Small Block Systematic FEC Codes", this document assigns FEC 926 Instance ID 0 to "Reed-Solomon Codes over GF(2^^8)". 928 11. Acknowledgments 930 The authors want to thank Brian Adamson for his valuable comments. 931 The authors also want to thank Luigi Rizzo for comments on the 932 subject and for the design of the reference Reed-Solomon codec. 934 12. References 936 12.1. Normative References 938 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 939 Levels", RFC 2119. 941 [2] Watson, M., Luby, M., and L. Vicisano, "Forward Error 942 Correction (FEC) Building Block", 943 draft-ietf-rmt-fec-bb-revised-07.txt (work in progress), 944 April 2007. 946 [3] Watson, M., "Basic Forward Error Correction (FEC) Schemes", 947 draft-ietf-rmt-bb-fec-basic-schemes-revised-03.txt (work in 948 progress), February 2007. 950 [4] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., 951 and J. Crowcroft, "The Use of Forward Error Correction (FEC) in 952 Reliable Multicast", RFC 3453, December 2002. 954 [5] "HMAC: Keyed-Hashing for Message Authentication", RFC 2104, 955 February 1997. 957 [6] "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): 958 Multicast Source Authentication Transform Introduction", 959 RFC 4082, June 2005. 961 12.2. Informative References 963 [7] Rizzo, L., "Reed-Solomon FEC codec (revised version of July 964 2nd, 1998), available at 965 http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz, and 966 mirrored at http://planete-bcast.inrialpes.fr/", July 1998. 968 [8] Mac Williams, F. and N. Sloane, "The Theory of Error Correcting 969 Codes", North Holland, 1977 . 971 [9] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, 972 "Raptor Forward Error Correction Scheme", 973 draft-ietf-rmt-bb-fec-raptor-object-08 (work in progress), 974 April 2007. 976 [10] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity 977 Check (LDPC) Forward Error Correction", 978 draft-ietf-rmt-bb-fec-ldpc-06.txt (work in progress), 979 May 2007. 981 [11] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered 982 Coding (ALC) Protocol Instantiation", 983 draft-ietf-rmt-pi-alc-revised-04.txt (work in progress), 984 February 2007. 986 [12] Adamson, B., Bormann, C., Handley, M., and J. Macker, 987 "Negative-acknowledgment (NACK)-Oriented Reliable Multicast 988 (NORM) Protocol", draft-ietf-rmt-pi-norm-revised-04.txt (work 989 in progress), March 2007. 991 [13] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, 992 "FLUTE - File Delivery over Unidirectional Transport", 993 draft-ietf-rmt-flute-revised-03.txt (work in progress), 994 January 2007. 996 [14] Gohberg, I. and V. Olshevsky, "Fast algorithms with 997 preprocessing for matrix-vector multiplication problems", 998 Journal of Complexity, pp. 411-427, vol. 10, 1994 . 1000 Authors' Addresses 1002 Jerome Lacan 1003 ENSICA/LAAS-CNRS 1004 1, place Emile Blouin 1005 Toulouse 31056 1006 France 1008 Email: jerome.lacan@ensica.fr 1009 URI: http://dmi.ensica.fr/auteur.php3?id_auteur=5 1011 Vincent Roca 1012 INRIA 1013 655, av. de l'Europe 1014 Inovallee; Montbonnot 1015 ST ISMIER cedex 38334 1016 France 1018 Email: vincent.roca@inrialpes.fr 1019 URI: http://planete.inrialpes.fr/~roca/ 1021 Jani Peltotalo 1022 Tampere University of Technology 1023 P.O. Box 553 (Korkeakoulunkatu 1) 1024 Tampere FIN-33101 1025 Finland 1027 Email: jani.peltotalo@tut.fi 1028 URI: http://atm.tut.fi/mad 1030 Sami Peltotalo 1031 Tampere University of Technology 1032 P.O. Box 553 (Korkeakoulunkatu 1) 1033 Tampere FIN-33101 1034 Finland 1036 Email: sami.peltotalo@tut.fi 1037 URI: http://atm.tut.fi/mad 1039 Full Copyright Statement 1041 Copyright (C) The IETF Trust (2007). 1043 This document is subject to the rights, licenses and restrictions 1044 contained in BCP 78, and except as set forth therein, the authors 1045 retain all their rights. 1047 This document and the information contained herein are provided on an 1048 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1049 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1050 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1051 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1052 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1053 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1055 Intellectual Property 1057 The IETF takes no position regarding the validity or scope of any 1058 Intellectual Property Rights or other rights that might be claimed to 1059 pertain to the implementation or use of the technology described in 1060 this document or the extent to which any license under such rights 1061 might or might not be available; nor does it represent that it has 1062 made any independent effort to identify any such rights. Information 1063 on the procedures with respect to rights in RFC documents can be 1064 found in BCP 78 and BCP 79. 1066 Copies of IPR disclosures made to the IETF Secretariat and any 1067 assurances of licenses to be made available, or the result of an 1068 attempt made to obtain a general license or permission for the use of 1069 such proprietary rights by implementers or users of this 1070 specification can be obtained from the IETF on-line IPR repository at 1071 http://www.ietf.org/ipr. 1073 The IETF invites any interested party to bring to its attention any 1074 copyrights, patents or patent applications, or other proprietary 1075 rights that may cover technology that may be required to implement 1076 this standard. Please address the information to the IETF at 1077 ietf-ipr@ietf.org. 1079 Acknowledgment 1081 Funding for the RFC Editor function is provided by the IETF 1082 Administrative Support Activity (IASA).