障害リンク特定システムの監視経路設定方法および装置
【課題】監視対象の実ネットワークを模した組合せグラフを利用して単一リンク障害および二重リンク障害を識別可能な監視パス経路を設定する。
【解決手段】ネットワークの各実リンクを通過する監視用パスが仮想ノードで表現され、各監視用パスの通過する実リンクが前記各仮想ノードを結ぶ仮想リンクで表現される組合せグラフに基づいて監視用パス群を設定する障害管理装置２が、基準組合せグラフを読み込む基準組合せグラフ読込部２０２と、基準組合せグラフを、その仮想リンク数が前記ネットワークの実リンク数に達するまで、監視用パス群により全ての単一リンク障害および二重リンク障害を識別できる制約条件下で順次に拡張する組合せグラフ拡張部２０３と、拡張された組合せグラフに基づいて監視用パス群を決定する監視経路決定部２０４とを具備した。
【解決手段】ネットワークの各実リンクを通過する監視用パスが仮想ノードで表現され、各監視用パスの通過する実リンクが前記各仮想ノードを結ぶ仮想リンクで表現される組合せグラフに基づいて監視用パス群を設定する障害管理装置２が、基準組合せグラフを読み込む基準組合せグラフ読込部２０２と、基準組合せグラフを、その仮想リンク数が前記ネットワークの実リンク数に達するまで、監視用パス群により全ての単一リンク障害および二重リンク障害を識別できる制約条件下で順次に拡張する組合せグラフ拡張部２０３と、拡張された組合せグラフに基づいて監視用パス群を決定する監視経路決定部２０４とを具備した。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、障害リンク特定システムの監視経路設定方法および装置に係り、特に、監視対象の実ネットワークを模した組合せグラフを利用して、単一リンク障害および二重リンク障害を識別可能な監視用パスの経路を設定する監視経路設定方法および装置に関する。
【背景技術】
【０００２】
特許文献１には、ネットワーク内の監視用パスを終端する品質監視装置において、監視用パスの品質劣化が検知された場合、障害監視装置において、品質劣化の検知された監視用パスが共通に通過するリンクを障害リンクと推定する技術が開示されている。
【０００３】
特許文献２には、ネットワークに接続された複数の品質監視装置によって終端され、かつ全ての単一リンク障害を特定できる最少かつ経路長の総和が最小である監視用パス群の経路を決定する技術が開示されている。
【０００４】
非特許文献１には、ネットワークに接続された複数の品質監視装置によって終端され、かつ多重リンク障害を含む予め想定されるリンク障害を特定できる経路長の総和が最小である監視用パス群を決定する技術が開示されている。
【０００５】
非特許文献２には、ネットワークを構成する各リンクと当該リンクを通過する監視用パスの組合せ表とが与えられた時、リンクの入れ替えや監視用パスの分割を行うことによって、ネットワーク上での連続性を満足する各監視用パスの経路を決定する技術が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第３８８５９３１号
【特許文献２】特願２００９−２８０３９３号
【非特許文献】
【０００７】
【非特許文献１】S. S. Ahuja, S. Ramasubramanian, and M. Krunz, "SRLG failure localization in all-optical networks using monitoring cycles and paths," Proc. of IEEE INFOCOM 2008, pp. 181-185, April 2008.
【非特許文献２】J. Tapolcai, B. Wu, and P-H. Ho, "On monitoring and failure localization in mesh all-optical networks," Proc. of IEEE INFOCOM 2009, pp. 1008-1016, April 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献１では、単一リンク障害を想定した場合、単一の障害リンクを正確に特定することができない。
【０００９】
特許文献２では、多重リンク障害が発生した場合、障害リンクを特定することができない。
【００１０】
非特許文献１では、監視用パス群の経路候補を予め与えて置く必要があり、全ての単一リンク障害および二重リンク障害を特定できるような多数の監視用パス群の経路を効率的に決定することができない。
【００１１】
非特許文献２では、全ての単一リンク障害と二重リンク障害の特定を想定した場合、ネットワークを構成する各リンクと当該リンクを通過する監視用パスの組合せ表を作成することが困難である。
【００１２】
本発明の目的は、上記した従来技術の課題を解決し、全ての単一リンク障害および二重リンク障害を特定でき、経路長の総和が小さく、少ない本数の監視用パス群の経路を設定できる監視経路設定方法および装置を提供することにある。
【課題を解決するための手段】
【００１３】
上記の目的を達成するために、本発明は、ネットワーク上の一部のノードに、監視データの送信機能および受信機能の少なくとも一方を備えた複数の品質監視装置を接続し、前記送信機能から受信機能へ複数の監視経路で監視データを送信し、その到達性に基づいて障害リンクを特定する障害リンク特定システムにおいて、ネットワークの各実リンクを通過する監視用パスが仮想ノードで表現され、各監視用パスの通過する実リンクが前記各仮想ノードを結ぶ仮想リンクで表現される組合せグラフに基づいて監視用パス群を設定する障害管理装置を設けた。
【００１４】
さらに、この障害管理装置に、組合せグラフの基本形となるレベル０の組合せグラフを読み込む基準組合せグラフ読込手段と、レベル０の組合せグラフを、その仮想リンク数が前記ネットワークの実リンク数に達するまで、前記監視用パス群により全ての単一リンク障害および二重リンク障害を識別できる制約条件下で順次に拡張する組合せグラフ拡張手段と、拡張された組合せグラフに基づいて監視用パス群を決定する監視経路決定手段とを設けた。
【発明の効果】
【００１５】
本発明によれば、監視対象のネットワーク構成および当該ネットワークにおいて単一リンク障害および二重リンク障害を識別できる監視用パス群の経路を組合せグラフで模擬できるようになるので、この組合せグラフを用いて、単一リンク障害および二重リンク障害を識別できる監視用パス群の経路を設定できるようになる。
【図面の簡単な説明】
【００１６】
【図１】本発明の監視経路設定方法および装置が適用されるネットワークの構成を示したブロック図である。
【図２】障害管理装置２の主要部の構成を示したブロック図である。
【図３】基準組合せグラフの一例を示した図である。
【図４】全ての二重仮想リンク障害を識別できる組合せグラフを作成するための制約条件を示した図である。
【図５】ネットワークを模擬できる組合せグラフの作成方法を示したフローチャートである。
【図６】ネットワークを模擬できる組合せグラフの拡張方法を示した模式図である。
【図７】監視対象のネットワークの一例を示した図である。
【図８】図７のネットワークを模擬する組合せグラフを示した図である。
【図９】図７のネットワークに対応した初期組合せ表を示した図である。
【図１０】監視用パスの接続性を保証する手順を示した図（その１）である。
【図１１】監視用パスの接続性を保証する手順を示した図（その２）である。
【図１２】監視用パスの接続性を保証する手順を示した図（その３）である。
【図１３】図７のネットワークに対応した最終組合せ表を示した図である。
【図１４】監視対象のネットワークを模した組合せグラフから監視用パス群を決定する手順を示したフローチャートである。
【発明を実施するための形態】
【００１７】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明の障害リンク特定システムが適用されるネットワークの構成を示したブロック図であり、監視対象のネットワークNWは、多数のノード装置nと、各ノード装置nを相互に接続する多数のリンクとから構成されている。
【００１８】
本発明では、複数のノード装置nに、監視データの送信機能(t)および受信機能(r)の少なくとも一方を備えた品質監視装置１がそれぞれ接続されており、送信機能を備えた品質監視装置１(t)から受信機能を備えた品質監視装置１(r)まで監視経路が設定される。なお、本実施形態では全ての品質監視装置１が監視データの送信機能(r)および受信機能(r)のいずれも備えているものとして説明する。
【００１９】
障害管理装置２は、監視データ送信機能(t)を備えた各品質監視装置１(t)に対して、監視経路を通して監視データを送信することを指示する。監視データ受信機能を備えた品質監視装置１(r)は、監視経路を通して受信した監視データの品質を監視し、品質劣化が検知されると障害管理装置２へ通報する。障害管理装置２は、各監視経路が通過するリンクに関する情報および品質劣化が検知された監視経路情報に基づいて障害リンクを特定する。これにより、リンク毎に品質監視装置１を設ける場合と比較して、必要な品質監視装置数の削減が図られる。前記障害管理装置２は、ネットワークNW上の各品質監視装置1と通信するための入出力インターフェースおよびそのアプリケーションが実装されたコンピュータで実現できる。
【００２０】
本発明では、障害リンクを必ず特定できるような複数の監視経路（監視用パスの経路群）が障害管理装置２により設定される。すなわち、本発明では単一リンク障害および二重リンク障害を想定し、これらのリンク障害が発生したとき、障害リンクを必ず特定できるような監視用パスの経路群が、後述する組合せグラフを利用することで設定される。
【００２１】
図２は、前記障害管理装置２の主要部の構成を示したブロック図であり、複数の監視経路（監視経路群）を設定する監視経路設定部２１と、各品質監視装置１から各監視経路に監視データを送信させて障害リンクを特定するリンク障害特定部２２とを含む。
【００２２】
前記リンク障害特定部２２は、前記設定された複数の監視経路に各品質監視装置１(t)から監視データを送信させ、当該監視データが品質監視装置１(r)に到達しない経路上、および監視データの到達が非常に遅いか、到達した監視データの誤り率が非常に高い経路上に障害が発生したと判定し、障害が発生している監視経路が通過し、かつ障害が発生していない監視経路が通過していないリンクを障害リンクと特定する。
【００２３】
前記監視経路設定部２１において、トポロジ取得部２０１は、監視対象ネットワークNWの物理的な実トポロジを取得する。基準組合せグラフ読込部２０２は、後述する基準組合せグラフを、記憶装置または入力インターフェース（いずれも、図示省略）から読み取る。組合せグラフ拡張部２０３は、前記基準組合せグラフを、監視対象のネットワークを模擬できる組合せグラフまで、所定の制約条件下で拡張する。監視経路決定部２０４は、前記拡張された組合せグラフに基づいて監視経路群を決定する。
【００２４】
以下、図面を参照して本発明の実施の形態について詳細に説明する。ここでは、初めに本発明の概要について説明し、次いで、具体的な動作について説明する。
【００２５】
本発明では、監視用パスの設定対象となる実ネットワークのトポロジを模擬し、かつ所定の制約条件を満足する組合せグラフを仮想的に構築し、この組合せグラフを用いて監視用パスを設定する。
【００２６】
前記組合せグラフは、各監視用パスのネットワーク上での連続性を考慮せずに、ネットワークの実リンクを模擬する仮想リンクと当該仮想リンクを通過する監視用パス組との関係を表すように作成される。本実施形態では、図３に一例を示したように、各監視用パスを組合せグラフのノード（黒丸●または白丸○）に対応させ、通過する監視用パス数が２本の仮想リンクは、当該通過する監視用パスに対応する２個のノードを接続する１本の実線仮想リンクによって表現される。また、通過する監視用パス数が３本の仮想リンクは、当該通過する監視用パスに対応する３個の頂点ノード（●）を接続する３本の破線仮想リンク列によって表現する。したがって、図３の組合せグラフは、以下の１３本の仮想リンクに対応する１３本の実リンクから構成されるネットワークトポロジを表現することになる。
【００２７】
・２本の監視用パスG0，A0が通過する実線仮想リンクL1
・２本の監視用パスA0，F0が通過する実線仮想リンクL2
・２本の監視用パスF0，I0が通過する実線仮想リンクL3
・２本の監視用パスG0，D0が通過する実線仮想リンクL4
・２本の監視用パスD0，E0が通過する実線仮想リンクL5
・２本の監視用パスE0，H0が通過する実線仮想リンクL6
・２本の監視用パスI0，C0が通過する実線仮想リンクL7
・２本の監視用パスC0，B0が通過する実線仮想リンクL8
・２本の監視用パスB0，H0が通過する実線仮想リンクL9
・２本の監視用パスA0，B0が通過する実線仮想リンクL10
・２本の監視用パスD0，C0が通過する実線仮想リンクL11
・２本の監視用パスE0，F0が通過する実線仮想リンクL12
・３本の監視用パスG0，I0、H0が通過する破線仮想リンク列L13
【００２８】
また、本発明では、監視負荷の低減および単一リンク障害と二重リンク障害とを識別するために、各実リンクに設定される監視用パスに以下の２つの条件が要求される。
【００２９】
・条件１：各実リンクを通過する監視用パス数は３本以下とする。これは、監視用データに起因するシステムの負荷を抑えるために設定される制約条件である。
・条件２：各実リンクを通過する監視用パス数は２本以上とする。これは、各リンクを通る監視用パス数が１本であると、当該監視用パスが通過する他のリンクが障害になった際、当該他のリンクの単一障害なのか、当該他のリンクと監視用パスが１本のみ通過するリンクとの二重リンク障害なのか識別できなくなるためである。
【００３０】
さらに、組合せグラフの構築に際して、全ての二重仮想リンク障害が互いに識別されるように、以下の５つの制約条件が課される。なお、監視用パス群によって全ての二重仮想リンク障害が互いに識別されれば、全ての単一仮想リンク障害も互いに識別できる。
【００３１】
・制約条件１：４つ以下の実線仮想リンクで構成される閉路を含まない。
・制約条件２：破線仮想リンク列で接続された２個の頂点間には３本以上の実線仮想リンクが存在しなければならない。
・制約条件３：２個の頂点を共有する２組の破線仮想リンク列の共有されない２個の頂点間には３本以上の実線仮想リンクが存在しなければならない。
・制約条件４：５つ以下の頂点で構成される３組の破線仮想リンク列を含まない。
・制約条件５：６つ以下の頂点で構成される４組の破線仮想リンク列を含まない。
【００３２】
図４(a)は、前記制約条件１を満足しない組合せグラフの一例であり、４本の実線仮想リンクにより閉路が形成されている。このような組合せグラフでは、監視用パスA、B、C、Dの品質劣化が検知された場合、監視用パスA、Bが通過する仮想リンクと監視用パスC、Dが通過する仮想リンクとの二重リンク障害であるのか、あるいは監視用パスA、Dが通過する仮想リンクと監視用パスB、Cが通過する仮想リンクとの二重リンク障害であるのかを識別することができない。これに対して、組合せグラフにおいて制約条件１が満足されれば、２本の監視用パスが通過する仮想リンクの全ての二重障害を互いに識別できる。
【００３３】
図４(b)は、前記制約条件２を満足しない組合せグラフの一例であり、破線仮想リンク列で接続された２個の頂点（C，D）の間には２本の実線仮想リンクしか存在しない。このような組合せグラフでは、監視用パスA，B，C，Dの品質劣化が検知された場合、監視用パスA，B，Cが通過する仮想リンクと監視用パスB，Dが通過する仮想リンクとの二重リンク障害であるのか、あるいは監視用パスA，B，Cが通過する仮想リンクと監視用パスC，Dが通過する仮想リンクとの二重リンク障害であるのかを識別することができない。
【００３４】
図４(c)は、前記制約条件３を満足しない組合せグラフの一例であり、２個の頂点（A，B）を共有する２組の破線仮想リンク列の共有されない２個の頂点（C，D）の間には２本の実線仮想リンクしか存在しない。このような組合せグラフでは、監視用パスA，B，C，D，Eの品質劣化が検知された場合、監視用パスA，B，Cが通過する仮想リンクと監視用パスD，Eが通過する仮想リンクとの二重リンク障害であるのか、監視用パスA，B，Dが通過する仮想リンクと監視用パスC，Eが通過する仮想リンクとの二重リンク障害であるのかを識別できない。
【００３５】
図４(d)は、前記制約条件４を満足しない組合せグラフの一例であり、５つ以下の頂点で構成される３組の破線仮想リンク列を含んでしまっている。このような組合せグラフでは、監視用パスA，B，C，D，Eの品質劣化が検知された場合、監視用パスA，B，Cが通過する仮想リンクと監視用パスC，D，Eが通過する仮想リンクとの二重リンク障害であるのか、監視用パスA，B，Dが通過する仮想リンクと監視用パスC，D，Eが通過する仮想リンクとの二重リンク障害であるのかを識別できない。組合せグラフにおいて、制約条件２，３，４が満足されれば、２本の監視用パスが通過する仮想リンクと３本の監視用パスが通過する仮想リンクとの二重障害を、他の全ての二重リンク障害から識別できる。
【００３６】
図４(e)は、前記制約条件５を満足しない組合せグラフの一例であり、６つ以下の頂点で構成される４組の破線仮想リンク列を含んでしまっている。このような組合せグラフでは、監視用パスA，B，C，D，E，Fの品質劣化が検知された場合、監視用パスA，B，Cが通過する仮想リンクと監視用パスD，E，Fが通過する仮想リンクとの二重リンク障害であるのか、監視用パスA，B，Dが通過する仮想リンクと監視用パスC，E，Fが通過する仮想リンクとの二重リンク障害であるのかを識別できない。組合せグラフにおいて、制約条件４，５が満足されれば、３本の監視用パスが通過する仮想リンクの全ての二重障害を互いに識別できる。
【００３７】
本実施形態では、以上に述べた２つの条件および５つの制約条件の下、組合せグラフの実線仮想リンク数と破線仮想リンク列数との和が、監視対象ネットワークの実リンク数と同数になるまで組合せグラフを拡張し、実線仮想リンク数と破線仮想リンク列数との和が実リンク数と同数以上になった拡張組合せグラフに基づいて監視用パスが決定される。
【００３８】
次いで、監視対象のネットワークを模擬した組合せグラフの作成方法を、図５のフローチャートおよび図６の模式図に沿って説明する。ステップＳ１では、監視対象となるネットワークのトポロジが、前記トポロジ取得部２０１により取得される。
【００３９】
ステップＳ２では、上記の各制約条件を満足する最小構成の組合せグラフが、前記基準組合せグラフ読込部２０２により基準（レベル０）組合せグラフとして取得される。本実施形態では、図６(a)に示したように、前記図３を参照して説明した組合せグラフがレベル０の基準組合せグラフとして取得される。この基準組合せグラフは上記の制約条件１，２を満足しており、１３本の仮想リンクを通過し、全ての単一仮想リンク障害および二重仮想リンク障害を特定できる９本の監視用パス群を示している。
【００４０】
ステップＳ３，Ｓ４では、前記基準組合せグラフを、その仮想リンク数（実線仮想リンク数と破線仮想リンク列数との和）がネットワークの実リンク数と同数となるまで、前記制約条件を満足させながら順次に拡張することで、ネットワークを模擬できる組合せグラフが作成される。
【００４１】
本発明では、基準組合せグラフに仮想ノードが１つずつ追加され、当該追加されたノードと既存の仮想ノードとを結ぶ仮想リンクが追加される。このような仮想ノードの追加および仮想リンクの追加による組合せグラフの拡張は、組合せグラフの仮想リンク数がネットワークの実リンク数に達するまで繰り返される。
【００４２】
なお、仮想ノードを１つずつ追加しても、構成可能な仮想リンク数が必ずしも１つずつ増える訳ではないが、本実施形態では、実リンク数と同数以上の仮想リンクを構成できるまで仮想ノードを１つずつ追加して行き、構成できるようになった段階で、実リンク数と同数の仮想リンクのみを組合せグラフ上に構成するようにしている。
【００４３】
次いで、組合せグラフの拡張方法について具体的に説明する。本実施形態では、上記のように、仮想ノードを１つずつ追加し、当該追加され仮想ノードと既存の仮想ノードとを結ぶことで仮想リンクが追加されるが、追加される仮想ノードや仮想リンクは、以下のようにして決定される。
【００４４】
初めに、組合せグラフ（初めは、レベル０の基準組合せグラフ）において破線仮想リンク列で接続されていたレベル０の各２頂点ノード[G0，H0]，[H0，I0]，[I0，G0]が、前記制約条件２に従って、最終的には図６(e)に示したように、新たに追加される各２個の頂点ノード(A1，E1)、(B1，F1)、(C1，D1)を経由する３本の実線仮想リンクによって接続されるまで、仮想ノードおよび仮想リンクの追加が繰り返される。
【００４５】
さらに具体的に説明すれば、初めに、図６(b)に示したように、基準組合せグラフに頂点ノードA1が追加され、当該頂点ノードA1と既存（レベル0）の頂点ノードG0とにより終端される実線仮想リンクL1が新たに構成される。本拡張によって、構成可能な仮想リンク数が１本増加する。
【００４６】
次いで、同図(c)に示したように、頂点ノードB1が追加され、当該頂点ノードB1と既存の頂点ノードH0とにより終端される実線仮想リンクL2、および頂点ノードC0、A1、B1を通過する破線仮想リンク列L3が新たに構成される。本拡張によって、構成可能な仮想リンク数が更に２本増加する。
【００４７】
次いで、同図(d)に示したように、頂点ノードC1が追加され、当該頂点ノードC1と既存の頂点ノードI0とにより終端される実線仮想リンクL4、頂点ノードA1、B1、C1を通過する破線仮想リンク列L5、頂点ノードA0、B1、C1を通過する破線仮想リンク列L6、および頂点ノードE0、C1、A1を通過する破線仮想リンク列L7が新たに構成される。本拡張によって、構成可能な仮想リンク数が更に４本増加する。
【００４８】
以下同様に、図示は省略するが次いで頂点ノードD1が追加され、当該頂点ノードD1と既存の頂点ノードG0とにより終端される実線仮想リンクL8、頂点ノードC1と頂点ノードD1とにより終端される実線仮想リンクL9、および頂点ノードC0、B1、D1を通過する破線仮想リンク列L10が新たに構成される。本拡張によって、構成可能な仮想リンク数が更に３本増加する。
【００４９】
さらに、次いで頂点ノードE1が追加され、当該頂点ノードE1と既存の頂点ノードH0とにより終端される実線仮想リンクL11、頂点ノードA1と頂点ノードE1とにより終端される実線仮想リンクL12、頂点ノードC0、D1、E1を通過する破線仮想リンク列L13、および頂点ノードA0、C1、E1を通過する破線仮想リンク列L14が新たに構成される。本拡張によって、構成可能な仮想リンク数が更に４本増加する。
【００５０】
さらに、次いで頂点ノードF1が追加され、当該頂点ノードF1と既存の頂点ノードI0とにより終端される実線仮想リンクL15、頂点ノードB1と頂点ノードF1とにより終端される実線仮想リンクL16、頂点ノードD1、E1、F1を通過する破線仮想リンク列L17、頂点ノードA0、E1、F1を通過する破線仮想リンク列L18、頂点ノードE0、F1、C1を通過する破線仮想リンク列L19、および頂点ノードE0、A1、F1を通過する破線仮想リンク列L20が新たに構成される。本拡張によって、構成可能な仮想リンク数が更に６本増加する。
【００５１】
このように、本実施形態では予め用意されているレベル０の組合せグラフを対象に、初めは、前記６つのレベル１頂点ノードのうちの３つ（A1，B1，C1）が１つずつ追加され、破線仮想リンク列で接続されている３つのレベル０頂点ノード（G1，H1，I1）が順番に１つずつ選択されて実線仮想リンク（Ｌ１，Ｌ２，Ｌ４）で接続される。その際、レベル１の組合せグラフにおいて最終的に構成可能な破線仮想リンク列の中で、レベル１頂点ノードを１つずつ追加する各段階で構成可能な破線リンク列があれば、各段階でそれらも構成される。
【００５２】
次いで、前記６つのレベル１頂点ノードのうちの残りの３つ（D1，E1，F1）が１つずつ追加され、最初に選択されたレベル０頂点ノードと３番目に追加されたレベル１頂点ノード、２番目に選択されたレベル０頂点ノードと最初に追加されたレベル１頂点ノード、および３番目に選択されたレベル０頂点ノードと２番目に追加されたレベル１頂点ノードとが、それぞれ実線仮想リンクで接続される。その際、レベル１の組合せグラフにおいて最終的に構成可能な破線仮想リンク列の中で、レベル１頂点ノードを１つずつ追加する各段階で構成可能な破線リンク列があれば、各段階でそれらも構成される。
【００５３】
図６(e)は、以上の手順でレベル0からレベル１への拡張が完了した時点での組合せグラフの構成を示した図であり、レベル０の基準組合せグラフにおいて破線仮想リンク列で接続されていた各２頂点ノード[G0，H0]，[H0，I0]，[I0，G0]が、新たに追加された各２個の頂点ノード(A1，E1)、(B1，F1)、(C1，D1)を経由する実線仮想リンクで接続されることにより、計９本の実線仮想リンクが新たに追加されている。
【００５４】
すなわち、レベルi（i > 0）の組合せグラフは、破線仮想リンク列で結ばれるレベルi-1の３個の頂点ノードの中の各２個の頂点ノードを、それぞれ新たに追加した２個のレベルiの頂点ノードを経由して直列接続することにより、最終的にはレベルi-1の組合せグラフ当該レベルに対して、２本の監視用パスが通過する９本の実線仮想リンクが新たに構成されるように拡張される。
【００５５】
さらに、図６(e)では図示が省略されているが、レベルi-1の３個の頂点ノードおよび新たに追加されたレベルiの６つの頂点ノードの計９個の頂点ノードから、前記制約条件が満足されるように選択された各３個のノードを経由する計１１本の破線仮想リンク列が新たに追加され、合計で２０本の仮想リンクが追加される。なお、前記新たに追加される１１本の破線仮想リンク列のうち、９本は１つのレベルi-1頂点と２つのレベルi頂点とを経由し、残り２本は６つのレベルi頂点の各３つを経由する。
【００５６】
ここではレベル0からレベル1への拡張を例にして説明したが、一般的にレベルiへの拡張では、３つのレベルi-1頂点ノードによって構成される破線仮想リンク列が2 i-1本存在するので、それらを順番に１つずつ選択して、前記レベル１への拡張と同様の手順で拡張を行なえば良い。
【００５７】
なお、上記の拡張手順において、レベル０の監視用パスC0，F0は、レベル１の監視用パスA1，B1、またはD1，E1、またはD1，B1と組み合わせることによって、それぞれ３本の破線仮想リンク列を新たに構成でき、各監視用パスの組合せは前記制約条件２を満足できる。
【００５８】
すなわち、レベル０の監視用パスC0に着目すれば、このC0とA1，B1とを通過する破線仮想リンク列、C0とD1，E1とを通過する破線仮想リンク列、およびC0とD1，B1とを通過する破線仮想リンク列の計３本の破線仮想リンク列を構成できる。また監視用パスF0に着目すれば、このF0とA1，B1とを通過する破線仮想リンク列、F0とD1，E1とを通過する破線仮想リンク列、およびF0とD1，B1とを通過する破線仮想リンク列の計３本の破線仮想リンク列を構成でき、合計で６本の破線仮想リンク列を構成できる。
【００５９】
しかしながら、制約条件３，４，５の違反を避けるために、ここでは監視用パスC0のみについて、レベル１の監視用パス組A1，B1との組合せ、D1，E1との組合せ、およびD1，B1との組合せを考え、C0とA1，B1とを通過する破線仮想リンク列、C0とD1，E1とを通過する破線仮想リンク列、およびC0とD1，B1とを通過する破線仮想リンク列の計３本の破線仮想リンク列が追加される。
【００６０】
同様に、レベル０の監視用パスA0，D0に着目した場合も、制約条件３，４，５の違反を避けるために、例えば監視用パスA0のみについて、レベル１の監視用パス組B1，C1との組合せ、E1，F1との組合せ、およびE1，C1との組合せを考え、A0とB1，C1とを通過する破線仮想リンク列、A0とE1，F1とを通過する破線仮想リンク列、およびA0とE1，C1とを通過する破線仮想リンク列の計３本の破線仮想リンク列が追加される。
【００６１】
同様に、レベル０の監視用パスD0，E0に着目した場合も、制約条件３，４，５の違反を避けるために、例えば監視用パスE0のみについて、レベル１の監視用パス組C1，A1との組合せ、F1，D1との組合せ、およびF1，A1との組合せを考え、E0とC1，A1とを通過する破線仮想リンク列、E0とF1，D1とを通過する破線仮想リンク列、およびE0とF1，A1とを通過する破線仮想リンク列の計３本の破線仮想リンク列が追加される。
【００６２】
図５へ戻り、ステップＳ４では、拡張後の組合せグラフで構成可能な仮想リンク総数が実リンク数と同数であるか否かが判定される。同数に満たなければステップＳ２へ戻り、前記レベル１の組合せグラフにおける拡張を行い、前記レベル１の組合せグラフにおける拡張が終了している場合には、レベル２の組合せグラフにおける拡張が同様に行なわれる。
【００６３】
すなわち、レベル２の組合せグラフもレベル１の組合せグラフと同様にして構成できる。図６(f)に示した様に、レベル２の組合せグラフでは、最終的に、破線仮想リンク列で接続されたレベル１の各２個の頂点ノードを、新たに追加した２個の頂点ノードを経由する３本の実線仮想リンクで接続する。レベル１の組合せグラフは２組の破線仮想リンク列を含むため、１２本のレベル２監視用パスの追加によって、レベル２監視用パスを含む２本の監視用パスが通過する１８本の実線仮想リンクと３本のレベル２監視用パスが通過する４本の破線仮想リンク列を新たに構成できる。更に、レベル２の組合せグラフでは、１本のレベル１以下の監視用パスと２本のレベル２監視用パスの組合せによって、１８本の破線仮想リンク列を新たに構成できる。
【００６４】
このように、本実施形態における組合せグラフのレベルi（i > 0）における拡張では、最終的に以下の３つの種類の仮想リンクが新たに構成できる。
【００６５】
第１種類：レベルi-1の３個の頂点ノードを経由する１つの破線仮想リンク列に対応して、３個の頂点ノードの中の各２個の頂点ノードを、それぞれ新たに追加した２個のレベルiの頂点ノードを経由して接続することにより、レベルi監視用パスを含む２本の監視用パスが通過する９本の実線仮想リンクを構成できる。
【００６６】
第２種類：レベルi-1の３個の頂点ノードを経由する１つの破線仮想リンク列に対応して、３本のレベルi監視用パスが通過する２本の破線仮想リンク列を構成できる。
【００６７】
第３種類：レベルi-1の３個の頂点ノードを経由する１つの破線仮想リンク列に対応して、１本のレベルi-１以下の監視用パスと２本のレベルi監視用パスが通過する９本の破線仮想リンク列を構成できる。
【００６８】
レベルi-1の３個の頂点ノードを経由する破線仮想リンク列の本数は2 i-1 であるため、レベルiへの拡張によって、最終的に20×2 i-1 本の仮想リンクを新たに構成できる。
【００６９】
以上のようにして、基準組合せグラフを、前記制約条件下で、１つずつ頂点ノードを追加して行くことによって拡張することにより、仮想リンク数が実リンク数と同数の組合せグラフが得られると、監視用パスの連続性は保障されないものの、全ての単一仮想リンク障害および二重仮想リンク障害を特定するための各仮想リンクと当該各仮想リンクを通過する監視用パス組との関係を表す組合せグラフが得られる。ステップＳ５では、前記拡張済みの組合せグラフに基づいて監視経路群が決定される。
【００７０】
次いで、図７に示した監視対象ネットワークを例にして、図１４のフローチャートに沿って監視経路の決定方法を説明する。
【００７１】
図７の監視対象ネットワークは、８つのノードと１６本の実リンクとによって構成され、ステップＳ１０では、上記の手順にしたがって、図８に示したように、監視対象ネットワークの実リンク数と同数の仮想リンクを含む組合せグラフが、前記基準組合せグラフを順次に拡張することで作成される。
【００７２】
本実施形態では、前記基準組合せグラフに仮想ノードが１つずつ追加され、当該追加されたノードと既存の仮想ノードとを結ぶ仮想リンクが追加され、このような仮想ノードの追加および仮想リンクの追加による組合せグラフの拡張が、組合せグラフの仮想リンク数がネットワークの実リンク数に達するまで繰り返される。
【００７３】
図８の組合せグラフでは、前記図６(a)の基準組合せグラフに２つの頂点ノードA1，B1を追加し、既存ノードG0と追加ノードA1とで終端される実線仮想リンクL1、既存ノードH0と追加ノードB1とで終端される実線仮想リンクL2、および既存ノードC0と追加ノードA1，B1とを結ぶ破線仮想リンク列L3の３本の仮想リンクを追加することにより、１６本の仮想リンクと１１本の監視用パス（９本の実線仮想リンクと２本の破線仮想リンク列）とを構成できる。
【００７４】
ステップＳ２０では、監視対象のネットワークを構成する実リンクと組合せグラフ中の仮想リンクとの対応関係が暫定的に決定される。本実施形態では、各リンクが以下の３つの手順により対応付けられる。
【００７５】
手順１：ネットワークを構成する各実リンクが、通過する監視用パス組を選択できる自由度に応じて順序付けされる。本実施形態では、接続している２個のノードの次数の積が大きい実リンクほど、監視用パス組の選択自由度が高いとして上位に順序付けられる。例えば、第１ノードと第８ノードとを結ぶ実リンクL1-8は、第１ノードの次数が「３」、第８ノードの次数が「４」なので、その積は「１２」となる。これに対して、第１ノードと第２ノードとを結ぶ実リンクL1-2は、第２ノードの次数が「５」なので、その積は「１５」となる。したがって、実リンクL1-2は実リンクL1-8よりも上位に位置付けられる。
【００７６】
なお、次数の積が等しい場合は、１つ順番が上位である実リンクと隣接している実リンクが上位に順序付けられる。例えば、第２ノードと第７ノードとを結ぶ実リンクL7-8および第２ノードと第３ノードとを結ぶ実リンクL2-3が選択された段階で、第２ノードと第４ノードとを結ぶ実リンクL2-4、第４ノードと第７ノードとを結ぶ実リンクL4-7、第５ノードと第７ノードとを結ぶ実リンクL5-7、および第７ノードと第８ノードとを結ぶ実リンクL7-8における次数の積は、いずれも「２０」である。この中で、１つ順番が上位である第２ノードと第３ノードとを結ぶ実リンクL2-3には、前記実リンクL2-4が隣接しているので、当該実リンクL2-4が上位に順序付けられる。なお、隣接リンクが複数ある場合には、ランダムに１本の実リンクが選択されて上位に順序付けられる。
【００７７】
手順２：組合せグラフ中の各仮想リンクが、組合せグラフによって指定されている監視用パス組の実現困難性に応じて順序付けされる。本実施形態では、通過する監視用パスの経路長の総和が大きい仮想リンクほど、実現困難性が高いとして上位に順序付けられる。なお、通過する監視用パスの経路長の総和が等しい場合は、１つ順番が上位の仮想リンクを通過する監視用パスがより多く通過する仮想リンクが上位に順序付けられる。なお、通過する監視用パスが同数の仮想リンクが複数ある場合には、ランダムに１本の仮想リンクが選択されて上位に順序付けられる。
【００７８】
手順３：以上のようにして順序付けられた実リンクおよび仮想リンクを、順番に一対一対応させることにより対応関係が決定される。すなわち、通過する監視用パス組を選択できる自由度が１番の実リンクと監視用パス組の実現困難性が１番の仮想リンクとが対応付けられ、各２番目のリンク同士が対応付けられ、以下同様に、順番が同一のリンク同士が一対一で対応付けられる。
【００７９】
本実施形態では、このような対応付けにより、監視用パスの連続性が可能な限り保障されるような仮想リンクと実リンクの対応関係が得られるので、後述するステップＳ５０における監視用パス数の増加が抑えられる。
【００８０】
ステップＳ３０では、前記ネットワークを構成する実リンクと組合せグラフ中の仮想リンクとの対応関係から、ネットワークの各実リンクを通過すべき監視用パス組を表現する初期組合せ表が導出される。
【００８１】
図９は、図８の組合せグラフから導出された初期組合せ表であり、実リンクと仮想リンクとの対応関係、および各リンクを通過する監視用パスの組合せが登録されている。本実施形態では、各監視用パスが通過すべきリンクの場所には「１」が、通過すべきでないリンクの場所には「０」が、それぞれ記されている。
【００８２】
ネットワークを構成する実リンクに関しては、上位に順序付けられるほど上方に記述されている。また、組合せグラフ中の仮想リンクに関しても、上位に順序付けられるほど上方に記述されている。このような初期組合せ表を参照すれば、ネットワークを構成する実リンクと組合せグラフ中の仮想リンクとの対応関係、ならびに各実リンクを通過すべき監視用パス組が明確になる。
【００８３】
ステップＳ４０では、前記初期組合せ表を構成する各監視用パスについて、その連続性を保障する困難さに応じて、連続性を保障する順番が以下の規則に従って決定される。
【００８４】
(1)経由リンク数が多い監視用パスほど先（上位）の順番とする。
【００８５】
(2)経由リンク数が等しい場合は順番が先である監視用パス群と多くのリンクを共用する監視用パスほど先の順番とする。
【００８６】
(3)共用するリンク数が等しい場合は、３本の監視用パスが通過するリンクを多く経由する監視用パスほど先の順番とする。
【００８７】
このように、本実施形態では連続性の保障が困難である監視用パスほど連続性の保障が先に実行されるので、後述するステップＳ５０における監視用パス数の増加が抑えられる。なお、図９の初期組合せ表では、当該ステップＳ４０で決定された監視用パスの順番も適用されており、右側の監視用パス欄において、より左側に記された監視用パスほど先の順番とされた監視用パスである。
【００８８】
ステップＳ５０では、初期組合せ表の右側に記された監視用パス欄から、全ての監視用パスの連続性が保障された最終組合せ表が導出される。
【００８９】
本実施形態では、ある監視用パスについて、連続性を満足しないリンクを通過する必要がある時は、連続性を満足するリンクの中で既に連続性が保障された監視用パスに関して、当該連続性を満足しないリンクと同一組の監視用パスが通過するリンクが存在するならば、そのリンクと当該連続性を満足しないリンクを組合せ表において入れ替える。これにより、既に連続性が保障された監視用パスに影響を与えることなく、当該監視用パスが連続したリンクを通過できることになる。
【００９０】
これを図１０の組合せ表を参照して具体的に説明すれば、図中右側の監視用パス欄において、左側から３番目までの３つの監視用パスG0、H0、C0は既に連続性が保証されている。これに対して、４番目の監視用パスI0は、実リンク(２，７)、(１，２)、(３，６)を通らなければならないが、実リンク(２，７)，(１，２)と(３，６)とは接続されていないので、その連続性が保証されていない。
【００９１】
一方、実リンク(１，８)に着目すると、当該実リンク(１，８)は前記相互に接続されている実リンク(２，７)，(１，２)のペアと一列に接続され、また前記連続性が既に保証されている監視用パスG0、H0、C0は、いずれも前記実リンク(１，８)，(３，６)を通過しないので、両者を入れ替えても監視用パスG0、H0、C0の連続性に影響を与えることが無い。したがって、ここでは図１１に示したように、実リンク(１，８)，(３，６)を相互に入れ替えることで監視用パスI0の連続性が新たに保証されるようになる。
【００９２】
なお、このようなリンク入れ替えを行っても連続性が保障されない場合は、当該監視用パスを連続性が保障される部分と保障されない部分とに分割する。そして、連続性が保障される部分のみを当該監視用パスと見なし、連続性が保障されない部分については、別の監視用パスとして新たに組合せ表の右側に追加する。
【００９３】
これを図１１の組合せ表を参照して具体的に説明すれば、監視用パスE0は実リンク(４，７)、(３，４)、(４，５)を通らなければならないが、実リンク(４，５)は実リンク(４，７)、(３，４)のペアと一列に連続していないので、その連続性が保証されていない。
【００９４】
しかも、図１１の組合せ表には、上述の条件を満足して実リンク(4, 5)と入れ替えることができる実リンクも存在しない。従って、当該リンク(4, 5)の部分については、図１２に示したように、別の監視用パスaが新たに組合せ表の右側に追加される。この場合、必要な監視用パス数は増加することになるが、前記ステップＳ２０ないしＳ４０の処理によって監視用パス数の増加は最小限に抑えられる。また、新たに組合せ表の右側に追加された監視用パスの連続性も、左側に記された監視用パスから同様の手順で保障できる。
【００９５】
以上のようにして、全ての監視用パスの連続性が保障された最終組合せ表が得られると、各監視用パスが通過すべきリンク情報から、全ての単一リンク障害および２重リンク障害を特定できる最少の監視用パス群の経路を決定する。
【００９６】
図１３は、図９の初期組合せ表に対して、各監視用パスの連続性を保障することによって得られた最終組合せ表であり、必要な監視用パス数は１４本となる。図１３に示されている最終組合せ表によって、全ての単一リンク障害および二重リンク障害を特定できる最少の監視用パスの経路が決定される。
【符号の説明】
【００９７】
１…品質監視装置，２…障害管理装置，２１…監視経路設定部，２２…リンク障害特定部，２０１…トポロジ取得部，２０２…基準組合せグラフ読込部，２０３…組合せグラフ拡張部，２０４…監視経路決定部
【技術分野】
【０００１】
本発明は、障害リンク特定システムの監視経路設定方法および装置に係り、特に、監視対象の実ネットワークを模した組合せグラフを利用して、単一リンク障害および二重リンク障害を識別可能な監視用パスの経路を設定する監視経路設定方法および装置に関する。
【背景技術】
【０００２】
特許文献１には、ネットワーク内の監視用パスを終端する品質監視装置において、監視用パスの品質劣化が検知された場合、障害監視装置において、品質劣化の検知された監視用パスが共通に通過するリンクを障害リンクと推定する技術が開示されている。
【０００３】
特許文献２には、ネットワークに接続された複数の品質監視装置によって終端され、かつ全ての単一リンク障害を特定できる最少かつ経路長の総和が最小である監視用パス群の経路を決定する技術が開示されている。
【０００４】
非特許文献１には、ネットワークに接続された複数の品質監視装置によって終端され、かつ多重リンク障害を含む予め想定されるリンク障害を特定できる経路長の総和が最小である監視用パス群を決定する技術が開示されている。
【０００５】
非特許文献２には、ネットワークを構成する各リンクと当該リンクを通過する監視用パスの組合せ表とが与えられた時、リンクの入れ替えや監視用パスの分割を行うことによって、ネットワーク上での連続性を満足する各監視用パスの経路を決定する技術が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第３８８５９３１号
【特許文献２】特願２００９−２８０３９３号
【非特許文献】
【０００７】
【非特許文献１】S. S. Ahuja, S. Ramasubramanian, and M. Krunz, "SRLG failure localization in all-optical networks using monitoring cycles and paths," Proc. of IEEE INFOCOM 2008, pp. 181-185, April 2008.
【非特許文献２】J. Tapolcai, B. Wu, and P-H. Ho, "On monitoring and failure localization in mesh all-optical networks," Proc. of IEEE INFOCOM 2009, pp. 1008-1016, April 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献１では、単一リンク障害を想定した場合、単一の障害リンクを正確に特定することができない。
【０００９】
特許文献２では、多重リンク障害が発生した場合、障害リンクを特定することができない。
【００１０】
非特許文献１では、監視用パス群の経路候補を予め与えて置く必要があり、全ての単一リンク障害および二重リンク障害を特定できるような多数の監視用パス群の経路を効率的に決定することができない。
【００１１】
非特許文献２では、全ての単一リンク障害と二重リンク障害の特定を想定した場合、ネットワークを構成する各リンクと当該リンクを通過する監視用パスの組合せ表を作成することが困難である。
【００１２】
本発明の目的は、上記した従来技術の課題を解決し、全ての単一リンク障害および二重リンク障害を特定でき、経路長の総和が小さく、少ない本数の監視用パス群の経路を設定できる監視経路設定方法および装置を提供することにある。
【課題を解決するための手段】
【００１３】
上記の目的を達成するために、本発明は、ネットワーク上の一部のノードに、監視データの送信機能および受信機能の少なくとも一方を備えた複数の品質監視装置を接続し、前記送信機能から受信機能へ複数の監視経路で監視データを送信し、その到達性に基づいて障害リンクを特定する障害リンク特定システムにおいて、ネットワークの各実リンクを通過する監視用パスが仮想ノードで表現され、各監視用パスの通過する実リンクが前記各仮想ノードを結ぶ仮想リンクで表現される組合せグラフに基づいて監視用パス群を設定する障害管理装置を設けた。
【００１４】
さらに、この障害管理装置に、組合せグラフの基本形となるレベル０の組合せグラフを読み込む基準組合せグラフ読込手段と、レベル０の組合せグラフを、その仮想リンク数が前記ネットワークの実リンク数に達するまで、前記監視用パス群により全ての単一リンク障害および二重リンク障害を識別できる制約条件下で順次に拡張する組合せグラフ拡張手段と、拡張された組合せグラフに基づいて監視用パス群を決定する監視経路決定手段とを設けた。
【発明の効果】
【００１５】
本発明によれば、監視対象のネットワーク構成および当該ネットワークにおいて単一リンク障害および二重リンク障害を識別できる監視用パス群の経路を組合せグラフで模擬できるようになるので、この組合せグラフを用いて、単一リンク障害および二重リンク障害を識別できる監視用パス群の経路を設定できるようになる。
【図面の簡単な説明】
【００１６】
【図１】本発明の監視経路設定方法および装置が適用されるネットワークの構成を示したブロック図である。
【図２】障害管理装置２の主要部の構成を示したブロック図である。
【図３】基準組合せグラフの一例を示した図である。
【図４】全ての二重仮想リンク障害を識別できる組合せグラフを作成するための制約条件を示した図である。
【図５】ネットワークを模擬できる組合せグラフの作成方法を示したフローチャートである。
【図６】ネットワークを模擬できる組合せグラフの拡張方法を示した模式図である。
【図７】監視対象のネットワークの一例を示した図である。
【図８】図７のネットワークを模擬する組合せグラフを示した図である。
【図９】図７のネットワークに対応した初期組合せ表を示した図である。
【図１０】監視用パスの接続性を保証する手順を示した図（その１）である。
【図１１】監視用パスの接続性を保証する手順を示した図（その２）である。
【図１２】監視用パスの接続性を保証する手順を示した図（その３）である。
【図１３】図７のネットワークに対応した最終組合せ表を示した図である。
【図１４】監視対象のネットワークを模した組合せグラフから監視用パス群を決定する手順を示したフローチャートである。
【発明を実施するための形態】
【００１７】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明の障害リンク特定システムが適用されるネットワークの構成を示したブロック図であり、監視対象のネットワークNWは、多数のノード装置nと、各ノード装置nを相互に接続する多数のリンクとから構成されている。
【００１８】
本発明では、複数のノード装置nに、監視データの送信機能(t)および受信機能(r)の少なくとも一方を備えた品質監視装置１がそれぞれ接続されており、送信機能を備えた品質監視装置１(t)から受信機能を備えた品質監視装置１(r)まで監視経路が設定される。なお、本実施形態では全ての品質監視装置１が監視データの送信機能(r)および受信機能(r)のいずれも備えているものとして説明する。
【００１９】
障害管理装置２は、監視データ送信機能(t)を備えた各品質監視装置１(t)に対して、監視経路を通して監視データを送信することを指示する。監視データ受信機能を備えた品質監視装置１(r)は、監視経路を通して受信した監視データの品質を監視し、品質劣化が検知されると障害管理装置２へ通報する。障害管理装置２は、各監視経路が通過するリンクに関する情報および品質劣化が検知された監視経路情報に基づいて障害リンクを特定する。これにより、リンク毎に品質監視装置１を設ける場合と比較して、必要な品質監視装置数の削減が図られる。前記障害管理装置２は、ネットワークNW上の各品質監視装置1と通信するための入出力インターフェースおよびそのアプリケーションが実装されたコンピュータで実現できる。
【００２０】
本発明では、障害リンクを必ず特定できるような複数の監視経路（監視用パスの経路群）が障害管理装置２により設定される。すなわち、本発明では単一リンク障害および二重リンク障害を想定し、これらのリンク障害が発生したとき、障害リンクを必ず特定できるような監視用パスの経路群が、後述する組合せグラフを利用することで設定される。
【００２１】
図２は、前記障害管理装置２の主要部の構成を示したブロック図であり、複数の監視経路（監視経路群）を設定する監視経路設定部２１と、各品質監視装置１から各監視経路に監視データを送信させて障害リンクを特定するリンク障害特定部２２とを含む。
【００２２】
前記リンク障害特定部２２は、前記設定された複数の監視経路に各品質監視装置１(t)から監視データを送信させ、当該監視データが品質監視装置１(r)に到達しない経路上、および監視データの到達が非常に遅いか、到達した監視データの誤り率が非常に高い経路上に障害が発生したと判定し、障害が発生している監視経路が通過し、かつ障害が発生していない監視経路が通過していないリンクを障害リンクと特定する。
【００２３】
前記監視経路設定部２１において、トポロジ取得部２０１は、監視対象ネットワークNWの物理的な実トポロジを取得する。基準組合せグラフ読込部２０２は、後述する基準組合せグラフを、記憶装置または入力インターフェース（いずれも、図示省略）から読み取る。組合せグラフ拡張部２０３は、前記基準組合せグラフを、監視対象のネットワークを模擬できる組合せグラフまで、所定の制約条件下で拡張する。監視経路決定部２０４は、前記拡張された組合せグラフに基づいて監視経路群を決定する。
【００２４】
以下、図面を参照して本発明の実施の形態について詳細に説明する。ここでは、初めに本発明の概要について説明し、次いで、具体的な動作について説明する。
【００２５】
本発明では、監視用パスの設定対象となる実ネットワークのトポロジを模擬し、かつ所定の制約条件を満足する組合せグラフを仮想的に構築し、この組合せグラフを用いて監視用パスを設定する。
【００２６】
前記組合せグラフは、各監視用パスのネットワーク上での連続性を考慮せずに、ネットワークの実リンクを模擬する仮想リンクと当該仮想リンクを通過する監視用パス組との関係を表すように作成される。本実施形態では、図３に一例を示したように、各監視用パスを組合せグラフのノード（黒丸●または白丸○）に対応させ、通過する監視用パス数が２本の仮想リンクは、当該通過する監視用パスに対応する２個のノードを接続する１本の実線仮想リンクによって表現される。また、通過する監視用パス数が３本の仮想リンクは、当該通過する監視用パスに対応する３個の頂点ノード（●）を接続する３本の破線仮想リンク列によって表現する。したがって、図３の組合せグラフは、以下の１３本の仮想リンクに対応する１３本の実リンクから構成されるネットワークトポロジを表現することになる。
【００２７】
・２本の監視用パスG0，A0が通過する実線仮想リンクL1
・２本の監視用パスA0，F0が通過する実線仮想リンクL2
・２本の監視用パスF0，I0が通過する実線仮想リンクL3
・２本の監視用パスG0，D0が通過する実線仮想リンクL4
・２本の監視用パスD0，E0が通過する実線仮想リンクL5
・２本の監視用パスE0，H0が通過する実線仮想リンクL6
・２本の監視用パスI0，C0が通過する実線仮想リンクL7
・２本の監視用パスC0，B0が通過する実線仮想リンクL8
・２本の監視用パスB0，H0が通過する実線仮想リンクL9
・２本の監視用パスA0，B0が通過する実線仮想リンクL10
・２本の監視用パスD0，C0が通過する実線仮想リンクL11
・２本の監視用パスE0，F0が通過する実線仮想リンクL12
・３本の監視用パスG0，I0、H0が通過する破線仮想リンク列L13
【００２８】
また、本発明では、監視負荷の低減および単一リンク障害と二重リンク障害とを識別するために、各実リンクに設定される監視用パスに以下の２つの条件が要求される。
【００２９】
・条件１：各実リンクを通過する監視用パス数は３本以下とする。これは、監視用データに起因するシステムの負荷を抑えるために設定される制約条件である。
・条件２：各実リンクを通過する監視用パス数は２本以上とする。これは、各リンクを通る監視用パス数が１本であると、当該監視用パスが通過する他のリンクが障害になった際、当該他のリンクの単一障害なのか、当該他のリンクと監視用パスが１本のみ通過するリンクとの二重リンク障害なのか識別できなくなるためである。
【００３０】
さらに、組合せグラフの構築に際して、全ての二重仮想リンク障害が互いに識別されるように、以下の５つの制約条件が課される。なお、監視用パス群によって全ての二重仮想リンク障害が互いに識別されれば、全ての単一仮想リンク障害も互いに識別できる。
【００３１】
・制約条件１：４つ以下の実線仮想リンクで構成される閉路を含まない。
・制約条件２：破線仮想リンク列で接続された２個の頂点間には３本以上の実線仮想リンクが存在しなければならない。
・制約条件３：２個の頂点を共有する２組の破線仮想リンク列の共有されない２個の頂点間には３本以上の実線仮想リンクが存在しなければならない。
・制約条件４：５つ以下の頂点で構成される３組の破線仮想リンク列を含まない。
・制約条件５：６つ以下の頂点で構成される４組の破線仮想リンク列を含まない。
【００３２】
図４(a)は、前記制約条件１を満足しない組合せグラフの一例であり、４本の実線仮想リンクにより閉路が形成されている。このような組合せグラフでは、監視用パスA、B、C、Dの品質劣化が検知された場合、監視用パスA、Bが通過する仮想リンクと監視用パスC、Dが通過する仮想リンクとの二重リンク障害であるのか、あるいは監視用パスA、Dが通過する仮想リンクと監視用パスB、Cが通過する仮想リンクとの二重リンク障害であるのかを識別することができない。これに対して、組合せグラフにおいて制約条件１が満足されれば、２本の監視用パスが通過する仮想リンクの全ての二重障害を互いに識別できる。
【００３３】
図４(b)は、前記制約条件２を満足しない組合せグラフの一例であり、破線仮想リンク列で接続された２個の頂点（C，D）の間には２本の実線仮想リンクしか存在しない。このような組合せグラフでは、監視用パスA，B，C，Dの品質劣化が検知された場合、監視用パスA，B，Cが通過する仮想リンクと監視用パスB，Dが通過する仮想リンクとの二重リンク障害であるのか、あるいは監視用パスA，B，Cが通過する仮想リンクと監視用パスC，Dが通過する仮想リンクとの二重リンク障害であるのかを識別することができない。
【００３４】
図４(c)は、前記制約条件３を満足しない組合せグラフの一例であり、２個の頂点（A，B）を共有する２組の破線仮想リンク列の共有されない２個の頂点（C，D）の間には２本の実線仮想リンクしか存在しない。このような組合せグラフでは、監視用パスA，B，C，D，Eの品質劣化が検知された場合、監視用パスA，B，Cが通過する仮想リンクと監視用パスD，Eが通過する仮想リンクとの二重リンク障害であるのか、監視用パスA，B，Dが通過する仮想リンクと監視用パスC，Eが通過する仮想リンクとの二重リンク障害であるのかを識別できない。
【００３５】
図４(d)は、前記制約条件４を満足しない組合せグラフの一例であり、５つ以下の頂点で構成される３組の破線仮想リンク列を含んでしまっている。このような組合せグラフでは、監視用パスA，B，C，D，Eの品質劣化が検知された場合、監視用パスA，B，Cが通過する仮想リンクと監視用パスC，D，Eが通過する仮想リンクとの二重リンク障害であるのか、監視用パスA，B，Dが通過する仮想リンクと監視用パスC，D，Eが通過する仮想リンクとの二重リンク障害であるのかを識別できない。組合せグラフにおいて、制約条件２，３，４が満足されれば、２本の監視用パスが通過する仮想リンクと３本の監視用パスが通過する仮想リンクとの二重障害を、他の全ての二重リンク障害から識別できる。
【００３６】
図４(e)は、前記制約条件５を満足しない組合せグラフの一例であり、６つ以下の頂点で構成される４組の破線仮想リンク列を含んでしまっている。このような組合せグラフでは、監視用パスA，B，C，D，E，Fの品質劣化が検知された場合、監視用パスA，B，Cが通過する仮想リンクと監視用パスD，E，Fが通過する仮想リンクとの二重リンク障害であるのか、監視用パスA，B，Dが通過する仮想リンクと監視用パスC，E，Fが通過する仮想リンクとの二重リンク障害であるのかを識別できない。組合せグラフにおいて、制約条件４，５が満足されれば、３本の監視用パスが通過する仮想リンクの全ての二重障害を互いに識別できる。
【００３７】
本実施形態では、以上に述べた２つの条件および５つの制約条件の下、組合せグラフの実線仮想リンク数と破線仮想リンク列数との和が、監視対象ネットワークの実リンク数と同数になるまで組合せグラフを拡張し、実線仮想リンク数と破線仮想リンク列数との和が実リンク数と同数以上になった拡張組合せグラフに基づいて監視用パスが決定される。
【００３８】
次いで、監視対象のネットワークを模擬した組合せグラフの作成方法を、図５のフローチャートおよび図６の模式図に沿って説明する。ステップＳ１では、監視対象となるネットワークのトポロジが、前記トポロジ取得部２０１により取得される。
【００３９】
ステップＳ２では、上記の各制約条件を満足する最小構成の組合せグラフが、前記基準組合せグラフ読込部２０２により基準（レベル０）組合せグラフとして取得される。本実施形態では、図６(a)に示したように、前記図３を参照して説明した組合せグラフがレベル０の基準組合せグラフとして取得される。この基準組合せグラフは上記の制約条件１，２を満足しており、１３本の仮想リンクを通過し、全ての単一仮想リンク障害および二重仮想リンク障害を特定できる９本の監視用パス群を示している。
【００４０】
ステップＳ３，Ｓ４では、前記基準組合せグラフを、その仮想リンク数（実線仮想リンク数と破線仮想リンク列数との和）がネットワークの実リンク数と同数となるまで、前記制約条件を満足させながら順次に拡張することで、ネットワークを模擬できる組合せグラフが作成される。
【００４１】
本発明では、基準組合せグラフに仮想ノードが１つずつ追加され、当該追加されたノードと既存の仮想ノードとを結ぶ仮想リンクが追加される。このような仮想ノードの追加および仮想リンクの追加による組合せグラフの拡張は、組合せグラフの仮想リンク数がネットワークの実リンク数に達するまで繰り返される。
【００４２】
なお、仮想ノードを１つずつ追加しても、構成可能な仮想リンク数が必ずしも１つずつ増える訳ではないが、本実施形態では、実リンク数と同数以上の仮想リンクを構成できるまで仮想ノードを１つずつ追加して行き、構成できるようになった段階で、実リンク数と同数の仮想リンクのみを組合せグラフ上に構成するようにしている。
【００４３】
次いで、組合せグラフの拡張方法について具体的に説明する。本実施形態では、上記のように、仮想ノードを１つずつ追加し、当該追加され仮想ノードと既存の仮想ノードとを結ぶことで仮想リンクが追加されるが、追加される仮想ノードや仮想リンクは、以下のようにして決定される。
【００４４】
初めに、組合せグラフ（初めは、レベル０の基準組合せグラフ）において破線仮想リンク列で接続されていたレベル０の各２頂点ノード[G0，H0]，[H0，I0]，[I0，G0]が、前記制約条件２に従って、最終的には図６(e)に示したように、新たに追加される各２個の頂点ノード(A1，E1)、(B1，F1)、(C1，D1)を経由する３本の実線仮想リンクによって接続されるまで、仮想ノードおよび仮想リンクの追加が繰り返される。
【００４５】
さらに具体的に説明すれば、初めに、図６(b)に示したように、基準組合せグラフに頂点ノードA1が追加され、当該頂点ノードA1と既存（レベル0）の頂点ノードG0とにより終端される実線仮想リンクL1が新たに構成される。本拡張によって、構成可能な仮想リンク数が１本増加する。
【００４６】
次いで、同図(c)に示したように、頂点ノードB1が追加され、当該頂点ノードB1と既存の頂点ノードH0とにより終端される実線仮想リンクL2、および頂点ノードC0、A1、B1を通過する破線仮想リンク列L3が新たに構成される。本拡張によって、構成可能な仮想リンク数が更に２本増加する。
【００４７】
次いで、同図(d)に示したように、頂点ノードC1が追加され、当該頂点ノードC1と既存の頂点ノードI0とにより終端される実線仮想リンクL4、頂点ノードA1、B1、C1を通過する破線仮想リンク列L5、頂点ノードA0、B1、C1を通過する破線仮想リンク列L6、および頂点ノードE0、C1、A1を通過する破線仮想リンク列L7が新たに構成される。本拡張によって、構成可能な仮想リンク数が更に４本増加する。
【００４８】
以下同様に、図示は省略するが次いで頂点ノードD1が追加され、当該頂点ノードD1と既存の頂点ノードG0とにより終端される実線仮想リンクL8、頂点ノードC1と頂点ノードD1とにより終端される実線仮想リンクL9、および頂点ノードC0、B1、D1を通過する破線仮想リンク列L10が新たに構成される。本拡張によって、構成可能な仮想リンク数が更に３本増加する。
【００４９】
さらに、次いで頂点ノードE1が追加され、当該頂点ノードE1と既存の頂点ノードH0とにより終端される実線仮想リンクL11、頂点ノードA1と頂点ノードE1とにより終端される実線仮想リンクL12、頂点ノードC0、D1、E1を通過する破線仮想リンク列L13、および頂点ノードA0、C1、E1を通過する破線仮想リンク列L14が新たに構成される。本拡張によって、構成可能な仮想リンク数が更に４本増加する。
【００５０】
さらに、次いで頂点ノードF1が追加され、当該頂点ノードF1と既存の頂点ノードI0とにより終端される実線仮想リンクL15、頂点ノードB1と頂点ノードF1とにより終端される実線仮想リンクL16、頂点ノードD1、E1、F1を通過する破線仮想リンク列L17、頂点ノードA0、E1、F1を通過する破線仮想リンク列L18、頂点ノードE0、F1、C1を通過する破線仮想リンク列L19、および頂点ノードE0、A1、F1を通過する破線仮想リンク列L20が新たに構成される。本拡張によって、構成可能な仮想リンク数が更に６本増加する。
【００５１】
このように、本実施形態では予め用意されているレベル０の組合せグラフを対象に、初めは、前記６つのレベル１頂点ノードのうちの３つ（A1，B1，C1）が１つずつ追加され、破線仮想リンク列で接続されている３つのレベル０頂点ノード（G1，H1，I1）が順番に１つずつ選択されて実線仮想リンク（Ｌ１，Ｌ２，Ｌ４）で接続される。その際、レベル１の組合せグラフにおいて最終的に構成可能な破線仮想リンク列の中で、レベル１頂点ノードを１つずつ追加する各段階で構成可能な破線リンク列があれば、各段階でそれらも構成される。
【００５２】
次いで、前記６つのレベル１頂点ノードのうちの残りの３つ（D1，E1，F1）が１つずつ追加され、最初に選択されたレベル０頂点ノードと３番目に追加されたレベル１頂点ノード、２番目に選択されたレベル０頂点ノードと最初に追加されたレベル１頂点ノード、および３番目に選択されたレベル０頂点ノードと２番目に追加されたレベル１頂点ノードとが、それぞれ実線仮想リンクで接続される。その際、レベル１の組合せグラフにおいて最終的に構成可能な破線仮想リンク列の中で、レベル１頂点ノードを１つずつ追加する各段階で構成可能な破線リンク列があれば、各段階でそれらも構成される。
【００５３】
図６(e)は、以上の手順でレベル0からレベル１への拡張が完了した時点での組合せグラフの構成を示した図であり、レベル０の基準組合せグラフにおいて破線仮想リンク列で接続されていた各２頂点ノード[G0，H0]，[H0，I0]，[I0，G0]が、新たに追加された各２個の頂点ノード(A1，E1)、(B1，F1)、(C1，D1)を経由する実線仮想リンクで接続されることにより、計９本の実線仮想リンクが新たに追加されている。
【００５４】
すなわち、レベルi（i > 0）の組合せグラフは、破線仮想リンク列で結ばれるレベルi-1の３個の頂点ノードの中の各２個の頂点ノードを、それぞれ新たに追加した２個のレベルiの頂点ノードを経由して直列接続することにより、最終的にはレベルi-1の組合せグラフ当該レベルに対して、２本の監視用パスが通過する９本の実線仮想リンクが新たに構成されるように拡張される。
【００５５】
さらに、図６(e)では図示が省略されているが、レベルi-1の３個の頂点ノードおよび新たに追加されたレベルiの６つの頂点ノードの計９個の頂点ノードから、前記制約条件が満足されるように選択された各３個のノードを経由する計１１本の破線仮想リンク列が新たに追加され、合計で２０本の仮想リンクが追加される。なお、前記新たに追加される１１本の破線仮想リンク列のうち、９本は１つのレベルi-1頂点と２つのレベルi頂点とを経由し、残り２本は６つのレベルi頂点の各３つを経由する。
【００５６】
ここではレベル0からレベル1への拡張を例にして説明したが、一般的にレベルiへの拡張では、３つのレベルi-1頂点ノードによって構成される破線仮想リンク列が2 i-1本存在するので、それらを順番に１つずつ選択して、前記レベル１への拡張と同様の手順で拡張を行なえば良い。
【００５７】
なお、上記の拡張手順において、レベル０の監視用パスC0，F0は、レベル１の監視用パスA1，B1、またはD1，E1、またはD1，B1と組み合わせることによって、それぞれ３本の破線仮想リンク列を新たに構成でき、各監視用パスの組合せは前記制約条件２を満足できる。
【００５８】
すなわち、レベル０の監視用パスC0に着目すれば、このC0とA1，B1とを通過する破線仮想リンク列、C0とD1，E1とを通過する破線仮想リンク列、およびC0とD1，B1とを通過する破線仮想リンク列の計３本の破線仮想リンク列を構成できる。また監視用パスF0に着目すれば、このF0とA1，B1とを通過する破線仮想リンク列、F0とD1，E1とを通過する破線仮想リンク列、およびF0とD1，B1とを通過する破線仮想リンク列の計３本の破線仮想リンク列を構成でき、合計で６本の破線仮想リンク列を構成できる。
【００５９】
しかしながら、制約条件３，４，５の違反を避けるために、ここでは監視用パスC0のみについて、レベル１の監視用パス組A1，B1との組合せ、D1，E1との組合せ、およびD1，B1との組合せを考え、C0とA1，B1とを通過する破線仮想リンク列、C0とD1，E1とを通過する破線仮想リンク列、およびC0とD1，B1とを通過する破線仮想リンク列の計３本の破線仮想リンク列が追加される。
【００６０】
同様に、レベル０の監視用パスA0，D0に着目した場合も、制約条件３，４，５の違反を避けるために、例えば監視用パスA0のみについて、レベル１の監視用パス組B1，C1との組合せ、E1，F1との組合せ、およびE1，C1との組合せを考え、A0とB1，C1とを通過する破線仮想リンク列、A0とE1，F1とを通過する破線仮想リンク列、およびA0とE1，C1とを通過する破線仮想リンク列の計３本の破線仮想リンク列が追加される。
【００６１】
同様に、レベル０の監視用パスD0，E0に着目した場合も、制約条件３，４，５の違反を避けるために、例えば監視用パスE0のみについて、レベル１の監視用パス組C1，A1との組合せ、F1，D1との組合せ、およびF1，A1との組合せを考え、E0とC1，A1とを通過する破線仮想リンク列、E0とF1，D1とを通過する破線仮想リンク列、およびE0とF1，A1とを通過する破線仮想リンク列の計３本の破線仮想リンク列が追加される。
【００６２】
図５へ戻り、ステップＳ４では、拡張後の組合せグラフで構成可能な仮想リンク総数が実リンク数と同数であるか否かが判定される。同数に満たなければステップＳ２へ戻り、前記レベル１の組合せグラフにおける拡張を行い、前記レベル１の組合せグラフにおける拡張が終了している場合には、レベル２の組合せグラフにおける拡張が同様に行なわれる。
【００６３】
すなわち、レベル２の組合せグラフもレベル１の組合せグラフと同様にして構成できる。図６(f)に示した様に、レベル２の組合せグラフでは、最終的に、破線仮想リンク列で接続されたレベル１の各２個の頂点ノードを、新たに追加した２個の頂点ノードを経由する３本の実線仮想リンクで接続する。レベル１の組合せグラフは２組の破線仮想リンク列を含むため、１２本のレベル２監視用パスの追加によって、レベル２監視用パスを含む２本の監視用パスが通過する１８本の実線仮想リンクと３本のレベル２監視用パスが通過する４本の破線仮想リンク列を新たに構成できる。更に、レベル２の組合せグラフでは、１本のレベル１以下の監視用パスと２本のレベル２監視用パスの組合せによって、１８本の破線仮想リンク列を新たに構成できる。
【００６４】
このように、本実施形態における組合せグラフのレベルi（i > 0）における拡張では、最終的に以下の３つの種類の仮想リンクが新たに構成できる。
【００６５】
第１種類：レベルi-1の３個の頂点ノードを経由する１つの破線仮想リンク列に対応して、３個の頂点ノードの中の各２個の頂点ノードを、それぞれ新たに追加した２個のレベルiの頂点ノードを経由して接続することにより、レベルi監視用パスを含む２本の監視用パスが通過する９本の実線仮想リンクを構成できる。
【００６６】
第２種類：レベルi-1の３個の頂点ノードを経由する１つの破線仮想リンク列に対応して、３本のレベルi監視用パスが通過する２本の破線仮想リンク列を構成できる。
【００６７】
第３種類：レベルi-1の３個の頂点ノードを経由する１つの破線仮想リンク列に対応して、１本のレベルi-１以下の監視用パスと２本のレベルi監視用パスが通過する９本の破線仮想リンク列を構成できる。
【００６８】
レベルi-1の３個の頂点ノードを経由する破線仮想リンク列の本数は2 i-1 であるため、レベルiへの拡張によって、最終的に20×2 i-1 本の仮想リンクを新たに構成できる。
【００６９】
以上のようにして、基準組合せグラフを、前記制約条件下で、１つずつ頂点ノードを追加して行くことによって拡張することにより、仮想リンク数が実リンク数と同数の組合せグラフが得られると、監視用パスの連続性は保障されないものの、全ての単一仮想リンク障害および二重仮想リンク障害を特定するための各仮想リンクと当該各仮想リンクを通過する監視用パス組との関係を表す組合せグラフが得られる。ステップＳ５では、前記拡張済みの組合せグラフに基づいて監視経路群が決定される。
【００７０】
次いで、図７に示した監視対象ネットワークを例にして、図１４のフローチャートに沿って監視経路の決定方法を説明する。
【００７１】
図７の監視対象ネットワークは、８つのノードと１６本の実リンクとによって構成され、ステップＳ１０では、上記の手順にしたがって、図８に示したように、監視対象ネットワークの実リンク数と同数の仮想リンクを含む組合せグラフが、前記基準組合せグラフを順次に拡張することで作成される。
【００７２】
本実施形態では、前記基準組合せグラフに仮想ノードが１つずつ追加され、当該追加されたノードと既存の仮想ノードとを結ぶ仮想リンクが追加され、このような仮想ノードの追加および仮想リンクの追加による組合せグラフの拡張が、組合せグラフの仮想リンク数がネットワークの実リンク数に達するまで繰り返される。
【００７３】
図８の組合せグラフでは、前記図６(a)の基準組合せグラフに２つの頂点ノードA1，B1を追加し、既存ノードG0と追加ノードA1とで終端される実線仮想リンクL1、既存ノードH0と追加ノードB1とで終端される実線仮想リンクL2、および既存ノードC0と追加ノードA1，B1とを結ぶ破線仮想リンク列L3の３本の仮想リンクを追加することにより、１６本の仮想リンクと１１本の監視用パス（９本の実線仮想リンクと２本の破線仮想リンク列）とを構成できる。
【００７４】
ステップＳ２０では、監視対象のネットワークを構成する実リンクと組合せグラフ中の仮想リンクとの対応関係が暫定的に決定される。本実施形態では、各リンクが以下の３つの手順により対応付けられる。
【００７５】
手順１：ネットワークを構成する各実リンクが、通過する監視用パス組を選択できる自由度に応じて順序付けされる。本実施形態では、接続している２個のノードの次数の積が大きい実リンクほど、監視用パス組の選択自由度が高いとして上位に順序付けられる。例えば、第１ノードと第８ノードとを結ぶ実リンクL1-8は、第１ノードの次数が「３」、第８ノードの次数が「４」なので、その積は「１２」となる。これに対して、第１ノードと第２ノードとを結ぶ実リンクL1-2は、第２ノードの次数が「５」なので、その積は「１５」となる。したがって、実リンクL1-2は実リンクL1-8よりも上位に位置付けられる。
【００７６】
なお、次数の積が等しい場合は、１つ順番が上位である実リンクと隣接している実リンクが上位に順序付けられる。例えば、第２ノードと第７ノードとを結ぶ実リンクL7-8および第２ノードと第３ノードとを結ぶ実リンクL2-3が選択された段階で、第２ノードと第４ノードとを結ぶ実リンクL2-4、第４ノードと第７ノードとを結ぶ実リンクL4-7、第５ノードと第７ノードとを結ぶ実リンクL5-7、および第７ノードと第８ノードとを結ぶ実リンクL7-8における次数の積は、いずれも「２０」である。この中で、１つ順番が上位である第２ノードと第３ノードとを結ぶ実リンクL2-3には、前記実リンクL2-4が隣接しているので、当該実リンクL2-4が上位に順序付けられる。なお、隣接リンクが複数ある場合には、ランダムに１本の実リンクが選択されて上位に順序付けられる。
【００７７】
手順２：組合せグラフ中の各仮想リンクが、組合せグラフによって指定されている監視用パス組の実現困難性に応じて順序付けされる。本実施形態では、通過する監視用パスの経路長の総和が大きい仮想リンクほど、実現困難性が高いとして上位に順序付けられる。なお、通過する監視用パスの経路長の総和が等しい場合は、１つ順番が上位の仮想リンクを通過する監視用パスがより多く通過する仮想リンクが上位に順序付けられる。なお、通過する監視用パスが同数の仮想リンクが複数ある場合には、ランダムに１本の仮想リンクが選択されて上位に順序付けられる。
【００７８】
手順３：以上のようにして順序付けられた実リンクおよび仮想リンクを、順番に一対一対応させることにより対応関係が決定される。すなわち、通過する監視用パス組を選択できる自由度が１番の実リンクと監視用パス組の実現困難性が１番の仮想リンクとが対応付けられ、各２番目のリンク同士が対応付けられ、以下同様に、順番が同一のリンク同士が一対一で対応付けられる。
【００７９】
本実施形態では、このような対応付けにより、監視用パスの連続性が可能な限り保障されるような仮想リンクと実リンクの対応関係が得られるので、後述するステップＳ５０における監視用パス数の増加が抑えられる。
【００８０】
ステップＳ３０では、前記ネットワークを構成する実リンクと組合せグラフ中の仮想リンクとの対応関係から、ネットワークの各実リンクを通過すべき監視用パス組を表現する初期組合せ表が導出される。
【００８１】
図９は、図８の組合せグラフから導出された初期組合せ表であり、実リンクと仮想リンクとの対応関係、および各リンクを通過する監視用パスの組合せが登録されている。本実施形態では、各監視用パスが通過すべきリンクの場所には「１」が、通過すべきでないリンクの場所には「０」が、それぞれ記されている。
【００８２】
ネットワークを構成する実リンクに関しては、上位に順序付けられるほど上方に記述されている。また、組合せグラフ中の仮想リンクに関しても、上位に順序付けられるほど上方に記述されている。このような初期組合せ表を参照すれば、ネットワークを構成する実リンクと組合せグラフ中の仮想リンクとの対応関係、ならびに各実リンクを通過すべき監視用パス組が明確になる。
【００８３】
ステップＳ４０では、前記初期組合せ表を構成する各監視用パスについて、その連続性を保障する困難さに応じて、連続性を保障する順番が以下の規則に従って決定される。
【００８４】
(1)経由リンク数が多い監視用パスほど先（上位）の順番とする。
【００８５】
(2)経由リンク数が等しい場合は順番が先である監視用パス群と多くのリンクを共用する監視用パスほど先の順番とする。
【００８６】
(3)共用するリンク数が等しい場合は、３本の監視用パスが通過するリンクを多く経由する監視用パスほど先の順番とする。
【００８７】
このように、本実施形態では連続性の保障が困難である監視用パスほど連続性の保障が先に実行されるので、後述するステップＳ５０における監視用パス数の増加が抑えられる。なお、図９の初期組合せ表では、当該ステップＳ４０で決定された監視用パスの順番も適用されており、右側の監視用パス欄において、より左側に記された監視用パスほど先の順番とされた監視用パスである。
【００８８】
ステップＳ５０では、初期組合せ表の右側に記された監視用パス欄から、全ての監視用パスの連続性が保障された最終組合せ表が導出される。
【００８９】
本実施形態では、ある監視用パスについて、連続性を満足しないリンクを通過する必要がある時は、連続性を満足するリンクの中で既に連続性が保障された監視用パスに関して、当該連続性を満足しないリンクと同一組の監視用パスが通過するリンクが存在するならば、そのリンクと当該連続性を満足しないリンクを組合せ表において入れ替える。これにより、既に連続性が保障された監視用パスに影響を与えることなく、当該監視用パスが連続したリンクを通過できることになる。
【００９０】
これを図１０の組合せ表を参照して具体的に説明すれば、図中右側の監視用パス欄において、左側から３番目までの３つの監視用パスG0、H0、C0は既に連続性が保証されている。これに対して、４番目の監視用パスI0は、実リンク(２，７)、(１，２)、(３，６)を通らなければならないが、実リンク(２，７)，(１，２)と(３，６)とは接続されていないので、その連続性が保証されていない。
【００９１】
一方、実リンク(１，８)に着目すると、当該実リンク(１，８)は前記相互に接続されている実リンク(２，７)，(１，２)のペアと一列に接続され、また前記連続性が既に保証されている監視用パスG0、H0、C0は、いずれも前記実リンク(１，８)，(３，６)を通過しないので、両者を入れ替えても監視用パスG0、H0、C0の連続性に影響を与えることが無い。したがって、ここでは図１１に示したように、実リンク(１，８)，(３，６)を相互に入れ替えることで監視用パスI0の連続性が新たに保証されるようになる。
【００９２】
なお、このようなリンク入れ替えを行っても連続性が保障されない場合は、当該監視用パスを連続性が保障される部分と保障されない部分とに分割する。そして、連続性が保障される部分のみを当該監視用パスと見なし、連続性が保障されない部分については、別の監視用パスとして新たに組合せ表の右側に追加する。
【００９３】
これを図１１の組合せ表を参照して具体的に説明すれば、監視用パスE0は実リンク(４，７)、(３，４)、(４，５)を通らなければならないが、実リンク(４，５)は実リンク(４，７)、(３，４)のペアと一列に連続していないので、その連続性が保証されていない。
【００９４】
しかも、図１１の組合せ表には、上述の条件を満足して実リンク(4, 5)と入れ替えることができる実リンクも存在しない。従って、当該リンク(4, 5)の部分については、図１２に示したように、別の監視用パスaが新たに組合せ表の右側に追加される。この場合、必要な監視用パス数は増加することになるが、前記ステップＳ２０ないしＳ４０の処理によって監視用パス数の増加は最小限に抑えられる。また、新たに組合せ表の右側に追加された監視用パスの連続性も、左側に記された監視用パスから同様の手順で保障できる。
【００９５】
以上のようにして、全ての監視用パスの連続性が保障された最終組合せ表が得られると、各監視用パスが通過すべきリンク情報から、全ての単一リンク障害および２重リンク障害を特定できる最少の監視用パス群の経路を決定する。
【００９６】
図１３は、図９の初期組合せ表に対して、各監視用パスの連続性を保障することによって得られた最終組合せ表であり、必要な監視用パス数は１４本となる。図１３に示されている最終組合せ表によって、全ての単一リンク障害および二重リンク障害を特定できる最少の監視用パスの経路が決定される。
【符号の説明】
【００９７】
１…品質監視装置，２…障害管理装置，２１…監視経路設定部，２２…リンク障害特定部，２０１…トポロジ取得部，２０２…基準組合せグラフ読込部，２０３…組合せグラフ拡張部，２０４…監視経路決定部
【特許請求の範囲】
【請求項１】
ネットワーク上の一部のノードに、監視データの送信機能および受信機能の少なくとも一方を備えた複数の品質監視装置を接続し、前記送信機能から受信機能へ複数の監視経路で監視データを送信し、その到達性に基づいて障害リンクを特定する障害リンク特定システムの監視経路設定装置において、
ネットワークの各実リンクを通過する監視用パスが仮想ノードで表現され、各監視用パスの通過する実リンクが前記各仮想ノードを結ぶ仮想リンクで表現される組合せグラフに基づいて監視用パス群を設定する障害管理装置を具備し、
前記障害管理装置が、
前記組合せグラフの基本形となるレベル０の組合せグラフを読み込む基準組合せグラフ読込手段と、
前記レベル０の組合せグラフを、その仮想リンク数が前記ネットワークの実リンク数に達するまで、前記監視用パス群により全ての単一リンク障害および二重リンク障害を識別できる制約条件下で順次に拡張する組合せグラフ拡張手段と、
前記拡張された組合せグラフに基づいて監視用パス群を決定する監視経路決定手段とを具備したことを特徴とする障害リンク特定システムの監視経路設定装置。
【請求項２】
前記組合せグラフ拡張手段は、前記レベル０の組合せグラフに仮想ノードを追加し、当該追加したノードと既存の仮想ノードとを結ぶ仮想リンク、および／または前記追加した仮想ノード同士を結んだ仮想リンクを追加することを特徴とする請求項１に記載の障害リンク特定システムの監視経路設定装置。
【請求項３】
前記組合せグラフ拡張手段は、前記仮想ノードの追加および仮想リンクの追加を、前記組合せグラフの仮想リンク数が前記ネットワークの実リンク数に達するまで繰り返すことを特徴とする請求項２に記載の障害リンク特定システムの監視経路設定装置。
【請求項４】
前記基準組合せグラフは、２本の監視用パスが通過する実線仮想リンクおよび３本の監視用パスが通過する破線仮想リンク列を含み、
前記組合せグラフ拡張手段は、拡張対象となるレベルi-1（i>0）の組合せグラフにおいて各々の破線仮想リンク列を構成するレベルi-1の３個のノードから選択した各２個を、それぞれ新たに追加したレベルiの各２個のノードを経由させて直列接続することで各３本の実線仮想リンクを追加し、計９本の実線仮想リンクを追加することを特徴とする請求項１ないし３のいずれかに記載の障害リンク特定システムの監視経路設定装置。
【請求項５】
前記組合せグラフ拡張手段は、前記追加されたレベルiの計６個のノードから選択した各３個のノードを接続する２組の破線仮想リンク列をさらに追加することを特徴とする請求項４に記載の障害リンク特定システムの監視経路設定装置。
【請求項６】
前記組合せグラフ拡張手段は、レベルi-1の１個のノードと前記追加されたレベルiの計６個のノードから選択した２個のノードとを接続する破線仮想リンク列をさらに追加することを特徴とする請求項４または５に記載の障害リンク特定システムの監視経路設定装置。
【請求項７】
前記組合せグラフ拡張手段は、
制約条件１：４つ以下の実線仮想リンクで構成される閉路を含まない
制約条件２：破線仮想リンク列で接続された２個のノード間には３本以上の仮想リンクが存在しなければならない
制約条件３：２個のノードを共有する２組の破線仮想リンク列の共有されない２個のノード間には３本以上の実線仮想リンクが存在しなければならない
制約条件４：５つ以下の仮想ノードで構成される３組の破線仮想リンク列を含まない
制約条件５：６つ以下の仮想ノードで構成される４組の破線仮想リンク列を含まない
の下で組合せグラフを拡張することを特徴とする請求項１ないし６のいずれかに記載の障害リンク特定システムの監視経路設定装置。
【請求項８】
前記監視経路決定手段は、
前記拡張された組合せグラフにおける仮想リンクと当該各仮想リンクを通過する監視用パスとの関係をネットワークの各実リンクと対応付ける初期組合せ表を作成する手段と、
各監視用パスの連続性が保障されるように、前記初期組合せ表を修正して最終組合せ表を作成する手段とを具備し、
前記最終組合せ表に基づいて監視用パス群を決定することを特徴とする請求項１ないし７のいずれかに記載の障害リンク特定システムの監視経路設定装置。
【請求項９】
前記初期組合せ表を作成する手段は、
ネットワークの各実リンクを、接続している２個のノードの次数の積が大きいほど上位に順序付ける手段と、
組合せグラフの各仮想リンクを、通過する監視用パスの経路長の総和が大きいほど上位に順序付ける手段と、
前記順序付けられた実リンクおよび仮想リンクを、その順序ごとに一対一対応させる手段とを含むことを特徴とする請求項８に記載の障害リンク特定システムの監視経路設定装置。
【請求項１０】
ネットワーク上の一部のノードに、監視データの送信機能および受信機能の少なくとも一方を備えた複数の品質監視装置を接続し、前記送信機能から受信機能へ複数の監視経路で監視データを送信し、その到達性に基づいて障害リンクを特定する障害リンク特定システムの監視経路設定方法において、
ネットワークの各実リンクを通過する監視用パスが仮想ノードで表現され、各監視用パスの通過する実リンクが前記各仮想ノードを結ぶ仮想リンクで表現される組合せグラフの、基本形となるレベル０の組合せグラフを読み込み、
前記レベル０の組合せグラフを、その仮想リンク数が前記ネットワークの実リンク数に達するまで、前記監視用パス群により全ての単一リンク障害および二重リンク障害を識別できる制約条件下で順次に拡張し、
前記拡張された組合せグラフに基づいて監視用パス群を決定することを特徴とする障害リンク特定システムの監視経路設定方法。
【請求項１】
ネットワーク上の一部のノードに、監視データの送信機能および受信機能の少なくとも一方を備えた複数の品質監視装置を接続し、前記送信機能から受信機能へ複数の監視経路で監視データを送信し、その到達性に基づいて障害リンクを特定する障害リンク特定システムの監視経路設定装置において、
ネットワークの各実リンクを通過する監視用パスが仮想ノードで表現され、各監視用パスの通過する実リンクが前記各仮想ノードを結ぶ仮想リンクで表現される組合せグラフに基づいて監視用パス群を設定する障害管理装置を具備し、
前記障害管理装置が、
前記組合せグラフの基本形となるレベル０の組合せグラフを読み込む基準組合せグラフ読込手段と、
前記レベル０の組合せグラフを、その仮想リンク数が前記ネットワークの実リンク数に達するまで、前記監視用パス群により全ての単一リンク障害および二重リンク障害を識別できる制約条件下で順次に拡張する組合せグラフ拡張手段と、
前記拡張された組合せグラフに基づいて監視用パス群を決定する監視経路決定手段とを具備したことを特徴とする障害リンク特定システムの監視経路設定装置。
【請求項２】
前記組合せグラフ拡張手段は、前記レベル０の組合せグラフに仮想ノードを追加し、当該追加したノードと既存の仮想ノードとを結ぶ仮想リンク、および／または前記追加した仮想ノード同士を結んだ仮想リンクを追加することを特徴とする請求項１に記載の障害リンク特定システムの監視経路設定装置。
【請求項３】
前記組合せグラフ拡張手段は、前記仮想ノードの追加および仮想リンクの追加を、前記組合せグラフの仮想リンク数が前記ネットワークの実リンク数に達するまで繰り返すことを特徴とする請求項２に記載の障害リンク特定システムの監視経路設定装置。
【請求項４】
前記基準組合せグラフは、２本の監視用パスが通過する実線仮想リンクおよび３本の監視用パスが通過する破線仮想リンク列を含み、
前記組合せグラフ拡張手段は、拡張対象となるレベルi-1（i>0）の組合せグラフにおいて各々の破線仮想リンク列を構成するレベルi-1の３個のノードから選択した各２個を、それぞれ新たに追加したレベルiの各２個のノードを経由させて直列接続することで各３本の実線仮想リンクを追加し、計９本の実線仮想リンクを追加することを特徴とする請求項１ないし３のいずれかに記載の障害リンク特定システムの監視経路設定装置。
【請求項５】
前記組合せグラフ拡張手段は、前記追加されたレベルiの計６個のノードから選択した各３個のノードを接続する２組の破線仮想リンク列をさらに追加することを特徴とする請求項４に記載の障害リンク特定システムの監視経路設定装置。
【請求項６】
前記組合せグラフ拡張手段は、レベルi-1の１個のノードと前記追加されたレベルiの計６個のノードから選択した２個のノードとを接続する破線仮想リンク列をさらに追加することを特徴とする請求項４または５に記載の障害リンク特定システムの監視経路設定装置。
【請求項７】
前記組合せグラフ拡張手段は、
制約条件１：４つ以下の実線仮想リンクで構成される閉路を含まない
制約条件２：破線仮想リンク列で接続された２個のノード間には３本以上の仮想リンクが存在しなければならない
制約条件３：２個のノードを共有する２組の破線仮想リンク列の共有されない２個のノード間には３本以上の実線仮想リンクが存在しなければならない
制約条件４：５つ以下の仮想ノードで構成される３組の破線仮想リンク列を含まない
制約条件５：６つ以下の仮想ノードで構成される４組の破線仮想リンク列を含まない
の下で組合せグラフを拡張することを特徴とする請求項１ないし６のいずれかに記載の障害リンク特定システムの監視経路設定装置。
【請求項８】
前記監視経路決定手段は、
前記拡張された組合せグラフにおける仮想リンクと当該各仮想リンクを通過する監視用パスとの関係をネットワークの各実リンクと対応付ける初期組合せ表を作成する手段と、
各監視用パスの連続性が保障されるように、前記初期組合せ表を修正して最終組合せ表を作成する手段とを具備し、
前記最終組合せ表に基づいて監視用パス群を決定することを特徴とする請求項１ないし７のいずれかに記載の障害リンク特定システムの監視経路設定装置。
【請求項９】
前記初期組合せ表を作成する手段は、
ネットワークの各実リンクを、接続している２個のノードの次数の積が大きいほど上位に順序付ける手段と、
組合せグラフの各仮想リンクを、通過する監視用パスの経路長の総和が大きいほど上位に順序付ける手段と、
前記順序付けられた実リンクおよび仮想リンクを、その順序ごとに一対一対応させる手段とを含むことを特徴とする請求項８に記載の障害リンク特定システムの監視経路設定装置。
【請求項１０】
ネットワーク上の一部のノードに、監視データの送信機能および受信機能の少なくとも一方を備えた複数の品質監視装置を接続し、前記送信機能から受信機能へ複数の監視経路で監視データを送信し、その到達性に基づいて障害リンクを特定する障害リンク特定システムの監視経路設定方法において、
ネットワークの各実リンクを通過する監視用パスが仮想ノードで表現され、各監視用パスの通過する実リンクが前記各仮想ノードを結ぶ仮想リンクで表現される組合せグラフの、基本形となるレベル０の組合せグラフを読み込み、
前記レベル０の組合せグラフを、その仮想リンク数が前記ネットワークの実リンク数に達するまで、前記監視用パス群により全ての単一リンク障害および二重リンク障害を識別できる制約条件下で順次に拡張し、
前記拡張された組合せグラフに基づいて監視用パス群を決定することを特徴とする障害リンク特定システムの監視経路設定方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１３−１１５５５０（Ｐ２０１３−１１５５５０Ａ）
【公開日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願番号】特願２０１１−２５８８５４（Ｐ２０１１−２５８８５４）
【出願日】平成２３年１１月２８日（２０１１．１１．２８）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２５年６月１０日（２０１３．６．１０）
【国際特許分類】
【出願日】平成２３年１１月２８日（２０１１．１１．２８）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]