--- 1/draft-ietf-rmt-bb-fec-ldpc-05.txt 2007-05-08 01:12:07.000000000 +0200
+++ 2/draft-ietf-rmt-bb-fec-ldpc-06.txt 2007-05-08 01:12:07.000000000 +0200
@@ -1,22 +1,22 @@
RMT V. Roca
Internet-Draft INRIA
Intended status: Experimental C. Neumann
-Expires: September 30, 2007 Thomson Research
+Expires: November 8, 2007 Thomson Research
D. Furodet
STMicroelectronics
- March 29, 2007
+ May 7, 2007
Low Density Parity Check (LDPC) Staircase and Triangle Forward Error
Correction (FEC) Schemes
- draft-ietf-rmt-bb-fec-ldpc-05.txt
+ draft-ietf-rmt-bb-fec-ldpc-06.txt
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
@@ -27,34 +27,33 @@
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
- This Internet-Draft will expire on September 30, 2007.
+ This Internet-Draft will expire on November 8, 2007.
Copyright Notice
Copyright (C) The IETF Trust (2007).
Abstract
This document describes two Fully-Specified FEC Schemes, LDPC-
Staircase and LDPC-Triangle, and their application to the reliable
delivery of objects on packet erasure channels. These systematic FEC
codes belong to the well known class of ``Low Density Parity Check''
- (LDPC) codes, and are large block FEC codes in these sense of
- RFC3453.
+ (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
3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 7
4. Formats and Codes . . . . . . . . . . . . . . . . . . . . . . 8
@@ -94,38 +93,38 @@
1. Introduction
RFC 3453 [3] introduces large block FEC codes as an alternative to
small block FEC codes like Reed-Solomon. 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 Fully-Specified FEC Encoding ID 3
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
- with the LDPC-Triangle FEC codes [4][7]. Both schemes belong to the
+ with the LDPC-Triangle FEC codes [6][9]. Both schemes belong to the
broad class of large block codes.
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.
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 [6].
+ available and distributed under a GNU/LGPL license [8].
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].
3. Definitions, Notations and Abbreviations
3.1. Definitions
@@ -283,21 +282,21 @@
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 [11] or NORM [13] protocols).
+ mechanism is used (e.g. within the ALC [13] or NORM [15] protocols).
0 1 2 3
0 1 2 3 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) | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| Transfer-Length (L) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoding Symbol Length (E) | G | B (MSB) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
@@ -318,21 +317,21 @@
for field alignment purposes.
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-
bit word of the EXT_FTI, and the remaining 12 least significant
bits (LSB) are in the fourth 32-bit 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 [12], the following XML attributes must be described
+ a FLUTE session [14], the following XML attributes must be described
for the associated object:
o FEC-OTI-FEC-Encoding-ID
o FEC-OTI-Transfer-length
o FEC-OTI-Encoding-Symbol-Length
o FEC-OTI-Maximum-Source-Block-Length
o FEC-OTI-Max-Number-of-Encoding-Symbols
@@ -399,21 +398,21 @@
(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
LDPC-Staircase and LDPC-Triangle schemes is the construction of the
right sub-matrix.
When the parity symbols have been created, the sender will transmit
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 [5].
+ interested reader will find more details in [7].
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).
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
@@ -698,31 +697,31 @@
% (n - k)];
}
}
}
5.6. Pseudo Random Number Generator
The present FEC Encoding ID relies on a pseudo-random 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 [8] is used. It
+ check matrix. The minimal standard generator [10] is used. It
defines a simple multiplicative congruential algorithm: Ij+1 = A * Ij
(modulo M), with the following choices: A = 7^^5 = 16807 and M =
2^^31 - 1 = 2147483647. Several implementations of this PRNG are
known and discussed in the literature. All of them provide the same
sequence of pseudo random numbers. A validation criteria of such a
PRNG is the following: if seed = 1, then the 10,000th value returned
MUST be equal to 1043618065.
The following implementation uses the Park and Miller algorithm with
- the optimization suggested by D. Carta in [9].
+ the optimization suggested by D. Carta in [11].
unsigned long seed;
/*
* Initialize the PRNG with a seed between
* 1 and 0x7FFFFFFE (i.e. 2^^31-2) inclusive.
*/
void srand (unsigned long s)
{
if ((s > 0) && (s < 0x7FFFFFFF))
@@ -749,21 +748,21 @@
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 = (long)lo;
/* don't use modulo, least significant bits are less random
- * than most significant bits [Numerical Recipies in C] */
+ * than most significant bits [Numerical Recipes in C] */
return ((unsigned long)
((double)seed * (double)maxv / (double)0x7FFFFFFF));
}
6. Full Specification of the LDPC-Staircase Scheme
6.1. General
The LDPC-Staircase scheme is identified by the Fully-Specified FEC
Encoding ID 3.
@@ -863,21 +862,21 @@
and generate repair symbol with ESI i before symbol ESI i+1.
6.4. Decoding
Decoding basically consists in solving a system of n-k 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 [10]: given a set of linear equations, if
+ following trivial algorithm [12]: given a set of linear equations, if
one of them has only one remaining unknown variable, then the value
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.
@@ -957,109 +956,148 @@
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
- The security considerations for this document are the same as that of
- [2].
+ Data delivery can be subject to denial-of-service 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 SHA-1 hash [4] of an object may be
+ appended before transmission, and the SHA-1 hash is computed and
+ checked after the object is decoded but before it is delivered to an
+ application. Source authentication SHOULD be provided, for example
+ by including a digital signature verifiable by the receiver computed
+ on top of the hash value. It is also RECOMMENDED that a packet
+ authentication protocol such as TESLA [5] be used to detect and
+ discard corrupted packets upon arrival. Furthermore, it is
+ RECOMMENDED that Reverse Path Forwarding checks be enabled in all
+ network routers and switches along the path from the sender to
+ receivers to limit the possibility of a bad agent successfully
+ injecting a corrupted packet into the multicast tree data path.
+
+ Another security concern is that some FEC information may be obtained
+ by receivers out-of-band in a session description, and if the session
+ description is forged or corrupted then the receivers will not use
+ the correct protocol for decoding content from received packets. To
+ avoid these problems, it is RECOMMENDED that measures be taken to
+ prevent receivers from accepting incorrect session descriptions,
+ e.g., by using source authentication to ensure that receivers only
+ accept legitimate session descriptions from authorized senders.
9. IANA Considerations
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]. This document assigns the Fully-
- Specified FEC Encoding ID 3 under the ietf:rmt:fec:encoding name-
- space to "LDPC Staircase Codes", and the Fully-Specified FEC Encoding
- ID 4 under the ietf:rmt:fec:encoding name-space to "LDPC Triangle
- Codes".
+ apply to this document, see [2].
+
+ This document assigns the Fully-Specified FEC Encoding ID 3 under the
+ "ietf:rmt:fec:encoding" name-space to "LDPC Staircase Codes".
+
+ This document assigns the Fully-Specified FEC Encoding ID 4 under the
+ "ietf:rmt:fec:encoding" name-space to "LDPC Triangle Codes".
10. Acknowledgments
Section 5.4 is derived from a previous Internet-Draft, 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.
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",
- draft-ietf-rmt-fec-bb-revised-06.txt (work in progress),
- March 2007.
+ draft-ietf-rmt-fec-bb-revised-07.txt (work in progress),
+ April 2007.
[3] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M.,
and J. Crowcroft, "The Use of Forward Error Correction (FEC) in
Reliable Multicast", RFC 3453, December 2002.
+ [4] "HMAC: Keyed-Hashing for Message Authentication", RFC 2104,
+ February 1997.
+
+ [5] "Timed Efficient Stream Loss-Tolerant Authentication (TESLA):
+ Multicast Source Authentication Transform Introduction",
+ RFC 4082, June 2005.
+
11.2. Informative References
- [4] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of
+ [6] Roca, V. and C. Neumann, "Design, Evaluation and Comparison of
Four Large Block FEC Codecs: LDPC, LDGM, LDGM-Staircase and
LDGM-Triangle, Plus a Reed-Solomon Small Block FEC Codec",
INRIA Research Report RR-5225, June 2004.
- [5] Neumann, C., Roca, V., Francillon, A., and D. Furodet, "Impacts
+ [7] Neumann, C., Roca, V., Francillon, A., and D. Furodet, "Impacts
of Packet Scheduling and Packet Loss Distribution on FEC
Performances: Observations and Recommendations", ACM CoNEXT'05
Conference, Toulouse, France (an extended version is available
as INRIA Research Report RR-5578), October 2005.
- [6] Roca, V., Neumann, C., and J. Laboure, "LDPC-Staircase/
+ [8] Roca, V., Neumann, C., and J. Laboure, "LDPC-Staircase/
LDPC-Triangle Codec Reference Implementation", INRIA Rhone-
Alpes and STMicroelectronics,
http://planete-bcast.inrialpes.fr/.
- [7] MacKay, D., "Information Theory, Inference and Learning
+ [9] MacKay, D., "Information Theory, Inference and Learning
Algorithms", Cambridge University Press, ISBN: 0521642981,
2003.
- [8] Park, S. and K. Miller, "Random Number Generators: Good Ones
+ [10] Park, S. and K. Miller, "Random Number Generators: Good Ones
are Hard to Find", Communications of the ACM, Vol. 31, No. 10,
pp.1192-1201, 1988.
- [9] Carta, D., "Two Fast Implementations of the Minimal Standard
+ [11] Carta, D., "Two Fast Implementations of the Minimal Standard
Random Number Generator", Communications of the ACM, Vol. 33,
No. 1, pp.87-88, January 1990.
- [10] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low-Density
+ [12] Zyablov, V. and M. Pinsker, "Decoding Complexity of Low-Density
Codes for Transmission in a Channel with Erasures", Translated
from Problemy Peredachi Informatsii, Vol.10, No. 1, pp.15-28,
January-March 1974.
- [11] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered
+ [13] Luby, M., Watson, M., and L. Vicisano, "Asynchronous Layered
Coding (ALC) Protocol Instantiation",
draft-ietf-rmt-pi-alc-revised-04.txt (work in progress),
February 2007.
- [12] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca,
+ [14] Paila, T., Walsh, R., Luby, M., Lehtonen, R., and V. Roca,
"FLUTE - File Delivery over Unidirectional Transport",
draft-ietf-rmt-flute-revised-03.txt (work in progress),
January 2007.
- [13] Adamson, B., Bormann, C., Handley, M., and J. Macker,
+ [15] Adamson, B., Bormann, C., Handley, M., and J. Macker,
"Negative-acknowledgment (NACK)-Oriented Reliable Multicast
(NORM) Protocol", draft-ietf-rmt-pi-norm-revised-04.txt (work
in progress), March 2007.
Appendix A. Trivial Decoding Algorithm (Informative Only)
- A trivial decoding algorithm is sketched below (please see [6] for
+ A trivial decoding algorithm is sketched below (please see [8] for
the details omitted here):
Initialization: allocate a table partial_sum[n-k] 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
@@ -1140,21 +1178,21 @@
Free the list of equations having symbols decoded;
Return;
}
Authors' Addresses
Vincent Roca
INRIA
655, av. de l'Europe
- Zirst; Montbonnot
+ Inovallee; Montbonnot
ST ISMIER cedex 38334
France
Email: vincent.roca@inrialpes.fr
URI: http://planete.inrialpes.fr/~roca/
Christoph Neumann
Thomson Research
46, Quai A. Le Gallo
Boulogne Cedex 92648