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

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

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

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

Expires: June 25, 2007 Thomson Research | Expires: September 30, 2007 Thomson Research | |||

D. Furodet | D. Furodet | |||

STMicroelectronics | STMicroelectronics | |||

December 22, 2006 | March 29, 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-04.txt | draft-ietf-rmt-bb-fec-ldpc-05.txt | |||

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

This Internet-Draft will expire on June 25, 2007. | This Internet-Draft will expire on September 30, 2007. | |||

Copyright Notice | Copyright Notice | |||

Copyright (C) The IETF Trust (2006). | 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 these sense of | |||

RFC3453. | RFC3453. | |||

skipping to change at page 3, line 31 | skipping to change at page 3, line 31 | |||

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

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

5.5. Identifying the Symbols of an Encoding Symbol Group . . . 16 | 5.5. Identifying the Symbols of an Encoding Symbol Group . . . 16 | |||

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

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

6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 21 | 6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 21 | |||

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

6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 23 | 6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 22 | |||

6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 23 | 6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 23 | |||

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

7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 25 | 7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 24 | |||

7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 25 | 7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 24 | |||

7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 25 | 7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 24 | |||

7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 26 | 7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 25 | |||

8. Security Considerations . . . . . . . . . . . . . . . . . . . 27 | 8. Security Considerations . . . . . . . . . . . . . . . . . . . 26 | |||

9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 28 | 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27 | |||

10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 29 | 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 28 | |||

11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 30 | 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 29 | |||

11.1. Normative References . . . . . . . . . . . . . . . . . . . 30 | 11.1. Normative References . . . . . . . . . . . . . . . . . . . 29 | |||

11.2. Informative References . . . . . . . . . . . . . . . . . . 30 | 11.2. Informative References . . . . . . . . . . . . . . . . . . 29 | |||

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

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

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

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

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

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

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

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

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

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

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

payload is(are) generated. There are a maximum of 2^^12 blocks | payload is(are) generated. There are a maximum of 2^^12 blocks | |||

per object. | per object. Source block numbering starts at 0. | |||

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

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

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

| 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 . | . Optional PRNG seed . | |||

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

Figure 2: EXT_FTI Header for FEC Encoding ID 132 | 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 | o The HEL (Header Extension Length) indicates whether the optional | |||

PRNG seed is present (HEL=5) or not (HEL=4). | 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 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 [12], 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 | |||

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

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

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

| 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 | FDT Instance for FEC Encoding ID 3 and 4. | |||

When no PRNG seed is to be carried in the FEC OTI, the seed field is | When no PRNG seed is to be carried in the FEC OTI, the seed field | |||

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

contains a valid value as explained in Section 4.2.3. | 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 | 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) and 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. | |||

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

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

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 Section 5.2, Section 5.3 and Section 5.4), | determined (respectively in Section 5.2, Section 5.3 and | |||

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

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

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

internal codec limitations. | internal 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/rate))) | |||

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

o rate == 1 (no repair symbols): max1_B = 2^^20 = 1,048,576 | o rate == 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 <= rate < 1: max1_B = 2^^19 = 524,288 symbols | |||

o 1/4 <= rate < 1/2: max1_B = 2^^18 = 262,144 symbols | o 1/4 <= rate < 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 <= rate < 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. This is the case for instance 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, | |||

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

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

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

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

codes are known to offer better protection for large blocks. In case | Indeed, LDPC codes are known to offer better protection for large | |||

of small objects, it can be a good practice to reduce the encoding | blocks. In case of small objects, it can be advantageous to reduce | |||

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

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

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

to the FEC OTI. | to the FEC OTI. | |||

Example: | Example: | |||

First define the target packet size, pkt_sz (usually the PMTU minus | First define the target packet payload size, pkt_sz (at most equal to | |||

the various protocol headers). The pkt_sz must be chosen in such a | the PMTU minus the size of the various protocol headers). The pkt_sz | |||

way that the symbol size is an integer. This can require that pkt_sz | must be chosen in such a way that the symbol size is an integer. | |||

be a multiple of 4, 8 or 16 (see the table below). Then calculate | This can require that pkt_sz be a multiple of 4, 8 or 16 (see the | |||

the number of packets: nb_pkts = ceil(L / pkt_sz). Finally use the | table below). Then calculate the 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. | 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 | | |||

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

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

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. | explains how to determine its value. | |||

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

source blocking algorithm. | source blocking algorithm. | |||

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

