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

Reliable Multicast Transport J. Lacan | Network Working Group J. Lacan | |||

Internet-Draft ISAE/LAAS-CNRS | Request for Comments: 5510 ISAE/LAAS-CNRS | |||

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

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

J. Peltotalo | J. Peltotalo | |||

S. Peltotalo | S. Peltotalo | |||

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

November 12, 2007 | ||||

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

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

Status of this Memo | ||||

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

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

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

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

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

other groups may also distribute working documents as Internet- | ||||

Drafts. | ||||

Internet-Drafts are draft documents valid for a maximum of six months | Status of This Memo | |||

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

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

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

The list of current Internet-Drafts can be accessed at | This document specifies an Internet standards track protocol for the | |||

http://www.ietf.org/ietf/1id-abstracts.txt. | Internet community, and requests discussion and suggestions for | |||

improvements. Please refer to the current edition of the "Internet | ||||

Official Protocol Standards" (STD 1) for the standardization state | ||||

and status of this protocol. Distribution of this memo is unlimited. | ||||

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

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

This Internet-Draft will expire on May 15, 2008. | Copyright (c) 2009 IETF Trust and the persons identified as the | |||

document authors. All rights reserved. | ||||

Copyright Notice | This document is subject to BCP 78 and the IETF Trust's Legal | |||

Provisions Relating to IETF Documents in effect on the date of | ||||

publication of this document (http://trustee.ietf.org/license-info). | ||||

Please review these documents carefully, as they describe your rights | ||||

and restrictions with respect to this document. | ||||

Copyright (C) The IETF Trust (2007). | This document may contain material from IETF Documents or IETF | |||

Contributions published or made publicly available before November | ||||

10, 2008. The person(s) controlling the copyright in some of this | ||||

material may not have granted the IETF Trust the right to allow | ||||

modifications of such material outside the IETF Standards Process. | ||||

Without obtaining an adequate license from the person(s) controlling | ||||

the copyright in such materials, this document may not be modified | ||||

outside the IETF Standards Process, and derivative works of it may | ||||

not be created outside the IETF Standards Process, except to format | ||||

it for publication as an RFC or to translate it into languages other | ||||

than English. | ||||

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), where m is | |||

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

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

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

during transmission). | during transmission). This document also describes a Fully-Specified | |||

FEC Scheme for the special case of Reed-Solomon codes over GF(2^^8) | ||||

This document also describes a Fully-Specified FEC Scheme for the | when there is no encoding symbol group. Finally, in the context of | |||

special case of Reed-Solomon codes over GF(2^^8) when there is no | the Under-Specified Small Block Systematic FEC Scheme (FEC Encoding | |||

encoding symbol group. | ID 129), this document assigns an FEC Instance ID to the special case | |||

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

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

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

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

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

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

symbols from any set of k received symbols. 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 . . . . . . . . . . . . . . . . . . . . . . . . . 5 | 1. Introduction ....................................................4 | |||

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

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

3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 7 | 3.1. Definitions ................................................5 | |||

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

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

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

4.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 10 | 4.1. FEC Payload ID .............................................7 | |||

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

4.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 11 | 4.2.1. Mandatory Elements ..................................8 | |||

4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 11 | 4.2.2. Common Elements .....................................8 | |||

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

4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 12 | 4.2.4. Encoding Format .....................................9 | |||

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

5.1. FEC Payload ID . . . . . . . . . . . . . . . . . . . . . . 14 | 5.1. FEC Payload ID ............................................11 | |||

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

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

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

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

5.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 15 | 5.2.4. Encoding Format ....................................12 | |||

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

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

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

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) . . . . . . . . . . . . . 19 | and Reed-Solomon Codes over GF(2^^8) ...........................15 | |||

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

8.1. Finite Field . . . . . . . . . . . . . . . . . . . . . . . 20 | 8.1. Finite Field ..............................................16 | |||

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

8.2.1. Encoding Principles . . . . . . . . . . . . . . . . . 21 | 8.2.1. Encoding Principles ................................17 | |||

8.2.2. Encoding Complexity . . . . . . . . . . . . . . . . . 22 | 8.2.2. Encoding Complexity ................................18 | |||

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

8.3.1. Decoding Principles . . . . . . . . . . . . . . . . . 22 | 8.3.1. Decoding Principles ................................18 | |||

