tech-invite

# RaptorQ Forward Error Correction Scheme for Object Delivery

Part 4 of 4, p. 62 to 69

```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.
```
```   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:
```
```   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,
```
```   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.
```
```   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
```
```   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.
```
```   [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.
```
```Authors' Addresses

Michael Luby
Qualcomm Incorporated
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