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-00

Abstract

This document describes a Generalized Object Encoding (GOE) approach for the protection of one or multiple objects, using one or several FEC schemes, in the context of a Content Delivery Protocol (CDP) like FLUTE/ALC, FCAST/ALC or FCAST/NORM. In RFC5052, the encoding process is determined by the object (e.g., file) boundaries, i.e., the same code is applied to the whole object that has been submitted to the CDP by the user. The GOE approach instead decouples the definition of source blocks that are FEC encoded from the natural object boundaries. More precisely, either different portions of a given object can be protected with different FEC codes (i.e., portions of different nature and/or with different code rates), with a possible overlapping, or at the opposite, different consecutive objects can be protected globally through a single FEC encoding. If a GOE FEC Scheme defines how to create and process repair packets using the GOE approach, source objects must be encoded with a standard No-Code FEC Scheme. Therefore the same flow of source packets can be shared by different flows of repair packets, using different systematic GOE FEC schemes. An additional benefit is that the GOE approach is backward compliant since the source packets can be processed by receivers that do not support any GOE FEC scheme by simply discarding the repair packets. The present document first of all introduces the GOE approach. It then 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 January 5, 2012.

Copyright Notice

Copyright (c) 2011 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
2.  Terminology
    2.1.  Definitions, Notations and Abbreviations
        2.1.1.  Definitions
        2.1.2.  Notations
        2.1.3.  Abbreviations
3.  Goals and Requirements
4.  GOE Principles
    4.1.  GOE at a CDP Sender
    4.2.  GOE at a CDP Receiver
5.  Formats and Codes with FEC Encoding ID XXX for Reed-Solomon codes over GF(2^^8)
    5.1.  FEC Payload ID (for Repair Packets Only)
    5.2.  FEC Object Transmission Information
        5.2.1.  Mandatory Elements
        5.2.2.  Common Elements
        5.2.3.  Scheme-Specific Elements
        5.2.4.  Encoding Format
6.  Procedures with FEC Encoding ID XXX for Reed-Solomon codes over GF(2^^8)
    6.1.  Determining the Encoding Symbol Length (E)
7.  Security Considerations
8.  IANA Considerations
9.  Acknowledgments
10.  References
    10.1.  Normative References
    10.2.  Informative References
Appendix A.  Two Examples of GOE Protection of Objects
§  Authors' Addresses

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] (Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, M., and J. Crowcroft, “The Use of Forward Error Correction (FEC) in Reliable Multicast,” December 2002.). The [RFC5052] (Watson, M., Luby, M., and L. Vicisano, “Forward Error Correction (FEC) Building Block,” August 2007.) document describes a generic framework to use FEC schemes with objects (e.g., files) delivery applications based on the ALC [RFC5775] (Luby, M., Watson, M., and L. Vicisano, “Asynchronous Layered Coding (ALC) Protocol Instantiation,” April 2010.) and NORM [RFC5740] (Adamson, B., Bormann, C., Handley, M., and J. Macker, “NACK-Oriented Reliable Multicast (NORM) Transport Protocol,” November 2009.) reliable multicast transport protocols.

More specifically, the [RFC5053] (Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, “Raptor Forward Error Correction Scheme,” June 2007.) (Raptor) and [RFC5170] (Roca, V., Neumann, C., and D. Furodet, “Low Density Parity Check (LDPC) Forward Error Correction,” June 2008.) (LDPC-Staircase) FEC schemes introduce erasure codes based on sparse parity check matrices for object delivery protocols like ALC and NORM. Similarly, the [RFC5510] (Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, “Reed-Solomon Forward Error Correction (FEC) Schemes,” April 2009.) 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. First of all, [RFC5052] (Watson, M., Luby, M., and L. Vicisano, “Forward Error Correction (FEC) Building Block,” August 2007.) 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] (Watson, M., Luby, M., and L. Vicisano, “Forward Error Correction (FEC) Building Block,” August 2007.) 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 (we assume an ideal (MDS) FEC code is used).

In order to mitigate the above limitations, a better approach consists in decoupling FEC protection from the 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] (Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, “Reed-Solomon Forward Error Correction (FEC) Schemes,” April 2009.) code definition) and for LDPC-Staircase codes (re-using the [RFC5170] (Roca, V., Neumann, C., and D. Furodet, “Low Density Parity Check (LDPC) Forward Error Correction,” June 2008.) 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] (Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, “Reed-Solomon Forward Error Correction (FEC) Schemes,” April 2009.). Similar documents are expected to specify GOE equivalents to other FEC schemes.

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] (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” .).

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] (Watson, M., Luby, M., and L. Vicisano, “Forward Error Correction (FEC) Building Block,” August 2007.):

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.

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 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.

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 (Two Examples of GOE Protection of Objects) 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:

• 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;
• 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;
• 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:

• 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.
• 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:

