RFC 6330
RaptorQ Forward Error Correction Scheme for Object Delivery
Internet Engineering Task Force (IETF) M. Luby Request for Comments: 6330 Qualcomm Incorporated Category: Standards Track A. Shokrollahi ISSN: 2070-1721 EPFL M. Watson Netflix Inc. T. Stockhammer Nomor Research L. Minder Qualcomm Incorporated August 2011 RaptorQ Forward Error Correction Scheme for Object DeliveryAbstract
This document describes a Fully-Specified Forward Error Correction (FEC) scheme, corresponding to FEC Encoding ID 6, for the RaptorQ FEC code and its application to reliable delivery of data objects. RaptorQ codes are a new family of codes that provide superior flexibility, support for larger source block sizes, and better coding efficiency than Raptor codes in RFC 5053. RaptorQ is also a fountain code, i.e., as many encoding symbols as needed can be generated on the fly by the encoder from the source symbols of a source block of data. The decoder is able to recover the source block from almost any set of encoding symbols of sufficient cardinality -- in most cases, a set of cardinality equal to the number of source symbols is sufficient; in rare cases, a set of cardinality slightly more than the number of source symbols is required. The RaptorQ code described here is a systematic code, meaning that all the source symbols are among the encoding symbols that can be generated. Status of This Memo This is an Internet Standards Track document. This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Further information on Internet Standards is available in Section 2 of RFC 5741.
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc6330. Copyright Notice Copyright (c) 2011 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 (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 4 3. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 5 3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 5 3.2. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 5 3.3. FEC Object Transmission Information . . . . . . . . . . . 5 3.3.1. Mandatory . . . . . . . . . . . . . . . . . . . . . . 5 3.3.2. Common . . . . . . . . . . . . . . . . . . . . . . . . 5 3.3.3. Scheme-Specific . . . . . . . . . . . . . . . . . . . 6 4. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 7 4.2. Content Delivery Protocol Requirements . . . . . . . . . . 7 4.3. Example Parameter Derivation Algorithm . . . . . . . . . . 7 4.4. Object Delivery . . . . . . . . . . . . . . . . . . . . . 9 4.4.1. Source Block Construction . . . . . . . . . . . . . . 9 4.4.2. Encoding Packet Construction . . . . . . . . . . . . . 11 4.4.3. Example Receiver Recovery Strategies . . . . . . . . . 12 5. RaptorQ FEC Code Specification . . . . . . . . . . . . . . . . 12 5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 12 5.1.1. Definitions . . . . . . . . . . . . . . . . . . . . . 13 5.1.2. Symbols . . . . . . . . . . . . . . . . . . . . . . . 14 5.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.3. Systematic RaptorQ Encoder . . . . . . . . . . . . . . . . 18 5.3.1. Introduction . . . . . . . . . . . . . . . . . . . . . 18 5.3.2. Encoding Overview . . . . . . . . . . . . . . . . . . 19 5.3.3. First Encoding Step: Intermediate Symbol Generation . 21 5.3.4. Second Encoding Step: Encoding . . . . . . . . . . . . 27 5.3.5. Generators . . . . . . . . . . . . . . . . . . . . . . 27 5.4. Example FEC Decoder . . . . . . . . . . . . . . . . . . . 30 5.4.1. General . . . . . . . . . . . . . . . . . . . . . . . 30 5.4.2. Decoding an Extended Source Block . . . . . . . . . . 31 5.5. Random Numbers . . . . . . . . . . . . . . . . . . . . . . 36 5.5.1. The Table V0 . . . . . . . . . . . . . . . . . . . . . 36 5.5.2. The Table V1 . . . . . . . . . . . . . . . . . . . . . 37 5.5.3. The Table V2 . . . . . . . . . . . . . . . . . . . . . 38 5.5.4. The Table V3 . . . . . . . . . . . . . . . . . . . . . 40 5.6. Systematic Indices and Other Parameters . . . . . . . . . 41 5.7. Operating with Octets, Symbols, and Matrices . . . . . . . 62 5.7.1. General . . . . . . . . . . . . . . . . . . . . . . . 62 5.7.2. Arithmetic Operations on Octets . . . . . . . . . . . 62 5.7.3. The Table OCT_EXP . . . . . . . . . . . . . . . . . . 63 5.7.4. The Table OCT_LOG . . . . . . . . . . . . . . . . . . 64 5.7.5. Operations on Symbols . . . . . . . . . . . . . . . . 65 5.7.6. Operations on Matrices . . . . . . . . . . . . . . . . 65 5.8. Requirements for a Compliant Decoder . . . . . . . . . . . 65 6. Security Considerations . . . . . . . . . . . . . . . . . . . 66
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 67 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 67 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 67 9.1. Normative References . . . . . . . . . . . . . . . . . . . 67 9.2. Informative References . . . . . . . . . . . . . . . . . . 681. Introduction
This document specifies an FEC scheme for the RaptorQ forward error correction code for object delivery applications. The concept of an FEC scheme is defined in RFC 5052 [RFC5052], and this document follows the format prescribed there and uses the terminology of that document. The RaptorQ code described herein is a next generation of the Raptor code described in RFC 5053 [RFC5053]. The RaptorQ code provides superior reliability, better coding efficiency, and support for larger source block sizes than the Raptor code of RFC 5053 [RFC5053]. These improvements simplify the usage of the RaptorQ code in an object delivery Content Delivery Protocol compared to RFC 5053 RFC 5053 [RFC5053]. A detailed mathematical design and analysis of the RaptorQ code together with extensive simulation results are provided in [RaptorCodes]. The RaptorQ FEC scheme is a Fully-Specified FEC scheme corresponding to FEC Encoding ID 6. RaptorQ is a fountain code, i.e., as many encoding symbols as needed can be generated on the fly by the encoder from the source symbols of a block. The decoder is able to recover the source block from almost any set of encoding symbols of cardinality only slightly larger than the number of source symbols. The code described in this document is a systematic code; that is, the original unmodified source symbols, as well as a number of repair symbols, can be sent from sender to receiver. For more background on the use of Forward Error Correction codes in reliable multicast, see [RFC3453].2. Requirements Notation
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 [RFC2119].
3. Formats and Codes
3.1. Introduction
The octet order of all fields is network byte order, i.e., big- endian.3.2. FEC Payload IDs
The FEC Payload ID MUST be a 4-octet field 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SBN | Encoding Symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1: FEC Payload ID Format o Source Block Number (SBN): 8-bit unsigned integer. A non-negative integer identifier for the source block that the encoding symbols within the packet relate to. o Encoding Symbol ID (ESI): 24-bit unsigned integer. A non-negative integer identifier for the encoding symbols within the packet. The interpretation of the Source Block Number and Encoding Symbol Identifier is defined in Section 4.3.3. FEC Object Transmission Information
3.3.1. Mandatory
The value of the FEC Encoding ID MUST be 6, as assigned by IANA (see Section 7).3.3.2. Common
The Common FEC Object Transmission Information elements used by this FEC scheme are: o Transfer Length (F): 40-bit unsigned integer. A non-negative integer that is at most 946270874880. This is the transfer length of the object in units of octets. o Symbol Size (T): 16-bit unsigned integer. A positive integer that is less than 2^^16. This is the size of a symbol in units of octets.
The encoded Common FEC Object Transmission Information (OTI) format is shown in Figure 2. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Transfer Length (F) | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Reserved | Symbol Size (T) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2: Encoded Common FEC OTI for RaptorQ FEC Scheme NOTE: The limit of 946270874880 on the transfer length is a consequence of the limitation on the symbol size to 2^^16-1, the limitation on the number of symbols in a source block to 56403, and the limitation on the number of source blocks to 2^^8.3.3.3. Scheme-Specific
The following parameters are carried in the Scheme-Specific FEC Object Transmission Information element for this FEC scheme: o The number of source blocks (Z): 8-bit unsigned integer. o The number of sub-blocks (N): 16-bit unsigned integer. o A symbol alignment parameter (Al): 8-bit unsigned integer. These parameters are all positive integers. The encoded Scheme- specific Object Transmission Information is a 4-octet field consisting of the parameters Z, N, and Al as shown in Figure 3. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Z | N | Al | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3: Encoded Scheme-Specific FEC Object Transmission Information The encoded FEC Object Transmission Information is a 12-octet field consisting of the concatenation of the encoded Common FEC Object Transmission Information and the encoded Scheme-specific FEC Object Transmission Information. These three parameters define the source block partitioning as described in Section 4.4.1.2.
4. Procedures
4.1. Introduction
For any undefined symbols or functions used in this section, in particular the functions "ceil" and "floor", refer to Section 5.1.4.2. Content Delivery Protocol Requirements
This section describes the information exchange between the RaptorQ FEC scheme and any Content Delivery Protocol (CDP) that makes use of the RaptorQ FEC scheme for object delivery. The RaptorQ encoder scheme and RaptorQ decoder scheme for object delivery require the following information from the CDP: o F: the transfer length of the object, in octets o Al: the symbol alignment parameter o T: the symbol size in octets, which MUST be a multiple of Al o Z: the number of source blocks o N: the number of sub-blocks in each source block The RaptorQ encoder scheme for object delivery additionally requires: - the object to be encoded, which is F octets long The RaptorQ encoder scheme supplies the CDP with the following information for each packet to be sent: o Source Block Number (SBN) o Encoding Symbol ID (ESI) o Encoding symbol(s) The CDP MUST communicate this information to the receiver.4.3. Example Parameter Derivation Algorithm
This section provides recommendations for the derivation of the three transport parameters, T, Z, and N. This recommendation is based on the following input parameters: o F: the transfer length of the object, in octets
o WS: the maximum size block that is decodable in working memory, in
octets
o P': the maximum payload size in octets, which is assumed to be a
multiple of Al
o Al: the symbol alignment parameter, in octets
o SS: a parameter where the desired lower bound on the sub-symbol
size is SS*Al
o K'_max: the maximum number of source symbols per source block.
Note: Section 5.1.2 defines K'_max to be 56403.
Based on the above inputs, the transport parameters T, Z, and N are
calculated as follows:
Let
o T = P'
o Kt = ceil(F/T)
o N_max = floor(T/(SS*Al))
o for all n=1, ..., N_max
* KL(n) is the maximum K' value in Table 2 in Section 5.6 such
that
K' <= WS/(Al*(ceil(T/(Al*n))))
o Z = ceil(Kt/KL(N_max))
o N is the minimum n=1, ..., N_max such that ceil(Kt/Z) <= KL(n)
It is RECOMMENDED that each packet contains exactly one symbol.
However, receivers SHALL support the reception of packets that
contain multiple symbols.
The value Kt is the total number of symbols required to represent the
source data of the object.
The algorithm above and that defined in Section 4.4.1.2 ensure that
the sub-symbol sizes are a multiple of the symbol alignment
parameter, Al. This is useful because the sum operations used for
encoding and decoding are generally performed several octets at a
time, for example, at least 4 octets at a time on a 32-bit processor. Thus, the encoding and decoding can be performed faster if the sub- symbol sizes are a multiple of this number of octets. The recommended setting for the input parameter Al is 4. The parameter WS can be used to generate encoded data that can be decoded efficiently with limited working memory at the decoder. Note that the actual maximum decoder memory requirement for a given value of WS depends on the implementation, but it is possible to implement decoding using working memory only slightly larger than WS.4.4. Object Delivery
4.4.1. Source Block Construction
4.4.1.1. General
In order to apply the RaptorQ encoder to a source object, the object may be broken into Z >= 1 blocks, known as source blocks. The RaptorQ encoder is applied independently to each source block. Each source block is identified by a unique Source Block Number (SBN), where the first source block has SBN zero, the second has SBN one, etc. Each source block is divided into a number, K, of source symbols of size T octets each. Each source symbol is identified by a unique Encoding Symbol Identifier (ESI), where the first source symbol of a source block has ESI zero, the second has ESI one, etc. Each source block with K source symbols is divided into N >= 1 sub- blocks, which are small enough to be decoded in the working memory. Each sub-block is divided into K sub-symbols of size T'. Note that the value of K is not necessarily the same for each source block of an object, and the value of T' may not necessarily be the same for each sub-block of a source block. However, the symbol size T is the same for all source blocks of an object, and the number of symbols K is the same for every sub-block of a source block. Exact partitioning of the object into source blocks and sub-blocks is described in Section 4.4.1.2 below.4.4.1.2. Source Block and Sub-Block Partitioning
The construction of source blocks and sub-blocks is determined based on five input parameters -- F, Al, T, Z, and N -- and a function Partition[]. The five input parameters are defined as follows: o F: the transfer length of the object, in octets
o Al: a symbol alignment parameter, in octets o T: the symbol size, in octets, which MUST be a multiple of Al o Z: the number of source blocks o N: the number of sub-blocks in each source block These parameters MUST be set so that ceil(ceil(F/T)/Z) <= K'_max. Recommendations for derivation of these parameters are provided in Section 4.3. The function Partition[I,J] derives parameters for partitioning a block of size I into J approximately equal-sized blocks. More specifically, it partitions I into JL blocks of length IL and JS blocks of length IS. The output of Partition[I, J] is the sequence (IL, IS, JL, JS), where IL = ceil(I/J), IS = floor(I/J), JL = I - IS * J, and JS = J - JL. The source object MUST be partitioned into source blocks and sub- blocks as follows: Let o Kt = ceil(F/T), o (KL, KS, ZL, ZS) = Partition[Kt, Z], o (TL, TS, NL, NS) = Partition[T/Al, N]. Then, the object MUST be partitioned into Z = ZL + ZS contiguous source blocks, the first ZL source blocks each having KL*T octets, i.e., KL source symbols of T octets each, and the remaining ZS source blocks each having KS*T octets, i.e., KS source symbols of T octets each. If Kt*T > F, then, for encoding purposes, the last symbol of the last source block MUST be padded at the end with Kt*T-F zero octets. Next, each source block with K source symbols MUST be divided into N = NL + NS contiguous sub-blocks, the first NL sub-blocks each consisting of K contiguous sub-symbols of size of TL*Al octets and the remaining NS sub-blocks each consisting of K contiguous sub- symbols of size of TS*Al octets. The symbol alignment parameter Al ensures that sub-symbols are always a multiple of Al octets.
Finally, the mth symbol of a source block consists of the concatenation of the mth sub-symbol from each of the N sub-blocks. Note that this implies that when N > 1, a symbol is NOT a contiguous portion of the object.4.4.2. Encoding Packet Construction
Each encoding packet contains the following information: o Source Block Number (SBN) o Encoding Symbol ID (ESI) o encoding symbol(s) Each source block is encoded independently of the others. Each encoding packet contains encoding symbols generated from the one source block identified by the SBN carried in the encoding packet. Source blocks are numbered consecutively from zero. Encoding Symbol ID values from 0 to K-1 identify the source symbols of a source block in sequential order, where K is the number of source symbols in the source block. Encoding Symbol IDs K onwards identify repair symbols generated from the source symbols using the RaptorQ encoder. Each encoding packet either contains only source symbols (source packet) or contains only repair symbols (repair packet). A packet may contain any number of symbols from the same source block. In the case that the last source symbol in a source packet includes padding octets added for FEC encoding purposes, then these octets need not be included in the packet. Otherwise, each packet MUST contain only whole symbols. The Encoding Symbol ID, X, carried in each source packet is the Encoding Symbol ID of the first source symbol carried in that packet. The subsequent source symbols in the packet have Encoding Symbol IDs X+1 to X+G-1 in sequential order, where G is the number of symbols in the packet. Similarly, the Encoding Symbol ID, X, placed into a repair packet is the Encoding Symbol ID of the first repair symbol in the repair packet, and the subsequent repair symbols in the packet have Encoding Symbol IDs X+1 to X+G-1 in sequential order, where G is the number of symbols in the packet. Note that it is not necessary for the receiver to know the total number of repair packets.
4.4.3. Example Receiver Recovery Strategies
A receiver can use the received encoding symbols for each source block of an object to recover the source symbols for that source block independently of all other source blocks. If there is one sub-block per source block, i.e., N = 1, then the portion of the data in the original object in its original order associated with a source block consists of the concatenation of the source symbols of a source block in consecutive ESI order. If there are multiple sub-blocks per source block, i.e., if N > 1, then the portion of the data in the original object in its original order associated with a source block consists of the concatenation of the sub-blocks associated with the source block, where sub-symbols within each sub-block are in consecutive ESI order. In this case, there are different receiver source block recovery strategies worth considering depending on the available amount of Random Access Memory (RAM) at the receiver, as outlined below. One strategy is to recover the source symbols of a source block using the decoding procedures applied to the received symbols for the source block to recover the source symbols as described in Section 5, and then to reorder the sub-symbols of the source symbols so that all consecutive sub-symbols of the first sub-block are first, followed by all consecutive sub-symbols of the second sub-block, etc., followed by all consecutive sub-symbols of the Nth sub-block. This strategy is especially applicable if the receiver has enough RAM to decode an entire source block. Another strategy is to separately recover the sub-blocks of a source block. For example, a receiver may demultiplex and store sub-symbols associated with each sub-block separately as packets containing encoding symbols arrive, and then use the stored sub-symbols received for a sub-block to recover that sub-block using the decoding procedures described in Section 5. This strategy is especially applicable if the receiver has enough RAM to decode only one sub- block at a time.
(page 12 continued on part 2)
