Internet Engineering Task Force RMT WG INTERNET-DRAFT M.Luby/Digital Fountain draft-ietf-rmt-bb-fec-02.txt L.Vicisano/Cisco J.Gemmell/Microsoft L.Rizzo/ACIRI and Univ. Pisa M.Handley/ACIRI J. Crowcroft/UCL 17 November 2000 Expires: May 2001 RMT BB Forward Error Correction Codes This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. 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@isi.edu. Abstract This memo describes the abstract packet formats and IANA registration procedures for use of Forward Error Correction (FEC) codes within the context of reliable IP multicast transport. This memo should be read in conjunction with and uses the terminology of the companion memo [1], which describes the use of Forward Error Correction (FEC) codes within the context of reliable IP multicast transport and Luby/Gemmell/Vicisano/Rizzo/Handley/Crowcroft [Page 1]
^L INTERNET-DRAFT Expires: May 2001 November 2000 provides an introduction to some commonly used FEC codes. 1. FEC Abstract Packet Fields and Out-of-Band Information This section specifies the information that protocol packets must carry to implement the various forms of FEC-based reliability. A session is defined to be all the information associated with a transmission of data about a particular object by a single sender. There are three classes of packets that may contain FEC information within a session: data packets, session-control packets and feedback packets. They generally contain different kinds of FEC information. Note that some protocols do not use feedback packets. Data packets MAY sometime serve as session-control packets as well; both data and session-control packets generally travel downstream (from the sender towards receivers) and are addressed to a multicast IP address (sometime the might be addressed to the unicast address of a specific receiver). In the following, for simplicity we will refer to both data and session control packets as downstream-traveling packets, or simply downstream packets. As a general rule, feedback packets travel upstream (from receivers to the sender) and are addressed to the unicast address of the sender. Sometimes, however, they might be addressed to a multicast IP address or to the unicast address of a receiver or also the the unicast address of some different node (intermediate node that provides recovery services or neighboring router). The FEC-related information that can be present in downstream packets can be classified as follows: 1) FEC Encoding Identifier Identifies the FEC encoding being used and has the purpose of allowing receivers to select the appropriate FEC decoder. As a general rule, the "FEC Encoding Identifier" MUST be the same for a given session, i.e., for all transmission of data related to a particular object, but MAY vary across different transmissions of data about different objects in different sessions, even if transmitted using the same set of multicast groups. 2) FEC payload ID Identifies the symbol(s) in the payload of the packet. The content of this piece of information depends on the encoder being used (e.g. in Block FEC codes this may be the combination of block Luby/Gemmell/Vicisano/Rizzo/Handley/Crowcroft Section 1. [Page 2]
^L INTERNET-DRAFT Expires: May 2001 November 2000 index and symbol index; in expandable FEC codes this may be just a flat symbol identifier). 3) FEC Object Transmission Information This is information regarding the encoding of a specific object needed by the FEC decoder (e.g. for Block FEC codes this may be the combination of block length and object length). This might also include general parameters of the FEC encoder. All the classes of information above, except 2), can either be transmitted within the transport session (using protocol packet-header fields) or out of band. The information described in 2) MUST be transmitted in data-packet header fields, as it provides a description of the data contained in the packet. In the following we specify the content of 1), 2) and 3) independent of whether these pieces of information are transmitted in protocol packets or out of band. This document does not specify out of band methods to transport the information. Within the context of FEC repair schemes, feedback packets are (optionally) used to request FEC retransmission. The FEC-related information present in feedback packets can be classified as follows: 1) FEC Block Identifier This is the identifier of the FEC block for which retransmission is requested. This information does not apply to some type of decoders. 2) Number of Repair Symbols This is the number of repair symbols requested, needed to recover the object. This is used when there are still an ample supply of previously unsent symbols that can be sent, and this specifies the number of such additional symbols that should be sent. This type of request is most applicable to both small and large block FEC codes and to expandable FEC codes. 2) Range of Repair Symbols This is a range of the symbol indices that are being requested as repair symbols. This is used when there is a specified set of repair symbols that will be most useful to reconstruct input symbols, and in general the requested symbols will be symbols not yet received by the requestor. This type of request is most applicable to both small and large block FEC codes, and less Luby/Gemmell/Vicisano/Rizzo/Handley/Crowcroft Section 1. [Page 3]
^L INTERNET-DRAFT Expires: May 2001 November 2000 applicable to expandable FEC codes. 2) List of Repair Symbols This is a list of the symbol indices that are being requested as repair symbols. This is used when there is a specified set of repair symbols that will be most useful to reconstruct input symbols, and in general the requested symbols will be symbols not yet received by the requestor. This type of request is most applicable to both small and large block FEC codes, and less applicable to expandable FEC codes. 1.1. FEC Encoding Identifier This is a numeric index that identifies a specific FEC encoding scheme OR a class of encoding schemes that share the same format of "FEC Payload ID" and "FEC Object Transmission Information". The FEC Encoding Identifier identifies a specific FEC encoding scheme when the encoding scheme is formally and fully specified, in a way that independent implementors can implement both encoder and decoder from the specification. Companion documents of this specification may specify such FEC encoding schemes and associate them with "FEC Encoding Identifier" values. These documents MUST also specify a correspondent format for the "FEC Payload ID" and "FEC Object Transmission Information". Currently FEC Encoding Identifiers in the range 0-127 are reserved for this class of encoding schemes. It is possible that a FEC encoding scheme cannot be completely specified or that such a specification is simply not available or also that a party exists that owns the encoding scheme and it is not willing to disclose its algorithm. We refer to these encoding schemes as "Under- Specified" schemes. Under-specified schemes can still be identified as follows: o A format of the fields "FEC Payload ID" and "FEC Object Transmission Information" MUST be defined for the encoding scheme. o A value of "FEC Encoding Identifier" MUST be reserved and associated to the format definitions above. An already reserved "FEC Encoding Identifier" MUST be reused if it is associated to the same format of "FEC Payload ID" and "FEC Object Transmission Information" as the ones needed for the new under-specified FEC encoding scheme. o A value of "FEC Encoding Name" must be reserved (see below). Luby/Gemmell/Vicisano/Rizzo/Handley/Crowcroft Section 1.1. [Page 4]
^L INTERNET-DRAFT Expires: May 2001 November 2000 An Under-specified FEC scheme is completely identified by the tuple (FEC Encoding Identifier, FEC Encoding Name). The party that owns this tuple MUST be able to provide an FEC encoder and decoder that implement the under-specified FEC encoding scheme identified by the tuple. "FEC Encoding Names" are numeric identifiers scoped by a FEC Encoding Identifier. The FEC Encoding Name MUST be part of the "FEC Object Transmission Information" and must be communicated to receivers together with the FEC Encoding Identifier. An FEC Encoding Identifier MAY also define a format for the (abstract) feedback packet fields "FEC Block Identifier", "Number of Repair Symbols", "Range of Repair Symbols" and "List of Repair Symbols". 1.2. FEC Payload ID and FEC Object Transmission Information A document that specifies an encoding scheme and reserves a value of FEC Encoding Identifier MUST define a packet-field format for FEC Payload ID and FEC Object Transmission Information according to the need of the encoding scheme. This also applies to documents that reserves values of FEC Encoding Identifiers for under-specified encoding schemes. In this case the FEC Object Transmission Information must also include a field to contain the "FEC Encoding Name". A packet field definition of FEC Object Transmission Information MUST be provided despite the fact that protocol instantiation may decide to communicate this information out of band. The packet field format of "FEC Block Identifier" and "Number of Repair Symbols" SHOULD be specified for each FEC encoding scheme, even the scheme is mainly intended for feedback-less protocols. FEC Block Identifier may not apply to some encoding schemes. All packet field definition (FEC Payload ID, FEC Object Transmission Information, FEC Block Identifier and Number of Repair Symbols) MUST be fully specified at level of bit-fields and they must have a length that is a multiple of a 4-byte word (this is to facilitate the alignment of packet fields in protocol instantiations). 2. Predefined FEC encoders This section specifies the FEC Encoding Identifier and the relative packets field for a number of known schemes that follow under the class Luby/Gemmell/Vicisano/Rizzo/Handley/Crowcroft Section 2. [Page 5]
^L INTERNET-DRAFT Expires: May 2001 November 2000 of under-specified FEC encoding schemes. Others may be specified in companion documents. 2.1. Small Block, Large Block and Expandable FEC Codes This section reserves a FEC Encoding Identifier for the family of codes described in Section 2.2, 2.3 and 2.4 and specifies the relative packet fields. Under-specified FEC encoding schemes that belong to this class MUST use this identifier and packet field definitions. The FEC Encoding Identifier assigned to Small Block, Large Block, and Expandable FEC Codes is 128. The FEC Payload ID is composed of an encoding symbol index and an encoding block number 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 block number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | encoding symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ In addition, a one bit FEC Encoding Flag SHOULD be included, and this flag indicates whether the encoding symbol(s) in the payload of the packet are source symbol(s) or redundant symbol(s). The FEC Object Transmission Information has the following structure: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | FEC Encoding Name | Object Length (MSB) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Object Length (LSB) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Block Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Note that this structure limits the range of possible FEC Encoding Names to 0-:-65536, despite the FEC Object Transmission Information can also be transmitted out of band. Luby/Gemmell/Vicisano/Rizzo/Handley/Crowcroft Section 2.1. [Page 6]
^L INTERNET-DRAFT Expires: May 2001 November 2000 The Object Length, composed of a Most Significant Bytes portion (MSB) and a Least Significant Bytes portion (LSB), is expressed in bytes. There are three different types of feedback packets: number type, range type, and list type. The type of feedback packets used by the application MUST be specified either out of band or within each feedback packet. Feedback packets MUST contain both an FEC Block Identifier and one of the following, depending on the type: o number type: The number of repair symbols requested. o range type: The range of symbol indices of the repair symbols requested. o list type: The list of symbol indices of the repair symbols requested. The structure of feedback packets is the following: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | FEC Block Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Number type: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Number of Repair Symbols | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Luby/Gemmell/Vicisano/Rizzo/Handley/Crowcroft Section 2.1. [Page 7]
^L INTERNET-DRAFT Expires: May 2001 November 2000 Range type: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Start Symbol Index of Repair Symbols | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | End Symbol Index of Repair Symbols | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ List type: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | N = Number of Symbols in the List | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Repair Symbol Index 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Repair Symbol Index 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Repair Symbol Index N-1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 3. IANA Considerations Values of FEC Encoding Identifiers and FEC Encoding Names are subject to IANA registration. FEC Encoding Identifiers and FEC Encoding Names are hierarchical: FEC Encoding Identifiers (at the top level) scope ranges of FEC Encoding Names. Not all FEC Encoding Identifiers have a corresponding FEC Encoding Name scope (see below). A FEC Encoding Identifier is a numeric non-negative index. Value from 0 to 127 are reserved for FEC encoders that are fully specified, as described in section 3.1. The assignment of a FEC Encoding Identifier in this range can only be granted if the requestor can provide such a specification published as an IETF RFC. Value grater than 127 can be assigned to under-specified encoding schemes. In any case values of FEC Encoding Identifiers can only be assigned if the required FEC packet fields corresponding to it (see section 3.1) are Luby/Gemmell/Vicisano/Rizzo/Handley/Crowcroft Section 3. [Page 8]
^L INTERNET-DRAFT Expires: May 2001 November 2000 specified in a RFC. Each FEC Encoding Identifier assigned to an under-specified encoding scheme scopes a range of FEC Encoding Names. An FEC Encoding Name is a numeric non-negative index. The document that reserves a FEC Encoding Identifier MAY also specify a range for the subordinate FEC Encoding Names. Under the scope of a FEC Encoding Identifier, FEC Encoding Names are assigned on a First Come First Served base to requestors that are able to provide point of contact information and a pointer to publicly accessible documentation describing the FEC encoder and a ways to obtain it. The requestor is responsible for keeping this information up to date. 4. References [1] Luby, M., Vicisano, L., Rizzo, L., Handley, M., Gemmell, J., Crowcroft, J., "The use of Forward Error Correction in Reliable Multicast", draft-ietf-rmt-info-fec-00 submited to the IETF RMT working group, November 2000. 5. Authors' Addresses Michael Luby luby@digitalfountain.com Digital Fountain 600 Alabama Street San Francisco, CA, USA, 94110 Lorenzo Vicisano lorenzo@cisco.com cisco Systems, Inc. 170 West Tasman Dr., San Jose, CA, USA, 95134 Jim Gemmell jgemmell@microsoft.com Microsoft Research 301 Howard St., #830 San Francisco, CA, USA, 94105 Luigi Rizzo luigi@iet.unipi.it ACIRI, 1947 Center St., Berkeley CA 94704 Luby/Gemmell/Vicisano/Rizzo/Handley/Crowcroft Section 5. [Page 9]
^L INTERNET-DRAFT Expires: May 2001 November 2000 and Dip. di Ing. dell'Informazione Universita` di Pisa via Diotisalvi 2, 56126 Pisa, Italy Mark Handley mjh@aciri.org ACIRI 1947 Center St. Berkeley CA, USA, 94704 Jon Crowcroft J.Crowcroft@cs.ucl.ac.uk Department of Computer Science University College London Gower Street, London WC1E 6BT, UK Luby/Gemmell/Vicisano/Rizzo/Handley/Crowcroft Section 5. [Page 10]
^L INTERNET-DRAFT Expires: May 2001 November 2000 6. Full Copyright Statement Copyright (C) The Internet Society (2000). 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/Gemmell/Vicisano/Rizzo/Handley/Crowcroft Section 6. [Page 11]
^L INTERNET-DRAFT Expires: May 2001 November 2000 Luby/Gemmell/Vicisano/Rizzo/Handley/Crowcroft Section 6. [Page 12]
