ネットワークの品質劣化箇所推定装置
【課題】各パスの正確な通信経路情報をネットワークから取得できない場合でも品質劣化箇所の正確に推定できるネットワークの品質劣化箇所推定装置を提供する。
【解決手段】計測部１０１は、各エンドノードに指示してパスごとにパケットロス率X1およびパケット遅延変動X2の計測結果を取得する。パス分類部１０２は、各パスを品質劣化に関して不良パスのグループおよび優良パスのグループを含む複数のグループに分類する。ネットワーク分割部１０３は、評価対象のネットワークを、その品質劣化を推定可能な最小単位である複数の候補箇所に分割する。識別部１０４は、前記優良パスのみが通過する候補箇所を識別する。集計部１０５は、優良パスのみが通過する候補箇所を除いた残りの候補箇所を対象に前記不良パスが通過する回数を集計する。推定部１０６は、候補箇所の中から、不良パスが通過する回数に基づいて不良箇所を推定する。
【解決手段】計測部１０１は、各エンドノードに指示してパスごとにパケットロス率X1およびパケット遅延変動X2の計測結果を取得する。パス分類部１０２は、各パスを品質劣化に関して不良パスのグループおよび優良パスのグループを含む複数のグループに分類する。ネットワーク分割部１０３は、評価対象のネットワークを、その品質劣化を推定可能な最小単位である複数の候補箇所に分割する。識別部１０４は、前記優良パスのみが通過する候補箇所を識別する。集計部１０５は、優良パスのみが通過する候補箇所を除いた残りの候補箇所を対象に前記不良パスが通過する回数を集計する。推定部１０６は、候補箇所の中から、不良パスが通過する回数に基づいて不良箇所を推定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの品質劣化箇所を推定する装置に係り、特に、負荷分散や多重化を目的に同一パスに複数の経路が確立されるネットワークの品質劣化箇所推定に好適な品質劣化箇所推定装置に関する。
【背景技術】
【０００２】
ネットワークの品質劣化箇所をリアルタイムに特定する方法として、複数のパス上でエンドツーエンドのパケットロス率やパケット遅延を周期的にアクティブ計測し、計測データ間の相関と経路情報とに基づいて品質劣化箇所を推定する方法が非特許文献１，２に開示されている。
【０００３】
非特許文献１は、パケットロス率に基づく推定手法であり、計測周期ごとに各パスのパケットロス率を予め設定された閾値と比較してパスの状態を３つに分類(good/bad/medium)し、分類結果をネットワークのトポロジ情報にマッピングさせることによりパケットロスの発生箇所を推定するものである。
【０００４】
非特許文献２は、パケット遅延に基づく推定手法であり、各パスをパケット遅延の時系列データの類似性に着目して複数のクラスタ(集合)に分類し、分類結果をネットワークのトポロジ情報にマッピングさせることによりパケット遅延の発生箇所を推定するものである。
【０００５】
図１１は、非特許文献２による品質劣化箇所の推定方法を模式的に表現した図であり、ここでは、送受信ノードがノードA，Bのペアであるパス１に関して、通信経路がRa→Rf→Re→Rdであり、パケットロス率に基づく品質分類が"bad"であり、パケット遅延に基づく品質分類が「クラスタ１」である計測データが得られている。
【０００６】
そして、他のパス２−６に関しても、計測データが図示の通りであれば、パケットロス率に基づく分類が"bad"のパスに共通するリンクとしてRf→Reが識別されるものの、その逆向きリンクRe→Rfを含む２つのパス５，６は、パケットロス率に基づく分類が"good"であり、パケット遅延に基づく分類も「クラスタ０」であることから、Rf→Reのリンク品質が劣化しているものと推定される。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】A. Tachibana, S. Ano, T. Hasegawa, M. Tsuru, Y. Oie, "Locating Congested Segments over the Internet Based on Multiple End-to-End Path Measurements," IEICE Transactions 89-B(4), pp. 1099-1109 (2006).
【非特許文献２】A. Tachibana, S. Ano, T. Hasegawa, M. Tsuru, Y. Oie, "Locating congested segments over the Internet by clustering the delay performance of multiple path," Computer Communications 32, pp. 1642-1654 (2009).
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記の各先行技術はいずれも、各パスの通信経路情報をネットワークから収集できることが前提とされていたため、通信経路情報を収集できなければ誤推定する問題がある。特に、近年のように、同一パスに通信経路(の候補)を複数設定し、ロードバランシングの実現や信頼性の向上を図るネットワークでは、各パスの正確な通信経路情報の取得が困難である場合が多い。
【０００９】
図１２は、ロードバランシングを採用するネットワークの一例を示した図であり、図示の例では、ノードRaは２つのノードRb，Rfのいずれか一方（または、両方）との間にリンクを自律的に確立するが、ネットワークからは、ノードA，B間にどのような経路が確立されているのかの情報を取得することが困難であるため、ノードA，Bのパスに品質劣化が生じても、その具体的な品質箇所を推定することができない。
【００１０】
本発明の目的は、上記した従来技術の課題を解決し、各パスの正確な通信経路情報をネットワークから取得できない場合でも、品質劣化箇所の正確に推定できるネットワークの品質劣化箇所推定装置を提供することにある。
【課題を解決するための手段】
【００１１】
上記の目的を達成するために、本発明は、エンドノード間に確立されるパスが少なくとも一つの経路候補を含むネットワークの品質劣化箇所推定装置において、パスごとに品質劣化の指標値を計測する計測手段を設けた。この指標値としては、例えばパケットロス率X1やパケット遅延変動X2を利用できる。
【００１２】
本発明はまた、前記指標値に基づいて、各パスを品質劣化に関して不良パスのグループおよび優良パスのグループを含む複数のグループに分類するパス分類手段と、ネットワークを、その品質劣化を推定可能な最小単位である複数の候補箇所に分割するネットワーク分割手段とを設けた。このネットワーク分割手段は、ネットワークを例えば分岐および合流の無い複数の区間kiおよび各区間kiの分岐、合流点に位置するネットワーク機器njに分割し、各区間kiおよびネットワーク機器njを候補箇所とする。
【００１３】
本発明はさらに、優良パスのみが通過する候補箇所を識別する識別手段と、優良パスのみが通過する候補箇所を除いた残りの候補箇所の集合を対象に前記不良パスが通過する回数を集計する集計手段と、候補箇所の中から、前記不良パスが通過する回数に基づいて不良箇所を推定する推定手段とを設けた。
【発明の効果】
【００１４】
本発明によれば、以下のような効果が達成される。
(1)各パスに通信経路の候補が複数存在するネットワークにおいても、各パスの品質が劣化したときに、その劣化箇所を推定できるようになる。
(2)劣化箇所を推定する際に、リンクのみならずネットワーク機器も候補とできるので、劣化箇所をリンクおよびネットワーク機器単位で正確に推定できるようになる。
【図面の簡単な説明】
【００１５】
【図１】本発明が評価対象とするネットワークのトポロジ情報の一例を示した図である。
【図２】ノード間に確立される各パスの構成を示した図である。
【図３】本発明における品質劣化箇所の推定方法を示したフローチャートである。
【図４】ネットワークを、その品質劣化箇所に関して複数の候補箇所に分割する方法を示した図である。
【図５】パケットロス率X1に基づく不良箇所の推定方法を示したフローチャートである。
【図６】候補箇所の一部を候補箇所の集合から除外する方法の一例を示した図である。
【図７】badパスの集計例を示した図である。
【図８】品質劣化箇所の推定例を示した図である。
【図９】パケット遅延変動X2に基づく劣化箇所の推定方法を示したフローチャートである。
【図１０】本発明に係る品質劣化箇所推定装置の機能ブロック図である。
【図１１】非特許文献２による品質劣化箇所の推定方法を模式的に表現した図である。
【図１２】ロードバランシングを採用するネットワークの一例を示した図である。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明が評価対象とするネットワークのトポロジ情報の一例を示した図であり、品質劣化箇所を推定する品質劣化箇所装置１がルータ等のネットワーク機器（ここでは、Rc）を介してネットワークに接続されている。図２は、各ノード間に確立されるパスの構成を示した図であり、本実施形態では、ノードAからノードBへ至るパス１のように、一つのパスが複数の経路候補L1，L2を含む場合もある。
【００１７】
図３は、本発明の一実施形態に係る品質劣化箇所の推定方法を示したフローチャートであり、主に前記品質劣化箇所装置１および各エンドノードA，B，C…の動作を示している。本実施形態では、品質劣化箇所が以下の５つのステップで推定され、当該推定処理は所定の周期で繰り返し実行される。
【００１８】
(1)ステップＳ１：全てのパス上で同時にエンドツーエンドのパケットロス率X1およびパケット遅延変動X2がアクティブ計測される。
【００１９】
(2)前記計測結果に基づいて、品質の劣化したパスが存在するか否かを判定し、劣化パスが存在すれば、ステップＳ３以降へ進んで劣化箇所の推定を進める。
【００２０】
(3)ステップＳ３：パケットロス率X1およびパケット遅延変動X2の計測結果が解析されて各パスの品質情報が計算(クラスタリング)される。
【００２１】
(4)ステップＳ４：ネットワークが、品質劣化箇所に関して複数の候補箇所（後述する区間kiおよびネットワーク機器nj）に分割される。
【００２２】
(5)ステップＳ５：各パスの品質情報をトポロジ情報にマッピングすることで品質劣化箇所が推定される。
【００２３】
ステップＳ１では、パスごとに、独立したランダムな時間間隔でテストパケットが連続的に送受信され、各パスの通信品質を代表する指標として、エンドツーエンドのパケットロス率X1およびパケット遅延変動X2が同時に計測される。このような計測は、各エンドノードが前記品質劣化箇所装置１からの計測要求に応答して計測を実行し、計測結果を前記品質劣化箇所装置１へ提供することにより行われる。前記パケット遅延変動X2は、送信側から受信側にパケットが到着する時間(パケット遅延)から、伝送遅延やルータ等の固定的な処理時間を除いた遅延の変動分で定義されるが、ここでは、パケット遅延−周期内の最小パケット遅延で近似される。
【００２４】
ステップＳ２では、前記品質劣化箇所装置１において、前記パケットロス率X1およびパケット遅延変動X2の少なくとも一方が、予め設定された閾値X1ref，Xref2を上回る劣化パスが検出されたか否かが判定される。品質の劣化したパスが検出されればステップ３以降へ進み、品質劣化箇所の推定が行われる。品質の劣化したパスが検出されなければ、該当周期においては品質劣化箇所の推定が行われない。
【００２５】
前記ステップ２において、パケットロス率X1が閾値X1refを上回る劣化パスが一つでも検出されていると、ステップＳ３では、前記品質劣化箇所装置１において、全てのパスのパケットロス率X1が予め設定された２つの閾値X1refl, X1refhと比較され、各パスが３つの状態(good/medium/bad)のいずれかに分類される。
【００２６】
本実施形態では、前記閾値X1refとX1reflとが同値であり、X1refl＜X1refhとされる。そして、X1≦X1reflの各パスがgoodパスのグループに分類され、X1refl＜X1≦X1refhの各パスがmediumパスのグループに分類され、X1refh＜X1の各パスがbadパスのグループに分類される。このように、本実施形態において各パスを３状態に分類するのは誤判定を回避するためであり、mediumパスのグループに分類されたパスの情報は以降の品質劣化箇所推定に利用されない。
【００２７】
一方、前記ステップ２において、パケット遅延変動X2が予め設定された閾値X2ref（例えば、１０ms）を上回る劣化パスが一つでも検出されていると、ステップＳ３では、各パスのパケット遅延変動X2の時系列の類似性に基づいて、各パスが複数のクラスタに分類される。
【００２８】
このように、本実施形態ではパケットロス率X1によるパスの分類結果として、good/ badのパスの集合(Sgood, Sbad)が得られ、パケット遅延変動X2によるパスの分類結果として、同一の品質劣化を経験したパスの集合（クラスタ）C1, C2, …, Cnおよび品質劣化を経験していないパスの集合C0が得られる。ここで、パケットロス率X1による分類では、各パスはSgood, (Smedium,) Sbadのいずれか一方に分類されるが、パケット遅延変動X2による分類では、同一パスが複数のクラスタに重複して分類される場合もある。
【００２９】
ステップ４では、前記品質劣化箇所装置１において、図４に一例を示したように、評価対象のネットワークが各パスの分岐・合流点を基準にして、ネットワークの品質劣化を推定可能な最小単位である複数の候補箇所に分割される。本実施形態では、ネットワークが分岐、合流の無い複数の区間ki（ネットワーク機器および当該ネットワーク機器同士を接続するリンクにより構成される）と、各区間kiの分岐、合流点に位置するルータ等のネットワーク機器njとに分割され、前記各区間kiおよび各ネットワーク機器njが品質劣化の候補箇所とされる。なお、本実施形態では区間kiの構成要素が同一であっても、パケットの通過方向が異なれば別区間として扱われる。
【００３０】
図３へ戻り、ステップＳ５では、前記品質劣化箇所装置１において前記品質劣化の候補箇所ki，njを対象に、パケットロス率X1に基づく不良箇所の推定およびパケット遅延変動X2に基づく不良箇所の推定が行われる。以下、パケットロス率X1に基づく不良箇所の推定方法、およびパケット遅延変動X2に基づく不良箇所の推定方法のそれぞれについて詳細に説明する。
【００３１】
[パケットロス率による推定]
図５は、前記パケットロス率X1に基づく不良箇所の推定方法を示したフローチャートであり、主に前記品質劣化箇所装置１の動作を示している。
【００３２】
ステップＳ２１では、goodパスの一つが今回の注目goodパスとして選択される。ステップＳ２２では、今回の注目goodパスに関して、その候補経路の全てが共有する箇所が品質劣化の候補箇所の集合から除外される。図６の例では、パス１が２つの経路候補L1，L2を含み、各経路候補L1，L2は送信ノードA→ネットワーク機器Raの区間およびネットワーク機器Rd→受信ノードBの区間を共有するので、当該２つの区間k1，k10が候補箇所の集合から除外される。ただし、区間k1，k10であっても、逆向きの経路（ネットワーク機器Ra→送信ノードAおよび受信ノードB→ネットワーク機器Rd）は扱いが異なるので、候補箇所の集合から除外されることはない。
【００３３】
ステップＳ２３では、全てのgoodパスに関して上記の除外処理が完了したか否かが判定される。完了していなければステップＳ２１へ戻り、注目するgoodパスを切り替えながら上記の各処理を全てのgoodパスを対象に繰り返すことで候補箇所が絞り込まれる。
【００３４】
ステップＳ２４では、品質劣化の候補箇所として残っている全ての箇所（区間kiおよびネットワーク機器nj）を対象に、通過または通過する可能性のあるbadパスの数が集計される。図７は、通過するbadパスの集計例を示した図であり、エンドノードA，Bを送受信ノードとするパス１がbadパスであれば、当該パスの２つの経路候補L1，L2が経由する全ての区間kiおよびネットワーク機器njのカウント値がインクリメント（＋１）される。ステップＳ２５では、全てのbadパスについて上記の集計が完了したか否かが判定される。完了していなければステップＳ２４へ戻り、badパスを切り替えながら集計が繰り返される。
【００３５】
ステップＳ２６では、各候補箇所を通過または通過する可能性のあるbadパス数Nbpathと、badパスの総数(=|Sbad|)との比Tloss(=Nbpath/|Sbad|)が計算され、Tlossが最大となる候補箇所が品質劣化箇所として推定される。図８は、品質劣化箇所の推定例を示した図であり、ここでは、ネットワーク機器Rfから同Reへ向かう区間k6のカウント値が「４」で最大値を示すので、当該区間k6が品質劣化箇所として推定される。
【００３６】
[パケット遅延変動による推定方法]
図９は、前記パケット遅延変動X2に基づく劣化箇所の推定方法を示したフローチャートであり、主に前記品質劣化箇所装置１の動作を示している。ここでは、パスの分類結果として得られたクラスタ (C1, C2… CN)ごとに劣化箇所が推定される。
【００３７】
ステップＳ３１では、クラスタCi(C0，C1…Cn)の一つが今回の注目クラスタCtとして選択される。ステップＳ３２では、今回の注目クラスタCtに含まれない全てのパスPjを対象に、各パスの経路候補同士の共有箇所が識別されて候補箇所の集合から除外される。ステップＳ３３では、品質劣化の候補箇所として残っている全ての箇所（区間kiおよび当該区間kiに含まれるネットワーク機器nj）を対象に、今回の注目クラスタCtに含まれるパスが当該箇所を通過する回数が集計される。
【００３８】
ステップＳ３４では、各候補箇所を通過するパス数 Ncpathと、今回の注目クラスタCtに含まれるパスの総数(=|Ct|)との比 Tdelay_ i(=Ncpath／|Ct|）が計算され、Tdelay_ iが最大となる候補箇所が品質劣化箇所として推定される。なお、前記ステップＳ３１〜３４の手順は、前記パケットロス率による推定において、今回の注目クラスタCiに含まれるパスの集合をSbad、それ以外のパスの集合をSgoodとした場合と同様である。
【００３９】
ステップＳ３５では、上記の推定手順が全てのクラスタCiに対して完了したか否かが判定される。完了していなければステップＳ３１へ戻り、注目クラスCtを切り替えながら上記の推定手順が他のクラスタ Ck(k=1,2…n, i≠k)に対して繰り返され、クラスタCiごとに品質劣化箇所が推定される。
【００４０】
図１０は、前記品質劣化箇所推定装置１の機能ブロック図であり、計測部１０１は、各エンドノードに指示してパスごとに品質劣化の指標値を計測させ、その計測結果を各エンドノードから取得する。本実施形態では、パケットロス率X1およびパケット遅延変動X2の計測が指示され、その計測結果が取得される。
【００４１】
パス分類部１０２は、前記指標値の計測結果に基づいて、各パスを品質劣化に関して不良パスのグループおよび優良パスのグループを含む複数のグループに分類する。本実施形態では、パケットロス率X1に関しては、各パスがそのパケットロス率に基づいて、不良パスのグループ、優良パスのグループおよびその中間のパスのグループに分類され、中間パスは品質劣化箇所の推定に使用されない。また、パケット遅延変動X2に関しては、各パスがそのパケット遅延変動に基づいて複数のクラスタに分類される。
【００４２】
ネットワーク分割部１０３は、評価対象のネットワークを、その品質劣化を推定可能な最小単位である複数の候補箇所に分割する。本実施形態では、ネットワークが分岐および合流の無い複数の区間kiおよび各区間kiの分岐、合流点に位置するネットワーク機器njに分割され、各区間kiおよびネットワーク機器njが候補箇所とされる。
【００４３】
識別部１０４は、前記優良パスのみが通過する候補箇所を識別する。集計部１０５は、前記優良パスのみが通過する候補箇所を除いた残りの候補箇所の集合を対象に前記不良パスが通過する回数を集計する。推定部１０６は、前記候補箇所の中から、前記不良パスが通過する回数に基づいて不良箇所を推定する。本実施形態では、不良パスの通過数が最大の候補箇所が不良箇所と推定される
【符号の説明】
【００４４】
１…品質劣化箇所推定装置，１０１…計測部，１０２…パス分類部，１０３…ネットワーク分割部，１０４…識別部，１０５…集計部，１０６…推定部
【技術分野】
【０００１】
本発明は、ネットワークの品質劣化箇所を推定する装置に係り、特に、負荷分散や多重化を目的に同一パスに複数の経路が確立されるネットワークの品質劣化箇所推定に好適な品質劣化箇所推定装置に関する。
【背景技術】
【０００２】
ネットワークの品質劣化箇所をリアルタイムに特定する方法として、複数のパス上でエンドツーエンドのパケットロス率やパケット遅延を周期的にアクティブ計測し、計測データ間の相関と経路情報とに基づいて品質劣化箇所を推定する方法が非特許文献１，２に開示されている。
【０００３】
非特許文献１は、パケットロス率に基づく推定手法であり、計測周期ごとに各パスのパケットロス率を予め設定された閾値と比較してパスの状態を３つに分類(good/bad/medium)し、分類結果をネットワークのトポロジ情報にマッピングさせることによりパケットロスの発生箇所を推定するものである。
【０００４】
非特許文献２は、パケット遅延に基づく推定手法であり、各パスをパケット遅延の時系列データの類似性に着目して複数のクラスタ(集合)に分類し、分類結果をネットワークのトポロジ情報にマッピングさせることによりパケット遅延の発生箇所を推定するものである。
【０００５】
図１１は、非特許文献２による品質劣化箇所の推定方法を模式的に表現した図であり、ここでは、送受信ノードがノードA，Bのペアであるパス１に関して、通信経路がRa→Rf→Re→Rdであり、パケットロス率に基づく品質分類が"bad"であり、パケット遅延に基づく品質分類が「クラスタ１」である計測データが得られている。
【０００６】
そして、他のパス２−６に関しても、計測データが図示の通りであれば、パケットロス率に基づく分類が"bad"のパスに共通するリンクとしてRf→Reが識別されるものの、その逆向きリンクRe→Rfを含む２つのパス５，６は、パケットロス率に基づく分類が"good"であり、パケット遅延に基づく分類も「クラスタ０」であることから、Rf→Reのリンク品質が劣化しているものと推定される。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】A. Tachibana, S. Ano, T. Hasegawa, M. Tsuru, Y. Oie, "Locating Congested Segments over the Internet Based on Multiple End-to-End Path Measurements," IEICE Transactions 89-B(4), pp. 1099-1109 (2006).
【非特許文献２】A. Tachibana, S. Ano, T. Hasegawa, M. Tsuru, Y. Oie, "Locating congested segments over the Internet by clustering the delay performance of multiple path," Computer Communications 32, pp. 1642-1654 (2009).
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記の各先行技術はいずれも、各パスの通信経路情報をネットワークから収集できることが前提とされていたため、通信経路情報を収集できなければ誤推定する問題がある。特に、近年のように、同一パスに通信経路(の候補)を複数設定し、ロードバランシングの実現や信頼性の向上を図るネットワークでは、各パスの正確な通信経路情報の取得が困難である場合が多い。
【０００９】
図１２は、ロードバランシングを採用するネットワークの一例を示した図であり、図示の例では、ノードRaは２つのノードRb，Rfのいずれか一方（または、両方）との間にリンクを自律的に確立するが、ネットワークからは、ノードA，B間にどのような経路が確立されているのかの情報を取得することが困難であるため、ノードA，Bのパスに品質劣化が生じても、その具体的な品質箇所を推定することができない。
【００１０】
本発明の目的は、上記した従来技術の課題を解決し、各パスの正確な通信経路情報をネットワークから取得できない場合でも、品質劣化箇所の正確に推定できるネットワークの品質劣化箇所推定装置を提供することにある。
【課題を解決するための手段】
【００１１】
上記の目的を達成するために、本発明は、エンドノード間に確立されるパスが少なくとも一つの経路候補を含むネットワークの品質劣化箇所推定装置において、パスごとに品質劣化の指標値を計測する計測手段を設けた。この指標値としては、例えばパケットロス率X1やパケット遅延変動X2を利用できる。
【００１２】
本発明はまた、前記指標値に基づいて、各パスを品質劣化に関して不良パスのグループおよび優良パスのグループを含む複数のグループに分類するパス分類手段と、ネットワークを、その品質劣化を推定可能な最小単位である複数の候補箇所に分割するネットワーク分割手段とを設けた。このネットワーク分割手段は、ネットワークを例えば分岐および合流の無い複数の区間kiおよび各区間kiの分岐、合流点に位置するネットワーク機器njに分割し、各区間kiおよびネットワーク機器njを候補箇所とする。
【００１３】
本発明はさらに、優良パスのみが通過する候補箇所を識別する識別手段と、優良パスのみが通過する候補箇所を除いた残りの候補箇所の集合を対象に前記不良パスが通過する回数を集計する集計手段と、候補箇所の中から、前記不良パスが通過する回数に基づいて不良箇所を推定する推定手段とを設けた。
【発明の効果】
【００１４】
本発明によれば、以下のような効果が達成される。
(1)各パスに通信経路の候補が複数存在するネットワークにおいても、各パスの品質が劣化したときに、その劣化箇所を推定できるようになる。
(2)劣化箇所を推定する際に、リンクのみならずネットワーク機器も候補とできるので、劣化箇所をリンクおよびネットワーク機器単位で正確に推定できるようになる。
【図面の簡単な説明】
【００１５】
【図１】本発明が評価対象とするネットワークのトポロジ情報の一例を示した図である。
【図２】ノード間に確立される各パスの構成を示した図である。
【図３】本発明における品質劣化箇所の推定方法を示したフローチャートである。
【図４】ネットワークを、その品質劣化箇所に関して複数の候補箇所に分割する方法を示した図である。
【図５】パケットロス率X1に基づく不良箇所の推定方法を示したフローチャートである。
【図６】候補箇所の一部を候補箇所の集合から除外する方法の一例を示した図である。
【図７】badパスの集計例を示した図である。
【図８】品質劣化箇所の推定例を示した図である。
【図９】パケット遅延変動X2に基づく劣化箇所の推定方法を示したフローチャートである。
【図１０】本発明に係る品質劣化箇所推定装置の機能ブロック図である。
【図１１】非特許文献２による品質劣化箇所の推定方法を模式的に表現した図である。
【図１２】ロードバランシングを採用するネットワークの一例を示した図である。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明が評価対象とするネットワークのトポロジ情報の一例を示した図であり、品質劣化箇所を推定する品質劣化箇所装置１がルータ等のネットワーク機器（ここでは、Rc）を介してネットワークに接続されている。図２は、各ノード間に確立されるパスの構成を示した図であり、本実施形態では、ノードAからノードBへ至るパス１のように、一つのパスが複数の経路候補L1，L2を含む場合もある。
【００１７】
図３は、本発明の一実施形態に係る品質劣化箇所の推定方法を示したフローチャートであり、主に前記品質劣化箇所装置１および各エンドノードA，B，C…の動作を示している。本実施形態では、品質劣化箇所が以下の５つのステップで推定され、当該推定処理は所定の周期で繰り返し実行される。
【００１８】
(1)ステップＳ１：全てのパス上で同時にエンドツーエンドのパケットロス率X1およびパケット遅延変動X2がアクティブ計測される。
【００１９】
(2)前記計測結果に基づいて、品質の劣化したパスが存在するか否かを判定し、劣化パスが存在すれば、ステップＳ３以降へ進んで劣化箇所の推定を進める。
【００２０】
(3)ステップＳ３：パケットロス率X1およびパケット遅延変動X2の計測結果が解析されて各パスの品質情報が計算(クラスタリング)される。
【００２１】
(4)ステップＳ４：ネットワークが、品質劣化箇所に関して複数の候補箇所（後述する区間kiおよびネットワーク機器nj）に分割される。
【００２２】
(5)ステップＳ５：各パスの品質情報をトポロジ情報にマッピングすることで品質劣化箇所が推定される。
【００２３】
ステップＳ１では、パスごとに、独立したランダムな時間間隔でテストパケットが連続的に送受信され、各パスの通信品質を代表する指標として、エンドツーエンドのパケットロス率X1およびパケット遅延変動X2が同時に計測される。このような計測は、各エンドノードが前記品質劣化箇所装置１からの計測要求に応答して計測を実行し、計測結果を前記品質劣化箇所装置１へ提供することにより行われる。前記パケット遅延変動X2は、送信側から受信側にパケットが到着する時間(パケット遅延)から、伝送遅延やルータ等の固定的な処理時間を除いた遅延の変動分で定義されるが、ここでは、パケット遅延−周期内の最小パケット遅延で近似される。
【００２４】
ステップＳ２では、前記品質劣化箇所装置１において、前記パケットロス率X1およびパケット遅延変動X2の少なくとも一方が、予め設定された閾値X1ref，Xref2を上回る劣化パスが検出されたか否かが判定される。品質の劣化したパスが検出されればステップ３以降へ進み、品質劣化箇所の推定が行われる。品質の劣化したパスが検出されなければ、該当周期においては品質劣化箇所の推定が行われない。
【００２５】
前記ステップ２において、パケットロス率X1が閾値X1refを上回る劣化パスが一つでも検出されていると、ステップＳ３では、前記品質劣化箇所装置１において、全てのパスのパケットロス率X1が予め設定された２つの閾値X1refl, X1refhと比較され、各パスが３つの状態(good/medium/bad)のいずれかに分類される。
【００２６】
本実施形態では、前記閾値X1refとX1reflとが同値であり、X1refl＜X1refhとされる。そして、X1≦X1reflの各パスがgoodパスのグループに分類され、X1refl＜X1≦X1refhの各パスがmediumパスのグループに分類され、X1refh＜X1の各パスがbadパスのグループに分類される。このように、本実施形態において各パスを３状態に分類するのは誤判定を回避するためであり、mediumパスのグループに分類されたパスの情報は以降の品質劣化箇所推定に利用されない。
【００２７】
一方、前記ステップ２において、パケット遅延変動X2が予め設定された閾値X2ref（例えば、１０ms）を上回る劣化パスが一つでも検出されていると、ステップＳ３では、各パスのパケット遅延変動X2の時系列の類似性に基づいて、各パスが複数のクラスタに分類される。
【００２８】
このように、本実施形態ではパケットロス率X1によるパスの分類結果として、good/ badのパスの集合(Sgood, Sbad)が得られ、パケット遅延変動X2によるパスの分類結果として、同一の品質劣化を経験したパスの集合（クラスタ）C1, C2, …, Cnおよび品質劣化を経験していないパスの集合C0が得られる。ここで、パケットロス率X1による分類では、各パスはSgood, (Smedium,) Sbadのいずれか一方に分類されるが、パケット遅延変動X2による分類では、同一パスが複数のクラスタに重複して分類される場合もある。
【００２９】
ステップ４では、前記品質劣化箇所装置１において、図４に一例を示したように、評価対象のネットワークが各パスの分岐・合流点を基準にして、ネットワークの品質劣化を推定可能な最小単位である複数の候補箇所に分割される。本実施形態では、ネットワークが分岐、合流の無い複数の区間ki（ネットワーク機器および当該ネットワーク機器同士を接続するリンクにより構成される）と、各区間kiの分岐、合流点に位置するルータ等のネットワーク機器njとに分割され、前記各区間kiおよび各ネットワーク機器njが品質劣化の候補箇所とされる。なお、本実施形態では区間kiの構成要素が同一であっても、パケットの通過方向が異なれば別区間として扱われる。
【００３０】
図３へ戻り、ステップＳ５では、前記品質劣化箇所装置１において前記品質劣化の候補箇所ki，njを対象に、パケットロス率X1に基づく不良箇所の推定およびパケット遅延変動X2に基づく不良箇所の推定が行われる。以下、パケットロス率X1に基づく不良箇所の推定方法、およびパケット遅延変動X2に基づく不良箇所の推定方法のそれぞれについて詳細に説明する。
【００３１】
[パケットロス率による推定]
図５は、前記パケットロス率X1に基づく不良箇所の推定方法を示したフローチャートであり、主に前記品質劣化箇所装置１の動作を示している。
【００３２】
ステップＳ２１では、goodパスの一つが今回の注目goodパスとして選択される。ステップＳ２２では、今回の注目goodパスに関して、その候補経路の全てが共有する箇所が品質劣化の候補箇所の集合から除外される。図６の例では、パス１が２つの経路候補L1，L2を含み、各経路候補L1，L2は送信ノードA→ネットワーク機器Raの区間およびネットワーク機器Rd→受信ノードBの区間を共有するので、当該２つの区間k1，k10が候補箇所の集合から除外される。ただし、区間k1，k10であっても、逆向きの経路（ネットワーク機器Ra→送信ノードAおよび受信ノードB→ネットワーク機器Rd）は扱いが異なるので、候補箇所の集合から除外されることはない。
【００３３】
ステップＳ２３では、全てのgoodパスに関して上記の除外処理が完了したか否かが判定される。完了していなければステップＳ２１へ戻り、注目するgoodパスを切り替えながら上記の各処理を全てのgoodパスを対象に繰り返すことで候補箇所が絞り込まれる。
【００３４】
ステップＳ２４では、品質劣化の候補箇所として残っている全ての箇所（区間kiおよびネットワーク機器nj）を対象に、通過または通過する可能性のあるbadパスの数が集計される。図７は、通過するbadパスの集計例を示した図であり、エンドノードA，Bを送受信ノードとするパス１がbadパスであれば、当該パスの２つの経路候補L1，L2が経由する全ての区間kiおよびネットワーク機器njのカウント値がインクリメント（＋１）される。ステップＳ２５では、全てのbadパスについて上記の集計が完了したか否かが判定される。完了していなければステップＳ２４へ戻り、badパスを切り替えながら集計が繰り返される。
【００３５】
ステップＳ２６では、各候補箇所を通過または通過する可能性のあるbadパス数Nbpathと、badパスの総数(=|Sbad|)との比Tloss(=Nbpath/|Sbad|)が計算され、Tlossが最大となる候補箇所が品質劣化箇所として推定される。図８は、品質劣化箇所の推定例を示した図であり、ここでは、ネットワーク機器Rfから同Reへ向かう区間k6のカウント値が「４」で最大値を示すので、当該区間k6が品質劣化箇所として推定される。
【００３６】
[パケット遅延変動による推定方法]
図９は、前記パケット遅延変動X2に基づく劣化箇所の推定方法を示したフローチャートであり、主に前記品質劣化箇所装置１の動作を示している。ここでは、パスの分類結果として得られたクラスタ (C1, C2… CN)ごとに劣化箇所が推定される。
【００３７】
ステップＳ３１では、クラスタCi(C0，C1…Cn)の一つが今回の注目クラスタCtとして選択される。ステップＳ３２では、今回の注目クラスタCtに含まれない全てのパスPjを対象に、各パスの経路候補同士の共有箇所が識別されて候補箇所の集合から除外される。ステップＳ３３では、品質劣化の候補箇所として残っている全ての箇所（区間kiおよび当該区間kiに含まれるネットワーク機器nj）を対象に、今回の注目クラスタCtに含まれるパスが当該箇所を通過する回数が集計される。
【００３８】
ステップＳ３４では、各候補箇所を通過するパス数 Ncpathと、今回の注目クラスタCtに含まれるパスの総数(=|Ct|)との比 Tdelay_ i(=Ncpath／|Ct|）が計算され、Tdelay_ iが最大となる候補箇所が品質劣化箇所として推定される。なお、前記ステップＳ３１〜３４の手順は、前記パケットロス率による推定において、今回の注目クラスタCiに含まれるパスの集合をSbad、それ以外のパスの集合をSgoodとした場合と同様である。
【００３９】
ステップＳ３５では、上記の推定手順が全てのクラスタCiに対して完了したか否かが判定される。完了していなければステップＳ３１へ戻り、注目クラスCtを切り替えながら上記の推定手順が他のクラスタ Ck(k=1,2…n, i≠k)に対して繰り返され、クラスタCiごとに品質劣化箇所が推定される。
【００４０】
図１０は、前記品質劣化箇所推定装置１の機能ブロック図であり、計測部１０１は、各エンドノードに指示してパスごとに品質劣化の指標値を計測させ、その計測結果を各エンドノードから取得する。本実施形態では、パケットロス率X1およびパケット遅延変動X2の計測が指示され、その計測結果が取得される。
【００４１】
パス分類部１０２は、前記指標値の計測結果に基づいて、各パスを品質劣化に関して不良パスのグループおよび優良パスのグループを含む複数のグループに分類する。本実施形態では、パケットロス率X1に関しては、各パスがそのパケットロス率に基づいて、不良パスのグループ、優良パスのグループおよびその中間のパスのグループに分類され、中間パスは品質劣化箇所の推定に使用されない。また、パケット遅延変動X2に関しては、各パスがそのパケット遅延変動に基づいて複数のクラスタに分類される。
【００４２】
ネットワーク分割部１０３は、評価対象のネットワークを、その品質劣化を推定可能な最小単位である複数の候補箇所に分割する。本実施形態では、ネットワークが分岐および合流の無い複数の区間kiおよび各区間kiの分岐、合流点に位置するネットワーク機器njに分割され、各区間kiおよびネットワーク機器njが候補箇所とされる。
【００４３】
識別部１０４は、前記優良パスのみが通過する候補箇所を識別する。集計部１０５は、前記優良パスのみが通過する候補箇所を除いた残りの候補箇所の集合を対象に前記不良パスが通過する回数を集計する。推定部１０６は、前記候補箇所の中から、前記不良パスが通過する回数に基づいて不良箇所を推定する。本実施形態では、不良パスの通過数が最大の候補箇所が不良箇所と推定される
【符号の説明】
【００４４】
１…品質劣化箇所推定装置，１０１…計測部，１０２…パス分類部，１０３…ネットワーク分割部，１０４…識別部，１０５…集計部，１０６…推定部
【特許請求の範囲】
【請求項１】
エンドノード間に確立されるパスが少なくとも一つの経路候補を含むネットワークの品質劣化箇所推定装置において、
パスごとに品質劣化の指標値を計測する計測手段と、
前記指標値に基づいて、各パスを品質劣化に関して不良パスのグループおよび優良パスのグループを含む複数のグループに分類するパス分類手段と、
ネットワークを、その品質劣化を推定可能な最小単位である複数の候補箇所に分割するネットワーク分割手段と、
前記優良パスのみが通過する候補箇所を識別する識別手段と、
前記優良パスのみが通過する候補箇所を除いた残りの候補箇所を対象に前記不良パスが通過する回数を集計する集計手段と、
前記候補箇所の中から、前記不良パスが通過する回数に基づいて不良箇所を推定する推定手段とを具備したことを特徴とするネットワークの品質劣化箇所推定装置。
【請求項２】
前記品質劣化の指標値がパケットロス率であることを特徴とする請求項１に記載のネットワークの品質劣化箇所推定装置。
【請求項３】
前記品質劣化の指標値がパケット遅延変動であることを特徴とする請求項１に記載のネットワークの品質劣化箇所推定装置。
【請求項４】
前記分類手段は、各パスをそのパケットロス率に基づいて、不良パスのグループ、優良パスのグループおよびその中間のパスのグループに分類し、中間パスを品質劣化箇所の推定に使用しないことを特徴とする請求項２に記載のネットワークの品質劣化箇所推定装置。
【請求項５】
前記分類手段は、各パスをそのパケット遅延変動に基づいて複数のクラスタに分類し、
前記識別手段は、クラスタごとに当該クラスタに含まれない各パスの経路候補が共有する候補箇所を識別し、
前記集計手段は、クラスタごとに当該クラスタに含まるパスが各候補箇所を通過する回数を集計することを特徴とする請求項３に記載のネットワークの品質劣化箇所推定装置。
【請求項６】
前記ネットワーク分割手段は、ネットワークを分岐および合流の無い複数の区間および各区間の分岐、合流点に位置する複数のネットワーク機器に分割し、前記各区間およびネットワーク機器が候補箇所とされることを特徴とする請求項１ないし５のいずれかに記載のネットワークの品質劣化箇所推定装置。
【請求項１】
エンドノード間に確立されるパスが少なくとも一つの経路候補を含むネットワークの品質劣化箇所推定装置において、
パスごとに品質劣化の指標値を計測する計測手段と、
前記指標値に基づいて、各パスを品質劣化に関して不良パスのグループおよび優良パスのグループを含む複数のグループに分類するパス分類手段と、
ネットワークを、その品質劣化を推定可能な最小単位である複数の候補箇所に分割するネットワーク分割手段と、
前記優良パスのみが通過する候補箇所を識別する識別手段と、
前記優良パスのみが通過する候補箇所を除いた残りの候補箇所を対象に前記不良パスが通過する回数を集計する集計手段と、
前記候補箇所の中から、前記不良パスが通過する回数に基づいて不良箇所を推定する推定手段とを具備したことを特徴とするネットワークの品質劣化箇所推定装置。
【請求項２】
前記品質劣化の指標値がパケットロス率であることを特徴とする請求項１に記載のネットワークの品質劣化箇所推定装置。
【請求項３】
前記品質劣化の指標値がパケット遅延変動であることを特徴とする請求項１に記載のネットワークの品質劣化箇所推定装置。
【請求項４】
前記分類手段は、各パスをそのパケットロス率に基づいて、不良パスのグループ、優良パスのグループおよびその中間のパスのグループに分類し、中間パスを品質劣化箇所の推定に使用しないことを特徴とする請求項２に記載のネットワークの品質劣化箇所推定装置。
【請求項５】
前記分類手段は、各パスをそのパケット遅延変動に基づいて複数のクラスタに分類し、
前記識別手段は、クラスタごとに当該クラスタに含まれない各パスの経路候補が共有する候補箇所を識別し、
前記集計手段は、クラスタごとに当該クラスタに含まるパスが各候補箇所を通過する回数を集計することを特徴とする請求項３に記載のネットワークの品質劣化箇所推定装置。
【請求項６】
前記ネットワーク分割手段は、ネットワークを分岐および合流の無い複数の区間および各区間の分岐、合流点に位置する複数のネットワーク機器に分割し、前記各区間およびネットワーク機器が候補箇所とされることを特徴とする請求項１ないし５のいずれかに記載のネットワークの品質劣化箇所推定装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１１−２１１３５８（Ｐ２０１１−２１１３５８Ａ）
【公開日】平成２３年１０月２０日（２０１１．１０．２０）
【国際特許分類】
【出願番号】特願２０１０−７５２０５（Ｐ２０１０−７５２０５）
【出願日】平成２２年３月２９日（２０１０．３．２９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２３年１０月２０日（２０１１．１０．２０）
【国際特許分類】
【出願日】平成２２年３月２９日（２０１０．３．２９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]