(57)【要約】【課題】ネットワークにおけるエンド・ツー・エンドの経路のＱｏＳを推定する方法を提供する。【解決手段】ＩＰネットワークにおける経路に沿った帯域幅の情報路容量、利用可能な帯域幅、および利用率を推定する方法が開示されている。ＩＣＭＰタイムスタンプ要求は、ネットワークの終端装置あるいはネットワーク中の発呼端末から宛先端末まで、エンド・ツー・エンドの経路上の全てのルータに送信される。タイムスタンプの値の差は、各ルータにおけるＱｏＳサービスの指標として使用される。収集された測定値は、次に、送信ホストにおいて、ＱｏＳパラメータを経路の情報路容量（ビット／秒）、利用可能帯域幅（ビット／秒）、個々のリンクの利用、および各ルータにおける輻輳を推定するために処理される。これらのパラメータを組み合わせることにより、エンド・ツー・エンドの経路における帯域幅という点でＱｏＳを推定する。【選択図】　　　図４
2004040793.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークにおけるエンド・ツー・エンドの経路の能力を推定する方法であって、
エンド・ツー・エンドの経路上にあるすべてのホップのアドレスを特定するために当該エンド・ツー・エンドの経路を測定するステップと、
少なくとも１つのタイムスタンプ要求パケットを生成するステップと、
前記少なくとも１つのタイムスタンプ要求パケットを、前記エンド・ツー・エンドの経路上の少なくとも１つのホップに送信するステップと、
前記ホップに対する前記タイムスタンプ要求パケットに応じて、タイムスタンプを生成するステップと、
少なくとも１つのＱｏＳ推定値を生成するために前記タイムスタンプを処理するステップと
を備える方法。
【請求項２】
ネットワークにおけるエンド・ツー・エンドの経路の能力を推定する方法であって、
エンド・ツー・エンドの経路上の複数のホップのアドレスを特定するために当該エンド・ツー・エンドの経路を測定するステップと、
発信ノードにおいて少なくとも１つのタイムスタンプ要求パケットを生成するステップと、
前記タイムスタンプ要求パケットを、前記ネットワークの他のホップによりスプーフィングされた前記発信ノードの発信元アドレスと共に、前記エンド・ツー・エンドの経路上の少なくとも１つのホップに送信するステップと、
前記ホップにおいて少なくとも１つのタイムスタンプを生成するステップと、前記ネットワークにおける少なくとも１つのホップにおいて、ＱｏＳ推定値を生成するために前記少なくとも１つのタイムスタンプを処理するステップと
を備える方法。
【請求項３】
ネットワークにおけるエンド・ツー・エンドの経路の能力を推定する方法であって、
ノードにおいて複数のホップを特定するためにエンド・ツー・エンドの経路を測定するステップと、
前記ノードにおいて少なくとも１つのタイムスタンプ要求パケットを生成するステップと、
前記少なくとも１つのタイムスタンプ要求パケットを、少なくとも１つのホップに送信するステップと、
前記ホップにおいてタイムスタンプを生成するステップと、
前記タイムスタンプを前記ノードに送信するステップと、
ＱｏＳ推定値を生成するために、前記少なくとも１つのタイムスタンプを処理するステップと、
を備える方法。
【請求項４】
前記エンド・ツー・エンドの経路上のホップを特定するための測定ステップは、Ｔｒａｃｅｒｏｕｔｅアプリケーションを用いることを特徴とする請求項１又は２のいずれかに記載の方法。
【請求項５】
前記エンド・ツー・エンドの経路上のホップを特定するための測定ステップは、発呼ノードから実行されることを特徴とする請求項１又は２のいずれかに記載の方法。
【請求項６】
前記エンド・ツー・エンドの経路上のホップを特定するための測定ステップは、宛先ノードから実行されることを特徴とする請求項１又は２のいずれかに記載の方法。
【請求項７】
前記エンド・ツー・エンドの経路上のホップを特定するための測定ステップは、発呼ノードおよび宛先ノードから実行されることを特徴とする請求項１又は２のいずれかに記載の方法。
【請求項８】
前記タイムスタンプを処理するステップは、発呼ノードで実行されることを特徴とする請求項１に記載の方法。
【請求項９】
前記タイムスタンプを処理するステップは、宛先ノードで実行されることを特徴とする請求項１に記載の方法。
【請求項１０】
前記タイムスタンプを処理するステップは、発呼ノードおよび宛先ノードで実行されることを特徴とする請求項１に記載の方法。
【請求項１１】
前記タイムスタンプ要求パケットはＩＣＭＰ要求であることを特徴とする請求項１に記載の方法。
【請求項１２】
生成され処理されるタイムスタンプ要求パケットの数は、少なくとも５つであることを特徴とする請求項１に記載の方法。
【請求項１３】
前記エンド・ツー・エンドの経路上の特定のホップに対するタイムスタンプ要求パケットのペアを生成する頻度を増加させるステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項１４】
測定される頻度を増加させるホップは、利用率、キューイング遅延、キューのサイズ、処理遅延、利用可能な帯域幅、輻輳状態の変化パターンのうち少なくとも１つに基づいて決定されることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記エンド・ツー・エンドの経路上の特定のホップに対するタイムスタンプ要求パケットを生成する頻度を減少させるステップをさらに備えること特徴とする請求項１に記載の方法。
【請求項１６】
測定される頻度を減少させるホップは、利用率、キューイング遅延、キューのサイズ、処理遅延、利用可能な帯域幅、輻輳状態の変化パターンのうち少なくとも１つに基づいて決定されることを特徴とする請求項１５に記載の方法。
【請求項１７】
連続するタイムスタンプ要求パケットの送信の間にあらかじめ決められたレイテンシ（待ち時間）を導入するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項１８】
高速なリンクに対し感度を向上させるために、ダミーデータを前記タイムスタンプ要求パケットに付加することにより、当該タイムスタンプ要求パケットのサイズを増加させるステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項１９】
高速なリンクに対し感度を向上させるために、ダミーデータを前記ＩＣＭＰ要求のＩＰペイロードフィールドに付加することにより、当該ＩＣＭＰ要求のサイズを増加させるステップをさらに備えることを特徴とする請求項１１に記載の方法。
【請求項２０】
前記ＱｏＳ推定値は、リンクおよび経路の情報路容量の推定値を含むことを特徴とする請求項１乃至３のいずれかに記載の方法。
【請求項２１】
前記ＱｏＳ推定値は、前記ホップにおけるキューイング遅延の推定値を含むことを特徴とする、請求項１乃至３のいずれかに記載の方法。
【請求項２２】
前記ＱｏＳ推定値は、リンクおよび経路の利用率の推定値を含むことを特徴とする、請求項１乃至３のいずれかに記載の方法。
【請求項２３】
前記ＱｏＳ推定値は、リンクおよび経路の利用可能な帯域幅の推定値を含むことを特徴とする請求項１乃至３のいずれかに記載の方法。
【請求項２４】
前記ＱｏＳ推定値は、前記ホップにおける干渉フローの推定値を含むことを特徴とする請求項１乃至３のいずれかに記載の方法。
【請求項２５】
経路表が更新された場合に前記測定ステップを再開するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項２６】
前記発信元アドレスは、前記エンド・ツー・エンドの経路の発呼ノードのアドレスであることを特徴とする請求項２に記載の方法。
【請求項２７】
前記発信元アドレスは、前記エンド・ツー・エンドの経路の宛先ノードのアドレスであることを特徴とする請求項２に記載の方法。
【請求項２８】
伝播遅延を考慮することにより、前記ＱｏＳ推定値の精度を向上させるステップをさらに備えることを特徴とする請求項２に記載の方法。
【請求項２９】
前記ノードは、発呼ノード、宛先ノード、独立ノードを含むノード群から選択されることを特徴とする請求項３に記載の方法。
【請求項３０】
通信相手と当該通信端末との間でエンド・ツー・エンドの通信が行われる場合に、前記エンド・ツー・エンドの通信の経路上にある全てのホップのアドレスを特定するためのアプリケーションを実行する実行手段と、
少なくとも１つのタイムスタンプ要求パケットを生成する生成手段と、
前記タイムスタンプ要求パケットを、前記実行手段によりそのアドレスが特定されたホップであって、前記エンド・ツー・エンドの通信の経路上の少なくとも１つのホップに送信する送信手段と、
前記タイムスタンプ要求パケットに応じて生成されたタイムスタンプを含んだパケットを前記経路を介して受信する受信手段と、
前記受信手段により受信したパケットに含まれるタイムスタンプに基づいてＱｏＳ推定値を算出する算出手段と、
を備える通信装置。
【請求項３１】
前記実行手段が実行するアプリケーションは、Ｔｒａｃｅｒｏｕｔｅアプリケーションであることを特徴とする請求項３０記載の通信装置。
【請求項３２】
前記生成手段により生成されるタイムスタンプ要求パケットは、ＩＣＭＰに準拠したものであることを特徴とする請求項３０記載の通信装置。
【請求項３３】
前記生成手段は、少なくとも５つのタイムスタンプ要求パケットを生成することを特徴とする請求項３０記載の通信装置。
【請求項３４】
前記エンド・ツー・エンドの経路上のホップのうち、特定のホップを選択する選択手段と、
前記選択手段により選択されたホップに対して送信されるタイムスタンプ要求パケットであって、前記生成手段により生成されるパケットの生成頻度を変更する変更手段と
をさらに備えることを特徴とする請求項３０記載の通信装置。
【請求項３５】
前記選択手段は、利用率、キューイング遅延、キューのサイズ、処理遅延、利用可能な帯域幅、輻輳状態の変化パターンのうち少なくとも１つに基づいてホップを選択することを特徴とする請求項３４に記載の通信装置。
【請求項３６】
前記タイムスタンプ要求パケットにダミーデータを付加する付加手段をさらに備えることを特徴とする請求項３０記載の通信装置。
【請求項３７】
前記タイムスタンプ要求パケットのＩＰペイロードフィールドにダミーデータを付加する付加手段をさらに備えることを特徴とする請求項３２に記載の通信装置。
【請求項３８】
前記算出手段は、リンクおよび経路の情報路容量の推定値を算出することを特徴とする請求項３０に記載の通信装置。
【請求項３９】
前記算出手段は、前記ホップにおけるキューイング遅延の推定値を算出することを特徴とする請求項３０に記載の通信装置。
【請求項４０】
前記算出手段は、リンクおよび経路の利用率の推定値を算出することを特徴とする請求項３０に記載の通信装置。
【請求項４１】
前記算出手段は、リンクおよび経路の利用可能な帯域幅の推定値を算出することを特徴とする請求項３０に記載の通信装置。
【請求項４２】
前記算出手段は、前記ホップにおける干渉フローの推定値を算出することを特徴とする請求項３０に記載の通信装置。
【請求項４３】
伝播遅延を考慮することにより、前記ＱｏＳ推定値の精度を向上させる再計算手段をさらに備えることを特徴とする請求項３０に記載の通信装置。
【請求項４４】
通信相手との間でエンド・ツー・エンドの通信が行われる場合に、前記エンド・ツー・エンドの通信の経路上にある全てのホップのアドレスを特定する特定ステップと、
少なくとも１つのタイムスタンプ要求パケットを生成する生成ステップと、
前記タイムスタンプ要求パケットを、前記特定ステップによりそのアドレスが特定されたホップであって、前記エンド・ツー・エンドの通信の経路上の少なくとも１つのホップに送信する送信ステップと、
前記タイムスタンプ要求パケットに応じて生成されたタイムスタンプを含んだパケットを前記経路を介して受信する受信ステップと、
前記受信ステップにより受信したパケットに含まれるタイムスタンプに基づいてＱｏＳ推定値を算出するステップと、
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＩＰ通信ネットワークに関するものである。より詳細には、ＩＰネットワーク上の通信経路に対するサービスの品質（ＱｏＳ）の推定方法およびその方法を利用する装置に関するものである。
【０００２】
【従来の技術】
インターネットの「ベストエフォート」特性は、エンドユーザが認識するＱｏＳ（サービスの品質）を、予想不能にし、また時には大きく変化させる。そのため、ＩＰネットワークのＱｏＳ性能を推定するための、早く、正確で、有効なツールは、ネットワーク通信において重要性を増している。パケットネットワーク、特にインターネットに固有の時々刻々変化する条件下で予想されるユーザおよびプロバイダに対するサービスを維持するため、ＱｏＳに関する情報を使用できるようにするためである。具体例としては、輻輳制御、リアルタイムストリーミングと双方向通信、ＱｏＳ検証、サーバの選択、およびネットワークの管理等が挙げられる。
【０００３】
ＱｏＳ推定方法は、大きく２つのカテゴリに分類することができる。それは、受動的推定方法と能動的推定方法である。受動的推定方法は、ネットワークに測定用の新たなトラフィックを必要としないという利点がある。受動的測定方法は、ネットワークをありのまま測定する。すなわち、測定のための測定トラフィックにより現在のネットワークが乱されることがないので、真のネットワーク挙動が測定される。
【０００４】
測定は、処理能力、記憶容量、および利用可能なリソースの程度により種々のレベルの細分性で行うことができる。パケット測定は、例えば、パケット遅延変化、パケットサイズ分布、およびホスト間のスループットのようなパケット毎の情報の測定を可能にする。より高レベルの、オーバーヘッドの少ない測定は、送信された総バイト数、フローの開始／終了時刻を記録するフローレベル測定により実現できる。
【０００５】
受動的測定技術の主な利点は、測定しようとするネットワークに負荷をかけない点である。これはまた、ネットワークのトラフィックを歪ませないため、実際のネットワーク状態に近い推定を可能にすることを意味する。しかしながら、受動的測定技術の欠点は、実際に存在するトラフィックに依存するので、そのトラフィックが、ある測定に必要とされる特性を有することが保証されないことである。ボトルネック帯域幅の測定技術は、例えば、一定のパケットサイズ分布、パケット間の出発速度を必要とする。トラフィック測定は、ネットワークの性能を推定する目的で受動的に測定トラフィックの特性を測定するものである。
【０００６】
ＳＮＭＰ（Ｓｉｍｐｌｅ　Ｎｅｔｗｏｒｋ　Ｍａｎａｇｅｍｅｎｔ　Ｐｒｏｔｏｃａｌ）およびＲＭＯＮ（Ｒｅｍｏｔｅ　Ｍｏｎｉｔｏｒｉｎｇ）は、受動的測定に最も広く採用されている標準的なものであり、様々なネットワーク要素（ホスト、ルータ、交換機）にインストールされた管理エージェントあるいは測定用のデータ、エージェントから収集されたデータを含むＭＩＢ（Ｍａｎａｇｅｍｅｎｔ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｂａｓｅ）、測定用のデータから情報を収集する管理局／コンソール、および管理局／測定用のデータ間での情報交換のためのプロトコルから構成される。ＭＩＢは、物理層あるいはＩＰ層で収集されたパケットサイズの統計、ＣＲＣ（巡回冗長検査）による誤り等々の様々なグループを有する。管理制御を利用したトラフィック測定は、収集された情報をエージェントからコンソールに転送することを必要とする。測定対象であるネットワークへの負荷はこの程度である。時には、交換されるトラフィックの量を減少させるためにデータのサンプリングを使用することができる。
【０００７】
一方、能動的測定方法は、測定用のデータをネットワークに送信し、通信相手に送信されるまでの遅延、遅延の変化量、および損失の観点から測定用のデータが受ける処理を測定することによりネットワークのＱｏＳを推定する方法である。遅延、ジッタ、パケット損失、帯域幅といった観点から性能を推定するために、多様なツールが存在する。これらのツールは通常、インターネット制御メッセージプロトコル（ＩＣＭＰ）の誤り通報能力、あるいはパケット分散技術のいずれかを用いる。
【０００８】
ビット／秒単位でのリンクの情報路容量の推定は、伝統的にパケット分散技術を用いて行われてきた。パケット分散技術とは、２つ以上のパケットグループを継続的に送信することにある。それは、同一のグループからのパケットは、経路のボトルネックリンクにおいて次々に待たされる（キューイングする）という概念に基づいている。他の競合トラフィック（すなわち、他の発呼端末からのトラフィック）からの干渉がなければ、その分散（すなわち、受信先におけるパケット到着時間の差異）は、ボトルネックの帯域幅に反比例する。この方法を用いたツールの例としては、Ｎｅｔｔｉｍｅｒ、Ｐａｔｈｒａｔｅ、およびＰａｃｋｅｔ　Ｂｕｎｃｈ　Ｍｏｄｅ（ＰＢＭ）がある。
【０００９】
情報路容量推定の別の方法は、ＩＣＭＰの時間超過メッセージ（Ｔｉｍｅ　Ｅｘｃｅｅｄｅｄ　ｍｅｓｓａｇｅ）のオプションに基づくものである。この技術のはしりであるＰａｔｈｃｈａｒというツールは、ＩＰ寿命（ＴＴＬ）値を増加させながらパケットを送信することにより測定を行う。これにより、経路にあるルータは、ＩＣＭＰエラーメッセージを返信し、そのルータ自身を明らかにするのである。エンド・ツー・エンド（ｅｎｄ−ｔｏ−ｅｎｄ）の経路上の連続するホップに対する往復遅延の測定により、ホップ毎の遅延の測定が可能になる。Ｐａｔｈｃｈａｒはまた、各ＴＴＬ値に対してパケットのサイズを変化させる機能を有する。これにより、リンクの情報路容量を、各パケットサイズに対して測定された遅延の最小値を結ぶ線の傾きの逆数として推測するのである。ＰｃｈａｒやＣｌｉｎｋといった他のツールも存在するが、それらもＰａｔｈｃｈａｒと同一の概念に基づいている。
【００１０】
ＣｐｒｏｂｅおよびＰｉｐｅｃｈａｒは、経路上の利用可能な帯域幅を推定するために提案された最初のツールである。これらのツールは、長いパケットトレイン（複数のパケット）の分散を使用している。そのようなパケットトレインの分散は、ボトルネックのホップにおいて、送信に利用可能な速度、すなわち利用可能な帯域幅に反比例すると仮定している。しかしながら、最近の研究では、そのような分散の逆数では実際は利用可能な帯域幅を測定できず、ＡＤＲ（非対称データ速度）と呼ばれる別のパラメータを測定することになることが示されている。
【００１１】
Ｄｅｌｐｈｉという別のツールは、インターネット経路は単一のキューによりモデル化されると仮定している。その仮定によると、経路上のいくつかのリンクにおいて大きなキューイング遅延が存在する場合に、あるいは、ボトルネックの情報路容量とボトルネックの利用可能帯域幅リンクが異なるリンクに位置する場合は、Ｄｅｌｐｈｉの性能は悪化する。
【００１２】
現在において、利用可能帯域幅を推定できるツールは、Ｐａｔｈｌｏａｄと呼ばれるツールしか知られていない。Ｐａｔｈｌｏａｄは、受信先で測定されるエンド・ツー・エンドの遅延は、発呼端末の送信速度が経路の利用可能帯域幅を超えたときに増加するという単純な原理に基づいている。現実的な測定では、ボトルネックが処理できる速度よりも高速で経路に注入されたトラフィックがそのホップでキューを起こし、それによりキューイング遅延および全体の遅延が増加することが知られている。
【００１３】
Ｐａｔｈｌｏａｄは、各ホップにおける転送速度を変化させ、受信先における遅延の変化を測定するといった動作を繰り返し行うことにより作動する。ポイントは、遅延を増加させない最高速度を発見することである。
【００１４】
【発明が解決しようとする課題】
本発明は、ＩＰネットワークにおける通信経路（ＩＰネットワーク上の２つのルータあるいはホスト間のものであることが好ましい）に対するＱｏＳ推定を提供する方法を開示するものである。
【００１５】
【課題を解決するための手段】
ＱｏＳ推定技術は、要求される通信経路にポーリングする通常の原理に基づいて使用される。好適な方法は、次のように構成される。まず、対象となるエンド・ツー・エンドの経路上の全てのルータ／ホストのネットワークアドレスを特定する。次に、タイムスタンプ要求を経路上の各ルータ／ホストに送信する。最後に、その方法は、ＱｏＳ推定値を算出するために、ルータ／ホストから返信されたタイムスタンプ要求の処理を要求する。本発明において、「ホップ」という単語は、各ノード間のエンド・ツー・エンドの経路上にあるルータ／ホストを総称するために使用される。
【００１６】
【課題を解決するための手段】
好適な実施形態において、経路上のホップのアドレスを得るための技術は、Ｔｒａｃｅｒｏｕｔｅアプリケーションを使用することである。加えて、タイムスタンプ要求は、ＩＣＭＰタイムスタンプ要求／返信機能を使用して得られる。本発明は、要求される経路上の全てのホップのアドレスを決定するためにＴｒａｃｅｒｏｕｔｅを使用することから開始する。次に、５つのＩＣＭＰタイムスタンプ要求からなるグループが、経路の一端の発呼端末から測定対象の経路上の各ルータに送信されるのが好ましい。各グループの最初の３つのパケットは、対応するホスト／ルータ（すなわち、ホップ）に対する測定の初期条件を決定するために使用される。５つのパケットからなるグループのうち残りの２つの測定パケットは、対応するホップにおいて、ＩＣＭＰ要求パケットにより費やされた時間の総和の推定値を得るために使用される。
【００１７】
さらに、もう１対の同様なＩＣＭＰタイムスタンプ要求パケットが、同様に各ホップでＩＣＭＰ要求により費やされた時間の合計を推定するために規則的な間隔で各ホップに送信される。そのような継続的測定は、各ホップにおけるキューイング遅延変化の推定のために使用される。本発明の好適な実施形態において、推定値は測定を開始した発呼ノードで算出される。さらに別の実施形態において、そのような推定値は受信先あるいは宛先ノードで算出される。
【００１８】
本発明の好適な実施形態において、各ホップにおけるサービス時間の合計およびキューイング遅延の変化は、各ホップにおいて経路方向の利用率の推定のために使用される。それは、リンクにおいて競合トラフィックに使用されていない、空いている送信リソースの部分を指す。算出される推定値はまた、経路方向の各リンクの利用可能な帯域幅の推定のために使用される。利用可能な帯域幅は、リンクが輻輳およびキューの発生なしにさらに維持することができる速度を指す。加えて、推定値は、競合する発呼端末からリンクに導入されるトラフィックの速度を推定するために使用される。
【００１９】
本発明の好適な実施形態において、提案されたアプリケーションは、ＱｏＳ測定を開始した１つのノードにのみ存在する。このノードは、ホップから収集されたタイムスタンプ値に基づいてＱｏＳ推定のために必要な処理を行う。別の実施形態において、提案されたアプリケーションは、測定対象となる経路の発呼端末および受信先の両方に存在してもよい。その場合、受信先は、収集されたタイムスタンプ値を処理する役割をもつ。その違いは、ルータに送信されたＩＣＭＰパケットは宛先端末に対しスプーフィングするアドレスを有し、したがって応答はＩＣＭＰ要求をした発呼端末ではなく受信先に送信されることである。
【００２０】
本発明のさらなる目的および利点は、本発明の好適な実施形態を図示した図面を参照しながら以下の説明で明らかになる。
【００２１】
【発明の実施の形態】
まず図１を参照して説明する。ＩＰネットワーク１０は、少なくとも２つの端末（ノード）を有すると概ね図示されている。その少なくとも２つの端末は、複数のルータ（ホスト）１２、およびＩＰネットワーク１０上のルータ（ホスト）１２を介して互いに通信する。ルータ（ホスト）１２の集合、各エンドの端末（ノード）、およびそれらを接続するリンクにより、経路が構成される。送信時、データグラムは、宛先端末に到達するためにいくつかのホップを通過する。これらのホップは、ルータ（ホスト）１２全体を指してもよい。このように本願において「ホップ」という単語は、ホストおよびルータの両方を含むと解釈される。送信するノード（端末）は、経路の発呼端末（要するに、発呼端末）ということができ、また受信するノード（端末）は、経路の宛先端末（要するに、宛先端末）というできる。図１の通り、発呼端末は、リモート端末１４でも固定端末１６でもよい。同様に、宛先端末もリモート端末１８でも固定端末２０でもよい。
【００２２】
固定端末１６および２０は、固定リンクを介してルータ１２の各々に直接接続されている。リモート端末１４および１８は、無線ホップ２２を介してアクセスポイント２４に接続されている。アクセスポイント２４は、通常、通信塔２６およびルータ１２を有する。リモート端末１４および１８は無線電話として描かれている。しかし、無線ＩＰネットワーク１０で使用されるリモート端末としては、無線電話に限られず、個人情報端末（ＰＤＡ）、携帯型コンピュータ等であってもよいことは当業者にとって自明である。したがって、図１における無線電話の描写は例示であり本発明を限定するものではない。さらに図１に示されるように、ルータ１２の各々は少なくとも１つの他のルータに接続されており、これにより端末間でＩＰネットワーク１０を介したパケット送信が可能になっている。
【００２３】
リモート端末である無線電話機は、ＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）や各種メモリを有する制御部、アクセスポイント２４と無線通信を行う無線通信部、ユーザが各種指示を入力するための操作入力部、各種情報を表示するための液晶表示部、音声通話を行うためのマイク及びスピーカ（いずれも図示略）などを備えている。また、固定端末は例えばコンピュータ装置であり、ＣＰＵや各種メモリを有する制御部、ハードディスク等の記憶装置、ネットワークと通信を行うための通信部、ユーザインターフェース（いずれも図示略）によって構成される。
【００２４】
図２には、ルータ１２における典型的なＩＰパケット処理の様子が図示されている。ＩＰパケットは、複数の入力ラインカード（Ｉｎｇｒｅｓｓ　Ｌｉｎｅ　Ｃａｒｄ）３０に到着し、ＩＰ処理段階３２に入る。次にパケットは、典型的にはルータ１２の特定の実行状況に依存して入力キュー３４あるいは出力キュー３６に置かれる。スイッチファブリック３８は、パケットを適切な出力ラインカード（Ｅｇｒｅｓｓ　Ｌｉｎｅ　Ｃａｒｄ）４０に誘導する。キューイングは、スイッチファブリック３８への入力および出力のどちらでも起こる可能性がある（もっとも最近のルータは入力キューイングを実行している）。しかし、キューイングは通常ＩＰ処理３２の後に起こる。後で詳細に説明するとおり、ＩＣＭＰタイムスタンプのオプションを使用する場合、ＩＣＭＰタイムスタンプ要求により引き出されたタイムスタンプは、入力キュー３４／出力キュー３６にエントリーする前の時刻を記録する。パケットは通常通信線の速度で取り扱われ、ＩＰ処理ステージ３２に対する待ち時間および実際の処理時間は、スイッチファブリック３８におけるキューイングおよび出口線カード４０における送信時間と比較して無視することができるので、ＩＰ処理の時間は短くてすむ。ＩＰ処理３２後のパケットのキューイングは、他のパケットが送信されるまでの待ち時間によるものである。キューイング遅延は、測定対象となるパケットの到達時におけるキューのサイズおよびリンクの転送速度と直接的に関連している。パケットは、キューが空くのを待って、送信される。
【００２５】
以降の議論においては、以下の項目を表すために次のような記号が使用される。ｔｎすなわちｎは、イベントが記録される時刻を表す。Ｑｉ（ｎ）は、時刻ｎ、リンクｉにおけるキューのサイズ（ビット）を表す。Ｂｉは、リンクｉの情報路容量（ビット／秒）を表す。Ｒｉ（ｎ）は、時刻ｎにキューに入ってくるフローの速度の総和（ビット／秒）を表す。ｑｉ（ｎ）は、時刻ｎにおいて、ルータｉにおけるキューイング遅延を表す。ｍは、パケットのサイズ（ビット）を表す。
【００２６】
時刻ｎにキューに入ったパケットに対して、既にキューに入っているデータのサイズはＱｉ（ｎ）である。そのパケットのキューイング遅延ｑｉ（ｎ）は、速度Ｂｉ（すなわち、パケットのキューイング遅延）において、リンクｉ中のキューを空けるのに必要な時間であり、以下のように表せる。
【数１】
2004040793.tif 000003
【００２７】
速度Ｂｉは、情報路容量、つまりリンクがデータを送信する速度を指す。つまり、リンクの転送速度のことである。したがってこの値は、ルータとネットワークの接続配置に固有の値である。
【００２８】
図３は、入ってくるフロー速度の変化に対する空いているキューのサイズ（つまり、キューイング時間）の変化を示す。Ｒｉが速度Ｂｉより小さい限り、キューサイズは増えない（Ｒｉが速度Ｂｉと等しい場合、リンクは出力ラインカード上でビットを直列化することができる）。しかし、インターネットトラフィックは爆発的に増加する性質のものであるため、Ｒｉが情報路容量Ｂｉを超え、キューイングが起こる可能性がある。本発明の目的に対して、時刻ｎにおけるリンクｉの利用率は以下のように定義される。
【数２】
2004040793.tif 000004
【００２９】
図３を参照すると、次の式が得られる。
【数３】
2004040793.tif 000005
あるいは、
【数４】
2004040793.tif 000006
ここで、簡略化のため、時刻ゼロにおけるネットワーク初期化の際には、全てのリンクにおけるキューは空いている、すなわち、全てのｉに対しＱｉ（０）＝０であると仮定している。
【００３０】
後で変化させるため、ｔｒ−１、ｔｒ間の時間間隔は、一定に設定されない。数１および数３から、次式が得られる。
【数５】
2004040793.tif 000007
また、数１および数４から
【数６】
2004040793.tif 000008
数２を数６に代入すると、
【数７】
2004040793.tif 000009
したがって利用率は次式のように表される。
【数８】
2004040793.tif 000010
【００３１】
通過時間Ｔｉ（ｎ）は、時刻ｎにおいて、ある連続したｍビットのデータがリンクを通過するのに必要な時間である。すなわち、通過時間は次式で表される。
【数９】
2004040793.tif 000011
【００３２】
ｍ／Ｂはまた、リンクの転送時間も指している。ここで定義される通過時間は、転送遅延およびキューイング遅延の総和であるが、伝播遅延および処理遅延は無視している。数７および数９から、次式が得られる。
【数１０】
2004040793.tif 000012
したがって、Ｂｉは次式のように表される。
【数１１】
2004040793.tif 000013
【００３３】
次に、数２を数１１に代入すると、Ｒｉは次式のように表される。
【数１２】
2004040793.tif 000014
【００３４】
新たなフローに対する利用可能な帯域幅は、あるリンクがサポートできる速度である。つまり、キューのサイズ（すなわち、キューイング遅延）が増えないような速度である。つまり、利用可能な帯域幅は、リンクの情報路容量Ｂのうち、速度の総和がＲである競合するフローに使用されない部分であり、次式のように表される。
【数１３】
2004040793.tif 000015
【００３５】
数２を数１３に代入すると、次式が得られる。
【数１４】
2004040793.tif 000016
ここで、ＡｖＢｗｉ（ｎ）は、時刻ｎ、リンクｉにおける利用可能な帯域幅である。
【００３６】
利用可能な帯域幅の測定値は、その経路が輻輳が始まることにより、遅延およびジッタの発生なしで付加できる入力フローのマージンを評価するのに使用することができる。例えば、音声符号機に対する帯域幅要求は、利用可能帯域幅の観点からのものである。
【００３７】
スループットは、通常、リンクあるいは経路を介して一定量のビットのデータを得るのに必要な時間を測ることにより測定される。したがって、受信先において測定されるリンクｉのスループットは、次式のように表される。
【数１５】
2004040793.tif 000017
ここで、ＴｈｒＢｗｉ（ｎ，ｋ）は、時刻ｎ，ｋにおけるリンクｉのスループット（ビット／秒）である。データパケットのサイズはビット単位で測定され、それは「データチャンク（ｄａｔａ　ｃｈｕｎｋ）」と呼ばれる。データチャンクは、種々のサイズのパケットで構成されることが可能である。Ｂｉはリンク情報路容量、ｑｉはリンクのｋビットチャンクのキューイング遅延である。
【００３８】
複数のリンクにより構成される経路全体に対して、数１５を使用すると、スループットは次式のように表される。
【数１６】
2004040793.tif 000018
【００３９】
数１６の右辺の分母は、実際にリンクおよび経路それぞれを通過するのに必要な遅延に対応している。したがって、スループットは、ネットワークにおける遅延状態を示す良い指標である。このように、スループットは、それ自体ではここで定義されるリンクあるいは経路の情報路容量、あるいは利用可能な帯域幅を表すものではない。
【００４０】
しかしながら、次のような方法でリンクあるいは経路の情報路容量、あるいは利用可能な帯域幅の測定に関連する。
【００４１】
数２および数５を連続した領域に拡張すると、次式が得られる。
【数１７】
2004040793.tif 000019
次に、数１４を用いると、次式が得られる。
【数１８】
2004040793.tif 000020
最後に、この結果を数１５に代入すると、スループットは次式のように表される。
【数１９】
2004040793.tif 000021
【００４２】
図４は、好適な実施形態における方法の全体的な動作を示す図である。この方法の本質は、連続するホップにおけるキューイング遅延の変化を推定することである。したがって、前述の数２、数１１〜数１３は、情報路容量Ｂ、利用可能帯域幅ＡｖＢｗ、入ってくる競合フローＲの総和、および利用率ｕの推定に使用される。
【００４３】
図４に示されるように、好適な方法は、その経路の発呼端末１４および１６からその経路の宛先端末１８および２０までに存在するルータ（ホップ）１２全部のネットワークアドレスを特定することから始まる（ステップ４０）。本方法の好適な実施形態において、これは、Ｔｒａｃｅｒｏｕｔｅアプリケーションを使用して実現される。次のステップは、経路上の各ホップにおけるキューイング遅延の第１の推定値を得ることである（ステップ４２）。ステップ４０とステップ４２を合わせて、好適な方法の初期化（ブートストラップ）段階４４と呼ぶ。それから、複数組のＩＣＭＰタイムスタンプ要求は、各ルータ１２に通常の間隔で送信される。これにより、前述の数式群４８を用いてルータ１２におけるキューイング遅延変化４６の測定が可能になる。また、ＩＣＭＰタイムスタンプ要求の各々により、図４で５０と示される、ルータ１２の各々に対するＱｏＳパラメータ（情報路容量、利用可能な帯域幅、スループット）について１つの推定値の生成が可能になる。さらに、リンクの利用率および競合トラフィックのサイズが推定される。図４で示されているステップ４６、４８、５０を合わせて、測定段階と呼ぶ。
【００４４】
測定は、エンド・ツー・エンドの経路上の全てのホップを特定するために、Ｔｒａｃｅｒｏｕｔｅアプリケーションを発呼端末１４あるいは１６に呼び出すことにより開始される。いったんホップのリストが得られると、本発明において、各ホップにおける遅延の変化量を得るために複数組のＩＣＭＰタイムスタンプ要求を使用する。以下は、あるホップに対しこれを実現する方法の説明である。その手順は、経路上の全てのホップに対し共通である。
【００４５】
図５は、連続したルータ１２における１組のＩＣＭＰタイムスタンプ要求６０および６２の処理の好適な実施形態を示す。第１のルータに到着後、第１のパケット６０は、ＩＰ処理部６６からタイムスタンプを受け取る。次に、好適な実施形態において、第１のパケット６０は、第１のルータ６４の返信キュー６８を介してその発信元に戻る。第２のパケット６２は、送信キュー７０、リンク７２を通って、第２のルータ７４のＩＰ処理部６６に到達しタイムスタンプを受け取る。次に、好適な実施形態において、第２のパケット６２は、第２のルータ７４の返信キュー６８を介してその発信元に戻る。
【００４６】
図５に示される第１のルータ６４から第２のルータ７４までのリンクにおけるキューイング遅延の変化を得るために、２つのＩＣＭＰタイムスタンプ要求が、第１のパケットの最終ビットの送信と第２のパケットの最初のビットの送信の時間差が生じないように次々に送信される。第１のパケットのＩＣＭＰ要求は、第１のルータ６４に指示され、第２のパケットのＩＣＭＰ要求は、第２のルータ７４に送信される。同一のペアに属するパケットは、識別子あるいはＩＣＭＰパケットのシークエンス番号フィールドを用いて特定される。
【００４７】
そのパケットペアの第１のパケットの、第１のルータ６４におけるタイムスタンプは、Θｉ１で表され、そのペアの第２のパケットの、第２のルータ７４におけるタイムスタンプは、Θｉ＋１２で表される。異なる時間軸上での測定を一般性を損なうことなく特定するため、ＩＣＭＰタイムスタンプ要求により報告される、同一のパケットペアのタイムスタンプは、第２のパケットがタイムスタンプを受け取ったときに記録されると仮定する。これは、記号Θｉ１（ｊ）とΘｉ＋１２（ｊ）に等しく、両方のタイムスタンプは、同時刻ｊに集積されることを意味する。次の関係は、これらのタイムスタンプの差を表す。
【数２０】
2004040793.tif 000022
ここで、ｍはＩＣＭＰタイムスタンプ要求パケットのサイズ（すなわち、ＩＣＭＰに対しては４０バイト、ＩＰに対しては２０バイト）である。ｑｉ（ｊ）は、第１のルータ６４から第２のルータ７４まで送信されるのを待っているパケットペアｊのキューイング遅延である。そして、ｄｉ→ｉ＋１（ｊ）は、２つのルータ間の伝播遅延である。
【００４８】
重要なことは、第１のパケットのタイムスタンプは、パケットが第１のルータ６４のＩＰ処理段階を出発した時刻を示すだけでなく、第２のパケットが同一の段階を出発した時刻も示すと仮定している点である。この仮定が成り立つためには、２つのＩＣＭＰパケットが、他のパケットの後で到達することが必要である。すなわち、これら２つのパケットがキューのため第１のルータ６４に到達するまで、２つのパケット間に干渉トラフィックは存在しないということである。これは、ほとんどの場合実情にあっていると考えられる。
【００４９】
伝播遅延、処理遅延を無視すると、次式が得られる。
【数２１】
2004040793.tif 000023
数２１は、前述の数９と同一である。すなわち、数２１は、リンク７２経由で第１のルータ６４から第２のルータ７４までの移動時間を定義する。リンクにおける送信時間およびキューイング時間は考慮しているが、伝播遅延および処理遅延は無視している。
【００５０】
第１のパケットペアの送信後、送信機は次のパケットペアを送信する前に、ユーザが定義した遅延αだけ待機する。今度は、集積される測定は、Θｉ１（ｊ＋１）とΘｉ＋１２（ｊ＋１）である。したがって、キューイング遅延変化は次式のように推定される。
【数２２】
2004040793.tif 000024
ここで数８を用いて、
【数２３】
2004040793.tif 000025
ここでｕｉ（ｊ＋１）は、第１のルータ６４と第２のルータ７４の間のリンクｉ７２における利用率であり、時刻ｔｊにおいて、２つの測定の組ｊおよびｊ＋１間で測定されたものである。さらに、
【数２４】
2004040793.tif 000026
であり、ここで、情報路容量Ｂｉは、数２１を用いて次式のように定義できる。
【数２５】
2004040793.tif 000027
【００５１】
数２５で未知の変数は、時刻ｔｊにおける第１のルータ６４におけるキューイング遅延である。キューイング遅延は次式のように表せる。
【数２６】
2004040793.tif 000028
ここで、Δｑｉ（ｊ−１，ｊ）は、パケットｊ−１とパケットｊのペアにより測定される、第１のルータ６４におけるキューイング遅延の変化である。したがって、キューイング遅延は次式のように表せる。
【数２７】
2004040793.tif 000029
【００５２】
数２７において、ｑｉ（０）は、測定開始時に第１のパケットペアが体験するキューイング遅延の推定値である。第１のルータ６４における第１のキューイング遅延の推定値ｑｉ（０）は、まず、３つの連続したＩＣＭＰタイムスタンプ要求を（最初の１つを第１のルータ６４へ、残りの２つを第２のルータ７４へ）送信することにより、最初の測定過程において得られる。これにより次の式が導かれる。
【数２８】
2004040793.tif 000030
【００５３】
したがって、第１のルータ６４から第２のルータ７４間のリンクの時刻０における情報路容量Ｂｉの推定値が次式のように得られる。
【数２９】
2004040793.tif 000031
【００５４】
情報路容量Ｂｉの推定値は、後述するように測定が進むにつれ後に更新される。しかし、時刻０（ゼロ）における数２１は、次式のようにも書ける。
【数３０】
2004040793.tif 000032
ここで、数２９と合わせて、キューイング遅延は次式のように表される。
【数３１】
2004040793.tif 000033
【００５５】
リンクｉにおけるキューイング遅延の初期の推定値は、数２７の測定過程を通じて使用することができる。また、数２７を使用して得られる推定値より良い推定値を得るために３つの連続したＩＣＭＰパケットを送信するという手順を通じて、キューイング遅延の推定を測定イベントごとに繰り返すことができる。
【００５６】
ｑｉ（ｊ）の推定値が得られると、それはリンクの情報路容量Ｂｉを推定するために数２５で使用される。したがって、Ｂｉは、数２５、数２７、数３１を用いて推定することができる。ここで入ってくる競合フローＲｉの総和は、数２、数２３、数２５、数２７、および数３１を用いて推定することができる。これはまず、情報路容量Ｂｉの推定により実行される。次に数２３を使用して利用率を推定する。そして数２を使用してＲｉを得る。さらに、利用可能な帯域幅ＡｖＢｗｉは、数２、数１３、数２３、数２５、数２７、および数３１を用いて、同一の過程により推定することができる。
【００５７】
本発明の好適な実施形態において、ルータ１２の全ては、規則的に、そして同一の頻度で測定される。さらに別の実施形態では、特定のルータ１２は、そのルータ自身のキューイング遅延の変化率に基づいて、測定頻度を変更してもよい。本発明の実施形態において、経路のホップのアドレスは、まずＩＣＭＰペアの送信が始まった後に特定される。さらに別の実施形態において、各ホップに対するＩＣＭＰペアの送信は、そのホップが特定されるとすぐに始まる。
【００５８】
本発明の好適な実施形態において、ＩＣＭＰタイムスタンプ要求は、ＩＣＭＰプロトコルで定められた標準サイズである。さらに別の実施形態においては、ＩＰペイロードフィールドにダミーデータが付加されてもよい。これにより、ルータにおける転送時間が増加するが、非常に高速なリンクに対しては有用な機能である。本発明の好適な実施形態において、経路の特定とタイムスタンプ要求は、発呼端末あるいは宛先端末のどちらからも送信される。さらに別の実施形態では、種々のタイムスタンプ要求および経路の特定は、発呼端末、受信先、あるいはネットワークの他のホストから同時に送信されてもよい。さらに、測定の処理は、ネットワーク上のホストの任意の１つ、一部、あるいは発呼端末および通信先ホストを含む全てのホストにおいて実行されてもよい。
【００５９】
この方法は、タイムスタンプ要求パケットのペアが経路上の最も遅いリンク（ボトルネックリンク）を介した送信を回避するように改良できる。これは、タイムスタンプ要求パケットのペアがそのリンクに到達したときのタイムスタンプ間の分散を回避するということである。これを実現するために、測定は、ボトルネックリンクを回避するために、発呼端末あるいは宛先ノードのどちらからも行われる。本発明の好適な実施形態において、種々のリンクの変化率の測定により、ボトルネックが特定される。この方法はまた、リンクの伝播遅延を考慮して測定の精度をさらに向上させることにより更に改良される。これは、伝播遅延の推定により実現される。
【００６０】
本発明は、現在最も好適と考えられる動作および実施の態様で説明されているが、本発明に関する他の態様、実施形態、および利点は、当業者には明らかであり、ここに含まれる。
【００６１】
【発明の効果】
以上で説明したように、本発明によれば、ＩＰネットワークにおける通信経路に対するＱｏＳ推定値を得ることができる。
【図面の簡単な説明】
【図１】ＩＰネットワークの例を示す図である。
【図２】ルータのパケット処理の詳細を示す図である。
【図３】入力速度に対するキューイングサイズの変化の例を示す図である。
【図４】好適な方法のフローチャートである。
【図５】１組のホップにおけるＩＣＭＰタイムスタンプ要求の処理の一例を示す図である。
【符号の説明】
１０……ＩＰネットワーク、１２……ルータ、１４、１８……リモート端末、１６、２０……固定端末、２４……アクセスポイント、３０……入力ラインカード、３４……入力キュー、３６……出力キュー、３８……スイッチファブリック、４０……出力ラインカード
【図１】
2004040793.tif 000034
【図２】
2004040793.tif 000035
【図３】
2004040793.tif 000036
【図４】
2004040793.tif 000037
【図５】
2004040793.tif 000038