8.3.2. Decoding Complexity . . . . . . . . . . . . . . . . . 23 | 8.3.2. Decoding Complexity ................................19 | |||

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

9. Security Considerations . . . . . . . . . . . . . . . . . . . 27 | 9. Security Considerations ........................................22 | |||

9.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 27 | 9.1. Problem Statement .........................................22 | |||

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

9.2.1. Access to Confidential Objects . . . . . . . . . . . . 27 | 9.2.1. Access to Confidential Objects .....................23 | |||

9.2.2. Content Corruption . . . . . . . . . . . . . . . . . . 28 | 9.2.2. Content Corruption .................................23 | |||

9.3. Attacks Against the FEC Parameters . . . . . . . . . . . . 29 | 9.3. Attacks against the FEC Parameters ........................24 | |||

10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 30 | 10. IANA Considerations ...........................................25 | |||

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

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

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

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

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

to use FEC in Content Delivery Protocols (CDP). The companion | to use FEC in Content Delivery Protocols (CDPs). The companion | |||

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

content delivery. | content delivery. | |||

Recent FEC schemes like [RFC5053] and [draft-ietf-rmt-bb-fec-ldpc] | Recent FEC schemes like [RFC5053] and [RFC5170] proposed erasure | |||

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

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

correction capabilities when dealing with "small" objects. | capabilities when dealing with "small" objects. | |||

The FEC scheme described in this document belongs to the class of | The FEC schemes 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. They are also systematic codes, which means that the k | |||

that of [RFC5053] or [draft-ietf-rmt-bb-fec-ldpc], this family of | source symbols are part of the encoding symbols. Even if the | |||

codes is very useful. | encoding/decoding complexity is larger than that of [RFC5053] or | |||

[RFC5170], 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 | |||

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

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

codec. | 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 | which specifies the use of Reed-Solomon codes over GF(2^^m), where | |||

in {2..16}, | m is 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 | which 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) | Scheme (FEC Encoding ID 129) [RFC5445], assigns the FEC Instance | |||

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

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

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

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

Schemes, see [RFC5052], section 4. | 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 [RFC2119]. | 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 | |||

skipping to change at page 7, line 19 | skipping to change at page 5, line 25 | |||

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

in [RFC5052]. 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 | 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 | source symbols and the number of encoding symbols. By | |||

belongs to a ]0; 1] interval. A code rate close to 1 indicates | definition, the code rate is such that: 0 < code rate <= 1. A | |||

that a small number of repair symbols have been produced during | code rate close to 1 indicates that a small number of repair | |||

the encoding process. | 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 | Packet Erasure Channel: a communication path where packets are | |||

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

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

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

is assumed that this packet is not corrupted. | 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 the object transfer length in bytes. | |||

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

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

block. | ||||

n denotes the encoding block length, i.e., the number of encoding | n the encoding block length, i.e., the number of encoding | |||

symbols generated for a source block. Therefore: n = k + n_r. | symbols generated for a source block. Therefore: n = k + | |||

n_r. | ||||

max_n denotes the maximum number of encoding symbols generated for | max_n the maximum number of encoding symbols generated for any | |||

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

B denotes the maximum source block length in symbols, i.e., the | B 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 the number of source blocks into which the object shall be | |||

be partitioned. | partitioned. | |||

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

S denotes the symbol size in units of m-bit elements. When m = 8, | S 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 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 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 the number of encoding symbols per group, i.e., the number | |||

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

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

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

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

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

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

3.3. Abbreviations | 3.3. Abbreviations | |||

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

ESI stands for Encoding Symbol ID. | ESI Encoding Symbol ID. | |||

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

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

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

GF(q) denotes a finite field (also known as Galois Field) with q | GF(q) 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 with 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, which specifies | |||

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

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

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

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

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

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

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

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

per object. | object. | |||

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

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

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

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

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

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

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 (32-8=24 bits) | Enc. Symb. ID | | | Source Block Number (32-8=24 bits) | Enc. Symb. ID | | |||

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

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

0 1 2 3 | 0 1 2 3 | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

For instance, for m = 8, for B = 2^^8 - 1 (because the codec | For instance, for m = 8, for B = 2^^8 - 1 (because the codec | |||

operates on a finite field with 2^^8 elements) and if E = 1024 | operates on a finite field with 2^^8 elements), and if E = 1024 | |||

