idnits 2.17.1 draft-ietf-rmt-bb-fec-basic-schemes-revised-04.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 15. -- Found old boilerplate from RFC 3978, Section 5.5, updated by RFC 4748 on line 779. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 790. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 797. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 803. 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 Copyright Line does not match the current year == Line 478 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 (November 16, 2007) is 6004 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 365, 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 (~~), 3 warnings (==), 9 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 Intended status: Standards Track November 16, 2007 5 Expires: May 19, 2008 7 Basic Forward Error Correction (FEC) Schemes 8 draft-ietf-rmt-bb-fec-basic-schemes-revised-04 10 Status of this Memo 12 By submitting this Internet-Draft, each author represents that any 13 applicable patent or other IPR claims of which he or she is aware 14 have been or will be disclosed, and any of which he or she becomes 15 aware will be disclosed, in accordance with Section 6 of BCP 79. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on May 19, 2008. 35 Copyright Notice 37 Copyright (C) The IETF Trust (2007). 39 Abstract 41 This document provides FEC Scheme specifications according to the RMT 42 FEC Building Block for the Compact No-Code FEC Scheme, the Small 43 Block, Large Block and Expandable FEC Scheme, the Small Block 44 Systematic FEC Scheme and the Compact FEC Scheme. 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 . . . . . . . . . . . . . . . . . . . . . . . . 8 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 . . . . . . . . . . . . . . . . . . 17 73 6. Compact FEC Scheme . . . . . . . . . . . . . . . . . . . . . . 18 74 6.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 18 75 6.2. Formats and Codes . . . . . . . . . . . . . . . . . . . . 18 76 6.2.1. FEC Payload ID(s) . . . . . . . . . . . . . . . . . . 18 77 6.2.2. FEC Object Transmission Information . . . . . . . . . 18 78 6.3. Procedures . . . . . . . . . . . . . . . . . . . . . . . . 18 79 6.4. FEC code specification . . . . . . . . . . . . . . . . . . 18 80 7. Security Considerations . . . . . . . . . . . . . . . . . . . 19 81 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 20 82 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 83 10. Changes from schemes defined in RFC3452 and RFC3695 . . . . . 22 84 11. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23 85 11.1. Normative References . . . . . . . . . . . . . . . . . . . 23 86 11.2. Informative References . . . . . . . . . . . . . . . . . . 23 87 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 24 88 Intellectual Property and Copyright Statements . . . . . . . . . . 25 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 RFC 3048 [RFC3048]. This document is 111 a product of the IETF RMT WG and follows the general guidelines 112 provided in RFC 3269 [RFC3269]. 114 RFC3452 [RFC3452] and RFC3695 [RFC3695] contained a previous versions 115 of the FEC Schemes defined in this specification. These RFCs were 116 published in the "Experimental" category. It was the stated intent 117 of the RMT working group to re-submit these specifications as an IETF 118 Proposed Standard in due course. 120 This Proposed Standard specification is thus based on and backwards 121 compatible with the FEC Schemes defined in RFC3452 [RFC3452] and 122 RFC3695 [RFC3695] updated according to accumulated experience and 123 growing protocol maturity since their original publication. Said 124 experience applies both to this specification itself and to 125 congestion control strategies related to the use of this 126 specification. 128 The differences between the FEC Scheme specifications in RFC3452 129 [RFC3452] and RFC3695 [RFC3695] and this document listed in 130 Section 10 132 2. Requirements notation 134 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 135 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 136 document are to be interpreted as described in [RFC2119]. 138 3. Compact No-Code FEC Scheme 140 3.1. Introduction 142 The Compact No-code FEC Scheme is a Fully-Specified FEC Scheme. The 143 scheme requires no FEC coding and is specified primarily to allow 144 simple interoperability testing between different implementations of 145 protocol instantiations that use the FEC building block. 147 3.2. Formats and Codes 149 3.2.1. FEC Payload ID(s) 151 The FEC Payload ID for the Compact No-Code FEC Scheme is composed of 152 a Source Block Number and an Encoding Symbol ID as shown in Figure 1. 154 0 1 2 3 155 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 156 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 157 | Source Block Number | Encoding Symbol ID | 158 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 160 Figure 1: FEC Payload ID format for Compact No-Code FEC Scheme 162 The 16-bit Source Block Number is used to identify from which source 163 block of the object the encoding symbol in the payload of the packet 164 is generated. There are two possible modes: In the unique SBN mode 165 each source block within the object has a unique Source Block Number 166 associated with it, and in the non-unique SBN mode the same Source 167 Block Number may be used for more than one source block within the 168 object. Which mode is being used for an object is outside the scope 169 of this document and MUST be communicated, either explicitly or 170 implicitly, out-of-band to receivers. 172 If the unique SBN mode is used then successive Source Block Numbers 173 are associated with consecutive source blocks of the object starting 174 with Source Block Number 0 for the first source block of the object. 175 In this case, there are at most 2^^16 source blocks in the object. 177 If the non-unique SBN mode is used then the mapping from source 178 blocks to Source Block Numbers MUST be communicated out-of-band to 179 receivers, and how this is done is outside the scope of this 180 document. This mapping could be implicit, for example determined by 181 the transmission order of the source blocks. In non-unique SBN mode, 182 packets for two different source blocks mapped to the same Source 183 Block Number SHOULD NOT be sent within an interval of time that is 184 shorter than the transport time of a source block. The transport 185 time of a source block includes the amount of time the source block 186 is processed at the transport layer by the sender, the network 187 transit time for packets, and the amount of time the source block is 188 processed at the transport layer by a receiver. This allows the 189 receiver to clearly decide which packets belong to which source 190 block. 192 The 16-bit Encoding Symbol ID identifies which specific encoding 193 symbol generated from the source block is carried in the packet 194 payload. The exact details of the correspondence between Encoding 195 Symbol IDs and the encoding symbols in the packet payload are 196 specified in Section 3.4. 198 3.2.2. FEC Object Transmission Information 200 3.2.2.1. Mandatory 202 The mandatory FEC Object Transmission Information element for the 203 Compact No-Code FEC Scheme is: 205 o FEC Encoding ID: zero (0) 207 3.2.2.2. Common 209 The common FEC Object Transmission Information elements and their 210 value ranges for the Compact No-code FEC Scheme are: 212 Transfer-Length: a non-negative integer less than 2^^48. 214 Encoding-Symbol-Length: a non-negative integer less than 2^^16. 216 Maximum-Source-Block-Length: a non-negative integer less than 2^^32. 218 Note that the semantics for the above elements are defined in 219 [RFC5052] and are not duplicated here. 221 The encoded Common FEC Object Transmission information is defined in 222 Figure 2. 224 0 1 2 3 225 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 226 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 227 | Transfer Length | 228 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 229 | | Reserved | 230 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 231 | Encoding Symbol Length | Max. Source Block Length (MSB)| 232 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 233 | Max. Source Block Length (LSB)| 234 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 236 Figure 2: Encoded Common FEC OTI for Compact No-Code FEC Scheme 238 All Encoding Symbols of a transport object MUST have length equal to 239 the length specified in the Encoding Symbol Length element, with the 240 optional exception of the last source symbol of the last source block 241 (so that redundant padding is not mandatory in this last symbol). 242 This last source symbol MUST be logically padded out with zeroes when 243 another Encoding Symbol is computed based on this source symbol to 244 ensure the same interpretation of this Encoding Symbol value by the 245 sender and receiver. However, this padding does not actually need to 246 be sent with the data of the last source symbol. 248 The "Reserved" field in the Encoded FEC Object Transmission 249 Information SHOULD be set to zero by senders and its value SHOULD be 250 ignored by receivers. 252 Note: this FEC Scheme was first defined in [RFC3695] which did not 253 require that the Encoding Symbol Length should be the same for 254 every source block. This document introduces a general 255 requirement that the Encoding Symbol Length be the same across 256 source blocks. Since no protocols were defined which support 257 variation in the Encoding Symbol Length between source blocks this 258 can be done without introducing backwards compatibility issues. 260 3.2.2.3. Scheme-Specific 262 No Scheme-Specific FEC Object Transmission Information elements are 263 defined by this FEC Scheme. 265 3.3. Procedures 267 The algorithm defined in Section 9.1. of [RFC5052] MUST be used to 268 partition the file into source blocks. 270 3.4. FEC code specification 272 The Compact No-Code FEC scheme does not require FEC encoding or 273 decoding. Instead, each encoding symbol consists of consecutive 274 bytes of a source block of the object. 276 The following two subsections describe the details of how the Compact 277 No-Code FEC scheme operates for each source block of an object. 279 3.4.1. Source Block Logistics 281 Let X > 0 be the length of a source block in bytes. Let L > 0 be the 282 length of the encoding symbol contained in the payload of each 283 packet. The value of X and L are part of the FEC Object Transmission 284 Information, and how this information is communicated to a receiver 285 is outside the scope of this document. 287 For a given source block X bytes in length with Source Block Number 288 I, let N = X/L rounded up to the nearest integer. The encoding 289 symbol carried in the payload of a packet consists of a consecutive 290 portion of the source block. The source block is logically 291 partitioned into N encoding symbols, each L bytes in length, and the 292 corresponding Encoding Symbol IDs range from 0 through N-1 starting 293 at the beginning of the source block and proceeding to the end. 294 Thus, the encoding symbol with Encoding Symbol ID Y consists of bytes 295 L*Y through L*(Y+1)-1 of the source block, where the bytes of the 296 source block are numbered from 0 through X-1. If X/L is not integral 297 then the last encoding symbol with Encoding Symbol ID = N-1 consists 298 of bytes L*(N-1) through the last byte X-1 of the source block, and 299 the remaining L*N - X bytes of the encoding symbol can by padded out 300 with zeroes. 302 As an example, suppose that the source block length X = 20,400 and 303 encoding symbol length L = 1,000. The encoding symbol with Encoding 304 Symbol ID = 10 contains bytes 10,000 through 10,999 of the source 305 block, and the encoding symbol with Encoding Symbol ID = 20 contains 306 bytes 20,000 through the last byte 20,399 of the source block and the 307 remaining 600 bytes of the encoding symbol can be padded with zeroes. 309 There are no restrictions beyond the rules stated above on how a 310 sender generates encoding symbols to send from a source block. 311 However, it is recommended that an implementor of refer to the 312 companion document [RFC3452] for general advice. 314 In the next subsection a procedure is recommended for sending and 315 receiving source blocks. 317 3.4.2. Sending and Receiving a Source Block 319 The following carousel procedure is RECOMMENDED for a sender to 320 generate packets containing FEC Payload IDs and corresponding 321 encoding symbols for a source block with Source Block Number I. Set 322 the length in bytes of an encoding symbol to a fixed value L which is 323 reasonable for a packet payload (e.g., ensure that the total packet 324 size does not exceed the MTU) and that is smaller than the source 325 block length X, e.g., L = 1,000 for X >= 1,000. Initialize Y to a 326 value randomly chosen in the interval [0..N-1]. Repeat the following 327 for each packet of the source block to be sent. 329 o If Y <= N-1 then generate the encoding symbol Y. 331 o Within the FEC Payload ID, set the Source Block Length to X, set 332 the Source Block Number = I, set the Encoding Symbol ID = Y, place 333 the FEC Payload ID and the encoding symbol into the packet to 334 send. 336 o In preparation for the generation of the next packet: if Y < N-1 337 then increment Y by one else if Y = N-1 then reset Y to zero. 339 The following procedure is RECOMMENDED for a receiver to recover the 340 source block based on receiving packets for the source block from a 341 sender that is using the carousel procedure described above. The 342 receiver can determine from which source block a received packet was 343 generated by the Source Block Number carried in the FEC Payload ID. 344 Upon receipt of the first FEC Payload ID for a source block, the 345 receiver uses the source block length received out-of-band as part of 346 the FEC Object Transmission Information to determine the length X in 347 bytes of the source block, and allocates space for the X bytes that 348 the source block requires. The receiver also computes the length L 349 of the encoding symbol in the payload of the packet by substracting 350 the packet header length from the total length of the received packet 351 (and the receiver checks that this length is the same in each 352 subsequent received packet from the same source block). After 353 calculating N = X/L rounded up to the nearest integer, the receiver 354 allocates a boolean array RECEIVED[0..N-1] with all N entries 355 initialized to false to track received encoding symbols. The 356 receiver keeps receiving packets for the source block as long as 357 there is at least one entry in RECEIVED still set to false or until 358 the application decides to give up on this source block and move on 359 to other source blocks. For each received packet for the source 360 block (including the first packet) the steps to be taken to help 361 recover the source block are as follows. Let Y be the value of the 362 Encoding Symbol ID within FEC Payload ID of the packet. If Y <= N-1 363 then the receiver copies the encoding symbol into the appropriate 364 place within the space reserved for the source block and sets 365 RECEIVED[Y] = true. If all N entries of RECEIVED are true then the 366 receiver has recovered the entire source block. 368 4. Small Block, Large Block and Expandable FEC Scheme 370 4.1. Introduction 372 This section defines an Under-Specified FEC Scheme for Small Block 373 FEC codes, Large Block FEC codes and Expandable FEC codes as 374 described in [RFC3453]. 376 4.2. Formats and Codes 378 4.2.1. FEC Payload ID(s) 380 The FEC Payload ID is composed of a Source Block Number and an 381 Encoding Symbol ID structured as shown in Figure 3. 383 0 1 2 3 384 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 385 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 386 | Source Block Number | 387 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 388 | Encoding Symbol ID | 389 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 391 Figure 3: FEC Payload ID format for Small Block, Large Block and 392 Expandable FEC Codes 394 The Source Block Number identifies from which source block of the 395 object the encoding symbol(s) in the payload are generated. These 396 blocks are numbered consecutively from 0 to N-1, where N is the 397 number of source blocks in the object. 399 The Encoding Symbol ID identifies which specific encoding symbol(s) 400 generated from the source block are carried in the packet payload. 401 The exact details of the correspondence between Encoding Symbol IDs 402 and the encoding symbol(s) in the packet payload are dependent on the 403 particular FEC Scheme instance used as identified by the FEC Encoding 404 ID and by the FEC Instance ID, and these details may be proprietary. 406 4.2.2. FEC Object Transmission Information 408 4.2.2.1. Mandatory 410 The mandatory FEC Object Transmission Information element for the 411 Small Block, Large Block and Expandable FEC Scheme are: 413 o FEC Encoding ID: 128 415 4.2.2.2. Common 417 The common FEC Object Transmission Information elements and their 418 value ranges for the Small Block, Large Block and Expandable FEC 419 Scheme are: 421 FEC Instance ID: a non-negative integer less than 2^^16. 423 Transfer-Length: a non-negative integer less than 2^^48. 425 Encoding-Symbol-Length: a non-negative integer less than 2^^16. 427 Maximum-Source-Block-Length: a non-negative integer less than 2^^32. 429 Note that the semantics for the above elements are defined in 430 [RFC5052] and are not duplicated here. 432 The encoded Common FEC Object Transmission information is defined in 433 Section 4.2.2.2. 435 0 1 2 3 436 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 437 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 438 | Transfer Length | 439 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 440 | | FEC Instance ID | 441 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 442 | Encoding Symbol Length | Max. Source Block Length (MSB)| 443 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 444 | Max. Source Block Length (LSB)| 445 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 447 Figure 4: Encoded Common FEC OTI for Small Block, Large Block and 448 Expandable FEC Scheme 450 4.2.2.3. Scheme-Specific 452 The Scheme-specific FEC Object Transmission Information field for the 453 Small block, Large Block and Expandable FEC Scheme provides for the 454 possibility of Instance-specific FEC Object Transmission Information. 455 The format of the Scheme-Specific FEC Object Transmission information 456 for this FEC Scheme is defined in Figure 5 457 0 1 2 3 458 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 459 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 460 | Length | Instance-specific FEC OTI | 461 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 462 | | 463 | Instance-specific FEC OTI contd. | 464 | | 465 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 467 Figure 5: Encoded Scheme-specific FEC OTI for Small Block, Large 468 Block and Expandable FEC Scheme 470 The Scheme-specific FEC Object Transmission Information field 471 contains the following sub-fields: 473 Length (1 octet) specifies the length of the Scheme-specific FEC OTI 474 in four-octet words (including this length field), except that the 475 value zero indicates that no Instance-specific FEC OTI information 476 follows. 478 Instance-specific FEC OTI Information the contents of this field 479 are FEC Scheme Instance-specific 481 Note that in the case of a Content Delivery protocol which supports 482 external signalling of the total FEC Object Transmission Information 483 length, then the Scheme-Specific FEC OTI field defined here is 484 optional. Otherwise, this field MUST be included. 486 4.3. Procedures 488 The algorithm defined in Section 9.1. of [RFC5052] MUST be used to 489 partition the file into source blocks. 491 4.4. FEC Code Specification 493 The FEC code specification and the correspondance of Encoding Symbols 494 IDs to encoding symbols are defined by specific instances of this 495 scheme and so are out of scope of this document. 497 5. Small Block Systematic FEC Scheme 499 5.1. Introduction 501 This section defines an Under-Specified FEC Scheme for Small Block 502 Systematic FEC codes as described in [RFC3453]. For Small Block 503 Systematic FEC codes, each source block is of length at most 65536 504 source symbols. 506 Although these codes can generally be accommodated by the FEC 507 Encoding ID described in Section 4, a specific FEC Encoding ID is 508 defined for Small Block Systematic FEC codes to allow more 509 flexibility and to retain header compactness. The small source block 510 length and small expansion factor that often characterize systematic 511 codes may require the data source to frequently change the source 512 block length. To allow the dynamic variation of the source block 513 length and to communicate it to the receivers with low overhead, the 514 block length is included in the FEC Payload ID. 516 5.2. Formats and Codes 518 5.2.1. FEC Payload ID(s) 520 The FEC Payload ID is composed of the Source Block Number, Source 521 Block Length and the Encoding Symbol ID structured as shown in 522 Figure 6. 524 0 1 2 3 525 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 526 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 527 | Source Block Number | 528 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 529 | Source Block Length | Encoding Symbol ID | 530 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 532 Figure 6: FEC Payload ID format for Small Block Systematic FEC scheme 534 The Source Block Number identifies from which source block of the 535 object the encoding symbol(s) in the payload are generated. These 536 blocks are numbered consecutively from 0 to N-1, where N is the 537 number of source blocks in the object. 539 The Source Block Length is the length in units of source symbols of 540 the source block identified by the Source Block Number. 542 The Encoding Symbol ID identifies which specific encoding symbol(s) 543 generated from the source block are carried in the packet payload. 544 Each encoding symbol is either an original source symbol or a 545 redundant symbol generated by the encoder. The exact details of the 546 correspondence between Encoding Symbol IDs and the encoding symbol(s) 547 in the packet payload are dependent on the particular FEC scheme 548 instance used as identified by the FEC Instance ID, and these details 549 may be proprietary. 551 5.2.2. FEC Object Transmission Information 553 5.2.2.1. Mandatory 555 The mandatory FEC Object Transmission Information element for the 556 Small Block Systematic FEC Scheme is: 558 o FEC Encoding ID: 129 560 5.2.2.2. Common 562 The common FEC Object Transmission Information elements and their 563 value ranges for the Small Block Systematic FEC Scheme are: 565 FEC Instance ID: a non-negative integer less than 2^^16. 567 Transfer-Length: a non-negative integer less than 2^^48. 569 Encoding-Symbol-Length: a non-negative integer less than 2^^16. 571 Maximum-Source-Block-Length: a non-negative integer less than 2^^16. 573 Max-Number-of-Encoding-Symbols: a non-negative integer less than 574 2^^16 576 Note that the semantics for the above elements are defined in 577 [RFC5052] and are not duplicated here. 579 The encoded Common FEC Object Transmission information is defined in 580 Figure 7. 582 0 1 2 3 583 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 584 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 585 | Transfer Length | 586 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 587 | | FEC Instance ID | 588 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 589 | Encoding Symbol Length | Maximum Source Block Length | 590 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 591 | Max. Num. of Encoding Symbols | 592 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 594 Figure 7: FEC OTI format for Small Block Systematic FEC Scheme 596 All Encoding Symbols of a transport object MUST have length equal to 597 the length specified in the Encoding Symbol Length field, with the 598 optional exception of the last source symbol of the last source block 599 (so that redundant padding is not mandatory in this last symbol). 600 This last source symbol MUST be logically padded out with zeroes when 601 another Encoding Symbol is computed based on this source symbol to 602 ensure the same interpretation of this Encoding Symbol value by the 603 sender and receiver. However, this padding need not be actually sent 604 with the data of the last source symbol. 606 Note: this FEC Scheme was first defined in [RFC3452] which did not 607 require that the Encoding Symbol Length should be the same for 608 every source block. However, no protocols have been defined which 609 support variation in the Encoding Symbol Length between source 610 blocks and thus introduction of a general requirement that the 611 Encoding Symbol Length be the same across source blocks (as 612 defined here) should not cause backwards compatibility issues and 613 will aid interoperability. 615 5.2.2.3. Scheme-Specific 617 The Scheme-Specific FEC Object Transmission Information format 618 defined in Section 4.2.2.3 SHALL be used. 620 5.3. Procedures 622 The algorithm defined in Section 9.1. of [RFC5052] MAY be used to 623 partition the file into source blocks. 625 5.4. FEC Code Specification 627 The FEC code specification and the correspondance of Encoding Symbols 628 IDs to encoding symbols are defined by specific instances of this 629 scheme and so are out of scope of this document. 631 6. Compact FEC Scheme 633 6.1. Introduction 635 The Compact FEC Scheme is an Under-Specified FEC scheme. This FEC 636 scheme is similar in spirit to the Compact No-Code FEC scheme, except 637 that a non-trivial FEC encoding (that is Under-Specified) may be used 638 to generate encoding symbol(s) placed in the payload of each packet 639 and a corresponding FEC decoder may be used to produce the source 640 block from received packets. 642 6.2. Formats and Codes 644 6.2.1. FEC Payload ID(s) 646 The FEC Payload ID format defined in Section 3.2.1 SHALL be used. 648 6.2.2. FEC Object Transmission Information 650 6.2.2.1. Mandatory 652 The mandatory FEC Object Transmission Information element for the 653 Compact No-Code FEC Scheme is: 655 o FEC Encoding ID: 130 657 6.2.2.2. Common 659 The common FEC Object Transmission Information elements and their 660 encoding are the same as defined for the Small Block, Large Block and 661 Expandable FEC Scheme in Figure 4. 663 6.2.2.3. Scheme-Specific 665 The Scheme-Specific FEC Object Transmission Information format 666 defined in Section 4.2.2.3 SHALL be used. 668 6.3. Procedures 670 The algorithm defined in Section 9.1. of [RFC5052] MUST be used to 671 partition the file into source blocks. 673 6.4. FEC code specification 675 The FEC code specification and the correspondance of Encoding Symbols 676 IDs to encoding symbols are defined by specific instances of this 677 scheme and so are out of scope of this document. 679 7. Security Considerations 681 This specification does not introduce any further security 682 considerations beyond those described in [RFC5052]. 684 8. Acknowledgments 686 This document is substantially based on [RFC3695] by Michael Luby and 687 Lorenzo Vicisano and [RFC3452] by Michael Luby, Lorenzo Vicisano, Jim 688 Gemmell, Luigi Rizzo, Mark Handley and Jon Crowcroft. 690 9. IANA Considerations 692 FEC Encoding IDs 0 and 130 were first defined and registered in the 693 ietf:rmt:fec:encoding namespace by [RFC3695]. This document updates 694 and obsoletes the definitions from that specification. 696 FEC Encoding IDs 128 and 129 were first defined and registered in the 697 ietf:rmt:fec:encoding namespace by [RFC3452]. This document updates 698 and obsoletes the definitions from that specification. 700 10. Changes from schemes defined in RFC3452 and RFC3695 702 This section describes the changes between the Exprimental versions 703 of these FEC Scheme specifictions contained in RFC3452 [RFC3452] and 704 RFC3695 [RFC3695] and those defined in this specification: 706 o Scheme definitions have been updated to meet the requirements of 707 [RFC5052]. 709 o Complete encoding formats for the FEC Object Trasmission 710 Information for each scheme are defined here, instead of within 711 content delivery protocol specifications, since th exact format 712 depends on the FEC Scheme. 714 o The previous specifications for the Compact No-Code and Small 715 Block Systematic FEC Schemes sis not require that all encoding 716 symbols of the object should have the same length. This 717 requirement is introduced in this specification. Since no 718 protocols have been defined which support variation of the 719 encoding symbol length within an object this should not cause 720 backwards compatibility issues. 722 11. References 724 11.1. Normative References 726 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 727 Requirement Levels", BCP 14, RFC 2119, March 1997. 729 [RFC5052] Watson, M., Luby, M., and L. Vicisano, "Forward Error 730 Correction (FEC) Building Block", RFC 5052, August 2007. 732 11.2. Informative References 734 [RFC3452] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, 735 M., and J. Crowcroft, "Forward Error Correction (FEC) 736 Building Block", RFC 3452, December 2002. 738 [RFC3453] Luby, M., Vicisano, L., Gemmell, J., Rizzo, L., Handley, 739 M., and J. Crowcroft, "The Use of Forward Error Correction 740 (FEC) in Reliable Multicast", RFC 3453, December 2002. 742 [RFC3269] Kermode, R. and L. Vicisano, "Author Guidelines for 743 Reliable Multicast Transport (RMT) Building Blocks and 744 Protocol Instantiation documents", RFC 3269, April 2002. 746 [RFC3048] Whetten, B., Vicisano, L., Kermode, R., Handley, M., 747 Floyd, S., and M. Luby, "Reliable Multicast Transport 748 Building Blocks for One-to-Many Bulk-Data Transfer", 749 RFC 3048, January 2001. 751 [RFC3695] Luby, M. and L. Vicisano, "Compact Forward Error 752 Correction (FEC) Schemes", RFC 3695, February 2004. 754 Author's Address 756 Mark Watson 757 Digital Fountain 758 39141 Civic Center Drive 759 Suite 300 760 Fremont, CA 94538 761 U.S.A. 763 Email: mark@digitalfountain.com 765 Full Copyright Statement 767 Copyright (C) The IETF Trust (2007). 769 This document is subject to the rights, licenses and restrictions 770 contained in BCP 78, and except as set forth therein, the authors 771 retain all their rights. 773 This document and the information contained herein are provided on an 774 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 775 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND 776 THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS 777 OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF 778 THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 779 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 781 Intellectual Property 783 The IETF takes no position regarding the validity or scope of any 784 Intellectual Property Rights or other rights that might be claimed to 785 pertain to the implementation or use of the technology described in 786 this document or the extent to which any license under such rights 787 might or might not be available; nor does it represent that it has 788 made any independent effort to identify any such rights. Information 789 on the procedures with respect to rights in RFC documents can be 790 found in BCP 78 and BCP 79. 792 Copies of IPR disclosures made to the IETF Secretariat and any 793 assurances of licenses to be made available, or the result of an 794 attempt made to obtain a general license or permission for the use of 795 such proprietary rights by implementers or users of this 796 specification can be obtained from the IETF on-line IPR repository at 797 http://www.ietf.org/ipr. 799 The IETF invites any interested party to bring to its attention any 800 copyrights, patents or patent applications, or other proprietary 801 rights that may cover technology that may be required to implement 802 this standard. Please address the information to the IETF at 803 ietf-ipr@ietf.org. 805 Acknowledgment 807 Funding for the RFC Editor function is provided by the IETF 808 Administrative Support Activity (IASA).