輻輳制御のソースを表示

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

== 概要 ==
バックプレッシャー、[[チョークパケット]]、暗黙の輻輳信号は輻輳制御技術である<ref name=":0">{{Cite book|title=Foundations of modern networking : SDN, NFV, QoE, IoT, and Cloud|url=https://www.worldcat.org/oclc/927715441|date=2016|location=Indianapolis, Indiana|isbn=978-0-13-417547-8|oclc=927715441|others=Florence Agboma, Sofiene Jelassi|first=William|last=Stallings}}</ref>。

バックプレッシャーとは、ソフトウェアの世界では、下流の力を「押し戻す」ためにシステムが実行するアクションを指す<ref>{{Cite web|title=Preventing Systemic Failure: Backpressure—What It Is and How It Works - Glasnostic Blog|url=https://glasnostic.com/blog/preventing-systemic-failure-backpressure|website=https://glasnostic.com|accessdate=2021-11-30|language=en|first=Pei-Ming|last=Wu}}</ref>。

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

暗黙の輻輳信号となる場合は、送信元が遅延の増加とパケットの破棄を検出できる場合である<ref>{{Cite web|url=http://site.iugaza.edu.ps/djabal/files/Network-Lecture-3.pdf|title=CAPTER 13 :CONGESTION CONTROL IN DATA NETWORK|accessdate=2021-11-30}}</ref>。

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

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

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

:  <math>\max\limits_x \sum_i U(x_i)</math>
:  ここで <math>Rx \le c</math>

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

: <math>y_i=\sum_l p_l r_{li}</math>

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

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

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

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

== 脚注 ==
{{reflist}}

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

== 外部リンク ==
*[http://www.icir.org/floyd/red.html Random Early Detection]
*[http://www.icir.org/floyd/ecn.html Explicit Congestion Notification]
*[http://www.icir.org/tfrc/ TFRC Homepage]

{{Normdaten}}
{{DEFAULTSORT:ふくそうせいきよ}}
[[Category:電気通信]]
[[Category:通信工学]]
[[Category:アクセス制御]]

[[de:Überlastkontrolle]]