Network Working Group                                            M. Luby
Request for Comments: 3453                              Digital Fountain
Category: Informational                                      L. Vicisano
                                                              J. Gemmell
                                                                L. Rizzo
                                                              Univ. Pisa
                                                              M. Handley
                                                            J. Crowcroft
                                                         Cambridge Univ.
                                                           December 2002
    The Use of Forward Error Correction (FEC) in Reliable Multicast

Status of this Memo


This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.


Copyright Notice


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




This memo describes the use of Forward Error Correction (FEC) codes to efficiently provide and/or augment reliability for one-to-many reliable data transport using IP multicast. One of the key properties of FEC codes in this context is the ability to use the same packets containing FEC data to simultaneously repair different packet loss patterns at multiple receivers. Different classes of FEC codes and some of their basic properties are described and terminology relevant to implementing FEC in a reliable multicast protocol is introduced. Examples are provided of possible abstract formats for packets carrying FEC.

このメモは効率的に提供及び/又はIPマルチキャストを用いて一対多信頼できるデータ転送のための信頼性を増強するための前方誤り訂正(FEC)符号の使用を記載しています。この文脈において、FECコードの重要な特性の一つは、同時に複数の受信機に異なるパケット損失パターンを修復するFECデータを含む同じパケットを使用する能力です。 FECコードとその基本的な性質のいくつかの異なるクラスが記載されており、信頼性の高いマルチキャストプロトコルにFECを実装に関連する用語が導入されます。例としては、FECを運ぶパケットのための可能な抽象フォーマットで提供されています。

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

There are many ways to provide reliability for transmission protocols. A common method is to use ARQ, automatic request for retransmission. With ARQ, receivers use a back channel to the sender to send requests for retransmission of lost packets. ARQ works well for one-to-one reliable protocols, as evidenced by the pervasive success of TCP/IP. ARQ has also been an effective reliability tool for one-to-many reliability protocols, and in particular for some reliable IP multicast protocols. However, for one-to-very-many reliability protocols, ARQ has limitations, including the feedback implosion problem because many receivers are transmitting back to the sender, and the need for a back channel to send these requests from the receiver. Another limitation is that receivers may experience different loss patterns of packets, and thus receivers may be delayed by retransmission of packets that other receivers have lost that but they have already received. This may also cause wasteful use of bandwidth used to retransmit packets that have already been received by many of the receivers.

伝送プロトコルのための信頼性を提供するために多くの方法があります。一般的な方法はARQ再送の自動要求を使用することです。 ARQでは、受信機は、失われたパケットの再送信のための要求を送信する送信者に戻ってチャンネルを使用しています。 TCP / IPの普及の成功によって証明されるようにARQは、一対一の信頼性の高いプロトコルに適しています。 ARQはまた、1対多の信頼性プロトコルのための効果的な信頼性のツールとなって、そしていくつかの信頼性の高いIPマルチキャストプロトコルのために特にました。多くの受信機は、送信者に戻って送信し、受信機からのこれらの要求を送信するバックチャネルを必要としているのでしかし、1対非常に-多くの信頼性のプロトコルのために、ARQフィードバック爆縮問題など、制限があります。別の制限は、受信機がパケットの異なる損失パターンを経験し得ることであるので、受信機は、他の受信機がそれを失っているが、それらは既に受信したパケットの再送によって遅延されてもよいです。また、これは、すでに受信機の多くが受信したパケットを再送するために使用される帯域幅の無駄な使用を引き起こす可能性があります。

In environments where ARQ is either costly or impossible because there is either a very limited capacity back channel or no back channel at all, such as satellite transmission, a Data Carousel approach to reliability is sometimes used [1]. With a Data Carousel, the sender partitions the object into equal length pieces of data, which we hereafter call source symbols, places them into packets, and then continually cycles through and sends these packets. Receivers continually receive packets until they have received a copy of each packet. Data Carousel has the advantage that it requires no back channel because there is no data that flows from receivers to the sender. However, Data Carousel also has limitations. For example, if a receiver loses a packet in one round of transmission it must wait an entire round before it has a chance to receive that packet again. This may also cause wasteful use of bandwidth, as the sender continually cycles through and transmits the packets until no receiver is missing a packet.


Forward Error Correction (FEC) codes provide a reliability method that can be used to augment or replace other reliability methods, especially for one-to-many reliability protocols such as reliable IP multicast. We first briefly review some of the basic properties and types of FEC codes before reviewing their uses in the context of 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 erasures (losses) and bit-level corruption. However, in the case of an IP multicast protocol, the network layers will detect corrupted packets and discard them or the transport layers can use packet authentication 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 reassembled from reception of packets containing the generated encoding using the corresponding FEC erasure decoder.


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 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 fixed. These encoding symbols are placed into packets for transmission. 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 into each packet. Also, in each packet is placed enough information to identify the particular encoding symbols carried in that packet. Upon receipt of packets containing encoding symbols, the receiver feeds these encoding symbols into the corresponding FEC decoder to recreate an exact copy of the k source symbols. Ideally, the FEC decoder can recreate an exact copy from any k of the encoding symbols.

