JP2008042879A - パケットの遅延変動時間に基づいて輻輳パスを分類する輻輳パス分類方法、管理装置及びプログラム - Google Patents

Abstract

【課題】パケット遅延変動によって短時間に発生する輻輳を検出するために、その輻輳を共通に経験するパスをパケット遅延から分類する輻輳パス分類方法等を提供する。
【解決手段】計測端末によって受信されたパケット毎に、送信時刻及び受信時刻の計測情報を受信する。２つのパスについて、送信時刻と受信時刻との間の転送時間の少なくとも一部が重なるパケットペアの集合を抽出する。次に、抽出されたパケットペアについて、送信時刻と受信時刻とからパケット遅延を算出する。次に、パス毎に、所定期間における複数の計測情報のパケット遅延の中で、最小遅延時間を導出する。次に、計測情報毎に、当該遅延と最小遅延時間との差を遅延変動時間として算出する。そして、抽出されたパケットペアの集合の中から、ワーピングコストを最小とする最小ワーピングパスを導出する。最後に、最小ワーピングパスにおける２つのパスの間の非類似度を算出する。
【選択図】図４

Description

本発明は、パケットの遅延変動時間に基づいて輻輳パスを分類する輻輳パス分類方法、管理装置及びプログラムに関する。特に、ＩＰ(Internet Protocol)ネットワークについて、パケット遅延に基づく短時間の輻輳を特定するために、パスを分類する方法等に関する。

インターネットは、ベストエフォート型通信であるので、正確な通信品質保証は困難である。これに対し、ＩＳＰ(Internet Service Provider)事業者が、品質劣化区間を特定し、経路変更又は回線増速等の運用制御によって品質劣化を回避している。しかし、インターネットは、多数の独立ネットワークによって構成されているために、ネットワーク内部の状態を直接的に計測できない場合がある。

従来、複数のパスの特性（例えばパケット損失率、パケット遅延等、以下「パス状態」という)を計測端末間でアクティブ計測して、ネットワークの品質劣化区間を特定する技術がある（例えば非特許文献１参照）。区間とは、分岐・合流点によって分割されるパスの一部をいう。この技術は、計測結果と所定閾値とを比較し、パスの品質を段階的に判定する（good/bad/ medium）。そして、品質劣化と判定されたパスの組み合わせと、それらパスの経路情報とによって、ネットワークにおける品質劣化区間を特定する。

また、複数のテストパケットを、複数のパスへ短い時間間隔で同時に送信し、受信されたパケットの相関によって、共有される区間の品質を推定する技術もある（例えば非特許文献２参照）。

更に、大規模ネットワークの品質制御・管理を目的として、直接的に計測することが困難なネットワーク内部の特性（遅延変動や損失率の分布）を、間接的に推定するネットワークトモグラフィ技術もある（例えば非特許文献２、３及び４参照）。

A. Tachibana、S. Ano、T. Hasegawa、M.Tsuru、Y. Oie、「Locating Congested Segments over the Internet Based on MultipleEnd-to-End Path Measurements」、IEICE Transactions on Communications InternetTechnology VI, April 2006 M. Tsuru、T. Takine and Y. Oie.、「Inferringlink characteristics from end-to-end path measurements」、In Proc. IEEE ICC、Helsinki(2001)、1534-1538 R. Caceres、N. Duffield、J. Horowitz、D.Towsley、「Multicast-based inference of network-internal loss characteristics」、IEEETrans. Info. Theory、45(7):2462--2480、1999. N. Duffield、F. L. Presti、V. Paxson、D.Towsley、「Inferring link loss using striped unicast probes」、Proc. IEEE infocom、Anchorage、Apr.2001.

しかしながら、非特許文献１のように、集計値（例えば一定周期の平均値や最大値）と所定閾値とを比較する場合、集計値と閾値との差が小さいと、極端に正常／異常とを判定することとなる。従って、閾値によって分類結果が大きく異なる可能性がある。また、非特許文献２によれば、全てのテストパケットについてパケット間の相関を判定するために、非常に高精度な計測及び複雑な計算が必要となる。極めて近接したテストパケットを送出することは困難な場合も多い。

従来技術は、パス毎に、パス状態の平均値や最大値を算出した集計値によって劣化状態を判定する。現実には、１つの区間において品質劣化が発生した場合、その区間を経由する複数のパスに同時に品質劣化が発生する。それにも関わらず、パス毎に単一の劣化状態と判定し、全体の集計値からパスの相関を検出しようとしている。

また、従来技術によれば、パス毎に、パス状態の集計値から品質劣化区間を特定しようとするために、パケット遅延のような短時間（例えば２０ｍｓ程度）発生する輻輳を特定することはできない。しかしながら、光ファイバによって基幹網が構築されているような場合は、短時間の輻輳であってもネットワーク全体に与える影響が大きい。従って、短時間の輻輳を時々発生するような経路を回避する必要がある。

更に、近年では、ＶｏＩＰ(Voice over IP)のように、パケットの遅延変動によって品質劣化するアプリケーションの利用も多くなっている。

