(57)【特許請求の範囲】
【請求項１】
複数のエリアに分割されたネットワークにおいて始点ノードと終点ノードを結ぶ二本以上の経路を計算する経路計算装置であって、
前記二本以上の経路の少なくとも一つが通過する通過エリアのうち複数の経路が通過する複数経路通過エリアを特定する複数経路通過エリア特定部と、
前記経路計算装置が存在するエリアである自エリアが、前記複数経路通過エリアである場合、前記二本以上の経路のうちの第一の経路を算出する際に、前記自エリアについて、前記自エリアを通過する経路の数と同数のエリア内経路を計算するエリア内経路計算部を備える
ことを特徴とする経路計算装置。
【請求項２】
複数のエリアに分割されたネットワークにおいて始点ノードと終点ノードを結ぶ二本以上の経路を計算する経路計算装置であって、
前記二本以上の経路の少なくとも一つが通過する通過エリアのうち複数の経路が通過する複数経路通過エリアの情報を含むデータを受信する受信部と、
前記経路計算装置が存在するエリアである自エリアが、前記複数経路通過エリアである場合、前記二本以上の経路のうちの第一の経路を算出する際に、前記自エリアについて、前記自エリアを通過する経路の数と同数のエリア内経路を計算するエリア内経路計算部を備える
ことを特徴とする経路計算装置。
【請求項３】
前記複数経路通過エリアに対して前記第一の経路の計算の際に計算された前記エリア内経路のうちで前記第一の経路に含まれていないエリア内経路を用いて、前記二本以上の経路のうちの第二の経路が通過する第二経路通過エリアを特定する通過エリア特定部と、
特定された前記第二経路通過エリアに含まれる経路計算装置に対して、前記第二経路通過エリアでの経路の計算を要求するとともに、前記第二経路通過エリアで計算されたエリア内経路の情報を受信するエリア間経路計算部と、
前記複数経路通過エリアについて得られたエリア内経路と前記第二経路通過エリアについて得られたエリア内経路を用いて、前記第二の経路を決定する経路決定部
をさらに備えることを特徴とする、請求項１記載の経路計算装置。
【請求項４】
前記複数経路通過エリアについて、前記複数経路通過エリアを通過する経路の数と同数のエリア内経路が得られない場合に、
前記エリア内経路計算部は、前記複数経路通過エリアから前記複数経路通過エリアに隣接する隣接エリアに到達するためのエリア内経路を計算する
ことを特徴とする請求項１記載の経路計算装置。
【請求項５】
前記複数経路通過エリアについて、前記複数経路通過エリアを通過する経路の数と同数のエリア内経路が得られない場合に、
前記エリア内経路計算部は、前記複数経路通過エリアを通過する経路の数から前記複数経路通過エリアにおいて得られたエリア内経路の数を差し引いた不足経路数のエリア内経路を、前記複数経路通過エリアから前記隣接エリアに到達するためのエリア内経路として前記複数経路通過エリア内で計算する
ことを特徴とする請求項４に記載の経路計算装置。
【請求項６】
前記通過エリア、前記複数経路通過エリア、前記複数経路通過エリアに隣接する隣接エリアの少なくとも一つで計算された前記エリア内経路を選択して組み合わせることによって、経路決定部が、前記始点ノードと前記終点ノードを結ぶ経路を設定する
ことを特徴とする請求項１記載の経路計算装置。
【請求項７】
複数のエリアに分割されたネットワークにおいて始点ノードと終点ノードを結ぶ二本以上の経路を計算する経路計算システムであって、
第一の経路計算装置が、前記二本以上の経路の少なくとも一つが通過する通過エリア、および、前記通過エリアのうち複数の経路が通過する複数経路通過エリアを特定し、
前記第一の経路計算装置が、前記通過エリアおよび前記複数経路通過エリアを、前記複数経路通過エリアを制御する第二の経路計算装置に通知し、
前記第二の経路計算装置は、前記複数経路通過エリアについて一つの経路を計算する際に、前記複数経路通過エリアを通過する経路の数と同数のエリア内経路を計算する
ことを特徴とする経路計算システム。
【請求項８】
前記第一の経路計算装置は、前記通過エリアおよび前記複数経路通過エリアを、前記通過エリアを制御する第三の経路計算装置に、さらに通知し、
前記第三の経路計算装置は、前記第三の経路計算装置が制御する前記通過エリアについてエリア内経路を計算し、
前記第二の経路計算装置は、前記第二の経路計算装置が制御する前記複数経路通過エリアについてのエリア内経路計算結果を、前記第一の経路計算装置に通知し、
前記第三の経路計算装置は、計算したエリア内経路を、前記第一の経路計算装置に通知し、
前記第一の経路計算装置は、前記第二の経路計算装置から通知された前記エリア内経路計算結果から選択したエリア内経路、前記第三の経路計算装置から通知されたエリア内経路、および、前記第一の経路計算装置が制御するエリアについてのエリア内経路の計算結果を接続して、前記始点ノードと前記終点ノードを結ぶ第一の経路を決定する
ことを特徴とする請求項７に記載の経路計算システム。
【請求項９】
前記第一の経路計算装置は、前記二本以上の経路のうちの第二の経路を計算する際に、前記第一の経路計算装置に通知された経路の数が二以上であるエリアを通過するように、前記第二の経路が通過する第二経路通過エリアを特定し、
前記第二経路通過エリアの経路計算を行う経路計算装置は、前記第一の経路計算装置の通知に応じてエリア内経路を計算する
ことを特徴とする請求項７記載の経路計算システム。
【請求項１０】
前記第二の経路計算装置が計算した前記複数経路通過エリアから前記通過エリアに到達する前記エリア内経路の数が、前記複数経路通過エリアを通過する経路の数よりも少ないとき、前記第二の経路計算装置は、前記複数経路通過エリアから前記複数経路通過エリアに隣接する隣接エリアに到達するためのエリア内経路を、前記複数経路通過エリアについて計算する
ことを特徴とする請求項７記載の経路計算システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークにおける経路計算に関わり、特に、複数に分割したネットワークにおける経路計算に関わる。
【背景技術】
【０００２】
大規模なネットワークで経路計算を行う場合には、装置内のデータベースサイズや経路計算に際して交換するネットワーク情報が膨大な量になる。例えば、ＯＳＰＦ（Open Shortest Path First）等のルーチングプロトコルを用いると、１００ノード程度しか詳細なトポロジを管理することができない。そこで、詳細なトポロジを管理するノード数を小さくするために、ネットワークを複数のエリアに分割することが多い。
【０００３】
図１９は、分割された複数のエリアにまたがる経路計算を行うための関連技術を説明する図である。図１９の例では、エリア２ａ、エリア２ｂ、エリア２ｃの３つのエリアからなるネットワークで、ルーチングプロトコルを使用して経路計算とシグナリングをすることを前提とする。
【０００４】
複数のノード１が含まれるエリア２において、経路を計算する機能を有する装置は、自装置が存在するエリア２（自エリア）の情報をサマライズし、自エリア以外に存在する装置にサマライズ情報として通知する。この情報交換により、経路計算を行う装置は、自エリア以外のエリア２についてのサマライズ情報と、自エリアの詳細情報を知ることができる。
【０００５】
経路計算が要求されると、始点ノードが存在するエリア２ａの経路計算を行う装置は、始点ノードから終点ノードに到達するために通過するエリア２を、サマライズ情報を使用して決定する。その後、始点側のエリアから順番に、各エリア２の詳細情報に基づいて自エリア内の詳細な経路計算を行い、シグナリングによるパス設定を行う。図１９の例では、エリア２ａ、エリア２ｂ、エリア２ｃの順に通過するものとする。そこで、まずエリア２ａについて詳細情報を用いて経路計算が行われ、シグナリングにより経路３のパス設定が行われる。次に、エリア２ｂにおいて、経路計算とシグナリングが同様に行われ経路３の設定が行われる。
【０００６】
また、上記の経路の計算を、経路計算エンジン（ＰＣＥ、Path Computation Element）を用いて行うことも検討されている。ＰＣＥを用いる場合においては、始点エリアのＰＣＥで通過エリアの特定を行い、各通過エリアのＰＣＥが通過経路を計算する。終点エリア側のＰＣＥから経路計算結果を元に、エリア内のツリーを作成する。作成されたツリーに接続可能なツリーを次のエリアで作成し、終点ノード側から始点ノード側へとツリーを作成する。その後、作成されたツリーを接続して得られる経路のうちの最短経路を選択し、シグナリングによるパス設定を行う。
【０００７】
関連する経路計算方法として、ＢＲＰＣ（Backward Recursive PCE-based Computation）という方法も非特許文献１に開示されている。この方法では、第一経路５と第二経路６の二つの経路を計算することができる。図２０は、ＢＲＰＣを用いた二つの経路の経路計算手法を説明する図である。図２０は、始点ノードから終点ノードに到達するために４つのエリア２（２ａ、２ｂ、２ｃ、２ｄ）を通過する経路を計算する場合であり、各エリア２にＰＣＥ４（４ａ、４ｂ、４ｃ、４ｄ）が備えられている場合を例として説明する。
（１）始点エリアのＰＣＥ４（４ａ）が、エリア２ａの次に経路が通過するエリア２ｂのＰＣＥ４ｂに対してエリア２ｂの経路計算要求を出す。この時点では、シグナリング等は
行われず、経路計算要求が送受信されるに止まる。
（２）ＰＣＥ４ｂは、自エリア２ｂの次に経路が通過するエリア２ｃを制御するＰＣＥ４ｃに対して経路計算要求を行う。ＰＣＥ４ｃも同様の動作を行う。
（３）ＰＣＥ４ｄが経路計算要求を受け取ると、ＰＣＥ４ｄは終点エリア２ｄに備えられているので、自エリアの経路計算を行った後にツリーの作成を行う。ツリー７は、終点ノードとエリア２ｄに存在するノード１ｄを結ぶ経路を意味する。ＰＣＥ４ｄは、ツリーの作成ができると、経路計算応答として、ツリーの情報を、ＰＣＥ４ｃに与える。
（４）ＰＣＥ４ｃは、自エリア２ｃの経路計算を行う。その結果を用いて、エリア２ｃに存在するノード１ｃのうち、エリア２ｄに接続可能なノードとエリア２ｂに接続可能なノードを結ぶツリー７の作成を行い、ツリーの情報を、ＰＣＥ４ｂに与える。ＰＣＥ４ｂも同様の動作を行う。
（５）ＰＣＥ４ａは、ＰＣＥ４ｂからの経路計算応答に応じて、自エリア２ａ内の経路計算を行い、ツリー７を作成する。
（６）ＰＣＥ４ａは、エリア２ａ〜２ｄで得られたツリー情報に基づき、始点ノードから終点ノードまでを結ぶ経路を選択する。このときに、全てのツリーを用いることができるわけではなく、ツリー８のようにツリー８の終点部分と結ぶことができるリソースが次のエリアにない場合は、使用できないツリー８となる。また、既に計算されているツリーから、第一経路５を構成するために用いるツリー７と、第二経路６を構成するために用いるツリー７など複数のツリーを選択することが可能である。ツリーの選択に際して各ツリー７のＣｏｓｔ値を用いることが多い。
【０００８】
特許文献１には、複数に分割されたネットワークにおける経路計算に関連する技術として、伝送ネットワークの伝送制御を行う制御ネットワークに接続され当該伝送ネットワークの伝送設定を行う制御ノードを利用したパス設定方法が開示されている。この制御ノードは、制御ネットワークのリンク情報に基づき、境界制御ノードのいずれか一つを終点ノードの属するエリア方向への出口となる出口ノードとして選択し、その出口ノードまでの経路を伝送ネットワークのリンク情報に基づいて決定する。
【０００９】
また、特許文献２には、同一のエリアに属する境界ノード間に優先度を設け、エリア境界ノード間で協調することで、起点・終点間で主要パスと共有リンクを持たない予備パスを設定する方法が開示されている。
【００１０】
特許文献３には、プロテクションタイプが１＋１である時は、二つの経路のメトリックの和が最小となる互いに排他な経路を計算する方法が開示されている。さらに、プロテクションタイプが１：１もしくは１：Ｎの場合は現用経路に対して排他的な予備経路を確保できる経路の組であることを前提条件として、メトリックが最小の経路を有する組を計算する方法も開示している。
【特許文献１】特開２００７−６０４６１号公報
【特許文献２】特開２００４−８０２１１号公報
【特許文献３】特開２００４−２３１７９号公報
【非特許文献１】http://www.ietf.org/html.charters/pce-charter.htmlA Backward Recursive PCE-based Computation (BRPC) procedure to compute shortest inter-domain Traffic Engineering Label Switched Paths：draft-ietf-pce-brpc-06.txt
【発明の開示】
【発明が解決しようとする課題】
【００１１】
サマライズ情報に含まれる情報は、サマライズの方法によって異なるが、各エリアのリソースの使用状況についての詳細な情報ではない。そのため、プロテクション経路が設定されていても自エリア以外の装置にはプロテクション情報が通知されないなど、サマライ
ズ情報のみから使用できるリソースを正しく判断できない場合がある。そこで、図１９に示した経路計算方法に従って、始点エリアからいくつかのエリア２までの経路計算とシグナリングによるパス設定が成功した場合であっても、次のエリア２でリソース不足により経路計算に失敗する可能性がある。かかる場合には、始点ノードと終点ノードを結ぶ経路を設定することができず、始点エリアから経路の再計算を行う必要が生じる。つまり、図１９で説明した方法は、経路の一部のエリアでパス設定をしても、経路計算に失敗して始点ノードのある発エリアから順番に全ての経路計算をやり直す必要が生ずる場合があるため、効率が悪い。
【００１２】
ＰＣＥを用いた場合や、ＢＲＰＣによる計算では、始点エリアから終点エリアまでの全てのエリアにおいて、終点エリア側からツリー７を作成し、作成されたツリー７を接続して経路を選択した後に、シグナリングによるパス設定を行う。従って図１９を参照して説明した方法のように、経路の途中までパス設定を行った後でリソース不足による再計算を行うことはない。
【００１３】
しかし、ＰＣＥを用いて経路計算を行って複数の経路を求める際には、図２１に示すように、現用経路などの第一経路５を計算して、第一経路５が求められた後に第二経路６の経路計算を行う（ステップＳ１０１〜１０３）。第二経路６を求めるのに失敗すると、再度、第一経路５の計算に戻る（ステップＳ１０４）。ここで、ＰＣＥ４が、エリア２内に複数の経路を設定することを前提に計算していないために、第一経路５として計算された経路以外の経路を確保できなくなる場合がある。かかる場合には、第一経路５も再計算しなければ、複数の経路を確保できず、経路の計算効率が悪くなる。特許文献２でも、主要パスの計算・設定が終了した後に、予備パスの計算を行っている。
【００１４】
ＢＲＰＣを用いて経路計算を行う場合においては、同一のエリアにおいて同時に複数の経路を同時に計算することが可能であり、経路計算の効率化が図られている。しかし、ＢＲＰＣでは、第一経路５と第二経路６が始点から終点まで同じエリアのみを通過する場合でなければ、第一経路５と第二経路６を独立に求めることができないという問題がある。従って、複数の経路を独立に求めようとする場合において、求めようとする経路の一つでも異なるエリアを通過する場合には、ひとつの経路計算が終了した時点で他の経路の計算を行うしかないのが現状である。なお、特許文献３では、分割されていないネットワーク中での複数の経路計算しか開示していない。
【００１５】
本発明の課題は、ネットワークにおいて複数のエリアを通過する複数の経路を設定するための効率的な方法を提供することである。
【課題を解決するための手段】
【００１６】
上記の課題は、複数のエリアに分割されたネットワークにおいて始点ノードと終点ノードを結ぶ二本以上の経路を計算する際に、前記二本以上の経路の少なくとも一つが通過する通過エリアのうち複数の経路が通過する複数経路通過エリアを特定する複数経路通過エリア特定部と、前記二本以上の経路のうちの第一の経路を算出する際に、特定された前記複数経路通過エリアについて、前記複数経路通過エリアを通過する経路の数と同数のエリア内経路を計算するエリア内経路計算部を備える経路計算装置を用いて経路計算を行うことにより解決することができる。
【００１７】
まず、複数経路通過エリア特定部は、複数の経路が通過するエリアを抽出して、複数の経路を計算する必要があるエリアを特定する。この装置のエリア内経路計算部は、抽出した複数経路通過エリア（競合エリア）の経路計算を行うときには、その複数経路通過エリアを通過する経路の数以上のエリア内の経路を計算する。
【発明の効果】
【００１８】
同時に通過する経路の数と同数の経路を計算することにより、複数経路通過エリアについて、第一の経路を計算するときに複数の経路を通過させることを考慮せずに経路計算を行ったために２本目以降の経路計算をするときに生じるリソース不足を防ぐことができる。また、抽出した複数経路通過エリアについて複数の経路を計算する構成にしているので、異なるエリアを経由する複数の経路についても独立な経路を計算することができる。
【００１９】
従って、本発明にかかる方法により、ネットワークにおいて複数のエリアを通過する複数の経路を効率的に設定することができる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明の実施形態について、図面を参照しながら詳細に説明する。
＜経路計算の概要＞
図１は、複数のエリアに分割されたネットワークと複数の経路の例を示す図である。図１では、７つのエリア２（Ａ１、Ａ２、Ａ３、Ａ４、Ａ５、Ａ６、Ａ７）を含むネットワークにおいて、始点ノードＳ１と終点ノードＤ１を結ぶ第一経路５と第二経路６の二つの経路を計算する場合を例として示している。以下、図１のネットワークにおいて、第一経路５および第二経路６を計算する場合を例として、本発明の実施形態に係る経路計算の概要を説明する。
【００２１】
本発明の実施形態に係る経路計算を行う前提として、各エリア２（Ａ１〜Ａ７）の情報の概要がサマライズ情報として他のエリアの装置に通知されているものとする。従って、各エリアの装置は、自装置が存在するエリア（自エリア）の詳細な情報と、自エリア以外のエリアのサマライズ情報を有する。ここでは、サマライズ情報として、エリア間のリンク情報がエリアＩＤと境界ノードＩＤを用いて交換されているとする。
【００２２】
（１）始点エリアＡ１の経路計算装置は、第一経路５と第二経路６の各々について、始点ノードＳ１から終点ノードＤ１に到達するまでに経由するエリア２を特定する。この特定を行う際には、サマライズ情報が用いられる。図１の例では、第一経路５は、Ａ１、Ａ２、Ａ４、Ａ５、Ａ７を通過する経路であり、第二経路６はＡ１、Ａ３、Ａ４、Ａ６、Ａ７を通過する経路である。ここで、エリア２の特定方法としては、任意の既知のエリア経路計算法を用いることができる。
【００２３】
（２）始点エリアＡ１の経路計算装置は、第一経路５と第二経路６の各々が通過するエリア２のＩＤを確認して、同一のエリア２が存在するかを調べる。同一のエリア２を通過する場合には、競合エリアとして抽出する。ここで、「競合エリア」とは、複数の経路が通過するエリア２のことであり、「複数経路通過エリア」と同義である。
【００２４】
（３）Ａ１の経路計算装置は、第一経路５の計算のための経路計算要求メッセージを、隣接するエリアＡ２の経路計算装置に対して送信する。このときに、経路計算要求メッセージには、通過するエリア（Ａ１、Ａ２、Ａ４、Ａ５、Ａ７）と、競合エリア（Ａ１、Ａ４、Ａ７）の情報を含めておく。
【００２５】
（４）経路計算要求メッセージを受信したＡ２の経路計算装置は、次の通過エリアであるＡ４の経路計算装置へメッセージを転送する。Ａ４、Ａ５の経路計算装置も同様の動作を行い、Ａ７の経路計算装置まで経路計算要求メッセージが送られる。
【００２６】
（５）終点エリアＡ７の経路計算装置は、経路計算要求メッセージを受け取ると、自エリア（Ａ７）の詳細情報を用いて、自エリア内のエリア内経路を計算する。このとき、Ａ７は競合エリアに該当するため、第一経路５と第二経路６のそれぞれに対しての経路を確
保する必要がある。経路計算装置は、第一経路用の経路を計算する際に、第二経路６で用いるための経路も詳細に計算する。
【００２７】
（６）Ａ７の経路計算装置は、第一経路５と第二経路６のために計算した二本の経路の計算結果を経路計算応答メッセージに書き込んで、第一経路５が通過するエリアであるＡ５に送信する。Ａ５は、経路計算応答メッセージを受け取ると、自エリアの詳細経路を計算する。Ａ５は、第一経路５のみが通過するので、一つの経路のみが計算される。
【００２８】
（７）Ａ５の経路計算装置の計算結果は、経路計算応答メッセージにさらに書き込まれてＡ４の経路計算装置に渡される。Ａ４、Ａ２、Ａ１も同様に経路計算を行う。なお、Ａ１とＡ４は競合エリアであるので、第一経路５と第二経路６の両者のための経路が計算され、Ａ２では第一経路５の経路のみが計算される。
【００２９】
（８）始点エリアであるＡ１は、自エリアでの経路計算を行った結果と、他のＡ２、Ａ４、Ａ５、Ａ７における計算結果とを有する。そこで、Ａ１の経路計算装置は、始点ノードＳ１から終点ノードＤ１に至る第一経路５が詳細経路として求まったかを確認する。始点ノードＳ１から終点ノードＤ１に至る経路の計算に失敗した場合には、手順（１）〜（８）を再度行う。
【００３０】
（９）第一経路５の計算に成功すると、次に第二経路６の計算が行われる。Ａ１の経路計算装置は、第二経路６の計算を行うための経路計算要求メッセージを第二経路６が通過するエリアに送信する。この経路計算要求メッセージには、第二経路が通過するエリア（Ａ１、Ａ３、Ａ４、Ａ６、Ａ７）と競合エリア（Ａ１、Ａ４、Ａ７）の情報が含まれる。競合エリアにおいては、第一経路５を計算したときに第二経路６のための経路を計算しているので、計算を行う必要がない。そこで、経路計算要求メッセージは、競合エリア以外のエリアにおいて、経路計算を要求するメッセージとして扱われる。
【００３１】
（１０）経路計算要求メッセージを受信した経路計算装置は、第一経路５の場合と同様に、第二経路６の通過順に経路計算要求メッセージを送信する。終点ノードＤ１が存在するＡ７の経路計算装置は、競合エリアであるので、経路計算要求メッセージを受信しても、自エリア内の経路計算を行わずに、経路計算応答メッセージをＡ６に送信する。
【００３２】
（１１）Ａ６は競合エリアではないので、経路計算要求メッセージに応答して自エリアの経路計算を行い、計算結果を経路計算応答メッセージに書き込んで、Ａ４に送信する。Ａ４は経路計算応答メッセージをＡ３に送り、Ａ３が自エリアの経路計算結果を経路計算応答メッセージに書き込んで始点エリアＡ１に送る。
【００３３】
（１２）始点エリアＡ１は、第一経路５の計算のときに競合エリアに対して計算された経路で第一経路５に使用しなかった経路と、競合エリアではないＡ３、Ａ６から通知された経路情報を用いて第二経路６が詳細経路として求まったかを確認する。
【００３４】
（１３）第二経路６の計算に失敗した場合には、第一経路５と第二経路６の両者について計算しなおすため、手順（１）から再計算を行う。
（１４）第一経路５と第二経路６の両者が求まっている場合には、それぞれの経路において、始点ノードＳ１から終点ノードＤ１に向けてシグナリングを行って、それぞれの経路を設定する。
【００３５】
なお、上記の説明で、エリア２や競合エリアの特定を行う装置を始点エリアＡ１の経路計算を行なう装置としたのは、理解を助けるために過ぎない。従って、他の装置がエリア２等の特定を行う構成にしても良い。かかる場合、エリア２などの特定を行った装置は、
経路計算要求を出す装置に対して、必要に応じて特定した情報を送信する。
【００３６】
上記のように、複数の経路が通過する競合エリアでは、第一経路５の計算時に複数の経路が通過することを前提として計算を行うため、競合エリアにおいて一本の経路のみに最適な経路を検索したことに起因するリソース不足を解消することができる。また、後で詳しく述べるように、エリア２内の経路を計算する際に既存の経路計算アルゴリズムを用いて、ノード独立、リンク独立などの制約条件を課すことができる。これにより、第一経路５と第二経路６がそれぞれ異なるエリア２を通過する場合においても、独立性が担保されている経路を計算することが可能である。また、シグナリングを行うのは、第一経路５と第二経路６の両者が求まった後であるので、経路を一部設定した後に、経路計算に失敗することがなく、無駄な経路設定を行うことがない。
【００３７】
＜経路計算装置の概要＞
図２は、実施形態の経路計算装置の構成の例を示す図である。経路計算装置１０は、回線１１、インターフェイス部１２、スイッチ部１３、装置内監視制御部２０を備える。経路計算を行う部分は経路計算部（ＰＣＥ、Path Computation Element）であり、ルーチング制御部２３に含まれる。経路計算部については後に詳しく述べる。経路計算装置１０の接続環境や使用状況に応じて、回線１１、インターフェイス部１２、スイッチ部１３の構成が異なるが、装置内監視制御部２０の構成は基本的に、同一である。インターフェイス部１２は、スイッチ部１３側と、他の装置との間を結んでおり、装置内監視制御部２０の指示に従って、他のノードとシグナリングメッセージなどの送受信を行う。また、スイッチ部１３は、パスの設定に用いられ、スイッチ部１３の設定を変更することにより、経路計算後のパス設定を行う。
【００３８】
装置内監視制御部２０は、経路計算装置１０の管理、制御を行う。装置内監視制御部２０は、装置管理部２１、シグナリング制御部２２、ルーチング制御部２３、警報管理部２４、性能管理部２５、パス管理部２６を備える。経路計算を行う経路計算部は、図３を参照しながら後述するように、複数の部分から構成されるハードウェア回路として実現されるが、ルーチング制御部２３に含まれている各部分の機能を用いて、ソフトウェアによって実現されることもある。
【００３９】
装置管理部２１は、経路計算装置１０において経路計算装置自体の制御全般を行う。シグナリング制御部２２は、経路計算装置１０が受信もしくは送信するシグナリングメッセージの制御を行う。ルーチング制御部２３は、経路計算装置１０が有するルーチング機能の制御を行う。警報管理部２４は、伝送路障害などを監視しており、警報の発出および抑止の制御、警報重要度の設定・変更を行う。性能管理部２５は、性能情報の記録、変更、更新、クリアなど、性能情報に対する制御を行う。パス管理部２６は、パスの状態を管理し、必要に応じてパスの状態を記録したデータベースを備える。なお、実施形態によって、シグナリング制御部２２やルーチング制御部２３を別個の装置として経路計算装置１０の本体と接続・分離が可能な構成とすることもできる。装置内監視制御部２０の各構成部分は、例えば、ハードウェア回路により実現される。ただし、これらの機能の一部または全部をソフトウェアにより実現するようにしてもよい。
【００４０】
図３は、実施形態の経路計算装置における経路計算部の構成例を示す図である。経路計算部３０は、エリア間ルーチング処理部３１、エリア間経路計算部３２、エリア内ルーチング処理部３３、エリア内経路計算部３４、および、経路計算管理部３５を備える。
【００４１】
エリア間ルーチング処理部３１は、ＯＩＦ  Ｅ−ＮＮＩルーチングプロトコル（Optical Internetworking Forum External Network Node Interface）等のルーチングプロトコルを使用してエリア間のリンク情報（ＴＥ  Ｌｉｎｋ、Traffic Engineering Link）や他
エリアのサマライズ情報を交換する。また、エリア間ルーチング処理部３１はメモリ機能を有し、情報交換などで得られた情報を記憶し、必要に応じて他の部分に提供する。例えば、図１の７つのエリア（Ａ１〜Ａ７）についてのサマライズ情報をそれぞれのエリアを管理する経路計算装置１０のエリア間ルーチング処理部３１同士で交換し、記憶している。
【００４２】
サマライズ情報は、エリア２の情報のサマライズ方法によって様々な形態となる。例えば、エリア間のリンク情報のみが含まれるサマライズ情報であっても、境界ノードＩＤ、エリアＩＤ、使用可能帯域などの一つ以上の情報を交換する形にすることができる。また、エリア２の境界ノード間の接続可能な境界ノード同士に仮想的にリンクを作成して交換することができる。例えば、図１のエリアＡ１のＡ１−１というノードと隣接するエリアＡ２のＡ２−１というノードが接続可能である場合に、仮想リンクを作成し、エリア間のリンク情報と共に交換することができる。このときに、仮想リンクの接続情報のみの交換、接続性および使用可能帯域の交換、さらには、接続性、使用可能帯域の情報に加えて詳細な情報も交換する構成も可能である。
【００４３】
エリア間経路計算部３２は、エリア間ルーチング処理部３１が有するエリア情報を用いて、エリア間経路を決定する。すなわち、第一経路５や第二経路６などの経路が通過するエリアを特定する。ここで、「エリア間経路」とは、ある経路がどのエリアをどの順番で通過するかという情報である。例えば、図１に示した第一経路５はＡ１、Ａ２、Ａ４、Ａ５、Ａ７の順にエリアを通過するということが、エリア間経路の計算結果である。エリア間経路計算部３２は、エリア間ルーチング処理部３１が記憶しているエリアＡ１〜Ａ７のサマライズ情報を用いて、エリア間経路の計算を行う。なお、サマライズ情報としてエリアの境界ノードが与えられている場合には、エリア間経路計算部３２は、検索した通過エリアの境界に位置するノード１のＩＤとしてエリア間経路計算結果を出力する構成にすることもできる。さらに、エリア間経路計算部３２は、必要に応じてエリア内経路計算結果などを格納しておく記憶領域を備える。
【００４４】
エリア内ルーチング処理部３３は、ＯＳＰＦ−ＴＥ（Open Shortest Path First - Traffic Engineering）やＩｎｔｅｇｒａｔｅ  ＩＳ−ＩＳ(Integrate Intermediate System-to-Intermediate System）などのルーチングプロトコルを使用してエリア内のリンク情報（ＴＥ  Ｌｉｎｋ）を交換する。また、エリア内ルーチング処理部３３は得られた情報を保持する記憶機能を有し、必要に応じてエリア内経路計算部３４などに提供する。
【００４５】
エリア内経路計算部３４は、エリア内ルーチング処理部３３によって収集された自エリア内のトポロジ情報を基に、自エリア内の詳細な経路計算を行う。エリア内経路計算部３４が行う自エリア内の経路計算では、経路が通過するノード１や通過順序など、エリア内を通過する経路の詳細を決定する。エリア内の経路計算の方法は、ｋ−ｓｈｏｒｔｅｓｔ
ｐａｔｈアルゴリズムなど、任意の既知の経路計算方法を用いることが可能である。ただし、一度に複数の経路を計算することが可能なアルゴリズムを使用することが望ましい。経路計算に際して、エリア内経路計算部３４がエリア内ルーチング処理部３３に対してトポロジ情報を要求する構成にすることもできる。
【００４６】
経路計算管理部３５は、経路計算装置１０が行う経路計算の制御や経路計算部３０の他の各部分に対する処理の振り分けを管理する。例えば、経路計算装置１０が自エリア内の経路計算を行う際には、経路計算が必要であることを認識した経路計算管理部３５が、エリア内経路計算部３４に対して計算を要求する。また、エリア内ルーチング処理部３３に対して、経路計算を行うのに必要な情報をエリア内経路計算部３４に渡すように指示する構成にすることも可能である。さらに、経路計算応答メッセージ５０に含まれている経路計算結果を基にして、第一経路５や第二経路６が求められたかの判断も、経路計算管理部
３５が行う。この判断は前述のとおり、始点ノードＳ１など始点エリアに存在する装置で行われることが多いが、他のノード１において経路計算管理部３１が行う構成にすることも可能である。経路計算管理部３５に経路決定部を備えることができ、この経路決定部が、経路計算結果に基づいて第一経路５や第二経路６を決定する構成にすることもできる。経路計算管理部３５は、エリア間経路計算部３２が決定したエリア間経路を用いて競合エリアの特定も行う。ここで、競合エリアの特定を行う複数経路通過エリア特定部を、経路計算管理部３５の内部に備える構成にすることもできる。
【００４７】
経路計算部３０の構成は、以上に述べたものには限られず、経路計算装置１０の実施形態によって様々である。例えば、エリア間ルーチング処理部３１とエリア間経路計算部３２を含んでいるエリア間経路計算処理部３６とすることができる。同様に、エリア内ルーチング処理部３３、エリア内経路計算部３４、および、経路計算管理部３５を一つの部分としてエリア内経路計算処理部３７とすることも可能である。
【００４８】
＜経路計算の実施形態（１）＞
以下に経路計算の実施形態の例を詳しく説明する。
〔第一経路の計算時の経路計算部の動作〕
まず、第一経路５の計算時に、経路計算部３０が行う動作を説明する。図４は、経路計算の際に経路計算部が行う動作を説明する図である。図４は、図１に示したネットワークのうち、エリアＡ１、Ａ２、Ａ７の部分を示している。また、エリア間経路計算処理部３６とエリア内経路計算処理部３７が別の装置に含まれるものとして表している。エリア２に存在するノード１の全てが経路計算機能を有していない場合もあり、図４では、経路計算機能を有さないノードをネットワークエレメント３８（ＮＥ）として表示している。
【００４９】
（１）エリア間ルーチング処理部３１が他のエリア２のエリア間経路計算処理部３６に含まれるエリア間ルーチング処理部３１とサマライズ情報を交換する。このサマライズ情報を用いて、始点エリアＡ１の経路計算装置１０に備えられたエリア間経路計算部３２が、第一経路５と第二経路６のそれぞれについて、始点ノードＳ１から終点ノードＤ１までに通過するエリアを計算する。
【００５０】
経路計算管理部３５は、エリア間経路計算部３２の計算が終わると、エリア間経路計算結果を用いて、複数の経路が通過する競合エリアの抽出を行う。経路計算管理部３５は、第一経路５が通過するエリアＡ１、Ａ２、Ａ４、Ａ５、Ａ７と、第二経路６のＡ１、Ａ３、Ａ４、Ａ６、Ａ７のエリアＩＤを比較し、Ａ１、Ａ４、Ａ７が競合エリアであると抽出する。競合エリアの抽出が終わると、経路計算管理部３５は、経路計算要求メッセージを作成してエリア間経路計算部３２に送り、経路計算要求を行う。
【００５１】
図５は、経路計算要求メッセージ４０の例を示す図である。経路計算要求メッセージ４０は、パスＩＤ情報４１、始点ＩＤ情報４２、終点ＩＤ情報４３、帯域情報４４、通過エリア情報４５、競合エリア情報４６などを備える。経路計算要求メッセージ４０は、第一経路５の計算を要求する際の経路計算要求メッセージ４０である。
【００５２】
（２）エリアＡ１のエリア間経路計算部３２は、経路計算管理部３５から受け取った経路計算要求メッセージ４０を確認する。経路計算要求メッセージ４０の通過エリア情報４５には、自エリアであるＡ１の次にエリアＡ２が指定されている。そこで、次の通過エリアであるＡ２のエリア間経路計算処理部３６に経路計算要求メッセージ４０を送信する。エリアＡ２のエリア間経路計算処理部３６でも、エリア間経路計算部３２が経路計算要求メッセージ４０を受信する。
【００５３】
（３）エリア間経路計算部３２は、受信した経路計算要求メッセージ４０の通過エリア
情報４５を参照して、自エリアの次の通過エリアへ経路計算要求メッセージ４０を送信する。この工程を繰り返し、終点エリアであるＡ７のエリア間経路計算処理部３６のエリア間経路計算部３２に経路計算要求メッセージ４０が送信される。
【００５４】
（４）終点エリアＡ７を管理するエリア間経路計算処理部３６のエリア間経路計算部３２は、経路計算要求メッセージ４０を確認する。自エリアが終点エリアであることを認識すると、自エリアを管理するエリア内経路計算処理部３７に含まれている経路計算管理部３５にエリア内経路計算を行うように要求する。
【００５５】
（５）エリア内経路計算要求を受けた経路計算管理部３５は、経路計算要求メッセージ４０を参照し、自エリアが競合エリア情報４６に指定されているかを確認する。競合エリア情報４６により、終点エリアＡ７を第一経路５と第二経路６が通過するので二本の経路を計算する必要があることが分かる。そこで、経路計算管理部３５は、エリア内経路計算部３４に、二本のエリア内経路の計算をするように要求する。
【００５６】
エリア内経路計算部３４は、エリア内ルーチング処理部３３が有するトポロジ情報を用いてエリア内経路を計算する。ここでの計算には、ｋ−ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムなど、複数の経路を計算可能な既知の方法を用いることができる。
【００５７】
エリア内経路計算部３４は、計算した結果を経路計算管理部３５に報告し、経路計算管理部３５がエリア間経路計算部３２に報告する。エリア間経路計算部３２は、受け取ったエリア内経路計算の結果から境界ノードを抽出して計算結果として格納する。例えば、図１のように、終点ノードＤ１からＡ７−１に到達する経路と、終点ノードＤ１からＡ７−２に到達する経路が見つかった場合には、「Ｄ１，Ａ７−１」および「Ｄ１，Ａ７−２」として格納される。
【００５８】
（６）エリアＡ７のエリア間経路計算処理部３６は、経路計算要求メッセージ４０に経路計算結果を加えた経路計算応答メッセージ５０を作成する。図６は経路計算応答メッセージ５０の例を示す図である。Ａ７のエリア間経路計算処理部３６は、第一経路５の通過するエリアＡ５のエリア間経路計算処理部３６に経路計算応答メッセージ５０を送信する。
【００５９】
（７）経路計算応答メッセージ５０を受信すると、エリアＡ５のエリア間経路計算処理部３６に含まれるエリア間経路計算部３２が、エリアＡ５の経路計算管理部３５に経路計算要求を行う。
【００６０】
（８）エリア内経路計算要求を受けた経路計算管理部３５は、経路計算要求メッセージ４０を参照して自エリアが競合エリアではないことを確認し、エリア内経路計算部３４に対して、一本のエリア内経路を計算するように要求する。
【００６１】
計算要求を受けたエリア内経路計算部３４は経路計算を行い、計算結果を経路計算管理部３５に報告する。経路計算管理部３５は、経路内計算結果から手順（５）で述べたのと同様に計算結果を格納する。
【００６２】
（９）Ａ５のエリア間経路計算処理部３６は、Ａ７から受信した経路計算応答メッセージ５０の経路計算結果情報５１部分に、格納したエリア内経路計算結果を付け加え、経路計算応答メッセージ５０を作成する。例えば、Ａ５において、境界ノードＡ５−２とＡ５−１を結ぶ経路が発見された場合であれば、経路計算結果情報５１は
（Ｄ１）−（Ａ７−１），（Ｄ１）−（Ａ７−２），（Ａ５−２）−（Ａ５−１）
と記載される。エリア間経路計算処理部３６は、作成した経路計算応答メッセージ５０を
通過エリアＡ４に送信する。通過エリアＡ４、Ａ２においても、これまで述べたのと同様の計算と経路計算応答メッセージ５０の送信が行われる結果、始点エリアＡ１のエリア間経路計算処理部３６に経路計算応答メッセージ５０が送信される。
【００６３】
（１０）始点エリアＡ１のエリア間経路計算処理部３６は、経路計算応答メッセージ５０を受け取ると、手順（５）と同様に動作する。
（１１）始点エリアＡ１の経路計算管理部３５は、Ａ１のエリア内経路計算結果、および、通過エリアＡ２から受信した経路計算応答メッセージ５０に記載されている経路計算結果情報５１から、第一経路５を決定する。経路計算結果情報５１には競合エリアについて複数の経路が記録されているが、経路計算管理部３５はエリア内ルーチング処理部３３の有するサマライズ情報を適宜使用し、どの経路を第一経路５に使用するかを決定する。
【００６４】
ここで説明した例では、図５に示したように、エリアＩＤを用いて第一経路５の通過エリアと競合エリアを指定した経路計算要求メッセージ４０を用いて経路計算をしている。つまり、第二経路６については競合エリア以外の情報が経路計算要求メッセージ４０に記載されていないため、競合エリアからどのエリアに向かう経路を第二経路６のために計算するかの指定がない。従って、競合エリアから到達可能な隣接エリアが２つ以上ある場合には、経路計算対象となっているエリアについて設定されている条件に従って経路計算をすることになる。この条件としては、上流側のエリアを優先的に計算するなど、任意の設定を行うことができ、経路計算装置１０などに設定を記憶させることができる。
【００６５】
｛詳細条件を加えた場合の経路計算｝
前述の例では、競合エリア内の第二経路６についての条件を加えなかったが、第二経路６が通過するノード１を指定して経路計算を行うこともできる。図７は、Ａ４−２とＡ４−４の二つの通過ノードを通過するように指定する場合の経路計算要求メッセージ４０の例を示す図である。通過ノード情報４７を有する経路計算要求メッセージ４０が使用された場合には、経路計算管理部３５が、自エリア内に通過ノード情報４７で指定されたノード１が存在するかを確認する。例えば、図７に示した経路計算要求メッセージ４０に対する経路計算応答メッセージ５０をエリアＡ４のエリア間経路計算部３２が受け取ると、エリア間経路計算部３２は経路計算管理部３５に経路計算依頼を行う。経路計算管理部３５は、エリア内ルーチング処理部３３が保持しているデータを参照して、Ａ４−２とＡ４−４が自エリアに存在することを確認する。自エリア内に通過ノード情報４７で指定されたノード１が存在する場合には、経路計算管理部３５は、エリア内経路計算部３４への計算要求に際して通過ノード情報４７も通知する。通過ノード情報４７を通知されたエリア内経路計算部３４は、第二経路６の経路計算をする際に、指定されたノード１を通過する経路を検索する。
【００６６】
なお、第一経路５についても同様に通過経路情報４８を用いて、通過するノードを指定して、経路計算を行うこともできる。図８は、通過経路情報を指定したときの第一経路の計算要求の例を示した図である。図８の例では、第一経路５がエリアＡ１を通過する際に始点ノードＳ１からＡ１−２に到達する経路をとるように指定されている。第一経路５の通過経路情報４８が指定された場合にも、エリア内経路計算部３４や経路計算管理部３５は、通過ノード情報４７が指定された場合と同様の処理を行う。
【００６７】
また、第一経路５と第二経路６の計算条件を含めて経路計算を行うこともできる。計算条件の例としては、ノード独立、リンク独立、ＳＲＬＧ（Shared Risk Link Group）独立などがある。ここで、ノード独立条件は、第一経路５と第二経路６で同一のノード１を通過しないという条件、リンク独立条件は、第一経路５と第二経路６が同一のリンクを通過しない条件である。ＳＲＬＧ独立条件は、同一管路に収容されているなどの同じリスクを共有するリンクを、第一経路５と第二経路６が共有しないという条件を指す。
【００６８】
これらの条件は、経路計算要求メッセージ４０に制約条件情報４９として図９に示すように記録される。また、各エリアの経路計算装置１０について計算条件と優先順位を記憶させておき、経路計算要求メッセージ４０に制約条件情報４９の指定がない場合には、優先順位が１番目の条件を、デフォルト条件として計算条件に使用する構成にすることもできる。経路計算管理部３５が、制約条件情報４９を確認し、エリア内経路計算部３４に計算要求をする際に制約条件情報４９の内容を伝える。エリア内経路計算部３４は、制約条件情報４９の条件を設定してエリア内経路計算を行う。例えば、ｋ−ｓｈｏｒｔｅｓｔ  ｐａｔｈアルゴリズムの設定を利用して、これらの条件設定を行うことができる。
【００６９】
これらの詳細条件を設定して経路計算を行うことができることにより、使用目的やリスクの大きさに応じて複数の経路を計算することができる。
〔第二経路計算時の経路計算部の動作〕
第一経路５の経路計算が成功した場合、第二経路６の計算を行う。以下、第二経路６を計算するときの経路計算部３０の動作について、図４を参照しながら詳しく述べる。以下の説明では、第一経路５を計算したときの計算により、第一経路５と競合エリア中で第二経路６に用いるための経路を求めることができているものとする。
【００７０】
（１２）経路計算管理部３５は、第一経路５を求めるのに成功すると、第一経路５の計算の際に得られた結果を用いて第二経路６を計算するための経路計算要求メッセージ６０を作成する。
【００７１】
図９は、第二経路６を計算する際の経路計算要求メッセージ６０の例を示す図である。対応する第一経路５の計算に用いた経路計算要求メッセージ４０も合わせて示す。経路計算要求メッセージ６０は、経路計算要求メッセージ４０と同様にパスＩＤ情報６１、始点ＩＤ情報６２、終点ＩＤ情報６３、帯域情報６４、通過エリア情報６５、競合エリア情報６６を備える。第二経路６の計算に用いる経路計算要求メッセージ６０は第一経路５の計算の際の経路計算要求メッセージ４０とほぼ同じであるが、通過エリア情報６５が第二経路用のエリア間経路情報である点と、通過経路情報６７を有する点が異なる。
【００７２】
第一経路５を計算したときに、競合エリアにおいては、既に第二経路６に使用する経路が計算されていて、第一経路５を決定する際の経路計算応答メッセージ５０の経路計算結果情報５１として、始点エリアＡ１の経路計算管理部３５に通知されている。そこで、経路計算管理部３５は、経路計算結果情報５１に含まれていた経路のうち、第一経路５に使用しなかった経路を、通過経路情報６７として記載した経路計算要求メッセージ６０を作成する。経路計算管理部３５は、作成した経路計算要求メッセージ６０をエリア間経路計算部３２に送る。
【００７３】
（１３）エリア間経路計算部３２は、第一経路５の計算のときと同様に、第二経路６での、次の通過エリアのエリア間経路計算処理部３６に経路計算要求メッセージ６０を送信する。図９の例では、次の通過エリアはＡ３である。経路計算要求メッセージ６０を受信したエリア間経路計算処理部３６は、次の通過エリアのエリア間経路計算処理部３６へと経路計算要求メッセージ６０を送っていき、終点エリアのエリア間経路計算処理部３６に経路計算要求メッセージ６０が送られる。
【００７４】
（１４）終点エリアＡ７のエリア間経路計算処理部３６が経路計算要求メッセージ６０を受け取ると、エリア間経路計算部３２は、自エリアについて通過経路情報６７が指定されているかを確認する。終点エリアＡ７は通過経路情報６７が指定されているので、エリア間経路計算部３２は経路計算管理部３５にエリア内計算要求を行わない。エリア間経路計算部３２は、通過経路情報６７に指定されている経路とエリア間経路計算部３２が格納
している経路を比較する。両者が一致する場合は、指定された経路の確保が可能であることを通知するために、経路計算応答メッセージを第二経路６の通過エリアであるＡ６のエリア間経路計算処理部３６に送信する。ここで送信される経路計算応答メッセージは、経路計算要求メッセージ６０の末尾に、エリア間経路計算部３２が格納していた経路のうち経路計算要求メッセージ６０で指定された経路を記載したものである。
【００７５】
（１５）エリアＡ６は競合エリアでないことを、エリアＡ６を管理するエリア間経路計算処理部３６に備えられたエリア間経路計算部３２が確認すると、エリア間経路計算部３２はエリア内経路計算要求を経路計算管理部３５に対して行う。その後で行われる動作は手順（８）〜（９）での説明と同様である。
【００７６】
エリアＡ６での経路計算が終わると、経路計算応答メッセージ５０がＡ４に送信される。その後、エリアＡ４では手順（１４）で説明したのと同様の処理が行われ、Ａ３ではＡ６で行われたのと同様の処理がなされ、始点エリアＡ１に経路計算応答メッセージ５０が送られる。
【００７７】
（１６）始点エリアＡ１は、競合エリアであるので、Ａ１のエリア内経路はエリア間経路計算部３２に格納されている。そこで、エリア間経路計算部３２は、格納しているエリア内経路情報と、通過エリアＡ２から受信した経路計算応答メッセージに記載されている経路計算結果情報から、第二経路６を決定する。
【００７８】
（１７）第一経路５と第二経路６の計算に成功すると、始点エリアの経路計算管理部３５は、経路計算装置１０のシグナリング制御部２２に、経路計算結果を通知する。通知を受けると、シグナリング制御部２２は、始点ノードＳ１から終点ノードＤ１までの経路のシグナリングを行い、経路を設定する。
【００７９】
なお、第二経路６についても、第一経路５と同様に、詳細条件を設定して計算を行うことも可能である。
また、第二経路６を計算するための経路計算要求メッセージ６０を作成する際に、通過経路情報６７を経路計算要求メッセージ６０に含めない構成にすることもできる。この場合は、エリア間経路計算処理部３６が経路計算要求メッセージ６０を受け取ると、エリア間経路計算部３２は、自エリアが競合エリアであるかを競合エリア情報６６によって確認する。競合エリアであれば、エリア間経路計算部３２は経路計算管理部３５にエリア内計算要求を行わない。エリア間経路計算部３２は、格納している結果を経路計算要求メッセージ６０の末尾に付した経路計算応答メッセージを、第二経路６の通過エリアであるＡ６のエリア間経路計算処理部３６に送信する。このような形態にすれば、通過経路情報６７を指定しなくても、経路計算応答メッセージ５０によって始点エリアの経路計算装置１０に送られた競合エリアの経路を用いて経路の決定をすることができる。
【００８０】
本実施形態で説明したように、第一経路５と第二経路６の両者が通過する競合エリアについては、同時に二本の経路を計算することにより、二本の経路を通過させる場合の最適経路を計算することができる。従って、競合エリアにおいて、一本目の経路をまず計算してから二本目の経路を計算したときのように、一本の最適経路を確保したために、リソース不足で他の経路を確保できなくなる可能性を低くすることができる。また、複数経路の計算を行うかを指定するのは、エリアごとである。このため、ＢＲＰＣを用いたときのように、複数の独立な経路を探すためには、第一経路５と第二経路６の通過エリアを全て同じにしなくてはならないという制約を受けない。
【００８１】
＜経路計算の実施形態（２）＞
実施形態（１）では、第一経路５と第二経路６の両方について、経路計算が成功した場
合について述べた。しかしながら、第一経路５の経路の計算に成功しても、競合エリアにおいて第二経路６に用いるための経路の計算に失敗することもあり得る。第二経路６の計算に失敗した場合には、第二経路６に使用するための代替となる経路を計算する必要がある。
【００８２】
以下に、図１０のネットワークにおいて第二経路６の経路計算に失敗した場合を例として、経路計算の失敗の報告と、第二経路用の代替経路の計算について詳しく述べる。例として、競合エリアＡ２で、第二経路６に用いるための経路計算に失敗したとする。図１１は複数の経路の検索に失敗する競合エリアＡ２の例を示す図である。エリアＡ２では、ノード１がＡ２−１からＡ２−９の９個のノードで構成されているとする。第二経路６は、通過ノード情報４７でＡ２−３を指定することにより、Ａ２からＡ３に到達する経路を計算するように指定され、さらに、第一経路５とノード独立であることを条件とされているものとする。なお、境界ノード指定を行って経路計算を行う場合や他の計算条件を用いて第二経路６の通過エリアを指定する場合も同様の方法を用いることができる。
【００８３】
〔経路計算の失敗報告と代替経路計算〕
第一経路５および競合エリアの計算を開始するために経路計算部３０が行う動作は、実施形態（１）で説明した手順（１）〜（９）と同様である。
【００８４】
（１）Ａ２にＡ４を管理しているエリア間経路計算部３２から経路計算応答メッセージ５０が送信されることにより、Ａ２での経路計算が開始される。Ａ２の経路計算管理部３５は、経路計算要求メッセージ４０を参照し、自エリア（Ａ２）が競合エリアであることを確認する。その後、経路計算管理部３５は、エリア内経路計算部３４に、二本のエリア内経路の計算をするように要求し、合わせて第二経路６の計算条件を通知する。
【００８５】
エリア内経路計算部３４は、第一経路５としてエリアＡ１からＡ４に到達する経路、第二経路６としてエリアＡ１からＡ３に到達する経路を計算しようと試みる。なお、ノードＡ２−４とＡ２−７の間には、経路計算要求メッセージ４０で要求されている帯域情報４４をみたす帯域については空きがないとする。この場合、エリア内経路計算部３４は、第一経路用に、ノードＡ２−５、Ａ２−４、Ａ２−１を通過する経路を計算できる。しかし、第二経路６を第一経路５とノード独立にするためには、ノードＡ２−３、Ａ２−２、Ａ２−１の経路をとることができない。また、ノードＡ２−４とＡ２−７の間を通過する経路をとることもできないので、エリア内経路計算部３４は、第二経路６に用いるためのエリア内経路の計算に失敗する。
【００８６】
（２）エリア内経路計算部３４は、第一経路５について計算した結果と第二経路６に用いるための経路計算に失敗したことを、経路計算管理部３５を通してエリア間経路計算部３２に報告する。エリア間経路計算部３２は、受け取ったエリア内経路計算の結果から境界ノード情報を抽出して格納する際、経路計算に失敗した第二経路６については経路計算ができなかったことを記録しておく。例えば、第一経路５はノードＡ２−５、Ａ２−４、Ａ２−１を通過し、第二経路６が見つからなかった場合には、「（Ａ２−５）−（Ａ２−１）」および「ＮＯＮＥ」として格納される。
【００８７】
（３）エリアＡ２のエリア間経路計算処理部３６は、経路計算に成功したときと同様に、経路計算要求メッセージ４０に経路計算結果を加えた経路計算応答メッセージ５０を作成する。図１２は、第二経路６の経路計算に失敗したことを示す経路計算応答メッセージ５０の例を示す図である。Ａ２のエリア間経路計算処理部３６は、始点エリアＡ１のエリア間経路計算処理部３６に経路計算応答メッセージ５０を送信する。経路計算応答メッセージ５０を受信した始点エリアＡ１では、既に述べたのと同様に第一経路５と第二経路６の計算が行われる。
【００８８】
（４）始点エリアＡ１の経路計算管理部３５は、実施形態（１）で説明した手順（１１）と同様に第一経路５の経路決定を行う。一方、第二経路６については、経路計算応答メッセージ５０に「ＮＯＮＥ」が記録されていて、競合エリアにおいて、経路計算に失敗したことを認識する。そこで、第二経路６はエリア間経路計算をやり直す必要があるため、経路計算管理部３５はエリア間経路計算部３２に、第二経路６のエリア間経路の再計算を要求する。
【００８９】
経路計算管理部３５は、エリア間経路計算部３２が行ったエリア間経路の再計算結果を基にして、第二経路６の経路計算用の経路計算要求メッセージ６０を作成する。第二経路６の計算用の経路計算要求メッセージ６０に基づく計算は、実施形態（１）で説明した手順（１２）〜（１７）と同様である。
【００９０】
このように、経路が発見できなかったという情報を含む経路計算応答メッセージ５０を始点エリアの経路計算部３０が受信することにより、第二経路６の経路計算に失敗したときに、第一経路５を決定して第二経路６のみを再計算することができる。
【００９１】
〔自律的な代替経路計算〕
先に述べた実施形態の例では、始点エリアのエリア間経路計算部がエリア間経路の再計算を行った後に代替経路の計算を行っているが、第二経路６の計算に失敗した競合エリアのエリア内経路計算部３４が自律的に代替経路の計算を行う構成にすることもできる。この場合、第二経路６の計算に失敗したエリア内経路計算部３４によって自エリアに隣接するエリアに到達するための経路が代替経路として計算され、計算結果が経路計算応答メッセージ５０によって通知される。以下に、図１０、１１を参照しながら詳しく説明する。
【００９２】
（１）第二経路６の計算に失敗したエリアＡ２のエリア内経路計算部３４は、計算に失敗したことを経路計算管理部３５に報告する。報告を受けた経路計算管理部３５は、エリア間経路計算部３２に対して、自エリア（Ａ２）の隣接エリアをエリア間経路計算部３２に問い合わせる。エリア間経路計算部３２は、エリア間ルーチング処理部３１が保持しているサマライズ情報を用いて、隣接エリアを検索し、経路計算管理部３５に通知する。
【００９３】
（２）エリア間経路計算部３２から隣接エリアとしてＡ３の他に、Ａ４、Ａ５が存在することが通知されると、経路計算管理部３５はエリア内経路計算部３４にＡ４とＡ５が自エリアの隣接エリアであることを通知する。通知を受けたエリア内経路計算部３４は、エリアＡ４もしくはＡ５に到達するための経路を計算する。図１１の例では、エリアＡ４に到達するためには、ノードＡ２−１、Ａ２−５など、第一経路５と共通のノードを使用する必要があるので、エリアＡ４に到達するための経路を計算することはできない。次に、エリアＡ５に到達するための経路を検索すると、ノードＡ２−９、Ａ２−８、Ａ２−６を通過する経路が得られる。エリア内経路計算部３４は得られた経路を経路計算管理部３５に通知する。
【００９４】
（３）通知を受けた経路計算管理部３５はエリア間経路計算部３２に経路計算結果を通知し、エリア間経路計算部３２は得られた経路の境界ノードＡ２−９、Ａ２−６を抽出して格納する。また、エリア間経路計算部３２は、代替経路の情報を加えた経路計算応答メッセージ５０を始点エリア（Ａ１）に送信する。
【００９５】
（４）始点エリアＡ１に経路計算応答メッセージ５０が届くと、エリア内経路計算部３４が始点エリア内の経路計算を行い、経路計算管理部３５が第一経路５を決定する。
（５）第一経路５を決定した後、第二経路６の経路計算要求メッセージ６０を作成する。経路計算応答メッセージ５０の経路計算結果情報５１に含まれている経路のうち第一経
路５に使用しなかった経路を通過経路情報６７として指定する。経路計算管理部３５は、通過経路情報６７として指定した競合エリアの経路が、第一経路５を計算する際に指定した経路であるかをエリア間経路計算部３２が有する情報を用いて確認する。
【００９６】
図１１の例では、Ａ２の第二経路６の計算結果として「（Ａ２−９）−（Ａ２−６）」が含まれることになる。第二経路６は経路計算要求メッセージ４０でＡ２−３を通過するように指定されていたのでＡ２において、代替経路が計算されたことが分かる。
【００９７】
代替経路が計算された場合には、エリア間経路計算部３２は、代替経路から接続可能なエリアを第二経路６が通過するようにエリア間経路を再計算する。エリア間経路計算部３２は、代替経路に含まれるＡ２−９がエリアＡ５とＡ２の境界ノードであることを判断する。そこで、第二経路６がエリアＡ２とＡ５を通過するように、第二経路６のエリア間経路を再計算する。経路計算管理部３５は再計算されたエリア間経路を通過エリア情報６５として指定した経路計算要求メッセージ６０を作成し、第二経路６の計算を要求する。第二経路６の計算用の経路計算要求メッセージ６０に基づく計算は、実施形態（１）で説明した手順（１２）〜（１７）と同様である。
【００９８】
また、エリア内経路計算部３４が代替経路を自律的に計算する際に、代替経路を通過させるエリアを、エリアの優先順位に従って指定することもできる。図１３は、第二経路６が求まらなかったときに、代替経路が通過するエリアを変更して計算する方法を説明するフローチャートである。図１３の例では、第一経路５と第二経路６の経路計算を行い、第二経路６の計算に失敗したときには、経路計算開始時に第二経路６のエリア間経路計算結果として得られていたエリアよりも下流側のエリアを第二経路６が通過するように再計算を行う（ステップＳ１１〜１３）。下流側のエリアが複数存在する場合には、計算対象とするエリアを、エリア間ルーチング処理部３１の有するサマライズ情報を使用して、経路計算管理部３５が選択して、エリア内経路計算部３４に通知する構成にすることができる。また、経路計算管理部３５は、エリア間経路計算部３２から通知された隣接エリアとその優先順位を記憶し、経路計算に失敗すると、優先順位が最も高い隣接エリアをエリア内経路計算部３４に通知する構成にすることもできる。
【００９９】
計算対象とした下流エリアを通過する経路計算を行った結果、第一経路５と第二経路６の両者が求められた場合には、計算を終了する（ステップＳ１４）。第二経路６の計算に再度失敗すると、さらに下流側にエリアが存在する場合には、さらに下流側のエリアを通過させたときに第二経路６を求めることができるか計算する（ステップＳ１５、１３、１４）。ここで、第二経路６の計算は、既に述べたとおりに行われる。
【０１００】
つまり、上流側のエリアから順に経路計算を試していき、経路計算に成功するか、さらに下流のエリアが存在しなくなるまで第二経路６の計算を続ける。なお、経路計算に失敗し、経路計算をする下流のエリアが存在しない場合には、エリア内経路計算部３４は、経路計算管理部３５に対して、経路計算を失敗した旨の報告を行う。経路計算管理部３５は経路が計算できなかったことをエリア間経路計算部３２に報告し、エリア間経路計算部３２は「ＮＯＮＥ」を計算結果として格納する。
【０１０１】
通過する境界ノード以外の詳細情報を経路計算要求メッセージ４０で指定している場合や、詳細条件を設定していない場合においても、同様に代替経路の計算を行うことができる。
【０１０２】
このように、経路計算を失敗したエリアにおいて自律的にエリア内経路計算部３４が代替経路を計算する構成にすると、第二経路６を再計算するときに、計算済みの代替経路を使用できるように第二経路６の通過エリアを選択することができるようになる。つまり、
実施形態（１）で説明した方法と同様に、第二経路の経路計算要求メッセージ６０を送信する前に、競合エリアでは第二経路６として使用可能な経路が計算されている状態にすることができる。従って、第一経路５の計算・設定をした後に、第二経路６の通過エリアを決定して独立に第二経路６を計算する場合に比べて、第二経路６の計算に成功する確率が高くなる。
【０１０３】
＜その他の経路計算＞
〔競合エリア以外で第二経路の計算に失敗した場合〕
実施形態（２）では、競合エリアにおける経路計算に失敗したために第二経路６について経路計算が失敗した場合の対処方法について述べた。しかしながら、第一経路５と競合エリアにおける複数の経路の計算に成功しても、第二経路６のみが通過するエリアにおいてリソース不足であるために、第二経路６の計算に失敗することもあり得る。
【０１０４】
第二経路６の計算に失敗したエリアのエリア間経路計算部３２は、経路計算管理部３５を介してエリア内経路計算部３４から経路がない旨の報告を受けると、計算結果として「ＮＯＮＥ」を格納する。格納された経路計算結果は、先に述べたように、経路計算結果情報５１に記載されて始点エリアまで送られると、始点エリアにおいて、エリア間経路計算が行われ、第二経路６の再計算がなされる。
【０１０５】
〔第一経路と第二経路の両者の計算に失敗した場合〕
競合エリアにおいて、第一経路５と第二経路６の両方の経路計算に失敗した場合、エリア間経路計算部３２は、経路計算管理部３５を介して第一経路５と第二経路６が発見されなかった旨の通知をエリア内経路計算部３４から受ける。このとき、エリア間経路計算部３２は、第一経路５と第二経路６の両方について「ＮＯＮＥ」を格納する。
【０１０６】
格納された情報を使用して経路計算応答メッセージ５０が作成されるときに、第一経路５と第二経路６が求められなかったエリアの経路計算結果情報５１は、第一経路５、第二経路６とも「ＮＯＮＥ」となる。
【０１０７】
第一経路５について「ＮＯＮＥ」という応答があったときには始点エリアのエリア間経路計算部３２は、第一経路５と第二経路６の両者についてエリア間経路を再計算し、得られた再計算結果に基づいて経路計算を行う。
【０１０８】
また、第一経路５のみが通過するエリアにおいて経路計算に失敗した場合においても同様に、第一経路５について「ＮＯＮＥ」が含まれる経路計算応答メッセージ５０が始点エリアのエリア間経路計算部３２に届くことになる。そこで、前述の場合と同様に、エリア間経路計算部３２は第一経路５と第二経路６の両者についてエリア間経路を再計算し、得られた再計算結果に基づいて経路計算を行う。
【０１０９】
図１４は、これまで説明した実施形態（１）、（２）等を使用する経路計算を説明するフローチャートである。まず、第一経路５と競合エリアにおける第二経路６を計算し、第一経路５と第二経路６が求まっているかを確認する（ステップＳ２１）。競合エリアにおいて第一経路５と第二経路６の両者が発見されなかった場合や、第一経路５の計算に失敗した場合には、第一経路５と第二経路６の両者についてエリア間経路の計算を含めて経路の再計算が行われる（ステップＳ２６）。
【０１１０】
第一経路５と競合エリア内の第二経路６が求まっている場合は、第二経路６がエリア間経路計算で指定された経路であるかを、さらに判断する（ステップＳ２２）。指定された経路である場合は、第二経路６のみが通過するエリアについても経路計算を行って第二経路６を求める（ステップＳ２７、実施形態（１））。
【０１１１】
競合エリアについて計算されている第二経路６が、エリア間経路計算で指定された経路でない場合は、既に計算されている代替経路を使用できるように第二経路６の通過エリアを変更して、第二経路６を計算する（ステップＳ２３〜２５、実施形態（２））。
【０１１２】
代替経路を使用できる第二経路６の計算に失敗した場合には、第一経路５と第二経路６の両者について、エリア間経路の計算から再計算を行う（ステップＳ２４、２８）。
このような計算を行うことによって、第一経路５と第二経路６の全体について経路の再計算を行う確率を低くし、迅速にパスの設定をすることができるようになる。
【０１１３】
なお、本発明は上記の実施形態に限られるものではなく、様々に変形可能である。以下にその例をいくつか述べる。
＜外部装置を利用して経路計算を行う実施形態＞
これまで詳しく述べた実施形態においては、経路計算装置１０に経路計算部３０が備えられていた。また、経路計算部３０にエリア間ルーチング処理部３１、エリア間経路計算部３２、エリア内ルーチング処理部３３、エリア内経路計算部３４、経路計算管理部３５が含まれていた。しかし、ＰＣＥ４などの外部装置に経路計算部３０を搭載し、外部装置が計算を行う形態としても良い。さらに、ＮＭＳ（ネットワークマネジメントシステム）やＥＭＳ（エレメントマネジメントシステム）などの外部の経路計算用のコンピュータに経路計算部３０や経路計算部３０の各部分を搭載しても良い。
【０１１４】
複数の経路を計算する場合において、エリア間の経路計算を行うのは各エリアの中のノードのうちの一部であることが多い。一方、エリア内経路計算を行う可能性のあるノードの数はエリア間の経路計算を行うノードの数よりも一般に多いことが想定される。そこで、図１５に示すように、経路計算装置１０には経路計算部７０として、エリア内ルーチング処理部３３、エリア内経路計算部３４、経路計算管理部３５のみを搭載することが考えられる。この場合においては、外部装置の経路計算部８０には、図１６に示すように、エリア間ルーチング処理部３１とエリア間経路計算部３２のみを搭載することができる。このように、エリア内の経路計算をする部分を各ノードに残し、エリア間経路計算に関する部分を外部装置に搭載することにより、各ノードの計算の負担を増大することなくシステムの簡略化を図ることができる。
【０１１５】
図１７は、外部装置によって第一経路５の経路計算を行う実施形態を説明する図である。始点エリアの経路計算を行うＰＣＥ４に含まれているエリア間経路計算部３２が、エリア間経路を計算し、第一経路５が通過する各エリアの計算を行うＰＣＥ４に経路計算要求メッセージ４０が送られる。第一経路５の計算で行われる動作は既に説明したとおりである。ただし、ＰＣＥ４にエリア間経路計算部３２やエリア間ルーチング処理部３１があるため、経路計算要求メッセージ４０に記録されている情報は、必要に応じてＰＣＥ４からエリア内経路の計算対象となるノードの経路計算管理部３５に送られる。第一経路５と競合エリアにおける第二経路６が求まると、図１８に示すように、第二経路６が通過するＰＣＥ４に経路計算要求メッセージ６０が送られて、第二経路６の経路計算が行われる。第二経路６の計算時には、先に述べたとおり、第二経路６のうち競合エリアを通過する部分（図１８の矢印部分）以外の計算が行われる。
【０１１６】
＜その他＞
計算の詳細設定として通過ノード指定や通過経路指定をすることも可能であることは先に述べたとおりである。通過エリアをエリアＩＤで指定せずに通過ノードの指定のみを行う場合には、指定された通過ノードのＩＤ等を用いて通過エリアをチェックして競合エリアを抽出することにより、前述の経路計算方法を使用できる。
【０１１７】
経路計算部３０および経路計算部７０は経路計算管理部３５を備えるものとして説明したが、必ずしも経路計算管理部３５をおく必要はない。経路計算部３０および経路計算部７０に経路計算管理部３５が存在しない場合は、例えばエリア内経路計算部３４などのほかの部分によって、経路計算管理部３５の機能を実現する構成にすることができる。
【０１１８】
また上記の実施形態において、経路計算部３０および経路計算部７０は、ルーチング制御部２３に存在する構成を説明したが、ルーチング制御部２３以外の装置内監視制御部２０に置くこともできる。また、複数の部分から構成されるハードウェア回路として実現されるだけでなく、装置内監視制御部２０に含まれている各部分の機能を用いた、ソフトウェアによって実現されることもある。
【０１１９】
本明細書において、第一経路５と第二経路６の二本の経路を計算する場合について詳細に説明したが、これは理解を助けるために過ぎず、二本以上の経路を一度に計算することも可能である。二本以上の経路を一度に計算する場合においても、複数の経路が通過するエリアについて、そのエリアを通過する数の経路に用いるエリア内経路を計算することができる。また、三本以上の経路を計算する場合には、二本以上の代替経路の計算を行うことも可能である。複数の代替経路を計算する際に、競合エリアから到達するエリアは、同時に計算される代替経路の間で異なっていても良いし、同じであっても良い。
【０１２０】
以上説明したことを概観すれば本発明は以下のような構成を備えるものである。
（付記１）複数のエリアに分割されたネットワークにおいて始点ノードと終点ノードを結ぶ二本以上の経路を計算する経路計算装置であって、
前記二本以上の経路の少なくとも一つが通過する通過エリアのうち複数の経路が通過する複数経路通過エリアを特定する複数経路通過エリア特定部と、
前記二本以上の経路のうちの第一の経路を算出する際に、特定された前記複数経路通過エリアについて、前記複数経路通過エリアを通過する経路の数と同数のエリア内経路を計算するエリア内経路計算部を備える
ことを特徴とする経路計算装置。
（付記２）複数のエリアに分割されたネットワークにおいて始点ノードと終点ノードを結ぶ二本以上の経路を計算する経路計算装置であって、
前記二本以上の経路の少なくとも一つが通過する通過エリアのうち複数の経路が通過する複数経路通過エリアの情報を含むデータを受信する受信部と、
前記二本以上の経路のうちの第一の経路を算出する際に、前記複数経路通過エリアについて、前記複数経路通過エリアを通過する経路の数と同数のエリア内経路を計算するエリア内経路計算部を備える
ことを特徴とする経路計算装置。
（付記３）前記複数経路通過エリアに対して前記第一の経路の計算の際に計算された前記エリア内経路を用いて、前記二本以上の経路のうちの第二の経路が通過する第二経路通過エリアを特定する通過エリア特定部と、
前記第二の経路を決定する経路決定部をさらに備え、
前記エリア内経路計算部は、特定された前記第二経路通過エリアについてエリア内経路を計算し、前記経路決定部は、前記複数経路通過エリアについて得られたエリア内経路と前記第二経路通過エリアについて得られたエリア内経路を用いて、前記第二の経路を決定することを特徴とする、付記１記載の経路計算装置。
（付記４）前記複数経路通過エリアについて、前記複数経路通過エリアを通過する経路の数と同数のエリア内経路が得られない場合に、
前記エリア内経路計算部は、前記複数経路通過エリアに隣接する前記通過エリアを、前記複数経路通過エリアの隣接エリアに変更して、前記複数経路通過エリアから前記隣接エリアに到達するためのエリア内経路を計算する
ことを特徴とする付記１記載の経路計算装置。
（付記５）前記複数経路通過エリアについて、前記複数経路通過エリアを通過する経路の数と同数のエリア内経路が得られない場合に、
前記エリア内経路計算部は、前記複数経路通過エリアを通過する経路の数から前記複数経路通過エリアにおいて得られたエリア内経路の数を差し引いた不足経路数のエリア内経路を、前記複数経路通過エリアから前記隣接エリアに到達するためのエリア内経路として前記複数経路通過エリア内で計算する
ことを特徴とする付記４に記載の経路計算装置。
（付記６）前記通過エリア、前記複数経路通過エリア、前記隣接エリアの少なくとも一つで計算された前記エリア内経路を選択して組み合わせることによって、経路決定部が、前記始点ノードと前記終点ノードを結ぶ経路を設定する
ことを特徴とする付記１記載の経路計算装置。
（付記７）前記通過エリア、および、前記複数経路通過エリアがその境界ノードを用いて特定されている場合に、前記エリア内経路計算部は、前記境界ノードの情報を用いて前記エリア内経路を計算する
ことを特徴とする、付記１記載の経路計算装置。
（付記８）前記エリア内経路計算部は、前記二本以上の経路が、デフォルト条件、ノード独立、リンク独立、もしくはＳＲＬＧ独立のいずれかの条件を満たすように、前記通過エリアもしくは前記複数経路通過エリアのエリア内経路を計算する
ことを特徴とする、付記１記載の経路計算装置。
（付記９）複数のエリアに分割されたネットワークにおいて始点ノードと終点ノードを結ぶ二本以上の経路を計算する経路計算システムであって、
第一の経路計算装置が、前記二本以上の経路の少なくとも一つが通過する通過エリア、および、前記通過エリアのうち複数の経路が通過する複数経路通過エリアを特定し、
前記第一の経路計算装置が、前記通過エリアおよび前記複数経路通過エリアを、前記複数経路通過エリアを制御する第二の経路計算装置に通知し、
前記第二の経路計算装置は、前記複数経路通過エリアについて一つの経路を計算する際に、前記複数経路通過エリアを通過する経路の数と同数のエリア内経路を計算する
ことを特徴とする経路計算システム。
（付記１０）  前記第一の経路計算装置は、前記通過エリアおよび前記複数経路通過エリアを、前記通過エリアを制御する第三の経路計算装置に、さらに通知し、
前記第三の経路計算装置は、前記第三の経路計算装置が制御する前記通過エリアについてエリア内経路を計算し、
前記第二の経路計算装置は、前記第二の経路計算装置が制御する前記複数経路通過エリアについてのエリア内経路計算結果を、前記第一の経路計算装置に通知し、
前記第三の経路計算装置は、計算したエリア内経路を、前記第一の経路計算装置に通知し、
前記第一の経路計算装置は、前記第二の経路計算装置から通知された前記エリア内経路計算結果から選択したエリア内経路、前記第三の経路計算装置から通知されたエリア内経路、および、前記第一の経路計算装置が制御するエリアについてのエリア内経路の計算結果を接続して、前記始点ノードと前記終点ノードを結ぶ第一の経路を決定する
ことを特徴とする付記９に記載の経路計算システム。
（付記１１）前記第一の経路計算装置は、前記二本以上の経路のうちの第二の経路を計算する際に、前記第一の経路計算装置に通知された経路の数が二以上であるエリアを通過するように、前記第二の経路が通過する第二経路通過エリアを特定し、
前記第二経路通過エリアの経路計算を行う経路計算装置は、前記第一の経路計算装置の通知に応じてエリア内経路を計算する
ことを特徴とする付記９記載の経路計算システム。
（付記１２）前記第二の経路計算装置が計算した前記複数経路通過エリアから前記通過エリアに到達する前記エリア内経路の数が、前記複数経路通過エリアを通過する経路の数よりも少ないとき、前記第二の経路計算装置は、前記複数経路通過エリアから前記複数経路
通過エリアに隣接する隣接エリアに到達するためのエリア内経路を、前記複数経路通過エリアについて計算する
ことを特徴とする付記９記載の経路計算システム。
（付記１３）前記第二の経路計算装置は、前記エリア内経路の計算結果を、前記第一の経路計算装置に通知し、
前記第一の経路計算装置は、前記複数経路通過エリアにおいて前記隣接エリアに到達するためのエリア内経路が通知されたとき、前記始点ノードと前記終点ノードを結ぶ経路であり、かつ、前記隣接エリアを経由する代替経路が通過する通過エリアを特定し、
特定された代替経路通過エリアの経路計算を行う経路計算装置は、前記第一の経路計算装置による通知を受けると、エリア内経路を計算する
ことを特徴とする付記１２に記載の経路計算システム。
（付記１４）前記代替経路通過エリアであり、かつ、前記複数経路通過エリアでもあるエリアに存在する前記経路計算装置は、第一の経路を計算したときに得られた前記エリア内経路を前記第一の経路計算装置に通知する
ことを特徴とする付記１３に記載の経路計算システム。
（付記１５）  複数のエリアに分割されたネットワークにおいて始点ノードと終点ノードを結ぶ二本以上の経路を計算する経路計算方法であって、
前記二本以上の経路の少なくとも一つが通過する通過エリアのうち、複数の経路が通過する複数経路通過エリアを特定し、
前記二本以上の経路のうちの第一の経路を計算する際に、前記複数経路通過エリアに対しては、少なくとも前記複数経路通過エリアを通過する経路の数と同数のエリア内経路を計算し、
前記複数経路通過エリアに対して前記第一の経路の計算の際に計算された前記エリア内経路を用いて、前記二本以上の経路のうちの第二の経路を計算する
ことを特徴とする経路計算方法。
（付記１６）前記複数経路通過エリアについて、前記複数経路通過エリアを通過する経路数の経路が得られない場合に、前記複数経路通過エリアに隣接する前記通過エリアを、前記複数経路通過エリアの隣接エリアに変更し、
前記複数経路通過エリアから前記隣接エリアに到達するためのエリア内経路を計算する
ことを特徴とする付記１５に記載の経路計算方法。
（付記１７）前記隣接エリアを通過する経路が始点ノードと終点ノードを結ぶときに通過するエリアを特定し、
前記複数経路通過エリアから前記隣接エリアに到達するためのエリア内経路の計算結果を用いて、前記隣接エリアを通過する経路を計算する
ことを特徴とする付記１６に記載の経路計算方法。
【図面の簡単な説明】
【０１２１】
【図１】複数のエリアに分割されたネットワークと複数の経路の例を示す図である。
【図２】実施形態の経路計算装置の構成の例を示す図である。
【図３】実施形態の経路計算装置における経路計算部の構成例を示す図である。
【図４】経路計算の際に経路計算部が行う動作を説明する図である。
【図５】経路計算要求メッセージの例を示す図である。
【図６】経路計算応答メッセージの例を示す図である。
【図７】通過ノードを通過するように指定する場合の経路計算要求メッセージの例を示す図である。
【図８】通過経路情報を指定したときの第一経路の計算要求の例を示す図である。
【図９】第二経路を計算する際の経路計算要求メッセージの例を示す図である。
【図１０】第二経路の再計算を行うネットワークの例を示す図である。
【図１１】複数の経路の検索に失敗した競合エリアの例を示す図である。
【図１２】第二経路の経路計算に失敗したことを示す経路計算応答メッセージの例を示す図である。
【図１３】代替経路が通過するエリアを変更して計算する方法を説明するフローチャートである。
【図１４】実施形態（１）、（２）等を使用する経路計算を説明するフローチャートである。
【図１５】外部装置を使用して経路計算を行う場合のエリア内の各ノードに搭載される経路計算部の例を示す図である。
【図１６】外部装置を使用して経路計算を行う場合に、外部装置に搭載される経路計算部の例を示す図である。
【図１７】外部装置によって第一経路の経路計算を行う実施形態を説明する図である。
【図１８】外部装置によって第二経路の経路計算を行う実施形態を説明する図である。
【図１９】分割された複数のエリアにまたがる経路計算を行うための関連技術を説明する図である。
【図２０】ＢＲＰＣを用いた二つの経路の経路計算手法を説明する図である。
【図２１】ＰＣＥを用いて経路計算を行って複数の経路を求める際の関連技術に関する方法を説明するフローチャートである。
【符号の説明】
【０１２２】
１  ノード
２、Ａ１、Ａ２、Ａ３、Ａ４、Ａ５、Ａ６、Ａ７  エリア
３  経路
４  ＰＣＥ
５  第一経路
６  第二経路
７、８  ツリー
１０  経路計算装置
１１  回線
１２  インターフェイス部
１３  スイッチ部
２０  装置内監視制御部
２１  装置管理部
２２  シグナリング制御部
２３  ルーチング制御部
２４  警報管理部
２５  性能管理部
２６  パス管理部
３０、７０、８０  経路計算部
３１  エリア間ルーチング処理部
３２  エリア間経路計算部
３３  エリア内ルーチング処理部
３４  エリア内経路計算部
３５  経路計算管理部
３６  エリア間経路計算処理部
３７  エリア内経路計算処理部
３８  ネットワークエレメント
４０、６０  経路計算要求メッセージ
４１、６１  パスＩＤ情報
４２、６２  始点ＩＤ情報
４３、６３  終点ＩＤ情報
４４、６４  帯域情報
４５、６５  通過エリア情報
４６、６６  競合エリア情報
４７  通過ノード情報
４８、６７  通過経路情報
４９  制約条件情報
５０  経路計算応答メッセージ
５１  経路計算結果情報
Ｓ１  始点ノード
Ｄ１  終点ノード
【図１】
0004968117.tif 000002
【図２】
0004968117.tif 000003
【図３】
0004968117.tif 000004
【図４】
0004968117.tif 000005
【図５】
0004968117.tif 000006
【図６】
0004968117.tif 000007
【図７】
0004968117.tif 000008
【図８】
0004968117.tif 000009
【図９】
0004968117.tif 000010
【図１０】
0004968117.tif 000011
【図１１】
0004968117.tif 000012
【図１２】
0004968117.tif 000013
【図１３】
0004968117.tif 000014
【図１４】
0004968117.tif 000015
【図１５】
0004968117.tif 000016
【図１６】
0004968117.tif 000017
【図１７】
0004968117.tif 000018
【図１８】
0004968117.tif 000019
【図１９】
0004968117.tif 000020
【図２０】
0004968117.tif 000021
【図２１】
0004968117.tif 000022