FECエンコーダへの入力は、等しい長さのソースシンボルのいくつかの数kです。 FEC符号器は、ソースシンボルと同じ長さである符号化シンボルのいくつかの数を生成します。シンボルの選択された長さは、FEC符号器の各用途に変えることができ、またはそれを固定することができます。これらの符号化シンボルを送信するためのパケットに配置されます。各パケットに入れ符号化シンボルの数パケット毎に変化することができる、またはシンボルの固定数(多くの場合、1つ)が、各パケットに入れることができます。また、各パケットに、そのパケットで運ば特定の符号化シンボルを識別するために十分な情報が配置されています。符号化シンボルを含むパケットを受信すると、受信機は、K個のソースシンボルの正確なコピーを再作成するために、対応するFECデコーダにこれらの符号化シンボルを供給する。理想的には、FECデコーダは、符号化シンボルのいずれkから正確なコピーを再作成することができます。

In a later section, we describe a technique for using FEC codes as 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 source symbols and a number n. The encoder generates a total of n encoding symbols. The encoder is systematic if it generates n-k 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 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 as input k source symbols and generates as many unique encoding symbols as requested on demand, where the amount of time for generating each 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 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, 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 overhead is ep*100%, e.g., if k*1.05 encoding symbols are needed then the reception overhead is 5%.

任意のk個の符号化シンボルの受信が、その場合、受信オーバヘッドが0%、K個のソースシンボルを回復するのに十分である場合、上記の定義は、理想的な状況を説明します。いくつかの実用的なFEC符号は、k個の符号化シンボルが必要とされるわずかに超えるK個のソースシンボルを回復します。 K×(1枚の+ EP)符号化シンボルが必要な場合はK * 1.05符号化シンボルが必要な場合、我々は受信オーバヘッドがEP * 100%であると言う、例えば、次に受信オーバヘッドは5%です。

Along a different dimension, we classify FEC codes loosely as being either small or large. A small FEC code is efficient in terms of processing time requirements for encoding and decoding for small values 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 that have encoding times proportional to n-k times the length of the k 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 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.

異なる次元に沿って、我々は緩く、小規模または大規模のいずれかであるとしてFECコードを分類します。小さいFECコードは、kの小さな値の符号化および復号化の処理時間の要件の点で効率的であり、そして大FECコードは、kのはるかに大きな値のための符号化及び復号化のために効率的です。 L倍に比例したNK倍に比例したk個のソースシンボルの長さを倍をコードしているブロックFECコードの実装、および復号時間は、Lは、Kのうち、欠落したソースシンボルの数であるk個のソースシンボルの長さがあります受信された符号化シンボル、LはKと同じ大きさであることができます。なぜならkおよびN-Kの積として符号化及び復号化時間の成長速度で、これらは、典型的には、小ブロックFECコードであると考えられます。 n個の符号化シンボルを生成することができ、n個の符号化シンボルの長さに比例した時間でk個のソースシンボルを復号することができる小型の受信オーバーヘッドでブロックFECコードがあります。これらのコードは、大きなブロックのFEC符号であると考えられています。その長さにほぼ比例した時間内に各符号化シンボルを生成することができ、そしてそれらの長さにほぼ比例した時間内にすべてのK個のソースシンボルを復号することができる小型の受信オーバーヘッドで拡張可能なFEC符号があります。これらは、大規模な拡張可能なFECコードであると考えられています。私たちは、後にコードのこれらのタイプのすべての例を記載しています。

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.


1.1. Application of FEC codes
1.1. FECコードの応用

For some reliable IP multicast protocols, FEC codes are used in 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 Carousel fashion to provide reliability, which we call an FEC Data Carousel. For example, an FEC Data Carousel using a large block FEC code could work as follows. The large block FEC encoder produces n encoding symbols considering all the k source symbols of an object as one block. The sender cycles through and transmits the n encoding symbols in packets in the same order in each round. An FEC Data 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.

他の信頼できるIPマルチキャストプロトコルのために、FECコードは、私たちがFECデータカルーセルを呼び出して、信頼性を提供するために、データカルーセル方式で使用されています。たとえば、次のように大ブロックFECコードを使用してFECデータカルーセルは、仕事ができます。大ブロックFECエンコーダは、1つのブロックとしてオブジェクトのすべてのK個のソースシンボルを考慮して、n個の符号化シンボルを生成します。センダサイクルを介して、各ラウンドにおいて同じ順序でパケット内のN個の符号化シンボルを送信します。 FECデータカルーセルは、データカルーセルよりもパケット損失に対するより良い保護を持つことができます。例えば、受信機は、任意の時点での伝送に参加することができ、そして、限り、受信機が次のn個の符号化シンボルの送信中に少なくともk個の符号化シンボルを受信するように、受信機は、完全にオブジェクトを回復することができます。これは、受信機は、符号化シンボルを通るパスの途中でパケットの受信を開始する場合も同様です。オブジェクトがブロックに分割され、ショートブロックFECコードが別々に各ブロックに適用されたときに、この方法を使用することもできます。我々は、以下により詳細に説明するように、この場合には、彼らが送信されたときに異なるブロックからシンボルをインタリーブするのに便利です。

Since any number of encoding symbols can be generated using an expandable FEC encoder, reliable IP multicast protocols that use expandable FEC codes generally rely solely on these codes for reliability. For example, when an expandable FEC code is used in a FEC Data Carousel application, the encoding packets never repeat, and thus any k of the encoding symbols in the potentially unbounded number of encoding symbols are sufficient to recover the original k source symbols.


For additional reliable IP multicast protocols, the method to obtain 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コード
2.1. Simple codes
2.1. シンプルなコード

