draft-ietf-rmt-bb-fec-rs-04.txt | draft-ietf-rmt-bb-fec-rs-05.txt | |||
---|---|---|---|---|

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

Internet-Draft ISAE | Internet-Draft ISAE/LAAS-CNRS | |||

Intended status: Standards Track V. Roca | Intended status: Standards Track V. Roca | |||

Expires: April 12, 2008 INRIA | Expires: May 15, 2008 INRIA | |||

J. Peltotalo | J. Peltotalo | |||

S. Peltotalo | S. Peltotalo | |||

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

October 10, 2007 | November 12, 2007 | |||

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

draft-ietf-rmt-bb-fec-rs-04.txt | draft-ietf-rmt-bb-fec-rs-05.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 April 12, 2008. | This Internet-Draft will expire on May 15, 2008. | |||

Copyright Notice | Copyright Notice | |||

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

Abstract | Abstract | |||

This document describes a Fully-Specified Forward Error Correction | This document describes a Fully-Specified Forward Error Correction | |||

(FEC) Scheme for the Reed-Solomon FEC codes over GF(2^^m), with m in | (FEC) Scheme for the Reed-Solomon FEC codes over GF(2^^m), with m in | |||

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

on the packet erasure channel. | on the packet erasure channel (i.e., a communication path where | |||

packets are either received without any corruption or discarded | ||||

during transmission). | ||||

This document also describes a Fully-Specified FEC Scheme for the | 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 | special case of Reed-Solomon codes over GF(2^^8) when there is no | |||

encoding symbol group. | encoding symbol group. | |||

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

FEC Scheme (FEC Encoding ID 129), this document assigns an FEC | 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). | 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. The schemes described | symbols from any set of k received symbols. The schemes described | |||

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

Table of Contents | Table of Contents | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 12 | 5.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 14 | |||

5.2. FEC Object Transmission Information . . . . . . . . . . . 12 | 5.2. FEC Object Transmission Information . . . . . . . . . . . 14 | |||

5.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 12 | 5.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 14 | |||

5.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 12 | 5.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 14 | |||

5.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 13 | 5.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 15 | |||

5.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 13 | 5.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 15 | |||

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

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

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

7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) | 7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) | |||

and Reed-Solomon Codes over GF(2^^8) . . . . . . . . . . . . . 16 | and Reed-Solomon Codes over GF(2^^8) . . . . . . . . . . . . . 19 | |||

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

8.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 17 | 8.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 20 | |||

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

8.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 18 | 8.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 21 | |||

8.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 19 | 8.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 22 | |||

8.3. Reed-Solomon Decoding Algorithm . . . . . . . . . . . . . 19 | 8.3. Reed-Solomon Decoding Algorithm . . . . . . . . . . . . . 22 | |||

8.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 19 | 8.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 22 | |||

8.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 20 | 8.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 23 | |||

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

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

9.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 23 | 9.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 27 | |||

9.2. Attacks Against the Data Flow . . . . . . . . . . . . . . 23 | 9.2. Attacks Against the Data Flow . . . . . . . . . . . . . . 27 | |||

9.3. Attacks against the FEC parameters . . . . . . . . . . . . 25 | 9.2.1. Access to Confidential Objects . . . . . . . . . . . . 27 | |||

10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 | 9.2.2. Content Corruption . . . . . . . . . . . . . . . . . . 28 | |||

11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 27 | 9.3. Attacks Against the FEC Parameters . . . . . . . . . . . . 29 | |||

12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 28 | 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 30 | |||

12.1. Normative References . . . . . . . . . . . . . . . . . . . 28 | 11. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 31 | |||

12.2. Informative References . . . . . . . . . . . . . . . . . . 28 | 12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 32 | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 30 | 12.1. Normative References . . . . . . . . . . . . . . . . . . . 32 | |||

Intellectual Property and Copyright Statements . . . . . . . . . . 31 | 12.2. Informative References . . . . . . . . . . . . . . . . . . 32 | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 34 | ||||

Intellectual Property and Copyright Statements . . . . . . . . . . 35 | ||||

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 [RFC5052] document describes a general framework | |||

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

describes some applications of FEC codes for content delivery. | document [RFC3453] describes some applications of FEC codes for | |||

content delivery. | ||||

Recent FEC schemes like [9] and [8] proposed erasure codes based on | Recent FEC schemes like [RFC5053] and [draft-ietf-rmt-bb-fec-ldpc] | |||

sparse graphs/matrices. These codes are efficient in terms of | proposed erasure codes based on sparse graphs/matrices. These codes | |||

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

