[第1実施例]
 以下、本発明の第1実施例について図面を参 照して説明する。図1は本発明の第1実施例に� ��るネットワークの構成例を示す図である。� ��ットワークには、ルータ(又はスイッチ)R1~RN が配置され、品質計測を行う試験端末A1~AK及� ��品質劣化箇所推定装置S1が接続されている� �また、本実施例では、ルータR1~RN間の通信リ ンクについては、同一のルータ間のリンクで あっても方向が異なるものは別のリンクであ るとして、各リンクにL1~LMの符号を付してあ� ��。

 試験端末A1~AKは、通信品質を計測する機� �と、計測した通信品質の情報を品質劣化箇� �推定装置S1に通知する機能と、品質劣化箇所 推定装置S1の指示に応じて試験フローを生成� ��てネットワークに送出する機能とを備えて� ��る。

 図2に本発明の第1実施例に係る品質劣化� �所推定装置S1の内部構成を示す。品質劣化箇 所推定装置S1は、フロー品質情報収集部1と、 経路情報収集部2と、フロー集合決定部3と、� ��ロー・リンクテーブル生成手段となるフロ� ��・リンクテーブル管理部4と、フロー・リン クテーブル記憶部5と、非劣化リンク除去部6� ��、縮小フロー・リンクテーブル記憶部7と、 品質劣化箇所推定部8と、表示部9とから構成� ��れている。品質劣化箇所推定装置S1は、試� �端末A1~AKからフロー毎の品質情報を集めて、 ルータR1~RNから得た経路情報を基に品質劣化� ��所を推定し、推定結果を表示部9に出力する 。

 以下に、品質劣化箇所推定装置S1の各構� �要素の動作を説明する。まず、フロー品質� �報収集部1は、試験端末A1~AKが通信を開始す� �と、試験端末A1~AKから通信開始の通知を受け 取る。また、フロー品質情報収集部1は、通� �開始以降は、試験端末A1~AKから定期的に、現 在の通信品質情報(例えばフローの送信元と� �る送信端末のアドレス、フローの宛先とな� �受信端末のアドレス、フロー品質情報、及� �フローレート)を受け取る。ここで、フロー� ��質情報とは、例えばパケットロス率、遅延� ��遅延ジッタなどの通信品質に関わる情報で� ��る。フローレートとは、通信に使われたフ� ��ーの1秒あたりのパケット数の情報である。 フロー品質情報収集部1は、試験端末A1~AKが通 信を終了すると、試験端末A1~AKから通信終了� ��通知を受け取る。

 次に、経路情報収集部2は、ルータ(又は� �イッチ)R1~RNから、ルーティングに関する経� �情報を収集する。この情報収集は、SMTP(Simple  Network Management Protocol)等を使って行うこと� ��可能である。経路情報があれば、送受信端� ��のアドレス情報から、当該送受信端末間の� ��信がどの経路で行われるかを決定すること� ��できる。ルータから収集する場合、経路情� ��は、具体的にはルーティングテーブル及びA RP(Address Resolution Protocol)テーブルの構成情報 である。また、スイッチから収集する場合、 経路情報は、具体的にはフォワーディングデ ーターベース及びスパニングツリーの構成情 報である。なお、経路情報については、ルー タ(又はスイッチ)R1~RNから収集せずに、ネッ� �ワーク管理者が与えることも可能である。

 次に、フロー集合決定部3は、試験端末A1~ AKがそれぞれ接続されたルータがどのルータ� ��あるかという情報を試験端末A1~AKから取得� �、この情報と経路情報収集部2が収集した経� ��情報に基づいて、どの端末間に試験フロー� ��流すべきかを以下に述べるように決定して� ��決定した端末間で試験フローを流すように� ��験端末A1~AKに対して指示する。図3はフロー� ��合決定部3の動作を示すフローチャートであ る。

 まず、フロー集合決定部3は、フローとフ ローが通過するリンクとフローの送信元とな る送信端末のアドレスとフローの宛先となる 受信端末のアドレスとを対応付けたフロー・ リンクテーブルを、K個の試験端末A1~AKのうち の任意の2つの端末間の全てのフローの組に� �いて生成する(図3ステップS100)。このフロー� ��リンクテーブルを、全フロー・リンクテー� ��ルXとする。フローの送受信の向きを区別す ると、K個の試験端末A1~AKのうちの任意の2つ� �端末間のフローの組は、K×(K-1)通り存在し得 る。したがって、K×(K-1)通りのフローについ� ��全フロー・リンクテーブルXを生成すること になる。

 全フロー・リンクテーブルXの1例を図4に示� ��。図4におけるF1はフローである。図4の例で は、全て空欄になっているが、実際の全フロ ー・リンクテーブルXでは、フローの行とこ� �フローが通過するリンクの列とが交差する� �にビット「1」が設定される。
 全フロー・リンクテーブルXは、試験端末A1~ AKから取得した、試験端末A1~AKの接続先のル� �タを示す情報と、経路情報収集部2が収集し� ��経路情報とを使うことによって生成するこ� ��が可能である。フロー集合決定部3は、全フ ロー・リンクテーブルXのK×(K-1)通りのフロー の中から、品質計測のために流す試験フロー の集合を以下の方法で決定する。

 本実施例では、フロー集合の決定方法と� ��て、第1のフロー集合決定方法を用いる。第 1のフロー集合決定方法を用いる場合、フロ� �集合決定部3は、まず全リンク数Mの1/2の値を Hとする(ステップS101)。全リンク数Mが2で割り 切れないときは、M/2の小数点以下を切り上げ あるいは切り捨てて、M/2の整数値をHとする� �

 次に、フロー集合決定部3は、全フロー・ リンクテーブルXから、各フローの通過リン� �数を求める(ステップS102)。通過リンク数を� �めるには、全フロー・リンクテーブルXの行� ��にビット「1」が立っている数を求めればよ い。フロー集合決定部3は、通過リンク数とH� ��の差の絶対値が小さいフローから順に並ぶ� ��うに全フロー・リンクテーブルXの各行をソ ートする(ステップS103)。ただし、通過リンク 数が同一のフロー、すなわち通過リンク数と Hとの差の絶対値が同一のフローが複数ある� �合には、これらのフロー中のソートの順は� �わないものとする。

 そして、フロー集合決定部3は、ソートし た全フロー・リンクテーブルXの各フローか� �優先順位が高い順に、すなわち通過リンク� �とHとの差の絶対値が小さい方から順に、予� ��定められた個数Jのフローを試験フローの集 合として決定する(ステップS104)。あるいは、 フロー集合決定部3は、ソートした全フロー� �リンクテーブルXの各フローのうち、通過リ� ��ク数とHとの差の絶対値が予め定められた閾 値以下であるフローを試験フローの集合とし て決定する(ステップS104)。

 最後に、フロー集合決定部3は、試験端末 A1~AKのうち、決定した試験フローの送信端末� ��受信端末に対して試験フローを流すように� ��示する(ステップS105)。

 次に、フロー・リンクテーブル管理部4は、 フロー品質情報収集部1が取得した通信品質� �報と、経路情報収集部2が収集した経路情報� ��に基づいて、現在通信が行われているフロ� ��について、送信端末のアドレスと受信端末� ��アドレスと通過するリンクとフローの品質( 例えばパケットロス率)とフローレートとを� �応付けたフロー・リンクテーブルを生成し� �このフロー・リンクテーブルをフロー・リ� �クテーブル記憶部5に記憶させる。
