 1/draftietffecframeldpc02.txt 20121004 12:14:20.953425850 +0200
+++ 2/draftietffecframeldpc03.txt 20121004 12:14:20.993425856 +0200
@@ 1,21 +1,21 @@
FecFrame V. Roca
InternetDraft INRIA
Intended status: Standards Track M. Cunche
Expires: September 9, 2012 NICTA
+Expires: April 7, 2013 INSALyon/INRIA
J. Lacan
 ISAE/LAASCNRS
 March 8, 2012
+ ISAE, Univ. of Toulouse
+ October 4, 2012
Simple LDPCStaircase Forward Error Correction (FEC) Scheme for FECFRAME
 draftietffecframeldpc02
+ draftietffecframeldpc03
Abstract
This document describes a fullyspecified simple FEC scheme for LDPC
Staircase codes that can be used to protect media streams along the
lines defined by the FECFRAME framework. These codes have many
interesting properties: they are systematic codes, they perform close
to ideal codes in many usecases and they also feature very high
encoding and decoding throughputs. LDPCStaircase codes are
therefore a good solution to protect a single high bitrate source
@@ 32,21 +32,21 @@
InternetDrafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as InternetDrafts. The list of current Internet
Drafts is at http://datatracker.ietf.org/drafts/current/.
InternetDrafts are draft documents valid for a maximum of six months
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."
 This InternetDraft will expire on September 9, 2012.
+ This InternetDraft will expire on April 7, 2013.
Copyright Notice
Copyright (c) 2012 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/licenseinfo) in effect on the date of
publication of this document. Please review these documents
@@ 70,33 +70,33 @@
4.2. ADU Block Creation . . . . . . . . . . . . . . . . . . . . 7
4.3. Source Block Creation . . . . . . . . . . . . . . . . . . 9
5. LDPCStaircase FEC Scheme for Arbitrary ADU Flows . . . . . . 10
5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 10
5.1.1. FEC Framework Configuration Information . . . . . . . 10
5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . . 12
5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 13
5.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . . 14
5.3. FEC Code Specification . . . . . . . . . . . . . . . . . . 14
6. Security Considerations . . . . . . . . . . . . . . . . . . . 14
 6.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 14
+ 6.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 15
6.1.1. Access to Confidential Content . . . . . . . . . . . . 15
6.1.2. Content Corruption . . . . . . . . . . . . . . . . . . 15
6.2. Attacks Against the FEC Parameters . . . . . . . . . . . . 15
6.3. When Several Source Flows are to be Protected Together . . 16
6.4. Baseline Secure FEC Framework Operation . . . . . . . . . 16
7. Operations and Management Considerations . . . . . . . . . . . 16
7.1. Operational Recommendations . . . . . . . . . . . . . . . 16
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18
9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 18
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 18
10.1. Normative References . . . . . . . . . . . . . . . . . . . 18
 10.2. Informative References . . . . . . . . . . . . . . . . . . 19
+ 10.2. Informative References . . . . . . . . . . . . . . . . . . 18
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20
1. Introduction
The use of Forward Error Correction (FEC) codes is a classic solution
to improve the reliability of unicast, multicast and broadcast
Content Delivery Protocols (CDP) and applications [RFC3453]. The
[RFC6363] document describes a generic framework to use FEC schemes
with media delivery applications, and for instance with realtime
streaming media applications based on the RTP realtime protocol.
@@ 287,56 +287,55 @@
o there MUST be exactly one source symbol per ADUI, and therefore
per ADU;
o there MUST be exactly one repair symbol per FEC Repair Packet;
o there MUST be exactly one source block per ADU block;
o the use of the LDPCStaircase scheme is such that there MUST be
exactly one encoding symbol per group, i.e., G MUST be equal to 1
[RFC5170];
4.2. ADU Block Creation
 Two kinds of limitations MUST be considered, that impact the ADU
 block creation:
+ Two kinds of limitations exist that impact the ADU block creation:
o at the FEC Scheme level: the FEC Scheme and the FEC codec have
limitations that define a maximum source block size;
 o at the FECFRAME instance level: the target usecase MAY have real
 time constraints that MAY define a maximum ADU block size;
