--- 1/draft-ietf-rmt-fec-bb-revised-01.txt 2006-02-04 17:26:05.000000000 +0100 +++ 2/draft-ietf-rmt-fec-bb-revised-02.txt 2006-02-04 17:26:05.000000000 +0100 @@ -1,20 +1,20 @@ Reliable Multicast M. Watson Internet-Draft M. Luby -Expires: March 5, 2006 Digital Fountain +Expires: April 21, 2006 Digital Fountain L. Vicisano Cisco Systems, Inc. - September 1, 2005 + October 18, 2005 Forward Error Correction (FEC) Building Block - draft-ietf-rmt-fec-bb-revised-01 + draft-ietf-rmt-fec-bb-revised-02 Status of this Memo 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 @@ -25,21 +25,21 @@ 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 March 5, 2006. + This Internet-Draft will expire on April 21, 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 @@ -74,52 +74,54 @@ 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 + 10. Requirements from other building blocks . . . . . . . . . . . 23 + 11. Security Considerations . . . . . . . . . . . . . . . . . . . 24 + 12. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25 + 12.1. Explicit IANA Assignment Guidelines . . . . . . . . . . . 25 + 13. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27 + 14. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28 + 14.1. Normative References . . . . . . . . . . . . . . . . . . . 28 + 14.2. Informative References . . . . . . . . . . . . . . . . . . 28 + Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 29 + Intellectual Property and Copyright Statements . . . . . . . . . . 30 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 [10]. This document is a product of the IETF RMT WG and follows the general guidelines 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 + codes/schemes, 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. + several distinct protocol mechanisms and may support any kind of + application requiring reliable transport - for example object + delivery and streaming applications. 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. @@ -156,21 +158,21 @@ FEC: Forward Error Correction 3. Requirements notation The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [1]. 4. Rationale - FEC codes are a valuable basic component of any CDP that is to + An FEC code is a valuable basic component of any CDP that is to 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 @@ -344,21 +346,21 @@ 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. + ID and 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-specific FEC Object Transmission Information element with the exception of the instance- @@ -366,24 +368,24 @@ 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 identify a single scheme instance that has at least one implementation. The party that owns this tuple MUST be able to - 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 + provide information on how to obtain 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 The FEC Object Transmission Information contains information which is essential to the decoder in order to decode the encoded object. It @@ -401,168 +403,176 @@ 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: + it uses and how the values of these elements are determined. - 1. A means to reliably communicated the Common FEC Object + Scheme-specific: An FEC scheme may specify a single Scheme-specific + FEC Object Transmission Information element. The FEC scheme + specifies the type, semantics and encoding format of the Scheme- + specific FEC Object Transmission Information element. The + resulting byte-string is known as the "encoded Scheme-specific FEC + Object Transmission Information". Each CDP specifies how the + encoded Scheme-specific FEC Object Transmission is communicated + reliably to the receiver(s) i.e. exactly where it shall be carried + within packets of the CDP. 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. + + Each FEC scheme specifies an encoding format for the Common and + Scheme-specific FEC Object Transmission Information. Each CDP must + specify at least one of the following: + + 1. A means to reliably communicate the Common FEC Object Transmission Information elements to the receiver(s) using the encoding format defined by the FEC scheme. 2. An alternative, CDP specific, encoding format for each of the Common FEC Object Transmission Information elements. - Scheme-specific: An FEC scheme may specify a single Scheme-specific - FEC Object Transmission Information element. The FEC scheme - specifies the type, semantics and encoding format of the Scheme- - specific FEC Object Transmission Information element. The - encoding format may assume that the receiver can determine the - length of the Scheme-specific FEC Object Transmission Information - element from information communicated outside that element. Each - CDP specifies how the Scheme-specific FEC Object Transmission - Element is communicated reliably to the receiver(s) i.e. exactly - where it shall be carried within packets of the CDP. CDPs also - 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 FEC Object Transmission Information 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. + Object Transmission Information elements (The FEC Encoding 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 the Mandatory FEC Object Transmission Information + element. Common FEC Object Transmission Information elements can be transported in two different ways: (a) the FEC Scheme defines an - 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 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). + encoding format for the Common FEC Object Transmission Information + elements that it uses and the CDP transports this encoded data block, + or (b) the CDP defines an encoding format for each Common FEC Object + Transmission Information element and transports the information in + this format. - Note that a CDP may provide support for one or both options. + An FEC Scheme MUST define an encoding format for the Common FEC + Object Transmission Information elements that it uses. The resulting + byte string is known as the "encoded Common FEC Object Transmission + Information". A CDP MAY define individual encoding formats for each + of 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 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. + In the case that the CDP uses the encoding format specified by the + FEC scheme then it may simply concatenate the encoded Common FEC + Object Transmission Information and the encoded Scheme-specific FEC + Object Transmission Information or it may carry each in a seperate + field or wrapper within the CDP. In the former case, the + concatenated byte-string is known as the encoded FEC Object + Transmission Information. The FEC scheme must define the encoding + format for the Common FEC Object Transmission Information 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. + how the resulting byte sequence is communicated. As with the + encoding format 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 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 - The Mandatory FEC Object Transmission Information elements are: + The Mandatory FEC Object Transmission Information element is: 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 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. + below. Note that with the exception of the FEC Instance ID, 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. + + FEC Instance ID: an integer between 0 and 65535 inclusive identifying + an instance of an Under-specifed FEC scheme 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) + The FEC Instance ID MUST be used by all Under-specified FEC schemes + and MUST NOT be used by Fully-specified FEC Schemes. + 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 [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. + element. FEC Schemes also define an encoding format for the subset + 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^^16)-1 in the case of + the FEC Instance ID, (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 the encoded Common FEC + Object Transmission information defined by the FEC 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 LCT header extension. 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, + Transmission Information element is an opaque, variable length, byte + string. The FEC Scheme defines the structure of this byte string, which may contain multiple distinct elements. 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 @@ -685,24 +695,20 @@ 2. Formats and Codes 2.1 FEC Payload ID(s) 2.2 FEC Object Transmission Information 2.2.1 Mandatory - - 2.2.2 Common 2.2.3 Scheme-Specific 3. Procedures