JP4449665B2 - ネットワークにおける輻輳区間を推定する方法、プログラム、サーバ及びシステム - Google Patents

Description

本発明は、ネットワークにおける輻輳区間を推定する方法、プログラム、サーバ及びシステムに関する。特に、パストポロジが動的に変化するか又は既知でないネットワークに関する。

パストポロジが動的に変化するか又は既知でないネットワークにおいて輻輳区間を推定するには、複数のパスに対するアクティブ計測によってパケット損失率又は遅延等の品質データを計測することを要する。「パス」とは、測定対象ネットワークを介して通信する端末間の経路をいう。パス上には、例えばルータのような複数の中継ノードが存在する。「アクティブ計測」とは、一方の端末からネットワークを介して試験用パケットを他方の端末へ送信し、その試験用パケットのパケット損失率及び／又は遅延等からパスの品質を測定することをいう。通常、アクティブ計測において、試験用パケットを送信する端末をソース、試験用パケットを受信する端末をデスティネーションと称す。

従来における輻輳区間の推定方法として、１つの端末から複数の端末に対するパケット損失率の計測、即ち、シングルソース・マルチデスティネーション間計測方法がある（例えば非特許文献１参照）。この方法は、木構造となるパストポロジを対象として推定される。

また、任意の端末から任意の端末に対するパケット損失率の計測、即ち、マルチソース・マルチデスティネーション間計測方法もある（例えば非特許文献２参照）。この方法では、任意のパストポロジに対して適用することができる。

更に、単一パスにおいて、各ルータまでのＲＴＴ(Round Trip Time)を計測し、その差分異によりボトルネックとなるリンクを推定する方法もある（例えば非特許文献３参照）。

Nick Duffield, "Simple Network Performance Tomography" Proc.ACM SIGCOM Internet Measurement Conference, 2003年10月 M.Tsuru, T.Takine, Y.Oie "Inferring Link Characteristics from End-to-End Path Measurements", Proc. Of IEEICC 2001, 2001年7月 A.Akella, S.Seshan, A.Shaikh, "An Empirical Evaluation of Wide-Area Internet Bottlenecks" Proc. Of ACM Internet Measurement Conference 2003(IMC 2003), 2003年10月

しかしながら、シングルソース・マルチデスティネーション間計測方法では、ソース端末が輻輳区間に近い場合、多数のパスの品質が同時に劣化し、多数の輻輳区間が推定されるという問題が生じる。これに対し、マルチソース・マルチデスティネーション間計測方法では、このような問題は生じないが、パストポロジが既知であることを前提としており、パストポロジが動的に変化する場合には適用が難しい。また、ＲＴＴ計測方法は、１回の計測において、数Ｍｂｐｓのテストパケットを数１０秒から数分間送信し、ネットワークに大きな負荷を与えるという問題がある。特に、複数のパスの一部が、同一中継ノードを経由している場合には、同時に計測することができないという問題もある。更に、従来の計測方法によれば、パス間の品質の相関を考慮することはなく、劣悪品質の区間の全てが輻輳区間と推定される。

従って、本発明は、パストポロジが動的に変化するか又は既知でないネットワークについて、そのネットワークに多大な負荷を与えることなく、輻輳区間を推定する方法、プログラム、サーバ及びシステムを提供することを目的とする。

本発明の方法によれば、
ネットワーク全体について、端末間でアクティブ計測された当該パスの品質データと、当該パス上にある１つ以上の中継ノードのリストとを収集する第１のステップと、
端末間毎のパスを並べた第１の軸と、該パス上にある１つ以上の中継ノードによって分割された区間を並べた第２の軸とを有するテーブルを構成し、当該パス上の区間に相当する要素に品質データを入力する第２のステップと、
テーブルの第１の軸に並べたパスのいずれか１つのパスをターゲットパスとして指定する第３のステップと、
ターゲットパスに対して劣悪品質を示す区間であって、且つ、当該区間を含むパスの全てが劣悪品質を示す１つ以上の区間を、ターゲット区間として指定する第４のステップと、
ターゲットパス以外のパスであって、且つ、１つ以上のターゲット区間に劣化品質データを含む１つ以上のパスを、テストパスとして指定する第５のステップと、
テストパス毎に、該テストパスの品質データとターゲットパスの品質データとの差分から、ターゲットパスに対する相関度を導出する第６のステップと、
所定条件によって相関度が高いと判断された高相関テストパスを選択する第７のステップと、
ターゲット区間毎に高相関テストパスの個数を算出し、該個数が最も多い区間に輻輳があると決定する第８のステップと、
既に指定されたターゲットパス及び高相関テストパス以外のパスをターゲットパスとして指定し、第４から第８のステップを繰り返すことを特徴とする。

また、本発明の方法における他の実施形態によれば、第７のステップについて、所定条件は、ターゲットパスの過去の品質データとテストパスの過去の品質データとの差分が所定閾値以内であって、且つ、ターゲットパスの最新の品質データとテストパスの最新の品質データとの差分が所定閾値以内である場合に、相関度が高いと判断されることも好ましい。

更に、本発明の方法における他の実施形態によれば、品質データはパケット損失率であって、該パケット損失率が所定値以上の場合に劣化品質を示すと判断されることも好ましい。