dealing with "small" objects. | correction capabilities when 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 [9] or [8], this family of codes is very useful. | that of [RFC5053] or [draft-ietf-rmt-bb-fec-ldpc], 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 | |||

[5]. The goal of the present document to specify an implementation | [RS-codec] [Rizzo97]. The goal of the present document is to specify | |||

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

codec. | ||||

The present document: | The present document: | |||

o introduces the Fully-Specified FEC Scheme with FEC Encoding ID 2 | 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 | that specifies the use of Reed-Solomon codes over GF(2^^m), with m | |||

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

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

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

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

per packet), and | per packet), and | |||

o in the context of the Under-Specified Small Block Systematic FEC | 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 | Scheme (FEC Encoding ID 129) | |||

the special case of Reed-Solomon codes over GF(2^^8) and no | [draft-ietf-rmt-bb-fec-basic-schemes-revised], assigns the FEC | |||

encoding symbol group. | Instance ID 0 to the special case of Reed-Solomon codes over | |||

GF(2^^8) and no encoding symbol group. | ||||

For a definition of the terms Fully-Specified and Under-Specified FEC | ||||

Schemes, see [RFC5052], section 4. | ||||

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 [RFC2119]. | |||

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

3.1. Definitions | 3.1. Definitions | |||

This document uses the same terms and definitions as those specified | This document uses the same terms and definitions as those specified | |||

in [2]. Additionally, it uses the following definitions: | in [RFC5052]. Additionally, it uses the following definitions: | |||

Source symbol: unit of data used during the encoding process. | Source symbol: unit of data used during the encoding process. | |||

Encoding symbol: unit of data generated by the encoding process. | Encoding symbol: unit of data generated by the encoding process. | |||

Repair symbol: encoding symbol that is not a source symbol. | Repair symbol: encoding symbol that is not a source symbol. | |||

Code rate: the k/n ratio, i.e., the ratio between the number of | ||||

source symbols and the number of encoding symbols. The code rate | ||||

belongs to a ]0; 1] interval. A code rate close to 1 indicates | ||||

that a small number of repair symbols have been produced during | ||||

the encoding process. | ||||

Systematic code: FEC code in which the source symbols are part of | Systematic code: FEC code in which the source symbols are part of | |||

the encoding symbols. | the encoding symbols. | |||

Source block: a block of k source symbols that are considered | Source block: a block of k source symbols that are considered | |||

together for the encoding. | together for the encoding. | |||

Encoding Symbol Group: a group of encoding symbols that are sent | Encoding Symbol Group: a group of encoding symbols that are sent | |||

together within the same packet, and whose relationships to the | together within the same packet, and whose relationships to the | |||

source block can be derived from a single Encoding Symbol ID. | source block can be derived from a single Encoding Symbol ID. | |||

Source Packet: a data packet containing only source symbols. | Source Packet: a data packet containing only source symbols. | |||

Repair Packet: a data packet containing only repair symbols. | Repair Packet: a data packet containing only repair symbols. | |||

Packet Erasure Channel: a communication path where packets are | ||||

either dropped (e.g., by a congested router, or because the number | ||||

of transmission errors exceeds the correction capabilities of the | ||||

physical layer codes) or received. When a packet is received, it | ||||

is assumed that this packet is not corrupted. | ||||

3.2. Notations | 3.2. Notations | |||

This document uses the following notations: | This document uses the following notations: | |||

L denotes the object transfer length in bytes. | L denotes the object transfer length in bytes. | |||

k denotes the number of source symbols in a source block. | k denotes the number of source symbols in a source block. | |||

n_r denotes the number of repair symbols generated for a source | n_r denotes the number of repair symbols generated for a source | |||

block. | block. | |||

skipping to change at page 7, line 19 | skipping to change at page 8, line 31 | |||

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}. | 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. | CR denotes the "code rate", i.e., the k/n ratio. | |||

a^^b denotes a raised to the power b. | a^^b denotes a raised to the power b. | |||

a^^-1 denotes the inverse of a. | a^^-1 denotes the inverse of a. | |||

I_k denotes the k*k identity matrix. | I_k denotes the k*k identity matrix. | |||

3.3. Abbreviations | 3.3. Abbreviations | |||

