経路計算方法、経路計算装置およびプログラム
【課題】マルチキャスト経路の合計コストと経路探索の計算量を抑えることを可能にした経路計算方法を提供する。
【解決手段】複数の受信ノードの経路計算の順位を決め、最上位から最下位の受信ノードまで順に第１の探索ノードに設定し、第１の探索ノード毎に隣接ノードまでの経路の合計コストを算出し、合計コストが最小となる隣接ノードを第２の探索ノードとし、第２の探索ノードが送信ノード、または上記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致するまで、合計コストが最小となる隣接ノードを第２の探索ノードに更新することで第１の探索ノードから第２の探索ノードを順に結ぶ経路を設定し、第２の探索ノードの隣接ノードの合計コストを算出する際、第２の探索ノードが受信ノードと一致する場合、第２の探索ノードまでの合計コストをゼロにリセットし、第２の探索ノードを起点とする経路のコストを合計コストとする。
【解決手段】複数の受信ノードの経路計算の順位を決め、最上位から最下位の受信ノードまで順に第１の探索ノードに設定し、第１の探索ノード毎に隣接ノードまでの経路の合計コストを算出し、合計コストが最小となる隣接ノードを第２の探索ノードとし、第２の探索ノードが送信ノード、または上記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致するまで、合計コストが最小となる隣接ノードを第２の探索ノードに更新することで第１の探索ノードから第２の探索ノードを順に結ぶ経路を設定し、第２の探索ノードの隣接ノードの合計コストを算出する際、第２の探索ノードが受信ノードと一致する場合、第２の探索ノードまでの合計コストをゼロにリセットし、第２の探索ノードを起点とする経路のコストを合計コストとする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチキャスト通信において、最適な経路を選択するために、ネットワークのリンクに距離や帯域などに関連したコスト値を与え、その合計が最小となるマルチキャスト経路を計算する経路計算方法、経路計算装置、およびコンピュータに実行させるためのプログラムに関する。
【背景技術】
【０００２】
近年、デジタル映像配信やグループビデオ会議など、マルチキャスト通信の需要が高まっている。このようなアプリケーションは、データサイズが大きいため、大量のトラフィックがネットワーク上を流れることになる。したがって、ネットワーク管理者は、アプリケーションが満たすべき品質や、データ量に応じて、マルチキャスト経路を決定し、管理する必要がある。リング型やスター型といった、シンプルなネットワークでは、マルチキャスト経路は一意に決まり、ネットワーク管理者は、経路の管理を容易に行うことができる。しかし、近年、ネットワークは複雑化しており、最適な経路を決定するためには、適したマルチキャスト経路計算アルゴリズムが必要である。最適なマルチキャスト経路の決定方法として、ネットワークのリンクにコスト値を与え、マルチキャスト経路全体の合計コストを最小化する方法がある。
【０００３】
合計コストが最小となるマルチキャスト経路を求める問題は、最小シュタイナーツリー問題として、古くから解かれているが、ＮＰ（Nondeterministic Polynomial）完全問題であることが知られており、実時間で最適解を見つけることは困難である。
【０００４】
近似解を求める手法として、非特許文献１には、送信ノードと受信ノードそれぞれを結ぶフルメッシュの最短路ネットワークを求め、求めたネットワークにおいて、最小全域木を求めることで、低コストマルチキャスト経路を計算する方法が開示されている。
【０００５】
また、非特許文献２には、送信ノードからダイクストラ法による最短経路計算を行い、経路探索中に受信ノードが発見されると、その受信ノードを経由して、他の受信ノードに向かう経路を優先的に選択することにより、一経路上に複数の受信ノードを乗せることで、低コストマルチキャスト経路を計算する方法が開示されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Kou. L., G. Markowsky, and L. Berman, "A fast algorithm for Steiner trees," IBM Thomas J Watson Research Center, Acta Information 15, pp.141-145, 1981.
【非特許文献２】A. Shaikh and K. Shin, "Destination-driven routing for low-cost multicast," IEEE Journal on Selected Areas in Communications, vol.15, No.3, April 1997.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１に開示された方法では、コストを低く抑えることが可能だが、送信ノードと受信ノードの全ての組み合わせのフルメッシュ経路を計算する必要があり、計算量が多くなってしまう。一方、非特許文献２に開示された方法では、計算量は少ないが、コストは非特許文献１より大きくなる傾向がある。
【０００８】
本発明は上述したような技術が有する問題点を解決するためになされたものであり、マルチキャスト経路の合計コストと経路探索の計算量を抑えることを可能にした経路計算方法、経路計算装置、およびコンピュータに実行させるためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するための本発明の経路計算方法は、
ネットワーク内の各ノードに対応する識別子、隣接するノード同士を接続する経路および各経路のコスト値の情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードのそれぞれの識別子の情報を取得し、
前記複数の受信ノードについて経路計算の順位を決め、
決定した順位の最上位の受信ノードから最下位の受信ノードまで順に第１の探索ノードに設定し、
設定した第１の探索ノード毎に、該第１の探索ノードの隣接ノードについて、該第１の探索ノードと該隣接ノードの間のコスト値を合計コストとし、該合計コストが最小となる隣接ノードを第２の探索ノードとし、該第２の探索ノードが前記送信ノード、または該第１の探索ノードよりも前記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致するまで、前記第１の探索ノードから該第２の探索ノードを経由して該第２の探索ノードの隣接ノードまでの前記合計コストが最小となる隣接ノードを第２の探索ノードに順次更新することで、前記第１の探索ノードから更新された第２の探索ノードを順に結ぶ経路を設定し、
前記第２の探索ノードについて前記隣接ノードの前記合計コストを算出する際、該第２の探索ノードが前記複数の受信ノードのうち、いずれかの受信ノードと一致する場合、該第２の探索ノードまでの前記合計コストをゼロにリセットし、該第２の探索ノードを起点とする経路のコスト値を前記合計コストとするものである。
【００１０】
また、本発明の経路計算装置は、
ネットワーク内の各ノードに対応する識別子、隣接するノード同士を接続する経路および各経路のコスト値の情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードのそれぞれの識別子の情報を保存する記憶手段と、
前記要求取得手段から受け取る前記複数の受信ノードについて経路計算の順位を決める計算順序決定手段と、
前記計算順序決定手段が決定した順位の最上位の受信ノードから最下位の受信ノードまで順に第１の探索ノードに設定し、設定した第１の探索ノード毎に、該第１の探索ノードの隣接ノードについて、該第１の探索ノードと該隣接ノードの間のコスト値を合計コストとし、該合計コストが最小となる隣接ノードを第２の探索ノードとし、前記第１の探索ノードから該第２の探索ノードを経由して該第２の探索ノードの隣接ノードまでの前記合計コストが最小となる隣接ノードを第２の探索ノードに順次更新する経路パラメータ計算手段と、
前記第２の探索ノードが前記送信ノード、または該第１の探索ノードよりも前記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致すると、前記第１の探索ノードから更新された第２の探索ノードを順に結ぶ経路を設定する経路パラメータ判定手段と、を有し、
前記経路パラメータ計算手段は、
前記第２の探索ノードについて前記隣接ノードの前記合計コストを算出する際、該第２の探索ノードが前記複数の受信ノードのうち、いずれかの受信ノードと一致する場合、該第２の探索ノードまでの前記合計コストをゼロにリセットし、該第２の探索ノードを起点とする経路のコスト値を前記合計コストとする構成である。
【００１１】
さらに、本発明のプログラムは、上記本発明の経路計算方法をコンピュータに実行させるものである。
【発明の効果】
【００１２】
本発明によれば、マルチキャスト通信を行う際、経路探索の計算量を抑制し、経路全体の合計コストを抑制できる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態におけるマルチキャスト経路計算装置の一構成例を示すブロック図である。
【図２】本発明の一実施形態におけるマルチキャスト経路計算方法の手順を示すフローチャートである。
【図３】第１の実施形態におけるマルチキャスト経路計算装置の一構成例を示すブロック図である。
【図４】第１の実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
【図５】第１の実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
【図６】第１の実施形態におけるマルチキャスト経路計算方法を具体的に説明するためのネットワークトポロジの一構成例を示す図である。
【図７Ａ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図７Ｂ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図７Ｃ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図７Ｄ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図８Ａ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図８Ｂ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図８Ｃ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図８Ｄ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図９Ａ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図９Ｂ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１０】第２の実施形態におけるマルチキャスト経路計算装置の一構成例を示すブロック図である。
【図１１】第２の実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
【図１２】第２の実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
【図１３Ａ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１３Ｂ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１３Ｃ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１３Ｄ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１４Ａ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１４Ｂ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１４Ｃ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１４Ｄ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１５Ａ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１５Ｂ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【発明を実施するための形態】
【００１４】
本発明のマルチキャスト経路計算装置は、ネットワークのリンクに距離や帯域などと関連付けられたコスト値を与え、コスト値の合計が最小となるマルチキャスト経路を計算する装置である。
【００１５】
本発明の一実施形態のマルチキャスト経路計算装置の構成を説明する。図１は本発明の一実施形態におけるマルチキャスト経路計算装置の一構成例を示すブロック図である。
【００１６】
マルチキャスト経路計算装置１００は、要求取得手段１と、計算順序決定手段２と、計算受信ノード決定手段３と、探索ノード決定手段４と、経路パラメータ計算手段５と、経路パラメータ判定手段６と、経路保存手段７と、経路出力手段８とを有する。また、マルチキャスト経路計算装置１００は、マルチキャスト経路を計算する過程で情報を保存し、また、計算結果を保存するための記憶手段を備えている。記憶手段は、経路記憶手段１１と、訪問済みノード記憶手段１２と、ノード情報記憶手段１３とを有する。
【００１７】
次に、図１に示したマルチキャスト経路計算装置１００による経路計算方法の動作を説明する。図２は本発明の一実施形態におけるマルチキャスト経路計算方法の手順を示すフローチャートである。
【００１８】
要求取得手段１が、ネットワーク内の各ノードの接続関係を表した情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードの識別子を受け付けると（ステップ１０１）、送信ノードの識別子を経路記憶手段１１に格納する。続いて、計算順序決定手段２が、受信ノードの経路計算の順序である計算順序を決定する（ステップ１０２）。計算受信ノード決定手段３が、経路記憶手段１１に格納されていない受信ノードの中で、計算順序最上位の受信ノードを決定する（ステップ１０３）。
【００１９】
次に、探索ノード決定手段４が、訪問済みノード記憶手段１２を参照し、経路計算が済んだノードである訪問済みノードが訪問済みノード記憶手段１２に保存されていない場合、ステップ１０３で決定された受信ノードを探索ノードとして決定する。一方、訪問済みノードが訪問済みノード記憶手段１２に保存されている場合、まだ経路計算が済んでいない（訪問済みとなっていない）ノードの中から、ノード情報記憶手段１３を参照して、合計コストが最小のノードを探索ノードとして決定し、探索ノードを訪問済みノード記憶手段１２に格納する（ステップ１０４）。
【００２０】
続いて、経路パラメータ計算手段５が、ステップ１０４で決定された探索ノードの隣接ノードについて、探索ノード経由の経路における合計コストを計算する（ステップ１０５）。その際、探索ノードが受信ノードである場合、経路パラメータ計算手段５は、探索ノードまでの合計コストをゼロにリセットし、探索ノードと隣接ノードとの間のコスト値を新たな合計コストとする。ステップ１０５で算出される合計コストを第１の合計コストと称する。なお、本実施形態では、ステップ１０５において、探索ノードが受信ノードであると、探索ノードまでの合計コストをゼロにリセットする場合で説明するが、その合計コストをゼロにリセットしなくてもよい。
【００２１】
経路パラメータ判定手段６は、隣接ノードについて、ノード情報記憶手段１３を参照し、合計コストが保存されていない場合、または、他のノード経由の経路で既に計算された合計コストである第２の合計コストが保存されているが、第1の合計コストの方が小さい場合（ステップ１０６）、第１の合計コストおよび上記探索ノード経由の経路を、ノード情報記憶手段１３に格納する（ステップ１０７）。第２の合計コストの方が第１の合計コストよりも小さい場合には、経路パラメータ判定手段６は、上記隣接ノードについて、ノード情報記憶手段１３の情報を更新しない。
【００２２】
経路記憶手段１１を参照し、経路記憶手段１１に探索ノードの識別子が含まれていなければ、ステップ１０４の探索ノード決定ステップからステップ１０７の経路パラメータ判定ステップまでの処理を繰り返す（ステップ１０８）。ステップ１０８で探索ノードが経路記憶手段１１に含まれていると、経路保存手段１０９が、ノード情報記憶手段１３を参照し、探索ノードから受信ノードまでの経路の情報として、探索ノードから受信ノードまでの各ノードの識別子を順に並べた情報を経路記憶手段１１に格納する（ステップ１０９）。
【００２３】
経路記憶手段１１を参照して、ステップ１０１で取得した、受信ノードの識別子が経路記憶手段１１に全て格納されていなければ、ステップ１０３の計算受信ノード決定ステップからステップ１０９の経路保存ステップまでの処理を繰り返す（ステップ１１０）。ステップ１１０で、受信ノードの識別子が経路記憶手段１１に全て格納されていれば、経路出力手段８は、経路記憶手段１１に格納された経路の情報を出力する（ステップ１１１）。
【００２４】
以下に、本発明のマルチキャスト経路計算方法およびマルチキャスト経路計算装置についての実施形態を詳しく説明する。
【００２５】
（第１の実施形態）
本実施形態のマルチキャスト経路計算装置の構成を説明する。図３は本実施形態におけるマルチキャスト経路計算装置の一構成例を示すブロック図である。
【００２６】
図３に示すように、マルチキャスト経路計算装置２００は、制御部２０と、記憶部３０とを有する。制御部２０は、要求取得部２１と、計算順序決定部２２と、初期化部２３と、計算受信ノード決定部２４と、探索ノード決定部２５と、経路パラメータ計算部２６と、経路パラメータ判定部２７と、経路保存部２８と、経路出力部２９とを有する。記憶部３０は、トポロジ情報記憶部３１と、送信・受信ノード記憶部３２と、経路記憶部３３と、訪問済みノード記憶部３４と、ノード情報記憶部３５とを有する。
【００２７】
要求取得部２１は、外部からトポロジ情報と、ネットワーク内のノードのうち送信ノードおよび複数の受信ノードのそれぞれを特定するための情報とが入力装置（不図示）を介して入力され、または、これらの情報を記憶装置（不図示）から読み出す。ノードを特定するための情報とは、ネットワーク内のノード毎に異なる識別子である。トポロジ情報には、ネットワーク内に配置されている全てのノードの識別子の情報と、隣接するノード同士を接続する経路の情報と、各経路のコスト値の情報とが含まれている。
【００２８】
要求取得部２１は、上記のようにして、トポロジ情報と、送信ノードおよび受信ノードのそれぞれの識別子の情報とを取得すると、トポロジ情報をトポロジ情報記憶部３１に格納し、送信ノードおよび受信ノードのそれぞれの識別子を送信・受信ノード記憶部３２に格納し、送信ノードの識別子を経路記憶部３３に格納する。
【００２９】
計算順序決定部２２は、送信・受信ノード記憶部３２を参照し、受信ノードの計算順序を決定し、決定した計算順序を送信・受信ノード記憶部３２に格納する。
【００３０】
初期化部２３は、訪問済みノード記憶部３４およびノード情報記憶部３５を初期化する。計算受信ノード決定部２４は、送信・受信ノード記憶部３２および経路記憶部３３を参照し、経路記憶部３３に格納されていない受信ノードの中で計算順序最上位の受信ノードを決定する。
【００３１】
探索ノード決定部２５は、訪問済みノード記憶部３４およびノード情報記憶部３５を参照し、探索ノードを決定し、決定した探索ノードを訪問済みノード記憶部３４に格納する。
【００３２】
経路パラメータ計算部２６は、トポロジ情報記憶部３１を参照し、上記探索ノードの隣接ノードについて、探索ノード経由の経路における第１の合計コストを計算する。
【００３３】
経路パラメータ判定部２７は、ノード情報記憶部３５を参照し、上記隣接ノードについて、既に算出された第２の合計コストがノード情報記憶部３５に格納されていると、第２の合計コストと第１の合計コストとを比較し、合計コストの小さい方を残すように、ノード情報記憶部３５の情報を更新する。ノード情報記憶部３５に上記隣接ノードの第２の合計コストが格納されていない場合、経路パラメータ判定部２７は、経路パラメータ計算部２６が算出した第１の合計コストを隣接ノードの識別子と組にしてノード情報記憶部３５に格納する。
【００３４】
経路保存部２８は、ノード情報記憶部３５を参照し、探索ノードから受信ノードまでの経路を、ノードを経路順に並べた情報として、経路記憶部３３に保存する。経路出力部２９は、経路記憶部３３に格納された経路の情報を出力する。
【００３５】
なお、制御部２０には、プログラムにしたがって処理を実行するＣＰＵ（Central Processing Unit）（不図示）と、プログラムを格納するためのメモリ（不図示）とが設けられている。ＣＰＵがプログラムを実行することで、要求取得部２１、計算順序決定部２２、初期化部２３、計算受信ノード決定部２４、探索ノード決定部２５、経路パラメータ計算部２６、経路パラメータ判定部２７、経路保存部２８および経路出力部２９がマルチキャスト経路計算装置２００に仮想的に構成される。
【００３６】
次に、本実施形態のマルチキャスト経路計算装置２００の動作を説明する。図４および図５は本実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
【００３７】
まず、ステップ２０１に示すように、要求取得部２１がネットワークの各ノードの接続関係を表したトポロジ情報と、送信ノードおよび受信ノードの識別子を取得する。トポロジ情報には、各ノードの接続関係の情報の他に、各リンクのコスト値の情報が含まれている。また、受信ノードは、ここでは、複数のノードとする。また、要求取得部２１は、取得したトポロジ情報をトポロジ情報記憶部３１に格納し、送信ノードと受信ノードの識別子を送信・受信ノード記憶部３２に保存する。
【００３８】
次に、要求取得部２１が、送信ノードの識別子を経路記憶部３３に保存する（ステップ２０２）。次に、計算順序決定部２２が、送信ノードから各受信ノードまでの最小合計コストを計算する（ステップ２０３）。
【００３９】
次に、計算順序決定部２２が、送信ノードから各受信ノードまでの最小合計コストを比較し、最小合計コストが最も小さい受信ノードを計算順序最上位、最も大きい受信ノードを最下位とし、計算順序を送信・受信ノード記憶部３２の各受信ノードに対応して保存する（ステップ２０４）。次に、初期化部２３が、訪問済みノード記憶部３４とノード情報記憶部の情報を削除する（ステップ２０５）。ただし、最初はデータが格納されていないため、この処理を行う必要はない。
【００４０】
次に、計算受信ノード決定部２４が、経路記憶部３３に保存されていない受信ノードの中で、計算順序最上位の受信ノードを決定する（ステップ２０６）。ただし、最初は、経路記憶部３３には、送信ノードの情報しか保存されていないため、計算順序最上位の受信ノードが決定される。
【００４１】
次に、探索ノード決定部２５が、訪問済みノード記憶部３４に何らかのノードが保存さているかを判定する（ステップ２０７）。訪問済みノード記憶部３４に何も保存されていない場合、探索ノード決定２５は、ステップ２０６で決定された受信ノードを探索ノードとして決定し、この受信ノードを訪問済みノード記憶部３４に保存する（ステップ２０８）。ここで設定される受信ノードが第１の探索ノードに相当する。
【００４２】
一方、ステップ２０７の判定で訪問済みノード記憶部３４に何らかのノードが保存されている場合、探索ノード決定部２５は、まだ訪問済みとなっていないノードについて、ノード情報記憶部３５に保存されているノードに対する合計コストと経路を参照する。そして、探索ノード決定部２５は、合計コストが最小のノードを１つ選び、選んだノードを探索ノードとして決定し、訪問済みノード記憶部３４に保存する（ステップ２０９）。ここで設定される探索ノードは第２の探索ノードに相当し、第２の探索ノードは、送信ノードまたは上記計算順序が上位の受信ノードにおける経路計算で設定された経路上のノードに一致するまで更新される。
【００４３】
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１（第１の合計コストに相当）を計算する（ステップ２１０）。合計コストＣ１は、
Ｃ１＝Ｉｄ＊Ｃ（ｖ）＋ｗ（ｖ，ｕ）・・・（式１）
で求まる。
【００４４】
（式１）において、Ｉｄは、探索ノードが受信ノードの１つであれば０であり、そうでなければ１である。Ｃ（ｖ）は、探索ノードｖの合計コストである。ｗ（ｖ，ｕ）は、探索ノードと隣接ノード間のリンクのコスト値である。Ｃ（ｖ）は、ノード情報記憶部３５に保存されている値を用いる。ノード情報記憶部３５に探索ノードｖが保存されていない場合、Ｃ（ｖ）は０である。
【００４５】
次に、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣ（第２の合計コストに相当）が既に保存されているかどうかを判定する（ステップ２１１）。合計コストＣが保存されていない場合、経路パラメータ判定部２７は、ノード情報記憶部３５の隣接ノードｕに、Ｃ１と、経路を示す情報として探索ノードの識別子とを一緒にして保存する。ステップ２１１の判定で既にＣが保存されている場合、経路パラメータ判定部２７は、Ｃ１＜Ｃかどうかを判定する（ステップ２１２）。Ｃ１＜Ｃである場合、経路パラメータ判定部２７は、ノード情報記憶部３５の隣接ノードｕに、Ｃ１と経路（探索ノード）の識別子の情報を上書きする（ステップ２１３）。
【００４６】
経路パラメータ判定部２７は、探索ノードに対する隣接ノード全てに対し、Ｃ１の計算が行われるまで、ステップ２１０〜ステップ２１３の処理を繰り返す（ステップ２１４）。ステップ２１４で、Ｃ１の計算を行っていない隣接ノードがなければ、経路パラメータ判定部２７は、探索ノードが経路記憶部３３に保存されているか否かを判定し（ステップ２１５）、探索ノードが経路記憶部３３に保存されていなければ、ステップ２０７〜ステップ２１４の処理を繰り返す。
【００４７】
ステップ２１５で探索ノードが経路記憶部３３に保存されているノードであれば、経路保存部２８は、ノード情報記憶部３５を参照し、探索ノードから受信ノードまでの経路を、ノードを経路順に並べた情報として、経路記憶部３３に保存する。つまり、経路保存部２８は、経路情報として、探索ノードから受信ノードまでの経路における各ノードの識別子を経路順に並べた情報を、経路記憶部３３に保存する。この経路は、ノード情報記憶部３５の各ノードに保存されている経路（ノード）をたどることで得られる。
【００４８】
このようにして、ステップ２０１で取得した識別子の全ての受信ノードの経路の情報が、経路記憶部３３に保存されるまで、初期化部２３が実行するステップ２０５〜経路保存部２８が実行するステップ２１６までの処理を繰り返す（ステップ２１７）。
【００４９】
全ての受信ノードの経路の情報が経路記憶部３３に保存されたら、最後に、経路出力部２９が、経路記憶部３３に保存されている経路の情報を出力することで（ステップ２１８）、処理が終了する。
【００５０】
次に、上述した本実施形態のマルチキャスト経路計算方法の具体例を、図６を参照して説明する。図６はネットワークトポロジの一構成例を示す図である。
【００５１】
図６に示す例では、ノードの識別子を１〜１６のノード番号としている。ノード間のリンク上の数値はコスト値を表している。
【００５２】
はじめに、要求取得部２１がトポロジ情報を外部から取得する。各ノードの接続関係、各リンクのコスト値は、図６に示すとおりである。次に、要求取得部２１は、送信ノードと複数の受信ノードの識別子を外部から取得する。本具体例では、送信ノードを図６に示すノード１とする。また、受信ノードの数は５個とし、受信ノードＡを図６に示すノード９とし、受信ノードＢをノード１０とし、受信ノードＣをノード１３とし、受信ノードＤをノード１２とし、受信ノードＥをノード１５とする。要求取得部２１は、トポロジ情報をトポロジ情報記憶部３１に保存し、送信ノードと受信ノードＡ〜Ｅの識別子を送信・受信ノード記憶部３２に保存する。さらに、要求取得部２１は、送信ノードの識別子を経路記憶部３３に保存する。
【００５３】
次に、計算順序決定部２２が、送信ノードから各受信ノードまでの最小合計コストを計算する。本具体例において、各受信ノードの最小合計コストは、受信ノードＡが３、受信ノードＢが５、受信ノードＣが６、受信ノードＤが９、受信ノードＥが１０となる。計算順序決定部２２は、これらのコスト値を比較し、最小合計コストが小さい方から順に、以下に示すように、計算順序を決定する。
１位：受信ノードＡ
２位：受信ノードＢ
３位：受信ノードＣ
４位：受信ノードＤ
５位：受信ノードＥ
計算順序決定部２２は、これらの最小合計コストと順位の情報を送信・受信ノード記憶部３２における、それぞれの受信ノードの識別子の情報に関連付けて保存する。
【００５４】
図７Ａから図９Ｂは、第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。図７Ａから図８Ａに示す黒三角印は探索ノードを示し、図７Ａから図９Ｂにおいて、ノードの脇に記述された四角の中のＣとＲの情報は、ノード情報記憶部３５に保存される情報を示す。
【００５５】
初期化部２３が、訪問済みノード記憶部３４とノード情報記憶部３５の情報を削除する。ただし、最初はデータが格納されていないため、この処理を行う必要はない。次に、計算受信ノード決定部２４が、経路記憶部３３に保存されていない受信ノードの中で、計算順序最上位の受信ノードを決定する。ただし、最初は、経路記憶部３３には、送信ノードの識別子しか保存されていないため、計算順序最上位の受信ノードが決定される。本具体例では、受信ノードＡが選択される。
【００５６】
次に、探索ノード決定部２５が、訪問済みノード記憶部３４に何らかのノードが保存さているかを判定する。最初は何も保存されていないため、ステップ２０６で決定された受信ノードＡを探索ノードとして決定し、受信ノードＡを訪問済みノード記憶部３４に保存する（図７Ａ）。
【００５７】
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１を計算する。ここでは、ノード９（受信ノードＡ）が探索ノードｖに相当し、ノード５、ノード６、ノード１０およびノード１３が隣接ノードｕに相当する。
【００５８】
さらに、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣが既に保存されているかどうかを判定する。最初は、合計コストＣが保存されていないため、ノード情報記憶部３５の隣接ノードｕに、Ｃ１および、経路として、探索ノードの識別子を保存する（図５に示したステップ２１３）。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図７Ｂ）。図７Ｂにおいて、合計コストをＣ、経路の目印として探索ノードの識別子をＲで示す。また、図７Ａから図９Ｂの各図において、経路記憶部３３および訪問済みノード記憶部３４のそれぞれに保存される、ノードの識別子を破線枠の中に示す。
【００５９】
続いて、図５に示したステップ２１５において、探索ノードが経路記憶部３３に保存されていないので、探索ノード決定の処理（図５に示したステップ２０７）に戻る。
【００６０】
探索ノード決定部２５が、訪問済みノード記憶部３４を参照し、ノードが保存されているため、訪問済みとなっていないノードについて、ノード情報記憶部３５に保存されているノードに対する合計コストと経路を参照し、合計コストが最小のノードを１つ選ぶ。ここでは、合計コストが２のノード５が探索ノードとして選択され、訪問済みノード記憶部３４に保存される（図７Ｃ）。
【００６１】
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１を計算する。ここでは、ノード５が探索ノードｖに相当し、ノード１、ノード２、ノード６およびノード９が隣接ノードｕに相当する。
【００６２】
さらに、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣが既に保存されているかどうかを判定する。保存されていないノードには、ノード情報記憶部３５の隣接ノードｕに、Ｃ１および、経路として、探索ノードを保存する。一方、既に、Ｃが保存されているノードにおいては、Ｃ１＜Ｃの場合、Ｃ１を新たなＣとして、また、探索ノードを経路として保存する。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図７Ｄ）。図７Ｄに示すように、ノード１およびノード２については、Ｃ１と経路として探索ノード（ノード５）とが保存され、ノード６およびノード９については情報が更新されなかった。
【００６３】
続いて、図５に示したステップ２１５において、探索ノードが経路記憶部３３に保存されていないので、探索ノード決定の処理（図５に示したステップ２０７）に戻る。
【００６４】
探索ノード決定部２５が、訪問済みノード記憶部３４を参照し、ノードが保存されているため、訪問済みとなっていないノードについて、ノード情報記憶部３５に保存されているノードに対する合計コストと経路を参照し、合計コストが最小のノードを１つ選ぶ。ここでは、合計コストが３のノード１が探索ノードとして選択され、訪問済みノード記憶部３４に保存される（図８Ａ）。ここで、合計コスト３のノードが複数あるが、そのような場合、ノード番号が最も小さいノードを選択することとした。
【００６５】
ノード１の識別子が経路記憶部３３に保存されているため、図４および図５に示したステップ２０７からステップ２１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＡまでの経路の情報が保存される（図８Ｂ）。ここで、探索ノードから受信ノードＡまでの経路の情報は、具体的には、送信ノード１、ノード５およびノード９の識別子が順に並んだ情報である。図８Ｂでは、保存された経路の情報に相当する経路を太線で示している。
【００６６】
経路記憶部３３には全ての受信ノードの識別子が保存されていないため、初期化部２３の処理（図４に示したステップ２０５）に戻る。初期化部２３は、訪問済みノード記憶部３４とノード情報記憶部３５の情報を削除する（図８Ｃ）。
【００６７】
次に、計算受信ノード決定部２４が、送信・受信ノード記憶部３２を参照し、次の計算対象の受信ノードとして、受信ノードＢを選択する。
【００６８】
受信ノードＢについて、探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を、受信ノードＡと同様に繰り返すと、探索ノードがノード１０、ノード６、ノード１１、ノード１３、ノード９の順に決定される。
【００６９】
ノード９の識別子が経路記憶部３３に保存されているため、図４および図５に示したステップ２０７からステップ２１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＢまでの経路が保存される（図８Ｄ）。ここで、ノード１３が探索ノードとして決定されたとき、経路パラメータ計算部２６において、Ｃ１の計算式（式１）では、Ｉｄが０にセットされることに注意が必要である。また、このとき、探索ノードに相当するノード９から受信ノードＢに相当するノード１０までの経路情報として、ノード９、ノード１３およびノード１０が順に並んだ情報が経路記憶部３３に保存される。つまり、受信ノードＣの識別子が経路記憶部３３に保存される。
【００７０】
経路記憶部３３に全ての受信ノードの識別子が保存されていないため、初期化部２３の処理（図４に示したステップ２０５）に戻る。初期化部２３は、訪問済みノード記憶部３４とノード情報記憶部３５の情報を削除する。次に、計算受信ノード決定部２４が、送信・受信ノード記憶部３２を参照し、次の計算対象の受信ノードとして、受信ノードＤを選択する。１つ前の順位である受信ノードＣは、受信ノードＢからの経路に含まれているため、受信ノードＣからの経路探索は行われない。
【００７１】
受信ノードＤについて、探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を、受信ノードＡと同様に繰り返すと、探索ノードがノード１２、ノード１１、ノード１５、ノード１４、ノード１６、ノード７、ノード１０の順に決定される。ここで、ノード１５が探索ノードとして決定されたとき、経路パラメータ計算部２６において、Ｃ１の計算式（式１）では、Ｉｄが０にセットされることに注意が必要である。
【００７２】
ノード１０の識別子が経路記憶部３３に保存されているため、図４および図５に示したステップ２０７からステップ２１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＤまでの経路が保存される（図９Ａ）。
【００７３】
経路記憶部３３に全ての受信ノードの識別子が保存されていないため、初期化部２３の処理（図４に示したステップ２０５）に戻る。初期化部２３は、訪問済みノード記憶部３４とノード情報記憶部３５の情報を削除する。次に、計算受信ノード決定部２４が、送信・受信ノード記憶部３２を参照し、次の計算対象の受信ノードとして、受信ノードＥを選択する。
【００７４】
受信ノードＥについて、探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を、受信ノードＡと同様に繰り返すと、探索ノードがノード１５、ノード１４、ノード１６、ノード１２の順に決定される。
【００７５】
ノード１２の識別子が経路記憶部３３に保存されているため、図４および図５に示したステップ２０７からステップ２１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＥまでの経路が保存される（図９Ｂ）。
【００７６】
経路記憶部３３に全ての受信ノードの識別子が保存されたため、最後に経路出力部２９が経路記憶部３３を参照し、マルチキャスト経路を、例えば以下のように出力し、処理を終了する。
受信ノードＡへの経路：１、５、９
受信ノードＢへの経路：１、５、９、１３、１０
受信ノードＣへの経路：１、５、９、１３
受信ノードＤへの経路：１、５、９、１３、１０、１１、１２
受信ノードＥへの経路：１、５、９、１３、１０、１１、１２、１６、１５
【００７７】
本実施形態によれば、受信ノードから送信ノードへ、また、受信ノードから既に確定した経路へ、最小の合計コストで経路を接続させていくことで、１つの経路に複数の受信ノードが乗り、マルチキャスト経路全体の合計コストを低く抑えることができる。また、送信ノードと受信ノードの全ての組み合わせのフルメッシュ経路を計算する場合よりも計算量が少なく済む。
【００７８】
また、本実施形態では、ある受信ノードからの経路探索の途中で他の受信ノードが発見されると、合計コストをゼロにリセットする場合を説明したが、必ずしもゼロにリセットしなくてもよい。このとき合計コストをゼロにリセットすることにより、他の受信ノードを経由する経路が優先的に選択されるため、さらにマルチキャスト経路全体の合計コストを最小限に抑えることが可能になる。
【００７９】
（第２の実施形態）
本実施形態のマルチキャスト経路計算装置の構成を説明する。
【００８０】
図１０は、本実施形態のマルチキャスト経路計算装置の一構成例を示すブロック図である。なお、本実施形態では、第１の実施形態と異なる点を詳細に説明し、第１の実施形態と同様な構成についてはその詳細な説明を省略する。
【００８１】
本実施形態のマルチキャスト経路計算装置３００は、第１の実施形態で説明した初期化部２３と計算受信ノード決定部２４の処理が異なる。本実施形態では、図１０に示すように、第１の実施形態における初期化部２３と計算受信ノード決定部２４の処理順序が逆転し、初期化部２３の代わりに情報更新部４１が設けられている。
【００８２】
情報更新部４１は、計算受信ノード決定部２４で決定された受信ノード（受信ノードｄとする）の１つ前の順位の受信ノード（受信ノードｄ’とする）からの経路探索において、受信ノードｄからの経路が計算されている場合に、その経路と合計コストの情報を含む経路探索情報を訪問済みノード記憶部３４とノード情報記憶部３５に残し、それ以外の情報を削除する。
【００８３】
図１１および図１２は、本実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
【００８４】
本実施形態におけるマルチキャスト経路計算方法は、図１０で示したマルチキャスト経路計算装置の構成に対応して、第１の実施形態で説明した初期化ステップ（ステップ２０５）と計算受信ノード決定ステップ（ステップ２０６）の順序が逆になり、初期化ステップ（ステップ２０５）の代わりに情報更新ステップ（ステップ３０６）を有する。
【００８５】
図４に示したステップ２０６は図１１に示すステップ３０５に相当し、図４に示したステップ２０１〜２０４およびステップ２０７〜２０９のそれぞれは図１１に示すステップ３０１〜３０４およびステップ３０７〜３０９のそれぞれに相当しており、同様な処理についての詳細な説明を省略する。また、図５に示したステップ２１０〜ステップ２１８のそれぞれは図１１に示すステップ３１０〜ステップ３１８に相当し、同様な処理についての詳細な説明を省略する。
【００８６】
本実施形態のマルチキャスト経路計算装置３００の動作の具体例について、第１の実施の形態と異なる部分を詳しく説明する。ここでも、ネットワークトポロジの一例として、図６に示したトポロジを用いる。
【００８７】
第１の実施形態で説明した動作を例に説明する。受信ノードＡからの経路探索終了後、計算受信ノード決定部２４が、探索ノードとして、計算順序次位の受信ノードである受信ノードＢに決定する。受信ノードＡからの経路探索では、受信ノードＢからの経路は計算されていないため、図１１に示すステップ３０６において、情報更新部４１は、訪問済みノード記憶部３４とノード情報記憶部３５の全ての情報を削除する。
【００８８】
次に、受信ノードＢからの経路探索終了後、計算受信ノード決定部２４が、探索ノードとして、計算順序次位の受信ノードである受信ノードＤに決定する。１つ前の順位である受信ノードＣは、受信ノードＢからの経路に含まれているため、受信ノードＣからの経路探索は行われていない。したがって、この場合にも、情報更新部４１は、訪問済みノード記憶部３４とノード情報記憶部３５の全ての情報を削除する。
【００８９】
受信ノードＤからの経路計算について、情報更新ステップ以降の処理を、具体的に説明する。図１３Ａから図１５Ｂは本実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【００９０】
探索ノード決定部２５が、受信ノードＤを探索ノードとして決定し、受信ノードＤの識別子を訪問済みノード記憶部３４に保存する（図１３Ａ）。
【００９１】
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１を計算する。さらに、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣが既に保存されているかどうかを判定する。最初は保存されていないため、ノード情報記憶部３５の隣接ノードｕに、Ｃ１および、経路として、探索ノードの識別子を保存する。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図１３Ｂ）。図１３Ｂにおいて、合計コストをＣ、経路の目印として探索ノードの識別子をＲで示す。
【００９２】
探索ノードが経路記憶部３３に保存されていないので、探索ノード決定の処理（図１１に示すステップ３０７）に戻る。
【００９３】
探索ノード決定部２５が、訪問済みノード記憶部３４を参照し、ノードが保存されているため、訪問済みとなっていないノードについて、ノード情報記憶部３５に保存されているノードに対する合計コストと経路を参照し、合計コストが最小のノードを１つ選ぶ。ここでは、合計コストが２のノード１１が探索ノードとして選択され、訪問済みノード記憶部３４に保存される（図１３Ｃ）。
【００９４】
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１を計算する。さらに、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣが既に保存されているかどうかを判定する。保存されていないノードには、ノード情報記憶部３５の隣接ノードｕに、Ｃ１および、経路として、探索ノードの識別子を保存する。既に、Ｃが保存されているノードにおいては、Ｃ１＜Ｃの場合、Ｃ１を新たなＣとして、また、探索ノードを経路として保存する。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図１３Ｄ）。
【００９５】
上記の探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を繰り返すと、探索ノードがノード１２、ノード１１、ノード１５、ノード１４、ノード１６、ノード７、ノード１０の順に決定される。ここで、ノード１５が探索ノードとして決定されたとき、経路パラメータ計算部２６において、Ｃ１の計算式（式１）では、Ｉｄが０にセットされることに注意が必要である（図１４Ａ〜図１４Ｃ）。
【００９６】
ノード１０の識別子が経路記憶部３３に保存されているため、図１１および図１２に示すステップ３０７からステップ３１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＤまでの経路が保存される（図１４Ｄ）。
【００９７】
経路記憶部３３に全ての受信ノードの識別子が保存されていないため、計算受信ノード決定部２４の処理に戻る。計算受信ノード決定部２４が、送信・受信ノード記憶部３２を参照し、次の計算対象の受信ノードとして、受信ノードＥを選択する。
【００９８】
次に、図１１に示したステップ３０６において、情報更新部４１が、受信ノードＤからの経路探索において、受信ノードＥからの経路が計算されているかを判定する。つまり、受信ノードＥの識別子が訪問済みノード記憶部３４に格納されており、受信ノードＥを経由して探索されたノードの識別子が訪問済みノード記憶部３４に格納されているかどうかを判定する。
【００９９】
受信ノードＥの識別子が訪問済みノード記憶部３４に格納されている場合には、情報更新部４１は、受信ノードＥと受信ノードＥから探索された訪問済みノードの識別子を、訪問済みノード記憶部３４に残し、それ以外のノードの識別子を削除する。また、情報更新部４１は、受信ノードＥを経由して探索された訪問済みノードに関する情報をノード情報記憶部３５に残し、それ以外のノードに関する情報を削除する。本動作例では、ノード１５、ノード１４、ノード１６が訪問済みノード記憶部３４に残され、ノード１４とノード１６の情報がノード情報記憶部３５に残される（図１５Ａ）。経路パラメータ計算部２６は、ノード１５、ノード１４およびノード１６の経路探索情報を利用することが可能となる。
【０１００】
これ以降は、受信ノードＤと同様に、探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を繰り返すと、探索ノードがノード１２と決定され、経路計算が完了する（図１５Ｂ）。
【０１０１】
第１の実施形態では、受信ノードＥから新たに経路計算を行ったが、本実施形態では、ノード１４とノード１６への経路探索を行う必要がなく、計算量が少なくてすむ。経路出力部２９が出力する経路の情報は、第１の実施形態と同じになる。
【０１０２】
本実施形態によれば、第１の実施形態と同様にマルチキャスト経路全体の合計コストを最小限に抑えられるだけでなく、ある受信ノードからの経路計算において、並行して計算された、次の計算順位の受信ノードからの経路を、次の受信ノードからの経路計算時に流用することで、計算量の低減を図ることが可能である。
【０１０３】
なお、上述した第１または第２の実施形態で説明した動作をプログラムとして構築し、そのプログラムをマルチキャスト経路計算装置として利用されるコンピュータにインストールして実行させる、または、そのプログラムをネットワークを介して流通させることが可能である。
【０１０４】
また、構築されたプログラムを、コンピュータ読み取り可能なディスク装置や、ＣＤ−ＲＯＭ等の搬送可能な記憶媒体に格納し、コンピュータにインストールして実行させる、または、配布することが可能である。
【０１０５】
本発明は、上記の実施形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１０６】
１００、２００、３００ マルチキャスト経路計算装置
１ 要求取得手段
２ 計算順序決定手段
４ 探索ノード決定手段
５ 経路パラメータ計算手段
６ 経路パラメータ判定手段
７ 経路保存手段
８ 経路出力手段
１１ 経路記憶手段
１２ 訪問済みノード記憶手段
１３ ノード情報記憶手段
２０ 制御部
３０ 記憶部
【技術分野】
【０００１】
本発明は、マルチキャスト通信において、最適な経路を選択するために、ネットワークのリンクに距離や帯域などに関連したコスト値を与え、その合計が最小となるマルチキャスト経路を計算する経路計算方法、経路計算装置、およびコンピュータに実行させるためのプログラムに関する。
【背景技術】
【０００２】
近年、デジタル映像配信やグループビデオ会議など、マルチキャスト通信の需要が高まっている。このようなアプリケーションは、データサイズが大きいため、大量のトラフィックがネットワーク上を流れることになる。したがって、ネットワーク管理者は、アプリケーションが満たすべき品質や、データ量に応じて、マルチキャスト経路を決定し、管理する必要がある。リング型やスター型といった、シンプルなネットワークでは、マルチキャスト経路は一意に決まり、ネットワーク管理者は、経路の管理を容易に行うことができる。しかし、近年、ネットワークは複雑化しており、最適な経路を決定するためには、適したマルチキャスト経路計算アルゴリズムが必要である。最適なマルチキャスト経路の決定方法として、ネットワークのリンクにコスト値を与え、マルチキャスト経路全体の合計コストを最小化する方法がある。
【０００３】
合計コストが最小となるマルチキャスト経路を求める問題は、最小シュタイナーツリー問題として、古くから解かれているが、ＮＰ（Nondeterministic Polynomial）完全問題であることが知られており、実時間で最適解を見つけることは困難である。
【０００４】
近似解を求める手法として、非特許文献１には、送信ノードと受信ノードそれぞれを結ぶフルメッシュの最短路ネットワークを求め、求めたネットワークにおいて、最小全域木を求めることで、低コストマルチキャスト経路を計算する方法が開示されている。
【０００５】
また、非特許文献２には、送信ノードからダイクストラ法による最短経路計算を行い、経路探索中に受信ノードが発見されると、その受信ノードを経由して、他の受信ノードに向かう経路を優先的に選択することにより、一経路上に複数の受信ノードを乗せることで、低コストマルチキャスト経路を計算する方法が開示されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Kou. L., G. Markowsky, and L. Berman, "A fast algorithm for Steiner trees," IBM Thomas J Watson Research Center, Acta Information 15, pp.141-145, 1981.
【非特許文献２】A. Shaikh and K. Shin, "Destination-driven routing for low-cost multicast," IEEE Journal on Selected Areas in Communications, vol.15, No.3, April 1997.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１に開示された方法では、コストを低く抑えることが可能だが、送信ノードと受信ノードの全ての組み合わせのフルメッシュ経路を計算する必要があり、計算量が多くなってしまう。一方、非特許文献２に開示された方法では、計算量は少ないが、コストは非特許文献１より大きくなる傾向がある。
【０００８】
本発明は上述したような技術が有する問題点を解決するためになされたものであり、マルチキャスト経路の合計コストと経路探索の計算量を抑えることを可能にした経路計算方法、経路計算装置、およびコンピュータに実行させるためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するための本発明の経路計算方法は、
ネットワーク内の各ノードに対応する識別子、隣接するノード同士を接続する経路および各経路のコスト値の情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードのそれぞれの識別子の情報を取得し、
前記複数の受信ノードについて経路計算の順位を決め、
決定した順位の最上位の受信ノードから最下位の受信ノードまで順に第１の探索ノードに設定し、
設定した第１の探索ノード毎に、該第１の探索ノードの隣接ノードについて、該第１の探索ノードと該隣接ノードの間のコスト値を合計コストとし、該合計コストが最小となる隣接ノードを第２の探索ノードとし、該第２の探索ノードが前記送信ノード、または該第１の探索ノードよりも前記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致するまで、前記第１の探索ノードから該第２の探索ノードを経由して該第２の探索ノードの隣接ノードまでの前記合計コストが最小となる隣接ノードを第２の探索ノードに順次更新することで、前記第１の探索ノードから更新された第２の探索ノードを順に結ぶ経路を設定し、
前記第２の探索ノードについて前記隣接ノードの前記合計コストを算出する際、該第２の探索ノードが前記複数の受信ノードのうち、いずれかの受信ノードと一致する場合、該第２の探索ノードまでの前記合計コストをゼロにリセットし、該第２の探索ノードを起点とする経路のコスト値を前記合計コストとするものである。
【００１０】
また、本発明の経路計算装置は、
ネットワーク内の各ノードに対応する識別子、隣接するノード同士を接続する経路および各経路のコスト値の情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードのそれぞれの識別子の情報を保存する記憶手段と、
前記要求取得手段から受け取る前記複数の受信ノードについて経路計算の順位を決める計算順序決定手段と、
前記計算順序決定手段が決定した順位の最上位の受信ノードから最下位の受信ノードまで順に第１の探索ノードに設定し、設定した第１の探索ノード毎に、該第１の探索ノードの隣接ノードについて、該第１の探索ノードと該隣接ノードの間のコスト値を合計コストとし、該合計コストが最小となる隣接ノードを第２の探索ノードとし、前記第１の探索ノードから該第２の探索ノードを経由して該第２の探索ノードの隣接ノードまでの前記合計コストが最小となる隣接ノードを第２の探索ノードに順次更新する経路パラメータ計算手段と、
前記第２の探索ノードが前記送信ノード、または該第１の探索ノードよりも前記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致すると、前記第１の探索ノードから更新された第２の探索ノードを順に結ぶ経路を設定する経路パラメータ判定手段と、を有し、
前記経路パラメータ計算手段は、
前記第２の探索ノードについて前記隣接ノードの前記合計コストを算出する際、該第２の探索ノードが前記複数の受信ノードのうち、いずれかの受信ノードと一致する場合、該第２の探索ノードまでの前記合計コストをゼロにリセットし、該第２の探索ノードを起点とする経路のコスト値を前記合計コストとする構成である。
【００１１】
さらに、本発明のプログラムは、上記本発明の経路計算方法をコンピュータに実行させるものである。
【発明の効果】
【００１２】
本発明によれば、マルチキャスト通信を行う際、経路探索の計算量を抑制し、経路全体の合計コストを抑制できる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態におけるマルチキャスト経路計算装置の一構成例を示すブロック図である。
【図２】本発明の一実施形態におけるマルチキャスト経路計算方法の手順を示すフローチャートである。
【図３】第１の実施形態におけるマルチキャスト経路計算装置の一構成例を示すブロック図である。
【図４】第１の実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
【図５】第１の実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
【図６】第１の実施形態におけるマルチキャスト経路計算方法を具体的に説明するためのネットワークトポロジの一構成例を示す図である。
【図７Ａ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図７Ｂ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図７Ｃ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図７Ｄ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図８Ａ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図８Ｂ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図８Ｃ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図８Ｄ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図９Ａ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図９Ｂ】第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１０】第２の実施形態におけるマルチキャスト経路計算装置の一構成例を示すブロック図である。
【図１１】第２の実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
【図１２】第２の実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
【図１３Ａ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１３Ｂ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１３Ｃ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１３Ｄ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１４Ａ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１４Ｂ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１４Ｃ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１４Ｄ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１５Ａ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【図１５Ｂ】第２の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【発明を実施するための形態】
【００１４】
本発明のマルチキャスト経路計算装置は、ネットワークのリンクに距離や帯域などと関連付けられたコスト値を与え、コスト値の合計が最小となるマルチキャスト経路を計算する装置である。
【００１５】
本発明の一実施形態のマルチキャスト経路計算装置の構成を説明する。図１は本発明の一実施形態におけるマルチキャスト経路計算装置の一構成例を示すブロック図である。
【００１６】
マルチキャスト経路計算装置１００は、要求取得手段１と、計算順序決定手段２と、計算受信ノード決定手段３と、探索ノード決定手段４と、経路パラメータ計算手段５と、経路パラメータ判定手段６と、経路保存手段７と、経路出力手段８とを有する。また、マルチキャスト経路計算装置１００は、マルチキャスト経路を計算する過程で情報を保存し、また、計算結果を保存するための記憶手段を備えている。記憶手段は、経路記憶手段１１と、訪問済みノード記憶手段１２と、ノード情報記憶手段１３とを有する。
【００１７】
次に、図１に示したマルチキャスト経路計算装置１００による経路計算方法の動作を説明する。図２は本発明の一実施形態におけるマルチキャスト経路計算方法の手順を示すフローチャートである。
【００１８】
要求取得手段１が、ネットワーク内の各ノードの接続関係を表した情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードの識別子を受け付けると（ステップ１０１）、送信ノードの識別子を経路記憶手段１１に格納する。続いて、計算順序決定手段２が、受信ノードの経路計算の順序である計算順序を決定する（ステップ１０２）。計算受信ノード決定手段３が、経路記憶手段１１に格納されていない受信ノードの中で、計算順序最上位の受信ノードを決定する（ステップ１０３）。
【００１９】
次に、探索ノード決定手段４が、訪問済みノード記憶手段１２を参照し、経路計算が済んだノードである訪問済みノードが訪問済みノード記憶手段１２に保存されていない場合、ステップ１０３で決定された受信ノードを探索ノードとして決定する。一方、訪問済みノードが訪問済みノード記憶手段１２に保存されている場合、まだ経路計算が済んでいない（訪問済みとなっていない）ノードの中から、ノード情報記憶手段１３を参照して、合計コストが最小のノードを探索ノードとして決定し、探索ノードを訪問済みノード記憶手段１２に格納する（ステップ１０４）。
【００２０】
続いて、経路パラメータ計算手段５が、ステップ１０４で決定された探索ノードの隣接ノードについて、探索ノード経由の経路における合計コストを計算する（ステップ１０５）。その際、探索ノードが受信ノードである場合、経路パラメータ計算手段５は、探索ノードまでの合計コストをゼロにリセットし、探索ノードと隣接ノードとの間のコスト値を新たな合計コストとする。ステップ１０５で算出される合計コストを第１の合計コストと称する。なお、本実施形態では、ステップ１０５において、探索ノードが受信ノードであると、探索ノードまでの合計コストをゼロにリセットする場合で説明するが、その合計コストをゼロにリセットしなくてもよい。
【００２１】
経路パラメータ判定手段６は、隣接ノードについて、ノード情報記憶手段１３を参照し、合計コストが保存されていない場合、または、他のノード経由の経路で既に計算された合計コストである第２の合計コストが保存されているが、第1の合計コストの方が小さい場合（ステップ１０６）、第１の合計コストおよび上記探索ノード経由の経路を、ノード情報記憶手段１３に格納する（ステップ１０７）。第２の合計コストの方が第１の合計コストよりも小さい場合には、経路パラメータ判定手段６は、上記隣接ノードについて、ノード情報記憶手段１３の情報を更新しない。
【００２２】
経路記憶手段１１を参照し、経路記憶手段１１に探索ノードの識別子が含まれていなければ、ステップ１０４の探索ノード決定ステップからステップ１０７の経路パラメータ判定ステップまでの処理を繰り返す（ステップ１０８）。ステップ１０８で探索ノードが経路記憶手段１１に含まれていると、経路保存手段１０９が、ノード情報記憶手段１３を参照し、探索ノードから受信ノードまでの経路の情報として、探索ノードから受信ノードまでの各ノードの識別子を順に並べた情報を経路記憶手段１１に格納する（ステップ１０９）。
【００２３】
経路記憶手段１１を参照して、ステップ１０１で取得した、受信ノードの識別子が経路記憶手段１１に全て格納されていなければ、ステップ１０３の計算受信ノード決定ステップからステップ１０９の経路保存ステップまでの処理を繰り返す（ステップ１１０）。ステップ１１０で、受信ノードの識別子が経路記憶手段１１に全て格納されていれば、経路出力手段８は、経路記憶手段１１に格納された経路の情報を出力する（ステップ１１１）。
【００２４】
以下に、本発明のマルチキャスト経路計算方法およびマルチキャスト経路計算装置についての実施形態を詳しく説明する。
【００２５】
（第１の実施形態）
本実施形態のマルチキャスト経路計算装置の構成を説明する。図３は本実施形態におけるマルチキャスト経路計算装置の一構成例を示すブロック図である。
【００２６】
図３に示すように、マルチキャスト経路計算装置２００は、制御部２０と、記憶部３０とを有する。制御部２０は、要求取得部２１と、計算順序決定部２２と、初期化部２３と、計算受信ノード決定部２４と、探索ノード決定部２５と、経路パラメータ計算部２６と、経路パラメータ判定部２７と、経路保存部２８と、経路出力部２９とを有する。記憶部３０は、トポロジ情報記憶部３１と、送信・受信ノード記憶部３２と、経路記憶部３３と、訪問済みノード記憶部３４と、ノード情報記憶部３５とを有する。
【００２７】
要求取得部２１は、外部からトポロジ情報と、ネットワーク内のノードのうち送信ノードおよび複数の受信ノードのそれぞれを特定するための情報とが入力装置（不図示）を介して入力され、または、これらの情報を記憶装置（不図示）から読み出す。ノードを特定するための情報とは、ネットワーク内のノード毎に異なる識別子である。トポロジ情報には、ネットワーク内に配置されている全てのノードの識別子の情報と、隣接するノード同士を接続する経路の情報と、各経路のコスト値の情報とが含まれている。
【００２８】
要求取得部２１は、上記のようにして、トポロジ情報と、送信ノードおよび受信ノードのそれぞれの識別子の情報とを取得すると、トポロジ情報をトポロジ情報記憶部３１に格納し、送信ノードおよび受信ノードのそれぞれの識別子を送信・受信ノード記憶部３２に格納し、送信ノードの識別子を経路記憶部３３に格納する。
【００２９】
計算順序決定部２２は、送信・受信ノード記憶部３２を参照し、受信ノードの計算順序を決定し、決定した計算順序を送信・受信ノード記憶部３２に格納する。
【００３０】
初期化部２３は、訪問済みノード記憶部３４およびノード情報記憶部３５を初期化する。計算受信ノード決定部２４は、送信・受信ノード記憶部３２および経路記憶部３３を参照し、経路記憶部３３に格納されていない受信ノードの中で計算順序最上位の受信ノードを決定する。
【００３１】
探索ノード決定部２５は、訪問済みノード記憶部３４およびノード情報記憶部３５を参照し、探索ノードを決定し、決定した探索ノードを訪問済みノード記憶部３４に格納する。
【００３２】
経路パラメータ計算部２６は、トポロジ情報記憶部３１を参照し、上記探索ノードの隣接ノードについて、探索ノード経由の経路における第１の合計コストを計算する。
【００３３】
経路パラメータ判定部２７は、ノード情報記憶部３５を参照し、上記隣接ノードについて、既に算出された第２の合計コストがノード情報記憶部３５に格納されていると、第２の合計コストと第１の合計コストとを比較し、合計コストの小さい方を残すように、ノード情報記憶部３５の情報を更新する。ノード情報記憶部３５に上記隣接ノードの第２の合計コストが格納されていない場合、経路パラメータ判定部２７は、経路パラメータ計算部２６が算出した第１の合計コストを隣接ノードの識別子と組にしてノード情報記憶部３５に格納する。
【００３４】
経路保存部２８は、ノード情報記憶部３５を参照し、探索ノードから受信ノードまでの経路を、ノードを経路順に並べた情報として、経路記憶部３３に保存する。経路出力部２９は、経路記憶部３３に格納された経路の情報を出力する。
【００３５】
なお、制御部２０には、プログラムにしたがって処理を実行するＣＰＵ（Central Processing Unit）（不図示）と、プログラムを格納するためのメモリ（不図示）とが設けられている。ＣＰＵがプログラムを実行することで、要求取得部２１、計算順序決定部２２、初期化部２３、計算受信ノード決定部２４、探索ノード決定部２５、経路パラメータ計算部２６、経路パラメータ判定部２７、経路保存部２８および経路出力部２９がマルチキャスト経路計算装置２００に仮想的に構成される。
【００３６】
次に、本実施形態のマルチキャスト経路計算装置２００の動作を説明する。図４および図５は本実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
【００３７】
まず、ステップ２０１に示すように、要求取得部２１がネットワークの各ノードの接続関係を表したトポロジ情報と、送信ノードおよび受信ノードの識別子を取得する。トポロジ情報には、各ノードの接続関係の情報の他に、各リンクのコスト値の情報が含まれている。また、受信ノードは、ここでは、複数のノードとする。また、要求取得部２１は、取得したトポロジ情報をトポロジ情報記憶部３１に格納し、送信ノードと受信ノードの識別子を送信・受信ノード記憶部３２に保存する。
【００３８】
次に、要求取得部２１が、送信ノードの識別子を経路記憶部３３に保存する（ステップ２０２）。次に、計算順序決定部２２が、送信ノードから各受信ノードまでの最小合計コストを計算する（ステップ２０３）。
【００３９】
次に、計算順序決定部２２が、送信ノードから各受信ノードまでの最小合計コストを比較し、最小合計コストが最も小さい受信ノードを計算順序最上位、最も大きい受信ノードを最下位とし、計算順序を送信・受信ノード記憶部３２の各受信ノードに対応して保存する（ステップ２０４）。次に、初期化部２３が、訪問済みノード記憶部３４とノード情報記憶部の情報を削除する（ステップ２０５）。ただし、最初はデータが格納されていないため、この処理を行う必要はない。
【００４０】
次に、計算受信ノード決定部２４が、経路記憶部３３に保存されていない受信ノードの中で、計算順序最上位の受信ノードを決定する（ステップ２０６）。ただし、最初は、経路記憶部３３には、送信ノードの情報しか保存されていないため、計算順序最上位の受信ノードが決定される。
【００４１】
次に、探索ノード決定部２５が、訪問済みノード記憶部３４に何らかのノードが保存さているかを判定する（ステップ２０７）。訪問済みノード記憶部３４に何も保存されていない場合、探索ノード決定２５は、ステップ２０６で決定された受信ノードを探索ノードとして決定し、この受信ノードを訪問済みノード記憶部３４に保存する（ステップ２０８）。ここで設定される受信ノードが第１の探索ノードに相当する。
【００４２】
一方、ステップ２０７の判定で訪問済みノード記憶部３４に何らかのノードが保存されている場合、探索ノード決定部２５は、まだ訪問済みとなっていないノードについて、ノード情報記憶部３５に保存されているノードに対する合計コストと経路を参照する。そして、探索ノード決定部２５は、合計コストが最小のノードを１つ選び、選んだノードを探索ノードとして決定し、訪問済みノード記憶部３４に保存する（ステップ２０９）。ここで設定される探索ノードは第２の探索ノードに相当し、第２の探索ノードは、送信ノードまたは上記計算順序が上位の受信ノードにおける経路計算で設定された経路上のノードに一致するまで更新される。
【００４３】
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１（第１の合計コストに相当）を計算する（ステップ２１０）。合計コストＣ１は、
Ｃ１＝Ｉｄ＊Ｃ（ｖ）＋ｗ（ｖ，ｕ）・・・（式１）
で求まる。
【００４４】
（式１）において、Ｉｄは、探索ノードが受信ノードの１つであれば０であり、そうでなければ１である。Ｃ（ｖ）は、探索ノードｖの合計コストである。ｗ（ｖ，ｕ）は、探索ノードと隣接ノード間のリンクのコスト値である。Ｃ（ｖ）は、ノード情報記憶部３５に保存されている値を用いる。ノード情報記憶部３５に探索ノードｖが保存されていない場合、Ｃ（ｖ）は０である。
【００４５】
次に、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣ（第２の合計コストに相当）が既に保存されているかどうかを判定する（ステップ２１１）。合計コストＣが保存されていない場合、経路パラメータ判定部２７は、ノード情報記憶部３５の隣接ノードｕに、Ｃ１と、経路を示す情報として探索ノードの識別子とを一緒にして保存する。ステップ２１１の判定で既にＣが保存されている場合、経路パラメータ判定部２７は、Ｃ１＜Ｃかどうかを判定する（ステップ２１２）。Ｃ１＜Ｃである場合、経路パラメータ判定部２７は、ノード情報記憶部３５の隣接ノードｕに、Ｃ１と経路（探索ノード）の識別子の情報を上書きする（ステップ２１３）。
【００４６】
経路パラメータ判定部２７は、探索ノードに対する隣接ノード全てに対し、Ｃ１の計算が行われるまで、ステップ２１０〜ステップ２１３の処理を繰り返す（ステップ２１４）。ステップ２１４で、Ｃ１の計算を行っていない隣接ノードがなければ、経路パラメータ判定部２７は、探索ノードが経路記憶部３３に保存されているか否かを判定し（ステップ２１５）、探索ノードが経路記憶部３３に保存されていなければ、ステップ２０７〜ステップ２１４の処理を繰り返す。
【００４７】
ステップ２１５で探索ノードが経路記憶部３３に保存されているノードであれば、経路保存部２８は、ノード情報記憶部３５を参照し、探索ノードから受信ノードまでの経路を、ノードを経路順に並べた情報として、経路記憶部３３に保存する。つまり、経路保存部２８は、経路情報として、探索ノードから受信ノードまでの経路における各ノードの識別子を経路順に並べた情報を、経路記憶部３３に保存する。この経路は、ノード情報記憶部３５の各ノードに保存されている経路（ノード）をたどることで得られる。
【００４８】
このようにして、ステップ２０１で取得した識別子の全ての受信ノードの経路の情報が、経路記憶部３３に保存されるまで、初期化部２３が実行するステップ２０５〜経路保存部２８が実行するステップ２１６までの処理を繰り返す（ステップ２１７）。
【００４９】
全ての受信ノードの経路の情報が経路記憶部３３に保存されたら、最後に、経路出力部２９が、経路記憶部３３に保存されている経路の情報を出力することで（ステップ２１８）、処理が終了する。
【００５０】
次に、上述した本実施形態のマルチキャスト経路計算方法の具体例を、図６を参照して説明する。図６はネットワークトポロジの一構成例を示す図である。
【００５１】
図６に示す例では、ノードの識別子を１〜１６のノード番号としている。ノード間のリンク上の数値はコスト値を表している。
【００５２】
はじめに、要求取得部２１がトポロジ情報を外部から取得する。各ノードの接続関係、各リンクのコスト値は、図６に示すとおりである。次に、要求取得部２１は、送信ノードと複数の受信ノードの識別子を外部から取得する。本具体例では、送信ノードを図６に示すノード１とする。また、受信ノードの数は５個とし、受信ノードＡを図６に示すノード９とし、受信ノードＢをノード１０とし、受信ノードＣをノード１３とし、受信ノードＤをノード１２とし、受信ノードＥをノード１５とする。要求取得部２１は、トポロジ情報をトポロジ情報記憶部３１に保存し、送信ノードと受信ノードＡ〜Ｅの識別子を送信・受信ノード記憶部３２に保存する。さらに、要求取得部２１は、送信ノードの識別子を経路記憶部３３に保存する。
【００５３】
次に、計算順序決定部２２が、送信ノードから各受信ノードまでの最小合計コストを計算する。本具体例において、各受信ノードの最小合計コストは、受信ノードＡが３、受信ノードＢが５、受信ノードＣが６、受信ノードＤが９、受信ノードＥが１０となる。計算順序決定部２２は、これらのコスト値を比較し、最小合計コストが小さい方から順に、以下に示すように、計算順序を決定する。
１位：受信ノードＡ
２位：受信ノードＢ
３位：受信ノードＣ
４位：受信ノードＤ
５位：受信ノードＥ
計算順序決定部２２は、これらの最小合計コストと順位の情報を送信・受信ノード記憶部３２における、それぞれの受信ノードの識別子の情報に関連付けて保存する。
【００５４】
図７Ａから図９Ｂは、第１の実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。図７Ａから図８Ａに示す黒三角印は探索ノードを示し、図７Ａから図９Ｂにおいて、ノードの脇に記述された四角の中のＣとＲの情報は、ノード情報記憶部３５に保存される情報を示す。
【００５５】
初期化部２３が、訪問済みノード記憶部３４とノード情報記憶部３５の情報を削除する。ただし、最初はデータが格納されていないため、この処理を行う必要はない。次に、計算受信ノード決定部２４が、経路記憶部３３に保存されていない受信ノードの中で、計算順序最上位の受信ノードを決定する。ただし、最初は、経路記憶部３３には、送信ノードの識別子しか保存されていないため、計算順序最上位の受信ノードが決定される。本具体例では、受信ノードＡが選択される。
【００５６】
次に、探索ノード決定部２５が、訪問済みノード記憶部３４に何らかのノードが保存さているかを判定する。最初は何も保存されていないため、ステップ２０６で決定された受信ノードＡを探索ノードとして決定し、受信ノードＡを訪問済みノード記憶部３４に保存する（図７Ａ）。
【００５７】
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１を計算する。ここでは、ノード９（受信ノードＡ）が探索ノードｖに相当し、ノード５、ノード６、ノード１０およびノード１３が隣接ノードｕに相当する。
【００５８】
さらに、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣが既に保存されているかどうかを判定する。最初は、合計コストＣが保存されていないため、ノード情報記憶部３５の隣接ノードｕに、Ｃ１および、経路として、探索ノードの識別子を保存する（図５に示したステップ２１３）。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図７Ｂ）。図７Ｂにおいて、合計コストをＣ、経路の目印として探索ノードの識別子をＲで示す。また、図７Ａから図９Ｂの各図において、経路記憶部３３および訪問済みノード記憶部３４のそれぞれに保存される、ノードの識別子を破線枠の中に示す。
【００５９】
続いて、図５に示したステップ２１５において、探索ノードが経路記憶部３３に保存されていないので、探索ノード決定の処理（図５に示したステップ２０７）に戻る。
【００６０】
探索ノード決定部２５が、訪問済みノード記憶部３４を参照し、ノードが保存されているため、訪問済みとなっていないノードについて、ノード情報記憶部３５に保存されているノードに対する合計コストと経路を参照し、合計コストが最小のノードを１つ選ぶ。ここでは、合計コストが２のノード５が探索ノードとして選択され、訪問済みノード記憶部３４に保存される（図７Ｃ）。
【００６１】
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１を計算する。ここでは、ノード５が探索ノードｖに相当し、ノード１、ノード２、ノード６およびノード９が隣接ノードｕに相当する。
【００６２】
さらに、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣが既に保存されているかどうかを判定する。保存されていないノードには、ノード情報記憶部３５の隣接ノードｕに、Ｃ１および、経路として、探索ノードを保存する。一方、既に、Ｃが保存されているノードにおいては、Ｃ１＜Ｃの場合、Ｃ１を新たなＣとして、また、探索ノードを経路として保存する。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図７Ｄ）。図７Ｄに示すように、ノード１およびノード２については、Ｃ１と経路として探索ノード（ノード５）とが保存され、ノード６およびノード９については情報が更新されなかった。
【００６３】
続いて、図５に示したステップ２１５において、探索ノードが経路記憶部３３に保存されていないので、探索ノード決定の処理（図５に示したステップ２０７）に戻る。
【００６４】
探索ノード決定部２５が、訪問済みノード記憶部３４を参照し、ノードが保存されているため、訪問済みとなっていないノードについて、ノード情報記憶部３５に保存されているノードに対する合計コストと経路を参照し、合計コストが最小のノードを１つ選ぶ。ここでは、合計コストが３のノード１が探索ノードとして選択され、訪問済みノード記憶部３４に保存される（図８Ａ）。ここで、合計コスト３のノードが複数あるが、そのような場合、ノード番号が最も小さいノードを選択することとした。
【００６５】
ノード１の識別子が経路記憶部３３に保存されているため、図４および図５に示したステップ２０７からステップ２１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＡまでの経路の情報が保存される（図８Ｂ）。ここで、探索ノードから受信ノードＡまでの経路の情報は、具体的には、送信ノード１、ノード５およびノード９の識別子が順に並んだ情報である。図８Ｂでは、保存された経路の情報に相当する経路を太線で示している。
【００６６】
経路記憶部３３には全ての受信ノードの識別子が保存されていないため、初期化部２３の処理（図４に示したステップ２０５）に戻る。初期化部２３は、訪問済みノード記憶部３４とノード情報記憶部３５の情報を削除する（図８Ｃ）。
【００６７】
次に、計算受信ノード決定部２４が、送信・受信ノード記憶部３２を参照し、次の計算対象の受信ノードとして、受信ノードＢを選択する。
【００６８】
受信ノードＢについて、探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を、受信ノードＡと同様に繰り返すと、探索ノードがノード１０、ノード６、ノード１１、ノード１３、ノード９の順に決定される。
【００６９】
ノード９の識別子が経路記憶部３３に保存されているため、図４および図５に示したステップ２０７からステップ２１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＢまでの経路が保存される（図８Ｄ）。ここで、ノード１３が探索ノードとして決定されたとき、経路パラメータ計算部２６において、Ｃ１の計算式（式１）では、Ｉｄが０にセットされることに注意が必要である。また、このとき、探索ノードに相当するノード９から受信ノードＢに相当するノード１０までの経路情報として、ノード９、ノード１３およびノード１０が順に並んだ情報が経路記憶部３３に保存される。つまり、受信ノードＣの識別子が経路記憶部３３に保存される。
【００７０】
経路記憶部３３に全ての受信ノードの識別子が保存されていないため、初期化部２３の処理（図４に示したステップ２０５）に戻る。初期化部２３は、訪問済みノード記憶部３４とノード情報記憶部３５の情報を削除する。次に、計算受信ノード決定部２４が、送信・受信ノード記憶部３２を参照し、次の計算対象の受信ノードとして、受信ノードＤを選択する。１つ前の順位である受信ノードＣは、受信ノードＢからの経路に含まれているため、受信ノードＣからの経路探索は行われない。
【００７１】
受信ノードＤについて、探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を、受信ノードＡと同様に繰り返すと、探索ノードがノード１２、ノード１１、ノード１５、ノード１４、ノード１６、ノード７、ノード１０の順に決定される。ここで、ノード１５が探索ノードとして決定されたとき、経路パラメータ計算部２６において、Ｃ１の計算式（式１）では、Ｉｄが０にセットされることに注意が必要である。
【００７２】
ノード１０の識別子が経路記憶部３３に保存されているため、図４および図５に示したステップ２０７からステップ２１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＤまでの経路が保存される（図９Ａ）。
【００７３】
経路記憶部３３に全ての受信ノードの識別子が保存されていないため、初期化部２３の処理（図４に示したステップ２０５）に戻る。初期化部２３は、訪問済みノード記憶部３４とノード情報記憶部３５の情報を削除する。次に、計算受信ノード決定部２４が、送信・受信ノード記憶部３２を参照し、次の計算対象の受信ノードとして、受信ノードＥを選択する。
【００７４】
受信ノードＥについて、探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を、受信ノードＡと同様に繰り返すと、探索ノードがノード１５、ノード１４、ノード１６、ノード１２の順に決定される。
【００７５】
ノード１２の識別子が経路記憶部３３に保存されているため、図４および図５に示したステップ２０７からステップ２１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＥまでの経路が保存される（図９Ｂ）。
【００７６】
経路記憶部３３に全ての受信ノードの識別子が保存されたため、最後に経路出力部２９が経路記憶部３３を参照し、マルチキャスト経路を、例えば以下のように出力し、処理を終了する。
受信ノードＡへの経路：１、５、９
受信ノードＢへの経路：１、５、９、１３、１０
受信ノードＣへの経路：１、５、９、１３
受信ノードＤへの経路：１、５、９、１３、１０、１１、１２
受信ノードＥへの経路：１、５、９、１３、１０、１１、１２、１６、１５
【００７７】
本実施形態によれば、受信ノードから送信ノードへ、また、受信ノードから既に確定した経路へ、最小の合計コストで経路を接続させていくことで、１つの経路に複数の受信ノードが乗り、マルチキャスト経路全体の合計コストを低く抑えることができる。また、送信ノードと受信ノードの全ての組み合わせのフルメッシュ経路を計算する場合よりも計算量が少なく済む。
【００７８】
また、本実施形態では、ある受信ノードからの経路探索の途中で他の受信ノードが発見されると、合計コストをゼロにリセットする場合を説明したが、必ずしもゼロにリセットしなくてもよい。このとき合計コストをゼロにリセットすることにより、他の受信ノードを経由する経路が優先的に選択されるため、さらにマルチキャスト経路全体の合計コストを最小限に抑えることが可能になる。
【００７９】
（第２の実施形態）
本実施形態のマルチキャスト経路計算装置の構成を説明する。
【００８０】
図１０は、本実施形態のマルチキャスト経路計算装置の一構成例を示すブロック図である。なお、本実施形態では、第１の実施形態と異なる点を詳細に説明し、第１の実施形態と同様な構成についてはその詳細な説明を省略する。
【００８１】
本実施形態のマルチキャスト経路計算装置３００は、第１の実施形態で説明した初期化部２３と計算受信ノード決定部２４の処理が異なる。本実施形態では、図１０に示すように、第１の実施形態における初期化部２３と計算受信ノード決定部２４の処理順序が逆転し、初期化部２３の代わりに情報更新部４１が設けられている。
【００８２】
情報更新部４１は、計算受信ノード決定部２４で決定された受信ノード（受信ノードｄとする）の１つ前の順位の受信ノード（受信ノードｄ’とする）からの経路探索において、受信ノードｄからの経路が計算されている場合に、その経路と合計コストの情報を含む経路探索情報を訪問済みノード記憶部３４とノード情報記憶部３５に残し、それ以外の情報を削除する。
【００８３】
図１１および図１２は、本実施形態におけるマルチキャスト経路計算方法の動作手順を示すフローチャートである。
【００８４】
本実施形態におけるマルチキャスト経路計算方法は、図１０で示したマルチキャスト経路計算装置の構成に対応して、第１の実施形態で説明した初期化ステップ（ステップ２０５）と計算受信ノード決定ステップ（ステップ２０６）の順序が逆になり、初期化ステップ（ステップ２０５）の代わりに情報更新ステップ（ステップ３０６）を有する。
【００８５】
図４に示したステップ２０６は図１１に示すステップ３０５に相当し、図４に示したステップ２０１〜２０４およびステップ２０７〜２０９のそれぞれは図１１に示すステップ３０１〜３０４およびステップ３０７〜３０９のそれぞれに相当しており、同様な処理についての詳細な説明を省略する。また、図５に示したステップ２１０〜ステップ２１８のそれぞれは図１１に示すステップ３１０〜ステップ３１８に相当し、同様な処理についての詳細な説明を省略する。
【００８６】
本実施形態のマルチキャスト経路計算装置３００の動作の具体例について、第１の実施の形態と異なる部分を詳しく説明する。ここでも、ネットワークトポロジの一例として、図６に示したトポロジを用いる。
【００８７】
第１の実施形態で説明した動作を例に説明する。受信ノードＡからの経路探索終了後、計算受信ノード決定部２４が、探索ノードとして、計算順序次位の受信ノードである受信ノードＢに決定する。受信ノードＡからの経路探索では、受信ノードＢからの経路は計算されていないため、図１１に示すステップ３０６において、情報更新部４１は、訪問済みノード記憶部３４とノード情報記憶部３５の全ての情報を削除する。
【００８８】
次に、受信ノードＢからの経路探索終了後、計算受信ノード決定部２４が、探索ノードとして、計算順序次位の受信ノードである受信ノードＤに決定する。１つ前の順位である受信ノードＣは、受信ノードＢからの経路に含まれているため、受信ノードＣからの経路探索は行われていない。したがって、この場合にも、情報更新部４１は、訪問済みノード記憶部３４とノード情報記憶部３５の全ての情報を削除する。
【００８９】
受信ノードＤからの経路計算について、情報更新ステップ以降の処理を、具体的に説明する。図１３Ａから図１５Ｂは本実施形態におけるマルチキャスト経路計算方法の具体例を説明するための図である。
【００９０】
探索ノード決定部２５が、受信ノードＤを探索ノードとして決定し、受信ノードＤの識別子を訪問済みノード記憶部３４に保存する（図１３Ａ）。
【００９１】
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１を計算する。さらに、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣが既に保存されているかどうかを判定する。最初は保存されていないため、ノード情報記憶部３５の隣接ノードｕに、Ｃ１および、経路として、探索ノードの識別子を保存する。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図１３Ｂ）。図１３Ｂにおいて、合計コストをＣ、経路の目印として探索ノードの識別子をＲで示す。
【００９２】
探索ノードが経路記憶部３３に保存されていないので、探索ノード決定の処理（図１１に示すステップ３０７）に戻る。
【００９３】
探索ノード決定部２５が、訪問済みノード記憶部３４を参照し、ノードが保存されているため、訪問済みとなっていないノードについて、ノード情報記憶部３５に保存されているノードに対する合計コストと経路を参照し、合計コストが最小のノードを１つ選ぶ。ここでは、合計コストが２のノード１１が探索ノードとして選択され、訪問済みノード記憶部３４に保存される（図１３Ｃ）。
【００９４】
次に、経路パラメータ計算部２６が、探索ノードｖの隣接ノードｕについて、探索ノード経由の合計コストＣ１を計算する。さらに、経路パラメータ判定部２７が、ノード情報記憶部３５を参照し、隣接ノードｕに対して、他のノード経由の合計コストＣが既に保存されているかどうかを判定する。保存されていないノードには、ノード情報記憶部３５の隣接ノードｕに、Ｃ１および、経路として、探索ノードの識別子を保存する。既に、Ｃが保存されているノードにおいては、Ｃ１＜Ｃの場合、Ｃ１を新たなＣとして、また、探索ノードを経路として保存する。経路パラメータ計算と、経路パラメータ判定の処理を全ての隣接ノードに対して行う（図１３Ｄ）。
【００９５】
上記の探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を繰り返すと、探索ノードがノード１２、ノード１１、ノード１５、ノード１４、ノード１６、ノード７、ノード１０の順に決定される。ここで、ノード１５が探索ノードとして決定されたとき、経路パラメータ計算部２６において、Ｃ１の計算式（式１）では、Ｉｄが０にセットされることに注意が必要である（図１４Ａ〜図１４Ｃ）。
【００９６】
ノード１０の識別子が経路記憶部３３に保存されているため、図１１および図１２に示すステップ３０７からステップ３１５までの繰り返し処理が終了し、経路記憶部３３に探索ノードから受信ノードＤまでの経路が保存される（図１４Ｄ）。
【００９７】
経路記憶部３３に全ての受信ノードの識別子が保存されていないため、計算受信ノード決定部２４の処理に戻る。計算受信ノード決定部２４が、送信・受信ノード記憶部３２を参照し、次の計算対象の受信ノードとして、受信ノードＥを選択する。
【００９８】
次に、図１１に示したステップ３０６において、情報更新部４１が、受信ノードＤからの経路探索において、受信ノードＥからの経路が計算されているかを判定する。つまり、受信ノードＥの識別子が訪問済みノード記憶部３４に格納されており、受信ノードＥを経由して探索されたノードの識別子が訪問済みノード記憶部３４に格納されているかどうかを判定する。
【００９９】
受信ノードＥの識別子が訪問済みノード記憶部３４に格納されている場合には、情報更新部４１は、受信ノードＥと受信ノードＥから探索された訪問済みノードの識別子を、訪問済みノード記憶部３４に残し、それ以外のノードの識別子を削除する。また、情報更新部４１は、受信ノードＥを経由して探索された訪問済みノードに関する情報をノード情報記憶部３５に残し、それ以外のノードに関する情報を削除する。本動作例では、ノード１５、ノード１４、ノード１６が訪問済みノード記憶部３４に残され、ノード１４とノード１６の情報がノード情報記憶部３５に残される（図１５Ａ）。経路パラメータ計算部２６は、ノード１５、ノード１４およびノード１６の経路探索情報を利用することが可能となる。
【０１００】
これ以降は、受信ノードＤと同様に、探索ノード決定、経路パラメータ計算、および経路パラメータ判定の処理を繰り返すと、探索ノードがノード１２と決定され、経路計算が完了する（図１５Ｂ）。
【０１０１】
第１の実施形態では、受信ノードＥから新たに経路計算を行ったが、本実施形態では、ノード１４とノード１６への経路探索を行う必要がなく、計算量が少なくてすむ。経路出力部２９が出力する経路の情報は、第１の実施形態と同じになる。
【０１０２】
本実施形態によれば、第１の実施形態と同様にマルチキャスト経路全体の合計コストを最小限に抑えられるだけでなく、ある受信ノードからの経路計算において、並行して計算された、次の計算順位の受信ノードからの経路を、次の受信ノードからの経路計算時に流用することで、計算量の低減を図ることが可能である。
【０１０３】
なお、上述した第１または第２の実施形態で説明した動作をプログラムとして構築し、そのプログラムをマルチキャスト経路計算装置として利用されるコンピュータにインストールして実行させる、または、そのプログラムをネットワークを介して流通させることが可能である。
【０１０４】
また、構築されたプログラムを、コンピュータ読み取り可能なディスク装置や、ＣＤ−ＲＯＭ等の搬送可能な記憶媒体に格納し、コンピュータにインストールして実行させる、または、配布することが可能である。
【０１０５】
本発明は、上記の実施形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【０１０６】
１００、２００、３００ マルチキャスト経路計算装置
１ 要求取得手段
２ 計算順序決定手段
４ 探索ノード決定手段
５ 経路パラメータ計算手段
６ 経路パラメータ判定手段
７ 経路保存手段
８ 経路出力手段
１１ 経路記憶手段
１２ 訪問済みノード記憶手段
１３ ノード情報記憶手段
２０ 制御部
３０ 記憶部
【特許請求の範囲】
【請求項１】
ネットワーク内の各ノードに対応する識別子、隣接するノード同士を接続する経路および各経路のコスト値の情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードのそれぞれの識別子の情報を取得し、
前記複数の受信ノードについて経路計算の順位を決め、
決定した順位の最上位の受信ノードから最下位の受信ノードまで順に第１の探索ノードに設定し、
設定した第１の探索ノード毎に、該第１の探索ノードの隣接ノードについて、該第１の探索ノードと該隣接ノードの間のコスト値を合計コストとし、該合計コストが最小となる隣接ノードを第２の探索ノードとし、該第２の探索ノードが前記送信ノード、または該第１の探索ノードよりも前記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致するまで、前記第１の探索ノードから該第２の探索ノードを経由して該第２の探索ノードの隣接ノードまでの前記合計コストが最小となる隣接ノードを第２の探索ノードに順次更新することで、前記第１の探索ノードから更新された第２の探索ノードを順に結ぶ経路を設定し、
前記第２の探索ノードについて前記隣接ノードの前記合計コストを算出する際、該第２の探索ノードが前記複数の受信ノードのうち、いずれかの受信ノードと一致する場合、該第２の探索ノードまでの前記合計コストをゼロにリセットし、該第２の探索ノードを起点とする経路のコスト値を前記合計コストとする、経路計算方法。
【請求項２】
請求項１記載の経路計算方法において、
前記第１の探索ノードの前記隣接ノードおよび前記合計コスト、ならびに前記第２の探索ノードの前記隣接ノードおよび前記合計コストの情報を含む経路探索情報を保存し、
決定した順位のうち、任意の順位の受信ノードの経路計算を行う際、該任意の順位よりも上位の順位の受信ノードの経路計算の過程で保存された前記経路探索情報を利用する、経路計算方法。
【請求項３】
請求項１または２記載の経路計算方法において、
前記複数の受信ノードについて経路計算の順位を決める際、前記複数の受信ノードのそれぞれについて、前記送信ノードから該受信ノードに至るまでの経路の前記合計コストのうち最小値である最小合計コストを求め、該最小合計コストが最も小さい受信ノードを前記最上位の受信ノードとし、該最小合計コストが最も大きい受信ノードを前記最下位の受信ノードとする、経路計算方法。
【請求項４】
ネットワーク内の各ノードに対応する識別子、隣接するノード同士を接続する経路および各経路のコスト値の情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードのそれぞれの識別子の情報を保存する記憶手段と、
前記要求取得手段から受け取る前記複数の受信ノードについて経路計算の順位を決める計算順序決定手段と、
前記計算順序決定手段が決定した順位の最上位の受信ノードから最下位の受信ノードまで順に第１の探索ノードに設定し、設定した第１の探索ノード毎に、該第１の探索ノードの隣接ノードについて、該第１の探索ノードと該隣接ノードの間のコスト値を合計コストとし、該合計コストが最小となる隣接ノードを第２の探索ノードとし、前記第１の探索ノードから該第２の探索ノードを経由して該第２の探索ノードの隣接ノードまでの前記合計コストが最小となる隣接ノードを第２の探索ノードに順次更新する経路パラメータ計算手段と、
前記第２の探索ノードが前記送信ノード、または該第１の探索ノードよりも前記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致すると、前記第１の探索ノードから更新された第２の探索ノードを順に結ぶ経路を設定する経路パラメータ判定手段と、を有し、
前記経路パラメータ計算手段は、
前記第２の探索ノードについて前記隣接ノードの前記合計コストを算出する際、該第２の探索ノードが前記複数の受信ノードのうち、いずれかの受信ノードと一致する場合、該第２の探索ノードまでの前記合計コストをゼロにリセットし、該第２の探索ノードを起点とする経路のコスト値を前記合計コストとする、経路計算装置。
【請求項５】
請求項４記載の経路計算装置において、
前記経路パラメータ判定手段は、
前記経路パラメータ計算手段が出力する、前記第１の探索ノードの前記隣接ノードおよび前記合計コスト、ならびに前記第２の探索ノードの前記隣接ノードおよび前記合計コストの情報を含む経路探索情報を前記記憶手段に保存し、
前記経路パラメータ計算手段は、
決定した順位のうち、任意の順位の受信ノードの経路計算を行う際、該任意の順位よりも上位の順位の受信ノードの経路計算の過程で前記記憶手段に保存された前記経路探索情報を利用する、経路計算方法。
【請求項６】
請求項４または５記載の経路計算装置において、
前記計算順序決定手段は、
前記複数の受信ノードについて経路計算の順位を決める際、前記複数の受信ノードのそれぞれについて、前記送信ノードから該受信ノードに至るまでの経路の前記合計コストのうち最小値である最小合計コストを求め、該最小合計コストが最も小さい受信ノードを前記最上位の受信ノードとし、該最小合計コストが最も大きい受信ノードを前記最下位の受信ノードとする、経路計算装置。
【請求項７】
請求項１から３のいずれか１項記載の経路計算方法をコンピュータに実行させるためのプログラム。
【請求項１】
ネットワーク内の各ノードに対応する識別子、隣接するノード同士を接続する経路および各経路のコスト値の情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードのそれぞれの識別子の情報を取得し、
前記複数の受信ノードについて経路計算の順位を決め、
決定した順位の最上位の受信ノードから最下位の受信ノードまで順に第１の探索ノードに設定し、
設定した第１の探索ノード毎に、該第１の探索ノードの隣接ノードについて、該第１の探索ノードと該隣接ノードの間のコスト値を合計コストとし、該合計コストが最小となる隣接ノードを第２の探索ノードとし、該第２の探索ノードが前記送信ノード、または該第１の探索ノードよりも前記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致するまで、前記第１の探索ノードから該第２の探索ノードを経由して該第２の探索ノードの隣接ノードまでの前記合計コストが最小となる隣接ノードを第２の探索ノードに順次更新することで、前記第１の探索ノードから更新された第２の探索ノードを順に結ぶ経路を設定し、
前記第２の探索ノードについて前記隣接ノードの前記合計コストを算出する際、該第２の探索ノードが前記複数の受信ノードのうち、いずれかの受信ノードと一致する場合、該第２の探索ノードまでの前記合計コストをゼロにリセットし、該第２の探索ノードを起点とする経路のコスト値を前記合計コストとする、経路計算方法。
【請求項２】
請求項１記載の経路計算方法において、
前記第１の探索ノードの前記隣接ノードおよび前記合計コスト、ならびに前記第２の探索ノードの前記隣接ノードおよび前記合計コストの情報を含む経路探索情報を保存し、
決定した順位のうち、任意の順位の受信ノードの経路計算を行う際、該任意の順位よりも上位の順位の受信ノードの経路計算の過程で保存された前記経路探索情報を利用する、経路計算方法。
【請求項３】
請求項１または２記載の経路計算方法において、
前記複数の受信ノードについて経路計算の順位を決める際、前記複数の受信ノードのそれぞれについて、前記送信ノードから該受信ノードに至るまでの経路の前記合計コストのうち最小値である最小合計コストを求め、該最小合計コストが最も小さい受信ノードを前記最上位の受信ノードとし、該最小合計コストが最も大きい受信ノードを前記最下位の受信ノードとする、経路計算方法。
【請求項４】
ネットワーク内の各ノードに対応する識別子、隣接するノード同士を接続する経路および各経路のコスト値の情報を含むトポロジ情報、ならびに送信ノードおよび複数の受信ノードのそれぞれの識別子の情報を保存する記憶手段と、
前記要求取得手段から受け取る前記複数の受信ノードについて経路計算の順位を決める計算順序決定手段と、
前記計算順序決定手段が決定した順位の最上位の受信ノードから最下位の受信ノードまで順に第１の探索ノードに設定し、設定した第１の探索ノード毎に、該第１の探索ノードの隣接ノードについて、該第１の探索ノードと該隣接ノードの間のコスト値を合計コストとし、該合計コストが最小となる隣接ノードを第２の探索ノードとし、前記第１の探索ノードから該第２の探索ノードを経由して該第２の探索ノードの隣接ノードまでの前記合計コストが最小となる隣接ノードを第２の探索ノードに順次更新する経路パラメータ計算手段と、
前記第２の探索ノードが前記送信ノード、または該第１の探索ノードよりも前記順位が上位の受信ノードにおける経路計算で設定された経路上のノードに一致すると、前記第１の探索ノードから更新された第２の探索ノードを順に結ぶ経路を設定する経路パラメータ判定手段と、を有し、
前記経路パラメータ計算手段は、
前記第２の探索ノードについて前記隣接ノードの前記合計コストを算出する際、該第２の探索ノードが前記複数の受信ノードのうち、いずれかの受信ノードと一致する場合、該第２の探索ノードまでの前記合計コストをゼロにリセットし、該第２の探索ノードを起点とする経路のコスト値を前記合計コストとする、経路計算装置。
【請求項５】
請求項４記載の経路計算装置において、
前記経路パラメータ判定手段は、
前記経路パラメータ計算手段が出力する、前記第１の探索ノードの前記隣接ノードおよび前記合計コスト、ならびに前記第２の探索ノードの前記隣接ノードおよび前記合計コストの情報を含む経路探索情報を前記記憶手段に保存し、
前記経路パラメータ計算手段は、
決定した順位のうち、任意の順位の受信ノードの経路計算を行う際、該任意の順位よりも上位の順位の受信ノードの経路計算の過程で前記記憶手段に保存された前記経路探索情報を利用する、経路計算方法。
【請求項６】
請求項４または５記載の経路計算装置において、
前記計算順序決定手段は、
前記複数の受信ノードについて経路計算の順位を決める際、前記複数の受信ノードのそれぞれについて、前記送信ノードから該受信ノードに至るまでの経路の前記合計コストのうち最小値である最小合計コストを求め、該最小合計コストが最も小さい受信ノードを前記最上位の受信ノードとし、該最小合計コストが最も大きい受信ノードを前記最下位の受信ノードとする、経路計算装置。
【請求項７】
請求項１から３のいずれか１項記載の経路計算方法をコンピュータに実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７Ａ】
【図７Ｂ】
【図７Ｃ】
【図７Ｄ】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図８Ｄ】
【図９Ａ】
【図９Ｂ】
【図１０】
【図１１】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１３Ｄ】
【図１４Ａ】
【図１４Ｂ】
【図１４Ｃ】
【図１４Ｄ】
【図１５Ａ】
【図１５Ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７Ａ】
【図７Ｂ】
【図７Ｃ】
【図７Ｄ】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図８Ｄ】
【図９Ａ】
【図９Ｂ】
【図１０】
【図１１】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１３Ｄ】
【図１４Ａ】
【図１４Ｂ】
【図１４Ｃ】
【図１４Ｄ】
【図１５Ａ】
【図１５Ｂ】
【公開番号】特開２０１３−５０７９（Ｐ２０１３−５０７９Ａ）
【公開日】平成２５年１月７日（２０１３．１．７）
【国際特許分類】
【出願番号】特願２０１１−１３２０５１（Ｐ２０１１−１３２０５１）
【出願日】平成２３年６月１４日（２０１１．６．１４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２５年１月７日（２０１３．１．７）
【国際特許分類】
【出願日】平成２３年６月１４日（２０１１．６．１４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]