Internet DRAFT - draft-roca-rmt-goe-fec
draft-roca-rmt-goe-fec
RMT V. Roca
Internet-Draft A. Roumy
Intended status: Experimental INRIA
Expires: February 1, 2013 B. Sayadi
Alcatel-Lucent, Bell Labs
July 31, 2012
The Generalized Object Encoding (GOE) Approach for the Forward Erasure
Correction (FEC) Protection of Objects and its Application to Reed-
Solomon Codes over GF(2^^8)
draft-roca-rmt-goe-fec-02
Abstract
This document describes a Generalized Object Encoding (GOE) approach
for the protection of one or multiple objects, in the context of a
Content Delivery Protocol (CDP) like FLUTE/ALC, FCAST/ALC or FCAST/
NORM. Unlike [RFC5052], the GOE approach [GOE] decouples the
definition of Generalized Objects over which FEC encoding takes place
homogeneously, from the natural source object boundaries. This
separation enables either an Unequal Erasure Protection (UEP) of
different portions of a given source object, or an efficient and
global protection of a set of potentially small files, depending on
the way the Generalized Objects are defined.
The present document first of all introduces the GOE approach. Then
it defines the GOE Reed-Solomon FEC Scheme for the particular case of
Reed-Solomon codes over GF(2^^8) and no encoding symbol group, the
GOE equivalent to FEC Encoding ID 5 defined in RFC5510.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
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."
This Internet-Draft will expire on February 1, 2013.
Roca, et al. Expires February 1, 2013 [Page 1]
Internet-Draft The GOE Approach for FEC July 2012
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/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. Traditional FEC Schemes, as per [RFC5052] . . . . . . . . 4
1.2. GOE FEC Scheme Principles . . . . . . . . . . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1. Definitions, Notations and Abbreviations . . . . . . . . . 5
2.1.1. Definitions . . . . . . . . . . . . . . . . . . . . . 5
2.1.2. Notations . . . . . . . . . . . . . . . . . . . . . . 6
2.1.3. Abbreviations . . . . . . . . . . . . . . . . . . . . 6
3. Goals and Requirements . . . . . . . . . . . . . . . . . . . . 7
4. GOE Principles . . . . . . . . . . . . . . . . . . . . . . . . 8
4.1. GOE at a CDP Sender . . . . . . . . . . . . . . . . . . . 8
4.2. GOE at a CDP Receiver . . . . . . . . . . . . . . . . . . 10
5. Formats and Codes with FEC Encoding ID XXX for
Reed-Solomon codes over GF(2^^8) . . . . . . . . . . . . . . . 11
5.1. FEC Payload ID (for Repair Packets Only) . . . . . . . . . 11
5.2. FEC Object Transmission Information . . . . . . . . . . . 11
5.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 11
5.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 12
5.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 12
5.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 12
6. Procedures with FEC Encoding ID XXX for Reed-Solomon codes
over GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 14
6.1. Determining the Encoding Symbol Length (E) . . . . . . . . 14
7. Security Considerations . . . . . . . . . . . . . . . . . . . 14
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15
9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 15
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.1. Normative References . . . . . . . . . . . . . . . . . . . 15
10.2. Informative References . . . . . . . . . . . . . . . . . . 15
Appendix A. Two Examples of GOE Protection of Objects . . . . . . 16
Roca, et al. Expires February 1, 2013 [Page 2]
Internet-Draft The GOE Approach for FEC July 2012
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18
Roca, et al. Expires February 1, 2013 [Page 3]
Internet-Draft The GOE Approach for FEC July 2012
1. Introduction
1.1. Traditional FEC Schemes, as per [RFC5052]
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
[RFC5052] document describes a generic framework to use FEC schemes
with objects (e.g., files) delivery applications based on the ALC
[RFC5775] and NORM [RFC5740] reliable multicast transport protocols.
More specifically, the [RFC5053] (Raptor) and [RFC5170] (LDPC-
Staircase) 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.
The way these FEC schemes is used leads to two limitations
[ExtendedFEC]. First of all, [RFC5052] defines an approach where the
same FEC encoding is applied to all the blocks of a given object,
i.e., the whole object is encoded using the same FEC scheme, with the
same target code rate, resulting in an equivalent protection. This
approach may not suit situations where some subsets of an object
deserve a higher erasure protection than the others.
A second limitation is associated to the protection of a large set of
small objects. [RFC5052] defines an approach where each object is
protected individually. This feature limits the robustness of their
delivery: since there is a small number of source and repair packets
for a given small object, a significant number of these packets may
be erased thereby preventing this object to be decoded at a receiver.
For instance, if the source and repair packets of a given object are
transmitted in sequence (which may not be the best strategy), a
packet erasure burst will significantly impact transmission
robustness. Other transmission ordering strategies (e.g., with long
packet interleavings or random ordering strategies) can reduce the
impacts of packet erasure bursts, but they do not solve the
fundamental problem of the protection of small objects. On the
opposite a global FEC protection of all the objects of this set,
using a single FEC encoding (when possible), provides optimal
transmission robustness, since all the objects can be decoded as long
as the erasure rate remains lower than the protection brought by the
FEC code rate.
1.2. GOE FEC Scheme Principles
In order to mitigate the limitations of the traditional FEC Schemes,
a better approach consists in decoupling FEC protection from the
Roca, et al. Expires February 1, 2013 [Page 4]
Internet-Draft The GOE Approach for FEC July 2012
natural object boundaries. This is the goal of the Generalized
Object Encoding (GOE) approach defined in the present document. The
GOE approach is independent of the nature of the FEC code, in the
sense that the general mechanisms it defines are not restricted to a
single type of FEC code. On the opposite, the GOE approach can be
used associated to any of the existing FEC schemes, re-using their
code definition. However a new FEC Encoding ID value, a new FEC
Object Transmission Information (FEC OTI) and a new FEC Payload ID
(FPI) must be defined in order to accommodate the GOE specifics.
This means that a dedicated FEC Scheme must be defined, for instance
for Reed-Solomon codes (re-using the [RFC5510] code definition) and
for LDPC-Staircase codes (re-using the [RFC5170] code definition).
The present document, in addition to presenting the GOE approach,
defines the GOE Reed-Solomon FEC Scheme for the particular case of
Reed-Solomon codes over GF(2^^8) and no encoding symbol group, the
GOE equivalent to FEC Encoding ID 5 defined in [RFC5510]. Similar
documents are expected to specify GOE equivalents to other FEC
schemes.
An evaluation of GOE can also be found in [Roumy11] and [Roumy12] and
a high level overview of GOE is available in [GOEatIETF81].
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].
2.1. Definitions, Notations and Abbreviations
2.1.1. Definitions
This document uses the following terms and definitions. Some of them
are FEC scheme specific and are in line with [RFC5052]:
Source Packet: a data packet containing only source symbols, that is
sent over the packet erasure channel. Most of the time a source
packet will contain a single source symbol.
Repair Packet: a data packet containing only repair symbols, that is
sent over the packet erasure channel. Most of the time a repair
packet will contain a single repair symbol.
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.
Roca, et al. Expires February 1, 2013 [Page 5]
Internet-Draft The GOE Approach for FEC July 2012
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.
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.
Object: the object (e.g., file) submitted to the CDP by the user.
Generalized Object: a group of consecutive source symbols, that
belong to one or several objects (as defined above) and that are
considered together for the purpose of a GOE scheme. Generalized
objects may be a subset of a given object or at the opposite
encompass several objects. The key point when defining
generalized objects is that all the source symbols of a
generalized object require an equal erasure protection.
Source symbol: unit of data used during the encoding process. In
this specification, there is always one source symbol per ADU.
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.
Source block: a block of k source symbols that are considered
together for the encoding.
2.1.2. Notations
This document uses the following notations:
k denotes the number of source symbols in a source block.
n denotes the number of encoding symbols generated for a source
block.
E denotes the encoding symbol length in bytes.
NO denotes the number of source objects to be considered.
NGO denotes the number of generalized objects to be considered.
2.1.3. Abbreviations
This document uses the following abbreviations:
ADU stands for Application Data Unit.
TOI stands for Transmission Object Identifier.
SBN stands for Source Block Number, i.e., a block identifier.
ESI stands for Encoding Symbol ID.
FEC stands for Forward Error (or Erasure) Correction code.
LDPC stands for Low Density Parity Check.
Roca, et al. Expires February 1, 2013 [Page 6]
Internet-Draft The GOE Approach for FEC July 2012
RS stands for Reed-Solomon.
MDS stands for Maximum Distance Separable code.
GO stands for Generalized Object.
UEP stands for Unequal Erasure Protection.
FEC OTI stands for FEC Object Transmission Information.
3. Goals and Requirements
The main goal of the GOE FEC protection approach is to decouple FEC
protection from the natural object boundaries, in order to enable
either a differentiated protection of sub-parts of a single object
(e.g., to achieve Unequal Erasure Protection (UEP)), or at the
opposite a global protection of several objects (e.g., a large set of
small objects). Appendix A gives two examples where the mapping from
object(s) to generalized object(s) brings benefits in terms of either
UEP or global protection of a set of objects.
Additionally, the following are general requirements for GOE FEC
schemes:
o it MUST be possible, within a single CDP session, to use different
GOE FEC schemes. This requirement enables each GOE FEC scheme to
be used where it is the most valuable, for instance a GOE Reed-
Solomon FEC scheme MAY be used for a small generalized object
while a GOE LDPC-Staircase FEC scheme MAY be used for a large
generalized object;
o it MUST be possible, within a single CDP session, to include
objects protected with one or several GOE FEC schemes and objects
protected with one or several traditional (i.e., non GOE-
compatible) FEC schemes. The same object MAY be protected both
with a GOE FEC scheme and traditional FEC scheme. This
requirement enables GOE FEC schemes to be used only where they
bring added value;
o if a source packet is part of several generalized objects, then
this source packet MUST be useful to all the associated repair
flows. It enables the same flow of source packets to be
associated to different flows of repair packets, for instance to
address different sets of receivers with different FEC
capabilities;
Because of the GOE features, the following are specific requirements
that a CDP SHOULD consider:
o the order in which the objects are submitted to the CDP is
significant. More specifically, if a goal is to enable a global
protection of several objects, these objects MUST be submitted in
sequence. The Transmission Object Identifier (TOI) of these
objects MUST be sequential.
Roca, et al. Expires February 1, 2013 [Page 7]
Internet-Draft The GOE Approach for FEC July 2012
o the FEC Object Transmission Information (FEC OTI) of a GOE FEC
scheme determines in particular the composition of a generalized
object, i.e., which source symbols of which objects are
considered. However a receiver needs to know, upon processing
this FEC OTI, the FEC OTI resulting from the No-Code FEC Encoding
of each associated object. There is therefore a dependency that
the CDP SHOULD try to minimize. In case of FLUTE, if the same FDT
Instance ID includes the FEC OTI of all the objects and
generalized objects, this is not an issue. In case of LCT, if the
EXT_FTI mechanism is used to carry the FEC OTI, then great care
should be taken since the FEC OTI of each object and generalized
object is transmitted independently. The CDP sender must be aware
of that dependency and SHOULD manage the session in such a way to
maximize the probability that a receiver receives all the required
FEC OTI in due time.
4. GOE Principles
4.1. GOE at a CDP Sender
Let us consider a CDP sender first. GOE encoding works as follows:
o within the CDP session, let us consider the set of objects that
need to be protected by a GOE FEC scheme. These objects MUST be
submitted submitted sequentially to the CDP and MUST be processed
in their submission order. The Transmission Object Identifier
(TOI) assigned to these objects MUST be sequential. Let NO be the
number of such objects. Let O[i], with i in 1..NO, be these
objects. Additional objects, that are not to be considered by a
GOE FEC scheme, MAY be submitted to the same CDP session. These
additional objects are not considered in the following and will be
managed with a traditional FEC scheme, as defined in [RFC5052],
without interfering with the GOE FEC scheme(s);
o the GOE sender chooses a source symbol size (see Section 6.1 for
considerations on how to choose this size). Let E be this source
symbol size (in bytes). This is the size that MUST be considered
for all the NO objects. By doing so, a generalized object that
straddles several objects (among the NO possibles) benefits from
the same source symbol size across object boundaries;
o each object, O[i], is encoded with the No-Code FEC scheme (FEC
Encoding ID 0), to produce an appropriate number of source
symbols, of fixed size E, except perhaps for the last symbol of an
object which may be shorter. This is the standard No-Code FEC
encoding process, as defined in [RFC5445]; During this encoding,
each (source) symbol is assigned a unique {TOI, SBN, ESI} tuple
that fully identifies this symbol within the whole CDP session;
Roca, et al. Expires February 1, 2013 [Page 8]
Internet-Draft The GOE Approach for FEC July 2012
o the set of source symbols from all the NO objects is now truncated
into one or more sequences of symbols, called Generalized Objects
(GO). Let NGO be the number of such generalized objects. Let
GO[i], with i in 1..NGO, be these generalized objects. The size
(i.e., number of source symbols) of a generalized object depends
on the desired protection features and is left as a choice for the
CDP. The generalized objects MAY also overlap (e.g., a given
subset of source symbols can be FEC protected multiple times). On
the opposite, there MAY be gaps (e.g., if the sender considers
that a given subset of source symbols is not worth any FEC
protection). The key point when defining generalized objects is
that all the source symbols of a generalized object require an
equal erasure protection;
o each generalized object, GO[i], is assigned a new TOI value,
otherwise unused. It consists of a sequence of a certain number
of source symbols (i.e., the size of this generalized object),
starting from the Initial Source Symbol ISS_i whose {TOI, SBN,
ESI} tuple is well known.
o each generalized object is partitioned into source blocks using
the standard block partitioning algorithm defined in Section 9.1
of [RFC5052]. This algorithm is used in the same way, with the
exception that the term "object" of that algorithm should be
replaced by "generalized object" as defined in this document, and
the variable T (number of source symbols in the object) of that
algorithm is already known and is the "size of the generalized
object" as defined in this document;
o for a given source block, source symbols of size strictly inferior
to E are first zero padded (this may happen if the generalized
object straddles several objects as explained above). Then FEC
encoding takes place for this block, taking into account the
optional zero padding (when present), using the associated GOE FEC
Scheme. A certain number of FEC repair symbols is produced,
depending on the target coding rate. Although the FEC codes used
by a particular GOE FEC scheme is systematic (i.e., source symbols
are part of the encoding symbols), these source symbols MUST NOT
be sent to the receivers as GOE FEC scheme symbols, since they
will already be sent as No-Code FEC scheme symbols;
o FEC OTI for this generalized object is communicated to the
receiver(s) using the same mechanisms (in-band versus out-of-band)
as those used for other objects of that session if any [RFC5052].
At a minimum the Scheme-specific element of this FEC OTI
identifies the ISS and size (in terms number of source symbols)
for that generalized object. Additional information may be added
as required by the GOE FEC scheme;
o to each FEC repair symbol an FPI, that is specific to the GOE FEC
Scheme used, is attached that indicates which block of which
generalized object this FEC repair symbol belongs to, and its
position within this block. Within the LCT or NORM header, the
Roca, et al. Expires February 1, 2013 [Page 9]
Internet-Draft The GOE Approach for FEC July 2012
TOI of each repair symbol is that of the generalized object;
o then source and repair packets are sent over the network, using an
appropriate packet ordering scheme that is out of the scope of
this document;
4.2. GOE at a CDP Receiver
Let us now consider a CDP receiver. GOE decoding works as follows:
o upon reception of a FEC OTI for an object that is considered by at
least one generalized object, using either an in-band or out-of-
band mechanism, process this FEC OTI in order to be ready to
process the source symbols received with a No-Code FEC scheme.
Note that the information contained in this FEC OTI will be
required during the processing of the FEC OTI of the associated
generalized object(s);
o upon reception of a FEC OTI for a generalized object, using either
an in-band or out-of-band mechanism, process this FEC OTI in order
to be ready to process the repair symbols received with a GOE FEC
scheme, for the same generalized object;
o in case of a packet associated to a traditional FEC scheme, then
process this packet in the traditional way.
o if the receiver is not interested by a generalized object(s) or
does not support the GOE FEC scheme(s) being used, this receiver
silently discards the associated packets;
o process all incoming packets containing a source symbol for one of
the NO objects, generated with a No-Code FEC encoding, in the
traditional way. If this source symbol is part of one (or
several) generalized object(s), check whether this fresh symbol
helps in decoding a block;
o incoming packets containing a repair symbol for one of the NGO
generalized objects are easily identified by their TOI value (and
in case of an ALC session by the Codepoint value of the LCT
header, that contains the GOE FEC Encoding ID). Process this
packet as specified by the GOE FEC scheme. Then check whether
this fresh symbol helps in decoding a block of the generalized
object;
Concerning FEC OTI processing, as explained in Section 3, if a given
generalized object, say GO[0], includes source symbols that belong to
several objects, say O[0], O[1] and O[2], then at some point of time,
the receiver must have processed the FEC OTI of both GO[0] and O[0],
O[1] and O[2]. When the FEC OTI is sent in separate packets (e.g.,
if FEC OTI is sent within EXT_FTI LCT or NORM header extensions),
there is a dependency between all of them. The CDP sender must be
aware of that dependency and SHOULD manage the session in such a way
to maximize the probability that a receiver receives all the required
FEC OTI in due time.
Roca, et al. Expires February 1, 2013 [Page 10]
Internet-Draft The GOE Approach for FEC July 2012
5. Formats and Codes with FEC Encoding ID XXX for Reed-Solomon codes
over GF(2^^8)
This section introduces the formats and codes associated with the
Fully-Specified FEC Scheme with FEC Encoding ID XXX, which focuses on
the special case of Reed-Solomon codes over GF(2^^8) and no encoding
symbol group. This GOE FEC Scheme is the GOE equivalent to FEC
Encoding ID 5 defined in [RFC5510].
5.1. FEC Payload ID (for Repair Packets Only)
The FEC Payload ID, to be used only with repair packets, i.e.,
packets containing a repair symbol each, is composed of the Source
Block Number (SBN) and the Encoding Symbol ID (ESI). There is no
change in terms of format with respect to [RFC5510] but a restriction
in terms of valid ESI as explained below:
o The Source Block Number (24-bit field) identifies from which
source block of the object the encoding symbol in the payload is
generated. There is a maximum of 2^^24 blocks per object.
o The Encoding Symbol ID (8-bit field) identifies which specific
encoding symbol generated from the source block is carried in the
packet payload. There is a maximum of 2^^8 encoding symbols per
block. The first k values (0 to k - 1) identify source symbols;
the remaining n-k values (k to n-k-1) identify repair symbols.
Since only repair symbols are considered by this GOE FEC scheme,
only the k to n-k-1 values, inclusive, MUST be used.
There MUST be exactly one FEC Payload ID per repair packet. This FEC
Payload ID refers to the one and only symbol of the packet.
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 (24 bits) | Enc. Symb. ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 1: FEC Payload ID Encoding Format with FEC Encoding ID XXX
5.2. FEC Object Transmission Information
5.2.1. Mandatory Elements
o FEC Encoding ID: the Fully-Specified FEC Scheme described in this
section uses FEC Encoding ID XXX.
Roca, et al. Expires February 1, 2013 [Page 11]
Internet-Draft The GOE Approach for FEC July 2012
5.2.2. Common Elements
The Common elements are the same as those specified in [RFC5510] for
FEC Encoding ID 5, namely: the Transfer-Length (L), the Encoding-
Symbol-Length (E), the Maximum-Source-Block-Length (B), the Max-
Number-of-Encoding-Symbols (max_n). These common elements refer to
the Generalized Object for which Reed-Solomon encoding is needed..
5.2.3. Scheme-Specific Elements
The following element MUST be defined with the present FEC scheme.
It defines the composition of a generalized object:
o the Initial Source Symbol TOI (ISS_TOI) identifies the TOI of the
first source symbol of this generalized object. The exact format
of this field depends on the TOI format, which is CDP and use-case
specific. For instance the TOI field of an ALC session is stored
in a field of length 32*O+16*H bits, where O and H are the TOI
flag and Half-word flag defined in LCT's header;
o the ISS TOI size (ISS_O) two bit field determines the TOI size,
which is equal to 32*ISS_O + 30 bits. This flexibility is meant
to be compatible with any NORM or ALC TOI format;
o the ISS Source Block Number (ISS_SBN) identifies the SBN of the
first source symbol of this generalized object, within its
original object. This is a 16 bit field, since this value results
from the No-Code FEC encoding of the original object;
o the ISS Encoding Symbol ID (ISS_ESI) identifies the ESI of the
first source symbol of this generalized object, within its
original block. This is a 16 bit field, since this value results
from the No-Code FEC encoding of the original object;
o the Generalized Object Size identifies the size, in terms of
number of source symbols that compose this generalized object;
5.2.4. Encoding Format
This section shows the two possible encoding formats of the above FEC
OTI. The present document does not specify when one encoding format
or the other should be used.
5.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 [RFC5775] or NORM [RFC5740]
protocols).
Roca, et al. Expires February 1, 2013 [Page 12]
Internet-Draft The GOE Approach for FEC July 2012
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 | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| Transfer Length (L) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Encoding Symbol Length (E) | MaxBlkLen (B) | max_n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|*_O| |
+-+-+ ISS_TOI (length = 32*ISS_O + 30 bits) +
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ISS Source Block Number | ISS Encoding Symbol ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Generalized Object Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2: EXT_FTI Header Format with FEC Encoding ID XXX
5.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 [FLUTE], the following XML attributes must be
described for the associated object:
o FEC-OTI-FEC-Encoding-ID
o FEC-OTI-Transfer-Length (L)
o FEC-OTI-Encoding-Symbol-Length (E)
o FEC-OTI-Maximum-Source-Block-Length (B)
o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n)
o FEC-OTI-Scheme-Specific-Info
The FEC-OTI-Scheme-Specific-Info contains the string resulting from
the Base64 encoding (in the XML Schema xs:base64Binary sense) of the
following value:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|*_O| |
+-+-+ ISS_TOI (length = 32*ISS_O + 30 bits) +
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ISS Source Block Number | ISS Encoding Symbol ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Generalized Object Size |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: FEC OTI Scheme Specific Information To Be Included in the
Roca, et al. Expires February 1, 2013 [Page 13]
Internet-Draft The GOE Approach for FEC July 2012
FDT Instance
During Base64 encoding, the FEC OTI Scheme-Specific Information (of
variable length) is transformed into a string of printable characters
(in the 64-character alphabet) that is added to the FEC-OTI-Scheme-
Specific-Info attribute.
6. Procedures with FEC Encoding ID XXX for Reed-Solomon codes over
GF(2^^8)
This section defines procedures that MUST be applied to FEC Encoding
ID XXX. The block partitioning algorithm that is defined in Section
9.1 of [RFC5052] MUST be used. The procedure called "Determining the
Maximum Source Block Length (B)" in [RFC5510] MUST be used. The
procedure called "Determining the Number of Encoding Symbols of a
Block" in [RFC5510] MUST be used.
6.1. Determining the Encoding Symbol Length (E)
The E parameter usually depends on the maximum transmission unit on
the path Maximum Transmission Unit (PMTU) from the source to each
receiver. This PMTU may be known, may be discovered, or may be
estimated, depending on the target use case. In order to minimize
the protocol header overhead (e.g., the Layered Coding Transport
(LCT), UDP, IPv4, or IPv6 headers in the case of ALC), E MAY be
chosen to be as large as possible. In that case, E is chosen so that
the size of a packet composed of a single encoding symbol remains
below but close to the PMTU (or by the minimum PMTU to each possible
destinations in case of one-to-many sessions). This value E is also
the source symbol size (i.e., the source symbols, before FEC
encoding, and the encoding symbols, after FEC encoding, are of equal
size).
This size MUST be used to segment all of the NO objects considered by
the GOE FEC schemes for this CDP into source symbols. By doing so, a
Generalized Object that straddles several objects (among the NO
possibles) benefits from the same source symbol size across object
boundaries.
7. Security Considerations
TBD
Roca, et al. Expires February 1, 2013 [Page 14]
Internet-Draft The GOE Approach for FEC July 2012
8. 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 [RFC5052].
This document assigns the Fully-Specified FEC Encoding ID XXX under
the "ietf:rmt:fec:encoding" name-space to "Generalized Object
Encoding for Reed-Solomon Codes over GF(2^^8)".
9. Acknowledgments
TBD
10. References
10.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", RFC 2119.
[ExtendedFEC]
Roca, V., Roumy, A., and B. Sayadi, "The Need for Extended
Forward Erasure Correction (FEC) Schemes: Problem
Position", Work in
progress draft-roca-rmt-extended-fec-problem, July 2012.
[RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo,
"Reed-Solomon Forward Error Correction (FEC) Schemes",
RFC 5510, April 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.
[RFC5445] Watson, M., "Basic Forward Error Correction (FEC)
Schemes", RFC 5445, March 2009.
[RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error
Correction (FEC) Building Block", RFC 5052, August 2007.
[Roumy11] Roumy, A., Roca, V., Sayadi, B., and R. Imad, "Unequal
Erasure Protection and Object Bundle Protection with the
Generalized Object Encoding Approach", Inria Research
Roca, et al. Expires February 1, 2013 [Page 15]
Internet-Draft The GOE Approach for FEC July 2012
Report RR-7699
(http://hal.inria.fr/inria-00612583_v1/en/), July 2011.
[Roumy12] Roumy, A., Roca, V., and B. Sayadi, "Memory Consumption
Analysis for the GOE and PET Unequal Erasure Protection
Schemes", IEEE International Conference on Communications
(ICC'12) (http://hal.inria.fr/hal-00668826/en/),
June 2012.
[GOEatIETF81]
Roca, V., Roumy, A., and B. Sayadi, "The GOE FEC schemes
(draft-roca-rmt-goe-fec-00) and UOD-RaptorQ versus GOE",
Slides presented during the RMT meeting at IETF81, http://
www.ietf.org/proceedings/81/slides/rmt-2.pdf, July 2011.
[RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity
Check (LDPC) Forward Error Correction", RFC 5170,
June 2008.
[RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer,
"Raptor Forward Error Correction Scheme", RFC 5053,
June 2007.
[RFC5740] Adamson, B., Bormann, C., Handley, M., and J. Macker,
"NACK-Oriented Reliable Multicast (NORM) Transport
Protocol", RFC 5740, November 2009.
[RFC5775] Luby, M., Watson, M., and L. Vicisano, "Asynchronous
Layered Coding (ALC) Protocol Instantiation", RFC 5775,
April 2010.
[FLUTE] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen,
"FLUTE - File Delivery over Unidirectional Transport",
Work in Progress, July 2012.
Appendix A. Two Examples of GOE Protection of Objects
Figure 4 is an example of use of a GOE FEC scheme to provide unequal
erasure protection of a large object, whose first part is of higher
importance than the second part. Different code rates are applied to
each generalized object, to provide for different erasure protection.
The 80 packets generated after a No-Code FEC encoding of the object
of TOI 1, along with the 20 repair symbols generated after a Reed-
Solomon(60, 40) encoding of the high priority generalized object of
TOI=10 and the 10 repair symbols generated after a Reed-Solomon(50,
40) encoding of the low priority generalized object of TOI=11 are
sent over the network.
Roca, et al. Expires February 1, 2013 [Page 16]
Internet-Draft The GOE Approach for FEC July 2012
+------------------------------------------------------------------+
| Object, TOI=1, k=80 source symbols |
+------------------------------------------------------------------+
\--------------- ----------------/\--------------- ----------------/
V V
+------------------------------+ +------------------------------+
| 1st GO (high prio) | | 2nd GO (low prio) |
| TOI=10, k=40 symbols | | TOI=11, k=40 symbols |
+------------------------------+ +------------------------------+
| |
FEC Encoding, code rate=2/3 FEC Encoding, code rate=0.8
| |
V V
20 repair symbols 10 repair symbols
Figure 4: Example of Object to Generalized Object mapping to provide
Unequal Erasure Protection.
On the opposite, Figure 4 is an example of use of a GOE FEC scheme to
globally protect a set of small objects. A single generalized object
of TOI 10 is defined that gathers the source symbols of the original
objects of TOI 1 to 7 inclusive. The 80 packets generated after a
No-Code FEC encoding of the objects of TOI 1 to 7, along with the 40
repair symbols generated after a Reed-Solomon(120, 80) encoding of
the generalized object of TOI=10 are sent over the network. With an
MDS code, any subset of 80 packets among the 120 possible packets are
sufficient to decode all the original objects.
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +------------------+
|TOI=1| |TOI=2| |TOI=3| |TOI=4| |TOI=5| |TOI=6| | TOI=7 |
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +------------------+
\-------------------------------- ---------------------------------/
V
+------------------------------------------------------------------+
| Generalized Object, TOI=10, k=80 source symbols |
+------------------------------------------------------------------+
|
FEC Encoding, code rate=2/3
|
V
40 repair symbols
Figure 5: Example of Object to Generalized Object mapping to globally
protect several small objects.
Roca, et al. Expires February 1, 2013 [Page 17]
Internet-Draft The GOE Approach for FEC July 2012
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/
Aline Roumy
INRIA
Campus Universitaire de Beaulieu
RENNES Cedex 35042
France
Email: aline.roumy@inria.fr
URI: http://www.irisa.fr/prive/Aline.Roumy/
Bessem Sayadi
Alcatel-Lucent, Bell Labs
France
Email: bessem.sayadi@alcatel-lucent.com
Roca, et al. Expires February 1, 2013 [Page 18]
