(57)【要約】【課題】リンクコストとしてリンクごとに個別のトラヒック量を用いた場合でも計算処理負荷を軽減でき、同一ノード間で複数の経路を迅速に選択できるようにする。【解決手段】経路制御装置３０で、送信元ノードから宛先ノードへの第１の経路を選択後に、当該経路を除く新たなトポロジを作成し、第１の経路とは異なる送信元ノードから宛先ノードへの第２の経路の後半経路として、接続点となる中継ノードと宛先ノードとの経路を選択し、第１の経路の選択処理ですでに得られた送信元ノードから接続点となるノードへの前半経路と上記後半経路とを合成した経路を、第２の経路として選択する。【選択図】  図１
2006074126.tif 000002
【特許請求の範囲】
【請求項１】
リンクを介して網状に接続された複数のノードからなるパケット通信ネットワークに設けられ、パケット通信を行う送信元ノードから次のノードへの経路を当該ネットワークから順次選択していくことにより、前記送信元ノードから所望の宛先ノードまでの経路を選択する経路制御装置であって、
前記各リンクでのパケット転送状況を示すリンク情報を前記各ノードから収集するリンク情報収集部と、
送信元ノードから任意のノードへの経路を選択する際、当該ノードへの経路をそれぞれ評価する最適化パラメータ値に基づき、前記ノードへの経路のいずれかを当該ノードへの経路として選択する経路選択部と、
前記リンク情報収集部で収集されたリンク情報、前記ノードの最適化パラメータ値、および前記経路選択部で選択した各ノードへの経路を記憶する記憶部とを備え、
前記経路選択部は、前記ノードの最適化パラメータ値を算出する際、前記記憶部に記憶されている前記ノードへの経路を構成する各リンクのリンク情報から前記最適化パラメータ値を算出し、
前記経路選択部は、前記第１の経路とは異なる第２の経路を選択する際、
前記送信元ノードから前記宛先ノードまでの経路を最初に選択した後、その第１の経路を構成するリンクおよびノードを除くリンクおよびノードから当該ネットワークの新たなトポロジを作成し、
前記第２の経路の後半経路として、前記宛先ノードから前記トポロジ内の任意のノードへの経路を前記トポロジから選択し、
前記第２の経路の前半経路として、前記送信元ノードから前記トポロジ内の任意のノードへの前半経路を前記記憶部から選択し、
前記前半経路と前記後半経路とを合成した経路を前記第２の経路として選択する
ことを特徴とする経路制御装置。
【請求項２】
請求項１に記載の経路制御装置において、
前記経路選択部は、前記前半経路と前記後半経路の接続点となる前記ノードとして、前記記憶部から最適化パラメータ値が最大のノードを選択することを特徴とする経路制御装置。
【請求項３】
リンクを介して網状に接続された複数のノードからなるパケット通信ネットワークに設けられた経路制御装置で、パケット通信を行う送信元ノードから次のノードへの経路を当該ネットワークから順次選択していくことにより、前記送信元ノードから所望の宛先ノードまでの経路を選択する経路選択方法であって、
前記各リンクでのパケット転送状況を示すリンク情報を前記各ノードから収集するリンク情報収集ステップと、
送信元ノードから任意のノードへの経路を選択する際、当該ノードへの経路をそれぞれ評価する最適化パラメータ値に基づき、前記ノードへの経路のいずれかを当該ノードへの経路として選択する経路選択ステップと、
前記リンク情報収集部で収集されたリンク情報、前記ノードの最適化パラメータ値、および前記経路選択部で選択した各ノードへの経路を記憶部で記憶する記憶ステップとを備え、
前記経路選択ステップは、前記ノードの最適化パラメータ値を算出する際、前記記憶部に記憶されている前記ノードへの経路を構成する各リンクのリンク情報から前記最適化パラメータ値を算出し、
前記経路選択ステップは、前記第１の経路とは異なる第２の経路を選択する際、
前記送信元ノードから前記宛先ノードまでの経路を最初に選択した後、その第１の経路を構成するリンクおよびノードを除くリンクおよびノードから当該ネットワークの新たなトポロジを作成するステップと、
前記第２の経路の後半経路として、前記宛先ノードから前記トポロジ内の任意のノードへの経路を前記トポロジから選択するステップと、
前記第２の経路の前半経路として、前記送信元ノードから前記トポロジ内の任意のノードへの前半経路を前記記憶部から選択ステップと、
前記前半経路と前記後半経路とを合成した経路を前記第２の経路として選択するステップとを行う
ことを特徴とする経路選択方法。
【請求項４】
請求項３に記載の経路選択方法において、
前記経路選択ステップは、前記前半経路と前記後半経路の接続点となる前記ノードとして、前記記憶部から最適化パラメータ値が最大のノードを選択することを特徴とする経路選択方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット通信技術に関し、特にパケット通信に用いる最適経路を選択する経路選択技術に関する。
【背景技術】
【０００２】
近年、インターネットの利用者数の急増や、大容量データをやり取りするアプリケーションの急速な普及により、インターネットの中心部にある大規模なバックボーンネットワークのトラヒック量が爆発的に増加している。したがって、バックボーンネットワークのトラヒック収容能力の向上が求められている。
【０００３】
トラヒックを分散しバックボーンネットワークのトラヒック収容能力を向上させるために、同一ノード間に互いに同一のノードやリンクを経由しない複数の経路を設定し、トラヒック状況に応じて、動的にトラヒックを分散させるトラヒックエンジニアリング技術が検討されている。加えて、一方の経路が通信不能になった際に他の経路へ切り替えることで、ネットワークの信頼性を高めることにも利用されている（例えば、非特許文献１など参照）
【０００４】
同一ノード間の経路を複数選択するの経路選択方法としては、最短経路ルーティングアルゴリズム（Shortest Path First）を改良した等価マルチパスアルゴリズム（Equal Cost Multi Path）がある。このアルゴリズムは、同一のノード間にコストが同一である複数の経路を計算する（例えば、非特許文献２など参照）。
しかしながら、上記の経路選択方法は、同一ノード間にコストの異なる経路しかなかった場合、これら経路を複数出力することができない。特にコストとしてリンクに個別のトラヒック量を用いると、実際にはリンクごとにトラヒック量は大きく異なる場合が多く、同一コストの経路が存在する可能性は低い。このため、必ずしも複数経路を計算できない問題がある。
【０００５】
これに対して、従来、同一ノード間で互いに同一のノードやリンクを経由せずにトラヒックを分散配置する経路選択問題を組合せ最適化問題であると捉え、最適解を求める手法として、数理計画法、遺伝的アルゴリズム（ＧＡ：Genetic Algorithm）、あるいはシミュレーテッド・アニーリング法（ＳＡ：Simulated Annealing）を用いた手法が提案されている（例えば、非特許文献３など参照）。
【０００６】
なお、出願人は、本明細書に記載した先行技術文献情報で特定される先行技術文献以外には、本発明に関連する先行技術文献を出願時までに発見するには至らなかった。
【非特許文献１】「ＩＰネットワークにおけるデッドラインに基づく優先制御・経路制御法」、電子情報通信学会論文誌VOL.J86-B No.12、p2501、電子情報通信学会、2003年12月
【非特許文献２】「ＲＦＣ３２７２  Overview and Principles of Internet Traffic Engineering 」、p30、THE INTERNET ENGINEERING TASK FORCE、2002年5月
【非特許文献３】「次世代インターネットとトラヒック工学」、電子情報通信学会論文誌VOL.J85-B No.6、pp875-889、電子情報通信学会、2002年6月
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、このような従来技術では、問題の規模の増加に伴い計算時間が急増する傾向があり、各リンクに個別のトラヒック情報などをコストとして用いた場合、実際にはリンクごとにトラヒック量は大きく異なる場合が多く、同一ノード間で複数の経路を計算するために時間を要していた。このため、バックボーンネットワークのような大規模ネットワークにおいて、トラヒックエンジニアリング技術のようなトラヒック変動に対する動的な経路制御における経路選択方法としての適用性が低いという問題があった。
【０００８】
本発明はこのような課題を解決するためのものであり、リンクコストとしてリンクごとに個別のトラヒック量を用いた場合でも計算処理負荷を軽減でき、同一ノード間で複数の経路を迅速に選択できる経路制御装置および経路選択方法を提供することを目的としている。
【課題を解決するための手段】
【０００９】
このような目的を達成するために、本発明にかかる経路制御装置は、リンクを介して網状に接続された複数のノードからなるパケット通信ネットワークに設けられ、パケット通信を行う送信元ノードから次のノードへの経路を当該ネットワークから順次選択していくことにより、送信元ノードから所望の宛先ノードまでの経路を選択する経路制御装置であって、各リンクでのパケット転送状況を示すリンク情報を各ノードから収集するリンク情報収集部と、送信元ノードから任意のノードへの経路を選択する際、当該ノードへの経路をそれぞれ評価する最適化パラメータ値に基づき、ノードへの経路のいずれかを当該ノードへの経路として選択する経路選択部と、リンク情報収集部で収集されたリンク情報、ノードの最適化パラメータ値、および経路選択部で選択した各ノードへの経路を記憶する記憶部とを備え、経路選択部で、ノードの最適化パラメータ値を算出する際、記憶部に記憶されているノードへの経路を構成する各リンクのリンク情報から最適化パラメータ値を算出し、経路選択部は、第１の経路とは異なる第２の経路を選択する際、送信元ノードから宛先ノードまでの経路を最初に選択した後、その第１の経路を構成するリンクおよびノードを除くリンクおよびノードから当該ネットワークの新たなトポロジを作成し、第２の経路の後半経路として、宛先ノードからトポロジ内の任意のノードへの経路をトポロジから選択し、第２の経路の前半経路として、送信元ノードからトポロジ内の任意のノードへの前半経路を記憶部から選択し、前半経路と後半経路とを合成した経路を第２の経路として選択する。
【００１０】
この際、経路選択部で、前半経路と後半経路の接続点となるノードとして、記憶部から最適化パラメータ値が最大のノードを選択するようにしてもよい。
【００１１】
また、本発明にかかる経路選択方法は、リンクを介して網状に接続された複数のノードからなるパケット通信ネットワークに設けられた経路制御装置で、パケット通信を行う送信元ノードから次のノードへの経路を当該ネットワークから順次選択していくことにより、送信元ノードから所望の宛先ノードまでの経路を選択する経路選択方法であって、各リンクでのパケット転送状況を示すリンク情報を各ノードから収集するリンク情報収集ステップと、送信元ノードから任意のノードへの経路を選択する際、当該ノードへの経路をそれぞれ評価する最適化パラメータ値に基づき、ノードへの経路のいずれかを当該ノードへの経路として選択する経路選択ステップと、リンク情報収集部で収集されたリンク情報、ノードの最適化パラメータ値、および経路選択部で選択した各ノードへの経路を記憶部で記憶する記憶ステップとを備え、経路選択ステップで、ノードの最適化パラメータ値を算出する際、記憶部に記憶されているノードへの経路を構成する各リンクのリンク情報から最適化パラメータ値を算出し、経路選択ステップで、第１の経路とは異なる第２の経路を選択する際、送信元ノードから宛先ノードまでの経路を最初に選択した後、その第１の経路を構成するリンクおよびノードを除くリンクおよびノードから当該ネットワークの新たなトポロジを作成するステップと、第２の経路の後半経路として、宛先ノードからトポロジ内の任意のノードへの経路をトポロジから選択するステップと、第２の経路の前半経路として、送信元ノードからトポロジ内の任意のノードへの前半経路を記憶部から選択ステップと、前半経路と後半経路とを合成した経路を第２の経路として選択するステップとを行う。
【００１２】
この際、経路選択ステップで、前半経路と後半経路の接続点となるノードとして、記憶部から最適化パラメータ値が最大のノードを選択するようにしてもよい。
【発明の効果】
【００１３】
本発明によれば、経路制御部の経路選択部で、第１の経路とは異なる第２の経路を選択する際、送信元ノードから宛先ノードまでの経路が最初に選択された後、その第１の経路を構成するリンクおよびノードを除くリンクおよびノードから当該ネットワークの新たなトポロジが作成され、第２の経路の後半経路として、宛先ノードからトポロジ内の任意のノードへの経路がトポロジから選択され、第２の経路の前半経路として、送信元ノードからトポロジ内の任意のノードへの前半経路を記憶部から選択され、前半経路と後半経路とを合成した経路が第２の経路として選択される。
【００１４】
これにより、第２の経路のうち前半経路については、第１の経路の計算結果を再利用することができる。したがって、従来のように最適解を求める手法として、数理計画法、遺伝的アルゴリズム（ＧＡ：Genetic Algorithm）、あるいはシミュレーテッド・アニーリング法（ＳＡ：Simulated Annealing）を経路選択に用いた場合と比較して、リンクコストとしてリンクごとに個別のトラヒック量を用いた場合でも計算処理負荷を軽減でき、同一ノード間で複数の経路を迅速に選択できる。
【発明を実施するための最良の形態】
【００１５】
次に、本発明の実施の形態について図面を参照して説明する。
［ネットワークモデル］
まず、図１を参照して、本発明の一実施の形態にかかる経路制御装置が適用される通信ネットワークについて説明する。図１は、本発明の一実施の形態にかかる経路制御装置が適用される通信ネットワークのネットワークモデル例を示すブロック図である。
この通信ネットワークは、ユーザ収容装置１０，１１、中継装置２０，２１、経路制御装置３０から構成され、各ユーザ端末４０，４１は、それぞれリンクを介して、ユーザ収容装置１０，１１にそれぞれ収容されている。
【００１６】
ユーザ収容装置１０，１１間は、リンク１００〜１０４と中継装置２０，２１によって接続されている。また経路制御装置３０は、管理ネットワーク３００を介して、ユーザ収容装置１０，１１および中継装置２０，２１と接続されている。
以下では、ユーザ収容装置１０，１１、中継装置２０，２１、およびユーザ収容装置１０，１１と中継装置２０，２１との間を接続するリンク１００〜１０４からバックボーンネットワーク２００を構成している。また、ユーザ収容装置１０，１１、中継装置２０，２１をバックボーンネットワーク２００を構成するノードという。
【００１７】
［経路制御装置］
次に、図２を参照して、本発明の一実施の形態にかかる経路制御装置について説明する。図２は、本発明の一実施の形態にかかる経路制御装置の構成を示すブロック図である。
この経路制御装置３０は、全体としてコンピュータを有する情報処理装置からなり、リンク情報収集部３１、経路選択部３２、経路制御部３３、および記憶部３４が設けられている。これら各部は、ＣＰＵでプログラムを実行することによりハードウェアとプログラムとを協働させて機能部を実現させる演算処理部（図示せず）や、管理ネットワーク３００を介して制御用パケットを送受信する通信インターフェース部（図示せず）から構成されている。
【００１８】
リンク情報収集部３１は、上記演算処理部により実現される機能部からなり、上記通信インターフェース部から管理ネットワーク３００を経由して、ユーザ収容装置１０，１１および中継装置２０，２１から各リンクでのパケット転送状況例えばトラヒック量を示すリンク情報を収集する機能と、収集したリンク情報から得たコスト値（例えばトラヒック量の逆数）に基づき記憶部３４に格納されているリンクコストテーブルを更新する機能を有している。
【００１９】
経路選択部３２は、上記演算処理部により実現される機能部からなり、パケット通信の送信元ノード（発側ノード）から宛先ノード（着側ノード）ヘの経路をＤｉｊｋｓｔｒａベースのアルゴリズムで計算する機能と、経路選択結果である経路とその経路上のノードの最適化パラメータ値とを記憶部３４の最適化パラメータテーブルと経路スタックに格納する機能と、経路スタックを検索して経路上のリンクとノードについて、記憶部３４のリンク使用可能性テーブルとノード使用可能性テーブルのフラグを使用不可能に変更する機能とを有している。
【００２０】
これに加えて、経路選択部３２は、リンク使用可能性テーブルとノード使用可能性テーブルを使用可能フラグで検索し、使用可能なノードとリンクのみから構成される新たなトポロジを作成する機能と、送信元ノードから宛先ノードへの経路が作成したトポロジ上に存在するかどうか確認する機能と、最適化パラメータテーブルをノード最適化パラメータ値でソートして最大値を持つノードを検索する機能と、宛先ノードから上記ノード宛の経路を上記トポロジ上で計算する機能と、計算結果を経路スタックヘ格納する機能とを有している。
【００２１】
なお、本発明でいう最適化パラメータ値とは、パケット通信の送信元ノードから任意のノードｕへの経路を選択する際、その選択基準に用いられる値であり、当該ノードｕへの経路を評価する評価値である。例えば、ＭＩＮ−ＭＡＸアルゴリズムでは、任意のノードｕへの経路を選択する際、ノードｕへの各経路ごとに最適化パラメータを求め、最適化パラメータが最大の経路を選択する。このとき、ノードｕにリンクを介して隣接している、すでに経路選択済みのノードｖまでの経路については、例えば送信元ノードからノードｖまでの選択済み経路を構成するリンクのコストの最小値すなわちノードｕの最適化パラメータが用いられる。
【００２２】
経路制御部３３は、上記演算処理部により実現される機能部からなり、記憶部３４に格納された経路スタックを検索する機能と、検索された経路を上記通信インターフェース部から管理ネットワーク３００を経由して、ユーザ収容装置１０，１１および中継装置２０，２１に設定する機能とを有している。
記憶部３４は、ハードディスクやメモリなどの記憶装置からなり、リンクコストテーブル３４Ａ、最適化パラメータテーブル３４Ｂ、経路スタック３４Ｃ、リンク使用可能性テーブル３４Ｄ、ノード使用可能性テーブル３４Ｅ、およびＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆをデータベースで管理し、リンク情報収集部３１、経路選択部３２、経路制御部３３からのアクセスに応じて、管理している値を提供したり、変更して保存したりする機能を有している。
【００２３】
図３は、記憶部３４で管理されているリンクコストテーブル３４Ａの構成例であり、図４は、記憶部３４で管理されている最適化パラメータテーブル３４Ｂの構成例であり、図５は、記憶部３４で管理されている経路スタック３４Ｃの構成例である。
また図６は、記憶部３４で管理されているリンク使用可能性テーブル３４Ｄの構成例であり、図７は、記憶部３４で管理されているノード使用可能性テーブル３４Ｅの構成例である。いずれの場合も、それぞれ経路選択開始前の値の例が示されている。
【００２４】
リンクコストテーブル３４Ａでは、ユーザ収容装置１０，１１および中継装置２０，２１の間を接続するリンク１００〜１０４ごとにそのリンクの評価値として、リンク情報収集部３１で収集されたリンク情報から得たリンクコストが管理される。最適化パラメータテーブル３４Ｂでは、ノードごとにその最適化パラメータ値を管理している。経路スタック３４Ｃでは、ノードごとにパケット通信の送信元ノードから当該ノードへの経路を管理している。
【００２５】
リンク使用可能性テーブル３４Ｄでは、リンク１００〜１０４ごとにそのリンクの使用可否が管理されている。ノード使用可能性テーブル３４Ｅでは、ノード１０，１１，２０，２１ごとにそのノードの使用可否が管理されている。ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆでは、ＭＩＮ−ＭＡＸアルゴリズムで用いる各種パラメータとして、例えば選択結果である経路や各ノードの最適化パラメータ値が管理されている。
【００２６】
本実施の形態では、経路制御装置３０の経路選択部３２で、Ｄｉｊｋｓｔｒａベースの経路選択アルゴリズムにより、パケット通信を行う送信元ノードから次のノードへの経路を当該ネットワークから順次選択していくことにより、送信元ノードから所望の宛先ノードまでの経路を選択する。そして、送信元ノードから宛先ノードヘの経路が１つ計算された際に、同時に送信元ノードから他のノードヘの経路が計算される特性を利用して、宛先ノードから他のノードに対する経路を選択し、すでに選択された経路と合成して送信元ノードから宛先ノードヘの他の経路を計算するようにしている。
【００２７】
具体的には、パケット通信の送信元ノードから宛先ノードまでの第１の経路選択後に、当該経路を構成するリンクおよびノードを除く新たなトポロジを作成し、第１の経路選択時に計算した最適化パラメータ値が最大のノードから宛先ノードまでの後半経路を上記トポロジ上で選択し、第１の経路選択時に選択済みの送信元ノードから最適化パラメータ値が最大のノードへの前半経路と上記後半経路とを合成した経路を、第１の経路とは異なる、宛先ノードから送信元ノードヘの第２の経路として選択している。
これにより、第１の経路の計算結果を再利用することができ、リンクコストとしてリンクごとに個別のトラヒック量を用いた場合でも計算処理負荷を軽減でき、同一ノード間で複数の経路を迅速に選択できる。
【００２８】
［経路制御装置の動作］
次に、図８を参照して、本発明の一実施の形態にかかる経路制御装置の動作について説明する。図８は、本発明の一実施の形態にかかる経路制御装置での経路選択処理を示すフローチャートである。
以下、前述した図１の通信ネットワークのうち、送信元ノードとなるユーザ収容装置１０から当該パケットの宛先ノードとなるユーザ収容装置１１への経路として、Ｄｉｊｋｓｔｒａベースの経路選択アルゴリズムの１つであるＭＩＮ−ＭＡＸアルゴリズムに基づき、複数の経路を選択する場合を例として説明する。
【００２９】
まず、経路制御装置３０は、リンク情報収集部３１により、管理ネットワーク３００を介してユーザ収容装置１０，１１および中継装置２０，２１から、各リンク１００〜１０４のリンク情報を収集し、そのリンク情報から得た、例えばトラヒック量の逆数からなるリンクコストを記憶部３４のリンクコストテーブル３４Ａに格納する（ステップ５００）。この例では、初期状態におけるリンクコストテーブル３４Ａとして、図１０に示した内容のリンクコストがそれぞれ記憶されているものとする。
【００３０】
［第１の経路の選択］
次に、経路制御装置３０は、ＭＩＮ−ＭＡＸアルゴリズム（例えば、特許文献１など参照）を用いて、送信元ノードから任意のノードへの経路を当該ネットワークから順次選択していくことにより、送信元ノードから所望の宛先ノードまでの第１の経路を選択する（ステップ５０１）。この際、送信元ノードから任意のノードへの経路として、当該ノードへの経路のうち、それぞれの経路を構成する各リンクのコストの最小値が最大となる経路が選択される。
図１０は、この際に用いるＭＩＮ−ＭＡＸアルゴリズムに関する定義および表記を示す説明図である。なお、この表記において、装置とはユーザ収容装置または中継装置を意味する。
【００３１】
ＭＩＮ−ＭＡＸアルゴリズムの処理開始時において、各パラメータは初期化される。図１１に、初期状態におけるＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆの記憶内容を示す。この際、図１１におけるＭＩＮ−ＭＡＸアルゴリズムパラメータの値は、図１０の定義に示されたパラメータの値と同じである。このうち、集合Ｖは経路選択対象となる全装置の集合である。また、集合Ｕは経路が確定した装置の集合であり、初期状態においてΦ（空集合）である。したがって集合Ｖ−Ｕは、経路未確定すなわち経路選択候補である装置の集合となる。経路は、経路選択処理により確定した任意の装置への経路であり、Ｃは各装置への最適化パラメータ値である。
【００３２】
［第１の経路の選択の１ステップ目］
まず、経路制御装置３０は、ＭＩＮ−ＭＡＸアルゴリズムを用いて、１ステップ目の経路選択処理を行う。図１１のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆにおいて、集合Ｖ−Ｕに含まれる装置のうち、ユーザ収容装置１０の持つコストＣ（１０）＝「∞（無限大）」が最大であるため、ユーザ収容装置１０が集合Ｕに含められる。そして、送信元ノードであるユーザ収容装置１０から経路選択対象ノードの１つであるユーザ収容装置１０への経路として「１０→１０」が求まる。この時点で、リンクのコストの最小値が最大である経路は、ユーザ収容装置１０からユーザ収容装置１０に至る経路であるが、リンクが含まれないので実質的にはまだ求まっていない。
【００３３】
続いて、集合Ｖ−Ｕに含まれている装置のうち、集合Ｕに含まれる任意の装置ここではユーザ収容装置１０とリンクを介して隣接する装置のコストすなわち最適化パラメータ値を、ＭＩＮ−ＭＡＸアルゴリズムに基づき、当該装置に至る経路上にあるリンクのコストの最小値に更新する。この場合、ユーザ収容装置１０に隣接する中継装置２０のコストＣ（２０）は、図９のリンクコストテーブル３４Ａのリンク１００より「４」となる。また、ユーザ収容装置１０に隣接する中継装置２１のコストＣ（２１）は、同じくリンク１０１より「３」となる。
この時点におけるＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆは、図１２の値を取る。
【００３４】
［第１の経路の選択の２ステップ目］
次に、経路制御装置３０は、ＭＩＮ−ＭＡＸアルゴリズムを用いて、２ステップ目の経路選択処理を行う。まず、図１２のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆにおいて、集合Ｖ−Ｕに含まれる装置のうち、中継装置２０の持つコストＣ（２０）＝「４」が最大であるため、中継装置２０が集合Ｕへ含められる。そして、コストＣ（２０）が計算された経路に基づき、送信元ノードであるユーザ収容装置１０から経路選択対象ノードの１つである中継装置２０への経路として「１０→２０」が求まる。
【００３５】
続いて、集合Ｖ−Ｕに含まれている装置のうち、集合Ｕに含まれる任意の装置とリンクを介して隣接する装置のコストが更新される。ここでは、中継装置２０に隣接するユーザ収容装置１１のコストＣ（１１）は、図９のリンクコストテーブル３４Ａにおけるリンク１０３のコスト「２」と中継装置２０のコストＣ（２０）＝「４」との最小値「２」となる。また、中継装置２０に隣接する中継装置２１のコストＣ（２１）は、リンク１０２よりコスト「１」と中継装置２０のコストＣ（２０）＝「４」との最小値「１」となるが、それまでに求められているユーザ収容装置１０から中継装置２１への経路のコストＣ（２１）＝「３」の方が大きいため、コストＣ（２１）＝「３」のままとなる。
この時点におけるＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆは、図１３の値を取る。
【００３６】
［第１の経路の選択の３ステップ目］
次に、経路制御装置３０は、ＭＩＮ−ＭＡＸアルゴリズムを用いて、３ステップ目の経路選択処理を行う。まず、図１３のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆにおいて、集合Ｖ−Ｕに含まれる装置のうち、中継装置２１の持つコストＣ（２１）＝「３」が最大であるため、中継装置２１が集合Ｕへ含められる。そして、コストＣ（２１）が計算された経路に基づき、送信元ノードであるユーザ収容装置１０から経路選択対象ノードの１つである中継装置２１への経路として「１０→２１」が求まる。
【００３７】
続いて、集合Ｖ−Ｕに含まれている装置のうち、集合Ｕに含まれる任意の装置とリンクを介して隣接する装置のコストが更新される。ここでは、中継装置２１に隣接するユーザ収容装置１１のコストＣ（１１）は、図９のリンクコストテーブル３４Ａにおけるリンク１０４のコスト「３」と中継装置２１のコストＣ（２１）＝「３」との最小値「３」となる。この際、それまでに求められている中継装置２０からユーザ収容装置１１からの経路のコストＣ（１１）＝「２」の方が小さいため、コストが最大である中継装置２１からの経路が選択され、コストＣ（２１）＝「３」に更新される。
この時点におけるＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆは、図１４の値を取る。
【００３８】
［第１の経路の選択の４ステップ目］
次に、経路制御装置３０は、ＭＩＮ−ＭＡＸアルゴリズムを用いて、４ステップ目の経路選択処理を行う。まず、図１４のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆにおいて、集合Ｖ−Ｕに含まれる装置のうち、ユーザ収容装置１１の持つコストＣ（１１）＝「３」が最大であるため、ユーザ収容装置１１が集合Ｕへ含められる。そして、コストＣ（１１）が計算された経路に基づき、送信元ノードであるユーザ収容装置１０から経路選択対象ノードの１つである中継装置２１への経路として「１０→２１→２０」が求まる。
【００３９】
これにより、送信元ノードであるユーザ収容装置１０から宛先ノードである所望のユーザ収容装置１１までの経路として、第１の経路が選択されたことになり、経路選択部３２における第１の経路の選択処理が終了する（ステップ５０１）。
この時点におけるＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆは、図１５の値を取る。
【００４０】
次に、経路選択部３２は、図１５のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆから、各ノードのコストＣ（１０），Ｃ（１１），Ｃ（２０），Ｃ（２１）を、記憶部３４の最適化パラメータテーブル３４Ｂに格納する（ステップ５０２）。この時点における最適化パラメータテーブル３４Ｂは、図１６の値を取る。
また、図１５のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆから、第１の経路の選択処理で得られた、送信元ノードから各ノードへの経路を、記憶部３４の経路スタック３４Ｃに格納する（ステップ５０２）。この時点における経路スタック３４Ｃは、図１７の値を取る。
【００４１】
続いて、経路選択部３２は、送信元ノードから宛先ノードへの第１の経路とは異なる第２の経路の選択を行うため、第１の経路を構成するリンクおよびノード以外のリンクおよびノードに基づきバックボーンネットワーク２００の新たなトポロジを作成する。
まず、図１７の経路スタック３４Ｃの宛先ノードであるユーザ収容装置１１への経路を参照して、記憶部３４のリンク使用可能性テーブル３４Ｄのうち、第１の経路で用いたリンク１０１，１０４を使用不可能に設定する（ステップ５０３）。この時点におけるリンク使用可能性テーブル３４Ｄは、図１８の値を取る。
また、記憶部３４のノード使用可能性テーブル３４Ｅのうち、第１の経路で用いたノードすなわち中継装置２１を使用不可能に設定する（ステップ５０３）。この時点におけるノード使用可能性テーブル３４Ｅは、図１９の値を取る。
【００４２】
そして、経路選択部３２は、記憶部３４のリンク使用可能性テーブル３４Ｄとノード使用可能性テーブル３４Ｅとを参照し、そのうち使用可能なリンクおよびノードから構成されるバックボーンネットワーク２００の新たなトポロジを作成する（ステップ５０４）。
図２０は、ステップ５０４で作成された新たなトポロジを示す説明図である。ここでは、リンク１００，１０２，１０３と中継装置２０から、送信元ノードであるユーザ収容装置１０と宛先ノードであるユーザ収容装置１１とを接続するバックボーンネットワーク２００の新たなトポロジが作成されている。
【００４３】
次に、経路制御装置３０は、図２０のトポロジにおいて、深さ優先選択を用いて、ユーザ収容装置１１からユーザ収容装置１０までの到達性を確認する（ステップ５０５）。すなわち、宛先ノードであるユーザ収容装置１１からリンクを介して接続されている中継装置を検索し、さらに当該中継装置に接続しているリンクをたどることで、ユーザ収容装置１０が接続されているかどうか確認する。
具体的には、図２０のトポロジにおいて、ユーザ収容装置１１に接続されているリンク１０３から中継装置２０へたどり、さらに中継装置２０に接続されているリンク１００からユーザ収容装置１０が接続されていることが確認される。
【００４４】
このようにして、送信元ノードから宛先ノードまでの経路が、図２０のトポロジ上に存在することを確認した後（ステップ５０５：ＹＥＳ）、経路選択部３２は、記憶部３４の最適化パラメータテーブル３４Ｂを、その最適化パラメータ値でソートするなどして、最大の最適化パラメータ値を持つノードここでは中継装置２０を、第２の経路の前半経路と後半経路を接続する接続点として選択する（ステップ５０６）。なお、ユーザ収容装置１０の最適化パラメータ値は「∞（無限大）」の値が付与されているため、ここでのノード選択候補から除外する。
【００４５】
そして、経路選択部３２は、図２０のトポロジにおいて、第１の経路とは異なる第２の経路を選択するため、その第２の経路の後半経路、すなわち宛先ノードであるユーザ収容装置１１から上記で選択した接続点となる中継装置２０までの経路について、経路選択処理を行う（ステップ５０７）。
この経路選択処理については、前述した第１の経路に関する経路選択処理と同様に、ＭＩＮ−ＭＡＸアルゴリズム（例えば、特許文献１など参照）が用いられる。ＭＩＮ−ＭＡＸアルゴリズムの処理開始時において、各パラメータは初期化される。図２２に、初期状態におけるＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆの記憶内容を示す。
【００４６】
［後半経路の選択の１ステップ目］
まず、経路制御装置３０は、ＭＩＮ−ＭＡＸアルゴリズム（例えば、特許文献１など参照）を用いて、１ステップ目の経路選択処理を行う。図２２のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆにおいて、集合Ｖ−Ｕに含まれる装置のうち、ユーザ収容装置１１の持つコストＣ（１１）＝「∞」が最大であるため、ユーザ収容装置１１が集合Ｕに含まれる。そして、ユーザ収容装置１１から経路選択対象ノードの１つであるユーザ収容装置１１への経路として「１１→１１」が求まる。この時点で、リンクのコストの最小値が最大である経路は、ユーザ収容装置１０からユーザ収容装置１０に至る経路であるが、リンクが含まれないので実質的にはまだ求まっていない。
【００４７】
続いて、集合Ｖ−Ｕに含まれている装置のうち、集合Ｕに含まれる任意の装置ここではユーザ収容装置１１とリンクを介して隣接する装置のコストすなわち最適化パラメータ値を、ＭＩＮ−ＭＡＸアルゴリズムに基づき、当該装置に至る経路のリンクコストの最小値とする。この場合、ユーザ収容装置１１に隣接する中継装置２０のコストＣ（２０）は、図９のリンクコストテーブル３４Ａのリンク１０３より「２」となる。
この時点におけるＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆは、図２３の値を取る。
【００４８】
［後半経路の選択の２ステップ目］
次に、経路制御装置３０は、ＭＩＮ−ＭＡＸアルゴリズムを用いて、２ステップ目の経路選択処理を行う。まず、図２３のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆにおいて、集合Ｖ−Ｕに含まれる装置のうち、中継装置２０の持つコストＣ（２０）＝「２」が最大であるため、中継装置２０が集合Ｕへ含められる。そして、コストＣ（２０）が計算された経路に基づき、宛先ノードであるユーザ収容装置１１から経路選択対象ノードの１つである中継装置２０への経路として「１１→２０」が求まる。
【００４９】
これにより、宛先ノードであるユーザ収容装置１１から接続点である所望の中継装置２０までの後半経路が選択されたことになり、経路選択部３２における後半経路の選択処理が終了する（ステップ５０７）。
この時点におけるＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆは、図２４の値を取る。
【００５０】
続いて、経路選択部３２は、第２の経路を構成する前半経路、すなわちパケットの送信元ノードであるユーザ収容装置１０から接続点となる中継装置２０までの経路として「１０→２０」を、記憶部３４の経路スタック３４Ｃ（図１７参照）から選択する（ステップ５０８）。
次に、記憶部３４のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル３４Ｆ（図２４参照）で記憶しているユーザ収容装置１１から中継装置２０までの後半経路「１１→２０」と、上記前半経路「１０→２０」とを合成した経路「１０→２０→１１」を第２の経路として選択し、その第２の経路「１０→２０→１１」を、記憶部３４の経路スタック３４Ｃヘ格納する（ステップ５０９）。この時点における経路スタック３４Ｃは、図２４の値を取る。
【００５１】
その後、前述したステップ５０３へ戻って、図２４の経路スタック３４Ｃの宛先ノードであるユーザ収容装置１１への経路を参照して、記憶部３４のリンク使用可能性テーブル３４Ｄのうち、第２の経路で用いたリンク１００，１０３を使用不可能に設定する（ステップ５０３）。この時点におけるリンク使用可能性テーブル３４Ｄは、図２６の値を取る。
また、記憶部３４のノード使用可能性テーブル３４Ｅのうち、第２の経路で用いたノードすなわち中継装置２０を使用不可能に設定する（ステップ５０３）。この時点におけるノード使用可能性テーブル３４Ｅは、図２７の値を取る。
【００５２】
そして、経路選択部３２は、記憶部３４のリンク使用可能性テーブル３４Ｄとノード使用可能性テーブル３４Ｅとを参照し、そのうち使用可能なリンクおよびノードから構成されるバックボーンネットワーク２００の新たなトポロジを作成する（ステップ５０４）。
図２８は、ステップ５０４で作成された新たなトポロジを示す説明図である。ここでは、リンク１０２から、送信元ノードであるユーザ収容装置１０と宛先ノードであるユーザ収容装置１１とを接続するバックボーンネットワーク２００の新たなトポロジが作成されている。
【００５３】
次に、経路制御装置３０は、図２８のトポロジにおいて、深さ優先選択を用いて、ユーザ収容装置１１からユーザ収容装置１０までの到達性を確認する（ステップ５０５）。この場合、宛先ノードであるユーザ収容装置１１に接続されているリンクが存在しないため、ユーザ収容装置１０までの到達性はないと判断し（ステップ５０５：ＮＯ）、一連の経路選択処理を終了する。
これにより、記憶部３４の経路スタック３４Ｃには、送信元ノードであるユーザ収容装置１０から宛先ノードであるユーザ収容装置１１までの経路として、第１の経路「１０→２１→１１」と第２の経路「１０→２０→１１」の２つの異なる経路が選択されている。
【００５４】
このように、本実施の形態では、送信元ノードから宛先ノードへの第１の経路を選択後に、当該経路を除くトポロジを作成し、第１の経路とは異なる送信元ノードから宛先ノードへの第２の経路の後半経路として、接続点となる中継ノードと宛先ノードとの経路を選択し、第１の経路の選択処理ですでに得られた送信元ノードから接続点となるノードへの前半経路と上記後半経路とを合成した経路を、第２の経路として選択するようにしたものである。
【００５５】
これにより、第２の経路を選択する際、すでに選択した第１の経路の計算結果を再利用することができ、リンクコストとしてリンクごとに個別のトラヒック量を用いた場合でも計算処理負荷を軽減でき、同一ノード間で複数の経路を迅速に選択できる。
【００５６】
また、第２の経路の前半経路と後半経路とを接続する接続点のノードして、上記トポロジ内のノードのうち最適化パラメータ値が最大のノードを選択するようにしたので、第１の経路と等しい性能の経路、または第１の経路に次ぐ性能の経路を、第２の経路として選択することができ、第１の経路と切り替えて使用される経路として最も相応しい経路を選択できる。
【００５７】
また、第１の経路と異なる経路として選択される第２の経路は、１つに限定されるものではない。例えば、第２の経路以外にも送信元ノードと宛先ノードとを結ぶ経路が存在していれば、図８のステップ５０３〜５０９が繰り返し実行されるため、第２の経路として複数の経路を選択でき、送信元ノードと宛先ノードとを結ぶ経路として３つ以上の異なる経路を選択できる。
【図面の簡単な説明】
【００５８】
なお、以上では、経路選択用アルゴリズムとしてＭＩＮ−ＭＡＸアルゴリズムを用いた場合を例として説明したが、これに限定されるものではなく、経路を評価する最適化パラメータ値を用いて次のノードを順次選択するアルゴリズムであれば、前述と同様にして本発明を適用でき、前述と同様の作用効果が得られる。
【００５９】
また、以上では、ＭＩＮ−ＭＡＸアルゴリズムとして、図６に示したように、任意の経路を構成するリンクのうちリンクコストの最小値を当該経路の最適化パラメータ値とし、各経路のうち最適化パラメータ値が最大となる経路を最適経路として選択する場合について説明したがこれに限定されるものではない。判断基準の大小を逆転させて、任意の経路を構成するリンクのうちリンクコストの最大値を当該経路の最適化パラメータ値とし、各経路のうち最適化パラメータ値が最小となる経路を最適経路として選択するＭＩＮ−ＭＡＸアルゴリズムを用いる場合でも、前述と同様にして本発明を適用でき、前述と同様の作用効果が得られる。この際、最適化パラメータ値は無限大「∞」などの処理上での所定の最大値に初期化される。また、第２の経路の前半経路と後半経路とを接続する接続点となるノードについては、最適化パラメータ値が最小のノードを選択すればよい。
【００６０】
【図１】本発明の一実施の形態にかかる経路制御装置が適用される通信ネットワークの構成例である。
【図２】本発明の一実施の形態にかかる経路制御装置の構成を示すブロック図である。
【図３】リンクコストテーブルの構成例である。
【図４】最適化パラメータテーブルの構成例である。
【図５】経路スタックの構成例である。
【図６】リンク使用可能性テーブルの構成例である。
【図７】ノード使用可能性テーブルの構成例である。
【図８】本発明の一実施の形態にかかる経路制御装置での経路選択処理を示すフローチャートである。
【図９】リンクコストテーブル（初期状態）の構成例である。
【図１０】ＭＩＮ−ＭＡＸアルゴリズムに関する定義および表記を示す説明図である。
【図１１】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（初期状態）である。
【図１２】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（第１の経路の１ステップ目）である。
【図１３】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（第１の経路の２ステップ目）である。
【図１４】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（第１の経路の３ステップ目）である。
【図１５】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（第１の経路の４ステップ目）である。
【図１６】最適化パラメータテーブルの記憶内容例（第１の経路確定時）である。
【図１７】経路スタックの記憶内容例（第１の経路確定時）である。
【図１８】リンク使用可能性テーブルの記憶内容例（第１の経路確定時）である。
【図１９】ノード使用可能性テーブルの記憶内容例（第１の経路確定時）である。
【図２０】トポロジ作成例（第１の経路確定後）である。
【図２１】最適化パラメータテーブルの記憶内容例（第２の経路の初期状態）である。
【図２２】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（第２の経路の初期状態）である。
【図２３】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（第２の経路の１ステップ目）である。
【図２４】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（第２の経路の２ステップ目）である。
【図２５】経路スタックの記憶内容例（第２の経路確定時）である。
【図２６】リンク使用可能性テーブルの記憶内容例（第２の経路確定時）である。
【図２７】ノード使用可能性テーブルの記憶内容例（第２の経路確定時）である。
【図２８】トポロジ作成例（第２の経路確定後）である。
【符号の説明】
【００６１】
１０，１１…ユーザ収容装置（ノード）、２０，２１…中継装置（ノード）、３０…経路制御装置、３１…リンク情報収集部、３２…経路選択部、３３…経路制御部、３４…記憶部、３４Ａ…リンクコストテーブル、３４Ｂ…最適化パラメータテーブル、３４Ｃ…経路スタック、３４Ｄ…リンク使用可能性テーブル、３４Ｅ…ノード使用可能性テーブル、３４Ｆ…ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル、４０，４１…ユーザ端末、１００〜１０４…リンク、２００…バックボーンネットワーク、３００…管理ネットワーク。
【図１】
2006074126.tif 000003
【図２】
2006074126.tif 000004
【図３】
2006074126.tif 000005
【図４】
2006074126.tif 000006
【図５】
2006074126.tif 000007
【図６】
2006074126.tif 000008
【図７】
2006074126.tif 000009
【図８】
2006074126.tif 000010
【図９】
2006074126.tif 000011
【図１０】
2006074126.tif 000012
【図１１】
2006074126.tif 000013
【図１２】
2006074126.tif 000014
【図１３】
2006074126.tif 000015
【図１４】
2006074126.tif 000016
【図１５】
2006074126.tif 000017
【図１６】
2006074126.tif 000018
【図１７】
2006074126.tif 000019
【図１８】
2006074126.tif 000020
【図１９】
2006074126.tif 000021
【図２０】
2006074126.tif 000022
【図２１】
2006074126.tif 000023
【図２２】
2006074126.tif 000024
【図２３】
2006074126.tif 000025
【図２４】
2006074126.tif 000026
【図２５】
2006074126.tif 000027
【図２６】
2006074126.tif 000028
【図２７】
2006074126.tif 000029
【図２８】
2006074126.tif 000030