draft-ietf-rmt-bb-fec-ldpc-06.txt | draft-ietf-rmt-bb-fec-ldpc-07.txt | |||
---|---|---|---|---|

RMT V. Roca | RMT V. Roca | |||

Internet-Draft INRIA | Internet-Draft INRIA | |||

Intended status: Experimental C. Neumann | Intended status: Standards Track C. Neumann | |||

Expires: November 8, 2007 Thomson Research | Expires: May 19, 2008 Thomson | |||

D. Furodet | D. Furodet | |||

STMicroelectronics | STMicroelectronics | |||

May 7, 2007 | November 16, 2007 | |||

Low Density Parity Check (LDPC) Staircase and Triangle Forward Error | Low Density Parity Check (LDPC) Staircase and Triangle Forward Error | |||

Correction (FEC) Schemes | Correction (FEC) Schemes | |||

draft-ietf-rmt-bb-fec-ldpc-06.txt | draft-ietf-rmt-bb-fec-ldpc-07.txt | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

This Internet-Draft will expire on November 8, 2007. | This Internet-Draft will expire on May 19, 2008. | |||

Copyright Notice | Copyright Notice | |||

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

Abstract | Abstract | |||

This document describes two Fully-Specified FEC Schemes, LDPC- | This document describes two Fully-Specified FEC Schemes, LDPC- | |||

Staircase and LDPC-Triangle, and their application to the reliable | Staircase and LDPC-Triangle, and their application to the reliable | |||

delivery of objects on packet erasure channels. These systematic FEC | delivery of data objects on the packet erasure channel (i.e., a | |||

communication path where packets are either received without any | ||||

corruption or discarded during transmission). These systematic FEC | ||||

codes belong to the well known class of ``Low Density Parity Check'' | codes belong to the well known class of ``Low Density Parity Check'' | |||

(LDPC) codes, and are large block FEC codes in the sense of RFC3453. | (LDPC) codes, and are large block FEC codes in the sense of RFC3453. | |||

Table of Contents | Table of Contents | |||

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

2. Requirements notation . . . . . . . . . . . . . . . . . . . . 5 | 2. Requirements notation . . . . . . . . . . . . . . . . . . . . 5 | |||

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

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

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

skipping to change at page 3, line 24 | skipping to change at page 2, line 34 | |||

4.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 8 | 4.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 8 | |||

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

4.2.1. Mandatory Element . . . . . . . . . . . . . . . . . . 8 | 4.2.1. Mandatory Element . . . . . . . . . . . . . . . . . . 8 | |||

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

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

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

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

5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 12 | 5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 12 | |||

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

5.3. Determining the Encoding Symbol Length (E) and Number | 5.3. Determining the Encoding Symbol Length (E) and Number | |||

of Encoding Symbols per Group (G) . . . . . . . . . . . . 13 | of Encoding Symbols per Group (G) . . . . . . . . . . . . 14 | |||

5.4. Determining the Number of Encoding Symbols of a Block . . 15 | 5.4. Determining the Maximum Number of Encoding Symbols | |||

5.5. Identifying the Symbols of an Encoding Symbol Group . . . 16 | Generated for Any Source Block (max_n) . . . . . . . . . . 15 | |||

5.6. Pseudo Random Number Generator . . . . . . . . . . . . . . 19 | 5.5. Determining the Number of Encoding Symbols of a Block | |||

6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 21 | (n) . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 | |||

6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 21 | 5.6. Identifying the G Symbols of an Encoding Symbol Group . . 16 | |||

6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 21 | 5.7. Pseudo Random Number Generator . . . . . . . . . . . . . . 20 | |||

6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 22 | 6. Full Specification of the LDPC-Staircase Scheme . . . . . . . 22 | |||

6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 23 | 6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 22 | |||

7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 24 | 6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 22 | |||

7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 24 | 6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 24 | |||

7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 24 | 6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 24 | |||

7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 24 | 7. Full Specification of the LDPC-Triangle Scheme . . . . . . . . 26 | |||

7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 25 | 7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 26 | |||

8. Security Considerations . . . . . . . . . . . . . . . . . . . 26 | 7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 26 | |||

9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27 | 7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 26 | |||

10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 28 | 7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 27 | |||

11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 29 | 8. Security Considerations . . . . . . . . . . . . . . . . . . . 28 | |||

11.1. Normative References . . . . . . . . . . . . . . . . . . . 29 | 8.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 28 | |||

11.2. Informative References . . . . . . . . . . . . . . . . . . 29 | 8.2. Attacks Against the Data Flow . . . . . . . . . . . . . . 28 | |||

Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 31 | 8.2.1. Access to Confidential Objects . . . . . . . . . . . . 28 | |||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 33 | 8.2.2. Content Corruption . . . . . . . . . . . . . . . . . . 29 | |||

Intellectual Property and Copyright Statements . . . . . . . . . . 34 | 8.3. Attacks Against the FEC Parameters . . . . . . . . . . . . 30 | |||

9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 31 | ||||

10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 32 | ||||

11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 33 | ||||

11.1. Normative References . . . . . . . . . . . . . . . . . . . 33 | ||||

11.2. Informative References . . . . . . . . . . . . . . . . . . 33 | ||||

Appendix A. Pseudo Random Number Generator Example | ||||

Implementation (Informative Only) . . . . . . . . . . 35 | ||||

Appendix B. Trivial Decoding Algorithm (Informative Only) . . . . 37 | ||||

Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 39 | ||||

Intellectual Property and Copyright Statements . . . . . . . . . . 40 | ||||

1. Introduction | 1. Introduction | |||

RFC 3453 [3] introduces large block FEC codes as an alternative to | [RFC3453] introduces large block FEC codes as an alternative to small | |||

small block FEC codes like Reed-Solomon. The main advantage of such | block FEC codes like Reed-Solomon. The main advantage of such large | |||

large block codes is the possibility to operate efficiently on source | block codes is the possibility to operate efficiently on source | |||

blocks of size several tens of thousands (or more) source symbols. | blocks of size several tens of thousands (or more) source symbols. | |||

The present document introduces the Fully-Specified FEC Encoding ID 3 | The present document introduces the Fully-Specified FEC Encoding ID 3 | |||

that is intended to be used with the LDPC-Staircase FEC codes, and | that is intended to be used with the LDPC-Staircase FEC codes, and | |||

the Fully-Specified FEC Encoding ID 4 that is intended to be used | the Fully-Specified FEC Encoding ID 4 that is intended to be used | |||

with the LDPC-Triangle FEC codes [6][9]. Both schemes belong to the | with the LDPC-Triangle FEC codes [RN04][MK03]. Both schemes belong | |||

broad class of large block codes. | to the broad class of large block codes. For a definition of the | |||

term Fully-Specified Scheme, see [RFC5052], section 4. | ||||

LDPC codes rely on a dedicated matrix, called a "Parity Check | LDPC codes rely on a dedicated matrix, called a "Parity Check | |||

Matrix", at the encoding and decoding ends. The parity check matrix | Matrix", at the encoding and decoding ends. The parity check matrix | |||

defines relationships (or constraints) between the various encoding | defines relationships (or constraints) between the various encoding | |||

symbols (i.e. source symbols and repair symbols), that are later used | symbols (i.e., source symbols and repair symbols), that are later | |||

by the decoder to reconstruct the original k source symbols if some | used by the decoder to reconstruct the original k source symbols if | |||

of them are missing. These codes are systematic, in the sense that | some of them are missing. These codes are systematic, in the sense | |||

the encoding symbols include the source symbols in addition to the | that the encoding symbols include the source symbols in addition to | |||

repair symbols. | the repair symbols. | |||

Since the encoder and decoder must operate on the same parity check | Since the encoder and decoder must operate on the same parity check | |||

matrix, information must be communicated between them as part of the | matrix, information must be communicated between them as part of the | |||

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

A publicly available reference implementation of these codes is | A publicly available reference implementation of these codes is | |||

available and distributed under a GNU/LGPL license [8]. | available and distributed under a GNU/LGPL license [LDPC-codec]. | |||

Besides, the code extracts included in this document (except | ||||

Appendix A that is only provided as an example) are directly | ||||

contributed to the IETF process by the authors of this document and | ||||

by Radford M. Neal. | ||||

2. Requirements notation | 2. Requirements notation | |||

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 [1]. | document are to be interpreted as described in [RFC2119]. | |||

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

3.1. Definitions | 3.1. Definitions | |||

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

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

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

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

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

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

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

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

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

the encoding process | ||||

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

the encoding symbols | ||||

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

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 object can be derived from a single Encoding Symbol ID. | source object can be derived from a single Encoding Symbol ID | |||

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

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

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

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

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

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

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

