idnits 2.17.1 draft-ietf-fecframe-simple-rs-03.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 (March 8, 2012) is 4425 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 419 -- Looks like a reference, but probably isn't: '1' on line 421 -- Looks like a reference, but probably isn't: '2' on line 423 -- Looks like a reference, but probably isn't: '3' on line 425 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: September 9, 2012 NICTA 6 J. Lacan 7 A. Bouabdallah 8 ISAE/LAAS-CNRS 9 K. Matsuzono 10 Keio University 11 March 8, 2012 13 Simple Reed-Solomon Forward Error Correction (FEC) Scheme for FECFRAME 14 draft-ietf-fecframe-simple-rs-03 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 September 9, 2012. 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 ESI stands for Encoding Symbol ID. 288 FEC stands for Forward Error (or Erasure) Correction code. 289 FFCI stands for FEC Framework Configuration Information. 290 FSSI stands for FEC Scheme Specific Information. 291 MDS stands for Maximum Distance Separable code. 292 SDP stands for Session Description Protocol. 294 4. Common Procedures Related to the ADU Block and Source Block Creation 296 This section introduces the procedures that are used during the ADU 297 block and the related source block creation, for the FEC scheme 298 considered. 300 4.1. Restrictions 302 This specification has the following restrictions: 303 o there MUST be exactly one source symbol per ADUI, and therefore 304 per ADU; 305 o there MUST be exactly one repair symbol per FEC Repair Packet; 306 o there MUST be exactly one source block per ADU block; 308 4.2. ADU Block Creation 310 Two kinds of limitations MUST be considered, that impact the ADU 311 block creation: 312 o at the FEC Scheme level: the finite field size (m parameter) 313 directly impacts the maximum source block size and the maximum 314 number of encoding symbols; 315 o at the FECFRAME instance level: the target use-case MAY have real- 316 time constraints that MAY define a maximum ADU block size; 317 Note that terminology "maximum source block size" and "maximum ADU 318 block size" depends on the point of view that is adopted (FEC Scheme 319 versus FECFRAME instance). However, in this document, both refer to 320 the same value since Section 4.1 requires there is exactly one source 321 symbol per ADU. We now detail each of these aspects. 323 The finite field size parameter, m, defines the number of non zero 324 elements in this field which is equal to: q - 1 = 2^^m - 1. This q - 325 1 value is also the theoretical maximum number of encoding symbols 326 that can be produced for a source block. For instance, when m = 8 327 (default) there is a maximum of 2^^8 - 1 = 255 encoding symbols. So: 328 k < n <= 255. Given the target FEC code rate (e.g., provided by the 329 end-user or upper application when starting the FECFRAME framework, 330 and taking into account the known or estimated packet loss rate), the 331 sender calculates: 332 max_k = floor((2^^m - 1) * CR) 333 This max_k value leaves enough room for the sender to produce the 334 desired number of repair symbols. Since there is one source symbol 335 per ADU, max_k is also an upper bound to the maximum number of ADUs 336 per ADU block. 338 The source ADU flows MAY have real-time constraints. When there are 339 multiple flows, with different real-time constraints, let us consider 340 the most stringent constraints (see [RFC6363], section 10.2, item 6 341 for recommendations when several flows are globally protected). In 342 that case the maximum number of ADUs of an ADU block must not exceed 343 a certain threshold since it directly impacts the decoding delay. 344 The larger the ADU block size, the longer a decoder may have to wait 345 until it has received a sufficient number of encoding symbols for 346 decoding to succeed, and therefore the larger the decoding delay. 347 When the target use-case is known, these real-time constraints result 348 in an upper bound to the ADU block size, max_rt. 350 For instance, if the use-case specifies a maximum decoding latency, 351 l, and if each source ADU covers a duration d of a continuous media 352 (we assume here the simple case of a constant bit rate ADU flow), 353 then the ADU block size must not exceed: 354 max_rt = floor(l / d) 355 After encoding, this block will produce a set of at most n = max_rt / 356 CR encoding symbols. These n encoding symbols will have to be sent 357 at a rate of n / l packets per second. For instance, with d = 10 ms, 358 l = 1 s, max_rt = 100 ADUs. 360 If we take into account all these constraints, we find: 361 max_B = min(max_k, max_rt) 362 This max_B parameter is an upper bound to the number of ADUs that can 363 constitute an ADU block. 365 4.3. Source Block Creation 367 In its most general form the FECFRAME framework and the Reed-Solomon 368 FEC scheme are meant to protect a set of independent flows. Since 369 the flows have no relationship to one another, the ADU size of each 370 flow can potentially vary significantly. Even in the special case of 371 a single flow, the ADU sizes can largely vary (e.g., the various 372 frames of a "Group of Pictures (GOP) of an H.264 flow will have 373 different sizes). This diversity must be addressed since the Reed- 374 Solomon FEC scheme requires a constant encoding symbol size (E 375 parameter) per source block. Since this specification requires that 376 there is only one source symbol per ADU, E must be large enough to 377 contain all the ADUs of an ADU block along with their prepended 3 378 bytes (see below). 380 In situations where E is determined per source block (default, 381 specified by the FFCI/FSSI with S = 0, Section 5.1.1.2), E is equal 382 to the size of the largest ADU of this source block plus three (for 383 the prepended 3 bytes, see below). In this case, upon receiving the 384 first FEC Repair Packet for this source block, since this packet MUST 385 contain a single repair symbol (Section 5.1.3), a receiver determines 386 the E parameter used for this source block. 388 In situations where E is fixed (specified by the FFCI/FSSI with S = 389 1, Section 5.1.1.2), then E must be greater or equal to the size of 390 the largest ADU of this source block plus three (for the prepended 3 391 bytes, see below). If this is not the case, an error is returned. 392 How to handle this error is use-case specific (e.g., a larger E 393 parameter may be communicated to the receivers in an updated FFCI 394 message, using an appropriate mechanism) and is not considered by 395 this specification. 397 The ADU block is always encoded as a single source block. There are 398 a total of B <= max_B ADUs in this ADU block. For the ADU i, with 0 399 <= i <= B-1, 3 bytes are prepended (Figure 2): 400 o The first byte, FID[i] (Flow ID), contains the integer identifier 401 associated to the source ADU flow to which this ADU belongs to. 402 It is assumed that a single byte is sufficient, or said 403 differently, that no more than 256 flows will be protected by a 404 single instance of the FECFRAME framework. 405 o The following two bytes, L[i] (Length), contain the length of this 406 ADU, in network byte order (i.e., big endian). This length is for 407 the ADU itself and does not include the FID[i], L[i], or Pad[i] 408 fields. 410 Then zero padding is added to ADU i (if needed) in field Pad[i], for 411 alignment purposes up to a size of exactly E bytes. The data unit 412 resulting from the ADU i and the F[i], L[i] and Pad[i] fields, is 413 called ADU Information (or ADUI). Each ADUI contributes to exactly 414 one source symbol to the source block. 416 Encoding Symbol Length (E) 417 < -------------------------------------------------------------- > 418 +----+----+-----------------------+------------------------------+ 419 |F[0]|L[0]| ADU[0] | Pad[0] | 420 +----+----+----------+------------+------------------------------+ 421 |F[1]|L[1]| ADU[1] | Pad[1] | 422 +----+----+----------+-------------------------------------------+ 423 |F[2]|L[2]| ADU[2] | 424 +----+----+------+-----------------------------------------------+ 425 |F[3]|L[3]|ADU[3]| Pad[3] | 426 +----+----+------+-----------------------------------------------+ 427 \_______________________________ _______________________________/ 428 \/ 429 simple FEC encoding 431 +----------------------------------------------------------------+ 432 | Repair 4 | 433 +----------------------------------------------------------------+ 434 . . 435 . . 436 +----------------------------------------------------------------+ 437 | Repair 7 | 438 +----------------------------------------------------------------+ 440 Figure 2: Source block creation, for code rate 1/2 (equal number of 441 source and repair symbols, 4 in this example), and S = 0. 443 Note that neither the initial 3 bytes nor the optional padding are 444 sent over the network. However, they are considered during FEC 445 encoding. It means that a receiver who lost a certain FEC source 446 packet (e.g., the UDP datagram containing this FEC source packet) 447 will be able to recover the ADUI if FEC decoding succeeds. Thanks to 448 the initial 3 bytes, this receiver will get rid of the padding (if 449 any) and identify the corresponding ADU flow. 451 5. Simple Reed-Solomon FEC Scheme over GF(2^^m) for Arbitrary ADU Flows 453 This Fully-Specified FEC Scheme specifies the use of Reed-Solomon 454 codes over GF(2^^m), with 2 <= m <= 16, with a simple FEC encoding 455 for arbitrary packet flows. 457 5.1. Formats and Codes 459 5.1.1. FEC Framework Configuration Information 461 The FEC Framework Configuration Information (or FFCI) includes 462 information that MUST be communicated between the sender and 463 receiver(s). More specifically, it enables the synchronization of 464 the FECFRAME sender and receiver instances. It includes both 465 mandatory elements and scheme-specific elements, as detailed below. 467 5.1.1.1. Mandatory Information 469 FEC Encoding ID: the value assigned to this fully-specified FEC 470 scheme MUST be XXX, as assigned by IANA (Section 8). 471 When SDP is used to communicate the FFCI, this FEC Encoding ID is 472 carried in the 'encoding-id' parameter. 474 5.1.1.2. FEC Scheme-Specific Information 476 The FEC Scheme Specific Information (FSSI) includes elements that are 477 specific to the present FEC scheme. More precisely: 478 Encoding symbol length (E): a non-negative integer that indicates 479 either the length of each encoding symbol in bytes ("strict" mode, 480 i.e., if S = 1), or the maximum length of any encoding symbol 481 (i.e., if S = 0). 482 Strict (S) flag: when set to 1 this flag indicates that the E 483 parameter is the actual encoding symbol length value for each 484 block of the session (unless otherwise notified by an updated FFCI 485 if this possibility is considered by the use-case or CDP). When 486 set to 0 this flag indicates that the E parameter is the maximum 487 encoding symbol length value for each block of the session (unless 488 otherwise notified by an updated FFCI if this possibility is 489 considered by the use-case or CDP). 490 m parameter (m): an integer that defines the length of the elements 491 in the finite field, in bits. We have: 2 <= m <= 16. 492 These elements are required both by the sender (Reed-Solomon encoder) 493 and the receiver(s) (Reed-Solomon decoder). 495 When SDP is used to communicate the FFCI, this FEC scheme-specific 496 information is carried in the 'fssi' parameter in textual 497 representation as specified in [RFC6364]. For instance: 499 fssi=E:1400,S:0,m:8 501 If another mechanism requires the FSSI to be carried as an opaque 502 octet string (for instance after a Base64 encoding), the encoding 503 format consists of the following 3 octets: 504 o Encoding symbol length (E): 16 bit field. 505 o Strict (S) flag: 1 bit field. 506 o m parameter (m): 7 bit field. 508 0 1 2 509 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 510 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 511 | Encoding Symbol Length (E) |S| m | 512 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 514 Figure 3: FSSI encoding format. 516 5.1.2. Explicit Source FEC Payload ID 518 A FEC source packet MUST contain an Explicit Source FEC Payload ID 519 that is appended to the end of the packet as illustrated in Figure 4. 521 +--------------------------------+ 522 | IP Header | 523 +--------------------------------+ 524 | Transport Header | 525 +--------------------------------+ 526 | ADU | 527 +--------------------------------+ 528 | Explicit Source FEC Payload ID | 529 +--------------------------------+ 531 Figure 4: Structure of a FEC Source Packet with the Explicit Source 532 FEC Payload ID. 534 More precisely, the Explicit Source FEC Payload ID is composed of the 535 Source Block Number, the Encoding Symbol ID, and the Source Block 536 Length. The length of the first two fields depends on the m 537 parameter (transmitted separately in the FFCI, Section 5.1.1.2): 538 Source Block Number (SBN) (32-m bit field): this field identifies 539 the source block to which this FEC source packet belongs. 540 Encoding Symbol ID (ESI) (m bit field): this field identifies the 541 source symbol contained in this FEC source packet. This value is 542 such that 0 <= ESI <= k - 1 for source symbols. 543 Source Block Length (k) (16 bit field): this field provides the 544 number of source symbols for this source block, i.e., the k 545 parameter. If 16 bits are too much when m <= 8, it is needed when 546 8 < m <= 16. Therefore we provide a single common format 547 regardless of m. 549 0 1 2 3 550 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 551 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 552 | Source Block Number (24 bits) | Enc. Symb. ID | 553 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 554 | Source Block Length (k) | 555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 557 Figure 5: Source FEC Payload ID encoding format for m = 8 (default). 559 0 1 2 3 560 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 561 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 562 | Source Block Nb (16 bits) | Enc. Symbol ID (16 bits) | 563 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 564 | Source Block Length (k) | 565 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 567 Figure 6: Source FEC Payload ID encoding format for m = 16. 569 The format of the Source FEC Payload ID for m = 8 and m = 16 are 570 illustrated in Figure 5 and Figure 6 respectively. 572 5.1.3. Repair FEC Payload ID 574 A FEC repair packet MUST contain a Repair FEC Payload ID that is 575 prepended to the repair symbol(s) as illustrated in Figure 7. There 576 MUST be a single repair symbol per FEC repair packet. 578 +--------------------------------+ 579 | IP Header | 580 +--------------------------------+ 581 | Transport Header | 582 +--------------------------------+ 583 | Repair FEC Payload ID | 584 +--------------------------------+ 585 | Repair Symbol | 586 +--------------------------------+ 588 Figure 7: Structure of a FEC Repair Packet with the Repair FEC 589 Payload ID. 591 More precisely, the Repair FEC Payload ID is composed of the Source 592 Block Number, the Encoding Symbol ID, and the Source Block Length. 593 The length of the first two fields depends on the m parameter 594 (transmitted separately in the FFCI, Section 5.1.1.2): 596 Source Block Number (SBN) (32-m bit field): this field identifies 597 the source block to which the FEC repair packet belongs. 598 Encoding Symbol ID (ESI) (m bit field) this field identifies the 599 repair symbol contained in this FEC repair packet. This value is 600 such that k <= ESI <= n - 1 for repair symbols. 601 Source Block Length (k) (16 bit field): this field provides the 602 number of source symbols for this source block, i.e., the k 603 parameter. If 16 bits are too much when m <= 8, it is needed when 604 8 < m <= 16. Therefore we provide a single common format 605 regardless of m. 607 0 1 2 3 608 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 609 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 610 | Source Block Number (24 bits) | Enc. Symb. ID | 611 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 612 | Source Block Length (k) | 613 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 615 Figure 8: Repair FEC Payload ID encoding format for m = 8 (default). 617 0 1 2 3 618 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 619 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 620 | Source Block Nb (16 bits) | Enc. Symbol ID (16 bits) | 621 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 622 | Source Block Length (k) | 623 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 625 Figure 9: Repair FEC Payload ID encoding format for m = 16. 627 The format of the Repair FEC Payload ID for m = 8 and m = 16 are 628 illustrated in Figure 8 and Figure 9 respectively. 630 5.2. Procedures 632 The following procedures apply: 633 o The source block creation procedures are specified in Section 4.3. 634 o The SBN value is incremented for each new source block, starting 635 at 0 for the first block of the ADU flow. Wrapping to zero will 636 happen for long sessions, after value 2^^(32-m) - 1. 637 o The ESI of encoding symbols is managed sequentially, starting at 0 638 for the first symbol. The first k values (0 <= ESI <= k - 1) 639 identify source symbols, whereas the last n-k values (k <= ESI <= 640 n - 1) identify repair symbols. 642 o The FEC repair packet creation procedures are specified in 643 Section 5.1.3. 645 5.3. FEC Code Specification 647 The present document inherits from [RFC5510] the specification of the 648 core Reed-Solomon codes based on Vandermonde matrices for a packet 649 transmission channel. 651 6. Security Considerations 653 The FEC Framework document [RFC6363] provides a comprehensive 654 analysis of security considerations applicable to FEC schemes. 655 Therefore the present section follows the security considerations 656 section of [RFC6363] and only discusses topics that are specific to 657 the use of Reed-Solomon codes. 659 6.1. Attacks Against the Data Flow 661 6.1.1. Access to Confidential Content 663 The Reed-Solomon FEC Scheme specified in this document does not 664 change the recommendations of [RFC6363]. To summarize, if 665 confidentiality is a concern, it is RECOMMENDED that one of the 666 solutions mentioned in [RFC6363] is used, with special considerations 667 to the way this solution is applied (e.g., before versus after FEC 668 protection, and within the end-system versus in a middlebox), to the 669 operational constraints (e.g., performing FEC decoding in a protected 670 environment may be complicated or even impossible) and to the threat 671 model. 673 6.1.2. Content Corruption 675 The Reed-Solomon FEC Scheme specified in this document does not 676 change the recommendations of [RFC6363]. To summarize, it is 677 RECOMMENDED that one of the solutions mentioned in [RFC6363] is used 678 on both the FEC Source and Repair Packets. 680 6.2. Attacks Against the FEC Parameters 682 The FEC Scheme specified in this document defines parameters that can 683 be the basis of several attacks. More specifically, the following 684 parameters of the FFCI may be modified by an attacker 685 (Section 5.1.1.2): 686 o FEC Encoding ID: changing this parameter leads the receiver to 687 consider a different FEC Scheme, which enables an attacker to 688 create a Denial of Service (DoS). 690 o Encoding symbol length (E): setting this E parameter to a value 691 smaller than the valid one enables an attacker to create a DoS 692 since the repair symbols and certain source symbols will be larger 693 than E, which is an incoherency for the receiver. Setting this E 694 parameter to a value larger than the valid one has similar impacts 695 when S=1 since the received repair symbol size will be smaller 696 than expected. On the opposite it will not lead to any 697 incoherency when S=0 since the actual symbol length value for the 698 block is determined by the size of any received repair symbol, as 699 long as this value is smaller than E. However setting this E 700 parameter to a larger value may have impacts on receivers that 701 pre-allocate memory space in advance to store incoming symbols. 702 o Strict (S) flag: flipping this S flag from 0 to 1 (i.e., E is now 703 considered as a strict value) enables an attacker to mislead the 704 receiver if the actual symbol size varies over different source 705 blocks. Flipping this S flag from 1 to 0 has no major 706 consequences unless the receiver requires to have a fixed E value 707 (e.g., because the receiver pre-allocates memory space). 708 o m parameter: changing this parameter triggers a DoS since the 709 receiver and sender will consider different codes, and the 710 receiver will interpret the Explicit Source FEC Payload ID and 711 Repair FEC Payload ID differently. Additionally, by increasing 712 this m parameter to a larger value (typically m=16 rather than 8, 713 when both values are possible in the target use-case) will create 714 additional processing load at a receiver if decoding is attempted. 716 It is therefore RECOMMENDED that security measures are taken to 717 guarantee the FFCI integrity, as specified in [RFC6363]. How to 718 achieve this depends on the way the FFCI is communicated from the 719 sender to the receiver, which is not specified in this document. 721 Similarly, attacks are possible against the Explicit Source FEC 722 Payload ID and Repair FEC Payload ID: by modifying the Source Block 723 Number (SBN), or the Encoding Symbol ID (ESI), or the Source Block 724 Length (k), an attacker can easily corrupt the block identified by 725 the SBN. Other consequences, that are use-case and/or CDP dependant, 726 may also happen. It is therefore RECOMMENDED that security measures 727 are taken to guarantee the FEC Source and Repair Packets as stated in 728 [RFC6363]. 730 6.3. When Several Source Flows are to be Protected Together 732 The Reed-Solomon FEC Scheme specified in this document does not 733 change the recommendations of [RFC6363]. 735 6.4. Baseline Secure FEC Framework Operation 737 The Reed-Solomon FEC Scheme specified in this document does not 738 change the recommendations of [RFC6363] concerning the use of the 739 IPsec/ESP security protocol as a mandatory to implement (but not 740 mandatory to use) security scheme. This is well suited to situations 741 where the only insecure domain is the one over which the FEC 742 Framework operates. 744 7. Operations and Management Considerations 746 The FEC Framework document [RFC6363] provides a comprehensive 747 analysis of operations and management considerations applicable to 748 FEC schemes. Therefore the present section only discusses topics 749 that are specific to the use of Reed-Solomon codes as specified in 750 this document. 752 7.1. Operational Recommendations: Finite Field Size (m) 754 The present document requires that m, the length of the elements in 755 the finite field, in bits, is such that 2 <= m <= 16. However all 756 possibilities are not equally interesting from a practical point of 757 view. It is expected that m=8, the default value, will be mostly 758 used since it offers the possibility to have small to medium sized 759 source blocks and/or a significant number of repair symbols (i.e., k 760 < n <= 255). Additionally, elements in the finite field are 8 bits 761 long which makes read/write memory operations aligned on bytes during 762 encoding and decoding. 764 An alternative when it is known that only very small source blocks 765 will be used is m=4 (i.e., k < n <= 15). Elements in the finite 766 field are 4 bits long, so if two elements are accessed at a time, 767 read/write memory operations are aligned on bytes during encoding and 768 decoding. 770 An alternative when very large source blocks are needed is m=16 771 (i.e., k < n <= 65535). However this choice has significant impacts 772 on the processing load. For instance using pre-calculated tables to 773 speedup operations over the finite field (as done with smaller finite 774 fields) may require a prohibitive amount of memory to be used on 775 embedded platforms. Alternative lightweight solutions (e.g., 776 [RFC5170]) MAY be preferred in situations where the processing load 777 is an issue [Matsuzono10]. 779 Since several values for the m parameter are possible, the use-case 780 SHOULD define which value(s) need(s) to be supported. In situations 781 where this is not specified, the default m=8 value SHOULD be 782 supported and used. 784 8. IANA Considerations 786 Values of FEC Encoding IDs are subject to IANA registration. 787 [RFC6363] defines general guidelines on IANA considerations. In 788 particular it defines a registry called FEC Framework (FECFRAME) FEC 789 Encoding IDs whose values are granted on an IETF Consensus basis. 791 This document registers one value in the FEC Framework (FECFRAME) FEC 792 Encoding IDs registry as follows: 793 o XXX refers to the Simple Reed-Solomon [RFC5510] FEC Scheme over 794 GF(2^^m) for Arbitrary Packet Flows. 796 9. Acknowledgments 798 The authors want to thank Hitoshi Asaeda and Ali Begen for their 799 valuable comments. 801 10. References 803 10.1. Normative References 805 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 806 Requirement Levels", RFC 2119. 808 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 809 Correction (FEC) Building Block", RFC 5052, August 2007. 811 [RFC5510] Lacan, J., Roca, V., Peltotalo, J., and S. Peltotalo, 812 "Reed-Solomon Forward Error Correction (FEC) Schemes", 813 RFC 5510, April 2009. 815 [RFC6363] Watson, M., Begen, A., and V. Roca, "Forward Error 816 Correction (FEC) Framework", RFC 6363, September 2011. 818 [RFC6364] Begen, A., "Session Description Protocol Elements for the 819 Forward Error Correction (FEC) Framework", RFC 6364, 820 October 2011. 822 10.2. Informative References 824 [RS-codec] 825 Rizzo, L., "Reed-Solomon FEC codec (revised version of 826 July 2nd, 1998), available at 827 http://info.iet.unipi.it/~luigi/vdm98/vdm980702.tgz, 828 mirrored at http://planete-bcast.inrialpes.fr/ and 829 http://openfec.org/", July 1998. 831 [Rizzo97] Rizzo, L., "Effective Erasure Codes for Reliable Computer 832 Communication Protocols", ACM SIGCOMM Computer 833 Communication Review Vol.27, No.2, pp.24-36, April 1997. 835 [Matsuzono10] 836 Matsuzono, K., Detchart, J., Cunche, M., Roca, V., and H. 837 Asaeda, "Performance Analysis of a High-Performance Real- 838 Time Application with Several AL-FEC Schemes", 35th Annual 839 IEEE Conference on Local Computer Networks (LCN 2010), 840 October 2010. 842 [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity 843 Check (LDPC) Forward Error Correction", RFC 5170, 844 June 2008. 846 [RFC5053] Luby, M., Shokrollahi, A., Watson, M., and T. Stockhammer, 847 "Raptor Forward Error Correction Scheme", RFC 5053, 848 June 2007. 850 [RFC5775] Luby, M., Watson, M., and L. Vicisano, "Asynchronous 851 Layered Coding (ALC) Protocol Instantiation", RFC 5775, 852 April 2010. 854 [RFC5740] Adamson, B., Bormann, C., Handley, M., and J. Macker, 855 "Negative-acknowledgment (NACK)-Oriented Reliable 856 Multicast (NORM) Protocol", RFC 5740, November 2009. 858 Authors' Addresses 860 Vincent Roca 861 INRIA 862 655, av. de l'Europe 863 Inovallee; Montbonnot 864 ST ISMIER cedex 38334 865 France 867 Email: vincent.roca@inria.fr 868 URI: http://planete.inrialpes.fr/people/roca/ 869 Mathieu Cunche 870 NICTA 871 Australia 873 Email: mathieu.cunche@nicta.com.au 874 URI: http://mathieu.cunche.free.fr/ 876 Jerome Lacan 877 ISAE/LAAS-CNRS 878 1, place Emile Blouin 879 Toulouse 31056 880 France 882 Email: jerome.lacan@isae.fr 883 URI: http://dmi.ensica.fr/auteur.php3?id_auteur=5 885 Amine Bouabdallah 886 ISAE/LAAS-CNRS 887 1, place Emile Blouin 888 Toulouse 31056 889 France 891 Email: Amine.Bouabdallah@isae.fr 892 URI: http://dmi.ensica.fr/ 894 Kazuhisa Matsuzono 895 Keio University 896 Graduate School of Media and Governance 897 5322 Endo 898 Fujisawa, Kanagawa 252-8520 899 Japan 901 Email: kazuhisa@sfc.wide.ad.jp