(57)【要約】【課題】品質監視装置を接続できる端点ノードが予め指定された時に、任意の障害を識別できる最小本数の監視用パス群の経路を決定する障害管理装置を提供する。【解決手段】初期組合せ表登録部２０１は、指定された端点ノードや各監視用パスの連結性を考慮せずに初期組合せ表を取得する。最終組合せ表導出部２０２は、初期組合せ表に基づいて、任意のリンクペアの通過監視用パス組を繰り返し交換することにより、監視用パスおよび監視用パス候補を示す最終組合せ表を導出する。追加監視用パス設定部２０３は、指定された端点ノードで終端されない監視用パス候補に関して、指定された端点ノードまで延伸し、その際、対象とするリンク障害の特定が不可能となる場合には、指定された端点ノード間に新たな監視用パスを追加設定する。【選択図】図２
2014225775.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク上の一部のノードに、監視データの送信機能および受信機能の少なくとも一方を備えた複数の品質監視装置を接続し、前記送信機能から受信機能へ複数の監視用パスを通して監視データを送信し、その到達性に基づいて障害リンクを特定する障害管理装置において、
品質監視装置が接続される端点ノードを登録する手段と、
ネットワークにおける所定のリンク障害シナリオに対応し、各行がネットワークの各リンクに対応し、各列が監視用パスに対応し、各行列の交差欄に、各リンクを各監視用パスが通過するか否かの情報が登録された初期組合せ表を登録する手段と、
前記初期組合せ表において、各監視用パスのパスセグメントが相互に連続して前記端点ノードにより終端されるように、ランダムに選択した２つの行に関して、通過する監視用パス組の入れ替えを繰り返して最終組合せ表を導出する手段と、
前記最終組合せ表において、少なくとも一端が前記端点ノードにより終端されていない監視用パス候補を対象に、当該終端されていない側の端部を近傍の端点ノードまで延伸して監視用パス化する手段とを具備したことを特徴とする障害管理装置。
【請求項２】
前記監視用パス候補の端部を端点ノードまで延伸することにより新たに識別不能になるリンク障害ペアを検査する手段と、
新たに識別不能になるリンク障害ペアが存在すると、前記端点ノード間に新たな監視用パスを追加する手段とを具備したことを特徴とする請求項１に記載の障害管理装置。
【請求項３】
前記新たに識別不能になるリンク障害ペアを検査する手段は、識別不能になるリンク障害ペアが満足すべき必要条件によって限定されたリンク障害ペアを対象に検査を行うことを特徴とする請求項２に記載の障害管理装置。
【請求項４】
前記新たな監視用パスは、前記延伸された監視用パスの延伸以前の経路と同じ経路を辿り、当該延伸された監視用パスの延伸部分を構成するリンクを通過しないことを特徴とする請求項２または３に記載の障害管理装置。
【請求項５】
前記新たな監視用パスの前記延伸以前の経路以外のパス部分を対象に、新たに識別不能になるリンク障害ペアを検査する手段を具備し、
前記新たな監視用パスは、前記識別不能になるリンク障害ペアを生じさせるリンクを避けて設定されることを特徴とする請求項４に記載の障害管理装置。
【請求項６】
前記初期組合せ表が、監視対象のネットワークに関して、内部に３つ以下の頂点で構成される閉路を含まない組合せグラフに対応したことを特徴とする請求項１ないし５のいずれかに記載の障害管理装置。
【請求項７】
前記初期組合せ表が、監視対象のネットワークに関して、内部に４つ以下の頂点で構成される閉路を含まない組合せグラフに対応したことを特徴とする請求項１ないし５のいずれかに記載の障害管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、障害管理装置に係り、特に、監視対象のネットワークに対応したグラフを表現できる初期組合せ表を利用して、ネットワークの単一リンク障害および二重リンク障害を識別する障害管理装置に関する。
【背景技術】
【０００２】
特許文献１には、ネットワーク内の監視用パスを終端する品質監視装置において、監視用パスの品質劣化が検知されると、障害監視装置において、品質劣化の検知された監視用パスが共通に通過するリンクを障害リンクと推定する技術が開示されている。
【０００３】
特許文献２には、監視対象ネットワークの各リンクを通過する監視用パス組を表す組合せグラフを用いることにより、全ての単一リンク障害および二重リンク障害を特定できる監視用パス群の経路を容易に決定する技術が開示されている。
【０００４】
特許文献３には、監視対象ネットワークの各リンクを通過する監視用パス組を表す組合せグラフを用いることにより、任意の単一リンクの保守を行っている間の全ての単一リンク障害を特定できる監視用パス群の経路を容易に決定する技術が開示されている。
【０００５】
特許文献４には、少数のノードに品質監視装置を接続することにより、単一リンク障害（保守）復旧以前に発生する単一リンク障害あるいは単一リンク障害も含めた同時に発生する２重リンク障害を識別できる監視用パス群の経路を容易に決定する技術が開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第３８８５９３１号公報
【特許文献２】特願２０１１−２５８８５４号
【特許文献３】特願２０１２−１６１８０９号
【特許文献４】特願２０１３−０３７４５７号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１では、単一リンク障害を想定した場合、単一の障害リンクを正確に特定することができず、また品質監視装置を接続できるノードを予め指定することができない。特許文献２，３では、監視用パス群の発着ノードの数が多くなり、多数のノードに品質監視装置を接続する必要がある。特許文献４では、品質監視装置を接続するノード数を少なくできるものの品質監視装置を接続できるノードを予め指定することができない。
【０００８】
本発明の目的は、上記した従来技術の課題を解決し、品質監視装置を接続できる端点ノードが予め指定された時に、想定するリンク障害シナリオの下で、任意の障害を識別できる最小本数の監視用パス群の経路を決定できる障害管理装置を提供することにある。
【課題を解決するための手段】
【０００９】
上記の目的を達成するために、本発明は、ネットワーク上の一部のノードに、監視データの送信機能および受信機能の少なくとも一方を備えた複数の品質監視装置を接続し、前記送信機能から受信機能へ複数の監視用パスを通して監視データを送信し、その到達性に基づいて障害リンクを特定する障害管理装置において、以下のような手段を講じた点に特徴がある。
【００１０】
(1)品質監視装置が接続される端点ノードを登録する手段と、ネットワークにおける所定のリンク障害シナリオに対応した初期組合せ表を登録する手段と、初期組合せ表から最終組合せ表を導出する手段と、最終組合せ表において、少なくとも一端が前記端点ノードにより終端されていない監視用パス候補を対象に、当該終端されていない側の端部を近傍の端点ノードまで延伸して監視用パス化する手段とを具備した。
【００１１】
(2)監視用パス候補の端部を端点ノードまで延伸することにより新たに識別不能になるリンク障害ペアを検査する手段と、新たに識別不能になるリンク障害ペアが存在する場合には、前記端点ノード間に新たな監視用パスを追加する手段とを具備した。
【００１２】
(3)新たに識別不能になるリンク障害ペアを検査する手段は、限定されたリンク障害ペアを対象に検査を行うようにした。
【００１３】
(4)新たな監視用パスは、前記延伸された監視用パスの延伸以前の経路と同じ経路を辿り、当該延伸された監視用パスの延伸部分を構成するリンクを通過しないようにした。
【００１４】
(5)新たな監視用パスの前記延伸以前の経路以外のパス部分を対象に、新たに識別不能になるリンク障害ペアを検査する手段を具備し、新たな監視用パスは、識別不能になるリンク障害ペアを生じさせるリンクを避けて設定されるようにした。
【発明の効果】
【００１５】
本発明によれば、以下のような効果が達成される。
【００１６】
(1)想定する任意のリンク障害シナリオに応じた初期組合せ表が与えられた時、予め指定された端点ノードで終端され、任意の障害を特定できる最小本数の監視用パス群の経路を少ない計算量で算出できる。
【００１７】
(2)予め指定された端点ノードで終端される監視用パス群の必要数が少なくなるような最終組合せ表を導出できる。
【００１８】
(3)最終組合せ表において、指定された端点ノードで終端されない監視用パスを端点ノードまで延伸した際に、検査対象とするリンク障害ペアを限定して、新たに識別不能になったリンク障害ペアが存在するか否かを検査できるので、少ない計算量で検査できる。
【００１９】
(4)追加された監視用パスが通過できないリンクを特定する際に、検査対象とする障害ペアを限定して、各々のリンクを通過できるか否かを検査できるので、通過できないリンクを少ない計算量で特定できる。
【図面の簡単な説明】
【００２０】
【図１】本発明が適用されるネットワークの構成を示したブロック図である。
【図２】障害管理装置の主要部の構成を示したブロック図である。
【図３】障害監視対象ネットワークのトポロジを示した図である。
【図４】単一リンク障害（保守）復旧以前に発生する単一リンク障害を特定する組合せグラフに対応した初期組合せ表の一例を示した図である。
【図５】任意の単一リンクの保守中に発生する全ての単一リンク障害を特定する場合の初期組合せ表の作成手順を示したフローチャートである。
【図６】全ての２重リンク障害を特定する場合の初期組合せ表の作成手順を示したフローチャートである。
【図７】単一リンク障害も含めた同時に発生する２重リンク障害を特定する組合せグラフに対応した初期組合せ表の一例を示した図である。
【図８】経路決定処理手順の第１ステージにおいて最終組合せ表を導出する手順を示したフローチャートである。
【図９】図４の初期組合せ表から導出された最終組合せ表を示した図である。
【図１０】図７の初期組合せ表から導出された最終組合せ表を示した図である。
【図１１】経路決定処理手順の第２ステージにおいて実施される監視用パスの延伸および追加の手順を示したフローチャートである。
【図１２】監視用パス候補の延伸方法を示した模式図である。
【図１３】図９の最終組合せ表から算出された監視用パス群の経路を示した図である。
【図１４】図１０の最終組合せ表から算出された監視用パス群の経路を示した図である。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明が適用されるネットワークの構成を示したブロック図であり、監視対象のネットワークNWは、多数のノード装置nと、各ノード装置nを相互に接続する多数のリンクとから構成されている。
【００２２】
本発明では、監視データの送信機能(t)および受信機能(r)の少なくとも一方を備えた複数の品質監視装置１が、予め指定された複数のノード装置nに接続されており、送信機能を備えた品質監視装置１(t)から、受信機能を備えた品質監視装置１(r)まで監視用パスが設定される。なお、本実施形態では全ての品質監視装置１が監視データの送信機能(t)および受信機能(r)のいずれも備えているものとして説明する。
【００２３】
障害管理装置２は、品質監視装置１を接続できるノード装置n（端点ノード）が予め指定された時に、想定するリンク障害シナリオの下で、任意の障害を特定できる最小本数の監視用パス群の経路を決定し、監視データ送信機能(t)を備えた各品質監視装置１(t)に対して、前記決定された監視用パスの設定および当該監視用パスを通した監視データの送信を要求する。
【００２４】
監視データ受信機能を備えた品質監視装置１(r)は、監視用パスを通して受信した監視データの品質を監視し、品質劣化が検知されたパスに関して障害検出パス情報を生成し、これを障害管理装置２へ通報する。障害管理装置２は、品質劣化が検知された監視用パス情報、および各監視用パスが通過するリンクに関する監視用パス経路情報から障害リンクを特定する。
【００２５】
これにより、リンク毎に品質監視装置１を設ける場合と比較して、必要な品質監視装置数の削減が図られる。前記障害管理装置２は、ネットワークNW上の各品質監視装置1と通信するための入出力インターフェースおよびそのアプリケーションが実装されたコンピュータで実現できる。
【００２６】
図２は、前記障害管理装置２の主要部の構成を示したブロック図であり、各監視用パスが頂点で表現され、２本の監視用パスの通過するリンクが当該２頂点を端点とする辺で表現される組合せグラフに基づいて監視用パス群を設定する監視用パス設定部２１と、各品質監視装置１から各監視用パスに監視データを送信させて障害リンクを特定するリンク障害特定部２２とを含む。
【００２７】
前記リンク障害特定部２２は、前記監視用パス設定部２１により設定された複数の監視用パスに各品質監視装置１(t)から監視データを送信させ、当該監視データが品質監視装置１(r)に到達しないパス上、および監視データの到達が非常に遅いか、到達した監視データの誤り率が非常に高いパス上に障害が発生したと判定し、障害が発生している監視用パスが通過する一方、障害が発生していない監視用パスが通過していないリンクを障害リンクとして特定する。
【００２８】
前記監視用パス設定部２１において、初期組合せ表登録部２０１は、想定するリンク障害シナリオの下で、任意の障害の特定を可能とする監視用パス群に関して、登録されている端点ノードや各監視用パスの連結性を考慮せずに、各リンクを通過する監視用パス組を示す初期組合せ表を登録する。
【００２９】
前記初期組合せ表は、後に図４，７を参照して詳述するように、監視対象ネットワークのトポロジに基づいて、各行がネットワークの各リンクに対応し、各列が監視用パスに対応し、各行列の交差欄に、各リンクを各監視用パスが通過するか否かの情報が登録された仮想的な表である。すなわち、初期組合せ表の各行は、各リンクを通過する監視用パスの組（監視用パス組）を示している。
【００３０】
このような初期組合せ表の構成は、想定される障害シナリオに依存し、例えば、障害シナリオとして単一リンク障害（保守）復旧以前に発生する単一リンク障害あるいは単一リンク障害も含めた同時に発生する２重リンク障害を想定する場合、初期組合せ表は前記特許文献４に開示された手法により与えられる。
【００３１】
すなわち、後に詳述するように、単一リンク障害（保守）復旧以前に発生する単一リンク障害を特定する場合は、内部に３つの頂点以下で構成される閉路を含まない組合せグラフに対応した初期組合せ表（図４）が生成され、または予め与えられて登録される。これに対して、単一リンク障害も含めた同時に発生する２重リンク障害を想定する場合は、内部に４つ以下の頂点で構成される閉路を含まない組合せグラフに対応した初期組合せ表（図７）が生成され、または予め与えられて登録される。
【００３２】
図２へ戻り、最終組合せ表導出部２０２は、本発明に固有の経路決定処理手順の第１ステージを担い、前記初期組合せ表に基づいて、任意のリンクペアの通過監視用パス組を繰り返し交換することにより、障害監視対象ネットワーク上で監視用パスセグメントを連結させて監視用パス数が最小化され、更に指定された端点ノードで終端されない監視用パス数が最小化された最終組合せ表を導出する。
【００３３】
追加監視用パス設定部２０３は、前記経路決定処理手順の第２ステージを担い、登録されている端点ノードで終端されない監視用パス候補に関して、その端部を前記指定された端点ノードまで延伸し、その際、対象とするリンク障害の特定が不可能となる場合には、登録されている端点ノード間に新たな監視用パスを追加設定する。そして、追加設定済みの最終組合せ表で定義される複数の監視用パスセグメントを監視用パス群に決定して前記リンク障害特定部２２へ通知する。
【００３４】
本実施形態では、最終組合せ表において端点ノードで終端されない全ての監視用パス候補に対して、この様な操作を繰り返すことにより監視用パス群の経路が決定される。これにより、品質監視装置２を接続できる端点ノードが予め指定、登録された時に、想定する障害シナリオの下で、任意の障害を特定できる最小本数の監視用パス群の経路を少ない計算量で算出できるようになる。
【００３５】
次いで、図３に示した障害監視対象ネットワークを例にして、初期組合せ表の作成方法を詳細に説明する。本実施形態では、監視対象ネットワークの総ノード数が８個、総リンク数は１６本である。また、ここではノード１，６が、前記品質監視装置１の接続される端点ノードに予め指定され、登録されているものとして説明する。図４は、図３の障害監視対象ネットワークにおいて、単一リンク障害（保守）復旧以前に発生する単一リンク障害を特定するための初期組合せ表の一例を示した図である。
【００３６】
この初期組合せ表では、縦に並ぶ各行が、監視対象ネットワークを構成する各リンクに対応し、横に並ぶ各列が、各監視用パスに対応する。あるリンク（i，j）を、ある監視用パスA，B，C，D…が通過する時、初期組合せ表の対応する行列欄の要素が"１"となり、通過しない時は"０"となる。すなわち、初期組合せ表の各行は、各リンクを通過する監視用パス組を示す。初期組合せ表の作成手順は、監視用パス群が発生個所を特定するリンク障害シナリオの種類によって異なる。
【００３７】
次いで、図５，６のフローチャートを参照して、初期組合せ表の作成手順について説明する。本実施形態では、監視用パス帯域を最小化するために、各リンクを通過する監視用パスが２本に限定される。さらに、各監視用パスが頂点で表現され、各リンクが、これを通過する２本の監視用パスに対応する２つの頂点を接続する辺で表現される組合せグラフを用いて初期組合せ表が作成される。
【００３８】
図５は、監視用パス群によって任意の単一リンクの保守中に発生する全ての単一リンク障害を特定する場合の初期組合せ表の作成手順を示したフローチャートであり、ここでは、内部に３つ以下の頂点で構成される閉路を含まない組合せグラフとして、辺数(リンク数)に対する頂点数（監視用パス数）が最小となる、各部に等しい数の頂点を有する完全２部グラフに対応した組合せグラフを使って初期組合せ表が作成される。
【００３９】
すなわち、組合せグラフの各部における頂点を１個ずつ交互に追加し、完全２部グラフの形で接続できる既存の頂点と辺で接続する。既存の頂点との接続は、より新しく追加された既存の頂点から行っていく。図５のフローチャートでは、組合せグラフに新しく追加した頂点に対応する監視用パスに対応する初期組合せ表の列が変数pで表され、接続可能な既存の頂点に対応する監視用パスに対応する初期組合せ表の列が変数p'で表される。
【００４０】
ステップＳ１０１では、行数が監視対象ネットワークの総リンク数Lに等しく、列数が十分に大きな数Pに等しい表が作成され、全ての要素に"０"が書き込まれる。ステップＳ１０２では、注目行を指定する行変数ｌに"０"がセットされ、注目列を指定する第１列変数pに"１"がセットされる。ステップＳ１０３では、第１列変数pがインクリメントされる。ステップＳ１０４では、第１列変数pから"１"を減じて第２列変数p'が求められる。ステップＳ１０５では、行変数lがインクリメントされる。ステップＳ１０６では、l行のp列およびp'列に"１"が書き込まれる。
【００４１】
ステップＳ１０７では、現在の行変数lと総行数Lとが比較され、初めはl＜Lと判定されるのでステップＳ１０８へ進み、第２列変数p'がデクリメント(-2)される。ステップＳ１０９では、p'＞０であるか否かが判定される。p'＞０であれば前記ステップＳ１０５へ戻り、p'＞０でなければ前記ステップＳ１０３へ戻る。また、前記ステップＳ１０７において、l＜Lではないと判定されるとステップＳ１１０へ進み、最後に"１"が書き込まれた第p列よりも大きい、全く"１"が書き込まれなかった第p''(> p)列が削除される。
【００４２】
このように、監視用パス群によって任意の単一リンクの保守中に発生する全ての単一リンク障害を特定する場合は、内部に３つ以下の頂点で構成される閉路を含まない組合せグラフに対応した初期組合せ表が構成される。
【００４３】
なお、内部に３点以下で構成される閉路を含まない組合せグラフに対応する初期組合せ表であれば、上記以外の手順で作成された初期組合せ表でも、任意の単一リンクの保守中に発生する全ての単一リンク障害を特定できる、各リンクを通過する２本の監視用パス組を与える。前記図４に示した初期組合せ表は上記の手順で生成されている。図４の初期組合せ表においては、障害監視対象ネットワーク上で連結した監視用パスセグメント数は１５本である。また、端点ノード１，６で終端されない監視用パスセグメント数は１４本である。
【００４４】
図６は、監視用パス群によって全ての２重リンク障害を特定する場合の初期組合せ表の作成手順を示したフローチャートであり、ここでは、内部に４つ以下の頂点で構成される閉路を含まない組合せグラフ対応した初期組合せ表が作成される。
【００４５】
すなわち、組合せグラフにおける頂点を１個ずつ追加し、内部に４つ以下の頂点で構成される閉路を含まない形で接続できる既存の頂点と辺で接続する。既存の頂点との接続は、より新しく追加された既存の頂点から行っていく。図６では、組合せグラフに新しく追加した頂点に対応する監視用パスに対応する初期組合せ表の列が変数pで表され、接続可能な既存の頂点に対応する監視用パスに対応する初期組合せ表の列が変数p'で表される。
【００４６】
ステップＳ１５１では、行数が監視対象ネットワークの総リンク数Lに等しく、列数が十分に大きな数Pに等しい表が作成され、全ての要素に"０"が書き込まれる。ステップＳ１５２では、注目行を指定する行変数ｌに"０"がセットされ、注目列を指定する第１列変数pに"１"がセットされる。ステップＳ１５３では、第１列変数pがインクリメントされる。ステップＳ１５４は、第１列変数pから"１"を減じて第２列変数p'が求められる。ステップＳ１５５では、行変数lがインクリメントされる。ステップＳ１５６では、l行のp列およびｐ'列に"１"が書き込まれる。
【００４７】
ステップＳ１５７では、現在の行変数lと総列数Lとが比較され、初めはl＜Lと判定されるのでステップＳ１５８へ進む。ステップＳ１５８では、pの偶奇が判定され、奇数でなければステップＳ１５３へ戻り、奇数であればステップＳ１５９へ進んで第２列変数p'がデクリメント(-3)される。ステップＳ１６０では、p'＞０であるか否かが判定される。p'＞０であれば前記ステップＳ１５５へ戻り、p'＞０でなければ前記ステップＳ１５３へ戻る。
【００４８】
なお、前記ステップＳ１５７において、l＜Lではないと判定されるとステップＳ１６１へ進み、最後に"１"が書き込まれた第p列よりも大きい、全く"１"が書き込まれなかった第p''(> p)列が削除される。内部に４頂点以下で構成される閉路を含まない組合せグラフに対応する初期組合せ表であれば、上記以外の手順で作成された初期組合せ表でも、全ての２重リンク障害を特定できる、各リンクを通過する２本の監視用パス組を与える。
【００４９】
図７は、前記図３に示した監視対象ネットワークに対して、図６の手順によって作成された初期組合せ表を示している。図７に示した初期組合せ表では、障害監視対象ネットワーク上で連結した監視用パスセグメント数は１７本である。また、端点ノード１，６で終端されない監視用パスセグメント数は１７本である。
【００５０】
本実施形態では、上記のようにして生成された初期組合せ表が、前記初期組合せ表登録部２０１に外部から提供されても良いし、あるいは初期組合せ表登録部２０１が自ら初期組合せ表を生成しても良い。
【００５１】
図８は、前記最終組合せ表導出部２０２が、経路決定処理手順の第１ステージにおいて最終組合せ表を導出する手順を示したフローチャートであり、初期組合せ表の上で、繰り返し任意の２つの行を入れ替えることにより、複数の監視用パスセグメントを連結させて監視用パスセグメント数を最小化し、更に繰り返し任意の２つの行を入れ替えて、指定された端点ノードで終端されない監視用パスセグメント数が最小化された最終組合せ表を導出する。
【００５２】
すなわち、ステップＳ２０１では、初期組合せ表において、監視用パスセグメント数Pおよび指定された端点ノードで終端されない監視用パスセグメント数P'がカウントされる。ステップＳ２０２では、監視用パス組（初期組合せ表の各行）の選択回数値Cがリセット（＝０）される。ステップＳ２０３では、前記初期組合せ表から２つの行がランダムに選択される。
【００５３】
ステップＳ２０４では、選択された２つの行を入れ替えた場合の、監視対象ネットワーク上での監視用パスセグメント数Pおよび指定された端点ノードで終端されない監視用パスセグメント数P'がカウントされる。ステップＳ２０５では、監視用パスセグメント数Pが減少するか否かが判定され、減少するのであればステップＳ２０８へ進む。ステップＳ２０８では、前記監視用パス組の入れ替えが初期組合せ表に反映される。ステップＳ２０９では、前記選択回数値CをリセットしてステップＳ２０３へ戻る。
【００５４】
これに対して、前記ステップＳ２０５において、監視用パスセグメント数Pが減少しないと判定されればステップＳ２０６へ進む。ステップＳ２０６では、監視用パスセグメント数Pが一定（±０）であるか否かが判定される。一定ではないと判定されればステップＳ２１０へ進み、選択回数Cがインクリメントされる。ステップＳ２１１では、選択回数Cが上限閾値Cthと比較され、選択回数Cが上限回数Cthに達していれば当該処理を終了し、上限回数Cthに達していなければ、ステップＳ２０３へ戻って上記の各処理が繰り返される。
【００５５】
前記ステップＳ２０６において、入れ替えの前後で監視用パスセグメント数Pが不変（±０）であると判定されるとステップＳ２０７へ進み、監視用パスセグメント数P'が減少するか否かが判定される。減少するのであれば前記ステップＳ２０８へ進み、減少しなければ前記ステップＳ２１０へ進む。
【００５６】
上記の第１ステージにより、指定された端点ノードで終端されない監視用パスセグメント数が最小である最小本数の監視用パスセグメント群が得られる。すなわち、指定された端点ノードで終端されない監視用パス数が最小である最小本数の監視用パス群の経路を決定できる。
【００５７】
図９は、図４の初期組合せ表に上記の手順を適用することで導出された最終組合せ表を示した図であり、この最終組合せ表では監視用パス数が８本となり、その内、少なくとも一端が端点ノード１，６により終端されない監視用パス候補数は３本（A，G，H）となっている。
【００５８】
図１０は、図７の初期組合せ表に上記の手順を適用することで導出された最終組合せ表を示した図であり、この最終組合せ表では、監視用パス数が１１本となり、その内、少なくとも一端が端点ノード１、６で終端されない監視用パス候補数は８本（A，B，D，E，F，H，J，K）となっている。
【００５９】
図１１は、前記追加監視用パス設定部２０３が第２ステージにおいて実施する監視用パスの延伸および追加の手順を示したフローチャートであり、最終組合せ表において少なくとも一端が端点ノード（１，６）に接続されていない監視用パス候補について、当該一端側にパスセグメントを追加し、いずれかの端点ノードまで延伸させて監視用パス化する「延伸処理」、当該延伸によって新たに識別不能になるリンク障害ペアが存在する場合には監視用パスを新たに追加する「追加処理」が行われる。
【００６０】
ステップＳ３０１では、前記最終組合せ表において監視用パスが１本選択される。ステップＳ３０２では、当該パスの両端が端点ノード（１，６）で終端されているか否かが判定され、両端が終端されていればステップＳ３０８へ進み、少なくとも一端が終端されていなければステップＳ３０３へ進む。ステップＳ３０３では、前記終端されていない一端について、直近の端点ノードまで、例えばダイクストラ法により最短経路に沿って監視用パスが延伸される。図１２に示した例では、一端側のノードn0から最も近い端点ノードteまで、最短経路に沿って監視用パスpeが延伸される。尚、両端共に終端されていない場合は、両端について、それぞれ直近の端点ノードまで最短経路に沿って監視用パスが延伸される。
【００６１】
ステップＳ３０４，Ｓ３０５では、前記監視用パスの延伸によって、新たに識別不能になったリンク障害ペアが存在するか否かが検査される。検査対象とする障害ペアは、その数を必要最小限に抑えて計算量を少なくするために、識別不能になるリンク障害ペアが満足すべき以下の必要条件(1)〜(4)を満足するリンク障害F1，F2のペアに限定される。
【００６２】
(1)一方のリンク障害F1は、監視用パスの延伸部分を構成するリンクle（∈Le：監視用パスpeの延伸部分）を少なくとも１本含む。
(2)一方のリンク障害F1は、延伸以前の監視用パスを構成するリンクla（∈La：監視用パスpeの本来部分）を含まない。
(3)他方のリンク障害F2は、延伸以前の監視用パスを構成するリンクla（∈La）を少なくとも１本含む。
(4)複数リンク障害を特定する障害シナリオの場合、リンク障害F2は、複数のリンクを含む。
【００６３】
このように、検査対象の障害ペアを限定することにより、少ない計算量で、新たに識別不能になったリンク障害ペアが存在するか否かを検査できる。そして、新たに識別不能になったリンク障害ペアが存在する場合は、「延伸処理」による監視用パス化に続いて新たな監視用パス（追加監視用パス）を追加すべくステップＳ３０６へ進む。
【００６４】
追加監視用パスは、リンク障害F1に含まれるリンクを通過せず、リンク障害F2に含まれる少なくとも１本のリンクを通過する必要がある。そこで、追加監視用パスは、延伸以前の監視用パスと同じ経路を辿り、監視用パスの延伸部分を構成するリンクを通過しないことを基本条件とする。
【００６５】
ステップＳ３０６では、リンク障害F1に含まれるために追加監視用パスが通過できないリンクが特定される。すなわち、延伸以後の監視用パスを構成するリンク以外の各リンクlx（∈Lx=L-Le-La）について、追加監視用パスが当該リンクlxを通過した時に、識別不能になるリンク障害ペアが存在するか否かが検査される。検査対象とする障害ペアは、以下の条件(1)〜(5)を満足するリンク障害F1とリンク障害F2のペアに限定される。
【００６６】
(1)リンク障害F1は、当該リンクlxを含む。
(2)リンク障害F1は、監視用パスの延伸部分を構成するリンクle（∈Le）を少なくとも１本含む。
(3)リンク障害F1は、延伸以前の監視用パスを構成するリンクla（∈La）を含まない。
(4)リンク障害F2は、延伸以前の監視用パスを構成するリンクla（∈La）を少なくとも１本含む。
(5)複数リンク障害を特定する障害シナリオの場合、リンク障害F2は、複数のリンクを含む。
【００６７】
このように、本実施形態では検査対象とする障害ペアを限定することにより、少ない計算量で、識別不能になるリンク障害ペアが存在するか否かを検査できる。
【００６８】
識別不能になるリンク障害ペアが存在する場合、追加監視用パスは、当該リンクlxを通過することができないので、ステップＳ３０７では、当該リンクlxを避けて、端点ノード間に追加の監視用パスが設定される。具体的には、まず延伸以前の監視用パスの経路に沿って追加監視用パスが設定され、次いで、現状の終端ノードから、監視用パスの延伸部分を構成するリンクと前記ステップＳ３０６で特定されたリンクを通過しない条件の下で、最短経路に沿って、指定された端点ノードの１つまで追加監視用パスが設定される。
【００６９】
例えば、図１２において、延伸以前の監視用パスの経路Laに沿って、かつ監視用パスの延伸部分を構成するリンクle（∈Le）およびステップＳ３０６で特定されたリンクlx（∈Lx）を通過せずに、端点ノードt0とtaの間の最短経路に沿って追加監視用パスpaが設定される。
【００７０】
障害シナリオとして、単一リンク障害（保守）復旧以前に発生する単一リンク障害を想定する場合は、前記ステップＳ３０４において検査対象とするリンク障害F1とリンク障害F2とのペアは、以下のケースに限定される。
【００７１】
ケース１：F1={l1}、F2={l1,l2}、但し、l1∈Le、l2∈La
ケース２：F1={l1,l2}、F2={l1,l3}、但し、l1∈Le、l2∈Le∪Lx、l3∈La
ケース３：F1={l1,l2}、F2={l1,l3}、但し、l1∈Lx、l2∈Le、l3∈La
【００７２】
また、前記ステップＳ３０６において、リンクlxに関して検査対象とするリンク障害F1とリンク障害F2とのペアは、以下のケースに限定される。
ケース１：F1={l1,l2}、F2={l1,l3}、但し、l1∈Le、l2=lx、l3∈La
ケース２：F1={l1,l2}、F2={l1,l3}、但し、l1=lx、l2∈Le、l3∈La
【００７３】
例えば、障害シナリオとして、単一リンク障害も含めた同時に発生する２重リンク障害を想定する場合は、前記ステップＳ３０４において検査対象とするリンク障害F1とリンク障害F2とのペアは、以下のケースに限定される。
【００７４】
ケース１：F1={l1}、F2={l1,l2}、但し、l1∈Le、l2∈La
ケース２：F1={l1}、F2={l2,l3}、但し、l1∈Le、l2∈La、l3∈L
ケース３：F1={l1,l2}、F2={l1,l3}、但し、l1∈Le、l2∈Le∪Lx、l3∈La
ケース４：F1={l1,l2}、F2={l1,l3}、但し、l1∈Lx、l2∈Le、l3∈La
ケース５：F1={l1,l2}、F2={l3,l4}、但し、l1∈Le、l2∈Le∪Lx、l3∈La、l4∈L
【００７５】
また、前記ステップＳ３０６において、リンクlxに関して検査対象とするリンク障害F1とリンク障害F2とのペアは、以下のケースに限定される。
【００７６】
ケース１：F1={l1,l2}、F2={l1,l3}、但し、l1∈Le、l2=lx、l3∈La
ケース２：F1={l1,l2}、F2={l1,l3}、但し、l1=lx、l2∈Le、l3∈La
ケース３：F1={l1,l2}、F2={l3,l4}、但し、l1∈lx、l2∈Le、l3∈La、l4∈L
【００７７】
図１３は、図９の最終組合せ表から算出された監視用パス群の経路を示した図表であり、最終的に、必要な追加監視用パス数は３本となって、端点ノード１，６で終端された監視用パス数は１１本となる。
【００７８】
図１４は、図１０の最終組合せ表から算出された監視用パス群の経路を示した図表であり、最終的に、必要な追加監視用パス数は４本となって、端点ノード１，６で終端された監視用パス数は１５本となる。
【符号の説明】
【００７９】
１…品質監視装置，２１…監視用パス設定部，２２…リンク障害特定部，２０１…初期組合せ表登録部，２０２…最終組合せ表導出部，２０３…追加監視用パス設定部
【図１】
2014225775.tif 000003
【図２】
2014225775.tif 000004
【図３】
2014225775.tif 000005
【図４】
2014225775.tif 000006
【図５】
2014225775.tif 000007
【図６】
2014225775.tif 000008
【図７】
2014225775.tif 000009
【図８】
2014225775.tif 000010
【図９】
2014225775.tif 000011
【図１０】
2014225775.tif 000012
【図１１】
2014225775.tif 000013
【図１２】
2014225775.tif 000014
【図１３】
2014225775.tif 000015
【図１４】
2014225775.tif 000016