3.2. Notations | 3.2. Notations | |||

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

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

k denotes the source block length in symbols, i.e. the number of | k denotes the source block length in symbols, i.e., the number of | |||

source symbols of a source block | source symbols of a source block | |||

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

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

symbols generated for a source block | symbols generated for a source block | |||

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

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

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

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

be partitioned | be partitioned | |||

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

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

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

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

any source block | any source block. This is in particular the number of encoding | |||

symbols generated for a source block of size B | ||||

H denotes the parity check matrix | H denotes the parity check matrix | |||

srand(s) denotes the initialization function of the pseudo-random | srand(s) denotes the initialization function of the pseudo-random | |||

number generator, where s is the seed (s > 0) | number generator, where s is the seed (s > 0) | |||

rand(m) denotes a pseudo-random number generator that returns a | rand(m) denotes a pseudo-random number generator that returns a | |||

new random integer in [0; m-1] each time it is called | new random integer in [0; m-1] each time it is called | |||

3.3. Abbreviations | 3.3. Abbreviations | |||

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

ESI: Encoding Symbol ID | ESI: Encoding Symbol ID | |||

FEC OTI: FEC Object Transmission Information | FEC OTI: FEC Object Transmission Information | |||

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

The Encoding Symbol ID (20 bit field) identifies which encoding | The Encoding Symbol ID (20 bit field) identifies which encoding | |||

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

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

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

remaining n-k values (k to n-k-1) identify repair symbols. | remaining n-k values (k to n-k-1) identify repair symbols. | |||

There MUST be exactly one FEC Payload ID per packet. In case of an | There MUST be exactly one FEC Payload ID per packet. In case of an | |||

Encoding Symbol Group, when multiple encoding symbols are sent in the | Encoding Symbol Group, when multiple encoding symbols are sent in the | |||

same packet, the FEC Payload ID refers to the first symbol of the | same packet, the FEC Payload ID refers to the first symbol of the | |||

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

symbol thanks to a dedicated function, as explained in Section 5.5 | symbol thanks to a dedicated function, as explained in Section 5.6 | |||

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 | Encoding Symbol ID (20 bits) | | | Source Block Number | Encoding Symbol ID (20 bits) | | |||

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

Figure 1: FEC Payload ID encoding format for FEC Encoding ID 3 and 4 | Figure 1: FEC Payload ID encoding format for FEC Encoding ID 3 and 4 | |||

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

4.2.1. Mandatory Element | 4.2.1. Mandatory Element | |||

o FEC Encoding ID: the LDPC-Staircase and LDPC-Triangle Fully- | o FEC Encoding ID: the LDPC-Staircase and LDPC-Triangle Fully- | |||

Specified FEC Schemes use respectively the FEC Encoding ID 3 | Specified FEC Schemes use respectively the FEC Encoding ID 3 | |||

(Staircase) and 4 (Triangle). | (Staircase) and 4 (Triangle). | |||

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

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

maximum transfer length = 2^^12 * B * E | maximum transfer length = 2^^12 * B * E | |||

For instance, if B=2^^19 (because of a code rate of 1/2, | For instance, if B=2^^19 (because of a code rate of 1/2, | |||

Section 5.2), and if E=1024 bytes, then the maximum transfer | Section 5.2), and if E=1024 bytes, then the maximum transfer | |||

length is 2^^41 bytes (or 2 TB). The upper limit, with symbols of | length is 2^^41 bytes (or 2 TB). The upper limit, with symbols of | |||

skipping to change at page 9, line 34 | skipping to change at page 9, line 34 | |||

max_n value. In particular max_n is at most equal to 2^^20. | max_n value. In particular max_n is at most equal to 2^^20. | |||

Section 5 explains how to define the values of each of these | Section 5 explains how to define the values of each of these | |||

elements. | elements. | |||

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

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

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 (i.e. per packet). The default value is 1, | symbols per group (i.e., per packet). The default value is 1, | |||

meaning that each packet contains exactly one symbol. Values | meaning that each packet contains exactly one symbol. Values | |||

greater than 1 can also be defined, as explained in Section 5.3. | greater than 1 can also be defined, as explained in Section 5.3. | |||

o PRNG seed: the seed is a 32 bit unsigned integer between 1 and | o PRNG seed: the seed is a 32 bit unsigned integer between 1 and | |||

0x7FFFFFFE (i.e. 2^^31-2) inclusive. This value is used to | 0x7FFFFFFE (i.e., 2^^31-2) inclusive. This value is used to | |||

initialize the Pseudo Random Number Generator (Section 5.6). This | initialize the Pseudo Random Number Generator (Section 5.7). | |||

element is optional. Whether or not it is present in the FEC OTI | ||||

is signaled in the associated encoding format through an | ||||

appropriate mechanism (Section 4.2.4). When the PRNG seed is not | ||||

carried within the FEC OTI, it is assumed that encoder and | ||||

decoders use another way to communicate the information, or use a | ||||

fixed, predefined value. | ||||

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

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

OTI. The present document does not specify when or how these | OTI. The present document does not specify when or how these | |||

encoding formats should be used. | encoding formats 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 [13] or NORM [15] protocols). | mechanism is used (e.g., within the ALC | |||

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

[draft-ietf-rmt-pi-norm-revised] protocols). | ||||

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

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

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

| HET = 64 | HEL (=4 or 5) | | | | HET = 64 | HEL = 5 | | | |||

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

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

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

| Encoding Symbol Length (E) | G | B (MSB) | | | Encoding Symbol Length (E) | G | B (MSB) | | |||

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

| B (LSB) | Max Nb of Enc. Symbols (max_n) | | | B (LSB) | Max Nb of Enc. Symbols (max_n) | | |||

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

. Optional PRNG seed . | | PRNG seed | | |||

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

Figure 2: EXT_FTI Header for FEC Encoding ID 3 and 4. | Figure 2: EXT_FTI Header for FEC Encoding ID 3 and 4. | |||

In particular: | In particular: | |||

o The HEL (Header Extension Length) indicates whether the optional | ||||

PRNG seed is present (HEL=5) or not (HEL=4). | ||||

o The Transfer-Length (L) field size (48 bits) is larger than the | o The Transfer-Length (L) field size (48 bits) is larger than the | |||

size required to store the maximum transfer length (Section 4.2.2) | size required to store the maximum transfer length (Section 4.2.2) | |||

for field alignment purposes. | for field alignment purposes. | |||

o The Maximum-Source-Block-Length (B) field (20 bits) is split into | o The Maximum-Source-Block-Length (B) field (20 bits) is split into | |||

two parts: the 8 most significant bits (MSB) are in the third 32- | two parts: the 8 most significant bits (MSB) are in the third 32- | |||

bit word of the EXT_FTI, and the remaining 12 least significant | bit word of the EXT_FTI, and the remaining 12 least significant | |||

bits (LSB) are in the fourth 32-bit word. | bits (LSB) are in the fourth 32-bit word. | |||

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

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

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

for the associated object: | attributes must be described for the associated object: | |||

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

o FEC-OTI-Transfer-length | o FEC-OTI-Transfer-length | |||

o FEC-OTI-Encoding-Symbol-Length | o FEC-OTI-Encoding-Symbol-Length | |||

o FEC-OTI-Maximum-Source-Block-Length | o FEC-OTI-Maximum-Source-Block-Length | |||

o FEC-OTI-Max-Number-of-Encoding-Symbols | o FEC-OTI-Max-Number-of-Encoding-Symbols | |||

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

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

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

following value: | following value: | |||

skipping to change at page 11, line 25 | skipping to change at page 11, line 18 | |||

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

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

| PRNG seed | | | PRNG seed | | |||

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

| G | | | G | | |||

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

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

FDT Instance for FEC Encoding ID 3 and 4. | FDT Instance for FEC Encoding ID 3 and 4. | |||

When no PRNG seed is to be carried in the FEC OTI, the seed field | During Base64 encoding, the 5 bytes of the FEC OTI Scheme Specific | |||

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

seed field contains a valid value as explained in Section 4.2.3. | ||||

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

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

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

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

5. Procedures | 5. Procedures | |||

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

and 4. | and 4. | |||

5.1. General | 5.1. General | |||

The B (maximum source block length in symbols) and E (encoding symbol | The B (maximum source block length in symbols), E (encoding symbol | |||

length in bytes) parameters are first determined, as explained in the | length in bytes) and G (number of encoding symbols per group) | |||

following sections. | parameters are first determined. The algorithms of Section 5.2 and | |||

Section 5.3 MAY be used to that purpose. Using other algorithms is | ||||

possible without compromising interoperability since the B, E and G | ||||

parameters are communicated to the receiver by means of the FEC OTI. | ||||

