(57)【特許請求の範囲】
【請求項１】
監視対象パケットの送信状態と受信状態を比較することによりネットワーク品質を監視し、品質低下を発見した場合には品質低下発生区間を判定する方法であって、
品質測定監視対象となる網に測定装置を複数台設置し、それぞれの測定装置においてパケットをプローブして得られたパケット通過時刻系列をもとにして、相互相関関数を計算する工程と、
パケットもしくはパケット群の発生周期を判定し、１周期範囲の時刻系列を取り出し、その時刻系列内における相関値の最大値を用いて品質評価を行う工程と、
品質低下が発生していると判断した場合には、予めパケット転送経路情報から木構造となる論理トポロジーを作成し、その論理トポロジーを利用して品質低下発生個所を判定する工程とを具えることを特徴とするパケット網における品質状態監視方法。
【請求項２】
監視すべきパケット網に配置され、互いに同期した周波数源を有する複数のパケットプローブ装置から出力されたパケット送信時刻列を表す送信側データ系列及びパケット受信時刻列を表す受信側データ系列を用いてパケット網の品質を監視し、当該パケット網に品質低下が生じたことが判明した場合、品質低下部位を判定するパケット網における品質状態監視方法であって、
前記送信側データ系列及び受信側データ系列を受け取り、これら送信側データ系列及び受信側データ系列を用いて相互相関関数を求め、求めた相互相関関数から品質低下が発生しているか否かを判定し、当該パケット網の品質評価結果を出力する工程と、
パケット網のパケット転送経路情報を受け取り、受信したパケット転送経路情報から木構造である論理トポロジーを作成する工程と、
前記出力された品質評価結果と、前記作成された論理トポロジーとに基づいて品質低下部位を判定する工程とを具えることを特徴とするパケット網における品質状態監視方法。
【請求項３】
請求項１又は２に記載のパケット網における品質状態監視方法において、試験パケットを生成してネットワーク品質を動的に監視する方法。
【請求項４】
請求項３に記載のパケット網における品質状態監視方法において試験パケットの生成方法としてマルチキャストを用いる方法。
【請求項５】
請求項３に記載のパケット網における品質状態監視方法において試験パケット生成方法として、複数本のユニキャストを利用する方法。
【請求項６】
請求項１又は２に記載のパケット網における品質状態監視方法において、相互相関関数を求めた後に、最大となる相関値を用いて品質評価を行う方法。
【請求項７】
請求項２に記載のパケット網における品質状態監視方法において、相互相関関数を求めた後に、パケットもしくはパケット群の発生周期を判定し、１周期範囲の時刻系列を取り出し、その時刻系列内における相関値の最大値を用いて品質評価を行う方法。
【請求項８】
請求項１又は２に記載のパケット網における品質状態監視方法において、相互相関関数を求めた後に、パケットもしくはパケット群の発生周期を判定し、１周期範囲の時刻系列を取り出し、その時刻系列内における相関値の最大値と最小値を求め、これらの差を用いて品質評価を行う方法。
【請求項９】
請求項１又は２に記載のパケット網における品質状態監視方法において、相互相関関数を求めた後にパケット送信時刻系列の自己相関関数を求め、パケットもしくはパケット群の発生周期を判定し、１周期範囲の時刻系列を取り出し、その時刻系列内における相互相関関数の積分値と自己相関関数の積分値を求め、相互相関関数の積分値を自己相関関数の積分値で割った値を用いて品質を評価する方法。
【請求項１０】
請求項１又は２に記載のパケット網における品質状態監視方法において、相互相関関数を求めた後にパケットもしくはパケット群の発生周期を判定し、１周期範囲の時刻系列を取り出し、取り出した時刻系列に対して縦軸方法により指数的な重み付けを行い、その時刻系列内における相関値の最大値と最小値を求め、これらの差を用いて品質評価を行う方法。
【請求項１１】
請求項１又は２に記載のパケット網における品質状態監視方法において、相互相関関数を求めた後に、パケット送信時刻系列の自己相関関数を求め、パケットもしくはパケット群の発生周期を判定し、１周期範囲の時刻系列を取り出し、取り出した時刻系列に対して縦軸方法により指数的な重み付けを行い、その時刻系列内における相互相関関数の積分値と自己相関関数の積分値を求め、相互相関関数の積分値を自己相関関数の積分値で割った値を用いて品質を評価する方法。
【請求項１２】
請求項１又は２に記載のパケット網における品質状態監視方法において、前記品質低下発生個所を判定する際、属性付のトークンを論理トポロジー上に伝播させることにより、分岐・合流といった閉じた領域を短絡除去して木構造を求める方法。
【請求項１３】
請求項１又は２に記載のパケット網における品質状態監視方法において、ｅｎｄ・ｅｎｄの測定結果から品質低下発生箇所を判定し、その測定結果から品質低下箇所が観測された際に、品質低下が判定されたパスから、論理トポロジーの構造を利用して品質低下が発生していないと考えられるノードとリンクを除去することにより、品質低下を示すリンクとノードを求める方法。
【請求項１４】
請求項１３に記載のパケット網における品質状態監視方法において、品質低下箇所が部分木として判定された際に、リーフ間においてｅｎｄ・ｅｎｄ測定結果の相関を求め、その結果と部分木の構造を利用することにより、さらに細かく品質低下箇所を推定する方法。
【請求項１５】
請求項１から１４までのいずれか１項に記載のパケット網における品質状態監視方法において、当該パケット網を、パケットの転送優先順位を転送クラスとして転送順位を分類し、クラス別に優先転送制御を行うＱｏＳ制御が行われるネットワークとしたことを特徴とする方法。
【請求項１６】
請求項１から１５までのいずれか１項に記載のパケット網における品質状態監視方法を用いて、優先転送されたネットワークの優先度誤りを監視することを特徴とするネットワークの監視方法。
【請求項１７】
監視すべきパケット網に配置され、互いに同期した周波数源を有する複数のパケットプローブ装置から出力されたパケット送信時刻列を表す送信側データ系列及びパケット受信時刻列を表す受信側データ系列を用いてパケット網の品質を監視し、当該パケット網に品質低下が生じたことが判明した場合、品質低下部位を判定するパケット網の品質状態監視装置であって、
前記送信側データ系列及び受信側データ系列を受け取り、これら送信側データ系列及び受信側データ系列を用いて相互相関関数を求め、求めた相互相関関数から品質低下が発生しているか否かを判定し、当該パケット網の品質評価結果を出力する品質監視装置と、
パケット網のパケット転送経路情報を受け取り、受信したパケット転送経路情報から木構造である論理トポロジーを作成するトポロジー把握装置と、
前記品質監視装置から出力された品質評価結果とトポロジー把握装置から出力された論理トポロジーとに基づいて品質低下部位を判定する品質低下箇所判定装置とを具えることを特徴とするパケット網の品質状態監視装置。
【請求項１８】
請求項１７に記載のパケット網の品質状態監視装置において、前記品質監視装置は、前記各送信側データ系列及び受信側データ系列について送信側の合成関数及び受信側の合成関数を生成する合成関数生成手段と、送信側合成関数と受信側の合成関数との間の相互相関を演算する相互相関演算手段と、得られた相互相関から品質低下が発生しているか否かを判定する品質低下判定手段とを具えることを特徴とする装置。
【請求項１９】
請求項１７又は１８に記載のパケット網の品質状態監視装置において、前記トポロジー把握装置は、前記パケットプローブ装置からパケットロス情報を受け取り、パケットの経路情報を推定する経路情報推定手段と、当該ネットワークの管理情報からパケットの経路情報を収集する経路情報収集手段と、経路情報収集手段から出力された経路情報から分岐及び／又は合流を短絡除去する分岐合流短絡除去手段と、前記経路情報推定手段からの出力及び分岐合流短絡除去手段からの出力に基づいて論理トポロジーを作成する論理トポロジーを作成手段とを具えることを特徴とする装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケット網の品質状態を監視し、品質情報が低下が判明した場合その部位を判定するパケット網の品質状態監視方法に関するものである。特に、本発明は、パケットの転送優先順位を転送クラスとして転送順位を分類し、クラス別に優先転送制御を行うＱｏＳ制御が行われるネットワークにおいて、優先転送制御を監視するのに好適な品質状態監視方法に関するものである。
さらに、本発明は、映像や音声転送といった、遅延変動や帯域変動の影響を受けやすい実時間アプリケーションのパケットの転送品質を監視するのに好適な品質状態監視方法に関する。
【０００２】
【従来の技術】
クラス別優先制御による品質制御監視を実現するためには、遅延変動の様子をクラス間で比較監視することにより実現できると考えられる。また、実時間アプリケーションを品質よく転送するためには、遅延変動が少ないことが求められる。このため、品質監視を実現するためには、以下のようにして片道遅延時間を算出する方法が考えられる。
・パケットプローブ装置において、周波数同期と時刻同期をおこなう。
・パケットプローブ装置間でパケットをプローブする。
・送信側と受信側のパケットプローブ装置からプローブ時刻付きのブローブデータ列を受け取る。
・検出されたパケットのプローブ時刻から片道遅延時間を計算し分布を求める。
【０００３】
次に品質監視を行う別の方法として、遅延変動を示すジッタを算出する方法が考えられる。ジッタを得るためには以下の処理を行う必要がある。
・パケットプローブ装置において、周波数同期をおこなう。
・パケットプローブ装置間でパケットをプローブする。
・送信側と受信側のパケットプローブ装置からプローブ時刻付きのプローブデータ列を受け取る。
・これらのデータ列から同一パケットを検索する。
・送受信間でのプローブ時刻から片道遅延時間を計算する。
・片道遅延時間からジッタを計算し分布を求める。
【０００４】
以上のように、片道遅延時間を測定するためには、パケットの送信時刻と受信時刻との差を求めて片道遅延時間を算出する必要がある。このため、片道遅延時間の測定ではパケットプローブ装置の時刻を全て一致（時刻同期）した上で、時計の進み方を同期（周波数同期）することが要求される。
【０００５】
ジッタを測定して品質監視を行う方法は、ジッタは片道遅延時間の差として求めるため、正確な時刻同期は必要としない。従って、ジッタの分布を求めて品質制御監視を行うためには、パケットプローブ装置の周波数同期が実現できればよい。なお、片道遅延時間やジッタを求めるためには、送信側と受信側のデータ列の組からプローブパケット数に相当する回数の同一パケット検索を行う必要がある。また、片道遅延やジッタの分布を求める方法では、品質変動の結果生じるパケットロスについて考慮されていない。
【０００６】
次に、片道遅延時間やジッタを求める方法により品質制御監視を行い、品質低下時にその個所を指摘するためには、パケットプローブ装置を監視対象ネットワーク内部に網羅的に配置して、各プローブ装置間での測定結果より品質低下区間を把握する方法が考えられる。この方法は、２対のプローブ装置間を測定区間と定め、測定区間内において片道遅延時間やジッタの計算を行い、その結果より品質低下の発生有無を判断する。品質低下が発生している場合にはその測定区間を品質低下箇所として報告する。この処理を全てのパケットプローブ装置で行うことにより、品質低下個所を判定することができる。
【０００７】
【発明が解決しようとする課題】
上述したように、片道遅延時間の測定のためには、正確な時刻同期と周波数同期が必要となる。しかし、近年ネットワークの広帯域化が進み、ｑｕｅｕｉｎｇｄｅｌａｙがない場合には、数μ秒／ｋｍといった最低遅延時間が提供されている。このため、片道遅延時間を求めるための時刻同期にはμ秒オーダーか、それ以下の精度が求められる。このような精度を実現するためにＧＰＳを利用する方法が考えられるが、設置箇所の限定といった問題が発生しており、パケットプローブを網羅的に分散配置することが困難な状況となっている。また、ＩＳＤＮを用いた時計同期方法が提案されているが、この方法では±10μ秒オーダー以下の精度で時刻を同期できない。
【０００８】
しかし，ＩＳＤＮを用いた周波数同期といった精度のよい周波数源があれば周波数同期が実現できる。周波数同期は数μ秒以下の精度を実現可能である。例えば１Ｇｂｉｔ／ｓのネットワーク上を１５００ｂｙｔｅのパケットが通過する時間は、１２μ秒であることから、１０--6 秒の精度で測定可能となる。そこで、周波数同期のみにより実現可能な測定方法、すなわち、ジッタを求めて品質監視を行うことが考えられる。
【０００９】
ここで、品質制御方法として優先度制御を行ったネットワークにおいて、優先度を高く設定したパケットと低く設定した他トラフィックの優先度が等しくなるという障害が発生した場合を想定する。この状況において、測定対象外のパケットのトラフィック量が多いと、試験パケットが常にｑｕｅｕｅの最後に位置する状態となる可能性がある。この場合には、遅延時間は長くなるが遅延変動が小さくなる可能性がある。このため、このような状態において、ジッタの分布を用いる方法を適用すると品質低下を発見できない。このような問題を回避するためには、常にｑｕｅｕｅの後方にパケットが位置する場合にはパケットロスの発生確率が非常に高くなっていることを考慮して、品質監視方法にパケットロスの要素が含まれる方法を選択する必要がある。
【００１０】
次に、品質低下箇所の把握方法について課題を述べる。障害発見後に品質低下箇所を把握するためには、パケットプローブ装置を網羅的に配置する必要がある。この際には、全てのパケットプローブ装置からプローブデータ列を受け取り、設定された監視区間内の両端のデータ列から、同一パケット検索を行う必要がある。網羅的にパケットプローブ装置を配置した場合には、一台のパケットプローブ装置の増加は一区間以上の監視区間の増加となり、ジッタ計算に必要となる同一パケット検索のためのテーブル数が増え処理時間が課題となる。さらに、遅延変動が大きい場合には、同一パケット検索のためのテーブルを大きくする必要があり、同一パケット検索に要する時間が非常に長くなる場合がある。
【００１１】
【発明の目的】
本発明の目的は、高精度時刻同期を用いずに、正確な周波数源のみを利用し、遅延変動の情報に加えてパケットロスの情報が含まれ、かつ、同一パケット検索を行うことなく品質監視を行う品質監視方法を提供することである。
さらに、本発明の別の目的は、パケットプローブ装置をネットワークに網羅的に配置することなく、ｅｎｄ−ｅｎｄ測定を利用して、品質低下が発生している品質低下箇所を判定する方法を提供することである。
【００１２】
【課題を解決するための手段】
図１は本発明によるパケット網における品質状態監視装置を具える品質状態監視システムの基本構成を示す。本発明による品質時刻監視装置は、パケット網１の品質状態を監視する品質監視装置２０、トポロジー把握装置３０、及び品質低下箇所判定装置４０から構成される。図１に示すように、高精度周波数源により駆動され時刻列生成機能を有するパケットプローブ装置１１〜１３を測定監視対象となるネットワーク１の端に複数設置する。パケットプローブ装置においてパケットをプローブしてｅｎｄ−ｔｏ−ｅｎｄ測定を行う。この際に、各パケットプローブ装置の時刻列生成機能により、送信側パケットプローブ装置１１においてパケット送信時刻列を求め、各受信側パケットプローブ装置１２及び１３においてパケット受信時刻列を得る。
【００１３】
送信側パケットプローブ装置１１により得られた送信時刻列及び受信側パケットプローブ装置１２及び１３により得られたパケット受信時刻列は、品質監視装置２０に供給する。品質監視装置２０において、Ｅｎｄ−ｔｏ−ｅｎｄ測定を行った結果得られたパケット送信時刻列とパケット受信時刻列より、合成関数作成機能２１と相互相関演算機能２２を用いて相互相関関数を求め、求めた相互相関関数に基づいて品質低下判定機能２３により品質低下の有無を判定し、品質低下判定結果を出力する。これにより、高精度時計同期と同一パケット検索を行うことなく、品質監視を実現する。また優先度の差がパケットロスとして観察される場合には、相関が低くなるため、例えば、ｑｕｅｕｅの後方に常にパケットが位置するといった品質低下についても測定可能となる。
【００１４】
トポロジー把握装置３０において、ネットワーク管理情報などにより収集されたパケット転送経路情報より、分岐合流短絡除去機能３１を用いて、経路情報の分岐や合流を短絡することにより除去する。次に、論理トポロジー作成機能３２により冗長な構造を取り除いて木構造となる論理トポロジーを作成する。ここで、木のルートは送信側パケットプローブ装置となり、リーフは全ての受信側パケットプローブ装置となる。方向はパケット転送方向を示す。この論理トポロジーを利用して、品質低下が発生している場合には、品質低下発生場所を判定する。
【００１５】
品質低下箇所判定装置４０において、品質監視装置２０から品質低下判定結果とデータ系列を受け取り、かつ、トポロジー把握装置３０から倫理トポロジーを受け取り、低下箇所判定機能４１により品質低下が発生している場合を把握する。次に、低下箇所推定機能４２により、さらに細かく低下箇所を推定する。そして、低下箇所判定機能４１及び低下箇所推定機能４２からの出力を表示装置５０に可視化表示することができる。
【００１６】
【発明の実施の形態】
図２に本発明の一実施形態として、本発明によるパケット網の品質状態監視装置の処理フローを示す。尚、図１で用いた構成要素と同一の構成要素には同一符号を付して説明する。図２において、太い実線で示した箇所が本発明に相当する。以下では、これらの機能を詳細に説明する。
（パケットプローブ装置）
パケットプローブ装置は、高精度な周波数源を利用して時計が運用されており、時計の進み方が正確に同期している。本装置は時刻列生成機能を持つ。以下では本機能の説明を行う。
「時刻列生成機能」
本機能では、パケットの通過時刻をサンプリング周波数ｆでサンプリングされたデータ系列に変換する。この際に、パケットがプローブされた時刻を１とし、それ以外を０としてデータ列を生成する。例えば、ｆ＝１０Ｈｚとし、０．０秒と０．３秒に試験パケットがプローブされた場合には、０．０秒＝１，０．１秒＝０，０．２＝０，０．３秒＝１とデータ系列を生成する。このデータ列は、時間間隔ｔで区切られて、品質監視装置２０へ連続して送信される。上記の例を用いると、ｔ＝１秒とした場合に、１０個のサンプルが１秒おきに品質監視装置２０へ送信される。
【００１７】
送信側時刻列より作成されたデータ系列をｘs c n とし、受信側時刻列より作成されたデータ系列をｘcpn として表す。ここで、ｃはこのデータ列が属する品質制御クラスを示し、０から順に１，２，３，......，ｃと示され、例えば１からｃの順に優先度が高くなる。受信側パケットプローブ装置に１から順に１，２，３，......，Ｎと番号を与え、ｐは、受信側パケットプローブ装置番号を示す。クラス分けされていないネットワークの場合には、Ｃは一つの固定値のみとなる。
【００１８】
試験パケットを用いて品質を動的に評価する場合には、一台のパケットプローブ装置から、マルチキャストや複数本のユニキャストを用いて、他の全てのパケットプローブ装置に試験パケットが送られる。試験パケットは一定の間隔△Ｔで周期的な特性をもつ連続した一定のパターンとして形成される。パケットプローブ装置は、このように生成された試験パケットに注目して、試験パケットの送信もしくは受信時刻を収集する。ｅｎｄ−ｔｏ−ｅｎｄにおいて流れるトラフィックの品質を受動的に評価する場合には、送受信間の端点にあるパケットプローブ装置において、当該トラフィックのみをプローブして送信時刻、受信時刻を収集する。なお事前に転送されているパケットの周期性を測定し、その値を△Ｔとする。例えば、一定の間隔でパケットが生成されている場合には、その間隔を△Ｔとする。
【００１９】
（品質監視装置）
ネットワークの品質を監視する品質監視装置２０は、合成関数作成機能２１、相互相関演算機能２２、品質低下判定機能２３により実現される。以下では、これらの装置の処理フローに従って動作内容の説明を行う。
「合成関数作成機能」
本装置では、上述の送信側及び受信側データ系列ｘs c n 及びｘcpn （０≦ｃ≦Ｃ，１≦ｐ≦Ｎ）に対して、あらかじめ用意されている関数ｇ、例えば、
［外１］
0003834258.tif 000002
といった関数との合成関数である新たな系列ｈs c n , ｈcpn を得る。実際には、関数ｇを周波数ｆでサンプリングした系列ｇn を作成し、ｘs c n , ｘcpn とｇn の合成関数であるｈs c n , ｈcpn を、高速フーリェ変換（ＦＦＴ）を用いて算出する。
【００２０】
「相互相関演算機能」
本装置では、合成関数作成機能２１により合成された系列ｈs c n , ｈcpn （０≦ｃ≦Ｃ，１≦ｐ≦Ｎ）を受け取り、送信側データ系列ｈs c n と一つの受信側データ系列ｈcpn を対にして相互相関をＦＦＴによって求め、新たな系列ｒcpn を得る。ここでは、Ｃ×Ｎ回の計算が行われる。なお、品質低下判定機能２３で必要となる場合には、ｈs c n の自己相関をＦＦＴにより求め、新たな系列ｒs c n を求める。なお、トラフィックを受動的にプローブしている際に、△Ｔが求められていない場合には、本機能においてｈs c n を算出して△Ｔを求める。ここで、ｒs c n , ｒcpn に対して
［外２］
0003834258.tif 000003
といった指数的なウェイトをかけた結果を新たなｒs c n , ｒcpn とする方法も考えられる。
【００２１】
「品質低下判定機能」
本装置では、相互相関演算機能２２より全てのデータ列ｒs c n , ｒcpn （０≦ｃ≦Ｃ，１≦ｐ≦Ｎ）を受け取り、０から△Ｔの範囲、もしくは、最初のピークが現れるラグをｔcpとし、ｔcpからｔcp＋△Ｔの範囲となるデータを抜き出し、これを新たなｒs c n , ｒcpn とする。データ点数は、ｍ＝△Ｔ／ｆとなる。
また、これらを用いて、以下のいずれかの方法により品質評価を行う。
・ｒcpn の最大値と最小値を求め、その差の絶対値をＥcpとする。
・ｒcpn の最大値を求め、その値をＥcpとする。
・
［外３］
0003834258.tif 000004
となるＥを求め、
［外４］
0003834258.tif 000005
となるＦcpを求める。次に、ＥcpをＦcpで割ることによりＥcpを正規化する。
・０から△Ｔの範囲において、バスタブカーブとなる関数を周波数ｆでサンプリングした系列ｗm を用意し、
［外５］
0003834258.tif 000006
となるＥを求め、
［外６］
0003834258.tif 000007
となるＦcpを求める。次に、ＥcpをＦcpで割ることによりＥcpを正規化する。
【００２２】
または、データ系列の範囲を抜き出さずに、以下のようにしてＥを求める。
ｒcpn のパワースペクトルを求め、△Ｔの周期となる周波数成分のスペクトル密度をＥcpとする。なおｒs c n のパワースペクトルを求め、△Ｔの周期となる周波数成分のスペクトル密度でＥcpを正規化する。
次に、Ｅcpが１に近いスレショルド値を超えない場合には、１cp＝０とし、スレショルドを超えた場合には１cp＝１とする。優先度誤りを監視する場合には、受信側パケットプローブ番号において、Ｅ0P＜Ｅ1P＜Ｅ2P＜・・・＜ＥNPであることを確認する。この関係が保たれている場合には、品質低下判定結果１ついて、１P ＝１とする。これはクラス間での品質低下が発生していないことを示す。上記関係が保たれていない場合には、１P ＝０とする。これは、クラス間での優先度誤りが発生していることを示す。なお、以降では、ある特定のクラスにおける１cpについても１P と表記する。
【００２３】
次にこの操作を全てのＥに対して行い、１P と、Ｅcpもしくはｈcpn もしくはｒcpn を出力値とする。
以上の操作を連続して行うことにより常時監視が実現される。
【００２４】
（トポロジー把握装置）
トポロジー把握装置３０は、経路情報推定機能３３、経路情報収集機能３４、分岐合流短絡除去機能３１、及び論理トポロジー作成機能３２により実現される。経路情報推定機能３３と経路情報収集機能３４は、従来技術により実現可能である。例えば、経路情報推定機能３３は、受信側パケットロープにおいてパケットロスを観測することにより行うことができ、または、パケット伝播経路を管理している場合にはその管理情報を用いて、または、ＳＮＭＰ（Simple Network Management Protocol）といったネットワーク管理プロトコルを利用することにより実現可能である。従って、パケットプローブ装置からパケットロス情報が経路情報推定機能３３に供給され、当該機能３３により推定された経路情報が論理トポロジー作成機能３２に供給される。ここでは、これらの技術によりパケット転送経路が得られたものとして説明を続ける。なお、パケット転送経路は、一台の送信機から受信機までの、ループのない経路となる。
【００２５】
経路情報収集機能３４は、パケット伝搬経路を管理している場合の管理情報又はネットワーク管理プロトコルを利用することにより経路情報を収集し、収集された経路情報を分岐合流短絡除去機能３１及び論理トポロジー作成機能３２に供給する。
【００２６】
分岐合流短絡除去機能３１、論理トポロジー作成機能３２では、経路情報推定機能３３もしくは経路情報収集機能３４により得られたパケット転送経路を、品質低下個所判定装置４０において利用可能な論理トポロジーに変換する機能を有する。論理トポロジーは木構造であり、ノードＶ、リンクＬ、ルートＶｒ、リーフＶｌにより構成される。リーフＶｌは回線とルータやスイッチの集合を示し、通常ルータやスイッチからなる経路の分岐点を示す。リンクＬは回線とルータにより構成される分岐のないパケット転送経路を示す。ルートＶｒは送信側パケットプローブを示し、リーフＶｌは受信側パケットプローブを示す。これらは以下の規則に従って接続されている。
・Ｖｒは、１個以上のノードＶが、もしくは、一個以上のリーフＶ１が、もしくは、一個以上のノードＶと一個以上のリーフＶ１が、リンクＬにより接続されている。
・リーフＶ１は、２個以上のノードＶが、もしくは、2 個以上のリーフＶ１が、もしくは、一個以上のノードＶと１個以上のリーフＶ１が、リンクＬにより接続されている。
・リーフＶ１は、１個のノードＶもしくは１個のルートＶｒにリンクＬにより接続されている。
【００２７】
実際のパケット転送経路は、一台のパケット送信機から見た場合に、その経路を有向グラフとすると、全てのルータやスイッチでは単方向連結するように経路設定されており．強連結成分は存在しない。しかし、分岐した後に合流する経路を持つ構造となる可能性がある。このため、本発明では、上記のルールに従った木構造となる論理トポロジーを得るために、第一段階として分岐合流短絡除去機能により、分岐して合流する経路を発見して、分岐と合流で閉じた領域にあるリンクとノードを全て短絡除去し、木構造となるトポロジーを得る作業を行う。なお、マルチキャストを用いて測定を行う場合には、分岐合流短絡除去機能を利用せず、経路情報推定機能３３もしくは経路情報収集機能３４から、直接論理トポロジー作成機能にマルチキャスト木を出力することも可能である。強連結成分（ループ）の存在は経路制御の問題であり、本発明では経路制御が正常に行われて強連結成分がないことを前提としている。
【００２８】
「分岐合流短絡除去機能」
本装置では、分岐と合流で閉じた領域にあるリンクを全て短絡除去する。短絡除去を行う一つの方法として、以下ではリンクを２色に色分けする方法による分岐合流短絡除去機能の一実施例を示す。
伝播トークンは、１個以上のデータトークンを持つ。データトクンは、分岐数、分岐ノード番号、色、及び始発リーフ番号の組からなるデータを持つ。またデータトークンは、分岐数、分岐ノード番号、色、及び始発リーフ番号の組からなるデータのスタック領域を持つ。また、パケット転送経路のノードは重複しないノード番号を持つ。この際に、トークンを以下のルールに従って流す。
・一つのリンク上では、一つの伝播トークンのみが有向木（経路テーブル）の方向と逆向きに通過できる。
・伝播トークンがノードに到着した際には、伝播トークンから全てのデータトークンが取り出される。
・ノードから出力される場合には、全てのデータトークンが伝播トークンに包まれる。
・データトークンの初期の属性は、分岐数＝なし、分岐ノード番号＝なし、色＝白色、スタックは空であり、トークンが生成されたリーフ番号が始発リーフ番号として与えられている。また、リンクの初期属性は白色である。
・伝播トークンが分岐、すなわち、２本以上の入力を持つノードにたどりついた際には、伝播トークンからデータトークンを取り出し、全てのデータトクンについて、現在の属性をスタックに格納し、分岐数＝分岐リンク数、色＝赤色、分岐ノード番号＝ノード番号を新たな属性として持たせる。始発リーフ番号は変更しない。次に、全てのデータトークンを一つの伝播トークンで包み、伝播トークンのコピーを作成し、同一伝播トークンを全てのリンク上に流す。
・リーフから複数に分岐している場合には、上記と同様の属性を持つデータトクンを生成して、そのデータトクンを一つの伝播トークンで包み、伝播トークンのコピーを作成し、同一伝播トークンを全てのリンク上に流す。
・赤色属性を持つデータトークンを含む伝播トークンが流れたリンクでは、リンクの属性が白色の場合には赤色と変更する。リンクの属性は赤色から白色となることはない。
・トークンが合流、すなわち、２本以上の出力を持つノードにたどり着いた場合には、全てのリンクから伝播トクーンが到着するまで待機して、以下の動作を行う。
同一の分岐ノード番号を持ち、かつ、同一の始発リーフ番号と分岐ノード番号を持つデータトークンについて、データトークンの個数が，データトークンの属性である分岐数と等しい場合には、データトークンの属性をスタックから取り出した属性と入れ替えて一つのトークンにまとめる。この作業を可能な限り繰り返し行う。
まとめるデータトークンがない場合には、全てのデータトークンを一つの伝播トークンで包んで出力する。
【００２９】
全てのリーフから上記のルールに従ってトークンを渡すことによって、リンクを色分けすることができる。このようにして色分けされたリンクの中で、赤色部分について短絡除去を行い、一つのノードとすることにより、木構造となる論理トポロジーを得ることが出来る。
【００３０】
図３に動作例を示す。図３において、太い実線は赤色属性を持つリンクを示し、細い実線は白色属性を持つリンクを示し、矢印の向きは経路テーブルが指す方向を示す。丸はノードであり、ノード番号が丸の中に示されている。四角はデータトークンであり，（ａ，ｂ，ｃ，ｄ）は属性を示し，［（ａ，ｂ，ｃ，ｄ）］はスタックに格納された属性を示す。ここで、ａは分岐数を示し、ｂは分岐ノード番号を示し、ｃは色属性を示し、ｄは始発リーフ番号を示す。スタックでは、属性は上に詰まれるように格納され上から順に取り出される。吹き出しは伝播トークンを示す。
【００３１】
図３では、トークンが始点リーフ番号１から出されたとして例示している。初期時は、全てのリンクの属性は白色であり、伝播トークンの中には一つのデータトクンがあり、（−，−，白，１）の属性を持つ。この伝播トークンが有向グラフ上を逆向きに流れている。ノード６において２本に分岐されるため、データトクンは、（２，６，赤，１）の属性となり、（−，−，白，１）の属性はスタックに格納される。赤色属性である、データトークンを持つ伝播トークンが通過したため、リンクの属性が赤色となる。次に、ノード５において、再度分岐が行われるため、データトークンは、（２，５，赤，１）の属性となり、（２，６，赤，１）の属性はスタックに格納される。ノード２において合流が行われるが、まとめることが可能なデータトークンが存在しないため、全てのデータトークンを一つの伝播トークンにまとめて上流に渡す。ノード１において合流が行われる。まず、（２，５，赤，１）の属性を持つデータトークンが２個現れるため、一つのデータトークンとしてまとめ、スタックから取り出した（２，６，赤）となる属性を与える。さらに、ノード１では、（２，６，赤，１）の属性を持つデータトークンが２個となるため、これらもまとめて、一つのデータトークンとする。この結果、図の最後のように、合流、分岐箇所が赤色リンクとして表現され、このリンクを短絡除去することにより、２本のリンクと一個のノードに変更することが出来る。
【００３２】
「論理トポロジー作成機能」
本装置では分岐合流短絡除去機能により得られた木構造をもとにして、前述した規則に従った構造となるように変更を行う。本装置では、一本のリンク入力と持ち、一本のリンクを出力と持つノードとリンクからなる部分を一本のリンクに変更する。図４に実際の変更を例示する。図４において、丸はノードを示し、矢印はリンクを示し、四角はリーフを示している。さらに、短絡するノードについて斜線で示してある。以上の▲１▼▲２▼に示した装置により論理トポロジーが作成され、トポロジー把握装置の出力となる。
【００３３】
（品質低下個所判定装置）
品質低下個所判定装置４０は、品質監視装置２０からＩP を受け取り、低下箇所判定機能４１と低下箇所推定機能４２によって品質低下個所を推定する機能である。以下ではこれらの装置の処理順序に従って説明を行う。
「低下箇所判定機能」
品質監視装置２０が品質低下の発生を判断した際に、低下箇所判定機能４１は品質監視装置２０から品質監視結果を受け取り、トポロジー把握装置３０から論理トポロジーを受け取る。低下箇所判定機能はこれらの結果を用いて処理を行う。
【００３４】
図５を用いて、基本的な判定方法を説明する。低下箇所判定機能は、品質監視装置からＩP を受け取り、低下箇所判定を行う。図５の左側に示すトポロジー情報と品質監視結果を受け取った場合に、ルートＶｒからリーフＶｌ２、Ｖｌ３への経路では、送信、受信パターンに違いが少なく、すなわち、パケットロスがなく、遅延変動が少ない品質であるといえる。しかし、リーフＶｌ１への経路上において、品質低下が発生している。ここでは、リーフＶｌ１への経路において、リーフ２、３への経路以外の箇所において、もしくは、リーフ２、３への経路とリーフ１への経路の分岐点での出力インターフェース部分において品質低下が発生していると考えられる。そこで、リーフ１への経路の中で、リーフ２、３への経路に含まれないリンクにマークをつけ、さらに、リーフ２、３への経路からリーフ１への経路の分岐点となるノードにマークを付ける。このマークの付いた箇所を品質低下が発生した可能性が高い箇所として出力する。図５において、品質低下が発生したリンクにマークを付して明瞭にする。このように、低下箇所判定機能４１は、品質監視装置から供給された品質低下判定結果とトポロジー把握装置３０から供給された論理トポロジーとに基づいて品質低下が生じたリンク部分を特定する。
【００３５】
以降では、論理トポロジーの構造に従って詳細な説明を行う。トポロジー把握装置から受け取ったトポロジー情報と、品質監視装置から受け取った一つのクラスに関する情報、もしくは、優先度誤りの判定結果を図６に例示する。図６において、リーフ内部の数字はリーフ番号を、括弧でくくられた内容はリーフの属性を示す。（○）は品質低下が発生していないこと、すなわち、ＩP ＝１であり、（×）は品質低下が発生したこと、すなわち、ＩP ＝０であることを示す。丸はノードを示し、ノード内部の数字はノード番号を示す。
【００３６】
最初に、リーフのみが接続しているノードにおいて、以下のルールに従って属性を付与する。図６では、ノード７，９，１０，１１，１３，１４，１５，１６，１７が対象となる。
・リーフの属性が全て（○）の場合には。ノードに（○，○）の属性を与える。
・リーフの属性が全て（×）の場合には。ノードに（×，×）の属性を与える。
・リーフの属性が（○）と（×）の場合には。ノードに（×，○）の属性を与える。
【００３７】
この結果を、図７に例示する。なお、（Ａ、Ｂ）の表記については、Ａはそのノードにおける品質状態を示し、これを自ノード状態と呼ぶ。Ｂはそのノードから上位部分において品質低下が発生した可能性を示し、これを伝播状態と呼ぶ。
【００３８】
次に、属性を持つノードとリーフのみを子としてもつノードについて、以下に従って属性を付与する。図では６、８、12が対象となる。
・全ての子ノードの伝播状態が○であり、子にリーフが存在する場合には全ての子リーフの属性が○の場合に、（〇，〇）とする。
・全ての子ノードの伝播状態が×であり、子にリーフが存在する場合には全ての子リーフの属性が×の場合に。（×，×）とする。
・子にリーフが存在する場合にはリーフの属性も含めて、子ノードの伝播状態に○と×が混在する場合に、（×，○）とする。
【００３９】
なお、ルートＶｒの属性も上記と同様とする。上記操作を繰り返し行った結果を、図８に例示する。
【００４０】
自ノード状態が×の場合には、下位ノード、もしくは、リーフにおいて品質低下が観測できることを示す。これは、上位ノードから既に品質低下が発生している可能性と、自ノードを含め自ノードから下位ノードの間で発生している可能性の二つが考えられる。しかし、自ノードの伝播状態が○である場合には、下位ノードの一部で品質低下が発生していない箇所があることを示すため、上位ノードから自ノードまでの区間において品質低下が発生している可能性が低いと考えられる。そこで、自ノードを含め自ノードから伝播状態が×となる子ノードヘのリンク、もしくは、（×）の属性を持つリーフヘのリンクで品質低下が発生した可能性が高いと考える。
【００４１】
前段落の仮定をもとにして、以下のルールに従ってマークを付与し、このマークの付いたノードとリンクが示すスイッチやルータの集合が、品質低下を起こした可能性のある箇所として低下箇所判定機能の出力とする。
・ルートも含めて自ノード状態が×となるノードにマークを付与する。
・マークが付与された個々のノードから伝播状態が×となる子ノードヘのリンク、もしくは、（×）の属性を持つリーフヘのリンクにマークを付ける。
【００４２】
この結果を図９に示す。なお、ルートの属性が（×，×）の場合には、ルートから見た子ノードに、もしくは、リーフにマークを付与し、かつ、そのノードもしくはリーフヘのリンクにマークを付ける。なお、図９において、ノード番号１，３，６，７，１５，１４の部分木内では、どの区間において品質低下が発生しているか判定できない。そこで、このような部分木について解析の必要があれば、品質低下が発生した可能性がある箇所を低下箇所推定機能４１により推定する。
【００４３】
「低下箇所推定機能」
（×，×）属性を持つノードやリーフが部分木を構成している場合には、その部分木を全て取り出す。以降では、取り出された部分木の一つについて推定方法を示すが、低下箇所推定機能４２は取り出された全ての部分木について以下の処理を行う。品質低下箇所を推定するための方法として、部分木内部の全てのリーフに属するデータ系列ＥCPの履歴データ（過去24時間164 時間といった時系列データ）や、ｈCPn もしくはｒCPn を用いて相関を求めて低下個所を推定する方法が考えられる。簡単な説明を図１０を用いて行う。
【００４４】
図１０において、上下とも相関関係からリーフＶｌ２とＶｌ３には、同一のパケット時刻列が到着していることがわかる。しかし、リーフＶｌ１にはリーフＶｌ２及び３とは異なるパターンでパケットが到着している。品質低下個所を通過した後の経路において、品質低下個所がない場合には、ＥCP、ｈCPn 、ｒCPn といったデータ系列間の相関関係が高くなると考えられる。このため、図の上については、ルートＶｒからリーフ１へ至る経路上とルートＶｒからノード２に至る経路上において、品質低下が発生している可能性があると考えられる。図の下については、ルートＶｒからリーフＶｌ１へ至る経路上に品質低下が発生している可能性があると考えられる。図１０では、このようにして求めた推定箇所にマークを付与している。低下箇所推定機能は、マークが付与された箇所を推定箇所として出力する。以降では、新たに図１１で示す木構造を用いて詳細に説明を行う。
【００４５】
木の中で、リーフと、リーフのみを子として持つノードとで構成される部分木を一つのグループとする。図１２にグループ化の結果を示す。図１２において、点線で囲まれた部分木がグループとなる。個々のグループにおいて、リーフに対応するデータ系列ＥCPの履歴データ（過去２４時間、１６４時間といった時系列データ）、もしくは、ｈCPn 、もしくは、ｒCPn を用いて、グループ内のリーフの全組み合わせで相関の強弱を求める。計算の結果。相関が高い組み合わせは「〇」とし、低い組み合わせは「×」とする。この結果を利用して、グループ内のノードとリンクに対して以下のルールに従って属性を付与する。
・グループ内の全組み合わせが「〇」の場合には、グループ内の全てのノードとリンクに（○）の属性を付与する。
・グループ内の全組み合わせが「×」の場合には、グループ内の全てのノードとリンクに（×）の属性を付与す
・組み合わせの属性に「〇」と「×」が混在する場合には、ノードに（×）の属性を付与し、さらに、「〇」の組み合わせに対応する２つのリーフに至る２本のリンクに（○）の属性を付与し、それ以外のリンクに（×）の属性を付与する。
【００４６】
この結果を図１３に示す。なお、相関の計算数を減らすための一方法として、計算対象となるリーフを頂点に持つ多角形を作成し、フルメッシュ状を引き、三角形に注目して相関を求める方法が考えられる。例えば、ａ，ｂ，ｃ，ｄ，ｅからなる５つのリーフがある場合に、五角形の頂点をそれぞれａ，ｂ，ｃ，ｄ，ｅとし、ａ，ｂ，ｃの三角形に注目した祭に、ａ−ｂは〇と計算され、ｂ−ｃは×と計算された場合には、ａ−ｃが×となる。ｃ−ｄが×と計算された場合には、ａ−ｃは計算する必要があり、ａ−ｅが○と計算された場合には、b −e は○となる。これらは以下のようにまとめられる。
【００４７】
・２辺が○の場合には、３辺目は○とする。
・１辺が○であり、他の１辺が×の場合には。３辺目は×とする。
・2 辺が×の場合には、3 辺目は計算する。
【００４８】
次に、以下のように、代表データ系列群を選択し、ノードに与える。
・グループ内の全組み合わせが「〇」の場合には、任意に一つのリーフに対応するデータを代表データ系列群とする。
・グループ内の全組み合わせが「×」の場合には、全てのリーフに対応するデータを代表データ系列群とする。
・組み合わせに「〇」と「×」が混在する場合には「〇」となる組み合わせに注目し、関連のある（閉じた）組み合わせから相関の最も高い組み合わせを選択してデータを任意に一つ選び出し、他は対象外とする。例えば、図１３においては、ノード８の属するグループにおいて閉じた組み合わせはリーフＶｌ５，６，７であり、例えば、リーフＶｌ５のデータを代表データ系列群へ含む。また、ノード１０においては、リーフＶｌ１０と１１，１２と２２の二つがそれぞれ独立に閉じた組み合わせとなるため、例えば、リーフ１０と１２のデータを代表データ系列群へ含む。残りの「×」となる組み合わせの全リーフに対応するデータも代表データ系列群へ含む。この結果を図１４に示す。
【００４９】
次に、子に属性が付与されたノードと前段で演算対象とされていないリーフを持ち、自らは属性を付与されていないノードを処理対象ノードとする。これらのノードとリーフにより構成される部分木を新たなグループとする。図１４を例とすると、ノード４，１１が処理対象ノードとなり、グループは点線で囲まれている。
【００５０】
個々のグループにおいて、処理対象ノードの子ノードが持つ代表データ系列群について相関を求める。この際に、代表データ系列群は、処理対象ノードから見た子ノードに属する単位でまとめられ、これを部分代表データ系列群と呼ぶ。子にり−フがある場合には、リーフに対応するデータ系列を一つの部分代表データ系列群とする。
【００５１】
処理対象ノードでは、部分代表データ系列群間で相互相関を計算する。部分代表データ系列群内のデータ系列間では組み合わせない。例えば、処理対象ノードに子ノードＡ，Ｂが存在し、ノードＡの代表データ系列群が1 ，2 であり、ノードＢの代表データ系列群が３，４である場合には、１，２と３，４という二組の部分代表データ系列群にまとめられ。組み合わせは１−３、１−４、２−３、２−４となる。
【００５２】
部分代表データ系列群間での相関の計算の結果、一つでも「○」となる組み合わせがある場合には、部分代表データ系列群間の相関は（○）とする。全ての組み合わせが「×」の場合には、部分代表データ系列群間の相関は（×）とする。
求めた相関の結果を用いて以下のようにノードとリンクに属性を与える。
・部分代表データ系列群間の相関が全て（○）の場合には、グループ内の処理対象ノードとリンクに対して「○」の属性を与える。
・部分代表データ系列群間の相関が全て（×）の場合には、グループ内のノードとリンクに対して「×」の属性を与える。
・部分代表データ系列群間の相関に、（○）と（×）が混在する場合には、（○）となる部分代表データ系列に対応する子ノードと子ノードへ至るリンクに「○」の属性を付与し、残りの子ノードとリンクに「×」の属性を与える。また、処理対象ノードに「×」の属性を与える。
【００５３】
次に、代表データ系列群を選定する。この結果を図１５に示す。
・グループ内の組み合わせが「〇」の場合には、相関の最も高い組み合わせの中から任意に一つのデータを代表データ系列群とする。
・グループ内の全組み合わせが「×」の場合には、全てのデータを代表データ系列群とする。
・組み合わせに「〇」と「×」が混在する場合には、「〇」となる組み合わせの中に注目し関連のある（閉じた）組み合わせから相関の最も高い組み合わせを選択してデータを任意に一つ選び出し、他は対象外とする。例えば、図１５においては、部分代表データ系列７と８の間において、２−５と４−９という２種類の閉じだ組み合わせがある。この場合は例えば、２，４を代表データとし、５，９を対象外とする。残りの「×」となる組み合わせの中で対象外とならなかったデータも代表データ系列群とする。
【００５４】
この結果を図１６に例示する。この後、新たな処理対象ノードを決定して同様の計算を行う。以上の操作を処理対象ノードがなくなるまで行う。最後に（Ｘ）の属性を持つノードとリンクにマークを付ける。実際の表示例を図１７に示す。
【００５５】
【発明の効果】
本発明により、優先度制御を行ったネットワークの品質制御の状態を監視し、優先度誤りといった制御異常状態が把握可能になる。また、品質異常が発生した際に、異常箇所を把握することができる。品質測定時に片道遅延時間といった時刻に関する品質測定を不要とすることができる。これにより、複数箇所に分散した測定装置が周波数同期のみを実現することにより、品質が可能になる。
【図面の簡単な説明】
【図１】  パケット網における品質状態監視装置の構成図である。
【図２】  パケット網における品質状態監視装置の実施例である。
【図３】  パケット経路情報から分岐、合流の構造を短終除去する一実現方法例である。
【図４】  短縮除去したトポロジーより論理トポロジーを作成するための変更例である。
【図５】  品質低下箇所把握の基本的な把握方法の例示である。
【図６】  品質監視装置とトポロジー把握装置の出力結果例である。
【図７】  リーフの属性よりノードの属性を作成した結果の例示である。
【図８】  子ノードの属性から親ノードの属性を作成した結果の例示である。
【図９】  品質低下が発生していると判定した箇所の例示である。
【図１０】  相関関係を基にした簡単な推定方法の例示である。
【図１１】  低下箇所推定機能が処理を行う有向木例である。
【図１２】  ノードとリーフのグループ化の例である。
【図１３】  グループ化された内部の処理結果の例示である。
【図１４】  代表データ系列群の選定結果の例示である。
【図１５】  低下箇所推定機能の処理結果の例示である。
【図１６】  代表データ系列群の選定結果の例示である。
【図１７】  最終的な品質低下箇所推定結果の例示である。
【符号の説明】
１  パケット網
１１，１２  パケットプローブ装置
２０  品質監視装置
２１  合成関数作成機能
２２  相互関数演算機能
２３  品質低下判定機能
３０  トポロジー把握機能
３１  分流合流短絡除去機能
３２  論理トポロジー作成機能
３３  経路情報推定機能
３４  経路情報収集機能
４０  品質低下箇所判定装置
４１  低下箇所判定機能
５０  表示装置
【図１】
0003834258.tif 000008
【図２】
0003834258.tif 000009
【図３】
0003834258.tif 000010
【図４】
0003834258.tif 000011
【図５】
0003834258.tif 000012
【図６】
0003834258.tif 000013
【図７】
0003834258.tif 000014
【図８】
0003834258.tif 000015
【図９】
0003834258.tif 000016
【図１０】
0003834258.tif 000017
【図１１】
0003834258.tif 000018
【図１２】
0003834258.tif 000019
【図１３】
0003834258.tif 000020
【図１４】
0003834258.tif 000021
【図１５】
0003834258.tif 000022
【図１６】
0003834258.tif 000023
【図１７】
0003834258.tif 000024