(57)【要約】  ネットワークの輻輳を削減するための、スケーラブル・キュー・サイズおよび１方向キューイング遅延測定を含む、遅延ベース・スキームである輻輳制御スキームを、本発明は提供する。キュー・サイズは、キュー制御、スケーラブル効用関数、ダイナミック・アルファ・チューニング、および／またはランダム化アルファ・チューニングにより管理される。１方向キューイング遅延は、受信器クロック期間を推定する種々の方法を用いて、復路キューイング遅延マネジメントを測定することにより、達成される。単一サンプルおよび多数サンプル・期間を用いて、受信器クロック期間を推定することを、実施形態は含んでいる。このシステムは、ルート・チェンジを検出する方法を含んでいる。
2008511205.tif 000002
【特許請求の範囲】
【請求項１】
最小キューイング遅延ｑ0を決定し、
前記最小キューイング遅延ｑ0を含む平衡条件を決め、
前記平衡条件を満足するα値を選択する、
ネットワークにおける輻輳を制御する方法。
【請求項２】
前記ネットワークがＴＣＰネットワークである請求項１に記載の方法。
【請求項３】
前記輻輳制御が、遅延ベースＴＣＰ輻輳制御スキームである請求項２に記載の方法。
【請求項４】
ｑ＝ｑ0＋Ｎα／ｃであり、
ここで、Ｎは前記ネットワーク上のトラヒック・フローの数であり、ｑは前記ネットワークにおける遅延であり、ｃは前記ネットワークの容量である請求項１に記載の方法。
【請求項５】
ネットワークにおけるパケット・ロスを検出し、
前記パケット・ロスが、ある閾値を超えたかどうかを判定し、
前記パケット・ロスが、前記閾値を超えていない場合は、あるα値を増加し、
前記パケット・ロスが、前記閾値を超えた場合は、前記α値を削減する、
ネットワークにおける輻輳を制御する方法。
【請求項６】
前記α値が加算的に増加され、乗算的に削減される請求項５に記載の方法。
【請求項７】
前記閾値が輻輳ロスを表す請求項５に記載の方法。
【請求項８】
前記閾値が８以上である請求項５に記載の方法。
【請求項９】
ネットワークのスループットを決定し、
ある現在のα値が、前記スループットと関連しているかどうかを判定し、
前記現在のα値が、前記スループットと対応していない場合には、前記α値を歩進する、ネットワークにおける輻輳を制御する方法。
【請求項１０】
複数の可能なα値から、ランダムにあるα値を割り当てるステップをさらに含む請求項９に記載の方法。
【請求項１１】
前記ランダムに前記α値を割り当てる前記ステップが、ある予め定められた期間の後に起こる請求項１０に記載の方法。
【請求項１２】
あるネットワーク上を送信される、あるメッセージの往路キューイング遅延（ＦＱＤ）を決定し、
ＦＱＤを使用して、前記ネットワークの前記キューイング遅延を調整する、
ネットワークにおける輻輳を制御する方法。
【請求項１３】
前記往路遅延を決定する前記ステップが、
１往復時間（ＲＴＴ）遅延を決定し、
復路キューイング遅延（ＢＱＤ）を決定し、
ＦＱＤを決定するために、ＲＴＴからＢＱＤを減算することを含む請求項１２に記載の方法。
【請求項１４】
ＢＱＤを決定することが、
受信器クロック期間ｐ2を決定し、
受信器クロックにおける変化後の、受領確認（ＡＣＫ）をサンプリングし、
ｐ2とＡＣＫに基づいて、ＢＱＤを計算することを含む請求項１３に記載の方法。
【請求項１５】
ある効用関数ｕ（ｘ）と、データ・フローの数Ｎとを含むバックログ平衡条件を決め、
Ｎが増加するにつれて、前記バックログがあるより低いレートで増加するように、ｕ（ｘ）を決める、
ネットワークにおける輻輳を制御する方法。
【請求項１６】
ｕ（ｘ）が、ある調整可能な定数βにより修正される請求項１５に記載の方法。
【請求項１７】
【数１】
2008511205.tif 000055
であり、ここで
【数２】
2008511205.tif 000056
はピーク・レートである請求項１６に記載の方法。
【請求項１８】
【数３】
2008511205.tif 000057
であるように、最小キューイング遅延ｑ0をさらに含む請求項１７に記載の方法。
【請求項１９】
平衡ロス確率ｐを計算し、
平衡キューイング遅延ｑを計算し、
ある予め定められたターゲット値に向けて、ｐとｑの関数を駆動する、
ネットワークにおける輻輳を制御する方法。
【請求項２０】
ｐを計算することが、あるインターバルＳにおける失われたパケットの数を、期間Ｓの間に送信されるパケットの全数により除算することを含む請求項１９に記載の方法。
【請求項２１】
ｐとｑを等しくすることが、比ｑ／ｐを、あるα値を更新することにより、ある値Ｋに向かって駆動することにより達成される請求項１９に記載の方法。
【請求項２２】
前記α値を更新することが、
ｐtとｑtを計算し、
あるλt値＝ｑt／ｐt／Ｋを生成し、
ある値ηt＝ｆ（η(t-1)，λt）を計算し、
新しいα値＝ηt＊α0を生成することにより達成される請求項２１に記載の方法。
【請求項２３】
ある値をΔαだけ歩進し、
前記ある値の歩進後に、往復時間における変化（ΔＲＴＴ）を決定し、
前記ΔＲＴＴ／Δαがゼロに接近する場合の発生として、あるルート・チェンジを決めることを含む、
ネットワークにおけるルート・チェンジを検出する方法。
【発明の詳細な説明】
【関連出願】
【０００１】
（関連出願の相互引用）
本出願は、２００４年８月３０日に、「遅延ベースＴＣＰを改良する方法」と題して出願されて係属中の、ここにその全部を参照により引用する、米国仮出願第６０／６０５，４５８号、および２００４年８月１９日に、「高速ＴＣＰキュー制御」と題して出願されて係属中の、ここにその全部を参照により引用する、米国仮出願第６０／６０２，９８７号、および２００４年８月１７日に、「ＴＣＰ／ＩＰネットワークの１方向遅延変化を測定する方法」と題して出願されて係属中の、ここにその全部を参照により引用する、米国仮出願第６０／６０２，１１１号、に基づく優先権を主張する。
【技術分野】
【０００２】
本発明は、ネットワークの分野に関し、輻輳制御のための方法と装置に関する。
【０００３】
本明細書の開示のいくつかの部分は、著作権の保護の対象である内容を含んでいる。特許庁のファイルまたは記録に表れている、本特許書類または本特許開示の複製について、著作権者は誰に対しても問題にしないが、それ以外については、何であれ全ての権利を留保する。
【背景技術】
【０００４】
コンピュータ・ネットワークは、１つまたは複数のコンピュータの間の通信を可能にする。ネットワークは、ローカル・エリア・ネットワーク（ＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、ワイヤレス・ネットワーク、混合デバイス・ネットワーク、その他を含んでいる。ネットワークの効率的な利用の１つの限界は、メッセージの発信元と着信先の数、さらにはメッセージ・トラヒックの量が当該ネットワークが効率的に取り扱える数量以上である時の、ネットワークの輻輳である。従来技術では、そのような輻輳の問題は、輻輳制御を実装することで取り扱われる。
【０００５】
輻輳制御は、競合するユーザの間において、ネットワーク・リソースを共有するための分配アルゴリズムである。そのアルゴリズムは、リソースの利用可能性と競合するユーザの集合が、時間に対して予測不可能に変動し、かつ効率的な共有が望まれる場合に、使用される。これらの制約、すなわち予測不可能な需要と供給、および効率的なオペレーションは、従来技術ではフィードバック制御を用いて解決されてきた。「クローズド・ループ」制御としても知られるフィードバック制御は、最適の結果を提供するために、動的かつ一般的な、リアルタイムのシステムの調整を決定するための、いくつかの測定基準の使用に関連している。そのようなシステムは、フィードバックのない、いわゆる「オープン・ループ」制御システムとは区別される（例えば、食肉温度計を使用せずに七面鳥を料理することはオープン・ループであり、食肉温度計を使用することはクローズド・ループ・フィードバック・システムである）。
【０００６】
この従来技術のアプローチでは、トラヒック・ソースは、それらのパスにおける輻輳に応じて、それらのレートを動的に適合する。輻輳制御として、フィードバック制御を使用するネットワークの一例は、インターネットである（データ転送に関係する、発信元コンピュータと着信先コンピュータにおいて、転送制御プロトコル（ＴＣＰ）を使用する）。ここではインターネットを議論しているが、本出願が他のネットワークに同様に適用されることを、理解すべきである。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
「リノ」としても知られる、現在のＴＣＰにおける輻輳制御アルゴリズムは、１９８８年に開発され、それ以来いくつかの変更を経てきている。帯域幅遅延の結果が成長を続けるので、ＴＣＰリノは最終的に性能のボトルネックになる、と現在の研究は予測している。言いかえれば、ネットワーク（インターネット）が、より高い帯域幅と性能を提供し続けるにもかかわらず、輻輳を管理するために使用されるその制御システムがまさに、当該のネットワークの不充分な利用に導くのである。大きな帯域幅遅延の結果を伴うネットワークにおいて、以下の４つの困難が、ＴＣＰリノの性能低下の原因になっている。
【０００８】
１．パケット・レベルでは、１往復遅延時間（ＲＴＴ）当たりの、１パケットによる線形的増加が低すぎ、またロス・イベント当たりの乗法的削減が急激すぎる。現在のスキームは、パケット・トラヒックの制御に、この「緩やか加速／急激減速」を使用しているが、高帯域幅システムでは効率的でない。
【０００９】
２．フロー・レベルでは、大きい平均輻輳ウィンドウを維持することは、極度に小さい均衡ロス確率を必要とし、そのように小さいロス確率の維持は、従来技術のシステムでは実際的ではない。
【００１０】
３．パケット・レベルでは、ＴＣＰがバイナリ輻輳信号（パケット・ロス）を使用しているので、発振が不可避である。
【００１１】
４．フロー・レベルでは、そのダイナミクスは不安定で、パケット・ロス確率の正確な推定と、フロー・ダイナミクスの安定な設計によってのみ削減可能である、深刻な発振に導く。現在のシステムは、パケット・ロスの充分正確な推定ができない。
【課題を解決するための手段】
【００１２】
ネットワークの輻輳を削減するための、スケーラブル・キュー・サイズと１方向キューイング遅延測定を含む、遅延ベース・スキームである輻輳制御スキームを本発明は提供する。キュー・サイズは、キュー制御、スケーラブル効用関数、ダイナミック・アルファ・チューニング、ランダム化アルファ・チューニング、方程式ベース・アルファ・チューニングにより管理される。１方向キューイング遅延測定は、受信器クロック期間を推定する種々の方法を用いて、バックワード・キューイング遅延を測定することにより、達成される。実施態様は、単一サンプルと多数サンプル・期間を用いて、受信器クロック期間を推定することを含んでいる。このシステムは、ルート・チェンジを検出する方法を含んでいる。
【発明を実施するための最良の形態】
【００１３】
輻輳制御のための、方法と装置が記述される。以下の記述では、より徹底的な本発明の記述を提供するために、多くの詳細が記載される。しかしながら本発明が、これらの特定の詳細なしでも、実施されることが、当業者には明白であろう。また、本発明を不必要に不明瞭にしないように、周知の特徴は詳細には記述されていない。
【００１４】
本発明は遅延ベースのモデルであり、輻輳測定として、キューイング遅延を使用している。それにより、従来技術のロス・ベースのシステムに対して利点を有する。１つの利点は、キューイング遅延は、ロス確率より正確に推定できることである。これは、大きな帯域幅遅延の結果を伴うネットワークにおけるパケット・ロスが、ＴＣＰリノやその変形（確率が、１０の−７乗以下のオーダー）の下ではまれなイベントであり、また、ロス・サンプルがキューイング遅延サンプルより粗雑な情報しか提供しないことを、その理由とする。特に、遅延の測定は、ロス確率の測定と同様に、ノイズが多い。このように、本発明の他の利点は、各々のパケット・ロスの測定（パケットが失われたか否か）がノイズのフィルタリングについて１ビットの情報しか提供しないのに対して、キューイング遅延の各々の測定が多数ビットの情報を提供することである。方程式ベースの実装が、あるネットワークを目標の公正性と高い有用性を伴う定常状態に安定させることを容易にする。さらに、キューイング遅延のダイナミクスは、ネットワークの容量に関するスケーリングを提供する。これは、ネットワークの容量がスケールアップされるにつれて、安定性の維持を助ける。遅延ベースの１つのスキームは、２００４年６月１４日に出願され、「ネットワーク輻輳制御方法および装置」と題されて、本発明の出願人に譲渡され、その全部がここに引用により参照される、米国出願第１０／８６８，５６４号に記載されている。引用されかつ参照された、特許出願に記載された技術は、以下では「遅延ベースＴＣＰ」として言及される。
【００１５】
本発明は、バッファ・オーバーフロー条件と、キューイング遅延測定技術を指向する。最初に、バッファ・オーバーフロー条件が議論される。
【００１６】
以上に引用された出願に記載されているように、接続の状態の平衡を決定するために使用される１つのパラメーターはαである。平衡状態では各々の接続は、中間ルータ・バッファ内のαパケットの合計数を維持する。ある実施形態では、共有されていない高速リンクを、単一のフローが完全に利用するように、ノイズの多い遅延測定にうち勝つために、ギガビット・ネットワークには、αが２００に設定される。しかしながら、体積の大きい多数のフローが、あるリンクを共有しようと試みると、フローが平衡に達する前に、バッファのオーバーフローが起こることがある。Ｎ個のフローがあり、必要なバッファリングを提供するために、Ｎαの量のメモリが要求される。しかしながら、当該のネットワーク上で、利用可能なバッファ・メモリの量は、そのような必要性を満たすために、常に充分であるとは限らない。バッファ・サイズが不適切であれば、オーバーフローが発生し、パケット・ロスが結果となる。
【００１７】
本発明は、バッファの容量が小さすぎるか、またはフローの数が多すぎる場合の、バッファ・オーバーフローを指向する、多くの方法を提案している。それらの技術は、キュー制御、スケーラブル効用関数、ダイナミックαチューニング、ランダム化されたαチューニング、方程式ベースのアルファ・チューニングを含んでいる。
【００１８】
バッファ・リミットが変化する（および未知である可能性がある）ネットワークにおいて、遅延ベースＴＣＰフローが高い有用性を有し、パケット・ロスが殆ど発生しないことを、アルファ・チューニングは保証する。例えば、いくつかの局面では、多数の遅延ベースＴＣＰフローをサポートするために、充分なバッファリングを、ネットワークが有さないことがある。アルファ・チューニングなしでは、全ての遅延ベースＴＣＰフローが、連続的なパケット・ロスを起こす。各々の遅延ベースＴＣＰが、適切なアルファ値を選択し、ネットワークを平衡に達させることを、アルファ・チューニングは援助することができる。
【００１９】
キュー制御
平衡状態にあるパスにおいて、各々のボトルネック・ルータでキューされ、それ自身のパケットの合計であるパラメーターαを、遅延ベースＴＣＰが有している（あるフローのパスには、１つよりも多いボトルネック・ルータがあってもよい）。遅延ベースＴＣＰが、より小さいα値を使用する一方で、同時にノイズの多い遅延測定に対してローバストであることを、キュー制御技術は可能にする。数学的には、キューされるパケットの数は、以下の平衡条件により表わされる。
キューされるパケットの数＝ｘ・ｑ＝α
ここでｘは実行されるスループット、またｑは測定される１往復キューイング遅延である。したがって、値αは、平衡キューイング遅延ｑを決定する。実際には、結果となるキューイング遅延ｑが、遅延測定においてノイズ・レベルよりも上であるように、αは充分大きく選択されなければならない。例えば、ネットワーク上にあるシングル・フローが存在する場合には、キューイング遅延は少なくとも５ｍ秒であるように、発明者らはαを典型的には選択する。
【００２０】
しかしながら、同じネットワークを共有する、フローの数が大きい場合には、大きなαは問題を起こすことがある。αは、遅延ベースＴＣＰフローから、パケット・ロスを避けるため、パケットを収容するのに必要なバッファリングの最小量なので、ｉ＝１，２，．．．，Ｎで表わされるＮ個のフローがある場合には、パラメーターαiを用いて、全部のバッファリング要求は、
【００２１】
【数１】
2008511205.tif 000003
である。全てのフローが同じパラメーター値、すなわち全てのＩ＝１，．．．，Ｎに対して、αi＝αである特別な場合には、
【００２２】
【数２】
2008511205.tif 000004
である。
【００２３】
この式から、バッファリング要求が、Ｎと共にゆっくりと成長するように、小さいαが望まれる。
【００２４】
したがって、遅延測定におけるノイズに対するローバスト性のために、大きなαが必要とされる一方で、ネットワークのバッファリングの要求を最小化するために、小さなαが必要とされる、ジレンマが起こる。キュー制御は、これらの対立する目的を、調停する技術である。
【００２５】
キュー制御のある実施形態の記述では、全てのフローが同じパラメーター値、すなわち、全てのｉに対して、αj＝αであることを発明者らは仮定している。図１は、本発明のキュー制御スキームの実施形態を示すフロー図である。
【００２６】
本発明のある実施形態は、以上に記述された平衡条件を、以下のように修正する。
ｘ・（ｑ−ｑ0）＝α
ここでｑ0は、遅延測定における誤差に対してローバストであるために、各々の端と端の間のパスで維持することを希望する最小キューイング遅延（例えば、５ｍ秒）である（ステップ１０１）。各々の遅延ベースＴＣＰ接続は、ｑ0を超えて、αパケットに貢献する。最小の遅延ｑ0を含むことにより、バッファリング要求Ｎαが、Ｎと共にゆっくりと増大するように、αを小さく選択することができる。例えば、（５ｍ秒に対向するように）ギガビット・ネットワークに対してすら、０．５ｍ秒程度に小さいキューイング遅延を生成するように、αが選択される。これを明瞭に見るために、共通パラメーターαを伴う、Ｎ＝１フローにより共有される、容量ｃを有する単一のリンクに対しては、スループットｘ＝ｃ／Ｎであることに留意すべきである。したがって、以上に記述された、改訂された平衡条件から、キューイング遅延は、以下により与えられる。
測定されるキューイング遅延＝ｑ＝ｑ0＋Ｎα／ｃ（ステップ１０４）
【００２７】
ステップ１０２で小さいαを選択した場合（およびＮ＝１であっても）でも、最小遅延ｑ0を含むことにより、測定されるキューイング遅延ｑは、ノイズ・レベルに比較すると、まだ充分大きい。Ｎ個（エレファント）のフローがある場合には、バッファリングの合計量は、
ネットワーク・バッファリング要求＝Ｎｘｑ＝ｃｑ0＋Ｎα（ステップ１０３）
【００２８】
したがって、小さいαは、Ｎにおけるバッファリング要求の、ゆっくりとした成長に帰結する（ｃｑ0の０ではない最小バッファリング要求を受けることを犠牲にして）。
【００２９】
要約すると、フローの数Ｎに関わりなく、キューイング遅延が、少なくとも最小キューイング遅延ｑ0を常に含んでいることをステップ１０４から分かる。ｑ0を、例えば５ｍ秒に選択すると、一定の５ｍ秒（Ｎとは独立）のキューイング遅延に加えてＮαを、バッファが収容する必要がある。ｑ0は遅延の測定においてノイズには既に無関係なので、ステップ１０３から、Ｎにおけるバッファリング要求が充分ゆっくりとした成長を与える非常に小さい値に、αを選択することができる。このように、ネットワークにおいてある固定のバッファ・サイズが与えられると、このキュー制御技術は、コンカレント遅延ベースＴＣＰフローの、より大きい数を可能にする。ステップ１０５では、例えば、全部のリンクの利用度とパケット・ロスの不存在の観察により、選択されたαが、フローの数Ｎに対して適切なバッファ・サイズに帰結するかどうかが、決定される。そうであれば、ステップ１０７でキュー制御が実行される。そうでなければ、ステップ１０３で他のα値が選択される。
【００３０】
時間ｋにおける、キューイング遅延がｑkである場合には、１つの遅延ベースＴＣＰウィンドウ更新アルゴリズムは、以下である。
【００３１】
【数３】
2008511205.tif 000005
ここで、ｗk、ｗk+1は、それぞれ時間ｋ、ｋ＋１におけるウィンドウ・サイズ、またｄは、伝搬遅延またはベースＲＴＴである。適用されるキュー制御により、ウィンドウ更新アルゴリズムは、以下になる。
【００３２】
【数４】
2008511205.tif 000006
【００３３】
実際のベースＲＴＴ測定と比較して、ｑ0だけ持ち上げられた、修正ベースＲＴＴ測定を見る、各々の遅延ベースＴＣＰとして、新しい平衡が解釈されてもよい。ベースＲＴＴ測定における誤差を伴っても、遅延ベースＴＣＰアルゴリズムは、それでも効用最大化問題を解決する。
【００３４】
スケーラブル効用関数
遅延ベースＴＣＰの効用関数をキュー制御が修正する観察を、第２の技術は一般化する。任意の複数のαの値に対するあるリンク上の、パスの数Ｎを伴うバッファ要求の成長を、制御するまたはゆっくりにさせることに帰着するために、この実施形態は効用関数を修正する。以下の平衡条件を考察する。
ｑ＝ｕ（ｘ）
ここで、ｕ（ｘ）は、限界効用関数である。したがって、容量ｃ＝Ｎｘの単一のリンクを共有する同一のＮ個のフローに対する平衡バックログは、
Ｂ（Ｎ）＝Ｎｘｑ＝ｃｕ（ｘ）＝ｃｕ（ｃ／Ｎ）
【００３５】
ｕは減少関数なので、合計のバックログＢ（Ｎ）はＮと共に増加するが、Ｎにおけるｕ（ｃ／Ｎ）の成長を制御するために、ｕを選択することができる。ある遅延ベースＴＣＰスキームは、ｕ（ｘ）＝α／ｘ、したがってＢ（Ｎ）＝αＮを有し、Ｎにおいて線形である。ＮにおけるＢ（Ｎ）の成長率を削減するために、
【００３６】
【数５】
2008511205.tif 000007
を選択することができ、ここで、
【００３７】
【数６】
2008511205.tif 000008
は、ピーク・レートであり、βは特定の環境に対して同調される、いくつかの正の定数である。したがって
【００３８】
【数７】
2008511205.tif 000009
である。
【００３９】
Ｎが増加するにつれて、線形に対してよりゆっくりとした、対数的なＢ（Ｎ）の成長に帰結する。スケーラブル効用関数の１つの利点は、バッファのオーバーフローを制御する、多数のβの値を使用できることである。例えば、β＝５ｍ秒とすると、ｃβは５ｍ秒のキューを収容することができるバッファ容量である。Ｂ（Ｎ）はＮにおいて対数的に成長することに留意されたい。
【００４０】
スケーラブル限界効用関数ｕ（ｘ）が一度選択されると、ウィンドウ調整は以下の形式をとることができる。
ｗk+1＝ｗk＋γ（ｕ（ｘk）−ｑk）
【００４１】
対数関数に加えて、ｕ（ｘ）の他の関数が、Ｎと共にＢ（Ｎ）のゆっくりとした成長を得るために、使用できることに留意すべきである。特にｕ（ｘ）は、準線形的に減少する任意の正の減少関数である。そのようなサンプルは、
【００４２】
【数８】
2008511205.tif 000010
であり、ここで
【００４３】
【数９】
2008511205.tif 000011
はピーク・レートである。したがって
【００４４】
【数１０】
2008511205.tif 000012
である。すなわちＢ（Ｎ）は、Ｎと共に線形にではなく、むしろ
【００４５】
【数１１】
2008511205.tif 000013
のように成長する。
最終的に、バッファ・オーバーフローを予防するために、前の章で記述されたキュー制御の技法と、以上に記述されたスケーラブル効用関数の技法とを組み合わせることができる。例えば、ｕ（ｘ）＝α／ｘをキュー制御技術と組み合わせることにより、新しい限界効用関数：ｕ（ｘ）＝α／ｘ＋ｑ0を得る。この方法に対して、バッファリング要求は
Ｂ（Ｎ）＝ｃｕ（ｃ／Ｎ）＝ｃｑ0＋αＮ
である。
【００４６】
【数１２】
2008511205.tif 000014
により、バッファリング要求は、
【００４７】
【数１３】
2008511205.tif 000015
である。したがって、最小キューイング遅延ｑ0により、βを非常に小さく選択することができ、かつＢ（Ｎ）における成長は、ｃβｌｏｇＮのオーダーである。ここでは対数関数が使用されているにもかかわらず、本発明の範囲と精神を逸脱することなく、他の関数が代わりに使用されてもよい。例えば、二乗根関数を使用することができる。
【００４８】
ダイナミックαチューニング
この技法は、ゆっくりとしたタイムスケール、かつ分配された方法で、αを動的に適合させようとする。この技法の実施形態は、図２のフロー図に示されている。各々のホスト・マシンにおいて、αを制御する信号として、この実施形態は、キューイング遅延の代わりに、パケット・ロス（ステップ２０１）を使用する。ホスト・マシンにより観察される、輻輳ロス・イベント毎（例えば、各々のＲＴＴにおける少なくとも８のバーストまたはｃｗｎｄ／１０のパケット・ロス）に対して（ステップ２０２）、このアルゴリズムは、その現在の値に比例する、ある量だけαを削減する（乗法的削減、またはＭＤ）（ステップ２０３）。このアルゴリズムは、各々の制御インターバルにおいて、ある一定の値（加法的増加、またはＡＩ）だけαを増加する（ステップ２０４）。言いかえれば、αはゆっくり増加するが、この技法の実施形態に応じて、急速に削減する（ＡＩＭＤと称する）。実際には、ある予め定められた範囲内でαは調整され、各々の調整の大きさには上限がある。
【００４９】
ＡＩＭＤアプローチは、ロス・ベース・アルゴリズムにおいて、輻輳ウィンドウの制御に使用される。ここではそれは、遅延ベース・アルゴリズムにおける、αのチューニングに使用される。この技法により、地球規模の協力なしでも、公正と効率を達成することができる。
【００５０】
従来技術のロス・ベース輻輳制御アルゴリズムは、パケット・ロスにおけるノイズという問題がある。これは、高速長距離ネットワークと無線ネットワークにおいて、非常に顕著である。これらのアルゴリズムは、パケット・ロスに対して、輻輳ウィンドウを削減することにより作用する。ランダム・パケット・ロスが優勢である局面では、ランダム・パケット・ロスがそのような変更を要求すべきではないのに、輻輳ウィンドウの削減を続けることにより、これらのアルゴリズムは不完全にしか動作しない。
【００５１】
輻輳信号としてパケット・ロスを使用する代わりに、αをチューニングするための信号として、この実施形態は輻輳ロス・イベントの使用を試みる。輻輳ロス・イベントは、輻輳のためにパケットが欠落したイベントと、定義される。対称的に、ランダム・パケット・ロスは、ランダム・リンク・エラーやその他の輻輳でない効果のために、パケットが欠落されるイベントである。ＴＣＰ輻輳制御アルゴリズムは、輻輳ロス・イベントに対してのみ作用すべきである。測定から、多数のパケット・ロスは、輻輳ロス・イベントにおいて一般的に現れる。単一のパケット・ロスは、ランダム・ロス・イベントにおいて一般的に現れる。本発明は、輻輳ロス・イベントを決定するために、あるパラメーターを利用する。
【００５２】
Ｐ＝８パケット：輻輳ロス・イベント検出のための閾値。１つのウィンドウにＰまたはＰ以上のパケット・ロスがある場合、検出アルゴリズムは、輻輳によるパケット・ロスを仮定する。Ｐは、正の整数であるべきである。
【００５３】
ｃｏｕｎｔｅｒ：現在のウィンドウにおいて検出された、パケット・ロスのためのカウンタ（負でない整数）。
【００５４】
ｃｗｎｄ：輻輳ウィンドウ（輻輳制御アルゴリズムから、このアルゴリズムのための入力変数）。
【００５５】
パラメーターＰは、輻輳ウィンドウｃｗｎｄの線形関数である。すなわち、Ｐ＝ｃｗｎｄ／ｋ。ここで、例えば、ｋ≧１００である。これは、パケット・ロス・イベントが、ｋ毎のパケットから１つが失われた場合のみに、輻輳ロス・イベントとして検出されることを意味する。そのような変形は、ランダム・ロス・レートが高い、無線ネットワークに関連する状況において、有用である。
【００５６】
図６は、本発明の輻輳ロス・イベント検出の、実施形態の動作を示すフロー図である。ステップ６０１でシステムは、初期化され、カウンタは０に設定される。判定ブロック６０２で、パケット・ロスが検出されたかどうかが判定される。そうでなければシステムは、パケット・ロスのチェックに戻る。イエスの場合、ステップ６０３で、カウンタが歩進（例えば、１だけ）される。
【００５７】
判定ブロック６０４で、カウンタがある閾値以上かどうかが判定される。記述される実施形態（例としての）では、その値が｛ｃｗｎｄ／１０，Ｐ｝より大きいかどうか見るために、カウンタがチェックされる。そうでなければ、システムはステップ６０２に戻る。イエスの場合、ステップ６０５で輻輳イベントがトリガーされる。判定ブロック６０６で、現在のＲＴＴが完了したかどうかが判定される。そうでなければ、システムはステップ６０２に戻る。イエスの場合、ステップ６０１でカウンタがゼロにリセットされる。
【００５８】
適応アルゴリズム
本発明の実施形態は、αの値を制御するための、適応アルゴリズムを提供する。このアルゴリズムは、提案される値を伴う、以下のパラメーターを有する。
【００５９】
Ｔ＝２０（秒）：定時制御インターバル。これは最大のＲＴＴより大きくあるべきである。
【００６０】
Ａ＝１（パケット）：各々の制御インターバルに対する、αの増分値。これは、正の整数であるべきである。
【００６１】
Ｂ＝１／８：各々の輻輳ロス・イベントに対する、αの減少部分。これは、（０，１）の間であるべきである。
【００６２】
β＝１／２：各々の制御インターバルに対する、αの減少部分の上限。これは、（Ｂ，１）の間および（０，１）の間であるべきである。
【００６３】
α＝８：αの下限（例示の実施形態）。これは、正の整数であるべきである。
【００６４】
【数１４】
2008511205.tif 000016
：αの上限（例示の実施形態）。これは、正の整数、かつαより大きくあるべきである。
【００６５】
ｃｕｒｒｅｎｔ＿ｔｉｍｅ：ローカル・マシンからの実際時刻であり、このアルゴリズムの入力変数である。
【００６６】
ｎｅｘｔ＿ｕｐｄａｔｅ＿ｔｉｍｅ：次の定時制御イベントの時刻。
【００６７】
ｌａｓｔ＿ａｌｐｈａ：最終定時制御イベントの直後の、α値。
【００６８】
図７は、本実施形態の適応アルゴリズムを示す、フロー図である。このアルゴリズムは、ＡＣＫまたは輻輳ロス・イベントが発生したかどうかに依存して、異なって作用する。このシステムは、ｎｅｘｔ＿ｕｐｄａｔｅ＿ｔｉｍｅ＝ｃｕｒｒｅｎｔ＿ｔｉｍｅ＋Ｔ、およびｌａｓｔ＿ａｌｐｈａ＝αで、初期化する。ステップ７０１で受信されたＡＣＫに対して、判定ブロック７０２で、現在時刻が次の更新時刻より大きいかどうかを見るために、システムがチェックする。そうでなければ、システムは次のＡＣＫを待つ。そうであれば、パラメーターを更新する時間である。ステップ７０４では、ｎｅｘｔ＿ｕｐｄａｔｅ＿ｔｉｍｅがＴだけ増加され、αがα＋Ａに設定される。判定ブロック７０５では、αの値が上限値
【００６９】
【数１５】
2008511205.tif 000017
を超えているかどうかを見るために、αの値がチェックされる。そうであれば、ステップ７０６で、αの値が、
【００７０】
【数１６】
2008511205.tif 000018
に等しく設定される。そうでなければ、ステップ７０７で、ｌａｓｔ＿ａｌｐｈａ値が、新しいα値に等しく設定される。このアルゴリズムの動作から見られるように、ＡＣＫ信号が受信される限り、アルファ値はアルファ値の上限まで、ゆっくりと増加される。
【００７１】
ステップ７０８で輻輳イベントが発生した場合には、ステップ７０９で、α＝（１−β）＊αに設定することにより、アルファ値が削減される。ステップ７１０では、これが（１−β）＊ｌａｓｔ＿ａｌｐｈａより小さいかどうかを見るために、この値がチェックされる。そうであれば、次にステップ７１１で、アルファ値が（１−β）＊ｌａｓｔ＿ａｌｐｈａに等しく設定される。判定ブロック７１０が偽であるか、またはステップ７１１の後に、判定ブロック７１２で、アルファ値がアルファ値の下限以下であるかどうか見るために、アルファ値がチェックされる。そうであれば、次にアルファ値がアルファ値の下限αに設定される。そうでなければ、エンド７１４に進む。
【００７２】
ルート・チェンジ検出
遅延ベースＴＣＰは、１往復時間（ＲＴＴ）から往復伝搬遅延（ｐＲＴＴ）を減算することにより、往復キューイング遅延を測定し、往復伝搬遅延が最小観察ＲＴＴであるように設定される。あるフローが、より長い伝搬遅延を伴う新しいパスに変更された場合、ＲＴＴの増加は、スループットの削減につながるルート・チェンジの代わりに、輻輳として解釈される。そのようなルート・チェンジの前に、αが増加された時に、増加されたキューイング遅延のために、ＲＴＴは増加すべきである。そのようなルート・チェンジの後には、キューが空なので、ＲＴＴは増加しない。したがって、多数の制御インターバルに対して、
【００７３】
【数１７】
2008511205.tif 000019
がゼロに近い場合は、ルート・チェンジが発生したように思われる。ある実施形態では、システムは１／Ｇを使用するが、ここでＧは、
【００７４】
【数１８】
2008511205.tif 000020
に対する閾値として、ｃｗｎｄ／ｍｉｎＲＴＴにより近似される、フローにより実行されるスループットである。
【００７５】
ルート・チェンジ検出のアルゴリズム
本発明の実施形態は、ルート・チェンジを検出するための、アルゴリズムを含んでいる。この実施形態のためのパラメーターと変数は、以下を含んでいる。
パラメーター
ＲＣ＿Ｔｈｒｅｓｈｏｌｄ＝１０：ルート・チェンジ検出のための閾値。ＲＣ＿Ｔｈｒｅｓｈｏｌｄ連続制御インターバル（各々のインターバルは、Ｔの長さを有する）に対して、
【００７６】
【数１９】
2008511205.tif 000021
が１／Ｇより小さい場合には、アルゴリズムはルート・チェンジ・イベントを検出する。
変数
ｍｉｎＲＴＴ：パケットの最終ウィンドウで観察される、全てのＲＴＴの最小値。これは、輻輳制御アルゴリズムからの入力変数である。
ｃｗｎｄ：パケットの最終ウィンドウの輻輳ウィンドウ。これは、輻輳制御アルゴリズムからの、入力変数である。
ｒｃ＿ｃｏｕｎｔ：
【００７７】
【数２０】
2008511205.tif 000022
が１／Ｇより小さい、連続インターバルの数のカウンタ。
ｌａｓｔ＿ｒｔｔ：
【００７８】
【数２１】
2008511205.tif 000023
が１／Ｇより小さい、現在の連続インターバルの、最初のインターバルにおけるｍｉｎＲＴＴ。
ｌａｓｔ＿ａｌｐｈａ：
【００７９】
【数２２】
2008511205.tif 000024
が１／Ｇより小さい、現在の連続インターバルの、最初のインターバルにおけるアルファ値。
【００８０】
図８は、本発明のルート・チェンジ検出の実施形態の、フロー図である。初期化は、ｒｃ＿ｃｏｕｎｔ＝０、ｌａｓｔ＿ｒｔｔ＝ｍｉｎＲＴＴ、ｌａｓｔ＿ａｌｐｈａ＝αに設定する。各々の制御インターバルＴに対して（ステップ８０１）輻輳ロス・イベントがあるかどうかを決定する（ステップ８０２）。そうであれば、ステップ８０７で、再度初期化する。そうでなければ、ステップ８０３で、（（α−ｌａｓｔ＿ａｌｐｈａ）／（ｍｉｎＲＴＴ−ｌａｓｔｓ＿ＲＴＴ））≦（ｃｗｎｄ／ｍｉｎＲＴＴ）かどうかを決定する。イエスの場合、ステップ８０７で、再度初期化する。そうでなければ、ステップ８０４で、ｒｃ＿ｃｏｕｎｔを歩進（例えば、１だけ）する。ステップ８０５では、ｒｃ＿ｃｏｕｎｔがｒｃ＿ｔｈｒｅｓｈｏｌｄを超えているかどうか見るためにチェックする。そうであれば、ステップ８０６でｐＲＴＴをｍｉｎＲＴＴに等しく設定し、ステップ８０７で再度初期化する。
【００８１】
ランダム化αチューニング
適応αチューニングの利点はその柔軟性である。１つの欠点は、ＡＩＭＤが常に遅いタイムスケールで、キューを満たすことである。補完的な技法は、予め定められた値の集合の間の、αの選択をランダム化することである。バッファが充分大きい場合には、この技法はキューを満たさないが、公正が制御され難い。ランダム化は、長期的に、公正を統計的に達成するために使用され、これは図３に示されている。
【００８２】
例えば、α＝８、２０、２００の３つの値のパケットが、それぞれ１０Ｍｂｐｓ、１００Ｍｂｐｓ、１Ｇｂｐｓの周囲のパスのために選択される。その現在のα値に対応する（ステップ３０２）スループット領域とは異なる最終更新インターバルの間で、あるフローがあるスループットを達成する（ステップ３０１）場合には、そのα値を次のレベルに増加または削減する（ステップ３０４）。そうでなければ、このα値は同じに留まる（ステップ３０３）。例えば、α＝２００パケットであり、達成されたスループットが９Ｍｂｐｓであれば、αがα＝２０パケットである次のレベルに削減される。
【００８３】
リソースを独占して、小さいα値を有するフローの損害になる、大きいα値を有するフローを防止するために、大きいタイムスケールで、各々のフローがランダムかつ独立して、そのα値を初期化し（ステップ３０５）、そのα値を再びシャッフルするために、上記のアルゴリズムを適用する。
【００８４】
方程式ベースのアルファ・チューニング
遅延ベースＴＣＰにおける、方程式ベースのアルファ・チューニングのゴールは、２つの輻輳フィードバック値、すなわち、ｑとｐの駆動関数の形式の、端から端までのキューイング遅延ｑとロス確率ｐを、予め定められたある目標、例えば平衡にあるｑ／ｐ／Ｋ定数に等しくすることである。ロス確率を正確に捕らえるのは困難なので、ある実施形態では、サイズＳのリング・バッファが、ロスの履歴を維持するために使用される。システムは、最終のＳインターバルを参照して、Ｓインターバル内で失われたパケットの合計数を決定し、Ｓインターバル内に送信されたパケットの全数でそれを除算する。この値は、ロス確率を表わし、ｐとして使用される。
【００８５】
多くの場合に、遅延ベースＴＣＰは、ロス・ベース輻輳制御プロトコル（例えばリノ）と一緒にネットワークで使用される。本発明は、遅延ベース・プロトコルと、ロス・ベース・プロトコルの双方が、合理的なスループットを有するような方法で、Ｋを選択する。Ｋの値は、実験データの大きな集合に基づいて、オフラインで計算される。本発明で使用されるＫの値の例は、１０である。
【００８６】
ある実施形態では、アルファ・チューニング・アルゴリズムは、各々の遅延ベースＴＣＰ送信器のみに実装され、それは平衡のｑとｐを反復して計算し、システム全体と同様に、それ自身のスループットを不安定にすることなく、遅延ベースＴＣＰ輻輳制御アルゴリズムのアルファ・パラメーターを動的に更新することにより、注意深く比ｑ／ｐをＫに向けて駆動する。アルファ・チューニング・アルゴリズムは、パケット・ロスが発生した場合に起動され、それによりゼロでないロス確率を生成する。全ての遅延ベースＴＣＰフローを有するよく準備されたネットワークでは、アルファの合計を収容する充分なバッファリングがある限り、アルファ・チューニングは起動されず、その平衡はアルファ・チューニングがない場合と同じである。このアルゴリズムは図９に示されている。初期条件は、η0＝１であり、かつαの初期値はａｌｐｈａ＿０である。時刻ｔに、周期的にｑtとｐtを、ステップ９０１で計算する。ステップ９０２で、λt＝ｑy／ｐt／ｋ（ここでｐtはゼロでない）。ステップ９０３で、ηt＝ｆ（η(t-1)，λt）を計算する。ステップ９０４で、新しいアルファ値αt＝ηt＊α0を計算する。λtが増加するにつれて、新しいαt値も増加する。同様に、λtが減少するにつれて、新しいαt値も減少する。λtは理論的に、０から無限大にまで変化するが、その実際の範囲は、αの初期値と、αの上下の限値に依存する。
【００８７】
関数ｆは、η(t-1)とλの現在の値に基づいて、新しい平均値ηtを計算する。任意の指数的に変化する平均化関数が、ｆとして使用されることができる。
【００８８】
ある実施形態では、浮動小数点演算を実行することは、不可能であるか、または望ましくない。したがって、浮動小数点演算は、有限の精度を有する整数を使用することにより、近似される。整数データの型式が大きいほど、浮動小数点近似はより高精度になる。本発明は、浮動小数点演算により実行されてもよい。
【００８９】
アルファの突然の急激な増加を防止するために、上記のＡＩＭＤスキームで記述されたような、現在のアルファ値に基づく、アルファの成長への制約を設定する。以上に記述された、他の実施形態で留意されたように、アルファの下方の閾値は、アルファが行かないであろう値よりも下に設定される。
【００９０】
１方向キューイング遅延測定
以上に記述された遅延ベース・スキームでは、遅延測定は往復遅延（ＲＴＴ）に基づいて実行される。これは、キューイング遅延を決定し、輻輳制御の正しい測定を適用することに関連する、往路パスと復路パスの双方からの遅延となる。ＲＴＴ遅延が大きい場合には、輻輳が仮定され、パケット・レートが削減される。これは、ある場合には望ましくない。例えば、往路パスでは輻輳していないが、復路パスでは輻輳している場合には、ＲＴＴ遅延は、輻輳を示唆して、往路パスでは削減される必要がないにもかかわらず、往路パスが削減される。往路と復路のパスは、それらのそれぞれの遅延において、対称的ではないので、復路パスでの輻輳を無視することがより適切である。平衡に達するために、輻輳ウィンドウのサイズの変更において、往路の遅延のみが使用されるように、復路のキューイング遅延を測定して減算する方法を、本発明は提供する。
【００９１】
復路パスでの輻輳から影響されないように、本発明のある実施形態は、復路パスでのキューイング遅延を測定し、ＲＴＴ測定からそれを減算して、往路でのキューイング遅延を得て、それをウィンドウ・サイズを決定するために使用する技法を含んでいる。ある実施形態では、パケットが送信された時に、送信器ＴＣＰエンジンにおいて、またそれが受信された時に、受信器ＴＣＰエンジンにおいて、それぞれパケットにタイムスタンプが押印される。これらのタイムスタンプの間の時間差は、往路パスでの遅延を表わしている。送信器と受信器のクロックが同期されておらず、それらのタイムスタンプを生成するのに、異なるクロック期間を使用しているので、問題が生じる。
【００９２】
復路キューイング遅延測定
復路キューイング遅延（ＢＱＤ）測定アルゴリズムは、送信器がクロック期間ｐ1を有し、受信器が、ｐ1≦ｐ2であるような、クロック期間ｐ2を有することを要求する。ｐ2クロックは、受信器のＲＦＣ１３２３タイムスタンプ・期間により固定され、送信器の期間ｐ1は、送信器の時間を測定する能力によってのみ限定されている。以下のアルゴリズムは、１ソース・クロック期間ｐ1内までの、ＢＱＤを測定する方法を提供する。高精度の測定は、１／ｐ2のレートで実行される。このアルゴリズムが、両端のエンド・ホスト・クロックが同期されていないことを容認する一方で、高精度の測定のためには、位相は安定しているべきである。ある実施形態では、ｐ2が既知であることを仮定し、他の実施形態では、ｐ2を推定する方法を提示する。
【００９３】
既知の受信器クロック期間
図４は、受信器クロック期間が既知である場合の、ＢＱＤを計算するための実施形態を示すフロー図である。ステップ４０１では、受信器クロック期間ｐ2が決定される。ステップ４０２では、受信器クロックが変化した後に、サンプルＡＣＫが取得される。ステップ４０３で、ＢＱＤの上方見積もりと下方見積もりとが計算される。ステップ４０３で生成された、上方見積もりと下方見積もりとを使用して、ステップ４０４で、ＢＱＤが決定される。ステップ４０５で、往路キューイング遅延ＦＱＤを生成するために、ＢＱＤが全キューイング遅延から減算される。ステップ４０６で、適切な輻輳制御応答を計算するために、ＦＱＤが使用される。
【００９４】
図５Ａは、以下の記述で参照される、受信器と送信器のクロック信号の、いくつかのタイミングの関係を示している。ｊ番目に送信されたパケットに対する、合計の復路パス遅延は、復路伝搬遅延ｄBPと復路キューイング遅延ｄBQjの和である。
ｄBj＝ｄBP＋ｄBQj      （１）
【００９５】
ｔ0jを、パケットｊの送信時間とする。ｊ番目に出ていくパケットは、時間ｔ1jに受信元に受信され、受信器は直ちにＡＣＫを送信して、時間ｔ2jに送信器に到着する。ｋ番目に受信されたパケットに対する、受領確認は、以下のタイムスタンプ値を有する。
【００９６】
【数２３】
2008511205.tif 000025
【００９７】
ｊ番目の受領確認が到着すると、送信器のクロックは、以下の値を有する。
【００９８】
【数２４】
2008511205.tif 000026
ここで、ｅは、２つのエンド・ホストのタイムスタンプ・クロックの間の、本来ずれである。パケットｊ、ｋからの情報により、２つの時間測定の間の、差異を以下のように定義する。
【００９９】
【数２５】
2008511205.tif 000027
これは以下のように拡張される。
【０１００】
【数２６】
2008511205.tif 000028
ここで、
【０１０１】
【数２７】
2008511205.tif 000029
である。
【０１０２】
可能な限り多くの他の項を除外するために、適切にパケットｊ、ｋを選択することにより、式（５）を使用して、伝搬遅延および、受信器クロックと送信器クロックの間のずれを推定することができる。
【０１０３】
【数２８】
2008511205.tif 000030
が整数であると仮定する。ｋ＝ｊである場合には、同じパケットに属する、到着時間と受信器タイムスタンプを使用して、ＣBjkが計算され、（５）は以下に単純化される。
【０１０４】
【数２９】
2008511205.tif 000031
【０１０５】
ｋが、受信器クロックの増加後に送信された最初の受領確認である（ステップ４０２）ように選択される場合には、最後の項が最小化されることに留意されたい。ＣBkを、ｋ番目のパケットの受領確認の到着時間における、全てのＣBkk測定の最小値であるとする。
ＣBK＝ＣBKK≦ＣBii  ｉ≦ｋ                          （７）
【０１０６】
ＣBkに対する下限値を、正確にサンプリングするためのこの条件が、受信器クロックが増加する時に、受領確認が送信され、復路キューイング遅延がなく、
【０１０７】
【数３０】
2008511205.tif 000032
であることに留意されたい。この値は、以下の最小値により、境界とされる。
【０１０８】
【数３１】
2008511205.tif 000033
これは、クロックずれと、復路伝搬遅延のみを含んでいる。特にＣBkkの最小値をサンプリングしたと仮定する。受信器クロックが増加した後の、最初のパケットであるように、ｋを選択した場合には、（６）と（８）を使用して、ＢＱＤの上方見積もりが構成され、ここで、Ａk＝Ａk-1＋１である。
【０１０９】
【数３２】
2008511205.tif 000034
【０１１０】
ｐ1が小さい場合には、
【０１１１】
【数３３】
2008511205.tif 000035
が以下で近似され、
【０１１２】
【数３４】
2008511205.tif 000036
第２項により導入される誤差は、常に上方見積もりに帰結する。
【０１１３】
ＢＱＤの下方見積もりを得るために（ステップ４０３）、ｊを期間Ａjに送信された最終の受領確認であり、ｋを次の期間Ａkでの最初の受領確認であるように、選択するとする。これは、ｋ＝ｊ＋１であり、Ａk＝Ａj＋１である。この場合（５）は、以下のように単純化される。
【０１１４】
【数３５】
2008511205.tif 000037
【０１１５】
最終の受領確認の選択により、最後の２項に起因する誤差を最小化することに留意されたい。ＢＱＤの下方見積もりを、以下と書くことができる。
ＤBQk＝ＣBJk−ＣB      （１２）
ここで、ｋ＝ｊ＋１、Ａk＝Ａj＋１である。再度、ｐ1が小さい場合には、ＤBQkは、以下に近似され、
【０１１６】
【数３６】
2008511205.tif 000038
最後の項により導入される誤差は、下方見積もりに帰結する。
【０１１７】
最小値８がサンプリングされ、受信器クロックが増加する前の最後の受領確認と、受信器クロックが増加した後の最初の受領確認との間のギャップが小さく、ｔ1j−ｔ1k→０であり、かつ送信器クロック期間が小さく、ｐ1→０である場合には、下方見積もりと上方見積もりが、復路キューイング遅延に近似する
ＤBQk→ｄBQk      （１４）
【０１１８】
【数３７】
2008511205.tif 000039
ことに留意されたい。
【０１１９】
単一のＢＱＤ見積もりは、下方見積もりと上方見積もりから、多数の異なる方法により計算できる（ステップ４０４）。ある実施形態は、異なるＡＣＫスペーシングにローバストな方法である。下方見積もりと上方見積もりは、ＡＣＫの送信時間に依存して、変化することに留意されたい。受信器クロックが増加した後のいつかに、ＡＣＫがなかった場合には、上方見積もりはエラーとなり、同様に、増加の前の最後のＡＣＫが、その増加のすぐ前ではない場合には、下方見積もりがエラーとなる。ＡＣＫスペーシングが信頼できない環境においては、ＢＱＤを、いくつかの下方および上方見積もりの、密接した境界に適合するある値に推定することができる。そのようなＢＱＤは、
【０１２０】
【数３８】
2008511205.tif 000040
を、
【０１２１】
【数３９】
2008511205.tif 000041
に推定する。
【０１２２】
受信器クロック期間推定−単一期間・サンプル
本発明は、受信器クロック期間の単一サンプルから、ｐ2を決定するための実施形態を含んでいる。この方法は、ＢＱＤ測定のためにｐ2を決定するには、不正確すぎることがある。しかしながら、ｐ2の大きさを決定し、この期間を使用する全てのオペレーティング・システムと互換性のある、既知の古典的な推定のテーブルからある推定を選択するために、その方法を使用することもできる。
【０１２３】
図５Ｂのタイミング図に示されているように、受信器クロックが増加する前後のＡＣＫの送信時間、それぞれ、ｔ(j-1)とｔ1jが、および、受信器クロックの次の増加の前後のＡＣＫの送信時間、それぞれ、ｔ(k-1)とｔ1kが既知である場合には、受信器クロック期間の下限値と上限値を計算することができる。この実施形態では、送信器はＡＣＫ送信時間を知らず、ｊ番目のパケットのＡＣＫ到着時間ｔ2jのみを知っており、ここで、ｔ2j＝ｔ1j＋ｄBjである。したがって、このクロック期間を推定するために、ＡＣＫ到着時間を使用する場合には、キューイング遅延の変化は、期間の境界推定にノイズを同様に付加する。クロックが増加する前後の、ＡＣＫの到着時間を使用することで、期間の下方の境界の推定
ｐ2k＝ｔ2(k-1)−ｔ2j＝ｔ1(k-1)−ｔ1j＋（ｄBQ(k-1)−ｄBQj）      （１７）
と上方の境界
【０１２４】
【数４０】
2008511205.tif 000042
を計算することができる。
【０１２５】
したがって、単一期間の測定からの受信器クロックの知識は、各々のＡＣＫが経験する、キューイング遅延の差異と同様に、ＡＣＫパケットのスペーシングの双方により限定される。
【０１２６】
受信器クロック期間推定−多数のサンプルの平均化
単一サンプル技法の精度の問題に、多数の期間に対するクロック期間測定の平均化により対処することができる。期間の推定を構成するために使用される平均化オペレータを定義する。
【０１２７】
【数４１】
2008511205.tif 000043
ここで、Ｘ（ｊ）は、時間ｔ2に取得されたサンプルＸiで、時間ｔ2jまでの全てのサンプルの集合、またＮ(S,e)は、期間ｓ＜ｔ2i＜ｅ内のサンプルの数である。ｔ2（ｊ）を、ｊ番目のＡＣＫの到着時刻における、全てのＡＣＫの到着時間の集合とし、また、Ａ（ｊ）を、ｔ2（ｊ）における、各々のＡＣＫに関連する、全ての受信器タイムスタンプの集合とする。
【０１２８】
受信器期間を推定する可能な１つの方法は、接続の開始から最新のパケットの時間までを、２つの領域に分割し、これらの２つの領域の間の、受信器クロックの平均増加に対する、送信器クロックの平均増加を計算することである。
【０１２９】
【数４２】
2008511205.tif 000044
【０１３０】
φj＝ｍｏｄ（ｔ1j，ｐ2）とすると、式（１８）を、ｐ2プラスＡＣＫ中間伝送時間に起因する誤差項と、キューイング遅延の変化に起因する誤差項とに、分離することができる。
【０１３１】
【数４３】
2008511205.tif 000045
ここで、
【０１３２】
【数４４】
2008511205.tif 000046
であり、
【０１３３】
【数４５】
2008511205.tif 000047
である。
【０１３４】
最大復路キューイング遅延がｄBQmaxである場合には、式（２２）と（２３）において、分子はそれぞれｐ2とｄBQmaxにより境界づけられる。したがって、ｔ1j→∞、ｒ（０，ｔ2j／２，ｔ2j／２，ｔ1j）→０、およびｅ（０，ｔ2j／２，ｔ2j／２，ｔ1j）→０、また
【０１３５】
【数４６】
2008511205.tif 000048
である。これは、
【０１３６】
【数４７】
2008511205.tif 000049
がＡＣＫ送信時間の分布またはキューイング遅延の変化とは無関係に、ｐ2にゆくゆくは収束することを意味する。
【０１３７】
有限の推定期間にわたる、期間推定の最悪の場合の誤差を考察する。期間推定の下限値と上限値を、計算することができる。最大の正の期間誤差は、キュー・サイズが最大で、最大φの後に、キュー・サイズが最小でφ＝０の領域が続く場合に発生する。期間推定の上限は、以下である。
【０１３８】
【数４８】
2008511205.tif 000050
【０１３９】
最大の負の期間誤差は、キュー・サイズが最小でφ＝０の領域の後に、キュー・サイズが最大で最大φが続く場合に発生する。期間の下限は、以下である。
【０１４０】
【数４９】
2008511205.tif 000051
【０１４１】
ｒ（ｓ１，ｅ１，ｓ２，ｅ２）項に起因する推定誤差は、受信器クロックが増加する後に、最初のパケットのみを選択することにより削減され、したがって、サンプルＡ（ｊ）とｔ2（ｊ）の集合は、Ａj＝Ａj-1＋１であるパケットのみを含んでいる。ｅ（ｓ１，ｅ１，ｓ２，ｅ２）項に起因する推定誤差は、同様に、２つの領域の間のキューイング遅延の差異についての情報が利用可能である場合に、削減される。
【０１４２】
ＢＱＤ検出を伴う遅延ベースＴＣＰ
ＢＱＤが一度決定されると、それは遅延ベースＴＣＰアルゴリズムに、組み込まれる。ｑｄｅｌａｙ＞０であり、
【０１４３】
【数５０】
2008511205.tif 000052
であるための、遅延ベースＴＣＰウィンドウ制御規則を思い出されたい。
【０１４４】
【数５１】
2008511205.tif 000053
【０１４５】
平衡状態では、式（２６）は
【０１４６】
【数５２】
2008511205.tif 000054
を与え、平衡ソース・レートが、αおよび往路キューと復路キュー
Ｘ（ＤBQ＋ＤFQ）＝α                            （２８）
に依存することを示唆する。
【０１４７】
ベースＲＴＴ’＝ベースＲＴＴ＋ＤBQのように、ＢＱＤ推定をベースＲＴＴ推定に付加することにより、ＢＱＤ測定を遅延ベースＴＣＰ制御規則に統合した。ベースＲＴＴの代わりに、ベースＲＴＴ’を使用することにより、ソース・レートがもはや復路キューに依存せず、
ＸＤFQ＝α                                      （２９）
であるように、この平衡特性が変更された。
【０１４８】
このようにして、輻輳制御のための、ウィンドウとアルファ調整を決定するために、往路キューイング遅延のみが使用される。
【図面の簡単な説明】
【０１４９】
【図１】本発明のキュー制御の実施形態を示す、フロー図である。
【図２】ダイナミックαチューニングの実施形態を示す、フロー図である。
【図３】ランダム化されたチューニングの実施形態を示す、フロー図である。
【図４】ＢＱＤ演算の実施形態を示す、フロー図である。
【図５Ａ】ＡＣＫ送信時および受信時の、受信器クロック値および送信器クロック値を示す、タイミング図である。
【図５Ｂ】サンプルからの受信器クロック期間の上限と下限を示す、タイミング図である。
【図６】本発明の実施形態における、輻輳ロス・イベントの検出を示す、フロー図である。
【図７】本発明の実施形態の適合アルゴリズムを示す、フロー図である。
【図８】本発明における、ルート・チェンジの検出の実施形態を示す、フロー図である。
【図９】本発明のアルファ・チューニングの実施形態を示す、フロー図である。
【図１】
2008511205.tif 000058
【図２】
2008511205.tif 000059
【図３】
2008511205.tif 000060
【図４】
2008511205.tif 000061
【図５Ａ】
2008511205.tif 000062
【図５Ｂ】
2008511205.tif 000063
【図６】
2008511205.tif 000064
【図７】
2008511205.tif 000065
【図８】
2008511205.tif 000066
【図９】
2008511205.tif 000067
【国際調査報告】
2008511205.tif 000068