更に、本発明の方法における他の実施形態によれば、テーブルの要素には、品質データに対して１つ以上の所定の品質判定閾値によって決定された品質ポイントが入力されることも好ましい。

本発明のプログラムによれば、
ネットワーク全体について、端末間でアクティブ計測された当該パスの品質データと、当該パス上にある１つ以上の中継ノードのリストとを収集する第１のステップと、
端末間毎のパスを並べた第１の軸と、該パス上にある１つ以上の中継ノードによって分割された区間を並べた第２の軸とを有するテーブルを構成し、当該パス上の区間に相当する要素に品質データを入力する第２のステップと、
テーブルの第１の軸に並べたパスのいずれか１つのパスをターゲットパスとして指定する第３のステップと、
ターゲットパスに対して劣悪品質を示す区間であって、且つ、当該区間を含むパスの全てが劣悪品質を示す１つ以上の区間を、ターゲット区間として指定する第４のステップと、
ターゲットパス以外のパスであって、且つ、１つ以上のターゲット区間に劣化品質データを含む１つ以上のパスを、テストパスとして指定する第５のステップと、
テストパス毎に、該テストパスの品質データとターゲットパスの品質データとの差分から、ターゲットパスに対する相関度を導出する第６のステップと、
所定条件によって相関度が高いと判断された高相関テストパスを選択する第７のステップと、
ターゲット区間毎に高相関テストパスの個数を算出し、該個数が最も多い区間に輻輳があると決定する第８のステップと、
既に指定されたターゲットパス及び高相関テストパス以外のパスをターゲットパスとして指定し、第４から第８のステップを繰り返す
ようにコンピュータを実行させることを特徴とする。

また、本発明のプログラムにおける他の実施形態によれば、第７のステップについて、所定条件は、ターゲットパスの過去の品質データとテストパスの過去の品質データとの差分が所定閾値以内であって、且つ、ターゲットパスの最新の品質データとテストパスの最新の品質データとの差分が所定閾値以内である場合に、相関度が高いと判断されるように実行されることも好ましい。

更に、本発明のプログラムにおける他の実施形態によれば、品質データはパケット損失率であって、該パケット損失率が所定値以上の場合に劣化品質を示すと判断されるように実行されることも好ましい。

更に、本発明のプログラムにおける他の実施形態によれば、テーブルの要素には、品質データに対して１つ以上の所定の品質判定閾値によって決定された品質ポイントが入力されるように実行されることも好ましい。

本発明の計測サーバによれば、
端末間のパスにおける品質データと、該パス上にある中継ノードのリストとを、端末から受信するするデータ収集手段と、
品質データ及び中継ノードリストを記憶する記憶手段と、
品質データ及び中継ノードリストに基づいてネットワークにおける輻輳区間を推定する輻輳区間推定手段とを有し、
輻輳区間推定手段は、
ネットワーク全体について、端末間でアクティブ計測された当該パスの品質データと、当該パス上にある１つ以上の中継ノードのリストとを収集し、
端末間毎のパスを並べた第１の軸と、該パス上にある１つ以上の中継ノードによって分割された区間を並べた第２の軸とを有するテーブルを構成し、当該パス上の区間に相当する要素に品質データを入力し、
テーブルの第１の軸に並べたパスのいずれか１つのパスをターゲットパスとして指定し、
ターゲットパスに対して劣悪品質を示す区間であって、且つ、当該区間を含むパスの全てが劣悪品質を示す１つ以上の区間を、ターゲット区間として指定し、
ターゲットパス以外のパスであって、且つ、１つ以上のターゲット区間に劣化品質データを含む１つ以上のパスを、テストパスとして指定し、
テストパス毎に、該テストパスの品質データとターゲットパスの品質データとの差分から、ターゲットパスに対する相関度を導出し、
所定条件によって相関度が高いと判断された高相関テストパスを選択し、
ターゲット区間毎に高相関テストパスの個数を算出し、該個数が最も多い区間に輻輳があると決定し、
既に指定されたターゲットパス及び高相関テストパス以外のパスをターゲットパスとして指定し、第４から第８のステップを繰り返す
ように機能することを特徴とする。

本発明の計測サーバにおける他の実施形態によれば、所定条件は、ターゲットパスの過去の品質データとテストパスの過去の品質データとの差分が所定閾値以内であって、且つ、ターゲットパスの最新の品質データとテストパスの最新の品質データとの差分が所定閾値以内である場合に、相関度が高いと判断されることも好ましい。

また、本発明の計測サーバにおける他の実施形態によれば、品質データはパケット損失率であって、該パケット損失率が所定値以上の場合に劣化品質を示すと判断されることも好ましい。

更に、本発明の計測サーバにおける他の実施形態によれば、テーブルの要素には、品質データに対して１つ以上の所定の品質判定閾値によって決定された品質ポイントが入力されることも好ましい。

本発明の計測システムによれば、測定対象となるネットワークと、該ネットワークに相互に接続された複数の端末と、前述された計測サーバとを有する計測システムであって、
端末は、
所定周期毎に、相手端末との間のパスにおける品質データをアクティブ計測するアクティブ計測手段と、
所定周期毎に、パス上にある中継ノードリストを取得する中継ノードリスト取得手段と、
品質データ及び中継ノードリストを計測サーバへ送信するデータ送信手段と
を有することを特徴とする。

