(57)【要約】【課題】  ＩＰネットワークの経路に沿った帯域容量、利用可能帯域幅、および利用を推定する方法を提供する。【解決手段】  ＩＣＭＰタイムスタンプ要求は、ネットワークの端部あるいは内部に位置する送信元ホストから、所望の宛先までのエンド・ツー・エンドの経路上のすべてのルータに送信される。タイムスタンプ値の差は、各ルータにおけるＱｏＳサービスの指標として用いられる。収集された測定結果は、経路の容量（ビット／秒）、利用可能帯域幅（ビット／秒）、個々のリンクの利用および各ルータにおける輻輳の観点からＱｏＳパラメータを推定するため送信元ホストで処理される。これらのパラメータは、エンド・ツー・エンドの経路の帯域幅の観点からＱｏＳサービスを推定するために組み合わされる。【選択図】      図４
2004312725.tif 000002
【特許請求の範囲】
【請求項１】
無線リンク全体の粗容量を得るステップと、
パケット輻輳を推定するステップと、
利用可能な粗リンク容量の量を決定するステップと、
前記利用可能な粗リンク容量の量に基づいてＱｏＳ値を算出するステップと
を有する方法。
【請求項２】
リモート端末に到達する第１のパケットに対するキューイング遅延を決定するステップをさらに有する請求項４５に記載の方法。
【請求項３】
前記キューイング遅延を決定するステップが、
アクセスルータの輻輳キューにおいて前記第１のパケットに先行する第２のパケットに対する総送信回数と、
前記第２のパケットの１回以上の再送信に対するコンテンション時間と、
再送信を決定するまでのタイムアウト遅延と、
前記無線リンクを通じた前記第１のパケットに対する送信遅延と、
前記無線リンクを通じた前記第１のパケットに対する伝播遅延と、
前記第２のパケットがコンテンションキューの先頭に到達するまでに消費する時間と
に基づいてキューイング遅延を決定することを特徴とする請求項４６に記載の方法。
【請求項４】
前記キューイング遅延を決定するステップが、少なくとも１部、
アクセスルータの輻輳キューにおいて前記第１のパケットに先行する前記第２のパケットに対する総送信回数と、
再送信されたフレームの数と、
リトライの最大値を超えたフレームの数と、
平均コンテンション時間と
に基づいてキューイング遅延を決定し、
前記総送信回数が無事送信されたフレームの数に基づいたものであることを特徴とする請求項４６に記載の方法。
【請求項５】
前記キューイング遅延を決定するステップが、少なくとも１部、
アクセスルータの輻輳キューにおいて前記第１のパケットに先行する第２のパケットに対する総送信回数に基づいてキューイング遅延を決定し、前記総送信回数が無事送信されたフレームの数に基づいたものであることを特徴とする請求項４６に記載の方法。
【請求項６】
ネットワークの有線部分に対する平均パケット損失の値を測定するステップと、
エンド・ツー・エンドのネットワーク経路における無線リンクに対するパケット損失の値を、前記ネットワークの有線部分のパケット損失の値の関数として算出するステップと
をさらに有する請求項４９に記載の方法。
【請求項７】
前記経路上のホップに対しｐｉｎｇ要求を送信するステップと、
ｐｉｎｇ応答を受信するステップと、
ＱｏＳ推定値を生成するために前記ｐｉｎｇ応答を処理するステップと
をさらに有する方法。
【請求項８】
送出するパケットを蓄積するキューと、
現在の無線リンクの全体の粗容量を得、パケット輻輳を推定し、利用可能な粗リンク容量の量を決定し、前記利用可能な粗リンク容量の量に基づいてＱｏＳ値を算出するために前記キューに接続されるＩＰ処理部と
を有するルータ。
【請求項９】
前記ＩＰ処理部が、リモート端末に到達する第１のパケットのキューイング遅延を決定することを特徴とする請求項５２に記載のルータ。
【請求項１０】
前記ＩＰ処理部が、ネットワークの有線部分に対する平均パケット損失を測定し、エンド・ツー・エンドのネットワーク経路における無線リンクに対するパケット損失の値を、前記ネットワークの有線部分に対する前記パケット損失の値の関数として算出する
ことを特徴とする請求項５２に記載の方法。
【請求項１１】
前記ＩＰ処理部が、
前記経路上のホップにｐｉｎｇ要求を送信し、
ｐｉｎｇ応答を受信し、
ＱｏＳ推定値を生成するために前記ｐｉｎｇ応答を処理する
ことを特徴とする請求項５２に記載の方法。
【請求項１２】
システムに、
現在の無線リンクの全体の粗容量を取得させ、
パケット輻輳を推定させ、
利用可能な粗リンク容量の量を決定させ、
前記利用可能な粗リンク容量の量に基づいてＱｏＳ値を算出させる
命令を記憶する１以上の記録可能な媒体を有する製品。
【請求項１３】
エンド・ツー・エンドの経路上のルータの容量を特定するために当該エンド・ツー・エンドの経路を測定するステップと、
ｐｉｎｇ要求を前記経路上のホップに送信するステップと、
ｐｉｎｇ応答を受信するステップと、
ＱｏＳ推定値を生成するために前記ｐｉｎｇ応答を処理するステップと
を有する方法。
【請求項１４】
前記ホップが、ＩＥＥＥ８０２．１１無線ＬＡＮ上のホップを有することを特徴とする請求項５７に記載の方法。
【請求項１５】
システムに、
エンド・ツー・エンドの経路上のルータの容量を特定するために当該エンド・ツー・エンドを測定させ、
前記経路上のホップにｐｉｎｇ要求を送信させ、
ｐｉｎｇ応答を受信させ、
ＱｏＳ推定値を生成するために前記ｐｉｎｇ応答を処理させる
命令を記憶する１以上の記録可能な媒体を有する製品。
【請求項１６】
ネットワークの有線部分に対する平均パケット損失の値を測定するステップと、
エンド・ツー・エンドのネットワーク経路における無線リンクに対するパケット損失の値を、前記ネットワークの有線部分に対する前記パケット損失の関数として算出するステップと、
前記パケット損失の値に基づいてＱｏＳ値を算出するステップと
を有する方法。
【請求項１７】
システムに、
ネットワークの有線部分に対する平均パケット損失の値を測定させ、
エンド・ツー・エンドのネットワーク経路の無線リンクに対するパケット損失の値を、前記ネットワークの有線部分に対する前記パケット損失の値の関数として算出させ、
前記パケット損失の値に基づいてＱｏＳ値を算出させる
命令を記憶する１以上の記録可能な媒体を有する製品。
【請求項１８】
エンド・ツー・エンドの経路上の第１のホップにおいてｐｉｎｇ要求パケットを生成するステップと、
前記ｐｉｎｇ要求パケットを前記エンド・ツー・エンドの経路上の第２のホップに送信するステップと、
前記第１のホップにおいて、前記ｐｉｎｇ要求パケットに応じて前記第２のホップからｐｉｎｇ応答を受信するステップと、
前記ｐｉｎｇ応答の関数としてＱｏＳ値を算出するステップと
を有するネットワークのエンド・ツー・エンドの経路に対するＱｏＳの推定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰ通信ネットワークに関するものである。より詳細には、ＩＰネットワーク上の通信経路に対するサービスの品質（ＱｏＳ）の推定方法に関するものである。
【背景技術】
【０００２】
インターネットの「ベストエフォート」特性は、エンドユーザが認識するＱｏＳ（サービスの品質）を予想不能にし、また時には大きく変化させる。そのため、ＩＰネットワークのＱｏＳ性能を推定するための、早く、正確で、有効なツールは、ネットワーク通信において重要性を増している。これは、パケットネットワーク、特にインターネットに固有の時々刻々変化する条件下で予想されるユーザおよびプロバイダに対するサービスを維持するために、ＱｏＳに関する情報が使用されるためである。具体例としては、輻輳制御、リアルタイムストリーミングと双方向通信、ＱｏＳ検証、サーバの選択、およびネットワークの管理等が挙げられる。
【０００３】
ＱｏＳ推定方法は、大きく２つのカテゴリに分類することができる。それは、受動的推定方法と能動的推定方法である。受動的推定方法は、ネットワークに測定用の新たなトラフィックを必要としないという利点がある。受動的測定方法は、ネットワークをありのまま測定する。すなわち、測定のための測定トラフィックにより現在のネットワークが乱されることがないので、真のネットワーク挙動が測定される。
【０００４】
測定は、処理能力、記憶容量、および利用可能なリソースの程度により種々のレベルの細分性をもって行うことができる。パケット測定は、例えば、パケット遅延変化、パケットサイズ分布、およびホスト間のスループットのようなパケット毎の情報の測定を可能にする。より高レベルの、オーバーヘッドの少ない測定は、送信された総バイト数、フローの開始／終了時刻を記録するフローレベル測定により実現できる。
【０００５】
受動的測定技術の主な利点は、測定しようとするネットワークに負荷をかけない点である。これはまた、ネットワークのトラフィックを歪ませないため、実際のネットワーク状態に近い推定を可能にすることを意味する。しかしながら、受動的測定技術の欠点は、実際に存在するトラフィックに依存するので、そのトラフィックが、ある測定に必要とされる特性を有することが保証されないことである。ボトルネック帯域幅の測定技術は、例えば、一定のパケットサイズ分布、パケット間の出発速度を必要とする。トラフィック測定は、ネットワークの性能を推定する目的で受動的に測定トラフィックの特性を測定するものである。
【０００６】
ＳＮＭＰ（Ｓｉｍｐｌｅ  Ｎｅｔｗｏｒｋ  Ｍａｎａｇｅｍｅｎｔ  Ｐｒｏｔｏｃａｌ）およびＲＭＯＮ（Ｒｅｍｏｔｅ  Ｍｏｎｉｔｏｒｉｎｇ）は、受動的測定に最も広く採用されている標準的なものであり、様々なネットワーク要素（ホスト、ルータ、交換機）にインストールされた管理エージェントあるいは測定用のデータ、エージェントから収集されたデータを含むＭＩＢ（Ｍａｎａｇｅｍｅｎｔ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｂａｓｅ）、測定用のデータから情報を収集する管理局／コンソール、および管理局／測定用のデータ間での情報交換のためのプロトコルから構成される。ＭＩＢは、物理層あるいはＩＰ層で収集されたパケットサイズの統計、ＣＲＣ（巡回冗長検査）による誤り等の様々なグループを有する。管理制御を利用したトラフィック測定は、収集された情報をエージェントからコンソールに転送することを必要とする。測定対象であるネットワークへの負荷はこの程度である。時には、交換されるトラフィックの量を減少させるためにデータのサンプリングを使用することができる。
【０００７】
一方、能動的測定方法は、測定用のデータをネットワークに送信し、通信相手に送信されるまでの遅延、遅延の変化量、および損失の観点から測定用のデータが受ける処理を測定することによりネットワークのＱｏＳを推定する方法である。遅延、ジッタ、パケット損失、帯域幅といった観点から性能を推定するために、多様なツールが存在する。これらのツールは通常、インターネット制御メッセージプロトコル（ＩＣＭＰ）の誤り通報能力、あるいはパケット分散技術のいずれかを用いる。
【０００８】
ビット／秒単位でのリンクの情報路容量の推定は、伝統的にパケット分散技術を用いて行われてきた。パケット分散技術とは、２つ以上のパケットグループを継続的に送信することにある。それは、同一のグループからのパケットは、経路のボトルネックリンクにおいて次々に待たされる（キューイングする）という概念に基づいている。他の競合トラフィック（すなわち、他の発呼端末からのトラフィック）からの干渉がなければ、その分散（すなわち、受信先におけるパケット到着時間の差異）は、ボトルネックの帯域幅に反比例する。この方法を用いたツールの例としては、Ｎｅｔｔｉｍｅｒ、Ｐａｔｈｒａｔｅ、およびＰａｃｋｅｔ  Ｂｕｎｃｈ  Ｍｏｄｅ（ＰＢＭ）がある。
【０００９】
情報路容量推定の別の方法は、ＩＣＭＰの時間超過メッセージ（Ｔｉｍｅ  Ｅｘｃｅｅｄｅｄ  ｍｅｓｓａｇｅ）のオプションに基づくものである。この技術のはしりであるＰａｔｈｃｈａｒというツールは、ＩＰ寿命（ＴＴＬ）値を増加させながらパケットを送信することにより測定を行う。これにより、経路にあるルータは、ＩＣＭＰエラーメッセージを返信し、そのルータ自身を明らかにするのである。エンド・ツー・エンド（ｅｎｄ−ｔｏ−ｅｎｄ）の経路上の連続するホップに対する往復遅延の測定により、ホップ毎の遅延の測定が可能になる。Ｐａｔｈｃｈａｒはまた、各ＴＴＬ値に対してパケットのサイズを変化させる機能を有する。これにより、リンクの情報路容量を、各パケットサイズに対して測定された遅延の最小値を結ぶ線の傾きの逆数として推測するのである。ＰｃｈａｒやＣｌｉｎｋといった他のツールも存在するが、それらもＰａｔｈｃｈａｒと同一の概念に基づいている。
【００１０】
ＣｐｒｏｂｅおよびＰｉｐｅｃｈａｒは、経路上の利用可能な帯域幅を推定するために提案された最初のツールである。これらのツールは、長いパケットトレイン（複数のパケット）の分散を使用している。そのようなパケットトレインの分散は、ボトルネックのホップにおいて、送信に利用可能な速度、すなわち利用可能な帯域幅に反比例すると仮定している。しかしながら、最近の研究では、そのような分散の逆数では実際は利用可能な帯域幅を測定できず、ＡＤＲ（非対称データ速度）と呼ばれる別のパラメータを測定することになることが示されている。
【００１１】
Ｄｅｌｐｈｉという別のツールは、インターネット経路は単一のキューによりモデル化されると仮定している。その仮定によると、経路上のいくつかのリンクにおいて大きなキューイング遅延が存在する場合に、あるいは、ボトルネックの情報路容量とボトルネックの利用可能帯域幅リンクが異なるリンクに位置する場合は、Ｄｅｌｐｈｉの性能は悪化する。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
現在において、利用可能帯域幅を推定できるツールは、Ｐａｔｈｌｏａｄと呼ばれるツールしか知られていない。Ｐａｔｈｌｏａｄは、各々における送信速度を変化させ、受信先における遅延変化を測定する種々の反復処理を行う。その目的は、遅延増加を起こさない最大速度を発見することである。Ｐａｔｈｌｏａｄは、受信先で測定されるエンド・ツー・エンドの遅延は、発呼端末の送信速度が経路の利用可能帯域幅を超えたときに増加するという単純な原理に基づいている。現実的な測定では、ボトルネックが処理できる速度よりも高速で経路に注入されたトラフィックがそのホップでキューを起こし、それによりキューイング遅延および全体の遅延が増加することが知られている。
【課題を解決するための手段】
【００１３】
本発明は、ネットワークにおいてＱｏＳを推定する方法および装置に関するものである。一実施形態において、本発明の方法は、エンド・ツー・エンドの経路上のすべてのホップのアドレスを特定するためにエンド・ツー・エンドの経路を測定するステップと、少なくとも１つのタイムスタンプ要求パケットを生成するステップと、前記少なくとも１つのタイムスタンプ要求パケットをエンド・ツー・エンドの経路上の少なくとも１つのホップに送信するステップと、前記ホップにおいて前記タイムスタンプ要求パケットに応じてタイムスタンプを生成するステップと、少なくとも１つのＱｏＳ推定値を得るために前記タイムスタンプを処理するステップとを有する。
【００１４】
ＩＰネットワークにおける通信経路に対するＱｏＳ推定値を提供するための方法および装置を開示する。通信経路は、ＩＰネットワークにおける２つのルータあるいはホスト間の経路を指す。ＱｏＳ推定技術は、要求される通信経路にポーリングする通常の原理に基づいて使用される。好適な方法は、次のように構成される。まず、対象となるエンド・ツー・エンドの経路上の全てのルータ／ホストのネットワークアドレスを特定する。次に、複数組のタイムスタンプ要求を経路上の各ルータ／ホストに送信する。最後に、ＱｏＳ推定値を算出するために、ルータ／ホストから返信されたタイムスタンプ要求が処理される。本発明において、「ホップ」という語は、各ノード間のエンド・ツー・エンドの経路上にあるルータ／ホストを総称するために使用される。
【００１５】
一実施形態において、経路上のホップのアドレスを得るための技術は、Ｔｒａｃｅｒｏｕｔｅアプリケーションを使用する。加えて、一実施形態において、タイムスタンプ要求は、ＩＣＭＰタイムスタンプ要求／返信機能を使用して得られる。本発明は、要求される経路上の全てのホップのアドレスを決定するためにＴｒａｃｅｒｏｕｔｅを使用することから開始する。次に、１群のＩＣＭＰタイムスタンプ要求が、経路の一端の発呼端末から測定対象の経路上の各ルータに送信される。一実施形態において、１群のＩＣＭＰタイムスタンプ要求は、５つのＩＣＭＰタイムスタンプ要求から構成される。各グループの最初の３つのパケットは、対応するホスト／ルータ（すなわち、経路上のホップ）に対する測定の初期条件を決定するために使用される。５つのパケットからなるグループのうち残りの２つの測定パケットは、対応するホップにおいて、ＩＣＭＰ要求パケットにより費やされた時間の総和の推定値を得るために使用される。
【００１６】
さらに、もう１対の同様なＩＣＭＰタイムスタンプ要求パケットが、同様に各ホップでＩＣＭＰ要求により費やされた時間の合計を推定するために規則的な間隔で各ホップに送信される。そのような継続的測定は、各ホップにおけるキューイング遅延変化の推定のために使用される。本発明の好適な実施形態において、推定値は測定を開始した発呼元あるいはノードで算出される。さらに別の実施形態において、そのような推定値は受信先あるいは宛先ノードで算出される。
【００１７】
一実施形態において、各ホップにおけるサービス時間の合計およびキューイング遅延の変化は、各ホップにおいて経路方向の利用率の推定のために使用される。それは、リンクにおいて競合トラフィックに使用されていない、空いている送信リソースの部分を指す。算出される推定値はまた、経路方向の各リンクの利用可能な帯域幅の推定のために使用される。利用可能な帯域幅は、リンクが輻輳およびキューの発生なしにさらに維持することができる速度を指す。加えて、推定値は、競合する発呼端末からリンクに導入されるトラフィックの速度を推定するために使用される。
【００１８】
一実施形態において、ここで説明される技術は、ＱｏＳ測定を開始する、１つのノードにのみ存在するアプリケーションにより実行される。このノードは、ホップから収集されたタイムスタンプ値に基づいてＱｏＳ推定のために必要な処理を行う。別の実施形態において、このアプリケーションは、測定対象となる経路の発呼元および受信先の両方に存在してもよい。その場合、受信先は、収集されたタイムスタンプ値を処理する役割をもつ。その違いは、ルータに送信されたＩＣＭＰパケットは宛先に対しスプーフィングするアドレスを有し、したがって応答はＩＣＭＰ要求をした発呼元ではなく受信先に送信されることである。
【発明を実施するための最良の形態】
【００１９】
本発明のさらなる目的および利点は、本発明の好適な実施形態を示した図面を参照しながら以下の説明で明らかになる。
【００２０】
以下の説明において、細部についての多くの説明が、本発明の説明を介してより多くの説明を提供するために行われる。しかし、当業者にとって、本発明はこれらの特定の細部がなくても実施可能であることは明らかである。他の場合において、本発明を不明瞭にするのを避けるため、周知の構造および装置は詳細にではなく、ブロック図の形式で示される。
【００２１】
以下の詳細な説明のいくつかの部分は、コンピュータメモリ内のデータビット上の動作のアルゴリズムあるいは記号的表現で表される。これらのアルゴリズム的説明および表現は、データ処理の技術分野に係る当業者により、最も効率的に彼らのワークを他の陶業者に伝えるために使用される方法である。ここで、および一般的に、アルゴリズムとは、所望の結果を得るための自己矛盾のないステップのシーケンスである。これらのステップは、物理量を物理的に操作することを必要とする。通常（必須ではないが）、これらの量は、電気的あるいは磁気的信号の形態をとり、保存、送信、結合、比較、およびその他の操作が可能である。便宜上、また、慣用上、これらの信号を、ビット、値、要素、記号、文字、語、数字等で表す。
【００２２】
しかし、これらの、およびこれらに類似する語は、適切な物理量に関連し、これらの量に適用された単に便利なラベルにすぎない点を心に留めるべきである。以下の議論では特に指定がない限り、「処理」、「計算」、「算出」、「判断」、「表示」等の表現を使用した議論は、コンピュータシステムあるいはそれと同様の電子計算機の動作および処理を指す。コンピュータシステムは、コンピュータシステムのレジスタおよびメモリ内で物理（電子的）量として表現されるデータを操作し、コンピュータシステムのメモリ、レジスタ、あるいは他の情報記録、送信、表示装置内において同様に物理量として表現された他のデータに変換する。
【００２３】
本発明はまた、この中の処理を行う装置に関する。この装置は、特に、必要な目的のために構成されるものであって、そのコンピュータ内に記憶されるコンピュータプログラムにより選択的に活性化あるいは再構築される一般的な目的のコンピュータを含んでもよい。このようなコンピュータプログラムは、例えば、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、ＭＯディスク、ＲＯＭ（ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）、ＲＡＭ（ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気あるいは光学カード、その他電子的指示の保存に適し、コンピュータのシステムバスに接続されるあらゆる形態の媒体に記録されてもよい。
コンピュータ読み取り可能な記録媒体に記録されてもよい。
【００２４】
ここで示されるアルゴリズムおよび表示は、本来的に特定のコンピュータ等の装置に関連するものではない。種々の一般目的のシステムを、本発明の教示によるプログラムを用いて使用してもよいし、必要なステップを実行する専用の装置を構成してもよい。これらのシステムに必要な構成は以下の説明で明らかになる。さらに、本発明は、特定のプログラム言語を用いて説明するものではない。本発明の教示を実行するために、種々のプログラム言語が使用されてもよいことがわかる。
【００２５】
機械読み取り可能な媒体は、機械（例えばコンピュータ）で読み取り可能な形式で情報を保存、送信するための、いかなるメカニズムを含むものであってもよい。例えば、機械読み取り可能な媒体は、ＲＯＭ、ＲＡＭ、磁気記録媒体、光記録媒体、フラッシュメモリ、電気的、光学的、音響的、あるいは他の形式の伝播信号（搬送波、赤外線信号、デジタル信号等）でもよい。
【００２６】
＜概説＞
図１はＩＰネットワークの一実施形態を示す図である。図１を参照すると、ＩＰネットワーク１０は、少なくとも２つの端末（ノード）を有すると概ね図示されている。その少なくとも２つの端末（ノード）は、複数のルータ（ホスト）１２、およびＩＰネットワーク１０上のルータ（ホスト）１２を介して互いに通信する。情報は、パケットあるいはデータグラムとしてＩＰネットワークを介して通信される。
【００２７】
ルータ（ホスト）１２の集合、各エンドの端末（ノード）、およびそれらを接続するリンクにより、経路が構成される。送信時、データグラムは、宛先端末に到達するためにいくつかのホップを通過する。これらのホップは、ルータ（ホスト）１２全体を指してもよい。このように本願において「ホップ」という単語は、ホストおよびルータの両方を含むと解釈される。送信するノード（端末）は、経路の発呼元という（あるいは単に「発呼元」という）ことができ、また受信するノード（端末）は、経路の宛先という（あるいは単に「宛先」という）できる。図示した通り、発呼端末は、リモート端末１４でも固定端末１６でもよい。同様に、宛先端末もリモート端末１８でも固定端末２０でもよい。
【００２８】
一実施形態において、固定端末１６および２０は、固定リンクを介してルータ１２の各々に直接接続されている。リモート端末１４および１８は、無線ホップ２２を介してアクセスポイント２４に接続されている。アクセスポイント２４は、通常、通信塔２６およびルータ１２を有する。なお、アクセスポイント２４は、ＩＥＥＥ８０２．１１のアクセスポイント（関連するルータ１２を伴っても伴わなくてもよい）のような無線ＬＡＮ（ＷＬＡＮ）準拠のアクセスポイント２６を含んでもよい。
【００２９】
リモート端末１４および１８は無線電話として描かれている。しかし、無線ＩＰネットワーク１０で使用されるリモート端末としては、無線電話に限られず、個人情報端末（ＰＤＡ）、携帯型コンピュータ等であってもよいことは当業者にとって自明である。したがって、図１における無線電話の描写は例示であり本発明を限定するものではない。さらに図１に示されるように、ルータ１２の各々は少なくとも１つの他のルータに接続されており、これにより端末間でＩＰネットワーク１０を介したパケット送信が可能になっている。
【００３０】
＜有線ＣＡＴ＞
図２は、ルータ１２におけるＩＰパケット処理の一実施形態を示すブロック図である。図２を参照すると、ＩＰパケットは、複数の入力ラインカード（Ｉｎｇｒｅｓｓ  Ｌｉｎｅ  Ｃａｒｄ）３０に到着し、ＩＰ処理段階３２に入る。次にパケットは、典型的にはルータ１２の特定の実行状況に依存して入力キュー３４あるいは出力キュー３６に置かれる。スイッチファブリック３８は、パケットを適切な出力ラインカード（Ｅｇｒｅｓｓ  Ｌｉｎｅ  Ｃａｒｄ）４０に誘導する。キューイングは、スイッチファブリック３８への入力および出力のどちらでも起こる可能性がある（もっとも最近のルータは入力キューイングを実行している）。しかし、キューイングは通常ＩＰ処理３２の後に起こる。後で詳細に説明するとおり、ＩＣＭＰタイムスタンプのオプションを使用する場合、ＩＣＭＰタイムスタンプ要求により引き出されたタイムスタンプは、入力キュー３４／出力キュー３６にエントリーする前の時刻を記録する。パケットは通常通信線の速度で取り扱われ、ＩＰ処理段階３２に対する待ち時間および実際の処理時間は、スイッチファブリック３８におけるキューイングおよび出口線カード４０における送信時間と比較して無視することができるので、ＩＰ処理の時間は短くてすむ。ＩＰ処理３２後のパケットのキューイングは、他のパケットが送信されるまでの待ち時間によるものである。キューイング遅延は、測定対象となるパケットの到達時におけるキューのサイズおよびリンクの転送速度と直接的に関連している。パケットは、キューが空くのを待って、送信される。
【００３１】
以降の議論においては、以下の項目を表すために次のような記号が使用される。ｔnすなわちｎは、イベントが記録される時刻を表す。Ｑi（ｎ）は、時刻ｎ、リンクｉにおけるキューのサイズ（ビット）を表す。Ｂiは、リンクｉの情報路容量（ビット／秒）を表す。Ｒi（ｎ）は、時刻ｎにキューに入ってくるフローの速度の総和（ビット／秒）を表す。ｑi（ｎ）は、時刻ｎにおいて、ルータｉにおけるキューイング遅延を表す。ｍは、パケットのサイズ（ビット）を表す。
【００３２】
時刻ｎにキューに入ったパケットに対して、既にキューに入っているデータのサイズはＱi（ｎ）である。そのパケットのキューイング遅延ｑi（ｎ）は、速度Ｂi（すなわち、パケットのキューイング遅延）において、リンクｉ中のキューを空けるのに必要な時間であり、以下のように表せる。
【数１】
2004312725.tif 000003
速度Ｂiは、情報路容量、つまりリンクがデータを送信する速度を指す。すなわち、リンクの転送速度のことである。したがってこの値は、ルータとネットワークの接続配置に固有の値である。
【００３３】
図３は、入ってくるフロー速度の変化に対する空いているキューのサイズ（つまり、キューイング時間）の変化を示す。Ｒiが速度Ｂiより小さい限り、キューサイズは増えない（Ｒiが速度Ｂiと等しい場合、リンクは出力ラインカード上でビットを直列化することができる）。しかし、インターネットトラフィックは爆発的に増加する性質のものであるため、Ｒiが情報路容量Ｂiを超え、キューイングが起こる可能性がある。本発明の目的に対して、時刻ｎにおけるリンクｉの利用率は以下のように定義される。
【数２】
2004312725.tif 000004
図３を参照すると、次の式が得られる。
【数３】
2004312725.tif 000005
あるいは、
【数４】
2004312725.tif 000006
ここで、簡略化のため、時刻ゼロにおけるネットワーク初期化の際には、全てのリンクにおけるキューは空いている、すなわち、全てのｉに対しＱi（０）＝０であると仮定している。
【００３４】
後で変化させるため、ｔr-1、ｔr間の時間間隔は、一定に設定されない。数１および数３から、次式が得られる。
【数５】
2004312725.tif 000007
また、数１および数４から
【数６】
2004312725.tif 000008
数２を数６に代入すると、
【数７】
2004312725.tif 000009
したがって利用率は次式のように表される。
【数８】
2004312725.tif 000010
【００３５】
通過時間Ｔi（ｎ）は、時刻ｎにおいて、ある連続したｍビットのデータがリンクをトラバースするのに必要な時間である。すなわち、通過時間は次式で表される。
【数９】
2004312725.tif 000011
ｍ／Ｂはまた、リンクの転送時間も指している。ここで定義される通過時間は、送信遅延およびキューイング遅延の総和であるが、伝播遅延および処理遅延は無視している。数７および数９から、次式が得られる。
【数１０】
2004312725.tif 000012
したがって、Ｂiは次式のように表される。
【数１１】
2004312725.tif 000013
次に、数２を数１１に代入すると、Ｒiは次式のように表される。
【数１２】
2004312725.tif 000014
【００３６】
新たなフローに対する利用可能な帯域幅は、あるリンクがサポートできる速度である。つまり、キューのサイズ（すなわち、キューイング遅延）が増えないような速度である。すなわち、利用可能な帯域幅は、リンクの情報路容量Ｂのうち、速度の総和がＲである競合するフローに使用されない部分であり、次式のように表される。
【数１３】
2004312725.tif 000015
数２を数１３に代入すると、次式が得られる。
【数１４】
2004312725.tif 000016
ここで、ＡｖＢｗi（ｎ）は、時刻ｎ、リンクｉにおける利用可能な帯域幅である。
【００３７】
利用可能な帯域幅の測定値は、その経路が輻輳が始まることにより、遅延およびジッタの発生なしで付加できる入力フローのマージンの評価に使用することができる。例えば、音声符号機に対する帯域幅要求は、利用可能帯域幅の観点からのものである。
【００３８】
スループットは、通常、リンクあるいは経路を介して一定量のビットのデータを得るのに必要な時間を測ることにより測定される。したがって、受信先において測定されるリンクｉのスループットは、次式のように表される。
【数１５】
2004312725.tif 000017
ここで、ＴｈｒＢｗi（ｎ，ｋ）は、時刻ｎ，ｋにおけるリンクｉのスループット（ビット／秒）である。データパケットのサイズはビット単位で測定され、それは「データチャンク（ｄａｔａ  ｃｈｕｎｋ）」と呼ばれる。データチャンクは、種々のサイズのパケットで構成されることが可能である。Ｂiはリンク情報路容量、ｑiはリンクのｋビットチャンクのキューイング遅延である。
【００３９】
複数のリンクにより構成される経路全体に対して、数１５を使用すると、スループットは次式のように表される。
【数１６】
2004312725.tif 000018
数１６の右辺の分母は、実際にリンクおよび経路それぞれをトラバースするのに必要な遅延に対応している。したがって、スループットは、ネットワークにおける遅延状態を示す良い指標である。このように、スループットは、それ自体ではここで定義されるリンクあるいは経路の情報路容量、あるいは利用可能な帯域幅を表すものではない。しかしながら、次のような方法でリンクあるいは経路の情報路容量、あるいは利用可能な帯域幅の測定に関連する。
【００４０】
数２および数５を連続した領域に拡張すると、次式が得られる。
【数１７】
2004312725.tif 000019
次に、数１４を用いると、次式が得られる。
【数１８】
2004312725.tif 000020
最後に、この結果を数１５に代入すると、スループットは次式のように表される。
【数１９】
2004312725.tif 000021
【００４１】
図４は、ＱｏＳ推定値を生成する処理の一実施形態の方法の全体的なフローを示す図である。この処理は、ハードウェア（回路素子、専用ロジック回路等）、ソフトウェア（多目的コンピュータシステムあるいは専用機上で動作するもの）、あるいはそれらの組み合わせを含む処理ロジックにより実行される。この方法の本質は、連続するホップにおけるキューイング遅延の変化を推定することである。したがって、前述の数２、数１１〜数１３は、情報路容量Ｂ、利用可能帯域幅ＡｖＢｗ、入ってくる競合フローＲの総和、および利用率ｕの推定に使用される。
【００４２】
図４に示されるように、本実施形態の方法は、処理ロジックが、その経路の発呼端末１４および１６からその経路の宛先端末１８および２０までに存在するルータ（ホップ）１２全部のネットワークアドレスを特定することから始まる（処理ブロック４０）。一実施形態において、これは、Ｔｒａｃｅｒｏｕｔｅアプリケーションを使用して実現される。次に、処理ロジックは、経路上の各ホップにおけるキューイング遅延の第１の推定値を得る（処理ブロック４２）。処理ブロック４０と処理ブロック４２を合わせて、プロセッサの初期化（ブートストラップ）段階４４と呼ぶ。続いて、複数組のＩＣＭＰタイムスタンプ要求は、各ルータ１２に規則的な間隔で送信される。これにより、前述の数式群を用いてルータ１２におけるキューイング遅延変化４６の測定が可能になる（処理ブロック４８）。一実施形態において、ＩＣＭＰタイムスタンプ要求の各々は、図４で５０と示される、ルータ１２の各々に対するＱｏＳパラメータ（情報路容量、利用可能な帯域幅、スループット）について１つの推定値を生成する。さらに、リンクの利用率および競合トラフィックのサイズが推定される。図４で示されている処理ブロック４６、４８、５０を合わせて、測定段階５２と呼ぶ。
【００４３】
一実施形態において、測定は、エンド・ツー・エンドの経路上の全てのホップを特定するために、Ｔｒａｃｅｒｏｕｔｅアプリケーションを宛先端末１８および２０に呼び出すことにより開始される。いったんホップのリストが得られると、複数組のＩＣＭＰタイムスタンプ要求が、各ホップにおける遅延の変化量を得るために使用される。以下は、あるホップに対しこれを実現する方法の説明である。その手順は、経路上の全てのホップに対し共通である。
【００４４】
図５は、連続したルータ１２における１組のＩＣＭＰタイムスタンプ要求６０および６２の処理の一実施形態を示す図である。ルータ６４に到着後、パケット６０は、ＩＰ処理部６６からタイムスタンプを受け取る。次に、一実施形態において、パケット６０は、ルータ６４の返信キュー６８を介してその発信元に戻る。パケット６２は、送信キュー７０、リンク７２を通って、ルータ７４のＩＰ処理部６６に到達しタイムスタンプを受け取る。次に、一実施形態において、パケット６２は、ルータ７４の返信キュー６８を介してその発信元に戻る。
【００４５】
図５に示されるルータ６４からルータ７４までのリンクにおけるキューイング遅延の変化を得るために、２つのＩＣＭＰタイムスタンプ要求が、第１のパケットの最終ビットの送信と第２のパケットの最初のビットの送信の時間差が生じないように次々に送信される。第１のパケットのＩＣＭＰ要求は、第１のルータ６４に向かい、第２のパケットのＩＣＭＰ要求は、第２のルータ７４に送信される。同一のペアに属するパケットは、識別子あるいはＩＣＭＰパケットのシークエンス番号フィールドを用いて特定される。
【００４６】
そのパケットペアの第１のパケットの、第１のルータ６４におけるタイムスタンプは、Θi1で表され、そのペアの第２のパケットの、第２のルータ７４におけるタイムスタンプは、Θi+12で表される。異なる時間軸上での測定を一般性を損なうことなく特定するため、ＩＣＭＰタイムスタンプ要求により報告される、同一のパケットペアのタイムスタンプは、第２のパケットがタイムスタンプを受け取ったときに記録されると仮定する。これは、記号Θi1（ｊ）とΘi+12（ｊ）に等しく、両方のタイムスタンプは、同時刻ｊに集積されることを意味する。次の関係は、これらのタイムスタンプの差を表す。
【数２０】
2004312725.tif 000022
ここで、ｍはＩＣＭＰタイムスタンプ要求パケットのサイズ（すなわち、ＩＣＭＰに対しては４０バイト、ＩＰに対しては２０バイト）である。ｑi（ｊ）は、第１のルータ６４から第２のルータ７４まで送信されるのを待っているパケットペアｊのキューイング遅延である。そして、ｄi→i+1（ｊ）は、２つのルータ間の伝播遅延である。
【００４７】
重要なことは、第１のパケットのタイムスタンプは、パケットが第１のルータ６４のＩＰ処理段階を出発した時刻を示すだけでなく、第２のパケットが同一の段階を出発した時刻も示すと仮定している点である。この仮定が成り立つためには、２つのＩＣＭＰパケットが、他のパケットの後で到達することが必要である。すなわち、これら２つのパケットがキューのため第１のルータ６４に到達するまで、２つのパケット間に干渉トラフィックは存在しないということである。
【００４８】
伝播遅延、処理遅延を無視すると、次式が得られる。
【数２１】
2004312725.tif 000023
数２１は、前述の数９と同一である。すなわち、数２１は、リンク７２経由でルータ６４からルータ７４までのトラバース時間を定義する。数２１は、リンクにおける送信時間およびキューイング時間は考慮しているが、伝播遅延および処理遅延は無視している。
【００４９】
第１のパケットペアの送信後、送信機は次のパケットペアを送信する前に、ユーザが定義した遅延αだけ待機する。今度は、集積される測定は、Θi1（ｊ＋１）とΘi+12（ｊ＋１）である。したがって、キューイング遅延変化は次式のように推定される。
【数２２】
2004312725.tif 000024
ここで数８を用いて、
【数２３】
2004312725.tif 000025
ここでｕi（ｊ＋１）は、ルータ６４とルータ７４の間のリンクｉ７２における利用率であり、時刻ｔjにおいて、２つの測定の組ｊおよびｊ＋１間で測定されたものである。さらに、
【数２４】
2004312725.tif 000026
である。
【００５０】
2004312725.tif 000027
【数２５】
2004312725.tif 000028
【００５１】
次に、ｋ≦Ｎを満たすすべてのノードに対してΔｑk（ｊ）が既知であると仮定すると、ΔｑN+1（ｊ）は、以下の式により計算される。
【数２６】
2004312725.tif 000029
ここで、容量Ｂiは数２１を用いて以下のように決定される。
【数２７】
2004312725.tif 000030
数２７において未知の変数は、ルータ６４における、時刻ｔjにおけるキューイング遅延である。しかし、それは以下の式によって求められる。
【数２８】
2004312725.tif 000031
ここで、Δｑi（ｊ−１，ｊ）は、パケットペアｊ−１およびｊにより測定される、ルータ６４におけるキューイング遅延の変化である。ここで、
【数２９】
2004312725.tif 000032
である。
【００５２】
数２９において、ｑi（０）は、測定開始時に送信された第１のパケットペアのパケットが体験したキューイング遅延の推定値である。ルータ６４における第１のキューイング遅延ｑi（０）の推定値は、測定プロセスのまさに最初に、まず３つの連続したＩＣＭＰタイムスタンプ要求を送信することにより得られる（最初の１つはルータ６４へ、次の２つはルータ７４へ送信される）。これにより次式が導かれる。
【数３０】
2004312725.tif 000033
したがって、第１のルータ６４から第２のルータ７４までのリンクの時刻０における容量Ｂiの推定値は、次式のように得られる。
【数３１】
2004312725.tif 000034
【００５３】
容量Ｂiの推定値は、以下で説明するように、測定の進行により、後ほど更新される。しかし、時刻０において、数２１は次式のように書き換えることができる。
【数３２】
2004312725.tif 000035
これを数３１に代入すると、
【数３３】
2004312725.tif 000036
が得られる。リンクｉにおけるキューイング遅延の推定値の初期値は、測定プロセスを通じて、数２９において用いられることができる。キューイング遅延の推定値はまた、数２９で用いるためによりよい推定値を得るため、３つの連続したＩＣＭＰパケットを送信するという同じ手順により、すべての測定イベントにおいて繰り返し求められる。
【００５４】
ｑi（ｊ）の推定値が得られると、それはリンクの情報路容量Ｂiを推定するために数２７で使用される。したがって、Ｂiは、数２７、数２９、数３３を用いて推定することができる。ここで入ってくる競合フローＲiの総和は、数２、数２３、数２７、数２９、および数３３を用いて推定することができる。これはまず、情報路容量Ｂiの推定により実行される。次に数２３を使用して利用率を推定する。そして数２を使用してＲiを得る。さらに、利用可能な帯域幅ＡｖＢｗiは、数２、数１３、数２３、数２７、数２９、および数３３を用いて、同一のプロセスにより推定することができる。
【００５５】
一実施形態において、ルータ１２の全ては、規則的に、そして同一の頻度で測定される。さらに別の実施形態では、特定のルータ１２は、そのルータ自身のキューイング遅延の変化率に基づいて、測定頻度が変更されてもよい。
【００５６】
本発明の実施形態において、経路のホップのアドレスは、まずＩＣＭＰペアの送信が始まった後に特定される。さらに別の実施形態において、各ホップに対するＩＣＭＰペアの送信は、そのホップが特定されるとすぐに始まる。
【００５７】
一実施形態において、ＩＣＭＰタイムスタンプ要求は、ＩＣＭＰプロトコルで定められた標準サイズの大きさである。さらに別の実施形態においては、ＩＰペイロードフィールドにダミーデータが付加されてもよい。これにより、ルータにおける転送時間が増加するが、非常に高速なリンクに対しては有用な機能である。
【００５８】
一実施形態において、経路の特定とタイムスタンプ要求は、発呼ホストあるいは宛先ホストのどちらからも送信される。さらに別の実施形態では、種々のタイムスタンプ要求および経路の特定は、発呼端末、受信先、あるいはネットワークの他のホストから同時に送信されてもよい。さらに、測定の処理は、ネットワーク上のホストの任意の１つ、一部、あるいは発呼元ホストおよび通信先ホストを含む全てのホストにおいて実行されてもよい。
【００５９】
この方法は、タイムスタンプ要求パケットのペアが経路上の最も遅いリンクを介した送信を回避するように改良できる。これは、タイムスタンプ要求パケットのペアがそのリンクに到達したときのタイムスタンプ間の分散を回避するということである。これを実現するために、測定は、ボトルネックリンクを回避するために、発呼端末あるいは宛先ノードのどちらからも行われる。本発明の好適な実施形態において、種々のリンクの変化率の測定により、ボトルネックが特定される。この方法はまた、リンクの伝播遅延を考慮して測定の精度をさらに向上させることにより更に改良される。これは、伝播遅延の推定により実現される。
【００６０】
＜無線リンクの実施形態（無線ＣＡＴ）＞
ネットワークにおけるエンド・ツー・エンドの経路のパケット損失率を推定するための方法および装置について説明する。一実施形態において、その方法は、エンド・ツー・エンドの経路上のすべてのルータのキュー容量を特定するためにそのエンド・ツー・エンドの経路を測定するステップと、その経路上のホップにｐｉｎｇ要求パケットを送信するステップと、ＱｏＳ推定値を生成するためにｐｉｎｇ応答を処理するステップとを有する。別の実施形態において、、エンド・ツー・エンドのネットワーク経路の無線リンクに対するＱｏＳ値を計算するための方法および動作は、そのネットワークの有線部分における平均パケット損失の値を測定するステップと、無線リンクに対するパケット損失値をネットワークの有線部分における平均パケット損失の値の関数として計算するステップとを有する。以下の本発明の説明においては、無線リンク２２を用いた実施例（ここでは、「無線ＣＡＴ」という）について説明する。
【００６１】
図１を参照すると、ＩＰネットワーク１０におけるネットワークの輻輳を評価する方法（所望の経路に沿ったルータ１２においてキューイング遅延の変化を測定する等の方法）は、利用可能帯域幅ＡｖＢｗの推定を可能にする。これらの技術は、有線ネットワーク（ここで、輻輳が単に無線リンク２２におけるルータ１２におけるキューによって起こる）で用いられているが、パケット輻輳は、キューイング輻輳に加え他の種々の要因で起こる可能性がある。これらは、ＩＥＥＥ８０２．１１、ＧＳＭ、ＰＣＳ等、共有型媒体技術における媒体に対するコンテンション（回線争奪）を含む。さらに、無線ネットワークにおけるパケット輻輳は、無線リンク上のランダムなパケット損失による再送信遅延によっても起こる可能性がある。
【００６２】
利用可能な無線帯域幅を測定する方法が、例示的な無線ホップであるＩＥＥＥ８０２．１１ｂの無線ＬＡＮを用いて説明される。この方法は、他の技術を用いてもよく、ＩＥＥＥ８０２．１１ｂの無線ＬＡＮ（ＷＬＡＮ）は、本発明を限定することを意図したものではない。ＩＥＥＥ８０２．１１ｂにおいて物理層における粗送信速度は、動的に４段階（１Ｍｂｐｓ、２Ｍｂｐｓ、５．５Ｍｂｐｓ、１１Ｍｂｐｓ）で変化する。選択された速度は、知覚されるフレーム誤り率（Ｆｒａｍｅ  Ｅｒｒｏｒ  Ｒａｔｅ、ＦＥＲ）によって変化する。速度を切り替えるためのＦＥＲのしきい値は、実装依存である。
【００６３】
一実施形態において、利用可能な無線帯域幅を推定する第１のステップは、無線リンクの現在の全体の粗容量を得るステップである。無線リンクの現在の全体の粗容量を得た後、次のステップは、リンクの粗容量のうち利用可能な量を評価するためにパケット輻輳を推定するステップである。
【００６４】
物理層における無線リンクの粗容量ＢＰＨＹは、ＷＬＡＮ装置のメーカによりユーザに一般的に提供されるソフトウェアにより決定されてもよい。例えば、シスコシステムズ（Ｃｉｓｃｏ  Ｓｙｓｔｅｍｓ）は、Ｗｉｎｄｏｗｓ（登録商標）ＣＥ  ２．１１に対してＡｉｒｏｎｅｔ“３５０”のクライアントユーティリティソフトウェアを提供している。Ａｉｒｏｎｅｔ“３５０”クライアントユーティリティソフトウェアは、サイト調査機能を含む。ここで、サイト調査機能により、クライアントアダプタは無線リンクのステイタスを２５０ミリ秒ごとに読み出してもよい。Ａｉｒｏｎｅｔ“３５０”クライアントユーティリティソフトウェアは、２つの動作モード（能動モードおよび受動モード）を有する。受動モードにおいては、そのユーティリティにより追加のＲＦトラフィックは生成されず、実際のトラフィックのみが測定され、粗容量ＢＰＨＹが推定される。能動モードにおいては、そのソフトウェアは、推定動作のために送信される能動的測定ストリームの特性の設定を可能にする。このような特性は、送信されるパケットの数、パケットサイズ、パケット間到着遅延、および粗送信速度（一実施形態において、この値は、１、２、５．５、１１Ｍｂｐｓである）を含む。
【００６５】
パケットトラバース無線リンクは、パケットトラバース有線リンクと比較して、さらなる遅延による損害を受ける。有線リンクにおいて、パケットは典型的には、処理、送信、輻輳および伝播遅延をうける。無線リンクにおいては、パケットはさらに、コンテンションおよび再送信遅延をうける可能性がある。ここで用いられるように、「コンテンション遅延」は、媒体の共有特性に起因する、パケットが無線チャンネルを「つかむ」のに必要な時間を指す。また、「再送信遅延」は、損失のある無線リンクに対してパケットを継続的に送信するのに必要な時間を指す（再送信を何回も試みる必要がある）。無線リンクにおけるパケット再送信は、以下で説明するようにモデル化できる。
【００６６】
図６および図７は、アクセスルータ（ＡＲ）１２に到達し、対応するアクセスポイント（ＡＰ）２４を通過し、無線リンク２２をトラバースし、リモート端末１８に到達するパケットの振る舞いを表すモデルを示す。
【００６７】
リモート端末１８宛てのあるパケット１２６は、まずアクセスルータ１２に到達する。ここで、あるパケット１２６は、他のルータからの到着に先立って、輻輳キュー１２２において、その他のパケット１２６を待つためキューイング遅延ｑcongestionをうける。パケット１２６の各々は、輻輳キュー１２２から１つずつ抜け出し、コンテンションキュー１２４に入る。パケット１２６のあるパケットが輻輳キューの先頭に来た場合、そのパケットは、無線リンク２２に対して送信可能となるの待つコンテンション遅延をうける。コンテンション遅延は、ＩＥＥＥ８０２．１１ｂ等の技術における伝送媒体の共有特性に起因する。
【００６８】
パケット１２６の各々は、コンテンションキュー１２４の先頭になり、無線リンク２２に対して送信される。障害が発生した場合、パケット１２６は、最後尾からコンテンションキュー１２４に再度入る。これは、リモート端末１８において無事に受信されるまで繰り返される。しかし、パケット１２６の再送信回数には制限回数ｎがあり、これを超えるとパケットは破棄される。結果において、アクセスルータ１２の輻輳キュー１２２の最後尾に入るパケット１２６は、リモート端末１８に到達するまで全体としてキューイング遅延ｑkをうける。この遅延は以下の式で与えられる。
【数３４】
2004312725.tif 000037
ここで、Ａkはアクセスルータ１２のコンテンションキュー１２４の先頭におけるあるパケットｋの総送信回数を、Ｂikはアクセスルータ１２のコンテンションキュー１２４の先頭におけるパケットｋのｉ番目の再送信に対するコンテンション時間を、τは先行するパケットの再送が決定する前のタイムアウト遅延（これは、往復伝播遅延、受け取り確認（ａｃｋｎｏｗｌｅｄｇｅｍｅｎｔ）パケットの送信を含む）、およびリモート端末における処理を含む）を、ｔxkはパケットｋの無線リンク２２に対する送信遅延を、ｔpropagationkは無線リンク２２に対するパケットｋの伝播遅延を、ｑpropagationkはアクセスルータ１２４の輻輳キュー１２２およびコンテンションキュー１２４の両方においてパケットｋに先行するパケットにより消費される時間を示す。
【００６９】
数３４は、平均値を用い、伝播遅延（典型的な１００メートルの無線リンク２２に対して約０．５マイクロ秒）を無視することにより、以下のように書き換えられる。
【数３５】
2004312725.tif 000038
すべてのパケットは破棄されるまでｎ回再送信されるので、
【数３６】
2004312725.tif 000039
ここで、ＩＥＥＥ８０２．１１ｂの実装において典型的にはｎは７である。
【００７０】
ここで、送信回数Ａkを推定する方法として、２つの実施形態を説明する。第１の実施形態は、アクセスポイントのクライアントユーティリティにより提供される情報に基づいており、一方、第２の実施形態はパケット損失の推定値を用いる。
【００７１】
まず第１の実施形態について説明すると、リモート端末１８あるいはアクセスポイント２４に存在するユーティリティは、アクセスポイントのクライアントユーティリティのドライバが読み込まれた時、あるいはドライバが読み込まれない場合または無線リンク２２が終了している場合に無線リンク２２が確立された時、典型的に表１から情報を収集する。例えば、シスコのＡｉｒｏｎｅｔ“３５０”ＷＬＡＮカードのクライアントユーティリティは、以下の情報をリアルタイムに収集する。
【表１】
2004312725.tif 000040
【００７２】
これらの変数間の特定の関係は図８に示されている。
この収集されたデータは、テキストファイルに書き込まれてもよい。また、このテキストファイルは、各変数の変化Δａ、Δｂ、Δｃを計算するために特定の時間間隔Ｔで測定されてもよい。時間間隔Ｔの間に扱われるパケットの総数はａ＋ｃである。総送信回数は、以下のように表される。
【数３７】
2004312725.tif 000041
あるパケットｋについての平均に対して、
【数３８】
2004312725.tif 000042
である。また、
【数３９】
2004312725.tif 000043
である。数３５を用いると、以下の式が得られる。
【数４０】
2004312725.tif 000044
ここで、
【数４１】
2004312725.tif 000045
【００７３】
続いて、送信回数Ａを推定する第２の実施形態について説明する。ｐは無線リンク２２におけるパケット損失の確率である。パケットｋの送信回数は、ランダムな変数Ａkである。ここで、Ａkの値の各々について、発生する確率が表２に示されている。
【表２】
2004312725.tif 000046
【００７４】
平均すると、無線リンク２２に対してパケットｋを無事送信するのに必要な送信回数は次式で与えられる。
【数４２】
2004312725.tif 000047
再び数３５を参照すると、
【数４３】
2004312725.tif 000048
である。
【００７５】
ＩＰネットワーク１０の固定端末１６は、リモート端末１８に、パケット１２６を有線および無線ホップの双方を介して送信する。したがって、エンド・ツー・エンドのパケット損失の測定は、無線パケットの損失を推定するには十分ではない。このシナリオにおいて、終点で観測されるパケット損失は、輻輳による有線リンク上の損失と、輻輳あるいはランダム損失による無線リンク上の損失と、二者のうちどちらも可能であり、無線リンク上のパケット損失に対応していない。
【００７６】
ネットワーク層において無線パケット損失を推定するためには、いくつかの実装方法が可能である。このような２つの実施形態は、有線ホップ上の損失を推定し、そして、ＲＴＣＰおよび以下で説明するパケット損失モデルを介してエンド・ツー・エンドのパケット損失の知識から無線リンク上の振る舞いを推定する。これらの実施形態のどちらも、経路の終点（この場合、固定端末１６およびリモート端末１８）における機能性実装を介して有線パケット損失を推定する。これらの実施形態は、処理ロジックにより実行される。処理ロジックは、ハードウェア（例えば、回路、専用ロジック回路）、ソフトウェア（多目的コンピュータ上で動作するもの、あるいは専用機で動作するもの）、あるいはこれらの組み合わせにより構成されてもよい。
【００７７】
一実施形態において、処理ロジックは、システムに対し有線リンク上のみの損失を推定することにより開始する。ここで、ＱｏＳ推定のためのハードウェアおよびソフトウェアは、経路の端部に配置される。専用ソフトウェアをアクセスポイント２４のルータ１２に配置することによりＱｏＳを推定するという提案がある。しかし、本発明の少なくとも１の実施形態は、専用ソフトウェアをアクセスポイント２４のルータ１２に配置するよいう要求を排除する。
【００７８】
別の実施形態において、処理ロジックは、ｐｉｎｇパケットを用いてネットワーク層における有線パケット損失を推定する。この実施形態の本質は、アクセスポイント２４のルータ１２からの応答をトリガし、実質的にルータ１２に特化されたソフトウェアを配置することなく有線ホップのパケット損失を推定することである。この目的のため、ｐｉｎｇパケットは、音声パケットストリーム内にインターリーブされる。これらのｐｉｎｇは、経路上のＴｒａｃｅｒｏｕｔｅ処理により明らかにされたルータ１２を目的とする。ｐｉｎｇパケットをインターリーブする割合は、パケット損失の振る舞いを捕捉するように、かつトラフィックに対し所定のオーバーヘッドを超えないように設定される。
【００７９】
例えば、２０音声パケットごとに１ｐｉｎｇパケットを送信すると、パケット換算で５パーセントのオーバーヘッドという結果になる。有線ネットワークにおいてパケット損失はバーストで起こるので、ｐｉｎｇパケットの損失の測定は、音声パケットの全体の損失割合のよい近似値を提供する。ｐｉｎｇ値間の時間間隔は、パケット損失のバースト性を捕捉するために設定あるいは変更される（したがって一定の間隔ではない）。その時間間隔は、有線ネットワークのパケット損失モデルの振る舞いを捕捉するために変化する。パケット損失モデルの例は、以下の「パケット損失モデル」の項で説明する。
【００８０】
第２の実施形態は、経路の終点における付加的な機能を介して有線パケット損失を推定するものである。この付加的な機能は、前述の有線リンクの実施形態（初期化段階、測定段階）に付加される第３段階として実行されてもよい。この新しい段階を、「ルータバッファ推定段階」という。一実施形態において、この新しい段階は以下のように動作する。有線リンク上の利用可能帯域幅の知識を用いて、送信機は、前述のようにＩＣＭＰタイムスタンプの組のストリームを、推定される利用可能帯域幅より高い速度で、固定端末１６からアクセスポイント２４までの有線ホップ上のルータ１２の各々に送信する。各ルータにおけるキューイング遅延は、目的のルータ１２におけるキューのオーバーフローによりＩＣＭＰパケットが損失し始めるまで推定され、測定される。ｉ番目のルータ１２の各々に対して、最後に観測されるキューイング遅延の値ｑmaxiが記録される。続いて、ｉ番目のルータ１２の各々におけるキュー容量が以下のように推定される。
【数４４】
2004312725.tif 000049
ここで、Ｂiの値は有線リンクｉの粗容量の測定値である。このルータバッファ推定段階は、測定プロセスの開始時に１回だけ行われてもよい。その後、有線ＣＡＴはリアルタイムの測定が終了するまで測定段階を繰り返す。その経路はＴ秒ごとに測定される。有線測定間隔Ｔの間のパケット損失ｐdの推定値は、測定間隔Ｔの間一定条件であるという仮定を用いて次式のように導出される。
Ｒi（Ｔ）＜Ｂiの場合、
【数４５】
2004312725.tif 000050
Ｒi（Ｔ）＞Ｂiの場合、
【数４６】
2004312725.tif 000051
である。したがって、
【数４７】
2004312725.tif 000052
である。ここで、
【数４８】
2004312725.tif 000053
である。
【００８１】
＜パケット損失モデル＞
経路のパケット損失ｐtを生成するために有線パケット損失ｐdと無線パケット損失ｐwとを組み合わせる方法について説明する。この説明は、ｐdを計算し、前述の方法でｐtの知識が与えられた後ｐwを推定する方法を提供する。ＩＰネットワークにおけるパケット損失のよいモデルは、ベルヌイのランダム損失モデル、２状態のマルコフチェーンモデル（あるいはギルバートモデル）、あるいはより複雑なｋ次のマルコフチェーンモデルを含む。本発明の実施形態は、前２つのモデルを用いており、以下でそれについて説明する。
【００８２】
ベルヌイモデルは、ランダムかつ独立したパケット損失のモデル化に使用可能な２状態のマルコフチェーンモデルである。図９は、ベルヌイモデルを示す。ここで、「０」はパケット送信が成功した状態を表し、「１」は損失を表す。状態「０」から状態「１」への遷移確率はｐで表され、状態「１」から状態「０」への遷移確率はｑで表される。ｑとｐの関係は次の通りである。
【数４９】
2004312725.tif 000054
【００８３】
一方、ギルバートモデルは、ＩＰネットワークにおける輻輳によるパケット損失のバースト性を表す２状態のマルコフチェーンモデルである。図１０は、ギルバートモデルを表す。ここで、「０」はパケット送信が成功した状態を表し、「１」は損失を表す。状態「０」から状態「１」への遷移確率はｐで表され、状態「１」から状態「０」への遷移確率はｑで表される。バースト性の効果を組み込むため、ベルヌイモデルのようにｑとｐの和は１とならない。その代わり、以下の関係が維持される。
【数５０】
2004312725.tif 000055
ここで、ｒは全体の平均パケット損失である。
【００８４】
ギルバートモデルに対するバースト長の平均値および標準偏差を図１１に示す。パケット損失のバースト性Ｂｌは、以下の式のようにこのモデルのパラメータと関連する。
【数５１】
2004312725.tif 000056
【００８５】
次に、有線ホップ上および無線ホップ上で測定されたパケット損失と、経路全体を特徴付けるエンド・ツー・エンドの損失との関係を得るために、経路のパケット損失について説明する。このモデルの導出は２つのステップに分けられる。まず、パケット損失モデルは、有線ホップおよび無線ホップについて別々に導出される。次に、これらの２つのモデルを組み合わせて単一のモデルとする。
【００８６】
経路の有線ホップに対しては、ギルバートのパケット損失モデルが用いられる。無線ホップ上の損失は、アクセスポイント２４における輻輳および無線リンク２２上のランダム損失の両方に起因すると仮定される。アクセスポイント２４における輻輳を取り扱う際にも、ギルバートモデルが用いられる。一方、無線リンク２２上のランダムなパケット損失を説明するためには、ベルヌイモデルが用いられる。終点１および２間の経路上のエンド・ツー・エンドのパケット損失ｐtを有線ホップの損失情報に関連付ける説明が導出される。
【００８７】
無線ホップ上のパケット損失は、アクセスポイント２４における輻輳に起因するものと、無線リンク２２におけるビットエラーに起因するものと、どちらも可能である。これらの２つの段階は、それぞれ別個にａおよびｂとしてモデル化される。図１２は、アクセスポイント２４における輻輳と、無線リンク２２におけるランダム損失との両方をうける単一のパケットに対する無線ホップ上の損失を表す３状態のマルコフモデルを示す。
【００８８】
図１２において、ｐa,sは、輻輳に起因する条件付きパケット損失であり、ｐb,sは、ランダム効果に起因する条件無しパケット損失であり、ｑa,sは、輻輳に起因する条件無しパケット損失を反映している。輻輳に関連するパラメータは添字ａを用いて示され、ランダム損失に関連するパラメータは添字ｂを用いて示される。すべてのパラメータは添字ｓを有するが、これは無線リンク２２に関連することを示している。
【００８９】
図１２は、３状態を示している。「０」は損失がないことを、「１」は損失があることを示す。状態（ａ，ｂ）は、それぞれ輻輳段階あるいは無線リンク２２の段階における送信条件（損失、あるいは成功）を反映している。状態（１，１）は、有線ホップ上で損失したパケットは無線ホップへ行くことはないので、事実上、状態（１，０）と同一である。この３状態モデルは、以下の遷移確率行列で完全に表される。
【数５２】
2004312725.tif 000057
【００９０】
Ｐ0,0、Ｐ0,1、Ｐ1,1を得るために、次の条件を満足するように解かれる
【数５３】
2004312725.tif 000058
【００９１】
エンド・ツー・エンドの経路の平均パケット損失ｐt、無線リンクの平均パケット損失ｒsは次式のように与えられる。
【数５４】
2004312725.tif 000059
【００９２】
数５４は、別個のホップ上のパケット損失は独立していると仮定している。しかし、このモデルは、同一リンク上のパケット同士のパケット損失の関係は考慮している。
有線および無線ホップを含む経路全体に対するパケット損失モデルは、図１２に示す３状態モデルと図１３に示すギルバートモデルとを組み合わせることにより得られる。図１３において、ｐdは有線ホップ上の条件付きパケット損失であり、ｑdは有線ホップ上の条件無しパケット損失である。添字ｄを有するパラメータは有線ホップに関連するものであり、添字ｓを有するパラメータは無線ホップに関連するものである。さらに、
【数５５】
2004312725.tif 000060
である。
【００９３】
図１３に示されるモデルは、４状態を用いている。ここで、各状態は、有線および無線ホップの条件を表している。「０」は損失がないことを、「１」は損失があることを示す。状態（ｄ，ａ，ｂ）は、それぞれ、有線ホップ、無線ホップの輻輳段階、無線ホップ段階における損失あるいは成功としての送信の条件を示す。有線ホップでパケット損失が起きた場合には無線ホップまで行かないので、状態（０，１，１）は、実態的には状態（０，１，０）と同一である。同様に、状態（１，１，１）、（１，０，０）、（１，１，０）、および（１，０，１）は同一のものである。
【００９４】
図１３に示される４状態モデルは、以下の遷移確率行列により表すことができる。
【数５６】
2004312725.tif 000061
Ｐ0,0,0、Ｐ0,0,1、Ｐ0,1,1、Ｐ1,1,1を得るために、この行列は以下の条件を用いて解かれる。
【数５７】
2004312725.tif 000062
ここで、エンド・ツー・エンドの経路の平均パケット損失ｐtは次式のように与えられる。
【数５８】
2004312725.tif 000063
【００９５】
数５８は、別個のホップのパケット損失は独立していると仮定している。しかし、このモデルは、同一のリンク上のパケット間のパケット損失の関係は考慮している。
【００９６】
図１３に示す４状態のマルコフチェーンモデルは、測定された有線ホップ上の平均パケット損失ｒdおよび無線ホップ上の平均パケット損失ｒsからｐtを算出するために用いられてもよい。このモデルを用いてｐtを算出するための第１のステップは、ｐd、ｑd、ｐa,s、ｐb,s、およびｑa,sを算出するステップである。ｑdおよびｑa,sの値は、前述のように、平均パケットバースト長の測定を維持し、数５１および図１１に示すグラフを利用することにより得られる。ｑdおよびｑa,sの初期値としては、０．９を用いることができる。この値は、平均損失１．１１パケット／バーストおよび標準偏差０．３５パケット／バーストに対応している（図１１参照）。これらの値は、現在のインターネットに対してもっともらしい値である。インターネットが進化した場合は、初期値として他の値を用いることが好ましい。
【００９７】
数５０から、ｐdは次式のように得られる。
【数５９】
2004312725.tif 000064
【００９８】
ｐa,sの値は、以下の３つの式と２つの未知数からなる方程式を解くことにより得られる。
【数６０】
2004312725.tif 000065
ここで、ｒsは無線リンク上で測定された平均パケット損失であり、ｑa,sは前述のように計算される。ｐd、ｑd、ｐa,s、ｐb,s、およびｑa,sの値が既知となると、数５７をＰ0,0,0、Ｐ0,0,1、Ｐ0,1,1、Ｐ1,1,1について解くことができる。最後に、Ｐ0,0,0、Ｐ0,0,1、Ｐ0,1,1、Ｐ1,1,1の値を数５８に代入することにより、エンド・ツー・エンドの経路平均パケット損失ｐtを得ることができる。
【００９９】
本発明に対する種々の改変、変更が可能であることは、以上の詳細な説明を読んだ当業者にとって明らかである。以上で説明した実施形態は例示であり、これに限定する意図はない。したがって、実施形態の細部については本発明に必須の特徴を限定するものではない。
【図面の簡単な説明】
【０１００】
【図１】ＩＰネットワークを例示する図である。
【図２】ルータのパケット処理を示すブロック図である。
【図３】入力速度に対するキューサイズの変化を示す図である。
【図４】ＱｏＳ推定値を生成するプロセスの一実施形態を示すフロー図である。
【図５】所望のホップの組において処理するＩＣＭＰタイムスタンプ要求を例示する図である。
【図６】アクセスルータ（ＡＲ）に到達し、対応するアクセスポイント（ＡＰ）を通過し、無線リンクをトラバースし、リモート端末に到達するパケットの振る舞いのモデルを示す図である。
【図７】アクセスルータ（ＡＲ）に到達し、対応するアクセスポイント（ＡＰ）を通過し、無線リンクをトラバースし、リモート端末に到達するパケットの振る舞いのモデルを示す図である。
【図８】アクセスポイントからリモート端末までの通信に関する変数の間の関係を示す図である。
【図９】ベルヌイモデルを示す図である。
【図１０】ギルバートモデルを示す図である。
【図１１】バースト長の平均および標準偏差を示すグラフである。
【図１２】３状態のマルコフモデルを示す図である。
【図１３】４状態のマルコフモデルを示す図である。
【図１】
2004312725.tif 000066
【図２】
2004312725.tif 000067
【図３】
2004312725.tif 000068
【図４】
2004312725.tif 000069
【図５】
2004312725.tif 000070
【図６】
2004312725.tif 000071
【図７】
2004312725.tif 000072
【図８】
2004312725.tif 000073
【図９】
2004312725.tif 000074
【図１０】
2004312725.tif 000075
【図１１】
2004312725.tif 000076
【図１２】
2004312725.tif 000077
【図１３】
2004312725.tif 000078
【外国語明細書】
2004312725000001.pdf
2004312725000002.pdf
2004312725000003.pdf
2004312725000004.pdf