輻輳制御

ウィキペディア

輻輳制御

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/04/19 19:24 UTC 版)

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

概要

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

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

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

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

理論

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

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

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

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

ここで ${\displaystyle Rx\leq c}$

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

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

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

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

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

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

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

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

脚注

1. ^ ^{a b} Stallings, William (2016). Foundations of modern networking : SDN, NFV, QoE, IoT, and Cloud. Florence Agboma, Sofiene Jelassi. Indianapolis, Indiana. ISBN 978-0-13-417547-8. OCLC 927715441. https://www.worldcat.org/oclc/927715441 
2. ^ Wu, Pei-Ming. “Preventing Systemic Failure: Backpressure—What It Is and How It Works - Glasnostic Blog” (英語). https://glasnostic.com. 2021年11月30日閲覧。
3. ^ “CAPTER 13 :CONGESTION CONTROL IN DATA NETWORK”. 2021年11月30日閲覧。

関連項目

• 帯域制御
• Quality of Service
• Transmission Control Protocol
• Bufferbloat
• 明示的輻輳通知（英語版）
• L4S（英語版）
• en:Sally Floyd - 輻輳制御に対して多大な貢献をした研究者として知られる。

外部リンク

• Random Early Detection
• Explicit Congestion Notification
• TFRC Homepage

ウィキペディア小見出し辞書

輻輳制御

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/01 19:49 UTC 版)

「Transmission Control Protocol」の記事における「輻輳制御」の解説

TCPは高性能を達成し輻輳崩壊（ネットワーク性能が数桁のオーダーで低下する現象）を防ぐため、輻輳制御機構をいくつか備えている。ネットワークに流入させるデータレートを制御し、崩壊のきっかけとなるようなレート未満でデータを送るよう保つ。また、おおまかに最大最小公平（英語版）なフロー割り当てを目指す。 送信データへの ACK (確認応答)の有無は、送信側でネットワークの状態を推測する材料となる。これをタイマと組み合わせ、データのフローの振る舞いを変化させることができる。これを一般に輻輳制御またはネットワーク輻輳回避などと呼ぶ。 最近のTCP実装では、スロースタート（英語版）、輻輳回避（英語版）、TCP高速再送アルゴリズム（英語版）、ファストリカバリ(en, RFC 5681) という4つの相互にからみあったアルゴリズムを使用している。 スループットをあげるため輻輳しない限界まで送信側はスライディングウィンドウを大きくする必要があるが、ウィンドウサイズを調整する輻輳回避アルゴリズムは長年研究されている。一覧は w:TCP congestion avoidance algorithm を参照。かつては、輻輳するとパケットロスが発生することを利用し、パケットロスをベースにした TCP Reno およびそれを改良した TCP NewReno (RFC 3782) がよく使われていたが、現在では、送信側のスライディングウィンドウにどれだけの時間とどまっていたかを元にしたアルゴリズム (Delay-based Congestion Avoidance) が中心になっており、Microsoft Windows では、Windows Vista 以降は、Compound TCP（英語版） が採用され、Linux では 2.6.8〜2.6.18 は BIC TCP（英語版） が、2.6.19 以降は CUBIC TCP（英語版） が使われている。 さらに送信側には「再送タイムアウト (RTO)」があり、送信してから確認応答が戻るまでの時間であるラウンドトリップタイム (RTT) を推算し、ばらつきも考慮して設定する。このタイマの動作は RFC 2988 で規定されている。RTTの推算には微妙な点がある。例えば、再送パケットのRTTを計算する場合は注意しなければならず、一般にカーンのアルゴリズム（英語版）やTCPタイムスタンプ（RFC 1323 参照）を使う。個々のRTTの標本から時系列で平均をとり、ジェイコブソンのアルゴリズムを使って Smoothed Round Trip Time (SRTT) を生成する。最終的にSRTT値がRTTの推算に使われる。 TCPを拡張して、喪失を高信頼に扱ったり、誤りを最小化したり、輻輳を制御してより高速化しようという試みが今も行われている。