+ o at the FECFRAME instance level: the target usecase can have real
+ time constraints that can/will define a maximum ADU block size;
Note that terminology "maximum source block size" and "maximum ADU
block size" depends on the point of view that is adopted (FEC Scheme
versus FECFRAME instance). However, in this document, both refer to
the same value since Section 4.1 requires there is exactly one source
symbol per ADU. We now detail each of these aspects.
The maximum source block size in symbols, max_k, depends on several
parameters: the code rate (CR), the Encoding Symbol ID (ESI) field
length in the Explicit Source/Repair FEC Payload ID (16 bits), as
well as possible internal codec limitations. More specifically,
max_k cannot be larger than the following values, derived from the
ESI field size limitation, for a given code rate:
max1_k = 2^^(16  ceil(Log2(1/CR)))
Some common max1_k values are:
o CR == 1 (no repair symbol): max1_k = 2^^16 = 65536 symbols
o 1/2 <= CR < 1: max1_k = 2^^15 = 32,768 symbols
o 1/4 <= CR < 1/2: max1_k = 2^^14 = 16,384 symbols
 Additionally, a codec MAY impose other limitations on the maximum
+ Additionally, a codec can impose other limitations on the maximum
source block size, for instance, because of a limited working memory
size. This decision MUST be clarified at implementation time, when
the target usecase is known. This results in a max2_k limitation.
Then, max_k is given by:
max_k = min(max1_k, max2_k)
Note that this calculation is only required at the encoder (sender),
since the actual k parameter (k <= max_k) is communicated to the
decoder (receiver) through the Explicit Source/Repair FEC Payload ID.
 The source ADU flows MAY have realtime constraints. When there are
+ The source ADU flows can have realtime constraints. When there are
multiple flows, with different realtime constraints, let us consider
the most stringent constraints (see [RFC6363], section 10.2, item 6
for recommendations when several flows are globally protected). In
that case the maximum number of ADUs of an ADU block must not exceed
a certain threshold since it directly impacts the decoding delay.
The larger the ADU block size, the longer a decoder may have to wait
until it has received a sufficient number of encoding symbols for
decoding to succeed, and therefore the larger the decoding delay.
When the target usecase is known, these realtime constraints result
in an upper bound to the ADU block size, max_rt.
@@ 588,30 +587,32 @@
 Source Block Number (SBN)  Encoding Symbol ID (ESI) 
+++++++++++++++++++++++++++++++++
 Source Block Length (k)  Number Encoding Symbols (n) 
+++++++++++++++++++++++++++++++++
Figure 7: Repair FEC Payload ID encoding format.
5.2. Procedures
The following procedures apply:
 o The source block creation procedures are specified in Section 4.3.
 o The SBN value is incremented for each new source block, starting
 at 0 for the first block of the ADU flow. Wrapping to zero will
 happen for long sessions, after value 2^^16  1.
 o The ESI of encoding symbols is managed sequentially, starting at 0
 for the first symbol. The first k values (0 <= ESI <= k  1)
 identify source symbols, whereas the last nk values (k <= ESI <=
 n  1) identify repair symbols.
 o The FEC repair packet creation procedures are specified in
 Section 5.1.3.
+ o The source block creation MUST follow the procedures specified in
+ Section 4.3.
+ o The SBN value MUST start with value 0 for the first block of the
+ ADU flow and MUST be incremented by 1 for each new source block.
+ Wrapping to zero will happen for long sessions, after value 2^^16
+  1.
+ o The ESI of encoding symbols MUST start with value 0 for the first
+ symbol and MUST be managed sequentially. The first k values (0 <=
+ ESI <= k  1) identify source symbols whereas the last nk values
+ (k <= ESI <= n  1) identify repair symbols.
+ o The FEC repair packet creation MUST follow the procedures
+ specified in Section 5.1.3.
5.3. FEC Code Specification
The present document inherits from [RFC5170] the specification of the
core LDPCStaircase codes for a packet erasure transmission channel.
Because of the requirement to have exactly one encoding symbol per
group, i.e., because G MUST be equal to 1 (Section 4.1), several
parts of [RFC5170] are useless. In particular, this is the case of
Section 5.6. "Identifying the G Symbols of an Encoding Symbol
@@ 710,90 +712,85 @@
The FEC Framework document [RFC6363] provides a comprehensive
analysis of operations and management considerations applicable to
FEC schemes. Therefore the present section only discusses topics
that are specific to the use of LDPCStaircase codes as specified in
this document.
7.1. Operational Recommendations
LDPCStaircase codes have excellent erasure recovery capabilities
with large source blocks, close to ideal MDS codes. For instance,
 independently of FECFRAME, with source block size k=1024, CR=2/3,
 N1=5, G=1, with a hybrid ITerative/Maximum Likelihood (IT/ML)
