From 4bfd864f10b68b71482b35c818559068ef8d5797 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Wed, 27 Nov 2024 20:54:24 +0100 Subject: doc: Add RFC documents --- doc/rfc/rfc5510.txt | 1571 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1571 insertions(+) create mode 100644 doc/rfc/rfc5510.txt (limited to 'doc/rfc/rfc5510.txt') diff --git a/doc/rfc/rfc5510.txt b/doc/rfc/rfc5510.txt new file mode 100644 index 0000000..3ec58b7 --- /dev/null +++ b/doc/rfc/rfc5510.txt @@ -0,0 +1,1571 @@ + + + + + + +Network Working Group J. Lacan +Request for Comments: 5510 ISAE/LAAS-CNRS +Category: Standards Track V. Roca + INRIA + J. Peltotalo + S. Peltotalo + Tampere University of Technology + April 2009 + + + Reed-Solomon Forward Error Correction (FEC) Schemes + +Status of This Memo + + This document specifies an Internet standards track protocol for the + Internet community, and requests discussion and suggestions for + improvements. Please refer to the current edition of the "Internet + Official Protocol Standards" (STD 1) for the standardization state + and status of this protocol. Distribution of this memo is unlimited. + +Copyright Notice + + Copyright (c) 2009 IETF Trust and the persons identified as the + document authors. All rights reserved. + + This document is subject to BCP 78 and the IETF Trust's Legal + Provisions Relating to IETF Documents in effect on the date of + publication of this document (http://trustee.ietf.org/license-info). + Please review these documents carefully, as they describe your rights + and restrictions with respect to this document. + + This document may contain material from IETF Documents or IETF + Contributions published or made publicly available before November + 10, 2008. The person(s) controlling the copyright in some of this + material may not have granted the IETF Trust the right to allow + modifications of such material outside the IETF Standards Process. + Without obtaining an adequate license from the person(s) controlling + the copyright in such materials, this document may not be modified + outside the IETF Standards Process, and derivative works of it may + not be created outside the IETF Standards Process, except to format + it for publication as an RFC or to translate it into languages other + than English. + + + + + + + + + +Lacan, et al. Standards Track [Page 1] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + +Abstract + + This document describes a Fully-Specified Forward Error Correction + (FEC) Scheme for the Reed-Solomon FEC codes over GF(2^^m), where m is + in {2..16}, and its application to the reliable delivery of data + objects on the packet erasure channel (i.e., a communication path + where packets are either received without any corruption or discarded + during transmission). This document also describes a Fully-Specified + FEC Scheme for the special case of Reed-Solomon codes over GF(2^^8) + when there is no encoding symbol group. Finally, in the context of + the Under-Specified Small Block Systematic FEC Scheme (FEC Encoding + ID 129), this document assigns an FEC Instance ID to the special case + of Reed-Solomon codes over GF(2^^8). + + 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 schemes described + here are compatible with the implementation from Luigi Rizzo. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Lacan, et al. Standards Track [Page 2] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + +Table of Contents + + 1. Introduction ....................................................4 + 2. Terminology .....................................................5 + 3. Definitions Notations and Abbreviations .........................5 + 3.1. Definitions ................................................5 + 3.2. Notations ..................................................6 + 3.3. Abbreviations ..............................................7 + 4. Formats and Codes with FEC Encoding ID 2 ........................7 + 4.1. FEC Payload ID .............................................7 + 4.2. FEC Object Transmission Information ........................8 + 4.2.1. Mandatory Elements ..................................8 + 4.2.2. Common Elements .....................................8 + 4.2.3. Scheme-Specific Elements ............................9 + 4.2.4. Encoding Format .....................................9 + 5. Formats and Codes with FEC Encoding ID 5 .......................11 + 5.1. FEC Payload ID ............................................11 + 5.2. FEC Object Transmission Information .......................12 + 5.2.1. Mandatory Elements .................................12 + 5.2.2. Common Elements ....................................12 + 5.2.3. Scheme-Specific Elements ...........................12 + 5.2.4. Encoding Format ....................................12 + 6. Procedures with FEC Encoding IDs 2 and 5 .......................13 + 6.1. Determining the Maximum Source Block Length (B) ...........13 + 6.2. Determining the Number of Encoding Symbols of a Block .....14 + 7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) + and Reed-Solomon Codes over GF(2^^8) ...........................15 + 8. Reed-Solomon Codes Specification for the Erasure Channel .......16 + 8.1. Finite Field ..............................................16 + 8.2. Reed-Solomon Encoding Algorithm ...........................17 + 8.2.1. Encoding Principles ................................17 + 8.2.2. Encoding Complexity ................................18 + 8.3. Reed-Solomon Decoding Algorithm ...........................18 + 8.3.1. Decoding Principles ................................18 + 8.3.2. Decoding Complexity ................................19 + 8.4. Implementation for the Packet Erasure Channel .............19 + 9. Security Considerations ........................................22 + 9.1. Problem Statement .........................................22 + 9.2. Attacks against the Data Flow .............................23 + 9.2.1. Access to Confidential Objects .....................23 + 9.2.2. Content Corruption .................................23 + 9.3. Attacks against the FEC Parameters ........................24 + 10. IANA Considerations ...........................................25 + 11. Acknowledgments ...............................................25 + 12. References ....................................................26 + 12.1. Normative References .....................................26 + 12.2. Informative References ...................................26 + + + + +Lacan, et al. Standards Track [Page 3] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + +1. Introduction + + The use of Forward Error Correction (FEC) codes is a classical + solution to improve the reliability of multicast and broadcast + transmissions. The [RFC5052] document describes a general framework + to use FEC in Content Delivery Protocols (CDPs). The companion + document [RFC3453] describes some applications of FEC codes for + content delivery. + + Recent FEC schemes like [RFC5053] and [RFC5170] proposed erasure + codes based on sparse graphs/matrices. These codes are efficient in + terms of processing but not optimal in terms of correction + capabilities when dealing with "small" objects. + + The FEC schemes described in this document belongs to the class of + Maximum Distance Separable codes that are optimal in terms of erasure + correction capability. In others words, it enables a receiver to + recover the k source symbols from any set of exactly k encoding + symbols. They are also systematic codes, which means that the k + source symbols are part of the encoding symbols. Even if the + encoding/decoding complexity is larger than that of [RFC5053] or + [RFC5170], this family of codes is very useful. + + Many applications dealing with content transmission or content + storage already rely on packet-based Reed-Solomon codes. In + particular, many of them use the Reed-Solomon codec of Luigi Rizzo + [RS-codec] [Rizzo97]. The goal of the present document is to specify + an implementation of Reed-Solomon codes that is compatible with this + codec. + + The present document: + + o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 2, + which specifies the use of Reed-Solomon codes over GF(2^^m), where + m is in {2..16}, + + o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 5, + which focuses on the special case of Reed-Solomon codes over + GF(2^^8) and no encoding symbol group (i.e., exactly one symbol + per packet), and + + o in the context of the Under-Specified Small Block Systematic FEC + Scheme (FEC Encoding ID 129) [RFC5445], assigns the FEC Instance + ID 0 to the special case of Reed-Solomon codes over GF(2^^8) and + no encoding symbol group. + + For a definition of the terms Fully-Specified and Under-Specified FEC + Schemes, see [RFC5052], Section 4. + + + +Lacan, et al. Standards Track [Page 4] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + +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 [RFC2119]. + +3. Definitions Notations and Abbreviations + +3.1. Definitions + + This document uses the same terms and definitions as those specified + in [RFC5052]. Additionally, it uses the following definitions: + + Source symbol: unit of data used during the encoding process. + + Encoding symbol: unit of data generated by the encoding process. + + Repair symbol: encoding symbol that is not a source symbol. + + Code rate: the k/n ratio, i.e., the ratio between the number of + source symbols and the number of encoding symbols. By + definition, the code rate is such that: 0 < code rate <= 1. A + code rate close to 1 indicates that a small number of repair + symbols have been produced during the encoding process. + + Systematic code: FEC code in which the source symbols are part of + the encoding symbols. + + Source block: a block of k source symbols that are considered + together for the encoding. + + Encoding Symbol Group: a group of encoding symbols that are sent + together within the same packet, and whose relationships to the + source block can be derived from a single Encoding Symbol ID. + + Source Packet: a data packet containing only source symbols. + + Repair Packet: a data packet containing only repair symbols. + + Packet Erasure Channel: a communication path where packets are + either dropped (e.g., by a congested router, or because the + number of transmission errors exceeds the correction + capabilities of the physical layer codes) or received. When a + packet is received, it is assumed that this packet is not + corrupted. + + + + + + +Lacan, et al. Standards Track [Page 5] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + +3.2. Notations + + This document uses the following notations: + + L the object transfer length in bytes. + + k the number of source symbols in a source block. + + n_r the number of repair symbols generated for a source block. + + n the encoding block length, i.e., the number of encoding + symbols generated for a source block. Therefore: n = k + + n_r. + + max_n the maximum number of encoding symbols generated for any + source block. + + B the maximum source block length in symbols, i.e., the + maximum number of source symbols per source block. + + N the number of source blocks into which the object shall be + partitioned. + + E the encoding symbol length in bytes. + + S the symbol size in units of m-bit elements. When m = 8, + then S and E are equal. + + m the length of the elements in the finite field, in bits. + In this document, m belongs to {2..16}. + + q the number of elements in the finite field. We have: q = + 2^^m in this specification. + + G the number of encoding symbols per group, i.e., the number + of symbols sent in the same packet. + + GM the Generator Matrix of a Reed-Solomon code. + + CR the "code rate", i.e., the k/n ratio. + + a^^b a raised to the power b. + + a^^-1 the inverse of a. + + I_k the k*k identity matrix. + + + + + +Lacan, et al. Standards Track [Page 6] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + +3.3. Abbreviations + + This document uses the following abbreviations: + + ESI Encoding Symbol ID. + + FEC OTI FEC Object Transmission Information. + + RS Reed-Solomon. + + MDS Maximum Distance Separable code. + + GF(q) a finite field (also known as Galois Field) with q + elements. We assume that q = 2^^m in this document. + +4. Formats and Codes with FEC Encoding ID 2 + + This section introduces the formats and codes associated with the + Fully-Specified FEC Scheme with FEC Encoding ID 2, which specifies + the use of Reed-Solomon codes over GF(2^^m). + +4.1. FEC Payload ID + + The FEC Payload ID is composed of the Source Block Number and the + Encoding Symbol ID. The lengths of these two fields depend on the + parameter m (which is transmitted in the FEC OTI) as follows: + + o The Source Block Number (field of size 32-m bits) identifies from + which source block of the object the encoding symbol(s) in the + payload are generated. There is a maximum of 2^^(32-m) blocks per + object. + + o The Encoding Symbol ID (field of size m bits) identifies which + specific encoding symbol(s) generated from the source block are + carried in the packet payload. There is a maximum of 2^^m + 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 source or repair packet. + In case of an 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. + + + + + + + +Lacan, et al. Standards Track [Page 7] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + 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 (32-8=24 bits) | Enc. Symb. ID | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Figure 1: FEC Payload ID Encoding Format for m = 8 (Default) + + + 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 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Src Block Nb (32-16=16 bits) | Enc. Symbol ID (m=16 bits) | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Figure 2: FEC Payload ID Encoding Format for m = 16 + + The formats of the FEC Payload ID for m = 8 and m = 16 are + illustrated in Figure 1 and Figure 2, respectively. + +4.2. FEC Object Transmission Information + +4.2.1. Mandatory Elements + + o FEC Encoding ID: the Fully-Specified FEC Scheme described in this + section uses FEC Encoding ID 2. + +4.2.2. Common Elements + + The following elements MUST be defined 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: + + max_transfer_length = 2^^(32-m) * B * E + + For instance, for m = 8, for B = 2^^8 - 1 (because the codec + operates on a finite field with 2^^8 elements), and if E = 1024 + bytes, then the maximum transfer length is approximately equal to + 2^^42 bytes (i.e., 4 terabytes). Similarly, for m = 16, for B = + 2^^16 - 1, and if E = 1024 bytes, then the maximum transfer length + is also approximately equal to 2^^42 bytes. For larger objects, + another FEC scheme, with a larger Source Block Number field in the + FEC Payload ID, could be defined. Another solution consists in + fragmenting large objects into smaller objects, each of them + complying with the above limits. + + + + +Lacan, et al. Standards Track [Page 8] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + 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. + + Section 6 explains how to derive the values of each of these + elements. + +4.2.3. Scheme-Specific Elements + + The following element MUST be defined with the present FEC scheme. + It contains two distinct pieces of information: + + o G: a non-negative integer indicating the number of encoding + symbols per group used for the object. The default value is 1, + meaning that each packet contains exactly one symbol. When no G + parameter is communicated to the decoder, then the latter MUST + assume that G = 1. + + o m: The m parameter is the length of the finite field elements, in + bits. It also characterizes the number of elements in the finite + field: q = 2^^m elements. The default value is m = 8. When no + finite field size parameter is communicated to the decoder, then + the latter MUST assume that m = 8. + +4.2.4. Encoding Format + + This section shows the two possible encoding formats of the above FEC + OTI. The present document does not specify when one encoding format + or the other 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 (e.g., within the ALC [ALC] or NORM [NORM] + protocols). + + + + + + + + + + +Lacan, et al. Standards Track [Page 9] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + 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 = 4 | | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + | Transfer Length (L) | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | m | G | Encoding Symbol Length (E) | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Max Source Block Length (B) | Max Nb Enc. Symbols (max_n) | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Figure 3: EXT_FTI Header Format + +4.2.4.2. Using the FDT Instance (FLUTE specific) + + When it is desired that the FEC OTI be carried in the FDT (File + Delivery Table) Instance of a FLUTE session [FLUTE], the following + XML attributes must be described for the associated object: + + o FEC-OTI-FEC-Encoding-ID + + o FEC-OTI-Transfer-Length (L) + + o FEC-OTI-Encoding-Symbol-Length (E) + + o FEC-OTI-Maximum-Source-Block-Length (B) + + o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) + + o FEC-OTI-Scheme-Specific-Info + + The FEC-OTI-Scheme-Specific-Info contains the string resulting from + the Base64 encoding (in the XML Schema xs:base64Binary sense) of the + following value: + + 0 1 + 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | m | G | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Figure 4: FEC OTI Scheme Specific Information To Be Included in the + FDT Instance + + When no m parameter is to be carried in the FEC OTI, the m field is + set to 0 (which is not a valid seed value). Otherwise, the m field + contains a valid value as explained in Section 4.2.3. Similarly, + + + +Lacan, et al. Standards Track [Page 10] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + when no G parameter is to be carried in the FEC OTI, the G field is + set to 0 (which is not a valid seed value). Otherwise, the G field + contains a valid value as explained in Section 4.2.3. When neither m + nor G are to be carried in the FEC OTI, then the sender simply omits + the FEC-OTI-Scheme-Specific-Info attribute. + + During Base64 encoding, the 2 bytes of the FEC OTI Scheme-Specific + Information are transformed into a string of 4 printable characters + (in the 64-character alphabet) that is added to the FEC-OTI-Scheme- + Specific-Info attribute. + +5. Formats and Codes with FEC Encoding ID 5 + + This section introduces the formats and codes associated with the + Fully-Specified FEC Scheme with FEC Encoding ID 5, which focuses on + the special case of Reed-Solomon codes over GF(2^^8) and no encoding + symbol group. + +5.1. FEC Payload ID + + The FEC Payload ID is composed of the Source Block Number and the + Encoding Symbol ID: + + o The Source Block Number (24-bit field) identifies from which + source block of the object the encoding symbol in the payload is + generated. There is a maximum of 2^^24 blocks per object. + + o The Encoding Symbol ID (8-bit field) identifies which specific + encoding symbol generated from the source block is carried in the + packet payload. There is a maximum of 2^^8 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 source or repair packet. + This FEC Payload ID refers to the one and only symbol of the packet. + + 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 (24 bits) | Enc. Symb. ID | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Figure 5: FEC Payload ID Encoding Format with FEC Encoding ID 5 + + + + + + + + +Lacan, et al. Standards Track [Page 11] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + +5.2. FEC Object Transmission Information + +5.2.1. Mandatory Elements + + o FEC Encoding ID: the Fully-Specified FEC Scheme described in this + section uses FEC Encoding ID 5. + +5.2.2. Common Elements + + The Common elements are the same as those specified in Section 4.2.2 + when m = 8 and G = 1. + +5.2.3. Scheme-Specific Elements + + No Scheme-Specific elements are defined by this FEC scheme. + +5.2.4. Encoding Format + + This section shows the two possible encoding formats of the above FEC + OTI. The present document does not specify when one encoding format + or the other should be used. + +5.2.4.1. Using the General EXT_FTI Format + + The FEC OTI binary format is the following, when the EXT_FTI + mechanism is used (e.g., within the ALC [ALC] or NORM [NORM] + protocols). + + 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 = 3 | | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + | Transfer Length (L) | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Encoding Symbol Length (E) | MaxBlkLen (B) | max_n | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Figure 6: EXT_FTI Header Format with FEC Encoding ID 5 + +5.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 [FLUTE], the following XML attributes must be + described for the associated object: + + o FEC-OTI-FEC-Encoding-ID + + + + +Lacan, et al. Standards Track [Page 12] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + o FEC-OTI-Transfer-Length (L) + + o FEC-OTI-Encoding-Symbol-Length (E) + + o FEC-OTI-Maximum-Source-Block-Length (B) + + o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) + +6. Procedures with FEC Encoding IDs 2 and 5 + + This section defines procedures that are common to FEC Encoding IDs 2 + and 5. In case of FEC Encoding ID 5, m = 8 and G = 1. The block + partitioning algorithm that is defined in Section 9.1 of [RFC5052] + MUST be used with FEC Encoding IDs 2 and 5. + +6.1. Determining the Maximum Source Block Length (B) + + The finite field size parameter, m, defines the number of non-zero + elements in this field, which is equal to: q - 1 = 2^^m - 1. Note + that q - 1 is also the theoretical maximum number of encoding symbols + that can be produced for a source block. For instance, when m = 8 + (default) there is a maximum of 2^^8 - 1 = 255 encoding symbols. + + Given the target FEC code rate (e.g., provided by the user when + starting a FLUTE sending application), the sender calculates: + + max1_B = floor((2^^m - 1) * CR) + + This max1_B value leaves enough room for the sender to produce the + desired number of parity symbols. + + Additionally, a codec MAY impose other limitations on the maximum + block size. Yet it is not expected that such limits exist when using + the default m = 8 value. This decision MUST 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. + + + + + + + + +Lacan, et al. Standards Track [Page 13] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + +6.2. Determining the Number of Encoding Symbols of a Block + + The following algorithm, also called "n-algorithm", explains how to + determine the maximum number of encoding symbols generated for any + source block (max_n) and the number of encoding symbols for a given + block (n) as a function of the target code rate. + + AT A SENDER: + + Input: + + B: Maximum source block length, for any source block. Section 6.1 + explains how to determine its value. + + k: Current source block length. This parameter is given by the + block partitioning algorithm. + + CR: FEC code rate, which is given by the user (e.g., when starting + a FLUTE sending application). 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: + + max_n = ceil(B / CR); + + if (max_n > 2^^m - 1), then return an error ("invalid code rate"); + + 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 block partitioning algorithm. + + + + + + +Lacan, et al. Standards Track [Page 14] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + Output: + + n + + Algorithm: + + n = floor(k * max_n / B); + + It is RECOMMENDED that the "n-algorithm" be used by a sender, but + other algorithms remain possible to determine max_n and/or n. + + At a receiver, the max_n value is extracted from the received FEC + OTI. Since the Reed-Solomon decoder does not need to know the actual + n value, using the receiver part of the "n-algorithm" is not + necessary from a decoding point of view. + + However, a receiver may want to have an estimate of n for other + reasons (e.g., for memory management purposes). In that case, a + receiver knows that the number of encoding symbols of a block cannot + exceed max_n. Additionally, if a receiver believes that a sender + uses the "n-algorithm", this receiver MAY use the receiver part of + the "n-algorithm" to get a better estimate of n. When this is the + case, a receiver MUST be prepared to handle symbols with an Encoding + Symbol ID superior or equal to the computed n value (e.g., it can + choose to simply drop them). + +7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) and Reed- + Solomon Codes over GF(2^^8) + + In the context of the Under-Specified Small Block Systematic FEC + Scheme (FEC Encoding ID 129) [RFC5445], this document assigns the FEC + Instance ID 0 to the special case of Reed-Solomon codes over GF(2^^8) + and no encoding symbol group. + + The FEC Instance ID 0 uses the Formats and Codes specified in + [RFC5445]. + + The FEC scheme with FEC Instance ID 0 MAY use the block partitioning + algorithm defined in Section 9.1 of [RFC5052] to partition the object + into source blocks. This FEC scheme MAY also use another algorithm. + For instance, the CDP sender may change the length of each source + block dynamically, depending on some external criteria (e.g., to + adjust the FEC coding rate to the current loss rate experienced by + NORM receivers) and inform the CDP receivers of the current block + length by means of the EXT_FTI mechanism. This choice is out of the + scope of the current document. + + + + + +Lacan, et al. Standards Track [Page 15] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + +8. Reed-Solomon Codes Specification for the Erasure Channel + + Reed-Solomon (RS) codes are linear block codes. They also belong to + the class of MDS codes. A [n,k]-RS code encodes a sequence of k + source elements defined over a finite field GF(q) into a sequence of + n encoding elements, where n is upper bounded by q - 1. The + implementation described in this document is based on a generator + matrix built from a Vandermonde matrix put into systematic form. + + Sections 8.1 to 8.3 specify the [n,k]-RS codes when applied to m-bit + elements, and Section 8.4 specifies the use of [n,k]-RS codes when + applied to symbols composed of several m-bit elements. The use + described in Section 8.4 is the crux of this specification. + + A reader who wants to understand the underlying theory is invited to + refer to references [Rizzo97] and [MWS77]. + +8.1. Finite Field + + A finite field GF(q) is defined as a finite set of q elements that + has a structure of field. It contains necessarily q = p^^m elements, + where p is a prime number. With packet erasure channels, p is always + set to 2. The elements of the field GF(2^^m) can be represented by + polynomials with binary coefficients (i.e., over GF(2)) of degree + lower or equal to m-1. The polynomials can be associated with binary + vectors of length m. For example, the vector (11001) 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 GF(2) and the + multiplication is the multiplication modulo a given irreducible + polynomial over GF(2) of degree m. Note that all the roots of this + polynomial are in GF(2^^m) but not in GF(2). + + The chosen polynomial representation of the finite field GF(2^^m) is + completely characterized by the irreducible polynomial. The + following polynomials are chosen to represent the field GF(2^^m), for + m varying from 2 to 16: + + m = 2, "111" (1+x+x^^2) + + m = 3, "1101", (1+x+x^^3) + + m = 4, "11001", (1+x+x^^4) + + m = 5, "101001", (1+x^^2+x^^5) + + m = 6, "1100001", (1+x+x^^6) + + + + +Lacan, et al. Standards Track [Page 16] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + m = 7, "10010001", (1+x^^3+x^^7) + + m = 8, "101110001", (1+x^^2+x^^3+x^^4+x^^8) + + m = 9, "1000100001", (1+x^^4+x^^9) + + m = 10, "10010000001", (1+x^^3+x^^10) + + m = 11, "101000000001", (1+x^^2+x^^11) + + m = 12, "1100101000001", (1+x+x^^4+x^^6+x^^12) + + m = 13, "11011000000001", (1+x+x^^3+x^^4+x^^13) + + m = 14, "110000100010001", (1+x+x^^6+x^^10+x^^14) + + m = 15, "1100000000000001", (1+x+x^^15) + + m = 16, "11010000000010001", (1+x+x^^3+x^^12+x^^16) + + In order to facilitate the implementation, these polynomials are also + primitive. This means that any element of GF(2^^m) can be expressed + as a power of a given root of this polynomial. These polynomials are + also chosen so that they contain the minimum number of monomials. + +8.2. Reed-Solomon Encoding Algorithm + +8.2.1. Encoding Principles + + Let s = (s_0, ..., s_{k-1}) be a source vector of k elements over + GF(2^^m). Let e = (e_0, ..., e_{n-1}) be the corresponding encoding + vector of n elements over GF(2^^m). Being a linear code, encoding is + performed by multiplying the source vector by a generator matrix, GM, + of k rows and n columns over GF(2^^m). Thus: + + e = s * GM. + + The definition of the generator matrix completely characterizes the + RS code. + + Let us consider that n = 2^^m - 1 and that 0 < k <= n. Let us denote + by alpha the root of the primitive polynomial of degree m chosen in + the list of Section 8.1 for the corresponding value of m. Let us + consider a Vandermonde matrix of k rows and n columns, denoted by + V_{k,n}, and built as follows: the {i, j} entry of V_{k,n} is v_{i,j} + = alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This + matrix generates a MDS code. However, this MDS code is not + systematic, which is a problem for many networking applications. To + + + +Lacan, et al. Standards Track [Page 17] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + obtain a systematic matrix (and code), the simplest solution consists + in considering the matrix V_{k,k} formed by the first k columns of + V_{k,n}, then to invert it and to multiply this inverse by V_{k,n}. + Clearly, the product V_{k,k}^^-1 * V_{k,n} contains the identity + matrix I_k on its first k columns, meaning that the first k encoding + elements are equal to source elements. Besides, the associated code + keeps the MDS property. + + Therefore, the generator matrix of the code considered in this + document is: + + GM = (V_{k,k}^^-1) * V_{k,n} + + Note that, in practice, the [n,k]-RS code can be shortened to a + [n',k]-RS code, where k <= n' < n, by considering the sub-matrix + formed by the n' first columns of GM. + +8.2.2. Encoding Complexity + + Encoding can be performed by first pre-computing GM and by + multiplying the source vector (k elements) by GM (k rows and n + columns). The complexity of the pre-computation of the generator + matrix can be estimated as the complexity of the multiplication of + the inverse of a Vandermonde matrix by n-k vectors (i.e., the last + n-k columns of V_{k,n}). Since the complexity of the inverse of a + k*k-Vandermonde matrix by a vector is O(k * (log(k))^^2), the + generator matrix can be computed in 0((n-k)* k * (log(k))^^2)) + operations. When the generator matrix is pre-computed, the encoding + needs k operations per repair element (vector-matrix multiplication). + + Encoding can also be performed by first computing the product s * + V_{k,k}^^-1 and then by multiplying the result with V_{k,n}. The + multiplication by the inverse of a square Vandermonde matrix is known + as the interpolation problem and its complexity is O(k * + (log(k))^^2). The multiplication by a Vandermonde matrix, known as + the multipoint evaluation problem, requires O((n-k) * log(k)) by + using Fast Fourier Transform, as explained in [GO94]. The total + complexity of this encoding algorithm is then O((k/(n-k)) * + (log(k))^^2 + log(k)) operations per repair element. + +8.3. Reed-Solomon Decoding Algorithm + +8.3.1. Decoding Principles + + The Reed-Solomon decoding algorithm for the erasure channel allows + the recovery of the k source elements from any set of k received + elements. It is based on the fundamental property of the generator + matrix, which is such that any k*k-submatrix is invertible (see + + + +Lacan, et al. Standards Track [Page 18] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + [MWS77]). The first step of the decoding consists in extracting the + k*k submatrix of the generator matrix obtained by considering the + columns corresponding to the received elements. Indeed, since any + encoding element is obtained by multiplying the source vector by one + column of the generator matrix, the received vector of k encoding + elements can be considered as the result of the multiplication of the + source vector by a k*k submatrix of the generator matrix. Since this + submatrix is invertible, the second step of the algorithm is to + invert this matrix and to multiply the received vector by the + obtained matrix to recover the source vector. + +8.3.2. Decoding Complexity + + The decoding algorithm described previously includes the matrix + inversion and the vector-matrix multiplication. With the classical + Gauss-Jordan algorithm, the matrix inversion requires O(k^^3) + operations and the vector-matrix multiplication is performed in + O(k^^2) operations. + + This complexity can be improved by considering that the received + submatrix of GM is the product between the inverse of a Vandermonde + matrix (V_(k,k)^^-1) and another Vandermonde matrix (denoted by V', + which is a submatrix of V_(k,n)). The decoding can be done by + multiplying the received vector by V'^^-1 (interpolation problem with + complexity O( k * (log(k))^^2) ) then by V_{k,k} (multipoint + evaluation with complexity O(k * log(k))). The global decoding + complexity is then O((log(k))^^2) operations per source element. + +8.4. Implementation for the Packet Erasure Channel + + In a packet erasure channel, each packet (including its symbol(s), + since packets contain G >= 1 symbols) is either correctly received or + erased. The location of the erased symbols in the sequence of + symbols MUST be known. The following specification describes the use + of Reed-Solomon codes for generating redundant symbols from the k + source symbols and for recovering the source symbols from any set of + k received symbols. + + The k source symbols of a source block are assumed to be composed of + S m-bit elements. Each m-bit element corresponds to an element of + the finite field GF(2^^m) through the polynomial representation + (Section 8.1). If some of the source symbols contain less than S + elements, they MUST be virtually padded with zero elements (this can + be the case for the last symbol of the last block of the object). + However, this padding does not need to be actually sent with the data + to the receivers. + + + + + +Lacan, et al. Standards Track [Page 19] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + The encoding process produces n encoding symbols of size S m-bit + elements, of which k are source symbols (this is a systematic code) + and n-k are repair symbols (Figure 7). The m-bit elements of the + repair symbols are calculated using the corresponding m-bit elements + of the source symbol set. A logical u-th source vector, comprised of + the u-th elements from the set of source symbols, is used to + calculate a u-th encoding vector. This u-th encoding vector then + provides the u-th elements for the set encoding symbols calculated + for the block. As a systematic code, the first k encoding symbols + are the same as the k source symbols, and the last n-k repair symbols + are the result of the Reed-Solomon encoding. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Lacan, et al. Standards Track [Page 20] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + Input: k source symbols + + 0 u S-1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | |X| | source symbol 0 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | |X| | source symbol 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + . . . + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | |X| | source symbol k-1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + * + + +--------------------+ + | generator matrix | + | GM | + | (k x n) | + +--------------------+ + + | + V + + Output: n encoding symbols (source + repair) + + 0 u S-1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | |X| | enc. symbol 0 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | |X| | enc. symbol 1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + . . . + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | |Y| | enc. symbol n-1 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Figure 7: Packet Encoding Scheme + + An asset of this scheme is that the loss of some encoding symbols + produces the same erasure pattern for each of the S encoding vectors. + It follows that the matrix inversion must be done only once and will + be used by all the S encoding vectors. For large S, this matrix + inversion cost becomes negligible in front of the S vector-matrix + multiplications. + + + + +Lacan, et al. Standards Track [Page 21] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + Another asset is that the n-k repair symbols can be produced on + demand. For instance, a sender can start by producing a limited + number of repair symbols and later on, depending on the observed + erasures on the channel, decide to produce additional repair symbols, + up to the n-k upper limit. Indeed, to produce the repair symbol e_j, + where k <= j < n, it is sufficient to multiply the S source vectors + with column j of GM. + +9. Security Considerations + +9.1. Problem Statement + + A content delivery system is potentially subject to many attacks: + some of them target the network (e.g., to compromise the routing + infrastructure, by compromising the congestion control component), + others target the Content Delivery Protocol (CDP) (e.g., to + compromise its normal behavior), and finally some attacks target the + content itself. Since this document focuses on a FEC building block + independently of any particular CDP (even if ALC and NORM are two + natural candidates), this section only discusses the additional + threats that an arbitrary CDP may be exposed to when using this + building block. + + More specifically, several kinds of attacks exist: + + o those that are meant to give access to confidential content (e.g., + in case of non-free content), + + o those that try to corrupt the object being transmitted (e.g., to + inject malicious code within an object or to prevent a receiver + from using an object), + + o and those that try to compromise the receiver's behavior (e.g., by + making the decoding of an object computationally expensive). + + These attacks can be launched either against the data flow itself + (e.g., by sending forged symbols) or against the FEC parameters that + are sent either in-band (e.g., in an EXT_FTI or FDT Instance) or out- + of-band (e.g., in a session description). + + + + + + + + + + + + +Lacan, et al. Standards Track [Page 22] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + +9.2. Attacks against the Data Flow + + First of all, let us consider the attacks against the data flow. + +9.2.1. Access to Confidential Objects + + Access control to the object being transmitted is typically provided + by means of encryption. This encryption can be done over the whole + object (e.g., by the content provider, before the FEC encoding + process), or be done on a packet per-packet basis (e.g., when IPsec + Encapsulating Security Payload (ESP) is used [RFC4303]). If access + control is a concern, it is RECOMMENDED that one of these solutions + be used. Even if we mention these attacks here, they are not related + nor facilitated by the use of FEC. + +9.2.2. Content Corruption + + Protection against corruptions (e.g., after sending forged packets) + is achieved by means of a content integrity verification/sender + authentication scheme. This service can be provided at the object + level, but in that case a receiver has no way to identify which + symbol(s) are corrupted if the object is detected as corrupted. This + service can also be provided at the packet level. In this case, + after removing all forged packets, the object may be recovered + sometimes. Several techniques can provide this source + authentication/content integrity service: + + o At the object level, the object MAY be digitally signed (with + public key cryptography), for instance by using RSASSA-PKCS1-v1_5 + [RFC3447]. This signature enables a receiver to check the object + integrity, once the object has been fully decoded. Even if + digital signatures are computationally expensive, this calculation + occurs only once per object, which is usually acceptable. + + o At the packet level, each packet can be digitally signed. A major + limitation is the high computational and transmission overheads + that this solution requires (unless Elliptic Curve Cryptography + (ECC) is used). To avoid this problem, the signature may span a + set of symbols (instead of a single one) in order to amortize the + signature calculation. But if a single symbol is missing, the + integrity of the whole set cannot be checked. + + o At the packet level, a Group Message Authentication Code (MAC) + [RFC2104] scheme can be used; for instance, by using HMAC-SHA-256 + with a secret key shared by all the group members (i.e., the + sender(s) and receivers). Thanks to the secret key, this + technique creates a cryptographically secured digest of a packet + that is sent along with the packet. The Group MAC scheme does not + + + +Lacan, et al. Standards Track [Page 23] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + create prohibitive processing load nor transmission overhead, but + it has a major limitation: it only provides a group + authentication/integrity service since all group members share the + same secret group key, which means that each member can send a + forged packet. It is therefore restricted to situations where + group members are fully trusted (or in association with another + technique as a pre-check). + + o At the packet level, TESLA [RFC4082] is a very attractive and + efficient solution that is robust to losses, provides a true + authentication/integrity service, and does not create any + prohibitive processing load or transmission overhead. Yet + checking a packet requires a small delay (a second or more) after + its reception. + + Techniques relying on public key cryptography (digital signatures and + TESLA during the bootstrap process, when used) require that public + keys be securely associated to the entities. This can be achieved by + a Public Key Infrastructure (PKI), or by a PGP Web of Trust, or by + pre-distributing the public keys of each group member. + + Techniques relying on symmetric key cryptography (group MAC) require + that a secret key be shared by all group members. This can be + achieved by means of a group key management protocol, or simply by + pre-distributing the secret key (but this manual solution has many + limitations). + + It is up to the developer and deployer, who know the security + requirements and features of the target application area, to define + which solution is the most appropriate. Nonetheless, in case there + is any concern of the threat of object corruption, it is RECOMMENDED + that at least one of these techniques be used. + +9.3. Attacks against the FEC Parameters + + Let us now consider attacks against the FEC parameters (or FEC OTI). + The FEC OTI can either be sent in-band (i.e., in an EXT_FTI or in an + FDT Instance containing FEC OTI for the object) or out-of-band (e.g., + in a session description). Attacks on these FEC parameters can + prevent the decoding of the associated object: for instance, + modifying the B parameter will lead to a different block partitioning + at a receiver thereby compromising decoding; or setting the m + parameter to 16 instead of 8 with FEC Encoding ID 2 will increase the + processing load while compromising decoding. + + It is therefore RECOMMENDED that security measures be taken to + guarantee the FEC OTI integrity. To that purpose, the packets + carrying the FEC parameters sent in-band in an EXT_FTI header + + + +Lacan, et al. Standards Track [Page 24] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + extension SHOULD be protected by one of the per-packet techniques + described above: digital signature, group MAC, or TESLA. When FEC + OTI is contained in an FDT Instance, this FDT Instance object SHOULD + be protected, for instance, by digitally signing it with XML digital + signatures [RFC3275]. Finally, when FEC OTI is sent out-of-band + (e.g., in a session description), this FEC OTI SHOULD be protected, + for instance, by digitally signing the object that includes this FEC + OTI. + + The same considerations concerning the key management aspects apply + here also. + +10. 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 [RFC5052]. + + This document assigns the Fully-Specified FEC Encoding ID 2 under the + "ietf:rmt:fec:encoding" name-space to "Reed-Solomon Codes over + GF(2^^m)". + + This document assigns the Fully-Specified FEC Encoding ID 5 under the + "ietf:rmt:fec:encoding" name-space to "Reed-Solomon Codes over + GF(2^^8)". + + This document assigns the FEC Instance ID 0 scoped by the Under- + Specified FEC Encoding ID 129 to "Reed-Solomon Codes over GF(2^^8)". + More specifically, under the "ietf:rmt:fec:encoding:instance" sub- + name-space that is scoped by the "ietf:rmt:fec:encoding" called + "Small Block Systematic FEC Codes", this document assigns FEC + Instance ID 0 to "Reed-Solomon Codes over GF(2^^8)". + +11. Acknowledgments + + The authors want to thank Brian Adamson, Igor Slepchin, Stephen Kent, + Francis Dupont, Elwyn Davies, Magnus Westerlund, and Alfred Hoenes + for their valuable comments. The authors also want to thank Luigi + Rizzo for his comments and for the design of the reference Reed- + Solomon codec. + + + + + + + + + + + +Lacan, et al. Standards Track [Page 25] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + +12. References + +12.1. Normative References + + [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate + Requirement Levels", BCP 14, RFC 2119, March 1997. + + [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error + Correction (FEC) Building Block", RFC 5052, August 2007. + + [RFC5445] Watson, M., "Basic Forward Error Correction (FEC) + Schemes", RFC 5445, March 2009. + +12.2. Informative References + + [RFC3453] 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. + + [RS-codec] Rizzo, L., "Reed-Solomon FEC codec", available at + http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz and + mirrored at http://planete-bcast.inrialpes.fr/, revised + version of July 1998. + + [Rizzo97] Rizzo, L., "Effective Erasure Codes for Reliable Computer + Communication Protocols", ACM SIGCOMM Computer + Communication Review Vol.27, No.2, pp.24-36, April 1997. + + [MWS77] Mac Williams, F. and N. Sloane, "The Theory of Error + Correcting Codes", North Holland, 1977. + + [GO94] Gohberg, I. and V. Olshevsky, "Fast algorithms with + preprocessing for matrix-vector multiplication problems", + Journal of Complexity, pp. 411-427, vol. 10, 1994. + + [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density + Parity Check (LDPC) Forward Error Correction", RFC 5170, + June 2008. + + [RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. + Stockhammer, "Raptor Forward Error Correction Scheme", + RFC 5053, October 2007. + + [ALC] Luby, M., Watson, M., and L. Vicisano, "Asynchronous + Layered Coding (ALC) Protocol Instantiation", Work + in Progress, November 2008. + + + + +Lacan, et al. Standards Track [Page 26] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + + [NORM] Adamson, B., Bormann, C., Handley, M., and J. Macker, + "NACK-Oriented Reliable Multicast Protocol", Work + in Progress, March 2009. + + [FLUTE] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. + Roca, "FLUTE - File Delivery over Unidirectional + Transport", Work in Progress, September 2008. + + [RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography + Standards (PKCS) #1: RSA Cryptography Specifications + Version 2.1", RFC 3447, February 2003. + + [RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)", + RFC 4303, December 2005. + + [RFC2104] "HMAC: Keyed-Hashing for Message Authentication", + RFC 2104, February 1997. + + [RFC4082] "Timed Efficient Stream Loss-Tolerant Authentication + (TESLA): Multicast Source Authentication Transform + Introduction", RFC 4082, June 2005. + + [RFC3275] Eastlake 3rd, D., Reagle, J., and D. Solo, "(Extensible + Markup Language) XML-Signature Syntax and Processing", + RFC 3275, March 2002. + + + + + + + + + + + + + + + + + + + + + + + + + + +Lacan, et al. Standards Track [Page 27] + +RFC 5510 Reed-Solomon Forward Error Correction April 2009 + + +Authors' Addresses + + Jerome Lacan + ISAE/LAAS-CNRS + 1, place Emile Blouin + Toulouse 31056 + France + + EMail: jerome.lacan@isae.fr + URI: http://pagespro.isae.fr/jerome-lacan/ + + + Vincent Roca + INRIA + 655, av. de l'Europe + Inovallee; Montbonnot + ST ISMIER cedex 38334 + France + + EMail: vincent.roca@inria.fr + URI: http://planete.inrialpes.fr/people/roca/ + + + Jani Peltotalo + Tampere University of Technology + P.O. Box 553 (Korkeakoulunkatu 1) + Tampere FIN-33101 + Finland + + EMail: jani.peltotalo@tut.fi + URI: http://mad.cs.tut.fi/ + + + Sami Peltotalo + Tampere University of Technology + P.O. Box 553 (Korkeakoulunkatu 1) + Tampere FIN-33101 + Finland + + EMail: sami.peltotalo@tut.fi + URI: http://mad.cs.tut.fi/ + + + + + + + + + + +Lacan, et al. Standards Track [Page 28] + -- cgit v1.2.3