本発明によれば、パストポロジが動的に変化するか又は既知でないネットワークについて、そのネットワークに多大な負荷を与えることなく、輻輳区間を推定することができる。特に、本発明によれば、時間変動に基づくパス間の品質の相関を考慮するために、結果的に推定される輻輳区間が減少し、輻輳区間推定のための精度が向上する。

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

図１は、本発明におけるシステム構成図である。

図１によれば、測定対象となるネットワーク２に、複数の端末１及び計測サーバ５が接続されている。ネットワーク２は、パケットの経路制御のための中継ノード３が複数存在する。ネットワークにおいては、複数の端末間の複数のパスが、ある区間について同一の中継ノードを経由するような、パスの合流又は分岐が存在し、これらパスの合流又は分岐により区切られたパスの一部を「区間」と称す。

図２は、パスが区間に分割されていることを表す説明図である。

図２によれば、ソース端末１１からデスティネーション端末１２へのパス４１は、中継ノード３１〜３５を介して構成される。同様に、端末１３から端末１４へのパス４２は、中継ノード３６、３２、３３及び３７を介して構成される。ここで、パス４１から見た場合、パス４２が中継ノード３２で合流し、中継ノード３３で分岐しているため、以下のように区間が分割される。
（区間１）端末１１から中継ノード３１まで
（区間２）中継ノード３２から中継ノード３３まで
（区間３）中継ノード３４から計測端末１２まで
同様に、パス４２も、区間４、区間２及び区間５に分割されている。

端末１は、記憶部１０１、アクティブ計測部１０２、中継ノードリスト取得部１０３及びデータ送信部１０４を有する。

アクティブ計測部１０２は、所定周期毎に、相手端末との間でアクティブ計測をし、品質データを取得する。アクティブ計測データは、ソース端末のＩＰアドレスとデスティネーション端末のＩＰアドレスとの組を表す送受信組と、計測時刻(tm_o)と、パケット損失率等の品質データとを含む。ここでは、品質データとして、パケット損失率のみを用いているが、遅延等の他の品質データを含めることも可能である。

表１は、測定されたアクティブ計測データである。

中継ノードリスト取得部１０３は、所定の周期毎に、相手端末までのパス上に存在する全中継ノードにおける、その並び順と共に、アドレス等の中継ノード識別情報を収集する。そのデータは、送受信組と、中継ノードリストを取得した時刻(tr_o)と、パス上の中継ノードを順に並べた中継ノードリストとを有する。この中継ノードリストデータは、記憶部１０１に保存され、データ送信部１０４を用いて計測サーバ５に送信される。例えば、ＩＰパケットのＴＴＬ(Time to Live)フィールドを利用した”traceroute”コマンド等を用いて、中継ノードリストデータが取得される。

表２は、測定された中継ノードリストである。

記憶部１０１には、計測相手である端末のアドレスと、アクティブ計測を行う周期と、中継ノードリスト取得を行う周期と、中継ノードリストデータと、アクティブ計測データとが保存される。

データ送信部１０４は、アクティブ計測データ及び中継ノードリストを、計測サーバ５に送信する。

次に、計測サーバ５は、データ収集部５０１、輻輳区間推定部５０２及び記憶部５０３を有する。

データ収集部５０１は、各計測端末からアクティブ計測データ及び中継ノードリストデータを受信する。計測サーバ５からのポーリングに基づく方法であってもよいし、各計測端末が自律的に送信する方法でもよい。

記憶部５０３は、データ収集対象である計測端末１のアドレスの他、後述する各種テーブルを保持する。また、品質判定閾値、マッピングテーブル更新周期、前回のマッピングテーブル更新時刻等の情報も保持する。マッピングテーブル更新周期は、各計測端末の計測結果を、できるだけ早くマッピングテーブルに反映させるため、各計測端末での計測周期と同じに設定することが望ましい。

輻輳区間推定部５０２は、記憶部５０３のテーブルを用いて計測対象ネットワークにおける輻輳区間を推定する。

図３は、本発明における輻輳区間推定部５０２のフローチャートである。以下では、フローチャートのシーケンス番号に基づいて説明する。

（Ｓ３０１）最初に、ネットワーク全体について、端末間でアクティブ計測された当該パスの品質データと、当該パス上にある１つ以上の中継ノードのリストとを収集する。

表３は、各端末から受信したアクティブ計測テーブルである。

表４は、各端末から受信した中継ノードリストテーブルである。

（Ｓ３０２）次に、マッピングテーブル作成更新処理を行う。ここでは、予め種々のテーブルを作成しておく必要がある。

表５は、区間テーブルである。区間テーブルは、計測対象ネットワークにおけるパスの分岐又は合流によって、そのパス上にある１つ以上の中継ノードを含む区間に対応付けられた区間ＩＤと、その区間上の中継ノードリストを表す。

表６は、パステーブルである。

パステーブルは、列として、パスＩＤと、中継ノードリストと、送受信組と、安定度と、時刻(tr_d)と、区間リストと、過去損失率と、最新損失率と、品質ポイントと、時刻(tm_d)とを有する。パスＩＤは、送信側端末のＩＰアドレスと受信側端末のＩＰアドレスとからなる送受信組毎に対応付けられたものであり、新規な送受信組が追加される度に指定される。時刻(tr_d)は、アクティブ計測テーブルから参照されたものである。安定度は、所定の期間内に、新規に作成されたパス又は経由する中継ノードが変更されたパスには「０」、所定の期間以前から変更なく存在しているパスに対しては「１」が付与され、中継ノードが安定したパスに対してのみ区間推定をするために付与されたものである。

