(57)【特許請求の範囲】
【請求項１】
通信ネットワークでパケットバッファを操作する方法であって、パケットバッファがパケットの複数のフローを受け入れるように動作可能である方法において、
所定期間のドロップタイマーを提供するステップであって、前記所定期間の期限切れは、前記パケットバッファの瞬間的なキューの長さ（ＩＱＬ）値および平均的なキューの長さ（ＡＱＬ）値の標本化をトリガーする、提供するステップと、
前記ＩＱＬ値が前記パケットバッファの最小キューしきい値より大きく、かつ前記ＡＱＬ値が前記パケットバッファのゲートキューしきい値より大きい場合に、前記パケットバッファに次の着信パケットをマークするステップと、
前記ＩＱＬ値が前記パケットバッファの前記最小キューしきい値未満であるか、または前記ＡＱＬ値が前記パケットバッファの前記ゲートキューしきい値未満である場合、前記所定期間の次の期限切れまで、次の着信パケットおよび後続するパケットをマークしないステップと
を含む、方法。
【請求項２】
マークされている着信パケットが前記パケットバッファに入れられることなく直ちにドロップされ、マークされていない着信パケットが前記パケットバッファに入れられるのに適格であるとみなされる、請求項１に記載の方法。
【請求項３】
マークされている着信パケットが、着信パケットの内部フィールドの１つまたは複数で変更され、前記パケットバッファに入れられるのに適格であるとみなされる、請求項１に記載の方法。
【請求項４】
前記ドロップタイマーの前記所定期間が可変であり、所与の修正間隔で調整される、請求項１に記載の方法。
【請求項５】
前記ドロップタイマーの前記所定期間を調整するための前記所与の修正間隔が、固定された期間である、請求項４に記載の方法。
【請求項６】
前記所与の修正間隔のうちの現在の１つの期限が切れている場合、前記ＡＱＬ値が前記最小キューしきい値と最大キューしきい値との間にあれば、前記ドロップタイマーの前記所定期間が変更されず、
前記所与の修正間隔のうちの現在の１つの期限が切れている場合、前記ＡＱＬ値が前記パケットバッファの前記最小キューしきい値未満なら、前記ドロップタイマーの前記所定期間が増加し、
前記所与の修正間隔のうちの現在の１つの期限が切れている場合、前記ＡＱＬ値が前記パケットバッファの前記最大キューしきい値より大きければ、前記ドロップタイマーの前記所定期間が減少する、
請求項４に記載の方法。
【請求項７】
前記パケットバッファの安全キューしきい値をさらに含み、前記ＡＱＬ値が前記安全キューしきい値を超えている場合、前記所与の修正間隔のうちの現在の１つが期限切れする前に、前記ドロップタイマーの前記所定期間の緊急修正を行うことができる、請求項４に記載の方法。
【請求項８】
前記ＡＱＬ値の、前記パケットバッファの前記最小キューしきい値に対する比率が小さくなるほど、前記ドロップタイマーの前記所定期間の増加が大きくなり、
前記ＡＱＬ値の、前記最大キューしきい値に対する比率が大きくなるほど、前記ドロップタイマーの前記所定期間の減少が大きくなる、
請求項６に記載の方法。
【請求項９】
前記ＡＱＬおよびＩＱＬの値が、サブパケットのデータ単位で測定され、マーキングアクションが、１つの次の着信パケットまたは複数の次の着信パケットに含まれていている可能性がある所定量の前記サブパケットデータの単位に適用される、
請求項１に記載の方法。
【請求項１０】
メモリを持つ通信デバイスであって、前記メモリが複数の命令をそこに格納し、前記デバイスがパケットバッファをさらに含み、パケットバッファがパケットの複数のフローを受け入れるように動作可能であり、複数の命令がプロセッサによって実行されると、前記プロセッサに、
ドロップタイマーの所与のドロップ期間の期限切れで、前記パケットバッファの瞬間的なキューの長さ（ＩＱＬ）値および平均的なキューの長さ（ＡＱＬ）値の標本化をトリガーするステップと、
前記ＩＱＬ値が前記パケットバッファの第１のキューしきい値より大きく、かつ前記ＡＱＬ値が前記パケットバッファの第２のキューしきい値より大きい場合に、前記パケットバッファに次の着信パケットをマークするステップと、
前記ＩＱＬ値が前記パケットバッファの前記第１のキューしきい値未満であるか、または前記ＡＱＬ値が前記パケットバッファの前記第２のキューしきい値未満である場合、前記所与のドロップ期間の次の期限切れまで、次の着信パケットおよび後続するパケットをマークしないステップと
を実行させる、通信デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、米国エネルギー省によって認められた補助金交付ＤＥ−ＥＥ０００２８８７の下で政府支援を受けて行われた。政府は、本発明において特定の権利を保持している。
【０００２】
本発明は、一般的に、通信システムに関し、より詳細には、ＩＰネットワークにおけるネットワーク要素のパケットバッファのメモリ割り当てに関する。
【背景技術】
【０００３】
ネットワークフローとは、インターネットプロトコル（ＩＰ）パケットヘッダの発信元アドレスフィールドにおいて、ＩＰヘッダの宛先アドレスフィールドにおいて、場合によっては、ＩＰヘッダの他のフィールドにおいて、およびまた転送制御プロトコル（ＴＣＰ）ヘッダの発信元および宛先のポート番号フィールドなど、他のプロトコルヘッダのフィールドにおいて、同一の値を運ぶ一連のデータパケットのことである。ネットワークフローの一例として、ＴＣＰ接続のトラフィック発信元（または送信側）によって生成された一連のパケットがある。
【０００４】
ネットワークの多くの部分においてパケット交換機およびルータは、パケットが同じ出力リンクを通じて送り出される複数のフローに単一のキューを割り当てる。複数のフローに単一のキューを使用することに対する代替案は、異なるキューに異なるフローのパケットを割り当てることであるが、これは、（数千を超える）多数のネットワークフローに対応するリンクの前では非実用的な場合がある。複数のフローのパケットに対応するために単一のキューが使用される場合、キューに割り当てられるバッファスペースのサイズ変更が、典型的には、ＴＣＰトラフィックがあるときにリンク利用度を損失するのを回避する必要性によって促される。
【０００５】
ＴＣＰ発信元の適応動作は、ＴＣＰトラフィックが横断するリンクの利用を、輻輳時に新しいパケットの許可を決定するためにリンクの前のバッファが使用するポリシーに非常に敏感にする。パケット損失がない場合、ＴＣＰ発信元は、生成するトラフィックの量を増加させ続けるため、パケットバッファでさらに輻輳を引き起こし、利用可能なバッファスペースを満たす。代わりに、パケットがドロップされた場合、対応する発信元は活動を減らし、しばらくしてから、ボトルネックになっているリンクの前の輻輳が軽減される。リンクの完全な利用は、バッファが空にならなければ達成され、また、パケット損失を認識するＴＣＰ発信元の一部と、トラフィック生成速度を増加させ続けることを許可されたＴＣＰ発信元の一部との間の素晴らしいバランスの結果である。
【０００６】
長年、一般的に、ＩＰネットワークの研究開発コミュニティにおいて、容量Ｃのリンクの前では、
【０００７】
【数１】
0005676780.tif 000002
のバッファスペースをＴＣＰトラフィックフローを扱うキューに割り当てるべきであり、
【０００８】
【数２】
0005676780.tif 000003
は、キュー内のすべてのＴＣＰフローを通じて推定される、パケットの平均的なラウンドトリップタイム（ＲＴＴ）であることが受け入れられていた。このバッファ割り当て基準の目標は、最初に、Ｃ．ＶｉｌｌａｍｉｚａｒおよびＣ．Ｓｏｎｇ、「Ｈｉｇｈ−Ｐｅｒｆｏｒｍａｎｃｅ  ＴＣＰ  ｉｎ  ＡＮＳＮＥＴ」、ＡＣＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｒｅｖｉｅｗ、２４（５）：４５−６０、１９９４年［Ｖｉｌｌａｍｉｚａｒ、１９９４］において主張され、一般的に、帯域幅遅延積（ＢＤＰ）ルールと呼ばれており、トラフィック輻輳のときにキューで発生するパケット損失の結果として、キューのアンダーフロー条件、したがってリンク利用度の減少を回避することである。２０１０コアネットワークリンクの典型的な値である、
【０００９】
【数３】
0005676780.tif 000004
およびＣ＝４０Ｇｂｐｓでは、リンクの前に必要なバッファスペースは、１０Ｇｂｉｔ＝１．２５ＧＢである。この比較的大きなバッファサイズは、少なくとも２つの理由から、ネットワーク装置の製造者およびネットワークオペレータにとって主な課題となっている。第一に、バッファのサイズのために、オンチップバッファメモリを実装することが不可能になり、システム密度、設計コスト、およびエネルギー消費に悪影響を与える。第２に、ＢＤＰルールでサイズ決定されたバッファは、平均的なＲＴＴくらいの大きさの影響をエンドツーエンドのパケットの転送遅延に容易に加えることができる。加えられたこの大きな遅延は、ネットワークフローのデータ経路に沿って複数回、パケットが遭遇する可能性があり、ネットワークアプリケーションについてのエンドユーザの認識を大きく低下させる可能性がある。
【００１０】
Ｓ．ＦｌｏｙｄおよびＶ．Ｊａｃｏｂｓｏｎ、「Ｒａｎｄｏｍ  Ｅａｒｌｙ  Ｄｅｔｅｃｔｉｏｎ  Ｇａｔｅｗａｙｓ  ｆｏｒ  Ｃｏｎｇｅｓｔｉｏｎ  Ａｖｏｉｄａｎｃｅ」、ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ、１（４）：３９７−４１３、１９９３年［Ｆｌｏｙｄ、１９９３］において、著者らは、キュー占有が利用可能なバッファスペースに近づくかなり前に、パケットのドロップを開始できる、ランダムアーリーディテクション（ＲＥＤ）と呼ばれるバッファ管理方式を導入している。ＲＥＤの目的は、キューを横断するすべてのＴＣＰフローの間で、できるだけ公平にパケットの損失を分散し、連続的な大量のパケット損失の後に、多数のＴＣＰ発信元がパケットの送信を同時に停止して、リンク利用度の低下を引き起こすという、グローバルな同期条件を回避することである。ＲＥＤでは、パケットをドロップする決定は、バッファ占有しきい値（ｂｍｉｎおよびｂｍａｘ）の小さなセットと、各パケット到着時に更新される平均的なキューの長さ（ＡＱＬ）との比較に基づいている。最大ドロップ確率ｐｍａｘとともに、バッファ占有しきい値に関するＡＱＬの現在の配置によって、キューに到着するときにパケットをドロップする確率が規定される。ＲＥＤの長所は一般的に認められているが、この方式のパフォーマンスは、キューのＴＣＰトラフィックの特性により、この方式のパラメータの適切な調整に非常に影響を受けやすいため、この技法は、実用的なネットワーク装置では部分的にしか利用されていない。
【００１１】
トラフィック特性（主にアクティブなＴＣＰフローの数、およびＲＴＴ値のフローごとの分布によって識別）と、ＲＥＤ構成パラメータに対して選択された値（パケットドロップ確率曲線のプロファイル、および平均重みｗを規定するものであり、ＡＱＬを実装するローパスフィルタの遮断周波数をほぼ規定する）との間の一致の程度に対するＲＥＤのパフォーマンスの敏感さが認識されているため、オリジナルのＲＥＤの両著者は、アルゴリズムのパフォーマンスの改善を目的とした変更を次に提案している。
【００１２】
Ｖ．Ｊａｃｏｂｓｏｎ、Ｋ．Ｎｉｃｈｏｌｓ、およびＫ．Ｐｏｄｕｒｉ、「ＲＥＤ  ｉｎ  ａ  Ｄｉｆｆｅｒｅｎｔ  Ｌｉｇｈｔ」、未出版、１９９９年、＜ｈｔｔｐ：／／ｗｗｗ．ｃｎａｆ．ｉｎｆｎ．ｉｔ／〜ｆｅｒｒａｒｉ／ｐａｐｅｒｓ／ｉｓｐｎ／ｒｅｄ＿ｌｉｇｈｔ＿９＿３０．ｐｄｆ＞［Ｊａｃｏｂｓｏｎ、１９９９］において、著者らは、ＲＥＤのパフォーマンスを改善し、その構成を簡素化する有益な提言を提供している。そのような提言は、次を含む：（ａ）パケット到着に依存する代わりに、固定された時間間隔で収集された瞬間的なキューの長さのサンプルでＡＱＬを更新する；（ｂ）ＲＴＴと同じ時間的尺度で発生するすべてのキューの長さの変化（ｄｙｎａｍｉｃｓ）を平滑化するのに十分に低い値でＡＱＬを規定するローパスフィルタの遮断周波数を設定する；および（ｃ）
【００１３】
【数４】
0005676780.tif 000005
でパケットのドロップが開始されるバッファ占有しきい値の値を設定し、ここでＲＴＴ値の実際の分布が分からない場合、
【００１４】
【数５】
0005676780.tif 000006
である。この提言は、ＲＥＤのリンク利用度の改善に貢献しているが、幅広いトラフィックシナリオでリンク利用度の損失を回避するのには十分ではない。さらに、
【００１５】
【数６】
0005676780.tif 000007
の選択は、ＢＤＰルールの
【００１６】
【数７】
0005676780.tif 000008
の指示と比較して、割り当てられたバッファメモリの大幅な減少につながらない。
【００１７】
Ｓ．Ｆｌｏｙｄ、Ｒ．Ｇｕｍｍａｄｉ、およびＳ．Ｓｈｅｎｋｅｒ、「Ａｄａｐｔｉｖｅ  ＲＥＤ：Ａｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｉｎｃｒｅａｓｉｎｇ  ｔｈｅ  Ｒｏｂｕｓｔｎｅｓｓ  ｏｆ  ＲＥＤ’ｓ  Ａｃｔｉｖｅ  Ｑｕｅｕｅ  Ｍａｎａｇｅｍｅｎｔ」、未公開、２００１年、＜ｈｔｔｐ：／／ｉｃｉｒ．ｏｒｇ／ｆｌｏｙｄ／ｐａｐｅｒｓ／ａｄａｐｔｉｖｅＲｅｄ．ｐｄｆ＞［Ｆｌｏｙｄ、２００１］において、著者らは、［Ｊａｃｏｂｓｏｎ、１９９９］の提言、およびＷ．Ｆｅｎｇ、Ｄ．Ｋａｎｄｌｕｒ、Ｄ．Ｓａｈａ、およびＫ．Ｓｈｉｎ、「Ａ  Ｓｅｌｆ−Ｃｏｎｆｉｇｕｒｉｎｇ  ＲＥＤ  Ｇａｔｅｗａｙ」、ＩＥＥＥ  Ｉｎｆｏｃｏｍ  １９９９の会議録［Ｆｅｎｇ、１９９９］に新しく提示された概念を利用して、ドロップ確率関数の傾斜が、ＡＱＬの進展に動的に調整され、ＡＱＬが上限しきい値ｂｕを超えた場合に、それを増加させ、ＡＱＬが下限しきい値ｂｌを下回る場合に、それを減少させるＡｄａｐｔｉｖｅ  ＲＥＤ（ＡＲＥＤ）アルゴリズムを規定している。ＲＥＤのオリジナルの設計と比較すると、ＡＲＥＤの改良により、パフォーマンスおよび構成の容易さの両方が改善され、ネットワーク管理者が構成するべきパラメータは２つだけになる：
【００１８】
【数８】
0005676780.tif 000009
の期待される値および平均的なキュー遅延ｄでの望ましい値である。パケットドロップ確率の傾斜を制御するアルゴリズムは、［Ｆｌｏｙｄ、２００１］では堅牢さと収束の速度について最適化されていない。さらに、まだパケットドロップ確率へのＡＱＬレベルのマッピングに依存している：つまり、安定境界内のパケットバッファを維持するために必要とされるドロップ率が高いほど、そのドロップ率を設定するＡＱＬ、したがってＴＣＰフローが経験する全体的なＲＴＴへのバッファの影響が大きくなる。最後に、ＡＱＬに対するパケットドロップ確率の線形の依存関係は、ＡＲＥＤの不安定さの原因として残る。なぜなら、それはＲＥＤの本来の設計に対するものであり、通常のトラフィック構成の下では本質的な場合があるリンク利用度の損失に結びつくからである。
【００１９】
より最近、Ｇ．Ａｐｐｅｎｚｅｌｌｅｒ、Ｉ．Ｋｅｓｌａｓｓｙ、およびＮ．ＭｃＫｅｏｗｎ、「Ｓｉｚｉｎｇ  Ｒｏｕｔｅｒ  Ｂｕｆｆｅｒｓ」、ＡＣＭ  ＳＩＧＣＯＭＭ  ２００４の会議録、ポートランド、オレゴン州、２００４年８月、［Ａｐｐｅｎｚｅｌｌｅｒ、２００４］において、著者らは、高速ネットワークリンクの前で多数の非同期化されたＴＣＰフローに対応するバッファのサイズ決定要件を検討し、
【００２０】
【数９】
0005676780.tif 000010
くらいの大きさのバッファサイズは、合計時間の制御可能な部分でバッファアンダーフロー条件の発生確率を維持するのに十分であると結論づけた。ここで、Ｎは、リンクの非同期化された長命（ｌｏｎｇ−ｌｉｖｅｄ）ＴＣＰフローの数である。何千もの非同期化された長命のボトルネックとなるＴＣＰフローを持つネットワークリンクにおいて（１セットのＴＣＰフローは、そのセットのフローの伝送窓が異なるときにピークに達する場合に非同期化される；長命のＴＣＰフローとは、その発信元が少なくとも１度、スロースタート状態を離れたことがあるフローである；ボトルネックとなるＴＣＰフローは、検討中の混雑したバッファでフローが受信する公平な割り当て分によって平均的なエンドツーエンドのスループットが設定されるフローである）、［Ａｐｐｅｎｚｅｌｌｅｒ，２００４］の著者らは、小型バッファルールは、オンチップメモリを使用する、その実装を可能にするのに十分なパケットバッファのサイズの削減をもたらすだろうと述べている。しかし、このバッファサイズ減少手法の堅牢さおよび範囲は、後に続く多くの論文で異議が申し立てられ、最終的には、提案の本来の著者らは結論を大幅に修正することとなった。
【００２１】
望ましいのは、ネットワークシステムデザイナが、ネットワークインターフェースの前でパケットをバッファリングするのに必要なメモリの量を減らすことを可能にして、これによって、バッファリング目的のためだけに個別のハードウェアコンポーネントを必要とする代わりに、同じメモリを、パケットを処理および転送するのと同じハードウェアコンポーネントに統合できる、バッファ管理／パケット許可の方式である。
【先行技術文献】
【非特許文献】
【００２２】
【非特許文献１】Ｃ．ＶｉｌｌａｍｉｚａｒおよびＣ．Ｓｏｎｇ、「Ｈｉｇｈ−Ｐｅｒｆｏｒｍａｎｃｅ  ＴＣＰ  ｉｎ  ＡＮＳＮＥＴ」、ＡＣＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｒｅｖｉｅｗ、２４（５）：４５−６０、１９９４年［Ｖｉｌｌａｍｉｚａｒ、１９９４］
【非特許文献２】Ｓ．ＦｌｏｙｄおよびＶ．Ｊａｃｏｂｓｏｎ、「Ｒａｎｄｏｍ  Ｅａｒｌｙ  Ｄｅｔｅｃｔｉｏｎ  Ｇａｔｅｗａｙｓ  ｆｏｒ  Ｃｏｎｇｅｓｔｉｏｎ  Ａｖｏｉｄａｎｃｅ」、ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ、１（４）：３９７−４１３、１９９３年［Ｆｌｏｙｄ、１９９３］
【非特許文献３】Ｖ．Ｊａｃｏｂｓｏｎ、Ｋ．Ｎｉｃｈｏｌｓ、およびＫ．Ｐｏｄｕｒｉ、「ＲＥＤ  ｉｎ  ａ  Ｄｉｆｆｅｒｅｎｔ  Ｌｉｇｈｔ」、未出版、１９９９年、＜ｈｔｔｐ：／／ｗｗｗ．ｃｎａｆ．ｉｎｆｎ．ｉｔ／〜ｆｅｒｒａｒｉ／ｐａｐｅｒｓ／ｉｓｐｎ／ｒｅｄ＿ｌｉｇｈｔ＿９＿３０．ｐｄｆ＞［Ｊａｃｏｂｓｏｎ、１９９９］
【非特許文献４】Ｓ．Ｆｌｏｙｄ、Ｒ．Ｇｕｍｍａｄｉ、およびＳ．Ｓｈｅｎｋｅｒ、「Ａｄａｐｔｉｖｅ  ＲＥＤ：Ａｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｉｎｃｒｅａｓｉｎｇ  ｔｈｅ  Ｒｏｂｕｓｔｎｅｓｓ  ｏｆ  ＲＥＤ’ｓ  Ａｃｔｉｖｅ  Ｑｕｅｕｅ  Ｍａｎａｇｅｍｅｎｔ」、未公開、２００１年、＜ｈｔｔｐ：／／ｉｃｉｒ．ｏｒｇ／ｆｌｏｙｄ／ｐａｐｅｒｓ／ａｄａｐｔｉｖｅＲｅｄ．ｐｄｆ＞［Ｆｌｏｙｄ、２００１］
【非特許文献５】Ｗ．Ｆｅｎｇ、Ｄ．Ｋａｎｄｌｕｒ、Ｄ．Ｓａｈａ、およびＫ．Ｓｈｉｎ、「Ａ  Ｓｅｌｆ−Ｃｏｎｆｉｇｕｒｉｎｇ  ＲＥＤ  Ｇａｔｅｗａｙ」、ＩＥＥＥ  Ｉｎｆｏｃｏｍ  １９９９の会議録［Ｆｅｎｇ、１９９９］
【非特許文献６】Ｇ．Ａｐｐｅｎｚｅｌｌｅｒ、Ｉ．Ｋｅｓｌａｓｓｙ、およびＮ．ＭｃＫｅｏｗｎ、「Ｓｉｚｉｎｇ  Ｒｏｕｔｅｒ  Ｂｕｆｆｅｒｓ」、ＡＣＭ  ＳＩＧＣＯＭＭ  ２００４の会議録、ポートランド、オレゴン州、２００４年８月、［Ａｐｐｅｎｚｅｌｌｅｒ、２００４］
【非特許文献７】Ａ．Ｖｉｓｈｗａｎａｔｈ、Ｖ．Ｓｉｖａｒａｍａｎ、およびＭ．Ｔｈｏｔｔａｎ、「Ｐｅｒｓｐｅｃｔｉｖｅｓ  ｏｎ  ｒｏｕｔｅｒ  ｂｕｆｆｅｒ  ｓｉｚｉｎｇ：Ｒｅｃｅｎｔ  ｒｅｓｕｌｔｓ  ａｎｄ  ｏｐｅｎ  ｐｒｏｂｌｅｍｓ」、ＡＣＭ  ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ  ３９（２）：３４−３９、２００９年［Ｖｉｓｈｗａｎａｔｈ、２００９］
【非特許文献８】Ｙ．ＧａｎｊａｌｉおよびＮ．ＭｃＫｅｏｗｎ、「Ｕｐｄａｔｅ  ｏｎ  ｂｕｆｆｅｒ  ｓｉｚｉｎｇ  ｉｎ  Ｉｎｔｅｒｎｅｔ  ｒｏｕｔｅｒｓ」、ＡＣＭ  ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ、３６（５）：６７−７０、２００６年［Ｇａｎｊａｌｉ，２００６］
【発明の概要】
【発明が解決しようとする課題】
【００２３】
本発明の原理により、従来技術を超えて、定期的な早期廃棄（ＰＥＤ）と呼ばれるバッファ管理方式のためのシステムおよび方法のために新しい手法に向けて前進する。本発明は、ＴＣＰトラフィックが存在するときに、キューの長さは、パケットをドロップするための適切な頻度の選択によって安定させることができるという観察に基礎を置いている。ＴＣＰ接続の数と、それぞれのＲＴＴ値の分布の組み合わせについて、キューのオーバーフローまたはアンダーフローを防ぐ理想的なパケットドロップ頻度が存在する。理想的なパケットドロップ頻度の値は、時間とともに急速に変わり、過去のパケット損失によって影響を受けた一連のＴＣＰ接続に敏感であり、特に、インラインで計算するのは不可能であるが、長期間にわたり、事前に規定された範囲内にキュー占有を維持することを可能にするように、誤差の範囲を用いて見積もることは可能である。ＰＥＤ方式は、（知られていない）理想的なパケットドロップ頻度を追跡し、キューを横断する１セットのＴＣＰ接続の集合的な時定数と同等の時間的尺度で発生する頻度修正で、キュー占有の進展に基づいて見積もった値を調整することを目的としている。
【課題を解決するための手段】
【００２４】
本発明の一実施形態では、通信ネットワークでパケットバッファを運用する方法が説明され、パケットバッファは、パケットの複数のフローを受け入れるように動作可能である。方法は、所定期間のドロップタイマーを提供するステップを含み、所定期間の期限が切れると、瞬間的なキューの長さ（ＩＱＬ）値および前記パケットバッファの平均的なキューの長さ（ＡＱＬ）値の標本化がトリガーされる。ＩＱＬ値が、パケットバッファの最小キューしきい値より大きく、かつＡＱＬ値が、パケットバッファのゲートキューしきい値より大きい場合、前記パケットバッファへの次の着信パケットがマークされる。ＩＱＬ値が、パケットバッファの最小キューしきい値未満である、またはＡＱＬ値が、パケットバッファのゲートキューしきい値未満である場合、所定期間の次の期限切れまで、次の着信パケットおよび後続するパケットはマークされない。
【００２５】
他の実施形態では、マークされている着信パケットは、前記パケットバッファに許可されずに直ちにドロップされ、マークされていない着信パケットは、前記パケットバッファに許可される資格を有していると考えられる。
【００２６】
他の実施形態では、マークされている着信パケットは、その内部フィールドの１つまたは複数で変更され、前記パケットバッファに許可される資格を有していると考えられる。
【００２７】
本発明の他の実施形態は、固定されたドロップタイマーを含み、他の実施形態は、所与の修正間隔で調整される可変ドロップタイマーを含む。他の実施形態では、前記ドロップタイマーの前記所定期間を調整するための所与の修正間隔は、固定された期間である。本発明の一実施形態では、前記所与の修正間隔の期限のうちの１つが切れている場合、ＡＱＬ値が最小キューしきい値と最大キューしきい値との間にあれば、ドロップタイマーの所定期間は変更されないままである。前記所与の修正間隔の期限うちの１つが切れた場合、ＡＱＬ値が前記パケットバッファの最小キューしきい値未満なら、前記ドロップタイマーの所定期間は増加し、前記所与の修正間隔の期限のうちの１つが切れた場合、ＡＱＬ値が前記パケットバッファの最大キューしきい値より大きければ、前記ドロップタイマーの所定期間は減少する。ＡＱＬ値とパケットバッファの最小キューしきい値との間の比率がより小さい場合、ドロップタイマーの所定期間の増加はより大きく、前記ＡＱＬ値と最大キューしきい値との間の比率がより大きい場合、前記ドロップタイマーの所定期間の減少はより大きい。
【００２８】
他の実施形態では、パケットバッファの安全キューしきい値がさらに含まれ、ＡＱＬ値が安全しきい値を超える場合、前記所与の修正間隔のうちの現在の１つが期限切れする前に、前記ドロップタイマーの所定期間の緊急修正を行うことができる。
【００２９】
一実施形態では、ドロップタイマーの所定期間の新しい値は、前記所定期間の少なくとも２つの最新の値の関数として計算される。一実施形態では、次の着信パケットの許可またはマーキングを決定する他の方法は、パケットバッファで同時に運用することができる。
【００３０】
他の実施形態では、ＡＱＬおよびＩＱＬの値は、サブパケットのデータ単位で測定され、マーキングアクションは、１つの次の着信パケットまたは複数の次の着信パケットに含まれている可能性がある所定量の前記サブパケットのデータ単位に適用される。一実施形態では、サブパケットのデータ単位はバイトである。他の実施形態では、サブパケットのデータ単位はメモリワードである。
【００３１】
本発明は、また、メモリを持つ通信デバイスに関し、メモリは、複数の命令をそこに格納し、前記デバイスがパケットバッファをさらに含み、パケットバッファがパケットの複数のフローを受け入れるように動作可能であり、複数の命令がプロセッサによって実行されると、プロセッサに前記方法のステップを実行させる。
【００３２】
本発明の別の実施形態では、通信ネットワークにおいてデータリンクの前でパケットバッファを運用する方法が開示され、着信パケットは、設定された頻度でマークされる。方法は、データリンクを通じてパケットの伝送に必要な時間より本質的に長い時間、設定された頻度の値を保持するステップと、パケットバッファの多数のパケットが事前に規定されたしきい値に達したときに、設定された頻度の値を新しい値に置き換えるステップとを含む。
【００３３】
本明細書の教示は、添付図面に関して以下の詳細な説明を考慮することによって容易に理解できるだろう。
【図面の簡単な説明】
【００３４】
【図１】本来のＲＥＤ方式のドロップ確率曲線を示す図である。
【図２】Ａｄａｐｔｉｖｅ  ＲＥＤの調整可能なパケットドロップ確率曲線を示す図である。
【図３】本発明によるドロップ期間更新の例示的な擬似コードを示す図である。
【図４】ＰＥＤアルゴリズムを実行するためのイベントの概要を示す図である。
【図５】例示的なネットワーク構成を示す図である。
【図６】第１の説明的なトラフィックシナリオのシミュレーションから得られたＰＥＤバッファの平均および瞬間的なキューの長さのプロットを示す図である。
【図７】第１の説明的なトラフィックシナリオのシミュレーションから得られたＡＲＥＤバッファの平均および瞬間的なキューの長さのプロットを示す図である。
【図８】図７のプロットから抽出された０．５ｓの時間間隔の詳細を用いるプロットを示す図である。
【図９】第２の説明的なトラフィックシナリオのシミュレーションから得られるＰＥＤバッファの平均および瞬間的なキューの長さのプロットを示す図である。
【図１０Ａ】本発明の定期的な早期廃棄（ＰＥＤ）方法の例示的な流れ図である。
【図１０Ｂ】本発明の定期的な早期廃棄（ＰＥＤ）方法の例示的な流れ図である。
【図１０Ｃ】本発明の定期的な早期廃棄（ＰＥＤ）方法の例示的な流れ図である。
【図１１】本発明の方法を実装するための例示的な通信デバイスのハイレベルブロック図である。
【発明を実施するための形態】
【００３５】
ここで、本発明の例示的な実施形態について、図を参照しながら記述する。そのいくつかは、以下の記述の過程において同時に参照する場合がある。しかし、本発明について記述する前に、本発明の態様に関係するので、従来技術についていくつかの説明を続ける。
【００３６】
［Ａｐｐｅｎｚｅｌｌｅｒ、２００４］の公開に続く大規模な研究労力（Ａ．Ｖｉｓｈｗａｎａｔｈ、Ｖ．Ｓｉｖａｒａｍａｎ、およびＭ．Ｔｈｏｔｔａｎ、「Ｐｅｒｓｐｅｃｔｉｖｅｓ  ｏｎ  ｒｏｕｔｅｒ  ｂｕｆｆｅｒ  ｓｉｚｉｎｇ：Ｒｅｃｅｎｔ  ｒｅｓｕｌｔｓ  ａｎｄ  ｏｐｅｎ  ｐｒｏｂｌｅｍｓ」、ＡＣＭ  ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ  ３９（２）：３４−３９、２００９年［Ｖｉｓｈｗａｎａｔｈ、２００９］に完全に要約されている）では、エッジおよびプライベートネットワークリンクのように、より少数かつ場合によっては同期された長命のフローを用いるより一般的な設定へと、［Ａｐｐｅｎｚｅｌｌｅｒ、２００４］の結果を拡張するための簡単な解決策はもたらされず、実際には、Ｙ．ＧａｎｊａｌｉおよびＮ．ＭｃＫｅｏｗｎ、「Ｕｐｄａｔｅ  ｏｎ  ｂｕｆｆｅｒ  ｓｉｚｉｎｇ  ｉｎ  Ｉｎｔｅｒｎｅｔ  ｒｏｕｔｅｒｓ」、ＡＣＭ  ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ、３６（５）：６７−７０、２００６年［Ｇａｎｊａｌｉ，２００６］において、コアネットワークリンクについても小型バッファルールの保守的な修正へとつながった：
【００３７】
【数１０】
0005676780.tif 000011
バッファオーバーフローおよびバッファアンダーフローの両方のイベントを回避するために、ＴＣＰ発信元の活動を円滑に制御するために輻輳の早期検出に依存するバッファ管理方式は、リンク利用度を理想である１００％目標に近く維持する際に、より高い効率の見込みを保持している。文献で提案されているすべてのＲＥＤタイプ（ｆｌａｖｏｒ）のうち、Ａｄａｐｔｉｖｅ  ＲＥＤ（ＡＲＥＤ）ファミリ（［Ｆｅｎｇ、１９９９］および［Ｆｌｏｙｄ、２００１］）は、構成の容易さ（構成するのは２つのパラメータだけで、そのうち一方は、パフォーマンス目標に依存し、他方は、推定されたネットワーク経路の特性に依存する）と、リンク利用度のパフォーマンスとの最善の組み合わせを提供しているように見える。一般的に、遅延パフォーマンスが厳格であるほど、必要なバッファスペースの合計は小さくなる。ネットワーク経路特性の推定の精度、すなわち１セットの進行中のＴＣＰ接続の平均ＲＴＴは、バッファにバッファオーバーフローおよびバッファアンダーフローのイベントが生じないように維持するために必要なパケットドロップ確率の最適な傾斜へとＡＲＥＤの閉ループ制御をロックする速度を規定する。
【００３８】
本来のＲＥＤバージョンを超えて、および簡素なテールドロップポリシーを超えてＡＲＥＤによって可能になった増分的な改善は疑問の余地がないが、もともと規定されていた方式では、特定のトラフィック構成において、そのパフォーマンスを害する可能性がある４つの欠点が提示されている。第一に、この方式は、混雑していない条件で閉ループ制御の運用を回避するための準備を含まない。結果として、ドロップ確率の傾斜は、高速に進展する輻輳期間の最終的な発生に反応できずに、利用可能な範囲の下端でロックされることになる可能性がある。第２に、バッファ平衡状態（パケットドロップイベントの頻度が、輻輳回避状態のＴＣＰ接続の数と、それぞれのＲＴＴ値との間の比率によって決定されたトラフィック成長率に一致するときに到達する）は、ＡＱＬの特定の値に関連しているため、より高いドロップ確率（より多くのＴＣＰ接続およびより短いネットワーク経路がある状態で必要）には、より高い平均的なキュー遅延が伴う。第３に、連続するドロップイベント間に間隔をあける時間を規定する際に、固定された時間間隔の代わりに確率を使用することで、一連のドロップイベントに不規則性が加えられるため、平衡点の周囲により広い振動（ｏｓｃｉｌｌａｔｉｏｎ）が引き起こされる。第４に、パケットドロップ決定は、ＡＱＬの観察に基づいており、これにより、（パケットをドロップすることによって）バッファ占有増加の修正処置が取られる時間と、（ＡＱＬを観察することによって）その修正の影響が測定される時間との間の距離が増加する。ネットワーク経路は、瞬間的なキューの長さ（ＩＱＬ）を通じて測定可能である、接続がパケットを失うときと、パケット損失が発信元活動の減少に変わるときとの間のＲＴＴと同等の遅延を本質的に引き起こす。パケットをドロップする決定のためにＡＱＬを使用することで、ＡＱＬ計算を実装するローパスフィルタの遮断周波数の逆数と同じくらい大きい可能性がある追加的な遅延が引き起こされる。理想的には、フィルタの遮断周波数は（逆数より小さいとはいかないにしても）ＲＴＴ値の逆数に設定されるので、パケットドロップ決定にＡＱＬ使用することで、その決定の時間の不正確さが２倍になる。
【００３９】
ＡＲＥＤの第１の欠点は、パケットドロップ確率の傾斜を制御するアルゴリズムの簡単な変更で修正することができるが、他の３つの欠点はＲＥＤの定義に本来備わっているものであるため、解決するためには、輻輳条件を早期検出するために根本的に異なる手法が必要である。
【００４０】
図１は、パケットドロップ確率にＡＱＬレベルをマッピングする関数の典型的なプロファイルを示している。図１の関数を使うと、ＡＱＬ
【００４１】
【数１１】
0005676780.tif 000012
が最小しきい値ｂｍｉｎを下回っている限り、ＲＥＤはパケットをドロップしない。ＡＱＬが最小しきい値ｂｍｉｎと最大しきい値ｂｍａｘとの間にある場合、着信パケットは、２つのしきい値の間にあるＡＱＬの現在位置に線形に依存する確率でドロップされる
（
【００４２】
【数１２】
0005676780.tif 000013
のとき、確率はｐｍａｘ）。
【００４３】
【数１３】
0005676780.tif 000014
のとき、およびまた利用可能な合計バッファスペースを規定するしきい値Ｑｍａｘ＞ｂｍａｘをＩＱＬが超える場合、ＲＥＤは、すべての着信パケットをドロップする。ＩＱＬの代わりにＡＱＬを使用することで、パケットドロップ決定は、輻輳条件の発生ではなく、通常のＴＣＰ変化を反映する短期的なＩＱＬ変動から分離されるため、パケットドロップ率に影響はない。
【００４４】
Ａｄａｐｔｉｖｅ  ＲＥＤ（ＡＲＥＤ）アルゴリズムは、［Ｆｌｏｙｄ、２００１］に指定されているように、事前に規定された範囲内にその値を設定する制御アルゴリズムにｐｍａｘを支配させる。トラフィック状況の変動に対する制御ループの遅い反応によって、過度に密度が高いパケットドロップの連鎖がトリガーされないことを確実にするように（これによって、リンク利用度に破滅的な損失があるグローバルな同期条件が引き起こされる可能性がある）、ＡＲＥＤは、緩やかなバージョンのドロップ確率曲線を採用している。これによって、
【００４５】
【数１４】
0005676780.tif 000015
から
【００４６】
【数１５】
0005676780.tif 000016
に直ちにはね上がらせるのではなく、（ｂｍａｘ，ｐｍａｘ）と（ｂｔｏｐ＝２ｂｍａｘ，１）との間を線形に増加する（図２を参照）。少なくとも時間Ｔの間、同じｐｍａｘ値を保持した後（５００ｍｓが［Ｆｌｏｙｄ、２００１］で推薦される値である）、ＡＱＬをｂｄ＝Ｃ・ｄ前後に設定するという最終目的で、ＡＱＬがしきい値ｂｕを超えるとすぐに、制御アルゴリズムはｐｍａｘを減少させる、またはＡＱＬがしきい値ｂｌを下回って落ちるとすぐに増加させる。ここで、ｄは、目標平均遅延時間（ｂｍｉｎ＜ｂｌ＜ｂｄ＜ｂｕ＜ｂｍａｘ）である。［Ｆｌｏｙｄ、２００１］の著者らは、目標平均遅延時間ｄからすべてのバッファしきい値を自動的に導き出し、それらの構成の不確実性からユーザを解放する：ｂｍｉｎ＝０．５ｂｄ、ｂｌ＝０．９ｂｄ、ｂｕ＝１．１ｂｄ、およびｂｍａｘ＝１．５ｂｄ。許可されたｐｍａｘ値の範囲も固定されている：［０．０１，０．５］。デフォルト値について、すべての提言に従うことによって、ユーザには、唯一の任意のパラメータとして目標平均遅延時間（またはバッファスペースＱｍａｘ≧ｂｔｏｐの望ましい全割り当て）が残される。簡単に言うと、ファントムドロップ率φ（ｔ）に継続的に一致する理想的なパケットドロップ確率ｐ＊（ｔ）に、目標平均遅延時間のＡＱＬをマッピングするという最終目的によって促されて、ＡＲＥＤは、パケットドロップ確率の２つの部分の傾斜を制御するためのメカニズムに、本来のＲＥＤを組み合わせる。著者らが記載しているように、［Ｆｌｏｙｄ、２００１］に指定された制御アルゴリズムは、収束の精度および速度について必ずしも最適化されていない。
【００４７】
上記のように、ＡＲＥＤの特定の欠点は、パケットドロップ確率の傾斜を制御するアルゴリズムの簡単な変更で修正することができるが、他の欠点はＲＥＤの定義に本来備わっているものであるため、解決するためには、輻輳条件を早期検出するために根本的に異なる手法が必要である。したがって、本発明の態様について、ここに記述する。
【００４８】
定期的な早期廃棄
本発明は、定期的な早期廃棄（ＰＥＤ）と呼ばれるバッファ管理方式を規定する。最先端技術のバッファ管理技術と比較して、ＰＥＤ方式は、リンク利用度（スループット）および平均的なキュー遅延など重要なパフォーマンスメトリックを明白に改善し、構成の複雑さを最小限にする（利用可能なメモリサイズがシステム設計によって規定されると、すべてのパラメータに固定値が与えられるか、または特定のパフォーマンス目標に基づいてカスタマイズすることができる）。
【００４９】
本発明は、ネットワーク要素においてパケットバッファの実装に必要なメモリの量を大幅に減らす方法を提供し、現在のオフチップ実装とは対照的に、そのようなバッファをオンチップに実装することを可能にする。これで、より多くのパケット処理コンポーネントをより小さな空間に適合できるため、この構成上の進歩の利点は、エネルギー消費ならびにシステムの拡張性および統合に関して非常に優れたものである。外部メモリをなくすことで、ネットワークシステムの設計が簡素化し、より高い統合が可能になり、エネルギー効率が改善される。メモリを小型化することで、また、ネットワークリンクの利用を減らすことなく、かつバッファを横断するＴＣＰフローの完了時間を増加させることなく（ＴＣＰフローの完了時間は、ＴＣＰ送信側からＴＣＰ受信側へと、ウェブベージなどのデータオブジェクト全体を伝えるのに必要な時間である）、ネットワークアプリケーションパケットが経験するエンドツーエンドの遅延に対するネットワークバッファの影響が減る。
【００５０】
本発明の根本概念は、ＴＣＰトラフィックが存在する場合、キューの長さは、パケットをドロップするための適切な頻度の選択によって安定させることができるという観察から由来している。ＴＣＰ接続の数と、それぞれのＲＴＴ値の分布の任意の組み合わせについて、キューがオーバーフローまたはアンダーフローするのを防ぐ理想的なファントムドロップ率φ（ｔ）が存在する。ファントムドロップ率の値は、時間とともに急速に変更でき、過去のパケット損失によって影響を受ける一連のＴＣＰ接続に敏感であり、特に、インラインで計算するのは不可能であるが、長期間の間、事前に規定された範囲内にキュー占有を維持することを可能にする誤差の範囲を用いて見積もることは考えられる。ＰＥＤ方式は、（知られていない）ファントムドロップ率を追跡し、キューを横断する１セットのＴＣＰ接続の集合的な時定数と同等の時間的尺度で発生する率修正で、キュー占有の進展に基づいて見積もった率の値を調整することを目的としている。
【００５１】
ＰＥＤは、ＲＥＤの安定したインスタンス（ｉｎｓｔａｎｃｅ）が、固定されたパケットドロップ確率をＡＱＬ値の拡張された範囲に関連づけるものであるという実験的な証拠に基礎を置いているため、（ＩＱＬに追いつくときの）ＡＱＬの通常の増加が、より高いパケットドロップ率およびグローバルな同期につながることはない。望ましいパケットドロップ率を一貫して実施するために、また、変化するドロップ間間隔をもたらすパケットドロップ確率についての概念を、均等に間隔があけられたパケットドロップイベントを実施し、本発明の名称の由来となるパケットドロップ期間に置き換える。
【００５２】
一般的な設計では、ＰＥＤは、異なる時間的尺度で動作する２つのコンポーネントを組み合わせる。より短い（パケットの）時間的尺度では、輻輳の兆候が明白な場合、ＰＥＤは固定された時間間隔でパケットをドロップする。より長い（ＲＴＴ）時間的尺度では、制御アルゴリズムは、ＡＱＬの進展へとパケットドロップ期間を調整する。
【００５３】
本発明のＰＥＤ方法の以下の特性について留意されたい。その態様は、当業者なら理解するであろう。
【００５４】
１．ＰＥＤのより簡単な実装は、パケットドロップ期間の動的調整のために制御アルゴリズムを含んでいなくてもよい。これらの実装は、一定のパケットドロップ期間で動作し、その値は、ネットワーク内のパケットバッファの配置に依存してネットワークオペレータが設定することができる。
【００５５】
２．ＰＥＤは、他のバッファ管理方式に関連して、または分離して、バッファへのパケットの許可を制御するために使用することができる。ＰＥＤを使用するすべてのケースにおいて、新しい着信パケットに対応するのに十分な空間がバッファにない場合、１つまたは複数のパケットが廃棄される。
【００５６】
３．この記述は、新しいパケットがバッファに許可されるかどうかを決定する方法としてＰＥＤを使用することに注目しているが、本発明の方法は、限定することなく、パケットマーキングのより一般的な用途に向いており、パケットヘッダのフィールドは、他のパケットより高い確率でドロップするために、パケットと見なすことができることをダウンストリームバッファに、または関連するフローが、そのデータ経路に沿ってネットワーク輻輳を経験していて、それぞれの発信元のトラフィック生成活動が減らされるべきであることを、単にパケットのエンド受信機に通知するために変更される。
【００５７】
４．この説明では、ＰＥＤ実行の結果はパケット全体に適用されるが、バイトおよびメモリワードなどサブパケットデータ単位に適用されるＰＥＤのバージョンを同様に実装することができる。
【００５８】
ＰＥＤは、より詳しくは本明細書に記述するように、ＩＱＬ  ｑおよびＡＱＬ
【００５９】
【数１６】
0005676780.tif 000017
の標本化、ならびにそれぞれのしきい値
【００６０】
【数１７】
0005676780.tif 000018
と
【００６１】
【数１８】
0005676780.tif 000019
との比較をトリガーするために、制御可能な継続時間の期間τＤを持つドロップタイマーを使用する。ドロップタイマーの期限が切れたときに
【００６２】
【数１９】
0005676780.tif 000020
および
【００６３】
【数２０】
0005676780.tif 000021
であれば、ＰＥＤは、次の着信パケットをドロップ（またはマーク）する；そうでない場合は、ドロップ期間の次の期限切れまで、次のパケットおよび後続するすべてのパケットをキューに受け入れる。
【００６４】
ＰＥＤは、ＡＱＬの進展に基づいてドロップタイマーの期間τＤを制御する。ほとんどのＴＣＰ接続（たとえば、Ｔ＝５００ｍｓ）のＲＴＴ値を含めるのに十分に大きい時定数Ｔより好ましくは短い時間間隔で、ＰＥＤは、
【００６５】
【数２１】
0005676780.tif 000022
を最小ＰＥＤしきい値
【００６６】
【数２２】
0005676780.tif 000023
および最大ＰＥＤしきい値
【００６７】
【数２３】
0005676780.tif 000024
と比較する。
【００６８】
【数２４】
0005676780.tif 000025
の場合、ＰＥＤはτＤを増加し、
【００６９】
【数２５】
0005676780.tif 000026
の場合、減少させる。両方の場合において、修正イベントｍのドロップ期間τＤ［ｍ］の新しい値は、現在値τＤ［ｍ−１］（修正イベントｍ−１で設定）および前回の値τＤ［ｍ−２］（修正イベントｍ−２で設定）の両方から得られる。期間修正のサイズは、ＡＱＬと関連するしきい値との間の比率によって変更される（期間増加については
【００７０】
【数２６】
0005676780.tif 000027
および期間減少については
【００７１】
【数２７】
0005676780.tif 000028
）。ドロップタイマーの期間は、２つのしきい値の間にＡＱＬがあると分かるたびに変更されずに維持される。
【００７２】
図３を参照すると、ドロップ期間更新の例示的な実装について、擬似コードが示されている。最新のドロップ期間更新以降、少なくとも時間Ｔが経過した後のパケットドロップ期間の更新をコードは要約している。図３の等式において、αは、ＡＱＬと最小ＰＥＤしきい値との間の比率（期間増加）、または最大ＰＥＤしきい値とＡＱＬとの間の比率（期間減少）のいずれかであり、Ｋは、期間修正の最大サイズである（α＝０のとき、修正は最大である）。
【００７３】
ＰＥＤは、ＡＱＬを更新するために、同期的で時間駆動型のバックグラウンドプロセスを使用する。平均期間τｑを設定する基準は、ＲＥＤの同期バージョンのものに似ている：期間は、キューの出力容量の典型的なサイズのパケットの送出間の時間より大きさであるべきであるが（たとえば、τｑ≧１５００Ｂ／４０Ｇｂｐｓ＝０．３μｓ）、目標平均遅延時間のごく一部分（たとえば５％）より大きくてはいけない（たとえば、τｐ≦０．０５・１ｍｓ＝５０μｓ）。通常のように、ＰＥＤは、指数加重移動平均（ＥＷＭＡ）としてＡＱＬ
【００７４】
【数２８】
0005676780.tif 000029
を計算する：
【００７５】
【数２９】
0005676780.tif 000030
。ＥＷＭＡ重みｗは、平均期間と、ＥＷＭＡによってインスタンス化されたローパスフィルタの時定数との間の比率によって規定される：ｗ＝τｑ／Ｔ。
【００７６】
通常のＴＣＰ変化が、ファントムドロップ率に一致する目標からドロップ期間の制御をそらすのを防ぐために、ＰＥＤは、また、次のためのプロビジョニングを含む：（ａ）最近のパケットドロップイベントの結果ではない、低負荷条件でのドロップ期間τＤの修正をサスペンドする、（ｂ）時定数Ｔに相当する時間内にバッファ占有が空からいっぱいに増えた後に、ドロップ期間を利用可能な最小値にリセットする（そのようなイベントは、現在のパケットドロップ期間が、現在のトラフィックミックスに適切に対処するには大きすぎるという兆候である）、かつ（ｃ）ＡＱＬが安全しきい値
【００７７】
【数３０】
0005676780.tif 000031
を超えるとすぐに、時定数Ｔの期限切れの前でも、ドロップ期間を緊急に修正することを許可する。
【００７８】
多くの点で、ＰＥＤはＲＥＤとは異なる。既に説明したように、ＰＥＤは、ＡＱＬを用いて継続的に変更する代わりに、最小時間Ｔに対して固定されたパケットドロップ率を維持する。これで、パケットドロップ確率を固定されたパケットドロップ期間に置き換えることによって、ドロップ間の時間における変動を最小限にする。
【００７９】
ＰＥＤの新規性の他の重要な要素は、バッファ管理方式とＴＣＰ発信元の変化との間の相互作用に対して、データ経路およびフィルタリング遅延が持つ影響について熟慮していることである。発信元がパケット損失を認識し、その認識でボトルネックキューのＩＱＬに対する明白な影響をもたらすのはＲＴＴに相当する時間がかかる。時定数
【００８０】
【数３１】
0005676780.tif 000032
を用いるＥＷＭＡのために、ＡＱＬがＩＱＬ変動に追いつくには同様の余分な時間がかかる。ファントムドロップ率を追跡する制御メカニズムの精度は、ＴＣＰ発信元の活動の調整と、それらの調整を促進するキューの長さへの修正処置との間の時間距離に密接に依存している。ＲＴＴによって引き起こされた遅延は回避できないが、パケットドロップ決定の規定においてＩＱＬに重要な役割を与えることによって、ＰＥＤは、ＥＷＭＡの余分な遅延の影響を取り除く。また、ＰＥＤは、輻輳の早期兆候が存在することを確認するためにＡＱＬをチェックするのは真実だが、この目的に使用されるしきい値
【００８１】
【数３２】
0005676780.tif 000033
は、主なしきい値
【００８２】
【数３３】
0005676780.tif 000034
のサイズの半分しかないため、ＥＷＭＡ遅延は、実際には決定に影響を及ぼさない。同様に、修正イベントｍでパケットドロップ期間を設定する際に、τＤ［ｍ−２］に、（既にτＤ［ｍ−１］に含まれているものに加えて）τＤ［ｍ］に対して追加的な寄与を与えさせる。その理由は、イベントｍ
【００８３】
【数３４】
0005676780.tif 000035
で観察されるキューの状態は、τＤ［ｍ−１］よりもτＤ［ｍ−２］に依存できるからである。実際、ドロップ期間τＤ［ｍ−１］によってトリガーされるパケット損失の影響を受ける発信元は、時間τＤ［ｍ］が設定されるまで、それらの損失に反応を開始してさえいなくてもよい。
【００８４】
ＰＥＤ構成
また、アルゴリズムを構成するのが簡単でなければ、パフォーマンスが優れていて、実装が複雑でなくても、ネットワーク装置において新しいアルゴリズムを広範に進展を強いることはできない。このセクションでは、ＰＥＤの運用を駆動する例示的な構成パラメータのセットを記載する。関連するパラメータの値に対して例示的な提言を提供するため、ＰＥＤの構成は簡単であり、一度リンク速度および利用可能なメモリの量が分かれば、完全に自動化することができる。理解されるように、例示的な構成パラメータは、本発明の実装の一実施形態のみを示すものであり、特定のネットワーク目的に依存して他のパラメータを選択することができる。
【００８５】
パラメータＱｍａｘは、利用可能な合計バッファスペースである。その値は、利用可能なバッファメモリのサイズなど、ハードウェアの設計制約によって設定される（たとえば、説明のためのトラフィックシナリオのバッファメモリのオンチップ実装についてＱｍａｘ＝３２ＭＢ。そのシミュレーション結果は、図６、図７、図８、および図９に示している）。
【００８６】
パラメータ
【００８７】
【数３５】
0005676780.tif 000036
は、最小ＰＥＤしきい値である。これは、利用可能な合計バッファスペースの固定された一部（たとえば２０％）として設定するべきである（たとえば、例では
【００８８】
【数３６】
0005676780.tif 000037
）。
【００８９】
パラメータ
【００９０】
【数３７】
0005676780.tif 000038
は、最大ＰＥＤしきい値である。これは、最小ＰＥＤしきい値の２倍の大きさであるべきである（しかし、
【００９１】
【数３８】
0005676780.tif 000039
より高い他の値は禁止されていない）：
【００９２】
【数３９】
0005676780.tif 000040
（たとえば、例では
【００９３】
【数４０】
0005676780.tif 000041
）。
【００９４】
パラメータ
【００９５】
【数４１】
0005676780.tif 000042
は、安全ＰＥＤしきい値である。これは、最小ＰＥＤしきい値の３倍の大きさであるべきである（しかし、最大ＰＥＤしきい値より高い他の値は禁止されていない）：
【００９６】
【数４２】
0005676780.tif 000043
（たとえば、
【００９７】
【数４３】
0005676780.tif 000044
）。
【００９８】
パラメータ
【００９９】
【数４４】
0005676780.tif 000045
は、ゲートＰＥＤしきい値である。ＡＱＬがこのしきい値を下回っている限り、パケットはドロップされない。これは、
【０１００】
【数４５】
0005676780.tif 000046
の半分のサイズであるべきである
（たとえば、
【０１０１】
【数４６】
0005676780.tif 000047
）。
【０１０２】
パラメータτｑは、ＡＱＬの更新期間である。同じパケットがキューから外に伝送中は、
【０１０３】
【数４７】
0005676780.tif 000048
の複数の更新を回避するために、十分な大きさがあるべきである（たとえば、τｑ＝１０μｓ）。
【０１０４】
パラメータＴは、ボトルネックリンクならびにそのパケットがリンクを横断する１セットのＴＣＰ送信側および受信側で構成される制御システムの時定数である。また、これは、
【０１０５】
【数４８】
0005676780.tif 000049
の計算を実装するローパスフィルタの遮断周波数の逆数である。ほとんどのＴＣＰ接続のＲＴＴ値が含まれることを確実にするために、特にそれらの実際の分布が分からない場合は、Ｔの値は、５００ｍｓに設定するべきである。ＲＴＴ分布が、明確により小さな値の前後に集中していることが分かっている場合は、より低い値は禁止されない。
【０１０６】
パラメータｗは、ＥＷＭＡとしてＡＱＬの計算に使用される重みである。その値は、平均期間τｑおよび時定数Ｔ：ｗ＝τｑ／Ｔ（たとえば、ｗ＝０．００００２）に対して選択された値から直接的に得られる。
【０１０７】
パラメータ
【０１０８】
【数４９】
0005676780.tif 000050
は、ＰＥＤドロップ期間τＤに対して認められた最小値である。これは、平均期間τｑと少なくとも同じ大きさであるべきである（たとえば
【０１０９】
【数５０】
0005676780.tif 000051
）。
【０１１０】
パラメータ
【０１１１】
【数５１】
0005676780.tif 000052
は、ＰＥＤドロップ期間τＤに対して認められた最大値である。これは、
【０１１２】
【数５２】
0005676780.tif 000053
の推定値より大きいが、Ｔより大きさであるべきではない（たとえば
【０１１３】
【数５３】
0005676780.tif 000054
）。
【０１１４】
パラメータＫは、パケットドロップ期間τＤを更新するために使用される固定された修正要素である（たとえばＫ＝２。値が大きいほど、制御ループはより高速になるが安定性がより低下する）。
【０１１５】
既に説明したように、例示的な構成パラメータは、本発明の例示的な一実施形態を反映している。当業者なら、他のパラメータおよびパラメータ値を選択できることを認識されるだろう。
【０１１６】
ＰＥＤ運用
以下の変数は、ＰＥＤの運用に関係している。
【０１１７】
変数ｑはＩＱＬである。これは、バイトまたはメモリワードなど、パケットまたはサブパケットのデータ単位で測定することができる。
【０１１８】
変数
【０１１９】
【数５４】
0005676780.tif 000055
は、時間ｎτｑと（ｎ＋１）τｑとの間のＡＱＬである。ここで、ｎは整数である。これは変数ｑと同じ単位で測定される。
【０１２０】
変数τＤは、ＰＥＤドロップ期間であり、その継続時間は、
【０１２１】
【数５５】
0005676780.tif 000056
の進展によって制御される。
【０１２２】
アルゴリズムの例示的な実施形態を実行するための補助変数は、ＰＥＤドロップ期間の最新更新の時間ｔＵ、キューが最後に空になった時間ｔＺ、ＰＥＤが最後にパケットをドロップする決定を下した時間ｔＤ、および次の着信パケットをドロップするべきかどうかを示すドロップフラグｆＤを含む。
【０１２３】
図４は、ＰＥＤ方式におけるしきい値の使用を要約している。図の各部分において、キューの長さの線の実線部分は、記載されたアクションが適用される基準測定（ＩＱＬまたはＡＱＬ）の値の範囲を示している。それぞれのしきい値と測定の比較は、各部分に対して記載されたイベントによってトリガーされる。パケット着信イベント１０について示すように、ＩＱＬ  ｑがしきい値Ｑｍａｘを超えると、２つのアクションが取られる。これらのアクションは、着信パケットをドロップすることと、ＰＥＤ期間をその最小にリセットすることである。次のアクションは、ＰＥＤドロップタイマー２０の期限切れである。ＩＱＬが最小ＰＥＤしきい値
【０１２４】
【数５６】
0005676780.tif 000057
に達し、かつＡＱＬがＰＥＤゲートしきい値
【０１２５】
【数５７】
0005676780.tif 000058
に達すると、ドロップフラグが設定される。次のイベント、ＰＥＤドロップタイマーの期限切れ、および時定数３０にて、最小ＰＥＤしきい値
【０１２６】
【数５８】
0005676780.tif 000059
に達していない場合、ＰＥＤ期間が増加する。この同じイベント、ＰＥＤドロップタイマーの期限切れ、および４０に示される時定数について、ＡＱＬについて最大ＰＥＤしきい値
【０１２７】
【数５９】
0005676780.tif 000060
に達している場合、ＰＥＤ期間が減らされる。５０に示すように、時定数の期限切れで、ＡＱＬが、ＰＥＤ安全しきい値
【０１２８】
【数６０】
0005676780.tif 000061
を超えている場合、ＰＥＤドロップフラグが設定され、ＰＥＤ期間が減らされる。
【０１２９】
ここで図１０ａを参照すると、本発明による全体的なＰＥＤ方法を実装するための流れ図１００が示されている。フローは開始点Ａ１０２から始まる。次に、第１のステップ１０４で、決定ボックスに達し、ＡＱＬタイマーの期限が切れたかどうかが決定される。期限が切れていない場合、フローは移行点Ｂ１０６に移る。ＡＱＬの期限が切れている場合、ステップ１０７にフローは移り、ＡＱＬ値が更新される。ステップ１０８で、ＡＱＬタイマーがリセットされ、フローは決定ボックス１１０に移り、ＡＱＬタイマーが安全しきい値より大きいかどうかが決定される。安全しきい値より大きい場合、フローは他の決定ボックス１１２に移り、時定数の期限が切れているかどうかが決定される。期限が切れている場合、フローはステップ１１４に移り、ドロップフラグが設定される。決定ボックス１１０または１１２のどちらかが「いいえ」という結論に達した場合、フローは移行ステップＢ１０６に移る。ステップ１１４でドロップフラグが設定された後、フローはステップ１１６に移り、ドロップ期間が更新される。ドロップタイマーは、次にステップ１１８でリセットされ、アルゴリズムは、移行ステップＢ１０６に移る。
【０１３０】
図１０ｂを参照すると、本発明の方法のフローが継続している。移行ステップＢ１０６の後に、決定ボックス１２０に達し、ドロップ期間の期限が切れたかどうかが決定される。期限が切れていない場合、フローは移行ステップＣ１２２に移る。ドロップ期間の期限が切れている場合、ＡＱＬがゲートしきい値
【０１３１】
【数６１】
0005676780.tif 000062
より大きいかどうかを決定するために、決定ボックス１２４でチェックが実行される。「はい」という決定に達した場合、フローは次の決定ボックス１２６に移り、ＩＱＬ値が最小しきい値より大きいかどうかが決定される。ＩＱＬ値が最小しきい値より大きい場合、ステップ１２８でドロップフラグが設定される。決定ボックス１２４または１２６のどちらかが「いいえ」という決定である場合、フローはステップ１３０に直接的に移り、ドロップタイマーがリセットされる。
【０１３２】
ステップ１２８でドロップフラグが設定された後、次の決定ボックス１３２に達し、時定数の期限が切れているかどうかが決定される。時定数の期限が切れている場合、次の決定ボックス１３４に移り、時定数に等しい継続時間の最後の時間間隔内に、ＩＱＬがヌルだったかどうかが決定される。時定数に等しい継続時間の最後の時間間隔内に、ＩＱＬがヌルでなかった場合、ステップ１３６でドロップ期間が更新される。決定ボックス１３２が「いいえ」という決定であるか、または決定ボックス１３４が「はい」という決定である場合、フローはステップ１３０に直接に移り、ドロップタイマーがリセットされる。ドロップタイマーがリセットされた後、アルゴリズムフローは移行ステップＣ１２２に移る。
【０１３３】
移行点Ｃの後に、決定ボックス１３８に達し、新しいパケットが到着したかどうかが決定される。到着していない場合、フローは、再び開始点Ａ１１２に移る。新しいパケットが到着している場合、決定ボックス１４０でドロップフラグが設定されているかどうかが決定される。ドロップフラグが設定されている場合、ステップ１４２でパケットはマークされ、ステップ１４４でドロップフラグはリセットされる。次に、フローは開始点Ａ１１２に移る。決定ボックス１４０で「いいえ」という決定に達し、ドロップフラグが設定されていない場合、決定ボックス１４６に移り、バッファがいっぱいかどうかに関して決定される。バッファがいっぱいの場合、決定ボックス１４８でＡＱＬがゲートしきい値より大きいかどうかを確かめるためにチェックが行われる。ＡＱＬがゲートしきい値より大きい場合、ステップ１５０でドロップ期間が最小値に設定される。次に、ステップ１５２でドロップタイマーがリセットされ、フローは開始点Ａ１１２に移る。決定ボックス１４６または１４８のどちらかが「いいえ」という決定である場合、フローは開始点Ａ１１２に直接的に移る。
【０１３４】
ＰＥＤパフォーマンス
図５を参照すると、例示的なネットワークトポロジ２００が示されており、ソースアグリゲーションノード（ＳＡＮ）２０２、ボトルネックノード（ＢＮＮ）２０４、およびシンク分布ノード（ＳＤＮ）２０６が含まれている。本発明の定期的な早期廃棄方法のリンク利用度パフォーマンスを検討するために、ネットワークシミュレータプラットフォームが使用される。Ｎ個のＴＣＰ  Ｒｅｎｏ発信元２０８は、それぞれの１Ｇｂｐｓリンク２１０によってＳＡＮに付けられる。これらのリンクのそれぞれの伝播遅延によって、それぞれのＴＣＰフローのＲＴＴが設定される。他のすべてのリンクの伝播遅延は無視できる。ＴＣＰシンク２１１は、１Ｇｂｐｓリンク２１２によってもＳＤＮに付けられる。その容量が４０Ｇｂｐｓより低い、ＢＮＮからＳＤＮまでのボトルネックリンク２１４を除いて、ネットワークノードの間のすべてのリンクは４０Ｇｂｐｓの容量を持っている（異なる実験ではボトルネック速度に異なる値を設定した）。ボトルネックキューで利用可能な合計バッファスペースは３２ＭＢであり、十分にオンチップバッファ実装の範囲内である。以前得られた例示的な値を持つＰＥＤパラメータを次のように構成する：
τｑ＝１０μｓ、Ｔ＝５００ｍｓ、
【０１３５】
【数６２】
0005676780.tif 000063
、
【０１３６】
【数６３】
0005676780.tif 000064
、
【０１３７】
【数６４】
0005676780.tif 000065
、
【０１３８】
【数６５】
0005676780.tif 000066
、Ｑｍａｘ＝３２ＭＢ、
【０１３９】
【数６６】
0005676780.tif 000067
、および
【０１４０】
【数６７】
0005676780.tif 000068
。
【０１４１】
下記のようにシナリオ１および２のトラフィック設定で、図５のネットワーク構成のシミュレーションによってＰＥＤのパフォーマンスを検討する。提示する結果は、説明する予定の主な結果に例外を見つけることができない、はるかに多くのセットから選択されている。シナリオ１には、Ｎ＝１００のＴＣＰフローがあり、すべて
【０１４２】
【数６８】
0005676780.tif 000069
である。フローの数およびＲＴＴ値は、どちらも比較的大きく、パケット損失を適切に分散する早期廃棄アルゴリズムの能力に挑むものである。ＲＴＴは、すべてのフローで同じなので、通常のＴＣＰ変化によって引き起こされるキューの長さの大きな振動が観察されることを期待する。パケットがあまりドロップされなければ、キューは容易にオーバーフローするだろう。パケットが頻繁にドロップされすぎると、グローバルな同期が発生するだろう。シナリオ２において、ファントムドロップ率の見積もりで早期廃棄方式の精度を強調するために、ＴＣＰフロー数をＮ＝１００に減数し（単一のパケットドロップイベントは、全体的なトラフィック負荷にかなり大きな影響を及ぼす）、ＴＣＰフローへのパケット損失の次善の割り当てに対して、この方式の堅牢性をテストするために、１０ｍｓと２９０ｍｓ（
【０１４３】
【数６９】
0005676780.tif 000070
）との間でＲＴＴ値を一様に分布する。
【０１４４】
シナリオ１で、第１の例示的なシミュレーション実験を実行する。図６では、ボトルネック速度が３２Ｇｂｐｓであるときに、３０ｓ間隔を通じてＡＱＬおよびＩＱＬの進展をプロットする。測定されたリンク利用度は１００％である。グラフは、ＩＱＬおよびＡＱＬの両方が自然に経験する振動にかかわらず、キューの長期的な安定性を保つ際に、安定したパケットドロップ期間（２０ｍｓ前後で小さく変動するのを観察）の重要な役割を明白に強調している。
【０１４５】
図６との比較のために、図７に、［Ｆｌｏｙｄ、２００１］で推薦された構成パラメータを用いて、ボトルネックキューでＡＲＥＤ方式が利用されるときのＡＱＬおよびＩＱＬの進展をプロットする。プロットで対象とする１００ｓの期間を通じて、リンク利用度７９．６％を測定する。最大ドロップ確率ｐｍａｘは、全期間の間に最小許容値（０．０１）から離れない。図７は、グローバルな同期条件の定期的な発生によるリンク利用度の損失について説明している。パケット損失は常にＡＲＥＤ決定の結果であり、決してバッファオーバーフローの結果ではないことに留意する（ＩＱＬは、常にＱｍａｘ＝３２ＭＢをはるかに下回る）。図８のより細かい時間詳細度を参照して、グローバル同期、したがって早期検出アルゴリズムの不安定さを引き起こすのは、ＡＲＥＤ（より一般的にはＲＥＤ）のパケットドロップ確率関数の単調な性質であるという特筆すべき証拠を見つける。図８では、ＩＱＬは、時間ｔｐ＝８４８．７７前後でピークになる。そのときまでに、グローバル同期イベントの条件は、過度のパケット損失によって既に設定されていた。ＩＱＬは、ｔｐの後すぐに０に落ちるため、過度の損失がｔｐの前に発生したことを知っている。これは、長期間にわたり保持されると、キューの長さを安定させることができる値でパケットドロップ確率がファントムドロップ率に一致する平衡時間ｔｅ＜ｔｐがあることを意味する。ｔｅの実際の配置は、議論には関係ない：重要なのは、ＩＱＬが落ち始める前に、平衡低下確率が確実に満たされることだけである。ＡＱＬを計算するローパスフィルタの遮断周波数に依存する遅延によって、ＩＱＬが増加しているときに、パケットドロップ決定を促進するためにＡＲＥＤが使用するＡＱＬは、系統的にＩＱＬを追跡する（プロットでは、ＡＱＬは５００ｍｓ未満でＩＱＬを追跡する）。ＡＱＬは、ＩＱＬより小さい限り、平衡時間ｔｅの後（およびｔｐの後でも）上昇し続ける。ＡＱＬが増え続けると、パケットドロップ確率も、ドロップ確率関数の単調な増加プロファイルの影響によって上昇する。このように、パケットドロップ確率は、ｔｐを超えて進展する時間、平衡値を上回る状態のままになる。ファントムドロップ率だけ平衡に必要な損失を超えて、ｔｅとｔｐとの間に発生するパケット損失は、グローバル同期イベントの発生の原因となるものである。図７および図８に示す振る舞いは、任意のＲＥＤの実施形態では、平衡状態に達した後に平衡状態にロックできないために引き起こされる。これは、最後にはドロップ確率関数の狭義に増加する性質から得られる。代わりに、本発明のＰＥＤ方式は、見積もりが、２つのしきい値
【０１４６】
【数７０】
0005676780.tif 000071
および
【０１４７】
【数７１】
0005676780.tif 000072
によって定められた範囲内にＡＱＬを維持できることが証明される限り、ファントムドロップ率の近い見積もりを保持する。
【０１４８】
シナリオ２で、第２の例示的な実験を実行する。図９では、ボトルネック速度が３６Ｇｂｐｓであるときに、１０ｓ間隔を超えてＡＱＬおよびＩＱＬの進展をプロットする。測定されたリンク利用度は９９．９４７％である。シナリオ１（図６）と比較して、ＩＱＬ振動の幅は増加するが、ＰＥＤは、何とかリンク利用度を１００％近くに維持している。安定した状態では、ＰＥＤドロップ期間は、最大許容値５００ｍｓで永久に安定することを認めることは重要である。これは、より広い範囲を利用できた場合は、ＰＥＤ制御ループは値を上昇させる可能性があることを示している。しかし、次のパケットドロップイベント間の適切な時間分離が、ゲートしきい値
【０１４９】
【数７２】
0005676780.tif 000073
とのＡＱＬの比較を通じたパケットドロップ決定のゲートによって、まだ実施されるため、最大ＰＥＤドロップ期間に対する値の制限によって、スループットパフォーマンスは損なわれない。
【０１５０】
ここで、本発明のＰＥＤ方法と、他の従来技術方法との違い、およびそれらの違いの一部の目的について説明する。
【０１５１】
１．オリジナルのＲＥＤおよびＡＲＥＤとは対照的に、ＰＥＤのＡＱＬの保守は、イベント駆動ではなく時間駆動のプロセスである。ＡＱＬは、パケットが到着するときではなく、固定された時間に更新される。こうすることで、ＡＱＬ値を規定するＥＷＭＡの重みと、ＥＷＭＡによってインスタンス化されるローパスフィルタの遮断周波数との間に決定関係を築くことが可能である。これにより、ＲＴＴ時間的尺度内に限定されたＴＣＰ変化が、ドロップ期間τＰＥＤの制御に不適切に影響することが防止される。また、これによってＥＷＭＡ重みｗの構成が簡単になる（ＲＴＴ分布が分からない場合は固定することができる。または、その分布の妥当な推定を利用できる場合は、ＲＴＴ分布に合わせることができる）。
【０１５２】
２．長命のボトルネックとなるＴＣＰ接続を用いるキューでは、パケットドロップ頻度が輻輳回避状態にある発信元のトラフィック生成速度の増加の平衡を保つ場合、安定が達成される。長命の接続の数Ｎごとに、およびそれらのＲＴＴ値のすべての分布ごとに、理想的なパケットドロップ頻度φ（ｔ）があるため、発信元活動において結果として生じる減少は、パケット損失によって影響されない発信元の発信元活動における増加に正確に一致する。より困難な定量化の複数の要因が決定に寄与するため（たとえば、次のパケットドロップによる影響を受ける接続は常に異なるか、または接続ごとに複数のドロップが短期間に発生するかなど）、頻度の正確な値は、実用システムで解析的に取得するのが難しい。しかし、なお、そのような値は、任意のときにシステムの任意の可能な状態に対して存在すると想定することができる。その値の推定における誤差が妥当な範囲内にあるとき、キューの安定が特定の時間にわたり保証される場合、パケットドロップ頻度が、制限された許容誤差内にある理想的な参照値を追跡している限り、混雑した時間の大部分において、そのような不完全な平衡にキューを維持することが可能である。ＰＥＤでは、見積もった頻度値が識別されると、ドロップタイマーの期限切れによって決定論的に実施される。ＲＥＤおよびＡＲＥＤでは、代わりに、今までどおり、目標ドロップ確率によって設定された平均頻度値の前後に広い変動を観察することができる。また、すべての着信パケットに、異なるＡＱＬ、したがって異なるドロップ確率が見つかるため、制御の不正確さがさらに増す可能性がある。
【０１５３】
３．制御理論の言い方では、ＲＥＤおよびＡＲＥＤは、ドロップ確率を制御するためにＡＱＬを使用するため、キューの平衡を保つために必要なドロップ頻度の各値は、最初にドロップ確率値に変換されて、次にＡＱＬの特定の値に変換される。必要なドロップ頻度が高いほど、平衡を確立するＡＱＬは高くなる（ＡＲＥＤは、ＲＥＤを通じて、少なくとも名目上、現在のトラフィック状況に基づいてドロップ確率値の範囲を調整することによって改善する）。ＰＥＤ方式は、代わりに、ドロップ頻度とＡＱＬを別々に制御し、異なるドロップ頻度を同じＡＱＬ（および対応する平均的なキュー遅延）で実施することができる。
【０１５４】
４．ＲＥＤおよびＡＲＥＤは、バッファ占有しきい値とのＡＱＬの比較の後にパケットをドロップする。ＰＥＤは、ＩＱＬを代わりに比較する。ＡＱＬ（ＰＥＤではドロップ期間τＰＥＤの制御に継続的に役立つ）を使用しない理由は、ＡＱＬは、ＴＣＰ発信元活動の制御に、Ｔ（したがって
【０１５５】
【数７３】
0005676780.tif 000074
）と同等の遅延コンポーネントを加えるからである。パケット損失イベントを検出するためにＴＣＰ発信元によって使用されるタイムアウトのために、
【０１５６】
【数７４】
0005676780.tif 000075
と同等の遅延が既に存在する。結果として、一部のＴＣＰ発信元が、既に前のパケット損失に対応するプロセスにある可能性があることを考慮することなくパケットドロップ決定が行われる。これは、パケットドロップ決定の不正確さの原因の１つである。ＡＱＬに基づいてパケットドロップ決定を行うことで（これにより遅延ＴだけＩＱＬの進展が遅れる）、ボトルネックキューでパケット損失を使用して、ＴＣＰ発信元の活動を規制する制御ループの合計遅延時間に時間Ｔが加えられる。その結果、ＲＥＤおよびＡＲＥＤにおいて、パケットドロップ決定の不正確さがさらに増す。
【０１５７】
５．キューが空になり、ＰＥＤ方式が空き状態の原因として除外される場合、ＰＥＤ方式は、ドロップ期間τＰＥＤを制御するアルゴリズムをサスペンドする。システムパラメータ（長命のＴＣＰ接続の数ＮおよびそれぞれのＲＴＴ値の分布）に依存して、発信元活動の休止の後に、キューに輻輳が再び発生するのには長い時間がかかる場合がある。ＰＥＤ方式には、この低負荷の時間区分の期間を規定する際に役割がないため、この間にドロップ期間τＰＥＤを変更するべきでない。
【０１５８】
６．ＰＥＤ方式では、ＡＱＬがゲートしきい値を超えることができる前にキューがオーバーフローしたときに、ドロップ期間τＰＥＤを最小許容値
【０１５９】
【数７５】
0005676780.tif 000076
にリセットする。そのようなオーバーフローイベントが示すのは、おそらくドロップ期間τＰＥＤが高すぎ、ＡＱＬがまだ低いために、ＰＥＤ方式には、キュー占有において高速な振動を平滑化する際に役割がなかったことである。長期間の低負荷と短命のオーバーフローイベントとの間の振動は、この状態を終えるのに好都合ではない。したがって、理想的なパケットドロップ頻度に近い範囲に再びロックするために制御アルゴリズムにとって新しい機会を作り出すために、ＰＥＤ方式は、可能な限り高いドロップ頻度の状態に戻ることを強制し、これにより、次のオーバーフローイベントを回避する可能性が最も高くなる。
【０１６０】
７．ＰＥＤ方式は、また、ＡＱＬが安全しきい値
【０１６１】
【数７６】
0005676780.tif 000077
を超えたときに、ドロップ間隔の早期割込みおよびドロップ期間τＰＥＤの下方修正を許可する。これは、ＡＱＬは高いが、ＩＱＬ増加を適切に抑制できるようにするにはドロップ期間τＰＥＤがまだ高すぎるときに、バッファオーバーフローイベントを回避するのを支援するためである。
【０１６２】
図１１を参照すると、本発明の方法を実装できる通信ノード３００の例示的な一実施形態が示されている。見られるように、ノード３００は、システムメモリ３０４（たとえば、任意の形式のランダムアクセスメモリ（ＲＡＭ）および読み出し専用メモリ（ＲＯＭ））に結合された少なくとも１つのプロセッサ３０２を含む。通信ノードは、また、複数の入力ポートおよび出力ポート３０５、３０６を含む。１つまたは複数のメモリバッファ３０８は、通信ノード３００で受信され、伝送される通信トラフィックをバッファリングするために利用される。理解されるように、プロセッサは、通信ノードで規定された機能を実行するためにメモリに格納されているプログラムコードを実行する。本発明の記述された方法を実行するためのプログラムコードは、システムメモリ３０４に格納し、プロセッサ３０２によって実行することができる。
【０１６３】
結論
ネットワークリンクにおいて伝送レートは常に増加を続けるため、パケットバッファメモリのオンチップ実装は、次世代ルータおよびスイッチの拡張およびエネルギー効率のための主な必要条件である。テールドロップおよびＲＥＤなど既存のバッファ管理手法では、一般的なトラフィックシナリオでＴＣＰ発信元のグローバル同期を回避できないため、必要なバッファスペースの削減ができない。ＲＥＤは、また、トラフィックミックスに関係なく最高のパフォーマンスを保証する構成戦略が不足している。
【０１６４】
ＲＥＤの欠点の主な理由は、キューの長さからパケットドロップイベントの頻度を導き出す制御法則の単調で減少しない特徴であるという強力な証拠を提供してきた。したがって、ＲＴＴ時間的尺度で調整されるレベルで制御法則が平坦である、新しい定期的な早期廃棄（ＰＥＤ）方式を規定した。現在の設計で使用されるメモリ容量の３％未満で、安定した状態で長命のＴＣＰフローで１００％のリンク利用度を一貫して実施するＰＥＤの機能を主張するシミュレーション結果を収集した。
【０１６５】
前記説明は、本発明の原理を説明しているに過ぎない。本明細書に明示的に記述または図示していないが、本発明の原理を具体化し、その趣旨および範囲に含まれるさまざまな配置を当業者であれば考案できることを理解されるだろう。さらに、列挙したすべての実施例および条件の言い回し（ｃｏｎｄｉｔｉｏｎａｌ  ｌａｎｇｕａｇｅ）は、原則として、読者が本発明の原理、およびその技術を推進する発明者によって提供された概念を理解するのを支援するために、教育のみを目的とすることを明確に意図するものであり、そのような具体的に詳述された実施例および条件に限定しないものとして解釈するべきである。さらに、本明細書において、本発明の原理、態様、および実施形態を詳述するすべての記述、およびその特定の例は、その構造的および機能的な均等物の両方を包含することを意図するものである。さらに、そのような均等物は、現在知られている均等物と、将来的に開発される均等物（つまり、構造に関係なく、同じ機能を実行する、開発される任意の要素）の両方を含むことを意図するものである。本発明の原理の他の多くの変更および応用が、当業者に明白になり、本明細書の教示によって考えられるだろう。したがって、本発明の範囲は、特許請求の範囲によってのみ限定される。
【図１】
0005676780.tif 000078
【図２】
0005676780.tif 000079
【図３】
0005676780.tif 000080
【図４】
0005676780.tif 000081
【図５】
0005676780.tif 000082
【図６】
0005676780.tif 000083
【図７】
0005676780.tif 000084
【図８】
0005676780.tif 000085
【図９】
0005676780.tif 000086
【図１０Ａ】
0005676780.tif 000087
【図１０Ｂ】
0005676780.tif 000088
【図１０Ｃ】
0005676780.tif 000089
【図１１】
0005676780.tif 000090