(57)【特許請求の範囲】
【請求項１】
複数のノード及び当該複数のノードを接続する複数のリンクを示すトポロジ情報を記憶する記憶部と、
隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように、前記トポロジ情報を更新し、当該更新されたトポロジ情報に基づいて、始点ノードから終点ノードに至るまでの経路を、通過するリンクの合計コストが低い順に、指定された数探索する経路探索部と、を備えること
を特徴とする経路探索装置。
【請求項２】
前記経路探索部は、前記探索された経路に、前記残されたリンク以外のリンクを戻すことで、前記探索された経路に多重接続リンクが含まれるようにし、当該多重接続リンクから一つずつリンクを選択することで、前記探索された経路に基づいて、前記始点ノードから前記終点ノードに至るまでの複数の経路パターンを生成し、前記探索された全ての経路のそれぞれから生成された全ての経路パターンから、通過するリンクの合計コストが低い順に、前記指定された数の経路候補を選択すること
を特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記経路探索部は、
前記経路候補に含まれているリンクを前記トポロジ情報から削除することで冗長経路用トポロジ情報を生成し、
隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように、前記冗長経路用トポロジ情報を更新し、
前記更新された冗長経路用トポロジ情報に基づいて、前記始点ノードから前記終点ノードに至るまでの経路の内、通過するリンクの合計コストが最も低い経路を冗長経路候補として探索すること
を特徴とする請求項２に記載の経路探索装置。
【請求項４】
前記経路探索部は、
前記経路候補に含まれているノードに接続されている全てのリンクを前記トポロジ情報から削除することで冗長経路用トポロジ情報を生成し、
隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように、前記冗長経路用トポロジ情報を更新し、
前記更新された冗長経路用トポロジ情報に基づいて、前記始点ノードから前記終点ノードに至るまでの経路の内、通過するリンクの合計コストが最も低い経路を冗長経路候補として探索すること
を特徴とする請求項２に記載の経路探索装置。
【請求項５】
複数のノード及び当該複数のノードを接続する複数のリンクを示すトポロジ情報を記憶する記憶部と、
隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように、前記トポロジ情報を更新し、当該更新されたトポロジ情報に基づいて、第１の始点ノードから第１の終点ノードに至るまでの経路を、指定された経由ノードで複数の区間に分割し、当該区間毎に、第２の始点ノード及び第２の終点ノードを特定して、当該更新されたトポロジ情報に基づいて、当該第２の始点ノード及び当該第２の終点ノードに至るまでの経路を、通過するリンクの合計コストが低い順に指定された数探索する経路探索部と、を備えること
を特徴とする経路探索装置。
【請求項６】
前記経路探索部は、前記探索された経路に、前記残されたリンク以外のリンクを戻すことで、前記探索された経路に多重接続リンクが含まれるようにし、当該多重接続リンクから一つずつリンクを選択することで、前記探索された経路に基づいて、前記第２の始点ノードから前記第２の終点ノードに至るまでの複数の経路パターンを生成し、前記探索された全ての経路のそれぞれから生成された全ての経路パターンから、通過するリンクの合計コストが低い順に、前記指定された数の経路候補を選択し、前記区間毎に、前記指定された数の経路候補から一つずつ選択して、組み合わせることで、複数の予備候補を生成し、当該予備候補の内、通過するリンクの合計コストが低い順に、前記指定された数の最終経路候補を選択する経路探索部と、を備えること
を特徴とする請求項５に記載の経路探索装置。
【請求項７】
前記経路探索部は、
前記最終経路候補に含まれているリンクを前記トポロジ情報から削除することで冗長経路用トポロジ情報を生成し、
隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように、前記冗長経路用トポロジ情報を更新し、
前記更新された冗長経路用トポロジ情報に基づいて、前記第１の始点ノードから前記第１の終点ノードに至るまでの経路の内、通過するリンクの合計コストが最も低い経路を冗長経路候補として探索すること
を特徴とする請求項６に記載の経路探索装置。
【請求項８】
前記経路探索部は、
前記最終経路候補に含まれているノードに接続されている全てのリンクを前記トポロジ情報から削除することで冗長経路用トポロジ情報を生成し、
隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように、前記冗長経路用トポロジ情報を更新し、
前記更新された冗長経路用トポロジ情報に基づいて、前記第１の始点ノードから前記第１の終点ノードに至るまでの経路の内、通過するリンクの合計コストが最も低い経路を冗長経路候補として探索すること
を特徴とする請求項６に記載の経路探索装置。
【請求項９】
複数のノード及び当該複数のノードを接続する複数のリンクを示すトポロジ情報を、隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように更新し、
前記更新されたトポロジ情報に基づいて、始点ノードから終点ノードに至るまでの経路を、通過するリンクの合計コストが低い順に、指定された数探索すること
を特徴とする経路探索方法。
【請求項１０】
前記探索された経路に、前記残されたリンク以外のリンクを戻すことで、前記探索された経路に多重接続リンクが含まれるようにし、当該多重接続リンクから一つずつリンクを選択することで、前記探索された経路に基づいて、前記始点ノードから前記終点ノードに至るまでの複数の経路パターンを生成し、
前記探索された全ての経路のそれぞれから生成された全ての経路パターンから、通過するリンクの合計コストが低い順に、前記指定された数の経路候補を選択すること
を特徴とする請求項９に記載の経路探索方法。
【請求項１１】
前記経路候補に含まれているリンクを前記トポロジ情報から削除することで冗長経路用トポロジ情報を生成し、
隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように、前記冗長経路用トポロジ情報を更新し、
前記更新された冗長経路用トポロジ情報に基づいて、前記始点ノードから前記終点ノードに至るまでの経路の内、通過するリンクの合計コストが最も低い経路を冗長経路候補として探索すること
を特徴とする請求項１０に記載の経路探索方法。
【請求項１２】
前記経路候補に含まれているノードに接続されている全てのリンクを前記トポロジ情報から削除することで冗長経路用トポロジ情報を生成し、
隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように、前記冗長経路用トポロジ情報を更新し、
前記更新された冗長経路用トポロジ情報に基づいて、前記始点ノードから前記終点ノードに至るまでの経路の内、通過するリンクの合計コストが最も低い経路を冗長経路候補として探索すること
を特徴とする請求項１０に記載の経路探索方法。
【請求項１３】
複数のノード及び当該複数のノードを接続する複数のリンクを示すトポロジ情報を、隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように更新し、
前記更新されたトポロジ情報に基づいて、第１の始点ノードから第１の終点ノードに至るまでの経路を、指定された経由ノードで複数の区間に分割し、
前記区間毎に、第２の始点ノード及び第２の終点ノードを特定して、前記更新されたトポロジ情報に基づいて、当該第２の始点ノード及び当該第２の終点ノードに至るまでの経路を、通過するリンクの合計コストが低い順に指定された数探索すること
を特徴とする経路探索方法。
【請求項１４】
前記探索された経路に、前記残されたリンク以外のリンクを戻すことで、前記探索された経路に多重接続リンクが含まれるようにし、当該多重接続リンクから一つずつリンクを選択することで、前記探索された経路に基づいて、前記第２の始点ノードから前記第２の終点ノードに至るまでの複数の経路パターンを生成し、
前記探索された全ての経路のそれぞれから生成された全ての経路パターンから、通過するリンクの合計コストが低い順に、前記指定された数の経路候補を選択し、
前記区間毎に、前記指定された数の経路候補から一つずつ選択して、組み合わせることで、複数の予備候補を生成し、当該予備候補の内、通過するリンクの合計コストが低い順に、当該指定された数の最終経路候補を選択すること
を特徴とする請求項１３に記載の経路探索方法。
【請求項１５】
前記最終経路候補に含まれているリンクを前記トポロジ情報から削除することで冗長経路用トポロジ情報を生成し、
隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように、前記冗長経路用トポロジ情報を更新し、
前記更新された冗長経路用トポロジ情報に基づいて、前記第１の始点ノードから前記第１の終点ノードに至るまでの経路の内、通過するリンクの合計コストが最も低い経路を冗長経路候補として探索すること
を特徴とする請求項１４に記載の経路探索方法。
【請求項１６】
前記最終経路候補に含まれているノードに接続されている全てのリンクを前記トポロジ情報から削除することで冗長経路用トポロジ情報を生成し、
隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように、前記冗長経路用トポロジ情報を更新し、
前記更新された冗長経路用トポロジ情報に基づいて、前記第１の始点ノードから前記第１の終点ノードに至るまでの経路の内、通過するリンクの合計コストが最も低い経路を冗長経路候補として探索すること
を特徴とする請求項１４に記載の経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索装置及び経路探索方法に関し、特に、隣接するノード間を多重接続している複数のリンクがある場合の経路探索装置及び経路探索方法に関する。
【背景技術】
【０００２】
近年の光伝送装置は、ネットワーク高信頼化のため、多方向に接続可能なメッシュ型の光ネットワークを構成している。このようなネットワークにおいて、２ノード間の経路は複数取り得るため、通過するリンクの合計コストが最も低くなるような経路を自動で探索する必要がある。最低コストの経路を探索する方法には、ダイクストラのアルゴリズムが広く知られている。
【０００３】
また、障害回避や負荷分散の目的で、予め複数の経路を探索する場合が多く、方法としては非特許文献１にあるようなｋ−ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムが知られている。ｋ−ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムは、コストの低い経路から昇順にｋ（任意の自然数）本の経路を探索することができる。
【０００４】
ｋ−ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムをはじめとする一般的な経路探索アルゴリズムは、隣接する２ノード間のリンク数が１本以下のネットワークに対して適用することができる。しかし、近年では、経路の冗長性を向上させる目的で、隣接する２ノード間に２本以上のリンク（以下、多重リンク）を張り巡らせているケースが多く、このようなネットワークに対して経路探索アルゴリズムを適用することができない。
【０００５】
そこで、特許文献１に記載されたネットワーク管理装置は、隣接する２ノード間に多重リンクが存在する場合、各ノードの接続接点に新たなノードを追加することによって多重リンクが存在しないトポロジを生成し、経路探索アルゴリズムを適用している。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１５−１１５６２３号公報
【非特許文献】
【０００７】
【非特許文献１】Ｊ．Ｙ．Ｙｅｎ，“Ｆｉｎｄｉｎｇ  ｔｈｅ  Ｋ  ｓｈｏｒｔｅｓｔ  ｌｏｏｐｌｅｓｓ  ｐａｔｈｓ  ｉｎ  ａ  ｎｅｔｗｏｒｋ”，Ｍａｎａｇｅｍｅｎｔ  Ｓｃｉｅｎｃｅ，Ｖｏｌ．１７，ｐｐ．７１２−７１６，Ｊｕｌｙ，１９７１
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献１に記載されたネットワーク管理装置では、多重リンクの数に応じてノード数及びリンク数が急激に増大してしまうため、経路探索に多くの時間を要する。
【０００９】
そこで、本発明は、多重リンクを含んだネットワークにおいて、ノード数及びリンク数を増大させることなく、複数の経路候補を合計コストが低い経路から昇順に探索できるようにすることを目的とする。
【課題を解決するための手段】
【００１０】
本発明の一態様に係る経路探索装置は、複数のノード及び当該複数のノードを接続する複数のリンクを示すトポロジ情報を記憶する記憶部と、隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように、前記トポロジ情報を更新し、当該更新されたトポロジ情報に基づいて、始点ノードから終点ノードに至るまでの経路を、通過するリンクの合計コストが低い順に、指定された数探索する経路探索部と、を備えることを特徴とする。
【００１１】
本発明の他の対象に係る経路探索装置は、複数のノード及び当該複数のノードを接続する複数のリンクを示すトポロジ情報を記憶する記憶部と、隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように、前記トポロジ情報を更新し、当該更新されたトポロジ情報に基づいて、第１の始点ノードから第１の終点ノードに至るまでの経路を、指定された経由ノードで複数の区間に分割し、当該区間毎に、第２の始点ノード及び第２の終点ノードを特定して、当該更新されたトポロジ情報に基づいて、当該第２の始点ノード及び当該第２の終点ノードに至るまでの経路を、通過するリンクの合計コストが低い順に指定された数探索する経路探索部と、を備えることを特徴とする。
【００１２】
本発明の一態様に係る経路探索方法は、複数のノード及び当該複数のノードを接続する複数のリンクを示すトポロジ情報を、隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように更新し、前記更新されたトポロジ情報に基づいて、始点ノードから終点ノードに至るまでの経路を、通過するリンクの合計コストが低い順に、指定された数探索することを特徴とする。
【００１３】
本発明の他の態様に係る経路探索方法は、複数のノード及び当該複数のノードを接続する複数のリンクを示すトポロジ情報を、隣接するノードの間を多重接続している複数のリンクの内、コストの最も低い一つのリンクが残るように更新し、前記更新されたトポロジ情報に基づいて、第１の始点ノードから第１の終点ノードに至るまでの経路を、指定された経由ノードで複数の区間に分割し、前記区間毎に、第２の始点ノード及び第２の終点ノードを特定して、前記更新されたトポロジ情報に基づいて、当該第２の始点ノード及び当該第２の終点ノードに至るまでの経路を、通過するリンクの合計コストが低い順に指定された数探索することを特徴とする。
【発明の効果】
【００１４】
本発明の一態様によれば、多重リンクを含んだネットワークを１本のリンクとみなして経路探索を実行するため、ノード数及びリンク数を増大させることなく、複数の経路候補を合計コストが低い経路から昇順に探索することができる。
【図面の簡単な説明】
【００１５】
【図１】実施の形態１〜３に係るネットワークシステムの構成を概略的に示すブロック図である。
【図２】実施の形態１〜３における経路探索装置の構成を概略的に示すブロック図である。
【図３】実施の形態１〜３におけるネットワーク情報の一例を示す概略図である。
【図４】実施の形態１〜３における経路探索条件を説明するための概略図である。
【図５】実施の形態１〜３におけるトポロジ情報の一例を示す概略図である。
【図６】（Ａ）及び（Ｂ）は、実施の形態１〜３における処理部のハードウェア構成を例示する概略図である。
【図７】実施の形態１における経路探索条件の一例を示す概略図である。
【図８】実施の形態１における更新後のトポロジ情報の一例を示す概略図である。
【図９】実施の形態１において、更新されたトポロジ情報で示されるネットワークシステムの第１例を示すブロック図である。
【図１０】実施の形態１において、更新されたトポロジ情報で示されるネットワークシステムの第２例を示すブロック図である。
【図１１】実施の形態１において、探索された経路における経由ノード及びそのリンクの組み合わせと、その合計コストとを示す概略図である。
【図１２】探索された２つの経由ノードにおけるリンクの組み合わせとその合計コストを示す概略図である。
【図１３】実施の形態１〜３における経路情報を構成する要素を説明するための概略図である。
【図１４】実施の形態１において経路探索結果を出力するための表示画面の一例を示す概略図である。
【図１５】実施の形態２における経路探索処理を示すフローチャートである。
【図１６】実施の形態２におけるノードの重複の判断例を示す概略図である。
【図１７】実施の形態２における経路探索条件の一例を示す概略図である。
【図１８】実施の形態２において経路候補を選択するための表示画面の一例を示す概略図である。
【図１９】実施の形態２における経路候補の選択例を示す概略図である。
【図２０】実施の形態３における予備候補の一例を示す概略図である。
【図２１】実施の形態３における経路探索処理を示すフローチャート（その１）である。
【図２２】実施の形態３における経路探索処理を示すフローチャート（その２）である。
【図２３】実施の形態３における経路探索条件の一例を示す概略図である。
【図２４】実施の形態３における経路候補の一例を示す概略図である。
【図２５】実施の形態３において、更新されたトポロジ情報で示されるネットワークシステムの第１例を示すブロック図である。
【図２６】実施の形態３における経路候補及びリンク冗長経路の一例を示す概略図である。
【図２７】実施の形態３において、更新されたトポロジ情報で示されるネットワークシステムの第２例を示すブロック図である。
【図２８】実施の形態３において経路探索結果を出力するための表示画面の一例を示す概略図である。
【発明を実施するための形態】
【００１６】
実施の形態１．
図１は、実施の形態１に係るネットワークシステム１００の構成を概略的に示すブロック図である。
図１に示されているように、ネットワークシステム１００は、６つのノード１１０Ａ〜１１０Ｆ（特に各々を区別する必要がない場合には、ノード１１０という）と、多重リンクを含む１２本のリンク１２０＃１〜１２０＃１２（特に各々を区別する必要がない場合には、リンク１２０という）と、経路探索装置１３０とを備える。
ここで、ノード１１０Ａ〜１１０Ｆの符号の一部Ａ〜Ｆは、各ノード１１０を識別するためのノード識別情報としてのノードＩＤを示している。また、リンク１２０＃１〜１２０＃１２の符号の一部＃１〜＃１２は、各リンク１２０を識別するためのリンク識別情報としてのリンクＩＤを示している。
【００１７】
図１に示されているように、ノード１１０Ａは、第１接続端１１１Ａａと、第２接続端１１１Ａｂと、第３接続端１１１Ａｃと、第４接続端１１１Ａｄとを備えている。ノード１１０Ｂは、第１接続端１１１Ｂａと、第２接続端１１１Ｂｂと、第３接続端１１１Ｂｃと、第４接続端１１１Ｂｄと、第５接続端１１１Ｂｅとを備えている。ノード１１０Ｃは、第１接続端１１１Ｃａと、第２接続端１１１Ｃｂと、第３接続端１１１Ｃｃとを備えている。ノード１１０Ｄは、第１接続端１１１Ｄａと、第２接続端１１１Ｄｂと、第３接続端１１１Ｄｃとを備えている。ノード１１０Ｅは、第１接続端１１１Ｅａと、第２接続端１１１Ｅｂと、第３接続端１１１Ｅｃと、第４接続端１１１Ｅｄと、第５接続端１１１Ｅｅとを備えている。ノード１１０Ｆは、第１接続端１１１Ｆａと、第２接続端１１１Ｆｂと、第３接続端１１１Ｆｃと、第４接続端１１１Ｆｄとを備えている。
【００１８】
経路探索装置１３０は、ネットワークシステム１００に存在する多重リンクを全て１本のリンクとみなして経路探索を実行する。
経路探索には、コストに基づいて経路を探索するアルゴリズムを用いる。ここでは、経路探索方法として、経路候補を合計リンクコスト昇順で複数探索することができるｋ−ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いて説明するが、これに限定されるものではない。
【００１９】
経路探索装置１３０は、ネットワークシステム１００における代表ノードに、例えば、ＴＣＰ／ＩＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）等の通信プロトコルを用いて接続されている。図１では、代表ノードはノード１１０Ｃである。
【００２０】
各ノード１１０間は、光ファイバで接続されており、それぞれの接続関係を示すネットワーク情報がネットワーク管理者により入力されることにより、経路探索装置１３０に、トポロジ情報として記憶される。トポロジ情報は、少なくとも、複数のノード１１０と、複数のノードを接続する複数のリンク１２０とを示す情報である。
【００２１】
また、各ノード１１０は、経路探索装置１３０からの経路探索結果に基づき、パスを設定する機能を備える。
【００２２】
図２は、経路探索装置１３０の構成を概略的に示すブロック図である。
図２に示されているように、経路探索装置１３０は、入出力部１３１と、処理部１３５と、通信部１３８と、記憶部１３９とを備える。
【００２３】
入出力部１３１は、情報の入力を受け付ける入力部及び情報を出力する出力部（表示部）として機能する。例えば、入出力部１３１は、経路探索装置１３０に接続されるキーボード及びマウス等の入力装置（図示せず）、並びに、液晶モニタ等の出力装置（図示せず）等のインターフェースである。
入出力部１３１は、情報入力部１３２と、経路探索条件入力部１３３と、経路探索結果出力部１３４とを備える。
【００２４】
情報入力部１３２は、各ノード１１０間の光ファイバの接続関係を示すネットワーク情報の入力を受け付ける。
図３は、ネットワーク情報の一例を示す概略図である。
図３に示されているように、ネットワーク情報１０１は、ノード列１０１ａと、接続端列１０１ｂとを有するテーブル形式の情報である。
ノード列１０１ａの各々の欄は、ノード１１０のノードＩＤを格納する。
接続端列１０１ｂの各々の欄は、ノード列１０１ａで識別されるノード１１０の接続端毎に、接続されているノードのノードＩＤを格納する。
【００２５】
図２に示されている経路探索条件入力部１３３は、ネットワーク管理者の要求する経路探索条件の入力を受け付ける。
図４は、経路探索条件入力部１３３で入力を受け付ける経路探索条件を説明するための概略図である。
図４に示されているように、ネットワーク管理者は、始点ノード、終点ノード、リンクコスト、経路導出数（ｋ）、経由ノード、経由禁止ノード、経由禁止リンク及び冗長経路探索の有無を入力する。始点ノード及び終点ノードは、経路探索において必須となるが、残りは、任意で入力が可能である。
【００２６】
図２に示されている経路探索結果出力部１３４は、処理部１３５にて探索された経路候補を示す経路情報を出力する。例えば、経路探索結果出力部１３４は、経路候補から予め定められた形式で表示する表示画面を生成して、この表示画面を表示する。
【００２７】
処理部１３５は、この経路探索装置１３０全体の制御を司り、入出力部１３１、通信部１３８及び記憶部１３９の制御と、入力された情報の処理とを行う。
処理部１３５は、情報処理部１３６と、経路探索部１３７と備える。
【００２８】
情報処理部１３６は、情報入力部１３２から入力されたネットワーク情報に基づいて、トポロジ情報を生成する。
図５は、トポロジ情報の一例を示す概略図である。
図５に示されているように、トポロジ情報１０２は、ノード列１０２ａと、ノード種別列１０２ｂと、接続端列１０２ｃとを有するテーブル形式の情報である。
ノード列１０２ａの各々の欄は、ノード１１０のノードＩＤを格納する。
ノード種別列１０２ｂの各々の欄は、ノード列１０２ａで識別されるノード１１０の種別を格納する。経路探索条件で始点ノードと終点ノードが指定されるため、始点ノードに指定されたノード１１０及び終点ノードに指定されたノード１１０に対応する欄に、始点ノード又は終点ノードであることを示す情報が格納される。なお、図５に示されているように、デフォルトでは、ノード種別列１０２ｂには、指定されていないことを示す「−」が格納されている。
接続端列１０２ｃの各々の欄は、ノード列１０２ａで識別されるノード１１０の接続端毎に、接続されているリンク１２０のリンクＩＤが格納される。なお、経路探索条件で各リンク１２０のコストが指定されるため、経路探索条件が入力された際に、各リンクＩＤの後ろの括弧内に、指定されたコストの値が格納される。なお、図５に示されているように、デフォルトでは、この括弧内には、コストが指定されていないことを示す「−」が格納されている。
【００２９】
そして、図２に示されている情報処理部１３６は、経路探索条件入力部１３３から入力された経路探索条件に基づいて、トポロジ情報を更新する。例えば、情報処理部１３６は、経路探索条件に基づいて、トポロジにおいて、使用不可能なノード１１０及びリンク１２０を削除する。また、情報処理部１３６は、経路探索条件で経由ノードが指定されている場合は、該当ノードに経由ノードのマーカーを付加し、経路探索部１３７へ更新されたトポロジ情報を引き渡す。
【００３０】
経路探索部１３７は、情報処理部１３６で更新されたトポロジ情報と、経路探索条件入力部１３３で入力された経路探索条件とをインプットとして、経路候補を複数探索する。
例えば、経路探索部１３７は、隣接するノード１１０の間を多重接続している複数のリンク１２０の内、コストの最も低い一つのリンク１２０が残るように、トポロジ情報を更新する。
また、経路探索部１３７は、更新されたトポロジ情報に基づいて、始点ノードから終点ノードに至るまでの経路を、通過するリンク１２０の合計コストが低い順に、指定された数探索する。
さらに、経路探索部１３７は、探索された経路に、残されたリンク１２０以外のリンク１２０を戻すことで、探索された経路に多重接続リンクが含まれるようにし、この多重接続リンクから一つずつリンク１２０を選択することで、探索された経路に基づいて、始点ノードから終点ノードに至るまでの複数の経路パターンを生成する。
そして、経路探索部１３７は、探索された全ての経路のそれぞれから生成された全ての経路パターンから、通過するリンク１２０の合計コストが低い順に、指定された数の経路候補を選択する。
なお、経路探索部１３７での処理の詳細は、後述する。
【００３１】
以上に記載された処理部１３５は、例えば、図６（Ａ）に示されているように、メモリ１５１と、メモリ１５１に格納されているプログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）等のプロセッサ１５２とにより構成することができる。このようなプログラムは、ネットワークを通じて提供されてもよく、また、記録媒体に記録されて提供されてもよい。
【００３２】
また、処理部１３５の一部又は全部は、例えば、図６（Ｂ）に示されているように、単一回路、復号回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔｓ）又はＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）等の処理回路１５３で構成することもできる。
【００３３】
図２に示されている通信部１３８は、各ノード１１０との通信を行う。具体的には、通信部１３８は、ＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）等の通信インターフェースにより実現することができる。
例えば、通信部１３８は、各ノード間の光ファイバの接続情報を情報入力部１３２へ送信する。また、通信部１３８は、経路探索結果出力部１３４によって出力された経路情報に基づいて選択された選択経路情報を、各ノード１１０へ送信する。このような選択経路情報に基づいて、各ノード１１０は、新規のパスを設定することができる。
【００３４】
記憶部１３９は、経路探索装置１３０の機能を実現するプログラムのほかに、経路探索装置１３０で必要な情報を記憶する。例えば、記憶部１３９は、処理部１３５が経路探索を行うときに参照する各種データ（トポロジ情報、及び、経路探索条件を示す経路探索条件情報等）を記憶する。この記憶部１３９は、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、フラッシュメモリ及びＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）等の記憶装置により実現することができる。
【００３５】
次に、経路探索装置１３０の動作例を説明する。
まず、経路探索装置１３０の経路探索条件入力部１３３は、経路探索条件の入力を受け付ける。ここでは、図７に示されている経路探索条件１０３が入力されたものとする。なお、このような経路探索情報が入力されると、経路探索条件入力部１３３は、入力された経路探索条件を示す経路探索条件情報を記憶部１３９に記憶する。
【００３６】
図７に示されている経路探索条件１０３では、経由ノードが指定されておらず、冗長経路探索も行わないことが指定されている。
経路探索条件にて経由ノードが指定された場合の探索方法は、実施の形態２にて説明する。また、冗長経路探索を行う場合の探索方法は、実施の形態３にて説明する。
【００３７】
図７に示されている経路探索条件１０３によると、図１に示されているネットワークシステム１００において、リンク１２０＃１２を通過することなく、ノード１１０Ａからノード１１０Ｆまでの合計リンクコストが低い順に２本の経路を探索することが経路探索装置１３０の目的となる。
【００３８】
情報処理部１３６は、入力された経路探索条件１０３に基づいて、始点ノード、終点ノード及びリンクコストを追加することで、図５に示されているトポロジ情報１０２を、図８に示されているトポロジ情報１０２−１に更新する。
なお、経由禁止ノードが指定されている場合には、情報処理部１３６は、トポロジ情報１０２において、経由の禁止が指定されたノード１１０に接続されている全リンク１２０を削除する。経由禁止リンクが指定されている場合には、情報処理部１３６は、トポロジ情報１０２において、指定されたリンク１２０を削除する。
図８に示されているトポロジ情報１０２−１によると、ネットワークシステム１００は、図９に示されていようなネットワークシステム１００−１として認識される。なお、図９では、ノード１１０間において最も低コストのリンク１２０が太線で示されており、リンク１２０＃１２は削除されたものとする。
【００３９】
次に、ネットワークシステム１００に多重リンク（図１では、リンク１２０＃１及びリンク１２０＃２、リンク１２０＃４及びリンク１２０＃５、リンク１２０＃６及びリンク１２０＃７、リンク１２０＃８及びリンク１２０＃９）が存在する場合、経路探索部１３７は、多重リンクの中から最もコストが低いリンク（以下、低コストリンクともいう）を１本選択することで、トポロジ情報を更新する。そして、選択されなかったリンク１２０は、ｋ−ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムにおける探索の対象外とする。
低コストリンク以外のリンク１２０を全て削除するように、トポロジ情報を更新すると、ネットワークシステム１００−１構成は、図１０に示されているネットワークシステム１００−２のようになる。なお、実施の形態１では、最大で２重のリンク１２０しか取り扱っていないが、リンク１２０はより多重化されていてもよい。
【００４０】
次に、経路探索部１３７は、更新されたトポロジ情報に基づいて、始点ノード（ノード１１０Ａ）から終点ノード（ノード１１０Ｆ）までの経路を合計コストの低い経路から順に２本探索する。この探索には、ｋ−ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムが使用されており、探索数ｋ＝２と設定されている場合、探索される経路は、図１１に示されているようになる。
【００４１】
次に、経路探索部１３７は、ｋ＝１の経路から順、言い換えると、合計コストの低い経路から順に、探索された経由ノード間の多重リンクを削除前の状態に戻して、探索された経由ノードにおけるリンク１２０の全組合せパターン（全経路パターン）の合計コストを再度算出する。ここで、探索された経由ノードにおいて、経由リンクの異なる経路は、新たな経路として合計コストが算出される。そして、経路探索部１３７は、合計コストの低いｋ本（ここでは、２本）を経路候補として選択する。
図１２は、探索された２つの経由ノードにおけるリンク１２０の組み合わせ（経路パターン）とその合計コストを示す概略図である。
【００４２】
そして、経路探索部１３７は、以上のようにして、探索された経由ノードにおける全てのリンク１２０の組み合わせにおいて、最も合計コストの低いｋ本の経路を、経路候補とする。このような選択を行うことにより、経路探索部１３７は、例えば、図１２において、Ｎｏ．５の経路よりも合計コストが低いＮｏ．２の経路を経路候補として選択することができる。
なお、ｎ（ｎは、１≦ｎ≦ｋを満たす整数）番目の経路を選択する際、合計コストが同一の経路が複数存在する場合、経路探索部１３７は、ｎ−１番目の経路とは経由ノードが異なる経路を優先的に選択するものとする。
【００４３】
そして、経路探索部１３７は、選択された経路候補を示す経路情報を生成して、経路探索結果出力部１３４に出力（表示）させる。ここで、経路情報を構成する要素の説明は、図１３に示されているとおりである。そして、経路探索結果出力部１３４には、例えば、図１４に示されているような表示画面ＩＭ１が表示されて、ネットワーク管理者は、これらの候補から、採用する経路を特定する。経路探索部１３７は、ネットワーク管理者より選択された経路を示す選択経路情報を生成し、通信部１３８を介して、各ノード１１０に送信する。なお、選択経路情報の要素は、図１３に示されている経路情報の要素と同一である。
【００４４】
以上のように、経路探索装置１３０は、多重リンクを含んだネットワークシステム１００に対して、複数の経路候補をコストの低いものから昇順に高速に探索できる。多重リンクを含むネットワークシステム１００でありながら、特許文献１のように余計なノードを追加する必要がないため、ｋ−ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムを用いた経路探索時間を短くすることができる。また、低コストリンクのみを使用して経路を探索した後、多重リンクの組み合わせを調べることにより、より低コストの複数の経路候補をネットワーク管理者に提示することができる。
【００４５】
なお、本手順により、経路探索条件を満たす経路を１本も探索できなかった場合、経路探索部１３７は、探索を強制終了するようにしてもよい。このとき、経路探索部１３７は、図２に示されている経路探索結果出力部１３４に経路を発見できなかったことを通知するメッセージを出力させ、経路探索条件の再入力を促す画面を表示させてもよい。
【００４６】
実施の形態２．
実施の形態１では、多重リンクを含むネットワークシステム１００において、始点ノードから終点ノードまでの経路を複数探索する方法を示したが、経路探索条件に経由ノードを指定することもできる。実施の形態２では、実施の形態１の機能に加えて、一又は複数の経由ノードを指定することができ、指定された順にノード１１０を通過し、かつノード１１０の重複が起こらない経路を複数探索することが可能となる。
なお、実施の形態２におけるネットワークシステム１００の構成は、実施の形態１におけるネットワークシステム１００と同様である。また、実施の形態２における経路探索装置１３０の構成も、実施の形態１における経路探索装置１３０と同様である。
【００４７】
実施の形態２では、複数のノード１１０の内、一又は複数のノード１１０が経由ノードとして指定されているので、経路探索部１３７は、第１の始点ノードから第１の終点ノードまでの経路を、経由ノードで複数の区間に分割し、その区間毎に、第２の始点ノード及び第２の終点ノードを特定する。例えば、第１の経由ノード及び第２の経由ノードがこの順番で指定された場合、経路は、始点ノード及び第１の経由ノードによる第１の区間、第１の経由ノード及び第２の経由ノードによる第２の区間、並びに、第２の経由ノード及び終点ノードによる第３の区間に分割される。第１の区間では、第１の経由ノードが終点ノードとなる。第２の区間では、第１の経由ノードが始点ノードとなり、第２の経由ノードが終点ノードとなる。第３の区間では、第２の経由ノードが始点ノードとなる。
【００４８】
そして、経路探索部１３７は、区間毎に、更新されたトポロジ情報に基づいて、第２の始点ノード及び第２の終点ノードに至るまでの経路を、通過するリンクの合計コストが低い順に指定された数探索する。
また、経路探索部１３７は、探索された経路に、残されたリンク以外のリンクを戻し、探索された経路に多重接続リンクが含まれるようにし、この多重接続リンクから一つずつリンクを選択することで、探索された経路に基づいて、第２の始点ノードから第２の終点ノードに至るまでの複数の経路パターンを生成し、探索された全ての経路のそれぞれから生成された全ての経路パターンから、通過するリンクの合計コストが低い順に、指定された数の経路候補を選択する。
さらに、経路探索部１３７は、区間毎に、指定された数の経路候補から一つずつ選択して、組み合わせることで、複数の予備候補を生成し、予備候補の内、通過するリンクの合計コストが低い順に、指定された数の最終経路候補を選択する。
【００４９】
図１５は、実施の形態２における経路探索処理を示すフローチャートである。
まず、経路探索条件入力部１３３が経路探索条件の入力を受けると、情報処理部１３６は、入力された経路探索条件に基づいて、トポロジ情報を更新する（Ｓ１０）。ここでは、情報処理部１３６は、実施の形態１と同様に、始点ノード、終点ノード及びリンクコスト等の経路探索条件をもとにトポロジ情報を更新する。
【００５０】
次に、経路探索部１３７は、経路探索条件に経由ノードが指定されているかどうかを確認する（Ｓ１１）。指定されていない場合（Ｓ１１でＮｏ）は、処理はステップＳ１２に進み、指定されている場合には、処理はステップＳ１３に進む。
ステップＳ１２では、経路探索部１３７は、実施の形態１と同様の処理を行い、ｋ本（経路導出数）の経路候補を選択する。
【００５１】
ステップＳ１３では、経由ノードが指定されているため、経路探索部１３７は、始点ノードから終点ノードまでの間を、経由ノードにより複数の区間に分割する。そして、経路探索部１３７は、分割された区間毎に、実施の形態１と同様の手順で、ｋ本の経路候補を選択する。例えば、始点ノードとしてノード１１０Ａ及び終点ノードとしてノード１１０Ｆが指定されており、経由ノードとして、ノード１１０Ｂ及びノード１１０Ｄが指定されている場合には、経路探索部１３７は、ノード１１０Ａ及びノード１１０Ｂの区間、ノード１１０Ｂ及びノード１１０Ｃの区間、並びに、ノード１１０Ｃ及びノード１１０Ｆの区間に分割する。そして、経路探索部１３７は、ノード１１０Ａ及びノード１１０Ｂの区間において、ノード１１０Ａを始点ノード、ノード１１０Ｂを終点ノードとして、ｋ本の経路候補を選択する。経路探索部１３７は、ノード１１０Ｂ及びノード１１０Ｃの区間、並びに、ノード１１０Ｃ及びノード１１０Ｆの区間でも同様にして、ｋ本の経路候補を選択する。
なお、区間毎にｋ本の経路候補を探索することにより、最終的に出力されるｋ本の経路候補が、合計コストが低い順に、最終的なｋ本の経路候補を選択することができる。
【００５２】
その後、経路探索部１３７は、区間毎に選択された経路候補を組合せて（Ｓ１４）、この組み合わせにおいてノード１１０が重複していないかどうかをチェックする（Ｓ１５）。
ノードが重複していなかった場合（Ｓ１５でＮｏ）は、その組み合わせを予備候補として追加する（Ｓ１６）。
ステップＳ１４からＳ１６の処理は、区間毎に選択された経路候補の全組み合わせパターンに対して行われ、その後、処理はステップＳ１７に進む。
【００５３】
ここで、図１６は、ノード１１０の重複の判断例を示す概略図である。図１６に示されているように、ノード１１０Ａ、ノード１１０Ｄ、ノード１１０Ｅ及びノード１１０Ｆの組み合わせは、同じノード１１０を複数回経由していないため、重複なしと判断される。一方、ノード１１０Ａ、ノード１１０Ｄ、ノード１１０Ａ、ノード１１０Ｂ、ノード１１０Ｃ及びノード１１０Ｆの組み合わせは、ノード１１０Ａが複数回（ここでは、２回）経由しているため、重複有りと判断される。
【００５４】
そして、図１５のステップＳ１７では、経路探索部１３７は、予備候補から合計コストの低いｋ本の経路を経路候補として選択し、最終的な出力とする。
【００５５】
以上により、実施の形態２における経路探索装置１３０は、多重リンクを含んだネットワークシステム１００に対して、経由ノードが複数指定されていても、複数の経路候補をコストの低い経路から昇順に高速に探索することができる。
【００５６】
なお、ステップＳ１４にてすべてのパターンを組み合わせても、ノード１１０に重複のない経路を探索できなかった場合、経路探索部１３７は、探索を強制終了するようにしてもよい。このとき、経路探索部１３７は、図２に示されている経路探索結果出力部１３４に経路重複のない経路を発見できなかったことを通知するメッセージを出力させ、経路探索条件の再入力を促す画面を表示させてもよい。
【００５７】
以下、実施の形態２における動作の具体例を説明する。
まず、実施の形態２では、図１７に示されている経路探索条件２０３が入力されたものとする。経路探索条件２０３では、経由ノードとしてノード１１０Ｄが指定されている。
【００５８】
実施の形態２における情報処理部１３６は、入力された経路探索条件２０３に基づいて、トポロジ情報を更新する。
そして、経路探索部１３７は、入力された経路探索条件及び更新されたトポロジ情報に基づいて、経路候補を選択する。
【００５９】
まず、経路探索部１３７は、経路探索条件で経由ノードとしてノード１１０Ｄが指定されているため、ノード１１０Ａ及びノード１１０Ｄの区間、並びに、ノード１１０Ｄ及びノード１１０Ｆの区間で、それぞれ実施の形態１と同じ手順によってｋ本の経路候補を選択する。
ノード１１０Ａ及びノード１１０Ｄの区間における経路候補は、例えば、図１８に示されているように選択され、ノード１１０Ｄ及びノード１１０Ｆの区間における経路候補は、例えば、図１９に示されているように選択される。
【００６０】
次に、経路探索部１３７は、それぞれの区間で選択された経路候補を組み合わせて、始点ノード及び終点ノードの経路を生成し、重複するノード１１０を含む経路を除外して、予備候補を特定する。ここでの予備候補は、図２０に示されているようになる。
【００６１】
最後に、経路探索部１３７は、合計コストの低い経路から順にｋ（ここでは、２）本の経路を経路候補として選択する。図２０に示されている例では、上位２本のＮｏ.１及びＮｏ.２の経路が経路候補として選択される。
【００６２】
実施の形態３．
実施の形態３は、実施の形態１及び２の機能に加えて、冗長経路探索を実施する機能を備える。実施の形態３は、実施の形態１又は２で選択された経路候補で使用されているノード１１０又はリンク１２０をトポロジから削除し、さらに最短経路を選択することにより、経路候補とノード１１０が重複しない冗長経路（以下、ノード冗長経路）、又は、経路候補とリンク１２０が重複しない冗長経路（以下、リンク冗長経路）を選択することができる。冗長経路探索の有無は経路探索条件にて選択することができ、冗長経路は、各経路候補につき１本ずつ探索される。
なお、実施の形態３におけるネットワークシステム１００の構成は、実施の形態１におけるネットワークシステム１００と同様である。また、実施の形態３における経路探索装置１３０の構成も、実施の形態１における経路探索装置１３０と同様である。
【００６３】
実施の形態３において、リンク冗長経路を選択する場合には、経路探索部１３７は、経路候補に含まれているリンク１２０をトポロジ情報から削除することで冗長経路用トポロジ情報を生成する。そして、経路探索部１３７は、隣接するノード１１０の間を多重接続している複数のリンク１２０の内、コストの最も低い一つのリンク１２０が残るように、冗長経路用トポロジ情報を更新する。さらに、経路探索部１３７は、更新された冗長経路用トポロジ情報に基づいて、始点ノードから終点ノードに至るまでの経路の内、通過するリンク１２０の合計コストが最も低い経路を冗長経路候補として探索する。
【００６４】
実施の形態３において、リンク冗長経路を選択する場合には、経路探索部１３７は、経路候補に含まれているノードに接続されている全てのリンク１２０を前記トポロジ情報から削除することで冗長経路用トポロジ情報を生成する。そして、経路探索部１３７は、隣接するノード１１０の間を多重接続している複数のリンク１２０の内、コストの最も低い一つのリンク１２０が残るように、冗長経路用トポロジ情報を更新する。さらに、経路探索部１３７は、更新された冗長経路用トポロジ情報に基づいて、始点ノードから終点ノードに至るまでの経路の内、通過するリンク１２０の合計コストが最も低い経路を冗長経路候補として探索する。
【００６５】
図２１及び図２２は、実施の形態３における経路探索処理を示すフローチャートである。
実施の形態３における経路探索処理は、冗長経路探索が有効になっている場合の経路探索処理である。
【００６６】
まず、経路探索装置１３０は、図２１のステップＳ１０〜Ｓ１７において、実施の形態１又は実施の形態２と同様の手順により、経路候補をｋ本（経路導出数）選択し、その後、処理は、図２２のステップＳ１８に進む。なお、図２１に示されているフローチャートのステップＳ１０〜Ｓ１７の処理は、図１５に示されているフローチャートのステップＳ１０〜Ｓ１７の処理と同様である。但し、図２１に示されているフローチャートでは、ステップＳ１７の処理の後、処理は図２２のステップＳ１８に進む。
【００６７】
図２２のステップＳ１８では、経路探索部１３７は、記憶部１３９に記憶されている経路探索条件情報を参照することにより、リンク冗長経路を探索するか否かを判断する。リンク冗長経路を探索する場合（Ｓ１８でＹｅｓ）には、処理はステップＳ１９に進む。リンク冗長経路を探索しない場合（Ｓ１８でＮｏ）には、処理はステップＳ２３に進む。
【００６８】
ステップＳ１９では、経路探索部１３７は、全ての経路候補に対して、ステップＳ２０〜ステップＳ２２で示されるリンク冗長経路の算出を行うまで、処理を繰り返す。
まず、ステップＳ２０では、経路探索部１３７は、一つの経路候補で使用されているリンク１２０をトポロジ情報から削除する。そして、経路探索部１３７は、実施の形態１に示されている手順を経路導出数ｋ＝１で実施することにより、リンク冗長経路を探索する（Ｓ２１）。その後、次の冗長経路探索に備え、ステップＳ２０で更新したトポロジ情報を元の状態に復元する（Ｓ２２）。
全ての経路候補に対して、ステップＳ２０〜ステップＳ２２で示される処理が行われた場合には、処理はステップＳ２８に進む。
【００６９】
一方、ステップＳ２３では、経路探索部１３７は、記憶部１３９に記憶されている経路探索条件情報を参照することにより、ノード冗長経路を探索するか否かを判断する。ノードリンク冗長経路を探索する場合（Ｓ２３でＹｅｓ）には、処理はステップＳ２４に進む。リンク冗長経路を探索しない場合（Ｓ２３でＮｏ）には、処理は終了する。
【００７０】
ステップＳ２４では、経路探索部１３７は、全ての経路候補に対して、ステップＳ２５〜ステップＳ２７で示されるノード冗長経路の算出を行うまで、処理を繰り返す。
まず、ステップＳ２５では、経路探索部１３７は、一つの経路候補で使用されているノード１１０に接続されている全てのリンク１２０をトポロジ情報から削除する。そして、経路探索部１３７は、実施の形態１に示されている手順を経路導出数ｋ＝１で実施することにより、ノード冗長経路を探索する（Ｓ２６）。その後、次の冗長経路探索に備え、ステップＳ２５で更新したトポロジ情報を元の状態に復元する（Ｓ２２）。
全ての経路候補に対して、ステップＳ２５〜ステップＳ２７で示される処理が行われた場合には、処理はステップＳ２８に進む。
【００７１】
ステップＳ２８では、経路探索部１３７は、ｋ本の冗長経路が算出できたかどうかを判定する。ｋ本の冗長経路が算出できた場合（Ｓ２８でＹｅｓ）には、処理は終了する。一方、ｋ本の冗長経路が算出できなかった場合（Ｓ２８でＮｏ）には、処理はステップＳ２９に進む。
【００７２】
ステップＳ２９では、経路探索部１３７は、経路探索回数が予め定められた上限に達したか否かを判断する。経路探索回数が予め定められた上限に達した場合（Ｓ２９でＹｅｓ）には、処理は終了する。この場合、経路探索部１３７は、予め装置内に設定されている経路探索回数の上限に達してもｋ本の冗長経路が算出できなかったため、計算を終了して、冗長経路の算出に成功した経路候補のみを計算結果として表示すればよい。
一方、経路探索回数が予め定められた上限に達していない場合（Ｓ２９でＮｏ）には、経路探索部１３７は、処理はステップＳ３０に進む。
【００７３】
ステップＳ３０では、経路探索部１３７は、冗長経路を算出することのできなかった経路候補を、選択の対象外として、図２１のステップＳ１１の処理に戻り、以降の処理を繰り返す。
なお、冗長経路が１本も算出できなかった場合、経路探索部１３７は、経路探索結果出力部１３４に冗長経路が１本も算出できなかったことを通知するメッセージを出力し、経路探索条件の再入力を促す画面を表示してもよい。
また、トポロジ情報からリンク１２０を削除したことにより、冗長経路が探索できなかった場合は、経路探索部１３７は、経路候補のみを探索結果として出力してもよい。
【００７４】
以上の手順により、多重リンクを含んだネットワークにおいて、各経路候補に対するノード冗長経路もしくはリンク冗長経路を合計コストの低い経路から昇順に複数探索することができる。
【００７５】
以下、実施の形態３における動作の具体例を説明する。
まず、図１に示されているネットワークシステム１００において、実施の形態１又は実施の形態２の手順により、経路探索条件をもとにトポロジ情報を生成及び更新し、経路候補を選択する。ここでは、本動作例では、図２３に示されている経路探索条件により、図２４に示されている経路候補が選択されたものとする。
【００７６】
次に、経路探索部１３７は、図２４に示されている各経路候補Ｎｏ.１及びＮｏ.２に対応する冗長経路を算出する。
まず、経路探索部１３７は、トポロジ情報から経路候補Ｎｏ．１で使用されているリンク１２０を削除し、低コストリンクを再選択すると、このトポロジ情報で示されるネットワークシステムは、図２５に示されているネットワークシステム３００−１となる。図２５では、経路候補Ｎｏ．１で使用されているリンク１２０＃２、リンク１２０＃３及びリンク１２０＃８は、破線で示されている。なお、ここでは、ノード１１０間にリンク１２０が残っていない場合、低コストリンクを再選択する必要はないものとする。
図２５に示されているネットワークシステム３００−１において、ノード１１０Ａからノード１１０Ｆまでの最短路を探索すると、図２６に示されているように、経路候補Ｎｏ．１に対してリンク冗長経路Ｎｏ．１が算出できる。
【００７７】
同様の手順で、経路探索部１３７は、トポロジ情報から経路候補Ｎｏ.２で使用されているリンク１２０を削除し、低コストリンクを再選択すると、このトポロジ情報で示されるネットワークシステムは、図２７に示されているネットワークシステム３００−２となる。図２７でも、経路候補Ｎｏ．２で使用されているリンク１２０＃１、リンク１２０＃３及びリンク１２０＃８は、破線で示されている。
図２７に示されているネットワークシステム３００−２において、ノード１１０Ａからノード１１０Ｆまでの最短路を探索すると、図２６に示されているように、経路候補Ｎｏ．２に対してリンク冗長経路Ｎｏ．２が探索できる。
【００７８】
そして、経路探索部１３７は、選択された経路候補を示す経路情報を生成して、経路探索結果出力部１３４に出力（表示）させる。ここで、実施の形態３においては、経路探索結果出力部１３４には、例えば、図２８に示されているような表示画面ＩＭ２が表示される。表示画面ＩＭ２では、経路候補がパス種別「Ｗｏｒｋｉｎｇ」で示されており、冗長経路がパス種別「Ｐｒｏｔｅｃｔｉｏｎ」で示されている。
なお、表示画面ＩＭ２では、運用パスの合計コストが昇順となるように表示されているが、例えば、運用パスと予備パスの合計コストの和が昇順となるようにソートされて表示されてもよい。
【符号の説明】
【００７９】
１００  ネットワークシステム、  １１０  ノード、  １２０  リンク、  １３０  経路探索装置、  １３１  入出力部、  １３２  情報入力部、  １３３  経路探索条件入力部、  １３４  経路探索結果出力部、  １３５  処理部、  １３６  情報処理部、  １３７  経路探索部、  １３８  通信部、  １３９  記憶部、  １５１  メモリ、  １５２  プロセッサ、  １５３  処理回路。
【図１】
0006587518.tif 000002
【図２】
0006587518.tif 000003
【図３】
0006587518.tif 000004
【図４】
0006587518.tif 000005
【図５】
0006587518.tif 000006
【図６】
0006587518.tif 000007
【図７】
0006587518.tif 000008
【図８】
0006587518.tif 000009
【図９】
0006587518.tif 000010
【図１０】
0006587518.tif 000011
【図１１】
0006587518.tif 000012
【図１２】
0006587518.tif 000013
【図１３】
0006587518.tif 000014
【図１４】
0006587518.tif 000015
【図１５】
0006587518.tif 000016
【図１６】
0006587518.tif 000017
【図１７】
0006587518.tif 000018
【図１８】
0006587518.tif 000019
【図１９】
0006587518.tif 000020
【図２０】
0006587518.tif 000021
【図２１】
0006587518.tif 000022
【図２２】
0006587518.tif 000023
【図２３】
0006587518.tif 000024
【図２４】
0006587518.tif 000025
【図２５】
0006587518.tif 000026
【図２６】
0006587518.tif 000027
【図２７】
0006587518.tif 000028
【図２８】
0006587518.tif 000029