The source object is then partitioned using the block partitioning | Then, the source object MUST be partitioned using the block | |||

algorithm specified in [2]. To that purpose, the B, L (object | partitioning algorithm specified in [RFC5052]. To that purpose, the | |||

transfer length in bytes), and E arguments are provided. As a | B, L (object transfer length in bytes), and E arguments are provided. | |||

result, the object is partitioned into N source blocks. These blocks | As a result, the object is partitioned into N source blocks. These | |||

are numbered consecutively from 0 to N-1. The first I source blocks | blocks are numbered consecutively from 0 to N-1. The first I source | |||

consist of A_large source symbols, the remaining N-I source blocks | blocks consist of A_large source symbols, the remaining N-I source | |||

consist of A_small source symbols. Each source symbol is E bytes in | blocks consist of A_small source symbols. Each source symbol is E | |||

length, except perhaps the last symbol which may be shorter. | bytes in length, except perhaps the last symbol which may be shorter. | |||

For each block the actual number of encoding symbols is determined, | Then, the max_n (maximum number of encoding symbols generated for any | |||

as explained in the following section. | source block) parameter is determined. The algorithm of Section 5.4 | |||

MAY be used to that purpose. Using another algorithm is possible | ||||

without compromising interoperability since the max_n parameter is | ||||

communicated to the receiver by means of the FEC OTI. | ||||

For each block, the actual number of encoding symbols, n, MUST then | ||||

be determined using the "n-algorithm" detailed in Section 5.5. | ||||

Then, FEC encoding and decoding can be done block per block, | Then, FEC encoding and decoding can be done block per block, | |||

independently. To that purpose, a parity check matrix is created, | independently. To that purpose, a parity check matrix is created, | |||

that forms a system of linear equations between the source and repair | that forms a system of linear equations between the source and repair | |||

symbols of a given block, where the basic operator is XOR. | symbols of a given block, where the basic operator is XOR. | |||

This parity check matrix is logically divided into two parts: the | This parity check matrix is logically divided into two parts: the | |||

left side (from column 0 to k-1) which describes the occurrence of | left side (from column 0 to k-1) describes the occurrences of each | |||

each source symbol in the equation system; and the right side (from | source symbol in the system of linear equations; the right side (from | |||

column k to n-1) which describes the occurrence of each repair symbol | column k to n-1) describes the occurrences of each repair symbol in | |||

in the equation system. An entry (a "1") in the matrix at position | the system of linear equations. The only difference between the | |||

(i,j) (i.e. at row i and column j) means that the symbol with ESI i | LDPC-Staircase and LDPC-Triangle schemes is the construction of this | |||

appears in equation j of the system. The only difference between the | right sub-matrix. An entry (a "1") in the matrix at position (i,j) | |||

LDPC-Staircase and LDPC-Triangle schemes is the construction of the | (i.e., at row i and column j) means that the symbol with ESI j | |||

right sub-matrix. | appears in equation i of the system. | |||

When the parity symbols have been created, the sender will transmit | When the parity symbols have been created, the sender transmits | |||

source and parity symbols. The way this transmission occurs can | source and parity symbols. The way this transmission occurs can | |||

largely impact the erasure recovery capabilities of the LDPC-* FEC. | largely impact the erasure recovery capabilities of the LDPC-* FEC. | |||

In particular, sending parity symbols in sequence is suboptimal. | In particular, sending parity symbols in sequence is suboptimal. | |||

Instead it is usually recommended the shuffle these symbols. The | Instead it is usually recommended the shuffle these symbols. The | |||

interested reader will find more details in [7]. | interested reader will find more details in [NRFF05]. | |||

The following sections detail how the B, E, and n parameters are | The following sections detail how the B, E, G, max_nand n parameters | |||

determined (respectively in Section 5.2, Section 5.3 and | are determined (respectively in Section 5.2, Section 5.3, Section 5.4 | |||

Section 5.4), how encoding symbol groups are created (Section 5.5), | and Section 5.5), how encoding symbol groups are created | |||

and finally specify the PRNG (Section 5.6). | (Section 5.6), and finally Section 5.7 details the PRNG. | |||

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

The B parameter (maximum source block length in symbols) depends on | The B parameter (maximum source block length in symbols) depends on | |||

several parameters: the code rate (rate), the Encoding Symbol ID | several parameters: the code rate (CR), the Encoding Symbol ID field | |||

field length of the FEC Payload ID (20 bits), as well as possible | length of the FEC Payload ID (20 bits), as well as possible internal | |||

internal codec limitations. | codec limitations. | |||

The B parameter cannot be larger than the following values, derived | The B parameter cannot be larger than the following values, derived | |||

from the FEC Payload ID limitations, for a given code rate: | from the FEC Payload ID limitations, for a given code rate: | |||

max1_B = 2^^(20 - ceil(Log2(1/rate))) | max1_B = 2^^(20 - ceil(Log2(1/CR))) | |||

Some common max1_B values are: | Some common max1_B values are: | |||

o rate == 1 (no repair symbol): max1_B = 2^^20 = 1,048,576 | o CR == 1 (no repair symbol): max1_B = 2^^20 = 1,048,576 | |||

o 1/2 <= rate < 1: max1_B = 2^^19 = 524,288 symbols | o 1/2 <= CR < 1: max1_B = 2^^19 = 524,288 symbols | |||

o 1/4 <= rate < 1/2: max1_B = 2^^18 = 262,144 symbols | o 1/4 <= CR < 1/2: max1_B = 2^^18 = 262,144 symbols | |||

o 1/8 <= rate < 1/4: max1_B = 2^^17 = 131,072 symbols | o 1/8 <= CR < 1/4: max1_B = 2^^17 = 131,072 symbols | |||

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

block size. This is the case for instance when the codec uses | block size. For instance, this is the case when the codec uses | |||

internally 16 bit unsigned integers to store the Encoding Symbol ID, | internally 16 bit unsigned integers to store the Encoding Symbol ID, | |||

since it does not enable to store all the possible values of a 20 bit | since it does not enable to store all the possible values of a 20 bit | |||

field. In that case, if for instance 1/2 <= rate < 1, then the | field. In that case, if for instance 1/2 <= CR < 1, then the maximum | |||

maximum source block length is 2^^15. Other limitations may also | source block length is 2^^15. Other limitations may also apply, for | |||

apply, for instance because of a limited working memory size. This | instance because of a limited working memory size. This decision | |||

decision MUST be clarified at implementation time, when the target | MUST be clarified at implementation time, when the target use case is | |||

use case is known. This results in a max2_B limitation. | known. This results in a max2_B limitation. | |||

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

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

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

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

5.3. Determining the Encoding Symbol Length (E) and Number of Encoding | 5.3. Determining the Encoding Symbol Length (E) and Number of Encoding | |||

Symbols per Group (G) | Symbols per Group (G) | |||

The E parameter usually depends on the maximum transmission unit on | The E parameter usually depends on the maximum transmission unit on | |||

the path (PMTU) from the source to the receivers. In order to | the path (PMTU) from the source to each receiver. In order to | |||

minimize the protocol header overhead (e.g. the LCT/UDP/IPv4 or IPv6 | minimize the protocol header overhead (e.g., the LCT/UDP/IPv4 or IPv6 | |||

headers in case of ALC), E is chosen as large as possible. In that | headers in case of ALC), E is chosen as large as possible. In that | |||

case, E is chosen so that the size of a packet composed of a single | case, E is chosen so that the size of a packet composed of a single | |||

symbol (G=1) remains below but close to the PMTU. | symbol (G=1) remains below but close to the PMTU. | |||

However other considerations can exist. For instance, the E | However other considerations can exist. For instance, the E | |||

parameter can be made a function of the object transfer length. | parameter can be made a function of the object transfer length. | |||

Indeed, LDPC codes are known to offer better protection for large | Indeed, LDPC codes are known to offer better protection for large | |||

blocks. In case of small objects, it can be advantageous to reduce | blocks. In case of small objects, it can be advantageous to reduce | |||

the encoding symbol length (E) in order to artificially increase the | the encoding symbol length (E) in order to artificially increase the | |||

number of symbols, and therefore the block size. | number of symbols, and therefore the block size. | |||

In order to minimize the protocol header overhead, several symbols | In order to minimize the protocol header overhead, several symbols | |||

can be grouped in the same Encoding Symbol Group (i.e. G > 1). | can be grouped in the same Encoding Symbol Group (i.e., G > 1). | |||

Depending on how many symbols are grouped (G) and on the packet loss | Depending on how many symbols are grouped (G) and on the packet loss | |||

rate (G symbols are lost for each packet erasure), this strategy | rate (G symbols are lost for each packet erasure), this strategy | |||

