輻輳制御
輻輳制御（英: congestion control）とは、電気通信においてトラフィックを制御し、例えばパケットの転送レートを削減するなどして中間ノードやネットワークの許容量（処理能力やリンク数）を超過することによる輻輳さらには輻輳崩壊を防ぐことである。受信側が受けきれなくなるのを防ぐフロー制御とは異なる概念である。
理論
輻輳制御の現代的理論は、Frank Kelly が先駆者である。彼は、ミクロ経済学と凸最適化理論を応用して、個々が自分のレートを制御することで最適なネットワーク転送レートを達成できることを示した。
最適な転送レートの例として、Max-Min公平性や Kelly が示唆した比例公平性があるが、他にもいろいろなものが考えられる。
最適転送レートの割り当てを数式で表すと次のようになる。フロー の転送レートを 、リンク の容量を とし、フロー がリンク を使う場合 を 1 とし、そうでなければ 0 とする。、、 を対応するベクトルおよび行列とする。 が増大する厳密な凸関数だとする。この関数を効用と呼び、あるユーザーがレート で送信したときに得られる利益を数値化したものである。最適な転送レートの割り当ては、以下を満たす。
- ここで
この問題のラグランジュ双対は切り離され、各フローはネットワークにより伝えられた「価格」にのみ基づいて自身の転送レートを決定する。各リンクの容量が制約となり、ラグランジュ乗数 が得られる。その総和
がフローに対する価格になる。
従って、輻輳制御とはこの問題を解く分散最適化アルゴリズムに他ならない。現在使われている輻輳制御の多くはこのフレームワークでモデル化でき、 は損失確率とされたり、リンク における遅延とされたりする。
このモデルの弱点は、全てのフローが同じ価格であると仮定する点である。実際にはフロー制御のウィンドウをスライドさせるとバースト的な転送が発生し、あるリンクでの損失や遅延が変化し、フローも変化する。
輻輳制御アルゴリズムの分類
輻輳制御アルゴリズムの分類法は以下のように様々である。
- ネットワークから得られるフィードバックの型や量で分類する。損失、遅延、シングルビット、マルチビットなど。
- 現在のインターネットからの増大時の対応によって分類する。送信側のみ修正が必要な場合、送信・受信双方で修正が必要な場合、ルーターのみ修正が必要な場合、送信側・受信側・ルーターで修正が必要な場合など。
- 性能面の改善の程度によって分類する。高帯域遅延積ネットワーク、損失性リンク、公平性、短いフローが有利となるもの、可変レートリンクなど。
- 使っている公平性基準によって分類する。Max-Min、比例、最小潜在遅延など。