(57)【要約】【課題】  マルチキャストMPLSネットワークにおいて、P2MP LSPに対する効率的な迂回経路設定を実現することができ、ネットワーク内のリンク／ノード障害から高速に迂回し、通信の信頼性を確保する。【解決手段】  本発明は、保護対象であるP2MP LSPが通る各ノード（PLR: Point of Local Repair）が、当該LSPに対する迂回経路の計算主体となって、当該LSPに接続されている直下のリンク、あるいは、直下のネクストホップルータに障害が発生した場合、該障害後に瞬時に切り替えを行い、該障害から回避し、通信の継続性を確保するための迂回用のP2MP LSPを算出し、設定する.【選択図】  図１
2007074308.tif 000002
【特許請求の範囲】
【請求項１】
マルチキャストMPLSにおけるP2MP LSP（Point to Multipoint Label Switched Path）に対する迂回経路算出設定方法であって、
保護対象であるP2MP LSPが通る各ノード（PLR: Point of Local Repair）が、当該LSPに対する迂回経路の計算主体となって、当該LSPに接続されている直下のリンク、あるいは、直下のネクストホップルータに障害が発生した場合、該障害後に瞬時に切り替えを行い、該障害から回避し、通信の継続性を確保するための迂回用のP2MP LSPを算出し、設定する
ことを特徴とする迂回経路算出設定方法。
【請求項２】
前記PLRは、
前記LSP上の当該PLR直下のネクストホップルータを迂回対象ノードと決定するステップと、
迂回経路計算のために、当該PLRに接続されている直下のリンクと、迂回対象ノードと、該迂回対象ノードに接続されているリンク全てを当該PLRで保持している経路計算用のネットワーク図から削除して、迂回経路計算用ネットワーク図を作成するステップと、
前記経路計算用ネットワーク図から、前記迂回対象ノード配下に存在する全Egressノードに到達可能となる元のP2MP LSPのツリーの一部である１つもしくは複数のサブツリーのルートとなるノードうち、最も上流となる１つもしくは複数のノード（以下マージポイントと記す）の候補を決定するステップと、
当該PLRを起点とし、１つもしくは複数のマージポイント候補を経由して迂回対象ノード配下に存在する全Egressノードに対して、迂回用のP2MP LSPをCSPFアルゴリズムにより算出するステップと、
算出された迂回用のP2MP LSPをRSVP-TEの拡張Pathメッセージを利用して設定するステップと、
を行う請求項１記載の迂回経路算出設定方法。
【請求項３】
前記PLRにおいて、
前記迂回経路計算用ネットワーク図から、前記迂回対象ノード配下に存在する全Egressノードに到達可能となる元のP2MP LSPのツリーの一部である１つもしくは複数のサブツリーのルートとなるノードのうち、最も上流となる１つもしくは複数のマージポイント候補を経由して、該迂回対象ノード配下に存在する全Egressノードに対する迂回用のP2MP LSPのパス計算を行った結果、算出されたパスがマージポイント候補に到達する前に、当該対象ノード配下のP2MP LSPのサブツリーが通るノード（以下、合流ノードと記す）と合流し、元のP2MP LSPにおける該合流ポイント配下のEgressノードと、対象ノード配下のEgressノードが同一である場合は、合流ノードを新たなマージポイント候補と決定し、再度当該PLRから１つもしくは複数の新たなマージポイント候補を経由して迂回対象ノード配下に存在する全Egressノードに対して、迂回用のP2MP LSPを算出するステップと、
算出された迂回用のP2MP LSPをRSVP-TEの拡張Pathメッセージを利用して設定するステップと、
を行う請求項２記載の迂回経路算出設定方法。
【請求項４】
前記PLRは、
前記迂回経路計算用ネットワーク図から、前記迂回対象ノード配下に存在する全Egressノードに到達可能となる元のP2MP LSPのツリーの一部である１つまたは複数のサブツリーのルートとなるノードのうち、最も上流となる１つもしくは複数のマージポイント候補を経由して、該迂回対象ノード配下に存在する全Egressノードに対する迂回用のP2MP LSPのパス計算を行った結果、算出されたパスがマージポイント候補に到達する前に、当該対象ノード配下のP2MP LSPのサブツリーが通る合流ノードと合流し、元のP2MP LSPにおける合流ノード配下のEgressノードと、該対象ノード配下のEgressノードが同一でない場合は、最も上流となる１つもしくは複数のマージポイント候補を経由して該迂回対象ノード配下に存在する全Egressノードに対する迂回用のP2MP LSPのパス計算を継続するステップを、
前記マージポイント候補に到達する、あるいは、前記P2MP LSPにおける合流ノード配下のEgressノードと、対象ノード配下のEgressノードが同一となる新たな合流ノードを発見し、新たなマージポイント候補を発見するまで繰り返す、
請求項２または、３記載の迂回経路算出設定方法。
【請求項５】
前記PLRは、
前記迂回経路計算用ネットワーク図から、前記迂回対象ノード配下に存在する全Egressノードに到達可能となる元のP2MP LSPのツリーの一部である１つもしくは複数のサブツリーのルートなるノードうち、最も上流となる１つもしくは複数のマージポイント候補を経由して迂回対象ノード配下に存在する全Egressノードに対する迂回用のP2MP LSPのパス計算を行った結果、該マージポイントまで到達できるパスが得られなかった場合に、当該PLRから当該対象ノードに対する迂回経路算出不可と判断し、処理を終了するステップを行う、
請求項２乃至４記載の迂回経路算出設定方法。
【請求項６】
前記PLRにおいて、複数の迂回対象ノードが存在する場合には、該迂回対象ノード毎に独立に請求項２乃至５のステップを行う、
請求項２乃至５記載の迂回経路算出設定方法。
【請求項７】
マルチキャストMPLSにおけるP2MP LSP（Point to Multipoint Label Switched Path）に対する迂回経路算出設定装置であって、
経路計算用のネットワーク図及び迂回経路計算用のネットワーク図を保持する記憶手段と、
請求項２乃至６記載の、保護対象であるP2MP LSPが通る各ノード（PLR: Point of Local Repair）が、行う各ステップを実行する手段と、を有することを特徴とする迂回経路算出設定装置。
【請求項８】
保護対象であるP2MP LSPが通る各ノードとして利用されるコンピュータに、
請求項２乃至６記載の迂回経路算出設定方法のステップを実行させることを特徴とする迂回経路算出設定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、迂回経路算出設定方法及び装置及びプログラムに係り、特に、マルチキャストMPLS(Multi Protocol Label Switching)ネットワークにおいて、ポイントツーマルチポイント（以下、P2MPと記す）Label Switched Path（以下、LSPと記す）の迂回経路の計算及び設定を実現するための技術であり、ネットワーク内のリンク／ノード障害から高速に迂回し、通信の信頼性を確保するための迂回経路算出設定方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
従来のMPLSにおけるLSPの迂回経路設定方式の一つとして、one-to-oneバックアップ技術がある。one-to-oneバックアップ技術とは、保護対象とするLSP(以下、Protected LSPと記す)が通過する各LSR(Label Switching Routing)において、下流のリンク／ノード障害を回避するために、Protected LSP毎に迂回経路（Detour LSP）を当該Protected LSPのEgressノードまで計算し、RSVP-TEを拡張したPath Messageを用いて設定するというものである（例えば、非特許文献１参照）。
【０００３】
また、各LSRが計算主体となってDetour LSPを計算し、このProtected LSP上でのDetour LSPの計算と設定を担うノードをPLR(Point of Local Repair)と呼ぶ。また、PLRから計算、設定されたDetour LSPが当該Protected LSPと合流するノードをMP(マージポイント)と呼ぶ。
【０００４】
一方、従来のMPLS技術をマルチキャスト拡張したマルチキャストMPLSにおいては、複数のEgressノードに対して、一つのP2MP LSPを設定することができ、同一のデータを複数のEgressノードに対して同報する際に、ネットワーク帯域が効率的に利用できるなど、規模拡張性に優れている（例えば、非特許文献２参照）。
【非特許文献１】P.Pan, Swallow, A. Atlas:”Fast Reroute Extensions to RSVP-TE for LSP Tunnels”, RFC4090
【非特許文献２】R. Aggarwal , D. Papadimitriou, S. Yasukawa:”Extensions to RSVP-TE for Point to Multipoint TE LSPs”,  draft-ietf-mpls-rsvp-te-p2mp-02.txt
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、従来のユニキャストのポイントツーポイント（P2P）LSPと比べて、P2MP LSPは複数のEgressノードが収容されるため、当該LSPが経由するリンク／ノードに障害が発生すると、障害ポイント配下のユーザ（Egressノード収容ユーザ）は全て影響を受ける。そのため、P2MP LSPに対する信頼性確保のための迂回経路設定方法は重要である。
【０００６】
但し、これまでのところマルチキャストMPLSにおけるP2MP LSPに対する迂回経路設定方法については検討されておらず、有効な手法はまだ存在しないという課題がある。ただ、P2MP LSPの迂回経路設定に従来のP2P LSPでの迂回経路設定方法を踏襲し、各PLRから全EgressノードまでP2PにてDetour LSPを設定する方法が考えられる。しかし、この手法では、各PLRが保持すべきLSP状態数が増大するといった点や、障害発生時に迂回経路に切り替わった後に、使用帯域が増大するといった問題がある。
【０００７】
本発明は、上記の点に鑑みなされたもので、マルチキャストMPLSネットワークにおいて、ポイントツーマルチポイント(P2MP)LSPに対する効率的な迂回経路設定を実現することができ、ネットワーク内のリンク／ノード障害から高速に迂回し、通信の信頼性を確保することが可能な迂回経路算出設定方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明（請求項１）は、マルチキャストMPLSにおけるP2MP LSPに対する迂回経路算出設定方法であって、
保護対象であるP2MP LSPが通る各ノード（PLR: Point of Local Repair）が、当該LSPに対する迂回経路の計算主体となって、当該LSPに接続されている直下のリンク、あるいは、直下のネクストホップルータに障害が発生した場合、該障害後に瞬時に切り替えを行い、該障害から回避し、通信の継続性を確保するための迂回用のP2MP LSPを算出し、設定する。
【０００９】
図１は、本発明の原理を説明するための図である。
【００１０】
本発明（請求項２）は、PLRにおいて、
LSP上の当該PLR直下のネクストホップルータを迂回対象ノードと決定するステップと、
迂回経路計算のために、当該PLRに接続されている直下のリンクと、迂回対象ノードと、該迂回対象ノードに接続されているリンク全てを当該PLRで保持している経路計算用のネットワーク図から削除して、迂回経路計算用ネットワーク図を作成するステップと、
経路計算用ネットワーク図から、迂回対象ノード配下に存在する全Egressノードに到達可能となる元のP2MP LSPのツリーの一部である１つもしくは複数のサブツリーのルートとなるノードうち、最も上流となる１つもしくは複数のノード（以下マージポイントと記す）の候補を決定するステップと、
当該PLRを起点とし、１つもしくは複数のマージポイント候補を経由して迂回対象ノード配下に存在する全Egressノードに対して、迂回用のP2MP LSPをCSPFアルゴリズムにより算出するステップと、
算出された迂回用のP2MP LSPをRSVP-TEの拡張Pathメッセージを利用して設定するステップと、を行う。
【００１１】
また、本発明（請求項３）は、請求項２の迂回経路算出設定方法であって、
PLRにおいて、
迂回経路計算用ネットワーク図から、迂回対象ノード配下に存在する全Egressノードに到達可能となる元のP2MP LSPのツリーの一部である１つもしくは複数のサブツリーのルートとなるノードのうち、最も上流となる１つもしくは複数のマージポイント候補を経由して迂回対象ノード配下に存在する全Egressノードに対する迂回用のP2MP LSPのパス計算を行った結果、算出されたパスがマージポイント候補に到達する前に、当該対象ノード配下のP2MP LSPのサブツリーが通るノード（以下、合流ノードと記す）と合流し、元のP2MP LSPにおける該合流ポイント配下のEgressノードと、対象ノード配下のEgressノードが同一である場合は、合流ノードを新たなマージポイント候補と決定し、再度当該PLRから１つもしくは複数の新たなマージポイント候補を経由して迂回対象ノード配下に存在する全Egressノードに対して、迂回用のP2MP LSPを算出するステップと、
算出された迂回用のP2MP LSPをRSVP-TEの拡張Pathメッセージを利用して設定するステップと、を行う。
【００１２】
また、本発明（請求項４）は、請求項２または、３の迂回経路算出設定方法であって、
PLRにおいて、
迂回経路計算用ネットワーク図から、迂回対象ノード配下に存在する全Egressノードに到達可能となる元のP2MP LSPのツリーの一部である１つまたは複数のサブツリーのルートとなるノードのうち、最も上流となる１つもしくは複数のマージポイント候補を経由して迂回対象ノード配下に存在する全Egressノードに対する迂回用のP2MP LSPのパス計算を行った結果、算出されたパスがマージポイント候補に到達する前に、当該対象ノード配下のP2MP LSPのサブツリーが通る合流ノードと合流し、元のP2MP LSPにおける合流ノード配下のEgressノードと、該対象ノード配下のEgressノードが同一でない場合は、最も上流となる１つもしくは複数のマージポイント候補を経由して該迂回対象ノード配下に存在する全Egressノードに対する迂回用のP2MP LSPのパス計算を継続するステップを、
マージポイント候補に到達する、あるいは、P2MP LSPにおける合流ノード配下のEgressノードと、対象ノード配下のEgressノードが同一となる新たな合流ノードを発見し、新たなマージポイント候補を発見するまで繰り返す。
【００１３】
また、本発明（請求項５）は、請求項２乃至４の迂回経路算出設定方法であって、
PLRは、
迂回経路計算用ネットワーク図から、迂回対象ノード配下に存在する全Egressノードに到達可能となる元のP2MP LSPのツリーの一部である１つもしくは複数のサブツリーのルートなるノードうち、最も上流となる１つもしくは複数のマージポイント候補を経由して迂回対象ノード配下に存在する全Egressノードに対する迂回用のP2MP LSPのパス計算を行った結果、該マージポイントまで到達できるパスが得られなかった場合に、当該PLRから当該対象ノードに対する迂回経路算出不可と判断し、処理を終了するステップを行う。
【００１４】
また、本発明（請求項６）は、請求項２乃至の迂回経路算出設定方法であって、
PLRにおいて、複数の迂回対象ノードが存在する場合には、該迂回対象ノード毎に独立に請求項２乃至５のステップを行う。
【００１５】
本発明（請求項７）は、マルチキャストMPLSにおけるP2MP LSP（Point to Multipoint Label Switched Path）に対する迂回経路算出設定装置であって、
経路計算用のネットワーク図及び迂回経路計算用のネットワーク図を保持する記憶手段と、
請求項２乃至６記載の、保護対象であるP2MP LSPが通る各ノード（PLR: Point of Local Repair）が、行う各ステップを実行する手段と、を有する。
【００１６】
本発明（請求項８）は、保護対象であるP2MP LSPが通る各ノードとして利用されるコンピュータに、請求項２乃至６記載の迂回経路算出設定方法のステップを実行させるプログラムである。
【発明の効果】
【００１７】
上記のように本発明によれば、マルチキャストMPLSネットワークにおいて、P2MPLSPに対する効率的な迂回経路設定を実現することができると共に、ネットワーク内のリンク／ノード障害から高速に迂回し、通信の信頼性を確保することができる。
【発明を実施するための最良の形態】
【００１８】
以下、図面と共に本発明の実施の形態を説明する。
【００１９】
［第１の実施の形態］
図２は、本発明の第１の実施の形態におけるネットワーク構成図とP2MP LSPパスを示し、図３は、本発明の第１の実施の形態におけるノード１（PLR）のDetour LSP計算のフローチャートを示し、図４は、本発明の第１の実施の形態における迂回経路計算用ネットワーク図を示し、図５は、本発明の第１の実施の形態における迂回経路設定例（PLR:ノード１）を示し、図６は、本発明の第１の実施の形態における迂回経路設定シーケンスチャートである。以下、これらの図を用いて説明する。
【００２０】
同図に示すネットワーク構成は、全１６台のノードから構成され、ノード１をIngressノードとし、ノード１３，１４，１５，１６をEgressノード（それぞれEgress１〜４と記載）とするP2MP LSPが設定されている。なお、このP2MP LSPをProtected LSPとする。ここでは、全ノードはマルチキャストMPLS対応のノードであるとし、LSPを分岐できるブランチノードとなり得るものとする。これを元に、Detour P2MP LSPの設定手順を説明する。
【００２１】
Protected P2MP LSP上における各PLRにてDetour LSPを計算し、設定する。以下では、PLRがノード１の場合の例を記載する。
【００２２】
なお、以下の説明は、図３に示すフローチャートと対応して記載しており、ステップｎは図３に記載の処理番号とする。
【００２３】
ネットワーク内の各ノードはOSPF-TＥ等のプロトコルによって、図２に示すようなネットワーク構成図は既知であるとし（ステップ１０１）、P2MP LSP上のノードは、マルチキャストMPLSプロトコルにおけるERO(Explicit Route Object)やRRO(Record Route Object)により、P2MP LSPがどの経路を通っているかは既知であるとする（ステップ１０２）。
【００２４】
まず、ノード１は、Protected LSPが経由する直下のノードを迂回対象ノードと決定すると共に（ステップ１０３）、当該ノードに接続されているリンク全てを上記ネットワーク構成図から削除し、図４に示すような迂回経路計算用のネットワーク図を新たに作成する（ステップ１０４）。この後、当該ネットワーク図を用いて、迂回対象ノード配下に存在する全Egressノードを特定し（ステップ１０５）、当該全ノードに到達可能となる、元のP2MP LSPのツリーの一部である一つもしくは複数のサブツリーのルートとなるノードうち、最も上流となるノードの候補を決定し、これをマージポイント候補とする（ステップ１０６）。本実施の形態では対象ノードがノード３であり、ノード３の配下の全Egressノードとは、ノード１３，１４，１５，１６であるので、これら４つのノードに全て到達可能な元のP2MP LSPのツリーのサブツリーの最上流ノードは、ノード５となるため、ノード５をマージポイント候補として設定する。
【００２５】
次に、PLR(ノード１)からノード５を経由して全Egressノードに到達可能となるようなDetour P2MP LSPの計算をCSPF(Constrained Shortest Path First)アルゴリズムにより行う（ステップ１０７）。なお、本発明では、用いるCSPFアルゴリズムを限定するものではなく、いかなるアルゴリズムを用いてもよい。ここで、ノード５までは最小ホップ数で接続するといったアルゴリズムを利用した場合、図４中の点線で示すようにノード１，ノード２，ノード５経由のDetour P2MP LSPが算出され、PLRにて当該Detour LSPの設定がRSVP-TEの拡張Path Messageを用いて行われる（ステップ１０８）。その後、マージポイント候補であるノード５において、保護対象のProtected P2MP LSP（図５の太線で示す）とDetour P2MP LSP（図５の点線で示す）がマージされ、PLRから対象ノードを迂回するDetour P2MP LSPの設定が完了する。以上の操作を、Protected LSP上の各PLRがそれぞれ独立に行う。
【００２６】
ここで、ステップ１０８のPLRにて、Detour LSPの設定を行う際のシーケンスを、図６を用いて説明する。
【００２７】
PLRにてDetour LSPの算出は終了しているものとする（ステップ２０１）。ここで算出されたDetour LSPは、ノードＥを経由するLSPであって、PLRから見て
ノード１−２−５−６−９−１３、
ノード１−２−５−６−９−１４、
ノード１−２−５−６−１０−１５、
ノード１−２−５−８−１２−１６
という経路になる。ここで、PLRにてP2MP LSPを設定するRSVP-TEの拡張Pathパスメッセージ（従来の非特許文献１，２による技術を用いて作成）に上記経路を全て挿入し、更に元のLSPのDetour LSP設定用としてDetourオブジェクトを挿入した拡張Pathメッセージを作成し、ノード２に送出する（ステップ２０２）。
【００２８】
その後、ノード２は受信したPathメッセージから次に転送すべきルータを決定し、自ノードからのPathメッセージをノード５に対して送出する（ステップ２０３）。なお、ノード５以降のPath メッセージについては、元のProtected LSPを設定した際に送出されていたPath Messageと同一となりノード５において元のProtected LSPとマージし、それ以降のDetour LSPを設定するためのPathメッセージ(detour)は改めて送出されない（そのためノード５から送出されるPathメッセージについては点線で示した）。以上の手順によりDetour LSPが設定される。
【００２９】
なお、本実施の形態では下流ノードから送出されるRSVP-TE RESVメッセージについては省略してある。
【００３０】
［第２の実施の形態］
本実施の形態では、対象ノードが複数の場合について説明する。
【００３１】
図７は、本発明の第２の実施の形態におけるネットワーク構成図とP2MP LSPパスを示し、図８は、本発明の第２の実施の形態における迂回経路計算用ネットワーク図を示し、
図９は、本発明の第２の実施の形態における迂回経路設定例（PLR:ノード５、対象ノード６）を示し、図１０は、本発明の第２の実施の形態における迂回経路計算用ネットワーク図を示し、図１１は、本発明の第２の実施の形態における迂回経路設定例（PLR:ノード５、対象ノード８を示し、図１２は、本発明の第２の実施の形態における迂回経路設定例（PLR:ノード５）を示す。
【００３２】
本実施の形態では、図７においてノード５をPLRとした場合、対象ノードは、ノード６とノード８の２つとなる。PLRはこれら２つの対象ノードに対して独立に第１の実施の形態に示したのと同様の操作を行う。
【００３３】
以下に、対象ノード６の場合の動作例を示す。
【００３４】
ノード５は、迂回対象ノード６に接続されるリンク全てを保持しているネットワーク構成図から削除し、図８に示すような迂回経路計算用のネットワーク図を新たに作成する。この後、当該ネットワーク図を用いて、迂回対象ノード配下に存在する全Egressノードに到達可能となる元のP2MP LSPのツリーの一部である１つもしくは複数のサブツリーのルートとなるノードのうち、最も上流となるノードの候補を決定し、これをマージポイント候補とする。本実施の形態では、対象ノードがノード６であり、ノード６配下の全Egressノードとは、ノード１３，１４，１５となるので、これら３つのノードに全て到達可能な元のP2MP LSPのツリーのサブツリーの最上流ノードは、ノード９とノード１０となるため、これら２つのノード９とノード１０をマージポイント候補として設定する。
【００３５】
次に、PLR(ノード５)からノード９及びノード１０を経由して全Egressノードに到達可能となるようなDetour P2MP LSPの計算をCSPFアルゴリズムにより行う。なお、本発明では、用いるCSPFアルゴリズムを限定するものではなく、いかなるアルゴリズムを用いてもよい。ここで、PLRからノード９及びノード１０まではそれぞれ最小ホップ数で接続するといったアルゴリズムを利用した場合、図９中の点線で示すように、ノード５・ノード２・ノード９経由と、ノード５・ノード７・ノード１０経由のDetour P2MP LSPが設定され、PLRとマージポイント候補が接続される。その後、マージポイント候補であるノード９及びノード１０において、保護対象のProtected P2MP LSP（図９中の太線で示す）とDetour P2MP LSP（図９中の点線で示す）がマージされ、PLRから対象ノードを迂回するDetour P2MP LSPの設定が完了する。ここまでが対象ノード６に対する動作である。
【００３６】
次に、対象ノード８に対する動作例を示す。
【００３７】
この場合も同様に、ノード５は、迂回対象ノード８に接続されるリンク全てを保持しているネットワーク構成図から削除し、図１０に示すような迂回経路計算用のネットワーク図を新たに作成する。この後、当該ネットワーク図を用いて、迂回対象ノードは以下に存在する全Egressノードに到達可能となる、元のP2MP LSPのツリーの一部である一つもしくは複数のサブツリーのルートとなるノードのうち、最も上流となるノードの候補を決定し、これをマージポイント候補とする。本実施の形態では、対象ノードがノード８であり、ノード８配下の全Egressノードとは、ノード１６となるので、このノード１６に到達可能な元のP2MP LSPのツリーのサブツリーの最上流ノードは、ノード１２となるため、ノード１２をマージポイント候補として設定する。
【００３８】
次に、PLR（ノード５）からノード１２を経由して全Egressノードに到達可能となるようなDetour P2MP LSPの計算をCFPFアルゴリズムにより行う。なお、本発明では、用いるCFPFアルゴリズムを限定するものではなく、いかなるアルゴリズムを用いてもよい。ここで、PLRからノード１２までを最小ホップ数で接続するといったアルゴリズムを利用した場合、図１１中の点線で示すように、ノード５・ノード７・ノード１２経由のDetour P2MP LSPが設定され、PLRとマージポイント候補が接続される。その後、マージポイント候補であるノード１２において、保護対象のProtected P2MP LSP（図１１の太線で示す）とDetour P2MP LSP（図１１の点線で示す）がマージされ、PLRから対象ノードを迂回するDetour P2MP LSPの設定が完了する。ここまでが対象ノード８に対する動作である。
【００３９】
なお、本実施の形態で記載した対象ノード６に対するDetour P2MP LSPと対象ノード８に対するDetour P2MP LSPとは独立のものとして扱うため、PLRがノード５における最終的なDetour P2MP LSPは図１２に示す形となる。
【００４０】
［第３の実施の形態］
図１３は、本発明の第３の実施の形態におけるネットワーク構成図とP2MP LSPパスを示し、図１４は、本発明の第３の実施の形態における迂回経路計算用ネットワークとマージポイント候補探索図を示し、図１５は、本発明の第３の実施の形態における迂回経路設定例（PLR:ノード１）を示し、図１６は、本発明の第３の実施の形態におけるノード１のDetour LSP計算フローチャートである。
【００４１】
本実施の形態を、上記の図１３から図１６を用いて説明する。
【００４２】
本実施の形態のネットワーク構成は、図１３に示すように、全１２台のノードから構成され、ノード１をIngressノードとし、ノード１０，１１，１２をEgressノード（それぞれEgress１からEgress３と記載）とするP2MP LSPが設定されている。なお、このP2MP LSPをProtected LSPとする。また、PLRがノード１の場合を記載する。この場合、迂回対象ノードはノード２となる。なお、以下の説明は、図１６に示すフローチャートと対応しており、処理ｎは図１６に記載のステップ番号と対応する。
【００４３】
ノード１は、第１の実施の形態に記載した手順に従って、Protected LSPが経由する直下のノードを迂回対象ノードと決定すると共に、当該ノードに接続されるリンク全てを上記のネットワーク構成図から削除し、図１４に示すような迂回経路計算用のネットワーク図を新たに作成する（ステップ３０１〜ステップ３０４）。その後、当該ネットワーク図を用いて、迂回対象ノード配下に存在する全Egressノードに到達可能となる、元のP2MP LSPのツリーの一部である一つもしくは複数のサブツリーのルートとなるノードのうち、最も上流となるノードの候補を決定し、これをマージポイント候補とする。本実施の形態では、対象ノードがノード２であり、ノード２配下の全Egressノードとは、ノード１０、１１，１２であるので、これら３つのノードに全て到達可能な元のP2MP LSPのツリーのサブツリー最上流ノードは、ノード３となるため、ノード３をマージポイント候補として設定する（ステップ３０５、ステップ３０６）。
【００４４】
次に、PLR(ノード１)からノード３を経由して全Egressノードに到達可能となるようなDetour P2MP LSPの計算をCSPFアルゴリズムにより行う。なお、本発明では、用いるCSPFアルゴリズムを限定するものではなく、いかなるアルゴリズムを用いてもよい。ここで、PLRからノード３までを最小ホップ数で接続するといったアルゴリズムを利用した場合、図１４中の点線で示すようにノード１・ノード７・ノード８・ノード４．ノード３経由のDetour P2MP LSPが計算される（ステップ３０７）。しかし、ノード１・ノード７・ノード８・ノード４の段階で、Protected P2MP LSP上のノードと合流する合流ノードが発見され（ステップ３０８）、かつ、当該ノード４、配下の全Egressノードと保護対象ノード配下のEgressノードが一致するため（ステップ３０９）、図１５に示すように、当該ノード４を新たなマージポイント候補として設定する。この後、PLR(ノード１)からノード４を経由して全Egressノードに到達可能となるようなDetour P2MP LSPの計算を再度実行し、ノード１・ノード７・ノード８・ノード４経由のDetour P2MP LSPが計算され（ステップ３１０）、マージポイント候補であるノード４において、保護対象のProtected P2MP LSP(図１５の太線で示す)とDetour P2MP LSP(図１５の点線で示す)がマージされ、PLRから対象ノードを迂回するDetour P2MP LSPの算出が完了し、第１の実施の形態で示した設定方法と同様の方法にて、Detour LSPが設定される（ステップ３１１）。
【００４５】
［第４の実施の形態］
図１７は、本発明の第４の実施の形態におけるネットワーク構成図とP2MP LSPパスを示し、図１８は、本発明の第４の実施の形態における迂回経路計算用ネットワーク図とマージポイント候補探索図を示し、図１９は、本発明の第４の実施の形態における迂回経路設定例（PLR:ノード１）を示し、図２０は、本発明の第４の実施の形態におけるノード１（PLR）のDetour LSP計算フローチャートを示す。
【００４６】
本実施の形態を図１７から図２０を用いて説明する。
【００４７】
図１７において、ネットワーク構成は、全１２台のノードから構成され、ノード１をIngressノードとし、ノード１０，１１，１２をEgressノード（それぞれEgress１から３と記載）とするP2MP LSPが設定されている。なお、このP2MP LSPをProtected LSPとする。また、PLRがノード１の場合を記載する。この場合、迂回対象ノードはノード２となる。なお、以下の説明は、図２０に示すフローチャートと対応させて記載しており、処理nは図２０のステップ番号に対応する。
【００４８】
ノード１は、第１の実施の形態に記載した手順に従って、Protected LSPが経由する直下のノードを迂回対象ノードと決定すると共に、当該ノードに接続されるリンク全てを上記ネットワーク構成図（図１７）から削除し、新たに図１８に示すような迂回経路計算用のネットワーク図を新たに作成する（ステップ４０１からステップ４０４）。この後、図１８に示す当該ネットワーク図を用いて、迂回対象ノード配下に存在する全Egressノードに到達可能となる、元のP2MP LSPのツリーの一部である１つもしくは複数のサブツリーのルートとなるノードのうち、最も上流となるノードの候補を決定し、これをマージポイント候補とする。本実施の形態では、対象ノードがノード２であり、ノード２配下の全Egressノードとは、ノード１０・１１・１２であるので、これら３つのノードに全て到達可能な元のP2MP LSPのツリーのサブツリーの最上流ノードはノード３となるため、ノード３をマージポイント候補として設定する（ステップ４０５、ステップ４０６）。
【００４９】
次に、PLR（ノード１）からノード３を経由して全Egressノードに到達可能となるようなDetour P2MP LSPの計算をCSPFアルゴリズムにより行う。なお、本発明では、CSPFアルゴリズムを限定するものではなく、いかなるアルゴリズムを用いてもよい。ここで、PLRからノード３までを最小ホップ数で接続するといったアルゴリズムを利用した場合、図１８中の点線で示すように、ノード１・ノード７・ノード８・ノード９・ノード６・ノード４・ノード３経由のDetour P2MP LSPが計算される（ステップ４０７）。しかし、ノード１・ノード７・ノード８・ノード９・ノード６の段階でProtected P2MP LSP上のノード（ノード６）と合流する合流ノードが発見される（ステップ４０８）。但し、この場合、当該ノード６配下の全Egressノード（ノード１１とノード１２）と保護対象ノード配下のEgressノード（ノード１０とノード１１とノード１２）が一致しないため、ノード６は、新たなマージポイント候補としては選択されず、次の検索ステップに移る。
【００５０】
次の合流ノードは、ノード１・ノード７・ノード８・ノード９・ノード６・ノード４となる場合のノード４となり（ステップ４０９）、この場合は当該ノード４配下のEgressノード（ノード１０とノード１１とノード１２）と保護対象ノード配下のEgressノード（ノード１０とノード１１とノード１２）が一致するため、ノード４を新たなマージポイント候補として選択される（ステップ４１０）。
【００５１】
この後、図１９に示すように、PLR(ノード１)からノード４を経由して全Egressノードに到達可能となるようなDetour P2MP LSPの計算を再度実行し、ノード１・ノード７・ノード８・ノード９・ノード６・ノード４経由のDetour P2MP LSPが計算され、（ステップ４１１）、マージポイント候補であるノード４において、保護対象のProtected P2MP LSP（図１９の太線で示す）とDetour P2MP LSP（図１９の点線で示す）がマージされ、PLRから対象ノードを迂回するDetour P2MP LSPの設定が完了し、第１の実施の形態に示した設定方法と同様の方法にてDetour LSPが設定される（ステップ４１２）。
【００５２】
［第５の実施の形態］
図２１は、本発明の第５の実施の形態におけるネットワーク構成図とP2MP LSPパスを示し、図２２は、本発明の第５の実施の形態における迂回経路計算用ネットワーク図を示し、図２３は、本発明の第５の実施の形態におけるノード１（PLR）のDetour LSP計算フローチャートを示す。
【００５３】
本実施の形態を、図２１から図２３を用いて説明する。
【００５４】
図２１において、ネットワーク構成は、全９台のノードから構成され、ノード１をIngressノードとし、ノード７，８，９をEgressノード（それぞれEgress１から３と記載）とするP2MP LSPが設定されている。なお、このP2MP LSPをProtected LSPとする。また、PLRがノード１の場合を記載する。この場合、迂回対象ノードはノード２となる。なお、以下の説明は図２３に示すフローチャートと対応して記載しており、処理nは、図２３のステップ番号と対応する。
【００５５】
ノード１は、第１の実施の形態に記載した手順に従って、Protected LSPが経由する直下のノードを迂回対象ノードと決定すると共に、当該ノードに接続されるリンク全てを上記ネットワーク構成図（図２１）から削除し、図２２に示すような迂回経路計算用のネットワーク図を新たに作成する（ステップ５０１〜ステップ５０４）。次に、PLRから迂回対象ノード配下に存在する全Egressノードに到達可能となる元のP2MP LSPのツリーの一部である１つもしくは複数のサブツリーのルートはノード３であり（ステップ５０５、ステップ５０６）、ノード３に到達する経路計算を行おうとするが（ステップ５０７）、その経路がないため計算不可となる。そのため、迂回経路算出不可と判定し、処理を終了する（ステップ５０８）。
【００５６】
［第６の実施の形態］
図２４は、本発明の第６の実施の形態におけるルータの構成を示す。
【００５７】
以下では、PLRの構成を示している。
【００５８】
同図に示すルータ（ノード）１００は、迂回経路計算部１１０と一般経路計算部１２０及び物理ＩＦ１３０，１４０を有する。迂回経路計算部１１０は、迂回経路算出部１１１、迂回経路設定部１１２、迂回経路計算用ネットワーク構成算出部１１３を有し、一般経路計算部１２０は、ネットワーク構成図記憶部１２１、MPLSパス管理部１２２を有する。
【００５９】
なお、本実施の形態では、特に、迂回経路計算部１１０の構成を主として示しており、その他、ＩＰパケットの転送処理を行う部分やルーティングプロトコル処理などを行う機能については特に明記しておらず、また、本発明を制限するものではない。
【００６０】
迂回経路計算用ネットワーク構成算出部１１３は、一般経路計算部１２０のネットワーク構成図記憶部１２１に所持している一般の経路計算用のネットワーク構成図から情報を取得し、迂回経路計算用のネットワーク構成図を作成する。具体的には、PLRとProtected LSPを通るLSRから対象ノードを決定し、対象ノードとそれに接続されるリンクを全て除いたネットワーク構成図を作成する。
【００６１】
次に、迂回経路算出部１１１において、当該迂回経路計算用ネットワーク図からマージポイント候補の選択や合流ノード有無など、第１〜第５の実施の形態に記載された処理を行い、迂回経路の算出可否を決定する。
【００６２】
次に、迂回経路が算出された後は、当該情報を迂回経路設定部１１１において、Detourオブジェクトを含むPathメッセージを作成し、送出すべきネクストホップルータがつながる物理ＩＦ１３０，１４０に対して送信を行うことで、Detour LSPの設定を行う。
【００６３】
また、本発明は、上記の実施の形態で示したＰＬＲの動作をプログラムとして構築し、ＰＬＲとして利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００６４】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００６５】
本発明は、マルチキャストMPLSネットワークにおいて、P2MP LSPが設定されている状態で、当該LSPが通る通信機器の故障発生時にも通信の継続性を担保することができ、ネットワークの信頼性向上に適用可能である。
【図面の簡単な説明】
【００６６】
【図１】本発明の原理を説明するための図である。
【図２】本発明の第１の実施の形態におけるネットワーク構成図とP2MP LSPパスを示す図である。
【図３】本発明の第１の実施の形態におけるノード(PLR)のDetour LSP計算のフローチャートである。
【図４】本発明の第１の実施の形態における迂回経路計算用ネットワーク図である。
【図５】本発明の第１の実施の形態における迂回経路設定例（PLR:ノード１）である。
【図６】本発明の第１の実施の形態における迂回経路設定シーケンスチャートである。
【図７】本発明の第２の実施の形態におけるネットワーク構成図とP2MP LSPパスを示す図である。
【図８】本発明の第２の実施の形態における迂回経路計算用ネットワーク図である。
【図９】本発明の第２の実施の形態における迂回経路設定例（PLR:ノード５、対象ノード６）である。
【図１０】本発明の第２の実施の形態における迂回経路計算用ネットワーク図である。
【図１１】本発明の第２の実施の形態における迂回経路設定例（PLR:ノード５、対象ノード８）である。
【図１２】本発明の第２の実施の形態における迂回経路設定例（PLR:ノード５）である。
【図１３】本発明の第３の実施の形態におけるネットワーク構成図とP2MP LSPパスを示す図である。
【図１４】本発明の第３の実施の形態における迂回経路計算用ネットワークとマージポイント候補探索図である。
【図１５】本発明の第３の実施の形態における迂回経路設定例(PLR:ノード１)である。
【図１６】本発明の第３の実施の形態におけるノード(PLR)のDetour LSP計算のフローチャートである。
【図１７】本発明の第４の実施の形態におけるネットワーク構成図とP2MP LSPパスを示す図である。
【図１８】本発明の第４の実施の形態における迂回経路計算用ネットワーク図とマージポイント候補探索図である。
【図１９】本発明の第４の実施の形態における迂回経路設定例（PLR:ノード１）である。
【図２０】本発明の第４の実施の形態におけるノード(PLR)のDetour LSP計算のフローチャートである。
【図２１】本発明の第５の実施の形態におけるネットワーク構成図とP2MP LSPパスを示す図である。
【図２２】本発明の第５の実施の形態における迂回経路計算用ネットワーク図である。
【図２３】本発明の第５の実施の形態におけるノード(PLR)のDetour LSP計算のフローチャートである。
【図２４】本発明の第６の実施の形態におけるルータ構成例である。
【符号の説明】
【００６７】
１〜１６  ノード
１００  ノード（ルータ）
１１０  迂回経路計算部
１１１  迂回経路算出部
１１２  迂回経路設定部
１１３  迂回経路計算用ネットワーク構成算出部
１２０  一般経路計算部
１２１  ネットワーク構成図記憶部
１２２  MPLSパス管理部
１３０  物理ＩＦ（インタフェース）
１４０  物理ＩＦ（インタフェース）
【図１】
2007074308.tif 000003
【図２】
2007074308.tif 000004
【図３】
2007074308.tif 000005
【図４】
2007074308.tif 000006
【図５】
2007074308.tif 000007
【図６】
2007074308.tif 000008
【図７】
2007074308.tif 000009
【図８】
2007074308.tif 000010
【図９】
2007074308.tif 000011
【図１０】
2007074308.tif 000012
【図１１】
2007074308.tif 000013
【図１２】
2007074308.tif 000014
【図１３】
2007074308.tif 000015
【図１４】
2007074308.tif 000016
【図１５】
2007074308.tif 000017
【図１６】
2007074308.tif 000018
【図１７】
2007074308.tif 000019
【図１８】
2007074308.tif 000020
【図１９】
2007074308.tif 000021
【図２０】
2007074308.tif 000022
【図２１】
2007074308.tif 000023
【図２２】
2007074308.tif 000024
【図２３】
2007074308.tif 000025
【図２４】
2007074308.tif 000026