経路表作成装置および経路表作成方法
【課題】網内の故障発生時の迂回経路を含む経路表の作成処理の負荷を軽減する。
【解決手段】経路表作成装置が、各宛先アドレスへの到達可能な装置を示した到達性情報１３２と、通信ネットワークのトポロジ情報１３３とを用いて、通信ネットワークの装置ごとに、当該装置で用いる第１の転送先（現用）と第２の転送先（予備）とを含む経路表１３３を作成する。そして、この作成した経路表１３３を各装置４０へ送信する。
【解決手段】経路表作成装置が、各宛先アドレスへの到達可能な装置を示した到達性情報１３２と、通信ネットワークのトポロジ情報１３３とを用いて、通信ネットワークの装置ごとに、当該装置で用いる第１の転送先（現用）と第２の転送先（予備）とを含む経路表１３３を作成する。そして、この作成した経路表１３３を各装置４０へ送信する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、IP（Internet Protocol）網の各ルータ等において宛先アドレスまたはサブネットワークに対する転送先を決定するために用いられる経路表の作成技術に関する。
【背景技術】
【０００２】
従来、IP網内のルータ等の各装置がパケット転送に用いる経路表は、各装置が、ＯＳＰＦ（Open Shortest Path First）やＢＧＰ（Border Gateway Protocol）等のルーティングプロトコルを用いて作成する（非特許文献１，２参照）。また、網内の装置や、各装置間を接続するリンクに故障が発生したときに、高速に迂回経路への切り替えを行うため、各装置において、故障発生前の転送路（第１の転送路）に加え、迂回経路である第２の転送路を事前に計算しておく技術も提案されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】IETF RFC2328 “OSPF Version 2”, April 1998.
【非特許文献２】IETF RFC 4271, “A Border Gateway Protocol 4 (BGP-4)”, January 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、従来技術により、各装置においてルーティングプロトコルを動作させ、迂回経路を含む経路表を作成するのは処理負荷が大きいという問題があった。特に、網内の装置それぞれが、他の多数の装置と接続されているようなトポロジの場合（例えば、網内の各装置がフルメッシュで接続されているトポロジの場合）、各装置における経路表作成処理の負荷は極めて大きくなる。さらに、そこで、本発明は、前記した問題を解決し、網内の故障発生時の迂回経路を含む経路表の作成処理の負荷を軽減することを目的とする。
【課題を解決するための手段】
【０００５】
前記した課題を解決するため、本発明は、網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置が以下の処理を行う。すなわち、この経路表作成装置は、宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークへ到達可能な装置の識別情報を示した到達性情報の入力を受け付け記憶部に記憶する。また、ネットワークを構成する各装置の接続状態および各装置を接続するリンクを示したトポロジ情報の入力を受け付け記憶部に記憶する。そして、この経路表作成装置は、到達性情報に示される宛先アドレスごとに、当該宛先アドレスへ到達可能な装置群の中から、現用装置と予備装置とを選択する。そして、経路表作成装置は、トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、始点装置から当該宛先アドレスへ到達可能な現用装置への現用経路を計算する。また、この始点装置から当該宛先アドレスへ到達可能な予備装置への予備経路とを計算する。そして、トポロジ情報を参照して、始点装置が現用経路で用いるリンクである現用リンクと、予備経路で用いるリンクである予備リンクとを選択する。この後、経路表作成装置は、始点装置それぞれについて、宛先アドレスごとに、当該宛先アドレスへの現用リンクおよび予備リンクを示した経路表を作成する。そして、経路表作成装置は、作成した経路表を、始点装置である各装置へ送信する。
【０００６】
このように経路表作成装置が、網内の故障発生時の迂回経路を含む各装置の経路表を作成するので、各装置がルーティングプロトコルを動作させて経路表を作成する必要がなくなる。
【０００７】
本発明は、網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置が以下の処理を行う。すなわち、この経路表作成装置は、到達性情報の入力を受け付け記憶部に記憶する。また、ネットワークを構成する各装置の接続状態および各装置を接続するリンクと、当該リンクが現用経路に用いられる現用リンクである場合、当該リンクに対する予備リンクの識別情報とを含むトポロジ情報との入力を受け付け、記憶部に記憶する。そして、経路表作成装置は、到達性情報に示される宛先アドレスごとに、当該宛先アドレスへ到達可能な装置群の中から、現用装置を選択する。次に、トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、始点装置から当該宛先アドレスへ到達可能な現用装置への現用経路を計算する。そして、トポロジ情報を参照して、現用経路に用いる現用リンクを選択し、トポロジ情報において、この選択した現用リンクに対する予備リンクを選択する。その後、経路表作成装置は、始点装置それぞれについて、宛先アドレスごとに、当該宛先アドレスへの現用リンクおよび予備リンクを示した経路表を作成する作成する。そして、経路表作成装置は、作成した経路表を、始点装置である各装置へ送信する。
【０００８】
このように経路表作成装置が、網内の故障発生時の迂回経路を含む各装置の経路表を作成するので、各装置がルーティングプロトコルを動作させて経路表を作成する必要がなくなる。また、この経路表作成装置によれば、トポロジ情報上で現用リンクとペアになる予備リンクを選択して経路表を作成するので、経路表作成の処理負荷を軽減できる。
【０００９】
本発明は、網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置が以下の処理を行う。すなわち、この経路表作成装置は、到達性情報と、トポロジ情報との入力を受け付け、記憶部に記憶する。経路表作成装置は、到達性情報に示される同じ宛先アドレスへの到達可能装置が２つ以上いずれかのリングに含まれるまで、トポロジ情報を参照して、リングを構成する装置群を探索する。そして、到達性情報を参照して、リングを構成する装置群ごとに、当該装置群がエッジノードとなっている宛先アドレス群を抽出する。次に、経路表作成装置は、トポロジ情報を参照して、リングを構成する装置群の装置それぞれについて、当該装置を始点装置としたとき、当該装置群により構成されるリングにおいて第１の回転方向の装置に接続されるリンクを現用リンクとして選択する。また、（２）当該リングにおいて第１の回転方向と逆の回転方向の装置に接続されるリンクを予備リンクとして選択する。その後、経路表作成装置は、始点装置それぞれについて、宛先アドレス群に示される宛先アドレスごとに、当該宛先アドレスへの現用リンクおよび予備リンクを示した経路表を作成する作成する。そして、経路表作成装置は、作成した経路表を、始点装置である各装置へ送信する。
【００１０】
このように経路表作成装置が、網内の故障発生時の迂回経路を含む各装置の経路表を作成するので、各装置がルーティングプロトコルを動作させて経路表を作成する必要がなくなる。また、この経路表作成装置によれば、トポロジ情報に、リング状に接続される装置群がある場合、その中の始点装置からみて第１の回転方向（例えば、時計回りの方向）に接続されるリンクを当該宛先アドレスへの現用リンクとして選択する。また、第１の回転方向と逆の回転方向（例えば、反時計回りの方向）の装置に接続されるリンクを当該宛先アドレスへの予備リンクとして選択する。例えば、装置Ａ，Ｂ，Ｃ，Ｄがリング状に接続されている場合において、装置Ａから見て時計回りの方向に装置Ｂが接続されていれば、経路表作成装置は、装置Ａから装置Ｂへのリンクを、装置Ａから当該宛先アドレスへの現用リンクとして選択する。また、装置Ａから装置Ｃへのリンクを、装置Ａから当該宛先アドレスへの予備リンクとして選択する。このようにすることで、経路表作成装置は、経路表作成の処理負荷を軽減できる。
【００１１】
本発明は、網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置が以下の処理を行う。すなわち、この経路表作成装置は、到達性情報と、トポロジ情報との入力を受け付け、記憶部に記憶する。そして、経路表作成装置は、到達性情報に、宛先アドレスが複数ある装置が複数登録され、かつ、当該装置間で設定された宛先アドレス群の少なくとも一部が同じであるとき、当該装置それぞれの宛先アドレスの集合である宛先グループを計算する。次に、経路表作成装置は、到達性情報に示される宛先アドレスごとに、当該宛先アドレスへ到達可能な装置群の中から、現用装置と予備装置とを選択する。そして、経路表作成装置は、トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、始点装置から当該宛先アドレスに到達可能な現用装置への現用経路を計算する。また、この始点装置から当該宛先アドレスに到達可能な予備装置への予備経路とを計算する。そして、トポロジ情報を参照して、始点装置が現用経路で用いるリンクである現用リンクと、予備経路で用いるリンクである予備リンクとを選択する。その後、経路表作成装置は、始点装置それぞれについて、計算した宛先グループの宛先アドレスごとに、当該宛先グループの宛先アドレスへの現用リンクおよび予備リンクを示した経路表を作成する。そして、経路表作成装置は、この作成した経路表を、始点装置である各装置へ送信する。
【００１２】
このようにすることで、経路表作成装置は、宛先アドレスごとに現用リンクおよび予備リンクを求める必要がなくなる。つまり、始点装置から宛先アドレスそれぞれについて現用リンクおよび予備リンクを選択する必要がなくなるので、経路表作成の処理負荷を軽減できる。
【００１３】
また、本発明の経路表作成装置のリンク選択部は、現用経路および予備経路を計算するとき、トポロジ情報を参照して、ホップ数またはリンクコストが最小となる経路を計算する。
【００１４】
このようにすることで、経路表作成装置は、始点装置から現用装置（または予備装置）へのホップ数またはリンクコストが最小となる経路の経路表を作成できる。
【００１５】
また、本発明の経路表作成装置のリンク選択部は、現用経路および予備経路を計算するとき、トポロジ情報を参照して、現用経路および予備経路が互いに、同じ装置またはリンクを経由しない経路を選択する。
【００１６】
このようにすることで、経路表作成装置は、現用経路上で障害が発生したときでも、その障害の影響を受けづらい予備経路を含む経路表を作成できる。
【００１７】
また、本発明の経路表作成装置の装置選択部は、現用装置を選択するとき、トポロジ情報を参照して、当該宛先アドレスへのホップ数またはリンクコストが最小の装置を選択する。
【００１８】
このようにすることで、経路表作成装置は、始点装置から現用装置へのホップ数またはリンクコストが最小となる経路の経路表を作成できる。
【発明の効果】
【００１９】
本発明によれば、網内の故障発生時の迂回経路を含む経路表の作成処理の負荷を軽減できる。
【図面の簡単な説明】
【００２０】
【図１】（ａ）は、各実施の形態のシステムの全体構成を例示した図であり、（ｂ）は、通信ネットワークのトポロジを例示した図である。
【図２】（ａ）は、第１の実施の形態の経路表作成装置の処理概要を概念的に示した図であり、（ｂ）は、到達性情報を例示した図である。（ｃ）は、トポロジ情報を例示した図であり、（ｄ）は、経路表を例示した図である。
【図３】第１の実施の形態および第２の実施の形態の経路表作成装置の構成を示した図である。
【図４】第１の実施の形態の経路表作成装置の処理手順を示したフローチャートである。
【図５】（ａ）は、通信ネットワークのトポロジの例および第２の実施の形態の経路表作成装置の処理概要を概念的に示した図であり、（ｂ）は、到達性情報を例示した図である。（ｃ）は、トポロジ情報を例示した図であり、（ｄ）は、経路表を例示した図である。
【図６】第２の実施の形態の経路表作成装置の処理手順を示したフローチャートである。
【図７】（ａ）は、通信ネットワークのトポロジの例および第２の実施の形態の経路表作成装置の処理概要を概念的に示した図であり、（ｂ）は、到達性情報を例示した図である。（ｃ）は、トポロジ情報を例示した図であり、（ｄ）は、経路表を例示した図である。
【図８】第３の実施の形態の経路表作成装置の構成を示した図である。
【図９】第３の実施の形態の経路表作成装置の処理手順を示したフローチャートである。
【図１０】（ａ）は、第４の実施の形態の経路表作成装置の処理概要を概念的に示した図であり、（ｂ）は、到達性情報を例示した図である。（ｃ）は、トポロジ情報を例示した図であり、（ｄ）は、経路表を例示した図である。
【図１１】第４の実施の形態の経路表作成装置の構成を示した図である。
【図１２】第４の実施の形態の経路表作成装置の処理手順を示したフローチャートである。
【発明を実施するための形態】
【００２１】
以下、図面を参照しながら、本発明の実施の形態を、第１の実施の形態から第４の実施の形態に分けて説明する。まず、図１を用いて、各実施の形態の経路表作成装置１０，１０Ａ，１０Ｂ，１０Ｃに共通するシステムの全体構成例を説明する。
【００２２】
図１（ａ）に示すようにシステムは、通信ネットワークと、経路表作成装置１０と、ネットワーク情報取得装置２０とを含んで構成される。この通信ネットワークは、複数の装置４０（例えば、ＩＰルータ等のノード）がリンク（例えば、光ファイバ等）により接続されたＩＰ網等である。経路表作成装置１０，１０Ａ，１０Ｂ，１０Ｃは、ネットワーク情報取得装置２０から取得した情報（例えば、トポロジ情報１３１や到達性情報１３２の元となる情報）に基づき、各装置４０の経路表１３３（後記）を作成する。そして、この経路表１３３を各装置４０へ送信し、各装置４０は受信した経路表１３３に基づきパケットを転送する。ネットワーク情報取得装置２０は、通信ネットワークから各装置４０の接続状態等の情報を取得し、経路表作成装置１０，１０Ａ，１０Ｂ，１０Ｃへ送信する。経路表作成装置１０，１０Ａ，１０Ｂ，１０Ｃおよびネットワーク情報取得装置２０は、ＩＰ等の通信プロトコルにより通信可能なコンピュータにより実現される。この経路表作成装置１０，１０Ａ，１０Ｂ，１０Ｃは、現用経路のほかに、この現用経路の予備経路も含む経路表１３３を作成する。これにより、この経路表１３３を受信した各装置４０は、網内の障害発生時に迂回経路（予備経路）への切り替えを高速に行うことができる。
【００２３】
＜第１の実施の形態＞
まず、第１の実施の形態の経路表作成装置１０を説明する。ここでは、経路表作成装置１０が、図１（ｂ）に示すようなトポロジの通信ネットワークの経路表１３３を作成する場合を例に説明する。図１（ｂ）の装置Ａ，Ｂ，Ｃ，Ｄは、装置４０に相当する。装置Ａ，Ｂはそれぞれ宛先アドレスｄ１，ｄ２へ到達可能な装置であることを示す。この宛先アドレスは、宛先となる装置のＩＰアドレスでもよいし、サブネットワークのアドレスであってもよい。
【００２４】
経路表作成装置１０は、図２（ａ）に示すように、到達性情報１３２（宛先アドレスごとに、その宛先アドレスへの到達可能な通信ネットワークのエッジノードの装置４０を示した情報（図２（ｂ）参照））と、通信ネットワークのトポロジ情報１３１（図２（ｃ）参照）とを参照して経路表計算を行い、通信ネットワークにおける各装置４０の経路表１３３（図２（ｄ）参照）を作成する。この経路表１３３は、宛先アドレス（宛先）ごとに、その宛先アドレスへの第１の転送先へのリンク（現用リンク）と、第２の転送先へのリンク（予備リンク）とを示した情報である。つまり、経路表１３３は、通信ネットワーク内の故障発生時において装置４０が迂回経路への高速切り替えを実現するため、同じ宛先アドレスに対し現用リンクと予備リンクとの両方を示した情報である。なお、図２（ｄ）には、装置Ｃ，Ｄの経路表１３３のみを示しているが、装置Ａ，Ｂの経路表１３３についても同様に作成される。
【００２５】
次に、図３を用いて経路表作成装置１０の構成を説明する。経路表作成装置１０は、大きく入出力部（入力部および出力部）１１、処理部１２および記憶部１３に分けられる。入出力部１１は、ネットワーク情報取得装置２０や通信ネットワークの各装置４０とのデータ送受信を司る。例えば、トポロジ情報１３１や到達性情報１３２の元となる情報を取得したり、経路表作成装置１０で作成した各装置４０の経路表１３３を、各装置４０へ送信したりする。処理部１２は、この経路表作成装置１０全体の制御を司り、主に各装置４０の経路表１３３を作成する。記憶部１３は、処理部１２が各装置４０の経路表１３３を作成するときに参照する各種情報を記憶する。
【００２６】
入出力部１１は、入出力インタフェースやＩＰにより通信可能な通信インタフェース等から構成される。また、処理部１２は、この経路表作成装置１０（１０Ａ，１０Ｂ，１０Ｃ）が備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。さらに、記憶部１３は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、経路表作成装置１０，１０Ａ，１０Ｂ，１０Ｃをプログラム実行処理により実現する場合、記憶部１３には、この経路表作成装置１０（１０Ａ，１０Ｂ，１０Ｃ）の機能を実現するためのプログラムが格納される。
【００２７】
記憶部１３は、トポロジ情報１３１と、到達性情報１３２とを記憶する。また、記憶部１３は、各装置４０の経路表１３３を記憶する領域を備える。
【００２８】
トポロジ情報１３１は、前記したとおり、通信ネットワークを構成する各装置４０の接続状態および各装置４０を接続するリンクを示した情報である。例えば、図２（ｃ）に示すトポロジ情報１３１は、図１（ｂ）に示す通信ネットワークのトポロジを示した情報であり、装置Ａ，Ｂ間はリンク＃１により接続されることを示す。なお、このトポロジ情報１３１は、各リンクのリンクコストの値を含んでいてもよい。また、例えば、装置Ａ→装置Ｂの通信に用いるリンクと、装置Ｂ→装置Ａの通信に用いるリンクとを区別する等、通信の方向によって用いるリンクを区別するようにしてもよい。
【００２９】
到達性情報１３２は、宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークに到達可能な装置４０（到達可能装置）の識別情報を示した情報である。例えば、図２（ｂ）に示す到達性情報１３２は、図１（ｂ）に示す通信ネットワークの到達性情報であり、宛先アドレスｄ１への到達可能装置は、装置Ａ，Ｂであり、宛先アドレスｄ２への到達可能装置も、装置Ａ，Ｂであることを示す。つまり、宛先アドレスｄ１，ｄ２へパケットを転送する場合、通信ネットワークの装置４０（始点装置）は、このいずれかの装置４０を目指してパケットを転送すればよいことを示す。
【００３０】
なお、このトポロジ情報１３１および到達性情報１３２は、経路表作成部１２３が経路表１３３を作成する際に参照される。このトポロジ情報１３１および到達性情報１３２は、ネットワーク情報取得装置２０から受信した情報をもとに処理部１２が作成してもよいし、予め外部装置で作成しておいたものを入出力部１１経由で入力してもよい。
【００３１】
処理部１２は、装置選択部１２１と、リンク選択部１２２と、経路表作成部１２３と、経路表送信部１２４とを備える。
【００３２】
装置選択部１２１は、到達性情報１３２（図２（ｂ）参照）に示される宛先アドレスへの到達可能装置の中から現用装置と予備装置とを選択する。選択した現用装置および予備装置それぞれの識別情報は、リンク選択部１２２へ出力する。なお、装置選択部１２１は、現用装置および予備装置を選択するとき、到達性情報１３２にＢＧＰ（Border Gate Protocol）の優先度の情報が含まれていれば、この優先度の値をもとに装置４０を選択してもよい。例えば、到達性情報１３２において、同じ宛先アドレスへの到達可能装置のうち、ＢＧＰの優先度が最も高い装置４０を現用装置として選択し、次に優先度が高い装置４０を予備装置として選択してもよい。また、装置選択部１２１は、現用装置および予備装置を選択する際、トポロジ情報１３１を参照して、始点装置からのホップ数やリンクコストの合計値をもとに現用装置および予備装置として選択してもよい。例えば、始点装置からのホップ数やリンクコストの合計値が最も小さい装置４０を、現用装置として選択し、その次に小さい装置４０を、予備装置として選択してもよい。
【００３３】
リンク選択部１２２は、トポロジ情報１３１（図２（ｃ）参照）に示される装置４０それぞれについて、当該装置４０を始点装置としたとき、この始点装置から現用装置への現用経路（第１の転送路）と、始点装置から予備装置への予備経路（第２の転送路）とを計算する。そして、トポロジ情報１３１に示されるリンク情報を参照して、始点装置が現用経路で用いるリンクである現用リンクおよび始点装置が予備経路で用いるリンクである予備リンクを選択する。そして、選択した各装置４０の現用リンクおよび予備リンクを、経路表作成部１２３へ出力する。また、リンク選択部１２２は、現用経路や予備経路を計算する際、同じ現用装置や予備装置への経路が複数あったとき、そのうちホップ数またはリンクコストが最小となる経路を選択してもよい。また、トポロジ情報１３１を参照して、現用経路および予備経路が互いに、同じ装置４０またはリンクを経由しない経路を選択するようにしてもよい。
【００３４】
経路表作成部１２３は、装置４０それぞれについて、宛先アドレスごとに、当該宛先アドレスへの現用リンクおよび予備リンクを示した経路表１３３（図２（ｄ）参照）を作成する。
【００３５】
経路表送信部１２４は、各装置４０の経路表１３３を、入出力部１１経由で通信ネットワーク装置の装置４０へ送信する。
【００３６】
このようにすることで経路表作成装置１０は、各装置４０の経路表１３３を作成し、各装置４０へ送信することができる。
【００３７】
＜処理手順＞
次に、図２，３を参照しつつ、図４を用いて、経路表作成装置１０の処理手順を説明する。
【００３８】
まず、図３の経路表作成装置１０の装置選択部１２１は、到達性情報１３２を参照して、ある宛先アドレス（例えば、図２（ａ）のｄ１）に対するすべての到達可能装置（例えば、装置Ａ，Ｂ）を抽出する（Ｓ１１）。つまり、到達性情報１３２に示される宛先アドレスから１つの宛先アドレスを選択し、宛先アドレスに対するすべての到達可能装置（装置４０）を抽出する。そして、装置選択部１２１は、抽出した到達可能装置から、現用装置（例えば、装置Ａ）と予備装置（例えば、装置Ｂ）とを選択する（Ｓ１２）。
【００３９】
次に、リンク選択部１２２は、トポロジ情報１３１（図２（ｃ）参照）に示される装置４０を１つ選択し、この装置４０（例えば、装置Ｃ）を始点装置として現用装置（例えば、装置Ａ）に到達するための現用リンク（例えば、リンク＃２）を選択する。また、この始点装置から予備装置（例えば、装置Ｂ）に到達するための予備リンク（例えば、リンク＃４）とを選択する（Ｓ１３）。つまり、まず、リンク選択部１２２は、始点装置から現用装置への現用経路と、始点装置から予備装置への予備経路とを計算する。そして、トポロジ情報１３１に示されるリンク情報を参照して、始点装置が現用経路で用いるリンクである現用リンクおよび予備経路で用いるリンクである予備リンクを選択する。選択された始点装置の現用リンクおよび予備リンクは、経路表作成部１２３が、当該始点装置（装置４０）に関する経路表１３３に記憶する。
【００４０】
そして、トポロジ情報１３１に示されるすべての装置４０について処理を終了し（Ｓ１４のＹｅｓ）、かつ、到達性情報１３２に示されるすべての宛先アドレスについて処理を終了していれば（Ｓ１５のＹｅｓ）、経路表作成処理を終了する。そして、経路表送信部１２４が、経路表１３３を、各装置４０へ送信する。
【００４１】
一方、トポロジ情報１３１に示される装置４０のうち、未処理の装置４０があれば（Ｓ１４のＮｏ）、装置選択部１２１は、未処理の装置４０に対し、Ｓ１２以降の処理を行う。また、到達性情報１３２に示される宛先アドレスについて未処理の宛先アドレスがあれば（Ｓ１５のＮｏ）、装置選択部１２１は、その未処理の宛先アドレスについてＳ１１以降の処理を実行する。
【００４２】
このようにすることで、経路表作成装置１０は、通信ネットワークの各装置４０で用いる経路表１３３を作成することができる。この経路表１３３は、各宛先アドレスの現用経路へのリンク（現用リンク）のみならず、予備経路へのリンク（予備リンク）も含む。よって、各装置４０は、網内に障害が発生した場合でも、迂回経路への経路切り替えを高速に行うことができる。
【００４３】
＜第２の実施の形態＞
次に、第２の実施の形態の経路表作成装置１０Ａを説明する。前記した実施の形態と同様の構成要素は、同じ符号を付して説明を省略する。
【００４４】
経路表作成装置１０Ａは、図５（ａ）に示すように、経路表計算を行う際、到達性情報１３２（図５（ｂ）参照）と、トポロジ情報１３１Ａ（図５（ｃ）参照）とを参照することを特徴とする。このトポロジ情報１３１Ａは、図５（ｃ）に例示するように、各リンクが、現用経路に用いるリンク（現用リンク）か、予備経路に用いるリンク（予備リンク）であるかを示す情報を含む。また、当該リンクが現用リンクである場合、ペアとなる予備リンクの識別情報を含み、当該リンクが予備リンクである場合、ペアとなる現用リンクの識別情報を含む。そして、経路表作成装置１０Ａは、ある装置４０の現用リンクを求めた後、予備リンクを選択するときには、このトポロジ情報１３１Ａに示される当該現用リンクの予備リンクを選択する。
【００４５】
このような経路表作成装置１０Ａの処理部１２は、図３に示すように、装置選択部１２１に代えて、装置選択部１２１Ａを備え、リンク選択部１２２に代えてリンク選択部１２２Ａを備える。さらに、トポロジ情報１３１に代えてトポロジ情報１３１Ａを備える。その他の構成は、経路表作成装置１０と同様なので説明を省略する。
【００４６】
装置選択部１２１Ａは、到達性情報１３２に示される宛先アドレスごとに、当該宛先アドレスへの到達可能装置群の中から、現用装置を選択する。選択した現用装置は、リンク選択部１２２Ａへ出力する。なお、この現用装置を選択するとき、例えば、トポロジ情報１３１Ａを参照して、当該宛先アドレスへのホップ数またはリンクコストが最小の装置を選択する。
【００４７】
リンク選択部１２２Ａは、トポロジ情報１３１に示される装置４０それぞれについて、当該装置４０を始点装置としたとき、始点装置から、装置選択部１２１Ａで選択した現用装置への現用経路を計算する。そして、トポロジ情報１３１Ａを参照して、現用経路に用いる現用リンクを選択すると、トポロジ情報１３１Ａを参照して、この現用リンクとペアになる予備リンクを選択する。選択した現用リンクおよび予備リンクは、経路表作成部１２３へ出力する。なお、このトポロジ情報１３１Ａに現用リンクの予備リンクが無い場合には、リンク選択部１２２Ａは、第１の実施の形態と同様に、現用装置と同じ宛先アドレスへの到達可能装置から予備装置を選択し、この予備装置への経路を計算して、予備リンクを求めるようにしてよい。
【００４８】
＜処理手順＞
次に、図３，５を参照しつつ、図６を用いて、経路表作成装置１０Ａの処理手順を説明する。Ｓ２１は、前記したＳ１１と同様なので、Ｓ２２から説明する。経路表作成装置１０Ａの装置選択部１２１Ａは、Ｓ２１で抽出した到達可能装置から、装置４０を１つ選択する（Ｓ２２）。例えば、図５（ａ）の装置Ａを選択する。
【００４９】
次に、リンク選択部１２２Ａは、トポロジ情報１３１Ａ（図５（ｃ）参照）に示される装置４０それぞれについて、当該装置４０を始点装置（例えば、装置Ｃ）としたとき、始点装置から、Ｓ２２で選択した装置４０（例えば、装置Ａ）に到達するための現用リンク（例えば、リンク＃２）を、トポロジ情報１３１Ａを参照して選択する（Ｓ２３）。つまり、リンク選択部１２２Ａは、Ｓ２２で選択した装置４０を現用装置として、始点装置からこの現用装置への現用経路を計算する。そして、トポロジ情報１３１Ａに示されるリンク情報を参照して、始点装置で用いる現用リンクを選択する。
【００５０】
また、リンク選択部１２２Ａは、トポロジ情報１３１Ａを参照して、Ｓ２３で選択したリンク（現用リンク）の予備リンク（例えば、リンク＃５）を選択する（Ｓ２４）。選択した始点装置の現用リンクおよび予備リンクは、経路表作成部１２３が、当該始点装置（例えば、装置Ｃ）の経路表１３３に記録する。この後のＳ２５およびＳ２６の処理は、前記したＳ１４およびＳ１５の処理と同様なので説明を省略する。
【００５１】
このような経路表作成装置１０Ａによれば、予備リンクを選択する際、トポロジ情報１３１Ａ上に設定されている予備リンクを選択すればよいので、経路表作成の処理負荷を軽減できる。
【００５２】
＜第３の実施の形態＞
次に、第３の実施の形態を説明する。前記した実施の形態と同様の構成要素は、同じ符号を付して説明を省略する。
【００５３】
経路表作成装置１０Ｂは、図７（ａ）に示すように、経路表計算を行うとき、トポロジ上でリング状に接続される装置４０を探索するリング探索を行い、このリングを用いて転送先計算を行うことを特徴とする。
【００５４】
例えば、経路表作成装置１０Ｂは、宛先アドレスｄ１，ｄ２への到達可能装置である装置Ａ，Ｂを含むリング（装置Ａ，Ｂ，Ｃ，Ｄ）を用いる場合を考える。この場合、装置Ｃから宛先アドレスｄ１（またはｄ２）への現用リンクとして、自身の装置Ｃを含むリングの時計周りの方向に隣接する装置Ｄへのリンク＃５を選択する。また、予備リンクとして、リングの反時計周りの方向に隣接する装置Ａへのリンク＃２を選択する。つまり、トポロジ上で、ある宛先アドレスへの到達可能装置を複数含むリングを見つければ、そのリングを構成する装置４０はそれぞれ、その宛先アドレスへのリンクを２本持つことになる。よって、その２本のリンクのうち１本のリンクを現用リンクとし、もう１本のリンクを予備リンクとすれば、現用リンクと予備リンクとを１本ずつ選ぶことができる。
【００５５】
このような経路表作成装置１０Ｂの処理部１２は、図８に示すように、リンク選択部１２２Ｂと、経路表作成部１２３と、経路表送信部１２４と、リング探索部１２５と、宛先アドレス抽出部１２６とを備える。
【００５６】
リンク選択部１２２Ｂは、トポロジ情報１３１（図７（ｃ）参照）に示されるリンク情報を参照して、リングを構成する装置群の装置４０それぞれについて、各装置４０を始点装置としたときの現用リンクと予備リンクとを選択する。このリンク選択部１２２Ｂのリンク選択処理の詳細は、図９を用いて後記する。
【００５７】
リング探索部１２５は、到達性情報１３２に示される同じ宛先アドレスへの到達可能装置が２つ以上、いずれかのリングに含まれるまで、トポロジ情報１３１から、リングを構成する装置群を探索する。これにより、各リングに、同じ宛先アドレスへの現用装置と予備装置とが含まれることになる。
【００５８】
宛先アドレス抽出部１２６は、到達性情報１３２（図７（ｂ）参照）を参照して、リングを構成する装置群（例えば、図７（ａ）の装置Ａ，Ｂ，Ｃ，Ｄ）から到達可能な宛先アドレス群（例えば、宛先アドレスｄ１，ｄ２）を抽出する。
【００５９】
なお、経路表作成部１２３は、宛先アドレス抽出部１２６により抽出された宛先アドレス群に示される宛先アドレス（例えば、宛先アドレスｄ１，ｄ２）ごとに、当該宛先アドレスへの転送に用いる現用リンクおよび予備リンクを示した経路表１３３（図７（ｄ）参照）を作成する。
【００６０】
＜処理手順＞
次に、図７，８を参照しつつ、図９を用いて、経路表作成装置１０Ｂの処理手順を説明する。
【００６１】
まず、図８の経路表作成装置１０Ｂのリング探索部１２５は、到達性情報１３２およびトポロジ情報１３１を参照して、リング状に接続される装置群（例えば、図７（ａ）の装置Ａ，Ｂ，Ｃ，Ｄ）を探索する（Ｓ３１）。このリング状に接続される装置群の探索にあたっては、到達性情報１３２を参照して、当該リングが、同じ宛先アドレス（例えば、宛先アドレスｄ１）への到達可能装置を２つ以上を含むようなものを探索する。
【００６２】
宛先アドレス抽出部１２６は、到達性情報１３２を参照して、リングを構成する装置群（例えば装置Ａ，Ｂ，Ｃ，Ｄ）から到達できる宛先アドレス（例えば、宛先アドレスｄ１，ｄ２）を抽出する（Ｓ３２）。
【００６３】
リンク選択部１２２Ｂは、Ｓ３１で探索したリングを構成する装置４０のうち、ある装置４０から、Ｓ３２で抽出した宛先アドレス群（例えば、宛先アドレスｄ１，ｄ２）への現用リンクをリングの時計回りに決定し（Ｓ３３）、また、リンク選択部１２２Ｂは、この装置４０から、Ｓ３２で抽出した宛先アドレス群への現用リンクをリングの反時計回りに決定する（Ｓ３４）。つまり、リンク選択部１２２Ｂは、Ｓ３１で探索したリングを構成する装置４０（例えば、装置Ａ，Ｂ，Ｃ，Ｄ）のうち、ある装置４０（例えば、装置Ｃ）を始点装置として、その始点装置からリングの時計回りの方向に接続される装置４０（例えば、装置Ｄ）へのリンク（例えば、リンク＃５）を現用リンクとして選択する。また、リンク選択部１２２Ｂは、その始点装置からリングの反時計回りに接続される装置４０（例えば、装置Ａ）に接続へのリンク（例えば、リンク＃２）を予備リンクとして選択する。そして、経路表作成部１２３は、当該始点装置（装置４０）に関する経路表１３３の当該宛先アドレス群（例えば、宛先アドレスｄ１，ｄ２）への転送先の欄に、選択した現用リンクおよび予備リンクを記憶する。
【００６４】
ここで、Ｓ３１で探索したリングを構成する装置４０（例えば、装置Ａ，Ｂ，Ｃ，Ｄ）すべてについて処理を終了し（Ｓ３５のＹｅｓ）、かつ、到達性情報１３２に示されるすべての宛先アドレスについて、到達可能装置が２つ以上、いずれかのリングの装置群に属していれば（Ｓ３６のＹｅｓ）、経路表作成処理を終了する。
【００６５】
一方、Ｓ３１で探索したリングを構成する装置４０（例えば、装置Ａ，Ｂ，Ｃ，Ｄ）のうち未処理の装置４０があれば（Ｓ３５のＮｏ）、未処理の装置４０に対し、Ｓ３３以降の処理を行う。また、到達性情報１３２に示される到達可能装置のうち、まだ到達性情報１３２に示される宛先アドレスのうち、到達可能装置が２以上いずれかのリングの装置群に属していないものがあるとき（Ｓ３６のＮｏ）、Ｓ３１以降の処理を実行する。
【００６６】
このようにすることで、経路表作成装置１０Ｂは、経路表１３３の作成にあたり、各装置４０の現用リンクと予備リンクとをリング上での向きで決定するので、経路表作成の処理負荷を軽減できる。
【００６７】
＜第４の実施の形態＞
次に、第４の実施の形態を説明する。前記した実施の形態と同様の構成要素は、同じ符号を付して説明を省略する。第４の実施の形態の経路表作成装置１０Ｃは、図１０（ａ）に示すように、経路表計算を行うとき、まず、到達性情報１３２（図１０（ｂ）参照）およびトポロジ情報１３１（図１０（ｃ）参照）を参照して宛先グループを計算することを特徴とする。この宛先グループとは、同じ装置４０の集合から到達可能な宛先アドレス群をまとめたものである。そして、その宛先グループを用いて転送先計算を行い、各装置４０の転送先を示した経路表１３３を作成する。
【００６８】
この宛先グループの計算について、具体例を用いて説明すると、例えば、経路表作成装置１０Ｃが、図１０（ｂ）に示す到達性情報１３２を参照して、図１（ｂ）に示す通信ネットワークの経路計算を行う場合を考える。この場合、図１０（ｂ）の到達性情報１３２には、装置Ａ，Ｂともに到達可能な宛先アドレスとしてｄ１，ｄ２が設定されているので、宛先グループは、ｄ１，ｄ２となる。そして、経路表作成装置１０Ｃは、始点装置となる装置４０から、この宛先グループの宛先アドレス（宛先アドレスｄ１，ｄ２）への現用経路と予備経路とを計算する。このように、経路表作成装置１０Ｃは、宛先グループ単位で経路計算を行うので、宛先アドレス単位で経路計算を行う必要がなくなる。これにより、経路表作成の処理負荷を軽減できる。
【００６９】
このような経路表作成装置１０Ｃの処理部１２は、図１１に示すように、装置選択部１２１Ｃと、リンク選択部１２２と、経路表作成部１２３Ｃと、宛先グループ計算部１２７と、経路表送信部１２４とを備える。その他の構成は、前記した経路表作成装置１０と同様なので説明を省略する。
【００７０】
装置選択部１２１Ｃは、宛先グループ計算部１２７で計算された宛先グループごとに、到達性情報１３２を参照して、当該宛先グループの宛先アドレスへの到達可能装置群の中から、現用装置と予備装置とを選択する。例えば、図１０（ｂ）に示す到達性情報１３２において、宛先アドレスｄ１，ｄ２への到達可能装置は、装置Ａ，Ｂであるので、装置選択部１２１Ｃは、これらの装置のうち、装置Ａを現用装置として選択する。また、装置Ｂを予備装置として選択する。そして、装置選択部１２１Ｃは、この現用装置と予備装置との識別情報をリンク選択部１２２へ出力する。
【００７１】
経路表作成部１２３Ｃは、始点装置（例えば、装置Ａ，Ｂ，Ｃ，Ｄ）それぞれについて、宛先グループ（例えば、宛先アドレスｄ１，ｄ２）への現用リンクおよび予備リンクを示した経路表１３３（図１０（ｄ）参照）を作成する。
【００７２】
宛先グループ計算部１２７は、到達性情報１３２に、（１）宛先アドレスが複数ある到達可能装置が複数登録され、かつ、（２）その到達可能装置間で宛先アドレス群の少なくとも一部が同じであるとき、その到達可能装置それぞれに設定された宛先アドレスの集合である宛先グループを求める。例えば、図１０（ｂ）の到達性情報１３２上で、宛先アドレスが複数ある到達可能装置（装置４０）は装置Ａ，Ｂである。そして、その装置Ａ，Ｂの宛先アドレスはいずれもｄ１，ｄ２なので、宛先グループは、宛先アドレスｄ１，ｄ２となる。宛先グループ計算部１２７は、この計算した宛先グループを、装置選択部１２１Ｃへ出力する。
【００７３】
＜処理手順＞
次に、図１０，１１を参照しつつ、図１２を用いて、経路表作成装置１０Ｃの処理手順を説明する。
【００７４】
まず、図１１の経路表作成装置１０Ｃの宛先グループ計算部１２７は、到達性情報１３２に示される装置４０の中から、同じ装置４０の集合（装置Ａ，Ｂ）から到達可能な宛先アドレスの集合である宛先グループ（宛先アドレスｄ１，ｄ２）を計算する（Ｓ４１）。
【００７５】
次に、装置選択部１２１Ｃは、到達性情報１３２を参照して、ある宛先グループに対するすべての到達可能装置を抽出する（Ｓ４２）。例えば、図１０（ｂ）の到達性情報１３２上で、宛先グループ（宛先アドレスｄ１，ｄ２）に対する到達可能装置は装置Ａ，Ｂなので、装置Ａ，Ｂを抽出する。
【００７６】
そして、装置選択部１２１Ｃは、Ｓ４２で抽出した装置４０（例えば、装置Ａ，Ｂ）の中から、現用装置（例えば、装置Ａ）および予備装置（例えば、装置Ｂ）を選択する（Ｓ４３）。
【００７７】
次に、リンク選択部１２２は、図４のＳ１３と同様に、現用装置に到達するための現用リンクと、予備装置に到達するための予備リンクとを選択する（Ｓ４４）。つまり、リンク選択部１２２は、トポロジ情報１３１（図１０（ｃ）参照）に示される装置４０それぞれについて、当該装置４０（例えば、装置Ｃ）を始点装置としたとき、この始点装置から現用装置（例えば、装置Ａ）に到達するための現用リンク（例えば、リンク＃２）を選択する。また、この始点装置から予備装置（例えば、装置Ｂ）に到達するための予備リンク（例えば、リンク＃４）とを選択する。選択された始点装置（例えば、装置Ｃ）の宛先グループ（宛先アドレスｄ１，ｄ２）への現用リンク（例えば、リンク＃２）および予備リンク（例えば、リンク＃４）は、経路表作成部１２３が、当該始点装置の経路表１３３（図１０（ｄ）の装置Ｃの経路表１３３参照）に記憶する。
【００７８】
Ｓ４４の後、トポロジ情報１３１に示されるすべての装置４０について処理を終了し（Ｓ４５のＹｅｓ）、かつ、Ｓ４１で計算したすべての宛先グループについて処理を終了していれば（Ｓ４６のＹｅｓ）、経路表作成処理を終了する。
【００７９】
一方、トポロジ情報１３１に示される装置４０のうち、未処理の装置４０があれば（Ｓ４５のＮｏ）、装置選択部１２１Ｃは、この未処理の装置４０に対し、Ｓ４２以降の処理を行う。また、未処理の宛先グループがあれば（Ｓ４６のＮｏ）、装置選択部１２１Ｃは、その未処理の宛先グループについてＳ４１以降の処理を実行する。
【００８０】
このように経路表作成装置１０Ｃは、宛先グループを対象に現用リンクおよび予備リンクを求めるので、宛先アドレスごとに現用リンクおよび予備リンクを求める必要がなくなる。これにより、経路表作成の処理負荷を軽減できる。
【符号の説明】
【００８１】
１０，１０Ａ，１０Ｂ，１０Ｃ 経路表作成装置
１１ 入出力部
１２ 処理部
１３ 記憶部
２０ ネットワーク情報取得装置
４０ 装置
１２１，１２１Ａ，１２１Ｃ 装置選択部
１２２，１２２Ａ，１２２Ｂ，１２２Ｃ リンク選択部
１２３，１２３Ｃ 経路表作成部
１２４ 経路表送信部
１２５ リング探索部
１２６ 宛先アドレス抽出部
１２７ 宛先グループ計算部
１３１，１３１Ａ トポロジ情報
１３２ 到達性情報
１３３ 経路表
【技術分野】
【０００１】
本発明は、IP（Internet Protocol）網の各ルータ等において宛先アドレスまたはサブネットワークに対する転送先を決定するために用いられる経路表の作成技術に関する。
【背景技術】
【０００２】
従来、IP網内のルータ等の各装置がパケット転送に用いる経路表は、各装置が、ＯＳＰＦ（Open Shortest Path First）やＢＧＰ（Border Gateway Protocol）等のルーティングプロトコルを用いて作成する（非特許文献１，２参照）。また、網内の装置や、各装置間を接続するリンクに故障が発生したときに、高速に迂回経路への切り替えを行うため、各装置において、故障発生前の転送路（第１の転送路）に加え、迂回経路である第２の転送路を事前に計算しておく技術も提案されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】IETF RFC2328 “OSPF Version 2”, April 1998.
【非特許文献２】IETF RFC 4271, “A Border Gateway Protocol 4 (BGP-4)”, January 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、従来技術により、各装置においてルーティングプロトコルを動作させ、迂回経路を含む経路表を作成するのは処理負荷が大きいという問題があった。特に、網内の装置それぞれが、他の多数の装置と接続されているようなトポロジの場合（例えば、網内の各装置がフルメッシュで接続されているトポロジの場合）、各装置における経路表作成処理の負荷は極めて大きくなる。さらに、そこで、本発明は、前記した問題を解決し、網内の故障発生時の迂回経路を含む経路表の作成処理の負荷を軽減することを目的とする。
【課題を解決するための手段】
【０００５】
前記した課題を解決するため、本発明は、網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置が以下の処理を行う。すなわち、この経路表作成装置は、宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークへ到達可能な装置の識別情報を示した到達性情報の入力を受け付け記憶部に記憶する。また、ネットワークを構成する各装置の接続状態および各装置を接続するリンクを示したトポロジ情報の入力を受け付け記憶部に記憶する。そして、この経路表作成装置は、到達性情報に示される宛先アドレスごとに、当該宛先アドレスへ到達可能な装置群の中から、現用装置と予備装置とを選択する。そして、経路表作成装置は、トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、始点装置から当該宛先アドレスへ到達可能な現用装置への現用経路を計算する。また、この始点装置から当該宛先アドレスへ到達可能な予備装置への予備経路とを計算する。そして、トポロジ情報を参照して、始点装置が現用経路で用いるリンクである現用リンクと、予備経路で用いるリンクである予備リンクとを選択する。この後、経路表作成装置は、始点装置それぞれについて、宛先アドレスごとに、当該宛先アドレスへの現用リンクおよび予備リンクを示した経路表を作成する。そして、経路表作成装置は、作成した経路表を、始点装置である各装置へ送信する。
【０００６】
このように経路表作成装置が、網内の故障発生時の迂回経路を含む各装置の経路表を作成するので、各装置がルーティングプロトコルを動作させて経路表を作成する必要がなくなる。
【０００７】
本発明は、網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置が以下の処理を行う。すなわち、この経路表作成装置は、到達性情報の入力を受け付け記憶部に記憶する。また、ネットワークを構成する各装置の接続状態および各装置を接続するリンクと、当該リンクが現用経路に用いられる現用リンクである場合、当該リンクに対する予備リンクの識別情報とを含むトポロジ情報との入力を受け付け、記憶部に記憶する。そして、経路表作成装置は、到達性情報に示される宛先アドレスごとに、当該宛先アドレスへ到達可能な装置群の中から、現用装置を選択する。次に、トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、始点装置から当該宛先アドレスへ到達可能な現用装置への現用経路を計算する。そして、トポロジ情報を参照して、現用経路に用いる現用リンクを選択し、トポロジ情報において、この選択した現用リンクに対する予備リンクを選択する。その後、経路表作成装置は、始点装置それぞれについて、宛先アドレスごとに、当該宛先アドレスへの現用リンクおよび予備リンクを示した経路表を作成する作成する。そして、経路表作成装置は、作成した経路表を、始点装置である各装置へ送信する。
【０００８】
このように経路表作成装置が、網内の故障発生時の迂回経路を含む各装置の経路表を作成するので、各装置がルーティングプロトコルを動作させて経路表を作成する必要がなくなる。また、この経路表作成装置によれば、トポロジ情報上で現用リンクとペアになる予備リンクを選択して経路表を作成するので、経路表作成の処理負荷を軽減できる。
【０００９】
本発明は、網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置が以下の処理を行う。すなわち、この経路表作成装置は、到達性情報と、トポロジ情報との入力を受け付け、記憶部に記憶する。経路表作成装置は、到達性情報に示される同じ宛先アドレスへの到達可能装置が２つ以上いずれかのリングに含まれるまで、トポロジ情報を参照して、リングを構成する装置群を探索する。そして、到達性情報を参照して、リングを構成する装置群ごとに、当該装置群がエッジノードとなっている宛先アドレス群を抽出する。次に、経路表作成装置は、トポロジ情報を参照して、リングを構成する装置群の装置それぞれについて、当該装置を始点装置としたとき、当該装置群により構成されるリングにおいて第１の回転方向の装置に接続されるリンクを現用リンクとして選択する。また、（２）当該リングにおいて第１の回転方向と逆の回転方向の装置に接続されるリンクを予備リンクとして選択する。その後、経路表作成装置は、始点装置それぞれについて、宛先アドレス群に示される宛先アドレスごとに、当該宛先アドレスへの現用リンクおよび予備リンクを示した経路表を作成する作成する。そして、経路表作成装置は、作成した経路表を、始点装置である各装置へ送信する。
【００１０】
このように経路表作成装置が、網内の故障発生時の迂回経路を含む各装置の経路表を作成するので、各装置がルーティングプロトコルを動作させて経路表を作成する必要がなくなる。また、この経路表作成装置によれば、トポロジ情報に、リング状に接続される装置群がある場合、その中の始点装置からみて第１の回転方向（例えば、時計回りの方向）に接続されるリンクを当該宛先アドレスへの現用リンクとして選択する。また、第１の回転方向と逆の回転方向（例えば、反時計回りの方向）の装置に接続されるリンクを当該宛先アドレスへの予備リンクとして選択する。例えば、装置Ａ，Ｂ，Ｃ，Ｄがリング状に接続されている場合において、装置Ａから見て時計回りの方向に装置Ｂが接続されていれば、経路表作成装置は、装置Ａから装置Ｂへのリンクを、装置Ａから当該宛先アドレスへの現用リンクとして選択する。また、装置Ａから装置Ｃへのリンクを、装置Ａから当該宛先アドレスへの予備リンクとして選択する。このようにすることで、経路表作成装置は、経路表作成の処理負荷を軽減できる。
【００１１】
本発明は、網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置が以下の処理を行う。すなわち、この経路表作成装置は、到達性情報と、トポロジ情報との入力を受け付け、記憶部に記憶する。そして、経路表作成装置は、到達性情報に、宛先アドレスが複数ある装置が複数登録され、かつ、当該装置間で設定された宛先アドレス群の少なくとも一部が同じであるとき、当該装置それぞれの宛先アドレスの集合である宛先グループを計算する。次に、経路表作成装置は、到達性情報に示される宛先アドレスごとに、当該宛先アドレスへ到達可能な装置群の中から、現用装置と予備装置とを選択する。そして、経路表作成装置は、トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、始点装置から当該宛先アドレスに到達可能な現用装置への現用経路を計算する。また、この始点装置から当該宛先アドレスに到達可能な予備装置への予備経路とを計算する。そして、トポロジ情報を参照して、始点装置が現用経路で用いるリンクである現用リンクと、予備経路で用いるリンクである予備リンクとを選択する。その後、経路表作成装置は、始点装置それぞれについて、計算した宛先グループの宛先アドレスごとに、当該宛先グループの宛先アドレスへの現用リンクおよび予備リンクを示した経路表を作成する。そして、経路表作成装置は、この作成した経路表を、始点装置である各装置へ送信する。
【００１２】
このようにすることで、経路表作成装置は、宛先アドレスごとに現用リンクおよび予備リンクを求める必要がなくなる。つまり、始点装置から宛先アドレスそれぞれについて現用リンクおよび予備リンクを選択する必要がなくなるので、経路表作成の処理負荷を軽減できる。
【００１３】
また、本発明の経路表作成装置のリンク選択部は、現用経路および予備経路を計算するとき、トポロジ情報を参照して、ホップ数またはリンクコストが最小となる経路を計算する。
【００１４】
このようにすることで、経路表作成装置は、始点装置から現用装置（または予備装置）へのホップ数またはリンクコストが最小となる経路の経路表を作成できる。
【００１５】
また、本発明の経路表作成装置のリンク選択部は、現用経路および予備経路を計算するとき、トポロジ情報を参照して、現用経路および予備経路が互いに、同じ装置またはリンクを経由しない経路を選択する。
【００１６】
このようにすることで、経路表作成装置は、現用経路上で障害が発生したときでも、その障害の影響を受けづらい予備経路を含む経路表を作成できる。
【００１７】
また、本発明の経路表作成装置の装置選択部は、現用装置を選択するとき、トポロジ情報を参照して、当該宛先アドレスへのホップ数またはリンクコストが最小の装置を選択する。
【００１８】
このようにすることで、経路表作成装置は、始点装置から現用装置へのホップ数またはリンクコストが最小となる経路の経路表を作成できる。
【発明の効果】
【００１９】
本発明によれば、網内の故障発生時の迂回経路を含む経路表の作成処理の負荷を軽減できる。
【図面の簡単な説明】
【００２０】
【図１】（ａ）は、各実施の形態のシステムの全体構成を例示した図であり、（ｂ）は、通信ネットワークのトポロジを例示した図である。
【図２】（ａ）は、第１の実施の形態の経路表作成装置の処理概要を概念的に示した図であり、（ｂ）は、到達性情報を例示した図である。（ｃ）は、トポロジ情報を例示した図であり、（ｄ）は、経路表を例示した図である。
【図３】第１の実施の形態および第２の実施の形態の経路表作成装置の構成を示した図である。
【図４】第１の実施の形態の経路表作成装置の処理手順を示したフローチャートである。
【図５】（ａ）は、通信ネットワークのトポロジの例および第２の実施の形態の経路表作成装置の処理概要を概念的に示した図であり、（ｂ）は、到達性情報を例示した図である。（ｃ）は、トポロジ情報を例示した図であり、（ｄ）は、経路表を例示した図である。
【図６】第２の実施の形態の経路表作成装置の処理手順を示したフローチャートである。
【図７】（ａ）は、通信ネットワークのトポロジの例および第２の実施の形態の経路表作成装置の処理概要を概念的に示した図であり、（ｂ）は、到達性情報を例示した図である。（ｃ）は、トポロジ情報を例示した図であり、（ｄ）は、経路表を例示した図である。
【図８】第３の実施の形態の経路表作成装置の構成を示した図である。
【図９】第３の実施の形態の経路表作成装置の処理手順を示したフローチャートである。
【図１０】（ａ）は、第４の実施の形態の経路表作成装置の処理概要を概念的に示した図であり、（ｂ）は、到達性情報を例示した図である。（ｃ）は、トポロジ情報を例示した図であり、（ｄ）は、経路表を例示した図である。
【図１１】第４の実施の形態の経路表作成装置の構成を示した図である。
【図１２】第４の実施の形態の経路表作成装置の処理手順を示したフローチャートである。
【発明を実施するための形態】
【００２１】
以下、図面を参照しながら、本発明の実施の形態を、第１の実施の形態から第４の実施の形態に分けて説明する。まず、図１を用いて、各実施の形態の経路表作成装置１０，１０Ａ，１０Ｂ，１０Ｃに共通するシステムの全体構成例を説明する。
【００２２】
図１（ａ）に示すようにシステムは、通信ネットワークと、経路表作成装置１０と、ネットワーク情報取得装置２０とを含んで構成される。この通信ネットワークは、複数の装置４０（例えば、ＩＰルータ等のノード）がリンク（例えば、光ファイバ等）により接続されたＩＰ網等である。経路表作成装置１０，１０Ａ，１０Ｂ，１０Ｃは、ネットワーク情報取得装置２０から取得した情報（例えば、トポロジ情報１３１や到達性情報１３２の元となる情報）に基づき、各装置４０の経路表１３３（後記）を作成する。そして、この経路表１３３を各装置４０へ送信し、各装置４０は受信した経路表１３３に基づきパケットを転送する。ネットワーク情報取得装置２０は、通信ネットワークから各装置４０の接続状態等の情報を取得し、経路表作成装置１０，１０Ａ，１０Ｂ，１０Ｃへ送信する。経路表作成装置１０，１０Ａ，１０Ｂ，１０Ｃおよびネットワーク情報取得装置２０は、ＩＰ等の通信プロトコルにより通信可能なコンピュータにより実現される。この経路表作成装置１０，１０Ａ，１０Ｂ，１０Ｃは、現用経路のほかに、この現用経路の予備経路も含む経路表１３３を作成する。これにより、この経路表１３３を受信した各装置４０は、網内の障害発生時に迂回経路（予備経路）への切り替えを高速に行うことができる。
【００２３】
＜第１の実施の形態＞
まず、第１の実施の形態の経路表作成装置１０を説明する。ここでは、経路表作成装置１０が、図１（ｂ）に示すようなトポロジの通信ネットワークの経路表１３３を作成する場合を例に説明する。図１（ｂ）の装置Ａ，Ｂ，Ｃ，Ｄは、装置４０に相当する。装置Ａ，Ｂはそれぞれ宛先アドレスｄ１，ｄ２へ到達可能な装置であることを示す。この宛先アドレスは、宛先となる装置のＩＰアドレスでもよいし、サブネットワークのアドレスであってもよい。
【００２４】
経路表作成装置１０は、図２（ａ）に示すように、到達性情報１３２（宛先アドレスごとに、その宛先アドレスへの到達可能な通信ネットワークのエッジノードの装置４０を示した情報（図２（ｂ）参照））と、通信ネットワークのトポロジ情報１３１（図２（ｃ）参照）とを参照して経路表計算を行い、通信ネットワークにおける各装置４０の経路表１３３（図２（ｄ）参照）を作成する。この経路表１３３は、宛先アドレス（宛先）ごとに、その宛先アドレスへの第１の転送先へのリンク（現用リンク）と、第２の転送先へのリンク（予備リンク）とを示した情報である。つまり、経路表１３３は、通信ネットワーク内の故障発生時において装置４０が迂回経路への高速切り替えを実現するため、同じ宛先アドレスに対し現用リンクと予備リンクとの両方を示した情報である。なお、図２（ｄ）には、装置Ｃ，Ｄの経路表１３３のみを示しているが、装置Ａ，Ｂの経路表１３３についても同様に作成される。
【００２５】
次に、図３を用いて経路表作成装置１０の構成を説明する。経路表作成装置１０は、大きく入出力部（入力部および出力部）１１、処理部１２および記憶部１３に分けられる。入出力部１１は、ネットワーク情報取得装置２０や通信ネットワークの各装置４０とのデータ送受信を司る。例えば、トポロジ情報１３１や到達性情報１３２の元となる情報を取得したり、経路表作成装置１０で作成した各装置４０の経路表１３３を、各装置４０へ送信したりする。処理部１２は、この経路表作成装置１０全体の制御を司り、主に各装置４０の経路表１３３を作成する。記憶部１３は、処理部１２が各装置４０の経路表１３３を作成するときに参照する各種情報を記憶する。
【００２６】
入出力部１１は、入出力インタフェースやＩＰにより通信可能な通信インタフェース等から構成される。また、処理部１２は、この経路表作成装置１０（１０Ａ，１０Ｂ，１０Ｃ）が備えるＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。さらに、記憶部１３は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、経路表作成装置１０，１０Ａ，１０Ｂ，１０Ｃをプログラム実行処理により実現する場合、記憶部１３には、この経路表作成装置１０（１０Ａ，１０Ｂ，１０Ｃ）の機能を実現するためのプログラムが格納される。
【００２７】
記憶部１３は、トポロジ情報１３１と、到達性情報１３２とを記憶する。また、記憶部１３は、各装置４０の経路表１３３を記憶する領域を備える。
【００２８】
トポロジ情報１３１は、前記したとおり、通信ネットワークを構成する各装置４０の接続状態および各装置４０を接続するリンクを示した情報である。例えば、図２（ｃ）に示すトポロジ情報１３１は、図１（ｂ）に示す通信ネットワークのトポロジを示した情報であり、装置Ａ，Ｂ間はリンク＃１により接続されることを示す。なお、このトポロジ情報１３１は、各リンクのリンクコストの値を含んでいてもよい。また、例えば、装置Ａ→装置Ｂの通信に用いるリンクと、装置Ｂ→装置Ａの通信に用いるリンクとを区別する等、通信の方向によって用いるリンクを区別するようにしてもよい。
【００２９】
到達性情報１３２は、宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークに到達可能な装置４０（到達可能装置）の識別情報を示した情報である。例えば、図２（ｂ）に示す到達性情報１３２は、図１（ｂ）に示す通信ネットワークの到達性情報であり、宛先アドレスｄ１への到達可能装置は、装置Ａ，Ｂであり、宛先アドレスｄ２への到達可能装置も、装置Ａ，Ｂであることを示す。つまり、宛先アドレスｄ１，ｄ２へパケットを転送する場合、通信ネットワークの装置４０（始点装置）は、このいずれかの装置４０を目指してパケットを転送すればよいことを示す。
【００３０】
なお、このトポロジ情報１３１および到達性情報１３２は、経路表作成部１２３が経路表１３３を作成する際に参照される。このトポロジ情報１３１および到達性情報１３２は、ネットワーク情報取得装置２０から受信した情報をもとに処理部１２が作成してもよいし、予め外部装置で作成しておいたものを入出力部１１経由で入力してもよい。
【００３１】
処理部１２は、装置選択部１２１と、リンク選択部１２２と、経路表作成部１２３と、経路表送信部１２４とを備える。
【００３２】
装置選択部１２１は、到達性情報１３２（図２（ｂ）参照）に示される宛先アドレスへの到達可能装置の中から現用装置と予備装置とを選択する。選択した現用装置および予備装置それぞれの識別情報は、リンク選択部１２２へ出力する。なお、装置選択部１２１は、現用装置および予備装置を選択するとき、到達性情報１３２にＢＧＰ（Border Gate Protocol）の優先度の情報が含まれていれば、この優先度の値をもとに装置４０を選択してもよい。例えば、到達性情報１３２において、同じ宛先アドレスへの到達可能装置のうち、ＢＧＰの優先度が最も高い装置４０を現用装置として選択し、次に優先度が高い装置４０を予備装置として選択してもよい。また、装置選択部１２１は、現用装置および予備装置を選択する際、トポロジ情報１３１を参照して、始点装置からのホップ数やリンクコストの合計値をもとに現用装置および予備装置として選択してもよい。例えば、始点装置からのホップ数やリンクコストの合計値が最も小さい装置４０を、現用装置として選択し、その次に小さい装置４０を、予備装置として選択してもよい。
【００３３】
リンク選択部１２２は、トポロジ情報１３１（図２（ｃ）参照）に示される装置４０それぞれについて、当該装置４０を始点装置としたとき、この始点装置から現用装置への現用経路（第１の転送路）と、始点装置から予備装置への予備経路（第２の転送路）とを計算する。そして、トポロジ情報１３１に示されるリンク情報を参照して、始点装置が現用経路で用いるリンクである現用リンクおよび始点装置が予備経路で用いるリンクである予備リンクを選択する。そして、選択した各装置４０の現用リンクおよび予備リンクを、経路表作成部１２３へ出力する。また、リンク選択部１２２は、現用経路や予備経路を計算する際、同じ現用装置や予備装置への経路が複数あったとき、そのうちホップ数またはリンクコストが最小となる経路を選択してもよい。また、トポロジ情報１３１を参照して、現用経路および予備経路が互いに、同じ装置４０またはリンクを経由しない経路を選択するようにしてもよい。
【００３４】
経路表作成部１２３は、装置４０それぞれについて、宛先アドレスごとに、当該宛先アドレスへの現用リンクおよび予備リンクを示した経路表１３３（図２（ｄ）参照）を作成する。
【００３５】
経路表送信部１２４は、各装置４０の経路表１３３を、入出力部１１経由で通信ネットワーク装置の装置４０へ送信する。
【００３６】
このようにすることで経路表作成装置１０は、各装置４０の経路表１３３を作成し、各装置４０へ送信することができる。
【００３７】
＜処理手順＞
次に、図２，３を参照しつつ、図４を用いて、経路表作成装置１０の処理手順を説明する。
【００３８】
まず、図３の経路表作成装置１０の装置選択部１２１は、到達性情報１３２を参照して、ある宛先アドレス（例えば、図２（ａ）のｄ１）に対するすべての到達可能装置（例えば、装置Ａ，Ｂ）を抽出する（Ｓ１１）。つまり、到達性情報１３２に示される宛先アドレスから１つの宛先アドレスを選択し、宛先アドレスに対するすべての到達可能装置（装置４０）を抽出する。そして、装置選択部１２１は、抽出した到達可能装置から、現用装置（例えば、装置Ａ）と予備装置（例えば、装置Ｂ）とを選択する（Ｓ１２）。
【００３９】
次に、リンク選択部１２２は、トポロジ情報１３１（図２（ｃ）参照）に示される装置４０を１つ選択し、この装置４０（例えば、装置Ｃ）を始点装置として現用装置（例えば、装置Ａ）に到達するための現用リンク（例えば、リンク＃２）を選択する。また、この始点装置から予備装置（例えば、装置Ｂ）に到達するための予備リンク（例えば、リンク＃４）とを選択する（Ｓ１３）。つまり、まず、リンク選択部１２２は、始点装置から現用装置への現用経路と、始点装置から予備装置への予備経路とを計算する。そして、トポロジ情報１３１に示されるリンク情報を参照して、始点装置が現用経路で用いるリンクである現用リンクおよび予備経路で用いるリンクである予備リンクを選択する。選択された始点装置の現用リンクおよび予備リンクは、経路表作成部１２３が、当該始点装置（装置４０）に関する経路表１３３に記憶する。
【００４０】
そして、トポロジ情報１３１に示されるすべての装置４０について処理を終了し（Ｓ１４のＹｅｓ）、かつ、到達性情報１３２に示されるすべての宛先アドレスについて処理を終了していれば（Ｓ１５のＹｅｓ）、経路表作成処理を終了する。そして、経路表送信部１２４が、経路表１３３を、各装置４０へ送信する。
【００４１】
一方、トポロジ情報１３１に示される装置４０のうち、未処理の装置４０があれば（Ｓ１４のＮｏ）、装置選択部１２１は、未処理の装置４０に対し、Ｓ１２以降の処理を行う。また、到達性情報１３２に示される宛先アドレスについて未処理の宛先アドレスがあれば（Ｓ１５のＮｏ）、装置選択部１２１は、その未処理の宛先アドレスについてＳ１１以降の処理を実行する。
【００４２】
このようにすることで、経路表作成装置１０は、通信ネットワークの各装置４０で用いる経路表１３３を作成することができる。この経路表１３３は、各宛先アドレスの現用経路へのリンク（現用リンク）のみならず、予備経路へのリンク（予備リンク）も含む。よって、各装置４０は、網内に障害が発生した場合でも、迂回経路への経路切り替えを高速に行うことができる。
【００４３】
＜第２の実施の形態＞
次に、第２の実施の形態の経路表作成装置１０Ａを説明する。前記した実施の形態と同様の構成要素は、同じ符号を付して説明を省略する。
【００４４】
経路表作成装置１０Ａは、図５（ａ）に示すように、経路表計算を行う際、到達性情報１３２（図５（ｂ）参照）と、トポロジ情報１３１Ａ（図５（ｃ）参照）とを参照することを特徴とする。このトポロジ情報１３１Ａは、図５（ｃ）に例示するように、各リンクが、現用経路に用いるリンク（現用リンク）か、予備経路に用いるリンク（予備リンク）であるかを示す情報を含む。また、当該リンクが現用リンクである場合、ペアとなる予備リンクの識別情報を含み、当該リンクが予備リンクである場合、ペアとなる現用リンクの識別情報を含む。そして、経路表作成装置１０Ａは、ある装置４０の現用リンクを求めた後、予備リンクを選択するときには、このトポロジ情報１３１Ａに示される当該現用リンクの予備リンクを選択する。
【００４５】
このような経路表作成装置１０Ａの処理部１２は、図３に示すように、装置選択部１２１に代えて、装置選択部１２１Ａを備え、リンク選択部１２２に代えてリンク選択部１２２Ａを備える。さらに、トポロジ情報１３１に代えてトポロジ情報１３１Ａを備える。その他の構成は、経路表作成装置１０と同様なので説明を省略する。
【００４６】
装置選択部１２１Ａは、到達性情報１３２に示される宛先アドレスごとに、当該宛先アドレスへの到達可能装置群の中から、現用装置を選択する。選択した現用装置は、リンク選択部１２２Ａへ出力する。なお、この現用装置を選択するとき、例えば、トポロジ情報１３１Ａを参照して、当該宛先アドレスへのホップ数またはリンクコストが最小の装置を選択する。
【００４７】
リンク選択部１２２Ａは、トポロジ情報１３１に示される装置４０それぞれについて、当該装置４０を始点装置としたとき、始点装置から、装置選択部１２１Ａで選択した現用装置への現用経路を計算する。そして、トポロジ情報１３１Ａを参照して、現用経路に用いる現用リンクを選択すると、トポロジ情報１３１Ａを参照して、この現用リンクとペアになる予備リンクを選択する。選択した現用リンクおよび予備リンクは、経路表作成部１２３へ出力する。なお、このトポロジ情報１３１Ａに現用リンクの予備リンクが無い場合には、リンク選択部１２２Ａは、第１の実施の形態と同様に、現用装置と同じ宛先アドレスへの到達可能装置から予備装置を選択し、この予備装置への経路を計算して、予備リンクを求めるようにしてよい。
【００４８】
＜処理手順＞
次に、図３，５を参照しつつ、図６を用いて、経路表作成装置１０Ａの処理手順を説明する。Ｓ２１は、前記したＳ１１と同様なので、Ｓ２２から説明する。経路表作成装置１０Ａの装置選択部１２１Ａは、Ｓ２１で抽出した到達可能装置から、装置４０を１つ選択する（Ｓ２２）。例えば、図５（ａ）の装置Ａを選択する。
【００４９】
次に、リンク選択部１２２Ａは、トポロジ情報１３１Ａ（図５（ｃ）参照）に示される装置４０それぞれについて、当該装置４０を始点装置（例えば、装置Ｃ）としたとき、始点装置から、Ｓ２２で選択した装置４０（例えば、装置Ａ）に到達するための現用リンク（例えば、リンク＃２）を、トポロジ情報１３１Ａを参照して選択する（Ｓ２３）。つまり、リンク選択部１２２Ａは、Ｓ２２で選択した装置４０を現用装置として、始点装置からこの現用装置への現用経路を計算する。そして、トポロジ情報１３１Ａに示されるリンク情報を参照して、始点装置で用いる現用リンクを選択する。
【００５０】
また、リンク選択部１２２Ａは、トポロジ情報１３１Ａを参照して、Ｓ２３で選択したリンク（現用リンク）の予備リンク（例えば、リンク＃５）を選択する（Ｓ２４）。選択した始点装置の現用リンクおよび予備リンクは、経路表作成部１２３が、当該始点装置（例えば、装置Ｃ）の経路表１３３に記録する。この後のＳ２５およびＳ２６の処理は、前記したＳ１４およびＳ１５の処理と同様なので説明を省略する。
【００５１】
このような経路表作成装置１０Ａによれば、予備リンクを選択する際、トポロジ情報１３１Ａ上に設定されている予備リンクを選択すればよいので、経路表作成の処理負荷を軽減できる。
【００５２】
＜第３の実施の形態＞
次に、第３の実施の形態を説明する。前記した実施の形態と同様の構成要素は、同じ符号を付して説明を省略する。
【００５３】
経路表作成装置１０Ｂは、図７（ａ）に示すように、経路表計算を行うとき、トポロジ上でリング状に接続される装置４０を探索するリング探索を行い、このリングを用いて転送先計算を行うことを特徴とする。
【００５４】
例えば、経路表作成装置１０Ｂは、宛先アドレスｄ１，ｄ２への到達可能装置である装置Ａ，Ｂを含むリング（装置Ａ，Ｂ，Ｃ，Ｄ）を用いる場合を考える。この場合、装置Ｃから宛先アドレスｄ１（またはｄ２）への現用リンクとして、自身の装置Ｃを含むリングの時計周りの方向に隣接する装置Ｄへのリンク＃５を選択する。また、予備リンクとして、リングの反時計周りの方向に隣接する装置Ａへのリンク＃２を選択する。つまり、トポロジ上で、ある宛先アドレスへの到達可能装置を複数含むリングを見つければ、そのリングを構成する装置４０はそれぞれ、その宛先アドレスへのリンクを２本持つことになる。よって、その２本のリンクのうち１本のリンクを現用リンクとし、もう１本のリンクを予備リンクとすれば、現用リンクと予備リンクとを１本ずつ選ぶことができる。
【００５５】
このような経路表作成装置１０Ｂの処理部１２は、図８に示すように、リンク選択部１２２Ｂと、経路表作成部１２３と、経路表送信部１２４と、リング探索部１２５と、宛先アドレス抽出部１２６とを備える。
【００５６】
リンク選択部１２２Ｂは、トポロジ情報１３１（図７（ｃ）参照）に示されるリンク情報を参照して、リングを構成する装置群の装置４０それぞれについて、各装置４０を始点装置としたときの現用リンクと予備リンクとを選択する。このリンク選択部１２２Ｂのリンク選択処理の詳細は、図９を用いて後記する。
【００５７】
リング探索部１２５は、到達性情報１３２に示される同じ宛先アドレスへの到達可能装置が２つ以上、いずれかのリングに含まれるまで、トポロジ情報１３１から、リングを構成する装置群を探索する。これにより、各リングに、同じ宛先アドレスへの現用装置と予備装置とが含まれることになる。
【００５８】
宛先アドレス抽出部１２６は、到達性情報１３２（図７（ｂ）参照）を参照して、リングを構成する装置群（例えば、図７（ａ）の装置Ａ，Ｂ，Ｃ，Ｄ）から到達可能な宛先アドレス群（例えば、宛先アドレスｄ１，ｄ２）を抽出する。
【００５９】
なお、経路表作成部１２３は、宛先アドレス抽出部１２６により抽出された宛先アドレス群に示される宛先アドレス（例えば、宛先アドレスｄ１，ｄ２）ごとに、当該宛先アドレスへの転送に用いる現用リンクおよび予備リンクを示した経路表１３３（図７（ｄ）参照）を作成する。
【００６０】
＜処理手順＞
次に、図７，８を参照しつつ、図９を用いて、経路表作成装置１０Ｂの処理手順を説明する。
【００６１】
まず、図８の経路表作成装置１０Ｂのリング探索部１２５は、到達性情報１３２およびトポロジ情報１３１を参照して、リング状に接続される装置群（例えば、図７（ａ）の装置Ａ，Ｂ，Ｃ，Ｄ）を探索する（Ｓ３１）。このリング状に接続される装置群の探索にあたっては、到達性情報１３２を参照して、当該リングが、同じ宛先アドレス（例えば、宛先アドレスｄ１）への到達可能装置を２つ以上を含むようなものを探索する。
【００６２】
宛先アドレス抽出部１２６は、到達性情報１３２を参照して、リングを構成する装置群（例えば装置Ａ，Ｂ，Ｃ，Ｄ）から到達できる宛先アドレス（例えば、宛先アドレスｄ１，ｄ２）を抽出する（Ｓ３２）。
【００６３】
リンク選択部１２２Ｂは、Ｓ３１で探索したリングを構成する装置４０のうち、ある装置４０から、Ｓ３２で抽出した宛先アドレス群（例えば、宛先アドレスｄ１，ｄ２）への現用リンクをリングの時計回りに決定し（Ｓ３３）、また、リンク選択部１２２Ｂは、この装置４０から、Ｓ３２で抽出した宛先アドレス群への現用リンクをリングの反時計回りに決定する（Ｓ３４）。つまり、リンク選択部１２２Ｂは、Ｓ３１で探索したリングを構成する装置４０（例えば、装置Ａ，Ｂ，Ｃ，Ｄ）のうち、ある装置４０（例えば、装置Ｃ）を始点装置として、その始点装置からリングの時計回りの方向に接続される装置４０（例えば、装置Ｄ）へのリンク（例えば、リンク＃５）を現用リンクとして選択する。また、リンク選択部１２２Ｂは、その始点装置からリングの反時計回りに接続される装置４０（例えば、装置Ａ）に接続へのリンク（例えば、リンク＃２）を予備リンクとして選択する。そして、経路表作成部１２３は、当該始点装置（装置４０）に関する経路表１３３の当該宛先アドレス群（例えば、宛先アドレスｄ１，ｄ２）への転送先の欄に、選択した現用リンクおよび予備リンクを記憶する。
【００６４】
ここで、Ｓ３１で探索したリングを構成する装置４０（例えば、装置Ａ，Ｂ，Ｃ，Ｄ）すべてについて処理を終了し（Ｓ３５のＹｅｓ）、かつ、到達性情報１３２に示されるすべての宛先アドレスについて、到達可能装置が２つ以上、いずれかのリングの装置群に属していれば（Ｓ３６のＹｅｓ）、経路表作成処理を終了する。
【００６５】
一方、Ｓ３１で探索したリングを構成する装置４０（例えば、装置Ａ，Ｂ，Ｃ，Ｄ）のうち未処理の装置４０があれば（Ｓ３５のＮｏ）、未処理の装置４０に対し、Ｓ３３以降の処理を行う。また、到達性情報１３２に示される到達可能装置のうち、まだ到達性情報１３２に示される宛先アドレスのうち、到達可能装置が２以上いずれかのリングの装置群に属していないものがあるとき（Ｓ３６のＮｏ）、Ｓ３１以降の処理を実行する。
【００６６】
このようにすることで、経路表作成装置１０Ｂは、経路表１３３の作成にあたり、各装置４０の現用リンクと予備リンクとをリング上での向きで決定するので、経路表作成の処理負荷を軽減できる。
【００６７】
＜第４の実施の形態＞
次に、第４の実施の形態を説明する。前記した実施の形態と同様の構成要素は、同じ符号を付して説明を省略する。第４の実施の形態の経路表作成装置１０Ｃは、図１０（ａ）に示すように、経路表計算を行うとき、まず、到達性情報１３２（図１０（ｂ）参照）およびトポロジ情報１３１（図１０（ｃ）参照）を参照して宛先グループを計算することを特徴とする。この宛先グループとは、同じ装置４０の集合から到達可能な宛先アドレス群をまとめたものである。そして、その宛先グループを用いて転送先計算を行い、各装置４０の転送先を示した経路表１３３を作成する。
【００６８】
この宛先グループの計算について、具体例を用いて説明すると、例えば、経路表作成装置１０Ｃが、図１０（ｂ）に示す到達性情報１３２を参照して、図１（ｂ）に示す通信ネットワークの経路計算を行う場合を考える。この場合、図１０（ｂ）の到達性情報１３２には、装置Ａ，Ｂともに到達可能な宛先アドレスとしてｄ１，ｄ２が設定されているので、宛先グループは、ｄ１，ｄ２となる。そして、経路表作成装置１０Ｃは、始点装置となる装置４０から、この宛先グループの宛先アドレス（宛先アドレスｄ１，ｄ２）への現用経路と予備経路とを計算する。このように、経路表作成装置１０Ｃは、宛先グループ単位で経路計算を行うので、宛先アドレス単位で経路計算を行う必要がなくなる。これにより、経路表作成の処理負荷を軽減できる。
【００６９】
このような経路表作成装置１０Ｃの処理部１２は、図１１に示すように、装置選択部１２１Ｃと、リンク選択部１２２と、経路表作成部１２３Ｃと、宛先グループ計算部１２７と、経路表送信部１２４とを備える。その他の構成は、前記した経路表作成装置１０と同様なので説明を省略する。
【００７０】
装置選択部１２１Ｃは、宛先グループ計算部１２７で計算された宛先グループごとに、到達性情報１３２を参照して、当該宛先グループの宛先アドレスへの到達可能装置群の中から、現用装置と予備装置とを選択する。例えば、図１０（ｂ）に示す到達性情報１３２において、宛先アドレスｄ１，ｄ２への到達可能装置は、装置Ａ，Ｂであるので、装置選択部１２１Ｃは、これらの装置のうち、装置Ａを現用装置として選択する。また、装置Ｂを予備装置として選択する。そして、装置選択部１２１Ｃは、この現用装置と予備装置との識別情報をリンク選択部１２２へ出力する。
【００７１】
経路表作成部１２３Ｃは、始点装置（例えば、装置Ａ，Ｂ，Ｃ，Ｄ）それぞれについて、宛先グループ（例えば、宛先アドレスｄ１，ｄ２）への現用リンクおよび予備リンクを示した経路表１３３（図１０（ｄ）参照）を作成する。
【００７２】
宛先グループ計算部１２７は、到達性情報１３２に、（１）宛先アドレスが複数ある到達可能装置が複数登録され、かつ、（２）その到達可能装置間で宛先アドレス群の少なくとも一部が同じであるとき、その到達可能装置それぞれに設定された宛先アドレスの集合である宛先グループを求める。例えば、図１０（ｂ）の到達性情報１３２上で、宛先アドレスが複数ある到達可能装置（装置４０）は装置Ａ，Ｂである。そして、その装置Ａ，Ｂの宛先アドレスはいずれもｄ１，ｄ２なので、宛先グループは、宛先アドレスｄ１，ｄ２となる。宛先グループ計算部１２７は、この計算した宛先グループを、装置選択部１２１Ｃへ出力する。
【００７３】
＜処理手順＞
次に、図１０，１１を参照しつつ、図１２を用いて、経路表作成装置１０Ｃの処理手順を説明する。
【００７４】
まず、図１１の経路表作成装置１０Ｃの宛先グループ計算部１２７は、到達性情報１３２に示される装置４０の中から、同じ装置４０の集合（装置Ａ，Ｂ）から到達可能な宛先アドレスの集合である宛先グループ（宛先アドレスｄ１，ｄ２）を計算する（Ｓ４１）。
【００７５】
次に、装置選択部１２１Ｃは、到達性情報１３２を参照して、ある宛先グループに対するすべての到達可能装置を抽出する（Ｓ４２）。例えば、図１０（ｂ）の到達性情報１３２上で、宛先グループ（宛先アドレスｄ１，ｄ２）に対する到達可能装置は装置Ａ，Ｂなので、装置Ａ，Ｂを抽出する。
【００７６】
そして、装置選択部１２１Ｃは、Ｓ４２で抽出した装置４０（例えば、装置Ａ，Ｂ）の中から、現用装置（例えば、装置Ａ）および予備装置（例えば、装置Ｂ）を選択する（Ｓ４３）。
【００７７】
次に、リンク選択部１２２は、図４のＳ１３と同様に、現用装置に到達するための現用リンクと、予備装置に到達するための予備リンクとを選択する（Ｓ４４）。つまり、リンク選択部１２２は、トポロジ情報１３１（図１０（ｃ）参照）に示される装置４０それぞれについて、当該装置４０（例えば、装置Ｃ）を始点装置としたとき、この始点装置から現用装置（例えば、装置Ａ）に到達するための現用リンク（例えば、リンク＃２）を選択する。また、この始点装置から予備装置（例えば、装置Ｂ）に到達するための予備リンク（例えば、リンク＃４）とを選択する。選択された始点装置（例えば、装置Ｃ）の宛先グループ（宛先アドレスｄ１，ｄ２）への現用リンク（例えば、リンク＃２）および予備リンク（例えば、リンク＃４）は、経路表作成部１２３が、当該始点装置の経路表１３３（図１０（ｄ）の装置Ｃの経路表１３３参照）に記憶する。
【００７８】
Ｓ４４の後、トポロジ情報１３１に示されるすべての装置４０について処理を終了し（Ｓ４５のＹｅｓ）、かつ、Ｓ４１で計算したすべての宛先グループについて処理を終了していれば（Ｓ４６のＹｅｓ）、経路表作成処理を終了する。
【００７９】
一方、トポロジ情報１３１に示される装置４０のうち、未処理の装置４０があれば（Ｓ４５のＮｏ）、装置選択部１２１Ｃは、この未処理の装置４０に対し、Ｓ４２以降の処理を行う。また、未処理の宛先グループがあれば（Ｓ４６のＮｏ）、装置選択部１２１Ｃは、その未処理の宛先グループについてＳ４１以降の処理を実行する。
【００８０】
このように経路表作成装置１０Ｃは、宛先グループを対象に現用リンクおよび予備リンクを求めるので、宛先アドレスごとに現用リンクおよび予備リンクを求める必要がなくなる。これにより、経路表作成の処理負荷を軽減できる。
【符号の説明】
【００８１】
１０，１０Ａ，１０Ｂ，１０Ｃ 経路表作成装置
１１ 入出力部
１２ 処理部
１３ 記憶部
２０ ネットワーク情報取得装置
４０ 装置
１２１，１２１Ａ，１２１Ｃ 装置選択部
１２２，１２２Ａ，１２２Ｂ，１２２Ｃ リンク選択部
１２３，１２３Ｃ 経路表作成部
１２４ 経路表送信部
１２５ リング探索部
１２６ 宛先アドレス抽出部
１２７ 宛先グループ計算部
１３１，１３１Ａ トポロジ情報
１３２ 到達性情報
１３３ 経路表
【特許請求の範囲】
【請求項１】
網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置であって、
宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークへ到達可能な装置の識別情報を示した到達性情報と、前記ネットワークを構成する各装置の接続状態および前記各装置を接続するリンクを示したトポロジ情報との入力を受け付け、記憶部に記憶する入力部と、
前記到達性情報に示される宛先アドレスごとに、当該宛先アドレスへ到達可能な装置群の中から、現用装置と予備装置とを選択する装置選択部と、
前記トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、前記始点装置から当該宛先アドレスへ到達可能な前記現用装置への現用経路と、前記始点装置から当該宛先アドレスへ到達可能な前記予備装置への予備経路とを計算し、前記トポロジ情報を参照して、前記始点装置が前記現用経路で用いるリンクである現用リンクと、前記予備経路で用いるリンクである予備リンクとを選択するリンク選択部と、
前記始点装置それぞれについて、前記宛先アドレスごとに、当該宛先アドレスへの前記現用リンクおよび前記予備リンクを示した経路表を作成する経路表作成部と、
前記作成した経路表を、前記始点装置である各装置へ送信する出力部とを備えることを特徴とする経路表作成装置。
【請求項２】
網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置であって、
宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークへ到達可能な装置の識別情報を示した到達性情報と、前記ネットワークを構成する各装置の接続状態および前記各装置を接続するリンクならびに当該リンクが現用経路に用いられる現用リンクである場合、当該リンクに対する予備リンクの識別情報を含むトポロジ情報との入力を受け付け、記憶部に記憶する入力部と、
前記到達性情報に示される宛先アドレスごとに、当該宛先アドレスへ到達可能な装置群の中から、現用装置を選択する装置選択部と、
前記トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、前記始点装置から当該宛先アドレスへ到達可能な前記現用装置への現用経路を計算し、前記トポロジ情報を参照して、前記始点装置が前記現用経路に用いる現用リンクを選択し、前記トポロジ情報において前記選択した現用リンクに対する予備リンクを選択するリンク選択部と、
前記始点装置それぞれについて、前記宛先アドレスごとに、当該宛先アドレスへの前記現用リンクおよび前記予備リンクを示した経路表を作成する作成する経路表作成部と、
前記作成した経路表を、前記始点装置である各装置へ送信する出力部とを備えることを特徴とする経路表作成装置。
【請求項３】
網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置であって、
宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークへ到達可能な装置の識別情報を示した到達性情報と、前記ネットワークを構成する各装置の接続状態および前記各装置を接続するリンクを示したトポロジ情報との入力を受け付け、記憶部に記憶する入力部と、
前記到達性情報に示される同じ宛先アドレスへの到達可能装置が２つ以上いずれかのリングに含まれるまで、前記トポロジ情報を参照して、前記リングを構成する装置群を探索するリング探索部と、
前記到達性情報を参照して、前記リングを構成する装置群ごとに、当該装置群がエッジノードとなっている宛先アドレス群を抽出する宛先アドレス抽出部と、
前記トポロジ情報を参照して、前記リングを構成する装置群の装置それぞれについて、当該装置を始点装置としたとき、（１）当該装置群により構成されるリングにおいて第１の回転方向の装置に接続されるリンクを現用リンクとして選択し、（２）当該リングにおいて第１の回転方向と逆の回転方向の装置に接続されるリンクを予備リンクとして選択するリンク選択部と、
前記始点装置それぞれについて、前記宛先アドレス群に示される宛先アドレスごとに、当該宛先アドレスへの前記現用リンクおよび前記予備リンクを示した経路表を作成する作成する経路表作成部と、
前記作成した経路表を、前記始点装置である各装置へ送信する出力部とを備えることを特徴とする経路表作成装置。
【請求項４】
網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置であって、
宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークへ到達可能な装置の識別情報を示した到達性情報と、前記ネットワークを構成する各装置の接続状態および前記各装置を接続するリンクを示したトポロジ情報との入力を受け付け、記憶部に記憶する入力部と、
前記到達性情報に、前記宛先アドレスが複数ある装置が複数登録され、かつ、当該装置間で前記設定された宛先アドレス群の少なくとも一部が同じであるとき、当該装置それぞれの宛先アドレスの集合である宛先グループを計算する宛先グループ計算部と、
前記到達性情報に示される宛先アドレスごとに、当該宛先アドレスへ到達可能な装置群の中から、現用装置と予備装置とを選択する装置選択部と、
前記トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、前記始点装置から当該宛先アドレスに到達可能な前記現用装置への現用経路と、前記始点装置から当該宛先アドレスに到達可能な前記予備装置への予備経路とを計算し、前記トポロジ情報を参照して、前記始点装置が前記現用経路で用いるリンクである現用リンクと、前記予備経路で用いるリンクである予備リンクとを選択するリンク選択部と、
前記始点装置それぞれについて、前記計算した宛先グループの宛先アドレスごとに、当該宛先グループの宛先アドレスへの前記現用リンクおよび前記予備リンクを示した経路表を作成する経路表作成部と、
前記作成した経路表を、前記始点装置である各装置へ送信する出力部とを備えることを特徴とする経路表作成装置。
【請求項５】
前記リンク選択部は、
前記現用経路および予備経路を計算するとき、
前記トポロジ情報を参照して、ホップ数またはリンクコストが最小となる経路を計算することを特徴とする請求項１、請求項２および請求項４のいずれか１項に記載の経路表作成装置。
【請求項６】
前記リンク選択部は、
前記現用経路および予備経路を計算するとき、
前記トポロジ情報を参照して、前記現用経路および予備経路が互いに、同じ装置またはリンクを経由しない経路を選択することを特徴とする請求項１、請求項２および請求項４のいずれか１項に記載の経路表作成装置。
【請求項７】
前記装置選択部は、
前記現用装置を選択するとき、前記トポロジ情報を参照して、当該宛先アドレスへのホップ数またはリンクコストが最小の装置を選択することを特徴とする請求項３に記載の経路表作成装置。
【請求項８】
網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置が、
宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークへ到達可能な装置の識別情報を示した到達性情報と、前記ネットワークを構成する各装置の接続状態および前記各装置を接続するリンクを示したトポロジ情報との入力を受け付け、記憶部に記憶するステップと、
前記到達性情報に示される宛先アドレスごとに、当該宛先アドレスへパケットを転送するエッジノードの装置群の中から、現用装置と予備装置とを選択するステップと、、
前記トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、前記始点装置から前記現用装置への現用経路と、前記始点装置から前記予備装置への予備経路とを計算し、前記トポロジ情報を参照して、前記始点装置が前記現用経路で用いるリンクである現用リンクおよび前記予備経路で用いるリンクである予備リンクを選択するステップと、
前記始点装置それぞれについて、前記宛先アドレスごとに、当該宛先アドレスへの前記現用リンクおよび前記予備リンクを示した経路表を作成するステップと、
前記作成した経路表を、前記始点装置である各装置へ送信するステップとを実行する経路表作成方法。
【請求項１】
網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置であって、
宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークへ到達可能な装置の識別情報を示した到達性情報と、前記ネットワークを構成する各装置の接続状態および前記各装置を接続するリンクを示したトポロジ情報との入力を受け付け、記憶部に記憶する入力部と、
前記到達性情報に示される宛先アドレスごとに、当該宛先アドレスへ到達可能な装置群の中から、現用装置と予備装置とを選択する装置選択部と、
前記トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、前記始点装置から当該宛先アドレスへ到達可能な前記現用装置への現用経路と、前記始点装置から当該宛先アドレスへ到達可能な前記予備装置への予備経路とを計算し、前記トポロジ情報を参照して、前記始点装置が前記現用経路で用いるリンクである現用リンクと、前記予備経路で用いるリンクである予備リンクとを選択するリンク選択部と、
前記始点装置それぞれについて、前記宛先アドレスごとに、当該宛先アドレスへの前記現用リンクおよび前記予備リンクを示した経路表を作成する経路表作成部と、
前記作成した経路表を、前記始点装置である各装置へ送信する出力部とを備えることを特徴とする経路表作成装置。
【請求項２】
網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置であって、
宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークへ到達可能な装置の識別情報を示した到達性情報と、前記ネットワークを構成する各装置の接続状態および前記各装置を接続するリンクならびに当該リンクが現用経路に用いられる現用リンクである場合、当該リンクに対する予備リンクの識別情報を含むトポロジ情報との入力を受け付け、記憶部に記憶する入力部と、
前記到達性情報に示される宛先アドレスごとに、当該宛先アドレスへ到達可能な装置群の中から、現用装置を選択する装置選択部と、
前記トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、前記始点装置から当該宛先アドレスへ到達可能な前記現用装置への現用経路を計算し、前記トポロジ情報を参照して、前記始点装置が前記現用経路に用いる現用リンクを選択し、前記トポロジ情報において前記選択した現用リンクに対する予備リンクを選択するリンク選択部と、
前記始点装置それぞれについて、前記宛先アドレスごとに、当該宛先アドレスへの前記現用リンクおよび前記予備リンクを示した経路表を作成する作成する経路表作成部と、
前記作成した経路表を、前記始点装置である各装置へ送信する出力部とを備えることを特徴とする経路表作成装置。
【請求項３】
網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置であって、
宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークへ到達可能な装置の識別情報を示した到達性情報と、前記ネットワークを構成する各装置の接続状態および前記各装置を接続するリンクを示したトポロジ情報との入力を受け付け、記憶部に記憶する入力部と、
前記到達性情報に示される同じ宛先アドレスへの到達可能装置が２つ以上いずれかのリングに含まれるまで、前記トポロジ情報を参照して、前記リングを構成する装置群を探索するリング探索部と、
前記到達性情報を参照して、前記リングを構成する装置群ごとに、当該装置群がエッジノードとなっている宛先アドレス群を抽出する宛先アドレス抽出部と、
前記トポロジ情報を参照して、前記リングを構成する装置群の装置それぞれについて、当該装置を始点装置としたとき、（１）当該装置群により構成されるリングにおいて第１の回転方向の装置に接続されるリンクを現用リンクとして選択し、（２）当該リングにおいて第１の回転方向と逆の回転方向の装置に接続されるリンクを予備リンクとして選択するリンク選択部と、
前記始点装置それぞれについて、前記宛先アドレス群に示される宛先アドレスごとに、当該宛先アドレスへの前記現用リンクおよび前記予備リンクを示した経路表を作成する作成する経路表作成部と、
前記作成した経路表を、前記始点装置である各装置へ送信する出力部とを備えることを特徴とする経路表作成装置。
【請求項４】
網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置であって、
宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークへ到達可能な装置の識別情報を示した到達性情報と、前記ネットワークを構成する各装置の接続状態および前記各装置を接続するリンクを示したトポロジ情報との入力を受け付け、記憶部に記憶する入力部と、
前記到達性情報に、前記宛先アドレスが複数ある装置が複数登録され、かつ、当該装置間で前記設定された宛先アドレス群の少なくとも一部が同じであるとき、当該装置それぞれの宛先アドレスの集合である宛先グループを計算する宛先グループ計算部と、
前記到達性情報に示される宛先アドレスごとに、当該宛先アドレスへ到達可能な装置群の中から、現用装置と予備装置とを選択する装置選択部と、
前記トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、前記始点装置から当該宛先アドレスに到達可能な前記現用装置への現用経路と、前記始点装置から当該宛先アドレスに到達可能な前記予備装置への予備経路とを計算し、前記トポロジ情報を参照して、前記始点装置が前記現用経路で用いるリンクである現用リンクと、前記予備経路で用いるリンクである予備リンクとを選択するリンク選択部と、
前記始点装置それぞれについて、前記計算した宛先グループの宛先アドレスごとに、当該宛先グループの宛先アドレスへの前記現用リンクおよび前記予備リンクを示した経路表を作成する経路表作成部と、
前記作成した経路表を、前記始点装置である各装置へ送信する出力部とを備えることを特徴とする経路表作成装置。
【請求項５】
前記リンク選択部は、
前記現用経路および予備経路を計算するとき、
前記トポロジ情報を参照して、ホップ数またはリンクコストが最小となる経路を計算することを特徴とする請求項１、請求項２および請求項４のいずれか１項に記載の経路表作成装置。
【請求項６】
前記リンク選択部は、
前記現用経路および予備経路を計算するとき、
前記トポロジ情報を参照して、前記現用経路および予備経路が互いに、同じ装置またはリンクを経由しない経路を選択することを特徴とする請求項１、請求項２および請求項４のいずれか１項に記載の経路表作成装置。
【請求項７】
前記装置選択部は、
前記現用装置を選択するとき、前記トポロジ情報を参照して、当該宛先アドレスへのホップ数またはリンクコストが最小の装置を選択することを特徴とする請求項３に記載の経路表作成装置。
【請求項８】
網内の各装置においてパケットの転送処理に用いられる経路表を作成する経路表作成装置が、
宛先アドレスごとに、当該宛先アドレスの装置またはサブネットワークへ到達可能な装置の識別情報を示した到達性情報と、前記ネットワークを構成する各装置の接続状態および前記各装置を接続するリンクを示したトポロジ情報との入力を受け付け、記憶部に記憶するステップと、
前記到達性情報に示される宛先アドレスごとに、当該宛先アドレスへパケットを転送するエッジノードの装置群の中から、現用装置と予備装置とを選択するステップと、、
前記トポロジ情報に示される装置それぞれについて、当該装置を始点装置としたとき、前記始点装置から前記現用装置への現用経路と、前記始点装置から前記予備装置への予備経路とを計算し、前記トポロジ情報を参照して、前記始点装置が前記現用経路で用いるリンクである現用リンクおよび前記予備経路で用いるリンクである予備リンクを選択するステップと、
前記始点装置それぞれについて、前記宛先アドレスごとに、当該宛先アドレスへの前記現用リンクおよび前記予備リンクを示した経路表を作成するステップと、
前記作成した経路表を、前記始点装置である各装置へ送信するステップとを実行する経路表作成方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１２−５００４５（Ｐ２０１２−５００４５Ａ）
【公開日】平成２４年３月８日（２０１２．３．８）
【国際特許分類】
【出願番号】特願２０１０−１９２９５６（Ｐ２０１０−１９２９５６）
【出願日】平成２２年８月３０日（２０１０．８．３０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年３月８日（２０１２．３．８）
【国際特許分類】
【出願日】平成２２年８月３０日（２０１０．８．３０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]