(57)【特許請求の範囲】
【請求項１】
通信装置からなる複数のノードとこれらノードを結ぶ伝送路からなるリンクとから構成される通信網上で、第１および第２のノード間を結ぶ経路のうち重複しない２つの最適経路を探索する経路探索方法であって、
複数のノードがリンクを介して多角形状に接続されてなるループを、隣接ループと少なくとも２つのノードで接するように前記通信網上に仮想的に定義し、
隣接配置された複数のループからなるループ経路であって、第１のノードが含まれる第１のループと第２のノードが含まれる第２のループとの間を結ぶループ経路のうち、そのループ経路評価値が最も小さいものを最適ループ経路として選択し、
前記最適ループ経路の外周に沿った第１および第２のノード間を結ぶノード経路を重複しない２つの最適経路として選択し、
任意のループ経路に関するループ経路評価値を算出する際、そのループ経路上に位置する各隣接ループごとに、その隣接する２つのループごとの外周リンクの伝送距離の和から前記隣接ループの隣接リンク部分の伝送距離を減算した値をループ間伝送距離として算出し、当該ループ経路を構成する各隣接ループのループ間伝送距離を合計することにより、当該ループ経路に関するループ経路評価値を得ることを特徴とする経路探索方法。
【請求項２】
請求項１記載の経路探索方法において、
任意のループ経路に関するループ経路評価値を算出する際、そのループ経路上に位置する各隣接ループごとに、その隣接する２つのループごとの外周リンクの伝送距離の和から前記隣接ループの隣接リンク部分の伝送距離を減算した値をループ間伝送距離として算出するとともに、その隣接する２つのループの各外周リンクの伝送空き容量から前記隣接ループの隣接リンク部分の伝送空き容量を除いた各伝送空き容量のうちの最小値をループ間伝送空き容量として算出し、これらループ間伝送距離およびループ間伝送空き容量を所定の重みで加算してループ間評価値を算出し、当該ループ経路を構成する各隣接ループのループ間評価値を合計することにより、当該ループ経路に関するループ経路評価値を得ることを特徴とする経路探索方法。
【請求項３】
通信装置からなる複数のノードとこれらノードを結ぶ伝送路からなるリンクとから構成される通信網上で、第１および第２のノード間を結ぶ経路のうち重複しない２つの最適経路を探索する経路探索装置であって、
複数のノードがリンクを介して多角形状に接続されてなるループを、隣接ループと少なくとも２つのノードで接するように前記通信網上に仮想的に定義するループ定義部と、
このループ定義部により配置された隣接する複数のループからなるループ経路であって、第１のノードが含まれる第１のループと第２のノードが含まれる第２のループとの間を結ぶループ経路のうち、そのループ経路評価値が最も小さいものを最適ループ経路として選択する最適ループ経路選択部と、
前記最適ループ経路の外周に沿った第１および第２のノード間を結ぶノード経路を重複しない２つの最適経路として選択する外周経路選択部とを備え、
前記最適ループ経路選択部は、任意のループ経路に関するループ経路評価値を算出する際、そのループ経路上に位置する各隣接ループごとに、その隣接する２つのループごとの外周リンクの伝送距離の和から前記隣接ループの隣接リンク部分の伝送距離を減算した値をループ間伝送距離として算出し、当該ループ経路を構成する各隣接ループのループ間伝送距離を合計することにより、当該ループ経路に関するループ経路評価値を得ることを特徴とする経路探索装置。
【請求項４】
請求項３記載の経路探索装置において、
前記最適ループ経路選択部は、任意のループ経路に関するループ経路評価値を算出する際、そのループ経路上に位置する各隣接ループごとに、その隣接する２つのループごとの外周リンクの伝送距離の和から前記隣接ループの隣接リンク部分の伝送距離を減算した値をループ間伝送距離として算出するとともに、その隣接する２つのループの各外周リンクの伝送空き容量から前記隣接ループの隣接リンク部分の伝送空き容量を除いた各伝送空き容量のうちの最小値をループ間伝送空き容量として算出し、これらループ間伝送距離およびループ間伝送空き容量を所定の重みで加算してループ間評価値を算出し、当該ループ経路を構成する各隣接ループのループ間評価値を合計することにより、当該ループ経路に関するループ経路評価値を得ることを特徴とする経路探索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、経路探索方法および装置に関し、特に２つのノード間を結ぶ経路のうち重複がない２つの最適経路探索する経路探索方法および装置に関するものである。
【０００２】
【従来の技術】
パケット通信などを行うデータ通信網において、データを多量かつ高速で転送する場合、送受信ノード間を結ぶ最適経路を探索する必要がある。
このような２つのノード間または与えられた１つのノードから他のすべてのノードを結ぶすべての経路のうち、その距離が最小となるような経路を求める最短経路問題のアルゴリズムとして、従来、Ｄｉｊｋｓｔｒａ（ダイクストラ）法が提案されている。
【０００３】
図１４，１５は従来の経路探索方法（Ｄｉｊｋｓｔｒａ法）の手順を示す説明図であり、ここでは、ノードＤに設定された開始点Ｓから各ノードまでの最短経路距離を算出する場合について説明する。
まず、Ｓｔｅｐ１では、開始点ＳであるノードＤとの距離を０（ゼロ）とする。そして、ノードＤに隣接するノードＡ，Ｂ，Ｃ，Ｅ，Ｆに、それに接続する辺の重みを距離として与えておく。また、隣接ノード以外の各ノードＧ，Ｈまでの距離はすべて無限大としておく。
【０００４】
次に、Ｓｔｅｐ２およびＳｔｅｐ３では、図１４，１１内で破線表示されている処理済みノード集合に含まれていないノードのうち、開始点Ｓから最も距離の小さいノードＢ，Ｅ（この場合は距離＝２）を処理済みノード集合に含め、そのノードに隣接するノードまでの距離を更新する。
ここではＳｔｅｐ３において、ノードＥに着目した場合、ノードＥを経由したノードＦまでの距離がノードＦへの直接接続する辺の距離より短いため、ノードＦまでの距離が５→３に更新される。同様にして、ノードＧを∞→４，ノードＨを∞→５と更新する。
【０００５】
続いて、Ｓｔｅｐ４〜Ｓｔｅｐ６に示すように、上記のＳｔｅｐ２，３と同様にしてすべてのノードが処理済みノード集合に含まれるまで繰り返す。
このとき、Ｓｔｅｐ４では、ノードＣを処理済みノード集合に含め、ノードＡまでの距離を５→４に更新している。またＳｔｅｐ５では、ノードＦを処理済みノード集合に含め、Ｓｔｅｐ６では、ノードＧを処理済みノード集合に含めている。
Ｄｉｊｋｓｔｒａ法では、このようにして開始点Ｓから各ノードまでの距離を順に更新し、所望のノードまでの最短経路を求めるものとなっていた。
【０００６】
【発明が解決しようとする課題】
しかしながら、このような従来の経路探索方法では、重複のない２つの最適経路を探索する場合、すなわち２つのノード間を接続する二重化された最適経路を探索する場合は、上記のような探索を繰り返し、かつ経路上に重複がないことを確認する処理が伴うため、探索回数が増え処理に時間がかかってしまうという問題点があった。また、ネットワークシステム上での通信に適用して、特定の２点間に複数の回線を設定する場合には、常に同じ経路が探索され、トラヒックに偏りが生じてしまうという問題点があった。
本発明は、このような課題を解決するためのものであり、２つのノード間を接続する二重化された最適経路を短時間で探索でき、またトラヒックに偏りがない経路を探索できる経路探索方法および装置を提供することを目的としている。
【０００７】
【課題を解決するための手段】
このような目的を達成するために、本発明にかかる経路探索方法は、通信装置からなる複数のノードとこれらノードを結ぶ伝送路からなるリンクとから構成される通信網上で、第１および第２のノード間を結ぶ経路のうち重複しない２つの最適経路を探索する経路探索方法であって、複数のノードがリンクを介して多角形状に接続されてなるループを、隣接ループと少なくとも２つのノードで接するように通信網上に仮想的に定義し、隣接配置された複数のループからなるループ経路であって、第１のノードが含まれる第１のループと第２のノードが含まれる第２のループとの間を結ぶループ経路のうち、そのループ経路評価値が最も小さいものを最適ループ経路として選択し、最適ループ経路の外周に沿った第１および第２のノード間を結ぶノード経路を重複しない２つの最適経路として選択し、任意のループ経路に関するループ経路評価値を算出する際、そのループ経路上に位置する各隣接ループごとに、その隣接する２つのループごとの外周リンクの伝送距離の和から隣接ループの隣接リンク部分の伝送距離を減算した値をループ間伝送距離として算出し、当該ループ経路を構成する各隣接ループのループ間伝送距離を合計することにより、当該ループ経路に関するループ経路評価値を得るようにしたものである。
【０００８】
任意のループ経路に関するループ経路評価値を算出する際、そのループ経路上に位置する各隣接ループごとに、その隣接する２つのループごとの外周リンクの伝送距離の和から隣接ループの隣接リンク部分の伝送距離を減算した値をループ間伝送距離として算出するとともに、その隣接する２つのループの各外周リンクの伝送空き容量から隣接ループの隣接リンク部分の伝送空き容量を除いた各伝送空き容量のうちの最小値をループ間伝送空き容量として算出し、これらループ間伝送距離およびループ間伝送空き容量を所定の重みで加算してループ間評価値を算出し、当該ループ経路を構成する各隣接ループのループ間評価値を合計することにより、当該ループ経路に関するループ経路評価値を得るようにしてもよい。
【０００９】
また、本発明にかかる経路探索装置は、通信装置からなる複数のノードとこれらノードを結ぶ伝送路からなるリンクとから構成される通信網上で、第１および第２のノード間を結ぶ経路のうち重複しない２つの最適経路を探索する経路探索装置であって、複数のノードがリンクを介して多角形状に接続されてなるループを、隣接ループと少なくとも２つのノードで接するように通信網上に仮想的に定義するループ定義部と、このループ定義部により配置された隣接する複数のループからなるループ経路であって、第１のノードが含まれる第１のループと第２のノードが含まれる第２のループとの間を結ぶループ経路のうち、そのループ経路評価値が最も小さいものを最適ループ経路として選択する最適ループ経路選択部と、最適ループ経路の外周に沿った第１および第２のノード間を結ぶノード経路を重複しない２つの最適経路として選択する外周経路選択部とを備え、最適ループ経路選択部で、任意のループ経路に関するループ経路評価値を算出する際、そのループ経路上に位置する各隣接ループごとに、その隣接する２つのループごとの外周リンクの伝送距離の和から隣接ループの隣接リンク部分の伝送距離を減算した値をループ間伝送距離として算出し、当該ループ経路を構成する各隣接ループのループ間伝送距離を合計することにより、当該ループ経路に関するループ経路評価値を得るようにしたものである。
【００１０】
最適ループ経路選択部では、任意のループ経路に関するループ経路評価値を算出する際、そのループ経路上に位置する各隣接ループごとに、その隣接する２つのループごとの外周リンクの伝送距離の和から隣接ループの隣接リンク部分の伝送距離を減算した値をループ間伝送距離として算出するとともに、その隣接する２つのループの各外周リンクの伝送空き容量から隣接ループの隣接リンク部分の伝送空き容量を除いた各伝送空き容量のうちの最小値をループ間伝送空き容量として算出し、これらループ間伝送距離およびループ間伝送空き容量を所定の重みで加算してループ間評価値を算出し、当該ループ経路を構成する各隣接ループのループ間評価値を合計することにより、当該ループ経路に関するループ経路評価値を得るようにしてもよい。
【００１１】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
図１は本発明の一実施の形態にかかる経路探索方法が適用される経路探索装置を示すブロック図である。この経路探索装置は、ループ定義部２、最適ループ経路選択部４、および外周経路選択部５から構成されている。なお、これら各部は、コンピュータなどのＣＰＵやメモリなどのハードウェア資源とそのＣＰＵで実行されるプログラムなどのソフトウェア資源とが協動することにより実現されている。
【００１２】
ループ定義部２では、通信網を構成する複数の通信装置すなわちノードとこれら通信装置間を接続する伝送路すなわちリンクとを示す網リンクデータ１に基づき後述するループを仮想的に定義し、定義したループを示すループ定義データ３を出力する。
最適ループ経路選択部４では、ループ定義部２からのループ定義データ３を用いて、隣接配置された複数のループからなるループ経路であって、送受信ノード間を結ぶループ経路のうち、所定のループ経路評価値に基づき最適ループ経路を選択し出力する。
外周経路選択部５では、最適ループ経路選択部４で選択された最適ループ経路に基づき、その最適ループ経路の外周に位置するノード経路を選択し、送受信ノード間を結ぶ最適二重化経路情報１２として出力する。
【００１３】
ここで、本発明で用いるループという概念について説明する。
通信網は、一般的に、複数の通信装置すなわちノードとこれら通信装置間を多角形状に接続する伝送路すなわちリンクの集合体と見なすことができる。本発明では、多角形状に接続されたこれら複数のノードとリンクとをループと仮想的に定義し、通信網がこれらループの集合体であると見なす。すなわち各ループでは、多角形の頂点にノードが配置され、多角形の辺がリンクとなり、ループ内にはノードが存在しない。。
また、これらループは、少なくとも２つのノードとこれらノード間を結ぶリンクとで隣接するループに接しているものとする。
【００１４】
各ループの定義については、例えば任意のノードで任意のリンクを選択し、そのリンクの他端に接続されているノードにおいて、直前に辿ってきたリンクの右または左に隣接するリンクを選択し、このように、右または左に隣接するリンクのみを順に一筆書きで辿ることによりループを定義できる。このようなループの定義を予め実行しておくことにより経路選択処理の所要時間を短縮できる。
【００１５】
次に、図２を参照して、本実施の形態にかかる動作について説明する。図２は経路探索方法の処理手順を示すフローチャートである。以下では、図３に示すような通信網において、データ伝送を行う送信ノードＡと受信ノードＨとの間を接続する二重化された最適経路を探索する場合を例として説明する。
図３に示す通信網は、図４のような網リンクデータ１で表すことができる。この網リンクデータでは、１つのリンクで接続されているノード間すなわち隣接ノード間の距離が示されており、「∞」は隣接されていない状態を示している。
ループ定義部２では、図４に示すような網リンクデータ１を用いて、上記のようなループ定義方法に基づき５つのループａ〜ｅを図３の通信網上に仮想的に定義し、各ループの接続関係を示す図５のようなループ定義データ３を生成する（ステップ２０）。このループ定義データ３には、各ループを構成するノードとリンクの情報が含まれている。
【００１６】
続いて、最適ループ経路選択部４では、送受信ノード情報１１としてノードＡおよびノードＨが設定入力されるとともに（ステップ２１）、ループ定義データ３を読み込む（ステップ２２）。そして、図６に示すように、各ループａ〜ｅを仮想的なノードと見なし、送信ノードＡを含むループａと受信ノードＨを含むループｃとを結ぶループ経路のうち、そのループ経路評価値が最も小さいループ経路を最適ループ経路として選択する（ステップ２３）。
【００１７】
本実施の形態では、ループ間伝送距離βをループ間評価値として用いてループ経路評価値を算出する。ループ間伝送距離βは、２つの隣接ループ間の伝送距離を示す値である。例えば、図６のループ経路４１を構成する２つのループａ，ｂ間のループ間伝送距離βａｂは、図７に示すように、ループａを構成する各リンクの伝送距離Ｌａ（１）〜Ｌａ（４）の和と、ループｂを構成する各リンクの伝送距離Ｌｂ（１）〜Ｌｂ（５）の和とを加算し、ここからループａ，ｂが接するリンクの伝送距離Ｌａ（２）およびＬｂ（５）を減算することにより求められ、これは隣接ループａ，ｂの外周リンク（図７中の太線部分）の伝送距離の和を表している。上記のようにして求められた各ループ間伝送距離βの算出結果例を図８に示す。ここでは、「∞」は隣接していない状態を示している。なお、各ループ間伝送距離βについては、通信網の構成が変更されない限り固定的な値であることから、ループ定義データと同様にして予め求めておいたものを用いてもよく、最適ループ経路選択処理の所要時間を短縮できる。
【００１８】
最適ループ経路選択部４では、当該ループ経路を構成する各隣接ループのループ間伝送距離を合計することにより、当該ループ経路に関するループ経路評価値を得る。そして、送受信ノードを含む２つのループ間を結ぶ各ループ経路のうち、そのループ経路評価値が最も小さいループ経路を最適ループ経路として選択する。
このようにして、最適ループ経路選択部４で、送受信ノードＡ，Ｈが存在する送受信ループａ，ｃ間を結ぶ最適ループ経路として、ループａ→ｂ→ｃが選択される。
【００１９】
次に、外周経路選択部５では、最適ループ経路選択部４で選択された最適ループ経路ａ→ｂ→ｃに基づいて、それぞれのループ定義データ３を参照することにより、最適ループ経路の外周に沿って送受信ノードＡ，Ｈを結ぶノード経路を選択する。ここでは、図９に示すように、ノードＡ→Ｂ→Ｅ→Ｈからなるノード経路６１と、ノードＡ→Ｄ→Ｃ→Ｇ→Ｆ→Ｉ→Ｈからなるノード経路６２とが選択される。そして、これら２つのノード経路が送受信ノードＡ，Ｈを結ぶ最短二重化経路情報１２として出力される。
【００２０】
このように、通信網にループを定義し、送受信ノードを含む送受信ループ間を結ぶ最適ループ経路をループ間伝送距離βを用いたループ経路評価値により選択し、その最適ループ経路の外周に沿った送受信ノードＡ，Ｈを結ぶノード経路を最短二重化経路として選択するようにしたので、従来のように、送受信ノードを結ぶ最短経路を繰り返し探索する必要がなく、探索回数が１回で済とともに、ノード間のノード経路でなく複数のノードからなるループ間のループ経路を探索するため、探索処理が大幅に短縮できる。これに対して、従来の方法によれば、図１０に示すように、まず最短経路としてノードＡ→Ｂ→Ｅ→Ｈを探索した後、この経路を通らないで次に短い経路としてノードＡ→Ｄ→Ｃ→Ｇ→Ｆ→Ｉ→Ｈを探索することになり、送受信ノードを結ぶ最短経路を繰り返し探索する必要があった。
また、本実施の形態によれば、最適ループ経路の外周経路を選択するため、探索された最適経路に重複がないことを確認する必要がなくなり、結果として２つのノード間を接続する二重化された最短経路をきわめて短い時間で探索できる。
【００２１】
次に、本発明の第２の実施の形態について説明する。
上記した第１の実施の形態では、最適ループ経路を選択するループ経路評価値として、ループ間伝送距離を用いて算出する場合を例として説明したが、本実施の形態では、このループ経路評価値として、ループ間伝送距離だけでなくループ間伝送空き容量も考慮する場合について説明する。
本実施の形態にかかる経路探索装置の構成は、図１と同様であるが、最適ループ経路選択部４では、図１３に示すように、ループ間伝送距離とループ間伝送空き容量とをパラメータとする評価関数ｆを用いて、各ループ経路を構成する隣接ループ間ごとにループ間評価値を算出し、これらループ間評価値の和すなわちループ経路評価値が最も小さいループ経路を最適ループ経路として選択する。
【００２２】
この評価関数ｆは、ループ間伝送距離βとループ間伝送空き容量γとを所定の割合αで合成したものである。ループ間伝送距離βは、第１の実施の形態で用いたものと同一である。また、ループ間伝送空き容量γについては、ループａ，ｂの外周リンクの伝送空き容量のうち、最も小さい値を表している。なお、各リンクの伝送空き容量は、そのリンク端の当該ノードからそれぞれ収集すればよい。
例えば、図６のループ経路４１を構成する２つのループａ，ｂ間のループ間伝送空き容量γａｂは、図１１に示すように、ループａを構成する各リンクの伝送空き容量Ｗａ（１）〜Ｗａ（４）と、ループｂを構成する各リンクの伝送空き容量Ｗｂ（１）〜Ｗｂ（５）とから、ループａ，ｂが接するリンクの伝送空き容量Ｗａ（２）およびＷｂ（５）を除いた各伝送空き容量のうち、その最小値が選択される。なお、関数Ｍｉｎ（Ｘ）は、集合Ｘの各要素から最小値を選択する関数を示す。
【００２３】
βmaxは、算出対象となるループ経路から算出された複数のループ間伝送距離βのうち、最も大きな値をとるものを示し、同じくγmaxは、算出対象となるループ経路から算出された複数のループ間伝送空き容量γのうち、最も大きな値をとるものを示している。図１３の評価関数ｆの式では、伝送距離および伝送空き容量に対して重みα，α−１を正確に与えるため、βmaxやγmaxでβおよびγを除算して伝送距離および伝送空き容量を正規化している。
図１２に、上記のようにして求められた各ループ間伝送空き容量γの算出結果例を示す。ここでは、上記のγmaxを「１０」と見なし、これに対する各リンクの伝送空き容量が「０」〜「１０」の値で表されている。なお、「０」は隣接していないループ間にも使用されている。
【００２４】
このように、伝送距離だけでなく伝送空き容量も考慮した評価関数値をループ間評価値として各隣接ループ間ごとに算出するとともに、各ループ経路に含まれる隣接ループのループ間評価値の和をループ経路評価値として算出し、各ループ経路のうち、そのループ経路評価値が最も小さいループ経路を最適ループ経路として選択するようにしたので、経路探索時点における伝送空き容量が考慮されるため、経路距離だけを用いて経路探索を行う場合と比較して、送受信ノードが同一であっても常に同じ経路が選択されなくなり、トラフィックに偏りのない経路探索を実現できるとともに、通信網上で輻輳や障害が発生した場合でも、その場所を回避した最適な二重化経路を選択できる。
【００２５】
【発明の効果】
以上説明したように、本発明は、通信網にループを定義し、送受信ノードを含む送受信ループ間を結ぶ最適ループ経路を、ループ間伝送距離βさらにはループ間伝送空き容量を用いたループ経路評価値により選択し、その最適ループ経路の外周に沿った送受信ノードを結ぶノード経路を最短二重化経路として選択するようにしたので、従来のように、送受信ノードを結ぶ最短経路を繰り返し探索する必要がなく、探索回数が１回で済とともに、ノード間のノード経路でなく複数のノードからなるループ間のループ経路を探索するため、探索処理が大幅に短縮できる。また、送受信ノードが同一であっても常に同じ経路が選択されなくなり、トラフィックに偏りのない経路探索を実現できる。
【図面の簡単な説明】
【図１】  本発明の一実施の形態による経路選択装置を示すブロック図である。
【図２】  経路選択方法の処理手順を示すフローチャートである。
【図３】  ループが配置された通信網の一例である。
【図４】  網リンクデータの構成例である。
【図５】  ループ定義データの構成例である。
【図６】  ループ経路の選択例である。
【図７】  ループ間伝送距離βを用いたループ経路評価値の算出例である。
【図８】  ループ間伝送距離の算出例である。
【図９】  最適二重化経路の選択例である。
【図１０】  従来の経路選択方法による最適二重化経路の選択例である。
【図１１】  ループ間伝送距離βおよびループ間伝送空き容量γを用いたループ経路評価値の算出例である。
【図１２】  ループ間空き容量の算出例である。
【図１３】  評価関数の算出例である。
【図１４】  従来の経路選択方法を示す説明図である。
【図１５】  従来の経路選択方法を示す説明図である。
【符号の説明】
１…網リンクデータ、２…ループ定義部、３…ループ定義データ、４…最適ループ経路選択部、５…外周経路選択部、１１…送受信ノード情報、１２…最適二重化経路情報。
【図１】
0004408000.tif 000002
【図２】
0004408000.tif 000003
【図３】
0004408000.tif 000004
【図４】
0004408000.tif 000005
【図５】
0004408000.tif 000006
【図６】
0004408000.tif 000007
【図７】
0004408000.tif 000008
【図８】
0004408000.tif 000009
【図９】
0004408000.tif 000010
【図１０】
0004408000.tif 000011
【図１１】
0004408000.tif 000012
【図１２】
0004408000.tif 000013
【図１３】
0004408000.tif 000014
【図１４】
0004408000.tif 000015
【図１５】
0004408000.tif 000016