draft-ietf-rmt-info-fec-01.txt | draft-ietf-rmt-info-fec-02.txt | |||
---|---|---|---|---|

Internet Engineering Task Force RMT WG | Internet Engineering Task Force RMT WG | |||

INTERNET-DRAFT M. Luby/Digital Fountain | INTERNET-DRAFT M. Luby/Digital Fountain | |||

draft-ietf-rmt-info-fec-01.txt L. Vicisano/Cisco | draft-ietf-rmt-info-fec-02.txt L. Vicisano/Cisco | |||

J. Gemmell/Microsoft | J. Gemmell/Microsoft | |||

L. Rizzo/ACIRI and Univ. Pisa | L. Rizzo/ACIRI and Univ. Pisa | |||

M. Handley/ACIRI | M. Handley/ACIRI | |||

J. Crowcroft/UCL | J. Crowcroft/UCL | |||

18 October 2001 | 8 February 2002 | |||

Expires: April 2002 | Expires: August 2002 | |||

The use of Forward Error Correction in Reliable Multicast | The Use of Forward Error Correction in Reliable Multicast | |||

This document is an Internet-Draft and is in full conformance with all | This document is an Internet-Draft and is in full conformance with all | |||

provisions of Section 10 of RFC2026. | provisions of Section 10 of RFC2026 [3]. | |||

Internet-Drafts are working documents of the Internet Engineering Task | Internet-Drafts are working documents of the Internet Engineering Task | |||

Force (IETF), its areas, and its working groups. Note that other groups | Force (IETF), its areas, and its working groups. Note that other groups | |||

may also distribute working documents as Internet-Drafts. | may also distribute working documents as Internet-Drafts. | |||

Internet-Drafts are valid for a maximum of six months and may be | Internet-Drafts are valid for a maximum of six months and may be | |||

updated, replaced, or obsoleted by other documents at any time. It is | updated, replaced, or obsoleted by other documents at any time. It is | |||

inappropriate to use Internet-Drafts as reference material or to cite | inappropriate to use Internet-Drafts as reference material or to cite | |||

them other than as a "work in progress". | them other than as a "work in progress". | |||

skipping to change at page 2, line 49 | skipping to change at page 2, line 49 | |||

packet. | packet. | |||

FEC codes provide a reliability method that can be used to augment or | FEC codes provide a reliability method that can be used to augment or | |||

replace other reliability methods, especially for one-to-many | replace other reliability methods, especially for one-to-many | |||

reliability protocols such as reliable IP multicast. We first briefly | reliability protocols such as reliable IP multicast. We first briefly | |||

review some of the basic properties and types of FEC codes before | review some of the basic properties and types of FEC codes before | |||

reviewing their uses in the context of reliable IP multicast. Later, we | reviewing their uses in the context of reliable IP multicast. Later, we | |||

provide a more detailed description of some of FEC codes. | provide a more detailed description of some of FEC codes. | |||

In the general literature, FEC refers to the ability to overcome both | In the general literature, FEC refers to the ability to overcome both | |||

erasures (losses) and bit-level corruption. However, in the case of IP | erasures (losses) and bit-level corruption. However, in the case of an | |||

multicast, lower network layers will detect corrupted packets and | IP multicast protocol, the network layers will detect corrupted packets | |||

discard them. Therefore, an IP multicast protocol need not be concerned | and discard them or the transport layers can use packet authentication | |||

with corruption; the focus is solely on erasure codes. The payloads are | to discard corrupted packets. Therefore the primary application of FEC | |||

codes to IP multicast protocols is as an erasure code. The payloads are | ||||

generated and processed using an FEC erasure encoder and objects are | generated and processed using an FEC erasure encoder and objects are | |||

reassembled from reception of packets using the corresponding FEC | reassembled from reception of packets containing the generated encoding | |||

erasure decoder. | using the corresponding FEC erasure decoder. | |||

The input to an FEC encoder is some number k of equal length source | The input to an FEC encoder is some number k of equal length source | |||

symbols. The FEC encoder generates some number of encoding symbols that | symbols. The FEC encoder generates some number of encoding symbols that | |||