区間リストは、当該パス上に存在する１つ以上の区間ＩＤを表しており、区間テーブルの区間ＩＤと対応付けられている。過去損失率及び最新損失率は、時間変動に伴うパケット損失率であり、パスの相関度を導出するために用いられる。品質ポイントは、予め記憶された品質判定閾値によって最新損失率を判定した値である。表６によれば、第１の品質判定閾値としてパケット損失率１％と、第２の品質判定閾値としてパケット損失率２％とによって判定されている。時刻(tm_d)は、中継ノードリストテーブルから参照されたものである。
品質ポイント０：最新損失率が１％未満の場合
品質ポイント１：最新損失率が１％以上２％未満の場合
品質ポイント２：最新損失率が２％以上の場合

マッピングテーブル作成更新処理は、表７のようなマッピングテーブルを構成する。

マッピングテーブルは、端末間毎のパスを並べた縦軸と、計測対象ネットワークにおける区間を並べた横軸とから構成される。そして、そのテーブルの要素に品質データが入力される。ここでは、品質判定閾値を用いた品質ポイントが入力されている。尚、マッピングテーブル作成更新処理の具体的な動作については、後述する。

（Ｓ３０３）マッピングテーブルの縦軸に並べたパスのいずれか１つのパスをターゲットパスとして指定する。

表８は、Ｓ３０３に相当するマッピングテーブルである。表８によれば、最初にパスＩＤ１をターゲットパスに指定したとする。

（Ｓ３０４）ターゲットパス（パスＩＤ１）について劣悪品質ポイントを示す１つ以上の区間を選択する。表８によれば、ターゲットパス（パスＩＤ１）について劣悪品質ポイント２を示す区間１、２、３、４、５、１５、１６及び１７が選択される。次に、ターゲットパス（パスＩＤ１）について劣悪品質ポイントを示す区間において、その区間を含むパスの全てが劣悪品質ポイントを示す区間を、ターゲット区間として指定する。

表９は、Ｓ３０４に相当するマッピングテーブルである。

表９によれば、ターゲットパス（パスＩＤ１）について劣悪品質ポイント２を示す区間１、２、３、４、５、１５、１６及び１７において、その区間を含むパスの全てが劣悪品質ポイントを示す区間１、２、５、１５及び１６を、ターゲット区間として指定する。

（Ｓ３０５）ターゲットパス以外の１つ以上のパスであって、且つ、ターゲット区間に劣化品質ポイントを含むパスを、テストパスとして指定する。表９によれば、ターゲットパス以外のパスＩＤ２〜９について、ターゲット区間に劣化品質データを含むパスＩＤ２、５、６及び９が順次指定される。

（Ｓ３０６）テストパス毎（パスＩＤ＝２、５、６，９）に、そのテストパスの品質データとターゲットパスの品質データとの差分から、ターゲットパスに対する相関度を導出する。例えば、品質データはパケット損失率であって、過去及び現在のパケット損失率を比較することによって相関度を導出することができる。

例えば、所定条件として、ターゲットパスの過去の劣化品質データとテストパスの過去の劣化品質データとの差分が所定閾値以内であって、ターゲットパスの最新の劣化品質データとテストパスの最新の劣化品質データとの差分が所定閾値以内である場合、相関度が高いと決定することができる。

（Ｓ３０７）所定条件によってその相関度が高いと判断された高相関テストパスを選択する。表９について、例えばテストパスとなるパスＩＤ２、５、６及び９の中で、ターゲットパスと相関度が高いパスとしてパスＩＤ２及び５が高相関テストパスとして導出されたとする。

図４は、相関度を説明するグラフである。

図４のグラフは、パケット損失率を縦軸に、時間を横軸に構成されており、ターゲットパスとテストパスとの時間変動に伴うパケット損失率を表す。ここで、最新時間tmに対して最新損失率はＰ（tm）で表され、過去時間tm−ΔTmに対して過去損失率はＰ（tm−ΔTm）で表される。そして、ターゲットパスとテストパスとについて、最新損失率差分をΔＰ（tm）で表し、過去損失率差分をΔＰ（tm−ΔTm）で表す。ここで、最新損失率差分ΔＰ（tm）が所定閾値Ｄｐ（例えば０．５％）以下であって、且つ、過去損失率差分ΔＰ（tm−ΔTm）が所定閾値Ｄｐ以下であったならば、相関が高いと判断される。

図５は、複数のパスを図４のグラフのように並べたグラフである。図５によれば、所定の時間におけるパス間の相関が明らかに理解できる。

（Ｓ３０８）ターゲット区間について高相関テストパスの個数を算出し、該パスの個数が最も多い区間に輻輳があると決定する。表９によれば、ターゲット区間に対する高相関テストパスの個数は、以下のようになる。
区間ＩＤ１に対する高相関テストパスの個数 ：２
区間ＩＤ２に対する高相関テストパスの個数 ：０
区間ＩＤ５に対する高相関テストパスの個数 ：１
区間ＩＤ１５に対する高相関テストパスの個数 ：１
区間ＩＤ５に対する高相関テストパスの個数 ：０
そうすると、高相関テストパスの個数が最も多い区間は区間ＩＤ１であり、区間ＩＤ１に輻輳があると決定される。