bytes, then the maximum transfer length is approximately equal to | bytes, then the maximum transfer length is approximately equal to | |||

2^^42 bytes (i.e., 4 Tera Bytes). Similarly, for m = 16, for B = | 2^^42 bytes (i.e., 4 terabytes). Similarly, for m = 16, for B = | |||

2^^16 - 1 and if E = 1024 bytes, then the maximum transfer length | 2^^16 - 1, and if E = 1024 bytes, then the maximum transfer length | |||

is also approximately equal to 2^^42 bytes. For larger objects, | is also approximately equal to 2^^42 bytes. For larger objects, | |||

another FEC scheme, with a larger Source Block Number field in the | another FEC scheme, with a larger Source Block Number field in the | |||

FEC Payload ID, could be defined. Another solution consists in | FEC Payload ID, could be defined. Another solution consists in | |||

fragmenting large objects into smaller objects, each of them | fragmenting large objects into smaller objects, each of them | |||

complying with the above limits. | complying with the above limits. | |||

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

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

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

skipping to change at page 11, line 49 | skipping to change at page 9, line 20 | |||

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

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

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

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

elements. | elements. | |||

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

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

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

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

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

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

parameter is communicated to the decoder, then this latter MUST | parameter is communicated to the decoder, then the latter MUST | |||

assume that G = 1. | assume that G = 1. | |||

o m: The m parameter is the length of the finite field elements, in | o m: The m parameter is the length of the finite field elements, in | |||

bits. It also characterizes the number of elements in the finite | bits. It also characterizes the number of elements in the finite | |||

field: q = 2^^m elements. The default value is m = 8. When no | field: q = 2^^m elements. The default value is m = 8. When no | |||

finite field size parameter is communicated to the decoder, then | finite field size parameter is communicated to the decoder, then | |||

this latter MUST assume that m = 8. | the latter MUST assume that m = 8. | |||

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 | mechanism is used (e.g., within the ALC [ALC] or NORM [NORM] | |||

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

[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 | Delivery Table) Instance of a FLUTE session [FLUTE], the following | |||

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

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

skipping to change at page 13, line 24 | skipping to change at page 10, line 47 | |||

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

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

following value: | following value: | |||

0 1 | 0 1 | |||

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

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

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

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

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

FDT Instance | FDT Instance | |||

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

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

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

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

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

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

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

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

During 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) that is 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 with 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, which focuses on | |||

special case of Reed-Solomon codes over GF(2^^8) and no encoding | the 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 refers 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 | |||

5.2.1. Mandatory Elements | 5.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 | |||

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

5.2.2. Common Elements | 5.2.2. Common Elements | |||

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

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

5.2.3. Scheme-Specific Elements | 5.2.3. Scheme-Specific Elements | |||

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

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 | mechanism is used (e.g., within the ALC [ALC] or NORM [NORM] | |||

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

[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 [draft-ietf-rmt-flute-revised], the following XML | a FLUTE session [FLUTE], the following XML attributes must be | |||

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

skipping to change at page 16, line 9 | skipping to change at page 13, line 16 | |||

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. The block | and 5. In case of FEC Encoding ID 5, m = 8 and G = 1. The block | |||

partitioning algorithm that is defined in section 9.1 of [RFC5052] | partitioning algorithm that is defined in Section 9.1 of [RFC5052] | |||

MUST be used with FEC Encoding IDs 2 and 5. | 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) * CR) | 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 | |||

skipping to change at page 17, line 26 | skipping to change at page 14, line 37 | |||

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 / CR); | 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. | |||

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

skipping to change at page 18, line 7 | skipping to change at page 15, line 21 | |||

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

It is RECOMMENDED that the "n-algorithm" be used by a sender, but | It is RECOMMENDED that the "n-algorithm" be used by a sender, but | |||

other algorithms remain possible to determine max_n and/or n. | other algorithms remain possible to determine max_n and/or n. | |||

At a receiver, the max_n value is extracted from the received FEC | At a receiver, the max_n value is extracted from the received FEC | |||

OTI. Since the Reed-Solomon decoder does not need to know the actual | OTI. Since the Reed-Solomon decoder does not need to know the actual | |||

