rfc5053.Raptor_Forward_Error_Correction_Scheme_for_Object

Network Working Group M. Luby Request for Comments: 5053 Digital Fountain Category: Standards Track A. Shokrollahi EPFL M. Watson Digital Fountain T. Stockhammer Nomor Research October 2007 Raptor Forward Error Correction Scheme for Object Delivery 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. Abstract This document describes a Fully-Specified Forward Error Correction (FEC) scheme, corresponding to FEC Encoding ID 1, for the Raptor forward error correction code and its application to reliable delivery of data objects. Raptor is a fountain code, i.e., as many encoding symbols as needed can be generated by the encoder on-the-fly from the source symbols of a source block of data. The decoder is able to recover the source block from any set of encoding symbols only slightly more in number than the number of source symbols. The Raptor code described here is a systematic code, meaning that all the source symbols are among the encoding symbols that can be generated. Luby, et al. Standards Track [Page 1]

RFC 5053 Raptor FEC Scheme October 2007 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Requirements Notation . . . . . . . . . . . . . . . . . . . . 3 3. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 3 3.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 3 3.2. FEC Object Transmission Information (OTI) . . . . . . . . 4 3.2.1. Mandatory . . . . . . . . . . . . . . . . . . . . . . 4 3.2.2. Common . . . . . . . . . . . . . . . . . . . . . . . . 4 3.2.3. Scheme-Specific . . . . . . . . . . . . . . . . . . . 5 4. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.1. Content Delivery Protocol Requirements . . . . . . . . . . 5 4.2. Example Parameter Derivation Algorithm . . . . . . . . . . 6 5. Raptor FEC Code Specification . . . . . . . . . . . . . . . . 8 5.1. Definitions, Symbols, and Abbreviations . . . . . . . . . 8 5.1.1. Definitions . . . . . . . . . . . . . . . . . . . . . 8 5.1.2. Symbols . . . . . . . . . . . . . . . . . . . . . . . 9 5.1.3. Abbreviations . . . . . . . . . . . . . . . . . . . . 11 5.2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.3. Object Delivery . . . . . . . . . . . . . . . . . . . . . 12 5.3.1. Source Block Construction . . . . . . . . . . . . . . 12 5.3.2. Encoding Packet Construction . . . . . . . . . . . . . 14 5.4. Systematic Raptor Encoder . . . . . . . . . . . . . . . . 15 5.4.1. Encoding Overview . . . . . . . . . . . . . . . . . . 15 5.4.2. First Encoding Step: Intermediate Symbol Generation . 16 5.4.3. Second Encoding Step: LT Encoding . . . . . . . . . . 20 5.4.4. Generators . . . . . . . . . . . . . . . . . . . . . . 21 5.5. Example FEC Decoder . . . . . . . . . . . . . . . . . . . 23 5.5.1. General . . . . . . . . . . . . . . . . . . . . . . . 23 5.5.2. Decoding a Source Block . . . . . . . . . . . . . . . 23 5.6. Random Numbers . . . . . . . . . . . . . . . . . . . . . . 28 5.6.1. The Table V0 . . . . . . . . . . . . . . . . . . . . . 28 5.6.2. The Table V1 . . . . . . . . . . . . . . . . . . . . . 29 5.7. Systematic Indices J(K) . . . . . . . . . . . . . . . . . 30 6. Security Considerations . . . . . . . . . . . . . . . . . . . 43 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 43 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 44 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 44 9.1. Normative References . . . . . . . . . . . . . . . . . . . 44 9.2. Informative References . . . . . . . . . . . . . . . . . . 44 Luby, et al. Standards Track [Page 2]

RFC 5053 Raptor FEC Scheme October 2007 1. Introduction This document specifies an FEC Scheme for the Raptor forward error correction code for object delivery applications. The concept of an FEC Scheme is defined in [RFC5052] and this document follows the format prescribed there and uses the terminology of that document. Raptor Codes were introduced in [Raptor]. For an overview, see, for example, [CCNC]. The Raptor FEC Scheme is a Fully-Specified FEC Scheme corresponding to FEC Encoding ID 1. Raptor is a fountain code, i.e., as many encoding symbols as needed can be generated by the encoder on-the-fly from the source symbols of a block. The decoder is able to recover the source block from any set of encoding symbols only slightly more in number than the number of source symbols. The code described in this document is a systematic code, that is, the original source symbols can be sent unmodified from sender to receiver, as well as a number of repair symbols. For more background on the use of Forward Error Correction codes in reliable multicast, see [RFC3453]. The code described here is identical to that described in [MBMS]. 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. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Source Block Number | Encoding Symbol ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1: FEC Payload ID format Luby, et al. Standards Track [Page 3]

RFC 5053 Raptor FEC Scheme October 2007 Source Block Number (SBN), (16 bits): An integer identifier for the source block that the encoding symbols within the packet relate to. Encoding Symbol ID (ESI), (16 bits): An integer identifier for the encoding symbols within the packet. The interpretation of the Source Block Number and Encoding Symbol Identifier is defined in Section 5. 3.2. FEC Object Transmission Information (OTI) 3.2.1. Mandatory The value of the FEC Encoding ID MUST be 1 (one), as assigned by IANA (see Section 7). 3.2.2. Common The Common FEC Object Transmission Information elements used by this FEC Scheme are: - Transfer Length (F) - Encoding Symbol Length (T) The Transfer Length is a non-negative integer less than 2^^45. The Encoding Symbol Length is a non-negative integer less than 2^^16. The encoded Common FEC Object Transmission Information 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 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Encoding Symbol Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2: Encoded Common FEC OTI for Raptor FEC Scheme NOTE 1: The limit of 2^^45 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 2^^13, and the Luby, et al. Standards Track [Page 4]

RFC 5053 Raptor FEC Scheme October 2007 limitation on the number of source blocks to 2^^16. However, the Transfer Length is encoded as a 48-bit field for simplicity. 3.2.3. Scheme-Specific The following parameters are carried in the Scheme-Specific FEC Object Transmission Information element for this FEC Scheme: - The number of source blocks (Z) - The number of sub-blocks (N) - A symbol alignment parameter (Al) These parameters are all non-negative integers. The encoded Scheme- specific Object Transmission Information is a 4-octet field consisting of the parameters Z (2 octets), N (1 octet), and Al (1 octet) 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 14-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 5.3.1.2. 4. Procedures 4.1. Content Delivery Protocol Requirements This section describes the information exchange between the Raptor FEC Scheme and any Content Delivery Protocol (CDP) that makes use of the Raptor FEC Scheme for object delivery. The Raptor encoder and decoder for object delivery require the following information from the CDP: - The transfer length of the object, F, in bytes Luby, et al. Standards Track [Page 5]

RFC 5053 Raptor FEC Scheme October 2007 - A symbol alignment parameter, Al - The symbol size, T, in bytes, which MUST be a multiple of Al - The number of source blocks, Z - The number of sub-blocks in each source block, N The Raptor encoder for object delivery additionally requires: - the object to be encoded, F bytes The Raptor encoder supplies the CDP with the following information for each packet to be sent: - Source Block Number (SBN) - Encoding Symbol ID (ESI) - Encoding symbol(s) The CDP MUST communicate this information to the receiver. 4.2. 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: - F the transfer length of the object, in bytes - W a target on the sub-block size, in bytes - P the maximum packet payload size, in bytes, which is assumed to be a multiple of Al - Al the symbol alignment parameter, in bytes - Kmax the maximum number of source symbols per source block. Note: Section 5.1.2 defines Kmax to be 8192. - Kmin a minimum target on the number of symbols per source block - Gmax a maximum target number of symbols per packet Luby, et al. Standards Track [Page 6]

RFC 5053 Raptor FEC Scheme October 2007 Based on the above inputs, the transport parameters T, Z, and N are calculated as follows: Let G = min{ceil(P*Kmin/F), P/Al, Gmax} T = floor(P/(Al*G))*Al Kt = ceil(F/T) Z = ceil(Kt/Kmax) N = min{ceil(ceil(Kt/Z)*T/W), T/Al} The value G represents the maximum number of symbols to be transported in a single packet. The value Kt is the total number of symbols required to represent the source data of the object. The values of G and N derived above should be considered as lower bounds. It may be advantageous to increase these values, for example, to the nearest power of two. In particular, the above algorithm does not guarantee that the symbol size, T, divides the maximum packet size, P, and so it may not be possible to use the packets of size exactly P. If, instead, G is chosen to be a value that divides P/Al, then the symbol size, T, will be a divisor of P and packets of size P can be used. The algorithm above and that defined in Section 5.3.1.2 ensure that the sub-symbol sizes are a multiple of the symbol alignment parameter, Al. This is useful because the XOR operations used for encoding and decoding are generally performed several bytes at a time, for example, at least 4 bytes 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 bytes. Recommended settings for the input parameters, Al, Kmin, and Gmax are as follows: Al = 4, Kmin = 1024, Gmax = 10. The parameter W 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 W depends on the implementation, but it is possible to implement decoding using working memory only slightly larger than W. Luby, et al. Standards Track [Page 7]

RFC 5053 Raptor FEC Scheme October 2007 5. Raptor FEC Code Specification 5.1. Definitions, Symbols, and Abbreviations 5.1.1. Definitions For the purposes of this specification, the following terms and definitions apply. Source block: a block of K source symbols that are considered together for Raptor encoding purposes. Source symbol: the smallest unit of data used during the encoding process. All source symbols within a source block have the same size. Encoding symbol: a symbol that is included in a data packet. The encoding symbols consist of the source symbols and the repair symbols. Repair symbols generated from a source block have the same size as the source symbols of that source block. Systematic code: a code in which all the source symbols may be included as part of the encoding symbols sent for a source block. Repair symbol: the encoding symbols sent for a source block that are not the source symbols. The repair symbols are generated based on the source symbols. Intermediate symbols: symbols generated from the source symbols using an inverse encoding process . The repair symbols are then generated directly from the intermediate symbols. The encoding symbols do not include the intermediate symbols, i.e., intermediate symbols are not included in data packets. Symbol: a unit of data. The size, in bytes, of a symbol is known as the symbol size. Encoding symbol group: a group of encoding symbols that are sent together, i.e., within the same packet whose relationship to the source symbols can be derived from a single Encoding Symbol ID. Encoding Symbol ID: information that defines the relationship between the symbols of an encoding symbol group and the source symbols. Encoding packet: data packets that contain encoding symbols Luby, et al. Standards Track [Page 8]

资料库

rfc5053.Raptor_Forward_Error_Correction_Scheme_for_Object_Delive....pdf

相关推荐

课程资源

热门标签

最新资料