通信ネットワーク、ネットワークノード、通信経路制御方式、及び通信経路制御プログラム
【課題】障害時に備えて保持される代替経路表を計算するための計算量、及び、記憶するためのメモリサイズを抑えつつ高速に通信経路の切り替えを行うことが可能な通信ネットワークを提供する。
【解決手段】ネットワークノードの各々は、複数のインターフェイスと、経路情報を記録した主経路表と、主経路表に基づいてパケットを転送するルーティング処理部と、ネットワークリソースの障害時に主経路表の経路情報を更新する代替経路情報を記録した代替経路表を記憶する代替経路表記憶部と、特定のネットワークリソースに障害が発生したときに当該ネットワークリソースに対応する代替経路表を作成するか否かを決定する代替経路表判定部と、代替経路情報を計算する代替経路表計算部と、障害の発生したネットワークリソースに対応する代替経路表を用いて主経路表を更新する経路表更新部とを備える。
【解決手段】ネットワークノードの各々は、複数のインターフェイスと、経路情報を記録した主経路表と、主経路表に基づいてパケットを転送するルーティング処理部と、ネットワークリソースの障害時に主経路表の経路情報を更新する代替経路情報を記録した代替経路表を記憶する代替経路表記憶部と、特定のネットワークリソースに障害が発生したときに当該ネットワークリソースに対応する代替経路表を作成するか否かを決定する代替経路表判定部と、代替経路情報を計算する代替経路表計算部と、障害の発生したネットワークリソースに対応する代替経路表を用いて主経路表を更新する経路表更新部とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動的に経路制御を行う通信ネットワークにおいて高速に経路切替を行う技術に関する。
【背景技術】
【０００２】
通信ネットワークの安定性向上が急務となっている。インターネットに代表される通信ネットワーク技術が広く普及するのに伴い、通信ネットワークの障害が社会へ与える影響度も増している。
【０００３】
通信ネットワークは、データを転送するネットワークノード（以下、ノード）と、ノード間を接続するリンクとで構成される。通常、通信ネットワークは、通信ネットワークを構成するネットワークリソースであるノードとリンクを冗長構成にすることでネットワークの信頼性の向上を計っている。動的に経路制御を行う通信ネットワークでは、各ノードにおいて最適な経路情報を制御する経路制御プロトコルが動作している。このような動的経路制御を行うネットワークにおいて各ノードは、通信ネットワークを構成する他のノードとの間で経路情報を交換して、取得された経路情報に基づいて最適な経路情報を自律的に形成する。例えば、自ノードに接続されたリンクや当該リンクを介して接続されるノードに障害が発生した場合、障害を検知したノードは、他のノードに障害を通知する。障害を通知されたノードは、障害の発生したノード、あるいはリンクを除いた状態で経路計算を行い、新たな経路情報を決定する。このように、動的経路制御を行う通信ネットワークは、通信ネットワーク内に障害が発生しても、他のノードやリンクを用いたデータ転送経路を自律的に形成することより通信を継続することを可能としている。
【０００４】
動的経路制御を行う経路制御プロトコルの一つとして、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）が知られている（非特許文献１）。ＯＳＰＦは、ＩＥＴＦ（Ｉｎｔｅｒｎｅｔ Ｅｎｇｉｎｅｅｒｉｎｇ Ｔａｓｋ Ｆｏｒｃｅ）で標準化されている代表的なリンクステートアルゴリズムである。ＯＳＰＦが動作する通信ネットワークにおいて、各ノードは、互いに、ネットワークのトポロジー情報を交換し合う。このトポロジー情報は、通信ネットワーク内のノードやリンクの接続関係を示しており、各ノードは、トポロジー情報に基づいて経路情報を計算する。各ノードは、トポロジー情報に基づいて計算された経路情報により、受信されるパケットの宛先に対する最適な次転送先を決定することができる。
【０００５】
通信ネットワーク内のノードやリンクに障害が発生した場合、以下のフェーズで通信の復旧が行われる。まず、障害の発生したノードやリンクに隣接するノードがその障害を検知する障害検知フェーズ。次に、検知した障害を通信ネットワーク中の他のノードへ通知する通知フェーズ。さらに、障害発生後のトポロジーに基づいて、転送経路の再計算を行う経路計算フェーズ。そして、各ノードが、経路計算結果を経路表へ更新する経路表更新フェーズ。以上の４つのフェーズである。通信ネットワークの安定のためには、障害の発生を検知してから各ノードの経路表が更新されるまでの時間が短いほうがよい。しかし、通信ネットワークが大規模になると、前述の経路計算フェーズに時間がかかってしまうために、通信の復旧までに長い時間を要してしまう。そこで、障害発生から通信復旧までの時間を短縮するために、通信ネットワーク中のリンクもしくはノードに障害が発生した場合に備えて、各ノードが、予め障害時に使用する経路表を計算して、代替経路表として保持しておく技術が以下の通り検討されている。
【０００６】
特許文献１は、代替経路のループ判定を行い、ループとならない経路のみを用いる高速経路切替方式を開示している。特許文献１の高速経路切替方式を実施するルータ装置は、ネットワークインターフェイスと、パケット転送部と、主経路計算部と、代替経路表計算部と、切替部とを少なくとも備え、さらにループ経路判定部を備える。ネットワークインターフェイスは、他のルータと接続される。パケット転送部は、予め主経路表に格納された経路情報に基づいてネットワークインターフェイス経由で受信したパケットのルーティング処理を行う。主経路計算部は、主経路表に格納する経路情報を計算する。代替経路表計算部は、ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の障害を検知したときに使用する代替経路を計算して代替経路表に格納する。ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の障害を検知したときに代替経路表に格納されている経路情報への入替処理を行う。ループ経路判定部は、代替経路表計算部により代替経路表に代替経路情報を格納する際に代替経路がループとなるか否かの判定を行って、ループとならないと判定された代替経路を代替経路表に格納する。
【０００７】
特許文献１の高速経路切替方式によれば、リンク障害時の高速経路切替を行う際にループとなる経路を切り替え対象から除外することができ、転送パケットのループの発生を防止し、ルータ装置の負荷を軽減しつつ、高速経路切替が実現できる。
【０００８】
しかし、このような高速切替方式においては、各ノードが障害の可能性のある全てのノード及びリンクに対応する代替経路表を予め用意しておくことになり、代替経路表を計算する計算量、および、代替経路表を保持しておくための記憶メモリの容量の点から現実的ではなかった。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００６−２７９４８２号公報
【非特許文献】
【００１０】
【非特許文献１】”OSPF Version2”,J.Moy,RFC2328,InternetEngineering Task Force,April 1998
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、障害時に備えて保持される代替経路表を計算するための計算量、及び、記憶するためのメモリサイズを抑えつつ高速に通信経路の切り替えを行うことが可能な通信ネットワークを提供することである。
【課題を解決するための手段】
【００１２】
本発明の通信ネットワークは、複数のネットワークノードを具備する通信ネットワークであって、複数のネットワークノードの各々は、複数のインターフェイスと、通信ネットワークにおける経路情報を記録した主経路表と、主経路表に基づいて複数のインターフェイスから入力されるパケットを転送するルーティング処理部と、通信ネットワークを構成するネットワークリソースに対応して設けられて、ネットワークリソースの障害時に主経路表に記録された経路情報のうちで更新されるべき経路情報の代替経路情報を記録した代替経路表を記憶する代替経路表記憶部と、ネットワークリソースは、複数のネットワークノード、および複数のネットワークノードの間を接続するリンクを含み、ネットワークリソースのうちから選択する選択ネットワークリソースに障害が発生したときに、主経路表の経路情報の更新が必要であるか否かに基づいて、選択ネットワークリソースに対応する代替経路表を作成するか否かを決定する代替経路表判定部と、代替経路表を作成すると決定された選択ネットワークリソースに対応する選択代替経路表に記録されるべき代替経路情報を計算する代替経路表計算部と、障害を検知すると障害の発生したネットワークリソースに対応する代替経路表に記録された代替経路情報を用いて主経路表の経路情報を更新する経路表更新部とを備える。
【００１３】
本発明のネットワークノードは、上述の通信ネットワークを構成する。
【００１４】
本発明の通信経路制御方式は、複数のネットワークノードを具備する通信ネットワークにおいて、通信ネットワークにおける経路情報を記録するステップと、主経路表に基づいて複数のインターフェイスから入力されるパケットを転送するステップと、通信ネットワークを構成するネットワークリソースに対応して設けられて、ネットワークリソースの障害時に主経路表に記録された前記経路情報のうちで更新されるべき経路情報の代替経路情報を記録した代替経路表を記憶するステップと、ネットワークリソースは、複数のネットワークノード、および複数のネットワークノードの間を接続するリンクを含み、ネットワークリソース選択する選択ネットワークリソースに障害が発生したときに、主経路表の経路情報の更新が必要であるか否かに基づいて、選択ネットワークリソースに対応する代替経路表を作成するか否かを決定するステップと、代替経路表を作成すると決定されたネットワークリソースに対応する選択代替経路表に記録されるべき代替経路情報を計算するステップと、障害を検知すると障害の発生したネットワークリソースに対応する代替経路表に記録された代替経路情報を用いて主経路表の経路情報を更新するステップとを備える。
【００１５】
本発明のコンピュータプログラムは、上述の通信経路制御方式をコンピュータに実行させる。
【発明の効果】
【００１６】
本発明によれば、障害時に備えて保持される代替経路表を計算するための計算量、及び、記憶するためのメモリサイズを抑えつつ高速に通信経路の切り替えを行うことが可能な通信ネットワークを提供することができる。
【図面の簡単な説明】
【００１７】
【図１】第１実施形態におけるノード１の構成を示す図である。
【図２Ａ】第１実施形態における主経路表１２２の一例を示す図である。
【図２Ｂ】第１実施形態における代替経路表１３１１〜１３１ｎの一例を示す図である。
【図３】第１実施形態における代替経路表を作成する動作フローを示している。
【図４】第１実施形態における代替経路表１３１１〜１３１ｎを作成するべきリンクを抽出する動作フローである。
【図５Ａ】第１実施形態における主経路計算部１１２の生成した最短パスツリーの一例を示す図である。
【図５Ｂ】第１実施形態における代替経路表判定部１１３が最短パスツリーから抽出したパス６２を示す図である。
【図６】第１実施形態におけるリンクｅｋの障害時に主経路表１２２の経路情報の更新が必要であるか否かを判定する動作フローである。
【図７】第２実施形態におけるノード１の構成を示す図である。
【図８Ａ】第２実施形態における作成指示メッセージのペイロードを示す図である。
【図８Ｂ】従来のＯＳＰＦにおける「Ｎｅｔｗｏｒｋ ＬＳＡ」のペイロードの構成を示す図である。
【図９】第２実施形態における代替経路表を作成する動作フローである。
【図１０】第２実施形態における計算指定ノードを特定する動作フローである。
【図１１】第２実施形態における他のノードから作成指示メッセージを受信した場合の動作フローを示している。
【発明を実施するための形態】
【００１８】
添付図面を参照して、本発明の実施形態による通信ネットワークを以下に説明する。
【００１９】
（第１実施形態）
はじめに、本発明の第１実施形態における通信ネットワークの説明を行う。
【００２０】
本実施形態の通信ネットワークは、通信ネットワークを構成する各ネットワークノード（以下、ノード）が、通信ネットワーク内に存在する各ノード間を接続するリンクの障害に備えて、各リンクに障害が発生した場合に使用するべき代替経路表を、各リンクに対応させて予め作成しておく。各ノードは、障害発生時において、障害の発生したリンクに対応する代替経路表を用いて、通常時に使用される主経路表を更新する。各ノードは、代替経路表を作成するときに、当該リンクに障害が発生したと想定した場合に、主経路表に記録された経路情報の更新が必要となるか否かを判定する。各ノードは、この判定において、主経路表の更新が必要と判定された場合にのみ、当該リンクに対応する代替経路表を作成する。このように、各ノードは、必要と判定された代替経路表のみを作成するため、代替経路表を計算する計算量、及び代替経路表を記憶するメモリ量を抑えることが可能となる。
【００２１】
［構成の説明］
まず、本実施形態における通信ネットワークを構成するノードの構成を説明する。図１は、本実施形態におけるノード１の構成を示す図である。本実施形態のノード１は、経路制御部１１と、パケット転送部１２と、代替経路表管理部１３と、ネットワークインターフェイス（以下、ＩＦ）２１〜２ｎを備える。
【００２２】
本実施形態の通信ネットワークは、図１に示すようなノード１を複数備えており、各ノード１は、ＩＦ２１〜２ｎに接続されたリンク３１〜３ｎにより他のノードと接続されて通信ネットワークを構成する。
【００２３】
はじめに、パケット転送部１２の説明を行う。パケット転送部１２は、ルーティング処理部１２１と、主経路表１２２とを備える。
【００２４】
まず、主経路表１２２は、経路情報を記録したデータテーブルである。図２Ａは、本実施形態における主経路表１２２の一例を示す図である。図２Ａを参照すると、主経路表１２２は、宛先４１、マスク長４２、次転送先４３、及びインターフェイス４４を一組に対応させて記録している。宛先４１は、ノード１が受信するパケットのヘッダに記録された宛先ＩＰ（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ）アドレスと対応されるべきネットワークアドレスである。マスク長４２は、宛先４１のネットワークアドレスにおけるサブネットマスクである。次転送先４３は、宛先４１のネットワークアドレスに対応する受信パケットの転送先のノード１のＩＰアドレスである。インターフェイス４４は、次転送先４３がリンクを介して接続されているＩＦ２１〜２ｎの番号である。なお、図２Ａは、ＩＰｖ４の場合を示しているが、これはＩＰｖ６であっても良い。
【００２５】
次に、ルーティング処理部１２１は、受信されたパケットの転送処理を行う。ルーティング処理部１２１は、ＩＦ２１〜２ｎを介して受信されたパケットのヘッダに格納された宛先ＩＰアドレスと、主経路表１２２の宛先４１及びマスク長４２とを参照して次転送先４３を特定する。ルーティング処理部１２１は、特定された次転送先４３に対応するインターフェイス４４へパケットを送出する。
【００２６】
次に、経路制御部１１の説明を行う。経路制御部１１は、トポロジー情報交換部１１１と、主経路計算部１１２と、代替経路表判定部１１３と、代替経路表計算部１１４とを備える。
【００２７】
まず、トポロジー情報交換部１１１は、ＯＳＰＦなどの経路制御プロトコルを使用して、隣接ノードとの間でトポロジー情報の交換を行う。ここで、トポロジー情報とは、通信ネットワーク内に存在するノードと、ノード間を接続するリンクとがどのような接続関係となっているかを示す情報である。また、隣接ノードとは、ＩＦ２１〜２ｎに接続されたリンク３１〜３ｎを介して接続されたノードである。トポロジー情報交換部１１１は、取得したトポロジー情報を、主経路計算部１１２、代替経路表判定部１１３、及び代替経路表計算部１１４とへ出力する。
【００２８】
また、トポロジー情報交換部１１１は、障害通知を送受信する。障害通知は、リンク３１〜３ｎに障害が発生した場合や、ノード１内に障害が発生した場合に、トポロジー情報交換部１１１によりパケット転送部１２を介して隣接ノードへ送信される。トポロジー情報交換部１１１は、障害通知を受信すると通信ネットワーク内の障害を検知して、通信ネットワーク内のトポロジーに変化が発生したことを検知する。トポロジー情報交換部１１１は、障害発生前後における通信ネットワークのトポロジー情報の変化分を抽出して、隣接ノードへ通知する。また、トポロジー情報交換部１１１は、障害通知を主経路計算部１１２と、代替経路表判定部１１３と、代替経路表計算部１１４と、経路表更新部１３２へ出力する。
【００２９】
なお、トポロジー情報交換部１１１は、トポロジー情報や障害通知を、パケット転送部１２と、ＩＦ３１〜３ｎとを介して隣接ノード１と交換する。
【００３０】
次に、主経路計算部１１２は、主経路表１２２へ記録するべき経路情報を計算する。主経路計算部１１２は、トポロジー情報交換部１１１からトポロジー情報を入力すると、トポロジー情報に基づいて経路情報を計算して、主経路表１２２の経路情報を更新する。主経路計算部１１２は、一般的なＩＧＰ（Ｉｎｔｅｒｉｏｒ Ｇａｔｅｗａｙ Ｐｒｏｔｏｃｏｌ）を用いて経路情報を計算する。ＩＧＰには、前述したＯＳＰＦが含まれる。
【００３１】
次に、代替経路表判定部１１３は、代替経路表を作成するべきか否かを判定する。代替経路表判定部１１３は、通信ネットワーク中の全てのリンクに対して、各リンクに障害が発生した場合に、各リンクに対応する代替経路表を作成するべきか否かを判定する。代替経路表判定部１１３は、トポロジー情報取得部１１１からトポロジー情報を入力したとき、あるいは、所定の時間毎に、各リンクに対応する代替経路表を作成するべきか否かの判定を行う。代替経路表判定部１１３は、判定結果を代替経路表計算部１１４へ通知する。判定結果は、代替経路表を作成するべきと判定されたリンクを含んでいる。
【００３２】
次に、代替経路表計算部１１４は、代替経路情報を計算する。代替経路表計算部１１４は、代替経路表判定部１１３から判定結果を入力すると、判定結果に含まれるリンクに対応する代替経路表に記録するべき代替経路情報を計算する。代替経路表計算部１１４は、代替経路情報を計算するべきリンクに、障害が発生したと想定して、代替経路情報を計算する。代替経路表計算部１１４は、後述する代替経路表管理部１３の代替経路表記録部１３１において、代替経路情報の計算されたリンクに対応した代替経路表へ計算された代替経路情報を記録する。
【００３３】
次に、代替経路表管理部１３の説明を行う。代替経路表管理部１３は、代替経路表記憶部１３１と、経路表更新部１３２とを備える。
【００３４】
まず、代替経路表記憶部１３１は、代替経路表１３１１〜１３１ｎを記録している。代替経路表１３１１〜１３１ｎは、通信ネットワーク内で障害が発生したときに、主経路表に記録された経路情報を更新するための代替経路情報を記録している。代替経路表１３１１〜１３１ｎは、通信ネットワークに存在する各リンクに対応して設けられる。本実施形態において代替経路表記憶部１３１は、通信ネットワークに存在する全てのリンクに対応する代替経路表１３１１〜１３１ｎを記憶しているわけではない。代替経路表記憶部１３１は、代替経路表判定部１１３の判定結果に基づいて、代替経路表１３１１〜１３１ｎを作成するべきと判定されたリンクに対応する代替経路表１３１１〜１３１ｎのみが記憶されている。
【００３５】
図２Ｂは、本実施形態における代替経路表１３１１〜１３１ｎの一例を示す図である。代替経路表１３１１〜１３１ｎは、主経路表１２２と同様の項目が記録されている。すなわち、代替経路表１３１１〜１３１ｎは、宛先５１、マスク長５２、次転送先５３、インターフェイス５４の項目を備える。これらはそれぞれ、主経路表１２２における宛先４１、マスク長４２、次転送先４３、インターフェイス４４の各項目と同様であるので重ねての説明を省略する。
【００３６】
経路表更新部１３２は、代替経路表１３１１〜１３１ｎを用いて主経路表１２２を更新する。経路表更新部１３２は、経路制御部１１のトポロジー情報交換部１１１から障害通知を入力する。経路表更新部１３２は、通信ネットワーク内の特定のリンクに障害が発生したことを検知すると、障害の発生したリンク（以下、障害リンク）に対応する代替経路表（以下、選択代替経路表）を代替経路表記憶部１３１から特定して、選択代替経路表を用いて主経路表１２２を更新する。すなわち、主経路表１３１の経路情報は、障害リンクに対応する選択代替経路表に記録された代替経路情報により更新される。
【００３７】
なお、経路表更新部１３２は、主経路表１２２に記録された経路情報のうち、選択代替経路表に記録された代替経路情報に対応する経路情報のみを更新する。例えば、図２Ｂを選択代替経路表として説明すると、図２Ｂに、宛先５１として、「１９２．１６８．１．０」と「１９２．１６８．１２．０」のみが記録されているとする。この場合、図２Ａの主経路表１２２では、「１９２．１６８．１．０」と「１９２．１６８．１２．０」に対応する情報のみが更新される。そのため、主経路表１２２における宛先４１「１９２．１６８．１０．０」や、その他の図示されない宛先４１については更新されない。宛先４１「１９２．１６８．１０．０」は、この情報のまま、主経路表１２２に残ることになり、このままルーティング処理部１２１により使用される。
【００３８】
以上が、本実施形態における通信ネットワークの構成の説明である。本実施形態では、経路制御部１１の代替経路表判定部１１３が、通信ネットワーク内の各リンクに対して、代替経路表１３１１〜１３１ｎを作成するべきか否かを判定する。代替経路表計算部１１４は、代替経路表１３１１〜１３１ｎを作成すべきと判定されたリンクに対応する代替経路表１３１１〜１３１ｎのみを作成して、代替経路表管理部１３の代替経路表記憶部１３１へ記憶させる。このように、必要と判定された代替経路表１３１１〜１３１ｎのみを作成して、また、記憶するので、代替経路表計算部１１４の計算量を抑えることができ、また、代替経路表記憶部１３１のメモリ容量も抑えることが可能となる。
【００３９】
［動作方法の説明］
次に、本実施形態における通信ネットワークの動作方法の説明を行う。はじめに、図３を用いて、本実施形態における代替経路表を作成する動作方法の説明を行う。図３は、本実施形態における代替経路表を作成する動作フローを示している。
【００４０】
（ステップＳ１０）
代替経路表判定部１１３は、ネットワーク中の全リンクのうちから、代替経路表１３１１〜１３１ｎを作成するべきリンクを抽出する。代替経路表判定部１１３は、抽出されたリンクの集合をＮｕとする。
【００４１】
（ステップＳ１１）
代替経路表計算部１１４は、集合Ｎｕに含まれる各リンクに対して、当該リンクに障害が発生したと想定して代替経路情報を計算する。
【００４２】
（ステップＳ１２）
代替経路表計算部１１４は、計算された代替経路情報を、代替経路表管理部１３の代替経路記憶部１３１の対応する代替経路表１３１１〜１３１ｎへ記録する。
【００４３】
以上が、本実施形態における代替経路表を作成する動作方法の説明である。このようにして、代替経路表１３１１〜１３１ｎは作成され、代替経路表記憶部１３１へ記憶される。
【００４４】
次に、本実施形態における代替経路表１３１１〜１３１ｎを作成するべきリンクを抽出する動作方法を説明する。本動作方法は、前述のステップＳ１０の詳細な動作方法を説明するものである。図４は、本実施形態における代替経路表１３１１〜１３１ｎを作成するべきリンクを抽出する動作フローを示している。
【００４５】
（ステップＳ２０）
代替経路表判定部１１３は、空集合ＮｕとＮｎとを生成する。集合Ｎｕは、代替経路表を作成するべきと判定されたリンクの登録されるべき集合である。一方、集合Ｎｎは、代替経路表を作成する必要はないと判定されたリンクの登録されるべき集合である。
【００４６】
（ステップＳ２１）
代替経路表判定部１１３は、最短パスツリーから、自ノードをルートノードとしてまだ以降の処理が行われていない任意のリーフノードへのパスを抽出する。代替経路表判定部１１３は、主経路計算部１１２から、最短パスツリーを取得する。ここで、最短パスツリーは、トポロジー情報に基づいて生成される有効グラフであり、主経路計算部１１２は、最短パスツリーを用いて主経路表１２２へ記録するべき経路情報を計算する。代替経路表判定部１１３は、最短パスツリーから、本ステップ以降の処理を行っていない任意のリーフノードを一つ選択する。ここで、リーフノードとは、最短パスツリーの末端に位置するノード１である。代替経路表判定部１１３は、最短パスツリーにおいて自ノードから選択されたリーフノードまでのパスを抽出する。
【００４７】
図５Ａは、本実施形態における主経路計算部１１２の生成した最短パスツリーの一例を示す図である。図５Ａにおいて、符号６０は、ルートノードである自ノードである。ここでルートノードとは、最短パスツリーの最上位のノード１である。図５Ａにおいて、符号６１−１〜５は、リーフノードである。代替経路表判定部１１３は、リーフノード６１−１を選択したとする。この場合、代替経路表判定部１１３は、ルートノード（自ノード）６０からリーフノード６１−１までのパス６２を抽出する。
【００４８】
（ステップＳ２２）
代替経路表判定部１１３は、最短パスツリーから抽出したパスにおいて、自ノードからリーフノードまで、自ノードから近い順にリンクを「ｅ１，ｅ２，ｅ３・・・ｅｍ」とする。
【００４９】
図５Ｂは、本実施形態における代替経路表判定部１１３が最短パスツリーから抽出したパス６２を示す図である。図５Ｂに示すように、ルートノード（自ノード）６０からリーフノード６１−１へ向けて、ルートノード６０に近い順にリンクが「ｅ１，ｅ２，ｅ３・・・ｅｍ」とされている。
【００５０】
（ステップＳ２３）
代替経路表判定部１１３は、変数ｉを生成して、ｉに「１」を代入する。
【００５１】
（ステップＳ２４）
代替経路表判定部１１３は、リンクｅｉが集合Ｎｕの要素であるか否かを判定する。つまり、代替経路表判定部１１３は、リンクｅｉが代替経路表を作成するべきと判定されたリンクの集合Ｎｕに含まれるか否かを判定する。リンクｅｉが集合Ｎｕの要素である場合、ステップＳ２５へ進む。一方、リンクｅｉが集合Ｎｕの要素でない場合、ステップＳ２６へ進む。
【００５２】
（ステップＳ２５）
代替経路表判定部１１３は、リンクｅｉが集合Ｎｕの要素である場合、ｉを「ｉ＝ｉ＋１」とインクリメントする。この後、ステップＳ２４へ戻る。
【００５３】
ステップＳ２４、Ｓ２５において、代替経路表判定部１１３は、自ノードに近いリンクｅｉから集合Ｎｕの要素であるか否かを判定している。図５Ｂを参照すると、代替経路表判定部１１３は、ルートノード（自ノード）６０に近いリンクから順に、リンクｅｉが代替経路表を作成するべきと判定されたリンクの集合Ｎｕに含まれるか否かを判定することになる。これは、自ノードに近いリンクほど、障害が発生した場合に自ノードへの影響が大きく、主経路表１２２に記録された経路情報を更新する必要性が高くなることによる。
【００５４】
（ステップＳ２６）
代替経路表判定部１１３は、リンクｅｉが集合Ｎｕの要素でない場合、変数ｊを生成して、ｊに「ｍ」を代入する。
【００５５】
（ステップＳ２７）
代替経路表判定部１１３は、リンクｅｊが集合Ｎｎの要素であるか否かを判定する。つまり、代替経路表判定部１１３は、リンクｅｊが代替経路表を作成する必要はないと判定されたリンクの集合Ｎｎに含まれるか否かを判定する。リンクｅｊが集合Ｎｎの要素である場合、ステップＳ２８へ進む。一方、リンクｅｊが集合Ｎｎの要素でない場合、ステップＳ２９へ進む。
【００５６】
（ステップＳ２８）
代替経路表判定部１１３は、リンクｅｍが集合Ｎｎの要素である場合、ｊを「ｉ＝ｊ−１」とデクリメントする。この後、ステップＳ２７へ戻る。
【００５７】
ステップＳ２７、Ｓ２８において、代替経路表判定部１１３は、自ノードに遠い（リーフノードに近い）リンクｅｊから集合Ｎｎの要素であるか否かを判定している。図５Ｂを参照すると、代替経路表判定部１１３は、リーフノード６１−１に近いリンクから順に、リンクｅｉが代替経路表を作成する必要はないと判定されたリンクの集合Ｎｎに含まれるか否かを判定することになる。これは、自ノードから遠い（リーフノードに近い）リンクほど、障害が発生した場合の自ノードへの影響が少なく、主経路表１２２に記録された経路情報を更新する必要性が低くなることによる。
【００５８】
（ステップＳ２９）
代替経路表判定部１１３は、リンクｅｉが集合Ｎｕの要素でない場合、変数ｋを生成して、現在のｉとｊとの相加平均をとってその値を超えない最大の整数を代入する。すなわち、代替経路表判定部１１３は、「ｋ＝［（ｉ＋ｊ）／２］」を計算する。
【００５９】
本ステップの時点で最短パスツリーから抽出されたパスに含まれるリンクのうち、「リンクｅｉ〜リンクｅｊ」に対して経路更新が必要であるか否かの判定が行われていない。前述したように、自ノードに近いリンクほど、当該リンク障害時に主経路表１２２の経路情報を更新する必要が高くなり、自ノードから遠いリンクほど、当該リンクの障害時に主経路表１２２の経路情報を更新する必要が低くなる。以下のステップにおいて、代替経路表判定部１１３は、特定のリーフノードへのパスにおいて、図５Ｂに示すように、特定のリンクの障害時に主経路表１２２の経路情報を更新する必要の有無の分岐点となるリンクを探す処理を行う。
【００６０】
（ステップＳ３０）
代替経路表判定部１１３は、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要であるか否かを判定する。本ステップの詳細な動作は、後述する。経路情報の更新が必要である場合、ステップＳ３１へ進む。一方、経路情報の更新が必要でない場合、ステップＳ３３へすすむ。
【００６１】
（ステップＳ３１）
代替経路表判定部１１３は、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要である場合、リンクｅｉ〜リンクｅｋを集合Ｎｕの要素に追加する。つまり、特定のリーフノードへのパスにおいて、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要と判定すると、リンクｅｋより自ノード側の全てのリンクを、各リンクに障害が発生した場合に主経路表１２２の経路情報の更新が必要なリンクと決定する。これは、前述の通り、自ノードに近いリンクであればあるほど、障害時に主経路表１２２の経路情報を更新する必要が高くなることによる。本実施形態では、このように処理を行うことで、代替経路表判定部１１３は、判定のための計算量を減少させることができる。
【００６２】
（ステップＳ３２）
代替経路表判定部１１３は、ｉを「ｉ＝ｋ＋１」とする。この後、ステップＳ３５へ進む。
【００６３】
（ステップＳ３３）
代替経路表判定部１１３は、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要ない場合、リンクｅｋ〜リンクｅｊを集合Ｎｎの要素に追加する。つまり、特定のリーフノードへのパスにおいて、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要でない判定すると、リンクｅｋよりリーフノード側のリンクを全て、各リンクに障害が発生した場合に主経路表１２２の経路情報の更新が必要でないと決定する。これは、前述の通り、自ノードから遠いリンクであればあるほど、障害時に主経路表１２２の経路情報を更新する必要が低くなることによる。このように処理を行うことで、代替経路表判定部１１３は、判定のための計算量を減少させることができる。
【００６４】
（ステップＳ３４）
代替経路表判定部１１３は、ｊを「ｊ＝ｋ−１」とする。この後、ステップＳ３５へ進む。
【００６５】
（ステップＳ３５）
代替経路表判定部１１３は、ｉの値がｊの値を超えているか、「ｉ＞ｊ」を判定する。ｉの値がｊの値を超えていれば当該パスに含まれる全てのリンクに対して処理が完了したことになる。一方、ｉの値がｊの値を超えていない場合、当該パスに含まれる全てのリンクに対して、まだ、処理が完了していないことになる。ｉの値がｊの値を超えている場合、ステップＳ３６へ進む。一方、ｉの値がｊの値を超えていない場合、ステップＳ２９へ戻る。
【００６６】
（ステップＳ３６）
代替経路表判定部１１３は、ｉの値がｊの値を超えている場合、最短パスツリーに含まれる全てのリーフノードへのパスに対する処理が完了したか否かを判定する。最短パスツリーに含まれる全てのリーフノードへのパスに対する処理が完了していない場合、他のリーフノードへのパスに対する処理を行うために、ステップＳ２１へ戻る。一方、最短パスツリーに含まれる全てのリーフノードへのパスに対する処理が完了した場合、本動作方法は終了となる。この時点で、集合Ｎｕに含まれるリンクが、代替経路表１３１１〜１３１ｎを作成するべきリンクとなる。
【００６７】
以上が、本実施形態における代替経路表１３１１〜１３１ｎを作成するべきリンクを抽出する動作方法の説明である。このようにして、代替経路表１３１１〜１３１ｎを作成するべきリンクが抽出される。
【００６８】
次に、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要であるか否かを判定する動作方法を説明する。本動作方法は、前述のステップＳ３０の詳細な動作方法を説明するものである。図６は、本実施形態におけるリンクｅｋの障害時に主経路表１２２の経路情報の更新が必要であるか否かを判定する動作フローを示している。
【００６９】
（ステップＳ４０）
代替経路表判定部１１３は、現在、主経路表１２２に記録されている経路情報を取得する。
【００７０】
（ステップＳ４１）
代替経路表計算部１１４は、リンクｅｋに障害が発生したと想定して、経路情報（以下、本説明において、障害時経路情報）を計算する。代替経路表計算部１１４は、主経路計算部１１２と同様の方法により、障害時経路情報を計算する。代替経路表計算部１１４は、計算された障害時経路情報を、代替経路表判定部１１３へ出力する。
【００７１】
（ステップＳ４２）
代替経路表判定部１１３は、ステップＳ４０において主経路計算部１１２から取得した現在の経路情報と、ステップＳ４１において代替経路表計算部１１４により計算されたリンクｅｋの障害時の障害時経路情報とを比較する。
【００７２】
（ステップＳ４３）
代替経路表判定部１１３は、ステップＳ４２の比較において、リンクｅｋの障害前後で次転送先が異なる宛先ネットワークが存在するか否かを判定する。リンクｅｋの障害前後で次転送先が異なる宛先ネットワークが一つでも存在する場合、ステップＳ４４へ進む。一方、リンクｅｋの障害前後で次転送先が異なる宛先ネットワークが一つも存在しない場合、ステップＳ４５へ進む。
【００７３】
（ステップＳ４４）
代替経路表判定部１１３は、リンクｅｋの障害前後で次転送先が異なる宛先ネットワークが存在する場合、リンクｅｋ対する経路更新が必要であると判定する。このため、前述により、リンクｅｋは集合Ｎｕに属することになり、リンクｅｋに対応する代替経路表１３１１〜１３１ｎが作成されることになる。この場合、本動作方法は、終了となる。
【００７４】
（ステップＳ４５）
代替経路表判定部１１３は、リンクｅｋの障害前後で次転送先が異なる宛先ネットワークが存在しない場合、リンクｅｋに対する経路更新が必要ではないと判定する。このため、前述により、リンクｅｋは、集合Ｎｎに属することとなり、リンクｅｋに対応する代替経路表１３１１〜１３１ｎは作成されないことになる。以上で、動作方法は終了となる。
【００７５】
以上が、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要であるか否かを判定する動作方法の説明である。
【００７６】
以上が、本実施形態における通信ネットワークの説明である。
【００７７】
（第２実施形態）
次に、第２実施形態の通信ネットワークの説明を行う。
【００７８】
本実施形態の通信ネットワークは、通信ネットワークを構成する各ノードが、代替経路表を作成するか否かを判定するリンクの対象が第１実施形態と異なる。第１実施形態では、各ノードは、通信ネットワーク内の全てのリンクに対して代替経路表を作成するか否かを判定していた。本実施形態において各ノードは、自ノードに接続されたリンクについてのみ代替経路表を作成するか否かを判定する。また、本実施形態では各ノードが自ノードのみではなく、他のノードが代替経路表を作成するべきリンクを特定して、当該リンクを他のノードに通知する点が第１実施形態と異なる。これにより、各ノードは、自ノードに接続されたリンクに対する判定処理を行って、代替経路表の作成が必要と判定されたリンクに対する代替経路表の作成し、また、他のノードから通知を受けた代替経路表を作成するべきリンクに対する代替経路表とを作成すればよいため、代替経路表を計算する計算量、及び代替経路表を記憶するメモリ量を抑えることが可能となる。
【００７９】
［構成の説明］
まず、本実施形態における通信ネットワークを構成するノードの構成を説明する。図７は、本実施形態におけるノード１の構成を示す図である。本実施形態におけるノード１は、第１実施形態とほぼ同様の構成である。そのため、第１実施形態と同様の部分については重ねての説明を省略し、異なる部分を中心に説明を行う。また、第１実施形態と同様の構成については、同様の符号を付与して説明を行う。
【００８０】
本実施形態のノード１は、第１実施形態と同様に、経路制御部１１と、パケット転送部１２と、代替経路表管理部１３と、ネットワークインターフェイス（以下、ＩＦ）２１〜２ｎを備え、さらに、本実施形態では、作成指示通信部１４を備える。
【００８１】
なお、本実施形態の通信ネットワークは、第１実施形態と同様に、図７に示すようなノード１を複数備えており、各ノード１は、ＩＦ２１〜２ｎに接続されたリンク３１〜３ｎにより他のノードと接続されて通信ネットワークを構成する。
【００８２】
はじめに、経路制御部１１の説明を行う。経路制御部１１は、第１実施形態と同様に、トポロジー情報交換部１１１と、主経路計算部１１２と、代替経路表計算部１１４とを備え、さらに、本実施形態では、代替経路表判定部１１３に替わり、接続リンク代替経路表１１５を備える。
【００８３】
まず、トポロジー情報交換部１１１は、第１実施形態と同様である。すなわち、トポロジー情報交換部１１１は、ＯＳＰＦなどの経路制御プロトコルを使用して、隣接ノードとの間でトポロジー情報の交換を行う。また、トポロジー情報交換部１１１は、障害通知を入力すると、通信ネットワークのトポロジーに変化が発生したことを検知して、トポロジー情報の変化分を隣接ノードへ通知する。
【００８４】
次に、主経路計算部１１２は、第１実施形態と同様である。すなわち、主経路計算部１１２は、トポロジー情報に基づいて主経路表１２２へ記録するべき経路情報を計算して、主経路表１２２の経路情報を更新する。
【００８５】
次に、接続リンク代替経路表判定部１１５は、代替経路表を作成するべきか否かを判定する。接続リンク代替経路表判定部１１５は、ＩＦ２１〜２ｎに接続されたリンク３１〜３ｎの各々に対して代替経路表１３１１〜１３１ｎを作成するべきか否かを判定する。つまり、接続リンク代替経路表判定部１１５は、自ノードに接続されたリンクに対してのみ、代替経路表１３１１〜１３１ｎを作成するべきか否かの判定を行う。接続リンク代替経路表判定部１１５は、判定結果を代替経路表計算部１１４へ通知する。判定結果は、代替経路表を作成するべきと判定されたリンクを含んでいる。
【００８６】
また、接続リンク代替経路表判定部１１５は、リンク３１〜３ｎに対応する代替経路表１３１１〜１３１ｎを作成するべき他のノードを特定する。接続リンク代替経路表判定部１１５は、リンク３１〜３ｎのうちの特定のリンク（以下、選択接続リンク）に対する代替経路表１３１１〜１３１ｎを作成するべきと特定された他のノード（以下、計算指定ノード）に対する作成指示メッセージを作成指示通信部１４へ出力する。
【００８７】
作成指示メッセージは、選択接続リンクに対応する代替経路表１３１１〜１３１ｎの作成を、計算指定ノードへ要求するメッセージである。図８Ａは、本実施形態における作成指示メッセージのペイロードを示す図である。作成指示メッセージは、図８Ａに示すように「Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ」フィールド７０および「Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋ」フィールド７１をペイロードに格納している。作成指示メッセージは、ペイロードに、ＩＰヘッダと、ＴＣＰヘッダあるいはＵＤＰヘッダを付与したパケットとして送信される。なお、通信プロトコルはこれらに限定はしない。「Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ」フィールド７０および「Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋ」フィールド７１へは、図２Ａに示した主経路表１２２において、インターフェイス４４（選択接続リンク）に対応する宛先４１およびマスク長４２がそれぞれ記録される。「Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ」フィールド７０および「Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋ」フィールド７１に記録するべき情報は、ＯＳＰＦが動作するネットワークの場合、トポロジー情報を送受信するための「Ｎｅｔｗｏｒｋ ＬＳＡ」を参照することで取得できる。参考までに、従来のＯＳＰＦにおける「Ｎｅｔｗｏｒｋ ＬＳＡ」のペイロードの構成を図８Ｂに示す。図８Ｂ中の「Ｌｉｎｋ」 Ｓｔａｔｅ ＩＤ」フィールド７２に、「Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ」フィールド７０に対応する情報が格納され、また、図８Ｂ中の「Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋ」フィールド７３に、「Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋ」フィールド７１に対応する情報が格納されている。
【００８８】
次に、代替経路表計算部１１４は、第１実施形態と同様に、代替経路表１３１１〜１３１ｎへ記録するべき代替経路情報を計算する。代替経路表計算部１１４は、接続リンク代替経路表判定部１１５が代替経路表１３１１〜１３１ｎを作成するべきと判定したリンクに対応する代替経路表１３１１〜１３１ｎへ記録するべき代替経路情報を計算する。代替経路表計算部１１４は、代替経路表１３１１〜１３１ｎを作成するべきリンクに、障害が発生した場合を想定して、代替経路情報を計算する。代替経路表計算部１１４は、計算された代替経路情報を、後述する代替経路表管理部１３の代替経路表記録部１３１における対応する代替経路表１３１１〜１３１ｎへ記録する。
【００８９】
また、代替経路表計算部１１４は、後述する作成指示通信部１４から作成指示メッセージを入力する。代替経路表計算部１１４は、作成指示メッセージに格納された情報に基づいて代替経路表１３１１〜１３１ｎを作成するべきリンクを特定する。代替経路表計算部１１４は、特定されたリンクに障害が発生したと想定した場合の代替経路情報を計算して、代替経路表記録部１３１の対応する代替経路表１３１１〜１３１ｎへ計算された代替経路情報を記録する。
【００９０】
次に、作成指示通信部１４の説明を行う。作成指示通信部１４は、作成指示送信部１４１と、作成指示受信部１４２とを備える。
【００９１】
まず、作成指示送信部１４１は、接続リンク代替経路表判定部１１５から入力される作成指示メッセージを、計算指定ノードへ、パケット転送部１２を介して送信する。
【００９２】
次に、作成指示受信部１４２は、パケット転送部１２を介して、他のノードから受信される作成指示メッセージを代替経路表計算部１１４へ出力する。
【００９３】
次に、パケット転送部１２の説明を行う。パケット転送部１２は、第１実施形態と同様である。すなわち、パケット転送部１２は、ルーティング処理部１２１と、主経路表１２２とを備える。主経路表１２２は、経路情報を記録したデータテーブルである。次に、ルーティング処理部１２１は、主経路表１２２に基づいて受信されたパケットの転送処理を行う。
【００９４】
次に、代替経路表管理部１３の説明を行う。代替経路表管理部１３は、第１実施形態と同様である。すなわち、代替経路表管理部１３は、代替経路表記憶部１３１と、経路表更新部１３２とを備える。代替経路表記憶部１３１は、代替経路表１３１１〜１３１ｎを記録しており、代替経路表１３１１〜１３１ｎは、通信ネットワーク内で障害が発生したときに、主経路表に記録された経路情報を更新するための代替経路情報を記録している。経路表更新部１３２は、トポロジー情報交換部１１１から障害通知を入力すると、代替経路表１３１１〜１３１ｎを用いて主経路表１２２を更新する。
【００９５】
以上が、本実施形態における通信ネットワークの構成の説明である。このように、本実施形態において各ノード１の接続リンク代替経路表判定部１１５は、ＩＦ２１〜２ｎに接続されたリンク３１〜３ｎのみに対して代替経路表１３１１〜１３１ｎを作成するべきか否かを判定する。また、代替経路計算部１１４は、接続リンク代替経路表判定部１１５の判定結果において、代替系経路表１３１１〜１３１ｎを作成するべきと判定されたリンクと、作成指示受信部１４２の受信した他のノードからの作成指示メッセージに含まれるネットワークアドレスに対応するリンクとにそれぞれ対応する代替経路表１３１１〜１３１ｎのみを作成する。そのため、接続リンク代替経路表判定部１１５、及び代替経路表計算部１１４の計算量を抑えることができ、また、代替経路表１３１１〜１３１ｎを記憶する代替経路表記憶部１３１のメモリ容量も抑えることが可能となる。
【００９６】
［動作方法の説明］
次に、本実施形態における通信ネットワークの動作方法の説明を行う。はじめに、図９を用いて、本実施形態における代替経路表を作成する動作方法の説明を行う。図９は、本実施形態における代替経路表を作成する動作フローを示している。
【００９７】
（ステップＳ５０）
接続リンク代替経路表判定部１１５は、ＩＦ２１〜２ｎに接続されているリンク３１〜３ｎのうちから、本動作方法による判定処理を行っていない任意のリンク（以下、選択接続リンク）を一つ選択する。接続リンク代替経路表判定部１１５は、選択接続リンクを、ｅｋとする。
【００９８】
（ステップＳ５１）
代替経路計算部１１４は、接続リンク代替経路表判定部１１５によって選択された選択接続リンクｅｋに障害が発生したと想定した場合に主経路表１２２へ記録されるべき代替経路情報を計算する。代替経路計算部１１４は、計算された代替経路情報をリンクｅｋに対応する代替経路表１３１１〜１３１ｎに記録する。なお、本ステップでは、選択接続リンクｅｋに障害が発生したときに、選択接続リンクｅｋの障害発生前後でリーフノードに対する経路情報に変更が発生するか否かを判定していない。これは、図５Ｂで説明を行ったとおり、自ノードに近いリンクであればあるほど障害時に自ノードの経路情報に影響を及ぼす可能性が高く、まして、選択接続リンクｅｋは、自ノードに直接接続されたリンクであるため、選択接続リンクｅｋの障害時には、必ず主経路表１２２の経路情報を更新する必要があると考えられるためである。なお、第１実施形態で説明を行ったとおり、選択接続リンクｅｋに対して主経路表１２２の経路情報を更新する必要あるか否かを判定する動作方法としてもよい。
【００９９】
（ステップＳ５２）
代替経路計算部１１４は、選択接続リンクｅｋの代替経路情報の計算過程で生成する最短パスツリー（以下、障害時最短パスツリー）を、接続リンク代替経路表判定部１１５へ出力する。
【０１００】
（ステップＳ５３）
接続リンク代替経路表判定部１１５は、主経路計算部１１２から、主経路表１２２へ記録するべき経路情報の計算過程で生成する最短パスツリーを取得する。この最短パスツリーは、通信ネットワーク内の全てのリンクに障害が発生してない状態で生成されたものである。
【０１０１】
（ステップＳ５４）
接続リンク代替経路表判定部１１５は、代替経路計算部１１４から取得した障害時最短パスツリーと、主経路計算部１１２から取得した最短パスツリーとに基づいて、通信ネットワーク内に存在する他のノード１のうちで、代替経路情報の計算が必要となるノード（以下、計算指定ノード）を特定する。なお、計算指定ノードの特定方法は、後述する。
【０１０２】
（ステップＳ５５）
接続リンク代替経路表判定部１１５は、接続選択リンクｅｋに対する代替経路表の作成を指示する作成指示メッセージを生成して、作成指示通信部１４の作成指示送信部１４１へ出力する。作成指示送信部１４１は、作成指示メッセージを、計算指定ノードへパケット転送部１２を介して送信する。
【０１０３】
（ステップＳ５６）
接続リンク代替経路表判定部１１５は、リンク３１〜３ｎの全てに対して、本動作方法による判定処理を行ったかを判定する。全てのリンク３１〜３ｎに大して判定処理が完了していない場合、新たに任意の選択接続リンクｅｋに対する判定処理を行うために、ステップＳ５０へもどる。一方、全てのリンク３１〜３ｎに対して判定処理を行った場合、本動作方法は終了となる。
【０１０４】
以上が、本実施形態における代替経路表を作成する動作方法の説明である。本実施形態では、このようにしてリンク３１〜３ｎから選択された接続選択リンクｅｋに対応する代替経路表１３１１〜１３１ｎが作成され、また、選択接続リンクｅｋに対応する代替経路表１３１１〜１３１ｎを作成する必要のある計算指定ノードを特定して、計算指定ノードへ選択接続リンクｅｋに対応する代替経路表１３１１〜１３１ｎを作成するように作成指示メッセージを送信する。
【０１０５】
次に、本実施形態における選択接続リンクｅｋに対応する代替経路表１３１１〜１３１ｎを作成する必要のあるノード（計算指定ノード）の特定方法について説明を行う。本説明は、前述のステップＳ５４の動作方法を詳細に説明するものである。図１０は、本実施形態における計算指定ノードを特定する動作フローである。
【０１０６】
（ステップＳ６０）
接続リンク代替経路表判定部１１５は、前述のステップＳ５０で選択された選択接続リンクｅｋにおいて、自ノード（以下、本説明においてノードｒ）を終点とする逆方向の最短パスツリーＴＲを生成する。
【０１０７】
（ステップＳ６１）
接続リンク代替経路表判定部１１５は、計算指定ノードの集合である集合Ｖｕを生成してＶｕを初期化する。
【０１０８】
（ステップＳ６２）
接続リンク代替経路表判定部１１５は、ステップＳ５３で取得した、主経路表１２２に記録されている現在の（選択接続リンクｅｋに障害発生前の）最短パスツリー（以下、最短パスツリーＴ）に基づいて、当該経路情報において、次転送先が選択接続リンクｅｋを介して接続している宛先ノードを処理対象として抽出する。つまり、ここでは、主経路表１２２に記録された宛先ノードのうちで、選択接続リンクｅｋに障害が発生することにより、次転送先の変更が必要となる宛先ノードが処理対象となる。接続リンク代替経路表判定部１１５は、抽出された処理対象のノード（以下、処理対象ノード）のうちから、本動作方法における以降の処理を実行していない任意のノードｄを選択する。
【０１０９】
（ステップＳ６３）
接続リンク代替経路表判定部１１５は、前述のステップＳ５２で取得した障害時最短パスツリー（以下、障害時最短パスツリーＴｉ）に基づいて、ノードｒ（自ノード）からノードｄまでのパスを抽出する。接続リンク代替経路表判定部１１５は、抽出されたパスにおいて、自ノードｒの次のノードを特定し、ノードｎとする。
【０１１０】
（ステップＳ６４）
接続リンク代替経路表判定部１１５は、障害時最短パスツリーＴｉにおけるノードｒからノードｄまでのパスのコストから障害前の最短パスツリーＴにおけるノードｒからノードｄまでのパスのコストを減算した値Ｃｄを計算する。
【０１１１】
（ステップＳ６５）
接続リンク代替経路表判定部１１５は、障害前の最短パスツリーＴにおけるノードｒからノードｎまでのパスのコストと、逆方向の最短パスツリーＴＲにおけるノードｎからノードｒまでのパスのコストとを合計した値Ｃｎを計算する。
【０１１２】
（ステップＳ６６）
接続リンク代替経路表判定部１１５は、ＣｎとＣｄとの値の大小を比較する。ＣｎがＣｄ以下の場合、ステップＳ６７へ進む。一方、ＣｎがＣｄより大きい場合、ステップＳ６９へ進む。
【０１１３】
（ステップＳ６７）
接続リンク代替経路表判定部１１５は、ＣｎがＣｄ以下の場合、ノードｎを、代替経路表の作成が必要な指定計算ノードであると特定する。接続リンク代替経路表判定部１１５は、ノードｎを集合Ｖｕへ追加する。
【０１１４】
（ステップＳ６８）
接続リンク代替経路表判定部１１５は、障害時最短パスツリーＴｉに基づいて、ノードｒからノードｄへのパスにおいて、ノードｎの次に位置するノードを特定して、当該ノードをノードｎとする。この後、ステップＳ６５へ戻る。
【０１１５】
（ステップＳ６９）
接続リンク代替経路表判定部１１５は、ＣｎがＣｄより大きい場合、ステップＳ６２で抽出した全ての処理対象ノードに対する判定処理が完了したかを判定する。全ての処理対象ノードに対して判定処理が完了していない場合、新たなノードｄを選択するために、ステップＳ６２へ戻る。一方、全ての処理対象ノードに対して判定勝利が完了している場合、本動作フローは終了となる。この時点で、集合Ｖｕに含まれているノードが代替経路表の作成が必要と判断された計算指定ノードとなる。
【０１１６】
以上が、本実施形態における計算指定ノードの特定方法について説明を行う。本実施形態において、計算指定ノードはこのようにして計算される。なお、計算指定ノードの特定方法は、上述した方法に限定はしない。
【０１１７】
次に、本実施形態において、他のノードから作成指示メッセージを受信した場合の動作方法の説明を行う。図１１は、本実施形態における他のノードから作成指示メッセージを受信した場合の動作フローを示している。
【０１１８】
（ステップＳ７０）
作成指示受信部１４２は、パケット転送部１２を介して他ノードのから作成指示メッセージを受信する。代替経路表計算部１１４は、作成指示メッセージに格納された代替経路表１３１１〜１３１ｎを作成するべきリンクに関する情報を抽出する。
【０１１９】
（ステップＳ７１）
代替経路表計算部１１４は、作成指示メッセージから抽出されたリンクに対して、当該リンクに障害が発生した場合に使用される代替経路情報を計算する。
【０１２０】
（ステップＳ７２）
代替経路表計算部１１４は、代替経路表記憶部１３１の作成指示メッセージから抽出されたリンクに対応する代替経路表１３１１〜１３１ｎへ、計算された代替経路情報を記録する。
【０１２１】
以上が、他のノードから作成指示メッセージを受信した場合の動作方法の説明である。このようにして、受信された作成指示メッセージに格納されたリンクに対応する代替経路表１３１１〜１３１ｎが作成される。
【０１２２】
以上が、本実施形態における通信ネットワークの説明である。
【０１２３】
ここまで、本発明の通信ネットワークの説明を行ってきた。本発明の通信ネットワークの第１実施形態によれば、通信ネットワークを構成する各ノード１において、代替経路表判定部１１３が、通信ネットワーク内に存在するリンクに対して、代替経路表１３１１〜１３１ｎを作成するか否かを判定する。代替経路表計算部１１４は、代替経路表１３１１〜１３１ｎを作成すると判定されたリンクに対応する代替経路表１３１１〜１３１ｎのみを作成する。そのため、代替経路表計算部１１４の計算量を抑えることができ、また代替経路表１３１１〜１３１ｎを記憶する代替経路記憶部１３１のメモリ容量も抑えることができる。
【０１２４】
また、本発明の通信ネットワークの第２実施形態によれば、各ノード１は、自ノード１に接続されたリンクについてのみ代替経路表１３１１〜１３１ｎを作成するか否かを判定する。また、本実施形態では各ノード１が自ノード１のみではなく、他のノード１が代替経路表を作成するべきリンクを特定して、当該リンクを他のノード１に通知する。これにより、各ノード１は、自ノード１に接続されたリンクに対する判定処理を行って、代替経路表１３１１〜１３１ｎの作成が必要と判定されたリンクに対する代替経路表１３１１〜１３１ｎの作成し、また、他のノード１から通知を受けた代替経路表１３１１〜１３１ｎを作成するべきリンクに対する代替経路表１３１１〜１３１ｎとを作成すればよいため、代替経路表１３１１〜１３１ｎを計算する計算量、及び代替経路表１３１１〜１３１ｎを記憶するメモリ量を抑えることが可能となる。
【０１２５】
第１実施形態、及び第２実施形態は、それぞれ独立してのみ実施可能ではない。それぞれ組み合わせて実現することも可能である。また、各実施形態では、リンクに障害が発生した場合のみを説明しているが、ノードに障害が発生した場合にも、適用が可能である。この場合、各ノードに対応した代替経路表が作成される。また、図４では、ステップＳ２１において抽出したパス中に含まれるリンクに対して処理を行っている。ノード障害を扱う場合には、ステップＳ２２において各リンクを「ｅ１，ｅ２，・・・ｅｍ」とする代わりに、パス中に含まれる各ノードをそれぞれ「ｎ１,ｎ２・・・ｎｍ」して以降の処理を行う。つまり、パス中の各リンクを対象とする代わりに、パス中の各ノードを対象として処理を行えばよい。また、図６では、ステップＳ４１において、リンクｅｋに障害の発生を想定しているが、これをノードｎｋおよびノードｎｋに接続される全てのリンクに障害が発生したと想定して経路情報を作成すればよい。また、実際に使用する代替経路表を作成する際も、ノードｎｋおよびノードｎｋに接続される全てのリンクに障害が発生したと想定した経路情報を作成すればよい。さらに、作成指示メッセージには、「Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ」フィールド７０の代わりに、ノードｎｋを一意に識別することが可能な情報を格納する。ノードｎｋを一意に識別することが可能な情報とは、例えば、ノードｎｋのＩＰアドレスである。このような、変更を行うことで、本願発明をノード障害に適応することが可能である。つまり、本発明は、ノードとリンクを含む通信ネットワークを構成するネットワークリソースに対して適用が可能である。
【０１２６】
また、代替経路表記憶部１３１は、通信ネットワークのトポロジーの変化に伴い、代替経路表１３１１〜１３１ｎが不要となった場合に、不要になった代替経路表１３１１〜１３１ｎ、あるいは、不要になった代替経路表１３１１〜１３１ｎ記録された代替経路情報を削除しても構わない。これにより、メモリ容量をより抑えることが可能となる。
【０１２７】
なお、本発明の通信ネットワークが備える各ネットワークノードは、実行するべき機能をハードウェアによっても実現可能であるし、ソフトウェアによっても実現可能である。ソフトウェアで実現される場合には、各ネットワークノードへ導入されるコンピュータプログラムは、例えばＣＤ−Ｒ（Ｃｏｍｐａｃｔ Ｄｉｓｃ Ｒｅｃｏｒｄａｂｌｅ）やＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）のような情報記録媒体に記録することが可能である。コンピュータプログラムは、このような記録媒体を用いて、各ネットワークノードへの導入が可能である。
【０１２８】
以上、実施形態を参照して本願発明を説明したが、本願発明は、上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明の範囲内で当業者が理解し得る様々な変更を行うことが可能である。
【符号の説明】
【０１２９】
１ ノード
１１ 経路制御部
１２ パケット転送部
１３ 代替経路表管理部
１４ 作成指示通信部
２１〜２ｎ ネットワークインターフェイス
３１〜３ｎ リンク
４１ 宛先
４２ マスク長
４３ 次転送先
４４ インターフェイス
５１ 宛先
５２ マスク長
５３ 次転送先
５４ インターフェイス
６０ ルートノード
６１−１〜５ リーフノード
６２ パス
７０ Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ フィールド（作成指示メッセージ）
７１ Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋ フィールド（作成指示メッセージ）
７２ Ｌｉｎｋ Ｓｔａｔｅ ＩＤフィールド（Ｎｅｔｗｏｒｋ ＬＳＡ）
７３ Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋフィールド（Ｎｅｔｗｏｒｋ ＬＳＡ）
１１１ トポロジー情報交換部
１１２ 主経路計算部
１１３ 代替経路表判定部
１１４ 代替経路表計算部
１１５ 接続リンク代替経路表判定部
１２１ ルーティング処理部
１２２ 主経路表
１３１ 代替経路表記憶部
１３２ 経路表更新部
１４１ 作成指示送信部
１４２ 作成指示受信部
１３１１〜１３１ｎ 代替経路表
【技術分野】
【０００１】
本発明は、動的に経路制御を行う通信ネットワークにおいて高速に経路切替を行う技術に関する。
【背景技術】
【０００２】
通信ネットワークの安定性向上が急務となっている。インターネットに代表される通信ネットワーク技術が広く普及するのに伴い、通信ネットワークの障害が社会へ与える影響度も増している。
【０００３】
通信ネットワークは、データを転送するネットワークノード（以下、ノード）と、ノード間を接続するリンクとで構成される。通常、通信ネットワークは、通信ネットワークを構成するネットワークリソースであるノードとリンクを冗長構成にすることでネットワークの信頼性の向上を計っている。動的に経路制御を行う通信ネットワークでは、各ノードにおいて最適な経路情報を制御する経路制御プロトコルが動作している。このような動的経路制御を行うネットワークにおいて各ノードは、通信ネットワークを構成する他のノードとの間で経路情報を交換して、取得された経路情報に基づいて最適な経路情報を自律的に形成する。例えば、自ノードに接続されたリンクや当該リンクを介して接続されるノードに障害が発生した場合、障害を検知したノードは、他のノードに障害を通知する。障害を通知されたノードは、障害の発生したノード、あるいはリンクを除いた状態で経路計算を行い、新たな経路情報を決定する。このように、動的経路制御を行う通信ネットワークは、通信ネットワーク内に障害が発生しても、他のノードやリンクを用いたデータ転送経路を自律的に形成することより通信を継続することを可能としている。
【０００４】
動的経路制御を行う経路制御プロトコルの一つとして、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）が知られている（非特許文献１）。ＯＳＰＦは、ＩＥＴＦ（Ｉｎｔｅｒｎｅｔ Ｅｎｇｉｎｅｅｒｉｎｇ Ｔａｓｋ Ｆｏｒｃｅ）で標準化されている代表的なリンクステートアルゴリズムである。ＯＳＰＦが動作する通信ネットワークにおいて、各ノードは、互いに、ネットワークのトポロジー情報を交換し合う。このトポロジー情報は、通信ネットワーク内のノードやリンクの接続関係を示しており、各ノードは、トポロジー情報に基づいて経路情報を計算する。各ノードは、トポロジー情報に基づいて計算された経路情報により、受信されるパケットの宛先に対する最適な次転送先を決定することができる。
【０００５】
通信ネットワーク内のノードやリンクに障害が発生した場合、以下のフェーズで通信の復旧が行われる。まず、障害の発生したノードやリンクに隣接するノードがその障害を検知する障害検知フェーズ。次に、検知した障害を通信ネットワーク中の他のノードへ通知する通知フェーズ。さらに、障害発生後のトポロジーに基づいて、転送経路の再計算を行う経路計算フェーズ。そして、各ノードが、経路計算結果を経路表へ更新する経路表更新フェーズ。以上の４つのフェーズである。通信ネットワークの安定のためには、障害の発生を検知してから各ノードの経路表が更新されるまでの時間が短いほうがよい。しかし、通信ネットワークが大規模になると、前述の経路計算フェーズに時間がかかってしまうために、通信の復旧までに長い時間を要してしまう。そこで、障害発生から通信復旧までの時間を短縮するために、通信ネットワーク中のリンクもしくはノードに障害が発生した場合に備えて、各ノードが、予め障害時に使用する経路表を計算して、代替経路表として保持しておく技術が以下の通り検討されている。
【０００６】
特許文献１は、代替経路のループ判定を行い、ループとならない経路のみを用いる高速経路切替方式を開示している。特許文献１の高速経路切替方式を実施するルータ装置は、ネットワークインターフェイスと、パケット転送部と、主経路計算部と、代替経路表計算部と、切替部とを少なくとも備え、さらにループ経路判定部を備える。ネットワークインターフェイスは、他のルータと接続される。パケット転送部は、予め主経路表に格納された経路情報に基づいてネットワークインターフェイス経由で受信したパケットのルーティング処理を行う。主経路計算部は、主経路表に格納する経路情報を計算する。代替経路表計算部は、ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の障害を検知したときに使用する代替経路を計算して代替経路表に格納する。ネットワークインターフェイスに接続するリンクもしくは隣接するルータ装置の障害を検知したときに代替経路表に格納されている経路情報への入替処理を行う。ループ経路判定部は、代替経路表計算部により代替経路表に代替経路情報を格納する際に代替経路がループとなるか否かの判定を行って、ループとならないと判定された代替経路を代替経路表に格納する。
【０００７】
特許文献１の高速経路切替方式によれば、リンク障害時の高速経路切替を行う際にループとなる経路を切り替え対象から除外することができ、転送パケットのループの発生を防止し、ルータ装置の負荷を軽減しつつ、高速経路切替が実現できる。
【０００８】
しかし、このような高速切替方式においては、各ノードが障害の可能性のある全てのノード及びリンクに対応する代替経路表を予め用意しておくことになり、代替経路表を計算する計算量、および、代替経路表を保持しておくための記憶メモリの容量の点から現実的ではなかった。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００６−２７９４８２号公報
【非特許文献】
【００１０】
【非特許文献１】”OSPF Version2”,J.Moy,RFC2328,InternetEngineering Task Force,April 1998
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明の目的は、障害時に備えて保持される代替経路表を計算するための計算量、及び、記憶するためのメモリサイズを抑えつつ高速に通信経路の切り替えを行うことが可能な通信ネットワークを提供することである。
【課題を解決するための手段】
【００１２】
本発明の通信ネットワークは、複数のネットワークノードを具備する通信ネットワークであって、複数のネットワークノードの各々は、複数のインターフェイスと、通信ネットワークにおける経路情報を記録した主経路表と、主経路表に基づいて複数のインターフェイスから入力されるパケットを転送するルーティング処理部と、通信ネットワークを構成するネットワークリソースに対応して設けられて、ネットワークリソースの障害時に主経路表に記録された経路情報のうちで更新されるべき経路情報の代替経路情報を記録した代替経路表を記憶する代替経路表記憶部と、ネットワークリソースは、複数のネットワークノード、および複数のネットワークノードの間を接続するリンクを含み、ネットワークリソースのうちから選択する選択ネットワークリソースに障害が発生したときに、主経路表の経路情報の更新が必要であるか否かに基づいて、選択ネットワークリソースに対応する代替経路表を作成するか否かを決定する代替経路表判定部と、代替経路表を作成すると決定された選択ネットワークリソースに対応する選択代替経路表に記録されるべき代替経路情報を計算する代替経路表計算部と、障害を検知すると障害の発生したネットワークリソースに対応する代替経路表に記録された代替経路情報を用いて主経路表の経路情報を更新する経路表更新部とを備える。
【００１３】
本発明のネットワークノードは、上述の通信ネットワークを構成する。
【００１４】
本発明の通信経路制御方式は、複数のネットワークノードを具備する通信ネットワークにおいて、通信ネットワークにおける経路情報を記録するステップと、主経路表に基づいて複数のインターフェイスから入力されるパケットを転送するステップと、通信ネットワークを構成するネットワークリソースに対応して設けられて、ネットワークリソースの障害時に主経路表に記録された前記経路情報のうちで更新されるべき経路情報の代替経路情報を記録した代替経路表を記憶するステップと、ネットワークリソースは、複数のネットワークノード、および複数のネットワークノードの間を接続するリンクを含み、ネットワークリソース選択する選択ネットワークリソースに障害が発生したときに、主経路表の経路情報の更新が必要であるか否かに基づいて、選択ネットワークリソースに対応する代替経路表を作成するか否かを決定するステップと、代替経路表を作成すると決定されたネットワークリソースに対応する選択代替経路表に記録されるべき代替経路情報を計算するステップと、障害を検知すると障害の発生したネットワークリソースに対応する代替経路表に記録された代替経路情報を用いて主経路表の経路情報を更新するステップとを備える。
【００１５】
本発明のコンピュータプログラムは、上述の通信経路制御方式をコンピュータに実行させる。
【発明の効果】
【００１６】
本発明によれば、障害時に備えて保持される代替経路表を計算するための計算量、及び、記憶するためのメモリサイズを抑えつつ高速に通信経路の切り替えを行うことが可能な通信ネットワークを提供することができる。
【図面の簡単な説明】
【００１７】
【図１】第１実施形態におけるノード１の構成を示す図である。
【図２Ａ】第１実施形態における主経路表１２２の一例を示す図である。
【図２Ｂ】第１実施形態における代替経路表１３１１〜１３１ｎの一例を示す図である。
【図３】第１実施形態における代替経路表を作成する動作フローを示している。
【図４】第１実施形態における代替経路表１３１１〜１３１ｎを作成するべきリンクを抽出する動作フローである。
【図５Ａ】第１実施形態における主経路計算部１１２の生成した最短パスツリーの一例を示す図である。
【図５Ｂ】第１実施形態における代替経路表判定部１１３が最短パスツリーから抽出したパス６２を示す図である。
【図６】第１実施形態におけるリンクｅｋの障害時に主経路表１２２の経路情報の更新が必要であるか否かを判定する動作フローである。
【図７】第２実施形態におけるノード１の構成を示す図である。
【図８Ａ】第２実施形態における作成指示メッセージのペイロードを示す図である。
【図８Ｂ】従来のＯＳＰＦにおける「Ｎｅｔｗｏｒｋ ＬＳＡ」のペイロードの構成を示す図である。
【図９】第２実施形態における代替経路表を作成する動作フローである。
【図１０】第２実施形態における計算指定ノードを特定する動作フローである。
【図１１】第２実施形態における他のノードから作成指示メッセージを受信した場合の動作フローを示している。
【発明を実施するための形態】
【００１８】
添付図面を参照して、本発明の実施形態による通信ネットワークを以下に説明する。
【００１９】
（第１実施形態）
はじめに、本発明の第１実施形態における通信ネットワークの説明を行う。
【００２０】
本実施形態の通信ネットワークは、通信ネットワークを構成する各ネットワークノード（以下、ノード）が、通信ネットワーク内に存在する各ノード間を接続するリンクの障害に備えて、各リンクに障害が発生した場合に使用するべき代替経路表を、各リンクに対応させて予め作成しておく。各ノードは、障害発生時において、障害の発生したリンクに対応する代替経路表を用いて、通常時に使用される主経路表を更新する。各ノードは、代替経路表を作成するときに、当該リンクに障害が発生したと想定した場合に、主経路表に記録された経路情報の更新が必要となるか否かを判定する。各ノードは、この判定において、主経路表の更新が必要と判定された場合にのみ、当該リンクに対応する代替経路表を作成する。このように、各ノードは、必要と判定された代替経路表のみを作成するため、代替経路表を計算する計算量、及び代替経路表を記憶するメモリ量を抑えることが可能となる。
【００２１】
［構成の説明］
まず、本実施形態における通信ネットワークを構成するノードの構成を説明する。図１は、本実施形態におけるノード１の構成を示す図である。本実施形態のノード１は、経路制御部１１と、パケット転送部１２と、代替経路表管理部１３と、ネットワークインターフェイス（以下、ＩＦ）２１〜２ｎを備える。
【００２２】
本実施形態の通信ネットワークは、図１に示すようなノード１を複数備えており、各ノード１は、ＩＦ２１〜２ｎに接続されたリンク３１〜３ｎにより他のノードと接続されて通信ネットワークを構成する。
【００２３】
はじめに、パケット転送部１２の説明を行う。パケット転送部１２は、ルーティング処理部１２１と、主経路表１２２とを備える。
【００２４】
まず、主経路表１２２は、経路情報を記録したデータテーブルである。図２Ａは、本実施形態における主経路表１２２の一例を示す図である。図２Ａを参照すると、主経路表１２２は、宛先４１、マスク長４２、次転送先４３、及びインターフェイス４４を一組に対応させて記録している。宛先４１は、ノード１が受信するパケットのヘッダに記録された宛先ＩＰ（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ）アドレスと対応されるべきネットワークアドレスである。マスク長４２は、宛先４１のネットワークアドレスにおけるサブネットマスクである。次転送先４３は、宛先４１のネットワークアドレスに対応する受信パケットの転送先のノード１のＩＰアドレスである。インターフェイス４４は、次転送先４３がリンクを介して接続されているＩＦ２１〜２ｎの番号である。なお、図２Ａは、ＩＰｖ４の場合を示しているが、これはＩＰｖ６であっても良い。
【００２５】
次に、ルーティング処理部１２１は、受信されたパケットの転送処理を行う。ルーティング処理部１２１は、ＩＦ２１〜２ｎを介して受信されたパケットのヘッダに格納された宛先ＩＰアドレスと、主経路表１２２の宛先４１及びマスク長４２とを参照して次転送先４３を特定する。ルーティング処理部１２１は、特定された次転送先４３に対応するインターフェイス４４へパケットを送出する。
【００２６】
次に、経路制御部１１の説明を行う。経路制御部１１は、トポロジー情報交換部１１１と、主経路計算部１１２と、代替経路表判定部１１３と、代替経路表計算部１１４とを備える。
【００２７】
まず、トポロジー情報交換部１１１は、ＯＳＰＦなどの経路制御プロトコルを使用して、隣接ノードとの間でトポロジー情報の交換を行う。ここで、トポロジー情報とは、通信ネットワーク内に存在するノードと、ノード間を接続するリンクとがどのような接続関係となっているかを示す情報である。また、隣接ノードとは、ＩＦ２１〜２ｎに接続されたリンク３１〜３ｎを介して接続されたノードである。トポロジー情報交換部１１１は、取得したトポロジー情報を、主経路計算部１１２、代替経路表判定部１１３、及び代替経路表計算部１１４とへ出力する。
【００２８】
また、トポロジー情報交換部１１１は、障害通知を送受信する。障害通知は、リンク３１〜３ｎに障害が発生した場合や、ノード１内に障害が発生した場合に、トポロジー情報交換部１１１によりパケット転送部１２を介して隣接ノードへ送信される。トポロジー情報交換部１１１は、障害通知を受信すると通信ネットワーク内の障害を検知して、通信ネットワーク内のトポロジーに変化が発生したことを検知する。トポロジー情報交換部１１１は、障害発生前後における通信ネットワークのトポロジー情報の変化分を抽出して、隣接ノードへ通知する。また、トポロジー情報交換部１１１は、障害通知を主経路計算部１１２と、代替経路表判定部１１３と、代替経路表計算部１１４と、経路表更新部１３２へ出力する。
【００２９】
なお、トポロジー情報交換部１１１は、トポロジー情報や障害通知を、パケット転送部１２と、ＩＦ３１〜３ｎとを介して隣接ノード１と交換する。
【００３０】
次に、主経路計算部１１２は、主経路表１２２へ記録するべき経路情報を計算する。主経路計算部１１２は、トポロジー情報交換部１１１からトポロジー情報を入力すると、トポロジー情報に基づいて経路情報を計算して、主経路表１２２の経路情報を更新する。主経路計算部１１２は、一般的なＩＧＰ（Ｉｎｔｅｒｉｏｒ Ｇａｔｅｗａｙ Ｐｒｏｔｏｃｏｌ）を用いて経路情報を計算する。ＩＧＰには、前述したＯＳＰＦが含まれる。
【００３１】
次に、代替経路表判定部１１３は、代替経路表を作成するべきか否かを判定する。代替経路表判定部１１３は、通信ネットワーク中の全てのリンクに対して、各リンクに障害が発生した場合に、各リンクに対応する代替経路表を作成するべきか否かを判定する。代替経路表判定部１１３は、トポロジー情報取得部１１１からトポロジー情報を入力したとき、あるいは、所定の時間毎に、各リンクに対応する代替経路表を作成するべきか否かの判定を行う。代替経路表判定部１１３は、判定結果を代替経路表計算部１１４へ通知する。判定結果は、代替経路表を作成するべきと判定されたリンクを含んでいる。
【００３２】
次に、代替経路表計算部１１４は、代替経路情報を計算する。代替経路表計算部１１４は、代替経路表判定部１１３から判定結果を入力すると、判定結果に含まれるリンクに対応する代替経路表に記録するべき代替経路情報を計算する。代替経路表計算部１１４は、代替経路情報を計算するべきリンクに、障害が発生したと想定して、代替経路情報を計算する。代替経路表計算部１１４は、後述する代替経路表管理部１３の代替経路表記録部１３１において、代替経路情報の計算されたリンクに対応した代替経路表へ計算された代替経路情報を記録する。
【００３３】
次に、代替経路表管理部１３の説明を行う。代替経路表管理部１３は、代替経路表記憶部１３１と、経路表更新部１３２とを備える。
【００３４】
まず、代替経路表記憶部１３１は、代替経路表１３１１〜１３１ｎを記録している。代替経路表１３１１〜１３１ｎは、通信ネットワーク内で障害が発生したときに、主経路表に記録された経路情報を更新するための代替経路情報を記録している。代替経路表１３１１〜１３１ｎは、通信ネットワークに存在する各リンクに対応して設けられる。本実施形態において代替経路表記憶部１３１は、通信ネットワークに存在する全てのリンクに対応する代替経路表１３１１〜１３１ｎを記憶しているわけではない。代替経路表記憶部１３１は、代替経路表判定部１１３の判定結果に基づいて、代替経路表１３１１〜１３１ｎを作成するべきと判定されたリンクに対応する代替経路表１３１１〜１３１ｎのみが記憶されている。
【００３５】
図２Ｂは、本実施形態における代替経路表１３１１〜１３１ｎの一例を示す図である。代替経路表１３１１〜１３１ｎは、主経路表１２２と同様の項目が記録されている。すなわち、代替経路表１３１１〜１３１ｎは、宛先５１、マスク長５２、次転送先５３、インターフェイス５４の項目を備える。これらはそれぞれ、主経路表１２２における宛先４１、マスク長４２、次転送先４３、インターフェイス４４の各項目と同様であるので重ねての説明を省略する。
【００３６】
経路表更新部１３２は、代替経路表１３１１〜１３１ｎを用いて主経路表１２２を更新する。経路表更新部１３２は、経路制御部１１のトポロジー情報交換部１１１から障害通知を入力する。経路表更新部１３２は、通信ネットワーク内の特定のリンクに障害が発生したことを検知すると、障害の発生したリンク（以下、障害リンク）に対応する代替経路表（以下、選択代替経路表）を代替経路表記憶部１３１から特定して、選択代替経路表を用いて主経路表１２２を更新する。すなわち、主経路表１３１の経路情報は、障害リンクに対応する選択代替経路表に記録された代替経路情報により更新される。
【００３７】
なお、経路表更新部１３２は、主経路表１２２に記録された経路情報のうち、選択代替経路表に記録された代替経路情報に対応する経路情報のみを更新する。例えば、図２Ｂを選択代替経路表として説明すると、図２Ｂに、宛先５１として、「１９２．１６８．１．０」と「１９２．１６８．１２．０」のみが記録されているとする。この場合、図２Ａの主経路表１２２では、「１９２．１６８．１．０」と「１９２．１６８．１２．０」に対応する情報のみが更新される。そのため、主経路表１２２における宛先４１「１９２．１６８．１０．０」や、その他の図示されない宛先４１については更新されない。宛先４１「１９２．１６８．１０．０」は、この情報のまま、主経路表１２２に残ることになり、このままルーティング処理部１２１により使用される。
【００３８】
以上が、本実施形態における通信ネットワークの構成の説明である。本実施形態では、経路制御部１１の代替経路表判定部１１３が、通信ネットワーク内の各リンクに対して、代替経路表１３１１〜１３１ｎを作成するべきか否かを判定する。代替経路表計算部１１４は、代替経路表１３１１〜１３１ｎを作成すべきと判定されたリンクに対応する代替経路表１３１１〜１３１ｎのみを作成して、代替経路表管理部１３の代替経路表記憶部１３１へ記憶させる。このように、必要と判定された代替経路表１３１１〜１３１ｎのみを作成して、また、記憶するので、代替経路表計算部１１４の計算量を抑えることができ、また、代替経路表記憶部１３１のメモリ容量も抑えることが可能となる。
【００３９】
［動作方法の説明］
次に、本実施形態における通信ネットワークの動作方法の説明を行う。はじめに、図３を用いて、本実施形態における代替経路表を作成する動作方法の説明を行う。図３は、本実施形態における代替経路表を作成する動作フローを示している。
【００４０】
（ステップＳ１０）
代替経路表判定部１１３は、ネットワーク中の全リンクのうちから、代替経路表１３１１〜１３１ｎを作成するべきリンクを抽出する。代替経路表判定部１１３は、抽出されたリンクの集合をＮｕとする。
【００４１】
（ステップＳ１１）
代替経路表計算部１１４は、集合Ｎｕに含まれる各リンクに対して、当該リンクに障害が発生したと想定して代替経路情報を計算する。
【００４２】
（ステップＳ１２）
代替経路表計算部１１４は、計算された代替経路情報を、代替経路表管理部１３の代替経路記憶部１３１の対応する代替経路表１３１１〜１３１ｎへ記録する。
【００４３】
以上が、本実施形態における代替経路表を作成する動作方法の説明である。このようにして、代替経路表１３１１〜１３１ｎは作成され、代替経路表記憶部１３１へ記憶される。
【００４４】
次に、本実施形態における代替経路表１３１１〜１３１ｎを作成するべきリンクを抽出する動作方法を説明する。本動作方法は、前述のステップＳ１０の詳細な動作方法を説明するものである。図４は、本実施形態における代替経路表１３１１〜１３１ｎを作成するべきリンクを抽出する動作フローを示している。
【００４５】
（ステップＳ２０）
代替経路表判定部１１３は、空集合ＮｕとＮｎとを生成する。集合Ｎｕは、代替経路表を作成するべきと判定されたリンクの登録されるべき集合である。一方、集合Ｎｎは、代替経路表を作成する必要はないと判定されたリンクの登録されるべき集合である。
【００４６】
（ステップＳ２１）
代替経路表判定部１１３は、最短パスツリーから、自ノードをルートノードとしてまだ以降の処理が行われていない任意のリーフノードへのパスを抽出する。代替経路表判定部１１３は、主経路計算部１１２から、最短パスツリーを取得する。ここで、最短パスツリーは、トポロジー情報に基づいて生成される有効グラフであり、主経路計算部１１２は、最短パスツリーを用いて主経路表１２２へ記録するべき経路情報を計算する。代替経路表判定部１１３は、最短パスツリーから、本ステップ以降の処理を行っていない任意のリーフノードを一つ選択する。ここで、リーフノードとは、最短パスツリーの末端に位置するノード１である。代替経路表判定部１１３は、最短パスツリーにおいて自ノードから選択されたリーフノードまでのパスを抽出する。
【００４７】
図５Ａは、本実施形態における主経路計算部１１２の生成した最短パスツリーの一例を示す図である。図５Ａにおいて、符号６０は、ルートノードである自ノードである。ここでルートノードとは、最短パスツリーの最上位のノード１である。図５Ａにおいて、符号６１−１〜５は、リーフノードである。代替経路表判定部１１３は、リーフノード６１−１を選択したとする。この場合、代替経路表判定部１１３は、ルートノード（自ノード）６０からリーフノード６１−１までのパス６２を抽出する。
【００４８】
（ステップＳ２２）
代替経路表判定部１１３は、最短パスツリーから抽出したパスにおいて、自ノードからリーフノードまで、自ノードから近い順にリンクを「ｅ１，ｅ２，ｅ３・・・ｅｍ」とする。
【００４９】
図５Ｂは、本実施形態における代替経路表判定部１１３が最短パスツリーから抽出したパス６２を示す図である。図５Ｂに示すように、ルートノード（自ノード）６０からリーフノード６１−１へ向けて、ルートノード６０に近い順にリンクが「ｅ１，ｅ２，ｅ３・・・ｅｍ」とされている。
【００５０】
（ステップＳ２３）
代替経路表判定部１１３は、変数ｉを生成して、ｉに「１」を代入する。
【００５１】
（ステップＳ２４）
代替経路表判定部１１３は、リンクｅｉが集合Ｎｕの要素であるか否かを判定する。つまり、代替経路表判定部１１３は、リンクｅｉが代替経路表を作成するべきと判定されたリンクの集合Ｎｕに含まれるか否かを判定する。リンクｅｉが集合Ｎｕの要素である場合、ステップＳ２５へ進む。一方、リンクｅｉが集合Ｎｕの要素でない場合、ステップＳ２６へ進む。
【００５２】
（ステップＳ２５）
代替経路表判定部１１３は、リンクｅｉが集合Ｎｕの要素である場合、ｉを「ｉ＝ｉ＋１」とインクリメントする。この後、ステップＳ２４へ戻る。
【００５３】
ステップＳ２４、Ｓ２５において、代替経路表判定部１１３は、自ノードに近いリンクｅｉから集合Ｎｕの要素であるか否かを判定している。図５Ｂを参照すると、代替経路表判定部１１３は、ルートノード（自ノード）６０に近いリンクから順に、リンクｅｉが代替経路表を作成するべきと判定されたリンクの集合Ｎｕに含まれるか否かを判定することになる。これは、自ノードに近いリンクほど、障害が発生した場合に自ノードへの影響が大きく、主経路表１２２に記録された経路情報を更新する必要性が高くなることによる。
【００５４】
（ステップＳ２６）
代替経路表判定部１１３は、リンクｅｉが集合Ｎｕの要素でない場合、変数ｊを生成して、ｊに「ｍ」を代入する。
【００５５】
（ステップＳ２７）
代替経路表判定部１１３は、リンクｅｊが集合Ｎｎの要素であるか否かを判定する。つまり、代替経路表判定部１１３は、リンクｅｊが代替経路表を作成する必要はないと判定されたリンクの集合Ｎｎに含まれるか否かを判定する。リンクｅｊが集合Ｎｎの要素である場合、ステップＳ２８へ進む。一方、リンクｅｊが集合Ｎｎの要素でない場合、ステップＳ２９へ進む。
【００５６】
（ステップＳ２８）
代替経路表判定部１１３は、リンクｅｍが集合Ｎｎの要素である場合、ｊを「ｉ＝ｊ−１」とデクリメントする。この後、ステップＳ２７へ戻る。
【００５７】
ステップＳ２７、Ｓ２８において、代替経路表判定部１１３は、自ノードに遠い（リーフノードに近い）リンクｅｊから集合Ｎｎの要素であるか否かを判定している。図５Ｂを参照すると、代替経路表判定部１１３は、リーフノード６１−１に近いリンクから順に、リンクｅｉが代替経路表を作成する必要はないと判定されたリンクの集合Ｎｎに含まれるか否かを判定することになる。これは、自ノードから遠い（リーフノードに近い）リンクほど、障害が発生した場合の自ノードへの影響が少なく、主経路表１２２に記録された経路情報を更新する必要性が低くなることによる。
【００５８】
（ステップＳ２９）
代替経路表判定部１１３は、リンクｅｉが集合Ｎｕの要素でない場合、変数ｋを生成して、現在のｉとｊとの相加平均をとってその値を超えない最大の整数を代入する。すなわち、代替経路表判定部１１３は、「ｋ＝［（ｉ＋ｊ）／２］」を計算する。
【００５９】
本ステップの時点で最短パスツリーから抽出されたパスに含まれるリンクのうち、「リンクｅｉ〜リンクｅｊ」に対して経路更新が必要であるか否かの判定が行われていない。前述したように、自ノードに近いリンクほど、当該リンク障害時に主経路表１２２の経路情報を更新する必要が高くなり、自ノードから遠いリンクほど、当該リンクの障害時に主経路表１２２の経路情報を更新する必要が低くなる。以下のステップにおいて、代替経路表判定部１１３は、特定のリーフノードへのパスにおいて、図５Ｂに示すように、特定のリンクの障害時に主経路表１２２の経路情報を更新する必要の有無の分岐点となるリンクを探す処理を行う。
【００６０】
（ステップＳ３０）
代替経路表判定部１１３は、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要であるか否かを判定する。本ステップの詳細な動作は、後述する。経路情報の更新が必要である場合、ステップＳ３１へ進む。一方、経路情報の更新が必要でない場合、ステップＳ３３へすすむ。
【００６１】
（ステップＳ３１）
代替経路表判定部１１３は、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要である場合、リンクｅｉ〜リンクｅｋを集合Ｎｕの要素に追加する。つまり、特定のリーフノードへのパスにおいて、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要と判定すると、リンクｅｋより自ノード側の全てのリンクを、各リンクに障害が発生した場合に主経路表１２２の経路情報の更新が必要なリンクと決定する。これは、前述の通り、自ノードに近いリンクであればあるほど、障害時に主経路表１２２の経路情報を更新する必要が高くなることによる。本実施形態では、このように処理を行うことで、代替経路表判定部１１３は、判定のための計算量を減少させることができる。
【００６２】
（ステップＳ３２）
代替経路表判定部１１３は、ｉを「ｉ＝ｋ＋１」とする。この後、ステップＳ３５へ進む。
【００６３】
（ステップＳ３３）
代替経路表判定部１１３は、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要ない場合、リンクｅｋ〜リンクｅｊを集合Ｎｎの要素に追加する。つまり、特定のリーフノードへのパスにおいて、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要でない判定すると、リンクｅｋよりリーフノード側のリンクを全て、各リンクに障害が発生した場合に主経路表１２２の経路情報の更新が必要でないと決定する。これは、前述の通り、自ノードから遠いリンクであればあるほど、障害時に主経路表１２２の経路情報を更新する必要が低くなることによる。このように処理を行うことで、代替経路表判定部１１３は、判定のための計算量を減少させることができる。
【００６４】
（ステップＳ３４）
代替経路表判定部１１３は、ｊを「ｊ＝ｋ−１」とする。この後、ステップＳ３５へ進む。
【００６５】
（ステップＳ３５）
代替経路表判定部１１３は、ｉの値がｊの値を超えているか、「ｉ＞ｊ」を判定する。ｉの値がｊの値を超えていれば当該パスに含まれる全てのリンクに対して処理が完了したことになる。一方、ｉの値がｊの値を超えていない場合、当該パスに含まれる全てのリンクに対して、まだ、処理が完了していないことになる。ｉの値がｊの値を超えている場合、ステップＳ３６へ進む。一方、ｉの値がｊの値を超えていない場合、ステップＳ２９へ戻る。
【００６６】
（ステップＳ３６）
代替経路表判定部１１３は、ｉの値がｊの値を超えている場合、最短パスツリーに含まれる全てのリーフノードへのパスに対する処理が完了したか否かを判定する。最短パスツリーに含まれる全てのリーフノードへのパスに対する処理が完了していない場合、他のリーフノードへのパスに対する処理を行うために、ステップＳ２１へ戻る。一方、最短パスツリーに含まれる全てのリーフノードへのパスに対する処理が完了した場合、本動作方法は終了となる。この時点で、集合Ｎｕに含まれるリンクが、代替経路表１３１１〜１３１ｎを作成するべきリンクとなる。
【００６７】
以上が、本実施形態における代替経路表１３１１〜１３１ｎを作成するべきリンクを抽出する動作方法の説明である。このようにして、代替経路表１３１１〜１３１ｎを作成するべきリンクが抽出される。
【００６８】
次に、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要であるか否かを判定する動作方法を説明する。本動作方法は、前述のステップＳ３０の詳細な動作方法を説明するものである。図６は、本実施形態におけるリンクｅｋの障害時に主経路表１２２の経路情報の更新が必要であるか否かを判定する動作フローを示している。
【００６９】
（ステップＳ４０）
代替経路表判定部１１３は、現在、主経路表１２２に記録されている経路情報を取得する。
【００７０】
（ステップＳ４１）
代替経路表計算部１１４は、リンクｅｋに障害が発生したと想定して、経路情報（以下、本説明において、障害時経路情報）を計算する。代替経路表計算部１１４は、主経路計算部１１２と同様の方法により、障害時経路情報を計算する。代替経路表計算部１１４は、計算された障害時経路情報を、代替経路表判定部１１３へ出力する。
【００７１】
（ステップＳ４２）
代替経路表判定部１１３は、ステップＳ４０において主経路計算部１１２から取得した現在の経路情報と、ステップＳ４１において代替経路表計算部１１４により計算されたリンクｅｋの障害時の障害時経路情報とを比較する。
【００７２】
（ステップＳ４３）
代替経路表判定部１１３は、ステップＳ４２の比較において、リンクｅｋの障害前後で次転送先が異なる宛先ネットワークが存在するか否かを判定する。リンクｅｋの障害前後で次転送先が異なる宛先ネットワークが一つでも存在する場合、ステップＳ４４へ進む。一方、リンクｅｋの障害前後で次転送先が異なる宛先ネットワークが一つも存在しない場合、ステップＳ４５へ進む。
【００７３】
（ステップＳ４４）
代替経路表判定部１１３は、リンクｅｋの障害前後で次転送先が異なる宛先ネットワークが存在する場合、リンクｅｋ対する経路更新が必要であると判定する。このため、前述により、リンクｅｋは集合Ｎｕに属することになり、リンクｅｋに対応する代替経路表１３１１〜１３１ｎが作成されることになる。この場合、本動作方法は、終了となる。
【００７４】
（ステップＳ４５）
代替経路表判定部１１３は、リンクｅｋの障害前後で次転送先が異なる宛先ネットワークが存在しない場合、リンクｅｋに対する経路更新が必要ではないと判定する。このため、前述により、リンクｅｋは、集合Ｎｎに属することとなり、リンクｅｋに対応する代替経路表１３１１〜１３１ｎは作成されないことになる。以上で、動作方法は終了となる。
【００７５】
以上が、リンクｅｋの障害時に主経路表１２２の経路情報の更新が必要であるか否かを判定する動作方法の説明である。
【００７６】
以上が、本実施形態における通信ネットワークの説明である。
【００７７】
（第２実施形態）
次に、第２実施形態の通信ネットワークの説明を行う。
【００７８】
本実施形態の通信ネットワークは、通信ネットワークを構成する各ノードが、代替経路表を作成するか否かを判定するリンクの対象が第１実施形態と異なる。第１実施形態では、各ノードは、通信ネットワーク内の全てのリンクに対して代替経路表を作成するか否かを判定していた。本実施形態において各ノードは、自ノードに接続されたリンクについてのみ代替経路表を作成するか否かを判定する。また、本実施形態では各ノードが自ノードのみではなく、他のノードが代替経路表を作成するべきリンクを特定して、当該リンクを他のノードに通知する点が第１実施形態と異なる。これにより、各ノードは、自ノードに接続されたリンクに対する判定処理を行って、代替経路表の作成が必要と判定されたリンクに対する代替経路表の作成し、また、他のノードから通知を受けた代替経路表を作成するべきリンクに対する代替経路表とを作成すればよいため、代替経路表を計算する計算量、及び代替経路表を記憶するメモリ量を抑えることが可能となる。
【００７９】
［構成の説明］
まず、本実施形態における通信ネットワークを構成するノードの構成を説明する。図７は、本実施形態におけるノード１の構成を示す図である。本実施形態におけるノード１は、第１実施形態とほぼ同様の構成である。そのため、第１実施形態と同様の部分については重ねての説明を省略し、異なる部分を中心に説明を行う。また、第１実施形態と同様の構成については、同様の符号を付与して説明を行う。
【００８０】
本実施形態のノード１は、第１実施形態と同様に、経路制御部１１と、パケット転送部１２と、代替経路表管理部１３と、ネットワークインターフェイス（以下、ＩＦ）２１〜２ｎを備え、さらに、本実施形態では、作成指示通信部１４を備える。
【００８１】
なお、本実施形態の通信ネットワークは、第１実施形態と同様に、図７に示すようなノード１を複数備えており、各ノード１は、ＩＦ２１〜２ｎに接続されたリンク３１〜３ｎにより他のノードと接続されて通信ネットワークを構成する。
【００８２】
はじめに、経路制御部１１の説明を行う。経路制御部１１は、第１実施形態と同様に、トポロジー情報交換部１１１と、主経路計算部１１２と、代替経路表計算部１１４とを備え、さらに、本実施形態では、代替経路表判定部１１３に替わり、接続リンク代替経路表１１５を備える。
【００８３】
まず、トポロジー情報交換部１１１は、第１実施形態と同様である。すなわち、トポロジー情報交換部１１１は、ＯＳＰＦなどの経路制御プロトコルを使用して、隣接ノードとの間でトポロジー情報の交換を行う。また、トポロジー情報交換部１１１は、障害通知を入力すると、通信ネットワークのトポロジーに変化が発生したことを検知して、トポロジー情報の変化分を隣接ノードへ通知する。
【００８４】
次に、主経路計算部１１２は、第１実施形態と同様である。すなわち、主経路計算部１１２は、トポロジー情報に基づいて主経路表１２２へ記録するべき経路情報を計算して、主経路表１２２の経路情報を更新する。
【００８５】
次に、接続リンク代替経路表判定部１１５は、代替経路表を作成するべきか否かを判定する。接続リンク代替経路表判定部１１５は、ＩＦ２１〜２ｎに接続されたリンク３１〜３ｎの各々に対して代替経路表１３１１〜１３１ｎを作成するべきか否かを判定する。つまり、接続リンク代替経路表判定部１１５は、自ノードに接続されたリンクに対してのみ、代替経路表１３１１〜１３１ｎを作成するべきか否かの判定を行う。接続リンク代替経路表判定部１１５は、判定結果を代替経路表計算部１１４へ通知する。判定結果は、代替経路表を作成するべきと判定されたリンクを含んでいる。
【００８６】
また、接続リンク代替経路表判定部１１５は、リンク３１〜３ｎに対応する代替経路表１３１１〜１３１ｎを作成するべき他のノードを特定する。接続リンク代替経路表判定部１１５は、リンク３１〜３ｎのうちの特定のリンク（以下、選択接続リンク）に対する代替経路表１３１１〜１３１ｎを作成するべきと特定された他のノード（以下、計算指定ノード）に対する作成指示メッセージを作成指示通信部１４へ出力する。
【００８７】
作成指示メッセージは、選択接続リンクに対応する代替経路表１３１１〜１３１ｎの作成を、計算指定ノードへ要求するメッセージである。図８Ａは、本実施形態における作成指示メッセージのペイロードを示す図である。作成指示メッセージは、図８Ａに示すように「Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ」フィールド７０および「Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋ」フィールド７１をペイロードに格納している。作成指示メッセージは、ペイロードに、ＩＰヘッダと、ＴＣＰヘッダあるいはＵＤＰヘッダを付与したパケットとして送信される。なお、通信プロトコルはこれらに限定はしない。「Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ」フィールド７０および「Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋ」フィールド７１へは、図２Ａに示した主経路表１２２において、インターフェイス４４（選択接続リンク）に対応する宛先４１およびマスク長４２がそれぞれ記録される。「Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ」フィールド７０および「Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋ」フィールド７１に記録するべき情報は、ＯＳＰＦが動作するネットワークの場合、トポロジー情報を送受信するための「Ｎｅｔｗｏｒｋ ＬＳＡ」を参照することで取得できる。参考までに、従来のＯＳＰＦにおける「Ｎｅｔｗｏｒｋ ＬＳＡ」のペイロードの構成を図８Ｂに示す。図８Ｂ中の「Ｌｉｎｋ」 Ｓｔａｔｅ ＩＤ」フィールド７２に、「Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ」フィールド７０に対応する情報が格納され、また、図８Ｂ中の「Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋ」フィールド７３に、「Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋ」フィールド７１に対応する情報が格納されている。
【００８８】
次に、代替経路表計算部１１４は、第１実施形態と同様に、代替経路表１３１１〜１３１ｎへ記録するべき代替経路情報を計算する。代替経路表計算部１１４は、接続リンク代替経路表判定部１１５が代替経路表１３１１〜１３１ｎを作成するべきと判定したリンクに対応する代替経路表１３１１〜１３１ｎへ記録するべき代替経路情報を計算する。代替経路表計算部１１４は、代替経路表１３１１〜１３１ｎを作成するべきリンクに、障害が発生した場合を想定して、代替経路情報を計算する。代替経路表計算部１１４は、計算された代替経路情報を、後述する代替経路表管理部１３の代替経路表記録部１３１における対応する代替経路表１３１１〜１３１ｎへ記録する。
【００８９】
また、代替経路表計算部１１４は、後述する作成指示通信部１４から作成指示メッセージを入力する。代替経路表計算部１１４は、作成指示メッセージに格納された情報に基づいて代替経路表１３１１〜１３１ｎを作成するべきリンクを特定する。代替経路表計算部１１４は、特定されたリンクに障害が発生したと想定した場合の代替経路情報を計算して、代替経路表記録部１３１の対応する代替経路表１３１１〜１３１ｎへ計算された代替経路情報を記録する。
【００９０】
次に、作成指示通信部１４の説明を行う。作成指示通信部１４は、作成指示送信部１４１と、作成指示受信部１４２とを備える。
【００９１】
まず、作成指示送信部１４１は、接続リンク代替経路表判定部１１５から入力される作成指示メッセージを、計算指定ノードへ、パケット転送部１２を介して送信する。
【００９２】
次に、作成指示受信部１４２は、パケット転送部１２を介して、他のノードから受信される作成指示メッセージを代替経路表計算部１１４へ出力する。
【００９３】
次に、パケット転送部１２の説明を行う。パケット転送部１２は、第１実施形態と同様である。すなわち、パケット転送部１２は、ルーティング処理部１２１と、主経路表１２２とを備える。主経路表１２２は、経路情報を記録したデータテーブルである。次に、ルーティング処理部１２１は、主経路表１２２に基づいて受信されたパケットの転送処理を行う。
【００９４】
次に、代替経路表管理部１３の説明を行う。代替経路表管理部１３は、第１実施形態と同様である。すなわち、代替経路表管理部１３は、代替経路表記憶部１３１と、経路表更新部１３２とを備える。代替経路表記憶部１３１は、代替経路表１３１１〜１３１ｎを記録しており、代替経路表１３１１〜１３１ｎは、通信ネットワーク内で障害が発生したときに、主経路表に記録された経路情報を更新するための代替経路情報を記録している。経路表更新部１３２は、トポロジー情報交換部１１１から障害通知を入力すると、代替経路表１３１１〜１３１ｎを用いて主経路表１２２を更新する。
【００９５】
以上が、本実施形態における通信ネットワークの構成の説明である。このように、本実施形態において各ノード１の接続リンク代替経路表判定部１１５は、ＩＦ２１〜２ｎに接続されたリンク３１〜３ｎのみに対して代替経路表１３１１〜１３１ｎを作成するべきか否かを判定する。また、代替経路計算部１１４は、接続リンク代替経路表判定部１１５の判定結果において、代替系経路表１３１１〜１３１ｎを作成するべきと判定されたリンクと、作成指示受信部１４２の受信した他のノードからの作成指示メッセージに含まれるネットワークアドレスに対応するリンクとにそれぞれ対応する代替経路表１３１１〜１３１ｎのみを作成する。そのため、接続リンク代替経路表判定部１１５、及び代替経路表計算部１１４の計算量を抑えることができ、また、代替経路表１３１１〜１３１ｎを記憶する代替経路表記憶部１３１のメモリ容量も抑えることが可能となる。
【００９６】
［動作方法の説明］
次に、本実施形態における通信ネットワークの動作方法の説明を行う。はじめに、図９を用いて、本実施形態における代替経路表を作成する動作方法の説明を行う。図９は、本実施形態における代替経路表を作成する動作フローを示している。
【００９７】
（ステップＳ５０）
接続リンク代替経路表判定部１１５は、ＩＦ２１〜２ｎに接続されているリンク３１〜３ｎのうちから、本動作方法による判定処理を行っていない任意のリンク（以下、選択接続リンク）を一つ選択する。接続リンク代替経路表判定部１１５は、選択接続リンクを、ｅｋとする。
【００９８】
（ステップＳ５１）
代替経路計算部１１４は、接続リンク代替経路表判定部１１５によって選択された選択接続リンクｅｋに障害が発生したと想定した場合に主経路表１２２へ記録されるべき代替経路情報を計算する。代替経路計算部１１４は、計算された代替経路情報をリンクｅｋに対応する代替経路表１３１１〜１３１ｎに記録する。なお、本ステップでは、選択接続リンクｅｋに障害が発生したときに、選択接続リンクｅｋの障害発生前後でリーフノードに対する経路情報に変更が発生するか否かを判定していない。これは、図５Ｂで説明を行ったとおり、自ノードに近いリンクであればあるほど障害時に自ノードの経路情報に影響を及ぼす可能性が高く、まして、選択接続リンクｅｋは、自ノードに直接接続されたリンクであるため、選択接続リンクｅｋの障害時には、必ず主経路表１２２の経路情報を更新する必要があると考えられるためである。なお、第１実施形態で説明を行ったとおり、選択接続リンクｅｋに対して主経路表１２２の経路情報を更新する必要あるか否かを判定する動作方法としてもよい。
【００９９】
（ステップＳ５２）
代替経路計算部１１４は、選択接続リンクｅｋの代替経路情報の計算過程で生成する最短パスツリー（以下、障害時最短パスツリー）を、接続リンク代替経路表判定部１１５へ出力する。
【０１００】
（ステップＳ５３）
接続リンク代替経路表判定部１１５は、主経路計算部１１２から、主経路表１２２へ記録するべき経路情報の計算過程で生成する最短パスツリーを取得する。この最短パスツリーは、通信ネットワーク内の全てのリンクに障害が発生してない状態で生成されたものである。
【０１０１】
（ステップＳ５４）
接続リンク代替経路表判定部１１５は、代替経路計算部１１４から取得した障害時最短パスツリーと、主経路計算部１１２から取得した最短パスツリーとに基づいて、通信ネットワーク内に存在する他のノード１のうちで、代替経路情報の計算が必要となるノード（以下、計算指定ノード）を特定する。なお、計算指定ノードの特定方法は、後述する。
【０１０２】
（ステップＳ５５）
接続リンク代替経路表判定部１１５は、接続選択リンクｅｋに対する代替経路表の作成を指示する作成指示メッセージを生成して、作成指示通信部１４の作成指示送信部１４１へ出力する。作成指示送信部１４１は、作成指示メッセージを、計算指定ノードへパケット転送部１２を介して送信する。
【０１０３】
（ステップＳ５６）
接続リンク代替経路表判定部１１５は、リンク３１〜３ｎの全てに対して、本動作方法による判定処理を行ったかを判定する。全てのリンク３１〜３ｎに大して判定処理が完了していない場合、新たに任意の選択接続リンクｅｋに対する判定処理を行うために、ステップＳ５０へもどる。一方、全てのリンク３１〜３ｎに対して判定処理を行った場合、本動作方法は終了となる。
【０１０４】
以上が、本実施形態における代替経路表を作成する動作方法の説明である。本実施形態では、このようにしてリンク３１〜３ｎから選択された接続選択リンクｅｋに対応する代替経路表１３１１〜１３１ｎが作成され、また、選択接続リンクｅｋに対応する代替経路表１３１１〜１３１ｎを作成する必要のある計算指定ノードを特定して、計算指定ノードへ選択接続リンクｅｋに対応する代替経路表１３１１〜１３１ｎを作成するように作成指示メッセージを送信する。
【０１０５】
次に、本実施形態における選択接続リンクｅｋに対応する代替経路表１３１１〜１３１ｎを作成する必要のあるノード（計算指定ノード）の特定方法について説明を行う。本説明は、前述のステップＳ５４の動作方法を詳細に説明するものである。図１０は、本実施形態における計算指定ノードを特定する動作フローである。
【０１０６】
（ステップＳ６０）
接続リンク代替経路表判定部１１５は、前述のステップＳ５０で選択された選択接続リンクｅｋにおいて、自ノード（以下、本説明においてノードｒ）を終点とする逆方向の最短パスツリーＴＲを生成する。
【０１０７】
（ステップＳ６１）
接続リンク代替経路表判定部１１５は、計算指定ノードの集合である集合Ｖｕを生成してＶｕを初期化する。
【０１０８】
（ステップＳ６２）
接続リンク代替経路表判定部１１５は、ステップＳ５３で取得した、主経路表１２２に記録されている現在の（選択接続リンクｅｋに障害発生前の）最短パスツリー（以下、最短パスツリーＴ）に基づいて、当該経路情報において、次転送先が選択接続リンクｅｋを介して接続している宛先ノードを処理対象として抽出する。つまり、ここでは、主経路表１２２に記録された宛先ノードのうちで、選択接続リンクｅｋに障害が発生することにより、次転送先の変更が必要となる宛先ノードが処理対象となる。接続リンク代替経路表判定部１１５は、抽出された処理対象のノード（以下、処理対象ノード）のうちから、本動作方法における以降の処理を実行していない任意のノードｄを選択する。
【０１０９】
（ステップＳ６３）
接続リンク代替経路表判定部１１５は、前述のステップＳ５２で取得した障害時最短パスツリー（以下、障害時最短パスツリーＴｉ）に基づいて、ノードｒ（自ノード）からノードｄまでのパスを抽出する。接続リンク代替経路表判定部１１５は、抽出されたパスにおいて、自ノードｒの次のノードを特定し、ノードｎとする。
【０１１０】
（ステップＳ６４）
接続リンク代替経路表判定部１１５は、障害時最短パスツリーＴｉにおけるノードｒからノードｄまでのパスのコストから障害前の最短パスツリーＴにおけるノードｒからノードｄまでのパスのコストを減算した値Ｃｄを計算する。
【０１１１】
（ステップＳ６５）
接続リンク代替経路表判定部１１５は、障害前の最短パスツリーＴにおけるノードｒからノードｎまでのパスのコストと、逆方向の最短パスツリーＴＲにおけるノードｎからノードｒまでのパスのコストとを合計した値Ｃｎを計算する。
【０１１２】
（ステップＳ６６）
接続リンク代替経路表判定部１１５は、ＣｎとＣｄとの値の大小を比較する。ＣｎがＣｄ以下の場合、ステップＳ６７へ進む。一方、ＣｎがＣｄより大きい場合、ステップＳ６９へ進む。
【０１１３】
（ステップＳ６７）
接続リンク代替経路表判定部１１５は、ＣｎがＣｄ以下の場合、ノードｎを、代替経路表の作成が必要な指定計算ノードであると特定する。接続リンク代替経路表判定部１１５は、ノードｎを集合Ｖｕへ追加する。
【０１１４】
（ステップＳ６８）
接続リンク代替経路表判定部１１５は、障害時最短パスツリーＴｉに基づいて、ノードｒからノードｄへのパスにおいて、ノードｎの次に位置するノードを特定して、当該ノードをノードｎとする。この後、ステップＳ６５へ戻る。
【０１１５】
（ステップＳ６９）
接続リンク代替経路表判定部１１５は、ＣｎがＣｄより大きい場合、ステップＳ６２で抽出した全ての処理対象ノードに対する判定処理が完了したかを判定する。全ての処理対象ノードに対して判定処理が完了していない場合、新たなノードｄを選択するために、ステップＳ６２へ戻る。一方、全ての処理対象ノードに対して判定勝利が完了している場合、本動作フローは終了となる。この時点で、集合Ｖｕに含まれているノードが代替経路表の作成が必要と判断された計算指定ノードとなる。
【０１１６】
以上が、本実施形態における計算指定ノードの特定方法について説明を行う。本実施形態において、計算指定ノードはこのようにして計算される。なお、計算指定ノードの特定方法は、上述した方法に限定はしない。
【０１１７】
次に、本実施形態において、他のノードから作成指示メッセージを受信した場合の動作方法の説明を行う。図１１は、本実施形態における他のノードから作成指示メッセージを受信した場合の動作フローを示している。
【０１１８】
（ステップＳ７０）
作成指示受信部１４２は、パケット転送部１２を介して他ノードのから作成指示メッセージを受信する。代替経路表計算部１１４は、作成指示メッセージに格納された代替経路表１３１１〜１３１ｎを作成するべきリンクに関する情報を抽出する。
【０１１９】
（ステップＳ７１）
代替経路表計算部１１４は、作成指示メッセージから抽出されたリンクに対して、当該リンクに障害が発生した場合に使用される代替経路情報を計算する。
【０１２０】
（ステップＳ７２）
代替経路表計算部１１４は、代替経路表記憶部１３１の作成指示メッセージから抽出されたリンクに対応する代替経路表１３１１〜１３１ｎへ、計算された代替経路情報を記録する。
【０１２１】
以上が、他のノードから作成指示メッセージを受信した場合の動作方法の説明である。このようにして、受信された作成指示メッセージに格納されたリンクに対応する代替経路表１３１１〜１３１ｎが作成される。
【０１２２】
以上が、本実施形態における通信ネットワークの説明である。
【０１２３】
ここまで、本発明の通信ネットワークの説明を行ってきた。本発明の通信ネットワークの第１実施形態によれば、通信ネットワークを構成する各ノード１において、代替経路表判定部１１３が、通信ネットワーク内に存在するリンクに対して、代替経路表１３１１〜１３１ｎを作成するか否かを判定する。代替経路表計算部１１４は、代替経路表１３１１〜１３１ｎを作成すると判定されたリンクに対応する代替経路表１３１１〜１３１ｎのみを作成する。そのため、代替経路表計算部１１４の計算量を抑えることができ、また代替経路表１３１１〜１３１ｎを記憶する代替経路記憶部１３１のメモリ容量も抑えることができる。
【０１２４】
また、本発明の通信ネットワークの第２実施形態によれば、各ノード１は、自ノード１に接続されたリンクについてのみ代替経路表１３１１〜１３１ｎを作成するか否かを判定する。また、本実施形態では各ノード１が自ノード１のみではなく、他のノード１が代替経路表を作成するべきリンクを特定して、当該リンクを他のノード１に通知する。これにより、各ノード１は、自ノード１に接続されたリンクに対する判定処理を行って、代替経路表１３１１〜１３１ｎの作成が必要と判定されたリンクに対する代替経路表１３１１〜１３１ｎの作成し、また、他のノード１から通知を受けた代替経路表１３１１〜１３１ｎを作成するべきリンクに対する代替経路表１３１１〜１３１ｎとを作成すればよいため、代替経路表１３１１〜１３１ｎを計算する計算量、及び代替経路表１３１１〜１３１ｎを記憶するメモリ量を抑えることが可能となる。
【０１２５】
第１実施形態、及び第２実施形態は、それぞれ独立してのみ実施可能ではない。それぞれ組み合わせて実現することも可能である。また、各実施形態では、リンクに障害が発生した場合のみを説明しているが、ノードに障害が発生した場合にも、適用が可能である。この場合、各ノードに対応した代替経路表が作成される。また、図４では、ステップＳ２１において抽出したパス中に含まれるリンクに対して処理を行っている。ノード障害を扱う場合には、ステップＳ２２において各リンクを「ｅ１，ｅ２，・・・ｅｍ」とする代わりに、パス中に含まれる各ノードをそれぞれ「ｎ１,ｎ２・・・ｎｍ」して以降の処理を行う。つまり、パス中の各リンクを対象とする代わりに、パス中の各ノードを対象として処理を行えばよい。また、図６では、ステップＳ４１において、リンクｅｋに障害の発生を想定しているが、これをノードｎｋおよびノードｎｋに接続される全てのリンクに障害が発生したと想定して経路情報を作成すればよい。また、実際に使用する代替経路表を作成する際も、ノードｎｋおよびノードｎｋに接続される全てのリンクに障害が発生したと想定した経路情報を作成すればよい。さらに、作成指示メッセージには、「Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ」フィールド７０の代わりに、ノードｎｋを一意に識別することが可能な情報を格納する。ノードｎｋを一意に識別することが可能な情報とは、例えば、ノードｎｋのＩＰアドレスである。このような、変更を行うことで、本願発明をノード障害に適応することが可能である。つまり、本発明は、ノードとリンクを含む通信ネットワークを構成するネットワークリソースに対して適用が可能である。
【０１２６】
また、代替経路表記憶部１３１は、通信ネットワークのトポロジーの変化に伴い、代替経路表１３１１〜１３１ｎが不要となった場合に、不要になった代替経路表１３１１〜１３１ｎ、あるいは、不要になった代替経路表１３１１〜１３１ｎ記録された代替経路情報を削除しても構わない。これにより、メモリ容量をより抑えることが可能となる。
【０１２７】
なお、本発明の通信ネットワークが備える各ネットワークノードは、実行するべき機能をハードウェアによっても実現可能であるし、ソフトウェアによっても実現可能である。ソフトウェアで実現される場合には、各ネットワークノードへ導入されるコンピュータプログラムは、例えばＣＤ−Ｒ（Ｃｏｍｐａｃｔ Ｄｉｓｃ Ｒｅｃｏｒｄａｂｌｅ）やＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）のような情報記録媒体に記録することが可能である。コンピュータプログラムは、このような記録媒体を用いて、各ネットワークノードへの導入が可能である。
【０１２８】
以上、実施形態を参照して本願発明を説明したが、本願発明は、上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明の範囲内で当業者が理解し得る様々な変更を行うことが可能である。
【符号の説明】
【０１２９】
１ ノード
１１ 経路制御部
１２ パケット転送部
１３ 代替経路表管理部
１４ 作成指示通信部
２１〜２ｎ ネットワークインターフェイス
３１〜３ｎ リンク
４１ 宛先
４２ マスク長
４３ 次転送先
４４ インターフェイス
５１ 宛先
５２ マスク長
５３ 次転送先
５４ インターフェイス
６０ ルートノード
６１−１〜５ リーフノード
６２ パス
７０ Ｎｅｔｗｏｒｋ Ａｄｄｒｅｓｓ フィールド（作成指示メッセージ）
７１ Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋ フィールド（作成指示メッセージ）
７２ Ｌｉｎｋ Ｓｔａｔｅ ＩＤフィールド（Ｎｅｔｗｏｒｋ ＬＳＡ）
７３ Ｎｅｔｗｏｒｋ Ｓｕｂｎｅｔ Ｍａｓｋフィールド（Ｎｅｔｗｏｒｋ ＬＳＡ）
１１１ トポロジー情報交換部
１１２ 主経路計算部
１１３ 代替経路表判定部
１１４ 代替経路表計算部
１１５ 接続リンク代替経路表判定部
１２１ ルーティング処理部
１２２ 主経路表
１３１ 代替経路表記憶部
１３２ 経路表更新部
１４１ 作成指示送信部
１４２ 作成指示受信部
１３１１〜１３１ｎ 代替経路表
【特許請求の範囲】
【請求項１】
複数のネットワークノードを具備する通信ネットワークであって、
前記複数のネットワークノードの各々は、
複数のインターフェイスと、
前記通信ネットワークにおける経路情報を記録した主経路表と、
前記主経路表に基づいて前記複数のインターフェイスから入力されるパケットを転送するルーティング処理部と、
前記通信ネットワークを構成するネットワークリソースに対応して設けられて、前記ネットワークリソースの障害時に前記主経路表に記録された前記経路情報のうちで更新されるべき経路情報の代替経路情報を記録した代替経路表を記憶する代替経路表記憶部と、
前記ネットワークリソースは、前記複数のネットワークノード、および前記複数のネットワークノードの間を接続するリンクを含み、
前記ネットワークリソースのうちから選択する選択ネットワークリソースに障害が発生したときに、前記主経路表の前記経路情報の更新が必要であるか否かに基づいて、前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定する代替経路表判定部と、
前記代替経路表を作成すると決定された前記選択ネットワークリソースに対応する選択代替経路表に記録されるべき前記代替経路情報を計算する代替経路表計算部と、
前記障害を検知すると前記障害の発生した前記ネットワークリソースに対応する前記代替経路表に記録された前記代替経路情報を用いて前記主経路表の前記経路情報を更新する経路表更新部と
を備える通信ネットワーク。
【請求項２】
請求項１に記載の通信ネットワークであって、
前記代替経路表判定部は、前記主経路表から前記経路情報を取得して、前記選択ネットワークリソースに障害が発生したと想定した場合に前記主経路表へ記録されるべき障害時経路情報を算出して、前記障害時経路情報と前記経路情報とが異なるか否かに基づいて前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定する
通信ネットワーク。
【請求項３】
請求項２に記載の通信ネットワークであって、
前記障害時経路情報と前記経路情報とを比較して、前記障害時経路情報と前記経路情報とのそれぞれに含まれる同一の宛先ネットワークに対応する次転送先ネットワークノードが異なっている場合に、前記選択ネットワークリソースに対応する前記代替経路表を作成すると決定する
通信ネットワーク。
【請求項４】
請求項１から請求項３までのいずれかに記載の通信ネットワークであって、
前記ネットワークにおける隣接ネットワークノードと前記通信ネットワークのトポロジー情報を送受信するトポロジー情報交換部と、
前記トポロジー情報に基づいて前記ネットワークの最短パスツリーを生成して、前記最短パスツリーに基づいて前記主経路表に記録された経路情報を更新する主経路計算部と
をさらに備え、
前記代替経路表判定部は、前記最短パスツリーに含まれるリーフノードのうちから任意の選択リーフノードを選択して、前記選択リーフノードまでのパスを前記最短パスツリーから抽出して、前記パスに含まれる前記ネットワークリソースのうちから前記選択ネットワークリソースを選択する
通信ネットワーク。
【請求項５】
請求項４に記載の通信ネットワークであって、
前記代替経路表判定部は、前記選択ネットワークリソースが前記代替経路表を作成するべき前記ネットワークリソースと決定すると、前記パスに存在する前記ネットワークリソースのうちで、前記選択ネットワークリソースより自身のネットワークノードに近い全ての前記ネットワークリソースに対して、前記代替経路表を作成すると決定する
通信ネットワーク。
【請求項６】
請求項４または請求項５に記載の通信ネットワークであって、
前記代替経路表判定部は、前記選択ネットワークリソースが前記代替経路表を作成する必要がない前記ネットワークリソースと決定すると、前記パスに存在する前記ネットワークリソースのうちで、前記選択ネットワークリソースより前記選択リーフノードに近い全ての前記ネットワークリソースに対して、前記代替経路表を作成する必要がないと決定する
通信ネットワーク。
【請求項７】
請求項１から請求項６までのいずれかに記載の通信ネットワークであって、
前記代替経路表判定部は、前記複数のインターフェイスに接続された前記リンクのうちから前記選択ネットワークリソースを選択する
通信ネットワーク。
【請求項８】
請求項７に記載の通信ネットワークであって、
前記選択ネットワークリソースに対応する前記代替経路表の作成を指示する作成指示メッセージを送受信する作成指示通信部
をさらに備え、
前記代替経路表判定部は、前記複数のネットワークノードのうちから、前記選択ネットワークリソースに障害が発生したと想定した場合に前記選択ネットワークリソースに対応する前記代替経路表を作成するべき計算指定ネットワークノードを特定し、
前記作成指示通信部は、前記計算指定ネットワークノードへ前記作成指示メッセージを送信する
通信ネットワーク。
【請求項９】
請求項８に記載の通信ネットワークであって、
前記作成指示通信部は、前記複数のネットワークノードから前記作成指示メッセージを受信して、
前記代替計算表計算部は、前記作成指示メッセージに格納された情報に基づいて前記代替経路表を作成するべき前記選択ネットワークリソースを特定して、前記選択ネットワークリソースに対応する代替経路表に記録されるべき前記代替経路情報を計算して、前記代替経路情報を前記選択ネットワークリソースに対応する前記代替経路表へ記録する
通信ネットワーク。
【請求項１０】
請求項８または請求項９に記載の通信ネットワークであって、
前記作成指示メッセージは、前記主経路表において、前記選択ネットワークリソースとして選択された前記リンクに対応する宛先ネットワークアドレスと、前記宛先ネットワークアドレスのサブネットマスクを記録しており、
前記代替経路表計算部は、前記宛先ネットワークアドレスと、前記宛先ネットワークアドレスのサブネットマスクに基づいて、前記選択ネットワークリソースとして選択された前記リンクを特定する
通信ネットワーク。
【請求項１１】
請求項１から請求項１０までのいずれかに記載の通信ネットワークを構成するネットワークノード。
【請求項１２】
複数のネットワークノードを具備する通信ネットワークにおいて、
前記通信ネットワークにおける経路情報を記録するステップと、
前記主経路表に基づいて複数のインターフェイスから入力されるパケットを転送するステップと、
前記通信ネットワークを構成するネットワークリソースに対応して設けられて、前記ネットワークリソースの障害時に前記主経路表に記録された前記経路情報のうちで更新されるべき経路情報の代替経路情報を記録した代替経路表を記憶するステップと、
前記ネットワークリソースは、前記複数のネットワークノード、および前記複数のネットワークノードの間を接続するリンクを含み、
前記ネットワークリソース選択する前記選択ネットワークリソースに障害が発生したときに、前記主経路表の前記経路情報の更新が必要であるか否かに基づいて、前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップと、
前記代替経路表を作成すると決定された前記ネットワークリソースに対応する選択代替経路表に記録されるべき前記代替経路情報を計算するステップと、
前記障害を検知すると前記障害の発生した前記ネットワークリソースに対応する前記代替経路表に記録された前記代替経路情報を用いて前記主経路表の前記経路情報を更新するステップと
を備える通信経路制御方式。
【請求項１３】
請求項１２に記載の通信経路制御方式であって、前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップは、
前記経路情報を取得するステップと、
前記選択ネットワークリソースに障害が発生したと想定した場合に前記主経路表へ記録されるべき障害時経路情報を算出するステップと、
前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを前記障害時経路情報と前記経路情報とが異なるか否かに基づいて決定するステップと
を含む通信経路制御方式。
【請求項１４】
請求項１３に記載の通信経路制御方式であって、前記障害時経路情報と前記経路情報とが異なるか否かに基づいて決定するステップは、
前記障害時経路情報と前記経路情報とを比較するステップと、
前記障害時経路情報と前記経路情報とのそれぞれに含まれる同一の宛先ネットワークに対応する次転送先ネットワークノードが異なっている場合に、前記選択ネットワークリソースに対応する前記代替経路表を作成すると決定するステップと
を含む通信経路制御方式。
【請求項１５】
請求項１２から請求項１４までのいずれかに記載の通信経路制御方式であって、
前記ネットワークにおける隣接ネットワークノードと前記通信ネットワークのトポロジー情報を送受信するステップと、
前記トポロジー情報に基づいて前記ネットワークの最短パスツリーを生成するステップと、
前記最短パスツリーに基づいて前記主経路表に記録された経路情報を更新するステップと
をさらに備え、
前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップは、
前記最短パスツリーに含まれるリーフノードのうちから任意の選択リーフノードを選択するステップと、
前記選択リーフノードまでのパスを前記最短パスツリーから抽出するステップと、
前記パスに含まれる前記ネットワークリソースのうちから前記選択ネットワークリソースを選択するステップと
を含む通信経路制御方式。
【請求項１６】
請求項１５に記載の通信経路制御方式であって、前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップは、
前記選択ネットワークリソースが前記代替経路表を作成するべき前記ネットワークリソースと決定すると、前記パスに存在する前記ネットワークリソースのうちで、前記選択ネットワークリソースより自身のネットワークノードに近い全ての前記ネットワークリソースに対して、前記代替経路表を作成すると決定するステップ
を含む通信経路制御方式。
【請求項１７】
請求項１５または請求項１６に記載の通信経路制御方式であって、前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップは、
前記選択ネットワークリソースが前記代替経路表を作成する必要がない前記ネットワークリソースと決定すると、前記パスに存在する前記ネットワークリソースのうちで、前記選択ネットワークリソースより前記選択リーフノードに近い全ての前記ネットワークリソースに対して、前記代替経路表を作成する必要がないと決定するステップ
を含む通信経路制御方式。
【請求項１８】
請求項１２から請求項１７までのいずれかに記載の通信経路制御方式であって、前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップは
前記複数のインターフェイスに接続された前記リンクのうちから前記選択ネットワークリソースを選択するステップ
を含む通信経路制御方式。
【請求項１９】
請求項１８に記載の通信経路制御方式であって、
前記選択ネットワークリソースに対応する前記代替経路表の作成を指示する作成指示メッセージを送受信するステップ
をさらに備え、
前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップは、
前記複数のネットワークノードのうちから、前記選択ネットワークリソースに障害が発生したと想定した場合に前記選択ネットワークリソースに対応する前記代替経路表を作成するべき計算指定ネットワークノードを特定するステップ
を含み、
前記作成指示メッセージを送受信するステップは、
前記計算指定ネットワークノードへ前記作成指示メッセージを送信するステップ
を含む通信経路制御方式。
【請求項２０】
請求項１９に記載の通信経路制御方式であって、前記作成指示メッセージを送受信するステップは、
前記複数のネットワークノードから前記作成指示メッセージを受信するステップ
を含み、
前記代替経路情報を計算するステップは、
前記作成指示メッセージに格納された情報に基づいて前記代替経路表を作成するべき前記選択ネットワークリソースを特定するステップと、
前記選択ネットワークリソースに対応する代替経路表に記録されるべき前記代替経路情報を計算するステップと、
前記代替経路情報を前記選択ネットワークリソースに対応する前記代替経路表へ記録するステップと
を含む通信経路制御方式。
【請求項２１】
請求項２０に記載の通信経路制御方式であって、
前記作成指示メッセージは、前記主経路表において、前記選択ネットワークリソースとして選択された前記リンクに対応する宛先ネットワークアドレスと、宛先ネットワークアドレスのサブネットマスクを記録しており、
前記代替経路表を作成するべき前記選択ネットワークリソースを特定するステップは、
宛先ネットワークアドレスと、宛先ネットワークアドレスのサブネットマスクに基づいて前記選択ネットワークリソースとして選択された前記選択リンクを特定するステップ
を含む通信経路制御方式。
【請求項２２】
請求項１２から請求項２１までのいずれかに記載の通信経路制御方式をコンピュータに実行させるコンピュータプログラム。
【請求項１】
複数のネットワークノードを具備する通信ネットワークであって、
前記複数のネットワークノードの各々は、
複数のインターフェイスと、
前記通信ネットワークにおける経路情報を記録した主経路表と、
前記主経路表に基づいて前記複数のインターフェイスから入力されるパケットを転送するルーティング処理部と、
前記通信ネットワークを構成するネットワークリソースに対応して設けられて、前記ネットワークリソースの障害時に前記主経路表に記録された前記経路情報のうちで更新されるべき経路情報の代替経路情報を記録した代替経路表を記憶する代替経路表記憶部と、
前記ネットワークリソースは、前記複数のネットワークノード、および前記複数のネットワークノードの間を接続するリンクを含み、
前記ネットワークリソースのうちから選択する選択ネットワークリソースに障害が発生したときに、前記主経路表の前記経路情報の更新が必要であるか否かに基づいて、前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定する代替経路表判定部と、
前記代替経路表を作成すると決定された前記選択ネットワークリソースに対応する選択代替経路表に記録されるべき前記代替経路情報を計算する代替経路表計算部と、
前記障害を検知すると前記障害の発生した前記ネットワークリソースに対応する前記代替経路表に記録された前記代替経路情報を用いて前記主経路表の前記経路情報を更新する経路表更新部と
を備える通信ネットワーク。
【請求項２】
請求項１に記載の通信ネットワークであって、
前記代替経路表判定部は、前記主経路表から前記経路情報を取得して、前記選択ネットワークリソースに障害が発生したと想定した場合に前記主経路表へ記録されるべき障害時経路情報を算出して、前記障害時経路情報と前記経路情報とが異なるか否かに基づいて前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定する
通信ネットワーク。
【請求項３】
請求項２に記載の通信ネットワークであって、
前記障害時経路情報と前記経路情報とを比較して、前記障害時経路情報と前記経路情報とのそれぞれに含まれる同一の宛先ネットワークに対応する次転送先ネットワークノードが異なっている場合に、前記選択ネットワークリソースに対応する前記代替経路表を作成すると決定する
通信ネットワーク。
【請求項４】
請求項１から請求項３までのいずれかに記載の通信ネットワークであって、
前記ネットワークにおける隣接ネットワークノードと前記通信ネットワークのトポロジー情報を送受信するトポロジー情報交換部と、
前記トポロジー情報に基づいて前記ネットワークの最短パスツリーを生成して、前記最短パスツリーに基づいて前記主経路表に記録された経路情報を更新する主経路計算部と
をさらに備え、
前記代替経路表判定部は、前記最短パスツリーに含まれるリーフノードのうちから任意の選択リーフノードを選択して、前記選択リーフノードまでのパスを前記最短パスツリーから抽出して、前記パスに含まれる前記ネットワークリソースのうちから前記選択ネットワークリソースを選択する
通信ネットワーク。
【請求項５】
請求項４に記載の通信ネットワークであって、
前記代替経路表判定部は、前記選択ネットワークリソースが前記代替経路表を作成するべき前記ネットワークリソースと決定すると、前記パスに存在する前記ネットワークリソースのうちで、前記選択ネットワークリソースより自身のネットワークノードに近い全ての前記ネットワークリソースに対して、前記代替経路表を作成すると決定する
通信ネットワーク。
【請求項６】
請求項４または請求項５に記載の通信ネットワークであって、
前記代替経路表判定部は、前記選択ネットワークリソースが前記代替経路表を作成する必要がない前記ネットワークリソースと決定すると、前記パスに存在する前記ネットワークリソースのうちで、前記選択ネットワークリソースより前記選択リーフノードに近い全ての前記ネットワークリソースに対して、前記代替経路表を作成する必要がないと決定する
通信ネットワーク。
【請求項７】
請求項１から請求項６までのいずれかに記載の通信ネットワークであって、
前記代替経路表判定部は、前記複数のインターフェイスに接続された前記リンクのうちから前記選択ネットワークリソースを選択する
通信ネットワーク。
【請求項８】
請求項７に記載の通信ネットワークであって、
前記選択ネットワークリソースに対応する前記代替経路表の作成を指示する作成指示メッセージを送受信する作成指示通信部
をさらに備え、
前記代替経路表判定部は、前記複数のネットワークノードのうちから、前記選択ネットワークリソースに障害が発生したと想定した場合に前記選択ネットワークリソースに対応する前記代替経路表を作成するべき計算指定ネットワークノードを特定し、
前記作成指示通信部は、前記計算指定ネットワークノードへ前記作成指示メッセージを送信する
通信ネットワーク。
【請求項９】
請求項８に記載の通信ネットワークであって、
前記作成指示通信部は、前記複数のネットワークノードから前記作成指示メッセージを受信して、
前記代替計算表計算部は、前記作成指示メッセージに格納された情報に基づいて前記代替経路表を作成するべき前記選択ネットワークリソースを特定して、前記選択ネットワークリソースに対応する代替経路表に記録されるべき前記代替経路情報を計算して、前記代替経路情報を前記選択ネットワークリソースに対応する前記代替経路表へ記録する
通信ネットワーク。
【請求項１０】
請求項８または請求項９に記載の通信ネットワークであって、
前記作成指示メッセージは、前記主経路表において、前記選択ネットワークリソースとして選択された前記リンクに対応する宛先ネットワークアドレスと、前記宛先ネットワークアドレスのサブネットマスクを記録しており、
前記代替経路表計算部は、前記宛先ネットワークアドレスと、前記宛先ネットワークアドレスのサブネットマスクに基づいて、前記選択ネットワークリソースとして選択された前記リンクを特定する
通信ネットワーク。
【請求項１１】
請求項１から請求項１０までのいずれかに記載の通信ネットワークを構成するネットワークノード。
【請求項１２】
複数のネットワークノードを具備する通信ネットワークにおいて、
前記通信ネットワークにおける経路情報を記録するステップと、
前記主経路表に基づいて複数のインターフェイスから入力されるパケットを転送するステップと、
前記通信ネットワークを構成するネットワークリソースに対応して設けられて、前記ネットワークリソースの障害時に前記主経路表に記録された前記経路情報のうちで更新されるべき経路情報の代替経路情報を記録した代替経路表を記憶するステップと、
前記ネットワークリソースは、前記複数のネットワークノード、および前記複数のネットワークノードの間を接続するリンクを含み、
前記ネットワークリソース選択する前記選択ネットワークリソースに障害が発生したときに、前記主経路表の前記経路情報の更新が必要であるか否かに基づいて、前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップと、
前記代替経路表を作成すると決定された前記ネットワークリソースに対応する選択代替経路表に記録されるべき前記代替経路情報を計算するステップと、
前記障害を検知すると前記障害の発生した前記ネットワークリソースに対応する前記代替経路表に記録された前記代替経路情報を用いて前記主経路表の前記経路情報を更新するステップと
を備える通信経路制御方式。
【請求項１３】
請求項１２に記載の通信経路制御方式であって、前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップは、
前記経路情報を取得するステップと、
前記選択ネットワークリソースに障害が発生したと想定した場合に前記主経路表へ記録されるべき障害時経路情報を算出するステップと、
前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを前記障害時経路情報と前記経路情報とが異なるか否かに基づいて決定するステップと
を含む通信経路制御方式。
【請求項１４】
請求項１３に記載の通信経路制御方式であって、前記障害時経路情報と前記経路情報とが異なるか否かに基づいて決定するステップは、
前記障害時経路情報と前記経路情報とを比較するステップと、
前記障害時経路情報と前記経路情報とのそれぞれに含まれる同一の宛先ネットワークに対応する次転送先ネットワークノードが異なっている場合に、前記選択ネットワークリソースに対応する前記代替経路表を作成すると決定するステップと
を含む通信経路制御方式。
【請求項１５】
請求項１２から請求項１４までのいずれかに記載の通信経路制御方式であって、
前記ネットワークにおける隣接ネットワークノードと前記通信ネットワークのトポロジー情報を送受信するステップと、
前記トポロジー情報に基づいて前記ネットワークの最短パスツリーを生成するステップと、
前記最短パスツリーに基づいて前記主経路表に記録された経路情報を更新するステップと
をさらに備え、
前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップは、
前記最短パスツリーに含まれるリーフノードのうちから任意の選択リーフノードを選択するステップと、
前記選択リーフノードまでのパスを前記最短パスツリーから抽出するステップと、
前記パスに含まれる前記ネットワークリソースのうちから前記選択ネットワークリソースを選択するステップと
を含む通信経路制御方式。
【請求項１６】
請求項１５に記載の通信経路制御方式であって、前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップは、
前記選択ネットワークリソースが前記代替経路表を作成するべき前記ネットワークリソースと決定すると、前記パスに存在する前記ネットワークリソースのうちで、前記選択ネットワークリソースより自身のネットワークノードに近い全ての前記ネットワークリソースに対して、前記代替経路表を作成すると決定するステップ
を含む通信経路制御方式。
【請求項１７】
請求項１５または請求項１６に記載の通信経路制御方式であって、前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップは、
前記選択ネットワークリソースが前記代替経路表を作成する必要がない前記ネットワークリソースと決定すると、前記パスに存在する前記ネットワークリソースのうちで、前記選択ネットワークリソースより前記選択リーフノードに近い全ての前記ネットワークリソースに対して、前記代替経路表を作成する必要がないと決定するステップ
を含む通信経路制御方式。
【請求項１８】
請求項１２から請求項１７までのいずれかに記載の通信経路制御方式であって、前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップは
前記複数のインターフェイスに接続された前記リンクのうちから前記選択ネットワークリソースを選択するステップ
を含む通信経路制御方式。
【請求項１９】
請求項１８に記載の通信経路制御方式であって、
前記選択ネットワークリソースに対応する前記代替経路表の作成を指示する作成指示メッセージを送受信するステップ
をさらに備え、
前記選択ネットワークリソースに対応する前記代替経路表を作成するか否かを決定するステップは、
前記複数のネットワークノードのうちから、前記選択ネットワークリソースに障害が発生したと想定した場合に前記選択ネットワークリソースに対応する前記代替経路表を作成するべき計算指定ネットワークノードを特定するステップ
を含み、
前記作成指示メッセージを送受信するステップは、
前記計算指定ネットワークノードへ前記作成指示メッセージを送信するステップ
を含む通信経路制御方式。
【請求項２０】
請求項１９に記載の通信経路制御方式であって、前記作成指示メッセージを送受信するステップは、
前記複数のネットワークノードから前記作成指示メッセージを受信するステップ
を含み、
前記代替経路情報を計算するステップは、
前記作成指示メッセージに格納された情報に基づいて前記代替経路表を作成するべき前記選択ネットワークリソースを特定するステップと、
前記選択ネットワークリソースに対応する代替経路表に記録されるべき前記代替経路情報を計算するステップと、
前記代替経路情報を前記選択ネットワークリソースに対応する前記代替経路表へ記録するステップと
を含む通信経路制御方式。
【請求項２１】
請求項２０に記載の通信経路制御方式であって、
前記作成指示メッセージは、前記主経路表において、前記選択ネットワークリソースとして選択された前記リンクに対応する宛先ネットワークアドレスと、宛先ネットワークアドレスのサブネットマスクを記録しており、
前記代替経路表を作成するべき前記選択ネットワークリソースを特定するステップは、
宛先ネットワークアドレスと、宛先ネットワークアドレスのサブネットマスクに基づいて前記選択ネットワークリソースとして選択された前記選択リンクを特定するステップ
を含む通信経路制御方式。
【請求項２２】
請求項１２から請求項２１までのいずれかに記載の通信経路制御方式をコンピュータに実行させるコンピュータプログラム。
【図１】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１１−６１５６０（Ｐ２０１１−６１５６０Ａ）
【公開日】平成２３年３月２４日（２０１１．３．２４）
【国際特許分類】
【出願番号】特願２００９−２０９８４８（Ｐ２００９−２０９８４８）
【出願日】平成２１年９月１０日（２００９．９．１０）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２３年３月２４日（２０１１．３．２４）
【国際特許分類】
【出願日】平成２１年９月１０日（２００９．９．１０）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]