There are some very simple codes that are effective for repairing packet loss under very low loss conditions. For example, to provide protection from a single loss is to partition the object into fixed 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 chosen so that it fits perfectly into the payload of a packet, i.e. if the packet payload is 512 bytes then each source symbol is 512 bytes. The header of each packet contains enough information to identify the payload. This is an example of encoding symbol ID. The encoding symbol IDs can consist of two parts in this example. The first part is an encoding flag that is equal to 1 if the encoding symbol is a source symbol and is equal to 0 if the encoding symbol is a redundant symbol. The second part of the encoding symbol ID is a source symbol ID if the encoding flag is 1 and a redundant symbol ID if the encoding flag is 0. The source symbol IDs can be numbered from 0 to k-1 and the redundant symbol ID can be 0. For example, if the object consists of four source symbols that have values a, b, c and d, then the value of the redundant symbol is e = a XOR b XOR c XOR d. Then, the packets carrying these symbols look like:

非常に低損失の条件の下でパケット損失を修復するのに有効であるいくつかの非常に単純なコードがあります。例えば、単一の損失からの保護を提供するために固定サイズのソースシンボルにオブジェクトを分割し、すべてのソースシンボルのパリティ(XOR)である冗長シンボルを追加することです。パケットペイロードが512バイトである場合、それは、パケットのペイロードの中に完全に収まるようにソースシンボルのサイズが選択され、すなわち各ソースシンボルは512バイトです。各パケットのヘッダは、ペイロードを識別するのに十分な情報を含んでいます。これは、シンボルIDを符号化する例です。符号化シンボルIDは、この例では2つの部分で構成することができます。最初の部分は、符号化シンボルは、ソースシンボルであり、符号化シンボルは、冗長シンボルである場合は0に等しい場合1に等しく、符号化フラグです。符号化フラグはソースシンボルIDはK-1を0から番号付けすることができ、冗長シンボルIDができ0である場合、符号化フラグが1と冗長シンボルIDである場合、符号化シンボルIDの第2の部分は、ソースシンボルIDでありますオブジェクトが値、B、CおよびDを有する4つのソースシンボルで構成されている場合、その後、冗長シンボルの値がEであり、例えば0で= XOR B型のXOR C XOR Dを。次に、これらのシンボルを搬送するパケットは次のようになります。

