draft-ietf-rmt-bb-fec-rs-02.txt | draft-ietf-rmt-bb-fec-rs-03.txt | |||
---|---|---|---|---|

Reliable Multicast Transport J. Lacan | Reliable Multicast Transport J. Lacan | |||

Internet-Draft ENSICA/LAAS-CNRS | Internet-Draft ENSICA/LAAS-CNRS | |||

Intended status: Experimental V. Roca | Intended status: Experimental V. Roca | |||

Expires: June 25, 2007 INRIA | Expires: November 8, 2007 INRIA | |||

J. Peltotalo | J. Peltotalo | |||

S. Peltotalo | S. Peltotalo | |||

Tampere University of Technology | Tampere University of Technology | |||

December 22, 2006 | May 7, 2007 | |||

Reed-Solomon Forward Error Correction (FEC) | Reed-Solomon Forward Error Correction (FEC) Schemes | |||

draft-ietf-rmt-bb-fec-rs-02.txt | draft-ietf-rmt-bb-fec-rs-03.txt | |||

Status of this Memo | Status of this Memo | |||

By submitting this Internet-Draft, each author represents that any | By submitting this Internet-Draft, each author represents that any | |||

applicable patent or other IPR claims of which he or she is aware | applicable patent or other IPR claims of which he or she is aware | |||

have been or will be disclosed, and any of which he or she becomes | have been or will be disclosed, and any of which he or she becomes | |||

aware will be disclosed, in accordance with Section 6 of BCP 79. | aware will be disclosed, in accordance with Section 6 of BCP 79. | |||

Internet-Drafts are working documents of the Internet Engineering | Internet-Drafts are working documents of the Internet Engineering | |||

Task Force (IETF), its areas, and its working groups. Note that | Task Force (IETF), its areas, and its working groups. Note that | |||

skipping to change at page 1, line 38 | skipping to change at page 1, line 38 | |||

and may be updated, replaced, or obsoleted by other documents at any | and may be updated, replaced, or obsoleted by other documents at any | |||

time. It is inappropriate to use Internet-Drafts as reference | time. It is inappropriate to use Internet-Drafts as reference | |||

material or to cite them other than as "work in progress." | material or to cite them other than as "work in progress." | |||

The list of current Internet-Drafts can be accessed at | The list of current Internet-Drafts can be accessed at | |||

http://www.ietf.org/ietf/1id-abstracts.txt. | http://www.ietf.org/ietf/1id-abstracts.txt. | |||

The list of Internet-Draft Shadow Directories can be accessed at | The list of Internet-Draft Shadow Directories can be accessed at | |||

http://www.ietf.org/shadow.html. | http://www.ietf.org/shadow.html. | |||

This Internet-Draft will expire on June 25, 2007. | This Internet-Draft will expire on November 8, 2007. | |||

Copyright Notice | Copyright Notice | |||

Copyright (C) The IETF Trust (2006). | Copyright (C) The IETF Trust (2007). | |||

Abstract | Abstract | |||

This document describes a Fully-Specified FEC scheme for the Reed- | This document describes a Fully-Specified FEC Scheme for the Reed- | |||

Solomon forward error correction code and its application to the | Solomon forward error correction codes over GF(2^^m), with m in | |||

reliable delivery of data objects on the packet erasure channel. | {2..16}, and its application to the reliable delivery of data objects | |||

on the packet erasure channel. | ||||

This document also describes a Fully-Specified FEC Scheme for the | ||||

special case of Reed-Solomon codes over GF(2^^8) when there is no | ||||

encoding symbol group. | ||||

Finally, in the context of the Under-Specified Small Block Systematic | ||||

FEC Scheme (FEC Encoding ID 129), this document assigns an FEC | ||||

Instance ID to the special case of Reed-Solomon codes over GF(2^^8). | ||||

Reed-Solomon codes belong to the class of Maximum Distance Separable | Reed-Solomon codes belong to the class of Maximum Distance Separable | |||

(MDS) codes, i.e. they enable a receiver to recover the k source | (MDS) codes, i.e. they enable a receiver to recover the k source | |||

symbols from any set of k received symbols. | symbols from any set of k received symbols. The schemes described | |||

here are compatible with the implementation from Luigi Rizzo. | ||||

The implementation described here is compatible with the | ||||

implementation from Luigi Rizzo. | ||||

Table of Contents | Table of Contents | |||

1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 | 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 | |||

2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 | 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 | |||

3. Definitions Notations and Abbreviations . . . . . . . . . . . 6 | 3. Definitions Notations and Abbreviations . . . . . . . . . . . 6 | |||

3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 6 | 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 6 | |||

3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 6 | 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 6 | |||

3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 7 | 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 7 | |||

4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 8 | 4. Formats and Codes with FEC Encoding ID 2 . . . . . . . . . . . 8 | |||

4.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 8 | 4.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 8 | |||

4.2. FEC Object Transmission Information . . . . . . . . . . . 9 | 4.2. FEC Object Transmission Information . . . . . . . . . . . 9 | |||

4.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 9 | 4.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 9 | |||

4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 9 | 4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 9 | |||

4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 9 | 4.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 9 | |||

4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 10 | 4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 10 | |||

5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 12 | 5. Formats and Codes with FEC Encoding ID 5 . . . . . . . . . . . 12 | |||

5.1. Determining the Maximum Source Block Length (B) . . . . . 12 | 5.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 12 | |||

5.2. Determining the Number of Encoding Symbols of a Block . . 12 | 5.2. FEC Object Transmission Information . . . . . . . . . . . 12 | |||

6. Reed-Solomon Codes Specification for the Erasure Channel . . . 14 | 5.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 12 | |||

6.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 14 | 5.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 12 | |||

6.2. Reed-Solomon Encoding Algorithm . . . . . . . . . . . . . 15 | 5.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 13 | |||

6.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 15 | 5.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 13 | |||

6.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 16 | 6. Procedures with FEC Encoding IDs 2 and 5 . . . . . . . . . . . 14 | |||

6.3. Reed-Solomon Decoding Algorithm . . . . . . . . . . . . . 16 | 6.1. Determining the Maximum Source Block Length (B) . . . . . 14 | |||

6.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 16 | 6.2. Determining the Number of Encoding Symbols of a Block . . 14 | |||

6.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 17 | 7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) | |||

6.4. Implementation for the Packet Erasure Channel . . . . . . 17 | and Reed-Solomon Codes over GF(2^^8) . . . . . . . . . . . . . 16 | |||

7. Security Considerations . . . . . . . . . . . . . . . . . . . 19 | 8. Reed-Solomon Codes Specification for the Erasure Channel . . . 17 | |||

8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 | 8.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 17 | |||

9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21 | 8.2. Reed-Solomon Encoding Algorithm . . . . . . . . . . . . . 18 | |||

10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22 | 8.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 18 | |||

10.1. Normative References . . . . . . . . . . . . . . . . . . . 22 | 8.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 19 | |||

10.2. Informative References . . . . . . . . . . . . . . . . . . 22 | 8.3. Reed-Solomon Decoding Algorithm . . . . . . . . . . . . . 19 | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24 | 8.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 19 | |||

Intellectual Property and Copyright Statements . . . . . . . . . . 25 | 8.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 20 | |||