are of the same length as the source symbols. The chosen length of the | are of the same length as the source symbols. The chosen length of the | |||

symbols can vary upon each application of the FEC encoder, or it can be | symbols can vary upon each application of the FEC encoder, or it can be | |||

fixed. These encoding symbols are placed into packets for transmission. | fixed. These encoding symbols are placed into packets for transmission. | |||

The number of encoding symbols placed into each packet can vary on a per | The number of encoding symbols placed into each packet can vary on a per | |||

packet basis, or a fixed number of symbols (often one) can be placed | packet basis, or a fixed number of symbols (often one) can be placed | |||

into each packet. Also, in each packet is placed enough information to | into each packet. Also, in each packet is placed enough information to | |||

identify the particular encoding symbols carried in that packet. Upon | identify the particular encoding symbols carried in that packet. Upon | |||

skipping to change at page 3, line 52 | skipping to change at page 4, line 4 | |||

The above definitions explain the ideal situation when the reception of | The above definitions explain the ideal situation when the reception of | |||

any k encoding symbols is sufficient to recover the k source symbols, in | any k encoding symbols is sufficient to recover the k source symbols, in | |||

which case the reception overhead is 0%. For some practical FEC codes, | which case the reception overhead is 0%. For some practical FEC codes, | |||

slightly more than k encoding symbols are needed to recover the k source | slightly more than k encoding symbols are needed to recover the k source | |||

symbols. If k*(1+ep) encoding symbols are needed, we say the reception | symbols. If k*(1+ep) encoding symbols are needed, we say the reception | |||

overhead is ep*100%, e.g., if k*1.05 encoding symbols are needed then | overhead is ep*100%, e.g., if k*1.05 encoding symbols are needed then | |||

the reception overhead is 5%. | the reception overhead is 5%. | |||

Along a different dimension, we classify FEC codes loosely as being | Along a different dimension, we classify FEC codes loosely as being | |||

either small or large. A small FEC code is efficient in terms of | ||||

either small or large. A small FEC code is efficient in terms of | ||||

processing time requirements for encoding and decoding for small values | processing time requirements for encoding and decoding for small values | |||

of k, and a large FEC code is efficient for encoding and decoding for | of k, and a large FEC code is efficient for encoding and decoding for | |||

much large values of k. There are implementations of block FEC codes | much large values of k. There are implementations of block FEC codes | |||

that have encoding times proportional to n times the length of the k | that have encoding times proportional to n-k times the length of the k | |||

source symbols, and decoding times proportional l times the length of | source symbols, and decoding times proportional to l times the length of | |||

the k source symbols, where l is the number of missing source symbols | the k source symbols, where l is the number of missing source symbols | |||

among the k received encoding symbols. Because of the growth rate of | among the k received encoding symbols and l can be as large as k. | |||

the encoding and decoding times as a product of k and n, these are | Because of the growth rate of the encoding and decoding times as a | |||

typically considered to be small block FEC codes. There are block FEC | product of k and n-k, these are typically considered to be small block | |||

codes with a small reception overhead that can generate n encoding | FEC codes. There are block FEC codes with a small reception overhead | |||

symbols and can decode the k source symbols in time proportional to the | that can generate n encoding symbols and can decode the k source symbols | |||

length of the n encoding symbols. These codes are considered to be | in time proportional to the length of the n encoding symbols. These | |||

large block FEC codes. There are expandable FEC codes with a small | codes are considered to be large block FEC codes. There are expandable | |||

reception overhead that can generate each encoding symbol in time | FEC codes with a small reception overhead that can generate each | |||

roughly proportional to its length, and can decode all k source symbols | encoding symbol in time roughly proportional to its length, and can | |||

in time roughly proportional to their length. These are considered to | decode all k source symbols in time roughly proportional to their | |||

be large expandable FEC codes. | length. These are considered to be large expandable FEC codes. We | |||

describe examples of all of these types of codes later. | ||||

Ideally, FEC codes in the context of IP multicast can be used to | Ideally, FEC codes in the context of IP multicast can be used to | |||