(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 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 = 2 can be recovered by computing a XOR b XOR d XOR e = c.

その後のXOR B XOR d個のXOR電子= Cを計算することによって回収することができるソースシンボルID = 2の欠落したソースシンボル値を受信して​​います。

Another way of forming the encoding symbol ID is to let values 0,...,k-1 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 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 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.

オブジェクト内のソースシンボルの数が多い場合、上記の単純なブロックコード変異体を使用することができます。この場合、ソースシンボルは、kが異なるブロックについて異なることができる連続したシンボルそれぞれ、いくつかの数kのソースブロックに一緒にグループ化されます。ブロックは、次に、K個のソースシンボルから構成されている場合、冗長シンボルがk + 1つの符号化シンボルからなる符号化ブロックを形成するために添加されます。その後、K個のソースシンボルからなるソースブロックは、関連する符号化ブロックからK + 1符号化シンボルのいずれkから回収することができます。

Slightly more sophisticated ways of adding redundant symbols using 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 = 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.

パリティを使用して冗長シンボルを追加するもう少し洗練された方法を用いることも可能です。例えば、一つの缶群のP X Pの正方行列、にオブジェクトのKのソースシンボルからなるブロックここで、p = SQRT(K)。次いで、行ごとに冗長シンボルは、行のすべてのソースシンボルのパリティである添加されます。同様に、各列の冗長シンボルは、列内のすべてのソースシンボルのパリティであることが追加されます。次いで、行列の任意の行は、行のp + 1つのシンボルの任意Pから回収することができ、同様に任意の列のため。この技術を用いて、より高い次元の製品コードを使用することもできます。しかし、1シンボルの損失の可能性パターンに向けたいくつかの考えなしにこれらの構造を使用しての警戒する必要があります。理想的には、一方が取得したいプロパティは、K個のソースシンボルは、N個の符号化シンボルに符号化されるならば、K個のソースシンボルは、Nの任意kから回収することができる(符号化シンボルは、ソースシンボルおよび冗長シンボルから成る)ことです符号化シンボル。上述した単純な構成を使用すると、この理想的な挙動を得るに近づくコードが得られません。

2.2. Small block FEC codes
2.2. 小ブロックFECコード

Reliable IP multicast protocols may use a block (n, k) FEC code [2]. For such codes, k source symbols are encoded into n > k encoding symbols, such that any k of the encoding symbols can be used to reassemble the original k source symbols. Thus, these codes have no reception overhead when used to encode the entire object directly. Block codes are usually systematic, which means that the n encoding symbols consist of the k 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 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 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 a class of Reed-Solomon codes, which are based on algebraic methods using finite fields. Implementations of (n, k) FEC erasure codes are efficient enough to be used by personal computers [16]. For example, [15] 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 for Pentium class machines of various vintages and j is upper bounded by min(k, n-k).

信頼できるIPマルチキャストプロトコル[2]ブロック(n、k)はFECコードを使用してもよいです。このようなコードのために、K個のソースシンボルは、符号化シンボルのいずれkは元のk個のソースシンボルを再構築するために使用することができるように、N> K個の符号化シンボルに符号化されます。直接オブジェクト全体を符号化するために使用される場合したがって、これらのコードには、受信オーバーヘッドを有していません。ブロック符号は、n個の符号化シンボルは、K個のソースシンボルおよび冗長シンボルのサイズは、ソースシンボルと同じであり、これらのk個のソースシンボルから生成されたN-k個の冗長シンボル、からなることを意味し、通常は系統的です。例えば、前節で説明した第1の単純なコード(XOR)が(K + 1、K)符号です。これは損失に対するより良い保護を提供することが可能と一般的には、K + 1 nより大きな選択する自由は、望ましいです。コードのこれらのタイプの一般的な例は、有限フィールドを使用して、代数的方法に基づいているリードソロモン符号のクラスです。 (n、k)はFEC消去符号の実装は、パーソナルコンピュータ、[16]で使用されるのに十分に効率的です。例えば、[15]の符号化及び復号化は定数Cは分によって上部に制限される10〜80バイト/さまざまなヴィンテージとjのPentiumクラスのマシンのための第二のオーダーであるC / J、として減衰速度実装について説明します(K、NK)。

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 prohibitively expensive. As many objects are longer than k symbols 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 a number of source blocks. Each source block consists of some number k 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 n encoding symbol encoding block, where the number n of encoding symbols in the encoding block may vary for each source block. For a receiver to completely recover the object, for each source block consisting of k source symbols, k distinct encoding symbols (i.e., with different encoding symbol IDs) must be received from the corresponding encoding block. For some encoding blocks, more encoding symbols may be received than there are source symbols in the corresponding source block, in which case the excess encoding symbols are discarded. An example encoding structure is shown in Figure 1.

大きな値は、符号化及び復号化は法外に高価なものとして、実際には、kの値は、nは小さいようなFECコードについて(256以下など)でなければなりません。多くのオブジェクトをkとシンボル長(1キロバイトのシンボルを使用して、K = 16のために16キロバイトよりも例えば大きい)の妥当な値のk個のシンボルよりも長い、それらは、ソースブロックの数に分割することができます。各ソースブロックは、kは、異なるソースブロックの間で変化し得るソースシンボル、いくつかの数kから成ります。 FECエンコーダは、符号化ブロック内の符号化シンボルの数nは、各ソースブロックに対して変化してもよいn個の符号化シンボルを符号化ブロックにk個のソースシンボルのソースブロックを符号化するために使用されます。完全にオブジェクトを回復する受信機のために、K個のソースシンボルからなる各ソースブロックについて、(すなわち、異なる符号化シンボルIDを持つ)異なる符号化シンボルをk個の対応する符号化ブロックから受信されなければなりません。いくつかの符号化ブロックのために、より多くの符号化シンボルは、過剰な符号化シンボルが破棄される場合に対応するソースブロック内のソースシンボルが、そこよりも受信することができます。例えば、符号化構造は、図1に示されています。

       |   source symbol IDs   |   source symbols IDs  |
       |   of source block 0   |   of source block 1   |
                    |                          |
                    v                          v
       |0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 |
                           FEC encoder
   |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         |
   |  of encoding block 0        | of encoding block 1         |

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 generate 2 additional redundant symbols (10 encoding symbols in total) for each of the two 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., 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 number k of source symbols. This also ensures that memory references are local when the sender reads source symbols to encode, and when the receiver reads encoding symbols to decode. Locality of reference is particularly important when the object is stored on disk, as it reduces 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 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.

多くの場合、オブジェクトは、各オブジェクトのk個の連続するソースシンボルから成る同じ長ソースブロックに分割され、すなわち、ブロックCは、ソースシンボルの範囲[CK、(C + 1)は、k-1]から成ります。これは、FEC符号器は、ソースシンボルの特定の数kを処理するように最適化することができることを確実にします。これはまた、送信者がコード化するためにソースシンボルを読み出し、受信機は、符号化シンボルを読み取る際に復号化するときに、メモリ参照がローカルであることを保証します。オブジェクトがディスク上に格納されている場合は、ディスクが必要シーク減少として参照の局所性は、特に重要です。ブロック番号とそのブロック内のソースシンボルIDは、一意のオブジェクト内のソースシンボルを指定するために使用することができます。オブジェクトのサイズは、K個のソースシンボルの倍数でない場合、最後のソースブロックは、k個のシンボル未満を含有します。

The block numbers can be numbered consecutively starting from zero. Encoding symbols within a block can be uniquely identified by an encoding symbol ID. One way of identifying encoding symbols within a block is to use the combination of an encoding flag that identifies the symbol as either a source symbol or a redundant symbol together with either a source symbol ID or a redundant symbol ID. For example, an encoding flag value of 1 can indicate that the encoding symbol is a source symbol and 0 can indicate that it is a redundant symbol. The source symbol IDs can be numbered from 0 to k-1 and the 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, c, d, e, f, g, h, i, and j, and k = 5 and n = 8, then there are two source blocks consisting of 5 symbols each, and there are two encoding blocks consisting of 8 symbols each. Let p, q and r be the values of the redundant symbols for the first encoding block, and let x, y and z be the values of the redundant symbols for the second encoding block. Then the encoding symbols together with their identifiers are

オブジェクトは、値A、B、C、D、E、F、G、H、I、およびJ、及びK = 5、N = 8と10個のソースシンボルからなる場合、例えば、次にからなる二つのソースブロックが存在します5つのシンボル毎、8つのシンボル毎からなる二符号化ブロックが存在します。 P、QおよびRは、第1の符号化ブロックのための冗長シンボルの値とすると、X、YおよびZは、第2の符号化ブロックのための冗長シンボルの値とします。そして、符号化シンボルは、一緒にその識別子であります

(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), (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).

(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)、(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)。

In this example, the first value identifies the block number and the second two values together identify the encoding symbol within the block, i.e, the encoding symbol ID consists of the encoding flag 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 symbol is written after the colon. Each block can be recovered from any 5 of the 8 encoding symbols associated with that 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)


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)