（Ｓ３０９）既に指定されたターゲットパス及び高相関テストパス以外のパスをターゲットパスとして、処理を繰り返す。表９によれば、ターゲットパスであるパスＩＤ１と、高相関テストパスであるパスＩＤ２及び５とは、次のターゲットパスとして指定されない。

表１０は、更なるＳ３０４におけるマッピングテーブルである。

表１０によれば、ターゲットパスであるパスＩＤ１と、高相関テストパスであるパスＩＤ２及び５と以外のパスであるパスＩＤ３がターゲットパスに指定されたとする。

（Ｓ３０４）ターゲットパス（パスＩＤ３）について劣悪品質ポイントを示す１つ以上の区間を選択する。表１０によれば、ターゲットパス（パスＩＤ３）について劣悪品質ポイント２を示す区間７、１０、１１、１２、１４及び１８が選択される。次に、ターゲットパス（パスＩＤ３）について劣悪品質ポイントを示す区間において、その区間を含むパスの全てが劣悪品質ポイントを示す区間を、ターゲット区間として指定する。

表１１は、更なるＳ３０４におけるマッピングテーブルである。

表１１によれば、ターゲットパス（パスＩＤ３）について劣悪品質ポイント２を示す区間７、１０、１１、１２、１４及び１８において、当該区間を含むパスの全てが劣悪品質ポイントを示す区間１０、１１及び１２を、ターゲット区間として指定する。

（Ｓ３０５）ターゲットパス以外の１つ以上のパスであって、且つ、ターゲット区間に劣化品質ポイントを含むパスを、テストパスとして指定する。表９によれば、ターゲットパスであるパスＩＤ３以外のパスＩＤ１、２、４〜９について、ターゲット区間に劣化品質データを含むパスＩＤ６及び９が順次指定される。
（Ｓ３０６）テストパス毎（パスＩＤ＝６、９）に、そのテストパスの品質データとターゲットパスの品質データとの差分から、ターゲットパスに対する相関度を導出する。
（Ｓ３０７）前述と同様に、所定条件によって該相関度が高いと判断された高相関テストパスを選択する。表１１について、例えばテストパスとなるパスＩＤ６及び９の両方とも、ターゲットパスと相関度が高い高相関テストパスとして導出されたとする。

（Ｓ３０８）ターゲット区間について高相関テストパスの個数を算出し、該パスの個数が最も多い区間に輻輳があると決定する。表１１によれば、ターゲット区間に対する高相関テストパスの個数は、以下のようになる。
区間ＩＤ１０に対する高相関テストパスの個数 ：１
区間ＩＤ１１に対する高相関テストパスの個数 ：２
区間ＩＤ１２に対する高相関テストパスの個数 ：２
そうすると、高相関テストパスの個数が最も多い区間は区間ＩＤ１１及び１２であり、区間ＩＤ１１及び１２に輻輳があると決定される。

表１２は、更なるＳ３０８におけるマッピングテーブルである。

（Ｓ３０９）更に、既に指定されたターゲットパス及び高相関テストパス以外のパスをターゲットパスとして、処理を繰り返す。表１２によれば、ターゲットパスであったパスＩＤ１及び３と、高相関テストパスであったパスＩＤ２、５、６及び９は、次のターゲットパスとして指定されない。次のターゲットパスの候補としては、例えば、パスＩＤ４、７及び８が選択される。しかしながら、パスＩＤ４、７及び８には、劣化品質データを示す品質ポイントが入力されていないので、輻輳区間の検出のための処理を終了する。

最後に、マッピングテーブル作成更新処理について説明する。この処理は、同一出願人による特願２００４−０８８８８８号に記載された方法と全く同様である。

図６は、図３のマッピングテーブル作成更新処理（Ｓ３０２）を表すフローチャートである。以下では、テーブルの各行をレコードと称し、各列をフィールドと称する。

（Ｓ６０１）アクティブ計測テーブルのレコードが処理対象レコードである。未処理レコードがある場合、処理対象レコード毎にＳ６０７までの処理を繰り返す。
（Ｓ６０２）パステーブルを参照し、処理対象レコードの送受信組と同一の送受信組を有するレコードが、パステーブルに存在するか否かを調べる。存在しない場合は、新規のパスが作成されたことを意味し、区間作成処理（Ｓ６０３）へ移行する。存在する場合、同一の送受信組を有するパステーブルレコードを抽出し、Ｓ６０４へ移行する。
（Ｓ６０４）処理対象レコードの時刻（tm_o）と、抽出したパステーブルレコードの時刻（tr_d）とを比較する。tm_oがtr_d以上である場合、即ち、処理対象レコードがパステーブルレコードより新しい場合、中継ノードリストテーブルのデータをパステーブルに反映させるために、区間作成処理（Ｓ６０３）へ移行する。
（Ｓ６０５）パステーブルの品質フィールドを更新する。品質フィールドの更新は、処理対象レコードのパケット損失率によって導出された品質ポイントを設定する。このとき、処理対象レコードの時刻（tm_o）を、当該パステーブルレコードの時刻（tm_d）に設定する。
（Ｓ６０６）前回のマッピングテーブル更新時刻と現在の時刻を比較し、差分がマッピングテーブル更新周期以上であれば、マッピングテーブル更新処理（Ｓ６０７）へ移行する。
（Ｓ６０９）全ての未処理レコードを処理するまでＳ６０２〜Ｓ６０７を繰り返す。