This document uses the following abbreviations: | This document uses the following abbreviations: | |||

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

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 (also known as Galois Field) with q | GF(q) denotes a finite field (also known as 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 with FEC Encoding ID 2 | 4. Formats and Codes with FEC Encoding ID 2 | |||

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

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

use of Reed-Solomon codes over GF(2^^m). | 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 | |||

skipping to change at page 10, line 26 | skipping to change at page 12, line 26 | |||

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

This section shows the 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 [10] or NORM [11] protocols). | mechanism is used (e.g., within the ALC | |||

[draft-ietf-rmt-pi-alc-revised] or NORM | ||||

[draft-ietf-rmt-pi-norm-revised] 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 = 4 | | | | 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 (File | When it is desired that the FEC OTI be carried in the FDT (File | |||

Delivery Table) Instance of a FLUTE session [12], the following XML | Delivery Table) Instance of a FLUTE session | |||

attributes must be described for the associated object: | [draft-ietf-rmt-flute-revised], the following XML attributes must be | |||

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

o FEC-OTI-Scheme-Specific-Info | o FEC-OTI-Scheme-Specific-Info | |||

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

skipping to change at page 11, line 34 | skipping to change at page 13, line 36 | |||

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 | During 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) that is added to the FEC-OTI-Scheme- | |||

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

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

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

Fully-Specified FEC Scheme with FEC Encoding ID 5 that focuses on 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 | special case of Reed-Solomon codes over GF(2^^8) and no encoding | |||

symbol group. | symbol group. | |||

5.1. FEC Payload ID | 5.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: | Encoding Symbol ID: | |||

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

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

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

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

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

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

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

the remaining n-k values identify repair 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. | |||

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

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

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

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

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

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

5.2. FEC Object Transmission Information | 5.2. FEC Object Transmission Information | |||

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

5.2.4. Encoding Format | 5.2.4. Encoding Format | |||

This section shows the 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. | |||

5.2.4.1. Using the General EXT_FTI Format | 5.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 [10] or NORM [11] protocols). | mechanism is used (e.g., within the ALC | |||

[draft-ietf-rmt-pi-alc-revised] or NORM | ||||

[draft-ietf-rmt-pi-norm-revised] 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 = 3 | | | | HET = 64 | HEL = 3 | | | |||

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

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

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

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

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

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

5.2.4.2. Using the FDT Instance (FLUTE specific) | 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 | When it is desired that the FEC OTI be carried in the FDT Instance of | |||

a FLUTE session [12], the following XML attributes must be described | a FLUTE session [draft-ietf-rmt-flute-revised], the following XML | |||

for the associated object: | attributes must be described 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) | |||

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

This section defines procedures that are common to FEC Encoding IDs 2 | 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 | and 5. In case of FEC Encoding ID 5, m = 8 and G = 1. The block | |||

block partitioning algorithm is defined in [2]. | partitioning algorithm that is defined in section 9.1 of [RFC5052] | |||

MUST be used with FEC Encoding IDs 2 and 5. | ||||

6.1. Determining the Maximum Source Block Length (B) | 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) there is a maximum of 2^^8 - 1 = 255 encoding symbols. | (default) there is a maximum of 2^^8 - 1 = 255 encoding symbols. | |||

Given the target FEC code rate (e.g., provided by the user when | Given the target FEC code rate (e.g., provided by the user when | |||

starting a FLUTE sending application), the sender calculates: | starting a FLUTE sending application), the sender calculates: | |||

max1_B = floor((2^^m - 1) * rate) | max1_B = floor((2^^m - 1) * CR) | |||

This max1_B value leaves enough room for the sender to produce the | This max1_B value leaves enough room for the sender to produce the | |||

desired number of parity symbols. | desired number of parity symbols. | |||

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

6.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 maximum number of encoding symbols generated for any | |||

source block (max_n) and the number of encoding symbols for a given | ||||

block (n) as a function of the target code rate. | ||||

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

Input: | Input: | |||

