Tech-invite3GPPspaceIETF RFCsSIP
93929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 6330

RaptorQ Forward Error Correction Scheme for Object Delivery

Pages: 69
Proposed Standard
Errata
Part 4 of 4 – Pages 62 to 69
First   Prev   None

Top   ToC   RFC6330 - Page 62   prevText

5.7. Operating with Octets, Symbols, and Matrices

5.7.1. General

The remainder of this section describes the arithmetic operations that are used to generate encoding symbols from source symbols and to generate source symbols from encoding symbols. Mathematically, octets can be thought of as elements of a finite field, i.e., the finite field GF(256) with 256 elements, and thus the addition and multiplication operations and identity elements and inverses over both operations are defined. Matrix operations and symbol operations are defined based on the arithmetic operations on octets. This allows a full implementation of these arithmetic operations without having to understand the underlying mathematics of finite fields.

5.7.2. Arithmetic Operations on Octets

Octets are mapped to non-negative integers in the range 0 through 255 in the usual way: A single octet of data from a symbol, B[7],B[6],B[5],B[4],B[3],B[2],B[1],B[0], where B[7] is the highest order bit and B[0] is the lowest order bit, is mapped to the integer i=B[7]*128+B[6]*64+B[5]*32+B[4]*16+B[3]*8+B[2]*4+B[1]*2+B[0]. The addition of two octets u and v is defined as the exclusive-or operation, i.e., u + v = u ^ v. Subtraction is defined in the same way, so we also have u - v = u ^ v.
Top   ToC   RFC6330 - Page 63
   The zero element (additive identity) is the octet represented by the
   integer 0.  The additive inverse of u is simply u, i.e.,

      u + u = 0.

   The multiplication of two octets is defined with the help of two
   tables OCT_EXP and OCT_LOG, which are given in Section 5.7.3 and
   Section 5.7.4, respectively.  The table OCT_LOG maps octets (other
   than the zero element) to non-negative integers, and OCT_EXP maps
   non-negative integers to octets.  For two octets u and v, we define

      u * v =

         0, if either u or v are 0,

         OCT_EXP[OCT_LOG[u] + OCT_LOG[v]] otherwise.

   Note that the '+' on the right-hand side of the above is the usual
   integer addition, since its arguments are ordinary integers.

   The division u / v of two octets u and v, and where v != 0, is
   defined as follows:

      u / v =

         0, if u == 0,

         OCT_EXP[OCT_LOG[u] - OCT_LOG[v] + 255] otherwise.

   The one element (multiplicative identity) is the octet represented by
   the integer 1.  For an octet u that is not the zero element, i.e.,
   the multiplicative inverse of u is

      OCT_EXP[255 - OCT_LOG[u]].

   The octet denoted by alpha is the octet with the integer
   representation 2.  If i is a non-negative integer 0 <= i < 256, we
   have

      alpha^^i = OCT_EXP[i].

5.7.3. The Table OCT_EXP

The table OCT_EXP contains 510 octets. The indexing starts at 0 and ranges to 509, and the entries are the octets with the following positive integer representation:
Top   ToC   RFC6330 - Page 64
   1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38, 76,
   152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192, 157,
   39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159, 35,
   70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111, 222,
   161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30, 60,
   120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163,
   91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26, 52,
   104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147, 59,
   118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218,
   169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85,
   170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198,
   145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171,
   75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25,
   50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81,
   162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9,
   18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11,
   22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71,
   142, 1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, 205, 135, 19, 38,
   76, 152, 45, 90, 180, 117, 234, 201, 143, 3, 6, 12, 24, 48, 96, 192,
   157, 39, 78, 156, 37, 74, 148, 53, 106, 212, 181, 119, 238, 193, 159,
   35, 70, 140, 5, 10, 20, 40, 80, 160, 93, 186, 105, 210, 185, 111,
   222, 161, 95, 190, 97, 194, 153, 47, 94, 188, 101, 202, 137, 15, 30,
   60, 120, 240, 253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223,
   163, 91, 182, 113, 226, 217, 175, 67, 134, 17, 34, 68, 136, 13, 26,
   52, 104, 208, 189, 103, 206, 129, 31, 62, 124, 248, 237, 199, 147,
   59, 118, 236, 197, 151, 51, 102, 204, 133, 23, 46, 92, 184, 109, 218,
   169, 79, 158, 33, 66, 132, 21, 42, 84, 168, 77, 154, 41, 82, 164, 85,
   170, 73, 146, 57, 114, 228, 213, 183, 115, 230, 209, 191, 99, 198,
   145, 63, 126, 252, 229, 215, 179, 123, 246, 241, 255, 227, 219, 171,
   75, 150, 49, 98, 196, 149, 55, 110, 220, 165, 87, 174, 65, 130, 25,
   50, 100, 200, 141, 7, 14, 28, 56, 112, 224, 221, 167, 83, 166, 81,
   162, 89, 178, 121, 242, 249, 239, 195, 155, 43, 86, 172, 69, 138, 9,
   18, 36, 72, 144, 61, 122, 244, 245, 247, 243, 251, 235, 203, 139, 11,
   22, 44, 88, 176, 125, 250, 233, 207, 131, 27, 54, 108, 216, 173, 71,
   142

