idnits 2.17.1 draft-ietf-rmt-bb-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: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** 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 are 7 instances of too long lines in the document, the longest one being 3 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 -- 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 (8 March 2000) is 8815 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 215, but not defined == Missing Reference: 'NON97' is mentioned on line 231, but not defined == Missing Reference: 'Riz97b' is mentioned on line 231, but not defined == Unused Reference: 'BLA94' is defined on line 486, but no explicit reference was found in the text == Unused Reference: 'DEE88' is defined on line 493, but no explicit reference was found in the text == Unused Reference: 'GEM99' is defined on line 496, but no explicit reference was found in the text == Unused Reference: 'HAN98' is defined on line 501, but no explicit reference was found in the text == Unused Reference: 'HAN96' is defined on line 504, but no explicit reference was found in the text == Unused Reference: 'LUB99' is defined on line 510, but no explicit reference was found in the text == Unused Reference: 'R2068' is defined on line 514, but no explicit reference was found in the text == Unused Reference: 'R2119' is defined on line 518, but no explicit reference was found in the text == Unused Reference: 'RIZ97a' is defined on line 521, but no explicit reference was found in the text == Unused Reference: 'RIZ97b' is defined on line 527, but no explicit reference was found in the text == Unused Reference: 'RUB99' is defined on line 534, but no explicit reference was found in the text == Unused Reference: 'VIC98A' is defined on line 537, but no explicit reference was found in the text == Unused Reference: 'VIC98B' is defined on line 541, 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' ** 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 (~~), 18 warnings (==), 15 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 RMT Working Group M. Luby 2 INTERNET DRAFT L. Vicisano 3 Expires 8 September 2000 L. Rizzo 4 J. Gemmell 5 J. Crowcroft 6 B. Lueckenhoff 7 8 March 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 draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "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 Copyright Notice 36 Copyright (C) The Internet Society (2000). All Rights Reserved. 38 Abstract 40 This memo describes the use of Forward Error Correction (FEC) codes 41 within the context of reliable IP multicast transport and provides an 42 introduction to some commonly-used FEC codes. 44 1. Rationale and Overview 45 There are many ways to provide reliability for transmission proto- 46 cols. A common method is to use ARQ, automatic request for 47 retransmission. With ARQ, receivers use a back channel to the sender 48 to send requests for retransmission of lost packets. ARQ works well 49 for one-to-one reliable protocols, as evidenced by the pervasive suc- 50 cess of TCP/IP. ARQ has also been an effective reliability tool for 51 one-to-many reliability protocols, and in particular for some reli- 52 able IP multicast protocols. However, for one-to-very many reliabil- 53 ity protocols, ARQ has limitations, including the feedback implosion 54 problem because many receivers are transmitting back to the sender, 55 and the need for a back channel to send these requests from the 56 receiver. Another limitation is that receivers may experience dif- 57 ferent loss patterns of packets, and thus receivers may be delayed by 58 retransmission of packets that other receivers have lost that but 59 they have already received. This may also cause wasteful use of 60 bandwidth used to retransmit packets that have already been received 61 by many of the receivers. 63 In environments where ARQ is either costly or impossible because 64 there is either a very limited capacity back channel or no back chan- 65 nel at all, such as satellite transmission, a Data Carousel approach 66 to reliability is sometimes used [AFZ95]. With a Data Carousel, the 67 sender partitions the object into equal length source symbols, places 68 them into packets, and then continually cycles through and sends 69 these packets. Receivers continually receive packets until they have 70 received a copy of each packet. Data Carousel has the advantage that 71 it requires no back channel because there is no data that flows from 72 receivers to the sender. However, Data Carousel also has limita- 73 tions. For example, if a receiver loses a packet in one round of 74 transmission it must wait an entire round before it has a chance to 75 receive that packet again. This may also cause wasteful use of 76 bandwidth, as the sender continually cycles through and transmits the 77 packets until no receiver is missing a packet. 79 FEC codes provide a reliability method that can be used to augment or 80 replace other reliability methods, especially for one-to-many relia- 81 bility protocols such as reliable IP multicast. Ideally, FEC codes 82 in the context of IP multicast can be used to encode an object into 83 packets in such a way that each received packet is fully useful to a 84 receiver to reassemble the object regardless of previous packet 85 reception patterns. Thus, if some packets are lost in transit between 86 the sender and the receiver, instead of asking for retransmission 87 using ARQ or waiting till the packets are resent using Data Carousel, 88 the receiver can use any other subsequent equal number of packets 89 that arrive to reassemble the object. This implies that the same 90 packet is fully useful to all receivers to reassemble the object, 91 even though the receivers may have previously experienced different 92 packet loss patterns. This property can reduce or even eliminate the 93 problems mentioned above associated with ARQ and Data Carousel and 94 thereby dramatically increase the scalability of the protocol to ord- 95 ers of magnitude more receivers. 97 For some reliable IP multicast protocols, FEC codes are used in con- 98 junction with ARQ to provide reliability. For example, in a first 99 round all of the source symbols could be transmitted, and then 100 receivers could report back to the sender the number of symbols they 101 are missing from each block. Then, the sender could compute the max- 102 imum number of missing symbols from each block among all receivers, 103 and then transmit that number of redundant symbols for each block. 104 In this case, even if different receivers are missing different sym- 105 bols in different blocks, transmitted redundant symbols for a given 106 block are useful to all receivers missing symbols from that block. 108 For others, FEC codes are used in a Data Carousel fashion to provide 109 reliability, by cycling through and transmitting the encoding symbols 110 instead of the source symbols. For example, suppose an FEC code is 111 applied to the entire object consisting of k source symbols to gen- 112 erate n encoding symbols with the property that the entire object can 113 be reassembled from any k encoding symbols, and the sender cycles 114 through and transmits the n encoding symbols in the same order in 115 each round. Then, a receiver can join the transmission at any point 116 in time, and as long as the receiver receives at least k encoding 117 symbols during the transmission of n encoding symbols then the 118 receiver can completely recover the object. This is true even if the 119 receiver joins the data carousel in the middle of a round. 121 For yet other reliable IP multicast protocols the sole method to 122 obtain reliability is to use FEC codes. For example, the sender can 123 decide a priori how many encoding symbols it will transmit, use an 124 FEC code to generate that number of encoding symbols from the object, 125 and then transmit the encoding symbols to all receivers. This method 126 is for example applicable to streaming protocols, where the stream is 127 partitioned into objects, each object is encoded into encoding sym- 128 bols using an FEC code, and then the sets of encoding symbols for 129 each object are transmitted one after the other using IP multicast. 130 The large on demand codes described below have the property that the 131 FEC encoder can generate sequentially as many encoding symbols as are 132 desired on demand. Thus, reliable IP multicast protocols that use 133 large on demand codes generally rely solely on these codes for relia- 134 bility. 136 In the general literature, FEC refers to the ability to overcome both 137 erasures (losses) and bit-level corruption. However, in the case of 138 IP multicast, lower network layers will detect corrupted packets and 139 discard them. Therefore, an IP multicast protocol need not be con- 140 cerned with corruption; the focus is solely on erasure codes. The 141 payloads are generated and processed using an FEC erasure encoder and 142 objects are reassembled from reception of packets using the 143 corresponding FEC erasure decoder. 145 The primary purpose of using FEC codes is to ensure that minimal 146 number of packets need be received in order for a receiver to 147 reassemble an object. Reception overhead is used to measure how 148 close a protocol comes to achieving this minimum. Reception overhead 149 is the aggregate length of packets needed to recover the object 150 beyond the object length, measured as a percentage of the object 151 length. For example, if it takes 15 MB of packets in order to 152 recover a 10 MB object, then the reception overhead is (15 10)/10 153 times 100, or 50%. The minimal reception overhead possible is 0%. 155 2. FEC Codes 157 2.1. Simple codes 159 There are some very simple codes that are effective for repairing 160 packet loss under very low loss conditions. For example, one simple 161 way to provide protection from a single loss is to partition the 162 object into fixed size source symbols and then add a redundant symbol 163 that is the parity (XOR) of all the source symbols. The size of a 164 source symbol is chosen so that it fits perfectly into the payload of 165 a packet, i.e. if the packet payload is 512 bytes then each source 166 symbol is 512 bytes. The header of each packet contains enough 167 information to identify the payload. In this case, this includes a 168 symbol ID. The symbol IDs are numbered consecutively starting from 169 zero independently for the source symbols and for the redundant sym- 170 bol. Thus, the packet header also contains an encoding flag that 171 indicates whether they symbol in the payload is a source symbol or a 172 redundant symbol, where 1 indicates source symbol and 0 indicates 173 redundant symbol. For example, if the object consists of four source 174 symbols that have values a, b, c and d, then the value of the redun- 175 dant symbol is e = a XOR b XOR c XOR d. Then, the packets carrying 176 these symbols look like (0, 1: a), (1, 1: b), (2, 1: c), (3, 1: d), 177 (0, 0: e). In this example, the first two fields are in the header 178 of the packet, where the first field is the symbol ID and the second 179 field is the encoding flag. The portion of the packet after the 180 colon is the payload. Any single symbol of the object can be 181 recovered as the parity of all the other symbols. For example, if 182 packets (0, 1: a), (1, 1: b), (3, 1: d), (0, 0: e) are received then 183 the symbol value for the missing source symbol with ID 2 can be 184 recovered by computing a XOR b XOR d XOR e = c. 186 When the number of source symbols in the object is large, a simple 187 block code variant of the above can be used. In this case, the 188 source symbols are grouped together into source blocks of k 189 consecutive symbols each, and then for each block of source symbols a 190 redundant symbol is added to form encoding blocks of k+1 symbols 191 each. Then, a source block can be recovered from any k of the k+1 192 symbols from the associated encoding block. 194 Slightly more sophisticated ways of adding redundant symbols using 195 parity can also be used. For example, one can group the k source sym- 196 bols in the object into a p x p square matrix, where p = sqrt(k). 197 Then, for each row a redundant symbol is added that is the parity of 198 all the source symbols in the row. Similarly, for each column a 199 redundant symbol is added that is the parity of all the source sym- 200 bols in the column. Then, Any row of the matrix can be recovered 201 from any p of the p+1 symbols in the row, and similarly for any 202 column. Higher dimensional product codes using this technique can 203 also be used. However, one must be wary of using these constructions 204 without some thought towards the possible loss patterns of symbols. 205 Ideally, the property that one would like to obtain is that if k 206 source symbols are encoded into n encoding symbols (the encoding sym- 207 bols consist of the source symbols and the redundant symbols) then 208 the k source symbols can be recovered from any k of the n encoding 209 symbols. Using the simple constructions described above does not 210 yield codes that come close to obtaining this ideal behavior. 212 2.2. Small block codes 214 Reliable IP multicast protocols may use a block (n, k) FEC erasure 215 code [BLA84]. A popular example of this types of codes is a class of 216 Reed-Solomon codes. For such codes, k source symbols are encoded into 217 n > k encoding symbols, such that any k of the encoding symbols can 218 be used to reassemble the original k source symbols. Thus, these 219 codes have 0% reception overhead when used to encode the entire 220 object directly. Block codes are usually systematic, which means 221 that the n encoding symbols consist of the k source symbols and n-k 222 redundant symbols generated from these k source symbols, where the 223 size of a redundant symbol is the same as that for a source symbol. 224 For example, the first simple code (XOR) described in the previous 225 subsection is a (k+1, k) code. In general, the freedom to choose n 226 larger than k+1 is desirable, as this can provide much better protec- 227 tion against losses. Codes of this sort are often based on alge- 228 braic methods using finite fields. Some of the most popular such 229 codes are based on linear block codes. Implementations of (n, k) 230 FEC erasure codes are efficient enough to be used by personal comput- 231 ers [RIZ97c, NON97]. For example, [Riz97b] describes an implementa- 232 tion where the encoding and decoding speeds decay as C/j, where the 233 constant C is on the order of 10 to 80 Mbytes/second for Pentium 234 class machines of various vintages and j is upper bounded by min(k, 235 n-k). 237 In practice, the values of k and n must be small for these codes as 238 large values make encoding and decoding prohibitively expensive. As 239 many objects are longer than k symbols for reasonable values of k and 240 the symbol length (e.g. larger than 16 KB for k = 16 using 1 KB sym- 241 bols), they are divided into m source blocks consisting of k source 242 symbols each. An erasure code is used to encode each source block 243 into an encoding block consisting of n encoding symbols. For a 244 receiver to completely recover the object, k distinct encoding sym- 245 bols (i.e., with different symbol IDs) must be received for each of 246 the encoding blocks. For some encoding blocks, more than k encoding 247 symbols may be received, in which case any additional encoding sym- 248 bols are discarded. An example encoding structure is shown in Figure 249 1. 251 | source symbols | source symbols | 252 | of source block 0 | of source block 1 | 253 | | 254 v v 255 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 256 |0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 | 257 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 258 | 259 encode 260 | 261 v 262 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 263 |0 |1 |2 |3 | 4| 5| 6| 7| 8| 9| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 264 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 265 ^ ^ 266 | | 267 | encoding symbols | encoding symbols | 268 | of encoding block 0 | of encoding block 1 | 270 Figure 1. Encoding structure for object divided into m = 2 source 271 blocks, k = 8 and n = 10 273 When using small block codes for objects that are larger than k 274 source symbols in length, the source symbols in the object are 275 assigned to blocks. Typically, each k contiguous source symbols of 276 the object is assigned to a block, i.e., block c consists of the 277 range of source symbols [ck, (c+1)k-1]. This ensures that memory 278 reference are local when the sender reads source symbols to encode, 279 and when the receiver reads encoding symbols to decode.Locality of 280 reference is particularly important when the object is stored on 281 disk, as it reduces the disk seeks required. 283 The block number and the source symbol ID within that block can be 284 used to uniquely specify a source symbol within the object. If the 285 size of the object is not a multiple of k source symbols, then the 286 last source block will contain less than k symbols. 288 Encoding symbols can be uniquely identified by block number and 289 encoding symbol ID. The block numbers can be numbered consecutively 290 starting from zero. One way of identifying encoding symbols within a 291 block are to use symbol IDs and an encoding flag that is used to 292 specify whether an encoding symbol is a source symbol or a redundant 293 symbol, where for example 1 indicates source symbol and 0 indicate 294 redundant symbol. The symbol IDs can be numbered consecutively 295 starting from zero for each block independently for the source sym- 296 bols and for the redundant symbols. Thus, an encoding symbol can be 297 identified by its block number, the encoding flag, and the symbol ID. 298 For example, if the object consists 10 source symbols with values a, 299 b, c, d, e, f, g, h, i, and j, and k = 5 and n = 8, then there are 300 two source blocks consisting of 5 symbols each, and there are two 301 encoding blocks consisting of 8 symbols each. Let p, q and r be the 302 values of the redundant symbols for the first encoding block, and let 303 x, y and z be the values of the redundant symbols for the second 304 encoding block. Then the encoding symbols together with their iden- 305 tifiers are (0, 0, 1:a), (0, 1, 1: b), (0, 2, 1: c), (0, 3, 1: d), 306 (0, 4, 1: e), (0, 0, 0: p), (0, 1, 0: q), (0, 2, 0: r), (1, 0, 1: f), 307 (1, 1, 1: g), (1, 2, 1: h), (1, 3, 1: i), (1, 4, 1: j), (1, 0, 0: x), 308 (1, 1, 0: y) and (1, 2, 0: z). In this example, the first three 309 fields identify the encoding symbol, where the first field is the 310 block number, the second field is the symbol ID and the third field 311 is the encoding flag. The value of the encoding symbol is written 312 after the colon. Each block can be recovered from any 5 of the 8 313 encoding symbols associated with that block. For example, reception 314 of (0, 1, 1: b), (0, 2, 1: c), (0, 3, 1: d), (0, 0, 0: p) and (0, 1, 315 0: q) are sufficient to recover the first source block and reception 316 of (1, 0, 1: f), (1, 1, 1: g), (1, 0, 0: x), (1, 1, 0: y) and (1, 2, 317 0: z) are sufficient to recover the second source block. 319 2.3. Large block codes 321 Tornado codes [LUB97] are block FEC erasure codes that provide an 322 alternative to small block codes. A (n, k) Tornado code requires 323 slightly more than k out of n encoding symbols to reassemble k source 324 symbols. However, the advantage is that the value of k may be on the 325 order of tens of thousands and still run efficiently. Because of 326 memory considerations, in practice the value of n is restricted to be 327 a small multiple of k, e.g., n = 2k. For example, [BYE98] describes 328 an implementation of Tornado codes where the encoding and decoding 329 speeds are proportional to 10 Mbytes/second to 80 Mbytes/second for 330 Pentium class machines of various vintages when k is in the tens of 331 thousands and n = 2k. The reception overhead for such values of k 332 and n is in the 5-10% range. Tornado codes require a large amount of 333 out of band information to be communicated to all senders and 334 receivers for each different object length, and require an amount of 335 memory on the encoder and decoder which is proportional to the object 336 length times 2n/k. 338 Tornado codes are designed to have low reception overhead on average 339 with respect to reception of a random portion of the encoding pack- 340 ets. Thus, to ensure that a receiver can reassemble the object with 341 low reception overhead, the packets are permuted into a random order 342 before transmission. 344 2.4. On demand codes 346 All of the FEC erasure codes described up to this point are block 347 codes. There is a different type of FEC erasure code that we call on 348 demand codes. Like block codes, an on demand encoder operates on an 349 object of known size that is partitioned into equal length source 350 symbols. Unlike block codes, there is no predetermined number of 351 encoding symbols that can be generated for on demand codes. 352 Instead, an on demand encoder can generate as few or as many encoding 353 symbols as required on demand. Also unlike block codes, optimal on 354 demand codes have the additional attractive property that encoding 355 symbols for the same object can be generated and transmitted from 356 multiple servers and concurrently received by a receiver and yet the 357 receiver incurs a 0% reception overhead. 359 LT codes are an example of a large on demand FEC code. An LT encoder 360 uses randomization to generate each encoding symbol randomly and 361 independently of all other encoding symbols. An LT encoder satisfies 362 the on demand property, as it can generate as few or as many encoding 363 symbols as required on demand. Let k be the number of source symbols 364 that the object is partitioned into. An LT decoder has the property 365 that with very high probability the receipt of any set of slightly 366 more than k encoding symbols is sufficient to reassemble the object. 367 Like Tornado codes, the value of k may be very large, i.e., on the 368 order of tens or hundreds of thousands, and the encoder and decoder 369 run efficiently in software. For example the encoding and decoding 370 speeds for LT codes are proportional to 3 Mbytes/second to 20 371 Mbytes/second for Pentium class machines of various vintages when k 372 is in the high tens of thousands. The reception overhead for such 373 values of k is in the 2-4% range. 375 When a new encoding symbol is to be generated, it is based on a key 376 that uniquely describes how the encoding symbol is to be generated. 377 Because encoding symbols are randomly and independently generated, LT 378 codes have the property that encoding symbols for the same object can 379 be generated and transmitted from multiple servers and concurrently 380 received by a receiver with no more reception overhead than if all 381 the encoding symbols were generated by a single sender. 383 There is a tradeoff between the number of source symbols and the 384 reception overhead, and the larger the number of source symbols the 385 smaller the reception overhead. Thus, for shorter objects, it is 386 sometimes advantageous to include multiple symbols in each packet. 387 Normally, and in the discussion below, there is only one symbol per 388 packet. 390 Like small block codes, there is a point when the object is large 391 enough that it makes sense to partition it into blocks when using LT 392 codes. Generally the object is partitioned into blocks whenever the 393 number of source symbols times the packet payload length is less than 394 the size of the object. Thus, if the packet payload is 1024 bytes 395 and the number of source symbols is 64,000 then any object over 64 MB 396 will be partitioned into more than one block. One can choose the 397 number of source symbols to partition the object into, depending on 398 the desired encoding and decoding speed versus reception overhead 399 tradeoff desired. Encoding symbols can be uniquely identified by a 400 block number (when the object is large enough to be partitioned into 401 more than one block) and an encoding symbol ID. The block numbers, 402 if they are used, are generally numbered consecutively starting from 403 zero within the object. The range of possible values for an encoding 404 symbol ID is orders of magnitude larger than the number of source 405 symbols in a block, i.e., on the range of possible values is gen- 406 erally in the billions. The block number and the encoding symbol ID 407 are both chosen uniformly and randomly from their range when an 408 encoding symbol is to be generated and transmitted. For example, 409 suppose the number of source symbols is 64,000 and the number of 410 blocks is 2. Then, each packet generated by the LT encoder could be 411 of the form (b, x: y). In this example, the first two fields iden- 412 tify the encoding symbol, where the first field is the block number b 413 = 0 or 1 and the second field is the randomly chosen encoding symbol 414 ID x. The value y after the colon is the value of the encoding sym- 415 bol. 417 3. Passing FEC coding information to receivers 419 There are two basic methods for passing FEC coding information to 420 receivers in order to decode an object: within the IP multicast 421 packet headers or through out of band methods. A description of the 422 variety of out of band methods is outside the scope of this document. 423 The FEC coding information can be classified as three types. FEC ses- 424 sion information is information needed by the FEC decoder that may 425 remain fixed for the transmission of many objects. FEC object 426 transmission information is information particular to the object 427 transmission session needed by the FEC decoder. The FEC payload ID 428 identifies the symbols in the payload of the ALC packet. 430 FEC coding information include the FEC codec type, the source block 431 length, the symbol length, the object length, the encoding block 432 number, the encoding symbol ID, and an encoding flag indicating 433 whether the encoding symbol is a source symbol or a redundant symbol. 434 The FEC codec type, the source block length and the symbol length are 435 often FEC session information, although they may classified as FEC 436 object transmission information for some protocols. Thus, sometimes 437 this information is passed to the receiver out of band, although they 438 can equally well be included in each IP multicast packet header as 439 long as the amount of space they take within each packet is minimal. 440 The object length is part of FEC object transmission information. 441 Depending on the protocol, the object length is passed to the 442 receiver out of band or included within each IP multicast packet 443 header. The FEC payload ID consists of the encoding block number (if 444 used), the encoding symbol ID and the encoding flag. The FEC payload 445 ID must be contained within each IP multicast packet header. 447 4. Security Considerations 449 The use of FEC, in and of itself, imposes no additional security con- 450 siderations versus sending the same information without FEC. How- 451 ever, just like for any transmission system, a malicious sender may 452 intentionally transmit bad symbols. If a receiver accepts one or more 453 bad symbols in place of authentic ones then such a receiver will have 454 its entire object down-load corrupted by the bad symbol. 455 Application-level transmission object authentication can detect the 456 corrupted transfer, but the receiver must then discard the 457 transferred object. Thus, transmitting false symbols is at least an 458 effective denial of service attack. At worst, a malicious sender 459 could add, delete, or replace arbitrary data within the transmitted 460 object. 462 In light of this possibility, FEC receivers may screen the source 463 address of a received symbol against a list of authentic transmitter 464 addresses. Since source addresses may be spoofed, FEC transport pro- 465 tocols may provide mechanisms for robust source authentication of 466 each encoded symbol. Multicast routers along the path of a FEC 467 transfer may provide the capability of discarding multicast packets 468 that originated on that subnet, and whose source IP address does not 469 correspond with that subnet. 471 5. Intellectual Property Disclosure 473 Both Tornado codes and LT codes have patents pending. 475 6. Acknowledgments 477 Thanks to Vincent Roca and Hayder Radha for their detailed comments 478 on this draft. 480 7. References 482 [AFZ95] Acharya, S., Franklin, M., and Zdonik, S., ``Dissemination- 483 Based Data Delivery Using Broadcast Disks'', IEEE Personal 484 Communications, pp.50-60, Dec 1995. 486 [BLA94] Blahut, R.E., ``Theory and Practice of Error Control Codes'', 487 Addison Wesley, MA 1984. 489 [BYE98] Byers, J.W., Luby, M., Mitzenmacher, M., and Rege, A., ``A 490 Digital Fountain Approach to Reliable Distribution of Bulk Data'', 491 Proceedings ACM SIGCOMM '98, Vancouver, Canada, Sept 1998. 493 [DEE88] Deering, S., ``Host Extensions for IP Multicasting'', RFC 494 1058, Stanford University, Stanford, CA, 1988. 496 [GEM99] Gemmell, J., Schooler, E., and Gray, J., ``ALC Scalable 497 Multicast File Distribution: Caching and Parameters Optimizations'' 498 Technical Report MSR-TR-99-14, Microsoft Research, Redmond, WA, April, 499 1999. 501 [HAN98] Handley, M., and Jacobson, V., ``SDP: Session Description 502 Protocol'', RFC 2327, April 1998. 504 [HAN96] Handley, M., ``SAP: Session Announcement Protocol'', Internet 505 Draft, IETF MMUSIC Working Group, Nov 1996. 507 [LUB97] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D., 508 Stemann, V., ``Practical Loss-Resilient Codes'' 29th STOC'97. 510 [LUB99] Luby, M., Vicisano, L., Speakman, T. ``Heterogeneous multicast 511 congestion control based on router packet filtering'', presented at 512 RMT meeting in Pisa, March 1999. 514 [R2068] Fielding, R., Gettys, J., Mogul, J. Frystyk, H., Berners-Lee, 515 T., Hypertext Transfer Protocol HTTP/1.1 (IETF RFC2068) 516 http://www.rfc-editor.org/rfc/rfc2068.txt 518 [R2119] Bradner, S., Key words for use in RFCs to Indicate Requirement 519 Levels (IETF RFC 2119) http://www.rfc-editor.org/rfc/rfc2119.txt 521 [RIZ97a] Rizzo, L, and Vicisano, L., ``Reliable Multicast Data 522 Distribution protocol based on software FEC techniques'', Proceedings 523 of the Fourth IEEES Workshop on the Architecture and Implementation of 524 High Performance Communication Systems, HPCS-97, Chalkidiki, Greece, 525 June 1997. 527 [RIZ97b] Rizzo, L., and Vicisano, L., ``Effective Erasure Codes for 528 Reliable Computer Communication Protocols'', ACM SIGCOMM Computer 529 Communication Review, Vol.27, No.2, pp.24-36, Apr 1997. 531 [RIZ97c] Rizzo, L., ``On the Feasibility of Software FEC'', DEIT Tech 532 Report, http://www.iet.unipi.it/~luigi/softfec.ps, Jan 1997. 534 [RUB99] Rubenstein, Dan, Kurose, Jim and Towsley, Don, ``The Impact of 535 Multicast Layering on Network Fairness'', Proceedings of ACM SIGCOMM'99. 537 [VIC98A] L.Vicisano, L.Rizzo, J.Crowcroft, ``TCP-like Congestion 538 Control for Layered Multicast Data Transfer'', IEEE Infocom '98, San 539 Francisco, CA, Mar.28-Apr.1 1998. 541 [VIC98B] Vicisano, L., ``Notes On a Cumulative Layered Organization 542 of Data Packets Across Multiple Streams with Different Rates'', 543 University College London Computer Science Research Note RN/98/25, 544 Work in Progress (May 1998). 546 8. Authors' Addresses 548 Michael Luby 549 luby@dfountain.com 550 Digital Fountain 551 600 Alabama Street 552 San Francisco, CA, USA, 94110 554 Lorenzo Vicisano 555 lorenzo@cisco.com 556 cisco Systems, Inc. 557 170 West Tasman Dr., 558 San Jose, CA, USA, 95134 560 Luigi Rizzo 561 luigi@iet.unipi.it 562 Dip. di Ing. dell'Informazione 563 Universita` di Pisa 564 via Diotisalvi 2, 56126 Pisa, Italy 566 Jim Gemmell 567 jgemmell@microsoft.com 568 Microsoft Research 569 301 Howard St., #830 570 San Francisco, CA, USA, 94105 571 Jon Crowcroft 572 J.Crowcroft@cs.ucl.ac.uk 573 Department of Computer Science 574 University College London 575 Gower Street, 576 London WC1E 6BT, UK 578 Bruce Lueckenhoff 579 brucelu@cadence.com 580 Cadence Design Systems, Inc. 581 120 Cremona Drive, Suite C 582 Santa Barbara, CA 93117