FecFrame V. Roca
Internet-Draft M. Cunche
Intended status: Standards Track INRIA
Expires: January 4, 2010 J. Lacan
ISAE/LAAS-CNRS
July 3, 2009
LDPC-Staircase Forward Error Correction (FEC) Schemes for FECFRAME
draft-roca-fecframe-ldpc-00
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79. This document may contain material
from IETF Documents or IETF Contributions published or made publicly
available before November 10, 2008. The person(s) controlling the
copyright in some of this material may not have granted the IETF
Trust the right to allow modifications of such material outside the
IETF Standards Process. Without obtaining an adequate license from
the person(s) controlling the copyright in such materials, this
document may not be modified outside the IETF Standards Process, and
derivative works of it may not be created outside the IETF Standards
Process, except to format it for publication as an RFC or to
translate it into languages other than English.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts 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 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 January 4, 2010.
Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved.
Roca, et al. Expires January 4, 2010 [Page 1]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Roca, et al. Expires January 4, 2010 [Page 2]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
Abstract
This document describes two fully-specified FEC schemes for LDPC-
Staircase codes that can be used to protect media streams along the
lines defined by the FECFRAME framework. It inherits from RFC5170
the specifications of LDPC-Staircase codes. More specifically, these
codes belong to the well-known class of "Low Density Parity Check"
codes. They are large block FEC codes, in the sense of RFC3453,
since they can efficiently deal with a large number of source
symbols. They are also systematic codes, since the source symbols
are part of the encoding symbols. Finally, they can perform close to
ideal codes in many use-cases, since decoding is often possible after
receiving a small number of encoding symbols in addition to the
strict minimum, while keeping very high encoding and decoding
throughputs with a software codec.
LDPC-Staircase codes are therefore a good solution for the protection
of high bitrate ADU flows, or when several mid-bitrate flows are
protected together by a single FECFRAME instance. They are also a
good solution whenever the processing load of a software encoder or
decoder must be kept to a minimum.
The first scheme describes the use of LDPC-Staircase codes in a
FECFRAME instance in order to protect arbitrary ADU flows. The
second scheme is similar to the first scheme, with the exception that
it is for a single sequenced ADU flow.
Roca, et al. Expires January 4, 2010 [Page 3]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 7
3. Definitions Notations and Abbreviations . . . . . . . . . . . 8
3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 8
3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 11
4. Common Procedures Related to the ADU Block and Source
Block Creation . . . . . . . . . . . . . . . . . . . . . . . . 12
4.1. Problem Statement and Related Constraints . . . . . . . . 12
4.2. Source Block Creation . . . . . . . . . . . . . . . . . . 13
5. LDPC-Staircase FEC Scheme for Arbitrary ADU Flows . . . . . . 15
5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 15
5.1.1. FEC Framework Configuration Information . . . . . . . 15
5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . . 16
5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 17
5.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . . 18
5.3. FEC Code Specification . . . . . . . . . . . . . . . . . . 18
6. LDPC-Staircase FEC Scheme for a Single Sequenced Flow . . . . 19
7. Security Considerations . . . . . . . . . . . . . . . . . . . 20
7.1. Problem Statement . . . . . . . . . . . . . . . . . . . . 20
7.2. Attacks Against the Data Flow . . . . . . . . . . . . . . 20
7.2.1. Access to Confidential Objects . . . . . . . . . . . . 20
7.2.2. Content Corruption . . . . . . . . . . . . . . . . . . 20
7.3. Attacks Against the FEC Parameters . . . . . . . . . . . . 21
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23
9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 24
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 25
10.1. Normative References . . . . . . . . . . . . . . . . . . . 25
10.2. Informative References . . . . . . . . . . . . . . . . . . 25
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 27
Roca, et al. Expires January 4, 2010 [Page 4]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
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
[FECFRAME-FRAMEWORK] document describes a generic framework to use
FEC schemes with media delivery applications, and for instance with
real-time streaming media applications based on the RTP real-time
protocol. Similarly the [RFC5052] document describes a generic
framework to use FEC schemes with with objects (e.g., files) delivery
applications based on the ALC [RMT-PI-ALC] and NORM [RMT-PI-NORM]
reliable multicast transport protocols.
More specifically, the [RFC5053] (Raptor) and [RFC5170] (LDPC-
Staircase and LDPC-Triangle) FEC schemes introduce erasure codes
based on sparse parity check matrices for object delivery protocols
like ALC and NORM. Similarly, the [RFC5510] document introduces
Reed-Solomon codes based on Vandermonde matrices for the same object
delivery protocols. All these codes are systematic codes, meaning
that the k source symbols are part of the n encoding symbols.
Additionally, the Reed-Solomon FEC codes belong to the class of
Maximum Distance Separable (MDS) codes that are optimal in terms of
erasure recovery capabilities. It means that a receiver can recover
the k source symbols from any set of exactly k encoding symbols out
of n. This is not the case with either Raptor or LDPC-Staircase
codes, and these codes require a certain number of encoding symbols
in excess to k. However, this number is small in practice when an
appropriate decoding scheme is used at the receiver [SPSC08].
Another key difference is the high encoding/decoding complexity of
Reed-Solomon codecs compared to Raptor or LDPC-Staircase codes. A
difference of an order of magnitude or more in terms of decoding
speed is often noticed between Reed-Solomon and LDPC-Staircase
software decoders [SPSC08].
The present document focuses on LDPC-Staircase codes. Because of
their key features, these codes are a good solution for the
protection of high bitrate source flows, for instance when several
mid-rate ADU flows are globally protected by a single FECFRAME
instance. They are also a good solution whenever processing
requirements at a software encoder or decoder must be kept to a
minimum, no matter the ADU flow(s) bitrate.
This documents inherits from [RFC5170] the specifications of the core
LDPC-Staircase codes. Therefore this document specifies only the
information specific to the FECFRAME context and refers to [RFC5170]
for the core specifications of the codes. To that purpose, the
present document introduces two schemes:
Roca, et al. Expires January 4, 2010 [Page 5]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
o The first scheme describes the use of LDPC-Staircase codes in a
FECFRAME instance in order to protect arbitrary ADU flows.
o The second scheme is similar to the first scheme, with the
exception that it is for a single sequenced ADU flow.
Finally, a publicly available reference implementation of these codes
is available and distributed under a GNU/LGPL (Lesser General Public
License) [LDPC-codec].
Roca, et al. Expires January 4, 2010 [Page 6]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
2. Terminology
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 RFC 2119 [RFC2119].
Roca, et al. Expires January 4, 2010 [Page 7]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
3. Definitions Notations and Abbreviations
3.1. Definitions
This document uses the following terms and definitions. Some of them
are FEC scheme specific and are in line with [RFC5052]:
Source symbol: unit of data used during the encoding process.
Encoding symbol: unit of data generated by the encoding process.
With systematic codes, source symbols are part of the encoding
symbols.
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. By
definition, the code rate is such that: 0 < code rate <= 1. 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. The Reed-Solomon codes introduced in
this document are systematic.
Source block: a block of k source symbols that are considered
together for the encoding.
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.
Some of them are FECFRAME framework specific and are in line with
[FECFRAME-FRAMEWORK]:
Application Data Unit (ADU): a unit of data coming from (sender) or
given to (receiver) the media delivery application. Depending
on the use-case, an ADU may use an RTP encapsulation.
(Source) ADU Flow: a flow of ADUs from a media delivery application
and to which FEC protection is applied. Depending on the use-
case, several ADU flows can be protected together by the
FECFRAME framework.
Roca, et al. Expires January 4, 2010 [Page 8]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
ADU Block: a set of ADUs that are considered together by the
FECFRAME instance for the purpose of the FEC scheme. Along
with the F[], L[], and Pad[] fields, they form the set of
source symbols over which FEC encoding will be performed
(either in a global way or separately depending on the FEC
scheme used).
ADU Information (ADUI): a unit of data constituted by the ADU and
the associated Flow ID, Length and Padding fields
(Section 4.2) This is the unit of data that is used to define
source symbols.
FEC Framework Configuration Information: the FEC scheme specific
information that enables the synchronization of the FECFRAME
sender and receiver instances.
FEC Source Packet: a data packet submitted to (sender) or received
from (receiver) the transport protocol. It contains an ADU
along with its optional Explicit Source FEC Payload ID, when
applicable.
FEC Repair Packet: a repair packet submitted to (sender) or received
from (receiver) the transport protocol. It contains a repair
symbol along with its Repair FEC Payload ID.
The above terminology is illustrated in Figure 1 from the sender
point of view:
Roca, et al. Expires January 4, 2010 [Page 9]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
+----------------------+
| Application |
+----------------------+
|
ADU flow | (1) Application Data Unit (ADU)
v
+----------------------+ +----------------+
| FEC Framework | | |
| |------------------------- >| FEC Scheme |
|(2) Construct an ADU | (4) Source Symbols for | |
| Block | this Source Block |(5) Perform FEC |
|(3) Construct ADU Info| | Encoding |
|(7) Construct FEC Src |< -------------------------| |
| Packets and FEC |(6) Ex src FEC Payload Ids,| |
| Repair Packets | Repair FEC Payload Ids,| |
+----------------------+ Repair Symbols +----------------+
| |
|(8) FEC Src |(8') FEC Repair
| packets | packets
v v
+----------------------+
| Transport Layer |
| (e.g., UDP ) |
+----------------------+
Figure 1: Terminology used in this document (sender point of view).
3.2. Notations
This document uses the following notations: Some of them are FEC
scheme specific:
k denotes the number of source symbols in a source block.
max_k denotes the maximum number of source symbols for any source
block.
n_r denotes the number of repair symbols generated for a source
block.
n denotes the number of encoding symbols generated for a source
block. Therefore: n = k + n_r.
max_n denotes the maximum number of encoding symbols generated for
any source block.
Roca, et al. Expires January 4, 2010 [Page 10]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
E denotes the encoding symbol length in bytes.
CR denotes the "code rate", i.e., the k/n ratio.
N1 denotes the target number of "1s" per column in the left side
of the parity check matrix.
N1m3 denotes the value N1 - 3.
G denotes the number of Repair Symbols in a given FEC Repair
Packet. This value may differ between different FEC Repair
Packets.
a^^b denotes a raised to the power b.
Some of them are FECFRAME framework specific:
B denotes the number of ADUs per ADU block.
max_B denotes the maximum number of ADUs for any ADU block.
3.3. Abbreviations
This document uses the following abbreviations:
ADU stands for Application Data Unit.
ESI stands for Encoding Symbol ID.
FFCI stands for FEC Framework Configuration Information.
LDPC stands for Low Density Parity Check.
RS stands for Reed-Solomon.
MDS stands for Maximum Distance Separable code.
Roca, et al. Expires January 4, 2010 [Page 11]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
4. Common Procedures Related to the ADU Block and Source Block Creation
This section introduces the procedures that are used during the ADU
block and the related Source Block creation, for the various FEC
schemes considered.
4.1. Problem Statement and Related Constraints
Several aspects must be considered, that impact the ADU Block and
Source Block creations:
o the distribution of ADU sizes for the ADU flow(s) protected by the
FECFRAME instance;
o the maximum source block size (max_k parameter);
o the potential real-time constraints, that impact the maximum ADU
block size, since the larger the block size, the larger the
decoding delay;
We now detail each of these aspects.
In its most general form the FECFRAME framework and the LDPC-
Staircase FEC schemes are meant to protect a set of independent
flows. Since the flows have no relationship to one another, the ADU
size of each flow will potentially vary significantly. Even in the
special case of a single flow, the ADU sizes may largely vary (e.g.,
the various frames of a "Group of Pictures (GOP) of an H.264 flow can
have different sizes). This diversity must be addressed by the
source block creation procedure since the LDPC-Staircase FEC schemes
require a constant encoding symbol size (E parameter).
The maximum source block length 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
Roca, et al. Expires January 4, 2010 [Page 12]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
o 1/4 <= CR < 1/2: max1_k = 2^^14 = 16,384 symbols
Additionally, a codec MAY impose other limitations on the maximum
block size, 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_k limitation.
Then, max_k is given by:
max_k = min(max1_k, max2_k)
Note that this calculation is only required at the coder, since the
actual k parameter (k <= max_k) is communicated to the decoder
through the Repair FEC Payload ID.
The source ADU flows usually have real-time constraints. It means
that the maximum number of ADUs of an ADU block must not exceed a
certain threshold since it directly impacts the decoding delay. It
is the role of the developer, who knows the ADU Flow(s) real-time
features, to define an appropriate upper bound to the ADU Block size,
max_B.
4.2. Source Block Creation
During Source Block creation, the ADU block is always encoded as a
single source block. The creation of the ADU Block MUST take into
account the constraints mentioned in Section 4.1. More specifically,
the sender first defines an appropriate E value, valid for the whole
session duration and transmitted in the FSSI. Then the sender
accumulates ADUs until either (1) B equals max_B, or (2) the
corresponding k equals max_k. As a consequence, there are a total of
B <= max_B ADUs in this ADU Block.
Then, for the ADU i, with 0 <= i <= B-1, 3 bytes are prepended
(Figure 2):
o The first byte, FID[i] (Flow ID), contains the integer identifier
associated to the source ADU flow to which this ADU belongs to.
It is assumed that a single byte is sufficient, or said
differently, that no more than 256 flows will be protected by a
single instance of the FECFRAME framework.
o The following two bytes, L[i] (Length), contain the length of this
ADU, in network byte order (i.e., big endian). This length is for
the ADU itself and does not include the FID[i], L[i], or Pad[i]
fields.
Zero padding is also added if needed, in field Pad[i], for alignment
Roca, et al. Expires January 4, 2010 [Page 13]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
purposes on source symbol boundaries. This can happen at most once
per ADU. The data unit resulting from the ADU and the F[], L[] and
Pad[] fields, is called ADU Information (or ADUI).
Thanks to the padding, a source symbol will never straddle several
ADUIs. As a direct consequence, a source symbol will never straddle
several FEC Source Packets.
Enc Symbol Len (E) Enc Symbol Len (E) Enc Symbol Len (E)
< ------------------ >< ------------------ >< ------------------ >
+----+----+-----------------------+--------+
|F[0]|L[0]| R[0] | Pad[1] |
+----+----+----------+------------+--------+
|F[1]|L[1]| R[1] |
+----+----+----------+--------------------------------------+----+
|F[2]|L[2]| R[2] |P[2]|
+----+----+----------+--------------------------------------+----+
|F[3]|L[3]| R[3] | P3|
+----+----+------+---+
\_______________________________ _______________________________/
\/
global FEC encoding
+--------------------+
| Repair 7 |
+--------------------+
. .
. .
+--------------------+
| Repair 13 |
+--------------------+
Figure 2: Source block creation with the global encoding scheme, for
code rate 1/2 (equal number of source and repair symbols, 7 in this
example).
Note that neither the initial 3 bytes nor the optional padding are
sent over the network. However, they are considered during FEC
encoding. It means that a receiver who lost a certain FEC Source
Packet (e.g., the UDP datagram containing this FEC source packet)
will be able to recover the ADUI if FEC decoding succeeds. Thanks to
the initial 3 bytes, this receiver will get rid of the padding (if
any) and identify the corresponding ADU flow.
Roca, et al. Expires January 4, 2010 [Page 14]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
5. LDPC-Staircase FEC Scheme for Arbitrary ADU Flows
5.1. Formats and Codes
5.1.1. FEC Framework Configuration Information
The FEC Framework Configuration Information (or FFCI) includes
information that MUST be communicated between the sender and
receiver(s). More specifically, it enables the synchronization of
the FECFRAME sender and receiver instances. It includes both
mandatory elements and scheme-specific elements, as detailed below.
5.1.1.1. Mandatory Information
o FEC Encoding ID: the value assigned to this fully-specified FEC
scheme MUST be XXX, as assigned by IANA (Section 8).
When SDP is used to communicate the FFCI, this FEC Encoding ID is
carried in the 'encoding-id' parameter.
5.1.1.2. FEC Scheme-Specific Information
The FEC Scheme Specific Information (FSSI) includes elements that are
specific to the present FEC scheme. More precisely:
PRNG seed: a non-negative 32 bit integer used as the seed of the
Pseudo Random Number Generator, as defined in [RFC5170].
Encoding symbol length (E): a non-negative integer indicating the
length of each encoding symbol in bytes.
N1m3: an integer between 0 (default) and 7, inclusive. The number
of "1s" per column in the left side of the parity check matrix,
N1, is then equal to N1m3 + 3, as specified in [RFC5170].
The encoding format consists of the following 7 octet field:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| PRNG seed |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoding Symbol Length (E) | N1m3 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: FSSI encoding format.
Roca, et al. Expires January 4, 2010 [Page 15]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
These elements are required both by the sender (LDPC-Staircase
encoder) and the receiver(s) (LDPC-Staircase decoder). When SDP is
used to communicate the FFCI, this FEC scheme-specific information is
carried in the 'fssi' parameter as an opaque octet string, using a
Base64 encoding, as specified in [SDP_ELEMENTS].
5.1.2. Explicit Source FEC Payload ID
A FEC source packet MUST contain an Explicit Source FEC Payload ID
that is appended to the end of the packet as illustrated in Figure 4.
+--------------------------------+
| IP Header |
+--------------------------------+
| Transport Header |
+--------------------------------+
| ADU |
+--------------------------------+
| Explicit Source FEC Payload ID |
+--------------------------------+
Figure 4: Structure of a FEC Source Packet with the Explicit Source
FEC Payload ID.
More precisely, the Explicit Source FEC Payload ID is composed of the
Source Block Number and the Encoding Symbol ID (Figure 5):
Source Block Number (SBN) (16 bit field): this field identifies the
source block to which this FEC source packet belongs.
Encoding Symbol ID (ESI) (16 bit field): this field identifies the
first source symbol associated to this FEC source packet in the
source block (remember there can be several source symbols per
ADUI, Section 4.2). This value belongs to interval {0..k - 1}
inclusive for source symbols.
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 (SBN) | Encoding Symbol ID (ESI) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 5: Source FEC Payload ID encoding format.
Roca, et al. Expires January 4, 2010 [Page 16]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
5.1.3. Repair FEC Payload ID
A FEC repair packet MUST contain a Repair FEC Payload ID that is
prepended to the Repair Symbol(s) as illustrated in Figure 6. There
can be several Repair Symbols per FEC Repair Packet as explained
below.
+--------------------------------+
| IP Header |
+--------------------------------+
| Transport Header |
+--------------------------------+
| Repair FEC Payload ID |
+--------------------------------+
| Repair Symbol(s) |
+--------------------------------+
Figure 6: Structure of a FEC Repair Packet with the Repair FEC
Payload ID.
More precisely, the Repair FEC Payload ID is composed of the Source
Block Number, the Encoding Symbol ID and the Source Block Length
(Figure 7):
Source Block Number (SBN) (16 bit field): this field identifies the
source block to which the FEC repair packet belongs.
Encoding Symbol ID (ESI) (16 bit field) this field identifies the
first repair symbol contained in this FEC repair packet (remember
there can be several repair symbols per FEC repair packet). This
value belongs to interval {k..n - 1} inclusive for repair symbols.
Source Block Length (k) (16 bit field): this field provides the
number of source symbols for this source block, i.e., the k
parameter.
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 (SBN) | Encoding Symbol ID (ESI) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Block Length (k) | Number Encoding Symbols (n) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 7: Repair FEC Payload ID encoding format.
The number of Repair Symbols for a given FEC Repair Packet, G, is
Roca, et al. Expires January 4, 2010 [Page 17]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
defined as follows. A sender can choose a G > 1 in order to limit
the transmission overhead due to the various protocol headers.
However G MUST be such that the corresponding IP datagram size does
not exceed the maximum Path Maximum Transmission Unit (or PMTU). The
G value is not communicated as such to the receiver(s). However a
receiver can easily calculate G by dividing the FEC Repair Packet
size (minus the Repair FEC Payload ID size) by the E parameter.
Another aspect is to define which Repair Symbols are contained in a
given FEC Repair Packet. In any case, the Repair FEC Payload ID of a
packet always refers to the first Repair Symbol. At a sender, the
remaining Repair Symbols can be deduced from the ESI of the first
Repair Symbol by using the sender_find_ESIs_of_group() function, as
specified in [RFC5170]. At a receiver, the other Repair Symbols can
be deduced from the ESI of the first Repair Symbol by using the
receiver_find_ESIs_of_group() function, as specified in [RFC5170].
By using these functions, the Repair Symbols considered for a given
FEC Repair Packet are not in sequence. The motivation is to avoid
loosing several, in sequence, Repair Symbols, since this situation is
known to negatively impact erasure recover capabilities.
5.2. Procedures
The following procedures apply:
o The source block creation procedures are specified in Section 4.2.
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 (from 0 to k - 1
inclusive) identify source symbols, whereas the last n-k values
(from k to n - 1 inclusive) identify repair symbols.
o The FEC repair packet creation procedures are specified in
Section 5.1.3.
5.3. FEC Code Specification
The present document inherits from [RFC5170] the specification of the
core LDPC-Staircase codes for a packet erasure transmission channel.
Roca, et al. Expires January 4, 2010 [Page 18]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
6. LDPC-Staircase FEC Scheme for a Single Sequenced Flow
TBD
Roca, et al. Expires January 4, 2010 [Page 19]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
7. Security Considerations
7.1. Problem Statement
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 various FEC schemes,
this section only discusses the additional threats that their use
within the FECFRAME framework can create to an arbitrary CDP.
More specifically, these attacks may have several goals:
o those that are meant to give access to a confidential content
(e.g., in case of a non-free content),
o those that try to corrupt the ADU Flows being transmitted (e.g.,
to prevent a receiver from using it),
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 FEC Source/Repair Packets) or against the FEC
parameters that are sent either in-band (e.g., in the Repair FEC
Payload ID) or out-of-band (e.g., in a session description).
7.2. Attacks Against the Data Flow
First of all, let us consider the attacks against the data flow.
7.2.1. Access to Confidential Objects
Access control to the ADU Flow being transmitted is typically
provided by means of encryption. This encryption can be done within
the content provider itself, by the application (for instance by
using the Secure Real-time Transport Protocol (SRTP) [RFC3711]), or
at the Network Layer, on a packet per packet basis 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.
7.2.2. Content Corruption
Protection against corruptions (e.g., after sending forged FEC
Source/Repair Packets) is achieved by means of a content integrity
Roca, et al. Expires January 4, 2010 [Page 20]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
verification/sender authentication scheme. This service is usually
provided at the packet level. In this case, after removing all
forged packets, the ADU Flow may be sometimes recovered. Several
techniques can provide this source authentication/content integrity
service:
o at the application level, the Secure Real-time Transport Protocol
(SRTP) [RFC3711] provides several solutions to verify the
authenticate and check the integrity of RTP and RTCP messages,
among other services. For instance, associated to the Timed
Efficient Stream Loss-Tolerant Authentication (TESLA) [RFC4383],
SRTP is an attractive 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 with TESLA. Other building blocks can be used
within SRTP to provide authentication/content integrity services.
o at the Network Layer, IPSec/AH offers an integrity verification
mechanism that can be used to provide authentication/content
integrity services.
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
pre-distributing 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
pre-distributing 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.
7.3. Attacks Against the FEC Parameters
Let us now consider attacks against the FEC parameters included in
the FFCI that are usually sent out-of-band (e.g., in a session
description). Attacks on these FEC parameters can prevent the
decoding of the associated object. For instance modifying the PRNG
seed or N1m3 fields will lead a receiver to consider a different
parity check matrix, i.e., a different code. Modifying the E
Roca, et al. Expires January 4, 2010 [Page 21]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
parameter will lead a receiver to consider bad Repair Symbols for a
received FEC Repair Packet.
It is therefore RECOMMENDED that security measures be taken to
guarantee the FFCI integrity. When the FFCI is sent out-of-band 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.
Roca, et al. Expires January 4, 2010 [Page 22]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
8. IANA Considerations
Values of FEC Encoding IDs are subject to IANA registration. TBD...
Roca, et al. Expires January 4, 2010 [Page 23]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
9. Acknowledgments
TBD
Roca, et al. Expires January 4, 2010 [Page 24]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
10. References
10.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119.
[RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity
Check (LDPC) Forward Error Correction", RFC 5170,
June 2008.
[FECFRAME-FRAMEWORK]
Watson, M., "Forward Error Correction (FEC) Framework",
draft-ietf-fecframe-framework-03 (Work in Progress),
October 2008.
[SDP_ELEMENTS]
Begen, A., "SDP Elements for FEC Framework",
draft-ietf-fecframe-sdp-elements-03 (Work in Progress),
June 2009.
10.2. Informative References
[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.
[RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error
Correction (FEC) Building Block", RFC 5052, August 2007.
[RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo,
"Reed-Solomon Forward Error Correction (FEC) Schemes",
RFC 5510, April 2009.
[RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer,
"Raptor Forward Error Correction Scheme", RFC 5053,
June 2007.
[RMT-PI-ALC]
Luby, M., Watson, M., and L. Vicisano, "Asynchronous
Layered Coding (ALC) Protocol Instantiation", Work
in Progress, November 2007.
[RMT-PI-NORM]
Adamson, B., Bormann, C., Handley, M., and J. Macker,
"Negative-acknowledgment (NACK)-Oriented Reliable
Multicast (NORM) Protocol", Work in Progress, May 2008.
Roca, et al. Expires January 4, 2010 [Page 25]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
[SPSC08] Cunche, M. and V. Roca, "Optimizing the Error Recovery
Capabilities of LDPC-staircase Codes Featuring a Gaussian
Elimination Decoding Scheme", 10th IEEE International
Workshop on Signal Processing for Space Communications
(SPSC'08), October 2008.
[LDPC-codec]
Cunche, M., Roca, V., Neumann, C., and J. Laboure, "LDPC-
Staircase/LDPC-Triangle Codec Reference Implementation",
INRIA Rhone-Alpes and STMicroelectronics,
<http://planete-bcast.inrialpes.fr/>.
[RFC4303] Kent, S., "IP Encapsulating Security Payload (ESP)",
RFC 4303, December 2005.
[RFC3711] Baugher, M., McGrew, D., Naslund, M., Carrara, E., and K.
Norrman, "The Secure Real-time Transport Protocol (SRTP)",
RFC 3711, March 2004.
[RFC4383] Baugher, M. and E. Carrara, "The Use of Timed Efficient
Stream Loss-Tolerant Authentication (TESLA) in the Secure
Real- time Transport Protocol (SRTP)", RFC 4383,
February 2006.
Roca, et al. Expires January 4, 2010 [Page 26]
Internet-Draft LDPC-Staircase FEC Schemes July 2009
Authors' Addresses
Vincent Roca
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
INRIA
655, av. de l'Europe
Inovallee; Montbonnot
ST ISMIER cedex 38334
France
Email: mathieu.cunche@inria.fr
URI: http://planete.inrialpes.fr/people/cunche/
Jerome Lacan
ISAE/LAAS-CNRS
1, place Emile Blouin
Toulouse 31056
France
Email: jerome.lacan@isae.fr
URI: http://dmi.ensica.fr/auteur.php3?id_auteur=5
Roca, et al. Expires January 4, 2010 [Page 27]