ネットワークの混雑

データネットワーキングとキューイング理論におけるネットワーク輻輳とは、ネットワークノードまたはリンクが処理できる以上のデータを運んでいるときに発生するサービス品質の低下です。典型的な影響には、キューイング遅延、パケット損失、または新しい接続のブロックが含まれます。輻輳の結果、提供される負荷の増分は、ネットワークスループットのわずかな増加または減少につながります。^[1]

輻輳によるパケット損失を補うために積極的な再送信を使用するネットワーク プロトコルは、初期負荷が通常はネットワーク輻輳を引き起こさないレベルまで低下した後でも、輻輳を増大させる可能性があります。このようなネットワークは、同じレベルの負荷で 2 つの安定状態を示します。スループットが低い安定状態は、輻輳崩壊と呼ばれます。

ネットワークは、輻輳制御と輻輳回避の技術を使用して、崩壊を回避しようとします。これには、802.11のCSMA/CAやオリジナルのEthernetの同様のCSMA/CD などのプロトコルの指数バックオフ、TCPのウィンドウ縮小、ルーターやネットワーク スイッチなどのデバイスの公平なキューイングが含まれます。輻輳に対処するその他の技術には、一部のパケットを他のパケットよりも優先して送信する優先順位スキームや、アドミッション制御を使用して特定のフローにネットワーク リソースを明示的に割り当てる方法などがあります。

ルーターの処理時間やリンクのスループットなど、ネットワーク リソースには限りがあります。ネットワーク上でリソースの競合が発生する一般的な状況はいくつかあります。ワイヤレス LAN は、1 台のパソコンで簡単にいっぱいになります。^[2]高速なコンピュータ ネットワークでも、バックボーンは数台のサーバーとクライアント PC で簡単に混雑します。ボットネットによるサービス拒否攻撃は、最大のインターネット バックボーンネットワーク リンクでもいっぱいにすることができ、大規模なネットワーク混雑を引き起こします。電話ネットワークでは、大量の呼び出しイベントによってデジタル電話回線が圧倒される可能性があり、これはサービス拒否攻撃として定義できます。

輻輳崩壊 (または輻輳崩壊) とは、輻輳によって有用な通信が妨げられたり制限されたりする状態です。輻輳崩壊は一般に、ネットワークのチョーク ポイントで発生します。このチョーク ポイントでは、着信トラフィックが発信帯域幅を超えます。ローカル エリア ネットワークとワイド エリア ネットワーク間の接続ポイントは、一般的なチョーク ポイントです。ネットワークがこの状態になると、トラフィック需要は高いものの、有用なスループットはほとんど利用できない安定した状態になり、その間にパケットの遅延や損失が発生し、サービス品質が極端に低下します。

輻輳崩壊は、1984年までに起こりうる問題として特定されました。^[3]これは、1986年10月に初期のインターネットで初めて観測されました。^[4] NSFNETフェーズIバックボーンの容量が32 kbit/sから3桁低下して40 bit/sになったときです。 ^[5]この状態は、エンドノードが1987年から1988年の間にVan JacobsonとSally Floydの輻輳制御を実装し始めるまで続きました。^{[6]中間ルーターで処理できる以上の}パケットが送信された場合、中間ルーターは、ネットワークのエンドポイントが情報を再送信することを期待して、多くのパケットを破棄しました。しかし、初期のTCP実装では再送信の動作が不十分でした。このパケット損失が発生すると、エンドポイントは失われた情報を繰り返す余分なパケットを送信し、受信レートを2倍にしました。

輻輳制御は、通信ネットワークへのトラフィックの流入を調整し、オーバーサブスクリプションによる輻輳の崩壊を回避します。^{[7]これは通常、パケットのレートを下げることによって実現されます。輻輳制御は送信者が}ネットワークに過負荷をかけるのを防ぎますが、フロー制御は送信者が受信者に過負荷をかけるのを防ぎます。

輻輳制御の理論は、ミクロ経済理論と凸最適化理論を応用して、各自のレートを制御する個人が相互作用して、ネットワーク全体で最適なレート割り当てを達成する方法を示したFrank Kellyによって開拓されました。最適なレート割り当ての例としては、最大最小公平割り当てや Kelly の提案した比例公平割り当てなどがありますが、他にも多くの割り当てが可能です。

をフローの速度、をリンクの容量、をフローがリンクを使用する場合は 1 、それ以外の場合は 0 とします。、、をそれぞれ対応するベクトルと行列とします。を、ユーザーが速度 で送信することでどれだけの利益が得られるかを測定する、増加する厳密に凹の関数(効用 )とします。最適な速度割り当ては次式を満たします。 ${\displaystyle x_{i}}$${\displaystyle i}$${\displaystyle c_{l}}$${\displaystyle l}$${\displaystyle r_{li}}$${\displaystyle i}$${\displaystyle l}$${\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}$

輻輳制御アルゴリズムを分類する方法には以下のものがあります。

