idnits 2.17.1 draft-ietf-rmt-fec-bb-revised-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 16. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 1112. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 1123. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 1130. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1136. 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 (February 22, 2007) is 6266 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 955, but not defined == Missing Reference: '255' is mentioned on line 972, but not defined == Missing Reference: '128' is mentioned on line 972, but not defined == Missing Reference: '127' is mentioned on line 955, but not defined == Unused Reference: '5' is defined on line 1045, 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: 2 errors (**), 0 flaws (~~), 6 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 Obsoletes: 3452 (if approved) L. Vicisano 5 Intended status: Standards Track Digital Fountain 6 Expires: August 26, 2007 February 22, 2007 8 Forward Error Correction (FEC) Building Block 9 draft-ietf-rmt-fec-bb-revised-05 11 Status of this Memo 13 By submitting this Internet-Draft, each author represents that any 14 applicable patent or other IPR claims of which he or she is aware 15 have been or will be disclosed, and any of which he or she becomes 16 aware will be disclosed, in accordance with Section 6 of BCP 79. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This Internet-Draft will expire on August 26, 2007. 36 Copyright Notice 38 Copyright (C) The IETF Trust (2007). 40 Abstract 42 This document describes how to use Forward Error Correction (FEC) 43 codes to efficiently provide and/or augment reliability for bulk data 44 transfer over IP multicast. This document defines a framework for 45 the definition of the information that needs to be communicated in 46 order to use an FEC code for bulk data transfer, in addition to the 47 encoded data itself, and for definition of formats and codes for 48 communcation of that information. Both information communicated with 49 the encoded data itself and information that needs to be communicated 50 'out-of-band' are considered. The procedures for specifying new FEC 51 codes, defining the information communication requirements associated 52 with those codes and registering them with the Internet Assigned 53 Numbers Authority (IANA) are also described. The requirements on 54 Content Delivery Protocols which wish to use FEC codes defined within 55 this framework are also defined. The companion document titled, "The 56 Use of Forward Error Correction (FEC) in Reliable Multicast" 57 describes some applications of FEC codes for delivering content. 58 This document obsoletes RFC3452. 60 Table of Contents 62 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 63 2. Definitions/Abbreviations . . . . . . . . . . . . . . . . . . 5 64 3. Requirements notation . . . . . . . . . . . . . . . . . . . . 6 65 4. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 7 66 5. Applicability Statement . . . . . . . . . . . . . . . . . . . 9 67 6. Functionality . . . . . . . . . . . . . . . . . . . . . . . . 10 68 6.1. FEC Schemes . . . . . . . . . . . . . . . . . . . . . . . 11 69 6.2. FEC Object Transmission Information . . . . . . . . . . . 13 70 6.2.1. Transport of FEC Object Transmission Information . . . 14 71 6.2.2. Opacity of FEC Object Transmission Information . . . . 15 72 6.2.3. Mandatory FEC Object Transmission Information 73 elements . . . . . . . . . . . . . . . . . . . . . . . 15 74 6.2.4. Common FEC Object Transmission Information elements . 16 75 6.2.5. Scheme-specific FEC Object Transmission 76 Information element . . . . . . . . . . . . . . . . . 16 77 6.3. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 17 78 7. FEC scheme specifications . . . . . . . . . . . . . . . . . . 18 79 8. CDP specifications . . . . . . . . . . . . . . . . . . . . . . 21 80 9. Common algorithms . . . . . . . . . . . . . . . . . . . . . . 22 81 9.1. Block partitioning algorithm . . . . . . . . . . . . . . . 22 82 9.1.1. First Step . . . . . . . . . . . . . . . . . . . . . . 22 83 9.1.2. Second step . . . . . . . . . . . . . . . . . . . . . 23 84 10. Requirements from other building blocks . . . . . . . . . . . 24 85 11. Security Considerations . . . . . . . . . . . . . . . . . . . 25 86 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 87 12.1. Explicit IANA Assignment Guidelines . . . . . . . . . . . 26 88 13. Changes from RFC3452 . . . . . . . . . . . . . . . . . . . . . 28 89 14. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 29 90 15. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30 91 15.1. Normative References . . . . . . . . . . . . . . . . . . . 30 92 15.2. Informative References . . . . . . . . . . . . . . . . . . 30 93 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 31 94 Intellectual Property and Copyright Statements . . . . . . . . . . 32 96 1. Introduction 98 This document describes how to use Forward Error Correction (FEC) 99 codes to provide support for reliable delivery of content within the 100 context of a Content Delivery Protocol (CDP). This document 101 describes a building block as defined in [10]. This document is a 102 product of the IETF RMT WG and follows the general guidelines 103 provided in [8]. 105 The purpose of this building block is to define a framework for 106 forward error correction such that: 108 1. CDPs can be designed to operate with a range of different FEC 109 codes/schemes, without needing to know details of the specific 110 FEC code/scheme that may be used 112 2. FEC schemes can be designed to operate with a range of different 113 CDPs, without needing to know details of the specific CDPs 115 Note that a 'CDP' in the context of this document may consist of 116 several distinct protocol mechanisms and may support any kind of 117 application requiring reliable transport - for example object 118 delivery and streaming applications. 120 This document also provides detailed guidelines on how to write an 121 RFC for an FEC scheme corresponding to a new FEC Encoding ID (for 122 both Fully-Specified and Under-Specified FEC Schemes). 124 RFC3452 [3], which is obsoleted by this document, contained a 125 previous version, which was published in the "Experimental" category. 126 It was the stated intent of the RMT working group to re-submit this 127 specification as an IETF Proposed Standard in due course. 129 This Proposed Standard specification is thus based on RFC3452 [3] 130 updated according to accumulated experience and growing protocol 131 maturity since the publication of RFC3452 [3]. Said experience 132 applies both to this specification itself and to congestion control 133 strategies related to the use of this specification. 135 The differences between RFC3452 [3] and this document listed in 136 Section 13 138 2. Definitions/Abbreviations 140 Object: An ordered sequence of bytes to be transferred by the 141 transport protocol. For example, a file or stream. 143 Symbol: A unit of data processed by the Forward Error Correction 144 code. A symbol is always considered as a unit i.e. it is either 145 completely received or completely lost. 147 Source symbol: A symbol containing information from the original 148 object. 150 Repair symbol: A symbol containing information generated by the FEC 151 code which can be used to recover lost source symbols. 153 Encoding symbol: A source symbol or a repair symbol. 155 Encoder: The FEC scheme specific functions required to transform a 156 object into FEC encoded data. i.e. the functions that produce 157 repair symbols using source symbols. 159 Decoder: The FEC scheme specific functions required to transform 160 received FEC encoded data into a copy of the original object 162 Receiver: A system supporting the receiving functions of a CDP and 163 FEC scheme according to this specification 165 Sender: A system supporting the sending functions of a CDP and FEC 166 scheme according to this specification 168 Source Block: A part of the object formed from a subset of the 169 object's source symbols 171 CDP: Content Delivery Protocol 173 FEC: Forward Error Correction 175 3. Requirements notation 177 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 178 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 179 document are to be interpreted as described in [1]. 181 4. Rationale 183 An FEC code is a valuable basic component of any CDP that is to 184 provide reliable delivery of an object. Using FEC codes is effective 185 in the context of IP multicast and reliable delivery because FEC 186 encoding symbols can be useful to all receivers for reconstructing an 187 object even when the receivers have received different encoding 188 symbols. Furthermore, FEC codes can ameliorate or even eliminate the 189 need for feedback from receivers to senders to request retransmission 190 of lost packets. 192 Central to this document is the concept of an 'FEC Scheme'. An FEC 193 scheme defines ancilliary information and procedures which, combined 194 with an FEC code specification, fully define how the FEC code can be 195 used with CDPs. An FEC scheme may be associated with a single 196 standardised FEC code (A 'Fully-Specified' FEC scheme) or may be 197 applicable to many FEC codes (An 'Under-Specified' FEC scheme). 199 This document describes a framework for the definition of FEC 200 schemes. Definition of actual FEC schemes is outside the scope of 201 this document. This document also defines requirements for reliable 202 CDPs that make use of FEC schemes. Any such CDP which is compliant 203 to the requirements specified in this document can make use of any 204 FEC scheme which is defined within the framework described here. 205 Note that FEC schemes may place restrictions on the types of CDP they 206 are intended to be used with. For example, some FEC schemes may be 207 specific to particular types of application, such as file delivery or 208 streaming. 210 The goal of the FEC building block is to describe functionality 211 directly related to FEC codes that is common to all reliable CDPs and 212 to all FEC schemes, and to leave out any additional functionality 213 that is specific to particular CDPs or particular FEC schemes. The 214 primary functionality described in this document that is common to 215 all such CDPs that use FEC codes is the definition and transport of 216 three kinds of information from sender to receiver(s): encoding 217 symbols themselves, anciliary information associated with encoding 218 symbols (or groups of such symbols, such as the group of symbols in a 219 single packet, or the group of symbols related to a single source 220 block) and anciliary information associated with the whole object 221 being transfered. It is important to note that this ancilliary 222 information is only required by the receiver if one or more of the 223 encoding symbols to which it relates are received. 225 This document for example does not describe how receivers may request 226 transmission of particular encoding symbols for an object. This is 227 because although there are CDPs where requests for transmission are 228 of use, there are also CDPs that do not require such requests. 230 The companion document [4] should be consulted for a full explanation 231 of the benefits of using FEC codes for reliable content delivery 232 using IP multicast. FEC codes are also useful in the context of 233 unicast, and thus the scope and applicability of this document is not 234 limited to IP multicast. 236 5. Applicability Statement 238 The FEC building block does not provide any support for congestion 239 control. Any complete multicast CDP MUST provide congestion control 240 that conforms to [6], and thus this MUST be provided by another 241 building block when the FEC building block is used in a CDP. 243 A more complete description of the applicability of FEC codes can be 244 found in the companion document [4]. 246 6. Functionality 248 This section describes FEC information that is either to be sent in 249 packets also containing FEC encoding symbols or 'out-of-band'. The 250 FEC information is associated with transmission of encoding symbols 251 related to a particular object. There are three classes of packets 252 that may contain FEC information: data packets, session-control 253 packets and feedback packets. They generally contain different kinds 254 of FEC information. Note that some CDPs may not use session-control 255 or feedback packets. 257 Data packets may sometimes serve as session-control packets as well; 258 both data and session-control packets generally travel downstream 259 from the sender towards receivers and are sent to a multicast channel 260 or to a specific receiver using unicast. Session-control packets may 261 additionally travel upstream from receivers to senders. 263 As a general rule, feedback packets travel upstream from receivers to 264 the sender. Sometimes, however, they might be sent to a multicast 265 channel or to another receiver or to some intermediate node or 266 neighboring router that provides recovery services. 268 This document specifies the FEC information that must be carried in 269 data packets and the other FEC information that must be communicated 270 from sender to receiver(s) either out-of-band or in data packets. 271 This document does not specify out-of-band methods nor does it 272 specify the way out-of-band FEC information is associated with FEC 273 information carried in data packets. These methods must be specified 274 in CDP specifications that use this FEC building block. 276 FEC information is classified as follows: 278 1. FEC information associated with an object 280 This is information that is essential for the FEC decoder to 281 decode a specific object. An example of this information is the 282 identity of the FEC scheme that is being used to encode the 283 object, in the form of the FEC Encoding ID. The FEC Encoding ID 284 is described further below. This information may also include 285 FEC scheme-specific parameters for the FEC decoder. 287 2. FEC information associated with specific encoding symbols for an 288 object 290 This is information which is associated with one or more encoding 291 symbols and is thus needed by the decoder whenever one or more of 292 those encoding symbols have been received. Depending on the FEC 293 scheme, information may be associated with individual symbols 294 and/or with groups of symbols. One common such grouping is the 295 group of symbols included within a single packet. Many FEC 296 schemes also segment the object being encoded into multiple 297 'source blocks', each of which is processed independently for FEC 298 purposes. Information about each source block is another type of 299 information associated with a group of encoding symbols, this 300 time the group of symbols which are related to a given source 301 block. 303 Two 'containers' are provided for communicating the FEC information 304 described above, but there is not necessarily a one-to-one 305 correspondance between the class of FEC information and the mechanism 306 used. The two mechanisms are: 308 a. FEC Object Transmission Information 310 CDPs must provide a reliable mechanism for communicating certain 311 FEC information from sender to receiver(s). This information is 312 known as 'FEC Object Transmission Information' and its contents 313 depend on the particular FEC scheme. It includes all information 314 of the first class above and may include information of the 315 second class. The FEC Object Transmission Information can be 316 sent to a receiver within the data packet headers, within session 317 control packets, or by some other means. 319 b. FEC Payload ID 321 CDPs must provide a mechanism for communicating information which 322 identifies (for FEC purposes) the encoding symbols carried by a 323 packet. This information is known as the FEC Payload ID and its 324 contents depend on the FEC scheme. It includes only information 325 of the second class above. A data packet that carries encoding 326 symbols MUST include an FEC Payload ID. 328 6.1. FEC Schemes 330 Two types of FEC scheme are defined by this document: 'Fully- 331 Specified' FEC schemes and 'Under-Specified' FEC schemes. An FEC 332 scheme is a Fully-Specified FEC scheme if the encoding scheme is 333 formally and Fully-Specified, in a way that independent implementors 334 can implement both encoder and decoder from a specification that is 335 an IETF RFC. 337 It is possible that an FEC scheme may not be a Fully-Specified FEC 338 scheme, because either a specification is simply not available or a 339 party exists that owns the encoding scheme and is not willing to 340 disclose the algorithm or specification. We refer to such an FEC 341 encoding scheme as an Under-Specified FEC scheme. 343 FEC schemes are identified by an FEC Encoding ID, which is an integer 344 identifier assigned by IANA. The FEC Encoding ID allows receivers to 345 select the appropriate FEC decoder. The value of the FEC Encoding ID 346 MUST be the same for all transmission of encoding symbols related to 347 a particular object, but MAY vary across different transmissions of 348 encoding symbols about different objects, even if transmitted to the 349 same set of multicast channels and/or using a single upper-layer 350 session. 352 The FEC Instance ID is an integer value that identifies a specific 353 instance of an Under-Specified FEC scheme. This value is not used 354 for Fully-Specified FEC schemes. The FEC Instance ID is scoped by 355 the FEC Encoding ID, and FEC Instance ID values are subject to IANA 356 registration. 358 The FEC Encoding ID for Fully-Specified FEC Schemes and both the FEC 359 Encoding ID and FEC Instance ID for Under-Specified FEc Schemes are 360 essential for the decoder to decode an object and thus are part of 361 the FEC Object Transmission Information. 363 The following requirements apply to all FEC schemes, whether Fully- 364 Specified or Under-Specified: 366 o The type, semantics and an encoding format for the FEC Payload ID 367 and the FEC Object Transmission Information MUST be defined. 369 o A value for the FEC Encoding ID MUST be reserved and associated 370 with the types, semantics and encoding format of the FEC Payload 371 ID and the FEC Object Transmission Information. 373 The specification for an Under-Specified FEC Scheme MAY allocate a 374 sub-field within the Scheme-specific FEC Object Transmission 375 Information element which is for instance-specific information. Each 376 specific instance of the Under-Specified FEC Scheme may then use this 377 field in an instance-specific way. The FEC scheme should define the 378 scheme-specific FEC Object Transmission Information element in such a 379 way that receivers that do not support the received FEC Instance ID 380 can still parse and interpret the scheme-specific FEC Object 381 Transmission Information element with the exception of the instance- 382 specific field. 384 An already defined Under-Specified FEC Scheme (i.e. FEC Encoding ID 385 value) MUST be reused if the associated FEC Payload ID and FEC Object 386 Transmission Information have the required fields and encoding 387 formats for a new Under-Specified FEC scheme instance. 389 An instance of an Under-Specified FEC scheme is fully identified by 390 the tuple (FEC Encoding ID, FEC Instance ID). The tuple MUST 391 identify a single scheme instance that has at least one 392 implementation. The party that owns this tuple MUST be able to 393 provide information on how to obtain the Under-Specified FEC scheme 394 instance identified by the tuple, e.g., a pointer to a publicly 395 available reference-implementation or the name and contacts of a 396 company that sells it, either separately or embedded in another 397 product. 399 This specification reserves the range 0-127 for the values of FEC 400 Encoding IDs for Fully-Specified FEC schemes and the range 128-255 401 for the values of Under-Specified FEC schemes. 403 6.2. FEC Object Transmission Information 405 The FEC Object Transmission Information contains information which is 406 essential to the decoder in order to decode the encoded object. It 407 may also contain information which is required to decode certain 408 groups of encoding symbols, for example individual Source Blocks 409 within the object. This information is communicated reliably by the 410 CDP to the receiver(s) as described in Section 8. 412 The FEC Object Transmission Information may consist of several 413 elements and each element may be one of three types, as follows: 415 Mandatory: These elements are defined in this specification and are 416 each mandatory for at least one of the two types of FEC Scheme. 417 Each FEC scheme specifies how the values of the Mandatory FEC 418 Object Transmission Information elements are determined and each 419 CDP specifies how this information is encoded and reliably 420 communicated to the receiver(s). The Mandatory FEC Object 421 Transmission Information includes the identification of the FEC 422 Scheme, which is needed by the receiver to determine whether it 423 supports the FEC Scheme. 425 Common: These elements are defined in this specification and are 426 optional to be used by an FEC scheme. Each FEC scheme specifies 427 which of the Common FEC Object Transmission Information elements 428 it uses and how the values of these elements are determined. 430 Scheme-specific: An FEC scheme may specify a single Scheme-specific 431 FEC Object Transmission Information element. The FEC scheme 432 specifies the type, semantics and encoding format of the Scheme- 433 specific FEC Object Transmission Information element. The 434 resulting byte-string is known as the "encoded Scheme-specific FEC 435 Object Transmission Information". Each CDP specifies how the 436 encoded Scheme-specific FEC Object Transmission is communicated 437 reliably to the receiver(s) i.e. exactly where it shall be carried 438 within packets of the CDP. Note that although from the point of 439 view of this specification and of CDPs there is only a single 440 Scheme-specific FEC Object Transmission Information element, the 441 FEC scheme may specify this element to contain multiple distinct 442 pieces of information. 444 Each FEC scheme specifies an encoding format for the Common and 445 Scheme-specific FEC Object Transmission Information. Each CDP must 446 specify at least one of the following: 448 1. A means to reliably communicate the Common FEC Object 449 Transmission Information elements to the receiver(s) using the 450 encoding format defined by the FEC scheme. 452 2. An alternative, CDP specific, encoding format for each of the 453 Common FEC Object Transmission Information elements. 455 The Mandatory and Common FEC Object Transmission Information elements 456 are defined in the sections below. 458 6.2.1. Transport of FEC Object Transmission Information 460 It is the responsibility of the CDP to reliably transport the FEC 461 Object Transmission Information to the receiver(s). 463 It is important to note that the encoding format of the Mandatory FEC 464 Object Transmission Information elements (The FEC Encoding ID) is 465 defined by the CDP. This is so that the receiver can identify the 466 FEC Scheme to be used for interpreting the remaining FEC Object 467 Transmission Information elements. All CDPs must define encoding 468 formats for the Mandatory FEC Object Transmission Information 469 element. 471 Common FEC Object Transmission Information elements can be 472 transported in two different ways: (a) the FEC Scheme defines an 473 encoding format for the Common FEC Object Transmission Information 474 elements that it uses and the CDP transports this encoded data block, 475 or (b) the CDP defines an encoding format for each Common FEC Object 476 Transmission Information element and transports the information in 477 this format. 479 An FEC Scheme MUST define an encoding format for the Common FEC 480 Object Transmission Information elements that it uses. The resulting 481 byte string is known as the "encoded Common FEC Object Transmission 482 Information". A CDP MAY define individual encoding formats for each 483 of the Common FEC Object Transmission Information elements. The CDP 484 determines which way the Common FEC Object Transmission Information 485 elements shall be transported, (a) or (b). Note that a CDP may 486 provide support for one or both options. 488 In the case that the CDP uses the encoding format specified by the 489 FEC scheme then it may simply concatenate the encoded Common FEC 490 Object Transmission Information and the encoded Scheme-specific FEC 491 Object Transmission Information or it may carry each in a seperate 492 field or wrapper within the CDP. In the former case, the 493 concatenated byte-string is known as the encoded FEC Object 494 Transmission Information. The FEC scheme must define the encoding 495 format for the Common FEC Object Transmission Information elements 496 that it uses in such a way that the length of each element is either 497 fixed or can be determined from the encoded data itself. 499 The encoding format of the Scheme-specific FEC Object Transmission 500 Information element is defined by the FEC scheme. CDPs specify only 501 how the resulting byte sequence is communicated. As with the 502 encoding format for the Common FEC Oject Transmission Information 503 elements the length of the Scheme-specific FEC Object Transmission 504 Information must either be fixed or it must be possible to determine 505 the length from the encoded data itself. 507 6.2.2. Opacity of FEC Object Transmission Information 509 The Scheme-specific FEC Object Transmission Information element is 510 opaque to the CDP in the sense that inspecting the contents of this 511 element can only be done if FEC scheme-specific logic is included in 512 the CDP. 514 The encoding formats defined by the FEC scheme for the Common FEC 515 Object Transmission Information elements are also opaque to the CDP 516 in the same sense. 518 The encoding formats defined by the CDP for the Common FEC Object 519 Transmission Information elements are not opaque in this sense, 520 although it must be considered that different FEC Schemes may use 521 different combinations of the Common FEC Object Transmission 522 Information elements. 524 6.2.3. Mandatory FEC Object Transmission Information elements 526 The Mandatory FEC Object Transmission Information element is: 528 FEC Encoding ID: an integer between 0 and 255 inclusive identifying 529 a specific FEC scheme (Fully-Specified or Under-Specified.) 531 6.2.4. Common FEC Object Transmission Information elements 533 The Common FEC Object Transmission Information elements are described 534 below. Note that with the exception of the FEC Instance ID, this 535 specification does not provide complete definitions of these fields. 536 Instead only aspects of the abstract type are defined. The precise 537 type and semantics are defined for each FEC scheme in the FEC scheme 538 specification. 540 FEC Instance ID: an integer between 0 and 65535 inclusive 541 identifying an instance of an Under-specifed FEC scheme 543 Transfer-Length: a non-negative integer indicating the length of the 544 object in bytes 546 Encoding-Symbol-Length: a non-negative integer indicating the length 547 of each encoding symbol in bytes 549 Maximum-Source-Block-Length: a non-negative integer indicating the 550 maximum number of source symbols in a source block 552 Max-Number-of-Encoding-Symbols: a non-negative integer indicating 553 the maximum number of encoding symbols (i.e. source plus repair 554 symbols in the case of a systematic code) 556 The FEC Instance ID MUST be used by all Under-specified FEC schemes 557 and MUST NOT be used by Fully-specified FEC Schemes. 559 FEC Schemes define the precise type of those of the above elements 560 that they use and in particular may restrict the value range of each 561 element. FEC Schemes also define an encoding format for the subset 562 of the above elements that they use. CDPs may also provide an 563 encoding format for each element in which case this encoding format 564 MUST be capable of representing values up to (2^^16)-1 in the case of 565 the FEC Instance ID, (2^^48)-1 in the case of the Transfer-Length and 566 up to (2^^32)-1 for the other elements. CDPs may additionally or 567 alternatively provide a mechanism to transport the encoded Common FEC 568 Object Transmission information defined by the FEC scheme. For 569 example, FLUTE [8] specifies an XML-based encoding format for these 570 elements, but can also transport FEC scheme-specific encoding formats 571 within the EXT-FTI LCT header extension. 573 6.2.5. Scheme-specific FEC Object Transmission Information element 575 The Scheme-specific FEC Object Transmission Information element may 576 be used by an FEC Scheme to communicate information which is 577 essential to the decoder which cannot adequately be represented 578 within the Mandatory or Common FEC Object Transmission Information 579 elements. 581 From the point of view of a CDP, the Scheme-specific FEC Object 582 Transmission Information element is an opaque, variable length, byte 583 string. The FEC Scheme defines the structure of this byte string, 584 which may contain multiple distinct elements. 586 6.3. FEC Payload ID 588 The FEC Payload ID contains information which indicates to the FEC 589 decoder the relationships between the encoding symbols carried by a 590 particular packet and the FEC encoding transformation. For example 591 if the packet carries source symbols then the FEC Payload ID 592 indicates which source symbols of the object are carried by the 593 packet. If the packet carries repair symbols, then the FEC Payload 594 ID indicates how those repair symbols were constructed from the 595 object. 597 The FEC Payload ID may also contain information about larger groups 598 of encoding symbols of which those contained in the packet are part. 599 For example, the FEC Payload ID may contain information about the 600 source block the symbols are related to. 602 The FEC Payload ID for a given packet is essential to the decoder if 603 and only if the packet itself is received. Thus it must be possible 604 to obtain the FEC Payload ID from the recieved packet. Usually, the 605 FEC Payload ID is simply carried explicitly as a separate field 606 within each packet. Some FEC schemes may specify means for deriving 607 the relationship between the carried encoding symbols and the object 608 implicitly from other information within the packet, such as protocol 609 headers already present. Such FEC schemes could obviously only be 610 used with CDPs which provided the appropriate information from which 611 the FEC Payload ID could be derived. 613 The encoding format of the FEC Payload ID is defined by the FEC 614 Scheme. CDPs specify how the FEC Payload ID is carried within data 615 packets i.e. the position of the FEC Payload ID within the CDP packet 616 format and the how it is associated with encoding symbols. 618 FEC schemes for systematic FEC codes may specify two FEC Payload ID 619 formats, one for packets carrying only source symbols and another for 620 packets carrying at least one repair symbol. CDPs must include an 621 indication of which of the two FEC Payload ID formats is included in 622 each packet if they wish to support such FEC Schemes. 624 7. FEC scheme specifications 626 A specification for a new FEC scheme MUST include the following 627 things: 629 1. The FEC Encoding ID value that uniquely identifies the FEC 630 scheme. This value MUST be registered with IANA as described in 631 Section 12. 633 2. The type, semantics and encoding format of one or two FEC Payload 634 IDs. Where two FEC Payload ID formats are specified, then the 635 FEC scheme MUST be a systematic FEC code and one FEC Payload ID 636 format MUST be designated for use with packets carrying only 637 source symbols and the other FEC Payload ID format MUST be 638 designated for use with packets carrying at least one repair 639 symbol. 641 3. The type and semantics of the FEC Object Transmission 642 Information. The FEC Scheme MAY define additional restrictions 643 on the type (including value range) of the Common FEC Object 644 Transmission Information elements. 646 4. An encoding format for the Common FEC Object Transmission 647 Information elements used by the FEC Scheme. 649 Fully-Specified FEC schemes MUST further specify: 651 1. A full specification of the FEC code. 653 This specification MUST precisely define the valid FEC Object 654 Transmission Information values, the valid FEC Payload ID values 655 and the valid packet payload sizes for any given object (where 656 packet payload refers to the space - not necessarily contiguous - 657 within a packet dedicated to carrying encoding symbol bytes). 659 Furthermore, given an object, valid values for each of the FEC 660 Object Transmission Information elements used by the FEC Scheme, 661 a valid FEC Payload ID value and a valid packet payload size, the 662 specification MUST uniquely define the values of the encoding 663 symbol bytes to be included in the packet payload of a packet 664 with the given FEC Payload ID value. 666 A common and simple way to specify the FEC code to the required 667 level of detail is to provide a precise specification of an 668 encoding algorithm which, given an object, valid values for each 669 of the FEC Object Transmission Information elements used by the 670 FEC Scheme for the object, a valid FEC Payload ID and packet 671 payload length as input produces the exact value of the encoding 672 symbol bytes as output. 674 2. A description of practical encoding and decoding algorithms. 676 This description need not be to the same level of detail as for 677 (1) above, however it must be sufficient to demonstrate that 678 encoding and decoding of the code is both possible and practical. 680 FEC scheme specifications MAY additionally define the following: 682 1. Type, semantics and encoding format of a Scheme-specific FEC 683 Object Transmission Information element. 685 Note that if an FEC sheme does not define a Scheme-specific FEC 686 Object Transmission Information then such an element MUST NOT be 687 introduced in future versions of the FEC Scheme. This requirement is 688 included to ensure backwards-compatibility of CDPs designed to 689 support only FEC Schemes which do not use the Scheme-specific FEC 690 Object Transmission Information element. 692 Whenever an FEC scheme specification defines an 'encoding format' for 693 an element, this must be defined in terms of a sequence of bytes 694 which can be embedded within a protocol. The length of the encoding 695 format MUST either be fixed or it must be possible to derive the 696 length from examining the encoded bytes themselves. For example, the 697 initial bytes may include some kind of length indication. 699 FEC schemes SHOULD make use of the Common FEC Object Transmission 700 Information elements in preference to including infomation in a 701 Scheme-specific FEC Object Transmission Information element. 703 FEC scheme specifications SHOULD use the terminology defined in this 704 document and SHOULD follow the following format: 706 1. Introduction 709 711 2. Formats and Codes 713 2.1 FEC Payload ID(s) 716 2.2 FEC Object Transmission Information 718 2.2.1 Mandatory 721 2.2.2 Common 725 2.2.3 Scheme-Specific 729 3. Procedures 734 4. FEC code specification (for Fully-Specified FEC schemes only) 735 737 Specifications MAY include additional sections, for example, 738 examples. 740 Each FEC scheme MUST be specified independently of all other FEC 741 schemes; for example, in a separate specification or a completely 742 independent section of larger specification. 744 8. CDP specifications 746 A specification for a CDP that uses this building block MUST include 747 the following things: 749 1. Definitions of an encoding formats for the Mandatory FEC Object 750 Transmission Information element. 752 2. A means to reliably communicate the Mandatory FEC Object 753 Transmission Information element from sender to receiver(s) using 754 the encoding format defined in (1). 756 3. Means to reliably communicate the Common FEC Object Transmission 757 Information element from sender to receiver(s) using either or 758 both of (a) the encoding format defined by the FEC Scheme or (b) 759 encoding formats defined by the CDP 761 4. A means to reliably communicate the Scheme-specific FEC Object 762 Transmission Information element from sender to receiver(s) using 763 the encoding format of the Scheme-specific FEC Object 764 Transmission Information element defined by the FEC scheme. 766 5. A means to communicate the FEC Payload ID in association with a 767 data packet. Note that the encoding format of the FEC Payload ID 768 is defined by the FEC Scheme. 770 If option (b) of (3) above is used, then the CDP MUST specify an 771 encoding format for the Common FEC Object Transmission Information 772 elements. 774 CDPs MAY additionally specify the following things: 776 1. A means to indicate whether the FEC Payload ID within a packet is 777 encoded according to the format for packets including only source 778 symbols or according to the format for packets including at least 779 one repair symbol. 781 9. Common algorithms 783 This section describes certain algorithms which are expected to be 784 commonly required by FEC schemes or by CDPs. FEC Schemes and CDPs 785 SHOULD use these algorithms in preference to scheme or protocol 786 specific algorithms where appropriate. 788 9.1. Block partitioning algorithm 790 This algorithm computes a partitioning of a object into source blocks 791 so that all source blocks are as close to being equal length as 792 possible. A first number of source blocks are of the same larger 793 length, and the remaining second number of source blocks of the same 794 smaller length. 796 This algorithm is described in two steps, the second of which may be 797 useful in itself as an independent algorithm in some cases. In the 798 first step, the number of source symbols (T) and the number of source 799 blocks (N) are derived from the Object transfer length (L), Maximum 800 Source Block Length (B) and Symbol Length (E). 802 In the second step, the partitioning of the object is derived from 803 the number of source symbols (T) and the number of source blocks (N). 804 The partitioning is defined in terms of a first number of source 805 blocks (I), a second number of source blocks (N-I), the length of 806 each of the first source blocks (A_large) and the length of each of 807 the second source blocks (A_small). 809 The following notation is used in the description below: 811 ceil[x] denotes x rounded up to the nearest integer. 813 floor[x] denotes x rounded down to the nearest integer. 815 9.1.1. First Step 817 Input: 819 B -- Maximum Source Block Length, i.e., the maximum number of source 820 symbols per source block 822 L -- Transfer Length in bytes 824 E -- Encoding Symbol Length in bytes 826 Output: 828 T -- the number of source symbols in the object. 830 N -- The number of source blocks into which the object shall be 831 partitioned. 833 Algorithm: 835 1. The number of source symbols in the transport object is computed 836 as T = ceil[L/E]. 838 2. The transport object shall be partitioned into N = ceil[T/B] 839 source blocks. 841 9.1.2. Second step 843 Input: 845 T -- the number of source symbols in the object. 847 N -- The number of source blocks into which the object is 848 partitioned. 850 Output: 852 I -- the number of larger source blocks. 854 A_large -- the length of each of the larger source blocks in 855 symbols. 857 A_small -- the length of each of the smaller source blocks in 858 symbols. 860 Algorithm: 862 1. A_large = ceil[T/N] 864 2. A_small = floor[T/N] 866 3. I = T - A_small * N 868 Each of the first I source blocks then consists of A_large source 869 symbols, each source symbol is E bytes in length. Each of the 870 remaining N-I source blocks consist of A_small source symbols, each 871 source symbol is E bytes in length except that the last source symbol 872 of the last source block is L-((L-1)/E) rounded down to the nearest 873 integer)*E bytes in length. 875 10. Requirements from other building blocks 877 The FEC building block does not provide any support for congestion 878 control. Any complete CDP MUST provide congestion control that 879 conforms to [6], and thus this MUST be provided by another building 880 block when the FEC building block is used in a CDP. 882 There are no other specific requirements from other building blocks 883 for the use of this FEC building block. However, any CDP that uses 884 the FEC building block may use other building blocks for example to 885 provide support for sending higher level session information within 886 data packets containing FEC encoding symbols. 888 11. Security Considerations 890 Data delivery can be subject to denial-of-service attacks by 891 attackers which send corrupted packets that are accepted as 892 legitimate by receivers. This is particularly a concern for 893 multicast delivery because a corrupted packet may be injected into 894 the session close to the root of the multicast tree, in which case 895 the corrupted packet will arrive to many receivers. This is 896 particularly a concern for the FEC building block because the use of 897 even one corrupted packet containing encoding data may result in the 898 decoding of an object that is completely corrupted and unusable. It 899 is thus RECOMMENDED that source authentication and integrity checking 900 are applied to decoded objects before delivering objects to an 901 application. For example, an MD5 hash [7] of an object may be 902 appended before transmission, and the MD5 hash is computed and 903 checked after the object is decoded but before it is delivered to an 904 application. Source authentication SHOULD be provided, for example 905 by including a digital signature verifiable by the receiver computed 906 on top of the hash value. It is also RECOMMENDED that a packet 907 authentication protocol such as TESLA [9] be used to detect and 908 discard corrupted packets upon arrival. Furthermore, it is 909 RECOMMENDED that Reverse Path Forwarding checks be enabled in all 910 network routers and switches along the path from the sender to 911 receivers to limit the possibility of a bad agent successfully 912 injecting a corrupted packet into the multicast tree data path. 914 Another security concern is that some FEC information may be obtained 915 by receivers out-of-band in a session description, and if the session 916 description is forged or corrupted then the receivers will not use 917 the correct protocol for decoding content from received packets. To 918 avoid these problems, it is RECOMMENDED that measures be taken to 919 prevent receivers from accepting incorrect session descriptions, 920 e.g., by using source authentication to ensure that receivers only 921 accept legitimate session descriptions from authorized senders. 923 12. IANA Considerations 925 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA 926 registration. FEC Encoding IDs and FEC Instance IDs are 927 hierarchical: FEC Encoding IDs scope independent ranges of FEC 928 Instance IDs. Only FEC Encoding IDs that correspond to Under- 929 Specified FEC schemes scope a corresponding set of FEC Instance IDs. 931 The FEC Encoding ID and FEC Instance IDs are non-negative integers. 932 In this document, the range of values for FEC Encoding IDs is 0 to 933 255. Values from 0 to 127 are reserved for Fully-Specified FEC 934 schemes and Values from 128 to 255 are reserved for Under-Specified 935 FEC schemes, as described in more detail in Section 6.1. 937 12.1. Explicit IANA Assignment Guidelines 939 This document defines a name-space for FEC Encoding IDs named: 940 ietf:rmt:fec:encoding 942 The values that can be assigned within the "ietf:rmt:fec:encoding" 943 name-space are numeric indexes in the range [0, 255], boundaries 944 included. Assignment requests are granted on a "IETF Consensus" 945 basis as defined in [2]. Section 7 defines explicit requirements 946 that documents defining new FEC Encloding IDs should meet. 948 This document also defines a name-space for FEC Instance IDs named: 949 ietf:rmt:fec:encoding:instance 951 The "ietf:rmt:fec:encoding:instance" name-space is a sub-name-space 952 associated with the "ietf:rmt:fec:encoding" name-space. Each value 953 of "ietf:rmt:fec:encoding" assigned in the range [128, 255] has a 954 separate "ietf:rmt:fec:encoding:instance" sub-name-space that it 955 scopes. Values of "ietf:rmt:fec:encoding" in the range [0, 127] do 956 not scope a "ietf:rmt:fec:encoding:instance" sub-name-space. 958 The values that can be assigned within each "ietf:rmt:fec:encoding: 959 instance" sub-name-space are non-negative integers less than 65536. 960 Assignment requests are granted on a "First Come First Served" basis 961 as defined in [2]. The same value of "ietf:rmt:fec:encoding: 962 instance" can be assigned within multiple distinct sub-name-spaces, 963 i.e., the same value of "ietf:rmt:fec:encoding:instance" can be used 964 for multiple values of "ietf:rmt:fec:encoding". 966 Requestors of "ietf:rmt:fec:encoding:instance" assignments MUST 967 provide the following information: 969 o The value of "ietf:rmt:fec:encoding" that scopes the "ietf:rmt: 970 fec:encoding:instance" sub-name-space. This must be in the range 972 [128, 255]. 974 o Point of contact information 976 o A pointer to publicly accessible documentation describing the 977 Under-Specified FEC scheme, associated with the value of "ietf: 978 rmt:fec:encoding:instance" assigned, and a way to obtain it (e.g., 979 a pointer to a publicly available reference-implementation or the 980 name and contacts of a company that sells it, either separately or 981 embedded in a product). 983 It is the responsibility of the requestor to keep all the above 984 information up to date. 986 13. Changes from RFC3452 988 This section lists the changes between the Experimental version of 989 this specification, [3], and this version: 991 o The requirements for definition of a new FEC Scheme and the 992 requirements for specification of new Content Delivery Protocols 993 which use FEC Schemes are made more explicit to permit independent 994 definition of FEC Schemes and Content Delivery Protocols. 996 o The definitions of basic FEC Schemes have been removed with the 997 intention of publishing these separately. 999 o The FEC Object Transmission Information is more explicitly defined 1000 and in particular three classes of FEC OTI (Mandatory, Common and 1001 Scheme-specific) are introduced to permit re-usable definition of 1002 explicit fields in Content Delivery Protocols to carry these 1003 elements. 1005 o FEC Schemes are required to specify a complete encoding for the 1006 FEC Object Transmission which can be carried transparently by 1007 Content Delivery protocols (instead of defining explicit 1008 elements). 1010 o The possibility for FEC Schemes to define two FEC Payload ID 1011 formats for use with souce and repair packets respectively in the 1012 case of systematic FEC codes is introduced. 1014 o The file blocking algorithm from FLUTE is included here as a 1015 common algorithm which is recommended to be re-used by FEC Schemes 1016 when appropriate. 1018 14. Acknowledgments 1020 This document is largely based on RFC3452 [3] and thus thanks are due 1021 to the additional authors of that document: J. Gemmell, L. Rizzo, M. 1022 Handley, J. Crowcroft. 1024 15. References 1026 15.1. Normative References 1028 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 1029 Levels", BCP 14, RFC 2119, March 1997. 1031 [2] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA 1032 Considerations Section in RFCs", BCP 26, RFC 2434, 1033 October 1998. 1035 15.2. Informative References 1037 [3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., 1038 and J. Crowcroft, "Forward Error Correction (FEC) Building 1039 Block", RFC 3452, December 2002. 1041 [4] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., 1042 and J. Crowcroft, "The Use of Forward Error Correction (FEC) in 1043 Reliable Multicast", RFC 3453, December 2002. 1045 [5] Kermode, R. and L. Vicisano, "Author Guidelines for Reliable 1046 Multicast Transport (RMT) Building Blocks and Protocol 1047 Instantiation documents", RFC 3269, April 2002. 1049 [6] Mankin, A., Romanov, A., Bradner, S., and V. Paxson, "IETF 1050 Criteria for Evaluating Reliable Multicast Transport and 1051 Application Protocols", RFC 2357, June 1998. 1053 [7] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, 1054 April 1992. 1056 [8] Paila, T., Luby, M., Lehtonen, R., Roca, V., and R. Walsh, 1057 "FLUTE - File Delivery over Unidirectional Transport", 1058 RFC 3926, October 2004. 1060 [9] Perrig, A., Song, D., Canetti, R., Tygar, J., and B. Briscoe, 1061 "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): 1062 Multicast Source Authentication Transform Introduction", 1063 RFC 4082, June 2005. 1065 [10] Whetten, B., Vicisano, L., Kermode, R., Handley, M., Floyd, S., 1066 and M. Luby, "Reliable Multicast Transport Building Blocks for 1067 One-to-Many Bulk-Data Transfer", RFC 3048, January 2001. 1069 Authors' Addresses 1071 Mark Watson 1072 Digital Fountain 1073 39141 Civic Center Drive 1074 Suite 300 1075 Fremont, CA 94538 1076 U.S.A. 1078 Email: mark@digitalfountain.com 1080 Michael Luby 1081 Digital Fountain 1082 39141 Civic Center Drive 1083 Suite 300 1084 Fremont, CA 94538 1085 U.S.A. 1087 Email: luby@digitalfountain.com 1089 Lorenzo Vicisano 1090 Digital Fountain 1091 39141 Civic Center Drive 1092 Suite 300 1093 Fremont, CA 94538 1094 U.S.A. 1096 Email: lorenzo@digitalfountain.com 1098 Full Copyright Statement 1100 Copyright (C) The IETF Trust (2007). 1102 This document is subject to the rights, licenses and restrictions 1103 contained in BCP 78, and except as set forth therein, the authors 1104 retain all their rights. 1106 This document and the information contained herein are provided on an 1107 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1108 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 1109 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 1110 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 1111 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1112 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1114 Intellectual Property 1116 The IETF takes no position regarding the validity or scope of any 1117 Intellectual Property Rights or other rights that might be claimed to 1118 pertain to the implementation or use of the technology described in 1119 this document or the extent to which any license under such rights 1120 might or might not be available; nor does it represent that it has 1121 made any independent effort to identify any such rights. Information 1122 on the procedures with respect to rights in RFC documents can be 1123 found in BCP 78 and BCP 79. 1125 Copies of IPR disclosures made to the IETF Secretariat and any 1126 assurances of licenses to be made available, or the result of an 1127 attempt made to obtain a general license or permission for the use of 1128 such proprietary rights by implementers or users of this 1129 specification can be obtained from the IETF on-line IPR repository at 1130 http://www.ietf.org/ipr. 1132 The IETF invites any interested party to bring to its attention any 1133 copyrights, patents or patent applications, or other proprietary 1134 rights that may cover technology that may be required to implement 1135 this standard. Please address the information to the IETF at 1136 ietf-ipr@ietf.org. 1138 Acknowledgment 1140 Funding for the RFC Editor function is provided by the IETF 1141 Administrative Support Activity (IASA).