Reliable Multicast Transport J. Lacan Internet-Draft ENSICA/LAAS-CNRS Expires: April 20, 2006 V. Roca INRIA J. Peltotalo S. Peltotalo Tampere University of Technology October 17, 2005 draft-lacan-rmt-fec-bb-rs-00 Reed Solomon Error Correction Scheme 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 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 April 20, 2006. Copyright Notice Copyright (C) The Internet Society (2005). Abstract This document describes a Fully-Specified FEC scheme for the Reed- Solomon forward error correction code and its application to reliable delivery of data objects on the packet erasure channel. Lacan, et al. Expires April 20, 2006 [Page 1] Internet-Draft draft-lacan-rmt-fec-bb-rs-00 October 2005 The Reed-Solomon codes belong to the class of Maximum Distance Separable (MDS) codes, i.e, they enable a receiver to recover the k source symbols from any set of k received symbols. The implementation described here is compatible with the IPR-free implementation described in [5]. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Definitions Notations and Abbreviations . . . . . . . . . . . 3 3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . 3 3.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . 4 3.3 Abbreviations . . . . . . . . . . . . . . . . . . . . . . 4 4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 4 4.1 FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 4 4.2 FEC Object Transmission Information . . . . . . . . . . . 5 4.2.1 Mandatory Elements . . . . . . . . . . . . . . . . . . 5 4.2.2 Common Elements . . . . . . . . . . . . . . . . . . . 5 4.2.3 Scheme-Specific Elements . . . . . . . . . . . . . . . 6 4.2.4 Encoding Format . . . . . . . . . . . . . . . . . . . 6 5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5.1 Determining the Maximum Source Block Length (B) . . . . . 7 5.2 Determining the Number of Encoding Symbols of a Block . . 7 6. Reed-Solomon Codes . . . . . . . . . . . . . . . . . . . . . . 8 6.1 Finite field . . . . . . . . . . . . . . . . . . . . . . . 8 6.2 Reed-Solomon Encoding Algorithm . . . . . . . . . . . . . 9 6.3 Reed-Solomon Decoding Algorithm for the Erasure Channel . 10 6.4 Implementation . . . . . . . . . . . . . . . . . . . . . . 11 6.4.1 Implementation for the Packet Erasure Channel . . . . 11 7. Security Considerations . . . . . . . . . . . . . . . . . . . 12 8. Intellectual Property . . . . . . . . . . . . . . . . . . . . 12 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 12 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 13 10.1 Normative References . . . . . . . . . . . . . . . . . . . 13 10.2 Informative References . . . . . . . . . . . . . . . . . . 13 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 14 Intellectual Property and Copyright Statements . . . . . . . . 15 Lacan, et al. Expires April 20, 2006 [Page 2] Internet-Draft draft-lacan-rmt-fec-bb-rs-00 October 2005 1. Introduction Forward Error Correction (FEC) is one of the most classical solutions to improve the reliability of multicast or real-time transmissions. The documents [2] and [3] describe a general framework to use FEC in the context of data transport. The companion document [4] describes some applications of FEC codes for content delivery. Recent FEC schemes [6] or [7] proposed propose erasure codes based on sparse graphs or matrices. These codes are are efficient in terms of CPU but not optimal in terms of correction capability, at least for short lengths. The FEC scheme presented in this document belongs to the class of Maximum-Distance Separable codes, i.e. it is optimal in terms of erasure correction capability. In others words, it enables the receiver to recover the k source symbols from any set of k encoding symbols. Even the coding/decoding complexity is larger than the one of [6] or [7], this family of codes could be very useful for applications requiring short length codes (e.g. video and audio streaming). Actually, many multicast applications already use packet-based Reed- Solomon codes. Most of these implementations are derived from the free implementation of Luigi Rizzo [5]. The implementation proposed in this document is compatible with this one. 2. Terminology 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]. 3. Definitions Notations and Abbreviations 3.1 Definitions This document uses the same terms and definitions as those specified in [3]. Additionally, it uses the following definitions: o Source symbol: unit of data used during the encoding process. The source symbols are a m-bit vectors considered as an element of a finite field. o Encoding symbol: unit of data generated by the encoding process. The encoding symbols are a m-bit vectors. o Encoding block: set of encoding symbols generated by an encoding process. Lacan, et al. Expires April 20, 2006 [Page 3] Internet-Draft draft-lacan-rmt-fec-bb-rs-00 October 2005 o Repair symbol: encoding symbols which are not source symbols. o Systematic code: a code in which the source symbols are included as part of the encoding symbols o Source block: a block of k source symbols which are considered together for the encoding. o Encoding Symbol Group: a group of encoding symbols that are sent together, within the same packet, and whose relationships to the source object can be derived from a single Encoding Symbol ID. o Source Packet: a data packet containing source symbols. Note that the source symbols included in a same packet does not belong to the same encoding block. o Repair Packet: a data packet containing repair symbols. Note that the repair symbols included in a same packet does not belong to the same encoding block. o Finite field size parameter, r: this parameter defines the number of elements in the finite field, q=2^^r. 3.2 Notations This document uses the following notations: o L denotes the object transfer length in bytes o k denotes the number of source symbols o n denotes the number of repair symbols o N denotes the number of source blocks into which the object shall be partitioned o rate denotes the so-called "code rate", i.e. the k/n ratio o a ^^ b a raised to the power b o I_k denotes the k*k identity matrix o sz denotes the size of the packets 3.3 Abbreviations This document uses the following abbreviations: o ESI Encoding Symbol ID o RS Reed-Solomon o MDS Maximum Distance separable Code o F_q finite field with q elements 4. Formats and Codes 4.1 FEC Payload IDs The FEC Payload ID is composed of the Source Block Number and the Encoding Symbol ID: The Source Block Number (20 bit field) identifies from which source block of the object the encoding symbol(s) in the payload is(are) generated. There is a maximum of 2^^20 blocks per object. Lacan, et al. Expires April 20, 2006 [Page 4] Internet-Draft draft-lacan-rmt-fec-bb-rs-00 October 2005 The Encoding Symbol ID (12 bit field) identifies which specific encoding symbol generated from the source block is carried in the packet payload. There is a maximum of 2^^12 encoding symbols per block. The first k values (0 to k-1) identify source symbols, the remaining n-k values identify repair symbols. There MUST be exactly one FEC Payload ID per packet. In case of en Encoding Symbol Group, when multiple encoding symbols are sent in the same packet, the FEC Payload ID refers to the first symbol of the packet. The other symbols can be deduced from the ESI of the first symbol by incrementing sequentially the ESI. 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 (20 bits) | Encoding Symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1: FEC Payload ID encoding format for FEC Encoding ID XX 4.2 FEC Object Transmission Information 4.2.1 Mandatory Elements o FEC Encoding ID: the Fully-Specified FEC Schemes described in this document use the FEC Encoding ID XX. 4.2.2 Common Elements The following elements MUST be used with the present FEC Scheme: o Transfer-Length (L): a non-negative integer indicating the length of the object in bytes. There are some restrictions on the maximum Transfer-Length that can be supported: maximum transfer length = 2^^20 * B * E For instance, if B=2^^8 (because the codec operates on a 2^^8 finite field), and if E=1024 bytes, then the maximum transfer length is 2^^38 bytes (i.e. a bit more than 274 Giga Bytes). It is expected that other FEC codes (e.g. LDPC codes) or another RS FEC Scheme be used for larger objects. o Encoding-Symbol-Length (E): a non-negative integer indicating the length of each encoding symbol in bytes. o Maximum-Source-Block-Length (B): a non-negative integer indicating the maximum number of source symbols in a source block. o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer indicating the maximum number of encoding symbols generated for any source block. Lacan, et al. Expires April 20, 2006 [Page 5] Internet-Draft draft-lacan-rmt-fec-bb-rs-00 October 2005 Section 5 explains how to derive the values of each of these elements. 4.2.3 Scheme-Specific Elements o Finite Field size parameter, r (optional): The r parameter defines the finite field size composed of q=p^^r elements. The r=8 value is the default. When no finite field size parameter is communicated to the decoder, then this latter MUST assume that r=8. 4.2.4 Encoding Format This section shows two possible encoding formats of the above FEC OTI. The present document does not specify when or how these encoding formats should be used. 4.2.4.1 Using the General EXT_FTI Format The FEC OTI binary format is the following, when the EXT_FTI mechanism is used. 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 (L) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 0 (not applicable) | Encoding Symbol Length (E) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Max Source Block Length (B) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Max Nb of Enc. Symbols (max_n) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ . Optional finite field size parameter (r) . +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The HEL (Header Extension Length) indicates whether the optional finite field size parameter, r, is present or not. 4.2.4.2 Using the FDT Instance (FLUTE specific) When it is desired that the FEC OTI be carried in the FDT Instance of a FLUTE session, the following XML elements must be described for the associated object: Lacan, et al. Expires April 20, 2006 [Page 6] Internet-Draft draft-lacan-rmt-fec-bb-rs-00 October 2005 o FEC-OTI-Transfer-length o FEC-OTI-Encoding-Symbol-Length o FEC-OTI-Maximum-Source-Block-Length o FEC-OTI-Max-Number-of-Encoding-Symbols o FEC-OTI-Finite-Field-Size-Parameter (optional) When no finite field size parameter is to be carried in the FEC OTI, the sender simply omits the FEC-OTI-Finite-Field-Size-Parameter element. 5. Procedures This section defines procedures for FEC Encoding ID XX. 5.1 Determining the Maximum Source Block Length (B) The B parameter (maximum source block length in symbols) depends on several parameters: the finite field size parameter, r, the code rate (rate), as well as possible internal codec limitations. The finite field size parameter, r, defines the number of elements in this field, q=2^^r, which is also the maximum number of encoding symbols for a source block (max_n). When r=8 (default): max1_B = 2 ^^ 8 Additionally, a codec MAY impose other limitations on the maximum block size. Yet it is not expected that such limits exist when using r=8 (default). This decision SHOULD be clarified at implementation time, when the target use case is known. This results in a max2_B limitation. Then, B is given by: B = min(max1_B, max2_B) Note that this calculation is only required at the coder, since the B parameter is communicated to the decoder through the FEC OTI. 5.2 Determining the Number of Encoding Symbols of a Block The following algorithm, also called "n-algorithm", explains how to determine the actual number of encoding symbols for a given block. AT A SENDER: Input: B Maximum source block length, for any source block. Section 5.1 explains how to determine its value. k Current source block length. This parameter is given by the source blocking algorithm. Lacan, et al. Expires April 20, 2006 [Page 7] Internet-Draft draft-lacan-rmt-fec-bb-rs-00 October 2005 rate FEC code rate, which is given by the user (e.g. when starting a FLUTE sending application) for a given use case. It is expressed as a floating point value. Output: max_n Maximum number of encoding symbols generated for any source block n Number of encoding symbols generated for this source block Algorithm: a. max_n = floor(B / R) b. n = floor(k * max_n / B) AT A RECEIVER: Input: B Extracted from the received FEC OTI max_n Extracted from the received FEC OTI k Given by the source blocking algorithm Output: n Algorithm: a. n = floor(k * max_n / B) 6. Reed-Solomon Codes Reed-Solomon (RS) codes form a special class of linear block codes, which offer maximum erasure correction capability. A [n,k]-RS code encodes a sequence of k source symbols defined over a finite field F_q into a sequence of n repair symbols, where n is upperbounded by q-1. The implementation described here is based on a Vandermonde matrix. The n symbols resulting from the encoding processing do not include the source symbols. Depending on the application, the encoding symbols can only be composed of the n repair symbols (non systematic case) or can also included the source symbols (systematic case). 6.1 Finite field A finite field F_q is defined as a finite set of q elements which have a structure of field. It contains necessarily q=p^r elements, where p is a prime number. In the practical context of data networks, p is always set to 2. The elements of the field F_(2^r) can be represented by polynomials with binary coefficients (i.e. over F_2) of degree less than r. The polynomials can be associated to binary vectors of length r. For example, the vector (11001) Lacan, et al. Expires April 20, 2006 [Page 8] Internet-Draft draft-lacan-rmt-fec-bb-rs-00 October 2005 represents the polynomial 1+x+x^^4. This representation is often called polynomial representation. The addition between two elements is defined as the addition of binary polynomials in F_2 and the multiplication is the multiplication modulo a given irreducible (i.e. non-factorizable) polynomial of degree r with coefficients in F_2. Since a finite field F_q is completely characterized by the irreducible polynomial, we propose the following polynomials to represent the field F_(2^^r), for r varying from 2 to 16 : r=2, "111" (1+x+x^^2) r=3, "1101", (1+x+x^^3) r=4, "11001", (1+x+x^^4) r=5, "101001", (1+x^^2+x^^5) r=6, "1100001", (1+x+x^^6) r=7, "10010001", (1+x^^3+x^^7) r=8, "101110001", (1+x^^2+x^^3+x^^4+x^^8) r=9, "1000100001", (1+x^^4+x^^9) r=10, "10010000001", (1+x^^3+x^^10) r=11, "101000000001", (1+x^^2+x^^11) r=12, "1100101000001", (1+x+x^^4+x^^6+x^^12) r=13, "11011000000001", (1+x+x^^3+x^^4+x^^13) r=14, "110000100010001", (1+x+x^^6+x^^10+x^^14) r=15, "1100000000000001", (1+x+x^^15) r=16, "11010000000010001", (1+x+x^^3+x^^12+x^^16) For implementation issues, these polynomials are also primitive and contain the minimum number of monomials. 6.2 Reed-Solomon Encoding Algorithm The encoding algorithm produces a block of repair symbols c=(c_0, ..., c_(n-1) ) over F_q from an source block of k symbols i=(i_0, ..., i_(k-1) ) over F_q. The linear codes can be encoded by multiplying the source block by a generator matrix G of k rows and n columns over F_q. Thus c = i * G. The definition of the generator matrix completely characterizes the code. Let us consider that n = q-1 and 0< k <= n. Let us denote alpha a primitive element of F_q, i.e. any element of F_q can be expressed as a power of alpha. The entry g_{i,j} of the generator matrix G of an RS code is equal to alpha^^(u*v), where 0<= u <= k-1 and 0<= u <= n-1. This matrix is a called a Vandermonde matrix. Note that, for practical applications, the length of the code can be shortened to n'| | | | | | | j |--------------| / |---------------------| | | | | | / | | | | | | | | | | encoding | | | | | | | | | | block | | | | | | | | | | j | | | | | | | | | | | | | | | | | | | | | | | | | ------------ ------------------- k source packets n encoding packets Figure 3: Packet encoding scheme It should be noted that the number of generated packets (and transmitted on the network) can be variable and adapted on demand. The only constraint is the maximum number depending on the finite field size (see Section Section 6.1) The main interest of this scheme is that the losses of some of the encoding packets produce the same erasure pattern for each of the sz RS encoding blocks. It follows that the matrix inversion must be done only once for the sz encoding blocks. For large sz, this complexity cost of the inversion becomes negligible compared to the sz matrix-vector multiplications. 7. Security Considerations The security considerations for this document are the same as they are for RFC 3452 [2]. 8. Intellectual Property To the best of our knowledge, there is no patent or patent application identified as being used in the Reed-Solomon FEC scheme. Yet other flavors of Reed-Solomon codes and associated techniques MAY be covered by Intellectual Property Rights. 9. Acknowledgments 10. References Lacan, et al. Expires April 20, 2006 [Page 12] Internet-Draft draft-lacan-rmt-fec-bb-rs-00 October 2005 10.1 Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119. [2] Luby, M., "Forward Error Correction (FEC) Building Block", RFC 3452, December 2002. [3] Watson, M., "Forward Error Correction (FEC) Building Block (revised)", (draft-ietf-rmt-fec-bb-revised-00 : Work in progress), April 2005. [4] Luby, M., "The Use of Forward Error Correction (FEC) in Reliable Multicast", RFC 3453, December 2002. 10.2 Informative References [5] Rizzo, L., "Effective Erasure Codes for Reliable Computer Communication Protocols", ACM SIGCOMM Computer Communication Review Vol.27, No.2, pp.24-36, April 1997. [6] Luby, M., "Raptor Forward Error Correction Scheme", Internet Draft (draft-ietf-rmt-bb-fec-raptor-object-01 : work in progress), June 2005. [7] Roca, V., "Low Density Parity Check (LDPC) Forward Error Correction", Internet Draft (draft-roca-rmt-ldpc-00.txt : work in progress), June 2005. [8] Mac Williams, F. and N. Sloane, "The Theory of Error Correcting Codes", North Holland, 1977 . [9] Shparlinski, I., "On the singularity of generalised Vandermonde matrices over finite fields", Finite Fields and Their Appl., 2005, v.11, 193-199. . [10] Bloemer, J., "Error Control Coding: Fundamentals and Applications", An XOR-Based Erasure-Resilient Coding Scheme", ICSI report TR-95-048, August 1995. . [11] Lacan, J. and J. Fimes, "Systematic MDS Erasure Codes based on Vandermonde Matrices", IEEE Communications Letters, pp. 570- 572, Vol. 8, Issue 9, Sept. 2004. . [12] Gohberg, I. and V. Olshevsky, "Fast algorithms with preprocessing for matrix-vector multiplication problems", Journal of Complexity, pp. 411-427, vol. 10, 1994 . Lacan, et al. Expires April 20, 2006 [Page 13] Internet-Draft draft-lacan-rmt-fec-bb-rs-00 October 2005 Authors' Addresses Jerome Lacan ENSICA/LAAS-CNRS 1, place Emile Blouin Toulouse 31056 France Email: jerome.lacan@ensica.fr URI: Vincent Roca INRIA 655, av. de l'Europe Zirst; Montbonnot ST ISMIER cedex 38334 France Email: vincent.roca@inrialpes.fr URI: Tampere University of Technology P.O. Box 553 (Korkeakoulunkatu 1) Tampere FIN-33101 Finland Email: jani.peltotalo@tut.fi URI: Tampere University of Technology P.O. Box 553 (Korkeakoulunkatu 1) Tampere FIN-33101 Finland Email: sami.peltotalo@tut.fi URI: Lacan, et al. Expires April 20, 2006 [Page 14] Internet-Draft draft-lacan-rmt-fec-bb-rs-00 October 2005 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights 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; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat 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 implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM 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. Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Lacan, et al. Expires April 20, 2006 [Page 15]