(57)【要約】【課題】広域エリアネットワークについて、プローブパケットを送受信することなく、短時間に発生する輻輳を検出し、その輻輳を共通に経験するパスを分類する輻輳パス分類方法、管理装置及びプログラムを提供する。【解決手段】管理装置は、ブロードキャストパケットを受信した計測端末から、少なくとも送信元アドレス、受信端末アドレス及び受信時刻を含む計測情報を受信する。次に、管理装置は、同一のブロードキャストパケットにおける複数の計測情報について、２つの受信端末をセットにして、２つの受信時刻の差分時間を導出する。そして、管理装置は、セット毎に、差分時間の変動に基づいて、輻輳パスを特定する。具体的には、差分変動時間に基づいて、非類似度の低い２つのパスのペアを導出し、ウォード法を適用してデンドログラムを作成し、そのクラスタを分類する。【選択図】図２
2008236479.tif 000002
【特許請求の範囲】
【請求項１】
複数の計測端末間の複数のパスから輻輳パスを分類する管理装置における輻輳パス特定方法であって、
ブロードキャストパケットを受信した前記計測端末から、少なくとも送信元アドレス、受信端末アドレス及び受信時刻を含む計測情報を受信する第１のステップと、
同一のブロードキャストパケットにおける複数の計測情報について、２つの受信端末をセットにして、２つの受信時刻の差分時間を導出する第２のステップと、
前記セット毎に、前記差分時間の変動に基づいて、輻輳パスを特定する第３のステップと
を有することを特徴とする輻輳パス特定方法。
【請求項２】
第２のステップについて、前記セット毎に、前記差分時間に基づく平均差分時間を導出し、
第３のステップについて、
前記セットに基づくパスのペア毎に、前記差分時間と前記平均差分時間との差を表す差分変動時間を導出するステップと、
前記差分変動時間の絶対値を非類似度として算出するステップと、
非類似度の低い２つのパスのペアを導出し、輻輳パスを特定するステップと
を有することを特徴とする請求項１に記載の輻輳パス特定方法。
【請求項３】
第３のステップについて、
前記セットに基づくパスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するステップと、
前記デンドログラムの非類似度に応じて、パスを分類するステップと
を更に有することを特徴とする請求項２に記載の輻輳パス特定方法。
【請求項４】
複数の計測端末間のパスにおけるパケット遅延から輻輳パスを分類する管理装置において、
ブロードキャストパケットを受信した前記計測端末から、少なくとも送信元アドレス、受信端末アドレス及び受信時刻を含む計測情報を受信する計測情報収集手段と、
同一のブロードキャストパケットにおける複数の計測情報について、２つの受信端末をセットにして、２つの受信時刻の差分時間を導出する差分時間導出手段と、
前記セット毎に、前記差分時間の変動に基づいて、輻輳パスを特定する輻輳パス特定手段と
を有することを特徴とする管理装置。
【請求項５】
前記セット毎に、前記差分時間に基づく平均差分時間を導出する平均差分時間導出手段を更に有し、
前記輻輳パス特定手段は、
前記セットに基づくパスのペア毎に、前記差分時間と前記平均差分時間との差を表す差分変動時間を導出する差分変動時間導出手段と、
前記差分変動時間の絶対値を非類似度として算出する非類似度算出手段と、
非類似度の低い２つのパスのペアを導出し、輻輳パスを特定する輻輳パス分類手段と
を有することを特徴とする請求項４に記載の管理装置。
【請求項６】
前記輻輳パス分類手段は、
前記パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するデンドログラム作成手段と、
前記デンドログラムの非類似度に応じて、パスを分類するパス分類手段と
を有することを特徴とする請求項５に記載の管理装置。
【請求項７】
複数の計測端末間のパスにおけるパケット遅延から輻輳パスを分類する管理装置に搭載されたコンピュータを機能させるプログラムにおいて、
ブロードキャストパケットを受信した前記計測端末から、少なくとも送信元アドレス、受信端末アドレス及び受信時刻を含む計測情報を受信する計測情報収集手段と、
同一のブロードキャストパケットにおける複数の計測情報について、２つの受信端末をセットにして、２つの受信時刻の差分時間を導出する差分時間導出手段と、
前記セット毎に、前記差分時間の変動に基づいて、輻輳パスを特定する輻輳パス特定手段と
してコンピュータを機能させることを特徴とする管理装置用のプログラム。
【請求項８】
前記セット毎に、前記差分時間に基づく平均差分時間を導出する平均差分時間導出手段を更に有し、
前記輻輳パス特定手段は、
前記セットに基づくパスのペア毎に、前記差分時間と前記平均差分時間との差を表す差分変動時間を導出する差分変動時間導出手段と、
前記差分変動時間の絶対値を非類似度として算出する非類似度算出手段と、
非類似度の低い２つのパスのペアを導出し、輻輳パスを特定する輻輳パス分類手段と
してコンピュータを機能させることを特徴とする請求項７に記載の管理装置用のプログラム。
【請求項９】
前記輻輳パス分類手段は、
前記パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するデンドログラム作成手段と、
前記デンドログラムの非類似度に応じて、パスを分類するパス分類手段と
してコンピュータを機能させることを特徴とする請求項８に記載の管理装置用のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広域エリアネットワークに発生した輻輳パスを分類する輻輳パス分類方法、管理装置及びプログラムに関する。特に、ＩＰ(Internet Protocol)ネットワークについて、短時間の輻輳を発生したパスを、輻輳の発生していないパスから分類する方法等に関する。
【背景技術】
【０００２】
広域エリアネットワークとして代表的なインターネットは、ベストエフォート型通信であるので、正確な通信品質保証は困難である。これに対し、ＩＳＰ(Internet Service Provider)事業者が、品質劣化区間を特定し、経路変更又は回線増速等の運用制御によって品質劣化を回避している。しかし、インターネットは、多数の独立ネットワークによって構成されているために、ネットワーク内部の状態を直接的に計測できない場合がある。特に、多数の端末及びサーバが既に接続した状態にあるので、ネットワーク機器の特性（例えばパケット損失率、パケット遅延等）を直接的に計測することは困難である。
【０００３】
代表的な技術としては、マルチキャストパケットを用いて、木構造パスに沿ったエンドツーエンドでパケット損失を観測し、内部リンクのパケット損失率を推定する技術がある（例えば非特許文献１参照）。また、複数個の連続したユニキャストパケットを用いたアクティブ計測によって、内部リンクのパスの特性を推定する技術もある（例えば非特許文献２参照）。
【０００４】
更に、近年では、複数パス上でランダムなタイミングで送出されるプローブパケットを用いてパケット損失率やパケット遅延変動を周期的にアクティブ計測し、ネットワークの品質劣化区間を推定する技術もある（例えば非特許文献３及び４参照）。この技術は、計測結果と所定閾値とを比較し、パスの品質を判定する。そして、品質劣化と判定されたパスの組み合わせと、それらパスの経路情報とによって、ネットワークにおける品質劣化区間を特定する。
【０００５】
【非特許文献１】R. Caceres, N. Duffield, J. Horowitz, andD. Towsley, "Multicast-based inference of network-internal losscharacteristics." IEEE Trans. Info. Theory, 45(7):2462--2480, 1999.
【非特許文献２】M. Tsuru, T. Takine, and Y. Oie,"Inferring link characteristics from end-to-end path measurements."Proc. IEEE ICC, pages 1534--1538, Helsinki, June 2001.
【非特許文献３】A. Tachibana, S. Ano, T. Hasegawa, M.Tsuru, and Y. Oie, "Locating Congested Segments over the Internet Based onMultiple End-to-End Path Measurements,".IEICE Transactions onCommunications Internet Technology VI, April 2006.
【非特許文献４】立花篤男、阿野茂浩、長谷川亨、鶴正人及び尾家祐二、「パケット遅延のクラスタリングに基づく品質劣化区間推定法」、信学会ＣＱ研究会、Jan. 2007.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
非特許文献１及び２によれば、パス毎に、パスの特定の平均値や最大値を算出した集計値によって、劣化状態を統計的に推定する。１つの区間において品質劣化が発生した場合、その区間を経由する複数のパスに、同時に品質劣化が発生する。従って、大量のプローブパケットを計測する必要がある。このような方法は、ネットワークに多大な負荷を与えることとなるだけでなく、複雑な計算のために長い推定時間を要する。
【０００７】
また、非特許文献３及び４によれば、複数のパス上のプローブパケットを周期的に集計するため、リアルタイム性は確保されるけれども、異なるプローブパケット同士を比較するため、計測情報同士の間の相関が弱い。パス毎に、パスの特性の集計値から品質劣化区間を特定しようとするために、瞬間的な品質劣化（例えば２０ｍｓ程度の輻輳）に対しては正確に推定できない。光ファイバによって基幹網が構築されているような場合は、短時間の輻輳であってもネットワーク全体に与える影響が大きい。従って、短時間の輻輳を時々発生するような経路を回避する必要がある。
【０００８】
いずれの技術によっても、アクティブ計測のためのプローブパケットを送受信するために、広域エリアネットワークに負荷をかけることとなる。
【０００９】
従って、本発明は、広域エリアネットワークについて、プローブパケットを送受信することなく、短時間に発生する輻輳を検出し、その輻輳を共通に経験するパスを分類する輻輳パス分類方法、管理装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明によれば、複数の計測端末間の複数のパスから輻輳パスを分類する管理装置における輻輳パス特定方法であって、
ブロードキャストパケットを受信した計測端末から、少なくとも送信元アドレス、受信端末アドレス及び受信時刻を含む計測情報を受信する第１のステップと、
同一のブロードキャストパケットにおける複数の計測情報について、２つの受信端末をセットにして、２つの受信時刻の差分時間を導出する第２のステップと、
セット毎に、差分時間の変動に基づいて、輻輳パスを特定する第３のステップと
を有することを特徴とする。
【００１１】
本発明の輻輳パス特定方法における他の実施形態によれば、
第２のステップについて、セット毎に、差分時間に基づく平均差分時間を導出し、
第３のステップについて、
セットに基づくパスのペア毎に、差分時間と平均差分時間との差を表す差分変動時間を導出するステップと、
差分変動時間の絶対値を非類似度として算出するステップと、
非類似度の低い２つのパスのペアを導出し、輻輳パスを特定するステップと
を有することも好ましい。
【００１２】
本発明の輻輳パス特定方法における他の実施形態によれば、第３のステップについて、
セットに基づくパスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するステップと、
デンドログラムの非類似度に応じて、パスを分類するステップと
を更に有することも好ましい。
【００１３】
本発明によれば、複数の計測端末間のパスにおけるパケット遅延から輻輳パスを分類する管理装置において、
ブロードキャストパケットを受信した計測端末から、少なくとも送信元アドレス、受信端末アドレス及び受信時刻を含む計測情報を受信する計測情報収集手段と、
同一のブロードキャストパケットにおける複数の計測情報について、２つの受信端末をセットにして、２つの受信時刻の差分時間を導出する差分時間導出手段と、
セット毎に、差分時間の変動に基づいて、輻輳パスを特定する輻輳パス特定手段と
を有することを特徴とする。
【００１４】
本発明の管理装置における他の実施形態によれば、
セット毎に、差分時間に基づく平均差分時間を導出する平均差分時間導出手段を更に有し、
輻輳パス特定手段は、
セットに基づくパスのペア毎に、差分時間と平均差分時間との差を表す差分変動時間を導出する差分変動時間導出手段と、
差分変動時間の絶対値を非類似度として算出する非類似度算出手段と、
非類似度の低い２つのパスのペアを導出し、輻輳パスを特定する輻輳パス分類手段と
を有することも好ましい。
【００１５】
本発明の管理装置における他の実施形態によれば、輻輳パス分類手段は、
パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するデンドログラム作成手段と、
デンドログラムの非類似度に応じて、パスを分類するパス分類手段と
を有することも好ましい。
【００１６】
本発明によれば、複数の計測端末間のパスにおけるパケット遅延から輻輳パスを分類する管理装置に搭載されたコンピュータを機能させるプログラムにおいて、
ブロードキャストパケットを受信した計測端末から、少なくとも送信元アドレス、受信端末アドレス及び受信時刻を含む計測情報を受信する計測情報収集手段と、
同一のブロードキャストパケットにおける複数の計測情報について、２つの受信端末をセットにして、２つの受信時刻の差分時間を導出する差分時間導出手段と、
セット毎に、差分時間の変動に基づいて、輻輳パスを特定する輻輳パス特定手段と
してコンピュータを機能させることを特徴とする。
【００１７】
本発明の管理装置用のプログラムにおける他の実施形態によれば、
セット毎に、差分時間に基づく平均差分時間を導出する平均差分時間導出手段を更に有し、
輻輳パス特定手段は、
セットに基づくパスのペア毎に、差分時間と平均差分時間との差を表す差分変動時間を導出する差分変動時間導出手段と、
差分変動時間の絶対値を非類似度として算出する非類似度算出手段と、
非類似度の低い２つのパスのペアを導出し、輻輳パスを特定する輻輳パス分類手段と
してコンピュータを機能させることも好ましい。
【００１８】
本発明の管理装置用のプログラムにおける他の実施形態によれば、輻輳パス分類手段は、
パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するデンドログラム作成手段と、
デンドログラムの非類似度に応じて、パスを分類するパス分類手段と
してコンピュータを機能させることも好ましい。
【発明の効果】
【００１９】
本発明の輻輳パス分類方法、管理装置及びプログラムによれば、広域エリアネットワークについて、プローブパケットを送受信することなく、短時間に発生する輻輳を検出し、その輻輳を共通に経験するパスを分類することができる。
【発明を実施するための最良の形態】
【００２０】
以下では、図面を用いて、本発明を実施するための最良の形態について詳細に説明する。
【００２１】
図１は、ネットワーク構成図である。
【００２２】
図１によれば、４つの計測端末Ａ〜Ｄが、区間１から５を有するネットワークを介して接続されている。また、ネットワークには管理装置２も接続されており、全ての計測端末Ａ〜Ｄは、計測情報を管理装置２へ送信する。ここで、「パス」とは、計測端末間毎の経路をいう。また、「区間」とは、分岐・合流点によって分割されるパスの一部をいう。
【００２３】
図１には、ネットワークトポロジの構成表も表されている。例えば、パス１は、計測端末Ａと計測端末Ｂとの間の経路を表し、区間１、区間２及び区間３を介して接続されている。
【００２４】
本発明によれば、各計測端末は、ブロードキャストパケットを送信する機能と、ブロードキャストパケットを受信する機能とを有する。ブロードキャストパケットは、ある計測端末から送信されると、ネットワークドメイン内の全ての端末によって受信される。ブロードキャストパケットに、宛先アドレスとしてブロードキャストアドレスが含められる。本発明は、広域エリアネットワークを流れるブロードキャストパケットを、多地点の計測端末でパッシブ計測された計測情報を用いて、品質劣化箇所を推定する。
【００２５】
図１によれば、計測端末Ａから送信されたブロードキャストパケットは、計測端末Ｂ、Ｃ及びＤによって受信され、計測端末Ｂから送信されたブロードキャストパケットは、計測端末Ａ、Ｃ及びＤによって受信される。
【００２６】
図２は、本発明におけるブロードキャストパケットの受信を表す説明図である。
【００２７】
図２によれば、計測端末Ｂに注目している。計測端末Ｂは、計測端末Ａとの間でパス１（区間１−区間２−区間３）を介して接続され、計測端末Ｃとの間でパス４（区間５−区間２−区間３）を介して接続され、計測端末Ｄとの間でパス５（区間４−区間３）を介して接続されている。
【００２８】
図２に表されたネットワークトポロジからも明らかなとおり、例えば区間２に輻輳が発生した場合、その輻輳は、パス１及び４を経由した複数のパケットによって経験される。また、区間３に発生した輻輳は、パス１、４及び５を経由した複数のパケットによって経験される。
【００２９】
（Ｓ２０１）計測端末Ｂは、計測端末Ａからブロードキャストパケットを受信したとする。計測端末Ｂは、パケット毎に、受信時刻をスタンプする。ブロードキャストパケットには、「送信元アドレス」及び「トータル長」が含まれている。「送信元アドレス」及び「トータル長」と受信時刻によって、ブロードキャストパケットの同一性が判断される。即ち、受信時刻の差が閾値（例えば１秒）以内であり、送信元アドレスとトータル長が一致するものを同一のブロードキャストパケットと判定する。尚、同一のブロードキャストパケットは、計測端末Ｃ及びＤによっても受信される。
【００３０】
（Ｓ２０２）計測端末Ｂは、受信したブロードキャストパケットに対する計測情報を生成する。計測情報には、ブロードキャストパケットを特定するための「送信元アドレス」「トータル長」と共に、「受信端末アドレス」及び「受信時刻」を含む。「受信端末アドレス」は、計測端末Ｂを特定する。「受信時刻」は、計測端末Ｂがブロードキャストパケットを受信した時刻である。そして、計測端末Ｂは、その計測情報を、管理装置２へ送信する。
【００３１】
ここで、計測端末１は、周期的（例えば１０秒毎）に、計測情報を管理装置２へ送信するように構成されていてもよい。
【００３２】
尚、全ての計測端末Ａ〜Ｄで、時刻は同期しているものとする。また、ブロードキャストパケットは、ランダムな送信間隔で送信されるものであってもよい。
【００３３】
更に、他の計測端末が、ブロードキャストパケットを送信する。図２によれば、計測端末Ｄが、ブロードキャストパケットを送信している。このブロードキャストパケットに対しても、他の計測端末は、前述したＳ２０１及びＳ２０２の処理を実行する。
【００３４】
（Ｓ２０３）管理装置２は、前述のシーケンスによって、全ての計測端末Ａ〜Ｄから、計測情報を受信する。図２によれば、「送信元アドレス」（計測端末Ａ）及び「トータル長」（１００）について、「受信端末アドレス」（計測端末Ｂ、Ｃ及びＤ）毎に「受信時刻」が特定される。
【００３５】
ここで、２つの受信端末をセットにして、２つの受信時刻の差分時間を導出する。セットとは、２つのパスのペアを意味する。
【００３６】
図２によれば、計測端末Ａから送信されたブロードキャストパケットに対して、計測端末Ｂの受信時刻と、計測端末Ｃの受信時刻との間の差分時間を導出する（セットＢ−Ｃ）。また、計測端末Ｂの受信時刻と、計測端末Ｄの受信時刻との間の差分時間を導出する（セットＢ−Ｄ）。更に、計測端末Ｃの受信時刻と、計測端末Ｄの受信時刻との間の差分時間を導出する（セットＣ−Ｄ）。
【００３７】
同様に、計測端末Ｄから送信されたブロードキャストパケットに対して、計測端末Ａの受信時刻と、計測端末Ｂの受信時刻との間の差分時間を導出する（セットＡ−Ｂ）。また、計測端末Ａの受信時刻と、計測端末Ｃの受信時刻との間の差分時間を導出する（セットＡ−Ｃ）。更に、計測端末Ｂの受信時刻と、計測端末Ｃの受信時刻との間の差分時間を導出する（セットＢ−Ｃ）。
【００３８】
尚、差分時間が、閾時間以上（例えば２０ｍｓ以上）となるセットは、除外することも好ましい。差分時間が長い場合、パスの間の相関が無く、短時間に発生する輻輳を特定できないからである。閾時間を、２０ｍｓとした場合、１つの区間で２０ｍｓ以上の遅延による輻輳が発生した場合、その区間を介した異なるパスに対して共通の輻輳として検出される。
【００３９】
本発明によれば、短時間の同一の輻輳を経験したブロードキャストパケットを抽出することによって、輻輳を発生した品質劣化区間を特定する。
【００４０】
図３は、本発明におけるフローチャートである。
【００４１】
（Ｓ２０１）ある計測端末が、ブロードキャストパケットを送信する。図２のＳ２０１と同じ処理をする。
（Ｓ２０２）ブロードキャストパケットを受信した計測端末は、計測情報を管理装置２へ送信する。図２のＳ２０２と同じ処理をする。
（Ｓ２０３）管理装置２は、複数の計測端末から複数の計測情報を、常時、受信する。図２のＳ２０３と同じ処理をする。管理装置２は、これら計測情報は、一定以上収集して記憶する。
【００４２】
（Ｓ２０４）同一のブロードキャストパケットにおける複数の計測情報について、２つの受信端末をセットにして、２つの受信時刻の差分時間を導出する。ここで、パケット損失によってブロードキャストパケットを受信しなかった端末との間の差分時間は、ＮＡ(Not Available)とする。
【００４３】
（Ｓ２０５）セット毎に、平均差分時間を導出する。平均差分時間は、差分変動時間の基準値となる。平均差分時間は、十分な期間（例えば数時間から１日程度）に、前述したＳ２０１〜Ｓ２０４を繰り返し、各パス間の平均差分時間を導出する。その平均差分時間を、各パス間の通常状態における差分時間と見なすことができる。
【００４４】
（Ｓ２０６）受信した計測情報によって導出された差分時間と、平均差分時間との差から、差分変動時間を導出する。輻輳が発生した場合、パケット遅延によって差分変動時間が大きくなる。その差分変動時間が所定閾値以上となった場合、品質劣化が発生したと判定し、同様に差分変動時間が所定閾値以上となったパス群を抽出する。
【００４５】
（Ｓ２０７）セットに基づくパスのペア毎に、その差分変動時間の絶対値を導出し、それらを非類似度として算出する。
【００４６】
（Ｓ２０８）パスのペア毎に、非類似度ｄの低いペアから順に、クラスタ分析（数値分類法）におけるウォード法を適用してデンドログラム（樹形図）を作成する。
【００４７】
クラスタ分析とは、異なる性質のもの同士が混ざり合っている集団の中から、互いに似たものを集めてクラスタを作り、対象を分類しようとする方法をいう。最初に、各パスを要素とするクラスタに分類する。Ｎ本のパスをクラスタリングする場合、Ｎ個のクラスタに分類する。そして、非類似度ｄが最小となる２つのパスを抽出し、それらを１つのクラスタに結合する。この結果、クラスタの総数は１個減少し、Ｎ−１個となる。
【００４８】
次に、結合したクラスタと、残りのクラスタとの非類似度を再計算する。再計算の方法は様々なアルゴリズムが提案されているが、代表的なウォード法を適用する。
【００４９】
ウォード法とは、階層型クラスタ分析方法の１つであって、互いに似たもの同士を分類する際に、クラスタ内の全ての個体に対してのクラスタ重心からの偏差平方和を求め、そのクラスタ内平方和の増分ができるだけ小さくなるように併合するものである。
【００５０】
互いに似ているかどうかの判定基準としては、ユークリッド平方距離を用いることが多い。互いが似ているパスのペアの併合を、１つのクラスタに結合されるまで繰り返し、デンドログラムを作成する。デンドログラムは、各クラスタ間の非類似度の関係を表す。
【００５１】
（Ｓ２０９）デンドログラムの非類似度に応じて、パスを分類する。パスの分類は、例えば、非類似度の最大値の所定の高さ（例えば１／２）で切断する。これにより、複数のクラスタに分類される。ある区間で輻輳が発生した場合、デンドログラムによれば、２つのクラスタに分類される。
【００５２】
その後、２つのクラスタの一方のパスの群（通常、小さい方のクラスタ群）について、各パスの経路情報を比較し、共有する区間を特定する。その区間を品質劣化区間として特定する。
【００５３】
図４は、デンドログラムである。
【００５４】
図４のデンドログラムは、Ｓ２０８によって作成される。縦軸は、クラスタ間の非類似度を表し、３０パスについて非類似度の低いパスから順に分類されている。
【００５５】
次に、Ｓ２０９によってパスが分類される。非類似度の所定の高さ（Ａ）で分類した場合、図４によれば、クラスタＡ（パス２１〜２５）と、クラスタＢ（Ａ以外の２５パス）との２つに分類されている。ここで、クラスタＡに含まれる５パスは、図４において差分変動時間が同期して増加したものである。一方、クラスタＢに含まれる２５パスでは、差分変動時間が増加していない。
【００５６】
このように、共通の輻輳を経験する５パスと、それ以外の２５パスとを、高い精度で分類することができる。即ち、クラスタＡ（劣化クラスタ）に属するパス群は、品質劣化区間を共通に経験したパスとして抽出される。
【００５７】
図５は、本発明における計測端末及び管理装置の機能構成図である。
【００５８】
図５によれば、計測端末１は、ブロードキャストパケット送信部１０と、パケット受信部１１と、計測パケット抽出部１２と、パケット遅延検出部１３と、パケット遅延送信部１４とを有する。これら機能部は、計測端末１に搭載されたコンピュータによって実行されるプログラムによっても実現できる。
【００５９】
ブロードキャストパケット送信部１０は、「送信元アドレス」及び「トータル長」を含むブロードキャストパケットを送信する。前述したＳ２０１の動作をする。
【００６０】
パケット受信部１１は、複数の相手方計測端末から、「送信元アドレス」及び「トータル長」を含むブロードキャストパケットを受信する。パケット受信部１１は、パケット毎に、受信時刻をスタンプする。ブロードキャストパケットは、計測情報生成部１２へ出力される。
【００６１】
計測情報生成部１２は、ブロードキャストパケット毎に、計測情報を生成する。計測情報は、ブロードキャストパケットを特定するための「送信元アドレス」「トータル長」と共に、「受信端末アドレス」及び「受信時刻」を含む。生成された計測情報は、計測情報送信部１３へ出力される。
【００６２】
計測情報送信部１３は、計測情報を管理装置２へ送信する。
【００６３】
尚、パケット受信部１１、計測情報生成部１２及び計測情報送信部１３は、前述したＳ２０２の動作をする。
【００６４】
図５によれば、管理装置２は、計測情報収集部２１と、差分時間導出部２２と、平均差分時間導出部２３と、輻輳パス特定部２４とを有する。また、輻輳パス特定部２４は、差分変動時間導出部２４１と、非類似度算出部２４２と、輻輳パス分類部２４３とを有する。更に、輻輳パス分類部２４３は、デンドログラム作成部２４３１と、パス分類部２４３２とを有する。これら機能部は、管理装置２に搭載されたコンピュータによって実行されるプログラムによっても実現できる。
【００６５】
計測情報収集部２１は、複数の計測端末から、ブロードキャストパケットに基づく計測情報を受信する。計測情報は、少なくとも「送信元アドレス」「受信端末アドレス」「受信時刻」を含む。前述したＳ２０３の動作をする。収集された計測情報は、差分時間導出部２２へ出力される。
【００６６】
差分時間導出部２２は、同一のブロードキャストパケットにおける複数の計測情報について、２つの受信端末をセットにして、２つの受信時刻の差分時間を導出する。前述したＳ２０４の動作をする。セット毎の差分時間は、平均差分時間導出部２３と、輻輳パス特定部２４の差分変動時間導出部２４１へ出力される。
【００６７】
平均差分時間導出部２３は、セット毎に、差分時間に基づく平均差分時間を導出する。前述したＳ２０５の動作をする。平均差分時間は、差分変動時間導出部２４１へ出力される。
【００６８】
輻輳パス特定部２４は、セット毎に、差分時間の変動に基づいて、輻輳パスを特定する。
【００６９】
輻輳パス特定部２４に含まれる差分変動時間導出部２４１は、セットに基づくパスのペア毎に、差分時間と平均差分時間との差を表す差分変動時間を導出する。前述したＳ２０６の動作をする。差分変動時間は、非類似度算出部２４２へ出力される。
【００７０】
輻輳パス特定部２４に含まれる非類似度算出部２４２は、差分変動時間の絶対値を非類似度として算出する。前述したＳ２０７の動作をする。セット毎の２つのパスの非類似度は、輻輳パス分類部２４３のデンドログラム作成部２４３１へ出力される。
【００７１】
輻輳パス特定部２４に含まれる輻輳パス分類部２４３は、非類似度の低い２つのパスのペアを導出し、輻輳パスを特定する。
【００７２】
輻輳パス分類部２４３に含まれるデンドログラム作成部２４３１は、パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成する。前述したＳ２０８の動作をする。作成されたデンドログラムは、輻輳パス分類部２４３へ出力される。
【００７３】
輻輳パス分類部２４３に含まれるパス分類部２４３２は、デンドログラムの非類似度に応じて、パスを分類する。前述したＳ２０９の動作をする。輻輳パス分類部２４３は、輻輳を発生したパスを列挙する。その複数のパスについて、共通する区間を導出することができる。結局、その区間が、品質劣化区間として推定される。
【００７４】
本発明の輻輳パス分類方法、管理装置及びプログラムによれば、広域エリアネットワークについて、プローブパケットを送受信することなく、短時間に発生する輻輳を検出し、その輻輳を共通に経験するパスを分類することができる。従って、"traceroute"では検出できないレイヤ２ノードでの劣化に対しても、パスを分類することができる。本発明は、パス毎に、差分変動時間の類似性に基づいて各パスの品質を分類することができる。また、輻輳を発生したパスの推定にクラスタリングを用いるために、計算処理量が少なく、計測情報の収集の周期を短く設定でき、輻輳を発生したパスを迅速に分類することができる。
【００７５】
前述した本発明における種々の実施形態によれば、当業者は、本発明の技術思想及び見地の範囲における種々の変更、修正及び省略を容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【図面の簡単な説明】
【００７６】
【図１】ネットワーク構成図である。
【図２】本発明におけるパケットペアの受信を表す説明図である。
【図３】本発明におけるフローチャートである。
【図４】デンドログラムである。
【図５】本発明における計測端末及び管理装置の機能構成図である。
【符号の説明】
【００７７】
１  計測端末
１０  ブロードキャストパケット送信部
１１  パケット受信部
１２  計測情報生成部
１３  計測情報送信部
２  管理装置
２１  計測情報収集部
２２  差分時間導出部
２３  平均差分時間導出部
２４  輻輳パス特定部
２４１  差分変動時間導出部
２４２  非類似度算出部
２４３  輻輳パス分類部
２４３１  デンドログラム作成部
２４３２  パス分類部
【図１】
2008236479.tif 000003
【図２】
2008236479.tif 000004
【図３】
2008236479.tif 000005
【図４】
2008236479.tif 000006
【図５】
2008236479.tif 000007