8.4. Implementation for the Packet Erasure Channel . . . . . . 20 | ||||

9. Security Considerations . . . . . . . . . . . . . . . . . . . 23 | ||||

10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 24 | ||||

11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 25 | ||||

12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26 | ||||

12.1. Normative References . . . . . . . . . . . . . . . . . . . 26 | ||||

12.2. Informative References . . . . . . . . . . . . . . . . . . 26 | ||||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 28 | ||||

Intellectual Property and Copyright Statements . . . . . . . . . . 29 | ||||

1. Introduction | 1. Introduction | |||

The use of Forward Error Correction (FEC) codes is a classical | The use of Forward Error Correction (FEC) codes is a classical | |||

solution to improve the reliability of multicast and broadcast | solution to improve the reliability of multicast and broadcast | |||

transmissions. The [2] document describes a general framework to use | transmissions. The [2] document describes a general framework to use | |||

FEC in Content Delivery Protocols (CDP). The companion document [3] | FEC in Content Delivery Protocols (CDP). The companion document [4] | |||

describes some applications of FEC codes for content delivery. | describes some applications of FEC codes for content delivery. | |||

Recent FEC schemes like [6] and [7] proposed erasure codes based on | Recent FEC schemes like [9] and [10] proposed erasure codes based on | |||

sparse graphs/matrices. These codes are efficient in terms of | sparse graphs/matrices. These codes are efficient in terms of | |||

processing but not optimal in terms of correction capabilities when | processing but not optimal in terms of correction capabilities when | |||

dealing with "small" objects. | dealing with "small" objects. | |||

The FEC scheme described in this document belongs to the class of | The FEC scheme described in this document belongs to the class of | |||

Maximum Distance Separable codes that are optimal in terms of erasure | Maximum Distance Separable codes that are optimal in terms of erasure | |||

correction capability. In others words, it enables a receiver to | correction capability. In others words, it enables a receiver to | |||

recover the k source symbols from any set of exactly k encoding | recover the k source symbols from any set of exactly k encoding | |||

symbols. Even if the encoding/decoding complexity is larger than | symbols. Even if the encoding/decoding complexity is larger than | |||

that of [6] or [7], this family of codes is very useful. | that of [9] or [10], this family of codes is very useful. | |||

Many applications dealing with content transmission or content | Many applications dealing with content transmission or content | |||

storage already rely on packet-based Reed-Solomon codes. In | storage already rely on packet-based Reed-Solomon codes. In | |||

particular, many of them use the Reed-Solomon codec of Luigi Rizzo | particular, many of them use the Reed-Solomon codec of Luigi Rizzo | |||

[4]. The goal of the present document to specify an implementation | [7]. The goal of the present document to specify an implementation | |||

of Reed-Solomon codes that is compatible with this codec. | of Reed-Solomon codes that is compatible with this codec. | |||

The present document: | ||||

o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 2 | ||||

that specifies the use of Reed-Solomon codes over GF(2^^m), with m | ||||

in {2..16}, | ||||

o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 5 | ||||

that focuses on the special case of Reed-Solomon codes over | ||||

GF(2^^8) and no encoding symbol group (i.e. exactly one symbol per | ||||

packet), and | ||||

o in the context of the Under-Specified Small Block Systematic FEC | ||||

Scheme (FEC Encoding ID 129) [3], assigns the FEC Instance ID 0 to | ||||

the special case of Reed-Solomon codes over GF(2^^8) and no | ||||

encoding symbol group. | ||||

2. Terminology | 2. Terminology | |||

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", | |||

"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this | "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this | |||

document are to be interpreted as described in RFC 2119 [1]. | document are to be interpreted as described in RFC 2119 [1]. | |||

3. Definitions Notations and Abbreviations | 3. Definitions Notations and Abbreviations | |||

3.1. Definitions | 3.1. Definitions | |||

skipping to change at page 7, line 14 | skipping to change at page 7, line 14 | |||

N denotes the number of source blocks into which the object shall | N denotes the number of source blocks into which the object shall | |||

be partitioned. | be partitioned. | |||

E denotes the encoding symbol length in bytes. | E denotes the encoding symbol length in bytes. | |||

S denotes the symbol size in units of m-bit elements. When m = 8, | S denotes the symbol size in units of m-bit elements. When m = 8, | |||

then S and E are equal. | then S and E are equal. | |||

m defines the length of the elements in the finite field, in bits. | m defines the length of the elements in the finite field, in bits. | |||

In this document, m belongs to {2..16}. | ||||

q defines the number of elements in the finite field. We have: q | q defines the number of elements in the finite field. We have: q | |||

= 2^^m in this specification. | = 2^^m in this specification. | |||

G denotes the number of encoding symbols per group, i.e. the | G denotes the number of encoding symbols per group, i.e. the | |||

number of symbols sent in the same packet. | number of symbols sent in the same packet. | |||

GM denotes the Generator Matrix of a Reed-Solomon code. | GM denotes the Generator Matrix of a Reed-Solomon code. | |||

rate denotes the "code rate", i.e. the k/n ratio. | rate denotes the "code rate", i.e. the k/n ratio. | |||

skipping to change at page 8, line 5 | skipping to change at page 8, line 5 | |||

FEC OTI stands for FEC Object Transmission Information. | FEC OTI stands for FEC Object Transmission Information. | |||

RS stands for Reed-Solomon. | RS stands for Reed-Solomon. | |||

MDS stands for Maximum Distance Separable code. | MDS stands for Maximum Distance Separable code. | |||

GF(q) denotes a finite field (A.K.A. Galois Field) with q | GF(q) denotes a finite field (A.K.A. Galois Field) with q | |||

elements. We assume that q = 2^^m in this document. | elements. We assume that q = 2^^m in this document. | |||

4. Formats and Codes | 4. Formats and Codes with FEC Encoding ID 2 | |||

This section introduces the formats and codes associated to the | ||||

Fully-Specified FEC Scheme with FEC Encoding ID 2 that specifies the | ||||

use of Reed-Solomon codes over GF(2^^m). | ||||

4.1. FEC Payload ID | 4.1. FEC Payload ID | |||

The FEC Payload ID is composed of the Source Block Number and the | The FEC Payload ID is composed of the Source Block Number and the | |||

Encoding Symbol ID. The length of these two fields depends on the | Encoding Symbol ID. The length of these two fields depends on the | |||

parameter m (which is transmitted in the FEC OTI) as follows : | parameter m (which is transmitted in the FEC OTI) as follows : | |||

o The Source Block Number (field of size 32-m bits) identifies from | o The Source Block Number (field of size 32-m bits) identifies from | |||

which source block of the object the encoding symbol(s) in the | which source block of the object the encoding symbol(s) in the | |||

payload is (are) generated. There are a maximum of 2^^(32-m) | payload is (are) generated. There are a maximum of 2^^(32-m) | |||

skipping to change at page 8, line 47 | skipping to change at page 9, line 4 | |||

| Source Block Number (32-8=24 bits) | Enc. Symb. ID | | | Source Block Number (32-8=24 bits) | Enc. Symb. ID | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

Figure 1: FEC Payload ID encoding format for m = 8 (default) | Figure 1: FEC Payload ID encoding format for m = 8 (default) | |||

