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

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

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

Expires: December 25, 2006 V. Roca | Intended status: Experimental V. Roca | |||

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

J. Peltotalo | J. Peltotalo | |||

S. Peltotalo | S. Peltotalo | |||

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

June 23, 2006 | December 22, 2006 | |||

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

draft-ietf-rmt-bb-fec-rs-01.txt | draft-ietf-rmt-bb-fec-rs-02.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 December 25, 2006. | This Internet-Draft will expire on June 25, 2007. | |||

Copyright Notice | Copyright Notice | |||

Copyright (C) The Internet Society (2006). | Copyright (C) The IETF Trust (2006). | |||

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 code and its application to the | |||

reliable delivery of data objects on the packet erasure channel. | reliable delivery of data objects on the packet erasure channel. | |||

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 implementation described here is compatible with the | The implementation described here is compatible with the | |||

implementation from Luigi Rizzo. | implementation from Luigi Rizzo. | |||

Table of Contents | Table of Contents | |||

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

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

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

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

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

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

4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 7 | 4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 8 | |||

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

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

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

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

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

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

5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 11 | 5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 12 | |||

5.1. Determining the Maximum Source Block Length (B) . . . . . 11 | 5.1. Determining the Maximum Source Block Length (B) . . . . . 12 | |||

5.2. Determining the Number of Encoding Symbols of a Block . . 11 | 5.2. Determining the Number of Encoding Symbols of a Block . . 12 | |||

6. Reed-Solomon Codes Specification for the Erasure Channel . . . 13 | 6. Reed-Solomon Codes Specification for the Erasure Channel . . . 14 | |||

6.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 13 | 6.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 14 | |||

6.2. Reed-Solomon Encoding Algorithm . . . . . . . . . . . . . 14 | 6.2. Reed-Solomon Encoding Algorithm . . . . . . . . . . . . . 15 | |||

6.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 14 | 6.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 15 | |||

6.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 15 | 6.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 16 | |||

6.3. Reed-Solomon Decoding Algorithm . . . . . . . . . . . . . 15 | 6.3. Reed-Solomon Decoding Algorithm . . . . . . . . . . . . . 16 | |||

6.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 15 | 6.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 16 | |||

6.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 16 | 6.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 17 | |||

6.4. Implementation for the Packet Erasure Channel . . . . . . 16 | 6.4. Implementation for the Packet Erasure Channel . . . . . . 17 | |||

7. Security Considerations . . . . . . . . . . . . . . . . . . . 18 | 7. Security Considerations . . . . . . . . . . . . . . . . . . . 19 | |||

8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 | 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 | |||

9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 20 | 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21 | |||

10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 21 | 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22 | |||

10.1. Normative References . . . . . . . . . . . . . . . . . . . 21 | 10.1. Normative References . . . . . . . . . . . . . . . . . . . 22 | |||

10.2. Informative References . . . . . . . . . . . . . . . . . . 21 | 10.2. Informative References . . . . . . . . . . . . . . . . . . 22 | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 23 | Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 24 | |||

Intellectual Property and Copyright Statements . . . . . . . . . . 24 | Intellectual Property and Copyright Statements . . . . . . . . . . 25 | |||

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 [3] | |||

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 [6] and [7] proposed erasure codes based on | |||

skipping to change at page 6, line 10 | skipping to change at page 7, line 10 | |||

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

B denotes the maximum source block length in symbols, i.e. the | B denotes the maximum source block length in symbols, i.e. the | |||

maximum number of source symbols per source block. | maximum number of source symbols per source block. | |||

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

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

skipping to change at page 7, line 13 | skipping to change at page 8, line 13 | |||

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

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 (32-m bit field) identifies from which | o The Source Block Number (field of size 32-m bits) identifies from | |||

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

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

object. | blocks per object. | |||

o The Encoding Symbol ID (m bit field) identifies which specific | o The Encoding Symbol ID (field of size m bits) identifies which | |||

encoding symbol(s) generated from the source block is(are) carried | specific encoding symbol(s) generated from the source block | |||

in the packet payload. There are a maximum of 2^^m encoding | is(are) carried in the packet payload. There are a maximum of | |||

symbols per block. The first k values (0 to k - 1) identify | 2^^m encoding symbols per block. The first k values (0 to k - 1) | |||

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

symbols. | ||||

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

In case of an Encoding Symbol Group, when multiple encoding symbols | In case of an Encoding Symbol Group, when multiple encoding symbols | |||

are sent in the same packet, the FEC Payload ID refers to the first | are sent in the same packet, the FEC Payload ID refers to the first | |||

symbol of the packet. The other symbols can be deduced from the ESI | symbol of the packet. The other symbols can be deduced from the ESI | |||

of the first symbol by incrementing sequentially the ESI. | of the first symbol by incrementing sequentially the ESI. | |||

