(57)【要約】【課題】MPLSとIPが混在したネットワークにおいて、故障が発生した場合の経路を正しく推定する。【解決手段】本発明は、トポロジ情報、LSP情報、トラフィック情報、FEC情報、故障発生復旧位置情報を取得し、LSP情報からRSVP-TEのLSP情報を取得し、LSPを影響を受けるか受けないかで分類し、故障発生または故障復旧による経路の変化を、影響を受けないLSPを先に計算し、影響を受けるLSPを後に計算し、該LSPの新利用経路と情報を格納し、LSP情報からRSVP-TE以外のLSPの情報を取得して計算し、該LSPの新利用経路と状態を格納し、FEC情報からMPLSトラフィックと関連付けられているLSPの新利用経路を取得し、該新利用経路を該MPLSトラフィックの新利用経路として格納し、IPのトラフィック情報から故障発生または故障復旧による経路の変化を計算し、IPトラフィックの新利用経路を格納し、LSP及びトラフィック毎の経路を出力する。【選択図】図１
2007318311.tif 000002
【特許請求の範囲】
【請求項１】
OSPF(Open Shortest Path First)を含むIP(Internet Protocol)ルーティング、及びRSVP-TE(Resource Reservation Signaling Protocol for Traffic Engineering)やLDP(Label Distribution Protocol)が動作するMPLS(Multi Protocol Label Switching)ネットワークに、LSP(Label Switched Path)及び、該LSPにFRR(Fast Reroute)やBackup LSPを含む代替経路が設定され、IP及びMPLSのトラフィック通信が行われている状況下で、あるリンクまたはノードで故障が発生した場合のLSPやトラフィックの経路変化を推定する故障発生時の経路推定方法であって、
情報取得手段が、前記ネットワークの各ノードの接続関係を表したトポロジ情報、及び、該ネットワークに設定されているLSP群の個々の設定情報と利用経路と状態を表すLSP情報及び、通信が行われているトラフィック情報及び、該LSPとMPLSトラフィックを関連付けるFEC(Forwarding Equivalence Class)情報、及び故障発生箇所の位置情報を表す故障発生位置情報を取得し、情報記憶手段に格納する情報取得ステップと、
RSVP-TE-LSP経路計算手段が、前記情報記憶手段を参照し、前記LSP情報のうち、RSVP-TEのLSP情報を取得し、故障発生による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段に格納するRSVP-TE-LSP経路計算ステップと、
LSP経路計算手段が、前記情報記憶手段を参照し、前記LSP情報のうち、RSVP-TE以外のLSP情報を取得し、故障発生による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段に格納するLSP経路計算ステップと、
MPLSトラフィック経路計算手段が、前記情報記憶手段に格納されている前記トラフィック情報のうち、MPLSのトラフィック情報を取得し、前記情報記憶手段に格納されている前記FEC情報を参照し、MPLSトラフィックと関連付けられているLSPの新利用経路を前記計算済みLSP記憶手段から取得し、該新利用経路を該MPLSトラフィックの新利用経路として、計算済みトラフィック記憶手段に格納するMPLSトラフィック経路計算ステップと、
IPトラフィック経路計算手段が、前記情報記憶手段に格納されている前記トラフィック情報のうち、IPのトラフィック情報を取得し、故障発生による経路の変化を計算し、IPトラフィックの新利用経路を計算済みトラフィック記憶手段に格納するＩＰトラフィック経路計算ステップと、
経路出力手段が、前記計算済みLSP記憶手段及び前記計算済みトラフィック記憶手段に格納されたLSP及びトラフィック毎の経路を出力する経路出力ステップと、
を行うことを特徴とする経路推定方法。
【請求項２】
前記RSVP-TE-LSP経路計算ステップにおいて、
LSP分類手段が、前記情報記憶手段の前記RSVP-TEのLSP情報を参照して、故障発生によって影響を受けるLSP群と、故障発生によって影響を受けないLSP群に分類し、前記LSP情報と共に分類毎にLSP分類記憶手段に格納するLSP分類ステップと、
影響なしLSP計算手段が、前記LSP分類記憶手段から、前記故障発生によって影響を受けないLSP群を取得し、該LSP群を前記LSP情報と共に計算済みLSP記憶手段に格納する影響なしLSP計算ステップと、
影響ありLSP計算手段が、前記LSP分類記憶手段から、前記故障発生によって影響を受けるLSP群のうち、前記計算済みLSP記憶手段を参照してまだ計算済みとなっていないLSPを１つ取得し、該LSPのLSP情報と前記故障発生位置情報を参照し、新利用経路と状態を計算し、該LSPを新しいLSP情報と共に該計算済みLSP記憶手段に格納する影響ありLSP計算ステップと、
計算済みとなっていないLSPを取得できなくなるまで、前記影響ありLSP計算ステップを繰り返す、
請求項１記載の経路推定方法。
【請求項３】
ある１つの箇所で故障が発生した場合の経路推定を行う場合に、
前記RSVP-TE-LSP経路計算ステップの前記LSP分類ステップにおいて、
前記故障発生によって影響を受けるLSP群を、更に、前記LSP情報の中の利用経路が故障発生箇所を通過するLSP群と、失敗状態から成功状態に変化する可能性があるLSP群とに分類し、該LSP情報と共に分類毎に前記LSP分類記憶手段に格納し、
前記RSVP-TE-LSP経路計算ステップの前記影響ありLSP計算ステップにおいて、
前記LSP情報の中の利用経路が故障発生箇所を通過するLSP群を先に計算し、失敗状態から成功状態に変化する可能性があるLSP群を後に計算する、
請求項１または２記載の経路推定方法。
【請求項４】
OSPFを含むIPルーティング、及びRSVP-TEやLDPが動作するMPLSネットワークに、LSP及び、該LSPにFRRやBackup LSPを含む代替経路が設定され、IP及びMPLSのトラフィック通信が行われている状況下で、あるリンクまたはノードの故障が復旧した場合のLSPやトラフィックの経路変化を推定する故障復旧時の経路推定方法であって、
情報取得手段が、前記ネットワークの各ノードの接続関係を表したトポロジ情報、及び、該ネットワークに設定されているLSP群の個々の設定情報と利用経路と状態を表すLSP情報及び、通信が行われているトラフィック情報及び、該LSPとMPLSトラフィックを関連付けるFEC情報、及び故障復旧箇所の位置情報を表す故障復旧位置情報を取得し、情報記憶手段に格納する情報取得ステップと、
RSVP-TE-LSP経路計算手段が、前記情報記憶手段を参照し、前記LSP情報のうち、RSVP-TEのLSP情報を取得し、故障復旧による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段に格納するRSVP-TE-LSP経路計算ステップと、
LSP経路計算手段が、前記情報記憶手段に格納されている前記LSP情報のうち、RSVP-TE以外のLSP情報を取得し、故障復旧による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段に格納するLSP経路計算ステップと、
MPLSトラフィック経路計算手段が、前記情報記憶手段に格納されている前記トラフィック情報のうち、MPLSのトラフィック情報を取得し、前記情報記憶手段に格納されている前記FEC情報を参照し、MPLSトラフィックと関連付けられているLSPの新利用経路を前記計算済みLSP記憶手段から取得し、該新利用経路を該MPLSトラフィックの新利用経路として、計算済みトラフィック記憶手段に格納するMPLSトラフィック経路計算ステップと、
IPトラフィック経路計算手段が、前記情報記憶手段に格納されている、前記トラフィック情報のうち、IPのトラフィック情報を取得し、故障復旧による経路の変化を計算し、IPトラフィックの新利用経路を計算済みトラフィック記憶手段に格納するＩＰトラフィック経路計算ステップと、
経路出力手段が、前記計算済みLSP記憶手段及び前記計算済みトラフィック記憶手段に格納されたLSP及びトラフィック毎の経路を出力する経路出力ステップと、
を行うことを特徴とする経路推定方法。
【請求項５】
前記RSVP-TE-LSP経路計算ステップにおいて、
LSP分類手段が、前記情報記憶手段に格納されている前記RSVP-TEのLSP情報を参照して、故障復旧によって影響を受けるLSP群と、故障復旧によって影響を受けないLSP群に分類し、前記LSP情報と共に分類毎にLSP分類記憶手段に格納するLSP分類ステップと、
影響なしLSP計算手段が、前記LSP分類記憶手段から、故障復旧によって影響を受けないLSP群を取得し、該LSP群を前記LSP情報と共に計算済みLSP記憶手段に格納する影響なしLSP計算ステップと、
影響ありLSP計算手段が、前記LSP分類記憶手段の故障復旧によって影響を受けるLSP群から、前記計算済みLSP記憶手段を参照して、まだ計算済みとなっていないLSPを１つ取得し、該LSPのLSP情報と前記故障復旧位置情報を参照し、新利用経路と状態を計算し、該LSPを新しいLSP情報と共に該計算済みLSP記憶手段に格納する影響ありLSP計算ステップと、
計算済みとなっていないLSPを取得できなくなるまで、前記影響ありLSP計算ステップを繰り返す、
請求項４記載の経路推定方法。
【請求項６】
ある１つの箇所で故障が復旧した場合の経路推定を行う場合に、
前記RSVP-TE-LSP経路計算ステップの前記LSP分類ステップにおいて、
前記故障復旧によって影響を受けるLSP群を、更に、前記LSP情報の中の利用経路が故障復旧による変化するLSP群と、失敗状態から成功状態に変化する可能性があるLSP群とに分類し、該LSP情報と共に分類毎に前記LSP分類記憶手段に格納し、
前記RSVP-TE-LSP経路計算ステップの前記影響ありLSP計算ステップにおいて、
前記LSP情報の中の利用経路が故障復旧により変化するLSP群を先に計算し、失敗状態から成功状態に変化する可能性があるLSP群を後に計算する、
請求項４または５記載の経路推定方法。
【請求項７】
OSPFを含むIPルーティング、及びRSVP-TEやLDPが動作するMPLSネットワークに、LSP及び、該LSPにFRRやBackup LSPを含む代替経路が設定され、IP及びMPLSのトラフィック通信が行われている状況下で、あるリンクまたはノードで故障が発生した場合のLSPやトラフィックの経路変化を推定する故障発生時の経路推定装置であって、
前記ネットワークの各ノードの接続関係を表したトポロジ情報、及び、該ネットワークに設定されているLSP群の個々の設定情報と利用経路と状態を表すLSP情報及び、通信が行われているトラフィック情報及び、該LSPとMPLSトラフィックを関連付けるFEC情報、及び故障発生箇所の位置情報を表す故障発生位置情報を取得し、情報記憶手段に格納する情報取得手段と、
前記情報記憶手段を参照し、前記LSP情報のうち、RSVP-TEのLSP情報を取得し、故障発生による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段に格納するRSVP-TE-LSP経路計算手段と、
前記情報記憶手段を参照し、前記LSP情報のうち、RSVP-TE以外のLSP情報を取得し、故障発生による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段に格納するLSP経路計算手段と、
前記情報記憶手段に格納されている前記トラフィック情報のうち、MPLSのトラフィック情報を取得し、前記情報記憶手段に格納されている前記FEC情報を参照し、MPLSトラフィックと関連付けられているLSPの新利用経路を前記計算済みLSP記憶手段から取得し、該新利用経路を該MPLSトラフィックの新利用経路として、計算済みトラフィック記憶手段に格納するMPLSトラフィック経路計算手段と、
前記情報記憶手段に格納されている前記トラフィック情報のうち、IPのトラフィック情報を取得し、故障発生による経路の変化を計算し、IPトラフィックの新利用経路を計算済みトラフィック記憶手段に格納するＩＰトラフィック経路計算手段と、
前記計算済みLSP記憶手段及び前記計算済みトラフィック記憶手段に格納されたLSP及びトラフィック毎の経路を出力する経路出力手段と、
を有することを特徴とする経路推定装置。
【請求項８】
前記RSVP-TE-LSP経路計算手段は、
前記情報記憶手段の前記RSVP-TEのLSP情報を参照して、故障発生によって影響を受けるLSP群と、故障発生によって影響を受けないLSP群に分類し、前記LSP情報と共に分類毎にLSP分類記憶手段に格納するLSP分類手段と、
前記LSP分類記憶手段から、前記故障発生によって影響を受けないLSP群を取得し、該LSP群を前記LSP情報と共に計算済みLSP記憶手段に格納する影響なしLSP計算手段と、
前記LSP分類記憶手段から、前記故障発生によって影響を受けるLSP群のうち、前記計算済みLSP記憶手段を参照してまだ計算済みとなっていないLSPを１つ取得し、該LSPのLSP情報と前記故障発生位置情報を参照し、新利用経路と状態を計算し、該LSPを新しいLSP情報と共に該計算済みLSP記憶手段に格納する処理を計算済みとなっていないLSPを取得できなくなるまで繰り返す影響ありLSP計算手段と、
を有する請求項７記載の経路推定装置。
【請求項９】
ある１つの箇所で故障が発生した場合の経路推定を行う場合に、
前記RSVP-TE-LSP経路計算手段の前記LSP分類手段は、
前記故障発生によって影響を受けるLSP群を、更に、前記LSP情報の中の利用経路が故障発生箇所を通過するLSP群と、失敗状態から成功状態に変化する可能性があるLSP群とに分類し、該LSP情報と共に分類毎に前記LSP分類記憶手段に格納する手段を含み、
前記RSVP-TE-LSP経路計算手段の前記影響ありLSP計算手段は、
前記LSP情報の中の利用経路が故障発生箇所を通過するLSP群を先に計算し、失敗状態から成功状態に変化する可能性があるLSP群を後に計算する手段を含む、
請求項７または８記載の経路推定装置。
【請求項１０】
OSPFを含むIPルーティング、及びRSVP-TEやLDPが動作するMPLSネットワークに、LSP及び、該LSPにFRRやBackup LSPを含む代替経路が設定され、IP及びMPLSのトラフィック通信が行われている状況下で、あるリンクまたはノードの故障が復旧した場合のLSPやトラフィックの経路変化を推定する故障復旧時の経路推定装置であって、
前記ネットワークの各ノードの接続関係を表したトポロジ情報、及び、該ネットワークに設定されているLSP群の個々の設定情報と利用経路と状態を表すLSP情報及び、通信が行われているトラフィック情報及び、該LSPとMPLSトラフィックを関連付けるFEC情報、及び故障復旧箇所の位置情報を表す故障復旧位置情報を取得し、情報記憶手段に格納する情報取得手段と、
前記情報記憶手段を参照し、前記LSP情報のうち、RSVP-TEのLSP情報を取得し、故障復旧による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段に格納するRSVP-TE-LSP経路計算手段と、
前記情報記憶手段に格納されている前記LSP情報のうち、RSVP-TE以外のLSP情報を取得し、故障復旧による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段に格納するLSP経路計算手段と、
前記情報記憶手段に格納されている前記トラフィック情報のうち、MPLSのトラフィック情報を取得し、前記情報記憶手段に格納されている前記FEC情報を参照し、MPLSトラフィックと関連付けられているLSPの新利用経路を前記計算済みLSP記憶手段から取得し、該新利用経路を該MPLSトラフィックの新利用経路として、計算済みトラフィック記憶手段に格納するMPLSトラフィック経路計算手段と、
前記情報記憶手段に格納されている、前記トラフィック情報のうち、IPのトラフィック情報を取得し、故障復旧による経路の変化を計算し、IPトラフィックの新利用経路を計算済みトラフィック記憶手段に格納するＩＰトラフィック経路計算手段と、
前記計算済みLSP記憶手段及び前記計算済みトラフィック記憶手段に格納されたLSP及びトラフィック毎の経路を出力する経路出力手段と、
を有することを特徴とする経路推定装置。
【請求項１１】
前記RSVP-TE-LSP経路計算手段は、
前記情報記憶手段に格納されている前記RSVP-TEのLSP情報を参照して、故障復旧によって影響を受けるLSP群と、故障復旧によって影響を受けないLSP群に分類し、前記LSP情報と共に分類毎にLSP分類記憶手段に格納するLSP分類手段と、
前記LSP分類記憶手段から、故障復旧によって影響を受けないLSP群を取得し、該LSP群を前記LSP情報と共に計算済みLSP記憶手段に格納する影響なしLSP計算手段と、
前記LSP分類記憶手段の故障復旧によって影響を受けるLSP群から、前記計算済みLSP記憶手段を参照して、まだ計算済みとなっていないLSPを１つ取得し、該LSPのLSP情報と前記故障復旧位置情報を参照し、新利用経路と状態を計算し、該LSPを新しいLSP情報と共に該計算済みLSP記憶手段に格納する処理を、計算済みとなっていないLSPを取得できなくなるまで繰り返す影響ありLSP計算手段と、
を有する請求項１０記載の経路推定装置。
【請求項１２】
ある１つの箇所で故障が復旧した場合の経路推定を行う場合に、
前記RSVP-TE-LSP経路計算手段の前記LSP分類手段は、
前記故障復旧によって影響を受けるLSP群を、更に、前記LSP情報の中の利用経路が故障復旧による変化するLSP群と、失敗状態から成功状態に変化する可能性があるLSP群とに分類し、該LSP情報と共に分類毎に前記LSP分類記憶手段に格納する手段を含み、
前記RSVP-TE-LSP経路計算手段の前記影響ありLSP計算手段は、
前記LSP情報の中の利用経路が故障復旧により変化するLSP群を先に計算し、失敗状態から成功状態に変化する可能性があるLSP群を後に計算する手段を含む、
請求項１０または１１記載の経路推定装置。
【請求項１３】
コンピュータに、
請求項７乃至１２記載の経路推定装置の各手段を実行させることを特徴とする経路推定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路推定方法及び装置及びプログラムに係り、特に、OSPF(Open Shortest Path First)などのＩＰ(Internet Protocol)ルーティング、及びRSVP-TE(Resource Reservation Signaling Protocol for Traffic Engineering)やLDP(Label Distribution Protocol)が動作するMPLS(Multi Protocol Label Switching)ネットワークにおいて、LDPやRSVP-TEの様々な設定のLSP(Label Switched Path)が設定され、また、RSVP-TEのLSPにはFRR(Fast Reroute)や、Backup LSPなどのプロテクション方式が設定されている環境下で、IPトラフィックやMPLSトラフィックの経路が、故障発生時または、故障復旧時にどのように変化するかを推定するための経路推定方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
近年、トラフィックエンジニアリングやIP-VPNなどを実現する技術として、MPLSが注目されている。MPLSでは、ラベルの配布により経路が決定されるが、その方法には、LDPのようにIGP(Interior Gateway Protocol)の最短経路に従う方法と、RSVP-TE（例えば、非特許文献１参照）のように経路を明示的に指定し、さらに、ネットワークの帯域を予約する方法がある。
【０００３】
RSVP-TEでは、シグナリングメッセージでExplicit Routeを指定することができ、その指定方法には、全ての通過ノードを指定するStrict指定と、指定されたノード間の経路は、IGPの最短経路に従うLoose指定がある。また、LSP毎に要求帯域を指定し、帯域を確保することができる。したがって、前述で決定した経路上のリンクに要求帯域の空きがない場合は、LSPを設定することができない。
【０００４】
また、RSVP-TEでは、故障発生時にLSPを迂回させるプロテクション方式を設定することができる。プロテクション方式は大きく分けてLocal RepairとGlobal Repairの２つである。Local Repairは、LSPの故障箇所を部分的に、かつ、高速に迂回する方式で、FRR(例えば、非特許文献２参照)とも呼ばれる。図１４に示すように、FRRには、１本のLSPの全てのノード・リンクを保護するようにノードが自動でDetour LSPをCSPFアルゴリズムにより計算し設定するOne-to-one Backupと、特定のリンク・ノードを保護し、複数のトンネルを同時に迂回可能なFacility Backupがある。Facility Backupの迂回路は、Bypass LSPと呼ばれ、ノードがCSPFアルゴリズムにより自動で計算する方法と、LSPと同様、Explicit Routeを指定する方法がある。Detour LSPやBypass LSPにおいて、迂回路の始点となるLSP上のノードをPLR(Point of Local Repair)、迂回路の終点となるLSP上のノードをMP(Merge Point)と呼ぶ。故障復旧時には、自動的に元の経路に戻ることが多い。Global Repairは、LSPのIngress-Egressノード間で新たなLSPに切り替える方式で、予備のLSP（Backup LSP）を予め設定しておき、故障発生がIngressノードに通知されると、Backup LSPに切り替えるという方法がある。この場合、故障復旧時に元のLSPに自動的に切り戻るか、戻らないかは、設定によって決めることが可能である。また、故障箇所がLoose指定区間にある場合、経路の再計算を行うことによって経路が発見されれば、Ingressノードで新経路に切り替わり、Global Repairが実行される。但し、経路の再計算で経路が発見されてもその経路に要求帯域分の空きが無ければ、迂回することはできない。
【０００５】
このように、RSVP-TEでは、LSPやプロテクション方式の設定方法により、故障発生または故障復旧時の経路の変化の仕方は大きく異なり、また、RSVP-TEのLSPを流れるトラフィックもLSPの経路変化に追従して変化する。一方、LDPのLSPやトラフィック、及びIPトラフィックは、経路指定や帯域予約を行わないので、故障発生時にもネットワーク中で正常に存在するリソースを用いて最短経路を計算し、経路が発見されなければその経路で通信を行う。
【０００６】
このように、IPとMPLSが混在するネットワークにおいて、故障発生または故障復旧時の経路の変動を知るためには、複雑な計算を要するが、これを自動的に計算・推定するシミュレータは従来技術として存在する（例えば、非特許文献３参照）。
【非特許文献１】RFC3209 RSVP-TE Extensions to RSVP for LSP Tunnels
【非特許文献２】RFC4090 Fast Reroute Extensions to RSVP-TE for LSP Tunnels
【非特許文献３】「IP/MPLS View」、WANDL社、[online],掲載日不明、[2006年３月７日検索]インターネット  ＜URL:http://www.wandl.com/html/mplsview/MPLSview_new.cfm>
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、RSVP-TEのExplicit Routeや予約帯域、FRR設定やBackup LSP設定など、設定の組み合わせや他のLSPの予約帯域を考慮して経路を推定する方法ではなく、実際のIP/MPLSネットワークの経路変動をシミュレートするには正確性に欠けるものであった。また、故障発生時のプロテクション能力が高いネットワークを構築するためのLSPやプロテクションを設計する際に、故障発生時の経路変化を手動で計算し、推定するのは非常に困難であった。
【０００８】
本発明は、上記の点に鑑みなされたもので、MPLSとIPが混在したネットワークにおいて、故障が発生した場合の経路を正しく推定することが可能な経路推定方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
図１は、本発明の原理を説明するための図である。
【００１０】
本発明（請求項１）は、OSPFを含むIPルーティング、及びRSVP-TEやLDPが動作するMPLSネットワークに、LSP及び、該LSPにFRRやBackup LSPを含む代替経路が設定され、IP及びMPLSのトラフィック通信が行われている状況下で、あるリンクまたはノードで故障が発生した場合のLSPやトラフィックの経路変化を推定する故障発生時の経路推定方法であって、
情報取得手段が、ネットワークの各ノードの接続関係を表したトポロジ情報、及び、該ネットワークに設定されているLSP群の個々の設定情報と利用経路と状態を表すLSP情報及び、通信が行われているトラフィック情報及び、該LSPとMPLSトラフィックを関連付けるFEC情報、及び故障発生箇所の位置情報を表す故障発生位置情報を取得し、情報記憶手段に格納する情報取得ステップ（ステップ１）と、
RSVP-TE-LSP経路計算手段が、情報記憶手段を参照し、LSP情報のうち、RSVP-TEのLSP情報を取得し、故障発生による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段に格納するRSVP-TE-LSP経路計算ステップ（ステップ２）と、
LSP経路計算手段が、情報記憶手段を参照し、LSP情報のうち、RSVP-TE以外のLSP情報を取得し、故障発生による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段に格納するLSP経路計算ステップ（ステップ３）と、
MPLSトラフィック経路計算手段が、情報記憶手段に格納されているトラフィック情報のうち、MPLSのトラフィック情報を取得し、情報記憶手段に格納されているFEC情報を参照し、MPLSトラフィックと関連付けられているLSPの新利用経路を計算済みLSP記憶手段から取得し、該新利用経路を該MPLSトラフィックの新利用経路として、計算済みトラフィック記憶手段に格納するMPLSトラフィック経路計算ステップ（ステップ４）と、
IPトラフィック経路計算手段が、情報記憶手段に格納されているトラフィック情報のうち、IPのトラフィック情報を取得し、故障発生による経路の変化を計算し、IPトラフィックの新利用経路を計算済みトラフィック記憶手段に格納するＩＰトラフィック経路計算ステップ（ステップ５）と、
経路出力手段が、計算済みLSP記憶手段及び計算済みトラフィック記憶手段に格納されたLSP及びトラフィック毎の経路を出力する経路出力ステップ（ステップ６）と、を行う。
【００１１】
また、本発明（請求項２）は、RSVP-TE-LSP経路計算ステップ（ステップ２）において、
LSP分類手段が、情報記憶手段のRSVP-TEのLSP情報を参照して、故障発生によって影響を受けるLSP群と、故障発生によって影響を受けないLSP群に分類し、LSP情報と共に分類毎にLSP分類記憶手段に格納するLSP分類ステップ（ステップ２１）と、
影響なしLSP計算手段が、LSP分類記憶手段から、故障発生によって影響を受けないLSP群を取得し、該LSP群をLSP情報と共に計算済みLSP記憶手段に格納する影響なしLSP計算ステップ（ステップ２２）と、
影響ありLSP計算手段が、LSP分類記憶手段から、故障発生によって影響を受けるLSP群のうち、計算済みLSP記憶手段を参照してまだ計算済みとなっていないLSPを１つ取得し、該LSPのLSP情報と故障発生位置情報を参照し、新利用経路と状態を計算し、該LSPを新しいLSP情報と共に該計算済みLSP記憶手段に格納する影響ありLSP計算ステップ（ステップ２３）と、
計算済みとなっていないLSPを取得できなくなるまで、影響ありLSP計算ステップ（ステップ２３）を繰り返す。
【００１２】
また、本発明（請求項３）は、ある１つの箇所で故障が発生した場合の経路推定を行う場合に、
RSVP-TE-LSP経路計算ステップのLSP分類ステップ（ステップ２１）において、
故障発生によって影響を受けるLSP群を、更に、LSP情報の中の利用経路が故障発生箇所を通過するLSP群と、失敗状態から成功状態に変化する可能性があるLSP群とに分類し、該LSP情報と共に分類毎にLSP分類記憶手段に格納し、
RSVP-TE-LSP経路計算ステップの影響ありLSP計算ステップ（ステップ２３）において、
LSP情報の中の利用経路が故障発生箇所を通過するLSP群を先に計算し、失敗状態から成功状態に変化する可能性があるLSP群を後に計算する。
【００１３】
本発明（請求項４）は、OSPFを含むIPルーティング、及びRSVP-TEやLDPが動作するMPLSネットワークに、LSP及び、該LSPにFRRやBackup LSPを含む代替経路が設定され、IP及びMPLSのトラフィック通信が行われている状況下で、あるリンクまたはノードの故障が復旧した場合のLSPやトラフィックの経路変化を推定する故障復旧時の経路推定方法であって、
情報取得手段が、ネットワークの各ノードの接続関係を表したトポロジ情報、及び、該ネットワークに設定されているLSP群の個々の設定情報と利用経路と状態を表すLSP情報及び、通信が行われているトラフィック情報及び、該LSPとMPLSトラフィックを関連付けるFEC情報、及び故障復旧箇所の位置情報を表す故障復旧位置情報を取得し、情報記憶手段に格納する情報取得ステップ（ステップ１）と、
RSVP-TE-LSP経路計算手段が、情報記憶手段を参照し、LSP情報のうち、RSVP-TEのLSP情報を取得し、故障復旧による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段に格納するRSVP-TE-LSP経路計算ステップ（ステップ２）と、
LSP経路計算手段が、情報記憶手段に格納されているLSP情報のうち、RSVP-TE以外のLSP情報を取得し、故障復旧による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段に格納するLSP経路計算ステップ（ステップ３）と、
MPLSトラフィック経路計算手段が、情報記憶手段に格納されているトラフィック情報のうち、MPLSのトラフィック情報を取得し、情報記憶手段に格納されているFEC情報を参照し、MPLSトラフィックと関連付けられているLSPの新利用経路を計算済みLSP記憶手段から取得し、該新利用経路を該MPLSトラフィックの新利用経路として、計算済みトラフィック記憶手段に格納するMPLSトラフィック経路計算ステップ（ステップ４）と、
IPトラフィック経路計算手段が、情報記憶手段に格納されている、トラフィック情報のうち、IPのトラフィック情報を取得し、故障復旧による経路の変化を計算し、IPトラフィックの新利用経路を計算済みトラフィック記憶手段に格納するＩＰトラフィック経路計算ステップ（ステップ５）と、
経路出力手段が、計算済みLSP記憶手段及び計算済みトラフィック記憶手段に格納されたLSP及びトラフィック毎の経路を出力する経路出力ステップ（ステップ６）と、を行う。
【００１４】
また、本発明（請求項５）は、RSVP-TE-LSP経路計算ステップ（ステップ２）において、
LSP分類手段が、情報記憶手段に格納されているRSVP-TEのLSP情報を参照して、故障復旧によって影響を受けるLSP群と、故障復旧によって影響を受けないLSP群に分類し、LSP情報と共に分類毎にLSP分類記憶手段に格納するLSP分類ステップ（ステップ２１）と、
影響なしLSP計算手段が、LSP分類記憶手段から、故障復旧によって影響を受けないLSP群を取得し、該LSP群をLSP情報と共に計算済みLSP記憶手段に格納する影響なしLSP計算ステップ（ステップ２２）と、
影響ありLSP計算手段が、LSP分類記憶手段の故障復旧によって影響を受けるLSP群から、計算済みLSP記憶手段を参照して、まだ計算済みとなっていないLSPを１つ取得し、該LSPのLSP情報と故障復旧位置情報を参照し、新利用経路と状態を計算し、該LSPを新しいLSP情報と共に該計算済みLSP記憶手段に格納する影響ありLSP計算ステップ（ステップ２３）と、
計算済みとなっていないLSPを取得できなくなるまで、影響ありLSP計算ステップ（ステップ２３）を繰り返す。
【００１５】
また、本発明（請求項６）は、ある１つの箇所で故障が復旧した場合の経路推定を行う場合に、
RSVP-TE-LSP経路計算ステップのLSP分類ステップ（ステップ２１）において、
故障復旧によって影響を受けるLSP群を、更に、LSP情報の中の利用経路が故障復旧による変化するLSP群と、失敗状態から成功状態に変化する可能性があるLSP群とに分類し、該LSP情報と共に分類毎にLSP分類記憶手段に格納し、
RSVP-TE-LSP経路計算ステップの影響ありLSP計算ステップ（ステップ２３）において、
LSP情報の中の利用経路が故障復旧により変化するLSP群を先に計算し、失敗状態から成功状態に変化する可能性があるLSP群を後に計算する。
【００１６】
図２は、本発明の原理構成図である。
【００１７】
本発明（請求項７）は、OSPFを含むIPルーティング、及びRSVP-TEやLDPが動作するMPLSネットワークに、LSP及び、該LSPにFRRやBackup LSPを含む代替経路が設定され、IP及びMPLSのトラフィック通信が行われている状況下で、あるリンクまたはノードで故障が発生した場合のLSPやトラフィックの経路変化を推定する故障発生時の経路推定装置であって、
ネットワークの各ノードの接続関係を表したトポロジ情報、及び、該ネットワークに設定されているLSP群の個々の設定情報と利用経路と状態を表すLSP情報及び、通信が行われているトラフィック情報及び、該LSPとMPLSトラフィックを関連付けるFEC情報、及び故障発生箇所の位置情報を表す故障発生位置情報を取得し、情報記憶手段１７０に格納する情報取得手段１１０と、
情報記憶手段１７０を参照し、LSP情報のうち、RSVP-TEのLSP情報を取得し、故障発生による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段１８０に格納するRSVP-TE-LSP経路計算手段１２０と、
情報記憶手段１７０を参照し、LSP情報のうち、RSVP-TE以外のLSP情報を取得し、故障発生による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段１８０に格納するLSP経路計算手段１３０と、
情報記憶手段１７０に格納されているトラフィック情報のうち、MPLSのトラフィック情報を取得し、情報記憶手段１７０に格納されているFEC情報を参照し、MPLSトラフィックと関連付けられているLSPの新利用経路を計算済みLSP記憶手段１８０から取得し、該新利用経路を該MPLSトラフィックの新利用経路として、計算済みトラフィック記憶手段１９０に格納するMPLSトラフィック経路計算手段１４０と、
情報記憶手段１７０に格納されているトラフィック情報のうち、IPのトラフィック情報を取得し、故障発生による経路の変化を計算し、IPトラフィックの新利用経路を計算済みトラフィック記憶手段１９０に格納するＩＰトラフィック経路計算手段１５０と、
計算済みLSP記憶手段１８０及び計算済みトラフィック記憶手段１９０に格納されたLSP及びトラフィック毎の経路を出力する経路出力手段１６０と、を有する。
【００１８】
また、本発明（請求項８）は、RSVP-TE-LSP経路計算手段１２０において、
情報記憶手段１７０のRSVP-TEのLSP情報を参照して、故障発生によって影響を受けるLSP群と、故障発生によって影響を受けないLSP群に分類し、LSP情報と共に分類毎にLSP分類記憶手段１２４に格納するLSP分類手段１２１と、
LSP分類記憶手段１２４から、故障発生によって影響を受けないLSP群を取得し、該LSP群をLSP情報と共に計算済みLSP記憶手段１８０に格納する影響なしLSP計算手段１２２と、
LSP分類記憶手段１２４から、故障発生によって影響を受けるLSP群のうち、計算済みLSP記憶手段１８０を参照してまだ計算済みとなっていないLSPを１つ取得し、該LSPのLSP情報と故障発生位置情報を参照し、新利用経路と状態を計算し、該LSPを新しいLSP情報と共に該計算済みLSP記憶手段１８０に格納する処理を計算済みとなっていないLSPを取得できなくなるまで繰り返す影響ありLSP計算手段１２３と、を有する。
【００１９】
また、本発明（請求項９）は、ある１つの箇所で故障が発生した場合の経路推定を行う場合に、
RSVP-TE-LSP経路計算手段１２０のLSP分類手段１２１は、
故障発生によって影響を受けるLSP群を、更に、LSP情報の中の利用経路が故障発生箇所を通過するLSP群と、失敗状態から成功状態に変化する可能性があるLSP群とに分類し、該LSP情報と共に分類毎にLSP分類記憶手段１２４に格納する手段を含み、
RSVP-TE-LSP経路計算手段１２０の影響ありLSP計算手段１２３は、
LSP情報の中の利用経路が故障発生箇所を通過するLSP群を先に計算し、失敗状態から成功状態に変化する可能性があるLSP群を後に計算する手段を含む。
【００２０】
本発明（請求項１０）は、OSPFを含むIPルーティング、及びRSVP-TEやLDPが動作するMPLSネットワークに、LSP及び、該LSPにFRRやBackup LSPを含む代替経路が設定され、IP及びMPLSのトラフィック通信が行われている状況下で、あるリンクまたはノードの故障が復旧した場合のLSPやトラフィックの経路変化を推定する故障復旧時の経路推定装置であって、
ネットワークの各ノードの接続関係を表したトポロジ情報、及び、該ネットワークに設定されているLSP群の個々の設定情報と利用経路と状態を表すLSP情報及び、通信が行われているトラフィック情報及び、該LSPとMPLSトラフィックを関連付けるFEC情報、及び故障復旧箇所の位置情報を表す故障復旧位置情報を取得し、情報記憶手段１７０に格納する情報取得手段１１０と、
情報記憶手段１７０を参照し、LSP情報のうち、RSVP-TEのLSP情報を取得し、故障復旧による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段１８０に格納するRSVP-TE-LSP経路計算手段１２０と、
情報記憶手段１７０に格納されているLSP情報のうち、RSVP-TE以外のLSP情報を取得し、故障復旧による経路の変化を計算し、該LSPの新利用経路と状態を計算済みLSP記憶手段１８０に格納するLSP経路計算手段１３０と、
情報記憶手段１７０に格納されているトラフィック情報のうち、MPLSのトラフィック情報を取得し、情報記憶手段１７０に格納されているFEC情報を参照し、MPLSトラフィックと関連付けられているLSPの新利用経路を計算済みLSP記憶手段１８０から取得し、該新利用経路を該MPLSトラフィックの新利用経路として、計算済みトラフィック記憶手段１９０に格納するMPLSトラフィック経路計算手段１４０と、
情報記憶手段１７０に格納されている、トラフィック情報のうち、IPのトラフィック情報を取得し、故障復旧による経路の変化を計算し、IPトラフィックの新利用経路を計算済みトラフィック記憶手段１９０に格納するＩＰトラフィック経路計算手段１５０と、
計算済みLSP記憶手段１８０及び計算済みトラフィック記憶手段１９０に格納されたLSP及びトラフィック毎の経路を出力する経路出力手段１６０と、を有する。
【００２１】
また、本発明（請求項１１）は、RSVP-TE-LSP経路計算手段１２０において、
情報記憶手段１７０に格納されているRSVP-TEのLSP情報を参照して、故障復旧によって影響を受けるLSP群と、故障復旧によって影響を受けないLSP群に分類し、LSP情報と共に分類毎にLSP分類記憶手段１２４に格納するLSP分類手段１２１と、
LSP分類記憶手段１２４から、故障復旧によって影響を受けないLSP群を取得し、該LSP群をLSP情報と共に計算済みLSP記憶手段１８０に格納する影響なしLSP計算手段１２２と、
LSP分類記憶手段１２４の故障復旧によって影響を受けるLSP群から、計算済みLSP記憶手段１８０を参照して、まだ計算済みとなっていないLSPを１つ取得し、該LSPのLSP情報と故障復旧位置情報を参照し、新利用経路と状態を計算し、該LSPを新しいLSP情報と共に該計算済みLSP記憶手段１８０に格納する処理を、計算済みとなっていないLSPを取得できなくなるまで繰り返す影響ありLSP計算手段１２３と、を有する。
【００２２】
また、本発明（請求項１２）は、ある１つの箇所で故障が復旧した場合の経路推定を行う場合に、
RSVP-TE-LSP経路計算手段１２０のLSP分類手段１２１は、
故障復旧によって影響を受けるLSP群を、更に、LSP情報の中の利用経路が故障復旧による変化するLSP群と、失敗状態から成功状態に変化する可能性があるLSP群とに分類し、該LSP情報と共に分類毎にLSP分類記憶手段１２４に格納する手段を含み、
RSVP-TE-LSP経路計算手段１２０の影響ありLSP計算手段１２３は、
LSP情報の中の利用経路が故障復旧により変化するLSP群を先に計算し、失敗状態から成功状態に変化する可能性があるLSP群を後に計算する手段を含む。
【００２３】
本発明（請求項１３）は、コンピュータに、
請求項７乃至１２記載の経路推定装置の各手段を実行させる経路推定プログラムである。
【発明の効果】
【００２４】
上記のように本発明によれば、IPトラフィックやMPLSトラフィックが混在するネットワークにおいて、特に、RSVP-TEでは、LSP毎に異なる経路設定や予約帯域設定がなされている場合や、LSP毎に異なるプロテクション方式が設定されている場合、故障発生時または故障復旧時の経路の変化の仕方がLSP毎に異なる。故障発生時には、どのLSPが通信断になったか、また、迂回によってトラフィックが集中しているリソースがないか、など、経路の変化を自動的に、かつ、できるだけ正確に推定する必要がある。また、LSPの経路を設計したり、プロテクション方式を設計したりする際に、故障発生や復旧を想定した正確なシミュレーションが必要である。
【００２５】
本発明は、このような問題に対し、様々な設定のRSVP-TEのLSPや、IPトラフィック、MPLSトラフィックが混在するネットワークにおいて、故障発生時、または、故障復旧時の経路の変化をできるだけ正確に推定することが可能である。
【００２６】
また、LSPやFRR(Fast Re Routing)をネットワークに設定する際、本発明により、故障発生・復旧時の経路を正確にシミュレートすることが可能となる。
【発明を実施するための最良の形態】
【００２７】
以下、図面と共に本発明の実施の形態を説明する。
【００２８】
[第１の実施の形態]
本実施の形態では、あるリンクやノードで故障が発生した場合にトラフィックの経路変化を推定する場合について説明する。
【００２９】
図３は、本発明の第１の実施の形態における故障発生時の経路推定装置の構成を示す。
【００３０】
同図に示す経路推定装置は、情報取得部１１０、RSVP-TE-LSP経路計算部１２０、LSP経路計算部１３０、MPLSトラフィック経路計算部１４０、IPトラフィック経路計算部１５０、経路出力部１６０、情報記憶部１７０、計算済みLSP記憶部１８０、計算済みトラフィック記憶部１９０から構成され、トポロジ情報、LSP情報、トラフィック情報、FEC(Forward Equivalence Class)情報、故障発生位置情報が入力され、LSPとトラフィック個々の経路が出力される。
【００３１】
RSVP-TE-LSP経路計算部１２０は、LSP分類部１２１、影響なしLSP計算部１２２、影響ありLSP計算部１２３、LSP分類記憶部１２４、予約帯域記憶部１２５を有する。
【００３２】
なお、上記の情報記憶部１７０、計算済みLSP記憶部１８０、計算済みトラフィック記憶部１９０、及び予約帯域記憶部１２５は、ハードディスク装置等の記憶手段である。
【００３３】
図４、図５は、本発明の第１の実施の形態における動作のフローチャートである。
【００３４】
ステップ１０１）  まず、情報取得部１１０において、ネットワークの各ノードの接続関係を表したトポロジ情報を取得し、情報記憶部１７０に格納する。トポロジ情報には、各ノードの接続関係のほか、各リンクのメトリック値及び帯域を含む。
【００３５】
ステップ１０２）  次に、情報取得部１１０は、ネットワークに接続されているLSP群の個々の設定情報と利用経路と状態を表すLSP情報を取得し、情報記憶部１７０に格納する。ここで、LSP情報では、主経路として用いるRSVP-TEやLDPのPrimary LSPの他に、FRR経路として設定されるDetour LSP及びBypass LSP、Backup LSPも１つのRSVP-TE-LSPとして独立に扱う。LSP情報におけるLSPの設定情報は、ID番号、LSP種別、Ingress(PLR)ノード、Egress(MP)ノード、要求経路（RSVP-TE-LSPの場合のみ）、要求帯域（RSVP-TE-LSPの場合のみ）、プロテクション方式（RSVP-TE-LSPのPrimary LSPの場合のみ）を含む。ここで、本実施の形態では、LSP種別は、RSVP-TEとLDPの２種類が存在するものとする。
【００３６】
LSP情報における状態は、RSVP-TE-LSPのみを対象とし、本実施の形態におけるRSVP-TEの状態を図６に示す。
【００３７】
同図において、
・「Success」状態：RSVP-TE-LSP上に故障がなく、かつ、予約帯域オーバ箇所がない状態を表す。
・「Success(FRR)」状態：RSVP-TEのPrimary LSPのみを対象とし、LSP上に既に故障が発生しているが、FRRの迂回経路により故障を回避している状態を表す。
・「Success(FRR, Backup)」状態：RSVP-TEのPrimary LSPのみを対象とし、LSP上に既に故障が発生しているが、FRRの迂回経路により故障を回避し、その後、Backup LSPによりGlobal Repairが行われている状態を表す。
・「Failure(Backup)」状態：RSVP-TEのPrimary LSPのみを対象とし、LSP上に既に故障が発生しているが、Backup LSPによりGlobal Repairが行われている状態を表す。
・「Failure(No Route)」状態：LSP上に既に故障が発生していたり、ノード等が存在しないため、経路が切断されている状態を表す。
・「Failure(No Bandwidth)」状態：RSVP-TE-LSPのみを対象とし、LSP上に故障は発生していないが、予約帯域オーバ箇所がある状態を表す。
【００３８】
本実施の形態においては、最初に取得されるLSPの状態には、Success、Failure(No Route)、Failure(No Bandwidth)のみが存在し、既存故障はないものとする。
【００３９】
LSP情報における利用経路は、RSVP-TE-LSPの場合で、かつ、状態が「Success」の場合、LSPが通過するノードをIngressノードからEgressノードまで順に示した情報とし、状態が「Success(FRR)」「Success(FRR, Backup)」の場合、LSPが通過するノード情報及び故障箇所情報とする。RSVP-TE-LSPの場合で、かつ、状態が「Failure(Backup)」「Failure(No Route)」「Failure(No Bandwidth)」の場合、「経路なし」とする。
【００４０】
LSPがRSVP-TE-LSP以外の場合は、LSPが通過するノード情報とし、故障などにより通信が切断されている場合、「経路なし」とする。
【００４１】
ステップ１０３）  次に、情報取得部１１０は、ネットワークで通信が行われているトラフィック群の個々のトラフィック情報を取得し、情報記憶部１７０に格納する。トラフィック情報は、ＩＤ番号、トラフィック種別、ソースノード、宛先ノード、利用経路を含む。ここで、利用経路とは、トラフィックが通過するノード情報とし、故障などにより通信が切断されている場合、「経路なし」とする。
【００４２】
ステップ１０４）  次に、情報取得部１１０は、ネットワークに設定されているLSPとMPLSトラフィックを関連付けるFEC情報を取得し、情報記憶部１７０に格納する。FEC情報には、LSPのＩＤ番号と、トラフィックのＩＤ番号を関連付ける情報を含む。
【００４３】
ステップ１０５）  次に、情報取得部１１０は、故障発生箇所情報を取得し、情報記憶部１７０に格納する。故障発生箇所情報は、故障ノード、または、故障リンクで表す。
【００４４】
ステップ１０６）  RSVP-TE-LSP経路計算部１２０のLSP分類部１２１において、情報取得部１１０で取得し、情報記憶部１７０に格納されているLSP情報と、故障発生箇所情報を参照し、LSPの分類を行い、分類された情報をLSP分類記憶部１２４に格納する。当該LSP分類処理を以下に示す。
【００４５】
図７は、本発明の第１の実施の形態におけるLSP分類処理のフローチャートである。
【００４６】
ここで、影響を受けるRSVP-TE-LSP群のうち、故障発生箇所を通過するRSVP-TE-LSP群をグループＡ，影響を受けるRSVP-TE-LSP群のうち、失敗状態から成功状態に変化する可能性があるRSVP-TE-LSP群をグループＢ、影響を受けないRSVP-TE-LSP群をグループＣ、RSVP-TE以外のLSP群をグループＤとする。
【００４７】
まず、LSP分類部１２１は、情報記憶部１７０から取得したLSP情報について、LSPがRSVP-TEのLSPかそうでないかを判定する（ステップ２０１）。RSVP-TEのLSPでない場合（ステップ２０１、Ｎｏ）は、当該LSPは、グループＤと判定される。RSVP-TEのLSPの場合（ステップ２０１，Ｙｅｓ）は、次のステップに移る。
【００４８】
次に、当該LSPの状態が「Failure(No Route)」の場合（ステップ２０２，Ｙｅｓ）、グループＣと判定する。そうでない場合（ステップ２０２、Ｎｏ）、次のステップに移る。
【００４９】
次に、LSPの状態が「Failure(No Bandwidth)」の場合（ステップ２０３，Ｙｅｓ）、グループＢと判定する。そうでない場合は（ステップ２０３、Ｎｏ）、次のステップに移る。
【００５０】
次に、情報記憶部１７０から取得した故障発生箇所がLSPの利用経路上にある場合（ステップ２０４，Ｙｅｓ）、グループＡと判定し、そうでない場合は（ステップ２０４、Ｎｏ）、グループＣと判定する。
【００５１】
グループが判定されると、グループ毎にLSP情報をLSP分類記憶部１２４に格納する。
【００５２】
ステップ１０７）  次に、影響なしLSP計算部１２２において、LSP分類記憶部１２４を参照し、グループＣ、つまり、影響を受けないRSVP-TE-LSP群の全てのLSPのLSP情報を計算済みLSP記憶部１８０に格納する。
【００５３】
ステップ１０８）  次に、影響なしLSP計算部１２２において、グループＣの個々のLSPの利用経路と要求帯域を参照し、LSPが通過するリンクに予約帯域を加算し、リンク毎の予約帯域を予約帯域記憶部１２５に保存する。利用経路が「経路なし」の場合は、予約帯域の加算は行わない。ここで、ステップ１０１で取得し、情報記憶部１７０に格納されているトポロジ情報の中に、全てのLSPの要求帯域を足し合わせた、リンク毎の予約帯域情報が含まれている場合は、グループＣのLSPの要求帯域を加算するのではなく、グループＡ及びＢ、つまり、影響を受けるLSPの個々の利用経路を参照し、当該利用経路のリンクから当該LSPの要求帯域を減算するという処理を行ってもよい。
【００５４】
ステップ１０９）  次に、影響ありLSP計算部１２３において、LSP分類記憶部１２４を参照し、グループＡ、つまり、影響を受けるRSVP-TE-LSP群のうち、故障発生箇所を通過するRSVP-TE-LSP群からまだ計算済みとなっていないLSPを１つ取り出し、新利用経路と新状態を判定する。その動作を以下に示す。
【００５５】
図８、図９は、本発明の第１の実施の形態におけるグループＡのLSPの新利用経路と新状態判定動作のフローチャートである。
【００５６】
LSPがBypassまたは、Detourまたは、Backupかそうでないかを判定する（ステップ３０１）。BypassまたはDetourまたはBackupの場合（ステップ３０１，Ｙｅｓ）、取得した故障発生箇所を取り除いたトポロジにおいて、Ingress(PLR)ノードからEgress(MP)ノードまでの経路を計算する（ステップ３０２）。ここで、Strict指定区間は、指定されたノードとそれらを接続するリンクが存在するかどうかを検査する。Loose指定区間は、指定されたノード間でIGPによる最短経路計算で経路が存在するかどうかを検査する。計算結果は一時的にメモリ等に保存しておく。
【００５７】
経路計算の結果が「経路なし」の場合（ステップ３０３、Ｎｏ）、LSPの新状態を「Failure(No Route)」とし、新利用経路を「経路なし」とする（ステップ３０４）。経路計算の結果、経路があるが、当該経路上に予約帯域オーバ箇所がある場合（ステップ３０５，Ｙｅｓ）、LSPの新状態を「Failure(No Bandwidth)」とし、新利用経路を「経路なし」とする（ステップ３０６）。経路計算の結果、経路があり（ステップ３０３，Ｙｅｓ）、当該経路上に予約帯域オーバ箇所がない場合（ステップ３０５、Ｎｏ）、LSPの新状態を「Success」とし、経路計算で得られた経路を新利用経路とする（ステップ３０７）。
【００５８】
次に、LSPがBypassまたはDetourまたはBackupでない場合（ステップ３０１、Ｎｏ）、上記同様、経路計算を行い（ステップ３０８）、経路があり（ステップ３０９，Ｙｅｓ）、かつ予約帯域オーバ箇所がない場合（ステップ３１０、Ｎｏ）、LSPの新状態を「Success」とし、経路計算で得られた経路を新利用経路とする（ステップ３１１）。
【００５９】
経路がないか（ステップ３０９、Ｎｏ）、または、経路はあるが予約帯域オーバ箇所がある場合（ステップ３１０，Ｙｅｓ）は、当該LSPにおいて、取得した故障発生箇所にFRRが設定されていて、かつ、当該BypassまたはDetourがグループＣに属し、「Success」状態かどうかを判断する（ステップ３１２）。そうであれば、当該LSPにBackupが設定されていて、当該BackupがグループＣに属し、「Success」状態かどうかを判定する（ステップ３１３）。そうであれば（ステップ３１３，Ｙｅｓ）、LSPの新状態を「Success(FRR, Backup)」とし、利用経路に取得した故障発生箇所情報を追加して新利用経路とする（ステップ３１４）。当該LSPにBackupが設定されていないか、または、当該BackupがグループＣに属さず、「Success」状態でない場合（ステップ３１３，Ｎｏ）、LSPの新状態を「Success(FRR)」とし、利用経路に、取得した故障発生箇所情報を追加して新利用経路とする（ステップ３１５）。
【００６０】
LSPにおいて、取得した故障発生箇所にFRRが設定されていないか、または、当該BypassまたはDetourがグループＣに属さず、「Success」状態でない場合も（ステップ３１２，Ｎｏ）、当該LSPにBackupが設定されていて、当該BackupがグループＣに属し、「Success」状態かどうかを判定する（ステップ３１６）。そうであれば（ステップ３１６，Ｙｅｓ）、LSPの新利用経路を「Failure(Backup)」とし、新利用経路を経路なしとする（ステップ３１７）。そうでなければ（ステップ３１６，Ｎｏ）、経路があり、かつ、予約帯域オーバ箇所があるかどうかを判定する（ステップ３１８）。そうであれば（ステップ３１８，Ｙｅｓ）、LSPの新状態を「Failure(No Bandwidth)」とし、新利用経路を経路なしとする（ステップ３１９）。経路がない場合は（ステップ３１８，Ｎｏ）、LSPの新状態を「Failure(No Route)」とし、新利用経路を経路なしとする（ステップ３２０）。
【００６１】
ステップ１１０）  次に、影響ありLSP計算部１２３は、上記のLSPについて、利用経路と状態を新利用経路と新状態に更新したLSP情報を、計算済みLSP記憶部１８０に格納する。
【００６２】
ステップ１１１）  影響ありLSP計算部１２３は、新利用経路と新状態と要求帯域を参照し、LSPが通過するリンクに予約帯域を加算し、リンク毎の予約帯域を予約帯域記憶部１２５に格納する。ここで、新状態が「Success(FRR, Backup)」と「Success(FRR)」の場合、故障箇所を除いた経路のリンクに帯域を加算する。ノード故障の場合は、当該故障ノードと経路上のその故障ノードの両端のノードまでを取り除いた経路、リンク故障の場合は、経路上の当該リンクを取り除いた経路とする。新利用経路が経路なしの場合は、帯域の加算は行わない。
【００６３】
ステップ１１２）  グループＡのLSPが全て計算済みLSP記憶部１８０に格納されるまで、新利用経路と新状態の判定（ステップ１０９）、計算済みLSP記憶部１８０への格納（ステップ１１０）、予約帯域の計算処理（ステップ１１１）の処理を繰り返す。
【００６４】
ステップ１１３）  次に、影響ありLSP計算部１２３は、LSP分類記憶部１２４を参照し、グループＢ、つまり、影響を受けるRSVP-TE-LSP群のうち、失敗状態から成功状態に変化する可能性があるRSVP-TE-LSP群から、まだ計算済みとなっていないLSPを１つ取り出し、新利用経路と新状態を判定する。その動作を以下に示す。
【００６５】
図１０は、本発明の第１の実施の形態におけるグループＢのLSPの新利用経路と新状態の判定動作のフローチャートである。
【００６６】
上記と同様に、影響ありLSP計算部１２３は、経路計算を行う（ステップ４０１）。経路がある場合で、かつ、予約帯域オーバ箇所がある場合は（ステップ４０２，４０３，Ｙｅｓ）、LSPの新状態を「Failure(No Bandwidth)」とし、新利用経路を経路なしとする（ステップ４０４）。経路がある場合で（ステップ４０２，Ｙｅｓ）、かつ、予約帯域オーバ箇所がない場合は（ステップ４０３，Ｎｏ）、LSPの新状態を「Success」とし、経路計算で得られた経路を新利用経路とする（ステップ４０５）。経路がない場合は、LSPの新状態を「Failure(No Route)」とし、新利用経路を経路なしとする（ステップ４０６）。
【００６７】
ステップ１１４）  影響ありLSP計算部１２３は、当該LSPについて、利用経路と状態を、新利用経路と新状態に更新したLSP情報を計算済みLSP記憶部１８０に格納する。
【００６８】
ステップ１１５）  次に、影響ありLSP計算部１２３は、新利用経路と新状態と要求帯域を参照し、上記と同様に、LSPが通過するリンクに予約帯域を加算し、リンク毎の予約帯域を予約帯域記憶部１２５に格納する。
【００６９】
ステップ１１６）  グループＢのLSPが全て計算済みLSP記憶部１８０に格納されるまで、新利用経路と新状態の判定処理（ステップ１１３）、計算済みLSP記憶部１８０への格納（ステップ１１４）、予約帯域の計算の処理（ステップ１１５）を繰り返す。
【００７０】
ステップ１１７）  LSP経路計算部１３０は、LSP分類記憶部１２４を参照し、グループＤ、つまり、RSVP-TE以外のLSP群からまだ計算済みとなっていないLSPを１つ取り出し、新利用経路を計算する。取得した故障発生箇所を取り除いたトポロジにおいて、IngressノードからEgressノードまで、IGPによる最短経路計算を行い、経路があれば当該経路を新利用経路とし、経路がない場合は新利用経路を経路なしとする。LSP情報の利用経路を新利用経路に更新し、計算済みLSP記憶部１８０に格納する。グループＤのLSPが全て計算済みLSP記憶部１８０に格納されるまで、新利用経路の計算、計算済みLSP記憶部１８０のへの格納の処理を繰り返す。
【００７１】
ステップ１１８）  次に、MPLSトラフィック経路計算部１４０は、情報記憶部１７０を参照し、トラフィック群のうち、トラフィック種別がMPLSトラフィックであるトラフィックについて、まだ計算済みとなっていないMPLSトラフィックを１つ取り出し、新利用経路を計算する。新利用経路の計算方法は以下の通りである。
【００７２】
まず、情報記憶部１７０のFEC情報を参照し、当該MPLSトラフィックのＩＤ番号と関連付けられているLSPのＩＤ番号を取得する。計算済みLSP記憶部１８０を参照し、取得したＩＤ番号のLSPの新利用経路を参照し、それを当該MPLSトラフィックの新利用経路とする。但し、当該MPLSトラフィックと関連付けられているLSPが、RSVP-TE-LSPで、かつ、当該LSPの新状態が、「Success(FRR)」の場合は、当該LSPの新利用経路と、当該LSPに設定されているBypassまたはDetour LSPの新利用経路を結合したものを当該MPLSトラフィックの新利用経路とし、「Success(FRR,Backup)」と「Failure(Backup)」の場合は、当該LSPに設定されているBackup LSPの新利用経路を当該MPLSトラフィックの新利用経路とする。トラフィック情報の利用経路を新利用経路に更新し、計算済みトラフィック記憶部１９０に格納する。MPLSトラフィックが全て計算済みトラフィック記憶部１９０に格納されるまで、新利用経路の計算、計算済みトラフィック記憶部１９０への格納の処理を繰り返す。
【００７３】
ステップ１１９）  次に、ＩＰトラフィック経路計算部１５０において、情報記憶部１７０から、トラフィック群のうち、トラフィック種別がＩＰトラフィックであるトラフィックについて、まだ計算済みとなっていないＩＰトラフィックを１つ取り出し、新利用経路を計算する。ステップ１０５で取得した故障発生箇所を取り除いたトポロジにおいて、ソースノードから宛先ノードまで、IGPによる最短経路計算を行い、経路があれば、当該経路を新利用経路とし、経路がない場合は、新利用経路を経路なしとする。トラフィック情報の利用経路を新利用経路に更新し、計算済みトラフィック記憶部１９０に格納する。ＩＰトラフィックが全て計算済みトラフィック記憶部１９０に格納されるまで、新利用経路の計算、計算済みトラフィック記憶部１９０への格納の処理を繰り返す。
【００７４】
ステップ１２０）  最後に、経路出力部１６０において、計算済みLSP記憶部１８０、及び計算済みトラフィック記憶部１９０に格納されているLSP毎、トラフィック毎の利用経路を出力して処理を終了する。
【００７５】
上記の第１の実施の形態によれば、MPLSとIPが混在したネットワークにおいて、故障が発生した場合の経路の変化を正しく推定することが可能である。
【００７６】
［第２の実施の形態］
本実施の形態では、故障復旧時の経路推定について説明する。
【００７７】
本実施の形態における経路推定装置は、前述の第１の実施の形態における経路推定装置と同様の構成であるので、以下では図３を用いて説明する。
【００７８】
以下に、本実施の形態における動作を説明する。本実施の形態では、故障箇所がネットワークに１つ存在していることを前提とし、当該故障箇所を復旧させることとする。
【００７９】
以下の動作を、前述の図４，５を用いて説明する。
【００８０】
ステップ１０１）  まず、情報取得部１１０において、ネットワークの各ノードの接続関係を表したトポロジ情報を取得し、情報記憶部１７０に格納する。トポロジ情報には、各ノードの接続関係のほか、各リンクのメトリック値及び帯域を含む。
【００８１】
ステップ１０２）  次に、ネットワークに接続されているLSP群の個々の設定情報と利用経路と状態を表すLSP情報を取得し、情報記憶部１７０に格納する。ここで、LSP情報では、主経路として用いるRSVP-TEやLDPのPrimary LSPの他に、FRR経路として設定されるDetour LSP及びBypass LSP、Backup LSPも１つのRSVP-TE-LSPとして独立に扱う。LSP情報におけるLSPの設定情報は、ID番号、LSP種別、Ingress(PLR)ノード、Egress(MP)ノード、要求経路（RSVP-TE-LSPの場合のみ）、要求帯域（RSVP-TE-LSPの場合のみ）、プロテクション方式（RSVP-TE-LSPのPrimary LSPの場合のみ）を含む。ここで、本実施の形態では、LSP種別は、RSVP-TEとLDPの２種類が存在するものとする。LSP情報における状態は、第１の実施の形態と同様の定義とする。LSPが通過するノードをIngressノードからEgressノードまで順に示した情報とし、状態が「Success(FRR)」「Success(FRR, Backup)」の場合、LSPが通過するノード情報及び故障箇所情報とするRSVP-TE-LSPの場合で、かつ、状態が「Failure(Backup)」、「Failure(No Route)」、「Failure(No Bandwidth)」の場合「経路なし」とする。LSPがRSVP-TE-LSP以外の場合は、LSPが通過するノード情報とし、故障などにより通信が切断されている場合、「経路なし」とする。
【００８２】
ステップ１０３）  次に、情報取得部１１０において、ネットワークで通信が行われているトラフィック群の個々のトラフィック情報を取得し、情報記憶部１７０に格納する。トラフィック情報は、ＩＤ番号、トラフィック種別、ソースノード、宛先ノード、利用経路を含む。ここで、利用経路は、トラフィックが通過するノード情報とし、故障などにより通信が切断されている場合、「経路なし」とする。
【００８３】
ステップ１０４）  次に、情報取得部１１０において、ネットワークに設定されているLSPとMPLSトラフィックを関連付けるFEC情報を取得し、情報記憶部１７０に格納する。FEC情報は、LSPのＩＤ番号と、トラフィックのＩＤ番号を関連付ける情報を含む。
【００８４】
ステップ１０５）  次に、情報取得部１１０において、故障復旧箇所情報を取得し、情報記憶部１７０に格納する。故障復旧箇所情報は、復旧ノード、または、復旧リンクで表す。
【００８５】
ステップ１０６）  RSVP-TE-LSP経路計算部１２０のLSP分類部１２１において、ステップ１０２で取得したLSP情報と、ステップ１０５で取得し、情報記憶部１７０に格納されている故障発生箇所情報を参照し、LSPの分類を行う。本実施の形態におけるLSPの分類方法を以下に示す。
【００８６】
図１１は、本発明の第２の実施の形態におけるLSP分類動作のフローチャートである。
【００８７】
ここで、影響を受けるRSVP-TE-LSP群のうち、故障復旧により経路が変更される「Success」「Success(FRR)」「Success(FRR, Backup)」状態のRSVP-TE-LSP群をグループＡ、影響を受けるRSVP-TE-LSP群のうち、失敗状態から成功状態に変化する可能性のある「Failure(No Route)」「Failure(No Bandwidth)」「Failure(Backup)」状態のLSP群をグループＢ、影響を受けないRSVP-TE-LSP群をグループＣ、RSVP-TE以外のLSP群をグループＤとする。
【００８８】
まず、LSP分類部１２１は、情報記憶部１７０に格納されているLSP情報のLSPがRSVP-TEのLSPかそうでないかを判定する（ステップ５０１）。RSVP-TEのLSPでない場合（ステップ５０１，Ｎｏ）、当該LSPはグループＤと判定される（ステップ５０２）。
【００８９】
RSVP-TEのLSPの場合は（ステップ５０１，Ｙｅｓ）、LSPの状態が「Failure(No Route)」または、「Failure(No Bandwidth)」、または、「Failure(Backup)」の場合（ステップ５０３，Ｙｅｓ）、グループＢと判定する（ステップ５０４）。そうでない場合（ステップ５０３，Ｎｏ）は、取得した故障復旧箇所を戻したトポロジにおいて、Ingress(PLR)ノードからEgress（MP）ノードまでの経路を計算する（ステップ５０５）。ここで、Strict指定区間は、指定されたノードとそれらを接続するリンクが存在するかどうかを検査する。Loose指定区間は、指定されたノード間でＩＧＰによる最短経路計算で経路が存在するかどうかを検査する。計算の結果得られた経路とLSPの利用経路が異なる場合、または、LSP上の故障箇所が復旧する場合（ステップ５０６，Ｙｅｓ）、グループＡと判定する（ステップ５０７）。そうでない場合は（ステップ５０６，Ｎｏ）、グループＣと判定する（ステップ５０８）。
【００９０】
ステップ１０７）  影響なしLSP計算部１２２において、LSP分類記憶部１２４を参照し、グループＣ、つまり、影響を受けないRSVP-TE-LSP群の全てのLSPについてLSP情報を計算済みLSP記憶部１８０に格納する。
【００９１】
ステップ１０８）  影響なしLSP計算部１２２において、グループＣの個々のLSPの利用経路と要求帯域を参照し、LSPが通過するリンクに予約帯域を加算し、リンク毎の予約帯域を予約帯域記憶部１２５に保存する。利用経路が「経路なし」の場合は、予約帯域の加算は行わない。ここで、ステップ１０１で取得し、情報記憶部１７０に格納されているトポロジ情報に中に、全てのLSPの要求帯域を足し合わせた、リンク毎の予約帯域情報が含まれている場合は、グループＣのSLPの要求帯域を加算するのではなく、グループＡ及びＢ、つまり影響を受けるLSPの個々の利用経路を参照し、当該利用経路のリンクから当該LSPの要求帯域を減算するという処理を行ってもよい。
【００９２】
ステップ１０９）  次に、影響ありLSP計算部１２３において、LSP分類記憶部１２４を参照し、グループＡ、つまり、影響を受けるRSVP-TE-LSP群のうち、故障復旧により経路が変更されるRSVP-TE-LSP群からまだ計算済みとなっていないLSPを１つ取り出し、新利用経路と新状態を判定する。その動作を以下に説明する。
【００９３】
図１２は、本発明の第２の実施の形態におけるグループＡのLSPの新利用経路と新状態の判定動作のフローチャートである。
【００９４】
まず、上記同様、LSP経路計算部１３０は、取得した故障復旧箇所を戻したトポロジにおいて経路計算を行う（ステップ６０１）。故障が復旧するので、経路は必ず存在する。予約帯域オーバ箇所がない場合（ステップ６０２，Ｎｏ）、LSPの新状態を「Success」とし、経路計算で得られた経路を新利用経路とする（ステップ６０３）。
【００９５】
予約帯域オーバ箇所がある場合（ステップ６０２，Ｙｅｓ）、LSPの状態が「Success(FRR)」であるかを判定する（ステップ６０４）。そうであれば（ステップ６０４，Ｙｅｓ）、LSPの新状態を「Success(FRR)」とし、利用経路の故障箇所を予約帯域オーバ箇所として新利用経路とする（ステップ６０５）。LSPの状態が「Success(FRR)」でない場合（ステップ６０４，Ｎｏ）、LSPの状態が「Success(FRR, Backup)」かどうかを判定する（ステップ６０６）。そうであれば（ステップ６０６，Ｙｅｓ）、LSPの新状態を「Success(FRR, Backup)」とし、利用経路の故障箇所を予約帯域オーバ箇所として新利用経路とする（ステップ６０７）。LSPが「Success(FRR, Backup)」でない場合は、LSPの新状態を「Failure(No Bandwidth)」とし、新利用経路を「経路なし」とする（ステップ６０８）。
【００９６】
ステップ１１０）  次に、影響ありLSP計算部１２３において、上記で求められたLSPの利用経路と状態を、新利用経路と新状態に更新したLSP情報を計算済みLSP記憶部１８０に格納する。
【００９７】
ステップ１１１）  影響ありLSP計算部１２３は、計算済みLSP記憶部１８０の新利用経路と新状態と要求帯域を参照し、LSPが通過するリンクに予約帯域を加算し、リンク毎の予約帯域を予約帯域記憶部１２５に格納する。ここで、新状態が「Success(FRR, Backup)」と「Success(FRR)」の場合、予約帯域オーバ箇所を除いた経路のリンクに帯域を加算する。ノード故障の場合は、当該故障ノードと経路上のその故障ノードの両端のノードまでを除いた経路、リンク故障の場合は、経路上の当該リンクを取り除いた経路とする。新利用経路が経路なしの場合は、帯域の加算は行わない。
【００９８】
ステップ１１２）  グループＡのLSPが全て計算済みLSP記憶部１８０に格納されるまで、新利用経路と新状態の判定（ステップ１０９）、計算済みLSP記憶部１８０への格納（ステップ１１０）、予約帯域計算の処理（ステップ１１１）を繰り返す。
【００９９】
ステップ１１３）  次に、影響ありLSP計算部１２３は、LSP分類記憶部１２４を参照し、グループＢ、つまり、影響を受けるRSVP-TE-LSP群のうち、失敗状態から成功状態に変化する可能性があるRSVP-TE-LSP群からまだ計算済みとなっていないLSPを１つ取り出し、新利用経路と新状態を判定する。その動作を以下に示す。
【０１００】
図１３は、本発明の第２の実施の形態におけるグループＢの新利用経路と新状態の判定動作のフローチャートである。
【０１０１】
まず、影響ありLSP計算部１２３において、LSPが「Failure(Backup)」かどうかを判定する（ステップ７０１）。「Failure(Backup)」であれば、上記同様の経路計算を行い（ステップ７０２）、予約帯域オーバ箇所があるかどうかを判定する（ステップ７０３）。予約帯域オーバ箇所がなければ（ステップ７０３，Ｎｏ）、LSPの新状態を「Success」とし、経路計算で得られた経路を新利用経路とする（ステップ７０４）。予約帯域オーバ箇所がある場合は（ステップ７０３，Ｙｅｓ）、LSPの新状態を「Failure(Backup)」とし、新利用経路は「経路なし」とする（ステップ７０５）。
【０１０２】
次に、LSPが「Failure(Backup)」でない場合（ステップ７０１，Ｎｏ）、上記同様の経路計算を行い（ステップ７０６）、経路があるかどうかを判定する（ステップ７０７）。経路があり、かつ、予約帯域オーバ箇所がない場合（ステップ７０８，Ｎｏ）、LSPの新状態を「Success」とし、経路計算で得られた経路を新利用経路とする（ステップ７０９）。予約帯域オーバ箇所がある場合（ステップ７０８，Ｙｅｓ）、LSPの新状態を「Failure(No Bandwidth)」とし、新利用経路を「経路なし」とする（ステップ７１０）。経路計算において経路がない場合（ステップ７０７，Ｎｏ）、LSPの新状態を「Failure(No Route)」とし、新利用経路を「経路なし」とする（ステップ７１１）。
【０１０３】
ステップ１１４）  次に、影響ありLSP計算部１２３において、当該LSPについて、利用経路と状態、新利用経路と新状態に更新したLSP情報を計算済みLSP記憶部１８０に格納する。
【０１０４】
ステップ１１５）  次に、影響ありLSP計算部１２３は、計算済みLSP記憶部１８０の新利用経路と新状態と要求帯域を参照し、上記同様、LSPが通過するリンクに予約帯域を加算し、リンク毎の予約帯域記憶部１２５に格納する。
【０１０５】
ステップ１１６）  影響ありLSP計算部１２３において、グループＢのLSPが全て計算済みLSP記憶部１８０に格納されるまで、新利用経路と新状態の判定（ステップ１１３）、計算済みLSP記憶部１８０への格納（ステップ１１４）、予約帯域の計算の処理（ステップ１１５）を繰り返す。
【０１０６】
ステップ１１７）  次に、LSP経路計算部１３０は、LSP分類記憶部１２４からグループＤ、つまり、RSVP-TE以外のLSP群からまだ計算済みとなっていないLSPを１つ取り出し、新利用経路を計算する。ステップ１０５で取得した故障復旧箇所を戻したトポロジにおいて、IngressノードからEgressノードまで、ＩＧＰによる最短経路計算を行い、経路があれば当該経路を新利用経路とし、経路がない場合は新利用経路を「経路なし」とする。LSP情報の利用経路を新利用経路に更新し、計算済みLSP記憶部１８０に格納する。グループＤのLSPが全て計算済みLSP記憶部１８０に格納されるまで、新利用経路の計算、計算済みLSP記憶部１８０への格納の処理を繰り返す。
【０１０７】
これ以降の、MPLSトラフィックの経路計算（ステップ１１８）、IPトラフィックの経路計算（ステップ１１９）、経路出力処理（ステップ１２０）は、前述の第１の実施の形態と同様である。但し、各経路計算処理において用いるトポロジは、取得した故障復旧箇所を戻したトポロジとする。
【０１０８】
上記の第２の実施の形態によれば、MPLSとIPが混在したネットワークにおいて、故障が復旧した場合の経路の変化を正しく推定することが可能である。
【０１０９】
なお、上記の第１・第２の実施の形態の動作をプログラムとして構築し、経路推定装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１１０】
また、構築されたプログラムを、コンピュータ読み取り可能なディスク装置や、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールして実行させる、または、配布することが可能である。
【０１１１】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【０１１２】
本発明は、RSVP-TEのLSP等が混在し、FRRやBackup LSP等が設定されているネットワークにおいて、故障発生時または、故障復旧時の状況をシミュレートするための技術に適用可能である。
【図面の簡単な説明】
【０１１３】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の第１及び第２の実施の形態における故障発生時または故障復旧時の系尾推定装置の構成図である。
【図４】本発明の第１及び第２の実施の形態における動作のフローチャート（その１）である。
【図５】本発明の第１及び第２の実施の形態における動作のフローチャート（その２）である。
【図６】本発明の第１及び第２の実施の形態におけるRSVP-TE-LSPの状態である。
【図７】本発明の第１の実施の形態におけるLSP分類動作のフローチャートである。
【図８】本発明の第１の実施の形態におけるグループＡのLSPの新利用経路と新状態の判定動作のフローチャート（その１）である。
【図９】本発明の第１の実施の形態におけるグループＡのLSPの新利用経路と新状態の判定動作のフローチャート（その２）である。
【図１０】本発明の第１の実施の形態におけるグループＢの新利用経路と新状態の判定動作のフローチャートである。
【図１１】本発明の第１の実施の形態におけるLSP分類動作のフローチャートである。
【図１２】本発明の第２の実施の形態におけるグループＡのLSPの新利用経路と新状態の判定動作のフローチャートである。
【図１３】本発明の第２の実施の形態におけるグループＢのLSPの新利用経路と新状態の判定動作のフローチャートである。
【図１４】FRRの分類である。
【符号の説明】
【０１１４】
１１０  情報取得手段、情報取得部
１２０  RSVP-TE-LSP経路計算手段
１２１  LSP分類手段、LSP分類部
１２２  影響なしLSP計算手段、影響なしLSP計算部
１２３  影響ありLSP計算手段、影響ありLSP計算部
１２４  LSP分類記憶手段、LSP分類記憶部
１２５  予約帯域記憶部
１３０  LSP経路計算手段、LSP経路計算部
１４０  MPLSトラフィック経路計算手段、MPLSトラフィック経路計算部
１５０  IPトラフィック経路計算手段、IPトラフィック経路計算部
１６０  経路出力手段、経路出力部
１７０  情報記憶手段、情報記憶部
１８０  計算済みLSP記憶手段、計算済みLSP記憶部
１９０  計算済みトラフィック記憶手段、計算済みトラフィック記憶部
【図１】
2007318311.tif 000003
【図２】
2007318311.tif 000004
【図３】
2007318311.tif 000005
【図４】
2007318311.tif 000006
【図５】
2007318311.tif 000007
【図６】
2007318311.tif 000008
【図７】
2007318311.tif 000009
【図８】
2007318311.tif 000010
【図９】
2007318311.tif 000011
【図１０】
2007318311.tif 000012
【図１１】
2007318311.tif 000013
【図１２】
2007318311.tif 000014
【図１３】
2007318311.tif 000015
【図１４】
2007318311.tif 000016