• ネットワークから受信したフィードバックの種類と量: 損失、遅延、単一ビットまたは複数ビットの明示的な信号
• 増分展開可能性により、送信者のみ変更が必要、送信者と受信者の変更が必要、ルーターのみ変更が必要、送信者、受信者、およびルーターの変更が必要。
• パフォーマンスの側面: 高帯域幅遅延積ネットワーク、損失リンク、公平性、短いフローの利点、可変レートリンク
• 公平性の基準: 最大最小公平性、比例公平性、遅延制御

ネットワークの輻輳を防止したり、ネットワークの崩壊に対処したりするためのメカニズムが発明されてきました。

• ネットワーク スケジューラ – 輻輳が発生した場合にネットワーク パケットを並べ替えたり選択的にドロップしたりするアクティブ キュー管理
• 明示的輻輳通知 – フロー制御メカニズムを追加するIPおよびTCP通信プロトコルの拡張機能
• TCP輻輳制御 – ネットワーク輻輳に対処するためのさまざまな実装

エンドポイントの正しい動作は、通常、ドロップされた情報を繰り返すことですが、繰り返し速度を徐々に遅くします。すべてのエンドポイントがこれを行うと、輻輳が解消され、ネットワークは通常の動作を再開します。^{[引用が必要]}スロー スタートなどの他の戦略により、輻輳検出が開始される前に、新しい接続がルーターを圧倒しないようにします。

一般的なルーターの輻輳回避メカニズムには、公平なキューイングやその他のスケジューリング アルゴリズム、および輻輳が検出されるとパケットがランダムにドロップされるランダム早期検出(RED) が含まれます。これにより、輻輳の崩壊が発生する前にエンドポイントの送信速度が遅くなるようにプロアクティブにトリガーされます。

いくつかのエンドツーエンドプロトコルは、輻輳状態でも適切に動作するように設計されており、TCP はよく知られた例です。輻輳を処理する最初の TCP 実装は 1984 年に説明されましたが、^{[8] Van Jacobson が 1988 年に Berkeley Standard Distribution UNIX (} BSD )にオープンソースソリューションを組み込んだときに初めて良好な動作が提供されました。

UDP は輻輳を制御しません。UDP 上に構築されたプロトコルは、輻輳を独立して処理する必要があります。輻輳に関係なく固定速度で送信するプロトコルは、問題を引き起こす可能性があります。多くのVoice over IPプロトコルを含むリアルタイム ストリーミング プロトコルには、この特性があります。したがって、輻輳が発生した場合にパケットがドロップされないようにするには、サービス品質などの特別な対策を講じる必要があります。

広く使用されているTCPプロトコルなどのコネクション指向プロトコルは、パケット損失やキューイング遅延を監視して伝送速度を調整します。さまざまなネットワーク輻輳回避プロセスがさまざまなトレードオフをサポートしています。^[9]

TCP輻輳回避アルゴリズムは、インターネット上の輻輳制御の基本的な基礎である。^{[10] [11] [12] [13] [14]}

同時 TCP フローでテールドロップが発生すると、特にバッファブロートが存在する場合に問題が発生します。この遅延パケット損失は、TCP の自動輻輳回避を妨げます。このパケット損失が発生するすべてのフローは、同時に TCP 再トレーニングを開始します。これをTCP グローバル同期と呼びます。

アクティブ キュー管理(AQM) は、ネットワーク インターフェイス コントローラ(NIC)に関連付けられた送信バッファ内でネットワーク パケットの順序を変更したりドロップしたりすることです。このタスクは、ネットワーク スケジューラによって実行されます。

解決策の1つは、ネットワーク機器の出力キューでランダム早期検出（RED）を使用することです。 ^{[15] [16]}複数の出力キューを持つネットワークハードウェアポートでは、重み付けランダム早期検出（WRED）を使用できます。

REDは、例えば平均キューの長さが閾値（例えば50%）を超えたときに一部のパケットをドロップすることでTCPの送信者と受信者に間接的に信号を送り、キューがさらにいっぱいになるにつれて、例えば100%まで 線形または3乗的にパケットを削除します^{[17] 。}

堅牢なランダム早期検出（RRED）アルゴリズムは、サービス拒否（DoS）攻撃、特に低レートのサービス拒否（LDoS）攻撃に対するTCPスループットを向上させるために提案されました。実験により、攻撃によって引き起こされるTCPキューサイズの変動により、REDのようなアルゴリズムはLDoS攻撃に対して脆弱であることが確認されました。^[18]

一部のネットワーク機器には、各フローを追跡して測定できるポートが装備されており、これにより、サービス品質ポリシーに従って帯域幅が大きすぎるフローを通知することができます。ポリシーは、いくつかの基準に従ってすべてのフロー間で帯域幅を分割することができます。^[19]

もう一つのアプローチは、明示的輻輳通知（ECN）を使用することです。 ^[20] ECNは、2つのホストがそれを使用することを通知した場合にのみ使用されます。この方法では、プロトコルビットを使用して明示的な輻輳を通知します。これは、RED/WREDアルゴリズムによるパケット損失によって通知される間接的な輻輳通知よりも優れていますが、両方のホストによるサポートが必要です。^{[21] [15]}