B: Maximum source block length, for any source block. Section 6.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 | CR: FEC code rate, which is given by the user (e.g., when starting | |||

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

floating point value. | value. | |||

Output: | Output: | |||

max_n: Maximum number of encoding symbols generated for any source | max_n: Maximum number of encoding symbols generated for any source | |||

block. | block. | |||

n: Number of encoding symbols generated for this source block. | n: Number of encoding symbols generated for this source block. | |||

Algorithm: | Algorithm: | |||

max_n = ceil(B / rate); | max_n = ceil(B / CR); | |||

if (max_n > 2^^m - 1) then return an error ("invalid code rate"); | if (max_n > 2^^m - 1) then return an error ("invalid code rate"); | |||

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

AT A RECEIVER: | AT A RECEIVER: | |||

Input: | Input: | |||

B: Extracted from the received FEC OTI. | B: Extracted from the received FEC OTI. | |||

skipping to change at page 15, line 45 | skipping to change at page 17, line 48 | |||

k: Given by the block partitioning algorithm. | k: Given by the block partitioning algorithm. | |||

Output: | Output: | |||

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. | It is RECOMMENDED that the "n-algorithm" be used by a sender, but | |||

Therefore the receiver part of the "n-algorithm" is not necessary | other algorithms remain possible to determine max_n and/or n. | |||

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

application using the Reed-Solomon FEC scheme will sometimes need to | At a receiver, the max_n value is extracted from the received FEC | |||

know the n value used by the sender, for instance for memory | OTI. Since the Reed-Solomon decoder does not need to know the actual | |||

management optimizations. To that purpose, the FEC OTI carries all | n value, using the receiver part of the "n-algorithm" is not | |||

the parameters needed for a receiver to execute the above algorithm. | necessary from a decoding point of view. | |||

However a receiver may want to have an estimate of n for other | ||||

reasons (e.g., for memory management purposes). In that case, a | ||||

receiver knows that the number of encoding symbols of a block cannot | ||||

exceed max_n. Additionally, if a receiver believes that a sender | ||||

uses the "n-algorithm", this receiver MAY use the receiver part of | ||||

the "n-algorithm" to get a better estimate of n. When this is the | ||||

case, a receiver MUST be prepared to handle symbols with an Encoding | ||||

Symbol ID superior or equal to the computed n value (e.g., it can | ||||

choose to simply drop them). | ||||

7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) and Reed- | 7. Small Block Systematic FEC Scheme (FEC Encoding ID 129) and Reed- | |||

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

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

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

Instance ID 0 to the special case of Reed-Solomon codes over GF(2^^8) | [draft-ietf-rmt-bb-fec-basic-schemes-revised], this document assigns | |||

and no encoding symbol group. | 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 Instance ID 0 uses the Formats and Codes specified in | |||

[draft-ietf-rmt-bb-fec-basic-schemes-revised]. | ||||

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

in Section 9.1. of [2] to partition the file into source blocks. | algorithm defined in Section 9.1. of [RFC5052] to partition the | |||

This FEC Scheme MAY also use another algorithm. For instance the CDP | object into source blocks. This FEC Scheme MAY also use another | |||

sender may change the length of each source block dynamically, | algorithm. For instance the CDP sender may change the length of each | |||

depending on some external criteria (e.g., to adjust the FEC coding | source block dynamically, depending on some external criteria (e.g., | |||

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

inform the CDP receivers of the current block length by means of the | NORM receivers) and inform the CDP receivers of the current block | |||

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

document. | scope of the current document. | |||

8. Reed-Solomon Codes Specification for the Erasure Channel | 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 8.1 to Section 8.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 8.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. | |||

A reader who wants to understand the underlying theory is invited to | ||||

refer to references [Rizzo97] and [MWS77]. | ||||

8.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 to m-1. The polynomials can be associated with 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 | |||

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

multiplication is the multiplication modulo a given irreducible | multiplication is the multiplication modulo a given irreducible | |||

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

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

GF(2). | ||||

A finite field GF(2^^m) is completely characterized by the | The chosen polynomial representation of the finite field GF(2^^m) is | |||

irreducible polynomial. The following polynomials are chosen to | completely characterized by the irreducible polynomial. The | |||

represent the field GF(2^^m), for m varying from 2 to 16: | following polynomials are chosen to 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) | |||

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

m = 6, "1100001", (1+x+x^^6) | m = 6, "1100001", (1+x+x^^6) | |||

skipping to change at page 19, line 27 | skipping to change at page 22, line 29 | |||

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

8.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 | 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 | n-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 | k*k-Vandermonde matrix by a vector is O(k * (log(k))^^2), the | |||

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

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

per repair element (vector-matrix multiplication). | needs k operations 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 * | |||

The multiplication by a Vandermonde matrix, known as the multipoint | (log(k))^^2). The multiplication by a Vandermonde matrix, known as | |||

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

Transform, as explained in [7]. The total complexity of this | using Fast Fourier Transform, as explained in [GO94]. The total | |||

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

operations per repair element. | (log(k))^^2 + log(k)) operations per repair element. | |||

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

8.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 [6]). | matrix which is such that any k*k-submatrix is invertible (see | |||

The first step of the decoding consists in extracting the k*k | [MWS77]). The first step of the decoding consists in extracting the | |||

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

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

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

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

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

