idnits 2.17.1 draft-ietf-rmt-bb-fec-basic-schemes-revised-06.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 17. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 851. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 862. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 869. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 875. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- == The 'Obsoletes: ' line in the draft header should list only the _numbers_ of the RFCs which will be obsoleted by this document (if approved); it should not include the word 'RFC' in the list. -- The abstract seems to indicate that this document obsoletes RFC3695, but the header doesn't have an 'Obsoletes:' line to match this. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust Copyright Line does not match the current year == Line 495 has weird spacing: '...rmation the ...' -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 31, 2008) is 5654 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) == Missing Reference: 'Y' is mentioned on line 374, but not defined -- Obsolete informational reference (is this intentional?): RFC 3452 (Obsoleted by RFC 5052, RFC 5445) -- Obsolete informational reference (is this intentional?): RFC 3695 (Obsoleted by RFC 5445) Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Reliable Multicast Transport M. Watson 3 Internet-Draft Digital Fountain 4 Obsoletes: rfc3695 October 31, 2008 5 (if approved) 6 Intended status: Standards Track 7 Expires: May 4, 2009 9 Basic Forward Error Correction (FEC) Schemes 10 draft-ietf-rmt-bb-fec-basic-schemes-revised-06 12 Status of this Memo 14 By submitting this Internet-Draft, each author represents that any 15 applicable patent or other IPR claims of which he or she is aware 16 have been or will be disclosed, and any of which he or she becomes 17 aware will be disclosed, in accordance with Section 6 of BCP 79. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as Internet- 22 Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at 30 http://www.ietf.org/ietf/1id-abstracts.txt. 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html. 35 This Internet-Draft will expire on May 4, 2009. 37 Abstract 39 This document provides Forward Error Correction (FEC) Scheme 40 specifications according to the RMT FEC Building Block for the 41 Compact No-Code FEC Scheme, the Small Block, Large Block and 42 Expandable FEC Scheme, the Small Block Systematic FEC Scheme and the 43 Compact FEC Scheme. This document obsoletes RFC3695 and assumes 44 responsibility for the FEC Schemes defined in RFC3452. 46 Table of Contents 48 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 49 2. Requirements notation . . . . . . . . . . . . . . . . . . . . 5 50 3. Compact No-Code FEC Scheme . . . . . . . . . . . . . . . . . . 6 51 3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 6 52 3.2. Formats and Codes . . . . . . . . . . . . . . . . . . . . 6 53 3.2.1. FEC Payload ID(s) . . . . . . . . . . . . . . . . . . 6 54 3.2.2. FEC Object Transmission Information . . . . . . . . . 7 55 3.3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . 9 56 3.4. FEC code specification . . . . . . . . . . . . . . . . . . 9 57 3.4.1. Source Block Logistics . . . . . . . . . . . . . . . . 9 58 3.4.2. Sending and Receiving a Source Block . . . . . . . . . 10 59 4. Small Block, Large Block and Expandable FEC Scheme . . . . . . 12 60 4.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 12 61 4.2. Formats and Codes . . . . . . . . . . . . . . . . . . . . 12 62 4.2.1. FEC Payload ID(s) . . . . . . . . . . . . . . . . . . 12 63 4.2.2. FEC Object Transmission Information . . . . . . . . . 12 64 4.3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . 14 65 4.4. FEC Code Specification . . . . . . . . . . . . . . . . . . 14 66 5. Small Block Systematic FEC Scheme . . . . . . . . . . . . . . 15 67 5.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 15 68 5.2. Formats and Codes . . . . . . . . . . . . . . . . . . . . 15 69 5.2.1. FEC Payload ID(s) . . . . . . . . . . . . . . . . . . 15 70 5.2.2. FEC Object Transmission Information . . . . . . . . . 16 71 5.3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . 17 72 5.4. FEC Code Specification . . . . . . . . . . . . . . . . . . 18 73 6. Compact FEC Scheme . . . . . . . . . . . . . . . . . . . . . . 19 74 6.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 19 75 6.2. Formats and Codes . . . . . . . . . . . . . . . . . . . . 19 76 6.2.1. FEC Payload ID(s) . . . . . . . . . . . . . . . . . . 19 77 6.2.2. FEC Object Transmission Information . . . . . . . . . 19 78 6.3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . 19 79 6.4. FEC code specification . . . . . . . . . . . . . . . . . . 19 80 7. Security Considerations . . . . . . . . . . . . . . . . . . . 20 81 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 21 82 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 83 10. Changes from schemes defined in RFC3452 and RFC3695 . . . . . 24 84 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 25 85 11.1. Normative References . . . . . . . . . . . . . . . . . . . 25 86 11.2. Informative References . . . . . . . . . . . . . . . . . . 25 87 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 26 88 Intellectual Property and Copyright Statements . . . . . . . . . . 27 90 1. Introduction 92 The document specifies the following FEC Schemes according to the 93 specification requirements of the FEC Building Block [RFC5052]: 95 o Compact No-Code FEC Scheme 97 o Small Block, Large Block and Expandable FEC Scheme 99 o Small Block Systematic FEC Scheme 101 o Compact FEC Scheme 103 This document inherits the context, language, declarations and 104 restrictions of the FEC building block [RFC5052]. This document also 105 uses the terminology of the companion document [RFC3453] which 106 describes the use of FEC codes within the context of reliable IP 107 multicast transport and provides an introduction to some commonly 108 used FEC codes. 110 Building blocks are defined in [RFC3048]. This document follows the 111 general guidelines provided in [RFC3269]. 113 [RFC3452] and [RFC3695] contained a previous versions of the FEC 114 Schemes defined in this specification. These RFCs were published in 115 the "Experimental" category. It was the stated intent of the RMT 116 working group to re-submit these specifications as an IETF Proposed 117 Standard in due course. This document obsoletes [RFC3695]. 118 [RFC3452] has already been obsoleted by [RFC5052] and this document 119 assumes responsibility for aspects of [RFC3452] that were not 120 included in [RFC5052]. 122 This Proposed Standard specification is thus based on and backwards 123 compatible with the FEC Schemes defined in [RFC3452] and [RFC3695] 124 updated according to accumulated experience and growing protocol 125 maturity since their original publication. Said experience applies 126 both to this specification itself and to congestion control 127 strategies related to the use of this specification. 129 The differences between the FEC Scheme specifications in [RFC3452] 130 and [RFC3695] and this document are listed in Section 10. 132 Integer fields specified in this document are all encoded in network 133 byte order. 135 2. Requirements notation 137 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 138 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 139 document are to be interpreted as described in [RFC2119]. 141 3. Compact No-Code FEC Scheme 143 3.1. Introduction 145 The Compact No-code FEC Scheme is a Fully-Specified FEC Scheme. The 146 scheme requires no FEC coding and is specified primarily to allow 147 simple interoperability testing between different implementations of 148 protocol instantiations that use the FEC building block. 150 3.2. Formats and Codes 152 3.2.1. FEC Payload ID(s) 154 The FEC Payload ID for the Compact No-Code FEC Scheme is composed of 155 a Source Block Number and an Encoding Symbol ID as shown in Figure 1. 157 0 1 2 3 158 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 159 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 160 | Source Block Number | Encoding Symbol ID | 161 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 163 Figure 1: FEC Payload ID format for Compact No-Code FEC Scheme 165 The Source Block Number (SBN) is a 16-bit unsigned interger that is 166 used to identify from which source block of the object the encoding 167 symbol in the payload of the packet is generated. There are two 168 possible modes: In the unique SBN mode each source block within the 169 object has a unique Source Block Number associated with it, and in 170 the non-unique SBN mode the same Source Block Number may be used for 171 more than one source block within the object. Which mode is being 172 used for an object is outside the scope of this document and MUST be 173 communicated, either explicitly or implicitly, out-of-band to 174 receivers. 176 If the unique SBN mode is used then successive Source Block Numbers 177 are associated with consecutive source blocks of the object starting 178 with Source Block Number 0 for the first source block of the object. 179 In this case, there are at most 2^^16 source blocks in the object. 181 If the non-unique SBN mode is used then the mapping from source 182 blocks to Source Block Numbers MUST be communicated out-of-band to 183 receivers, and how this is done is outside the scope of this 184 document. This mapping could be implicit, for example determined by 185 the transmission order of the source blocks. In non-unique SBN mode, 186 packets for two different source blocks mapped to the same Source 187 Block Number SHOULD NOT be sent within an interval of time that is 188 shorter than the transport time of a source block. The transport 189 time of a source block includes the amount of time needed to process 190 the source block at the sender transport layer, the network transit 191 time for packets, and the amount of time needed to process the source 192 block at the receiver transport. This allows the receiver to clearly 193 decide which packets belong to which source block. 195 The Encoding Symbol ID is a 16-bit unsigned integer that identifies 196 which specific encoding symbol generated from the source block is 197 carried in the packet payload. The exact details of the 198 correspondence between Encoding Symbol IDs and the encoding symbols 199 in the packet payload are specified in Section 3.4. 201 3.2.2. FEC Object Transmission Information 203 3.2.2.1. Mandatory 205 The mandatory FEC Object Transmission Information element for the 206 Compact No-Code FEC Scheme is: 208 o FEC Encoding ID: zero (0) 210 3.2.2.2. Common 212 The common FEC Object Transmission Information elements and their 213 value ranges for the Compact No-code FEC Scheme are: 215 Transfer-Length: a non-negative integer less than 2^^48. 217 Encoding-Symbol-Length: a non-negative integer less than 2^^16. 219 Maximum-Source-Block-Length: a non-negative integer less than 2^^32. 221 Note that the semantics for the above elements are defined in 222 [RFC5052] and are not duplicated here. 224 The encoded Common FEC Object Transmission information is defined in 225 Figure 2. 227 0 1 2 3 228 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 229 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 230 | Transfer Length | 231 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 232 | | Reserved | 233 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 234 | Encoding Symbol Length | Max. Source Block Length (MSB)| 235 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 236 | Max. Source Block Length (LSB)| 237 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 239 Figure 2: Encoded Common FEC OTI for Compact No-Code FEC Scheme 241 The Transfer Length, Encoding Symbol Length and Maximum Source Block 242 length are encoded as unsigned integers, of length 48 bits, 16 bits 243 and 32 bits respectivly. 245 All Encoding Symbols of a transport object MUST have length equal to 246 the length specified in the Encoding Symbol Length element, with the 247 optional exception of the last source symbol of the last source block 248 (so that redundant padding is not mandatory in this last symbol). 249 This last source symbol MUST be logically padded out with zeroes when 250 another Encoding Symbol is computed based on this source symbol to 251 ensure the same interpretation of this Encoding Symbol value by the 252 sender and receiver. However, this padding does not actually need to 253 be sent with the data of the last source symbol. 255 The "Reserved" field in the Encoded FEC Object Transmission 256 Information MUST be set to zero by senders and its value MUST be 257 ignored by receivers. 259 Note: this FEC Scheme was first defined in [RFC3695] which did not 260 require that the Encoding Symbol Length should be the same for 261 every source block. This document introduces a general 262 requirement that the Encoding Symbol Length be the same across 263 source blocks. Since no protocols were defined which support 264 variation in the Encoding Symbol Length between source blocks this 265 can be done without introducing backwards compatibility issues. 267 3.2.2.3. Scheme-Specific 269 No Scheme-Specific FEC Object Transmission Information elements are 270 defined by this FEC Scheme. 272 3.3. Procedures 274 The algorithm defined in Section 9.1. of [RFC5052] MUST be used to 275 partition the file into source blocks. 277 3.4. FEC code specification 279 The Compact No-Code FEC scheme does not require FEC encoding or 280 decoding. Instead, each encoding symbol consists of consecutive 281 bytes of a source block of the object. 283 The following two subsections describe the details of how the Compact 284 No-Code FEC scheme operates for each source block of an object. 286 3.4.1. Source Block Logistics 288 Let X > 0 be the length of a source block in bytes. Let L > 0 be the 289 length of the encoding symbol contained in the payload of each 290 packet. The value of X and L are part of the FEC Object Transmission 291 Information, and how this information is communicated to a receiver 292 is outside the scope of this document. 294 For a given source block X bytes in length with Source Block Number 295 I, let N = X/L rounded up to the nearest integer. The encoding 296 symbol carried in the payload of a packet consists of a consecutive 297 portion of the source block. The source block is logically 298 partitioned into N encoding symbols, each L bytes in length, and the 299 corresponding Encoding Symbol IDs range from 0 through N-1 starting 300 at the beginning of the source block and proceeding to the end. 301 Thus, the encoding symbol with Encoding Symbol ID Y consists of bytes 302 L*Y through L*(Y+1)-1 of the source block, where the bytes of the 303 source block are numbered from 0 through X-1. If X/L is not integral 304 then the last encoding symbol with Encoding Symbol ID = N-1 consists 305 of bytes L*(N-1) through the last byte X-1 of the source block, and 306 the remaining L*N - X bytes of the encoding symbol can by padded out 307 with zeroes. 309 As an example, suppose that the source block length X = 20,400 and 310 encoding symbol length L = 1,000. The encoding symbol with Encoding 311 Symbol ID = 10 contains bytes 10,000 through 10,999 of the source 312 block, and the encoding symbol with Encoding Symbol ID = 20 contains 313 bytes 20,000 through the last byte 20,399 of the source block and the 314 remaining 600 bytes of the encoding symbol can be padded with zeroes. 316 There are no restrictions beyond the rules stated above on how a 317 sender generates encoding symbols to send from a source block. 318 However, it is recommended that an implementor refer to the companion 319 document [RFC3452] for general advice. 321 In the next subsection a procedure is recommended for sending and 322 receiving source blocks. 324 3.4.2. Sending and Receiving a Source Block 326 The following carousel procedure is RECOMMENDED for a sender to 327 generate packets containing FEC Payload IDs and corresponding 328 encoding symbols for a source block with Source Block Number I. Set 329 the length in bytes of an encoding symbol to a fixed value L which is 330 reasonable for a packet payload (e.g., ensure that the total packet 331 size does not exceed the MTU) and that is smaller than the source 332 block length X, e.g., L = 1,000 for X >= 1,000. Initialize Y to a 333 value randomly chosen in the interval [0..N-1]. Repeat the following 334 for each packet of the source block to be sent. 336 o If Y <= N-1 then generate the encoding symbol Y. 338 o Within the FEC Payload ID, set the Source Block Length to X, set 339 the Source Block Number = I, set the Encoding Symbol ID = Y, place 340 the FEC Payload ID and the encoding symbol into the packet to 341 send. 343 o In preparation for the generation of the next packet: if Y < N-1 344 then increment Y by one else if Y = N-1 then reset Y to zero. 346 The following procedure is RECOMMENDED for a receiver to recover the 347 source block based on receiving packets for the source block from a 348 sender that is using the carousel procedure described above. The 349 receiver can determine from which source block a received packet was 350 generated by the Source Block Number carried in the FEC Payload ID. 351 Upon receipt of the first FEC Payload ID for a source block, the 352 receiver uses the Source Block Length and Encoding Symbol Length 353 received out-of-band as part of the FEC Object Transmission 354 Information to determine the length X in bytes of the source block 355 and length L in bytes of each encoding symbol. The reciever 356 allocates space for the X bytes that the source block requires. The 357 receiver also computes the length of the encoding symbol in the 358 payload of the packet by subtracting the packet header length from 359 the total length of the received packet. The receiver checks that 360 this symbol length is equal to L, except in the case that this is the 361 last symbol of the source block in which case the symbol length in 362 the packet may be less than L. After calculating N = X/L rounded up 363 to the nearest integer, the receiver allocates a boolean array 364 RECEIVED[0..N-1] with all N entries initialized to false to track 365 received encoding symbols. The receiver keeps receiving packets for 366 the source block as long as there is at least one entry in RECEIVED 367 still set to false or until the application decides to give up on 368 this source block and move on to other source blocks. For each 369 received packet for the source block (including the first packet) the 370 steps to be taken to help recover the source block are as follows. 371 Let Y be the value of the Encoding Symbol ID within the FEC Payload 372 ID of the packet. If Y <= N-1 then the receiver copies the encoding 373 symbol into the appropriate place within the space reserved for the 374 source block and sets RECEIVED[Y] = true. If all N entries of 375 RECEIVED are true then the receiver has recovered the entire source 376 block. 378 4. Small Block, Large Block and Expandable FEC Scheme 380 4.1. Introduction 382 This section defines an Under-Specified FEC Scheme for Small Block 383 FEC codes, Large Block FEC codes and Expandable FEC codes as 384 described in [RFC3453]. 386 4.2. Formats and Codes 388 4.2.1. FEC Payload ID(s) 390 The FEC Payload ID is composed of a Source Block Number and an 391 Encoding Symbol ID structured as shown in Figure 3. 393 0 1 2 3 394 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 395 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 396 | Source Block Number | 397 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 398 | Encoding Symbol ID | 399 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 401 Figure 3: FEC Payload ID format for Small Block, Large Block and 402 Expandable FEC Codes 404 The Source Block Number is a 32-bit unsigned integer that identifies 405 from which source block of the object the encoding symbol(s) in the 406 payload are generated. These blocks are numbered consecutively from 407 0 to N-1, where N is the number of source blocks in the object. 409 The Encoding Symbol ID is a 32-bit unsigned integer that identifies 410 which specific encoding symbol(s) generated from the source block are 411 carried in the packet payload. The exact details of the 412 correspondence between Encoding Symbol IDs and the encoding symbol(s) 413 in the packet payload are dependent on the particular FEC Scheme 414 instance used as identified by the FEC Encoding ID and by the FEC 415 Instance ID, and these details may be proprietary. 417 4.2.2. FEC Object Transmission Information 419 4.2.2.1. Mandatory 421 The mandatory FEC Object Transmission Information element for the 422 Small Block, Large Block and Expandable FEC Scheme are: 424 o FEC Encoding ID: 128 426 4.2.2.2. Common 428 The common FEC Object Transmission Information elements and their 429 value ranges for the Small Block, Large Block and Expandable FEC 430 Scheme are: 432 FEC Instance ID: a non-negative integer less than 2^^16. 434 Transfer-Length: a non-negative integer less than 2^^48. 436 Encoding-Symbol-Length: a non-negative integer less than 2^^16. 438 Maximum-Source-Block-Length: a non-negative integer less than 2^^32. 440 Note that the semantics for the above elements are defined in 441 [RFC5052] and are not duplicated here. 443 The encoded Common FEC Object Transmission information is defined in 444 Figure 4. 446 0 1 2 3 447 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 448 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 449 | Transfer Length | 450 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 451 | | FEC Instance ID | 452 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 453 | Encoding Symbol Length | Max. Source Block Length (MSB)| 454 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 455 | Max. Source Block Length (LSB)| 456 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 458 Figure 4: Encoded Common FEC OTI for Small Block, Large Block and 459 Expandable FEC Scheme 461 The Transfer Length (48 bits), FEC Instance ID (16 bits), Encoding 462 Symbol Length (16 bits) and Maximum Source Block Length (32 bits) are 463 encoded as unsigned integers. 465 4.2.2.3. Scheme-Specific 467 The Scheme-specific FEC Object Transmission Information field for the 468 Small block, Large Block and Expandable FEC Scheme provides for the 469 possibility of Instance-specific FEC Object Transmission Information. 470 The format of the Scheme-Specific FEC Object Transmission information 471 for this FEC Scheme is defined in Figure 5 472 0 1 2 3 473 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 474 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 475 | Length | Instance-specific FEC OTI | 476 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 477 | | 478 | Instance-specific FEC OTI contd. | 479 | | 480 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 482 Figure 5: Encoded Scheme-specific FEC OTI for Small Block, Large 483 Block and Expandable FEC Scheme 485 The Scheme-specific FEC Object Transmission Information field 486 contains the following sub-fields: 488 Length (1 octet) an unsigned integer that specifies the length of 489 the Scheme-specific FEC OTI in four-octet words (including this 490 length field), except that the value zero indicates that no 491 Instance-specific FEC OTI information is provided. When the 492 Length is zero, three padding bytes containing value zero SHALL 493 follow the Length field to maintain 4-octet alignment. 495 Instance-specific FEC OTI Information the contents of this field 496 are FEC Scheme Instance-specific 498 Note that in the case of a Content Delivery protocol which supports 499 external signalling of the total FEC Object Transmission Information 500 length, then the Scheme-Specific FEC OTI field defined here is 501 optional. Otherwise, this field MUST be included. 503 4.3. Procedures 505 The algorithm defined in Section 9.1. of [RFC5052] MUST be used to 506 partition the file into source blocks. 508 4.4. FEC Code Specification 510 The FEC code specification and the correspondance of Encoding Symbols 511 IDs to encoding symbols are defined by specific instances of this 512 scheme and so are out of scope of this document. 514 5. Small Block Systematic FEC Scheme 516 5.1. Introduction 518 This section defines an Under-Specified FEC Scheme for Small Block 519 Systematic FEC codes as described in [RFC3453]. For Small Block 520 Systematic FEC codes, each source block is of length at most 65535 521 source symbols. 523 Although these codes can generally be accommodated by the FEC 524 Encoding ID described in Section 4, a specific FEC Encoding ID is 525 defined for Small Block Systematic FEC codes to allow more 526 flexibility and to retain header compactness. The small source block 527 length and small expansion factor that often characterize systematic 528 codes may require the data source to frequently change the source 529 block length. To allow the dynamic variation of the source block 530 length and to communicate it to the receivers with low overhead, the 531 block length is included in the FEC Payload ID. 533 5.2. Formats and Codes 535 5.2.1. FEC Payload ID(s) 537 The FEC Payload ID is composed of the Source Block Number, Source 538 Block Length and the Encoding Symbol ID structured as shown in 539 Figure 6. 541 0 1 2 3 542 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 543 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 544 | Source Block Number | 545 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 546 | Source Block Length | Encoding Symbol ID | 547 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 549 Figure 6: FEC Payload ID format for Small Block Systematic FEC scheme 551 The Source Block Number is a 32-bit unsigned integer that identifies 552 from which source block of the object the encoding symbol(s) in the 553 payload are generated. These blocks are numbered consecutively from 554 0 to N-1, where N is the number of source blocks in the object. 556 The Source Block Length is a 16-bit unsigned integer that specifies 557 the length in units of source symbols of the source block identified 558 by the Source Block Number. 560 The Encoding Symbol ID is a 16-bit unsigned integer that identifies 561 which specific encoding symbol(s) generated from the source block are 562 carried in the packet payload. Each encoding symbol is either an 563 original source symbol or a redundant symbol generated by the 564 encoder. The exact details of the correspondence between Encoding 565 Symbol IDs and the encoding symbol(s) in the packet payload are 566 dependent on the particular FEC scheme instance used as identified by 567 the FEC Instance ID, and these details may be proprietary. 569 5.2.2. FEC Object Transmission Information 571 5.2.2.1. Mandatory 573 The mandatory FEC Object Transmission Information element for the 574 Small Block Systematic FEC Scheme is: 576 o FEC Encoding ID: 129 578 5.2.2.2. Common 580 The common FEC Object Transmission Information elements and their 581 value ranges for the Small Block Systematic FEC Scheme are: 583 FEC Instance ID: a non-negative integer less than 2^^16. 585 Transfer-Length: a non-negative integer less than 2^^48. 587 Encoding-Symbol-Length: a non-negative integer less than 2^^16. 589 Maximum-Source-Block-Length: a non-negative integer less than 2^^16. 591 Max-Number-of-Encoding-Symbols: a non-negative integer less than 592 2^^16 594 Note that the semantics for the above elements are defined in 595 [RFC5052] and are not duplicated here. 597 The encoded Common FEC Object Transmission information is defined in 598 Figure 7. 600 0 1 2 3 601 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 602 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 603 | Transfer Length | 604 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 605 | | FEC Instance ID | 606 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 607 | Encoding Symbol Length | Maximum Source Block Length | 608 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 609 | Max. Num. of Encoding Symbols | 610 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 612 Figure 7: FEC OTI format for Small Block Systematic FEC Scheme 614 The Transfer Length (48 bits), FEC Instance ID (16 bits), Encoding 615 Symbol Length (16 bits), Maximum Source Block Length (16 bits) and 616 Maximum Number of Encoding Symbols (16 bits) are encoded as unsigned 617 integers. 619 All Encoding Symbols of a transport object MUST have length equal to 620 the length specified in the Encoding Symbol Length field, with the 621 optional exception of the last source symbol of the last source block 622 (so that redundant padding is not mandatory in this last symbol). 623 This last source symbol MUST be logically padded out with zeroes when 624 another Encoding Symbol is computed based on this source symbol to 625 ensure the same interpretation of this Encoding Symbol value by the 626 sender and receiver. However, this padding need not be actually sent 627 with the data of the last source symbol. 629 Note: this FEC Scheme was first defined in [RFC3452] which did not 630 require that the Encoding Symbol Length should be the same for 631 every source block. However, no protocols have been defined which 632 support variation in the Encoding Symbol Length between source 633 blocks and thus introduction of a general requirement that the 634 Encoding Symbol Length be the same across source blocks (as 635 defined here) should not cause backwards compatibility issues and 636 will aid interoperability. 638 5.2.2.3. Scheme-Specific 640 The Scheme-Specific FEC Object Transmission Information format 641 defined in Section 4.2.2.3 SHALL be used. 643 5.3. Procedures 645 The algorithm defined in Section 9.1. of [RFC5052] MAY be used to 646 partition the file into source blocks. Otherwise the FEC Scheme 647 instance MUST specify the algorithm that is used. 649 5.4. FEC Code Specification 651 The FEC code specification and the correspondance of Encoding Symbols 652 IDs to encoding symbols are defined by specific instances of this 653 scheme and so are out of scope of this document. 655 6. Compact FEC Scheme 657 6.1. Introduction 659 The Compact FEC Scheme is an Under-Specified FEC scheme. This FEC 660 scheme is similar in spirit to the Compact No-Code FEC scheme, except 661 that a non-trivial FEC encoding (that is Under-Specified) may be used 662 to generate encoding symbol(s) placed in the payload of each packet 663 and a corresponding FEC decoder may be used to produce the source 664 block from received packets. 666 6.2. Formats and Codes 668 6.2.1. FEC Payload ID(s) 670 The FEC Payload ID format defined in Section 3.2.1 SHALL be used. 672 6.2.2. FEC Object Transmission Information 674 6.2.2.1. Mandatory 676 The mandatory FEC Object Transmission Information element for the 677 Compact No-Code FEC Scheme is: 679 o FEC Encoding ID: 130 681 6.2.2.2. Common 683 The common FEC Object Transmission Information elements and their 684 encoding are the same as defined for the Small Block, Large Block and 685 Expandable FEC Scheme in Figure 4. 687 6.2.2.3. Scheme-Specific 689 The Scheme-Specific FEC Object Transmission Information format 690 defined in Section 4.2.2.3 SHALL be used. 692 6.3. Procedures 694 The algorithm defined in Section 9.1. of [RFC5052] MUST be used to 695 partition the file into source blocks. 697 6.4. FEC code specification 699 The FEC code specification and the correspondance of Encoding Symbols 700 IDs to encoding symbols are defined by specific instances of this 701 scheme and so are out of scope of this document. 703 7. Security Considerations 705 This specification does not introduce any further security 706 considerations beyond those described in [RFC5052]. 708 8. Acknowledgments 710 This document is substantially based on [RFC3695] by Michael Luby and 711 Lorenzo Vicisano and [RFC3452] by Michael Luby, Lorenzo Vicisano, Jim 712 Gemmell, Luigi Rizzo, Mark Handley and Jon Crowcroft. 714 9. IANA Considerations 716 FEC Encoding IDs 0 and 130 were first defined and registered in the 717 ietf:rmt:fec:encoding namespace by [RFC3695]. This document updates 718 and obsoletes the definitions from that specification. References to 719 that specification should be replaced with references to this 720 document. 722 FEC Encoding IDs 128 and 129 were first defined and registered in the 723 ietf:rmt:fec:encoding namespace by [RFC3452]. This document updates 724 and obsoletes the definitions from that specification. ces to that 725 specification should be replaced with references to this document. 727 Values of FEC Encoding IDs and FEC Instance IDs are subject to IANA 728 registration. For general guidelines on IANA considerations as they 729 apply to this document, see [RFC5052]. 731 This document assigns the Fully-Specified FEC Encoding ID 0 under the 732 ietf:rmt:fec:encoding name-space (which was previously assigned by 733 [RFC3695] which is obsoleted by this document) to "Compact No-Code" 734 as specified in Section 3 above. 736 This document assigns the Under-Specified FEC Encoding ID 128 under 737 the ietf:rmt:fec:encoding name-space (which was previously assigned 738 by [RFC3452]) to "Small Block, Large Block and Expandable FEC Codes" 739 as specified in Section 4 above. 741 This document assigns the Under-Specified FEC Encoding ID 129 under 742 the ietf:rmt:fec:encoding name-space (which was previously assigned 743 by [RFC3452]) to "Small Block, Systematic FEC Codes" as specified in 744 Section 5 above. 746 This document assigns the Under-Specified FEC Encoding ID 130 under 747 the ietf:rmt:fec:encoding name-space (which was previously assigned 748 by [RFC3695] which is obsoleted by this document) to "Compact FEC" as 749 specified in Section 6 above. 751 As FEC Encoding IDs 128, 129 and 130 are Under-Specified, "FEC 752 Instance ID" sub-name-spaces must be established, in accordance to 753 [RFC5052]. Hence this document also assumes responsibility for the 754 "FEC Instance ID" registriesnamed 756 ietf:rmt:fec:encoding:instance:128, scoped by ietf:rmt:fec: 757 encoding = 128 759 ietf:rmt:fec:encoding:instance:129, scoped by ietf:rmt:fec: 760 encoding = 129 761 ietf:rmt:fec:encoding:instance:130, scoped by ietf:rmt:fec: 762 encoding = 130 764 The values that can be assigned within these namespaces are non- 765 negative numeric indices. Assignment requests are granted on a 766 "First Come First Served" basis. [RFC5052] specifies additional 767 criteria that MUST be met for the assignment within the generic ietf: 768 rmt:fec:encoding:instance name-space. These criteria also apply to 769 ietf:rmt:fec:encoding:instance:128, ietf:rmt:fec:encoding:instance: 770 129 and ietf:rmt:fec:encoding:instance:130. 772 10. Changes from schemes defined in RFC3452 and RFC3695 774 This section describes the changes between the Exprimental versions 775 of these FEC Scheme specifictions contained in RFC3452 [RFC3452] and 776 RFC3695 [RFC3695] and those defined in this specification: 778 o Scheme definitions have been updated to meet the requirements of 779 [RFC5052]. 781 o Complete encoding formats for the FEC Object Trasmission 782 Information for each scheme are defined here, instead of within 783 content delivery protocol specifications, since the exact format 784 depends on the FEC Scheme. 786 o The previous specifications for the Compact No-Code and Small 787 Block Systematic FEC Schemes did not require that all encoding 788 symbols of the object should have the same length. This 789 requirement is introduced in this specification. Since no 790 protocols have been defined which support variation of the 791 encoding symbol length within an object this should not cause 792 backwards compatibility issues. 794 11. References 796 11.1. Normative References 798 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 799 Requirement Levels", BCP 14, RFC 2119, March 1997. 801 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 802 Correction (FEC) Building Block", RFC 5052, August 2007. 804 11.2. Informative References 806 [RFC3452] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, 807 M., and J. Crowcroft, "Forward Error Correction (FEC) 808 Building Block", RFC 3452, December 2002. 810 [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, 811 M., and J. Crowcroft, "The Use of Forward Error Correction 812 (FEC) in Reliable Multicast", RFC 3453, December 2002. 814 [RFC3269] Kermode, R. and L. Vicisano, "Author Guidelines for 815 Reliable Multicast Transport (RMT) Building Blocks and 816 Protocol Instantiation documents", RFC 3269, April 2002. 818 [RFC3048] Whetten, B., Vicisano, L., Kermode, R., Handley, M., 819 Floyd, S., and M. Luby, "Reliable Multicast Transport 820 Building Blocks for One-to-Many Bulk-Data Transfer", 821 RFC 3048, January 2001. 823 [RFC3695] Luby, M. and L. Vicisano, "Compact Forward Error 824 Correction (FEC) Schemes", RFC 3695, February 2004. 826 Author's Address 828 Mark Watson 829 Digital Fountain 830 39141 Civic Center Drive 831 Suite 300 832 Fremont, CA 94538 833 U.S.A. 835 Email: mark@digitalfountain.com 837 Full Copyright Statement 839 Copyright (C) The IETF Trust (2008). 841 This document is subject to the rights, licenses and restrictions 842 contained in BCP 78, and except as set forth therein, the authors 843 retain all their rights. 845 This document and the information contained herein are provided on an 846 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 847 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 848 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 849 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 850 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 851 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 853 Intellectual Property 855 The IETF takes no position regarding the validity or scope of any 856 Intellectual Property Rights or other rights that might be claimed to 857 pertain to the implementation or use of the technology described in 858 this document or the extent to which any license under such rights 859 might or might not be available; nor does it represent that it has 860 made any independent effort to identify any such rights. Information 861 on the procedures with respect to rights in RFC documents can be 862 found in BCP 78 and BCP 79. 864 Copies of IPR disclosures made to the IETF Secretariat and any 865 assurances of licenses to be made available, or the result of an 866 attempt made to obtain a general license or permission for the use of 867 such proprietary rights by implementers or users of this 868 specification can be obtained from the IETF on-line IPR repository at 869 http://www.ietf.org/ipr. 871 The IETF invites any interested party to bring to its attention any 872 copyrights, patents or patent applications, or other proprietary 873 rights that may cover technology that may be required to implement 874 this standard. Please address the information to the IETF at 875 ietf-ipr@ietf.org.