n value, using the receiver part of the "n-algorithm" is not | n value, using the receiver part of the "n-algorithm" is not | |||

necessary from a decoding point of view. | necessary from a decoding point of view. | |||

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

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

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

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

uses the "n-algorithm", this receiver MAY use the receiver part of | 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 | 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 | 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 | Symbol ID superior or equal to the computed n value (e.g., it can | |||

choose to simply drop them). | 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) | Scheme (FEC Encoding ID 129) [RFC5445], this document assigns the FEC | |||

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

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

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

The FEC Instance ID 0 uses the Formats and Codes specified in | The FEC Instance ID 0 uses the Formats and Codes specified in | |||

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

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

algorithm defined in Section 9.1. of [RFC5052] to partition the | algorithm defined in Section 9.1 of [RFC5052] to partition the object | |||

object into source blocks. This FEC Scheme MAY also use another | into source blocks. This FEC scheme MAY also use another algorithm. | |||

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

source block dynamically, depending on some external criteria (e.g., | block dynamically, depending on some external criteria (e.g., to | |||

to adjust the FEC coding rate to the current loss rate experienced by | adjust the FEC coding rate to the current loss rate experienced by | |||

NORM receivers) and inform the CDP receivers of the current block | NORM receivers) and inform the CDP receivers of the current block | |||

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

scope of the current 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 | Sections 8.1 to 8.3 specify the [n,k]-RS codes when applied to m-bit | |||

m-bit elements, and Section 8.4 the use of [n,k]-RS codes when | elements, and Section 8.4 specifies 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. The use | |||

target of this specification. | described in Section 8.4 is the crux of this specification. | |||

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

refer to references [Rizzo97] and [MWS77]. | 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 that | |||

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

skipping to change at page 21, line 44 | skipping to change at page 17, line 44 | |||

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

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

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

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

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

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

RS code. | RS code. | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

skipping to change at page 22, line 51 | skipping to change at page 18, line 51 | |||

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