is sufficient to recover the second source block.


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 let the encoding symbol IDs for redundant symbols be k,...,n-1.


2.3. Large block FEC codes
2.3. 大ブロックFECコード

Tornado codes [12], [13], [10], [11], [9] are large block FEC codes that provide an alternative 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., there is a small reception overhead. The benefit of the small cost of non-zero reception overhead is that the value of k may be on the order of tens of thousands and still the encoding and decoding are efficient. Because of memory considerations, in practice the value of n is 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 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% range. Tornado codes require a large amount of out of band information to be communicated to all senders and receivers for each different object length, and require an amount of memory on the encoder and decoder which is proportional to the object length times 2n/k.

トルネード符号[12]、[13]、[10]、[11]、[9]小ブロックFECコードに代わるものを提供する大規模なブロックFECコードです。 (N、K)トルネード符号、すなわち、小受信オーバヘッドがある、k個のソースシンボルを回復するために、n個の符号化シンボルのうちKよりわずかに多くを必要とします。非ゼロの受信オーバヘッドの小さなコストの利点は、kの値は、数万のオーダーであってもよく、依然として符号化および復号化が効率的であるということです。なぜなら、メモリの考慮事項のため、実際にはnの値がN = 2Kを、例えばk個の小さな倍数に制限されます。例えば、[4]、kは数万であり、n = 2kのとき符号化及び復号化速度は、様々なヴィンテージのPentiumクラスのマシンの毎秒メガバイト数十あるトルネード符号の実装を記述する。 K、Nのような値の受信オーバヘッドは5~10%の範囲です。トルネード符号はそれぞれ、異なる物体長のためのすべての送信者と受信者に通信される帯域情報のうちの大量を必要とし、物体の長さの時間2N / Kに比例し、エンコーダとデコーダのメモリの量を必要とします。

Tornado codes are designed to have low reception overhead on average with respect to reception of a random portion of the encoding packets. Thus, to ensure that a receiver can reassemble the object with low reception overhead, the packets are permuted into a random order before transmission.


2.4. Expandable FEC codes
2.4. 拡張FECコード

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. Like block codes, an expandable FEC encoder operates on an object of known size that is partitioned into equal length source symbols. Unlike block codes, there is no predetermined number of encoding symbols that can be generated for expandable FEC codes. Instead, an expandable FEC encoder can generate as few or as many unique encoding symbols as required on demand.


LT codes [6], [7], [8], [5] are an example of large expandable FEC codes with a small reception overhead. An LT encoder uses randomization to generate each encoding symbol randomly and independently of all other encoding 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, 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 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 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 chosen encoding symbol ID that uniquely describes how the encoding symbol is to be generated from the source symbols. In general, each encoding symbol ID value corresponds to a unique encoding symbol, and thus the space of possible encoding symbols is approximately four billion if for example the encoding symbol ID is 4 bytes. Thus, the chance that a particular encoding symbol is the same as any other particular encoding symbol is inversely proportional to the number of possible encoding symbol IDs. An LT decoder has the property that with very high probability the receipt of any set of slightly more than k randomly and independently generated encoding symbols is sufficient to reassemble the k source symbols. For example, when k is on the order of tens to hundreds of thousands the reception overhead is less than 5% with no failures in hundreds of millions of trials under any loss conditions.

LT符号は、[6]、[7]、[8]、[5]小受信オーバーヘッドで大きな拡張可能なFECコードの一例です。 LT符号は、ランダムかつ独立に、他のすべての符号化シンボルの各符号化シンボルを生成するためにランダム化を使用します。トルネード符号のような、ソースシンボルkの数は数千から数百数十、ソフトウェアにおいて効率的に実行するエンコーダおよびデコーダで、LTコード、即ちため非常に大きくてもよいです。 kは、数千の高い数十であるとき、例えばLT符号の符号化および復号化の速度は、様々なヴィンテージのPentiumクラスのマシンの毎秒3〜20メガバイトの範囲です。オンデマンドで必要に応じて、LTエンコーダは、わずかかなど、多くの符号化シンボルを生成することができます。新たな符号化シンボルは、LT符号化器によって生成される場合には、一意の符号化シンボルは、ソースシンボルから生成する方法について説明し、ランダムに選択された符号化シンボルIDに基づいています。一般的に、各符号化シンボルID値が一意の符号化シンボルに相当し、例えば符号化シンボルIDは4バイトである場合ことができる符号化シンボルのスペースは、約4億です。したがって、特定の符号化シンボルは、任意の他の特定の符号化シンボルと同じである可能性が可能な符号化シンボルIDの数に反比例します。 LTデコーダは、非常に高い確率でKよりもわずかにランダムかつ独立に生成された符号化シンボルのセットの受信がk個のソースシンボルを再構築するのに十分であるという特性を有しています。 kは、数千の数十〜数百のオーダーである場合、例えば、受信オーバーヘッドが損失条件下での試験の数百万でない障害が発生して5%未満です。

Because encoding symbols are randomly and independently generated by choosing random encoding symbol IDs, LT codes have the property that encoding symbols for the same k source symbols can be generated and transmitted from multiple senders and received by a receiver and the reception overhead and the decoding time is the same as if though all the encoding symbols were generated by a single sender. The only requirement is that the senders choose their encoding symbol IDs randomly and independently of one another.


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 symbols the smaller the reception overhead. Thus, for shorter objects, it is sometimes advantageous to partition the object into many short source symbols and include multiple encoding symbols in each packet. In this case, a single encoding symbol ID is used to identify the multiple encoding symbols contained in a single packet.


