| RMT | V. Roca |
| Internet-Draft | A. Roumy |
| Intended status: Informational | INRIA |
| Expires: January 29, 2013 | B. Sayadi |
| Alcatel-Lucent, Bell Labs | |
| July 30, 2012 |
The Need for Extended Forward Erasure Correction (FEC) Schemes: Problem Position
This document discusses the limits of [RFC5052]-compliant traditional FEC schemes, and in particular for two use-cases that are not efficiently addressed, namely Unequal Erasure Protection (UEP) of subsets of an object and file bundle protection. This document defines the problem but not the potential solutions. This is left to companion documents.
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 29, 2013.
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.
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] (e.g. FLUTE [FLUTE]) and NORM [RFC5740] reliable multicast transport protocols.
More specifically, the [RFC5053]/[RFC6330] (Raptor/RaptorQ) 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 these object delivery protocols. Finally [RFC5445] introduces the Compact No-Code FEC Scheme that is not attached to any FEC code but behaves as if it was the case. This No-Code FEC Scheme can be very useful when an object is small enough to be sent within a single source symbol, since robustness can be achieved by repeating it, relying on a No-Code FEC Scheme for signaling considerations.
Let us consider a source object, submitted by the CDP or application, that needs to be FEC protected by one of the FEC schemes mentioned before. This FEC scheme, the underlying FEC code or the associated codec (i.e. a concrete implementation of the FEC code) defines a maximum number of source symbol that can be considered together for FEC encoding. If the object size, in terms of number of source symbols, is superior to this maximum size, this object is partitioned into multiple smaller blocks, of approximately equal size ([RFC5052], section 9.1, "Block Partitioning Algorithm"). FEC encoding is then applied independently to each block, and repair symbols are produced. The same process is then applied to each source object submitted by the CDP or application.
We see that with these FEC schemes, FEC encoding is directly applied on the source objects. Although natural, this approach leads to serious limits as we will detail. The goal of the present document is to discuss these limits. However this document does not define any solution to actually bypass these limits. This is the role of companion documents, like [GOE-RS] and [GOE-LDPC], that decouples FEC protection from the natural object boundaries, and [UOD-RaptorQ] that relies on a specific packetization technique.
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].
This document uses the following terms and definitions. Some of them are FEC scheme specific and are in line with [RFC5052]:
This document uses the following notations:
This document uses the following abbreviations:
We now list two major use-cases, namely UEP and file bundle protection. Those are the two use-cases that any Extended FEC scheme MUST support. Further, optional to support, use-cases may be added.
This first use-case defines a situation where some subsets of an object deserve a higher erasure protection than the others. The traditional FEC Schemes, as per [RFC5052], lead to apply the same FEC encoding 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.
There is no way to bypass this limit within the traditional [RFC5052]-compliant FEC Schemes. However the CDP or the application may decide to split the original object into say two sub-objects, one per important class, and to submit each sub-object separately to the FEC Scheme. Modifying the CDP specifications, e.g., FLUTE/ALC, to do that is clearly non appropriate: some of these CDP have been widely deployed and modifying deeply the specifications to address this new requirement is not desired. Modifying the application to do that does not require any modification of the specifications, but requires extra logic to manage scattering/gathering within the application. Additionally, each application has to be modified: there is no factorization of the functionality within a common underlying layer, in our case the FEC Scheme.
TODO: concrete example where UEP improves object delivery.
This second use-case defines a situation where a set of objects need to be reliably transferred within a given CDP session with the same amount of protection. All the receivers are also supposed to recover the full set of objects. With traditional FEC schemes, efficiency problems arise when this set is large and the objects are small (i.e., composed of a few source symbols each). For instance, if we consider the case where each object is composed of a single source symbol and a code rate one half is applied, each object contributes to two encoding symbols (in practice we use a No-Code FEC scheme and repeat each source symbol twice). If the two encoding symbols of an object are lost, a receiver will not be able to recover these erasures.
With traditional FEC schemes, efficiency problems also arise when objects of largely varying sizes need to be transferred within the same session. Indeed, large objects benefit from a higher number of encoding symbols than small ones (since the code rate is kept constant, the higher the number of source symbols, k, the higher the number of encoding symbols, n = k / CR). Therefore large objects will be more robust in front of erasure bursts of a given length than small objects.
In these two examples, interleaving techniques can be used to reduce the probability of losing many symbols of a given object, due to erasure bursts. However, if long packet interleaving strategies can reduce the impacts of packet erasure bursts, they do not solve the fundamental problem.
There is no way to bypass this limit within the traditional [RFC5052]-compliant FEC Schemes. However the CDP or the application may decide to create an archive that contains all the objects and to submit this archive in place of each individual object. Here also, modifying the CDP specifications, e.g., FLUTE/ALC, to do that is clearly non appropriate (same reasons). Similarly, modifying the application to do that requires extra logic, and there is no factorization of the functionality within a common underlying layer.
TODO: concrete example where UEP improves object delivery.
This section defines requirements (mandatory to support) and properties for any Extended FEC scheme.
The following are functional requirements that an Extended FEC scheme MUST provide:
Several additional properties may be considered. Some of them concern performance. For instance what is the performance in terms of unequal protection (e.g., is the protection differentiation actually achieved?), erasure recovery (e.g., does the Extended FEC scheme perform well in recovering from lost packets?), predictability (e.g., is the Extended FEC scheme behavior predictable or not?).
Some of them concern algorithm agility. For instance does the distribution of objects (i.e., total number and individual size) in a bundle impact performance with the file bundle protection use-case? Or does the Extended FEC scheme enable priority classes to be freely defined, with possible overlapping of data chunks (e.g., can subset1, of highest priority, be either independent from subset2, of lower priority, or at the opposite be part of subset2 so that repair symbols for subset2 also help in recovering erased symbols from subset1?) and gaps (e.g., a very low importance subset of an object might not be FEC encoded at all). Another aspect is the possibility to use different kinds of underlying FEC code in an Extended scheme. Finally, backward compatibility with receivers that do not support the Extended FEC scheme can also be useful in situations where the set of receivers is largely heterogeneous: backward compatibility could enable a legacy receiver to benefit from source symbols even if repair symbols will be disposed, by lack of the required logic to process them.
This list is far from exhaustive and is only for informative purposes (e.g., to compare the pros/cons of several Extended FEC schemes).
TBD
TBD
| [RFC2119] | Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, . |