vector by a k*k submatrix of the generator matrix. Since this | source 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. | |||

8.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(k))^^2) ) then by V_{k,k} (multipoint | |||

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

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

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

for recovering 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 corresponds 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 8.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 MUST be virtually padded with zero elements (it can be | elements, they MUST be virtually padded with zero elements (this can | |||

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

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

to the receivers. | to the receivers. | |||

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

elements, of which k are source symbols (this is a systematic code) | elements, of which k are source symbols (this is a systematic code) | |||

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

repair symbols are calculated using the corresponding m-bit elements | repair symbols are calculated using the corresponding m-bit elements | |||

of the source symbol set. A logical j-th source vector, comprised of | of the source symbol set. A logical u-th source vector, comprised of | |||

the j-th elements from the set of source symbols, is used to | the u-th elements from the set of source symbols, is used to | |||

calculate a j-th encoding vector. This j-th encoding vector then | calculate a u-th encoding vector. This u-th encoding vector then | |||

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

for the block. As a systematic code, the first k encoding symbols | 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 same as the k source symbols and the last n-k repair symbols | |||

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

Input: k source symbols | Input: k source symbols | |||

0 j S-1 | 0 u S-1 | |||

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

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

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

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

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

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

. . . | . . . | |||

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

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

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

skipping to change at page 21, line 39 | skipping to change at page 25, line 32 | |||

| generator matrix | | | generator matrix | | |||

| GM | | | GM | | |||

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

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

| | | | |||

V | V | |||

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

0 j S-1 | 0 u S-1 | |||

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

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

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

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

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

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

. . . | . . . | |||

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

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

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

skipping to change at page 23, line 40 | skipping to change at page 27, line 40 | |||

making the decoding of an object computationally expensive). | making the decoding of an object computationally expensive). | |||

These attacks can be launched either against the data flow itself | These attacks can be launched either against the data flow itself | |||

(e.g. by sending forged symbols) or against the FEC parameters that | (e.g. by sending forged symbols) or against the FEC parameters that | |||

are sent either in-band (e.g., in an EXT_FTI or FDT Instance) or out- | are sent either in-band (e.g., in an EXT_FTI or FDT Instance) or out- | |||

of-band (e.g., in a session description). | of-band (e.g., in a session description). | |||

9.2. Attacks Against the Data Flow | 9.2. Attacks Against the Data Flow | |||

First of all, let us consider the attacks against the data flow. | First of all, let us consider the attacks against the data flow. | |||

Access control is typically provided by means of encryption. This | ||||

encryption can be done over the whole object (e.g., by the content | ||||

provider, before the FEC encoding process), or be done on a packet | ||||

per packet basis (e.g., when IPSec/ESP is used [14]). If access | ||||

control is a concern, it is RECOMMENDED that one of these solutions | ||||

be used. Even if we mention these attacks here, they are not related | ||||

nor facilitated by the use of FEC. | ||||

Protection against corruptions (forged packets) is achieved by means | 9.2.1. Access to Confidential Objects | |||

of a content integrity verification/sender authentication scheme. | ||||

This service can be provided at the object level, but in that case a | Access control to the object being transmitted is typically provided | |||

receiver has no way to identify which symbol(s) is(are) corrupted if | by means of encryption. This encryption can be done over the whole | |||

the object is detected as corrupted. This service can also be | object (e.g., by the content provider, before the FEC encoding | |||

provided at the packet level, and after having removed all forged | process), or be done on a packet per packet basis (e.g., when IPSec/ | |||

packets, the object can be recovered if the number of symbols | ESP is used [RFC4303]). If access control is a concern, it is | |||

remaining is sufficient. Several techniques can provide this source | RECOMMENDED that one of these solutions be used. Even if we mention | |||

these attacks here, they are not related nor facilitated by the use | ||||

of FEC. | ||||

9.2.2. Content Corruption | ||||

Protection against corruptions (e.g., after sending forged packets) | ||||

is achieved by means of a content integrity verification/sender | ||||

authentication scheme. This service can be provided at the object | ||||

level, but in that case a receiver has no way to identify which | ||||

symbol(s) is(are) corrupted if the object is detected as corrupted. | ||||

This service can also be provided at the packet level. In this case, | ||||

after removing all forged packets, the object may be in some case | ||||

recovered. Several techniques can provide this source | ||||

authentication/content integrity service: | authentication/content integrity service: | |||

o at the object level, the object MAY be digitally signed (with | o at the object level, the object MAY be digitally signed (with | |||

public key cryptography) (e.g., using RSASSA-PKCS1-v1_5 [13]). | public key cryptography), for instance by using RSASSA-PKCS1-v1_5 | |||

This signature enables a receiver to check the object, once this | [RFC3447]. This signature enables a receiver to check the object | |||

latter has been fully decoded. Even if digital signatures are | integrity, once this latter has been fully decoded. Even if | |||

computationally expensive, this calculation occurs only once per | digital signatures are computationally expensive, this calculation | |||

object, which is usually acceptable; | occurs only once per object, which is usually acceptable; | |||

o at the packet level, each packet can be digitally signed. A major | o at the packet level, each packet can be digitally signed. A major | |||

limitation is the high computational and transmission overheads | limitation is the high computational and transmission overheads | |||

that this solution incurs (unless ECC is used, but ECC is | that this solution requires (unless Elliptic Curve Cryptography | |||

protected by IPR). To avoid this problem, the signature may span | (ECC) is used, but ECC is the subject of proprietary patents). To | |||

a set of symbols in order to amortize the signature calculation, | avoid this problem, the signature may span a set of symbols | |||

but if a single symbol is missing, the integrity of the whole set | (instead of a single one) in order to amortize the signature | |||

cannot be checked; | calculation. But if a single symbol is missing, the integrity of | |||

the whole set cannot be checked; | ||||

o at the packet level, a Group Message Authentication Code (MAC) | o at the packet level, a Group Message Authentication Code (MAC) | |||

[15] (e.g., using HMAC-SHA-1 with a secret key shared by all the | [RFC2104] scheme can be used, for instance by using HMAC-SHA-1 | |||

group members, senders and receivers) scheme can be used. This | with a secret key shared by all the group members, senders and | |||

technique creates a cryptographically secured (thanks to the | receivers. This technique creates a cryptographically secured | |||

secret key) digest of a packet that is sent along with the packet. | (thanks to the secret key) digest of a packet that is sent along | |||

The Group MAC scheme does not incur prohibitive processing load | with the packet. The Group MAC scheme does not create prohibitive | |||

nor transmission overhead, but it has a major limitation: it only | processing load nor transmission overhead, but it has a major | |||

provides a group authentication/integrity service since all group | limitation: it only provides a group authentication/integrity | |||

members share the same secret group key, which means that each | service since all group members share the same secret group key, | |||

member can send a forged packet. It is therefore restricted to | which means that each member can send a forged packet. It is | |||

situations where group members are fully trusted (or in | therefore restricted to situations where group members are fully | |||

association with another technique as a pre-check); | trusted (or in association with another technique as a pre-check); | |||

o at the packet level, TESLA [16] is a very attractive and efficient | ||||

solution that is robust to losses, provides a true authentication/ | ||||

integrity service, and does not incur any prohibitive processing | ||||

load or transmission overhead. | ||||

It is up to the developer, who knows the security requirements of the | ||||

target use-case, to define which solution is the most appropriate. | ||||

Nonetheless, it is RECOMMENDED that at least one of these techniques | ||||

be used. | ||||

o at the packet level, TESLA [RFC4082] is a very attractive and | ||||

efficient solution that is robust to losses, provides a true | ||||

authentication/integrity service, and does not create any | ||||

prohibitive processing load or transmission overhead. Yet | ||||

checking a packet requires a small delay (a second or more) after | ||||

its reception; | ||||

Techniques relying on public key cryptography (digital signatures and | Techniques relying on public key cryptography (digital signatures and | |||

TESLA during the bootstrap process) require that public keys be | TESLA during the bootstrap process, when used) require that public | |||

securely associated to the entities. This can be achieved by a | keys be securely associated to the entities. This can be achieved by | |||

Public Key Infrastructure (PKI), or by a PGP Web of Trust, or by pre- | a Public Key Infrastructure (PKI), or by a PGP Web of Trust, or by | |||

distributing the public keys of each group member. It is up to the | pre-distributing the public keys of each group member. | |||

developer, who knows the features of the target use-case, to define | ||||

which solution to use. | ||||

Techniques relying on symmetric key cryptography (group MAC) require | Techniques relying on symmetric key cryptography (group MAC) require | |||

that a secret key be shared by all group members. This can be | that a secret key be shared by all group members. This can be | |||

achieved by means of a group key management protocol, or simply by | achieved by means of a group key management protocol, or simply by | |||

pre-distributing the secret key (but this manual solution has many | pre-distributing the secret key (but this manual solution has many | |||

limitations). Here also, it is up to the developer to define which | limitations). | |||

solution to use, taking into account the target use-case features. | ||||

9.3. Attacks against the FEC parameters | It is up to the developer and deployer, who know the security | |||

requirements and features of the target application area, to define | ||||

which solution is the most appropriate. Nonetheless, in case there | ||||

is any concern of the threat of object corruption, it is RECOMMENDED | ||||

that at least one of these techniques be used. | ||||

9.3. Attacks Against the FEC Parameters | ||||

Let us now consider attacks against the FEC parameters (or FEC OTI). | Let us now consider attacks against the FEC parameters (or FEC OTI). | |||

The FEC OTI can either be sent in-band (i.e., in an EXT_FTI or in an | The FEC OTI can either be sent in-band (i.e., in an EXT_FTI or in an | |||

FDT Instance containing FEC OTI for the object) or out-of-band (e.g., | FDT Instance containing FEC OTI for the object) or out-of-band (e.g., | |||

in a session description). Attacks on these FEC parameters can | in a session description). Attacks on these FEC parameters can | |||

prevent the decoding of the associated object: for instance modifying | prevent the decoding of the associated object: for instance modifying | |||

the B parameter will lead to a different block partitioning at a | the B parameter will lead to a different block partitioning at a | |||

receiver thereby compromising decoding; or setting the m parameter to | receiver thereby compromising decoding; or setting the m parameter to | |||

16 instead of 8 with FEC Encoding ID 2 will increase the processing | 16 instead of 8 with FEC Encoding ID 2 will increase the processing | |||

load while compromising decoding. | load while compromising decoding. | |||

It is therefore RECOMMENDED that security measures be taken to | It is therefore RECOMMENDED that security measures be taken to | |||

guarantee the FEC OTI integrity. To that purpose, the packets | guarantee the FEC OTI integrity. To that purpose, the packets | |||

carrying the FEC parameters sent in-band (i.e., in an EXT_FTI header | carrying the FEC parameters sent in-band in an EXT_FTI header | |||

extension or in an FDT Instance) may be protected by one of the per- | extension SHOULD be protected by one of the per-packet techniques | |||

packet techniques described above: TESLA, digital signature, or a | described above: digital signature, group MAC, or TESLA. When FEC | |||

group MAC. Alternatively, when FEC OTI is contained in an FDT | OTI is contained in an FDT Instance, this object SHOULD be protected, | |||

Instance, this object may be digitally signed. Finally, when FEC OTI | for instance by digitally signing it with XML digital signatures | |||

is sent out-of-band for instance in a session description, this | [RFC3275]. Finally, when FEC OTI is sent out-of-band (e.g., in a | |||

latter may be protected by a digital signature. | session description) this latter SHOULD be protected, for instance by | |||

digitally signing it. | ||||

The same considerations concerning the key management aspects apply | The same considerations concerning the key management aspects apply | |||

here also. | here also. | |||

10. IANA Considerations | 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]. | apply to this document, see [RFC5052]. | |||

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

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

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