+ independently of FECFRAME, with source block size k=1024 symbols,
+ CR=2/3, N1=7, G=1, a hybrid ITerative/Maximum Likelihood (IT/ML)
decoding approach (see below) and when all symbols are sent in a
 random order (see below), the average overhead amounts to 0.64%
 (corresponding to 6.5 symbols in addition to k) and receiving 1046
 symbols (corresponding to a 2.1% overhead) is sufficient to reduce
 the decoding failure probability to 5.9*10^^5. This is why these
 codes are a good solution to protect a single high bitrate source
 flow as in [Matsuzono10], or to protect globally several midrate
 source flows within a single FECFRAME instance: in both cases the
 source block size can be assumed to be equal to a few hundreds (or
 more) source symbols.
+ random order, the average overhead amounts to 0.237% (i.e., receiving
+ 2.43 symbols in addition to k enables a successful decoding with a
+ probability 0.5) and an overhead of 1.46% (i.e., receiving 15 symbols
+ in addition to k) is sufficient to reduce the decoding failure
+ probability to 8.2*10^^5. This is why these codes are a good
+ solution to protect a single high bitrate source flow as in
+ [Matsuzono10], or to protect globally several midrate source flows
+ within a single FECFRAME instance: in both cases the source block
+ size can be assumed to be equal to a few hundreds (or more) source
+ symbols.
LDPCStaircase codes are also a good solution whenever processing
requirements at a software encoder or decoder must be kept to a
minimum. This is true when the decoder uses an IT decoding
algorithm, or an ML algorithm (we use a Gaussian Elimination as the
 ML algorithm) when this latter is carefully implemented and the
 source block size kept reasonable, or a mixture of both techniques
 which is the recommended solution [Cunche08][CunchePHD10]. For
 instance an average decoding speed between 1.3 Gbps (corresponding to
 a very bad channel, close to the theoretical decoding limit and
 requiring an ML decoding) and 4.3 Gbps (corresponding to a medium
 quality channel where IT decoding is sufficient) are easily achieved
 with a source block size composed of k=1024 source symbols, a code
 rate CR=2/3 (i.e., 512 repair symbols), 1024 byte long symbols, G=1,
 and N1=5, on an Intel Xeon 5120/1.86GHz workstation running Linux/64
 bits. Additionally, with a hybrid IT/ML approach, a receiver can
 decide if and when ML decoding is used, depending on local criteria
 (e.g., battery or CPU capabilities), independently from other
 receivers.
+ ML algorithm) when this latter is carefully implemented, or a mixture
+ of both techniques which is the recommended solution
+ [Cunche08][CunchePHD10][LDPCcodecOpenFEC]. For instance an average
+ decoding speed between 1.78 Gbps (overhead of 2 symbols in addition
+ to k, corresponding to a very bad channel, close to the theoretical
+ decoding limit, where ML decoding is required) and 3.41 Gbps
+ (corresponding to a medium quality channel where IT decoding is
+ sufficient) is easily achieved with a source block size composed of
+ k=1024 source symbols, a code rate CR=2/3 (i.e., 512 repair symbols),
+ 1024 byte long symbols, G=1, and N1=7, on an Intel Xeon 5120/1.86GHz
+ workstation running Linux/64 bits. Under the same conditions, on a
+ Samsung Galaxy SII (GTI9100P model, featuring an ARM CortexA9/1.2
+ GHz processor and running Android 2.3.4), decoding speed is between
+ 278 Mbps (overhead of 2 symbols and ML decoding) and 626 Mbps (IT
+ decoding).
As the source block size decreases, the erasure recovery capabilities
of LDPC codes in general also decrease. In the case of LDPC
 Staircase codes, in order to compensate this phenomenon, it is
 recommended to increase the N1 parameter (e.g., experiments carried
 out in [Matsuzono10] use N1=7 if k=170 symbols, and N1=5 otherwise)
 and to use a hybrid IT/ML decoding approach. For instance,
 independently of FECFRAME, with a small source block size k=256
 symbols, CR=2/3, N1=7, and G=1, 8he average overhead amounts to 0.71%
 (corresponding to 1.8 symbols in addition to k), and receiving 271
 symbols (corresponding to a 5.9% overhead) is sufficient to reduce
 the decoding failure probability to 5.9*10^^5. Using N1=9 or 10
 further improves these results if need be, which also enables to use
 LDPCStaircase codes with k=100 symbols for instance.