generate encoding symbols that are transmitted in packets in such a way | generate encoding symbols that are transmitted in packets in such a way | |||

that each received packet is fully useful to a receiver to reassemble | that each received packet is fully useful to a receiver to reassemble | |||

the object regardless of previous packet reception patterns. Thus, if | the object regardless of previous packet reception patterns. Thus, if | |||

some packets are lost in transit between the sender and the receiver, | some packets are lost in transit between the sender and the receiver, | |||

instead of asking for specific retransmission of the lost packets or | instead of asking for specific retransmission of the lost packets or | |||

waiting till the packets are resent using Data Carousel, the receiver | waiting till the packets are resent using Data Carousel, the receiver | |||

can use any other subsequent equal number of packets that arrive to | can use any other subsequent equal number of packets that arrive to | |||

reassemble the object. These packets can either be proactively | reassemble the object. These packets can either be proactively | |||

skipping to change at page 6, line 46 | skipping to change at page 6, line 48 | |||

is either a source symbol ID or the redundant symbol ID. The portion of | is either a source symbol ID or the redundant symbol ID. The portion of | |||

the packet after the colon is the value of the encoding symbol. Any | the packet after the colon is the value of the encoding symbol. Any | |||

single source symbol of the object can be recovered as the parity of all | single source symbol of the object can be recovered as the parity of all | |||

the other symbols. For example, if packets | the other symbols. For example, if packets | |||

(1, 0: a), (1, 1: b), (1, 3: d), (0, 0: e) | (1, 0: a), (1, 1: b), (1, 3: d), (0, 0: e) | |||

are received then the missing source symbol value with source symbol ID | are received then the missing source symbol value with source symbol ID | |||

= 2 can be recovered by computing a XOR b XOR d XOR e = c. | = 2 can be recovered by computing a XOR b XOR d XOR e = c. | |||

Another way of forming the encoding symbol ID is to let values 0,...,k-1 | Another way of forming the encoding symbol ID is to let values 0,...,k-1 | |||

correspond to the k source symbols and value k corresponds to the | correspond to the k source symbols and value k correspond to the | |||

redundant symbol that is the XOR of the k source symbols. | redundant symbol that is the XOR of the k source symbols. | |||

When the number of source symbols in the object is large, a simple block | When the number of source symbols in the object is large, a simple block | |||

code variant of the above can be used. In this case, the source symbols | code variant of the above can be used. In this case, the source symbols | |||

are grouped together into source blocks of some number k of consecutive | are grouped together into source blocks of some number k of consecutive | |||

symbols each, where k may be different for different blocks. If a block | symbols each, where k may be different for different blocks. If a block | |||

consists of k source symbols then a redundant symbol is added to form an | consists of k source symbols then a redundant symbol is added to form an | |||

encoding block consisting of k+1 encoding symbols. Then, a source block | encoding block consisting of k+1 encoding symbols. Then, a source block | |||

consisting of k source symbols can be recovered from any k of the k+1 | consisting of k source symbols can be recovered from any k of the k+1 | |||

encoding symbols from the associated encoding block. | encoding symbols from the associated encoding block. | |||

Slightly more sophisticated ways of adding redundant symbols using | Slightly more sophisticated ways of adding redundant symbols using | |||

parity can also be used. For example, one can group a block consisting | parity can also be used. For example, one can group a block consisting | |||

of k source symbols in an object into a p x p square matrix, where p = | of k source symbols in an object into a p x p square matrix, where p = | |||

skipping to change at page 7, line 46 | skipping to change at page 7, line 48 | |||

when used to encode the entire object directly. Block codes are usually | when used to encode the entire object directly. Block codes are usually | |||

systematic, which means that the n encoding symbols consist of the k | systematic, which means that the n encoding symbols consist of the k | |||

source symbols and n-k redundant symbols generated from these k source | source symbols and n-k redundant symbols generated from these k source | |||

symbols, where the size of a redundant symbol is the same as that for a | symbols, where the size of a redundant symbol is the same as that for a | |||

source symbol. For example, the first simple code (XOR) described in | source symbol. For example, the first simple code (XOR) described in | |||

