draft-ietf-rmt-info-fec-03.txt | rfc3453.txt | |||
---|---|---|---|---|

Internet Engineering Task Force RMT WG | ||||

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

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

J. Gemmell/Microsoft | ||||

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

M. Handley/ACIRI | ||||

J. Crowcroft/UCL | ||||

3 September 2002 | ||||

Expires: March 2003 | ||||

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

Status of this Memo | Network Working Group M. Luby | |||

Request for Comments: 3453 Digital Fountain | ||||

This document is an Internet-Draft and is in full conformance with all | Category: Informational L. Vicisano | |||

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

J. Gemmell | ||||

Microsoft | ||||

L. Rizzo | ||||

Univ. Pisa | ||||

M. Handley | ||||

ICIR | ||||

J. Crowcroft | ||||

Cambridge Univ. | ||||

December 2002 | ||||

Internet-Drafts are working documents of the Internet Engineering Task | The Use of Forward Error Correction (FEC) in Reliable Multicast | |||

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

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

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

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

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

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

The list of current Internet-Drafts can be accessed at | This memo provides information for the Internet community. It does | |||

http://www.ietf.org/ietf/1id-abstracts.txt | not specify an Internet standard of any kind. Distribution of this | |||

memo is unlimited. | ||||

To view the list Internet-Draft Shadow Directories, see | Copyright Notice | |||

http://www.ietf.org/shadow.html. | ||||

This document is a product of the IETF RMT WG. Comments should be | Copyright (C) The Internet Society (2002). All Rights Reserved. | |||

addressed to the authors, or the WG's mailing list at rmt@lbl.gov. | ||||

Abstract | Abstract | |||

This memo describes the use of Forward Error Correction codes to | This memo describes the use of Forward Error Correction (FEC) codes | |||

efficiently provide and/or augment reliability for one-to-many reliable | to efficiently provide and/or augment reliability for one-to-many | |||

data transport using IP multicast. One of the key properties of Forward | reliable data transport using IP multicast. One of the key | |||

Error Correction codes in this context is the ability to use the same | properties of FEC codes in this context is the ability to use the | |||

packets containing Forward Error Correction data to simultaneously | same packets containing FEC data to simultaneously repair different | |||

repair different packet loss patterns at multiple receivers. Different | packet loss patterns at multiple receivers. Different classes of FEC | |||

classes of Forward Error Correction codes and some of their basic | codes and some of their basic properties are described and | |||

properties are described and terminology relevant to implementing | terminology relevant to implementing FEC in a reliable multicast | |||

Forward Error Correction Codes in a reliable multicast protocol is | protocol is introduced. Examples are provided of possible abstract | |||

introduced. Examples are provided of possible abstract formats for | formats for packets carrying FEC. | |||

packets carrying Forward Error Correction data. | ||||

Table of Contents | Table of Contents | |||

1. Rationale and Overview . . . . . . . . . . . . . . . . . . . . 2 | ||||

1.1. Application of FEC codes . . . . . . . . . . . . . . . . . 5 | ||||

2. FEC Codes. . . . . . . . . . . . . . . . . . . . . . . . . . . 6 | ||||

2.1. Simple codes . . . . . . . . . . . . . . . . . . . . . . . 6 | ||||

2.2. Small block FEC codes. . . . . . . . . . . . . . . . . . . 8 | ||||

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

2.4. Expandable FEC codes . . . . . . . . . . . . . . . . . . . 11 | ||||

2.5. Source blocks with variable length source symbols. . . . . 13 | ||||

3. Security Considerations. . . . . . . . . . . . . . . . . . . . 14 | ||||

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

5. Acknowledgments. . . . . . . . . . . . . . . . . . . . . . . . 15 | ||||

6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 15 | ||||

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

8. Full Copyright Statement . . . . . . . . . . . . . . . . . . . 18 | ||||

1. Rationale and Overview. . . . . . . . . . . . . . . . . . . . . . 4 | ||||

1.1. Application of FEC codecs. . . . . . . . . . . . . . . . . . . 6 | ||||

2. FEC Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 | ||||

2.1. Simple codes . . . . . . . . . . . . . . . . . . . . . . . . . 8 | ||||

2.2. Small block FEC codes. . . . . . . . . . . . . . . . . . . . . 9 | ||||

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

2.4. Expandable FEC codes . . . . . . . . . . . . . . . . . . . . . 12 | ||||

2.5. Source blocks with variable length source | ||||

symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 | ||||

3. Security Considerations . . . . . . . . . . . . . . . . . . . . . 15 | ||||

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

5. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 16 | ||||

6. References. . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 | ||||

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

8. Full Copyright Statement. . . . . . . . . . . . . . . . . . . . . 19 | ||||

1. Rationale and Overview | 1. Rationale and Overview | |||

There are many ways to provide reliability for transmission protocols. | There are many ways to provide reliability for transmission | |||

A common method is to use ARQ, automatic request for retransmission. | protocols. A common method is to use ARQ, automatic request for | |||

With ARQ, receivers use a back channel to the sender to send requests | retransmission. With ARQ, receivers use a back channel to the sender | |||

for retransmission of lost packets. ARQ works well for one-to-one | to send requests for retransmission of lost packets. ARQ works well | |||

reliable protocols, as evidenced by the pervasive success of TCP/IP. | for one-to-one reliable protocols, as evidenced by the pervasive | |||

ARQ has also been an effective reliability tool for one-to-many | success of TCP/IP. ARQ has also been an effective reliability tool | |||

reliability protocols, and in particular for some reliable IP multicast | for one-to-many reliability protocols, and in particular for some | |||

protocols. However, for one-to-very-many reliability protocols, ARQ has | reliable IP multicast protocols. However, for one-to-very-many | |||

limitations, including the feedback implosion problem because many | reliability protocols, ARQ has limitations, including the feedback | |||

receivers are transmitting back to the sender, and the need for a back | implosion problem because many receivers are transmitting back to the | |||

channel to send these requests from the receiver. Another limitation is | sender, and the need for a back channel to send these requests from | |||

that receivers may experience different loss patterns of packets, and | the receiver. Another limitation is that receivers may experience | |||

thus receivers may be delayed by retransmission of packets that other | different loss patterns of packets, and thus receivers may be delayed | |||

receivers have lost that but they have already received. This may also | by retransmission of packets that other receivers have lost that but | |||

cause wasteful use of bandwidth used to retransmit packets that have | they have already received. This may also cause wasteful use of | |||

already been received by many of the receivers. | bandwidth used to retransmit packets that have already been received | |||

by many of the receivers. | ||||

In environments where ARQ is either costly or impossible because there | In environments where ARQ is either costly or impossible because | |||

is either a very limited capacity back channel or no back channel at | there is either a very limited capacity back channel or no back | |||

all, such as satellite transmission, a Data Carousel approach to | channel at all, such as satellite transmission, a Data Carousel | |||

reliability is sometimes used [1]. With a Data Carousel, the sender | approach to reliability is sometimes used [1]. With a Data Carousel, | |||

partitions the object into equal length pieces of data, which we | the sender partitions the object into equal length pieces of data, | |||

hereafter call source symbols, places them into packets, and then | which we hereafter call source symbols, places them into packets, and | |||

continually cycles through and sends these packets. Receivers | then continually cycles through and sends these packets. Receivers | |||

continually receive packets until they have received a copy of each | continually receive packets until they have received a copy of each | |||

packet. Data Carousel has the advantage that it requires no back | packet. Data Carousel has the advantage that it requires no back | |||

channel because there is no data that flows from receivers to the | channel because there is no data that flows from receivers to the | |||

sender. However, Data Carousel also has limitations. For example, if a | sender. However, Data Carousel also has limitations. For example, | |||

