Loading article…
コンピュータネットワークと待ち行列理論におけるネットワーク輻輳とは、ネットワークノードまたはリンクがその容量を超える負荷を処理または伝送しているときに発生するサービス品質の低下のことです。典型的な影響としては、待ち行列遅延、パケット損失、新規接続のブロックなどが挙げられます。輻輳の結果、提供される負荷が段階的に増加しても、ネットワークスループットはわずかに増加するか、あるいは減少することさえあります。[ 1 ]
輻輳によるパケット損失を補償するために積極的な再送信を行うネットワークプロトコルは、初期負荷が通常であればネットワーク輻輳を引き起こさないレベルまで低下した後でも、輻輳を悪化させる可能性があります。このようなネットワークは、同じ負荷レベルでも2つの安定状態を示します。スループットが低い安定状態は、輻輳崩壊として知られています。
ネットワークは、輻輳制御と輻輳回避の技術を用いて、ネットワークの崩壊を防ごうとします。これには、 TCPにおけるウィンドウ縮小や、ルーターやネットワークスイッチなどの機器における公平なキューイングなどが含まれます。輻輳に対処するその他の技術としては、優先度の高いパケットを他のパケットよりも優先して送信する優先度スキームや、アドミッションコントロールを用いて特定のフローにネットワークリソースを明示的に割り当てる方法などがあります。
ネットワークのリソースには、ルーターの処理時間やリンクのスループットなど、制限があります。リソースの競合は、いくつかの一般的な状況でネットワーク上で発生する可能性があります。無線LANは、1台のパーソナルコンピュータで簡単に満杯になります。[ 2 ]高速コンピュータネットワークであっても、バックボーンは少数のサーバーとクライアントPCで簡単に混雑する可能性があります。ボットネットによるサービス拒否攻撃は、最大のインターネットバックボーンネットワークリンクでさえ満杯にし、大規模なネットワーク混雑を引き起こす可能性があります。電話ネットワークでは、大量通話イベントによりデジタル電話回線が過負荷になり、これはサービス拒否攻撃と定義できます。
輻輳崩壊（または輻輳崩壊）とは、輻輳によって有用な通信が妨げられたり制限されたりする状態のことです。輻輳崩壊は一般的に、ネットワークのボトルネック、つまり受信トラフィックが送信帯域幅を超える箇所で発生します。ローカルエリアネットワークとワイドエリアネットワーク間の接続点は、よく見られるボトルネックです。ネットワークがこの状態になると、トラフィック需要は高いものの、有用なスループットはほとんど得られない安定状態に陥り、パケットの遅延や損失が発生し、サービス品質は極めて低下します。
輻輳崩壊は、1984 年までに起こりうる問題として認識されていました。[ 3 ]最初に観測されたのは、1986 年 10 月の初期のインターネットで、[ 4 ] NSFNET フェーズ I バックボーンの容量が 32 kbit/s から 40 bit/sに3 桁も低下した時でした。 [ 5 ]この状態は、エンド ノードが 1987 年と 1988 年の間にVan JacobsonとSally Floydの輻輳制御を実装し始めるまで続きました。 [ 6 ]中間ルーターで処理できる以上のパケットが送信されると、中間ルーターは多くのパケットを破棄し、ネットワークのエンドポイントが情報を再送信することを期待しました。しかし、初期の TCP 実装では再送信動作が不十分でした。このパケット損失が発生すると、エンドポイントは失われた情報を繰り返す余分なパケットを送信し、受信レートが 2 倍になりました。
輻輳制御は、過剰加入による輻輳崩壊を回避するために、通信ネットワークへのトラフィックの流入を調整します。[ 7 ]これは通常、パケットのレートを下げることによって実現されます。輻輳制御は送信者がネットワークを圧倒するのを防ぐのに対し、フロー制御は送信者が受信者を圧倒するのを防ぎます。
混雑制御理論はフランク・ケリーによって開拓され、彼はミクロ経済学と凸最適化理論を応用して、各個人が自身の料金を制御することで、ネットワーク全体で最適な料金配分を実現する方法を記述した。最適な料金配分の例としては、最大最小公平配分やケリーが提案した比例公平配分などがあるが、他にも多くの方法が存在する。
させて流量、リンクの容量、 そして流れが1の場合は1になるリンクを使用するそれ以外の場合は0とする。、そして対応するベクトルと行列をそれぞれとする。は増加関数であり、厳密に凹関数である。これは効用と呼ばれ、ユーザーがレートで送信することによってどれだけの利益を得るかを測定する。最適なレート配分は以下を満たす。
この問題のラグランジュ双対では、各フローがネットワークによって示される価格のみに基づいて独自のレートを設定するように分離されます。各リンク容量は制約を課し、ラグランジュ乗数を生み出します。これらの乗数の合計は、これは、フローが反応する価格です。
すると、輻輳制御は分散最適化アルゴリズムとなる。現在の多くの輻輳制御アルゴリズムはこのフレームワークでモデル化でき、リンクにおける損失確率または待ち行列遅延のいずれか大きな弱点は、すべてのフローに同じ価格を割り当てる点です。一方、スライディングウィンドウフロー制御はバースト性を引き起こし、特定のリンクにおいて異なるフローが異なる損失や遅延を観測することになります。
輻輳制御アルゴリズムを分類する方法には、以下のようなものがある。
ネットワークの混雑を防ぐため、あるいはネットワークの崩壊に対処するために、様々な仕組みが考案されてきた。
エンドポイントの正しい動作は通常、ドロップされた情報を繰り返すことですが、繰り返しレートを徐々に遅くします。すべてのエンドポイントがこれを実行すると、輻輳が解消され、ネットワークは正常な動作に戻ります。[ 5 ]スロースタートなどの他の戦略では、輻輳検出が開始される前に新しい接続がルータを過負荷にしないようにします。
一般的なルーターの輻輳回避メカニズムには、公平なキューイングやその他のスケジューリングアルゴリズム、および輻輳が検出された際にパケットをランダムに破棄するランダム早期検出などがあります。これにより、輻輳が崩壊する前にエンドポイントが送信速度を落とすように事前に促されます。
エンドツーエンドプロトコルの中には、輻輳状態でも適切に動作するように設計されているものがあります。TCPはその代表的な例です。輻輳を処理する最初のTCP実装は1984年に記述されましたが[ 8 ] 、1988年にVan JacobsonがオープンソースソリューションをBerkeley Standard Distribution UNIX（「 BSD 」）に組み込んだことで、初めて良好な動作が実現しました。
UDPは輻輳制御を行いません。UDP上に構築されたプロトコルは、輻輳を独自に処理する必要があります。輻輳に関係なく一定の速度で送信するプロトコルは問題となる可能性があります。多くのVoIPプロトコルを含むリアルタイムストリーミングプロトコルは、この特性を持っています。したがって、輻輳が発生してもパケットがドロップされないように、QoS（サービス品質）などの特別な対策を講じる必要があります。
広く使用されているTCPプロトコルなどのコネクション指向プロトコルは、パケット損失やキューイング遅延を監視して送信レートを調整します。さまざまなネットワーク輻輳回避プロセスは、異なるトレードオフをサポートしています。[ 9 ]
TCP輻輳回避アルゴリズムは、インターネット上の輻輳制御の主要な基盤である。[ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ]
同時実行されるTCPフローでテールドロップが発生すると、特にバッファブロートが発生している場合に問題が発生します。この遅延パケット損失は、TCPの自動輻輳回避機能を妨げます。このパケット損失が発生したすべてのフローは、同時にTCPの再トレーニングを開始します。これはTCPグローバル同期と呼ばれます。
アクティブキュー管理（AQM）とは、ネットワークインターフェイスコントローラ（NIC）に関連付けられた送信バッファ内のネットワークパケットの順序変更や破棄のことです。このタスクはネットワークスケジューラによって実行されます。
一つの解決策は、ネットワーク機器の出力キューでランダム早期検出（RED）を使用することです。 [ 15 ] [ 16 ]複数の出力キューを持つネットワークハードウェアポートでは、重み付きランダム早期検出（WRED）を使用できます。
REDは、平均キュー長がしきい値（例えば50%）を超えた場合などにパケットを破棄することでTCP送信者と受信者に間接的に通知し、キューがさらに満たされるにつれて、より多くのパケットを線形または3乗的に削除します[ 17 ]。最大で100%まで削除します。
堅牢なランダム早期検出（RRED）アルゴリズムは、サービス拒否（DoS）攻撃、特に低レートのサービス拒否（LDoS）攻撃に対するTCPスループットを向上させるために提案されました。実験により、REDのようなアルゴリズムは、攻撃によって引き起こされるTCPキューサイズの変動により、LDoS攻撃に対して脆弱であることが確認されました。[ 18 ]
ネットワーク機器の中には、各フローを追跡および測定できるポートを備えており、それによってサービス品質ポリシーに従って帯域幅が大きすぎるフローを通知することができます。ポリシーは、何らかの基準に基づいてすべてのフロー間で帯域幅を分割することができます。[ 19 ]
別のアプローチとして、明示的輻輳通知(ECN)を使用する方法があります。[ 20 ] ECN は、2 つのホストが使用したいと通知した場合にのみ使用されます。この方法では、プロトコル ビットを使用して明示的な輻輳を通知します。これは、RED/WRED アルゴリズムによるパケット損失によって通知される間接的な輻輳通知よりも優れていますが、両方のホストによるサポートが必要です。[ 21 ] [ 15 ]
ルータがECN対応としてマークされたパケットを受信し、輻輳を予測した場合、ECNフラグを設定して送信元に輻輳を通知します。送信元は、TCPウィンドウサイズを小さくするなどして送信レートを下げるなど、送信帯域幅を縮小することで対応する必要があります。
L4SプロトコルはECNの拡張版であり、送信者がネットワークデバイスと連携して輻輳を制御できるようにするものである。[ 22 ]
トラフィックを削減することで、輻輳を効率的に回避できます。アプリケーションが大きなファイル、グラフィック、またはウェブページを要求すると、通常は32K ～ 64K のウィンドウを通知します。これにより、サーバーはウィンドウいっぱいのデータを送信します (ファイルがウィンドウより大きい場合)。多くのアプリケーションが同時にダウンロードを要求すると、このデータによって上流のプロバイダで輻輳ポイントが発生する可能性があります。ウィンドウ通知を減らすことで、リモート サーバーが送信するデータが少なくなり、輻輳が軽減されます。[ 23 ] [ 24 ]
後方ECN（BECN）は、提案されている別の輻輳通知メカニズムです。IPシグナリングメカニズムとしてICMPソースクエンチメッセージを使用して、IPネットワークの基本的なECNメカニズムを実装し、輻輳通知をIPレベルにとどめ、ネットワークエンドポイント間のネゴシエーションを必要としません。効果的な輻輳通知は、適切な調整のためにTCPやUDPなどのトランスポート層プロトコルに伝播できます。[ 25 ]
輻輳崩壊を回避するプロトコルは、一般的にデータ損失は輻輳によって引き起こされると想定しています。有線ネットワークでは、伝送中のエラーはまれです。Wi -Fi、3G 、その他の無線層を持つネットワークは、干渉によるデータ損失の影響を受けやすく、場合によってはスループットが低下することがあります。無線ベースの物理層上で動作するTCP接続はデータ損失を検知し、輻輳が発生していると誤って判断する傾向があります。
スロースタートプロトコルは、短い接続ではパフォーマンスが低下します。古いWebブラウザは、多数の短命な接続を作成し、ファイルごとに接続を開閉していました。そのため、ほとんどの接続がスロースタートモードのままになっていました。初期パフォーマンスは低く、多くの接続はスロースタート状態から抜け出せず、レイテンシが大幅に増加していました。この問題を回避するため、最新のブラウザは複数の接続を同時に開くか、特定のサーバーから要求されたすべてのファイルに対して1つの接続を再利用します。
アドミッションコントロールとは、デバイスが新しいネットワーク接続を確立する前に許可を得ることを要求するシステムのことです。新しい接続によって輻輳が発生する恐れがある場合、許可は拒否されます。例としては、従来の配線を使用したホームネットワーク向けのITU-T G.hn規格における競合フリー伝送機会（CFTXOP）、 IPネットワーク向けのリソース予約プロトコル、イーサネット向けのストリーム予約プロトコルなどがあります。
86 年 10 月、インターネットは一連の「輻輳崩壊」の最初のものとなった。この期間中、LBL から UC Berkeley (400 ヤード離れ、 2 つの IMP ホップ) へのデータスループットは 32 Kbps から 40 bps に低下した。帯域幅が突然 1000 分の 1 に低下したことに私たちは興味を持ち、なぜ事態がこれほど悪化したのかの調査に着手した。特に、4.3BSD (Berkeley UNIX) TCP が誤動作しているのか、それとも劣悪なネットワーク条件下でより良く動作するように調整できるのか疑問に思った。これらの質問に対する答えはどちらも「はい」だった。
...この関数の利点は、大きな振動を回避するだけでなく、低負荷時のリンク利用率の低下も回避できる点にあります。導出された関数の適用範囲は負荷範囲に依存せず、パラメータを調整する必要はありません。元の線形ドロップ関数と比較すると、適用範囲ははるかに広くなっています...現実的なシステムパラメータを用いた例では、キューサイズの3乗の近似関数が得られます...
