 1/draftietfrmtbbfecldpc06.txt 20071116 17:12:13.000000000 +0100
+++ 2/draftietfrmtbbfecldpc07.txt 20071116 17:12:13.000000000 +0100
@@ 1,22 +1,22 @@
RMT V. Roca
InternetDraft INRIA
Intended status: Experimental C. Neumann
Expires: November 8, 2007 Thomson Research
+Intended status: Standards Track C. Neumann
+Expires: May 19, 2008 Thomson
D. Furodet
STMicroelectronics
 May 7, 2007
+ November 16, 2007
Low Density Parity Check (LDPC) Staircase and Triangle Forward Error
Correction (FEC) Schemes
 draftietfrmtbbfecldpc06.txt
+ draftietfrmtbbfecldpc07.txt
Status of this Memo
By submitting this InternetDraft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
@@ 27,31 +27,33 @@
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use InternetDrafts as reference
material or to cite them other than as "work in progress."
The list of current InternetDrafts can be accessed at
http://www.ietf.org/ietf/1idabstracts.txt.
The list of InternetDraft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
 This InternetDraft will expire on November 8, 2007.
+ This InternetDraft will expire on May 19, 2008.
Copyright Notice
Copyright (C) The IETF Trust (2007).
Abstract
This document describes two FullySpecified FEC Schemes, LDPC
Staircase and LDPCTriangle, 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''
(LDPC) codes, and are large block FEC codes in the sense of RFC3453.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Requirements notation . . . . . . . . . . . . . . . . . . . . 5
3. Definitions, Notations and Abbreviations . . . . . . . . . . . 6
3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 6
3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 6
@@ 60,125 +62,165 @@
4.1. FEC Payload IDs . . . . . . . . . . . . . . . . . . . . . 8
4.2. FEC Object Transmission Information . . . . . . . . . . . 8
4.2.1. Mandatory Element . . . . . . . . . . . . . . . . . . 8
4.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 8
4.2.3. SchemeSpecific Elements . . . . . . . . . . . . . . . 9
4.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 9
5. Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.2. Determining the Maximum Source Block Length (B) . . . . . 13
5.3. Determining the Encoding Symbol Length (E) and Number
 of Encoding Symbols per Group (G) . . . . . . . . . . . . 13
 5.4. Determining the Number of Encoding Symbols of a Block . . 15
 5.5. Identifying the Symbols of an Encoding Symbol Group . . . 16
 5.6. Pseudo Random Number Generator . . . . . . . . . . . . . . 19
 6. Full Specification of the LDPCStaircase Scheme . . . . . . . 21
 6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 21
 6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 21
 6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 22
 6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 23
 7. Full Specification of the LDPCTriangle Scheme . . . . . . . . 24
 7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 24
 7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 24
 7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 24
 7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 25
 8. Security Considerations . . . . . . . . . . . . . . . . . . . 26
 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27
 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 28
 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 29
 11.1. Normative References . . . . . . . . . . . . . . . . . . . 29
 11.2. Informative References . . . . . . . . . . . . . . . . . . 29
 Appendix A. Trivial Decoding Algorithm (Informative Only) . . . . 31
 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 33
 Intellectual Property and Copyright Statements . . . . . . . . . . 34
+ of Encoding Symbols per Group (G) . . . . . . . . . . . . 14
+ 5.4. Determining the Maximum Number of Encoding Symbols
+ Generated for Any Source Block (max_n) . . . . . . . . . . 15
+ 5.5. Determining the Number of Encoding Symbols of a Block
+ (n) . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
+ 5.6. Identifying the G Symbols of an Encoding Symbol Group . . 16
+ 5.7. Pseudo Random Number Generator . . . . . . . . . . . . . . 20
+ 6. Full Specification of the LDPCStaircase Scheme . . . . . . . 22
+ 6.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 22
+ 6.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 22
+ 6.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 24
+ 6.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 24
+ 7. Full Specification of the LDPCTriangle Scheme . . . . . . . . 26
+ 7.1. General . . . . . . . . . . . . . . . . . . . . . . . . . 26
+ 7.2. Parity Check Matrix Creation . . . . . . . . . . . . . . . 26
+ 7.3. Encoding . . . . . . . . . . . . . . . . . . . . . . . . . 26
+ 7.4. Decoding . . . . . . . . . . . . . . . . . . . . . . . . . 27
+ 8. Security Considerations . . . . . . . . . . . . . . . . . . . 28
+ 8.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 28
+ 8.2. Attacks Against the Data Flow . . . . . . . . . . . . . . 28
+ 8.2.1. Access to Confidential Objects . . . . . . . . . . . . 28
+ 8.2.2. Content Corruption . . . . . . . . . . . . . . . . . . 29
+ 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
 RFC 3453 [3] introduces large block FEC codes as an alternative to
 small block FEC codes like ReedSolomon. The main advantage of such
 large block codes is the possibility to operate efficiently on source