5.7.4. The Table OCT_LOG

The table OCT_LOG contains 255 non-negative integers. The table is indexed by octets interpreted as integers. The octet corresponding to the zero element, which is represented by the integer 0, is excluded as an index, and thus indexing starts at 1 and ranges up to 255, and the entries are the following: 0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, 27, 104, 199, 75, 4, 100, 224, 14, 52, 141, 239, 129, 28, 193, 105, 248, 200, 8, 76, 113, 5, 138, 101, 47, 225, 36, 15, 33, 53, 147, 142, 218, 240, 18, 130, 69, 29, 181, 194, 125, 106, 39, 249, 185, 201, 154, 9, 120, 77, 228, 114,
Top   ToC   RFC6330 - Page 65
   166, 6, 191, 139, 98, 102, 221, 48, 253, 226, 152, 37, 179, 16, 145,
   34, 136, 54, 208, 148, 206, 143, 150, 219, 189, 241, 210, 19, 92,
   131, 56, 70, 64, 30, 66, 182, 163, 195, 72, 126, 110, 107, 58, 40,
   84, 250, 133, 186, 61, 202, 94, 155, 159, 10, 21, 121, 43, 78, 212,
   229, 172, 115, 243, 167, 87, 7, 112, 192, 247, 140, 128, 99, 13, 103,
   74, 222, 237, 49, 197, 254, 24, 227, 165, 153, 119, 38, 184, 180,
   124, 17, 68, 146, 217, 35, 32, 137, 46, 55, 63, 209, 91, 149, 188,
   207, 205, 144, 135, 151, 178, 220, 252, 190, 97, 242, 86, 211, 171,
   20, 42, 93, 158, 132, 60, 57, 83, 71, 109, 65, 162, 31, 45, 67, 216,
   183, 123, 164, 118, 196, 23, 73, 236, 127, 12, 111, 246, 108, 161,
   59, 82, 41, 157, 85, 170, 251, 96, 134, 177, 187, 204, 62, 90, 203,
   89, 95, 176, 156, 169, 160, 81, 11, 245, 22, 235, 122, 117, 44, 215,
   79, 174, 213, 233, 230, 231, 173, 232, 116, 214, 244, 234, 168, 80,
   88, 175

5.7.5. Operations on Symbols

Operations on symbols have the same semantics as operations on vectors of octets of length T in this specification. Thus, if U and V are two symbols formed by the octets u[0], ..., u[T-1] and v[0], ..., v[T-1], respectively, the sum of symbols U + V is defined to be the component-wise sum of octets, i.e., equal to the symbol D formed by the octets d[0], ..., d[T-1], such that d[i] = u[i] + v[i], 0 <= i < T. Furthermore, if beta is an octet, the product beta*U is defined to be the symbol D obtained by multiplying each octet of U by beta, i.e., d[i] = beta*u[i], 0 <= i < T.

5.7.6. Operations on Matrices

All matrices in this specification have entries that are octets, and thus matrix operations and definitions are defined in terms of the underlying octet arithmetic, e.g., operations on a matrix, matrix rank, and matrix inversion.

5.8. Requirements for a Compliant Decoder

If a RaptorQ-compliant decoder receives a mathematically sufficient set of encoding symbols generated according to the encoder specification in Section 5.3 for reconstruction of a source block, then such a decoder SHOULD recover the entire source block. A RaptorQ-compliant decoder SHALL have the following recovery properties for source blocks with K' source symbols for all values of K' in Table 2 of Section 5.6.
Top   ToC   RFC6330 - Page 66
   1.  If the decoder receives K' encoding symbols generated according
       to the encoder specification in Section 5.3 with corresponding
       ESIs chosen independently and uniformly at random from the range
       of possible ESIs, then on average the decoder will fail to
       recover the entire source block at most 1 out of 100 times.

   2.  If the decoder receives K'+1 encoding symbols generated according
       to the encoder specification in Section 5.3 with corresponding
       ESIs chosen independently and uniformly at random from the range
       of possible ESIs, then on average the decoder will fail to
       recover the entire source block at most 1 out of 10,000 times.

   3.  If the decoder receives K'+2 encoding symbols generated according
       to the encoder specification in Section 5.3 with corresponding
       ESIs chosen independently and uniformly at random from the range
       of possible ESIs, then on average the decoder will fail to
       recover the entire source block at most 1 out of 1,000,000 times.

   Note that the Example FEC Decoder specified in Section 5.4 fulfills
   both requirements, i.e.,

   1.  it can reconstruct a source block as long as it receives a
       mathematically sufficient set of encoding symbols generated
       according to the encoder specification in Section 5.3, and

   2.  it fulfills the mandatory recovery properties from above.

