線形ネットワークコーディング

コンピュータ ネットワーク において、線形ネットワーク コーディングは、中間ノードが線形結合によってソース ノードからシンク ノードにデータを送信するプログラムです。

線形ネットワーク コーディングは、ネットワークのスループット、効率、スケーラビリティを向上させるだけでなく、攻撃や盗聴を減らすためにも使用できます。ネットワークのノードは複数のパケットを受け取り、送信のために組み合わせます。このプロセスは、ネットワークで可能な限り最大の情報 フローを実現するために使用できます。

理論的には、 1つのソースを持つマルチキャスト問題では、線形符号化で上限を達成するのに十分であることが証明されています。^{[1]しかし、線形符号化は一般に十分ではありません。}畳み込み符号化やフィルタバンク符号化などのより一般的な線形バージョンでも同様です。 ^[2]任意の要求を持つ一般的なネットワーク問題に対する最適な符号化ソリューションを見つけることは困難な問題であり、NP困難^{[3] [4]} や決定不可能な場合もあります。^{[5] [6]}

線形ネットワーク コーディングの問題では、ソース ノードからシンク ノードへのデータの移動にノード グループが関与します。 各ノードは、通常サイズ の有限体から選択された係数を乗算して、過去に受信​​したパケットの線形結合である新しいパケットを生成します。${\displaystyle P}$${\displaystyle S}$${\displaystyle K}$${\displaystyle GF(2^{s})}$

より正式には、入度、の各ノードは、次の式に従って 受信したメッセージの線形結合からメッセージを生成します。${\displaystyle p_{k}}$${\displaystyle InDeg(p_{k})=S}$${\displaystyle X_{k}}$${\displaystyle \{M_{i}\}_{i=1}^{S}}$

${\displaystyle X_{k}=\sum _{i=1}^{S}g_{k}^{i}\cdot M_{i}}$

ここで、値はから選択された係数です。演算は有限体で計算されるため、生成されたメッセージは元のメッセージと同じ長さになります。各ノードは、計算された値と、レベルで使用される係数 を転送します。 ${\displaystyle g_{k}^{i}}$${\displaystyle GF(2^{s})}$${\displaystyle X_{k}}$${\displaystyle g_{k}^{i}}$${\displaystyle k^{\text{th}}}$${\displaystyle g_{k}^{i}}$

シンクノードはこれらのネットワークコード化されたメッセージを受信し、それらを行列に集める。元のメッセージは、行列に対してガウス消去法を実行することで復元できる。^[7]縮小行階段形式では、デコードされたパケットは、形式の行に対応する。${\displaystyle e_{i}=[0...010...0]}$

ネットワークは有向グラフ で表されます。はノードまたは頂点の集合、は有向リンク (またはエッジ) の集合、は の各リンクの容量を示します。をノードからノード への最大可能スループットとします。最大フロー最小カット定理により、はすべてのカットの最小容量 によって上限が定められます。これは、これら 2 つのノード間のカットのエッジの容量の合計です。 ${\displaystyle {\mathcal {G}}=(V,E,C)}$${\displaystyle V}$${\displaystyle E}$${\displaystyle C}$${\displaystyle E}$${\displaystyle T(s,t)}$${\displaystyle s}$${\displaystyle t}$${\displaystyle T(s,t)}$

カール・メンガーは、ユニキャストのシナリオでは常に上限を達成するエッジ分離パスの集合が存在することを証明しました。これは最大フロー最小カット定理として知られています。その後、フォード・フルカーソンアルゴリズムが多項式時間でそのようなパスを見つけるために提案されました。その後、エドモンズは論文「エッジ分離分岐」^{[ which? ]}で、ブロードキャストのシナリオでも上限が達成可能であることを証明し、多項式時間アルゴリズムを提案しました。

しかし、マルチキャストのシナリオでは状況がより複雑であり、実際、従来のルーティングの考え方ではこのような上限に到達することはできません。Ahlswedeらは、中間ノードで追加の計算タスク（着信パケットを1つまたは複数の発信パケットに結合する）を実行できれば、これを達成できることを証明しました。^[8]

バタフライネットワーク^[8]は、線形ネットワークコーディングがルーティングよりも優れている理由を説明するためによく使用されます。2つのソースノード（図の上部）には、2つの宛先ノード（下部）に送信する必要がある情報AとBがあります。各宛先ノードは、AとBの両方を知りたいと考えています。各エッジは1つの値のみを運ぶことができます（各タイムスロットで1ビットを送信するエッジと考えることができます）。

ルーティングのみが許可されている場合、中央のリンクは A または B のみを伝送でき、両方を伝送することはできません。中央経由で A を送信すると、左の宛先は A を 2 回受信しますが、B はまったく認識されません。B を送信すると、右の宛先で同様の問題が発生します。ルーティングが不十分であると言われるのは、ルーティング スキームでは A と B の両方を同時に両方の宛先に送信できないためです。一方、両方の宛先ノードが A と B を認識するには、合計 4 つのタイム スロットが必要です。

図に示すように、単純なコードを使用すると、2 つのリレー ノードを介してシンボルの合計を送信することで、A と B を両方の宛先に同時に送信できます。つまり、式「A+B」を使用して A と B をエンコードします。左側の宛先は A と A + B を受信し、2 つの値を減算することで B を計算できます。同様に、右側の宛先は B と A + B を受信し、A と B の両方を決定で​​きます。したがって、ネットワーク コーディングでは、3 つのタイム スロットしかかからず、スループットが向上します。

ランダム線形ネットワーク符号化^[9] (RLNC) はシンプルですが強力な符号化方式で、ブロードキャスト伝送方式では分散アルゴリズムを使用してほぼ最適なスループットを実現します。ノードは受信したパケットのランダム線形結合を送信します。係数はガロア体から一様分布でランダムに選択されます。体のサイズが十分に大きい場合、受信者が線形独立な結合を取得する確率 (したがって革新的な情報を取得する確率) は 1 に近づきます。ただし、ランダム線形ネットワーク符号化は優れたスループット性能を備えていますが、受信者が取得するパケット数が不十分な場合、元のパケットを復元できる可能性は極めて低いことに注意してください。これは、受信者が適切な数のパケットを取得するまで追加のランダム線形結合を送信することで対処できます。

RLNC には 3 つの重要なパラメータがあります。最初のパラメータは世代サイズです。RLNC では、ネットワークを介して送信される元のデータはパケットに分割されます。ネットワーク内のソース ノードと中間ノードは、元のパケットとコード化されたパケットのセットを結合および再結合できます。元のパケットは、通常、世代と呼ばれるブロックを形成します。結合および再結合された元のパケットの数は、世代サイズです。2 番目のパラメータはパケット サイズです。通常、元のパケットのサイズは固定です。サイズが不均等なパケットの場合、短い場合はゼロ パディングされ、長い場合は複数のパケットに分割されます。実際には、パケット サイズは、基盤となるネットワーク プロトコルの最大転送単位(MTU) のサイズになります。たとえば、イーサネット フレームでは約 1500 バイトになります。3 番目の重要なパラメータは、使用されるガロア フィールドです。実際には、最も一般的に使用されるガロア フィールドはバイナリ拡張フィールドです。ガロア フィールドの最も一般的に使用されるサイズは、バイナリ フィールドといわゆるバイナリ 8 ( ) です。バイナリ フィールドでは、各要素の長さは 1 ビットですが、バイナリ 8 では 1 バイトです。パケット サイズは通常フィールド サイズよりも大きいため、各パケットはガロア フィールドの要素 (通常はシンボルと呼ばれます) が結合されたセットとして表示されます。パケットには固定数のシンボル (ガロア フィールド要素) があり、すべての操作はガロア フィールド上で実行されるため、パケットのサイズは後続の線形結合によって変化しません。 ${\displaystyle M}$${\displaystyle GF(2)}$${\displaystyle GF(2^{8})}$

ソースと中間ノードは、線形演算を実行して、元のパケットと以前にコード化されたパケットの任意のサブセットを組み合わせることができます。RLNC でコード化されたパケットを形成するには、元のパケットと以前にコード化されたパケットをランダムに選択された係数で乗算し、一緒に加算します。各パケットはガロア体の要素の付加セットにすぎないため、乗算と加算の演算は、例の図に示すように、パケットの個々のシンボルごとにシンボル単位で実行されます。

コードのステートレス性を保つために、コード化パケットの生成に使用されたコード化係数は、ネットワーク経由で送信されるパケットに追加されます。したがって、ネットワーク内の各ノードは、各コード化パケットの生成に使用された係数を確認できます。従来のブロック コードと比較した線形ネットワーク コーディングの目新しい点の 1 つは、以前にコード化されたパケットを新しい有効なコード化パケットに再結合できることです。このプロセスは通常、再コーディングと呼ばれます。再コーディング操作の後、追加されたコード化係数のサイズは変わりません。すべての操作は線形であるため、ペイロードと追加されたコード化係数に同じ加算と乗算の操作を適用することで、再コード化されたパケットの状態を保存できます。次の例では、このプロセスについて説明します。

宛先ノードは、元のデータを再構築するために十分な線形独立コード化パケットを収集する必要があります。コード化された各パケットは、係数がパケットに追加されるため既知である線形方程式として理解できます。これらの方程式では、元の各パケットは未知数です。線形方程式系を解くには、宛先には少なくとも線形独立方程式 (パケット) が必要です。 ${\displaystyle M}$${\displaystyle M}$

図では、2 つのパケットが線形に結合されて新しいコード化パケットになる例を見ることができます。この例では、パケットとパケットという 2 つのパケットがあります。この例の世代サイズは 2 です。これは、各パケットに 2 つのコーディング係数 ( ) が付加されていることからわかります。付加された係数は、ガロア体から任意の値を取ることができます。ただし、元のコード化されていないデータ パケットには、コーディング係数またはが付加されます。つまり、これらは、パケットの 1 つを 0 倍し、もう 1 つのパケットを 1 倍した線形結合によって構築されます。コード化されたパケットには、他の係数が付加されます。この例では、たとえばパケット に係数 が付加されています。ネットワーク コーディングは通信プロトコルのどの層でも適用できるため、これらのパケットには他の層のヘッダーが含まれることがありますが、これはネットワーク コーディング操作では無視されます。 ${\displaystyle f}$${\displaystyle e}$${\displaystyle C_{ij}}$${\displaystyle [0,1]}$${\displaystyle [1,0]}$${\displaystyle f}$${\displaystyle [C_{11},C_{12}]}$

ここで、ネットワーク ノードがパケットとパケット を組み合わせて新しいコード化パケットを生成すると仮定します。RLNC では、2 つのコード化係数 (この例では と) がランダムに選択されます。ノードはパケット の各シンボルにを乗算し、パケット の各シンボルに を乗算します。次に、結果をシンボルごとに加算して、新しいコード化データを生成します。コード化パケットのコード化係数に対して、乗算と加算の同じ操作を実行します。 ${\displaystyle f}$${\displaystyle e}$${\displaystyle d_{1}}$${\displaystyle d_{2}}$${\displaystyle f}$${\displaystyle d_{1}}$${\displaystyle e}$${\displaystyle d_{2}}$

線形ネットワーク コーディングはまだ比較的新しいテーマです。しかし、このテーマは過去 20 年間にわたって広範囲に研究されてきました。それでも、もはや当てはまらない誤解がいくつか残っています。

デコードの計算複雑性:ネットワーク コーディング デコーダーは長年にわたって改良されてきました。現在、アルゴリズムは非常に効率的で並列化可能です。2016 年には、SIMD命令が有効になっている Intel Core i5 プロセッサーでは、ネットワーク コーディングのデコード グッドプットは、16 パケットの生成サイズで 750 MB/秒、64 パケットの生成サイズで 250 MB/秒でした。^[10]さらに、今日のアルゴリズムは大幅に並列化できるため、エンコードとデコードのグッドプットがさらに向上します。^[11]

送信オーバーヘッド:ネットワーク コーディングの送信オーバーヘッドは、各コード化パケットにコーディング係数を付加する必要があるため、通常は高いと考えられています。実際には、このオーバーヘッドはほとんどのアプリケーションで無視できます。コーディング係数によるオーバーヘッドは、次のように計算できます。各パケットには、付加されたコーディング係数があります。各係数のサイズは、ガロア体の 1 つの要素を表すために必要なビット数です。実際には、ほとんどのネットワーク コーディング アプリケーションでは、1 世代あたり 32 パケット以下の世代サイズと、256 要素 (バイナリ 8) のガロア体を使用します。これらの数値では、各パケットに付加されたオーバーヘッドのバイトが必要です。各パケットの長さが 1500 バイト (つまり、イーサネット MTU) の場合、32 バイトは 2% のオーバーヘッドに過ぎません。 ${\displaystyle M}$${\displaystyle M*log_{2}(s)=32}$

線形依存性によるオーバーヘッド: RLNC ではコーディング係数がランダムに選択されるため、送信されるコーディング パケットの一部は、線形依存性のあるパケットの組み合わせを使用して形成されるため、宛先にとって有益ではない可能性があります。ただし、このオーバーヘッドはほとんどのアプリケーションで無視できます。線形依存性はガロア体のサイズに依存し、使用される生成サイズとは実質的に無関係です。次の例でこれを説明できます。要素のガロア体と生成サイズのパケットを使用していると仮定します。宛先がコーディング パケットを受信して​​いない場合、自由度があるとされ、ほぼすべてのコーディング パケットが有用かつ革新的になります。実際、ゼロ パケット (コーディング係数がゼロのみ) のみが革新的ではありません。ゼロ パケットを生成する確率は、各コーディング係数がガロア体のゼロ要素に等しい確率に等しくなります。つまり、革新的でないパケットの確率は です。連続する革新的な送信ごとに、革新的でないパケットの確率の指数が 1 ずつ減少することが示されています。宛先が革新的なパケットを受信した場合 (つまり、データを完全にデコードするのにあと 1 つのパケットのみが必要な場合)、革新的でないパケットの確率は です。この知識を使用して、世代あたりの線形従属パケットの予想数を計算できます。最悪のシナリオでは、使用するガロア体に 2 つの要素のみが含まれる場合 ( )、世代あたりの線形従属パケットの予想数は 1.6 個の追加パケットです。世代のサイズが 32 または 64 パケットの場合、これはそれぞれ 5% または 2.5% のオーバーヘッドを表します。バイナリ 8 フィールド ( ) を使用する場合、世代あたりの線形従属パケットの予想数は実質的にゼロです。線形依存関係によるオーバーヘッドの主な原因は最後のパケットであるため、この知識を活用する調整可能なスパース ネットワーク コーディング^[12]などの RLNC ベースのプロトコルがあります。これらのプロトコルは、送信開始時にコーディング係数にスパース性（ゼロ要素）を導入してデコードの複雑さを軽減し、送信終了時にスパース性を低減して線形依存性によるオーバーヘッドを軽減します。 ${\displaystyle q}$${\displaystyle M}$${\displaystyle M}$${\displaystyle M}$${\displaystyle {\frac {1}{q^{M}}}}$${\displaystyle M-1}$${\displaystyle {\frac {1}{q}}}$${\displaystyle q=2}$${\displaystyle q=256}$

長年にわたり、多くの研究者や企業がネットワークコーディングソリューションをアプリケーションに統合してきました。^[13]さまざまな分野におけるネットワークコーディングのアプリケーションをいくつか挙げることができます。

• VoIP : ^[14]無線メッシュネットワークを介したVoIPなどのストリーミングサービスのパフォーマンスは、ネットワークコーディングによってネットワーク遅延とジッタを低減することで向上できます。^[要出典]
• ビデオ^[15]とオーディオ^[16]のストリーミングと会議: ^{[17] [18]}パケット消失が発生しやすい無線ネットワーク上でのMPEG-4トラフィックの遅延、パケット損失、ジッターに関するパフォーマンスは、RLNC によって改善できます。 ^[15]無線メッシュ ネットワーク上のオーディオ ストリーミングの場合、簡易マルチキャスト転送や部分的ドミナント プルーニングなどのパケット転送ベースのプロトコルの代わりに RLNC を使用すると、ネットワークのパケット配信率、待ち時間、ジッター パフォーマンスが大幅に向上します。^[16]ビデオ会議のネットワーク コーディングによるパフォーマンスの向上は、理論上のものではありません。 2016 年に、^{[17]の著者らは、ネットワーク コーディング ベースのビデオ会議システムの実現可能性を評価するために、15 台のワイヤレス}Androidデバイスの実際のテストベッドを構築しました。 その結果、パケット転送に基づくマルチキャスト技術と比較して、特に品質の悪いリンク上で、パケット配信率と全体的なユーザー エクスペリエンスが大幅に向上することが示されました。
• ソフトウェア定義広域ネットワーク（SD-WAN）：^{[19] [20] [21] [22]}大規模な産業用IoTワイヤレスネットワークは、ネットワークコーディングの恩恵を受けることができます。研究者らは、ネットワークコーディングとそのチャネルバンドル機能により、複数のセルラー接続を持つ多数のノードを持つSD-WANのパフォーマンスが向上することを示しました[ ^{19] 。今日では、}バラクーダなどの企業は、低遅延、コンピューティングデバイスのフットプリントが小さい、オーバーヘッドが低いという利点があるため、RLNCベースのソリューションを採用しています。^{[21] [22]}
• チャネルバンドリング：^[23] RLNC はステートレスなため、チャネルバンドリング、つまり複数のネットワークインターフェースを介した情報伝送を効率的に実行できます。^[23]コード化パケットはランダムに生成され、コードの状態はコード化パケットとともにネットワークを通過するため、送信元はコード化パケットをすべてのネットワークインターフェースを介して送信するだけで、あまり計画を立てずにバンドリングを実現できます。宛先は、ネットワークインターフェースに関係なく、コード化パケットが十分に到着すると情報をデコードできます。RLNC のチャネルバンドリング機能を紹介するビデオは、こちらでご覧いただけます。^[24]
• 5Gプライベートネットワーク：^{[25] [26] RLNCを}5G NR標準に統合することで、5Gシステムでのビデオ配信のパフォーマンスを向上させることができます。^{[25] 2018年に}コンシューマーエレクトロニクスショーで発表されたデモでは、NFVとSDNテクノロジーを備えたRLNCの実用的な展開が示され、コアネットワークの輻輳によるパケット損失に対するビデオ品質が向上しました。^[26]
• リモートコラボレーション^[27]
• 拡張現実による遠隔サポートとトレーニング。^[28]
• 遠隔車両運転アプリケーション。^{[29] [30] [31] [32]}
• コネクテッドカーネットワーク。^{[33] [34]}
• 低遅延ストリーミングやマルチプレイヤー接続などのゲームアプリケーション。^{[35] [36] [37] [38]}
• ヘルスケアアプリケーション。^{[39] [40] [41]}
• インダストリー4.0 [ ^{42] [43] [44]}
• 衛星ネットワーク^[45]
• 農業用センサーフィールド^{[46] [47]}
• 機内エンターテイメントネットワーク^[48]
• モバイル製品ファミリー向けの主要なセキュリティおよびファームウェアのアップデート。^{[49] [50]}
• スマートシティインフラ。^{[51] [52]}
• 情報中心ネットワークと名前付きデータネットワーク: ^[53]線形ネットワークコーディングは、そのようなシステムのマルチソースマルチキャストの性質を利用することで、情報中心ネットワークソリューションのネットワーク効率を向上させることができます。^{[53] RLNCを}IPFSなどの分散コンテンツ配信ネットワークに統合することで、ストレージリソースを削減しながらデータの可用性を高めることができることが示されています。 ^[54]
• 従来のネットワークやパケット損失のある無線ネットワークにおける前方誤り訂正や自動再送要求の代替手段として、コード化TCP ^[55]やマルチユーザーARQ ^[56]などがある。
• スヌーピング、盗聴、リプレイ、データ破損などのネットワーク攻撃に対する保護。^{[57] [58]}
• デジタルファイル配布とP2Pファイル共有、例：MicrosoftのAvalancheファイルシステム
• 分散ストレージ^{[53] [59] [60]}
• 無線メッシュネットワークにおけるスループットの向上、例：COPE、^[61] CORE、^[62]コーディングを考慮したルーティング、[ ^63] BATMAN ^[64]
• 空間センサーネットワークにおけるバッファと遅延の削減：空間バッファ多重化^[65]
• 無線ブロードキャスト：^[66] RLNCはシングルホップ無線マルチキャストネットワークのパケット送信数を削減し、ネットワーク帯域幅を向上させることができる^[66]
• 分散ファイル共有^[67]
• モバイルデバイスへの低複雑性ビデオストリーミング^[68]
• デバイス間拡張^{[69] [70] [71] [72] [73]}

• 秘密共有プロトコル
• ネットワークコーディングのための準同型署名
• 三角ネットワークコーディング

• Fragouli, C.、Le Boudec, J.、Widmer, J.「ネットワーク コーディング: すぐに使える入門書」Computer Communication Review、2006 年。https://doi.org/10.1145/1111322.1111337
• Ali Farzamnia、Sharifah K. Syed-Yusof、Norsheila Fisa「p-Cycle ネットワーク コーディングを使用したマルチキャスティング複数記述コーディング」、KSII Transactions on Internet and Information Systems、Vol 7、No 12、2013。doi :10.3837/ tiis.2013.12.009

• ネットワークコーディングホームページ
• ネットワークコーディングの参考文献
• Raymond W. Yeung、情報理論とネットワークコーディング、Springer 2008、http://iest2.ie.cuhk.edu.hk/~whyeung/book2/
• Raymond W. Yeung 他著、「ネットワーク コーディング理論」、now Publishers、2005 年、http://iest2.ie.cuhk.edu.hk/~whyeung/netcode/monograph.html
• Christina Fragouli 他、「ネットワーク コーディング: インスタント入門」、ACM SIGCOMM 2006、http://infoscience.epfl.ch/getfile.py?mode=best&recid=58339。
• Avalanche ファイルシステム、http://research.microsoft.com/en-us/projects/avalanche/default.aspx
• ランダム ネットワーク コーディング、https://web.archive.org/web/20060618083034/http://www.mit.edu/~medard/coding1.htm
• デジタル ファウンテン コード、http://www.icsi.berkeley.edu/~luby/
• コーディングを考慮したルーティング、https://web.archive.org/web/20081011124616/http://arena.cse.sc.edu/papers/rocx.secon06.pdf
• MITではネットワークコーディング入門コースを提供しています
• ネットワーク コーディング: ネットワークの次の革命?
• ワイヤレス ネットワークのコーディングを考慮したプロトコル設計: http://scholarcommons.sc.edu/etd/230/