the previous subsection is a (k+1, k) code. In general, the freedom to | the previous subsection is a (k+1, k) code. In general, the freedom to | |||

choose n larger than k+1 is desirable, as this can provide much better | choose n larger than k+1 is desirable, as this can provide much better | |||

protection against losses. A popular example of these types of codes is | protection against losses. A popular example of these types of codes is | |||

a class of Reed-Solomon codes, which are based on algebraic methods | a class of Reed-Solomon codes, which are based on algebraic methods | |||

using finite fields. Implementations of (n, k) FEC erasure codes are | using finite fields. Implementations of (n, k) FEC erasure codes are | |||

efficient enough to be used by personal computers [8]. For example, [7] | efficient enough to be used by personal computers [9]. For example, [8] | |||

describes an implementation where the encoding and decoding speeds decay | describes an implementation where the encoding and decoding speeds decay | |||

as C/j, where the constant C is on the order of 10 to 80 Mbytes/second | as C/j, where the constant C is on the order of 10 to 80 Mbytes/second | |||

for Pentium class machines of various vintages and j is upper bounded by | for Pentium class machines of various vintages and j is upper bounded by | |||

min(k, n-k). | min(k, n-k). | |||

In practice, the values of k and n must be small (for example below 256) | In practice, the values of k and n must be small (for example below 256) | |||

for such FEC codes as large values make encoding and decoding | for such FEC codes as large values make encoding and decoding | |||

prohibitively expensive. As many objects are longer than k symbols for | prohibitively expensive. As many objects are longer than k symbols for | |||

reasonable values of k and the symbol length (e.g. larger than 16 | reasonable values of k and the symbol length (e.g. larger than 16 | |||

kilobyte for k = 16 using 1 kilobyte symbols), they can be divided into | kilobyte for k = 16 using 1 kilobyte symbols), they can be divided into | |||

a number of source blocks. Each source block consists of some number k | a number of source blocks. Each source block consists of some number k | |||

of source symbols, where k may vary between different source blocks. | of source symbols, where k may vary between different source blocks. | |||

The FEC encoder is used to encode a k source symbol source block into a | The FEC encoder is used to encode a k source symbol source block into a | |||

skipping to change at page 8, line 42 | skipping to change at page 8, line 44 | |||

| | | | |||

v | v | |||

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | |||

|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| 2| 3| 4| 5| 6| 7| 8| 9| | |||

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | |||

^ ^ | ^ ^ | |||

| | | | | | |||

| encoding symbol IDs | encoding symbol IDs | | | encoding symbol IDs | encoding symbol IDs | | |||

| of encoding block 0 | of encoding block 1 | | | of encoding block 0 | of encoding block 1 | | |||

Figure 1. Encoding structure for object divided into two source | Figure 1. The encoding structure for an object divided into two source | |||

blocks consisting of 8 source symbols each, and the FEC encoder is used to | blocks consisting of 8 source symbols each, and the FEC encoder is used to | |||

generate 2 additional redundant symbols (10 encoding symbols in total) | generate 2 additional redundant symbols (10 encoding symbols in total) | |||

for each of the two source blocks. | for each of the two source blocks. | |||

In many cases, an object is partitioned into equal length source blocks | In many cases, an object is partitioned into equal length source blocks | |||

each consisting of k contiguous source symbols of the object, i.e., | each consisting of k contiguous source symbols of the object, i.e., | |||

block c consists of the range of source symbols [ck, (c+1)k-1]. This | block c consists of the range of source symbols [ck, (c+1)k-1]. This | |||

ensures that the FEC encoder can be optimized to handle a particular | ensures that the FEC encoder can be optimized to handle a particular | |||

number k of source symbols. This also ensures that memory references | number k of source symbols. This also ensures that memory references | |||

are local when the sender reads source symbols to encode, and when the | are local when the sender reads source symbols to encode, and when the | |||

receiver reads encoding symbols to decode. Locality of reference is | receiver reads encoding symbols to decode. Locality of reference is | |||

particularly important when the object is stored on disk, as it reduces | particularly important when the object is stored on disk, as it reduces | |||