更に、ネットワークトモグラフィ技術によれば、統計的特性（分布）を利用するために、品質劣化区間のリアルタイム推定への適用が困難である。また、大量の計測パケット（テストパケット、プローブパケット）を必要とする。高精度に推定するためには、計測パケットとして、マルチキャストパケットやパケット間隔の小さい連続パケットを送受信する必要があるため、ツリー状トポロジにしか適用できないという問題もある。

従って、本発明は、ＩＰネットワークについて、短時間に発生する輻輳を検出するために、複数のパケットの遅延変動の時系列を周期的に比較することにより、その輻輳を共通に経験するパスを、リアルタイムに分類することができる輻輳パス分類方法、管理装置及びプログラムを提供することを目的とする。

本発明によれば、複数の計測端末間のパスにおける遅延変動時間に基づいて、輻輳パスを分類する管理装置における輻輳パス特定方法であって、
計測端末によって受信された計測パケットに基づいて、該計測端末から、送信元アドレス、受信端末アドレス、送信時刻及び受信時刻を含む計測情報を受信する第１のステップと、
２つのパスについて、送信時刻と受信時刻との間の転送時間の少なくとも一部が重なるパケットペアの集合を抽出する第２のステップと、
抽出されたパケットペアについて、計測情報の送信時刻及び受信時刻から各パケットの遅延時間を算出する第３のステップと、
パス毎に、所定期間における複数の遅延時間から、遅延変動時間を算出する第４のステップと、
抽出されたパケットペアの集合の中から、ワーピングコストを最小とする最小ワーピングパスを導出する第５のステップと、
最小ワーピングパスにおける２つのパスの間の非類似度を算出する第６のステップと、
非類似度をクラスタリングすることによって非輻輳パスの集合と輻輳パスの集合とを特定する第７のステップと
を有することを特徴とする。

本発明の輻輳パス特定方法における他の実施形態によれば、第４のステップについて、
パス毎に、所定期間における複数の計測情報のパケット遅延の中で最小遅延時間を導出し、計測情報毎に、当該遅延時間と最小遅延時間との差を遅延変動時間として算出することも好ましい。

本発明の輻輳パス特定方法における他の実施形態によれば、第４のステップについて、当該遅延時間と最小遅延時間との差の最大値が、所定閾値以下となる場合は、当該パスを非輻輳パスとして特定する。

本発明の輻輳パス特定方法における他の実施形態によれば、第７のステップについて、２つのパスのパケットペア毎に、遅延変動時間の差の二乗に対する、それらの平均値との比を算出し、それら比の和により算出される非類似度の低い２つのパスのペアを導出することも好ましい。

本発明の輻輳パス特定方法における他の実施形態によれば、第７のステップについて、
２つのパスの非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成し、
デンドログラムの非類似度に応じて、パスを分類することも好ましい。

本発明によれば、複数の計測端末間のパスにおける遅延変動時間に基づいて、輻輳パスを分類する管理装置において、
計測端末によって受信された計測パケットに基づいて、該計測端末から、送信元アドレス、受信端末アドレス、送信時刻及び受信時刻を含む計測情報を受信する計測情報収集手段と、
２つのパスについて、送信時刻と受信時刻との間の転送時間の少なくとも一部が重なるパケットペアの集合を抽出する計測情報抽出手段と、
抽出されたパケットペアについて、計測情報の送信時刻及び受信時刻から各パケットの遅延時間を算出する遅延時間算出手段と、
パス毎に、所定期間における複数の遅延時間から、遅延変動時間を算出する遅延変動算出手段と、
抽出されたパケットペアの集合の中から、ワーピングコストを最小とする最小ワーピングパスを導出する最小ワーピングパス導出手段と、
最小ワーピングパスにおける２つのパスの間の非類似度を算出する非類似度算出手段と、
クラスタリングによって非輻輳パスの集合と輻輳パスの集合とを特定する輻輳パス特定手段と
を有することを特徴とする。

本発明の管理装置における他の実施形態によれば、
パス毎に、所定期間における複数の計測情報のパケット遅延の中で最小遅延時間を導出する最小遅延時間導出手段を更に有し、
遅延変動算出手段は、計測情報毎に、当該遅延時間と最小遅延時間との差を遅延変動時間として算出することも好ましい。

本発明の管理装置における他の実施形態によれば、遅延変動算出手段から出力された当該遅延時間と最小遅延時間との差の最大値が、所定閾値以下となる場合は、当該パスを非輻輳パスとして特定する非輻輳パスフィルタ手段を更に有する。

本発明の管理装置における他の実施形態によれば、輻輳パス特定手段は、２つのパスのパケットペア毎に、遅延変動時間の差の二乗に対する、それらの平均値との比を算出し、それら比の和により算出される非類似度の低い２つのパスのペアを導出することも好ましい。

本発明の管理装置における他の実施形態によれば、輻輳パス特定手段は、
２つのパスの非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するデンドログラム作成手段と、
デンドログラムの非類似度に応じて、パスを分類するパス分類手段と
を更に有することも好ましい。

