RMT J. Peltotalo Internet-Draft S. Peltotalo Expires: December 10, 2004 Tampere University of Technology V. Roca INRIA Rhone-Alpes June 11, 2004 Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes draft-peltotalo-rmt-bb-fec-supp-xor-pcm-rs-00 Status of this Memo 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 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 December 10, 2004. Copyright Notice Copyright (C) The Internet Society (2004). All Rights Reserved. Abstract This document introduces several Forward Error Correction (FEC) schemes that supplement the FEC schemes described in RFC 3452 [5] and RFC 3695 [7]. More specifically it describes the Fully-Specified FEC scheme corresponding to FEC Encoding ID 2, reserved to simple XOR FEC scheme, and the Under-Specified FEC scheme corresponding to FEC Encoding ID 132, reserved to parity check matrix-based FEC scheme. This document also specifies the FEC Instance IDs 0 and 1, scoped by the FEC Encoding ID 129 and reserved to Reed-Solomon FEC codes. It Peltotalo, et al. Expires December 10, 2004 [Page 1] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 also specifies the FEC Instance ID 0, scoped by the FEC Encoding ID 132 and reserved to LDGM-Staircase codes. Finally this document specifies two algorithms that MAY be used with all block FEC codes. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Simple XOR FEC Scheme . . . . . . . . . . . . . . . . . . 3 1.2 Reed-Solomon FEC Schemes . . . . . . . . . . . . . . . . . 4 1.3 Parity Check Matrix-based FEC Scheme . . . . . . . . . . . 4 2. Conventions Used in This Document . . . . . . . . . . . . . . 6 3. Packet Header Fields . . . . . . . . . . . . . . . . . . . . . 7 3.1 FEC Payload ID for FEC Encoding IDs 2 and 132 . . . . . . 7 3.2 Simple XOR FEC Scheme . . . . . . . . . . . . . . . . . . 7 3.3 Parity Check Matrix-based FEC Scheme . . . . . . . . . . . 8 3.4 Use of EXT_FTI to Deliver FEC Object Transmission Information . . . . . . . . . . . . . . . . . . . . . . . 9 3.4.1 General EXT_FTI Format . . . . . . . . . . . . . . . . 10 3.4.2 FEC Encoding ID 2 Specific Format for EXT_FTI . . . . 11 3.4.3 FEC Encoding ID 132 Specific Format for EXT_FTI . . . 11 4. Use of the Reed-Solomon FEC Codes with Well Known Block Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5. Use of the Reed-Solomon FEC Codes with Unknown Block Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 16 6. Use of the FEC Encoding ID 132/FEC Instance ID 0 for LDGM-Staircase Codes . . . . . . . . . . . . . . . . . . . . . 18 7. Algorithm for Computing the Source Block Structure . . . . . . 19 8. Algorithm for Computing the Number of Encoding Symbols of a Block . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 9. Security Considerations . . . . . . . . . . . . . . . . . . . 23 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . 24 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 25 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 26 12.1 Normative References . . . . . . . . . . . . . . . . . . . . 26 12.2 Informative References . . . . . . . . . . . . . . . . . . . 26 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 27 Intellectual Property and Copyright Statements . . . . . . . . 28 Peltotalo, et al. Expires December 10, 2004 [Page 2] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 1. Introduction This document describes two new Forward Error Correction (FEC) schemes corresponding to FEC Encoding IDs 2 and 132, which supplement the FEC schemes corresponding to FEC Encoding IDs 128 and 129 described in the FEC Building Block [5]. The two new FEC Encoding IDs 2 and 132 are described in Section 3, and this supplements Section 5 of the FEC Building Block [5]. Section 1.1 of this document describes the Fully-Specified FEC scheme corresponding to the FEC Encoding ID 2. FEC scheme corresponding to the FEC Encoding ID 132 is Under-Specified. Sections 4 and 5 of this document specify the use of Reed-Solomon FEC codes, and Section 6 specifies the use of LDGM-Staircase FEC codes. This document also discusses the use of block FEC codes in general, and specifies two mathematical algorithms needed when using block FEC codes. First, source blocking algorithm, is specified in Section 7, and second, "n-algorithm", is specified in Section 8. This document inherits the context, language, declarations and restrictions of the FEC Building Block [5]. This document also uses the terminology of the companion document [6], 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 [2]. This document follows the general guidelines provided in RFC 3269 [3]. 1.1 Simple XOR FEC Scheme There are some very simple codes that are effective for repairing packet loss under very low loss conditions. The Simple XOR FEC scheme is designed to provide protection from a single loss by partitioning a source block into fixed size source symbols and then adding a redundant symbol that is the XOR sum of all the source symbols. This is (k+1, k) code, where k is the number of source symbols. For example if the source block consists of four source symbols (source symbol IDs from 0 to 3) that have values a, b, c and d, then the value of the redundant symbol is e = XOR(a,b,c,d). Then, the packets carrying these symbols look like: (0: a), (1: b), (2: c), (3: d), (4: e). In this example, any single source symbol of the source block can be recovered as the XOR sum of all the other symbols. For example, if Peltotalo, et al. Expires December 10, 2004 [Page 3] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 packets (0: a), (1: b), (3: d), (4: e) are received then the missing source symbol value with source symbol ID = 2 can be recovered by computing c = XOR(a,b,d,e). In this context the source block length determines the percentage of FEC data added to the stream. If the source block length value is low there is naturally more FEC symbols than is when the value is high. (E.g. source blocks of length one source symbol result in 100% redundant parity data, or a 1:1 ratio; and source blocks of length 100 source symbols result in 1% redundant parity data, or a 100:1 ratio.) 1.2 Reed-Solomon FEC Schemes This document reserves two FEC Instance IDs, 0 and 1, for the Under-Specified FEC Encoding ID 129 name-space. Both of these FEC Instance IDs are for Reed-Solomon codes built on Vandermonde matrices [9]. A reference implementation for such codes can be obtained from the author of [9]. These FEC Instance IDs share the same FEC Payload ID and FEC Object Transmission Information extension (EXT_FTI) formats specified respectively in the FEC Building Block [5] and FLUTE [8] documents. Yet they differ in the way the source block structure is computed: FEC Instance ID 0 mandates the use of the algorithm defined in Section 7, while FEC Instance ID 1 leaves to the source the responsibility to define an appropriate source block structure. Sections 4 and 5 define these FEC Instance IDs with more details. The use of the 129/0 FEC scheme (rather than the 129/1 FEC scheme) is RECOMMENDED for ALC [4](and in particular FLUTE [8]) sessions using Reed-Solomon FEC. NORM [10] sessions, using Reed-Solomon FEC, MAY use either 129/0 or 129/1 FEC schemes and this decision is outside the scope of this document. 1.3 Parity Check Matrix-based FEC Scheme RFC 3453 [6] introduces large block FEC codes as an alternative to small block FEC codes like Reed-Solomon. The main advantage of such large block codes is the possibility to operate efficiently on source blocks of several tens of thousands (or more) source symbols of size. The present document introduces the Under-Specified FEC Encoding ID 132 to enable the use of a subset of large block FEC codes. More specifically we consider here the large block FEC codes that rely on Peltotalo, et al. Expires December 10, 2004 [Page 4] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 a dedicated matrix, named a "Parity Check Matrix", at the encoding and decoding ends. The parity check matrix defines relationships (or constraints) between the various encoding symbols (i.e. source symbols and redundant symbols), that are later used by the decoder to reconstruct the original k source symbols if some of them are missing. These codes are systematic, in the sense that the resulting encoding symbols, for delivery, include all the source symbols as well as redundant symbols. The LDPC (Low Density Parity Check) codes and the LDGM (Low Density Generator Matrix) variants [11] fall into this category, but other codes, existing or forthcoming, may also fall in this category. Since the encoder and decoder must operate on the same parity check matrix, some information must be communicated between them, as part of the FEC Object Transmission Information. Its content and the associated EXT_FTI are fully described in Sections 3.3 and 3.4 respectively. This document also reserves the FEC Instance ID value 0 for the LDGM-Staircase codes [11], also called LDPC-Staircase in [13]. A publicly available reference implementation of these codes is available and distributed under a GNU LGPL license [12]. Peltotalo, et al. Expires December 10, 2004 [Page 5] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 2. Conventions Used in This Document 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 RFC 2119 [1]. k: The number of source symbols per block (Source Block Length). n: The number of encoding symbols per block (Encoding Block Length). Peltotalo, et al. Expires December 10, 2004 [Page 6] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 3. Packet Header Fields This section specifies FEC Encoding IDs 2 and 132 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 2 is Fully-Specified, and the FEC scheme associated with FEC Encoding ID 132 is Under-Specified. FEC Encoding IDs 2 and 132 have the same FEC Payload ID format, which is described in Section 3.1. The FEC Object Transmission Information for FEC Encoding IDs 2 and 132 is described in Sections 3.2, 3.3 and 3.4. 3.1 FEC Payload ID for FEC Encoding IDs 2 and 132 FEC Encoding IDs 2 and 132 have the same FEC Payload ID format as that of FEC Encoding ID 128, which is specified in RFC 3452 [5]. The FEC Payload ID for FEC Encoding IDs 2 and 132 is composed of the Source Block Number and the Encoding Symbol ID: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Block Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Encoding Symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1: FEC Payload ID for FEC Encoding IDs 2 and 132 The Source Block Number identifies from which source block of the object the encoding symbol in the payload is generated. These blocks are numbered consecutively from 0 to N-1, where N is the number of source blocks in the object. The Encoding Symbol ID identifies which specific encoding symbol generated from the source block is carried in the packet payload. Each encoding symbol is either an original source symbol or a redundant symbol generated by the encoder. 3.2 Simple XOR FEC Scheme FEC Encoding ID 2 is reserved for the Simple XOR FEC scheme that is described in this section and in Section 1.1. This is a Fully-Specified FEC scheme that is primary intended to be used to protect against small transfer errors. Peltotalo, et al. Expires December 10, 2004 [Page 7] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 The FEC Payload ID format for FEC Encoding ID 2 is described in Section 3.1. The FEC Object Transmission Information has the following specific information: o The FEC Encoding ID 2. o The total length of the object in bytes. o The maximum number of source symbols that can compose any source block (Maximum Source Block Length). This field is provided to allow receivers to compute the source block structure of the object. o The length in bytes of encoding symbols, common to all source blocks. The FEC Encoding ID 2 requires that an algorithm is known to both senders and receivers for determining the size of all source blocks of the transport object. Section 7 describes the blocking algorithm that MUST be used for this purpose. With FEC Encoding ID 2 there MUST be at most one symbol per packet. 3.3 Parity Check Matrix-based FEC Scheme FEC Encoding ID 132 is reserved for the Parity Check Matrix-based FEC scheme that is described in this section. This is an Under-Specified FEC scheme that is primarily intended to be used to protect against normal transfer errors. The FEC Instance ID value of 0, under the scope of FEC Encoding ID 132, is reserved for the LDGM-Staircase codes. The FEC Payload ID format for FEC Encoding ID 132 is described in Section 3.1. The FEC Object Transmission Information has the following specific information: o The FEC Encoding ID 132. o The FEC Instance ID to be used. 0 is reserved for LDGM-Staircase codes. o The total length of the object in bytes. o The maximum number of source symbols that can compose any source block (Maximum Source Block Length). This field is provided to allow receivers to compute the source block structure of the object. o The maximum number of encoding symbols that can be generated for any source block. This field is provided to allow receivers to compute the number of encoding symbols of an encoding block. Peltotalo, et al. Expires December 10, 2004 [Page 8] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 o The length in bytes of encoding symbols, common to all source blocks. o A FEC Instance ID-Specific Information that is used, along with other information (in particular the (k, n) parameters of a block), to create the parity check matrix. For instance, with FEC Instance ID 0 (LDGM-Staircase), this Specific Information, when specified, is the seed of the pseudo random number generator used during the creation of the matrix. Other FEC Instance IDs may have other requirements (e.g. the number of constraints a source symbol is implied in, in case of a regular parity check matrix, MAY be required too). How this field should be interpreted will be defined in each FEC Instance ID scoped by FEC Encoding ID 132. FEC Encoding ID 132 requires that an algorithm is known to both senders and receivers for determining the size of all source blocks of the transport object. Section 7 describes the blocking algorithm that MUST be used for this purpose. Using this algorithm is required even in case of a large block FEC code, since the codec may have practical limits on the maximum block size it can accept, or the environment where this codec runs may impose its own practical limits on the block size (e.g. due to limited available memory constraints). Therefore a large object MAY have to be split into several blocks. Yet it is expected that each source block remains an order of magnitude larger than when using small block codes. This specification also requires that the "n-algorithm" of Section 8 MUST be used by the senders and the receivers to determine the n parameter (Number of Encoding Symbols) associated to each source block of size k (Number of source symbols for this block), as defined by the Blocking algorithm of Section 7. 3.4 Use of EXT_FTI to Deliver FEC Object Transmission Information As specified by Asynchronous Layered Coding (ALC) [4], the EXT_FTI header extension is intended to carry the FEC Object Transmission Information for an object in-band with the object's delivery session. The receiver MUST support the discovery of FEC Object Transmission Information using the EXT_FTI header for FEC Encoding IDs 2 and 132. Out-of-band communication of this information is also possible, but it is outside the scope of this document. It is left up to individual implementations to decide how frequently and in which packets the EXT_FTI header extension is included. In environments with higher packet loss rate, the EXT_FTI might need to be included more frequently in packets than in environments with low error probability. The ALC specification does not define the format or the processing of the EXT_FTI header extension. The following sections specify EXT_FTI Peltotalo, et al. Expires December 10, 2004 [Page 9] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 when used with FEC Encoding IDs 2 and 132. The general format of the EXT_FTI header is same than is specified by FLUTE [8]. For FEC Encoding IDs 2 and 132, the FEC Encoding ID (8 bits) is carried in the Codepoint field of the ALC header when ALC is used, and in the fec_id field of the NORM header when NORM is used. 3.4.1 General EXT_FTI Format The general EXT_FTI format specifies the structure and those attributes of FEC Object Transmission Information that are applicable to any FEC Encoding ID. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | HET = 64 | HEL | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Transfer Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | FEC Instance ID | FEC Enc. ID Specific Format | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2: General EXT_FTI Header Header Extension Type (HET), 8 bits: 64 as defined in RFC 3450 [4]. Header Extension Length (HEL), 8 bits: The length of the whole Header Extension field, expressed in multiples of 32-bit words. This length includes the FEC Encoding ID specific format part. Transfer Length, 48 bits: The length of the transport object in bytes. FEC Instance ID, optional, 16 bits: This field is used for carrying the FEC Instance ID. It is only present if the value of FEC Encoding ID is in the range of 128-255. When the value of FEC Encoding ID is in the range of 0-127, this field is set to 0. Peltotalo, et al. Expires December 10, 2004 [Page 10] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 FEC Encoding ID Specific Format: Different FEC encoding schemes will need different sets of encoding parameters. Thus, the structure and length of this field depends on FEC Encoding ID. The next sections specify structure of this field for FEC Encoding IDs 2 and 132. 3.4.2 FEC Encoding ID 2 Specific Format for EXT_FTI FEC Encoding ID 2 is for Simple XOR FEC. The FEC Encoding ID specific format of EXT_FTI is defined 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ General EXT_FTI format | Encoding Symbol Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Maximum Source Block Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3: Specific EXT_FTI Header for FEC Encoding ID 2 Encoding Symbol Length, 16 bits: Length of Encoding Symbol in bytes. All Encoding Symbols of a transport object MUST be equal to this length, with the optional exception of the last source symbol of the last source block (so that redundant padding is not mandatory in this last symbol). This last source symbol MUST be logically padded out with zeroes when another Encoding Symbol is computed based on this source symbol to ensure the same interpretation of this Encoding Symbol value by the sender and receiver. However, this padding need not be actually sent with the data of the last source symbol. Maximum Source Block Length, 32 bits: The maximum number of source symbols per source block. 3.4.3 FEC Encoding ID 132 Specific Format for EXT_FTI FEC Encoding ID 132 is for Parity Check Matrix-based FEC. The FEC Encoding ID specific format of EXT_FTI is defined as follows. Peltotalo, et al. Expires December 10, 2004 [Page 11] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ General EXT_FTI format | Encoding Symbol Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Maximum Source Block Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Maximum Number of Encoding Symbols | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ . FEC Instance ID-Specific Information (of variable size) . . . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 4: Specific EXT_FTI Header for FEC Encoding ID 132 Encoding Symbol Length, 16 bits: Length of Encoding Symbol in bytes. All Encoding Symbols of a transport object MUST be equal to this length, with the optional exception of the last source symbol of the last source block (so that redundant padding is not mandatory in this last symbol). This last source symbol MUST be logically padded out with zeroes when another Encoding Symbol is computed based on this source symbol to ensure the same interpretation of this Encoding Symbol value by the sender and receiver. However, this padding need not be actually sent with the data of the last source symbol. Maximum Source Block Length, 32 bits: The maximum number of source symbols per source block. Maximum Number of Encoding Symbols, 32 bits: Maximum number of Encoding symbols that can be generated for a source block. FEC Instance ID-Specific Information, variable size (of size >= 0, multiple of four bytes): When present, this FEC Instance ID-Specific Information is used, along with other information, to create the parity check matrix. The exact size (which MUST be multiple of four bytes) and content of this field MUST be specified for each FEC Instance ID scoped by FEC Encoding ID 132. For some FEC Instance IDs, this field MAY also be optional. Upon receiving an EXT_FTI, the HEL field indicates if this field is present, and its size, after subtracting 5 (i.e. the size of the fixed part of EXT_FTI) to its value. Section 6 specifies the Peltotalo, et al. Expires December 10, 2004 [Page 12] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 content of this field in the particular case of FEC Encoding ID 0. Peltotalo, et al. Expires December 10, 2004 [Page 13] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 4. Use of the Reed-Solomon FEC Codes with Well Known Block Structure The FEC Instance ID value of 0, for the Under-Specified FEC Encoding ID 129 name-space, is reserved and used as described in this section for Reed-Solomon FEC codes built on Vandermonde matrices [9], and used with the algorithm defined in Section 7. A reference implementation for such codes can be obtained from the author of [9]. With this FEC Instance ID the block structure is known to both ends once the FEC Object Transmission Information and the algorithm of Section 7 have been used. Since this scheme does not make any assumption on the presence or not of feedback information from the set of receivers, it can be used with both ALC (and in particular FLUTE) and NORM sessions. The FEC Object Transmission Information has the following specific information: o The FEC Encoding ID 129. o The FEC Instance ID 0. o The total length of the object in bytes. o The maximum number of source symbols that can compose any source block (Maximum Source Block Length). This field is provided to allow receivers to compute the source block structure of the object. This field is also used when computing the number of encoding symbols of an encoding block. o The maximum number of encoding symbols that can be generated for any source block. This field is provided to allow receivers to compute the number of encoding symbols of an encoding block. o The length in bytes of encoding symbols, common to all source blocks. The receiver MUST support delivery of FEC Object Transmission Information using the EXT_FTI header for Reed-Solomon 129/0 FEC scheme. It is left up to individual implementations to decide how frequently and in which packets the EXT_FTI header extension is included. Out-of-band communication of this information is also possible, but it is outside the scope of this document. The format of the EXT_FTI header is same as is specified by FLUTE [8] for FEC Encoding ID 129. The FEC Encoding ID (8 bits) is carried in the Codepoint field of the ALC header when ALC is used, and in the fec_id field of the NORM header when NORM is used. With Reed-Solomon 129/0 FEC scheme there MUST be at most one symbol per packet. Peltotalo, et al. Expires December 10, 2004 [Page 14] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 When using Reed-Solomon (n, k) FEC codes, the values for k and n have to be known for each block. These values are required both during the encoding and decoding phases. This specification requires that a sender MUST use both the algorithm for computing the source block structure described in Section 7 and the n-algorithm described in Section 8. The same Maximum Source Block Length (B) input value MUST be used by both algorithms, and the output value from the source blocking algorithm for k, for a given block, MUST be used as the input value for k in the n-algorithm for computing the associated n value. With FEC Encoding ID 129, the FEC Payload ID of each data packet contains a Source Block Length field for the source block corresponding to the encoding symbol the packet carries. This Source Block Length field MUST contain the actual source block length (k) calculated by the source blocking algorithm. The output max_n value of the n-algorithm MUST be used for the Maximum Number of Encoding Symbols field of the EXT_FTI (this max_n value does not depend on the k input parameter of the n-algorithm, and will be the same for all executions of the n-algorithm for the various blocks). The Maximum Source Block Length field MUST contain the input value specified for both algorithms. The receivers determine the k value for a given block either from the FEC Payload ID's Source Block Length field of an encoding symbol belonging to this block, or by computing it using the source blocking algorithm. In the latter case the Maximum Source Block Length is extracted from the EXT_FTI header field. The n value for this block is then determined by the n-algorithm, with the k value determined previously, and the Maximum Source Block Length / Maximum Number of Encoding Symbols values extracted from the EXT_FTI header fields. Peltotalo, et al. Expires December 10, 2004 [Page 15] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 5. Use of the Reed-Solomon FEC Codes with Unknown Block Structure The FEC Instance ID value of 1 for the Under-Specified FEC Encoding ID 129 name-space, is reserved and used as described in this section for Reed-Solomon FEC codes built on Vandermonde matrices [9], and used with unknown block structure. A reference implementation for such codes can be obtained from the author of [9]. With this FEC Instance ID the block structure is communicated to the receiver(s) progressively, thanks to the Source Block Length field of the FEC Payload ID which specifies the size of this block. The block structure cannot be known until one packet for each block has been received. Motivation for this FEC mode is that sender can adapt to loss rates. This is done by reducing the number of source symbols (k) in order to increase the number of parity symbols (n-k), so that the number of encoding symbols (n) is kept the same. It is therefore well suited to NORM sessions. The FEC Object Transmission Information has the following specific information: o The FEC Encoding ID 129. o The FEC Instance ID 1. o The total length of the object in bytes. o The number of encoding symbols that can be generated for a source block. o The length in bytes of encoding symbols, common to all source blocks. The receiver MUST support delivery of FEC Object Transmission Information using the EXT_FTI header for Reed-Solomon 129/1 FEC scheme. It is left up to individual implementations to decide how frequently and in which packets the EXT_FTI header extension is included. Out-of-band communication of this information is also possible, but it is outside the scope of this document. The format of the EXT_FTI header is same as is specified by FLUTE [8] for FEC Encoding ID 129. The FEC Encoding ID (8 bits) is carried in the Codepoint field of the ALC header when ALC is used, and in the fec_id field of the NORM header when NORM is used. With Reed-Solomon 129/1 FEC scheme there MUST be at most one symbol per packet. When using Reed-Solomon (n, k) FEC codes, the values for k and n have Peltotalo, et al. Expires December 10, 2004 [Page 16] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 to be known for each block. These values are required both during the encoding and decoding phases. Here the receivers MUST get the value for k from the FEC Payload ID's Source Block Length field. The Maximum Number of Encoding Symbols field of the EXT_FTI header MUST be used as the n value for all blocks. Peltotalo, et al. Expires December 10, 2004 [Page 17] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 6. Use of the FEC Encoding ID 132/FEC Instance ID 0 for LDGM-Staircase Codes The FEC Instance ID value of 0, for the Under-Specified FEC Encoding ID 132 name-space, is reserved and used as described in this section for LDGM-Staircase codes [11]. A publicly available reference implementation of these codes is available and distributed under a GNU LGPL license [12]. This FEC Instance ID MUST use the FEC Payload ID and FEC Object Transmission Information extension (EXT_FTI) formats specified in Sections 3.1 and 3.4. The FEC Instance ID-Specific Information field of the EXT_FTI, if present, MUST contain a seed that is used by the pseudo random number generator during the creation of the matrix. Since different versions of pseudo-random number generator exist, requiring different seed sizes (e.g. srand assumes an "unsigned int", srand48 a "long int", and seed48 an array of three "unsigned short" elements, for a total of 48 bits), its length is variable. In some cases a fixed value, for instance defined at compilation time (or provided by an out-of-band mechanism) can be used, in which case no FEC Instance ID-Specific Information field is included in the EXT_FTI. Upon receiving an EXT_FTI, the HEL field indicates if this field is present and its size, after subtracting 5 (i.e. the size of the fixed part of EXT_FTI) to its value. With LDGM-Staircase 132/0 FEC scheme there MUST be at most one symbol per packet. The algorithm for computing the block structure, in Section 7, and the n-algorithm for computing the number of encoding symbols of a block, in Section 8, are both REQUIRED. Peltotalo, et al. Expires December 10, 2004 [Page 18] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 7. Algorithm for Computing the Source Block Structure This algorithm is same as is specified by FLUTE [8]. The algorithm does two things: (a) it tells the receiver the length of each particular source block as it is receiving packets for that source block and, (b) it provides the source block structure immediately to the receiver so that the receiver can determine where to save recovered source blocks at the beginning - this is an optimisation, which is essential for some implementations. This algorithm computes a source block structure 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 are sent of the same smaller length. The total number of source blocks (N), the first number of source blocks (I), the second number of source blocks (N-I), the larger length (A_large) and the smaller length (A_small) are calculated thus, Input: B -- Maximum Source Block Length, i.e., the maximum number of source symbols per source block. This is given by the FEC codec specifications and/or the execution environment limitations. L -- Transfer Length in bytes, i.e., the length of the transport object in bytes. E -- Encoding Symbol Length in bytes. Output: N -- The number of source blocks into which the transport object is partitioned. The number and lengths of source symbols in each of the N source blocks. Algorithm: (a) The number of source symbols in the transport object is computed as T = L/E rounded up to the nearest integer (if L mod E == 0 then T = L div E, otherwise T = L div E + 1) (b) The transport object is partitioned into N source blocks, where N = T/B rounded up to the nearest integer (if T mod B == 0 then N = T div B, otherwise N = T div B + 1) (c) A_large = T/N rounded up to the nearest integer (if T mod N == 0 then A_large = T div N, otherwise A_large = T div N + 1) (d) A_small = T/N rounded down to the nearest integer (A_small = T div N) Peltotalo, et al. Expires December 10, 2004 [Page 19] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 (e) I = T mod N (I is an integer between 0 and N-1) (f) Each of the first I source blocks 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) div E))*E bytes in length. Notes: (1) X div Y denotes the integer quotient of the division X/Y (2) X mod Y denotes the integer remainder of the division X/Y (3) X div Y + 1 = (X div Y) + 1 (4) T/N is the average length of the source block (5) If T mod N is zero then A_small = A_large The use of floating point arithmetic in the algorithm might lead to erroneous results caused by rounding problems, depending on the mathematical library used. These problems can be avoided by using only integer math in all algorithm calculations. It is strongly recommended not to use rounding functions, and the comments in brackets illustrate a method for this. Peltotalo, et al. Expires December 10, 2004 [Page 20] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 8. Algorithm for Computing the Number of Encoding Symbols of a Block When using block (n, k) FEC codes, for example Reed-Solomon codes, values for k and n have to be known for each block. These values are required both in encoding and decoding phase. This section describes an algorithm, called the "n-algorithm" in this document, which can be used to compute the value of n based on the variables that are communicated to receivers using, for example, an EXT_FTI header. This algorithm is used to compute the value for n. AT A SENDER: Input: B -- Maximum Source Block Length, i.e., the maximum number of source symbols per source block. This is given by the FEC codec specifications and/or the execution environment limitations. k -- Source Block Length, i.e., the number of source symbols per source block. This is given by source blocking algorithm. R or -- FEC code rate, which is given by the user (e.g. when (a, b) starting a FLUTE sending application). It is expressed either as a floating point value, R, or as a quotient a/b. The latter option is RECOMMENDED for the integer math version of the algorithm. For instance, if we consider a (n, k) systematic FEC code, then a=k, number of source symbols after FEC encoding, and b=n, number of encoding symbols, data plus parity. For example R=1/2 means that 50 percent of the encoded data is parity and 50 percent is original data. Output: max_n -- Maximum Number of Encoding Symbols per encoding block. This depends on FEC code rate. n -- Encoding Block Length, i.e., the number of encoding symbols generated for the source block. Algorithm: (a) max_n = B / R rounded down to the nearest integer (max_n = (B * b) div a) (b) n = k * max_n / B rounded down to the nearest integer (n = (k * max_n) div B) AT A RECEIVER Peltotalo, et al. Expires December 10, 2004 [Page 21] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 Input: B max_n k Output: n Algorithm: (a) n = k * max_n / B rounded down to the nearest integer (n = (k * max_n) div B) Notes: (1) X div Y denotes the integer quotient of the division X/Y The use of floating point arithmetic in the algorithm might lead to erroneous results caused by rounding problems, depending on the mathematical library used. These problems can be avoided by using only integer math in all algorithm calculations. It is strongly recommended not to use rounding functions, and how to do that is presented in brackets. Peltotalo, et al. Expires December 10, 2004 [Page 22] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 9. Security Considerations The security considerations for this document are the same as they are for RFC 3452 [5]. Peltotalo, et al. Expires December 10, 2004 [Page 23] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 10. IANA Considerations Values of FEC Encoding IDs are subject to IANA registration. For general guidelines on IANA considerations as they apply to this document, see RFC 3452 [5]. This document assigns the Fully-Specified FEC Encoding ID 2 under the ietf:rmt:fec:encoding name-space to "Simple XOR FEC". The FEC Payload ID format and corresponding FEC Object Transmission Information associated with FEC Encoding ID 2 is described in Sections 3.1 and 3.2, and the corresponding FEC scheme is described in Section 1.1. This document assigns the Under-Specified FEC Encoding ID 132 under the ietf:rmt:fec:encoding name-space to "Parity Check Matrix-based FEC". The FEC Payload ID format and corresponding FEC Object Transmission Information associated with FEC Encoding ID 132 are described in Sections 3.1 and 3.3. As FEC Encoding ID 132 is Under-Specified, a new "FEC Instance ID" sub-name-space must be established, in accordance to RFC 3452. Hence this document also establishes a new "FEC Instance ID" registry named ietf:rmt:fec:encoding:instance:132 and scoped by ietf:rmt:fec:encoding = 132 (Parity Check Matrix-based FEC) As per RFC 3452 [5], the values that can be assigned within ietf:rmt:fec:encoding:instance:132 are non-negative numeric indices. Assignment requests are granted on a "First Come First Served" basis. RFC 3452 [5] specifies additional criteria that MUST be met for the assignment within the generic ietf:rmt:fec:encoding:instance name- space. These criteria also apply to ietf:rmt:fec:encoding:instance:132. This document assigns the FEC Instance ID value 0 for the LDGM-Staircase codes [11] from scope ietf:rmt:fec:encoding = 132. This document assigns the FEC Instance ID value 0 for the Reed-Solomon 129/0 FEC scheme from scope ietf:rmt:fec:encoding = 129. This document assigns the FEC Instance ID value 1 for the Reed-Solomon 129/1 FEC scheme from scope ietf:rmt:fec:encoding = 129. Peltotalo, et al. Expires December 10, 2004 [Page 24] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 11. Acknowledgements The authors would like to thank all the people who gave feedback on this document. Peltotalo, et al. Expires December 10, 2004 [Page 25] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 12. References 12.1 Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, BCP 14, March 1997. [2] 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. [3] Kermode, R. and L. Vicisano, "Author Guidelines for Reliable Multicast Transport (RMT) Building Blocks and Protocol Instantiation documents", RFC 3269, April 2002. [4] Luby, M., Gemmell, J., Vicisano, L., Rizzo, L. and J. Crowcroft, "Asynchronous Layered Coding (ALC) Protocol Instantiation", RFC 3450, December 2002. [5] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M. and J. Crowcroft, "Forward Error Correction (FEC) Building Block", RFC 3452, December 2002. [6] 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. [7] Luby, M. and L. Vicisano, "Compact Forward Error Correction (FEC) Schemes", RFC 3695, February 2004. [8] Paila, T., Luby, M., Lehtonen, R., Roca, V. and R. Walsh, "FLUTE - File Delivery over Unidirectional Transport", draft-ietf-rmt-flute-08 (work in progress), June 2004. 12.2 Informative References [9] Rizzo, L., "Effective Erasure Codes for Reliable Computer Communication Protocols", ACM SIGCOMM Computer Communication Review Vol.27, No.2, pp.24-36, April 1997. [10] Adamson, B., Bormann, C., Handley, M. and J. Macker, "NACK-Oriented Reliable Multicast Protocol (NORM)", draft-ietf-rmt-pi-norm-09 (work in progress), January 2004. [11] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of Four Large Block FEC Codecs, LDPC, LDGM, LDGM Staircase and LDGM Triangle, Plus a Reed-Solomon Small Block FEC Codec", INRIA Research Report RR-5225, June 2004. Peltotalo, et al. Expires December 10, 2004 [Page 26] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 [12] Roca, V., Neumann, C., Laboure, J. and Z. Khallouf, "LDGM-staircase codec reference implementation", MCLv3 project PLANETE Research Team, INRIA Rhone-Alpes, April 2004. [13] MacKay, D., "Information Theory, Inference and Learning Algorithms", Cambridge University Press, ISBN: 0521642981, 2003. Authors' Addresses Jani Peltotalo Tampere University of Technology P.O. Box 553 (Korkeakoulunkatu 1) Tampere FIN-33101 Finland EMail: jani.peltotalo@tut.fi Sami Peltotalo Tampere University of Technology P.O. Box 553 (Korkeakoulunkatu 1) Tampere FIN-33101 Finland EMail: sami.peltotalo@tut.fi Vincent Roca INRIA Rhone-Alpes 655, av. de l'Europe Montbonnot St Ismier cedex 38334 France EMail: vincent.roca@inrialpes.fr Peltotalo, et al. Expires December 10, 2004 [Page 27] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards-related documentation can be found in BCP-11. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can be obtained from the IETF Secretariat. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights which may cover technology that may be required to practice this standard. Please address the information to the IETF Executive Director. Full Copyright Statement Copyright (C) The Internet Society (2004). 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 Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assignees. 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 Peltotalo, et al. Expires December 10, 2004 [Page 28] Internet-Draft Simple XOR, Reed-Solomon, and Parity Check Matrix-based FEC Schemes June 2004 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Peltotalo, et al. Expires December 10, 2004 [Page 29]