図７は、図６の区間作成処理（Ｓ６０３）を表すフローチャートである。

（Ｓ７０１）図６の区間作成処理における処理対象レコードの送受信組と同一の送受信組を有する中継ノードリストテーブルのレコードが処理対象となる。処理対象レコードの送受信組と同一の送受信組を有するレコードが、パステーブルに存在するか否かを調べる。存在しない場合は、新規レコードであり、Ｓ７０２へ移行する。存在する場合は、Ｓ７０３へ移行する。
（Ｓ７０２）処理対象レコードを、パステーブルの新規レコードとして追加する。新規レコードのパスＩＤには、他のレコードと重複しないパスＩＤ値が割り当てられる。また、新規レコードの安定度は０とする。更に、新たに割り当てたパスＩＤ値を、変更パスリストに追加する。
（Ｓ７０３）処理対象レコードの送受信組と同一の送受信組を有するパステーブルレコードを抽出する。次に、処理対象レコードの中継ノードリストと、抽出したパステーブルレコードの中継ノードリストが完全に一致しているか否かを調べる。完全に一致している場合は、既存パスであって変更もないために、抽出したパステーブルレコードの安定度を１とし、時刻（tr_d）には、処理対象レコードの時刻（tr_o）を設定する（Ｓ７０５）。完全に一致していない場合は、パス上の中継ノードが変更されており、Ｓ７０４へ移行する。
（Ｓ７０４）抽出したパステーブルレコードのパスＩＤを、変更パスリストに追加する。次に、中継ノードテーブルを参照し、抽出したパステーブルレコードの中継ノードリストフィールドの各中継ノードを経由するパスＩＤを、変更パスリストに追加する。その後、抽出したパステーブルレコードの中継ノードリスト及び時刻を、処理対象レコードの該当するフィールド値に更新する。また、抽出したパステーブルレコードの安定度には０を設定する。
（Ｓ７０６）Ｓ７０２において追加したパステーブルのレコード又はＳ７０４で変更したパステーブルのレコードが処理対象レコードである。処理対象レコードの中継ノードリストフィールドの中継ノードが、中継ノードテーブルに存在するか否かを確認する。存在する場合は、中継ノードテーブルから中継ノードを経由しているパスＩＤ値を、変更パスリストに追加する。存在しない場合は、中継ノードを、新規レコードとして中継ノードテーブルに追加する。追加した中継ノードテーブルレコードのパスＩＤには、処理対象レコードのパスＩＤを設定する。

（Ｓ７０７）変更パスリストの各パスが処理対象となる。未処理パスが無い場合は終了する。
（Ｓ７０８）未処理パスがある場合は、処理対象パスを選択する。
（Ｓ７０９）処理対象パス上の中継ノードリストを、パステーブルの中継ノードリストフィールドから抽出する。次に、中継ノードリストの各中継ノードを経由するパスＩＤを、中継ノードテーブルを参照して求める。中継ノードリストの各中継ノードを順に並べ、隣り合う中継ノードを経由しているパスＩＤが、完全に一致するか否かを調べる。完全に一致する場合は、隣り合う中継ノードは同じ区間に属することを意味し、完全に一致しない場合は、パスの分岐又は合流があり、違う区間に属することを意味する。これら操作によって、パス上にある区間の境界を認識でき、パスを区間に分割することができる。また、同じ区間に属する中継ノードリストも抽出することができる。

Ｓ７０９の処理を、図２を例にして説明する。処理対象パスとしてパス４１が選択されている。中継ノードリストして、中継ノード３１〜３５が抽出されている。中継ノード３１、３４及び３５を経由するパスＩＤは、パス４１のみである。中継ノード３２及び中継ノード３３を経由するパスＩＤは、パス４１及びパス４２である。従って、隣り合う中継ノードで、経由するパスＩＤが完全に一致しない、中継ノード３１−中継ノード３２及び中継ノード３３−中継ノード３４は、それぞれ、別の区間に属するものと判断することができる。その他は隣り合う中継ノードで、経由するパスＩＤが完全に一致する中継であるため、同じ区間に属するものと判断することができる。よって、パス４１は、区間１、２、３の３つから成ると判断でき、各区間の中継ノードリストも抽出できる。

（Ｓ７１０）Ｓ７０９で分割した各区間に属する中継ノードリストと、同一の中継ノードリストを有するレコードが、区間テーブルに存在するか否かを調べる。存在しない場合は、区間ＩＤを割当て、区間テーブルに新規レコードとして登録する。次に、処理対象パス上の区間ＩＤを区間テーブルで調べ、対応するパステーブルレコードの区間リストを更新する。

図８は、図６のマッピングテーブル更新処理（Ｓ６０７）を表すフローチャートである。