本発明によれば、複数の計測端末間のパスにおける遅延変動時間に基づいて、輻輳パスを分類する管理装置に搭載されたコンピュータを機能させるプログラムにおいて、
計測端末によって受信された計測パケットに基づいて、該計測端末から、送信元アドレス、受信端末アドレス、送信時刻及び受信時刻を含む計測情報を受信する計測情報収集手段と、
２つのパスについて、送信時刻と受信時刻との間の転送時間の少なくとも一部が重なるパケットペアの集合を抽出する計測情報抽出手段と、
抽出されたパケットペアについて、計測情報の送信時刻及び受信時刻から各パケットの遅延時間を算出する遅延時間算出手段と、
パス毎に、所定期間における複数の遅延時間から、遅延変動時間を算出する遅延変動算出手段と、
抽出されたパケットペアの集合の中から、ワーピングコストを最小とする最小ワーピングパスを導出する最小ワーピングパス導出手段と、
最小ワーピングパスにおける２つのパスの間の非類似度を算出する非類似度算出手段と、
クラスタリングによって非輻輳パスの集合と輻輳パスの集合とを特定する輻輳パス特定手段と
してコンピュータを機能させることを特徴とする。

本発明の管理装置用のプログラムにおける他の実施形態によれば、
パス毎に、所定期間における複数の計測情報のパケット遅延の中で最小遅延時間を導出する最小遅延時間導出手段を更に有し、
遅延変動算出手段は、計測情報毎に、当該遅延時間と最小遅延時間との差を遅延変動時間として算出するようにコンピュータを機能させることも好ましい。

本発明の管理装置用のプログラムにおける他の実施形態によれば、遅延変動算出手段から出力された当該遅延時間と最小遅延時間との差の最大値が、所定閾値以下となる場合は、当該パスを非輻輳パスとして特定する非輻輳パスフィルタ手段を更に有する。

本発明の管理装置用のプログラムにおける他の実施形態によれば、輻輳パス特定手段は、２つのパスのパケットペア毎に、遅延変動時間の差の二乗に対する、それらの平均値との比を算出し、それら比の和により算出される非類似度の低い２つのパスのペアを導出するようにコンピュータを機能させることも好ましい。

本発明の管理装置用のプログラムにおける他の実施形態によれば、輻輳パス特定手段は、
２つのパスの非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するデンドログラム作成手段と、
デンドログラムの非類似度に応じて、パスを分類するパス分類手段と
してコンピュータを機能させることも好ましい。

本発明の輻輳パス分類方法、管理装置及びプログラムによれば、ＩＰネットワークについて、短時間に発生する輻輳を検出するために、複数のパケットの遅延変動の時系列を周期的に比較することにより、その輻輳を共通に経験するパスを、リアルタイムに分類することができる。遅延変動時間の計測において、ランダムなパケット間隔のプローブパケットを用いるため、大規模なＩＰネットワークに適用することができる。更に、輻輳パスを特定するために必要な計測情報をできる限り少なくすることのよって、計算量を削減することができる。

以下では、図面を用いて、本発明を実施するための最良の形態について詳細に説明する。

本発明は、複数のパスに沿ってランダムな間隔の計測パケット（テストパケット、プロローブパケット）を転送する。これにより、遅延変動時間を計測する。収集された遅延変動時間が周期的に比較され、時系列の類似性に基づいて共通の品質劣化を経験したパス群を抽出する。パス群の経路情報を比較し、ネットワーク内部の品質劣化区間を推定する。

図１は、ネットワーク構成図である。

図１によれば、４つの計測端末Ａ〜Ｄが、区間１から５を有するネットワークを介して接続されている。計測端末同士の間では、複数の計測パケットが連続的に送受信される。また、ネットワークには管理装置２も接続されており、全ての計測端末Ａ〜Ｄは、計測情報を管理装置２へ送信する。ここで、「パス」とは、計測端末間毎の経路をいう。また、「区間」とは、分岐・合流点によって分割されるパスの一部をいう。

図１には、ネットワークトポロジの構成表も表されている。例えば、パス１は、計測端末Ａと計測端末Ｂとの間の経路を表し、区間１、区間２及び区間３を介して接続されている。

図２は、本発明におけるパケット受信を表す説明図である。

図２によれば、計測端末Ｂに注目している。計測端末Ｂは、計測端末Ａとの間でパス１（区間１−区間２−区間３）を介して接続され、計測端末Ｃとの間でパス４（区間５−区間２−区間３）を介して接続され、計測端末Ｄとの間でパス５（区間４−区間３）を介して接続されている。

図２に表されたネットワークトポロジからも明らかなとおり、例えば区間２に輻輳が発生した場合、その輻輳は、パス１及び４を経由した複数のパケットによって経験される。また、区間３に発生した輻輳は、パス１、４及び５を経由した複数のパケットによって経験される。

（Ｓ２０１）計測端末Ｂは、計測端末Ａ、Ｃ及びＤから、計測パケットを受信する。計測端末Ｂは、受信した計測パケット毎に、受信時刻をスタンプする。計測パケットには、「送信元アドレス」「シーケンス番号」「送信時刻」が含まれている。

計測パケットの送信間隔は、一定である必要はなく、ランダムであってもよい。尚、全ての計測端末Ａ〜Ｄで、時刻は同期しているものとする。また、計測パケットは、計測用のテストパケット（プローブパケット）であってもよいし、通常のデータパケットであってもよい。例えば、ＲＴＰ(Realtime Transfer Protocol)によれば、ヘッダにタイムスタンプが含められる。