the disk seeks required. The block number and the source symbol ID | the disk seeks required. The block number and the source symbol ID | |||

within that block can be used to uniquely specify a source symbol within | within that block can be used to uniquely specify a source symbol within | |||

the object. If the size of the object is not a multiple of k source | the object. If the size of the object is not a multiple of k source | |||

symbols, then the last source block will contain less than k symbols. | symbols, then the last source block will contain less than k symbols. | |||

skipping to change at page 10, line 14 | skipping to change at page 10, line 16 | |||

(1, 1, 0: f), (1, 1, 1: g), (1, 0, 0: x), (1, 0, 1: y), (1, 0, 2: z) | (1, 1, 0: f), (1, 1, 1: g), (1, 0, 0: x), (1, 0, 1: y), (1, 0, 2: z) | |||

is sufficient to recover the second source block. | is sufficient to recover the second source block. | |||

Another way of uniquely identifying encoding symbols within a block is | Another way of uniquely identifying encoding symbols within a block is | |||

to let the encoding symbol IDs for source symbols be 0,...,k-1 and to | to let the encoding symbol IDs for source symbols be 0,...,k-1 and to | |||

let the encoding symbol IDs for redundant symbols be k,...,n-1. | let the encoding symbol IDs for redundant symbols be k,...,n-1. | |||

2.3. Large block FEC codes | 2.3. Large block FEC codes | |||

Tornado codes [4] are large block FEC codes that provide an alternative | Tornado codes [5] are large block FEC codes that provide an alternative | |||

to small block FEC codes. An (n, k) Tornado code requires slightly more | to small block FEC codes. An (n, k) Tornado code requires slightly more | |||

than k out of n encoding symbols to recover k source symbols, i.e., | than k out of n encoding symbols to recover k source symbols, i.e., | |||

there is a small reception overhead. However, the advantage is that the | there is a small reception overhead. The benefit of the small cost of | |||

value of k may be on the order of tens of thousands and still run | non-zero reception overhead is that the value of k may be on the order | |||

efficiently. Because of memory considerations, in practice the value of | of tens of thousands and still the encoding and decoding are efficient. | |||

n is restricted to be a small multiple of k, e.g., n = 2k. For example, | Because of memory considerations, in practice the value of n is | |||

[3] describes an implementation of Tornado codes where the encoding and | restricted to be a small multiple of k, e.g., n = 2k. For example, [4] | |||

describes an implementation of Tornado codes where the encoding and | ||||

decoding speeds are tens of megabytes per second for Pentium class | decoding speeds are tens of megabytes per second for Pentium class | |||

machines of various vintages when k is in the tens of thousands and n = | machines of various vintages when k is in the tens of thousands and n = | |||

2k. The reception overhead for such values of k and n is in the 5-10% | 2k. The reception overhead for such values of k and n is in the 5-10% | |||

range. Tornado codes require a large amount of out of band information | range. Tornado codes require a large amount of out of band information | |||

to be communicated to all senders and receivers for each different | to be communicated to all senders and receivers for each different | |||

object length, and require an amount of memory on the encoder and | object length, and require an amount of memory on the encoder and | |||

decoder which is proportional to the object length times 2n/k. | decoder which is proportional to the object length times 2n/k. | |||

Tornado codes are designed to have low reception overhead on average | Tornado codes are designed to have low reception overhead on average | |||

with respect to reception of a random portion of the encoding packets. | with respect to reception of a random portion of the encoding packets. | |||

skipping to change at page 10, line 47 | skipping to change at page 11, line 5 | |||

All of the FEC codes described up to this point are block codes. There | All of the FEC codes described up to this point are block codes. There | |||

is a different type of FEC codes that we call expandable FEC codes. | is a different type of FEC codes that we call expandable FEC codes. | |||

Like block codes, an expandable FEC encoder operates on an object of | Like block codes, an expandable FEC encoder operates on an object of | |||

known size that is partitioned into equal length source symbols. Unlike | known size that is partitioned into equal length source symbols. Unlike | |||