This document assigns the Fully-Specified FEC Encoding ID 5 under the | This document assigns the Fully-Specified FEC Encoding ID 5 under the | |||

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

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

This document assigns the FEC Instance ID 0 scoped by the Under- | 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)". | Specified FEC Encoding ID 129 to "Reed-Solomon Codes over GF(2^^8)". | |||

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

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

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

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

11. Acknowledgments | 11. Acknowledgments | |||

The authors want to thank Brian Adamson, Igor Slepchin, Stephen Kent, | The authors want to thank Brian Adamson, Igor Slepchin, Stephen Kent, | |||

and Francis Dupont for their valuable comments. The authors also | Francis Dupont, Elwyn Davies, Magnus Westerlund and Alfred Hoenes for | |||

want to thank Luigi Rizzo for his comments and for the design of the | their valuable comments. The authors also want to thank Luigi Rizzo | |||

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

codec. | ||||

12. References | 12. References | |||

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

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

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

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

Correction (FEC) Building Block", RFC 5052, August 2007. | Correction (FEC) Building Block", RFC 5052, August 2007. | |||

[3] Watson, M., "Basic Forward Error Correction (FEC) Schemes", | [draft-ietf-rmt-bb-fec-basic-schemes-revised] | |||

draft-ietf-rmt-bb-fec-basic-schemes-revised-03.txt (work in | Watson, M., "Basic Forward Error Correction (FEC) | |||

progress), February 2007. | Schemes", | |||

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