（Ｓ２０２）計測端末Ｂは、受信した計測パケットに対する計測情報を生成する。計測情報には、「送信元アドレス」「受信端末アドレス」「送信時刻」「受信時刻」を含む。「受信端末アドレス」は、計測端末Ｂを特定する。「受信時刻」は、計測端末Ｂがブロードキャストパケットを受信した時刻である。そして、計測端末Ｂは、その計測情報を、管理装置２へ送信する。

ここで、計測端末１は、周期的（例えば１０秒毎）に、計測情報を管理装置２へ送信するように構成されていてもよい。

（Ｓ２０３）管理装置２は、計測端末Ｂから計測情報を受信だけでなく、全ての計測端末から計測情報を受信する。受信した計測情報は、受信端末毎に、記録される。

図３は、本発明におけるフローチャートである。

（Ｓ２０１）送信側計測端末は、複数の計測パケットを相手方計測端末へ送信する。前述した図２のＳ２０１と同じ処理をする。

（Ｓ２０２）計測パケットを受信した受信側計測端末は、計測情報を管理装置２へ送信する。前述した図２のＳ２０２と同じ処理をする。

（Ｓ２０３）管理装置２は、複数の計測端末から複数の計測情報を、常時、受信する。これら計測情報は、一定以上収集して記憶する。前述した図２のＳ２０３と同じ処理をする。

（Ｓ２０４）管理装置２は、受信端末毎に、送信元アドレスの異なる２つのパスについて、送信時刻と受信時刻との間の転送時間の少なくとも一部が重なるパケットペアの集合を抽出する。

例えば、パスＰにおけるi番目のパケットＰiと、パスＱにおけるj番目のパケットＱjとを比較するとする。パスＰは、送信端末Ａから受信端末Ｂへの経路とする。パスＱは、送信端末Ｃから受信端末Ｂへの経路とする。ここで、パケットＰiの転送時間と、パケットＱjの転送時間とを比較し、少なくとも一部が重なるか否かを判定する。パケットＰiの転送時間とは、送信端末Ａの送信時刻から受信端末Ｂの受信時刻までの時間である。パケットＱjの転送時間とは、送信端末Ｃの送信時刻から受信端末Ｂの受信時刻までの時間である。

更に、少なくとも一部の転送時間が重なると判定されたパケットＰi及びＱiについて、これら受信時刻の時間間隔（パケットペアギャップ）が閾時間以内となるパケットペアのみを抽出することも好ましい。閾時間とは、数十ミリ秒程度、例えば２０ｍｓであってもよい。これにより、１つの区間で２０ｍｓ程度以上の遅延による輻輳が発生した場合、その区間を介した異なるパスに対して共通の影響が検出される。

これにより、パス間において、同時に短時間の輻輳を経験する可能性のあるパケットのみを抽出し、それらパケットのみについて遅延変動時間（遅延時間と最小遅延時間との差）を計測することができる。

（Ｓ２０５）管理装置２は、抽出されたパケットペアの集合の中の各計測情報について、送信時刻と受信時刻とから遅延時間（＝受信時刻−送信時刻）を算出する。

（Ｓ２０６）パス毎に、一定期間における複数の計測情報のパケット遅延の中で、最小遅延時間を導出する。最小遅延時間は、遅延変動時間の基準値となる。従って、その最小遅延時間に対して遅延変動時間が算出される。

（Ｓ２０７）計測情報毎に、当該遅延時間と最小遅延時間との差を遅延変動時間として算出する。即ち、遅延変動時間は、最小遅延時間からの変化分で定義される。

（Ｓ２０８）ここで、当該遅延時間と最小遅延時間との差の最大値が、所定閾値以下となるパスを、非輻輳パスとして特定する。非輻輳パスとして特定されたパスは、そのままＳ２１２へ通知される。これにより、非輻輳パスについて、非類似度をクラスタリングする処理（Ｓ２０９〜Ｓ２１１）を省略することができる。品質劣化区間を通過した可能性の低いパスに対する計測情報は、計算に導入されない。即ち、品質劣化区間を通過した可能性の高いパスに対する計測情報のみを、計算に導入することができる。尚、所定閾値は、例えば、通常時の値の範囲として、過去の計測データより算出される各パスの遅延変動の標準偏差値の平均値を利用する。

（Ｓ２０９）抽出されたパケットペアの集合の中の各計測情報から、ワーピングコストを最小とする最小ワーピングパスを導出する。ワーピングパスは、２つの時系列データの対応付けを表す。ここで、タイムワーピング距離とは、時間軸方向のずれ（伸縮）に柔軟性を持たせて、２つの時系列データの類似度を導出するための要素である。例えば、以下のような参考文献がある。
大桃 諭、陳 漢雄、古瀬 一隆、大保 信夫、「タイムワーピングに基づく時系列データの類似検索：次元縮小による効率化」、日本データベース学会Letters Vo.4, N0.1、[online]、[平成１８年７月５日検索]、インターネット＜ＵＲＬ：http://www.dbsj.org/Japanese/DBSJLetters/vol4/no1/papers/oomomo.pdf＞

図４は、パケットの遅延変動時間に対するワーピングパスの説明図である。

図４のN×M行列は、横軸をパスＰにおけるパケットＰi（i＝1〜N）とし、縦軸をパスＱにおけるパケットＱj（j＝1〜M）とする。パスＰのパケットの遅延変動時間は、p1,p2, …, pNで表され、パスＱのパケットの遅延変動時間は、q1, q2,…, qMで表されている。

