パケット化されたネットワークにおける損失率についての推定方法
一方法が提供され、その方法に従って、データが、ネットワーク内の単一ポイントにおけるダウンストリーム・パケット損失について収集される。その収集されたデータから、パケット損失率が、収集ポイントの下流の少なくとも２つのサブネットワークで推定される。それぞれのサブネットワークは、１つまたは複数のリンクだけ異なっている可能性がある。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの性能を監視するための方法に関し、より詳細には、パケット損失率（ｐａｃｋｅｔ ｌｏｓｓ ｒａｔｅｓ）の決定に関する。
【背景技術】
【０００２】
データ・ネットワークの性能は、パケットの損失の影響を受けやすい。ネットワークの性能を最適化することができるようにするために、オペレータは、ネットワークの様々なリンクのパケット損失についての情報を有する必要がある。例えば、パケット損失についての１つの主要な原因は、バッファ・オーバーフロー（ｂｕｆｆｅｒ ｏｖｅｒｆｌｏｗ）である。ネットワークのノードにおいて、バッファ・オーバーフローに起因する損失率を識別すること、および定量化することにより、ネットワーク・オペレータは、ネットワークのオーバーロードされたリンク、またはオーバーロードされたノードにおけるトラフィック・ロード（ｔｒａｆｉｃ ｌｏａｄ）を解放するポリシーを適用することができる可能性がある。
【０００３】
パケット損失をもたらすオーバーロードの危険性は、３Ｇおよび４Ｇのワイヤレス・ネットワークにおいて特に深刻なものになってきている。１つの理由は、そのようなネットワークにおいては、データ・アプリケーションと、音声アプリケーションと、ビデオおよび他のアプリケーションとの間にネットワーク・リソースについての競合が存在し、それらのアプリケーションのおのおのは、異なる帯域幅要件と、異なる配信モードとを有することである。この競合は、エア・インターフェース（ａｉｒ ｉｎｔｅｒｆａｃｅ）のコンテンツ配信のために使用可能な限られた帯域幅により、また一般的にワイヤレス通信を可能にするために必要とされる大量の信号伝達オーバーヘッドにより、悪化させられる。
【０００４】
結果として、高度ワイヤレス・ネットワークにおいては、パケット損失を監視すべき特に大きな必要性が存在する。特定の利点は、例えば、Ｗ−ＣＤＭＡモバイル電気通信ネットワークなどのＧＰＲＳがサポートされるネットワークのＧＧＳＮと、ＧＧＳＮが関連づけられる基地局のおのおのとの間の大部分のリンク、またはすべてのリンクを監視することにより獲得されることになる。しかしながら、従来の方法によりこれを行うことは、監視されるべきリンクのおのおのので展開されるべき監視デバイスを必要とすることになる。高度ワイヤレス・ネットワークは、とりわけ、数百個の、あるいは数千個さえもの、そのようなリンクを有する可能性があるので、監視デバイスのそのような幅の広い展開は、通常、実現可能ではない。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
したがって、ネットワーク上の限られた数のロケーションから展開することができ、依然として多数の個々のリンクの損失率についての情報を得ることができる、パケット損失を監視する方法についての必要性が、依然として存在している。
【課題を解決するための手段】
【０００６】
本発明者等は、そのような一方法を見出している。本発明者等の方法は、ネットワーク内の単一ポイントにおいてダウンストリーム・パケット損失についてのデータを収集するステップと、その収集されたデータから、収集ポイントの少なくとも２つのサブネットワーク・ダウンストリームのパケット損失率を推定するステップとを含み、そこでそれらのサブネットワークは、少なくとも１つのリンクだけ異なっている。
【０００７】
特定の実施形態においては、データ収集は、専用ハードウェア監視デバイスによって実行される。いくつかの実施形態においては、そのようなデバイスは、ＧＰＲＳコア・ネットワーク（ＧＰＲＳ ｃｏｒｅ ｎｅｔｗｏｒｋ）のＧＧＳＮ（ＧＰＲＳサポート・ノード）の下の第１のリンクで展開される。
【０００８】
特定の実施形態においては、収集されたデータは、監視ポイントから複数の基地局へと延びており、またいくつかの実施形態においては、それらの基地局によってサポートされる移動局へとさえ延びているコア・ネットワーク、またはその一部分のパケット損失に関する。
【図面の簡単な説明】
【０００９】
【図１】ＧＰＲＳコア・ネットワークを有する典型的なワイヤレス通信ネットワークの一部分についての簡略化された概略図である。
【図２】例示の一実施形態において本発明を実行するためのタップの包含を示すように修正された、図１のネットワークの一部分についての図である。
【図３】ツリー・グラフ（ｔｒｅｅ ｇｒａｐｈ）の一例を示す図である。
【図４】図３と一緒に読まれるべき、例示の一実施形態における本発明を実施する際に有用なプロシージャのフローチャートである。
【図５】図３のツリー・グラフの詳細を示す図である。
【図６】図５と一緒に読まれるべき、例示の一実施形態における本発明を実施する際に有用なプロシージャのフローチャートである。
【図７】図３のツリー・グラフのさらなる図である。
【発明を実施するための形態】
【００１０】
ＧＰＲＳコア・ネットワークを有する典型的なワイヤレス通信ネットワークの一部分が、図１に概略的に示されている。ダウンストリーム方向に進むと、インターネット１０からＧＧＳＮ２０へのリンクがあり、ＧＧＳＮから複数のＳＧＳＮ（ＧＰＲＳサポート・ノードをサーブする（Ｓｅｒｖｉｎｇ））３０へのリンクがあり、各ＳＧＳＮから複数のＲＮＣ（無線ネットワーク・コントローラ）４０へのリンクがあり、また各ＲＮＣから複数の基地局５０へのリンクがあることが分かる。各基地局は、複数の移動局６０と連絡をとることができる。
【００１１】
ＧＧＳＮから少なくとも基地局へと下に向かって、様々なネットワーク要素は、ＧＧＳＮにルートが置かれたツリー・グラフのノードを形成し、各要素からその下の要素までのリンクは、ツリー・グラフの頂点を形成することが、図１から明らかであろう。
【００１２】
本発明者等の方法は、ツリー・グラフによって表され得るパケット化された任意の通信ネットワークに適用することができる。上記で指摘されるように、図１のネットワークなどのワイヤレスＧＰＲＳネットワークは、本発明者等の方法が特に有用となる場合の一例である。しかしながら、本発明者等の方法の適用は、ＧＰＲＳネットワーク、またはワイヤレス・ネットワークだけに限定されるものではない。
【００１３】
本発明者等の方法は、図１のＧＧＳＮや他のノードなどのネットワーク・ノードにおいて実行されるコンピュータ、またはデジタル・プロセッサ上で展開することができ、あるいはその方法は、専用マシン上で展開することができる。方法が展開されるマシンは、例えば、ソフトウェア命令の下で動作する汎用マシン、あるいはハードウェアまたはファームウェアの制御の下で動作する特定用途マシンとすることができる。
【００１４】
いくつかの実施形態においては、メッセージが展開されるマシンは、リンクの中間ポイントにインストールされるタップを通してパケット・トラフィックのコピーを迂回させることにより、パケット損失情報を収集することになる。例えば、図２は、図１のネットワークの一部分を示しており、そこでは、タップ７０が、ＧＧＳＮ２０と、ＳＧＳＮ８０との間のリンクに追加されており、監視デバイス９０が、タップ７０からコピーされ、迂回されたパケットを受信する。迂回されたパケットから情報を集め、また本発明者等の方法の実施をサポートする必要な計算する能力を有することができる監視デバイスは、よく知られており、そしてここで詳細に説明する必要はない。
【００１５】
そのようなロケーションにおいては、一般的に信号伝達情報からネットワーク・トポロジーを取得することができるので、一般に、タップ７０は、ＧＧＳＮに、またはその下における任意のポイントに位置付けることができる。監視デバイスは、そのロケーションの下流のツリー・ネットワークのトポロジーを知って、これから説明する方法によるパケット損失率を推論することができるようになる必要がある。
【００１６】
本発明者等は、次に、図３および４を参照して、本発明者等の方法の例示の実施形態について説明する。図３は、５つのレベルを有するツリー・グラフの一般化された一例を示すものである。図４は、本発明者等が、以下で、アルゴリズム１と呼ぶことになるプロシージャのステップのフローチャートである。
【００１７】
図３に戻って参照すると、ツリー・グラフ中のレベルの数は、任意であり、５つのレベルのグラフは、例証の目的のためだけに選択されていることに注意すべきである。いくつかの実用的な用途においては、本発明者等の方法は、そのツリー・グラフが、５つよりも少ないレベルを有するネットワークに適用されるであろう。例えば、本方法は、図１のＧＧＳＮにルートが置かれるグラフに有用に適用することができる。グラフの複数のリーフ（ｌｅａｖｅｓ）が、複数の移動局であると考えられる場合に、グラフは、５つのレベルを有することになるのに対して、複数のリーフが、複数の基地局であると考えられる場合には、グラフは、４つのレベルだけを有することになる。
【００１８】
この点で、少なくともいくつかの実施においては、グラフの複数のリーフとして複数の移動局を含めることが望ましいことになるが、移動局は、あまりにも多数になり得るので、個々のエア・インターフェース・リンクを考慮することは、計算的に実現可能ではないことに注意すべきである。そのような場合には、各基地局が少なくとも２つの等価ノードをサーブするようなやり方で、複数の移動局をひとまとめにした等価ノードへとグループ分けすることが、有利になる。そのようなアプローチは、個々のエア・リンクの損失率を与えないけれども、それは、多くの場合にエア・リンクの母集団（ｐｏｐｕｌａｔｉｏｎｓ）で平均された損失率についての有用な情報を提供することになる。
【００１９】
図３において、ルート・ノードは、ｎ０とラベルが付けられる。本発明者等は、ノードｎ４やｎ６など、ツリー・グラフのリーフを「エンド・ノード（ｅｎｄ ｎｏｄｅｓ）」と呼ぶ。本発明者等は、ルート・ノードと、エンド・ノードとの間のすべてのノードを「中間ノード（ｉｎｔｅｒｍｅｄｉａｔｅ ｎｏｄｅｓ）」と呼ぶ。中間ノードの例は、ノードｎ２、ｎ３、およびｎ５である。
【００２０】
本発明者等が行ってきている１つの重要な観察は、パケットの相関対の損失に関連したネットワークの１つのリンクにおいて収集される情報は、ネットワークの他のダウンストリーム・リンクの損失率の証拠になり得ることである。この観察を実現するために、本発明者等は、時間間隔δ内に共にルート・ノードから送信された、異なるエンド・ノードに向かう２つのパケットとして「対」を定義している。δの値は、オペレータによって指定することができ、あるいは、それは、適応的に決定することができる。多数のネットワークにおいては、特に、１つのパケットが、バッファ・オーバーフローに起因して脱落される場合に、短時間後に続いているパケットは、同じ運命に出合う可能性が高いので、時間的に十分に近接して送信されるパケットの損失の間には、高い相関が存在することになる。δについての有用な値は、関心のある特定のネットワークの特性に依存することになるけれども、Ｗ−ＣＤＭＡネットワークにおける典型的な値は、５０〜１００ｍｓの範囲内にある可能性がある。
【００２１】
パケット損失率を、すなわち監視ポイントから、リーフ・ノードとしてサーブするネットワーク要素へのエンド・ツー・エンド・パスの適切な時間平均化間隔にわたって失われるパケットの割合を決定することができる現在使用可能な監視デバイスが、存在している。１つのそのようなデバイスは、アルカテル・ルーセント９９００ワイヤレス・ネットワーク・ガーディアン（Ａｌｃａｔｅｌ−Ｌｕｃｅｎｔ ９９００ Ｗｉｒｅｌｅｓｓ Ｎｅｔｗｏｒｋ Ｇｕａｒｄｉａｎ）であり、これは、ニュー・ジャージー州、マレー・ヒル市、マウンティン・アベニュー、６００番地にオフィスを有するアルカテル・ルーセント社（Ａｌｃａｔｅｌ−Ｌｕｃｅｎｔ Ｉｎｃ．）から入手可能である。そのようなデバイスが、例えば、ＧＰＲＳコア・ネットワークのＧＧＳＮに、またはＧＧＳＮの直下に位置付けられるときに、それは、ＧＧＳＮと、そのＧＧＳＮに関連する基地局によって（個々に、あるいは等価ノードにグループ分けされるように）サーブされる移動局との間のエンド・ツー・エンド・パケット損失率を簡単に測定することができる。
【００２２】
したがって、多数のネットワークの中で測定可能である１つの量は、ルート・ノードｎ０からエンド・ノードｎｉへのエンド・ツー・エンド・パケット損失率Ｆｉである。２つの異なるエンド・ノードｎｉ、ｎｊを仮定すると、別の多くの場合に測定可能な量は、ｎｉに向かうことになっているパケットと、ｎｊに向かうことになっているパケットとが、２つのパケットが上記で定義されるような対に属することを仮定すると、共に、失われることになるという確率Ｆｉ，ｊ；δである。
【００２３】
多数のネットワークの中で測定可能である別の量は、エンド・ノードの与えられた対ｎｉ、ｎｊに向かうことになっているルート・ノードから送信されるすべてのパケット対（適切な平均化期間の間にカウントされる）の割合Ｗｉｊである。すなわち、ｉ≠ｊであるすべてのエンド・ノードｎｉ、ｎｊについて、Ｎｉｊが、（ｎｉ、ｎｊ）に向かうことになっているパケット対の平均化期間の間の総カウントを表すものとする。そのときに、一般に、Ｗｉｊ＝Ｎｉｊ／ΣＮｌｍであり、そこで総和（すなわち、インデックスｌ、ｍにわたっての）が、異なるエンド・ノードのすべての対にわたって取られる。下記で説明される方法の実施のために、総和は、異なる外部ノード（ｏｕｔｅｒ ｎｏｄｅｓ）のすべての対にわたってだけ取られ、これらの外部ノードは、下記で定義される。
【００２４】
次に、本発明者等は、ルート・ノードｎ０から選択された中間ノードｎｉへのパケット損失率ｆ０ｉを推定するための、本明細書においてアルゴリズム１と称されるプロシージャについて説明する。したがって、例えば、アルゴリズム１は、図３のルート・ノードからノードｎ２への損失率を、すなわち、パスｌ１とｌ２との連結（ｃｏｎｃａｔｅｎａｔｉｏｎ）であるパスの損失率を推定するために適用される可能性がある。本発明者等は、選択された中間ノードを「内部ノード（ｉｎｎｅｒ ｎｏｄｅ）」と呼ぶ。当業者は、正確なプロセス・ステップは、非常に多くの変動の影響を受け、説明されるように、単に例示的なものにすぎないことを理解するであろう。
【００２５】
中間ノードは、それが内部ノードとして適格であるために満たす必要がある判断基準が存在する。適格であるためには、選択された中間ノードは、選択されたノードにおいて交差する異なるブランチ（ｂｒａｎｃｈｅｓ）を経由して少なくとも２つのエンド・ノードに対するルート・ノードとなる必要がある。例えば、図３のノードｎ２は、ツリー・グラフのブランチ・ポイントである。１つのブランチは、ノードｎ３へと進み、そしてそこから２つのサブブランチ（ｓｕｂ−ｂｒａｎｃｈｅｓ）を有し、サブブランチの一方は、エンド・ノードｎ４で終結する。他のブランチは、ノードｎ５へと進み、次いでエンド・ノードｎ６で終結する。
【００２６】
本発明者等はまた、ここで外部ノードの概念を導入し、これについては、上記で述べている。選択された内部ノードを仮定すると、１対のエンド・ノードは、（１）選択された内部ノードが、選択されたエンド・ノードに対するルートであり、また（２）少なくとも２つの異なるブランチが、選択された内部ノードにおいて交差し、それらのおのおのが、選択されたエンド・ノードのそれぞれ１つで終結する場合に、外部ノードである。図３の例においては、ｎ４とｎ６とは、（選択された内部ノードｎ２に対する）外部ノードとして適格である。
【００２７】
次に図４を参照すると、プロシージャの第１のステップ１１０は、ルート・ノードｎ０から可能性のある各外部ノードｎｐへのエンド・ツー・エンド損失率Ｆｐと、ルート・ノードｎ０から外部ノードの可能性のある各対ｎｐ、ｎｐ’への対−損失率（ｐａｉｒ−ｌｏｓｓ ｒａｔｅ）Ｆｐ，ｐ’；δと、外部ノードのすべての可能性のある対ｎｐ、ｎｐ’についての対割合（ｐａｉｒ ｆｒａｃｔｉｏｎｓ）Ｗｐ，ｐ’とを測定値から取得することである。（この説明の他のどこかで指摘されるように、多数の可能性のある外部ノードが存在する場合に、計算の節約は、複数のエンド・ノードをひとまとめにされた等価ノードへと人為的にグループ分けすることにより達成することができる。
【００２８】
プロシージャの次のステップ１２０は、内部ノードｎｉを選択することである。図３の例においては、ノードｎ２は、内部ノードとして選択される。
【００２９】
次のステップ１３０は、外部ノードとして適格である２つのエンド・ノードｎｊ、ｎｋを選択することである。次のステップ１４０は、ステップ１１０において取得される情報を使用してルート・ノードｎ０から選択された内部ノードｎｉへのパケット損失率ｆ０ｉの推定値を計算することである。計算を行うための式は、以下で提供される。図３の例においては、損失率ｆ０２は、エンド・ツー・エンド損失率Ｆｐと、対割合Ｗｌｍと、Ｆ４，６；δとから推定される。
【００３０】
本発明者等は、次に、選択された中間ノードｎｊからツリー・グラフ中のｎｊの下に存在する選択された中間ノードｎｋへのパスＰｊｋのパケット損失率を推定するための、ここでアルゴリズム２と称されるプロシージャについて説明することになる。選択された中間ノードｎｊとｎｋとが、アルゴリズム２の適用のために適格であるようにするためには、それらのおのおのは、アルゴリズム１に関連して上記で定義されるように、少なくとも１対の外部ノードに対する内部ノードとして適格である必要がある。アルゴリズム２は、図５および６を参照して説明されることになる。図５は、さらなる詳細を有する図３のツリー・グラフを示している。図６は、アルゴリズム２のステップのフローチャートである。当業者は、正確なプロセス・ステップが、非常に多数の変動の影響を受け、また説明されるように単に例示的なものにすぎないことを理解するであろう。
【００３１】
図５の例においては、パケット損失率は、ノードｎ１からノードｎ３へのパスＰ１３で推定されることになる。図５を参照すると、このパスは、リンクｌ２とｌ３との連結として説明することができる。
【００３２】
次に図６を参照すると、プロシージャの第１のステップ２１０は、中間ノードｎｊ、ｎｋを選択することである。図５の例においては、指摘されるように、選択された中間ノードは、ｎ１、ｎ３である。
【００３３】
次のステップ２２０は、アルゴリズム１を使用して損失率ｆ０ｊ、ｆ０ｋを計算することである。図５の例においては、計算された損失率は、ｆ０１、すなわちリンクｌ１の損失率と、ｆ０３、すなわちリンクｌ１と、ｌ２と、ｌ３との連結であるパスの損失率とである。
【００３４】
次のステップ２３０は、ステップ２２０において取得された率から選択された中間ノードの間の損失率ｆｊｋを計算することである。図５の例においては、損失率ｆ１３は、リンクｌ２とｌ３との連結であるパスの損失率である。
【００３５】
図５から、ステップ２３０は、３−レベルのパスｎ０・ツー・ｎ１・ツー・ｎ３（ｎ０−ｔｏ−ｎ１−ｔｏ ｎ３）を１対の２−レベルのパスｎ０・ツー・ｎ１（ｎ０−ｔｏ−ｎ１）と、ｎ０・ツー・ｎ３（ｎ０−ｔｏ−ｎ３）とに分解して、その分解からもたらされる２つのパスの間の差についてのパケット損失率を取得することであると考えることができることは、明らかであろう。
【００３６】
ステップ２３０において使用される式は、ｆｊｋ＝（ｆ０ｋ−ｆ０ｊ）／（１−ｆ０ｊ）である。図５の例においては、その計算は、ｆ１３＝（ｆ０３−ｆ０１）／（１−ｆ０１）となる。この式を適用する際に、ｆｊｋの負の値はゼロへと端数を切り上げられる。
【００３７】
アルゴリズム１と２とを反復して適用することにより、あらゆる適格リンクでパケット損失率を推定することが簡単に達成可能である。リンクは、（ａ）リンクが、エンド・ノードで終結し、または（ｂ）リンクが、適格な内部ノードで終結する場合に、適格である。
【００３８】
例えば、本発明者等は、次に図７を参照して、ルート・ノードｎ０からエンド・ノードｎ４へのパスの各リンクのパケット損失率を推定するためのプロシージャについて説明することになる。
【００３９】
ｎ０からｎ４へのエンド・ツー・エンド損失率は、測定可能である。その結果として、ｆ０４は、Ｆ４と見なされる。
【００４０】
ｎ０から中間ノードｎ３へのエンド・ツー・エンド損失率ｆ０３は、ルート・ノードｎ０からノードｎ４およびｎ７へのエンド・ツー・エンド損失率の測定値と、対−損失確率Ｆ４，７；δの測定値とを使用してアルゴリズム１によって計算される。次いで、アルゴリズム２を使用して、リンクｌ４の損失率ｆ３４を計算する。
【００４１】
次いで、アルゴリズム１を使用して、ルート・ノードｎ０からノードｎ４およびｎ６へのエンド・ツー・エンド損失率の測定値と、対−損失確率Ｆ４，６；δの測定値とを使用してｎ０から中間ノードｎ２への損失率ｆ０２を計算する。次いで、アルゴリズム２を使用して、ｆ０２とｆ０３との決定された値を使用してリンクｌ３の損失率ｆ２３を計算する。
【００４２】
次いで、アルゴリズム１を使用して、ｎ０からｎ４およびさらなるノードｎ８（図の中で識別されていない）へのエンド・ツー・エンド損失率の測定値と、対−損失確率Ｆ４，８；δの測定値とを使用してｎ０からｎ１への損失率Ｆ０１を計算する。次いで、アルゴリズム２を使用して、ｆ０１とｆ０２とからリンクｌ２の損失率ｆ１２を計算する。
【００４３】
ｎ０からｎ１への損失率、すなわちリンクｌ１の損失率は、率ｆ０１に設定され、この率は、アルゴリズム１を使用して計算されている。
【００４４】
数学的詳細
ｎｋを選択された内部ノードであるとし、またｎｉおよびｎｊを対応する外部ノードであるとする。ｆ０ｋをルート・ノードｎ０からノードｎｋへのパケット損失率であるとし、またｆｋｉと、ｆｋｊとをｎｋからｎｉへと、ｎｋからｎｊへとのそれぞれのパケット損失率であるとする。パケット対のうちの２つのパケットが、同じ損失イベントを、すなわち両方が到着することに成功することになるか、または両方が到着するのに失敗することになるかのいずれかを経験することになり、そして異なるリンクの損失イベントが独立しているという仮定の下では、
Ｆｉｊ−ＦｉＦｊ＝ｆ０ｋ（１−ｆ０ｋ）（１−ｆｋｉｆｋｊ）
のように、またそれゆえに
【００４５】
【数１】
のように示すことができ、合計は、外部ノードのすべての可能性のある対に対して取られる。
【００４６】
次に、対の両方のパケットが、
【００４７】
【数２】
によって失われることになる確率の重み付け平均値Ｆｐａｉｒを定義し、式中で合計は、外部ノードのすべての可能性のある対に対して取られる。ｆｋｉは、Ｆｉよりも大きくすることができないので、
【００４８】
【数３】
が成立することになる。
【００４９】
ｆ０ｋは、
【００５０】
【数４】
によって表されるように、下限と、上限とを有するということになる。
【００５１】
上記式を簡略化するための有用な近似によれば、与えられたリーフ対についてのパケット対の発生は、複数のリーフ、それら自体と独立していることが仮定され、すなわち、パケットは、確率ｗｉでブランチｉへと進み、それゆえに、
【００５２】
【数５】
となる。
【００５３】
上記仮定の下では、
【００５４】
【数６】
となる。それゆえに、対割合Ｗｉｊではなくて個々のパケット割合ｗｉを追跡して、上限と、下限との有用な近似を得ることで十分な可能性がある。
【００５５】
次に、リーフに対する平均エンド・ツー・エンド損失率ＦＬを
【００５６】
【数７】
によって定義し、合計は、可能性のある外部ノードであるすべてのリーフ、すなわち、エンド・ノードにわたって取られる。それゆえに、先行する近似を使用して
【００５７】
【数８】
となる。多数のリーフが存在しているが、パケットの到着が、それらのどれもが支配的でないリーフの間で十分に一様である場合に、合計
【００５８】
【数９】
は、小さくなる。合計が、無視できるほど小さいと見なされる場合には、近似、
【００５９】
【数１０】
が、成り立ち、これは、式
【００６０】
【数１１】
に応じて、近似的な下限と上限とを与える。
【００６１】
上記で指摘されるように、計算の簡略化は、ブランチを複数のひとまとめにされた疑似ブランチへとグループ分けすることにより、多数のリーフ・ブランチが存在する場合に達成することができる。このグループ分けは、ランダムに、有利に実行される。これは、推定効率の実質的な損失なしに、行うことができる。すなわち、グループ分けによって削除される唯一の情報は、そのそれぞれの宛先が、同じグループに含まれるパケット対に関連した情報である。それゆえに、例えば、少なくとも１０個のグループが存在するという条件では、パケット対のわずか１０％についての情報が、失われることになるにすぎない。
【００６２】
上記で説明されるように、アルゴリズム１についての計算に必要とされる様々な合計は、外部ノードのすべての可能性のある対にわたって実行される。アルゴリズム１を適用するための代替的なアプローチにおいては、本発明者等は、以下を行う。
【００６３】
与えられた内部ノードについて、そのブランチのおのおのと、これらのブランチを終結させるエンド・ノードのすべてとを考える。与えられたブランチを人為的なひとまとめにされたエンド・ノードに終結させるすべてのエンド・ノードをグループ化する。ひとまとめにされたエンド・ノードを単一ノードとして取り扱うことにより、与えられた内部ノードからひとまとめにされたエンド・ノードへと延びるツリー・グラフの一部分は、一般的に、各ブランチが、ひとまとめにされたエンド・ノードのうちの１つによって終結させられる多数のブランチを有する、２−レベルのツリーへと変換される。この代替的なアプローチが適用されるときに、合計は、（異なる）ひとまとめにされたエンド・ノードのすべての可能性のある対にわたって取られる。
【００６４】
少なくともいくつかの場合には、上記で説明される代替的なアプローチは、計算の量を低減させることと、精度を高めることとの両方により、有利にすることができる。その理由は、その上で合計を実行すべき有効な外部ノードがより少ないこと、また外部ノードの連結が、あまりにも少ないパケットがいくつかのエンド・ノードに向かうことになっているときにエンド・ツー・エンド損失率の決定において起こる可能性のある不正確さを軽減することである。
【技術分野】
【０００１】
本発明は、ネットワークの性能を監視するための方法に関し、より詳細には、パケット損失率（ｐａｃｋｅｔ ｌｏｓｓ ｒａｔｅｓ）の決定に関する。
【背景技術】
【０００２】
データ・ネットワークの性能は、パケットの損失の影響を受けやすい。ネットワークの性能を最適化することができるようにするために、オペレータは、ネットワークの様々なリンクのパケット損失についての情報を有する必要がある。例えば、パケット損失についての１つの主要な原因は、バッファ・オーバーフロー（ｂｕｆｆｅｒ ｏｖｅｒｆｌｏｗ）である。ネットワークのノードにおいて、バッファ・オーバーフローに起因する損失率を識別すること、および定量化することにより、ネットワーク・オペレータは、ネットワークのオーバーロードされたリンク、またはオーバーロードされたノードにおけるトラフィック・ロード（ｔｒａｆｉｃ ｌｏａｄ）を解放するポリシーを適用することができる可能性がある。
【０００３】
パケット損失をもたらすオーバーロードの危険性は、３Ｇおよび４Ｇのワイヤレス・ネットワークにおいて特に深刻なものになってきている。１つの理由は、そのようなネットワークにおいては、データ・アプリケーションと、音声アプリケーションと、ビデオおよび他のアプリケーションとの間にネットワーク・リソースについての競合が存在し、それらのアプリケーションのおのおのは、異なる帯域幅要件と、異なる配信モードとを有することである。この競合は、エア・インターフェース（ａｉｒ ｉｎｔｅｒｆａｃｅ）のコンテンツ配信のために使用可能な限られた帯域幅により、また一般的にワイヤレス通信を可能にするために必要とされる大量の信号伝達オーバーヘッドにより、悪化させられる。
【０００４】
結果として、高度ワイヤレス・ネットワークにおいては、パケット損失を監視すべき特に大きな必要性が存在する。特定の利点は、例えば、Ｗ−ＣＤＭＡモバイル電気通信ネットワークなどのＧＰＲＳがサポートされるネットワークのＧＧＳＮと、ＧＧＳＮが関連づけられる基地局のおのおのとの間の大部分のリンク、またはすべてのリンクを監視することにより獲得されることになる。しかしながら、従来の方法によりこれを行うことは、監視されるべきリンクのおのおのので展開されるべき監視デバイスを必要とすることになる。高度ワイヤレス・ネットワークは、とりわけ、数百個の、あるいは数千個さえもの、そのようなリンクを有する可能性があるので、監視デバイスのそのような幅の広い展開は、通常、実現可能ではない。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
したがって、ネットワーク上の限られた数のロケーションから展開することができ、依然として多数の個々のリンクの損失率についての情報を得ることができる、パケット損失を監視する方法についての必要性が、依然として存在している。
【課題を解決するための手段】
【０００６】
本発明者等は、そのような一方法を見出している。本発明者等の方法は、ネットワーク内の単一ポイントにおいてダウンストリーム・パケット損失についてのデータを収集するステップと、その収集されたデータから、収集ポイントの少なくとも２つのサブネットワーク・ダウンストリームのパケット損失率を推定するステップとを含み、そこでそれらのサブネットワークは、少なくとも１つのリンクだけ異なっている。
【０００７】
特定の実施形態においては、データ収集は、専用ハードウェア監視デバイスによって実行される。いくつかの実施形態においては、そのようなデバイスは、ＧＰＲＳコア・ネットワーク（ＧＰＲＳ ｃｏｒｅ ｎｅｔｗｏｒｋ）のＧＧＳＮ（ＧＰＲＳサポート・ノード）の下の第１のリンクで展開される。
【０００８】
特定の実施形態においては、収集されたデータは、監視ポイントから複数の基地局へと延びており、またいくつかの実施形態においては、それらの基地局によってサポートされる移動局へとさえ延びているコア・ネットワーク、またはその一部分のパケット損失に関する。
【図面の簡単な説明】
【０００９】
【図１】ＧＰＲＳコア・ネットワークを有する典型的なワイヤレス通信ネットワークの一部分についての簡略化された概略図である。
【図２】例示の一実施形態において本発明を実行するためのタップの包含を示すように修正された、図１のネットワークの一部分についての図である。
【図３】ツリー・グラフ（ｔｒｅｅ ｇｒａｐｈ）の一例を示す図である。
【図４】図３と一緒に読まれるべき、例示の一実施形態における本発明を実施する際に有用なプロシージャのフローチャートである。
【図５】図３のツリー・グラフの詳細を示す図である。
【図６】図５と一緒に読まれるべき、例示の一実施形態における本発明を実施する際に有用なプロシージャのフローチャートである。
【図７】図３のツリー・グラフのさらなる図である。
【発明を実施するための形態】
【００１０】
ＧＰＲＳコア・ネットワークを有する典型的なワイヤレス通信ネットワークの一部分が、図１に概略的に示されている。ダウンストリーム方向に進むと、インターネット１０からＧＧＳＮ２０へのリンクがあり、ＧＧＳＮから複数のＳＧＳＮ（ＧＰＲＳサポート・ノードをサーブする（Ｓｅｒｖｉｎｇ））３０へのリンクがあり、各ＳＧＳＮから複数のＲＮＣ（無線ネットワーク・コントローラ）４０へのリンクがあり、また各ＲＮＣから複数の基地局５０へのリンクがあることが分かる。各基地局は、複数の移動局６０と連絡をとることができる。
【００１１】
ＧＧＳＮから少なくとも基地局へと下に向かって、様々なネットワーク要素は、ＧＧＳＮにルートが置かれたツリー・グラフのノードを形成し、各要素からその下の要素までのリンクは、ツリー・グラフの頂点を形成することが、図１から明らかであろう。
【００１２】
本発明者等の方法は、ツリー・グラフによって表され得るパケット化された任意の通信ネットワークに適用することができる。上記で指摘されるように、図１のネットワークなどのワイヤレスＧＰＲＳネットワークは、本発明者等の方法が特に有用となる場合の一例である。しかしながら、本発明者等の方法の適用は、ＧＰＲＳネットワーク、またはワイヤレス・ネットワークだけに限定されるものではない。
【００１３】
本発明者等の方法は、図１のＧＧＳＮや他のノードなどのネットワーク・ノードにおいて実行されるコンピュータ、またはデジタル・プロセッサ上で展開することができ、あるいはその方法は、専用マシン上で展開することができる。方法が展開されるマシンは、例えば、ソフトウェア命令の下で動作する汎用マシン、あるいはハードウェアまたはファームウェアの制御の下で動作する特定用途マシンとすることができる。
【００１４】
いくつかの実施形態においては、メッセージが展開されるマシンは、リンクの中間ポイントにインストールされるタップを通してパケット・トラフィックのコピーを迂回させることにより、パケット損失情報を収集することになる。例えば、図２は、図１のネットワークの一部分を示しており、そこでは、タップ７０が、ＧＧＳＮ２０と、ＳＧＳＮ８０との間のリンクに追加されており、監視デバイス９０が、タップ７０からコピーされ、迂回されたパケットを受信する。迂回されたパケットから情報を集め、また本発明者等の方法の実施をサポートする必要な計算する能力を有することができる監視デバイスは、よく知られており、そしてここで詳細に説明する必要はない。
【００１５】
そのようなロケーションにおいては、一般的に信号伝達情報からネットワーク・トポロジーを取得することができるので、一般に、タップ７０は、ＧＧＳＮに、またはその下における任意のポイントに位置付けることができる。監視デバイスは、そのロケーションの下流のツリー・ネットワークのトポロジーを知って、これから説明する方法によるパケット損失率を推論することができるようになる必要がある。
【００１６】
本発明者等は、次に、図３および４を参照して、本発明者等の方法の例示の実施形態について説明する。図３は、５つのレベルを有するツリー・グラフの一般化された一例を示すものである。図４は、本発明者等が、以下で、アルゴリズム１と呼ぶことになるプロシージャのステップのフローチャートである。
【００１７】
図３に戻って参照すると、ツリー・グラフ中のレベルの数は、任意であり、５つのレベルのグラフは、例証の目的のためだけに選択されていることに注意すべきである。いくつかの実用的な用途においては、本発明者等の方法は、そのツリー・グラフが、５つよりも少ないレベルを有するネットワークに適用されるであろう。例えば、本方法は、図１のＧＧＳＮにルートが置かれるグラフに有用に適用することができる。グラフの複数のリーフ（ｌｅａｖｅｓ）が、複数の移動局であると考えられる場合に、グラフは、５つのレベルを有することになるのに対して、複数のリーフが、複数の基地局であると考えられる場合には、グラフは、４つのレベルだけを有することになる。
【００１８】
この点で、少なくともいくつかの実施においては、グラフの複数のリーフとして複数の移動局を含めることが望ましいことになるが、移動局は、あまりにも多数になり得るので、個々のエア・インターフェース・リンクを考慮することは、計算的に実現可能ではないことに注意すべきである。そのような場合には、各基地局が少なくとも２つの等価ノードをサーブするようなやり方で、複数の移動局をひとまとめにした等価ノードへとグループ分けすることが、有利になる。そのようなアプローチは、個々のエア・リンクの損失率を与えないけれども、それは、多くの場合にエア・リンクの母集団（ｐｏｐｕｌａｔｉｏｎｓ）で平均された損失率についての有用な情報を提供することになる。
【００１９】
図３において、ルート・ノードは、ｎ０とラベルが付けられる。本発明者等は、ノードｎ４やｎ６など、ツリー・グラフのリーフを「エンド・ノード（ｅｎｄ ｎｏｄｅｓ）」と呼ぶ。本発明者等は、ルート・ノードと、エンド・ノードとの間のすべてのノードを「中間ノード（ｉｎｔｅｒｍｅｄｉａｔｅ ｎｏｄｅｓ）」と呼ぶ。中間ノードの例は、ノードｎ２、ｎ３、およびｎ５である。
【００２０】
本発明者等が行ってきている１つの重要な観察は、パケットの相関対の損失に関連したネットワークの１つのリンクにおいて収集される情報は、ネットワークの他のダウンストリーム・リンクの損失率の証拠になり得ることである。この観察を実現するために、本発明者等は、時間間隔δ内に共にルート・ノードから送信された、異なるエンド・ノードに向かう２つのパケットとして「対」を定義している。δの値は、オペレータによって指定することができ、あるいは、それは、適応的に決定することができる。多数のネットワークにおいては、特に、１つのパケットが、バッファ・オーバーフローに起因して脱落される場合に、短時間後に続いているパケットは、同じ運命に出合う可能性が高いので、時間的に十分に近接して送信されるパケットの損失の間には、高い相関が存在することになる。δについての有用な値は、関心のある特定のネットワークの特性に依存することになるけれども、Ｗ−ＣＤＭＡネットワークにおける典型的な値は、５０〜１００ｍｓの範囲内にある可能性がある。
【００２１】
パケット損失率を、すなわち監視ポイントから、リーフ・ノードとしてサーブするネットワーク要素へのエンド・ツー・エンド・パスの適切な時間平均化間隔にわたって失われるパケットの割合を決定することができる現在使用可能な監視デバイスが、存在している。１つのそのようなデバイスは、アルカテル・ルーセント９９００ワイヤレス・ネットワーク・ガーディアン（Ａｌｃａｔｅｌ−Ｌｕｃｅｎｔ ９９００ Ｗｉｒｅｌｅｓｓ Ｎｅｔｗｏｒｋ Ｇｕａｒｄｉａｎ）であり、これは、ニュー・ジャージー州、マレー・ヒル市、マウンティン・アベニュー、６００番地にオフィスを有するアルカテル・ルーセント社（Ａｌｃａｔｅｌ−Ｌｕｃｅｎｔ Ｉｎｃ．）から入手可能である。そのようなデバイスが、例えば、ＧＰＲＳコア・ネットワークのＧＧＳＮに、またはＧＧＳＮの直下に位置付けられるときに、それは、ＧＧＳＮと、そのＧＧＳＮに関連する基地局によって（個々に、あるいは等価ノードにグループ分けされるように）サーブされる移動局との間のエンド・ツー・エンド・パケット損失率を簡単に測定することができる。
【００２２】
したがって、多数のネットワークの中で測定可能である１つの量は、ルート・ノードｎ０からエンド・ノードｎｉへのエンド・ツー・エンド・パケット損失率Ｆｉである。２つの異なるエンド・ノードｎｉ、ｎｊを仮定すると、別の多くの場合に測定可能な量は、ｎｉに向かうことになっているパケットと、ｎｊに向かうことになっているパケットとが、２つのパケットが上記で定義されるような対に属することを仮定すると、共に、失われることになるという確率Ｆｉ，ｊ；δである。
【００２３】
多数のネットワークの中で測定可能である別の量は、エンド・ノードの与えられた対ｎｉ、ｎｊに向かうことになっているルート・ノードから送信されるすべてのパケット対（適切な平均化期間の間にカウントされる）の割合Ｗｉｊである。すなわち、ｉ≠ｊであるすべてのエンド・ノードｎｉ、ｎｊについて、Ｎｉｊが、（ｎｉ、ｎｊ）に向かうことになっているパケット対の平均化期間の間の総カウントを表すものとする。そのときに、一般に、Ｗｉｊ＝Ｎｉｊ／ΣＮｌｍであり、そこで総和（すなわち、インデックスｌ、ｍにわたっての）が、異なるエンド・ノードのすべての対にわたって取られる。下記で説明される方法の実施のために、総和は、異なる外部ノード（ｏｕｔｅｒ ｎｏｄｅｓ）のすべての対にわたってだけ取られ、これらの外部ノードは、下記で定義される。
【００２４】
次に、本発明者等は、ルート・ノードｎ０から選択された中間ノードｎｉへのパケット損失率ｆ０ｉを推定するための、本明細書においてアルゴリズム１と称されるプロシージャについて説明する。したがって、例えば、アルゴリズム１は、図３のルート・ノードからノードｎ２への損失率を、すなわち、パスｌ１とｌ２との連結（ｃｏｎｃａｔｅｎａｔｉｏｎ）であるパスの損失率を推定するために適用される可能性がある。本発明者等は、選択された中間ノードを「内部ノード（ｉｎｎｅｒ ｎｏｄｅ）」と呼ぶ。当業者は、正確なプロセス・ステップは、非常に多くの変動の影響を受け、説明されるように、単に例示的なものにすぎないことを理解するであろう。
【００２５】
中間ノードは、それが内部ノードとして適格であるために満たす必要がある判断基準が存在する。適格であるためには、選択された中間ノードは、選択されたノードにおいて交差する異なるブランチ（ｂｒａｎｃｈｅｓ）を経由して少なくとも２つのエンド・ノードに対するルート・ノードとなる必要がある。例えば、図３のノードｎ２は、ツリー・グラフのブランチ・ポイントである。１つのブランチは、ノードｎ３へと進み、そしてそこから２つのサブブランチ（ｓｕｂ−ｂｒａｎｃｈｅｓ）を有し、サブブランチの一方は、エンド・ノードｎ４で終結する。他のブランチは、ノードｎ５へと進み、次いでエンド・ノードｎ６で終結する。
【００２６】
本発明者等はまた、ここで外部ノードの概念を導入し、これについては、上記で述べている。選択された内部ノードを仮定すると、１対のエンド・ノードは、（１）選択された内部ノードが、選択されたエンド・ノードに対するルートであり、また（２）少なくとも２つの異なるブランチが、選択された内部ノードにおいて交差し、それらのおのおのが、選択されたエンド・ノードのそれぞれ１つで終結する場合に、外部ノードである。図３の例においては、ｎ４とｎ６とは、（選択された内部ノードｎ２に対する）外部ノードとして適格である。
【００２７】
次に図４を参照すると、プロシージャの第１のステップ１１０は、ルート・ノードｎ０から可能性のある各外部ノードｎｐへのエンド・ツー・エンド損失率Ｆｐと、ルート・ノードｎ０から外部ノードの可能性のある各対ｎｐ、ｎｐ’への対−損失率（ｐａｉｒ−ｌｏｓｓ ｒａｔｅ）Ｆｐ，ｐ’；δと、外部ノードのすべての可能性のある対ｎｐ、ｎｐ’についての対割合（ｐａｉｒ ｆｒａｃｔｉｏｎｓ）Ｗｐ，ｐ’とを測定値から取得することである。（この説明の他のどこかで指摘されるように、多数の可能性のある外部ノードが存在する場合に、計算の節約は、複数のエンド・ノードをひとまとめにされた等価ノードへと人為的にグループ分けすることにより達成することができる。
【００２８】
プロシージャの次のステップ１２０は、内部ノードｎｉを選択することである。図３の例においては、ノードｎ２は、内部ノードとして選択される。
【００２９】
次のステップ１３０は、外部ノードとして適格である２つのエンド・ノードｎｊ、ｎｋを選択することである。次のステップ１４０は、ステップ１１０において取得される情報を使用してルート・ノードｎ０から選択された内部ノードｎｉへのパケット損失率ｆ０ｉの推定値を計算することである。計算を行うための式は、以下で提供される。図３の例においては、損失率ｆ０２は、エンド・ツー・エンド損失率Ｆｐと、対割合Ｗｌｍと、Ｆ４，６；δとから推定される。
【００３０】
本発明者等は、次に、選択された中間ノードｎｊからツリー・グラフ中のｎｊの下に存在する選択された中間ノードｎｋへのパスＰｊｋのパケット損失率を推定するための、ここでアルゴリズム２と称されるプロシージャについて説明することになる。選択された中間ノードｎｊとｎｋとが、アルゴリズム２の適用のために適格であるようにするためには、それらのおのおのは、アルゴリズム１に関連して上記で定義されるように、少なくとも１対の外部ノードに対する内部ノードとして適格である必要がある。アルゴリズム２は、図５および６を参照して説明されることになる。図５は、さらなる詳細を有する図３のツリー・グラフを示している。図６は、アルゴリズム２のステップのフローチャートである。当業者は、正確なプロセス・ステップが、非常に多数の変動の影響を受け、また説明されるように単に例示的なものにすぎないことを理解するであろう。
【００３１】
図５の例においては、パケット損失率は、ノードｎ１からノードｎ３へのパスＰ１３で推定されることになる。図５を参照すると、このパスは、リンクｌ２とｌ３との連結として説明することができる。
【００３２】
次に図６を参照すると、プロシージャの第１のステップ２１０は、中間ノードｎｊ、ｎｋを選択することである。図５の例においては、指摘されるように、選択された中間ノードは、ｎ１、ｎ３である。
【００３３】
次のステップ２２０は、アルゴリズム１を使用して損失率ｆ０ｊ、ｆ０ｋを計算することである。図５の例においては、計算された損失率は、ｆ０１、すなわちリンクｌ１の損失率と、ｆ０３、すなわちリンクｌ１と、ｌ２と、ｌ３との連結であるパスの損失率とである。
【００３４】
次のステップ２３０は、ステップ２２０において取得された率から選択された中間ノードの間の損失率ｆｊｋを計算することである。図５の例においては、損失率ｆ１３は、リンクｌ２とｌ３との連結であるパスの損失率である。
【００３５】
図５から、ステップ２３０は、３−レベルのパスｎ０・ツー・ｎ１・ツー・ｎ３（ｎ０−ｔｏ−ｎ１−ｔｏ ｎ３）を１対の２−レベルのパスｎ０・ツー・ｎ１（ｎ０−ｔｏ−ｎ１）と、ｎ０・ツー・ｎ３（ｎ０−ｔｏ−ｎ３）とに分解して、その分解からもたらされる２つのパスの間の差についてのパケット損失率を取得することであると考えることができることは、明らかであろう。
【００３６】
ステップ２３０において使用される式は、ｆｊｋ＝（ｆ０ｋ−ｆ０ｊ）／（１−ｆ０ｊ）である。図５の例においては、その計算は、ｆ１３＝（ｆ０３−ｆ０１）／（１−ｆ０１）となる。この式を適用する際に、ｆｊｋの負の値はゼロへと端数を切り上げられる。
【００３７】
アルゴリズム１と２とを反復して適用することにより、あらゆる適格リンクでパケット損失率を推定することが簡単に達成可能である。リンクは、（ａ）リンクが、エンド・ノードで終結し、または（ｂ）リンクが、適格な内部ノードで終結する場合に、適格である。
【００３８】
例えば、本発明者等は、次に図７を参照して、ルート・ノードｎ０からエンド・ノードｎ４へのパスの各リンクのパケット損失率を推定するためのプロシージャについて説明することになる。
【００３９】
ｎ０からｎ４へのエンド・ツー・エンド損失率は、測定可能である。その結果として、ｆ０４は、Ｆ４と見なされる。
【００４０】
ｎ０から中間ノードｎ３へのエンド・ツー・エンド損失率ｆ０３は、ルート・ノードｎ０からノードｎ４およびｎ７へのエンド・ツー・エンド損失率の測定値と、対−損失確率Ｆ４，７；δの測定値とを使用してアルゴリズム１によって計算される。次いで、アルゴリズム２を使用して、リンクｌ４の損失率ｆ３４を計算する。
【００４１】
次いで、アルゴリズム１を使用して、ルート・ノードｎ０からノードｎ４およびｎ６へのエンド・ツー・エンド損失率の測定値と、対−損失確率Ｆ４，６；δの測定値とを使用してｎ０から中間ノードｎ２への損失率ｆ０２を計算する。次いで、アルゴリズム２を使用して、ｆ０２とｆ０３との決定された値を使用してリンクｌ３の損失率ｆ２３を計算する。
【００４２】
次いで、アルゴリズム１を使用して、ｎ０からｎ４およびさらなるノードｎ８（図の中で識別されていない）へのエンド・ツー・エンド損失率の測定値と、対−損失確率Ｆ４，８；δの測定値とを使用してｎ０からｎ１への損失率Ｆ０１を計算する。次いで、アルゴリズム２を使用して、ｆ０１とｆ０２とからリンクｌ２の損失率ｆ１２を計算する。
【００４３】
ｎ０からｎ１への損失率、すなわちリンクｌ１の損失率は、率ｆ０１に設定され、この率は、アルゴリズム１を使用して計算されている。
【００４４】
数学的詳細
ｎｋを選択された内部ノードであるとし、またｎｉおよびｎｊを対応する外部ノードであるとする。ｆ０ｋをルート・ノードｎ０からノードｎｋへのパケット損失率であるとし、またｆｋｉと、ｆｋｊとをｎｋからｎｉへと、ｎｋからｎｊへとのそれぞれのパケット損失率であるとする。パケット対のうちの２つのパケットが、同じ損失イベントを、すなわち両方が到着することに成功することになるか、または両方が到着するのに失敗することになるかのいずれかを経験することになり、そして異なるリンクの損失イベントが独立しているという仮定の下では、
Ｆｉｊ−ＦｉＦｊ＝ｆ０ｋ（１−ｆ０ｋ）（１−ｆｋｉｆｋｊ）
のように、またそれゆえに
【００４５】
【数１】
のように示すことができ、合計は、外部ノードのすべての可能性のある対に対して取られる。
【００４６】
次に、対の両方のパケットが、
【００４７】
【数２】
によって失われることになる確率の重み付け平均値Ｆｐａｉｒを定義し、式中で合計は、外部ノードのすべての可能性のある対に対して取られる。ｆｋｉは、Ｆｉよりも大きくすることができないので、
【００４８】
【数３】
が成立することになる。
【００４９】
ｆ０ｋは、
【００５０】
【数４】
によって表されるように、下限と、上限とを有するということになる。
【００５１】
上記式を簡略化するための有用な近似によれば、与えられたリーフ対についてのパケット対の発生は、複数のリーフ、それら自体と独立していることが仮定され、すなわち、パケットは、確率ｗｉでブランチｉへと進み、それゆえに、
【００５２】
【数５】
となる。
【００５３】
上記仮定の下では、
【００５４】
【数６】
となる。それゆえに、対割合Ｗｉｊではなくて個々のパケット割合ｗｉを追跡して、上限と、下限との有用な近似を得ることで十分な可能性がある。
【００５５】
次に、リーフに対する平均エンド・ツー・エンド損失率ＦＬを
【００５６】
【数７】
によって定義し、合計は、可能性のある外部ノードであるすべてのリーフ、すなわち、エンド・ノードにわたって取られる。それゆえに、先行する近似を使用して
【００５７】
【数８】
となる。多数のリーフが存在しているが、パケットの到着が、それらのどれもが支配的でないリーフの間で十分に一様である場合に、合計
【００５８】
【数９】
は、小さくなる。合計が、無視できるほど小さいと見なされる場合には、近似、
【００５９】
【数１０】
が、成り立ち、これは、式
【００６０】
【数１１】
に応じて、近似的な下限と上限とを与える。
【００６１】
上記で指摘されるように、計算の簡略化は、ブランチを複数のひとまとめにされた疑似ブランチへとグループ分けすることにより、多数のリーフ・ブランチが存在する場合に達成することができる。このグループ分けは、ランダムに、有利に実行される。これは、推定効率の実質的な損失なしに、行うことができる。すなわち、グループ分けによって削除される唯一の情報は、そのそれぞれの宛先が、同じグループに含まれるパケット対に関連した情報である。それゆえに、例えば、少なくとも１０個のグループが存在するという条件では、パケット対のわずか１０％についての情報が、失われることになるにすぎない。
【００６２】
上記で説明されるように、アルゴリズム１についての計算に必要とされる様々な合計は、外部ノードのすべての可能性のある対にわたって実行される。アルゴリズム１を適用するための代替的なアプローチにおいては、本発明者等は、以下を行う。
【００６３】
与えられた内部ノードについて、そのブランチのおのおのと、これらのブランチを終結させるエンド・ノードのすべてとを考える。与えられたブランチを人為的なひとまとめにされたエンド・ノードに終結させるすべてのエンド・ノードをグループ化する。ひとまとめにされたエンド・ノードを単一ノードとして取り扱うことにより、与えられた内部ノードからひとまとめにされたエンド・ノードへと延びるツリー・グラフの一部分は、一般的に、各ブランチが、ひとまとめにされたエンド・ノードのうちの１つによって終結させられる多数のブランチを有する、２−レベルのツリーへと変換される。この代替的なアプローチが適用されるときに、合計は、（異なる）ひとまとめにされたエンド・ノードのすべての可能性のある対にわたって取られる。
【００６４】
少なくともいくつかの場合には、上記で説明される代替的なアプローチは、計算の量を低減させることと、精度を高めることとの両方により、有利にすることができる。その理由は、その上で合計を実行すべき有効な外部ノードがより少ないこと、また外部ノードの連結が、あまりにも少ないパケットがいくつかのエンド・ノードに向かうことになっているときにエンド・ツー・エンド損失率の決定において起こる可能性のある不正確さを軽減することである。
【特許請求の範囲】
【請求項１】
ネットワーク内の単一ポイントにおけるダウンストリーム・パケット損失についてのデータを収集するステップと、
前記収集されたデータから、収集ポイントの下流の少なくとも２つのサブネットワークのパケット損失率を推定するステップと
を含み、前記サブネットワークは、少なくとも１つのリンクだけ異なっている、方法。
【請求項２】
前記データ収集は、専用のハードウェア監視デバイスによって実行される、請求項１に記載の方法。
【請求項３】
前記データ収集は、ＧＰＲＳコア・ネットワークのＧＰＲＳサポート・ノード（ＧＧＳＮ）の下の第１のリンクで展開される専用のハードウェア監視デバイスによって実行される、請求項１に記載の方法。
【請求項４】
前記収集されたデータは、前記収集ポイントから複数の基地局へと延びるＧＰＲＳコア・ネットワークの一部分のパケット損失に関連している、請求項１に記載の方法。
【請求項５】
前記収集されたデータは、前記収集ポイントから複数の移動局へと延びるＧＰＲＳコア・ネットワークの一部分のパケット損失に関連している、請求項１に記載の方法。
【請求項６】
ネットワーク内の単一ポイントにおけるダウンストリーム・パケット損失についてのデータを収集するための入力と、
前記収集されたデータから、前記収集ポイントの下流の少なくとも２つのサブネットワークのパケット損失率の推定値を計算するように構成された回路と
を備え、前記サブネットワークは、少なくとも１つのリンクだけ異なっている、監視デバイス。
【請求項１】
ネットワーク内の単一ポイントにおけるダウンストリーム・パケット損失についてのデータを収集するステップと、
前記収集されたデータから、収集ポイントの下流の少なくとも２つのサブネットワークのパケット損失率を推定するステップと
を含み、前記サブネットワークは、少なくとも１つのリンクだけ異なっている、方法。
【請求項２】
前記データ収集は、専用のハードウェア監視デバイスによって実行される、請求項１に記載の方法。
【請求項３】
前記データ収集は、ＧＰＲＳコア・ネットワークのＧＰＲＳサポート・ノード（ＧＧＳＮ）の下の第１のリンクで展開される専用のハードウェア監視デバイスによって実行される、請求項１に記載の方法。
【請求項４】
前記収集されたデータは、前記収集ポイントから複数の基地局へと延びるＧＰＲＳコア・ネットワークの一部分のパケット損失に関連している、請求項１に記載の方法。
【請求項５】
前記収集されたデータは、前記収集ポイントから複数の移動局へと延びるＧＰＲＳコア・ネットワークの一部分のパケット損失に関連している、請求項１に記載の方法。
【請求項６】
ネットワーク内の単一ポイントにおけるダウンストリーム・パケット損失についてのデータを収集するための入力と、
前記収集されたデータから、前記収集ポイントの下流の少なくとも２つのサブネットワークのパケット損失率の推定値を計算するように構成された回路と
を備え、前記サブネットワークは、少なくとも１つのリンクだけ異なっている、監視デバイス。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公表番号】特表２０１３−５０２１５５（Ｐ２０１３−５０２１５５Ａ）
【公表日】平成２５年１月１７日（２０１３．１．１７）
【国際特許分類】
【出願番号】特願２０１２−５２４７３７（Ｐ２０１２−５２４７３７）
【出願日】平成２２年８月２日（２０１０．８．２）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０４４０９５
【国際公開番号】ＷＯ２０１１／０１９５３４
【国際公開日】平成２３年２月１７日（２０１１．２．１７）
【出願人】（３９１０３０３３２）アルカテル−ルーセント (1,149)
【Ｆターム（参考）】
【公表日】平成２５年１月１７日（２０１３．１．１７）
【国際特許分類】
【出願日】平成２２年８月２日（２０１０．８．２）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０４４０９５
【国際公開番号】ＷＯ２０１１／０１９５３４
【国際公開日】平成２３年２月１７日（２０１１．２．１７）
【出願人】（３９１０３０３３２）アルカテル−ルーセント (1,149)
【Ｆターム（参考）】
[ Back to top ]