ランダム早期検出

ランダム早期検出（RED ）は、ランダム早期破棄またはランダム早期ドロップとも呼ばれ、輻輳回避に適したネットワークスケジューラのキューイング規則です。^[1]

従来のテールドロップアルゴリズムでは、ルーターまたはその他のネットワークコンポーネントは、できる限り多くのパケットをバッファリングし、バッファリングできないパケットは単にドロップします。バッファが常にいっぱいになると、ネットワークは輻輳します。テールドロップは、トラフィックフロー間でバッファスペースを不公平に分配します。テールドロップは、すべてのTCP接続が同時に「保留」され、その後同時に前進するため、 TCP グローバル同期を引き起こす可能性もあります。ネットワークは、波のように、十分に活用されずにあふれてしまいます。

REDはバッファが完全にいっぱいになる前にパケットを事前にドロップすることでこれらの問題に対処します。REDは予測モデルを使用してドロップするパケットを決定します。REDは1990年代初頭にサリー・フロイドとヴァン・ジェイコブソンによって発明されました。^[2]

手術

RED は平均キューサイズを監視し、統計的な確率に基づいてパケットをドロップします ( ECNと組み合わせて使用する場合はマークします) 。バッファがほぼ空の場合、すべての着信パケットが受け入れられます。キューが大きくなるにつれて、着信パケットをドロップする確率も大きくなります。バッファがいっぱいになると、確率は 1 に達し、すべての着信パケットがドロップされます。

RED は、帯域幅のごく一部しか使用しないバーストトラフィックに対して偏りがないという意味で、テールドロップよりも公平です。ホストのパケットがドロップされる可能性はキュー内のデータ量に比例するため、ホストの送信量が多いほど、パケットがドロップされる可能性が高くなります。早期検出により、TCP グローバル同期を回避できます。

クラシックREDの問題

Van Jacobson によれば、「クラシック RED には 1 つではなく 2 つのバグがある」とのことです。^[3]アルゴリズムの改良が開発され、草稿^[4]も準備されましたが、論文は公開されず、改良は広く普及も実装もされませんでした。研究を終わらせ、バグを修正するための作業がいくつか行われてきました。^[3]

純粋なREDはサービス品質（QoS）の差別化には対応していません。重み付けRED（WRED）とRED with In and Out（RIO）^[5]は、 QoSを考慮した早期検出を提供します。

その他のバリエーション

ワードレッド

重み付けREDでは、異なる優先度（ IP優先順位、DSCP）やキューごとに異なる確率を設定できます。 ^[6]

アレッド

適応型REDまたはアクティブRED（ARED）アルゴリズム^[7]は、平均キュー長の観測に基づいて、REDをより積極的にするか、より緩やかにするかを推測します。平均キュー長が最小しきい値付近で振動する場合、早期検出は積極的すぎます。一方、平均キュー長が最大しきい値付近で振動する場合、早期検出は保守的すぎます。アルゴリズムは、トラフィックが破棄されていることを感知する積極性に応じて確率を変更します。

これらの技術とその分析の詳細については Srikant ^{[8]を参照してください。}

レッド

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

参照

参考文献

