(57)【要約】【課題】広域かつ多数のノードからなるオーバーレイネットワークにおいて品質の制御や設備の効率的利用を実現する。【解決手段】各ノード１は、オーバーレイネットワーク上で所属するクラスタを自律的に決定し、論理ネットワーク構成情報１１０を作成するクラスタ決定部１２と、所属クラスタに隣接するクラスタ内の任意のノードとの間で距離情報を定期的に測定し、測定した情報をリンク情報１１１とするリンク情報測定部１３と、他ノードとの間でリンク情報１１１を送受信するリンク情報送受信部１４と、リンク情報に基づいてトポロジ情報を作成し、トポロジ情報に基づいてルーティングテーブル１１３を作成するルーティングテーブル作成部１５と、ルーティングテーブル１１３に従ってパケット転送を行う経路制御部１６とを備える。【選択図】  図２
2010199972.tif 000002
【特許請求の範囲】
【請求項１】
各ノード装置がオーバーレイネットワーク上で所属するクラスタを自律的に決定し、所属クラスタと隣接クラスタとを記述した論理ネットワーク構成情報を作成するクラスタ決定手順と、
各ノード装置が前記論理ネットワーク構成情報に基づいて所属クラスタに隣接するクラスタ内の任意のノード装置との間で距離情報を定期的に測定し、測定した情報をリンク情報とするリンク情報測定手順と、
各ノード装置が他ノード装置との間で前記リンク情報を送受信するリンク情報送受信手順と、
各ノード装置が自ノード装置で測定したリンク情報および他ノード装置から受信したリンク情報に基づいてトポロジ情報を作成し、このトポロジ情報に基づいてルーティングテーブルを作成するルーティングテーブル作成手順と、
各ノード装置が前記ルーティングテーブルに従ってパケット転送を行う経路制御手順とを備えることを特徴とする経路制御方法。
【請求項２】
請求項１記載の経路制御方法において、
前記クラスタ決定手順は、ネットワーク品質に基づいて自ノード装置の所属クラスタを定期的に見直し、前記論理ネットワーク構成情報を更新する手順を含むことを特徴とする経路制御方法。
【請求項３】
請求項１記載の経路制御方法において、
前記リンク情報送受信手順は、他ノード装置から送信された前記リンク情報を受信すると共に、他ノード装置に対して検索要求を送出することにより、不足しているリンク情報を取得する手順を含むことを特徴とする経路制御方法。
【請求項４】
請求項１記載の経路制御方法において、
前記ルーティングテーブル作成手順は、受信した複数のリンク情報のうち測定時刻が最も新しい情報を採用して前記トポロジ情報を作成するか、あるいは受信した複数のリンク情報を統計処理して前記トポロジ情報を作成する手順を含むことを特徴とする経路制御方法。
【請求項５】
請求項１記載の経路制御方法において、
前記経路制御手順は、前記ルーティングテーブルに従って転送先のノード装置宛にパケットを転送すると同時に、任意のクラスタに属するノード装置を前記転送先のノード装置と同等とし、この任意のクラスタに属するノード装置宛にも前記パケットを転送する手順を含むことを特徴とする経路制御方法。
【請求項６】
オーバーレイネットワーク上で自ノード装置が所属するクラスタを自律的に決定し、所属クラスタと隣接クラスタとを記述した論理ネットワーク構成情報を作成するクラスタ決定手段と、
前記論理ネットワーク構成情報に基づいて所属クラスタに隣接するクラスタ内の任意のノード装置との間で距離情報を定期的に測定し、測定した情報をリンク情報とするリンク情報測定手段と、
他ノード装置との間で前記リンク情報を送受信するリンク情報送受信手段と、
自ノード装置で測定したリンク情報および他ノード装置から受信したリンク情報に基づいてトポロジ情報を作成し、このトポロジ情報に基づいてルーティングテーブルを作成するルーティングテーブル作成手段と、
前記ルーティングテーブルに従ってパケット転送を行う経路制御手段とを備えることを特徴とするノード装置。
【請求項７】
請求項６記載のノード装置において、
前記クラスタ決定手段は、ネットワーク品質に基づいて自ノード装置の所属クラスタを定期的に見直し、前記論理ネットワーク構成情報を更新することを特徴とするノード装置。
【請求項８】
請求項６記載のノード装置において、
前記リンク情報送受信手段は、他ノード装置から送信された前記リンク情報を受信すると共に、他ノード装置に対して検索要求を送出することにより、不足しているリンク情報を取得することを特徴とするノード装置。
【請求項９】
請求項６記載のノード装置において、
前記ルーティングテーブル作成手段は、受信した複数のリンク情報のうち測定時刻が最も新しい情報を採用して前記トポロジ情報を作成するか、あるいは受信した複数のリンク情報を統計処理して前記トポロジ情報を作成することを特徴とするノード装置。
【請求項１０】
請求項６記載のノード装置において、
前記経路制御手段は、前記ルーティングテーブルに従って転送先のノード装置宛にパケットを転送すると同時に、任意のクラスタに属するノード装置を前記転送先のノード装置と同等とし、この任意のクラスタに属するノード装置宛にも前記パケットを転送することを特徴とするノード装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット等の広域ネットワークやセンサーネットワーク等の超多ノード環境において、コネクティビティの確保や品質向上、トラヒック制御を行うための経路制御方法およびノード装置に関するものである。
【背景技術】
【０００２】
従来の経路制御においては、比較的小規模な狭いネットワークについては静的（スタティック）な経路制御方式が用いられる。中規模のネットワークでは、ブロードキャストやＲＩＰ（Routing Information Protocol）のようなプロトコルもよく用いられている。
【０００３】
少し大規模なネットワーク（数百ノード程度）では、ＯＳＰＦ（Open Shortest Path First）やＩＳ−ＩＳ（Intermediate System to Intermediate System）が主に用いられるが、ノード数の増加に伴いスケーラビリティに課題を抱えることがある。そこで、経路テーブルをノード間で互いに共有したり、区切られたＯＳＰＦ／ＩＳ−ＩＳ領域を相互に静的に接続したりする方式もスケーラビリティ向上のために採用される。
【０００４】
さらに大規模なインターネット領域になると、ＢＧＰ（Border Gateway Protocol）によりネットワーク間を相互接続することが定められている。
このように、広域かつ多ノードなネットワークでは、現在のところ前述したように階層型の制御を行うＯＳＰＦ／ＢＧＰが主に用いられている。
【０００５】
図５にインターネットルーティングの階層構造を示す。図５は、比較的小規模な狭いネットワークの領域１００では、静的な経路制御が用いられ、少し大規模なネットワークの領域１０１では、ＯＳＰＦやＩＳ−ＩＳが用いられ、さらに大規模なネットワークの領域１０２では、ＢＧＰが用いられることを示している。
【０００６】
一般的なリンクステート型の経路制御システムの処理の流れを図６に示す。各ルータ２００は、他のルータ２００と接続するリンク２０１を持つ。このルータ２００とリンク２０１とからなるネットワークを表す情報を物理ネットワーク情報とする。各ルータ２００は、この物理ネットワーク情報を予め保持している。
各ルータ２００は、隣接するルータ２００との接続情報（接続の有無やリンクの品質）を測定／取得する（ステップＳ１）。この測定／取得した情報をリンク情報とする。
【０００７】
続いて、各ルータ２００は、リンク情報を他のルータ２００へ送信する（ステップＳ２）。このリンク情報の送信をＯＳＰＦではフラッディングと呼ぶ。
次に、各ルータ２００は、収集したリンク情報を基にトポロジ情報を作成し、ダイクストラ（Dijkstra）アルゴリズム等に基づきルーティングテーブル２０２を作成する（ステップＳ３）。
そして、各ルータ２００は、パケットをルーティングテーブル２０２に従って転送する（ステップＳ４）。
【０００８】
以上のような既存手法においては階層が固定的であるため、最短経路探索や、輻輳を回避する経路探索、リソース利用の最適化等、なんらかの指標に基づく最適化を行う場合、その最適化範囲は部分的なものに留まり、その仕組み上、局所的な最適化しか実現することができない。
広域での最適化を可能とする手法として、オーバーレイルーティングが提案されている（非特許文献１参照）。オーバーレイルーティングとは、オーバーレイネットワークで行われるアプリケーションレベルの経路制御のことである。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】長谷川剛，「オーバーレイルーティングとネットワークただ乗り問題」，ＪＡＮＯＧ２２  Ｍｅｅｔｉｎｇ，Ｊｕｌ，２００８
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、オーバーレイルーティングは、今のところ一箇所で集中的に経路計算をする仕組みになっており、広域には対応できても、多ノード化・大規模化には対応できないという問題点があった。
【００１１】
本発明の目的は、上述の問題点に鑑み、広域かつ多数のノードからなるオーバーレイネットワークにおいて品質の制御や設備の効率的利用を実現することにある。
【課題を解決するための手段】
【００１２】
本発明の経路制御方法は、各ノード装置がオーバーレイネットワーク上で所属するクラスタを自律的に決定し、所属クラスタと隣接クラスタとを記述した論理ネットワーク構成情報を作成するクラスタ決定手順と、各ノード装置が前記論理ネットワーク構成情報に基づいて所属クラスタに隣接するクラスタ内の任意のノード装置との間で距離情報を定期的に測定し、測定した情報をリンク情報とするリンク情報測定手順と、各ノード装置が他ノード装置との間で前記リンク情報を送受信するリンク情報送受信手順と、各ノード装置が自ノード装置で測定したリンク情報および他ノード装置から受信したリンク情報に基づいてトポロジ情報を作成し、このトポロジ情報に基づいてルーティングテーブルを作成するルーティングテーブル作成手順と、各ノード装置が前記ルーティングテーブルに従ってパケット転送を行う経路制御手順とを備えることを特徴とするものである。
また、本発明の経路制御方法の１構成例において、前記クラスタ決定手順は、ネットワーク品質に基づいて自ノード装置の所属クラスタを定期的に見直し、前記論理ネットワーク構成情報を更新する手順を含むことを特徴とするものである。
また、本発明の経路制御方法の１構成例において、前記リンク情報送受信手順は、他ノード装置から送信された前記リンク情報を受信すると共に、他ノード装置に対して検索要求を送出することにより、不足しているリンク情報を取得する手順を含むことを特徴とするものである。
また、本発明の経路制御方法の１構成例において、前記ルーティングテーブル作成手順は、受信した複数のリンク情報のうち測定時刻が最も新しい情報を採用して前記トポロジ情報を作成するか、あるいは受信した複数のリンク情報を統計処理して前記トポロジ情報を作成する手順を含むことを特徴とするものである。
また、本発明の経路制御方法の１構成例において、前記経路制御手順は、前記ルーティングテーブルに従って転送先のノード装置宛にパケットを転送すると同時に、任意のクラスタに属するノード装置を前記転送先のノード装置と同等とし、この任意のクラスタに属するノード装置宛にも前記パケットを転送する手順を含むことを特徴とするものである。
【００１３】
また、本発明のノード装置は、オーバーレイネットワーク上で自ノード装置が所属するクラスタを自律的に決定し、所属クラスタと隣接クラスタとを記述した論理ネットワーク構成情報を作成するクラスタ決定手段と、前記論理ネットワーク構成情報に基づいて所属クラスタに隣接するクラスタ内の任意のノード装置との間で距離情報を定期的に測定し、測定した情報をリンク情報とするリンク情報測定手段と、他ノード装置との間で前記リンク情報を送受信するリンク情報送受信手段と、自ノード装置で測定したリンク情報および他ノード装置から受信したリンク情報に基づいてトポロジ情報を作成し、このトポロジ情報に基づいてルーティングテーブルを作成するルーティングテーブル作成手段と、前記ルーティングテーブルに従ってパケット転送を行う経路制御手段とを備えることを特徴とするものである。
【発明の効果】
【００１４】
本発明によれば、オーバーレイネットワーク上のノードをクラスタ化し、クラスタ単位での自律分散型の経路制御を行うことにより、広域かつ多数のノードからなるネットワークにおいて、リンクステートベースのルーティングインフラを構築することが可能となり、各種品質の制御や設備の効率的利用を実現することができる。
【００１５】
また、本発明では、各ノードがネットワーク品質に基づいて所属クラスタを定期的に見直すことにより、例えばネットワーク品質が極端に悪化した時などにクラスタ構成を適切かつ自律的に見直すことができる。
【００１６】
また、本発明では、他ノード装置から送信されたリンク情報を受信すると共に、他ノード装置に対して検索要求を送出することにより、不足しているリンク情報を取得することにより、広域かつ多数のノードからなるネットワークに対応することができる。
【００１７】
また、本発明では、受信した複数のリンク情報のうち測定時刻が最も新しい情報を採用してトポロジ情報を作成するか、あるいは受信した複数のリンク情報を統計処理してトポロジ情報を作成することにより、リンク情報の信頼性、網羅性が低い場合であっても、より適切なトポロジ情報を作成することができる。
【００１８】
また、本発明では、ルーティングテーブルに従って転送先のノード装置宛にパケットを転送すると同時に、任意のクラスタに属するノード装置を転送先のノード装置と同等とし、この任意のクラスタに属するノード装置宛にもパケットを転送することにより、フォワーディングの信頼性を向上させることができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施の形態に係るオーバーレイネットワークの構成を示すブロック図である。
【図２】本発明の実施の形態に係るオーバーレイネットワークに参加する各ノードの構成を示すブロック図である。
【図３】本発明の実施の形態に係るオーバーレイネットワークに参加する各ノードの経路制御動作を示すフローチャートである。
【図４】本発明の実施の形態におけるリンク情報の取得の様子を示す図である。
【図５】インターネットルーティングの階層構造を示す図である。
【図６】リンクステート型の経路制御システムの処理の流れを示す図である。
【発明を実施するための形態】
【００２０】
以下、本発明の実施の形態について図面を参照して説明する。図１は本発明の実施の形態に係るオーバーレイネットワークの構成を示すブロック図である。
オーバーレイネットワークは、ＩＰネットワークなどの広域ネットワーク上に論理的に形成される。オーバーレイネットワークは、多数のノード装置（以下、ノードと略する）１−ａ，１−ｂ，１−ｃ，１−ｄ，１−ｅをその構成要素として持つ。各ノード１は、ハッシュ値等により生成された固有の識別情報であるノードｉｄを有する。
【００２１】
オーバーレイネットワークは、複数のクラスタ２（２−Ｘ，２−Ｙ，２−Ｚ）に分かれる。すなわち、オーバーレイネットワークに参加した各ノード１は、いずれかのクラスタ２に所属する。各クラスタ２は、固有の識別情報であるクラスタｉｄを有する。本実施の形態では、ルーティングの単位として、このクラスタ２を用いる。各クラスタ２は、隣接クラスタ２と接続する仮想的な論理リンク３（３−ＸＹ，３−ＹＺ）を持つものとする。
【００２２】
図１のオーバーレイネットワークに参加する各ノード１の構成を図２に示す。各ノード１は、それぞれオーバーレイネットワークと接続するためのネットワーク接続部１０と、情報を記憶する記憶部１１と、オーバーレイネットワーク上で自ノード１が所属するクラスタ２を自律的に決定し、論理ネットワーク構成情報を作成するクラスタ決定部１２と、所属クラスタ２に隣接するクラスタ２内の任意のノード１との間で距離情報を定期的に測定し、測定した情報をリンク情報とするリンク情報測定部１３と、他ノード１との間でリンク情報を送受信するリンク情報送受信部１４と、リンク情報に基づいてトポロジ情報を作成し、トポロジ情報に基づいてルーティングテーブルを作成するルーティングテーブル作成部１５と、ルーティングテーブルに従ってパケット転送を行う経路制御部１６とを有する。
【００２３】
次に、本実施の形態の経路制御動作について説明する。図３は各ノード１の経路制御動作を示すフローチャートである。
最初に、各ノード１は、以下のような論理ネットワーク構成情報１１０を取得して保持している（ステップＳ１００）。図１の例は、３つのクラスタ２−Ｘ，２−Ｙ，２−Ｚが存在し、クラスタ２−Ｘと２−Ｙ間、クラスタ２−Ｙと２−Ｚ間にそれぞれ論理リンク３−ＸＹ，３−ＹＺが存在する状態を示している。
【００２４】
図１の例の場合、クラスタ２−Ｘに所属するノード１に注目すると、このノード１が保持する論理ネットワーク構成情報１１０は、以下のようになる。
（所属クラスタｉｄ，（隣接クラスタリスト））
＝（所属クラスタｉｄ，（隣接クラスタｉｄ−１，隣接クラスタｉｄ−２，・・・））
＝（ｉｄ−Ｘ，（ｉｄ−Ｙ））
【００２５】
ｉｄ−Ｘ，ｉｄ−Ｙはそれぞれクラスタ２−Ｘ，２−Ｙのクラスタｉｄである。オーバーレイネットワ−クにおいては、ネットワーク構造は可変である。例えば各ノード１は、リンク情報が極端に悪化した時などに所属クラスタを自律的に見直すことが考えられる（文献１「亀井聡，川原亮一，“大規模ネットワークの自律クラスタ化手法の提案”，電子情報通信学会総合大会講演論文集，Ｖｏｌ．２００７年  通信，Ｎｏ．２（２００７０３０７），ｐ．１１０，２００７／０３」参照）。このように、自律的に所属クラスタを決定する処理を行うのが各ノード１のクラスタ決定部１２である。
【００２６】
上記文献１によると、各クラスタ２には代表ノード１−ｒが存在する。各代表ノード１−ｒのクラスタ決定部１２は、代表ノード間で定期的にフルメッシュ測定を実施する。測定対象としてはネットワーク品質（例えば遅延時間）がある。各代表ノード１−ｒのクラスタ決定部１２は、測定結果ベクトルを保持する。
【００２７】
新規ノード１がオーバーレイネットワークに参加する場合、新規ノード１のクラスタ決定部１２は、クラスタ毎の代表ノード１−ｒを探索し、全代表ノード１−ｒとの間でネットワーク品質を測定し、測定結果ベクトルを保持する。新規ノード１のクラスタ決定部１２は、自身が保持する測定結果ベクトルを各代表ノード１が保持する測定結果ベクトルと比較し、ベクトル間距離が最も近い代表ノード１−ｒが所属するクラスタ２に自らを所属させる。こうして、所属クラスタが決まると、新規ノード１のクラスタ決定部１２は、上記のような論理ネットワーク構成情報１１０を作成して記憶部１１に格納する。
【００２８】
また、オーバーレイネットワークに参加している各ノード１は、新規ノードと同様に定期的にネットワーク品質を測定し、自身の所属クラスタを決定する。所属クラスタの決定により、各ノード１のクラスタ決定部１２は、論理ネットワーク構成情報１１０を更新する。
【００２９】
代表ノード１−ｒを決定するには、まずランダムに初期代表ノード１−ｒを配置し、各ノード毎に上記のように所属クラスタを決定した後、各クラスタ２で重心ノードを求め、この重心ノードを新代表ノード１−ｒとする。重心の計算には、ベクトル間距離を用い、各クラスタ２においてベクトル間距離の合計が最小になるノード１を重心ノードとする。そして、各ノード１のクラスタ決定部１２は、代表ノード１−ｒの決定と自身の所属クラスタの決定とを繰り返す。
【００３０】
以上により、各ノード１は、所属クラスタ２を決定し、論理ネットワーク構成情報１１０を作成・更新することができる。この論理ネットワーク構成情報１１０は、従来の物理ネットワーク情報に相当するものである。
【００３１】
次に、各ノード１のリンク情報測定部１３は、論理ネットワーク構成情報１１０に基づいてリンク情報１１１を測定し、測定したリンク情報１１１を記憶部１１に格納する（ステップＳ１０１）。具体的には、各ノード１のリンク情報測定部１３は、所属クラスタに隣接するクラスタ内の任意のノードとの間で距離情報（遅延時間等）を定期的に測定する。さらに、リンク情報測定部１３は、このときの測定時刻も取得する。リンク情報１１１の形式は以下のようになる。
（測定元ノードｉｄ，測定元クラスタｉｄ，測定先ノードｉｄ，測定先クラスタｉｄ，  距離情報，測定時刻）
【００３２】
リンク情報１１１の測定の際には、ランダムに相手を選択する等して、同一クラスタ間のリンクにおいて複数のリンク情報１１１を取得するようにしてもよい。
図４の例のように、クラスタ２−Ｙに所属するノード１−ａからクラスタ２−Ｘに所属するノード１−ｂに対して測定を行うと、リンク情報１１１は以下のようになる。
（ｉｄ−ａ，ｉｄ−Ｙ，ｉｄ−ｂ，ｉｄ−Ｘ，距離情報，測定時刻）
【００３３】
ｉｄ−ａ，ｉｄ−ｂはそれぞれノード１−ａ，１−ｂのノードｉｄである。リンク情報１１１は、従来のステップＳ１で取得するリンク情報に相当するものである。
【００３４】
続いて、各ノード１のリンク情報送受信部１４は、リンク情報１１１を他のノード１へ送信し、また他のノード１からリンク情報１１１を受信する（ステップＳ１０２）。リンク情報送受信部１４は、他のノード１から受信した情報をリンク情報１１２として記憶部１１に格納する。
【００３５】
リンク情報の送信については、従来のように全リンク情報を広域伝播（ブロードキャスト）させるのは現実的ではないことから、リンク情報をある程度ランダムに伝播させる方法と、このランダムに伝播するリンク情報でオーバーレイネットワーク全体をカバーできていないときに不足しているリンク情報を能動的に取得しに行く方法とを組み合わせることが現状では現実的である。このような処理は、Ｐ２Ｐ（Peer to Peer）の検索システムであるウィニー（Winny ）等において見られる（文献２「“ｗｉｎｎｙ．ｉｎｆｏ  キー配布”，ｈｔｔｐ：／／ｗｉｎｎｙ．ｉｎｆｏ／ｋｅｙ．ｈｔｍｌ」参照）。文献２によると、各ノード１は、隣接ノード１に情報を送信し、不足している情報については検索要求を送出することによりネットワーク全体から情報を取得する。
以上のステップＳ１０２の処理は、従来のステップＳ２に相当するものである。
【００３６】
次に、各ノード１のルーティングテーブル作成部１５は、リンク情報１１１，１１２を基にルーティングテーブル１１３を作成する（ステップＳ１０３）。具体的には、ルーティングテーブル作成部１５は、リンク情報１１１，１１２に基づいて、任意の２つのノード間の経路と経路のコスト（本実施の形態では遅延）とを表すトポロジ情報（経路情報）を作成し、ダイクストラアルゴリズム等に基づきルーティングテーブル１１３を作成する。
【００３７】
本実施の形態では、リンク情報１１１，１１２が完全にはフラッディングされないため、情報取得の課程が必要となる。具体的には，上記のステップＳ１０２で説明したように、一定確率に基づきランダムに伝播したリンク情報と検索要求によりオ−バーレイネットワーク全体から収集したリンク情報とを基にトポロジ情報を作成し、ルーティングテーブル１１３を作成することになる。
【００３８】
ルーティングテーブル１１３を作成するにあたっては、従来と比較してリンク情報１１１の信頼性、網羅性が低いことから、トポロジ情報の作成には注意を要する。すなわち、ルーティングテーブル作成部１５は、トポロジ情報を作成する際には、測定元ノードｉｄが同一で、測定元クラスタｉｄが同一で、測定先ノードｉｄが同一で、かつ測定先クラスタｉｄが同一の複数のリンク情報１１１のうち、測定時刻が最も新しいものを用いる。
【００３９】
また、ルーティングテーブル作成部１５は、リンク情報１１１に対して何らかの統計処理を行ってトポロジ情報を作成するようにしてもよい。統計処理としては、例えば測定元ノードｉｄが同一で、測定元クラスタｉｄが同一で、測定先ノードｉｄが同一で、かつ測定先クラスタｉｄが同一の複数のリンク情報１１１からそれぞれ距離情報を抽出して、距離情報の平均値を求めることが考えられる。また、この複数のリンク情報１１１に含まれる測定時刻の現在時刻に対する近さに応じて、これらのリンク情報１１１に含まれる距離情報の重み付け平均を求めるようにしてもよい。この場合は、現在時刻に近いほど加重が重くなるようにする。
【００４０】
作成したトポロジ情報においては、任意の２つのノード間について複数の経路が存在する場合がある。そこで、経路上のリンクのコストを何らかの方法で評価して、最適な経路を計算し、ルーティングテーブル１１３を作成する必要がある。本実施の形態では、最適な経路計算方法として、例えばダイクストラアルゴリズムを使用する。ダイクストラアルゴリズムは、経路上のリンクのコスト（本実施の形態では遅延）を合計して、合計値が最小である経路あるいは最大である経路を選択する経路計算方法である。こうして、ルーティングテーブル作成部１５は、任意の２つのノード間の最適経路を表すルーティングテーブル１１３を作成する。
以上のステップＳ１０３の処理は、従来のステップＳ３に相当するものである。
【００４１】
次に、各ノード１の経路制御部１６は、作成したルーティングテーブル１１３に従ってフォワーディング（パケット転送）を行う（ステップＳ１０４）。このフォワーディングについては、ノード１の信頼性が低いこと等の理由から注意を要する。具体的には、経路制御部１６は、ルーティングテーブル１１３に従って転送先のノード１宛にパケットを転送すると同時に、任意のクラスタ２に属するノード１を転送先のノード１と同等とし、この任意のクラスタ２に属するノード１宛にも同じパケットを転送すればよい。
【００４２】
パケットを受信したノード１の経路制御部１６は、自身宛のパケットの場合は、このパケットを記憶部１１に格納し、自身宛のパケットでない場合は、ルーティングテーブル１１３に従ってパケットを転送する。こうして、フォワーディングの信頼性を上げることができる。
以上のステップＳ１０４の処理は、従来のステップＳ４に相当するものである。
【００４３】
以上のように、本実施の形態では、オーバーレイネットワーク上のノードをクラスタ化し、クラスタ単位での自律分散型の経路制御を行うことにより、広域かつ多数のノードからなるネットワークにおいて、リンクステートベースのルーティングインフラを構築することが可能となり、各種品質の制御や設備の効率的利用を実現することができる。
【００４４】
本実施の形態で説明したノード１は、ＣＰＵ、記憶装置およびインタフェースを備えたコンピュータと、これらのハードウェア資源を制御するプログラムによって実現することができる。各ノード１のＣＰＵは、記憶装置に格納されたプログラムに従って本実施の形態で説明した処理を実行する。
【産業上の利用可能性】
【００４５】
本発明は、インターネット等の広域ネットワークやセンサーネットワーク等の超多ノード環境に適用することができる。
【符号の説明】
【００４６】
１…ノード、２…クラスタ、３…論理リンク、１０…ネットワーク接続部、１１…記憶部、１２…クラスタ決定部、１３…リンク情報測定部、１４…リンク情報送受信部、１５…ルーティングテーブル作成部、１６…経路制御部、１１０…論理ネットワーク構成情報、１１１，１１２…リンク情報、１１３…ルーティングテーブル。
【図１】
2010199972.tif 000003
【図２】
2010199972.tif 000004
【図３】
2010199972.tif 000005
【図４】
2010199972.tif 000006
【図５】
2010199972.tif 000007
【図６】
2010199972.tif 000008