might or might not be appropriate. A balance must therefore be | might or might not be appropriate. A balance must therefore be | |||

found. | found. | |||

The current specification does not mandate any value for either E or | The current specification does not mandate any value for either E or | |||

G. The current specification only provides an example of possible | G. The current specification only provides an example of possible | |||

choices for E and G. Note that this choice is done by the sender. | choices for E and G. Note that this choice is done by the sender, and | |||

Then the E and G parameters are communicated to the receivers thanks | the E and G parameters are then communicated to the receiver thanks | |||

to the FEC OTI. | to the FEC OTI. Note also that the decoding algorithm used | |||

influences the choice of the E and G parameters. Indeed, increasing | ||||

the number of symbols will negatively impact the processing load when | ||||

decoding is based (in part or totally) on Gaussian elimination, | ||||

whereas the impacts will be rather low when decoding is based on the | ||||

trivial algorithm sketched in Section 6.4. | ||||

Example: | Example: | |||

First define the target packet payload size, pkt_sz (at most equal to | Let us assume that the trivial decoding algorithm sketched in | |||

the PMTU minus the size of the various protocol headers). The pkt_sz | Section 6.4 is used. First define the target packet payload size, | |||

must be chosen in such a way that the symbol size is an integer. | pkt_sz (at most equal to the PMTU minus the size of the various | |||

This can require that pkt_sz be a multiple of 4, 8 or 16 (see the | protocol headers). The pkt_sz must be chosen in such a way that the | |||

table below). Then calculate the number of packets in the object: | symbol size is an integer. This can require that pkt_sz be a | |||

nb_pkts = ceil(L / pkt_sz). Finally, thanks to nb_pkts, use the | multiple of 4, 8 or 16 (see the table below). Then calculate the | |||

following table to find a possible G value. | number of packets in the object: nb_pkts = ceil(L / pkt_sz). | |||

Finally, thanks to nb_pkts, use the following table to find a | ||||

possible G value. | ||||

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

| Number of packets | G | Symbol size | k | | | Number of packets | G | Symbol size | k | | |||

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

| 4000 <= nb_pkts | 1 | pkt_sz | 4000 <= k | | | 4000 <= nb_pkts | 1 | pkt_sz | 4000 <= k | | |||

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

| 1000 <= nb_pkts < 4000 | 4 | pkt_sz / 4 | 4000 <= k < 16000 | | | 1000 <= nb_pkts < 4000 | 4 | pkt_sz / 4 | 4000 <= k < 16000 | | |||

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

| 500 <= nb_pkts < 1000 | 8 | pkt_sz / 8 | 4000 <= k < 8000 | | | 500 <= nb_pkts < 1000 | 8 | pkt_sz / 8 | 4000 <= k < 8000 | | |||

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

| 1 <= nb_pkts < 500 | 16 | pkt_sz / 16 | 16 <= k < 8000 | | | 1 <= nb_pkts < 500 | 16 | pkt_sz / 16 | 16 <= k < 8000 | | |||

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

5.4. Determining the Number of Encoding Symbols of a Block | 5.4. Determining the Maximum Number of Encoding Symbols Generated for | |||

Any Source Block (max_n) | ||||

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

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

AT A SENDER: | The following algorithm MAY be used by a sender to determine the | |||

maximum number of encoding symbols generated for any source block | ||||

(max_n) as a function of B and the target code rate. Since the max_n | ||||

parameter is communicated to the decoder by means of the FEC OTI, | ||||

another method MAY be used to determine max_n. | ||||

Input: | Input: | |||

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

explains how to determine its value. | MAY be used to determine its value. | |||

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

source blocking algorithm. | ||||

rate: FEC code rate. It is provided by the user, for instance | CR: FEC code rate, which is provided by the user (e.g., when | |||

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

floating point value. The rate value must be such that the | floating point value. The CR value must be such that the | |||

resulting number of encoding symbols per block is at most equal to | resulting number of encoding symbols per block is at most equal to | |||

2^^20 (Section 4.1). | 2^^20 (Section 4.1). | |||

Output: | Output: | |||

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

block | block. | |||

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

Algorithm: | Algorithm: | |||

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

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

(NB: if B has been defined as explained in Section 5.2, this error | (NB: if B has been defined as explained in Section 5.2, this error | |||

should never happen) | should never happen) | |||

n = floor(k * max_n / B); | 5.5. Determining the Number of Encoding Symbols of a Block (n) | |||

AT A RECEIVER: | The following algorithm, also called "n-algorithm", MUST be used by | |||

the sender and the receiver to determine the number of encoding | ||||

symbols for a given block (n) as a function of B, k, and max_n. | ||||

Input: | Input: | |||

B: Extracted from the received FEC OTI | B: Maximum source block length, for any source block. At a | |||

sender, Section 5.2 MAY be used to determine its value. At a | ||||

receiver, this value MUST be extracted from the received FEC OTI. | ||||

max_n: Extracted from the received FEC OTI | k: Current source block length. At a sender or receiver, the | |||

k: Given by the source blocking algorithm | block partitioning algorithm MUST be used to determine its value. | |||

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

block. At a sender, Section 5.4 MAY be used to determine its | ||||

value. At a receiver, this value MUST be extracted from the | ||||

received FEC OTI. | ||||

Output: | Output: | |||

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

Algorithm: | Algorithm: | |||

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

5.5. Identifying the Symbols of an Encoding Symbol Group | 5.6. Identifying the G Symbols of an Encoding Symbol Group | |||

When multiple encoding symbols are sent in the same packet, the FEC | When multiple encoding symbols are sent in the same packet, the FEC | |||

Payload ID information of the packet MUST refer to the first encoding | Payload ID information of the packet MUST refer to the first encoding | |||

symbol. It MUST then be possible to identify each symbol from this | symbol. It MUST then be possible to identify each symbol from this | |||

single FEC Payload ID. To that purpose, the symbols of an Encoding | single FEC Payload ID. To that purpose, the symbols of an Encoding | |||

Symbol Group (i.e. packet): | Symbol Group (i.e. packet): | |||

o MUST all be either source symbols, or repair symbols. Therefore | o MUST all be either source symbols, or repair symbols. Therefore | |||

only source packets and repair packets are permitted, not mixed | only source packets and repair packets are permitted, not mixed | |||

ones. | ones. | |||

o are identified by a function, sender(resp. | o are identified by a function, sender(resp. | |||

receiver)_find_ESIs_of_group(), that takes as argument: | receiver)_find_ESIs_of_group(), that takes as argument: | |||

* for a sender, the index of the Encoding Symbol Group (i.e. | * for a sender, the index of the Encoding Symbol Group (i.e., | |||

packet) that the application wants to create, | packet) that the application wants to create, | |||

* for a receiver, the ESI information contained in the FEC | * for a receiver, the ESI information contained in the FEC | |||

Payload ID. | Payload ID. | |||

and returns a list of G Encoding Symbol IDs. In case of a source | and returns a list of G Encoding Symbol IDs. In case of a source | |||

packet, the G Encoding Symbol IDs are chosen consecutively, by | packet, the G Encoding Symbol IDs are chosen consecutively, by | |||

incrementing the ESI. In case of a repair packet, the G repair | incrementing the ESI. In case of a repair packet, the G repair | |||

symbols are chosen randomly, as explained below. | symbols are chosen randomly, as explained below. | |||

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

void | void | |||

initialize_tables () | initialize_tables () | |||

{ | { | |||

int i; | int i; | |||

int randInd; | int randInd; | |||

int backup; | int backup; | |||

txseqToID = malloc((n-k) * sizeof(int)); | txseqToID = malloc((n-k) * sizeof(int)); | |||

IDtoTxseq = malloc((n-k) * sizeof(int)); | IDtoTxseq = malloc((n-k) * sizeof(int)); | |||

/* initialize the two tables that map ID | /* initialize the two tables that map ID | |||

* (i.e. ESI-k) to/from TxSequence. */ | * (i.e., ESI-k) to/from TxSequence. */ | |||

for (i = 0; i < n - k; i++) { | for (i = 0; i < n - k; i++) { | |||

IDtoTxseq[i] = i; | IDtoTxseq[i] = i; | |||

txseqToID[i] = i; | txseqToID[i] = i; | |||

} | } | |||

/* now randomize everything */ | /* now randomize everything */ | |||

for (i = 0; i < n - k; i++) { | for (i = 0; i < n - k; i++) { | |||

randInd = rand(n - k); | randInd = rand(n - k); | |||

backup = IDtoTxseq[i]; | backup = IDtoTxseq[i]; | |||

IDtoTxseq[i] = IDtoTxseq[randInd]; | IDtoTxseq[i] = IDtoTxseq[randInd]; | |||

IDtoTxseq[randInd] = backup; | IDtoTxseq[randInd] = backup; | |||

skipping to change at page 18, line 37 | skipping to change at page 19, line 37 | |||

for (i = 0; i < G; i++) { | for (i = 0; i < G; i++) { | |||

ESIs[i] = | ESIs[i] = | |||

k + | k + | |||

txseqToID[(i + (PktIdx - nbSourcePkts) * G) | txseqToID[(i + (PktIdx - nbSourcePkts) * G) | |||

% (n - k)]; | % (n - k)]; | |||

} | } | |||

} | } | |||

return; | return; | |||

} | } | |||

Similarly, upon receiving an Encoding Symbol Group (i.e. packet), a | Similarly, upon receiving an Encoding Symbol Group (i.e., packet), a | |||

receiver can determine the sequence of G Encoding Symbol IDs from the | receiver can determine the sequence of G Encoding Symbol IDs from the | |||

first ESI, esi0, that is contained in the FEC Payload ID. | first ESI, esi0, that is contained in the FEC Payload ID. | |||

/* | /* | |||

* Determine the sequence of ESIs for the packet received. | * Determine the sequence of ESIs for the packet received. | |||

* Warning: use only when G > 1. | * Warning: use only when G > 1. | |||

* esi0 (IN): : ESI contained in the FEC Payload ID | * esi0 (IN): : ESI contained in the FEC Payload ID | |||

* ESIs[] (OUT): list of ESIs for the packet | * ESIs[] (OUT): list of ESIs for the packet | |||

*/ | */ | |||

void | void | |||

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

/* this is a repair packet */ | /* this is a repair packet */ | |||

for (i = 0; i < G; i++) { | for (i = 0; i < G; i++) { | |||

ESIs[i] = | ESIs[i] = | |||

k + | k + | |||

txseqToID[(i + IDtoTxseq[esi0 - k]) | txseqToID[(i + IDtoTxseq[esi0 - k]) | |||

% (n - k)]; | % (n - k)]; | |||

} | } | |||

} | } | |||

} | } | |||