^ Floyd, Sally; Jacobson, Van (1993 年 8 月)。「輻輳回避のための Random Early Detection (RED) ゲートウェイ」。IEEE /ACM Transactions on Networking。1 ( 4): 397–413。CiteSeerX 10.1.1.147.3833。doi : 10.1109/90.251892。S2CID 221977646。2008年3月16 日閲覧。
^ ハフナー、ケイティ（2019年9月4日）。「オンラインで物事がスムーズに進むよう支援したサリー・フロイドが69歳で死去」ニューヨーク・タイムズ。
^ ab Gettys, Jim (2010-12-17). 「RED in a Different Light」jg's Ramblings . 2010-12-27閲覧。
^ ジェイコブソン、ヴァン; ニコルズ、キャシー; ポドゥリ、ケダール (1999-09-30). 「RED in a Different Light」. CiteSeerX 10.1.1.22.9406 . {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
^ Clark, David D.; Wroclawski, John (1997 年 7 月)。「インターネットにおけるサービス割り当てへのアプローチ」。IETF データトラッカー。IETF。p. 12。2011年 5月 27 日閲覧。
^ Chao, H. Jonathan (2002). 「Frontmatter and Index」.高速ネットワークにおけるサービス品質制御. ニューヨーク: John Wiley & Sons Inc. pp. i–xvi. doi :10.1002/0471224391.fmatter_indsub. ISBN 978-0-471-00397-7。
^ Floyd, Sally; Gummadi, Ramakrishna; Shenker, Scott (2001-08-01). 「Adaptive RED: RED のアクティブキュー管理の堅牢性を高めるアルゴリズム」。2008-03-16に取得。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
^ スリカント、ラヤドゥルガム (2004)。インターネット輻輳制御の数学。米国マサチューセッツ州ボストン: ビルクホイザー。ISBN 978-0-8176-3227-4。
^ ab Zhang, Changwang; Yin, Jianping; Cai, Zhiping; Chen, Weifeng (2010 年 5 月 1 日)。「RRED: 低レートのサービス拒否攻撃に対抗する堅牢な RED アルゴリズム」IEEE Communications Letters . 14 (5): 489–491. doi :10.1109/LCOMM.2010.05.091407. S2CID 1121461。

外部リンク

RED (ランダム早期検出) キュー管理。著者: サリー・フロイド
Guduz – シンプルなランダム早期検出 (RED) シミュレーター
RED のバリエーション 2017-07-20 にWayback Machineにアーカイブされました。著者: Hei Xiao Jun
ランダム早期検出（RED）スキームに関する最近の出版物 2016-09-17 にWayback Machineでアーカイブ

[1] Floyd, Sally; Jacobson, Van (1993 年 8 月)。「輻輳回避のための Random Early Detection (RED) ゲートウェイ」。IEEE /ACM Transactions on Networking。1 ( 4): 397–413。CiteSeerX 10.1.1.147.3833。doi : 10.1109/90.251892。S2CID 221977646。2008年3月16 日閲覧。

[2] ハフナー、ケイティ（2019年9月4日）。「オンラインで物事がスムーズに進むよう支援したサリー・フロイドが69歳で死去」ニューヨーク・タイムズ。

[jgred-3] Gettys, Jim (2010-12-17). 「RED in a Different Light」jg's Ramblings . 2010-12-27閲覧。

[4] ジェイコブソン、ヴァン; ニコルズ、キャシー; ポドゥリ、ケダール (1999-09-30). 「RED in a Different Light」. CiteSeerX 10.1.1.22.9406 . {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です

[5] Clark, David D.; Wroclawski, John (1997 年 7 月)。「インターネットにおけるサービス割り当てへのアプローチ」。IETF データトラッカー。IETF。p. 12。2011年 5月 27 日閲覧。

[6] Chao, H. Jonathan (2002). 「Frontmatter and Index」.高速ネットワークにおけるサービス品質制御. ニューヨーク: John Wiley & Sons Inc. pp. i–xvi. doi :10.1002/0471224391.fmatter_indsub. ISBN 978-0-471-00397-7。

[7] Floyd, Sally; Gummadi, Ramakrishna; Shenker, Scott (2001-08-01). 「Adaptive RED: RED のアクティブキュー管理の堅牢性を高めるアルゴリズム」。2008-03-16に取得。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です

[8] スリカント、ラヤドゥルガム (2004)。インターネット輻輳制御の数学。米国マサチューセッツ州ボストン: ビルクホイザー。ISBN 978-0-8176-3227-4。

[RRED-9] Zhang, Changwang; Yin, Jianping; Cai, Zhiping; Chen, Weifeng (2010 年 5 月 1 日)。「RRED: 低レートのサービス拒否攻撃に対抗する堅牢な RED アルゴリズム」IEEE Communications Letters . 14 (5): 489–491. doi :10.1109/LCOMM.2010.05.091407. S2CID 1121461。