経路探索装置、経路探索方法及び経路探索プログラム
【課題】ポート間の接続に制限のあるノードを含むネットワーク上で終点から始点へ向かうリンクを含む冗長経路を探索する。
【解決手段】経路探索装置は、第一経路探索部、トポロジ情報変更部、ポート情報変更部、第二経路探索部及び冗長経路探索部を備える。第一経路探索部は、トポロジ情報を用いて、始点ノードから終点ノードへ至る複数の経路から第一経路を探索する。トポロジ情報変更部は、第一経路を構成する構成リンクに対して当該構成リンクと方向が反対である追加リンクを設定することにより、トポロジ情報を変更する。ポート情報変更部は、ポート間の接続に制限を含む制限ノードが第一経路に含まれる場合に、ポート情報を変更する。第二経路探索部は、変更されたトポロジ情報及びポート情報を用いて、複数の経路から第二経路を探索する。冗長経路探索部は、第一経路と第二経路とで重複する構成リンクを削除することにより、一対の冗長経路を探索する。
【解決手段】経路探索装置は、第一経路探索部、トポロジ情報変更部、ポート情報変更部、第二経路探索部及び冗長経路探索部を備える。第一経路探索部は、トポロジ情報を用いて、始点ノードから終点ノードへ至る複数の経路から第一経路を探索する。トポロジ情報変更部は、第一経路を構成する構成リンクに対して当該構成リンクと方向が反対である追加リンクを設定することにより、トポロジ情報を変更する。ポート情報変更部は、ポート間の接続に制限を含む制限ノードが第一経路に含まれる場合に、ポート情報を変更する。第二経路探索部は、変更されたトポロジ情報及びポート情報を用いて、複数の経路から第二経路を探索する。冗長経路探索部は、第一経路と第二経路とで重複する構成リンクを削除することにより、一対の冗長経路を探索する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索装置、経路探索方法及び経路探索プログラムに関する。
【背景技術】
【０００２】
近年、ネットワークの信頼性を高めるために、ネットワーク上でノード障害やリンク障害が発生した場合に障害箇所を迂回するための経路である冗長経路を探索する経路探索方式が種々検討されている。このような経路探索方式として、例えば、ネットワーク上で始点ノードから終点ノード至る複数の経路から互いに重複しない一対の冗長経路を探索する経路探索方式が提案されている。
【０００３】
また、近年のネットワークには、ポート間の接続に制限を含むノード（以下「制限ノード」という）を含むものがある。このような制限ノードを含んだネットワーク上で一対の冗長経路を探索する経路探索方式が実行された場合には、本来通信が制限される部位を含む経路が、冗長経路として探索される可能性がある。そのため、制限ノードにおけるポート間の接続制限に反する経路を冗長経路の候補から除外する経路探索方式が提案されている。
【０００４】
このような経路探索方式では、経路探索装置は、ネットワークにおけるノード間の接続状態を示すトポロジ情報を用いて、始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索する。そして、経路探索装置は、第一経路を複数の経路から除外することにより、トポロジ情報を変更する。そして、経路探索装置は、第一経路上にポート間の接続に制限を含む制限ノードが含まれる場合に、制限ノードにおけるポート間の接続の制限を示すポート情報を、制限に反する経路が一対の冗長経路として探索されないように変更する。そして、経路探索装置は、変更されたトポロジ情報と変更されたポート情報とを用いて第一経路と異なる第二経路を探索する。そして、経路探索装置は、第一経路と第二経路とで重複するリンクを削除することにより互いに重複しない一対の冗長経路を探索する。これにより、ネットワークに制限ノードが含まれる場合であっても、制限ノードにおけるポート間の接続制限に反する冗長経路が誤って探索されることを回避することが可能となる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１１−４１０１７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、制限ノードにおけるポート間の接続制限に反する経路を冗長経路の候補から除外する従来の経路探索方式では、ネットワーク上で終点から始点へ向かうリンクを含む冗長経路を適切に探索することができない恐れがあるという問題がある。
【０００７】
具体的には、従来の経路探索方式では、第一経路を構成するリンクの方向を終点ノードから始点ノードへ向かう方向に変更することにより、第一経路を複数の経路から除外する。そのため、従来の経路探索方式では、冗長経路を探索する際に第一経路と第二経路とで重複するリンクが削除されると、終点ノードから始点ノードへ向かう方向に変更されたリンクが、第一経路を構成する構成リンクによって相殺されて消滅する。つまり、従来の経路探索方式では、終点ノードから始点ノードへ向かう方向のリンクが消滅するので、制限ノードを含むネットワーク上で終点から始点へ向かうリンクを含む経路を冗長経路として適切に探索することができない恐れがある。
【０００８】
開示の技術は、上記に鑑みてなされたものであって、ポート間の接続に制限のあるノードを含むネットワーク上で終点から始点へ向かうリンクを含む冗長経路を探索することができる経路探索装置、経路探索方法及び経路探索プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本願の開示する経路探索装置は、第一経路探索部と、トポロジ情報変更部と、ポート情報変更部と、第二経路探索部と、冗長経路探索部とを備える。第一経路探索部は、複数のノードがリンクで接続されたネットワークにおけるノード間の接続状態を示すトポロジ情報を用いて、前記ネットワーク上で始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索する。トポロジ情報変更部は、前記第一経路を前記複数の経路から除外するとともに、前記第一経路を構成する構成リンクに対して当該構成リンクと方向が反対である追加リンクを設定することにより、前記トポロジ情報を変更する。ポート情報変更部は、ポート間の接続に制限を含む制限ノードが前記第一経路に含まれる場合に、前記構成リンク及び前記追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、前記制限ノードにおけるポート間の接続の制限を示すポート情報を変更する。第二経路探索部は、前記変更されたトポロジ情報と前記変更されたポート情報とを用いて、前記複数の経路から前記第一経路と異なる第二経路を探索する。冗長経路探索部は、前記第一経路と前記第二経路とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する。
【発明の効果】
【００１０】
本願の開示する経路探索装置の一つの態様によれば、ポート間の接続に制限のあるノードを含むネットワーク上で終点から始点へ向かうリンクを含む冗長経路を探索することができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】図１は、本実施例に係る経路探索装置による経路探索方法について説明するための図である。
【図２】図２は、本実施例に係る経路探索装置の構成を示すブロック図である。
【図３】図３は、トポロジ情報記憶部の一例を示す図である。
【図４】図４は、第一経路情報記憶部の一例を示す図である。
【図５】図５は、ポート情報記憶部の一例を示す図である。
【図６】図６は、第二経路情報記憶部の一例を示す図である。
【図７】図７は、冗長経路情報記憶部の一例を示す図である。
【図８Ａ】図８Ａは、第一経路上に制限ノードが含まれる場合のトポロジ情報変更部による処理を説明するための図である。
【図８Ｂ】図８Ｂは、第一経路上に通常ノードが含まれる場合のトポロジ情報変更部による処理を説明するための図である。
【図９】図９は、トポロジ情報変更部によって変更されたトポロジ情報の一例を示す図である。
【図１０Ａ】図１０Ａは、ポート情報変更部による処理を説明するための図である。
【図１０Ｂ】図１０Ｂは、ポート情報変更部による処理を説明するための図である。
【図１０Ｃ】図１０Ｃは、ポート情報変更部による処理を説明するための図である。
【図１１】図１１は、ポート情報変更部によって変更されたポート情報の一例を示す図である。
【図１２】図１２は、本実施例に係る経路探索装置による経路探索処理の処理手順を示すフローチャートである。
【図１３Ａ】図１３Ａは、トポロジ情報変更部による処理のその他の例を説明するための図である。
【図１３Ｂ】図１３Ｂは、トポロジ情報変更部による処理のその他の例を説明するための図である。
【図１４】図１４は、本実施例に係る経路探索装置を構成するコンピュータのハードウェア構成を示す図である。
【発明を実施するための形態】
【００１２】
以下に、本願の開示する経路探索装置、経路探索方法及び経路探索プログラムを図面に基づいて詳細に説明する。
【実施例】
【００１３】
まず、本実施例に係る経路探索装置による経路探索方法について説明する。図１は、本実施例に係る経路探索装置による経路探索方法について説明するための図である。図１に示すネットワークは、複数のノード１１〜１７を含む。複数のノード１１〜１７は、互いにリンクで接続されている。リンク近傍に記された数字は、当該リンクの理論的な距離を表すコストである。例えば、ノード１４とノード１６とを接続するリンクのコストは、「３」である。
【００１４】
また、複数のノード１１〜１７のうちノード１１は、始点となるノードであり始点ノードと呼ばれる。ノード１５は、終点となるノードであり終点ノードと呼ばれる。また、ノード１２及びノード１３は、ポートＰ１〜Ｐ３間の接続に制限を含むノードであり制限ノードと呼ばれる。ここでは、制限ノード１２を介してノード１３と始点ノード１１又はノード１７との通信は許可され、制限ノード１２を介してノード１１とノード１７との通信は制限されているものとする。また、制限ノード１３を介してノード１２と始点ノード１１又はノード１４との通信は許可され、制限ノード１３を介して始点ノード１１とノード１４との通信は制限されているものとする。
【００１５】
まず、経路探索装置は、ネットワークにおけるノード間の接続状態を示すトポロジ情報を用いて、ネットワーク上で始点ノード１１から終点ノード１５へ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索する（図１の（１）参照）。図１の例では、経路探索装置は、トポロジ情報を用いて、リンクのコストの総和が最小の「６」となる経路を第一経路ＳＰ１として探索する。このようにして探索された第一経路ＳＰ１は、「始点ノード１１→ノード１２→ノード１３→ノード１４→終点ノード１５」により構成される。
【００１６】
続いて、経路探索装置は、第一経路ＳＰ１を複数の経路から除外するとともに、第一経路ＳＰ１を構成する構成リンクに対して当該構成リンクと方向が反対である追加リンクを設定することにより、トポロジ情報を変更する（図１の（２）参照）。図１の例では、経路探索装置は、第一経路ＳＰ１を構成する構成リンクの方向を反転するとともに、構成リンクのコストの正負を逆転して、第一経路ＳＰ１を複数の経路から除外する。そして、経路探索装置は、第一経路ＳＰ１に含まれる制限ノード１２、制限ノード１３及びノード１４を、それぞれサブノード１２ａ、１２ｂ、サブノード１３ａ、１３ｂ及びサブノード１４ａ〜１４ｃに分割する。そして、経路探索装置は、第一経路ＳＰ１を構成する構成リンクの方向を逆転して、第一経路ＳＰ１を構成する構成リンクに対して追加リンクを設定する。
【００１７】
続いて、経路探索装置は、構成リンク及び追加リンクにて終点ノード１５から始点ノード１１へ向かう通信が許可されるように、制限ノード１２、１３におけるポートＰ１〜Ｐ３の接続の制限を示すポート情報を変更する（図１の（２）参照）。図１の例では、経路探索装置は、制限ノード１２ａにおいて、始点側ノード１１と終点側ノード１３ａとを結ぶポートＰ１〜Ｐ２間の接続については構成リンクに沿って終点側ノード１３ａから始点側ノード１１へ向かう方向の通信を許可することにより、ポート情報を変更する。また、経路探索装置は、制限ノード１３ａまたは制限ノード１３ｂにおいて、始点側ノード１２ａと終点側ノード１４ａとを結ぶポートＰ１〜Ｐ２間の接続については構成リンクに沿って終点側ノード１４ａから始点側ノード１２ａへ向かう方向の通信を許可することにより、ポート情報を変更する。また、経路探索装置は、制限ノード１３ａまたは制限ノード１３ｂにおいて、始点側ノード１２ｂと終点側ノード１４ｃとを結ぶポートＰ１〜Ｐ２間の接続については追加リンクに沿って終点側ノード１４ｃから始点側ノード１２ｂへ向かう方向の通信を許可することにより、ポート情報を変更する。また、経路探索装置は、制限ノード１３ａまたは制限ノード１３ｂにおいて、 終点側ノード１４ｃと始点側ノード１２ａとを結ぶポートＰ１〜Ｐ２間の接続については構成リンクに沿って終点側ノード１４ｃから始点側ノード１２ａへ向かう方向の通信を許可することにより、ポート情報を変更する。また、経路探索装置は、制限ノード１３ａまたは制限ノード１３ｂにおいて、終点側ノード１４ａと始点側ノード１２ｂとを結ぶポートＰ１〜Ｐ２間の接続については追加リンクに沿って終点側ノード１４ａから始点側ノード１２ｂへ向かう方向の通信を許可することにより、ポート情報を変更する。
【００１８】
また、経路探索装置は、制限ノード１２ａにおいて、終点側ノード１３ａまたは１３ｂと経路外ノード１７とを結ぶポートＰ２〜Ｐ３間の接続については構成リンクに沿って経路外ノード１７から終点側ノード１３ａまたは１３ｂへ向かう方向の通信を許可することにより、ポート情報を変更する。さらに、経路探索装置は、制限ノード１２ｂにおいて、終点側ノード１３ａまたは１３ｂと経路外ノード１７とを結ぶポートＰ２〜Ｐ３間の接続については追加リンクに沿って終点側ノード１３ａまたは１３ｂから経路外ノード１７へ向かう方向の通信を許可することにより、ポート情報を変更する。
【００１９】
また、経路探索装置は、制限ノード１３ａにおいて、始点側ノード１２ａと経路外ノード１１とを結ぶポートＰ１〜Ｐ３間の接続については構成リンクに沿って始点側ノード１２ａから経路外ノード１１へ向かう方向の通信を許可することにより、ポート情報を変更する。さらに、経路探索装置は、制限ノード１３ｂにおいて、始点側ノード１２ｂと経路外ノード１１とを結ぶポートＰ１〜Ｐ３間の接続については追加リンクに沿って経路外ノード１１から始点側ノード１２ａへ向かう方向の通信を許可することにより、ポート情報を変更する。
【００２０】
なお、始点側ノードとは、第一経路にて制限ノードよりも始点ノード側に存在するノード、又は、始点ノードである。また、終点側ノードとは、第一経路にて制限ノードよりも終点ノード側に存在するノード、又は、終点ノードである。また、経路外ノードとは、第一経路に含まれないノード、又は、第一経路に含まれるノードのうち制限ノードと隣接しないノードである。
【００２１】
続いて、経路探索装置は、変更されたトポロジ情報と変更されたポート情報とを用いて、複数の経路から第一経路ＳＰ１と異なる第二経路ＳＰ２を探索する（図１の（３）及び（４）参照）。図１の例では、経路探索装置は、変更されたトポロジ情報及びポート情報を用いて、リンクのコストの総和が最小の「８」となる経路を第二経路ＳＰ２として探索する。このようにして探索された第二経路ＳＰ２は、「始点ノード１１→ノード１６→ノード１４→制限ノード１３→制限ノード１２→始点ノード１１→制限ノード１３→制限ノード１２→ノード１７→終点ノード１５」により構成される。
【００２２】
続いて、経路探索装置は、第一経路ＳＰ１と第二経路ＳＰ２とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する（図１の（５）参照）。図１の例では、経路探索装置は、第一経路ＳＰ１と第二経路ＳＰ２とで重複する構成リンクとして、制限ノード１２と制限ノード１３とを接続するリンクを削除することにより、互いに重複しない一対の冗長経路Ｐａｔｈ１、Ｐａｔｈ２を探索する。このようにして探索された冗長経路Ｐａｔｈ１は、「始点ノード１１→ノード１６→ノード１４→終点ノード１５」により構成される。また、冗長経路Ｐａｔｈ２は、「始点ノード１１→制限ノード１３→制限ノード１２→ノード１７→終点ノード１５」により構成される。
【００２３】
ここで、冗長経路Ｐａｔｈ１及びＰａｔｈ２のうち冗長経路Ｐａｔｈ２は、制限ノード１２、１３を含むが、制限ノード１２、１３におけるポートＰ１〜Ｐ３の接続制限を満足するため、適正な冗長経路である。さらに、冗長経路Ｐａｔｈ２は、第一経路ＳＰ１上で終点ノード１５から始点ノード１１へ向かうリンクとして、制限ノード１３と制限ノード１２とを接続するリンクを含んでいる。
【００２４】
このように、本実施例の経路探索装置は、第一経路を複数の経路から除外するとともに、第一経路を構成する構成リンクに対して構成リンクと反対方向の追加リンクを設定することにより、トポロジ情報を変更する。そして、経路探索装置は、構成リンク及び追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、制限ノードのポート情報を変更する。そして、経路探索装置は、変更されたトポロジ情報及びポート情報を用いて複数の経路から第一経路と異なる第二経路を探索する。
【００２５】
そのため、本実施例の経路探索装置は、第一経路及び第二経路から一対の冗長経路を探索する際に、第一経路と第二経路とで重複する構成リンクを削除しても、第一経路上で終点ノードから始点ノードへ向かうリンクを残存させることができる。すなわち、本実施例の経路探索装置は、ポート間の接続に制限のあるノードを含むネットワーク上で第一経路上の終点から始点へ向かうリンクを含む冗長経路を適切に探索することができる。
【００２６】
次に、図２を用いて、本実施例に係る経路探索装置の構成を説明する。図２は、本実施例に係る経路探索装置１００の構成を示すブロック図である。図２に示すように、経路探索装置１００は、記憶部１１０及び制御部１２０を有する。
【００２７】
記憶部１１０は、制御部１２０による各種の処理に必要なデータや、制御部１２０による各種の処理の結果を記憶する。具体的には、記憶部１１０は、トポロジ情報記憶部１１１、第一経路情報記憶部１１２、ポート情報記憶部１１３、第二経路情報記憶部１１４及び冗長経路情報記憶部１１５を有する。
【００２８】
トポロジ情報記憶部１１１は、複数のノードがリンクで接続されたネットワークにおけるノード間の接続状態を示すトポロジ情報を記憶する。トポロジ情報記憶部１１１は、経路探索装置１００のユーザにより入力された情報や通信インターフェースにより各ノードから収集された情報をトポロジ情報として記憶する。トポロジ情報記憶部１１１の一例を図３に示す。図３に示すトポロジ情報記憶部１１１は、リンクＩＤ（IDentifier）、ノード１、ノード２、コスト及び方向といった項目を対応付けて記憶する。
【００２９】
リンクＩＤは、ネットワークを構成するノード間を接続するリンクを識別するための識別情報である。ノード１は、リンクの一端に接続される一方のノードの識別情報である。ノード２は、リンクの他端に接続される他方のノードの識別情報である。コストは、リンクの理論的な距離であるコストである。方向は、リンクの通信の方向であり、ノード１からノード２へ向かう方向及びノード２からノード１へ向かう方向の通信が許可されている場合に「０」となる。また、方向は、ノード１からノード２へ向かう方向の通信が許可されている場合に「１」となり、ノード２からノード１へ向かう方向の通信が許可されている場合に「２」となる。
【００３０】
第一経路情報記憶部１１２は、ネットワーク上で始点ノードから終点ノードへ至る複数の経路から探索された第一経路に関する情報を第一経路情報として記憶する。第一経路情報記憶部１１２によって記憶される第一経路情報は、後述する第一経路探索部１２１によって作成されて格納される。第一経路情報記憶部１１２の一例を図４に示す。図４に示す第一経路情報記憶部１１２は、第一経路ＩＤ、構成ノード及びコスト総和といった項目を対応付けて記憶する。
【００３１】
第一経路ＩＤは、第一経路を識別するための識別情報である。構成ノードは、第一経路を構成するノードの識別情報である。例えば、「Ｎ１→Ｎ２→Ｎ３→Ｎ４→Ｎ５」は、ノードＮ１を始点ノードとし、ノードＮ２、Ｎ３及びＮ４を経由して、ノードＮ５を終点ノードとする第一経路ＳＰ１を構成するノードを表している。コスト総和は、第一経路に含まれるリンクのコストの総和である。
【００３２】
ポート情報記憶部１１３は、制限ノードにおけるポート間の接続の制限を示す情報をポート情報として記憶する。ポート情報記憶部１１３は、経路探索装置１００のユーザによって入力された情報や通信インターフェースにより各ノードから収集された情報をポート情報として記憶する。ポート情報記憶部１１３の一例を図５に示す。図５に示すポート情報記憶部１１３は、制限ノードＩＤ、ポート間接続、ノード１、ノード２及び接続状態といった項目を対応付けて記憶する。
【００３３】
制限ノードＩＤは、制限ノードを識別するための識別情報である。ポート間接続は、制限ノードが有するポートのうち任意の一対のポートどうしの接続を示し、例えば「Ｐ１−Ｐ２」は、ポートＰ１とポートＰ２との接続を表している。ノード１は、ポート間接続における一対のポートのうち一方のポートに接続されるノードである。ノード２は、ポート間接続における一対のポートのうち他方のポートに接続されるノードである。接続状態は、ポート間接続の接続状態を示し、ノード１からノード２へ向かう方向及びノード２からノード１へ向かう方向の通信が許可されている場合に「０」となる。また、接続状態は、ノード１からノード２へ向かう方向の通信が許可されている場合に「１」となり、ノード２からノード１へ向かう方向の通信が許可されている場合に「２」となり、ノード１とノード２との間の通信が制限されている場合に「３」となる。
【００３４】
第二経路情報記憶部１１４は、ネットワーク上で始点ノードから終点ノードへ至る複数の経路から探索された第二経路に関する情報を第二経路情報として記憶する。第二経路情報記憶部１１４によって記憶される第二経路情報は、後述する第二経路探索部１２４によって作成されて格納される。第二経路情報記憶部１１４の一例を図６に示す。図６に示す第二経路情報記憶部１１４は、第二経路ＩＤ、構成ノード及びコスト総和といった項目を対応付けて記憶する。
【００３５】
第二経路ＩＤは、第二経路を識別するための識別情報である。構成ノードは、第二経路を構成するノードの識別情報である。例えば、「Ｎ１→Ｎ６→Ｎ４→Ｎ３→Ｎ２→Ｎ１→Ｎ３→Ｎ２→Ｎ７→Ｎ５」は、ノードＮ１を始点ノードとし、ノードＮ６、Ｎ４、Ｎ３、Ｎ２、Ｎ１、Ｎ３、Ｎ２及びＮ７を経由して、ノードＮ５を終点ノードとする第二経路ＳＰ２を構成するノードを表している。コスト総和は、第二経路に含まれるリンクのコストの総和である。
【００３６】
冗長経路情報記憶部１１５は、ネットワーク上で始点ノードから終点ノードへ至る複数の経路から探索された、互いに重複しない一対の冗長経路に関する情報を冗長経路情報として記憶する。冗長経路情報記憶部１１５によって記憶される冗長経路情報は、後述する冗長経路探索部１２５によって作成されて格納される。冗長経路情報記憶部１１５の一例を図７に示す。図７に示す冗長経路情報記憶部１１５は、冗長経路ＩＤ、構成ノード及びコスト総和といった項目を対応付けて記憶する。
【００３７】
冗長経路ＩＤは、冗長経路を識別するための識別情報である。構成ノードは、冗長経路を構成するノードの識別情報である。例えば、「Ｎ１→Ｎ６→Ｎ４→Ｎ５」は、ノードＮ１を始点ノードとし、ノードＮ６及びＮ４を経由して、ノードＮ５を終点ノードとする冗長経路Ｐａｔｈ１を構成するノードを表している。コスト総和は、冗長経路に含まれるリンクのコストの総和である。
【００３８】
制御部１２０は、各種の処理手順などを規定したプログラム及び所要データを格納するための内部メモリを有し、これらによって種々の処理を実行する。具体的には、制御部１２０は、第一経路探索部１２１、トポロジ情報変更部１２２、ポート情報変更部１２３、第二経路探索部１２４、冗長経路探索部１２５及び出力部１２６を有する。
【００３９】
第一経路探索部１２１は、トポロジ情報を用いて、ネットワーク上で始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索する。具体的には、第一経路探索部１２１は、トポロジ情報記憶部１１１からトポロジ情報を読み出す。そして、第一経路探索部１２１は、読み出したトポロジ情報に、Ｄｉｊｋｓｔｒａ法等に代表されるグラフ上の経路探索アルゴリズムを適用することにより、複数の経路からリンクのコストの総和が最小となる第一経路を探索する。また、第一経路探索部１２１は、探索した第一経路に関する情報を第一経路情報として第一経路情報記憶部１１２に格納する。
【００４０】
トポロジ情報変更部１２２は、探索された第一経路をネットワーク上の複数の経路から除外するとともに、第一経路を構成する構成リンクに対して構成リンクと方向が反対である追加リンクを設定することにより、トポロジ情報を変更する。具体的には、トポロジ情報変更部１２２は、探索された第一経路（例えば、第一経路ＩＤ「ＳＰ１」）の構成ノード（例えば、構成ノード「Ｎ１→Ｎ２→Ｎ３→Ｎ４→Ｎ５」）を第一経路情報記憶部１１２から読み出す。そして、トポロジ情報変更部１２２は、トポロジ情報記憶部１１１を参照し、読み出された構成ノード間を接続するリンク、すなわち、第一経路を構成する構成リンクの方向を反転するとともに、構成リンクのコストの正負を逆転する。これにより、第一経路がネットワーク上の複数の経路から除外される。そして、トポロジ情報変更部１２２は、トポロジ情報記憶部１１１を参照し、第一経路に含まれるノードを複数のサブノードに分割する。そして、トポロジ情報変更部１２２は、第一経路を構成する構成リンクの方向を反転する。これにより、第一経路を構成する構成リンクに対して追加リンクが設定される。
【００４１】
ここで、トポロジ情報変更部１２２がトポロジ情報を変更する手法について具体的に説明する。まず、図８Ａを用いて、第一経路上に制限ノードが含まれる場合のトポロジ情報変更部１２２による処理について説明する。図８Ａは、第一経路上に制限ノードが含まれる場合のトポロジ情報変更部１２２による処理について説明するための図である。
【００４２】
図８Ａに示すように、トポロジ情報変更部１２２は、第一経路を構成する構成リンクの方向を反転するとともに、構成リンクのコスト「ｃ」及び「ｄ」の正負を逆転する。これにより、第一経路がネットワーク上の複数の経路から除外される。そして、トポロジ情報変更部１２２は、第一経路に含まれる制限ノードを２つのサブノードに分割する。そして、トポロジ情報変更部１２２は、第一経路を構成する構成リンクの方向を反転する。これにより、第一経路を構成する構成リンクに対して追加リンクが設定される。
【００４３】
次いで、図８Ｂを用いて、第一経路上に通常ノードが含まれる場合のトポロジ情報変更部１２２による処理について説明する。図８Ｂは、第一経路上に通常ノードが含まれる場合のトポロジ情報変更部による処理について説明するための図である。なお、以下では、制限ノード以外のノードのことを通常ノードと言うことがあるものとする。
【００４４】
図８Ｂに示すように、トポロジ情報変更部１２２は、第一経路を構成する構成リンクの方向を反転するとともに、構成リンクのコスト「ｃ」及び「ｄ」の正負を逆転する。これにより、第一経路がネットワーク上の複数の経路から除外される。そして、トポロジ情報変更部１２２は、第一経路に含まれる通常ノードを４つのサブノードに分割する。そして、トポロジ情報変更部１２２は、第一経路を構成する構成リンクの方向を反転する。これにより、第一経路を構成する構成リンクに対して追加リンクが設定される。
【００４５】
具体的な一例を挙げて説明すると、トポロジ情報変更部１２２は、図３に示したトポロジ情報記憶部１１１に記憶されたトポロジ情報を、図９の右側に示すトポロジ情報に変更する。すなわち、トポロジ情報変更部１２２は、第一経路を構成する構成リンク（例えば、リンクＩＤ「Ｌ１」、「Ｌ２ａ」、「Ｌ２ｂ」、「Ｌ３ａ」、「Ｌ３ｂ」、「Ｌ４」）の方向を反転するとともに、構成リンクのコストの正負を逆転する。これにより、第一経路がネットワーク上の複数の経路から除外される。そして、トポロジ情報変更部１２２は、第一経路に含まれる制限ノード（例えば、ノード「Ｎ２」、「Ｎ３」）をそれぞれ２つのサブノード（例えば、ノード「Ｎ２ａ」、「Ｎ２ｂ」及びノード「Ｎ３ａ」、「Ｎ３ｂ」）に分割する。また、トポロジ情報変更部１２２は、第一経路に含まれる通常ノード（例えば、ノード「Ｎ４」）を３つのサブノード（例えば、ノード「Ｎ４ａ」、「Ｎ４ｂ」、「Ｎ４ｃ」）に分割する。そして、トポロジ情報変更部１２２は、第一経路を構成する構成リンク（例えば、リンクＩＤ「Ｌ２ｃ」、「Ｌ２ｄ」、「Ｌ３ｃ」、「Ｌ３ｄ」）の方向を反転する。これにより、第一経路を構成する構成リンク対して追加リンクが設定される。なお、図９は、トポロジ情報変更部１２２によって変更されたトポロジ情報の一例を示す図である。
【００４６】
図２に戻って、ポート情報変更部１２３は、制限ノードが第一経路に含まれる場合に、第一経路を構成する構成リンク及び構成リンクに設定された追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、ポート情報を変更する。具体的には、ポート情報変更部１２３は、探索された第一経路（例えば、第一経路ＩＤ「ＳＰ１」）の構成ノード（例えば、構成ノード「Ｎ１→Ｎ２→Ｎ３→Ｎ４→Ｎ５」）を第一経路情報記憶部１１２から読み出す。
【００４７】
そして、ポート情報変更部１２３は、ポート情報記憶部１１３を参照し、読み出された構成ノード（例えば、構成ノード「Ｎ１→Ｎ２→Ｎ３→Ｎ４→Ｎ５」）に、制限ノードＩＤ（例えば、「Ｎ２」、「Ｎ３」）に対応する制限ノードが含まれるか否かを判定する。その結果、ポート情報変更部１２３は、制限ノードが含まれる場合に、ポート情報変更部１２３に記憶されたポート情報を変更する。
【００４８】
ここで、図１０Ａ〜図１０Ｃを用いて、ポート情報変更部１２３がポート情報を変更する手法について説明する。図１０Ａ〜図１０Ｃは、ポート情報変更部１２３による処理を説明するための図である。
【００４９】
ポート情報変更部１２３は、始点側ノードと終点側ノードとを結ぶポート間の接続については、図１０Ａに示すように、構成リンク及び追加リンクに沿って終点側ノードから始点側ノードへ向かう方向の通信を許可することにより、ポート情報を変更する。ここで、第二経路がサブノードに生成された接続を使用する場合、制限ノード内の終点側ノードから始点側ノードへの接続も使用しなければならない。すなわち、第二経路は追加リンクを使用する場合、構成リンクも使用しなければならない。
【００５０】
また、ポート情報変更部１２３は、始点側ノードと経路外ノードとを結ぶポート間の接続については、図１０Ｂに示すように、構成リンクに沿って始点側ノードから経路外ノードへ向かう方向の通信を許可することにより、ポート情報を変更する。さらに、ポート情報変更部１２３は、追加リンクに沿って経路外ノードから始点側ノードへ向かう方向の通信を許可することにより、ポート情報を変更する。ここで、第二経路がサブノードあるいは制限ノード内の経路外ノードと始点側ノード間の接続を使用する場合、制限ノード内の終点側ノードから始点側ノードへの接続も使用しなければならない。すなわち、第二経路が追加リンクを使用する場合は対応する構成リンクも使用せねばならず、また第二経路が制限ノードと経路外ノードとの間のリンクを使用する場合、直前のノードは第一経路上の終点側隣接ノード（サブノードを含む）でなければならない。
【００５１】
また、ポート情報変更部１２３は、終点側ノードと経路外ノードとを結ぶポート間の接続については、図１０Ｃに示すように、構成リンクに沿って経路外ノードから終点側ノードへ向かう方向の通信を許可することにより、ポート情報を変更する。さらに、ポート情報変更部１２３は、追加リンクに沿って終点側ノードから経路外ノードへ向かう方向の通信を許可することにより、ポート情報を変更する。ここで、第二経路がサブノードあるいは制限ノード内の経路外ノードと終点側ノード間の接続を使用する場合、制限ノード内の終点側ノードから始点側ノードへの接続も使用しなければならない。すなわち、第二経路が追加リンクを使用する場合は対応する構成リンクも使用せねばならず、また第二経路が制限ノードと経路外ノードとの間のリンクを使用する場合、直後のノードは第一経路上の始点側隣接ノード（サブノードを含む）でなければならない。
【００５２】
具体的な一例を挙げて説明すると、ポート情報変更部１２３は、図５に示したポート情報記憶部１１３に記憶されたポート情報のうち接続状態を、図１１の下側に示すポート情報に変更する。つまり、ポート情報変更部１２３は、始点側ノード（ノード１「Ｎ１」）と終点側ノード（ノード２「Ｎ３ａ」）とを結ぶポート間の接続（ポート間接続「Ｐ１−Ｐ２」）に対応する接続状態を、構成リンクに沿って終点側ノード→始点側ノードを示す「２」とする。また、ポート情報変更部１２３は、始点側ノード（ノード１「Ｎ２ａ」）と終点側ノード（ノード２「Ｎ４ａ」）とを結ぶポート間の接続（ポート間接続「Ｐ１−Ｐ２」）に対応する接続状態を、構成リンクに沿って終点側ノード→始点側ノードを示す「２」とする。また、ポート情報変更部１２３は、始点側ノード（ノード１「Ｎ２ｂ」）と終点側ノード（ノード２「Ｎ４ｃ」）とを結ぶポート間の接続（ポート間接続「Ｐ１−Ｐ２」）に対応する接続状態を、追加リンクに沿って終点側ノード→始点側ノードを示す「２」とする。
【００５３】
また、ポート情報変更部１２３は、終点側ノード（ノード１「Ｎ３ａ」）と経路外ノード（ノード２「Ｎ７」）とを結ぶポート間の接続（ポート間接続「Ｐ２−Ｐ３」）に対応する接続状態を、構成リンクに沿って経路外ノード→終点側ノードを示す「２」とする。さらに、ポート情報変更部１２３は、終点側ノード（ノード１「Ｎ３ｂ」）と経路外ノード（ノード２「Ｎ７」）とを結ぶポート間の接続（ポート間接続「Ｐ２−Ｐ３」）に対応する接続状態を、追加リンクに沿って終点側ノード→経路外ノードを示す「１」とする。
【００５４】
また、ポート情報変更部１２３は、経路外ノード（ノード１「Ｎ１」）と始点側ノード（ノード２「Ｎ２ａ」）とを結ぶポート間の接続（ポート間接続「Ｐ１−Ｐ３」）に対応する接続状態を、構成リンクに沿って始点側ノード→経路外ノードを示す「２」とする。さらに、ポート情報変更部１２３は、経路外ノード（ノード１「Ｎ１」）と始点側ノード（ノード２「Ｎ２ｂ」）とを結ぶポート間の接続（ポート間接続「Ｐ１−Ｐ３」）に対応する接続状態を、追加リンクに沿って経路外ノード→始点側ノードを示す「１」とする。なお、図１１は、ポート情報変更部によって変更されたポート情報の一例を示す図である。
【００５５】
図２に戻って、第二経路探索部１２４は、トポロジ情報変更部１２２によって変更されたトポロジ情報とポート情報変更部１２３によって変更されたポート情報とを用いて、ネットワーク上で始点ノードから終点ノードへ至る複数の経路から第二経路を探索する。具体的には、第二経路探索部１２４は、トポロジ情報変更部１２２によって変更されたトポロジ情報をトポロジ情報記憶部１１１から読み出す。そして、第二経路探索部１２４は、ポート情報変更部１２３によって変更されたポート情報をポート情報記憶部１１３から読み出す。
【００５６】
そして、第二経路探索部１２４は、読み出されたトポロジ情報及びポート情報にＤｉｊｋｓｔｒａ法等に代表されるグラフ上の経路探索アルゴリズムを適用することにより、複数の経路からリンクのコストの総和が最小となる第二経路を探索する。また、第二経路探索部１２４は、探索した第二経路に関する情報を第二経路情報として第二経路情報記憶部１１４に格納する。
【００５７】
冗長経路探索部１２５は、第一経路と第二経路とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する。具体的には、冗長経路探索部１２５は、第一経路の構成ノードを第一経路情報記憶部１１２から読み出す。そして、冗長経路探索部１２５は、第二経路の構成ノードを第二経路情報記憶部１１４から読み出す。そして、冗長経路探索部１２５は、読み出した第一経路の構成ノードと第二経路の構成ノードとを対比し、第一経路と第二経路とで重複する構成リンクを特定する。そして、冗長経路探索部１２５は、特定した構成リンクを、第一経路の構成ノード及び第二経路の構成ノードから削除して残りの部分を連結する。これにより、互いに重複しない一対の冗長経路が探索される。
【００５８】
ここで、図４及び図６に示した例を用いて、冗長経路探索部１２５による処理を説明する。冗長経路探索部１２５は、第一経路ＩＤ「ＳＰ１」の構成ノード「Ｎ１→Ｎ２→Ｎ３→Ｎ４→Ｎ５」を第一経路情報記憶部１１２から読み出す。そして、冗長経路探索部１２５は、第二経路ＩＤ「ＳＰ２」の構成ノード「Ｎ１→Ｎ６→Ｎ４→Ｎ３→Ｎ２→Ｎ１→Ｎ３→Ｎ２→Ｎ７→Ｎ５」を第二経路情報記憶部１１４から読み出す。そして、冗長経路探索部１２５は、読み出した第一経路の構成ノードと第二経路の構成ノードとを対比し、第一経路と第二経路とで重複する構成リンクとして、ノード「Ｎ２」〜ノード「Ｎ３」間の構成リンクを特定する。そして、冗長経路探索部１２５は、特定したノード「Ｎ２」〜ノード「Ｎ３」間の構成リンクを削除して残りの部分を連結する。これにより、互いに重複しない一対の冗長経路が探索される。そして、冗長経路探索部１２５は、探索した一対の冗長経路に関する情報を冗長経路情報として冗長経路情報記憶部１１５に格納する。
【００５９】
出力部１２６は、冗長経路情報記憶部１１５に記憶された冗長経路情報を処理結果としてディスプレイ等の表示部に出力する。
【００６０】
なお、上述した制御部１２０の第一経路探索部１２１、トポロジ情報変更部１２２、ポート情報変更部１２３、第二経路探索部１２４、冗長経路探索部１２５及び出力部１２６は、例えば、集積回路又は電子回路である。集積回路は、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）等である。電子回路は、例えば、ＣＰＵ（Central Processing Unit）やＭＰＵ（Micro Processing Unit）等である。
【００６１】
また、上述した記憶部１１０のトポロジ情報記憶部１１１、第一経路情報記憶部１１２、ポート情報記憶部１１３、第二経路情報記憶部１１４及び冗長経路情報記憶部１１５は、例えば、半導体メモリ素子又は記憶装置である。半導体メモリ素子は、例えば、ＲＡＭ（Random Access Memory)、ＲＯＭ（Read Only Memory)、フラッシュメモリ（Flash Memory）等である。記憶装置は、例えば、ＨＤＤ（Hard Disc Drive）、光ディスク等である。
【００６２】
次に、図１２を用いて、本実施例に係る経路探索装置１００による経路探索処理の処理手順について説明する。図１２は、本実施例に係る経路探索装置１００による経路探索処理の処理手順を示すフローチャートである。
【００６３】
図１２に示すように、第一経路情報記憶部１１２は、トポロジ情報を用いて、始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索する（ステップＳ１０１）。
【００６４】
そして、トポロジ情報変更部１２２は、第一経路を複数の経路から除外するとともに、第一経路を構成する構成リンクに対して構成リンクと方向が反対である追加リンクを設定することにより、トポロジ情報を変更する（ステップＳ１０２）。
【００６５】
そして、ポート情報変更部１２３は、構成リンク及び追加リンクにて終点ノードから始点ノードへ向かう方向の通信が許可されるように、制限ノードにおけるポートの接続の制限を示すポート情報を変更する（ステップＳ１０３）。そして、第二経路探索部１２４は、変更されたトポロジ情報と変更されたポート情報とを用いて、複数の経路から第一経路と異なる第二経路を探索する（ステップＳ１０４）。
【００６６】
そして、冗長経路探索部１２５は、探索された第一経路と第二経路とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する（ステップＳ１０５）。そして、冗長経路探索部１２５は、探索した一対の冗長経路に関する情報を冗長経路情報として冗長経路情報記憶部１１５に格納する。そして、出力部１２６は、冗長経路情報記憶部１１５に記憶された冗長経路情報を表示出力する（ステップＳ１０６）。
【００６７】
上述してきたように、本実施例の経路探索装置１００は、第一経路を複数の経路から除外するとともに、第一経路を構成する構成リンクに対して構成リンクと反対方向の追加リンクを設定することにより、トポロジ情報を変更する。そして、経路探索装置１００は、構成リンク及び追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、制限ノードのポート情報を変更する。そして、経路探索装置１００は、変更されたトポロジ情報及びポート情報を用いて複数の経路から第一経路と異なる第二経路を探索する。
【００６８】
そのため、本実施例の経路探索装置１００は、第一経路及び第二経路から一対の冗長経路を探索する際に、第一経路と第二経路とで重複する構成リンクを削除しても、終点ノードから始点ノードへ向かう追加リンクを残存させることができる。すなわち、本実施例の経路探索装置１００は、ポート間の接続に制限のあるノードを含むネットワーク上で終点から始点へ向かうリンクを含む冗長経路を適切に探索することができる。
【００６９】
ところで、上記実施例では、ポート情報変更部１２３が、制限ノードが第一経路に含まれる場合に、構成リンク及び追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、ポート情報を変更する例を説明した。しかしながら、制限ノードが第一経路に含まれる場合に、構成リンク及び追加リンクにて終点ノードから始点ノードへ向かう通信を許可する手法はこれに限定されるものではない。例えば、制限ノードが第一経路に含まれる場合に、トポロジ情報変更部１２２が、構成リンク及び追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、トポロジ情報を変更してもよい。
【００７０】
以下では、図１３Ａ及び図１３Ｂを用いて、トポロジ情報変更部１２２による処理のその他の例を説明する。図１３Ａ及び図１３Ｂは、トポロジ情報変更部１２２による処理のその他の例を説明するための図である。
【００７１】
トポロジ情報変更部１２２は、制限ノードが第一経路に含まれる場合に、以下に説明するようにトポロジ情報を変更する。すなわち、トポロジ情報変更部１２２は、始点側ノードと経路外ノードとを結ぶポート間の接続については、図１３Ａに示すように、構成リンクに沿って始点側ノードから経路外ノードへ向かうリンクを新たに生成することにより、トポロジ情報を変更する。さらに、トポロジ情報変更部１２２は、追加リンクに沿って経路外ノードから始点側ノードへ向かうリンクを新たに生成することにより、トポロジ情報を変更する。
【００７２】
また、トポロジ情報変更部１２２は、終点側ノードと経路外ノードとを結ぶポート間の接続については、図１３Ｂに示すように、構成リンクに沿って経路外ノードから終点側ノードへ向かうリンクを新たに生成することにより、トポロジ情報を変更する。さらに、トポロジ情報変更部１２２は、追加リンクに沿って終点側ノードから経路外ノードへ向かうリンクを新たに生成することにより、トポロジ情報を変更する。
【００７３】
なお、経路探索装置１００は、上記の実施例で説明した各種の処理は、あらかじめ用意されたプログラムをコンピュータで実行することによって実現することができる。そこで、以下では、上記の実施例と同様の機能を有するプログラムを実行するコンピュータについて説明する。
【００７４】
図１４は、本実施例に係る経路探索装置を構成するコンピュータのハードウェア構成を示す図である。図１４に示すように、コンピュータ２００は、ＲＡＭ２１０と、ＨＤＤ２２０と、ＣＰＵ２３０と、ＲＯＭ２４０とを有する。各装置２１０〜２４０は、バス２５０に接続される。
【００７５】
そして、ＲＯＭ２４０には、上記の実施例と同様の機能を発揮するプログラムがあらかじめ記憶されている。つまり、ＲＯＭ２４０には、第一経路探索プログラム２４１、トポロジ情報変更プログラム２４２、ポート情報変更プログラム２４３、第二経路探索プログラム２４４、冗長経路探索プログラム２４５及び出力プログラム２４６があらかじめ記憶されている。
【００７６】
そして、ＣＰＵ２３０が、プログラム２４１〜２４４を読み出して実行することで、第一経路探索プロセス２３１、トポロジ情報変更プロセス２３２、ポート情報変更プロセス２３３及び第二経路探索プロセス２３４として機能するようになる。また、ＣＰＵ２３０が、プログラム２４５及び２４６を読み出して実行することで、冗長経路探索プロセス２３５及び出力プロセス２３６として機能するようになる。なお、各プロセス２３１〜２３６は、図２に示した第一経路探索部１２１、トポロジ情報変更部１２２、ポート情報変更部１２３、第二経路探索部１２４、冗長経路探索部１２５及び出力部１２６にそれぞれ対応する。
【００７７】
また、ＨＤＤ２２０には、トポロジテーブル２２１、第一経路テーブル２２２、ポートテーブル２２３、第二経路テーブル２２４及び冗長経路テーブル２２５が設けられる。なお、各テーブル２２１〜２２５は、図２に示したトポロジ情報記憶部１１１、第一経路情報記憶部１１２、ポート情報記憶部１１３、第二経路情報記憶部１１４及び冗長経路情報記憶部１１５にそれぞれ対応する。
【００７８】
なお、上記のプログラム２４１〜２４６は、必ずしもＲＯＭ２４０に記憶させておく必要はなく、ＣＤ−ＲＯＭ等の記憶媒体に記憶されたプログラムを、コンピュータ２００が読み出して実行するようにしてもよい。また、公衆回線、インターネット、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等にこれらプログラムを記憶させておき、コンピュータ２００がこれらからプログラムを読み出して実行するようにしてもよい。
【符号の説明】
【００７９】
１００ 経路探索装置
１１０ 記憶部
１１１ トポロジ情報記憶部
１１２ 第一経路情報記憶部
１１３ ポート情報記憶部
１１４ 第二経路情報記憶部
１１５ 冗長経路情報記憶部
１２０ 制御部
１２１ 第一経路探索部
１２２ トポロジ情報変更部
１２３ ポート情報変更部
１２４ 第二経路探索部
１２５ 冗長経路探索部
１２６ 出力部
【技術分野】
【０００１】
本発明は、経路探索装置、経路探索方法及び経路探索プログラムに関する。
【背景技術】
【０００２】
近年、ネットワークの信頼性を高めるために、ネットワーク上でノード障害やリンク障害が発生した場合に障害箇所を迂回するための経路である冗長経路を探索する経路探索方式が種々検討されている。このような経路探索方式として、例えば、ネットワーク上で始点ノードから終点ノード至る複数の経路から互いに重複しない一対の冗長経路を探索する経路探索方式が提案されている。
【０００３】
また、近年のネットワークには、ポート間の接続に制限を含むノード（以下「制限ノード」という）を含むものがある。このような制限ノードを含んだネットワーク上で一対の冗長経路を探索する経路探索方式が実行された場合には、本来通信が制限される部位を含む経路が、冗長経路として探索される可能性がある。そのため、制限ノードにおけるポート間の接続制限に反する経路を冗長経路の候補から除外する経路探索方式が提案されている。
【０００４】
このような経路探索方式では、経路探索装置は、ネットワークにおけるノード間の接続状態を示すトポロジ情報を用いて、始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索する。そして、経路探索装置は、第一経路を複数の経路から除外することにより、トポロジ情報を変更する。そして、経路探索装置は、第一経路上にポート間の接続に制限を含む制限ノードが含まれる場合に、制限ノードにおけるポート間の接続の制限を示すポート情報を、制限に反する経路が一対の冗長経路として探索されないように変更する。そして、経路探索装置は、変更されたトポロジ情報と変更されたポート情報とを用いて第一経路と異なる第二経路を探索する。そして、経路探索装置は、第一経路と第二経路とで重複するリンクを削除することにより互いに重複しない一対の冗長経路を探索する。これにより、ネットワークに制限ノードが含まれる場合であっても、制限ノードにおけるポート間の接続制限に反する冗長経路が誤って探索されることを回避することが可能となる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１１−４１０１７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、制限ノードにおけるポート間の接続制限に反する経路を冗長経路の候補から除外する従来の経路探索方式では、ネットワーク上で終点から始点へ向かうリンクを含む冗長経路を適切に探索することができない恐れがあるという問題がある。
【０００７】
具体的には、従来の経路探索方式では、第一経路を構成するリンクの方向を終点ノードから始点ノードへ向かう方向に変更することにより、第一経路を複数の経路から除外する。そのため、従来の経路探索方式では、冗長経路を探索する際に第一経路と第二経路とで重複するリンクが削除されると、終点ノードから始点ノードへ向かう方向に変更されたリンクが、第一経路を構成する構成リンクによって相殺されて消滅する。つまり、従来の経路探索方式では、終点ノードから始点ノードへ向かう方向のリンクが消滅するので、制限ノードを含むネットワーク上で終点から始点へ向かうリンクを含む経路を冗長経路として適切に探索することができない恐れがある。
【０００８】
開示の技術は、上記に鑑みてなされたものであって、ポート間の接続に制限のあるノードを含むネットワーク上で終点から始点へ向かうリンクを含む冗長経路を探索することができる経路探索装置、経路探索方法及び経路探索プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
本願の開示する経路探索装置は、第一経路探索部と、トポロジ情報変更部と、ポート情報変更部と、第二経路探索部と、冗長経路探索部とを備える。第一経路探索部は、複数のノードがリンクで接続されたネットワークにおけるノード間の接続状態を示すトポロジ情報を用いて、前記ネットワーク上で始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索する。トポロジ情報変更部は、前記第一経路を前記複数の経路から除外するとともに、前記第一経路を構成する構成リンクに対して当該構成リンクと方向が反対である追加リンクを設定することにより、前記トポロジ情報を変更する。ポート情報変更部は、ポート間の接続に制限を含む制限ノードが前記第一経路に含まれる場合に、前記構成リンク及び前記追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、前記制限ノードにおけるポート間の接続の制限を示すポート情報を変更する。第二経路探索部は、前記変更されたトポロジ情報と前記変更されたポート情報とを用いて、前記複数の経路から前記第一経路と異なる第二経路を探索する。冗長経路探索部は、前記第一経路と前記第二経路とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する。
【発明の効果】
【００１０】
本願の開示する経路探索装置の一つの態様によれば、ポート間の接続に制限のあるノードを含むネットワーク上で終点から始点へ向かうリンクを含む冗長経路を探索することができるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】図１は、本実施例に係る経路探索装置による経路探索方法について説明するための図である。
【図２】図２は、本実施例に係る経路探索装置の構成を示すブロック図である。
【図３】図３は、トポロジ情報記憶部の一例を示す図である。
【図４】図４は、第一経路情報記憶部の一例を示す図である。
【図５】図５は、ポート情報記憶部の一例を示す図である。
【図６】図６は、第二経路情報記憶部の一例を示す図である。
【図７】図７は、冗長経路情報記憶部の一例を示す図である。
【図８Ａ】図８Ａは、第一経路上に制限ノードが含まれる場合のトポロジ情報変更部による処理を説明するための図である。
【図８Ｂ】図８Ｂは、第一経路上に通常ノードが含まれる場合のトポロジ情報変更部による処理を説明するための図である。
【図９】図９は、トポロジ情報変更部によって変更されたトポロジ情報の一例を示す図である。
【図１０Ａ】図１０Ａは、ポート情報変更部による処理を説明するための図である。
【図１０Ｂ】図１０Ｂは、ポート情報変更部による処理を説明するための図である。
【図１０Ｃ】図１０Ｃは、ポート情報変更部による処理を説明するための図である。
【図１１】図１１は、ポート情報変更部によって変更されたポート情報の一例を示す図である。
【図１２】図１２は、本実施例に係る経路探索装置による経路探索処理の処理手順を示すフローチャートである。
【図１３Ａ】図１３Ａは、トポロジ情報変更部による処理のその他の例を説明するための図である。
【図１３Ｂ】図１３Ｂは、トポロジ情報変更部による処理のその他の例を説明するための図である。
【図１４】図１４は、本実施例に係る経路探索装置を構成するコンピュータのハードウェア構成を示す図である。
【発明を実施するための形態】
【００１２】
以下に、本願の開示する経路探索装置、経路探索方法及び経路探索プログラムを図面に基づいて詳細に説明する。
【実施例】
【００１３】
まず、本実施例に係る経路探索装置による経路探索方法について説明する。図１は、本実施例に係る経路探索装置による経路探索方法について説明するための図である。図１に示すネットワークは、複数のノード１１〜１７を含む。複数のノード１１〜１７は、互いにリンクで接続されている。リンク近傍に記された数字は、当該リンクの理論的な距離を表すコストである。例えば、ノード１４とノード１６とを接続するリンクのコストは、「３」である。
【００１４】
また、複数のノード１１〜１７のうちノード１１は、始点となるノードであり始点ノードと呼ばれる。ノード１５は、終点となるノードであり終点ノードと呼ばれる。また、ノード１２及びノード１３は、ポートＰ１〜Ｐ３間の接続に制限を含むノードであり制限ノードと呼ばれる。ここでは、制限ノード１２を介してノード１３と始点ノード１１又はノード１７との通信は許可され、制限ノード１２を介してノード１１とノード１７との通信は制限されているものとする。また、制限ノード１３を介してノード１２と始点ノード１１又はノード１４との通信は許可され、制限ノード１３を介して始点ノード１１とノード１４との通信は制限されているものとする。
【００１５】
まず、経路探索装置は、ネットワークにおけるノード間の接続状態を示すトポロジ情報を用いて、ネットワーク上で始点ノード１１から終点ノード１５へ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索する（図１の（１）参照）。図１の例では、経路探索装置は、トポロジ情報を用いて、リンクのコストの総和が最小の「６」となる経路を第一経路ＳＰ１として探索する。このようにして探索された第一経路ＳＰ１は、「始点ノード１１→ノード１２→ノード１３→ノード１４→終点ノード１５」により構成される。
【００１６】
続いて、経路探索装置は、第一経路ＳＰ１を複数の経路から除外するとともに、第一経路ＳＰ１を構成する構成リンクに対して当該構成リンクと方向が反対である追加リンクを設定することにより、トポロジ情報を変更する（図１の（２）参照）。図１の例では、経路探索装置は、第一経路ＳＰ１を構成する構成リンクの方向を反転するとともに、構成リンクのコストの正負を逆転して、第一経路ＳＰ１を複数の経路から除外する。そして、経路探索装置は、第一経路ＳＰ１に含まれる制限ノード１２、制限ノード１３及びノード１４を、それぞれサブノード１２ａ、１２ｂ、サブノード１３ａ、１３ｂ及びサブノード１４ａ〜１４ｃに分割する。そして、経路探索装置は、第一経路ＳＰ１を構成する構成リンクの方向を逆転して、第一経路ＳＰ１を構成する構成リンクに対して追加リンクを設定する。
【００１７】
続いて、経路探索装置は、構成リンク及び追加リンクにて終点ノード１５から始点ノード１１へ向かう通信が許可されるように、制限ノード１２、１３におけるポートＰ１〜Ｐ３の接続の制限を示すポート情報を変更する（図１の（２）参照）。図１の例では、経路探索装置は、制限ノード１２ａにおいて、始点側ノード１１と終点側ノード１３ａとを結ぶポートＰ１〜Ｐ２間の接続については構成リンクに沿って終点側ノード１３ａから始点側ノード１１へ向かう方向の通信を許可することにより、ポート情報を変更する。また、経路探索装置は、制限ノード１３ａまたは制限ノード１３ｂにおいて、始点側ノード１２ａと終点側ノード１４ａとを結ぶポートＰ１〜Ｐ２間の接続については構成リンクに沿って終点側ノード１４ａから始点側ノード１２ａへ向かう方向の通信を許可することにより、ポート情報を変更する。また、経路探索装置は、制限ノード１３ａまたは制限ノード１３ｂにおいて、始点側ノード１２ｂと終点側ノード１４ｃとを結ぶポートＰ１〜Ｐ２間の接続については追加リンクに沿って終点側ノード１４ｃから始点側ノード１２ｂへ向かう方向の通信を許可することにより、ポート情報を変更する。また、経路探索装置は、制限ノード１３ａまたは制限ノード１３ｂにおいて、 終点側ノード１４ｃと始点側ノード１２ａとを結ぶポートＰ１〜Ｐ２間の接続については構成リンクに沿って終点側ノード１４ｃから始点側ノード１２ａへ向かう方向の通信を許可することにより、ポート情報を変更する。また、経路探索装置は、制限ノード１３ａまたは制限ノード１３ｂにおいて、終点側ノード１４ａと始点側ノード１２ｂとを結ぶポートＰ１〜Ｐ２間の接続については追加リンクに沿って終点側ノード１４ａから始点側ノード１２ｂへ向かう方向の通信を許可することにより、ポート情報を変更する。
【００１８】
また、経路探索装置は、制限ノード１２ａにおいて、終点側ノード１３ａまたは１３ｂと経路外ノード１７とを結ぶポートＰ２〜Ｐ３間の接続については構成リンクに沿って経路外ノード１７から終点側ノード１３ａまたは１３ｂへ向かう方向の通信を許可することにより、ポート情報を変更する。さらに、経路探索装置は、制限ノード１２ｂにおいて、終点側ノード１３ａまたは１３ｂと経路外ノード１７とを結ぶポートＰ２〜Ｐ３間の接続については追加リンクに沿って終点側ノード１３ａまたは１３ｂから経路外ノード１７へ向かう方向の通信を許可することにより、ポート情報を変更する。
【００１９】
また、経路探索装置は、制限ノード１３ａにおいて、始点側ノード１２ａと経路外ノード１１とを結ぶポートＰ１〜Ｐ３間の接続については構成リンクに沿って始点側ノード１２ａから経路外ノード１１へ向かう方向の通信を許可することにより、ポート情報を変更する。さらに、経路探索装置は、制限ノード１３ｂにおいて、始点側ノード１２ｂと経路外ノード１１とを結ぶポートＰ１〜Ｐ３間の接続については追加リンクに沿って経路外ノード１１から始点側ノード１２ａへ向かう方向の通信を許可することにより、ポート情報を変更する。
【００２０】
なお、始点側ノードとは、第一経路にて制限ノードよりも始点ノード側に存在するノード、又は、始点ノードである。また、終点側ノードとは、第一経路にて制限ノードよりも終点ノード側に存在するノード、又は、終点ノードである。また、経路外ノードとは、第一経路に含まれないノード、又は、第一経路に含まれるノードのうち制限ノードと隣接しないノードである。
【００２１】
続いて、経路探索装置は、変更されたトポロジ情報と変更されたポート情報とを用いて、複数の経路から第一経路ＳＰ１と異なる第二経路ＳＰ２を探索する（図１の（３）及び（４）参照）。図１の例では、経路探索装置は、変更されたトポロジ情報及びポート情報を用いて、リンクのコストの総和が最小の「８」となる経路を第二経路ＳＰ２として探索する。このようにして探索された第二経路ＳＰ２は、「始点ノード１１→ノード１６→ノード１４→制限ノード１３→制限ノード１２→始点ノード１１→制限ノード１３→制限ノード１２→ノード１７→終点ノード１５」により構成される。
【００２２】
続いて、経路探索装置は、第一経路ＳＰ１と第二経路ＳＰ２とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する（図１の（５）参照）。図１の例では、経路探索装置は、第一経路ＳＰ１と第二経路ＳＰ２とで重複する構成リンクとして、制限ノード１２と制限ノード１３とを接続するリンクを削除することにより、互いに重複しない一対の冗長経路Ｐａｔｈ１、Ｐａｔｈ２を探索する。このようにして探索された冗長経路Ｐａｔｈ１は、「始点ノード１１→ノード１６→ノード１４→終点ノード１５」により構成される。また、冗長経路Ｐａｔｈ２は、「始点ノード１１→制限ノード１３→制限ノード１２→ノード１７→終点ノード１５」により構成される。
【００２３】
ここで、冗長経路Ｐａｔｈ１及びＰａｔｈ２のうち冗長経路Ｐａｔｈ２は、制限ノード１２、１３を含むが、制限ノード１２、１３におけるポートＰ１〜Ｐ３の接続制限を満足するため、適正な冗長経路である。さらに、冗長経路Ｐａｔｈ２は、第一経路ＳＰ１上で終点ノード１５から始点ノード１１へ向かうリンクとして、制限ノード１３と制限ノード１２とを接続するリンクを含んでいる。
【００２４】
このように、本実施例の経路探索装置は、第一経路を複数の経路から除外するとともに、第一経路を構成する構成リンクに対して構成リンクと反対方向の追加リンクを設定することにより、トポロジ情報を変更する。そして、経路探索装置は、構成リンク及び追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、制限ノードのポート情報を変更する。そして、経路探索装置は、変更されたトポロジ情報及びポート情報を用いて複数の経路から第一経路と異なる第二経路を探索する。
【００２５】
そのため、本実施例の経路探索装置は、第一経路及び第二経路から一対の冗長経路を探索する際に、第一経路と第二経路とで重複する構成リンクを削除しても、第一経路上で終点ノードから始点ノードへ向かうリンクを残存させることができる。すなわち、本実施例の経路探索装置は、ポート間の接続に制限のあるノードを含むネットワーク上で第一経路上の終点から始点へ向かうリンクを含む冗長経路を適切に探索することができる。
【００２６】
次に、図２を用いて、本実施例に係る経路探索装置の構成を説明する。図２は、本実施例に係る経路探索装置１００の構成を示すブロック図である。図２に示すように、経路探索装置１００は、記憶部１１０及び制御部１２０を有する。
【００２７】
記憶部１１０は、制御部１２０による各種の処理に必要なデータや、制御部１２０による各種の処理の結果を記憶する。具体的には、記憶部１１０は、トポロジ情報記憶部１１１、第一経路情報記憶部１１２、ポート情報記憶部１１３、第二経路情報記憶部１１４及び冗長経路情報記憶部１１５を有する。
【００２８】
トポロジ情報記憶部１１１は、複数のノードがリンクで接続されたネットワークにおけるノード間の接続状態を示すトポロジ情報を記憶する。トポロジ情報記憶部１１１は、経路探索装置１００のユーザにより入力された情報や通信インターフェースにより各ノードから収集された情報をトポロジ情報として記憶する。トポロジ情報記憶部１１１の一例を図３に示す。図３に示すトポロジ情報記憶部１１１は、リンクＩＤ（IDentifier）、ノード１、ノード２、コスト及び方向といった項目を対応付けて記憶する。
【００２９】
リンクＩＤは、ネットワークを構成するノード間を接続するリンクを識別するための識別情報である。ノード１は、リンクの一端に接続される一方のノードの識別情報である。ノード２は、リンクの他端に接続される他方のノードの識別情報である。コストは、リンクの理論的な距離であるコストである。方向は、リンクの通信の方向であり、ノード１からノード２へ向かう方向及びノード２からノード１へ向かう方向の通信が許可されている場合に「０」となる。また、方向は、ノード１からノード２へ向かう方向の通信が許可されている場合に「１」となり、ノード２からノード１へ向かう方向の通信が許可されている場合に「２」となる。
【００３０】
第一経路情報記憶部１１２は、ネットワーク上で始点ノードから終点ノードへ至る複数の経路から探索された第一経路に関する情報を第一経路情報として記憶する。第一経路情報記憶部１１２によって記憶される第一経路情報は、後述する第一経路探索部１２１によって作成されて格納される。第一経路情報記憶部１１２の一例を図４に示す。図４に示す第一経路情報記憶部１１２は、第一経路ＩＤ、構成ノード及びコスト総和といった項目を対応付けて記憶する。
【００３１】
第一経路ＩＤは、第一経路を識別するための識別情報である。構成ノードは、第一経路を構成するノードの識別情報である。例えば、「Ｎ１→Ｎ２→Ｎ３→Ｎ４→Ｎ５」は、ノードＮ１を始点ノードとし、ノードＮ２、Ｎ３及びＮ４を経由して、ノードＮ５を終点ノードとする第一経路ＳＰ１を構成するノードを表している。コスト総和は、第一経路に含まれるリンクのコストの総和である。
【００３２】
ポート情報記憶部１１３は、制限ノードにおけるポート間の接続の制限を示す情報をポート情報として記憶する。ポート情報記憶部１１３は、経路探索装置１００のユーザによって入力された情報や通信インターフェースにより各ノードから収集された情報をポート情報として記憶する。ポート情報記憶部１１３の一例を図５に示す。図５に示すポート情報記憶部１１３は、制限ノードＩＤ、ポート間接続、ノード１、ノード２及び接続状態といった項目を対応付けて記憶する。
【００３３】
制限ノードＩＤは、制限ノードを識別するための識別情報である。ポート間接続は、制限ノードが有するポートのうち任意の一対のポートどうしの接続を示し、例えば「Ｐ１−Ｐ２」は、ポートＰ１とポートＰ２との接続を表している。ノード１は、ポート間接続における一対のポートのうち一方のポートに接続されるノードである。ノード２は、ポート間接続における一対のポートのうち他方のポートに接続されるノードである。接続状態は、ポート間接続の接続状態を示し、ノード１からノード２へ向かう方向及びノード２からノード１へ向かう方向の通信が許可されている場合に「０」となる。また、接続状態は、ノード１からノード２へ向かう方向の通信が許可されている場合に「１」となり、ノード２からノード１へ向かう方向の通信が許可されている場合に「２」となり、ノード１とノード２との間の通信が制限されている場合に「３」となる。
【００３４】
第二経路情報記憶部１１４は、ネットワーク上で始点ノードから終点ノードへ至る複数の経路から探索された第二経路に関する情報を第二経路情報として記憶する。第二経路情報記憶部１１４によって記憶される第二経路情報は、後述する第二経路探索部１２４によって作成されて格納される。第二経路情報記憶部１１４の一例を図６に示す。図６に示す第二経路情報記憶部１１４は、第二経路ＩＤ、構成ノード及びコスト総和といった項目を対応付けて記憶する。
【００３５】
第二経路ＩＤは、第二経路を識別するための識別情報である。構成ノードは、第二経路を構成するノードの識別情報である。例えば、「Ｎ１→Ｎ６→Ｎ４→Ｎ３→Ｎ２→Ｎ１→Ｎ３→Ｎ２→Ｎ７→Ｎ５」は、ノードＮ１を始点ノードとし、ノードＮ６、Ｎ４、Ｎ３、Ｎ２、Ｎ１、Ｎ３、Ｎ２及びＮ７を経由して、ノードＮ５を終点ノードとする第二経路ＳＰ２を構成するノードを表している。コスト総和は、第二経路に含まれるリンクのコストの総和である。
【００３６】
冗長経路情報記憶部１１５は、ネットワーク上で始点ノードから終点ノードへ至る複数の経路から探索された、互いに重複しない一対の冗長経路に関する情報を冗長経路情報として記憶する。冗長経路情報記憶部１１５によって記憶される冗長経路情報は、後述する冗長経路探索部１２５によって作成されて格納される。冗長経路情報記憶部１１５の一例を図７に示す。図７に示す冗長経路情報記憶部１１５は、冗長経路ＩＤ、構成ノード及びコスト総和といった項目を対応付けて記憶する。
【００３７】
冗長経路ＩＤは、冗長経路を識別するための識別情報である。構成ノードは、冗長経路を構成するノードの識別情報である。例えば、「Ｎ１→Ｎ６→Ｎ４→Ｎ５」は、ノードＮ１を始点ノードとし、ノードＮ６及びＮ４を経由して、ノードＮ５を終点ノードとする冗長経路Ｐａｔｈ１を構成するノードを表している。コスト総和は、冗長経路に含まれるリンクのコストの総和である。
【００３８】
制御部１２０は、各種の処理手順などを規定したプログラム及び所要データを格納するための内部メモリを有し、これらによって種々の処理を実行する。具体的には、制御部１２０は、第一経路探索部１２１、トポロジ情報変更部１２２、ポート情報変更部１２３、第二経路探索部１２４、冗長経路探索部１２５及び出力部１２６を有する。
【００３９】
第一経路探索部１２１は、トポロジ情報を用いて、ネットワーク上で始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索する。具体的には、第一経路探索部１２１は、トポロジ情報記憶部１１１からトポロジ情報を読み出す。そして、第一経路探索部１２１は、読み出したトポロジ情報に、Ｄｉｊｋｓｔｒａ法等に代表されるグラフ上の経路探索アルゴリズムを適用することにより、複数の経路からリンクのコストの総和が最小となる第一経路を探索する。また、第一経路探索部１２１は、探索した第一経路に関する情報を第一経路情報として第一経路情報記憶部１１２に格納する。
【００４０】
トポロジ情報変更部１２２は、探索された第一経路をネットワーク上の複数の経路から除外するとともに、第一経路を構成する構成リンクに対して構成リンクと方向が反対である追加リンクを設定することにより、トポロジ情報を変更する。具体的には、トポロジ情報変更部１２２は、探索された第一経路（例えば、第一経路ＩＤ「ＳＰ１」）の構成ノード（例えば、構成ノード「Ｎ１→Ｎ２→Ｎ３→Ｎ４→Ｎ５」）を第一経路情報記憶部１１２から読み出す。そして、トポロジ情報変更部１２２は、トポロジ情報記憶部１１１を参照し、読み出された構成ノード間を接続するリンク、すなわち、第一経路を構成する構成リンクの方向を反転するとともに、構成リンクのコストの正負を逆転する。これにより、第一経路がネットワーク上の複数の経路から除外される。そして、トポロジ情報変更部１２２は、トポロジ情報記憶部１１１を参照し、第一経路に含まれるノードを複数のサブノードに分割する。そして、トポロジ情報変更部１２２は、第一経路を構成する構成リンクの方向を反転する。これにより、第一経路を構成する構成リンクに対して追加リンクが設定される。
【００４１】
ここで、トポロジ情報変更部１２２がトポロジ情報を変更する手法について具体的に説明する。まず、図８Ａを用いて、第一経路上に制限ノードが含まれる場合のトポロジ情報変更部１２２による処理について説明する。図８Ａは、第一経路上に制限ノードが含まれる場合のトポロジ情報変更部１２２による処理について説明するための図である。
【００４２】
図８Ａに示すように、トポロジ情報変更部１２２は、第一経路を構成する構成リンクの方向を反転するとともに、構成リンクのコスト「ｃ」及び「ｄ」の正負を逆転する。これにより、第一経路がネットワーク上の複数の経路から除外される。そして、トポロジ情報変更部１２２は、第一経路に含まれる制限ノードを２つのサブノードに分割する。そして、トポロジ情報変更部１２２は、第一経路を構成する構成リンクの方向を反転する。これにより、第一経路を構成する構成リンクに対して追加リンクが設定される。
【００４３】
次いで、図８Ｂを用いて、第一経路上に通常ノードが含まれる場合のトポロジ情報変更部１２２による処理について説明する。図８Ｂは、第一経路上に通常ノードが含まれる場合のトポロジ情報変更部による処理について説明するための図である。なお、以下では、制限ノード以外のノードのことを通常ノードと言うことがあるものとする。
【００４４】
図８Ｂに示すように、トポロジ情報変更部１２２は、第一経路を構成する構成リンクの方向を反転するとともに、構成リンクのコスト「ｃ」及び「ｄ」の正負を逆転する。これにより、第一経路がネットワーク上の複数の経路から除外される。そして、トポロジ情報変更部１２２は、第一経路に含まれる通常ノードを４つのサブノードに分割する。そして、トポロジ情報変更部１２２は、第一経路を構成する構成リンクの方向を反転する。これにより、第一経路を構成する構成リンクに対して追加リンクが設定される。
【００４５】
具体的な一例を挙げて説明すると、トポロジ情報変更部１２２は、図３に示したトポロジ情報記憶部１１１に記憶されたトポロジ情報を、図９の右側に示すトポロジ情報に変更する。すなわち、トポロジ情報変更部１２２は、第一経路を構成する構成リンク（例えば、リンクＩＤ「Ｌ１」、「Ｌ２ａ」、「Ｌ２ｂ」、「Ｌ３ａ」、「Ｌ３ｂ」、「Ｌ４」）の方向を反転するとともに、構成リンクのコストの正負を逆転する。これにより、第一経路がネットワーク上の複数の経路から除外される。そして、トポロジ情報変更部１２２は、第一経路に含まれる制限ノード（例えば、ノード「Ｎ２」、「Ｎ３」）をそれぞれ２つのサブノード（例えば、ノード「Ｎ２ａ」、「Ｎ２ｂ」及びノード「Ｎ３ａ」、「Ｎ３ｂ」）に分割する。また、トポロジ情報変更部１２２は、第一経路に含まれる通常ノード（例えば、ノード「Ｎ４」）を３つのサブノード（例えば、ノード「Ｎ４ａ」、「Ｎ４ｂ」、「Ｎ４ｃ」）に分割する。そして、トポロジ情報変更部１２２は、第一経路を構成する構成リンク（例えば、リンクＩＤ「Ｌ２ｃ」、「Ｌ２ｄ」、「Ｌ３ｃ」、「Ｌ３ｄ」）の方向を反転する。これにより、第一経路を構成する構成リンク対して追加リンクが設定される。なお、図９は、トポロジ情報変更部１２２によって変更されたトポロジ情報の一例を示す図である。
【００４６】
図２に戻って、ポート情報変更部１２３は、制限ノードが第一経路に含まれる場合に、第一経路を構成する構成リンク及び構成リンクに設定された追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、ポート情報を変更する。具体的には、ポート情報変更部１２３は、探索された第一経路（例えば、第一経路ＩＤ「ＳＰ１」）の構成ノード（例えば、構成ノード「Ｎ１→Ｎ２→Ｎ３→Ｎ４→Ｎ５」）を第一経路情報記憶部１１２から読み出す。
【００４７】
そして、ポート情報変更部１２３は、ポート情報記憶部１１３を参照し、読み出された構成ノード（例えば、構成ノード「Ｎ１→Ｎ２→Ｎ３→Ｎ４→Ｎ５」）に、制限ノードＩＤ（例えば、「Ｎ２」、「Ｎ３」）に対応する制限ノードが含まれるか否かを判定する。その結果、ポート情報変更部１２３は、制限ノードが含まれる場合に、ポート情報変更部１２３に記憶されたポート情報を変更する。
【００４８】
ここで、図１０Ａ〜図１０Ｃを用いて、ポート情報変更部１２３がポート情報を変更する手法について説明する。図１０Ａ〜図１０Ｃは、ポート情報変更部１２３による処理を説明するための図である。
【００４９】
ポート情報変更部１２３は、始点側ノードと終点側ノードとを結ぶポート間の接続については、図１０Ａに示すように、構成リンク及び追加リンクに沿って終点側ノードから始点側ノードへ向かう方向の通信を許可することにより、ポート情報を変更する。ここで、第二経路がサブノードに生成された接続を使用する場合、制限ノード内の終点側ノードから始点側ノードへの接続も使用しなければならない。すなわち、第二経路は追加リンクを使用する場合、構成リンクも使用しなければならない。
【００５０】
また、ポート情報変更部１２３は、始点側ノードと経路外ノードとを結ぶポート間の接続については、図１０Ｂに示すように、構成リンクに沿って始点側ノードから経路外ノードへ向かう方向の通信を許可することにより、ポート情報を変更する。さらに、ポート情報変更部１２３は、追加リンクに沿って経路外ノードから始点側ノードへ向かう方向の通信を許可することにより、ポート情報を変更する。ここで、第二経路がサブノードあるいは制限ノード内の経路外ノードと始点側ノード間の接続を使用する場合、制限ノード内の終点側ノードから始点側ノードへの接続も使用しなければならない。すなわち、第二経路が追加リンクを使用する場合は対応する構成リンクも使用せねばならず、また第二経路が制限ノードと経路外ノードとの間のリンクを使用する場合、直前のノードは第一経路上の終点側隣接ノード（サブノードを含む）でなければならない。
【００５１】
また、ポート情報変更部１２３は、終点側ノードと経路外ノードとを結ぶポート間の接続については、図１０Ｃに示すように、構成リンクに沿って経路外ノードから終点側ノードへ向かう方向の通信を許可することにより、ポート情報を変更する。さらに、ポート情報変更部１２３は、追加リンクに沿って終点側ノードから経路外ノードへ向かう方向の通信を許可することにより、ポート情報を変更する。ここで、第二経路がサブノードあるいは制限ノード内の経路外ノードと終点側ノード間の接続を使用する場合、制限ノード内の終点側ノードから始点側ノードへの接続も使用しなければならない。すなわち、第二経路が追加リンクを使用する場合は対応する構成リンクも使用せねばならず、また第二経路が制限ノードと経路外ノードとの間のリンクを使用する場合、直後のノードは第一経路上の始点側隣接ノード（サブノードを含む）でなければならない。
【００５２】
具体的な一例を挙げて説明すると、ポート情報変更部１２３は、図５に示したポート情報記憶部１１３に記憶されたポート情報のうち接続状態を、図１１の下側に示すポート情報に変更する。つまり、ポート情報変更部１２３は、始点側ノード（ノード１「Ｎ１」）と終点側ノード（ノード２「Ｎ３ａ」）とを結ぶポート間の接続（ポート間接続「Ｐ１−Ｐ２」）に対応する接続状態を、構成リンクに沿って終点側ノード→始点側ノードを示す「２」とする。また、ポート情報変更部１２３は、始点側ノード（ノード１「Ｎ２ａ」）と終点側ノード（ノード２「Ｎ４ａ」）とを結ぶポート間の接続（ポート間接続「Ｐ１−Ｐ２」）に対応する接続状態を、構成リンクに沿って終点側ノード→始点側ノードを示す「２」とする。また、ポート情報変更部１２３は、始点側ノード（ノード１「Ｎ２ｂ」）と終点側ノード（ノード２「Ｎ４ｃ」）とを結ぶポート間の接続（ポート間接続「Ｐ１−Ｐ２」）に対応する接続状態を、追加リンクに沿って終点側ノード→始点側ノードを示す「２」とする。
【００５３】
また、ポート情報変更部１２３は、終点側ノード（ノード１「Ｎ３ａ」）と経路外ノード（ノード２「Ｎ７」）とを結ぶポート間の接続（ポート間接続「Ｐ２−Ｐ３」）に対応する接続状態を、構成リンクに沿って経路外ノード→終点側ノードを示す「２」とする。さらに、ポート情報変更部１２３は、終点側ノード（ノード１「Ｎ３ｂ」）と経路外ノード（ノード２「Ｎ７」）とを結ぶポート間の接続（ポート間接続「Ｐ２−Ｐ３」）に対応する接続状態を、追加リンクに沿って終点側ノード→経路外ノードを示す「１」とする。
【００５４】
また、ポート情報変更部１２３は、経路外ノード（ノード１「Ｎ１」）と始点側ノード（ノード２「Ｎ２ａ」）とを結ぶポート間の接続（ポート間接続「Ｐ１−Ｐ３」）に対応する接続状態を、構成リンクに沿って始点側ノード→経路外ノードを示す「２」とする。さらに、ポート情報変更部１２３は、経路外ノード（ノード１「Ｎ１」）と始点側ノード（ノード２「Ｎ２ｂ」）とを結ぶポート間の接続（ポート間接続「Ｐ１−Ｐ３」）に対応する接続状態を、追加リンクに沿って経路外ノード→始点側ノードを示す「１」とする。なお、図１１は、ポート情報変更部によって変更されたポート情報の一例を示す図である。
【００５５】
図２に戻って、第二経路探索部１２４は、トポロジ情報変更部１２２によって変更されたトポロジ情報とポート情報変更部１２３によって変更されたポート情報とを用いて、ネットワーク上で始点ノードから終点ノードへ至る複数の経路から第二経路を探索する。具体的には、第二経路探索部１２４は、トポロジ情報変更部１２２によって変更されたトポロジ情報をトポロジ情報記憶部１１１から読み出す。そして、第二経路探索部１２４は、ポート情報変更部１２３によって変更されたポート情報をポート情報記憶部１１３から読み出す。
【００５６】
そして、第二経路探索部１２４は、読み出されたトポロジ情報及びポート情報にＤｉｊｋｓｔｒａ法等に代表されるグラフ上の経路探索アルゴリズムを適用することにより、複数の経路からリンクのコストの総和が最小となる第二経路を探索する。また、第二経路探索部１２４は、探索した第二経路に関する情報を第二経路情報として第二経路情報記憶部１１４に格納する。
【００５７】
冗長経路探索部１２５は、第一経路と第二経路とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する。具体的には、冗長経路探索部１２５は、第一経路の構成ノードを第一経路情報記憶部１１２から読み出す。そして、冗長経路探索部１２５は、第二経路の構成ノードを第二経路情報記憶部１１４から読み出す。そして、冗長経路探索部１２５は、読み出した第一経路の構成ノードと第二経路の構成ノードとを対比し、第一経路と第二経路とで重複する構成リンクを特定する。そして、冗長経路探索部１２５は、特定した構成リンクを、第一経路の構成ノード及び第二経路の構成ノードから削除して残りの部分を連結する。これにより、互いに重複しない一対の冗長経路が探索される。
【００５８】
ここで、図４及び図６に示した例を用いて、冗長経路探索部１２５による処理を説明する。冗長経路探索部１２５は、第一経路ＩＤ「ＳＰ１」の構成ノード「Ｎ１→Ｎ２→Ｎ３→Ｎ４→Ｎ５」を第一経路情報記憶部１１２から読み出す。そして、冗長経路探索部１２５は、第二経路ＩＤ「ＳＰ２」の構成ノード「Ｎ１→Ｎ６→Ｎ４→Ｎ３→Ｎ２→Ｎ１→Ｎ３→Ｎ２→Ｎ７→Ｎ５」を第二経路情報記憶部１１４から読み出す。そして、冗長経路探索部１２５は、読み出した第一経路の構成ノードと第二経路の構成ノードとを対比し、第一経路と第二経路とで重複する構成リンクとして、ノード「Ｎ２」〜ノード「Ｎ３」間の構成リンクを特定する。そして、冗長経路探索部１２５は、特定したノード「Ｎ２」〜ノード「Ｎ３」間の構成リンクを削除して残りの部分を連結する。これにより、互いに重複しない一対の冗長経路が探索される。そして、冗長経路探索部１２５は、探索した一対の冗長経路に関する情報を冗長経路情報として冗長経路情報記憶部１１５に格納する。
【００５９】
出力部１２６は、冗長経路情報記憶部１１５に記憶された冗長経路情報を処理結果としてディスプレイ等の表示部に出力する。
【００６０】
なお、上述した制御部１２０の第一経路探索部１２１、トポロジ情報変更部１２２、ポート情報変更部１２３、第二経路探索部１２４、冗長経路探索部１２５及び出力部１２６は、例えば、集積回路又は電子回路である。集積回路は、例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）等である。電子回路は、例えば、ＣＰＵ（Central Processing Unit）やＭＰＵ（Micro Processing Unit）等である。
【００６１】
また、上述した記憶部１１０のトポロジ情報記憶部１１１、第一経路情報記憶部１１２、ポート情報記憶部１１３、第二経路情報記憶部１１４及び冗長経路情報記憶部１１５は、例えば、半導体メモリ素子又は記憶装置である。半導体メモリ素子は、例えば、ＲＡＭ（Random Access Memory)、ＲＯＭ（Read Only Memory)、フラッシュメモリ（Flash Memory）等である。記憶装置は、例えば、ＨＤＤ（Hard Disc Drive）、光ディスク等である。
【００６２】
次に、図１２を用いて、本実施例に係る経路探索装置１００による経路探索処理の処理手順について説明する。図１２は、本実施例に係る経路探索装置１００による経路探索処理の処理手順を示すフローチャートである。
【００６３】
図１２に示すように、第一経路情報記憶部１１２は、トポロジ情報を用いて、始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索する（ステップＳ１０１）。
【００６４】
そして、トポロジ情報変更部１２２は、第一経路を複数の経路から除外するとともに、第一経路を構成する構成リンクに対して構成リンクと方向が反対である追加リンクを設定することにより、トポロジ情報を変更する（ステップＳ１０２）。
【００６５】
そして、ポート情報変更部１２３は、構成リンク及び追加リンクにて終点ノードから始点ノードへ向かう方向の通信が許可されるように、制限ノードにおけるポートの接続の制限を示すポート情報を変更する（ステップＳ１０３）。そして、第二経路探索部１２４は、変更されたトポロジ情報と変更されたポート情報とを用いて、複数の経路から第一経路と異なる第二経路を探索する（ステップＳ１０４）。
【００６６】
そして、冗長経路探索部１２５は、探索された第一経路と第二経路とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する（ステップＳ１０５）。そして、冗長経路探索部１２５は、探索した一対の冗長経路に関する情報を冗長経路情報として冗長経路情報記憶部１１５に格納する。そして、出力部１２６は、冗長経路情報記憶部１１５に記憶された冗長経路情報を表示出力する（ステップＳ１０６）。
【００６７】
上述してきたように、本実施例の経路探索装置１００は、第一経路を複数の経路から除外するとともに、第一経路を構成する構成リンクに対して構成リンクと反対方向の追加リンクを設定することにより、トポロジ情報を変更する。そして、経路探索装置１００は、構成リンク及び追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、制限ノードのポート情報を変更する。そして、経路探索装置１００は、変更されたトポロジ情報及びポート情報を用いて複数の経路から第一経路と異なる第二経路を探索する。
【００６８】
そのため、本実施例の経路探索装置１００は、第一経路及び第二経路から一対の冗長経路を探索する際に、第一経路と第二経路とで重複する構成リンクを削除しても、終点ノードから始点ノードへ向かう追加リンクを残存させることができる。すなわち、本実施例の経路探索装置１００は、ポート間の接続に制限のあるノードを含むネットワーク上で終点から始点へ向かうリンクを含む冗長経路を適切に探索することができる。
【００６９】
ところで、上記実施例では、ポート情報変更部１２３が、制限ノードが第一経路に含まれる場合に、構成リンク及び追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、ポート情報を変更する例を説明した。しかしながら、制限ノードが第一経路に含まれる場合に、構成リンク及び追加リンクにて終点ノードから始点ノードへ向かう通信を許可する手法はこれに限定されるものではない。例えば、制限ノードが第一経路に含まれる場合に、トポロジ情報変更部１２２が、構成リンク及び追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、トポロジ情報を変更してもよい。
【００７０】
以下では、図１３Ａ及び図１３Ｂを用いて、トポロジ情報変更部１２２による処理のその他の例を説明する。図１３Ａ及び図１３Ｂは、トポロジ情報変更部１２２による処理のその他の例を説明するための図である。
【００７１】
トポロジ情報変更部１２２は、制限ノードが第一経路に含まれる場合に、以下に説明するようにトポロジ情報を変更する。すなわち、トポロジ情報変更部１２２は、始点側ノードと経路外ノードとを結ぶポート間の接続については、図１３Ａに示すように、構成リンクに沿って始点側ノードから経路外ノードへ向かうリンクを新たに生成することにより、トポロジ情報を変更する。さらに、トポロジ情報変更部１２２は、追加リンクに沿って経路外ノードから始点側ノードへ向かうリンクを新たに生成することにより、トポロジ情報を変更する。
【００７２】
また、トポロジ情報変更部１２２は、終点側ノードと経路外ノードとを結ぶポート間の接続については、図１３Ｂに示すように、構成リンクに沿って経路外ノードから終点側ノードへ向かうリンクを新たに生成することにより、トポロジ情報を変更する。さらに、トポロジ情報変更部１２２は、追加リンクに沿って終点側ノードから経路外ノードへ向かうリンクを新たに生成することにより、トポロジ情報を変更する。
【００７３】
なお、経路探索装置１００は、上記の実施例で説明した各種の処理は、あらかじめ用意されたプログラムをコンピュータで実行することによって実現することができる。そこで、以下では、上記の実施例と同様の機能を有するプログラムを実行するコンピュータについて説明する。
【００７４】
図１４は、本実施例に係る経路探索装置を構成するコンピュータのハードウェア構成を示す図である。図１４に示すように、コンピュータ２００は、ＲＡＭ２１０と、ＨＤＤ２２０と、ＣＰＵ２３０と、ＲＯＭ２４０とを有する。各装置２１０〜２４０は、バス２５０に接続される。
【００７５】
そして、ＲＯＭ２４０には、上記の実施例と同様の機能を発揮するプログラムがあらかじめ記憶されている。つまり、ＲＯＭ２４０には、第一経路探索プログラム２４１、トポロジ情報変更プログラム２４２、ポート情報変更プログラム２４３、第二経路探索プログラム２４４、冗長経路探索プログラム２４５及び出力プログラム２４６があらかじめ記憶されている。
【００７６】
そして、ＣＰＵ２３０が、プログラム２４１〜２４４を読み出して実行することで、第一経路探索プロセス２３１、トポロジ情報変更プロセス２３２、ポート情報変更プロセス２３３及び第二経路探索プロセス２３４として機能するようになる。また、ＣＰＵ２３０が、プログラム２４５及び２４６を読み出して実行することで、冗長経路探索プロセス２３５及び出力プロセス２３６として機能するようになる。なお、各プロセス２３１〜２３６は、図２に示した第一経路探索部１２１、トポロジ情報変更部１２２、ポート情報変更部１２３、第二経路探索部１２４、冗長経路探索部１２５及び出力部１２６にそれぞれ対応する。
【００７７】
また、ＨＤＤ２２０には、トポロジテーブル２２１、第一経路テーブル２２２、ポートテーブル２２３、第二経路テーブル２２４及び冗長経路テーブル２２５が設けられる。なお、各テーブル２２１〜２２５は、図２に示したトポロジ情報記憶部１１１、第一経路情報記憶部１１２、ポート情報記憶部１１３、第二経路情報記憶部１１４及び冗長経路情報記憶部１１５にそれぞれ対応する。
【００７８】
なお、上記のプログラム２４１〜２４６は、必ずしもＲＯＭ２４０に記憶させておく必要はなく、ＣＤ−ＲＯＭ等の記憶媒体に記憶されたプログラムを、コンピュータ２００が読み出して実行するようにしてもよい。また、公衆回線、インターネット、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等にこれらプログラムを記憶させておき、コンピュータ２００がこれらからプログラムを読み出して実行するようにしてもよい。
【符号の説明】
【００７９】
１００ 経路探索装置
１１０ 記憶部
１１１ トポロジ情報記憶部
１１２ 第一経路情報記憶部
１１３ ポート情報記憶部
１１４ 第二経路情報記憶部
１１５ 冗長経路情報記憶部
１２０ 制御部
１２１ 第一経路探索部
１２２ トポロジ情報変更部
１２３ ポート情報変更部
１２４ 第二経路探索部
１２５ 冗長経路探索部
１２６ 出力部
【特許請求の範囲】
【請求項１】
複数のノードがリンクで接続されたネットワークにおけるノード間の接続状態を示すトポロジ情報を用いて、前記ネットワーク上で始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索する第一経路探索部と、
前記第一経路を前記複数の経路から除外するとともに、前記第一経路を構成する構成リンクに対して当該構成リンクと方向が反対である追加リンクを設定することにより、前記トポロジ情報を変更するトポロジ情報変更部と、
ポート間の接続に制限を含む制限ノードが前記第一経路に含まれる場合に、前記構成リンク及び前記追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、前記制限ノードにおけるポート間の接続の制限を示すポート情報を変更するポート情報変更部と、
前記変更されたトポロジ情報と前記変更されたポート情報とを用いて、前記複数の経路から前記第一経路と異なる第二経路を探索する第二経路探索部と、
前記第一経路と前記第二経路とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する冗長経路探索部と
を備えたことを特徴とする経路探索装置。
【請求項２】
前記ポート情報変更部は、前記第一経路にて前記制限ノードよりも始点ノード側に存在する始点側ノードと前記第一経路にて前記制限ノードよりも終点ノード側に存在する終点側ノードとを結ぶポート間の接続については、前記構成リンク及び前記追加リンクに沿って前記終点側ノードから前記始点側ノードへ向かう方向の通信を許可することにより、前記ポート情報を変更することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記第二経路探索部は、
探索すべき前記第二経路がサブノードに生成された接続を使用する場合、前記制限ノード内の前記終点側ノードから前記始点側ノードへの接続を使用することを特徴とする請求項２に記載の経路探索装置。
【請求項４】
前記ポート情報変更部は、前記始点側ノードと前記第一経路に含まれないノードである経路外ノードとを結ぶポート間の接続については、前記構成リンクに沿って前記始点側ノードから前記経路外ノードへ向かう方向の通信を許可し、かつ、前記追加リンクに沿って前記経路外ノードから前記始点側ノードへ向かう方向の通信を許可することにより、前記ポート情報を変更することを特徴とする請求項２に記載の経路探索装置。
【請求項５】
前記第二経路探索部は、
探索すべき前記第二経路がサブノードあるいは前記制限ノード内の前記経路外ノードと前記始点側ノード間の接続を使用する場合、前記制限ノード内の前記終点側ノードから前記始点側ノードへの接続を使用することを特徴とする請求項４に記載の経路探索装置。
【請求項６】
前記ポート情報変更部は、前記終点側ノードと前記経路外ノードとを結ぶポート間の接続については、前記構成リンクに沿って前記経路外ノードから前記終点側ノードへ向かう方向の通信を許可し、かつ、前記追加リンクに沿って前記終点側ノードから前記経路外ノードへ向かう方向の通信を許可することにより、前記ポート情報を変更することを特徴とする請求項４に記載の経路探索装置。
【請求項７】
前記第二経路探索部は、
探索すべき前記第二経路がサブノードあるいは前記制限ノード内の前記経路外ノードと前記終点側ノード間の接続を使用する場合、前記制限ノード内の前記終点側ノードから前記始点側ノードへの接続を使用することを特徴とする請求項６に記載の経路探索装置。
【請求項８】
コンピュータが
複数のノードがリンクで接続されたネットワークにおけるノード間の接続状態を示すトポロジ情報を用いて、前記ネットワーク上で始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索し、
前記第一経路を前記複数の経路から除外するとともに、前記第一経路を構成する構成リンクに当該構成リンクと方向が反対である追加リンクを設定することにより、前記トポロジ情報を変更し、
ポート間の接続に制限を含む制限ノードが前記第一経路に含まれる場合に、前記構成リンク及び前記追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、前記制限ノードにおけるポート間の接続の制限を示すポート情報を変更し、
前記変更されたトポロジ情報と前記変更されたポート情報とを用いて、前記複数の経路から前記第一経路と異なる第二経路を探索し、
前記第一経路と前記第二経路とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する
ことを含むことを特徴とする経路探索方法。
【請求項９】
コンピュータに、
複数のノードがリンクで接続されたネットワークにおけるノード間の接続状態を示すトポロジ情報を用いて、前記ネットワーク上で始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索し、
前記第一経路を前記複数の経路から除外するとともに、前記第一経路を構成する構成リンクに当該構成リンクと方向が反対である追加リンクを設定することにより、前記トポロジ情報を変更し、
ポート間の接続に制限を含む制限ノードが前記第一経路に含まれる場合に、前記構成リンク及び前記追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、前記制限ノードにおけるポート間の接続の制限を示すポート情報を変更し、
前記変更されたトポロジ情報と前記変更されたポート情報とを用いて、前記複数の経路から前記第一経路と異なる第二経路を探索し、
前記第一経路と前記第二経路とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する
処理を実行させることを特徴とする経路探索プログラム。
【請求項１】
複数のノードがリンクで接続されたネットワークにおけるノード間の接続状態を示すトポロジ情報を用いて、前記ネットワーク上で始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索する第一経路探索部と、
前記第一経路を前記複数の経路から除外するとともに、前記第一経路を構成する構成リンクに対して当該構成リンクと方向が反対である追加リンクを設定することにより、前記トポロジ情報を変更するトポロジ情報変更部と、
ポート間の接続に制限を含む制限ノードが前記第一経路に含まれる場合に、前記構成リンク及び前記追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、前記制限ノードにおけるポート間の接続の制限を示すポート情報を変更するポート情報変更部と、
前記変更されたトポロジ情報と前記変更されたポート情報とを用いて、前記複数の経路から前記第一経路と異なる第二経路を探索する第二経路探索部と、
前記第一経路と前記第二経路とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する冗長経路探索部と
を備えたことを特徴とする経路探索装置。
【請求項２】
前記ポート情報変更部は、前記第一経路にて前記制限ノードよりも始点ノード側に存在する始点側ノードと前記第一経路にて前記制限ノードよりも終点ノード側に存在する終点側ノードとを結ぶポート間の接続については、前記構成リンク及び前記追加リンクに沿って前記終点側ノードから前記始点側ノードへ向かう方向の通信を許可することにより、前記ポート情報を変更することを特徴とする請求項１に記載の経路探索装置。
【請求項３】
前記第二経路探索部は、
探索すべき前記第二経路がサブノードに生成された接続を使用する場合、前記制限ノード内の前記終点側ノードから前記始点側ノードへの接続を使用することを特徴とする請求項２に記載の経路探索装置。
【請求項４】
前記ポート情報変更部は、前記始点側ノードと前記第一経路に含まれないノードである経路外ノードとを結ぶポート間の接続については、前記構成リンクに沿って前記始点側ノードから前記経路外ノードへ向かう方向の通信を許可し、かつ、前記追加リンクに沿って前記経路外ノードから前記始点側ノードへ向かう方向の通信を許可することにより、前記ポート情報を変更することを特徴とする請求項２に記載の経路探索装置。
【請求項５】
前記第二経路探索部は、
探索すべき前記第二経路がサブノードあるいは前記制限ノード内の前記経路外ノードと前記始点側ノード間の接続を使用する場合、前記制限ノード内の前記終点側ノードから前記始点側ノードへの接続を使用することを特徴とする請求項４に記載の経路探索装置。
【請求項６】
前記ポート情報変更部は、前記終点側ノードと前記経路外ノードとを結ぶポート間の接続については、前記構成リンクに沿って前記経路外ノードから前記終点側ノードへ向かう方向の通信を許可し、かつ、前記追加リンクに沿って前記終点側ノードから前記経路外ノードへ向かう方向の通信を許可することにより、前記ポート情報を変更することを特徴とする請求項４に記載の経路探索装置。
【請求項７】
前記第二経路探索部は、
探索すべき前記第二経路がサブノードあるいは前記制限ノード内の前記経路外ノードと前記終点側ノード間の接続を使用する場合、前記制限ノード内の前記終点側ノードから前記始点側ノードへの接続を使用することを特徴とする請求項６に記載の経路探索装置。
【請求項８】
コンピュータが
複数のノードがリンクで接続されたネットワークにおけるノード間の接続状態を示すトポロジ情報を用いて、前記ネットワーク上で始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索し、
前記第一経路を前記複数の経路から除外するとともに、前記第一経路を構成する構成リンクに当該構成リンクと方向が反対である追加リンクを設定することにより、前記トポロジ情報を変更し、
ポート間の接続に制限を含む制限ノードが前記第一経路に含まれる場合に、前記構成リンク及び前記追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、前記制限ノードにおけるポート間の接続の制限を示すポート情報を変更し、
前記変更されたトポロジ情報と前記変更されたポート情報とを用いて、前記複数の経路から前記第一経路と異なる第二経路を探索し、
前記第一経路と前記第二経路とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する
ことを含むことを特徴とする経路探索方法。
【請求項９】
コンピュータに、
複数のノードがリンクで接続されたネットワークにおけるノード間の接続状態を示すトポロジ情報を用いて、前記ネットワーク上で始点ノードから終点ノードへ至る複数の経路からリンクのコストの総和が最小となる第一経路を探索し、
前記第一経路を前記複数の経路から除外するとともに、前記第一経路を構成する構成リンクに当該構成リンクと方向が反対である追加リンクを設定することにより、前記トポロジ情報を変更し、
ポート間の接続に制限を含む制限ノードが前記第一経路に含まれる場合に、前記構成リンク及び前記追加リンクにて終点ノードから始点ノードへ向かう通信が許可されるように、前記制限ノードにおけるポート間の接続の制限を示すポート情報を変更し、
前記変更されたトポロジ情報と前記変更されたポート情報とを用いて、前記複数の経路から前記第一経路と異なる第二経路を探索し、
前記第一経路と前記第二経路とで重複する構成リンクを削除することにより、互いに重複しない一対の冗長経路を探索する
処理を実行させることを特徴とする経路探索プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１０Ｃ】
【図１１】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１０Ｃ】
【図１１】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図１４】
【公開番号】特開２０１３−５１６４７（Ｐ２０１３−５１６４７Ａ）
【公開日】平成２５年３月１４日（２０１３．３．１４）
【国際特許分類】
【出願番号】特願２０１１−１８９７７３（Ｐ２０１１−１８９７７３）
【出願日】平成２３年８月３１日（２０１１．８．３１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２５年３月１４日（２０１３．３．１４）
【国際特許分類】
【出願日】平成２３年８月３１日（２０１１．８．３１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]