idnits 2.17.1 draft-ietf-fecframe-simple-rs-05.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 6, 2012) is 4188 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '0' on line 469 -- Looks like a reference, but probably isn't: '1' on line 471 -- Looks like a reference, but probably isn't: '2' on line 473 -- Looks like a reference, but probably isn't: '3' on line 475 Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 FecFrame V. Roca 3 Internet-Draft INRIA 4 Intended status: Standards Track M. Cunche 5 Expires: May 10, 2013 INSA-Lyon/INRIA 6 J. Lacan 7 ISAE, Univ. of Toulouse 8 A. Bouabdallah 9 CDTA 10 K. Matsuzono 11 Keio University 12 November 6, 2012 14 Simple Reed-Solomon Forward Error Correction (FEC) Scheme for FECFRAME 15 draft-ietf-fecframe-simple-rs-05 17 Abstract 19 This document describes a fully-specified simple FEC scheme for Reed- 20 Solomon codes over GF(2^^m), with 2 <= m <= 16, that can be used to 21 protect arbitrary media streams along the lines defined by the 22 FECFRAME framework. Reed-Solomon codes belong to the class of 23 Maximum Distance Separable (MDS) codes which means they offer optimal 24 protection against packet erasures. They are also systematic codes, 25 which means that the source symbols are part of the encoding symbols. 26 The price to pay is a limit on the maximum source block size, on the 27 maximum number of encoding symbols, and a computational complexity 28 higher than that of LDPC codes for instance. 30 Status of This Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at http://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on May 10, 2013. 47 Copyright Notice 48 Copyright (c) 2012 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 64 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 65 3. Definitions Notations and Abbreviations . . . . . . . . . . . 4 66 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 4 67 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 6 68 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 7 69 4. Common Procedures Related to the ADU Block and Source 70 Block Creation . . . . . . . . . . . . . . . . . . . . . . . . 8 71 4.1. Restrictions . . . . . . . . . . . . . . . . . . . . . . . 8 72 4.2. ADU Block Creation . . . . . . . . . . . . . . . . . . . . 8 73 4.3. Source Block Creation . . . . . . . . . . . . . . . . . . 9 74 5. Simple Reed-Solomon FEC Scheme over GF(2^^m) for Arbitrary 75 ADU Flows . . . . . . . . . . . . . . . . . . . . . . . . . . 11 76 5.1. Formats and Codes . . . . . . . . . . . . . . . . . . . . 11 77 5.1.1. FEC Framework Configuration Information . . . . . . . 11 78 5.1.2. Explicit Source FEC Payload ID . . . . . . . . . . . . 13 79 5.1.3. Repair FEC Payload ID . . . . . . . . . . . . . . . . 14 80 5.2. Procedures . . . . . . . . . . . . . . . . . . . . . . . . 15 81 5.3. FEC Code Specification . . . . . . . . . . . . . . . . . . 16 82 6. Security Considerations . . . . . . . . . . . . . . . . . . . 16 83 6.1. Attacks Against the Data Flow . . . . . . . . . . . . . . 16 84 6.1.1. Access to Confidential Content . . . . . . . . . . . . 16 85 6.1.2. Content Corruption . . . . . . . . . . . . . . . . . . 16 86 6.2. Attacks Against the FEC Parameters . . . . . . . . . . . . 17 87 6.3. When Several Source Flows are to be Protected Together . . 18 88 6.4. Baseline Secure FEC Framework Operation . . . . . . . . . 18 89 7. Operations and Management Considerations . . . . . . . . . . . 18 90 7.1. Operational Recommendations: Finite Field Size (m) . . . . 18 91 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 19 92 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 19 93 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 94 10.1. Normative References . . . . . . . . . . . . . . . . . . . 19 95 10.2. Informative References . . . . . . . . . . . . . . . . . . 20 97 1. Introduction 99 The use of Forward Error Correction (FEC) codes is a classic solution 100 to improve the reliability of unicast, multicast and broadcast 101 Content Delivery Protocols (CDP) and applications. The [RFC6363] 102 document describes a generic framework to use FEC schemes with media 103 delivery applications, and for instance with real-time streaming 104 media applications based on the RTP real-time protocol. Similarly 105 the [RFC5052] document describes a generic framework to use FEC 106 schemes with objects (e.g., files) delivery applications based on the 107 Asynchronous Layered Coding (ALC) [RFC5775] and NACK-Oriented 108 Reliable Multicast (NORM) [RFC5740] reliable multicast transport 109 protocols. 111 More specifically, the [RFC5053] and [RFC5170] FEC schemes introduce 112 erasure codes based on sparse parity check matrices for object 113 delivery protocols like ALC and NORM. These codes are efficient in 114 terms of processing but not optimal in terms of erasure recovery 115 capabilities when dealing with "small" objects. 117 The Reed-Solomon FEC codes described in this document belong to the 118 class of Maximum Distance Separable (MDS) codes that are optimal in 119 terms of erasure recovery capability. It means that a receiver can 120 recover the k source symbols from any set of exactly k encoding 121 symbols. These codes are also systematic codes, which means that the 122 k source symbols are part of the encoding symbols. However they are 123 limited in terms of maximum source block size and number of encoding 124 symbols. Since the real-time constraints of media delivery 125 applications usually limit the maximum source block size, this is not 126 considered to be a major issue in the context of the FEC Framework 127 for many (but not necessarily all) use-cases. Additionally, if the 128 encoding/decoding complexity is higher with Reed-Solomon codes than 129 it is with [RFC5053] or [RFC5170] codes, it remains reasonable for 130 most use-cases, even in case of a software codec. 132 Many applications dealing with reliable content transmission or 133 content storage already rely on packet-based Reed-Solomon erasure 134 recovery codes. In particular, many of them use the Reed-Solomon 135 codec of Luigi Rizzo [RS-codec] [Rizzo97]. The goal of the present 136 document is to specify a simple Reed-Solomon scheme that is 137 compatible with this codec. 139 More specifically, the [RFC5510] document introduced such Reed- 140 Solomon codes and several associated FEC schemes that are compatible 141 with the [RFC5052] framework. The present document inherits from 142 [RFC5510], Section 8 "Reed-Solomon Codes Specification for the 143 Erasure Channel", the specifications of the core Reed-Solomon codes 144 based on Vandermonde matrices, and specifies a simple FEC scheme that 145 is compatible with the FECFRAME framework [RFC6363]: 147 o the Fully-Specified FEC Scheme with FEC Encoding ID XXX that 148 specifies a simple way of using of Reed-Solomon codes over 149 GF(2^^m), with 2 <= m <= 16, with a simple FEC encoding for 150 arbitrary packet flows; 152 Therefore sections 4, 5, 6 and 7 of [RFC5510], that define [RFC5052] 153 specific Formats and Procedures, are not considered and are replaced 154 by FECFRAME specific Formats and Procedures. 156 For instance, with this scheme, a set of Application Data Units (or 157 ADUs) coming from one or several media delivery applications (e.g., a 158 set of RTP packets), are grouped in an ADU block and FEC encoded as a 159 whole. With Reed-Solomon codes over GF(2^^8), there is a strict 160 limit over the number of ADUs that can be protected together, since 161 the number of encoded symbols, n, must be inferior or equal to 255. 162 This constraint is relaxed when using a higher finite field size (m > 163 8), at the price of an increased computational complexity. 165 2. Terminology 167 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 168 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 169 document are to be interpreted as described in RFC 2119 [RFC2119]. 171 3. Definitions Notations and Abbreviations 173 3.1. Definitions 175 This document uses the following terms and definitions. Some of them 176 are FEC scheme specific and are in line with [RFC5052]: 178 Source symbol: unit of data used during the encoding process. In 179 this specification, there is always one source symbol per ADU. 181 Encoding symbol: unit of data generated by the encoding process. 182 With systematic codes, source symbols are part of the encoding 183 symbols. 185 Repair symbol: encoding symbol that is not a source symbol. 187 Code rate: the k/n ratio, i.e., the ratio between the number of 188 source symbols and the number of encoding symbols. By definition, 189 the code rate is such that: 0 < code rate <= 1. A code rate close 190 to 1 indicates that a small number of repair symbols have been 191 produced during the encoding process. 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. 197 Source block: a block of k source symbols that are considered 198 together for the encoding. 200 Packet Erasure Channel: a communication path where packets are 201 either dropped (e.g., by a congested router, or because the number 202 of transmission errors exceeds the correction capabilities of the 203 physical layer codes) or received. When a packet is received, it 204 is assumed that this packet is not corrupted. 206 Some of them are FECFRAME framework specific and are in line with 207 [RFC6363]: 209 Application Data Unit (ADU): The unit of source data provided as 210 payload to the transport layer. Depending on the use-case, an ADU 211 may use an RTP encapsulation. 213 (Source) ADU Flow: A sequence of ADUs associated with a transport- 214 layer flow identifier (such as the standard 5-tuple {Source IP 215 address, source port, destination IP address, destination port, 216 transport protocol}). Depending on the use-case, several ADU 217 flows may be protected together by the FECFRAME framework. 219 ADU Block: a set of ADUs that are considered together by the 220 FECFRAME instance for the purpose of the FEC scheme. Along with 221 the flow ID (F[]), length (L[]), and padding (Pad[]) fields, they 222 form the set of source symbols over which FEC encoding will be 223 performed. 225 ADU Information (ADUI): a unit of data constituted by the ADU and 226 the associated Flow ID, Length and Padding fields (Section 4.3). 227 This is the unit of data that is used as source symbol. 229 FEC Framework Configuration Information (FFCI): Information which 230 controls the operation of the FEC Framework. The FFCI enables the 231 synchronization of the FECFRAME sender and receiver instances. 233 FEC Source Packet: At a sender (respectively, at a receiver) a 234 payload submitted to (respectively, received from) the transport 235 protocol containing an ADU along with an Explicit Source FEC 236 Payload ID (that must be present in the FEC scheme defined by the 237 present document, see Section 5.1.2). 239 FEC Repair Packet: At a sender (respectively, at a receiver) a 240 payload submitted to (respectively, received from) the transport 241 protocol containing one repair symbol along with a Repair FEC 242 Payload ID and possibly an RTP header. 244 The above terminology is illustrated in Figure 1 (sender's point of 245 view): 247 +----------------------+ 248 | Application | 249 +----------------------+ 250 | 251 | (1) Application Data Units (ADUs) 252 | 253 v 254 +----------------------+ +----------------+ 255 | FEC Framework | | | 256 | |-------------------------->| FEC Scheme | 257 |(2) Construct source |(3) Source Block | | 258 | blocks | |(4) FEC Encoding| 259 |(6) Construct FEC |<--------------------------| | 260 | source and repair | | | 261 | packets |(5) Explicit Source FEC | | 262 +----------------------+ Payload IDs +----------------+ 263 | Repair FEC Payload IDs 264 | Repair symbols 265 | 266 |(7) FEC source and repair packets 267 v 268 +----------------------+ 269 | Transport Layer | 270 | (e.g., UDP) | 271 +----------------------+ 273 Figure 1: Terminology used in this document (sender). 275 3.2. Notations 277 This document uses the following notations: Some of them are FEC 278 scheme specific: 280 k denotes the number of source symbols in a source block. 282 max_k denotes the maximum number of source symbols for any source 283 block. 285 n denotes the number of encoding symbols generated for a source 286 block. 288 E denotes the encoding symbol length in bytes. 290 GF(q) denotes a finite field (also known as Galois Field) with q 291 elements. We assume that q = 2^^m in this document. 293 m defines the length of the elements in the finite field, in 294 bits. In this document, m is such that 2 <= m <= 16. 296 q defines the number of elements in the finite field. We have: 297 q = 2^^m in this specification. 299 CR denotes the "code rate", i.e., the k/n ratio. 301 a^^b denotes a raised to the power b. 303 Some of them are FECFRAME framework specific: 305 B denotes the number of ADUs per ADU block. 307 max_B denotes the maximum number of ADUs for any ADU block. 309 3.3. Abbreviations 311 This document uses the following abbreviations: 313 ADU stands for Application Data Unit. 315 ADUI stands for Application Data Unit Information. 317 ESI stands for Encoding Symbol ID. 319 FEC stands for Forward Error (or Erasure) Correction code. 321 FFCI stands for FEC Framework Configuration Information. 323 FSSI stands for FEC Scheme Specific Information. 325 MDS stands for Maximum Distance Separable code. 327 SBN stands for Source Block Number. 329 SDP stands for Session Description Protocol. 331 4. Common Procedures Related to the ADU Block and Source Block Creation 333 This section introduces the procedures that are used during the ADU 334 block and the related source block creation, for the FEC scheme 335 considered. 337 4.1. Restrictions 339 This specification has the following restrictions: 341 o there MUST be exactly one source symbol per ADUI, and therefore 342 per ADU; 344 o there MUST be exactly one repair symbol per FEC Repair Packet; 346 o there MUST be exactly one source block per ADU block; 348 4.2. ADU Block Creation 350 Two kinds of limitations exist that impact the ADU block creation: 352 o at the FEC Scheme level: the finite field size (m parameter) 353 directly impacts the maximum source block size and the maximum 354 number of encoding symbols; 356 o at the FECFRAME instance level: the target use-case can have real- 357 time constraints that can/will define a maximum ADU block size; 359 Note that terminology "maximum source block size" and "maximum ADU 360 block size" depends on the point of view that is adopted (FEC Scheme 361 versus FECFRAME instance). However, in this document, both refer to 362 the same value since Section 4.1 requires there is exactly one source 363 symbol per ADU. We now detail each of these aspects. 365 The finite field size parameter, m, defines the number of non zero 366 elements in this field which is equal to: q - 1 = 2^^m - 1. This q - 367 1 value is also the theoretical maximum number of encoding symbols 368 that can be produced for a source block. For instance, when m = 8 369 (default) there is a maximum of 2^^8 - 1 = 255 encoding symbols. So: 370 k < n <= 255. Given the target FEC code rate (e.g., provided by the 371 end-user or upper application when starting the FECFRAME framework, 372 and taking into account the known or estimated packet loss rate), the 373 sender calculates: 375 max_k = floor((2^^m - 1) * CR) 377 This max_k value leaves enough room for the sender to produce the 378 desired number of repair symbols. Since there is one source symbol 379 per ADU, max_k is also an upper bound to the maximum number of ADUs 380 per ADU block. 382 The source ADU flows can have real-time constraints. When there are 383 multiple flows, with different real-time constraints, let us consider 384 the most stringent constraints (see [RFC6363], section 10.2, item 6 385 for recommendations when several flows are globally protected). In 386 that case the maximum number of ADUs of an ADU block must not exceed 387 a certain threshold since it directly impacts the decoding delay. 388 The larger the ADU block size, the longer a decoder may have to wait 389 until it has received a sufficient number of encoding symbols for 390 decoding to succeed, and therefore the larger the decoding delay. 391 When the target use-case is known, these real-time constraints result 392 in an upper bound to the ADU block size, max_rt. 394 For instance, if the use-case specifies a maximum decoding latency, 395 l, and if each source ADU covers a duration d of a continuous media 396 (we assume here the simple case of a constant bit rate ADU flow), 397 then the ADU block size must not exceed: 399 max_rt = floor(l / d) 401 After encoding, this block will produce a set of at most n = max_rt / 402 CR encoding symbols. These n encoding symbols will have to be sent 403 at a rate of n / l packets per second. For instance, with d = 10 ms, 404 l = 1 s, max_rt = 100 ADUs. 406 If we take into account all these constraints, we find: 408 max_B = min(max_k, max_rt) 410 This max_B parameter is an upper bound to the number of ADUs that can 411 constitute an ADU block. 413 4.3. Source Block Creation 415 In its most general form the FECFRAME framework and the Reed-Solomon 416 FEC scheme are meant to protect a set of independent flows. Since 417 the flows have no relationship to one another, the ADU size of each 418 flow can potentially vary significantly. Even in the special case of 419 a single flow, the ADU sizes can largely vary (e.g., the various 420 frames of a "Group of Pictures (GOP) of an H.264 flow will have 421 different sizes). This diversity must be addressed since the Reed- 422 Solomon FEC scheme requires a constant encoding symbol size (E 423 parameter) per source block. Since this specification requires that 424 there is only one source symbol per ADU, E must be large enough to 425 contain all the ADUs of an ADU block along with their prepended 3 426 bytes (see below). 428 In situations where E is determined per source block (default, 429 specified by the FFCI/FSSI with S = 0, Section 5.1.1.2), E is equal 430 to the size of the largest ADU of this source block plus three (for 431 the prepended 3 bytes, see below). In this case, upon receiving the 432 first FEC Repair Packet for this source block, since this packet MUST 433 contain a single repair symbol (Section 5.1.3), a receiver determines 434 the E parameter used for this source block. 436 In situations where E is fixed (specified by the FFCI/FSSI with S = 437 1, Section 5.1.1.2), then E must be greater or equal to the size of 438 the largest ADU of this source block plus three (for the prepended 3 439 bytes, see below). If this is not the case, an error is returned. 440 How to handle this error is use-case specific (e.g., a larger E 441 parameter may be communicated to the receivers in an updated FFCI 442 message, using an appropriate mechanism) and is not considered by 443 this specification. 445 The ADU block is always encoded as a single source block. There are 446 a total of B <= max_B ADUs in this ADU block. For the ADU i, with 0 447 <= i <= B-1, 3 bytes are prepended (Figure 2): 449 o The first byte, F[i] (Flow ID), contains the integer identifier 450 associated to the source ADU flow to which this ADU belongs to. 451 It is assumed that a single byte is sufficient, or said 452 differently, that no more than 256 flows will be protected by a 453 single instance of the FECFRAME framework. 455 o The following two bytes, L[i] (Length), contain the length of this 456 ADU, in network byte order (i.e., big endian). This length is for 457 the ADU itself and does not include the F[i], L[i], or Pad[i] 458 fields. 460 Then zero padding is added to ADU i (if needed) in field Pad[i], for 461 alignment purposes up to a size of exactly E bytes. The data unit 462 resulting from the ADU i and the F[i], L[i] and Pad[i] fields, is 463 called ADU Information (or ADUI). Each ADUI contributes to exactly 464 one source symbol of the source block. 466 Encoding Symbol Length (E) 467 < -------------------------------------------------------------- > 468 +----+----+-----------------------+------------------------------+ 469 |F[0]|L[0]| ADU[0] | Pad[0] | 470 +----+----+----------+------------+------------------------------+ 471 |F[1]|L[1]| ADU[1] | Pad[1] | 472 +----+----+----------+-------------------------------------------+ 473 |F[2]|L[2]| ADU[2] | 474 +----+----+------+-----------------------------------------------+ 475 |F[3]|L[3]|ADU[3]| Pad[3] | 476 +----+----+------+-----------------------------------------------+ 477 \_______________________________ _______________________________/ 478 \/ 479 simple FEC encoding 481 +----------------------------------------------------------------+ 482 | Repair 4 | 483 +----------------------------------------------------------------+ 484 . . 485 . . 486 +----------------------------------------------------------------+ 487 | Repair 7 | 488 +----------------------------------------------------------------+ 490 Figure 2: Source block creation, for code rate 1/2 (equal number of 491 source and repair symbols, 4 in this example), and S = 0. 493 Note that neither the initial 3 bytes nor the optional padding are 494 sent over the network. However, they are considered during FEC 495 encoding. It means that a receiver who lost a certain FEC source 496 packet (e.g., the UDP datagram containing this FEC source packet) 497 will be able to recover the ADUI if FEC decoding succeeds. Thanks to 498 the initial 3 bytes, this receiver will get rid of the padding (if 499 any) and identify the corresponding ADU flow. 501 5. Simple Reed-Solomon FEC Scheme over GF(2^^m) for Arbitrary ADU Flows 503 This Fully-Specified FEC Scheme specifies the use of Reed-Solomon 504 codes over GF(2^^m), with 2 <= m <= 16, with a simple FEC encoding 505 for arbitrary packet flows. 507 5.1. Formats and Codes 509 5.1.1. FEC Framework Configuration Information 511 The FEC Framework Configuration Information (or FFCI) includes 512 information that must be communicated between the sender and 513 receiver(s) [RFC6363]. More specifically, it enables the 514 synchronization of the FECFRAME sender and receiver instances. It 515 includes both mandatory elements and scheme-specific elements, as 516 detailed below. 518 5.1.1.1. Mandatory Information 520 o FEC Encoding ID: the value assigned to this fully-specified FEC 521 scheme MUST be XXX, as assigned by IANA (Section 8). 523 When SDP is used to communicate the FFCI, this FEC Encoding ID MUST 524 be carried in the 'encoding-id' parameter of the 'fec-repair-flow' 525 attribute specified in RFC 6364 [RFC6364]. 527 5.1.1.2. FEC Scheme-Specific Information 529 The FEC Scheme Specific Information (FSSI) includes elements that are 530 specific to the present FEC scheme. More precisely: 532 o Encoding symbol length (E): a non-negative integer that indicates 533 either the length of each encoding symbol in bytes ("strict" mode, 534 i.e., if S = 1), or the maximum length of any encoding symbol 535 (i.e., if S = 0). 537 o Strict (S) flag: when set to 1 this flag indicates that the E 538 parameter is the actual encoding symbol length value for each 539 block of the session (unless otherwise notified by an updated FFCI 540 if this possibility is considered by the use-case or CDP). When 541 set to 0 this flag indicates that the E parameter is the maximum 542 encoding symbol length value for each block of the session (unless 543 otherwise notified by an updated FFCI if this possibility is 544 considered by the use-case or CDP). 546 o m parameter (m): an integer that defines the length of the 547 elements in the finite field, in bits. We have: 2 <= m <= 16. 549 These elements are required both by the sender (Reed-Solomon encoder) 550 and the receiver(s) (Reed-Solomon decoder). 552 When SDP is used to communicate the FFCI, this FEC scheme-specific 553 information MUST be carried in the 'fssi' parameter of the 'fec- 554 repair-flow' attribute, in textual representation as specified in RFC 555 6364 [RFC6364]. For instance: 557 a=fec-repair-flow: encoding-id=XXX; fssi=E:1400,S:0,m:8 559 If another mechanism requires the FSSI to be carried as an opaque 560 octet string (for instance after a Base64 encoding), the encoding 561 format consists of the following 3 octets of Figure 3: 563 o Encoding symbol length (E): 16 bit field. 565 o Strict (S) flag: 1 bit field. 567 o m parameter (m): 7 bit field. 569 0 1 2 570 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 571 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 572 | Encoding Symbol Length (E) |S| m | 573 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 575 Figure 3: FSSI encoding format. 577 5.1.2. Explicit Source FEC Payload ID 579 A FEC source packet MUST contain an Explicit Source FEC Payload ID 580 that is appended to the end of the packet as illustrated in Figure 4. 582 +--------------------------------+ 583 | IP Header | 584 +--------------------------------+ 585 | Transport Header | 586 +--------------------------------+ 587 | ADU | 588 +--------------------------------+ 589 | Explicit Source FEC Payload ID | 590 +--------------------------------+ 592 Figure 4: Structure of a FEC Source Packet with the Explicit Source 593 FEC Payload ID. 595 More precisely, the Explicit Source FEC Payload ID is composed of the 596 Source Block Number, the Encoding Symbol ID, and the Source Block 597 Length. The length of the first two fields depends on the m 598 parameter (transmitted separately in the FFCI, Section 5.1.1.2): 600 o Source Block Number (SBN) (32-m bit field): this field identifies 601 the source block to which this FEC source packet belongs. 603 o Encoding Symbol ID (ESI) (m bit field): this field identifies the 604 source symbol contained in this FEC source packet. This value is 605 such that 0 <= ESI <= k - 1 for source symbols. 607 o Source Block Length (k) (16 bit field): this field provides the 608 number of source symbols for this source block, i.e., the k 609 parameter. If 16 bits are too much when m <= 8, it is needed when 610 8 < m <= 16. Therefore we provide a single common format 611 regardless of m. 613 0 1 2 3 614 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 615 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 616 | Source Block Number (24 bits) | Enc. Symb. ID | 617 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 618 | Source Block Length (k) | 619 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 621 Figure 5: Source FEC Payload ID encoding format for m = 8 (default). 623 0 1 2 3 624 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 625 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 626 | Source Block Nb (16 bits) | Enc. Symbol ID (16 bits) | 627 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 628 | Source Block Length (k) | 629 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 631 Figure 6: Source FEC Payload ID encoding format for m = 16. 633 The format of the Source FEC Payload ID for m = 8 and m = 16 are 634 illustrated in Figure 5 and Figure 6 respectively. 636 5.1.3. Repair FEC Payload ID 638 A FEC repair packet MUST contain a Repair FEC Payload ID that is 639 prepended to the repair symbol(s) as illustrated in Figure 7. There 640 MUST be a single repair symbol per FEC repair packet. 642 +--------------------------------+ 643 | IP Header | 644 +--------------------------------+ 645 | Transport Header | 646 +--------------------------------+ 647 | Repair FEC Payload ID | 648 +--------------------------------+ 649 | Repair Symbol | 650 +--------------------------------+ 652 Figure 7: Structure of a FEC Repair Packet with the Repair FEC 653 Payload ID. 655 More precisely, the Repair FEC Payload ID is composed of the Source 656 Block Number, the Encoding Symbol ID, and the Source Block Length. 657 The length of the first two fields depends on the m parameter 658 (transmitted separately in the FFCI, Section 5.1.1.2): 660 o Source Block Number (SBN) (32-m bit field): this field identifies 661 the source block to which the FEC repair packet belongs. 663 o Encoding Symbol ID (ESI) (m bit field): this field identifies the 664 repair symbol contained in this FEC repair packet. This value is 665 such that k <= ESI <= n - 1 for repair symbols. 667 o Source Block Length (k) (16 bit field): this field provides the 668 number of source symbols for this source block, i.e., the k 669 parameter. If 16 bits are too much when m <= 8, it is needed when 670 8 < m <= 16. Therefore we provide a single common format 671 regardless of m. 673 0 1 2 3 674 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 675 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 676 | Source Block Number (24 bits) | Enc. Symb. ID | 677 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 678 | Source Block Length (k) | 679 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 681 Figure 8: Repair FEC Payload ID encoding format for m = 8 (default). 683 0 1 2 3 684 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 685 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 686 | Source Block Nb (16 bits) | Enc. Symbol ID (16 bits) | 687 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 688 | Source Block Length (k) | 689 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 691 Figure 9: Repair FEC Payload ID encoding format for m = 16. 693 The format of the Repair FEC Payload ID for m = 8 and m = 16 are 694 illustrated in Figure 8 and Figure 9 respectively. 696 5.2. Procedures 698 The following procedures apply: 700 o The source block creation MUST follow the procedures specified in 701 Section 4.3. 703 o The SBN value MUST start with value 0 for the first block of the 704 ADU flow and MUST be incremented by 1 for each new source block. 705 Wrapping to zero will happen for long sessions, after value 706 2^^(32-m) - 1. 708 o The ESI of encoding symbols MUST start with value 0 for the first 709 symbol and MUST be managed sequentially. The first k values (0 <= 710 ESI <= k - 1) identify source symbols whereas the last n-k values 711 (k <= ESI <= n - 1) identify repair symbols. 713 o The FEC repair packet creation MUST follow the procedures 714 specified in Section 5.1.3. 716 5.3. FEC Code Specification 718 The present document inherits from [RFC5510], Section 8 "Reed-Solomon 719 Codes Specification for the Erasure Channel", the specifications of 720 the core Reed-Solomon codes based on Vandermonde matrices. 722 6. Security Considerations 724 The FEC Framework document [RFC6363] provides a comprehensive 725 analysis of security considerations applicable to FEC schemes. 726 Therefore the present section follows the security considerations 727 section of [RFC6363] and only discusses topics that are specific to 728 the use of Reed-Solomon codes. 730 6.1. Attacks Against the Data Flow 732 6.1.1. Access to Confidential Content 734 The Reed-Solomon FEC Scheme specified in this document does not 735 change the recommendations of [RFC6363]. To summarize, if 736 confidentiality is a concern, it is RECOMMENDED that one of the 737 solutions mentioned in [RFC6363] is used, with special considerations 738 to the way this solution is applied (e.g., is encryption applied 739 before or after FEC protection, within the end-system or in a 740 middlebox), to the operational constraints (e.g., performing FEC 741 decoding in a protected environment may be complicated or even 742 impossible) and to the threat model. 744 6.1.2. Content Corruption 746 The Reed-Solomon FEC Scheme specified in this document does not 747 change the recommendations of [RFC6363]. To summarize, it is 748 RECOMMENDED that one of the solutions mentioned in [RFC6363] is used 749 on both the FEC Source and Repair Packets. 751 6.2. Attacks Against the FEC Parameters 753 The FEC Scheme specified in this document defines parameters that can 754 be the basis of several attacks. More specifically, the following 755 parameters of the FFCI may be modified by an attacker 756 (Section 5.1.1.2): 758 o FEC Encoding ID: changing this parameter leads the receiver to 759 consider a different FEC Scheme, which enables an attacker to 760 create a Denial of Service (DoS). 762 o Encoding symbol length (E): setting this E parameter to a value 763 smaller than the valid one enables an attacker to create a DoS 764 since the repair symbols and certain source symbols will be larger 765 than E, which is an incoherency for the receiver. Setting this E 766 parameter to a value larger than the valid one has similar impacts 767 when S=1 since the received repair symbol size will be smaller 768 than expected. On the opposite it will not lead to any 769 incoherency when S=0 since the actual symbol length value for the 770 block is determined by the size of any received repair symbol, as 771 long as this value is smaller than E. However setting this E 772 parameter to a larger value may have impacts on receivers that 773 pre-allocate memory space in advance to store incoming symbols. 775 o Strict (S) flag: flipping this S flag from 0 to 1 (i.e., E is now 776 considered as a strict value) enables an attacker to mislead the 777 receiver if the actual symbol size varies over different source 778 blocks. Flipping this S flag from 1 to 0 has no major 779 consequences unless the receiver requires to have a fixed E value 780 (e.g., because the receiver pre-allocates memory space). 782 o m parameter: changing this parameter triggers a DoS since the 783 receiver and sender will consider different codes, and the 784 receiver will interpret the Explicit Source FEC Payload ID and 785 Repair FEC Payload ID differently. Additionally, by increasing 786 this m parameter to a larger value (typically m=16 rather than 8, 787 when both values are possible in the target use-case) will create 788 additional processing load at a receiver if decoding is attempted. 790 It is therefore RECOMMENDED that security measures are taken to 791 guarantee the FFCI integrity, as specified in [RFC6363]. How to 792 achieve this depends on the way the FFCI is communicated from the 793 sender to the receiver, which is not specified in this document. 795 Similarly, attacks are possible against the Explicit Source FEC 796 Payload ID and Repair FEC Payload ID: by modifying the Source Block 797 Number (SBN), or the Encoding Symbol ID (ESI), or the Source Block 798 Length (k), an attacker can easily corrupt the block identified by 799 the SBN. Other consequences, that are use-case and/or CDP dependant, 800 may also happen. It is therefore RECOMMENDED that security measures 801 are taken to guarantee the FEC Source and Repair Packets as stated in 802 [RFC6363]. 804 6.3. When Several Source Flows are to be Protected Together 806 The Reed-Solomon FEC Scheme specified in this document does not 807 change the recommendations of [RFC6363]. 809 6.4. Baseline Secure FEC Framework Operation 811 The Reed-Solomon FEC Scheme specified in this document does not 812 change the recommendations of [RFC6363] concerning the use of the 813 IPsec/ESP security protocol as a mandatory to implement (but not 814 mandatory to use) security scheme. This is well suited to situations 815 where the only insecure domain is the one over which the FEC 816 Framework operates. 818 7. Operations and Management Considerations 820 The FEC Framework document [RFC6363] provides a comprehensive 821 analysis of operations and management considerations applicable to 822 FEC schemes. Therefore the present section only discusses topics 823 that are specific to the use of Reed-Solomon codes as specified in 824 this document. 826 7.1. Operational Recommendations: Finite Field Size (m) 828 The present document requires that m, the length of the elements in 829 the finite field, in bits, is such that 2 <= m <= 16. However all 830 possibilities are not equally interesting from a practical point of 831 view. It is expected that m=8, the default value, will be mostly 832 used since it offers the possibility to have small to medium sized 833 source blocks and/or a significant number of repair symbols (i.e., k 834 < n <= 255). Additionally, elements in the finite field are 8 bits 835 long which makes read/write memory operations aligned on bytes during 836 encoding and decoding. 838 An alternative when it is known that only very small source blocks 839 will be used is m=4 (i.e., k < n <= 15). Elements in the finite 840 field are 4 bits long, so if two elements are accessed at a time, 841 read/write memory operations are aligned on bytes during encoding and 842 decoding. 844 An alternative when very large source blocks are needed is m=16 845 (i.e., k < n <= 65535). However this choice has significant impacts 846 on the processing load. For instance using pre-calculated tables to 847 speedup operations over the finite field (as done with smaller finite 848 fields) may require a prohibitive amount of memory to be used on 849 embedded platforms. Alternative lightweight solutions (e.g., 850 [RFC5170]) may be preferred in situations where the processing load 851 is an issue and the source block length is large enough 852 [Matsuzono10]. 854 Since several values for the m parameter are possible, the use-case 855 SHOULD define which value(s) need(s) to be supported. In situations 856 where this is not specified, the default m=8 value SHOULD be 857 supported and used. 859 8. IANA Considerations 861 Values of FEC Encoding IDs are subject to IANA registration. 862 [RFC6363] defines general guidelines on IANA considerations. In 863 particular it defines the "FEC Framework (FECFRAME) FEC Encoding IDs" 864 subregistry of the "Reliable Multicast Transport (RMT) FEC Encoding 865 IDs and FEC Instance IDs" registry, whose values are granted on an 866 IETF Consensus basis. 868 This document registers one value in the FEC Framework (FECFRAME) FEC 869 Encoding IDs subregistry as follows: 871 o XXX refers to the Simple Reed-Solomon [RFC5510] FEC Scheme over 872 GF(2^^m) for Arbitrary Packet Flows. 874 9. Acknowledgments 876 The authors want to thank Hitoshi Asaeda and Ali Begen for their 877 valuable comments. 879 10. References 881 10.1. Normative References 883 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 884 Requirement Levels", RFC 2119. 886 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 887 Correction (FEC) Building Block", RFC 5052, 888 August 2007. 890 [RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, 891 "Reed-Solomon Forward Error Correction (FEC) Schemes", 892 RFC 5510, April 2009. 894 [RFC6363] Watson, M., Begen, A., and V. Roca, "Forward Error 895 Correction (FEC) Framework", RFC 6363, September 2011. 897 [RFC6364] Begen, A., "Session Description Protocol Elements for 898 the Forward Error Correction (FEC) Framework", 899 RFC 6364, October 2011. 901 10.2. Informative References 903 [RS-codec] Rizzo, L., "Reed-Solomon FEC codec (C language)", 904 original codec: http://info.iet.unipi.it/~luigi/vdm98/ 905 vdm980702.tgz, improved codec: http://openfec.org/, 906 July 1998. 908 [Rizzo97] Rizzo, L., "Effective Erasure Codes for Reliable 909 Computer Communication Protocols", ACM SIGCOMM 910 Computer Communication Review Vol.27, No.2, pp.24-36, 911 April 1997. 913 [Matsuzono10] Matsuzono, K., Detchart, J., Cunche, M., Roca, V., and 914 H. Asaeda, "Performance Analysis of a High-Performance 915 Real-Time Application with Several AL-FEC Schemes", 916 35th Annual IEEE Conference on Local Computer 917 Networks (LCN 2010), October 2010. 919 [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density 920 Parity Check (LDPC) Forward Error Correction", 921 RFC 5170, June 2008. 923 [RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. 924 Stockhammer, "Raptor Forward Error Correction Scheme 925 for Object Delivery", RFC 5053, June 2007. 927 [RFC5775] Luby, M., Watson, M., and L. Vicisano, "Asynchronous 928 Layered Coding (ALC) Protocol Instantiation", 929 RFC 5775, April 2010. 931 [RFC5740] Adamson, B., Bormann, C., Handley, M., and J. Macker, 932 "Negative-acknowledgment (NACK)-Oriented Reliable 933 Multicast (NORM) Protocol", RFC 5740, November 2009. 935 Authors' Addresses 937 Vincent Roca 938 INRIA 939 655, av. de l'Europe 940 Inovallee; Montbonnot 941 ST ISMIER cedex 38334 942 France 944 EMail: vincent.roca@inria.fr 945 URI: http://planete.inrialpes.fr/people/roca/ 947 Mathieu Cunche 948 INSA-Lyon/INRIA 949 Laboratoire CITI 950 6 av. des Arts 951 Villeurbanne cedex 69621 952 France 954 EMail: mathieu.cunche@inria.fr 955 URI: http://mathieu.cunche.free.fr/ 957 Jerome Lacan 958 ISAE, Univ. of Toulouse 959 10 av. Edouard Belin; BP 54032 960 Toulouse cedex 4 31055 961 France 963 EMail: jerome.lacan@isae.fr 964 URI: http://personnel.isae.fr/jerome-lacan/ 966 Amine Bouabdallah 967 CDTA 968 Center for Development of Advanced Technologies 969 Cite 20 aout 1956, Baba Hassen 970 Algiers 971 Algeria 973 EMail: abouabdallah@cdta.dz 974 Kazuhisa Matsuzono 975 Keio University 976 Graduate School of Media and Governance 977 5322 Endo 978 Fujisawa, Kanagawa 252-8520 979 Japan 981 EMail: kazuhisa@sfc.wide.ad.jp