輻輳制御

輻輳制御（ふくそうせいぎょ、）は、電気通信においてトラフィックを制御し、例えばパケットの転送レートを削減するなどして中間ノードやネットワークの許容量（処理能力やリンク数）を超過することによる輻輳さらには輻輳崩壊を防ぐことである。受信側が受信バッファの容量を超えてしまう処理超過を防ぐフロー制御とは異なる概念である。
概要.
バックプレッシャー、チョークパケット、暗黙の輻輳信号は輻輳制御技術である。
バックプレッシャーとは、ソフトウェアの世界では、下流の力を「押し戻す」ためにシステムが実行するアクションを指す。
チョークパケットは、ネットワークでイベントや災害時に発生する、通信要求過多により、通信が成立しにくくなる現象における伝送制御単位である。コンピュータなどの装置で生成され、トラフィックフローを制限するために送信元装置に返送される制御単位である。
暗黙の輻輳信号となる場合は、送信元が遅延の増加とパケットの破棄を検出できる場合である。
理論.
輻輳制御の現代的理論は、Frank Kelly が先駆者である。彼は、ミクロ経済学と凸最適化理論を応用して、個々が自分のレートを制御することで最適なネットワーク転送レートを達成できることを示した。
最適な転送レートの例として、Max-Min公平性や Kelly が示唆した比例公平性があるが、他にもいろいろなものが考えられる。
最適転送レートの割り当てを数式で表すと次のようになる。フロー formula_1 の転送レートを formula_2、リンク formula_3 の容量を formula_4 とし、フロー formula_1 がリンク formula_3 を使う場合 formula_7 を 1 とし、そうでなければ 0 とする。formula_8、formula_9、formula_10 を対応するベクトルおよび行列とする。formula_11 が増大する厳密な凸関数だとする。この関数を効用と呼び、あるユーザーがレート formula_8 で送信したときに得られる利益を数値化したものである。最適な転送レートの割り当ては、以下を満たす。
この問題のラグランジュ双対は切り離され、各フローはネットワークにより伝えられた「価格」にのみ基づいて自身の転送レートを決定する。各リンクの容量が制約となり、ラグランジュ乗数 formula_15 が得られる。その総和 
がフローに対する価格になる。
従って、輻輳制御とはこの問題を解く分散最適化アルゴリズムに他ならない。現在使われている輻輳制御の多くはこのフレームワークでモデル化でき、formula_15 は損失確率とされたり、リンク formula_3 における遅延とされたりする。
このモデルの弱点は、全てのフローが同じ価格であると仮定する点である。実際にはフロー制御のウィンドウをスライドさせるとバースト的な転送が発生し、あるリンクでの損失や遅延が変化し、フローも変化する。
輻輳制御アルゴリズムの分類.
輻輳制御アルゴリズムの分類法は以下のように様々である。