【手続補正書】
【提出日】平成21年6月1日(2009.6.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の計測端末間のパスにおけるパケット遅延から輻輳パスを分類する管理装置における輻輳パス特定方法であって、
前記計測端末によって受信されたパケットについて、該計測端末から、送信元端末、宛先端末、送信時刻及び受信時刻の計測情報を受信する第１のステップと、
前記送信元端末を共通にする計測情報を、送信時刻順に並べて、隣接する送信時刻の時間間隔が閾時間以内となる２つパケットを抽出する第２のステップと、
前記宛先端末を共通にする計測情報を、受信時刻順に並べて、隣接する受信時刻の時間間隔が閾時間以内となるパケットペアを抽出する第３のステップと、
抽出された複数のパケットについて送信時刻と受信時刻との差から算出されるパケット遅延に基づいて、輻輳パスを特定する第４のステップと
を有することを特徴とする輻輳パス特定方法。
【請求項２】
前記第４のステップについて、
パス毎に、パケット遅延の最小値を導出するステップと、
２つのパスのペア毎に、パケット遅延と前記最小値との間の変化分の二乗和を導出し、それらの平均値を非類似度として算出するステップと
を有し、非類似度の低い２つのパスのペアを導出することを特徴とする請求項１に記載の輻輳パス特定方法。
【請求項３】
前記第４のステップについて、
前記パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するステップと、
前記デンドログラムの非類似度に応じて、パスを分類するステップと
を更に有することを特徴とする請求項２に記載の輻輳パス特定方法。
【請求項４】
複数の計測端末間のパスにおけるパケット遅延から輻輳パスを分類する管理装置において、
前記計測端末によって受信されたパケットについて、該計測端末から、送信元端末、宛先端末、送信時刻及び受信時刻の計測情報を受信する計測情報収集手段と、
前記送信元端末を共通にする計測情報を、送信時刻順に並べて、隣接する送信時刻の時間間隔が閾時間以内となる２つパケットを抽出し、更に、前記宛先端末を共通にする計測情報を、受信時刻順に並べて、隣接する受信時刻の時間間隔が閾時間以内となるパケットペアを抽出する計測パケット抽出手段と、
抽出された複数のパケットについて送信時刻と受信時刻との差からパケット遅延を算出するパケット遅延検出手段と
を有することを特徴とする管理装置。
【請求項５】
パス毎に、パケット遅延の最小値を導出するパケット遅延最小値導出手段と、
２つのパスのペア毎に、パケット遅延と前記最小値との間の変化分の二乗和を導出し、それらの平均値を非類似度として算出する非類似度算出手段と、
非類似度の低い２つのパスのペアを導出する輻輳パス分類手段と
更に有することを特徴とする請求項４に記載の管理装置。
【請求項６】
前記輻輳パス分類手段は、
前記パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するデンドログラム作成手段と、
前記デンドログラムの非類似度に応じて、パスを分類するパス分類手段と
を有することを特徴とする請求項５に記載の管理装置。
【請求項７】
複数の計測端末間のパスにおけるパケット遅延から輻輳パスを分類する管理装置に搭載されたコンピュータを機能させるプログラムにおいて、
前記計測端末によって受信されたパケットについて、該計測端末から、送信元端末、宛先端末、送信時刻及び受信時刻の計測情報を受信する計測情報収集手段と、
前記送信元端末を共通にする計測情報を、送信時刻順に並べて、隣接する送信時刻の時間間隔が閾時間以内となる２つパケットを抽出し、更に、前記宛先端末を共通にする計測情報を、受信時刻順に並べて、隣接する受信時刻の時間間隔が閾時間以内となるパケットペアを抽出する計測パケット抽出手段と、
抽出された複数のパケットについて送信時刻と受信時刻との差からパケット遅延を算出するパケット遅延検出手段と
してコンピュータを機能させることを特徴とする管理装置用のプログラム。
【請求項８】
パス毎に、パケット遅延の最小値を導出するパケット遅延最小値導出手段と、
２つのパスのペア毎に、パケット遅延と前記最小値との間の変化分の二乗和を導出し、それらの平均値を非類似度として算出する非類似度算出手段と、
非類似度の低い２つのパスのペアを導出する輻輳パス分類手段と
して更にコンピュータを機能させることを特徴とする請求項７に記載の管理装置用のプログラム。
【請求項９】
前記輻輳パス分類手段は、
前記パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するデンドログラム作成手段と、
前記デンドログラムの非類似度に応じて、パスを分類するパス分類手段と
して更にコンピュータを機能させることを特徴とする請求項８に記載の管理装置用のプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【発明の名称】パケット遅延から輻輳パスを分類する輻輳パス分類方法、管理装置及びプログラム
【技術分野】
【０００１】
本発明は、パケット遅延から輻輳パスを分類する輻輳パス分類方法、管理装置及びプログラムに関する。特に、ＩＰ(Internet Protocol)ネットワークについて、パケット遅延に基づく短時間の輻輳を特定するために、パスを分類する方法等に関する。
【背景技術】
【０００２】
従来、複数のパスの特性（例えばパケット損失率、パケット遅延等、以下「パス状態」という)を計測端末間でアクティブ計測して、ネットワークの品質劣化区間を特定する技術がある（例えば非特許文献１参照）。区間とは、分岐・合流点によって分割されるパスの一部をいう。この技術は、計測結果と所定閾値とを比較し、パスの品質を段階的に判定する（good/bad/medium）。そして、品質劣化と判定されたパスの組み合わせと、それらパスの経路情報とによって、ネットワークにおける品質劣化区間を特定する。
【０００３】
また、複数のテストパケットを、複数のパスへ短い時間間隔で同時に送信し、受信されたパケットの相関によって、共有される区間の品質を推定する技術もある（例えば非特許文献２参照）。
【０００４】
【非特許文献１】A. Tachibana、S. Ano、T. Hasegawa、M. Tsuru、Y. Oie,、「EmpiricalStudy on Locating Congested Segments over the Internet Based on Multiple End-to-EndPath Measurements」、In Proc. E.G.,EE/IPSJ SAINT, 2005
【非特許文献２】「Inferringlink characteristics from end-to-end path measurements」、In Proc. IEEE ICC、Helsinki(2001)、1534-1538
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１のように、集計値（例えば一定周期の平均値や最大値）と所定閾値とを比較する場合、集計値と閾値との差が小さいと、極端に正常／異常とを判定することとなる。従って、閾値によって分類結果が大きく異なる可能性がある。また、非特許文献２によれば、全てのテストパケットについてパケット間の相関を判定するために、非常に高精度な計測及び複雑な計算が必要となる。
【０００６】
従来技術は、パス毎に、パス状態の平均値や最大値を算出した集計値によって劣化状態を判定する。現実には、１つの区間において品質劣化が発生した場合、その区間を経由する複数のパスに同時に品質劣化が発生する。それにも関わらず、パス毎に単一の劣化状態と判定し、全体の集計値からパスの相関を検出しようとしている。
【０００７】
また、従来技術によれば、パス毎に、パス状態の集計値から品質劣化区間を特定しようとするために、パケット遅延のような短時間（例えば２０ｍｓ程度）発生する輻輳を特定することはできない。しかしながら、光ファイバによって基幹網が構築されているような場合は、短時間の輻輳であってもネットワーク全体に与える影響が大きい。従って、短時間の輻輳を時々発生するような経路を回避する必要がある。
【０００８】
従って、本発明は、ＩＰネットワークについて、パケット遅延によって短時間に発生する輻輳を検出するために、その輻輳を共通に経験するパスをパケット遅延から分類する輻輳パス分類方法、管理装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明によれば、複数の計測端末間のパスにおけるパケット遅延から輻輳パスを分類する管理装置における輻輳パス特定方法であって、
計測端末によって受信されたパケットについて、該計測端末から、送信元端末、宛先端末、送信時刻及び受信時刻の計測情報を受信する第１のステップと、
送信元端末を共通にする計測情報を、送信時刻順に並べて、隣接する送信時刻の時間間隔が閾時間以内となる２つパケットを抽出する第２のステップと、
宛先端末を共通にする計測情報を、受信時刻順に並べて、隣接する受信時刻の時間間隔が閾時間以内となるパケットペアを抽出する第３のステップと、
抽出された複数のパケットについて送信時刻と受信時刻との差から算出されるパケット遅延に基づいて、輻輳パスを特定する第４のステップと
を有することを特徴とする。
【００１０】
本発明の輻輳パス特定方法における他の実施形態によれば、第４のステップについて、
パス毎に、パケット遅延の最小値を導出するステップと、
２つのパスのペア毎に、パケット遅延と最小値との間の変化分の二乗和を導出し、それらの平均値を非類似度として算出するステップと
を有し、非類似度の低い２つのパスのペアを導出することも好ましい。
【００１１】
本発明の輻輳パス特定方法における他の実施形態によれば、第４のステップについて、
パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するステップと、
デンドログラムの非類似度に応じて、パスを分類するステップと
を更に有することも好ましい。
【００１２】
本発明によれば、複数の計測端末間のパスにおけるパケット遅延から輻輳パスを分類する管理装置において、
計測端末によって受信されたパケットについて、該計測端末から、送信元端末、宛先端末、送信時刻及び受信時刻の計測情報を受信する計測情報収集手段と、
送信元端末を共通にする計測情報を、送信時刻順に並べて、隣接する送信時刻の時間間隔が閾時間以内となる２つパケットを抽出し、更に、宛先端末を共通にする計測情報を、受信時刻順に並べて、隣接する受信時刻の時間間隔が閾時間以内となるパケットペアを抽出する計測パケット抽出手段と、
抽出された複数のパケットについて送信時刻と受信時刻との差からパケット遅延を算出するパケット遅延検出手段と
を有することを特徴とする。
【００１３】
本発明の管理装置における他の実施形態によれば、
パス毎に、パケット遅延の最小値を導出するパケット遅延最小値導出手段と、
２つのパスのペア毎に、パケット遅延と最小値との間の変化分の二乗和を導出し、それらの平均値を非類似度として算出する非類似度算出手段と、
非類似度の低い２つのパスのペアを導出する輻輳パス分類手段と
更に有することも好ましい。
【００１４】
本発明の管理装置における他の実施形態によれば、輻輳パス分類手段は、
パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するデンドログラム作成手段と、
デンドログラムの非類似度に応じて、パスを分類するパス分類手段と
を有することも好ましい。
【００１５】
本発明によれば、複数の計測端末間のパスにおけるパケット遅延から輻輳パスを分類する管理装置に搭載されたコンピュータを機能させるプログラムにおいて、
計測端末によって受信されたパケットについて、該計測端末から、送信元端末、宛先端末、送信時刻及び受信時刻の計測情報を受信する計測情報収集手段と、
送信元端末を共通にする計測情報を、送信時刻順に並べて、隣接する送信時刻の時間間隔が閾時間以内となる２つパケットを抽出し、更に、宛先端末を共通にする計測情報を、受信時刻順に並べて、隣接する受信時刻の時間間隔が閾時間以内となるパケットペアを抽出する計測パケット抽出手段と、
抽出された複数のパケットについて送信時刻と受信時刻との差からパケット遅延を算出するパケット遅延検出手段と
してコンピュータを機能させることを特徴とする。
【００１６】
本発明のプログラムにおける他の実施形態によれば、
パス毎に、パケット遅延の最小値を導出するパケット遅延最小値導出手段と、
２つのパスのペア毎に、パケット遅延と最小値との間の変化分の二乗和を導出し、それらの平均値を非類似度として算出する非類似度算出手段と、
非類似度の低い２つのパスのペアを導出する輻輳パス分類手段と
して更にコンピュータを機能させることも好ましい。
【００１７】
本発明のプログラムにおける他の実施形態によれば、輻輳パス分類手段は、
パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するデンドログラム作成手段と、
デンドログラムの非類似度に応じて、パスを分類するパス分類手段と
して更にコンピュータを機能させることも好ましい。
【発明の効果】
【００１８】
本発明の輻輳パス分類方法、管理装置及びプログラムによれば、ＩＰネットワークについて、パケット遅延によって短時間に発生する輻輳を検出するために、その輻輳を共通に経験するパスをパケット遅延から分類することができる。
【発明を実施するための最良の形態】
【００１９】
以下では、図面を用いて、本発明を実施するための最良の形態について詳細に説明する。
【００２０】
図１は、ネットワーク構成図である。
【００２１】
図１によれば、４つの計測端末Ａ〜Ｄが、区間１から５を有するネットワークを介して接続されている。また、ネットワークには管理装置２も接続されており、全ての計測端末Ａ〜Ｄは、計測情報を管理装置２へ送信する。ここで、パスとは、計測端末間毎の経路をいう。また、区間とは、分岐・合流点によって分割されるパスの一部をいう。例えば、ＰＡＴＨ１は、計測端末Ａと計測端末Ｂとの間の経路を表し、区間１、区間２及び区間３を介して接続されている。
【００２２】
表１は、図１のネットワークトポロジを表す。
【表１】
2007243368.tif 000001
【００２３】
図２は、本発明におけるパケットペアの受信を表す説明図である。
【００２４】
パケットペアとは、時間的に隣接する２つのパケットの組み合わせをいう。図２によれば、計測端末Ｂに注目している。計測端末Ｂは、計測端末Ａとの間でＰＡＴＨ１を、計測端末Ｃとの間でＰＡＴＨ４を、計測端末Ｄとの間でＰＡＴＨ５を接続している。ＰＡＴＨ１は、区間１、２及び３を介して接続され、ＰＡＴＨ４は、区間２、３及び５を介して接続され、ＰＡＴＨ５は、区間３及び４を介して接続されている。
【００２５】
表２は、計測端末Ｂについてのネットワークトポロジを表す。
【表２】
2007243368.tif 000002
【００２６】
表２からも明らかなとおり、区間２に発生したパケット遅延による輻輳は、ＰＡＴＨ１及び４を経由した複数のパケットによって経験されることとなる。また、区間３に発生した遅延による輻輳は、ＰＡＴＨ１、４及び５を経由した複数のパケットによって経験されることとなる。
【００２７】
図２によれば、宛先端末を共通にする計測情報を、受信時刻順に並べて、隣接する受信時刻の時間間隔が閾時間以内となるパケットペアを抽出することが表されている。パケットペアギャップとは、パケットペアにおける受信時刻又は送信時刻の時間間隔をいう。図２には、パケット毎に、送信元の計測端末の識別子と、そのシーケンス番号とが表されている。
【００２８】
表３は、計測端末Ｂによって受信されたパケットを、受信時刻順に並べたものである。
【表３】
2007243368.tif 000003
【００２９】
表３に基づいて、計測パケットとなるパケットペアを抽出する。抽出されるパケットペアは、時間的に隣接する２つのパケットであって、パスが異なり（送信元の計測端末が異なり）、且つ、パケットペアギャップが閾時間以内（例えば２０ｍｓ以下）であることを条件とする。
【００３０】
・パケットＡ（１）及びパケットＡ（２）は、送信元が計測端末Ａで同一であって且つパスも同一であるので、計測パケットとして抽出しない。
・パケットＡ（２）及びパケットＣ（１）は、パケットペアギャップが閾時間以内であるので、計測パケットとして抽出する。
・パケットＣ（１）及びパケットＤ（１）は、パケットペアギャップが閾時間以内であるので、計測パケットとして抽出する。
・パケットＤ（１）及びパケットＣ（２）は、パケットペアギャップが閾時間より長いので、計測パケットとして抽出しない。
・パケットＣ（２）及びパケットＤ（２）は、パケットペアギャップが閾時間以内であるので、計測パケットとして抽出する。
【００３１】
前述とは逆に、送信元端末を共通にする計測情報を、送信時刻順に並べて、隣接する送信時刻の時間間隔が閾時間以内となる２つパケットも抽出する。従って、送信時刻順に並べると、前述した表３とは異なる並びとなる。
【００３２】
表４は、計測端末Ｂへ送信されたパケットを、送信時刻順に並べたものである。
【表４】
2007243368.tif 000004
【００３３】
表４に基づいて、更に、計測パケットとなるパケットペアを抽出する。抽出されるパケットペアは、時間的に隣接する２つのパケットであって、パスが異なり（宛先の計測端末が異なり）、且つ、パケットペアギャップが閾時間以内（例えば２０ｍｓ以下）であることを条件とする。
【００３４】
本発明によれば、各パス間において、同時に短時間の輻輳を経験する可能性のあるパケットのみを抽出し、それらパケットのみについてパケット遅延を計測することができる。このパケット遅延変動（遅延と最小値との差）に基づいて、同じ輻輳を経験するパスを導出することができる。
【００３５】
尚、転送されるパケットは、送信時刻を含むことを要する。従って、パケット自体は、計測用のテストパケットであってもよいし、通常のデータパケットであってもよい。例えば、ＲＴＰ(Realtime Transfer Protocol)によれば、ヘッダにタイムスタンプが含められる。
【００３６】
図３は、本発明におけるフローチャートである。
【００３７】
（Ｓ３０１）送信側計測端末は、複数のパケットを相手方計測端末へ送信する。パケットは、送信時刻を含む。また、パケットの送信間隔は一定ではなく、ランダム性を有する。尚、全ての計測端末の時刻は同期しているものとする。
【００３８】
（Ｓ３０２）受信側計測端末は、送信側計測端末から送信されたパケット受信する。このとき、パケット毎に受信時刻をスタンプする。これにより、受信したパケットについて、送信時刻と受信時刻とを取得することができる。
（Ｓ３０３）受信側計測端末は、計測情報を生成する。計測情報は、受信したパケット毎に、送信元端末のアドレスと、宛先端末のアドレスと、送信時刻と、受信時刻とを含む。
【表５】
2007243368.tif 000005
【００３９】
（Ｓ３０４）受信側計測端末は、パケット毎の計測情報を、管理装置へ送信する。
【００４０】
（Ｓ３０５）管理装置は、複数の受信側計測端末から、複数の計測情報を受信する。これら計測情報は、一定以上収集して記憶する。
（Ｓ３０６）管理装置は、送信元端末を共通にする計測情報を、送信時刻順に並べて、隣接する送信時刻の時間間隔（パケットペアギャップ）が閾時間以内となるパケットペアを抽出する。また、宛先端末を共通にする計測情報を、受信時刻順に並べて、隣接する受信時刻の時間間隔（パケットペアギャップ）が閾時間以内となるパケットペアを抽出する。閾時間とは、数十ミリ秒程度、例えば２０ｍｓであってもよい。これにより、１つの区間で２０ｍｓ程度以上の遅延による輻輳が発生した場合、その区間を介した異なるパスに対して共通のパケット遅延変動として検出される。
【００４１】
（Ｓ３０７）管理装置は、抽出されたパケットペアについて、送信側計測端末の送信時刻と、受信側計測端末の受信時刻との差から、パケット遅延を導出する。
（Ｓ３０８）パス毎に、パケット遅延の最小値を導出する。最小値は、パケット遅延変動の基準値となる。従って、その最小値に対してパケット遅延変動が算出される。
【００４２】
（Ｓ３０９）非類似度ｄは、以下の式によって算出される。
【数１】
2007243368.tif 000006
ｎは、比較するパケットのペア数である。ｘk及びｙkは、それぞれ異なる２パス上のパケット遅延変動（パケット遅延と最小値との間の変化分）を表す。従って、（ｘk−ｙk）は、２つのパスのペアについて、パケット遅延変動の差を表す。ａｖｅ（ｘk、ｙk）は、パケット遅延変動の平均値を表す。従って、（ｘk−ｙk）／ａｖｅ（ｘk、ｙk）は、平均値に対するパケット遅延変動の差の比率を表す。これら比率の二乗和を導出することにより、非類似度ｄを算出する。
【００４３】
（Ｓ３１０）パスのペア毎に、非類似度ｄの低いペアから順に、クラスタ分析（数値分類法）におけるウォード法を適用してデンドログラム（樹形図）を作成する。クラスタ分析とは、異なる性質のもの同士が混ざり合っている集団の中から、互いに似たものを集めてクラスタを作り、対象を分類しようとする方法をいう。ウォード法とは、階層型クラスタ分析方法の１つであって、互いに似たもの同士を分類する際に、クラスタ内の全ての個体に対してのクラスタ重心からの偏差平方和を求め、そのクラスタ内平方和の増分ができるだけ小さくなるように併合するものである。互いに似ているかどうかの判定基準としては、ユークリッド平方距離を用いることが多い。互いが似ているパスのペアの併合を繰り返し、デンドログラムを作成する。
【００４４】
（Ｓ３１１）デンドログラムの非類似度に応じて、パスを分類する。パスの分類は、例えば、非類似度の最大値の１／２の高さで分類するというように条件を要する。ある区間で輻輳が発生した場合、デンドログラムによれば、２つのクラスタに分類される。
【００４５】
その後、各パスの経路情報を比較し、輻輳パスが共有しており、かつ、非輻輳パスが経由しない区間を輻輳区間として特定する。
【００４６】
図４は、インターネット上のトラヒック計測実験結果によって計算した、ある５秒間における３０パスのパケット遅延変動を表すグラフである。
【００４７】
図４のグラフは、Ｓ３０９において算出される。２拠点でそれぞれ３つのＩＳＰ(Internet Service Provider)網に光アクセス回線を介して接続したネットワークを用いた。アクティブ計測実験は、送受信ＩＳＰの組み合わせによって３０パスを介して２４時間実施した。各パスでは、６４バイトのＵＤＰテストパケットを１０〜９０ｍｓの一様分布に従う間隔で送信した。
【００４８】
５秒周期で各パスのパケット遅延変動の９９％値を集計し、少なくとも１パスで閾時間２０ｍｓ以上となった５秒間を対象とし、３０パスのクラスタリングをした（７０４回）。閾時間は、共通のパケット遅延変動の影響を受ける可能性が高い間隔以下に設定する必要があるために、対象とするパケット遅延変動の９９％値と同じ２０ｍｓを採用した。
【００４９】
図５は、図４のデンドログラムである。
【００５０】
図５のグラフは、Ｓ３１０によって作成される。図５のグラフによれば、縦軸はクラスタ間の非類似度を表し、３０パスについて非類似度の低いパスから順に分類されている。
【００５１】
次に、Ｓ３１１によってパスが分類される。非類似度の最大値の１／２の高さで分類した場合、図５のグラフによれば、クラスタＡ（パス１３、２４、２９、３、８）と、クラスタＢ（Ａ以外の２５パス）との２つに分類されている。ここで、クラスタＡに含まれる５パスは、図４においてパケット遅延変動が同期して増加している５パスに対応する。一方、クラスタＢに含まれる２５パスでは、パケット遅延変動が増加していない。このように、共通の輻輳を経験する５パスと、それ以外の２５パスとを、高い精度で分類することができる。
【００５２】
図６は、本発明における計測端末及び管理装置の機能構成図である。
【００５３】
図６によれば、計測端末１は、パケット送信部１０と、パケット受信部１１と、計測情報生成部１２と、計測情報送信部１３とを有する。これら機能部は、計測端末１に搭載されたコンピュータによって実行されるプログラムによっても実現できる。
【００５４】
パケット送信部１０は、送信時刻を含む複数のパケットを、相手方計測端末へ送信する。前述したＳ３０１の動作をする。
【００５５】
パケット受信部１１は、複数の相手方計測端末から、送信時刻を含む複数のパケットを受信する。前述したＳ３０２の動作をする。
【００５６】
計測情報生成部１２は、受信したパケット毎に、送信元端末のアドレスと、宛先端末のアドレスと、送信時刻と、受信時刻とを含む計測情報を生成する。前述したＳ３０３の動作をする。
【００５７】
計測情報送信部１３は、生成された計測情報を管理装置へ送信する。前述したＳ３０４の動作をする。
【００５８】
図６によれば、管理装置２は、計測情報収集部２１と、計測パケット抽出部２２と、パケット遅延算出部２３と、パケット遅延最小値導出部２４と、非類似度算出部２５と、輻輳パス分類部２６とを有する。輻輳パス分類部２６は、デンドログラム作成部２６１と、パス分類部２６２とを有する。これら機能部は、管理装置２に搭載されたコンピュータによって実行されるプログラムによっても実現できる。
【００５９】
計測情報収集部２１は、複数の計測端末から、計測情報を受信し蓄積する。前述したＳ３０６の動作をする。
【００６０】
計測パケット抽出部２２は、計測対象となるパケットペアを抽出する。送信元端末を共通にする計測情報を、送信時刻順に並べて、隣接する送信時刻の時間間隔が閾時間以内となるパケットペアを抽出する。また、宛先端末を共通にする計測情報を、受信時刻順に並べて、隣接する受信時刻の時間間隔が閾時間以内となるパケットペアを抽出する。前述したＳ３０７の動作をする。
【００６１】
パケット遅延最小値導出部２４は、パス毎に、パケット遅延の最小値を導出する。前述したＳ３０８の動作をする。
【００６２】
非類似度算出部２５は、２つのパスのペア毎に、パケット遅延と最小値との間の変化分の二乗和を導出し、それらの平均値を非類似度として算出する。前述したＳ３０９の動作をする。
【００６３】
デンドログラム作成部２６１は、パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成する。前述したＳ３１０の動作をする。
【００６４】
パス分類部２６２は、デンドログラムの非類似度に応じて、パスを分類する。前述したＳ３１１の動作をする。
【００６５】
パスの途中にある区間でのパケットペアギャップは計測することが困難なため、比較するパスの送信ノードが共通の場合は、パケット送信時刻の差、受信ノードが共通の場合は受信時刻の差をパケットペアギャップとする。それ以外の場合は、区間を共有してない可能性があるため、便宜上、受信時刻の差で計算する。
【００６６】
本発明の輻輳パス分類方法等によれば、ＩＰネットワークについて、パケット遅延によって短時間に発生する輻輳を検出するために、その輻輳を共通に経験するパスをパケット遅延から分類することができる。従って、"traceroute"では検出できないレイヤ２ノードでの劣化に対しても、パスを分類することができる。本発明は、パス毎のパケット遅延変動をパケット単位で比較し、その変動の類似性に基づいて各パスの品質を分類することができる。
【００６７】
前述した本発明における種々の実施形態によれば、当業者は、本発明の技術思想及び見地の範囲における種々の変更、修正及び省略を容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【図面の簡単な説明】
【００６８】
【図１】ネットワーク構成図である。
【図２】本発明におけるパケットペアの受信を表す説明図である。
【図３】本発明におけるフローチャートである。
【図４】インターネット上のトラヒック計測実験結果によって計算した、ある５秒間における３０パスのパケット遅延変動を表すグラフである。
【図５】図４のデンドログラムである。
【図６】本発明における計測端末及び管理装置の機能構成図である。
【符号の説明】
【００６９】
１  計測端末
１０  パケット送信部
１１  パケット受信部
１２  計測情報生成部
１３  計測情報送信部
２  管理装置
２１  計測情報収集部
２２  計測パケット抽出部
２３  パケット遅延算出部
２４  パケット遅延最小値導出部
２５  非類似度算出部
２６  輻輳パス分類部
２６１  デンドログラム作成部
２６２  パス分類部
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2007243368.tif 000007
【図２】
2007243368.tif 000008
【図３】
2007243368.tif 000009
【図４】
2007243368.tif 000010
【図５】
2007243368.tif 000011
【図６】
2007243368.tif 000012