5.6. Pseudo Random Number Generator | 5.7. Pseudo Random Number Generator | |||

The present FEC Encoding ID relies on a pseudo-random number | The FEC Encoding IDs 3 and 4 rely on a pseudo-random number generator | |||

generator (PRNG) that must be fully specified, in particular in order | (PRNG) that must be fully specified, in particular in order to enable | |||

to enable the receivers and the senders to build the same parity | the receivers and the senders to build the same parity check matrix. | |||

check matrix. The minimal standard generator [10] is used. It | ||||

defines a simple multiplicative congruential algorithm: Ij+1 = A * Ij | ||||

(modulo M), with the following choices: A = 7^^5 = 16807 and M = | ||||

2^^31 - 1 = 2147483647. Several implementations of this PRNG are | ||||

known and discussed in the literature. All of them provide the same | ||||

sequence of pseudo random numbers. A validation criteria of such a | ||||

PRNG is the following: if seed = 1, then the 10,000th value returned | ||||

MUST be equal to 1043618065. | ||||

The following implementation uses the Park and Miller algorithm with | The minimal standard generator [PM88] MUST be used. It defines a | |||

the optimization suggested by D. Carta in [11]. | simple multiplicative congruential algorithm: Ij+1 = A * Ij (modulo | |||

M), with the following choices: A = 7^^5 = 16807 and M = 2^^31 - 1 = | ||||

2147483647. Several implementations of this PRNG are known and | ||||

discussed in the literature. All of them provide the same sequence | ||||

of pseudo random numbers. A validation criteria of such a PRNG is | ||||

the following: if seed = 1, then the 10,000th value returned MUST be | ||||

equal to 1043618065. | ||||

unsigned long seed; | An optimized implementation of this algorithm, using only 32 bit | |||

mathematics which does not require any division, is provided, as an | ||||

example, in Appendix A. Yet any other implementation of the PRNG | ||||

algorithm that matches the above validation criteria is appropriate. | ||||

/* | This PRNG produces a 31 bit value between 1 and 0x7FFFFFFE (2^^31-2) | |||

* Initialize the PRNG with a seed between | inclusive. When it is desired to scale the pseudo random number | |||

* 1 and 0x7FFFFFFE (i.e. 2^^31-2) inclusive. | between 0 and maxv-1 inclusive, one must keep the most significant | |||

*/ | bits of the value returned by the PRNG (the least significant bits | |||

void srand (unsigned long s) | are known to be less random and modulo based solutions should be | |||

{ | avoided [PTVF92]). The following algorithm MUST be used: | |||

if ((s > 0) && (s < 0x7FFFFFFF)) | ||||

seed = s; | ||||

else | ||||

exit(-1); | ||||

} | ||||

/* | Input: | |||

* Returns a random integer in [0; maxv-1] | ||||

* Derived from rand31pmc, Robin Whittle, | ||||

* September 20th, 2005. | ||||

* http://www.firstpr.com.au/dsp/rand31/ | ||||

* 16807 multiplier constant (7^^5) | ||||

* 0x7FFFFFFF modulo constant (2^^31-1) | ||||

* The inner PRNG produces a value between 1 and | ||||

* 0x7FFFFFFE (2^^31-2) inclusive. | ||||

* This value is then scaled between 0 and maxv-1 | ||||

* inclusive. | ||||

*/ | ||||

unsigned long | ||||

rand (unsigned long maxv) | ||||

{ | ||||

unsigned long hi, lo; | ||||

lo = 16807 * (seed & 0xFFFF); | raw_value: random integer generated by the inner PRNG algorithm, | |||

hi = 16807 * (seed >> 16); /* binary shift to right */ | between 1 and 0x7FFFFFFE (2^^31-2) inclusive. | |||

lo += (hi & 0x7FFF) < < 16; /* binary shift to left */ | ||||

lo += hi >> 15; | maxv: upper bound used during the scaling operation. | |||

if (lo > 0x7FFFFFFF) | ||||

lo -= 0x7FFFFFFF; | Output: | |||

seed = (long)lo; | ||||

/* don't use modulo, least significant bits are less random | scaled_value: random integer between 0 and maxv-1 inclusive. | |||

* than most significant bits [Numerical Recipes in C] */ | ||||

return ((unsigned long) | Algorithm: | |||

((double)seed * (double)maxv / (double)0x7FFFFFFF)); | ||||

} | scaled_value = (unsigned long) ((double)maxv * (double)raw_value / | |||

(double)0x7FFFFFFF); | ||||

(NB: the above C type casting to unsigned long is equivalent to | ||||

using floor() with positive floating point values) | ||||

6. Full Specification of the LDPC-Staircase Scheme | 6. Full Specification of the LDPC-Staircase Scheme | |||

6.1. General | 6.1. General | |||

The LDPC-Staircase scheme is identified by the Fully-Specified FEC | The LDPC-Staircase scheme is identified by the Fully-Specified FEC | |||

Encoding ID 3. | Encoding ID 3. | |||

The PRNG used by the LDPC-Staircase scheme must be initialized by a | The PRNG used by the LDPC-Staircase scheme must be initialized by a | |||

seed. This PRNG seed is an optional instance-specific FEC OTI | seed. This PRNG seed is an instance-specific FEC OTI attribute | |||

attribute (Section 4.2.3). When this PRNG seed is not carried within | (Section 4.2.3). | |||

the FEC OTI, it is assumed that encoder and decoders either use | ||||

another way to communicate the seed value or use a fixed, predefined | ||||

value. | ||||

6.2. Parity Check Matrix Creation | 6.2. Parity Check Matrix Creation | |||

The LDPC-Staircase matrix can be divided into two parts: the left | The LDPC-Staircase matrix can be divided into two parts: the left | |||

side of the matrix defines in which equations the source symbols are | side of the matrix defines in which equations the source symbols are | |||

involved; the right side of the matrix defines in which equations the | involved; the right side of the matrix defines in which equations the | |||

repair symbols are involved. | repair symbols are involved. | |||

The left side is generated with the following algorithm: | The left side is generated with the following algorithm: | |||

/* | ||||

* Derived from: "Software for Low Density Parity Check Codes" | ||||

* Version of 2001-11-18, Radford M. Neal, Univ. of Toronto. | ||||

* Copyright (c) 1995, 1996, 2000, 2001 by Radford M. Neal | ||||

* http://www.cs.toronto.edu/~radford/ldpc.software.html | ||||

*/ | ||||

/* initialize a list of all possible choices in order to | /* initialize a list of all possible choices in order to | |||

* guarantee a homogeneous "1" distribution */ | * guarantee a homogeneous "1" distribution */ | |||

for (h = 3*k-1; h >= 0; h--) { | for (h = 3*k-1; h >= 0; h--) { | |||

u[h] = h % (n-k); | u[h] = h % (n-k); | |||

} | } | |||