このフロー・リンクテーブルをフロー・リン クテーブルYと呼ぶ。図5はフロー・リンクテ� ��ブル管理部4の動作を示すフローチャートで ある。

 フロー・リンクテーブル管理部4は、フロ ー品質情報収集部1から通信品質情報を受信� �(図5ステップS200)、経路情報収集部2から経路 情報を受信すると(ステップS201)、通信品質情 報から送信端末のアドレスと受信端末のアド レスとフロー品質とフローレートとを取得し (ステップS202)、送受信端末のアドレスと経路 情報を基にフローの通過リンクを決定し(ス� �ップS203)、フロー・リンクテーブルYを生成� �て(ステップS204)、フロー・リンクテーブルY� ��フロー・リンクテーブル記憶部5に登録する (ステップS205)。

 フロー・リンクテーブルYの1例を図6に示す� ��全フロー・リンクテーブルXの場合と同様に 、フローの行とこのフローが通過するリンク の列とが交差する欄にはビット「1」が設定� �れる。
 前述のフロー集合決定部3の動作により、試 験端末A1~AK間に試験フローが流れるので、試� ��端末A1~AKからはこの試験フローの通信品質� �報が品質劣化箇所推定装置S1に送信される。 したがって、フロー・リンクテーブルYは、� �験フローを含む、現在通信が行われている� �ローについて作成されることになる。

 次に、非劣化リンク除去部6は、フロー・ リンクテーブルYに対して定期的に非劣化リ� �ク除去処理を行って、縮小フロー・リンク� �ーブルZを生成し、この縮小フロー・リンク� ��ーブルZを縮小フロー・リンクテーブル記憶 部7に記憶させる。図7は非劣化リンク除去部6 の動作を示すフローチャートである。

 まず、非劣化リンク除去部6は、フロー・ リンクテーブル記憶部5から定期的にフロー� �リンクテーブルYを読み出し、あらかじめ定� ��られた劣化閾値より品質が悪い劣化フロー� ��存在するかどうか調べる(図7ステップS300)。 非劣化リンク除去部6は、劣化フローが存在� �る場合、フロー・リンクテーブルYから、劣� ��フローを除く非劣化フローの行と非劣化フ� ��ーが通過するリンクの列とを削除すると共� ��、送信端末のアドレスと受信端末のアドレ� ��とフロー品質とフローレートとを削除して� ��縮小フロー・リンクテーブルZを生成し(ス� �ップS301)、縮小フロー・リンクテーブルZを� �小フロー・リンクテーブル記憶部7に登録す� ��(ステップS302)。縮小フロー・リンクテーブ� ��Zの1例を図8に示す。

 図9は品質劣化箇所推定部8の動作を示す� �ローチャートである。品質劣化箇所推定部8� ��、縮小フロー・リンクテーブル記憶部7から 縮小フロー・リンクテーブルZを読み出し(ス� ��ップS400)、品質劣化フロー数推定法あるい� �最小リンク数推定法を用いて品質劣化箇所� �推定し(ステップS401)、推定した品質劣化箇� �を表示部9に表示させる(ステップS402)。

 図19を用いて説明したように、品質劣化フ� �ー数推定法は、縮小フロー・リンクテーブ� �Zに登録された各リンクのうち、通過する劣� ��フローの数が最も多いリンクを品質劣化箇� ��とする方法である。
 一方、最小リンク数推定法は、縮小フロー� ��リンクテーブルZに登録された全ての劣化フ ローを包含するリンク集合(リンクの組み合� �せ)のうち、最小のリンク数を持つ最小リン� ��集合を品質劣化箇所とする方法である。

 こうして、品質劣化箇所推定装置S1では� �品質劣化箇所として推定されたリンクが表� �部9に表示される。

 次に、本実施例の効果について説明する� ��特開2006-238052号公報に開示された品質劣化� �所推定方法では、フロー・リンクテーブルY� ��各リンクの列に立っている縦のビット列に� ��いて、同じビット列を持つ1つ以上のリンク があると、それらのリンクはどれが品質劣化 を起こしても、全てが品質劣化箇所の候補と なってしまう。例えば、フロー・リンクテー ブルYが図10のようであったとする。このフロ ー・リンクテーブルYでリンクL2とL4は同じビ� ��ト列を持っているため、どちらか一方が品� ��劣化を起こしても、図11のような縮小フロ� �・リンクテーブルZが生成される。このため� ��品質劣化箇所推定部8では、品質劣化フロー 数に基づく推定法あるいは最小リンク数推定 法のいずれを用いても、L2,L4の両方のリンク� ��品質劣化箇所と判定されてしまう。この結� ��、どちらか一方の品質劣化していないリン� ��は誤って品質劣化箇所と判定されることに� ��り、推定精度が悪化することになる。

 これに対して、本実施例のフロー集合決� ��部3では、できるだけ少ないフロー数で、こ のような同じビット列を持つリンクの組が少 なくなるような試験フローの集合を選択して いる。本実施例の第1のフロー集合決定方法� �は、全フロー・リンクテーブルXの各行に立� ��ているビット数(通過リンク数)が、全リン� �数の1/2に近いフローを優先的に試験フロー� �して決定する。

 第1のフロー集合決定方法を用いる理由は 、全フロー・リンクテーブルXの2つの行(フロ ー)に着目したときに、各行に立つビットが� �ンダムである場合には、1/2のビットが立っ� �いるような行が最も多く起こり得る上、着� �した2行のビットが異なる位置の平均値が最� ��になるためである。このような現象が起こ� ��ことは、全フロー・リンクテーブルXの各列 にビットが立つ確率をpとすると、2つの行で� ��じ数だけビットが立つものについて、ビッ� ��が異なる確立はp×(1-p)であり、この確率が� �大となるのはp=1/2であることから明らかであ る。

 こうして、本実施例のフロー集合決定部3 において決定された試験フローの集合によれ ば、フロー・リンクテーブルYの行数(フロー� ��)を少なくすることができるので、特開2006-2 38052号公報に開示された品質劣化箇所推定方� ��に比べて品質劣化箇所の推定に要する時間� ��短縮することができ、またフロー・リンク� ��ーブルY上で縦のビット列が同一となるよう なリンクを少なくすることができるので、品 質劣化箇所の推定精度を向上させることがで きる。