0 1 2 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 | 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 | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| Src Block Nb (32-16=16 bits) | Enc. Symbol ID (m=16 bits) | | | Src Block Nb (32-16=16 bits) | Enc. Symbol ID (m=16 bits) | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

Figure 2: FEC Payload ID encoding format for m = 16 | Figure 2: FEC Payload ID encoding format for m = 16 | |||

4.2. FEC Object Transmission Information | 4.2. FEC Object Transmission Information | |||

4.2.1. Mandatory Elements | 4.2.1. Mandatory Elements | |||

o FEC Encoding ID: the Fully-Specified FEC Scheme described in this | o FEC Encoding ID: the Fully-Specified FEC Scheme described in this | |||

document uses FEC Encoding ID 2. | section uses FEC Encoding ID 2. | |||

4.2.2. Common Elements | 4.2.2. Common Elements | |||

The following elements MUST be defined with the present FEC scheme: | The following elements MUST be defined with the present FEC scheme: | |||

o Transfer-Length (L): a non-negative integer indicating the length | o Transfer-Length (L): a non-negative integer indicating the length | |||

of the object in bytes. There are some restrictions on the | of the object in bytes. There are some restrictions on the | |||

maximum Transfer-Length that can be supported : | maximum Transfer-Length that can be supported : | |||

max_transfer_length = 2^^(32-m) * B * E | max_transfer_length = 2^^(32-m) * B * E | |||

skipping to change at page 9, line 43 | skipping to change at page 9, line 44 | |||

o Encoding-Symbol-Length (E): a non-negative integer indicating the | o Encoding-Symbol-Length (E): a non-negative integer indicating the | |||

length of each encoding symbol in bytes. | length of each encoding symbol in bytes. | |||

o Maximum-Source-Block-Length (B): a non-negative integer indicating | o Maximum-Source-Block-Length (B): a non-negative integer indicating | |||

the maximum number of source symbols in a source block. | the maximum number of source symbols in a source block. | |||

o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer | o Max-Number-of-Encoding-Symbols (max_n): a non-negative integer | |||

indicating the maximum number of encoding symbols generated for | indicating the maximum number of encoding symbols generated for | |||

any source block. | any source block. | |||

Section 5 explains how to derive the values of each of these | Section 6 explains how to derive the values of each of these | |||

elements. | elements. | |||

4.2.3. Scheme-Specific Elements | 4.2.3. Scheme-Specific Elements | |||

The following element MUST be defined with the present FEC Scheme. | The following element MUST be defined with the present FEC Scheme. | |||

It contains two distinct pieces of information: | It contains two distinct pieces of information: | |||

o G: a non-negative integer indicating the number of encoding | o G: a non-negative integer indicating the number of encoding | |||

symbols per group used for the object. The default value is 1, | symbols per group used for the object. The default value is 1, | |||

meaning that each packet contains exactly one symbol. When no G | meaning that each packet contains exactly one symbol. When no G | |||

skipping to change at page 10, line 20 | skipping to change at page 10, line 20 | |||

o Finite Field parameter, m: The m parameter is the length of the | o Finite Field parameter, m: The m parameter is the length of the | |||

finite field elements, in bits. It also characterizes the number | finite field elements, in bits. It also characterizes the number | |||

of elements in the finite field: q = 2^^m elements. The default | of elements in the finite field: q = 2^^m elements. The default | |||

value is m = 8. When no finite field size parameter is | value is m = 8. When no finite field size parameter is | |||

communicated to the decoder, then this latter MUST assume that m = | communicated to the decoder, then this latter MUST assume that m = | |||

8. | 8. | |||

4.2.4. Encoding Format | 4.2.4. Encoding Format | |||

This section shows two possible encoding formats of the above FEC | This section shows the two possible encoding formats of the above FEC | |||

OTI. The present document does not specify when one encoding format | OTI. The present document does not specify when one encoding format | |||

or the other should be used. | or the other should be used. | |||

4.2.4.1. Using the General EXT_FTI Format | 4.2.4.1. Using the General EXT_FTI Format | |||

The FEC OTI binary format is the following, when the EXT_FTI | The FEC OTI binary format is the following, when the EXT_FTI | |||

mechanism is used (e.g. within the ALC [8] or NORM [9] protocols). | mechanism is used (e.g. within the ALC [11] or NORM [12] protocols). | |||

0 1 2 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 | 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 | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| HET = 64 | HEL | | | | HET = 64 | HEL = 4 | | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | |||

| Transfer-Length (L) | | | Transfer-Length (L) | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| m | G | Encoding Symbol Length (E) | | | m | G | Encoding Symbol Length (E) | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| Max Source Block Length (B) | Max Nb Enc. Symbols (max_n) | | | Max Source Block Length (B) | Max Nb Enc. Symbols (max_n) | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

Figure 3: EXT_FTI Header Format | Figure 3: EXT_FTI Header Format | |||

4.2.4.2. Using the FDT Instance (FLUTE specific) | 4.2.4.2. Using the FDT Instance (FLUTE specific) | |||

When it is desired that the FEC OTI be carried in the FDT Instance of | When it is desired that the FEC OTI be carried in the FDT Instance of | |||

a FLUTE session [10], the following XML attributes must be described | a FLUTE session [13], the following XML attributes must be described | |||

for the associated object: | for the associated object: | |||

o FEC-OTI-FEC-Encoding-ID | o FEC-OTI-FEC-Encoding-ID | |||

o FEC-OTI-Transfer-Length (L) | o FEC-OTI-Transfer-Length (L) | |||

o FEC-OTI-Encoding-Symbol-Length (E) | o FEC-OTI-Encoding-Symbol-Length (E) | |||

o FEC-OTI-Maximum-Source-Block-Length (B) | o FEC-OTI-Maximum-Source-Block-Length (B) | |||

o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) | o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) | |||

skipping to change at page 11, line 22 | skipping to change at page 11, line 22 | |||

The FEC-OTI-Scheme-Specific-Info contains the string resulting from | The FEC-OTI-Scheme-Specific-Info contains the string resulting from | |||

the Base64 encoding (in the XML Schema xs:base64Binary sense) of the | the Base64 encoding (in the XML Schema xs:base64Binary sense) of the | |||

following value: | following value: | |||

0 1 | 0 1 | |||

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 | 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

| m | G | | | m | G | | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

Figure 4: FEC OTI Scheme Specific Information to be Included in the | Figure 4: FEC OTI Scheme Specific Information to be included in the | |||

FDT Instance | FDT Instance | |||

When no m parameter is to be carried in the FEC OTI, the m field is | When no m parameter is to be carried in the FEC OTI, the m field is | |||

set to 0 (which is not a valid seed value). Otherwise the m field | set to 0 (which is not a valid seed value). Otherwise the m field | |||

contains a valid value as explained in Section 4.2.3. Similarly, | contains a valid value as explained in Section 4.2.3. Similarly, | |||

when no G parameter is to be carried in the FEC OTI, the G field is | when no G parameter is to be carried in the FEC OTI, the G field is | |||

set to 0 (which is not a valid seed value). Otherwise the G field | set to 0 (which is not a valid seed value). Otherwise the G field | |||

contains a valid value as explained in Section 4.2.3. When neither m | contains a valid value as explained in Section 4.2.3. When neither m | |||

nor G are to be carried in the FEC OTI, then the sender simply omits | nor G are to be carried in the FEC OTI, then the sender simply omits | |||