N×M行列の要素は、以下の式に基づく距離（非類似度）ｄ(i,j)を表す。以下の式は、パケットの遅延変動時間の差の二乗に対する、それらの平均値との比を、距離として表す。
ｄ（i, j） ＝ （pi−qj）^２／average（pi, qi）
avarage（pi, qi）:パケットの遅延変動時間の平均値

２つの計測パケットは、ランダムな間隔（例えば５０ｍｓ程度の一様分布）で送信される。２つの計測パケットは、同期していないために、同一の品質劣化を経験したとしても、パケットの遅延変動時間は正確に一致しない。そのために、遅延変動時間が長いと、piとqjの差（pi−qj）が大きくなる。

本発明によれば、非類似度ｄに、時系列を時間軸方向に伸縮させて比較するタイムワーピング距離を応用する。

図４によれば、パケットＰiとパケットＱjについて、送信時刻と受信時刻との間の転送時間が少なくとも一部で重なっている要素は、灰色で表されている。灰色で表されたパケットペアの集合Ｕについて、順列で表されるワーピングパスＷ＝w1,w2, …, wK, wk＝(i, j), max(M, N)≦K＜M+N-1を導出する。

ワーピングパスは、以下の条件を満たす。
（条件１）w1=(min(i), min(j))、wK=(max(i), max(j))とする。但し、(i,j)∈Ｕである。
（条件２）wk=(a, b), wk+1=(a’, b’)とすると，0≦a-a’かつ0≦b-b’となる。図４によれば、必ず横方向及び／又は上方向にワーピングパスが伸びる。
（条件３）wk=(a, b), wk+1=(a’, b’)とすると，a-a’≦1かつb-b’≦1となる。図４によれば、ワーピングパスが伸びる場合、必ず１要素分だけ伸びる。但し、集合Ｕが複数の部分データに分割されており、この条件を満たす(a’,b’)が存在しない場合は、wk+1=(min(i), min(j)), (i>a, j>b))となる。これにより、次のワーピングパスを見つけることとなる。

（Ｓ２１１）最小ワーピングパスにおける２つのパスの間の非類似度を算出する。集合Ｕ内においては、条件１〜３を満たすワーピングパスは複数存在するため、それぞれのワーピングパスに対して、ワーピングコストを計算する。ワーピングコストは、ワーピングパスにおけるｄ(wk)＝d(i, j) (wk=(i, j))の和によって定義される。
Ｃ＝１／Ｋ・√（Σ_k=1 ^Kｄ(ｗ_k)）

そして、ワーピングコストが最小となるワーピングパスを、最小ワーピングパスとして採用する。そのワーピングコストが、２つのパスの間の非類似度ｄとして定義される（ｄ＝min（Ｃ））。

更に、仮想的に遅延変動時間が、常に０であるパス（「ベストパス」という）との非類似度を計算する。パスＰとベストパス０との距離は、以下のようになる。
ｄ（Ｐ，０）＝ｄ（ｗ_k）＝ｐi

図５は、２つのパスの遅延変動時間の類似関係を表すグラフである。

図５によれば、２つの遅延変動時間の間に、細線が引かれている。これは、転送時間が重なっている２つのパケット同士を結んでいる。タイムワーピング距離を用いることにより、時間軸方向のずれ（伸縮）に柔軟性を持たせて、２つの時系列データの類似度を導出することができる。

（Ｓ２１０）パスのペア毎に、非類似度ｄの低いペアから順に、クラスタ分析（数値分類法）におけるウォード法を適用してデンドログラム（樹形図）を作成する。

クラスタ分析とは、異なる性質のもの同士が混ざり合っている集団の中から、互いに似たものを集めてクラスタを作り、対象を分類しようとする方法をいう。最初に、各パスを要素とするクラスタに分類する。Ｎ本のパスをクラスタリングする場合、Ｎ個のクラスタに分類する。そして、非類似度ｄが最小となる２つのパスを抽出し、それらを１つのクラスタに結合する。この結果、クラスタの総数は１個減少し、Ｎ−１個となる。

次に、結合したクラスタと、残りのクラスタとの非類似度を再計算する。再計算の方法は様々なアルゴリズムが提案されているが、代表的なウォード法を適用する。

ウォード法とは、階層型クラスタ分析方法の１つであって、互いに似たもの同士を分類する際に、クラスタ内の全ての個体に対してのクラスタ重心からの偏差平方和を求め、そのクラスタ内平方和の増分ができるだけ小さくなるように併合するものである。

互いに似ているかどうかの判定基準としては、ユークリッド平方距離を用いることが多い。互いが似ているパスのペアの併合を、１つのクラスタに結合されるまで繰り返し、デンドログラムを作成する。デンドログラムは、各クラスタ間の非類似度の関係を表す。

（Ｓ２１２）デンドログラムの非類似度における適当な高さ（例えば１／２）で切断し、パスを複数のクラスタに分類する。少なくとも最も高い位置で切断した場合、２つのクラスタに分類される。

その後、各パスの経路情報を比較し、共通の輻輳を経験しているパスが共有しており、かつ、その他のパスが経由しない区間を輻輳区間として特定する。