starting a FLUTE sending application). It is expressed as a | when 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 rate 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 | n: Number of encoding symbols generated for this source block | |||

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

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, ESIs_of_group(), that takes as | o are identified by a function, sender(resp. | |||

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 the list of G Encoding Symbol IDs that will be packed | and returns a list of G Encoding Symbol IDs. In case of a source | |||

together. In case of a source packet, the G source symbols are | packet, the G Encoding Symbol IDs are chosen consecutively, by | |||

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

o are stored in sequence in the packet, without any padding. In | o are stored in sequence in the packet, without any padding. In | |||

other words, the last byte of the symbol with ESI i (where i is | other words, the last byte of the i-th symbol is immediately | |||

the i-th ESI returned by the function ESIs_of_group()) is | followed by the first byte of (i+1)-th symbol. | |||

immediately followed by the first byte of symbol i+1. | ||||

The system must first be initialized by creating a random permutation | The system must first be initialized by creating a random permutation | |||

of the n-k indexes. This initialization function MUST be called | of the n-k indexes. This initialization function MUST be called | |||

immediately after creating the parity check matrix. More precisely, | immediately after creating the parity check matrix. More precisely, | |||

since the PRNG seed is not re-initialized, no call to the PRNG | since the PRNG seed is not re-initialized, no call to the PRNG | |||

function must have happened between the time the parity check matrix | function must have happened between the time the parity check matrix | |||

has been initialized and the time the following initialization | has been initialized and the time the following initialization | |||

function is called. This is true both at a sender and at a receiver. | function is called. This is true both at a sender and at a receiver. | |||

int *txseqToID; | int *txseqToID; | |||

skipping to change at page 22, line 5 | skipping to change at page 21, line 28 | |||

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 23, line 46 | skipping to change at page 23, line 28 | |||

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

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

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

using the trivial algorithm above and finish with a Gauss 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. | |||

Yet choosing a decoding technique will have great practical impacts. | However choosing a decoding technique will have great practical | |||

It will impact the erasure capabilities: a Gauss elimination | impacts. It will impact the erasure capabilities: a Gaussian | |||

technique enables to solve the system with a smaller number of known | elimination enables to solve the system with a smaller number of | |||

symbols compared to the trivial technique. It will also impact the | known symbols compared to the trivial technique. It will also impact | |||

CPU load: a Gauss elimination technique requires much more processing | the CPU load: a Gaussian elimination requires more processing than | |||

than the trivial technique. 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 optional instance-specific FEC OTI | |||

skipping to change at page 30, line 14 | skipping to change at page 29, line 14 | |||

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

September 2006. | March 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. | |||

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

[4] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of | [4] 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", | |||

skipping to change at page 31, line 9 | skipping to change at page 30, line 9 | |||

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 | [10] 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 | [11] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered | |||

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

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

April 2006. | February 2007. | |||

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

August 2006. | January 2007. | |||

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

in progress), September 2006. | 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 [6] 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 | |||

* in the decoding of the associated source block. | * in the decoding of the associated source block. | |||

* NB: in case of a symbol group (G>1), this function is called for | * NB: in case of a symbol group (G>1), this function is called for | |||

* each symbol of the received packet. | * each symbol of the received packet. | |||

* NB: a callback function indicates to the caller that new symbol(s) | ||||

* has(have) been decoded. | ||||

* new_esi (IN): ESI of the new symbol received or decoded | * new_esi (IN): ESI of the new symbol received or decoded | |||

* new_symb (IN): Buffer of the new symbol received or decoded | * new_symb (IN): Buffer of the new symbol received or decoded | |||

*/ | */ | |||

void | void | |||

decoding_step(ESI_t new_esi, | decoding_step(ESI_t new_esi, | |||

symbol_t *new_symb) | symbol_t *new_symb) | |||

{ | { | |||

If (new_symb is an already decoded or received symbol) { | If (new_symb is an already decoded or received symbol) { | |||

Return; /* don't waste time with this symbol */ | Return; /* don't waste time with this symbol */ | |||

} | } | |||

skipping to change at page 33, line 35 | skipping to change at page 32, line 37 | |||

If ((degree of equation eq == 1) { | If ((degree of equation eq == 1) { | |||

Let dec_esi be the ESI of the newly decoded symbol in | Let dec_esi be the ESI of the newly decoded symbol in | |||

equation eq; | equation eq; | |||

Remove entry(eq, dec_esi); | Remove entry(eq, dec_esi); | |||

Allocate a buffer, dec_symb, for this symbol and | Allocate a buffer, dec_symb, for this symbol and | |||

copy partial_sum[eq] to dec_symb; | copy partial_sum[eq] to dec_symb; | |||

Inform the caller that a new symbol has been | ||||

decoded via a callback function; | ||||

/* finally, call this function recursively */ | /* finally, call this function recursively */ | |||

decoding_step(dec_esi, dec_symb); | decoding_step(dec_esi, dec_symb); | |||

} | } | |||

} | } | |||

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

Return; | Return; | |||

} | } | |||

Authors' Addresses | Authors' Addresses | |||

skipping to change at page 35, line 7 | skipping to change at page 34, line 7 | |||

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

Full Copyright Statement | Full Copyright Statement | |||

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

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

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

retain all their rights. | retain all their rights. | |||

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

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

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

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

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

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

70 lines changed or deleted | | 81 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/ |