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

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

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

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

Expires: September 30, 2007 Thomson Research | Expires: November 8, 2007 Thomson Research | |||

D. Furodet | D. Furodet | |||

STMicroelectronics | STMicroelectronics | |||

March 29, 2007 | May 7, 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-05.txt | draft-ietf-rmt-bb-fec-ldpc-06.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 September 30, 2007. | This Internet-Draft will expire on November 8, 2007. | |||

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 objects on packet erasure channels. 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 these sense of | (LDPC) codes, and are large block FEC codes in the sense of RFC3453. | |||

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

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

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

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

1. Introduction | 1. Introduction | |||

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

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

large block codes is the possibility to operate efficiently on source | large 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 [4][7]. Both schemes belong to the | with the LDPC-Triangle FEC codes [6][9]. Both schemes belong to the | |||

broad class of large block codes. | broad class of large block codes. | |||

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

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

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

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

repair symbols. | 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 [6]. | available and distributed under a GNU/LGPL license [8]. | |||

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

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

3.1. Definitions | 3.1. Definitions | |||

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

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

This section shows two possible encoding formats of the above FEC | This section shows 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 [11] or NORM [13] protocols). | mechanism is used (e.g. within the ALC [13] or NORM [15] 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 (=4 or 5) | | | |||

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

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

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

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

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

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

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 [12], the following XML attributes must be described | a FLUTE session [14], the following XML attributes must be described | |||

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

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

o FEC-OTI-Transfer-length | 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 | |||

skipping to change at page 12, line 48 | skipping to change at page 12, line 48 | |||

(i,j) (i.e. at row i and column j) means that the symbol with ESI i | (i,j) (i.e. at row i and column j) means that the symbol with ESI i | |||

appears in equation j of the system. The only difference between the | appears in equation j of the system. The only difference between the | |||

LDPC-Staircase and LDPC-Triangle schemes is the construction of the | LDPC-Staircase and LDPC-Triangle schemes is the construction of the | |||

right sub-matrix. | right sub-matrix. | |||

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

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 [5]. | interested reader will find more details in [7]. | |||

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

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

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

and finally specify the PRNG (Section 5.6). | and finally specify the PRNG (Section 5.6). | |||

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 (rate), the Encoding Symbol ID | |||

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

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

} | } | |||

} | } | |||

} | } | |||

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

The present FEC Encoding ID relies on a pseudo-random number | The present FEC Encoding ID relies on a pseudo-random number | |||

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

to enable the receivers and the senders to build the same parity | to enable the receivers and the senders to build the same parity | |||

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

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

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

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

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

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

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

MUST be equal to 1043618065. | MUST be equal to 1043618065. | |||

The following implementation uses the Park and Miller algorithm with | The following implementation uses the Park and Miller algorithm with | |||

the optimization suggested by D. Carta in [9]. | the optimization suggested by D. Carta in [11]. | |||

unsigned long seed; | unsigned long seed; | |||

/* | /* | |||

* Initialize the PRNG with a seed between | * Initialize the PRNG with a seed between | |||

* 1 and 0x7FFFFFFE (i.e. 2^^31-2) inclusive. | * 1 and 0x7FFFFFFE (i.e. 2^^31-2) inclusive. | |||

*/ | */ | |||

void srand (unsigned long s) | void srand (unsigned long s) | |||