receiver loses a packet in one round of transmission it must wait an | if a receiver loses a packet in one round of transmission it must | |||

entire round before it has a chance to receive that packet again. This | wait an entire round before it has a chance to receive that packet | |||

may also cause wasteful use of bandwidth, as the sender continually | again. This may also cause wasteful use of bandwidth, as the sender | |||

cycles through and transmits the packets until no receiver is missing a | continually cycles through and transmits the packets until no | |||

packet. | receiver is missing a packet. | |||

Forward Error Correction (FEC) codes provide a reliability method that | Forward Error Correction (FEC) codes provide a reliability method | |||

can be used to augment or replace other reliability methods, especially | that can be used to augment or replace other reliability methods, | |||

for one-to-many reliability protocols such as reliable IP multicast. We | especially for one-to-many reliability protocols such as reliable IP | |||

first briefly review some of the basic properties and types of FEC codes | multicast. We first briefly review some of the basic properties and | |||

before reviewing their uses in the context of reliable IP multicast. | types of FEC codes before reviewing their uses in the context of | |||

Later, we provide a more detailed description of some of FEC codes. | reliable IP multicast. Later, we 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 an | erasures (losses) and bit-level corruption. However, in the case of | |||

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

and discard them or the transport layers can use packet authentication | packets and discard them or the transport layers can use packet | |||

to discard corrupted packets. Therefore the primary application of FEC | authentication to discard corrupted packets. Therefore the primary | |||

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

generated and processed using an FEC erasure encoder and objects are | code. The payloads are generated and processed using an FEC erasure | |||

reassembled from reception of packets containing the generated encoding | encoder and objects are reassembled from reception of packets | |||

using the corresponding FEC erasure decoder. | containing the generated encoding 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 | |||

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

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

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

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

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

into each packet. Also, in each packet is placed enough information to | one) can be placed into each packet. Also, in each packet is placed | |||

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

receipt of packets containing encoding symbols, the receiver feeds these | carried in that packet. Upon receipt of packets containing encoding | |||

encoding symbols into the corresponding FEC decoder to recreate an exact | symbols, the receiver feeds these encoding symbols into the | |||

copy of the k source symbols. Ideally, the FEC decoder can recreate an | corresponding FEC decoder to recreate an exact copy of the k source | |||

exact copy from any k of the encoding symbols. | symbols. Ideally, the FEC decoder can recreate an exact copy from | |||

any k of the encoding symbols. | ||||

In a later section, we describe a technique for using FEC codes as | In a later section, we describe a technique for using FEC codes as | |||

described above to handle blocks with variable length source symbols. | described above to handle blocks with variable length source symbols. | |||

Block FEC codes work as follows. The input to a block FEC encoder is k | Block FEC codes work as follows. The input to a block FEC encoder is | |||

source symbols and a number n. The encoder generates a total of n | k source symbols and a number n. The encoder generates a total of n | |||

encoding symbols. The encoder is systematic if it generates n-k | encoding symbols. The encoder is systematic if it generates n-k | |||

redundant symbols yielding an encoding block of n encoding symbols in | redundant symbols yielding an encoding block of n encoding symbols in | |||

total composed of the k source symbols and the n-k redundant symbols. A | total composed of the k source symbols and the n-k redundant symbols. | |||

block FEC decoder has the property that any k of the n encoding symbols | ||||

in the encoding block is sufficient to reconstruct the original k source | ||||

symbols. | ||||

Expandable FEC codes work as follows. An expandable FEC encoder takes | A block FEC decoder has the property that any k of the n encoding | |||

as input k source symbols and generates as many unique encoding symbols | symbols in the encoding block is sufficient to reconstruct the | |||

as requested on demand, where the amount of time for generating each | original k source symbols. | |||

encoding symbol is the same independent of how many encoding symbols are | ||||

generated. An expandable FEC decoder has the property that any k of the | ||||

unique encoding symbols is sufficient to reconstruct the original k | ||||

source symbols. | ||||

The above definitions explain the ideal situation when the reception of | Expandable FEC codes work as follows. An expandable FEC encoder | |||

any k encoding symbols is sufficient to recover the k source symbols, in | takes as input k source symbols and generates as many unique encoding | |||

which case the reception overhead is 0%. For some practical FEC codes, | symbols as requested on demand, where the amount of time for | |||

slightly more than k encoding symbols are needed to recover the k source | generating each encoding symbol is the same independent of how many | |||

symbols. If k*(1+ep) encoding symbols are needed, we say the reception | encoding symbols are generated. An expandable FEC decoder has the | |||

overhead is ep*100%, e.g., if k*1.05 encoding symbols are needed then | property that any k of the unique encoding symbols is sufficient to | |||

the reception overhead is 5%. | reconstruct the original k source symbols. | |||

Along a different dimension, we classify FEC codes loosely as being | The above definitions explain the ideal situation when the reception | |||

either small or large. A small FEC code is efficient in terms of | of any k encoding symbols is sufficient to recover the k source | |||

processing time requirements for encoding and decoding for small values | symbols, in which case the reception overhead is 0%. For some | |||

of k, and a large FEC code is efficient for encoding and decoding for | practical FEC codes, slightly more than k encoding symbols are needed | |||

much large values of k. There are implementations of block FEC codes | to recover the k source symbols. If k*(1+ep) encoding symbols are | |||

that have encoding times proportional to n-k times the length of the k | needed, we say the reception overhead is ep*100%, e.g., if k*1.05 | |||

source symbols, and decoding times proportional to l times the length of | encoding symbols are needed then the reception overhead is 5%. | |||

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

among the k received encoding symbols and l can be as large as k. | ||||

Because of the growth rate of the encoding and decoding times as a | ||||

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

FEC codes. There are block FEC codes with a small reception overhead | ||||

that can generate n encoding symbols and can decode the k source symbols | ||||

in time proportional to the length of the n encoding symbols. These | ||||

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

FEC codes with a small reception overhead that can generate each | ||||

encoding symbol in time roughly proportional to its length, and can | ||||

decode all k source symbols in time roughly proportional to their | ||||

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 | Along a different dimension, we classify FEC codes loosely as being | |||

generate encoding symbols that are transmitted in packets in such a way | either small or large. A small FEC code is efficient in terms of | |||

that each received packet is fully useful to a receiver to reassemble | processing time requirements for encoding and decoding for small | |||

the object regardless of previous packet reception patterns. Thus, if | values of k, and a large FEC code is efficient for encoding and | |||

some packets are lost in transit between the sender and the receiver, | decoding for much large values of k. There are implementations of | |||

instead of asking for specific retransmission of the lost packets or | block FEC codes that have encoding times proportional to n-k times | |||

waiting till the packets are resent using Data Carousel, the receiver | the length of the k source symbols, and decoding times proportional | |||

can use any other subsequent equal number of packets that arrive to | to l times the length of the k source symbols, where l is the number | |||

reassemble the object. These packets can either be proactively | of missing source symbols among the k received encoding symbols and l | |||

transmitted or they can be explicitly requested by receivers. This | can be as large as k. Because of the growth rate of the encoding and | |||

implies that the same packet is fully useful to all receivers to | decoding times as a product of k and n-k, these are typically | |||

reassemble the object, even though the receivers may have previously | considered to be small block FEC codes. There are block FEC codes | |||

experienced different packet loss patterns. This property can reduce or | with a small reception overhead that can generate n encoding symbols | |||

even eliminate the problems mentioned above associated with ARQ and Data | and can decode the k source symbols in time proportional to the | |||

Carousel and thereby dramatically increase the scalability of the | length of the n encoding symbols. These codes are considered to be | |||

protocol to orders of magnitude more receivers. | large block FEC codes. There are expandable FEC codes with a small | |||