+ [RFC3453] introduces large block FEC codes as an alternative to small
+ block FEC codes like ReedSolomon. The main advantage of such large
+ block codes is the possibility to operate efficiently on source
blocks of size several tens of thousands (or more) source symbols.
The present document introduces the FullySpecified FEC Encoding ID 3
that is intended to be used with the LDPCStaircase FEC codes, and
the FullySpecified FEC Encoding ID 4 that is intended to be used
 with the LDPCTriangle FEC codes [6][9]. Both schemes belong to the
 broad class of large block codes.
+ with the LDPCTriangle FEC codes [RN04][MK03]. Both schemes belong
+ to the broad class of large block codes. For a definition of the
+ term FullySpecified Scheme, see [RFC5052], section 4.
LDPC codes rely on a dedicated matrix, called a "Parity Check
Matrix", at the encoding and decoding ends. The parity check matrix
defines relationships (or constraints) between the various encoding
 symbols (i.e. source symbols and repair symbols), that are later used
 by the decoder to reconstruct the original k source symbols if some
 of them are missing. These codes are systematic, in the sense that
 the encoding symbols include the source symbols in addition to the
 repair symbols.
+ symbols (i.e., source symbols and repair symbols), that are later
+ used by the decoder to reconstruct the original k source symbols if
+ some of them are missing. These codes are systematic, in the sense
+ that the encoding symbols include the source symbols in addition to
+ the repair symbols.
Since the encoder and decoder must operate on the same parity check
matrix, information must be communicated between them as part of the
FEC Object Transmission Information.
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 [LDPCcodec].
+ 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
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"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.1. Definitions
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
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
This document uses the following notations:
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

 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
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
N denotes the number of source blocks into which the object shall
be partitioned
G denotes the number of encoding symbols per group, i.e. the
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
 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
srand(s) denotes the initialization function of the pseudorandom
number generator, where s is the seed (s > 0)
+
rand(m) denotes a pseudorandom number generator that returns a
new random integer in [0; m1] each time it is called
3.3. Abbreviations
This document uses the following abbreviations:
ESI: Encoding Symbol ID
FEC OTI: FEC Object Transmission Information
@@ 204,41 +246,41 @@
The Encoding Symbol ID (20 bit field) identifies which encoding
symbol(s) generated from the source block is(are) carried in the
packet payload. There are a maximum of 2^^20 encoding symbols per
block. The first k values (0 to k1) identify source symbols, the
remaining nk values (k to nk1) identify repair symbols.
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
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
 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 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) 
+++++++++++++++++++++++++++++++++
Figure 1: FEC Payload ID encoding format for FEC Encoding ID 3 and 4
4.2. FEC Object Transmission Information
4.2.1. Mandatory Element
o FEC Encoding ID: the LDPCStaircase and LDPCTriangle Fully
Specified FEC Schemes use respectively the FEC Encoding ID 3
(Staircase) and 4 (Triangle).
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 TransferLength (L): a nonnegative integer indicating the length
of the object in bytes. There are some restrictions on the
maximum TransferLength that can be supported:
maximum transfer length = 2^^12 * B * E
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
length is 2^^41 bytes (or 2 TB). The upper limit, with symbols of
@@ 259,86 +301,80 @@
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
elements.
4.2.3. SchemeSpecific Elements
The following elements MUST be defined with the present FEC Scheme:
o G: a nonnegative 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
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
 0x7FFFFFFE (i.e. 2^^312) inclusive. This value is used to
 initialize the Pseudo Random Number Generator (Section 5.6). This
 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.
+ 0x7FFFFFFE (i.e., 2^^312) inclusive. This value is used to
+ initialize the Pseudo Random Number Generator (Section 5.7).
4.2.4. Encoding Format
This section shows two possible encoding formats of the above FEC
OTI. The present document does not specify when or how these
encoding formats should be used.
4.2.4.1. Using the General EXT_FTI Format
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
+ [draftietfrmtpialcrevised] or NORM
+ [draftietfrmtpinormrevised] protocols).
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
+++++++++++++++++++++++++++++++++
  HET = 64  HEL (=4 or 5)  
+  HET = 64  HEL = 5  
+++++++++++++++++ +
 TransferLength (L) 
+++++++++++++++++++++++++++++++++
 Encoding Symbol Length (E)  G  B (MSB) 
+++++++++++++++++++++++++++++++++
 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.
In particular:
 o The HEL (Header Extension Length) indicates whether the optional
 PRNG seed is present (HEL=5) or not (HEL=4).

o The TransferLength (L) field size (48 bits) is larger than the
size required to store the maximum transfer length (Section 4.2.2)
for field alignment purposes.
o The MaximumSourceBlockLength (B) field (20 bits) is split into
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
bits (LSB) are in the fourth 32bit word.
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
 a FLUTE session [14], the following XML attributes must be described
 for the associated object:
+ a FLUTE session [draftietfrmtfluterevised], the following XML
+ attributes must be described for the associated object:
o FECOTIFECEncodingID
o FECOTITransferlength
o FECOTIEncodingSymbolLength
+
o FECOTIMaximumSourceBlockLength
o FECOTIMaxNumberofEncodingSymbols
o FECOTISchemeSpecificInfo
The FECOTISchemeSpecificInfo contains the string resulting from
the Base64 encoding (in the XML Schema xs:base64Binary sense) of the
following value:
@@ 346,242 +382,260 @@
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 
+++++++++++++++++++++++++++++++++
 G 
+++++++++
Figure 3: FEC OTI Scheme Specific Information to be Included in the
FDT Instance for FEC Encoding ID 3 and 4.
 When no PRNG seed is to be carried in the FEC OTI, the seed field
 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
+ During Base64 encoding, the 5 bytes of the FEC OTI Scheme Specific
Information are transformed into a string of 8 printable characters
 (in the 64character alphabet) and added to the FECOTIScheme
+ (in the 64character alphabet) that is added to the FECOTIScheme
SpecificInfo attribute.
5. Procedures
This section defines procedures that are common to FEC Encoding IDs 3
and 4.
5.1. General
 The B (maximum source block length in symbols) and E (encoding symbol
 length in bytes) parameters are first determined, as explained in the
 following sections.
+ The B (maximum source block length in symbols), E (encoding symbol
+ length in bytes) and G (number of encoding symbols per group)
+ 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
 algorithm specified in [2]. To that purpose, the B, L (object
 transfer length in bytes), and E arguments are provided. As a
 result, the object is partitioned into N source blocks. These blocks
 are numbered consecutively from 0 to N1. The first I source blocks
 consist of A_large source symbols, the remaining NI source blocks
 consist of A_small source symbols. Each source symbol is E bytes in
 length, except perhaps the last symbol which may be shorter.
+ Then, the source object MUST be partitioned using the block
+ partitioning algorithm specified in [RFC5052]. To that purpose, the
+ B, L (object transfer length in bytes), and E arguments are provided.
+ As a result, the object is partitioned into N source blocks. These
+ blocks are numbered consecutively from 0 to N1. The first I source
+ blocks consist of A_large source symbols, the remaining NI source
+ blocks consist of A_small source symbols. Each source symbol is E
+ bytes in length, except perhaps the last symbol which may be shorter.
 For each block the actual number of encoding symbols is determined,
 as explained in the following section.
