(57)【要約】各ノードはあらかじめ自ノードの性能、資源に応じて自ノードの最大リンク数を設定しておき、ネットワーククラスタに接続を試みるノードは、ネットワーククラスタを構成するノードの使用リンク数と最大リンク数を含むノード基本情報から実際に接続するノードを決定する。
2004066569.tif 000002
【特許請求の範囲】
【請求項１】
他の装置と通信してネットワークを構成する通信装置であって、
ネットワーク上に存在するノードの最大リンク数と現状リンク数を含むノード基本情報を保持する記憶部と、
前記基本情報に基きリンクを確立する相手ノードの候補を選択する選択部とを
備えたことを特徴とする通信装置。
【請求項２】
前記選択部は、現状リンク数が最大リンク数を超えていないノードの中で、現状リンク数が最大のノードをリンク相手ノードの候補とすることを特徴とする請求項１の通信装置。
【請求項３】
請求項１において更に、他の装置との通信リンクを確立するリンク生成部を備え、該リンク生成部は前記選択部が選択した相手装置と、各装置が既に所属するネットワークを構成しているノード群のノード名と宛先を含むネットワーク情報を互いに交換することを特徴とする通信装置。
【請求項４】
請求項１において更に、他のノードとの通信リンクを確立するリンク生成部を備え、該リンク生成部は他のノードから接続要求を受けた場合に、自装置の現状リンク数と最大リンク数とを比較し、現状リンク数が最大リンク数を超えていない場合に接続許可応答を他のノードに送信してリンクを確立することを特徴とする通信装置。
【請求項５】
請求項３において更に、リンク管理部を備え、該リンク管理部は確立されたリンクを使用してネットワーク情報を送受信し、前記リンクを通じて取得したネットワーク情報を、前記リンクに関連付けて保持することを特徴とする通信装置。
【請求項６】
前記リンク管理部は、前記リンクを通じて取得したネットワーク情報と当該通信装置が前記リンクに関連付けて保持しているネットワーク情報が同一内容の場合には、ネットワーク情報の再送信を抑止することを特徴とする請求項５の通信端末。
【請求項７】
前記リンク管理部は、前記リンクを通じて取得したネットワーク情報を当該通信装置が既に保持していたネットワーク情報とマージし、前記リンク以外のリンクに対してマージ後のネットワーク情報を再送信することを特徴とする請求項５の通信装置。
【請求項８】
前記リンク管理部は、確立済みリンクが消滅したことを検出したときに、消滅したリンクに関連つけていたネットワーク情報を消去することを特徴とする請求項５の通信装置。
【請求項９】
前記リンク管理部は、リンクによって形成される経路に閉路が形成されたとき、前記閉路を構成するすべてのノード間リンクのＩＤを、前記すべてのノード上で同一の結果が得られる方法で計算することによって、前記閉路を構成する通信端末間リンクの中から１つのリンクを選択し、前記選択を行ったリンクを切断することによって前記閉路を切断することを特徴とする請求項５の通信端末。
【請求項１０】
請求項１の通信端末において、前記記憶部が保持する前記ノード基本情報を定期的にネットワークにブロードキャストすることを特徴とする通信端末。
【請求項１１】
前記リンク管理部は、前記最大リンク数を、ＣＰＵ性能、ネットワーク性能を含むノード性能や、ノードが保持するデータの量、データの質に基づいて決定することを特徴とする請求項１の通信端末。
【請求項１２】
各ノードがリンクを確立する相手ノードを自立的に判断するネットワークシステムにおいて、
前記ノードのそれぞれが、ネットワーク上に存在するノードの最大リンク数と現状リンク数を含むノード基本情報を保持する記憶部と、
前記基本情報に基きリンクを確立する相手ノードの候補を選択する選択部とを
備えることを特徴とするネットワークシステム。
【請求項１３】
前記選択部は、現状リンク数が最大リンク数を超えていないノードの中で、現状リンク数が最大のノードをリンク相手ノードの候補とすることを特徴とする請求項１２のネットワークシステム。
【請求項１４】
請求項１２において、前記ノードは更に他のノードとの通信リンクを確立するリンク生成部を備え、該リンク生成部は前記選択部が選択した相手ノードと、各ノードが既に所属するネットワークを構成しているノード群のノード名と宛先を含むネットワーク情報を互いに交換することを特徴とするネットワークシステム。
【請求項１５】
請求項１２において、前記ノードは更に、他のノードとの通信リンクを確立するリンク生成部を備え、該リンク生成部は他のノードから接続要求を受けた場合に、自装置の現状リンク数と最大リンク数とを比較し、現状リンク数が最大リンク数を超えていない場合に接続許可応答を他のノードに送信してリンクを確立することを特徴とするネットワークシステム。
【請求項１６】
請求項１４において、前記ノードは更にリンク管理部を備え、該リンク管理部は確立されたリンクを使用してネットワーク情報を送受信し、前記リンクを通じて取得したネットワーク情報を、前記リンクに関連付けて保持することを特徴とするネットワークシステム。
【請求項１７】
請求項１２において、前記記憶部が保持する前記ノード基本情報を定期的にネットワークにブロードキャストすることを特徴とするネットワークシステム。
【請求項１８】
前記ネットワークを構成する一部のノードは、当該ノードが保持するネットワーク情報から、ノードの最大リンク数と現状リンク数を含むノード基本情報を生成し、前記ネットワーククラスタを構成するノードのノード基本情報を定期的にブロードキャストすることを特徴とする請求項１２のネットワークシステム。
【請求項１９】
請求項１２において、前記選択部はネットワーククラスタを構成するノードの内、宛先変化が少ないｗｅｌｌ−ｋｎｏｗｎノードにネットワーククラスタを構成するノードのノード基本情報を問い合わせ、前記ｗｅｌｌ−ｋｎｏｗｎノードから受信したノード基本情報からリンクを確立する相手ノードの候補を選択することを特徴とするネットワークシステム。
【請求項２０】
各ノードがリンクを確立する相手ノードを自立的に判断するネットワークシステムにおいて、
各ノードにネットワーク上に存在するノードの最大リンク数と現状リンク数を含むノード基本情報を保持し、
前記基本情報に基きリンクを確立する相手ノードの候補を選択することを特徴とするリンク生成方法。
【請求項２１】
前記選択ステップは、現状リンク数が最大リンク数を超えていないノードの中で、現状リンク数が最大のノードをリンク相手ノードの候補とすることを特徴とする請求項２０のリンク生成方法。
【請求項２２】
請求項２１において更に、前記選択部が選択した相手ノードと、各ノードが既に所属するネットワークを構成しているノード群のノード名と宛先を含むネットワーク情報を互いに交換することを特徴とするリンク生成方法。
【請求項２３】
請求項２０において更に、他のノードから接続要求を受けた場合に、自装置の現状リンク数と最大リンク数とを比較し、現状リンク数が最大リンク数を超えていない場合に接続許可応答を他のノードに送信してリンクを確立することを特徴とするリンク生成方法。
【発明の詳細な説明】
【技術分野】  本発明は、Ｐ２Ｐ（Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ）型自立分散システムに関し、特にネットワークの形成方法に関する。
【背景技術】  通信に集中型サーバが介在せず、ネットワーク上のノード同士が直接通信するＰ２Ｐ型ネットワークシステムにおいては、ネットワーク全体を対象とした検索処理を行う場合等、検索要求メッセージをネットワーク全体にブロードキャストする必要がある。通常ブロードキャスト処理は、検索要求メッセージ等をノードからノードへ転送していく方法で行われている。このような処理を可能とするため、ネットワーク上のすべてのノードがリンクを通じて互いに接続されているような、ノード間リンクを形成し、上記リンクに基づいた適切なメッセージルーティングを行う必要がある。
リンクの形成方法として、Ａ  Ｓｃａｌａｂｌｅ  Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｎｅｔｗｏｒｋ（ＳＩＧＣＯＭＭ  ２００１  Ｐｒｏｃｅｅｄｉｎｇ）には仮想空間のタイル状分割を考えることによってリンクを形成するノードを選択するアルゴリズムが論じられている。また特開２００２−１７１２８３号公報ではＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）装置を用いて、地理的に近接するノード同士が上記リンクを形成する方法が開示される。
Ｐ２Ｐ型ネットワークシステムでは、ノードの移動、消滅時にネットワークトポロジを変更する必要がある。特に無線ＬＡＮに代表されるモバイル環境ではネットワークトポロジ変更が頻繁に起こる。Ａ  Ｓｃａｌａｂｌｅ  Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｎｅｔｗｏｒｋでは、ノード消滅時等のネットワークトポロジ変更処理が複雑である。
また、通常上記リンクとしてＴＣＰリンクを利用するが、計算機資源が貧弱な小型端末ではＴＣＰリンクの使用数の上限が厳しい。たとえＴＣＰリンク数に余裕があったとしても、リンク数を制限しなければ特定端末への集中アクセスが発生し、性能劣化を招く恐れがある。従って、リンク数制御はＰ２Ｐ型ネットワークシステムにおいて重要であるが、従来技術ではこれらの問題が考慮されておらず、端末ごとにリンク数を設定することができない。
ホップ数（あるメッセージを送信するときのメッセージ転送回数）がなるべく少なくなるようなノード間リンクを容易に形成することも十分考慮されていない。
さらに特開２００２−１７１２８３号公報では、リンクを確立するノードを選択するときに物理位置情報を利用しているので、物理位置情報を得る手段を持たないシステムには適用できない。
【発明の開示】
本発明は、ノード生成、消滅時のネットワークトポロジ変化に簡単なアルゴリズムで柔軟に対応することを目的とする。
また、さらにノード間リンク数の制限を考慮したリンクを容易に形成することができるＰ２Ｐネットワークシステムを提供することを目的とする。
本発明の他の目的は、メッセージ転送に必要なホップ数ができるだけ小さくなるような最適なネットワークトポロジを、Ｐ２Ｐネットワークシステムにおいて自動生成することにある。
本発明では、Ｐ２Ｐ型ネットワークシステムにおいて、第１ノードが第２ノードとリンクを確立するときに、ネットワーク上に存在するノードの最大リンク数と現状リンク数を含むノード基本情報から第２ノードを決定する。このリンク確立手段によって、各ノードが使用するリンク数を考慮した効率的なネットワークトポロジの構築が可能となる。
上記ノード基本情報の最大リンク数は、ＣＰＵ性能、ネットワーク性能を含むノード性能やノードが保持するデータの量、データの質から決定し、各ノードに保持させておく。これにより、リンク数を制限すべき端末の制限リンク数を考慮したネットワークトポロジを容易に確立することや、負荷に耐え得る高性能端末にアクセスを集中するなどの端末性能を考慮したネットワーク制御やアプリケーションの効率化を図ることが可能になる。
また、ノード基本情報に基き、現状リンク数が最大リンク数を超えていない新規ノードの中で、現状リンク数が最大のノードをリンク確立の相手ノードとして選択することでメッセージ転送に必要なホップ数を小さくできる。
また本発明では、ネットワーククラスタを構成する各ノードは、ネットワーククラスタ内ノードのノード名と宛先を含むネットワーク情報を、互いに交換することによって前記ネットワーククラスタ内のルーティング情報を最新に保つ。このネットワーク情報は、ノード間リンクが確立されたとき、及びノード間リンクが消滅したとき、を契機としてノード間リンクを使用してネットワーククラスタ全体に転送される。ルーティングを効率的に行うために、上記ネットワーク情報には目的のノードに到達するまでのノード間リンクのホップ数を含ませる。
更に本発明は、各ノードが前記ノード基本情報をブロードキャストすることによって、ブロードキャストが到達する範囲に存在するノード同士が、確実に互いを認識しノード間リンクを確立することを可能とする。
また本発明の変形例では、上記ネットワーク情報にノード基本情報を含めることによって、ネットワーククラスタ全体にそのネットワーククラスタを構成するノードのノード基本情報をノード間リンクを使用して転送する。そして、上記ネットワーククラスタを構成するノードの一部が、前記ノード基本情報をブロードキャストする。ブロードキャスト処理を行うノードを制限することによって、ネットワーク負荷を抑えることができる。ブロードキャスト処理を行うノードは前記ネットワーク情報から決定する。
また本発明の別の変形例では、ｗｅｌｌ−ｋｎｏｗｎノードにネットワーククラスタを構成するノードのノード基本情報を問い合わせることにより、上記ブロードキャスト処理を不要とする。
【図面の簡単な説明】図１は、本発明の実施例におけるノードの構成を示す図。
図２は、ノード群の接続状態を模式的に示す図。
図３は、ノード基本情報テーブルを示す図。
図４（ａ）、図４（ｂ）は、あるノード内に生成されるリンクオブジェクトを示す図。
図５は、ノード間リンク生成処理を示すフローチャート１。
図６は、ノード間リンク生成処理を示すフローチャート２。
図７は、接続要求のデータ構造を示す図。
図８は、接続応答のデータ構造を示す図。
図９は、別のノード内に構成されるリンクオブジェクトを示す図。
図１０は、別のリンクオブジェクトを示す図。
図１１（ａ）、図１１（ｂ）は、あるノードが送信するネットワーク情報更新メッセージを示す図。
図１２は、ネットワーク情報更新メッセージ転送処理を表すフローチャート。
図１３（ａ）、図１３（ｂ）、図１３（ｃ）は、別のノード内に構成されるリンクオブジェクトを示す図。
図１４は、別のネットワーク情報更新メッセージを示す図。
図１５は、ノード消滅時のノード間リンク削除処理を示す図。
図１６（ａ）、図１６（ｂ）は、別のネットワーク情報更新メッセージを示す図。
図１７（ａ）は、アプリケーションメッセージの送信処理を示すフローチャート。
図１７（ｂ）は、アプリケーションメッセージの受信処理を示すフローチャート。
【発明を実施するための最良の形態】
【実施例１】  以下、本発明の実施例を図面を用いて詳細に説明する。図１はノード１０１の一例としての携帯端末のハードウェア構成と、各ノードが備えるノード管理のためのソフトウェア構成を示す。
記憶装置１０７に格納されるノード管理プログラム１０２は、メッセージ処理部１０３、リンク生成部１０４とリンク管理部とを含む。メッセージ処理部１０３は、ノード間リンクを通して送られてきたメッセージを、実際にメッセージ処理を行うコンポーネントに配送する。例えば、上記メッセージがノード間リンク管理用制御メッセージの場合リンク管理部１０５に配送し、アプリケーション用データメッセージの場合当該アプリケーションに配送する。リンク生成部１０４は、ノード間リンクの生成処理を行う。リンク管理部１０５は、ネットワーク内に存在するノードの基本情報（ノード名、最大リンク数（使用可能な最大リンク数）、使用リンク数（現在使用中のリンク数）、宛先）を保持するノード基本情報テーブルの管理および、リンクオブジェクトの管理を行う。
上記ノード基本情報テーブルは、ノード間リンクを新規確立するときノード間リンク確立相手を選択するヒントとして使用する。リンクオブジェクトはノード間リンクに対応するオブジェクトであり、当該リンクを使用して通信可能なすべてのノードのネットワーク情報（ノード名、ノード間リンクを使用して概ノードに到達するために必要なホップ数、概ノードの宛先）を含む。このリンクオブジェクトは当該ノード間リンクを確立する両ノードに生成される。また、リンクオブジェクトは仮想的なノード間リンクを表すものであり、実際のノード間通信手段は任意（ＴＣＰ、ＵＤＰなどが使用可能）である。
上記最大リンク数はノードごとに設定可能なパラメータである。例えば、より大きな負荷に耐えうるノード（ＣＰＵ性能やネットワーク性能が高いノード）の最大リンク数を通常ノードより大きく設定することによって、性能面での効率化を図ることができる。また、データベースサーバなどのように多くの情報を有するノードや、質の高い情報を有するノードの最大リンク数を大きく設定することで、アプリケーションの効率化を図ることができる。
ＣＰＵ１０８はワークメモリ１０９を経由してノード管理プログラム１０２を記憶装置１０７から順次読み出して実行する。ＣＰＵ１０８が行うデータ処理結果は必要に応じてディスプレイ１１０に可視的に出力される。ノードの処理にユーザの入力が必要なときにはキーボード１１２からユーザの入力を受け取りＣＰＵ１０８で処理する。１１１は他のノードと通信を行うための無線通信装置であり、１１３はノード管理プログラムがＣＤ−ＲＯＭ等の記憶媒体に格納されている場合に、媒体からそれらを読み出して記憶装置に格納する際に使用される。ノードの内部に含まれる各コンポーネントはバス１１４によって相互に通信可能に接続される。図１では携帯端末の構成を示したがノード管理プログラムが動作できる環境であればキーボード、ディスプレイ媒体リーダライタ等はなくてもよい。また本実施例ではノード管理をプログラムとＣＰＵの処理で実現させているが、ノード管理プログラムの各機能モジュールを集積回路化し、ハードウェア回路群で構成してもよい。
図２はノード群のノード間リンクによる結合形態の一例を模式的に示す。実線は既に確立されているノード間リンクを表しており、ノード１からノード５がネットワーククラスタを構成している。ノード６はノード４に接続（以下ノード間リンクを確立することを接続と呼ぶ）しようとしているがまだノード間リンクは確立されていない。このときノード４内には以下に説明するようなノード基本情報テーブルおよびリンクオブジェクトが構成されている。
図３はノード４が保持するノード基本情報テーブル３００を示す。このテーブルは各ノードのリンク管理部がネットワークにブロードキャストするノードの基本情報（ノード名、最大リンク数、使用リンク数、宛先）を、収集することによって生成される。従って、ブロードキャストが到達可能な範囲に存在するノードは、すべて同一のノード基本情報テーブルを保持することになる。上記ノード基本情報テーブル３００では、ノードの宛先としてＨＴＴＰプロトコルによるＵＲＬを使用しているが、これは宛先として使用可能なものであれば何でもよく、例えばＩＰアドレスとポート番号の組だけでもよい。
図４はノード４のリンク管理部が保持するリンクオブジェクトを示している。
リンクオブジェクト４０１はノード４とノード１間に確立されているノード間リンクに対応し、リンクオブジェクト４０２はノード４とノード５間に確立されているノード間リンクに対応する。ノード４から見ると、ノード１の先にノード２とノード３がノード間リンクによって接続されているので、リンクオブジェクト４０１はノード２とノード３の情報も含んでいる。リンクオブジェクト内のどのノードがノード間リンク確立相手であるかは、そのノードのホップ数が１であることから判断できる。各ノードは自分が確立しているノード間リンクに対応するリンクオブジェクトを保持し、リンクオブジェクトは対応するリンクの先にノード間リンクによって接続されているすべてのノードのネットワーク情報を含むので、各ノードは自ノード内のすべてのリンクオブジェクトが含むネットワーク情報を列挙すればネットワーククラスタ内の全ノードを列挙し尽くすことができる。
次に新規ノードがネットワーククラスタに接続する場合のノード間リンク生成処理を、ノード６がノード４に接続する例を用いて説明する。まずノード基本情報テーブル管理処理について説明する。この処理では、ノード間通信手段としてノード間リンクの有無に関係なくすべてのノードが互いに通信可能な手段、例えばブロードキャストアドレスを利用した通信手段を使用する。各ノードのリンク管理部は定期的に自ノードの基本情報をネットワークにブロードキャストする。
ノード６は上記ブロードキャストメッセージを受信すると、当該ノードの情報をノード基本情報テーブルに登録する。また、一定時間上記ブロードキャストメッセージを受信できなかったノードは、ノード基本情報テーブルから削除する。このようにして、ノード６内のノード基本情報テーブルは常に最新に保たれる。例えば、ノード６が図２に示すネットワークに現れると、ノード６内のノード基本情報テーブルは図３のようになる。このノード基本情報テーブル管理処理はすべてのノードで行われるので、すべてのノードは同一のノード基本情報テーブルを保持することになる。
図５はリンク生成部を読み込んで実行しているＣＰＵ１０８の動作を示すフローである。以下、図５を用いてノード６が新規ノード間リンクを生成する過程を説明する。なお、説明の都合上、動作の主体を簡単にリンク生成部と呼ぶこととする（以下の説明のリンク管理部／メッセージ処理部も同様）。ノード６のリンク生成部は、自ノードの使用リンク数が自ノードの最大リンク数より小さいことを確認する。もし使用リンク数≧最大リンク数であれば、リンク生成処理を中止し一定時間待つ（５０１）。次にノード６のリンク生成部は、ネットワーク内に新規ノードが存在するかどうかを確認する。上記新規ノードとは、自ノードのノード基本情報テーブルには含まれるが、いずれのリンクオブジェクトにも含まれていないノードのことである。つまり、自ノードが含まれるネットワーククラスタ内に存在しないが、ノード基本テーブルに含まれるノードが新規ノードとなる。この時点では、ノード６はいずれのノードとも接続していないので、ノード基本情報テーブルに含まれるすべての他ノードが新規ノードとなる（５０３）。
次にノード６のリンク生成部は、ステップ５０３で検出した新規ノードの中から、実際に接続処理を行うノードを選択する。選択方法は、使用リンク数が最大リンク数より小さいノードの内、使用リンク数が最大のものを選択する方法を採る。この選択方法を採用することによって、ノード間リンクによる通信時のホップ数が小さなネットワークトロポジを生成することが可能となる。ノード６は図３に示すようなノード基本情報テーブルを保持するので、ノード６は接続相手として最大リンク数が３（各ノード共通）で使用リンク数が２のノード４を選択する（５０４）。
次にノード６のリンク生成部は、接続相手であるノード４に接続要求７０１を送信する。接続要求７０１のデータ構成を図７に示す。この接続要求は、接続要求送信ノードがその一部であるネットワーククラスタ内の全ノードのネットワーク情報を含む。現時点でノード６はどのノードとも接続していないので、ノード６が含まれるネットワーククラスタは、ノード６のみから構成される。従って、ノード６が送信する接続要求は、ノード６自身のネットワーク情報のみとなっている（５０５）。
上記接続要求を受信したノード４のリンク生成部が接続を許可した場合、ノード４のリンク生成部はノード４内にノード６とのノード間リンクに対応するリンクオブジェクトを生成し、ノード６に接続応答８０１（図８に示す）を返信する。
接続応答８０１は、ノード４がその一部であるネットワーククラスタ内の全ノードのネットワーク情報を含む。ノード４内の詳細な処理については後述する。接続応答８０１を受けたノード６のリンク生成部はノード４とのノード間リンクに対応するリンクオブジェクト９０１を生成する。リンクオブジェクト９０１に登録すべきネットワーク情報は、接続応答８０１内のネットワーク情報のホップ数に１加算することで得られる。もし上記接続応答が接続拒否もしくは応答なしであれば、ノード６のリンク生成部は一定時間待機した後、ステップ５０１に戻る（ステップ５０６から５０８）。
ノード６が既存ノード間リンク（ステップ５０８で生成したリンクオブジェクト以外のリンクオブジェクトに対応するノード間リンク）を確立している場合、ノード６のリンク生成部は、既存ノード間リンクに対してネットワーク情報更新メッセージを送信する。本例では、ノード６は既存ノード間リンクを持たないので、このステップの処理はない。このステップの具体的な処理内容は後述するステップ６０６と同様である。そして一定時間待機した後、ステップ５０１に戻る（５０９）。
ステップ５０２において、次回のリンク生成処理を行うまで一定時間待機するが、この待機時間は使用リンク数、最大リンク数などのパラメータによって変動させてもよい。例えば、（使用リンク数／最大リンク数）に比例させて変動させると、接続個数の少ないノードは他ノードに積極的に接続しようとし、接続個数の多いノードは他ノードからの接続待ち状態になっていることが多くなる。これによってノード間リンク生成処理を効率化できる。また複数のノードが、互いに同時に接続要求を発行する状況を避けるために、上記待機時間の決定に乱数を用いることが望ましい。
次に、ノード６からの接続要求を受信したノード４の処理を図６を用いて説明する。
ノード４のリンク管理部はノード６から接続要求７０１を受信すると、自ノード（ノード４）のリンク生成部が接続要求中（ステップ５０２の待機処理以外の処理を実行中である場合）でないことを確認する。もし接続要求中であれば、ノード６に接続拒否を返信する。この処理は複数のノードが互いに同時に接続要求を送りあったときにも、ノード間リンク生成処理が正常動作するために必要である（ステップ６０１、６０２）。
次にノード４のリンク管理部は、使用リンク数が最大リンク数より小さいことを確認する。もし、（使用リンク数）≧（最大リンク数）であれば（（使用リンク数）＜（最大リンク数）でなければ）、上記リンク管理部は接続拒否を返信する（６０３）。
次にノード４のリンク管理部は、接続要求７０１に含まれるネットワーク情報のホップ数に１加算することによってリンクオブジェクト１００１を生成する。
この結果ノード４は３つのリンクオブジェクト４０１、４０２、１００１を保持することになる（６０４）。
次にノード４のリンク管理部は、リンク要求送信ノード（ノード６）に接続応答８０１を返信する。接続応答８０１には、前ステップで生成したリンクオブジェクト以外のリンクオブジェクトが保持するネットワーク情報と自ノードのネットワーク情報を含める。すなわち、上記接続応答はリンクオブジェクト４０１、４０２が保持するネットワーク情報と自ノードのネットワーク情報を含める（６０５）。
次にノード４のリンク管理部は、既存ノード間リンク（リンクオブジェクト４０１、４０２に対応するノード間リンク）にネットワーク情報更新メッセージを送信する。もし送信すべきノード間リンクが存在しない場合は、上記ネットワーク情報更新メッセージの送信は行わない。上記ネットワーク情報更新メッセージには、送信するノード間リンクに対応するリンクオブジェクト以外のすべてのリンクオブジェクトが含むネットワーク情報と自ノード（ノード４）のネットワーク情報を含める。例えば、リンクオブジェクト４０１に対応するノード間リンクに送信するメッセージには、リンクオブジェクト４０２及び１００１が保持するネットワーク情報を含めるので、ネットワーク情報更新メッセージ１１０１のようになる。同様にノード４のリンク管理部は、リンクオブジェクト４０２に対応するノード間リンクに、ネットワーク情報更新メッセージ１１０２を送信する（６０６）。以上の処理でノード４とノード６間にノード間リンクが確立される。
ノード間リンク確立後、各ノードはネットワーク情報更新メッセージを既存ノード間リンクを使用してネットワーククラスタに転送していく。以下ではこのネットワーク情報更新処理を図１２を参照しつつ、上記具体例を用いて説明する。
ノード４からネットワーク情報更新メッセージ１１０１を受信したノード１のリンク管理部は、自ノード（ノード１）のリンク生成部が接続要求中でないことを確認する。もし接続要求中であれば、接続要求処理が終了するまで待機する（ステップ１２０１から１２０３）。
次にノード１のリンク管理部は、上記ネットワーク更新メッセージ１１０１を受信したノード間リンク（ノード４との間に確立しているノード間リンク）に対応するリンクオブジェクトをいったん廃棄する。そして、ステップ６０４で説明した方法でリンクオブジェクト１３０１を生成する。上記リンクオブジェクト１３０１は先ほど廃棄したリンクオブジェクトに代わる新しいリンクオブジェクトである。この結果、ノード１内のリンクオブジェクトは図１３に示すようになる。
もしリンクオブジェクト内のネットワーク情報に変更がない場合、ネットワーク情報更新処理を終了する（ステップ１２０４、１２０５）。
次にノード１のリンク管理部は、上記ネットワーク更新メッセージ１１０１が送信されてきたリンクオブジェクト以外のリンクオブジェクトに対応するノード間リンクに対して、ネットワーク情報更新メッセージを送信する。もし、送信すべきリンクオブジェクトが存在しない場合は、上記メッセージの送信は行わない。送信するネットワーク情報更新メッセージの作成方法は、ステップ６０６における、ネットワーク情報更新メッセージの作成方法と同様である。例えば、ノード１のリンク管理部はリンクオブジェクト１３０２に対応するノード間リンクに対して、ネットワーク情報更新メッセージ１４０１を送信する。上記リンク管理部は、リンクオブジェクト１３０３に対応するノード間リンクに対しても、同様にネットワーク情報更新メッセージを作成、送信する（ステップ１２０６から１２０８）。
以上説明したように、新規ノードがネットワーククラスタに接続したとき、新規ノード間リンクに対応するリンクオブジェクトが生成された後、既存ノード間リンクを通じてネットワーククラスタ全体にネットワーク情報更新メッセージを転送していく。この結果、ネットワーククラスタを構成するすべてのノード内のリンクオブジェクトは常に最新状態に保たれる。
次にネットワーククラスタからノードが消滅するときの処理について説明する。以下では図１５を参照しつつ、ノード５がネットワーククラスタから消滅する場合を例に説明する。ノード５はネットワークから切断するときに、切断メッセージをノード５が確立済みのノード間リンクに送信する。ノード５とノード間リンクを確立していたノード（ノード４）は上記メッセージを受けることによって、ノード５の切断を検出する。ノードのクラッシュなどによってノード５が上記メッセージを送信できない場合は、ノード４はノード５との通信失敗によってノード５の切断を検出する（１５０１）。
ノード５の消滅を検出したノード４のリンク管理部は、自ノード（ノード４）のリンク生成部が接続要求中でないことを確認する。もし接続要求中であれば、接続要求処理が終了するまで待機する（ステップ１５０２、１５０３）。次にノード４のリンク管理部は、ノード５とのノード間リンクに対応するリンクオブジェクト４０２を削除する（１５０４）。
次にノード４のリンク管理部は、確立済みノード間リンク（リンクオブジェクト４０１、１００１に対応するリンクオブジェクト）に対して、ネットワーク情報更新メッセージを送信する。上記ネットワーク情報更新メッセージの作成方法はステップ６０６での処理と同様である。すなわち、ノード４はネットワーク情報更新メッセージ１６０１をリンクオブジェクト１００１に対応するノード間リンクに送信し、ネットワーク情報更新メッセージ１６０２をリンクオブジェクト４０１に対応するノード間リンクに送信する（ステップ１５０５からステップ１５０７）。
上記ネットワーク情報更新メッセージを受信したノード１、ノード６のリンク管理部は、ステップ１２０１から１２０８の処理を実行する。このように、ネットワーククラスタからノードが消滅した場合、ノード消滅を検出したノードを起点としてネットワーク情報更新メッセージをネットワーククラスタ全体に転送していく。この結果、ネットワーククラスタを構成するすべてのノード内のリンクオブジェクトは常に最新状態に保たれる。
次にノード間リンクを使用して、アプリケーションメッセージ（以下、ＡＰメッセージと呼ぶ）を特定ノードに送信する処理（メッセージルーティング処理）を説明する。メッセージ処理部はＡＰメッセージ送信時、転送経路、宛先ノード名、ＴＴＬ（最大ホップ数）、経路モードから構成されるデータヘッダを付加する。経路モードには、「ホップバイホップモード」と「経路指定モード」の２種類が存在する。「ホップバイホップモード」使用時、ＡＰメッセージを転送する各ノードが転送経路をオンデマンドで経路を決定し、データヘッダ内の転送経路はＡＰメッセージが転送されてきた履歴を意味する。「経路指定モード」使用時、ＡＰメッセージ作成ノードが完全な転送経路を指定するので、データヘッダ内の転送経路はＡＰメッセージがこれから転送されていく経路を表す。通常ＲＰＣ型の通信モデルにおいて、要求メッセージ送信時は宛先ノードまでの経路が不明であるのでホップバイホップモードを使用するが、返答メッセージ送信時は要求メッセージがたどってきた経路履歴から宛先ノードまでの経路を知ることができるので経路指定モードを使用する。
以下、ノード４がノード２にＡＰメッセージをホップバイホップモードで送信する場合を例に挙げて説明する。図１７に処理フローを示す。まず、ノード４のメッセージ処理部は、リンク生成部が保持するリンクオブジェクトからノード２のネットワーク情報を含むリンクオブジェクトを選択する。複数存在する場合は、ホップ数が最小であるようなネットワーク情報を含むリンクオブジェクトを選択する（１７０１）。もし、条件に合うリンクオブジェクトが存在しない場合、送信処理をエラーとし実際の送信は行わない（１７０５）。この例ではリンクオブジェクト４０１を選択する。
上記メッセージ処理部は、次のデータヘッダ（転送経路、宛先ノード名、ＴＴＬ、経路モード）＝（ｎｏｄｅ４、ｎｏｄｅ２、５、ホップバイホップ）を生成してＡＰメッセージに付加し（１７０２）、リンクオブジェクト４０１に対応するノード間リンクにそのＡＰメッセージを送信する（１７０４）。上記例ではＴＴＬ＝５に設定されているが、ＴＴＬはアプリケーションが自由に設定できる項目である。もしＴＴＬがリンクオブジェクト４０１に登録されているノード２のネットワーク情報のホップ数より小さければ、送信処理をエラーとし実際の送信は行わない（１７０３，１７０５）。
上記メッセージを受信したノード１のメッセージ処理部は、宛先ノード名が自ノードでないことを確認すると再転送処理を行う（１７０６）。まず上記メッセージ処理部は、データを次に送信すべきノード間リンクを選択する。この処理はステップ１７０１におけるノード間リンク選択処理と同様である。従って、上記メッセージ処理部はリンクオブジェクト１３０２に対応するノード間リンクを選択する（１７０７）。
次にノード１のＡＰメッセージ処理部は、データヘッダの転送経路に自ノードの情報を加え、ＴＴＬから１減算する。すなわちデータヘッダを、（転送経路、宛先ノード名、ＴＴＬ、経路モード）＝（（ｎｏｄｅ４，ｎｏｄｅ１）、ｎｏｄｅ２、４、ホップバイホップ）のように変更する。（１７０８）
次にノード１のメッセージ処理部は、データヘッダ内のＴＴＬが上記リンクオブジェクト１３０２に登録されている宛先ノード（ノード２）のネットワーク情報のホップ数以上であることを確認した後（１７０９）、ステップＲ４で選択したノード間リンクにＡＰメッセージを送信する（１７１０）。もしＴＴＬが上記ホップ数以下であれば、送信処理をエラーとし実際の送信は行わない（１７１１）。
上記ＡＰメッセージを受信したノード２のメッセージ処理部は、宛先ノードが自ノードであることを確認すると、対応するアプリケーションにデータを配送する（１７１２）。
上記アプリケーションが上記ＡＰメッセージ送信元であるノード４に返信用ＡＰメッセージを返信する場合、経路指定モードを使用して返信用ＡＰメッセージを送信する。以下ではこの処理を説明する。ノード２のメッセージ処理部は返信用メッセージに以下のようなデータヘッダを付加する。
（転送経路、宛先ノード名、ＴＴＬ、経路モード）＝（（ｎｏｄｅ１，ｎｏｄｅ４）、ｎｏｄｅ１、５、経路指定）
上記転送経路は、ステップＲ６でメッセージ処理部が受信したＡＰメッセージに含まれるデータヘッダの転送経路情報を逆順に指定する。上記例では宛先ノード名とＴＴＬを指定しているが、経路指定モードでは宛先ノードまでの完全な経路が転送経路に含まれるので、実際には宛先ノード名およびＴＴＬを指定する必要は無い（１７１３）。
ノード２のメッセージ処理部は、次の転送先ノード（ノード１）との間にノード間リンクが確立されていることを碓認し、対応するノード間リンクを使用して返信用ＡＰメッセージを送信する（１７１４）。
上記返信用ＡＰメッセージを受信したノード１のメッセージ処理部は、転送経路から自ノードの情報を削除し、次の転送先ノード（ノード４）との間にノード間リンクが確立されていることを確認する。そして、対応するノード間リンクを使用して返信用ＡＰメッセージを送信する（ステップ１７０６から１７１０：但し１７０９の判断は返信時は省略される）。このようにデータヘッダに記載された転送経路に従って、データを転送していくことによって、目的のノードまで所望のメッセージを送信することができる。
ネットワーククラスタが大規模になり、リンクオブジェクトに登録されているネットワーク情報が十分速くネットワークに広まらない場合、ノード間リンクに閉路が形成される場合がある。
閉路が形成された場合、上記データヘッダのＴＴＬが０になるまでＡＰメッセージは閉路を回り続けてしまう。閉路におけるＡＰメッセージの無限ループを回避するには、上記データヘッダ内の転送経路をチェックすればよい。つまり、メッセージ処理部はノード間リンクを通じてＡＰメッセージを受信したとき、データヘッダの転送経路に既に自ノードが登録されていないことを確認する。もし自ノードが登録されていた場合、それは上記データが閉路を一周してきたことを示しているのでそのデータを廃棄する。
上記チェックはＡＰメッセージだけではなく、ノード間リンクを使用して送受信するすべてのメッセージについて行う必要がある。つまり、メッセージ処理部はネットワーク情報更新メッセージにも上記データヘッダを付加し、閉路内におけるネットワーク情報更新メッセージの無限ループ回避チェックを行う。ここでは、上記データヘッダを転送経路を記録するためだけに使用し、宛先ノード名などデータヘッダが含む他の情報は使用しない。メッセージ処理部は、閉路を一周してきたネットワーク更新メッセージについては、リンク管理部に配送せずに廃棄する。また、ネットワーク情報更新メッセージの転送処理はリンク処理部が行うので、メッセージ処理部は上記メッセージの転送処理を行わない。
閉路が形成されたとき、閉路を構成するノード間リンクの１つを切断（閉路切断処理）してもよい。以下、この閉路切断処理を説明する。
メッセージ処理部はノード間リンクを転送するすべてのメッセージ（ＡＰメッセージ、ネットワーク情報更新メッセージ）にデータヘッダを付加し、上述のようにデータヘッダ内の経路情報をチェックすることにより閉路検出を行う。閉路検出時、実際に検出対象となったデータヘッダの経路情報は閉路を表している。メッセージ処理部はこの経路情報（以下閉路情報と呼ぶ）をリンク管理部に配送する。上記閉路情報を受け取ったリンク管理部は、閉路を構成するノード間リンク（切断予定ノード間リンク）を１つ選択する。上記リンク選択処理は、閉路を構成するすべてのノードのリンク管理部が行うが、結果としてすべてのノードのリンク管理部が同一のリンクを選択するようなアルゴリズムによって行う。切断予定ノード間リンク選択後、リンク管理部は自ノードがそのリンクを確立しているかどうかを確認する。切断予定リンクを確立しているノードは、そのリンクを切断する。
以下、切断予定リンクの選択方法を説明する。リンク管理部はノード間リンクの両端ノードのＩＰアドレス（またはノード名）から適当なハッシュ関数を用いて、ノード間リンクのＩＤ値を求める。閉路を構成するノード間リンクの中で、最大（または最小）のＩＤ値を持つノード間リンクを切断予定ノード間リンクとする。
もし最大のＩＤ値を持つノード間リンクが複数存在する場合は、次にＩＤ値が大きなノード間リンクを切断予定ノード間リンクとする。このように、１つのノード間リンクが決定するまでＩＤ値の比較を行う。上記選択方法ではすべてのノードが同一の計算を行うので、すべてのノードが切断予定リンクとして同一のノード間リンクを決定することになる。上記方法では理論的には、最後まで唯一のノード間リンクを決定できない場合があるが、ＭＤ５等有用なハッシュ値計算アルゴリズムを用いることで実用上問題は発生しない。
【実施例２】  実施例１ではすべてのノードが自ノードの基本情報をブロードキャストしていた。この方式は確実にノード検出を行うことができる反面、ノード数に比例してネットワーク負荷が増加する。実施例２ではブロードキャストを行うノードがネットワーククラスタ内で最低１個存在すれば十分であるような、ネットワーク構成方法を提供する。以下実施例１との差異を中心に説明する。
図２に示した例（ノード６がノード４に接続する例）を用いて、新規ノードがネットワーククラスタに接続する方法を説明する。ネットワーククラスタを構成する各ノードは、自分がその一部であるネットワーククラスタ内の全ノードの基本情報を自ノードのノード基本情報テーブルに登録している。ネットワーククラスタ内のあるノード（ブロードキャストノード）が、上記ネットワーククラスタを形成する全ノードの基本情報をブロードキャストする。この例では、ノード１からノード５がネットワーククラスタを構成しているので、ブロードキャストノードはノード１からノード５の基本情報をブロードキャストする。
ブロードキャストノードの選択は、ネットワーククラスタ内で特定の１個のノードに決定できる方法であれば、どのような方法で行ってもかまわない。例えば、ノード基本情報テーブルに登録されたノードのうち、ＩＰアドレスが最小のノードがブロードキャストノードになるという方法が利用できる。またノード名等によって決定してもよい。
ノード６のリンク管理部は上記ブロードキャストメッセージを受信すると、自ノードのノード基本情報テーブルに受信した基本情報をマージする。ノード６のリンク管理部はステップ５０１から５０４の処理を実行してノード４をノード間リンク確立相手として選択し、接続要求７０１および接続応答８０１を送受信することによって、ノード間リンクを確立する（ステップ５０５，５０６）。本実施例においては、ノード６は接続要求７０１にさらに自ノードのノード基本情報テーブルの内容を含める。またノード４も接続応答８０１に自ノードのノード基本情報テーブルの内容を含める。ノード４、ノード６のリンク管理部は接続要求及び接続応答を受信すると、それらに含まれるノードの基本情報をそれぞれのノード基本情報テーブルにマージする。
ノード４とノード６はノード間リンク確立後、ステップ１２０１から１２０８の処理と同様の方法で、ネットワーク情報更新メッセージを既存ノード間リンクを通じて、ネットワーククラスタ全体に転送する。このとき各ノードのリンク管理部は、転送するネットワーク情報更新メッセージに自ノードのノード基本情報テーブルの内容を含める。ネットワーク情報更新メッセージを受信したノードのリンク管理部は、上記ネットワーク情報更新メッセージに含まれるノードの基本情報を自ノードのノード基本情報テーブルとマージする。
ノードがネットワーククラスタから消滅した場合、実施例１ではネットワーク情報更新メッセージをネットワーククラスタ全体に転送することによって、リンクオブジェクト内のネットワーク情報更新を行っていた。実施例２では上記ネットワーク情報更新メッセージにさらにノード基本情報テーブルの内容を含める。
つまりノード消滅時、ノード消滅検出ノードは自ノードのノード基本情報テーブルから消滅ノードを削除した後、ノード基本情報テーブルの内容を含めたネットワーク情報更新メッセージをノード間リンクに送信する。上記ネットワーク情報更新メッセージを受信したノードのリンク管理部は、上記ネットワーク情報更新メッセージに従って自ノードのノード基本情報テーブルを更新した後、ノード基本情報テーブルの内容を含めたネットワーク情報更新メッセージを受信経路以外のノード間リンクに転送する。
以上のように本実施例では、新規ノードの接続及び既存ノードの消滅発生時、ノード間リンクを通じて送受信するメッセージ（接続要求、接続応答、ネットワーク情報更新メッセージ）にノードの基本情報を含めることによって、ブロードキャスト処理に頼らずにネットワーククラスタを構成する各ノードのノード基本情報テーブルを更新する。これによって、ブロードキャスト処理を行うノードはネットワーククラスタ内で高々１個あれば十分であり、結果的にネットワーク負荷を軽減することができる。
【実施例３】  実施例１、２ではブロードキャストを利用してネットワーククラスタを構成するノードの基本情報を新規ノードに送信している。しかし、ブロードキャストは通常同一ネットワーク（セグメント）内に存在するノード間だけで使用可能であり、遠隔地に存在するノードと通信するには向いていいない。実施例３ではブロードキャストを一切使用しないネットワーク構成方法を提供する。
本実施例では、ネットワーククラスタから消滅しない（または消滅する頻度が低い）ノード（ｗｅｌｌ−ｋｎｏｗｎノード）が少なくとも１個存在することを仮定する。そして、ネットワーククラスタに接続するノードは上記ｗｅｌｌ−ｋｎｏｗｎノードの宛先をあらかじめ知っている必要がある。
以下、新規ノードがネットワーククラスタに接続する方法につて、実施例２との差異を中心に説明する。まずネットワーククラスタに接続しようとするノード（ノード６）のリンク管理部はｗｅｌｌ−ｋｎｏｗｎノードに基本情報要求メッセージを送信する。このメッセージを受信したｗｅｌｌ−ｋｎｏｗｎノードは、自ノードのネットワーク基本情報テーブルの内容を返信する。ここでのメッセージ送受信はノード間リンクを使用しない方法（単純なＵＤＰによるデータ転送など）で行う。
上記ネットワーク基本情報テーブルを受信したノード６のリンク管理部は、自ノードのネットワーク基本情報テーブルを更新することによりネットワーククラスタを構成するノードを検出する。検出方法はステップ５０３で説明した方法と同様である。この後実施例２と同様の方法で、ノード６はノード間リンクを確立しネットワーククラスタに接続する。ノード６の基本情報及びネットワーク情報は、ネットワーク情報更新メッセージ転送処理によってネットワーククラスタ全体に転送される。ｗｅｌｌ−ｋｎｏｗｎノードはネットワーククラスタの一部であるので、上記情報はｗｅｌｌ−ｋｎｏｗｎノードにも転送される。従って、次に別ノードがｗｅｌｌ−ｋｎｏｗｎノードに基本情報要求メッセージを送信したときに、ｗｅｌｌ−ｋｎｏｗｎノードはノード６の情報を含むノード群の基本情報を返信することになる。ノードの消滅処理は実施例２と同じである。
以上説明したように、この実施形態によればｗｅｌｌ−ｋｎｏｗｎノードの存在を仮定することで、ブロードキャストが利用できない場合にも、実施例１、２で説明したネットワークシステムが利用可能となる。上記ｗｅｌｌ−ｋｎｏｗｎノードはネットワーククラスタ内に最低１個存在すればよいが、ｗｅｌｌ−ｋｎｏｗｎノードの台数を増やすことで、ｗｅｌｌ−ｋｎｏｗｎノードの負荷を低減することができる。
また、ブロードキャストによってネットワーククラスタの存在を検出できれば実施例１の方法を採用し、そうでなければ本実施例の方法を採用する、という具合に２つの実施例を組み合わせた利用方法も考えられる。これによって、ｗｅｌｌ−ｋｎｏｗｎノードへの問い合わせ回数が減少し、結果的にｗｅｌｌ−ｋｎｏｗｎノードの負荷、ネットワーク負荷等を減少ることができる。
以上説明したように、本発明によればメッセージ転送に必要なホップ数が、できるだけ小さくなるような最適なネットワークトポロジを、Ｐ２Ｐネットワークシステムにおいて自動生成することができる。
また本発明によればノード生成、消滅時のネットワークトポロジ変化に簡単なアルゴリズムで柔軟に対応することができる。
また本発明によれば、ノードごとに最大リンク数を設定することができるので、上記ネットワークトポロジはノードの性能、資源を考慮したものとなる。
【図１】
2004066569.tif 000003
【図２】
2004066569.tif 000004
【図３】
2004066569.tif 000005
2004066569.tif 000006
【図５】
2004066569.tif 000007
【図６】
2004066569.tif 000008
【図７】
2004066569.tif 000009
【図８】
2004066569.tif 000010
【図９】
2004066569.tif 000011
【図１０】
2004066569.tif 000012
2004066569.tif 000013
【図１２】
2004066569.tif 000014
2004066569.tif 000015
【図１４】
2004066569.tif 000016
【図１５】
2004066569.tif 000017
2004066569.tif 000018
2004066569.tif 000019
【国際調査報告】
2004066569.tif 000020
2004066569.tif 000021