(57)【要約】  データ伝送経路における状態が適切にモデル化されれば、その状態の推定値を提供するためにフィルタベースのアプローチを使用することができる。これにより、データ処理リソース及びメモリリソースに関して控え目な要求条件で、状態に関する正確でリアルタイムの推定が可能になる。
2009516984.tif 000002
【特許請求の範囲】
【請求項１】
データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する方法であって、
前記データ伝送経路のリアルタイム動作中に前記データ伝送経路を通過するプローブパケットを提供するステップと、
前記プローブパケットによる前記データ伝送経路の通過に応えて、且つ前記データ伝送経路の前記リアルタイム動作中に、前記状態を推定するために使用する推定データを提供するステップと、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成するステップであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するステップを含むステップと、
を備えることを特徴とする方法。
【請求項２】
前記状態は、前記データ伝送経路において利用可能な帯域であることを特徴とする請求項１に記載の方法。
【請求項３】
前記適用するステップは、カルマンフィルタを使用するステップを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記適用するステップは、カルマンフィルタを使用するステップを含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記データ伝送経路の通過の直前及び直後に前記プローブパケットそれぞれに対してタイムスタンプを提供するステップを含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記適用するステップは、前記推定データによって表される特性に対応する状態ベクトルを使用するステップを含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記特性は区分的に線形であることを特徴とする請求項６に記載の方法。
【請求項８】
前記生成するステップ及び前記適用するステップのうちの一方を、関連する前記推定データが前記区分的に線形な特性の複数の線形部分の所定の１つに対応する場合にのみ実行するステップを含むことを特徴とする請求項７に記載の方法。
【請求項９】
前記状態は、前記データ伝送経路において利用可能な帯域であり、
前記１番目に述べた提供するステップは、所定の速度で前記データ伝送経路中に前記プローブパケットのシーケンスを送信するステップを含み、
前記線形部分の前記所定の１つは、前記所定の速度が前記利用可能な帯域の現在の推定値と同じだけ大きい状況に対応する
ことを特徴とする請求項８に記載の方法。
【請求項１０】
前記１番目に述べた提供するステップは、所定の速度で前記データ伝送経路中に前記プローブパケットのシーケンスを送信するステップを含み、前記シーケンスの１つのプローブパケット中に前記所定の速度を示す情報を提供することを含む
ことを特徴とする請求項１に記載の方法。
【請求項１１】
前記１番目に述べた提供するステップは、前記データ伝送経路中に複数の前記プローブパケットのシーケンスをそれぞれ対応する複数の速度で送信するステップを含み、
前記生成するステップは、前記シーケンスのいくつかにそれぞれ対応する前記状態の推定値を生成するステップを含む
ことを特徴とする請求項１０に記載の方法。
【請求項１２】
データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する装置であって、
前記データ伝送経路のリアルタイム動作中に前記データ伝送経路を通過してきたプローブパケットを受信するデータ生成ユニットであって、前記プローブパケットによる前記データ伝送経路の通過に応えて、前記データ伝送経路の前記リアルタイム動作中に、前記状態を推定するために使用する推定データを生成するデータ生成ユニットと、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成する、前記データ生成ユニットに結合された推定ユニットであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するフィルタを含む推定ユニットと、
を備えることを特徴とする装置。
【請求項１３】
前記推定ユニットと、前記データ生成ユニットの一部とは、前記データ生成ユニットの残りの部分から物理的に離れて配置されることを特徴とする請求項１２に記載の装置。
【請求項１４】
前記フィルタはカルマンフィルタを含み、
前記状態は前記データ伝送経路中において利用可能な帯域である
ことを特徴とする請求項１２に記載の装置。
【請求項１５】
前記推定データは区分的に線形な特性を表し、
前記フィルタは、前記区分的に線形な特性に対応する状態ベクトルを使用する
ことを特徴とする請求項１２に記載の装置。
【請求項１６】
前記フィルタは、前記推定データが前記区分的に線形な特性の複数の線形部分の所定の１つに対応する場合にのみ前記フィルタ動作を適用するように構成されることを特徴とする請求項１５に記載の装置。
【請求項１７】
前記データ生成ユニットは、前記区分的に線形な特性の複数の線形部分の所定の１つに対応する前記推定データのインスタンスのみを生成するように構成されることを特徴とする請求項１５に記載の装置。
【請求項１８】
データネットワークに結合され、前記データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する装置であって、
前記データ伝送経路のリアルタイム動作中に前記データ伝送経路を通過するプローブパケットを提供するように構成された、前記データ通信ノードのうちの１つと、
前記プローブパケットによる前記データ伝送経路の通過に応えて、前記データ伝送経路の前記リアルタイム動作中に、前記状態を推定するために使用する推定データを生成するデータ生成ユニットを含む、前記データ通信ノードのうちの他の１つと、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成する、前記データ生成ユニットに結合された推定ユニットであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するフィルタを含む推定ユニットと、
を備えることを特徴とする装置。
【請求項１９】
前記データネットワークは、インターネット及びプライベートイントラネットのうちの１つを含むことを特徴とする請求項１８に記載の装置。
【請求項２０】
前記フィルタはカルマンフィルタを含み、
前記状態は前記データ伝送経路中において利用可能な帯域である
ことを特徴とする請求項１８に記載の装置。
【請求項２１】
前記推定ユニットは、前記他のデータ通信ノードから物理的に離れて配置されることを特徴とする請求項１８に記載の装置。
【請求項２２】
データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する装置であって、
前記データ伝送経路のリアルタイム動作中に推定データを受信する入力部と、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成する、前記入力部に結合された推定ユニットであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するフィルタを含む推定ユニットと、
を備え、
前記推定データは、前記データ伝送経路の前記リアルタイム動作中のプローブパケットによる前記データ伝送経路の通過に応えて、前記データ伝送経路の前記リアルタイム動作中に生成される
ことを特徴とする装置。
【請求項２３】
データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する方法であって、
前記データ伝送経路のリアルタイム動作中に前記データ伝送経路を通過するプローブパケットを提供するステップと、
前記プローブパケットによる前記データ伝送経路の通過に応えて、且つ前記データ伝送経路の前記リアルタイム動作中に、前記状態を推定するために使用する推定データを提供するステップと、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成するステップであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するステップを含むステップと、
ランダムに選択した複数の時点でプローブパケットを提供する前記ステップを繰り返すステップと、
を備えることを特徴とする方法。
【請求項２４】
データネットワークに結合され、前記データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する装置であって、
前記データ伝送経路のリアルタイム動作中に前記データ伝送経路を通過するプローブパケットを提供するように構成された、前記データ通信ノードのうちの１つと、
前記プローブパケットによる前記データ伝送経路の通過に応えて、前記データ伝送経路の前記リアルタイム動作中に、前記状態を推定するために使用する推定データを生成するデータ生成ユニットを含む、前記データ通信ノードのうちの他の１つと、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成する、前記データ生成ユニットに結合された推定ユニットであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するフィルタを含む推定ユニットと、
を備え、
前記１つのデータ通信ノードは、ランダムに選択した複数の時点でプローブパケットを提供することを繰り返すように構成される
ことを特徴とする装置。
【請求項２５】
データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する方法であって、
前記データ伝送経路のリアルタイム動作中に前記データ伝送経路を通過する２Ｎ個のプローブパケットのシーケンスを提供するステップと、
前記プローブパケットによる前記データ伝送経路の通過に応えて、且つ前記データ伝送経路の前記リアルタイム動作中に、前記状態を推定するために使用する推定データを提供するステップであって、前記２Ｎ個のプローブパケットをプローブパケットのＮ個のペアとして処理するステップを含むステップと、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成するステップであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するステップを含むステップと、
を備えることを特徴とする方法。
【請求項２６】
データネットワークに結合され、前記データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する装置であって、
前記データ伝送経路のリアルタイム動作中に前記データ伝送経路を通過する２Ｎ個のプローブパケットのシーケンスを提供するように構成された、前記データ通信ノードのうちの１つと、
前記プローブパケットによる前記データ伝送経路の通過に応えて、前記データ伝送経路の前記リアルタイム動作中に、前記状態を推定するために使用する推定データを生成するデータ生成ユニットを含む、前記データ通信ノードのうちの他の１つと、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成する、前記データ生成ユニットに結合された推定ユニットであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するフィルタを含む推定ユニットと、
を備え、
前記データ処理ユニットは、前記２Ｎ個のプローブパケットをプローブパケットのＮ個のペアとして処理する
ことを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概してデータネットワークに関し、より詳細には、データネットワークにおけるデータ伝送経路の評価に関する。
【背景技術】
【０００２】
以下に列挙する文書を、ここに参照により本願に組み込む。
2009516984.tif 000003
2009516984.tif 000004
2009516984.tif 000005
ＳＬＡ（サービス・レイヤ・アグリーメント）の検証とネットワークの監視とサーバの選択とを含むいくつかの文脈において、データネットワークにおける経路上でエンド・ツー・エンドで利用可能な帯域を測定する機能は有用である。エンド・ツー・エンドのネットワーク経路に関して利用可能な帯域を受動的に監視することは、経路中の全ネットワークにアクセス可能であれば、原理上は可能である。しかしながら、通常これは可能ではなく、通常はネットワーク経路のアクティブプロービングによってエンド・ツー・エンドで利用可能な帯域の推定が行われている。利用可能な帯域は、ネットワーク中にプローブトラヒック（調査用トラヒック）を投入してプローブ上のクロストラヒックについて観察された影響を分析することによって推定可能である。この種の能動的測定では、送信側ホスト（ノード）及び受信側ホスト（ノード）のみに対するアクセスが必要とされ、送信側と受信側との間の経路中のいかなる中間ノードに対するアクセスも必要とされない。
【０００３】
アクティブプロービングに関する従来のアプローチは、利用可能な全帯域を一時的に使用して輻輳を引き起こすのに十分な速度で、対象の経路中にプローブパケットトラヒックを注入することを必要とする。少数のプローブパケットしか使用されなかった場合、誘発された一時的な輻輳はノード中のバッファキューによって吸収可能である。従って、パケットロスは引き起こされず、いくつかのパケットに関して経路遅延の小さな増大が引き起こされるだけである。利用可能な帯域に関する所望の測定は、遅延の増大に基づいて判断される。プローブパケットは、様々なプローブパケット速度で、ペアで又は連なって(in trains)送信可能である。経路遅延が増大し始めるプローブパケット速度は輻輳のポイントに対応し、それゆえ、利用可能な帯域を示す。プローブパケットはまた、所与の連なり(train)内のプローブパケット間の時間的間隔が変化するようにも送信可能なので、各連なりは一連のプローブ速度をカバーすることができる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
上述したような従来のソリューションは、利用可能な帯域に関するリアルタイムの推定値を生成しないか、又は、利用可能な帯域に関する十分に正確な推定値を生成しないか、或いはその両方である。これらのソリューションはまた、大きなデータ処理リソースを必要とするか、又は、大きなメモリリソースを必要とするか、或いはその両方である。
【０００５】
それゆえ、従来のソリューションに係る上述した困難無しにデータネットワーク中の経路の利用可能な帯域を推定可能な、アクティブプロービングソリューションを提供することが望まれる。
【課題を解決するための手段】
【０００６】
本発明の典型的な実施形態は、状態の推定を提供するフィルタベースのアプローチを使用することを可能にするためにデータ伝送経路の状態を適切にモデリングすることを提供する。これにより、データ処理リソース及びメモリリソースに関して控え目な要求条件で、状態に関する正確でリアルタイムの推定が可能になる。
【発明を実施するための最良の形態】
【０００７】
本発明の典型的な実施形態は、パケット交換ネットワークの経路（例えば、インターネット又は他のＩＰネットワーク上の２つのホスト又はネットワークノードの間の経路）に関連する、時間依存の状態に関する高速で正確な推定を提供する。対象の状態に関するネットワークモデルの変数を推定するために、フィルタリングと共にアクティブブロービングが使用される。そして、推定された変数に基づいて対象の状態の推定値が取得される。
【０００８】
ネットワーク経路を跨ってプローブパケットを特定のパターンで送信することにより、ネットワーク経路のプロパティ（性質）がサンプリングされる。プローブパケットのタイムスタンプが送信時及び受信時に記録され、ネットワークモデルの変数に関する量の測定結果を提供する。対象の状態を追跡することが望まれている限り、これは何度も繰り返される。
【０００９】
フィルタリングの使用は、リアルタイムの推定を可能にする。システムをサンプリングすることによって取得される新しい測定結果それぞれについて、ネットワークモデルの単数又は複数の変数に関する新しい推定値が、前回の推定値と新しい測定結果とから算出される。これにより、ネットワーク経路の新しいサンプリング毎に、対象の状態に関する更新された推定値（即ち、新しい推定値）を次々に生成することが可能になる。サンプリング（即ち、測定）は適宜頻繁に実行可能であるので、その結果リアルタイムの応答がもたらされる。それゆえ、フィルタは、システム状態に関する前回の推定値
2009516984.tif 000006
及び新しい測定結果ｚｋを入力として取り、これらの入力に基づいてシステム状態の新しい推定値
2009516984.tif 000007
を算出することができる。これにより、フィルタは、状態変数の推定値をリアルタイムで生成すること、即ちシステム状態を追跡することが可能となる。
【００１０】
推定フィルタの一例は、確立している高速且つ軽量なカルマンフィルタである。カルマンフィルタを適用することを可能にするために、システムモデル及び測定モデルの両方が、線形な（リニアな）形で表現される必要がある。即ち、新しいシステム状態は前回のシステム状態に加えてノイズの項目にリニアに依存し、測定された量はシステム状態の変数に加えてノイズの項目にリニアに依存する。
【００１１】
システム状態の変数の推定に対するフィルタベースのアプローチを更に説明する前に、推定対象の状態及び適切な測定技術の例を説明する。
【００１２】
本発明のいくつかの実施形態において、例えば、推定対象の状態とはネットワーク経路の利用可能な帯域である。利用可能な帯域の概念は、以下の通り理解可能である。ネットワーク経路の各リンクｊがある容量Ｃｊを持ち、これはリンクの各端点のノードにおけるネットワークインタフェースによって判定される。容量Ｃｊは単純にリンク上のパケットレベルでの最も可能性の高いビットレートである。一般的に容量は短いタイムスケールでは変化しない。しかしながら、所与のリンクｊ上のＳｊ（ｔ）と示される負荷或いはクロストラヒックは変化する。リンクｊについて利用可能な帯域Ｂｊ（ｔ）は、Ｂｊ（ｔ）＝Ｃｊ−Ｓｊ（ｔ）である。経路に沿う複数のリンクｊのうちの１つが、最小の利用可能な帯域を持つ。この「ボトルネックリンク」が、経路の利用可能な帯域を決定する。ネットワーク経路の利用可能な帯域Ｂ（ｔ）は、それぞれその構成するリンクに関連する利用可能な帯域の最小値
2009516984.tif 000008
である。
【００１３】
あらゆる時刻ｔでのネットワーク経路の利用可能な帯域は、それゆえ、時刻ｔにおいて理論上輻輳を引き起こさずに行える送信側から受信側へのデータレートの最大増加量として解釈可能である。
【００１４】
なお、クロストラヒック負荷及び利用可能な帯域は、何らかの平均化タイムスケールであるタウを使用して定義される。即ち、Ｓｊ（ｔ）は、ある時間間隔長タウに亘って時刻ｔの周りを平均化することによって算出される。タウに関する普遍的で当然の選択というものは存在せず、これはむしろ応用に関する仕様に依存する。有限のリンク容量及びクロストラヒックのパケットサイズが原因で、タウを任意に小さく選択することはできない。しかしながら、近代のデータネットワークについては、利用可能な帯域及びクロストラヒック負荷は、秒未満の領域の小ささでタウを使用して定義することができる。
【００１５】
本発明のいくつかの実施形態において、測定のためのサンプリングに使用されるアクティブプロービングは、タイムスタンプ付きのプローブパケットのペアを送信側から受信側へ送信するという良く知られた慣行に基礎を置いている。例えば、ネットワーク経路は一連のホップとしてモデル化可能であり、各ホップは入力ＦＩＦＯキュー及び送信リンクを持つ。各送信リンクｊは定数の容量Ｃｊと、時間的に変化するクロストラヒックとを持つ。シーケンス中のｉ番目のパケットが時刻τｉにあるホップに到達し、時刻τ＊ｉに次のホップに到達するというパケットシーケンス（ひと続きのパケット）を考える。関心を持つべきものはパケットペアの到達時間間隔である。各パケットペアがパケットシーケンスにおいて（ｉ−１）番目のパケットとｉ番目のパケットを含むように定義される場合、上述のホップでの所与のパケットペアの到達時間間隔は、
ｔｉ＝τｉ−τｉ−１  及び  ｔ＊ｉ＝τ＊ｉ−τ＊ｉ−１
である。
【００１６】
無次元量であるパケット間変形量(strain)はεとして示され、
2009516984.tif 000009
によって定義される。
【００１７】
測定を行うために選択されたプローブパケットの送信レートがｕであり、ホップを出るプローブパケットトラヒックの速度がｒであり、プローブパケットのサイズがｂである場合、
2009516984.tif 000010
である。
【００１８】
パケット間変形量εはそれゆえ、プローブトラヒック速度ｕと利用可能な帯域Ｂとの間の関係の指標を提供するように見ることができる。ｕがＢより小さい場合、ε＝０となり、輻輳は存在しない。しかしながら、ｕがＢに達すると、輻輳が存在し、輻輳（或いは、より厳密には変形量）は過負荷であるｕ−Ｂに比例して増大する。これは、上述した文書"A new end-to-end probing and analysis method for estimating bandwidth bottlenecks", by B. Melander et al.における流体モデルを使用して示されてきた。パケット間変形量に関する上述の振る舞いは、以下の方程式１において示される。
2009516984.tif 000011
【００１９】
方程式１のモデルにおいて、αは１／Ｃに等しい状態変数であり、βは（Ｓ／Ｃ）−１に等しい状態変数であり、ｖは測定ノイズである。利用可能な帯域は、
2009516984.tif 000012
として状態変数に関連する。それゆえ、状態変数α及びβが推定可能であれば、利用可能な帯域の推定値は容易に取得可能である。
【００２０】
ここでフィルタベースのアプローチというアイデアに戻ると、システム状態は、システム状態に依存するいくつかの量に関する繰り返しの測定結果と、システム状態がある測定機会から次の測定機会にどのように進化するかに関する所与のモデルと、測定された量がシステム状態にどのように依存するかに関する所与のモデルと、から推定される。これらの依存関係は共に、ランダムノイズの項目を含み、即ち、前者がプロセスノイズを、後者が測定ノイズを、それぞれ含む。システムの方程式はそこで、
2009516984.tif 000013
であり、ここで、ｘはシステム状態であり、ｚは測定結果であり、ｗはプロセスノイズであり、ｖは測定ノイズである。関数ｆ及びｈはシステムの進化モデル及び測定モデルをそれぞれ表す。下付き文字は「離散時間」を表す。
【００２１】
関数ｆ及びｈがリニアであり、プロセスノイズ及び測定ノイズが共にガウシアンであって無相関である場合、最適なフィルタ即ちカルマンフィルタが存在する。実験によれば、例えこれらの条件が厳密には満足されなくても、カルマンフィルタがしばしば極めて良好に機能するということが示されてきた。即ち、ノイズ分布は厳密にガウシアンである必要はない。関数ｆ及びｈに関するリニアからのある偏りも、ノイズの項目によって調節可能である。カルマンフィルタに関する他の重要な利点は、システムの次元が極めて大きいのではない限り、計算量が軽量でありＣＰＵ及びメモリに関して最低限の要求条件で済むということである。このリニアの場合において、システムは行列（マトリクス）を用いて以下のように表現可能である。
2009516984.tif 000014
【００２２】
前回の推定値と新しい測定結果とから新しい推定値の算出を可能にするカルマンフィルタの方程式は、
2009516984.tif 000015
であり、ここで、
2009516984.tif 000016
2009516984.tif 000017
である。
【００２３】
カルマンフィルタリングは、各繰り返しにおいて２つの演算フェーズが存在するプロセスとして理解することができる。第１に、「予測」フェーズが存在し、ここでは、システムのモデルに従って前回の推定値が１つの離散時間ステップ（方程式５）で進化する(evolve)。次に、「訂正」フェーズが存在し、ここでは、新しい測定結果が考慮される（方程式４）。状態推定値に関する更新された誤差共分散行列Ｐｋも算出される。
【００２４】
方程式６及び５に見られるように、カルマンゲインＫｋは、Ｑで増加してＲで減少する。これらのカルマンフィルタ入力Ｑ及びＲは、それぞれプロセスノイズｗ及び測定ノイズｖの共分散である。これらの量は以下のように直感的に理解可能である。システムのモデルにおいてノイズの変動が大きい（Ｑが高い）ということは、システムのモデルに従う予測があまり正確ではなさそうであるということを意味し、新しい測定結果により大きい重み付けを行うべきである。測定ノイズにおいて変動が大きい（Ｒが高い）ということは、新しい測定結果があまり正確ではなさそうであるということを意味し、予測により大きい重み付けを行うべきである。なお、測定された量ｚ＝εはスカラーであり、Ｒもスカラーである（或いは、１×１の行列である）。
【００２５】
本発明の典型的な実施形態は、新しい測定それぞれについてネットワーク経路上の利用可能な帯域の最新の推定値を生成するために、カルマンフィルタを使用する。各測定は、タイムスタンプ付きのパケットペアのシーケンスを送信することと、平均のパケット間変形量を算出することとを含む。いくつかの実施形態において、パケットペアのシーケンスは、連なるように合体させられてもよい。カルマンフィルタ方程式のためのＲ入力を生成するために、パケット間変形量の変動も算出される。いくつかの実施形態において、プロービング速度ｕは、例えば一様分布などの確率分布に従って、各測定についてランダムに選択される。いくつかの実施形態において、例えば間隔として１秒が確率１で選択される一点分布(one-point distribution)のような確率分布から、新しい測定それぞれについてランダムに選択される時間間隔の後に測定が繰り返される。
【００２６】
なお、カルマンフィルタの手法は極めて「寛容(forgiving)」であり、例え理想的な状態が僅かに崩れている場合であっても、しばしば良い結果が生成される。それゆえ、区分的に線形なシステム曲線から幾分逸れた特性をこのシステムが表す場合であっても、結果である利用可能な帯域の推定値が自動的に無効になるということはない。もちろん、このモデルにおける全ての変数は動的であるため、即ち時間と共に変化し得るため、それらは（この説明において時々省略される(suppressed)）下付き文字に依存する。
【００２７】
方程式１のモデルは線形ではないが、区分的に線形である。これの一例が図３にグラフを使って示されている。カルマンフィルタは通常このような場合には適用可能でないが、この問題は本発明の典型的な実施形態に従って回避され、効果的な収束を得ることができる。使用される区分的に線形なモデルが近似に過ぎない場合であっても、ノイズの項目が「モデリング失敗(mismodeling)」に起因するいくらかの誤差を調節することができるので、依然としてカルマンフィルタは良好な推定値を生成することができる。方程式１のモデルによれば、システムの状態が方程式１の傾いた直線部分の２つのパラメータを含むベクトルによって表現される場合に、カルマンフィルタの適用が可能になる。
2009516984.tif 000018
【００２８】
カルマンフィルタの適用可能性に関する線形性基準を充足するために、本発明のいくつかの実施形態は、Ｂに関してｕを追跡し、方程式１の傾いた線部分上に留まろうと試みる（図３も参照）。利用可能な帯域Ｂの真の値は未知であるため、本発明の典型的な実施形態は、最も間近の推定値
2009516984.tif 000019
、或いは
2009516984.tif 000020
近傍の何らかの適切な閾値を使用する。ｕが閾値よりも小さい場合、測定結果は無視されて状態ベクトルの推定値更新されない。離散時刻ｋにおける変形量(strain)の測定結果εｋは、
εｋ＝Ｈｘｋ＋ｖｋ
と記述することができる。ここで、Ｈ＝［ｕ  １］である。また、システム状態の進化は、
ｘｋ＝ｘｋ−１＋ｗｋ−１
と記述することができる。
【００２９】
それゆえ、カルマンフィルタの形式論(formalism)は、Ａ＝Ｉ及びｚ＝εを用いて、方程式７の状態ベクトルに対して適用できる。ここで、Ｉは恒等式(Identity)行列である。
【００３０】
方程式７の状態ベクトルｘは二次元であるため、プロセスノイズｗの共分散Ｑは２×２の行列である。コントロールされている既知のトラヒックを伴いそれゆえ利用可能な帯域が既知である基準ネットワークを仮定すれば、このＱ行列は、性能調整（パフォーマンスチューニング）のために使用可能である。方程式７の二次元状態ベクトルに適用する場合、カルマン方程式は計算量の点で極めて単純になり、各繰り返しについて僅かの浮動小数点演算が必要なだけである。フィルタがシステム状態変数α及びβを推定する際に、利用可能な帯域Ｂの推定値
2009516984.tif 000021
は推定値
2009516984.tif 000022
及び
2009516984.tif 000023
から容易に
2009516984.tif 000024
として算出される。
【００３１】
本発明に従う典型的な動作を、番号が付けられた以下の段落において説明する。これらの典型的な動作は図１の１１−１８においても示されている。
【００３２】
１．  １１に示すように、受信側は、状態ベクトルの初期推定値
2009516984.tif 000025
、及び
2009516984.tif 000026
に対応する誤差共分散行列の初期推定値Ｐ０を生成する。１２に示すように、
2009516984.tif 000027
から、利用可能な帯域の推定値
2009516984.tif 000028
が算出される。
【００３３】
２．  １３に示すように、送信側は、所望の確率分布に従い、プローブパケット強度ｕでＮ個のプローブパケットペアのシーケンス（或いは、連なり）を送信する。（いくつかの実施形態において、ｕのための確率分布は、過去の経験又は実験に基づいて選択される。）Ｎ個のプローブパケットペアは、パケット間変形量の測定のために使用される。いくつかの実施形態では、Ｎ個のペアのプローブパケットを形成するために使用されるＮ＋１個のプローブパケットのシーケンスを送信する。即ち、１番目のパケットペアの２番目のプローブパケットは、２番目のペアの１番目のプローブパケットとしても使用され、同様に続く。いくつかの実施形態では、プローブパケットはプローブパケットペアの間で共有されないので、２Ｎ個のプローブパケットのシーケンスがＮ個の別々のプローブパケットペアを形成するために使用される。送信側は、プローブパケットトラヒック速度ｕの現在の値を、プローブパケットの中で受信側へ受け渡す。
【００３４】
３．  １４に示すように、受信したプローブパケットのシーケンスについて、受信側はプローブパケットからトラヒック強度ｕを復元する。１５でｕが閾値（例えば、
2009516984.tif 000029
或いは
2009516984.tif 000030
近傍で適切に選択された値）を超える場合、１６に示すように、受信側はプローブパケットのタイムスタンプを使用して、Ｎ個のパケットペアに対応するＮ個のパケット間変形量の値の平均値εを算出する。受信側は共分散Ｒも算出する。１５でｕが閾値以下である場合、プローブパケットのタイムスタンプは無視され、更新は行われず、１８に示すように動作は上の＃２に戻る。
【００３５】
４．  １７に示すように、カルマンフィルタは上の動作３からの平均パケット間変形量の値及び共分散行列（あれば）を使用して、状態ベクトル
2009516984.tif 000031
の推定値及び誤差共分散行列Ｐを更新する。１２に示すように、新しい状態ベクトル推定値から、利用可能な帯域の新しい推定値
2009516984.tif 000032
が算出される。
【００３６】
５．  動作は上の＃２に戻り、１３に示すように、プローブパケットの次のシーケンスが生成される。
【００３７】
図２は、本発明の典型的な実施形態に従う、データ伝送経路を評価する装置を図式的に示す。いくつかの実施形態において、図２の装置は、図１に示す上述した動作を実行することが可能である。いくつかの実施形態において、ノード２１及び２３、及びデータ伝送経路２２は、例えばインターネットやプライベートイントラネットなどのパケット交換データネットワークを構成するか、或いはその一部を形成する。送信側ノード２１は、データ伝送経路２２を介して、プローブパケットペアのシーケンスを受信側ノード２３へ送信する。送信側ノード及び受信側ノードでタイムスタンプを付けるという前述したことは、明示的には示されていない。受信側ノード２３は、プローブパケットからタイムスタンプ情報及びプローブパケット速度ｕを抽出する抽出ユニット２４を含む。変形量算出ユニット２５は、受信したシーケンスにおけるプローブパケットの各ペアに関するパケット間変形量の値を算出し、また、パケット間変形量の値の平均及び分散を算出する。
【００３８】
変形量算出ユニット２５は、カルマンフィルタ２６へのｚ入力として平均パケット間変形量εを提供し、また、カルマンフィルタ２６への入力値としてパケット間変形量分散Ｒを提供する。カルマンフィルタ２６はまた、入力としてＱ行列と状態ベクトル
2009516984.tif 000033
の初期推定値及び誤差共分散行列Ｐ０の初期推定値とを受信する。いくつかの実施形態において、状態ベクトル
2009516984.tif 000034
の初期推定値及び誤差共分散行列Ｐ０の初期推定値は、過去の経験及び実験から導出される。これらの初期推定値の正確さは、カルマンフィルタの動作において重要な要素ではない。
【００３９】
カルマンフィルタ２６は、Ａ行列入力として恒等行列Ｉを受信し、また、行列生成器２７から行列Ｈ（例えば、Ｈ＝［ｕ  １］）を受信する。行列生成器２７は、抽出ユニット２４によってプローブパケットから抽出されたプローブパケット速度ｕに応えて行列Ｈを生成する。入力に応えて、カルマンフィルタ２６は更新された状態ベクトル推定値
2009516984.tif 000035
を生成する。利用可能帯域算出ユニット２８は、更新された状態ベクトル推定値を使用して利用可能な帯域の推定値
2009516984.tif 000036
を更新する。利用可能な帯域の推定値
2009516984.tif 000037
は、出力結果としてノード２３から提供され、また、比較ユニット２９へ提供される。比較ユニット２９は、プローブパケット速度ｕと、
2009516984.tif 000038
に等しいか或いは適切にこれに近い閾値とを比較する。この比較結果に応じて、比較ユニット２９は変形量算出ユニット２５に対して、変形量算出ユニット２５がプローブパケットペアの現在のシーケンスについて演算を行うべきか否かに関する指標２０を提供する。いくつかの実施形態において、指標２０はカルマンフィルタ２６へ提供され、変形量算出ユニット２５の結果に対してフィルタが適用されるべきであるか否かを知らせる。これは破線２０１によって示される。
【００４０】
図２に関する前述の説明から、抽出ユニット２４及び変形量算出ユニット２５は、利用可能な帯域を推定するために使用される推定データ（図２の例におけるε及びＲ）を最終的に生成するデータ生成ユニットのコンポーネントとして見ることができる。また、カルマンフィルタ２６及び利用可能帯域推定器２８は、利用可能な帯域の推定値を生成するために推定データに対してカルマンフィルタを適用する推定ユニットのコンポーネントとして見ることができる。
【００４１】
追跡性能を最適化するために、所望の利用可能な帯域平均化タイムスケールタウでいくつかの実施形態を調節することができる。例えば、タウ＝１０秒の場合、利用可能な帯域の測定は１０秒のタイムスケールに亘って行われる。いくつかの実施形態において、タウ＝１０秒であり、２×２の行列ＱがＱ１１＝１０−５、Ｑ１２＝０、Ｑ２１＝０、Ｑ２２＝１０−３の値を持つ。タイムスケールがより短い実施形態においては、Ｑ１１、Ｑ１２、及びＱ２１が同一のまま維持されながら、Ｑ２２の値が増加し得る。
【００４２】
いくつかの実施形態では、数値計算におけるスケーリングを使用することによって、関連する量が無次元になる。上述したように、第１にεが無次元であり、それゆえ、β、ｖ、及びＲも無次元である。他の全ての量を無次元にするために、プローブトラヒック速度ｕが、プローブの送信側ホスト／ノードからの最初のホップの最大容量でスケーリングされる。このことは、ｕ＝１が可能な最大プロービング速度であり、α、ｘ、ｗ、及びＱが無次元であるということを意味する。
【００４３】
いくつかの実施形態において、図２の２５乃至２９におけるコンポーネントは、受信側ノード２３の外部に分離して提供されるが、受信側ノード２３からタイムスタンプ情報及びプローブパケット速度ｕを受信する抽出ユニット２４に結合される。この種の分割は、図２において破線２００によって示される。この分割例において、コンポーネント２５乃至２９の全ては、受信側ノード２３の外部に分離して、例えばネットワークの１以上の他のノード内に提供される。
【００４４】
本発明は、システムの各新しいサンプリングについて、即ちプローブパケットペアの各新しい連なりについて、利用可能な帯域の更新された推定値を生成することができる。連なりは任意の頻度で送信可能（即ち、サンプリング測定のためのタイムスケールは任意に縮小可能）なので、利用可能な帯域はリアルタイムで追跡可能である。
【００４５】
上述したフィルタリング演算を実行するためのデータ処理とメモリとの要求条件は、比較的容易に満足することができる。例えば、いくつかの実施形態において、図２の受信側ノード２３はマイクロプロセッサプラットフォームである。カルマンフィルタの方程式を使用して利用可能な帯域の推定値を更新することは、僅かな浮動小数点演算（いくつかの実施形態においては１００よりも１０に近い）を実行することに帰着する。更新された状態ベクトル推定値を算出するためには前回の状態ベクトル推定値及び新しい測定結果が必要なだけなので、過去の(historical)データを保存する必要がない。
【００４６】
多様な実施形態において、本発明はハードウェアにも、ソフトウェアにも、或いはソフトウェアとハードウェアとの組み合わせにも実装可能であるということは、当業者にとって明白であろう。
【００４７】
以上、本発明の典型的な実施形態を詳細に説明してきたが、これは本発明の範囲を限定するものではない。本発明は、多様な実施形態において実施可能である。
【図面の簡単な説明】
【００４８】
【図１】本発明に従って実行可能な典型的な動作を示す図である。
【図２】本発明の典型的な実施形態に従う、データ伝送経路を評価する装置を図式的に示す図である。
【図３】本発明の典型的な実施形態によって利用される区分的に線形なモデルをグラフで示す図である。
【図１】
2009516984.tif 000039
【図２】
2009516984.tif 000040
【図３】
2009516984.tif 000041
【手続補正書】
【提出日】平成20年2月1日(2008.2.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する方法であって、
前記データ伝送経路のリアルタイム動作中に前記データ伝送経路を通過するプローブパケットを提供するステップと、
前記プローブパケットによる前記データ伝送経路の通過に応えて、且つ前記データ伝送経路の前記リアルタイム動作中に、前記状態を推定するために使用する推定データを提供するステップと、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成するステップであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するステップを含むステップと、
を備え、
前記フィルタ動作は、新しいフィルタ状態情報を生成するために前記推定データと現在のフィルタ状態情報とを組み合わせるために使用する組み合わせパラメータを必要とし、
前記適用するステップは、前記フィルタ動作において使用する前記必要とされる組み合わせパラメータの全てを提供するステップを含む
ことを特徴とする方法。
【請求項２】
前記状態は、前記データ伝送経路において利用可能な帯域であり、
前記適用するステップは、カルマンフィルタを使用するステップを含む
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記組み合わせパラメータのうちの１つは、前記プローブパケットに関連するタイミングパラメータであることを特徴とする請求項１に記載の方法。
【請求項４】
送信速度で前記データ伝送経路中に前記プローブパケットのシーケンスを送信するステップを含み、
前記タイミングパラメータは前記伝送速度である
ことを特徴とする請求項３に記載の方法。
【請求項５】
前記プローブパケットのうちの１つの中に前記送信速度を示す指標を提供するステップを含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記プローブパケットのうちの１つの中に前記タイミングパラメータを提供するステップを含むことを特徴とする請求項３に記載の方法。
【請求項７】
前記プローブパケットのうちの１つの中に前記組み合わせパラメータのうちの１つを提供するステップを含むことを特徴とする請求項１に記載の方法。
【請求項８】
データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する装置であって、
前記データ伝送経路のリアルタイム動作中に前記データ伝送経路を通過してきたプローブパケットを受信するデータ生成ユニットであって、前記プローブパケットによる前記データ伝送経路の通過に応えて、前記データ伝送経路の前記リアルタイム動作中に、前記状態を推定するために使用する推定データを生成するデータ生成ユニットと、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成する、前記データ生成ユニットに結合された推定ユニットであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するフィルタを含む推定ユニットと、
を備え、
前記フィルタ動作は、新しいフィルタ状態情報を生成するために前記推定データと現在のフィルタ状態情報とを組み合わせるために使用する組み合わせパラメータを必要とし、
当該装置は、前記フィルタ動作において使用する前記必要とされる組み合わせパラメータの全てを前記推定ユニットに提供する、前記推定ユニットに結合された設備を備える
ことを特徴とする装置。
【請求項９】
前記推定ユニットと、前記データ生成ユニットの一部とは、前記データ生成ユニットの残りの部分から物理的に離れて配置されることを特徴とする請求項８に記載の装置。
【請求項１０】
前記フィルタはカルマンフィルタを含み、
前記状態は前記データ伝送経路中において利用可能な帯域である
ことを特徴とする請求項８に記載の装置。
【請求項１１】
前記組み合わせパラメータのうちの１つは、前記プローブパケットに関連するタイミングパラメータであることを特徴とする請求項８に記載の装置。
【請求項１２】
前記タイミングパラメータは、前記データ伝送経路中を前記プローブパケットが送信された送信速度であることを特徴とする請求項１１に記載の装置。
【請求項１３】
前記設備は、前記プローブパケットのうちの１つから前記送信速度を示す指標を抽出するために、前記データ生成ユニットに結合されることを特徴とする請求項１２に記載の装置。
【請求項１４】
前記設備は、前記プローブパケットのうちの１つから前記タイミングパラメータを抽出するために、前記データ生成ユニットに結合されることを特徴とする請求項１１に記載の装置。
【請求項１５】
前記設備は、前記プローブパケットのうちの１つから前記組み合わせパラメータのうちの１つを抽出するために、前記データ生成ユニットに結合されることを特徴とする請求項８に記載の装置。
【請求項１６】
データネットワークに結合され、前記データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する装置であって、
前記データ伝送経路のリアルタイム動作中に前記データ伝送経路を通過するプローブパケットを提供するように構成された、前記データ通信ノードのうちの１つと、
前記プローブパケットによる前記データ伝送経路の通過に応えて、前記データ伝送経路の前記リアルタイム動作中に、前記状態を推定するために使用する推定データを生成するデータ生成ユニットを含む、前記データ通信ノードのうちの他の１つと、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成する、前記データ生成ユニットに結合された推定ユニットであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するフィルタを含む推定ユニットと、
を備え、
前記フィルタ動作は、新しいフィルタ状態情報を生成するために前記推定データと現在のフィルタ状態情報とを組み合わせるために使用する組み合わせパラメータを必要とし、
当該装置は、前記フィルタ動作において使用する前記必要とされる組み合わせパラメータの全てを前記推定ユニットに提供する、前記推定ユニットに結合された設備を備える
ことを特徴とする装置。
【請求項１７】
前記データネットワークは、インターネット及びプライベートイントラネットのうちの１つを含むことを特徴とする請求項１６に記載の装置。
【請求項１８】
前記フィルタはカルマンフィルタを含み、
前記状態は前記データ伝送経路中において利用可能な帯域である
ことを特徴とする請求項１６に記載の装置。
【請求項１９】
前記推定ユニットは、前記他のデータ通信ノードから物理的に離れて配置されることを特徴とする請求項１６に記載の装置。
【請求項２０】
データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する装置であって、
前記データ伝送経路のリアルタイム動作中に推定データを受信する入力部と、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成する、前記入力部に結合された推定ユニットであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するフィルタを含む推定ユニットと、
を備え、
前記推定データは、前記データ伝送経路の前記リアルタイム動作中のプローブパケットによる前記データ伝送経路の通過に応えて、前記データ伝送経路の前記リアルタイム動作中に生成され、
前記フィルタ動作は、新しいフィルタ状態情報を生成するために前記推定データと現在のフィルタ状態情報とを組み合わせるために使用する組み合わせパラメータを必要とし、
当該装置は、前記フィルタ動作において使用する前記必要とされる組み合わせパラメータの全てを前記推定ユニットに提供する、前記推定ユニットに結合された設備を備える
ことを特徴とする装置。
【請求項２１】
データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する方法であって、
前記データ伝送経路のリアルタイム動作中に前記データ伝送経路を通過するプローブパケットを提供するステップと、
前記プローブパケットによる前記データ伝送経路の通過に応えて、且つ前記データ伝送経路の前記リアルタイム動作中に、前記状態を推定するために使用する推定データを提供するステップと、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成するステップであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するステップを含むステップと、
ランダムに選択した複数の時点でプローブパケットを提供する前記ステップを繰り返すステップと、
を備えることを特徴とする方法。
【請求項２２】
データネットワークに結合され、前記データネットワークのデータ通信ノード間でデータを伝送するデータ伝送経路における状態を評価する装置であって、
前記データ伝送経路のリアルタイム動作中に前記データ伝送経路を通過するプローブパケットを提供するように構成された、前記データ通信ノードのうちの１つと、
前記プローブパケットによる前記データ伝送経路の通過に応えて、前記データ伝送経路の前記リアルタイム動作中に、前記状態を推定するために使用する推定データを生成するデータ生成ユニットを含む、前記データ通信ノードのうちの他の１つと、
前記データ伝送経路の前記リアルタイム動作中に前記状態の推定値を生成する、前記データ生成ユニットに結合された推定ユニットであって、前記データ伝送経路の前記リアルタイム動作中に前記推定データに対してフィルタ動作を適用するフィルタを含む推定ユニットと、
を備え、
前記１つのデータ通信ノードは、ランダムに選択した複数の時点でプローブパケットを提供することを繰り返すように構成される
ことを特徴とする装置。
【国際調査報告】
2009516984.tif 000042
2009516984.tif 000043
2009516984.tif 000044