the FEC-OTI-Scheme-Specific-Info attribute. | the FEC-OTI-Scheme-Specific-Info attribute. | |||

After Base64 encoding, the 2 bytes of the FEC OTI Scheme Specific | After Base64 encoding, the 2 bytes of the FEC OTI Scheme Specific | |||

Information are transformed into a string of 4 printable characters | Information are transformed into a string of 4 printable characters | |||

(in the 64-character alphabet) and added to the FEC-OTI-Scheme- | (in the 64-character alphabet) and added to the FEC-OTI-Scheme- | |||

Specific-Info attribute. | Specific-Info attribute. | |||

5. Procedures | 5. Formats and Codes with FEC Encoding ID 5 | |||

5.1. Determining the Maximum Source Block Length (B) | This section introduces the formats and codes associated to the | |||

Fully-Specified FEC Scheme with FEC Encoding ID 5 that focuses on the | ||||

special case of Reed-Solomon codes over GF(2^^8) and no encoding | ||||

symbol group. | ||||

5.1. FEC Payload ID | ||||

The FEC Payload ID is composed of the Source Block Number and the | ||||

Encoding Symbol ID: | ||||

o The Source Block Number (24 bit field) identifies from which | ||||

source block of the object the encoding symbol in the payload is | ||||

generated. There are a maximum of 2^^24 blocks per object. | ||||

o The Encoding Symbol ID (8 bit field) identifies which specific | ||||

encoding symbol generated from the source block is carried in the | ||||

packet payload. There are a maximum of 2^^8 encoding symbols per | ||||

block. The first k values (0 to k - 1) identify source symbols, | ||||

the remaining n-k values identify repair symbols. | ||||

There MUST be exactly one FEC Payload ID per source or repair packet. | ||||

This FEC Payload ID refer to the one and only symbol of the packet. | ||||

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 | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

| Source Block Number (24 bits) | Enc. Symb. ID | | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

Figure 5: FEC Payload ID encoding format with FEC Encoding ID 5 | ||||

5.2. FEC Object Transmission Information | ||||

5.2.1. Mandatory Elements | ||||

o FEC Encoding ID: the Fully-Specified FEC Scheme described in this | ||||

section uses FEC Encoding ID 5. | ||||

5.2.2. Common Elements | ||||

The Common Elements are the same as those specified in Section 4.2.2 | ||||

when m = 8 and G = 1. | ||||

5.2.3. Scheme-Specific Elements | ||||

No Scheme-Specific elements are defined by this FEC Scheme. | ||||

5.2.4. Encoding Format | ||||

This section shows the two possible encoding formats of the above FEC | ||||

OTI. The present document does not specify when one encoding format | ||||

or the other should be used. | ||||

5.2.4.1. Using the General EXT_FTI Format | ||||

The FEC OTI binary format is the following, when the EXT_FTI | ||||

mechanism is used (e.g. within the ALC [11] or NORM [12] protocols). | ||||

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 | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

| HET = 64 | HEL = 3 | | | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | ||||

| Transfer-Length (L) | | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

| Encoding Symbol Length (E) | MaxBlkLen (B) | max_n | | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

Figure 6: EXT_FTI Header Format with FEC Encoding ID 5 | ||||

5.2.4.2. Using the FDT Instance (FLUTE specific) | ||||

When it is desired that the FEC OTI be carried in the FDT Instance of | ||||

a FLUTE session [13], the following XML attributes must be described | ||||

for the associated object: | ||||

o FEC-OTI-FEC-Encoding-ID | ||||

o FEC-OTI-Transfer-Length (L) | ||||

o FEC-OTI-Encoding-Symbol-Length (E) | ||||

o FEC-OTI-Maximum-Source-Block-Length (B) | ||||

o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) | ||||

6. Procedures with FEC Encoding IDs 2 and 5 | ||||

This section defines procedures that are common to FEC Encoding IDs 2 | ||||

and 5. In case of FEC Encoding ID 5, m = 8 and G = 1. Note that the | ||||

block partitioning algorithm is defined in [2]. | ||||

6.1. Determining the Maximum Source Block Length (B) | ||||

The finite field size parameter, m, defines the number of non zero | The finite field size parameter, m, defines the number of non zero | |||

elements in this field which is equal to: q - 1 = 2^^m - 1. Note | elements in this field which is equal to: q - 1 = 2^^m - 1. Note | |||

that q - 1 is also the theoretical maximum number of encoding symbols | that q - 1 is also the theoretical maximum number of encoding symbols | |||

that can be produced for a source block. For instance, when m = 8 | that can be produced for a source block. For instance, when m = 8 | |||

(default): | (default): | |||

max1_B = 2^^8 - 1 = 255 | max1_B = 2^^8 - 1 = 255 | |||

Additionally, a codec MAY impose other limitations on the maximum | Additionally, a codec MAY impose other limitations on the maximum | |||

skipping to change at page 12, line 30 | skipping to change at page 14, line 34 | |||

implementation time, when the target use case is known. This results | implementation time, when the target use case is known. This results | |||

in a max2_B limitation. | in a max2_B limitation. | |||

Then, B is given by: | Then, B is given by: | |||

B = min(max1_B, max2_B) | B = min(max1_B, max2_B) | |||

Note that this calculation is only required at the coder, since the B | Note that this calculation is only required at the coder, since the B | |||

parameter is communicated to the decoder through the FEC OTI. | parameter is communicated to the decoder through the FEC OTI. | |||

5.2. Determining the Number of Encoding Symbols of a Block | 6.2. Determining the Number of Encoding Symbols of a Block | |||

The following algorithm, also called "n-algorithm", explains how to | The following algorithm, also called "n-algorithm", explains how to | |||

determine the actual number of encoding symbols for a given block. | determine the actual number of encoding symbols for a given block. | |||

AT A SENDER: | AT A SENDER: | |||

Input: | Input: | |||

B: Maximum source block length, for any source block. Section 5.1 | B: Maximum source block length, for any source block. Section 6.1 | |||

explains how to determine its value. | explains how to determine its value. | |||

k: Current source block length. This parameter is given by the | k: Current source block length. This parameter is given by the | |||

block partitioning algorithm. | block partitioning algorithm. | |||

rate: FEC code rate, which is given by the user (e.g. when | rate: FEC code rate, which is given by the user (e.g. when | |||

starting a FLUTE sending application). It is expressed as a | starting a FLUTE sending application). It is expressed as a | |||

floating point value. | floating point value. | |||

Output: | Output: | |||

skipping to change at page 14, line 5 | skipping to change at page 16, line 5 | |||

n = floor(k * max_n / B); | n = floor(k * max_n / B); | |||

Note that a Reed-Solomon decoder does not need to know the n value. | Note that a Reed-Solomon decoder does not need to know the n value. | |||

Therefore the receiver part of the "n-algorithm" is not necessary | Therefore the receiver part of the "n-algorithm" is not necessary | |||

from the Reed-Solomon decoder point of view. Yet a receiving | from the Reed-Solomon decoder point of view. Yet a receiving | |||

application using the Reed-Solomon FEC scheme will sometimes need to | application using the Reed-Solomon FEC scheme will sometimes need to | |||

know the n value used by the sender, for instance for memory | know the n value used by the sender, for instance for memory | |||