There are a couple of factors for choosing the appropriate symbol length/ number of source symbols tradeoff. The primary consideration is that there is a fixed overhead per symbol in the overall processing requirements of the encoding and decoding, independent of the number of source symbols. Thus, using shorter symbols means that this fixed overhead processing per symbol will be a larger component of the overall processing requirements, leading to larger overall processing requirements. A second much less important consideration is that there is a component of the processing per symbol that depends logarithmically on the number of source symbols, and thus for 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 that it makes sense to partition it into blocks when using LT codes. Generally the object is partitioned into blocks whenever the number of source symbols times the packet payload length is less than the size of the object. Thus, if the packet payload is 1024 bytes and the maximum number of source symbols is 128,000 then any object over 128 megabytes will be partitioned into more than one block. One can choose the maximum number of source symbols to use, depending on the desired encoding and decoding speed versus reception overhead tradeoff desired. Encoding symbols can be uniquely identified by a block number (when the object is large enough to be partitioned into more than one block) and an encoding symbol ID. The block numbers, if they are used, are generally numbered consecutively starting from zero within the object. The block number and the encoding symbol ID are both chosen uniformly and randomly from their range when an encoding symbol is to be transmitted. For example, suppose the number of source symbols is 128,000 and the number of blocks is 2. Then, each packet generated by the LT encoder could be of the form (b, x: y). In this example, the first value identifies the block number and the second value identifies the encoding symbol within the block. In this example, the block number b is either 0 or 1, and the encoding symbol ID x might be a 32-bit value. The value y after the colon is the value of the encoding symbol.

小さなブロック符号のように、オブジェクトは、それがLT符号を用いた場合にブロックにそれを分割することは理にかなっていることを十分な大きさである点があります。パケットペイロード長倍ソースシンボルの数は、オブジェクトのサイズ以下であるときはいつでも一般の目的は、ブロックに分割されます。したがって、場合には、パケットのペイロードは1024バイトであり、ソースシンボルの最大数は128,000次いで、128メガバイトを超える任意のオブジェクトは、複数のブロックに分割されています。一つは、所望の受信オーバーヘッドのトレードオフに対する所望の符号化及び復号化の速度に応じて、使用するソースシンボルの最大数を選択することができます。符号化シンボルは、一意ブロック番号(オブジェクトが複数のブロックに分割することが十分に大きい場合)、符号化シンボルIDによって識別することができます。ブロック番号は、それらが使用される場合、一般的に連続的オブジェクト内のゼロから始まる番号が付けられています。符号化シンボルが送信される場合にブロック番号および符号化シンボルIDは、両方の彼らの範囲から一様にランダムに選択されます。例えば、ソースシンボルの数は128,000であり、ブロック数が次に2であると仮定し、LT符号化器によって生成された各パケットの形式(:Y B、X)のものであってもよいです。この例では、最初の値は、ブロック番号を識別し、第2の値は、ブロック内の符号化シンボルを識別する。この例では、ブロック番号bは0または1のいずれかであり、符号化シンボルID Xは、32ビット値であるかもしれません。コロンの後の値yは、符号化シンボルの値です。

2.5. Source blocks with variable length source symbols
2.5. 可変長ソースシンボルとソースブロック

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 describe a general technique to handle the case when it is desirable to use source symbols of varying lengths in a single source block. This technique is applicable to block FEC codes.


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 be the maximum over i = 1, ... , k of l_i. To prepare the source block for the FEC encoder, pad each source symbol i out to length lmax with a suffix of lmax-l_i zeroes, and then prepend to the beginning of this the value l_i. Thus, each padded source symbol is of length x+lmax, assuming that it takes x bytes to store an integer with possible values 0,...,lmax, where x is a protocol constant known to both the encoder and the decoder. These padded source symbols, each of length x+lmax, are the input to the encoder, together with the value n. The encoder then generates n-k redundant symbols, each of length x+lmax.

L_1、L_2を聞かせ、...、同じソースブロックの一部とみなされるべき長さのソースシンボルを変えるkのバイトの長さであるL_K。最大ことLMAXましょう超えるI = 1、...、L_iをのK。 FECエンコーダ、パッドLMAX-L_iをゼロの接尾辞長LMAX各ソースシンボルI OUTのためのソースブロックを準備し、この値L_iをの先頭の前に付加します。このように、各パディングソースシンボルは、それが可能な値0の整数を格納するためにxバイトを取ると仮定すると、長さX + LMAXであり、...、LMAX、xはエンコーダとデコーダの両方に知られているプロトコルの定数です。これらのパディングソースシンボル、長さx + LMAXの各々は、一緒に値Nと、符号器に入力されます。エンコーダは次いで、N-k個の冗長シンボル、長さx + LMAXのそれぞれを生成します。

