Internet Engineering Task Force RMT WG INTERNET-DRAFT M. Luby draft-luby-rmt-bb-fec-supp-simple-00.txt Digital Fountain 7 June 2004 Expires: December 2004 Simple Forward Error Correction (FEC) Schemes Status of this Document This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026 [1]. 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 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 a "work in progress". The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt To view the list Internet-Draft Shadow Directories, see http://www.ietf.org/shadow.html. This document is a product of the IETF RMT WG. Comments should be addressed to the authors, or the WG's mailing list at rmt@lbl.gov. Abstract This document introduces some Forward Error Correction (FEC) schemes that supplement the FEC schemes described in RFC 3452 [4] and RFC 3695 [5]. The primary benefits of these additional FEC schemes are that they are designed for reliable bulk delivery of objects using a simpler FEC Payload ID, and in particular they can be used to deliver objects without using any explicit source block structure. Thus, they allow simpler delivery with less packet header overhead. Luby [Page 1] ^L INTERNET-DRAFT Expires: December 2004 June 2004 This document also describes the Fully-Specified FEC scheme corresponding to FEC Encoding ID 1. This Fully-Specified FEC scheme requires no FEC coding and delivers the object without any source block structure, and is introduced primarily to allow simple interoperability testing between different implementations of protocol instantiations that use the FEC building block. Luby [Page 2] ^L INTERNET-DRAFT Expires: December 2004 June 2004 Table of Contents 1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Packet Header Fields. . . . . . . . . . . . . . . . . . . . . . . 5 2.1. FEC Payload ID for FEC Encoding IDs 1 and 131. . . . . . . . . 5 2.2. Simple No-Code FEC scheme. . . . . . . . . . . . . . . . . . . 5 2.3. Simple FEC scheme. . . . . . . . . . . . . . . . . . . . . . . 6 3. Simple No-Code FEC scheme . . . . . . . . . . . . . . . . . . . . 7 3.1. Object Logistics . . . . . . . . . . . . . . . . . . . . . . . 8 3.2. Sending and Receiving an Object. . . . . . . . . . . . . . . . 9 4. Usage Example . . . . . . . . . . . . . . . . . . . . . . . . . . 10 5. Security Considerations . . . . . . . . . . . . . . . . . . . . . 10 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 10 7. Normative References. . . . . . . . . . . . . . . . . . . . . . . 11 8. Informative References. . . . . . . . . . . . . . . . . . . . . . 12 9. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . . . 12 10. Full Copyright Statement . . . . . . . . . . . . . . . . . . . . 13 Luby [Page 3] ^L INTERNET-DRAFT Expires: December 2004 June 2004 1. Introduction This document describes two new Forward Error Correction (FEC) schemes corresponding to FEC Encoding IDs 1 and 131 which supplement the FEC schemes corresponding to FEC Encoding IDs 128 and 129 described in RFC 3452 [4] and the FEC schemes corresponding to FEC Encoding IDs 0 and 130 described in RFC 3695 [5]. The new FEC schemes allow a simpler delivery scheme when an object is not explicitly partitioned into source blocks. If there is an implicit source block structure (which may be the case for FEC Encoding ID 131) then this source block structure can implicitly determined based on the FEC Object Transmission Information and the FEC Instance ID, which allows more flexibility and saves the additional overhead of carrying one or more source block numbers within the FEC Payload ID of each packet. The new FEC schemes are similar to the FEC schemes with FEC Encoding ID 128 defined in RFC 3452 [4], except that the FEC Payload ID is simpler (and shorter) and only carries the Encoding Symbol ID and not the Source Block Number. This is the reason that these new FEC schemes are called Simple FEC schemes. The primary focus of FEC Encoding IDs 128 and 129 is to reliably deliver bulk objects of known length. The FEC schemes described in this document are designed with the same primary focus. In the spirit of a building block (see RFC 3048 [7]), the FEC schemes described in this document can be used to provide reliability for other service models as well. The two new FEC Encoding IDs 1 and 131 are described in Section 2, and this supplements Section 5 of the FEC building block [4]. Section 3 of this document describes the Fully-Specified FEC scheme corresponding to the FEC Encoding ID 1. This Fully-Specified FEC scheme requires no FEC coding and is specified primarily to allow simple interoperability testing between different implementations of protocol instantiations that use the FEC building block. This document inherits the context, language, declarations and restrictions of the FEC building block [4]. This document also uses the terminology of the companion document [10] which describes the use of FEC codes within the context of reliable IP multicast transport and provides an introduction to some commonly used FEC codes. Building blocks are defined in RFC 3048 [7]. This document is a product of the IETF RMT WG and follows the general guidelines provided in RFC 3269 [3]. The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this Luby Section 1. [Page 4] ^L INTERNET-DRAFT Expires: December 2004 June 2004 document are to be interpreted as described in RFC 2119 [2]. 2. Packet Header Fields This section specifies FEC Encoding IDs 1 and 131 and the associated FEC Payload ID formats and the specific information in the corresponding FEC Object Transmission Information. The FEC scheme associated with FEC Encoding ID 1 is Fully-Specified whereas the FEC schemes associated with FEC Encoding ID 131 are Under-Specified. FEC Encoding IDs 1 and 131 have the same FEC Payload ID format, which is described in the following subsection. The FEC Object Transmission Information for FEC Encoding IDs 1 and 131 is different, and is described in the subsequent two subsections. 2.1. FEC Payload ID for FEC Encoding IDs 1 and 131 The FEC Payload ID for FEC Encoding IDs 1 and 131 is composed of an Encoding Symbol ID structured as follows: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Encoding Symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The 32-bit Encoding Symbol ID identifies the specific encoding symbol(s) generated from the object that is (are) carried in the packet payload. The exact details of the correspondence between Encoding Symbol IDs and the encoding symbols in the packet payload for FEC Encoding ID 1 are specified in Section 3. The exact details of the correspondence between Encoding Symbol IDs and the encoding symbol(s) in the packet payload for FEC Encoding ID 131 are dependent on the particular encoding algorithm used as identified by the FEC Encoding ID and by the FEC Instance ID. 2.2. Simple No-Code FEC scheme This subsection reserves FEC Encoding ID 1 for the Simple No-Code FEC scheme that is described in this subsection and in Section 3. This is a Fully-Specified FEC scheme that is primarily intended to be used for simple interoperability testing between different implementations of protocol instantiations that use the FEC building block. The value of this FEC scheme is that no FEC encoding or decoding is required to Luby Section 2.2. [Page 5] ^L INTERNET-DRAFT Expires: December 2004 June 2004 implement it and therefore it is easy to test interoperability between protocols that may use different proprietary FEC schemes in production in their first implementations. The FEC Payload ID format for FEC Encoding ID 1 is described in Subsection 2.1. The FEC Object Transmission Information has the following specific information: o The FEC Encoding ID 1. o The length in bytes of the encoding symbol carried in the packet payload. This length MUST be the same for all packets sent for the object. o The length of the object in bytes. For convenience, the object length MAY be a multiple of the length of the encoding symbol carried in one packet payload. How this out-of-band information is communicated is outside the scope of this document. 2.3. Simple FEC scheme This subsection reserves FEC Encoding ID 131 for the Simple FEC scheme that is described in this subsection. This is an Under-Specified FEC scheme. This FEC scheme is similar in spirit to the Simple No-Code FEC scheme, except that a non-trivial FEC encoding (that is Under-Specified) may be used to generate encoding symbol(s) placed in the payload of each packet and a corresponding FEC decoder may be used to produce the object from received packets. Furthermore, a Simple FEC scheme MAY implicitly partition the file into source blocks, and it MAY send more than one encoding symbol, potentially for different source blocks, in each packet payload. In this case, the Encoding Symbol ID carried as the FEC Payload ID in each packet together with the FEC Object Transmission Information and FEC Instance ID MUST be sufficient for a receiver to determine how the encoding symbols carried in the packet were generated from the object. Any such implicit partitioning of the object into source blocks and sending of more than one encoding symbol in each packet payload is FEC Instance ID specific. The FEC Payload ID format for FEC Encoding ID 131 is described in Subsection 2.1. The FEC Object Transmission Information has the Luby Section 2.3. [Page 6] ^L INTERNET-DRAFT Expires: December 2004 June 2004 following specific information: o The FEC Encoding ID 131. o The FEC Instance ID associated with the FEC Encoding ID 131 to be used. o The aggregate length of the encoding symbol(s) carried in one packet payload. This length MUST be the same for all packets sent for the same object. o The length of the object in bytes. o The maximum source block length in bytes. For convenience, the object length and the maximum source block length MAY be a multiple of the aggregate length of the encoding symbol(s) carried in one packet payload. How this out-of-band information is communicated is outside the scope of this document. 3. Simple No-Code FEC scheme In this section we describe a Fully-Specified FEC scheme corresponding to FEC Encoding ID 1. The primary purpose for introducing this FEC schemes is to allow simple interoperability testing between different implementations of the same protocol instantiation that uses the FEC building block. The Simple No-Code FEC scheme does not require FEC encoding or decoding. Instead, each encoding symbol consists of consecutive bytes of the object. It is very similar to the Compact No-Code FEC scheme with FEC Encoding ID 0 described in [5]. The difference is that the Simple No- Code FEC scheme does not partition the object into source blocks, i.e., it treats the object as a single source block. The FEC Payload ID consists the 32-bit Encoding Symbol ID, as described in Subsection 2.1. The length of the Encoding Symbol ID was chosen to be the same for FEC Encoding IDs 1 and 131, and because of this testing interoperability of the FEC scheme associated with FEC Encoding ID 1 provides a first basic step to testing interoperability of an FEC scheme Luby Section 3. [Page 7] ^L INTERNET-DRAFT Expires: December 2004 June 2004 associated with FEC Encoding ID 131. The next two subsections describe the details of how the Simple No-Code FEC scheme operates for an object. These subsections are not meant to suggest a particular implementation, but just to illustrate the general algorithm through the description of a simple, non-optimized implementation. 3.1. Object Logistics Let X > 0 be the length of an object in bytes. The value of X is part of the FEC Object Transmission Information, and how this information is communicated to a receiver is outside the scope of this document. Let L > 0 be the length of the encoding symbol contained in the payload of each packet. There are several possible ways the length of the encoding symbol L can be communicated to the receiver, and how this is done is outside the scope of this document. As an example, a sender could fix the packet payload length to be L in order to place the encoding symbol of length L into the packet, and then a receiver could infer the value of L from the length of the received packet payload. It is REQUIRED that L be the same for all packets sent for the same object but MAY be different for different objects. For a given object X bytes in length, let N = X/L rounded up to the nearest integer. The encoding symbol carried in the payload of a packet consists of a consecutive portion of the object. The object is logically partitioned into N encoding symbols, each L bytes in length, and the corresponding Encoding Symbol IDs range from 0 through N-1 starting at the beginning of the object and proceeding to the end. Thus, the encoding symbol with Encoding Symbol ID Y consists of bytes L*Y through L*(Y+1)-1 of the object, where the bytes of the object are numbered from 0 through X-1. If X/L is not integral then the last encoding symbol with Encoding Symbol ID = N-1 consists of bytes L*(N-1) through the last byte X-1 of the object, and the remaining L*N - X bytes of the encoding symbol can by padded out with zeroes. As an example, suppose that the object length X = 20,400 and encoding symbol length L = 1,000. The encoding symbol with Encoding Symbol ID = 10 contains bytes 10,000 through 10,999 of the object, and the encoding symbol with Encoding Symbol ID = 20 contains bytes 20,000 through the last byte 20,399 of the object and the remaining 600 bytes of the encoding symbol can be padded with zeroes. There are no restrictions beyond the rules stated above on how a sender Luby Section 3.1. [Page 8] ^L INTERNET-DRAFT Expires: December 2004 June 2004 generates encoding symbols to send from an object. However, it is recommended that an implementor of refer to the companion document [10] for general advice. In the next subsection a procedure is recommended for sending and receiving an object. 3.2. Sending and Receiving an Object The following carousel procedure is RECOMMENDED for a sender to generate packets containing FEC Payload IDs and corresponding encoding symbols for an object that is X bytes in length. Set the length in bytes of an encoding symbol to a fixed value L which is reasonable for a packet payload (e.g., ensure that the total packet size does not exceed the MTU) and that is smaller than the object length X, e.g., L = 1,000 for X >= 1,000. Set N = X/L rounded up to the nearest integer. Initialize Y to a value randomly chosen in the interval [0..N-1]. Repeat the following for each packet of the object to be sent. o If Y < N-1 then generate the encoding symbol consisting of the L bytes of the object numbered L*Y through L*(Y+1)-1. o If Y = N-1 then generate the encoding symbol consisting of the last X - L*(N-1) bytes of the object numbered L*(N-1) through X-1 followed by L*N - X padding bytes of zeroes. o Set the Encoding Symbol ID = Y in the packet (this is the FEC Payload ID), and put the encoding symbol into the packet payload to send. o In preparation for the generation of the next packet: if Y < N-1 then increment Y by one elseif Y = N-1 then reset Y to zero. The following procedure is RECOMMENDED for a receiver to recover the object based on receiving packets for the object from a sender that is using the carousel procedure describe above. Upon receipt of the first FEC Payload ID for an object, the receiver uses the FEC Object Transmission Information received out-of-band to determine the object length X in bytes, and allocates space for the X bytes that the object requires. The receiver also computes the length L of the encoding symbol(s) in the payload of the packet by subtracting the packet header length from the total length of the received packet (and the receiver checks that this length is the same in each subsequent received packet from the object). After calculating N = X/L rounded up to the nearest Luby Section 3.2. [Page 9] ^L INTERNET-DRAFT Expires: December 2004 June 2004 integer, the receiver allocates a boolean array RECEIVED[0..N-1] with all N entries initialized to false to track received encoding symbols. The receiver keeps receiving packets for the object as long as there is at least one entry in RECEIVED still set to false or until the application decides to give up on trying to receive this object. For each received packet for the object (including the first packet) the steps to be taken to help recover the object are as follows. Let Y be the value of the Encoding Symbol ID (which is the FEC Payload ID) of the packet. If Y < N-1 then the receiver copies the L bytes of the encoding symbol into bytes numbered L*Y through L*(Y+1)-1 of the space reserved for the object. If Y = N-1 then the receiver copies the first X - L*(N-1) bytes of the encoding symbol into bytes numbered L*(N-1) through X-1 of the space reserved for the object. In either case, the receiver sets RECEIVED[Y] = true. At each point in time, the receiver has successfully recovered bytes L*Y through min{L*(Y+1), X} - 1 of the object for all Y in the interval [0..N-1] for which RECEIVED[Y] is true. If all all N entries of RECEIVED are true then the receiver has recovered the entire object. 4. Usage Example The primary usage example for FEC Encoding IDs 1 and 131 is reliable bulk data delivery. In this model, one or more objects are to be reliably delivered to potentially multiple receivers using multicast (or broadcast, or unicast). The maximum length of an object that can be delivered is at most L times the number of distinct Encoding Symbols IDs, where L is the length in bytes of the encoding symbol(s) carried in the packet payload. Thus the maximum length of an object is 2^32 * L for FEC Encoding IDs 1 and 131. If for example L = 1 KB then the length of an object can be up to around 4 TB. 5. Security Considerations The security considerations for this document are the same as they are for RFC 3452 [4]. 6. IANA Considerations Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA registration. For general guidelines on IANA considerations as they apply to this document, see RFC 3452 [4]. This document assigns the Fully-Specified FEC Encoding ID 1 under the ietf:rmt:fec:encoding name- Luby Section 6. [Page 10] ^L INTERNET-DRAFT Expires: December 2004 June 2004 space to "Simple No-Code". The FEC Payload ID format and corresponding FEC Object Transmission Information associated with FEC Encoding ID 1 is described in Subsections 2.1 and 2.2, and the corresponding FEC scheme is described in Section 3. This document assigns the Under-Specified FEC Encoding ID 131 under the ietf:rmt:fec:encoding name-space to "Simple FEC". This document also establishes a new "FEC Instance ID" registry ietf:rmt:fec:encoding:instance:131 ietf:rmt:fec:encoding = 131 (Simple FEC) The FEC Payload ID format and corresponding FEC Object Transmission Information associated with FEC Encoding ID 131 is described in Subsections 2.1 and 2.3. 7. Normative References [1] Bradner, S., "The Internet Standards Process -- Revision 3", RFC 2026, October 1996. [2] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, March 1997. [3] Kermode, R., Vicisano, L., ``Author Guidelines for Reliable Multicast Transport (RMT) Building Blocks and Protocol Instantiation documents'', RFC 3269, April 2002. [4] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M. and J. Crowcroft, "Forward Error Correction (FEC) Building Block", RFC 3452, December 2002. [5] Luby, M. and Vicisano, L., "Compact Forward Error Correction (FEC) Schemes", RFC 3695, February 2004. [6] Mankin, A., Romanow, A., Bradner, S., Paxson V., "IETF Criteria for Evaluating Reliable Multicast Transport and Application Protocols", RFC 2357, June 1998. [7] Whetten, B., Vicisano, L., Kermode, R., Handley, M., Floyd, S., Luby, M., "Reliable Multicast Transport Building Blocks for One-to-Many Bulk-Data Transfer", RFC 3048, January 2001. Luby Section 7. [Page 11] ^L INTERNET-DRAFT Expires: December 2004 June 2004 8. Informative References [8] Luby, M., Gemmell, J., Vicisano, L., Rizzo, L. and J. Crowcroft, "Asynchronous Layered Coding (ALC) Protocol Instantiation", RFC 3450 December 2002. [9] Luby, M., Gemmell, J., Vicisano, L., Rizzo, L., Handley, M. and J. Crowcroft, "Layered Coding Transport (LCT) Building Block", RFC 3451 December 2002. [10] 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. 9. Authors' Addresses Michael Luby luby@digitalfountain.com Digital Fountain, Inc. 39141 Civic Center Drive Suite 300 Fremont, CA 94538 Luby Section 9. [Page 12] ^L INTERNET-DRAFT Expires: December 2004 June 2004 10. Full Copyright Statement Copyright (C) The Internet Society (2002). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE." Luby Section 10. [Page 13] ^L INTERNET-DRAFT Expires: December 2004 June 2004 Luby Section 10. [Page 14]