in progress), February 2007. | ||||

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

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

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

Reliable Multicast", RFC 3453, December 2002. | (FEC) in Reliable Multicast", RFC 3453, December 2002. | |||

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

2nd, 1998), available at | Rizzo, L., "Reed-Solomon FEC codec (revised version of | |||

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

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

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

July 1998. | ||||

[6] Mac Williams, F. and N. Sloane, "The Theory of Error Correcting | [Rizzo97] Rizzo, L., "Effective Erasure Codes for Reliable Computer | |||

Codes", North Holland, 1977. | Communication Protocols", ACM SIGCOMM Computer | |||

Communication Review Vol.27, No.2, pp.24-36, April 1997. | ||||

[7] Gohberg, I. and V. Olshevsky, "Fast algorithms with | [MWS77] Mac Williams, F. and N. Sloane, "The Theory of Error | |||

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

[GO94] 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. | |||

[8] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity | [draft-ietf-rmt-bb-fec-ldpc] | |||

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-06.txt (work in progress), | draft-ietf-rmt-bb-fec-ldpc-07.txt (work in progress), | |||

May 2007. | November 2007. | |||

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

"Raptor Forward Error Correction Scheme", | "Raptor Forward Error Correction Scheme", RFC 5053, | |||

draft-ietf-rmt-bb-fec-raptor-object-09 (work in progress), | ||||