[第2実施例]
 次に、本発明の第2実施例について説明する 。本実施例においても、ネットワーク及び品 質劣化箇所推定装置S1の構成は第1実施例と同 様であるので、図1、図2の符号を用いて説明� ��る。
 第1実施例との違いは、フロー集合決定部3� �おいてフロー集合の決定方法として第2のフ� ��ー集合決定方法を用いる点である。以下、� ��の第2のフロー集合決定方法について説明す る。

 図12は本実施例のフロー集合決定部3の動� ��を示すフローチャートである。まず、本実� ��例のフロー集合決定部3は、ステップS100と� �様に全フロー・リンクテーブルXを生成し(ス テップS500)、ステップS101と同様に全リンク数 Mの1/2の値をHとし(ステップS501)、ステップS102 と同様に全フロー・リンクテーブルXから、� �フローの通過リンク数を求める(ステップS502 )。

 続いて、フロー集合決定部3は、通過リン ク数が大きいフローから順に並ぶように全フ ロー・リンクテーブルXの各行をソートする(� ��テップS503)。ただし、通過リンク数が同一� �フローが複数ある場合には、これらのフロ� �中のソートの順は問わないものとする。

 そして、フロー集合決定部3は、ソートし た全フロー・リンクテーブルXの各フローか� �優先順位が高い順に、すなわち通過リンク� �が大きい方から順に、予め定められた個数J� ��フローを試験フローの集合として決定する( ステップS504)。あるいは、フロー集合決定部3 は、ソートした全フロー・リンクテーブルX� �各フローのうち、通過リンク数が予め定め� �れた閾値以上であるフローを試験フローの� �合として決定する(ステップS504)。

 最後に、フロー集合決定部3は、試験端末A1~ AKのうち、決定した試験フローの送信端末と� ��信端末に対して試験フローを流すように指� ��する(ステップS505)。こうして、フロー集合� ��定部3の処理が終了する。
 品質劣化箇所推定装置S1のその他の構成要� �の動作は、第1実施例と同じである。

 本実施例のフロー集合決定部3における第 2のフロー集合決定方法は、第1のフロー集合� ��定方法と同じ発想であるが、一般にネット� ��ークトポロジを考えると、フローはネット� ��ークの全リンク数Mの1/2より遙かに少ない数 のリンク数しか通過できない可能性が高い。 このため、全リンク数Mの1/2に近い数のリン� �を通るということは、現実的にはできるだ� �多くのリンクを通過するということと同義� �あるので、本実施例の第2のフロー集合決定� ��法によれば、第1のフロー集合決定方法と同 等の効果を得ることができる。

