輻輳制御の原則

輻輳制御は、送信者が共有ネットワークにデータを注入するレートを調整し、総需要が容量の近くに維持されるようにする。これにより、提供された負荷がネットワークの配信能力を圧倒したときに発生する輻輳崩壊を回避する。

Definition

輻輳制御とは、ネットワーク輻輳の信号に応じて送信者が送信レートを調整し、競合するフロー間で公平に共有しながら、総負荷をネットワークの容量近くに保つための一連のメカニズムである。

Scope

このトピックでは、輻輳制御の原則と実践について説明する。具体的には、フロー制御との区別、輻輳の原因とコスト、エンドツーエンドとネットワーク支援型アプローチ、加算増加/乗算減少（AIMD）ダイナミクスとその公平性および安定性特性、TCPの具体的なアルゴリズム（スロースタート、輻輳回避、高速回復）、明示的輻輳通知の役割、代替アルゴリズムの存在などである。ただし、ネットワークの過負荷ではなく損失回復に対処する接続ごとの信頼性メカニズムは含まれない。

Core questions

• 輻輳制御はフロー制御とどのように異なるのか？
• 輻輳は何が原因で発生し、輻輳崩壊とは何か？
• AIMDダイナミクスとは何か、なぜ公平性と安定性をもたらすのか？
• TCPのスロースタート、輻輳回避、高速回復の各フェーズはどのように機能するのか？
• エンドツーエンド（損失/遅延）信号は、ECNなどのネットワーク支援信号と比較してどうか？

Key concepts

• 輻輳とフロー制御
• 輻輳崩壊
• 加算増加/乗算減少（AIMD）
• スロースタート
• 輻輳回避
• 高速再送と高速回復
• 輻輳ウィンドウ
• 明示的輻輳通知（ECN）
• 公平性と効率性

Key theories

加算増加、乗算減少（AIMD）

輻輳がない間は送信ウィンドウを線形に増加させ、輻輳信号があった場合は半分にすることで、競合するフローが容量を均等かつ効率的に共有するように誘導される。分析により、AIMDは公平性と効率性に収束することが示されており、これがTCPが採用する理由である。

TCP輻輳制御フェーズ

TCPは、指数関数的なスロースタートで帯域幅をプローブし、推定容量に近づくと線形的な輻輳回避に切り替わる。また、個別の損失に反応するために、再開することなく高速再送/高速回復を使用し、主にパケット損失から輻輳を推測する。

輻輳崩壊の回避

レート制御がない場合、過負荷時の再送はネットワークを輻輳崩壊に陥らせ、スループットが急落する可能性がある。1980年代後半に輻輳回避が導入されたことで、インターネットは繰り返される崩壊から救われた。

Clinical relevance

輻輳制御は、共有インターネットが重い負荷の下でも利用可能であるための重要な要素である。1980年代後半以来、システム全体の崩壊を防ぎ、何十億ものフローに対してスループット、遅延、公平性のバランスを継続的に維持してきた。その設計は、ダウンロード速度、ビデオストリーミング品質、データセンターのパフォーマンスに直接影響を与え、CUBICやBBRなどのアルゴリズムや低遅延キュー管理に関する活発な研究が、このバランスを洗練し続けている。

History

1986年から1987年にかけて初期のインターネットで一連の輻輳崩壊が発生した後、Van Jacobsonの1988年の研究でスロースタートと輻輳回避が導入され、現代のTCP輻輳制御が確立された。ChiuとJainの1989年の分析は、AIMDが公平性と効率性をもたらす理由を説明した。その後の数十年間で、Reno、NewReno、CUBIC、モデルベースのBBRなどのバリアント、およびREDやECNなどのルーター側メカニズムが開発された。

Debates

損失ベースと遅延・モデルベースの輻輳制御

損失ベースのTCPはバッファがオーバーフローしたときにのみ反応するため、高い遅延（バッファブロート）を引き起こしたり、高速な長距離リンクを十分に活用できなかったりする可能性がある。これがBBRのような遅延ベースおよびモデルベースのスキームを動機付けている。これらのスキームが従来の損失ベースのフローと共存する場合の公平性が議論の中心となっている。

Key figures

• Van Jacobson
• Dah-Ming Chiu
• Raj Jain
• Sally Floyd

Seminal works

• jacobson1988
• chiu1989
• kurose2021

Frequently asked questions

フロー制御と輻輳制御の違いは何ですか？

フロー制御は受信者を保護するもので、高速な送信者が低速な受信者のバッファを溢れさせるのを防ぐ。輻輳制御はネットワークを保護するもので、送信者全体がルーターやリンクを圧倒するのを防ぐ。TCPは両方を行い、フロー制御には受信ウィンドウを、輻輳制御には輻輳ウィンドウを使用する。

パケット損失が発生するとTCPの速度が低下するのはなぜですか？

損失は、ネットワークが輻輳していることを示すTCPの主要な信号である。損失が発生した際に送信レートを大幅に減らし、それ以外の場合には徐々にしか増加させないことで、TCPはネットワークが過負荷のときに後退し、そうでないときに余剰容量をプローブする。これにより、総トラフィックは容量近くに保たれ、帯域幅はほぼ公平に共有される。