The format of the FEC Payload ID for m = 8 and m = 16 is illustrated | The format of the FEC Payload ID for m = 8 and m = 16 is illustrated | |||

in Figure 1 and Figure 2 respectively. | in Figure 1 and Figure 2 respectively. | |||

skipping to change at page 8, line 10 | skipping to change at page 9, line 10 | |||

| 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 XX. | document 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 49 | skipping to change at page 10, line 49 | |||

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

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 [10], the following XML attributes must be described | |||

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

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

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

o FEC-OTI-Number-of-Encoding-Symbols-per-Group (optional) (G) | o FEC-OTI-Scheme-Specific-Info | |||

o FEC-OTI-Finite-Field-Parameter (optional) (m) | The FEC-OTI-Scheme-Specific-Info contains the string resulting from | |||

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

following value: | ||||

When no G parameter is to be carried in the FEC OTI, the sender | 0 1 | |||

simply omits the FEC-OTI-Number-of-Encoding-Symbols-per-Group | 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 | |||

attribute. When no Finite Field parameter is to be carried in the | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

FEC OTI, the sender simply omits the FEC-OTI-Finite-Field-Parameter | | m | G | | |||

attribute. | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | |||

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

FDT Instance | ||||

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

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

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

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

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

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

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

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

Specific-Info attribute. | ||||

5. Procedures | 5. Procedures | |||

5.1. Determining the Maximum Source Block Length (B) | 5.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 | |||

block size. Yet it is not expected that such limits exist when using | block size. Yet it is not expected that such limits exist when using | |||

the default m = 8 value. This decision SHOULD be clarified at | the default m = 8 value. This decision MUST be clarified at | |||

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

skipping to change at page 12, line 36 | skipping to change at page 13, line 36 | |||

n | n | |||

Algorithm: | Algorithm: | |||

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 value of n 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 | 6. 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 | |||

skipping to change at page 13, line 25 | skipping to change at page 14, line 25 | |||

m-bit elements, and Section 6.4 the use of [n,k]-RS codes when | m-bit elements, and Section 6.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 | 6.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 less | polynomials with binary coefficients (i.e. over GF(2)) of degree | |||

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

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

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

representation. The addition between two elements is defined as the | polynomial representation. The addition between two elements is | |||

addition of binary polynomials in GF(2) and the multiplication is the | defined as the addition of binary polynomials in GF(2) and the | |||

multiplication modulo a given irreducible polynomial over GF(2) of | multiplication is the multiplication modulo a given irreducible | |||

degree m with coefficients in GF(2). Note that all the roots of this | polynomial over GF(2) of degree m with coefficients in GF(2). Note | |||

polynomial are in GF(2^^m) but not in GF(2). | that all the roots of this polynomial are in GF(2^^m) but not in | |||

GF(2). | ||||

A finite field GF(2^^m) is completely characterized by the | A finite field GF(2^^m) is completely characterized by the | |||

irreducible polynomial. The following polynomials are chosen to | irreducible polynomial. The following polynomials are chosen to | |||

represent the field GF(2^^m), for m varying from 2 to 16: | represent the field GF(2^^m), for m varying from 2 to 16: | |||

m = 2, "111" (1+x+x^^2) | m = 2, "111" (1+x+x^^2) | |||

m = 3, "1101", (1+x+x^^3) | m = 3, "1101", (1+x+x^^3) | |||

m = 4, "11001", (1+x+x^^4) | m = 4, "11001", (1+x+x^^4) | |||

skipping to change at page 14, line 40 | skipping to change at page 15, line 42 | |||

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

alpha the primitive element of GF(2^^m) chosen in the list of | alpha the root of the primitive polynomial of degree m chosen in the | |||

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

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

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 matrix | = alpha^^(i*j), where 0 <= i <= k - 1 and 0 <= j <= n - 1. This | |||

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

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

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

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

elements are equal to source elements. Besides the associated code | elements are equal to source elements. Besides the associated code | |||

keeps the MDS property. | keeps the MDS property. | |||

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

skipping to change at page 16, line 31 | skipping to change at page 17, line 33 | |||

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 | 6.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 received correctly 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 k source symbols and to | codes for generating redundant symbols from the k source symbols and | |||

recover the source symbols from any set of k received symbols. | to recover 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 is associated 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 6.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 are virtually padded with zero elements (it can be the | |||

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

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

elements, the k source symbols being also part of the n encoding | elements, the k source symbols being also part of the n encoding | |||

symbols (Figure 4). These repair symbols are created m-bit element | symbols (Figure 5). These repair symbols are created m-bit element | |||

per m-bit element. More specifically, the j-th source vector is | per m-bit element. More specifically, the j-th source vector is | |||

composed of the j-th element of each of the source symbols. | composed of the j-th element of each of the source symbols. | |||

Similarly, the j-th encoding vector is composed of the j-th element | Similarly, the j-th encoding vector is composed of the j-th element | |||

of each encoding symbol. | of each encoding symbol. | |||

------------ --------------- ------------------- | n | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

k source symbols n encoding symbols | k source symbols n encoding symbols | |||

(source + repair) | (source + repair) | |||

Figure 4: Packet encoding scheme | Figure 5: 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 | |||

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

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

The security considerations for this document are the same as that of | The security considerations for this document are the same as that of | |||

[2]. | [2]. | |||

8. IANA Considerations | 8. 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]. This document assigns the Fully- | |||

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

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

