(57)【特許請求の範囲】
【請求項１】
ＭＰＬＳパスを設定可能な装置と、該ＭＰＬＳパスの経路を決定するパス収容計算装置を有する完全冗長化ネットワークにおいて、該ＭＰＬＳパスを設定可能な入口ノードと出口ノードを結ぶ、正常系パスと異常系迂回パスを設定するためのパス収容計算方法であって、
前記パス収容計算装置において、
正常系パス計算手段が、ノード、リンク接続関係情報、リンクコスト情報、入口ノードと出口ノードの要求帯域情報を格納したトポロジ情報記憶手段を参照して、入口ノードから出口ノードまでの、残余帯域を確保可能で、既に正常系パスが既に確保している帯域の少ない経路の候補で、最小ホップとなる経路で正常系パスの経路を計算し、パス記憶手段に記録する正常系パス計算ステップと、
異常系パス迂回経路計算手段が、前記正常系パス計算ステップで計算された前記正常系パスと対応する異常系迂回パスについて、前記入口ノードから前記出口ノードまでの該正常系パスの通過するノードとリンクと完全に交わらない経路を対象として、前記トポロジ情報記憶手段を参照して、該入口ノードから該出口ノードまでの残余帯域を確保可能な最小ホップ経路で異常系迂回パスの計算を行い、前記パス記憶手段に記録する異常系迂回パス計算ステップと、
前記パス記憶手段に格納された前記正常系パスと前記異常系迂回パスを、前記ＭＰＬＳパスを設定可能な装置に設定するパス設定ステップと、
を行う、
ことを特徴とするパス収容計算方法。
【請求項２】
ＭＰＬＳパスを設定可能な装置と、該ＭＰＬＳパスの経路を決定するパス収容計算装置を有する完全冗長化ネットワークにおいて、該ＭＰＬＳパスを設定可能な入口ノードと出口ノードを結ぶ、正常系パスと異常系迂回パスを設定するためのパス収容計算装置であって、
ノード、リンク接続関係情報、リンクコスト情報、入口ノードと出口ノードの要求帯域情報を格納したトポロジ情報記憶手段と、
前記トポロジ情報記憶手段を参照して、入口ノードから出口ノードまでの、残余帯域を確保可能で、既に正常系パスが既に確保している帯域の少ない経路の候補で、最小ホップとなる経路で正常系パスの経路を計算し、パス記憶手段に記録する正常系パス計算手段と、
前記正常系パス計算手段で計算された前記正常系パスと対応する異常系迂回パスについて、前記入口ノードから前記出口ノードまでの該正常系パスの通過するノードとリンクと完全に交わらない経路を対象として、前記トポロジ情報記憶手段を参照して、該入口ノードから該出口ノードまでの残余帯域を確保可能な最小ホップ経路で異常系迂回パスの計算を行い、前記パス記憶手段に記録する異常系迂回パス計算手段と、
前記パス記憶手段に格納された前記正常系パスと前記異常系迂回パスを、前記ＭＰＬＳパスを設定可能な装置に設定するパス設定手段と、
を有する
ことを特徴とするパス収容計算装置。
【請求項３】
コンピュータに、
請求項２記載のパス収容計算装置の各手段を実行させることを特徴とするパス収容計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パス収容計算装置及びパス収容計算方法及びプログラムに係り、特に、Traffic Engineering (TE) Label Switched Path (LSP)を設定可能なMPLSネットワーク技術における、Point-to-point (P2P)または、Point-to-multipoint (P2MP)TE LSPのソース（Ingress）ノードと宛先(Egress)ノードを結ぶ正常系(Primary)パスと異常系迂回（Detour）パスを設定するためのパス収容計算装置及びパス収容計算方法及びプログラムに関する。
【背景技術】
【０００２】
MPLSネットワーク技術については種々開示されている（例えば、非特許文献１〜３参照）。
【０００３】
また、P2Pまたは、P2MP TE LSPのIngressノードとEgressノードを結ぶ、Primaryパスと、Detourパスを設定するためのパス収容計算技術も提案されている（例えば、非特許文献４参照）。
【非特許文献１】R. Braden, et al., “Resource ReSerVation Protocol (RSVP) Version 1 Functional Specification, “ RFC 2205, Sept. 1997.
【非特許文献２】D. Awduche., L. Berger., D. Gan.,T. Li., V. Srinivasan, G. Swallow, “RSVP-TE: Extensions to RSVP for LSP Tunnels”, RFC3209, December 2001
【非特許文献３】Rosen, E., Viswanathan, A. and R. Callon, “Multiprotocol Label Switching Architecture”, RFC 3031, January 2001.
【非特許文献４】D. Katz. et al, “Traffic Engineering (TE) Extensions to OSPF Version 2”, RFC3630, September 2003
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、完全冗長化ネットワークでは、正常系用のリンクに正常系パスを設定し、異常系用のリンクに異常系迂回パスを設定することを前提にネットワーク設計を行っているが、正常系用のリンク正常系パスを集中配置してしまうと、正常系リンクに障害が発生した時の影響度が大きい。
【０００５】
例えば、上記の非特許文献４を用いて正常系パスと異常系迂回パスを設計した場合、図２８に示すように、片方向（正常系リンク）に正常系パスが集中してしまう。
【０００６】
本発明は、上記の点に鑑みなされたもので、完全冗長化ネットワークでは、正常系または異常系リンクに障害が発生したときの全体のパスへの影響度を軽減させることが可能なパス収容計算装置及びパス収容計算方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
図１は、本発明の原理を説明するための図である。
【０００８】
本発明（請求項１）は、ＭＰＬＳパスを設定可能な装置と、該ＭＰＬＳパスの経路を決定するパス収容計算装置を有する完全冗長化ネットワークにおいて、該ＭＰＬＳパスを設定可能な入口ノードと出口ノードを結ぶ、正常系パスと異常系迂回パスを設定するためのパス収容計算方法であって、
パス収容計算装置において、
正常系パス計算手段が、ノード、リンク接続関係情報、リンクコスト情報、入口ノードと出口ノードの要求帯域情報を格納したトポロジ情報記憶手段を参照して、入口ノードから出口ノードまでの、残余帯域を確保可能で、既に正常系パスが既に確保している帯域の少ない経路の候補で、最小ホップとなる経路で正常系パスの経路を計算し、パス記憶手段に記録する正常系パス計算ステップ（ステップ１）と、
異常系パス迂回経路計算手段が、正常系パス計算ステップで計算された正常系パスと対応する異常系迂回パスについて、入口ノードから出口ノードまでの該正常系パスの通過するノードとリンクと完全に交わらない経路を対象として、トポロジ情報記憶手段を参照して、該入口ノードから該出口ノードまでの残余帯域を確保可能な最小ホップ経路で異常系迂回パスの計算を行い、パス記憶手段に記録する異常系迂回パス計算ステップ（ステップ２）と、
パス記憶手段に格納された正常系パスと異常系迂回パスを、ＭＰＬＳパスを設定可能な装置に設定するパス設定ステップ（ステップ３）と、
を行う。
【０００９】
図２は、本発明の原理構成図である。
【００１０】
本発明（請求項２）は、ＭＰＬＳパスを設定可能な装置と、該ＭＰＬＳパスの経路を決定するパス収容計算装置を有する完全冗長化ネットワークにおいて、該ＭＰＬＳパスを設定可能な入口ノードと出口ノードを結ぶ、正常系パスと異常系迂回パスを設定するためのパス収容計算装置であって、
ノード、リンク接続関係情報、リンクコスト情報、入口ノードと出口ノードの要求帯域情報を格納したトポロジ情報記憶手段１５０と、
トポロジ情報記憶手段１５０を参照して、トポロジ情報記憶手段を参照して、入口ノードから出口ノードまでの、残余帯域を確保可能で、既に正常系パスが既に確保している帯域の少ない経路の候補で、最小ホップとなる経路で正常系パスの経路を計算し、パス記憶手段１７０に記録する正常系パス計算手段１３０と、
正常系パス計算手段１３０で計算された正常系パスと対応する異常系迂回パスについて、入口ノードから出口ノードまでの該正常系パスの通過するノードとリンクと完全に交わらない経路を対象として、トポロジ情報記憶手段を参照して、該入口ノードから該出口ノードまでの残余帯域を確保可能な最小ホップ経路で異常系迂回パスの計算を行い、パス記憶手段１７０に記録する異常系迂回パス計算手段１４０と、
パス記憶手段１７０に格納された正常系パスと異常系迂回パスを、ＭＰＬＳパスを設定可能な装置に設定するパス設定手段１２０と、
を有する。
【００１１】
本発明（請求項３）は、コンピュータに、請求項２記載のパス収容計算装置の各手段を実行させるパス収容計算プログラムである。
【発明の効果】
【００１２】
上記のように本発明によれば、完全冗長化ネットワークにおいて、正常系用リンクと異常系用リンクに正常系パスと異常系迂回パスを分散配置させることが可能となり、正常系または異常系リンクに障害が発生したときの全体のパスへの影響度を軽減させることが可能となる。
【発明を実施するための最良の形態】
【００１３】
以下、図面と共に本発明の実施の形態を説明する。
【００１４】
図３は、本発明の一実施の形態におけるパス収容計算装置の構成を示す。
【００１５】
同図に示すパス収容計算装置１００は、入力部１１０、パス収容計算制御部１２０、正常系パス経路計算部１３０、異常系迂回パス経路計算部１４０、トポロジ情報ＤＢ（データベース）１５０、出力部１６０、パス情報ＤＢ（データベース）１７０から構成され、ルータコンフィグ変換部２００に接続されている。
【００１６】
入力部１１０は、ノード、リンク接続関係情報、リンクコスト情報、入口（ソース）ノードと出口（宛先）ノードの要求帯域情報等のトポロジ情報を入力し、トポロジ情報ＤＢ１５０に格納する。また、要求ＬＳＰ情報、入口ノード情報、出口ノード情報を入力し、パス収容計算制御部１２０に転送する。
【００１７】
パス収容計算制御部１２０は、正常系パス経路計算部１３０、異常系迂回パス経路計算部１４０に対して、正常系パス経路計算、異常系迂回パス経路計算を指示すると共に、正常系パス経路計算部１３０、異常系迂回パス経路計算部１４０の計算結果である経路をパス情報ＤＢ１７０から取得し、出力部１６０に送出する。また、既にＭＰＬＳパスを設定可能な装置（ルータ）に正常系パスが設定されている場合に、再度正常系パス経路計算部１３０に対して、残余帯域を確保可能で、既に正常系パスが既に確保している帯域の少ない経路で、最小ホップとなる経路で正常系パスの経路計算を正常系パス経路計算部１３０に指示する。
【００１８】
正常系パス計算部１３０は、トポロジ情報ＤＢ１５０を参照して、入口ノードから出口ノードまでの残余帯域を取得し、当該残余帯域を確保可能な最小ホップ経路で正常系パスを計算し、パス情報ＤＢ１７０に格納する。
【００１９】
異常系パス計算部１４０は、正常系パス計算部１３０で正常系パスが計算された後、計算された当該正常系パスと対応する異常系迂回系パスを計算する。このとき、入口ノードから出口ノードまでの正常系パスの通過するノード・リンクと完全に交わらない経路をパス情報ＤＢ１７０を参照して抽出し、抽出された当該経路を対象として、トポロジ情報ＤＢ１５０を参照して、入口ノードから出口ノードまでの残余帯域を確保可能な最小ホップ経路で異常系迂回パスの経路を計算し、パス情報ＤＢ１７０に格納する。
【００２０】
出力部１６０は、パス収容計算制御部１２０から正常系パス、異常系パスをパス情報ＤＢ１７０に格納または、ルータコンフィグ変換部２００に出力する。
【００２１】
ルータコンフィグ変換部２００は、出力部１６０からの情報または、出力情報ＤＢ１７０の情報をルータコンフィグに変換し、ＭＰＬＳパスを設定可能な装置（ルータ）に設定する。
【００２２】
図４は、本発明の一実施の形態におけるパス収容計算装置における動作のフローチャートである。以下では、予め、ノード、リンク接続関係情報、リンクコスト情報、入口ノードと出口ノードの要求帯域情報がトポロジ情報ＤＢ１５０に格納されているものとする。
【００２３】
ステップ１０１）  まず、パス収容計算制御部１２０において、要求ＬＳＰ情報、入り口ノード情報、出口ノード情報が入力されると、正常系パス経路計算部１３０に対して正常系パス経路の計算を指示する。これにより正常系パス経路計算部１３０は、トポロジ情報ＤＢ１５０を参照して、入口ノードから出口ノードまでの残余帯域を確保可能な最小ホップ経路で正常系パス経路を計算する。正常系パス経路の求め方については後述する。
計算された正常系パス経路をパス情報ＤＢ１７０に格納する。
【００２４】
ステップ１０２）  正常系パス経路計算部１３０は、求められた正常系パスの経路をパス情報ＤＢ１７０に格納する。
【００２５】
ステップ１０３）  異常系パス迂回経路計算部１４０は、パス情報ＤＢ１７０を参照して、入口ノードから出口ノードまでの正常系パスの通過するノード・リンクと完全に交わらない経路を抽出する。
【００２６】
ステップ１０４）  異常系パス迂回経路計算部１４０は、抽出された経路を対象に、トポロジ情報ＤＢ１５０を参照して、入口ノードから出口ノードまでの残余帯域を確保可能な最小ホップ経路で異常系迂回パスの経路を計算する。
【００２７】
ステップ１０５）  異常系パス迂回経路計算部１４０は、求められた異常系迂回パスをパス情報ＤＢに格納する。
【００２８】
ステップ１０６）  パス収容計算制御部１２０は、パス情報ＤＢ１７０から、正常系パスと異常系迂回パスを読み出して、出力部１６０を介してルータコンフィグ変換部２００に渡す。これにより、ルータコンフィグ変換部２００は、当該情報をルータに適合する形に変換し、ＭＰＬＳパスが設定可能なルータに設定する。
【００２９】
以下に具体的に説明する。
【００３０】
図５は、本発明の一実施の形態におけるネットワーク構成図である。以下に示す図中の、Ａ〜Ｒはノードを表す。
【００３１】
以下では、正常系と異常系の２つの面を備えた完全二重化ネットワークでの設計を想定し、以下に示すようなネットワーク構成とした。
【００３２】
正常系のパス用のリンクを、
Ａ−Ｇ，Ｇ−Ｍ，Ｍ−Ｎ，Ｎ−Ｏ，Ｎ−Ｉ，Ｉ−Ｃ，Ｏ−Ｋ，Ｋ−Ｅ
として、リンクコストを３とし、
異常系パス用のリンクを、
Ｂ−Ｈ，Ｈ−Ｐ，Ｐ−Ｑ，Ｑ−Ｒ，Ｑ−Ｊ，Ｊ−Ｄ，Ｒ−Ｌ，Ｌ−Ｆ
として、リンクコストを１０とし、また、正常系パス用のリンクと異常系迂回パス用のリンクとの渡りリンクを、
Ｐ−Ｍ，Ｑ−Ｎ，Ｒ−Ｏ，Ｇ−Ｈ，Ｉ−Ｊ，Ｋ−Ｌ
として、リンクコストを１００とした。
【００３３】
リンクのパス設定可能帯域はそれぞれ１００Ｍbpsとした。
【００３４】
なお、これらの設定については、入力部１１０から入力され、トポロジ情報ＤＢ１５０に格納されているものとする。
【００３５】
図６〜図１９を参照して、上記の図５のネットワークにおけるパス収容方式の動作説明を行う。
【００３６】
ここでは、背景パス情報として、ネットワーク上には既に設定されたパスは存在しないものとし、その状態でノードＡからノードＣに対して、３０Ｍｂｐｓの正常系パス、３０Ｍｂｐｓの異常系迂回パスを設定するときの動作を説明する。
【００３７】
以下では、トポロジ情報ＤＢ１５０からリンク接続関係情報を読み出してメモリ（図示せず）上にリンク候補の一覧を作成しておくものとする。
【００３８】
図６は、本発明の一実施の形態における正常系パス設計動作（手順１）を示す。
【００３９】
手順１において、正常系パス経路計算部１３０では、ノードＡから１ホップで到達するノードへのリンク候補の一覧を探索する。ここで、要求パスの帯域が３０Ｍｂｐｓなので、リンク候補はこの要求パス帯域を設定可能な分だけの残余帯域を備えるものをトポロジ情報ＤＢ１５０を参照してとしてメモリ（図示せず）に記録する。これにより、Ａ〜Ｇ、Ａ〜Ｈへのリンクが候補となるが、ノードＧ，Ｈへのリンクの候補がこれらの他に存在しないため、Ａ〜Ｇ、Ａ〜Ｈへのリンクが確定する。ここで、Ａ〜Ｇ、Ａ〜Ｈへの経路上の各リンクで正常系のパスが確保している帯域で最大の帯域が設定されている数値を当該リンクと共にメモリ（図示せず）に記憶しておく。ここでは、Ａ〜Ｇへの経路中の正常系パスの予約されているリンクの中で最大帯域となっているのは０Ｍｂｐｓ、Ａ〜Ｈへの経路中の正常系パスの予約されているリンクの中で最大帯域となっているのは０Ｍｂｐｓとなる。この場合、背景として設定されているパスが存在しないため、以降の経路確定ステップでも同様に０Ｍｂｐｓとなるため、以下のＡ〜Ｃへのパスが決定される手順における本手順の説明は省略する。
【００４０】
図７は、本発明の一実施の形態における正常系パス設計動作（手順２）を示す。
【００４１】
手順２において、正常系パス計算部１３０は、ノードＡから２ホップで到達するノードへのリンク候補の一覧を探索する。ここで、要求パスの帯域が３０Ｍｂｐｓなので、リンク候補に対し、この要求パス帯域を設定可能な分だけの残余帯域を備えるものを、トポロジ情報ＤＢ１５０を参照してメモリ（図示せず）に記録する。これにより、Ａ〜Ｇ〜Ｈ，Ａ〜Ｈ〜Ｇ、Ａ〜Ｇ〜Ｂ，Ａ〜Ｇ〜Ｍ、Ａ〜Ｈ〜Ｐへのリンクが候補となるが、ノードＢ，Ｍ，Ｐへのリンクの候補がこれらの他に存在しないため、Ａ〜Ｇ〜Ｂ，Ａ〜Ｇ〜Ｍ，Ａ〜Ｈ〜Ｐへのリンクが確定し、メモリ（図示せず）に格納する。Ａ〜Ｇ〜Ｈ、Ａ〜Ｈ〜Ｇは、既にノードＧ、Ｈへのリンク候補が手順１で確定しているため候補から削除される。
【００４２】
図８は、本発明の一実施の形態における正常系パス設計動作（手順３）を示す。
【００４３】
手順３において、正常系パス経路計算部１３０は、ノードＡから３ホップで到達するノードへリンク候補の一覧を探索する。ここで、要求パスの帯域が３０Ｍｂｐｓなので、リンク候補に対し、この要求パス帯域を設定可能な分だけの残余帯域を備えるものをとしてメモリ（図示せず）に記録する。これにより、Ａ〜Ｇ〜Ｍ〜Ｎ、Ａ〜Ｇ〜Ｍ〜Ｐ，Ａ〜Ｈ〜Ｐ〜Ｑへのリンクが候補となるが、ノードＮ、Ｑへのリンクの候補がこれらの他に存在しないため、Ａ〜Ｇ〜Ｍ〜Ｎ、Ａ〜Ｈ〜Ｐ〜Ｑへのリンクが確定し、メモリ（図示せず）に格納する。Ａ〜Ｇ〜Ｍ〜Ｐは、既にＰへのリンク候補が手順２で確定しているため候補から削除される。
【００４４】
図９は、本発明の一実施の形態における正常系パス設計動作（手順４）を示す。
【００４５】
手順４において、上記の手順３と同様の手順により、Ａ〜Ｇ〜Ｍ〜Ｎ〜Ｉ、Ａ〜Ｈ〜Ｐ〜Ｑ〜Ｊ、Ａ〜Ｇ〜Ｍ〜Ｎ〜Ｏ，Ａ〜Ｈ〜Ｐ〜Ｑ〜Ｒへリンクが確定し、メモリ（図示せず）に格納する。
【００４６】
図１０は、本発明の一実施の形態における正常系パス設計動作（手順５）を示す。
【００４７】
手順５において、正常系パス経路計算部１３０は、ノードＡから５ホップで到達するノードへのリンク候補一覧を探索する。ここで要求パスの帯域が３０Ｍｂｐｓなので、リンク候補はこの要求パス帯域を設定可能な分だけ残余帯域を備えるものを候補としてメモリ（図示せず）に記録する。これにより、Ａ〜Ｇ〜Ｍ〜Ｎ〜Ｉ〜Ｃ、Ａ〜Ｇ〜Ｍ〜Ｎ〜Ｉ〜Ｄ、Ａ〜Ｈ〜Ｐ〜Ｑ〜Ｊ〜Ｃ、Ａ〜Ｈ〜Ｐ〜Ｑ〜Ｊ〜Ｄ、Ａ〜Ｇ〜Ｍ〜Ｎ〜Ｏ〜Ｋ、Ａ〜Ｇ〜Ｍ〜Ｎ〜Ｏ〜Ｒ，Ａ〜Ｈ〜Ｐ〜Ｑ〜Ｒ〜Ｌ、Ａ〜Ｈ〜Ｐ〜Ｑ〜Ｒ〜Ｏへのリンクが候補となるが、ノードＫ、Ｌへのリンクの候補がこれらの他に存在しないため、Ａ〜Ｇ〜Ｍ〜Ｎ〜Ｏ〜Ｋ、Ａ〜Ｈ〜Ｐ〜Ｑ〜Ｒ〜Ｌへのリンクが確定し、メモリ（図示せず）に格納する。Ａ〜Ｇ〜Ｍ〜Ｎ〜Ｏ〜Ｒ、Ａ〜Ｈ〜Ｐ〜ｑ〜Ｒ〜Ｏは、既にＲ，Ｏへのリンク候補が手順４で確定しているため候補から削除される。
【００４８】
また、ノードＣへの候補とノードＤへの候補が、Ａ〜Ｇ〜Ｍ〜Ｎ〜Ｉ〜Ｃ、Ａ〜Ｈ〜Ｐ〜Ｑ〜Ｊ〜ＣとＡ〜Ｇ〜Ｍ〜Ｎ〜Ｉ〜Ｄ、Ａ〜Ｈ〜Ｐ〜Ｑ〜Ｊ〜Ｄのそれぞれ２候補ずつ存在しているが、この場合は、ソースノードから宛先ノードへのリンクコストの総数が小さい経路を選択する。これにより、ノードＣへの経路としてＡ〜Ｇ〜Ｍ〜Ｎ〜Ｉ〜Ｃが、ノードＤへの経路としてＡ〜Ｇ〜Ｍ〜Ｎ〜Ｉ〜Ｄが確定する。
【００４９】
図１１は、本発明の一実施の形態における正常系パス設計動作（手順６）を示す。
【００５０】
ここでは、宛先Ｃへの経路が決定したため、ここで、手順を終了する。
【００５１】
図１２は、本発明の一実施の形態における正常系パス設計動作（手順７）を示す。
【００５２】
正常系パス経路計算部１３０は、ソースノードＡから宛先ノードＣの経路が確定したため、他の不要な確定候補を削除する。
【００５３】
ノードＣへの経路として、Ａ〜Ｇ〜Ｍ〜Ｎ〜Ｉ〜Ｃが決定し、正常系パス経路計算部１３０はこれを正常系パスとしてパス情報ＤＢ１７０に格納する。これにより、パス収容計算制御部１２０は当該パスを正常系パスとして設定する。
【００５４】
パス収容計算制御部１２０は、正常系パスとして設定されたら、その経路を通るリンクＡ〜Ｇ，Ｇ〜Ｍ、Ｍ〜Ｎ、Ｎ〜Ｉ、Ｉ〜Ｃに対して正常系パス予約帯域をパス情報ＤＢ１７０に格納する。ここでは、３０Ｍｂｐｓの正常系パスが設定されたので、各リンクに３０Ｍｂｐｓを予約帯域としてパス情報ＤＢ１７０に記憶する。
【００５５】
また、上記の各リンクに帯域が３０Ｍｂｐｓ予約されたので、各リンクのパス設定可能な残余帯域は、１００−３０＝７０Ｍｂｐｓとなり、これをパス情報ＤＢ１７０に格納する。
【００５６】
次に、上記の正常系パスに対する異常系迂回パスの計算について説明する。
【００５７】
図１３は、本発明の一実施の形態における異常系迂回パス設計動作（手順１）を示す。
【００５８】
手順１において、異常系パス迂回経路計算部１４０は、パス情報ＤＢ１７０を参照して、上記の正常系パス設計においてメモリ（図示せず）に格納されている上記正常系パスとして決定された経路Ａ〜Ｇ〜Ｍ〜Ｎ〜Ｉ〜Ｃを、異常系迂回パス設計における経路候補から削除する。
【００５９】
図１４は、本発明の一実施の形態における異常系迂回パス設計動作（手順２）を示す。
【００６０】
手順２において、異常系パス迂回経路計算部１４０は、ノードＡから１ホップで到達するノードへのリンク候補の一覧を探索する。ここで、要求パスの帯域が３０Ｍｂｐｓなので、リンク候補はこの要求帯域を設定可能な分だけ残余帯域を備えるものを候補とする。これにより、Ａ〜Ｈへのリンクが候補となるが、ノードＨへのリンクの候補がこれらの他に存在しないため、Ａ〜Ｈへのリンクが確定する。
【００６１】
図１５〜図２０は、本発明の一実施の形態における正常系パスに対する異常系迂回パスの設計における動作を示す。
【００６２】
異常系パス迂回経路計算部１４０において、上記の正常系パスの経路決定処理と同様の手法により、Ａ〜Ｈ〜Ｐ〜Ｑ〜Ｊ〜Ｄへのリンクを確定する。これをノードＡからノードＣへの異常系迂回経路としてパス情報ＤＢ１７０に格納する。
【００６３】
パス収容計算制御部１２０は、異常系パス迂回経路計算部１４０において、異常系迂回パスとして確定されたら、その経路を通るリンクＡ〜Ｈ、Ｈ〜Ｐ、Ｐ〜Ｑ、Ｑ〜Ｊ、Ｊ〜Ｄに対して正常系パス予約帯域をパス情報ＤＢ１７０に格納する。ここでは、３０Ｍｂｐｓの異常系迂回パスが設定されたので、その経路を通る各リンクＡ〜Ｈ、Ｈ〜Ｐ、Ｐ〜Ｑ，Ｑ〜Ｊ、Ｊ〜Ｄに対して帯域が３０Ｍｂｐｓ予約されたので、各リンクのパス設定可能な残余帯域は１００−３０＝７０Ｍｂｐｓとなり、これをパス情報ＤＢ１７０に格納する。
【００６４】
次に、上記のステップよって設定されたノードＡからノードＣへの正常系パスと異常系迂回パスの状態について説明する。
【００６５】
図２１は、本発明の一実施の形態における設定されたパスを示し、図２２、図２３は、本発明の一実施の形態における正常系パスと異常系迂回パスの状態を示す。また、図２４は、本発明の一実施の形態における正常系パスと異常系迂回パスの設定例である。
【００６６】
ここで、図２４を参照して、背景パス情報として、ネットワーク上に既にノードＡからノードＣへの正常系パスと異常系迂回パスが設定されている状態で、ノードＢからノードＦに対して３０Ｍｂｐｓの正常系パス、３０Ｍｂｐｓの異常系迂回パスを設計する時の動作を説明する。
【００６７】
まず、正常系パス経路計算部１３０は、手順１として、ノードＢから１ホップで到達するノードへのリンク候補の一覧を探索する。ここで、要求パスの帯域が３０Ｍｂｐｓなので、リンク候補はこの要求パス帯域を設定可能な分だけ残余帯域を備えるものを候補とする。これにより、ノードＢ〜Ｇ、Ｂ〜Ｈへのリンクが候補となるが、ノードＧ、Ｈへのリンクの候補がこれらの他に存在しないため、Ａ〜Ｇ、Ａ〜Ｈへのリンクが確定する。ここで、Ａ〜Ｇ、Ａ〜Ｈへの経路上の各リンクで正常系のパスが確保している帯域で最大の帯域が設定されている数値をメモリ（図示せず）に記憶しておく。ここでは、Ａ〜Ｇへの経路中の正常系パスの予約されているリンクの中で最大帯域となっているのは０Ｍｂｐｓ、リンクＡ〜Ｈへの経路中の正常系パスの予約されているリンクの中で最大帯域となっているのは０Ｍｂｐｓとなる。
【００６８】
次に、正常系パス経路計算部１３０は、手順２において、Ａから２ホップで到達するノードへのリンク候補の一覧を探索する。ここで、要求パスの帯域が３０Ｍｂｐｓなので、リンク候補はこの要求パス帯域を設定可能な分だけの残余帯域を備えるものを候補とする。これにより、Ｂ〜Ｇ〜Ｈ、Ｂ〜Ｈ〜Ｇ、Ｂ〜Ｇ〜Ａ，Ｂ〜Ｇ〜Ｍ、Ｂ〜Ｈ〜Ｐへのリンクが候補となるが、ノードＡ，Ｍ，Ｐへのリンクの候補がこれらの他に存在しないため、Ｂ〜Ｇ〜Ａ、Ｂ〜Ｇ〜Ｍ、Ｂ〜Ｈ〜Ｐへのリンクが確定する。Ｂ〜Ｇ〜Ｈ、Ｂ〜Ｈ〜Ｇは、既にＧ、Ｈへのリンク候補が手順１で確定しているため候補から削除される。ここで、Ｂ〜Ｇ〜Ａ、Ｂ〜Ｇ〜Ｍ、Ｂ〜Ｈ〜Ｐへの経路上の各リンクで正常系のパスが確保している帯域で最大の帯域が設定されている数値をメモリ（図示せず）に記憶しておく。ここでは、Ｂ〜Ｇ〜Ａへの経路中の正常系パスの予約されているリンクの中で最大帯域となっているのは０Ｍｐｂｓ、Ｂ〜Ｇ〜Ｍへの経路中の正常系パスの予約されているリンクの中で最大帯域となっているのは、リンクＧ〜Ｍ間で３０Ｍｂｐｓ、Ｂ〜Ｇ〜Ｐへの経路の正常系パスの予約されているリンクの中で最大帯域となっているのは０Ｍｂｐｓとなる。
【００６９】
同様に、手順を進めることによって、Ｂ〜Ｇ〜Ｍ〜Ｎ〜Ｏ〜Ｋ、Ｂ〜Ｈ〜Ｐ〜Ｑ〜Ｒ〜Ｌへのリンクが確定する。ここで、Ｂ〜Ｇ〜Ｍ〜Ｎ〜Ｏ〜Ｋへの経路中の正常系パスの予約されているリンクの中で、最大帯域となっているのは、リンクＧ〜Ｍ、Ｍ〜Ｎ間で３０Ｍｂｐｓ、Ｂ〜Ｈ〜Ｐ〜Ｑ〜Ｒ〜Ｌへの経路中の正常系パスの予約されているリンクの中で最大帯域となっているのは０Ｍｂｐｓとなる。
【００７０】
正常系パス経路計算部１３０は、次の手順で、ノードＢからＦに到達するノードへのリンク候補が、Ｂ〜Ｇ〜Ｍ〜Ｎ〜Ｏ〜Ｋ〜Ｆと、Ｂ〜Ｈ〜Ｐ〜Ｑ〜Ｒ〜Ｌ〜Ｆの２経路が確定するが、この場合は、まず、Ｂ〜Ｇ〜Ｍ〜Ｎ〜Ｏ〜Ｋ〜ＦとＢ〜Ｈ〜Ｐ〜Ｑ〜Ｒ〜Ｌ〜Ｆを比較して、経路中の正常系パスの予約されているリンクの中で最大帯域となっている位置が小さい経路を選択する。この場合、Ｂ〜Ｇ〜Ｍ〜Ｎ〜Ｏ〜Ｋ〜Ｆへの経路中の正常系パスの予約されているリンクの中で最大帯域となっているのは、リンクＧ〜Ｍ、Ｍ〜Ｎ間で３０Ｍｂｐｓ、Ｂ〜Ｈ〜Ｐ〜Ｑ〜Ｒ〜Ｌ〜Ｆへの経路中の正常系パスの予約されているリンクの中で最大帯域となっているのは０Ｍｂｐｓとなっているので、値の小さいＢ〜Ｈ〜Ｐ〜Ｑ〜Ｒ〜Ｌ〜Ｆの経路が確定する。もし仮に、この帯域の値が同一値だった場合には、ソースノードから宛先ノードへのリンクコストの総数が小さい経路を選択する。
【００７１】
以下、異常系迂回パス経路計算部１４０においても、上記と同様の手順で、異常系迂回パスを決定する。その例を図２５に示す。
【００７２】
図２６は、ノードＤからＥへの正常系パスを設定した場合の経路であり、当該経路がパス情報ＤＢ１７０に格納される。
【００７３】
図２７は、ノードＤからＥへの異常系迂回パスを設定した場合の経路であり、当該経路がパス情報ＤＢ１７０に格納される。
【００７４】
なお、本発明は、上記のパス収容計算装置の動作をプログラムとして構築し、パス収容計算装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００７５】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００７６】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００７７】
本発明は、完全冗長化ネットワークにおけるパス収容計算技術に適用可能である。
【図面の簡単な説明】
【００７８】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態におけるパス収容装置の構成図である。
【図４】本発明の一実施の形態におけるパス収容計算装置における動作のフローチャートである。
【図５】本発明の一実施の形態におけるネットワーク構成図である。
【図６】本発明の一実施の形態における正常系パス設計動作（手順１）を示す図である。
【図７】本発明の一実施の形態における正常系パス設計動作（手順２）を示す図である。
【図８】本発明の一実施の形態における正常系パス設計動作（手順３）を示す図である。
【図９】本発明の一実施の形態における正常系パス設計動作（手順４）を示す図である。
【図１０】本発明の一実施の形態における正常系パス設計動作（手順５）を示す図である。
【図１１】本発明の一実施の形態における正常系パス設計動作（手順６）を示す図である。
【図１２】本発明の一実施の形態における正常系パス設計動作（確定）を示す図である。
【図１３】本発明の一実施の形態における異常系迂回パス設計動作（手順１）を示す図である。
【図１４】本発明の一実施の形態における異常系迂回パス設計動作（手順２）を示す図である。
【図１５】本発明の一実施の形態における異常系迂回パス設計動作（手順３）を示す図である。
【図１６】本発明の一実施の形態における異常系迂回パス設計動作（手順４）を示す図である。
【図１７】本発明の一実施の形態における異常系迂回パス設計動作（手順５）を示す図である。
【図１８】本発明の一実施の形態における異常系迂回パス設計動作（手順６）を示す図である。
【図１９】本発明の一実施の形態における異常系迂回パス設計動作（手順７）を示す図である。
【図２０】本発明の一実施の形態における異常系迂回パス設計動作（確定）を示す図である。
【図２１】本発明の一実施の形態における設定されたパスを示す図である。
【図２２】本発明の一実施の形態におけるＡ〜Ｃの正常系パスと異常系迂回パスの状態を示す図（その１）である。
【図２３】本発明の一実施の形態におけるＡ〜Ｃの正常系パスと異常系迂回パスの状態を示す図（その２）である。
【図２４】本発明の一実施の形態における正常系パスと異常系迂回パスの設定例である。
【図２５】本発明の一実施の形態における決定した異常系迂回パスの例である。
【図２６】本発明の一実施の形態におけるＤからＥへの正常系パスを設定した例である。
【図２７】本発明の一実施の形態におけるＤからＥへの異常系迂回パスを設定した例である。
【図２８】従来の経路計算結果の例である。
【符号の説明】
【００７９】
１００  パス収容計算装置
１１０  入力部
１２０  パス設定手段、パス収容計算制御部
１３０  正常系パス計算手段、正常系パス経路計算部
１４０  異常系パス迂回経路計算手段、異常系パス迂回経路計算部
１５０  トポロジ情報記憶手段、トポロジ情報ＤＢ
１６０  出力部
１７０  パス記憶手段、パス情報ＤＢ
２００  ルータコンフィグ変換部
【図１】
0004509969.tif 000002
【図２】
0004509969.tif 000003
【図３】
0004509969.tif 000004
【図４】
0004509969.tif 000005
【図５】
0004509969.tif 000006
【図６】
0004509969.tif 000007
【図７】
0004509969.tif 000008
【図８】
0004509969.tif 000009
【図９】
0004509969.tif 000010
【図１０】
0004509969.tif 000011
【図１１】
0004509969.tif 000012
【図１２】
0004509969.tif 000013
【図１３】
0004509969.tif 000014
【図１４】
0004509969.tif 000015
【図１５】
0004509969.tif 000016
【図１６】
0004509969.tif 000017
【図１７】
0004509969.tif 000018
【図１８】
0004509969.tif 000019
【図１９】
0004509969.tif 000020
【図２０】
0004509969.tif 000021
【図２１】
0004509969.tif 000022
【図２２】
0004509969.tif 000023
【図２３】
0004509969.tif 000024
【図２４】
0004509969.tif 000025
【図２５】
0004509969.tif 000026
【図２６】
0004509969.tif 000027
【図２７】
0004509969.tif 000028
【図２８】
0004509969.tif 000029