このように、特定のパスに品質劣化が発生した場合、同じ品質劣化を経験する他のパスにも、その影響が生じる。これを、パケットの遅延変動時間によって、パケットペアの集合を、クラスタリングによって分類することにより、同じ品質劣化を経験するパスを特定することができる。

図６は、インターネット上のトラヒック計測実験結果によって計算した、ある５秒間における３０パスの遅延変動を表すグラフである。

図６のグラフは、Ｓ２０７において算出される。２拠点でそれぞれ３つのＩＳＰ(Internet Service Provider)網に光アクセス回線を介して接続したネットワークを用いた。アクティブ計測実験は、送受信ＩＳＰの組み合わせによって３０パスを介して２４時間実施した。各パスでは、６４バイトのＵＤＰテストパケットを１０〜９０ｍｓの一様分布に従う間隔で送信した。

５秒周期で各パスのパケットの遅延変動の９９％値を集計し、少なくとも１パスで閾時間２０ｍｓ以上となった５秒間を対象とし、３０パスのクラスタリングをした（７０４回）。

図７は、図６のデンドログラムである。

図７のグラフは、Ｓ２１０によって作成される。図７のグラフによれば、縦軸はクラスタ間の非類似度を表し、３０パスについて非類似度の低いパスから順に分類されている。

非類似度の最大値の１／２の高さで分類した場合、図７のグラフによれば、クラスタＡ（パス１３、２４、２９、３、８）と、クラスタＢ（Ａ以外の２５パス）との２つに分類されている。ここで、クラスタＡに含まれる５パスは、図６においてパケットの遅延変動が同期して増加している５パスに対応する。一方、クラスタＢに含まれる２５パスでは、パケットの遅延変動が増加していない。このように、共通の輻輳を経験する５パスと、それ以外の２５パスとを、高い精度で分類することができる。

分類は、最初に、各クラスタに分類されたパスのパケット遅延変動の９９％値を集計する。そして、例えば、１パスで閾時間２０ｍｓ以上となった５秒間を対象として、そのパスが属するクラスタは、共通の品質劣化を経験したパスの集合であると判定する。即ち、図６及び図７によれば、クラスタＡに分類された５本のパス（パス１３、２４、２９、３、８）のいずれかにおいて、閾時間２０ｍｓ以上となっているため、これら５本のパスを共通の輻輳を経験する５パスとして分類する。一方、クラスタＢに分類された２５本のパスでは、パケット遅延変動の９９％値が閾時間２０ｍｓ以上とならないため、共通の輻輳を経験したと判断せず、非輻輳パスとして特定する。。

前述では、非類似度の最大値の１／２の高さで分類している。これに代えて、同一クラスタに分類される２パス間の非類似度が、異なるクラスタに分類される２パス間の非類似度よりも常に大きくなるような高さで分類することも好ましい。

図８は、本発明における計測端末及び管理装置の機能構成図である。

図８によれば、計測端末１は、パケット送信部１０と、パケット受信部１１と、計測情報生成部１２と、計測情報送信部１３とを有する。これら機能部は、計測端末１に搭載されたコンピュータによって実行されるプログラムによっても実現できる。

パケット送信部１０は、送信時刻を含む複数のパケットを、相手方計測端末へ送信する。前述したＳ２０１の動作をする。

パケット受信部１１は、複数の相手方計測端末から、送信時刻を含む複数のパケットを受信する。前述したＳ２０２の動作をする。

計測情報生成部１２は、受信したパケット毎に、送信元端末のアドレスと、宛先端末のアドレスと、送信時刻と、受信時刻とを含む計測情報を生成する。前述したＳ２０３の動作をする。

計測情報送信部１３は、生成された計測情報を管理装置へ送信する。前述したＳ２０４の動作をする。

図８によれば、管理装置２は、計測情報収集部２１と、計測情報抽出部２２と、遅延時間算出部２３と、最小遅延時間導出部２４と、遅延変動算出部２５と、非輻輳パスフィルタ部２６と、最小ワーピングパス導出部２７と、非類似度算出部２８と、輻輳パス分類部２９とを有する。輻輳パス分類部２９は、デンドログラム作成部２９１と、パス分類部２９２とを有する。これら機能部は、管理装置２に搭載されたコンピュータによって実行されるプログラムによっても実現できる。

計測情報収集部２１は、複数の計測端末から、計測情報を受信し蓄積する。前述した図３のＳ２０３の動作をする。

計測情報抽出部２２は、計測対象となるパケットペアを抽出する。２つのパスについて、送信時刻と受信時刻との間の転送時間の少なくとも一部が重なるパケットペアの集合を抽出する。前述した図３のＳ２０４の動作をする。

遅延時間算出部２３は、抽出されたパケットペアについて、送信時刻と受信時刻とからパケット遅延を算出する。前述した図３のＳ２０５の動作をする。

最小遅延時間導出部２４は、パス毎に、所定期間における複数の計測情報のパケット遅延の中で、最小遅延時間を導出する。前述した図３のＳ２０６の動作をする。

遅延変動算出部２５は、計測情報毎に、当該遅延時間と最小遅延時間との差を遅延変動時間として算出する。前述した図３のＳ２０７の動作をする。