block codes, there is no predetermined number of encoding symbols that | block codes, there is no predetermined number of encoding symbols that | |||

can be generated for expandable FEC codes. Instead, an expandable FEC | can be generated for expandable FEC codes. Instead, an expandable FEC | |||

encoder can generate as few or as many unique encoding symbols as | encoder can generate as few or as many unique encoding symbols as | |||

required on demand. | required on demand. | |||

LT codes [5] are an example of large expandable FEC codes with a small | LT codes [6] are an example of large expandable FEC codes with a small | |||

reception overhead. An LT encoder uses randomization to generate each | reception overhead. An LT encoder uses randomization to generate each | |||

encoding symbol randomly and independently of all other encoding | encoding symbol randomly and independently of all other encoding | |||

symbols. Like Tornado codes, the number of source symbols k may be very | symbols. Like Tornado codes, the number of source symbols k may be very | |||

large for LT codes, i.e., on the order of tens to hundreds of thousands, | large for LT codes, i.e., on the order of tens to hundreds of thousands, | |||

and the encoder and decoder run efficiently in software. For example the | and the encoder and decoder run efficiently in software. For example the | |||

encoding and decoding speeds for LT codes are in the range 3-20 | encoding and decoding speeds for LT codes are in the range 3-20 | |||

megabytes per second for Pentium class machines of various vintages when | megabytes per second for Pentium class machines of various vintages when | |||

k is in the high tens of thousands. An LT encoder can generate as few | k is in the high tens of thousands. An LT encoder can generate as few | |||

or as many encoding symbols as required on demand. When a new encoding | or as many encoding symbols as required on demand. When a new encoding | |||

symbol is to be generated by an LT encoder, it is based on a randomly | symbol is to be generated by an LT encoder, it is based on a randomly | |||

chosen encoding symbol ID that uniquely describes how the encoding | chosen encoding symbol ID that uniquely describes how the encoding | |||

skipping to change at page 13, line 49 | skipping to change at page 14, line 4 | |||

corrupted transfer, but the receiver must then discard the transferred | corrupted transfer, but the receiver must then discard the transferred | |||

object. Thus, injecting corrupted encoding symbols they are accepted as | object. Thus, injecting corrupted encoding symbols they are accepted as | |||

valid encoding symbols by a receiver is at the very least an effective | valid encoding symbols by a receiver is at the very least an effective | |||

denial of service attack. | denial of service attack. | |||

In light of this possibility, FEC receivers may screen the source | In light of this possibility, FEC receivers may screen the source | |||

address of a received symbol against a list of authentic transmitter | address of a received symbol against a list of authentic transmitter | |||

addresses. Since source addresses may be spoofed, transport protocols | addresses. Since source addresses may be spoofed, transport protocols | |||

using FEC may provide mechanisms for robust source authentication of | using FEC may provide mechanisms for robust source authentication of | |||

each encoding symbol. Multicast routers along the path of a FEC transfer | each encoding symbol. Multicast routers along the path of a FEC transfer | |||

may provide the capability of discarding multicast packets that | may provide the capability of discarding multicast packets that | |||

originated on that subnet, and whose source IP address does not | originated on that subnet, and whose source IP address does not | |||

correspond with that subnet. | correspond with that subnet. | |||

It is recommended that a packet authentication scheme such as TESLA [6] | It is recommended that a packet authentication scheme such as TESLA [7] | |||

be used in conjunction with FEC codes. Then, packets that cannot be | be used in conjunction with FEC codes. Then, packets that cannot be | |||

authenticated can be discarded and the object can be reliably recovered | authenticated can be discarded and the object can be reliably recovered | |||

from the received authenticated packets. | from the received authenticated packets. | |||

4. Intellectual Property Disclosure | 4. Intellectual Property Disclosure | |||

Tornado codes [4] have both patents issued and patents pending. There | Tornado codes [5] have both patents issued and patents pending. There | |||

is an issued patent for LT codes [5]. | is an issued patent for LT codes [6]. | |||

5. Acknowledgments | 5. Acknowledgments | |||