management optimizations. To that purpose, the FEC OTI carries all | management optimizations. To that purpose, the FEC OTI carries all | |||

the parameters needed for a receiver to execute the above algorithm. | the parameters needed for a receiver to execute the above algorithm. | |||

6. Reed-Solomon Codes Specification for the Erasure Channel | 7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) and Reed- | |||

Solomon Codes over GF(2^^8) | ||||

In the context of the Under-Specified Small Block Systematic FEC | ||||

Scheme (FEC Encoding ID 129) [3], this document assigns the FEC | ||||

Instance ID 0 to the special case of Reed-Solomon codes over GF(2^^8) | ||||

and no encoding symbol group. | ||||

The FEC Instance ID 0 uses the Formats and Codes specified in [3]. | ||||

The FEC Scheme with FEC Instance ID 0 MAY use the algorithm defined | ||||

in Section 9.1. of [3] to partition the file into source blocks. | ||||

This FEC Scheme MAY also use another algorithm. For instance the CDP | ||||

sender may change the length of each source block dynamically, | ||||

depending on some external criteria (e.g. to adjust the FEC coding | ||||

rate to the current loss rate experienced by NORM receivers) and | ||||

inform the CDP receivers of the current block length by means of the | ||||

EXT_FTI mechanism. This choice is out of the scope of the current | ||||

document. | ||||

8. Reed-Solomon Codes Specification for the Erasure Channel | ||||

Reed-Solomon (RS) codes are linear block codes. They also belong to | Reed-Solomon (RS) codes are linear block codes. They also belong to | |||

the class of MDS codes. A [n,k]-RS code encodes a sequence of k | the class of MDS codes. A [n,k]-RS code encodes a sequence of k | |||

source elements defined over a finite field GF(q) into a sequence of | source elements defined over a finite field GF(q) into a sequence of | |||

n encoding elements, where n is upper bounded by q - 1. The | n encoding elements, where n is upper bounded by q - 1. The | |||

implementation described in this document is based on a generator | implementation described in this document is based on a generator | |||

matrix built from a Vandermonde matrix put into systematic form. | matrix built from a Vandermonde matrix put into systematic form. | |||

Section 6.1 to Section 6.3 specify the [n,k]-RS codes when applied to | Section 8.1 to Section 8.3 specify the [n,k]-RS codes when applied to | |||

m-bit elements, and Section 6.4 the use of [n,k]-RS codes when | m-bit elements, and Section 8.4 the use of [n,k]-RS codes when | |||

applied to symbols composed of several m-bit elements, which is the | applied to symbols composed of several m-bit elements, which is the | |||

target of this specification. | target of this specification. | |||

6.1. Finite Field | 8.1. Finite Field | |||

A finite field GF(q) is defined as a finite set of q elements which | A finite field GF(q) is defined as a finite set of q elements which | |||

has a structure of field. It contains necessarily q = p^^m elements, | has a structure of field. It contains necessarily q = p^^m elements, | |||

where p is a prime number. With packet erasure channels, p is always | where p is a prime number. With packet erasure channels, p is always | |||

set to 2. The elements of the field GF(2^^m) can be represented by | set to 2. The elements of the field GF(2^^m) can be represented by | |||

polynomials with binary coefficients (i.e. over GF(2)) of degree | polynomials with binary coefficients (i.e. over GF(2)) of degree | |||

lower or equal than m-1. The polynomials can be associated to binary | lower or equal than m-1. The polynomials can be associated to binary | |||

vectors of length m. For example, the vector (11001) represents the | vectors of length m. For example, the vector (11001) represents the | |||

polynomial 1 + x + x^^4. This representation is often called | polynomial 1 + x + x^^4. This representation is often called | |||

polynomial representation. The addition between two elements is | polynomial representation. The addition between two elements is | |||

skipping to change at page 15, line 27 | skipping to change at page 18, line 27 | |||

m = 15, "1100000000000001", (1+x+x^^15) | m = 15, "1100000000000001", (1+x+x^^15) | |||

m = 16, "11010000000010001", (1+x+x^^3+x^^12+x^^16) | m = 16, "11010000000010001", (1+x+x^^3+x^^12+x^^16) | |||

In order to facilitate the implementation, these polynomials are also | In order to facilitate the implementation, these polynomials are also | |||

primitive. This means that any element of GF(2^^m) can be expressed | primitive. This means that any element of GF(2^^m) can be expressed | |||

as a power of a given root of this polynomial. These polynomials are | as a power of a given root of this polynomial. These polynomials are | |||

also chosen so that they contain the minimum number of monomials. | also chosen so that they contain the minimum number of monomials. | |||

6.2. Reed-Solomon Encoding Algorithm | 8.2. Reed-Solomon Encoding Algorithm | |||

6.2.1. Encoding Principles | 8.2.1. Encoding Principles | |||

Let s = (s_0, ..., s_{k-1}) be a source vector of k elements over | Let s = (s_0, ..., s_{k-1}) be a source vector of k elements over | |||

GF(2^^m). Let e = (e_0, ..., e_{n-1}) be the corresponding encoding | GF(2^^m). Let e = (e_0, ..., e_{n-1}) be the corresponding encoding | |||

vector of n elements over GF(2^^m). Being a linear code, encoding is | vector of n elements over GF(2^^m). Being a linear code, encoding is | |||

performed by multiplying the source vector by a generator matrix, GM, | performed by multiplying the source vector by a generator matrix, GM, | |||

of k rows and n columns over GF(2^^m). Thus: | of k rows and n columns over GF(2^^m). Thus: | |||

e = s * GM. | e = s * GM. | |||

The definition of the generator matrix completely characterizes the | The definition of the generator matrix completely characterizes the | |||

RS code. | RS code. | |||

Let us consider that: n = 2^^m - 1 and: 0 < k <= n. Let us denote by | Let us consider that: n = 2^^m - 1 and: 0 < k <= n. Let us denote by | |||

alpha the root of the primitive polynomial of degree m chosen in the | alpha the root of the primitive polynomial of degree m chosen in the | |||

list of Section 6.1 for the corresponding value of m. Let us | list of Section 8.1 for the corresponding value of m. Let us | |||

consider a Vandermonde matrix of k rows and n columns, denoted by | consider a Vandermonde matrix of k rows and n columns, denoted by | |||

V_{k,n}, and built as follows: the {i, j} entry of V_{k,n} is v_{i,j} | V_{k,n}, and built as follows: the {i, j} entry of V_{k,n} is v_{i,j} | |||

= alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This | = alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This | |||

matrix generates a MDS code. However, this MDS code is not | matrix generates a MDS code. However, this MDS code is not | |||

systematic, which is a problem for many networking applications. To | systematic, which is a problem for many networking applications. To | |||

obtain a systematic matrix (and code), the simplest solution consists | obtain a systematic matrix (and code), the simplest solution consists | |||

in considering the matrix V_{k,k} formed by the first k columns of | in considering the matrix V_{k,k} formed by the first k columns of | |||

V_{k,n}, then to invert it and to multiply this inverse by V_{k,n}. | V_{k,n}, then to invert it and to multiply this inverse by V_{k,n}. | |||

Clearly, the product V_{k,k}^^-1 * V_{k,n} contains the identity | Clearly, the product V_{k,k}^^-1 * V_{k,n} contains the identity | |||