非輻輳パスフィルタ部２６は、当該遅延時間と最小遅延時間との差の最大値が、所定閾値以下となる場合は、当該パスを非輻輳パスとして特定する。非輻輳パスとして特定されたパスは、そのままパス分類部２９２へ通知される。これにより、非輻輳パスについて、非類似度をクラスタリングする処理を省略することができる。即ち、最小ワーピングパス導出部２７、非類似度算出部２８、及びデンドログラム作成部２９１の処理を省略することができる。尚、所定閾値は、例えば、通常時の値の範囲として、過去の計測データより算出される各パスの遅延変動の標準偏差値の平均値を利用する。非輻輳パスフィルタ部２６は、前述した図３のＳ２０８の動作をする。

最小ワーピングパス導出部２７は、抽出されたパケットペアの集合の中から、ワーピングコストを最小とする最小ワーピングパスを導出する。前述した図３のＳ２０９の動作をする。

非類似度算出部２８は、最小ワーピングパスにおける２つのパス間の非類似度を算出する。非類似度算出部２８は、２つのパスのパケットペア毎に、遅延変動時間の差の二乗に対する、それらの平均値との比を算出し、それら比の和により算出される非類似度の低い２つのパスのペアを導出する。前述したＳ２１０の動作をする。前述した図３のＳ２１０の動作をする。

デンドログラム作成部２９１は、パスのペア毎に、非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成する。前述した図３のＳ２１１の動作をする。

パス分類部２９２は、デンドログラムの非類似度に応じて、パスを分類する。前述した図３のＳ２１２の動作をする。

以上、詳細に説明したように、本発明の輻輳パス分類方法、管理装置及びプログラムによれば、ＩＰネットワークについて、短時間に発生する輻輳を検出するために、その輻輳を共通に経験するパスをパケットの遅延変動時間から分類することができる。従って、"traceroute"では検出できないレイヤ２ノードでの劣化に対しても、パスを分類することができる。本発明は、パス毎のパケットの遅延変動時間をパケット単位で比較し、その変動の類似性に基づいて各パスの品質を分類することができる。

前述した本発明における種々の実施形態によれば、当業者は、本発明の技術思想及び見地の範囲における種々の変更、修正及び省略を容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。

ネットワーク構成図である。 本発明におけるパケットペアの受信を表す説明図である。 本発明におけるフローチャートである。 パケットの遅延変動時間に対するワーピングパスの説明図である。 ２つのパスの遅延変動時間の類似関係を表すグラフである。 インターネット上のトラヒック計測実験結果によって計算した、ある５秒間における３０パスの遅延変動時間を表すグラフである。 図６のデンドログラムである。 本発明における計測端末及び管理装置の機能構成図である。

符号の説明

１ 計測端末
１０ パケット送信部
１１ パケット受信部
１２ 計測情報生成部
１３ 計測情報送信部
２ 管理装置
２１ 計測情報収集部
２２ 計測情報抽出部
２３ 遅延時間算出部
２４ 最小遅延時間導出部
２５ 遅延変動算出部
２６ 非輻輳パスフィルタ部
２７ 最小ワーピングパス導出部
２８ 非類似度算出部
２９ 輻輳パス分類部
２９１ デンドログラム作成部
２９２ パス分類部

Claims (15)

1. 複数の計測端末間のパスにおける遅延変動時間に基づいて、輻輳パスを分類する管理装置における輻輳パス特定方法であって、
   前記計測端末によって受信された計測パケットに基づいて、該計測端末から、送信元アドレス、受信端末アドレス、送信時刻及び受信時刻を含む計測情報を受信する第１のステップと、
   ２つのパスについて、送信時刻と受信時刻との間の転送時間の少なくとも一部が重なるパケットペアの集合を抽出する第２のステップと、
   抽出されたパケットペアについて、前記計測情報の送信時刻及び受信時刻から各パケットの遅延時間を算出する第３のステップと、
   パス毎に、所定期間における複数の前記遅延時間から、遅延変動時間を算出する第４のステップと、
   抽出された前記パケットペアの集合の中から、ワーピングコストを最小とする最小ワーピングパスを導出する第５のステップと、
   前記最小ワーピングパスにおける２つのパスの間の非類似度を算出する第６のステップと、
   前記非類似度をクラスタリングすることによって非輻輳パスの集合と輻輳パスの集合とを特定する第７のステップと
   を有することを特徴とする輻輳パス特定方法。
2. 第４のステップについて、
   パス毎に、所定期間における複数の計測情報のパケット遅延の中で最小遅延時間を導出し、
   前記計測情報毎に、当該遅延時間と前記最小遅延時間との差を遅延変動時間として算出する
   ことを特徴とする請求項１に記載の輻輳パス特定方法。
3. 第４のステップについて、当該遅延時間と前記最小遅延時間との差の最大値が、所定閾値以下となる場合は、当該パスを非輻輳パスとして特定することを特徴とする請求項２に記載の輻輳パス特定方法。
4. 第７のステップについて、２つのパスのパケットペア毎に、遅延変動時間の差の二乗に対する、それらの平均値との比を算出し、それら比の和により算出される非類似度の低い２つのパスのペアを導出することを特徴とする請求項１から３のいずれか１項に記載の輻輳パス特定方法。
5. 第７のステップについて、
   前記２つのパスの非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成し、
   前記デンドログラムの非類似度に応じて、パスを分類する
   ことを特徴とする請求項４に記載の輻輳パス特定方法。
