idnits 2.17.1 draft-ietf-rmt-bb-fec-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 1 longer page, the longest (page 2) being 112 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 25 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 3 instances of too long lines in the document, the longest one being 2 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 373 has weird spacing: '... is used t...' == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- 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 (13 January 2000) is 8870 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: 'BLA84' is mentioned on line 307, but not defined == Missing Reference: 'NON97' is mentioned on line 326, but not defined == Unused Reference: 'BLA94' is defined on line 837, but no explicit reference was found in the text == Unused Reference: 'DEE88' is defined on line 844, but no explicit reference was found in the text == Unused Reference: 'GEM99' is defined on line 847, but no explicit reference was found in the text == Unused Reference: 'HAN98' is defined on line 852, but no explicit reference was found in the text == Unused Reference: 'HAN96' is defined on line 855, but no explicit reference was found in the text == Unused Reference: 'LUB99' is defined on line 863, but no explicit reference was found in the text == Unused Reference: 'R2068' is defined on line 870, but no explicit reference was found in the text == Unused Reference: 'R2119' is defined on line 874, but no explicit reference was found in the text == Unused Reference: 'RIZ97a' is defined on line 877, but no explicit reference was found in the text == Unused Reference: 'RUB99' is defined on line 890, but no explicit reference was found in the text == Unused Reference: 'VIC98A' is defined on line 893, but no explicit reference was found in the text == Unused Reference: 'VIC98B' is defined on line 897, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'AFZ95' -- Possible downref: Non-RFC (?) normative reference: ref. 'BLA94' -- Possible downref: Non-RFC (?) normative reference: ref. 'BYE98' ** Downref: Normative reference to an Historic RFC: RFC 1058 (ref. 'DEE88') -- Possible downref: Non-RFC (?) normative reference: ref. 'GEM99' ** Obsolete normative reference: RFC 2327 (ref. 'HAN98') (Obsoleted by RFC 4566) -- Possible downref: Non-RFC (?) normative reference: ref. 'HAN96' -- Possible downref: Non-RFC (?) normative reference: ref. 'LUB97' -- Possible downref: Non-RFC (?) normative reference: ref. 'LUB99' -- Possible downref: Non-RFC (?) normative reference: ref. 'LUB00' ** Obsolete normative reference: RFC 2068 (Obsoleted by RFC 2616) -- Possible downref: Non-RFC (?) normative reference: ref. 'RIZ97a' -- Possible downref: Non-RFC (?) normative reference: ref. 'RIZ97b' -- Possible downref: Non-RFC (?) normative reference: ref. 'RIZ97c' -- Possible downref: Non-RFC (?) normative reference: ref. 'RUB99' -- Possible downref: Non-RFC (?) normative reference: ref. 'VIC98A' -- Possible downref: Non-RFC (?) normative reference: ref. 'VIC98B' Summary: 7 errors (**), 0 flaws (~~), 20 warnings (==), 16 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 RMT Working Group M.Luby/Digital Fountain 2 Internet Engineering Task Force L.Vicisano/Cisco 3 INTERNET-DRAFT L.Rizzo/U. of Pisa 4 draft-ietf-rmt-bb-fec-01.txt J.Gemmell/Microsoft 5 13 July 2000 J.Crowcroft/UCL 6 B. Lueckenhoff/Cadence 7 Expires 13 January 2000 9 Reliable Multicast Transport Building Block: 10 Forward Error Correction Codes 11 13 Status of this Memo 15 This document is an Internet-Draft and is in full conformance with 16 all provisions of Section 10 of RFC2026. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are valid for a maximum of six months and may be 24 updated, replaced, or obsoleted by other documents at any time. It 25 is inappropriate to use Internet-Drafts as reference material or to 26 cite them other than as a "work in progress". 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 Abstract 36 This memo describes the use of Forward Error Correction (FEC) codes 37 within the context of reliable IP multicast transport and provides an 38 introduction to some commonly-used FEC codes. 40 Draft RMT BB, Forward Error Correction Codes 13 July 2000 42 1. Rationale and Overview 44 There are many ways to provide reliability for transmission protocols. 45 A common method is to use ARQ, automatic request for retransmission. 46 With ARQ, receivers use a back channel to the sender to send requests 47 for retransmission of lost packets. ARQ works well for one-to-one 48 reliable protocols, as evidenced by the pervasive success of TCP/IP. 49 ARQ has also been an effective reliability tool for one-to-many 50 reliability protocols, and in particular for some reliable IP multicast 51 protocols. However, for one-to-very many reliability protocols, ARQ has 52 limitations, including the feedback implosion problem because many 53 receivers are transmitting back to the sender, and the need for a back 54 channel to send these requests from the receiver. Another limitation is 55 that receivers may experience different loss patterns of packets, and 56 thus receivers may be delayed by retransmission of packets that other 57 receivers have lost that but they have already received. This may also 58 cause wasteful use of bandwidth used to retransmit packets that have 59 already been received by many of the receivers. 61 In environments where ARQ is either costly or impossible because there 62 is either a very limited capacity back channel or no back channel at 63 all, such as satellite transmission, a Data Carousel approach to 64 reliability is sometimes used [AFZ95]. With a Data Carousel, the sender 65 partitions the object into equal length pieces of data, which we 66 hereafter call source symbols, places them into packets, and then 67 continually cycles through and sends these packets. Receivers 68 continually receive packets until they have received a copy of each 69 packet. Data Carousel has the advantage that it requires no back 70 channel because there is no data that flows from receivers to the 71 sender. However, Data Carousel also has limitations. For example, if a 72 receiver loses a packet in one round of transmission it must wait an 73 entire round before it has a chance to receive that packet again. This 74 may also cause wasteful use of bandwidth, as the sender continually 75 cycles through and transmits the packets until no receiver is missing a 76 packet. 78 FEC codes provide a reliability method that can be used to augment or 79 replace other reliability methods, especially for one-to-many 80 reliability protocols such as reliable IP multicast. We first briefly 81 review some of the basic properties and types of FEC codes before 82 reviewing their uses in the context of reliable IP multicast. Later, we 83 provide a more detailed description of some of FEC codes. 85 In the general literature, FEC refers to the ability to overcome both 86 erasures (losses) and bit-level corruption. However, in the case of IP 88 Draft RMT BB, Forward Error Correction Codes 13 July 2000 90 multicast, lower network layers will detect corrupted packets and 91 discard them. Therefore, an IP multicast protocol need not be concerned 92 with corruption; the focus is solely on erasure codes. The payloads are 93 generated and processed using an FEC erasure encoder and objects are 94 reassembled from reception of packets using the corresponding FEC 95 erasure decoder. 97 The input to an FEC encoder is some number k of equal length source 98 symbols. The FEC encoder generates some number of encoding symbols that 99 are of the same length as the source symbols. The chosen length of the 100 symbols can vary upon each application of the FEC encoder, or it can be 101 fixed. These encoding symbols are placed into packets for transmission. 102 The number of encoding symbols placed into each packet can vary on a per 103 packet basis, or a fixed number of symbols (often one) can be placed 104 into each packet. Also, in each packet is placed enough information to 105 identify the particular encoding symbols carried in that packet. Upon 106 receipt of packets containing encoding symbols, the receiver feeds these 107 encoding symbols into the corresponding FEC decoder to recreate an exact 108 copy of the k source symbols. Ideally, the FEC decoder can recreate an 109 exact copy from any k of the encoding symbols. 111 In a later section, we describe a technique for using FEC codes as 112 described above to handle blocks with variable length source symbols. 114 Block FEC codes work as follows. The input to a block FEC encoder is k 115 source symbols and a number n. The encoder generates n-k redundant 116 symbols yielding an encoding block of n encoding symbols in total 117 composed of the k source symbols and the n-k redundant symbols. A block 118 FEC decoder has the property that any k of the n encoding symbols in the 119 encoding block is sufficient to reconstruct the original k source 120 symbols. 122 Expandable FEC codes work as follows. An expandable FEC encoder takes 123 as input k source symbols and generates as many unique encoding symbols 124 as requested on demand, where the amount of time for generating each 125 encoding symbol is the same independent of how many encoding symbols are 126 generated. Unlike block FEC codes, the source symbols are not 127 considered part of the encoding symbols for an expandable FEC code. An 128 expandable FEC decoder has the property that any k of the unique 129 encoding symbols is sufficient to reconstruct the original k source 130 symbols. 132 Along a different dimension, we classify FEC codes loosely as being 133 either small or large. A small FEC code is efficient in terms of 134 processing time requirements for encoding and decoding for small values 136 Draft RMT BB, Forward Error Correction Codes 13 July 2000 138 of k, and a large FEC code is efficient for encoding and decoding for 139 much large values of k. There are implementations of standard block FEC 140 codes that have encoding times proportional to n times the length of the 141 k source symbols, and decoding times proportional l times the length of 142 the k source symbols, where l is the number of missing source symbols 143 among the k received encoding symbols. Because of the growth rate of 144 the encoding and decoding times as a function of k and n, these are 145 typically considered to be small block FEC codes. There are close 146 approximations to block FEC codes which for all practical purposes can 147 generate n encoding symbols and can decode the k source symbols in time 148 proportional to the length of the n encoding symbols. These codes are 149 considered to be large block FEC codes. There are close approximations 150 to expandable FEC codes which for all practical purposes can generate 151 each encoding symbol in time proportional to its length, and can decode 152 all k source symbols in time proportional to their length. These are 153 considered to be large expandable FEC codes. 155 Ideally, FEC codes in the context of IP multicast can be used to 156 generate encoding symbols that are transmitted in packets in such a way 157 that each received packet is fully useful to a receiver to reassemble 158 the object regardless of previous packet reception patterns. Thus, if 159 some packets are lost in transit between the sender and the receiver, 160 instead of asking for specific retransmission of the lost packets or 161 waiting till the packets are resent using Data Carousel, the receiver 162 can use any other subsequent equal amount of data contained in packets 163 that arrive to reassemble the object. These packets can either be 164 proactively transmitted or they can be explicitly requested by 165 receivers. This implies that the data contained in the same packet is 166 fully useful to all receivers to reassemble the object, even though the 167 receivers may have previously experienced different packet loss 168 patterns. This property can reduce or even eliminate the problems 169 mentioned above associated with ARQ and Data Carousel and thereby 170 dramatically increase the scalability of the protocol to orders of 171 magnitude more receivers. 173 1.1. Application of FEC codecs 175 For some reliable IP multicast protocols, FEC codes are used in 176 conjunction with ARQ to provide reliability. For example, a large 177 object could be partitioned into a number of source blocks consisting of 178 a small number of source symbols each, and in a first round of 179 transmission all of the source symbols for all the source blocks could 180 be transmitted. Then, receivers could report back to the sender the 181 number of source symbols they are missing from each source block. The 183 Draft RMT BB, Forward Error Correction Codes 13 July 2000 185 sender could then compute the maximum number of missing source symbols 186 from each source block among all receivers. Based on this, a small 187 block FEC encoder could be used to generate for each source block a 188 number of redundant symbols equal to the computed maximum number of 189 missing source symbols from the block among all receivers. In a second 190 round of transmission, the server would then send all of these redundant 191 symbols for all blocks. In this example, if there are no losses in the 192 second round of transmission then all receivers will be able to recreate 193 an exact copy of each original block. In this case, even if different 194 receivers are missing different symbols in different blocks, transmitted 195 redundant symbols for a given block are useful to all receivers missing 196 symbols from that block in the second round. 198 For other reliable IP multicast protocols, FEC codes are used in a Data 199 Carousel fashion to provide reliability, which we call an FEC Data 200 Carousel. For example, an FEC Data Carousel using a large block FEC 201 code could work as follows. The large block FEC encoder produces n 202 encoding symbols considering all the k source symbols of an object as 203 one block. The sender cycles through and transmits the n encoding 204 symbols in packets in the same order in each round. An FEC Data 205 Carousel can have much better protection against packet loss than a Data 206 Carousel. For example, a receiver can join the transmission at any 207 point in time, And, as long as the receiver receives at least k encoding 208 symbols during the transmission of the next n encoding symbols, the 209 receiver can completely recover the object. This is true even if the 210 receiver starts receiving packets in the middle of a pass through the 211 encoding symbols. This method can also be used when the object is 212 partitioned into blocks and a short block FEC code is applied to each 213 block separately. In this case, as we explain in more detail below, it 214 is useful to interleave the symbols from the different blocks when they 215 are transmitted. 217 Since any number of encoding symbols can be generated using an 218 expandable FEC encoder, reliable IP multicast protocols that use 219 expandable FEC codes generally rely solely on these codes for 220 reliability. For example, when an expandable FEC code is used in a FEC 221 Data Carousel application, the encoding packets never repeat, and thus 222 any k of the encoding symbols in the potentially unbounded number of 223 encoding symbols are sufficient to recover the original k source 224 symbols. 226 For yet other reliable IP multicast protocols the method to obtain 227 reliability is to generate enough encoding symbols so that each encoding 228 symbol is transmitted at most once. For example, the sender can decide 229 a priori how many encoding symbols it will transmit, use an FEC code to 231 Draft RMT BB, Forward Error Correction Codes 13 July 2000 233 generate that number of encoding symbols from the object, and then 234 transmit the encoding symbols to all receivers. This method is for 235 example applicable to streaming protocols, where the stream is 236 partitioned into objects, the source symbols for each object are encoded 237 into encoding symbols using an FEC code, and then the sets of encoding 238 symbols for each object are transmitted one after the other using IP 239 multicast. 241 2. FEC Codes 243 2.1. Simple codes 245 There are some very simple codes that are effective for repairing packet 246 loss under very low loss conditions. For example, one simple way to 247 provide protection from a single loss is to partition the object into 248 fixed size source symbols and then add a redundant symbol that is the 249 parity (XOR) of all the source symbols. The size of a source symbol is 250 chosen so that it fits perfectly into the payload of a packet, i.e. if 251 the packet payload is 512 bytes then each source symbol is 512 bytes. 252 The header of each packet contains enough information to identify the 253 payload. In this case, this includes a symbol ID. The symbol IDs are 254 numbered consecutively starting from zero independently for the source 255 symbols and for the redundant symbol. Thus, the packet header also 256 contains an encoding flag that indicates whether the symbol in the 257 payload is a source symbol or a redundant symbol, where 1 indicates 258 source symbol and 0 indicates redundant symbol. For example, if the 259 object consists of four source symbols that have values a, b, c and d, 260 then the value of the redundant symbol is e = a XOR b XOR c XOR d. 261 Then, the packets carrying these symbols look like 263 (0, 1: a), (1, 1: b), (2, 1: c), (3, 1: d), (0, 0: e). 265 In this example, the first two fields are in the header of the packet, 266 where the first field is the symbol ID and the second field is the 267 encoding flag. The portion of the packet after the colon is the 268 payload. Any single symbol of the object can be recovered as the parity 269 of all the other symbols. For example, if packets 271 (0, 1: a), (1, 1: b), (3, 1: d), (0, 0: e) 273 are received then the symbol value for the missing source symbol with ID 274 2 can be recovered by computing a XOR b XOR d XOR e = c. 276 Draft RMT BB, Forward Error Correction Codes 13 July 2000 278 When the number of source symbols in the object is large, a simple block 279 code variant of the above can be used. In this case, the source symbols 280 are grouped together into source blocks of some number k of consecutive 281 symbols each, where k may be different for different blocks. If a block 282 consists of k source symbols then a redundant symbol is added to form an 283 encoding block consisting of k+1 encoding symbols. Then, a source block 284 consisting of k source symbols can be recovered from any k of the k+1 285 encoding symbols from the associated encoding block. 287 Slightly more sophisticated ways of adding redundant symbols using 288 parity can also be used. For example, one can group a block consisting 289 of k source symbols in an object into a p x p square matrix, where p = 290 sqrt(k). Then, for each row a redundant symbol is added that is the 291 parity of all the source symbols in the row. Similarly, for each column 292 a redundant symbol is added that is the parity of all the source symbols 293 in the column. Then, any row of the matrix can be recovered from any p 294 of the p+1 symbols in the row, and similarly for any column. Higher 295 dimensional product codes using this technique can also be used. 296 However, one must be wary of using these constructions without some 297 thought towards the possible loss patterns of symbols. Ideally, the 298 property that one would like to obtain is that if k source symbols are 299 encoded into n encoding symbols (the encoding symbols consist of the 300 source symbols and the redundant symbols) then the k source symbols can 301 be recovered from any k of the n encoding symbols. Using the simple 302 constructions described above does not yield codes that come close to 303 obtaining this ideal behavior. 305 2.2. Small block FEC codes 307 Reliable IP multicast protocols may use a block (n, k) FEC code [BLA84]. 308 A popular example of these types of codes is a class of Reed-Solomon 309 codes. For such codes, k source symbols are encoded into n > k encoding 310 symbols, such that any k of the encoding symbols can be used to 311 reassemble the original k source symbols. Thus, these codes have 0% 312 reception overhead when used to encode the entire object directly. 313 Block codes are usually systematic, which means that the n encoding 314 symbols consist of the k source symbols and n-k redundant symbols 315 generated from these k source symbols, where the size of a redundant 316 symbol is the same as that for a source symbol. For example, the first 317 simple code (XOR) described in the previous subsection is a (k+1, k) 318 code. In general, the freedom to choose n larger than k+1 is desirable, 319 as this can provide much better protection against losses. Codes of 320 this sort are often based on algebraic methods using finite fields. 321 Some of the most popular such codes are based on linear block codes. 323 Draft RMT BB, Forward Error Correction Codes 13 July 2000 325 Implementations of (n, k) FEC erasure codes are efficient enough to be 326 used by personal computers [RIZ97c, NON97]. For example, [RIZ97b] 327 describes an implementation where the encoding and decoding speeds decay 328 as C/j, where the constant C is on the order of 10 to 80 Mbytes/second 329 for Pentium class machines of various vintages and j is upper bounded by 330 min(k, n-k). 332 In practice, the values of k and n must be small (below 256) for such 333 FEC codes as large values make encoding and decoding prohibitively 334 expensive. As many objects are longer than k symbols for reasonable 335 values of k and the symbol length (e.g. larger than 16 kilobyte for k = 336 16 using 1 kilobyte symbols), they can be divided into a number of 337 source blocks. Each source block consists of some number k of source 338 symbols, where k may vary between different source blocks. The FEC 339 encoder is used to encode a k source symbol source block into a n 340 encoding symbol encoding block, where the length n of the encoding block 341 may vary for each source block. For a receiver to completely recover 342 the object, for each source block consisting of k source symbols, k 343 distinct encoding symbols (i.e., with different symbol IDs) must be 344 received from the corresponding encoding block. For some encoding 345 blocks, more encoding symbols may be received than there are source 346 symbols in the corresponding source block, in which case any additional 347 encoding symbols are discarded. An example encoding structure is shown 348 in Figure 1. 350 Draft RMT BB, Forward Error Correction Codes 13 July 2000 352 | source symbols | source symbols | 353 | of source block 0 | of source block 1 | 354 | | 355 v v 356 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 357 |0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 | 358 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 359 | 360 FEC encoder 361 | 362 v 363 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 364 |0 |1 |2 |3 | 4| 5| 6| 7| 8| 9| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 365 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 366 ^ ^ 367 | | 368 | encoding symbols | encoding symbols | 369 | of encoding block 0 | of encoding block 1 | 371 Figure 1. Encoding structure for object divided into two source 372 blocks consisting of 8 source symbols each, and the FEC encoder 373 is used to generate 2 additional redundant symbols (10 encoding 374 symbols in total) for each of the two source blocks. 376 In many cases, an object is partitioned into equal length source blocks 377 each consisting of k contiguous source symbols of the object, i.e., 378 block c consists of the range of source symbols [ck, (c+1)k-1]. This 379 ensure that the FEC encoder can be optimized to handle a particular 380 number k of source symbols. This also ensures that memory references 381 are local when the sender reads source symbols to encode, and when the 382 receiver reads encoding symbols to decode. Locality of reference is 383 particularly important when the object is stored on disk, as it reduces 384 the disk seeks required. The block number and the source symbol ID 385 within that block can be used to uniquely specify a source symbol within 386 the object. If the size of the object is not a multiple of k source 387 symbols, then the last source block will contain less than k symbols. 389 Encoding symbols can be uniquely identified by block number and encoding 390 symbol ID. The block numbers can be numbered consecutively starting 391 from zero. One way of identifying encoding symbols within a block are 392 to use symbol IDs and an encoding flag that is used to specify whether 393 an encoding symbol is a source symbol or a redundant symbol, where for 394 example 1 indicates source symbol and 0 indicate redundant symbol. The 396 Draft RMT BB, Forward Error Correction Codes 13 July 2000 398 symbol IDs can be numbered consecutively starting from zero for each 399 block independently for the source symbols and for the redundant 400 symbols. Thus, an encoding symbol can be identified by its block 401 number, the encoding flag, and the symbol ID. For example, if the 402 object consists 10 source symbols with values a, b, c, d, e, f, g, h, i, 403 and j, and k = 5 and n = 8, then there are two source blocks consisting 404 of 5 symbols each, and there are two encoding blocks consisting of 8 405 symbols each. Let p, q and r be the values of the redundant symbols for 406 the first encoding block, and let x, y and z be the values of the 407 redundant symbols for the second encoding block. Then the encoding 408 symbols together with their identifiers are 410 (0, 0, 1: a), (0, 1, 1: b), (0, 2, 1: c), (0, 3, 1: d), (0, 4, 1: e), 411 (0, 0, 0: p), (0, 1, 0: q), (0, 2, 0: r), 413 (1, 0, 1: f), (1, 1, 1: g), (1, 2, 1: h), (1, 3, 1: i), (1, 4, 1: j), 414 (1, 0, 0: x), (1, 1, 0: y), (1, 2, 0: z). 416 In this example, the first three fields identify the encoding symbol, 417 where the first field is the block number, the second field is the 418 symbol ID and the third field is the encoding flag. The value of the 419 encoding symbol is written after the colon. Each block can be recovered 420 from any 5 of the 8 encoding symbols associated with that block. For 421 example, reception of (0, 1, 1: b), (0, 2, 1: c), (0, 3, 1: d), (0, 0, 422 0: p) and (0, 1, 0: q) are sufficient to recover the first source block 423 and reception of (1, 0, 1: f), (1, 1, 1: g), (1, 0, 0: x), (1, 1, 0: y) 424 and (1, 2, 0: z) are sufficient to recover the second source block. 426 2.3. Large block FEC codes 428 Tornado codes [LUB97] are block FEC codes that provide an alternative to 429 small block FEC codes. A (n, k) Tornado code requires slightly more 430 than k out of n encoding symbols to reassemble k source symbols. 431 However, the advantage is that the value of k may be on the order of 432 tens of thousands and still run efficiently. Because of memory 433 considerations, in practice the value of n is restricted to be a small 434 multiple of k, e.g., n = 2k. For example, [BYE98] describes an 435 implementation of Tornado codes where the encoding and decoding speeds 436 are tens of megabytes per second range for Pentium class machines of 437 various vintages when k is in the tens of thousands and n = 2k. The 438 reception overhead for such values of k and n is in the 5-10% range. 439 Tornado codes require a large amount of out of band information to be 440 communicated to all senders and receivers for each different object 442 Draft RMT BB, Forward Error Correction Codes 13 July 2000 444 length, and require an amount of memory on the encoder and decoder which 445 is proportional to the object length times 2n/k. 447 Tornado codes are designed to have low reception overhead on average 448 with respect to reception of a random portion of the encoding packets. 449 Thus, to ensure that a receiver can reassemble the object with low 450 reception overhead, the packets are permuted into a random order before 451 transmission. 453 2.4. Expandable FEC codes 455 All of the FEC codes described up to this point are block codes. There 456 is a different type of FEC codes that we call expandable FEC codes. 457 Like block codes, an expandable FEC encoder operates on an object of 458 known size that is partitioned into equal length source symbols. Unlike 459 block codes, ideally there is no predetermined number of encoding 460 symbols that can be generated for expandable FEC codes. Instead, an 461 expandable FEC encoder can generate as few or as many unique encoding 462 symbols as required on demand. Also unlike block codes, optimal 463 expandable FEC codes have the additional attractive property that 464 encoding symbols for the same object can be generated and transmitted 465 from multiple servers and concurrently received by a receiver and yet 466 the receiver incurs a 0% reception overhead. 468 LT codes [LUB00] are an example of large expandable FEC codes. An LT 469 encoder uses randomization to generate each encoding symbol randomly and 470 independently of all other encoding symbols. Like Tornado codes, the 471 number of source symbols k may be very large for LT codes, i.e., on the 472 order of tens to hundreds of thousands, and the encoder and decoder run 473 efficiently in software. For example the encoding and decoding speeds 474 for LT codes are in the range 3-20 megabytes per second for Pentium 475 class machines of various vintages when k is in the high tens of 476 thousands. An LT encoder closely approximates the properties of an 477 ideal expandable FEC encoder, as it can generate as few or as many 478 encoding symbols as required on demand. When a new encoding symbol is 479 to be generated by an LT encoder, it is based on a randomly chosen 480 32-bit encoding symbol ID that uniquely describes how the encoding 481 symbol is to be generated from the input symbols. In general, each 482 encoding symbol ID value corresponds to a unique encoding symbol, and 483 thus the space of possible encoding symbols is approximately four 484 billion. Thus, the chance that a particular encoding symbol is the same 485 as any other particular encoding symbol is tiny. An LT decoder has the 486 property that with very high probability the receipt of any set of 487 slightly more than k randomly and independently generated encoding 489 Draft RMT BB, Forward Error Correction Codes 13 July 2000 491 symbols is sufficient to reassemble the k source symbols. For example, 492 when k is on the order of tens to hundreds of thousands the reception 493 overhead is less than 5% with no failures in tens of millions of trials 494 under a variety of loss conditions. 496 Because encoding symbols are randomly and independently generated by 497 choosing random encoding symbol IDs, LT codes have the property that 498 encoding symbols for the same k source symbols can be generated and 499 transmitted from multiple senders ad than if all the encoding symbols 500 were generated by a single sender. The only requirement is that the 501 senders choose their encoding symbol IDs randomly and independently of 502 one another. 504 There is a weak tradeoff between the number of source symbols and the 505 reception overhead for LT codes, and the larger the number of source 506 symbols the smaller the reception overhead. Thus, for shorter objects, 507 it is sometimes advantageous to include multiple symbols in each packet. 508 Normally, and in the discussion below, there is only one symbol per 509 packet. 511 There are a couple of factors for choosing the appropriate symbol 512 length/ number of input symbols tradeoff. The primary consideration is 513 that there is a fixed overhead per symbol component in the overall 514 processing requirements of the encoding and decoding, independent of the 515 number of input symbols. Thus, using shorter symbols means that this 516 fixed overhead processing per symbol will be a larger component of the 517 overall processing requirements, leading to larger overall processing 518 requirements. Because of this, it is advisable to use a reasonably 519 sized fixed symbol length independent of the length of the object, and 520 thus shorter objects will be partitioned into fewer symbols than larger 521 objects. A second much less important consideration is that there is a 522 component of the processing per symbol that depends logarithmically on 523 the number of input symbols, and thus for this reason there is a slight 524 preference towards less input symbols. 526 Like small block codes, there is a point when the object is large enough 527 that it makes sense to partition it into blocks when using LT codes. 528 Generally the object is partitioned into blocks whenever the number of 529 source symbols times the packet payload length is less than the size of 530 the object. Thus, if the packet payload is 1024 bytes and the number of 531 source symbols is 64,000 then any object over 64 megabytes will be 532 partitioned into more than one block. One can choose the number of 533 source symbols to partition the object into, depending on the desired 534 encoding and decoding speed versus reception overhead tradeoff desired. 535 Encoding symbols can be uniquely identified by a block number (when the 537 Draft RMT BB, Forward Error Correction Codes 13 July 2000 539 object is large enough to be partitioned into more than one block) and 540 an encoding symbol ID. The block numbers, if they are used, are 541 generally numbered consecutively starting from zero within the object. 542 The block number and the encoding symbol ID are both chosen uniformly 543 and randomly from their range when an encoding symbol is to be generated 544 and transmitted. For example, suppose the number of source symbols is 545 64,000 and the number of blocks is 2. Then, each packet generated by 546 the LT encoder could be of the form (b, x: y). In this example, the 547 first two fields identify the encoding symbol, where the first field is 548 the block number b = 0 or 1 and the second field is the randomly chosen 549 encoding symbol ID x. The value y after the colon is the value of the 550 encoding symbol. 552 2.5. Source blocks with variable length source symbols 554 For all the FEC codes described above, all the source symbols in the 555 same source block are all of the same length. In this section, we 556 describe a general technique to handle the case when it is desirable to 557 use source symbols of varying lengths in a single source block. This 558 technique is applicable to block FEC codes. 560 Let l_1, l_2, ... , l_k be the lengths of k varying length source 561 symbols to be considered part of the same source block. Let lmax be the 562 maximum over i = 1, ... , k of l_i. To prepare the source block for the 563 FEC encoder, pad each source symbol i out to length lmax with a suffix 564 of lmax-i zeroes, and then prepend to the beginning of this the value 565 l_i. Thus, each padded source symbol is of length x+lmax, assuming that 566 the length of an original symbol takes x bytes to store. These padded 567 source symbols, each of length x+lmax, are the input to the encoder, 568 together with the value n. The encoder then generates n-k redundant 569 symbols, each of length x+lmax. 571 The encoding symbols that are placed into packets consist of the 572 original k varying length source symbols and n-k redundant symbols, each 573 of length x+lmax. >From any k of the received encoding symbols, the FEC 574 decoder recreates the k original source symbols as follows. If all k 575 original source symbols are received, then no decoding is necessary. 576 Otherwise, at least one redundant symbol is received, from which the 577 receiver can easily whether the block was composed of variable-length 578 source symbols: if the redundant symbol(s) has a size different (larger) 579 from the source symbols then the source symbols are variable-length. 580 Note that in a variable-length block the redundant symbols are always 581 larger than the largest source symbol, due to the presence of the 582 encoded symbol-length. The receiver can determine the value of lmax by 584 Draft RMT BB, Forward Error Correction Codes 13 July 2000 586 subtracting x from the length of a received redundant symbol. Note that 587 x MUST be a protocol constant. For each of the received original source 588 symbols, the receiver can generate the corresponding padded source 589 symbol as described above. Then, the input to the FEC decoder is the 590 set of received redundant symbols, together with the set of padded 591 source symbols constructed from the received original symbols. The FEC 592 decoder then produces the set of k padded source symbols. Once the k 593 padded source symbols have been recovered, the length l_i of original 594 source symbol i can be recovered from the first x bytes of the ith 595 padded source symbol, and then original source symbol i is obtained by 596 taking the next l_i bytes following the x bytes of the length field. 598 3. FEC Abstract Packet Fields and Out-of-Band Information 600 This section specify the information that protocol packets must carry to 601 implement the various forms of FEC-based reliability. A session is 602 defined to be all the information associated with a transmission of data 603 about a particular object by a single sender. There are three classes 604 of packets that may contain FEC information within a session: data 605 packets, session-control packets and feedback packets. They generally 606 contain different kinds of FEC information. Note that some protocols do 607 not use feedback packets. 609 Data packets MAY sometime serve as session-control packets as well; both 610 data and session-control packets generally travel downstream (from the 611 sender towards receivers) and are addressed to a multicast IP address 612 (sometime the might be addressed to the unicast address of a specific 613 receiver). In the following, for simplicity we will refer to both data 614 and session control packets as downstream-traveling packets, or simply 615 downstream packets. 617 As a general rule, feedback packets travel upstream (from receivers to 618 the sender) and are addressed to the unicast address of the sender. 619 Sometimes, however, they might be addressed to a multicast IP address or 620 to the unicast address of a receiver or also the the unicast address of 621 some different node (intermediate node that provides recovery services 622 or neighboring router). 624 The FEC-related information that can be present in downstream packets 625 can be classified as follows: 627 1) FEC Encoding Identifier 629 Draft RMT BB, Forward Error Correction Codes 13 July 2000 631 Identifies the FEC encoding being used and has the purpose of 632 allowing receivers to select the appropriate FEC decoder. As a 633 general rule, the "FEC Encoding Identifier" MUST be the same for 634 a given session, i.e., for all transmission of data related to a 635 particular object, but MAY vary across different transmissions of 636 data about different objects in different sessions, even if 637 transmitted using the same set of multicast groups. 639 2) FEC payload ID 641 Identifies the symbol(s) in the payload of the packet. The 642 content of this piece of information depends on the encoder being 643 used (e.g. in Block FEC codes this may be the combination of 644 block index and symbol index; in expandable FEC codes this may be 645 just a flat symbol identifier). 647 3) FEC Object Transmission Information 649 This is information regarding the encoding of a specific object 650 needed by the FEC decoder (e.g. for Block FEC codes this may be 651 the combination of block length and object length). This might 652 also include general parameters of the FEC encoder. 654 All the classes of information above, except 2), can either be 655 transmitted within the transport session (using protocol packet-header 656 fields) or out of band. The information described in 2) MUST be 657 transmitted in data-packet header fields, as it provides a description 658 of the data contained in the packet. In the following we specify the 659 content of 1), 2) and 3) independent of whether these pieces of 660 information are transmitted in protocol packets or out of band. This 661 document does not specify out of band methods to transport the 662 information. 664 Within the context of FEC repair schemes, feedback packets are 665 (optionally) used to request FEC retransmission. The FEC-related 666 information present in feedback packets can be classified as follow: 668 1) FEC Block Identifier 670 This is the identifier of the FEC block for which retransmission 671 is requested. This information does not apply to some type of 672 decoders. 674 Draft RMT BB, Forward Error Correction Codes 13 July 2000 676 2) Number of Repair Symbols 678 This is the number of repair symbols requested, needed to recover 679 the object. 681 3.1. FEC Encoding Identifier 683 This is a numeric index that identifies a specific FEC encoding scheme 684 OR a class of encoding schemes that share the same format of "FEC 685 Payload ID" and "FEC Object Transmission Information". 687 The FEC Encoding Identifier identifies a specific FEC encoding scheme 688 when the encoding scheme is formally and fully specified, in a way that 689 independent implementors can implement both encoder and decoder from the 690 specification. Companion documents of this specification may specify 691 such FEC encoding schemes and associate them with "FEC Encoding 692 Identifier" values. These documents MUST also specify a correspondent 693 format for the "FEC Payload ID" and "FEC Object Transmission 694 Information". Currently FEC Encoding Identifiers in the range 0-127 are 695 reserved for this class of encoding schemes. 697 It is possible that a FEC encoding scheme cannot be completely specified 698 or that such a specification is simply not available or also that a 699 party exists that owns the encoding scheme and it is not willing to 700 disclose its algorithm. We refer to these encoding schemes as "Under- 701 Specified" schemes. Under-specified schemes can still be identified as 702 follows: 704 o A format of the fields "FEC Payload ID" and "FEC Object 705 Transmission Information" MUST be defined for the encoding scheme. 707 o A value of "FEC Encoding Identifier" MUST be reserved and 708 associated to the format definitions above. An already reserved 709 "FEC Encoding Identifier" MUST be reused if it is associated to 710 the same format of "FEC Payload ID" and "FEC Object Transmission 711 Information" as the ones needed for the new under-specified FEC 712 encoding scheme. 714 o A value of "FEC Encoding Name" must be reserved (see below). 716 An Under-specified FEC scheme is completely identified by the tuple (FEC 717 Encoding Identifier, FEC Encoding Name). The party that owns this tuple 718 MUST be able to provide an FEC encoder and decoder that implement the 720 Draft RMT BB, Forward Error Correction Codes 13 July 2000 722 under-specified FEC encoding scheme identified by the tuple. 724 "FEC Encoding Names" are numeric identifiers scoped by a FEC Encoding 725 Identifier. 727 The FEC Encoding Name MUST be part of the "FEC Object Transmission 728 Information" and must be communicated to receivers together with the FEC 729 Encoding Identifier. 731 An FEC Encoding Identifier MAY also define a format for the (abstract) 732 feedback packet fields "FEC Block Identifier" and "Number of Repair 733 Symbols". 735 3.2. FEC Payload ID and FEC Object Transmission Information 737 A document that specifies an encoding scheme and reserves a value of FEC 738 Encoding Identifier MUST define a packet-field format for FEC Payload ID 739 and FEC Object Transmission Information according to the need of the 740 encoding scheme. This also applies to documents that reserves values of 741 FEC Encoding Identifiers for under-specified encoding schemes. In this 742 case the FEC Object Transmission Information must also include a field 743 to contain the "FEC Encoding Name". 745 A packet field definition of FEC Object Transmission Information MUST be 746 provided despite the fact that protocol instantiation may decide to 747 communicate this information out of band. 749 The packet field format of "FEC Block Identifier" and "Number of Repair 750 Symbols" SHOULD be specified for each FEC encoding scheme, even the 751 scheme is mainly intended for feedback-less protocols. FEC Block 752 Identifier may not apply to some encoding schemes. 754 All packet field definition (FEC Payload ID, FEC Object Transmission 755 Information, FEC Block Identifier and Number of Repair Symbols) MUST be 756 fully specified at level of bit-fields and they must have a length that 757 is a multiple of a 4-byte word (this is to facilitate the alignment of 758 packet fields in protocol instantiations). 760 4. IANA Considerations 762 Values of FEC Encoding Identifiers and FEC Encoding Names are subject to 763 IANA registration. FEC Encoding Identifiers and FEC Encoding Names are 764 hierarchical: FEC Encoding Identifiers (at the top level) scope ranges 766 Draft RMT BB, Forward Error Correction Codes 13 July 2000 768 of FEC Encoding Names. Not all FEC Encoding Identifiers have a 769 corresponding FEC Encoding Name scope (see below). 771 A FEC Encoding Identifier is a numeric non-negative index. Value from 0 772 to 127 are reserved for FEC encoders that are fully specified, as 773 described in section 3.1. The assignment of a FEC Encoding Identifier in 774 this range can only be granted if the requestor can provide such a 775 specification published as an IETF RFC. Value grater than 127 can be 776 assigned to under-specified encoding schemes. 778 In any case values of FEC Encoding Identifiers can only be assigned if 779 the required FEC packet fields corresponding to it (see section 3.1) are 780 specified in a RFC. 782 Each FEC Encoding Identifier assigned to an under-specified encoding 783 scheme scopes a range of FEC Encoding Names. An FEC Encoding Name is a 784 numeric non-negative index. The document that reserves a FEC Encoding 785 Identifier MAY also specify a range for the subordinate FEC Encoding 786 Names. 788 Under the scope of a FEC Encoding Identifier, FEC Encoding Names are 789 assigned on a First Come First Served base to requestors that are able 790 to provide point of contact information and a pointer to publicly 791 accessible documentation describing the FEC encoder and a ways to obtain 792 it. The requestor is responsible for keeping this information up to 793 date. 795 5. Security Considerations 797 The use of FEC, in and of itself, imposes no additional security 798 considerations versus sending the same information without FEC. 799 However, just like for any transmission system, a malicious sender may 800 intentionally transmit bad symbols. If a receiver accepts one or more 801 bad symbols in place of authentic ones then such a receiver will have 802 its entire object down-load corrupted by the bad symbol. Application- 803 level transmission object authentication can detect the corrupted 804 transfer, but the receiver must then discard the transferred object. 805 Thus, transmitting false symbols is at least an effective denial of 806 service attack. At worst, a malicious sender could add, delete, or 807 replace arbitrary data within the transmitted object. 809 In light of this possibility, FEC receivers may screen the source 810 address of a received symbol against a list of authentic transmitter 811 addresses. Since source addresses may be spoofed, FEC transport 813 Draft RMT BB, Forward Error Correction Codes 13 July 2000 815 protocols may provide mechanisms for robust source authentication of 816 each encoded symbol. Multicast routers along the path of a FEC transfer 817 may provide the capability of discarding multicast packets that 818 originated on that subnet, and whose source IP address does not 819 correspond with that subnet. 821 6. Intellectual Property Disclosure 823 Tornado codes [LUB97] have both patents issued and patents pending. LT 824 codes [LUB00] have patents pending. 826 7. Acknowledgments 828 Thanks to Vincent Roca and Hayder Radha for their detailed comments on 829 this draft. 831 8. References 833 [AFZ95] Acharya, S., Franklin, M., and Zdonik, S., ``Dissemination- 834 Based Data Delivery Using Broadcast Disks'', IEEE Personal 835 Communications, pp.50-60, Dec 1995. 837 [BLA94] Blahut, R.E., ``Theory and Practice of Error Control Codes'', 838 Addison Wesley, MA 1984. 840 [BYE98] Byers, J.W., Luby, M., Mitzenmacher, M., and Rege, A., ``A 841 Digital Fountain Approach to Reliable Distribution of Bulk Data'', 842 Proceedings ACM SIGCOMM '98, Vancouver, Canada, Sept 1998. 844 [DEE88] Deering, S., ``Host Extensions for IP Multicasting'', RFC 845 1058, Stanford University, Stanford, CA, 1988. 847 [GEM99] Gemmell, J., Schooler, E., and Gray, J., ``ALC Scalable 848 Multicast File Distribution: Caching and Parameters Optimizations'' 849 Technical Report MSR-TR-99-14, Microsoft Research, Redmond, WA, April, 850 1999. 852 [HAN98] Handley, M., and Jacobson, V., ``SDP: Session Description 853 Protocol'', RFC 2327, April 1998. 855 [HAN96] Handley, M., ``SAP: Session Announcement Protocol'', Internet 856 Draft, IETF MMUSIC Working Group, Nov 1996. 858 Draft RMT BB, Forward Error Correction Codes 13 July 2000 860 [LUB97] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D., 861 Stemann, V., ``Practical Loss-Resilient Codes'' 29th STOC'97. 863 [LUB99] Luby, M., Vicisano, L., Speakman, T. ``Heterogeneous multicast 864 congestion control based on router packet filtering'', presented at 865 RMT meeting in Pisa, March 1999. 867 [LUB00] Luby, M., "An overview of LT codes", Digital Fountain white paper, 868 July 2000. 870 [R2068] Fielding, R., Gettys, J., Mogul, J. Frystyk, H., Berners-Lee, 871 T., Hypertext Transfer Protocol HTTP/1.1 (IETF RFC2068) 872 http://www.rfc-editor.org/rfc/rfc2068.txt 874 [R2119] Bradner, S., Key words for use in RFCs to Indicate Requirement 875 Levels (IETF RFC 2119) http://www.rfc-editor.org/rfc/rfc2119.txt 877 [RIZ97a] Rizzo, L, and Vicisano, L., ``Reliable Multicast Data 878 Distribution protocol based on software FEC techniques'', Proceedings 879 of the Fourth IEEE Workshop on the Architecture and Implementation of 880 High Performance Communication Systems, HPCS-97, Chalkidiki, Greece, 881 June 1997. 883 [RIZ97b] Rizzo, L., and Vicisano, L., ``Effective Erasure Codes for 884 Reliable Computer Communication Protocols'', ACM SIGCOMM Computer 885 Communication Review, Vol.27, No.2, pp.24-36, Apr 1997. 887 [RIZ97c] Rizzo, L., ``On the Feasibility of Software FEC'', DEIT Tech 888 Report, http://www.iet.unipi.it/ luigi/softfec.ps, Jan 1997. 890 [RUB99] Rubenstein, Dan, Kurose, Jim and Towsley, Don, ``The Impact of 891 Multicast Layering on Network Fairness'', Proceedings of ACM SIGCOMM'99. 893 [VIC98A] L.Vicisano, L.Rizzo, J.Crowcroft, ``TCP-like Congestion 894 Control for Layered Multicast Data Transfer'', IEEE Infocom '98, San 895 Francisco, CA, Mar.28-Apr.1 1998. 897 [VIC98B] Vicisano, L., ``Notes On a Cumulative Layered Organization 898 of Data Packets Across Multiple Streams with Different Rates'', 899 University College London Computer Science Research Note RN/98/25, 900 Work in Progress (May 1998). 902 Draft RMT BB, Forward Error Correction Codes 13 July 2000 904 A. Predefined FEC encoders 906 This appendix specifies the FEC Encoding Identifier and the relative 907 packets field for a number of known schemes that follow under the class 908 of under-specified FEC encoding schemes. Others may be specified in 909 companion documents. 911 A.1. Small Block, Large Block and Expandable FEC Codes 913 This section reserves a FEC Encoding Identifier for the family of codes 914 described in Section 2.2, 2.3 and 2.4 and specifies the relative packet 915 fields. Under-specified FEC encoding schemes that belong to this class 916 MUST use this identifier and packet field definitions. 918 The FEC Encoding Identifier assigned to Small Block, Large Block, and 919 Expandable FEC Codes is 128. 921 The FEC Payload ID is composed of an encoding symbol index and an 922 encoding block number structured as follows: 924 0 1 2 3 925 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 926 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 927 | encoding block number | 928 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 929 | encoding symbol ID | 930 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 932 In addition, a one bit FEC Encoding Flag SHOULD be included, and this 933 flag indicates whether the encoding symbol(s) in the payload of the 934 packet are source symbol(s) or redundant symbol(s). The FEC Object 935 Transmission Information has the following structure: 937 Draft RMT BB, Forward Error Correction Codes 13 July 2000 939 0 1 2 3 940 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 941 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 942 | FEC Encoding Name | Object Length (MSB) | 943 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 944 | Object Length (LSB) | 945 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 946 | Source Block Length | 947 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 949 Note that this structure limits the range of possible FEC Encoding Names 950 to 0-:-65536, despite the FEC Object Transmission Information can also 951 be transmitted out of band. 953 The Object Length, composed of a Most Significant Bytes portion (MSB) 954 and a Least Significant Bytes portion (LSB), is expressed in bytes. 956 Feedback packet MUST contain both FEC Block Identifier and Number of 957 Repair Symbols. Their structure is the following: 959 0 1 2 3 960 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 961 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 962 | FEC Block Identifier | 963 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 965 0 1 2 3 966 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 967 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 968 | Number of Repair Symbols | 969 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 971 9. Authors' Addresses 973 Michael Luby 974 luby@digitalfountain.com 975 Digital Fountain 976 600 Alabama Street 977 San Francisco, CA, USA, 94110 979 Draft RMT BB, Forward Error Correction Codes 13 July 2000 981 Lorenzo Vicisano 982 lorenzo@cisco.com 983 cisco Systems, Inc. 984 170 West Tasman Dr., 985 San Jose, CA, USA, 95134 987 Luigi Rizzo 988 luigi@iet.unipi.it 989 Dip. di Ing. dell'Informazione 990 Universita` di Pisa 991 via Diotisalvi 2, 56126 Pisa, Italy 993 Jim Gemmell 994 jgemmell@microsoft.com 995 Microsoft Research 996 301 Howard St., #830 997 San Francisco, CA, USA, 94105 999 Jon Crowcroft 1000 J.Crowcroft@cs.ucl.ac.uk 1001 Department of Computer Science 1002 University College London 1003 Gower Street, 1004 London WC1E 6BT, UK 1006 Bruce Lueckenhoff 1007 brucelu@cadence.com 1008 Cadence Design Systems, Inc. 1009 120 Cremona Drive, Suite C 1010 Santa Barbara, CA 93117 1012 Draft RMT BB, Forward Error Correction Codes 13 July 2000 1014 10. Full Copyright Statement 1016 Copyright (C) The Internet Society (2000). All Rights Reserved. 1018 This document and translations of it may be copied and furnished to 1019 others, and derivative works that comment on or otherwise explain it or 1020 assist in its implementation may be prepared, copied, published and 1021 distributed, in whole or in part, without restriction of any kind, 1022 provided that the above copyright notice and this paragraph are included 1023 on all such copies and derivative works. However, this document itself 1024 may not be modified in any way, such as by removing the copyright notice 1025 or references to the Internet Society or other Internet organizations, 1026 except as needed for the purpose of developing Internet standards in 1027 which case the procedures for copyrights defined in the Internet 1028 languages other than English. 1030 The limited permissions granted above are perpetual and will not be 1031 revoked by the Internet Society or its successors or assigns. 1033 This document and the information contained herein is provided on an "AS 1034 IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK 1035 FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT 1036 LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT 1037 INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR 1038 FITNESS FOR A PARTICULAR PURPOSE." 1040 Draft RMT BB, Forward Error Correction Codes 13 July 2000 1042 Table of Contents 1044 1 Rationale and Overview .......................................... 2 1045 1.1 Application of FEC codecs ..................................... 4 1046 2 FEC Codes ....................................................... 6 1047 2.1 Simple codes .................................................. 6 1048 2.2 Small block FEC codes ......................................... 7 1049 2.3 Large block FEC codes ......................................... 10 1050 2.4 Expandable FEC codes .......................................... 11 1051 2.5 Source blocks with variable length source symbols ............. 13 1052 3 FEC Abstract Packet Fields and Out-of-Band Information .......... 14 1053 3.1 FEC Encoding Identifier ....................................... 16 1054 3.2 FEC Payload ID and FEC Object Transmission Information ........ 17 1055 4 IANA Considerations ............................................. 17 1056 5 Security Considerations ......................................... 18 1057 6 Intellectual Property Disclosure ................................ 19 1058 7 Acknowledgments ................................................. 19 1059 8 References ...................................................... 19 1060 A. Predefined FEC encoders ....................................... 21 1061 A.1. Small Block, Large Block and Expandable FEC Codes ........... 21 1062 9 Authors' Addresses .............................................. 22 1063 10 Full Copyright Statement ....................................... 24