reception overhead that can generate each encoding symbol in time | ||||

roughly proportional to its length, and can decode all k source | ||||

symbols in time roughly proportional to their length. These are | ||||

considered to be large expandable FEC codes. We describe examples of | ||||

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

1.1. Application of FEC codecs | 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 that each received packet is fully useful to a receiver to | ||||

reassemble the object regardless of previous packet reception | ||||

patterns. Thus, if some packets are lost in transit between the | ||||

sender and the receiver, instead of asking for specific | ||||

retransmission of the lost packets or waiting till the packets are | ||||

resent using Data Carousel, the receiver can use any other subsequent | ||||

equal number of packets that arrive to reassemble the object. These | ||||

packets can either be proactively transmitted or they can be | ||||

explicitly requested by receivers. This implies that the same packet | ||||

is fully useful to all receivers to reassemble the object, even | ||||

though the receivers may have previously experienced different packet | ||||

loss patterns. This property can reduce or even eliminate the | ||||

problems mentioned above associated with ARQ and Data Carousel and | ||||

thereby dramatically increase the scalability of the protocol to | ||||

orders of magnitude more receivers. | ||||

For some reliable IP multicast protocols, FEC codes are used in | 1.1. Application of FEC codes | |||

conjunction with ARQ to provide reliability. For example, a large | ||||

object could be partitioned into a number of source blocks consisting of | ||||

a small number of source symbols each, and in a first round of | ||||

transmission all of the source symbols for all the source blocks could | ||||

be transmitted. Then, receivers could report back to the sender the | ||||

number of source symbols they are missing from each source block. The | ||||

sender could then compute the maximum number of missing source symbols | ||||

from each source block among all receivers. Based on this, a small | ||||

block FEC encoder could be used to generate for each source block a | ||||

number of redundant symbols equal to the computed maximum number of | ||||

missing source symbols from the block among all receivers, as long as | ||||

this maximum maximum for each block does not exceed the number of | ||||

redundant symbols that can be generated efficiently. In a second round | ||||

of transmission, the server would then send all of these redundant | ||||

symbols for all blocks. In this example, if there are no losses in the | ||||

second round of transmission then all receivers will be able to recreate | ||||

an exact copy of each original block. In this case, even if different | ||||

receivers are missing different symbols in different blocks, transmitted | ||||

redundant symbols for a given block are useful to all receivers missing | ||||

symbols from that block in the second round. | ||||

For other reliable IP multicast protocols, FEC codes are used in a Data | For some reliable IP multicast protocols, FEC codes are used in | |||

Carousel fashion to provide reliability, which we call an FEC Data | conjunction with ARQ to provide reliability. For example, a large | |||

Carousel. For example, an FEC Data Carousel using a large block FEC | object could be partitioned into a number of source blocks consisting | |||

code could work as follows. The large block FEC encoder produces n | of a small number of source symbols each, and in a first round of | |||

encoding symbols considering all the k source symbols of an object as | transmission all of the source symbols for all the source blocks | |||

one block. The sender cycles through and transmits the n encoding | could be transmitted. Then, receivers could report back to the | |||

symbols in packets in the same order in each round. An FEC Data | sender the number of source symbols they are missing from each source | |||

Carousel can have much better protection against packet loss than a Data | block. The sender could then compute the maximum number of missing | |||

Carousel. For example, a receiver can join the transmission at any | source symbols from each source block among all receivers. Based on | |||

point in time, and, as long as the receiver receives at least k encoding | this, a small block FEC encoder could be used to generate for each | |||

symbols during the transmission of the next n encoding symbols, the | source block a number of redundant symbols equal to the computed | |||

receiver can completely recover the object. This is true even if the | maximum number of missing source symbols from the block among all | |||

receiver starts receiving packets in the middle of a pass through the | receivers, as long as this maximum maximum for each block does not | |||

encoding symbols. This method can also be used when the object is | exceed the number of redundant symbols that can be generated | |||

partitioned into blocks and a short block FEC code is applied to each | efficiently. In a second round of transmission, the server would | |||

block separately. In this case, as we explain in more detail below, it | then send all of these redundant symbols for all blocks. In this | |||

is useful to interleave the symbols from the different blocks when they | example, if there are no losses in the second round of transmission | |||

are transmitted. | then all receivers will be able to recreate an exact copy of each | |||

original block. In this case, even if different receivers are | ||||

missing different symbols in different blocks, transmitted redundant | ||||

symbols for a given block are useful to all receivers missing symbols | ||||

from that block in the second round. | ||||

Since any number of encoding symbols can be generated using an | For other reliable IP multicast protocols, FEC codes are used in a | |||

expandable FEC encoder, reliable IP multicast protocols that use | Data Carousel fashion to provide reliability, which we call an FEC | |||

expandable FEC codes generally rely solely on these codes for | Data Carousel. For example, an FEC Data Carousel using a large block | |||

reliability. For example, when an expandable FEC code is used in a FEC | FEC code could work as follows. The large block FEC encoder produces | |||

Data Carousel application, the encoding packets never repeat, and thus | n encoding symbols considering all the k source symbols of an object | |||

any k of the encoding symbols in the potentially unbounded number of | as one block. The sender cycles through and transmits the n encoding | |||

encoding symbols are sufficient to recover the original k source | symbols in packets in the same order in each round. An FEC Data | |||

symbols. | Carousel can have much better protection against packet loss than a | |||

Data Carousel. For example, a receiver can join the transmission at | ||||

any point in time, and, as long as the receiver receives at least k | ||||

encoding symbols during the transmission of the next n encoding | ||||

symbols, the receiver can completely recover the object. This is | ||||

true even if the receiver starts receiving packets in the middle of a | ||||

pass through the encoding symbols. This method can also be used when | ||||

the object is partitioned into blocks and a short block FEC code is | ||||

applied to each block separately. In this case, as we explain in | ||||

more detail below, it is useful to interleave the symbols from the | ||||

different blocks when they are transmitted. | ||||

For yet other reliable IP multicast protocols the method to obtain | Since any number of encoding symbols can be generated using an | |||

reliability is to generate enough encoding symbols so that each encoding | expandable FEC encoder, reliable IP multicast protocols that use | |||

symbol is transmitted at most once. For example, the sender can decide | expandable FEC codes generally rely solely on these codes for | |||

a priori how many encoding symbols it will transmit, use an FEC code to | reliability. For example, when an expandable FEC code is used in a | |||

generate that number of encoding symbols from the object, and then | FEC Data Carousel application, the encoding packets never repeat, and | |||

transmit the encoding symbols to all receivers. This method is for | thus any k of the encoding symbols in the potentially unbounded | |||

example applicable to streaming protocols, where the stream is | number of encoding symbols are sufficient to recover the original k | |||

partitioned into objects, the source symbols for each object are encoded | source symbols. | |||

into encoding symbols using an FEC code, and then the sets of encoding | ||||

symbols for each object are transmitted one after the other using IP | For additional reliable IP multicast protocols, the method to obtain | |||

multicast. | reliability is to generate enough encoding symbols so that each | |||

encoding symbol is transmitted only once (at most). For example, the | ||||

sender can decide a priori how many encoding symbols it will | ||||

transmit, use an FEC code to generate that number of encoding symbols | ||||

from the object, and then transmit the encoding symbols to all | ||||

receivers. This method is applicable to streaming protocols, for | ||||

example, where the stream is partitioned into objects, the source | ||||

symbols for each object are encoded into encoding symbols using an | ||||

FEC code, and then the sets of encoding symbols for each object are | ||||

transmitted one after the other using IP multicast. | ||||

2. FEC Codes | 2. FEC Codes | |||

2.1. Simple codes | 2.1. Simple codes | |||