matrix I_k on its first k columns, meaning that the first k encoding | matrix I_k on its first k columns, meaning that the first k encoding | |||

skipping to change at page 16, line 19 | skipping to change at page 19, line 19 | |||

Therefore, the generator matrix of the code considered in this | Therefore, the generator matrix of the code considered in this | |||

document is: | document is: | |||

GM = (V_{k,k}^^-1) * V_{k,n} | GM = (V_{k,k}^^-1) * V_{k,n} | |||

Note that, in practice, the [n,k]-RS code can be shortened to a | Note that, in practice, the [n,k]-RS code can be shortened to a | |||

[n',k]-RS code, where k <= n' < n, by considering the sub-matrix | [n',k]-RS code, where k <= n' < n, by considering the sub-matrix | |||

formed by the n' first columns of GM. | formed by the n' first columns of GM. | |||

6.2.2. Encoding Complexity | 8.2.2. Encoding Complexity | |||

Encoding can be performed by first pre-computing GM and by | Encoding can be performed by first pre-computing GM and by | |||

multiplying the source vector (k elements) by GM (k rows and n | multiplying the source vector (k elements) by GM (k rows and n | |||

columns). The complexity of the pre-computation of the generator | columns). The complexity of the pre-computation of the generator | |||

matrix can be estimated as the complexity of the multiplication of | matrix can be estimated as the complexity of the multiplication of | |||

the inverse of a Vandermonde matrix by n-k vectors (i.e. the last n-k | the inverse of a Vandermonde matrix by n-k vectors (i.e. the last n-k | |||

columns of V_{k,n}). Since the complexity of the inverse of a k*k- | columns of V_{k,n}). Since the complexity of the inverse of a k*k- | |||

Vandermonde matrix by a vector is O(k * log^^2(k)), the generator | Vandermonde matrix by a vector is O(k * log^^2(k)), the generator | |||

matrix can be computed in 0((n-k)* k * log^^2(k)) operations. When | matrix can be computed in 0((n-k)* k * log^^2(k)) operations. When | |||

the genarator matrix is pre-computed, the encoding needs k operations | the generator matrix is pre-computed, the encoding needs k operations | |||

per repair element (vector-matrix multiplication). | per repair element (vector-matrix multiplication). | |||

Encoding can also be performed by first computing the product s * | Encoding can also be performed by first computing the product s * | |||

V_{k,k}^^-1 and then by multiplying the result with V_{k,n}. The | V_{k,k}^^-1 and then by multiplying the result with V_{k,n}. The | |||

multiplication by the inverse of a square Vandermonde matrix is known | multiplication by the inverse of a square Vandermonde matrix is known | |||

as the interpolation problem and its complexity is O(k * log^^2 (k)). | as the interpolation problem and its complexity is O(k * log^^2 (k)). | |||

The multiplication by a Vandermonde matrix, known as the multipoint | The multiplication by a Vandermonde matrix, known as the multipoint | |||

evaluation problem, requires O((n-k) * log(k)) by using Fast Fourier | evaluation problem, requires O((n-k) * log(k)) by using Fast Fourier | |||

Transform, as explained in [11]. The total complexity of this | Transform, as explained in [14]. The total complexity of this | |||

encoding algorithm is then O((k/(n-k)) * log^^2(k) + log(k)) | encoding algorithm is then O((k/(n-k)) * log^^2(k) + log(k)) | |||

operations per repair element. | operations per repair element. | |||

6.3. Reed-Solomon Decoding Algorithm | 8.3. Reed-Solomon Decoding Algorithm | |||

6.3.1. Decoding Principles | 8.3.1. Decoding Principles | |||

The Reed-Solomon decoding algorithm for the erasure channel allows | The Reed-Solomon decoding algorithm for the erasure channel allows | |||

the recovery of the k source elements from any set of k received | the recovery of the k source elements from any set of k received | |||

elements. It is based on the fundamental property of the generator | elements. It is based on the fundamental property of the generator | |||

matrix which is such that any k*k-submatrix is invertible (see [5]). | matrix which is such that any k*k-submatrix is invertible (see [8]). | |||

The first step of the decoding consists in extracting the k*k | The first step of the decoding consists in extracting the k*k | |||

submatrix of the generator matrix obtained by considering the columns | submatrix of the generator matrix obtained by considering the columns | |||

corresponding to the received elements. Indeed, since any encoding | corresponding to the received elements. Indeed, since any encoding | |||

element is obtained by multiplying the source vector by one column of | element is obtained by multiplying the source vector by one column of | |||

the generator matrix, the received vector of k encoding elements can | the generator matrix, the received vector of k encoding elements can | |||

be considered as the result of the multiplication of the source | be considered as the result of the multiplication of the source | |||

vector by a k*k submatrix of the generator matrix. Since this | vector by a k*k submatrix of the generator matrix. Since this | |||

submatrix is invertible, the second step of the algorithm is to | submatrix is invertible, the second step of the algorithm is to | |||

invert this matrix and to multiply the received vector by the | invert this matrix and to multiply the received vector by the | |||

obtained matrix to recover the source vector. | obtained matrix to recover the source vector. | |||

6.3.2. Decoding Complexity | 8.3.2. Decoding Complexity | |||

The decoding algorithm described previously includes the matrix | The decoding algorithm described previously includes the matrix | |||

inversion and the vector-matrix multiplication. With the classical | inversion and the vector-matrix multiplication. With the classical | |||

Gauss-Jordan algorithm, the matrix inversion requires O(k^^3) | Gauss-Jordan algorithm, the matrix inversion requires O(k^^3) | |||

operations and the vector-matrix multiplication is performed in | operations and the vector-matrix multiplication is performed in | |||

O(k^^2) operations. | O(k^^2) operations. | |||

This complexity can be improved by considering that the received | This complexity can be improved by considering that the received | |||

submatrix of GM is the product between the inverse of a Vandermonde | submatrix of GM is the product between the inverse of a Vandermonde | |||

matrix (V_(k,k)^^-1) and another Vandermonde matrix (denoted by V' | matrix (V_(k,k)^^-1) and another Vandermonde matrix (denoted by V' | |||

which is a submatrix of V_(k,n)). The decoding can be done by | which is a submatrix of V_(k,n)). The decoding can be done by | |||

multiplying the received vector by V'^^-1 (interpolation problem with | multiplying the received vector by V'^^-1 (interpolation problem with | |||

complexity O( k * log^^2(k)) ) then by V_{k,k} (multipoint evaluation | complexity O( k * log^^2(k)) ) then by V_{k,k} (multipoint evaluation | |||

with complexity O(k * log(k))). The global decoding complexity is | with complexity O(k * log(k))). The global decoding complexity is | |||

then O(log^^2(k)) operations per source element. | then O(log^^2(k)) operations per source element. | |||

6.4. Implementation for the Packet Erasure Channel | 8.4. Implementation for the Packet Erasure Channel | |||

In a packet erasure channel, each packet (and symbol(s) since packets | In a packet erasure channel, each packet (and symbol(s) since packets | |||

contain G >= 1 symbols) is either correctly received or erased. The | contain G >= 1 symbols) is either correctly received or erased. The | |||

location of the erased symbols in the sequence of symbols must be | location of the erased symbols in the sequence of symbols MUST be | |||

