RaptorQ Forward Error Correction Scheme for Object Delivery
RFC 6330
| Document | Type | RFC - Proposed Standard (August 2011) Errata IPR | |
|---|---|---|---|
| Authors | Lorenz Minder , Amin Shokrollahi , Mark Watson , Michael Luby , Thomas Stockhammer | ||
| Last updated | 2020-06-03 | ||
| RFC stream | Internet Engineering Task Force (IETF) | ||
| Formats | |||
| Additional resources | Mailing list discussion | ||
| IESG | Responsible AD | David Harrington | |
| Send notices to | (None) |
RFC 6330
Luby, et al. Standards Track [Page 54] RFC 6330 RaptorQ FEC Scheme August 2011 +-------+-------+-------+-------+-------+ | 10351 | 15 | 251 | 11 | 10453 | +-------+-------+-------+-------+-------+ | 10458 | 976 | 251 | 11 | 10559 | +-------+-------+-------+-------+-------+ | 10567 | 584 | 251 | 11 | 10667 | +-------+-------+-------+-------+-------+ | 10676 | 267 | 257 | 11 | 10781 | +-------+-------+-------+-------+-------+ | 10787 | 876 | 257 | 11 | 10891 | +-------+-------+-------+-------+-------+ | 10899 | 642 | 257 | 12 | 11003 | +-------+-------+-------+-------+-------+ | 11015 | 794 | 257 | 12 | 11119 | +-------+-------+-------+-------+-------+ | 11130 | 78 | 263 | 12 | 11239 | +-------+-------+-------+-------+-------+ | 11245 | 736 | 263 | 12 | 11353 | +-------+-------+-------+-------+-------+ | 11358 | 882 | 269 | 12 | 11471 | +-------+-------+-------+-------+-------+ | 11475 | 251 | 269 | 12 | 11587 | +-------+-------+-------+-------+-------+ | 11590 | 434 | 269 | 12 | 11701 | +-------+-------+-------+-------+-------+ | 11711 | 204 | 269 | 12 | 11821 | +-------+-------+-------+-------+-------+ | 11829 | 256 | 271 | 12 | 11941 | +-------+-------+-------+-------+-------+ | 11956 | 106 | 277 | 12 | 12073 | +-------+-------+-------+-------+-------+ | 12087 | 375 | 277 | 12 | 12203 | +-------+-------+-------+-------+-------+ | 12208 | 148 | 277 | 12 | 12323 | +-------+-------+-------+-------+-------+ | 12333 | 496 | 281 | 12 | 12451 | +-------+-------+-------+-------+-------+ | 12460 | 88 | 281 | 12 | 12577 | +-------+-------+-------+-------+-------+ | 12593 | 826 | 293 | 12 | 12721 | +-------+-------+-------+-------+-------+ | 12726 | 71 | 293 | 12 | 12853 | +-------+-------+-------+-------+-------+ | 12857 | 925 | 293 | 12 | 12983 | +-------+-------+-------+-------+-------+ | 13002 | 760 | 293 | 12 | 13127 | +-------+-------+-------+-------+-------+ Luby, et al. Standards Track [Page 55] RFC 6330 RaptorQ FEC Scheme August 2011 +-------+-------+-------+-------+-------+ | 13143 | 130 | 293 | 12 | 13267 | +-------+-------+-------+-------+-------+ | 13284 | 641 | 307 | 12 | 13421 | +-------+-------+-------+-------+-------+ | 13417 | 400 | 307 | 12 | 13553 | +-------+-------+-------+-------+-------+ | 13558 | 480 | 307 | 12 | 13693 | +-------+-------+-------+-------+-------+ | 13695 | 76 | 307 | 12 | 13829 | +-------+-------+-------+-------+-------+ | 13833 | 665 | 307 | 12 | 13967 | +-------+-------+-------+-------+-------+ | 13974 | 910 | 307 | 12 | 14107 | +-------+-------+-------+-------+-------+ | 14115 | 467 | 311 | 12 | 14251 | +-------+-------+-------+-------+-------+ | 14272 | 964 | 311 | 12 | 14407 | +-------+-------+-------+-------+-------+ | 14415 | 625 | 313 | 12 | 14551 | +-------+-------+-------+-------+-------+ | 14560 | 362 | 317 | 12 | 14699 | +-------+-------+-------+-------+-------+ | 14713 | 759 | 317 | 12 | 14851 | +-------+-------+-------+-------+-------+ | 14862 | 728 | 331 | 12 | 15013 | +-------+-------+-------+-------+-------+ | 15011 | 343 | 331 | 12 | 15161 | +-------+-------+-------+-------+-------+ | 15170 | 113 | 331 | 12 | 15319 | +-------+-------+-------+-------+-------+ | 15325 | 137 | 331 | 12 | 15473 | +-------+-------+-------+-------+-------+ | 15496 | 308 | 331 | 12 | 15643 | +-------+-------+-------+-------+-------+ | 15651 | 800 | 337 | 12 | 15803 | +-------+-------+-------+-------+-------+ | 15808 | 177 | 337 | 12 | 15959 | +-------+-------+-------+-------+-------+ | 15977 | 961 | 337 | 12 | 16127 | +-------+-------+-------+-------+-------+ | 16161 | 958 | 347 | 12 | 16319 | +-------+-------+-------+-------+-------+ | 16336 | 72 | 347 | 12 | 16493 | +-------+-------+-------+-------+-------+ | 16505 | 732 | 347 | 12 | 16661 | +-------+-------+-------+-------+-------+ Luby, et al. Standards Track [Page 56] RFC 6330 RaptorQ FEC Scheme August 2011 +-------+-------+-------+-------+-------+ | 16674 | 145 | 349 | 12 | 16831 | +-------+-------+-------+-------+-------+ | 16851 | 577 | 353 | 12 | 17011 | +-------+-------+-------+-------+-------+ | 17024 | 305 | 353 | 12 | 17183 | +-------+-------+-------+-------+-------+ | 17195 | 50 | 359 | 12 | 17359 | +-------+-------+-------+-------+-------+ | 17376 | 351 | 359 | 12 | 17539 | +-------+-------+-------+-------+-------+ | 17559 | 175 | 367 | 12 | 17729 | +-------+-------+-------+-------+-------+ | 17742 | 727 | 367 | 12 | 17911 | +-------+-------+-------+-------+-------+ | 17929 | 902 | 367 | 12 | 18097 | +-------+-------+-------+-------+-------+ | 18116 | 409 | 373 | 12 | 18289 | +-------+-------+-------+-------+-------+ | 18309 | 776 | 373 | 12 | 18481 | +-------+-------+-------+-------+-------+ | 18503 | 586 | 379 | 12 | 18679 | +-------+-------+-------+-------+-------+ | 18694 | 451 | 379 | 12 | 18869 | +-------+-------+-------+-------+-------+ | 18909 | 287 | 383 | 12 | 19087 | +-------+-------+-------+-------+-------+ | 19126 | 246 | 389 | 12 | 19309 | +-------+-------+-------+-------+-------+ | 19325 | 222 | 389 | 12 | 19507 | +-------+-------+-------+-------+-------+ | 19539 | 563 | 397 | 12 | 19727 | +-------+-------+-------+-------+-------+ | 19740 | 839 | 397 | 12 | 19927 | +-------+-------+-------+-------+-------+ | 19939 | 897 | 401 | 12 | 20129 | +-------+-------+-------+-------+-------+ | 20152 | 409 | 401 | 12 | 20341 | +-------+-------+-------+-------+-------+ | 20355 | 618 | 409 | 12 | 20551 | +-------+-------+-------+-------+-------+ | 20564 | 439 | 409 | 12 | 20759 | +-------+-------+-------+-------+-------+ | 20778 | 95 | 419 | 13 | 20983 | +-------+-------+-------+-------+-------+ | 20988 | 448 | 419 | 13 | 21191 | +-------+-------+-------+-------+-------+ Luby, et al. Standards Track [Page 57] RFC 6330 RaptorQ FEC Scheme August 2011 +-------+-------+-------+-------+-------+ | 21199 | 133 | 419 | 13 | 21401 | +-------+-------+-------+-------+-------+ | 21412 | 938 | 419 | 13 | 21613 | +-------+-------+-------+-------+-------+ | 21629 | 423 | 431 | 13 | 21841 | +-------+-------+-------+-------+-------+ | 21852 | 90 | 431 | 13 | 22063 | +-------+-------+-------+-------+-------+ | 22073 | 640 | 431 | 13 | 22283 | +-------+-------+-------+-------+-------+ | 22301 | 922 | 433 | 13 | 22511 | +-------+-------+-------+-------+-------+ | 22536 | 250 | 439 | 13 | 22751 | +-------+-------+-------+-------+-------+ | 22779 | 367 | 439 | 13 | 22993 | +-------+-------+-------+-------+-------+ | 23010 | 447 | 443 | 13 | 23227 | +-------+-------+-------+-------+-------+ | 23252 | 559 | 449 | 13 | 23473 | +-------+-------+-------+-------+-------+ | 23491 | 121 | 457 | 13 | 23719 | +-------+-------+-------+-------+-------+ | 23730 | 623 | 457 | 13 | 23957 | +-------+-------+-------+-------+-------+ | 23971 | 450 | 457 | 13 | 24197 | +-------+-------+-------+-------+-------+ | 24215 | 253 | 461 | 13 | 24443 | +-------+-------+-------+-------+-------+ | 24476 | 106 | 467 | 13 | 24709 | +-------+-------+-------+-------+-------+ | 24721 | 863 | 467 | 13 | 24953 | +-------+-------+-------+-------+-------+ | 24976 | 148 | 479 | 13 | 25219 | +-------+-------+-------+-------+-------+ | 25230 | 427 | 479 | 13 | 25471 | +-------+-------+-------+-------+-------+ | 25493 | 138 | 479 | 13 | 25733 | +-------+-------+-------+-------+-------+ | 25756 | 794 | 487 | 13 | 26003 | +-------+-------+-------+-------+-------+ | 26022 | 247 | 487 | 13 | 26267 | +-------+-------+-------+-------+-------+ | 26291 | 562 | 491 | 13 | 26539 | +-------+-------+-------+-------+-------+ | 26566 | 53 | 499 | 13 | 26821 | +-------+-------+-------+-------+-------+ Luby, et al. Standards Track [Page 58] RFC 6330 RaptorQ FEC Scheme August 2011 +-------+-------+-------+-------+-------+ | 26838 | 135 | 499 | 13 | 27091 | +-------+-------+-------+-------+-------+ | 27111 | 21 | 503 | 13 | 27367 | +-------+-------+-------+-------+-------+ | 27392 | 201 | 509 | 13 | 27653 | +-------+-------+-------+-------+-------+ | 27682 | 169 | 521 | 13 | 27953 | +-------+-------+-------+-------+-------+ | 27959 | 70 | 521 | 13 | 28229 | +-------+-------+-------+-------+-------+ | 28248 | 386 | 521 | 13 | 28517 | +-------+-------+-------+-------+-------+ | 28548 | 226 | 523 | 13 | 28817 | +-------+-------+-------+-------+-------+ | 28845 | 3 | 541 | 13 | 29131 | +-------+-------+-------+-------+-------+ | 29138 | 769 | 541 | 13 | 29423 | +-------+-------+-------+-------+-------+ | 29434 | 590 | 541 | 13 | 29717 | +-------+-------+-------+-------+-------+ | 29731 | 672 | 541 | 13 | 30013 | +-------+-------+-------+-------+-------+ | 30037 | 713 | 547 | 13 | 30323 | +-------+-------+-------+-------+-------+ | 30346 | 967 | 547 | 13 | 30631 | +-------+-------+-------+-------+-------+ | 30654 | 368 | 557 | 14 | 30949 | +-------+-------+-------+-------+-------+ | 30974 | 348 | 557 | 14 | 31267 | +-------+-------+-------+-------+-------+ | 31285 | 119 | 563 | 14 | 31583 | +-------+-------+-------+-------+-------+ | 31605 | 503 | 569 | 14 | 31907 | +-------+-------+-------+-------+-------+ | 31948 | 181 | 571 | 14 | 32251 | +-------+-------+-------+-------+-------+ | 32272 | 394 | 577 | 14 | 32579 | +-------+-------+-------+-------+-------+ | 32601 | 189 | 587 | 14 | 32917 | +-------+-------+-------+-------+-------+ | 32932 | 210 | 587 | 14 | 33247 | +-------+-------+-------+-------+-------+ | 33282 | 62 | 593 | 14 | 33601 | +-------+-------+-------+-------+-------+ | 33623 | 273 | 593 | 14 | 33941 | +-------+-------+-------+-------+-------+ Luby, et al. Standards Track [Page 59] RFC 6330 RaptorQ FEC Scheme August 2011 +-------+-------+-------+-------+-------+ | 33961 | 554 | 599 | 14 | 34283 | +-------+-------+-------+-------+-------+ | 34302 | 936 | 607 | 14 | 34631 | +-------+-------+-------+-------+-------+ | 34654 | 483 | 607 | 14 | 34981 | +-------+-------+-------+-------+-------+ | 35031 | 397 | 613 | 14 | 35363 | +-------+-------+-------+-------+-------+ | 35395 | 241 | 619 | 14 | 35731 | +-------+-------+-------+-------+-------+ | 35750 | 500 | 631 | 14 | 36097 | +-------+-------+-------+-------+-------+ | 36112 | 12 | 631 | 14 | 36457 | +-------+-------+-------+-------+-------+ | 36479 | 958 | 641 | 14 | 36833 | +-------+-------+-------+-------+-------+ | 36849 | 524 | 641 | 14 | 37201 | +-------+-------+-------+-------+-------+ | 37227 | 8 | 643 | 14 | 37579 | +-------+-------+-------+-------+-------+ | 37606 | 100 | 653 | 14 | 37967 | +-------+-------+-------+-------+-------+ | 37992 | 339 | 653 | 14 | 38351 | +-------+-------+-------+-------+-------+ | 38385 | 804 | 659 | 14 | 38749 | +-------+-------+-------+-------+-------+ | 38787 | 510 | 673 | 14 | 39163 | +-------+-------+-------+-------+-------+ | 39176 | 18 | 673 | 14 | 39551 | +-------+-------+-------+-------+-------+ | 39576 | 412 | 677 | 14 | 39953 | +-------+-------+-------+-------+-------+ | 39980 | 394 | 683 | 14 | 40361 | +-------+-------+-------+-------+-------+ | 40398 | 830 | 691 | 15 | 40787 | +-------+-------+-------+-------+-------+ | 40816 | 535 | 701 | 15 | 41213 | +-------+-------+-------+-------+-------+ | 41226 | 199 | 701 | 15 | 41621 | +-------+-------+-------+-------+-------+ | 41641 | 27 | 709 | 15 | 42043 | +-------+-------+-------+-------+-------+ | 42067 | 298 | 709 | 15 | 42467 | +-------+-------+-------+-------+-------+ | 42490 | 368 | 719 | 15 | 42899 | +-------+-------+-------+-------+-------+ Luby, et al. Standards Track [Page 60] RFC 6330 RaptorQ FEC Scheme August 2011 +-------+-------+-------+-------+-------+ | 42916 | 755 | 727 | 15 | 43331 | +-------+-------+-------+-------+-------+ | 43388 | 379 | 727 | 15 | 43801 | +-------+-------+-------+-------+-------+ | 43840 | 73 | 733 | 15 | 44257 | +-------+-------+-------+-------+-------+ | 44279 | 387 | 739 | 15 | 44701 | +-------+-------+-------+-------+-------+ | 44729 | 457 | 751 | 15 | 45161 | +-------+-------+-------+-------+-------+ | 45183 | 761 | 751 | 15 | 45613 | +-------+-------+-------+-------+-------+ | 45638 | 855 | 757 | 15 | 46073 | +-------+-------+-------+-------+-------+ | 46104 | 370 | 769 | 15 | 46549 | +-------+-------+-------+-------+-------+ | 46574 | 261 | 769 | 15 | 47017 | +-------+-------+-------+-------+-------+ | 47047 | 299 | 787 | 15 | 47507 | +-------+-------+-------+-------+-------+ | 47523 | 920 | 787 | 15 | 47981 | +-------+-------+-------+-------+-------+ | 48007 | 269 | 787 | 15 | 48463 | +-------+-------+-------+-------+-------+ | 48489 | 862 | 797 | 15 | 48953 | +-------+-------+-------+-------+-------+ | 48976 | 349 | 809 | 15 | 49451 | +-------+-------+-------+-------+-------+ | 49470 | 103 | 809 | 15 | 49943 | +-------+-------+-------+-------+-------+ | 49978 | 115 | 821 | 15 | 50461 | +-------+-------+-------+-------+-------+ | 50511 | 93 | 821 | 16 | 50993 | +-------+-------+-------+-------+-------+ | 51017 | 982 | 827 | 16 | 51503 | +-------+-------+-------+-------+-------+ | 51530 | 432 | 839 | 16 | 52027 | +-------+-------+-------+-------+-------+ | 52062 | 340 | 853 | 16 | 52571 | +-------+-------+-------+-------+-------+ | 52586 | 173 | 853 | 16 | 53093 | +-------+-------+-------+-------+-------+ | 53114 | 421 | 857 | 16 | 53623 | +-------+-------+-------+-------+-------+ | 53650 | 330 | 863 | 16 | 54163 | +-------+-------+-------+-------+-------+ Luby, et al. Standards Track [Page 61] RFC 6330 RaptorQ FEC Scheme August 2011 +-------+-------+-------+-------+-------+ | 54188 | 624 | 877 | 16 | 54713 | +-------+-------+-------+-------+-------+ | 54735 | 233 | 877 | 16 | 55259 | +-------+-------+-------+-------+-------+ | 55289 | 362 | 883 | 16 | 55817 | +-------+-------+-------+-------+-------+ | 55843 | 963 | 907 | 16 | 56393 | +-------+-------+-------+-------+-------+ | 56403 | 471 | 907 | 16 | 56951 | +-------+-------+-------+-------+-------+ Table 2: Systematic Indices and Other Parameters 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. Luby, et al. Standards Track [Page 62] RFC 6330 RaptorQ FEC Scheme August 2011 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: Luby, et al. Standards Track [Page 63] RFC 6330 RaptorQ FEC Scheme August 2011 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, Luby, et al. Standards Track [Page 64] RFC 6330 RaptorQ FEC Scheme August 2011 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. Luby, et al. Standards Track [Page 65] RFC 6330 RaptorQ FEC Scheme August 2011 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 Luby, et al. Standards Track [Page 66] RFC 6330 RaptorQ FEC Scheme August 2011 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. Luby, et al. Standards Track [Page 67] RFC 6330 RaptorQ FEC Scheme August 2011 [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. Luby, et al. Standards Track [Page 68] RFC 6330 RaptorQ FEC Scheme August 2011 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 Luby, et al. Standards Track [Page 69]