（Ｓ８０１）パステーブルのレコードを処理対象とする。未処理レコードがある場合は、処理対象レコードを１つ選択する。未処理レコードがない場合は終了する。
（Ｓ８０２）処理対象レコードの時刻（tr_d）と、時刻（tm_d）とを調べる。マッピングテーブル更新周期をΔＴとしたとき、tm_d−tr_d＞ΔＴである場合、即ち、処理対象レコードの中継ノードリストの収集時刻が、品質の測定時刻より、マッピングテーブル更新周期以上に、古いものである場合には、処理対象レコードを、マッピングテーブル更新には使用せずＳ８０１に戻る。古い中継ノードリストを有するレコードを、マッピングテーブル更新には使用しないことで、推定される輻輳区間に対する信頼性を高めることができる。
（Ｓ８０３）処理対象レコードの安定度を参照し、安定度０の場合は、処理対象レコードをマッピングテーブル更新に使用せず、Ｓ８０１に戻る。安定度０を有するレコードは、区間作成処理において、新規パス又変更パスと認識されたものであり、安定したパスを処理対象とすることで、推定される輻輳区間に対する信頼性を高めることができる。
（Ｓ８０４）処理対象レコードのパスＩＤが、マッピングテーブルのレコードに既に存在しているか否かを調べる。存在しない場合は、新規レコードを追加する。次に、処理対象レコードの区間リストの区間ＩＤが、マッピングテーブルのフィールドに存在しているか否かを調べる。存在しない区間ＩＤがあれば、新規フィールドの追加を行う。

処理対象レコードのパスＩＤと同一のパスＩＤを有するマッピングテーブルレコードを抽出する。抽出したマッピングテーブルレコードのフィールドの中で、処理対象レコードの区間リストの区間ＩＤに対応するフィールドに、処理対象レコードの品質フィールド値を設定し、残りのフィールドの値はヌル値に設定する。

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

本発明におけるシステム構成図である。 パスが区間に分割されていることを表す説明図である。 本発明におけるフローチャートである。 相関度を説明するグラフである。 複数のパスを図４のグラフのように並べたグラフである。 図３のマッピングテーブル作成更新処理（Ｓ３０２）を表すフローチャートである。 図６の区間作成処理（Ｓ６０３）を表すフローチャートである。 図６のマッピングテーブル更新処理（Ｓ６０７）を表すフローチャートである。

符号の説明

１、１１〜１４ 計測端末
１０１ 記憶部
１０２ アクティブ計測部
１０３ 中継ノードリスト取得部
１０４ データ送信部
２ 計測対象となるネットワーク
３、３１〜３７ 中継ノード
４１、４２ パス
５ 計測サーバ
５０１ データ収集部
５０２ 輻輳区間推定部
５０３ 記憶部

Claims (13)

1. 複数の端末が相互に通信可能なネットワークにおける輻輳区間を計測サーバが特定する方法であって、
   前記ネットワーク全体について、前記端末間でアクティブ計測された当該パスの品質データと、当該パス上にある１つ以上の中継ノードのリストとを収集する第１のステップと、
   前記端末間毎のパスを並べた第１の軸と、該パス上にある１つ以上の中継ノードによって分割された区間を並べた第２の軸とを有するテーブルを構成し、当該パス上の区間に相当する要素に前記品質データを入力する第２のステップと、
   前記テーブルの前記第１の軸に並べたパスのいずれか１つのパスをターゲットパスとして指定する第３のステップと、
   前記ターゲットパスに対して劣悪品質を示す区間であって、且つ、当該区間を含むパスの全てが劣悪品質を示す１つ以上の区間を、ターゲット区間として指定する第４のステップと、
   前記ターゲットパス以外のパスであって、且つ、１つ以上の前記ターゲット区間に劣化品質データを含む１つ以上のパスを、テストパスとして指定する第５のステップと、
   前記テストパス毎に、該テストパスの品質データと前記ターゲットパスの品質データとの差分から、前記ターゲットパスに対する相関度を導出する第６のステップと、
   所定条件によって前記相関度が高いと判断された高相関テストパスを選択する第７のステップと、
   前記ターゲット区間毎に前記高相関テストパスの個数を算出し、該個数が最も多い区間に輻輳があると決定する第８のステップと、
   既に指定されたターゲットパス及び高相関テストパス以外のパスを前記ターゲットパスとして指定し、前記第４から第８のステップを繰り返すことを特徴とする方法。
   
