ネットワークコーディングの原理と利点

「転送するだけ」をやめる発想

従来のネットワークでは、中継ノード（ルータやスイッチ）の仕事はパケットを蓄積して転送することに限られます。受信したビット列はそのまま、宛先に向けて出力ポートへ流すだけです。ネットワークコーディングは、この大前提を覆します。中継点が複数の受信パケットを符号化して混ぜ合わせ、新しいパケットを生成して送る——この一手間が、同じ物理帯域でより多くの情報を運べる場面を生みます。

混ぜ方の中心は線形結合です。各パケットをある体（フィールド）上のベクトルとみなし、係数をかけて足し合わせます。係数の集合（符号化に使った重み）さえ受信側に伝われば、受信側は逆算して元のパケットを取り出せます。鍵は「転送＝コピー」という素朴な仮定が、マルチキャストや無線では最適でないことにあります。

バタフライネットワーク：容量の上限に届く

ネットワークコーディングの威力を最小の例で示すのがバタフライネットワークです。送信元 S が2つのビット a と b を、2つの宛先 T1 と T2 の両方に届けたいとします。網の途中には1本だけ容量1の共有リンク（ボトルネック）があり、ここを a と b の両方が通らなければなりません。

純粋なルーティング（転送だけ）では、この共有リンクに a か b のどちらか一方しか流せません。a を流せば T2 が b を受け取れず、b を流せば T1 が a を受け取れない。つまり片方の宛先は1ビット足りなくなります。

ネットワークコーディングはここを次のように解きます。

中継ノード(共有リンクの入口)で:
  受信した a と b を XOR して a⊕b を作る
  共有リンクには a⊕b の1ビットだけを流す

宛先 T1: 別経路で a を直接受信済み → (a⊕b) ⊕ a = b を復元
宛先 T2: 別経路で b を直接受信済み → (a⊕b) ⊕ b = a を復元

共有リンクには1ビット（a⊕b）しか流していないのに、両方の宛先が a と b の2ビットを再構成できました。これにより、グラフのカット容量で決まるマルチキャスト容量の理論上限（最大フロー＝最小カット）を実際に達成できます。ルーティングだけではこの上限に届かないことがある、というのが理論的な核心です。

復号の数理：有限体上の連立一次方程式

XOR はビット単位の例ですが、一般には有限体（ガロア体）GF(2^8) などの上で演算します。GF(2^8) は1バイトを1つの元として扱えるため実装に都合がよく、加算は XOR、乗算は多項式の積を既約多項式で割った剰余として定義されます。同じ多項式除算の世界はイーサネットの CRC 誤り検出でも使われており、GF(2) 上の代数という共通の土台に立っています。

元データを n 個のパケット {p1, ..., pn}（それぞれ体上のベクトル）に分割するとします。符号化ノードは係数 {c1, ..., cn} を選び、次の線形結合を生成します。

y = c1*p1 + c2*p2 + ... + cn*pn   （演算はすべて GF(2^8) 上）

受信側は係数ベクトル {c1, ..., cn} を（パケットヘッダに載せるなどして）受け取り、複数の符号化パケット y を集めます。n 個の符号化パケットが集まれば、係数を並べた n×n 行列 C と未知の元パケットベクトル P について次の連立方程式が立ちます。

Y = C * P
P = C^(-1) * Y     （C が正則なら逆行列で復元）

つまり復号は係数行列の逆行列を求める操作に帰着します。復号できる条件は、集めた n 個の符号化パケットの係数ベクトルが一次独立で、行列 C が正則（行列式が0でない）であることです。一次従属な符号化パケットは新しい情報を含まず、復号には役立ちません。

無線マルチキャストへの応用

ネットワークコーディングが特に効くのが無線です。無線は電波が周囲に同報される性質（ブロードキャスト性）を持ち、1回の送信を複数の端末が同時に聞けます。この性質と符号化を組み合わせると、再送回数を劇的に減らせます。

代表例が COPE 型の機会的符号化です。中継ノード R が端末 A と B の間を仲介する状況を考えます。

従来（転送のみ）: A→R→B と B→R→A で R は計2回送信
符号化あり:
  R は p_A⊕p_B を 1回だけブロードキャスト
  A は自分が送った p_A を覚えている → (p_A⊕p_B)⊕p_A = p_B を得る
  B は自分が送った p_B を覚えている → (p_A⊕p_B)⊕p_B = p_A を得る

2回必要だった中継送信が1回で済み、無線媒体の占有時間が半分になります。無線では送信機会そのものが希少資源なので、これはCSMA/CA とバックオフで媒体を奪い合う回数を減らすことに直結します。さらにパケットロスが多い無線リンクでは、RLNC により「どのパケットが落ちても、一次独立な符号化パケットが規定数届けば復元できる」ため、個別パケットの再送（どの番号が落ちたかを特定して送り直す）が不要になり、フィードバックの往復遅延を隠せます。

利点と代償の整理

ネットワークコーディングの利点は、(1) マルチキャストで理論上限のスループットに届く、(2) 無線で再送と送信回数を減らす、(3) RLNC により個別パケットの取りこぼしに強くなる（消失訂正に近い効果）、の3点に集約されます。一方で代償もあります。

• 計算コスト: 中継・受信ノードに有限体の乗算と逆行列計算が増える。体のサイズが大きいほど一次独立性は確保しやすいが演算は重くなる。
• 係数のオーバーヘッド: 符号化に使った係数ベクトルをヘッダで運ぶため、ペイロードに対する純帯域は若干削られる。
• 遅延の性質が変わる: 復号には n 個の独立パケットが揃う必要があり、最後の1個が届くまで何も取り出せない場面がある（ブロック単位の復号遅延）。

まとめ

ネットワークコーディングは「中継は転送するだけ」という固定観念を、有限体上の線形結合で置き換える技術です。バタフライネットワークはルーティングの限界とマルチキャスト容量の到達可能性を示す最小例であり、復号は係数行列の逆行列計算という連立一次方程式に帰着します。無線の同報性と組み合わせると再送・送信回数を削減でき、マルチキャスト配信やCDN 的な大規模同報の効率を、転送一辺倒では届かない領域へ押し上げる理論的な基盤になります。