The encoding symbols that are placed into packets consist of the original k varying length source symbols and n-k redundant symbols, each of length x+lmax. From any k of the received encoding symbols, the FEC decoder recreates the k original source symbols as follows. If all k original source symbols are received, then no decoding is necessary. Otherwise, at least one redundant symbol is received, from which the receiver can easily determine if the block is composed of variable- length source symbols: if the redundant symbol(s) is longer than the source symbols then the source symbols are variable-length. Note that in a variable-length block the redundant symbols are always longer than the longest source symbol, due to the presence of the prepended symbol- length. The receiver can determine the value of lmax by subtracting x from the length of a received redundant symbol. For each of the received original source symbols, the receiver can generate the corresponding padded source symbol as described above. Then, the input to the FEC decoder is the set of received redundant symbols, together with the set of padded source symbols constructed from the received original symbols. The FEC decoder then produces the set of k padded source symbols. Once the k padded source symbols have been recovered, the length l_i of original source symbol i can be recovered from the first x bytes of the ith padded source symbol, and then original source symbol i is obtained by taking the next l_i bytes following the x bytes of the length field.

パケット内に配置される符号化シンボルは、長さ、ソースシンボルとn-k個の冗長シンボル、長さx + LMAXの各々を変える元Kから成ります。次のように受信された符号化シンボルのいずれkから、FECデコーダは、k個のオリジナルソースシンボルを再作成します。全てのkオリジナルソースシンボルが受信される場合、いかなる復号化は不要です。ブロックは可変長ソースシンボルから構成されている場合はそうでなければ、少なくとも一つの冗長シンボルが受信され、受信機は容易に決定することができ、そこから:冗長シンボル(s)は、より長いソースシンボルを超える場合、ソースシンボルが可変長であります。冗長シンボルが原因付加シンボル - 長さが存在するために、最長のソースシンボルよりも常に長い可変長ブロック内ことに留意されたいです。受信機は、受信された冗長シンボルの長さからXを減算することによりLMAXの値を決定することができます。上記のように受信したオリジナルソースシンボルのそれぞれについて、受信機は、対応するパッド入りのソースシンボルを生成することができます。次に、FECデコーダへの入力は、一緒に受信し、元のシンボルから構成されたパディングソースシンボルのセットと、受信された冗長シンボルのセットです。 FECデコーダは、次に、Kパディングソースシンボルのセットを生成します。 Kパディングソースシンボルが回復された後、元のソースシンボルの長さL_iをiは、i番目のパディングソースシンボルの最初のxバイトから回収することができ、その後、元のソースシンボルiはXの次L_iをバイトを取ることによって得られます。長さフィールドのバイト。

3. Security Considerations

The use of FEC, in and of itself, imposes no additional security considerations versus sending the same information without FEC. However, just like for any transmission system, a malicious sender may try to inject packets carrying corrupted encoding symbols. If a receiver accepts one or more corrupted encoding symbol, in place of authentic ones, then such a receiver may reconstruct a corrupted object.


Application-level transmission object authentication can detect the corrupted transfer, but the receiver must discard the transferred object. By injecting corrupted encoding symbols, they are accepted as valid encoding symbols by a receiver, which at the very least, is an effective denial of service attack.


In light of this possibility, FEC receivers may screen the source address of a received symbol against a list of authentic transmitter addresses. Since source addresses may be spoofed, transport protocols using FEC may provide mechanisms for robust source authentication of each encoding symbol. Multicast routers along the path of a FEC transfer may provide the capability of discarding multicast packets that originated on that subnet, and whose source IP address does not correspond with that subnet.

この可能性に照らして、FEC受信機は、本物の送信機アドレスのリストに対して受信シンボルの送信元アドレスをスクリーニングすることができます。送信元アドレスを偽装することができるので、FECを使用したトランスポートプロトコルは、各符号化シンボルのロバストなソース認証のためのメカニズムを提供することができます。 FEC転送の経路に沿ってマルチキャストルータは、そのサブネット上に発信マルチキャストパケットを廃棄する能力を提供し、そのソースIPアドレスそのサブネットと一致しないことができます。

It is recommended that a packet authentication scheme such as TESLA [14] be used in conjunction with FEC codes. Then, packets that cannot be authenticated can be discarded and the object can be reliably recovered from the received authenticated packets.


4. Intellectual Property Disclosure

The IETF has been notified of intellectual property rights claimed in regard to some or all of the specification contained in this document. For more information consult the online list of claimed rights.


5. Acknowledgments

Thanks to Vincent Roca and Hayder Radha for their detailed comments on this document.


6. References

[1] Acharya, S., Franklin, M. and S. Zdonik, "Dissemination - Based Data Delivery Using Broadcast Disks", IEEE Personal Communications, pp.50-60, Dec 1995.

[1] Acharyaさん、S.、フランクリン、M.およびS. Zdonik、 - 、IEEEパーソナル・コミュニケーションズ、pp.50-60、1995年12月 "普及ブロードキャストディスクの使用基づいてデータ配信"。

[2] Blahut, R.E., "Theory and Practice of Error Control Codes", Addison Wesley, MA, 1984.

[2]、アディソンウェズリー、MA、1984 Blahut、R.E.、 "誤り制御符号の理論と実践"。

[3] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996.

[3]ブラドナーの、S.、 "インターネット標準化プロセス - リビジョン3"、BCP 9、RFC 2026、1996年10月。

[4] Byers, J.W., Luby, M., Mitzenmacher, M. and A. Rege, "A Digital Fountain Approach to Reliable Distribution of Bulk Data", Proceedings ACM SIGCOMM '98, Vancouver, Canada, Sept 1998.

[4]バイヤーズ、J.W.、ルビー、M.、Mitzenmacher、M.とA.レゲ、 "バルクデータの信頼性の高い配信にデジタル泉アプローチ"、議事録のACM SIGCOMM '98、バンクーバー、カナダ、1998年9月。