2. 前記第７のステップについて、前記所定条件は、前記ターゲットパスの過去の品質データと前記テストパスの過去の品質データとの差分が所定閾値以内であって、且つ、前記ターゲットパスの最新の品質データと前記テストパスの最新の品質データとの差分が所定閾値以内である場合に、前記相関度が高いと判断されることを特徴とする請求項１に記載の方法。
3. 前記品質データはパケット損失率であって、該パケット損失率所定値以上の場合に前記劣化品質を示すと判断されることを特徴とする請求項１又は２に記載の方法。
4. 前記テーブルの要素には、前記品質データに対して１つ以上の所定の品質判定閾値によって決定された品質ポイントが入力されることを特徴とする請求項３に記載の方法。
5. 複数の端末が相互に通信可能なネットワークにおける輻輳区間を特定するプログラムであって、
   前記ネットワーク全体について、前記端末間でアクティブ計測された当該パスの品質データと、当該パス上にある１つ以上の中継ノードのリストとを収集する第１のステップと、
   前記端末間毎のパスを並べた第１の軸と、該パス上にある１つ以上の中継ノードによって分割された区間を並べた第２の軸とを有するテーブルを構成し、当該パス上の区間に相当する要素に前記品質データを入力する第２のステップと、
   前記テーブルの前記第１の軸に並べたパスのいずれか１つのパスをターゲットパスとして指定する第３のステップと、
   前記ターゲットパスに対して劣悪品質を示す区間であって、且つ、当該区間を含むパスの全てが劣悪品質を示す１つ以上の区間を、ターゲット区間として指定する第４のステップと、
   前記ターゲットパス以外のパスであって、且つ、１つ以上の前記ターゲット区間に劣化品質データを含む１つ以上のパスを、テストパスとして指定する第５のステップと、
   前記テストパス毎に、該テストパスの品質データと前記ターゲットパスの品質データとの差分から、前記ターゲットパスに対する相関度を導出する第６のステップと、
   所定条件によって前記相関度が高いと判断された高相関テストパスを選択する第７のステップと、
   前記ターゲット区間毎に前記高相関テストパスの個数を算出し、該個数が最も多い区間に輻輳があると決定する第８のステップと、
   既に指定されたターゲットパス及び高相関テストパス以外のパスを前記ターゲットパスとして指定し、前記第４から第８のステップを繰り返す
   ようにコンピュータを実行させることを特徴とするプログラム。
6. 前記第７のステップについて、前記所定条件は、前記ターゲットパスの過去の品質データと前記テストパスの過去の品質データとの差分が所定閾値以内であって、且つ、前記ターゲットパスの最新の品質データと前記テストパスの最新の品質データとの差分が所定閾値以内である場合に、前記相関度が高いと判断されるように実行されることを特徴とする請求項５に記載のプログラム。
7. 前記品質データはパケット損失率であって、該パケット損失率が所定値以上の場合に前記劣化品質を示すと判断されるように実行されることを特徴とする請求項５又は６に記載のプログラム。
8. 前記テーブルの要素には、前記品質データに対して１つ以上の所定の品質判定閾値によって決定された品質ポイントが入力されるように実行されることを特徴とする請求項７に記載のプログラム。
9. 複数の端末が相互に通信可能なネットワークにおける輻輳区間を特定する計測サーバであって、
   端末間のパスにおける品質データと、該パス上にある中継ノードのリストとを、前記端末から受信するするデータ収集手段と、
   前記品質データ及び中継ノードリストを記憶する記憶手段と、
   前記品質データ及び中継ノードリストに基づいて前記ネットワークにおける輻輳区間を推定する輻輳区間推定手段とを有し、
   前記輻輳区間推定手段は、
   前記ネットワーク全体について、前記端末間でアクティブ計測された当該パスの品質データと、当該パス上にある１つ以上の中継ノードのリストとを収集し、
   前記端末間毎のパスを並べた第１の軸と、該パス上にある１つ以上の中継ノードによって分割された区間を並べた第２の軸とを有するテーブルを構成し、当該パス上の区間に相当する要素に前記品質データを入力し、
   前記テーブルの前記第１の軸に並べたパスのいずれか１つのパスをターゲットパスとして指定し、
   前記ターゲットパスに対して劣悪品質を示す区間であって、且つ、当該区間を含むパスの全てが劣悪品質を示す１つ以上の区間を、ターゲット区間として指定し、
   前記ターゲットパス以外のパスであって、且つ、１つ以上の前記ターゲット区間に劣化品質データを含む１つ以上のパスを、テストパスとして指定し、
   前記テストパス毎に、該テストパスの品質データと前記ターゲットパスの品質データとの差分から、前記ターゲットパスに対する相関度を導出し、
   所定条件によって前記相関度が高いと判断された高相関テストパスを選択し、
   前記ターゲット区間毎に前記高相関テストパスの個数を算出し、該個数が最も多い区間に輻輳があると決定し、
   既に指定されたターゲットパス及び高相関テストパス以外のパスを前記ターゲットパスとして指定し、前記ターゲット区間として指定しから輻輳があると決定しまでを繰り返す
   ように機能することを特徴とする計測サーバ。
10. 前記所定条件は、前記ターゲットパスの過去の品質データと前記テストパスの過去の品質データとの差分が所定閾値以内であって、且つ、前記ターゲットパスの最新の品質データと前記テストパスの最新の品質データとの差分が所定閾値以内である場合に、前記相関度が高いと判断されることを特徴とする請求項９に記載の計測サーバ。
11. 前記品質データはパケット損失率であって、該パケット損失率が所定値以上の場合に前記劣化品質を示すと判断されることを特徴とする請求項９又は１０に記載の計測サーバ。
12. 前記テーブルの要素には、前記品質データに対して１つ以上の所定の品質判定閾値によって決定された品質ポイントが入力されることを特徴とする請求項１１に記載の計測サーバ。
13. 測定対象となるネットワークと、該ネットワークに相互に接続された複数の端末と、請求項９から１２のいずれか１項に記載の計測サーバとを有する計測システムであって、
    前記端末は、
    所定周期毎に、相手端末との間のパスにおける品質データをアクティブ計測するアクティブ計測手段と、
    所定周期毎に、前記パス上にある中継ノードリストを取得する中継ノードリスト取得手段と、
    前記品質データ及び前記中継ノードリストを前記計測サーバへ送信する前記データ送信手段と
    を有することを特徴とする計測システム。

Images