{ | { | |||

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

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

unsigned long hi, lo; | unsigned long hi, lo; | |||

lo = 16807 * (seed & 0xFFFF); | lo = 16807 * (seed & 0xFFFF); | |||

hi = 16807 * (seed >> 16); /* binary shift to right */ | hi = 16807 * (seed >> 16); /* binary shift to right */ | |||

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

lo += hi >> 15; | lo += hi >> 15; | |||

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

lo -= 0x7FFFFFFF; | lo -= 0x7FFFFFFF; | |||

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

/* don't use modulo, least significant bits are less random | /* don't use modulo, least significant bits are less random | |||

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

return ((unsigned long) | return ((unsigned long) | |||

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

} | } | |||

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

skipping to change at page 23, line 17 | skipping to change at page 23, line 17 | |||

and generate repair symbol with ESI i before symbol ESI i+1. | and generate repair symbol with ESI i before symbol 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 [10]: given a set of linear equations, if | following trivial algorithm [12]: given a set of linear equations, if | |||

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

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

variable by its value in all the remaining linear equations and | 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 A sketches a possible implementation of this algorithm. | |||

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

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

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

[2]. | attackers which send corrupted packets that are accepted as | |||

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

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

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

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

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

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

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

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

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

application. For example, a SHA-1 hash [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 | ||||

by receivers out-of-band in a session description, and if the session | ||||

description is forged or corrupted then the receivers will not use | ||||

the correct protocol for decoding content from received packets. To | ||||

avoid these problems, it is RECOMMENDED that measures be taken to | ||||

prevent receivers from accepting incorrect session descriptions, | ||||

e.g., by using source authentication to ensure that receivers only | ||||

accept legitimate session descriptions from authorized senders. | ||||

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]. This document assigns the Fully- | apply to this document, see [2]. | |||

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

space to "LDPC Staircase Codes", and the Fully-Specified FEC Encoding | This document assigns the Fully-Specified FEC Encoding ID 3 under the | |||

ID 4 under the ietf:rmt:fec:encoding name-space to "LDPC Triangle | "ietf:rmt:fec:encoding" name-space to "LDPC Staircase Codes". | |||

Codes". | ||||

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

"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.4 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 and Shao Wenjian for their comments. | |||

11. References | 11. References | |||

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

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

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

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

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

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

March 2007. | April 2007. | |||

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

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

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

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

February 1997. | ||||

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

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

RFC 4082, June 2005. | ||||

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

[4] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of | [6] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of | |||

Four Large Block FEC Codecs: LDPC, LDGM, LDGM-Staircase and | Four Large Block FEC Codecs: LDPC, LDGM, LDGM-Staircase and | |||

LDGM-Triangle, Plus a Reed-Solomon Small Block FEC Codec", | LDGM-Triangle, Plus a Reed-Solomon Small Block FEC Codec", | |||

INRIA Research Report RR-5225, June 2004. | INRIA Research Report RR-5225, June 2004. | |||

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

of Packet Scheduling and Packet Loss Distribution on FEC | of Packet Scheduling and Packet Loss Distribution on FEC | |||

Performances: Observations and Recommendations", ACM CoNEXT'05 | Performances: Observations and Recommendations", ACM CoNEXT'05 | |||

Conference, Toulouse, France (an extended version is available | Conference, Toulouse, France (an extended version is available | |||

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

[6] Roca, V., Neumann, C., and J. Laboure, "LDPC-Staircase/ | [8] Roca, V., Neumann, C., and J. Laboure, "LDPC-Staircase/ | |||

LDPC-Triangle Codec Reference Implementation", INRIA Rhone- | LDPC-Triangle Codec Reference Implementation", INRIA Rhone- | |||

Alpes and STMicroelectronics, | Alpes and STMicroelectronics, | |||

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

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

Algorithms", Cambridge University Press, ISBN: 0521642981, | Algorithms", Cambridge University Press, ISBN: 0521642981, | |||

2003. | 2003. | |||

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

are Hard to Find", Communications of the ACM, Vol. 31, No. 10, | are Hard to Find", Communications of the ACM, Vol. 31, No. 10, | |||

pp.1192-1201, 1988. | pp.1192-1201, 1988. | |||

[9] Carta, D., "Two Fast Implementations of the Minimal Standard | [11] Carta, D., "Two Fast Implementations of the Minimal Standard | |||

Random Number Generator", Communications of the ACM, Vol. 33, | Random Number Generator", Communications of the ACM, Vol. 33, | |||

No. 1, pp.87-88, January 1990. | No. 1, pp.87-88, January 1990. | |||

[10] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low-Density | [12] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low-Density | |||

Codes for Transmission in a Channel with Erasures", Translated | Codes for Transmission in a Channel with Erasures", Translated | |||

from Problemy Peredachi Informatsii, Vol.10, No. 1, pp.15-28, | from Problemy Peredachi Informatsii, Vol.10, No. 1, pp.15-28, | |||

January-March 1974. | January-March 1974. | |||

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

Coding (ALC) Protocol Instantiation", | 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. | |||

[12] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca, | [14] 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-03.txt (work in progress), | |||

January 2007. | January 2007. | |||

[13] Adamson, B., Bormann, C., Handley, M., and J. Macker, | [15] Adamson, B., Bormann, C., Handley, M., and J. Macker, | |||

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

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

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

Appendix A. Trivial Decoding Algorithm (Informative Only) | Appendix A. Trivial Decoding Algorithm (Informative Only) | |||

A trivial decoding algorithm is sketched below (please see [6] for | A trivial decoding algorithm is sketched below (please see [8] for | |||

the details omitted here): | 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 | |||

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

Free the list of equations having symbols decoded; | Free the list of equations having symbols decoded; | |||

Return; | Return; | |||

} | } | |||

Authors' Addresses | Authors' Addresses | |||

Vincent Roca | Vincent Roca | |||

INRIA | INRIA | |||

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

Zirst; Montbonnot | Inovallee; Montbonnot | |||

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

France | France | |||

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

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

Christoph Neumann | Christoph Neumann | |||

Thomson Research | Thomson Research | |||

46, Quai A. Le Gallo | 46, Quai A. Le Gallo | |||

Boulogne Cedex 92648 | Boulogne Cedex 92648 | |||

End of changes. 30 change blocks. | ||||

36 lines changed or deleted | | 74 lines changed or added | ||

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