[5] Haken, A., Luby, M., Horn, G., Hernek, D., Byers, J. and M. Mitzenmacher, "Generating high weight encoding symbols using a basis", U.S. Patent No. 6,411,223, June 25, 2002.

[5]派遣、A.、ルビー、M.、ホーン、G.、Hernek、D.、バイヤーズ、J.とM. Mitzenmacher、 "基準を用いて高い重量符号化シンボルを生成"、米国特許第6411223 6月25、2002。

[6] Luby, M., "Information Additive Code Generator and Decoder for Communication Systems", U.S. Patent No. 6,307,487, October 23, 2001.


[7] Luby, M., "Information Additive Group Code Generator and Decoder for Communication Systems", U.S. Patent No. 6,320,520, November 20, 2001.


[8] Luby, M., "Information Additive Code Generator and Decoder for Communication Systems", U.S. Patent No. 6,373,406, April 16, 2002.


[9] Luby, M. and M. Mitzenmacher, "Loss resilient code with double heavy tailed series of redundant layers", U.S. Patent No. 6,195,777, February 27, 2001.

[9]ルビー、M.およびM. Mitzenmacher、「冗長な層の二重テールシリーズと損失弾性コード」、米国特許第6195777、2001年2月27日。

[10] Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D. and V. Stemann, "Message encoding with irregular graphing", U.S. Patent No. 6,163,870, December 19, 2000.

[10]ルビー、M.、Mitzenmacher、M.、ショクロラヒ、A.、Spielman、D.およびV. Stemann、 "不規則なグラフとメッセージエンコーディング"、米国特許第6163870、2000年12月19日。

[11] Luby, M., Mitzenmacher, M., Shokrollahi, A. and D. Spielman, "Efficient Erasure Correcting Codes", IEEE Transactions on Information Theory, Special Issue: Codes on Graphs and Iterative Algorithms, pp. 569-584, Vol. 47, No. 2, February 2001.

[11]ルビー、M.、Mitzenmacher、M.、ショクロラヒ、A. D.およびSpielman、情報理論に関するIEEEトランザクション、特集「効率的な消去がコード修正」:グラフ及び反復アルゴリズム、頁上のコードを569から584まで巻。 47、第2号、2001年2月。

[12] Luby, M., Shokrollahi, A., Stemann, V., Mitzenmacher, M. and D. Spielman, "Loss resilient decoding technique", U.S. Patent No. 6,073,250, June 6, 2000.

[12]ルビー、M.、ショクロラヒ、A.、Stemann、V.、Mitzenmacher、M.とD. Spielman、 "損失弾性復号化技術"、米国特許第6073250、2000年6月6日。

[13] Luby, M., Shokrollahi, A., Stemann, V., Mitzenmacher, M. and D. Spielman, "Irregularly graphed encoding technique", U.S. Patent No. 6,081,909, June 27, 2000.

[13]ルビー、M.、ショクロラヒ、A.、Stemann、V.、Mitzenmacher、M.とD. Spielman、 "不規則なグラフ符号化技術"、米国特許第6081909、2000年6月27日。

[14] Perrig, A., Canetti, R., Song, D. and J.D. Tygar, "Efficient and Secure Source Authentication for Multicast", Network and Distributed System Security Symposium, NDSS 2001, pp. 35-46, February 2001.

[14] Perrig、A.、カネッティ、R.、歌、D.およびJ.D. Tygar、 "マルチキャストのための効率的で安全なソース認証"、ネットワークと分散システムセキュリティシンポジウム、NDSS 2001、頁35-46、2001年2月。

[15] Rizzo, L., "Effective Erasure Codes for Reliable Computer Communication Protocols", ACM SIGCOMM Computer Communication Review, Vol.27, No.2, pp.24-36, Apr 1997.

[15] Rizzo氏、L.、 "信頼性の高いコンピュータ通信プロトコルのための効果的な消去符号"、ACM SIGCOMMコンピュータコミュニケーションレビュー、Vol.27、第2号、pp.24-36、1997年4月。

[16] Rizzo, L., "On the Feasibility of Software FEC", DEIT Tech Report,, Jan 1997.

"ソフトウェアFECの可能性について" [16] Rizzo氏、L.、DEITテックレポート、、1997年1月。

7. Authors' Addresses

Michael Luby Digital Fountain 39141 Civic Center Drive Suite 300 Fremont, CA 94538

マイケル・ルビーデジタル噴水39141シビックセンタードライブスイート300フリーモント、CA 94538



Lorenzo Vicisano Cisco Systems, Inc. 170 West Tasman Dr., San Jose, CA, USA, 95134




Jim Gemmell Microsoft Research 455 Market St. #1690 San Francisco, CA, 94105




Luigi Rizzo Dip. di Ing. dell'Informazione Universita` di Pisa via Diotisalvi 2, 56126 Pisa, Italy



Mark Handley ICSI Center for Internet Research 1947 Center St. Berkeley CA, USA, 94704




Jon Crowcroft Marconi Professor of Communications Systems University of Cambridge Computer Laboratory William Gates Building J J Thomson Avenue Cambridge CB3 0FD

ケンブリッジの通信システム大学のコンピュータ研究所のウィリアム・ゲイツビルJ JトムソンアベニューケンブリッジCB3 0FDのジョン・クロークロフトマルコーニ教授



8. Full Copyright Statement

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


This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for 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 revoked by the Internet Society or its successors or assigns.






Funding for the RFC Editor function is currently provided by the Internet Society.

RFC Editor機能のための基金は現在、インターネット協会によって提供されます。