idnits 2.17.1 draft-roca-rmt-goe-fec-02.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 abstract seems to contain references ([GOE], [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 -- The document date (July 31, 2012) is 4258 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'GOE' is mentioned on line 19, but not defined -- Looks like a reference, but probably isn't: '0' on line 419 -- Looks like a reference, but probably isn't: '1' on line 420 -- Looks like a reference, but probably isn't: '2' on line 420 == Outdated reference: A later version (-02) exists of draft-roca-rmt-goe-fec-00 Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 4 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: Experimental INRIA 5 Expires: February 1, 2013 B. Sayadi 6 Alcatel-Lucent, Bell Labs 7 July 31, 2012 9 The Generalized Object Encoding (GOE) Approach for the Forward Erasure 10 Correction (FEC) Protection of Objects and its Application to Reed- 11 Solomon Codes over GF(2^^8) 12 draft-roca-rmt-goe-fec-02 14 Abstract 16 This document describes a Generalized Object Encoding (GOE) approach 17 for the protection of one or multiple objects, in the context of a 18 Content Delivery Protocol (CDP) like FLUTE/ALC, FCAST/ALC or FCAST/ 19 NORM. Unlike [RFC5052], the GOE approach [GOE] decouples the 20 definition of Generalized Objects over which FEC encoding takes place 21 homogeneously, from the natural source object boundaries. This 22 separation enables either an Unequal Erasure Protection (UEP) of 23 different portions of a given source object, or an efficient and 24 global protection of a set of potentially small files, depending on 25 the way the Generalized Objects are defined. 27 The present document first of all introduces the GOE approach. Then 28 it defines the GOE Reed-Solomon FEC Scheme for the particular case of 29 Reed-Solomon codes over GF(2^^8) and no encoding symbol group, the 30 GOE equivalent to FEC Encoding ID 5 defined in RFC5510. 32 Status of this Memo 34 This Internet-Draft is submitted in full conformance with the 35 provisions of BCP 78 and BCP 79. 37 Internet-Drafts are working documents of the Internet Engineering 38 Task Force (IETF). Note that other groups may also distribute 39 working documents as Internet-Drafts. The list of current Internet- 40 Drafts is at http://datatracker.ietf.org/drafts/current/. 42 Internet-Drafts are draft documents valid for a maximum of six months 43 and may be updated, replaced, or obsoleted by other documents at any 44 time. It is inappropriate to use Internet-Drafts as reference 45 material or to cite them other than as "work in progress." 47 This Internet-Draft will expire on February 1, 2013. 49 Copyright Notice 51 Copyright (c) 2012 IETF Trust and the persons identified as the 52 document authors. All rights reserved. 54 This document is subject to BCP 78 and the IETF Trust's Legal 55 Provisions Relating to IETF Documents 56 (http://trustee.ietf.org/license-info) in effect on the date of 57 publication of this document. Please review these documents 58 carefully, as they describe your rights and restrictions with respect 59 to this document. Code Components extracted from this document must 60 include Simplified BSD License text as described in Section 4.e of 61 the Trust Legal Provisions and are provided without warranty as 62 described in the Simplified BSD License. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 67 1.1. Traditional FEC Schemes, as per [RFC5052] . . . . . . . . 4 68 1.2. GOE FEC Scheme Principles . . . . . . . . . . . . . . . . 4 69 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 70 2.1. Definitions, Notations and Abbreviations . . . . . . . . . 5 71 2.1.1. Definitions . . . . . . . . . . . . . . . . . . . . . 5 72 2.1.2. Notations . . . . . . . . . . . . . . . . . . . . . . 6 73 2.1.3. Abbreviations . . . . . . . . . . . . . . . . . . . . 6 74 3. Goals and Requirements . . . . . . . . . . . . . . . . . . . . 7 75 4. GOE Principles . . . . . . . . . . . . . . . . . . . . . . . . 8 76 4.1. GOE at a CDP Sender . . . . . . . . . . . . . . . . . . . 8 77 4.2. GOE at a CDP Receiver . . . . . . . . . . . . . . . . . . 10 78 5. Formats and Codes with FEC Encoding ID XXX for 79 Reed-Solomon codes over GF(2^^8) . . . . . . . . . . . . . . . 11 80 5.1. FEC Payload ID (for Repair Packets Only) . . . . . . . . . 11 81 5.2. FEC Object Transmission Information . . . . . . . . . . . 11 82 5.2.1. Mandatory Elements . . . . . . . . . . . . . . . . . . 11 83 5.2.2. Common Elements . . . . . . . . . . . . . . . . . . . 12 84 5.2.3. Scheme-Specific Elements . . . . . . . . . . . . . . . 12 85 5.2.4. Encoding Format . . . . . . . . . . . . . . . . . . . 12 86 6. Procedures with FEC Encoding ID XXX for Reed-Solomon codes 87 over GF(2^^8) . . . . . . . . . . . . . . . . . . . . . . . . 14 88 6.1. Determining the Encoding Symbol Length (E) . . . . . . . . 14 89 7. Security Considerations . . . . . . . . . . . . . . . . . . . 14 90 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 91 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 15 92 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 15 93 10.1. Normative References . . . . . . . . . . . . . . . . . . . 15 94 10.2. Informative References . . . . . . . . . . . . . . . . . . 15 95 Appendix A. Two Examples of GOE Protection of Objects . . . . . . 16 96 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18 98 1. Introduction 100 1.1. Traditional FEC Schemes, as per [RFC5052] 102 The use of Forward Error Correction (FEC) codes is a classic solution 103 to improve the reliability of unicast, multicast and broadcast 104 Content Delivery Protocols (CDP) and applications [RFC3453]. The 105 [RFC5052] document describes a generic framework to use FEC schemes 106 with objects (e.g., files) delivery applications based on the ALC 107 [RFC5775] and NORM [RFC5740] reliable multicast transport protocols. 109 More specifically, the [RFC5053] (Raptor) and [RFC5170] (LDPC- 110 Staircase) FEC schemes introduce erasure codes based on sparse parity 111 check matrices for object delivery protocols like ALC and NORM. 112 Similarly, the [RFC5510] document introduces Reed-Solomon codes based 113 on Vandermonde matrices for the same object delivery protocols. 115 The way these FEC schemes is used leads to two limitations 116 [ExtendedFEC]. First of all, [RFC5052] defines an approach where the 117 same FEC encoding is applied to all the blocks of a given object, 118 i.e., the whole object is encoded using the same FEC scheme, with the 119 same target code rate, resulting in an equivalent protection. This 120 approach may not suit situations where some subsets of an object 121 deserve a higher erasure protection than the others. 123 A second limitation is associated to the protection of a large set of 124 small objects. [RFC5052] defines an approach where each object is 125 protected individually. This feature limits the robustness of their 126 delivery: since there is a small number of source and repair packets 127 for a given small object, a significant number of these packets may 128 be erased thereby preventing this object to be decoded at a receiver. 129 For instance, if the source and repair packets of a given object are 130 transmitted in sequence (which may not be the best strategy), a 131 packet erasure burst will significantly impact transmission 132 robustness. Other transmission ordering strategies (e.g., with long 133 packet interleavings or random ordering strategies) can reduce the 134 impacts of packet erasure bursts, but they do not solve the 135 fundamental problem of the protection of small objects. On the 136 opposite a global FEC protection of all the objects of this set, 137 using a single FEC encoding (when possible), provides optimal 138 transmission robustness, since all the objects can be decoded as long 139 as the erasure rate remains lower than the protection brought by the 140 FEC code rate. 142 1.2. GOE FEC Scheme Principles 144 In order to mitigate the limitations of the traditional FEC Schemes, 145 a better approach consists in decoupling FEC protection from the 146 natural object boundaries. This is the goal of the Generalized 147 Object Encoding (GOE) approach defined in the present document. The 148 GOE approach is independent of the nature of the FEC code, in the 149 sense that the general mechanisms it defines are not restricted to a 150 single type of FEC code. On the opposite, the GOE approach can be 151 used associated to any of the existing FEC schemes, re-using their 152 code definition. However a new FEC Encoding ID value, a new FEC 153 Object Transmission Information (FEC OTI) and a new FEC Payload ID 154 (FPI) must be defined in order to accommodate the GOE specifics. 155 This means that a dedicated FEC Scheme must be defined, for instance 156 for Reed-Solomon codes (re-using the [RFC5510] code definition) and 157 for LDPC-Staircase codes (re-using the [RFC5170] code definition). 159 The present document, in addition to presenting the GOE approach, 160 defines the GOE Reed-Solomon FEC Scheme for the particular case of 161 Reed-Solomon codes over GF(2^^8) and no encoding symbol group, the 162 GOE equivalent to FEC Encoding ID 5 defined in [RFC5510]. Similar 163 documents are expected to specify GOE equivalents to other FEC 164 schemes. 166 An evaluation of GOE can also be found in [Roumy11] and [Roumy12] and 167 a high level overview of GOE is available in [GOEatIETF81]. 169 2. Terminology 171 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 172 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 173 document are to be interpreted as described in RFC 2119 [RFC2119]. 175 2.1. Definitions, Notations and Abbreviations 177 2.1.1. Definitions 179 This document uses the following terms and definitions. Some of them 180 are FEC scheme specific and are in line with [RFC5052]: 181 Source Packet: a data packet containing only source symbols, that is 182 sent over the packet erasure channel. Most of the time a source 183 packet will contain a single source symbol. 184 Repair Packet: a data packet containing only repair symbols, that is 185 sent over the packet erasure channel. Most of the time a repair 186 packet will contain a single repair symbol. 187 Packet Erasure Channel: a communication path where packets are 188 either dropped (e.g., by a congested router, or because the number 189 of transmission errors exceeds the correction capabilities of the 190 physical layer codes) or received. When a packet is received, it 191 is assumed that this packet is not corrupted. 193 Systematic code: FEC code in which the source symbols are part of 194 the encoding symbols. The Reed-Solomon codes introduced in this 195 document are systematic. 196 Code rate: the k/n ratio, i.e., the ratio between the number of 197 source symbols and the number of encoding symbols. By definition, 198 the code rate is such that: 0 < code rate <= 1. A code rate close 199 to 1 indicates that a small number of repair symbols have been 200 produced during the encoding process. 201 Object: the object (e.g., file) submitted to the CDP by the user. 202 Generalized Object: a group of consecutive source symbols, that 203 belong to one or several objects (as defined above) and that are 204 considered together for the purpose of a GOE scheme. Generalized 205 objects may be a subset of a given object or at the opposite 206 encompass several objects. The key point when defining 207 generalized objects is that all the source symbols of a 208 generalized object require an equal erasure protection. 209 Source symbol: unit of data used during the encoding process. In 210 this specification, there is always one source symbol per ADU. 211 Encoding symbol: unit of data generated by the encoding process. 212 With systematic codes, source symbols are part of the encoding 213 symbols. 214 Repair symbol: encoding symbol that is not a source symbol. 215 Source block: a block of k source symbols that are considered 216 together for the encoding. 218 2.1.2. Notations 220 This document uses the following notations: 221 k denotes the number of source symbols in a source block. 222 n denotes the number of encoding symbols generated for a source 223 block. 224 E denotes the encoding symbol length in bytes. 225 NO denotes the number of source objects to be considered. 226 NGO denotes the number of generalized objects to be considered. 228 2.1.3. Abbreviations 230 This document uses the following abbreviations: 231 ADU stands for Application Data Unit. 232 TOI stands for Transmission Object Identifier. 233 SBN stands for Source Block Number, i.e., a block identifier. 234 ESI stands for Encoding Symbol ID. 235 FEC stands for Forward Error (or Erasure) Correction code. 236 LDPC stands for Low Density Parity Check. 238 RS stands for Reed-Solomon. 239 MDS stands for Maximum Distance Separable code. 240 GO stands for Generalized Object. 241 UEP stands for Unequal Erasure Protection. 242 FEC OTI stands for FEC Object Transmission Information. 244 3. Goals and Requirements 246 The main goal of the GOE FEC protection approach is to decouple FEC 247 protection from the natural object boundaries, in order to enable 248 either a differentiated protection of sub-parts of a single object 249 (e.g., to achieve Unequal Erasure Protection (UEP)), or at the 250 opposite a global protection of several objects (e.g., a large set of 251 small objects). Appendix A gives two examples where the mapping from 252 object(s) to generalized object(s) brings benefits in terms of either 253 UEP or global protection of a set of objects. 255 Additionally, the following are general requirements for GOE FEC 256 schemes: 257 o it MUST be possible, within a single CDP session, to use different 258 GOE FEC schemes. This requirement enables each GOE FEC scheme to 259 be used where it is the most valuable, for instance a GOE Reed- 260 Solomon FEC scheme MAY be used for a small generalized object 261 while a GOE LDPC-Staircase FEC scheme MAY be used for a large 262 generalized object; 263 o it MUST be possible, within a single CDP session, to include 264 objects protected with one or several GOE FEC schemes and objects 265 protected with one or several traditional (i.e., non GOE- 266 compatible) FEC schemes. The same object MAY be protected both 267 with a GOE FEC scheme and traditional FEC scheme. This 268 requirement enables GOE FEC schemes to be used only where they 269 bring added value; 270 o if a source packet is part of several generalized objects, then 271 this source packet MUST be useful to all the associated repair 272 flows. It enables the same flow of source packets to be 273 associated to different flows of repair packets, for instance to 274 address different sets of receivers with different FEC 275 capabilities; 277 Because of the GOE features, the following are specific requirements 278 that a CDP SHOULD consider: 279 o the order in which the objects are submitted to the CDP is 280 significant. More specifically, if a goal is to enable a global 281 protection of several objects, these objects MUST be submitted in 282 sequence. The Transmission Object Identifier (TOI) of these 283 objects MUST be sequential. 285 o the FEC Object Transmission Information (FEC OTI) of a GOE FEC 286 scheme determines in particular the composition of a generalized 287 object, i.e., which source symbols of which objects are 288 considered. However a receiver needs to know, upon processing 289 this FEC OTI, the FEC OTI resulting from the No-Code FEC Encoding 290 of each associated object. There is therefore a dependency that 291 the CDP SHOULD try to minimize. In case of FLUTE, if the same FDT 292 Instance ID includes the FEC OTI of all the objects and 293 generalized objects, this is not an issue. In case of LCT, if the 294 EXT_FTI mechanism is used to carry the FEC OTI, then great care 295 should be taken since the FEC OTI of each object and generalized 296 object is transmitted independently. The CDP sender must be aware 297 of that dependency and SHOULD manage the session in such a way to 298 maximize the probability that a receiver receives all the required 299 FEC OTI in due time. 301 4. GOE Principles 303 4.1. GOE at a CDP Sender 305 Let us consider a CDP sender first. GOE encoding works as follows: 306 o within the CDP session, let us consider the set of objects that 307 need to be protected by a GOE FEC scheme. These objects MUST be 308 submitted submitted sequentially to the CDP and MUST be processed 309 in their submission order. The Transmission Object Identifier 310 (TOI) assigned to these objects MUST be sequential. Let NO be the 311 number of such objects. Let O[i], with i in 1..NO, be these 312 objects. Additional objects, that are not to be considered by a 313 GOE FEC scheme, MAY be submitted to the same CDP session. These 314 additional objects are not considered in the following and will be 315 managed with a traditional FEC scheme, as defined in [RFC5052], 316 without interfering with the GOE FEC scheme(s); 317 o the GOE sender chooses a source symbol size (see Section 6.1 for 318 considerations on how to choose this size). Let E be this source 319 symbol size (in bytes). This is the size that MUST be considered 320 for all the NO objects. By doing so, a generalized object that 321 straddles several objects (among the NO possibles) benefits from 322 the same source symbol size across object boundaries; 323 o each object, O[i], is encoded with the No-Code FEC scheme (FEC 324 Encoding ID 0), to produce an appropriate number of source 325 symbols, of fixed size E, except perhaps for the last symbol of an 326 object which may be shorter. This is the standard No-Code FEC 327 encoding process, as defined in [RFC5445]; During this encoding, 328 each (source) symbol is assigned a unique {TOI, SBN, ESI} tuple 329 that fully identifies this symbol within the whole CDP session; 331 o the set of source symbols from all the NO objects is now truncated 332 into one or more sequences of symbols, called Generalized Objects 333 (GO). Let NGO be the number of such generalized objects. Let 334 GO[i], with i in 1..NGO, be these generalized objects. The size 335 (i.e., number of source symbols) of a generalized object depends 336 on the desired protection features and is left as a choice for the 337 CDP. The generalized objects MAY also overlap (e.g., a given 338 subset of source symbols can be FEC protected multiple times). On 339 the opposite, there MAY be gaps (e.g., if the sender considers 340 that a given subset of source symbols is not worth any FEC 341 protection). The key point when defining generalized objects is 342 that all the source symbols of a generalized object require an 343 equal erasure protection; 344 o each generalized object, GO[i], is assigned a new TOI value, 345 otherwise unused. It consists of a sequence of a certain number 346 of source symbols (i.e., the size of this generalized object), 347 starting from the Initial Source Symbol ISS_i whose {TOI, SBN, 348 ESI} tuple is well known. 349 o each generalized object is partitioned into source blocks using 350 the standard block partitioning algorithm defined in Section 9.1 351 of [RFC5052]. This algorithm is used in the same way, with the 352 exception that the term "object" of that algorithm should be 353 replaced by "generalized object" as defined in this document, and 354 the variable T (number of source symbols in the object) of that 355 algorithm is already known and is the "size of the generalized 356 object" as defined in this document; 357 o for a given source block, source symbols of size strictly inferior 358 to E are first zero padded (this may happen if the generalized 359 object straddles several objects as explained above). Then FEC 360 encoding takes place for this block, taking into account the 361 optional zero padding (when present), using the associated GOE FEC 362 Scheme. A certain number of FEC repair symbols is produced, 363 depending on the target coding rate. Although the FEC codes used 364 by a particular GOE FEC scheme is systematic (i.e., source symbols 365 are part of the encoding symbols), these source symbols MUST NOT 366 be sent to the receivers as GOE FEC scheme symbols, since they 367 will already be sent as No-Code FEC scheme symbols; 368 o FEC OTI for this generalized object is communicated to the 369 receiver(s) using the same mechanisms (in-band versus out-of-band) 370 as those used for other objects of that session if any [RFC5052]. 371 At a minimum the Scheme-specific element of this FEC OTI 372 identifies the ISS and size (in terms number of source symbols) 373 for that generalized object. Additional information may be added 374 as required by the GOE FEC scheme; 375 o to each FEC repair symbol an FPI, that is specific to the GOE FEC 376 Scheme used, is attached that indicates which block of which 377 generalized object this FEC repair symbol belongs to, and its 378 position within this block. Within the LCT or NORM header, the 379 TOI of each repair symbol is that of the generalized object; 380 o then source and repair packets are sent over the network, using an 381 appropriate packet ordering scheme that is out of the scope of 382 this document; 384 4.2. GOE at a CDP Receiver 386 Let us now consider a CDP receiver. GOE decoding works as follows: 387 o upon reception of a FEC OTI for an object that is considered by at 388 least one generalized object, using either an in-band or out-of- 389 band mechanism, process this FEC OTI in order to be ready to 390 process the source symbols received with a No-Code FEC scheme. 391 Note that the information contained in this FEC OTI will be 392 required during the processing of the FEC OTI of the associated 393 generalized object(s); 394 o upon reception of a FEC OTI for a generalized object, using either 395 an in-band or out-of-band mechanism, process this FEC OTI in order 396 to be ready to process the repair symbols received with a GOE FEC 397 scheme, for the same generalized object; 398 o in case of a packet associated to a traditional FEC scheme, then 399 process this packet in the traditional way. 400 o if the receiver is not interested by a generalized object(s) or 401 does not support the GOE FEC scheme(s) being used, this receiver 402 silently discards the associated packets; 403 o process all incoming packets containing a source symbol for one of 404 the NO objects, generated with a No-Code FEC encoding, in the 405 traditional way. If this source symbol is part of one (or 406 several) generalized object(s), check whether this fresh symbol 407 helps in decoding a block; 408 o incoming packets containing a repair symbol for one of the NGO 409 generalized objects are easily identified by their TOI value (and 410 in case of an ALC session by the Codepoint value of the LCT 411 header, that contains the GOE FEC Encoding ID). Process this 412 packet as specified by the GOE FEC scheme. Then check whether 413 this fresh symbol helps in decoding a block of the generalized 414 object; 416 Concerning FEC OTI processing, as explained in Section 3, if a given 417 generalized object, say GO[0], includes source symbols that belong to 418 several objects, say O[0], O[1] and O[2], then at some point of time, 419 the receiver must have processed the FEC OTI of both GO[0] and O[0], 420 O[1] and O[2]. When the FEC OTI is sent in separate packets (e.g., 421 if FEC OTI is sent within EXT_FTI LCT or NORM header extensions), 422 there is a dependency between all of them. The CDP sender must be 423 aware of that dependency and SHOULD manage the session in such a way 424 to maximize the probability that a receiver receives all the required 425 FEC OTI in due time. 427 5. Formats and Codes with FEC Encoding ID XXX for Reed-Solomon codes 428 over GF(2^^8) 430 This section introduces the formats and codes associated with the 431 Fully-Specified FEC Scheme with FEC Encoding ID XXX, which focuses on 432 the special case of Reed-Solomon codes over GF(2^^8) and no encoding 433 symbol group. This GOE FEC Scheme is the GOE equivalent to FEC 434 Encoding ID 5 defined in [RFC5510]. 436 5.1. FEC Payload ID (for Repair Packets Only) 438 The FEC Payload ID, to be used only with repair packets, i.e., 439 packets containing a repair symbol each, is composed of the Source 440 Block Number (SBN) and the Encoding Symbol ID (ESI). There is no 441 change in terms of format with respect to [RFC5510] but a restriction 442 in terms of valid ESI as explained below: 444 o The Source Block Number (24-bit field) identifies from which 445 source block of the object the encoding symbol in the payload is 446 generated. There is a maximum of 2^^24 blocks per object. 447 o The Encoding Symbol ID (8-bit field) identifies which specific 448 encoding symbol generated from the source block is carried in the 449 packet payload. There is a maximum of 2^^8 encoding symbols per 450 block. The first k values (0 to k - 1) identify source symbols; 451 the remaining n-k values (k to n-k-1) identify repair symbols. 452 Since only repair symbols are considered by this GOE FEC scheme, 453 only the k to n-k-1 values, inclusive, MUST be used. 455 There MUST be exactly one FEC Payload ID per repair packet. This FEC 456 Payload ID refers to the one and only symbol of the packet. 458 0 1 2 3 459 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 460 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 461 | Source Block Number (24 bits) | Enc. Symb. ID | 462 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 464 Figure 1: FEC Payload ID Encoding Format with FEC Encoding ID XXX 466 5.2. FEC Object Transmission Information 468 5.2.1. Mandatory Elements 470 o FEC Encoding ID: the Fully-Specified FEC Scheme described in this 471 section uses FEC Encoding ID XXX. 473 5.2.2. Common Elements 475 The Common elements are the same as those specified in [RFC5510] for 476 FEC Encoding ID 5, namely: the Transfer-Length (L), the Encoding- 477 Symbol-Length (E), the Maximum-Source-Block-Length (B), the Max- 478 Number-of-Encoding-Symbols (max_n). These common elements refer to 479 the Generalized Object for which Reed-Solomon encoding is needed.. 481 5.2.3. Scheme-Specific Elements 483 The following element MUST be defined with the present FEC scheme. 484 It defines the composition of a generalized object: 486 o the Initial Source Symbol TOI (ISS_TOI) identifies the TOI of the 487 first source symbol of this generalized object. The exact format 488 of this field depends on the TOI format, which is CDP and use-case 489 specific. For instance the TOI field of an ALC session is stored 490 in a field of length 32*O+16*H bits, where O and H are the TOI 491 flag and Half-word flag defined in LCT's header; 492 o the ISS TOI size (ISS_O) two bit field determines the TOI size, 493 which is equal to 32*ISS_O + 30 bits. This flexibility is meant 494 to be compatible with any NORM or ALC TOI format; 495 o the ISS Source Block Number (ISS_SBN) identifies the SBN of the 496 first source symbol of this generalized object, within its 497 original object. This is a 16 bit field, since this value results 498 from the No-Code FEC encoding of the original object; 499 o the ISS Encoding Symbol ID (ISS_ESI) identifies the ESI of the 500 first source symbol of this generalized object, within its 501 original block. This is a 16 bit field, since this value results 502 from the No-Code FEC encoding of the original object; 503 o the Generalized Object Size identifies the size, in terms of 504 number of source symbols that compose this generalized object; 506 5.2.4. Encoding Format 508 This section shows the two possible encoding formats of the above FEC 509 OTI. The present document does not specify when one encoding format 510 or the other should be used. 512 5.2.4.1. Using the General EXT_FTI Format 514 The FEC OTI binary format is the following, when the EXT_FTI 515 mechanism is used (e.g., within the ALC [RFC5775] or NORM [RFC5740] 516 protocols). 518 0 1 2 3 519 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 520 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 521 | HET = 64 | HEL | | 522 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 523 | Transfer Length (L) | 524 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 525 | Encoding Symbol Length (E) | MaxBlkLen (B) | max_n | 526 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 527 |*_O| | 528 +-+-+ ISS_TOI (length = 32*ISS_O + 30 bits) + 529 | ... | 530 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 531 | ISS Source Block Number | ISS Encoding Symbol ID | 532 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 533 | Generalized Object Size | 534 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 536 Figure 2: EXT_FTI Header Format with FEC Encoding ID XXX 538 5.2.4.2. Using the FDT Instance (FLUTE specific) 540 When it is desired that the FEC OTI be carried in the FDT Instance of 541 a FLUTE session [FLUTE], the following XML attributes must be 542 described for the associated object: 543 o FEC-OTI-FEC-Encoding-ID 544 o FEC-OTI-Transfer-Length (L) 545 o FEC-OTI-Encoding-Symbol-Length (E) 546 o FEC-OTI-Maximum-Source-Block-Length (B) 547 o FEC-OTI-Max-Number-of-Encoding-Symbols (max_n) 548 o FEC-OTI-Scheme-Specific-Info 549 The FEC-OTI-Scheme-Specific-Info contains the string resulting from 550 the Base64 encoding (in the XML Schema xs:base64Binary sense) of the 551 following value: 553 0 1 2 3 554 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 555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 556 |*_O| | 557 +-+-+ ISS_TOI (length = 32*ISS_O + 30 bits) + 558 | ... | 559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 560 | ISS Source Block Number | ISS Encoding Symbol ID | 561 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 562 | Generalized Object Size | 563 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 565 Figure 3: FEC OTI Scheme Specific Information To Be Included in the 566 FDT Instance 568 During Base64 encoding, the FEC OTI Scheme-Specific Information (of 569 variable length) is transformed into a string of printable characters 570 (in the 64-character alphabet) that is added to the FEC-OTI-Scheme- 571 Specific-Info attribute. 573 6. Procedures with FEC Encoding ID XXX for Reed-Solomon codes over 574 GF(2^^8) 576 This section defines procedures that MUST be applied to FEC Encoding 577 ID XXX. The block partitioning algorithm that is defined in Section 578 9.1 of [RFC5052] MUST be used. The procedure called "Determining the 579 Maximum Source Block Length (B)" in [RFC5510] MUST be used. The 580 procedure called "Determining the Number of Encoding Symbols of a 581 Block" in [RFC5510] MUST be used. 583 6.1. Determining the Encoding Symbol Length (E) 585 The E parameter usually depends on the maximum transmission unit on 586 the path Maximum Transmission Unit (PMTU) from the source to each 587 receiver. This PMTU may be known, may be discovered, or may be 588 estimated, depending on the target use case. In order to minimize 589 the protocol header overhead (e.g., the Layered Coding Transport 590 (LCT), UDP, IPv4, or IPv6 headers in the case of ALC), E MAY be 591 chosen to be as large as possible. In that case, E is chosen so that 592 the size of a packet composed of a single encoding symbol remains 593 below but close to the PMTU (or by the minimum PMTU to each possible 594 destinations in case of one-to-many sessions). This value E is also 595 the source symbol size (i.e., the source symbols, before FEC 596 encoding, and the encoding symbols, after FEC encoding, are of equal 597 size). 599 This size MUST be used to segment all of the NO objects considered by 600 the GOE FEC schemes for this CDP into source symbols. By doing so, a 601 Generalized Object that straddles several objects (among the NO 602 possibles) benefits from the same source symbol size across object 603 boundaries. 605 7. Security Considerations 607 TBD 609 8. IANA Considerations 611 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA 612 registration. For general guidelines on IANA considerations as they 613 apply to this document, see [RFC5052]. 615 This document assigns the Fully-Specified FEC Encoding ID XXX under 616 the "ietf:rmt:fec:encoding" name-space to "Generalized Object 617 Encoding for Reed-Solomon Codes over GF(2^^8)". 619 9. Acknowledgments 621 TBD 623 10. References 625 10.1. Normative References 627 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 628 Requirement Levels", RFC 2119. 630 [ExtendedFEC] 631 Roca, V., Roumy, A., and B. Sayadi, "The Need for Extended 632 Forward Erasure Correction (FEC) Schemes: Problem 633 Position", Work in 634 progress draft-roca-rmt-extended-fec-problem, July 2012. 636 [RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, 637 "Reed-Solomon Forward Error Correction (FEC) Schemes", 638 RFC 5510, April 2009. 640 10.2. Informative References 642 [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, 643 M., and J. Crowcroft, "The Use of Forward Error Correction 644 (FEC) in Reliable Multicast", RFC 3453, December 2002. 646 [RFC5445] Watson, M., "Basic Forward Error Correction (FEC) 647 Schemes", RFC 5445, March 2009. 649 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 650 Correction (FEC) Building Block", RFC 5052, August 2007. 652 [Roumy11] Roumy, A., Roca, V., Sayadi, B., and R. Imad, "Unequal 653 Erasure Protection and Object Bundle Protection with the 654 Generalized Object Encoding Approach", Inria Research 655 Report RR-7699 656 (http://hal.inria.fr/inria-00612583_v1/en/), July 2011. 658 [Roumy12] Roumy, A., Roca, V., and B. Sayadi, "Memory Consumption 659 Analysis for the GOE and PET Unequal Erasure Protection 660 Schemes", IEEE International Conference on Communications 661 (ICC'12) (http://hal.inria.fr/hal-00668826/en/), 662 June 2012. 664 [GOEatIETF81] 665 Roca, V., Roumy, A., and B. Sayadi, "The GOE FEC schemes 666 (draft-roca-rmt-goe-fec-00) and UOD-RaptorQ versus GOE", 667 Slides presented during the RMT meeting at IETF81, http:// 668 www.ietf.org/proceedings/81/slides/rmt-2.pdf, July 2011. 670 [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity 671 Check (LDPC) Forward Error Correction", RFC 5170, 672 June 2008. 674 [RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, 675 "Raptor Forward Error Correction Scheme", RFC 5053, 676 June 2007. 678 [RFC5740] Adamson, B., Bormann, C., Handley, M., and J. Macker, 679 "NACK-Oriented Reliable Multicast (NORM) Transport 680 Protocol", RFC 5740, November 2009. 682 [RFC5775] Luby, M., Watson, M., and L. Vicisano, "Asynchronous 683 Layered Coding (ALC) Protocol Instantiation", RFC 5775, 684 April 2010. 686 [FLUTE] Paila, T., Walsh, R., Luby, M., Roca, V., and R. Lehtonen, 687 "FLUTE - File Delivery over Unidirectional Transport", 688 Work in Progress, July 2012. 690 Appendix A. Two Examples of GOE Protection of Objects 692 Figure 4 is an example of use of a GOE FEC scheme to provide unequal 693 erasure protection of a large object, whose first part is of higher 694 importance than the second part. Different code rates are applied to 695 each generalized object, to provide for different erasure protection. 696 The 80 packets generated after a No-Code FEC encoding of the object 697 of TOI 1, along with the 20 repair symbols generated after a Reed- 698 Solomon(60, 40) encoding of the high priority generalized object of 699 TOI=10 and the 10 repair symbols generated after a Reed-Solomon(50, 700 40) encoding of the low priority generalized object of TOI=11 are 701 sent over the network. 703 +------------------------------------------------------------------+ 704 | Object, TOI=1, k=80 source symbols | 705 +------------------------------------------------------------------+ 706 \--------------- ----------------/\--------------- ----------------/ 707 V V 708 +------------------------------+ +------------------------------+ 709 | 1st GO (high prio) | | 2nd GO (low prio) | 710 | TOI=10, k=40 symbols | | TOI=11, k=40 symbols | 711 +------------------------------+ +------------------------------+ 712 | | 713 FEC Encoding, code rate=2/3 FEC Encoding, code rate=0.8 714 | | 715 V V 716 20 repair symbols 10 repair symbols 718 Figure 4: Example of Object to Generalized Object mapping to provide 719 Unequal Erasure Protection. 721 On the opposite, Figure 4 is an example of use of a GOE FEC scheme to 722 globally protect a set of small objects. A single generalized object 723 of TOI 10 is defined that gathers the source symbols of the original 724 objects of TOI 1 to 7 inclusive. The 80 packets generated after a 725 No-Code FEC encoding of the objects of TOI 1 to 7, along with the 40 726 repair symbols generated after a Reed-Solomon(120, 80) encoding of 727 the generalized object of TOI=10 are sent over the network. With an 728 MDS code, any subset of 80 packets among the 120 possible packets are 729 sufficient to decode all the original objects. 731 +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +------------------+ 732 |TOI=1| |TOI=2| |TOI=3| |TOI=4| |TOI=5| |TOI=6| | TOI=7 | 733 +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +------------------+ 734 \-------------------------------- ---------------------------------/ 735 V 736 +------------------------------------------------------------------+ 737 | Generalized Object, TOI=10, k=80 source symbols | 738 +------------------------------------------------------------------+ 739 | 740 FEC Encoding, code rate=2/3 741 | 742 V 743 40 repair symbols 745 Figure 5: Example of Object to Generalized Object mapping to globally 746 protect several small objects. 748 Authors' Addresses 750 Vincent Roca 751 INRIA 752 655, av. de l'Europe 753 Inovallee; Montbonnot 754 ST ISMIER cedex 38334 755 France 757 Email: vincent.roca@inria.fr 758 URI: http://planete.inrialpes.fr/people/roca/ 760 Aline Roumy 761 INRIA 762 Campus Universitaire de Beaulieu 763 RENNES Cedex 35042 764 France 766 Email: aline.roumy@inria.fr 767 URI: http://www.irisa.fr/prive/Aline.Roumy/ 769 Bessem Sayadi 770 Alcatel-Lucent, Bell Labs 771 France 773 Email: bessem.sayadi@alcatel-lucent.com