+ Then, the max_n (maximum number of encoding symbols generated for any
+ 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 "nalgorithm" detailed in Section 5.5.
Then, FEC encoding and decoding can be done block per block,
independently. To that purpose, a parity check matrix is created,
that forms a system of linear equations between the source and repair
symbols of a given block, where the basic operator is XOR.
This parity check matrix is logically divided into two parts: the
 left side (from column 0 to k1) which describes the occurrence of
 each source symbol in the equation system; and the right side (from
 column k to n1) which describes the occurrence of each repair symbol
 in the equation system. An entry (a "1") in the matrix at position
 (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
 LDPCStaircase and LDPCTriangle schemes is the construction of the
 right submatrix.
+ left side (from column 0 to k1) describes the occurrences of each
+ source symbol in the system of linear equations; the right side (from
+ column k to n1) describes the occurrences of each repair symbol in
+ the system of linear equations. The only difference between the
+ LDPCStaircase and LDPCTriangle schemes is the construction of this
+ right submatrix. An entry (a "1") in the matrix at position (i,j)
+ (i.e., at row i and column j) means that the symbol with ESI j
+ 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
largely impact the erasure recovery capabilities of the LDPC* FEC.
In particular, sending parity symbols in sequence is suboptimal.
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
 determined (respectively in Section 5.2, Section 5.3 and
 Section 5.4), how encoding symbol groups are created (Section 5.5),
 and finally specify the PRNG (Section 5.6).
+ The following sections detail how the B, E, G, max_nand n parameters
+ are determined (respectively in Section 5.2, Section 5.3, Section 5.4
+ and Section 5.5), how encoding symbol groups are created
+ (Section 5.6), and finally Section 5.7 details the PRNG.
5.2. Determining the Maximum Source Block Length (B)
The B parameter (maximum source block length in symbols) depends on
 several parameters: the code rate (rate), the Encoding Symbol ID
 field length of the FEC Payload ID (20 bits), as well as possible
 internal codec limitations.
+ several parameters: the code rate (CR), the Encoding Symbol ID field
+ length of the FEC Payload ID (20 bits), as well as possible internal
+ codec limitations.
The B parameter cannot be larger than the following values, derived
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:
 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
 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,
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
 maximum source block length is 2^^15. Other limitations may also
 apply, for instance because of a limited working memory size. This
 decision MUST be clarified at implementation time, when the target
 use case is known. This results in a max2_B limitation.
+ field. In that case, if for instance 1/2 <= CR < 1, then the maximum
+ source block length is 2^^15. Other limitations may also apply, for
+ instance because of a limited working memory size. This decision
+ MUST be clarified at implementation time, when the target use case is
+ known. This results in a max2_B limitation.
Then, B is given by:
B = min(max1_B, max2_B)
Note that this calculation is only required at the coder, since the B
parameter is communicated to the decoder through the FEC OTI.
5.3. Determining the Encoding Symbol Length (E) and Number of Encoding
Symbols per Group (G)
The E parameter usually depends on the maximum transmission unit on
 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
+ 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
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
symbol (G=1) remains below but close to the PMTU.
However other considerations can exist. For instance, the E
parameter can be made a function of the object transfer length.
Indeed, LDPC codes are known to offer better protection for large
blocks. In case of small objects, it can be advantageous to reduce
the encoding symbol length (E) in order to artificially increase the
number of symbols, and therefore the block size.
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
rate (G symbols are lost for each packet erasure), this strategy
might or might not be appropriate. A balance must therefore be
found.
The current specification does not mandate any value for either E or
G. The current specification only provides an example of possible
 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
 to the FEC OTI.
+ choices for E and G. Note that this choice is done by the sender, and
+ the E and G parameters are then communicated to the receiver thanks
+ 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:
 First define the target packet payload size, pkt_sz (at most equal to
 the PMTU minus the size of the various protocol headers). The pkt_sz
 must be chosen in such a way that the symbol size is an integer.
 This can require that pkt_sz be a multiple of 4, 8 or 16 (see 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.
+ Let us assume that the trivial decoding algorithm sketched in
+ Section 6.4 is used. First define the target packet payload size,
+ pkt_sz (at most equal to the PMTU minus the size of the various
+ protocol headers). The pkt_sz must be chosen in such a way that the
+ symbol size is an integer. This can require that pkt_sz be a
+ multiple of 4, 8 or 16 (see 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.
+++++
 Number of packets  G  Symbol size  k 
+++++
 4000 <= nb_pkts  1  pkt_sz  4000 <= k 
    
 1000 <= nb_pkts < 4000  4  pkt_sz / 4  4000 <= k < 16000 
    
 500 <= nb_pkts < 1000  8  pkt_sz / 8  4000 <= k < 8000 
    
 1 <= nb_pkts < 500  16  pkt_sz / 16  16 <= k < 8000 
+++++
5.4. Determining the Number of Encoding Symbols of a Block

 The following algorithm, also called "nalgorithm", explains how to
 determine the actual number of encoding symbols for a given block.
+5.4. Determining the Maximum Number of Encoding Symbols Generated for
+ Any Source Block (max_n)
 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:
B: Maximum source block length, for any source block. Section 5.2
 explains how to determine its value.

 k: Current source block length. This parameter is given by the
 source blocking algorithm.
+ MAY be used to determine its value.
 rate: FEC code rate. It is provided by the user, for instance
 when starting a FLUTE sending application. It is expressed as a
 floating point value. The rate value must be such that the
+ CR: FEC code rate, which is provided by the user (e.g., when
+ starting a FLUTE sending application). It is expressed as a
+ floating point value. The CR value must be such that the
resulting number of encoding symbols per block is at most equal to
2^^20 (Section 4.1).
Output:
max_n: Maximum number of encoding symbols generated for any source
 block

 n: Number of encoding symbols generated for this source block
+ block.
Algorithm:
 max_n = floor(B / rate);
+ max_n = ceil(B / CR);
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
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 "nalgorithm", 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:
 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: Given by the source blocking algorithm
+ k: Current source block length. At a sender or receiver, the
+ 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:
 n: Number of encoding symbols generated for this source block
+ n: Number of encoding symbols generated for this source block.
Algorithm:
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
Payload ID information of the packet MUST refer to the first encoding
symbol. It MUST then be possible to identify each symbol from this
single FEC Payload ID. To that purpose, the symbols of an Encoding
Symbol Group (i.e. packet):
o MUST all be either source symbols, or repair symbols. Therefore
only source packets and repair packets are permitted, not mixed
ones.
o are identified by a function, sender(resp.
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,
* for a receiver, the ESI information contained in the FEC
Payload ID.
and returns a list of G Encoding Symbol IDs. In case of a source
packet, the G Encoding Symbol IDs are chosen consecutively, by
incrementing the ESI. In case of a repair packet, the G repair
symbols are chosen randomly, as explained below.
@@ 607,21 +661,21 @@
void
initialize_tables ()
{
int i;
int randInd;
int backup;
txseqToID = malloc((nk) * sizeof(int));
IDtoTxseq = malloc((nk) * sizeof(int));
/* initialize the two tables that map ID
 * (i.e. ESIk) to/from TxSequence. */
+ * (i.e., ESIk) to/from TxSequence. */
for (i = 0; i < n  k; i++) {
IDtoTxseq[i] = i;
txseqToID[i] = i;
}
/* now randomize everything */
for (i = 0; i < n  k; i++) {
randInd = rand(n  k);
backup = IDtoTxseq[i];
IDtoTxseq[i] = IDtoTxseq[randInd];
IDtoTxseq[randInd] = backup;
@@ 659,21 +713,21 @@
for (i = 0; i < G; i++) {
ESIs[i] =
k +
txseqToID[(i + (PktIdx  nbSourcePkts) * G)
% (n  k)];
}
}
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
first ESI, esi0, that is contained in the FEC Payload ID.
/*
* Determine the sequence of ESIs for the packet received.
* Warning: use only when G > 1.
* esi0 (IN): : ESI contained in the FEC Payload ID
* ESIs[] (OUT): list of ESIs for the packet
*/
void
@@ 692,110 +746,86 @@
/* this is a repair packet */
for (i = 0; i < G; i++) {
ESIs[i] =
k +
txseqToID[(i + IDtoTxseq[esi0  k])
% (n  k)];
}
}
}
5.6. Pseudo Random Number Generator
+5.7. Pseudo Random Number Generator
 The present FEC Encoding ID relies on a pseudorandom number
 generator (PRNG) that must be fully specified, in particular in order
 to enable the receivers and the senders to build the same parity
 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 FEC Encoding IDs 3 and 4 rely on a pseudorandom number generator
+ (PRNG) that must be fully specified, in particular in order to enable
+ the receivers and the senders to build the same parity check matrix.
 The following implementation uses the Park and Miller algorithm with
 the optimization suggested by D. Carta in [11].
+ The minimal standard generator [PM88] MUST be 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.
 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.
 /*
 * Initialize the PRNG with a seed between
 * 1 and 0x7FFFFFFE (i.e. 2^^312) inclusive.
 */
 void srand (unsigned long s)
 {
 if ((s > 0) && (s < 0x7FFFFFFF))
 seed = s;
 else
 exit(1);
 }
+ This PRNG produces a 31 bit value between 1 and 0x7FFFFFFE (2^^312)
+ inclusive. When it is desired to scale the pseudo random number
+ between 0 and maxv1 inclusive, one must keep the most significant
+ bits of the value returned by the PRNG (the least significant bits
+ are known to be less random and modulo based solutions should be
+ avoided [PTVF92]). The following algorithm MUST be used:
 /*
 * Returns a random integer in [0; maxv1]
 * Derived from rand31pmc, Robin Whittle,
 * September 20th, 2005.
 * http://www.firstpr.com.au/dsp/rand31/
 * 16807 multiplier constant (7^^5)
 * 0x7FFFFFFF modulo constant (2^^311)
 * The inner PRNG produces a value between 1 and
 * 0x7FFFFFFE (2^^312) inclusive.
 * This value is then scaled between 0 and maxv1
 * inclusive.
 */
 unsigned long
 rand (unsigned long maxv)
 {
 unsigned long hi, lo;
+ Input:
 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 = (long)lo;
 /* don't use modulo, least significant bits are less random
 * than most significant bits [Numerical Recipes in C] */
 return ((unsigned long)
 ((double)seed * (double)maxv / (double)0x7FFFFFFF));
 }
+ raw_value: random integer generated by the inner PRNG algorithm,
+ between 1 and 0x7FFFFFFE (2^^312) inclusive.
+
+ maxv: upper bound used during the scaling operation.
+
+ Output:
+
+ scaled_value: random integer between 0 and maxv1 inclusive.
+
+ Algorithm:
+
+ 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 LDPCStaircase Scheme
6.1. General
The LDPCStaircase scheme is identified by the FullySpecified FEC
Encoding ID 3.
The PRNG used by the LDPCStaircase scheme must be initialized by a
 seed. This PRNG seed is an optional instancespecific FEC OTI
 attribute (Section 4.2.3). When this PRNG seed is not carried within
 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.
+ seed. This PRNG seed is an instancespecific FEC OTI attribute
+ (Section 4.2.3).
6.2. Parity Check Matrix Creation
The LDPCStaircase matrix can be divided into two parts: the left
side of the matrix defines in which equations the source symbols are
involved; the right side of the matrix defines in which equations the
repair symbols are involved.
The left side is generated with the following algorithm:
 /*
 * Derived from: "Software for Low Density Parity Check Codes"
 * Version of 20011118, 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
* guarantee a homogeneous "1" distribution */
for (h = 3*k1; h >= 0; h) {
u[h] = h % (nk);
}
/* left limit within the list of possible choices, u[] */
t = 0;
for (j = 0; j < k; j++) { /* for each source symbol column */
for (h = 0; h < 3; h++) { /* add 3 "1s" */
@@ 821,30 +851,29 @@
matrix_insert_entry(i, j);
}
}
}
/* Add extra bits to avoid rows with less than two "1s".
* This is needed when the code rate is smaller than 2/5. */
for (i = 0; i < nk; i++) { /* for each row */
if (degree_of_row(i) == 0) {
j = rand(k);
 e = matrix_insert_entry(i, j);
+ matrix_insert_entry(i, j);
}
if (degree_of_row(i) == 1) {
do {
j = rand(k);
} while (matrix_has_entry(i, j));
matrix_insert_entry(i, j);
}
}

The right side (the staircase) is generated by the following
algorithm:
matrix_insert_entry(0, k); /* first row */
for (i = 1; i < nk; i++) { /* for the following rows */
matrix_insert_entry(i, k+i); /* identity */
matrix_insert_entry(i, k+i1); /* staircase */
}
Note that just after creating this parity check matrix, when encoding
@@ 841,51 +870,51 @@
The right side (the staircase) is generated by the following
algorithm:
matrix_insert_entry(0, k); /* first row */
for (i = 1; i < nk; i++) { /* for the following rows */
matrix_insert_entry(i, k+i); /* identity */
matrix_insert_entry(i, k+i1); /* staircase */
}
Note that just after creating this parity check matrix, when encoding
 symbol groups are used (i.e. G > 1), the function initializing the
 two random permutation tables (Section 5.5) MUST be called. This is
+ symbol groups are used (i.e., G > 1), the function initializing the
+ two random permutation tables (Section 5.6) MUST be called. This is
true both at a sender and at a receiver.
6.3. Encoding
Thanks to the staircase matrix, repair symbol creation is
straightforward: each repair symbol is equal to the sum of all source
symbols in the associated equation, plus the previous repair symbol
(except for the first repair symbol). Therefore encoding MUST follow
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
Decoding basically consists in solving a system of nk linear
equations whose variables are the n source and repair symbols. Of
course, the final goal is to recover the value of the k source
symbols only.
To that purpose, many techniques are possible. One of them is the
 following trivial algorithm [12]: given a set of linear equations, if
 one of them has only one remaining unknown variable, then the value
 of this variable is that of the constant term. So, replace this
 variable by its value in all the remaining linear equations and
+ following trivial algorithm [ZP74]: given a set of linear equations,
+ if one of them has only one remaining unknown variable, then the
+ value of this variable is that of the constant term. So, replace
+ this variable by its value in all the remaining linear equations and
reiterate. The value of several variables can therefore be found
recursively. Applied to LDPC FEC codes working over an erasure
channel, the parity check matrix defines a set of linear equations
whose variables are the source symbols and repair symbols. Receiving
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
possible decoding technique. Hybrid solutions that start by using
the trivial algorithm above and finish with a Gaussian elimination
are also possible.
Because interoperability does not depend on the decoding algorithm
used, the current document does not recommend any particular
technique. This choice is left to the codec developer.
@@ 897,25 +926,22 @@
the above trivial algorithm. Depending on the target use case, the
codec developer will favor one feature or the other.
7. Full Specification of the LDPCTriangle Scheme
7.1. General
LDPCTriangle is identified by the FullySpecified FEC Encoding ID 4.
The PRNG used by the LDPCTriangle scheme must be initialized by a
 seed. This PRNG seed is an optional instancespecific FEC OTI
 attribute (Section 4.2.3). When this PRNG seed is not carried within
 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.
+ seed. This PRNG seed is an instancespecific FEC OTI attribute
+ (Section 4.2.3).
7.2. Parity Check Matrix Creation
The LDPCTriangle matrix can be divided into two parts: the left side
of the matrix defines in which equations the source symbols are
involved; the right side of the matrix defines in which equations the
repair symbols are involved.
The left side is generated with the same algorithm as that of LDPC
Staircase (Section 6.2).
@@ 929,176 +955,355 @@
matrix_insert_entry(i, k+i1); /* staircase */
/* now fill the triangle */
j = i1;
for (l = 0; l < j; l++) { /* limit the # of "1s" added */
j = rand(j);
matrix_insert_entry(i, k+j);
}
}
Note that just after creating this parity check matrix, when encoding
 symbol groups are used (i.e. G > 1), the function initializing the
 two random permutation tables (Section 5.5) MUST be called. This is
+ symbol groups are used (i.e., G > 1), the function initializing the
+ two random permutation tables (Section 5.6) MUST be called. This is
true both at a sender and at a receiver.
7.3. Encoding
Here also repair symbol creation is straightforward: each repair
 symbol is equal to the sum of all source symbols in the associated
 equation, plus the repair symbols in the triangle. Therefore
+ symbol of ESI i is equal to the sum of all source and repair symbols
+ (with ESI lower than i) in the associated equation. Therefore
encoding MUST follow the natural repair symbol order: start with the
first repair symbol, and generate repair symbol with ESI i before
 symbol ESI i+1.
+ symbol with ESI i+1.
7.4. Decoding
Decoding basically consists in solving a system of nk linear
equations, whose variables are the n source and repair symbols. Of
course, the final goal is to recover the value of the k source
symbols only. To that purpose, many techniques are possible, as
explained in Section 6.4.
Because interoperability does not depend on the decoding algorithm
used, the current document does not recommend any particular
technique. This choice is left to the codec implementer.
8. Security Considerations
 Data delivery can be subject to denialofservice attacks by
 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 SHA1 hash [4] of an object may be
 appended before transmission, and the SHA1 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.
+8.1. Problem Statement
 Another security concern is that some FEC information may be obtained
 by receivers outofband 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.
+ A content delivery system is potentially subject to many attacks:
+ some of them target the network (e.g., to compromise the routing
+ infrastructure, by compromising the congestion control component),
+ others target the Content Delivery Protocol (CDP) (e.g., to
+ compromise its normal behavior), and finally some attacks target the
+ content itself. Since this document focuses on a FEC building block
+ independently of any particular CDP (even if ALC and NORM are two
+ 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 nonfree 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 inband (e.g., in an EXT_FTI or FDT Instance) or out
+ ofband (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 RSASSAPKCS1v1_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 HMACSHA1
+ 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 precheck);
+
+ 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
+ predistributing 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
+ predistributing 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 inband (i.e., in an EXT_FTI or in an
+ FDT Instance containing FEC OTI for the object) or outofband (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 inband in an EXT_FTI header
+ extension SHOULD be protected by one of the perpacket 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 outofband (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
Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA
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 FullySpecified FEC Encoding ID 3 under the
"ietf:rmt:fec:encoding" namespace to "LDPC Staircase Codes".
This document assigns the FullySpecified FEC Encoding ID 4 under the
"ietf:rmt:fec:encoding" namespace to "LDPC Triangle Codes".
10. Acknowledgments
 Section 5.4 is derived from a previous InternetDraft, and we would
+ Section 5.5 is derived from a previous InternetDraft, and we would
like to thank S. Peltotalo and J. Peltotalo for their contribution.
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.1. Normative References
 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement
 Levels", RFC 2119, BCP 14, March 1997.

 [2] Watson, M., Luby, M., and L. Vicisano, "Forward Error
 Correction (FEC) Building Block",
 draftietfrmtfecbbrevised07.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.
+ [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
+ Requirement Levels", RFC 2119, BCP 14, March 1997.
 [4] "HMAC: KeyedHashing for Message Authentication", RFC 2104,
 February 1997.
+ [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error
+ Correction (FEC) Building Block", RFC 5052, August 2007.
 [5] "Timed Efficient Stream LossTolerant Authentication (TESLA):
 Multicast Source Authentication Transform Introduction",
 RFC 4082, June 2005.
+ [RFC3453] 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.
11.2. Informative References
 [6] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of
 Four Large Block FEC Codecs: LDPC, LDGM, LDGMStaircase and
 LDGMTriangle, Plus a ReedSolomon Small Block FEC Codec",
 INRIA Research Report RR5225, June 2004.
+ [ZP74] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low
+ Density Codes for Transmission in a Channel with
+ Erasures", Translated from Problemy Peredachi
+ Informatsii, Vol.10, No. 1, pp.1528, JanuaryMarch 1974.
 [7] Neumann, C., Roca, V., Francillon, A., and D. Furodet, "Impacts
 of Packet Scheduling and Packet Loss Distribution on FEC
 Performances: Observations and Recommendations", ACM CoNEXT'05
 Conference, Toulouse, France (an extended version is available
 as INRIA Research Report RR5578), October 2005.
+ [RN04] Roca, V. and C. Neumann, "Design, Evaluation and
+ Comparison of Four Large Block FEC Codecs: LDPC, LDGM,
+ LDGMStaircase and LDGMTriangle, Plus a ReedSolomon
+ Small Block FEC Codec", INRIA Research Report RR5225,
+ June 2004.
 [8] Roca, V., Neumann, C., and J. Laboure, "LDPCStaircase/
 LDPCTriangle Codec Reference Implementation", INRIA Rhone
 Alpes and STMicroelectronics,
+ [NRFF05] Neumann, C., Roca, V., Francillon, A., and D. Furodet,
+ "Impacts of Packet Scheduling and Packet Loss Distribution
+ on FEC Performances: Observations and Recommendations",
+ ACM CoNEXT'05 Conference, Toulouse, France (an extended
+ version is available as INRIA Research Report RR5578),
+ October 2005.
+
+ [LDPCcodec]
+ Roca, V., Neumann, C., Cunche, M., and J. Laboure, "LDPC
+ Staircase/LDPCTriangle Codec Reference Implementation",
+ INRIA RhoneAlpes and STMicroelectronics,
http://planetebcast.inrialpes.fr/.
 [9] MacKay, D., "Information Theory, Inference and Learning
 Algorithms", Cambridge University Press, ISBN: 0521642981,
 2003.
+ [MK03] MacKay, D., "Information Theory, Inference and Learning
+ Algorithms", Cambridge University Press, ISBN: 0521
+ 642981, 2003.
 [10] Park, S. and K. Miller, "Random Number Generators: Good Ones
 are Hard to Find", Communications of the ACM, Vol. 31, No. 10,
 pp.11921201, 1988.
+ [PM88] Park, S. and K. Miller, "Random Number Generators: Good
+ Ones are Hard to Find", Communications of the ACM, Vol.
+ 31, No. 10, pp.11921201, 1988.
 [11] Carta, D., "Two Fast Implementations of the Minimal Standard
 Random Number Generator", Communications of the ACM, Vol. 33,
 No. 1, pp.8788, January 1990.
+ [CA90] Carta, D., "Two Fast Implementations of the Minimal
+ Standard Random Number Generator", Communications of the
+ ACM, Vol. 33, No. 1, pp.8788, January 1990.
 [12] Zyablov, V. and M. Pinsker, "Decoding Complexity of LowDensity
 Codes for Transmission in a Channel with Erasures", Translated
 from Problemy Peredachi Informatsii, Vol.10, No. 1, pp.1528,
 JanuaryMarch 1974.
+ [PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery,
+ "Numerical Recipies in C; Second Edition", Cambridge
+ University Press, ISBN: 0521431085, 1992.
 [13] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered
 Coding (ALC) Protocol Instantiation",
+ [draftietfrmtpialcrevised]
+ Luby, M., Watson, M., and L. Vicisano, "Asynchronous
+ Layered Coding (ALC) Protocol Instantiation",
draftietfrmtpialcrevised04.txt (work in progress),
February 2007.
 [14] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca,
+ [draftietfrmtpinormrevised]
+ Adamson, B., Bormann, C., Handley, M., and J. Macker,
+ "Negativeacknowledgment (NACK)Oriented Reliable
+ Multicast (NORM) Protocol",
+ draftietfrmtpinormrevised05.txt (work in progress),
+ March 2007.
+
+ [draftietfrmtfluterevised]
+ Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca,
"FLUTE  File Delivery over Unidirectional Transport",
 draftietfrmtfluterevised03.txt (work in progress),
 January 2007.
+ draftietfrmtfluterevised05.txt (work in progress),
+ October 2007.
 [15] Adamson, B., Bormann, C., Handley, M., and J. Macker,
 "Negativeacknowledgment (NACK)Oriented Reliable Multicast
 (NORM) Protocol", draftietfrmtpinormrevised04.txt (work
 in progress), March 2007.
+ [RFC3447] Jonsson, J. and B. Kaliski, "PublicKey Cryptography
+ Standards (PKCS) #1: RSA Cryptography Specifications
+ Version 2.1", RFC 3447, February 2003.
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
 the details omitted here):
+ [RFC2104] "HMAC: KeyedHashing for Message Authentication",
+ RFC 2104, February 1997.
+
+ [RFC4082] "Timed Efficient Stream LossTolerant Authentication
+ (TESLA): Multicast Source Authentication Transform
+ Introduction", RFC 4082, June 2005.
+
+ [RFC3275] Eastlake, D., Reagle, J., and D. Solo, "(Extensible Markup
+ Language) XMLSignature 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 maxv1
+ 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^^312) inclusive.
+ */
+ void srand (unsigned long s)
+ {
+ if ((s > 0) && (s < 0x7FFFFFFF))
+ seed = s;
+ else
+ exit(1);
+ }
+
+ /*
+ * Returns a random integer in [0; maxv1]
+ * Derived from rand31pmc, Robin Whittle,
+ * September 20th, 2005.
+ * http://www.firstpr.com.au/dsp/rand31/
+ * 16807 multiplier constant (7^^5)
+ * 0x7FFFFFFF modulo constant (2^^311)
+ * The inner PRNG produces a value between 1 and
+ * 0x7FFFFFFE (2^^312) inclusive.
+ * This value is then scaled between 0 and maxv1
+ * 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
+ [LDPCcodec] for the details omitted here):
Initialization: allocate a table partial_sum[nk] of buffers, each
buffer being of size the symbol size. There's one
entry per equation since the buffers are meant to
store the partial sum of each equation; Reset all
the buffers to zero;
/*
* For each newly received or decoded symbol, try to make progress
* in the decoding of the associated source block.
@@ 1182,31 +1387,31 @@
Authors' Addresses
Vincent Roca
INRIA
655, av. de l'Europe
Inovallee; Montbonnot
ST ISMIER cedex 38334
France
 Email: vincent.roca@inrialpes.fr
 URI: http://planete.inrialpes.fr/~roca/
+ Email: vincent.roca@inria.fr
+ URI: http://planete.inrialpes.fr/people/roca/
Christoph Neumann
 Thomson Research
 46, Quai A. Le Gallo
 Boulogne Cedex 92648
+ Thomson
+ 12, bd de Metz
+ Rennes 35700
France
Email: christoph.neumann@thomson.net
 URI: http://planete.inrialpes.fr/~chneuman/
+ URI: http://planete.inrialpes.fr/people/chneuman/
David Furodet
STMicroelectronics
12, Rue Jules Horowitz
BP217
Grenoble Cedex 38019
France
Email: david.furodet@st.com
URI: http://www.st.com/