[第3実施例]
 次に、本発明の第3実施例について説明する 。本実施例においても、ネットワーク及び品 質劣化箇所推定装置S1の構成は第1実施例と同 様であるので、図1、図2の符号を用いて説明� ��る。
 第1実施例との違いは、フロー集合決定部3� �おいてフロー集合の決定方法として第3のフ� ��ー集合決定方法を用いる点である。以下、� ��の第3のフロー集合決定方法について説明す る。

 図13は本実施例のフロー集合決定部3の動� ��を示すフローチャートである。まず、本実� ��例のフロー集合決定部3は、ステップS100と� �様に全フロー・リンクテーブルXを生成し(ス テップS600)、ステップS101と同様に全リンク数 Mの1/2の値をHとする(ステップS601)。続いて、� ��ロー集合決定部3は、全フロー・リンクテー ブルXの全てのフロー(行)の集合をUとし、集� �Uの2つの要素間の距離を全ての要素の組み合 わせについて求める(ステップS602)。

 集合Uの2つの要素間の距離としては、通� �リンクを示すビット列間のハミング距離、� �なわち2つの要素間で異なる通過リンクの個� ��を用いる。例えば全フロー・リンクテーブ� ��Xにおいて、フローF1の通過リンクがL1,L3で� �フローF2の通過リンクがL1であるとすれば、� ��合Uの2つの要素であるフローF1とF2の間で異� ��る通過リンクはL3である。したがって、フ� �ーF1とF2間の距離は1となる。なお、集合Uに� �いて2つの要素のとり得る組み合わせは、全� ��でK×(K-1)×{K×(K-1)-1}通り存在する。以下、ス テップS602で要素間距離を求めた要素の組を� �アと呼ぶ。

 次に、フロー集合決定部3は、ステップS60 2で要素間距離を求めた全てのペアについて� �要素間距離とHとの差の絶対値を求め、要素� ��距離とHとの差の絶対値が小さいペアから順 に並ぶように全フロー・リンクテーブルXの� �行をソートする(ステップS603)。

 フロー集合決定部3は、ソートした全フロ ー・リンクテーブルXの先頭から優先順位が� �い順に、すなわち要素間距離とHとの差の絶� ��値が小さい方から順に、予め定められた個� ��Pのペアを選択する(ステップS604)。あるいは 、フロー集合決定部3は、ソートした全フロ� �・リンクテーブルXの各ペアのうち、要素間� ��離とHとの差の絶対値が予め定められた閾値 以下であるペアを選択する(ステップS604)。

 そして、フロー集合決定部3は、ステップS60 4で選択したペアの集合について、ペアの少� �くとも一方に含まれる全てのフローを試験� �ローとして決定する(ステップS605)。最後に� �フロー集合決定部3は、試験端末A1~AKのうち� �決定した試験フローの送信端末と受信端末� �対して試験フローを流すように指示する(ス� ��ップS606)。こうして、フロー集合決定部3の� ��理が終了する。
 品質劣化箇所推定装置S1のその他の構成要� �の動作は、第1実施例と同じである。

 本実施例のフロー集合決定部3における第3� �フロー集合決定方法によれば、以下のよう� �効果がある。
 全フロー・リンクテーブルXの任意の2行に� �目したとき、その通過リンクのビットが異� �る個数がハミング距離に対応している。任� �の2つのフローにおいて、同じリンクに立つ� ��ットの組は(0、0)、(0、1)、(1、0)、(1、1)の4� �りしかなく、この2つのフローの品質の現れ� ��の組み合わせにより、全リンクが4通りに分 類される。

 任意の2つのフローが(0、0)、(0、1)、(1、0) 、(1、1)の4つのリンクを含むとき、この4つの リンクに関してのハミング距離は2である。� �れを全リンクに拡張すれば、ハミング距離� �全リンクの数の1/2となっている場合に、最� �均一に全リンクが4通りに識別されることと� ��る。k本のフローがあったとき、k本のフロ� �で識別できるリンク数が最大となる(つまり� ��縦のビット列が同一となるようなリンクを� ��なくできる)のは、どのフローも均一に4通� �の識別を行う場合であり、このようなフロ� �集合を使うことで、最も少ないフロー数で� �品質劣化箇所の推定精度を最大化すること� �できる。

 このように、本実施例では、互いのハミ� ��グ距離が全リンク数の1/2に近付くようなフ� ��ー集合を集めており、少ないフロー数で品� ��劣化箇所推定精度が最大化されることが期� ��できる。

