(57)【特許請求の範囲】
【請求項１】
設計対象となるネットワークトポロジーにおいて探索したい経路の始発ノード及び終着ノードの先に仮想ノードを設置する手段と、前記ネットワークトポロジーに対してリンクをノードとするトポロジーへの変換を行う手段と、この新しいトポロジーに対して経路設計処理を実行する手段と、その経路設計処理で得られた経路を元のトポロジー上の経路に戻す手段とを有し、
前記ネットワークトポロジーを変換してノードやリンクの少なくともネットワークの使用に伴うコストを示すメトリックのみならず、隣接する２つのリンクから規定されたコストを示す隣接メトリックを用いた通信経路の設計を可能としたことを特徴とする通信路設計装置。
【請求項２】
設計対象となるネットワークトポロジーにおいて探索したい経路の始発ノード及び終着ノードの先に仮想ノードを設置する手段と、前記ネットワークトポロジーに対してリンクをノードとするトポロジーへの変換を行う手段と、この新しいトポロジーに対して経路設計処理を実行する手段と、その経路設計処理で得られた経路を元のトポロジー上の経路に戻す手段とを有することを特徴とする通信路設計装置。
【請求項３】
前記仮想ノードを設置する手段は、前記トポロジーに変換する手段によるトポロジー変換処理を行うための準備として前記仮想ノードを設置するようにしたことを特徴とする請求項２記載の通信路設計装置。
【請求項４】
前記トポロジーに変換する手段は、前記新しいトポロジーにおけるリンクを元のトポロジーのリンクの隣接関係を表すようにしたことを特徴とする請求項２または請求項３記載の通信路設計装置。
【請求項５】
前記経路設計処理を実行する手段は、前記新しいトポロジーにおけるリンクの少なくともネットワークの使用に伴うコストを示すメトリックであり、隣接する２つのリンクから規定されかつ少なくともネットワークの使用に伴うコストを示す隣接リンクメトリックを基に経路設計処理を行うようにしたことを特徴とする請求項２から請求項４のいずれか記載の通信路設計装置。
【請求項６】
設計対象となるネットワークトポロジーにおいて探索したい経路の始発ノード及び終着ノードの先に仮想ノードを設置するステップと、前記ネットワークトポロジーに対してリンクをノードとするトポロジーへの変換を行うステップと、この新しいトポロジーに対して経路設計処理を実行するステップと、その経路設計処理で得られた経路を元のトポロジー上の経路に戻すステップとを有し、
前記ネットワークトポロジーを変換してノードやリンクの少なくともネットワークの使用に伴うコストを示すメトリックのみならず、隣接する２つのリンクから規定されたコストを示す隣接メトリックを用いた通信経路の設計を可能としたことを特徴とする通信路設計方法。
【請求項７】
設計対象となるネットワークトポロジーにおいて探索したい経路の始発ノード及び終着ノードの先に仮想ノードを設置するステップと、前記ネットワークトポロジーに対してリンクをノードとするトポロジーへの変換を行うステップと、この新しいトポロジーに対して経路設計処理を実行するステップと、その経路設計処理で得られた経路を元のトポロジー上の経路に戻すステップとを有することを特徴とする通信路設計方法。
【請求項８】
前記仮想ノードを設置するステップは、前記トポロジーに変換するステップによるトポロジー変換処理を行うための準備として前記仮想ノードを設置するようにしたことを特徴とする請求項７記載の通信路設計方法。
【請求項９】
前記トポロジーに変換するステップは、前記新しいトポロジーにおけるリンクを元のトポロジーのリンクの隣接関係を表すようにしたことを特徴とする請求項７または請求項８記載の通信路設計方法。
【請求項１０】
前記経路設計処理を実行するステップは、前記新しいトポロジーにおけるリンクの少なくともネットワークの使用に伴うコストを示すメトリックであり、隣接する２つのリンクから規定されかつ少なくともネットワークの使用に伴うコストを示す隣接リンクメトリックを基に経路設計処理を行うようにしたことを特徴とする請求項７から請求項９のいずれか記載の通信路設計方法。
【請求項１１】
コンピュータに、設計対象となるネットワークトポロジーにおいて探索したい経路の始発ノード及び終着ノードの先に仮想ノードを設置する処理と、前記ネットワークトポロジーに対してリンクをノードとするトポロジーへの変換を行う処理と、この新しいトポロジーに対して経路設計処理を実行する処理と、その経路設計処理で得られた経路を元のトポロジー上の経路に戻す処理とを実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は通信路設計装置及びそれに用いる通信路設計方法並びにそのプログラムに関し、特に隣接するリンクメトリックを用いた通信路設計方法に関する。
【０００２】
【従来の技術】
従来、通信路設計方法においては、隣接するリンクに付与されるメトリック（Ｍｅｔｒｉｃｓ）［ここでは、ネットワークの使用に伴う価格（コスト）等のパスやルートを選択する際の基準を示す］を用いて設計をしなければならない状況がある。例えば、ルータ（またはスイッチ）は、図６に示すように、入側インタフェース（Ｉ／Ｆ）１０１〜１０３と、キュー１１１〜１１３と、スイッチ１２０と、出側インタフェース（Ｉ／Ｆ）１３１〜１３３とから構成されている。
【０００３】
この構成において、パケットは入側インターフェース１０１〜１０３から入り、出側インターフェース１３１〜１３３に対応したキュー１１１〜１１３に入る。キュー１１１〜１１３ではスイッチ１２０の混雑状況に応じて待たされた後、スイッチ１２０を通り、出側インタフェース１３１〜１３３から出て行く。
【０００４】
パケットがどのキュー１１１〜１１３に入るかは入側インタフェース１０１〜１０３と出側インタフェース１３１〜１３３とから特定される。各インタフェースはそれぞれこのルータ１００につながっているリンクに対応する。言い換えると、キュー１１１〜１１３はパケットが通っていく隣接した２つのリンクによって特定される。
【０００５】
例えば、遅延が短くなる経路を探索する場合、キュー１１１〜１１３において待たされる時間を考慮する必要がある。こういった場合には、パケットが通っていく隣接した２つのリンクのメトリックを考慮する必要がある。
【０００６】
パスの代表的な作成方法としては、Ｄｉｊｋｓｔｒａ法（最適化ハンドブック、伊理正夫、今野浩、刀根薫監訳、１９９５、朝倉書店）（以下、参考文献１とする）がある。このＤｉｊｋｓｔｒａ法は、ある入口ノードから出口ノードまでの最小メトリック値の経路を発見する方法である。このとき、メトリックはリンク毎に与えられる。
【０００７】
このＤｉｊｋｓｔｒａ法では、始点ノードからはじめて、始点からメトリックの合計が最小となる隣接ノードへの移動を繰り返しながら、最小メトリック経路を作成している。
【０００８】
図７を用いてその最小メトリック経路の作成例について説明する。尚、Ｄｉｊｋｓｔｒａ法の基本は始点から他の終点までの経路を一連の探索で見つける方法であるが、ここではターゲットとなるひとつの終点まで経路が探索できればよいものと限定して説明する。
【０００９】
まず、ノードＮ１からノードＮ５までの経路を探索するとする。ノードＮ１に隣接するノードＮ２，Ｎ３，Ｎ４のうちリンクのメトリックが最も小さいリンクはリンクＬ２であるので、ノードＮ３へ移動する。続いて、まだ到達していないノードＮ２，Ｎ４，Ｎ５のうち、もっともメトリックの合計が小さいリンクはリンクＬ６になるので、ノードＮ２に移動する。
【００１０】
また、まだ到達していないノードＮ４，Ｎ５のうち、もっともメトリックの合計が小さいのはノードＮ５であるので、ノードＮ５に移動する。この結果、リンクメトリックを最小にする経路Ｎ１→Ｎ３→Ｎ２→Ｎ５が探索される。
【００１１】
【発明が解決しようとする課題】
上述した従来の通信路設計方法では、パスの代表的な作成方法として、Ｄｉｊｋｓｔｒａ法が用いられているが、このＤｉｊｋｓｔｒａ法はリンクメトリックを用いて、次に移動するノードを決定するプロセスを繰り返す方法ということができる。このことから、上述したように、隣接する２つのリンクによって規定されるメトリックを使う場合には、このＤｉｊｋｓｔｒａ法を適用することができないという問題がある。
【００１２】
そこで、本発明の目的は上記の問題点を解消し、隣接する２つのリンクから規定されるメトリックを用いた通信経路を設計することができる通信路設計装置及びそれに用いる通信路設計方法並びにそのプログラムを提供することにある。
【００１３】
【課題を解決するための手段】
本発明による通信路設計装置は、設計対象となるネットワークトポロジーにおいて探索したい経路の始発ノード及び終着ノードの先に仮想ノードを設置する手段と、前記ネットワークトポロジーに対してリンクをノードとするトポロジーへの変換を行う手段と、この新しいトポロジーに対して経路設計処理を実行する手段と、その経路設計処理で得られた経路を元のトポロジー上の経路に戻す手段とを備え、
前記ネットワークトポロジーを変換してノードやリンクの少なくともネットワークの使用に伴うコストを示すメトリックのみならず、隣接する２つのリンクから規定されたコストを示す隣接メトリックを用いた通信経路の設計を可能としている。
【００１４】
本発明による他の通信路設計装置は、設計対象となるネットワークトポロジーにおいて探索したい経路の始発ノード及び終着ノードの先に仮想ノードを設置する手段と、前記ネットワークトポロジーに対してリンクをノードとするトポロジーへの変換を行う手段と、この新しいトポロジーに対して経路設計処理を実行する手段と、その経路設計処理で得られた経路を元のトポロジー上の経路に戻す手段とを備えている。
【００１５】
本発明による通信路設計方法は、設計対象となるネットワークトポロジーにおいて探索したい経路の始発ノード及び終着ノードの先に仮想ノードを設置するステップと、前記ネットワークトポロジーに対してリンクをノードとするトポロジーへの変換を行うステップと、この新しいトポロジーに対して経路設計処理を実行するステップと、その経路設計処理で得られた経路を元のトポロジー上の経路に戻すステップとを備え、
前記ネットワークトポロジーを変換してノードやリンクの少なくともネットワークの使用に伴うコストを示すメトリックのみならず、隣接する２つのリンクから規定されたコストを示す隣接メトリックを用いた通信経路の設計を可能としている。
【００１６】
本発明による他の通信路設計方法は、設計対象となるネットワークトポロジーにおいて探索したい経路の始発ノード及び終着ノードの先に仮想ノードを設置するステップと、前記ネットワークトポロジーに対してリンクをノードとするトポロジーへの変換を行うステップと、この新しいトポロジーに対して経路設計処理を実行するステップと、その経路設計処理で得られた経路を元のトポロジー上の経路に戻すステップとを備えている。
【００１７】
本発明による通信路設計方法のプログラムは、コンピュータに、設計対象となるネットワークトポロジーにおいて探索したい経路の始発ノード及び終着ノードの先に仮想ノードを設置する処理と、前記ネットワークトポロジーに対してリンクをノードとするトポロジーへの変換を行う処理と、この新しいトポロジーに対して経路設計処理を実行する処理と、その経路設計処理で得られた経路を元のトポロジー上の経路に戻す処理とを実行させている。
【００１８】
すなわち、本発明の通信路設計方法は、ノードやリンクのメトリック（Ｍｅｔｒｉｃｓ）［ここでは、ネットワークの使用に伴う価格（コスト）等のパスやルートを選択する際の基準を示す］のみならず、隣接する２つのリンクから規定されるメトリックを用いた通信経路の設計を可能とすることを特徴とする。これは、例えば入力側にキューがあるようなルータにおいて、キューの遅延を考慮した設計を行う場合に必要になる。尚、この「隣接する２つのリンクから規定されるメトリック」を、以下、「隣接リンクメトリック」とする。本発明の通信路設計方法では、この隣接リンクメトリックを用いた設計を行うために、トポロジー変換を行うことを特徴としている。
【００１９】
より具体的に説明すると、本発明の通信路設計方法では、まず設計対象となるネットワークトポロジーにおいて、探索したい経路の始発ノード、終着ノードの先に仮想ノードを設置する処理を行う。この処理は続くトポロジー変換処理を行うための準備である。
【００２０】
トポロジー変換処理では、現在のトポロジーを、リンクをノードとするトポロジーに変換する。この場合、新しいトポロジーにおけるリンクは元のトポロジーのリンクの隣接関係を表す。
【００２１】
続いて、この新しいトポロジーに対して経路設計処理を実行する。「隣接リンクメトリック」は新しいトポロジーにおけるリンクメトリックと表されているので、この経路設計処理には従来の各種の経路設計アルゴリズムを適用することが可能となる。
【００２２】
最後に、経路設計処理で得られた経路を元のトポロジー上の経路に戻すと、求めようとしていた経路が得られる。これによって、ノードやリンクのメトリックのみならず、隣接する２つのリンクから規定されるメトリックを用いた通信経路の設計を行うことが可能となる。
【００２３】
【発明の実施の形態】
次に、本発明の一実施例について図面を参照して説明する。図１は本発明の一実施例による通信路設計装置の構成を示すブロック図である。図１において、通信路設計装置１は仮想ノード配置手段１１と、トポロジー変換手段１２と、経路設計手段１３と、経路復元手段１４と、記録媒体１５とから構成されている。尚、通信路設計装置１の各手段はコンピュータが記録媒体１５に格納されたプログラムを実行することで実現される。
【００２４】
図２は本発明の一実施例による通信路設計装置の動作を示すフローチャートである。これら図１及び図２を参照して本発明の一実施例による通信路設計装置１の動作について説明する。尚、図２に示す処理はコンピュータが記録媒体１５に格納されたプログラムを実行することで実現される。
【００２５】
仮想ノード配置手段１１は設計対象となるネットワークトポロジーにおいて、探索したい経路の始発ノード、終着ノードの先に仮想ノードを設置する（図２ステップＳ１）。この仮想ノード配置手段１１による処理は続くトポロジー変換処理を行うための準備である。
【００２６】
トポロジー変換手段１２は現在のトポロジーを、リンクをノードとするトポロジーに変換する（図２ステップＳ２）。この場合、新しいトポロジーにおけるリンクは元のトポロジーのリンクの隣接関係を表す。
【００２７】
経路設計手段１３はこの新しいトポロジーに対して経路設計処理を実行する（図２ステップＳ３）。「隣接リンクメトリック」は新しいトポロジーにおけるリンクメトリックと表されているので、この経路設計処理には従来の各種の経路設計アルゴリズムを適用することが可能となる。ここで、メトリック（Ｍｅｔｒｉｃｓ）とは、ネットワークの使用に伴う価格（コスト）等のパスやルートを選択する際の基準を示している。
【００２８】
経路復元手段１４は経路設計処理で得られた経路を元のトポロジー上の経路に戻す（図２ステップＳ４）。この経路復元手段１４による処理によって、求めようとしていた経路が得られる。
【００２９】
図３は本発明の一実施例に適用するネットワーク例を示す図である。図３において、ネットワークトポロジーはノード（丸で表現）Ｎ１〜Ｎ５とリンク（矢印つきの線分）Ｌ０〜Ｌ１１とから構成されている。
【００３０】
ノードＮ１〜Ｎ５から破線で引き出された箱の中には、そのノードＮ１〜Ｎ５を介して接続される隣接リンクメトリックを記載している。すなわち、ノードＮ１には｛［Ｌ０，Ｌ１］（４），［Ｌ０，Ｌ２］（１），［Ｌ０，Ｌ３］（２）｝が記載され、ノードＮ２には｛［Ｌ１，Ｌ４］（２），［Ｌ１，Ｌ５］（３），［Ｌ６，Ｌ５］（３）｝が記載され、ノードＮ３には｛［Ｌ２，Ｌ６］（４），［Ｌ２，Ｌ７］（１），［Ｌ２，Ｌ８］（２），［Ｌ９，Ｌ６］（２），［Ｌ９，Ｌ８］（３），［Ｌ４，Ｌ７］（２），［Ｌ４，Ｌ８］（２）｝が記載され、ノードＮ４には｛［Ｌ３，Ｌ９］（２），［Ｌ３，Ｌ１０］（１），［Ｌ７，Ｌ１０］（１）｝が記載され、ノードＮ５には｛［Ｌ５，Ｌ１１］（４），［Ｌ８，Ｌ１１］（１），［Ｌ１０，Ｌ１１］（２）｝が記載されている。
【００３１】
ここで、例えば［Ｌ２，Ｌ６］（４）はリンクＬ２からリンクＬ６へと流れるトラフィックに関する隣接リンクメトリックが（４）であることを示している。尚、ループとなる部分（例えば、リンクＬ４とリンクＬ６とによるループ、リンクＬ７とリンクＬ９とによるループ）は使わないとしてメトリックから省いている。
【００３２】
図４及び図５は本発明の一実施例による通信路設計装置１の処理を説明するための図である。これら図１〜図５を参照して本発明の一実施例による通信路設計装置の処理について説明する。以下の説明では、始発ノードをノードＮ１、終着ノードをノードＮ５として、このノードＮ１とノードＮ５との間の経路を設計する処理について述べる。
【００３３】
まず、仮想ノード設置手段１１は設計対象となるネットワークトポロジーにおいて、探索したい経路の始発ノードＮ１、終着ノードＮ５の先に仮想ノードＮ０，Ｎ６を設置する（図２ステップＳ１）。この時、始発ノードＮ１、終着ノードＮ５に接続されているアクセスリンクの情報が明らかになっている場合には、アクセスリンク毎に仮想ノードを設置する。
【００３４】
図３に示す例では始発ノードＮ１及び終着ノードＮ５にはそれぞれ一本のアクセスリンクがつながっており、それぞれ仮想ノードを１つずつ設置する。その仮想ノードを設置した結果が図４であり、図４において、斜線で表したノードＮ０及びノードＮ６が仮想ノードである。この場合、ノードＮ０を仮想始発ノード、ノードＮ６を仮想終着ノードと呼ぶこともある。
【００３５】
この例では１つの始発ノードから１つの終着ノードの経路を探索する例であるが、複数の始発ノード、複数の終着ノード等の場合には、複数の仮想ノードを設置しても良い。アクセスリンクに関する情報がない場合には始発ノード側、終着ノード側それぞれに仮想ノードをひとつ設置する。
【００３６】
この結果、図４に示すように、ノードＮ１〜Ｎ５を介して接続される隣接リンクメトリックは、ノードＮ１〜Ｎ５から破線で引き出された箱の中に記載される。
【００３７】
続いて、トポロジーの変換手段１２はトポロジーの変換を行う（図２ステップＳ２）。この変換ではリンクが新しいトポロジーでのノードとなり、リンクの隣接関係があたらしトポロジーでのリンクとなる。
【００３８】
図４に示すトポロジーを変換した結果が図５である。変換前のトポロジー（図４）では、リンクＬ０〜Ｌ１１までのリンクがあるが、これが変換後のトポロジー（図５）では、ノードになっている。また、変換後のトポロジー（図５）のリンクはリンクの隣接関係を表しているので、変換前のトポロジー（図４）の隣接リンクメトリックの数だけのリンクがある。
【００３９】
例えば、リンクＬ０の例でリンクを作成する過程を説明する。図４において、リンクＬ０はノードＮ１を隔ててリンクＬ１，Ｌ２，Ｌ３の３つのリンクに隣接している。そこで、新しいトポロジー（図５）において、リンクＬ０に対してはリンクＬ１，Ｌ２，Ｌ３との間にリンク［Ｌ０，Ｌ１］（４），［Ｌ０，Ｌ２］（１），［Ｌ０，Ｌ３］（２）が設置される。
【００４０】
同様に、リンクＬ１に対してはリンクＬ４，Ｌ５との間にリンク［Ｌ１，Ｌ４］（２），［Ｌ１，Ｌ５］（３）が設置され、リンクＬ２に対してはリンクＬ６，Ｌ７，Ｌ８との間にリンク［Ｌ２，Ｌ６］（４），［Ｌ２，Ｌ７］（１），［Ｌ２，Ｌ８］（２）が設置される。
【００４１】
リンクＬ３に対してはリンクＬ９，Ｌ１０との間にリンク［Ｌ３，Ｌ９］（２），［Ｌ３，Ｌ１０］（１）が設置され、リンクＬ４に対してはリンクＬ７，Ｌ８との間にリンク［Ｌ４，Ｌ７］（２），［Ｌ４，Ｌ８］（２）が設置される。リンクＬ５に対してはリンクＬ１１との間にリンク［Ｌ５，Ｌ１１］（４）が設置され、リンクＬ６に対してはリンクＬ５との間にリンク［Ｌ６，Ｌ５］（３）が設置される。
【００４２】
リンクＬ７に対してはリンクＬ１０との間にリンク［Ｌ７，Ｌ１０］（２）が設置され、リンクＬ８に対してはリンクＬ１１との間にリンク［Ｌ８，Ｌ１１］（１）が設置される。リンクＬ９に対してはリンクＬ６，Ｌ８との間にリンク［Ｌ９，Ｌ６］（２），［Ｌ９，Ｌ８］（３）が設置され、リンクＬ１０に対してはリンクＬ１１との間にリンク［Ｌ１０，Ｌ１１］（２）が設置される。
【００４３】
上記のようにしてトポロジー変換を行う。尚、ループになる部分（例えば、リンクＬ７及びリンクＬ９）に関しては新しいトポロジーにおいてリンクを作成していない。これは、一般に、経路を設計する時にループを避けるためである。本実施例ではループを除くことに限定されず、必要に応じて、ループ部分のリンクを作成してもよい。
【００４４】
次に、経路設計手段１３は変換後のトポロジー（図５）を用いて経路を設計する（図２ステップＳ３）。これは既存の任意の経路設計のアルゴリズムを使用してよい。例えば、隣接リンクメトリック最小となるように経路を一本作成する場合にはＤｉｊｋｓｔｒａ法（上記の参考文献１）の方法を適用することができる。
【００４５】
また、迂回経路を合わせて作成する場合には、経路ペアの作成が可能なネットワーク構成であれば、確実に経路ペアを作成可能な経路ペア設計方法を用いればよい。この経路ペア設計方法としては、様々な方法が提案されており、特にその方法について限定されるものではない。
【００４６】
ここでは、隣接リンクメトリックが最小となる経路を一本作成するとすると、Ｄｉｊｋｓｔｒａ法を適用した結果、リンクＬ０→リンクＬ２→リンクＬ８→リンクＬ１１という経路が作成される。
【００４７】
上記のステップＳ３で得られた結果は、変換後のトポロジー上の経路であるので、経路復元手段１４でその設計された経路を元のトポロジー上の経路に戻す（図２ステップＳ４）。リンクＬ０→リンクＬ２→リンクＬ８→リンクＬ１１という経路を元のトポロジー上の経路に直すと、ノードＮ１→（リンクＬ２）→ノードＮ３→（リンクＬ８）→ノードＮ５という経路になる。
【００４８】
このように、元のトポロジー上の経路に直し、経路設計を終了することで、ノードやリンクのメトリックのみならず、隣接する２つのリンクから規定されるメトリックを用いた通信経路を設計することができる。
【００４９】
【発明の効果】
以上説明したように本発明は、設計対象となるネットワークトポロジーにおいて探索したい経路の始発ノード及び終着ノードの先に仮想ノードを設置し、このネットワークトポロジーに対してリンクをノードとするトポロジーへの変換を行い、その新しいトポロジーに対して経路設計処理を実行し、この経路設計処理で得られた経路を元のトポロジー上の経路に戻すことによって、隣接する２つのリンクから規定されるメトリックを用いた通信経路を設計することができるという効果が得られる。
【図面の簡単な説明】
【図１】本発明の一実施例による通信路設計装置の構成を示すブロック図である。
【図２】本発明の一実施例による通信路設計装置の動作を示すフローチャートである。
【図３】本発明の一実施例に適用するネットワーク例を示す図である。
【図４】本発明の一実施例による通信路設計装置１の処理を説明するための図である。
【図５】本発明の一実施例による通信路設計装置１の処理を説明するための図である。
【図６】従来のルータ（スイッチ）の構成を示すブロック図である。
【図７】従来のネットワーク例を示す図である。
【符号の説明】
１  通信路設計装置
１１  仮想ノード配置手段
１２  トポロジー変換手段
１３  経路設計手段
１４  経路復元手段
１５  記録媒体
Ｎ０，Ｎ６  仮想ノード
Ｎ１〜Ｎ５  ノード
Ｌ０〜Ｌ１１  リンク
【図１】
0003651437.tif 000002
【図２】
0003651437.tif 000003
【図３】
0003651437.tif 000004
【図４】
0003651437.tif 000005
【図５】
0003651437.tif 000006
【図６】
0003651437.tif 000007
【図７】
0003651437.tif 000008