• 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] (Watson, M., Luby, M., and L. Vicisano, “Forward Error Correction (FEC) Building Block,” August 2007.), without interfering with the GOE FEC scheme(s);
• the GOE sender chooses a source symbol size (see Section 6.1 (Determining the Encoding Symbol Length (E)) 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;
• 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] (Watson, M., “Basic Forward Error Correction (FEC) Schemes,” March 2009.); During this encoding, each (source) symbol is assigned a unique {TOI, SBN, ESI} tuple that fully identifies this symbol within the whole CDP session;
• 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;
• 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.
• each generalized object is partitioned into source blocks using the standard block partitioning algorithm defined in Section 9.1 of [RFC5052] (Watson, M., Luby, M., and L. Vicisano, “Forward Error Correction (FEC) Building Block,” August 2007.). 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;
• 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;
• 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] (Watson, M., Luby, M., and L. Vicisano, “Forward Error Correction (FEC) Building Block,” August 2007.). 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;
• 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 TOI of each repair symbol is that of the generalized object;
• 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:

• 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);
• 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;
• in case of a packet associated to a traditional FEC scheme, then process this packet in the traditional way.
• 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;
• 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;
• 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 (Goals and Requirements), 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.

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] (Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, “Reed-Solomon Forward Error Correction (FEC) Schemes,” April 2009.).

5.1.  FEC Payload ID (for Repair Packets Only)

The FEC Payload ID, to be used only with repair packet, 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] (Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, “Reed-Solomon Forward Error Correction (FEC) Schemes,” April 2009.) but a restriction in terms of valid ESI as explained below:

• 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.
• 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 identify repair symbols. Since only repair symbols are considered by this GOE FEC scheme, values 0 to k-1 inclusive MUST NOT 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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

5.2.  FEC Object Transmission Information

5.2.1.  Mandatory Elements

• FEC Encoding ID: the Fully-Specified FEC Scheme described in this section uses FEC Encoding ID XXX.

5.2.2.  Common Elements

The Common elements are the same as those specified in [RFC5510] (Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, “Reed-Solomon Forward Error Correction (FEC) Schemes,” April 2009.) for FEC Encoding ID 5.

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:

• 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;
• the Initial Source Symbol 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;
• the Initial Source Symbol 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;
• the Initial Source Symbol 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;
• the Generalized Object Size (GOS) 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] (Luby, M., Watson, M., and L. Vicisano, “Asynchronous Layered Coding (ALC) Protocol Instantiation,” April 2010.) or NORM [RFC5740] (Adamson, B., Bormann, C., Handley, M., and J. Macker, “NACK-Oriented Reliable Multicast (NORM) Transport Protocol,” November 2009.) 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 = 3    |                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                               +
|                      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                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

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] (Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen, “FLUTE - File Delivery over Unidirectional Transport,” February 2011.), the following XML attributes must be described for the associated object:

• FEC-OTI-FEC-Encoding-ID
• FEC-OTI-Transfer-Length (L)
• FEC-OTI-Encoding-Symbol-Length (E)
• FEC-OTI-Maximum-Source-Block-Length (B)
• FEC-OTI-Max-Number-of-Encoding-Symbols (max_n)
• 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
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|*_O|                                                           |
+-+-+         ISS_TOI (length = 32*ISS_O + 30 bits)             +
|                          ...                                  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    ISS Source Block Number    |    ISS Encoding Symbol ID     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                 Generalized Object Size                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

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] (Watson, M., Luby, M., and L. Vicisano, “Forward Error Correction (FEC) Building Block,” August 2007.) MUST be used. The procedure called "Determining the Maximum Source Block Length (B)" in [RFC5510] (Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, “Reed-Solomon Forward Error Correction (FEC) Schemes,” April 2009.) MUST be used. The procedure called "Determining the Number of Encoding Symbols of a Block" in [RFC5510] (Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, “Reed-Solomon Forward Error Correction (FEC) Schemes,” April 2009.) 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 PTMU 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

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] (Watson, M., Luby, M., and L. Vicisano, “Forward Error Correction (FEC) Building Block,” August 2007.).

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

10.2. Informative References

Appendix A.  Two Examples of GOE Protection of Objects

Figure 4 (Example of Object to Generalized Object mapping to provide Unequal Erasure Protection.) 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 remaining bytes. 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-Solomo(50, 40) encoding of the low priority generalized object of TOI=11 are sent over the network. Here the two generalized objects are kept separate, however nothing in the GOE approach requires this is the case. Other types of mappings are possible.

+------------------------------------------------------------------+
| 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=0.5       FEC Encoding, code rate=0.8
                |                                 |
                V                                 V
        20 repair symbols                 10 repair symbols

On the opposite, Figure 4 (Example of Object to Generalized Object mapping to provide Unequal Erasure Protection.) 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 included. 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=0.5
                                 |
                                 V
                         40 repair symbols

Authors' Addresses