(log(k))^^2 + log(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 | matrix, which is such that any k*k-submatrix is invertible (see | |||

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

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

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

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

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

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

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

skipping to change at page 23, line 25 | skipping to change at page 19, line 25 | |||

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(k))^^2) ) then by V_{k,k} (multipoint | complexity O( k * (log(k))^^2) ) then by V_{k,k} (multipoint | |||

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

complexity is then O((log(k))^^2) 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 (including its symbol(s), | |||

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

location of the erased symbols in the sequence of symbols MUST be | erased. The location of the erased symbols in the sequence of | |||

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

codes for generating redundant symbols from the k source symbols and | of Reed-Solomon codes for generating redundant symbols from the k | |||

for recovering the source symbols from any set of k received symbols. | source symbols and 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 (this can | elements, they MUST be virtually padded with zero elements (this can | |||

be 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 u-th source vector, comprised of | of the source symbol set. A logical u-th source vector, comprised of | |||

the u-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 u-th encoding vector. This u-th encoding vector then | calculate a u-th encoding vector. This u-th encoding vector then | |||

provides the u-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 u 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 | |||

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

* | * | |||

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

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

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

Figure 7: Packet encoding scheme | Figure 7: Packet Encoding Scheme | |||

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

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

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

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

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

multiplications. | multiplications. | |||

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

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

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

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

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

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

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

skipping to change at page 27, line 22 | skipping to change at page 22, line 30 | |||

others target the Content Delivery Protocol (CDP) (e.g., to | others target the Content Delivery Protocol (CDP) (e.g., to | |||

compromise its normal behavior), and finally some attacks target the | compromise its normal behavior), and finally some attacks target the | |||

content itself. Since this document focuses on a FEC building block | content itself. Since this document focuses on a FEC building block | |||

independently of any particular CDP (even if ALC and NORM are two | independently of any particular CDP (even if ALC and NORM are two | |||

natural candidates), this section only discusses the additional | natural candidates), this section only discusses the additional | |||

threats that an arbitrary CDP may be exposed to when using this | threats that an arbitrary CDP may be exposed to when using this | |||

building block. | building block. | |||

More specifically, several kinds of attacks exist: | More specifically, several kinds of attacks exist: | |||

o those that are meant to give access to a confidential content | o those that are meant to give access to confidential content (e.g., | |||

(e.g., in case of a non-free content), | in case of non-free content), | |||

o those that try to corrupt the object being transmitted (e.g., to | o those that try to corrupt the object being transmitted (e.g., to | |||

inject malicious code within an object, or to prevent a receiver | inject malicious code within an object or to prevent a receiver | |||

from using an object), | from using an object), | |||

o and those that try to compromise the receiver's behavior (e.g., by | o and those that try to compromise the receiver's behavior (e.g., by | |||

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

9.2.1. Access to Confidential Objects | 9.2.1. Access to Confidential Objects | |||

Access control to the object being transmitted is typically provided | Access control to the object being transmitted is typically provided | |||

by means of encryption. This encryption can be done over the whole | by means of encryption. This encryption can be done over the whole | |||

object (e.g., by the content provider, before the FEC encoding | 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/ | process), or be done on a packet per-packet basis (e.g., when IPsec | |||

ESP is used [RFC4303]). If access control is a concern, it is | Encapsulating Security Payload (ESP) is used [RFC4303]). If access | |||

RECOMMENDED that one of these solutions be used. Even if we mention | control is a concern, it is RECOMMENDED that one of these solutions | |||

these attacks here, they are not related nor facilitated by the use | be used. Even if we mention these attacks here, they are not related | |||

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

9.2.2. Content Corruption | 9.2.2. Content Corruption | |||

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

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

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

level, but in that case a receiver has no way to identify which | 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. | symbol(s) are corrupted if the object is detected as corrupted. This | |||

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

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

recovered. Several techniques can provide this source | sometimes. 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), for instance by using RSASSA-PKCS1-v1_5 | public key cryptography), for instance by using RSASSA-PKCS1-v1_5 | |||

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

integrity, once this latter has been fully decoded. Even if | integrity, once the object has been fully decoded. Even if | |||

digital signatures are computationally expensive, this calculation | digital signatures are computationally expensive, this calculation | |||

occurs only once per 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 requires (unless Elliptic Curve Cryptography | that this solution requires (unless Elliptic Curve Cryptography | |||

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

avoid this problem, the signature may span a set of symbols | set of symbols (instead of a single one) in order to amortize the | |||

(instead of a single one) in order to amortize the signature | signature calculation. But if a single symbol is missing, the | |||

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

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

[RFC2104] scheme can be used, for instance by using HMAC-SHA-1 | [RFC2104] scheme can be used; for instance, by using HMAC-SHA-256 | |||

with a secret key shared by all the group members, senders and | with a secret key shared by all the group members (i.e., the | |||

receivers. This technique creates a cryptographically secured | sender(s) and receivers). Thanks to the secret key, this | |||

(thanks to the secret key) digest of a packet that is sent along | technique creates a cryptographically secured digest of a packet | |||

with the packet. The Group MAC scheme does not create prohibitive | that is sent along with the packet. The Group MAC scheme does not | |||

processing load nor transmission overhead, but it has a major | create prohibitive processing load nor transmission overhead, but | |||

limitation: it only provides a group authentication/integrity | it has a major limitation: it only provides a group | |||

service since all group members share the same secret group key, | authentication/integrity service since all group members share the | |||

which means that each member can send a forged packet. It is | same secret group key, which means that each member can send a | |||

therefore restricted to situations where group members are fully | forged packet. It is therefore restricted to situations where | |||

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

technique as a pre-check). | ||||

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

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

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

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

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

its reception; | 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, when used) require that public | TESLA during the bootstrap process, when used) require that public | |||

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

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

pre-distributing the public keys of each group member. | pre-distributing the public keys of each group member. | |||

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

It is up to the developer and deployer, who know the security | It is up to the developer and deployer, who know the security | |||

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

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

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

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

9.3. Attacks Against the FEC Parameters | 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, | |||

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

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

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

load while compromising decoding. | processing 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 in an EXT_FTI header | carrying the FEC parameters sent in-band in an EXT_FTI header | |||

extension SHOULD be protected by one of the per-packet techniques | extension SHOULD be protected by one of the per-packet techniques | |||

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

OTI is contained in an FDT Instance, this object SHOULD be protected, | OTI is contained in an FDT Instance, this FDT Instance object SHOULD | |||

for instance by digitally signing it with XML digital signatures | be protected, for instance, by digitally signing it with XML digital | |||

[RFC3275]. Finally, when FEC OTI is sent out-of-band (e.g., in a | signatures [RFC3275]. Finally, when FEC OTI is sent out-of-band | |||

session description) this latter SHOULD be protected, for instance by | (e.g., in a session description), this FEC OTI SHOULD be protected, | |||

digitally signing it. | for instance, by digitally signing the object that includes this FEC | |||

OTI. | ||||

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

skipping to change at page 31, line 8 | skipping to change at page 25, line 40 | |||

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

Francis Dupont, Elwyn Davies, Magnus Westerlund and Alfred Hoenes for | Francis Dupont, Elwyn Davies, Magnus Westerlund, and Alfred Hoenes | |||

their valuable comments. The authors also want to thank Luigi Rizzo | for their valuable comments. The authors also want to thank Luigi | |||

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

codec. | Solomon codec. | |||

12. References | 12. References | |||

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

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

Requirement Levels", RFC 2119. | Requirement Levels", BCP 14, RFC 2119, March 1997. | |||

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

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

Watson, M., "Basic Forward Error Correction (FEC) | Schemes", RFC 5445, March 2009. | |||

Schemes", | ||||

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

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

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

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

M., and J. Crowcroft, "The Use of Forward Error Correction | M., and J. Crowcroft, "The Use of Forward Error | |||

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

December 2002. | ||||

[RS-codec] | [RS-codec] Rizzo, L., "Reed-Solomon FEC codec", 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/", | mirrored at http://planete-bcast.inrialpes.fr/, revised | |||

July 1998. | version of July 1998. | |||

[Rizzo97] Rizzo, L., "Effective Erasure Codes for Reliable Computer | [Rizzo97] Rizzo, L., "Effective Erasure Codes for Reliable Computer | |||

Communication Protocols", ACM SIGCOMM Computer | Communication Protocols", ACM SIGCOMM Computer | |||

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

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

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

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

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

Roca, V., Neumann, C., and D. Furodet, "Low Density Parity | Parity Check (LDPC) Forward Error Correction", RFC 5170, | |||

Check (LDPC) Forward Error Correction", | June 2008. | |||

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

November 2007. | ||||

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

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

June 2007. | RFC 5053, October 2007. | |||

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

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

Layered Coding (ALC) Protocol Instantiation", | in Progress, November 2008. | |||

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

February 2007. | ||||

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

Adamson, B., Bormann, C., Handley, M., and J. Macker, | "NACK-Oriented Reliable Multicast Protocol", Work | |||

"Negative-acknowledgment (NACK)-Oriented Reliable | in Progress, March 2009. | |||

Multicast (NORM) Protocol", | ||||

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

March 2007. | ||||

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

Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, | Roca, "FLUTE - File Delivery over Unidirectional | |||

"FLUTE - File Delivery over Unidirectional Transport", | Transport", Work in Progress, September 2008. | |||

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

October 2007. | ||||

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

Standards (PKCS) #1: RSA Cryptography Specifications | Standards (PKCS) #1: RSA Cryptography Specifications | |||

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

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

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

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

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

[RFC4082] "Timed Efficient Stream Loss-Tolerant Authentication | [RFC4082] "Timed Efficient Stream Loss-Tolerant Authentication | |||

(TESLA): Multicast Source Authentication Transform | (TESLA): Multicast Source Authentication Transform | |||

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

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

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

March 2002. | RFC 3275, March 2002. | |||

Authors' Addresses | Authors' Addresses | |||

Jerome Lacan | Jerome Lacan | |||

ISAE/LAAS-CNRS | 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://pagespro.isae.fr/jerome-lacan/ | |||

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@inria.fr | EMail: vincent.roca@inria.fr | |||

URI: http://planete.inrialpes.fr/people/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://mad.cs.tut.fi/ | |||

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://mad.cs.tut.fi/ | |||

Full Copyright Statement | ||||

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

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

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

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

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

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

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

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

Copies of IPR disclosures made to the IETF Secretariat and any | ||||

assurances of licenses to be made available, or the result of an | ||||

attempt made to obtain a general license or permission for the use of | ||||

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

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

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

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

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

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

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

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

Acknowledgment | ||||

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

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

End of changes. 136 change blocks. | ||||

333 lines changed or deleted | | 314 lines changed or added | ||

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