There are some very simple codes that are effective for repairing packet | There are some very simple codes that are effective for repairing | |||

loss under very low loss conditions. For example, one simple way to | packet loss under very low loss conditions. For example, to provide | |||

provide protection from a single loss is to partition the object into | protection from a single loss is to partition the object into fixed | |||

fixed size source symbols and then add a redundant symbol that is the | size source symbols and then add a redundant symbol that is the | |||

parity (XOR) of all the source symbols. The size of a source symbol is | parity (XOR) of all the source symbols. The size of a source symbol | |||

chosen so that it fits perfectly into the payload of a packet, i.e. if | is chosen so that it fits perfectly into the payload of a packet, | |||

the packet payload is 512 bytes then each source symbol is 512 bytes. | i.e. if the packet payload is 512 bytes then each source symbol is | |||

The header of each packet contains enough information to identify the | 512 bytes. The header of each packet contains enough information to | |||

payload. In this case, this is an encoding symbol ID. The encoding | identify the payload. This is an example of encoding symbol ID. The | |||

symbol IDs can consist of two parts in this example. The first part is | encoding symbol IDs can consist of two parts in this example. The | |||

an encoding flag that is equal to 1 if the encoding symbol is a source | first part is an encoding flag that is equal to 1 if the encoding | |||

symbol and is equal to 0 if the encoding symbol is a redundant symbol. | symbol is a source symbol and is equal to 0 if the encoding symbol is | |||

The second part of the encoding symbol ID is a source symbol ID if the | a redundant symbol. The second part of the encoding symbol ID is a | |||

encoding flag is 1 and a redundant symbol ID if the encoding flag is 0. | source symbol ID if the encoding flag is 1 and a redundant symbol ID | |||

The source symbol IDs can be numbered from 0 to k-1 and the redundant | if the encoding flag is 0. The source symbol IDs can be numbered | |||

symbol ID can be 0. For example, if the object consists of four source | from 0 to k-1 and the redundant symbol ID can be 0. For example, if | |||

symbols that have values a, b, c and d, then the value of the redundant | the object consists of four source symbols that have values a, b, c | |||

symbol is e = a XOR b XOR c XOR d. Then, the packets carrying these | and d, then the value of the redundant symbol is e = a XOR b XOR c | |||

symbols look like | XOR d. Then, the packets carrying these symbols look like: | |||

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

In this example, the encoding symbol ID consists of the first two | (1, 0: a), (1, 1: b), (1, 2: c), (1, 3: d), (0, 0: e). | |||

values, where the first value is the encoding flag and the second value | ||||

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 | ||||

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

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

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

are received then the missing source symbol value with source symbol ID | In this example, the encoding symbol ID consists of the first two | |||

= 2 can be recovered by computing a XOR b XOR d XOR e = c. | values, where the first value is the encoding flag and the second | |||

value 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 single source symbol of the object can be recovered as | ||||

the parity of all the other symbols. For example, if packets | ||||

Another way of forming the encoding symbol ID is to let values 0,...,k-1 | (1, 0: a), (1, 1: b), (1, 3: d), (0, 0: e) | |||

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

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 | are received then the missing source symbol value with source symbol | |||

code variant of the above can be used. In this case, the source symbols | ID = 2 can be recovered by computing a XOR b XOR d XOR e = c. | |||

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 | ||||

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 | ||||

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

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

Slightly more sophisticated ways of adding redundant symbols using | Another way of forming the encoding symbol ID is to let values | |||

parity can also be used. For example, one can group a block consisting | 0,...,k-1 correspond to the k source symbols and value k correspond | |||

of k source symbols in an object into a p x p square matrix, where p = | to the redundant symbol that is the XOR of the k source symbols. | |||

sqrt(k). Then, for each row a redundant symbol is added that is the | ||||

parity of all the source symbols in the row. Similarly, for each column | When the number of source symbols in the object is large, a simple | |||

a redundant symbol is added that is the parity of all the source symbols | block code variant of the above can be used. In this case, the | |||

in the column. Then, any row of the matrix can be recovered from any p | source symbols are grouped together into source blocks of some number | |||

of the p+1 symbols in the row, and similarly for any column. Higher | k of consecutive symbols each, where k may be different for different | |||

dimensional product codes using this technique can also be used. | blocks. If a block consists of k source symbols then a redundant | |||

However, one must be wary of using these constructions without some | symbol is added to form an encoding block consisting of k+1 encoding | |||

thought towards the possible loss patterns of symbols. Ideally, the | symbols. Then, a source block consisting of k source symbols can be | |||

property that one would like to obtain is that if k source symbols are | recovered from any k of the k+1 encoding symbols from the associated | |||

encoded into n encoding symbols (the encoding symbols consist of the | encoding block. | |||

source symbols and the redundant symbols) then the k source symbols can | ||||

be recovered from any k of the n encoding symbols. Using the simple | Slightly more sophisticated ways of adding redundant symbols using | |||

constructions described above does not yield codes that come close to | parity can also be used. For example, one can group a block | |||

obtaining this ideal behavior. | consisting of k source symbols in an object into a p x p square | |||

matrix, where p = sqrt(k). Then, for each row a redundant symbol is | ||||

added that is the parity of all the source symbols in the row. | ||||

Similarly, for each column a redundant symbol is added that is the | ||||

parity of all the source symbols in the column. Then, any row of the | ||||

matrix can be recovered from any p of the p+1 symbols in the row, and | ||||

similarly for any column. Higher dimensional product codes using | ||||

this technique can also be used. However, one must be wary of using | ||||

these constructions without some thought towards the possible loss | ||||

patterns of symbols. Ideally, the property that one would like to | ||||

obtain is that if k source symbols are encoded into n encoding | ||||

symbols (the encoding symbols consist of the source symbols and the | ||||

redundant symbols) then the k source symbols can be recovered from | ||||

any k of the n encoding symbols. Using the simple constructions | ||||

described above does not yield codes that come close to obtaining | ||||

this ideal behavior. | ||||

2.2. Small block FEC codes | 2.2. Small block FEC codes | |||

Reliable IP multicast protocols may use a block (n, k) FEC code [2]. For | Reliable IP multicast protocols may use a block (n, k) FEC code [2]. | |||

such codes, k source symbols are encoded into n > k encoding symbols, | For such codes, k source symbols are encoded into n > k encoding | |||

such that any k of the encoding symbols can be used to reassemble the | symbols, such that any k of the encoding symbols can be used to | |||

original k source symbols. Thus, these codes have no reception overhead | reassemble the original k source symbols. Thus, these codes have no | |||

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

systematic, which means that the n encoding symbols consist of the k | Block codes are usually systematic, which means that the n encoding | |||

source symbols and n-k redundant symbols generated from these k source | symbols consist of the k source symbols and n-k redundant symbols | |||

symbols, where the size of a redundant symbol is the same as that for a | generated from these k source symbols, where the size of a redundant | |||

source symbol. For example, the first simple code (XOR) described in | symbol is the same as that for a source symbol. For example, the | |||

the previous subsection is a (k+1, k) code. In general, the freedom to | first simple code (XOR) described in the previous subsection is a | |||

choose n larger than k+1 is desirable, as this can provide much better | (k+1, k) code. In general, the freedom to choose n larger than k+1 | |||

protection against losses. A popular example of these types of codes is | is desirable, as this can provide much better protection against | |||

a class of Reed-Solomon codes, which are based on algebraic methods | losses. A popular example of these types of codes is a class of | |||

using finite fields. Implementations of (n, k) FEC erasure codes are | Reed-Solomon codes, which are based on algebraic methods using finite | |||

efficient enough to be used by personal computers [16]. For example, | fields. Implementations of (n, k) FEC erasure codes are efficient | |||

