(57)【特許請求の範囲】
【請求項１】
ルーティングプロトコルのエリア内において、あるソースノードから前記エリア内の各宛先ノードまでの候補経路を計算する経路計算装置であって、
前記エリアを複数の仮想的なサブエリアに分割するサブエリア分割手段と、前記サブエリア分割手段で分割された各サブエリア内の候補経路をそれぞれ計算するサブエリア内候補経路計算手段と、前記サブエリア間の境界ノードにおいて前記サブエリア内候補経路計算手段で計算された各サブエリア内の候補経路の関連付けを行って前記ソースノードから前記ソースノードを含まないサブエリア内の各宛先ノードまでの候補経路を作成するサブエリア内候補経路関連付け手段とを有し、
前記サブエリア内候補経路計算手段において、複数の計算アルゴリズムを含み、各サブエリア毎の候補経路計算においてそれぞれのサブエリアに対して前記計算アルゴリズムを選択的に用いるようにしたことを特徴とする経路計算装置。
【請求項２】
前記計算アルゴリズムの１つとして、ダイクストラ計算を反復的に繰り返すことで通過するノード及びリンクを互いに共有しない候補経路を複数本求めるアルゴリズムを用いるようにしたことを特徴とする請求項１記載の経路計算装置。
【請求項３】
前記計算アルゴリズムの１つとして、１回のダイクストラ計算によって最短経路木を求めることで候補経路を作成するアルゴリズムを用いるようにしたことを特徴とする請求項１記載の経路計算装置。
【請求項４】
前記サブエリア分割手段は、リンクコストを基準に複数のサブエリアに分割するよう構成したことを特徴とする請求項１から請求項３のいずれか記載の経路計算装置。
【請求項５】
前記サブエリア分割手段は、ポリシを基準に複数のサブエリアに分割するよう構成したことを特徴とする請求項１から請求項３のいずれか記載の経路計算装置。
【請求項６】
前記サブエリア分割手段は、前記ソースノードを含むローカルサブエリア及びそれ以外のリモートサブエリアの２つのサブエリアに分割するよう構成したことを特徴とする請求項１から請求項３のいずれか記載の経路計算装置。
【請求項７】
ルーティングプロトコルのエリア内において、あるソースノードから前記エリア内の各宛先ノードまでの候補経路を計算する経路計算方法であって、
前記エリアを複数の仮想的なサブエリアに分割する第１のステップと、その分割された各サブエリア内の候補経路をそれぞれ計算する第２のステップと、前記サブエリア間の境界ノードにおいて前記第２のステップで計算された各サブエリア内の候補経路の関連付けを行って前記ソースノードから前記ソースノードを含まないサブエリア内の各宛先ノードまでの候補経路を作成する第３のステップとを有し、
前記第２のステップにおいて、複数の計算アルゴリズムを含み、各サブエリア毎の候補経路計算においてそれぞれのサブエリアに対して前記計算アルゴリズムを選択的に用いるようにしたことを特徴とする経路計算方法。
【請求項８】
前記計算アルゴリズムの１つとして、ダイクストラ計算を反復的に繰り返すことで通過するノード及びリンクを互いに共有しない候補経路を複数本求めるアルゴリズムを用いるようにしたことを特徴とする請求項７記載の経路計算方法。
【請求項９】
前記計算アルゴリズムの１つとして、１回のダイクストラ計算によって最短経路木を求めることで候補経路を作成するアルゴリズムを用いるようにしたことを特徴とする請求項７記載の経路計算方法。
【請求項１０】
前記第１のステップは、リンクコストを基準に複数のサブエリアに分割するようにしたことを特徴とする請求項７から請求項９のいずれか記載の経路計算方法。
【請求項１１】
前記第１のステップは、ポリシを基準に複数のサブエリアに分割するようにしたことを特徴とする請求項７から請求項９のいずれか記載の経路計算方法。
【請求項１２】
前記第１のステップは、前記ソースノードを含むローカルサブエリア及びそれ以外のリモートサブエリアの２つのサブエリアに分割するようにしたことを特徴とする請求項７から請求項９のいずれか記載の経路計算方法。
【請求項１３】
ルーティングプロトコルのエリア内において、あるソースノードから前記エリア内の各宛先ノードまでの候補経路を計算する経路計算制御プログラムを記録した記録媒体であって、
前記経路計算制御プログラムはコンピュータに、前記エリアを複数の仮想的なサブエリアに分割する第１のステップと、その分割された各サブエリア内の候補経路をそれぞれ計算する第２のステップと、前記サブエリア間の境界ノードにおいて前記第２のステップで計算された各サブエリア内の候補経路の関連付けを行って前記ソースノードから前記ソースノードを含まないサブエリア内の各宛先ノードまでの候補経路を作成する第３のステップとを実行させ、
前記第２のステップにおいて、複数の計算アルゴリズムを含み、各サブエリア毎の候補経路計算においてそれぞれのサブエリアに対して前記計算アルゴリズムを選択的に用いるようにしたことを特徴とする経路計算制御プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は経路計算装置及びそれに用いる経路計算方法並びにその制御プログラムを記録した記録媒体に関し、特にソースルーティングを行う機能を有するルーティングプロトコルにおいて、ソースノードから各宛先ノードまで１つあるいは複数の異なる候補経路を計算する経路計算装置に関する。
【０００２】
【従来の技術】
従来、この種の経路計算装置においては、コネクションオリエンテッド型通信網におけるコネクション設定時に、要求される通信品質を満たす経路をその都度計算する手間を省くために、予め自ノードから各宛先ノードまで１つあるいは複数の候補経路を計算しておき、これらの候補経路の中から要求される通信品質を満たす経路を検索するために用いられている。
【０００３】
障害回復性能やスループットの向上の観点から、候補経路上の途中のノード及びリンクは互いに共有されない（ディスジョイントである）ことが望まれる。そこで、互いにディスジョイントな複数の候補経路を計算するアルゴリズムとして、ＫＳＰ（ｋ−Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ）アルゴリズムが用いられている。
【０００４】
例えば、アイ・イー・イー・イー・ジャーナル・オン・セレクテッド・エリアズ・イン・コミュニケーションズ、第１２巻、第１号、１９９４年１月、８８〜９９ページ（ＩＥＥＥ  ＪＯＵＲＮＡＬ  ＯＮ  ＳＥＬＥＣＴＥＤ  ＡＲＥＡＳＩＮ  ＣＯＭＭＵＮＩＣＡＴＩＯＮＳ，ＶＯＬ．１２，ＮＯ．１，ＪＡＮＵＡＲＹ  １９９４，ｐｐ．８８−９９）にＫＳＰアルゴリズムによる複数ディスジョイント経路の計算方法について述べられている。
【０００５】
ＫＳＰアルゴリズムでは、１，２，・・・，（ｋ−１）本目の候補経路上のノード及びリンクを取り除いたサブグラフにおいて、ｋ本目の候補経路がダイクストラ計算によって求められる。上記の計算は各宛先ノードに対して別々に行われ、１つの宛先ノードまでの最大候補経路数をｋとした場合、ｋ本の候補経路が見つかるか、あるいはその前に互いにディスジョイントな候補経路が見つからなくまで行われる。但し、１本目の候補経路計算時のみ、ソースノードからの最短経路木を計算することによって、全ての宛先ノードまでの候補経路を同時に求めることができる。
【０００６】
したがって、ＫＳＰアルゴリズムでは、ダイクストラ計算を最大で、
１＋（ｋ−１）ｎ
回実行する。ここで、ｋはある宛先までの候補経路の最大本数であり、例えばｋ＝４等の値が用いられる。ｎはエリア内に存在する宛先ノードの数である。また、繰り返し行われるダイクストラ計算は１回当たり最大で、
ｍ＋ｎ（ｌｏｇ（ｎ））
に比例する計算量を要する。ここで、ｍはエリア内のノード間リンクの本数である。
【０００７】
したがって、ＫＳＰアルゴリズムによってソースノードから各宛先までのｋ本の候補経路を求める計算は、
（１＋（ｋ−１）ｎ）［ｍ＋ｎ（ｌｏｇ（ｎ））］
に比例する計算量を必要とする。ｎの値が十分に大きい時、この候補経路を求める計算は、
ｍｎ＋ｎ2 ｌｏｇ（ｎ）
に比例する。
【０００８】
【発明が解決しようとする課題】
上述した従来の経路計算装置では、ＫＳＰアルゴリズムによってソースノードから各宛先ノードまでのｋ本の候補経路を求めるための計算量が大きいという問題がある。
【０００９】
ルーティングプロトコルの１つであるＯＳＰＦ（Ｏｐｅｎ  ＳｈｏｒｔｅｓｔＰａｔｈ  Ｆｉｒｓｔ）では、１回のルーティングテーブル計算を行うために、
ｍ＋ｎ（ｌｏｇ（ｎ））
に比例する計算量を要するが、ＫＳＰアルゴリズムによる計算量はこれのｎ倍大きい。計算量はエリアの規模が大きくなるとともに、飛躍的に増大するため、大規模エリアではルーティングテーブル計算と比較して計算にかかる時間が無視できなくなる。
【００１０】
また、従来の経路計算装置では、ＫＳＰアルゴリズムにおいて通過するノード及びリンクを互いに共有しない候補経路を求めるため、エリアのトポロジによってはソースノードから宛先ノードまでの候補経路がｋ本見つからないような場合もありうる。十分な数の候補経路を見つけることができないようなトポロジにおいては、コネクション設定に際して要求を満たす通信品質（残余帯域、遅延等）をもつ候補経路が存在しない確率（呼損率）が、十分な数の候補経路が存在する場合に比べて高くなる。
【００１１】
そこで、本発明の目的は上記の問題点を解消し、ソースノードから各宛先ノードまでの候補経路を求める計算において、ＫＳＰアルゴリズムよりも計算量の小さいアルゴリズムを実現することができる経路計算装置及びそれに用いる経路計算方法並びにその制御プログラムを記録した記録媒体提供することにある。
【００１２】
本発明の他の目的は、ＫＳＰアルゴリズムによって十分な数の候補経路が見つからないようなトポロジにおいても、十分な数の候補経路を見つけることができ、呼損率を悪化させないようなアルゴリズムを実現することができる経路計算装置及びそれに用いる経路計算方法並びにその制御プログラムを記録した記録媒体を提供することにある。
【００１５】
【課題を解決するための手段】
本発明による経路計算装置は、ルーティングプロトコルのエリア内において、あるソースノードから前記エリア内の各宛先ノードまでの候補経路を計算する経路計算装置であって、
前記エリアを複数の仮想的なサブエリアに分割するサブエリア分割手段と、前記サブエリア分割手段で分割された各サブエリア内の候補経路をそれぞれ計算するサブエリア内候補経路計算手段と、前記サブエリア間の境界ノードにおいて前記サブエリア内候補経路計算手段で計算された各サブエリア内の候補経路の関連付けを行って前記ソースノードから前記ソースノードを含まないサブエリア内の各宛先ノードまでの候補経路を作成するサブエリア内候補経路関連付け手段とを備え、
前記サブエリア内候補経路計算手段において、複数の計算アルゴリズムを含み、各サブエリア毎の候補経路計算においてそれぞれのサブエリアに対して前記計算アルゴリズムを選択的に用いるようにしている。
【００１８】
本発明による経路計算方法は、ルーティングプロトコルのエリア内において、あるソースノードから前記エリア内の各宛先ノードまでの候補経路を計算する経路計算方法であって、
前記エリアを複数の仮想的なサブエリアに分割する第１のステップと、その分割された各サブエリア内の候補経路をそれぞれ計算する第２のステップと、前記サブエリア間の境界ノードにおいて前記第２のステップで計算された各サブエリア内の候補経路の関連付けを行って前記ソースノードから前記ソースノードを含まないサブエリア内の各宛先ノードまでの候補経路を作成する第３のステップとを備え、
前記第２のステップにおいて、複数の計算アルゴリズムを含み、各サブエリア毎の候補経路計算においてそれぞれのサブエリアに対して前記計算アルゴリズムを選択的に用いるようにしている。
【００２１】
本発明による経路計算制御プログラムを記録した記録媒体は、ルーティングプロトコルのエリア内において、あるソースノードから前記エリア内の各宛先ノードまでの候補経路を計算する経路計算制御プログラムを記録した記録媒体であって、
前記経路計算制御プログラムはコンピュータに、前記エリアを複数の仮想的なサブエリアに分割する第１のステップと、その分割された各サブエリア内の候補経路をそれぞれ計算する第２のステップと、前記サブエリア間の境界ノードにおいて前記第２のステップで計算された各サブエリア内の候補経路の関連付けを行って前記ソースノードから前記ソースノードを含まないサブエリア内の各宛先ノードまでの候補経路を作成する第３のステップとを実行させ、
前記第２のステップにおいて、複数の計算アルゴリズムを含み、各サブエリア毎の候補経路計算においてそれぞれのサブエリアに対して前記計算アルゴリズムを選択的に用いるようにしている。
【００２２】
すなわち、本発明の経路計算装置は、ソースノードからエリア内の各宛先ノードまでの候補経路を計算する経路計算手段において、エリアを複数のサブエリア（ローカルサブエリア及びリモートサブエリア）に分割するサブエリア分割手段と、分割された各サブエリア内の候補経路を計算するサブエリア内候補経路計算手段と、ソースノードを含まないサブエリア内の宛先ノードに対してサブエリアボーダーノードにおいて各サブエリア内の候補経路の関連付けを行うことによってソースノードからの候補経路を作成するサブエリア内候補経路関連付け手段とを有している。
【００２３】
上記のような構成を採用することによって、ダイクストラ計算において、対象となる網規模を縮小することが可能となるため、サブエリア分割を行わない場合に比べて１回のダイクストラ計算に要する計算量を削減することが可能となる。
【００２４】
また、各サブエリア内の候補経路計算に用いられる計算アルゴリズムの組合わせを工夫することによって、ＫＳＰアルゴリズムよりも計算回数を削減することが可能となる。
【００２５】
したがって、全体の計算量を削減することが可能となり、ソースノードから各宛先ノードまでの候補経路を求める計算において、ＫＳＰアルゴリズムよりも計算量の小さいアルゴリズムが実現される。
【００２６】
また、本発明の経路計算装置では、ＫＳＰアルゴリズムによって十分な数の候補経路が見つからないようなトポロジにおいても、リモートサブエリア内の候補経路に関して、各サブエリア内候補経路の関連付けによって十分多くの候補経路を作成することが可能となり、呼損率を悪化させないようなアルゴリズムが実現される。
【００２７】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。図１は本発明の第１の実施の形態による経路計算装置の構成を示すブロック図である。図１において、本発明の第１の実施の形態による経路計算装置はデータ処理装置１と、記憶装置２とから構成されている。
【００２８】
データ処理装置１はルーティングプロトコル手段１１と、経路計算手段１２と、候補経路検索手段１６とから構成され、経路計算手段１２はサブエリア分割手段１３と、サブエリア内候補経路計算手段１４と、サブエリア内候補経路関連付け手段１５とを備えている。記憶装置２はルーティング情報記憶部２１と、候補経路格納テーブル２２とから構成されている。
【００２９】
ルーティングプロトコル手段１１はＯＳＰＦ等のルーティングプロトコルを用いて、図示せぬ隣接ルータとのエリア内ルーティング情報の交換１００を行う。ルーティングプロトコル手段１１によって得られたエリア内ルーティング情報はルーティング情報記憶部２１に格納され、この情報を基にして経路計算手段１２によって候補経路の計算が行われる。
【００３０】
経路計算手段１２によって計算された候補経路は候補経路格納テーブル２２に格納される。経路計算要求１０１に対しては候補経路検索手段１６を介して候補経路格納テーブル２２内に要求を満たす通信品質を持つ経路が存在すれば、その経路が経路計算応答１０２として返される。
【００３１】
経路計算手段１２はルーティングプロトコルにおけるエリア［例えば、ＯＳＰＦにおいて同一のＲｏｕｔｅｒ−ＬＳＡ（Ｌｉｎｋ  Ｓｔａｔｅ  Ａｄｖｅｒｔｉｓｉｎｇ）がフラッディング（ｆｌｏｏｄｉｎｇ）されるエリア；同一エリア内では同一のリンクステート情報を保持する］において、エリア内に存在する各宛先ノードまでの候補経路を計算する。
【００３２】
図２は本発明の第１の実施の形態におけるエリア構成を示す図であり、図３は本発明の第１の実施の形態による経路計算装置の動作を示すフローチャートであり、図４は図１の候補経路格納テーブル２２の構成を示す図である。これら図１〜図４を参照して経路計算手段１２の動作について説明する。
【００３３】
また、以下の説明において、計算を行うノード自身をソースノードと呼ぶ。宛先ノードはエリア内に存在するノードのうち、宛先として候補経路を計算する必要のあるものを指すが、ここではソースノードを除くエリア内の全ノードが宛先ノードであるとする。図２のエリア３において候補経路の計算を行う例を用いる。エリア３においてはノード１０１がソースノードである。
【００３４】
経路計算手段１２はまずサブエリア分割手段１３によって、エリアを２つのサブエリアに分割する（図３ステップＳ１）。この分割はソースノードにおいてある基準にしたがって仮想的かつ動的に行われてもよいし、ポリシ等を基にした設定によって静的に行われてもよい。但し、静的な設定の場合においても、エリア内の全ノードに同じサブエリア構成を設定する必要はなく、あくまでもソースノードだけによる仮想的な分割の形態をとる。
【００３５】
すなわち、サブエリア分割はソースノードだけによって有効であり、別のノードがソースノードとなる場合には、他のサブエリア分割の形態をとる。分割によって、エリア内の各ノードはいずれかのサブエリアに所属する。以下、分割したサブエリアのうち、ソースノードを含むものをローカルサブエリア（ＬｏｃａｌＳｕｂａｒｅａ；ＬＳ）、他方をリモートサブエリア（Ｒｅｍｏｔｅ  Ｓｕｂａｒｅａ；ＲＳ）と呼ぶ。
【００３６】
サブエリア分割の例として、リンクコストを基準に半数のノードをＬＳ、残りの半数をＲＳとするといった基準や、グラフ理論の最小カットアルゴリズムによってエリアを分割するといった基準等が考えられる。ここで、リンクコストとはホップ数やリンクメトリックのような静的なものでもよいし、最大帯域値、遅延等のような動的なパラメータから算出されてもよい。
【００３７】
図２に示す例はソースノード１０１からのホップ数が小さい順に半数のノードをＬＳ３１、残りの半数をＲＳ３２としたサブエリア分割の例であり、ＬＳ３１はノード１０１〜１０５によって構成され、ＲＳ３２はノード１０６〜１１０によって構成されている。
【００３８】
ステップＳ１で分割したＬＳ３１内のノード１０１〜１０５のうち、ＲＳ３２内のノード１０６〜１１０と直接接続されているノードをサブエリアボーダーノード（Ｓｕｂａｒｅａ  Ｂｏｒｄｅｒ  Ｎｏｄｅ；ＳＢＮ）とする（図３ステップＳ２）。図２に示す例では、ノード１０３，１０４がＳＢＮとなる。
【００３９】
上述した動作はエリア３内の各ノード１０１〜１１０がいずれかのサブエリアに所属するようなサブエリア分割の例であり、リンクによってサブエリアが分割されるが、他の方法として、ノードによってサブエリアを分割してもよい．すなわち、サブエリア境界上のノードは複数のサブエリアに所属する。この場合、ＳＢＮはサブエリア境界上のノードとなる。但し、本実施の形態ではリンクによってサブエリアが分割される場合について述べる。
【００４０】
次に、サブエリア内候補経路計算手段１４はＬＳ３１内、ＲＳ３２内の候補経路を計算する。まず、サブエリア内候補経路計算手段１４はＬＳ３１内の候補経路として、ソースノード１０１からＬＳ３１内の各宛先ノードまでの候補経路を計算する（図３ステップＳ３）。複数の候補経路を計算するアルゴリズムの例として、ＫＳＰアルゴリズム等を用いる。また、この計算において、ＬＳ３１内のリンクステート情報だけが用いられる。例えば、図２に示すＬＳ３１の場合には、図４に示す候補経路格納テーブル２２におけるＬＳ３１に対する候補経路リスト２２ａのようになる。
【００４１】
例えば、起点ノード１０１から宛先ノード１０３に対しては、Ｐ３，Ｐ４，Ｐ５の３つの候補経路がある。Ｐ＊によって示される候補経路は、具体的に、ノード間の連結によって表現される。Ｐ３がノード１０１を起点とし、ノード１０２を経由してノード１０３へ至る候補経路であるとすると、具体的には［１０１→１０２→１０３］と表現することができるが、本実施の形態ではこのような表現の代わりに単にＰ＊とだけ記す。また、各宛先ノードがＳＢＮであるかどうかも判別できるようになっており、宛先ノード１０３，１０４はＳＢＮであることがわかる（「Ｙｅｓ」で表示）。
【００４２】
続いて、サブエリア内候補経路計算手段１４はＲＳ３２内の候補経路を計算する（図３ステップＳ４）。ＲＳ３２内の候補経路として、ステップＳ２で選択された各ＳＢＮを起点とする、ＲＳ３２内の各宛先ノードまでの候補経路を計算する。すなわち、ＳＢＮの数だけＲＳ３２内の各宛先ノードまでの候補経路計算が繰り返される。
【００４３】
この繰り返し計算回数を削減するために、ステップＳ２で選択された全てのＳＢＮを起点ノードとして用いずに、起点ノードとなるＳＢＮの数を制限してもよい。また、この計算において、起点となるＳＢＮ及びＲＳ３２内のリンクステート情報だけが用いられる。ＳＢＮからＲＳ３２内の各宛先ノードまでの候補経路は１つでもよいし、複数であってもよい。１つの場合には、１回のダイクストラ計算で最短経路木を作成することによって、あるＳＢＮからＲＳ３２内の全ての宛先ノードまでの候補経路を１度に求めることができる。
【００４４】
図２に示す例の場合、図４に示す候補経路格納テーブル２２におけるＲＳ３２に対する候補経路リスト２２ｂのようになる。例えば、宛先ノード１０６に対する候補経路は、起点ＳＢＮがノード１０３であればＰ１１，Ｐ１２であり、起点ＳＢＮがノード１０４であればＰ１８である。
【００４５】
最後に、サブエリア内候補経路関連付け手段１５によって、ソースノードからＲＳ３２内の各宛先ノードまでの候補経路を求める（図３ステップＳ５）。ステップＳ３で求めたソースノードからＳＢＮとなっている宛先ノードまでの候補経路に対し、各ＳＢＮにおいて、そのＳＢＮを起点とするＲＳ３２内の候補経路を関連付ける。ここで、関連付けとは、例えばポインタ等を用いて、ある候補経路から別の候補経路を参照することができるようにすることである。
【００４６】
図２において、ソースノードから宛先ノード１０６までの候補経路について、ＳＢＮであるノード１０３を経由するものを求める場合、ノード１０１（ソースノード）からノード１０３（ＳＢＮ）までの３本の候補経路｛Ｐ３，Ｐ４，Ｐ５｝に対してノード１０３からノード１０６（宛先ノード）までの２本の候補経路｛Ｐ１１，Ｐ１２｝が関連付けられる。
【００４７】
すなわち、｛Ｐ３，Ｐ４，Ｐ５｝の３つの候補経路は｛Ｐ１１，Ｐ１２｝の２つ候補経路を参照することができ、ソースノード１０１から宛先ノード１０６までの候補経路として、［Ｐ３→Ｐ１１］，［Ｐ３→Ｐ１２］，［Ｐ４→Ｐ１１］，［Ｐ４→Ｐ１２］，［Ｐ５→Ｐ１１］，［Ｐ５→Ｐ１２］の６本の候補経路を作ることに相当する。この関連付けによる候補経路作成はポインタ等を用いることによって、新たな記憶容量をほとんど消費しないことも大きな特長の１つである。
【００４８】
上記と同様に、ノード１０４を経由する宛先ノード１０６までの候補経路を作るために、｛Ｐ６，Ｐ７，Ｐ８｝に｛Ｐ１８｝が関連付けられる。上述した処理によって、ソースノード１０１から宛先ノード１０６まで合計で３×２＋３×１＝９本の候補経路が作られる。
【００４９】
本実施の形態ではエリアを２つのサブエリアに分割し、各サブエリアに対して候補経路を計算する。特に、ソースノードからＲＳ内の宛先ノードに対してはＬＳ内の候補経路とＲＳ内の候補経路との関連付けによって候補経路を作成する。ＬＳ内の候補経路計算にはＫＳＰアルゴリズムが用いられ、ＲＳ内の候補経路計算に最短経路木計算（１つのＳＢＮに対して１回のダイクストラ計算が行われる）が用いられる場合、ＬＳ内の各宛先ノードに対する候補経路計算に要するダイクストラ計算の回数は、
１＋（ｋ−１）・（ｎ／２）
であり、ＲＳ内の各宛先ノードに対する候補経路計算に要するダイクストラ計算の回数はＳＢＮの数と同じである。
【００５０】
この場合、（ＳＢＮの数）≧（ｎ／２）なので、エリア内の各宛先ノードに対する候補経路計算に要するダイクストラ計算の回数は、
１＋ｋ・（ｎ／２）
以下になる。例えば、ｋ＝４の時、ｎの数が十分に大きいとすると、ダイクストラ計算の回数はＫＳＰアルゴリズムの２／３以下になる。
【００５１】
また、各ダイクストラ計算において、エリア全体の半分のリンクステート情報だけが用いられるので、ダイクストラ計算１回当たり最大で、
ｍ＋（ｎ／２）ｌｏｇ（ｎ／２）
に比例する計算量となる。
【００５２】
上記の処理によって、ダイクストラ計算の計算回数と１回あたりの計算量とを削減することができるため、本実施の形態ではＫＳＰアルゴリズムの計算量を削減することが可能となる。
【００５３】
また、本実施の形態ではＬＳ内の宛先ノードに対して、ＫＳＰアルゴリズムと同様、最大ｋ本の候補経路を作成するが、ＲＳ内の宛先ノードに対しては少なくともＳＢＮの数だけの候補経路を作成することができ、各サブエリア内に複数の候補経路がある場合には各サブエリアの候補経路間の関連付けによってさらに多くの候補経路を作成することができる。したがって、ＫＳＰアルゴリズムによって十分な数の候補経路が見つからないようなトポロジにおいても、十分な数の候補経路を見つけることができる。
【００５４】
図５は本発明の第２の実施の形態におけるエリア構成を示す図であり、図６は本発明の第２の実施の形態における動的なサブエリア分割の例を示す図であり、図７は本発明の第２の実施の形態による経路計算装置の動作を示すフローチャートであり、図８は本発明の第２の実施の形態による候補経路格納テーブルの構成を示す図である。これら図５〜図８を参照して本発明の第２の実施の形態について説明する。
【００５５】
本発明の第２の実施の形態による経路計算装置は経路計算手段１２のサブエリア分割手段１３がエリアを複数のサブエリアに分割するようにした以外は図１に示す本発明の第１の実施の形態による経路計算装置と同様の構成となっているので、本発明の第２の実施の形態についての説明でも図１に示す構成を用いるものとする。
【００５６】
本発明の第１の実施の形態ではサブエリア分割手段１３がエリアを２つのサブエリアに分割しているが、本発明の第２の実施の形態ではこれを複数のサブエリアに分割するようにしている（図７ステップＳ１１）。
【００５７】
この分割は本発明の第１の実施の形態と同様に、ソースノードにおいてある基準にしたがって仮想的かつ動的に行われてもよいし、ポリシ等を基にした設定によって静的に行われてもよい。分割したサブエリアのうち、ソースノードを含むものをローカルサブエリア（Ｌｏｃａｌ  Ｓｕｂａｒｅａ；ＬＳ）、ＬＳ以外をリモートサブエリア（Ｒｅｍｏｔｅ  Ｓｕｂａｒｅａ；ＲＳ）とし、複数のＲＳに対してＲＳ（１），ＲＳ（２），…と区別する。
【００５８】
図５に示すエリア４に対するのサブエリア分割はポリシによる設定によって行われた静的な分割の例を示している。ここでは、ノード１１１がソースノードであり、ノード１１１〜１１３によって構成されるＬＳ４１、ノード１１４〜１１６によって構成されるＲＳ（１）４２、ノード１１７〜１１９によって構成されるＲＳ（２）４３の３つのサブエリアに分割している。
【００５９】
また、図６にはリンクコストを基準に動的にサブエリアに分割する例について示している。この例では、ソースノードから１ホップ以内にあるノードをＬＳ４４、２ホップのノードをＲＳ（１）４５、３ホップ以上をＲＳ（２）４６と分割する場合であり、ノード１１１〜１１３がＬＳ４４、ノード１１４，１１５，１１７，１１８がＲＳ（１）４５、ノード１１６，１１９がＲＳ（２）４６をそれぞれ構成している。
【００６０】
以下、図５に示す静的なサブエリア分割の場合について述べるが、図６に示すような動的なサブエリア分割の場合についても、以下の処理動作を同様に適用することができる。
【００６１】
ステップＳ１１で分割した各サブエリア内のノードのうち、異なるサブエリア（但し、ＬＳは除く）内のノードに直接接続されているノードをＳＢＮとする（図７ステップＳ１２）。また、各ＳＢＮがどのサブエリアと直接接続されているのかも分かるようにしておく。図５に示す例では、ノード１１２，１１８がＲＳ（１）４２と直接接続されているＳＢＮ、ノード１１３，１１５がＲＳ（２）４３と直接接続されているＳＢＮである。
【００６２】
上記のサブエリア分割において、本発明の第１の実施の形態と同様に、リンクによってサブエリアを分割するのではなく、ノードによってサブエリアを分割してもよい。本実施の形態ではリンクによってサブエリアを分割する場合について述べる。
【００６３】
次に、サブエリア内候補経路計算手段１４によって、ＬＳ及び各ＲＳ内の候補経路を計算する。まず、ＬＳ内の候補経路として、ソースノードからＬＳ内の各宛先ノードまでの候補経路を計算する（図７ステップＳ１３）。
【００６４】
このステップＳ１３の動作は本発明の第１の実施の形態と同じ動作であり、計算に際してはＬＳ内のリンクステート情報だけが用いられる。例えば、図５に示すＬＳの場合には、図８に示す候補経路格納テーブル２２におけるＬＳ４１に対する候補経路リスト２２ｃのようになる。起点ノード１１１から宛先ノード１１２に対してはＰ１，Ｐ２の２つの候補経路が存在し、さらに宛先ノード１１２はＲＳ（１）４２に直接接続されているＳＢＮとなっていることが分かる。
【００６５】
また、各ＲＳ（１）４２，ＲＳ（２）４３内の候補経路を計算する（図７ステップＳ１４）。例えば、ＲＳ（１）４２内の候補経路を計算する場合、他サブエリア内におけるＲＳ（１）４２と直接接続されているＳＢＮを抽出する。そして各ＳＢＮを起点とするＲＳ（１）４２内の各宛先ノードまでの候補経路を計算する。この動作は本発明の第１の実施の形態と同様である。
【００６６】
この計算において、起点となるノード及びＲＳ（１）４２内のリンクステート情報のみが用いられる。ＲＳは複数存在するので、上記の計算を上記と同様にして、ＲＳ（２），ＲＳ（３），…についても行う。図５に示すＲＳ（１），ＲＳ（２）の場合、作成される候補経路リストはそれぞれ図８に示す候補経路リスト２２ｄ，２２ｅのようになる。
【００６７】
最後に、サブエリア内候補経路計算手段１４によって、ソースノードから各ＲＳ内の各宛先ノードまでの候補経路を求める（図７ステップＳ１５）。まず、各サブエリア同士の接続性を調べる。図５に示すエリア４に対しては、各サブエリア同士の接続性が図８に示すサブエリア接続テーブル２２ｆに示すようなツリー構造になる。
【００６８】
すなわち、サブエリア接続テーブル２２ｆによって、ＬＳからはノード１１２においてＲＳ（１）４２と、ノード１１３においてＲＳ（２）４３とにそれぞれ接続されており、さらにＲＳ（１）４２はノード１１５においてＲＳ（２）４３と、ＲＳ（２）４３はノード１１８においてＲＳ（１）４２とそれぞれ接続されているということがわかる。
【００６９】
次に、このサブエリア接続テーブル２２ｆを用いて、各サブエリア内の候補経路を、各サブエリア同士を接続するＳＢＮにおいて互いに関連付けることによって、ソースノードから各ＲＳ内の各宛先ノードまでの候補経路を作成する。ここでは、ＲＳ（１）４２内の候補経路を作成する場合について説明する。
【００７０】
サブエリア接続テーブル２２ｆによって、ソースノード１１１からＲＳ（１）４２へ至るためには、ＬＳ４１→ＳＢＮ（ノード１１２）→ＲＳ（１）４２、ＬＳ４１→ＳＢＮ（ノード１１３）→ＲＳ（２）４３→ＳＢＮ（ノード１１８）→ＲＳ（１）４２の２つの到達可能性があることがわかる。
【００７１】
例えば、ソースノード１１１からノード１１５までの候補経路は、ＬＳ４１→ＳＢＮ（ノード１１２）→ＲＳ（１）４２に対応して、ノード１１１からノード１１２までの候補経路｛Ｐ１，Ｐ２｝とノード１１２からノード１１５までの候補経路｛Ｐ７，Ｐ８｝との関連付けによって作成される。これは２×２＝４本の候補経路を作ることに相当する。
【００７２】
また、ＬＳ４１→ＳＢＮ（ノード１１３）→ＲＳ（２）４３→ＳＢＮ（ノード１１８）→ＲＳ（１）４２に対応して、ノード１１１からノード１１３までの候補経路｛Ｐ３，Ｐ４｝、ノード１１３からノード１１８までの候補経路｛Ｐ１４｝、ノード１１８からノード１１５までの候補経路｛Ｐ１１｝の関連付けによって作成される。これは２×１×１＝２本の候補経路を作ることに相当する。
【００７３】
結果として、ソースノード１１１からノード１１５までの候補経路として、２×２＋２×１×１＝６本の候補経路が作成される。同様の関連付けは他のＲＳ（１）４２内の宛先ノードに対しても行われ、さらにＲＳ（２）４３に対してもＲＳ（１）４２と同様の手順によって候補経路の作成が行われる。
【００７４】
本実施の形態では、エリアを複数のサブエリアに分割することができる。２つのサブエリアに分割する場合と比べて、網トポロジの特性に応じた、より柔軟なサブエリア分割が可能であり、すなわちより柔軟な候補経路作成が可能である。また、２つのサブエリアに分割する場合よりも１つ当たりのサブエリア内のノード数及びリンク数は小さいので、１回当たりのダイクストラ計算の計算量を削減することができる。但し、１回当たりの計算量と計算回数との積によって全体の計算量が決まるので、全体の計算量を削減するためには計算回数を大きく増やさないことが重要である。
【００７５】
図９は本発明の第３の実施の形態による経路計算装置の構成を示すブロック図である。図９において、本発明の第３の実施の形態による経路計算装置は、本発明の第１及び第２の実施の形態による経路計算装置と同様に、データ処理装置１及び記憶装置２を備え、さらにルーティングプロトコル手段１１と経路計算手段１２と候補経路検索手段１６とで動作するプログラムを記録した記録媒体５を備えている。この記録媒体５は磁気ディスクや半導体メモリ、その他の記録媒体であってよい。
【００７６】
ルーティングプロトコル手段１１と経路計算手段１２と候補経路検索手段１６とは記録媒体５からデータ処理装置１に読込まれ、ルーティングプロトコル手段１１によって収集されたルーティング情報をルーティング情報記憶部２１に記憶する。ルーティング情報記憶部２１内のルーティング情報を用いて、経路計算手段１２は上述した本発明の第１及び第２の実施の形態における処理と同一の経路計算を実行する。
【００７７】
経路計算手段１２によって計算された経路は候補経路格納テーブル２２に格納され、候補経路検索手段１６を介して経路計算要求に対して要求を満たす候補経路の応答を行う。
【００７８】
図１０は本発明の一実施例における候補経路格納テーブルを示す図である。この図１０を参照して本発明の一実施例について説明する。本実施例は本発明の第１の実施の形態に対応するものであり、特に、本発明の第１の実施の形態の動作において、ソースノードからエリア内の各宛先ノードまでの候補経路の計算方法について具体的な例を挙げて説明する。
【００７９】
本実施例では図２に示すエリア３において、ソースノード（ノード１０１）からエリア３内の各宛先ノード（ノード１０２〜１１０）までの候補経路を計算する。
【００８０】
まず、エリア３において、ソースノードからの最小ホップ数の小さい順に半数のノードを抽出し、それらのノードから構成される網をＬＳとし、さらに残りの半数のノードから構成される網をＲＳとする。すなわち、サブエリア３１，３２がそれぞれＬＳ、ＲＳとなる。また、ＬＳ内のノードのうち、ＲＳ内のノードに直接接続されているノードをＳＢＮとする。ノード１０３，１０４がＳＢＮとなる。
【００８１】
次に、ソースノードからＬＳ内の各宛先ノード（ノード１０２〜１０５）までの候補経路をＫＳＰアルゴリズム（ｋ＝３とする）を用いて計算する。この候補経路計算において、ＬＳ内のリンクステート情報のみが用いられる。候補経路計算の結果、図１０に示す候補経路格納テーブル２２内の候補経路リスト２２ｇに示される候補経路が作成される。
【００８２】
さらに、各ＳＢＮからＲＳ内の宛先ノード（ノード１０６〜１１０）までの候補経路を最短経路木計算によって作成する。ＳＢＮの数は２つであるため、２回の最短経路木計算が必要となる。これは２回のダイクストラ計算を行うことに相当する。この候補経路計算において、起点となるＳＢＮ及びＲＳ内のリンクステート情報のみが用いられる。候補経路計算の結果、候補経路格納テーブル２２内の候補経路リスト２２ｈに示される候補経路が作成される。
【００８３】
最後に、ソースノードからＲＳ内の各宛先ノードまでの候補経路を求める。ソースノードからＳＢＮとなっているＬＳ内の宛先ノードまでの候補経路に対し、各ＳＢＮにおいて、そのＳＢＮを起点とするＲＳ内の候補経路を関連付ける。
【００８４】
図２のエリア３においては、ノード１０３，１０４がＳＢＮであるため、候補経路リスト２２ｇにおけるノード１０１からノード１０３までの候補経路に、候補経路リスト２２ｈにおけるノード１０３からＲＳ内の各宛先ノードまでの候補経路が関連付けられ、さらに候補経路リスト２２ｇにおけるノード１０１からノード１０４までの候補経路に、候補経路リスト２２ｈにおけるノード１０４からＲＳ内の各宛先ノードまでの候補経路が関連付けられる。
【００８５】
例えば、ノード１０３を経由する宛先ノード１０８までの候補経路を作るために、｛［１０１→１０３］，［１０１→１０２→１０３］，［１０１→１０４→１０３］｝に｛［１０３→１０７→１０８］｝が関連付けられる。ノード１０４を経由する候補経路も同様にして作られる。この場合、ノード１０１からノード１０８までの候補経路として、３×１＋３×１＝６本作られることに相当する。
【００８６】
図１１は本発明の他の実施例における候補経路格納テーブルを示す図である。この図１１を参照して本発明の他の実施例について説明する。本実施例は本発明の第２の実施の形態に対応するものである。
【００８７】
本実施例では図５に示すエリア４において、ソースノード（ノード１１１）から、エリア４内の各宛先ノード（ノード１１２〜１１９）までの候補経路を計算する。
【００８８】
まず、エリア４内のノードを３つのサブエリアに分割する。ポリシによる静的な設定によってノード１１１〜１１３から構成されるＬＳ４１、ノード１１４〜１１６によって構成されるＲＳ（１）４２、ノード１１７〜１１９によって構成されるＲＳ（２）４３の３つに分割される。また、分割された各サブエリア内のノードのうち、異なるサブエリア（ただしＬＳは除く）内のノードと直接接続されているノードをＳＢＮとする。さらに、各ＳＢＮがどのサブエリアと直接接続されているのかも分かるようにしておく。ここでは、ノード１１２，１１８がＲＳ（１）４２と直接接続されているＳＢＮ、ノード１１３，１１５がＲＳ（２）４３と直接接続されているＳＢＮである。
【００８９】
次に、ソースノードからＬＳ内の各宛先ノード（ノード１１２，１１３）までの候補経路をＫＳＰアルゴリズム（ｋ＝３とする）を用いて計算する。この候補経路計算において、ＬＳ内のリンクステート情報のみが用いられる。候補経路計算の結果、図１１に示す候補経路格納テーブル２２内の候補経路リスト２２ｉに示される候補経路が作成される。
【００９０】
また、各ＲＳ内の候補経路を最短経路木計算によって計算する。ここではＲＳ（１）４２内の候補経路を計算する場合について述べる。まず、ＲＳ（１）４２と直接接続されているＳＢＮであるノード１１２，１１８を抽出する。そしてノード１１２，１１８のそれぞれを起点とするＲＳ（１）４２内の各宛先ノード（ノード１１４〜１１６）までの最短経路木を計算し、求められた経路を候補経路とする。この計算において、起点となるノード及びＲＳ（１）４２内のリンクステート情報のみが用いられる。上記と同様の計算はＲＳ（２）４３についても行われる。作成されたＲＳ（１）４２，ＲＳ（２）４３内の候補経路は図１１に示す候補経路格納テーブル２２内の候補経路リスト２２ｊ，２２ｋに示されるものとなる。
【００９１】
最後に、ソースノードから各ＲＳ内の各宛先ノードまでの候補経路を求める。まず、各サブエリア同士の接続性を調べる。図５に示すエリア４に対しては、各サブエリア同士の接続性が図１１に示すサブエリア接続テーブル２２ｌに示すようなツリー構造になる。
【００９２】
次に、このサブエリア接続テーブル２２ｌを用いて、各サブエリア内の候補経路を、各サブエリア同士を接続するＳＢＮにおいて互いに関連付けることによって、ソースノードから各ＲＳ内の各宛先ノードまでの候補経路を作成する。
【００９３】
ここでは、ＲＳ（２）４３内のノード１１９までの候補経路を作る手順について述べる。サブエリア接続テーブル２２ｌによって、ソースノードからＲＳ（２）４３へ至るためには、ＬＳ４１→ＳＢＮ（ノード１１３）→ＲＳ（２）４３、ＬＳ４１→ＳＢＮ（ノード１１２）→ＲＳ（１）４２→ＳＢＮ（ノード１１５）→ＲＳ（２）４３の２つの到達可能性があることがわかる。
【００９４】
ＬＳ４１→ＳＢＮ（ノード１１３）→ＲＳ（２）４３に対応して、｛［１１１→１１３］，［１１１→１１２→１１３］｝，｛［１１３→１１７→１１９］｝が関連付けられ、ＬＳ４１→ＳＢＮ（ノード１１２）→ＲＳ（１）４２→ＳＢＮ（ノード１１５）→ＲＳ（２）４３に対応して、｛［１１１→１１２］，［１１１→１１３→１１２］｝，｛［１１２→１１５］｝，｛［１１５→１１８→１１９］｝が関連付けられる。
【００９５】
結果として、ソースノードからノード１１９までの候補経路として、２×１＋２×１×１＝４本の候補経路を作ることに相当する。同様の関連付けは他のＲＳ（２）４３内の他の宛先ノードに対しても行われ、さらにＲＳ（１）４２に対しても上記のＲＳ（２）４３と同様の手順によって候補経路の作成が行われる。
【００９６】
このように、候補経路計算において、分割されたサブエリア内のリンクステート情報のみを用いてダイクストラ計算が行われるため、エリア全体のリンクステート情報を用いてダイクストラ計算を行う場合よりも１回当たりのダイクストラ計算の計算量を削減することができ、また各サブエリア内の候補経路計算に用いられる計算アルゴリズムの組合わせを工夫することによって、ＫＳＰアルゴリズムよりも計算回数を削減することができる。したがって、エリア内の各宛先ノードへの候補経路計算に要する計算量をＫＳＰアルゴリズムと比較して削減することができる。
【００９７】
さらに、リモートサブエリア内の候補経路に関してはサブエリアボーダーノードにおける各サブエリア内候補経路の関連付けによって多くの候補経路を作成することができる。これはＫＳＰアルゴリズムによって十分な数の候補経路が見つからないようなトポロジにおいても有効であり、結果として呼損率の低減につながる。
【００９８】
【発明の効果】
以上説明したように本発明の経路計算装置によれば、候補経路計算において、分割されたサブエリア内のリンクステート情報のみを用いてダイクストラ計算を行うことによって、ソースノードから各宛先ノードまでの候補経路を求める計算において、ＫＳＰアルゴリズムよりも計算量の小さいアルゴリズムを実現することができるという効果がある。
【００９９】
また、本発明の他の経路計算装置によれば、リモートサブエリア内の候補経路に関して、サブエリアボーダーノードにおける各サブエリア内候補経路の関連付けを行うことによって、ＫＳＰアルゴリズムによって十分な数の候補経路が見つからないようなトポロジにおいても、十分な数の候補経路を見つけることができ、呼損率を悪化させないようなアルゴリズムを実現することができるという効果がある。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態による経路計算装置の構成を示すブロック図である。
【図２】本発明の第１の実施の形態におけるエリア構成を示す図である。
【図３】本発明の第１の実施の形態による経路計算装置の動作を示すフローチャートである。
【図４】図１の候補経路格納テーブルの構成を示す図である。
【図５】本発明の第２の実施の形態におけるエリア構成を示す図である。
【図６】本発明の第２の実施の形態における動的なサブエリア分割の例を示す図である。
【図７】本発明の第２の実施の形態による経路計算装置の動作を示すフローチャートである。
【図８】本発明の第２の実施の形態による候補経路格納テーブルの構成を示す図である。
【図９】本発明の第３の実施の形態による経路計算装置の構成を示すブロック図である。
【図１０】本発明の一実施例における候補経路格納テーブルを示す図である。
【図１１】本発明の他の実施例における候補経路格納テーブルを示す図である。
【符号の説明】
１  データ処理装置
２  記憶装置
３，４  エリア
５  記録媒体
１１  ルーティングプロトコル手段
１２  経路計算手段
１３  サブエリア分割手段
１４  サブエリア内候補経路計算手段
１５  サブエリア内候補経路関連付け手段
１６  候補経路検索手段
２１  ルーティング情報記憶部
２２  候補経路格納テーブル
２２ａ〜２２ｅ，
２２ｇ〜２２ｋ  候補経路リスト
２２ｆ，２２ｌ  サブエリア接続テーブル
３１，４１，４４  ローカルサブエリア
３２，４２，４３，
４５，４６  リモートサブエリア
１０１〜１１９  ノード
２０１〜２２９  リンク
【図１】
0003815206.tif 000002
【図２】
0003815206.tif 000003
【図３】
0003815206.tif 000004
【図４】
0003815206.tif 000005
【図５】
0003815206.tif 000006
【図６】
0003815206.tif 000007
【図７】
0003815206.tif 000008
【図８】
0003815206.tif 000009
【図９】
0003815206.tif 000010
【図１０】
0003815206.tif 000011
【図１１】
0003815206.tif 000012