idnits 2.17.1 draft-ietf-fecframe-simple-rs-04.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 (October 3, 2012) is 4223 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 420 -- Looks like a reference, but probably isn't: '1' on line 422 -- Looks like a reference, but probably isn't: '2' on line 424 -- Looks like a reference, but probably isn't: '3' on line 426 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: April 6, 2013 INSA-Lyon/INRIA 6 J. Lacan 7 A. Bouabdallah 8 ISAE, Univ. of Toulouse 9 K. Matsuzono 10 Keio University 11 October 3, 2012 13 Simple Reed-Solomon Forward Error Correction (FEC) Scheme for FECFRAME 14 draft-ietf-fecframe-simple-rs-04 16 Abstract 18 This document describes a fully-specified simple FEC scheme for Reed- 19 Solomon codes over GF(2^^m), with 2 <= m <= 16, that can be used to 20 protect arbitrary media streams along the lines defined by the 21 FECFRAME framework. Reed-Solomon codes belong to the class of 22 Maximum Distance Separable (MDS) codes which means they offer optimal 23 protection against packet erasures. They are also systematic codes, 24 which means that the source symbols are part of the encoding symbols. 25 The price to pay is a limit on the maximum source block size, on the 26 maximum number of encoding symbols, and a computational complexity 27 higher than that of LDPC codes for instance. 29 Status of this Memo 31 This Internet-Draft is submitted in full conformance with the 32 provisions of BCP 78 and BCP 79. 34 Internet-Drafts are working documents of the Internet Engineering 35 Task Force (IETF). Note that other groups may also distribute 36 working documents as Internet-Drafts. The list of current Internet- 37 Drafts is at http://datatracker.ietf.org/drafts/current/. 39 Internet-Drafts are draft documents valid for a maximum of six months 40 and may be updated, replaced, or obsoleted by other documents at any 41 time. It is inappropriate to use Internet-Drafts as reference 42 material or to cite them other than as "work in progress." 44 This Internet-Draft will expire on April 6, 2013. 46 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 . . . . . . . . . . . . . . . . . . . . . . . . . 4 64 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5 65 3. Definitions Notations and Abbreviations . . . . . . . . . . . 5 66 3.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 5 67 3.2. Notations . . . . . . . . . . . . . . . . . . . . . . . . 7 68 3.3. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 8 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 . . . . . . . . . . . . 16 87 6.3. When Several Source Flows are to be Protected Together . . 17 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 . . . . . . . . . . . . . . . . . . 19 97 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20 99 1. Introduction 101 The use of Forward Error Correction (FEC) codes is a classic solution 102 to improve the reliability of unicast, multicast and broadcast 103 Content Delivery Protocols (CDP) and applications. The [RFC6363] 104 document describes a generic framework to use FEC schemes with media 105 delivery applications, and for instance with real-time streaming 106 media applications based on the RTP real-time protocol. Similarly 107 the [RFC5052] document describes a generic framework to use FEC 108 schemes with objects (e.g., files) delivery applications based on the 109 ALC [RFC5775] and NORM [RFC5740] reliable multicast transport 110 protocols. 112 More specifically, the [RFC5053] and [RFC5170] FEC schemes introduce 113 erasure codes based on sparse parity check matrices for object 114 delivery protocols like ALC and NORM. These codes are efficient in 115 terms of processing but not optimal in terms of erasure recovery 116 capabilities when dealing with "small" objects. 118 The Reed-Solomon FEC codes described in this document belong to the 119 class of Maximum Distance Separable (MDS) codes that are optimal in 120 terms of erasure recovery capability. It means that a receiver can 121 recover the k source symbols from any set of exactly k encoding 122 symbols. These codes are also systematic codes, which means that the 123 k source symbols are part of the encoding symbols. However they are 124 limited in terms of maximum source block size and number of encoding 125 symbols. Since the real-time constraints of media delivery 126 applications usually limit the maximum source block size, this is not 127 considered to be a major issue in the context of the FEC Framework 128 for many (but not necessarily all) use-cases. Additionally, if the 129 encoding/decoding complexity is higher with Reed-Solomon codes than 130 it is with [RFC5053] or [RFC5170] codes, it remains reasonable for 131 most use-cases, even in case of a software codec. 133 Many applications dealing with reliable content transmission or 134 content storage already rely on packet-based Reed-Solomon erasure 135 recovery codes. In particular, many of them use the Reed-Solomon 136 codec of Luigi Rizzo [RS-codec] [Rizzo97]. The goal of the present 137 document is to specify a simple Reed-Solomon scheme that is 138 compatible with this codec. 140 More specifically, the [RFC5510] document introduced such Reed- 141 Solomon codes and several associated FEC schemes that are compatible 142 with the [RFC5052] framework. The present document inherits from 143 [RFC5510] the specification of the core Reed-Solomon codes based on 144 Vandermonde matrices, and specifies a simple FEC scheme that is 145 compatible with the FECFRAME framework [RFC6363]. Therefore this 146 document specifies only the information specific to the FECFRAME 147 context and refers to [RFC5510] for the core specifications of the 148 codes. To that purpose, the present document introduces: 149 o the Fully-Specified FEC Scheme with FEC Encoding ID XXX that 150 specifies a simple way of using of Reed-Solomon codes over 151 GF(2^^m), with 2 <= m <= 16, with a simple FEC encoding for 152 arbitrary packet flows; 154 For instance, with this scheme, a set of Application Data Units (or 155 ADUs) coming from one or several media delivery applications (e.g., a 156 set of RTP packets), are grouped in an ADU block and FEC encoded as a 157 whole. With Reed-Solomon codes over GF(2^^8), there is a strict 158 limit over the number of ADUs that can be protected together, since 159 the number of encoded symbols, n, must be inferior or equal to 255. 160 This constraint is relaxed when using a higher finite field size (m > 161 8), at the price of an increased computational complexity. 163 2. Terminology 165 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 166 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 167 document are to be interpreted as described in RFC 2119 [RFC2119]. 169 3. Definitions Notations and Abbreviations 171 3.1. Definitions 173 This document uses the following terms and definitions. Some of them 174 are FEC scheme specific and are in line with [RFC5052]: 175 Source symbol: unit of data used during the encoding process. In 176 this specification, there is always one source symbol per ADU. 177 Encoding symbol: unit of data generated by the encoding process. 178 With systematic codes, source symbols are part of the encoding 179 symbols. 180 Repair symbol: encoding symbol that is not a source symbol. 181 Code rate: the k/n ratio, i.e., the ratio between the number of 182 source symbols and the number of encoding symbols. By definition, 183 the code rate is such that: 0 < code rate <= 1. A code rate close 184 to 1 indicates that a small number of repair symbols have been 185 produced during the encoding process. 186 Systematic code: FEC code in which the source symbols are part of 187 the encoding symbols. The Reed-Solomon codes introduced in this 188 document are systematic. 190 Source block: a block of k source symbols that are considered 191 together for the encoding. 192 Packet Erasure Channel: a communication path where packets are 193 either dropped (e.g., by a congested router, or because the number 194 of transmission errors exceeds the correction capabilities of the 195 physical layer codes) or received. When a packet is received, it 196 is assumed that this packet is not corrupted. 198 Some of them are FECFRAME framework specific and are in line with 199 [RFC6363]: 200 Application Data Unit (ADU): The unit of source data provided as 201 payload to the transport layer. Depending on the use-case, an ADU 202 may use an RTP encapsulation. 203 (Source) ADU Flow: A sequence of ADUs associated with a transport- 204 layer flow identifier (such as the standard 5-tuple {Source IP 205 address, source port, destination IP address, destination port, 206 transport protocol}). Depending on the use-case, several ADU 207 flows may be protected together by the FECFRAME framework. 208 ADU Block: a set of ADUs that are considered together by the 209 FECFRAME instance for the purpose of the FEC scheme. Along with 210 the F[], L[], and Pad[] fields, they form the set of source 211 symbols over which FEC encoding will be performed. 212 ADU Information (ADUI): a unit of data constituted by the ADU and 213 the associated Flow ID, Length and Padding fields (Section 4.3). 214 This is the unit of data that is used as source symbol. 215 FEC Framework Configuration Information: Information which controls 216 the operation of the FEC Framework. The FFCI enables the 217 synchronization of the FECFRAME sender and receiver instances. 218 FEC Source Packet: At a sender (respectively, at a receiver) a 219 payload submitted to (respectively, received from) the transport 220 protocol containing an ADU along with an Explicit Source FEC 221 Payload ID (that must be present in the FEC scheme defined by the 222 present document, see Section 5.1.2). 223 FEC Repair Packet: At a sender (respectively, at a receiver) a 224 payload submitted to (respectively, received from) the transport 225 protocol containing one repair symbol along with a Repair FEC 226 Payload ID and possibly an RTP header. 228 The above terminology is illustrated in Figure 1 (sender's point of 229 view): 231 +----------------------+ 232 | Application | 233 +----------------------+ 234 | 235 | (1) Application Data Units (ADUs) 236 | 237 v 238 +----------------------+ +----------------+ 239 | FEC Framework | | | 240 | |-------------------------->| FEC Scheme | 241 |(2) Construct source |(3) Source Block | | 242 | blocks | |(4) FEC Encoding| 243 |(6) Construct FEC |<--------------------------| | 244 | source and repair | | | 245 | packets |(5) Explicit Source FEC | | 246 +----------------------+ Payload IDs +----------------+ 247 | Repair FEC Payload IDs 248 | Repair symbols 249 | 250 |(7) FEC source and repair packets 251 v 252 +----------------------+ 253 | Transport Layer | 254 | (e.g., UDP) | 255 +----------------------+ 257 Figure 1: Terminology used in this document (sender). 259 3.2. Notations 261 This document uses the following notations: Some of them are FEC 262 scheme specific: 263 k denotes the number of source symbols in a source block. 264 max_k denotes the maximum number of source symbols for any source 265 block. 266 n denotes the number of encoding symbols generated for a source 267 block. 268 E denotes the encoding symbol length in bytes. 269 GF(q) denotes a finite field (also known as Galois Field) with q 270 elements. We assume that q = 2^^m in this document. 271 m defines the length of the elements in the finite field, in 272 bits. In this document, m is such that 2 <= m <= 16. 273 q defines the number of elements in the finite field. We have: 274 q = 2^^m in this specification. 276 CR denotes the "code rate", i.e., the k/n ratio. 277 a^^b denotes a raised to the power b. 279 Some of them are FECFRAME framework specific: 280 B denotes the number of ADUs per ADU block. 281 max_B denotes the maximum number of ADUs for any ADU block. 283 3.3. Abbreviations 285 This document uses the following abbreviations: 286 ADU stands for Application Data Unit. 287 ADUI stands for Application Data Unit Information. 288 ESI stands for Encoding Symbol ID. 289 FEC stands for Forward Error (or Erasure) Correction code. 290 FFCI stands for FEC Framework Configuration Information. 291 FSSI stands for FEC Scheme Specific Information. 292 MDS stands for Maximum Distance Separable code. 293 SBN stands for Source Block Number. 294 SDP stands for Session Description Protocol. 296 4. Common Procedures Related to the ADU Block and Source Block Creation 298 This section introduces the procedures that are used during the ADU 299 block and the related source block creation, for the FEC scheme 300 considered. 302 4.1. Restrictions 304 This specification has the following restrictions: 305 o there MUST be exactly one source symbol per ADUI, and therefore 306 per ADU; 307 o there MUST be exactly one repair symbol per FEC Repair Packet; 308 o there MUST be exactly one source block per ADU block; 310 4.2. ADU Block Creation 312 Two kinds of limitations exist that impact the ADU block creation: 313 o at the FEC Scheme level: the finite field size (m parameter) 314 directly impacts the maximum source block size and the maximum 315 number of encoding symbols; 316 o at the FECFRAME instance level: the target use-case can have real- 317 time constraints that can/will define a maximum ADU block size; 318 Note that terminology "maximum source block size" and "maximum ADU 319 block size" depends on the point of view that is adopted (FEC Scheme 320 versus FECFRAME instance). However, in this document, both refer to 321 the same value since Section 4.1 requires there is exactly one source 322 symbol per ADU. We now detail each of these aspects. 324 The finite field size parameter, m, defines the number of non zero 325 elements in this field which is equal to: q - 1 = 2^^m - 1. This q - 326 1 value is also the theoretical maximum number of encoding symbols 327 that can be produced for a source block. For instance, when m = 8 328 (default) there is a maximum of 2^^8 - 1 = 255 encoding symbols. So: 329 k < n <= 255. Given the target FEC code rate (e.g., provided by the 330 end-user or upper application when starting the FECFRAME framework, 331 and taking into account the known or estimated packet loss rate), the 332 sender calculates: 333 max_k = floor((2^^m - 1) * CR) 334 This max_k value leaves enough room for the sender to produce the 335 desired number of repair symbols. Since there is one source symbol 336 per ADU, max_k is also an upper bound to the maximum number of ADUs 337 per ADU block. 339 The source ADU flows MAY have real-time constraints. When there are 340 multiple flows, with different real-time constraints, let us consider 341 the most stringent constraints (see [RFC6363], section 10.2, item 6 342 for recommendations when several flows are globally protected). In 343 that case the maximum number of ADUs of an ADU block must not exceed 344 a certain threshold since it directly impacts the decoding delay. 345 The larger the ADU block size, the longer a decoder may have to wait 346 until it has received a sufficient number of encoding symbols for 347 decoding to succeed, and therefore the larger the decoding delay. 348 When the target use-case is known, these real-time constraints result 349 in an upper bound to the ADU block size, max_rt. 351 For instance, if the use-case specifies a maximum decoding latency, 352 l, and if each source ADU covers a duration d of a continuous media 353 (we assume here the simple case of a constant bit rate ADU flow), 354 then the ADU block size must not exceed: 355 max_rt = floor(l / d) 356 After encoding, this block will produce a set of at most n = max_rt / 357 CR encoding symbols. These n encoding symbols will have to be sent 358 at a rate of n / l packets per second. For instance, with d = 10 ms, 359 l = 1 s, max_rt = 100 ADUs. 361 If we take into account all these constraints, we find: 362 max_B = min(max_k, max_rt) 363 This max_B parameter is an upper bound to the number of ADUs that can 364 constitute an ADU block. 366 4.3. Source Block Creation 368 In its most general form the FECFRAME framework and the Reed-Solomon 369 FEC scheme are meant to protect a set of independent flows. Since 370 the flows have no relationship to one another, the ADU size of each 371 flow can potentially vary significantly. Even in the special case of 372 a single flow, the ADU sizes can largely vary (e.g., the various 373 frames of a "Group of Pictures (GOP) of an H.264 flow will have 374 different sizes). This diversity must be addressed since the Reed- 375 Solomon FEC scheme requires a constant encoding symbol size (E 376 parameter) per source block. Since this specification requires that 377 there is only one source symbol per ADU, E must be large enough to 378 contain all the ADUs of an ADU block along with their prepended 3 379 bytes (see below). 381 In situations where E is determined per source block (default, 382 specified by the FFCI/FSSI with S = 0, Section 5.1.1.2), E is equal 383 to the size of the largest ADU of this source block plus three (for 384 the prepended 3 bytes, see below). In this case, upon receiving the 385 first FEC Repair Packet for this source block, since this packet MUST 386 contain a single repair symbol (Section 5.1.3), a receiver determines 387 the E parameter used for this source block. 389 In situations where E is fixed (specified by the FFCI/FSSI with S = 390 1, Section 5.1.1.2), then E must be greater or equal to the size of 391 the largest ADU of this source block plus three (for the prepended 3 392 bytes, see below). If this is not the case, an error is returned. 393 How to handle this error is use-case specific (e.g., a larger E 394 parameter may be communicated to the receivers in an updated FFCI 395 message, using an appropriate mechanism) and is not considered by 396 this specification. 398 The ADU block is always encoded as a single source block. There are 399 a total of B <= max_B ADUs in this ADU block. For the ADU i, with 0 400 <= i <= B-1, 3 bytes are prepended (Figure 2): 401 o The first byte, FID[i] (Flow ID), contains the integer identifier 402 associated to the source ADU flow to which this ADU belongs to. 403 It is assumed that a single byte is sufficient, or said 404 differently, that no more than 256 flows will be protected by a 405 single instance of the FECFRAME framework. 406 o The following two bytes, L[i] (Length), contain the length of this 407 ADU, in network byte order (i.e., big endian). This length is for 408 the ADU itself and does not include the FID[i], L[i], or Pad[i] 409 fields. 411 Then zero padding is added to ADU i (if needed) in field Pad[i], for 412 alignment purposes up to a size of exactly E bytes. The data unit 413 resulting from the ADU i and the F[i], L[i] and Pad[i] fields, is 414 called ADU Information (or ADUI). Each ADUI contributes to exactly 415 one source symbol to the source block. 417 Encoding Symbol Length (E) 418 < -------------------------------------------------------------- > 419 +----+----+-----------------------+------------------------------+ 420 |F[0]|L[0]| ADU[0] | Pad[0] | 421 +----+----+----------+------------+------------------------------+ 422 |F[1]|L[1]| ADU[1] | Pad[1] | 423 +----+----+----------+-------------------------------------------+ 424 |F[2]|L[2]| ADU[2] | 425 +----+----+------+-----------------------------------------------+ 426 |F[3]|L[3]|ADU[3]| Pad[3] | 427 +----+----+------+-----------------------------------------------+ 428 \_______________________________ _______________________________/ 429 \/ 430 simple FEC encoding 432 +----------------------------------------------------------------+ 433 | Repair 4 | 434 +----------------------------------------------------------------+ 435 . . 436 . . 437 +----------------------------------------------------------------+ 438 | Repair 7 | 439 +----------------------------------------------------------------+ 441 Figure 2: Source block creation, for code rate 1/2 (equal number of 442 source and repair symbols, 4 in this example), and S = 0. 444 Note that neither the initial 3 bytes nor the optional padding are 445 sent over the network. However, they are considered during FEC 446 encoding. It means that a receiver who lost a certain FEC source 447 packet (e.g., the UDP datagram containing this FEC source packet) 448 will be able to recover the ADUI if FEC decoding succeeds. Thanks to 449 the initial 3 bytes, this receiver will get rid of the padding (if 450 any) and identify the corresponding ADU flow. 452 5. Simple Reed-Solomon FEC Scheme over GF(2^^m) for Arbitrary ADU Flows 454 This Fully-Specified FEC Scheme specifies the use of Reed-Solomon 455 codes over GF(2^^m), with 2 <= m <= 16, with a simple FEC encoding 456 for arbitrary packet flows. 458 5.1. Formats and Codes 460 5.1.1. FEC Framework Configuration Information 462 The FEC Framework Configuration Information (or FFCI) includes 463 information that MUST be communicated between the sender and 464 receiver(s). More specifically, it enables the synchronization of 465 the FECFRAME sender and receiver instances. It includes both 466 mandatory elements and scheme-specific elements, as detailed below. 468 5.1.1.1. Mandatory Information 470 FEC Encoding ID: the value assigned to this fully-specified FEC 471 scheme MUST be XXX, as assigned by IANA (Section 8). 472 When SDP is used to communicate the FFCI, this FEC Encoding ID is 473 carried in the 'encoding-id' parameter. 475 5.1.1.2. FEC Scheme-Specific Information 477 The FEC Scheme Specific Information (FSSI) includes elements that are 478 specific to the present FEC scheme. More precisely: 479 Encoding symbol length (E): a non-negative integer that indicates 480 either the length of each encoding symbol in bytes ("strict" mode, 481 i.e., if S = 1), or the maximum length of any encoding symbol 482 (i.e., if S = 0). 483 Strict (S) flag: when set to 1 this flag indicates that the E 484 parameter is the actual encoding symbol length value for each 485 block of the session (unless otherwise notified by an updated FFCI 486 if this possibility is considered by the use-case or CDP). When 487 set to 0 this flag indicates that the E parameter is the maximum 488 encoding symbol length value for each block of the session (unless 489 otherwise notified by an updated FFCI if this possibility is 490 considered by the use-case or CDP). 491 m parameter (m): an integer that defines the length of the elements 492 in the finite field, in bits. We have: 2 <= m <= 16. 493 These elements are required both by the sender (Reed-Solomon encoder) 494 and the receiver(s) (Reed-Solomon decoder). 496 When SDP is used to communicate the FFCI, this FEC scheme-specific 497 information is carried in the 'fssi' parameter in textual 498 representation as specified in [RFC6364]. For instance: 500 fssi=E:1400,S:0,m:8 502 If another mechanism requires the FSSI to be carried as an opaque 503 octet string (for instance after a Base64 encoding), the encoding 504 format consists of the following 3 octets of Figure 3: 505 o Encoding symbol length (E): 16 bit field. 506 o Strict (S) flag: 1 bit field. 507 o m parameter (m): 7 bit field. 509 0 1 2 510 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 511 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 512 | Encoding Symbol Length (E) |S| m | 513 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 515 Figure 3: FSSI encoding format. 517 5.1.2. Explicit Source FEC Payload ID 519 A FEC source packet MUST contain an Explicit Source FEC Payload ID 520 that is appended to the end of the packet as illustrated in Figure 4. 522 +--------------------------------+ 523 | IP Header | 524 +--------------------------------+ 525 | Transport Header | 526 +--------------------------------+ 527 | ADU | 528 +--------------------------------+ 529 | Explicit Source FEC Payload ID | 530 +--------------------------------+ 532 Figure 4: Structure of a FEC Source Packet with the Explicit Source 533 FEC Payload ID. 535 More precisely, the Explicit Source FEC Payload ID is composed of the 536 Source Block Number, the Encoding Symbol ID, and the Source Block 537 Length. The length of the first two fields depends on the m 538 parameter (transmitted separately in the FFCI, Section 5.1.1.2): 539 Source Block Number (SBN) (32-m bit field): this field identifies 540 the source block to which this FEC source packet belongs. 541 Encoding Symbol ID (ESI) (m bit field): this field identifies the 542 source symbol contained in this FEC source packet. This value is 543 such that 0 <= ESI <= k - 1 for source symbols. 544 Source Block Length (k) (16 bit field): this field provides the 545 number of source symbols for this source block, i.e., the k 546 parameter. If 16 bits are too much when m <= 8, it is needed when 547 8 < m <= 16. Therefore we provide a single common format 548 regardless of m. 550 0 1 2 3 551 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 552 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 553 | Source Block Number (24 bits) | Enc. Symb. ID | 554 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 555 | Source Block Length (k) | 556 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 558 Figure 5: Source FEC Payload ID encoding format for m = 8 (default). 560 0 1 2 3 561 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 562 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 563 | Source Block Nb (16 bits) | Enc. Symbol ID (16 bits) | 564 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 565 | Source Block Length (k) | 566 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 568 Figure 6: Source FEC Payload ID encoding format for m = 16. 570 The format of the Source FEC Payload ID for m = 8 and m = 16 are 571 illustrated in Figure 5 and Figure 6 respectively. 573 5.1.3. Repair FEC Payload ID 575 A FEC repair packet MUST contain a Repair FEC Payload ID that is 576 prepended to the repair symbol(s) as illustrated in Figure 7. There 577 MUST be a single repair symbol per FEC repair packet. 579 +--------------------------------+ 580 | IP Header | 581 +--------------------------------+ 582 | Transport Header | 583 +--------------------------------+ 584 | Repair FEC Payload ID | 585 +--------------------------------+ 586 | Repair Symbol | 587 +--------------------------------+ 589 Figure 7: Structure of a FEC Repair Packet with the Repair FEC 590 Payload ID. 592 More precisely, the Repair FEC Payload ID is composed of the Source 593 Block Number, the Encoding Symbol ID, and the Source Block Length. 594 The length of the first two fields depends on the m parameter 595 (transmitted separately in the FFCI, Section 5.1.1.2): 597 Source Block Number (SBN) (32-m bit field): this field identifies 598 the source block to which the FEC repair packet belongs. 599 Encoding Symbol ID (ESI) (m bit field) this field identifies the 600 repair symbol contained in this FEC repair packet. This value is 601 such that k <= ESI <= n - 1 for repair symbols. 602 Source Block Length (k) (16 bit field): this field provides the 603 number of source symbols for this source block, i.e., the k 604 parameter. If 16 bits are too much when m <= 8, it is needed when 605 8 < m <= 16. Therefore we provide a single common format 606 regardless of m. 608 0 1 2 3 609 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 610 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 611 | Source Block Number (24 bits) | Enc. Symb. ID | 612 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 613 | Source Block Length (k) | 614 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 616 Figure 8: Repair FEC Payload ID encoding format for m = 8 (default). 618 0 1 2 3 619 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 620 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 621 | Source Block Nb (16 bits) | Enc. Symbol ID (16 bits) | 622 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 623 | Source Block Length (k) | 624 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 626 Figure 9: Repair FEC Payload ID encoding format for m = 16. 628 The format of the Repair FEC Payload ID for m = 8 and m = 16 are 629 illustrated in Figure 8 and Figure 9 respectively. 631 5.2. Procedures 633 The following procedures apply: 634 o The source block creation MUST follow the procedures specified in 635 Section 4.3. 636 o The SBN value MUST start with value 0 for the first block of the 637 ADU flow and MUST be incremented by 1 for each new source block. 638 Wrapping to zero will happen for long sessions, after value 639 2^^(32-m) - 1. 640 o The ESI of encoding symbols MUST start with value 0 for the first 641 symbol and MUST be managed sequentially. The first k values (0 <= 642 ESI <= k - 1) identify source symbols whereas the last n-k values 643 (k <= ESI <= n - 1) identify repair symbols. 645 o The FEC repair packet creation MUST follow the procedures 646 specified in Section 5.1.3. 648 5.3. FEC Code Specification 650 The present document inherits from [RFC5510] the specification of the 651 core Reed-Solomon codes based on Vandermonde matrices for a packet 652 transmission channel. 654 6. Security Considerations 656 The FEC Framework document [RFC6363] provides a comprehensive 657 analysis of security considerations applicable to FEC schemes. 658 Therefore the present section follows the security considerations 659 section of [RFC6363] and only discusses topics that are specific to 660 the use of Reed-Solomon codes. 662 6.1. Attacks Against the Data Flow 664 6.1.1. Access to Confidential Content 666 The Reed-Solomon FEC Scheme specified in this document does not 667 change the recommendations of [RFC6363]. To summarize, if 668 confidentiality is a concern, it is RECOMMENDED that one of the 669 solutions mentioned in [RFC6363] is used, with special considerations 670 to the way this solution is applied (e.g., before versus after FEC 671 protection, and within the end-system versus in a middlebox), to the 672 operational constraints (e.g., performing FEC decoding in a protected 673 environment may be complicated or even impossible) and to the threat 674 model. 676 6.1.2. Content Corruption 678 The Reed-Solomon FEC Scheme specified in this document does not 679 change the recommendations of [RFC6363]. To summarize, it is 680 RECOMMENDED that one of the solutions mentioned in [RFC6363] is used 681 on both the FEC Source and Repair Packets. 683 6.2. Attacks Against the FEC Parameters 685 The FEC Scheme specified in this document defines parameters that can 686 be the basis of several attacks. More specifically, the following 687 parameters of the FFCI may be modified by an attacker 688 (Section 5.1.1.2): 689 o FEC Encoding ID: changing this parameter leads the receiver to 690 consider a different FEC Scheme, which enables an attacker to 691 create a Denial of Service (DoS). 693 o Encoding symbol length (E): setting this E parameter to a value 694 smaller than the valid one enables an attacker to create a DoS 695 since the repair symbols and certain source symbols will be larger 696 than E, which is an incoherency for the receiver. Setting this E 697 parameter to a value larger than the valid one has similar impacts 698 when S=1 since the received repair symbol size will be smaller 699 than expected. On the opposite it will not lead to any 700 incoherency when S=0 since the actual symbol length value for the 701 block is determined by the size of any received repair symbol, as 702 long as this value is smaller than E. However setting this E 703 parameter to a larger value may have impacts on receivers that 704 pre-allocate memory space in advance to store incoming symbols. 705 o Strict (S) flag: flipping this S flag from 0 to 1 (i.e., E is now 706 considered as a strict value) enables an attacker to mislead the 707 receiver if the actual symbol size varies over different source 708 blocks. Flipping this S flag from 1 to 0 has no major 709 consequences unless the receiver requires to have a fixed E value 710 (e.g., because the receiver pre-allocates memory space). 711 o m parameter: changing this parameter triggers a DoS since the 712 receiver and sender will consider different codes, and the 713 receiver will interpret the Explicit Source FEC Payload ID and 714 Repair FEC Payload ID differently. Additionally, by increasing 715 this m parameter to a larger value (typically m=16 rather than 8, 716 when both values are possible in the target use-case) will create 717 additional processing load at a receiver if decoding is attempted. 719 It is therefore RECOMMENDED that security measures are taken to 720 guarantee the FFCI integrity, as specified in [RFC6363]. How to 721 achieve this depends on the way the FFCI is communicated from the 722 sender to the receiver, which is not specified in this document. 724 Similarly, attacks are possible against the Explicit Source FEC 725 Payload ID and Repair FEC Payload ID: by modifying the Source Block 726 Number (SBN), or the Encoding Symbol ID (ESI), or the Source Block 727 Length (k), an attacker can easily corrupt the block identified by 728 the SBN. Other consequences, that are use-case and/or CDP dependant, 729 may also happen. It is therefore RECOMMENDED that security measures 730 are taken to guarantee the FEC Source and Repair Packets as stated in 731 [RFC6363]. 733 6.3. When Several Source Flows are to be Protected Together 735 The Reed-Solomon FEC Scheme specified in this document does not 736 change the recommendations of [RFC6363]. 738 6.4. Baseline Secure FEC Framework Operation 740 The Reed-Solomon FEC Scheme specified in this document does not 741 change the recommendations of [RFC6363] concerning the use of the 742 IPsec/ESP security protocol as a mandatory to implement (but not 743 mandatory to use) security scheme. This is well suited to situations 744 where the only insecure domain is the one over which the FEC 745 Framework operates. 747 7. Operations and Management Considerations 749 The FEC Framework document [RFC6363] provides a comprehensive 750 analysis of operations and management considerations applicable to 751 FEC schemes. Therefore the present section only discusses topics 752 that are specific to the use of Reed-Solomon codes as specified in 753 this document. 755 7.1. Operational Recommendations: Finite Field Size (m) 757 The present document requires that m, the length of the elements in 758 the finite field, in bits, is such that 2 <= m <= 16. However all 759 possibilities are not equally interesting from a practical point of 760 view. It is expected that m=8, the default value, will be mostly 761 used since it offers the possibility to have small to medium sized 762 source blocks and/or a significant number of repair symbols (i.e., k 763 < n <= 255). Additionally, elements in the finite field are 8 bits 764 long which makes read/write memory operations aligned on bytes during 765 encoding and decoding. 767 An alternative when it is known that only very small source blocks 768 will be used is m=4 (i.e., k < n <= 15). Elements in the finite 769 field are 4 bits long, so if two elements are accessed at a time, 770 read/write memory operations are aligned on bytes during encoding and 771 decoding. 773 An alternative when very large source blocks are needed is m=16 774 (i.e., k < n <= 65535). However this choice has significant impacts 775 on the processing load. For instance using pre-calculated tables to 776 speedup operations over the finite field (as done with smaller finite 777 fields) may require a prohibitive amount of memory to be used on 778 embedded platforms. Alternative lightweight solutions (e.g., 779 [RFC5170]) may be preferred in situations where the processing load 780 is an issue and the source block length is large enough 781 [Matsuzono10]. 783 Since several values for the m parameter are possible, the use-case 784 SHOULD define which value(s) need(s) to be supported. In situations 785 where this is not specified, the default m=8 value SHOULD be 786 supported and used. 788 8. IANA Considerations 790 Values of FEC Encoding IDs are subject to IANA registration. 791 [RFC6363] defines general guidelines on IANA considerations. In 792 particular it defines a registry called FEC Framework (FECFRAME) FEC 793 Encoding IDs whose values are granted on an IETF Consensus basis. 795 This document registers one value in the FEC Framework (FECFRAME) FEC 796 Encoding IDs registry as follows: 797 o XXX refers to the Simple Reed-Solomon [RFC5510] FEC Scheme over 798 GF(2^^m) for Arbitrary Packet Flows. 800 9. Acknowledgments 802 The authors want to thank Hitoshi Asaeda and Ali Begen for their 803 valuable comments. 805 10. References 807 10.1. Normative References 809 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 810 Requirement Levels", RFC 2119. 812 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 813 Correction (FEC) Building Block", RFC 5052, August 2007. 815 [RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, 816 "Reed-Solomon Forward Error Correction (FEC) Schemes", 817 RFC 5510, April 2009. 819 [RFC6363] Watson, M., Begen, A., and V. Roca, "Forward Error 820 Correction (FEC) Framework", RFC 6363, September 2011. 822 [RFC6364] Begen, A., "Session Description Protocol Elements for the 823 Forward Error Correction (FEC) Framework", RFC 6364, 824 October 2011. 826 10.2. Informative References 828 [RS-codec] 829 Rizzo, L., "Reed-Solomon FEC codec (C language)", original 830 codec: http://info.iet.unipi.it/~luigi/vdm98/ 831 vdm980702.tgz, improved codec: http://openfec.org/, 832 July 1998. 834 [Rizzo97] Rizzo, L., "Effective Erasure Codes for Reliable Computer 835 Communication Protocols", ACM SIGCOMM Computer 836 Communication Review Vol.27, No.2, pp.24-36, April 1997. 838 [Matsuzono10] 839 Matsuzono, K., Detchart, J., Cunche, M., Roca, V., and H. 840 Asaeda, "Performance Analysis of a High-Performance Real- 841 Time Application with Several AL-FEC Schemes", 35th Annual 842 IEEE Conference on Local Computer Networks (LCN 2010), 843 October 2010. 845 [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity 846 Check (LDPC) Forward Error Correction", RFC 5170, 847 June 2008. 849 [RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, 850 "Raptor Forward Error Correction Scheme", RFC 5053, 851 June 2007. 853 [RFC5775] Luby, M., Watson, M., and L. Vicisano, "Asynchronous 854 Layered Coding (ALC) Protocol Instantiation", RFC 5775, 855 April 2010. 857 [RFC5740] Adamson, B., Bormann, C., Handley, M., and J. Macker, 858 "Negative-acknowledgment (NACK)-Oriented Reliable 859 Multicast (NORM) Protocol", RFC 5740, November 2009. 861 Authors' Addresses 863 Vincent Roca 864 INRIA 865 655, av. de l'Europe 866 Inovallee; Montbonnot 867 ST ISMIER cedex 38334 868 France 870 Email: vincent.roca@inria.fr 871 URI: http://planete.inrialpes.fr/people/roca/ 872 Mathieu Cunche 873 INSA-Lyon/INRIA 874 Laboratoire CITI 875 6 av. des Arts 876 Villeurbanne cedex 69621 877 France 879 Email: mathieu.cunche@inria.fr 880 URI: http://mathieu.cunche.free.fr/ 882 Jerome Lacan 883 ISAE, Univ. of Toulouse 884 10 av. Edouard Belin; BP 54032 885 Toulouse cedex 4 31055 886 France 888 Email: jerome.lacan@isae.fr 889 URI: http://personnel.isae.fr/jerome-lacan/ 891 Amine Bouabdallah 892 ISAE, Univ. of Toulouse 893 10 av. Edouard Belin; BP 54032 894 Toulouse cedex 4 31055 895 France 897 Email: amine.bouabdallah@gmail.com 899 Kazuhisa Matsuzono 900 Keio University 901 Graduate School of Media and Governance 902 5322 Endo 903 Fujisawa, Kanagawa 252-8520 904 Japan 906 Email: kazuhisa@sfc.wide.ad.jp