(57)【特許請求の範囲】
【請求項１】
接続関係情報やリンクコスト情報を有し、ポイントツーマルチポイント（P2MP）パスを設定するための迂回経路計算を行う迂回経路計算装置であって、
経路設定の対象となるノードとリンク集合と、迂回パスが必要となるP2MPパスの入口ノードと複数の出口ノードの情報が入力されると、該迂回パスが必要となるP2MP TE LSP(P2MP Traffic Engineering Label Switched Path)に対して、該リンク集合からP2MP プライマリパスを通る物理リンクと物理ノードを除いて、該入口ノードから該出口ノードまで、該P2MPプライマリパスと交わらないように残りのリンクとノードから、該入口ノードから該出口ノードまでのP2MP迂回パスを計算する迂回パス計算手段と、
前記迂回パス計算手段の結果を格納する記憶手段と、を有し、
前記迂回パス計算手段は、
前記迂回パスが必要となるP2MP TE LSPに対して、前記リンク集合から前記プライマリパスが通る物理リンクと物理ノードを除いた残りのリンクとノードを用いて、該プライマリパスが設定された前記入口ノードから前記出口ノードまでを、経路計算アルゴリズムによって最短経路または最小経路を計算し、該入口ノードから該出口ノードまで該プライマリパスとリンクの交わらないP2MP迂回パスを計算する第１の迂回パス計算手段と、
前記第１の迂回パス計算手段で計算された経路に基づいて、前記P2MP迂回パスを該経路上のノードに設定する第１の迂回パス設定手段と、
前記第１の迂回パス計算手段において、前記出口ノードの中に経路到達不可能であった該出口ノードが存在し、経路が計算されなかった場合、前記入口ノードから、経路到達不能となった該出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでを、再度、前記経路計算アルゴリズムにより最短経路または、最小経路を計算し、経路到達可能かを確認する第１の確認手段と、
前記経路計算アルゴリズムにより、経路到達可能であった場合は、前記入口ノードから、経路到達不可能であった前記出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでの経路について、前記経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流の該ノードから到達不可能であった該出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定する第２の迂回パス設定手段と、
前記経路計算アルゴリズムにより、経路到達が不可能であった場合は、前記入口ノードから、到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノードに対して、再度前記経路計算アルゴリズムにより経路計算を行い、経路到達可能かを確認する第２の確認手段と、
さらに、経路到達不可能であれば、前記第２の確認手段を、前記入口ノードに到達するまでｎホップ分繰り返す繰り返し手段と、
前記繰り返し手段において、経路到達可能であった場合は、該入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、該経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流のノードから該到達不可能であった出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定し、該入口ノードに至るまで（ｋ＝ｎ）経路到達不可能であった該出口ノードに対しては、該入口ノードから該出口ノードまでの該プライマリパスと同一の経路を、P2MP迂回パスを通る経路として該経路上のノードに設定する第３の迂回パス設定手段と、
を含むことを特徴とする迂回経路計算装置。
【請求項２】
経路計算結果を格納する記憶手段を有するコンピュータを、
前記請求項１記載の迂回経路計算装置として機能させることを特徴とする迂回経路計算プログラム。
【請求項３】
迂回パスが必要となるP2MP入口ノードと複数の出口ノードを有するネットワークにおいて、迂回パスを設定する迂回経路計算サーバであって、
請求項１記載の迂回経路計算装置と、
前記ネットワーク上のノードに対して前記迂回経路計算装置で求められた迂回P2MPパスの情報を送信する手段と、
を有することを特徴とする迂回経路計算サーバ。
【請求項４】
迂回パスが必要となるルータであって、
請求項１記載の迂回経路計算装置と、
前記迂回経路計算装置から取得した迂回経路情報を格納するデータベースと、
を有することを特徴とするルータ。
【請求項５】
ポイントツーマルチポイント（P2MP）パスを設定可能な迂回経路計算装置を有し、該装置が接続関係情報やリンクコスト情報を有するネットワークにおいて、迂回経路計算を行う迂回経路計算方法であって、
迂回パスが必要となるプライマリパスに対して、リンク集合から該プライマリパスが通る物理リンクと物理ノードを除いた残りのリンクとノードを用いて、該プライマリパスが設定された入口ノードから出口ノードまでを、経路計算アルゴリズムによって最短経路または最小経路を計算し、該入口ノードから該出口ノードまで該プライマリパスとリンクの交わらないP2MP迂回パスを計算する迂回パス計算ステップと、
前記迂回パス計算ステップで計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定する第１の迂回パス設定ステップと、
前記迂回パス計算ステップにおいて、前記出口ノードの中に経路到達不可能であった該出口ノードが存在し、経路が計算されなかった場合、前記入口ノードから、経路到達不能となった該出口ノードの通るプライマリパスから１ホップ上流のノードと経路到達可能であった出口ノードまでを、再度、前記経路計算アルゴリズムにより最短経路または、最小経路を計算し、経路到達可能かを確認する第１の確認ステップと、
前記経路計算アルゴリズムにより、経路到達可能であった場合は、前記入口ノードから、経路到達不可能であった前記出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、前記経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流の該ノードから到達不可能であった該出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定する第２の迂回パス設定ステップと、
前記計算アルゴリズムにより、経路到達が不可能であった場合は、前記入口ノードから、到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノードに対して、再度前記経路計算アルゴリズムにより経路計算を行い、経路到達可能かを確認する第２の確認ステップと、
さらに、経路到達不可能であれば、前記第２の確認ステップを、前記入口ノードに到達するまでｎホップ分繰り返す繰り返しステップと、
前記繰り返しステップにおいて、経路到達可能であった場合は、該入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、該経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流のノードから該到達不可能であった出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定し、該入口ノードに至るまで（ｋ＝ｎ）経路到達不可能であった該出口ノードに対しては、該入口ノードから該出口ノードまでの該プライマリパスと同一の経路を、P2MP迂回パスを通る経路として該経路上のノードに設定する第３の迂回パス設定ステップと、
を行うことを特徴とする迂回経路計算方法。
【請求項６】
ポイントツーマルチポイント（P2MP）パスを設定可能な迂回経路計算装置を有し、該装置が接続関係情報やリンクコスト情報を有するネットワークにおいて、迂回経路計算を行う迂回経路計算システムであって、
経路設定の対象となるノードとリンク集合と、迂回パスが必要となるP2MPパスの入口ノードと複数の出口ノードの情報が入力されると、該迂回パスが必要となるP2MP TE LSPに対して、該リンク集合からP2MPプライマリパスが通る物理リンクと物理ノードを除いた残りのリンクとノードを用いて、該プライマリパスが設定された該入口ノードから該出口ノードまでを経路計算アルゴリズムによって最短経路または最小経路を計算し、該入口ノードから該出口ノードまでの該プライマリパスとリンクの交わらないP2MP迂回パスを計算する迂回パス計算手段と、
前記迂回パス計算手段で計算された経路に基づいて、P2MP迂回パスを該経路上のノードに設定する第１の迂回パス設定手段と、
前記迂回パス計算手段において、前記出口ノードの中に経路到達不可能であった該出口ノードが存在し、経路が計算されなかった場合、前記入口ノードから、経路到達不能となった該出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでを、再度、前記経路計算アルゴリズムにより最短経路または、最小経路を計算し、経路到達可能かを確認する第１の確認手段と、
前記経路計算アルゴリズムにより、経路到達可能であった場合は、前記入口ノードから、経路到達不可能であった前記出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、前記経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流の該ノードから到達不可能であった該出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定する第２の迂回パス設定手段と、
前記経路計算アルゴリズムにより、経路到達が不可能であった場合は、前記入口ノードから、到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノードに対して、再度前記経路計算アルゴリズムにより経路計算を行い、経路到達可能かを確認する第２の確認手段と、
さらに、経路到達不可能であれば、前記第２の確認手段を、前記入口ノードに到達するまでｎホップ分繰り返す繰り返し手段と、
前記繰り返し手段において、経路到達可能であった場合は、該入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、該経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流のノードから該到達不可能であった出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定し、該入口ノードに至るまで（ｋ＝ｎ）経路到達不可能であった該出口ノードに対しては、該入口ノードから該出口ノードまでの該プライマリパスと同一の経路を、P2MP迂回パスを通る経路として該経路上のノードに設定する第３の迂回パス設定手段と、
を有することを特徴とする迂回経路計算システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、迂回経路計算装置及びプログラム及び迂回経路計算サーバ及びルータ及び迂回経路計算方法及びシステムに係り、特に、Point-to-MultiPoint(P2MP)Trafic Engineering(TE)Label Switched Path(LSP)を設定可能なMPLSネットワーク技術における、P2MP TE LSPのIngress（ソース）ノードと複数Egress（リーフ）ノードを結ぶPrimaryパスに対して、End-End間でのP2MP迂回パスを設定するための迂回経路計算装置及びプログラム及び迂回経路計算サーバ及びルータ及び迂回経路計算方法及びシステムに関する。
【背景技術】
【０００２】
P2MP TE LSPに対して、P2P TE LSPの迂回パスを設定する方式があるが、P2MP TE LSPに対して、P2MP TE LSPの迂回パスを設定する方式は今まで提案されておらず、Primary P2MP TE LSPを設定しているリンクが故障などを引き起こした場合に、迂回させる技術がない。
【０００３】
なお、P2Pのパスを設定するためのプロトコル規定（例えば、非特許文献１参照）やP2MPのパスを設定するためのプロトコル規定（例えば、非特許文献２参照）がある。
【非特許文献１】http://www.ietf.org/rfc3209.txt?number=3209
【非特許文献２】http://ietf.org/internet-drafts/draft-ietf-mpls-rsvp-te-p2mp-02.txt
【発明の開示】
【発明が解決しようとする課題】
【０００４】
上記のように、P2MP TE LSPに対して、P2MP TE LSPの迂回パスを設定する方式がないため、仮に、P2MP TE LSPに対して、P2P TE LSPの迂回パスを設定すると、リンク使用効率が悪くなるという問題がある。
【０００５】
また、従来の迂回パス計算では、迂回パスを求められない場合は、解無しとしてしまうため、それ以外の迂回パスを求められたそれ以外の多くのユーザに影響を及ぼしてしまうという問題がある。
【０００６】
本発明は、上記の点に鑑みなされたもので、P2MP TE LSPによるP2MP TE LSPのための迂回パスを設定することが可能で、かつ、迂回パスを求められないような状況においても必ず解を出すことが可能な迂回経路計算装置及びプログラム及び迂回経路計算サーバ及びルータ及び迂回経路計算方法及びシステムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
図１は、本発明の原理構成図である。
【０００９】
本発明（請求項１）は、接続関係情報やリンクコスト情報を有し、P2MPパスを設定するための迂回経路計算を行う迂回経路計算装置であって、
経路設定の対象となるノード情報とリンク集合と、迂回パスが必要となるP2MPパスの入口ノードと複数の出口ノードの情報が入力されると、該迂回パスが必要となるP2MP TE LSPに対して、リンク集合からP2MP プライマリパスを通る物理リンクと物理ノードを除いて、該入口ノードから該出口ノードまで、該P2MPプライマリパスと交わらないように残りのノードとリンクから、該入口ノードから該出口ノードまでのP2MP迂回パスを計算する迂回パス計算手段４０と、
迂回パス計算手段４０の結果を格納する記憶手段２０と、を有し、
迂回パス計算手段４０は、
迂回パスが必要となるプライマリパスに対して、リンク集合から該プライマリパスが通る物理リンクと物理ノードを除いた残りのリンクとノードを用いて、該プライマリパスが設定された入口ノードから出口ノードまでを、経路計算アルゴリズムによって最短経路または最小経路を計算し、該入口ノードから該出口ノードまで該プライマリパスとリンクの交わらないP2MP迂回パスを計算する第１の迂回パス計算手段と、
第１の迂回パス計算手段で計算された経路に基づいて、P2MP迂回パスを該経路上のノードに設定する第１の迂回パス設定手段と、
第１の迂回パス計算手段において、出口ノードの中に経路到達不可能であった該出口ノードが存在し、経路が計算されなかった場合、入口ノードから、経路到達不能となった該出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでを、再度、経路計算アルゴリズムにより最短経路または、最小経路を計算し、経路到達可能かを確認する第１の確認手段と、
経路計算アルゴリズムにより、経路到達可能であった場合は、入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流の該ノードから到達不可能であった該出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定する第２の迂回パス設定手段と、
経路計算アルゴリズムにより、経路到達が不可能であった場合は、入口ノードから、到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノードに対して、再度経路計算アルゴリズムにより経路計算を行い、経路到達可能かを確認する第２の確認手段と、
さらに、経路到達不可能であれば、第２の確認手段を、入口ノードに到達するまでｎホップ分繰り返す繰り返し手段と、
繰り返し手段において、経路到達可能であった場合は、該入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、該経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流のノードから該到達不可能であった出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定し、該入口ノードに至るまで（ｋ＝ｎ）経路到達不可能であった該出口ノードに対しては、該入口ノードから該出口ノードまでの該プライマリパスと同一の経路を、P2MP迂回パスを通る経路として該経路上のノードに設定する第３の迂回パス設定手段と、を含む。
【００１０】
本発明（請求項２）は、経路計算結果を格納する記憶手段を有するコンピュータを、
請求項１記載の迂回経路計算装置として機能させるプログラムである。
【００１１】
本発明（請求項３）は、迂回パスが必要となるP2MP入口ノードと複数の出口ノードを有するネットワークにおいて、迂回パスを設定する迂回経路計算サーバであって、
請求項１記載の迂回経路計算装置と、
ネットワークのノードに対して迂回経路計算装置で求められた迂回P2MPパスの情報を送信する手段と、を有する。
【００１２】
本発明（請求項４）は、迂回パスが必要となるルータであって、
請求項１記載の迂回経路計算装置と、
迂回経路計算装置から取得した迂回経路情報を格納するデータベースと、を有する。
【００１３】
図２は、本発明の原理説明図である。
【００１４】
本発明は、ポイントツーマルチポイント（P2MP）パスを設定可能な迂回経路計算装置を有し、該装置が接続関係情報やリンクコスト情報を有するネットワークにおいて、迂回経路計算を行う迂回経路計算方法であって、
経路設定の対象となるノードとリンク集合と、迂回パスが必要となるP2MPパスの入口ノードと複数の出口ノードの情報が入力されると、該迂回パスが必要となるP2MP TE LSPに対して、リンク集合からP2MP プライマリパスを通る物理リンクと物理ノードを除いて（ステップ２）、該入口ノードから該出口ノードまで、該P2MPプライマリパスと交わらないように残りのノードとリンクから、該入口ノードから該出口ノードまでのP2MP迂回パスを計算する迂回パス計算ステップ（ステップ３）と、
迂回パス計算ステップの結果を記憶手段に格納するステップ（ステップ４）と、を行う。
【００１５】
本発明（請求項５）は  ポイントツーマルチポイント（P2MP）パスを設定可能な迂回経路計算装置を有し、該装置が接続関係情報やリンクコスト情報を有するネットワークにおいて、迂回経路計算を行う迂回経路計算方法であって、
迂回パスが必要となるP2MPパスの入口ノードと複数の出口ノードが特定されると、
迂回パスが必要となるP2P TE LSPに対して、リンク集合からプライマリパスが通る物理リンクと物理ノードを除いた残りのリンクとノードを用いて、該プライマリパスが設定された入口ノードから出口ノードまでを、経路計算アルゴリズムによって最短経路または最小経路を計算し、該入口ノードから該出口ノードまで該プライマリパスとリンクの交わらないP2MP迂回パスを計算する第１の迂回パス計算ステップと、
第１の迂回パス計算ステップで計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定する第１の迂回パス設定ステップと、
出口ノードの中に経路到達不可能であった該出口ノードが存在し、経路が計算されなかった場合、入口ノードから、経路到達不能となった該出口ノードの通るプライマリパスから１ホップ上流のノードと経路到達可能であった出口ノードまでを、再度、経路計算アルゴリズムにより最短経路または、最小経路を計算し、経路到達可能かを確認する第１の確認ステップと、
経路計算アルゴリズムにより、経路到達可能であった場合は、入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流の該ノードから到達不可能であった該出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定する第２の迂回パス設定ステップと、
経路計算アルゴリズムにより、経路到達が不可能であった場合は、入口ノードから、到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノードに対して、再度経路計算アルゴリズムにより経路計算を行い、経路到達可能かを確認する第２の確認ステップと、
さらに、経路到達不可能であれば、第２の確認ステップを、入口ノードに到達するまでｎホップ分繰り返す繰り返しステップと、
繰り返しステップにおいて、経路到達可能であった場合は、該入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、該経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流のノードから該到達不可能であった出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定し、該入口ノードに至るまで（ｋ＝ｎ）経路到達不可能であった該出口ノードに対しては、該入口ノードから該出口ノードまでの該プライマリパスと同一の経路を、P2MP迂回パスを通る経路として該経路上のノードに設定する第３の迂回パス設定ステップと、を行う。
【００１６】
本発明（請求項６）は、ポイントツーマルチポイント（P2MP）パスを設定可能な迂回経路計算装置を有し、該装置が接続関係情報やリンクコスト情報を有するネットワークにおいて、迂回経路計算を行う迂回経路計算システムであって、
経路設定の対象となるノードとリンク集合と、迂回パスが必要となるP2MPパスの入口ノードと複数の出口ノードの情報が入力されると、迂回パスが必要となるP2MP TE LSPに対して、リンク集合からプライマリパスが通る物理リンクと物理ノードを除いた残りのリンクとノードを用いて、該プライマリパスが設定された入口ノードから出口ノードまでを、経路計算アルゴリズムによって最短経路または最小経路を計算し、該入口ノードから該出口ノードまで該プライマリパスとリンクの交わらないP2MP迂回パスを計算する迂回パス計算手段と、
迂回パス計算手段で計算された経路に基づいて、迂回パスを該経路上のノードに設定する第１の迂回パス設定手段と、
迂回パス計算手段において、出口ノードの中に経路到達不可能であった該出口ノードが存在し、経路が計算されなかった場合、入口ノードから、経路到達不能となった該出口ノードの通るプライマリパスから１ホップ上流のノードと経路到達可能であった出口ノードまでを、再度、経路計算アルゴリズムにより最短経路または、最小経路を計算し、経路到達可能かを確認する第１の確認手段と、
経路計算アルゴリズムにより、経路到達可能であった場合は、入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスから１ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流の該ノードから到達不可能であった該出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定する第２の迂回パス設定手段と、
経路計算アルゴリズムにより、経路到達が不可能であった場合は、入口ノードから、到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノードに対して、再度経路計算アルゴリズムにより経路計算を行い、経路到達可能かを確認する第２の確認手段と、
さらに、経路到達不可能であれば、第２の確認手段を、入口ノードに到達するまでｎホップ分繰り返す繰り返し手段と、
繰り返し手段において、経路到達可能であった場合は、該入口ノードから、経路到達不可能であった出口ノードの通るプライマリパスからｋ（ｋ＝２，３，…，ｎ）ホップ上流のノード及び経路到達可能であった出口ノードまでの経路については、該経路計算アルゴリズムによって計算された経路に基づいて、該経路上のノードにP2MP迂回パスを設定し、ｋホップ上流のノードから該到達不可能であった出口ノードまでの経路については、該プライマリパスと同一の経路を通るように、該経路上のノードにP2MP迂回パスを設定し、該入口ノードに至るまで（ｋ＝ｎ）経路到達不可能であった該出口ノードに対しては、該入口ノードから該出口ノードまでの該プライマリパスと同一の経路を、P2MP迂回パスを通る経路として該経路上のノードに設定する第３の迂回パス設定手段と、を有する。
【発明の効果】
【００１７】
上記のように本発明によれば、P2MP TE LSPで設定されたプライマリパスに対して、Ingress（入口ノード）から複数のEgressノード（出口ノード）に対して、P2MP TE LSPを迂回パスとして設定することにより、P2MP TE LSPの迂回経路を実現することができる。
【００１８】
また、P2MP TE LSPのプライマリパス、迂回パスは、P2P TE LSPと比較して多くのリンクに分岐するため、ネットワーク状態によっては完全にプライマリパスと交わらない迂回パスを設計できないケースも考えられる。そこで、本発明は、ネットワーク状態によって最適なP2MP迂回パスを設定することにより、あらゆるネットワーク状態に応じてP2MP TE LSPの迂回経路を実現することができる。
【００１９】
さらに、本発明によれば、迂回パスを求められないような状況においても、条件緩和を施すことによって必ず解を出すことができる。これにより、P2MP TE LSPのような１ソースに対して複数の宛先が存在するパスにおいては、１つの宛先に対して迂回パスを求められなった場合に解無しとしてしまうと、それ以外の迂回パスを求められたそれ以外の多くのユーザに影響を及ぼしてしまうが、本発明の条件緩和による迂回パスの設定によって、必ず解を出すようにすることで、ユーザへの影響度を軽減させることができる。
【００２０】
また、上記の本発明の条件緩和のための方法をP2MP TE LSPにも適用することが可能である。
【発明を実施するための最良の形態】
【００２１】
以下、図面と共に本発明の実施の形態を説明する。
【００２２】
本実施の形態では、迂回経路を計算するための動作の概要を説明する。
【００２３】
図３は、本発明の一実施の形態におけるP2MP 迂回パスのネットワークを示す。以下、同図の構成を例に説明する。
【００２４】
図４は、本発明の一実施の形態における経路計算装置の構成図である。同図に示すように、経路計算装置１は、迂回パス計算部４０とデータベース２０から構成される。
【００２５】
図５は、本発明の一実施の形態における動作の概要を示すフローチャートである。
【００２６】
ステップ１０１）  最初に、経路設定対象のノード、リンク集合と共に、ソースノード、リーフノードが、オペレータから入力されることにより特定される。ここでは、図３に示すように、Ingressノード（ソースノード）をノードＡとし、Egressノード（リーフノード）をノードＬ，Ｍ，Ｎ，Ｏとする。なお、ここで入力されるノードやリンク集合は、データベースなどの記憶手段から読み込んで入力されるものとする。
【００２７】
ステップ１０２）  まず、経路計算装置１の迂回パス計算部４０は、迂回パス（迂回経路）が必要となるP2MP TE LSPに対して、入力されたリンク集合からそのプライマリパスが通る物理リンクを除く。図６の例では、プライマリP2MP TE LSPを通るリンクＡ−Ｃ，Ｃ−Ｅ，Ｅ−Ｈ，Ｈ−Ｌ，Ｈ−Ｍ，Ｅ−Ｉ，Ｉ−Ｎ，Ｃ−Ｇ、Ｇ−Ｋ，Ｋ−０を除く。
【００２８】
ステップ１０３）  迂回パス計算部４０は、図７に示すような、プライマリパスが削除された残りのリンク（ソースノードからリーフノードまで）を用いて、経路計算アルゴリズムで迂回パスの通る経路を計算する。具体的には、Dijkstra経路計算アルゴリズムによって、最短パスを計算し、End-to-Endでプライマリパスと交わらないP2MP 迂回パスのための経路を計算する。
【００２９】
ステップ１０４）  迂回パス計算部４０は、経路計算アルゴリズム（Dijkstra経路計算アルゴリズム）によって経路が出力された場合（End-to-EndでP2MP 迂回パスが設定可能となった場合）は、ステップ１１０に移行する。一方、経路が出力されなかった場合には、ステップ１０５に移行する。
【００３０】
ステップ１０５）  迂回パス計算部４０は、End-to-EndでP2MP 迂回パスを設定できない場合は、図８に示すように、ソースノードをＡ、リーフノードをＬ，Ｍ，Ｎ，Ｏとし、迂回パスが必要となるP2MP TE LSPに対して、そのプライマリパスが通る物理リンクを除く。その結果は、図９のようになる。図９の例では、P2MPプライマリパスを通るリンクＡ−Ｃ，Ｃ−Ｅ、Ｅ−Ｈ，Ｈ−Ｌ，Ｈ−Ｍ，Ｅ−Ｉ，Ｉ−Ｎ，Ｃ−Ｇ，Ｇ−Ｋ，Ｋ−Ｏを除く。
【００３１】
ステップ１０６）  迂回パス計算部４０は、残りのリンクを用いて、プライマリパスが設定されたソースノードからリーフノードまでをDijkstra経路計算アルゴリズムによって最短パスを計算し、End-to-Endでプライマリパスと交わらないP2MP 迂回パスのための経路を計算する。
【００３２】
ステップ１０７）  迂回パス計算部４０は、経路計算の経路が出力されたかを判断する。経路が出力された場合は、ステップ１１０に移行する。一方、経路が出力されなかった場合は、ステップ１０８に移行する。この例では、図１０に示すように、リーフノードＭへの経路が見つからなかった。
【００３３】
ステップ１０８）  経路が出力されない場合は、まず、次のノードがソースノードであるかを判定し、ソースノードである場合は処理を終了し、ソースノードでない場合はステップ１０９に移行する。
【００３４】
ステップ１０９）  リーフノードの中に経路到達不可能であったノードが存在することとなり、次は、ソースノードからその到達不可能であったリーフノードの通るプライマリパスから１ホップ上流のノードと経路到達可能であったリーフノードまでを、再度Dijkstra経路計算を行い、ステップ１０７に移行し、経路到達可能か確認する。
【００３５】
ステップ１１０）  迂回パス計算部４０は、ステップ１０４及びステップ１０７において、経路が出力された場合には、経路計算の結果をデータベース２０に格納する。さらに、経路計算の結果、経路が出力された場合には、当該経路を元に、図１１に示すようにP2MP 迂回パスを設定する。なお、図１１において、点線はP2MP プライマリパスを示し、実線はP2MP 迂回パスを示す。
【００３６】
上記の処理において、Dijkstra経路計算アルゴリズムによって経路到達が不可能であった場合は、次は、ソースノードから、その到達不可能であったリーフノードの通るプライマリパスから２ホップ上流のノードに対して、再度、Dijkstra経路計算を行い、経路到達可能かを計算する。さらに、経路到達不可能であれば、図１２、図１３に示すように、これをソースノードに到達するまでｎホップ分繰り返す。
【００３７】
この場合、リーフノードＭの通るプライマリパス上のリンクで１ホップ上流側のノードＨを検索し、再度ソースノードＡからリーフノードＬ，Ｎ，ＯとノードＨに対して、Dijkstraアルゴリズムによってプライマリパスと交わらない経路を計算する。（今度は、ノードＨに対してＡ−Ｄ−Ｇ−Ｆ−Ｈを通る経路が計算される）。
【００３８】
Dijkstra経路計算アルゴリズムによって出力された経路を元に、P2MP 迂回パスを設定する。ソースノードから経路到達不可能であったリーフノードの通るプライマリパスからｋ（ｋ＝１，２，…，ｎ）ホップ上流のノードと経路到達可能であったリーフノードまでの経路は、Dijkstraアルゴリズムによって計算された経路を元に、P2MP 迂回パスを設定する。ｋホップ上流のノードから到達不可能であったリーフノードまでの経路は、プライマリパスと同一の経路を通るように、迂回パスを設定する。ソースノードに至るまでの（ｋ＝ｎ）経路到達不可能であったリーフノードに対しては、ソースノードからリーフノードまでのプライマリパスと同一の経路をP2MP 迂回パスを通る経路として設定する。経路が設定された例を図１４に示す。なお、同図において、点線はP2MP プライマリパスを示し、実線はP2MP 迂回パスを示す。
【００３９】
図１５は、本発明の一実施の形態におけるサーバの構成を示す。
【００４０】
同図に示すサーバ１００は、上記の図４に示す迂回パス計算部４０とネットワーク上の各ノードにP2MPパスの情報を送信するための送信部２を有する。
【００４１】
図１６は、本発明の一実施の形態におけるルータの構成図である。
【００４２】
同図に示すルータ２００は、上記の図４に示す迂回パス計算部４０と、迂回パス計算部４０から出力された経路計算結果を格納するデータベース３及び送受信部４を有する。
【００４３】
上記の図１５、図１６に示すように、経路計算装置１の迂回パス計算部４０をサーバ１００または、ルータ２００のいずれかに設けることができる。
【００４４】
なお、上記の例では、経路計算アルゴリズムとして、Dijkstraアルゴリズムを用いたが、その他、Prim、ＫＭＢ，ＤＤＭＣ等のアルゴリズムを利用することも可能である。
【００４５】
また、上記の迂回経路計算装置の動作をプログラムとして構築し、迂回経路計算装置として利用されるコンピュータ、サーバ、ノードにインストールして実行させることも可能である。
【００４６】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００４７】
本発明は、P2MP迂回経路を設定するための技術に適用可能である。
【図面の簡単な説明】
【００４８】
【図１】本発明の原理構成図である。
【図２】本発明の原理説明図である。
【図３】本発明の一実施の形態におけるP2MP迂回パス設定を行うネットワークを示す図である。
【図４】本発明の一実施の形態における動作の概要を示すフローチャートである。
【図５】本発明の一実施の形態におけるプライマリパスの削除を示す図である。
【図６】本発明の一実施の形態におけるプライマリパスが削除されたネットワークを示す図である。
【図７】本発明の一実施の形態におけるP2MP迂回パスが設定できなかった場合のネットワークを示す図である。
【図８】本発明の一実施の形態におけるプライマリパスを削除した例である。
【図９】本発明の一実施の形態における経路計算の結果を示す図である。
【図１０】本発明の一実施の形態における経路計算により経路が出力された場合のP2MP迂回パスの設定例である。
【図１１】本発明の一実施の形態における経路計算により経路が出力されなかった場合の動作を説明するための図（その１）である。
【図１２】本発明の一実施の形態における経路計算により経路が出力されなかった場合の動作を説明するための図（その２）である。
【図１３】本発明の一実施の形態における迂回パス設定の例である。
【符号の説明】
【００４９】
Ａ〜Ｏ  ノード
１  迂回経路計算装置
２  送信部
３  データベース
４  送受信部
１０  ルータコンフィグ変換部
２０  記憶手段、データベース
４０  迂回パス計算手段、迂回パス計算部
１００  サーバ
２００  ルータ
【図１】
0004417896.tif 000002
【図２】
0004417896.tif 000003
【図３】
0004417896.tif 000004
【図４】
0004417896.tif 000005
【図５】
0004417896.tif 000006
【図６】
0004417896.tif 000007
【図７】
0004417896.tif 000008
【図８】
0004417896.tif 000009
【図９】
0004417896.tif 000010
【図１０】
0004417896.tif 000011
【図１１】
0004417896.tif 000012
【図１２】
0004417896.tif 000013
【図１３】
0004417896.tif 000014