6. 複数の計測端末間のパスにおける遅延変動時間に基づいて、輻輳パスを分類する管理装置において、
   前記計測端末によって受信された計測パケットに基づいて、該計測端末から、送信元アドレス、受信端末アドレス、送信時刻及び受信時刻を含む計測情報を受信する計測情報収集手段と、
   ２つのパスについて、送信時刻と受信時刻との間の転送時間の少なくとも一部が重なるパケットペアの集合を抽出する計測情報抽出手段と、
   抽出されたパケットペアについて、前記計測情報の送信時刻及び受信時刻から各パケットの遅延時間を算出する遅延時間算出手段と、
   パス毎に、所定期間における複数の前記遅延時間から、遅延変動時間を算出する遅延変動算出手段と、
   抽出された前記パケットペアの集合の中から、ワーピングコストを最小とする最小ワーピングパスを導出する最小ワーピングパス導出手段と、
   前記最小ワーピングパスにおける２つのパスの間の非類似度を算出する非類似度算出手段と、
   クラスタリングによって非輻輳パスの集合と輻輳パスの集合とを特定する輻輳パス特定手段と
   を有することを特徴とする管理装置。
7. パス毎に、所定期間における複数の計測情報のパケット遅延の中で最小遅延時間を導出する最小遅延時間導出手段を更に有し、
   前記遅延変動算出手段は、前記計測情報毎に、当該遅延時間と前記最小遅延時間との差を遅延変動時間として算出する
   ことを特徴とする請求項６に記載の管理装置。
8. 前記遅延変動算出手段から出力された当該遅延時間と前記最小遅延時間との差の最大値が、所定閾値以下となる場合は、当該パスを非輻輳パスとして特定する非輻輳パスフィルタ手段を更に有することを特徴とする請求項７に記載の管理装置。
9. 前記輻輳パス特定手段は、２つのパスのパケットペア毎に、遅延変動時間の差の二乗に対する、それらの平均値との比を算出し、それら比の和により算出される非類似度の低い２つのパスのペアを導出することを特徴とする請求項６から８のいずれか１項に記載の管理装置。
10. 前記輻輳パス特定手段は、
    前記２つのパスの非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するデンドログラム作成手段と、
    前記デンドログラムの非類似度に応じて、パスを分類するパス分類手段と
    を更に有することを特徴とする請求項９に記載の管理装置。
11. 複数の計測端末間のパスにおける遅延変動時間に基づいて、輻輳パスを分類する管理装置に搭載されたコンピュータを機能させるプログラムにおいて、
    前記計測端末によって受信された計測パケットに基づいて、該計測端末から、送信元アドレス、受信端末アドレス、送信時刻及び受信時刻を含む計測情報を受信する計測情報収集手段と、
    ２つのパスについて、送信時刻と受信時刻との間の転送時間の少なくとも一部が重なるパケットペアの集合を抽出する計測情報抽出手段と、
    抽出されたパケットペアについて、前記計測情報の送信時刻及び受信時刻から各パケットの遅延時間を算出する遅延時間算出手段と、
    パス毎に、所定期間における複数の前記遅延時間から、遅延変動時間を算出する遅延変動算出手段と、
    抽出された前記パケットペアの集合の中から、ワーピングコストを最小とする最小ワーピングパスを導出する最小ワーピングパス導出手段と、
    前記最小ワーピングパスにおける２つのパスの間の非類似度を算出する非類似度算出手段と、
    クラスタリングによって非輻輳パスの集合と輻輳パスの集合とを特定する輻輳パス特定手段と
    してコンピュータを機能させることを特徴とする管理装置用のプログラム。
12. パス毎に、所定期間における複数の計測情報のパケット遅延の中で最小遅延時間を導出する最小遅延時間導出手段を更に有し、
    前記遅延変動算出手段は、前記計測情報毎に、当該遅延時間と前記最小遅延時間との差を遅延変動時間として算出する
    ようにコンピュータを機能させることを特徴とする請求項９に記載の管理装置用のプログラム。
13. 前記遅延変動算出手段から出力された当該遅延時間と前記最小遅延時間との差の最大値が、所定閾値以下となる場合は、当該パスを非輻輳パスとして特定する非輻輳パスフィルタ手段を更に有するようにコンピュータを機能させることを特徴とする請求項１２に記載の管理装置用のプログラム。
14. 前記輻輳パス特定手段は、２つのパスのパケットペア毎に、遅延変動時間の差の二乗に対する、それらの平均値との比を算出し、それら比の和により算出される非類似度の低い２つのパスのペアを導出するようにコンピュータを機能させることを特徴とする請求項１１から１３のいずれか１項に記載の管理装置用のプログラム。
15. 前記輻輳パス特定手段は、
    前記２つのパスの非類似度の低いペアから順に、ウォード法を適用してデンドログラムを作成するデンドログラム作成手段と、
    前記デンドログラムの非類似度に応じて、パスを分類するパス分類手段と
    してコンピュータを機能させることを特徴とする請求項１４に記載の管理装置用のプログラム。

Images