idnits 2.17.1 draft-roca-rmt-extended-fec-problem-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The abstract seems to contain references ([RFC5052]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: The following are functional requirements that an Extended FEC scheme MUST provide: o the use of an Extended FEC scheme MUST NOT require conflicting modifications of the CDP specifications (when applicable). Of course supporting an additional FEC scheme will require some extra logic within the CDP, but the modifications are limited to the implementations of the CDP, without any conflicting impact on the signaling mechanism (or any other mechanism) defined by the CDP. o it MUST be possible, within a single CDP session, to include objects protected with one or several Extended FEC schemes and at the same time objects protected with one or several traditional FEC schemes. The use of Extended and traditional FEC Schemes MUST not be exclusive with one another. -- The document date (July 30, 2012) is 4281 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC5053' is defined on line 332, but no explicit reference was found in the text == Unused Reference: 'RFC6330' is defined on line 336, but no explicit reference was found in the text -- Duplicate reference: draft-roca-rmt-goe-fec, mentioned in 'GOE-LDPC', was also mentioned in 'GOE-RS'. Summary: 2 errors (**), 0 flaws (~~), 4 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 RMT V. Roca 3 Internet-Draft A. Roumy 4 Intended status: Informational INRIA 5 Expires: January 31, 2013 B. Sayadi 6 Alcatel-Lucent, Bell Labs 7 July 30, 2012 9 The Need for Extended Forward Erasure Correction (FEC) Schemes: Problem 10 Position 11 draft-roca-rmt-extended-fec-problem-00 13 Abstract 15 This document discusses the limits of [RFC5052]-compliant traditional 16 FEC schemes, and in particular for two use-cases that are not 17 efficiently addressed, namely Unequal Erasure Protection (UEP) of 18 subsets of an object and file bundle protection. This document 19 defines the problem but not the potential solutions. This is left to 20 companion documents. 22 Status of this Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at http://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on January 31, 2013. 39 Copyright Notice 41 Copyright (c) 2012 IETF Trust and the persons identified as the 42 document authors. All rights reserved. 44 This document is subject to BCP 78 and the IETF Trust's Legal 45 Provisions Relating to IETF Documents 46 (http://trustee.ietf.org/license-info) in effect on the date of 47 publication of this document. Please review these documents 48 carefully, as they describe your rights and restrictions with respect 49 to this document. Code Components extracted from this document must 50 include Simplified BSD License text as described in Section 4.e of 51 the Trust Legal Provisions and are provided without warranty as 52 described in the Simplified BSD License. 54 Table of Contents 56 1. Introduction: traditional FEC Schemes, as per [RFC5052] . . . . 3 57 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 3 58 2.1. Definitions, Notations and Abbreviations . . . . . . . . . 4 59 2.1.1. Definitions . . . . . . . . . . . . . . . . . . . . . . 4 60 2.1.2. Notations . . . . . . . . . . . . . . . . . . . . . . . 4 61 2.1.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . 4 62 3. Use-Cases not Correctly Addressed by [RFC5052]-compliant 63 FEC Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . 5 64 3.1. Major use-Case 1: Unequal Protection of Parts of an 65 Object . . . . . . . . . . . . . . . . . . . . . . . . . . 5 66 3.2. Major use-Case 2: File Bundle Protection . . . . . . . . . 5 67 4. Requirements and Good Properties for an Extended FEC Scheme . . 6 68 4.1. Mandatory to Support Functional Requirements . . . . . . . 6 69 4.2. Additional Properties . . . . . . . . . . . . . . . . . . . 7 70 5. Security Considerations . . . . . . . . . . . . . . . . . . . . 7 71 6. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . 7 72 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 73 7.1. Normative References . . . . . . . . . . . . . . . . . . . 8 74 7.2. Informative References . . . . . . . . . . . . . . . . . . 8 75 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9 77 1. Introduction: traditional FEC Schemes, as per [RFC5052] 79 The use of Forward Error Correction (FEC) codes is a classic solution 80 to improve the reliability of unicast, multicast and broadcast 81 Content Delivery Protocols (CDP) and applications [RFC3453]. The 82 [RFC5052] document describes a generic framework to use FEC schemes 83 with objects (e.g., files) delivery applications based on the ALC 84 [RFC5775] (e.g. FLUTE [FLUTE]) and NORM [RFC5740] reliable multicast 85 transport protocols. 87 More specifically, the [RFC5053]/[RFC6330] (Raptor/RaptorQ) and 88 [RFC5170] (LDPC-Staircase) FEC schemes introduce erasure codes based 89 on sparse parity check matrices for object delivery protocols like 90 ALC and NORM. Similarly, the [RFC5510] document introduces Reed- 91 Solomon codes based on Vandermonde matrices for these object delivery 92 protocols. Finally [RFC5445] introduces the Compact No-Code FEC 93 Scheme that is not attached to any FEC code but behaves as if it was 94 the case. This No-Code FEC Scheme can be very useful when an object 95 is small enough to be sent within a single source symbol, since 96 robustness can be achieved by repeating it, relying on a No-Code FEC 97 Scheme for signaling considerations. 99 Let us consider a source object, submitted by the CDP or application, 100 that needs to be FEC protected by one of the FEC schemes mentioned 101 before. This FEC scheme, the underlying FEC code or the associated 102 codec (i.e. a concrete implementation of the FEC code) defines a 103 maximum number of source symbol that can be considered together for 104 FEC encoding. If the object size, in terms of number of source 105 symbols, is superior to this maximum size, this object is partitioned 106 into multiple smaller blocks, of approximately equal size ([RFC5052], 107 section 9.1, "Block Partitioning Algorithm"). FEC encoding is then 108 applied independently to each block, and repair symbols are produced. 109 The same process is then applied to each source object submitted by 110 the CDP or application. 112 We see that with these FEC schemes, FEC encoding is directly applied 113 on the source objects. Although natural, this approach leads to 114 serious limits as we will detail. The goal of the present document 115 is to discuss these limits. However this document does not define 116 any solution to actually bypass these limits. This is the role of 117 companion documents, like [GOE-RS] and [GOE-LDPC], that decouples FEC 118 protection from the natural object boundaries, and [UOD-RaptorQ] that 119 relies on a specific packetization technique. 121 2. Terminology 123 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 124 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 125 document are to be interpreted as described in RFC 2119 [RFC2119]. 127 2.1. Definitions, Notations and Abbreviations 129 2.1.1. Definitions 131 This document uses the following terms and definitions. Some of them 132 are FEC scheme specific and are in line with [RFC5052]: 133 Source Packet: a data packet containing only source symbols, that is 134 sent over the packet erasure channel. Most of the time a source 135 packet will contain a single source symbol. 136 Repair Packet: a data packet containing only repair symbols, that is 137 sent over the packet erasure channel. Most of the time a repair 138 packet will contain a single repair symbol. 139 Packet Erasure Channel: a communication path where packets are 140 either dropped (e.g., by a congested router, or because the number 141 of transmission errors exceeds the correction capabilities of the 142 physical layer codes) or received. When a packet is received, it 143 is assumed that this packet is not corrupted. 144 Object: the object (e.g., file) submitted to the CDP by the user. 145 Source symbol: unit of data used during the encoding process. In 146 this specification, there is always one source symbol per ADU. 147 Encoding symbol: unit of data generated by the encoding process. 148 With systematic codes, source symbols are part of the encoding 149 symbols. 150 Repair symbol: encoding symbol that is not a source symbol. 151 Source block: a block of k source symbols that are considered 152 together for the encoding. 154 2.1.2. Notations 156 This document uses the following notations: 157 k denotes the number of source symbols in a source block. 158 n denotes the number of encoding symbols generated for a source 159 block. 160 CR denotes the "code rate", i.e., the k/n ratio. 162 2.1.3. Abbreviations 164 This document uses the following abbreviations: 165 FEC stands for Forward Error (or Erasure) Correction code. 166 LDPC stands for Low Density Parity Check. 167 RS stands for Reed-Solomon. 169 UEP stands for Unequal Erasure Protection. 171 3. Use-Cases not Correctly Addressed by [RFC5052]-compliant FEC Schemes 173 We now list two major use-cases, namely UEP and file bundle 174 protection. Those are the two use-cases that any Extended FEC scheme 175 MUST support. Further, optional to support, use-cases may be added. 177 3.1. Major use-Case 1: Unequal Protection of Parts of an Object 179 This first use-case defines a situation where some subsets of an 180 object deserve a higher erasure protection than the others. The 181 traditional FEC Schemes, as per [RFC5052], lead to apply the same FEC 182 encoding to all the blocks of a given object, i.e., the whole object 183 is encoded using the same FEC scheme, with the same target code rate, 184 resulting in an equivalent protection. 186 There is no way to bypass this limit within the traditional 187 [RFC5052]-compliant FEC Schemes. However the CDP or the application 188 may decide to split the original object into say two sub-objects, one 189 per important class, and to submit each sub-object separately to the 190 FEC Scheme. Modifying the CDP specifications, e.g., FLUTE/ALC, to do 191 that is clearly non appropriate: some of these CDP have been widely 192 deployed and modifying deeply the specifications to address this new 193 requirement is not desired. Modifying the application to do that 194 does not require any modification of the specifications, but requires 195 extra logic to manage scattering/gathering within the application. 196 Additionally, each application has to be modified: there is no 197 factorization of the functionality within a common underlying layer, 198 in our case the FEC Scheme. 200 TODO: concrete example where UEP improves object delivery. 202 3.2. Major use-Case 2: File Bundle Protection 204 This second use-case defines a situation where a set of objects need 205 to be reliably transferred within a given CDP session with the same 206 amount of protection. All the receivers are also supposed to recover 207 the full set of objects. With traditional FEC schemes, efficiency 208 problems arise when this set is large and the objects are small 209 (i.e., composed of a few source symbols each). For instance, if we 210 consider the case where each object is composed of a single source 211 symbol and a code rate one half is applied, each object contributes 212 to two encoding symbols (in practice we use a No-Code FEC scheme and 213 repeat each source symbol twice). If the two encoding symbols of an 214 object are lost, a receiver will not be able to recover these 215 erasures. 217 With traditional FEC schemes, efficiency problems also arise when 218 objects of largely varying sizes need to be transferred within the 219 same session. Indeed, large objects benefit from a higher number of 220 encoding symbols than small ones (since the code rate is kept 221 constant, the higher the number of source symbols, k, the higher the 222 number of encoding symbols, n = k / CR). Therefore large objects 223 will be more robust in front of erasure bursts of a given length than 224 small objects. 226 In these two examples, interleaving techniques can be used to reduce 227 the probability of losing many symbols of a given object, due to 228 erasure bursts. However, if long packet interleaving strategies can 229 reduce the impacts of packet erasure bursts, they do not solve the 230 fundamental problem. 232 There is no way to bypass this limit within the traditional 233 [RFC5052]-compliant FEC Schemes. However the CDP or the application 234 may decide to create an archive that contains all the objects and to 235 submit this archive in place of each individual object. Here also, 236 modifying the CDP specifications, e.g., FLUTE/ALC, to do that is 237 clearly non appropriate (same reasons). Similarly, modifying the 238 application to do that requires extra logic, and there is no 239 factorization of the functionality within a common underlying layer. 241 TODO: concrete example where UEP improves object delivery. 243 4. Requirements and Good Properties for an Extended FEC Scheme 245 This section defines requirements (mandatory to support) and 246 properties for any Extended FEC scheme. 248 4.1. Mandatory to Support Functional Requirements 250 The following are functional requirements that an Extended FEC scheme 251 MUST provide: 252 o the use of an Extended FEC scheme MUST NOT require conflicting 253 modifications of the CDP specifications (when applicable). Of 254 course supporting an additional FEC scheme will require some extra 255 logic within the CDP, but the modifications are limited to the 256 implementations of the CDP, without any conflicting impact on the 257 signaling mechanism (or any other mechanism) defined by the CDP. 258 o it MUST be possible, within a single CDP session, to include 259 objects protected with one or several Extended FEC schemes and at 260 the same time objects protected with one or several traditional 261 FEC schemes. The use of Extended and traditional FEC Schemes MUST 262 not be exclusive with one another. 264 o an Extended FEC scheme MUST support the use-cases 1 and 2 detailed 265 in Section 3. These two use-cases form the minimum set of 266 functionalities required for any Extended FEC scheme. 268 4.2. Additional Properties 270 Several additional properties may be considered. Some of them 271 concern performance. For instance what is the performance in terms 272 of unequal protection (e.g., is the protection differentiation 273 actually achieved?), erasure recovery (e.g., does the Extended FEC 274 scheme perform well in recovering from lost packets?), predictability 275 (e.g., is the Extended FEC scheme behavior predictable or not?). 277 Some of them concern algorithm agility. For instance does the 278 distribution of objects (i.e., total number and individual size) in a 279 bundle impact performance with the file bundle protection use-case? 280 Or does the Extended FEC scheme enable priority classes to be freely 281 defined, with possible overlapping of data chunks (e.g., can subset1, 282 of highest priority, be either independent from subset2, of lower 283 priority, or at the opposite be part of subset2 so that repair 284 symbols for subset2 also help in recovering erased symbols from 285 subset1?) and gaps (e.g., a very low importance subset of an object 286 might not be FEC encoded at all). Another aspect is the possibility 287 to use different kinds of underlying FEC code in an Extended scheme. 288 Finally, backward compatibility with receivers that do not support 289 the Extended FEC scheme can also be useful in situations where the 290 set of receivers is largely heterogeneous: backward compatibility 291 could enable a legacy receiver to benefit from source symbols even if 292 repair symbols will be disposed, by lack of the required logic to 293 process them. 295 This list is far from exhaustive and is only for informative purposes 296 (e.g., to compare the pros/cons of several Extended FEC schemes). 298 5. Security Considerations 300 TBD 302 6. Acknowledgments 304 TBD 306 7. References 307 7.1. Normative References 309 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 310 Requirement Levels", RFC 2119. 312 7.2. Informative References 314 [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, 315 M., and J. Crowcroft, "The Use of Forward Error Correction 316 (FEC) in Reliable Multicast", RFC 3453, December 2002. 318 [RFC5445] Watson, M., "Basic Forward Error Correction (FEC) 319 Schemes", RFC 5445, March 2009. 321 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 322 Correction (FEC) Building Block", RFC 5052, August 2007. 324 [RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, 325 "Reed-Solomon Forward Error Correction (FEC) Schemes", 326 RFC 5510, April 2009. 328 [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity 329 Check (LDPC) Forward Error Correction", RFC 5170, 330 June 2008. 332 [RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, 333 "Raptor Forward Error Correction Scheme", RFC 5053, 334 June 2007. 336 [RFC6330] Luby, M., Shokrollahi, A., Watson, M., Stockhammer, T., 337 and L. Minder, "RaptorQ Forward Error Correction Scheme 338 for Object Delivery", RFC 6330, August 2011. 340 [RFC5740] Adamson, B., Bormann, C., Handley, M., and J. Macker, 341 "NACK-Oriented Reliable Multicast (NORM) Transport 342 Protocol", RFC 5740, November 2009. 344 [RFC5775] Luby, M., Watson, M., and L. Vicisano, "Asynchronous 345 Layered Coding (ALC) Protocol Instantiation", RFC 5775, 346 April 2010. 348 [FLUTE] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen, 349 "FLUTE - File Delivery over Unidirectional Transport", 350 Work in Progress, June 2012. 352 [GOE-RS] Roca, V., Roumy, A., and S. Bessem, "The Generalized 353 Object Encoding (GOE) Approach for the Forward Erasure 354 Correction (FEC) Protection of Objects and its Application 355 to Reed-Solomon Codes over GF(2^^8)", Work in 356 progress draft-roca-rmt-goe-fec, July 2012. 358 [GOE-LDPC] 359 Roca, V., Roumy, A., and S. Bessem, "The Generalized 360 Object Encoding (GOE) LDPC-Staircase FEC Scheme", Work in 361 progress draft-roca-rmt-goe-fec, July 2012. 363 [UOD-RaptorQ] 364 Luby, M. and T. Stockhammer, "Universal Object Delivery 365 using RaptorQ", Work in progress draft-luby-uod-raptorq, 366 September 2011. 368 Authors' Addresses 370 Vincent Roca 371 INRIA 372 655, av. de l'Europe 373 Inovallee; Montbonnot 374 ST ISMIER cedex 38334 375 France 377 Email: vincent.roca@inria.fr 378 URI: http://planete.inrialpes.fr/people/roca/ 380 Aline Roumy 381 INRIA 382 Campus Universitaire de Beaulieu 383 RENNES Cedex 35042 384 France 386 Email: aline.roumy@inria.fr 387 URI: http://www.irisa.fr/prive/Aline.Roumy/ 389 Bessem Sayadi 390 Alcatel-Lucent, Bell Labs 391 France 393 Email: bessem.sayadi@alcatel-lucent.com