[15] describes an implementation where the encoding and decoding speeds | enough to be used by personal computers [16]. For example, [15] | |||

decay as C/j, where the constant C is on the order of 10 to 80 | describes an implementation where the encoding and decoding speeds | |||

Mbytes/second for Pentium class machines of various vintages and j is | decay as C/j, where the constant C is on the order of 10 to 80 | |||

upper bounded by min(k, n-k). | Mbytes/second for Pentium class machines of various vintages and j is | |||

upper bounded by 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 | |||

for such FEC codes as large values make encoding and decoding | 256) 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 | |||

reasonable values of k and the symbol length (e.g. larger than 16 | for 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 | |||

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

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

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

n encoding symbol encoding block, where the number n of encoding symbols | block into a n encoding symbol encoding block, where the number n of | |||

in the encoding block may vary for each source block. For a receiver to | encoding symbols in the encoding block may vary for each source | |||

completely recover the object, for each source block consisting of k | block. For a receiver to completely recover the object, for each | |||

source symbols, k distinct encoding symbols (i.e., with different | source block consisting of k source symbols, k distinct encoding | |||

encoding symbol IDs) must be received from the corresponding encoding | symbols (i.e., with different encoding symbol IDs) must be received | |||

block. For some encoding blocks, more encoding symbols may be received | from the corresponding encoding block. For some encoding blocks, | |||

than there are source symbols in the corresponding source block, in | more encoding symbols may be received than there are source symbols | |||

which case the excess encoding symbols are discarded. An example | in the corresponding source block, in which case the excess encoding | |||

encoding structure is shown in Figure 1. | symbols are discarded. An example encoding structure is shown in | |||

Figure 1. | ||||

| source symbol IDs | source symbols IDs | | | source symbol IDs | source symbols IDs | | |||

| of source block 0 | of source block 1 | | | of source block 0 | of source block 1 | | |||

| | | | | | |||

v v | v v | |||

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

|0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 | | |0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 | | |||

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

| | | | |||

FEC encoder | FEC encoder | |||

| | | | |||

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. The encoding structure for an object divided into two source | Figure 1. The encoding structure for an object divided into two | |||

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

generate 2 additional redundant symbols (10 encoding symbols in total) | encoder is used to generate 2 additional redundant symbols (10 | |||

for each of the two source blocks. | encoding symbols in total) 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 | |||

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

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

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

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

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

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

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

the disk seeks required. The block number and the source symbol ID | disk, as it reduces the disk seeks required. The block number and | |||

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

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

symbols, then the last source block will contain less than k symbols. | is not a multiple of k source symbols, then the last source block | |||

will contain less than k symbols. | ||||

The block numbers can be numbered consecutively starting from zero. | The block numbers can be numbered consecutively starting from zero. | |||

Encoding symbols within a block can be uniquely identified by an | Encoding symbols within a block can be uniquely identified by an | |||

encoding symbol ID. One way of identifying encoding symbols within a | encoding symbol ID. One way of identifying encoding symbols within a | |||

block is to use the combination of an encoding flag that identifies the | block is to use the combination of an encoding flag that identifies | |||

symbol as either a source symbol or a redundant symbol together with | the symbol as either a source symbol or a redundant symbol together | |||

either a source symbol ID or a redundant symbol ID. For example, an | with either a source symbol ID or a redundant symbol ID. For | |||

encoding flag value of 1 can indicate that the encoding symbol is a | example, an encoding flag value of 1 can indicate that the encoding | |||

source symbol and 0 can indicate that it is a redundant symbol. The | symbol is a source symbol and 0 can indicate that it is a redundant | |||

source symbol IDs can be numbered from 0 to k-1 and the redundant symbol | symbol. The source symbol IDs can be numbered from 0 to k-1 and the | |||

IDs can be numbered from 0 to n-k-1. | redundant symbol IDs can be numbered from 0 to n-k-1. | |||

For example, if the object consists 10 source symbols with values a, b, | For example, if the object consists 10 source symbols with values a, | |||

c, d, e, f, g, h, i, and j, and k = 5 and n = 8, then there are two | b, c, d, e, f, g, h, i, and j, and k = 5 and n = 8, then there are | |||

source blocks consisting of 5 symbols each, and there are two encoding | two source blocks consisting of 5 symbols each, and there are two | |||

blocks consisting of 8 symbols each. Let p, q and r be the values of | encoding blocks consisting of 8 symbols each. Let p, q and r be the | |||

the redundant symbols for the first encoding block, and let x, y and z | values of the redundant symbols for the first encoding block, and let | |||

be the values of the redundant symbols for the second encoding block. | x, y and z be the values of the redundant symbols for the second | |||

Then the encoding symbols together with their identifiers are | encoding block. Then the encoding symbols together with their | |||

identifiers are | ||||

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

(0, 0, 0: p), (0, 0, 1: q), (0, 0, 2: r), | (0, 0, 0: p), (0, 0, 1: q), (0, 0, 2: r), | |||

(1, 1, 0: f), (1, 1, 1: g), (1, 1, 2: h), (1, 1, 3: i), (1, 1, 4: j), | (1, 1, 0: f), (1, 1, 1: g), (1, 1, 2: h), (1, 1, 3: i), (1, 1, 4: j), | |||

(1, 0, 0: x), (1, 0, 1: y), (1, 0, 2: z). | (1, 0, 0: x), (1, 0, 1: y), (1, 0, 2: z). | |||

In this example, the first value identifies the block number and the | In this example, the first value identifies the block number and the | |||

second two values together identify the encoding symbol within the | second two values together identify the encoding symbol within the | |||

block, i.e, the encoding symbol ID consists of the encoding flag | block, i.e, the encoding symbol ID consists of the encoding flag | |||

together with either the source symbol ID or the redundant symbol ID | together with either the source symbol ID or the redundant symbol ID | |||

depending on the value of the encoding flag. The value of the encoding | depending on the value of the encoding flag. The value of the | |||

symbol is written after the colon. Each block can be recovered from any | encoding symbol is written after the colon. Each block can be | |||

5 of the 8 encoding symbols associated with that block. For example, | recovered from any 5 of the 8 encoding symbols associated with that | |||

reception of | block. For example, reception of | |||

(0, 1, 1: b), (0, 1, 2: c), (0, 1, 3: d), (0, 0, 0: p), (0, 0, 1: q) | (0, 1, 1: b), (0, 1, 2: c), (0, 1, 3: d), (0, 0, 0: p), (0, 0, 1: q) | |||

is sufficient to recover the first source block, and reception of | is sufficient to recover the first source block, and reception of | |||

(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 | |||

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

let the encoding symbol IDs for redundant symbols be k,...,n-1. | to 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 [12], [13], [10], [11], [9] are large block FEC codes that | Tornado codes [12], [13], [10], [11], [9] are large block FEC codes | |||

provide an alternative to small block FEC codes. An (n, k) Tornado code | that provide an alternative to small block FEC codes. An (n, k) | |||

requires slightly more than k out of n encoding symbols to recover k | Tornado code requires slightly more than k out of n encoding symbols | |||

source symbols, i.e., there is a small reception overhead. The benefit | to recover k source symbols, i.e., there is a small reception | |||

of the small cost of non-zero reception overhead is that the value of k | overhead. The benefit of the small cost of non-zero reception | |||

may be on the order of tens of thousands and still the encoding and | overhead is that the value of k may be on the order of tens of | |||

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

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

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

encoding and decoding speeds are tens of megabytes per second for | an implementation of Tornado codes where the encoding and decoding | |||

Pentium class machines of various vintages when k is in the tens of | speeds are tens of megabytes per second for Pentium class machines of | |||

thousands and n = 2k. The reception overhead for such values of k and n | various vintages when k is in the tens of thousands and n = 2k. The | |||

is in the 5-10% range. Tornado codes require a large amount of out of | reception overhead for such values of k and n is in the 5-10% range. | |||

band information to be communicated to all senders and receivers for | Tornado codes require a large amount of out of band information to be | |||

each different object length, and require an amount of memory on the | communicated to all senders and receivers for each different object | |||

encoder and decoder which is proportional to the object length times | length, and require an amount of memory on the encoder and decoder | |||

2n/k. | 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 | |||

Thus, to ensure that a receiver can reassemble the object with low | packets. Thus, to ensure that a receiver can reassemble the object | |||

reception overhead, the packets are permuted into a random order before | with low reception overhead, the packets are permuted into a random | |||

transmission. | order before transmission. | |||

2.4. Expandable FEC codes | 2.4. Expandable FEC codes | |||

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. | |||

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

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

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

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

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

encoder can generate as few or as many unique encoding symbols as | Instead, an expandable FEC encoder can generate as few or as many | |||

required on demand. | unique encoding symbols as required on demand. | |||

LT codes [6], [7], [8], [5] are an example of large expandable FEC codes | LT codes [6], [7], [8], [5] are an example of large expandable FEC | |||

with a small reception overhead. An LT encoder uses randomization to | codes with a small reception overhead. An LT encoder uses | |||

generate each encoding symbol randomly and independently of all other | randomization to generate each encoding symbol randomly and | |||

encoding symbols. Like Tornado codes, the number of source symbols k | independently of all other encoding symbols. Like Tornado codes, the | |||

may be very large for LT codes, i.e., on the order of tens to hundreds | number of source symbols k may be very large for LT codes, i.e., on | |||

of thousands, and the encoder and decoder run efficiently in software. | the order of tens to hundreds of thousands, and the encoder and | |||

For example the encoding and decoding speeds for LT codes are in the | decoder run efficiently in software. For example the encoding and | |||

range 3-20 megabytes per second for Pentium class machines of various | decoding speeds for LT codes are in the range 3-20 megabytes per | |||

vintages when k is in the high tens of thousands. An LT encoder can | second for Pentium class machines of various vintages when k is in | |||

generate as few or as many encoding symbols as required on demand. When | the high tens of thousands. An LT encoder can generate as few or as | |||

a new encoding symbol is to be generated by an LT encoder, it is based | many encoding symbols as required on demand. When a new encoding | |||

on a randomly chosen encoding symbol ID that uniquely describes how the | symbol is to be generated by an LT encoder, it is based on a randomly | |||

encoding symbol is to be generated from the source symbols. In general, | chosen encoding symbol ID that uniquely describes how the encoding | |||

each encoding symbol ID value corresponds to a unique encoding symbol, | symbol is to be generated from the source symbols. In general, each | |||

and thus the space of possible encoding symbols is approximately four | encoding symbol ID value corresponds to a unique encoding symbol, and | |||

billion if for example the encoding symbol ID is 4 bytes. Thus, the | thus the space of possible encoding symbols is approximately four | |||

chance that a particular encoding symbol is the same as any other | billion if for example the encoding symbol ID is 4 bytes. Thus, the | |||

particular encoding symbol is inversely proportional to the number of | chance that a particular encoding symbol is the same as any other | |||

possible encoding symbol IDs. An LT decoder has the property that with | particular encoding symbol is inversely proportional to the number of | |||

very high probability the receipt of any set of slightly more than k | possible encoding symbol IDs. An LT decoder has the property that | |||

randomly and independently generated encoding symbols is sufficient to | with very high probability the receipt of any set of slightly more | |||

reassemble the k source symbols. For example, when k is on the order of | than k randomly and independently generated encoding symbols is | |||

tens to hundreds of thousands the reception overhead is less than 5% | sufficient to reassemble the k source symbols. For example, when k | |||

with no failures in hundreds of millions of trials under any loss | is on the order of tens to hundreds of thousands the reception | |||

conditions. | overhead is less than 5% with no failures in hundreds of millions of | |||

trials under any loss conditions. | ||||

Because encoding symbols are randomly and independently generated by | Because encoding symbols are randomly and independently generated by | |||

choosing random encoding symbol IDs, LT codes have the property that | choosing random encoding symbol IDs, LT codes have the property that | |||

encoding symbols for the same k source symbols can be generated and | encoding symbols for the same k source symbols can be generated and | |||

transmitted from multiple senders and received by a receiver and the | transmitted from multiple senders and received by a receiver and the | |||

reception overhead and the decoding time is the same as if though all | reception overhead and the decoding time is the same as if though all | |||

the encoding symbols were generated by a single sender. The only | the encoding symbols were generated by a single sender. The only | |||

requirement is that the senders choose their encoding symbol IDs | requirement is that the senders choose their encoding symbol IDs | |||

randomly and independently of one another. | randomly and independently of one another. | |||

There is a weak tradeoff between the number of source symbols and the | There is a weak tradeoff between the number of source symbols and the | |||

reception overhead for LT codes, and the larger the number of source | reception overhead for LT codes, and the larger the number of source | |||

symbols the smaller the reception overhead. Thus, for shorter objects, | symbols the smaller the reception overhead. Thus, for shorter | |||

it is sometimes advantageous to partition the object into many short | objects, it is sometimes advantageous to partition the object into | |||

source symbols and include multiple encoding symbols in each packet. In | many short source symbols and include multiple encoding symbols in | |||

this case, a single encoding symbol ID is used to identify the multiple | each packet. In this case, a single encoding symbol ID is used to | |||

encoding symbols contained in a single packet. | identify the multiple encoding symbols contained in a single packet. | |||

There are a couple of factors for choosing the appropriate symbol | There are a couple of factors for choosing the appropriate symbol | |||

length/ number of source symbols tradeoff. The primary consideration is | length/ number of source symbols tradeoff. The primary consideration | |||

that there is a fixed overhead per symbol in the overall processing | is that there is a fixed overhead per symbol in the overall | |||

requirements of the encoding and decoding, independent of the number of | processing requirements of the encoding and decoding, independent of | |||

source symbols. Thus, using shorter symbols means that this fixed | the number of source symbols. Thus, using shorter symbols means that | |||

overhead processing per symbol will be a larger component of the overall | this fixed overhead processing per symbol will be a larger component | |||

processing requirements, leading to larger overall processing | of the overall processing requirements, leading to larger overall | |||

requirements. A second much less important consideration is that there | processing requirements. A second much less important consideration | |||

is a component of the processing per symbol that depends logarithmically | is that there is a component of the processing per symbol that | |||

on the number of source symbols, and thus for this reason there is a | depends logarithmically on the number of source symbols, and thus for | |||

slight preference towards fewer source symbols. | this reason there is a slight preference towards fewer source | |||

symbols. | ||||

Like small block codes, there is a point when the object is large enough | Like small block codes, there is a point when the object is large | |||

that it makes sense to partition it into blocks when using LT codes. | enough that it makes sense to partition it into blocks when using LT | |||

Generally the object is partitioned into blocks whenever the number of | codes. Generally the object is partitioned into blocks whenever the | |||

source symbols times the packet payload length is less than the size of | number of source symbols times the packet payload length is less than | |||

the object. Thus, if the packet payload is 1024 bytes and the maximum | the size of the object. Thus, if the packet payload is 1024 bytes | |||

number of source symbols is 128,000 then any object over 128 megabytes | and the maximum number of source symbols is 128,000 then any object | |||

will be partitioned into more than one block. One can choose the | over 128 megabytes will be partitioned into more than one block. One | |||

maximum number of source symbols to use, depending on the desired | can choose the maximum number of source symbols to use, depending on | |||

encoding and decoding speed versus reception overhead tradeoff desired. | the desired encoding and decoding speed versus reception overhead | |||

Encoding symbols can be uniquely identified by a block number (when the | tradeoff desired. Encoding symbols can be uniquely identified by a | |||

object is large enough to be partitioned into more than one block) and | block number (when the object is large enough to be partitioned into | |||

an encoding symbol ID. The block numbers, if they are used, are | more than one block) and an encoding symbol ID. The block numbers, | |||

generally numbered consecutively starting from zero within the object. | if they are used, are generally numbered consecutively starting from | |||

The block number and the encoding symbol ID are both chosen uniformly | zero within the object. The block number and the encoding symbol ID | |||

and randomly from their range when an encoding symbol is to be | are both chosen uniformly and randomly from their range when an | |||

transmitted. For example, suppose the number of source symbols is | encoding symbol is to be transmitted. For example, suppose the | |||

128,000 and the number of blocks is 2. Then, each packet generated by | number of source symbols is 128,000 and the number of blocks is 2. | |||

the LT encoder could be of the form (b, x: y). In this example, the | Then, each packet generated by the LT encoder could be of the form | |||

first value identifies the block number and the second value identifies | (b, x: y). In this example, the first value identifies the block | |||

the encoding symbol within the block. In this example, the block number | number and the second value identifies the encoding symbol within the | |||

b is either 0 or 1, and the encoding symbol ID x might be a 32-bit | block. In this example, the block number b is either 0 or 1, and the | |||

value. The value y after the colon is the value of the encoding symbol. | encoding symbol ID x might be a 32-bit value. The value y after the | |||

colon is the value of the encoding symbol. | ||||

2.5. Source blocks with variable length source symbols | 2.5. Source blocks with variable length source symbols | |||

For all the FEC codes described above, all the source symbols in the | For all the FEC codes described above, all the source symbols in the | |||

same source block are all of the same length. In this section, we | same source block are all of the same length. In this section, we | |||

describe a general technique to handle the case when it is desirable to | describe a general technique to handle the case when it is desirable | |||

use source symbols of varying lengths in a single source block. This | to use source symbols of varying lengths in a single source block. | |||

technique is applicable to block FEC codes. | This technique is applicable to block FEC codes. | |||

Let l_1, l_2, ... , l_k be the lengths in bytes of k varying length | Let l_1, l_2, ... , l_k be the lengths in bytes of k varying length | |||

source symbols to be considered part of the same source block. Let lmax | source symbols to be considered part of the same source block. Let | |||

be the maximum over i = 1, ... , k of l_i. To prepare the source block | lmax be the maximum over i = 1, ... , k of l_i. To prepare the | |||

for the FEC encoder, pad each source symbol i out to length lmax with a | source block for the FEC encoder, pad each source symbol i out to | |||

suffix of lmax-l_i zeroes, and then prepend to the beginning of this the | length lmax with a suffix of lmax-l_i zeroes, and then prepend to the | |||

value l_i. Thus, each padded source symbol is of length x+lmax, | beginning of this the value l_i. Thus, each padded source symbol is | |||

assuming that it takes x bytes to store an integer with possible values | of length x+lmax, assuming that it takes x bytes to store an integer | |||

0,...,lmax, where x is a protocol constant known to both the encoder and | with possible values 0,...,lmax, where x is a protocol constant known | |||

the decoder. These padded source symbols, each of length x+lmax, are | to both the encoder and the decoder. These padded source symbols, | |||

the input to the encoder, together with the value n. The encoder then | each of length x+lmax, are the input to the encoder, together with | |||

generates n-k redundant symbols, each of length x+lmax. | the value n. The encoder then generates n-k redundant symbols, each | |||

of length x+lmax. | ||||

The encoding symbols that are placed into packets consist of the | The encoding symbols that are placed into packets consist of the | |||

original k varying length source symbols and n-k redundant symbols, each | original k varying length source symbols and n-k redundant symbols, | |||

of length x+lmax. From any k of the received encoding symbols, the FEC | each of length x+lmax. From any k of the received encoding symbols, | |||

decoder recreates the k original source symbols as follows. If all k | the FEC decoder recreates the k original source symbols as follows. | |||

original source symbols are received, then no decoding is necessary. | If all k original source symbols are received, then no decoding is | |||

Otherwise, at least one redundant symbol is received, from which the | necessary. Otherwise, at least one redundant symbol is received, | |||

receiver can easily determine if the block is composed of variable- | from which the receiver can easily determine if the block is composed | |||

length source symbols: if the redundant symbol(s) is longer than the | of variable- length source symbols: if the redundant symbol(s) is | |||

source symbols then the source symbols are variable-length. Note that in | longer than the source symbols then the source symbols are variable- | |||

a variable-length block the redundant symbols are always longer than the | length. Note that in a variable-length block the redundant symbols | |||

longest source symbol, due to the presence of the prepended symbol- | are always longer than the longest source symbol, due to the presence | |||

length. The receiver can determine the value of lmax by subtracting x | of the prepended symbol- length. The receiver can determine the | |||

from the length of a received redundant symbol. For each of the | value of lmax by subtracting x from the length of a received | |||

received original source symbols, the receiver can generate the | redundant symbol. For each of the received original source symbols, | |||

corresponding padded source symbol as described above. Then, the input | the receiver can generate the corresponding padded source symbol as | |||

to the FEC decoder is the set of received redundant symbols, together | described above. Then, the input to the FEC decoder is the set of | |||

with the set of padded source symbols constructed from the received | received redundant symbols, together with the set of padded source | |||

original symbols. The FEC decoder then produces the set of k padded | symbols constructed from the received original symbols. The FEC | |||

source symbols. Once the k padded source symbols have been recovered, | decoder then produces the set of k padded source symbols. Once the k | |||

the length l_i of original source symbol i can be recovered from the | padded source symbols have been recovered, the length l_i of original | |||

first x bytes of the ith padded source symbol, and then original source | source symbol i can be recovered from the first x bytes of the ith | |||

symbol i is obtained by taking the next l_i bytes following the x bytes | padded source symbol, and then original source symbol i is obtained | |||

of the length field. | by taking the next l_i bytes following the x bytes of the length | |||

field. | ||||

3. Security Considerations | 3. Security Considerations | |||

The use of FEC, in and of itself, imposes no additional security | The use of FEC, in and of itself, imposes no additional security | |||

considerations versus sending the same information without FEC. | considerations versus sending the same information without FEC. | |||

However, just like for any transmission system, a malicious sender may | However, just like for any transmission system, a malicious sender | |||

try to inject packets carrying corrupted encoding symbols. If a | may try to inject packets carrying corrupted encoding symbols. If a | |||

receiver accepts one or more corrupted encoding symbol in place of | receiver accepts one or more corrupted encoding symbol, in place of | |||

authentic ones then such a receiver may reconstruct a corrupted object. | authentic ones, then such a receiver may reconstruct a corrupted | |||

object. | ||||

Application-level transmission object authentication can detect the | Application-level transmission object authentication can detect the | |||

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

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

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

denial of service attack. | an effective 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 | |||

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

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

may provide the capability of discarding multicast packets that | path of a FEC transfer may provide the capability of discarding | |||

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

correspond with that subnet. | address does not correspond with that subnet. | |||

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

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

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

from the received authenticated packets. | reliably recovered from the received authenticated packets. | |||

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

The IETF has been notified of intellectual property rights claimed in | The IETF has been notified of intellectual property rights claimed in | |||

regard to some or all of the specification contained in this document. | regard to some or all of the specification contained in this | |||

For more information consult the online list of claimed rights. | document. For more information consult the online list of claimed | |||

rights. | ||||

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 | |||

this draft. | on this document. | |||

6. References | 6. References | |||

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

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

pp.50-60, Dec 1995. | Communications, 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] Bradner, S., "The Internet Standards Process -- Revision 3", | [3] Bradner, S., "The Internet Standards Process -- Revision 3", BCP | |||

RFC2026, October 1996. | 9, RFC 2026, October 1996. | |||

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

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

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

[5] Haken, A., Luby, M., Horn, G., Hernek, D., Byers, J., Mitzenmacher, | [5] Haken, A., Luby, M., Horn, G., Hernek, D., Byers, J. and M. | |||

M., "Generating high weight encoding symbols using a basis", U.S. Patent | Mitzenmacher, "Generating high weight encoding symbols using a | |||

No. 6,411,223, June 25, 2002. | basis", U.S. Patent No. 6,411,223, June 25, 2002. | |||

[6] 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. | ||||

[7] Luby, M., "Information Additive Group Code Generator and Decoder for | [7] Luby, M., "Information Additive Group Code Generator and Decoder | |||

Communication Systems", U.S. Patent No. 6,320,520, November 20, 2001. | for Communication Systems", U.S. Patent No. 6,320,520, November | |||

20, 2001. | ||||

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

Communication Systems", U.S. Patent No. 6,373,406, April 16, 2002. | Communication Systems", U.S. Patent No. 6,373,406, April 16, | |||

2002. | ||||

[9] Luby, M., Mitzenmacher, ``Loss resilient code with double heavy | [9] Luby, M. and M. Mitzenmacher, "Loss resilient code with double | |||

tailed series of redundant layers'', U.S. Patent No. 6,195,777, February | heavy tailed series of redundant layers", U.S. Patent No. | |||

27, 2001. | 6,195,777, February 27, 2001. | |||

[10] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D., Stemann, | [10] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D. and V. | |||

V., ``Message encoding with irregular graphing'', U.S. Patent No. | Stemann, "Message encoding with irregular graphing", U.S. Patent | |||

6,163,870, December 19, 2000. | No. 6,163,870, December 19, 2000. | |||

[11] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D., | [11] Luby, M., Mitzenmacher, M., Shokrollahi, A. and D. Spielman, | |||

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

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

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

[12] Luby, M., Shokrollahi, A., Stemann, V., Mitzenmacher, M., Spielman, | [12] Luby, M., Shokrollahi, A., Stemann, V., Mitzenmacher, M. and D. | |||

D., ``Loss resilient decoding technique'', U.S. Patent No. 6,073,250, | Spielman, "Loss resilient decoding technique", U.S. Patent No. | |||

June 6, 2000. | 6,073,250, June 6, 2000. | |||

[13] Luby, M., Shokrollahi, A., Stemann, V., Mitzenmacher, M., Spielman, | [13] Luby, M., Shokrollahi, A., Stemann, V., Mitzenmacher, M. and D. | |||

D., ``Irregularly graphed encoding technique'', U.S. Patent No. | Spielman, "Irregularly graphed encoding technique", U.S. Patent | |||

6,081,909, June 27, 2000. | No. 6,081,909, June 27, 2000. | |||

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

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

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

February 2001. | ||||

[15] Rizzo, L., ``Effective Erasure Codes for Reliable Computer | [15] Rizzo, L., "Effective Erasure Codes for Reliable Computer | |||

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

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

[16] Rizzo, L., ``On the Feasibility of Software FEC'', DEIT Tech | [16] Rizzo, L., "On the Feasibility of Software FEC", DEIT Tech | |||

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

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

Michael Luby | Michael Luby | |||

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 | |||

EMail: luby@digitalfountain.com | ||||

Lorenzo Vicisano | Lorenzo Vicisano | |||

lorenzo@cisco.com | Cisco Systems, Inc. | |||

cisco Systems, Inc. | ||||

170 West Tasman Dr., | 170 West Tasman Dr., | |||

San Jose, CA, USA, 95134 | San Jose, CA, USA, 95134 | |||

EMail: lorenzo@cisco.com | ||||

Jim Gemmell | Jim Gemmell | |||

jgemmell@microsoft.com | ||||

Microsoft Research | Microsoft Research | |||

301 Howard St., #830 | 455 Market St. #1690 | |||

San Francisco, CA, USA, 94105 | San Francisco, CA, 94105 | |||

EMail: jgemmell@microsoft.com | ||||

Luigi Rizzo | Luigi Rizzo | |||

luigi@iet.unipi.it | ||||

Dip. di Ing. dell'Informazione | Dip. di Ing. dell'Informazione | |||

Universita` di Pisa | Universita` di Pisa | |||

via Diotisalvi 2, 56126 Pisa, Italy | via Diotisalvi 2, 56126 Pisa, Italy | |||

EMail:luigi@iet.unipi.it | ||||

Mark Handley | Mark Handley | |||

mjh@icir.org | ||||

ICSI Center for Internet Research | ICSI Center for Internet Research | |||

1947 Center St. | 1947 Center St. | |||

Berkeley CA, USA, 94704 | Berkeley CA, USA, 94704 | |||

EMail: mjh@icir.org | ||||

Jon Crowcroft | Jon Crowcroft | |||

J.Crowcroft@cl.cam.ac.uk | ||||

Marconi Professor of Communications Systems | Marconi Professor of Communications Systems | |||

University of Cambridge | University of Cambridge | |||

Computer Laboratory | Computer Laboratory | |||

William Gates Building | William Gates Building | |||

J J Thomson Avenue | J J Thomson Avenue | |||

Cambridge | Cambridge | |||

CB3 0FD | CB3 0FD | |||

EMail: Jon.Crowcroft@cl.cam.ac.uk | ||||

8. Full Copyright Statement | 8. Full Copyright Statement | |||

Copyright (C) The Internet Society (2002). All Rights Reserved. | Copyright (C) The Internet Society (2002). All Rights Reserved. | |||

This document and translations of it may be copied and furnished to | This document and translations of it may be copied and furnished to | |||

others, and derivative works that comment on or otherwise explain it or | others, and derivative works that comment on or otherwise explain it | |||

assist in its implementation may be prepared, copied, published and | or assist in its implementation may be prepared, copied, published | |||

distributed, in whole or in part, without restriction of any kind, | and distributed, in whole or in part, without restriction of any | |||

provided that the above copyright notice and this paragraph are included | kind, provided that the above copyright notice and this paragraph are | |||

on all such copies and derivative works. However, this document itself | included on all such copies and derivative works. However, this | |||

may not be modified in any way, such as by removing the copyright notice | document itself may not be modified in any way, such as by removing | |||

or references to the Internet Society or other Internet organizations, | the copyright notice or references to the Internet Society or other | |||

except as needed for the purpose of developing Internet standards in | Internet organizations, except as needed for the purpose of | |||

which case the procedures for copyrights defined in the Internet | developing Internet standards in which case the procedures for | |||

languages other than English. | copyrights defined in the Internet Standards process must be | |||

followed, or as required to translate it into languages other than | ||||

English. | ||||

The limited permissions granted above are perpetual and will not be | The limited permissions granted above are perpetual and will not be | |||

revoked by the Internet Society or its successors or assigns. | revoked by the Internet Society or its successors or assigns. | |||

This document and the information contained herein is provided on an "AS | This document and the information contained herein is provided on an | |||

IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK | "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING | |||

FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT | TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING | |||

LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT | BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION | |||

INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR | HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF | |||

FITNESS FOR A PARTICULAR PURPOSE." | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. | |||

Acknowledgement | ||||

Funding for the RFC Editor function is currently provided by the | ||||

Internet Society. | ||||

End of changes. 95 change blocks. | ||||

633 lines changed or deleted | | 660 lines changed or added | ||

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ |