tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Gloss.     Arch.     IMS     UICC    |    Misc.    |    search     info

RFC 6330

Proposed STD
Pages: 69
Top     in Index     Prev     Next
in Group Index     Prev in Group     Next in Group     Group: RMT

RaptorQ Forward Error Correction Scheme for Object Delivery

Part 1 of 4, p. 1 to 12
None       Next RFC Part

 


Top       ToC       Page 1 
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 Delivery

Abstract

   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.

Page 2 
   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.

Top       Page 3 
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

Top      ToC       Page 4 
   7.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 67
   8.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 67
   9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 67
     9.1.  Normative References . . . . . . . . . . . . . . . . . . . 67
     9.2.  Informative References . . . . . . . . . . . . . . . . . . 68

1.  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].

Top      ToC       Page 5 
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.

Top      ToC       Page 6 
   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.

Top      ToC       Page 7 
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

Top      ToC       Page 8 
   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

Top      ToC       Page 9 
   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

Top      ToC       Page 10 
   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.

Top      ToC       Page 11 
   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.

Top      ToC       Page 12 
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)

Next RFC Part