--- 1/draft-ietf-rmt-fec-bb-revised-00.txt 2006-02-04 17:28:16.000000000 +0100 +++ 2/draft-ietf-rmt-fec-bb-revised-01.txt 2006-02-04 17:28:16.000000000 +0100 @@ -1,47 +1,45 @@ Reliable Multicast M. Watson Internet-Draft M. Luby -Expires: October 31, 2005 Digital Fountain +Expires: March 5, 2006 Digital Fountain L. Vicisano Cisco Systems, Inc. - April 29, 2005 + September 1, 2005 Forward Error Correction (FEC) Building Block - draft-ietf-rmt-fec-bb-revised-00 + draft-ietf-rmt-fec-bb-revised-01 Status of this Memo - This document is an Internet-Draft and is subject to all provisions - of Section 3 of RFC 3667. By submitting this Internet-Draft, each - author represents that any applicable patent or other IPR claims of - which he or she is aware have been or will be disclosed, and any of - which he or she become aware will be disclosed, in accordance with - RFC 3668. + By submitting this Internet-Draft, each author represents that any + applicable patent or other IPR claims of which he or she is aware + have been or will be disclosed, and any of which he or she becomes + aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. - This Internet-Draft will expire on October 31, 2005. + This Internet-Draft will expire on March 5, 2006. Copyright Notice Copyright (C) The Internet Society (2005). Abstract This document describes how to use Forward Error Correction (FEC) codes to efficiently provide and/or augment reliability for data transport. This document defines a framework for the definition of @@ -55,129 +53,77 @@ those codes and registering them with the Internet Assigned Numbers Authority (IANA) are also described. The requirements on Content Delivery Protocols which wish to use FEC codes defined within this framework are also defined. The companion document titled, "The Use of Forward Error Correction (FEC) in Reliable Multicast" describes some applications of FEC codes for delivering content. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 - 2. Definitions/Abbreviations . . . . . . . . . . . . . . . . . . 5 - 3. Requirements notation . . . . . . . . . . . . . . . . . . . . 6 - 4. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 7 - 5. Applicability Statement . . . . . . . . . . . . . . . . . . . 9 - 6. Functionality . . . . . . . . . . . . . . . . . . . . . . . . 10 - 6.1 FEC Schemes . . . . . . . . . . . . . . . . . . . . . . . 11 - 6.2 FEC Object Transmission Information . . . . . . . . . . . 13 - 6.2.1 Transport of Object Transmission Information . . . . . 14 - 6.2.2 Opacity of Object Transmission Information . . . . . . 15 - 6.2.3 Mandatory FEC Object Transmission Information - elements . . . . . . . . . . . . . . . . . . . . . . . 15 - 6.2.4 Common FEC Object Transmission Information elements . 15 - 6.2.5 Scheme-specific FEC Object Transmission - Information element . . . . . . . . . . . . . . . . . 16 - 6.3 FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 16 - 7. FEC scheme specifications . . . . . . . . . . . . . . . . . . 18 - 8. CDP specifications . . . . . . . . . . . . . . . . . . . . . . 21 - 9. Common algorithms . . . . . . . . . . . . . . . . . . . . . . 22 - 9.1 Block partitioning algorithm . . . . . . . . . . . . . . . 22 - 9.1.1 First Step . . . . . . . . . . . . . . . . . . . . . . 22 - 9.1.2 Second step . . . . . . . . . . . . . . . . . . . . . 23 - 10. Requirements from other building blocks . . . . . . . . . . 25 - 11. Security Considerations . . . . . . . . . . . . . . . . . . 26 - 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . 27 - 12.1 Explicit IANA Assignment Guidelines . . . . . . . . . . . 27 - 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 29 - 14. References . . . . . . . . . . . . . . . . . . . . . . . . . 29 - Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 30 - Intellectual Property and Copyright Statements . . . . . . . . 31 + 2. Definitions/Abbreviations . . . . . . . . . . . . . . . . . . 4 + 3. Requirements notation . . . . . . . . . . . . . . . . . . . . 5 + 4. Rationale . . . . . . . . . . . . . . . . . . . . . . . . . . 6 + 5. Applicability Statement . . . . . . . . . . . . . . . . . . . 8 + 6. Functionality . . . . . . . . . . . . . . . . . . . . . . . . 9 + 6.1. FEC Schemes . . . . . . . . . . . . . . . . . . . . . . . 10 + 6.2. FEC Object Transmission Information . . . . . . . . . . . 12 + 6.2.1. Transport of FEC Object Transmission Information . . . 13 + 6.2.2. Opacity of FEC Object Transmission Information . . . . 14 + 6.2.3. Mandatory FEC Object Transmission Information + elements . . . . . . . . . . . . . . . . . . . . . . . 14 + 6.2.4. Common FEC Object Transmission Information elements . 15 + 6.2.5. Scheme-specific FEC Object Transmission + Information element . . . . . . . . . . . . . . . . . 15 + 6.3. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 16 + 7. FEC scheme specifications . . . . . . . . . . . . . . . . . . 17 + 8. CDP specifications . . . . . . . . . . . . . . . . . . . . . . 20 + 9. Common algorithms . . . . . . . . . . . . . . . . . . . . . . 21 + 9.1. Block partitioning algorithm . . . . . . . . . . . . . . . 21 + 9.1.1. First Step . . . . . . . . . . . . . . . . . . . . . . 21 + 9.1.2. Second step . . . . . . . . . . . . . . . . . . . . . 22 + 10. Requirements from other building blocks . . . . . . . . . . . 24 + 11. Security Considerations . . . . . . . . . . . . . . . . . . . 25 + 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 + 12.1. Explicit IANA Assignment Guidelines . . . . . . . . . . . 26 + 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 28 + 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 29 + 14.1. Normative References . . . . . . . . . . . . . . . . . . . 29 + 14.2. Informative References . . . . . . . . . . . . . . . . . . 29 + Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 30 + Intellectual Property and Copyright Statements . . . . . . . . . . 31 1. Introduction This document describes how to use Forward Error Correction (FEC) codes to provide support for reliable delivery of content within the context of a Content Delivery Protocol (CDP). This document - describes a building block as defined in [11]. This document is a + describes a building block as defined in [10]. This document is a product of the IETF RMT WG and follows the general guidelines - provided in [9]. + provided in [8]. The purpose of this building block is to define a framework for forward error correction such that: 1. CDPs can be designed to operate with a range of different FEC codes/scheme, without needing to know details of the specific FEC code/scheme that may be used 2. FEC schemes can be designed to operate with a range of different CDPs, without needing to know details of the specific CDPs Note that a 'CDP' in the context of this document may consist of several distinct protocol mechanisms. - Editor's note (to be removed): This document proposes an update to - RFC3452. The primary goals of this update are: - - 1. Move the FEC Building Block from Experimental to Proposed - Standard - - 2. Clarify some confusing language in the current RFC 3452, which - is not incorrect but has been misinterpreted on some occasions - (based on comments on the mailing list and during the RMT - meetings). - - 3. Provide detailed guidelines on how to write an RFC for an FEC - scheme corresponding to a new FEC Encoding ID (for both Fully- - Specified and Under-Specified FEC Schemes) - - 4. Ensure that the FEC building block is applicable to multiple - protocols, including FLUTE and NORM. The FEC Building Block - will not preclude the application of FEC Schemes to streaming - protocols, for FEC schemes that support it. - - 5. Ensure that protocols using this building block can be defined - in a way whch is 'FEC Scheme independent' so that new FEC - schemes can be defined without the need to amend the CDPs. - - 6. Ensure that new FEC schemes can be defined in a way which is - 'CDP independent' so that new CDPs can be defined without the - need to amend the FEC schemes. - - 7. Ensure on-the-wire backwards compatibility with existing - implementations of protocols that are compliant with the - current Experimental RFCs, e.g., existing implementations of - FLUTE and NORM. - - It is anticipated that updates to other RMT RFCs to Proposed - Standard status will be carried out independently and in parallel - with this work. Whilst on-the-wire backwards compatibility is a - mandatory requirement, some reorganisation of material amongst the - RFCs is implied by the approach proposed in this document. - Specifically: - - 8. FEC Scheme definitions from RFC3452 should be moved to a - separate document. The scheme definitions will be revised to - follow the format specified in this document. - - 9. FEC scheme specific information in FLUTE (RFC3926) should be - moved into the FEC Scheme specification document referred to - above, for example the formats of the FEC Object Transmission - Information when carried in EXT_FTI. - - 10. Provision for transport of FEC scheme specific Object - Transmission Information needs to be included in FLUTE and - NORM (in a backwards-compatible way). - - It is also proposed that the algorithm for partitioning objects - into source blocks currently included in the FLUTE specification - should be moved into this document as a common algorithm to be - used by multiple FEC Schemes. + This document also provides detailed guidelines on how to write an + RFC for an FEC scheme corresponding to a new FEC Encoding ID (for + both Fully-Specified and Under-Specified FEC Schemes). 2. Definitions/Abbreviations Object: An ordered sequence of bytes to be transferred by the transport protocol. For example, a file or stream. Symbol: A unit of data processed by the Forward Error Correction code. A symbol is always considered as a unit i.e. it is either completely received or completely lost. @@ -221,84 +167,82 @@ provide reliable delivery of an object. Using FEC codes is effective in the context of IP multicast and reliable delivery because FEC encoding symbols can be useful to all receivers for reconstructing an object even when the receivers have received different encoding symbols. Furthermore, FEC codes can ameliorate or even eliminate the need for feedback from receivers to senders to request retransmission of lost packets. Central to this document is the concept of an 'FEC Scheme'. An FEC scheme defines ancilliary information and procedures which, combined - with an FEC encoding algorithm, fully define how the FEC code can be + with an FEC code specification, fully define how the FEC code can be used with CDPs. An FEC scheme may be associated with a single - standardised FEC algorithm (A 'Fully specified' FEC scheme) or may be - applicable to many FEC algorithms (An 'under-specified' FEC scheme). + standardised FEC code (A 'Fully-Specified' FEC scheme) or may be + applicable to many FEC codes (An 'Under-Specified' FEC scheme). This document describes a framework for the definition of FEC schemes. Definition of actual FEC schemes is outside the scope of this document. This document also defines requirements for reliable - CDPs that make use of FEC schemes. Any such protocol which is - compliant to the requirements specified in this document can make use - of any FEC scheme which is defined within the framework described - here. Note that FEC schemes may place restrictions on the types of - CDP they are intended to be used with. For example, some FEC schemes - may be specific to particular types of application, such as file - delivery or streaming. + CDPs that make use of FEC schemes. Any such CDP which is compliant + to the requirements specified in this document can make use of any + FEC scheme which is defined within the framework described here. + Note that FEC schemes may place restrictions on the types of CDP they + are intended to be used with. For example, some FEC schemes may be + specific to particular types of application, such as file delivery or + streaming. The goal of the FEC building block is to describe functionality directly related to FEC codes that is common to all reliable CDPs and to all FEC schemes, and to leave out any additional functionality - that is specific to particular protocols or particular FEC schemes. - The primary functionality described in this document that is common - to all such protocols that use FEC codes is the definition and - transport of three kinds of information from sender to receiver(s): - encoding symbols themselves, anciliary information associated with - encoding symbols (or groups of such symbols, such as the group of - symbols in a single packet, or the group of symbols related to a - single source block) and anciliary information associated with the - whole object being transfered. It is important to note that this - ancilliary information is only required by the receiver if one or - more of the encoding symbols to which it relates are received. + that is specific to particular CDPs or particular FEC schemes. The + primary functionality described in this document that is common to + all such CDPs that use FEC codes is the definition and transport of + three kinds of information from sender to receiver(s): encoding + symbols themselves, anciliary information associated with encoding + symbols (or groups of such symbols, such as the group of symbols in a + single packet, or the group of symbols related to a single source + block) and anciliary information associated with the whole object + being transfered. It is important to note that this ancilliary + information is only required by the receiver if one or more of the + encoding symbols to which it relates are received. This document for example does not describe how receivers may request transmission of particular encoding symbols for an object. This is - because although there are protocols where requests for transmission - are of use, there are also protocols that do not require such - requests. + because although there are CDPs where requests for transmission are + of use, there are also CDPs that do not require such requests. - The companion document [3] should be consulted for a full explanation + The companion document [4] should be consulted for a full explanation of the benefits of using FEC codes for reliable content delivery using IP multicast. FEC codes are also useful in the context of unicast, and thus the scope and applicability of this document is not limited to IP multicast. 5. Applicability Statement The FEC building block does not provide any support for congestion - control. Any complete multicast protocol MUST provide congestion - control that conforms to [5], and thus this MUST be provided by - another building block when the FEC building block is used in a - protocol. + control. Any complete multicast CDP MUST provide congestion control + that conforms to [6], and thus this MUST be provided by another + building block when the FEC building block is used in a CDP. A more complete description of the applicability of FEC codes can be - found in the companion document [3]. + found in the companion document [4]. 6. Functionality This section describes FEC information that is either to be sent in packets also containing FEC encoding symbols or 'out-of-band'. The FEC information is associated with transmission of encoding symbols related to a particular object. There are three classes of packets that may contain FEC information: data packets, session-control packets and feedback packets. They generally contain different kinds - of FEC information. Note that some protocols may not use session- - control or feedback packets. + of FEC information. Note that some CDPs may not use session-control + or feedback packets. Data packets may sometimes serve as session-control packets as well; both data and session-control packets generally travel downstream from the sender towards receivers and are sent to a multicast channel or to a specific receiver using unicast. Session-control packets may additionally travel upstream from receivers to senders. As a general rule, feedback packets travel upstream from receivers to the sender. Sometimes, however, they might be sent to a multicast channel or to another receiver or to some intermediate node or @@ -357,26 +301,26 @@ b. FEC Payload ID CDPs must provide a mechanism for communicating information which identifies (for FEC purposes) the encoding symbols carried by a packet. This information is known as the FEC Payload ID and its contents depend on the FEC scheme. It includes only information of the second class above. A data packet that carries encoding symbols MUST include an FEC Payload ID. -6.1 FEC Schemes +6.1. FEC Schemes Two types of FEC scheme are defined by this document: 'Fully- - specified' FEC schemes and 'Under-specified' FEC schemes. An FEC + Specified' FEC schemes and 'Under-Specified' FEC schemes. An FEC scheme is a Fully-Specified FEC scheme if the encoding scheme is - formally and fully specified, in a way that independent implementors + formally and Fully-Specified, in a way that independent implementors can implement both encoder and decoder from a specification that is an IETF RFC. It is possible that an FEC scheme may not be a Fully-Specified FEC scheme, because either a specification is simply not available or a party exists that owns the encoding scheme and is not willing to disclose the algorithm or specification. We refer to such an FEC encoding scheme as an Under-Specified FEC scheme. FEC schemes are identified by an FEC Encoding ID, which is an integer @@ -387,42 +331,43 @@ encoding symbols about different objects, even if transmitted to the same set of multicast channels and/or using a single upper-layer session. The FEC Instance ID is an integer value that identifies a specific instance of an Under-Specified FEC scheme. This value is not used for Fully-Specified FEC schemes. The FEC Instance ID is scoped by the FEC Encoding ID, and FEC Instance ID values are subject to IANA registration. - The FEC Encoding ID and FEC Instance ID are essential for the decoder - to decode an object and thus are part of the FEC Object Transmission - Information. + The FEC Encoding ID for Fully-Specified FEC Schemes and both the FEC + Encoding ID and FEC Instance ID for Under-Specified FEc Schemes are + essential for the decoder to decode an object and thus are part of + the FEC Object Transmission Information. The following requirements apply to all FEC schemes, whether Fully- Specified or Under-Specified: o The type, semantics and an encoding format for the FEC Payload ID and the FEC Object Transmission Information MUST be defined. o A value for the FEC Encoding ID MUST be reserved and associated with the types, semantics and encoding format of the FEC Payload ID and the the FEC Object Transmission Information. The specification for an Under-Specified FEC Scheme MAY allocate a sub-field within the Scheme-specific FEC Object Transmission Information element which is for instance-specific information. Each specific instance of the Under-Specified FEC Scheme may then use this field in an instance-specific way. The FEC scheme should define the scheme-specific FEC Object Transmission Information element in such a way that receivers that do not support the received FEC Instance ID - can still parse and interpret the scheme-speific FEC Object + can still parse and interpret the scheme-specific FEC Object Transmission Information element with the exception of the instance- specific field. An already defined Under-Specified FEC Scheme (i.e. FEC Encoding ID value) MUST be reused if the associated FEC Payload ID and FEC Object Transmission Information have the required fields and encoding formats for a new Under-Specified FEC scheme instance. An instance of an Under-Specified FEC scheme is fully identified by the tuple (FEC Encoding ID, FEC Instance ID). The tuple MUST @@ -431,40 +376,41 @@ provide information on how to obtain the the Under-Specified FEC scheme instance identified by the tuple, e.g., a pointer to a publicly available reference-implementation or the name and contacts of a company that sells it, either separately or embedded in another product. This specification reserves the range 0-127 for the values of FEC Encoding IDs for Fully-Specified FEC schemes and the range 128-255 for the values of Under-Specified FEC schemes. -6.2 FEC Object Transmission Information +6.2. FEC Object Transmission Information The FEC Object Transmission Information contains information which is essential to the decoder in order to decode the encoded object. It may also contain information which is required to decode certain groups of encoding symbols, for example individual Source Blocks within the object. This information is communicated reliably by the CDP to the receiver(s) as described in Section 8. The FEC Object Transmission Information may consist of several elements and each element may be one of three types, as follows: Mandatory: These elements are defined in this specification and are - mandatory for all FEC Schemes. Each FEC scheme specifies how the - values of the Mandatory FEC Object Transmission Information - elements are determined and each CDP specifies how this - information is encoded and reliably communicated to the - receiver(s). The Mandatory FEC Object Transmission Information - includes the identification of the FEC Scheme, which is needed by - the receiver to determine whether it supports the FEC Scheme. + each mandatory for at least one of the two types of FEC Scheme. + Each FEC scheme specifies how the values of the Mandatory FEC + Object Transmission Information elements are determined and each + CDP specifies how this information is encoded and reliably + communicated to the receiver(s). The Mandatory FEC Object + Transmission Information includes the identification of the FEC + Scheme, which is needed by the receiver to determine whether it + supports the FEC Scheme. Common: These elements are defined in this specification and are optional to be used by an FEC scheme. Each FEC scheme specifies which of the Common FEC Object Transmission Information elements it uses and how the values of these elements are determined. Each FEC scheme also specifies an encoding format for the information. Each CDP must specify at least one of the following: 1. A means to reliably communicated the Common FEC Object Transmission Information elements to the receiver(s) using the @@ -486,138 +432,140 @@ specify how the length of the Scheme-specific FEC Object Transmission Information can be determined by the receiver. Note that although from the point of view of this specification and of CDPs there is only a single Scheme-specific FEC Object Transmission Information element, the FEC scheme may specify this element to contain multiple distinct pieces of information. The Mandatory and Common FEC Object Transmission Information elements are defined in the sections below. -6.2.1 Transport of Object Transmission Information +6.2.1. Transport of FEC Object Transmission Information - It is the responsibility of the CDP to reliably transport the Object - Transmission Information to the receiver(s). + It is the responsibility of the CDP to reliably transport the FEC + Object Transmission Information to the receiver(s). It is important to note that the encoding format of the Mandatory FEC Object Transmission Information elements (The FEC Encoding ID and FEC Instance ID) is defined by the CDP. This is so that the receiver can identify the FEC Scheme to be used for interpreting the remaining FEC Object Transmission Information elements. All CDPs must define encoding formats for all the Mandatory FEC Object Transmission Information elements. Common FEC Object Transmission Information elements can be transported in two different ways: (a) the FEC Scheme defines an - encoding format for each Common Object Transmission Information - element and the CDP transports it, or (b) the CDP defines an encoding - format and transports the information in this format. + encoding format for each Common FEC Object Transmission Information + element that it uses and the CDP transports it, or (b) the CDP + defines an encoding format and transports the information in this + format. An FEC Scheme MUST define encoding formats for the Common FEC Object - Transmission Information elements. A CDP MAY define encoding formats - for the Common FEC Object Transmission Information elements. The CDP - determines which way the Common FEC Object Transmission Information - elements shall be transported, (a) or (b). Note that a CDP may - provide support for one or both options. + Transmission Information elements that it uses. A CDP MAY define + encoding formats for the Common FEC Object Transmission Information + elements. The CDP determines which way the Common FEC Object + Transmission Information elements shall be transported, (a) or (b). + + Note that a CDP may provide support for one or both options. In the case that the CDP uses the encoding formats specified by the FEC scheme then it may simply concatenate the encoding formats defined by the FEC scheme or it may carry each element in a seperate field or wrapper within the CDP. The FEC scheme must define the encoding formats of the Common FEC Object Transmission Information - elements in such a way that the length of each element is either - fixed or can be determined from the encoded data itself. + elements that it uses in such a way that the length of each element + is either fixed or can be determined from the encoded data itself. The encoding format of the Scheme-specific FEC Object Transmission Information element is defined by the FEC scheme. CDPs specify only how the resulting byte sequence is communicated. As with encoding formats for the Common FEC Oject Transmission Information elements the length of the Scheme-specific FEC Object Transmission Information must either be fixed or it must be possible to determine the length from the encoded data itself. -6.2.2 Opacity of Object Transmission Information +6.2.2. Opacity of FEC Object Transmission Information The Scheme-specific FEC Object Transmission Information element is opaque to the CDP in the sense that inspecting the contents of this element can only be done if FEC scheme-specific logic is included in the CDP. The encoding formats defined by the FEC scheme for the Common FEC Object Transmission Information elements are also opaque to the CDP in the same sense. The encoding formats defined by the CDP for the Common FEC Object Transmission Information elements are not opaque in this sense, although it must be considered that different FEC Schemes may use different combinations of the Common FEC Object Transmission Information elements. -6.2.3 Mandatory FEC Object Transmission Information elements +6.2.3. Mandatory FEC Object Transmission Information elements The Mandatory FEC Object Transmission Information elements are: FEC Encoding ID: an integer between 0 and 255 inclusive identifying a specific FEC scheme (Fully-Specified or Under-Specified.) FEC Instance ID (if the FEC Encoding ID identifies an Under-Specified FEC scheme): an integer between 0 and 65535 inclusive identifying an instance of an Under-specifed FEC scheme -6.2.4 Common FEC Object Transmission Information elements +6.2.4. Common FEC Object Transmission Information elements The Common FEC Object Transmission Information elements are described below. Note that this specification does not provide complete definitions of these fields. Instead only aspects of the abstract type are defined. The precise type and semantics are defined for each FEC scheme in the FEC scheme specification. Transfer-Length: a non-negative integer indicating the length of the object in bytes Encoding-Symbol-Length: a non-negative integer indicating the length of each encoding symbol in bytes Maximum-Source-Block-Length: a non-negative integer indicating the maximum number of source symbols in a source block Max-Number-of-Encoding-Symbols: a non-negative integer indicating the maximum number of encoding symbols (i.e. source plus repair symbols in the case of a systematic code) - FEC Schemes define the precise type of these elements and in - particular may restrict the value range of each element. FEC Schemes - also define an encoding format for each of the above elements that - they require. CDPs may also provide an encoding format for each - element in which case this encoding format MUST be capable of - representing values up to (2^^48)-1 in the case of the Transfer- - Length and up to (2^^32)-1 for the other elements. CDPs may + FEC Schemes define the precise type of those of the above elements + that they use and in particular may restrict the value range of each + element. FEC Schemes also define an encoding format for each of the + above elements that they use. CDPs may also provide an encoding + format for each element in which case this encoding format MUST be + capable of representing values up to (2^^48)-1 in the case of the + Transfer-Length and up to (2^^32)-1 for the other elements. CDPs may additionally or alternatively provide a mechanism to transport these elements encoded according to the encoding format defined by the FEC - scheme. For example, FLUTE [9] specifies an XML-based encoding + scheme. For example, FLUTE [8] specifies an XML-based encoding format for these elements, but can also transport FEC scheme-specific encoding formats within the EXT-FTI header extension. -6.2.5 Scheme-specific FEC Object Transmission Information element +6.2.5. Scheme-specific FEC Object Transmission Information element The Scheme-specific FEC Object Transmission Information element may be used by an FEC Scheme to communicate information which is essential to the decoder which cannot adequately be represented within the Mandatory or Common FEC Object Transmission Information elements. From the point of view of a CDP, the Scheme-specific FEC Object Transmission Information element is an opaque, variable length, bitstring. The FEC Scheme defines the structure of this bitstring, which may contain multiple distinct elements. -6.3 FEC Payload ID +6.3. FEC Payload ID The FEC Payload ID contains information which indicates to the FEC decoder the relationships between the encoding symbols carried by a particular packet and the FEC encoding transformation. For example if the packet carries source symbols then the FEC Payload ID indicates which source symbols of the object are carried by the packet. If the packet carries repair symbols, then the FEC Payload ID indicates how those repair symbols were constructed from the object. @@ -666,41 +614,44 @@ symbol. 3. The type and semantics of the FEC Object Transmission Information. The FEC Scheme MAY define additional restrictions on the type (including value range) of the Common FEC Object Transmission Information elements. 4. An encoding format for the Common FEC Object Transmission Information elements used by the FEC Scheme. - Fully-specified FEC schemes MUST further specify: + Fully-Specified FEC schemes MUST further specify: 1. A full specification of the FEC code. This specification MUST precisely define the valid FEC Object Transmission Information values, the valid FEC Payload ID values and the valid packet payload sizes for any given object (where packet payload refers to the space - not necessarily contiguous - within a packet dedicated to carrying encoding symbol bytes). - Furthermore, given an object, a valid Object Transmission - Information value, a valid FEC Payload ID value and a valid - packet payload size, the specification MUST uniquely define the - values of the encoding symbol bytes to be included in the packet + + Furthermore, given an object, valid values for each of the FEC + Object Transmission Information elements used by the FEC Scheme, + a valid FEC Payload ID value and a valid packet payload size, the + specification MUST uniquely define the values of the encoding + symbol bytes to be included in the packet payload of a packet with the given FEC Payload ID value. A common and simple way to specify the FEC code to the required level of detail is to provide a precise specification of an - encoding algorithm which, given an object, a valid FEC Object - Transmission Information for the object, a valid FEC Payload ID - and packet payload length as input produces the exact value of - the encoding symbol bytes as output. + encoding algorithm which, given an object, valid values for each + of the FEC Object Transmission Information elements used by the + FEC Scheme for the object, a valid FEC Payload ID and packet + payload length as input produces the exact value of the encoding + symbol bytes as output. 2. A description of practical encoding and decoding algorithms. This description need not be to the same level of detail as for (1) above, however it must be sufficient to demonstrate that encoding and decoding of the code is both possible and practical. FEC scheme specifications MAY additionally define the following: 1. Type, semantics and encoding format of a Scheme-specific FEC @@ -773,53 +724,53 @@ A specification for a CDP that uses this building block MUST include the following things: 1. Definitions of encoding formats for the Mandatory FEC Object Transmission Information elements. 2. A means to reliably communicate the Mandatory FEC Object Transmission Information elements from sender to receiver(s) using the encoding format defined in (1). - 3. A means to reliably communicate the Scheme-specific FEC Object - Transmission Information element from sender to receiver(s) using - the encoding format of the Scheme-specific FEC Object - Transmission Information element defined by the FEC scheme. - - 4. Means to reliably communicate the Common FEC Object Transmission + 3. Means to reliably communicate the Common FEC Object Transmission Information element from sender to receiver(s) using either or both of (a) encoding formats defined by the FEC Scheme or (b) encoding formats defined by the CDP + 4. A means to reliably communicate the Scheme-specific FEC Object + Transmission Information element from sender to receiver(s) using + the encoding format of the Scheme-specific FEC Object + Transmission Information element defined by the FEC scheme. + 5. A means to communicate the FEC Payload ID in association with a data packet. Note that the encoding format of the FEC Payload ID is defined by the FEC Scheme. - If option (b) of (4) above is used, then the CDP MUST specify an + If option (b) of (3) above is used, then the CDP MUST specify an encoding format for the Common FEC Object Transmission Information elements. CDPs MAY additionally specify the following things: 1. A means to indicate whether the FEC Payload ID within a packet is encoded according to the format for packets including only source symbols or according to the format for packets including at least one repair symbol. 9. Common algorithms This section describes certain algorithms which are expected to be commonly required by FEC schemes or by CDPs. FEC Schemes and CDPs SHOULD use these algorithms in preference to scheme or protocol specific algorithms where appropriate. -9.1 Block partitioning algorithm +9.1. Block partitioning algorithm This algorithm computes a partitioning of a object into source blocks so that all source blocks are as close to being equal length as possible. A first number of source blocks are of the same larger length, and the remaining second number of source blocks of the same smaller length. This algorithm is described in two steps, the second of which may be useful in itself as an independent algorithm in some cases. In the first step, the number of source symbols (T) and the number of source @@ -827,54 +778,54 @@ Source Block Length (B) and Symbol Length (E). In the second step, the partitioning of the object is derived from the number of source symbols (T) and the number of source blocks (N). The partitioning is defined in terms of a first number of source blocks (I), a second number of source blocks (N-I), the length of each of the first source blocks (A_large) and the length of each of the second source blocks (A_small). This algorithm is identical to the one specified in Section 5.1.2.3 - of FLUTE [9] + of FLUTE [8] The following notation is used in the description below: ceil[x] denotes x rounded up to the nearest integer. floor[x] denotes x rounded down to the nearest integer. -9.1.1 First Step +9.1.1. First Step Input: B -- Maximum Source Block Length, i.e., the maximum number of source symbols per source block - L -- Transfer Length in bytes + L -- Transfer Length in bytes E -- Encoding Symbol Length in bytes Output: T -- the number of source symbols in the object. N -- The number of source blocks into which the object shall be partitioned. Algorithm: 1. The number of source symbols in the transport object is computed as T = ceil[L/E]. 2. The transport object shall be partitioned into N = ceil[T/B] source blocks. -9.1.2 Second step +9.1.2. Second step Input: T -- the number of source symbols in the object. N -- The number of source blocks into which the object is partitioned. Output: @@ -896,50 +847,50 @@ Each of the first I source blocks then consists of A_large source symbols, each source symbol is E bytes in length. Each of the remaining N-I source blocks consist of A_small source symbols, each source symbol is E bytes in length except that the last source symbol of the last source block is L-(((L-1)/E) rounded down to the nearest integer)*E bytes in length. 10. Requirements from other building blocks The FEC building block does not provide any support for congestion - control. Any complete protocol MUST provide congestion control that - conforms to [5], and thus this MUST be provided by another building - block when the FEC building block is used in a protocol. + control. Any complete CDP MUST provide congestion control that + conforms to [6], and thus this MUST be provided by another building + block when the FEC building block is used in a CDP. There are no other specific requirements from other building blocks - for the use of this FEC building block. However, any protocol that - uses the FEC building block will inevitably use other building blocks - for example to provide support for sending higher level session - information within data packets containing FEC encoding symbols. + for the use of this FEC building block. However, any CDP that uses + the FEC building block may use other building blocks for example to + provide support for sending higher level session information within + data packets containing FEC encoding symbols. 11. Security Considerations Data delivery can be subject to denial-of-service attacks by attackers which send corrupted packets that are accepted as legitimate by receivers. This is particularly a concern for multicast delivery because a corrupted packet may be injected into the session close to the root of the multicast tree, in which case the corrupted packet will arrive to many receivers. This is particularly a concern for the FEC building block because the use of even one corrupted packet containing encoding data may result in the decoding of an object that is completely corrupted and unusable. It is thus RECOMMENDED that the decoded objects be checked for integrity before delivering objects to an application. For example, an MD5 - hash [6] of an object may be appended before transmission, and the + hash [7] of an object may be appended before transmission, and the MD5 hash is computed and checked after the object is decoded but before it is delivered to an application. Moreover, in order to obtain strong cryptographic integrity protection a digital signature verifiable by the receiver SHOULD be computed on top of such a hash value. It is also RECOMMENDED that a packet authentication protocol - such as TESLA [10] be used to detect and discard corrupted packets + such as TESLA [9] be used to detect and discard corrupted packets upon arrival. Furthermore, it is RECOMMENDED that Reverse Path Forwarding checks be enabled in all network routers and switches along the path from the sender to receivers to limit the possibility of a bad agent successfully injecting a corrupted packet into the multicast tree data path. Another security concern is that some FEC information may be obtained by receivers out-of-band in a session description, and if the session description is forged or corrupted then the receivers will not use the correct protocol for decoding content from received packets. To @@ -955,44 +906,44 @@ hierarchical: FEC Encoding IDs scope independent ranges of FEC Instance IDs. Only FEC Encoding IDs that correspond to Under- Specified FEC schemes scope a corresponding set of FEC Instance IDs. The FEC Encoding ID and FEC Instance IDs are non-negative integers. In this document, the range of values for FEC Encoding IDs is 0 to 255. Values from 0 to 127 are reserved for Fully-Specified FEC schemes and Values from 128 to 255 are reserved for Under-Specified FEC schemes, as described in more detail in Section 6.1. -12.1 Explicit IANA Assignment Guidelines +12.1. Explicit IANA Assignment Guidelines This document defines a name-space for FEC Encoding IDs named: ietf:rmt:fec:encoding The values that can be assigned within the "ietf:rmt:fec:encoding" name-space are numeric indexes in the range [0, 255], boundaries included. Assignment requests are granted on a "IETF Consensus" - basis as defined in [8]. + basis as defined in [2]. This document also defines a name-space for FEC Instance IDs named: ietf:rmt:fec:encoding:instance The "ietf:rmt:fec:encoding:instance" name-space is a sub-name-space associated with the "ietf:rmt:fec:encoding" name-space. Each value of "ietf:rmt:fec:encoding" assigned in the range [128, 255] has a separate "ietf:rmt:fec:encoding:instance" sub-name-space that it scopes. Values of "ietf:rmt:fec:encoding" in the range [0, 127] do not scope a "ietf:rmt:fec:encoding:instance" sub-name-space. The values that can be assigned within each "ietf:rmt:fec:encoding: instance" sub-name-space are non-negative integers less than 65536. Assignment requests are granted on a "First Come First Served" basis - as defined in [8]. The same value of "ietf:rmt:fec:encoding: + as defined in [2]. The same value of "ietf:rmt:fec:encoding: instance" can be assigned within multiple distinct sub-name-spaces, i.e., the same value of "ietf:rmt:fec:encoding:instance" can be used for multiple values of "ietf:rmt:fec:encoding". Requestors of "ietf:rmt:fec:encoding:instance" assignments MUST provide the following information: o The value of "ietf:rmt:fec:encoding" that scopes the "ietf:rmt: fec:encoding:instance" sub-name-space. This must be in the range [128, 255]. @@ -1004,68 +955,65 @@ rmt:fec:encoding:instance" assigned, and a way to obtain it (e.g., a pointer to a publicly available reference-implementation or the name and contacts of a company that sells it, either separately or embedded in a product). It is the responsibility of the requestor to keep all the above information up to date. 13. Acknowledgments - This document is largely based on RFC3452 [2] and thus thanks are due + This document is largely based on RFC3452 [3] and thus thanks are due to the additional authors of that document: J. Gemmell, L. Rizzo, M. Handley, J. Crowcroft. 14. References +14.1. Normative References + [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. - [2] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., + [2] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA + Considerations Section in RFCs", BCP 26, RFC 2434, October 1998. + +14.2. Informative References + + [3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and J. Crowcroft, "Forward Error Correction (FEC) Building Block", RFC 3452, December 2002. - [3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., + [4] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and J. Crowcroft, "The Use of Forward Error Correction (FEC) in Reliable Multicast", RFC 3453, December 2002. - [4] Kermode, R. and L. Vicisano, "Author Guidelines for Reliable + [5] Kermode, R. and L. Vicisano, "Author Guidelines for Reliable Multicast Transport (RMT) Building Blocks and Protocol Instantiation documents", RFC 3269, April 2002. - [5] Mankin, A., Romanov, A., Bradner, S., and V. Paxson, "IETF + [6] Mankin, A., Romanov, A., Bradner, S., and V. Paxson, "IETF Criteria for Evaluating Reliable Multicast Transport and Application Protocols", RFC 2357, June 1998. - [6] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, + [7] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 1992. - [7] Masinter, L., "Hyper Text Coffee Pot Control Protocol - (HTCPCP/1.0)", RFC 2324, April 1998. - - [8] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA - Considerations Section in RFCs", BCP 26, RFC 2434, - October 1998. - - [9] Paila, T., Luby, M., Lehtonen, R., Roca, V., and R. Walsh, + [8] Paila, T., Luby, M., Lehtonen, R., Roca, V., and R. Walsh, "FLUTE - File Delivery over Unidirectional Transport", RFC 3926, October 2004. - [10] Perrig, A., Cametti, R., Song, D., and J. Tygar, "Efficient and - Secure Source Authentication for Multicast", February 2001. - - Network and Distributed System Security Symposium - - NDDS 2001 - pp. 35-46 + [9] Perrig, A., Song, D., Canetti, R., Tygar, J., and B. Briscoe, + "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): + Multicast Source Authentication Transform Introduction", + RFC 4082, June 2005. - [11] Whetten, B., Vicisano, L., Kermode, R., Handley, M., Floyd, S., + [10] Whetten, B., Vicisano, L., Kermode, R., Handley, M., Floyd, S., and M. Luby, "Reliable Multicast Transport Building Blocks for One-to-Many Bulk-Data Transfer", RFC 3048, January 2001. Authors' Addresses Mark Watson Digital Fountain 39141 Civic Center Drive Suite 300 Fremont, CA 94538