known. The following specification describes the use of Reed-Solomon | known. The following specification describes the use of Reed-Solomon | |||

codes for generating redundant symbols from the k source symbols and | codes for generating redundant symbols from the k source symbols and | |||

to recover the source symbols from any set of k received symbols. | for recovering the source symbols from any set of k received symbols. | |||

The k source symbols of a source block are assumed to be composed of | The k source symbols of a source block are assumed to be composed of | |||

S m-bit elements. Each m-bit element is associated to an element of | S m-bit elements. Each m-bit element corresponds to an element of | |||

the finite field GF(2^^m) through the polynomial representation | the finite field GF(2^^m) through the polynomial representation | |||

(Section 6.1). If some of the source symbols contain less than S | (Section 8.1). If some of the source symbols contain less than S | |||

elements, they are virtually padded with zero elements (it can be the | elements, they MUST be virtually padded with zero elements (it can be | |||

case for the last symbol of the last block of the object). | the case for the last symbol of the last block of the object). | |||

However, this padding need not be actually sent with the data to the | ||||

receivers. | ||||

The encoding process produces n-k repair symbols of size S m-bit | The encoding process produces n encoding symbols of size S m-bit | |||

elements, the k source symbols being also part of the n encoding | elements, of which k are source symbols (this is a systematic code) | |||

symbols (Figure 5). These repair symbols are created m-bit element | and n-k are repair symbols (Figure 7). The m-bit elements of the | |||

per m-bit element. More specifically, the j-th source vector is | repair symbols are calculated using the corresponding m-bit elements | |||

composed of the j-th element of each of the source symbols. | of the source symbol set. A logical j-th source vector, comprised of | |||

Similarly, the j-th encoding vector is composed of the j-th element | the j-th elements from the set of source symbols, is used to | |||

of each encoding symbol. | calculate a j-th encoding vector. This j-th encoding vector then | |||

provides the j-th elements for the set encoding symbols calculated | ||||

for the block. As a systematic code, the first k encoding symbols | ||||

are the same as the k source symbols and the last n-k repair symbols | ||||

are the result of the Reed Solomon encoding. | ||||

n | Input: k source symbols | |||

+-+-+----+-+ +---------------+ +-+-+-----------+-+ | ||||

0 | | | | | | | | | | | | | ||||

| | | | | * | generator | = | | | | | | ||||

| | | | | | matrix | | | | | | | ||||

| | | | | | GM | | | | | | | ||||

source +--------------+ | (k x n) | +---------------------+ | ||||

vector | | | | | | | +---------------+ ->| | | | | | | | ||||

j +--------------+ / +---------------------+ | ||||

| | | | | / | | | | | | ||||

| | | | | encoding | | | | | | ||||

| | | | | vector | | | | | | ||||

| | | | | j | | | | | | ||||

| | | | | | | | | | | ||||

S-1 | | | | | | | | | | | ||||

+-+-+----+-+ +-+-+-----------+-+ | ||||

k source symbols n encoding symbols | ||||

(source + repair) | ||||

Figure 5: Packet encoding scheme | 0 j S-1 | |||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

| |X| | source symbol 0 | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

| |X| | source symbol 1 | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

. . . | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

| |X| | source symbol k-1 | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

* | ||||

+----------------+ | ||||

| generator | | ||||

| matrix | | ||||

| GM | | ||||

| (k x n) | | ||||

+----------------+ | ||||

| | ||||

V | ||||

Output: n encoding symbols (source + repair) | ||||

0 j S-1 | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

| |X| | enc. symbol 0 | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

| |X| | enc. symbol 1 | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

. . . | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

| |Y| | enc. symbol n-1 | ||||

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ||||

Figure 7: Packet encoding scheme | ||||

An asset of this scheme is that the loss of some encoding symbols | An asset of this scheme is that the loss of some encoding symbols | |||

produces the same erasure pattern for each of the S encoding vectors. | produces the same erasure pattern for each of the S encoding vectors. | |||

It follows that the matrix inversion must be done only once and will | It follows that the matrix inversion must be done only once and will | |||

be used by all the S encoding vectors. For large S, this matrix | be used by all the S encoding vectors. For large S, this matrix | |||

inversion cost becomes negligible in front of the S matrix-vector | inversion cost becomes negligible in front of the S matrix-vector | |||

multiplications. | multiplications. | |||

Another asset is that the n-k repair symbols can be produced on | Another asset is that the n-k repair symbols can be produced on | |||

demand. For instance, a sender can start by producing a limited | demand. For instance, a sender can start by producing a limited | |||

number of repair symbols and later on, depending on the observed | number of repair symbols and later on, depending on the observed | |||

erasures on the channel, decide to produce additional repair symbols, | erasures on the channel, decide to produce additional repair symbols, | |||

up to the n-k upper limit. Indeed, to produce the repair symbol e_j, | up to the n-k upper limit. Indeed, to produce the repair symbol e_j, | |||

where k <= j < n, it is sufficient to multiply the S source vectors | where k <= j < n, it is sufficient to multiply the S source vectors | |||

with column j of GM. | with column j of GM. | |||

7. Security Considerations | 9. Security Considerations | |||

The security considerations for this document are the same as that of | Data delivery can be subject to denial-of-service attacks by | |||

[2]. | attackers which 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. This is | ||||

particularly a concern for the FEC building block because 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-1 hash [5] of an object may be | ||||

appended before transmission, and the SHA-1 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 [6] be used to detect and | ||||

discard corrupted packets upon arrival. 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. | ||||

8. IANA Considerations | 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. | ||||

10. IANA Considerations | ||||

Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA | Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA | |||

registration. For general guidelines on IANA considerations as they | registration. For general guidelines on IANA considerations as they | |||

apply to this document, see [2]. This document assigns the Fully- | apply to this document, see [2]. | |||

Specified FEC Encoding ID 2 under the ietf:rmt:fec:encoding name- | ||||

space to "Reed-Solomon Codes". | ||||

9. Acknowledgments | This document assigns the Fully-Specified FEC Encoding ID 2 under the | |||

"ietf:rmt:fec:encoding" name-space to "Reed-Solomon Codes over | ||||

GF(2^^m)". | ||||

The authors want to thank Luigi Rizzo for comments on the subject and | This document assigns the Fully-Specified FEC Encoding ID 5 under the | |||

for the design of the reference Reed-Solomon codec. | "ietf:rmt:fec:encoding" name-space to "Reed-Solomon Codes over | |||

GF(2^^8)". | ||||

10. References | This document assigns the FEC Instance ID 0 scoped by the Under- | |||

Specified FEC Encoding ID 129 to "Reed-Solomon Codes over GF(2^^8)". | ||||

More specifically, under the "ietf:rmt:fec:encoding:instance" sub- | ||||

name-space that is scoped by the "ietf:rmt:fec:encoding" called | ||||

"Small Block Systematic FEC Codes", this document assigns FEC | ||||

Instance ID 0 to "Reed-Solomon Codes over GF(2^^8)". | ||||

10.1. Normative References | 11. Acknowledgments | |||

The authors want to thank Brian Adamson for his valuable comments. | ||||

The authors also want to thank Luigi Rizzo for comments on the | ||||

subject and for the design of the reference Reed-Solomon codec. | ||||

