RFC3453 日本語訳
3453 The Use of Forward Error Correction (FEC) in Reliable Multicast.M. Luby, L. Vicisano, J. Gemmell, L. Rizzo, M. Handley, J. Crowcroft. December 2002. (Format: TXT=46853 bytes) (Status: INFORMATIONAL)
プログラムでの自動翻訳です。
英語原文
Network Working Group M. Luby
Request for Comments: 3453 Digital Fountain
Category: Informational L. Vicisano
Cisco
J. Gemmell
Microsoft
L. Rizzo
Univ. Pisa
M. Handley
ICIR
J. Crowcroft
Cambridge Univ.
December 2002
Lubyがコメントのために要求するワーキンググループM.をネットワークでつないでください: 3453年のデジタル噴水カテゴリ: 情報のL.のJ.GemmellマイクロソフトL.リゾーVicisanoコクチマス大学 ピサM.ハンドレーICIR J.クロウクロフトケンブリッジ大学 2002年12月
The Use of Forward Error Correction (FEC) in Reliable Multicast
信頼できるマルチキャストにおける前進型誤信号訂正(FEC)の使用
Status of this Memo
この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.
Copyright(C)インターネット協会(2002)。 All rights reserved。
Abstract
要約
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マルチキャストを使用することで多くへの1のための信頼性の確実な資料輸送を効率的に提供する、そして/または、増大させるためにForward Error Correction(FEC)コードの使用について説明します。 FECコードの基本性質の1つはこのような関係においては同時に複数の受信機で異なったパケット損失パターンを修理するのにFECデータを含む同じパケットを使用する能力です。 異なったクラスのFECコードと彼らのいくつかの基礎特性が説明されます、そして、信頼できるマルチキャストプロトコルでFECを実行すると関連している用語は紹介されます。 パケットのための可能な抽象的な形式がFECを運ぶのについて例を提供します。
Luby, et. al. Informational [Page 1] RFC 3453 FEC in Reliable Multicast December 2002
et Luby、アル。 信頼できるマルチキャスト2002年12月の情報[1ページ]のRFC3453FEC
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. 原理と概観. . . . . . . . . . . . . . . . . . . . 2 1.1。 FECのアプリケーションは.5 2をコード化します。 FECコード。 . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1. 簡単なコード. . . . . . . . . . . . . . . . . . . . . . . 6 2.2。 小さいブロックFECコード。 . . . . . . . . . . . . . . . . . . 8 2.3. 大きいブロックFECコード。 . . . . . . . . . . . . . . . . . . 10 2.4. 拡張可能なFECは.112.5をコード化します。 ソースは可変長ソースと共にシンボルを妨げます。 . . . . 13 3. セキュリティ問題。 . . . . . . . . . . . . . . . . . . . 14 4. 知的所有権公開. . . . . . . . . . . . . . . 14 5。 承認。 . . . . . . . . . . . . . . . . . . . . . . . 15 6. 参照. . . . . . . . . . . . . . . . . . . . . . . . . . 15 7。 作者のアドレス. . . . . . . . . . . . . . . . . . . . . . 17 8。 完全な著作権宣言文. . . . . . . . . . . . . . . . . . . 18
1. Rationale and Overview
1. 原理と概観
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と共に、受信機は、無くなっているパケットの「再-トランスミッション」を求める要求を送るのに送付者の戻っているチャンネルを使用します。 ARQはTCP/IPの普及している成功によって証明されるようによく1〜1のための信頼できるプロトコルを扱います。 また、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,
どんな非常に限られた容量戻っているチャンネルも戻っているチャンネルもどちらかの衛星通信などに全く似ていないので、ARQが高価であるか、または不可能である環境で、信頼性へのData Carouselアプローチは時々使用された[1]です。 次に、送付者は、Data Carouselと共に、これらのパケットを等しい長さのデータに物を仕切って、それらをパケットに置いて、を通して絶えず自転車で行って、送ります。(私たちは今後データをソースシンボルと呼びます)。 彼らがそれぞれのパケットのコピーを受けるまで、受信機はパケットを絶えず受けます。 受信機から送付者まで流れるデータが全くないので、データCarouselはそれがすぎ前で必要とする利点を精神を集中させます。 しかしながら、Data Carouselには、また、制限があります。 例えば
Luby, et. al. Informational [Page 2] RFC 3453 FEC in Reliable Multicast December 2002
et Luby、アル。 信頼できるマルチキャスト2002年12月の情報[2ページ]のRFC3453FEC
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.
受信機がトランスミッションの1ラウンドでパケットを失うなら、再びそのパケットを受ける機会がある前にそれは全体のラウンドを待たなければなりません。 また、これは帯域幅の無駄な使用を引き起こすかもしれません、どんな受信機もパケットを逃さないまで、送付者がパケットをを通して絶えず自転車で行って、伝えるとき。
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.
前進のError Correction(FEC)コードは他の信頼性の方法(特に多くへの1のための信頼できるIPマルチキャストなどの信頼性のプロトコル)を増大するか、または置き換えるのに使用できる信頼性の方法を提供します。 信頼できるIPマルチキャストの文脈における彼らの用途を見直す前に、私たちは最初に、簡潔にFECコードの基礎特性と何人かのタイプを見直します。 その後、私たちはいくつかのFECコードの、より詳細な記述を提供します。
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.
一般的な文学では、FECは消去(損失)とビットレベル不正の両方に打ち勝つ能力について言及します。 しかしながら、IPマルチキャストプロトコルの場合では、ネットワーク層が、崩壊したパケットを検出して、それらを捨てるだろうか、またはトランスポート層は、崩壊したパケットを捨てるのにパケット認証を使用できます。 したがって、消去コードとしてIPマルチキャストプロトコルへのFECコードの第一の利用があります。 ペイロードは、FEC消去エンコーダを使用することで発生して、処理されます、そして、物は対応するFEC消去デコーダを使用することで発生しているコード化を含むパケットのレセプションから組み立て直されます。
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エンコーダの各アプリケーションのときに異なることができますか、またはそれは修理できます。 シンボルをコード化するこれらはトランスミッションのためにパケットに置かれます。 シンボルが各パケットに置いたコード化の数がパケット基礎あたりのaで異なることができますか、またはシンボル(しばしば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.
後のセクションで、私たちは可変長ソースシンボルでブロックを扱うために上で説明されるようにFECコードを使用するためのテクニックについて説明します。
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.
ブロックFECコードは以下の通り働いています。 ブロックFECエンコーダへの入力は、kソースシンボルとNo.nです。 エンコーダは合計シンボルをコード化するnを発生させます。 kソースシンボルとn-kの余分なシンボルで構成された合計におけるシンボルをコード化しながらnのコード化ブロックをもたらすn-kの余分なシンボルを発生させるなら、エンコーダは系統的です。
Luby, et. al. Informational [Page 3] RFC 3453 FEC in Reliable Multicast December 2002
et Luby、アル。 信頼できるマルチキャスト2002年12月の情報[3ページ]のRFC3453FEC
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.
ブロックFECデコーダには、nもののどんなkもコード化ブロックでシンボルをコード化して、オリジナルのkソースシンボルを再建するために十分な特性があります。
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.
拡張可能なFECコードは以下の通り働いています。 拡張可能なFECエンコーダは、入力kソースシンボルとして取って、要求された通り同じくらい多くのユニークなコード化シンボルを要求に応じて発生させます、いくつのコード化シンボルが発生するかの如何にかかわらずシンボルをコード化しながらそれぞれを発生させるための時間が同じであるところで。 拡張可能なFECデコーダで、ユニークなコード化シンボルのどんなkも十分である特性はオリジナルのkソースシンボルを再建します。
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のレセプションもkソースシンボルを回復するために十分であるときに、上の定義で理想的な状況がわかります、その場合、レセプションオーバーヘッドは0%です。 いくつかの実用的なFECコードにおいて、シンボルをコード化するkわずかに以上が、kソースシンボルを回復するのに必要です。 k*であるなら、(1+ep)コード化シンボルが必要です、私たちは、レセプションオーバーヘッドがep*100%であると言います、例えば、シンボルをコード化するk*1.05が必要であるなら、レセプションオーバーヘッドは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の小さい値のためにコード化して、解読するための処理時間要件で効率的であり、kの多くの大きい値のためにコード化して、解読するのに、大きいFECコードは効率的です。 シンボルをコード化しながら回をコード化するのをl回に比例しているlがkの中のなくなったソースシンボルの数であるkソースシンボルの長さのkソースシンボルの長さの、そして、解読している倍が受けたn-k回に比例するようにするブロックFECコードの実現があって、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
理想的に、IPマルチキャストの文脈のFECコードは前のパケットレセプションパターンにかかわらず物を組み立て直すためにパケットでそれぞれの容認されたパケットが完全に受信機の役に立つような方法で伝えられるシンボルをコード化するのにおいて発生するのにおいて使用されている場合があります。 したがって、いくつかのパケットが中で失われているなら、詳細を求めることの代わりに送付者と受信機の間を通過してください。
Luby, et. al. Informational [Page 4] RFC 3453 FEC in Reliable Multicast December 2002
et Luby、アル。 信頼できるマルチキャスト2002年12月の情報[4ページ]のRFC3453FEC
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.
無くなっているパケットかData Carouselを使用するのをパケットを再送するまで待つ「再-トランスミッション」、受信機は物を組み立て直すために到着するいかなる他のその後の等しい数のパケットも使用できます。 これらのパケットを予測して伝えることができますか、または受信機は明らかにそれらを要求できます。 これは、物を組み立て直すために同じパケットが完全にすべての受信機の役に立つのを含意します、受信機が以前に、異なったパケット損失パターンを経験したかもしれませんが。 この特性は、減少するか、ARQとData Carouselに関連していた状態で前記のように問題を解決さえして、またはその結果、何桁も、より多くの受信機にプロトコルのスケーラビリティを劇的に増加させることができます。
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.
いくつかの信頼できるIPマルチキャストプロトコルにおいて、FECコードは、信頼性を提供するのにARQに関連して使用されます。 例えば、それぞれ少ない数のソースシンボルから成る多くのソースブロックに大きい物を仕切ることができました、そして、トランスミッションの最初のラウンドでは、すべてのソースブロックのソースシンボルのすべてを送ることができました。 そして、受信機はそれらがそれぞれのソースブロックから逃しているソースシンボルの数の送付者に報告を持ちかえるかもしれません。 送付者は計算できて、次に、すべての受信機の中でそれぞれのソースブロックからなくなったソースシンボルの最大数を計算してください。 これに基づいて、すべての受信機の中でブロックから計算された最大数のなくなったソースシンボルと等しい多くの余分なシンボルをそれぞれのソースブロックに発生させるのに小さいブロックFECエンコーダを使用できました、この各ブロック最大の最大が効率的に発生できる余分なシンボルの数を超えていない限り。 そして、トランスミッションの2番目のラウンドでは、サーバはすべてのブロックのこれらの余分なシンボルのすべてを送るでしょう。 この例では、トランスミッションの2番目のラウンドにおける損失が全くないと、すべての受信機がそれぞれの元のブロックの正確なコピーを再作成できるでしょう。 この場合、与えられたブロックの伝えられた余分なシンボルは異なった受信機が異なったブロックのなくなった異なったシンボルであっても、2番目のラウンドでそのブロックからのシンボルを逃すすべての受信機の役に立ちます。
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
他の信頼できるIPマルチキャストプロトコルにおいて、FECコードは、信頼性を提供するのにData Carouselファッションで使用されます。(私たちはFEC Data Carouselを信頼性と呼びます)。 例えば、大きいブロックFECコードを使用するFEC Data Carouselは以下の通り働くことができました。 大きいブロックFECエンコーダは、1ブロックとしてすべてのkが物のソースシンボルであると考える場合シンボルをコード化しながら、nを生産します。 送付者は、パケットで各ラウンドにおける同次でシンボルをコード化しながら、nをを通して自転車で行って、伝えます。 FEC Data CarouselはData Carouselよりはるかに良い保護をパケット損失に抱くことができます。 例えば、そして、次のnコード化のトランスミッションの間、シンボルをコード化しながら少なくともkを受ける限り、受信機は時間内に、任意な点でトランスミッションに参加できます。
Luby, et. al. Informational [Page 5] RFC 3453 FEC in Reliable Multicast December 2002
et Luby、アル。 信頼できるマルチキャスト2002年12月の情報[5ページ]のRFC3453FEC
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.
シンボルであり、受信機は物を完全に回収できます。 受信機がコード化シンボルを通してパスの中央でパケットを受け始めてさえいるなら、これは本当です。 また、物がブロックに仕切られるとき、この方法を使用できます、そして、短ブロック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.
以来、シンボルをどんな数もコード化するのが拡張可能なFECエンコーダを使用することで発生できて、一般に、拡張可能なFECコードを使用する信頼できるIPマルチキャストプロトコルは信頼性のために唯一これらのコードを当てにします。 拡張可能なFECコードがFEC Data Carouselアプリケーションで使用されるとき、例えば、コード化シンボルの潜在的に限りない数におけるコード化シンボルのコード化パケット決して反復しなく、およびその結果、どんなkも、オリジナルのkソースシンボルを回復するために十分です。
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.
追加信頼できるIPマルチキャストプロトコルのために、信頼性を得る方法がシンボルをコード化しながら十分を発生させることであるので、それぞれシンボルをコード化するのは一度(高々)だけ伝えられます。 例えば、送付者は、それがいくつのコード化シンボルを伝えるかを先験的に決めて、物からその数のコード化シンボルを発生させるのにFECコードを使用して、次に、コード化シンボルをすべての受信機に伝えることができます。 この方法はIPマルチキャストを使用するのにおいて例えば、流れが物に仕切られて、それぞれの物のソースシンボルがFECコードを使用することでコード化シンボルにコード化されて、次に、それぞれの物のシンボルをコード化するセットが次々と伝えられるストリーミングのプロトコルに適切です。
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
いくつかの非常に低い損失条件のもとでパケット損失を修理するのに、有効な非常に簡単なコードがあります。 例えば、単一の損失から保護を提供するのは、固定サイズソースシンボルに物を仕切って、次に、すべてのソースシンボルの同等(XOR)である余分なシンボルを追加することです。 ソースシンボルのサイズが選ばれているので、パケットのペイロードに完全に収まります、すなわち、パケットペイロードが512バイトであるなら、それぞれのソースシンボルは512バイトです。 それぞれのパケットのヘッダーはペイロードを特定できるくらいの情報を含んでいます。 これはシンボルIDをコード化する例です。 コード化しているシンボルIDはこの例の2つの部品から成ることができます。 最初の部分は、コード化シンボルがソースシンボルであるなら1と等しいコード化旗であり、コード化シンボルが余分なシンボルであるなら0と等しいです。 コード化旗が0であるならコード化旗が1余分なシンボルIDであるなら、コード化シンボルIDの第二部はソースシンボルIDです。 ソースシンボルIDに付番できます。
Luby, et. al. Informational [Page 6] RFC 3453 FEC in Reliable Multicast December 2002
et Luby、アル。 信頼できるマルチキャスト2002年12月の情報[6ページ]のRFC3453FEC
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:
0〜k-1と余分なシンボルまで、IDは0であるかもしれません。 例えば、物が値a、b、c、およびdを持っている4つのソースシンボルから成るなら、余分なシンボルの値はXOR b XOR c e=XOR dです。 次に、これらのシンボルを運ぶパケットに似ています:
(1, 0: a), (1, 1: b), (1, 2: c), (1, 3: d), (0, 0: e).
(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
2番目の値は、この例では、コード化シンボルIDが最初の2つの値から成って、ソースシンボルIDか余分なシンボルIDのどちらかです。(そこでは、最初の値がコード化旗です)。 コロン後のパケットの一部がコード化シンボルの値です。 他のすべてのシンボルの同等として物のどんなただ一つのソースシンボルも回復できます。 例えばパケットです。
(1, 0: a), (1, 1: b), (1, 3: d), (0, 0: e)
(1、0: a)、(1、1: b)、(1、3: d)(0、0:、e)
are received then the missing source symbol value with source symbol ID = 2 can be recovered by computing a XOR b XOR d XOR e = c.
その時受け取って、XOR b XOR d XOR e=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.
IDがさせることになっているコード化シンボルを形成する別の方法は0を評価します…k-1はkソースシンボルに対応しています、そして、値kはkソースシンボルのXORである余分なシンボルに対応しています。
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 シンボルをコード化しながら、加えられます。 そして、+1 関連コード化ブロックからシンボルをコード化しながら、kソースシンボルから成るソースブロックからkのどんな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
また、同等を使用することで余分なシンボルを加えるわずかに高度な方法を使用できます。 例えば、1つは物でpがsqrt(k)と等しいp x p正方行列の中にkソースシンボルから成るブロックを分類できます。 そして、各列において、列のすべてのソースシンボルの同等である余分なシンボルは加えられます。 同様に、各コラムに関して、コラムのすべてのソースシンボルの同等である余分なシンボルは加えられます。 そして、どんなコラムのためにも列で同様にp+1シンボルのどんなpもマトリクスのどんな列からも取り戻すことができます。 また、このテクニックを使用するより高い次元製品コードは使用できます。 しかしながら、シンボルの可能な損失パターンに向かって考えられたいくつかなしでこれらの構造を使用するのに用心深いに違いありません。 理想的に、1つが入手したがっている資産はkソースシンボルがシンボルをコード化しながらnにコード化されるなら(コード化シンボルはソースシンボルと余分なシンボルから成ります)kソースシンボルから回復できるということです。
Luby, et. al. Informational [Page 7] RFC 3453 FEC in Reliable Multicast December 2002
et Luby、アル。 信頼できるマルチキャスト2002年12月の情報[7ページ]のRFC3453FEC
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.
シンボルをコード化する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マルチキャストプロトコルはブロック(n、k)FECコード[2]を使用するかもしれません。 そのようなコードにおいて、kソースシンボルはシンボルをコード化しながら、n>kにコード化されます、オリジナルのkソースシンボルを組み立て直すのにコード化シンボルのどんなkも使用できるように。 したがって、直接全体の物をコード化するのに使用される場合、これらのコードにはレセプションオーバーヘッドが全くありません。 通常、ブロック・コードは系統的です(シンボルをコード化するnが余分なシンボルのサイズがソースシンボルのためのそれと同じであるこれらのkソースシンボルから発生するkソースシンボルとn-kの余分なシンボルから成ることを意味します)。 例えば、前の小区分で説明された最初の簡単なコード(XOR)は(k+1、k)コードです。 一般に、k+1が望ましいよりこれとして大きいnを選ぶ自由は損失に対するはるかに良い保護を提供できます。 これらのタイプのコードのポピュラーな例はリードソロモン符号のクラスです。(リードソロモン符号は、有限分野を使用することで代数的な方法に基づいています)。 (n、k)FEC消去コードの実現はパーソナルコンピュータ[16]で使用できるくらい効率的です。 例えば、コード化と解読速度がC/jとして腐食するところで[15]は実現について説明して、クラスが機械加工する様々なヴィンテージとjのPentiumが上側であるので、10〜80の注文には定数CがあるところでMbytes/秒は分(k、n-k)までにバウンドしました。
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.
実際には、コード化と解読が大きい値で法外に高価になるので、そのようなFECコードには、kとnの値は小さくなければなりません(例えば、256未満)。 多くの物がkの適正価値のkシンボルとシンボルの長さより長いときに(例えば、1キロバイトのシンボルを使用するk=のための16キロバイトより大きい16)、それらを多くのソースブロックに分割できます。 それぞれのソースブロックは何らかの数kのソースシンボルから成ります。そこでは、kが異なったソースブロックの間で異なるかもしれません。 FECエンコーダは、コード化ブロックのコード化シンボルのNo.nがそれぞれのソースブロックに異なるかもしれないブロックをコード化するシンボルをコード化しながらkソースシンボルソースブロックをnにコード化するのに使用されます。 受信機がkソースシンボルから成るそれぞれのソースブロックに物を完全に回収するように、ブロックをコード化する対応からk異なったコード化シンボル(すなわち、異なったコード化しているシンボルIDがある)を受け取らなければなりません。 いくつかに関しては、ブロックをコード化して、ソースシンボルが対応するソースブロックにあるよりシンボルをさらにコード化するのを受け取るかもしれません、その場合、シンボルをコード化する過剰は捨てます。 構造をコード化する例は図1に示されます。
Luby, et. al. Informational [Page 8] RFC 3453 FEC in Reliable Multicast December 2002
et Luby、アル。 信頼できるマルチキャスト2002年12月の情報[8ページ]のRFC3453FEC
| 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
|
v
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|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 |
| ソースシンボルID| ソースシンボルID| | ソースブロック0について| ソースブロック1について| | | v対+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+|0 |1 |2 |3 |4 |5 |6 |7 |0 |1 |2 |3 | 4|5 |6 |7 | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | FECエンコーダ| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+に対して|0 |1 |2 |3 | 4| 5| 6| 7| 8| 9| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ ^ ^ | | | シンボルIDをコード化します。| シンボルIDをコード化します。| | ブロック0をコード化するのについて| ブロック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.
図1。 物のためのコード化構造はそれぞれ8つのソースシンボルから成る2つのソースブロックに分割されました、そして、FECエンコーダは、それぞれの2つのソースブロックの2つの追加余分なシンボル(合計でシンボルをコード化する10)を発生させるのに使用されます。
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.
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.
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.
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.
Luby, et. al. Informational [Page 9] RFC 3453 FEC in Reliable Multicast December 2002
Luby, et. al. Informational [Page 9] RFC 3453 FEC in Reliable Multicast December 2002
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
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
(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
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)
(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 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.
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. Large block FEC codes
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
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
Luby, et. al. Informational [Page 10] RFC 3453 FEC in Reliable Multicast December 2002
Luby, et. al. Informational [Page 10] RFC 3453 FEC in Reliable Multicast December 2002
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.
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.
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.
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. Expandable FEC codes
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.
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
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
Luby, et. al. Informational [Page 11] RFC 3453 FEC in Reliable Multicast December 2002
Luby, et. al. Informational [Page 11] RFC 3453 FEC in Reliable Multicast December 2002
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.
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.
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.
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 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.
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
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
Luby, et. al. Informational [Page 12] RFC 3453 FEC in Reliable Multicast December 2002
Luby, et. al. Informational [Page 12] RFC 3453 FEC in Reliable Multicast December 2002
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.
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.
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 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.
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.
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.
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
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
Luby, et. al. Informational [Page 13] RFC 3453 FEC in Reliable Multicast December 2002
Luby, et. al. Informational [Page 13] RFC 3453 FEC in Reliable Multicast December 2002
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.
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.
3. Security Considerations
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.
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.
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.
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.
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.
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
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.
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.
Luby, et. al. Informational [Page 14] RFC 3453 FEC in Reliable Multicast December 2002
Luby, et. al. Informational [Page 14] RFC 3453 FEC in Reliable Multicast December 2002
5. Acknowledgments
5. Acknowledgments
Thanks to Vincent Roca and Hayder Radha for their detailed comments on this document.
Thanks to Vincent Roca and Hayder Radha for their detailed comments on this document.
6. References
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., Franklin, M. and S. Zdonik, "Dissemination - Based Data Delivery Using Broadcast Disks", IEEE Personal Communications, pp.50-60, Dec 1995.
[2] Blahut, R.E., "Theory and Practice of Error Control Codes",
Addison Wesley, MA, 1984.
[2] Blahut, R.E., "Theory and Practice of Error Control Codes", Addison Wesley, MA, 1984.
[3] Bradner, S., "The Internet Standards Process -- Revision 3", BCP
9, RFC 2026, October 1996.
[3] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996.
[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] 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.
[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] 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.
[6] Luby, M., "Information Additive Code Generator and Decoder for
Communication Systems", U.S. Patent No. 6,307,487, October 23,
2001.
[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.
[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.
[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] 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.
[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] 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.
Luby, et. al. Informational [Page 15] RFC 3453 FEC in Reliable Multicast December 2002
Luby, et. al. Informational [Page 15] RFC 3453 FEC in Reliable Multicast December 2002
[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] 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.
[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] 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.
[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] 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.
[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., 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.
[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., "Effective Erasure Codes for Reliable Computer Communication Protocols", ACM SIGCOMM Computer Communication Review, Vol.27, No.2, pp.24-36, Apr 1997.
[16] Rizzo, L., "On the Feasibility of Software FEC", DEIT Tech
Report, http://www.iet.unipi.it/~luigi/softfec.ps, Jan 1997.
[16] Rizzo, L., "On the Feasibility of Software FEC", DEIT Tech Report, http://www.iet.unipi.it/~luigi/softfec.ps, Jan 1997.
Luby, et. al. Informational [Page 16] RFC 3453 FEC in Reliable Multicast December 2002
Luby, et. al. Informational [Page 16] RFC 3453 FEC in Reliable Multicast December 2002
7. Authors' Addresses
7. Authors' Addresses
Michael Luby Digital Fountain 39141 Civic Center Drive Suite 300 Fremont, CA 94538
Michael Luby Digital Fountain 39141 Civic Center Drive Suite 300 Fremont, CA 94538
EMail: luby@digitalfountain.com
EMail: luby@digitalfountain.com
Lorenzo Vicisano Cisco Systems, Inc. 170 West Tasman Dr., San Jose, CA, USA, 95134
Lorenzo Vicisano Cisco Systems, Inc. 170 West Tasman Dr., San Jose, CA, USA, 95134
EMail: lorenzo@cisco.com
EMail: lorenzo@cisco.com
Jim Gemmell Microsoft Research 455 Market St. #1690 San Francisco, CA, 94105
Jim Gemmell Microsoft Research 455 Market St. #1690 San Francisco, CA, 94105
EMail: jgemmell@microsoft.com
EMail: jgemmell@microsoft.com
Luigi Rizzo Dip. di Ing. dell'Informazione Universita` di Pisa via Diotisalvi 2, 56126 Pisa, Italy
Luigi Rizzo Dip. di Ing. dell'Informazione Universita` di Pisa via Diotisalvi 2, 56126 Pisa, Italy
EMail:luigi@iet.unipi.it
EMail:luigi@iet.unipi.it
Mark Handley ICSI Center for Internet Research 1947 Center St. Berkeley CA, USA, 94704
Mark Handley ICSI Center for Internet Research 1947 Center St. Berkeley CA, USA, 94704
EMail: mjh@icir.org
EMail: mjh@icir.org
Jon Crowcroft Marconi Professor of Communications Systems University of Cambridge Computer Laboratory William Gates Building J J Thomson Avenue Cambridge CB3 0FD
Jon Crowcroft Marconi Professor of Communications Systems University of Cambridge Computer Laboratory William Gates Building J J Thomson Avenue Cambridge CB3 0FD
EMail: Jon.Crowcroft@cl.cam.ac.uk
EMail: Jon.Crowcroft@cl.cam.ac.uk
Luby, et. al. Informational [Page 17] RFC 3453 FEC in Reliable Multicast December 2002
Luby, et. al. Informational [Page 17] RFC 3453 FEC in Reliable Multicast December 2002
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 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.
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.
The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Acknowledgement
Funding for the RFC Editor function is currently provided by the Internet Society.
Funding for the RFC Editor function is currently provided by the Internet Society.
Luby, et. al. Informational [Page 18]
Luby, et. al. Informational [Page 18]
一覧
スポンサーリンク
