idnits 2.17.1 draft-ietf-rmt-info-fec-00.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. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard == It seems as if not all pages are separated by form feeds - found 0 form feeds but 18 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an Abstract section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There is 1 instance of too long lines in the document, the longest one being 2 characters in excess of 72. ** There are 41 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == 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 (17 November 2000) is 8532 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) == Unused Reference: '4' is defined on line 633, but no explicit reference was found in the text == Unused Reference: '5' is defined on line 636, but no explicit reference was found in the text == Unused Reference: '6' is defined on line 640, but no explicit reference was found in the text == Unused Reference: '7' is defined on line 644, but no explicit reference was found in the text == Unused Reference: '8' is defined on line 647, but no explicit reference was found in the text == Unused Reference: '10' is defined on line 653, but no explicit reference was found in the text == Unused Reference: '12' is defined on line 659, but no explicit reference was found in the text == Unused Reference: '13' is defined on line 663, but no explicit reference was found in the text == Unused Reference: '14' is defined on line 666, but no explicit reference was found in the text == Unused Reference: '17' is defined on line 680, but no explicit reference was found in the text == Unused Reference: '18' is defined on line 683, but no explicit reference was found in the text == Unused Reference: '19' is defined on line 687, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' ** Downref: Normative reference to an Historic RFC: RFC 1058 (ref. '4') == Outdated reference: A later version (-07) exists of draft-ietf-rmt-bb-fec-01 ** Downref: Normative reference to an Experimental draft: draft-ietf-rmt-bb-fec (ref. '5') -- Possible downref: Non-RFC (?) normative reference: ref. '6' ** Obsolete normative reference: RFC 2327 (ref. '7') (Obsoleted by RFC 4566) -- Possible downref: Non-RFC (?) normative reference: ref. '8' -- Possible downref: Non-RFC (?) normative reference: ref. '9' -- Possible downref: Non-RFC (?) normative reference: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' ** Obsolete normative reference: RFC 2068 (ref. '12') (Obsoleted by RFC 2616) -- Possible downref: Non-RFC (?) normative reference: ref. '14' -- Possible downref: Non-RFC (?) normative reference: ref. '15' -- Possible downref: Non-RFC (?) normative reference: ref. '16' -- Possible downref: Non-RFC (?) normative reference: ref. '17' -- Possible downref: Non-RFC (?) normative reference: ref. '18' -- Possible downref: Non-RFC (?) normative reference: ref. '19' Summary: 13 errors (**), 0 flaws (~~), 17 warnings (==), 16 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Engineering Task Force RMT WG 2 INTERNET-DRAFT M.Luby/Digital Fountain 3 draft-ietf-rmt-info-fec-00.txt L.Vicisano/Cisco 4 J.Gemmell/Microsoft 5 L.Rizzo/ACIRI and Univ. Pisa 6 M.Handley/ACIRI 7 J. Crowcroft/UCL 8 17 November 2000 9 Expires: May 2001 11 The use of Forward Error Correction in Reliable Multicast 13 This document is an Internet-Draft and is in full conformance with all 14 provisions of Section 10 of RFC2026. 16 Internet-Drafts are working documents of the Internet Engineering Task 17 Force (IETF), its areas, and its working groups. Note that other groups 18 may also distribute working documents as Internet-Drafts. 20 Internet-Drafts are valid for a maximum of six months and may be 21 updated, replaced, or obsoleted by other documents at any time. It is 22 inappropriate to use Internet-Drafts as reference material or to cite 23 them other than as a "work in progress". 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt 28 To view the list Internet-Draft Shadow Directories, see 29 http://www.ietf.org/shadow.html. 31 This document is a product of the IETF RMT WG. Comments should be 32 addressed to the authors, or the WG's mailing list at rmt@lbl.gov. 34 Abstract 36 This memo describes the use of Forward Error Correction (FEC) 37 codes within the context of reliable IP multicast transport 38 and provides an introduction to some commonly-used FEC codes. 40 ^L 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 [1]. 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 87 multicast, lower network layers will detect corrupted packets and 88 discard them. Therefore, an IP multicast protocol need not be concerned 89 with corruption; the focus is solely on erasure codes. The payloads are 91 ^L 92 generated and processed using an FEC erasure encoder and objects are 93 reassembled from reception of packets using the corresponding FEC 94 erasure decoder. 96 The input to an FEC encoder is some number k of equal length source 97 symbols. The FEC encoder generates some number of encoding symbols that 98 are of the same length as the source symbols. The chosen length of the 99 symbols can vary upon each application of the FEC encoder, or it can be 100 fixed. These encoding symbols are placed into packets for transmission. 101 The number of encoding symbols placed into each packet can vary on a per 102 packet basis, or a fixed number of symbols (often one) can be placed 103 into each packet. Also, in each packet is placed enough information to 104 identify the particular encoding symbols carried in that packet. Upon 105 receipt of packets containing encoding symbols, the receiver feeds these 106 encoding symbols into the corresponding FEC decoder to recreate an exact 107 copy of the k source symbols. Ideally, the FEC decoder can recreate an 108 exact copy from any k of the encoding symbols. 110 In a later section, we describe a technique for using FEC codes as 111 described above to handle blocks with variable length source symbols. 113 Block FEC codes work as follows. The input to a block FEC encoder is k 114 source symbols and a number n. The encoder generates n-k redundant 115 symbols yielding an encoding block of n encoding symbols in total 116 composed of the k source symbols and the n-k redundant symbols. A block 117 FEC decoder has the property that any k of the n encoding symbols in the 118 encoding block is sufficient to reconstruct the original k source 119 symbols. 121 Expandable FEC codes work as follows. An expandable FEC encoder takes 122 as input k source symbols and generates as many unique encoding symbols 123 as requested on demand, where the amount of time for generating each 124 encoding symbol is the same independent of how many encoding symbols are 125 generated. Unlike block FEC codes, the source symbols are not 126 considered part of the encoding symbols for an expandable FEC code. An 127 expandable FEC decoder has the property that any k of the unique 128 encoding symbols is sufficient to reconstruct the original k source 129 symbols. 131 Along a different dimension, we classify FEC codes loosely as being 132 either small or large. A small FEC code is efficient in terms of 133 processing time requirements for encoding and decoding for small values 134 of k, and a large FEC code is efficient for encoding and decoding for 135 much large values of k. There are implementations of standard block FEC 136 codes that have encoding times proportional to n times the length of the 137 k source symbols, and decoding times proportional l times the length of 138 the k source symbols, where l is the number of missing source symbols 139 among the k received encoding symbols. Because of the growth rate of 141 ^L 142 the encoding and decoding times as a function of k and n, these are 143 typically considered to be small block FEC codes. There are close 144 approximations to block FEC codes which for all practical purposes can 145 generate n encoding symbols and can decode the k source symbols in time 146 proportional to the length of the n encoding symbols. These codes are 147 considered to be large block FEC codes. There are close approximations 148 to expandable FEC codes which for all practical purposes can generate 149 each encoding symbol in time proportional to its length, and can decode 150 all k source symbols in time proportional to their length. These are 151 considered to be large expandable FEC codes. 153 Ideally, FEC codes in the context of IP multicast can be used to 154 generate encoding symbols that are transmitted in packets in such a way 155 that each received packet is fully useful to a receiver to reassemble 156 the object regardless of previous packet reception patterns. Thus, if 157 some packets are lost in transit between the sender and the receiver, 158 instead of asking for specific retransmission of the lost packets or 159 waiting till the packets are resent using Data Carousel, the receiver 160 can use any other subsequent equal amount of data contained in packets 161 that arrive to reassemble the object. These packets can either be 162 proactively transmitted or they can be explicitly requested by 163 receivers. This implies that the data contained in the same packet is 164 fully useful to all receivers to reassemble the object, even though the 165 receivers may have previously experienced different packet loss 166 patterns. This property can reduce or even eliminate the problems 167 mentioned above associated with ARQ and Data Carousel and thereby 168 dramatically increase the scalability of the protocol to orders of 169 magnitude more receivers. 171 1.1. Application of FEC codecs 173 For some reliable IP multicast protocols, FEC codes are used in 174 conjunction with ARQ to provide reliability. For example, a large 175 object could be partitioned into a number of source blocks consisting of 176 a small number of source symbols each, and in a first round of 177 transmission all of the source symbols for all the source blocks could 178 be transmitted. Then, receivers could report back to the sender the 179 number of source symbols they are missing from each source block. The 180 sender could then compute the maximum number of missing source symbols 181 from each source block among all receivers. Based on this, a small 182 block FEC encoder could be used to generate for each source block a 183 number of redundant symbols equal to the computed maximum number of 184 missing source symbols from the block among all receivers. In a second 185 round of transmission, the server would then send all of these redundant 186 symbols for all blocks. In this example, if there are no losses in the 187 second round of transmission then all receivers will be able to recreate 188 an exact copy of each original block. In this case, even if different 190 ^L 191 receivers are missing different symbols in different blocks, transmitted 192 redundant symbols for a given block are useful to all receivers missing 193 symbols from that block in the second round. 195 For other reliable IP multicast protocols, FEC codes are used in a Data 196 Carousel fashion to provide reliability, which we call an FEC Data 197 Carousel. For example, an FEC Data Carousel using a large block FEC 198 code could work as follows. The large block FEC encoder produces n 199 encoding symbols considering all the k source symbols of an object as 200 one block. The sender cycles through and transmits the n encoding 201 symbols in packets in the same order in each round. An FEC Data 202 Carousel can have much better protection against packet loss than a Data 203 Carousel. For example, a receiver can join the transmission at any 204 point in time, And, as long as the receiver receives at least k encoding 205 symbols during the transmission of the next n encoding symbols, the 206 receiver can completely recover the object. This is true even if the 207 receiver starts receiving packets in the middle of a pass through the 208 encoding symbols. This method can also be used when the object is 209 partitioned into blocks and a short block FEC code is applied to each 210 block separately. In this case, as we explain in more detail below, it 211 is useful to interleave the symbols from the different blocks when they 212 are transmitted. 214 Since any number of encoding symbols can be generated using an 215 expandable FEC encoder, reliable IP multicast protocols that use 216 expandable FEC codes generally rely solely on these codes for 217 reliability. For example, when an expandable FEC code is used in a FEC 218 Data Carousel application, the encoding packets never repeat, and thus 219 any k of the encoding symbols in the potentially unbounded number of 220 encoding symbols are sufficient to recover the original k source 221 symbols. 223 For yet other reliable IP multicast protocols the method to obtain 224 reliability is to generate enough encoding symbols so that each encoding 225 symbol is transmitted at most once. For example, the sender can decide 226 a priori how many encoding symbols it will transmit, use an FEC code to 227 generate that number of encoding symbols from the object, and then 228 transmit the encoding symbols to all receivers. This method is for 229 example applicable to streaming protocols, where the stream is 230 partitioned into objects, the source symbols for each object are encoded 231 into encoding symbols using an FEC code, and then the sets of encoding 232 symbols for each object are transmitted one after the other using IP 233 multicast. 235 ^L 236 2. FEC Codes 238 2.1. Simple codes 240 There are some very simple codes that are effective for repairing packet 241 loss under very low loss conditions. For example, one simple way to 242 provide protection from a single loss is to partition the object into 243 fixed size source symbols and then add a redundant symbol that is the 244 parity (XOR) of all the source symbols. The size of a source symbol is 245 chosen so that it fits perfectly into the payload of a packet, i.e. if 246 the packet payload is 512 bytes then each source symbol is 512 bytes. 247 The header of each packet contains enough information to identify the 248 payload. In this case, this includes a symbol ID. The symbol IDs are 249 numbered consecutively starting from zero independently for the source 250 symbols and for the redundant symbol. Thus, the packet header also 251 contains an encoding flag that indicates whether the symbol in the 252 payload is a source symbol or a redundant symbol, where 1 indicates 253 source symbol and 0 indicates redundant symbol. For example, if the 254 object consists of four source symbols that have values a, b, c and d, 255 then the value of the redundant symbol is e = a XOR b XOR c XOR d. 256 Then, the packets carrying these symbols look like 257 (0, 1: a), (1, 1: b), (2, 1: c), (3, 1: d), (0, 0: e). 259 In this example, the first two fields are in the header of the packet, 260 where the first field is the symbol ID and the second field is the 261 encoding flag. The portion of the packet after the colon is the 262 payload. Any single symbol of the object can be recovered as the parity 263 of all the other symbols. For example, if packets 264 (0, 1: a), (1, 1: b), (3, 1: d), (0, 0: e) 266 are received then the symbol value for the missing source symbol with ID 267 2 can be recovered by computing a XOR b XOR d XOR e = c. 269 When the number of source symbols in the object is large, a simple block 270 code variant of the above can be used. In this case, the source symbols 271 are grouped together into source blocks of some number k of consecutive 272 symbols each, where k may be different for different blocks. If a block 273 consists of k source symbols then a redundant symbol is added to form an 274 encoding block consisting of k+1 encoding symbols. Then, a source block 275 consisting of k source symbols can be recovered from any k of the k+1 276 encoding symbols from the associated encoding block. 278 Slightly more sophisticated ways of adding redundant symbols using 279 parity can also be used. For example, one can group a block consisting 280 of k source symbols in an object into a p x p square matrix, where p = 281 sqrt(k). Then, for each row a redundant symbol is added that is the 282 parity of all the source symbols in the row. Similarly, for each column 284 ^L 285 a redundant symbol is added that is the parity of all the source symbols 286 in the column. Then, any row of the matrix can be recovered from any p 287 of the p+1 symbols in the row, and similarly for any column. Higher 288 dimensional product codes using this technique can also be used. 289 However, one must be wary of using these constructions without some 290 thought towards the possible loss patterns of symbols. Ideally, the 291 property that one would like to obtain is that if k source symbols are 292 encoded into n encoding symbols (the encoding symbols consist of the 293 source symbols and the redundant symbols) then the k source symbols can 294 be recovered from any k of the n encoding symbols. Using the simple 295 constructions described above does not yield codes that come close to 296 obtaining this ideal behavior. 298 2.2. Small block FEC codes 300 Reliable IP multicast protocols may use a block (n, k) FEC code [2]. A 301 popular example of these types of codes is a class of Reed-Solomon 302 codes. For such codes, k source symbols are encoded into n > k encoding 303 symbols, such that any k of the encoding symbols can be used to 304 reassemble the original k source symbols. Thus, these codes have 0% 305 reception overhead when used to encode the entire object directly. 306 Block codes are usually systematic, which means that the n encoding 307 symbols consist of the k source symbols and n-k redundant symbols 308 generated from these k source symbols, where the size of a redundant 309 symbol is the same as that for a source symbol. For example, the first 310 simple code (XOR) described in the previous subsection is a (k+1, k) 311 code. In general, the freedom to choose n larger than k+1 is desirable, 312 as this can provide much better protection against losses. Codes of 313 this sort are often based on algebraic methods using finite fields. 314 Some of the most popular such codes are based on linear block codes. 315 Implementations of (n, k) FEC erasure codes are efficient enough to be 316 used by personal computers [16]. For example, [15] describes an 317 implementation where the encoding and decoding speeds decay as C/j, 318 where the constant C is on the order of 10 to 80 Mbytes/second for 319 Pentium class machines of various vintages and j is upper bounded by 320 min(k, n-k). 322 In practice, the values of k and n must be small (below 256) for such 323 FEC codes as large values make encoding and decoding prohibitively 324 expensive. As many objects are longer than k symbols for reasonable 325 values of k and the symbol length (e.g. larger than 16 kilobyte for k = 326 16 using 1 kilobyte symbols), they can be divided into a number of 327 source blocks. Each source block consists of some number k of source 328 symbols, where k may vary between different source blocks. The FEC 329 encoder is used to encode a k source symbol source block into a n 330 encoding symbol encoding block, where the length n of the encoding block 331 may vary for each source block. For a receiver to completely recover 333 ^L 334 the object, for each source block consisting of k source symbols, k 335 distinct encoding symbols (i.e., with different symbol IDs) must be 336 received from the corresponding encoding block. For some encoding 337 blocks, more encoding symbols may be received than there are source 338 symbols in the corresponding source block, in which case any additional 339 encoding symbols are discarded. An example encoding structure is shown 340 in Figure 1. 342 | source symbols | source symbols | 343 | of source block 0 | of source block 1 | 344 | | 345 v v 346 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 347 |0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 | 348 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 349 | 350 FEC encoder 351 | 352 v 353 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 354 |0 |1 |2 |3 | 4| 5| 6| 7| 8| 9| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 355 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 356 ^ ^ 357 | | 358 | encoding symbols | encoding symbols | 359 | of encoding block 0 | of encoding block 1 | 361 Figure 1. Encoding structure for object divided into two source 362 blocks consisting of 8 source symbols each, and the FEC encoder is used to 363 generate 2 additional redundant symbols (10 encoding symbols in total) 364 for each of the two source blocks. 366 In many cases, an object is partitioned into equal length source blocks 367 each consisting of k contiguous source symbols of the object, i.e., 368 block c consists of the range of source symbols [ck, (c+1)k-1]. This 369 ensure that the FEC encoder can be optimized to handle a particular 370 number k of source symbols. This also ensures that memory references 371 are local when the sender reads source symbols to encode, and when the 372 receiver reads encoding symbols to decode. Locality of reference is 373 particularly important when the object is stored on disk, as it reduces 374 the disk seeks required. The block number and the source symbol ID 375 within that block can be used to uniquely specify a source symbol within 376 the object. If the size of the object is not a multiple of k source 377 symbols, then the last source block will contain less than k symbols. 379 ^L 380 Encoding symbols can be uniquely identified by block number and encoding 381 symbol ID. The block numbers can be numbered consecutively starting 382 from zero. One way of identifying encoding symbols within a block are 383 to use symbol IDs and an encoding flag that is used to specify whether 384 an encoding symbol is a source symbol or a redundant symbol, where for 385 example 1 indicates source symbol and 0 indicate redundant symbol. The 386 symbol IDs can be numbered consecutively starting from zero for each 387 block independently for the source symbols and for the redundant 388 symbols. Thus, an encoding symbol can be identified by its block 389 number, the encoding flag, and the symbol ID. For example, if the 390 object consists 10 source symbols with values a, b, c, d, e, f, g, h, i, 391 and j, and k = 5 and n = 8, then there are two source blocks consisting 392 of 5 symbols each, and there are two encoding blocks consisting of 8 393 symbols each. Let p, q and r be the values of the redundant symbols for 394 the first encoding block, and let x, y and z be the values of the 395 redundant symbols for the second encoding block. Then the encoding 396 symbols together with their identifiers are 398 (0, 0, 1: a), (0, 1, 1: b), (0, 2, 1: c), (0, 3, 1: d), (0, 4, 1: e), 399 (0, 0, 0: p), (0, 1, 0: q), (0, 2, 0: r), 400 (1, 0, 1: f), (1, 1, 1: g), (1, 2, 1: h), (1, 3, 1: i), (1, 4, 1: j), 401 (1, 0, 0: x), (1, 1, 0: y), (1, 2, 0: z). 403 In this example, the first three fields identify the encoding symbol, 404 where the first field is the block number, the second field is the 405 symbol ID and the third field is the encoding flag. The value of the 406 encoding symbol is written after the colon. Each block can be recovered 407 from any 5 of the 8 encoding symbols associated with that block. For 408 example, reception of 410 (0, 1, 1: b), (0, 2, 1: c), (0, 3, 1: d), (0, 0, 0: p), (0, 1, 0: q) 412 is sufficient to recover the first source block, and reception of 414 (1, 0, 1: f), (1, 1, 1: g), (1, 0, 0: x), (1, 1, 0: y), (1, 2, 0: z) 416 is sufficient to recover the second source block. 418 2.3. Large block FEC codes 420 Tornado codes [9] are block FEC codes that provide an alternative to 421 small block FEC codes. An (n, k) Tornado code requires slightly more 422 than k out of n encoding symbols to reassemble k source symbols. 423 However, the advantage is that the value of k may be on the order of 424 tens of thousands and still run efficiently. Because of memory 426 ^L 427 considerations, in practice the value of n is restricted to be a small 428 multiple of k, e.g., n = 2k. For example, [3] describes an 429 implementation of Tornado codes where the encoding and decoding speeds 430 are tens of megabytes per second range for Pentium class machines of 431 various vintages when k is in the tens of thousands and n = 2k. The 432 reception overhead for such values of k and n is in the 5-10% range. 433 Tornado codes require a large amount of out of band information to be 434 communicated to all senders and receivers for each different object 435 length, and require an amount of memory on the encoder and decoder which 436 is proportional to the object length times 2n/k. 438 Tornado codes are designed to have low reception overhead on average 439 with respect to reception of a random portion of the encoding packets. 440 Thus, to ensure that a receiver can reassemble the object with low 441 reception overhead, the packets are permuted into a random order before 442 transmission. 444 2.4. Expandable FEC codes 446 All of the FEC codes described up to this point are block codes. There 447 is a different type of FEC codes that we call expandable FEC codes. 448 Like block codes, an expandable FEC encoder operates on an object of 449 known size that is partitioned into equal length source symbols. Unlike 450 block codes, ideally there is no predetermined number of encoding 451 symbols that can be generated for expandable FEC codes. Instead, an 452 expandable FEC encoder can generate as few or as many unique encoding 453 symbols as required on demand. Also unlike block codes, optimal 454 expandable FEC codes have the additional attractive property that 455 encoding symbols for the same object can be generated and transmitted 456 from multiple servers and concurrently received by a receiver and yet 457 the receiver incurs a 0% reception overhead. 459 LT codes [11] are an example of large expandable FEC codes. An LT 460 encoder uses randomization to generate each encoding symbol randomly and 461 independently of all other encoding symbols. Like Tornado codes, the 462 number of source symbols k may be very large for LT codes, i.e., on the 463 order of tens to hundreds of thousands, and the encoder and decoder run 464 efficiently in software. For example the encoding and decoding speeds 465 for LT codes are in the range 3-20 megabytes per second for Pentium 466 class machines of various vintages when k is in the high tens of 467 thousands. An LT encoder closely approximates the properties of an 468 ideal expandable FEC encoder, as it can generate as few or as many 469 encoding symbols as required on demand. When a new encoding symbol is 470 to be generated by an LT encoder, it is based on a randomly chosen 471 32-bit encoding symbol ID that uniquely describes how the encoding 472 symbol is to be generated from the input symbols. In general, each 473 encoding symbol ID value corresponds to a unique encoding symbol, and 475 ^L 476 thus the space of possible encoding symbols is approximately four 477 billion. Thus, the chance that a particular encoding symbol is the same 478 as any other particular encoding symbol is tiny. An LT decoder has the 479 property that with very high probability the receipt of any set of 480 slightly more than k randomly and independently generated encoding 481 symbols is sufficient to reassemble the k source symbols. For example, 482 when k is on the order of tens to hundreds of thousands the reception 483 overhead is less than 5% with no failures in tens of millions of trials 484 under a variety of loss conditions. 486 Because encoding symbols are randomly and independently generated by 487 choosing random encoding symbol IDs, LT codes have the property that 488 encoding symbols for the same k source symbols can be generated and 489 transmitted from multiple senders ad than if all the encoding symbols 490 were generated by a single sender. The only requirement is that the 491 senders choose their encoding symbol IDs randomly and independently of 492 one another. 494 There is a weak tradeoff between the number of source symbols and the 495 reception overhead for LT codes, and the larger the number of source 496 symbols the smaller the reception overhead. Thus, for shorter objects, 497 it is sometimes advantageous to include multiple symbols in each packet. 498 Normally, and in the discussion below, there is only one symbol per 499 packet. 501 There are a couple of factors for choosing the appropriate symbol 502 length/ number of input symbols tradeoff. The primary consideration is 503 that there is a fixed overhead per symbol component in the overall 504 processing requirements of the encoding and decoding, independent of the 505 number of input symbols. Thus, using shorter symbols means that this 506 fixed overhead processing per symbol will be a larger component of the 507 overall processing requirements, leading to larger overall processing 508 requirements. Because of this, it is advisable to use a reasonably 509 sized fixed symbol length independent of the length of the object, and 510 thus shorter objects will be partitioned into fewer symbols than larger 511 objects. A second much less important consideration is that there is a 512 component of the processing per symbol that depends logarithmically on 513 the number of input symbols, and thus for this reason there is a slight 514 preference towards less input symbols. 516 Like small block codes, there is a point when the object is large enough 517 that it makes sense to partition it into blocks when using LT codes. 518 Generally the object is partitioned into blocks whenever the number of 519 source symbols times the packet payload length is less than the size of 520 the object. Thus, if the packet payload is 1024 bytes and the number of 521 source symbols is 64,000 then any object over 64 megabytes will be 522 partitioned into more than one block. One can choose the number of 523 source symbols to partition the object into, depending on the desired 525 ^L 526 encoding and decoding speed versus reception overhead tradeoff desired. 527 Encoding symbols can be uniquely identified by a block number (when the 528 object is large enough to be partitioned into more than one block) and 529 an encoding symbol ID. The block numbers, if they are used, are 530 generally numbered consecutively starting from zero within the object. 531 The block number and the encoding symbol ID are both chosen uniformly 532 and randomly from their range when an encoding symbol is to be generated 533 and transmitted. For example, suppose the number of source symbols is 534 64,000 and the number of blocks is 2. Then, each packet generated by 535 the LT encoder could be of the form (b, x: y). In this example, the 536 first two fields identify the encoding symbol, where the first field is 537 the block number b = 0 or 1 and the second field is the randomly chosen 538 encoding symbol ID x. The value y after the colon is the value of the 539 encoding symbol. 541 2.5. Source blocks with variable length source symbols 543 For all the FEC codes described above, all the source symbols in the 544 same source block are all of the same length. In this section, we 545 describe a general technique to handle the case when it is desirable to 546 use source symbols of varying lengths in a single source block. This 547 technique is applicable to block FEC codes. 549 Let l_1, l_2, ... , l_k be the lengths of k varying length source 550 symbols to be considered part of the same source block. Let lmax be the 551 maximum over i = 1, ... , k of l_i. To prepare the source block for the 552 FEC encoder, pad each source symbol i out to length lmax with a suffix 553 of lmax-i zeroes, and then prepend to the beginning of this the value 554 l_i. Thus, each padded source symbol is of length x+lmax, assuming that 555 the length of an original symbol takes x bytes to store. These padded 556 source symbols, each of length x+lmax, are the input to the encoder, 557 together with the value n. The encoder then generates n-k redundant 558 symbols, each of length x+lmax. 560 The encoding symbols that are placed into packets consist of the 561 original k varying length source symbols and n-k redundant symbols, each 562 of length x+lmax. From any k of the received encoding symbols, the FEC 563 decoder recreates the k original source symbols as follows. If all k 564 original source symbols are received, then no decoding is necessary. 565 Otherwise, at least one redundant symbol is received, from which the 566 receiver can easily whether the block was composed of variable-length 567 source symbols: if the redundant simbol(s) has a size different (larger) 568 from the source symbols then the source symbols are variable-length. 569 Note that in a variable-length block the redundant symbols are always 570 larger than the largest source symbol, due to the presence of the 571 encoded symbol-length. The receiver can determine the value of lmax by 572 subtracting x from the length of a received redundant symbol. Note that 574 ^L 575 x MUST be a protocol constant. For each of the received original source 576 symbols, the receiver can generate the corresponding padded source 577 symbol as described above. Then, the input to the FEC decoder is the 578 set of received redundant symbols, together with the set of padded 579 source symbols constructed from the received original symbols. The FEC 580 decoder then produces the set of k padded source symbols. Once the k 581 padded source symbols have been recovered, the length l_i of original 582 source symbol i can be recovered from the first x bytes of the ith 583 padded source symbol, and then original source symbol i is obtained by 584 taking the next l_i bytes following the x bytes of the length field. 586 3. Security Considerations 588 The use of FEC, in and of itself, imposes no additional security 589 considerations versus sending the same information without FEC. 590 However, just like for any transmission system, a malicious sender may 591 intentionally transmit bad symbols. If a receiver accepts one or more 592 bad symbols in place of authentic ones then such a receiver will have 593 its entire object down-load corrupted by the bad symbol. Application- 594 level transmission object authentication can detect the corrupted 595 transfer, but the receiver must then discard the transferred object. 596 Thus, transmitting false symbols is at least an effective denial of 597 service attack. At worst, a malicious sender could add, delete, or 598 replace arbitrary data within the transmitted object. 600 In light of this possibility, FEC receivers may screen the source 601 address of a received symbol against a list of authentic transmitter 602 addresses. Since source addresses may be spoofed, FEC transport 603 protocols may provide mechanisms for robust source authentication of 604 each encoded symbol. Multicast routers along the path of a FEC transfer 605 may provide the capability of discarding multicast packets that 606 originated on that subnet, and whose source IP address does not 607 correspond with that subnet. 609 4. Intellectual Property Disclosure 611 Tornado codes [9] have both patents issued and patents pending. LT 612 codes [11] have patents pending. 614 5. Acknowledgments 616 Thanks to Vincent Roca and Hayder Radha for their detailed comments on 617 this draft. 619 ^L 620 6. References 622 [1] Acharya, S., Franklin, M., and Zdonik, S., ``Dissemination- Based 623 Data Delivery Using Broadcast Disks'', IEEE Personal Communications, 624 pp.50-60, Dec 1995. 626 [2] Blahut, R.E., ``Theory and Practice of Error Control Codes'', 627 Addison Wesley, MA 1984. 629 [3] Byers, J.W., Luby, M., Mitzenmacher, M., and Rege, A., ``A Digital 630 Fountain Approach to Reliable Distribution of Bulk Data'', Proceedings 631 ACM SIGCOMM '98, Vancouver, Canada, Sept 1998. 633 [4] Deering, S., ``Host Extensions for IP Multicasting'', RFC 1058, 634 Stanford University, Stanford, CA, 1988. 636 [5] Luby, M., Vicisano, Gemmell, J., L., Rizzo, L., Handley, M., 637 Crowcroft, J., "RMT BB Forward Error Correction Codes", draft-ietf-rmt- 638 bb-fec-01 submited to the IETF RMT working group, November 2000. 640 [6] Gemmell, J., Schooler, E., and Gray, J., ``ALC Scalable Multicast 641 File Distribution: Caching and Parameters Optimizations'' Technical 642 Report MSR-TR-99-14, Microsoft Research, Redmond, WA, April, 1999. 644 [7] Handley, M., and Jacobson, V., ``SDP: Session Description 645 Protocol'', RFC 2327, April 1998. 647 [8] Handley, M., ``SAP: Session Announcement Protocol'', Internet Draft, 648 IETF MMUSIC Working Group, Nov 1996. 650 [9] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D., Stemann, 651 V., ``Practical Loss-Resilient Codes'' 29th STOC'97. 653 [10] Luby, M., Vicisano, L., Speakman, T. ``Heterogeneous multicast 654 congestion control based on router packet filtering'', presented at RMT 655 meeting in Pisa, March 1999. 657 [11] Digital Fountain Web Site, www.digitalfountain.com 659 [12] Fielding, R., Gettys, J., Mogul, J. Frystyk, H., Berners-Lee, T., 660 Hypertext Transfer Protocol HTTP/1.1 (IETF RFC2068) http://www.rfc- 661 editor.org/rfc/rfc2068.txt 663 [13] Bradner, S., Key words for use in RFCs to Indicate Requirement 664 Levels (IETF RFC 2119) http://www.rfc-editor.org/rfc/rfc2119.txt 666 [14] Rizzo, L, and Vicisano, L., ``Reliable Multicast Data Distribution 667 protocol based on software FEC techniques'', Proceedings of the Fourth 669 ^L 670 IEEE Workshop on the Architecture and Implementation of High Performance 671 Communication Systems, HPCS-97, Chalkidiki, Greece, June 1997. 673 [15] Rizzo, L., ``Effective Erasure Codes for Reliable Computer 674 Communication Protocols'', ACM SIGCOMM Computer Communication Review, 675 Vol.27, No.2, pp.24-36, Apr 1997. 677 [16] Rizzo, L., ``On the Feasibility of Software FEC'', DEIT Tech 678 Report, http://www.iet.unipi.it/~luigi/softfec.ps, Jan 1997. 680 [17] Rubenstein, Dan, Kurose, Jim and Towsley, Don, ``The Impact of 681 Multicast Layering on Network Fairness'', Proceedings of ACM SIGCOMM'99. 683 [18] L.Vicisano, L.Rizzo, J.Crowcroft, ``TCP-like Congestion Control for 684 Layered Multicast Data Transfer'', IEEE Infocom '98, San Francisco, CA, 685 Mar.28-Apr.1 1998. 687 [19] Vicisano, L., ``Notes On a Cumulative Layered Organization of Data 688 Packets Across Multiple Streams with Different Rates'', University 689 College London Computer Science Research Note RN/98/25, Work in Progress 690 (May 1998). 692 7. Authors' Addresses 694 Michael Luby 695 luby@digitalfountain.com 696 Digital Fountain 697 600 Alabama Street 698 San Francisco, CA, USA, 94110 700 Lorenzo Vicisano 701 lorenzo@cisco.com 702 cisco Systems, Inc. 703 170 West Tasman Dr., 704 San Jose, CA, USA, 95134 706 Jim Gemmell 707 jgemmell@microsoft.com 708 Microsoft Research 709 301 Howard St., #830 710 San Francisco, CA, USA, 94105 712 Luigi Rizzo 713 luigi@iet.unipi.it 714 ACIRI, 1947 Center St., Berkeley CA 94704 715 and 716 Dip. di Ing. dell'Informazione 718 ^L 719 Universita` di Pisa 720 via Diotisalvi 2, 56126 Pisa, Italy 722 Mark Handley 723 mjh@aciri.org 724 ACIRI 725 1947 Center St. 726 Berkeley CA, USA, 94704 728 Jon Crowcroft 729 J.Crowcroft@cs.ucl.ac.uk 730 Department of Computer Science 731 University College London 732 Gower Street, 733 London WC1E 6BT, UK 735 ^L 737 8. Full Copyright Statement 739 Copyright (C) The Internet Society (2000). All Rights Reserved. 741 This document and translations of it may be copied and furnished to 742 others, and derivative works that comment on or otherwise explain it or 743 assist in its implementation may be prepared, copied, published and 744 distributed, in whole or in part, without restriction of any kind, 745 provided that the above copyright notice and this paragraph are included 746 on all such copies and derivative works. However, this document itself 747 may not be modified in any way, such as by removing the copyright notice 748 or references to the Internet Society or other Internet organizations, 749 except as needed for the purpose of developing Internet standards in 750 which case the procedures for copyrights defined in the Internet 751 languages other than English. 753 The limited permissions granted above are perpetual and will not be 754 revoked by the Internet Society or its successors or assigns. 756 This document and the information contained herein is provided on an "AS 757 IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK 758 FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT 759 LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT 760 INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR 761 FITNESS FOR A PARTICULAR PURPOSE." 763 ^L