/* left limit within the list of possible choices, u[] */ | /* left limit within the list of possible choices, u[] */ | |||

t = 0; | t = 0; | |||

for (j = 0; j < k; j++) { /* for each source symbol column */ | for (j = 0; j < k; j++) { /* for each source symbol column */ | |||

for (h = 0; h < 3; h++) { /* add 3 "1s" */ | for (h = 0; h < 3; h++) { /* add 3 "1s" */ | |||

skipping to change at page 22, line 24 | skipping to change at page 23, line 44 | |||

matrix_insert_entry(i, j); | matrix_insert_entry(i, j); | |||

} | } | |||

} | } | |||

} | } | |||

/* Add extra bits to avoid rows with less than two "1s". | /* Add extra bits to avoid rows with less than two "1s". | |||

* This is needed when the code rate is smaller than 2/5. */ | * This is needed when the code rate is smaller than 2/5. */ | |||

for (i = 0; i < n-k; i++) { /* for each row */ | for (i = 0; i < n-k; i++) { /* for each row */ | |||

if (degree_of_row(i) == 0) { | if (degree_of_row(i) == 0) { | |||

j = rand(k); | j = rand(k); | |||

e = matrix_insert_entry(i, j); | matrix_insert_entry(i, j); | |||

} | } | |||

if (degree_of_row(i) == 1) { | if (degree_of_row(i) == 1) { | |||

do { | do { | |||

j = rand(k); | j = rand(k); | |||

} while (matrix_has_entry(i, j)); | } while (matrix_has_entry(i, j)); | |||

matrix_insert_entry(i, j); | matrix_insert_entry(i, j); | |||

} | } | |||

} | } | |||

The right side (the staircase) is generated by the following | The right side (the staircase) is generated by the following | |||

algorithm: | algorithm: | |||

matrix_insert_entry(0, k); /* first row */ | matrix_insert_entry(0, k); /* first row */ | |||

for (i = 1; i < n-k; i++) { /* for the following rows */ | for (i = 1; i < n-k; i++) { /* for the following rows */ | |||

matrix_insert_entry(i, k+i); /* identity */ | matrix_insert_entry(i, k+i); /* identity */ | |||

matrix_insert_entry(i, k+i-1); /* staircase */ | matrix_insert_entry(i, k+i-1); /* staircase */ | |||

} | } | |||

Note that just after creating this parity check matrix, when encoding | Note that just after creating this parity check matrix, when encoding | |||

skipping to change at page 22, line 44 | skipping to change at page 24, line 14 | |||

The right side (the staircase) is generated by the following | The right side (the staircase) is generated by the following | |||

algorithm: | algorithm: | |||

matrix_insert_entry(0, k); /* first row */ | matrix_insert_entry(0, k); /* first row */ | |||

for (i = 1; i < n-k; i++) { /* for the following rows */ | for (i = 1; i < n-k; i++) { /* for the following rows */ | |||

matrix_insert_entry(i, k+i); /* identity */ | matrix_insert_entry(i, k+i); /* identity */ | |||

matrix_insert_entry(i, k+i-1); /* staircase */ | matrix_insert_entry(i, k+i-1); /* staircase */ | |||

} | } | |||

Note that just after creating this parity check matrix, when encoding | Note that just after creating this parity check matrix, when encoding | |||

symbol groups are used (i.e. G > 1), the function initializing the | symbol groups are used (i.e., G > 1), the function initializing the | |||

two random permutation tables (Section 5.5) MUST be called. This is | two random permutation tables (Section 5.6) MUST be called. This is | |||

true both at a sender and at a receiver. | true both at a sender and at a receiver. | |||

6.3. Encoding | 6.3. Encoding | |||

Thanks to the staircase matrix, repair symbol creation is | Thanks to the staircase matrix, repair symbol creation is | |||

straightforward: each repair symbol is equal to the sum of all source | straightforward: each repair symbol is equal to the sum of all source | |||

symbols in the associated equation, plus the previous repair symbol | symbols in the associated equation, plus the previous repair symbol | |||

(except for the first repair symbol). Therefore encoding MUST follow | (except for the first repair symbol). Therefore encoding MUST follow | |||

the natural repair symbol order: start with the first repair symbol, | the natural repair symbol order: start with the first repair symbol, | |||

and generate repair symbol with ESI i before symbol ESI i+1. | and generate repair symbol with ESI i before symbol with ESI i+1. | |||

6.4. Decoding | 6.4. Decoding | |||

Decoding basically consists in solving a system of n-k linear | Decoding basically consists in solving a system of n-k linear | |||

equations whose variables are the n source and repair symbols. Of | equations whose variables are the n source and repair symbols. Of | |||

course, the final goal is to recover the value of the k source | course, the final goal is to recover the value of the k source | |||

symbols only. | symbols only. | |||

To that purpose, many techniques are possible. One of them is the | To that purpose, many techniques are possible. One of them is the | |||

following trivial algorithm [12]: given a set of linear equations, if | following trivial algorithm [ZP74]: given a set of linear equations, | |||

one of them has only one remaining unknown variable, then the value | if one of them has only one remaining unknown variable, then the | |||

of this variable is that of the constant term. So, replace this | value of this variable is that of the constant term. So, replace | |||

variable by its value in all the remaining linear equations and | this variable by its value in all the remaining linear equations and | |||

reiterate. The value of several variables can therefore be found | reiterate. The value of several variables can therefore be found | |||

recursively. Applied to LDPC FEC codes working over an erasure | recursively. Applied to LDPC FEC codes working over an erasure | |||

channel, the parity check matrix defines a set of linear equations | channel, the parity check matrix defines a set of linear equations | |||

whose variables are the source symbols and repair symbols. Receiving | whose variables are the source symbols and repair symbols. Receiving | |||

or decoding a symbol is equivalent to having the value of a variable. | or decoding a symbol is equivalent to having the value of a variable. | |||

Appendix A sketches a possible implementation of this algorithm. | Appendix B sketches a possible implementation of this algorithm. | |||

A Gaussian elimination (or any optimized derivative) is another | A Gaussian elimination (or any optimized derivative) is another | |||

possible decoding technique. Hybrid solutions that start by using | possible decoding technique. Hybrid solutions that start by using | |||

the trivial algorithm above and finish with a Gaussian elimination | the trivial algorithm above and finish with a Gaussian elimination | |||

are also possible. | are also possible. | |||

Because interoperability does not depend on the decoding algorithm | Because interoperability does not depend on the decoding algorithm | |||

used, the current document does not recommend any particular | used, the current document does not recommend any particular | |||

technique. This choice is left to the codec developer. | technique. This choice is left to the codec developer. | |||

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

the above trivial algorithm. Depending on the target use case, the | the above trivial algorithm. Depending on the target use case, the | |||

codec developer will favor one feature or the other. | codec developer will favor one feature or the other. | |||

7. Full Specification of the LDPC-Triangle Scheme | 7. Full Specification of the LDPC-Triangle Scheme | |||

7.1. General | 7.1. General | |||

LDPC-Triangle is identified by the Fully-Specified FEC Encoding ID 4. | LDPC-Triangle is identified by the Fully-Specified FEC Encoding ID 4. | |||

The PRNG used by the LDPC-Triangle scheme must be initialized by a | The PRNG used by the LDPC-Triangle scheme must be initialized by a | |||

seed. This PRNG seed is an optional instance-specific FEC OTI | seed. This PRNG seed is an instance-specific FEC OTI attribute | |||

attribute (Section 4.2.3). When this PRNG seed is not carried within | (Section 4.2.3). | |||

the FEC OTI, it is assumed that encoder and decoders either use | ||||

another way to communicate the seed value or use a fixed, predefined | ||||

value. | ||||

7.2. Parity Check Matrix Creation | 7.2. Parity Check Matrix Creation | |||

The LDPC-Triangle matrix can be divided into two parts: the left side | The LDPC-Triangle matrix can be divided into two parts: the left side | |||

of the matrix defines in which equations the source symbols are | of the matrix defines in which equations the source symbols are | |||

involved; the right side of the matrix defines in which equations the | involved; the right side of the matrix defines in which equations the | |||

repair symbols are involved. | repair symbols are involved. | |||

The left side is generated with the same algorithm as that of LDPC- | The left side is generated with the same algorithm as that of LDPC- | |||

Staircase (Section 6.2). | Staircase (Section 6.2). | |||

skipping to change at page 24, line 44 | skipping to change at page 26, line 41 | |||

matrix_insert_entry(i, k+i-1); /* staircase */ | matrix_insert_entry(i, k+i-1); /* staircase */ | |||

