(57)【要約】【課題】  １つのネットワークを複数のエリアに分割して経路制御プロトコルを運用しているネットワーク内において、パスの起点となる発側ノードから終点となる着側ノードの間に異なる経路を通る複数のパスを設定し、設定された複数のパスを、トラヒック負荷分散やパスプロテクションに利用可能な経路計算方法を提供する。【解決手段】  複数のエリアに分割された階層型通信網において、発側ノードと着側ノードの間に、中継エリアを経由して複数のパスを設定する際に、前記発側エリアに属する経路計算装置が、前記発側エリア内のパスの中継経路を計算し、前記複数のパスが経由する中継エリア、および前記着側エリアに属する経路計算装置が、前記計算されたパスの中継経路に基づき、前記複数のパスが経由する中継エリア、および前記着側エリア内のパスの中継経路を計算する。【選択図】        図１
2005252368.tif 000002
【特許請求の範囲】
【請求項１】
発側エリアと、着側エリアと、前記発側エリアと着側エリアとの間に位置する複数の中継エリアとに分割され、前記発側エリアに属しパスの開始点となる発側ノードと、前記着側エリアに属しパスの終点となる着側ノードと、エリアとエリアとの境界に位置する境界ノードとを有する階層型通信網における経路計算方法であって、
前記発側ノードと前記着側ノードの間に、前記中継エリアを経由して複数のパスを設定する際に、前記発側エリア内のパスの中継経路を計算するステップ１と、
前記計算されたパスの中継経路に基づき、前記複数のパスが経由する中継エリア、および前記着側エリア内のパスの中継経路を計算するステップ２とを有することを特徴とする経路計算方法。
【請求項２】
前記ステップ１、ステップ２において、指定されたノード間で、リンク、ノード、およびファイバを含む、ネットワークリソースを共有しない複数のパスの経路を計算することを特徴とする請求項１に記載の経路計算方法。
【請求項３】
前記発側エリア内に前記境界ノードが複数存在する場合に、前記ステップ１は、発側ノードとの間でリンク、ノード、およびファイバを含むネットワークリソースを共有しないパスを設定可能な境界ノードの組合せを検索するステップを含むことを特徴とする請求項２に記載の経路計算方法。
【請求項４】
前記ステップ２において、前記複数のパスが経由する中継エリア、および前記着側エリアでネットワークリソースを共有しないパスを発見できなかった場合に、前記ステップ１において経路計算を試行していない境界ノードの組合せを選択して、再度、ステップ１、ステップ２の処理を実行するステップ３を有することを特徴とする請求項３に記載の経路計算方法。
【請求項５】
発側エリアと、着側エリアと、前記発側エリアと着側エリアとの間に位置する複数の中継エリアとに分割され、前記発側エリアに属しパスの開始点となる発側ノードと、前記着側エリアに属しパスの終点となる着側ノードと、エリアとエリアとの境界に位置する境界ノードとを有する階層型通信網における経路計算方法であって、
前記発側ノードと前記着側ノードの間に、前記中継エリアを経由して複数のパスを設定する際に、前記複数のパスが経由する中継エリア、および前記着側エリアのトポロジ情報を収集するステップ１と、
前記発側エリアのトポロジ情報、および前記ステップ１で収集したトポロジ情報に基づき、前記発側ノードと前記着側ノードまでの前記各エリア内のパスの中継経路を計算するステップ２とを有することを特徴とする経路計算方法。
【請求項６】
発側エリアと、着側エリアと、前記発側エリアと着側エリアとの間に位置する複数の中継エリアとに分割され、前記発側エリアに属しパスの開始点となる発側ノードと、前記着側エリアに属しパスの終点となる着側ノードと、エリアとエリアとの境界に位置する境界ノードとを有する階層型通信網における経路計算システムであって、
前記各エリアに属する複数の経路計算装置を有し、
前記着側ノードの間に、前記中継エリアを経由して複数のパスを設定する際に、前記発側エリアに属する経路計算装置は、前記発側エリア内のパスの中継経路を計算する計算手段を有し、
前記複数のパスが経由する中継エリア、および前記着側エリアに属する経路計算装置は、前記発側エリアに属する経路計算装置でパスの中継経路に基づき、前記複数のパスが経由する中継エリア、および前記着側エリア内のパスの中継経路を計算する経路計算手段を有することを特徴とする経路計算システム。
【請求項７】
前記発側エリア、前記複数のパスが経由する中継エリア、および前記着側エリアに属する各経路計算装置の経路計算手段は、指定されたノード間で、リンク、ノード、およびファイバを含む、ネットワークリソースを共有しない複数のパスの経路を計算することを特徴とする請求項６に記載の経路計算システム。
【請求項８】
前記発側エリアに属する境界ノードが複数存在する場合に、前記発側エリアに属する経路計算装置は、発側ノードとの間でリンク、ノード、およびファイバを含むネットワークリソースを共有しないパスを設定可能な境界ノードの組合せを検索する検索手段を備えることを特徴とする請求項７に記載の経路計算システム。
【請求項９】
前記複数のパスが経由する中継エリア、および前記着側エリアに属する経路計算装置の経路計算手段が、ネットワークリソースを共有しないパスを発見できなかった場合に、前記発側エリアに属する経路計算装置の検索手段は、これまで経路計算を試行していない境界ノードの組合せを検索し、
前記発側エリアに属する経路計算装置の経路計算手段は、前記検索手段により検索された境界ノードの組合せを選択して、再度、前記発側エリア内のパスの中継経路を計算し、
前記複数のパスが経由する中継エリア、および前記着側エリアに属する経路計算装置の経路計算手段は、前記発側エリアに属する経路計算装置でパスの中継経路に基づき、再度、前記複数のパスが経由する中継エリア、および前記着側エリア内のパスの中継経路を計算することを特徴とする請求項８に記載の経路計算システム。
【請求項１０】
発側エリアと、着側エリアと、前記発側エリアと着側エリアとの間に位置する複数の中継エリアとに分割され、前記発側エリアに属しパスの開始点となる発側ノードと、前記着側エリアに属しパスの終点となる着側ノードと、エリアとエリアとの境界に位置する境界ノードとを有する階層型通信網における経路計算システムであって、
前記各エリアに属する複数の経路計算装置と、トポロジ情報を仲介するトポロジ情報仲介装置とを有し、
前記着側ノードの間に、前記中継エリアを経由して複数のパスを設定する際に、前記発側エリアに属する経路計算装置は、前記トポロジ情報仲介装置を介して、前記複数のパスが経由する中継エリア、および前記着側エリアのトポロジ情報を収集する収集手段と、
前記発側エリアのトポロジ情報、および前記収集手段で収集したトポロジ情報に基づき、前記発側ノードと前記着側ノードまでの前記各エリア内のパスの中継経路を計算する経路計算手段とを有することを特徴とする経路計算システム。
【請求項１１】
前記各経路計算装置は、前記境界ノードに接続されることを特徴とする請求項６ないし請求項１０のいずれか１項に記載の経路計算システム。
【請求項１２】
前記各経路計算装置は、前記境界ノード内に配置されることを特徴とする請求項６ないし請求項１０のいずれか１項に記載の経路計算システム。
【請求項１３】
請求項６ないし請求項１０のいずれか１項に記載された経路計算システムを利用して、設定された複数のパスを基に、トラヒックの負荷分散を行うことを特徴とする通信ノード。
【請求項１４】
請求項６ないし請求項１０のいずれか１項に記載された経路計算システムを利用して、設定された複数のパスを基に、１本のパスを主要パスとして常時通信に使用し、それ以外のパスは、前記主要パスに故障が発生した際の予備パスとして使用することを特徴とする通信ノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信網に収容される各コネクションの中継経路の計算を行う、階層化網における経路計算システム、経路計算方法、及び通信ノードに係わり、特に、レイヤ３のヘッダ情報を元に転送を行なうノード網、固定長のラベルを転送するパケットに付与することで通信網内を転送するＭＰＬＳ通信網、ＴＤＭ（Time Division Multiplexing）のタイムスロットや光の波長を一般化ラベルとして扱うＧＭＰＬＳ通信網に関する。
【背景技術】
【０００２】
近年、インターネットやＬＡＮの急速な普及から、ＩＰ（Internet Protocol）トラヒックを含めたデータトラヒックが指数関数的に増加している。
トラヒックの増加に対応するため、バックボーンネットワークにおける高速なＩＰパケットの転送を実現するメカニズムが求められている。
同時にＩＰをベースとしたアプリケーションも多様化しており、従来は電子メールやウェッブ等のネットワークに品質を要求しないアプリケーションが中心であったが、最近ではＩＰ電話や電子商取引のようにネットワークに高い品質を要求するアプリケーションも普及しはじめている。
従来のＩＰルータ網では、中継段の各ルータで電気的なパケット処理が必要であり、またＥｎｄ−Ｅｎｄで高度な品質制御を行うメカニズムを持たないため、高速化の実現と高品質なサービスの提供を実現することが困難であった。
ここで、品質としては、パケットの遅延時間や損失率という転送品質の他にも、ユーザから見えるサービス中断時間といった信頼性も重要な指標となる。
特に、従来のＩＰルータ網では自立分散的なルーティングを行っており、網の規模が拡大するにつれて、障害発生後の復旧時間が増大するという問題点もあった。
つまり、大規模網における高信頼性の実現が課題であった。
上述のＩＰルータ網に関わる問題を解決するひとつの手段として、ＭＰＬＳ（Multiprotocol Label Switching）が提案されている。
【０００３】
ＭＰＬＳでは、転送するパケットに固定長のラベルを付与し、ラベルをもとに通信網内の各ノードでは転送する方路を決定する。
このＭＰＬＳをＩＰバックボーンネットワークに導入することにより高速なＩＰパケットの転送と高度なTraffic Engineeringが可能となる。
さらに、近年、ＩＰネットワークの中継ノードに光クロスコネクト等のレイヤ１技術を利用したネットワークアーキテクチャが提案されている。
これまでに、ＡＳＯＮ（Automated Switched Optical Network）、ＧＭＰＬＳ（Generalized Multiprotocol Label Switching）などが提案されている。
これらネットワークに共通する特徴としては、パス（コネクション）がシグナリングにより動的に設定される点にある。
このため、従来のレイヤ１網に比べて、パス開通までの時間を大幅に短縮でき、より効率的な網運営が期待できる。
前述のＭＰＬＳ、ＧＭＰＬＳに共通な特徴としては、ＩＰパケットを含むユーザのトラヒックを転送するにあたって、事前にパス設定を行う必要がある点があげられる。
パス設定を行うためにはルーティングプロトコル等を用いてネットワークのトポロジ情報（ノード間の接続構成に関する情報）を収集し、パスの中継経路を計算した上で、ＣＲ−ＬＤＰ（Constraint-based Routed Label Distribution Protocol）やＲＳＶＰ−ＴＥ（Resource ReserVation Protocol-Traffic Engineering）等のシグナリングプロトコルによってパスの設定を行う。
パスの設定完了後に、該当パス上にトラヒックの転送を開始する。また、ＧＭＰＬＳとＭＰＬＳの関係であるが、ＧＭＰＬＳはＭＰＬＳの一般化であり、基本的にＭＰＬＳを包含するものである。
【０００４】
次に、図９を用いて、ＭＰＬＳやＧＭＰＬＳを用いて、ネットワークの高信頼化を実現する技術について説明する。なお、ここでは、一例として、ＧＭＰＬＳの場合を説明するが、ＭＰＬＳの場合にも適用可能である。
ＧＭＰＬＳにおける高信頼化技術としては、パスプロテクションがよく知られている（非特許文献１参照）。
図９に示すように、パスプロテクションとは、通信の起点となる通信ノード（図９に示すノード（発側）１）から終点となる通信ノード（図９に示すノード（着側）２）間に２本以上のパスを予め設定し、そのうちの１つを主要パス５として、通常時にユーザトラヒックを転送する。
主要パス以外のパスを予備パス６と呼ぶ。この予備パス６を主要パス５と、リンクおよびノード（図９の中継ノード２）を共有しないように設定する。
図９に示す例のように、２つのパス（主要パス５、予備パス６）が共有するリンクおよびノードを持たないとき、disjoint（互いに素）なパスと呼ぶ。
主要パス上のノードまたはリンクに障害が発生した際に、起点となるノード（発側）においてパス切替えを行い、ユーザトラヒックを予備パス上に転送する。
主要パス５の経路上に障害が発生した際に、直ちに予備パス６に切替えることにより、ユーザトラヒックの不通時間を短縮し、高信頼化を実現している。
予備パス６は、前述した通り、主要パス５とはリンクおよびノードを共有していないため、主要パス５上の障害の影響を受けない。
【０００５】
なお、本願発明に関連する先行技術文献としては以下のものがある。
【非特許文献１】E.Oki 他, ”A Disjoint Path Selection Scheme with SRLG in GMPLS networks” 2002 Wksp.IEEE HPSR,May 2002,88-92.
【非特許文献２】E.L. Lawler,  ”A procedure for computing the K best path solutions to discrete optimization problems and its application to the shortest path problem”, Management Science, 18, 401-405 1972.
【非特許文献３】特願２００２−２３５９８０号
【発明の開示】
【発明が解決しようとする課題】
【０００６】
前述した高信頼化技術の基本となるものが、パスの起点となる通信ノードと終点となる通信ノード間に複数のdisjointパスの経路を計算し、設定する方法である。
ここで、disjointな複数パスのことをマルチパスとも呼ぶ。
ＭＰＬＳ／ＧＭＰＬＳネットワークにおいて、disjointなパスを計算・設定する方法はこれまでに数多く提案されてきている。
従来方式としては、Lawlerにより提案されたk-shortest path方式がある（非特許文献２参照）。
この方式はネットワークトポロジが既知という前提のもとで、ｋ本のマルチパスを発見するアルゴリズムである。
この方式の問題点としては、マルチパス発見のための計算が複雑であることと、ネットワークの完全なトポロジ情報が必要なことである。
通常のＭＰＬＳ／ＧＭＰＬＳネットワークでは、網内の各通信ノード間でＯＳＰＦ（Open Shortest Path Fast）等の経路制御（ルーティング，Routing）プロトコルを動作させて、各通信ノードはネットワークのトポロジ情報を学習し、それをもとに経路制御を行っている。
小規模なネットワークでは、各ノードはネットワーク全体のトポロジ情報を学習可能であるが、大規模なネットワークになるとネットワーク全体の経路情報を学習し、経路制御することは難しい。
これはネットワーク内の通信ノード数が比例すると、それに応じて各通信ノードが保持しなければならない経路表が増大することと、経路制御プロトコルの制御メッセージ量が網内の通信ノード数の２乗に比例して増加するためである。
【０００７】
図１０に示すように、通常、多数の通信ノードで構成される大規模ネットワークでは、１つのネットワークを複数のエリア（Ａｒｅａ）、即ち、パスの開始点となる発側ノード１が属する発側エリア（Ａ１）と、パスの終点となる着側ノード２が属する着側エリア（Ａ２）と、発側エリア（Ａ１）および着側エリア（Ａ２）以外の中継エリア（Ａ３１〜Ａ３ｎ）とに分割して、各エリアにある程度の独立性を持たせて経路制御プロトコルを動作させている。
このように、複数のエリアに分割されたネットワークのことを階層化されたネットワーク（Hierarchical Network）、もしくはマルチエリアネットワークとも呼ぶ。
この場合、各通信ノードは、自エリア内のトポロジ情報を持つが、自エリア以外のエリアのトポロジ情報は持たないため大規模網では、従来方式であるk-shortest path法は部分的にしか適用できない。
前述の非特許文献１、非特許文献２では、同一エリア内で終端されるパスに対してはdisjointなパスを構築することは可能であるが、複数のエリアを通過するパスに対してdisjointなパスを構築することはできない。
また、マルチエリアネットワークにおける複数パス設定方法としては、前述の特許文献３に記載されたものもあるが、この方式では中継エリアが１つのみのネットワークを前提としているため、図１０に示されるような、中継エリアが複数存在するネットワークには用いることはできない。
さらにエリア毎に、独立に経路計算を行っているため、効率的にdisjointなパスを設定することも難しい。
つまり、従来方式では、複数エリアで構成されているネットワークにおいて、複数エリアを通過するパスの信頼性を高めることは難しいという問題点があった。
【０００８】
本発明は、前記従来技術の問題点を解決するためになされたものであり、本発明の目的は、１つのネットワークを複数のエリアに分割して経路制御プロトコルを運用しているネットワーク内において、パスの起点となる発側ノードから終点となる着側ノードの間に異なる経路を通る複数のパスを設定し、設定された複数のパスを、トラヒック負荷分散やパスプロテクションに利用可能な経路計算システム、および経路計算方法、並びに通信ノードを提供することにある。
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述及び添付図面によって明らかにする。
【課題を解決するための手段】
【０００９】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
即ち、本発明は、発側エリアと、着側エリアと、前記発側エリアと着側エリアとの間に位置する複数の中継エリアとに分割され、前記発側エリアに属しパスの開始点となる発側ノードと、前記着側エリアに属しパスの終点となる着側ノードと、エリアとエリアとの境界に位置する境界ノードとを有する階層型通信網において、前記発側ノードと前記着側ノードの間に、前記中継エリアを経由して複数のパスを設定する際に、前記発側エリアに属する経路計算装置が、前記発側エリア内のパスの中継経路を計算し、前記複数のパスが経由する中継エリア、および前記着側エリアに属する経路計算装置が、前記発側エリアに属する経路計算装置が計算したパスの中継経路に基づき、前記中継エリア、および前記着側エリア内のパスの中継経路を計算することを特徴とする。
【００１０】
また、本発明は、発側エリアと、着側エリアと、前記発側エリアと着側エリアとの間に位置する複数の中継エリアとに分割され、前記発側エリアに属しパスの開始点となる発側ノードと、前記着側エリアに属しパスの終点となる着側ノードと、エリアとエリアとの境界に位置する境界ノードとを有する階層型通信網において、前記着側ノードの間に、前記中継エリアを経由して複数のパスを設定する際に、前記発側エリアに属する経路計算装置が、トポロジ情報仲介装置を介して、前記複数のパスが経由する中継エリア、および前記着側エリアのトポロジ情報を収集し、前記発側エリアのトポロジ情報、および前記収集手段で収集したトポロジ情報に基づき、前記発側ノードと前記着側ノードまでの前記各エリア内のパスの中継経路を計算することを特徴とする。
また、本発明は、前述の経路計算システムを利用して、設定された複数のパスを基に、トラヒックの負荷分散、あるいは、１本のパスを主要パスとして常時通信に使用し、それ以外のパスは、前記主要パスに故障が発生した際の予備パスとして使用する通信ノードである。
【発明の効果】
【００１１】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。
本発明によれば、ルーティングプロトコルのドメインが複数エリアに分割されたネットワークにおいても、ネットワーク全体のトポロジ情報を収集することなく、発側ノード、着側ノード間で効率的に複数のリンク、ノード、またはファイバ等を共有しない複数のパスの中継経路を計算し、設定することが可能となる。
【発明を実施するための最良の形態】
【００１２】
以下、図面を参照して本発明の実施例を詳細に説明する。
なお、実施例を説明するための全図において、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。
［実施例１］
図１は、本発明の実施例１の経路計算システムが適用される通信ネットワークの概略構成を示すブロック図である。
図１に示すネットワークでは、網内の各ノードでルーティングプロトコルを動作させて、トポロジ情報の収集を行っている。ここで、ルーティングプロトコルとしてはＯＳＰＦやＩＳ−ＩＳ（Intermediate System to Intermediate System）などが通常利用されている。
図１に示すように、ネットワークは、複数のノード（１，２，３，４）および経路計算装置（１０，２０，３０）で構成されている。
各ノードは、発側ノード１、中継ノード３（境界ノード４を含む）、着側ノード２に分類される。
発側ノード１はパスの開始点となるノードで、新たなパスを設定する際に設定のためのシグナリングメッセージの生成などを行う。
例えば、ＧＭＰＬＳネットワークの場合、ＣＲ−ＬＤＰ（Constraint-based Routed Label Distribution Protocol）やＲＳＶＰ−ＴＥ（Resource ReserVation Protocol-Traffic Engineering）などのシグナリングを用いてパスの設定を行う。
中継ノード３は、パス上を転送されるデータの中継を主に行う。
着側ノード２は、パスの終端点となるノードである。
【００１３】
さらに構成例では、１つのネットワークのルーティングドメインが複数のエリアに分割されている。
図１ではルーティングドメインがｎ（ｎ≧２）の中継エリア（Ａ３１〜Ａ３ｎ）と２つのエリア（Ａ１，Ａ２）に分割されている。
通常、ルーティングドメインをエリア分割する場合、１つ以上の中継エリア（Ａ３１〜Ａ３ｎ）とそれに接続する複数のエリア（Ａ１，Ａ２）に分割される。
図１に示すように、エリア分割は、発側エリア（Ａ１）、着側エリア（Ａ２）が、１つ以上の中継エリア（Ａ３１〜Ａ３ｎ）に直接接続するように行われる。
ここで、発側ノード１が属するエリアを発側エリア（Ａ１）、着側ノード２が属するエリアを着側エリア（Ａ２）と呼ぶ。
２つのエリアの両方に属しているノードを境界ノード４と呼ぶ。
例えば、ＯＳＰＦでは、この境界ノード４のことを特にＡＢＲ（Area Border Router）と呼ぶ。境界ノード４は、前述の中継ノード３の一種である。
境界ノード以外のノード（１，２，３）は１つのエリアのみに属し、自身が属しているエリアのトポロジ情報しか持たない。境界ノード４は、自身が属している中継エリアと、発側エリア（Ａ１）あるいは着側エリア（Ａ２）のトポロジ情報を持つ。
経路計算装置（１０，２０，３０）は、エリア毎に少なくとも１つ配備されており、各境界ノード４は少なくとも１つの経路計算装置（１０，２０，３０）と接続している。
【００１４】
図２は、本発明の実施例の経路計算装置の概略構成を示す機能ブロック図である。
経路計算装置は、経路計算情報送受信部１１、ルーティング情報送受信部１２、経路計算制御部１３、制約付き経路計算部１４、中継ＡＢＲ選択リスト１５、トポロジデータベース１６、経路計算メッセージ格納部１７で構成されている。
経路計算情報送受信部１１は、他のノードまたは経路計算装置との間での経路計算要求メッセージ・経路計算応答メッセージの送受信を行う。
また、経路計算情報送受信部１１が受信したメッセージは経路計算制御部１３に転送される。
ルーティング情報送受信部１２は、配備されているエリアに属する境界ノード４と接続されており、境界ノード４からルーティング情報を受信する。
受信したルーティング情報をもとに、ルーティング情報送受信部１２は、ネットワークのトポロジを作成して、その情報をトポロジデータベース１６に保存する。
経路計算装置内のトポロジデータベース１６は、接続している境界ノード４が保持するトポロジ情報と同一の情報を保持している。
例えば、図１の発側エリア（Ａ１）に配置されている経路計算装置１は、境界ノード４（ＡＢＲ１）および境界ノード４（ＡＢＲ２）と同じトポロジ情報を保持している。
【００１５】
境界ノード４（ＡＢＲ１，ＡＢＲ２）は、中継エリア１（Ａ３１）と発側エリア（Ａ１）に属しているため、経路計算装置１（１０）も中継エリア１（Ａ３１）と発側エリア（Ａ１）のトポロジ情報を持つ。
したがって、本実施例では、特に、中継エリアにのみ属する経路計算装置を特に設ける必要はない。
経路計算制御部１３は、経路計算情報送受信部１１から転送された経路計算要求メッセージおよび経路計算応答メッセージを、経路計算メッセージ格納部１７に保存する。
さらに、経路計算要求メッセージの情報を解析して、経路計算を要求されているパスの制約条件を制約付き経路計算部１４に受け渡す処理も行う。また、中継ＡＢＲ選択リスト１５の作成も実施する。
ここで、中継ＡＢＲ選択リスト１５とは、同一の発側ノード１、着側ノード２間で複数のパスを設定する際に、各パスが選択可能な境界ルータの候補が格納されたリストである。
制約付き経路計算部１４は、経路計算制御部１３からの要求に基づき、指定された条件にもとづくパスの中継経路の計算を行い、計算結果を経路計算制御部１３に応答する。
また、経路計算はトポロジデータベース１６の情報を用いて実行される。
【００１６】
以下、本発明の経路計算装置を用いて、発側ノード１と着側ノード２間に２本のdisjointパスを設定する方法について説明する。
２本のパスのうち、一方を主要パス５、他方を予備パス６と呼ぶものとする。
まず、発側ノード１は、パス設定に先立って、パスの中継経路の解決を行うために経路計算要求メッセージを経路計算装置１（１０）に送信する。
このときに、発側ノード１は、発側エリア（Ａ１）に属する経路計算装置１（１０）のアドレス情報を持つ必要があるが、本実施例では、経路計算装置１（１０）は境界ノード４（ＡＢＲ１，ＡＢＲ２）に接続されているため、境界ノード４（ＡＢＲ１，ＡＢＲ２）のアドレス宛にメッセージを送信して、境界ノード４（ＡＢＲ１，ＡＢＲ２）が、経路計算要求メッセージを経路計算装置１（１０）に転送してもよい。
図１に示すように、発側エリア（Ａ１）が複数の中継エリア（Ａ３１〜Ａ３ｎ）に接続している場合、着側エリア（Ａ２）に到達可能な中継エリアに接続している経路計算装置を１つ選択する。図１では、経路計算装置１（１０）を選択している。
また、各ノードは、ルーティングプロトコルにより得られる情報を基に、着側エリア（Ａ２）ヘの到達可能な中継エリアと、自エリアと、当該中継エリアを接続している境界ノード４のアドレスを知ることができる。
選択した中継エリアに属する境界ノード４のアドレス宛に経路計算要求メッセージを送信する。
【００１７】
経路計算要求メッセージには、少なくとも以下の情報が含まれる。
（１）発側ノード１のアドレス
（２）着側ノード２のアドレス
（３）設定するパスの本数
（４）パスのポリシー
（５）要求帯域
ここで、パスのポリシーとは、複数パス間でリンクまたはノードの共有を許容するか、予備パス６のリソースの共有を許容するかなどである。
本実施例では、設定するパスは２本で、パスのポリシーは、リンク・ノード・ファイバそれぞれに対してdisjointである。
経路計算要求メッセージを受信した境界ノード４（ＡＢＲ１）（あるいは、境界ノード４（ＡＢＲ２））は、メッセージを経路計算装置１（１０）に転送する。
【００１８】
以下、図３を用いて、発側エリアに属する経路計算装置の処理手順を説明する。
初めに、発側ノード１からの経路計算要求を発側エリアの経路計算装置（ここでは、経路計算装置１（１０））が受信すると（ステップ１０１）、選択された中継エリアに属する境界ノードを選択する（ステップ１０３）。
次に、選択された中継エリア内の境界ノードと発側ノード間の要求を満たす経路を計算し（ステップ１０４）、要求を満たす経路が存在するか否かを判断する（ステップ１０５）。
ステップ１０５において、要求を満たす経路が存在する場合には、着側エリアの経路計算装置（ここでは、経路計算装置２（２０））に経路計算要求メッセージを送信し（ステップ１０７）、また、要求を満たす経路が存在しない場合には、中継ＡＢＲ選択リストから境界ノードを再選択する（ステップ１０６）。
以下に、発側エリア（Ａ１）に属する経路計算装置が経路計算装置１（１０）、および発側エリア（Ａ２）に属する経路計算装置が経路計算装置２（２０）の場合における、経路計算装置１（１０）の処理手順をさらに詳細に説明する。
【００１９】
経路計算装置１（１０）は、受信したメッセージを経路計算制御部１３に渡す。
次に、中継ＡＢＲ選択リスト１５から主要パス５、予備パス６が通過する境界ノード４を１つづつ選択する。この中継ＡＢＲ選択リスト１５には、自エリアに属する境界ノード４のアドレス情報が格納されている。
主要パス５と予備パス６が通過する境界ノードの選択方法としては、下記のようなポリシーに従って、優先度を設定する。
リスト内で最も優先度が高い境界ノードを主要パス５が、次に優先度が高い境界ノードを予備パス６が通過する境界ルータとして選択する。
優先度設定のポリシーとしては、以下の方法がある。
（１）発側ノード１からのルーティングプロトコルのコストが小さいルータほど高い優先度を設定。
（２）保守者があらかじめ、各境界ノード毎に優先度を設定。
（３）経路制御プロトコルのメッセージ内の情報（ルータＩＤなど）をもとに優先度を設定。
【００２０】
図１に示す例では、主要パス５、予備パス６は、それぞれ境界ノード（ＡＢＲ２）、境界ノード（ＡＢＲ１）を選択している。
次に、発側エリア（Ａ１）内の主要パス５と予備パス６の経路計算を行う。
経路計算は、制約付き経路計算部１４にてトポロジデータベース１６の情報を用いて行われる。
経路計算制御部１３は、制約付き経路計算部１４に計算するパスの制約条件を受け渡す。
図１に示す例では、要求帯域、発側ノード１と境界ノード４（ＡＢＲ１）のパスと、発側ノード１と境界ノード４（ＡＢＲ２）間でdisjointとなるという条件を満たすパスの経路を計算する。
制約を満たすパスが発見できない場合は再度、経路計算制御部１３にて境界ノード４の再選択を実施する。
選択可能な境界ノードが存在する限り、disjointなパスを発見できるまで境界ノード４の再選択を繰り返す。
【００２１】
発側エリア（Ａ１）内の経路計算が完了すると、経路計算制御部１３は、着側エリア（Ａ２）の経路計算装置２（２０））に送信する経路計算要求メッセージを作成する。
このメッセージは、経路計算メッセージ格納部１７に保存されるととともに、経路計算情報送受信部１１に渡される。
発側エリア（Ａ１）に属する経路計算装置１（１０）は、各着側エリア（Ａ２）の経路計算装置２（２０）のアドレス情報を保持しており、該当する着側エリア（Ａ２）の経路計算装置２（２０）のアドレスを検索し、経路計算装置２（２０）に経路計算要求メッセージを送信する。
このときの経路計算要求メッセージには、前述の発側ノード１から送信された経路計算要求メッセージに加えて、少なくとも、各パスが使用する発側エリア（Ａ１）の境界ノード４のアドレス情報が含まれる。
【００２２】
以下、図４を用いて、着側エリアに属する経路計算装置の処理手順を説明する。
着側エリアの経路計算装置（ここでは、経路計算装置２（２０））が経路計算要求を受信すると（ステップ１１１）、中継エリアと着側エリア内の経路を計算する（ステップ１１２）。
次に、要求を満たす経路が存在するか否かを判断し（ステップ１１３）、ステップ１１３において、要求を満たす経路が存在しない場合には、経路計算要求メッセージを送信した経路計算装置（ここでは、経路計算装置１（１０））にエラー通知を送信する（ステップ１１４）。
また、ステップ１１３において、要求を満たす経路が存在する場合には、経路計算結果を経路計算要求メッセージを送信した経路計算装置に送信する（ステップ１１５）。
以下に、発側エリア（Ａ１）に属する経路計算装置が経路計算装置１（１０）、および発側エリア（Ａ２）に属する経路計算装置が経路計算装置２（２０）の場合における、経路計算装置２（２０）の処理手順をさらに詳細に説明する。
経路計算要求メッセージを受信した着側エリア（Ａ２）の経路計算装置２（２０）内の経路計算情報送受信部１１は、まず受信したメッセージを経路計算制御部１３に渡し、発側の経路計算装置１（１０）と同様に、経路計算制御部１３は受信メッセージを経路計算メッセージ格納部１７に保存する。
次に、制約付き経路計算部１４は、経路計算要求メッセージから要求を満たすパスの経路、即ち、経路計算要求メッセージに記述されている境界ノード４と着側ノード２との間で要求を満たすパスの経路を計算する。
このときに要求を満たす経路が存在しない場合は、エラー通知を経路計算要求メッセージの送信元、つまり発側エリア（Ａ１）の経路計算装置１（１０）に送信する。
要求を満たす経路が存在する場合、着側エリア（Ａ２）の経路計算装置２（２０）は、計算結果を経路計算応答メッセージとして、経路計算要求メッセージの送信元の経路計算装置１（１０）に送信する。
【００２３】
この経路計算応答メッセージには、少なくとも以下の情報が含まれる。
（１）該当する経路計算要求メッセージを識別可能な情報
（２）発側ノード１のアドレス
（３）着側ノード２のアドレス
（４）中継エリア（Ａ３）と着側エリア（Ａ２）内のパスの中継経路情報。
最終的に、経路計算応答メッセージが発側エリア（Ａ１）に属する経路計算装置１（１０）にまで到達すると、経路計算装置１（１０）は、受信した経路応答メッセージに、発側エリア（Ａ１）内のパス経路情報を追加して、発側ノード１に経路計算応答メッセージを送信する。
このメッセージには、各パスの発側ノード１と着側ノード２間の中継経路の情報が含まれている。
経路計算応答メッセージを受信した発側ノード１は、受信したメッセージに含まれている着側ノード２までのパスの経路情報を用いて、シグナリング等により着側ノード２との間でパスを設定する。
以上の装置間シーケンスの一例を図６に示す。
【００２４】
以下、図５を用いて、エラー通知受信時の発側エリア（Ａ１）に属する経路計算装置の処理手順を説明する。
発側エリアの経路計算装置（ここでは、経路計算装置１（１０））がエラー通知を受信すると（ステップ１２１）、エラー通知に対応する経路計算要求メッセージを検索する（ステップ１２２）。
次に、中継ＡＢＲ選択リスト１５と経路計算要求メッセージの情報から選択可能な境界ノード４の組み合わせ検索する（ステップ１２３）。
次に、選択可能な境界ノード４があるか否かを判断し（ステップ１２４）、ステップ１２４において、選択可能な境界ノード４がない場合には、発側ノード１にエラー通知を送信する（ステップ１２５）。
また、選択可能な境界ノードがある場合には、着側エリアの経路計算装置（ここでは、経路計算装置２（２０））に経路計算要求メッセージを送信する（ステップ１２６）。
以下に、発側エリア（Ａ１）に属する経路計算装置が経路計算装置１（１０）、および発側エリア（Ａ２）に属する経路計算装置が経路計算装置２（２００）の場合における、エラー通知受信時の経路計算装置１（１０）の処理手順を説明する。
【００２５】
発側エリア（Ａ１）の経路計算装置１（１０）がエラー通知を受信した際に、エラー通知メッセージは、経路計算情報送受信部１１から経路計算制御部１３に渡され、経路計算制御部１３にて、エラー通知に対応する、着側エリア（Ａ２）の経路計算装置に送信した経路計算要求リクエストを検索する。
まず、この検索により該当メッセージでこれまでに選択した境界ノード４の組合せを列挙する。
この組合せ情報と中継ＡＢＲ選択リスト１５の組合せから、これまでに経路計算要求メッセージを送信していない境界ノード４の組合せ、かつ、発側ノード１と各境界ノード４間にdisjoint性等の要求を満たすパスが存在するという条件を満たす境界ノードの組合せを検索する。
このような組合せが存在すれば、再度経路計算要求メッセージを着側エリア（Ａ２）の経路計算装置２（２０）に送信する。
このとき、経路計算制御部１３は、同一の要求に対する経路計算要求メッセージの再送信回数が規定回数を超えている場合には、再送信する代わりに、発側ノード１に対するエラー通知を作成し、経路計算情報送受信部１１を介して、発側ノード１にエラー通知を送信することもできる。
【００２６】
前述の条件を満たす境界ノード４の組合せが存在しない場合、経路計算制御部１３は発側ノード１に対するエラー通知を作成し、経路計算情報送受信部１１を介して、発側ノード１にエラー通知を送信する。
エラー通知を受信した発側ノード１はパス設定の試行を中断するか、選択した中継エリア以外にも着側エリア（Ａ２）に到達可能な中継エリアがある場合、該当エリアに属する経路計算装置に、再度経路計算要求メッセージを送信する。
このように、本実施例によれば、複数エリアから構成される大規模ネットワークにおいても、発側ノード１、着側ノード２間で、効率的に、リンク、ノード、またはファイバを含むネットワークリソースを共有しない複数のパスの中継経路を計算し、ネットワーク上に複数のパスを設定することができる。
また、上記の手順で設定した主要パス５と予備パス６は、パスプロテクションや負荷分散などのTraffic Engineeringなどに用いることができる。
また、実施例で記載されている経路計算装置は、境界ノード４と別装置として説明されているが、境界ノード内に経路計算装置を配置してもよい。
【００２７】
［実施例２］
図７は、本発明の実施例２の経路計算システムが適用される通信ネットワークの概略構成を示すブロック図である。
図７に示すネットワークは、複数のノード（１，２，３）および経路計算装置（１０，２０，３０１〜３０ｎ）、１台以上のトポロジ情報中継装置５０で構成される。
網内の各ノード上では、ルーティングプロトコルが動作しており、ネットワークのルーティングドメインは複数のエリアで構成されている。
コネクションの起点となるノードを発側ノード１、発側ノード１が属するエリアを発側エリア（Ａ１）、コネクションの終点となるノードを着側ノード２、着側ノード２が属するエリアを着側エリア（Ａ２）と呼ぶ。
また、着側エリア（Ａ２）と発側エリア（Ａ１）以外のエリアを中継エリア（Ａ３１〜Ａ３ｎ）と呼ぶ。他のエリアとの境界に位置するノードを境界ノード４と呼ぶ。
各エリアに少なくとも１つの経路計算装置（１０，２０，３０１〜３０ｎ）が配置される。
各経路計算装置（１０，２０，３０１〜３０ｎ）は、属しているエリアのトポロジ情報（ノードの接続構成に関する情報）を保持し、ノードからの要求に基づきパスの中継経路の計算を行う。
トポロジ情報中継装置５０は、各エリアに配置されている経路計算装置（１０，２０，３０１〜３０ｎ）と接続しており、経路計算装置間でトポロジ情報を交換する際に仲介を行う。
【００２８】
以下、本実施例において、発側ノード１と着側ノード２との間で２本以上の異なる経路のパスを設定する方法について説明する。
発側ノード１は、発側エリア（Ａ１）に配置されている経路計算装置１０のアドレス情報を持ち、このアドレス情報をもとに経路計算要求メッセージを、経路計算装置１０に送信する。
この経路計算要求メッセージには、少なくとも以下の情報が含まれる。
（１）発側ノード１のアドレス
（２）着側ノード２のアドレス
（３）設定するパスの本数
（４）パスのポリシー
ここで、パスのポリシーとは、複数パス間でリンクまたはノードの共有を許容するか、予備パス６のリソースの共有を許容するかなどである。
経路計算要求メッセージを受信した経路計算装置１０は、前記メッセージの着側ノード２のアドレス情報をもとに、着側ノード２が発側エリア（Ａ１）内かどうかを判断する。
図７に示すように、発側エリア（Ａ１）と着側エリア（Ａ２）が異なる場合、発側エリア（Ａ１）の経路計算装置１０はトポロジ情報を持たないため着側ノード２までの中継経路を計算することができない。
そのため、経路計算装置１０は、トポロジ情報中継装置５０に着側エリア（Ａ２）と中継エリアのトポロジ情報を要求する。
【００２９】
このときに、発側エリア（Ａ１）の経路計算装置１０は、自エリアと接続している中継エリアが複数存在する場合、着側エリア（Ａ２）に到達可能な中継エリア（例えば、Ａ３１）を１つ選択する。
中継エリアの選択方法としては、以下の方法がある。
（１）発側ノード１からのコストが最も小さい境界ノード４が属する中継エリアを選択。
（２）予め、発側ノード１に各中継エリア（Ａ３）の優先度が設定されており、優先度の最も高い中継エリアを選択。
（３）複数の中継エリアの中からランダムに１つ選択。
発側エリア（Ａ１）の経路計算装置１０は、選択した中継エリアを識別可能な情報と着側ノード２のアドレスの情報を含むトポロジ情報要求メッセージをトポロジ情報中継装置５０に送信する。
トポロジ情報要求メッセージを受信したトポロジ情報中継装置５０は、着側ノード２のアドレスから着側エリア（Ａ２）を特定する。
次に、メッセージで指定されている中継エリアの経路計算装置（例えば、経路計算装置３０１）と着側エリア（Ａ２）の経路計算装置２０にトポロジ情報要求メッセージを送信する。
【００３０】
トポロジ情報要求メッセージを受信した各経路計算装置は、自エリア内のトポロジ情報を含むトポロジ情報応答メッセージをトポロジ情報中継装置５０に送信する。
トポロジ情報中継装置５０は、受信した中継エリア（例えば、Ａ３１）と着側エリア（Ａ２）の情報を、トポロジ情報応答メッセージとして発側エリア（Ａ１）の経路計算装置１０に送信する。
メッセージを受信した発側エリア（Ａ１）の経路計算装置１０は、着側エリア（Ａ２）までのトポロジを作成し、パスの中継経路を計算する。
これまでの応答により、経路計算装置１０は、発側ノード１から着側ノード２までのトポロジ情報を保持することになるため、例えば、前述の非特許文献２に記載されている計算方法により、２地点間の複数パスを計算することができる。
条件を満たすパスが発見できた場合、経路計算装置１０は、発側ノード１から着側ノード２までのパスの中継経路の情報を経路計算応答メッセージとして、発側ノード１に送信する。
また、選択した中継エリアで条件を満たす複数パスが発見できなかった場合、発側エリア（Ａ１）の経路計算装置１０は、パスの中継エリアの再選択を行う。
このときに、先ほど選択した中継エリアの除いて、着側エリア（Ａ２）に到達可能な中継エリアを１つ選択する。
【００３１】
選択した中継エリア（例えば、Ａ３ｎ）を識別可能な情報を含むトポロジ情報要求メッセージをトポロジ情報中継装置５０に送信する。
トポロジ情報中継装置５０は、前述した方法と同様の方法により、中継エリアの経路計算装置にアクセスして、トポロジ情報を収集して、再度発側エリア（Ａ１）の経路計算装置１０に、トポロジ情報応答メッセージとしてトポロジ情報を送信する。
トポロジ情報応答メッセージを受信した経路計算装置１０は、再度着側ノード２までの経路を計算する。
発側エリア（Ａ１）の経路計算装置１０は、要求を満たすパスを発見できるか、もしくは選択可能な中継エリアがなくなるまで、中継エリアの再選択を実施する。
以上のシーケンスを図８に示す。
経路計算応答メッセージを受信した発側ノード１は、受信したメッセージに含まれている着側ノード２までのパスの経路情報を用いて、シグナリング等により着側ノード２との間でパスを設定する。
以上、本発明者によってなされた発明を、前記実施例に基づき具体的に説明したが、本発明は、前記実施例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【図面の簡単な説明】
【００３２】
【図１】本発明の経路計算システムが適用される通信ネットワークの一例の概略構成を示すブロック図である。
【図２】本発明の実施例の経路計算装置の概略構成を示す機能ブロック図である。
【図３】発側エリアに属する経路計算装置の処理手順を説明するためのフローチャートである。
【図４】着側エリアに属する経路計算装置の処理手順を説明するためのフローチャートである。
【図５】エラー通知受信時の発側エリアに属する経路計算装置の処理手順を説明するためのフローチャートである。
【図６】図１に示す通信ネットワークにおいて、発側ノードと着側ノード間にパスを設定する場合のシーケンスの一例を示す図である。
【図７】本発明の経路計算システムが適用される通信ネットワークの他の例の概略構成を示すブロック図である。
【図８】図７に示す通信ネットワークにおいて、発側ノードと着側ノード間にパスを設定する場合のシーケンスの一例を示す図である。
【図９】ネットワークの高信頼化を実現するマルチパスについて説明するための図である。
【図１０】階層化されたネットワークを説明するための図である。
【符号の説明】
【００３３】
Ａ１  発側エリア
Ａ２  着側エリア
Ａ３１〜Ａ３ｎ  中継エリア
１  発側ノード
２  着側ノード
３  中継ノード
４  境界ノード
５  主要パス
６  予備パス
１０，２０，３０，３０１〜３０ｎ  経路計算装置
１１  経路計算情報送受信部
１２  ルーティング情報送受信部
１３  経路計算制御部
１４  制約付き経路計算部
１５  中継ＡＢＲ選択リスト
１６  トポロジデータベース
１７  経路計算メッセージ格納部
５０  トポロジ情報中継装置
【図１】
2005252368.tif 000003
【図２】
2005252368.tif 000004
【図３】
2005252368.tif 000005
【図４】
2005252368.tif 000006
【図５】
2005252368.tif 000007
【図６】
2005252368.tif 000008
【図７】
2005252368.tif 000009
【図８】
2005252368.tif 000010
【図９】
2005252368.tif 000011
【図１０】
2005252368.tif 000012