(57)【要約】  複数のノード装置間におけるパケット転送に用いるネットワーク上でトポロジーに変化が生じた場合に、新たな正常な経路を確立する動的経路制御を行うノード装置。他のノード装置から経路を決定するために必要となる情報を含む経路制御メッセージを受信する手段と、前記受信した経路制御メッセージを元に前記ネットワーク上の経路を計算する手段と、他のノード装置で前記ネットワーク上の経路を決定するために必要な情報を含む経路制御メッセージを他のノード装置に送信する手段と、前記経路制御メッセージを受信すると、トポロジー変更箇所と自ノード装置との距離に基づいて、前記経路計算と前記メッセージ送信とによる経路制御動作に関わる動作開始時間を算出する手段と、前記算出された動作開始時間に基づいて、前記経路制御動作の実行を制御する手段と、を備える。
2010058537.tif 000002
【特許請求の範囲】
【請求項１】
複数のノード装置間におけるパケット転送に用いるネットワーク上でトポロジーに変化が生じた場合に、新たな正常な経路を確立する動的経路制御を行うノード装置であって、
他のノード装置から経路を決定するために必要となる情報を含む経路制御メッセージを受信するメッセージ受信手段と、
前記受信した経路制御メッセージを元に前記ネットワーク上の経路を決定する経路計算手段と、
他のノード装置で前記ネットワーク上の経路を決定するために必要な情報を含む経路制御メッセージを他のノード装置に送信するメッセージ送信手段と、
前記メッセージ受信手段により経路制御メッセージを受信すると、トポロジー変更箇所と自ノード装置との距離に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作に関わる動作開始時間を算出する遅延計算手段と、
前記遅延計算手段により算出された動作開始時間に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作の実行を制御する実行制御手段と、
を備えることを特徴とするノード装置。
【請求項２】
前記実行制御手段は、前記遅延計算手段により算出された動作開始時間に基づいて、前記経路計算手段による経路計算の開始までの時間を計時する計算開始遅延タイマ手段を備えることを特徴とする請求項１記載のノード装置。
【請求項３】
前記実行制御手段は、前記計算開始遅延タイマ手段による計時が前記動作開始時間に達すると、前記経路計算手段に経路計算の開始を指示する遅延実行手段を備えることを特徴とする請求項２記載のノード装置。
【請求項４】
前記実行制御手段は、前記遅延計算手段により算出された動作開始時間に基づいて、前記メッセージ送信手段による経路制御メッセージの送信の開始までの時間を計時するメッセージ転送遅延タイマ手段を備えることを特徴とする請求項１記載のノード装置。
【請求項５】
前記実行制御手段は、前記メッセージ転送遅延タイマ手段による計時が前記動作開始時間に達すると、前記メッセージ送信手段に経路制御メッセージの送信を指示する遅延実行手段を備えることを特徴とする請求項４記載のノード装置。
【請求項６】
前記遅延計算手段は、前記動作開始時間を算出するために用いる距離として、トポロジー変更箇所と自ノード装置との間に存在するノード数であるホップ数を用いることを特徴とする請求項１記載のノード装置。
【請求項７】
前記遅延計算手段は、前記動作開始時間を算出するために用いる距離として、トポロジー変更箇所と自ノード装置との間のパスのコストの合計値を用いることを特徴とする請求項１記載のノード装置。
【請求項８】
前記遅延計算手段は、前記動作開始時間を算出するために用いる距離として、トポロジー変更箇所と自ノード装置との間にある自律システム数を用いることを特徴とする請求項１記載のノード装置。
【請求項９】
前記遅延計算手段は、前記動作開始時間を算出するために用いる距離を決定する際に、前記経路計算手段による経路計算過程において生成される最短パスツリーを用いることを特徴とする請求項１記載のノード装置。
【請求項１０】
前記遅延計算手段は、前記動作開始時間を算出するために用いる距離を決定する際に、他のシステムにより算出され、通知された距離を用いることを特徴とする請求項１記載のノード装置。
【請求項１１】
前記遅延計算手段は、前記距離を求める際に用いる前記トポロジー変更箇所を、前記メッセージ受信手段により受信された経路制御メッセージから取得することを特徴とする請求項１記載のノード装置。
【請求項１２】
前記遅延計算手段は、前記距離を求める際に用いる前記トポロジー変更箇所を、他のシステムにより決定され、通知された情報により取得することを特徴とする請求項１記載のノード装置。
【請求項１３】
前記遅延計算手段は、前記トポロジー変更箇所と前記自ノード装置との距離に比例した値を、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作に関わる動作開始時間とすることを特徴とする請求項１記載のノード装置。
【請求項１４】
前記遅延計算手段は、前記トポロジー変更箇所までの距離と予め設定されている値との比較結果に応じて決定した計算方法により、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作に関わる動作開始時間を算出することを特徴とする請求項１記載のノード装置。
【請求項１５】
前記遅延計算手段は、前記比較結果により、前記トポロジー変更箇所までの距離が予め定められた値よりも大きかった場合、前記予め定められた値を距離として用いて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作に関わる動作開始時間を算出することを特徴とする請求項１４記載のノード装置。
【請求項１６】
前記遅延計算手段は、前記比較結果により、前記トポロジー変更箇所までの距離が予め定められた値よりも大きかった場合、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作に関わる動作開始時間を無限大とすることを特徴とする請求項１４記載のノード装置。
【請求項１７】
前記遅延計算手段は、算出された動作開始時間と予め定められた値とを比較し、算出された動作開始時間が予め定められた値よりも大きかった場合、前記予め定められた値を前記動作開始時間とすることを特徴とする請求項１記載のノード装置。
【請求項１８】
前記遅延計算手段は、前記比較結果により、算出された動作開始時間が予め定められた値よりも小さかった場合にのみ、算出された動作開始時間を有効とすることを特徴とする請求項１７記載のノード装置。
【請求項１９】
前記実行制御手段は、前記遅延計算手段により算出された動作開始時間に基づいて、前記経路計算手段により計算された経路で、パケット転送に用いる前記ネットワーク上の経路情報を保持する経路表の更新を開始するまでの時間を計時する経路更新開始遅延タイマ手段を備えることを特徴とする請求項１記載のノード装置。
【請求項２０】
前記実行制御手段は、前記経路更新開始遅延タイマ手段による計時が前記動作開始時間に達すると、前記経路計算手段に経路表の更新の開始を指示する遅延実行手段を備えることを特徴とする請求項１９記載のノード装置。
【請求項２１】
前記実行制御手段は、前記メッセージ受信手段により新たな経路制御メッセージが受信されると、前記タイマ手段が動作中だった場合、前記遅延計算手段により算出された動作開始時間と現在動作中の前記タイマ手段の計時時間との比較結果に基づいて、前記タイマ手段による計時時間の更新を制御する遅延管理手段を備えることを特徴とする請求項２、４，１９のいずれかに記載のノード装置。
【請求項２２】
前記遅延計算手段は、前記動作開始時間を算出するために用いる距離として、トポロジー変更箇所と自ノード装置との間に存在するノード数であるホップ数を用い、前記トポロジー変更箇所を、前記メッセージ受信手段により受信された経路制御メッセージから取得することを特徴とする請求項３、５のいずれかに記載のノード装置。
【請求項２３】
複数のノード装置間におけるパケット転送に用いるネットワーク上でトポロジーに変化が生じた場合に、新たな正常な経路を確立するための経路制御方法であって、
前記ネットワーク上の経路を決定するために必要となる情報を含む経路制御メッセージを受信する受信ステップと、
前記受信した経路制御メッセージを元に前記ネットワーク上の経路を決定する経路計算ステップと、
他のノード装置で前記ネットワーク上の経路を決定するために必要な情報を含む経路制御メッセージを他のノード装置に送信する送信ステップと、
前記経路制御メッセージを受信すると、トポロジー変更箇所と自ノード装置との距離に基づいて、前記ネットワーク上の経路の決定動作と前記経路制御メッセージの送信動作とに関わる動作開始時間を算出する遅延計算ステップと、
前記算出された動作開始時間に基づいて、前記経路の決定動作と前記経路制御メッセージの送信動作との実行を制御する実行制御ステップと、
を含むことを特徴とする経路制御方法。
【請求項２４】
前記実行制御ステップは、前記動作開始時間に基づいて、前記経路の決定動作開始までの時間を計時する計算開始時間計時ステップを含むことを特徴とする請求項２３の経路制御方法。
【請求項２５】
前記実行制御ステップは、前記動作開始時間に基づいて、前記経路制御メッセージの送信の開始までの時間を計時するメッセージ転送開始時間計時ステップを含むことを請求項２３記載の経路制御方法。
【請求項２６】
前記遅延計算ステップは、前記動作開始時間を算出するために用いる距離として、トポロジー変更箇所と自ノード装置との間に存在するノード数であるホップ数を用いることを特徴とする請求項２３記載の経路制御方法。
【請求項２７】
前記遅延計算ステップは、前記動作開始時間を算出するために用いる距離として、トポロジー変更箇所と自ノード装置との間のパスのコストの合計値を用いることを特徴とする請求項２３記載の経路制御方法。
【請求項２８】
前記遅延計算ステップは、前記動作開始時間を算出するために用いる距離として、トポロジー変更箇所と自ノード装置との間にある自律システム数を用いることを特徴とする請求項２３記載の経路制御方法。
【請求項２９】
前記遅延計算ステップは、前記動作開始時間を算出するために用いる距離を決定する際に、前記経路計算ステップにおいて生成される最短パスツリーを用いることを特徴とする請求項２３記載の経路制御方法。
【請求項３０】
前記遅延計算ステップは、前記動作開始時間を算出するために用いる距離を決定する際に、他のシステムにより算出され、通知された距離を用いることを特徴とする請求項２３記載の経路制御方法。
【請求項３１】
前記遅延計算ステップは、前記距離を求める際に用いる前記トポロジー変更箇所を、前記受信ステップで受信された経路制御メッセージから取得することを特徴とする請求項２３記載の経路制御方法。
【請求項３２】
前記遅延計算ステップは、前記距離を求める際に用いる前記トポロジー変更箇所を、他のシステムにより決定され、通知された情報により取得することを特徴とする請求項２３記載の経路制御方法。
【請求項３３】
前記遅延計算ステップは、前記トポロジー変更箇所と前記自ノード装置との距離に比例した値を、前記経路の決定動作と前記経路制御メッセージの送信動作とに関わる動作開始時間とすることを特徴とする請求項２３記載の経路制御方法。
【請求項３４】
前記遅延計算ステップは、前記トポロジー変更箇所までの距離と予め設定されている値との比較結果に応じて決定した計算方法により、前記経路の決定動作と前記経路制御メッセージの送信動作とに関わる動作開始時間を算出することを特徴とする請求項２３記載の経路制御方法。
【請求項３５】
前記遅延計算ステップは、前記比較結果により、前記トポロジー変更箇所までの距離が予め定められた値よりも大きかった場合、前記予め定められた値を距離として用いて、前記経路の決定動作と前記経路制御メッセージの送信動作とに関わる動作開始時間を算出することを特徴とする請求項３４記載の経路制御方法。
【請求項３６】
前記遅延計算ステップは、前記比較結果により、前記トポロジー変更箇所までの距離が予め定められた値よりも大きかった場合、前記経路の決定動作と前記経路制御メッセージの送信動作とに関わる動作開始時間を無限大とすることを特徴とする請求項３４記載の経路制御方法。
【請求項３７】
前記遅延計算ステップは、算出された動作開始時間と予め定められた値とを比較し、算出された動作開始時間が予め定められた値よりも大きかった場合、前記予め定められた値を前記動作開始時間とすることを特徴とする請求項２３記載の経路制御方法。
【請求項３８】
前記遅延計算ステップは、前記比較結果により、算出された動作開始時間が予め定められた値よりも小さかった場合にのみ、算出された動作開始時間を有効とすることを特徴とする請求項３７記載の経路制御方法。
【請求項３９】
実行制御ステップは、前記遅延計算ステップで算出された動作開始時間に基づいて、前記経路計算ステップ計算された経路で、パケット転送に用いる前記ネットワーク上の経路情報を保持する経路表の更新を開始するまでの時間を計時する経路更新開始時間計時ステップを含むことを特徴とする請求項２３記載の経路制御方法。
【請求項４０】
前記実行制御ステップは、前記受信ステップで新たな経路制御メッセージを受信すると、前記計時ステップが動作中だった場合、前記遅延計算ステップで前記新たな経路制御メッセージから算出された動作開始時間と現在動作中の前記計時ステップでの計時時間とを比較し、該比較結果に基づいて、前記計時ステップによる計時動作の更新を制御する遅延管理ステップを含むことを特徴とする請求項２４、２５、３９のいずれかに記載の経路制御方法。
【請求項４１】
同一の自律システム内で動作し、自律システム内の内部ネットワークを介して互いに接続されるノード装置と故障箇所推定装置とからなり、パケット転送に用いるネットワーク上でトポロジーに変化が生じた場合に、新たな正常な経路を確立するための動的経路制御を行う経路計算システムであって、
前記故障箇所推定装置は、
トポロジー変更箇所を推定する故障箇所推定手段と、
前記故障箇所推定手段により推定された前記トポロジー変更箇所をノード装置に通知する故障箇所通知手段とを備え、
前記ノード装置は、
他のノード装置から前記ネットワーク上の経路を決定するために必要となる情報を含む経路制御メッセージを受信するメッセージ受信手段と、
前記故障箇所推定装置から前記トポロジー変更箇所を受信する故障箇所受信手段と、
前記受信した経路制御メッセージを元に経路を決定する経路計算手段と、
他のノード装置で前記ネットワーク上の経路を決定するために必要な情報を含む経路制御メッセージを他のノード装置に送信するメッセージ送信手段と、
前記メッセージ受信手段により経路制御メッセージを受信すると、前記故障箇所受信手段により受信した前記トポロジー変更箇所と自ノード装置との距離に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作に関わる動作開始時間を算出する遅延計算手段と、
前記遅延計算手段により算出された動作開始時間に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作の実行を制御する実行制御手段と
を備えることを特徴とする経路計算システム。
【請求項４２】
同一の自律システム内で動作し、自律システム内の内部ネットワークを介して互いに接続されるノード装置と距離推定装置とからなり、パケット転送に用いるネットワーク上でトポロジーに変化が生じた場合に、新たな正常な経路を確立するための動的経路制御を行う経路計算システムであって、
前記距離推定装置は、
前記ノード装置とトポロジー変更箇所までの距離を推定する距離推定手段と、
前記距離推定手段により推定された距離を前記ノード装置に通知する距離通知手段とを備え、
前記ノード装置は、
他のノード装置から前記ネットワーク上の経路を決定するために必要となる情報を含む経路制御メッセージを受信するメッセージ受信手段と、
前記距離推定装置から前記トポロジー変更箇所までの距離を受信する距離受信手段と、
前記受信した経路制御メッセージを元に前記ネットワーク上の経路を決定する経路計算手段と、
他のノード装置で前記ネットワーク上の経路を決定するために必要な情報を含む経路制御メッセージを他のノード装置に送信するメッセージ送信手段と、
前記メッセージ受信手段により経路制御メッセージを受信すると、前記距離受信手段により受信した前記トポロジー変更箇所までの距離に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作に関わる動作開始時間を算出する遅延計算手段と、
前記遅延計算手段により算出された動作開始時間に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作の実行を制御する実行制御手段と
を備えることを特徴とする経路計算システム。
【請求項４３】
複数のノード装置の少なくとも１つのノード装置に接続され、パケット転送に用いるネットワーク上でトポロジーに変化が生じた場合に、新たな正常な経路を確立するための動的経路制御を行う経路計算装置であって、
前記少なくとも１つのノード装置から前記ネットワーク上の経路を決定するために必要となる情報を含む経路制御メッセージを受信するメッセージ受信手段と、
前記受信した経路制御メッセージを元に前記ネットワーク上の経路を決定する経路計算手段と、
他のノード装置で前記ネットワーク上の経路を決定するために必要な情報を含む経路制御メッセージを、前記少なくとも１つのノード装置を介して他のノード装置に送信するメッセージ送信手段と、
前記メッセージ受信手段により経路制御メッセージを受信すると、トポロジー変更箇所と前記少なくとも１つのノード装置との距離に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作に関わる動作開始時間を算出する遅延計算手段と、
前記遅延計算手段により算出された動作開始時間に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作の実行を制御する実行制御手段と
を備えることを特徴とする経路計算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動的に経路制御を行うネットワークシステムに係り、ノード装置、経路制御方法、経路計算システム、及び経路計算装置に関する。
本願は、２００８年１１月１９日に出願された特願２００８−２９５９２８号に基づき優先権を主張し、その内容をここに援用する。
【背景技術】
【０００２】
インターネットに代表されるネットワーク技術の普及に伴い、ネットワークに対する信頼性の向上が急務となっている。
従来、ネットワークを構成するノード装置や、リンクなどを予め冗長に構成しておき、動的経路制御を行うことで、ネットワーク信頼性の向上を行っていた。動的経路制御を行っているネットワークでは、ネットワークを構成するノード装置同士が互いの接続状況に関する情報を交換し、それらの情報を元に最適な経路を自律的に決定している。【０００３】
例えば、自身に接続するリンクや、隣接するノード装置などに故障（トポロジー変更）が発生した場合、その故障を検知したノード装置は、他のノード装置に通知を行う。このことにより、ネットワーク中の全ノード装置は、故障したノード装置や、リンクなどを除いた状態で経路計算を行い、新たな経路を決定する。
このように、動的経路制御は、故障が発生しても、残りのノード装置や、リンクなどのみで通信サービスを継続することを可能としている。【０００４】
このような動的経路制御を実現するために、標準化団体であるＩＥＴＦ（Internet Engineering Task Force）において、ＢＧＰ（Border Gateway Protocol）−４（例えば、非特許文献１参照）や、ＯＳＰＦ（Open Shortest Path First）（例えば、非特許文献２参照）、ＲＩＰ（Routing Information Protocol）（例えば、非特許文献３参照）といった経路制御プロトコルが標準化されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Y. Rekhter, T. Li and S. Hares : “A Border Gateway Protocol 4 (BGP-4)”, RFC 4271, pp. 1-6,InternetEngineering Task Force, 2006.
【非特許文献２】J. Moy : “OSPF Version 2”, RFC 2328, Internet Engineering Task Force, pp. 1-3,1998.
【非特許文献３】G. Malkin : “RIP Version 2”, RFC 2453, Internet Engineering Task Force, pp. 1-4, 1998.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、故障発生時のサービス停止時間を短くするためには、故障を検知したノード装置からネットワーク中の全ノードに対して、より短い時間で故障の通知を行う必要がある。この場合、故障の通知を受け取ったノード装置は、なるべく間を置かずに隣接するノード装置に通知を転送する必要がある。【０００７】
しかしながら、上述した非特許文献１、２、３では、ネットワーク中の各ノード装置がこのような動作を行った場合、各ノード装置の負荷が一時的に高くなるという問題がある。経路計算処理によりノード装置の負荷が高くなると、他の処理を行うことができなくなり、ノード装置としての役割を果たせなくなる可能性がある。このように処理負荷の増大は、ネットワークの安定性に影響を与える可能性がある。【０００８】
各ノード装置の負荷が高まるのを抑えるために、各種タイマが用いられている。例えば、通知受信後、その通知を隣接ルータに送るまでの時間を管理する転送タイマや、通知受信後経路計算を開始するまでの計算開始タイマが、これに相当する。【０００９】
このようなタイマに長めの値を設定すると、経路計算の負荷が一時的に高まることを防ぐことで、ネットワークの安定性向上を実現できるが、その分、故障発生時のサービス停止時間が長くなる。
このように、サービス停止時間とネットワークの安定性とは、トレードオフの関係にあり、両立することが難しいという問題があった。【００１０】
本発明は、このような事情を考慮してなされたものであり、その目的は、ネットワークの安定性を損なうことなく、サービス停止時間を短縮することができるノード装置、経路制御方法、経路計算システム、及び経路計算装置を提供することにある。
【課題を解決するための手段】
【００１１】
上述した課題を解決するために、本発明は、複数のノード装置間におけるパケット転送に用いるネットワーク上でトポロジーに変化が生じた場合に、新たな正常な経路を確立する動的経路制御を行うノード装置であって、他のノード装置から経路を決定するために必要となる情報を含む経路制御メッセージを受信するメッセージ受信手段と、前記受信した経路制御メッセージを元に前記ネットワーク上の経路を決定する経路計算手段と、他のノード装置で前記ネットワーク上の経路を決定するために必要な情報を含む経路制御メッセージを他のノード装置に送信するメッセージ送信手段と、前記メッセージ受信手段により経路制御メッセージを受信すると、トポロジー変更箇所と自ノード装置との距離に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作に関わる動作開始時間を算出する遅延計算手段と、前記遅延計算手段により算出された動作開始時間に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作の実行を制御する実行制御手段と、を備えることを特徴とするノード装置を提供する。【００１２】
また、上述した課題を解決するために、本発明は、複数のノード装置間におけるパケット転送に用いるネットワーク上でトポロジーに変化が生じた場合に、新たな正常な経路を確立するための経路制御方法であって、前記ネットワーク上の経路を決定するために必要となる情報を含む経路制御メッセージを受信する受信ステップと、前記受信した経路制御メッセージを元に前記ネットワーク上の経路を決定する経路計算ステップと、他のノード装置で前記ネットワーク上の経路を決定するために必要な情報を含む経路制御メッセージを他のノード装置に送信する送信ステップと、前記経路制御メッセージを受信すると、トポロジー変更箇所と自ノード装置との距離に基づいて、前記ネットワーク上の経路の決定動作と前記経路制御メッセージの送信動作とに関わる動作開始時間を算出する遅延計算ステップと、前記算出された動作開始時間に基づいて、前記経路の決定動作と前記経路制御メッセージの送信動作との実行を制御する実行制御ステップとを含むことを特徴とする経路制御方法も提供する。【００１３】
また、上述した課題を解決するために、本発明は、同一の自律システム内で動作し、自律システム内の内部ネットワークを介して互いに接続されるノード装置と故障箇所推定装置とからなり、パケット転送に用いるネットワーク上でトポロジーに変化が生じた場合に、新たな正常な経路を確立するための動的経路制御を行う経路計算システムであって、前記故障箇所推定装置は、トポロジー変更箇所を推定する故障箇所推定手段と、故障箇所推定手段により推定された前記トポロジー変更箇所をノード装置に通知する故障箇所通知手段とを備え、前記ノード装置は、他のノード装置から前記ネットワーク上の経路を決定するために必要となる情報を含む経路制御メッセージを受信するメッセージ受信手段と、前記故障箇所推定装置から前記トポロジー変更箇所を受信する故障箇所受信手段と、前記受信した経路制御メッセージを元に経路を決定する経路計算手段と、他のノード装置で前記ネットワーク上の経路を決定するために必要な情報を含む経路制御メッセージを他のノード装置に送信するメッセージ送信手段と、前記メッセージ受信手段により経路制御メッセージを受信すると、前記故障箇所受信手段により受信した前記トポロジー変更箇所と自ノード装置との距離に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作に関わる動作開始時間を算出する遅延計算手段と、前記遅延計算手段により算出された動作開始時間に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作の実行を制御する実行制御手段とを備えることを特徴とする経路計算システムも提供する。【００１４】
また、上述した課題を解決するために、本発明は、同一の自律システム内で動作し、自律システム内の内部ネットワークを介して互いに接続されるノード装置と距離推定装置とからなり、パケット転送に用いるネットワーク上でトポロジーに変化が生じた場合に、新たな正常な経路を確立するための動的経路制御を行う経路計算システムであって、前記距離推定装置は、前記ノード装置とトポロジー変更箇所までの距離を推定する距離推定手段と、前記距離推定手段により推定された距離を前記ノード装置に通知する距離通知手段とを備え、前記ノード装置は、他のノード装置から前記ネットワーク上の経路を決定するために必要となる情報を含む経路制御メッセージを受信するメッセージ受信手段と、前記距離推定装置から前記トポロジー変更箇所までの距離を受信する距離受信手段と、前記受信した経路制御メッセージを元に前記ネットワーク上の経路を決定する経路計算手段と、他のノード装置で前記ネットワーク上の経路を決定するために必要な情報を含む経路制御メッセージを他のノード装置に送信するメッセージ送信手段と、前記メッセージ受信手段により経路制御メッセージを受信すると、前記距離受信手段により受信した前記トポロジー変更箇所までの距離に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作に関わる動作開始時間を算出する遅延計算手段と、前記遅延計算手段により算出された動作開始時間に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作の実行を制御する実行制御手段とを備えることを特徴とする経路計算システムも提供する。【００１５】
また、上述した課題を解決するために、本発明は、複数のノード装置の少なくとも１つのノード装置に接続され、パケット転送に用いるネットワーク上でトポロジーに変化が生じた場合に、新たな正常な経路を確立するための動的経路制御を行う経路計算装置であって、前記少なくとも１つのノード装置から前記ネットワーク上の経路を決定するために必要となる情報を含む経路制御メッセージを受信するメッセージ受信手段と、前記受信した経路制御メッセージを元に前記ネットワーク上の経路を決定する経路計算手段と、他のノード装置で前記ネットワーク上の経路を決定するために必要な情報を含む経路制御メッセージを、前記少なくとも１つのノード装置を介して他のノード装置に送信するメッセージ送信手段と、前記メッセージ受信手段により経路制御メッセージを受信すると、トポロジー変更箇所と前記少なくとも１つのノード装置との距離に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作に関わる動作開始時間を算出する遅延計算手段と、前記遅延計算手段により算出された動作開始時間に基づいて、前記経路計算手段と前記メッセージ送信手段とによる経路制御動作の実行を制御する実行制御手段とを備えることを特徴とする経路計算装置も提供する。
【発明の効果】
【００１６】
この発明によれば、ネットワーク上でトポロジーに変化が生じたとき、ネットワークの安定性を損なうことなく、サービス停止時間を短縮することができるという利点が得られる。
【図面の簡単な説明】
【００１７】
【図１】本発明の第１実施形態によるノード装置の構成を示すブロック図である。
【図２】本第１実施形態によるノード装置の経路制御プロトコルによるメッセージ受信時の動作を説明するためのフローチャートである。
【図３】ＯＳＰＦメッセージにおけるＬＳＡ  ｈｅａｄｅｒの各フィールドの構成を示す概念図である。
【図４】ＯＳＰＦメッセージにおけるＲｏｕｔｅｒ  ＬＳＡの各フィールドの構成を示す概念図である。
【図５】ＯＳＰＦメッセージにおけるＮｅｔｗｏｒｋ  ＬＳＡの各フィールドの構成を示す概念図である。
【図６】本第１実施形態において、経路計算時に得られるツリー構造を示す概念図である。
【図７】本第１実施形態において、ＯＳＰＦによる故障箇所までの距離を求める手順を説明するためのフローチャートである。
【図８】本発明の第２実施形態によるノード装置の構成を示すブロック図である。
【図９】本第２実施形態によるノード装置１’と故障箇所推定システム２の構成例を示すブロック図である。
【図１０】本第２実施形態における経路制御プロトコルによるメッセージ受信時の動作を説明するためのフローチャートである。
【図１１】本発明の第３実施形態によるノード装置１０の構成を示すブロック図である。
【図１２】本発明の第４実施形態によるノード装置１０’の構成を示すブロック図である。
【発明を実施するための形態】
【００１８】
以下、本発明の一実施形態を、図面を参照して説明する。
【００１９】
Ａ．第１実施形態
まず、本発明の第１実施形態について説明する。
図１は、本発明の第１実施形態によるノード装置の構成を示すブロック図である。
図において、ノード装置１は、他のノード装置との間で経路情報等の交換を行い、パケット転送に用いる経路表を作成する経路制御部１１と、該経路制御部１１で作成された経路表の情報を元にパケットの転送を行うパケット転送部１２と、経路制御部１１が用いる各種タイマを管理するタイマ管理部１３と、現在時刻を保持するリアルタイムクロック１４と、外部のネットワーク３１〜３ｎと接続するためのネットワークインターフェイス２１〜２ｎとから構成されている。
【００２０】
経路制御部１１は、他のノード装置からの経路制御プロトコルにおけるメッセージを受信するメッセージ受信部１１１と、遅延実行部１３３から動作指示を受けたときに、他のノード装置に対して経路制御プロトコルにおけるメッセージを送信するメッセージ送信部１１２と、メッセージ受信部１１１により他のノード装置から取得した経路情報を保存しておく経路情報データベース１１３と、遅延実行部１３３から動作指示を受けたときに経路情報データベース１１３に保存された経路情報を用いて経路計算を行う経路計算部１１４と、メッセージ受信部１１１がメッセージを受信したとき、そのメッセージにより通知されるトポロジー変更箇所を用いて、メッセージ受信後、経路計算を開始するまでの時間、及び受信したメッセージを隣接ノード装置へ転送するまでの時間を計算する遅延計算部１１５とから構成されている。
【００２１】
また、パケット転送部１２は、ネットワークインターフェイス２１〜２ｎを介して受信したパケットの転送処理を行うルーティング処理部１２１と、パケットの宛先から、次の転送先と、どのネットワークインターフェイスから送出するかを決定するためのテーブルを持つ主経路表１２２とから構成されている。
【００２２】
タイマ管理部１３は、メッセージ受信後、経路計算を開始するまでの時間ｔｃ（タイマ値ｔｃ）を計時する計算開始遅延タイマ１３１と、受信したメッセージを隣接ノード装置へ転送するまでの時間ｔｔ（タイマ値ｔｔ）を計時するメッセージ転送遅延タイマ１３２と、計算開始遅延タイマ１３１、及びメッセージ転送遅延タイマ１３２のいずれかにおいて計時時間が設定されたタイマ値ｔｃ、ｔｔ分の時間が経過した旨の通知を受けたときに、それぞれ経路計算部１１４、もしくはメッセージ送信部１１２に動作開始の指示を出す遅延実行部１３３から構成されている。
【００２３】
なお、本第１実施形態では、経路制御部１１、タイマ管理部１３、及びリアルタイムクロック１４は、ノード装置１の内部にあるが、ノード装置１とは別の装置上に存在してもよい。
例えば、ノード装置１と別にサーバ装置を用意し、そのサーバ装置内に経路制御部１１、タイマ管理部１３、及びリアルタイムクロック１４が存在してもよい。
ノード装置１とサーバ装置との間は、専用のケーブルを用いて一対一で接続を行ってもよいし、ノード装置１と接続されたネットワーク３１、３２、…、３ｎのいずれかを介して接続を行ってもよい。
【００２４】
次に、本第１実施形態の動作について説明する。
図２は、本第１実施形態によるノード装置の経路制御プロトコルによるメッセージ受信時の動作を説明するためのフローチャートである。
経路制御プロトコルによるメッセージは、ネットワークを構成するノード装置や、リンクなどの故障によりトポロジーに変化があった場合に通知される以外にも、隣接ノード装置の監視などにも用いられる。
ここでいう経路制御プロトコルによるメッセージとは、何らかのトポロジーの変更を通知するメッセージを意味しており、以下、このようなメッセージを受信したときの動作について説明するものである。
【００２５】
まず、メッセージ受信部１１１により、隣接ノードからの経路制御プロトコルのメッセージが到着するのを待つ（ステップＳａ１）。
次に、遅延計算部１１５は、メッセージ受信部１１１が受け取った経路制御プロトコルのメッセージから、自ノードと障害箇所との間の距離ｄを求める（ステップＳａ２）。ここでの距離ｄは、自ノードから故障箇所（トポロジー変更箇所）までの最短パス上におけるノードの数（ホップ数）とする。
【００２６】
遅延計算部１１５は、予め設定された値ｔｉｃ、ｔｉｔを用いて、計算開始遅延タイマ１３１に設定するタイマ値ｔｃ＝ｔｉｃ×ｄ、及びメッセージ転送遅延タイマ１３２に設定するタイマ値ｔｔ＝ｔｉｔ×ｄを求める（ステップＳａ３）。
次に、遅延計算部１１５は、求めたタイマ値ｔｃ、及びタイマ値ｔｔを、それぞれ、計算開始遅延タイマ１３１、及びメッセージ転送遅延タイマ１３２に設定し、それぞれの計時動作を開始させる（ステップＳａ４）。
【００２７】
計算開始遅延タイマ１３１による計時時間が設定されたタイマ値ｔｃ分の時間が経過すると、遅延実行部１３３は、経路計算部１１４に経路計算の実行を行うよう指示を出す（ステップＳａ５）。
さらに、メッセージ転送遅延タイマ１３２による計時時間が設定されたタイマ値ｔｔ分の時間が経過すると、遅延実行部１３３は、メッセージ送信部１１２にメッセージの送信を行うよう指示を出す（ステップＳａ６）。
なお、ステップＳａ５、及びステップＳａ６は、設定されるタイマ値ｔｃ、ｔｔの値によっては、実行順序が入れ替わってもよい。
そして、全ての処理が終了すると、ステップＳａ１へ戻り、上述した処理を繰り返し実行する。
【００２８】
なお、ステップＳａ３では、タイマ値ｔｃ、ｔｔは、距離ｄに比例した値として算出されているが、これに限定されることなく、例えば、これらのタイマ値ｔｃ、ｔｔを距離ｄの自乗に比例する値にしてもよいし、あるいは、距離ｄを変数とする任意の関数により求められる値にしてもよい。
【００２９】
あるいは、次のように算出してもよい。
上述した方法で求められたタイマ値ｔｃ、またはタイマ値ｔｔと、予め設定により与えられた上限値ｔｃｍａｘ、ｔｔｍａｘとをそれぞれ比較し、後者（上限値）の方が小さかった場合に、後者の上限値ｔｃｍａｘ、ｔｔｍａｘをタイマ値ｔｃ、ｔｔとして用いる。つまり、タイマ値ｔｔ、ｔｃの値が大きくなりすぎてしまうのを防ぐために、タイマ値がとりうる値として、上限値ｔｃｍａｘ、ｔｔｍａｘを定めておくということである。
この上限値の設定は、計算により求められるタイマ値ｔｃ、ｔｔに対してのみでなく、距離ｄに対して適用してもよい。例えば、計算に用いる距離ｄが予め設定された上限値ｄｍａｘよりも大きかった場合、タイマ値のｔｃ、ｔｔの算出に、距離ｄの代わりに上限値ｄｍａｘを用いればよい。
【００３０】
また、タイマ値ｔｃ、ｔｔの計算は、次のように算出してもよい。
遅延計算部１１５により求められたタイマ値ｔｃ、またはタイマ値ｔｔと、予め設定により与えられた所定の値とを比較し、前者の方が大きかった場合、タイマ値ｔｃ、ｔｔを無限大とする。
タイマ値ｔｃ、ｔｔを無限大とするということは、つまり、計算開始遅延タイマ１３１とメッセージ転送遅延タイマ１３２とを動作させないということであり、経路計算部１１４による経路計算、及びメッセージ送信部１１２によるメッセージの再転送を行わないということである。
【００３１】
このとき、経路計算等は行われないが、経路情報データベース１１３には、今回受信した経路制御メッセージにより通知された変更分（経路情報）が反映されている。この後、別の経路制御メッセージを受信し、遅延計算部１１５により求められたタイマ値ｔｃ、ｔｔが無限大でなかったときには、前回の変更分を含む形で経路計算を行う。また、このとき、メッセージの送信に関しても、前回送信されなかった分の経路制御メッセージも同時に送信される。
同様な処理は、距離ｄに対する上限値ｄｍａｘにも適用することができる。計算に用いる距離ｄが上限値ｄｍａｘを超えていた場合、タイマ値ｔｃ、ｔｔを無限大として扱う。
【００３２】
また、計算に用いる距離ｄが予め定められた閾値ｄｔｈを超えているか否かで、異なる計算方法を用いてもよい。
例えば、距離ｄが閾値ｄｔｈを超えていなければ、距離ｄに比例するタイマ値ｔｃ、ｔｔを用い、そうでなければ、距離ｄの自乗に比例する値を用いるという具合にしてもよい。
ここでの閾値は１つでなく、複数の閾値を用いるようにしてもよい。例えば、閾値ｄｔｈ１，ｄｔｈ２（ｄｔｈ１＜ｄｔｈ２）の２つを用いるようにし、計算に用いる距離ｄについて、以下の３つのケースでそれぞれ異なる計算方法を用いるようにしてもよい。
【００３３】
（１）ｄ＜ｄｔｈ１
（２）ｄｔｈ１≦ｄ＜ｄｔｈ２
（３）ｄｔｈ２≦ｄ
【００３４】
なお、ステップＳａ３で用いる距離ｄとして、ホップ数の代わりに、２つのノード間のパスのコスト値の合計を用いてもよい。パスのコスト値とは、経由する各ノードと各リンクのコスト値の合計である。
ＯＳＰＦのように、各リンクにのみコスト値が設定されており、各ノードにコスト値が設定されていない場合には、パスのコスト値として、経由する各リンクのコスト値の合計を用いてもよい。
逆に各ノードにのみコスト値が設定されており、各リンクにコスト値が設定されていない場合には、パスのコスト値として、経由する各ノードのコスト値の合計を用いてもよい。
【００３５】
次に、ステップＳａ２における距離ｄを求めるプロセスについて、もう少し詳細に説明する。
本第１実施形態におけるこのプロセスでは、図１に示す経路計算部１１４において、一般的なＯＳＰＦにおける経路計算を行う過程で生成されるツリー構造の情報を用いる。このため、まず、ＯＳＰＦにおける経路計算とそのために利用される情報とについて説明する。
【００３６】
ＯＳＰＦにより運用されているネットワーク中の各ノード装置間では、ＬＳＡ（Link State Advertisement）と呼ばれる単位で情報が交換され、経路計算に用いられている。図３乃至図５は、主に使用されるＬＳＡのパケットフォーマットを示す概念図である。
図３は、ＯＳＰＦメッセージにおけるＬＳＡ  ｈｅａｄｅｒと呼ばれる部分のフォーマットであり、各種ＬＳＡの種類を問わず共通に使用される部分である。
図４は、ＯＳＰＦメッセージにおけるＲｏｕｔｅｒ  ＬＳＡのパケットフォーマットを表しており、図３で示したＬＳＡ  ｈｅａｄｅｒに続いて配置される。
【００３７】
Ｒｏｕｔｅｒ  ＬＳＡでは、図３のフィールド４２（Ｌｉｎｋ  Ｓｔａｔｅ  Ｔｙｐｅ）に、このＬＳＡがＲｏｕｔｅｒ  ＬＳＡであることを示す数値「１」が格納される。
図３のフィールド４３（Ｌｉｎｋ  Ｓｔａｔｅ  ＩＤ）には、ノード装置（ルータ）毎に一意に割り当てられた番号（Ｒｏｕｔｅｒ  ＩＤ）が格納される。
ＬＳＡ  ｈｅａｄｅｒに続いて配置される図４の部分では、フィールド５３〜５７で一組となり、ノード装置に接続するリンクに関する情報が格納される。
また、ノード装置に接続されるリンクが複数存在する場合には、同様な情報が図４のフィールド５８以降のフィールドに続けて格納される。
このように、Ｒｏｕｔｅｒ  ＬＳＡは、ノード装置（ルータ）がどのリンクと接続しているかを表している。
【００３８】
次に、図５は、ＯＳＰＦメッセージにおけるＮｅｔｗｏｒｋ  ＬＳＡのパケットフォーマットを表しており、図３で示したＬＳＡ  ｈｅａｄｅｒに続いて配置される。
Ｎｅｔｗｏｒｋ  ＬＳＡでは、図３のフィールド４２（Ｌｉｎｋ  Ｓｔａｔｅ  Ｔｙｐｅ）に、このＬＳＡがＮｅｔｗｏｒｋ  ＬＳＡであることを示す数値「２」が格納される。
図３のフィールド４３（Ｌｉｎｋ  Ｓｔａｔｅ  ＩＤ）には、そのリンクに接続されているノード装置（ルータ）のうち、指名ルータと呼ばれる代表となるノード装置（ルータ）を一意に識別するためのＩＤ（Ｒｏｕｔｅｒ  ＩＤ）が格納される。
図５のフィールド７１〜７ｎ（Ａｔｔａｃｈｅｄ  Ｒｏｕｔｅｒ  １〜ｎ）には、このリンクに接続されるノード装置のＲｏｕｔｅｒ  ＩＤが格納される。
このように、Ｎｅｔｗｏｒｋ  ＬＳＡは、当該リンクにそのルータが接続しているかを表している。
【００３９】
ＯＳＰＦでは、経路計算を行う際に、収集したＲｏｕｔｅｒ  ＬＳＡ、及びＮｅｔｗｏｒｋ  ＬＳＡの情報を繋ぎ合わせることで得られるネットワークのトポロジー情報を利用している。そして、このトポロジー情報に対して最短経路問題を解くためのアルゴリズムであるダイクストラアルゴリズムを適用することで、最短経路を決定している。
図６は、本第１実施形態において、経路計算時に得られるツリー構造を示す概念図である。
この計算過程において、図６に示すような、自分自身を表すＲｏｕｔｅｒ  ＬＳＡを頂点（Ｌ１１）とするツリー構造の情報を得ることができる。
本第１実施形態では、故障箇所からノード装置１までの距離ｄを求めるために、このツリー構造の情報を用いる。
【００４０】
図７は、本第１実施形態において、ＯＳＰＦによる故障箇所までの距離を求める手順を説明するためのフローチャートである。
まず、経路計算部１１４において経路計算を行った際に得られるツリー構造の情報を遅延計算部１１５へと送る（ステップＳｂ１）。これは、一回前の経路計算時に得られるツリー構造の情報を用いて、次の経路計算、もしくはメッセージ送信のためのタイマ値ｔｃ、ｔｔを決定するということを示す。
次に、受信したメッセージ中のＬＳＡを参照し、そのＬＳＡがツリー構造のどの部分に相当するかを調べる（ステップＳｂ２）。
【００４１】
次に、ステップＳｂ２において見つけたツリー構造上のＬＳＡと、このツリーのルートとの間にいくつのＲｏｕｔｅｒ  ＬＳＡが存在するかを調べる（ステップＳｂ３）。
そして、ステップＳｂ３で求めた値に「１」を加えた数を距離ｄとする（ステップＳｂ４）。
例えば、図６におけるＲｏｕｔｅｒ（ＬＳＡ）Ｌ５３と接続するＮｅｔｗｏｒｋ（ＬＳＡ）Ｌ６１との間に故障が発生した場合について説明を行う。
このとき、Ｒｏｕｔｅｒ（ＬＳＡ）５３が表すノード装置は、Ｎｅｔｗｏｒｋ（ＬＳＡ）Ｌ６１が表すリンクと接続関係がなくなるため、Ｒｏｕｔｅｒ（ＬＳＡ）Ｌ５３が更新され、各ノード装置に通知される。
【００４２】
図６に示すツリー構造の情報を管理しているノード装置が当該通知を受け取った時、ステップＳｂ３における処理で、Ｒｏｕｔｅｒ（ＬＳＡ）Ｌ５３とルートであるＲｏｕｔｅｒ（ＬＳＡ）Ｌ１１との間にあるＲｏｕｔｅｒ（ＬＳＡ）の数を調べる。
該当するのは、Ｒｏｕｔｅｒ（ＬＳＡ）Ｌ３４の１つのみであるため、これに１を足して、このときの距離は「２」となる。
【００４３】
なお、本第１実施形態においては、ＩＰｖ４の経路制御プロトコルであるＯＳＰＦを用いて説明を行っているが、ＩＰｖ６における経路制御でも、同様な仕組みで動作可能である。
【００４４】
上述した第１実施形態によれば、負荷増大防止のために用いられているタイマに、故障箇所からノード装置自身までの距離に応じたタイマ値を用いることにより、故障箇所から近いノード装置に対しては、より小さなタイマ値を用いることで、サービス停止時間を短縮することができる一方、故障箇所から遠いノード装置に対しては、大きなタイマ値を用いることで、経路計算における負荷が一時的に高まることを抑え、ネットワークの安定性向上させることができる。
【００４５】
また、このようにすることで、故障箇所から近いノード装置では、従来技術よりも経路計算負荷が高まる可能性もあるが、ネットワーク全体としてみると、平均的に経路計算負荷を低くすることができる。
【００４６】
Ｂ．第２実施形態
次に、本発明の第２実施形態について説明する。
図８は、本発明の第２実施形態によるノード装置の構成を示すブロック図である。
図において、本第２実施形態は、前述した第１実施形態による構成（図１）と比較して、故障箇所情報受信部１１６を備えている点で異なる。
【００４７】
ＢＧＰなどパスベクトル型の経路制御プロトコルでは、通知されるプレフィックスは、ＡＳ（Autonomous System）パスと共に通知される。リンク故障などが発生した場合には、代替の経路が新たなパスと共に通知されるが、通知された情報からだけでは、どこに故障が発生したのかは分からない。
しかし、参考文献１（立花  篤男、阿野  茂浩、鶴  正人：“シミュレーション解析に基づくＢＧＰ経路障害箇所推定法の提案”、２００８年電子情報通信学会通信ソサイエティ大会、Ｂ−１６−６、ｐ．３１４、２００８．）などでは、各種情報から故障箇所を推定する技術が研究開発されている。
このため、本第２実施形態によるノード装置１’では、後述する故障箇所推定システムにより推定された故障箇所に関する情報の通知を故障箇所情報受信部１１６により受信し、その情報を元にタイマ値ｔｃ、ｔｔの決定を行う。
【００４８】
図９は、本第２実施形態によるノード装置１’と故障箇所推定システム２の構成例を示すブロック図である。
図において、ノード装置１’と故障箇所推定システム２との間は、ＢＧＰにおける同一の自律システム内で動作し、自律システム内の内部ネットワーク４を介して接続される。また、故障箇所推定システム２は、自律システムの外部のネットワーク５とは、内部ネットワーク４、もしくはノード装置１’を介して接続されている。
図９の故障箇所推定システム２内には、故障箇所の推定を行う故障箇所推定部２１０、及び故障箇所推定部により推定された故障箇所をノード装置１’に通知する故障箇所通知部２２０が備えられている。
【００４９】
図１０は、本第２実施形態における経路制御プロトコルによるメッセージ受信時の動作を説明するためのフローチャートである。
なお、図１０において、ステップＳｃ１、Ｓｃ５、Ｓｃ６、Ｓｃ７、及びステップＳｃ８は、前述した第１実施形態における動作を示している図２のステップＳａ１、Ｓａ３、Ｓｃ４、Ｓｃ５、及びＳｃ６と同じであり、ステップＳｃ１とＳｃ４の間に新たにステップＳｃ２、Ｓｃ３が追加されている点で異なるとともに、ステップＳｃ４（図２のステップＳａ２に対応）の動作が一部異なる。
【００５０】
ステップＳｃ２では、故障箇所推定システム２が隣接ノードから到着したメッセージから故障箇所を推定し、ノード装置１’へと通知を行う。
さらに、ステップＳｃ３では、ノード装置１’における故障箇所情報受信部１１６は、故障箇所推定システム２から推定された故障箇所に関する情報が到着するのを待つ。
さらに、ステップＳｃ４では、遅延計算部１１５は、故障箇所情報受信部１１６から通知された障害箇所と自ノード間の距離ｄを求める。
前述した第１実施形態における距離ｄはノードのホップ数であったが、本第２実施形態では、ホップ数の代わりに、経由するＡＳパス数を用いてもよい。
【００５１】
また、本第２実施形態では、故障箇所を外部にある故障箇所推定システム２で推定しているが、故障箇所までの距離ｄについても、外部のシステムで求めるようにしてもよい。この場合、本第２実施形態におけるノード装置１’は、外部システムから故障箇所までの距離ｄを受け取り、受け取った距離ｄを元に経路制御に用いるタイマ値ｔｃ、ｔｔを求めるようにしてもよい。
【００５２】
上述した第２実施形態によれば、外部の故障箇所推定システム２で故障箇所、または故障箇所までの距離を推定し、ノード装置１’では、外部の故障箇所推定システム２から受信した故障箇所、または故障箇所までの距離を用いて、経路制御に用いるタイマ値ｔｃ、ｔｔを求めるようにしたので、経路制御に係る負荷をより軽減することができ、ネットワークの安定性をより向上させることができる。
【００５３】
Ｃ．第３実施形態
次に、本発明の第３実施形態について説明する。
図１１は、本発明の第３実施形態によるノード装置１０の構成を示すブロック図である。
図において、本第３実施形態は、前述した第１実施形態による構成（図１）と比較して、遅延管理部１３４を備えている点で異なる。
【００５４】
本第３実施形態では、計算開始遅延タイマ１３１、もしくはメッセージ転送遅延タイマ１３２の動作中に、さらに、経路制御プロトコルにおけるメッセージを受信した場合への対応を行っている。
前述した第１実施形態と同様に、遅延計算部１１５において、経路計算開始、もしくはメッセージの再転送開始までのタイマ値ｔｃ、ｔｔを決定し、遅延管理部１３４へと送る。
遅延管理部１３４は、遅延計算部１１５から送られてきた経路計算開始までのタイマ値ｔｃと、計算開始遅延タイマ１３１における現在値との比較を行う。
そして、遅延計算部１１５から送られてきた経路計算開始までのタイマ値ｔｃの方が小さい場合に、計算開始遅延タイマ１３１の値を、遅延計算部１１５から送られてきたタイマ値ｔｃで更新する。
【００５５】
同様に、遅延管理部１３４は、遅延計算部１１５から送られてきたメッセージ転送までのタイマ値ｔｔとメッセージ転送遅延タイマ１３２における現在値とを比較し、前者の値が小さい場合に、メッセージ転送遅延タイマ１３２の値を、遅延計算部１１５から送られてきたメッセージ転送までのタイマ値ｔｔで更新する。
【００５６】
上述した第３実施形態によれば、ネットワークトポロジーの変更が複数箇所で起きた場合にも対応することができる。
【００５７】
Ｄ．第４実施形態
次に、本発明の第４実施形態について説明する。
図１２は、本発明の第４実施形態によるノード装置１０’の構成を示すブロック図である。
図において、本第４実施形態は、前述した第１実施形態による構成（図１）と比較して、計算開始遅延タイマ１３１、及びメッセージ転送遅延タイマ１３２の代わりに、経路更新開始遅延タイマ３１５が存在する点が異なる。
【００５８】
本第４実施形態による遅延計算部１１５は、第１実施形態と同様な方法で、経路更新を開始するまでのタイマ値ｔｒを計算し、経路更新開始遅延タイマ３１５に設定する。
経路更新開始遅延タイマ３１５は、タイマ値ｔｒが設定されると、該タイマ値ｔｒが「０」になるまでのカウントダウン動作を開始する。
遅延実行部１３３は、経路更新開始遅延タイマ３１５の値が「０」になると、経路計算部１１４に対し、経路計算求められた経路を用いて、主経路表１２２の更新を開始するよう指示を行う。
【００５９】
本第４実施形態によれば、経路表更新時のパケット転送部１２の動作の不安定さに起因するネットワークにおける安定性の低下を、主経路表１２２の更新自体を遅らせることにより、時間的、空間的に分散し、ネットワークの安定性をより向上させることができる。
【産業上の利用可能性】
【００６０】
本発明の活用例として、主にキャリアバックボーンのＩＰネットワークにおける高可用性ルータに適用することを想定している。
【符号の説明】
【００６１】
１，１’，１０，１０’  ノード装置
１１  経路制御部
１２  パケット転送部
１３  タイマ管理部
１４  リアルタイムクロック
２１〜２ｎ  ネットワークインターフェイス
３１〜３ｎ  外部のネットワーク
１１１  メッセージ受信部
１１２  メッセージ送信部
１１３  経路情報データベース
１１４  経路計算部
１１５  遅延計算部
１１６  故障箇所情報受信部
１２１  ルーティング処理部
１２２  主経路表
１３１  計算開始遅延タイマ
１３２  メッセージ転送遅延タイマ
１３３  遅延実行部
１３４  遅延管理部
１３５  経路更新開始遅延タイマ
２  故障箇所推定システム
２１０  故障箇所推定部
２２０  故障箇所通知部
４  内部ネットワーク
５  外部ネットワーク
【図１】
2010058537.tif 000003
【図２】
2010058537.tif 000004
【図３】
2010058537.tif 000005
【図４】
2010058537.tif 000006
【図５】
2010058537.tif 000007
【図６】
2010058537.tif 000008
【図７】
2010058537.tif 000009
【図８】
2010058537.tif 000010
【図９】
2010058537.tif 000011
【図１０】
2010058537.tif 000012
【図１１】
2010058537.tif 000013
【図１２】
2010058537.tif 000014
【国際調査報告】
2010058537.tif 000015
2010058537.tif 000016