ルータは、ECN 対応としてマークされたパケットを受信し、輻輳を予測すると、ECN フラグを設定して送信者に輻輳を通知します。送信者は、TCP ウィンドウ サイズを縮小するなどして送信速度を下げるなど、伝送帯域幅を減らすことで応答する必要があります。

輻輳回避は、トラフィックを減らすことで効率的に達成できます。アプリケーションが大きなファイル、グラフィック、または Web ページを要求する場合、通常は32K から 64K のウィンドウをアドバタイズします。これにより、サーバーは完全なウィンドウのデータを送信します (ファイルがウィンドウより大きいと仮定)。多くのアプリケーションが同時にダウンロードを要求すると、このデータによって上流プロバイダーで輻輳ポイントが発生する可能性があります。ウィンドウのアドバタイズを減らすことで、リモート サーバーが送信するデータが少なくなり、輻輳が軽減されます。^{[22] [23]}

バックワードECN（BECN）は、提案されている別の輻輳通知メカニズムです。これは、 IPシグナリングメカニズムとしてICMPソースクエンチメッセージを使用して、IPネットワークの基本的なECNメカニズムを実装し、輻輳通知をIPレベルに保ち、ネットワークエンドポイント間のネゴシエーションを必要としません。効果的な輻輳通知は、適切な調整のためにTCPやUDPなどのトランスポート層プロトコルに伝播できます。^[24]

輻輳による崩壊を回避するプロトコルは、一般的に、データ損失は輻輳によって引き起こされると想定しています。有線ネットワークでは、送信中にエラーが発生することはまれです。WiFi 、 3G 、および無線層を備えたその他のネットワークは、干渉によるデータ損失の影響を受けやすく、場合によってはスループットが低下することがあります。無線ベースの物理層で実行される TCP 接続は、データ損失を認識し、輻輳が発生していると誤って認識する傾向があります。

スロースタート プロトコルは、短い接続ではパフォーマンスが低下します。古いWeb ブラウザは、多数の短命な接続を作成し、ファイルごとに接続を開いたり閉じたりしていました。そのため、ほとんどの接続がスロースタート モードのままでした。初期のパフォーマンスは低下する可能性があり、多くの接続がスロースタート モードから抜け出せず、遅延が大幅に増加します。この問題を回避するために、最新のブラウザは、複数の接続を同時に開くか、特定のサーバーから要求されたすべてのファイルに対して1 つの接続を再利用します。

アドミッション コントロールとは、新しいネットワーク接続を確立する前にデバイスが許可を得ることを要求するシステムです。新しい接続によって輻輳が発生する恐れがある場合、許可を拒否できます。例としては、従来の配線によるホーム ネットワーキング用のITU-T G.hn標準の Contention-Free Transmission Opportunities (CFTXOP)、IP ネットワークのリソース予約プロトコル、イーサネットのストリーム予約プロトコルなどがあります。

• 帯域幅管理 – 通信ネットワークの容量制御
• 連鎖的な失敗 – 失敗の体系的なリスク
• チョーク交換機 – 多数の同時通話を処理できるように設計された電話交換機
• アーラン（単位）  – 通信における負荷測定
• 魔法使いの弟子症候群 - TFTP のオリジナル バージョンにおけるネットワーク プロトコルの欠陥
• 通信トラフィック工学 – 通信トラフィック工学理論の応用
• スラッシング – メモリとストレージ間の継続的な交換
• トラフィックシェーピング – 通信帯域幅管理技術
• 信頼性（コンピュータネットワーク）  - プロトコル確認機能

• Floyd, S. および K. Fall、「インターネットにおけるエンドツーエンドの輻輳制御の使用促進」 (IEEE/ACM Transactions on Networking、1999 年 8 月)
• サリー・フロイド、「インターネットにおけるエンドツーエンドの輻輳制御の進化について：特異な視点」（通信ネットワークにおけるスケーリング現象に関する IMA ワークショップ、1999 年 10 月）（pdf形式）
• Linktionary 用語: キューイング 2003-03-08 にWayback Machineでアーカイブ
• Pierre-Francois Quet、Sriram Chellappan、Arjan Durresi、Mukundan Sridharan、Hitay Ozbay、Raj Jain、「流体フローベースの TCP モデルを使用したマルチレベル ECN の最適化ガイドライン」
• サリー・フロイド、ラトゥル・マハジャン、デイヴィッド・ウェザロール: RED-PD: 優先ドロップ付き RED 2003-04-02ウェイバックマシンにアーカイブ
• Mehmet Suzen による教育目的の汎用シンプル RED シミュレーター
• パケットネットワークにおける輻輳制御へのアプローチ
• 輻輳制御に関する論文
• ランダム早期検出ホームページ
• 明示的輻輳通知ホームページ
• TFRCホームページ
• AIMD-FCホームページ
• 低レートのサービス拒否 (DoS) 攻撃に関する最近の出版物