+ Staircase codes, in order to limit this phenomenon, it is recommended
+ to use a value of the N1 parameter at least equal to 7 (e.g.,
+ experiments carried out in [Matsuzono10] use N1=7 if k=170 symbols,
+ and N1=5 otherwise). For instance, independently of FECFRAME, with
+ source block size k=256 symbols, CR=2/3, N1=7, and G=1, the average
+ overhead amounts to 0.706% (i.e., receiving 1.8 symbols in addition
+ to k enables a successful decoding with a probability 0.5), and an
+ overhead of 5.86% (i.e., receiving 15 symbols ina addition to k) is
+ sufficient to reduce the decoding failure probability to 5.9*10^^5.
 With very small source blocks (e.g., a few tens symbols), using for
 instance ReedSolomon codes [SIMPLE_RS] or 2D parity check codes MAY
 be more appropriate.
+ With very small source blocks (e.g., a few tens of symbols), using
+ for instance ReedSolomon codes [SIMPLE_RS] or 2D parity check codes
+ may be more appropriate.
The way the FEC Repair Packets are transmitted is of high importance.
A good strategy, that works well for any kind of channel loss model,
consists in sending FEC Repair Packets in random order (rather than
in sequence) while FEC Source Packets are sent first and in sequence.
Sending all packets in a random order is another possibility, but it
requires that all repair symbols for a source block be produced
first, which adds some extra delay at a sender.
8. IANA Considerations
 Values of FEC Encoding IDs are subject to IANA registration.
 [RFC6363] defines general guidelines on IANA considerations. In
 particular it defines a registry called FEC Framework (FECFRAME) FEC
 Encoding IDs whose values are granted on an IETF Consensus basis.

This document registers one value in the FEC Framework (FECFRAME) FEC
 Encoding IDs registry as follows:
 o XXX refers to the Simple LDPCStaircase [RFC5170] FEC Scheme for
 Arbitrary Packet Flows.
+ Encoding IDs registry [RFC6363] as follows:
+ o XXX refers to the Simple LDPCStaircase FEC Scheme for Arbitrary
+ Packet Flows, as defined in Section 5 of this document.
9. Acknowledgments
The authors want to thank K. Matsuzono, J. Detchart and H. Asaeda for
their contributions in evaluating the use of LDPCStaircase codes in
the context of FECFRAME [Matsuzono10].
10. References
10.1. Normative References
@@ 881,24 +877,27 @@
INRIA
655, av. de l'Europe
Inovallee; Montbonnot
ST ISMIER cedex 38334
France
Email: vincent.roca@inria.fr
URI: http://planete.inrialpes.fr/people/roca/
Mathieu Cunche
 NICTA
 Australia
+ INSALyon/INRIA
+ Laboratoire CITI
+ 6 av. des Arts
+ Villeurbanne cedex 69621
+ France
 Email: mathieu.cunche@nicta.com.au
+ Email: mathieu.cunche@inria.fr
URI: http://mathieu.cunche.free.fr/
Jerome Lacan
 ISAE/LAASCNRS
 1, place Emile Blouin
 Toulouse 31056
+ ISAE, Univ. of Toulouse
+ 10 av. Edouard Belin; BP 54032
+ Toulouse cedex 4 31055
France
Email: jerome.lacan@isae.fr
 URI: http://dmi.ensica.fr/auteur.php3?id_auteur=5
+ URI: http://personnel.isae.fr/jeromelacan/