12. References | ||||

12.1. Normative References | ||||

[1] Bradner, S., "Key words for use in RFCs to Indicate Requirement | [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement | |||

Levels", RFC 2119. | Levels", RFC 2119. | |||

[2] Watson, M., Luby, M., and L. Vicisano, "Forward Error | [2] Watson, M., Luby, M., and L. Vicisano, "Forward Error | |||

Correction (FEC) Building Block", | Correction (FEC) Building Block", | |||

draft-ietf-rmt-fec-bb-revised-04.txt (work in progress), | draft-ietf-rmt-fec-bb-revised-07.txt (work in progress), | |||

September 2006. | April 2007. | |||

[3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., | [3] Watson, M., "Basic Forward Error Correction (FEC) Schemes", | |||

draft-ietf-rmt-bb-fec-basic-schemes-revised-03.txt (work in | ||||

progress), February 2007. | ||||

[4] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., | ||||

and J. Crowcroft, "The Use of Forward Error Correction (FEC) in | and J. Crowcroft, "The Use of Forward Error Correction (FEC) in | |||

Reliable Multicast", RFC 3453, December 2002. | Reliable Multicast", RFC 3453, December 2002. | |||

10.2. Informative References | [5] "HMAC: Keyed-Hashing for Message Authentication", RFC 2104, | |||

February 1997. | ||||

[4] Rizzo, L., "Reed-Solomon FEC codec (revised version of July | [6] "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): | |||

Multicast Source Authentication Transform Introduction", | ||||

RFC 4082, June 2005. | ||||

12.2. Informative References | ||||

[7] Rizzo, L., "Reed-Solomon FEC codec (revised version of July | ||||

2nd, 1998), available at | 2nd, 1998), available at | |||

http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz", | http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz, and | |||

July 1998. | mirrored at http://planete-bcast.inrialpes.fr/", July 1998. | |||

[5] Mac Williams, F. and N. Sloane, "The Theory of Error Correcting | [8] Mac Williams, F. and N. Sloane, "The Theory of Error Correcting | |||

Codes", North Holland, 1977 . | Codes", North Holland, 1977 . | |||

[6] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, | [9] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, | |||

"Raptor Forward Error Correction Scheme", Internet | "Raptor Forward Error Correction Scheme", | |||

Draft draft-ietf-rmt-bb-fec-raptor-object-04 (work in | draft-ietf-rmt-bb-fec-raptor-object-08 (work in progress), | |||

progress), June 2006. | April 2007. | |||

[7] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity | [10] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity | |||

Check (LDPC) Forward Error Correction", | Check (LDPC) Forward Error Correction", | |||

draft-ietf-rmt-bb-fec-ldpc-04.txt (work in progress), | draft-ietf-rmt-bb-fec-ldpc-06.txt (work in progress), | |||

December 2006. | May 2007. | |||

[8] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered | [11] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered | |||

Coding (ALC) Protocol Instantiation", | Coding (ALC) Protocol Instantiation", | |||

draft-ietf-rmt-pi-alc-revised-03.txt (work in progress), | draft-ietf-rmt-pi-alc-revised-04.txt (work in progress), | |||

April 2006. | February 2007. | |||

[9] Adamson, B., Bormann, C., Handley, M., and J. Macker, | [12] Adamson, B., Bormann, C., Handley, M., and J. Macker, | |||

"Negative-acknowledgment (NACK)-Oriented Reliable Multicast | "Negative-acknowledgment (NACK)-Oriented Reliable Multicast | |||

(NORM) Protocol", draft-ietf-rmt-pi-norm-revised-03.txt (work | (NORM) Protocol", draft-ietf-rmt-pi-norm-revised-04.txt (work | |||

in progress), September 2006. | in progress), March 2007. | |||

[10] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, | [13] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, | |||

"FLUTE - File Delivery over Unidirectional Transport", | "FLUTE - File Delivery over Unidirectional Transport", | |||

draft-ietf-rmt-flute-revised-02.txt (work in progress), | draft-ietf-rmt-flute-revised-03.txt (work in progress), | |||

August 2006. | January 2007. | |||

[11] Gohberg, I. and V. Olshevsky, "Fast algorithms with | [14] Gohberg, I. and V. Olshevsky, "Fast algorithms with | |||

preprocessing for matrix-vector multiplication problems", | preprocessing for matrix-vector multiplication problems", | |||

Journal of Complexity, pp. 411-427, vol. 10, 1994 . | Journal of Complexity, pp. 411-427, vol. 10, 1994 . | |||

Authors' Addresses | Authors' Addresses | |||

Jerome Lacan | Jerome Lacan | |||

ENSICA/LAAS-CNRS | ENSICA/LAAS-CNRS | |||

1, place Emile Blouin | 1, place Emile Blouin | |||

Toulouse 31056 | Toulouse 31056 | |||

France | France | |||

Email: jerome.lacan@ensica.fr | Email: jerome.lacan@ensica.fr | |||

URI: http://dmi.ensica.fr/auteur.php3?id_auteur=5 | URI: http://dmi.ensica.fr/auteur.php3?id_auteur=5 | |||

Vincent Roca | Vincent Roca | |||

INRIA | INRIA | |||

655, av. de l'Europe | 655, av. de l'Europe | |||

Zirst; Montbonnot | Inovallee; Montbonnot | |||

ST ISMIER cedex 38334 | ST ISMIER cedex 38334 | |||

France | France | |||

Email: vincent.roca@inrialpes.fr | Email: vincent.roca@inrialpes.fr | |||

URI: http://planete.inrialpes.fr/~roca/ | URI: http://planete.inrialpes.fr/~roca/ | |||

Jani Peltotalo | Jani Peltotalo | |||

Tampere University of Technology | Tampere University of Technology | |||

P.O. Box 553 (Korkeakoulunkatu 1) | P.O. Box 553 (Korkeakoulunkatu 1) | |||

Tampere FIN-33101 | Tampere FIN-33101 | |||

skipping to change at page 25, line 7 | skipping to change at page 29, line 7 | |||

Tampere University of Technology | Tampere University of Technology | |||

P.O. Box 553 (Korkeakoulunkatu 1) | P.O. Box 553 (Korkeakoulunkatu 1) | |||

Tampere FIN-33101 | Tampere FIN-33101 | |||

Finland | Finland | |||

Email: sami.peltotalo@tut.fi | Email: sami.peltotalo@tut.fi | |||

URI: http://atm.tut.fi/mad | URI: http://atm.tut.fi/mad | |||

Full Copyright Statement | Full Copyright Statement | |||

Copyright (C) The IETF Trust (2006). | Copyright (C) The IETF Trust (2007). | |||

This document is subject to the rights, licenses and restrictions | This document is subject to the rights, licenses and restrictions | |||

contained in BCP 78, and except as set forth therein, the authors | contained in BCP 78, and except as set forth therein, the authors | |||

retain all their rights. | retain all their rights. | |||

This document and the information contained herein are provided on an | This document and the information contained herein are provided on an | |||

"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS | "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS | |||

OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND | OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND | |||

THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS | THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS | |||

OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF | OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF | |||

End of changes. 75 change blocks. | ||||

137 lines changed or deleted | | 366 lines changed or added | ||

This html diff was produced by rfcdiff 1.33. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ |