輻輳制御

輻輳制御（ふくそうせいぎょ、英: congestion control）は、電気通信においてトラフィックを制御し、例えばパケットの転送レートを削減するなどして中間ノードやネットワークの許容量（処理能力やリンク数）を超過することによる輻輳さらには輻輳崩壊を防ぐことである。受信側が受信バッファの容量を超えてしまう処理超過を防ぐフロー制御とは異なる概念である。

概要

バックプレッシャー、チョークパケット、暗黙の輻輳信号は輻輳制御技術である。

バックプレッシャーとは、ソフトウェアの世界では、下流の力を「押し戻す」ためにシステムが実行するアクションを指す。

チョークパケットは、ネットワークでイベントや災害時に発生する、通信要求過多により、通信が成立しにくくなる現象における伝送制御単位である。コンピュータなどの装置で生成され、トラフィックフローを制限するために送信元装置に返送される制御単位である。

暗黙の輻輳信号となる場合は、送信元が遅延の増加とパケットの破棄を検出できる場合である。

理論

輻輳制御の現代的理論は、Frank Kelly が先駆者である。彼は、ミクロ経済学と凸最適化理論を応用して、個々が自分のレートを制御することで最適なネットワーク転送レートを達成できることを示した。

最適な転送レートの例として、Max-Min公平性や Kelly が示唆した比例公平性があるが、他にもいろいろなものが考えられる。

最適転送レートの割り当てを数式で表すと次のようになる。フロー $i$ の転送レートを $x_{i}$、リンク $l$ の容量を $C_{l}$ とし、フロー $i$ がリンク $l$ を使う場合 $r_{li}$ を 1 とし、そうでなければ 0 とする。$x$、$c$、$R$ を対応するベクトルおよび行列とする。$U(x)$ が増大する厳密な凸関数だとする。この関数を効用と呼び、あるユーザーがレート $x$ で送信したときに得られる利益を数値化したものである。最適な転送レートの割り当ては、以下を満たす。

$\max \limits _{x}\sum _{i}U(x_{i})$

ここで $Rx\leq c$

この問題のラグランジュ双対は切り離され、各フローはネットワークにより伝えられた「価格」にのみ基づいて自身の転送レートを決定する。各リンクの容量が制約となり、ラグランジュ乗数 $p_{l}$ が得られる。その総和

$y_{i}=\sum _{l}p_{l}r_{li}$

がフローに対する価格になる。

従って、輻輳制御とはこの問題を解く分散最適化アルゴリズムに他ならない。現在使われている輻輳制御の多くはこのフレームワークでモデル化でき、$p_{l}$ は損失確率とされたり、リンク $l$ における遅延とされたりする。

このモデルの弱点は、全てのフローが同じ価格であると仮定する点である。実際にはフロー制御のウィンドウをスライドさせるとバースト的な転送が発生し、あるリンクでの損失や遅延が変化し、フローも変化する。

輻輳制御アルゴリズムの分類

輻輳制御アルゴリズムの分類法は以下のように様々である。

• ネットワークから得られるフィードバックの型や量で分類する。損失、遅延、シングルビット、マルチビットなど。
• 現在のインターネットからの増大時の対応によって分類する。送信側のみ修正が必要な場合、送信・受信双方で修正が必要な場合、ルーターのみ修正が必要な場合、送信側・受信側・ルーターで修正が必要な場合など。
• 性能面の改善の程度によって分類する。高帯域遅延積ネットワーク、損失性リンク、公平性、短いフローが有利となるもの、可変レートリンクなど。
• 使っている公平性基準によって分類する。Max-Min、比例、最小潜在遅延など。

関連項目

• 帯域制御
• Quality of Service
• Transmission Control Protocol
• Bufferbloat
• en:Sally Floyd - 輻輳制御に対して多大な貢献をした研究者として知られる。

外部リンク

• Random Early Detection
• Explicit Congestion Notification
• TFRC Homepage