6. Security Considerations

Data delivery can be subject to denial-of-service attacks by attackers that send corrupted packets that are accepted as legitimate by receivers. This is particularly a concern for multicast delivery because a corrupted packet may be injected into the session close to the root of the multicast tree, in which case the corrupted packet will arrive at many receivers. The use of even one corrupted packet containing encoding data may result in the decoding of an object that is completely corrupted and unusable. It is thus RECOMMENDED that source authentication and integrity checking are applied to decoded objects before delivering objects to an application. For example, a SHA-256 hash [FIPS.180-3.2008] of an object may be appended before transmission, and the SHA-256 hash is computed and checked after the object is decoded but before it is delivered to an application. Source authentication SHOULD be provided, for example, by including a digital signature verifiable by the receiver computed on top of the hash value. It is also RECOMMENDED that a packet authentication protocol such as TESLA [RFC4082] be used to detect and discard corrupted packets upon arrival. This method may also be used to provide source authentication. Furthermore, it is RECOMMENDED that
Top   ToC   RFC6330 - Page 67
   Reverse Path Forwarding checks be enabled in all network routers and
   switches along the path from the sender to receivers to limit the
   possibility of a bad agent successfully injecting a corrupted packet
   into the multicast tree data path.

   Another security concern is that some FEC information may be obtained
   by receivers out-of-band in a session description, and if the session
   description is forged or corrupted, then the receivers will not use
   the correct protocol for decoding content from received packets.  To
   avoid these problems, it is RECOMMENDED that measures be taken to
   prevent receivers from accepting incorrect session descriptions,
   e.g., by using source authentication to ensure that receivers only
   accept legitimate session descriptions from authorized senders.

7. 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]. IANA has assigned the value 6 under the ietf:rmt:fec:encoding registry to "RaptorQ Code" as the Fully-Specified FEC Encoding ID value associated with this specification.

8. Acknowledgements

Thanks are due to Ranganathan (Ranga) Krishnan. Ranga Krishnan has been very supportive in finding and resolving implementation details and in finding the systematic indices. In addition, Habeeb Mohiuddin Mohammed and Antonios Pitarokoilis, both from the Munich University of Technology (TUM), and Alan Shinsato have done two independent implementations of the RaptorQ encoder/decoder that have helped to clarify and to resolve issues with this specification.

9. References

9.1. Normative References

[FIPS.180-3.2008] National Institute of Standards and Technology, "Secure Hash Standard", FIPS PUB 180-3, October 2008. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC4082] Perrig, A., Song, D., Canetti, R., Tygar, J., and B. Briscoe, "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): Multicast Source Authentication Transform Introduction", RFC 4082, June 2005.
Top   ToC   RFC6330 - Page 68
   [RFC5052]  Watson, M., Luby, M., and L. Vicisano, "Forward Error
              Correction (FEC) Building Block", RFC 5052, August 2007.

9.2. Informative References

[LTCodes] Luby, M., "LT codes", Annual IEEE Symposium on Foundations of Computer Science, pp. 271-280, November 2002. [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. [RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, "Raptor Forward Error Correction Scheme for Object Delivery", RFC 5053, October 2007. [RaptorCodes] Shokrollahi, A. and M. Luby, "Raptor Codes", Foundations and Trends in Communications and Information Theory: Vol. 6: No. 3-4, pp. 213-322, 2011.
Top   ToC   RFC6330 - Page 69

Authors' Addresses

Michael Luby Qualcomm Incorporated 3165 Kifer Road Santa Clara, CA 95051 U.S.A. EMail: luby@qualcomm.com Amin Shokrollahi EPFL Laboratoire d'algorithmique Station 14 Batiment BC Lausanne 1015 Switzerland EMail: amin.shokrollahi@epfl.ch Mark Watson Netflix Inc. 100 Winchester Circle Los Gatos, CA 95032 U.S.A. EMail: watsonm@netflix.com Thomas Stockhammer Nomor Research Brecherspitzstrasse 8 Munich 81541 Germany EMail: stockhammer@nomor.de Lorenz Minder Qualcomm Incorporated 3165 Kifer Road Santa Clara, CA 95051 U.S.A. EMail: lminder@qualcomm.com