(57)【特許請求の範囲】
【請求項１】
複数のノードをリンクにより接続することで構成されるネットワークに流れるパケットの経路を更新する経路情報更新システムであって、
各ノードは、
前記ネットワークに属する前記各ノードに接続される前記リンクのインタフェースの情報であるリンクステートが格納される網トポロジ情報ＤＢを備え、
接続される前記リンクが変更された場合に、隣接する他のノードに前記リンクステートをリンクステート通知として送信するリンクステート送信部と、
前記リンクステート通知を受信した場合に、受信したリンクステート通知に基づいて前記網トポロジ情報ＤＢを更新するリンクステート受信部と、
前記網トポロジ情報ＤＢを更新した場合に、
受信したリンクステート通知を隣接する他の前記ノードへさらに転送するリンクステート転送部と、
前記網トポロジ情報ＤＢに基づいて、現用系経路の計算を行う現用系経路計算部と、
前記網トポロジ情報ＤＢに基づいて、前記現用系経路が使用できない場合に使用する予備系経路の計算を行う予備系経路計算部と、
前記リンクステート転送部、前記現用系経路計算部、及び前記予備系経路計算部の処理の順番を制御するプロトコル制御部と、を備え、
前記プロトコル制御部は、
前記リンクステート転送部、及び前記現用系経路計算部の処理が終了した後に、前記予備系経路計算部の処理を行わせる、
ことを特徴とする経路情報更新システム。
【請求項２】
前記プロトコル制御部は、
前記リンクステート転送部、及び前記現用系経路計算部の処理が終了した後に、前記予備系経路計算部の処理を行わせるのに代えて、
前記予備系経路計算部の処理が終了した後に、前記リンクステート転送部、及び前記現用系経路計算部の処理を行わせる、
ことを特徴とする請求項１に記載の経路情報更新システム。
【請求項３】
前記プロトコル制御部は、
前記リンクステート転送部、及び前記現用系経路計算部の処理が終了した後に、前記予備系経路計算部の処理を行わせるのに代えて、
前記現用系経路計算部、及び前記予備系経路計算部の処理が終了した後に、前記リンクステート転送部の処理を行わせる、
ことを特徴とする請求項１に記載の経路情報更新システム。
【請求項４】
複数のノードをリンクにより接続することで構成されるネットワークと、前記ネットワークに流れるパケットの経路を計算する経路制御装置とで構成される経路情報更新システムであって、
前記経路制御装置は、
前記ネットワークに属する前記各ノードに接続される前記リンクのインタフェースの情報であるリンクステートが格納される網トポロジ情報ＤＢを備え、
前記ノードに接続される前記リンクが変更された場合に、当該ノードから前記リンクステートを収集し、収集した前記リンクステートに基づいて前記網トポロジ情報ＤＢを更新するリンクステート収集部と、
前記網トポロジ情報ＤＢを更新した場合に、
前記網トポロジ情報ＤＢに基づいて、前記ノードそれぞれの現用系経路の計算を行う現用系経路計算部と、
前記網トポロジ情報ＤＢに基づいて、前記現用系経路が使用できない場合に使用する前記ノードそれぞれの予備系経路の計算を行う予備系経路計算部と、
前記ノードに対して、前記予備系経路計算部が計算した前記予備系経路を配信した後に、前記現用系経路計算部が計算した前記現用系経路を各ノードに対して配信する経路配信部と、を備える、
ことを特徴とする経路情報更新システム。
【請求項５】
複数のノードをリンクにより接続することで構成されるネットワークに流れるパケットの経路を更新する経路情報更新システムの経路情報更新方法であって、
各ノードは、
前記ネットワークに属する前記各ノードに接続される前記リンクのインタフェースの情報であるリンクステートが格納される網トポロジ情報ＤＢを備え、
接続される前記リンクが変更された場合に、隣接する他のノードに前記リンクステートをリンクステート通知として送信するリンクステート送信ステップと、
前記リンクステート通知を受信した場合に、受信したリンクステート通知に基づいて前記網トポロジ情報ＤＢを更新するリンクステート受信ステップと、
前記網トポロジ情報ＤＢを更新した場合に、
受信したリンクステート通知を隣接する他の前記ノードへさらに転送するリンクステート転送ステップと、
前記網トポロジ情報ＤＢに基づいて、現用系経路の計算を行う現用系経路計算ステップと、
前記網トポロジ情報ＤＢに基づいて、前記現用系経路が使用できない場合に使用する予備系経路の計算を行う予備系経路計算ステップと、の処理を実行し、
前記処理の手順は、
前記リンクステート転送ステップ、及び前記現用系経路計算ステップの処理が終了した後に、前記予備系経路計算ステップの処理を実行する、
ことを特徴とする経路情報更新方法。
【請求項６】
前記処理の手順は、
前記リンクステート転送ステップ、及び前記現用系経路計算ステップの処理が終了した後に、前記予備系経路計算ステップの処理を実行するのに代えて、
前記予備系経路計算ステップの処理が終了した後に、前記リンクステート転送ステップ、及び前記現用系経路計算ステップの処理を実行する、
ことを特徴とする請求項５に記載の経路情報更新方法。
【請求項７】
前記処理の手順は、
前記リンクステート転送ステップ、及び前記現用系経路計算ステップの処理が終了した後に、前記予備系経路計算ステップの処理を実行するのに代えて、
前記現用系経路計算ステップ、及び前記予備系経路計算ステップの処理が終了した後に、前記リンクステート転送ステップの処理を実行する、
ことを特徴とする請求項５に記載の経路情報更新方法。
【請求項８】
複数のノードをリンクにより接続することで構成されるネットワークと、前記ネットワークに流れるパケットの経路を計算する経路制御装置とで構成される経路情報更新システムの経路情報更新方法であって、
前記経路制御装置は、
前記ネットワークに属する前記各ノードに接続される前記リンクのインタフェースの情報であるリンクステートが格納される網トポロジ情報ＤＢを備え、
前記ノードに接続される前記リンクが変更された場合に、当該ノードから前記リンクステートを収集し、収集した前記リンクステートに基づいて前記網トポロジ情報ＤＢを更新するリンクステート収集ステップと、
前記網トポロジ情報ＤＢを更新した場合に、
前記網トポロジ情報ＤＢに基づいて、前記ノードそれぞれの現用系経路の計算を行う現用系経路計算ステップと、
前記網トポロジ情報ＤＢに基づいて、前記現用系経路が使用できない場合に使用する前記ノードそれぞれの予備系経路の計算を行う予備系経路計算ステップと、
前記ノードに対して、前記予備系経路計算ステップで計算した前記予備系経路を配信した後に、前記現用系経路計算ステップで計算した前記現用系経路を各ノードに対して配信する経路配信ステップと、を実行する、
ことを特徴とする経路情報更新方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰ(Internet Protocol)ネットワークなどのパケット交換網における、設備増減設時の経路情報更新システム、及び経路情報更新方法に関する。
【背景技術】
【０００２】
ネットワークにおいては、予期しない故障の発生に対して迅速に転送経路を切り替えることで故障復旧を行い、転送品質の維持を行うことが重要である。ＩＰネットワークにおける故障復旧方式として、ＯＳＰＦ(Open Shortest Path First)等のルーチングプロトコルを用いた動的な復旧方式がある（非特許文献１参照）。
【０００３】
ＯＳＰＦでは、故障を検知したノードは、全ノードに故障情報を通知（フラッディング）する。故障情報を受け取ったノードは、故障箇所を除いた網トポロジ情報をもとに予備系経路を計算することで、自動的に転送経路を切り替えることが可能となる。しかし、ＯＳＰＦでは故障発生後に予備系経路を計算するため、故障の復旧に秒単位の時間を必要とする問題がある。また、故障情報の通知や予備系経路の計算は、ＩＰネットワークの規模に依存して増加する。
【０００４】
このような問題点を解決する方法として、事前に予備系経路を計算しておくことで高速な故障復旧を実現するＩＰ−ＦＲＲ(IP Fast Reroute)方式が提案されている（非特許文献２参照）。ＩＰ−ＦＲＲ方式は、事前に予備トポロジを作成し、故障発生時には該当故障箇所をプロテクトする（迂回する）予備トポロジに従った転送経路に切り替えることで故障復旧を行う。
【０００５】
ＩＰ−ＦＲＲ方式における予備トポロジを用いた故障復旧方法の具体例を図１０を用いて説明する。図１０（ａ）は、通常のトポロジの一例を示し、図１０（ｂ）は、予備トポロジの一例を示す。
【０００６】
まず、ノードは、リンク断絶に備えたコンフィグレーション（予備トポロジ）を予め用意しておく。例えば、ノードは、リンク１−２（ノード番号「１」のノードと、ノード番号「２」のノードとの間のリンク）が断絶した場合に備え、このリンク１−２をプロテクトリンクとする予備トポロジを事前に作成する。なお、予備トポロジにおけるプロテクトリンクのリンクコストは、このプロテクトリンクが経路として選択されないようにするため、設定可能な最大値を付与する。これにより、予備トポロジ上でリンクコストの総和が最小となる最小コストルーティングにより経路を計算すると、プロテクトリンクを使用しない経路が算出される。この予備トポロジはすべてのノードに投入され、すべてのノードは予備トポロジに従った予備系経路が事前に（トラヒック転送前に）計算される。
【０００７】
ここで、ノード番号「１」のノードをsrc（発ノード）とし、ノード番号「５」のノードをdst（着ノード）とする経路上において、リンク１−２の故障を検出した場合を考える。例えば、図１０（ａ）に示す通常のトポロジ上で、（１）リンク１−２の故障を検出すると、故障検出ノード（ノード番号「１」のノード）は、故障リンクをプロテクトする予備トポロジＡに従ってパケットをノード番号「４」のノードに転送する(図１０（ｂ）参照)。このとき、故障検出ノード（ノード番号「１」のノード）は、リンク１−２が故障したことを知っているので、予備トポロジＡを使用すれば故障箇所を迂回できることを知っている。
【０００８】
しかし、他のノード（例えば、ノード番号「４」のノード）は、故障箇所を把握できていない。そこで、故障検出ノード（ノード番号「１」のノード）は、（２）使用する予備トポロジＡを選択し、この予備トポロジＡのＩＤをノード番号「４」のノードに転送するパケットのヘッダに付与する。そして、予備系経路上に存在する他のノード（ここでは、ノード番号「４」のノード）はパケットを受信すると、（３）このパケットのヘッダを参照し、使用すべき予備トポロジＡを選択し、その選択した予備トポロジＡに従った予備系経路であるノード番号「５」のノードにパケットを転送する。
【０００９】
このように、従来検討されてきたＩＰ−ＦＲＲ方式は、基準となるトポロジがノードの増設や減設がされずに固定であることを前提として、各リンクをプロテクトする予備トポロジを複数個作成することで、任意の単一リンクの故障に対する高速復旧を実現する。なお、予備トポロジの接続性が担保される限り、予備トポロジにおいて複数個所のリンクをプロテクトしてもよい。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】“OSPF Version 2”、[online]、April 1998、IETF、[平成２３年７月２５日検索]、インターネット<URL: http://www.ietf.org/rfc/rfc2328.txt>
【非特許文献２】A.Kyalbein, A.F.Hansen, T.Cicic, S.Gjessing, and O.Lysne, “Fast IP Network Recovery using Multiple Routing Configurations,” in Proceedings of INFOCOM, Apr.2006
【発明の概要】
【発明が解決しようとする課題】
【００１１】
上述した通り、従来検討されてきたＩＰ−ＦＲＲ方式では基準となるトポロジが固定であることを前提としている。トポロジは、設備の増設、減設等を契機に変化するため、トポロジの変化に伴って現用系経路だけでなくＩＰ−ＦＲＲのための予備系経路についても再計算や設定を行う必要がある。
しかしながら、非特許文献２では、トポロジが変更された場合が考慮されていないので、トポロジが変更された場合に現用系経路及び予備系経路を再計算することができなかった。
【００１２】
本発明は前記問題に鑑みてなされたものであり、トポロジの変更時に、リンクステート通知、現用系経路計算、予備系経路計算の順番を最適に設定して経路を更新することができる経路情報更新システム、及び経路情報更新方法を提供することを課題とする。
【課題を解決するための手段】
【００１３】
前記課題を解決するため、本発明に係る経路情報更新システムは、複数のノードをリンクにより接続することで構成されるネットワークに流れるパケットの経路を更新する経路情報更新システムであって、各ノードが、前記ネットワークに属する前記各ノードに接続される前記リンクのインタフェースの情報であるリンクステートが格納される網トポロジ情報ＤＢを備え、接続される前記リンクが変更された場合に、隣接する他のノードに前記リンクステートをリンクステート通知として送信するリンクステート送信部と、前記リンクステート通知を受信した場合に、受信したリンクステート通知に基づいて前記網トポロジ情報ＤＢを更新するリンクステート受信部と、前記網トポロジ情報ＤＢを更新した場合に、受信したリンクステート通知を隣接する他の前記ノードへさらに転送するリンクステート転送部と、前記網トポロジ情報ＤＢに基づいて、現用系経路の計算を行う現用系経路計算部と、前記網トポロジ情報ＤＢに基づいて、前記現用系経路が使用できない場合に使用する予備系経路の計算を行う予備系経路計算部と、前記リンクステート転送部、前記現用系経路計算部、及び前記予備系経路計算部の処理の順番を制御するプロトコル制御部と、を備え、前記プロトコル制御部が、前記リンクステート転送部、及び前記現用系経路計算部の処理が終了した後に、前記予備系経路計算部の処理を行わせる、ことを特徴とする。
【００１４】
このようにすることで、本発明に係る経路情報更新システムは、経路の計算前にリンクステート通知を他のノードへ転送することができる。したがって、本発明に係る経路情報更新システムは、通信ネットワーク内の各ノードに対して、より早くリンクステート通知を送信することができる。特に、設備減設時には、即時的に減設情報(リンクステート通知)を通知することで、消失した設備（リンク）を使用することを回避することができる。
【００１５】
また、本発明に係る経路情報更新システムは、前記プロトコル制御部が、前記リンクステート転送部、及び前記現用系経路計算部の処理が終了した後に、前記予備系経路計算部の処理を行わせるのに代えて、前記予備系経路計算部の処理が終了した後に、前記リンクステート転送部、及び前記現用系経路計算部の処理を行わせる、ことを特徴とする。
【００１６】
このようにすることで、本発明に係る経路情報更新システムは、予備系経路の計算をリンクステート通知の転送に先立って行うことができる。したがって、本発明に係る経路情報更新システムは、増設されたノードで予備系経路の計算が終了しておらずに現用系経路のみの計算が終了している状態で故障が発生した場合に、物理的には迂回できる経路が存在するにも関わらず予備系経路の計算が終了していないためにパケット転送ができない状態が発生しない。つまり、予備系経路が先立って計算されているので、現用系経路が故障した場合に、物理的な接続性が担保される限り予備系経路を用いて確実にパケットを送信できる。
【００１７】
また、本発明に係る経路情報更新システムは、前記プロトコル制御部が、前記リンクステート転送部、及び前記現用系経路計算部の処理が終了した後に、前記予備系経路計算部の処理を行わせるのに代えて、前記現用系経路計算部、及び前記予備系経路計算部の処理が終了した後に、前記リンクステート転送部の処理を行わせる、ことを特徴とする。
【００１８】
このようにすることで、本発明に係る経路情報更新システムは、リンクステート通知の転送前に現用系経路及び予備系経路の計算を完了できる。したがって、本発明に係る経路情報更新システムは、リンクステート通知の転送元の現用系経路の計算が完了する前に、転送先の現用系経路の計算が完了してしまい、転送元から転送先へのＩＰパケットの転送時に転送元でＩＰパケットをロス(破棄)する現象が発生しない。
【発明の効果】
【００１９】
本発明に係る経路情報更新方法、及び経路情報更新システムによれば、トポロジの変更時に、リンクステート通知、現用系経路計算、予備系経路計算の順番を最適に設定して経路を更新することができる。
【図面の簡単な説明】
【００２０】
【図１】第１実施形態に係る通信ネットワークの構成図である。
【図２】第１実施形態に係るノードの機能構成図である。
【図３】従来のノードの処理手順（ＯＳＰＦ）を示すフローチャートである。
【図４】第１実施形態に係るノードの処理手順（ケース１）を示すフローチャートである。
【図５】第１実施形態に係るノードの処理手順（ケース２）を示すフローチャートである。
【図６】第１実施形態に係るノードの処理手順（ケース３）を示すフローチャートである。
【図７】第１実施形態に係る通信ネットワークの概略図である。図７（ａ）は、通信ネットワークに、１つのノードを物理的に増設した状態を示し、図７（ｂ）は、増設したノード及び隣接するノードのインタフェースの設定及びプロトコルの設定を行っている状態を示し、図７（ｃ）は、増設したノードが通信ネットワークのトポロジに関する情報を取得する様子を示し、図７（ｄ）は、増設したノードから送信されたリンクステート通知が他のノードに転送される様子を示す。
【図８】第２実施形態に係る通信ネットワークの構成図である。
【図９】第２実施形態に係る制御サーバの機能構成図である。
【図１０】ＩＰ−ＦＲＲ方式における予備トポロジを用いた故障復旧方法を説明するための図である。
【発明を実施するための形態】
【００２１】
[発明の概要]
従来からある方式であるＯＳＰＦでは、ネットワークトポロジの変化に伴って、(１)他のノードへの「インタフェースの情報（リンクステート）」の通知、(２)現用系経路の計算、の順番に処理を行っていた。本発明は、(１)他のノードへのリンクステートの通知、(２)現用系経路の計算、に加えて(３)予備系経路の計算の処理を考慮に入れた最適な処理の順番を提案する。
以下、本発明の実施の形態を、第１実施形態及び第２実施形態に分けて説明する。第１実施形態では、ネットワークトポロジの変化に伴ってそれぞれのノードが経路計算を行う分散型処理について説明し、第２実施形態では、ネットワークトポロジの変化に伴ってネットワークを制御するネットワーク制御装置が経路計算を行い、それぞれのノードに計算した経路を配布する集中型処理について説明する。
【００２２】
以下、図面を参照して、本発明の実施の形態につき詳細に説明する。
なお、各図は、本発明を十分に理解できる程度に、概略的に示してあるに過ぎない。よって、本発明は、図示例のみに限定されるものではない。なお、各図において、共通する構成要素や同様な構成要素については、同一の符号を付し、それらの重複する説明を省略する。
【００２３】
［第１実施形態］
≪経路情報更新システムの構成≫
以下、図１を参照して、第１実施形態に係る経路情報更新システムとしての通信ネットワーク１０００の構成について説明する。なお、図１は、第１実施形態に係る通信ネットワーク１０００の構成図である。
【００２４】
経路情報更新システムとしての通信ネットワーク１０００は、複数のノード１００と、各々のノード１００を接続するリンクとで構成される。通信ネットワーク１０００は、例えば、インターネットやイントラネット等である。
【００２５】
＜ノード＞
図２を参照して、第１実施形態に係るノード１００の構成について説明する。なお、図２は、第１実施形態に係るノード１００の機能構成図である。
ノード１００は、中継装置であり、例えば、ルータである。ノード１００は、記憶部１０と、制御部２０と、通信部３０とで構成される。通信部３０は、リンクを介して他のノード１００と通信可能に接続する装置である。通信部３０は、複数のインタフェース３で構成され、それぞれのインタフェース３には接続先のノード１００別のリンクが接続される。以下では、「インタフェース」を「Ｉ／Ｆ」と省略して呼ぶ場合がある。
【００２６】
制御部２０は、このノード１００が備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。さらに、記憶部１０は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、ノード１００をプログラム実行処理により実現する場合、記憶部１０には、このノード１００の機能を実現するための経路情報更新プログラムが格納される。
【００２７】
本実施の形態に係るノード１００は、前記したような処理を実行させるプログラムによって実現することができ、そのプログラムをコンピュータによる読み取り可能な記録媒体（ＣＤ−ＲＯＭ等）に記憶して提供することが可能である。また、そのプログラムを、インターネット等のネットワークを通して提供することも可能である。
【００２８】
記憶部１０には、網トポロジ情報ＤＢ１１と、現用系経路情報ＤＢ１２と、予備系経路情報ＤＢ１３とが記憶される。
（網トポロジ情報ＤＢ）
網トポロジ情報ＤＢ１１には、通信ネットワーク１０００のトポロジに関する情報が格納される。具体的には、通信ネットワーク１０００を構成するそれぞれのノード１００に接続されるリンクのインタフェース３の情報（以下、「インタフェース３の情報」を「リンクステート」と呼ぶ場合がある）が格納される。
【００２９】
この網トポロジ情報ＤＢ１１は、例えば、ＯＳＰＦで規定されるリンクステートデータベース(ＬＳＤ：Link State Database)である。網トポロジ情報ＤＢ１１は、それぞれのノード１００から送信されるリンクステートについての通知(以下、「リンクステートについての通知(ＬＳＡ：Link State Advertisement)」を省略して「リンクステート通知」と呼ぶ場合がある)を後記するリンクステート受信部２２が受信した場合に、受信したリンクステート通知に基づいて更新される。
【００３０】
（現用系経路情報ＤＢ）
現用系経路情報ＤＢ１２には、受信したパケットの宛先のノード１００と、受信したパケットを出力するインタフェース３との対応関係が規定されるテーブルが格納される。以下では、現用系経路情報ＤＢ１２に格納されるテーブルを現用系経路情報テーブルと呼ぶこととし、現用系経路情報テーブルにはテーブルＩＤとして「０」が設定されている。現用系経路情報ＤＢ１２は、網トポロジ情報ＤＢ１１を基にして、後記する現用系経路計算部２４により作成される。
【００３１】
（予備系経路情報ＤＢ）
予備系経路情報ＤＢ１３には、現用系経路情報ＤＢ１２と同様に、受信したパケットの宛先のノード１００と、受信したパケットを出力するインタフェース３の対応関係が規定されるテーブルが格納される。以下では、予備系経路情報ＤＢ１３に格納されるテーブルを予備系経路情報テーブルと呼ぶこととする。予備系経路情報テーブルは、通信ネットワーク１０００を構成するノード１００やリンクに故障等の不具合が発生した場合に、現用系経路情報テーブルに代わって用いられる。予備系経路情報テーブルは、通信ネットワーク１０００の故障箇所に対応させて複数存在し、これらの複数の予備系経路情報テーブルにはテーブルＩＤとして「０」以外の数字が連番で設定されている。
【００３２】
制御部２０は、リンクステート送信部２１と、リンクステート受信部２２と、リンクステート転送部２３と、現用系経路計算部２４と、予備系経路計算部２５と、プロトコル制御部２６と、パケット転送処理部２７とを備えて構成される。以下では、ノード１００の増減設によりトポロジが変化した場合の制御部２０の機能について説明する。
【００３３】
（リンクステート送信部）
リンクステート送信部２１は、隣接するノード１００が増減設されることによりインタフェース３に接続されるリンクが追加や変更された場合に、インタフェース３の設定やプロトコルの設定を行う。ここで、インタフェース３の設定とは、インタフェース３に接続されたリンクを介して隣接するノード３と電気信号のやり取りを行える状態にすることである。プロトコルの設定とは、リンクを介して隣接するノード１００と情報の送受信を行うための規約を決め交わすことである。インタフェース３の設定やプロトコルの設定を行うことにより、ノード１００は、リンクを介して隣接するノード１００と情報の送受信を行える状態になる。そして、リンクステート送信部２１は、インタフェース３の設定やプロトコルの設定を行った後に、自身の変更されたインタフェースに関する情報をリンクステート通知として、隣接するノード１００に送信する。
【００３４】
（リンクステート受信部）
リンクステート受信部２２は、隣接するノード１００からリンクステート通知を受信し、受信したリンクステート通知に基づいて網トポロジ情報ＤＢ１１を更新する。
【００３５】
（リンクステート転送部）
リンクステート転送部２３は、既にリンクステート通知を受信しているノード１００を除く隣接するノード１００に対して、受信したリンクステート通知を転送する。リンクステート転送部２３が、リンクステート通知を転送するタイミングは、後記するプロトコル制御部２６に制御される。
【００３６】
（現用系経路計算部）
現用系経路計算部２４は、例えば、ＯＳＰＦで用いられるダイクストラ(Dijkstra)のアルゴリズムを使用して網トポロジ情報ＤＢ１１から現用系経路情報テーブルを作成し、現用系経路情報ＤＢ１２を更新する。現用系経路計算部２４が、現用系経路情報テーブルを作成するタイミングは、後記するプロトコル制御部２６に制御される。
【００３７】
（予備系経路計算部）
予備系経路計算部２５は、例えば、ＩＰ−ＦＲＲ方式を使用して網トポロジ情報ＤＢ１１から予備系経路情報テーブルを作成し、予備系経路情報ＤＢ１３を更新する。予備系経路計算部２５が、予備系経路情報テーブルを作成するタイミングは、後記するプロトコル制御部２６に制御される。
【００３８】
（プロトコル制御部）
プロトコル制御部２６は、リンクステート転送部２３、現用系経路計算部２４、及び予備系経路計算部２５の処理の順番を制御し、それぞれ実行させる指示を行う。なお、トポロジの変更を最初に検出したノード１００のプロトコル制御部２６の処理においては、リンクステート転送部２３が行う処理をリンクステート送信部２１が行う処理に置き替えた処理となる。
プロトコル制御部２６がリンクステート転送部２３、現用系経路計算部２４、及び予備系経路計算部２５に処理の指示を出す順番は、３種類のケースが存在する。以下では、図３を参照し、従来のＯＳＰＦに規定される処理の順番を最初に説明し、そのあとに、図４〜図６を参照し、本実施形態に係る３種類のケースについて説明する。
【００３９】
＜従来の処理（ＯＳＰＦ）＞
図３を参照してＯＳＰＦに規定される従来の処理手順を説明する。
ＯＳＰＦに基づいて動作するノードは、リンクステート通知を他のノードから受信した場合に、受信したリンクステート通知をさらに隣接するノードに転送し（ステップＳ１０）、次に、受信したリンクステート通知の内容を反映した現用系経路を計算する（ステップＳ２０）。これにより、従来技術では、通信ネットワーク内の各ノードに対して、より早くリンクステート通知を送信することができたが、現用系経路の更新と同じタイミングで予備系経路を更新していないので、予備系経路が更新されるまでに通信ネットワーク内で故障が発生した場合に、トポロジ変更後の予備系経路を用いることができないという問題があった。
【００４０】
＜ケース１＞
次に、図４を参照してケース１の処理手順を説明する。
プロトコル制御部２６は、リンクステート通知を他のノードから受信した場合に、最初に、リンクステート転送部２３に対して処理の指示を出し、それによりリンクステート転送部２３は、リンクステート通知を隣接するノード１００に転送する（ステップＳ１１０）。次に、プロトコル制御部２６は、現用系経路計算部２４に対して処理の指示を出し、それにより現用系経路計算部２４は、現用系経路を計算し（ステップＳ１２０）現用系経路情報ＤＢ１２を更新する。次に、プロトコル制御部２６は、予備系経路計算部２５に対して処理の指示を出し、それにより予備系経路計算部２５は、予備系経路を計算し（ステップＳ１３０）予備系経路情報ＤＢ１３を更新する。
なお、ステップＳ１１０のリンクステート通知の転送と、ステップＳ１２０の現用系経路の計算は、並行して処理を行ってもよい。
【００４１】
ケース１の処理手順は、リンクステート通知の転送を優先したい場合の制御である。ケース１の処理手順は、例えば、ノード１００の減設によるトポロジの変更のように、リンクステート通知を他のノード１００へ転送することに即時性が求められる場合に有効である。
【００４２】
＜ケース２＞
次に、図５を参照してケース２の処理手順を説明する。
プロトコル制御部２６は、リンクステート通知を他のノードから受信した場合に、最初に、予備系経路計算部２５に対して処理の指示を出し、それにより予備系経路計算部２５は、予備系経路を計算し（ステップＳ２１０）予備系経路情報ＤＢ１３を更新する。次に、プロトコル制御部２６は、リンクステート転送部２３に対して処理の指示を出し、それによりリンクステート転送部２３は、リンクステート通知を隣接するノード１００に転送する（ステップＳ２２０）。次に、プロトコル制御部２６は、現用系経路計算部２４に対して処理の指示を出し、それにより現用系経路計算部２４は、現用系経路を計算し（ステップＳ２３０）現用系経路情報ＤＢ１２を更新する。
なお、ステップＳ２２０のリンクステート通知の転送と、ステップＳ２３０の現用系経路の計算は、並行して処理を行ってもよい。
【００４３】
ケース２の処理手順は、ケース１に比べて経路更新の安定した切り替えを実現したい場合の制御である。ここで、経路更新の安定した切り替えとは、ケース１では、現用系経路の計算の後に予備系経路の計算を行っているので、経路更新の過渡期において一時的ではあるが現用系経路のみの計算が終了している事が想定される。また、リンクステート通知の転送後に経路計算を行っているため、リンクステート通知の転送元のノード１００は、転送先の予備系経路の計算が終了する前に、ＩＰパケットを転送する可能性がある。そのため、増設されたノード１００で予備系経路の計算が終了せずに現用系経路のみの計算が終了している状態で故障が発生した場合に、物理的には迂回できる経路が存在するにも関わらず予備系経路の計算が終了していないためにパケット転送ができない状態が発生する。しかしながら、ケース２では予備系経路の計算をリンクステート通知の転送に先立って行っているので、このような問題が発生しない。ケース２の処理手順は、例えば、ノード１００の増設によるトポロジの変更のように、他のノード１００へのリンクステート通知に即時性が求められない場合に有効である。
【００４４】
＜ケース３＞
次に、図６を参照してケース３の処理手順を説明する。
プロトコル制御部２６は、リンクステート通知を他のノードから受信した場合に、最初に、現用系経路計算部２４に対して処理の指示を出し、それにより現用系経路計算部２４は、現用系経路を計算し（ステップＳ３１０）現用系経路情報ＤＢ１２を更新する。次に、プロトコル制御部２６は、予備系経路計算部２５に対して処理の指示を出し、それにより予備系経路計算部２５は、予備系経路を計算し（ステップＳ３２０）予備系経路情報ＤＢ１３を更新する。次に、プロトコル制御部２６は、リンクステート転送部２３に対して処理の指示を出し、それによりリンクステート転送部２３は、リンクステート通知を隣接するノード１００に転送する（ステップＳ３３０）。
なお、ステップＳ３１０の現用系経路の計算と、ステップＳ３２０の予備系経路の計算は、並行して処理を行ってもよいし、又は順序を逆転して予備系経路の計算の後に現用系経路の計算を行ってもよい。
【００４５】
ケース３の処理手順は、ケース１やケース２と比べて経路更新のさらに安定した切り替えを実現したい場合の制御である。ここで、経路更新のさらに安定した切り替えとは、ケース１やケース２では、現用系経路の計算前若しくは並行してリンクステート通知の転送を行うので、リンクステート通知の転送元の現用系経路の計算が完了する前に、転送先の現用系経路の計算が完了してしまい、転送元から転送先へのＩＰパケットの転送時に転送元でＩＰパケットをロス(破棄)する現象が原理的に発生する可能性がある。しかしながら、ケース３ではリンクステート通知の転送前に現用系経路及び予備系経路の計算を完了することからこのような問題が発生しない。ケース３の処理手順は、現用系経路及び予備系経路の計算を待つので、リンクステート通知の伝搬がケース１やケース２よりも遅れるが、経路更新の安定した切り替えが優先される場合に有効である。
【００４６】
上述したケース１ないしケース３の処理手順は、何れか１つを選択してもよいし、トポロジが変更される形態によってケース１ないしケース３の中から適切なケースを適宜選択するようにしてもよい。例えば、ノード１００が増設されることによるトポロジの変更には、ケース２やケース３の処理手順を使用し、ノード１００が減設されることによるトポロジの変更には、ケース１の処理手順を使用するようにしてもよい。また、ノード１００が増減設される場所を考慮してケースを選択してもよいし、ノード１００が増減設される時間帯(ＩＰパケットの量)を考慮してケースを選択してもよい。また、通信ネットワーク１０００のサイズを考慮してケースを選択してもよい。
【００４７】
（パケット転送処理部）
図２に戻り、パケット転送処理部２７は、受信したＩＰパケットを、どの経路に従って転送するかを決定して、決定した経路に従って受信したＩＰパケット転送する。具体的には、パケット転送処理部２７は、ＩＰパケットの宛先ＩＤ（例えばＩＰアドレス等）と、テーブルＩＤをキーとして出力インタフェース３(Ｉ／Ｆ)を決定して、決定した出力インタフェース３を介して受信したＩＰパケットを送信する。テーブルＩＤは、現用系経路か予備系経路かを指定するものであり、例えばＩＰパケットのＴｏＳ(Type of Service)フィールドに記述される。
以上で、ノード１００の構成の説明を終了する。また、経路情報更新システムとしての通信ネットワーク１０００の構成の説明を終了する。
【００４８】
≪経路情報更新システムの動作≫
以下、図７を参照して、第１実施形態に係る経路情報更新システムとしての通信ネットワーク１０００にノード１００が増設されることよりトポロジが変化した場合の経路情報更新の動作について、ケース２の処理を例にとり説明する。なお、ノード１００の減設によりトポロジが変化した場合については、設備の増設によりトポロジが変化した場合の説明を援用することとして詳細な説明を省略する。また、ケース１及びケース３の処理手順についても、以下の説明を援用することとして詳細な説明は省略する。
【００４９】
図７は、第１実施形態に係る通信ネットワーク１０００の概略図である。図７（ａ）は、通信ネットワーク１０００に、１つのノード１００を物理的に増設した状態を示し、図７（ｂ）は、増設したノード１００及び隣接するノード１００のインタフェースの設定及びプロトコルの設定を行っている状態を示し、図７（ｃ）は、増設したノード１００が通信ネットワーク１０００のトポロジに関する情報を取得する様子を示し、図７（ｄ）は、増設したノード１００から送信されたリンクステート通知が他のノード１００に転送される様子を示す。
【００５０】
図７（ａ）に示すように、ノード番号「１」〜「５」のノード１００で構成される通信ネットワーク１０００に、ノード番号「６」のノード１００を物理的に増設したとする。すると、図７（ｂ）に示すように、ノード番号「１」及び「６」のノード１００は、ノード番号「１」のノード１００とノード番号「６」のノード１００との間を接続するリンク１−６のインタフェース３の設定及びノード間のプロトコルの設定を行う。これにより、ノード番号「１」のノード１００とノード番号「６」のノード１００とは、情報の送受信を行える状態になる。
【００５１】
次に、図７（ｃ）に示すように、増設されたノード番号「６」のノード１００は、既設のノード番号「１」のノード１００から、網トポロジ情報ＤＢ１１に格納される通信ネットワーク１０００のトポロジに関する情報を受信する(符号５１の矢印)。符号５１の矢印で示す網トポロジに関する情報は、ノード番号「６」のノード１００が増設される前の、ノード番号「１」〜「５」のノード１００で構成される通信ネットワーク１０００のトポロジの情報を取得する様子である。これにより、ノード番号「６」のノード１００は、受信したトポロジに関する情報を基にして網トポロジ情報ＤＢ１１を更新する。
【００５２】
次に、図７（ｃ）に示すノード番号「６」のノード１００のプロトコル制御部２６は、図５のフローチャートに従って指示を行う。それにより、まずノード番号「６」のノード１００の予備系経路計算部２５は、網トポロジ情報ＤＢ１１から予備系経路情報テーブルを作成し、予備系経路情報ＤＢ１３を更新する。次に、ノード番号「６」のノード１００のリンクステート送信部２１は、設定したインタフェース３に関する情報をリンクステート通知としてノード番号「１」のノード１００に対して送信する(図７（ｄ）における符号５２の矢印)。次に、ノード番号「６」のノード１００の現用系経路計算部２４は、網トポロジ情報ＤＢ１１から現用系経路情報テーブルを作成し、現用系経路情報ＤＢ１２を更新する。
【００５３】
一方、ノード番号「１」のリンクステート受信部２２は、増設されたノード番号「６」のノード１００のリンクステート送信部２１から設定したインタフェース３に関する情報をリンクステート通知として受信し(図７（ｄ）における符号５２の矢印)、受信したリンクステート通知に基づいて網トポロジ情報ＤＢ１１を更新する。
【００５４】
次に、図７（ｄ）に示すノード番号「１」のノード１００のプロトコル制御部２６は、図５のフローチャートに従って指示を行う。それにより、まずノード番号「１」のノード１００の予備系経路計算部２５は、網トポロジ情報ＤＢ１１から予備系経路情報テーブルを作成し、予備系経路情報ＤＢ１３を更新する。次に、ノード番号「１」のノード１００のリンクステート転送部２３は、ノード番号「６」のノード１００から受信したリンクステート通知を隣接するノード番号「２」及び「５」のノード１００に対して転送する(符号５３，５４の矢印)。次に、ノード番号「１」のノード１００の現用系経路計算部２４は、網トポロジ情報ＤＢ１１から現用系経路情報テーブルを作成し、現用系経路情報ＤＢ１２を更新する。
【００５５】
一方、図７（ｄ）に示すノード番号「２」のノード１００のリンクステート受信部２２は、ノード番号「１」のノード１００のリンクステート転送部２３から転送されたリンクステート通知を受信し(符号５３の矢印)、受信したリンクステート通知に基づいて網トポロジ情報ＤＢ１１を更新する。
【００５６】
そして、図７（ｄ）に示すノード番号「２」のノード１００のプロトコル制御部２６は、図５のフローチャートに従って指示を行う。それにより、まずノード番号「２」のノード１００の予備系経路計算部２５は、網トポロジ情報ＤＢ１１から予備系経路情報テーブルを作成し、予備系経路情報ＤＢ１３を更新する。次に、ノード番号「２」のノード１００のリンクステート転送部２３は、ノード番号「１」のノード１００から受信したリンクステート通知を隣接するノード番号「３」のノード１００に対して転送する(符号５５の矢印)。次に、ノード番号「２」のノード１００の現用系経路計算部２４は、網トポロジ情報ＤＢ１１から現用系経路情報テーブルを作成し、現用系経路情報ＤＢ１２を更新する。
【００５７】
一方、図７（ｄ）に示すノード番号「５」のノード１００は、ノード番号「２」のノード１００と同様の処理を行い、ノード番号「１」のノード１００から受信したリンクステート通知を隣接するノード番号「４」のノード１００に対して転送する(符号５６の矢印)。次に、ノード番号「３」や「４」のノード１００も、受信したリンクステート通知に基づき経路計算を行う。
以上で、経路情報更新システムとしての通信ネットワーク１０００の動作の説明を終了する。
【００５８】
以上のように、第１実施形態に係る通信ネットワーク１０００は、トポロジの変更時に、リンクステート通知、現用系経路計算、予備系経路計算の順番を最適に設定して経路を更新することができる。
具体的には、ケース１の手順に従えば、経路の計算前にリンクステート通知を他のノード１００へ転送することができるので、通信ネットワーク１０００内の各ノード１００に対して、より早くリンクステート通知を送信することができる。
また、ケース２の手順に従えば、予備系経路の計算をリンクステート通知の転送に先立って行うので、現用系経路が故障した場合に、物理的な接続性が担保される限り予備系経路を用いて確実にＩＰパケットを送信できる。
また、ケース３の手順に従えば、リンクステート通知の転送前に現用系経路及び予備系経路の計算が完了するので、転送元のノード１００から転送先のノード１００へＩＰパケットを転送するときに、転送元でＩＰパケットをロス(破棄)する現象が発生しない。
【００５９】
［第２実施形態］
≪経路情報更新システムの構成≫
以下、図８を参照して、第２実施形態に係る経路情報更新システムとしての通信ネットワーク１０００ａの構成について説明する。なお、図８は、第２実施形態に係る通信ネットワーク１０００ａの構成図である。
【００６０】
経路情報更新システムとしての通信ネットワーク１０００ａは、ネットワーク情報取得装置３００と、制御サーバ４００と、複数のノード１００ａと、各々のノード１００ａを接続するリンクとで構成される。通信ネットワーク１０００ａは、例えば、インターネットやイントラネット等である。
【００６１】
＜ネットワーク情報取得装置＞
ネットワーク情報取得装置３００は、例えば、ＮＭＳ(Network Management System)であり、通信ネットワーク１０００ａを構成するノード１００ａからインタフェース３の情報（リンクステート）を含む情報を取得して、取得した情報を制御サーバ４００に送信する。
【００６２】
＜制御サーバ＞
図９を参照して、第２実施形態に係る制御サーバ４００の構成について説明する。なお、図９は、第２実施形態に係る制御サーバ４００の機能構成図である。
制御サーバ４００は、通信ネットワーク１０００ａの経路を計算し、計算した経路をそれぞれのノード１００ａに通知する装置である。制御サーバ４００は、記憶部４１０と、制御部４２０と、通信部４３０とで構成される。通信部４３０は、他の装置と通信可能に接続するためのインタフェース等の装置である。
【００６３】
記憶部４１０には、網トポロジ情報ＤＢ１１と、現用系経路情報ＤＢ１２と、予備系経路情報ＤＢ１３とが記憶される。これらの情報は、第１実施形態と同様である。
制御部４２０は、現用系経路計算部２４と、予備系経路計算部２５と、経路配信部４２６とを備えて構成される。現用系経路計算部２４及び予備系経路計算部２５は、第１実施形態と同様である。
【００６４】
（経路配信部）
経路配信部４２６は、現用系経路計算部２４が計算した現用系経路、及び予備系経路計算部２５が計算した予備系経路をノード１００ａに送信(配信)する。経路配信部４２６が、現用系経路→予備系経路の順番に経路を配信することで、第１実施形態のプロトコル制御部２６の「ケース１」と同様の効果を得ることができる。また、経路配信部４２６が、予備系経路→現用系経路の順番に経路を配信することで、第１実施形態のプロトコル制御部２６の「ケース２」と同様の効果を得ることができる。
【００６５】
＜ノード＞
ノード１００ａは、第１実施形態に係るノード１００と異なり自身で経路計算を行わず、制御サーバ４００から現用系経路及び予備系経路を取得する。
以上で、経路情報更新システムとしての通信ネットワーク１０００ａの構成の説明を終了する。
【００６６】
以上のように、第２実施形態に係る通信ネットワーク１０００ａは、第１実施形態に係る通信ネットワーク１０００と同様の効果を得ることができる。
【００６７】
[変形例]
以上、本発明の第１実施形態及び第２実施形態について説明したが、本発明はこれに限定されるものではなく、その趣旨を変えない範囲で実施することができる。第１実施形態及び第２実施形態の変形例を以下に示す。
【００６８】
（プロトコル制御部）
第１実施形態におけるプロトコル制御部２６では、リンクステート通知、現用系経路計算、予備系経路計算の順番を入れ替える処理手順を説明した。ここで、通信ネットワーク１０００が、パスネットワークのようにある現用系経路に対して予備系経路が存在する場合、現用系経路が決まらないと予備系経路が計算できない。そのような場合は、現用系経路→予備系経路の順番に経路計算は行い、プロトコル制御部２６における「計算」の部分を「ＩＰパケットを転送するための設定」に読み替えるようにする。
【００６９】
（制御サーバ）
第２実施形態における制御サーバ４００では、インタフェース３の情報（リンクステート）をネットワーク情報取得装置３００から受信していたが、制御サーバ４００がネットワーク情報取得装置３００の機能(リンクステート収集部)を備えるようして、制御サーバ４００がノード１００ａからリンクステートを直接受信するようにしてもよい。
【符号の説明】
【００７０】
３      インタフェース
１０    記憶部
１１    網トポロジ情報ＤＢ
１２    現用系経路情報ＤＢ
１３    予備系経路情報ＤＢ
２０    制御部
２１    リンクステート送信部
２２    リンクステート受信部
２３    リンクステート転送部
２４    現用系経路計算部
２５    予備系経路計算部
２６    プロトコル制御部
２７    パケット転送処理部
３０    通信部
１００，１００ａ  ノード
３００  ネットワーク情報取得装置（リンクステート収集部）
４００  制御サーバ（経路制御装置）
４１０  記憶部
４２０  制御部
４３０  通信部
４２６  経路配信部
１０００，１０００ａ  通信ネットワーク（経路情報更新システム）
【図１】
0005576837.tif 000002
【図２】
0005576837.tif 000003
【図３】
0005576837.tif 000004
【図４】
0005576837.tif 000005
【図５】
0005576837.tif 000006
【図６】
0005576837.tif 000007
【図７】
0005576837.tif 000008
【図８】
0005576837.tif 000009
【図９】
0005576837.tif 000010
【図１０】
0005576837.tif 000011