/* now fill the triangle */ | /* now fill the triangle */ | |||

j = i-1; | j = i-1; | |||

for (l = 0; l < j; l++) { /* limit the # of "1s" added */ | for (l = 0; l < j; l++) { /* limit the # of "1s" added */ | |||

j = rand(j); | j = rand(j); | |||

matrix_insert_entry(i, k+j); | matrix_insert_entry(i, k+j); | |||

} | } | |||

} | } | |||

Note that just after creating this parity check matrix, when encoding | Note that just after creating this parity check matrix, when encoding | |||

symbol groups are used (i.e. G > 1), the function initializing the | symbol groups are used (i.e., G > 1), the function initializing the | |||

two random permutation tables (Section 5.5) MUST be called. This is | two random permutation tables (Section 5.6) MUST be called. This is | |||

true both at a sender and at a receiver. | true both at a sender and at a receiver. | |||

7.3. Encoding | 7.3. Encoding | |||

Here also repair symbol creation is straightforward: each repair | Here also repair symbol creation is straightforward: each repair | |||

symbol is equal to the sum of all source symbols in the associated | symbol of ESI i is equal to the sum of all source and repair symbols | |||

equation, plus the repair symbols in the triangle. Therefore | (with ESI lower than i) in the associated equation. Therefore | |||

encoding MUST follow the natural repair symbol order: start with the | encoding MUST follow the natural repair symbol order: start with the | |||

first repair symbol, and generate repair symbol with ESI i before | first repair symbol, and generate repair symbol with ESI i before | |||

symbol ESI i+1. | symbol with ESI i+1. | |||

7.4. Decoding | 7.4. Decoding | |||

Decoding basically consists in solving a system of n-k linear | Decoding basically consists in solving a system of n-k linear | |||

equations, whose variables are the n source and repair symbols. Of | equations, whose variables are the n source and repair symbols. Of | |||

course, the final goal is to recover the value of the k source | course, the final goal is to recover the value of the k source | |||

symbols only. To that purpose, many techniques are possible, as | symbols only. To that purpose, many techniques are possible, as | |||

explained in Section 6.4. | explained in Section 6.4. | |||

Because interoperability does not depend on the decoding algorithm | Because interoperability does not depend on the decoding algorithm | |||

used, the current document does not recommend any particular | used, the current document does not recommend any particular | |||

technique. This choice is left to the codec implementer. | technique. This choice is left to the codec implementer. | |||

8. Security Considerations | 8. Security Considerations | |||

Data delivery can be subject to denial-of-service attacks by | 8.1. Problem Statement | |||

attackers which send corrupted packets that are accepted as | ||||

legitimate by receivers. This is particularly a concern for | ||||

multicast delivery because a corrupted packet may be injected into | ||||

the session close to the root of the multicast tree, in which case | ||||

the corrupted packet will arrive at many receivers. This is | ||||

particularly a concern for the FEC building block because the use of | ||||

even one corrupted packet containing encoding data may result in the | ||||

decoding of an object that is completely corrupted and unusable. It | ||||

is thus RECOMMENDED that source authentication and integrity checking | ||||

are applied to decoded objects before delivering objects to an | ||||

application. For example, a SHA-1 hash [4] of an object may be | ||||

appended before transmission, and the SHA-1 hash is computed and | ||||

checked after the object is decoded but before it is delivered to an | ||||

application. Source authentication SHOULD be provided, for example | ||||

by including a digital signature verifiable by the receiver computed | ||||

on top of the hash value. It is also RECOMMENDED that a packet | ||||

authentication protocol such as TESLA [5] be used to detect and | ||||

discard corrupted packets upon arrival. Furthermore, it is | ||||

RECOMMENDED that Reverse Path Forwarding checks be enabled in all | ||||

network routers and switches along the path from the sender to | ||||

receivers to limit the possibility of a bad agent successfully | ||||

injecting a corrupted packet into the multicast tree data path. | ||||

Another security concern is that some FEC information may be obtained | A content delivery system is potentially subject to many attacks: | |||

by receivers out-of-band in a session description, and if the session | some of them target the network (e.g., to compromise the routing | |||

description is forged or corrupted then the receivers will not use | infrastructure, by compromising the congestion control component), | |||

the correct protocol for decoding content from received packets. To | others target the Content Delivery Protocol (CDP) (e.g., to | |||

avoid these problems, it is RECOMMENDED that measures be taken to | compromise its normal behavior), and finally some attacks target the | |||

prevent receivers from accepting incorrect session descriptions, | content itself. Since this document focuses on a FEC building block | |||

e.g., by using source authentication to ensure that receivers only | independently of any particular CDP (even if ALC and NORM are two | |||

accept legitimate session descriptions from authorized senders. | natural candidates), this section only discusses the additional | |||

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

building block. | ||||

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

o those that are meant to give access to a confidential content | ||||

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

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

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

from using an object), | ||||

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

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

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

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

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

8.2. Attacks Against the Data Flow | ||||

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

8.2.1. Access to Confidential Objects | ||||

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

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

object (e.g., by the content provider, before the FEC encoding | ||||

process), or be done on a packet per packet basis (e.g., when IPSec/ | ||||

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

RECOMMENDED that one of these solutions be used. Even if we mention | ||||

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

of FEC. | ||||

8.2.2. Content Corruption | ||||

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

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

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

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

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

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

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

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

authentication/content integrity service: | ||||

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

public key cryptography), for instance by using RSASSA-PKCS1-v1_5 | ||||

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

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

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

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

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

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

that this solution requires (unless Elliptic Curve Cryptography | ||||

(ECC) is used). To avoid this problem, the signature may span a | ||||

set of symbols (instead of a single one) in order to amortize the | ||||

signature calculation. But if a single symbol is missing, the | ||||

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

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

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

with a secret key shared by all the group members, senders and | ||||

receivers. This technique creates a cryptographically secured | ||||

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

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

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

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

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

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

therefore restricted to situations where 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 | ||||

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

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

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

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

its reception; | ||||

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

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

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

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

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

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

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

limitations). | ||||

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

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

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

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

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

8.3. Attacks Against the FEC Parameters | ||||

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

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

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

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

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

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

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

carrying the FEC parameters sent in-band in an EXT_FTI header | ||||

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

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

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

for instance by digitally signing it with XML digital signatures | ||||

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

session description) this latter SHOULD be protected, for instance by | ||||

digitally signing it. | ||||

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

here also. | ||||

9. IANA Considerations | 9. IANA Considerations | |||

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

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

apply to this document, see [2]. | apply to this document, see [RFC5052]. | |||

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

"ietf:rmt:fec:encoding" name-space to "LDPC Staircase Codes". | "ietf:rmt:fec:encoding" name-space to "LDPC Staircase Codes". | |||

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

"ietf:rmt:fec:encoding" name-space to "LDPC Triangle Codes". | "ietf:rmt:fec:encoding" name-space to "LDPC Triangle Codes". | |||

10. Acknowledgments | 10. Acknowledgments | |||

Section 5.4 is derived from a previous Internet-Draft, and we would | Section 5.5 is derived from a previous Internet-Draft, and we would | |||

like to thank S. Peltotalo and J. Peltotalo for their contribution. | like to thank S. Peltotalo and J. Peltotalo for their contribution. | |||

We would also like to thank Pascal Moniot, Laurent Fazio, Aurelien | We would also like to thank Pascal Moniot, Laurent Fazio, Aurelien | |||

Francillon and Shao Wenjian for their comments. | Francillon, Shao Wenjian, Brian Carpenter, Magnus Westerlund, and | |||

Alfred Hoenes for their comments. | ||||

Last but not least, the authors are grateful to Radford M. Neal | ||||

(University of Toronto) whose LDPC software | ||||