[第4実施例]
 次に、本発明の第4実施例について説明する 。本実施例においても、ネットワーク及び品 質劣化箇所推定装置S1の構成は第1実施例と同 様であるので、図1、図2の符号を用いて説明� ��る。
 第1実施例との違いは、フロー集合決定部3� �おいてフロー集合の決定方法として第4のフ� ��ー集合決定方法を用いる点である。以下、� ��の第4のフロー集合決定方法について説明す る。

 図14は本実施例のフロー集合決定部3の動� ��を示すフローチャートである。まず、本実� ��例のフロー集合決定部3は、ステップS100と� �様に全フロー・リンクテーブルXを生成し(ス テップS700)、全フロー・リンクテーブルXの全 てのフロー(行)の集合をUとし、フロー集合S� �空集合とし、T=0とする(ステップS701)。

 次に、フロー集合決定部3は、Tがあらか� �め決められた値J以上か、あるいはUが空集合 かどうかを調べ、いずれかの条件が成り立て ば図14の処理を終了し、そうでなければ、次� ��ステップ(ステップS703)に進む(ステップS702)� ��フロー集合決定部3は、Sの要素であるフロ� �のうち、フロー・リンクテーブルXを用い、� ��なくとも1つのフローが通過しているリンク の総数Pを求める(ステップS703)。フロー集合� �定部3は、Uの要素である各フローrのそれぞ� �について、Sにrを加えたフロー集合S∩{r}を� �め、S∩{r}の要素のフローのうち、少なくと� ��1つのフローが通過しているリンクの総数P� �(r)を求める(ステップS704)。

 フロー集合決定部3は、ステップS704で求め� �各フローrについてのP’(r)と、ステップS703� �求めたPとの差P’(r)-Pを求め、この差が大き� ��ものから優先的にフローを選択し、Sに加え る(ステップS705)。フロー集合決定部3は、ス� �ップS705でSに加えたフローをUから除外し、� �えたフローの本数をTに加算し、ステップS702 へ戻る(ステップS706)。ステップS705の処理を� �う度に、Tは単調に増加し、Uの要素は単調に 減少するため、いつか必ずステップS702の2つ� ��条件のいずれかが成立し、フロー集合決定� ��3は動作を停止する。
 品質劣化箇所推定装置S1のその他の構成要� �の動作は、第1実施例と同じである。

 本実施例のフロー集合決定部3における第4� �フロー集合決定方法によれば、以下のよう� �効果がある。
 全フロー・リンクテーブルの各列に着目し� ��とき、どのフローも通過していないリンク� ��もし劣化が発生しても、どのフローも劣化� ��ならず、品質劣化の発生自体が見逃されて� ��まい、品質劣化箇所の推定精度が悪化する� ��本実施例では、フロー集合の決定の際に、� ��のフローも通過していないリンクを少なく� ��るようにフローを選択して追加している。� ��のため、少ないフロー数で、品質劣化発生� ��見逃す可能性を最小化する事が期待され、� ��質劣化箇所推定精度を最大化することが期� ��できる。

 なお、第1実施例~第4実施例における品質� ��化箇所推定装置S1は、例えばCPU、記憶装置� �よびインタフェースを備えたコンピュータ� �これらのハードウェア資源を制御するプロ� �ラムによって実現することができる。この� �うなコンピュータを動作させるための品質� �化箇所推定プログラムは、フレキシブルデ� �スク、CD-ROM、DVD-ROM、メモリカードなどの記� ��媒体に記録された状態で提供される。CPUは� ��読み込んだプログラムを記憶装置に書き込� ��、このプログラムに従って第1実施例~第4実� ��例で説明した処理を実行する。