(57)【要約】【課題】  所定の制約条件のもとで最適なマルチキャスト経路を計算する経路計算方法を提供し、通信ネットワークにおけるマルチキャスト経路のコストパフォーマンスを向上させる。【解決手段】  ０＜ｄ≦Δなるｄに対して、二つのノードをつなぐ経路のうち、リンクの制約パラメータの和がｄであり、コストパラメータの和が最小になる経路を抽出し（Ｓ３）、必通ノードにより完全グラフＧ’を生成し（Ｓ４）、必通ノードを一つ取り出し、グラフＧ’の部分グラフＧ”を生成し（Ｓ５）、グラフＧ”に含まれるノードとグラフＧ”に含まれないグラフＧ’のノードとをつなぐリンクのうち、制約パラメータが所定の条件を満たし、コストパラメータが最小となるリンクを選択し、選択したリンクとノードをグラフＧ”に追加し（Ｓ６）、Ｒに含まれるノードがすべてＧ”に含まれるまでステップＳ６を実行する（Ｓ７）ことに基づいて最適なマルチキャスト経路を計算する。【選択図】      図２
2006222875.tif 000002
【特許請求の範囲】
【請求項１】
ノードの集合Ｖとリンクの集合ＥとからなるグラフＧにおいて、所定の制約条件下で所定のパラメータを最適化する経路を、処理部と記憶部とを少なくとも備えたコンピュータにより計算して求める経路計算方法であって、
前記コンピュータが
前記リンクの集合Ｅに含まれるリンクに対して第１のパラメータと第２のパラメータとを設定する第１のステップと、
前記ノードの集合Ｖに含まれるノードのうち求めるべき経路が必ず通るノードを取り出し、前記取り出したノードにより必通ノード集合Ｒを設定するとともに、前記求めるべき経路上の任意の２つのノード間の経路に含まれるリンクに設定された前記第２のパラメータの和ｄの最大値としてΔを設定する第２のステップと、
前記ｄが０＜ｄ≦Δを満たすすべてのｄに対して、前記ノードの集合Ｖに含まれる任意の２つのノードをつなぐ経路のうち、その経路上のリンクに設定された前記第２のパラメータの和がｄであり、その経路上のリンクに設定された前記第１のパラメータの和が最小になる経路を抽出し、その抽出した経路の経路情報と、その抽出した経路に含まれるリンクに設定された前記第１のパラメータの和の値とを前記記憶部に記憶する第３のステップと、
前記必通ノード集合Ｒに含まれるすべてのノードにより完全グラフＧ’を生成する第４のステップと、
前記必通ノード集合Ｒに含まれるノードを１つ取り出して、前記完全グラフＧ’に含まれる部分グラフＧ”を生成する第５のステップと、
前記部分グラフＧ”に含まれるリンクについて、そのリンクの前記グラフＧ上の経路を求めるとともに、前記求められた経路に含まれるリンクの前記第１のパラメータの和および前記第２のパラメータの和を、それぞれ第３のパラメータおよび第４のパラメータとして前記記憶部に記憶する第６のステップと、
前記部分グラフＧ”に含まれるノードと、前記部分グラフＧ”に含まれず、前記完全グラフＧ’に含まれるノードとをつなぐ前記完全グラフＧ’上のリンクについて、そのリンクの前記グラフＧ上の経路を求めるとともに、前記求められた経路に含まれるリンクの前記第１のパラメータの和および前記第２のパラメータの和を、それぞれ第５のパラメータおよび第６のパラメータとして前記記憶部に記憶する第７のステップと、
前記部分グラフＧ”に含まれるノードと、前記部分グラフＧ”に含まれず、前記完全グラフＧ’に含まれるノードとをつなぐ前記完全グラフＧ’上のリンクのうち、前記第６のパラメータを前記部分グラフＧ”に含まれる任意の２ノード間をつなぐ経路に含まれるリンクの前記第２のパラメータの和の最大値に加算した値が前記Δの値以下であって、前記第５のパラメータの値が最小になるリンクを抽出し、前記抽出されたリンクおよび前記抽出されたリンクの前記部分グラフＧ”に含まれないノードを前記部分グラフＧ”に追加する第８のステップと、
前記必通ノード集合Ｒに含まれるノードがすべて前記部分グラフＧ”に含まれるかを判定し、前記必通ノード集合Ｒに含まれるノードであって前記部分グラフＧ”に含まれていないノードがあった場合には、そのノードの１つを取り出し、前記必通ノード集合Ｒに含まれるノードがすべて前記部分グラフＧ”に含まれるまで前記第６のステップないし前記第８のステップを繰り返し実行する第９のステップと、
前記部分グラフＧ”に含まれるすべてのリンクによって構成される経路について、その経路に含まれる前記部分グラフＧ”上のリンクを前記グラフＧ上の経路に変換し、前記変換したグラフＧ上の経路にループがあるか否かをチェックし、ループがなかった場合には、前記変換したグラフＧ上の経路を求めるべき経路として抽出する第１０のステップと
を実行することを特徴とする経路計算方法。
【請求項２】
請求項１に記載の経路計算方法において、
前記コンピュータは、
前記グラフＧを通信ネットワークであるとし、前記第１のパラメータには前記通信ネットワークにおけるリンクのコストに係るパラメータを設定し、前記第２のパラメータには前記通信ネットワークにおけるリンクの性能に係るパラメータを設定すること
を特徴とする経路計算方法。
【請求項３】
請求項１または請求項２に記載の経路計算方法をコンピュータに実行させるためのプログラムであることを特徴とする経路計算プログラム。
【請求項４】
請求項３に記載の経路計算プログラムをコンピュータ読み取り可能な記憶媒体に記憶したことを特徴とする経路計算プログラム記憶媒体。
【請求項５】
処理部と記憶部とを少なくとも備え、ノードの集合Ｖとリンクの集合ＥとからなるグラフＧにおいて、所定の制約条件下で所定のパラメータを最適化する経路を計算して求める経路計算装置であって、
前記処理部が、
前記リンクの集合Ｅに含まれるリンクに対して第１のパラメータと第２のパラメータとを設定する第１の処理と、
前記ノードの集合Ｖに含まれるノードのうち求めるべき経路が必ず通るノードを取り出し、前記取り出したノードにより必通ノード集合Ｒを設定するとともに、前記求めるべき経路上の任意の２つのノード間の経路に含まれるリンクに設定された前記第２のパラメータの和ｄの最大値としてΔを設定する第２の処理と、
前記ｄが０＜ｄ≦Δを満たすすべてのｄに対して、前記ノードの集合Ｖに含まれる任意の２つのノードをつなぐ経路のうち、その経路上のリンクに設定された前記第２のパラメータの和がｄであり、その経路上のリンクに設定された前記第１のパラメータの和が最小になる経路を抽出し、その抽出した経路の経路情報と、その抽出した経路に含まれるリンクに設定された前記第１のパラメータの和の値とを前記記憶部に記憶させる第３の処理と、
前記必通ノード集合Ｒに含まれるすべてのノードにより完全グラフＧ’を生成する第４の処理と、
前記必通ノード集合Ｒに含まれるノードを１つ取り出して、前記完全グラフＧ’に含まれる部分グラフＧ”を生成する第５の処理と、
前記部分グラフＧ”に含まれるリンクについて、そのリンクの前記グラフＧ上の経路を求めるとともに、前記求められた経路に含まれるリンクの前記第１のパラメータの和および前記第２のパラメータの和を、それぞれ第３のパラメータおよび第４のパラメータとして前記記憶部に記憶させる第６の処理と、
前記部分グラフＧ”に含まれるノードと、前記部分グラフＧ”に含まれず、前記完全グラフＧ’に含まれるノードとをつなぐ前記完全グラフＧ’上のリンクについて、そのリンクの前記グラフＧ上の経路を求めるとともに、前記求められた経路に含まれるリンクの前記第１のパラメータの和および前記第２のパラメータの和を、それぞれ第５のパラメータおよび第６のパラメータとして前記記憶部に記憶させる第７の処理と、
前記部分グラフＧ”に含まれるノードと、前記部分グラフＧ”に含まれず、前記完全グラフＧ’に含まれるノードとをつなぐ前記完全グラフＧ’上のリンクのうち、前記第６のパラメータを前記部分グラフＧ”に含まれる任意の２ノード間をつなぐ経路に含まれるリンクの前記第２のパラメータの和の最大値に加算した値が前記Δの値以下であって、前記第５のパラメータの値が最小になるリンクを抽出し、前記抽出されたリンクおよび前記抽出されたリンクの前記部分グラフＧ”に含まれないノードを前記部分グラフＧ”に追加する第８の処理と、
前記必通ノード集合Ｒに含まれるノードがすべて前記部分グラフＧ”に含まれるかを判定し、前記必通ノード集合Ｒに含まれるノードであって前記部分グラフＧ”に含まれていないノードがあった場合には、そのノードの１つを取り出し、前記必通ノード集合Ｒに含まれるノードがすべて前記部分グラフＧ”に含まれるまで前記第６の処理ないし前記第８の処理を繰り返し実行する第９の処理と、
前記部分グラフＧ”に含まれるすべてのリンクによって構成される経路について、その経路に含まれる前記部分グラフＧ”上のリンクを前記グラフＧ上の経路に変換し、前記変換したグラフＧ上の経路にループがあるか否かをチェックし、ループがなかった場合には、前記変換したグラフＧ上の経路を求めるべき経路として抽出する第１０の処理と
を実行することを特徴とする経路計算装置。
【請求項６】
請求項５に記載の経路計算装置において、
前記処理部は、
前記グラフＧを通信ネットワークであるとし、前記第１のパラメータとして、前記通信ネットワークにおけるリンクのコストに係るパラメータを設定し、前記第２のパラメータとして、前記通信ネットワークにおけるリンクの性能に係るパラメータを設定すること
を特徴とする経路計算装置。
【請求項７】
請求項６に記載の経路計算装置において、
前記処理部が、
前記必通ノード集合Ｒを構成するノードとして、マルチキャスト通信経路の始点ノードおよび終点ノードをすべて含むように設定すること
を特徴とする経路計算装置。
【請求項８】
請求項６または請求項７に記載の経路計算装置を含んで構成されること
を特徴とするネットワーク管理装置。
【請求項９】
請求項６または請求項７に記載の経路計算装置を含んで構成されること
を特徴とするネットワーク経路決定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークなどからなるグラフにおいて、そのグラフに含まれる経路についてその経路に属するリンクに設定されたパラメータに基づき計算される値が最小となるような経路を抽出する経路計算方法、経路計算プログラム、経路計算プログラム記憶媒体および経路計算装置に関し、その経路計算装置を用いたネットワーク管理装置およびネットワーク経路決定装置に関する。
【背景技術】
【０００２】
近年、コンピュータネットワーク上で、動画や音声を特定多数のユーザに転送するマルチキャスト通信が注目を集めている。マルチキャスト通信においては、情報発信元の始点からは１つの情報として転送が開始されるが、始点と情報転送先として選択された多数の終点とを結ぶ経路の途中で経路が分岐する場合には、転送される情報は、その分岐点でコピーされ、各終点へと情報が転送される。これに対し、始点が多数の終点との間で１対１のユニキャスト通信を行う場合には、始点では終点の数だけの情報を転送する必要がある。従って、マルチキャスト通信を行うことにより、そのネットワークにおける情報転送の総量を減少させることができる。
【０００３】
マルチキャスト通信では、転送先となる特定多数の終点は、マルチキャストグループと呼ばれる単位で管理され、そのマルチキャストグループに対して1つの情報転送経路が設定される。この情報転送経路は、始点とマルチキャストグループに属するすべての終点とを接続するよう設定される。このマルチキャストグループに設定された情報転送経路は、マルチキャストグループに新たなユーザが参加したり、脱退者があったりした場合には変化する。
【０００４】
マルチキャスト通信を用いるアプリケーションとして、テレビ会議、オンラインゲーム、映画やテレビ番組などの動画配信などがある。このうち、テレビ会議ではデータ転送遅延が重要な性能項目となる。通常行われる会話では、音声が相手に届くまでの遅延時間が100ms以下である場合、違和感なく会話できることがわかっている。従って、ユーザが満足できるようにテレビ会議サービスなどのアプリケーションを提供するためには、情報転送経路における遅延時間をある所定の値以下にすることが要求される。すなわち、マルチキャストグループの情報転送経路を選択するにあたっては、始点からすべての終点までの遅延時間をある所定の値以下にする必要がある。
【０００５】
また、ネットワーク管理の観点から経路全体での情報転送量を減らし、経路使用者の観点からは経路の使用料金を低減する必要がある。すなわち、マルチキャストグループの情報転送経路を算出する経路計算では、経路全体のコストを最小化することが要求される。このため、テレビ会議などのマルチキャスト通信サービスを実現するためには、経路の遅延条件を満たしつつ、経路全体のコストを最小化することを目的としたアルゴリズムが必要となる。
【０００６】
さらに、同様のアルゴリズムは、近年注目されている光信号を用いた情報ネットワークでも求められている。光信号は、スイッチやファイバなどのリンクで信号レベルが減衰することが知られており、その減衰の仕方は、指数関数的であることがわかっている。すなわち、光信号でマルチキャスト通信を行う場合には、送受信者間の信号レベルの減衰量が所定の減衰量を超えないような情報転送経路を設定する必要がある。なお、ここでの減衰量（例えば、dBで表した値）は、前記ビデオ会議の例における遅延時間に対応する。
【０００７】
以上のような場合における経路計算では、複数の始点と複数の終点とを結ぶ経路のうち、始点と終点とを結ぶ経路の部分経路（リンク）それぞれに割り当てられたある値（例えば、遅延時間）の経路ごとの総和がある所定の値を下回るような経路であって、さらに、各リンクに割り当てられた他の値（例えば、コスト）の総和が最小になるような経路を算出する必要がある。
【０００８】
このような経路計算を行うアルゴリズムは、Delay Constrained Multicast Algorithm（以下、ＤＣＭＡと略称する）と呼ばれることがある。近年、マルチキャスト通信のアプリケーションが増加し、光技術による通信ネットワークが整備されるに伴い、ＤＣＭＡの実現方法に注目が集まっている。例えば、非特許文献１には、単一の始点と複数の終点とを結ぶマルチキャスト経路についてのＤＣＭＡの例が示されている。
【非特許文献１】V. Kompella他, "Multicast routing for multimedia communication", IEEE/ACM Transactions on Networking, Vol.1, No.3, p.286 - p.292, June 1993
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、複数の始点と複数の終点とを結ぶマルチキャスト経路についてのＤＣＭＡを開示した公知文献は、現在のところ見当たらない。そのため、テレビ会議などのマルチキャストアプリケーションを実現する場合には、始点の利用者ごとに単一の始点と複数の終点とを結ぶマルチキャスト経路についてのＤＣＭＡを用いてその始点ごとのマルチキャスト経路を求めていた。そして、始点ごとのマルチキャスト経路を統合してマルチキャストグループ全体のマルチキャスト経路としていた。
【００１０】
一般に、始点ごとに求められるマルチキャスト経路は、必ずしも同じ経路になるとは限らない。そして、対象となるネットワークが大規模または複雑になればなるほど、それぞれの始点で求められるマルチキャスト経路が異なる確率は大きくなる。それぞれの経路つまりリンクにはコストなどのパラメータが割り当てられているので、異なる経路が生ずれば生ずるほど、マルチキャストグループ全体のマルチキャスト経路におけるコストなどのパラメータの総和は大きくなる。従って、単一の始点と複数の終点とを結ぶマルチキャスト経路についてのＤＣＭＡでは、マルチキャストグループ全体のマルチキャスト経路におけるコストなどのパラメータの総和を十分に低減させることはできないということができる。つまり、単一の始点と複数の終点とを結ぶマルチキャスト経路についてのＤＣＭＡでは、コストパフォーマンスのよいマルチキャストグループ全体のマルチキャスト経路を形成できない。
【００１１】
以上の従来技術の問題点に鑑み、本発明の目的は、複数の始点と複数の終点とを結ぶマルチキャスト経路のなかから所定の制約条件のもとで最適なマルチキャスト経路を計算する経路計算方法、経路計算プログラム、経路計算プログラム記憶媒体および経路計算装置を提供するとともに、通信ネットワークにおけるマルチキャスト経路のコストパフォーマンスを向上させることが可能なネットワーク管理装置およびネットワーク経路決定装置を提供することにある。
【課題を解決するための手段】
【００１２】
請求項１に記載の発明は、ノードの集合Ｖとリンクの集合ＥとからなるグラフＧにおいて、所定の制約条件下で所定のパラメータを最適化する経路を、処理部と記憶部とを少なくとも備えたコンピュータにより計算して求める経路計算方法であって、前記コンピュータが、前記リンクの集合Ｅに含まれるリンクに対して第１のパラメータと第２のパラメータとを設定する第１のステップと、前記ノードの集合Ｖに含まれるノードのうち求めるべき経路が必ず通るノードを取り出し、前記取り出したノードにより必通ノード集合Ｒを設定するとともに、前記求めるべき経路上の任意の２つのノード間の経路に含まれるリンクに設定された前記第２のパラメータの和ｄの最大値としてΔを設定する第２のステップと、前記ｄが０＜ｄ≦Δを満たすすべてのｄに対して、前記ノードの集合Ｖに含まれる任意の２つのノードをつなぐ経路のうち、その経路上のリンクに設定された前記第２のパラメータの和がｄであり、その経路上のリンクに設定された前記第１のパラメータの和が最小になる経路を抽出し、その抽出した経路の経路情報と、その抽出した経路に含まれるリンクに設定された前記第１のパラメータの和の値とを前記記憶部に記憶する第３のステップと、前記必通ノード集合Ｒに含まれるすべてのノードにより完全グラフＧ’を生成する第４のステップと、前記必通ノード集合Ｒに含まれるノードを１つ取り出して、前記完全グラフＧ’に含まれる部分グラフＧ”を生成する第５のステップと、前記部分グラフＧ”に含まれるリンクについて、そのリンクの前記グラフＧ上の経路を求めるとともに、前記求められた経路に含まれるリンクの前記第１のパラメータの和および前記第２のパラメータの和を、それぞれ第３のパラメータおよび第４のパラメータとして前記記憶部に記憶する第６のステップと、前記部分グラフＧ”に含まれるノードと、前記部分グラフＧ”に含まれず、前記完全グラフＧ’に含まれるノードとをつなぐ前記完全グラフＧ’上のリンクについて、そのリンクの前記グラフＧ上の経路を求めるとともに、前記求められた経路に含まれるリンクの前記第１のパラメータの和および前記第２のパラメータの和を、それぞれ第５のパラメータおよび第６のパラメータとして前記記憶部に記憶する第７のステップと、前記部分グラフＧ”に含まれるノードと、前記部分グラフＧ”に含まれず、前記完全グラフＧ’に含まれるノードとをつなぐ前記完全グラフＧ’上のリンクのうち、前記第６のパラメータを前記部分グラフＧ”に含まれる任意の２ノード間をつなぐ経路に含まれるリンクの前記第２のパラメータの和の最大値に加算した値が前記Δの値以下であって、前記第５のパラメータの値が最小になるリンクを抽出し、前記抽出されたリンクおよび前記抽出されたリンクの前記部分グラフＧ”に含まれないノードを前記部分グラフＧ”に追加する第８のステップと、前記必通ノード集合Ｒに含まれるノードがすべて前記部分グラフＧ”に含まれるかを判定し、前記必通ノード集合Ｒに含まれるノードであって前記部分グラフＧ”に含まれていないノードがあった場合には、そのノードの１つを取り出し、前記必通ノード集合Ｒに含まれるノードがすべて前記部分グラフＧ”に含まれるまで前記第６のステップないし前記第８のステップを繰り返し実行する第９のステップと、前記部分グラフＧ”に含まれるすべてのリンクによって構成される経路について、その経路に含まれる前記部分グラフＧ”上のリンクを前記グラフＧ上の経路に変換し、前記変換したグラフＧ上の経路にループがあるか否かをチェックし、ループがなかった場合には、前記変換したグラフＧ上の経路を求めるべき経路として抽出する第１０のステップとを実行することを特徴とする経路計算方法である。
【００１３】
請求項２に記載の発明は、請求項１に記載の経路計算方法において、前記コンピュータは、前記グラフＧが通信ネットワークであるとし、前記第１のパラメータには前記通信ネットワークにおけるリンクのコストに係るパラメータを設定し、前記第２のパラメータには前記通信ネットワークにおけるリンクの性能に係るパラメータを設定することを特徴とする経路計算方法である。
【００１４】
請求項１または請求項２に記載の経路計算方法によれば、例えば、第１のパラメータとして通信ネットワークにおけるリンクの使用料金、第２のパラメータとしてリンクの遅延時間などを設定すれば、複数の始点および複数の終点とをつなぐマルチキャスト経路のうち、その経路内の遅延時間が所定の最大時間以内であって、その経路の使用料金を最小にするようなマルチキャスト経路などを計算することができる。
【００１５】
請求項３に記載の発明は、請求項１または請求項２に記載の経路計算方法をコンピュータに実行させるための経路計算プログラムである。また、請求項４に記載の発明は、請求項３に記載の経路計算プログラムをコンピュータ読み取り可能な記憶媒体に記憶した経路計算プログラム記憶媒体である。
【００１６】
請求項５に記載の発明は、処理部と記憶部とを少なくとも備え、ノードの集合Ｖとリンクの集合ＥとからなるグラフＧにおいて、所定の制約条件下で所定のパラメータを最適化する経路を計算して求める経路計算装置であって、前記処理部が、前記リンクの集合Ｅに含まれるリンクに対して第１のパラメータと第２のパラメータとを設定する第１の処理と、前記ノードの集合Ｖに含まれるノードのうち求めるべき経路が必ず通るノードを取り出し、前記取り出したノードにより必通ノード集合Ｒを設定するとともに、前記求めるべき経路上の任意の２つのノード間の経路に含まれるリンクに設定された前記第２のパラメータの和ｄの最大値としてΔを設定する第２の処理と、前記ｄが０＜ｄ≦Δを満たすすべてのｄに対して、前記ノードの集合Ｖに含まれる任意の２つのノードをつなぐ経路のうち、その経路上のリンクに設定された前記第２のパラメータの和がｄであり、その経路上のリンクに設定された前記第１のパラメータの和が最小になる経路を抽出し、その抽出した経路の経路情報と、その抽出した経路に含まれるリンクに設定された前記第１のパラメータの和の値とを前記記憶部に記憶させる第３の処理と、前記必通ノード集合Ｒに含まれるすべてのノードにより完全グラフＧ’を生成する第４の処理と、前記必通ノード集合Ｒに含まれるノードを１つ取り出して、前記完全グラフＧ’に含まれる部分グラフＧ”を生成する第５の処理と、前記部分グラフＧ”に含まれるリンクについて、そのリンクの前記グラフＧ上の経路を求めるとともに、前記求められた経路に含まれるリンクの前記第１のパラメータの和および前記第２のパラメータの和を、それぞれ第３のパラメータおよび第４のパラメータとして前記記憶部に記憶させる第６の処理と、前記部分グラフＧ”に含まれるノードと、前記部分グラフＧ”に含まれず、前記完全グラフＧ’に含まれるノードとをつなぐ前記完全グラフＧ’上のリンクについて、そのリンクの前記グラフＧ上の経路を求めるとともに、前記求められた経路に含まれるリンクの前記第１のパラメータの和および前記第２のパラメータの和を、それぞれ第５のパラメータおよび第６のパラメータとして前記記憶部に記憶させる第７の処理と、前記部分グラフＧ”に含まれるノードと、前記部分グラフＧ”に含まれず、前記完全グラフＧ’に含まれるノードとをつなぐ前記完全グラフＧ’上のリンクのうち、前記第６のパラメータを前記部分グラフＧ”に含まれる任意の２ノード間をつなぐ経路に含まれるリンクの前記第２のパラメータの和の最大値に加算した値が前記Δの値以下であって、前記第５のパラメータの値が最小になるリンクを抽出し、前記抽出されたリンクおよび前記抽出されたリンクの前記部分グラフＧ”に含まれないノードを前記部分グラフＧ”に追加する第８の処理と、前記必通ノード集合Ｒに含まれるノードがすべて前記部分グラフＧ”に含まれるかを判定し、前記必通ノード集合Ｒに含まれるノードであって前記部分グラフＧ”に含まれていないノードがあった場合には、そのノードの１つを取り出し、前記必通ノード集合Ｒに含まれるノードがすべて前記部分グラフＧ”に含まれるまで前記第６の処理ないし前記第８の処理を繰り返し実行する第９の処理と、前記部分グラフＧ”に含まれるすべてのリンクによって構成される経路について、その経路に含まれる前記部分グラフＧ”上のリンクを前記グラフＧ上の経路に変換し、前記変換したグラフＧ上の経路にループがあるか否かをチェックし、ループがなかった場合には、前記変換したグラフＧ上の経路を求めるべき経路として抽出する第１０の処理とを実行することを特徴とする経路計算装置である。
【００１７】
請求項６に記載の発明は、請求項５に記載の経路計算装置において、前記処理部が、前記グラフＧを通信ネットワークであるとし、前記第１のパラメータとして、前記通信ネットワークにおけるリンクのコストに係るパラメータを設定し、前記第２のパラメータとして、前記通信ネットワークにおけるリンクの性能に係るパラメータを設定することを特徴とする経路計算装置である。
【００１８】
請求項７に記載の発明は、請求項６に記載の経路計算装置において、前記処理部が、前記必通ノード集合Ｒを構成するノードとして、マルチキャスト通信経路の始点ノードおよび終点ノードをすべて含むように設定することを特徴とする経路計算装置である。
【００１９】
請求項５ないし請求項７に記載の経路計算装置によれば、例えば、第１のパラメータとして通信ネットワークにおけるリンクの使用料金、第２のパラメータとしてリンクの遅延時間などを設定すれば、その経路計算装置は、複数の始点および複数の終点とをつなぐマルチキャスト経路のうち、その経路内の遅延時間が所定の最大時間以内であって、その経路の使用料金を最小にするようなマルチキャスト経路などを計算することができる。
【００２０】
請求項８に記載の発明は、請求項６または請求項７に記載の経路計算装置を含んで構成されることを特徴とするネットワーク管理装置である。また、請求項９に記載の発明は、請求項６または請求項７に記載の経路計算装置を含んで構成されることを特徴とするネットワーク経路決定装置である。
【００２１】
請求項８に記載のネットワーク管理装置または請求項９に記載のネットワーク経路決定装置によれば、複数の始点および複数の終点とをつなぐマルチキャスト経路として、例えば、その経路内の遅延時間が所定の最大時間以内であって、その経路の使用料金を最小にするように最適化したマルチキャスト経路を設定できるようになる。そのため、通信ネットワークにおけるマルチキャスト経路のコストパフォーマンスを向上させることができる。
【発明の効果】
【００２２】
以上、請求項１ないし請求項７の発明によれば、複数の始点および複数の終点とをつなぐマルチキャスト経路のうち、その経路内に含まれる２つのノードを結ぶリンクの第２のパラメータの和が所定の最大時間以内であって、マルチキャスト経路に含まれるリンクの第１のパラメータの和が最小になるように最適化したマルチキャスト経路を計算することができるようになる。また、通信ネットワークにおける経路計算に適用することによって、コストパフォーマンスのよいマルチキャスト経路を設定することができるようになる。
【００２３】
請求項８または請求項９の発明によれば、通信ネットワークにおいて、最適化したマルチキャスト経路を設定することができるようになるので、マルチキャスト経路のコストパフォーマンスが向上する。
【発明を実施するための最良の形態】
【００２４】
以下、図面を参照して本発明の実施形態について詳しく説明する。
【００２５】
一般に、インターネットなど多数のコンピュータを相互に接続するネットワークは、ルータやスイッチなどネットワークにおける通信経路を決定する経路決定装置と、その経路決定装置相互間を結ぶ通信線路とによって構成される。そして、しばしば、経路決定装置をノード、経路決定装置相互間を結ぶ通信線路をリンクと呼び、そのネットワークをノードとリンクとで構成されたグラフと呼ぶ。
【００２６】
図１は、本発明の実施形態に係る経路決定装置の構成の例を示した図である。図１に示すように、経路決定装置１０は、経路計算装置１、ネットワーク管理装置２、転送装置３を含んで構成される。
【００２７】
経路計算装置１は、処理部１２、記憶部１３、入出力部１１などを含んだいわゆるコンピュータによって構成される。ここで、処理部１２は、複数の始点ノードと複数の終点ノードとを１つにつながった経路として求めたマルチキャスト経路のなかから、所定の制約条件のもとで最適なマルチキャスト経路を求める計算処理を実行する。そして、計算した結果をネットワーク管理装置２に伝える。または、入出力部１１を介して外部装置に伝える。
【００２８】
また、記憶部１３は、前記の最適なマルチキャスト経路を求める計算をするためのプログラムが格納されており、そのプログラムは、例えば、処理部１２が図示しないＣＤ−ＲＯＭなどの可搬型記憶媒体に記憶されたものを読み取って記憶部１３に格納する。また、記憶部１３は、計算対象となるネットワークのリンクおよびノードのデータ、そのリンクに設定される各種パラメータ、さらには、プログラム実行時に必要となる作業用データなどを記憶する。
【００２９】
なお、記憶部１３に記憶される各種パラメータとしては、リンク（通信線路）の使用料金などのようにマルチキャスト経路計算時に最小化または最適化の対象とされるパラメータや、遅延時間などのようにマルチキャスト経路計算時に制約条件として使用されるパラメータなどがある。以下、本明細書では、最小化または最適化の対象となるパラメータをコストパラメータ(請求項では、第１のパラメータ)と呼び、制約条件に使用されるリンクの性能などに係るパラメータを制約パラメータ(請求項では、第２のパラメータ)と呼ぶ。
【００３０】
ネットワーク管理装置２は、処理部２２、記憶部２３、入出力部２１などを含んで構成される。処理部２２は、転送装置３に送られてきたリンクの性能などに係る計測パラメータを読み取り、記憶部２３に記憶する。また、処理部２２は、記憶部２３に記憶した計測パラメータを処理してコストパラメータなどに変換し、適宜、経路計算装置１へ転送する。また、処理部２２は、経路計算装置１が計算したマルチキャスト経路計算の計算結果を受け取り、経路情報の一部として記憶部２３に記憶する。
【００３１】
なお、ネットワーク管理装置２は、経路計算装置１と同様にいわゆるコンピュータを主要構成要素として構成することができ、この場合には、経路計算装置１の機能をネットワーク管理装置２に含むように構成しても構わない。
【００３２】
転送装置３は、通信部３１、処理部３２、記憶部３３などを含んで構成される。通信部３１は、１以上の信号用媒体（通信線路）とのインタフェースを備え、信号の変復調や符号・復号などの処理を行う。処理部３２は、通信部３１で処理された通信データに係る通信プロトコルの処理を行い、その情報を記憶部３３のデータバッファや転送先情報などの記憶領域になどにバッファリングする。また、転送装置３は、他の経路決定装置１０などとの間で、適宜、ネットワーク計測パラメータやマルチキャスト経路計算結果などの情報のやり取りを行う。
【００３３】
なお、以上の経路決定装置１０の構成は、最大機能の構成を示したものであり、所定のネットワークにおける経路決定装置１０のすべてが、経路計算装置１を含む必要はない。また、経路計算装置１は、経路決定装置１０に含まれず、独立した装置であってもよい。
【００３４】
続いて、図２〜図４を参照して、経路計算装置１における所定の制約条件のもとで最適なマルチキャスト経路を求める計算の処理の流れについて説明する。ここで、図２は、所定の制約条件のもとで最適なマルチキャスト経路を求める計算処理の流れの概要を示した図、図３は、制約パラメータの和がｄとなるような経路のうちコストパラメータの和が最小となる経路を求める処理の流れを詳しく示した図、図４は、必通ノード集合の完全グラフ上ですべての必通ノードをつなぐ経路のうち制約パラメータの制約条件を満たしつつコストパラメータの和が最小となる経路を求める処理の流れを詳しく示した図である。
【００３５】
最適なマルチキャスト経路を求める経路計算を行うにあたって、まず、経路計算の対象となるネットワークＧを設定する。ここで、ネットワークＧは、ノードの集合Ｖとリンクの集合Ｅとからなるものとし、リンクの集合Ｅに含まれるリンクｅには、コストパラメータＣ(ｅ)と制約パラメータＤ(ｅ)とが設定されている。ここで、コストパラメータＣ(ｅ)は、リンクｅに割り当てられた回線の使用料金であり、制約パラメータＤ(ｅ)は、リンクｅで生じる信号の遅延時間とする。ただし、コストパラメータＣ(ｅ)および制約パラメータＤ(ｅ)としては、これらのパラメータに限定されることなく、他のパラメータであっても構わない。
【００３６】
そこで、図２において、経路計算装置１の処理部１２は、まず、ノードの集合Ｖとリンクの集合ＥとからなるネットワークＧのリンクの集合Ｅに含まれるリンクｅに対してコストパラメータＣ(ｅ)と制約パラメータＤ(ｅ)とを設定し（ステップＳ１）、設定したパラメータを記憶部１３に記憶する。
【００３７】
次に、処理部１２は、ノード集合Ｖの部分集合として必通ノード集合Ｒを設定し、求めるべき経路の制約パラメータの最大値としてΔを設定する（ステップＳ２）。設定された必通ノード集合Ｒの情報および制約パラメータの最大値Δの情報は、記憶部１３に記憶される。ここで、必通ノード集合とは、求めるべき経路が必ず通るノードのことで、マルチキャスト経路計算の場合には、マルチキャスト経路の始点または終点となるノードは、必通ノード集合のノードとなる。また、ネットワークのトポロジカルな形状のため、どうしても通過せざるを得ないノードがあれば、そのノードも必通ノード集合に入れてもよい。
【００３８】
次に、処理部１２は、０＜ｄ≦Δであるようなすべてのｄに対して、制約パラメータの経路上の和がｄとなるような２つのノード（ｖ，ｗ）（ｖ，ｗ∈Ｖ）をつなぐ経路のうち、コストパラメータの和が最小となる経路を抽出し、その経路情報およびコストパラメータの値を記憶部１３に記憶する（ステップＳ３）。なお、このステップＳ３の詳細については、別途、図４を参照して説明する。
【００３９】
次に、処理部１２は、必通ノード集合Ｒのすべてのノードにより完全グラフＧ’を生成し、そのリンクの集合をＥ’とする（ステップＳ４）。ここで、完全グラフとは、すべての２つのノードの間にリンクが存在するグラフをいう。さらに、処理部１２は、必通ノード集合Ｒに含まれるノードを１つ取り出し、完全グラフＧ’に含まれる部分グラフＧ”を生成する（ステップＳ５）。
【００４０】
次に、処理部１２は、部分グラフＧ”に含まれるノードと部分グラフＧ”に含まれない完全グラフＧ’のノードとをつなぐリンクのうち、所定の制約パラメータの条件を満足し、かつ、コストパラメータが最小となるリンクを選択し、選択したリンクおよびノード（部分グラフＧ”に含まれないノード）を部分グラフＧ”に追加する（ステップＳ６）。なお、このステップＳ６の詳細については、別途、図５を参照して説明する。
【００４１】
次に、処理部１２は、必通ノード集合Ｒに含まれるノードがすべて部分グラフＧ”に含まれるかを判定する（ステップＳ７）。すなわち、必通ノード集合Ｒに含まれるノードをすべてつないだ経路が形成されたかを判定する。その判定の結果、必通ノード集合Ｒに含まれるノードがすべて部分グラフＧ”に含まれていない場合には（ステップＳ７でＮｏ）、その部分グラフＧ”に含まれていないノードの１つを取り出し、ステップＳ５を繰り返して実行する。
【００４２】
また、必通ノード集合Ｒに含まれるノードがすべて部分グラフＧ”に含まれていた場合には（ステップＳ７でＹｅｓ）、求めるべき完全グラフＧ’上の経路が部分グラフＧ”のリンクとして求められたことになる。なお、このようにして求められた完全グラフＧ’の経路は、しばしば、完全グラフＧ’の最小木と呼ばれる。
【００４３】
次に、処理部１２は、完全グラフＧ’上での最小木の経路として求められた完全グラフＧ’上のリンクを対応するグラフＧ上の経路に変換する（ステップＳ８）。この変換時に、グラフＧ上の経路の選択の仕方によってはループが形成されることがあるので、求められたグラフＧ上の経路についてループの有無をチェックし（ステップＳ９）、ループがあった場合には、ループとなる部分を検出して除去する。以上のようにして得られたグラフＧ上の経路が求めるべき最適なマルチキャスト経路となる。
【００４４】
次に、図３を参照して、ステップＳ３の詳細な処理の流れについて説明する。なお、ステップＳ３を処理するにあたっては、コストパラメータＣ(ｅ)、制約パラメータＤ(ｅ)および制約パラメータの最大値Δは、経路計算装置１の記憶部１３に記憶されている状態にある。
【００４５】
ここで、ノード集合Ｖに含まれる２つのノードをｖ，ｗとしたとき、コストパラメータＣ(ｅ)および制約パラメータＤ(ｅ)は、それぞれ、Ｃ(ｖ，ｗ)、Ｄ(ｖ，ｗ)と表記され、記憶部１３には、２次元のテーブルとして記憶される。この場合、２つのノードｖとｗとが直接リンクで接続されていない場合は、その値は、存在しないもの（空欄）とする。
【００４６】
また、ｄを、式０＜ｄ≦Δを満足する離散的な数とする。例えば、制約パラメータがリンクの遅延時間を表わす場合には、ｄは、例えば、ｍ秒単位の整数を表わすものとすることができる。この場合には、制約パラメータＤ(ｅ)および制約パラメータの最大値Δも同様にｍ秒単位の整数で表わされているものとする。
【００４７】
最初に、処理部１２は、０＜ｄ≦Δおよびｖ，ｗ∈Ｖを満たすすべてのｄ，ｖ，ｗの組み合わせについて、Ｃ’(ｄ，ｖ，ｗ)＝０とする（ステップＳ３１）。ここで、Ｃ’(ｄ，ｖ，ｗ)は、記憶部１３に記憶される３次元のテーブルである。
【００４８】
続いて、処理部１２は、ｄの初期値として、ｄにＤ(ｖ，ｗ)（ｖ，ｗ∈Ｖ）の最小値を代入する（ステップＳ３２）。そして、ノード集合Ｖから２つのノードｖ，ｗ（ｖ≠ｗ）を選択する（ステップＳ３３）。
【００４９】
次に、処理部１２は、ノードｗと直接にリンクで接続されているすべてのノードｕに対して、
Ｃ’(ｄ，ｖ，ｗ)＝ｍｉｎ[Ｃ’(ｄ−Ｄ(ｕ，ｗ)，ｖ，ｕ)＋Ｃ(ｕ，ｗ)]
を計算し、その値およびそのときのノードｕを経路情報として記憶部１３に記憶する（ステップＳ３４）。ここで、Ｃ’(ｄ−Ｄ(ｕ，ｗ)，ｖ，ｗ)は、ｖとｕとを結ぶ任意のリンクのうち、経路が通るリンクの制約パラメータの総和がｄ−Ｄ(ｕ，ｗ)であり、かつ、コストパラメータの総和が最小となる経路のコストパラメータの総和である。
【００５０】
次に、処理部１２は、ノード集合Ｖに属するノードのすべての組み合わせのｖ，ｗを選択したか否かを判定する（ステップＳ３５）。そして、その判定の結果、すべての組み合わせのｖ，ｗを選択していない場合には（ステップＳ３５でＮｏ）、処理部１２は、ステップＳ３３およびステップＳ３４を繰り返し実行する。
【００５１】
また、すべての組み合わせのｖ，ｗを選択した場合には（ステップＳ３５でＹｅｓ）、処理部１２は、２ノード間を結ぶ経路が通るリンクの制約パラメータの総和がとり得る値のうち、現在のｄの次に小さい値をｄとする（ステップＳ３６）。そして、その新たなｄが、ｄ≦Δであるかを判定する（ステップＳ３７）。その判定の結果、ｄ≦Δであった場合には（ステップＳ３７でＹｅｓ）、処理部１２は、ステップＳ３３〜ステップＳ３６を繰り返し実行する。また、ｄ≦Δでなかった場合には（ステップＳ３７でＮｏ）、処理を終了する。
【００５２】
以上のようにして、３次元テーブルのデータとして、Ｃ’(ｄ，ｖ，ｗ)を得ることができる。
【００５３】
次に、図４を参照して、ステップＳ６の詳細な処理の流れについて説明する。この図４に示す処理の流れは、完全グラフＧ’におけるいわゆる最小木を探索する処理に相当している。なお、ステップＳ６を処理するにあたっては、必通ノード集合Ｒに含まれるノードによって完全グラフＧ’が形成され、さらに、そのノードの１つが選択され、選択されたノードにより完全グラフＧ’の部分グラフＧ”が形成された状態にある。ただし、この時点では、部分グラフＧ”は、１つのノードを有するだけで、リンクはまだ有していない。
【００５４】
ここで、必通ノード集合Ｒに含まれるノードをｓ，ｔとしたとき、記憶部１３に以下のステップで計算するＤ’(ｓ，ｔ)およびＤmax(ｓ)を記憶する領域を確保する。そして、処理部１２は、ステップＳ５（図２参照）で必通ノード集合Ｒから取り出されたノードをノードｓ’とし、
Ｄ’(ｓ’，ｓ’)＝０，  Ｄmax(ｓ’)＝０
とする（ステップＳ６０）。
【００５５】
なお、このステップＳ６０は、ステップＳ７（図２、図４参照）からの戻り先から判断すれば、図２に示した処理の流れににおいてはステップＳ５に含まれるとするほうが正しい。しかしながら、このステップの処理は、ステップＳ６１〜ステップＳ６６を実行するための初期化の処理なので、ステップＳ６の処理の一部として説明したものである。
【００５６】
次に、処理部１２は、完全グラフＧ’において、部分グラフＧ”に含まれるノードを
ｓ’とし、部分グラフＧ”に含まれないノードをｔとしたとき、ノードｓ’に対して、
Ｃ’(Δ―Ｄmax(ｓ’)，ｓ’，ｔ)
が最小となるノードｔ’を求める（ステップＳ６１）。そして、完全グラフＧ’上のリンク(ｓ’，ｔ’)に対応するグラフＧ上の経路をノードｓ’，ｔ’間の経路とする（ステップＳ６２）。
【００５７】
次に、処理部１２は、パラメータＣG'(ｓ’，ｔ’)、ＤG'(ｓ’，ｔ’)を次の式
ＣG'(ｓ’，ｔ’)＝Ｃ’(Δ―Ｄmax(ｓ’)，ｓ’，ｔ’)
ＤG'(ｓ’，ｔ’)＝グラフＧ上に含まれるリンクｅ”に割り当てられた
Ｄ(ｅ”)の総和
により計算する（ステップＳ６３）。
【００５８】
次に、処理部１２は、ノードｓ’，ｔ’を結ぶリンク(ｓ’，ｔ’)の中で、パラメータＣG'(ｓ’，ｔ’)が最小となるリンク(ｓ”，ｔ”)を選択し、選択したリンク(ｓ”，ｔ”)を部分グラフＧ”に追加する（ステップＳ６４）。すなわち、部分グラフＧ”には、ノードｔ”とリンク(ｓ”，ｔ”)とが追加される。
【００５９】
次に、処理部１２は、リンク(ｓ”，ｔ”)を追加する前の部分グラフＧ”に含まれるノードｕに対して、
Ｄ’(ｕ，ｔ”)＝Ｄ’(ｕ，ｓ”)＋ＤG'(ｓ”，ｔ”)
Ｄ’(ｔ”，ｕ)＝ＤG'(ｔ”，ｓ”)＋ＤG'(ｓ”，ｕ)
を計算する（ステップＳ６５）。さらに、リンク(ｓ”，ｔ”)を追加した後の部分グラフＧ”に含まれるノードｕ’に対して、
Ｄmax(ｕ’)＝ｍａｘＤG'(ｕ’，ｔ)  （ｔ∈Ｇ”）
を計算する（ステップＳ６６）。
【００６０】
そして、処理部１２は、必通ノード集合Ｒに含まれるノードがすべて部分グラフＧ”に含まれるかを判定する（ステップＳ７：このステップは、図２のステップＳ７と同じステップ）。すなわち、必通ノード集合Ｒに含まれるノードをすべてつないだ経路が形成されたかを判定する。その判定の結果、必通ノード集合Ｒに含まれるノードがすべて部分グラフＧ”に含まれていない場合には（ステップＳ７でＮｏ）、その部分グラフＧ”に含まれていないノードの１つを取り出して、ステップＳ６１へ戻り、ステップＳ６１〜ステップＳ６６の処理を繰り返して実行する。
【００６１】
また、必通ノード集合Ｒに含まれるノードがすべて部分グラフＧ”に含まれていた場合には（ステップＳ７でＹｅｓ）、求めるべき完全グラフＧ’の経路が部分グラフＧ”のリンク、すなわち、最小木として求められたことになる。
【００６２】
以上に示したように、経路計算装置１は、図２〜図４に示した処理を実行することによって、複数の始点と複数の終点があった場合にも、制約パラメータｄが０＜ｄ≦Δの条件を満足しつつ、経路上のリンクのコストパラメータの和を最小化するようなマルチキャスト経路を求めることができる。従って、このようにして、マルチキャスト経路に係るコストパラメータ和を最小化することができるので、マルチキャスト経路のコストパフォーマンスを向上させることができる。
【００６３】
続いて、図５〜図１４を参照して、経路計算装置１において行われるマルチキャスト経路計算の処理を具体的なネットワークに基づいて説明する。
【００６４】
図５は、ネットワークＧの具体例を示した図である。図５に示すように、ネットワークＧは、ノードの集合[１，２，３，ａ，ｂ，ｃ，ｄ]と、図示されたようなリンクの集合とを有するグラフである。また、ノード１，２，３を、始点および終点となるノードであるとし、ノードの集合[１，２，３]を必通ノード集合とする。また、各リンクには、制約パラメータＤ(ｅ)とコストパラメータＣ(ｅ)が付されており、その値は、図では実線、破線、一点鎖線の違いによって区別されている。そして、制約パラメータの総和の最大値Δとしてここでは４を設定している。
【００６５】
図６は、送信元からあて先への経路のうち、コストパラメータが最小になる経路の計算の具体例を示したものである。図２のステップＳ３で説明したように、ステップＳ３では記憶部１３に３次元のテーブルが作成される。図６に示したテーブルは、その例を示したもので、そのテーブルの各欄には、α1，α2，α3の情報が格納される。ここで、α1は、あて先の１つ手前のノード、α2は、あて先の１つ手前のノードとあて先とを結ぶリンクの制約パラメータの値、α3は、送信元からあて先までの経路に含まれるリンクのコストパラメータの和であることを示している。なお、図２のステップＳ３での表記に従えば、α3は、Ｃ’(ｄ，ｖ，ｗ)＝ｍｉｎ[Ｃ’(ｄ−Ｄ(ｕ，ｗ)，ｖ，ｕ)＋Ｃ(ｕ，ｖ)]の式の値であり、α1は、この式が成立するときのｕの値であり、α2は、Ｄ(ｕ，ｗ)の値である。
【００６６】
図６においては、Ｃ’(ｄ，ｖ，ｗ)に対応するテーブルは、ｄ＝１およびｄ＝２についてしか示されていないが、実際には、０＜ｄ≦Δの範囲で、ｄがとり得る値すべてについて作成する必要がある。従って、本例の場合は、ｄ＝３およびｄ＝４についても作成する必要がある。
【００６７】
図７は、図６に示したテーブルに基づき、経路探索を行う例を示した図である。ここでは、ノード１からノード３までを結び、制約パラメータが２であり、コストパラメータが最小となる経路を探索する。この場合、まず、ｄ＝２のテーブルを参照し、さらに、送信元＝１、あて先＝３の欄を参照する。すると、あて先の１つ手前のノードがｄ，ノードｄからあて先までの制約パラメータが１，送信元からあて先の経路に含まれるコストパラメータの和が２という情報が得られる。次に、ｄ＝１のテーブル、送信元がリンクｄの欄を参照すると、あて先が１の欄には手前のノードが１という情報があるので、これによって、求めるべき送信元からあて先までの経路は、１→ｄ→３であることが分かる。
【００６８】
図８は、図５に示したネットワークの例に基づき、必通ノード集合に含まれるノードにより完全グラフＧ’を作成し、パラメータの初期化を行った例を示したものである。本例の場合、必通ノード集合Ｒは、[１，２，３]である。従って、そのノードによる完全グラフＧ’は、これらのノードを直接結ぶリンク(１，２)、(２，３)、(３，１)を有している。そして、必通ノード集合Ｒの１つのノードｓ’を取り出し、ステップＳ５のパラメータの初期化処理を行う。本例の場合、ｓ’＝１であり、部分グラフＧ”は、ノード１だけを含むグラフである。図８には、パラメータの初期化後のそれぞれのノードにおけるパラメータの値が示されている。
【００６９】
図９〜図１２は、図４の処理の流れに従って、完全グラフＧ’の最小木を探索するときの経路選択の例を示した図である。図９では、まず、ステップＳ６１に従い、部分グラフＧ”に含まれないノードｔ（本例のこのステップでは、ｔは、２および３となる）に対して、Ｃ’(４―Ｄmax(１)，１，ｔ)を計算し、Ｃ’(４，１，２)＝３、Ｃ’(４，１，３)＝２を得る。その結果、コストパラメータの総和は、後者が小さいので、経路として、ノード１→ノード３を選択する。そして、部分グラフＧ”にノード３とリンク（１，３）とを加える。
【００７０】
次に、図１０では、ステップＳ６５およびステップＳ６６に従って、部分グラフＧ”上での制約パラメータを計算する。本例では、図１０に示されているように、ノード１に対して、Ｄ’(１，３)＝２、Ｄmax(１)＝２が、また、ノード３に対して、Ｄ’(３，１)＝２、Ｄmax(３)＝２が計算される。
【００７１】
次に、図１１では、ｓ’＝１、ｔ＝２、および、ｓ’＝３、ｔ＝２として、それぞれ、Ｃ’(２，１，２)を計算する。その結果、図１１に示しているように、ｓ’＝１、ｔ＝２のとき、Ｃ’(２，１，２)＝φとなり、ｓ’＝３、ｔ＝２のとき、Ｃ’(２，１，２)＝２となる。そこで、リンク（３，２）を選択し、ノード２とリンク（３，２）とを部分グラフＧ”に加える。
【００７２】
さらに、図１２では、再度、ステップＳ６５およびステップＳ６６に従って、部分グラフＧ”上での制約パラメータを計算する。本例では、図１２に示されているように、ノード１に対して、Ｄ(１，２)＝４、Ｄmax(１)＝４が、ノード３に対して、Ｄ’(３，２)＝２、Ｄmax(３)＝２が、また、ノード２に対して、Ｄ’(２，１)＝４、Ｄ’(２，３)＝２、Ｄmax(２)＝４が計算される。
【００７３】
以上のようにして、部分グラフＧ”は、必通ノード集合Ｒのノードをすべて含むこととなったので、完全グラフＧ’上での最小木が求められたことになる。この場合、最小木が示す経路は、ノード１−ノード３−ノード２の経路である。
【００７４】
そこで、図１３に示すように、完全グラフＧ’上での最小木の経路として求められた完全グラフＧ’上のリンクを対応するグラフＧ上の経路に変換する（ステップＳ８参照）。本例では、完全グラフＧ’上のリンク(１，３)は、ネットワークＧ上の経路(１−ｄ−３)に対応し、完全グラフＧ’上のリンク(２，３)は、ネットワークＧ上の経路(２−３)に対応する。よって、ネットワークＧ上でのマルチキャスト経路には、経路１−ｄ−３−２が選ばれたことになる。
【００７５】
さらに、図１４に示すように、このマルチキャスト経路１−ｄ−３−２にループがないかをチェックして、ループがない場合にマルチキャスト経路１−ｄ−３−２を最終的なマルチキャスト経路とする。
【００７６】
以上のようにして求めたマルチキャスト経路１−ｄ−３−２における制約パラメータの和は４であり、コストパラメータの和は３となっている。このようにして、制約パラメータｄが０＜ｄ≦４の条件を満足しつつ、経路上のリンクのコストパラメータの和が最小となるマルチキャスト経路を求めることが、マルチキャスト経路の最適化を図ることができる。
【図面の簡単な説明】
【００７７】
【図１】本発明の実施形態に係る経路決定装置の構成の例を示した図である。
【図２】本発明の実施形態において所定の制約条件のもとで最適なマルチキャスト経路を求める計算処理の流れの概要を示した図である。
【図３】本発明の実施形態において制約パラメータの和がｄとなるような経路のうちコストパラメータの和が最小となる経路を求める処理の流れを詳しく示した図である。
【図４】本発明の実施形態において必通ノード集合の完全グラフ上ですべての必通ノードをつなぐ経路のうち制約パラメータの制約条件を満たしつつコストパラメータの和が最小となる経路を求める処理の流れを詳しく示した図である。
【図５】本発明の実施形態における処理の流れを説明するためのネットワークＧの具体例を示した図である。
【図６】図２のステップＳ３の処理において、送信元からあて先への経路のうち、コストパラメータが最小になる経路の計算の具体例を示したものである。
【図７】図６に示したテーブルに基づき、経路探索を行う例を示した図である。
【図８】図５に示したネットワークの例に基づき、必通ノード集合に含まれるノードにより完全グラフＧ’を作成し、パラメータの初期化を行った例を示したものである。
【図９】図４の処理の流れに従って、完全グラフＧ’の最小木を探索するときの経路選択の例を示した図である。
【図１０】図４の処理の流れに従って、完全グラフＧ’の最小木を探索するときの経路選択の例を示した図である。
【図１１】図４の処理の流れに従って、完全グラフＧ’の最小木を探索するときの経路選択の例を示した図である。
【図１２】図４の処理の流れに従って、完全グラフＧ’の最小木を探索するときの経路選択の例を示した図である。
【図１３】図２のステップＳ８において、完全グラフＧ’上での最小木の経路として求められた完全グラフＧ’上のリンクを対応するグラフＧ上の経路に変換する例を示した図である。
【図１４】図２のステップＳ９において、求められたマルチキャスト経路にループがないかをチェックして、ループがない場合にマルチキャスト経路１−ｄ−３−２を最終的なマルチキャスト経路とする例を示した図である。
【符号の説明】
【００７８】
１      経路計算装置
２      ネットワーク管理装置
３      転送装置
１０    経路決定装置
１１    入出力部
１２    処理部
１３    記憶部
２１    入出力部
２２    処理部
２３    記憶部
３１    通信部
３２    処理部
３３    記憶部
【図１】
2006222875.tif 000003
【図２】
2006222875.tif 000004
【図３】
2006222875.tif 000005
【図４】
2006222875.tif 000006
【図５】
2006222875.tif 000007
【図６】
2006222875.tif 000008
【図７】
2006222875.tif 000009
【図８】
2006222875.tif 000010
【図９】
2006222875.tif 000011
【図１０】
2006222875.tif 000012
【図１１】
2006222875.tif 000013
【図１２】
2006222875.tif 000014
【図１３】
2006222875.tif 000015
【図１４】
2006222875.tif 000016