Thanks to Vincent Roca and Hayder Radha for their detailed comments on | Thanks to Vincent Roca and Hayder Radha for their detailed comments on | |||

this draft. | this draft. | |||

6. References | 6. References | |||

[1] Acharya, S., Franklin, M., and Zdonik, S., ``Dissemination- Based | [1] Acharya, S., Franklin, M., and Zdonik, S., ``Dissemination- Based | |||

Data Delivery Using Broadcast Disks'', IEEE Personal Communications, | Data Delivery Using Broadcast Disks'', IEEE Personal Communications, | |||

pp.50-60, Dec 1995. | pp.50-60, Dec 1995. | |||

[2] Blahut, R.E., ``Theory and Practice of Error Control Codes'', | [2] Blahut, R.E., ``Theory and Practice of Error Control Codes'', | |||

Addison Wesley, MA 1984. | Addison Wesley, MA 1984. | |||

[3] Byers, J.W., Luby, M., Mitzenmacher, M., and Rege, A., ``A Digital | [3] Bradner, S., "The Internet Standards Process -- Revision 3", | |||

RFC2026, October 1996. | ||||

[4] Byers, J.W., Luby, M., Mitzenmacher, M., and Rege, A., ``A Digital | ||||

Fountain Approach to Reliable Distribution of Bulk Data'', Proceedings | Fountain Approach to Reliable Distribution of Bulk Data'', Proceedings | |||

ACM SIGCOMM '98, Vancouver, Canada, Sept 1998. | ACM SIGCOMM '98, Vancouver, Canada, Sept 1998. | |||

[4] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D., | [5] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D., | |||

``Efficient Erasure Correcting Codes'', IEEE Transactions on Information | ``Efficient Erasure Correcting Codes'', IEEE Transactions on Information | |||

Theory, Special Issue: Codes on Graphs and Iterative Algorithms, pp. | Theory, Special Issue: Codes on Graphs and Iterative Algorithms, pp. | |||

569-584, Vol. 47, No. 2, February 2001. | 569-584, Vol. 47, No. 2, February 2001. | |||

[5] Luby, M., "Information Additive Code Generator and Decoder for | [6] Luby, M., "Information Additive Code Generator and Decoder for | |||

Communication Systems", U.S. Patent No. 6,307,487, October 23, 2001. | Communication Systems", U.S. Patent No. 6,307,487, October 23, 2001. | |||

[6] Perrig, A., Canetti, R., Song, D., Tygar, J.D., "Efficient and | [7] Perrig, A., Canetti, R., Song, D., Tygar, J.D., "Efficient and | |||

Secure Source Authentication for Multicast", Network and Distributed | Secure Source Authentication for Multicast", Network and Distributed | |||

System Security Symposium, NDSS 2001, pp. 35-46, February 2001. | System Security Symposium, NDSS 2001, pp. 35-46, February 2001. | |||

[7] Rizzo, L., ``Effective Erasure Codes for Reliable Computer | [8] Rizzo, L., ``Effective Erasure Codes for Reliable Computer | |||

Communication Protocols'', ACM SIGCOMM Computer Communication Review, | Communication Protocols'', ACM SIGCOMM Computer Communication Review, | |||

Vol.27, No.2, pp.24-36, Apr 1997. | Vol.27, No.2, pp.24-36, Apr 1997. | |||

[8] Rizzo, L., ``On the Feasibility of Software FEC'', DEIT Tech Report, | [9] Rizzo, L., ``On the Feasibility of Software FEC'', DEIT Tech Report, | |||

http://www.iet.unipi.it/~luigi/softfec.ps, Jan 1997. | http://www.iet.unipi.it/~luigi/softfec.ps, Jan 1997. | |||

7. Authors' Addresses | 7. Authors' Addresses | |||

Michael Luby | Michael Luby | |||

luby@digitalfountain.com | luby@digitalfountain.com | |||

Digital Fountain | Digital Fountain | |||

39141 Civic Center Drive | 39141 Civic Center Drive | |||

Suite 300 | Suite 300 | |||

Fremont, CA 94538 | Fremont, CA 94538 | |||

End of changes. | ||||

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/ |