(57)【特許請求の範囲】
【請求項１】
MPLSパスを設定可能な装置と該MPLSパスの経路を設定するパス収容計算装置を有するネットワークにおいて、入口ノードと宛先ノードを結ぶプライマリパスと迂回パスを設定するためのパス収容計算方法であって、
前記パス収容計算装置において、
同時に経路を設定する入口ノードと宛先ノードの組み合わせが複数存在する場合に、接続関係情報やリンクコスト情報を格納したデータベースを参照して、該入口ノードから該宛先ノードまでの残余帯域を確保可能な最短経路で全ての組み合わせのプライマリパスを計算するプライマリパス計算ステップと、
前記プライマリパス計算ステップで計算された前記プライマリパスを、前記MPLSパスを設定可能な装置に設定するプライマリパス設定ステップと、
前記プライマリパスの設定後に、前記プライマリパスの通過するリンクと完全に交わらない経路を対象として、前記データベースを参照して、前記入口ノードから前記宛先ノードまでの残余帯域を確保可能な最短経路で迂回パスを計算する迂回パス計算ステップと、
前記迂回パス計算ステップで計算された前記迂回パスを、前記MPLSパスを設定可能な装置に設定する迂回パス設定ステップと、
を行うことを特徴とするパス収容計算方法。
【請求項２】
MPLSパスを設定可能な装置とネットワークを介して接続され、入口ノードと宛先ノードを結ぶプライマリパスと迂回パスを設定するためのパス収容計算装置であって、
接続関係情報やリンクコスト情報を格納したデータベースと、
同時に経路を設定する入口ノードと宛先ノードの組み合わせが複数存在する場合に、前記データベースを参照して、該入口ノードから該宛先ノードまでの残余帯域を確保可能な最短経路で全ての組み合わせのプライマリパスを計算するプライマリパス計算手段と、
前記プライマリパス計算手段で計算された前記プライマリパスを、前記MPLSパスを設定可能な装置に設定するプライマリパス設定手段と、
前記プライマリパスの設定後に、前記プライマリパスの通過するリンクと完全に交わらない経路を対象として、前記データベースを参照して、前記入口ノードから前記宛先ノードまでの残余帯域を確保可能な最短経路で迂回パスを計算する迂回パス計算手段と、
前記迂回パス計算手段で計算された前記迂回パスを、前記MPLSパスを設定可能な装置に設定する迂回パス設定手段と、
を有することを特徴とするパス収容計算装置。
【請求項３】
コンピュータを、
請求項２記載のパス収容計算装置として機能させることを特徴とするパス収容計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パス収容計算装置及びパス収容計算方法及びプログラムに係り、特に、Traffic Engineering (TE) Label Switched Path (LSP)を設定可能なMulti Protocol Label Switching(MPLS)ネットワーク技術における、P2P(Point to Point) TE LSPのソース（Ingress）ノードと宛先(Egress)ノードを結ぶプライマリ(Primary)パスと迂回(Detour)パスを設定するためのパス収容計算装置及びパス収容計算方法及びプログラムに関する。
【背景技術】
【０００２】
従来のTE LSPを設定可能なMPLSネットワーク技術において、P2P TE LSPの入口ノードと宛先ノードを結ぶプライマリ（Primary）パスと迂回（Detour）パスを設定するための技術としてOSPF-TE(Open Shortest Path First Traffic engineering)がある（例えば、非特許文献１〜５参照）。
【０００３】
図２７から図３５に従来のOSPF-TEの動作を示す。
【０００４】
従来のOSPF-TEは、それぞれの要求に応じて、ＡからＢへのPrimary LSP、ＡからＢへのDetour LSP、ＡからＤへのPrimary LSP、ＡからＤへのDetour LSP、ＩからＢへのPrimary LSP、ＩからＢへのDetour LSP、ＩからDへのPrimary ＬＳＰ、ＩからＤへのDetour LSP、と順にＬＳＰを設定するものとする。
【０００５】
以下では、全てのリンクのTE予約可能帯域を１００Ｍとし、以下では、ＡからＢ、ＡからＤ，ＩからＢ、ＩからＤへそれぞれ順番に３０ＭのPrimary/Detour LSPを設定するものとする。
【０００６】
図２７では、ＡからＢへのPrimary LSP設定手順を示している。OSPF-TEアルゴリズムの計算に従い、Ａ−Ｈ−Ｇ−Ｆ−Ｂの経路が計算され、そのコストは３．５となる。
【０００７】
図２８では、ＡからＢへのDetour LSP設定手順を示している。まず有向グラフからＡ〜Ｂ間のプライマリパスの通る経路を除いたグラフを作成し、OSPF-TEアルゴリズムの計算に従い、Ａ−Ｉ−Ｅ−Ｃ−Ｂの経路が計算される。
【０００８】
図２９では、Ａ〜ＤへのPrimary LSP設定手順を示す。OSPF-TEアルゴリズムの計算に従い、Ａ−Ｈ−Ｅ−Ｅの経路が計算され、そのコストは３．５となる。
【０００９】
図３０では、ＡからＤへのDetour LSP設定手順を示す。まず、有向グラフからＡ〜Ｄ間のプライマリパスの通る経路を除いたグラフを作成し、OSPF-TEアルゴリズムの計算に従い、Ａ−Ｉ−Ｅ−Ｃ−Ｄの経路が計算される。
【００１０】
図３１では、ＩからＢへのPrimary LSP設定手順を示す。OSPF-TEアルゴリズムの計算に従い、Ｉ−Ｅ−Ｆ−Ｂの経路が計算され、そのコストは３となる。
【００１１】
図３２では、ＩからＢへのDetour LSP設定手順を示す。まず、有向グラフからＩ〜Ｂ間のプライマリパスの通る経路を除いたグラフを作成し、OSPF-TEアルゴリズムの計算に従い、Ｉ−Ａ−Ｈ−Ｅ−Ｃ−Ｂの経路が計算される。
【００１２】
図３３では、ＩからＤへのPrimary LSP設定手順を示す。OSPF-TEアルゴリズムの計算に従い、Ｉ−Ｈ−Ｅ−Ｄの経路が計算され、コストは５．５となる。
【００１３】
図３４では、ＩからＤへのDetour LSP設定手順を示す。まず、有向グラフからＩ〜Ｄ間のプライマリパスの通る経路を除いたグラフを作成し、OSPF-TEアルゴリズムの計算に従い、Ｉ−Ａ−Ｂ−Ｃ−Ｄの経路が計算される。
【非特許文献１】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 Version2”, RFC3630, September 2003
【非特許文献５】M. Takagi, K. Mochizuki, K. Takahashi, M. Shimizu, S. Yasukawa, “P2P and P2MP TE LSPs packing algorithms for MPLS networks”, APSITT2005, IEICE, C-6-4, November 2005.
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかしながら、上記の手法では、ネットワークオペレータが任意の入口ノード群と宛先ノード群に対してPrimary LSPと同帯域のバックアップLSP（Primary/Detour Path）をフルメッシュで設計する際に、図３５に示すように、従来のOSPF-TEによる経路計算の場合、迂回パスによってプライマリパスの通過すべき最短経路が確保できなくなることが懸念される。
【００１５】
本発明は、上記の点に鑑みなされたもので、プライマリパスの最短経路を確保できるパス収容計算装置及びパス収容計算方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１６】
図１は、本発明の原理を説明するための図である。
【００１７】
本発明（請求項１）は、MPLSパスを設定可能な装置と該MPLSパスの経路を設定するパス収容計算装置を有するネットワークにおいて、入口ノードと宛先ノードを結ぶプライマリパスと迂回パスを設定するためのパス収容計算方法であって、
パス収容計算装置において、
同時に経路を設定する入口ノードと宛先ノードの組み合わせが複数存在する場合に、接続関係情報やリンクコスト情報を格納したデータベースを参照して、該入口ノードから該宛先ノードまでの残余帯域を確保可能な最短経路で全ての組み合わせのプライマリパスを計算するプライマリパス計算ステップ（ステップ１）と、
プライマリパス計算ステップ（ステップ１）で計算されたプライマリパスを、MPLSパスを設定可能な装置に設定するプライマリパス設定ステップ（ステップ２）と、
プライマリパスの設定後に、プライマリパスの通過するリンクと完全に交わらない経路を対象として、データベースを参照して、入口ノードから宛先ノードまでの残余帯域を確保可能な最短経路で迂回パスを計算する迂回パス計算ステップ（ステップ３）と、
迂回パス計算ステップで計算された迂回パスを、MPLSパスを設定可能な装置に設定する迂回パス設定ステップ（ステップ４）と、を行う。
【００１９】
図２は、本発明の原理構成図である。
【００２０】
本発明（請求項２）は、MPLSパスを設定可能な装置とネットワークを介して接続され、入口ノードと宛先ノードを結ぶプライマリパスと迂回パスを設定するためのパス収容計算装置であって、
接続関係情報やリンクコスト情報を格納したデータベース１２０と、
同時に経路を設定する入口ノードと宛先ノードの組み合わせが複数存在する場合に、データベース１２０を参照して、該入口ノードから該宛先ノードまでの残余帯域を確保可能な最短経路で全ての組み合わせのプライマリパスを計算するプライマリパス計算手段１５１と、
プライマリパス計算手段１５１で計算されたプライマリパスを、MPLSパスを設定可能な装置に設定するプライマリパス設定手段１１０−１と、
プライマリパスの設定後に、プライマリパスの通過するリンクと完全に交わらない経路を対象として、データベース１２０を参照して、入口ノードから宛先ノードまでの残余帯域を確保可能な最短経路で迂回パスを計算する迂回パス計算手段１５２と、
迂回パス計算手段１５２で計算された迂回パスを、MPLSパスを設定可能な装置に設定する迂回パス設定手段１１０−２と、を有する。
【００２２】
本発明（請求項３）は、コンピュータを、請求項２記載のパス収容計算装置として機能させるパス収容計算プログラムである。
【発明の効果】
【００２３】
上記のように本発明によれば、トポロジ情報からプライマリパスを最短になるように計算し、その後迂回パスを計算し、その結果をルータに設定することにより、迂回パスが存在しても、プライマリパスが最短経路になるように計算できるため、従来のOSPF-TEによる計算と比較して、プライマリパスの最短経路を確保することができる。
【発明を実施するための最良の形態】
【００２４】
以下、図面と共に本発明の実施の形態を説明する。
【００２５】
［第１の実施の形態］
本実施の形態では、同時に設定する入口ノード、宛先ノードの組み合わせが複数存在する場合に、全ての組み合わせのプライマリパスから設定し、当該プライマリパスの設定後に、迂回パスを設定するものである。つまり、プライマリパスの最短経路を確保するために、同時に設定する入口ノード、宛先ノードの組み合わせが複数存在する場合は、全ての組み合わせのプライマリパスから設定し、その後に迂回パスを設定する。このとき、プライマリパス及び迂回パス共に、OSPF-TE計算により、入口ノードから宛先ノードまでの残余帯域を考慮した最短経路で設定する。また、迂回パスは該当するプライマリパスの通過するリンクに完全に交わらない経路で設定する。
【００２６】
図３は、本発明のパス収容計算システムの概念図を示し、図４は、本発明の第１の実施の形態におけるパス収容計算装置の構成を示す。
【００２７】
サーバ１００は、データベース１２０、プライマリ・バックアップパスパッキング部１３０、順序制御部１４０、経路計算部１５０から構成され、プライマリパスと迂回パスをルータ(Ａ〜Ｏ)に設定する。
【００２８】
データベース１２０は、オペレータ等から取得した要求パス情報(入口ノード・出口ノード)やトポロジ情報、及び、プライマリ・バックアップパスパキング部１３０から渡されたプライマリ情報及び迂回パス情報を格納する。
【００２９】
順序制御部１４０は、順序制御アルゴリズム１４１を有し、要求ＬＳＰが複数存在する場合に、順序制御アルゴリズム１４１を起動して、経路計算部１５０のプライマリパス計算処理と迂回パス計算処理の順序を制御する。
【００３０】
経路計算部１５０は、プライマリパスを計算するプライマリパス計算部１５１と、迂回パスを計算する迂回パス計算部１５２とを有し、プライマリ・バックアップパスパッキング部１３０からの制御により、プライマリパス計算部１５１の処理によりプライマリパスの設定完了後に迂回パス計算部１５２の処理が行われる。
【００３１】
プライマリ・バックアップパスパッキング部１３０は、複数の要求ＬＳＰ情報が入力された場合には、順序制御部１４０の順序制御アルゴリズムの制御に従って経路計算部１５０に対して全ての組み合わせのプライマリパスの計算、その後に迂回パスの計算を実行させ、その結果をルータに一括設定する。
【００３２】
次に、上記のプライマリ・バックアップパスパッキング部１３０の処理について説明する。
【００３３】
以下では、連結グラフ（有向グラフ）Ｇ＝（Ｖ，Ｅ）の全ての（ｉ，ｊ）に対して長さＬｉｊとし、長さＬｉｊ＞０の辺（ｉ，ｊ）の有向グラフＧ＝（Ｖ，Ｅ）がデータベース１２０より与えられているとき、経路計算部１５０のプライマリパス計算部１５１、迂回パス計算部１５２を用いて、プライマリパス集合Ｔｋ（Ｖｔｋ，Ｅｔｋ）、Ｔの迂回パス集合Ｔ'ｋ（Ｖ'ｔｋ，Ｅ’ ｔｋ）を決定する。
【００３４】
まず、プライマリ・バックアップパスパッキング部１３０は、データベース１２０から連結グラフ（有向グラフ）Ｇの辺（ｉ，ｊ）とそれらの長さＬｉを取得し、順序制御部１４０の制御により、まず、プライマリパス計算部１５１を用いてプライマリパス集合Ｔを計算し、メモリ（図示せず）に格納する。プライマリパス計算部１５１では、OSPF-TEアルゴリズムが用いられる。解としてＴが導出されたならば、メモリ（図示せず）に格納されたプライマリパス集合Ｔｋ（Ｖｔｋ，Ｅｔｋ）をデータベース１２０に出力する。これをｋ＝１〜ｎまで繰り返す。
【００３５】
次に、プライマリ・バックアップパスパッキング部１３０は、有向グラフＧからプライマリパス集合Ｔｋを除いた有向グラフＧ’（Ｖ’，Ｅ’）を作成し、Ｇ’から迂回パス計算部１５２を用いて迂回パス集合Ｔ’を計算し、メモリ（図示せず）に格納する。迂回パス計算部１５２はOSPF-TEアルゴリズムを用いる。解としてＴ’が導出されたならば、プライマリ・バックアップパスパッキング部１３０は、メモリ（図示せず）に格納された迂回パス集合Ｔ’ｋ（Ｖ’ｔｋ，Ｅ’ｔｋ）をデータベース１２０に出力する。これをｋ＝１〜ｎまで繰り返す。
【００３６】
上記の処理が終了すると、データベース１２０に格納されていたプライマリパス・迂回パスをルータに設定する。
【００３７】
上記の処理を詳細に説明する。
【００３８】
図５は、本発明の第１の実施の形態における経路計算処理のフローチャートである。
【００３９】
ステップ１００）  プライマリ計算処理：プライマリ・バックアップパスパッキング部１３０は、プライマリパス計算部１５１を用いてプライマリパスの計算を行う。
【００４０】
ステップ１０１）  プライマリパス計算部１５１は、データベース１２０のトポロジ情報、要求ＬＳＰ情報、入口ノード情報、宛先ノード情報に基づいて、有向グラフＧから残余帯域の余っていないリンクを削除する。当該リンクが削除された有向グラフをメモリ（図示せず）に格納する。
【００４１】
ステップ１０２）  トポロジ情報に基づいて、メモリ（図示せず）に格納された有向グラフＧについて、宛先ノードまでの最短経路を選択し、当該プライマリパスをメモリ（図示せず）に格納する。
【００４２】
ステップ１０３）  ｋを１インクリメントする。
【００４３】
ステップ１０４）  ｋ＞ｎであればメモリ（図示せず）に格納されているプライマリパスを出力し、ステップ２００に移行し、そうでなければステップ１０１に移行する。
【００４４】
ステップ２００）  ステップ１００のプライマリ計算処理が終了し、プライマリパスの設定が完了すると、プライマリ・バックアップパスパッキング部１３０は、迂回パス計算部１５２を用いて迂回パスの計算を行う。
【００４５】
ステップ２０１）  迂回パス計算部１５２は、データベース１２０のトポロジ情報、要求ＬＳＰ情報、入口ノード情報、宛先ノード情報に基づいて、有向グラフＧからステップ１００で設定されたプライマリパスが通るリンクを削除し、当該プライマリが通るリンクが削除された有向グラフをメモリ（図示せず）に格納する。
【００４６】
ステップ２０２）  データベース１２０のトポロジ情報を参照して、メモリ（図示せず）に格納された有向グラフＧから残余帯域の余っていないリンクを削除し、削除後の有向グラフをメモリ（図示せず）に格納する。
【００４７】
ステップ２０３）  ステップ２０２でメモリ（図示せず）に格納された有向グラフＧについて、入口ノードノードから宛先ノードまでの最小プライマリ予約帯域について最小経路を計算し、迂回パスとしてメモリ（図示せず）に格納する。
【００４８】
ステップ２０４）  ｋを１インクリメントする。
【００４９】
ステップ２０５）  ｋ＞ｎであれば、メモリ（図示せず）に格納されている迂回パスを出力し、そうでなければステップ２０１に移行する。
【００５０】
上記の処理において、プライマリ・バックアップパスパッキング部１３０が、ステップ１０２、ステップ２０３でメモリ（図示せず）に格納されているプライマリパス・迂回パスが経路計算部１５０から出力されると、ルータに一括設定する。
【００５１】
以下に、本実施の形態の具体的な例を説明する。
【００５２】
図６は、評価ネットワークを示す。入口ノードをＡ，Ｉ、宛先ノードをＢ，Ｄ、全てのリンクのTE予約可能帯域を１００Ｍとし、ここでは、ＡからＢ、ＡからＤ、ＩからＢ、ＩからＤへそれぞれ順番に３０ＭのPrimary/Detour LSPを設定するケースについて説明する。
【００５３】
ここで、
ＡからＢへの最短経路はＡ−Ｈ−Ｇ−Ｆ−Ｂとなり、コストは３．５；
ＡからＤへの最短経路はＡ−Ｈ−Ｅ−Ｄとなり、コストは３．５；
ＩからＢへの最短経路はＩ−Ｅ−Ｆ−Ｂとなり、コストは３；
ＩからＤへの最短経路はＩ−Ｅ−Ｄとなり、コストは３；
である。よって、以下に示す経路計算結果が上記と等しくなれば最短性が確保されたこととなる。
【００５４】
以下では、順序制御部１４０によるPrimary/Detour LSPの順番制御によって計算順序を変更することによって、Primary LSPの経路の最短性を確保しようとする。ここで提案する方式は、従来のOSPF-TEの計算順序を変更し、要求のあったLSPのPrimary LSPから計算し、その後、Detour LSPを計算する。よって、ＡからＢへのPrimary LSP、ＡからＤへのPrimary LSP、ＩからＢへのPrimary LSP、ＩからＤへのPrimary LSP、ＡからＢへのDetour LSP、ＡからＤへのDetour LSP、ＩからＢへのDetour LSP、IからＤへのDetour LSP、順にLSPを設定するものとする。
【００５５】
図７は、ＡからＢへのPrimary LSP設定手順であり、プライマリパス計算部１５１（OSPF-TEアルゴリズム）の計算に従い、Ａ−Ｈ−Ｇ−Ｆ−Ｂの経路が計算され、そのコストは３．５（＝１＋１／２＋１＋１）となる。
【００５６】
図８は、ＡからＤへのPrimary LSP設定手順であり、プライマリパス計算部１５１（OSPF-TEアルゴリズム）の計算に従い、Ａ−Ｈ−Ｅ−Ｄの経路が計算され、そのコストは３．５（＝１＋１／２＋２）となる。
【００５７】
図９は、ＩからＢへのPrimary LSP設定手順であり、プライマリパス計算部１５１（OSPF-TEアルゴリズム）の計算に従い、Ｉ−Ｅ−Ｆ−Ｂの経路が計算され、そのコストは３（＝１＋１＋１）となる。
【００５８】
図１１は、ＡからＢへのDetour LSP設定手順であり、まず、有向グラフＧからＡ〜Ｂ間のプライマリパスの通る経路を除いたグラフを作成し、迂回パス計算部１５２（OSPF-TEアルゴリズム）の計算に従い、Ａ−Ｉ−Ｅ−Ｃ−Ｂの経路が計算され、そのコストは９（１＋１＋２＋５）となる。
【００５９】
図１２は、ＡからＤへのDetour LSP設定手順であり、まず、有向グラフＧからＡ〜Ｄ間のプライマリパスの通る経路を除いたグラフを作成し、迂回パス計算部１５２（OSPF-TEアルゴリズム）の計算に従い、Ａ−Ｉ−Ｈ−Ｇ−Ｆ−Ｅ−Ｃ−Ｄの経路が計算され、そのコストは１４．５（１＋３＋１／２＋１＋１＋２＋６）となる。
【００６０】
図１３は、ＩからＢへのDetour LSP設定手順であり、まず、有向グラフＧからＩ〜Ｂ間のプライマリパスの通る経路を除いたグラフを作成し、迂回パス計算部１５２（OSPF-TEアルゴリズム）の計算に従い、Ｉ−Ａ−Ｈ−Ｅ−Ｃ−Ｂの経路が計算され、そのコストは９．５（１＋１＋１／２＋２＋５）となる。
【００６１】
図１４は、ＩからＤへのDetour LSP設定手順であり、まず、有向グラフＧからＩ〜Ｄ間のプライマリパスの通る経路を除いたグラフを作成し、迂回パス計算部１５２（OSPF-TEアルゴリズム）の計算に従い、Ｉ−Ｈ−Ｇ−Ｆ−Ｂ−Ｃ−Ｄの経路が計算され、そのコストは１６．５（３＋１／２＋１＋１＋５＋６）となる。
【００６２】
上記の例におけるコストを図１５に示す。同図からわかるように、Primary LSPの最短性が確保される。
【００６３】
［第２の実施の形態］
本実施の形態では、プライマリパスはメインパスであるので、OSPF-TE計算により入口ノードから宛先ノードまでの残余帯域を考慮した最短経路で設定する。迂回パスは、入口ノードから宛先ノードまでの、総ホップ数が最小で、かつ、入口ノードから宛先ノードまでの残余帯域の候補が最大のリンクとなる経路を選択する。なおこの場合の経路の計算はダイクストラアルゴリズムを用いる。迂回パスは該当するプライマリパスの通過するリンクとは完全に交わらない経路で設定する。
【００６４】
本実施の形態におけるパス収容計算サーバの構成は、図１６に示すように、図４の構成から順序制御部を除いた構成である。本実施の形態では、Primary LSPとDetour LSPの経路計算方法を変えることによって順番制御を行わず、Primary LSPの経路の最短性を求めるものである。図１６に示すプライマリパス計算部１５１では、従来のOSPF-TEあるゴリズムを用い、迂回パス計算部１５２では、最小ホップ、最大最小残余帯域を考慮したダイクストラアルゴリズムによる計算を行う。
【００６５】
上記のプライマリ・バックアップパスパッキング部１３０の処理について説明する。
【００６６】
以下では、Ｇ＝（Ｖ，Ｅ）の全ての（ｉ，ｊ）に対してＬｉｊとし、長さＬｉｊ＞０の辺（ｉ，ｊ）の連結グラフＧ＝（Ｖ，Ｅ）が与えられているとき、経路計算部１５０のプライマリパス計算部１５１、迂回パス計算部１５２を用いて、プライマリパス集合Ｔｋ（Ｖｔｋ，Ｅｔｋ）、Ｔの迂回パス集合Ｔ'ｋ（Ｖ'ｔｋ，Ｅ’ ｔｋ）を決定する。
【００６７】
まず、プライマリ・バックアップパスパッキング部１３０は、データベース１２０から連結グラフ（有向グラフ）Ｇの辺（ｉ，ｊ）とそれらの長さＬｉを取得し、プライマリパス計算部１５１を用いてプライマリパス集合Ｔを計算し、メモリ（図示せず）に格納する。プライマリパス計算部１５１では、OSPF-TEアルゴリズムが用いられる。解としてＴが導出されたならば、メモリ（図示せず）に格納されたプライマリパス集合Ｔｋ（Ｖｔｋ，Ｅｔｋ）をルータに出力する。これをｋ＝１〜ｎまで繰り返す。
【００６８】
次に、プライマリ・バックアップパスパッキング部１３０は、Ｇからプライマリパス集合Ｔｋを除いた有向グラフＧ’（Ｖ’，Ｅ’）を作成し、迂回パス計算部１５２を用いてＧ’から入口ノードから宛先ノードまでの最小ホップ数・最大最小残余帯域となるような最短経路Ｔ’を計算し、Ｔ’をメモリ（図示せず）に格納する。迂回パス計算部１５２では、ダイクストラアルゴリズムが用いられる。解としてＴ’が導出されたならば、プライマリ・バックアップパスパッキング部１３０は、迂回パス集合Ｔ’ （Ｖ'ｔｋ，Ｅ’ ｔｋ）を、ルータに出力する。これをｋ＝１〜ｎまで繰り返す。
【００６９】
次に、上記の処理を詳細に説明する。
【００７０】
図１７は、本発明の第２の実施の形態における経路計算処理のフローチャートである。
【００７１】
ステップ３００）  プライマリ・バックアップパスパッキング部１３０は、経路計算部１５０のプライマリパス計算部１５１を用いて、プライマリパスの計算を行う。
【００７２】
ステップ３０１）  プライマリパス計算部１５１は、データベース１２０のトポロジ情報、要求ＬＳＰ情報、入口ノード情報、宛先ノード情報に基づいて、有向グラフＧから残余帯域の余っていないリンクを削除し、当該リンクが削除された有向グラフをメモリ（図示せず）に格納する。
【００７３】
ステップ３０２）  メモリ（図示せず）に格納されている有向グラフについて入口ノードから宛先ノードまでの最短経路を選択し、出力する。
【００７４】
ステップ４００）  プライマリ・バックアップパスパッキング部１３０は、経路計算部１５０の迂回パス計算部１５２を用いて、迂回パスの計算を行う。
【００７５】
ステップ４０１）  迂回パス計算部１５２は、データベース１２０のトポロジ情報、要求ＬＳＰ情報、入口ノード情報、宛先ノード情報に基づいて、有向グラフＧから該当プライマリパスの通るリンクを削除し、当該リンクが削除された有向グラフＧをメモリ（図示せず）に格納する。
【００７６】
ステップ４０２）  メモリ（図示せず）に格納されている有向グラフＧから残余帯域の余っていないリンクを削除し、当該リンクが削除された有向グラフをメモリ（図示せず）に格納する。
【００７７】
ステップ４０３）  ステップ４０２でメモリ（図示せず）に格納された有向グラフについて、入口ノードから宛先ノードまでの最小ホップ・最大最小残余帯域を考慮した経路を選択し、出力する。
【００７８】
ステップ５０１）  ｋを１インクリメントする。
【００７９】
ステップ５０２）  ｋ＞ｎであれば、処理を終了し、そうでなければステップ３０１に移行する。
【００８０】
以下に、本実施の形態の具体的な例を説明する。
【００８１】
評価ネットワークについては図６と同様である。
【００８２】
図１８は、ＡからＢへのPrimary LSP設定手順であり、プライマリパス計算部１５１（OSPF-TEアルゴリズム）の計算に従い、Ａ−Ｈ−Ｇ−Ｆ−Ｂの経路が計算され、そのコストは３．５（＝１＋１／２＋１＋１）となる。
【００８３】
図１９は、ＡからＢへのDetour LSP設定手順であり、まず、有向グラフからＡ〜Ｂ間のプライマリパスの通る経路を除いたグラフを作成し、迂回パス計算部１５２（ダイクストラ）の計算に従い、Ａ−Ｂの経路が計算され、そのコストは１０である。
【００８４】
図２０は、ＡからＤへのPrimary LSP設定手順であり、プライマリパス計算部１５１（OSPF-TEアルゴリズム）の計算に従い、Ａ−Ｈ−Ｅ−Ｄの経路が計算され、そのコストは３．５（＝１＋１／２＋２）となる。
【００８５】
図２１は、ＡからＤへのDetour LSP設定手順であり、まず、有向グラフからＡ〜Ｄ間のプライマリパスの通る経路を除いたグラフを作成し、迂回パス計算部１５２（ダイクストラ）の計算に従い、Ａ−Ｂ−Ｃ−Ｄの経路が計算され、そのコストは２１（＝１０＋５＋６）である。
【００８６】
図２２は、ＩからＢへのPrimary LSP設定手順であり、プライマリパス計算部１５１（OSPF-TEアルゴリズム）の計算に従い、Ｉ−Ｅ−Ｆ−Ｂの経路が計算され、そのコストは３（＝１＋１＋１）である。
【００８７】
図２３は、ＩからＢへのDetour LSP設定手順であり、まず、有向グラフからＩ〜Ｂ間のプライマリパスの通る経路を除いたグラフを作成し、迂回パス計算部１５２（ダイクストラ）の計算に従い、Ｉ−Ａ−Ｂの経路が計算され、そのコストは１１（＝１＋１０）である。
【００８８】
図２４は、ＩからＤへのPrimary LSP設定手順であり、プライマリ計算部１５１（OSPF-TEアルゴリズム）の計算に従い、Ｉ−Ｅ−Ｄの経路が計算され、そのコストは３（＝１＋２）である。
【００８９】
図２５は、ＩからＤへのDetour LSP設定手順であり、まず、有向グラフからＩ〜Ｄ間のプライマリパスの通る経路を除いたグラフを作成し、迂回パス計算部１５２（ダイクストラ）の計算に従い、Ｉ−Ｈ−Ｅ−Ｃ−Ｄの経路が計算され、そのコストは１１．５（＝３＋１／２＋２＋６）である。
【００９０】
図２６に上記で求められたコストの例を示す。同図からわかるように、それぞれの要求に応じてＡからＢへのPrimary LSP、ＡからＢへのDetour LSP、ＡからＤへのPrimary LSP、ＡからＤへのDetour LSP、ＩからＢへのPrimary LSP、ＩからＢへのDetour LSP、ＩからDへのPrimary LSP、ＩからＤへのDetour LSP、と順にLSPしてもPrimary LSPの最短性が確保される。
【００９１】
前述の従来の技術では、図３５に示すように、
ＡからＢへの最短経路はＡ−Ｈ−Ｇ−Ｆ−Ｂとなり、コストは３．５；
ＡからＤへの最短経路はＡ−Ｈ−Ｅ−Ｄとなり、コストは３．５；
ＩからＢへの最短経路はＩ−Ｅ−Ｆ−Ｂとなり、コストは３；
ＩからＤへの最短経路はＩ−Ｅ−Ｄとなり、コストは５．５；
となり、迂回パスによってプライマリパスの通過すべき最短経路が確保できなくなることがあるのに対し、上記の第１の実施の形態の図１５、第２の実施の形態の図２６に示すようにPrimary LSPの最短性が確保される。
【００９２】
なお、本発明は、上記の第１の実施の形態及び第２の実施の形態のパス収容計算サーバの機能をプログラムとして構築し、パス収容計算サーバ（装置）として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００９３】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００９４】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００９５】
本発明は、TE LSPを設定可能なMPLSネットワーク技術における、P2P TE LSPのソース（Ingress）ノードと宛先(Egress)ノードを結ぶプライマリパスと迂回パスを設定する技術に適用可能である。また、重要度の高いトラフィックと低いトラフィックを振り分けるようなサービスにも適用可能である。
【図面の簡単な説明】
【００９６】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明のパス収容計算システムの概念図である。
【図４】本発明の第１の実施の形態におけるパス収容計算装置の構成図である。
【図５】本発明の第１の実施の形態における経路計算処理のフローチャートである。
【図６】本発明の第１の実施の形態における動作例を示す図（その１）である。
【図７】本発明の第１の実施の形態における動作例を示す図（その２）である。
【図８】本発明の第１の実施の形態における動作例を示す図（その３）である。
【図９】本発明の第１の実施の形態における動作例を示す図（その４）である。
【図１０】本発明の第１の実施の形態における動作例を示す図（その５）である。
【図１１】本発明の第１の実施の形態における動作例を示す図（その６）である。
【図１２】本発明の第１の実施の形態における動作例を示す図（その７）である。
【図１３】本発明の第１の実施の形態における動作例を示す図（その８）である。
【図１４】本発明の第１の実施の形態における動作例を示す図（その９）である。
【図１５】本発明の第１の実施の形態におけるコストを示す図である。
【図１６】本発明の第２の実施の形態におけるパス収容計算サーバの構成図である。
【図１７】本発明の第２の実施の形態における経路計算処理のフローチャートである。
【図１８】本発明の第２の実施の形態における動作例を示す図（その１）である。
【図１９】本発明の第２の実施の形態における動作例を示す図（その２）である。
【図２０】本発明の第２の実施の形態における動作例を示す図（その３）である。
【図２１】本発明の第２の実施の形態における動作例を示す図（その４）である。
【図２２】本発明の第２の実施の形態における動作例を示す図（その５）である。
【図２３】本発明の第２の実施の形態における動作例を示す図（その６）である。
【図２４】本発明の第２の実施の形態における動作例を示す図（その７）である。
【図２５】本発明の第２の実施の形態における動作例を示す図（その８）である。
【図２６】本発明の第２の実施の形態におけるコストを示す図である。
【図２７】従来のOSPF-TEを説明するための図（その１）である。
【図２８】従来のOSPF-TEを説明するための図（その２）である。
【図２９】従来のOSPF-TEを説明するための図（その３）である。
【図３０】従来のOSPF-TEを説明するための図（その４）である。
【図３１】従来のOSPF-TEを説明するための図（その５）である。
【図３２】従来のOSPF-TEを説明するための図（その６）である。
【図３３】従来のOSPF-TEを説明するための図（その７）である。
【図３４】従来のOSPF-TEを説明するための図（その８）である。
【図３５】従来のコストの例である。
【符号の説明】
【００９７】
１００  パス収容計算装置、パス収容計算サーバ
１１０−１  プライマリパス設定手段
１１０−２  迂回パス設定手段
１２０  データベース
１３０  ノード特定手段、プライマリ・バックアップパスパッキング部
１４０  順序制御部
１４１  順序制御アルゴリズム
１５０  経路計算部
１５１  プライマリパス計算手段、プライマリパス計算部
１５２  迂回パス計算手段、迂回パス計算部
【図１】
0004463779.tif 000002
【図２】
0004463779.tif 000003
【図３】
0004463779.tif 000004
【図４】
0004463779.tif 000005
【図５】
0004463779.tif 000006
【図６】
0004463779.tif 000007
【図７】
0004463779.tif 000008
【図８】
0004463779.tif 000009
【図９】
0004463779.tif 000010
【図１０】
0004463779.tif 000011
【図１１】
0004463779.tif 000012
【図１２】
0004463779.tif 000013
【図１３】
0004463779.tif 000014
【図１４】
0004463779.tif 000015
【図１５】
0004463779.tif 000016
【図１６】
0004463779.tif 000017
【図１７】
0004463779.tif 000018
【図１８】
0004463779.tif 000019
【図１９】
0004463779.tif 000020
【図２０】
0004463779.tif 000021
【図２１】
0004463779.tif 000022
【図２２】
0004463779.tif 000023
【図２３】
0004463779.tif 000024
【図２４】
0004463779.tif 000025
【図２５】
0004463779.tif 000026
【図２６】
0004463779.tif 000027
【図２７】
0004463779.tif 000028
【図２８】
0004463779.tif 000029
【図２９】
0004463779.tif 000030
【図３０】
0004463779.tif 000031
【図３１】
0004463779.tif 000032
【図３２】
0004463779.tif 000033
【図３３】
0004463779.tif 000034
【図３４】
0004463779.tif 000035
【図３５】
0004463779.tif 000036