(57)【特許請求の範囲】
【請求項１】
データパケットを処理する方法であって、
送信したパケットに対するフィードバック信号を観察すること、
観察されたフィードバック信号からネットワークの輻輳の周期プロフィールを生成することであって、前記周期プロフィールは、過去に観察されたフィードバック信号が前記ネットワークの輻輳状態を示す時間間隔および過去に観察されたフィードバック信号が前記ネットワークの非輻輳状態を示す時間間隔の少なくとも１つを反映すること、
前記観察されたフィードバック信号に基づくネットワークの状態を前記周期プロフィールにマッチさせること、
前記周期プロフィールに基づいて前記ネットワークの将来の状態を推定すること、および
前記ネットワークが、将来の輻輳した状態を有すると推定される場合、１または複数のデータパケットの送信を遅延させること
を備えたことを特徴とするデータパケットを処理する方法。
【請求項２】
前記推定し、遅延させることは、エンドユーザのコンピュータで実行されることを特徴とする請求項１に記載の方法。
【請求項３】
前記推定することは、前記フィードバック信号から求められる複数の変数を、０（非輻輳）状態および１（輻輳）状態におけるそれぞれの滞在時間の推定であるΩ０、Ω１と、１つの状態が別の状態に変化した最後の時刻の推定であるlast_tと、時刻last_tにおいて入ったと考えられる状態であるlast_stateとしたとき、
【数１】
0004703063.tif 000017
に従って行い、ここで、
【数２】
0004703063.tif 000018
は、ネットワークの将来の状態の推定を備えることを特徴とする請求項１に記載の方法。
【請求項４】
前記ネットワークの状態が変化したときに前記変数のうちの１または複数を更新することであって、前記更新することは、
【数３】
0004703063.tif 000019
に従って行い、ここで、Ｈは０と１の間をとることができ、t1,t2,..．はパケットが送信された連続する時刻であり、Y(t1),Y(t2),...は対応するフィードバックであり、Y(tn+1)は入手可能な最新フィードバックであることをさらに備えたことを特徴とする請求項１に記載の方法。
【請求項５】
前記推定に関連する信頼度を計算することをさらに備え、前記計算することは、前記輻輳状態および前記非輻輳状態での滞在時間の分散を、
【数４】
0004703063.tif 000020
に従って行い、ここで、Ｈχは０と１の間をとることができることを特徴とする請求項１に記載の方法。
【請求項６】
１または複数のエンドユーザのコンピュータによって実行されたとき、前記エンドユーザのコンピュータに、
送信したパケットに対するフィードバック信号を観察すること、
観察されたフィードバック信号からネットワークの輻輳の周期プロフィールを生成することであって、前記周期プロフィールは、過去に観察されたフィードバック信号が前記ネットワークの輻輳状態を示す時間間隔および過去に観察されたフィードバック信号が前記ネットワークの非輻輳状態を示す時間間隔の少なくとも１つを反映すること、
前記観察されたフィードバック信号に基づくネットワークの状態を前記周期プロフィールにマッチさせること、
前記周期プロフィールに基づいて前記ネットワークの将来の状態を推定すること、および
前記ネットワークが、将来の輻輳した状態を有すると推定される場合、１または複数のデータパケットの送信を遅延させること
を実行させるコンピュータ実行可能命令を有するコンピュータ読み取り可能記憶媒体。
【請求項７】
前記推定することは、前記フィードバック信号から求められる複数の変数を、０（非輻輳）状態および１（輻輳）状態におけるそれぞれの滞在時間の推定であるΩ０、Ω１と、１つの状態が別の状態に変化した最後の時刻の推定であるlast_tと、時刻last_tにおいて入ったと考えられる状態であるlast_stateとしたとき、
【数５】
0004703063.tif 000021
に従って行い、ここで、
【数６】
0004703063.tif 000022
は、ネットワークの将来の状態の推定を備えることを特徴とする請求項６に記載のコンピュータ読み取り可能記憶媒体。
【請求項８】
前記ネットワークの状態が変化したときに前記変数のうちの１または複数を更新することであって、前記更新することは、
【数７】
0004703063.tif 000023
に従って行い、ここで、Ｈは０と１の間をとることができ、t1,t2,..．はパケットが送信された連続する時刻であり、Y(t1),Y(t2),...は対応するフィードバックであり、Y(tn+1)は入手可能な最新フィードバックであることをさらに実行させるコンピュータ実行可能命令を有する請求項６に記載のコンピュータ読み取り可能記憶媒体。
【請求項９】
前記エンドユーザのコンピュータに、前記推定に関連する信頼度を計算することをさらに実行させ、前記計算することは、前記輻輳状態および前記非輻輳状態での滞在時間の分散を、
【数８】
0004703063.tif 000024
に従って行い、ここで、Ｈχは０と１の間をとることができることを特徴とする請求項６に記載のコンピュータ読み取り可能記憶媒体。
【請求項１０】
データパケットを処理する装置であって、
ネットワークを介して送られるデータパケットを生成する１または複数のプロトコルモジュールと、
前記ネットワークを介した送信のため前記プロトコルモジュールによって生成されたデータパケットをスケジューリングするパケットスケジューラと、
送信したデータパケットに対するフィードバック信号を観察して、前記ネットワークの輻輳を推定するように構成された予測器モジュールであって、
観察されたフィードバック信号からネットワークの輻輳の周期プロフィールを生成することであって、前記周期プロフィールは、過去に観察されたフィードバック信号が前記ネットワークの輻輳状態を示す時間間隔および過去に観察されたフィードバック信号が前記ネットワークの非輻輳状態を示す時間間隔の少なくとも１つを反映し、
前記観察されたフィードバック信号に基づくネットワークの状態を前記周期プロフィールにマッチさせ、
前記周期プロフィールに基づいて前記ネットワークの将来の状態を推定し、
さらに、前記パケットスケジューラが使用することができ、前記将来の時点でネットワークの輻輳が起こりそうな場合、パケットの送信を遅延させるための情報を、前記パケットスケジューラに提供する予測器モジュールと
を備えたことを特徴とする装置。
【請求項１１】
エンドユーザのコンピュータ上で実現されることを特徴とする請求項１０に記載の装置。
【請求項１２】
前記１または複数のプロトコルモジュールは、ＴＣＰモジュールを備えることを特徴とする請求項１０に記載の装置。
【請求項１３】
前記ネットワークは、インターネットであることを特徴とする請求項１０に記載の装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ネットワーク輻輳を緩和する方法およびシステムに関し、詳細には、パケットトラヒックの誘発するネットワーク振動に起因してインターネットに起こり得るネットワーク輻輳を緩和する方法およびシステムに関する。
【０００２】
【従来の技術】
インターネットなどのネットワークを介してデータを転送するために利用可能な多くのプロトコルのなかで、ＴＣＰ／ＩＰ（これは、伝送制御プロトコル／インターネットプロトコルを表す）が、最も広く受け入れられているものである。
ＴＣＰは、データを別々のパケットで伝送することによって、信頼できる転送を確実にする。より正確には、ＴＣＰは、データをセグメント化し、ＩＰヘッダとともにＴＣＰセグメントが、ＩＰパケットを形成する。ＴＣＰセグメントのサイズは、最大セグメントサイズ（ＭＳＳ）によって制限され、これは、接続に依存するものであり、５３６バイトのデフォルト値を有する。「スライディングウインドウ」プロトコルまたは「ハンドシェーク」プロトコルは、伝送を３つの分かれたフェーズに区分する。第１フェーズは、送る準備のできたデータを表す。第２フェーズは、伝送中であるか、または着信したが、まだ肯定応答されていないかのいずれかであるデータを表す。第３フェーズは、着信に成功し、肯定応答されたデータを表す。したがって、２５６Ｋｂのファイルは、いくつかのパケットに分割され、そのそれぞれが、順次、３つのフェーズすべてを経過する。ＴＣＰ／ＩＰの説明を提供する優れたテキストは、Comerの「Internet working with TCP/IP, Volume I: Principles, Protocols, and Architecture Third Edition」である。
【０００３】
予期されるとおり、ネットワークを介するデータトラヒックは、輻輳の影響を受けやすい可能性がある。輻輳は、１つまたは複数のスイッチングポイント（例えば、ルータ）におけるパケット（またはデータグラム）のオーバーロードによって引き起こされるひどい遅延の状態である。輻輳が起きたとき、遅延が増大して、ルータは、パケットを経路指定できるまで、キューに入れ始める。各ルータは、有限の記憶容量を有し、パケットまたはデータグラムは、その記憶領域のために競い合わなければならない（すなわち、データグラムベースのインターネットでは、個々のＴＣＰ接続に対するリソースの事前割当てが存在しない）。最悪の場合、輻輳の起きたルータに着信するパケットまたはデータグラムの総数は、そのルータの容量に達して、パケットを廃棄し始めるまで増える。
【０００４】
通信接続のエンドポイントは、通常、どこで、またはなぜ輻輳が起きたのかの詳細を知らない。それらにとって、輻輳は、単に増大した遅延または失われたパケットを意味する。残念ながら、ほとんどのトランスポートプロトコルは、タイムアウトおよび再送を使用し、したがって、増大した遅延または損失に対し、パケットまたはデータグラムを再送によって対応する。再送は、輻輳を緩和するのではなく、それを悪化させる。それが抑制されない場合、増大したトラヒックは、増大した遅延をもたらすことになって、これが増大したトラヒックにつながり、ネットワークが役に立たなくなるまで続く。この状態は、「輻輳崩壊」として知られている。
【０００５】
輻輳崩壊を回避するためには、ＴＣＰは、輻輳が発生したとき、伝送速度を抑えなければならない。ルータは、キュー長を監視し、ある技法を使用して、ホストに輻輳が発生したことを知らせるが、ＴＣＰのようなトランスポートプロトコルは、遅延が起きたときはいつでも自動的に伝送速度を抑えることによって輻輳を回避する。もちろん、輻輳を回避するアルゴリズムは、注意深く構成しなければならない。というのは、通常の動作条件の下でさえ、ネットワークは、往復遅延の幅広い変動を示し得るからである。
【０００６】
輻輳を回避するため、ＴＣＰ規格は、現在、２つの技法、スロースタート（slow-start）および乗法的縮小（multiplicative decrease）を使用することを推奨している。これらの技法は、関連しており、容易に実施することができる。各ＴＣＰ接続ごとに、ＴＣＰは、受信側のウインドウのサイズを憶えていなければならない（すなわち、「ウインドウ」は、肯定応答で示されるバッファサイズとして定義される）。輻輳を制御するため、ＴＣＰは、「輻輳ウインドウ制限」または単に「輻輳ウインドウ」と呼ばれる第２制限を維持する。常時、ＴＣＰは、ウインドウサイズが、（１）受信側のウインドウと（２）輻輳ウインドウのうちの小さい方であるように動作する。
【０００７】
輻輳のない接続での安定した状態では、輻輳ウインドウは、受信側のウインドウと同じサイズである。輻輳ウインドウのサイズを縮小することが、ＴＣＰがその接続に注入することになるトラヒックを抑える。輻輳ウインドウサイズを推定するため、ＴＣＰは、ほとんどのパケットまたはデータグラムの損失が、輻輳から来るものであると想定して、次の戦略を使用する。
【０００８】
乗法的縮小輻輳回避：セグメントが損失すると、輻輳ウインドウを半分に（少なくとも１セグメントの最小限にまで）縮小する。許容されるウインドウ内に残ったセグメントに対して、再送タイマを指数的に後退させる。
【０００９】
ＴＣＰは、各損失ごとに輻輳ウインドウを半分に縮小するので、損失が続く場合、そのウインドウを指数的に縮小する。言い換えれば、輻輳が続く場合、ＴＣＰは、トラヒックの量を指数的に減少させ、また再送の速度を指数的に低下させる。損失が続く場合、ＴＣＰは、最終的には、伝送を単一のパケットまたはデータグラムに制限して、再送の前にタイムアウト値を２倍にすることを続ける。その着想は、迅速で有意なトラヒック削減を提供して、ルータがすでにそのキューの中にあるパケットまたはデータグラムを解消するのに十分な時間を与えることである。
【００１０】
輻輳から回復するためには、この処理を単に逆に行って、トラヒックが再び流れ始めたときに、輻輳ウインドウを２倍にすることを考えるかもしれない。しかし、そうすることは、トラヒックがない状態と輻輳の間で大きく振動する不安定なシステムをもたらす。代わりに、ＴＣＰは、スロースタートと呼ばれる技法を使用して、伝送をスケールアップする。
【００１１】
スロースタート（加法的）回復：新しい接続上でトラヒックを開始する、あるいは輻輳の期間の後にトラヒックを増加するときはいつでも、輻輳ウインドウを単一セグメントのサイズで開始して、この輻輳ウインドウを肯定応答が着信するたびに毎回、１セグメントずつ増加する。
【００１２】
スロースタートは、輻輳が解消された直後に、あるいは新しい接続が突然に開始したとき、追加のトラヒックでインターネットを溢れさせることを回避する。
【００１３】
「スロースタート」という用語は、誤った名前であるかもしれない。というのは、理想的な条件下では、その開始は非常に遅くはないからである。ＴＣＰは、輻輳ウインドウを１に初期設定し、初期セグメントを送信して待つ。肯定応答が着信したとき、それは、輻輳ウインドウを２に増大し、２つのセグメントを送信して待つ。２つの肯定応答が着信したとき、それぞれ輻輳ウインドウを１だけ増大し、したがって、ＴＣＰは、４つのセグメントを送信することができる。それらに対する肯定応答は、輻輳ウインドウを８に増大することになる。４回の往復のなかで、ＴＣＰは、１６のセグメントを送信することができ、これは、しばしば、受信側のウインドウの制限に達するのに十分である。極めて大きいウインドウの場合でさえ、ＴＣＰがＮ個のセグメントを送信できるまでには、ｌｏｇ２Ｎ回の往復しか要しない。
【００１４】
ウインドウサイズをあまりにも急速に増大させて、さらなる輻輳を引き起こすことを回避するため、ＴＣＰは、もう１つの制約を追加する。輻輳ウインドウが輻輳以前の元のサイズの１／２に達すると、ＴＣＰは、輻輳回避フェーズに入って、増分のレートを低下させる。輻輳回避中、ＴＣＰは、ウインドウ内のすべてのセグメントが肯定応答された場合にのみ、輻輳ウインドウを１だけ増大させる。これは、線形増加フェーズとして知られている。
【００１５】
輻輳回避のスロースタート増加、線形増加、および乗法的縮小の動作、ならびに指数的なタイマの戻しがまとまりとなって、プロトコルソフトウェアに有意な計算上のオーバーヘッドを全く加えることなく、パフォーマンスを向上させる。
【００１６】
したがって、ＴＣＰトラヒックソースは、その動作に同期する傾向があり、これが、ネットワークのボトルネックリンクでのバッファ占有レベルの振動をもたらすことが認められている。こうした振動は、望ましくない。というのは、使用する帯域幅の与えられたレベルに対して、より大きなキュー遅延、またはより多くのパケット損失を含む可能性が高いからである。
【００１７】
ランダム早期検出（「ＲＥＤ」）が、ＴＣＰソースを非同期化し、したがって、そうした振動の影響を抑えるために提案されている。ＲＥＤは、FloydおよびJacobsonの「Random early detection gateways for congestion avoidance, IEEE/ACM Trans. On Networking, 1(4), 1993」に詳細に記載されている。ＲＥＤは、輻輳の起きているバッファリソースによって送信されるバイナリフィードバック信号を平滑化することによって、振動の影響を抑えようとする。そうしたバイナリフィードバック信号は、パケット損失イベントまたは早期輻輳通知（ＥＣＮ）マークの形態をとることができる。例えば、Floydの「TCP and explicit congestion notification, ACM Computer Communication Review, 24 pp.10〜23, 1994」を参照されたい。この初期提案の多くの変形形態が示唆されており、いくつかの最近の研究は、どのようにＲＥＤパラメータを調整して最大効率を得るかという微妙な問題に取り組んでいる。例えば、FiroiuおよびBordenの「A study of active queue management for congestion control, Infocom 2000」を参照されたい。補完的な提案は、ＥＣＮマークの使用を提案している。これは、アクティブなバッファ管理判断が行われる時点で、パケットをドロップするのではなく、それにマーク付けをして、不必要なパケット伝送を回避している間、ソースに控えているように伝える。
【００１８】
【発明が解決しようとする課題】
ＲＥＤおよびその変形形態の実施についての継続中の研究からは、実現されるバッファ占有での振動の抑制は、当初に期待されていたほど劇的なものではないように思われる。いつパケットにマーク付けするか、またはいつそれをドロップするかを判断するために提案された規則は、さらに改良できることを正当に主張し得る。
【００１９】
したがって、本発明は、ネットワーク輻輳問題、詳細には、インターネットの環境内でのこの問題に対処するために使用される方法およびシステムを改良することに関連する関心から生まれた。
【００２０】
【課題を解決するための手段】
ネットワークフィードバックから輻輳パターンを検出して、予測する方法およびシステムを説明する。本発明の実施形態では、バイナリフィードバックメッセージの形式においてネットワークフィードバックが受信される。このネットワークフィードバックは、任意の適切なフィードバックメッセージを含むことができ、図示して説明する実施形態では、そのいくつかだけを挙げれば、パケット損失イベントまたはＥＣＮマークを含む。本発明の実施形態は、ネットワークフィードバックを使用して、将来、いつ輻輳が起きる可能性が高いかを予測する。これらの予測に基づいて、システム内のエンドユーザの行動は、輻輳を抑えるように変更することができる。詳細には、エンドユーザによって送信されるデータパケットは、典型的に、予測される輻輳が緩和される時点まで遅延することができる。したがって、本発明のシステムおよび方法は、ネットワーク輻輳問題に対処するのに、反応的手法ではなく、予測的で予防的な手法をとる。
【００２１】
【発明の実施の形態】
（概要）
ネットワークフィードバックから輻輳パターンを検出して予測する方法およびシステムを説明する。本発明の実施形態では、バイナリフィードバックメッセージの形式でのネットワークフィードバックが受信される。このネットワークフィードバックは、任意の適切なフィードバックメッセージを含むことが可能であり、図示して説明する実施形態では、そのいくつかだけを挙げれば、パケット損失イベントまたはＥＣＮマークを含む。フィードバックは、例えば、損失イベントまたはＥＣＮマークが使用される場合、ＴＣＰのリターンパスを利用することによって受信することができる。本発明の実施形態は、ネットワークフィードバックを使用して、将来、いつ輻輳が起きる可能性が高いかを予測する。これらの予測に基づいて、システム内のエンドユーザの行動は、輻輳を抑えるように変更することができる。詳細には、エンドユーザによって伝送されるデータパケットは、典型的に、予測される輻輳が緩和される時点まで遅延することができる。したがって、本発明のシステムおよび方法は、ネットワーク輻輳問題に対処するために、上記の「従来の技術」で述べたシステムによって代表される反応的手法ではなく、予測的で予防的な手法をとる。
【００２２】
（例としての動作環境）
記載された実施形態が動作することのできる１つの例としての動作環境は、一般的な分散コンピュータ環境を含み、これには、一般的に、インターネットを介して他のクライアントおよび他のネットワークに接続された、ハブ、ルータ、ゲートウェイ、トンネルサーバ、アプリケーションサーバなどを有するローカルエリアネットワークが含まれ得る。典型的なインターネットネットワーク構成の要素のいくつかが図１に示され、あるインターネットサービスプロバイダ（ＩＳＰ）接続１０８を介して、インターネット１０７に接続されたゲートウェイ／ハブ／トンネルサーバ／など１０６に接続された、いくつかのクライアントマシン１０５が含まれる。また、ＩＳＰ接続１０４を介して、インターネット１０７に同様に接続された他の可能なクライアント１０１、１０３も示されている。これらのユニットは、様々な企業アプリケーションサーバ１１２、１１３、１１４に１１１で接続されたゲートウェイ／トンネルサーバ１１０に、ＩＳＰ接続１０９を介して、場合によっては、ホームオフィスと通信する。これらのアプリケーションサーバは、別のハブ／ルータ１１５を介して、様々なローカルクライアント１１６、１１７、１１８に接続することができる。これは、本発明の実施形態を使用することができる１つの例としてのネットワークコンピュータ環境だけを示していることが理解されよう。
【００２３】
（例としてのコンピュータ環境）
上記に示したネットワーク環境は、いくつかのコンピュータユニットで構成されている。個々のコンピュータユニットは、図２のコンピュータユニットによって説明することができる。
【００２４】
図２は、そこで下記に説明する本発明の技法を実施することができる適切なコンピュータ環境２２０の例を示している。
【００２５】
例としてのコンピュータ環境２２０は、単に、適切なコンピュータ環境の一例であり、記載する技法の使用または機能性の範囲に関するどのような制限を示唆することを意図するものではない。また、コンピュータ環境２２０も、例としてのコンピュータ環境２２０内で示される構成要素のどれか、またはそれらの組合せに関係するどのような依存性または要件も有するものと解釈すべきではない。
【００２６】
記載する技法は、多数の他の汎用または特殊目的のコンピュータシステム環境または構成を使用して、動作することができる。記載する技法と共に使用するのに適切であり得るよく知られたコンピュータシステム環境および／または構成の例には、パーソナルコンピュータ、サーバコンピュータ、シンクライアント、シッククライアント、ハンドヘルドデバイスまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能な家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、前記システムまたはデバイスいずれかを含む分散コンピュータ環境などが含まれるが、それらには限定されない。
【００２７】
記載する技法は、コンピュータによって実行される、プログラムモジュールなどのコンピュータ実行可能命令の一般的文脈で説明することができる。一般的に、プログラムモジュールには、特定のタスクを実行するまたは特定の抽象的データタイプを実施する、ルーチン、プログラム、オブジェクト、構成要素、データ構造などが含まれる。記載する技法は、また、タスクが通信ネットワークを介してリンクされた遠隔処理デバイスによって実行される分散コンピュータ環境で実行することも可能である。分散コンピュータ環境では、プログラムモジュールは、メモリ記憶装置を含むローカルおよび遠隔、両方のコンピュータ記憶媒体内に配置することができる。
【００２８】
図２に示すとおり、コンピュータ環境２２０には、コンピュータ２３０の形態での汎用コンピュータ装置が含まれる。コンピュータ２２０の構成要素には、１つまたは複数のプロセッサまたは処理装置２３２、システムメモリ２３４、およびシステムメモリ２３４を含む様々なシステム構成要素をプロセッサ２３２に結合するバス２３６が含まれ得るが、それらには限定されない。
【００２９】
バス２３６は、いくつかのタイプのバス構造のうちの任意の１つまたは複数のものを表し、これには、メモリバスまたはメモリコントローラ、周辺バス、加速グラフィックスポート、および様々なバスアーキテクチャのうちのいずれかを使用するプロセッサまたはローカルバスが含まれる。例として制限するものではなく、そうしたアーキテクチャには、Industry Standard Architecture（ＩＳＡ）バス、Micro Channel Architecture（ＭＣＡ）バス、Enhanced ISA（ＥＩＳＡ）バス、Video Electronics Standards Association（ＶＥＳＡ）ローカルバス、およびMezzanineバスとしても知られているPeripheral Component Interconnects（ＰＣＩ）バスが含まれる。
【００３０】
コンピュータ２３０は、典型的に、様々なコンピュータ可読媒体を含む。そうした媒体は、コンピュータ２３０によってアクセス可能な任意の入手できる媒体であり、これには、揮発性媒体と不揮発性媒体、取外し可能媒体と取外し不可能な媒体の両方が含まれる。
【００３１】
図２では、システムメモリには、ランダムアクセスメモリ（ＲＡＭ）２４０などの揮発性メモリ、および／または読取り専用メモリ（ＲＯＭ）２３８などの不揮発性メモリの形態において、コンピュータ可読媒体が含まれる。始動中など、コンピュータ２３０内の要素間で情報を転送するのを助ける基本ルーチンを含んだ基本入力／出力システム（ＢＩＯＳ）２４２が、ＲＯＭ２３８内に記憶されている。ＲＡＭ２４０は、典型的には、プロセッサ２３２にとって直接にアクセス可能であり、かつ／またはそれによって現在、実行されているデータおよび／またはプログラムモジュールを含む。
【００３２】
コンピュータ２３０は、さらに、他の取外し可能／取外し不可能な、揮発性／不揮発性のコンピュータ記憶媒体を含み得る。単に例として、図２は、取外し不可能な不揮発性の磁気媒体（図示しておらず、典型的に、「ハードドライブ」と呼ばれる）から読み取り、そこに書き込むためのハードディスクドライブ２４４と、取外し可能な不揮発性の磁気ディスク２４８（例えば、「フロッピー（登録商標）ディスク」）から読み取り、そこに書き込むための磁気ディスクドライブ２４６と、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、または他の光媒体などの、取外し可能な不揮発性の光ディスク２５２から読み取り、そこに書き込むための光ディスクドライブ２５０とを示している。ハードディスクドライブ２４４、磁気ディスクドライブ２４６、および光ディスクドライブ２５０は、それぞれ、１つまたは複数のインターフェース２５４によってバス２３６に接続されている。
【００３３】
これらのドライブおよびその関連するコンピュータ可読媒体は、コンピュータ２３０のための、コンピュータ可読命令、データ構造、プログラムモジュール、および他のデータの不揮発性記憶領域を提供する。本明細書に記載する例としての環境は、ハードディスク、取外し可能な磁気ディスク２４８、および取外し可能な光ディスク２５２を使用するが、磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ランダムアクセスメモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）などの、コンピュータによってアクセス可能な、データを記憶することができる他のタイプのコンピュータ可読媒体も、例としての動作環境で使用できることが、当分野の技術者によって理解されよう。
【００３４】
いくつかのプログラムモジュールをハードディスク、磁気ディスク２４８、光ディスク２５２、ＲＯＭ２３８、またはＲＡＭ２４０上に記憶することができ、これには、例として制限するものではなく、オペレーティングシステム５８、１つまたは複数のアプリケーションプログラム２６０、他のプログラムモジュール２６２、およびプログラムデータ２６４が含まれる。
【００３５】
ユーザは、キーボード２６６およびポインティングデバイス２６８（「マウス」などの）などの入力デバイスを介して、コマンドおよび情報をコンピュータ２３０に入力することができる。他の入力デバイス（図示せず）には、マイクロホン、ジョイスティック、ゲームパッド、サテライトディッシュ、シリアルポート、スキャナ、またはそれらに類するものを含むことができる。これらの入力デバイスおよび他の入力デバイスは、バス２３６に結合されたユーザ入力インターフェース２７０を介して、処理装置２３２に接続されているが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）などの他のインターフェースおよびバス構造によって接続することもできる。
【００３６】
モニタ２７２または他のタイプの表示装置もまた、ビデオアダプタ２７４などのインターフェースを介して、バス２３６に接続されている。モニタに加えて、パーソナルコンピュータは、典型的に、スピーカやプリンタなどの他の周辺出力装置（図示せず）を含み、これらは、出力周辺インターフェース２７５を介して接続することができる。
【００３７】
コンピュータ２３０は、遠隔コンピュータ２８２などの１つまたは複数の遠隔コンピュータに対する論理接続を使用するネットワーク化された環境で動作することができる。遠隔コンピュータ２８２は、コンピュータ２３０に関連して本明細書で記載した要素および機能の多くまたはすべてを含み得る。
【００３８】
図２に示す論理接続は、ローカルエリアネットワーク（ＬＡＮ）２７７および汎用ワイドエリアネットワーク（ＷＡＮ）２７９である。そうしたネットワーク環境は、オフィス、企業ワイドのコンピュータネットワーク、イントラネット、およびインターネットでは一般的である。
【００３９】
ＬＡＮネットワーク環境で使用するとき、コンピュータ２３０は、ＬＡＮ２７７のネットワークインターフェースまたはネットワークアダプタ２８６に接続される。ＷＡＮネットワーク環境で使用するとき、コンピュータは、典型的に、ＷＡＮ２７９を介する通信を確立するモデム２７８または他の手段を含む。内部または外部にあることが可能なモデム２７８は、ユーザ入力インターフェース２７０または他の適切な機構を介して、システムバス２３６に接続することができる。
【００４０】
図２に描かれているのは、インターネットを介するＷＡＮの特定の実施態様である。インターネットを介して、コンピュータ２３０は、典型的に、インターネット２８０を介して通信を確立するモデム２７８または他の手段を含む。内部または外部にあることが可能なモデム２７８は、インターフェース２７０を介してバス２３６に接続されている。
【００４１】
ネットワーク化された環境では、パーソナルコンピュータ２３０に関連して描いたプログラムモジュール、またはその部分は、遠隔メモリ記憶装置内に記憶することができる。例として制限するものではなく、図２は、遠隔アプリケーションプログラム２８９が、遠隔コンピュータ２８２のメモリデバイス上に常駐しているものとして示している。図示して説明するネットワーク接続は、例であり、コンピュータ間で通信リンクを確立する他の手段も使用できることが理解されよう。
【００４２】
図２は、記載する技法をそこで実施することができる適切な動作環境２２０の例を示している。詳細には、記載する技法は、図２の任意のプログラム２６０〜２６２またはオペレーティングシステム２５８によって実施され得る。
【００４３】
この動作環境は、単に、適切な動作環境の例であり、記載する技法の機能性の使用の範囲に関するどのような制限も示唆することを意図するものではない。記載する技法と共に使用するのに適切であり得る他のよく知られたコンピュータシステム、環境および／または構成には、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイスまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、プログラム可能な家庭用電化製品、ワイヤレス通信装置、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記システムまたはデバイスいずれかを含む分散コンピュータ環境などが含まれるが、それらには限定されない。
【００４４】
記載する技法の実施態様は、１つまたは複数のコンピュータまたは他のデバイスによって実行される、プログラムモジュールなどのコンピュータ実行可能命令の一般的文脈で説明することができる。一般的に、プログラムモジュールには、特定のタスクを実行する、または特定の抽象的データタイプを実施する、ルーチン、プログラム、オブジェクト、構成要素、データ構造などが含まれる。典型的には、プログラムモジュールの機能性は、様々な実施形態で所望に応じて、組み合わせ、または分散させることが可能である。
【００４５】
記載する技法の実施態様は、何らかの形態のコンピュータ可読媒体上に記憶する、あるいはそれを介して伝送することができる。コンピュータ可読媒体は、コンピュータによってアクセスできる任意の入手可能な媒体であり得る。例として制限するものではなく、コンピュータ可読媒体は、コンピュータ記憶媒体および通信媒体を含み得る。
【００４６】
コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報を記憶するための任意の方法または技術で実施される揮発性および不揮発性の、取外し可能および取外し不可能な媒体が含まれる。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタルバーサタイルディスク（ＤＶＤ）または他の光ストーレッジ、磁気カセット、磁気テープ、磁気ディスクストーレッジまたは他の磁気記憶装置、あるいは所望の情報を記憶するのに使用でき、コンピュータによってアクセスすることができる任意の他の媒体が含まれるが、それらには限定されない。
【００４７】
通信媒体は、典型的に、コンピュータ可読命令、データ構造、プログラムモジュール、あるいは搬送波または他のトランスポート機構などの変調されたデータ信号内の他のデータを具現化し、これには任意の情報送達媒体が含まれる。「変調されたデータ信号」という用語は、その特性セットのうちの１つまたは複数を有する信号、またはその信号内に情報を符号化するような方式で変更された信号を意味する。例として制限するものではなく、通信媒体には、ワイヤドネットワークまたは直接ワイヤ接続などのワイヤ媒体、および音響媒体、ＲＦ媒体、赤外線媒体、または他のワイヤレス媒体などのワイヤレス媒体が含まれる。上述した媒体のどの組合せも、また、コンピュータ可読媒体の範囲内に含まれる。
【００４８】
（同期ＴＣＰソースおよび振動）
このセクションでの議論は、本発明の実施形態をそこで使用することができるネットワーク環境の振動する性質を例示するのを助けるシミュレーションに関する。説明するシミュレーションは、下記のことから構成される。毎秒４０００パケットの容量（すなわち、１ｋＢの名目のパケットサイズの場合、３２Ｍｂ／秒）を有する単一のボトルネックリンクが、図３に示すとおり、いくらかのバックグラウンドの非反応的な（unreactive）トラヒックを搬送し、これが、全帯域幅のおよそ１０％を使用する。加えて、５０人の反応的な（reactive）ユーザが、残りの帯域幅を競い合っている。これらのユーザは、すべて、０．１秒に等しい往復伝搬遅延を有する。パケットは、ボトルネックキューからのその発信時に、その後ろに少なくとも１０個のパケットがキューにある場合に、ボトルネックリソースでＥＣＮマークを受信する。キュー長は、損失が決して起きないように、十分に高く（例えば、５００パケット）設定されている。
【００４９】
５０人すべてのユーザが、ＥＣＮを認識するＴＣＰを実行するとき、キューサイズは、図４のように振る舞う。同期および振動の振舞いが、明らかに見られる。この効果をさらに例示するため、ミリ秒毎にサンプリングされ、ボトルネックによって生成されたマークの数が与えられたプロセスを考慮されたい（その場合、インターバル中に０個から４個のマークが存在し得る）。
【００５０】
図５は、時間および周波数の分析をプロットしている。図５（Ａ）は、自己相関関数（correlogram）であり、図５（Ｂ）は、そのデータの１０秒間のスナップショットに対するピリオドグラム（periodogram：自己相関関数の変換）である。図５（Ｃ）は、そのデータの生の高速フーリエ変換であり、図５（Ｄ）は、インターバル当りのマークの数が０または１であることを確実にするより細かい初期サンプリングに基づく、ハールウェーブレットを使用する離散ウェーブレット変換のエネルギーレベルである。
【００５１】
これらの図のすべては、同じメッセージを伝えている、すなわち、「マーク」信号には、正と負の両方の相関を有する強い周期成分が存在し、また、このセットアップの振動の最も強い周期は、およそ０．５秒（数回の往復時間）である。より正確には、このピリオドグラムから、最も強い信号は、１０秒間隔当り２３サイクルの周波数にあり、したがって、その周期は、１０／２３＝０．４３秒である。このウェーブレット分解は、０．１ミリ秒のサンプルに基づいており、最も強いエネルギーは、０．４秒の周期に関係するスケール１２（すなわち２１２）である。
【００５２】
実際に、個々には、集合したマークではなく、自分のマークだけを見る。このサンプリングは、より雑音の多い信号をもたらし、図６が、図５よりは小さい振幅ではあるが、同様の周期を有する個々の信号の自己相関関数およびピリオドグラムを使用して、情報の低下を示している。言い換えれば、周期構造は残るが、個々のユーザに関して周期を推定することはより難しい。
【００５３】
（スムースＴＣＰ）
輻輳回避モードでは、ＴＣＰは、ＥＣＮマークが受信されたとき、その輻輳ウインドウｃｗｎｄを半分にして、マークのない肯定応答が受信されたとき、それを１／ｃｗｎｄだけ増大させる。同じ均衡点に達するようにこれらの規則を適合するが、それをよりスムースに行う多くの可能な方式が存在する。例示のシミュレーションで使用するものは、マークのないＡＣＫを受信したとき、１／（ｃｗｎｄ）２だけｃｗｎｄを増大させ（線形増加ではなく、対数増加）、マークを受信したとき、それを１／２に縮減してから（乗法的縮小ではなく、減算）、タイムアウトモードに入ることに相当する。単純な流動モデルが、実際に、ＴＣＰソースと同じ均衡点を求めるが、適合レートがｃｗｎｄによって分割されることを示す。ＴＣＰおよびスムースＴＣＰに関するｃｗｎｄの展開を図７に示す。これは、マーク付けの確率が固定されたままにされる場合、同じスループットをもたらすが、マーク付けの振舞い自体が、その負荷によって影響を受け、スムースＴＣＰの集合は、よりスムースな負荷を生成すると推測され、よりバースト性の低いマーク付けにつながり、したがって、所与のスループットに対してより低いマーク付けの比率につながる。
【００５４】
上述の同じシミュレーションを考慮されたい。５０人のユーザの各々に対する公平なシェアは、毎秒、およそ７２パケットである。表１（図８）は、ＴＣＰがスムースＴＣＰによって次第に置き換えられるにつれて、送信されマーク付けされるパケットを提示している。これは、どのようにスムースＴＣＰがフローを平滑化し、一般に、より少ないマークの利用を増大させ、典型的には、各ＴＣＰフローより、より少ないマークと、およそ８％多いスループットとを有することを示している。
【００５５】
スループットは確率的であり、図９は５０のフローに関し、４９が通常のＴＣＰフロー（図９（Ａ））であり、１つだけが通常のＴＣＰフロー（図９（Ｂ））である場合での、個々の送信レートおよびマークレートを示している。個々の値の変動にもかかわらず、ＴＣＰソースをスムースＴＣＰソースで置き換えることによって実現される改善は明らかである。
【００５６】
（予測ＴＣＰ）
このセクションは、エンドユーザが、自らのフィードバック履歴から、現行のネットワーク状況を推測することを可能にする予測スキームを提供する本発明の実施形態を説明する。以下に与えられた説明を考える１つの考え方は、次のとおりである。上述したとおり、ネットワーク輻輳は、典型的に、周期的な性質を有する。つまり、ネットワーク環境のダイナミックスのため、輻輳周期は、相当に規則的で反復可能な周期を有する傾向がある。１を輻輳であると見なし、また０を非輻輳と見なして、１と０の間で振動する規則的な方形波の類似を考慮されたい。下記の本発明の手法は、ネットワーク輻輳の周期性を見て、次に、この周期性に基づいて将来のある時点でのネットワークの状態を予測する。したがって、本発明の手法は、適当な程度の確実性をもって、どこで方形波１および０が起きる可能性が高いかを確かめることができる。
【００５７】
図１０は、開示された実施形態による処理ステップを一般的に説明する流れ図である。この方法は、適切なハードウェア、ソフトウェア、ファームウェア、またはその組合せで実施することができる。さらに、この方法は、ネットワークコンピュータ環境内の適切なロケーションでも、例えば、パーソナルコンピュータ装置、サーバなどの上でも実行することができる。
【００５８】
ステップ１０００は、ネットワーク輻輳に関する、または何らかの形でそれを示すネットワーク動作条件を監視する。これらの動作条件は、現在、利用されている、または将来、利用される可能性のある任意の適切な条件であり得る。これらの動作条件は、本例では、ネットワークフィードバックの形態で実現され、これには、示している例では、制限するものではなく、パケット損失イベントまたはパケット損失通知、あるいはＥＣＮマークなどのバイナリフィードバックメッセージが含まれる。これらの条件を監視することによって、ネットワーク輻輳の周期および非輻輳周期を確かめることができる。ステップ１００２は、監視された動作条件に基づいて、将来のある時点でのネットワーク輻輳を推定する。つまり、動作条件によって明らかにされる輻輳および非輻輳の周期を観察することによって、本発明の方法は、将来の輻輳の周期を予測することができる。ステップ１００４は、推定されたネットワーク輻輳の信頼度を計算する。任意の適切な信頼度でも使用することができる。信頼度判定の特定の統計的一例を下記に示す。ステップ１００６は、推定されたネットワーク輻輳（および、それが適切な場合、その推定の信頼性）に鑑みて、パケットがネットワーク輻輳に遭遇する可能性が高いかどうかを確かめる。パケットがネットワーク輻輳に遭遇する可能性が低いことをステップ１００２によって提供される推定が示す場合には、ステップ１００８は、そのパケットを送信または伝送する。そうではなく、パケットが遅延する可能性が高いことをその推定が示す場合には、ステップ１０１０は、そのパケットの伝送を遅延させる。パケットは、任意の適切な期間、あるいはパケットが輻輳に遭遇する可能性が低いことをネットワーク輻輳の推定が示していると思われるまで遅延させることができる。この方法は、好都合に、ネットワークの動作条件を継続的に監視して、輻輳推定が適時であるようにする。
【００５９】
（特定の実施態様）
下記の議論は、ネットワーク輻輳に関する予測的推定をそこで行い、パケット伝送動作を変更するのに使用することができるフィードバックシステムを実行するために、１つの特定の詳細な方法だけを提示する。これは、単に一例だけを成すことが認められ、理解されよう。したがって、請求する主題の趣旨および範囲を逸脱することなく、他の手法も利用することができる。
【００６０】
将来でのネットワーク輻輳を予測するタスクは、一般的かつ数学的には、次のように説明することができる。１セットの時刻t1<...<tn、および｛０，１｝の値をとる対応する信号Y(t1)...Y(tn)を所与として、ある後の時刻t>tnで受信されるフィードバックY(t)の値をどのように推測するか。所望の戦略がオンラインで実行され、したがって、最も単純なパターンを観察されるデータに当てはめることを試みなければならない。すなわち、データに下記のタイプの周期プロフィールをマッチさせることを試みる。
【００６１】
【数１０】
0004703063.tif 000002
【００６２】
将来の時刻ｔでのフィードバック値を予測するため、過去の観察から計算されるべき次の４つの変数だけを利用する。Ω０，Ω１は、それぞれ、０（非輻輳）状態および１（輻輳）状態での滞在時間の推定である。last_tは、フィードバックプロセスが、１つの状態から別の状態に変化した（すなわち、０から１に、または１から０にジャンプした）最後の時刻の推定である。そして最後に、last_stateは、時刻last_tでフィードバックプロセスが入ったはずの状態である。これらの４つの変数に基づいて、次の推定が戻される。
【００６３】
【数１１】
0004703063.tif 000003
【００６４】
新しい観察から、すなわち、フィードバックY(tn+1)が与えられたある時点ｔｎ＋１で、変数Ω０，Ω１，last_t，last_stateを更新するために、下記の規則を利用する。新しく観察されたフィードバックY(tn+1)と前のフィードバックY(t)が一致するときには、何も変更が行われない。状態変化が起きているときには、下記の更新が行われる。
【００６５】
【数１２】
0004703063.tif 000004
【００６６】
これらの方程式の背後にある動機付けは、次のとおりである。２つの観察、例えば、tnおよびtn 1での０および１を所与として、これらの２つの時刻間に、フィードバックで１回だけ状態変化が起きたと想定し、また、さらに、それが正確に中間点である(tn tn 1)/2で起きたと想定する。このことから、正確に(tn tn 1)/2 last_tという状態０での滞在時間が観察されたと想定する。Ω０に関する更新規則は、状態０で想定される「真の」滞在時間について、従来の指数的に加重された移動平均（ＥＷＭＡ）の推定である。パラメータＨは、原則として、０と１の間のどの値でもとることが可能である。それを１に等しくすることが、常に、現行の推定で最後のサンプルに使用される。これは、ほとんどのサンプルが同一の値をとるように同期されている多くの状況において適切である。
【００６７】
したがって、上述した処理は、将来のある時点でネットワーク輻輳が経験されることになる可能性の予測を可能にする。本発明の手法は、観察可能なネットワーク輻輳に関連するプロフィールをそれに関連する様々なパラメータの点から特徴付ける。この特徴付けに基づいて、その輻輳のプロフィールが、将来に数学的に投射される。下記に見るとおり、輻輳プロフィールのこの投射は、次に、ユーザの行動、例えば、パケット伝送の基準としての役割をすることが可能である。
【００６８】
（信頼度）
上述の技法を補完するため、
【００６９】
【外３】
0004703063.tif 000005
【００７０】
を予測することに加えて、この予測または推定に対して有する信頼の程度を提供することが役に立つと判明している。そうするためには、状態０および１での滞在時間の変動の推定を更新しなければならない。更新は、状態の変化が観察された時点で行われ、また、ＥＷＭＡ方程式によって行われる。この方程式は、当分野の技術者には、理解され、その価値が認められよう。
【００７１】
【数１３】
0004703063.tif 000006
【００７２】
パラメータＨχは、前のパラメータＨとは異なり得ることに留意されたい。実際、この文書で報告するすべての実験で、Ｈχ1/2である。次に、前記方程式によって与えられる推定の
【００７３】
【外４】
0004703063.tif 000007
【００７４】
を有する信頼を推定する。そうする上で、次の統計的仮定が行われる。連続するマーク付け周期は、iidであり、平均値Ω１および分散Ｖ１を有し、やはりiidであり、平均値Ω０および分散Ｖ０を有する後続の非マーク付け周期とは独立している。さらに、状態の変化は、正確にlast_tで起きると想定する。推定の
【００７５】
【外５】
0004703063.tif 000008
【００７６】
は、last_tからｔまでの交互するマーク付けおよび非マーク付け周期が、正確にその予期される持続時間、持続する場合には、完全に信頼できるものとなる。例えば、図１１に図示する状況を考慮されたい。ここで、推定の
【００７７】
【数１４】
0004703063.tif 000009
【００７８】
が戻される。ｔが非マーク付け周期に対応する間隔[t-,t+)内にあると想定されるためである。しかしながら、その確率分布が正の分散を有するとき、マーク付け間隔および非マーク付け間隔は、その予期される値とは異なることになる。この場合も、図１１の例から、[t-,t+)と一致すると想定される非マーク付け周期は、わずかに異なるエンドポイントを有する、すなわち、それは、[t-+Δt-, t++Δt+]から成る。この場合、行った統計的仮定の下で、ランダム変数Δt-,Δt+は、それぞれの分散V-=2(V0+V1)およびV+=2(V0+V1)+V0を有する。予測
【００７９】
【数１５】
0004703063.tif 000010
【００８０】
は、下記の条件が成立するとすれば、確実に正しいことになる。
Δt-<t-t-, and Δt+>t-t+
【００８１】
チェビチェフの不等式を使用することによって、これらのイベントが起きない確率は、下記によって上限が定められる。
【００８２】
【数１６】
0004703063.tif 000011
【００８３】
Δｔ変数の分布がゼロのまわりで対称的であるとさらに想定すると、上限は、２によってさらに割ることができる。また、考慮する２つのイベントは互いに排他的であり、したがって、それらの結合の確率は、それらの確率の合計に等しいことにも留意されたい。
【００８４】
要約すると、次の推定が得られる。
【００８５】
【数１７】
0004703063.tif 000012
【００８６】
パラメータｔ±およびＶ±に関する方程式は、容易に導出することができ、したがって、この限界は、実際に計算することができる。結果の限界は、チェビチェフの不等式を利用すると、極めて緩いものであり得る。より明瞭な限界は、マーク付け持続時間および非マーク付け持続時間が、固定確率分布によって分布していると想定することによって得られる。例えば、これらの持続時間がガウス分布であると想定すると、より締まった限界を標準正規分布の分位数から計算することができる。推定の
【００８７】
【外８】
0004703063.tif 000013
【００８８】
とともにそれが正しいことの確率に関する下限（細い線）、これはチェビチェフ不等式またはガウス分布のいずれかの結果である推定の
【００８９】
【外９】
0004703063.tif 000014
【００９０】
に対する信頼の程度を、図１２にプロットする。
【００９１】
（例としての輻輳制御アプリケーション）
上述の方法は、パフォーマンスに有利に影響を与えることが可能なエンドユーザ制御システムに関連して実行することができる。下記に見るとおり、本発明の方法は、いわゆる「振動を認識」するユーザに関してだけでなく、「振動を認識」していないユーザに関しても、そのパフォーマンスに影響を与えることができる。
【００９２】
（受動的予測器（Passive Predictor)）
５０のソースすべてが、標準ＥＣＮを認識するＴＣＰを使用し、１つのソースに予測器モジュールを追加して、これが上述した手法により計算されたΩ０，Ω１，last_t，last_state，Ｖ０およびＶ１の値を記憶する場合を考慮する。ただし、このソースは、予測器モジュールからの影響なしに、そのＴＣＰモジュールにより、いつパケットを送信するかを判断する。
【００９３】
図１３および１４は、それぞれ、Ω０，Ω１の連続する推定を示し、これらは、それぞれ、幅
【００９４】
【外１０】
0004703063.tif 000015
【００９５】
の誤差バーを有している。観察されたマーク付け持続時間および非マーク付け持続時間が、ほとんどの場合、固定値と一致することが明らかに見られ、これは、マーク付け周期が予測可能なはずである。例えば、マーク付け持続時間は、典型的に０．１秒の間であり、これは、５０ソースすべての往復伝搬遅延である。
【００９６】
図１５は、タグ付きソースによって送信されるパケットの予測される状態および実際の状態を提示し、図１６は、それに関連する信頼を示している。
【００９７】
（能動的予測器）
次に、さらなる議論で「予測ＴＣＰ（Pred TCP）」ソースと呼ぶいくつかのソースが、次の方式で変更される。これらのソースは、ＴＣＰを実行するが、パケットが時刻ｔで通常に送信されるとき、このパケットがマーク付けされる可能性が高いかをＴＣＰが予測器に尋ねる。予測値
【００９８】
【外１１】
0004703063.tif 000016
【００９９】
が１に等しく、かつ予測器がこれについて確信を有する場合、すなわち、上述のとおり計算される量p-およびp+が、ある信頼レベルσに関して、p-+p+<σを検証する場合、ＴＣＰは、そのパケットを送信する資格がなく、マークが付けられることを予測器がもはや確信していない次の時刻を待たなければならない。
【０１００】
図１７は、ＴＣＰソースを予測ＴＣＰソースによって置き換えることの影響を示す表である。
【０１０１】
図１８は、様々な数の予測ＴＣＰソースに関するグローバルレートのグラフである。ＴＣＰソースを予測ＴＣＰソースで置き換えることは、全体の利用をわずかに低減させるが、マークを受けないパケットがそこで送信されるレートを増加させることに留意されたい。
【０１０２】
図１９は、様々な数の予測ＴＣＰソースの個々のレートのグラフである。このグラフは、ＴＣＰソースを予測ＴＣＰソースによって置き換えることによって、ＴＣＰソースと予測ＴＣＰソースの両方が、その送信レートを増加することに留意されたい。最後に、図２０は、ＴＣＰソースを予測ＴＣＰソースによって置き換えることのマーク付けレートに対する影響を示している。詳細には、予測ＴＣＰソースは、ＴＣＰソースよりもわずかに小さいマーク付けレートを得るが、その導入は、ＴＣＰソースによって実現されるマーク付けレートを低下させる。したがって、実験結果は、より小さなマーク付けレートを得ることによって、ＴＣＰに対する改善を実現するのが可能であることを示し、これは、ＴＣＰソースに改善が共有されることで、「ＴＣＰフレンドリ」なままである。また、スムースＴＣＰの場合と同様に、反応性が犠牲にされていないことにも留意されたい。興味深いことに、図２０は、バックグラウンドトラヒックが、典型的に、最小のマーク付けレートを受けることを示している。したがって、反応性の欠如は、スムースＴＣＰの場合と同様に、この場合も割に合うように思われる。
【０１０３】
図２１は、例としての予測システム内にある様々な構成要素の概念上の階層化を記述するプロトコル階層化スキーム２１００を示している。パケット分類器２１０２は、インターネットなどのネットワークを介して送信するためにパケットをスケジュールするパケットスケジューラ２１０４を含む。ＴＣＰ２１０６は、この階層化スキーム内で、ＩＰ２１０８の上に常駐して、パケットスケジューラ２１０４によってスケジュールされたＩＰパケットをネットワークインターフェース上で生成する。予測アルゴリズム構成要素２１１０は、ＴＣＰ２１０６の上に常駐して、上述したとおり、ネットワークから受信された情報に関連して動作する。予測器モジュール２１１２は、パケットスケジューラ２１０４とリンクされて、予測器によって展開された情報が、パケットスケジューラ２１０４によって使用され、予測された輻輳状況に応じて、パケットを遅延またはスケジュールを行う。これは、ＴＣＰが、通常どおりに動作することを可能にする、つまり、ＴＣＰは単に伝送のためにパケットを作成し、次に、パケットスケジューラ２１０４によって管理される。パケットスケジューラ２１０４は、次に、予測器２１１２によって提供された情報に反応する。
【０１０４】
上述のシステムは、必ずしもＴＣＰだけでなく、他のプロトコル、例えば、ＥＣＮストリーミングプロトコルなどに関連して利用できることを理解されたい。
【０１０５】
上述した実施形態は、したがって、インターネットなどの遠隔通信ネットワーク内での輻輳周期の予測を可能にして、データがネットワークに送り込まれるレートを変更できるようにする。エンドシステムまたはエンドユーザにとっての１つの利益は、向上した「グッドプット（goodput）」（有効スループット）であり、またネットワークにとっての利益は、向上した効率／利用および過負荷防止である。ユーザに対し、何らかの形式の輻輳価格付けを介して輻輳が調停されるような場合には、ユーザにとっての利益は、所与のスループットに対するより低い価格でもあることになる。
【０１０６】
前述した実施形態は、いくつかの方式で実施することができる。例えば、アプリケーションをコンピュータ上で提供して、これは、損失パケットという形で、または特定の実施態様で、輻輳情報に反応する。ここで、ＥＣＮマークと、輻輳間隔を予測して、輻輳が予測されるときに低いレートで、また輻輳の可能性が低いときに、高いレートでパケットを送信することによってなされる。別法では、プログラムされたデバイスが、コンピュータ（または複数のコンピュータ、ＬＡＮなど）とネットワークとの間に提供され、輻輳周期を推定し、コンピュータ（または複数のコンピュータ、ＬＡＮなど）の送信レートを中断することが可能である。特定の実施態様では、これは、トランスポート層でパケットの肯定応答（ＡＣＫ）を遅延させることによって実現することが可能である。これは、単一のチャネルまたはチャネルの集合に適用することができる。
【０１０７】
（結論）
記載した実施形態は、いくつかのソースの輻輳回避の振舞いを変更することによって、ネットワークリソースの利用において振動を抑えるのに適用することができる。変更されたソースを導入することによって、すべてのソースにより、つまり、まだ標準ＴＣＰ実施態様を使用しているソースによってさえも、利益が享受される。
【０１０８】
本発明は、構造的特徴および／または方法ステップに固有の言語で説明してきたが、添付する請求項で定義される本発明は、必ずしも記載した特定の特徴またはステップに限定されないことを理解されたい。むしろ、特定の特徴および特定のステップは、請求する発明を実施する好ましい形態として開示している。
【図面の簡単な説明】
【図１】本発明の実施形態をそこで使用することができる例としてのネットワークを示すブロック図である。
【図２】記載する実施形態を実施する際に使用するのに適したコンピュータシステムを示すブロック図である。
【図３】バックグラウンドトラヒックの着信レートを表すグラフである。
【図４】キューサイズの振動を表すグラフである。
【図５】集合マークに関するデータ分析を表す４つのグラフを含む図である。
【図６】個々のマークのデータ分析を表す２つのグラフを含む図である。
【図７】（ａ）ＥＣＮ認識ＴＣＰおよび（ｂ）スムースＴＣＰでの輻輳ウインドウ展開を表す２つのグラフを含む図である。
【図８】様々な数のＴＣＰストリームおよびスムースＴＣＰストリームに関する送信レートおよびマーク付きパケットの比率を表す表である。
【図９】（ａ）４９のＴＣＰと１つのスムースＴＣＰ、（ｂ）１つのＴＣＰと４９のスムースＴＣＰにおける、送信レートおよびマーク付けレートを表す２つのグラフを含む図である。
【図１０】記載する実施形態にかかる方法のステップを表す流れ図である。
【図１１】記載する実施形態にかかる予測値対実際値を示すグラフである。
【図１２】チェビチェフ不等式およびガウス分布に基づいて予測値およびそれに関連する信頼を示すグラフである。
【図１３】受動的予測器によって収集されたΩ０に関する信頼間隔および推定を示すグラフである。
【図１４】受動的予測器によって収集されたΩ１に関する信頼間隔および推定を示すグラフである。
【図１５】受動的予測器によって収集された実際の状態および予測される状態を示すグラフである。
【図１６】受動予測器によって行われた予測の信頼を示すグラフである。
【図１７】様々な数のＴＣＰストリームおよび予測ＴＣＰストリームに関する送信レートおよびマーク付きパケットの比率を表す表である。
【図１８】様々な数の予測ＴＣＰソースに関するグローバルレートを表すグラフである。
【図１９】様々な数の予測ＴＣＰソースに関する個々のレートを表すグラフである。
【図２０】様々な数の予測ＴＣＰソースに関するマーク付けレートを表すグラフである。
【図２１】記載する実施形態にかかるプロトコル階層化スキームを示す図である。
【符号の説明】
１０１、１０３  クライアント
１０４、１０８、１０９  インターネットサービスプロバイダ接続
１０５  クライアントマシン
１０６、１１０  ゲートウェイ／トンネルサーバ
１０７  インターネット
１１１  接続
１１２、１１３、１１４  企業アプリケーションサーバ
１１５  ハブ／ルータ
１１６、１１７、１１８  ローカルクライアント
２２０  コンピュータ環境
２３０  パーソナルコンピュータ
２３２  処理装置
２３４  システムメモリ
２３６  バス
２３８  読取り専用メモリ
２４０  ランダムアクセスメモリ
２４２  入力／出力システム
２４４  ハードディスクドライブ
２４６  磁気ディスクドライブ
２４８  不揮発性磁気ディスク
２５０  光ディスクドライブ
２５２  不揮発性光ディスク
２５４  データ媒体インターフェース
２５８  オペレーティングシステム
２６０  アプリケーションプログラム
２６２  他のプログラム
２６４  プログラムデータ
２６６  キーボード
２６８  ポインティングデバイス
２７０  ユーザ入力インターフェース
２７２  モニタ
２７４  ビデオアダプタ
２７５  出力周辺インターフェース
２７７  ローカルエリアネットワーク
２７８  モデム
２７９  ワイドエリアネットワーク
２８０  インターネット
２８２  遠隔コンピュータ
２８６  ネットワークアダプタ
２８９  遠隔アプリケーション
【図１】
0004703063.tif 000025
【図２】
0004703063.tif 000026
【図３】
0004703063.tif 000027
【図４】
0004703063.tif 000028
【図５】
0004703063.tif 000029
【図６】
0004703063.tif 000030
【図７】
0004703063.tif 000031
【図８】
0004703063.tif 000032
【図９】
0004703063.tif 000033
【図１０】
0004703063.tif 000034
【図１１】
0004703063.tif 000035
【図１２】
0004703063.tif 000036
【図１３】
0004703063.tif 000037
【図１４】
0004703063.tif 000038
【図１５】
0004703063.tif 000039
【図１６】
0004703063.tif 000040
【図１７】
0004703063.tif 000041
【図１８】
0004703063.tif 000042
【図１９】
0004703063.tif 000043
【図２０】
0004703063.tif 000044
【図２１】
0004703063.tif 000045