June 2007. | June 2007. | |||

[10] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered | [draft-ietf-rmt-pi-alc-revised] | |||

Coding (ALC) Protocol Instantiation", | Luby, M., Watson, M., and L. Vicisano, "Asynchronous | |||

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

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

February 2007. | February 2007. | |||

[11] Adamson, B., Bormann, C., Handley, M., and J. Macker, | [draft-ietf-rmt-pi-norm-revised] | |||

"Negative-acknowledgment (NACK)-Oriented Reliable Multicast | Adamson, B., Bormann, C., Handley, M., and J. Macker, | |||

(NORM) Protocol", draft-ietf-rmt-pi-norm-revised-05.txt (work | "Negative-acknowledgment (NACK)-Oriented Reliable | |||

in progress), March 2007. | Multicast (NORM) Protocol", | |||

draft-ietf-rmt-pi-norm-revised-05.txt (work in progress), | ||||

March 2007. | ||||

[12] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, | [draft-ietf-rmt-flute-revised] | |||

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-04.txt (work in progress), | draft-ietf-rmt-flute-revised-05.txt (work in progress), | |||

October 2007. | October 2007. | |||

[13] Jonsson, J. and B. Kaliski, "Public-Key Cryptography Standards | [RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography | |||

(PKCS) #1: RSA Cryptography Specifications Version 2.1", | Standards (PKCS) #1: RSA Cryptography Specifications | |||

RFC 3447, February 2003. | Version 2.1", RFC 3447, February 2003. | |||

[14] Kent, S., "IP Encapsulating Security Payload (ESP)", RFC 4303, | [RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)", | |||

December 2005. | RFC 4303, December 2005. | |||

[15] "HMAC: Keyed-Hashing for Message Authentication", RFC 2104, | [RFC2104] "HMAC: Keyed-Hashing for Message Authentication", | |||

February 1997. | RFC 2104, February 1997. | |||

[16] "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): | [RFC4082] "Timed Efficient Stream Loss-Tolerant Authentication | |||

Multicast Source Authentication Transform Introduction", | (TESLA): Multicast Source Authentication Transform | |||

RFC 4082, June 2005. | Introduction", RFC 4082, June 2005. | |||

[RFC3275] Eastlake, D., Reagle, J., and D. Solo, "(Extensible Markup | ||||

Language) XML-Signature Syntax and Processing", RFC 3275, | ||||

March 2002. | ||||

Authors' Addresses | Authors' Addresses | |||

Jerome Lacan | Jerome Lacan | |||

ISAE | ISAE/LAAS-CNRS | |||

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

Toulouse 31056 | Toulouse 31056 | |||

France | France | |||

Email: jerome.lacan@isae.fr | Email: jerome.lacan@isae.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 | |||

Inovallee; Montbonnot | Inovallee; Montbonnot | |||

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

France | France | |||

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

URI: http://planete.inrialpes.fr/~roca/ | URI: http://planete.inrialpes.fr/people/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 | |||

Finland | Finland | |||

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

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

End of changes. 84 change blocks. | ||||

251 lines changed or deleted | | 321 lines changed or added | ||

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