tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search     info

RFC 6330

 
 
 

RaptorQ Forward Error Correction Scheme for Object Delivery

Part 4 of 4, p. 62 to 69
Prev RFC Part

 


prevText      Top      Up      ToC       Page 62 
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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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      Up      ToC       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