(http://www.cs.toronto.edu/~radford/ldpc.software.html) inspired this | ||||

work. | ||||

11. References | 11. References | |||

11.1. Normative References | 11.1. Normative References | |||

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

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

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

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

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

April 2007. | ||||

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

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

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

[4] "HMAC: Keyed-Hashing for Message Authentication", RFC 2104, | [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error | |||

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

[5] "Timed Efficient Stream Loss-Tolerant Authentication (TESLA): | [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, | |||

Multicast Source Authentication Transform Introduction", | M., and J. Crowcroft, "The Use of Forward Error Correction | |||

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

11.2. Informative References | 11.2. Informative References | |||

[6] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of | [ZP74] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low- | |||

Four Large Block FEC Codecs: LDPC, LDGM, LDGM-Staircase and | Density Codes for Transmission in a Channel with | |||

LDGM-Triangle, Plus a Reed-Solomon Small Block FEC Codec", | Erasures", Translated from Problemy Peredachi | |||

INRIA Research Report RR-5225, June 2004. | Informatsii, Vol.10, No. 1, pp.15-28, January-March 1974. | |||

[7] Neumann, C., Roca, V., Francillon, A., and D. Furodet, "Impacts | [RN04] Roca, V. and C. Neumann, "Design, Evaluation and | |||

of Packet Scheduling and Packet Loss Distribution on FEC | Comparison of Four Large Block FEC Codecs: LDPC, LDGM, | |||

Performances: Observations and Recommendations", ACM CoNEXT'05 | LDGM-Staircase and LDGM-Triangle, Plus a Reed-Solomon | |||

Conference, Toulouse, France (an extended version is available | Small Block FEC Codec", INRIA Research Report RR-5225, | |||

as INRIA Research Report RR-5578), October 2005. | June 2004. | |||

[8] Roca, V., Neumann, C., and J. Laboure, "LDPC-Staircase/ | [NRFF05] Neumann, C., Roca, V., Francillon, A., and D. Furodet, | |||

LDPC-Triangle Codec Reference Implementation", INRIA Rhone- | "Impacts of Packet Scheduling and Packet Loss Distribution | |||

Alpes and STMicroelectronics, | on FEC Performances: Observations and Recommendations", | |||

ACM CoNEXT'05 Conference, Toulouse, France (an extended | ||||

version is available as INRIA Research Report RR-5578), | ||||

October 2005. | ||||

[LDPC-codec] | ||||

Roca, V., Neumann, C., Cunche, M., and J. Laboure, "LDPC- | ||||

Staircase/LDPC-Triangle Codec Reference Implementation", | ||||

INRIA Rhone-Alpes and STMicroelectronics, | ||||

http://planete-bcast.inrialpes.fr/. | http://planete-bcast.inrialpes.fr/. | |||

[9] MacKay, D., "Information Theory, Inference and Learning | [MK03] MacKay, D., "Information Theory, Inference and Learning | |||

Algorithms", Cambridge University Press, ISBN: 0521642981, | Algorithms", Cambridge University Press, ISBN: 0-521- | |||

2003. | 64298-1, 2003. | |||

[10] Park, S. and K. Miller, "Random Number Generators: Good Ones | [PM88] Park, S. and K. Miller, "Random Number Generators: Good | |||

are Hard to Find", Communications of the ACM, Vol. 31, No. 10, | Ones are Hard to Find", Communications of the ACM, Vol. | |||

pp.1192-1201, 1988. | 31, No. 10, pp.1192-1201, 1988. | |||

[11] Carta, D., "Two Fast Implementations of the Minimal Standard | [CA90] Carta, D., "Two Fast Implementations of the Minimal | |||

Random Number Generator", Communications of the ACM, Vol. 33, | Standard Random Number Generator", Communications of the | |||

No. 1, pp.87-88, January 1990. | ACM, Vol. 33, No. 1, pp.87-88, January 1990. | |||

[12] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low-Density | [PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery, | |||

Codes for Transmission in a Channel with Erasures", Translated | "Numerical Recipies in C; Second Edition", Cambridge | |||

from Problemy Peredachi Informatsii, Vol.10, No. 1, pp.15-28, | University Press, ISBN: 0-521-43108-5, 1992. | |||

January-March 1974. | ||||

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

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

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

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

February 2007. | February 2007. | |||

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

Adamson, B., Bormann, C., Handley, M., and J. Macker, | ||||

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

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

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

March 2007. | ||||

[draft-ietf-rmt-flute-revised] | ||||

Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, | ||||

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

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

January 2007. | October 2007. | |||

[15] Adamson, B., Bormann, C., Handley, M., and J. Macker, | [RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography | |||

"Negative-acknowledgment (NACK)-Oriented Reliable Multicast | Standards (PKCS) #1: RSA Cryptography Specifications | |||

(NORM) Protocol", draft-ietf-rmt-pi-norm-revised-04.txt (work | Version 2.1", RFC 3447, February 2003. | |||

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

Appendix A. Trivial Decoding Algorithm (Informative Only) | [RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)", | |||

RFC 4303, December 2005. | ||||

A trivial decoding algorithm is sketched below (please see [8] for | [RFC2104] "HMAC: Keyed-Hashing for Message Authentication", | |||

the details omitted here): | RFC 2104, February 1997. | |||

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

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

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

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

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

March 2002. | ||||

Appendix A. Pseudo Random Number Generator Example Implementation | ||||

(Informative Only) | ||||

The following is an implementation of the minimal standard generator | ||||

defined in Section 5.7 that scales the result between 0 and maxv-1 | ||||

inclusive. It uses the Park and Miller algorithm [PM88] with the | ||||

optimization suggested by D. Carta in [CA90]. The inner algorithm | ||||

relies on 32 bit mathematics only and does not require any division. | ||||

unsigned long seed; | ||||

/* | ||||

* Initialize the PRNG with a seed between | ||||

* 1 and 0x7FFFFFFE (i.e., 2^^31-2) inclusive. | ||||

*/ | ||||

void srand (unsigned long s) | ||||

{ | ||||

if ((s > 0) && (s < 0x7FFFFFFF)) | ||||

seed = s; | ||||

else | ||||

exit(-1); | ||||

} | ||||

/* | ||||

* Returns a random integer in [0; maxv-1] | ||||

* Derived from rand31pmc, Robin Whittle, | ||||

* September 20th, 2005. | ||||

* http://www.firstpr.com.au/dsp/rand31/ | ||||

* 16807 multiplier constant (7^^5) | ||||

* 0x7FFFFFFF modulo constant (2^^31-1) | ||||

* The inner PRNG produces a value between 1 and | ||||

* 0x7FFFFFFE (2^^31-2) inclusive. | ||||

* This value is then scaled between 0 and maxv-1 | ||||

* inclusive. | ||||

*/ | ||||

unsigned long | ||||

rand (unsigned long maxv) | ||||

{ | ||||

unsigned long hi, lo; | ||||

lo = 16807 * (seed & 0xFFFF); | ||||

hi = 16807 * (seed >> 16); /* binary shift to right */ | ||||

lo += (hi & 0x7FFF) << 16; /* binary shift to left */ | ||||

lo += hi >> 15; | ||||

if (lo > 0x7FFFFFFF) | ||||

lo -= 0x7FFFFFFF; | ||||

seed = lo; | ||||

/* don't use modulo, least significant bits are less random | ||||

* than most significant bits [PTVF92] */ | ||||

return ((unsigned long) | ||||

((double)maxv * (double)seed / (double)0x7FFFFFFF)); | ||||

} | ||||

Appendix B. Trivial Decoding Algorithm (Informative Only) | ||||

A trivial decoding algorithm is sketched below (please see | ||||

[LDPC-codec] for the details omitted here): | ||||

Initialization: allocate a table partial_sum[n-k] of buffers, each | Initialization: allocate a table partial_sum[n-k] of buffers, each | |||

buffer being of size the symbol size. There's one | buffer being of size the symbol size. There's one | |||

entry per equation since the buffers are meant to | entry per equation since the buffers are meant to | |||

store the partial sum of each equation; Reset all | store the partial sum of each equation; Reset all | |||

the buffers to zero; | the buffers to zero; | |||

/* | /* | |||

* For each newly received or decoded symbol, try to make progress | * For each newly received or decoded symbol, try to make progress | |||

* in the decoding of the associated source block. | * in the decoding of the associated source block. | |||

skipping to change at page 33, line 14 | skipping to change at page 39, line 14 | |||

Authors' Addresses | Authors' Addresses | |||

Vincent Roca | Vincent Roca | |||

INRIA | INRIA | |||

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

Inovallee; Montbonnot | Inovallee; Montbonnot | |||

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

France | France | |||

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

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

Christoph Neumann | Christoph Neumann | |||

Thomson Research | Thomson | |||

46, Quai A. Le Gallo | 12, bd de Metz | |||

Boulogne Cedex 92648 | Rennes 35700 | |||

France | France | |||

Email: christoph.neumann@thomson.net | Email: christoph.neumann@thomson.net | |||

URI: http://planete.inrialpes.fr/~chneuman/ | URI: http://planete.inrialpes.fr/people/chneuman/ | |||

David Furodet | David Furodet | |||

STMicroelectronics | STMicroelectronics | |||

12, Rue Jules Horowitz | 12, Rue Jules Horowitz | |||

BP217 | BP217 | |||

Grenoble Cedex 38019 | Grenoble Cedex 38019 | |||

France | France | |||

Email: david.furodet@st.com | Email: david.furodet@st.com | |||

URI: http://www.st.com/ | URI: http://www.st.com/ | |||

End of changes. 110 change blocks. | ||||

334 lines changed or deleted | | 539 lines changed or added | ||

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