9. Acknowledgments | 9. Acknowledgments | |||

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

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

10. References | 10. References | |||

10.1. Normative References | 10.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 Correction | [2] Watson, M., Luby, M., and L. Vicisano, "Forward Error | |||

(FEC) Building Block", draft-ietf-rmt-fec-bb-revised-03.txt | Correction (FEC) Building Block", | |||

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

September 2006. | ||||

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

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 | 10.2. Informative References | |||

[4] Rizzo, L., "Reed-Solomon FEC codec (revised version of July | [4] 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", | |||

July 1998. | July 1998. | |||

[5] Mac Williams, F. and N. Sloane, "The Theory of Error Correcting | [5] 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, | [6] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, | |||

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

Draft draft-ietf-rmt-bb-fec-raptor-object-03 (work in | Draft draft-ietf-rmt-bb-fec-raptor-object-04 (work in | |||

progress), October 2005. | progress), June 2006. | |||

[7] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity | [7] 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-01.txt (work in progress), | draft-ietf-rmt-bb-fec-ldpc-04.txt (work in progress), | |||

March 2006. | December 2006. | |||

[8] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered | [8] 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-03.txt (work in progress), | |||

April 2006. | April 2006. | |||

[9] Adamson, B., Bormann, C., Handley, M., and J. Macker, | [9] 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-01.txt (work | (NORM) Protocol", draft-ietf-rmt-pi-norm-revised-03.txt (work | |||

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

[10] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, | [10] 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-01.txt (work in progress), | draft-ietf-rmt-flute-revised-02.txt (work in progress), | |||

January 2006. | August 2006. | |||

[11] Gohberg, I. and V. Olshevsky, "Fast algorithms with | [11] 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 | |||

skipping to change at page 24, line 5 | skipping to change at page 25, line 5 | |||

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

Finland | Finland | |||

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

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

Intellectual Property Statement | Full Copyright Statement | |||

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

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

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

retain all their rights. | ||||

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

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

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

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

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

THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED | ||||

WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. | ||||

Intellectual Property | ||||

The IETF takes no position regarding the validity or scope of any | The IETF takes no position regarding the validity or scope of any | |||

Intellectual Property Rights or other rights that might be claimed to | Intellectual Property Rights or other rights that might be claimed to | |||

pertain to the implementation or use of the technology described in | pertain to the implementation or use of the technology described in | |||

this document or the extent to which any license under such rights | this document or the extent to which any license under such rights | |||

might or might not be available; nor does it represent that it has | might or might not be available; nor does it represent that it has | |||

made any independent effort to identify any such rights. Information | made any independent effort to identify any such rights. Information | |||

on the procedures with respect to rights in RFC documents can be | on the procedures with respect to rights in RFC documents can be | |||

found in BCP 78 and BCP 79. | found in BCP 78 and BCP 79. | |||

skipping to change at page 24, line 29 | skipping to change at page 25, line 45 | |||

such proprietary rights by implementers or users of this | such proprietary rights by implementers or users of this | |||

specification can be obtained from the IETF on-line IPR repository at | specification can be obtained from the IETF on-line IPR repository at | |||

http://www.ietf.org/ipr. | http://www.ietf.org/ipr. | |||

The IETF invites any interested party to bring to its attention any | The IETF invites any interested party to bring to its attention any | |||

copyrights, patents or patent applications, or other proprietary | copyrights, patents or patent applications, or other proprietary | |||

rights that may cover technology that may be required to implement | rights that may cover technology that may be required to implement | |||

this standard. Please address the information to the IETF at | this standard. Please address the information to the IETF at | |||

ietf-ipr@ietf.org. | ietf-ipr@ietf.org. | |||

Disclaimer of Validity | ||||

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

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

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

ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, | ||||

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

INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED | ||||

WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. | ||||

Copyright Statement | ||||

Copyright (C) The Internet Society (2006). This document is subject | ||||

to the rights, licenses and restrictions contained in BCP 78, and | ||||

except as set forth therein, the authors retain all their rights. | ||||

Acknowledgment | Acknowledgment | |||

Funding for the RFC Editor function is currently provided by the | Funding for the RFC Editor function is provided by the IETF | |||

Internet Society. | Administrative Support Activity (IASA). | |||

End of changes. 37 change blocks. | ||||

120 lines changed or deleted | | 145 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/ |