(57)【特許請求の範囲】
【請求項１】
ネットワーク上の一の送信元側端点と、複数の送信先側端点間の経路設計を行う通信経路の設計回路であって、
選択された複数の送信先側端点のそれぞれに接続される一の送信先側仮想ノードと、この仮想ノードと前記送信先側端点を接続する複数の仮想リンクを作成する仮想ノード・仮想リンク作成手段と、
前記送信元側端点及び前記送信先側仮想ノード間の経路の設計を行う一送信元対一送信先間経路設計手段と、
前記仮想ノード及び前記仮想リンクを、設計された前記経路から削除する仮想ノード・仮想リンク削除手段とを有する
ことを特徴とする通信経路の設計回路。
【請求項２】
ネットワーク上の複数の送信元側端点と、一の送信先側端点間の経路設計を行う通信経路の設計回路であって、
選択された複数の送信元側端点のそれぞれに接続される一の送信元側仮想ノードと、この仮想ノードと前記送信元側端点を接続する複数の仮想リンクを作成する仮想ノード・仮想リンク作成手段と、
前記送信元側仮想ノード及び前記送信先側端点間の経路の設計を行う一送信元対一送信先間経路設計手段と、
前記仮想ノード及び前記仮想リンクを、設計された前記経路から削除する仮想ノード・仮想リンク削除手段とを有する
ことを特徴とする通信経路の設計回路。
【請求項３】
ネットワーク上の複数の送信元側端点と、複数の送信先側端点間の経路設計を行う通信経路の設計回路であって、
選択された複数の送信元側端点のそれぞれに接続される一の送信元側仮想ノードと、選択された複数の送信先側端点のそれぞれに接続される一の送信先側仮想ノードと、これらの仮想ノードとそれぞれの前記端点を接続する複数の仮想リンクを作成する仮想ノード・仮想リンク作成手段と、
前記送信元側仮想ノード及び前記送信先側仮想ノード間の経路の設計を行う一送信元対一送信先間経路設計手段と、
前記仮想ノード及び前記仮想リンクを、設計された前記経路から削除する仮想ノード・仮想リンク削除手段とを有する
ことを特徴とする通信経路の設計回路。
【請求項４】
複数のネットワーク間の経路設計を行うにあたって、
前記ネットワーク内において、送信元側のネットワークと共有されるノードがある場合は、このノードを送信元側端点とし、送信先側のネットワークと共有されるノードがある場合は、このノードを送信先側端点とする
ことを特徴とする請求項１〜３のいずれかに記載の通信経路の設計回路。
【請求項５】
前記通信経路の設計回路が、トラフィック要求データ、ネットワークデータ及び経路設計条件を入力する入力部を有することを特徴とする請求項１〜４のいずれかに記載の通信経路の設計回路。
【請求項６】
ネットワーク上の一の送信元側端点と、複数の送信先側端点間の経路設計を行う通信経路の設計方法であって、
通信経路の設計回路が、
選択された複数の送信先側端点のそれぞれに接続される一の送信先側仮想ノードと、この仮想ノードと前記送信先側端点を接続する複数の仮想リンクを作成し、
前記送信元側端点及び前記送信先側仮想ノード間で、一送信元対一送信先間の経路設計を行い、
この設計された経路から前記仮想ノード及び前記仮想リンクを削除する
ことを特徴とする通信経路の設計方法。
【請求項７】
ネットワーク上の複数の送信元側端点と、一の送信先側端点間の経路設計を行う通信経路の設計方法であって、
通信経路の設計回路が、
選択された複数の送信元側端点のそれぞれに接続される一の送信元側仮想ノードと、この仮想ノードと前記送信元側端点を接続する複数の仮想リンクを作成し、
前記送信元側仮想ノード及び前記送信先側端点間で、一送信元対一送信先間の経路設計を行い、
この設計された経路から前記仮想ノード及び前記仮想リンクを削除することを特徴とする通信経路の設計方法。
【請求項８】
ネットワーク上の複数の送信元側端点と、複数の送信先側端点間の経路設計を行う通信経路の設計方法であって、
通信経路の設計回路が、
選択された複数の送信元側端点のそれぞれに接続される一の送信元側仮想ノードと、選択された複数の送信先側端点のそれぞれに接続される一の送信先側仮想ノードと、これらの仮想ノードとそれぞれの前記端点を接続する複数の仮想リンクを作成し、
前記送信元側仮想ノードと前記送信先側仮想ノード間で、一送信元対一送信先間の経路設計を行い、
この設計された経路から前記仮想ノード及び前記仮想リンクを削除する
ことを特徴とする通信経路の設計方法。
【請求項９】
ネットワーク上の複数の送信元側端点と、複数の送信先側端点間の経路設計を行う通信経路の設計プログラムであって、
通信経路の設計回路に、
選択された複数の送信元側端点のそれぞれに接続される一の送信元側仮想ノードと、選択された複数の送信先側端点のそれぞれに接続される一の送信先側仮想ノードと、これらの仮想ノードとそれぞれの前記端点を接続する複数の仮想リンクを作成させ、
前記送信元側仮想ノードと前記送信先側仮想ノード間で、一送信元対一送信先間の経路設計を行わせ、
この設計された経路から前記仮想ノード及び前記仮想リンクを削除させることを実行させるための通信経路の設計プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ネットワークにおける複数の送受信端点に対して、仮想ノード及び仮想リンクを設定することにより、一送信元対一送信先間の経路設計を適用可能とし、複数の送受信端点間における適切な経路の設計を行う通信経路の設計回路、通信経路の設計方法及び通信経路の設計プログラムに関する。
【０００２】
【従来の技術】
従来、ネットワークにおける送信元側端点と送信先側端点間の経路設計に関して、一の送信元側端点と一の送信先側端点を両端として経路設計する方法があった。
この方法としては、例えば、「Ｈ．  Ｓａｉｔｏ，  ｅｔ  ａｌ，  “Ｊｏｉｎｔ  ｃａｐａｃｉｔｙ  ａｓｓｉｇｎｍｅｎｔ  ｔｏ  ｓｔａｔｅ−ｉｎｄｅｐｅｎｄｅｎｔ  ｗｏｒｋｉｎｇ  ａｎｄ  ｓｐａｒｅ  ｐａｔｈｓ  ｆｏｒ  ｅｎｈａｎｃｅｄ  ｎｅｔｗｏｒｋ  ｓｕｒｖｉｖａｂｉｌｉｔｙ”，  Ｐｒｏｃ．  ＩＣＣ’９８，  ｐｐ．  １７４３−１７４８，  Ｊｕｎｅ  １９９８．」に示されているものを挙げることができる。
これによれば、一の送信元側端点と一の送信先側端点間を結ぶ通信経路として、適切な１又は２以上の経路を設計することが可能であった。
【０００３】
【発明が解決しようとする課題】
しかしながら、このような設計方法を用いた場合には、送信元側端点又は送信先側端点が複数ある場合には、送信元側端点の数×送信先側端点の数の回数分の経路設計を行う必要があり、経路設計に要する時間が極めて大きくなるという問題があった。
【０００４】
また、送信元側端点又は送信先側端点が複数ある場合の経路設計においては、経路設計条件として、求める複数の経路間で同一のノードを共有しないなど、経路間で非独立な制約条件を設定する場合には、従来の方法では困難であった。
すなわち、このような経路間で非独立な制約条件がある場合には、送信元側端点の数×送信先側端点の数の回数分の経路設計の計算における早い段階で、この非独立な制約条件を考慮し、不必要な計算を排除することができない。
【０００５】
この場合は、送信元側端点の数×送信先側端点の数の回数分の経路結果が得られた後にチェックすることが必要であり、経路設計のために更に大きな計算時間が必要になるという問題があった。
ところが、複数のネットワークを接続する場合には、複数の送信元側端点及び複数の送信先側端点を選択できることがあり、近年このような接続において、適切な経路設計を行うための方法などの実現が望まれていた。
【０００６】
本発明は、上記の事情にかんがみなされたものであり、従来のような通信経路の設計に関する不都合を解消し、ネットワークにおいて、複数の送受信端点がある場合にも適切な経路設計を実現することのできる通信経路の設計回路、通信経路の設計方法及び通信経路の設計プログラムの提供を目的とする。
【０００７】
【課題を解決するための手段】
上記目的を達成するため、本発明の請求項１記載の通信経路の設計回路は、ネットワーク上の一の送信元側端点と、複数の送信先側端点間の経路設計を行う通信経路の設計回路であって、選択された複数の送信先側端点のそれぞれに接続される一の送信先側仮想ノードと、この仮想ノードと送信先側端点を接続する複数の仮想リンクを作成する仮想ノード・仮想リンク作成手段と、送信元側端点及び送信先側仮想ノード間の経路の設計を行う一送信元対一送信先間経路設計手段と、仮想ノード及び仮想リンクを、設計された経路から削除する仮想ノード・仮想リンク削除手段とを有する構成としてある。
【０００８】
通信経路の設計回路をこのような構成にすれば、ネットワークにおいて、一の送信元側端点から、複数の送信先側端点への通信経路を設計するにあたり、適切な設計を行うことが可能となる。
これを、従来の一送信元対一送信先間の経路設計（以下、一対一設計と称する。）をそのまま用いて行うことは、実質的に極めて困難であった。
本発明の通信経路の設計回路によれば、従来の一対一設計をそのまま用いて、上述のような通信経路設計を行う場合に比較して、計算量を大幅に削減することが可能となる。
【０００９】
このため、このような新たな設計回路を用いることにより、複数のネットワーク間における通信経路の設計をより適切に実現することも可能となる。
なお、この通信経路の設計回路における一送信元対一送信先間経路設計手段は、従来の一対一設計を実行するものであり、仮想ノード及び仮想リンクを用いることにより、複数の送受信端点を仮想的に一対一とすることに本発明の特徴がある。
【００１０】
本発明の請求項２記載の通信経路の設計回路は、ネットワーク上の複数の送信元側端点と、一の送信先側端点間の経路設計を行う通信経路の設計回路であって、選択された複数の送信元側端点のそれぞれに接続される一の送信元側仮想ノードと、この仮想ノードと送信元側端点を接続する複数の仮想リンクを作成する仮想ノード・仮想リンク作成手段と、送信元側仮想ノード及び送信先側端点間の経路の設計を行う一送信元対一送信先間経路設計手段と、仮想ノード及び仮想リンクを、設計された経路から削除する仮想ノード・仮想リンク削除手段とを有する構成としてある。
【００１１】
通信経路の設計回路をこのような構成にすれば、ネットワークにおいて、複数の送信元側端点から、一の送信先側端点への通信経路を設計するにあたり、適切な設計を行うことが可能となる。
【００１２】
本発明の請求項３記載の通信経路の設計回路は、ネットワーク上の複数の送信元側端点と、複数の送信先側端点間の経路設計を行う通信経路の設計回路であって、選択された複数の送信元側端点のそれぞれに接続される一の送信元側仮想ノードと、選択された複数の送信先側端点のそれぞれに接続される一の送信先側仮想ノードと、これらの仮想ノードとそれぞれの端点を接続する複数の仮想リンクを作成する仮想ノード・仮想リンク作成手段と、送信元側仮想ノード及び送信先側仮想ノード間の経路の設計を行う一送信元対一送信先間経路設計手段と、仮想ノード及び仮想リンクを、設計された経路から削除する仮想ノード・仮想リンク削除手段とを有する構成としてある。
【００１３】
通信経路の設計回路をこのような構成にすれば、ネットワークにおいて、送信元側端点が複数あり、かつ、送信先側端点も複数ある場合に、適切な通信経路を設計することができる。
【００１４】
本発明の請求項４記載の通信経路の設計回路は、複数のネットワーク間の経路設計を行うにあたって、ネットワーク内において、送信元側のネットワークと共有されるノードがある場合は、このノードを送信元側端点とし、送信先側のネットワークと共有されるノードがある場合は、このノードを送信先側端点とする構成としてある。
【００１５】
通信経路の設計回路をこのような構成にすれば、あるネットワーク内における通信経路の設計にあたり、このネットワークと、このネットワークの送信元側の他のネットワークが共有する複数のノードから、同様に送信先側のネットワークと共有される複数のノードへの適切な経路設計を行うことが可能となる。
【００１６】
このため、従来は、ネットワーク内において、経路設計を行うにあたっては、特定の一の送信元側端点と一の送信先側端点を指定する必要があったが、本通信経路の設計回路により、複数の送受信端点を指定でき、一層適切な通信経路を自動的に設計することができることとなる。
なお、通信経路全体における送信元側端点又は送信先側端点は、ネットワーク間の共有ノードではないが、この場合は、それぞれをそのまま送信元側端点又は送信先側端点として設定できるのはもちろんのことである。
【００１７】
本発明の請求項５記載の通信経路の設計回路は、通信経路の設計回路が、トラフィック要求データ、ネットワークデータ及び経路設計条件を入力する入力部を有する構成としてある。
【００１８】
通信経路の設計回路をこのような構成にすれば、入力されたトラフィック要求データ、ネットワークデータ及び経路設計条件にもとづいて経路設計を実施することが可能となる。
このトラフィック要求データとは、各トラフィックの送信元側端点（ノード）、送信先側端点（ノード）及び設計経路数である。また、これらにトラフィック要求の帯域などのデータが含まれることもある。
また、ネットワークデータとは、ノードとリンクの接続データを意味する。また、必要があればリンク帯域などのデータが含まれることもある。
【００１９】
そして、経路設計条件とは、設計する経路の制約条件と目的関数を意味する。
例えば、制約条件としては、経路が互いに点素であること、経路がループしないことなどが挙げられる。この点素とは、算出される複数の経路がノードを共有しないこと、すなわち、同一ノードを経由しないことを意味する。
また、目的関数としては、ホップ数の最小化、遅延最小化、収容するトラフィック要求の帯域などを考慮した負荷分散最適化等の設計基準にもとづいた関数を挙げることができる。
【００２０】
経路が互いに点素であること等の条件は、経路に対して非独立な条件であるといえる。
これに対して、経路がループしないこと、ホップ数の最小化などは、経路に対して独立な条件である。
経路に対して非独立な条件を設定する場合には、従来の経路設計では、これらを計算の早い段階で排除することができず、送信元端点の数×送信先端点の数の回数分の一対一設計を行った後にそのチェックする必要などがあり、大きな計算時間が必要であった。
【００２１】
本発明の請求項６記載の通信経路の設計方法は、ネットワーク上の一の送信元側端点と、複数の送信先側端点間の経路設計を行う通信経路の設計方法であって、通信経路の設計回路が、選択された複数の送信先側端点のそれぞれに接続される一の送信先側仮想ノードと、この仮想ノードと送信先側端点を接続する複数の仮想リンクを作成し、送信元側端点及び送信先側仮想ノード間で、一送信元対一送信先間の経路設計を行い、この設計された経路から仮想ノード及び仮想リンクを削除する方法としてある。
【００２２】
通信経路の設計方法をこのような方法にすれば、ネットワークにおいて、一の送信元側端点から、複数の送信先側端点への通信経路を設計するにあたり、適切な設計を行うことができる。
【００２３】
本発明の請求項７記載の通信経路の設計方法は、ネットワーク上の複数の送信元側端点と、一の送信先側端点間の経路設計を行う通信経路の設計方法であって、通信経路の設計回路が、選択された複数の送信元側端点のそれぞれに接続される一の送信元側仮想ノードと、この仮想ノードと送信元側端点を接続する複数の仮想リンクを作成し、送信元側仮想ノード及び送信先側端点間で、一送信元対一送信先間の経路設計を行い、この設計された経路から仮想ノード及び仮想リンクを削除する方法としてある。
【００２４】
通信経路の設計方法をこのような方法にすれば、ネットワークにおいて、複数の送信元側端点から、一の送信先側端点への通信経路を設計するにあたり、適切な設計を行うことができる。
【００２５】
本発明の請求項８記載の通信経路の設計方法は、ネットワーク上の複数の送信元側端点と、複数の送信先側端点間の経路設計を行う通信経路の設計方法であって、通信経路の設計回路が、選択された複数の送信元側端点のそれぞれに接続される一の送信元側仮想ノードと、選択された複数の送信先側端点のそれぞれに接続される一の送信先側仮想ノードと、これらの仮想ノードとそれぞれの端点を接続する複数の仮想リンクを作成し、送信元側仮想ノードと送信先側仮想ノード間で、一送信元対一送信先間の経路設計を行い、この設計された経路から仮想ノード及び仮想リンクを削除する方法としてある。
【００２６】
通信経路の設計方法をこのような方法にすれば、ネットワークにおいて、送信元側端点が複数あり、かつ、送信先側端点も複数ある場合に、適切な通信経路を設計することが可能となる。
【００２７】
本発明の請求項９記載の通信経路の設計プログラムは、ネットワーク上の複数の送信元側端点と、複数の送信先側端点間の経路設計を行う通信経路の設計プログラムであって、通信経路の設計回路に、選択された複数の送信元側端点のそれぞれに接続される一の送信元側仮想ノードと、選択された複数の送信先側端点のそれぞれに接続される一の送信先側仮想ノードと、これらの仮想ノードとそれぞれの端点を接続する複数の仮想リンクを作成させ、送信元側仮想ノードと送信先側仮想ノード間で、一送信元対一送信先間の経路設計を行わせ、この設計された経路から仮想ノード及び仮想リンクを削除させる構成としてある。
【００２８】
通信経路の設計プログラムをこのような構成にすれば、通信経路の設計回路に、仮想ノード及び仮想リンクを作成させることにより、ネットワークにおける複数の送信元側端点から複数の送信先側端点までの適切な経路を算出させることが可能となる。
【００２９】
【発明の実施の形態】
以下、本発明の実施形態につき、図面を参照して説明する。
まず、図１を参照して説明する。同図は、本発明の各実施形態における通信経路の設計回路の構成を示すブロック図である。
【００３０】
同図に示すように、通信経路の設計回路は、入力部１０、記憶部２０、経路設計部３０及び出力部４０を有している。
入力部１０は、トラフィック要求データ、ネットワークデータ及び経路設計条件を入力する装置である。
記憶部２０は、入力部１０により入力されたトラフィック要求データ、ネットワークデータ及び経路設計条件を記憶する装置である。また、記憶部２０は、出力部４０により出力された経路情報も記憶する。
【００３１】
経路設計部３０は、仮想ノード・仮想リンク作成手段３１、一送信元対一送信先間経路設計手段３２及び仮想ノード・仮想リンク削除手段３３を有している。仮想ノード・仮想リンク作成手段３１は、記憶部２０からトラフィック要求データ、ネットワークデータを抽出し、これらにもとづいて、ネットワーク内に送信元側端点が複数ある場合には、このそれぞれに接続される一の仮想ノードを作成するものである。
【００３２】
また、この仮想ノードと各送信元側端点のそれぞれを接続する仮想リンクを作成する。
さらに、送信先側端点についても同様に、仮想ノード及び仮想リンクを作成することができる。
【００３３】
この仮想ノード及び仮想リンクの作成は、例えば、複数の送信先側端点のそれぞれに接続される他のネットワークの特定のノードの代わりに、仮想のノードを想定し、上記特定のノードへのアドレスが設定されるべき経路情報を、この仮想ノードのアドレスに変換することにより行うことができる。
また、送信元側端点が複数の場合についても同様にして作成することが可能である。
【００３４】
一送信元対一送信先間経路設計手段３２は、従来の一対一設計を実施するものである。
この際、送信元側端点及び送信先側端点としては、仮想ノードを利用することにより、それぞれ一つの送信元又は送信先を指定することが可能となり、従来の一対一設計を利用することが可能となる。
また、その他の設計経路数や、経路設計条件等の情報は、記憶部２０からトラフィック要求データ、ネットワークデータ及び経路設計条件を抽出し、これらにもとづいて設定する。
【００３５】
設計する経路情報としては、最適な一つの経路のみならず、複数の経路情報を算出することが可能である。
この場合、この複数の経路情報について、より通信に有利な順に順位付けすることも可能である。
【００３６】
仮想ノード・仮想リンク削除手段３３は、設計された経路情報から仮想ノード及び仮想リンクを削除することにより、必要な経路のみを有する経路情報を作成するものである。
そして、出力部４０は、このようにして作成された経路情報を出力するものである。出力された経路情報は、記憶部２０によって記憶される。
【００３７】
次に、第一実施形態の通信経路の設計回路における処理手順について、図２を参照して説明する。
同図は、本実施形態の通信経路の設計回路における処理手順を示す動作手順図である。
【００３８】
まず、入力部１０は、トラフィック要求データ、ネットワークデータ及び経路設計条件をそれぞれ入力する（順にステップ１０，１１，１２）。
このトラフィック要求データ及びネットワークデータは、仮想ノード・仮想リンク作成手段３１が、仮想ノード及び仮想リンクを作成する際（ステップ１３）に使用される。
【００３９】
また、経路設計条件は、一送信元対一送信先間経路設計手段３２が、一対一設計を実行する際（ステップ１４）に使用される。
なお、それぞれの入力情報の入力順は、どのような順であってもよい。また、ネットワークデータは、ネットワーク内の全ノードとその接続情報であるため、通常事前に入力し、記憶部２０に記憶しておくことが好ましい情報である。
これは、一度入力しておけば、例えば、ネットワーク内のノードの構成に変更があった場合にのみ修正すればよい。
【００４０】
また、トラフィック要求データと経路設計条件は、取得したい経路に応じて入力するものであり、同一内容で使用する場合には、一度記憶部２０に記憶しておけば、以降は省略することができる。
ステップ１３における仮想ノード及び仮想リンクを作成することにより、擬似的に送信元側端点及び送信先側端点のいずれをも一の端点とすることができるため、ステップ１４において、一対一設計を実行することが可能となる。
【００４１】
この一対一設計の実行により作成された経路情報は、送信元側仮想ノードと送信元側端点間の部分、及び送信先側端点と送信先側仮想ノード間の部分が不要である。
このため、次に仮想ノード・仮想リンク削除手段３３は、作成された経路情報から仮想ノード及び仮想リンクを削除する（ステップ１５）。これによって、適切な経路情報が完成する。
そして、出力部４０は、完成した経路情報を出力する（ステップ１６）。
【００４２】
次に、第一実施形態の通信経路の設計回路の動作を、図２の動作手順図と、図３〜図７のネットワークを示す図にもとづき詳細に説明する。
【００４３】
（１）一の送信元側端点から複数の送信先側端点への経路設計の場合
図３は、本発明の通信経路の設計を行う対象であるネットワークＮＷＫ１を示す図であり、このネットワークＮＷＫ１は、Ｒ１〜Ｒ８の各ノードを有している。
はじめに、同図において、送信元側端点としてＲ１を、送信先側端点としてＲ７及びＲ８を選択し、この間に２本の経路を設計する場合について考える。
【００４４】
まず、トラフィック要求データとして、送信元側端点と送信先側端点の集合の対｛（Ｒ１），（Ｒ７，Ｒ８）｝と、経路本数として２を入力する。
次に、経路設計条件を入力する。この場合は、経路が互いに点素である（ノードを共有しない）、経路がループしないという制約条件、及び経路のホップ数の合計を最小化するという目的関数を入力する。この経路設計条件は、通信経路の設計基準となるものである。
【００４５】
また、ネットワークデータが未登録である場合には、この入力を行う。これは、ネットワーク内の全ノードとその接続関係の情報を有するデータである。
次に、入力された情報にもとづいて仮想ノード及び仮想リンクの作成が行われる。
【００４６】
図４は、送信先側仮想ノード及び仮想リンクを付加したネットワークＮＷＫ１を示す図である。
通信経路の設計回路の経路設計部３０における仮想ノード・仮想リンク作成手段３１が、送信先側端点であるＲ７とＲ８に接続される仮想ノードＶ１と、このＶ１とＲ７及びＲ８とを接続する仮想リンクを作成する。
【００４７】
次に、一送信元対一送信先間経路設計手段３２が、経路設計を実行する。
この経路設計の実行にあたり、送信元側端点としてＲ１、送信先側端点としてＶ１が設定される。
このようにして、擬似的に送信元及び送信先の両端点が共に一つとなるため、従来の一対一設計を実行することができる。
【００４８】
この実行の結果、Ｒ１→Ｒ３→Ｒ６→Ｒ７→Ｖ１と、Ｒ１→Ｒ５→Ｒ８→Ｖ１の２組の経路情報を得ることができる。
しかしながら、この経路情報には、Ｒ７とＶ１間、Ｒ８とＶ１間の経路情報が余分に含まれているため、この分の経路情報を仮想ノード・仮想リンク削除手段３３により削除する。
そして、最終的にＲ１→Ｒ３→Ｒ６→Ｒ７と、Ｒ１→Ｒ５→Ｒ８の経路情報が得られ、出力部４０が、これらを設計結果として出力する。
【００４９】
（２）複数の送信元側端点から複数の送信先側端点への経路設計の場合
次に、図３において、送信元側端点としてＲ１及びＲ２を、送信先側端点としてＲ７及びＲ８を選択し、この間に２本の経路を設計する場合について考える。他の経路設計条件等は、（１）の場合と同様とする。
【００５０】
この場合、仮想ノード・仮想リンク作成手段３１は、（１）の場合と同様に仮想ノードＶ１と、このＶ１とＲ７及びＲ８を接続する仮想リンクを作成することに加え、送信元側端点Ｒ１及びＲ２に接続する仮想ノードＶ２と、このＶ２とＲ１及びＲ２を接続する仮想リンクを作成する。
【００５１】
図５は、このようにして作成された送信元側及び送信先側仮想ノード及び仮想リンクを付加したネットワークＮＷＫ１を示す図である。
同図における仮想ノードＶ２を送信元側端点とし、仮想ノードＶ１を送信先側端点として、一送信元対一送信先間経路設計手段３２は、一対一設計を実行する。
【００５２】
この場合、ノードを共有せず、経路がループしない経路としては、▲１▼（Ｖ２→Ｒ１→Ｒ３→Ｒ６→Ｒ７→Ｖ１，Ｖ２→Ｒ２→Ｒ５→Ｒ８→Ｖ１）、▲２▼（Ｖ２→Ｒ１→Ｒ３→Ｒ６→Ｒ７→Ｖ１，Ｖ２→Ｒ２→Ｒ４→Ｒ８→Ｖ１）、▲３▼（Ｖ２→Ｒ１→Ｒ５→Ｒ８→Ｖ１，Ｖ２→Ｒ２→Ｒ４→Ｒ６→Ｒ７→Ｖ１）、▲４▼（Ｖ２→Ｒ１→Ｒ３→Ｒ４→Ｒ６→Ｒ７→Ｖ１，Ｖ２→Ｒ２→Ｒ５→Ｒ８→Ｖ１）、▲５▼（Ｖ２→Ｒ１→Ｒ５→Ｒ８→Ｖ１，Ｖ２→Ｒ２→Ｒ４→Ｒ３→Ｒ６→Ｒ７→Ｖ１）、▲６▼（Ｖ２→Ｒ１→Ｒ３→Ｒ６→Ｒ７→Ｖ１，Ｖ２→Ｒ２→Ｒ４→Ｒ５→Ｒ８→Ｖ１）、▲７▼（Ｖ２→Ｒ１→Ｒ３→Ｒ６→Ｒ７→Ｖ１，Ｖ２→Ｒ２→Ｒ５→Ｒ４→Ｒ８→Ｖ１）の組が挙げられるが、このうちホップ数が最小である▲１▼〜▲３▼の経路のうちの任意の一組が設計される。
【００５３】
また、実際には、経路設計条件として、遅延最小化や、負荷分散最適化等の関数を設定することにより、さらに最も適切な一を絞りこむこともできる。
このようにして設計された経路情報には、Ｖ２とＲ１及びＲ２間、Ｖ１とＲ７及びＲ８間の経路情報が余分であるため、（１）の場合と同様にして、仮想ノード・仮想リンク削除手段３３により、これらが削除され、必要な経路のみが設計されて、出力部４０によって出力される。
【００５４】
なお、（２）においては、送信元側端点及び送信先側端点がそれぞれ２つある場合を例に説明したが、これらの一方又は双方が３つ以上ある場合についても、トラフィック要求データにそれらを設定することにより、同様にして経路設計を行うことができる。
【００５５】
また、設計経路数についても、（１），（２）では２本の経路を求めたが、従来の一対一設計は、３本以上にも対応しているため、これを用いることのできる本発明においても、トラフィック要求データに設計経路数として３本以上を指定することにより、同様に設計することができる。
【００５６】
（３）複数のネットワーク間で経路設計をする場合
次に、あるネットワークの送信元側端点から他のネットワークにおける送信先側端点への通信経路の設計について図６を用いて説明する。
同図は、本発明の通信経路の設計を行う対象であるネットワークＮＷＫ１と送信先側端点を含むネットワークＮＷＫ２を示す図である。
【００５７】
同図において、Ｒ１を送信元側端点とし、Ｒ１２を送信先側端点とする。
この場合、ネットワークＮＷＫ１の管理者は、ＮＷＫ１内の経路しか設計しないため、Ｒ１２へ到達可能なＲ７又はＲ８までの経路を設計する。
すなわち、この場合は、上記（１）と同様にして通信経路の設計を行うことができる。
【００５８】
図７は、本発明の、ネットワークＮＷＫ２側の仮想ノード及び仮想リンクを有するネットワークＮＷＫ１を示す図である。
同図に示すように、他のネットワーク内の送信先側端点への通信経路を設計する場合であっても、Ｒ１２へ到達可能なＮＷＫ１における端点、すなわちＲ７及びＲ８までの通信経路の設計を行えばよい。
【００５９】
そして、（１）の場合と同様に、これらＲ７及びＲ８に接続する仮想ノード及び仮想リンクを作成し、一対一設計を実行することによって、適切な経路を設計することができる。
また、ネットワークＮＷＫ１の前にさらにネットワークＮＷＫ０が存在し、このネットワークＮＷＫ０における送信元側端点から、ネットワークＮＷＫ１を経由し、ネットワークＮＷＫ２における送信先側端点への通信経路を設計する場合も同様に考えることができる。
【００６０】
すなわち、ネットワークＮＷＫ０からネットワークＮＷＫ１への経路として、Ｒ１及びＲ２が考えられる場合には、これらを送信元側端点とし、Ｒ７及びＲ８を送信先側端点として、上記（２）の場合と同様にして、経路設計を行うことができる。
【００６１】
このように、複数のネットワーク間で経路設計する場合は、それぞれのネットワークの中で本発明の通信経路の設計を実行する。
例えば、ネットワークＮＷＫ２においては、Ｒ７及びＲ８を送信元側端点とし、Ｒ１２を送信先側端点として、同様に通信経路の設計を実行すればよいこととなる。
【００６２】
また、このようなネットワーク間の通信経路の設計においても、上述のように送信元側端点、送信先側端点が３以上となる場合や、設計経路数が３以上である場合であっても、トラフィック要求データとしてこれらを指定することにより同様にして設計することができる。
【００６３】
上記の実施形態における仮想ノード・仮想リンク作成や、一対一設計等は、通信経路の設計プログラムにより実行される。
この通信経路の設計プログラムは、コンピュータの各構成要素に指令を送り、所定の処理、例えば、仮想ノード・仮想リンク作成処理や、一対一設計処理等を行わせる。
これによって、これらの処理は、通信経路の設計プログラムとコンピュータとが協働した通信経路の設計回路により実現される。
【００６４】
なお、通信経路の設計プログラムは、コンピュータのＲＯＭやハードディスクに記憶させる他、コンピュータ読み取り可能な記録媒体、たとえば、外部記憶装置及び可搬記録媒体等に格納することができる。
外部記憶装置とは、磁気ディスク等の記録媒体を内蔵し、例えば通信経路の設計回路などに外部接続される記憶増設装置をいう。一方、可搬記録媒体とは、記録媒体駆動装置（ドライブ装置）に装着でき、かつ、持ち運び可能な記録媒体であって、たとえば、ＣＤ−ＲＯＭ、フレキシブルディスク、メモリカード、光磁気ディスク等をいう。
【００６５】
そして、記録媒体に記録されたプログラムは、コンピュータのＲＡＭにロードされて、ＣＰＵにより実行される。この実行により、上述した本実施形態の通信経路の設計回路の機能が実現される。
さらに、コンピュータで通信経路の設計プログラムをロードする場合、他のコンピュータで保有された通信経路の設計プログラムを、通信回線を利用して自己の有するＲＡＭや外部記憶装置にダウンロードすることもできる。
【００６６】
このダウンロードされた通信経路の設計プログラムも、ＣＰＵにより実行され、本実施形態の仮想ノード・仮想リンク作成処理や、一対一設計処理等を実現する。
【００６７】
【発明の効果】
以上のように、本発明によれば、通信経路の設計において、送信元側のノードや、送信先側のノードが複数あり、これらの選択が可能な場合に、仮想ノード及び仮想リンクを作成することにより、従来の一対一設計を適用することが可能となる。
【００６８】
このような送受信端点が複数の場合は、従来の設計手法では、送信元側ノードと送信先側ノードの全ての組合せで経路を設計し、その後に経路が点素である等の制約条件をチェックすることなどを行う必要がある。
本発明によれば、上記のような全ての組合せの設計を行う必要がなく、また、経路が互いに点素であること等の、経路に非独立な制約条件による不必要な探索範囲を、計算の早い段階で排除できるため、大幅に計算時間及びこれに使用するリソースを減少させることができる。
【００６９】
また、本発明は、特に複数のネットワークにまたがる通信経路の設計において、その真価を発揮する。
すなわち、このような場合には、ネットワーク間を接続するノードが複数となる場合があり、より効果の高い通信経路を設計するには、複数の送受信端点間の設計に対応する設計回路及びその方法を実現する必要がある。
そして、これにより、複数の送受信端点を選択肢に含んだ上で、障害回避、あるいは負荷分散を考慮した経路設計を行うことが可能となる。
【００７０】
また、通信経路の設計プログラムは、コンピュータの各構成要素へ所定の指令を送ることにより、この仮想ノード・仮想リンク作成機能や、一対一設計機能等を実現させることができる。
これによって、これらの機能等は、通信経路の設計プログラムとコンピュータとが協働した通信経路の設計回路により実現可能である。
【図面の簡単な説明】
【図１】本発明の各実施形態の通信経路の設計回路の構成を示すブロック図である。
【図２】本発明の各実施形態の通信経路の設計回路の処理手順を示す動作手順図である。
【図３】本発明の通信経路の設計を行う対象であるネットワークＮＷＫ１を示す図である。
【図４】本発明の送信先側仮想ノード及び仮想リンクを付加したネットワークＮＷＫ１を示す図である。
【図５】本発明の送信元側及び送信先側仮想ノード及び仮想リンクを付加したネットワークＮＷＫ１を示す図である。
【図６】本発明の通信経路の設計を行う対象であるネットワークＮＷＫ１と送信先側端点を含むネットワークＮＷＫ２を示す図である。
【図７】本発明の、ネットワークＮＷＫ２側の仮想ノード及び仮想リンクを付加したネットワークＮＷＫ１を示す図である。
【符号の説明】
１０  入力部
２０  記憶部
３０  経路設計部
３１  仮想ノード・仮想リンク作成手段
３２  一送信元対一送信先間経路設計手段
３３  仮想ノード・仮想リンク削除手段
４０  出力部
【図１】
0003632650.tif 000002
【図２】
0003632650.tif 000003
【図３】
0003632650.tif 000004
【図４】
0003632650.tif 000005
【図５】
0003632650.tif 000006
【図６】
0003632650.tif 000007
【図７】
0003632650.tif 000008