[要約] RFC 3453は、信頼性のあるマルチキャストでの前方誤り訂正（FEC）の使用についての要約です。このRFCの目的は、FECを使用してマルチキャスト通信の信頼性を向上させることです。
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
The Use of Forward Error Correction (FEC) in Reliable Multicast
信頼できるマルチキャストでのフォワードエラー補正（FEC）の使用
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.
Copyright（c）The Internet Society（2002）。無断転載を禁じます。
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対多くの信頼できるデータトランスポートの信頼性を効率的に提供および/または増強するためのフォワードエラー補正（FEC）コードの使用について説明しています。このコンテキストでのFECコードの重要なプロパティの1つは、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
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マルチキャストプロトコルの効果的な信頼性ツールでもあります。ただし、多くの受信機が送信者に送信されているため、フィードバック爆発の問題を含むARQには、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.
ARQが非常に限られた容量のバックチャネルがあるか、衛星伝送など、バックチャネルがまったくないためにコストまたは不可能の環境では、信頼性に対するデータカルーセルアプローチが使用されることがあります[1]。データカルーセルを使用すると、送信者はオブジェクトを等しい長さのデータに分割します。これは、以下でソースシンボルを呼び出し、パケットに配置し、これらのパケットを継続的に循環して送信します。受信機は、各パケットのコピーを受け取るまで継続的にパケットを受け取ります。データカルーセルには、レシーバーから送信者に流れるデータがないため、バックチャネルを必要としないという利点があります。ただし、データカルーセルにも制限があります。たとえば、レシーバーが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.
フォワードエラー補正（FEC）コードは、特に信頼性の高いIPマルチキャストなどの1対多くの信頼性プロトコルについて、他の信頼性方法を増強または置換するために使用できる信頼性方法を提供します。信頼性の高い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エンコーダーの各アプリケーションによって異なる場合があります。または、固定できます。これらのエンコードシンボルは、送信用のパケットに配置されます。各パケットに配置されたエンコードシンボルの数は、パケットごとに異なる場合があります。または、各パケットに固定された数のシンボル（多くの場合1）を配置できます。また、各パケットには、そのパケットに掲載された特定のエンコードシンボルを識別するのに十分な情報が配置されます。エンコーディングシンボルを含むパケットを受け取ると、受信機はこれらのエンコードシンボルを対応するFECデコーダーにフィードして、Kソース記号の正確なコピーを再現します。理想的には、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ソースシンボルとa数nです。エンコーダーは、合計nエンコードシンボルを生成します。エンコーダーは、n-K冗長シンボルを生成し、kソース記号とn-k冗長シンボルで構成される合計でnエンコードシンボルのエンコードブロックを生成する場合に体系的です。
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の小さな値のエンコードとデコードの処理時間要件の点で効率的であり、大きなFECコードは、kのはるかに大きな値のエンコードとデコードに効率的です。kソース記号の長さのn-k倍に比例したエンコード時間をエンコードするブロックFECコードの実装、およびkソースシンボルの長さのl倍に比例するデコード時間はあります。受信したエンコード記号とlはkと同じくらい大きい場合があります。KおよびN-Kの積としてエンコードおよびデコード時間の成長率のため、これらは通常、小さなブロックFECコードと見なされます。nエンコードシンボルを生成できる小さな受信オーバーヘッドを備えたブロックFECコードがあり、nエンコードシンボルの長さに比例してKソースシンボルを時間内にデコードできます。これらのコードは、大きなブロックFECコードと見なされます。長さにほぼ比例して各エンコードシンボルを生成できる小さな受信オーバーヘッドを備えた拡張可能なFECコードがあり、長さにほぼ比例した時間内にすべてのKソース記号をデコードできます。これらは、大規模な拡張可能な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.
理想的には、IPマルチキャストのコンテキストでのFECコードを使用して、受信した各パケットがレシーバーに完全に役立つようにパケットに送信されるエンコードシンボルを生成して、以前のパケット受信パターンに関係なくオブジェクトを再組み立てできます。したがって、一部のパケットが送信者と受信機の間の輸送中に失われた場合、失われたパケットの特定の再送信を要求する代わりに、またはデータカルーセルを使用してパケットがresするまでパケットがresするまで待機する場合、受信者は到着する他の後続の同数のパケットを使用できますオブジェクトを再組み立てします。これらのパケットは、積極的に送信するか、レシーバーが明示的に要求することもできます。これは、レシーバーが以前に異なるパケット損失パターンを経験した可能性がある場合でも、同じパケットがすべてのレシーバーにとって完全に役立つことを意味します。このプロパティは、ARQおよびデータカルーセルに関連する上記の問題を軽減または排除することさえでき、それにより、プロトコルのスケーラビリティが桁違いに劇的に増加します。
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マルチキャストプロトコルの場合、ARQと組み合わせてFECコードが使用されます。たとえば、大きなオブジェクトは、それぞれ少数のソース記号で構成される多くのソースブロックに分割できます。最初のラウンドの送信では、すべてのソースブロックのすべてのソース記号を送信できます。次に、受信者は、各ソースブロックから欠落しているソース記号の数を送信者に報告できます。送信者は、すべてのレシーバーの各ソースブロックから欠落しているソース記号の最大数を計算できます。これに基づいて、各ソースブロックの小さなブロック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 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 CarouselファッションでFECコードが使用され、FECデータカルーセルと呼ばれる信頼性が提供されます。たとえば、大きなブロックFECコードを使用したFECデータカルーセルは、次のように機能する可能性があります。大きなブロックFECエンコーダは、オブジェクトのすべてのkソース記号を1つのブロックとして考慮して、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.
拡張可能なFECエンコーダを使用して、任意の数のエンコードシンボルを生成できるため、一般に拡張可能なFECコードを使用する信頼性の高いIPマルチキャストプロトコルは、一般に信頼性のためにこれらのコードのみに依存しています。たとえば、FECデータカルーセルアプリケーションで拡張可能なFECコードが使用される場合、エンコーディングパケットが繰り返されることはありません。したがって、潜在的に無制限の数のエンコードシンボルのエンコードシンボルの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マルチキャストプロトコルの場合、信頼性を取得する方法は、各エンコードシンボルが（せいぜい）1回だけ送信されるように、十分なエンコードシンボルを生成することです。たとえば、送信者は、[エンコード記号]を送信し、FECコードを使用してオブジェクトからその数のエンコーディングシンボルを生成し、エンコードシンボルをすべての受信機に送信するために、先験的に先験的に決定できます。この方法は、ストリーミングプロトコルに適用できます。たとえば、ストリームがオブジェクトに分割され、各オブジェクトのソースシンボルがFECコードを使用してエンコードシンボルにエンコードされ、次に各オブジェクトのエンコードシンボルのセットが送信されます。IPマルチキャストを使用するその他。
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つの部分で構成できます。最初の部分は、エンコードシンボルがソースシンボルであり、エンコードシンボルが冗長シンボルである場合、1に等しい1に等しいエンコードフラグです。エンコードシンボルIDの2番目の部分は、エンコードフラグが1の場合のソースシンボルID、エンコードフラグが0の場合は冗長シンボルIDですたとえば、オブジェクトが値a、b、c、dを持つ4つのソース記号で構成されている場合、冗長シンボルの値はe = a xor b xor c 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
この例では、エンコードシンボルIDは最初の2つの値で構成されます。最初の値はエンコードフラグであり、2番目の値はソースシンボルIDまたは冗長シンボルIDです。コロンの後のパケットの部分は、エンコードシンボルの値です。オブジェクトの単一のソース記号は、他のすべてのシンボルのパリティとして回復できます。たとえば、パケットの場合
(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を計算することにより、SOURCEシンボル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 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.
パリティを使用して冗長記号を追加するわずかに洗練された方法も使用できます。たとえば、オブジェクト内のkソース記号で構成されるブロックをグループAブロックP x P正方形マトリックス（p = sqrt（k））にすることができます。次に、各行に、行のすべてのソースシンボルのパリティである冗長シンボルが追加されます。同様に、各列について、列内のすべてのソースシンボルのパリティである冗長記号が追加されます。次に、行の任意の行を、行のp 1記号の任意のPから、また同様に任意の列について復元できます。この手法を使用した高次元の製品コードも使用できます。ただし、シンボルの損失パターンの可能性に向けて考えなくても、これらの構造を使用することに注意する必要があります。理想的には、取得したい特性は、kソースシンボルがnエンコードシンボル（エンコードシンボルがソース記号と冗長記号で構成されている）にエンコードされている場合、kソースシンボルはnの任意のkから回復できることです。シンボルをエンコードします。上記の単純な構造を使用しても、この理想的な動作を得ることに近づくコードは得られません。
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を選択する自由が望ましいです。これは、損失に対するはるかに良い保護を提供できるためです。これらのタイプのコードの一般的な例は、有限フィールドを使用した代数法に基づいたReed-Solomonコードのクラスです。（n、k）FEC消去コードの実装は、パーソナルコンピューターで使用するのに十分な効率です[16]。たとえば、[15]は、エンコードとデコードの速度がc/jとして減衰する実装を説明します。ここで、さまざまなヴィンテージのペンティウムクラスマシンの場合、定数Cは10〜80 mbytes/秒であり、jはminで上限に縛られています。（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.
実際には、kとnの値は、大きい値がエンコードとデコードが法外に高価になるため、kとnの値を小さい（たとえば256未満）する必要があります。多くのオブジェクトは、kの合理的な値とシンボルの長さのk記号よりも長いため（たとえば、1キロバイト記号を使用してk = 16で16キロバイトより大きく）、それらは多くのソースブロックに分割できます。各ソースブロックは、ソースシンボルのいくつかの数kで構成されており、Kはソースブロックが異なる場合があります。FECエンコーダーは、Kソースシンボルソースブロックをエンコードシンボルエンコードブロックにエンコードするために使用されます。エンコードブロック内のエンコードシンボルの数は、各ソースブロックで異なる場合があります。受信機がオブジェクトを完全に回復するには、kソースシンボルで構成されるソースブロックごとに、k異なるエンコードシンボル（つまり、異なるエンコードシンボルID）を対応するエンコードブロックから受信する必要があります。一部のエンコーディングブロックの場合、対応するソースブロックにソースシンボルがあるよりも多くのエンコーディングシンボルが受信される場合があります。その場合、過剰なエンコードシンボルが破棄されます。エンコード構造の例を図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
|
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 |
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.
多くの場合、オブジェクトは、オブジェクトの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.
ブロック番号は、ゼロから連続して番号を付けることができます。ブロック内のシンボルをエンコードすることは、エンコードシンボルIDによって一意に識別できます。ブロック内のエンコードシンボルを識別する1つの方法は、シンボルをソースシンボルまたは冗長シンボルのいずれかとともに、ソースシンボルIDまたは冗長シンボルIDのいずれかとして識別するエンコードフラグの組み合わせを使用することです。たとえば、1のエンコードフラグ値は、エンコードシンボルがソースシンボルであり、0が冗長シンボルであることを示すことができます。ソースシンボルIDは0からk-1に番号を付けることができ、冗長シンボルIDには0から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、g、h、h、j、およびk = 5とn = 8を持つ10のソース記号で構成されている場合、2つのソースブロックがあります。それぞれ5つのシンボルがあり、それぞれ8つのシンボルで構成される2つのエンコードブロックがあります。P、Q、Rを、最初のエンコードブロックの冗長記号の値とし、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
この例では、最初の値がブロック番号を識別し、2番目の2つの値が一緒にブロック内のエンコードシンボルを識別します。つまり、エンコードシンボルIDは、ソースシンボルIDまたは冗長シンボルIDとともにエンコードフラグで構成されています。エンコーディングフラグの値。エンコーディングシンボルの値は、コロンの後に記述されます。各ブロックは、そのブロックに関連付けられた8つのエンコードシンボルのうち5つから回復できます。たとえば、の受信
(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.
2番目のソースブロックを回復するのに十分です。
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.
ブロック内のエンコードシンボルをユニークに識別する別の方法は、ソースシンボルのエンコードシンボルIDを0、...、k-1にし、冗長シンボルのエンコードシンボルIDをk、...、n-1にすることです。。
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の値はkの小さな倍数に制限されています。たとえば、n = 2k。たとえば、[4]は、kが数万とn = 2kである場合、さまざまなヴィンテージのペンティウムクラスマシンのエンコード速度とデコード速度が1秒あたり数十である竜巻コードの実装を説明しています。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.
竜巻コードは、エンコーディングパケットのランダム部分を受信することに関して、平均してオーバーヘッドが低いように設計されています。したがって、受信機が低い受信オーバーヘッドでオブジェクトを再構築できるようにするために、送信前にパケットはランダムな順序に順応します。
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.
この時点までに説明されているFECコードはすべて、ブロックコードです。拡張可能なFECコードと呼ばれる異なるタイプのFECコードがあります。ブロックコードと同様に、拡張可能なFECエンコーダーは、等しい長さのソースシンボルに分割される既知のサイズのオブジェクトで動作します。ブロックコードとは異なり、拡張可能なFECコードで生成できるエンコードシンボルの事前に決められた数はありません。代わりに、拡張可能なFECエンコーダーは、必要なオンデマンドで必要な限り少数または多くの一意のエンコードシンボルを生成できます。
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コード、つまり数十から数十万の順序で非常に大きく、エンコーダーとデコーダーはソフトウェアで効率的に実行されます。たとえば、LTコードのエンコーディング速度とデコード速度は、Kが多い数万人の場合、さまざまなヴィンテージのペンティウムクラスのマシンの範囲3〜20メガバイトです。LTエンコーダーは、必要な数のエンコードシンボルをオンデマンドで生成できます。新しいエンコードシンボルがLTエンコーダーによって生成される場合、それは、ソースシンボルからエンコードシンボルがどのように生成されるかを一意に説明するランダムに選択されたエンコードシンボルIDに基づいています。一般に、各エンコードシンボルID値は一意のエンコードシンボルに対応しているため、たとえばエンコードシンボルIDが4バイトである場合、可能なエンコードシンボルのスペースは約40億です。したがって、特定のエンコードシンボルが他の特定のエンコードシンボルと同じである可能性は、可能なエンコードシンボル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.
エンコードシンボルはランダムなエンコードシンボルIDを選択することによりランダムかつ独立して生成されるため、LTコードには、同じkソースシンボルのエンコードシンボルを生成および複数の送信者から生成し、受信機とレセプションオーバーヘッドとデコード時間を受信できるプロパティがあります。すべてのエンコードシンボルが単一の送信者によって生成された場合と同じです。唯一の要件は、送信者がエンコードシンボルIDを互いにランダムかつ独立して選択することです。
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.
ソースシンボルの数とLTコードのレセプションオーバーヘッドとの間には弱いトレードオフがあり、ソースシンボルの数が大きいほど、レセプションオーバーヘッドが小さくなります。したがって、より短いオブジェクトの場合、オブジェクトを多くの短いソース記号に分割し、各パケットに複数のエンコードシンボルを含めることが有利な場合があります。この場合、単一のエンコードシンボルIDを使用して、単一のパケットに含まれる複数のエンコードシンボルを識別します。
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.
ソースシンボルのトレードオフの適切なシンボルの長さ/数を選択するためのいくつかの要因があります。主な考慮事項は、ソース記号の数とは無関係に、エンコードとデコードの全体的な処理要件に記号あたりの固定オーバーヘッドがあることです。したがって、より短いシンボルを使用すると、シンボルごとにこの固定オーバーヘッド処理が全体的な処理要件のより大きなコンポーネントになり、全体的な処理要件が大きくなります。2つ目の重要性の低い考慮事項は、ソースシンボルの数に対数的に依存するシンボルごとの処理のコンポーネントがあるため、このため、ソースシンボルの数が少ないことがわずかに好まれることです。
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エンコーダーによって生成された各パケットがフォーム（b、x：y）である可能性があります。この例では、最初の値はブロック数を識別し、2番目の値はブロック内のエンコードシンボルを識別します。この例では、ブロック番号bは0または1であり、エンコードシンボルID xは32ビット値である可能性があります。コロンの後の値yは、エンコード記号の値です。
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.
上記のすべてのFECコードについて、同じソースブロックのすべてのソース記号はすべて同じ長さです。このセクションでは、単一のソースブロックでさまざまな長さのソース記号を使用することが望ましい場合に、ケースを処理する一般的な手法について説明します。この手法は、FECコードのブロックに適用できます。
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、...、l_kを、同じソースブロックの一部と見なされるKの変化する長さのソース記号のバイトの長さとします。lmaxをi = 1、...、l_iの最大値とします。FECエンコーダのソースブロックを準備するには、各ソースシンボルをLMAX-L_Iゼロの接尾辞で長さのLMAXにパッドし、次にこの値L_Iの先頭にプレイエンドします。したがって、各パッド付きソースシンボルは、長さx lmaxであり、可能な値0、...、lmaxで整数を保存するのにxバイトが必要であると仮定します。ここで、xはエンコーダーとデコーダーの両方に知られているプロトコル定数です。これらのパッド入りソース記号、各長さx lmaxは、値nとともにエンコーダーへの入力です。エンコーダは、長さx lmaxの各n-K冗長記号を生成します。
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.
パケットに配置されたエンコーディングシンボルは、長さx lmaxのそれぞれの元のkさまざまな長さのソースシンボルとn-k冗長シンボルで構成されています。受信したエンコードシンボルの任意のKから、FECデコーダーは次のようにKの元のソースシンボルを再現します。すべてのK元のソースシンボルを受信した場合、デコードは必要ありません。それ以外の場合、少なくとも1つの冗長シンボルが受信されます。そこからブロックが可変長さのソースシンボルで構成されているかどうかを簡単に判断できます。冗長シンボルがソースシンボルよりも長い場合、ソースシンボルは可変 - 長さです。可変長ブロックでは、冗長なシンボルは、優先されたシンボル長が存在するため、常に最長のソースシンボルよりも長いことに注意してください。受信者は、受信した冗長シンボルの長さからxを差し引くことにより、LMAXの値を決定できます。受信した元のソース記号のそれぞれについて、受信機は上記のように対応するパッド付きソースシンボルを生成できます。次に、FECデコーダーへの入力は、受信した元のシンボルのセットと、受信した元のシンボルから構築されたパッド付きソースシンボルのセットです。次に、FECデコーダーは、kパディングソースシンボルのセットを生成します。kパッド入りソースシンボルが回収されると、元のソースシンボルの長さl_iは、xh paddedソースシンボルの最初のxバイトから回復できます。そして、xに続いて次のl_iバイトを取得することで元のソースシンボルiが取得されます。長さフィールドのバイト。
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.
FECの使用自体は、FECなしで同じ情報を送信することに対して、追加のセキュリティ上の考慮事項を課されません。ただし、送信システムと同様に、悪意のある送信者は、破損したエンコードシンボルを運ぶパケットを注入しようとする場合があります。受信者が本物のものの代わりに1つ以上の破損したエンコードシンボルを受け入れる場合、そのような受信機は破損したオブジェクトを再構築する場合があります。
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.
Tesla [14]などのパケット認証スキームをFECコードと組み合わせて使用することをお勧めします。次に、認証できないパケットを破棄し、受信した認証されたパケットからオブジェクトを確実に回収できます。
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.
IETFは、このドキュメントに含まれる仕様の一部またはすべてに関して請求された知的財産権について通知されています。詳細については、請求権のオンラインリストを参照してください。
Thanks to Vincent Roca and Hayder Radha for their detailed comments on this document.
この文書に関する詳細なコメントをしてくれたVincent RocaとHayder Radhaに感謝します。
[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。、およびS. Zdonik、「普及 - 放送ディスクを使用したデータ提供に基づく」、IEEE Personal Communications、pp.50-60、1995年12月。
[2] Blahut, R.E., "Theory and Practice of Error Control Codes", Addison Wesley, MA, 1984.
[2] Blahut、R.E。、「エラー制御コードの理論と実践」、Addison Wesley、MA、1984。
[3] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 9, RFC 2026, October 1996.
[3] Bradner、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] Byers、J.W.、Luby、M.、Mitzenmacher、M.、A。Rege、「バルクデータの信頼できる分布へのデジタル噴水アプローチ」、Proceedings 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] Haken、A.、Luby、M.、Horn、G.、Hernek、D.、Byers、J。and M. Mitzenmacher、「基礎を使用した高重量エンコードシンボルの生成」、米国特許第6,411,223号、2002年6月25日。
[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。、「通信システム用の情報添加剤コードジェネレーターとデコーダー」、米国特許第6,307,487号、2001年10月23日。
[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。、「通信システム用の情報添加剤グループコードジェネレーターとデコーダー」、米国特許第6,320,520号、2001年11月20日。
[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。、「通信システム用の情報添加剤コードジェネレーターとデコーダー」、米国特許第6,373,406号、2002年4月16日。
[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、「冗長層の二重の重いテールシリーズを備えた損失回復力のあるコード」、米国特許第6,195,777、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] Luby、M.、Mitzenmacher、M.、Shokrollahi、A.、Spielman、D。、およびV. Stemann、「不規則なグラフ化でエンコードするメッセージ」、米国特許第6,163,870、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] Luby、M.、Mitzenmacher、M.、Shokrollahi、A。and D. Spielman、「効率的な消去コード」、情報理論に関するIEEEトランザクション、特別号：グラフと反復アルゴリズムのコード、pp。569-584、vol。47、No。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] Luby、M.、Shokrollahi、A.、Stemann、V.、Mitzenmacher、M。and D. Spielman、「Loss Resilient Decoding Technique」、米国特許第6,073,250、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] Luby、M.、Shokrollahi、A.、Stemann、V.、Mitzenmacher、M。and D. Spielman、「不規則なグラフ化されたエンコード技術」、米国特許第6,081,909号、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.、Canetti、R.、Song、D。and J.D. Tygar、「マルチキャストの効率的かつ安全なソース認証」、ネットワークおよび分散システムセキュリティシンポジウム、NDSS 2001、pp。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 Computer Communication Review、Vol.27、No.2、pp.24-36、1997年4月。
[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。、「ソフトウェアFECの実現可能性について」、DEIT Tech Report、http：//www.iet.unipi.it/~luigi/softfec.ps、1997年1月。
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
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
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
Luigi Rizzo Dip. di Ing. dell'Informazione Universita` di Pisa via Diotisalvi 2, 56126 Pisa, Italy
Luigi Rizzo Dip。ディーイング。Dell'informazione Universita` Diotisalvi 2、56126 Pisa、イタリア経由
EMail:luigi@iet.unipi.it
電子メール：luigi@iet.unipi.it
Mark Handley ICSI Center for Internet Research 1947 Center St. Berkeley CA, USA, 94704
マークハンドリーICSIインターネット研究センター1947センターセントバークレーCA、米国、94704
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
ジョンクロウクロフトマルコーニコミュニケーションシステム教授ケンブリッジ大学コンピューター研究所ウィリアムゲイツビルディングJ JトムソンアベニューケンブリッジCB3 0FD
EMail: Jon.Crowcroft@cl.cam.ac.uk
Copyright (C) The Internet Society (2002). All Rights Reserved.
Copyright（c）The Internet Society（2002）。無断転載を禁じます。
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.
上記の限られた許可は永続的であり、インターネット社会またはその後継者または譲受人によって取り消されることはありません。
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
謝辞
Funding for the RFC Editor function is currently provided by the Internet Society.
RFCエディター機能の資金は現在、インターネット協会によって提供されています。