idnits 2.17.1 draft-ietf-rmt-fec-bb-revised-02.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 17. -- Found old boilerplate from RFC 3978, Section 5.5 on line 1078. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1055. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1062. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1068. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 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 18, 2005) is 6757 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) == Missing Reference: '0' is mentioned on line 938, but not defined == Missing Reference: '255' is mentioned on line 954, but not defined == Missing Reference: '128' is mentioned on line 954, but not defined == Missing Reference: '127' is mentioned on line 938, but not defined == Unused Reference: '5' is defined on line 994, but no explicit reference was found in the text ** Obsolete normative reference: RFC 2434 (ref. '2') (Obsoleted by RFC 5226) -- Obsolete informational reference (is this intentional?): RFC 3452 (ref. '3') (Obsoleted by RFC 5052, RFC 5445) -- Obsolete informational reference (is this intentional?): RFC 3926 (ref. '8') (Obsoleted by RFC 6726) Summary: 4 errors (**), 0 flaws (~~), 7 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Reliable Multicast M. Watson 3 Internet-Draft M. Luby 4 Expires: April 21, 2006 Digital Fountain 5 L. Vicisano 6 Cisco Systems, Inc. 7 October 18, 2005 9 Forward Error Correction (FEC) Building Block 10 draft-ietf-rmt-fec-bb-revised-02 12 Status of this Memo 14 By submitting this Internet-Draft, each author represents that any 15 applicable patent or other IPR claims of which he or she is aware 16 have been or will be disclosed, and any of which he or she becomes 17 aware will be disclosed, in accordance with Section 6 of BCP 79. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as Internet- 22 Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt. 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html. 35 This Internet-Draft will expire on April 21, 2006. 37 Copyright Notice 39 Copyright (C) The Internet Society (2005). 41 Abstract 43 This document describes how to use Forward Error Correction (FEC) 44 codes to efficiently provide and/or augment reliability for data 45 transport. This document defines a framework for the definition of 46 the information that needs to be communicated in order to use an FEC 47 code for delivering content, in addition to the encoded data itself, 48 and for definition of formats and codes for communcation of that 49 information. Both information communicated with the encoded data 50 itself and information that needs to be communicated 'out-of-band' 51 are considered. The procedures for specifying new FEC codes, 52 defining the information communication requirements associated with 53 those codes and registering them with the Internet Assigned Numbers 54 Authority (IANA) are also described. The requirements on Content 55 Delivery Protocols which wish to use FEC codes defined within this 56 framework are also defined. The companion document titled, "The Use 57 of Forward Error Correction (FEC) in Reliable Multicast" describes 58 some applications of FEC codes for delivering content. 60 Table of Contents 62 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 63 2. Definitions/Abbreviations . . . . . . . . . . . . . . . . . . 4 64 3. Requirements notation . . . . . . . . . . . . . . . . . . . . 5 65 4. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 6 66 5. Applicability Statement . . . . . . . . . . . . . . . . . . . 8 67 6. Functionality . . . . . . . . . . . . . . . . . . . . . . . . 9 68 6.1. FEC Schemes . . . . . . . . . . . . . . . . . . . . . . . 10 69 6.2. FEC Object Transmission Information . . . . . . . . . . . 12 70 6.2.1. Transport of FEC Object Transmission Information . . . 13 71 6.2.2. Opacity of FEC Object Transmission Information . . . . 14 72 6.2.3. Mandatory FEC Object Transmission Information 73 elements . . . . . . . . . . . . . . . . . . . . . . . 14 74 6.2.4. Common FEC Object Transmission Information elements . 15 75 6.2.5. Scheme-specific FEC Object Transmission 76 Information element . . . . . . . . . . . . . . . . . 15 77 6.3. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 16 78 7. FEC scheme specifications . . . . . . . . . . . . . . . . . . 17 79 8. CDP specifications . . . . . . . . . . . . . . . . . . . . . . 20 80 9. Common algorithms . . . . . . . . . . . . . . . . . . . . . . 21 81 9.1. Block partitioning algorithm . . . . . . . . . . . . . . . 21 82 9.1.1. First Step . . . . . . . . . . . . . . . . . . . . . . 21 83 9.1.2. Second step . . . . . . . . . . . . . . . . . . . . . 22 84 10. Requirements from other building blocks . . . . . . . . . . . 23 85 11. Security Considerations . . . . . . . . . . . . . . . . . . . 24 86 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25 87 12.1. Explicit IANA Assignment Guidelines . . . . . . . . . . . 25 88 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27 89 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28 90 14.1. Normative References . . . . . . . . . . . . . . . . . . . 28 91 14.2. Informative References . . . . . . . . . . . . . . . . . . 28 92 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 29 93 Intellectual Property and Copyright Statements . . . . . . . . . . 30 95 1. Introduction 97 This document describes how to use Forward Error Correction (FEC) 98 codes to provide support for reliable delivery of content within the 99 context of a Content Delivery Protocol (CDP). This document 100 describes a building block as defined in [10]. This document is a 101 product of the IETF RMT WG and follows the general guidelines 102 provided in [8]. 104 The purpose of this building block is to define a framework for 105 forward error correction such that: 107 1. CDPs can be designed to operate with a range of different FEC 108 codes/schemes, without needing to know details of the specific 109 FEC code/scheme that may be used 111 2. FEC schemes can be designed to operate with a range of different 112 CDPs, without needing to know details of the specific CDPs 114 Note that a 'CDP' in the context of this document may consist of 115 several distinct protocol mechanisms and may support any kind of 116 application requiring reliable transport - for example object 117 delivery and streaming applications. 119 This document also provides detailed guidelines on how to write an 120 RFC for an FEC scheme corresponding to a new FEC Encoding ID (for 121 both Fully-Specified and Under-Specified FEC Schemes). 123 2. Definitions/Abbreviations 125 Object: An ordered sequence of bytes to be transferred by the 126 transport protocol. For example, a file or stream. 128 Symbol: A unit of data processed by the Forward Error Correction 129 code. A symbol is always considered as a unit i.e. it is either 130 completely received or completely lost. 132 Source symbol: A symbol containing information from the original 133 object. 135 Repair symbol: A symbol containing information generated by the FEC 136 code which can be used to recover lost source symbols. 138 Encoding symbol: A source symbol or a repair symbol. 140 Encoder: The FEC scheme specific functions required to transform a 141 object into FEC encoded data. i.e. the functions that produce 142 repair symbols using source symbols. 144 Decoder: The FEC scheme specific functions required to transform 145 received FEC encoded data into a copy of the original object 147 Receiver: A system supporting the receiving functions of a CDP and 148 FEC scheme according to this specification 150 Sender: A system supporting the sending functions of a CDP and FEC 151 scheme according to this specification 153 Source Block: A part of the object formed from a subset of the 154 object's source symbols 156 CDP: Content Delivery Protocol 158 FEC: Forward Error Correction 160 3. Requirements notation 162 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 163 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 164 document are to be interpreted as described in [1]. 166 4. Rationale 168 An FEC code is a valuable basic component of any CDP that is to 169 provide reliable delivery of an object. Using FEC codes is effective 170 in the context of IP multicast and reliable delivery because FEC 171 encoding symbols can be useful to all receivers for reconstructing an 172 object even when the receivers have received different encoding 173 symbols. Furthermore, FEC codes can ameliorate or even eliminate the 174 need for feedback from receivers to senders to request retransmission 175 of lost packets. 177 Central to this document is the concept of an 'FEC Scheme'. An FEC 178 scheme defines ancilliary information and procedures which, combined 179 with an FEC code specification, fully define how the FEC code can be 180 used with CDPs. An FEC scheme may be associated with a single 181 standardised FEC code (A 'Fully-Specified' FEC scheme) or may be 182 applicable to many FEC codes (An 'Under-Specified' FEC scheme). 184 This document describes a framework for the definition of FEC 185 schemes. Definition of actual FEC schemes is outside the scope of 186 this document. This document also defines requirements for reliable 187 CDPs that make use of FEC schemes. Any such CDP which is compliant 188 to the requirements specified in this document can make use of any 189 FEC scheme which is defined within the framework described here. 190 Note that FEC schemes may place restrictions on the types of CDP they 191 are intended to be used with. For example, some FEC schemes may be 192 specific to particular types of application, such as file delivery or 193 streaming. 195 The goal of the FEC building block is to describe functionality 196 directly related to FEC codes that is common to all reliable CDPs and 197 to all FEC schemes, and to leave out any additional functionality 198 that is specific to particular CDPs or particular FEC schemes. The 199 primary functionality described in this document that is common to 200 all such CDPs that use FEC codes is the definition and transport of 201 three kinds of information from sender to receiver(s): encoding 202 symbols themselves, anciliary information associated with encoding 203 symbols (or groups of such symbols, such as the group of symbols in a 204 single packet, or the group of symbols related to a single source 205 block) and anciliary information associated with the whole object 206 being transfered. It is important to note that this ancilliary 207 information is only required by the receiver if one or more of the 208 encoding symbols to which it relates are received. 210 This document for example does not describe how receivers may request 211 transmission of particular encoding symbols for an object. This is 212 because although there are CDPs where requests for transmission are 213 of use, there are also CDPs that do not require such requests. 215 The companion document [4] should be consulted for a full explanation 216 of the benefits of using FEC codes for reliable content delivery 217 using IP multicast. FEC codes are also useful in the context of 218 unicast, and thus the scope and applicability of this document is not 219 limited to IP multicast. 221 5. Applicability Statement 223 The FEC building block does not provide any support for congestion 224 control. Any complete multicast CDP MUST provide congestion control 225 that conforms to [6], and thus this MUST be provided by another 226 building block when the FEC building block is used in a CDP. 228 A more complete description of the applicability of FEC codes can be 229 found in the companion document [4]. 231 6. Functionality 233 This section describes FEC information that is either to be sent in 234 packets also containing FEC encoding symbols or 'out-of-band'. The 235 FEC information is associated with transmission of encoding symbols 236 related to a particular object. There are three classes of packets 237 that may contain FEC information: data packets, session-control 238 packets and feedback packets. They generally contain different kinds 239 of FEC information. Note that some CDPs may not use session-control 240 or feedback packets. 242 Data packets may sometimes serve as session-control packets as well; 243 both data and session-control packets generally travel downstream 244 from the sender towards receivers and are sent to a multicast channel 245 or to a specific receiver using unicast. Session-control packets may 246 additionally travel upstream from receivers to senders. 248 As a general rule, feedback packets travel upstream from receivers to 249 the sender. Sometimes, however, they might be sent to a multicast 250 channel or to another receiver or to some intermediate node or 251 neighboring router that provides recovery services. 253 This document specifies the FEC information that must be carried in 254 data packets and the other FEC information that must be communicated 255 from sender to receiver(s) either out-of-band or in data packets. 256 This document does not specify out-of-band methods nor does it 257 specify the way out-of-band FEC information is associated with FEC 258 information carried in data packets. These methods must be specified 259 in CDP specifications that use this FEC building block. 261 FEC information is classified as follows: 263 1. FEC information associated with an object 265 This is information that is essential for the FEC decoder to 266 decode a specific object. An example of this information is the 267 identity of the FEC scheme that is being used to encode the 268 object, in the form of the FEC Encoding ID. The FEC Encoding ID 269 is described further below. This information may also include 270 FEC scheme-specific parameters for the FEC decoder. 272 2. FEC information associated with specific encoding symbols for an 273 object 275 This is information which is associated with one or more encoding 276 symbols and is thus needed by the decoder whenever one or more of 277 those encoding symbols have been received. Depending on the FEC 278 scheme, information may be associated with individual symbols 279 and/or with groups of symbols. One common such grouping is the 280 group of symbols included within a single packet. Many FEC 281 schemes also segment the object being encoded into multiple 282 'source blocks', each of which is processed independently for FEC 283 purposes. Information about each source block is another type of 284 information associated with a group of encoding symbols, this 285 time the group of symbols which are related to a given source 286 block. 288 Two 'containers' are provided for communicating the FEC information 289 described above, but there is not necessarily a one-to-one 290 correspondance between the class of FEC information and the mechanism 291 used. The two mechanisms are: 293 a. FEC Object Transmission Information 295 CDPs must provide a reliable mechanism for communicating certain 296 FEC information from sender to receiver(s). This information is 297 known as 'FEC Object Transmission Information' and its contents 298 depend on the particular FEC scheme. It includes all information 299 of the first class above and may include information of the 300 second class. The FEC Object Transmission Information can be 301 sent to a receiver within the data packet headers, within session 302 control packets, or by some other means. 304 b. FEC Payload ID 306 CDPs must provide a mechanism for communicating information which 307 identifies (for FEC purposes) the encoding symbols carried by a 308 packet. This information is known as the FEC Payload ID and its 309 contents depend on the FEC scheme. It includes only information 310 of the second class above. A data packet that carries encoding 311 symbols MUST include an FEC Payload ID. 313 6.1. FEC Schemes 315 Two types of FEC scheme are defined by this document: 'Fully- 316 Specified' FEC schemes and 'Under-Specified' FEC schemes. An FEC 317 scheme is a Fully-Specified FEC scheme if the encoding scheme is 318 formally and Fully-Specified, in a way that independent implementors 319 can implement both encoder and decoder from a specification that is 320 an IETF RFC. 322 It is possible that an FEC scheme may not be a Fully-Specified FEC 323 scheme, because either a specification is simply not available or a 324 party exists that owns the encoding scheme and is not willing to 325 disclose the algorithm or specification. We refer to such an FEC 326 encoding scheme as an Under-Specified FEC scheme. 328 FEC schemes are identified by an FEC Encoding ID, which is an integer 329 identifier assigned by IANA. The FEC Encoding ID allows receivers to 330 select the appropriate FEC decoder. The value of the FEC Encoding ID 331 MUST be the same for all transmission of encoding symbols related to 332 a particular object, but MAY vary across different transmissions of 333 encoding symbols about different objects, even if transmitted to the 334 same set of multicast channels and/or using a single upper-layer 335 session. 337 The FEC Instance ID is an integer value that identifies a specific 338 instance of an Under-Specified FEC scheme. This value is not used 339 for Fully-Specified FEC schemes. The FEC Instance ID is scoped by 340 the FEC Encoding ID, and FEC Instance ID values are subject to IANA 341 registration. 343 The FEC Encoding ID for Fully-Specified FEC Schemes and both the FEC 344 Encoding ID and FEC Instance ID for Under-Specified FEc Schemes are 345 essential for the decoder to decode an object and thus are part of 346 the FEC Object Transmission Information. 348 The following requirements apply to all FEC schemes, whether Fully- 349 Specified or Under-Specified: 351 o The type, semantics and an encoding format for the FEC Payload ID 352 and the FEC Object Transmission Information MUST be defined. 354 o A value for the FEC Encoding ID MUST be reserved and associated 355 with the types, semantics and encoding format of the FEC Payload 356 ID and the FEC Object Transmission Information. 358 The specification for an Under-Specified FEC Scheme MAY allocate a 359 sub-field within the Scheme-specific FEC Object Transmission 360 Information element which is for instance-specific information. Each 361 specific instance of the Under-Specified FEC Scheme may then use this 362 field in an instance-specific way. The FEC scheme should define the 363 scheme-specific FEC Object Transmission Information element in such a 364 way that receivers that do not support the received FEC Instance ID 365 can still parse and interpret the scheme-specific FEC Object 366 Transmission Information element with the exception of the instance- 367 specific field. 369 An already defined Under-Specified FEC Scheme (i.e. FEC Encoding ID 370 value) MUST be reused if the associated FEC Payload ID and FEC Object 371 Transmission Information have the required fields and encoding 372 formats for a new Under-Specified FEC scheme instance. 374 An instance of an Under-Specified FEC scheme is fully identified by 375 the tuple (FEC Encoding ID, FEC Instance ID). The tuple MUST 376 identify a single scheme instance that has at least one 377 implementation. The party that owns this tuple MUST be able to 378 provide information on how to obtain the Under-Specified FEC scheme 379 instance identified by the tuple, e.g., a pointer to a publicly 380 available reference-implementation or the name and contacts of a 381 company that sells it, either separately or embedded in another 382 product. 384 This specification reserves the range 0-127 for the values of FEC 385 Encoding IDs for Fully-Specified FEC schemes and the range 128-255 386 for the values of Under-Specified FEC schemes. 388 6.2. FEC Object Transmission Information 390 The FEC Object Transmission Information contains information which is 391 essential to the decoder in order to decode the encoded object. It 392 may also contain information which is required to decode certain 393 groups of encoding symbols, for example individual Source Blocks 394 within the object. This information is communicated reliably by the 395 CDP to the receiver(s) as described in Section 8. 397 The FEC Object Transmission Information may consist of several 398 elements and each element may be one of three types, as follows: 400 Mandatory: These elements are defined in this specification and are 401 each mandatory for at least one of the two types of FEC Scheme. 402 Each FEC scheme specifies how the values of the Mandatory FEC 403 Object Transmission Information elements are determined and each 404 CDP specifies how this information is encoded and reliably 405 communicated to the receiver(s). The Mandatory FEC Object 406 Transmission Information includes the identification of the FEC 407 Scheme, which is needed by the receiver to determine whether it 408 supports the FEC Scheme. 410 Common: These elements are defined in this specification and are 411 optional to be used by an FEC scheme. Each FEC scheme specifies 412 which of the Common FEC Object Transmission Information elements 413 it uses and how the values of these elements are determined. 415 Scheme-specific: An FEC scheme may specify a single Scheme-specific 416 FEC Object Transmission Information element. The FEC scheme 417 specifies the type, semantics and encoding format of the Scheme- 418 specific FEC Object Transmission Information element. The 419 resulting byte-string is known as the "encoded Scheme-specific FEC 420 Object Transmission Information". Each CDP specifies how the 421 encoded Scheme-specific FEC Object Transmission is communicated 422 reliably to the receiver(s) i.e. exactly where it shall be carried 423 within packets of the CDP. Note that although from the point of 424 view of this specification and of CDPs there is only a single 425 Scheme-specific FEC Object Transmission Information element, the 426 FEC scheme may specify this element to contain multiple distinct 427 pieces of information. 429 Each FEC scheme specifies an encoding format for the Common and 430 Scheme-specific FEC Object Transmission Information. Each CDP must 431 specify at least one of the following: 433 1. A means to reliably communicate the Common FEC Object 434 Transmission Information elements to the receiver(s) using the 435 encoding format defined by the FEC scheme. 437 2. An alternative, CDP specific, encoding format for each of the 438 Common FEC Object Transmission Information elements. 440 The Mandatory and Common FEC Object Transmission Information elements 441 are defined in the sections below. 443 6.2.1. Transport of FEC Object Transmission Information 445 It is the responsibility of the CDP to reliably transport the FEC 446 Object Transmission Information to the receiver(s). 448 It is important to note that the encoding format of the Mandatory FEC 449 Object Transmission Information elements (The FEC Encoding ID) is 450 defined by the CDP. This is so that the receiver can identify the 451 FEC Scheme to be used for interpreting the remaining FEC Object 452 Transmission Information elements. All CDPs must define encoding 453 formats for the Mandatory FEC Object Transmission Information 454 element. 456 Common FEC Object Transmission Information elements can be 457 transported in two different ways: (a) the FEC Scheme defines an 458 encoding format for the Common FEC Object Transmission Information 459 elements that it uses and the CDP transports this encoded data block, 460 or (b) the CDP defines an encoding format for each Common FEC Object 461 Transmission Information element and transports the information in 462 this format. 464 An FEC Scheme MUST define an encoding format for the Common FEC 465 Object Transmission Information elements that it uses. The resulting 466 byte string is known as the "encoded Common FEC Object Transmission 467 Information". A CDP MAY define individual encoding formats for each 468 of the Common FEC Object Transmission Information elements. The CDP 469 determines which way the Common FEC Object Transmission Information 470 elements shall be transported, (a) or (b). Note that a CDP may 471 provide support for one or both options. 473 In the case that the CDP uses the encoding format specified by the 474 FEC scheme then it may simply concatenate the encoded Common FEC 475 Object Transmission Information and the encoded Scheme-specific FEC 476 Object Transmission Information or it may carry each in a seperate 477 field or wrapper within the CDP. In the former case, the 478 concatenated byte-string is known as the encoded FEC Object 479 Transmission Information. The FEC scheme must define the encoding 480 format for the Common FEC Object Transmission Information elements 481 that it uses in such a way that the length of each element is either 482 fixed or can be determined from the encoded data itself. 484 The encoding format of the Scheme-specific FEC Object Transmission 485 Information element is defined by the FEC scheme. CDPs specify only 486 how the resulting byte sequence is communicated. As with the 487 encoding format for the Common FEC Oject Transmission Information 488 elements the length of the Scheme-specific FEC Object Transmission 489 Information must either be fixed or it must be possible to determine 490 the length from the encoded data itself. 492 6.2.2. Opacity of FEC Object Transmission Information 494 The Scheme-specific FEC Object Transmission Information element is 495 opaque to the CDP in the sense that inspecting the contents of this 496 element can only be done if FEC scheme-specific logic is included in 497 the CDP. 499 The encoding formats defined by the FEC scheme for the Common FEC 500 Object Transmission Information elements are also opaque to the CDP 501 in the same sense. 503 The encoding formats defined by the CDP for the Common FEC Object 504 Transmission Information elements are not opaque in this sense, 505 although it must be considered that different FEC Schemes may use 506 different combinations of the Common FEC Object Transmission 507 Information elements. 509 6.2.3. Mandatory FEC Object Transmission Information elements 511 The Mandatory FEC Object Transmission Information element is: 513 FEC Encoding ID: an integer between 0 and 255 inclusive identifying a 514 specific FEC scheme (Fully-Specified or Under-Specified.) 516 6.2.4. Common FEC Object Transmission Information elements 518 The Common FEC Object Transmission Information elements are described 519 below. Note that with the exception of the FEC Instance ID, this 520 specification does not provide complete definitions of these fields. 521 Instead only aspects of the abstract type are defined. The precise 522 type and semantics are defined for each FEC scheme in the FEC scheme 523 specification. 525 FEC Instance ID: an integer between 0 and 65535 inclusive identifying 526 an instance of an Under-specifed FEC scheme 528 Transfer-Length: a non-negative integer indicating the length of the 529 object in bytes 531 Encoding-Symbol-Length: a non-negative integer indicating the length 532 of each encoding symbol in bytes 534 Maximum-Source-Block-Length: a non-negative integer indicating the 535 maximum number of source symbols in a source block 537 Max-Number-of-Encoding-Symbols: a non-negative integer indicating the 538 maximum number of encoding symbols (i.e. source plus repair 539 symbols in the case of a systematic code) 541 The FEC Instance ID MUST be used by all Under-specified FEC schemes 542 and MUST NOT be used by Fully-specified FEC Schemes. 544 FEC Schemes define the precise type of those of the above elements 545 that they use and in particular may restrict the value range of each 546 element. FEC Schemes also define an encoding format for the subset 547 of the above elements that they use. CDPs may also provide an 548 encoding format for each element in which case this encoding format 549 MUST be capable of representing values up to (2^^16)-1 in the case of 550 the FEC Instance ID, (2^^48)-1 in the case of the Transfer-Length and 551 up to (2^^32)-1 for the other elements. CDPs may additionally or 552 alternatively provide a mechanism to transport the encoded Common FEC 553 Object Transmission information defined by the FEC scheme. For 554 example, FLUTE [8] specifies an XML-based encoding format for these 555 elements, but can also transport FEC scheme-specific encoding formats 556 within the EXT-FTI LCT header extension. 558 6.2.5. Scheme-specific FEC Object Transmission Information element 560 The Scheme-specific FEC Object Transmission Information element may 561 be used by an FEC Scheme to communicate information which is 562 essential to the decoder which cannot adequately be represented 563 within the Mandatory or Common FEC Object Transmission Information 564 elements. 566 From the point of view of a CDP, the Scheme-specific FEC Object 567 Transmission Information element is an opaque, variable length, byte 568 string. The FEC Scheme defines the structure of this byte string, 569 which may contain multiple distinct elements. 571 6.3. FEC Payload ID 573 The FEC Payload ID contains information which indicates to the FEC 574 decoder the relationships between the encoding symbols carried by a 575 particular packet and the FEC encoding transformation. For example 576 if the packet carries source symbols then the FEC Payload ID 577 indicates which source symbols of the object are carried by the 578 packet. If the packet carries repair symbols, then the FEC Payload 579 ID indicates how those repair symbols were constructed from the 580 object. 582 The FEC Payload ID may also contain information about larger groups 583 of encoding symbols of which those contained in the packet are part. 584 For example, the FEC Payload ID may contain information about the 585 source block the symbols are related to. 587 The FEC Payload ID for a given packet is essential to the decoder if 588 and only if the packet itself is received. Thus it must be possible 589 to obtain the FEC Payload ID from the recieved packet. Usually, the 590 FEC Payload ID is simply carried explicitly as a separate field 591 within each packet. Some FEC schemes may specify means for deriving 592 the relationship between the carried encoding symbols and the object 593 implicitly from other information within the packet, such as protocol 594 headers already present. Such FEC schemes could obviously only be 595 used with CDPs which provided the appropriate information from which 596 the FEC Payload ID could be derived. 598 The encoding format of the FEC Payload ID is defined by the FEC 599 Scheme. CDPs specify how the FEC Payload ID is carried within data 600 packets i.e. the position of the FEC Payload ID within the CDP packet 601 format and the how it is associated with encoding symbols. 603 FEC schemes for systematic FEC codes may specify two FEC Payload ID 604 formats, one for packets carrying only source symbols and another for 605 packets carrying at least one repair symbol. CDPs must include an 606 indication of which of the two FEC Payload ID formats is included in 607 each packet if they wish to support such FEC Schemes. 609 7. FEC scheme specifications 611 A specification for a new FEC scheme MUST include the following 612 things: 614 1. The FEC Encoding ID value that uniquely identifies the FEC 615 scheme. This value MUST be registered with IANA as described in 616 Section 12. 618 2. The type, semantics and encoding format of one or two FEC Payload 619 IDs. Where two FEC Payload ID formats are specified, then the 620 FEC scheme MUST be a systematic FEC code and one FEC Payload ID 621 format MUST be designated for use with packets carrying only 622 source symbols and the other FEC Payload ID format MUST be 623 designated for use with packets carrying at least one repair 624 symbol. 626 3. The type and semantics of the FEC Object Transmission 627 Information. The FEC Scheme MAY define additional restrictions 628 on the type (including value range) of the Common FEC Object 629 Transmission Information elements. 631 4. An encoding format for the Common FEC Object Transmission 632 Information elements used by the FEC Scheme. 634 Fully-Specified FEC schemes MUST further specify: 636 1. A full specification of the FEC code. 638 This specification MUST precisely define the valid FEC Object 639 Transmission Information values, the valid FEC Payload ID values 640 and the valid packet payload sizes for any given object (where 641 packet payload refers to the space - not necessarily contiguous - 642 within a packet dedicated to carrying encoding symbol bytes). 644 Furthermore, given an object, valid values for each of the FEC 645 Object Transmission Information elements used by the FEC Scheme, 646 a valid FEC Payload ID value and a valid packet payload size, the 647 specification MUST uniquely define the values of the encoding 648 symbol bytes to be included in the packet payload of a packet 649 with the given FEC Payload ID value. 651 A common and simple way to specify the FEC code to the required 652 level of detail is to provide a precise specification of an 653 encoding algorithm which, given an object, valid values for each 654 of the FEC Object Transmission Information elements used by the 655 FEC Scheme for the object, a valid FEC Payload ID and packet 656 payload length as input produces the exact value of the encoding 657 symbol bytes as output. 659 2. A description of practical encoding and decoding algorithms. 661 This description need not be to the same level of detail as for 662 (1) above, however it must be sufficient to demonstrate that 663 encoding and decoding of the code is both possible and practical. 665 FEC scheme specifications MAY additionally define the following: 667 1. Type, semantics and encoding format of a Scheme-specific FEC 668 Object Transmission Information element. 670 Note that if an FEC sheme does not define a Scheme-specific FEC 671 Object Transmission Information then such an element MUST NOT be 672 introduced in future versions of the FEC Scheme. This requirement is 673 included to ensure backwards-compatibility of CDPs designed to 674 support only FEC Schemes which do not use the Scheme-specific FEC 675 Object Transmission Information element. 677 Whenever an FEC scheme specification defines an 'encoding format' for 678 an element, this must be defined in terms of a sequence of bytes 679 which can be embedded within a protocol. The length of the encoding 680 format MUST either be fixed or it must be possible to derive the 681 length from examining the encoded bytes themselves. For example, the 682 initial bytes may include some kind of length indication. 684 FEC schemes SHOULD make use of the Common FEC Object Transmission 685 Information elements in preference to including infomation in a 686 Scheme-specific FEC Object Transmission Information element. 688 FEC scheme specifications SHOULD use the terminology defined in this 689 document and SHOULD follow the following format: 691 1. Introduction 694 696 2. Formats and Codes 698 2.1 FEC Payload ID(s) 701 2.2 FEC Object Transmission Information 703 2.2.1 Mandatory 706 2.2.2 Common 710 2.2.3 Scheme-Specific 714 3. Procedures 719 4. FEC code specification (for Fully-Specified FEC schemes 720 only) 722 Specifications MAY include additional sections, for example, 723 examples. 725 Each FEC scheme MUST be specified independently of all other FEC 726 schemes; for example, in a separate specification or a completely 727 independent section of larger specification. 729 8. CDP specifications 731 A specification for a CDP that uses this building block MUST include 732 the following things: 734 1. Definitions of an encoding formats for the Mandatory FEC Object 735 Transmission Information element. 737 2. A means to reliably communicate the Mandatory FEC Object 738 Transmission Information element from sender to receiver(s) using 739 the encoding format defined in (1). 741 3. Means to reliably communicate the Common FEC Object Transmission 742 Information element from sender to receiver(s) using either or 743 both of (a) the encoding format defined by the FEC Scheme or (b) 744 encoding formats defined by the CDP 746 4. A means to reliably communicate the Scheme-specific FEC Object 747 Transmission Information element from sender to receiver(s) using 748 the encoding format of the Scheme-specific FEC Object 749 Transmission Information element defined by the FEC scheme. 751 5. A means to communicate the FEC Payload ID in association with a 752 data packet. Note that the encoding format of the FEC Payload ID 753 is defined by the FEC Scheme. 755 If option (b) of (3) above is used, then the CDP MUST specify an 756 encoding format for the Common FEC Object Transmission Information 757 elements. 759 CDPs MAY additionally specify the following things: 761 1. A means to indicate whether the FEC Payload ID within a packet is 762 encoded according to the format for packets including only source 763 symbols or according to the format for packets including at least 764 one repair symbol. 766 9. Common algorithms 768 This section describes certain algorithms which are expected to be 769 commonly required by FEC schemes or by CDPs. FEC Schemes and CDPs 770 SHOULD use these algorithms in preference to scheme or protocol 771 specific algorithms where appropriate. 773 9.1. Block partitioning algorithm 775 This algorithm computes a partitioning of a object into source blocks 776 so that all source blocks are as close to being equal length as 777 possible. A first number of source blocks are of the same larger 778 length, and the remaining second number of source blocks of the same 779 smaller length. 781 This algorithm is described in two steps, the second of which may be 782 useful in itself as an independent algorithm in some cases. In the 783 first step, the number of source symbols (T) and the number of source 784 blocks (N) are derived from the Object transfer length (L), Maximum 785 Source Block Length (B) and Symbol Length (E). 787 In the second step, the partitioning of the object is derived from 788 the number of source symbols (T) and the number of source blocks (N). 789 The partitioning is defined in terms of a first number of source 790 blocks (I), a second number of source blocks (N-I), the length of 791 each of the first source blocks (A_large) and the length of each of 792 the second source blocks (A_small). 794 The following notation is used in the description below: 796 ceil[x] denotes x rounded up to the nearest integer. 798 floor[x] denotes x rounded down to the nearest integer. 800 9.1.1. First Step 802 Input: 804 B -- Maximum Source Block Length, i.e., the maximum number of source 805 symbols per source block 807 L -- Transfer Length in bytes 809 E -- Encoding Symbol Length in bytes 811 Output: 813 T -- the number of source symbols in the object. 815 N -- The number of source blocks into which the object shall be 816 partitioned. 818 Algorithm: 820 1. The number of source symbols in the transport object is computed 821 as T = ceil[L/E]. 823 2. The transport object shall be partitioned into N = ceil[T/B] 824 source blocks. 826 9.1.2. Second step 828 Input: 830 T -- the number of source symbols in the object. 832 N -- The number of source blocks into which the object is 833 partitioned. 835 Output: 837 I -- the number of larger source blocks. 839 A_large -- the length of each of the larger source blocks in symbols. 841 A_small -- the length of each of the smaller source blocks in 842 symbols. 844 Algorithm: 846 1. A_large = ceil[T/N] 848 2. A_small = floor[T/N] 850 3. I = T - A_small * N 852 Each of the first I source blocks then consists of A_large source 853 symbols, each source symbol is E bytes in length. Each of the 854 remaining N-I source blocks consist of A_small source symbols, each 855 source symbol is E bytes in length except that the last source symbol 856 of the last source block is L-((L-1)/E) rounded down to the nearest 857 integer)*E bytes in length. 859 10. Requirements from other building blocks 861 The FEC building block does not provide any support for congestion 862 control. Any complete CDP MUST provide congestion control that 863 conforms to [6], and thus this MUST be provided by another building 864 block when the FEC building block is used in a CDP. 866 There are no other specific requirements from other building blocks 867 for the use of this FEC building block. However, any CDP that uses 868 the FEC building block may use other building blocks for example to 869 provide support for sending higher level session information within 870 data packets containing FEC encoding symbols. 872 11. 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 to 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 the decoded objects be checked for integrity 884 before delivering objects to an application. For example, an MD5 885 hash [7] of an object may be appended before transmission, and the 886 MD5 hash is computed and checked after the object is decoded but 887 before it is delivered to an application. Moreover, in order to 888 obtain strong cryptographic integrity protection a digital signature 889 verifiable by the receiver SHOULD be computed on top of such a hash 890 value. It is also RECOMMENDED that a packet authentication protocol 891 such as TESLA [9] be used to detect and discard corrupted packets 892 upon arrival. Furthermore, it is RECOMMENDED that Reverse Path 893 Forwarding checks be enabled in all network routers and switches 894 along the path from the sender to receivers to limit the possibility 895 of a bad agent successfully injecting a corrupted packet into the 896 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 12. IANA Considerations 909 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA 910 registration. FEC Encoding IDs and FEC Instance IDs are 911 hierarchical: FEC Encoding IDs scope independent ranges of FEC 912 Instance IDs. Only FEC Encoding IDs that correspond to Under- 913 Specified FEC schemes scope a corresponding set of FEC Instance IDs. 915 The FEC Encoding ID and FEC Instance IDs are non-negative integers. 916 In this document, the range of values for FEC Encoding IDs is 0 to 917 255. Values from 0 to 127 are reserved for Fully-Specified FEC 918 schemes and Values from 128 to 255 are reserved for Under-Specified 919 FEC schemes, as described in more detail in Section 6.1. 921 12.1. Explicit IANA Assignment Guidelines 923 This document defines a name-space for FEC Encoding IDs named: 924 ietf:rmt:fec:encoding 926 The values that can be assigned within the "ietf:rmt:fec:encoding" 927 name-space are numeric indexes in the range [0, 255], boundaries 928 included. Assignment requests are granted on a "IETF Consensus" 929 basis as defined in [2]. 931 This document also defines a name-space for FEC Instance IDs named: 932 ietf:rmt:fec:encoding:instance 934 The "ietf:rmt:fec:encoding:instance" name-space is a sub-name-space 935 associated with the "ietf:rmt:fec:encoding" name-space. Each value 936 of "ietf:rmt:fec:encoding" assigned in the range [128, 255] has a 937 separate "ietf:rmt:fec:encoding:instance" sub-name-space that it 938 scopes. Values of "ietf:rmt:fec:encoding" in the range [0, 127] do 939 not scope a "ietf:rmt:fec:encoding:instance" sub-name-space. 941 The values that can be assigned within each "ietf:rmt:fec:encoding: 942 instance" sub-name-space are non-negative integers less than 65536. 943 Assignment requests are granted on a "First Come First Served" basis 944 as defined in [2]. The same value of "ietf:rmt:fec:encoding: 945 instance" can be assigned within multiple distinct sub-name-spaces, 946 i.e., the same value of "ietf:rmt:fec:encoding:instance" can be used 947 for multiple values of "ietf:rmt:fec:encoding". 949 Requestors of "ietf:rmt:fec:encoding:instance" assignments MUST 950 provide the following information: 952 o The value of "ietf:rmt:fec:encoding" that scopes the "ietf:rmt: 953 fec:encoding:instance" sub-name-space. This must be in the range 954 [128, 255]. 956 o Point of contact information 958 o A pointer to publicly accessible documentation describing the 959 Under-Specified FEC scheme, associated with the value of "ietf: 960 rmt:fec:encoding:instance" assigned, and a way to obtain it (e.g., 961 a pointer to a publicly available reference-implementation or the 962 name and contacts of a company that sells it, either separately or 963 embedded in a product). 965 It is the responsibility of the requestor to keep all the above 966 information up to date. 968 13. Acknowledgments 970 This document is largely based on RFC3452 [3] and thus thanks are due 971 to the additional authors of that document: J. Gemmell, L. Rizzo, M. 972 Handley, J. Crowcroft. 974 14. References 976 14.1. Normative References 978 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 979 Levels", BCP 14, RFC 2119, March 1997. 981 [2] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA 982 Considerations Section in RFCs", BCP 26, RFC 2434, October 1998. 984 14.2. Informative References 986 [3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., 987 and J. Crowcroft, "Forward Error Correction (FEC) Building 988 Block", RFC 3452, December 2002. 990 [4] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., 991 and J. Crowcroft, "The Use of Forward Error Correction (FEC) in 992 Reliable Multicast", RFC 3453, December 2002. 994 [5] Kermode, R. and L. Vicisano, "Author Guidelines for Reliable 995 Multicast Transport (RMT) Building Blocks and Protocol 996 Instantiation documents", RFC 3269, April 2002. 998 [6] Mankin, A., Romanov, A., Bradner, S., and V. Paxson, "IETF 999 Criteria for Evaluating Reliable Multicast Transport and 1000 Application Protocols", RFC 2357, June 1998. 1002 [7] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, 1003 April 1992. 1005 [8] Paila, T., Luby, M., Lehtonen, R., Roca, V., and R. Walsh, 1006 "FLUTE - File Delivery over Unidirectional Transport", 1007 RFC 3926, October 2004. 1009 [9] Perrig, A., Song, D., Canetti, R., Tygar, J., and B. Briscoe, 1010 "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): 1011 Multicast Source Authentication Transform Introduction", 1012 RFC 4082, June 2005. 1014 [10] Whetten, B., Vicisano, L., Kermode, R., Handley, M., Floyd, S., 1015 and M. Luby, "Reliable Multicast Transport Building Blocks for 1016 One-to-Many Bulk-Data Transfer", RFC 3048, January 2001. 1018 Authors' Addresses 1020 Mark Watson 1021 Digital Fountain 1022 39141 Civic Center Drive 1023 Suite 300 1024 Fremont, CA 94538 1025 U.S.A. 1027 Email: mark@digitalfountain.com 1029 Michael Luby 1030 Digital Fountain 1031 39141 Civic Center Drive 1032 Suite 300 1033 Fremont, CA 94538 1034 U.S.A. 1036 Email: luby@digitalfountain.com 1038 Lorenzo Vicisano 1039 Cisco Systems, Inc. 1040 170 West Tasman Dr. 1041 San Jose, CA 95134 1042 U.S.A. 1044 Email: lorenzo@cisco.com 1046 Intellectual Property Statement 1048 The IETF takes no position regarding the validity or scope of any 1049 Intellectual Property Rights or other rights that might be claimed to 1050 pertain to the implementation or use of the technology described in 1051 this document or the extent to which any license under such rights 1052 might or might not be available; nor does it represent that it has 1053 made any independent effort to identify any such rights. Information 1054 on the procedures with respect to rights in RFC documents can be 1055 found in BCP 78 and BCP 79. 1057 Copies of IPR disclosures made to the IETF Secretariat and any 1058 assurances of licenses to be made available, or the result of an 1059 attempt made to obtain a general license or permission for the use of 1060 such proprietary rights by implementers or users of this 1061 specification can be obtained from the IETF on-line IPR repository at 1062 http://www.ietf.org/ipr. 1064 The IETF invites any interested party to bring to its attention any 1065 copyrights, patents or patent applications, or other proprietary 1066 rights that may cover technology that may be required to implement 1067 this standard. Please address the information to the IETF at 1068 ietf-ipr@ietf.org. 1070 Disclaimer of Validity 1072 This document and the information contained herein are provided on an 1073 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1074 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 1075 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 1076 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 1077 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1078 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1080 Copyright Statement 1082 Copyright (C) The Internet Society (2005). This document is subject 1083 to the rights, licenses and restrictions contained in BCP 78, and 1084 except as set forth therein, the authors retain all their rights. 1086 Acknowledgment 1088 Funding for the RFC Editor function is currently provided by the 1089 Internet Society.