(57)【特許請求の範囲】
【請求項１】
複数のノードから構成されるオーバーレイネットワークと、
前記複数のノードの部分集合から構成される、階層化された複数のサブオーバーレイネットワークであって、前記オーバーレイネットワークを最上位の階層の第０レベルのサブオーバーレイネットワークとする階層構造に含まれる複数のサブオーバーレイネットワークとを具備し、
前記複数のサブオーバーレイネットワークの各々には、当該サブオーバーレイネットワークを識別するための当該サブオーバーレイネットワークの階層レベルに対応するビット数のサブオーバーレイネットワークＩＤが割り当てられ、
前記サブオーバーレイネットワークＩＤの上位ビットは、当該サブオーバーレイネットワークＩＤのサブオーバーレイネットワークよりも上位の階層であって、当該上位ビットのビット数に対応した上位の階層のサブオーバーレイネットワークのサブオーバーレイネットワークＩＤをも示し、
前記複数のノードの各々は、前記階層構造において自身を含む最も深い階層のサブオーバーレイネットワークである第ｍａｓｋレベルのサブオーバーレイネットワークのサブオーバーレイネットワークＩＤを、自身が参加しているサブオーバーレイネットワークのサブオーバーレイネットワークＩＤとして管理すると共に、少なくとも当該第ｍａｓｋレベルのサブオーバーレイネットワークに含まれる他のノードと識別可能なノードＩＤを管理し、
前記複数のノードの各々は、
前記階層構造において自身が参加している前記第ｍａｓｋレベルのサブオーバーレイネットワークから前記第０レベルのサブオーバーレイネットワークまでの階層毎に、その階層のサブオーバーレイネットワークに含まれる全てのノードのノードＩＤを当該ノードＩＤの大きさの順序でリング状に整列した際に自身に隣接するノードのノードＩＤ及びアドレスを保持する隣接テーブルと、
自身が第１のノードとして、任意のノードである第２のノードのアドレスを取得するルーティングを実行するルーティング手段であって、前記第２のノードのノードＩＤと、前記第２のノードが参加しているサブオーバーレイネットワークのサブオーバーレイネットワークＩＤとを入力として自身が有する前記隣接テーブルを参照することにより、前記第２のノードが参加しているサブオーバーレイネットワーク、または前記第２のノードが参加しているサブオーバーレイネットワークを包含するサブオーバーレイネットワークの階層に対応する前記隣接テーブルの情報に基づいて前記第２のノードのアドレスを取得し、前記第２のノードのアドレスを取得できなかった場合には、前記隣接テーブルに保持されている、前記第１のノードに隣接するノードのアドレスを用いて、当該隣接するノードに前記第２のノードのアドレスの取得を要求するルーティング手段とを有している
ことを特徴とするオーバーレイネットワークシステム。
【請求項２】
前記複数のノードのノードＩＤは長さがＭビットで前記オーバーレイネットワーク全体で固有であり、当該ノードＩＤの上位ｍａｓｋビットは、前記ノードＩＤのノードが参加している前記第ｍａｓｋレベルのサブオーバーレイネットワークのサブオーバーレイネットワークＩＤを示し、当該ノードＩＤの下位Ｍ−ｍａｓｋビットは、前記第ｍａｓｋレベルのサブオーバーレイネットワークに含まれる他のノードと識別可能であり
前記複数のノードの各々は、自身が参加している前記第ｍａｓｋレベルのサブオーバーレイネットワークのサブオーバーレイネットワークＩＤを、当該ノードのノードＩＤとマスクビット数ｍａｓｋとによって管理する
ことを特徴とする請求項１記載のオーバーレイネットワークシステム。
【請求項３】
前記ルーティング手段は、前記第２のノードのアドレスを取得するのに、前記第２のノードが参加しているサブオーバーレイネットワーク及び前記第２のノードが参加しているサブオーバーレイネットワークを包含するサブオーバーレイネットワークと、前記第１のノードが参加しているサブオーバーレイネットワーク及び前記第１のノードが参加しているサブオーバーレイネットワークを包含するサブオーバーレイネットワークとの間で共通するサブオーバーレイネットワークのうち、最も深い階層のサブオーバーレイネットワークに対応する前記隣接テーブルの情報を選択して使用することを特徴とする請求項２記載のオーバーレイネットワークシステム。
【請求項４】
前記ルーティング手段は、前記第２のノードの示すサブオーバーレイネットワークＩＤと前記第１のノードの示すサブオーバーレイネットワークＩＤとが最上位ビットから連続して一致する最大ビット数ｋをカウントし、カウントされた最大ビット数ｋの示す第ｋレベルのサブオーバーレイネットワークを、前記共通するサブオーバーレイネットワークのうちの前記最も深い階層のサブオーバーレイネットワークであると決定することを特徴とする請求項３記載のオーバーレイネットワークシステム。
【請求項５】
前記複数のノードは、当該複数のノードのうちの、当該複数のノードのノードＩＤを当該ノードＩＤの大きさの順序でリング状に整列した際に自身に隣接しないノードを含む複数の任意のノードの各々をスキップノードとして、当該スキップノードのノードＩＤ及びアドレスを保持するスキップテーブルを更に有しており、
前記ルーティング手段は、前記第２のノードのアドレスを取得するルーティング時に、自身が有する前記スキップテーブルを参照することにより、前記スキップテーブルの情報に基づいて前記第２のノードのアドレスを取得し、前記第２のノードのアドレスを取得できなかった場合には、前記スキップテーブルに保持されている前記スキップノードのアドレスを用いて、当該スキップノードに前記第２のノードのアドレスの取得を要求する
ことを特徴とする請求項１または２に記載のオーバーレイネットワークシステム。
【請求項６】
前記複数の任意のノードは、当該複数の任意のノードのノードＩＤ及びアドレスが保持される前記スキップテーブルを有するノードが参加している前記第ｍａｓｋレベルのサブオーバーレイネットワークに参加している他のノードを含むことを特徴とする請求項５記載のオーバーレイネットワークシステム。
【請求項７】
前記複数の任意のノードは、当該複数の任意のノードのノードＩＤ及びアドレスが保持される前記スキップテーブルを有するノードが参加している前記第ｍａｓｋレベルのサブオーバーレイネットワークを包含する前記第０レベルのサブオーバーレイネットワークまでの各サブオーバーレイネットワークに含まれる他のノードを含むことを特徴とする請求項６記載のオーバーレイネットワークシステム。
【請求項８】
前記ルーティング手段は、前記第２のノードのアドレスを取得できなかった場合に、前記第２のノードが参加しているサブオーバーレイネットワーク及び前記第２のノードが参加しているサブオーバーレイネットワークを包含するサブオーバーレイネットワークと、前記第１のノードが参加しているサブオーバーレイネットワーク及び前記第１のノードが参加しているサブオーバーレイネットワークを包含するサブオーバーレイネットワークとの間で共通するサブオーバーレイネットワークのうち、最も深い階層のサブオーバーレイネットワークに対応する前記スキップテーブルの情報を選択し、当該選択されたスキップテーブルの情報使用して、前記第２のノードのアドレスの取得を要求するスキップノードを決定することを特徴とする請求項７記載のオーバーレイネットワークシステム。
【請求項９】
前記複数のノードの各々は、
複数のオブジェクトを格納するためのオブジェクト格納手段と、
任意のオブジェクトを、前記複数のノードのいずれかの前記オブジェクト格納手段に格納するためのオブジェクト格納処理手段とを更に具備し、
前記複数のオブジェクトの各々には、当該オブジェクトの格納先となるノードである格納先ノードを決定するのに用いられるオブジェクトＩＤと前記格納先ノード内で当該オブジェクトを識別するためのオブジェクトサブＩＤとから構成される固有のＩＤが割り当てられ、前記オブジェクトＩＤは当該オブジェクトの格納先ノードが参加しているサブオーバーレイネットワークを指定するサブオーバーレイネットワークＩＤ部及び前記格納先ノードを指定するためのノードＩＤ部とから構成され、
前記オブジェクト格納処理手段は、任意のオブジェクトを格納するための格納処理において、当該オブジェクトのオブジェクトＩＤのサブオーバーレイネットワークＩＤ部と同じサブオーバーレイネットワークＩＤのサブオーバーレイネットワークに参加している全てのノードのうち、当該全てのノードのノードＩＤを当該ノードＩＤの大きさの順序でリング状に整列した際に当該オブジェクトのオブジェクトＩＤのノードＩＤ部に最も近いノードＩＤのノードを前記ルーティング手段により探索させ、探索されたノードに当該オブジェクトを格納することを特徴とする請求項１または２に記載のオーバーレイネットワークシステム。
【請求項１０】
複数のノードから構成されるオーバーレイネットワークと、前記複数のノードの部分集合から構成される、階層化された複数のサブオーバーレイネットワークであって、前記オーバーレイネットワークを最上位の階層の第０レベルのサブオーバーレイネットワークとする階層構造に含まれる複数のサブオーバーレイネットワークとを備え、前記複数のサブオーバーレイネットワークの各々には、当該サブオーバーレイネットワークを識別するための当該サブオーバーレイネットワークの階層レベルに対応するビット数のサブオーバーレイネットワークＩＤが割り当てられ、前記サブオーバーレイネットワークＩＤの上位ビットは、当該サブオーバーレイネットワークＩＤのサブオーバーレイネットワークよりも上位の階層であって、当該上位ビットのビット数に対応した上位の階層のサブオーバーレイネットワークのサブオーバーレイネットワークＩＤをも示すオーバーレイネットワークシステムにおけるオーバーレイネットワーク構築・維持方法において、
前記複数のサブオーバーレイネットワークのうちの第ｍａｓｋレベルのサブオーバーレイネットワークに新たに参加するノードである第１のノードが、当該第１のノードに隣接するノードを、前記複数のノードのうちの任意のノードである第２のノードに対して問い合わせるステップと、
前記第１のノードから問い合わせに応じ、前記第２のノードが有する第２の隣接テーブルであって、前記階層構造において当該第２のノードを含む最も深い階層のサブオーバーレイネットワークのサブオーバーレイネットワークを当該第２のノードが参加しているサブオーバーレイネットワークとして、当該第２のノードが参加しているサブオーバーレイネットワークから前記第０レベルのサブオーバーレイネットワークまでの階層毎に、その階層のサブオーバーレイネットワークに含まれる全てのノードのノードＩＤを当該ノードＩＤの大きさの順序でリング状に整列した際に自身に隣接するノードのノードＩＤ及びアドレスを保持する第２の隣接テーブルを前記第２のノードが参照することにより、前記第２のノードが、前記第ｍａｓｋレベルのサブオーバーレイネットワークから前記第０レベルのサブオーバーレイネットワークまでの階層毎に、前記第１のノードに隣接するかを判定するステップと、
前記第２のノードが前記第１のノードに隣接すると判定される都度、当該隣接すると判定された階層に対応する前記第２の隣接テーブルの情報と、前記第１のノードが有している、前記第２の隣接テーブルに対応する構造の第１の隣接テーブルの情報であって、当該隣接すると判定された階層に対応する第１の隣接テーブルの情報とを、前記第２のノードが更新するステップと、
前記第２のノードによる前記判定するステップ及び前記更新するステップの後、前記第２のノードから前記第０レベルのサブオーバーレイネットワーク上で前記第２のノードに隣接するノードに前記第１のノードからの問い合わせを転送するステップと、
前記複数のノードのうちの任意のノードである第３のノードが前記複数のノードのうちの別の任意のノードである第４のノードのアドレスを取得する必要がある場合、前記第４のノードのノードＩＤと、前記第４のノードが参加しているサブオーバーレイネットワークのサブオーバーレイネットワークＩＤとを入力として、前記第３のノードが有している、前記第１の隣接テーブルに対応する構造の第３の隣接テーブルを参照することにより、前記第４のノードが参加しているサブオーバーレイネットワーク、または前記第４のノードが参加しているサブオーバーレイネットワークを包含するサブオーバーレイネットワークの階層に対応する前記第３の隣接テーブルの情報に基づいて前記第４のノードのアドレスを取得するためのルーティングを前記第３のノードが実行するステップと、
前記第４のノードのアドレスを取得できなかった場合には、前記第３の隣接テーブルに保持されている、前記第３のノードに隣接するノードのアドレスを用いて、前記第３のノードから当該第３のノードに隣接するノードに前記第４のノードのアドレスの取得を要求するステップと
を具備することを特徴とするオーバーレイネットワーク構築・維持方法。
【請求項１１】
前記複数のノードのノードＩＤは長さがＭビットで前記オーバーレイネットワーク全体で固有であり、当該ノードＩＤの上位ｍａｓｋビットは、前記ノードＩＤのノードが参加している前記第ｍａｓｋレベルのサブオーバーレイネットワークのサブオーバーレイネットワークＩＤを示し、当該ノードＩＤの下位Ｍ−ｍａｓｋビットは、前記第ｍａｓｋレベルのサブオーバーレイネットワークに含まれる他のノードと識別可能であり
前記複数のノードの各々は、自身が参加している前記第ｍａｓｋレベルのサブオーバーレイネットワークのサブオーバーレイネットワークＩＤを、当該ノードのノードＩＤとマスクビット数ｍａｓｋとによって管理する
ことを特徴とする請求項１０記載のオーバーレイネットワーク構築・維持方法。
【請求項１２】
前記ルーティングを実行するステップは、前記第４のノードのアドレスを取得するのに、前記第４のノードが参加しているサブオーバーレイネットワーク及び前記第４のノードが参加しているサブオーバーレイネットワークを包含するサブオーバーレイネットワークと、前記第３のノードが参加しているサブオーバーレイネットワーク及び前記第３のノードが参加しているサブオーバーレイネットワークを包含するサブオーバーレイネットワークとの間で共通するサブオーバーレイネットワークのうち、最も深い階層のサブオーバーレイネットワークに対応する前記第３の隣接テーブルの情報を選択するステップを含むことを特徴とする請求項１１記載のオーバーレイネットワーク構築・維持方法。
【請求項１３】
第１のノードを含む複数のノードから構成されるオーバーレイネットワークと、前記複数のノードの部分集合から構成される、階層化された複数のサブオーバーレイネットワークであって、前記オーバーレイネットワーク全体を示す最上位の階層サブオーバーレイネットワークである第０レベルのサブオーバーレイネットワークを含む複数のサブオーバーレイネットワークとを備え、前記複数のサブオーバーレイネットワークのうち前記０レベルのサブオーバーレイネットワークを除くサブオーバーレイネットワークの各々には、当該サブオーバーレイネットワークを識別するための当該サブオーバーレイネットワークの階層レベルに対応するビット数のサブオーバーレイネットワークＩＤが割り当てられ、前記サブオーバーレイネットワークＩＤの上位ビットは、当該サブオーバーレイネットワークＩＤのサブオーバーレイネットワークよりも上位の階層であって、当該上位ビットのビット数に対応した上位の階層のサブオーバーレイネットワークのサブオーバーレイネットワークＩＤをも示すオーバーレイネットワークシステムにおいて、前記第１のノードで実行されるプログラムであって、
前記第１のノードに、
前記複数のサブオーバーレイネットワークのうち第ｍａｓｋレベルのサブオーバーレイネットワークに新たに参加するノードである第２のノードから、当該第２のノードに隣接するノードが前記第１のノードに対して問い合わせられた場合に、前記第１のノードが有する第１の隣接テーブルであって、前記階層構造において当該第１のノードを含む最も深い階層のサブオーバーレイネットワークのサブオーバーレイネットワークを当該第１のノードが参加しているサブオーバーレイネットワークとして、当該第１のノードが参加しているサブオーバーレイネットワークから前記第０レベルのサブオーバーレイネットワークまでの階層毎に、その階層のサブオーバーレイネットワークに含まれる全てのノードのノードＩＤを当該ノードＩＤの大きさの順序でリング状に整列した際に自身に隣接するノードのノードＩＤ及びアドレスを保持する第１の隣接テーブルを参照することにより、前記第ｍａｓｋレベルのサブオーバーレイネットワークから前記第０レベルのサブオーバーレイネットワークまでの階層毎に、前記第２のノードに隣接するかを判定するステップと、
前記第１のノードが前記第２のノードに隣接すると判定される都度、当該隣接すると判定された階層に対応する前記第１の隣接テーブルの情報と、前記第２のノードが有している、前記第１の隣接テーブルに対応する構造の第２の隣接テーブルの情報であって、当該隣接すると判定された階層に対応する第２の隣接テーブルの情報とを更新するステップと、
前記判定するステップ及び前記更新するステップの後、前記第０レベルのサブオーバーレイネットワーク上で前記第１のノードに隣接するノードである第３のノードに前記第２のノードからの問い合わせを転送するステップと、
前記第１のノードが前記複数のノードのうちの任意のノードのアドレスを取得する必要がある場合、前記任意のノードのノードＩＤと、前記任意のノードが参加しているサブオーバーレイネットワークのサブオーバーレイネットワークＩＤとを入力として、前記第１の隣接テーブルに対応する構造の隣接テーブルを参照することにより、前記任意のノードが参加しているサブオーバーレイネットワーク、または前記任意のノードが参加しているサブオーバーレイネットワークを包含するサブオーバーレイネットワークの階層に対応する前記隣接テーブルの情報に基づいて前記任意のノードのアドレスを取得するためのルーティングを実行するステップと、
前記任意のノードのアドレスを取得できなかった場合には、前記第１の隣接テーブルに保持されている、前記第１のノードに隣接するノードのアドレスを用いて、前記第１のノードから当該第１のノードに隣接するノードに前記任意のノードのアドレスの取得を要求するステップと
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えばピアツーピアシステムに好適なオーバーレイネットワークシステム、同システムにおけるオーバーレイネットワーク構築・維持方法、及びプログラムに関する。
【背景技術】
【０００２】
近年、ピアツーピアシステム（Ｐ２Ｐシステム）のオーバーレイネットワークを構築及び維持する手法またはこれを利用したシステムの研究開発が盛んになりつつある。このＰ２Ｐシステムのオーバーレイネットワークを構築及び維持する手法には様々なものがあるが、その中でも特に、カルフォルニア大学バークレー校（ＵＣＢ）を中心としたＴａｐｅｓｔｒｙ（タペストリ）（非特許文献１及び２参照）、マイクロソフト社を中心としたＰａｓｔｒｙ（ペストリ）（非特許文献３及び４参照）、マサチューセッツ工科大学（ＭＩＴ）を中心としたＣｈｏｒｄ（コード）（非特許文献５及び６参照）などが注目されている。
【０００３】
これらの手法に共通するのは、ＩＤ（識別子）の近さをリングで管理するＣｏｎｓｉｓｔｅｎｔＨａｓｈｉｎｇ（コンシステントハッシング）を用いて、オーバーレイネットワークを構築するということである。ＣｏｎｓｉｓｔｅｎｔＨａｓｈｉｎｇとは、
１）全てのノードとファイルのようなオブジェクトとについて、それらが持つユニークな識別子（例えばノードならホスト名やＩＰ（Internet Protocol）アドレス、オブジェクトならその名前やデータ自体）をハッシュ関数に投入し、
２）そこから得られたノードとオブジェクトのハッシュ値（ＩＤ）をもとに、
３）オブジェクトを、オブジェクトＩＤとノードＩＤが最も「近い」ノードに格納する
という技術である。これにより、オブジェクトを探すには、オブジェクトＩＤに最も「近い」ノードＩＤを持つノードを尋ねればよいことになる。各ノードは分散ハッシュテーブル（ＤＨＴ）を構成する。
【０００４】
ここでのＩＤの「近さ」の定義には様々な方法が知られている。例えば非特許文献５及び６による方法では、ノードのＩＰアドレスのハッシュ値をノードＩＤ、オブジェクトのデータ自体のハッシュ値をオブジェクトＩＤとし、取り得る全てのＩＤ（０からＮ＝２M−１までの２M個のＩＤ）を収容できるリングの上に、それぞれのＩＤが当てはめられる。このリング上で、２つのＩＤが時計回りでどれだけ離れているかによって、当該２つのＩＤの近さが測られる。２M個のＩＤを収容できるリングは、Ｍビットのリングと呼ばれる。
【０００５】
以下に、非特許文献５及び６に記載されたＣｏｎｓｉｓｔｅｎｔＨａｓｈｉｎｇの動作を、例を用いて説明する。図２８は、３ビットのリングを示す。このリング上の丸印はＩＤを示し、当該丸印内に記述された数値０〜７は、対応するＩＤがＩＤ０〜ＩＤ７（値が０〜７のＩＤ）であることを示す。図２８の例では、ＩＤ０に最も近いＩＤはＩＤ０自身であり、次に近いＩＤはＩＤ１である。一方、ＩＤ７に最も近いＩＤはＩＤ７で自身であり、次に近いＩＤはＩＤ０である（ＩＤ６ではないことに注意されたい）。
【０００６】
図２８に示される３ビットのリングに、ノードＩＤが｛０，３，６｝のノードをあてはめる（参加させる）と、図２９のようになる。このリングを各ノードが構築し維持する方法については、非特許文献５または６を参照されたい。
【０００７】
３ビットのリングに、ノードＩＤが｛０，３，６｝のノードが参加した（仮想的につながっている）状態で、オブジェクト０（オブジェクトＩＤが０のオブジェクト）は、そのＩＤが最も近いノード０（ノードＩＤが０のノード）に格納される。同様に、オブジェクト４はノード６に格納される。
【０００８】
図３０は、図２９の例において、ＩＤ０，ＩＤ３及びＩＤ６のノードがそれぞれ格納するオブジェクトの範囲を示す。ここで、あるノードＩＤまたはオブジェクトＩＤ（ノード／オブジェクトＩＤ）に最も近いＩＤを持つノードをｓｕｃｃｅｓｓｏｒ（サクセサー）、最も遠いＩＤ（反時計回りに最も近いＩＤ）を持つノードをｐｒｅｄｅｃｅｓｓｏｒ（プレデセサー）と呼ぶ。図３０の例では、ノード６はノード３のｓｕｃｃｅｓｓｏｒであり、ノード０のｐｒｅｄｅｃｅｓｓｏｒであると同時に、オブジェクト４から６までのｓｕｃｃｅｓｓｏｒである。このように、オーバーレイネットワークにオブジェクトを格納するには、当該オブジェクトはオブジェクトＩＤのｓｕｃｃｅｓｓｏｒに格納される。
【０００９】
Ｐ２Ｐシステムでは、オーバーレイネットワークに格納されたオブジェクトの格納先ノードのアドレスは記憶されない。このため、オーバーレイネットワークからオブジェクトを取り出すには、その都度、当該ネットワーク上でオブジェクトＩＤ（或いはオブジェクトＩＤを生成するための数値もしくは文字列）を入力とした、多段ホップでの探索が必要となる。そのためＰ２Ｐの技術では、探索するために必要となる、各ノードが維持する探索パスの維持コストと、探索時にいかに早く目的のノードに到達できるかという探索コストのバランスが非常に重要になる。その探索の方法として、ブロードキャストによる方法（第１の方法）及びフルフラッディングによる方法（第２の方法）が知られている。
【００１０】
Ｎをネットワークに収容できる最大ノード数とすると、第１の方法では、通信コスト、記憶領域及び時間は、それぞれＯ（Ｎ）、Ｏ（Ｎ2）及びＯ(１）で示されるように、値Ｎ、Ｎ2及び１に依存する。第１の方法は、ネットワークに参加している全ノードの参加状況（参加・離脱・異常停止）を監視する必要があることが知られている。
【００１１】
一方、第２の方法では、通信コスト、記憶領域及び時間は、それぞれＯ（Ｎ）、Ｏ（Ｎ）及び，Ｏ(Ｎ）で示されるように、いずれもＮに依存する。第２の方法は、経路上での障害でフルフラッディングが機能しなくなるので信頼性が低いことが知られている。また、第１及び第２の方法のいずれも、オーバーレイネットワークの規模が大きくなると機能しなくなってしまう。
【００１２】
そこで、例えば非特許文献５及び６では、各ノードがＭ＝ｌｏｇ（Ｎ）個の探索のショートカットパスを用意することで、高々Ｍホップの探索要求転送で、参照が完了するアルゴリズムを提案している。このようなショートカットパスを、スキップテーブル（フィンガーテーブル）と呼ぶ。オブジェクトを参照するときには、このスキップテーブルを確認し、探索要求を転送する。スキップテーブルの構成方法については非特許文献５または６を参照されたい。
【００１３】
以上、非特許文献５及び６に記載された技術を例として、既存のＣｏｎｓｉｓｔｅｎｔＨａｓｈｉｎｇ技術を説明した。このＣｏｎｓｉｓｔｅｎｔＨａｓｈｉｎｇでは、ＩＤの「近さ」によりオブジェクトの格納先が決定され、探索経路が決定される。このことから、従来のＣｏｎｓｉｓｔｅｎｔＨａｓｈｉｎｇ技術には、以下のような「近接性」と「非均質性」に関する課題が存在する。
【００１４】
＜近接性＞
Ｐ２Ｐのオーバーレイネットワーク（論理ネットワーク）と例えばＩＰのアンダーレイネットワーク（物理ネットワーク）の「近さ」の違いをどのように関連付けるか。オブジェクトを格納するノードと、オブジェクトを探索するための経路を決定するときに、物理ネットワークを考慮するにはどのようにすればよいか。
【００１５】
＜非均質性＞
オーバーレイネットワークに参加しているノードの個性（ディスク容量・性能、ネットワーク速度や遅延などの能力の「ばらつき」）を考慮したオブジェクトの格納先決定をどのように行うか。
【００１６】
このように、オーバーレイネットワークを構成する際には、近接性と非均質性を考慮することが重要であり、研究開発も活発に行われている。例えば特許文献１には、ノードに「名前ＩＤ」と「数値ＩＤ」の２つのＩＤを付与し、これとＰｌａｘｔｏｎのアルゴリズムを組み合わせることで、近接性と非均質性について考慮したオーバーレイネットワークを構築する手法が記載されている。
【特許文献１】特開２００４−２６６７９６号公報
【非特許文献１】ｈｔｔｐ：／／ｐ２ｐ．ｃｓ．ｕｃｓｂ．ｅｄｕ／ｃｈｉｍｅｒａ／
【非特許文献２】Ｂｅｎ  Ｙ．  Ｚｈａｏ，Ｌｉｎｇ  Ｈｕａｎｇ，Ｊｅｒｅｍｙ  Ｓｔｒｉｂｌｉｎｇ，Ｓｅａｎ  Ｃ．  Ｒｈｅａ，Ａｎｔｈｏｎｙ  Ｄ．  Ｊｏｓｅｐｈ，ａｎｄ  Ｊｏｈｎ  Ｄ．  Ｋｕｂｉａｔｏｗｉｃｚ．, “Ｔａｐｅｓｔｒｙ：  Ａ  Ｒｅｓｉｌｉｅｎｔ  Ｇｌｏｂａｌ−Ｓｃａｌｅ  Ｏｖｅｒｌａｙ  ｆｏｒ  Ｓｅｒｖｉｃｅ  Ｄｅｐｌｏｙｍｅｎｔ”，ＩＥＥＥ  Ｊｏｕｒｎａｌ  ｏｎ  Ｓｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｉｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｖｏｌ  ２２，Ｎｏ．１，（２００４）
【非特許文献３】ｈｔｔｐ：／／ｒｅｓｅａｒｃｈ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ／〜ａｎｔｒ／ＰＡＳＴ／ｄｅｆａｕｌｔ．ｈｔｍ
【非特許文献４】Ａ．  Ｒｏｗｓｔｒｏｎ  ａｎｄ  Ｐ．  Ｄｒｕｓｃｈｅｌ，“Ｓｔｏｒａｇｅ  ｍａｎａｇｅｍｅｎｔ  ａｎｄ  ｃａｃｈｉｎｇ  ｉｎ  ＰＡＳＴ，ａ  ｌａｒｇｅ−ｓｃａｌｅ，ｐｅｒｓｉｓｔｅｎｔ  ｐｅｅｒ−ｔｏ−ｐｅｅｒ  ｓｔｏｒａｇｅ  ｕｔｉｌｉｔｙ”，１８ｔｈ  ＡＣＭ  ＳＯＳＰ,０１，Ｌａｋｅ  Ｌｏｕｉｓｅ，Ａｌｂｅｒｔａ，Ｃａｎａｄａ，（２００１）
【非特許文献５】ｈｔｔｐ：／／ｐｄｏｓ．ｃｓａｉｌ．ｍｉｔ．ｅｄｕ／ｃｈｏｒｄ／
【非特許文献６】Ｉｏｎ  Ｓｔｏｉｃａ，Ｒｏｂｅｒｔ  Ｍｏｒｒｉｓ，Ｄａｖｉｄ  Ｋａｒｇｅｒ，Ｍ．  Ｆｒａｎｓ  Ｋａａｓｈｏｅｋ，ａｎｄ  Ｈａｒｉ  Ｂａｌａｋｒｉｓｈｎａｎ，“Ｃｈｏｒｄ：Ａ  Ｓｃａｌａｂｌｅ  Ｐｅｅｒ−ｔｏ−ｐｅｅｒ  Ｌｏｏｋｕｐ  Ｓｅｒｖｉｃｅ  ｆｏｒ  Ｉｎｔｅｒｎｅｔ  Ａｐｐｌｉｃａｔｉｏｎｓ”，ＡＣＭ  ＳＩＧＣＯＭＭ  ２００１，（２００１）
【発明の開示】
【発明が解決しようとする課題】
【００１７】
しかしながら、上記特許文献１に記載された方法では、
１）オーバーレイネットワークに参加するノードは固有の名前ＩＤと数値ＩＤとの２つのＩＤを管理する必要がある
２）名前ＩＤの辞書編集的な並びと数値ＩＤの並び方によって、数値ＩＤによる問い合わせに必要な探索コストが変化する
という問題がある。
【００１８】
本発明は上記事情を考慮してなされたものでその目的は、オーバーレイネットワークに参加するノードが当該ノードに固有のＩＤを管理するだけで、近接性を考慮したオーバーレイネットワークを構築し、維持することができるオーバーレイネットワークシステム、同システムにおけるオーバーレイネットワーク構築・維持方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【００１９】
本発明の１つの態様によれば、複数のノードから構成されるオーバーレイネットワークと、前記複数のノードの部分集合から構成される、階層化された複数のサブオーバーレイネットワークであって、前記オーバーレイネットワークを最上位の階層の第０レベルのサブオーバーレイネットワークとする階層構造に含まれる複数のサブオーバーレイネットワークとを具備するオーバーレイネットワークシステムが提供される。前記オーバーレイネットワークシステムにおいて、前記複数のサブオーバーレイネットワークの各々には、当該サブオーバーレイネットワークを識別するための当該サブオーバーレイネットワークの階層レベルに対応するビット数のサブオーバーレイネットワークＩＤが割り当てられる。また、前記サブオーバーレイネットワークＩＤの上位ビットは、当該サブオーバーレイネットワークＩＤのサブオーバーレイネットワークよりも上位の階層であって、当該上位ビットのビット数に対応した上位の階層のサブオーバーレイネットワークのサブオーバーレイネットワークＩＤをも示す。また、前記複数のノードの各々は、前記階層構造において自身を含む最も深い階層のサブオーバーレイネットワークである第ｍａｓｋレベルのサブオーバーレイネットワークのサブオーバーレイネットワークＩＤを、自身が参加しているサブオーバーレイネットワークのサブオーバーレイネットワークＩＤとして管理すると共に、少なくとも当該第ｍａｓｋレベルのサブオーバーレイネットワークに含まれる他のノードと識別可能なノードＩＤを管理する。
【００２０】
前記複数のノードの各々は、前記階層構造において自身が参加している前記第ｍａｓｋレベルのサブオーバーレイネットワークから前記第０レベルのサブオーバーレイネットワークまでの階層毎に、その階層のサブオーバーレイネットワークに含まれる全てのノードのノードＩＤを当該ノードＩＤの大きさの順序でリング状に整列した際に自身に隣接するノードのノードＩＤ及びアドレスを保持する隣接テーブルと、自身が第１のノードとして、任意のノードである第２のノードのアドレスを取得するルーティングを実行するルーティング手段であって、前記第２のノードのノードＩＤと、前記第２のノードが参加しているサブオーバーレイネットワークのサブオーバーレイネットワークＩＤとを入力として自身が有する前記隣接テーブルを参照することにより、前記第２のノードが参加しているサブオーバーレイネットワーク、または前記第２のノードが参加しているサブオーバーレイネットワークを包含するサブオーバーレイネットワークの階層に対応する前記隣接テーブルの情報に基づいて前記第２のノードのアドレスを取得し、前記第２のノードのアドレスを取得できなかった場合には、前記隣接テーブルに保持されている、前記第１のノードに隣接するノードのアドレスを用いて、当該隣接するノードに前記第２のノードのアドレスの取得を要求するルーティング手段とを有している。
【発明の効果】
【００２１】
本発明によれば、オーバーレイネットワークにおいて、近接性を考慮したルーティングを可能にするためのＩＤ割り当てを実現できる。つまり本発明によれば、ＩＤ割り当てを利用して近接性を考慮したルーティングを実現することができる。
【発明を実施するための最良の形態】
【００２２】
以下、本発明の実施の形態につき図面を参照して説明する。  
［第１の実施形態］
図１は本発明の第１の実施形態に係るオーバーレイネットワークシステムにおけるオーバーレイネットワークの階層構造を示す。図１のオーバーレイネットワークシステムは、オーバーレイネットワーク１０を含む。オーバーレイネットワーク１０は、最大８つのノードを収容できるものとする。このオーバーレイネットワーク１０に収容されるノードを、オーバーレイネットワーク１０に参加するノードと表現することもある。オーバーレイネットワーク１０に収容（参加）可能な８つのノードのＩＤは、２進数表記で０００，００１，０１０，０１１，１００，１０１，１１０，１１１（１０進数表記で０，１，２，３，４，５，６，７）であるものとする。このＩＤの組をＩＤ＝｛０００，００１，０１０，０１１，１００，１０１，１１０，１１１｝のように表す。このＩＤは、後述するようにノードＩＤとは異なる。そこで、このＩＤをＩＤ ｉｄで表し、ノードＩＤをＩＤ ｎｉｄで表すこともある。
【００２３】
図１のオーバーレイネットワークシステムでは、オーバーレイネットワーク１０は２つのサブオーバーレイネットワーク１１-0及び１１-1に分割して管理される。また、サブオーバーレイネットワーク１１-0及び１１-1のうちの１つ、サブオーバーレイネットワーク１１-1は、２つのサブオーバーレイネットワーク１１０-0及び１１０-1に分割して管理される。このように、図１のオーバーレイネットワークシステムは、階層構造のオーバーレイネットワークを有する。図１において、オーバーレイネットワーク１０、サブオーバーレイネットワーク１１-0，１１-1，１１０-0，１１０-1上の破線の丸印は収容可能なノードを示し、その丸印の近傍に記述されている３桁の数値は、そのノードのＩＤ（ＩＤ ｉｄ）を示す。
【００２４】
ここで、オーバーレイネットワーク１０を第０レベル（最上位層）のサブオーバーレイネットワークと呼ぶ。またサブオーバーレイネットワーク１１-0及び１１-1を第１レベルのサブオーバーレイネットワークと呼び、サブオーバーレイネットワーク１１０-0及び１１０-1を第２レベルのオーバーレイネットワークと呼ぶ。
【００２５】
図１のオーバーレイネットワークシステムでは、オーバーレイネットワーク１０に収容される（参加する）ノード（つまりオーバーレイネットワーク１０を構成するノード）は上述のように当該オーバーレイネットワーク１０上のＩＤで識別される。各ノードは、このＩＤを用いて連携して様々な動作を行う。一方、実際の通信にはアンダーレイネットワークのアドレスが必要となる。このため、オーバーレイネットワーク上のＩＤからアンダーレイネットワークのアドレスを効率よく求めることが必要となる。このＩＤからアドレスを得る処理をルーティングと呼ぶ。
【００２６】
本実施形態において、アンダーレイネットワークはＩＰ（Internet Protocol）により構築されるネットワークを指し、オーバーレイネットワーク１０はアンダーレイネットワークの上位に構築されるネットワークを指す。アンダーレイネットワークのアドレスはＩＰアドレス（ａｄｄｒ）を指す。
【００２７】
オーバーレイネットワーク１０に収容される各ノードは、階層の異なる複数のサブオーバーレイネットワークに収容可能である。ここで、階層の異なる複数のサブオーバーレイネットワークのうちの最も深い階層のサブオーバーレイネットワークに収容されるノードを、当該最も深い階層のサブオーバーレイネットワークに参加するノードと表現することもある。また、単にサブオーバーレイネットワークに収容されるノードを、サブオーバーレイネットワークに所属するまたは含まれるノードと表現することもある。
【００２８】
オーバーレイネットワーク１０に収容される各ノードは、自身が参加しているサブオーバーレイネットワークと、そのサブオーバーレイネットワークを包含する最上位層（第０レベル）までのサブオーバーレイネットワークについて、「隣接」しているノードのＩＤ（ｉｄ）及びアドレス（ａｄｄｒ）を保持する。これにより、ルーティングは、ノードが所属しないサブオーバーレイネットワークをできるだけ経由することなく行うことができる。あるサブオーバーレイネットワークにノードが所属（参加）している場合、当該ノードは当該サブオーバーレイネットワークを包含する最上位層（第０レベル）までの各サブオーバーレイネットワークにも所属していることになる。
【００２９】
図２は、図１のオーバーレイネットワーク１０（第０サブオーバーレイネットワーク１０）に、ＩＤ＝｛０００，００１，０１１，１００，１１０，１１１｝に６つのノード２０-0，２０-1，２０-3，２０-4，２０-6，２０-7が参加（所属）している状態を示す。これらのノード２０-0，２０-1，２０-3，２０-4，２０-6，２０-7は実線の丸印で示されている。また、これらの丸印の近傍には、対応するノードのＩＤと共にアドレス（ＩＰアドレス）が表記されている。また、ノード２０-0，２０-1，２０-3はサブオーバーレイネットワーク１１-0に所属し、ノード２０-4，２０-6，２０-7はサブオーバーレイネットワーク１１-1に所属している。また、ノード２０-4，２０-6，２０-7のうちのノード２０-4はサブオーバーレイネットワーク１１０-0にも所属し、残りのノード２０-6，２０-7はサブオーバーレイネットワーク１１-1にも所属する。以後の説明では、ノードが所属するサブオーバーレイネットワークのうち、最も深いレベルのサブオーバーレイネットワークのみを、そのノードが参加するサブオーバーレイネットワークと呼ぶこともある。また、オーバーレイネットワーク１０全体について説明する場合には、各ノード（ここではノード２０-0，２０-1，２０-3，２０-4，２０-6，２０-7）は、オーバーレイネットワーク１０に参加していると表現する。
【００３０】
図２には、ノード２０-t（Ｔ＝７，３，１）が管理する構成情報５０-t、即ちＩＤ＝１１１のノード２００-7が管理する構成情報５０-7（ｔ＝７）、ＩＤ＝０１１のノード２００-3が管理する構成情報５０-3（ｔ＝３）、及びＩＤ＝００１のノード２００-1が管理する構成情報５０-1（ｔ＝１）も示されている。構成情報５０-tについては図５を参照して後述する。なお、図２に示される構成情報５０-t（ｔ＝７，３，１）には、図５から明らかなように、一部の情報（ノード情報５１-tの一部）が省略されている。
【００３１】
図３は、ノード２０-tのハードウェア構成を示す。ノード２０-tは図２に示されるノード２０-0，２０-1，２０-3，２０-4，２０-6，２０-7だけでなく、オーバーレイネットワーク１０に参加可能な、ノード２０-0，２０-1，２０-3，２０-4，２０-6，２０-7以外のノード（ノード２０-2及び２０-5）をも指すものとする。
【００３２】
本実施形態において、ノード２０-tはコンピュータである。ノード２０-tは、処理ユニット２１と、主記憶装置２２と、補助記憶装置２３と、通信機構２４と、入出力装置２５とを含む。補助記憶装置２３は例えばハードディスクドライブを用いて構成される。補助記憶装置２３には、各ノード２０-tが連携してオーバーレイネットワーク１０を構築・維持するためのプログラム２３０が格納されている。通信機構２４は、後述する制御部２６による例えばノード探索のために当該制御部２６によって指定されたノードとＩＰアドレス（アンダーレイネットワークのアドレス）を用いて通信する。
【００３３】
図４は、ノード２０-tの主として機能構成を示す。ノード２０-tは、通信機構２４と、制御部２６とを含む。制御部２６は、構成情報記憶部２７、テーブル管理部２８及びルーティング部２９を含む。  
構成情報記憶部２７は図３に示す主記憶装置２２の所定記憶領域を用いて構成され、後述する構成情報５０-tを記憶するのに用いられる。
【００３４】
テーブル管理部２８は、構成情報記憶部２７に格納される構成情報５０-t（に含まれる後述する隣接テーブル５２-t）を管理する。テーブル管理部２８は特に、新しいノード２０-tが図２のオーバーレイネットワーク１０に参加する場合に、当該新しいノード２０-tからの要求（問い合わせ）、または他のノード２０-tからの要求に応じて、当該テーブル管理部２８を含むノード２０-t及び当該新しいノード２０-tがそれぞれ保持する構成情報５０-tに含まれる隣接テーブル５２-tを更新する。
【００３５】
ルーティング部２９は、他のノード（の通信機構２４）またはクライアント（図示せず）からノード探索要求（ルーティング要求）を受け取って、当該要求で指定されたノード探索（ルーティング）を実行する。ノード探索（ルーティング）とは、ノード探索要求で指定されたノードのＩＤに基づき、当該ノードのＩＰアドレスを取得するための処理を指す。このノード探索は、構成情報５０-tを利用して行われる。
【００３６】
制御部２６内のルーティング部２９によるノード探索は、図４において矢印Ａ１で示されるように、幾つかのノードを経由して探索要求を転送することにより行われる。制御部２６（内のルーティング部２９）は、図４において矢印Ａ２で示されるように、ノード探索要求に対するノード探索の結果の応答を受け取る。ノード探索の結果の応答は、ノード探索の成功または失敗を示す情報を含む。また、ノード探索成功の場合、ノード探索の結果は取得されたＩＰアドレスを含む。
【００３７】
本実施形態において制御部２６は、図２に示されるノード２０-t内の処理ユニット２１が、補助記憶装置２３に格納されているプログラム２３０を当該ノード２０-t内の主記憶装置２２に読み込んで実行することにより実現されるものとする。
【００３８】
＜ノードが保持する構成情報＞
図５は、図４に示されるノード２０-tの構成情報記憶部２７に格納される構成情報５０-tのデータ構造例を示す。構成情報５０-tは、ノード情報５１-t及び隣接テーブル５２-tから構成される。  
ノード情報５１-tは、ＩＤ ｉｄビット数Ｍ、ＩＤ ｉｄ、マスクビット数ｍａｓｋ及びＩＰアドレスａｄｄｒから構成される。
【００３９】
ＩＤ ｉｄビット数Ｍは、ＩＤ ｉｄのビット数を示す。Ｍの値は全ノードで共通である。図５の例ではＭ＝３である。
【００４０】
ＩＤ ｉｄは、ノード２０-tのＩＤを示し、ノード２０-tが参加しているオーバーレイネットワーク１０の中で固有のＩＤである。特許請求の範囲に記載されたノードＩＤは当該ノード２０-tのＩＤを指す。
【００４１】
ＩＤ ｉｄは、ノード２０-tのノードＩＤ ｎｉｄと当該ノード２０-tが参加しているサブオーバーレイネットワークを識別するためのサブオーバーレイネットワークＩＤ ｎｗｉｄとから構成される。つまりノード２０-tは、自身のノードＩＤ ｎｉｄと自身が参加しているサブオーバーレイネットワークのサブオーバーレイネットワークＩＤ ｎｗｉｄとを持つ。ノードＩＤ ｎｉｄは、ノード２０-tが参加しているサブオーバーレイネットワークの中で固有のＩＤである。
【００４２】
本実施形態では、ＭビットのＩＤ ｉｄの上位側ｘビットによりノード２０-t自身が参加しているサブオーバーレイネットワークのサブオーバーレイネットワークＩＤ ｎｗｉｄが表され、下位側“Ｍ−ｘ”ビットによりノードＩＤ ｎｉｄが表される。このｘは次に述べるマスクビット数ｍａｓｋによって示される。つまり、サブオーバーレイネットワークＩＤ ｎｗｉｄはＩＤ ｉｄの上位側“ｍａｓｋ”ビットであり、ノードＩＤ ｎｉｄはＩＤ ｉｄの下位側“Ｍ−ｍａｓｋ”ビットである。
【００４３】
マスクビット数ｍａｓｋは、ＩＤ ｉｄからノードＩＤ ｎｉｄ及びサブオーバーレイネットワークＩＤ ｎｗｉｄを切り出すためのマスクビット数を示す。マスクビット数ｍａｓｋは、ノード毎に異なる場合がある。また、マスクビット数ｍａｓｋは、ノード２０-tが参加しているサブオーバーレイネットワークのレベル（階層）、つまりノード２０-tが所属しているサブオーバーレイネットワークのレベルのうちの最も低いレベル（第ｍａｓｋレベル）をも示す。図５の例ではｍａｓｋ＝ｘ＝２である。
【００４４】
図６に、ｉｄと当該ｉｄを構成するｎｉｄ及びｎｗｉｄとの関係、並びにｉｄ，ｎｉｄ及びｎｗｉｄのビット数を示す。
【００４５】
図５において、隣接テーブル５２-tは、ノード２０-tが参加している第ｍａｓｋレベルのサブオーバーレイネットワーク、及び第ｍａｓｋレベルのサブオーバーレイネットワークより上位の当該ノード２０-tが所属している全てのサブオーバーレイネットワーク（第ｍａｓｋレベルのサブオーバーレイネットワークを包含する全てのサブオーバーレイネットワーク）、つまりノード２０-tが所属している第ｍａｓｋレベルのサブオーバーレイネットワークから第０レベル（最上位層）のサブオーバーレイネットワークまでのそれぞれのレベルのサブオーバーレイネットワーク上で、ノード２０-tに隣接するノード（隣接ノード）の情報（隣接ノード情報）を保持するエントリ（隣接ノード情報エントリ）ｔａｂｌｅ［ｍａｓｋ］〜ｔａｂｌｅ［０］を有する。隣接ノードとは、各レベルのサブオーバーレイネットワークに包まれる全てのノードのｉｄ（ＩＤ ｉｄ）を昇順に整列してリング状に並べたときの、ノード２０-t自身のｉｄから時計回りで隣接しているｉｄを持つノードを指す。以降の説明では、このリングを、サブオーバーレイネットワークのリングと表現することもある。
【００４６】
隣接テーブル５２-tのエントリｔａｂｌｅ［ｍａｓｋ］〜ｔａｂｌｅ［０］に保持される隣接ノード情報は、隣接ノードのＩＤ ｉｄ及びＩＰアドレスａｄｄｒを含む。以下の説明では、エントリｔａｂｌｅ［ｉ］（ｉ＝０，…，ｍａｓｋ）に保持されるｉｄ及びａｄｄｒを、それぞれ、ｔａｂｌｅ［ｉ］．ｉｄ及びｔａｂｌｅ［ｉ］．ａｄｄｒと表記することもある。
【００４７】
本実施形態では、ノード２０-tのＩＤ ｉｄにサブオーバーレイネットワークＩＤ ｎｗｉｄを含めることにより、当該ノード２０-tが所属している第ｍａｓｋレベルから第０レベルまでの全てのサブオーバーレイネットワークのＩＤを得ることができる。サブオーバーレイネットワークＩＤ ｎｗｉｄの上位ｌビット（０≦ｌ≦ｍａｓｋ）は、第ｌレベルのサブオーバーレイネットワークを示す（ただし第０レベルのサブオーバーレイネットワークはオーバーレイネットワーク全体を示す）。
【００４８】
例えば、ノード２０-tがサブオーバーレイネットワークＩＤ ｎｗｉｄ＝１０１（ｍａｓｋ＝３）のサブオーバーレイネットワークに参加しているとする。このサブオーバーレイネットワークは、第３レベルのサブオーバーレイネットワークである。サブオーバーレイネットワークＩＤ ｎｗｉｄ＝１０１のサブオーバーレイネットワークは、サブオーバーレイネットワークＩＤ＝１０の第２レベルのサブオーバーレイネットワークに包含される。更に、このサブオーバーレイネットワークＩＤ＝１０の第２レベルのサブオーバーレイネットワークは、サブオーバーレイネットワークＩＤ＝１の第０レベルのサブオーバーレイネットワークに包含される。
【００４９】
このように本実施形態では、サブオーバーレイネットワークを１ビットの値で識別するため、任意のレベルのサブオーバーレイネットワークが包含できる下位レベルのサブオーバーレイネットワークは２つとなる。なお、サブオーバーレイネットワークを２以上のビット数で識別することも可能である。例えば、サブオーバーレイネットワークを２ビットの値で識別するならば、任意のレベルのサブオーバーレイネットワークが包含できる下位レベルのサブオーバーレイネットワークは４つとなる。
【００５０】
ここで、サブオーバーレイネットワークＩＤとして、例えばアンダーレイネットワークのトポロジーを考慮したグルーピングのために、
（１）ドメイン名の一部もしくは全部、またはドメイン名の一部もしくは全部をもとに生成される固有な値
（２）物理的な地点を表現する値もしくは文字列の一部もしくは全部、または、物理的な地点を表現する値もしくは文字列の一部もしくは全部をもとに生成される固有な値
（３）組織名の一部もしくは全部、または組織名の一部もしくは全部をもとに生成される固有な値
を用いることができる。
【００５１】
再び図２を参照すると、当該図２には、オーバーレイネットワーク１０に参加しているノード２０-0，２０-1，２０-3，２０-4，２０-6，２０-7のうちのノード２０-1，２０-3，２０-7（つまり、ＩＤ＝｛００１，０１１，１１１｝のノード２０-1，２０-3，２０-7）の構成情報５０-1，５０-3，５０-7の例が示されている。以下の説明では、ノード２０-1，２０-3，２０-7を、当該ノード２０-1，２０-3，２０-7のＩＤ＝｛００１，０１１，１１１｝を用いて、ノード“００１”，“０１１”，“１１１”と呼ぶこともある。
【００５２】
図２の例では、ノード“１１１”の構成情報５０-7は、ノード情報５１-7及び隣接テーブル５２-7から構成される。ノード情報５１-7は、ＩＤ ｉｄ＝１１１、マスクビット数ｍａｓｋ＝２、ＩＰアドレスａｄｄｒ＝１９２．１６８．０．１の各情報を含む。この場合、ＩＤ ｉｄ＝１１１は、サブオーバーレイネットワークＩＤ ｎｗｉｄ＝１１、ノードＩＤ ｎｉｄ＝１を表す。なお、ＩＤ ｉｄビット数Ｍ＝３については省略されている。
【００５３】
隣接テーブル５２-7は、第０レベルのサブオーバーレイネットワーク１０（オーバーレイネットワーク１０全体）に対応する隣接ノード情報エントリｔａｂｌｅ［０］を有する。このエントリｔａｂｌｅ［０］には、図２において矢印２０１で示される、第０レベルのサブオーバーレイネットワーク１０上のノード“１１１”の隣接ノード“０００”のＩＤ ｔａｂｌｅ［０］．ｉｄ＝０００及び当該隣接ノード“０００”のＩＰアドレスｔａｂｌｅ［０］．ａｄｄｒ＝１０．０．１．１が保持される。
【００５４】
隣接テーブル５２-7はまた、第１レベルのサブオーバーレイネットワーク１１-1に対応する隣接ノード情報エントリｔａｂｌｅ［１］を有する。このエントリｔａｂｌｅ［１］には、図２において矢印２０２で示される、第１レベルのサブオーバーレイネットワーク１１-1上のノード“１１１”の隣接ノード“１００”のＩＤ ｔａｂｌｅ［１］．ｉｄ＝１００及び当該隣接ノード“１００”のＩＰアドレスｔａｂｌｅ［１］．ａｄｄｒ＝１９２．１６８．１．５が保持される。隣接テーブル５２-7は更に、第２レベルのサブオーバーレイネットワーク１１０-1に対応する隣接ノード情報エントリｔａｂｌｅ［２］を有する。このエントリｔａｂｌｅ［２］には、図２において矢印２０３で示される、第２レベルのサブオーバーレイネットワーク１１０-1上のノード“１１１”の隣接ノード“１１０”のＩＤ ｔａｂｌｅ［２］．ｉｄ＝１１０及び当該隣接ノード“１１０”のＩＰアドレスｔａｂｌｅ［２］．ａｄｄｒ＝１９２．１６８．１００．３が保持される。
【００５５】
ノード“０１１”の構成情報５０-3は、ノード情報５１-3及び隣接テーブル５２-3から構成される。ノード情報５１-3は、ＩＤ ｉｄ＝０１１、マスクビット数ｍａｓｋ＝１、ＩＰアドレスａｄｄｒ＝１０．０．０．１の各情報を含む。この場合、ＩＤ ｉｄ＝０１１は、サブオーバーレイネットワークＩＤ ｎｗｉｄ＝０、ノードＩＤ ｎｉｄ＝１１を表す。
【００５６】
隣接テーブル５２-3は、第０レベルのサブオーバーレイネットワーク１０（オーバーレイネットワーク１０全体）に対応する隣接ノード情報エントリｔａｂｌｅ［０］を有する。このエントリｔａｂｌｅ［０］には、図２において矢印２０４で示される、第０レベルのサブオーバーレイネットワーク１０上のノード“０１１”の隣接ノード“１００”のＩＤｔａｂｌｅ［０］．ｉｄ＝１００及び当該隣接ノード“１００”のＩＰアドレスｔａｂｌｅ［０］．ａｄｄｒ＝１９２．１６８．１．５が保持される。
【００５７】
隣接テーブル５２-3はまた、第１レベルのサブオーバーレイネットワーク１１-0に対応する隣接ノード情報エントリｔａｂｌｅ［１］を有する。このエントリｔａｂｌｅ［１］には、図２において矢印２０５で示される、第１レベルのサブオーバーレイネットワーク１１-0上のノード“０１１”の隣接ノード“０００”のＩＤ ｔａｂｌｅ［１］．ｉｄ＝０００及び当該隣接ノード“０００”のＩＰアドレスｔａｂｌｅ［１］．ａｄｄｒ＝１０．０．１．１が保持される。
【００５８】
ノード“００１”の構成情報５０-1は、ノード情報５１-1及び隣接テーブル５２-1から構成される。ノード情報５１-1は、ＩＤ ｉｄ＝００１、マスクビット数ｍａｓｋ＝１、ＩＰアドレスａｄｄｒ＝１９２．１６８．３．１の各情報を含む。この場合、ＩＤ ｉｄ＝００１は、サブオーバーレイネットワークＩＤ ｎｗｉｄ＝０、ノードＩＤ ｎｉｄ＝０１を表す。
【００５９】
隣接テーブル５２-1は、第０レベルのサブオーバーレイネットワーク１０（オーバーレイネットワーク１０全体）に対応する隣接ノード情報エントリｔａｂｌｅ［０］を有する。このエントリｔａｂｌｅ［０］には、図２において矢印２０６で示される、第０レベルのサブオーバーレイネットワーク１０上のノード“００１”の隣接ノード“０１１”のＩＤ ｔａｂｌｅ［０］．ｉｄ＝０１１及び当該隣接ノード“０１１”のＩＰアドレスｔａｂｌｅ［０］．ａｄｄｒ＝１０．０．０．１が保持される。
【００６０】
隣接テーブル５２-1はまた、第１レベルのサブオーバーレイネットワーク１１-0に対応する隣接ノード情報エントリｔａｂｌｅ［１］を有する。このエントリｔａｂｌｅ［１］には、図２において矢印２０７で示される、第１レベルのサブオーバーレイネットワーク１１-0上のノード“００１”の隣接ノード“０１１”のＩＤ ｔａｂｌｅ［１］．ｉｄ＝０１１及び当該隣接ノード“０１１”のＩＰアドレスｔａｂｌｅ［１］．ａｄｄｒ＝１０．０．０．１が保持される。
【００６１】
＜オーバーレイネットワークの構成＞
ノードが新しく図２のオーバーレイネットワーク１０に参加する場合、つまりオーバーレイネットワーク１０を再構成する場合、新しく参加するノードで隣接テーブルを構築し、新しく参加するノードと隣接する既存の全てのノードで隣接テーブルを更新する必要がある。
【００６２】
以下、新しく参加するノードの隣接テーブルを構築する手順並びに新しく参加するノード及び既存のノードの隣接テーブルを更新する手順について、それぞれ、図７及び図８のフローチャートを参照して説明する。
【００６３】
ここで、新しく参加するノードがノードＮｏｄｅであり、既にオーバーレイネットワーク１０に参加している任意のノードがノードｎであるものとする。ノードｎは、図２の例ではノード２０-0，２０-1，２０-3，２０-4，２０-6，２０-7のいずれかである。ノードｎのＩＤをｎ．ｉｄ（ＩＤ ｎ．ｉｄ）で表現し、当該ｎ．ｉｄが“ｓｔａｒｔ”（ＩＤ ｎ．ｉｄ＝ｓｔａｒｔ）であるものとする。
【００６４】
また、ノードＮｏｄｅ及びノードｎは、図３に示されるノード２０-tのハードウェア構成及び図４に示されるノード２０-tの機能構成と同一のハードウェア構成及び機能構成を有しているものとする。そこで、ノードＮｏｄｅ及びノードｎのハードウェア構成及び機能構成について、図３及び図４を援用する。ここで、ノードＮｏｄｅの構成情報記憶部２７に格納される構成情報５０-t、当該構成情報５０-tに含まれているノード情報５１-t及び隣接テーブル５２-tを、それぞれ構成情報５０-t(N)、ノード情報５１-t(N)及び隣接テーブル５２-t(N)と表現する。同様に、ノードｎの構成情報記憶部２７に格納される構成情報５０-t、当該構成情報５０-tに含まれているノード情報５１-t及び隣接テーブル５２-tを、それぞれ構成情報５０-t(n)、ノード情報５１-t(n)及び隣接テーブル５２-t(n)と表現する。
【００６５】
ノードＮｏｄｅがオーバーレイネットワーク１０に参加するには、当該オーバーレイネットワーク１０に既に参加している任意のノードｎのＩＰアドレスを何らかの方法で（例えば、ユーザがノードＮｏｄｅの入出力装置２５を操作してノードｎのＩＰアドレスを入力することにより）取得しておく必要がある。この状態で、ノードＮｏｄｅの制御部２６に含まれているルーティング部２９は、自身の隣接テーブル５２-t(N)を初期化する（ステップＳ１）。ここで、ノードＮｏｄｅの隣接テーブル５２-t(N)に保持される第ｉレベルのサブオーバーレイネットワーク上での隣接ノードのｉｄ（ｔａｂｌｅ［ｉ］．ｉｄ），ａｄｄｒ（ｔａｂｌｅ［ｉ］．ａｄｄｒ）を、それぞれＮｏｄｅ．ｔａｂｌｅ［ｉ］．ｉｄ，Ｎｏｄｅ．ｔａｂｌｅ［ｉ］．ａｄｄｒと表記する。同様に、隣接テーブル５２-t(n)に保持される第ｉレベルのサブオーバーレイネットワーク上での隣接ノードのｉｄ（ｔａｂｌｅ［ｉ］．ｉｄ），ａｄｄｒ（ｔａｂｌｅ［ｉ］．ａｄｄｒ）を、それぞれｎ．ｔａｂｌｅ［ｉ］．ｉｄ，ｎ．ｔａｂｌｅ［ｉ］．ａｄｄｒと表記する。
【００６６】
ノードＮｏｄｅの構成情報５０-t(N)のノード情報５１-t(N)に含まれているマスクビット数ｍａｓｋがＮｏｄｅ．ｍａｓｋであるものとする。この場合、隣接テーブル５２-t(N)の初期化（ステップＳ１）は、ｉ＝０〜ｉ＝Ｎｏｄｅ．ｍａｓｋまでの各レベル（第ｉレベル）のサブオーバーレイネットワーク上での隣接ノードのｉｄ（つまり、Ｎｏｄｅ．ｔａｂｌｅ［ｉ］．ｉｄ）及び当該隣接ノードのａｄｄｒ（つまり、Ｎｏｄｅ．ｔａｂｌｅ［ｉ］．ａｄｄｒ）を、それぞれ、当該ノードＮｏｄｅのｉｄ（つまり、Ｎｏｄｅ．ｉｄ）及びａｄｄｒ（つまり、Ｎｏｄｅ．ａｄｄｒ）に初期設定することにより行われる。
【００６７】
ノードＮｏｄｅのテーブル管理部２８は、自身の隣接テーブル５２-t(N)を初期化すると、ノードｎに対して当該ノードＮｏｄｅの参加を要求する（ステップＳ２）。即ちノードＮｏｄｅのテーブル管理部２８は、ノードｎ（ＩＤ ｎ．ｉｄ＝ｓｔａｒｔ）に対して当該ノードＮｏｄｅの隣接ノードを通信機構２４経由で問い合わせる。
【００６８】
この問い合わせ（参加要求）は、引数として、ノードＮｏｄｅの構成情報５０-t(N)及びノードｎのＩＤ（ＩＤ ｎ．ｉｄ＝ｓｔａｒｔ）を含む。構成情報５０-t(N)に含まれるノード情報５１-t(N)をＮｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ｝で表す。Ｎｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ｝は、Ｎｏｄｅ．ｉｄ，Ｎｏｄｅ．ｍａｓｋ及びＮｏｄｅ．ａｄｄｒの各情報を表す。また構成情報５０-t(N)に含まれる隣接テーブル５２-t(N)全体をＮｏｄｅ．ｔａｂｌｅ［］で表す。この場合、構成情報５０-t(N)は、Ｎｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ，ｔａｂｌｅ［］｝で表される。また上記問い合わせは、当該問い合わせに対する戻り値としてＮｏｄｅ．ｔａｂｌｅ［］を要求することを示す。図７のフローチャートには、これらの引数及び戻り値が、それぞれ入力及び出力（問い合わせ先のノードにとっての入力及び出力）と表記されている。この表記は、後述する他のフローチャートにおける問い合わせ（要求）においても同様である。
【００６９】
ノードｎのテーブル管理部２８は、ノードＮｏｄｅから上記の問い合わせを受け取ると、図８のフローチャートの示す手順で以下の処理を実行する。まずノードｎのテーブル管理部２８は、受け取った問い合わせが、ノードＮｏｄｅの隣接ノードに関する問い合わせの場合、当該問い合わせが１回目の問い合わせであるかを判定する（ステップＳ１１）。
【００７０】
もし、ノードＮｏｄｅの隣接ノードに関する１回目の問い合わせの場合、ノードｎのテーブル管理部２８は、当該問い合わせに含まれているＮｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ，ｔａｂｌｅ［］｝，ｓｔａｒｔに基づき、ｉ＝０〜ｉ＝Ｎｏｄｅ．ｍａｓｋまでのレベル（第ｉレベル）毎に、そのレベルのサブオーバーレイネットワーク上で当該ノードＮｏｄｅがノードｎの隣接ノードとなるかを判定する（ステップＳ１２）。
【００７１】
ステップＳ１２における判定は、ｎ．ｉｄiがＮｏｄｅ．ｉｄiで、かつｒｉｎｇ［ｎ．ｉｄM-t，Ｎｏｄｅ．ｉｄM-t，ｎ．ｔａｂｌｅ［ｉ］．ｉｄM-t）が正であるかを調べることによって行われる。ここでｘkはｘの上位ｋビットを、ｘkはｘの下位ｋビットを表す。したがって、上述のｎ．ｉｄi，Ｎｏｄｅ．ｉｄiは、それぞれｎ．ｉｄ，Ｎｏｄｅ．ｉｄの上位ｉビットを示す。ｎ．ｉｄi＝Ｎｏｄｅ．ｉｄiの場合、ノードｎ及びノードＮｏｄｅは共に第ｉレベルのサブオーバーレイネットワークに参加していることを示す。
【００７２】
一方、ｒｉｎｇ［ｘ，ｙ，ｚ）（ｘ＝ｎ．ｉｄM-t，ｙ＝Ｎｏｄｅ．ｉｄM-t，ｚ＝ｎ．ｔａｂｌｅ［ｉ］．ｉｄM-t）は、ＩＤ＝ｙが、リング上で範囲［ｘ，ｚ）に収まるという条件を満たした並びであるときに正を返す関数である。“［ｘ”における“［”は、範囲［ｘ，ｚ）にｘを含むことを表し、“ｚ）”における“）”は、範囲［ｘ，ｚ）にｚを含まないことを表す。例えば、ｘ＝２，ｚ＝５とすると、［ｘ，ｚ）の範囲（つまり［２，５）の範囲）に収まるｙの値は、｛２，３，４｝となる。ｎ．ｉｄM-t，Ｎｏｄｅ．ｉｄM-t，ｎ．ｔａｂｌｅ［ｉ］．ｉｄM-tは、それぞれノードｎのＩＤ，ノードＮｏｄｅのＩＤ，現時点におけるノードｎの隣接ノード（ｎ．ｔａｂｌｅ［ｉ］）のＩＤを示す。この場合、ノードＮｏｄｅのＩＤが、ノードｎのＩＤ及びノードｎの隣接ノードのＩＤの間に位置するならば正が返される。例えば、ノードＮｏｄｅの参加により、当該ノードＮｏｄｅが新たにノードｎの隣接ノードとなり、したがって当該ノードＮｏｄｅが参加するまではノードｎに隣接していたノード（ｎ．ｔａｂｌｅ［ｉ］）が新たに当該ノードＮｏｄｅの隣接ノードとなるならば、正が返される。
【００７３】
なお、ＩＤ＝ｙがリング上で範囲（ｘ，ｚ］に収まるという条件を満たした並びであるときに正を返す関数は、ｒｉｎｇ（ｘ，ｙ，ｚ］で表される。ここで、“（ｘ”における“（”は、範囲（ｘ，ｚ］にｘを含まないことを表し、“ｚ］”における“］”は、範囲（ｘ，ｚ］にｚを含むことを表す。
【００７４】
ノードｎのテーブル管理部２８は、ｎ．ｉｄiがＮｏｄｅ．ｉｄiで、かつｒｉｎｇ［ｎ．ｉｄM-t，Ｎｏｄｅ．ｉｄM-t，ｎ．ｔａｂｌｅ［ｉ］．ｉｄM-t）が“Ｙｅｓ”の場合、ノードＮｏｄｅが第ｉレベルのサブオーバーレイネットワーク上で新たに当該ノードｎ自身の隣接ノードとなると判定する（ステップＳ１２）。この場合、ノードｎのテーブル管理部２８は、ノードＮｏｄｅからの問い合わせに含まれている当該ノードＮｏｄｅの隣接テーブル５２-t(N)の内容（Ｎｏｄｅ．ｔａｂｌｅ［］）、及び当該ノードｎ自身の隣接テーブル５２-t(n)の内容（ｎ．ｔａｂｌｅ［］）を修正する（ステップＳ１３）。具体的には、ノードｎのテーブル管理部２８は、ノードＮｏｄｅの隣接テーブル５２-t(N)におけるＮｏｄｅ．ｔａｂｌｅ［ｉ］．ｉｄ及びＮｏｄｅ．ｔａｂｌｅ［ｉ］．ａｄｄｒを、それぞれ当該ノードｎの隣接テーブル５２-t(n)におけるｎ．ｔａｂｌｅ［ｉ］．ｉｄ及びｎ．ｔａｂｌｅ［ｉ］．ａｄｄｒに修正（更新）する。また、ノードｎのテーブル管理部２８は、ノードｎの隣接テーブル５２-t(n)におけるｎ．ｔａｂｌｅ［ｉ］．ｉｄ及びｎ．ｔａｂｌｅ［ｉ］．ａｄｄｒを、それぞれノードＮｏｄｅのｉｄ（Ｎｏｄｅ．ｉｄ）及びａｄｄｒ（Ｎｏｄｅ．ａｄｄｒ）に修正（更新）する。
【００７５】
一方、ｎ．ｉｄiがＮｏｄｅ．ｉｄiで、かつｒｉｎｇ［ｎ．ｉｄM-t，Ｎｏｄｅ．ｉｄM-t，ｎ．ｔａｂｌｅ［ｉ］．ｉｄM-t）が正である条件が不成立の場合、ノードｎのテーブル管理部２８はステップＳ１３をスキップする。
【００７６】
ノードｎ（以下、旧ノードｎと称する）のテーブル管理部２８は、ｉ＝０〜ｉ＝Ｎｏｄｅ．ｍａｓｋまでのレベルについて上述の処理を実行すると、当該ノードｎの隣接テーブル５２-t(n)、即ちｎ．ｔａｂｌｅ［］に保持されている例えば第０レベルのサブオーバーレイネットワーク上での隣接ノードのｉｄ（つまり、ｎ．ｔａｂｌｅ［０］．ｉｄ）に基づき、当該隣接ノードに、ノードＮｏｄｅからの問い合わせを転送する（ステップＳ１４）。この隣接ノードが、ノードＮｏｄｅから問い合わせられた新たなノード（新ノード）ｎとなる。新ノードｎは、ｎ．ｔａｂｌｅ［０］．ｉｄで示される。新ノードｎに転送される問い合わせは、ノードＮｏｄｅの構成情報５０-t(N)、即ちＮｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ，ｔａｂｌｅ［］｝及び“ｓｔａｒｔ”（ＩＤ ｎ．ｉｄ＝ｓｔａｒｔ）を含む。但し、上記ステップＳ１３が実行された場合、新ノードｎに転送される問い合わせに含まれるＮｏｄｅ．ｔａｂｌｅ［］は修正されたＮｏｄｅ．ｔａｂｌｅ［］となる。
【００７７】
新ノードｎは、旧ノードｎからの問い合わせを受け取ると、旧ノードｎと同様に、図８のフローチャートに示す処理を実行する。
【００７８】
このようにして、Ｎｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ，ｔａｂｌｅ［］｝及び“ｓｔａｒｔ”（ＩＤ ｎ．ｉｄ＝ｓｔａｒｔ）を含む問い合わせが、第０レベルのサブオーバーレイネットワーク１０上で隣接するノード間で受け渡されながら、その都度当該問い合わせに含まれるＮｏｄｅ．ｔａｂｌｅ［］が更新される。やがて、この問い合わせの受け渡しが第０レベルのサブオーバーレイネットワーク１０上で一巡し、ノードＮｏｄｅから直接に参加要求（問い合わせ）を受けたノードｎが隣接ノードから再び問い合わせを受け取ったものとする。
【００７９】
するとノードｎのテーブル管理部２８は、受け取ったノードＮｏｄｅの隣接ノードに関する問い合わせが、１回目の問い合わせであるかを判定する（ステップＳ１１）。この例のように２回目の問い合わせの場合、ノードｎのテーブル管理部２８は、当該問い合わせに含まれているＮｏｄｅ．ｔａｂｌｅ［］が完成し、且つオーバーレイネットワーク１０に既に参加している全てのノードの隣接テーブル５２-tがノードＮｏｄｅの参加を反映するように更新されたものと判断する。そこでノードｎのテーブル管理部２８は、ノードＮｏｄｅからの問い合わせに対する応答を当該ノードＮｏｄｅに返す（ステップＳ１５）。この応答は、２回目の問い合わせに含まれている修正されたＮｏｄｅ．ｔａｂｌｅ［］を含む。
【００８０】
ノードＮｏｄｅのテーブル管理部２８は、いずれかのノードｎから問い合わせに対する応答を確認すると、当該応答に含まれているＮｏｄｅ．ｔａｂｌｅ［］を、当該ノードＮｏｄｅの構成情報記憶部２７に格納されている構成情報５０-t(N)中の隣接テーブル５２-t(N)にコピーする（ステップＳ３）。即ちノードＮｏｄｅのテーブル管理部２８は、構成情報記憶部２７に格納されている隣接テーブル５２-t(N)を応答に含まれているＮｏｄｅ．ｔａｂｌｅ［］で更新する。これにより、ノードＮｏｄｅは、自身の隣接テーブル５２-t(N)を構築する。
【００８１】
このように本実施形態においては、ノードＮｏｄｅからの参加要求（問い合わせ）を受けたノードｎは、当該ノードｎ自身がノードＮｏｄｅの隣接ノードであればノードＮｏｄｅの隣接テーブル５２-t(N)（Ｎｏｄｅ．ｔａｂｌｅ［］）を修正すると共に、当該ノードｎの隣接ノード（新ノードｎ）に対して問い合わせを転送する。このようにしてノードｎから順にオーバーレイネットワーク１０上で隣接するノードがノードＮｏｄｅの隣接テーブル５２-t(N)（Ｎｏｄｅ．ｔａｂｌｅ［］）を構築していく。隣接テーブル５２-t(N)（Ｎｏｄｅ．ｔａｂｌｅ［］）の構築が完了したならば、最初にノードＮｏｄｅからの問い合わせを受け取ったノードｎが、構築された隣接テーブル５２-t(N)（Ｎｏｄｅ．ｔａｂｌｅ［］）を当該ノードＮｏｄｅに応答する。この応答を受けてノードＮｏｄｅは、構成情報記憶部２７に格納されている隣接テーブル５２-t(N)を正しい状態に更新することができる。
【００８２】
＜ノードの探索＞
次に、図２のオーバーレイネットワークシステムにおいて、あるノードが任意のノードのルーティングを行う場合の手順について、図９及び図１０のフローチャートを参照して説明する。
【００８３】
今、ＩＤ ｉｄがｓｔａｒｔ（ｓｔａｒｔ．ｉｄ）のノード（以下、ノードｓｔａｒｔと称する）が、例えばクライアントからの要求に従い、当該クライアントから要求されたノードＮｏｄｅのルーティング、つまりノードＮｏｄｅのＩＤ ｉｄ（Ｎｏｄｅ．ｉｄ）を入力して当該ノードＮｏｄｅのＩＰアドレスを出力（取得）するノード探索処理を行うものとする。また、ノードｓｔａｒｔは、図３に示されるノード２０-tのハードウェア構成及び図４に示されるノード２０-tの機能構成と同一のハードウェア構成及び機能構成を有しているものとする。そこで、ノードＮｏｄｅと同様、ノードｓｔａｒｔのハードウェア構成及び機能構成についても図３及び図４を援用する。ここで、ノードｓｔａｒｔの構成情報記憶部２７に格納される隣接テーブル５２-tを隣接テーブル５２-t(S)と表現する。また、第ｉレベルのサブオーバーレイネットワークに対応する隣接テーブル５２-t(S)のエントリ（ｔａｂｌｅ［ｉ］）をｓｔａｒｔ．ｔａｂｌｅ［ｉ］と表記し、エントリｓｔａｒｔ．ｔａｂｌｅ［ｉ］に保持されている第ｉレベルのサブオーバーレイネットワーク上の隣接ノードのｉｄ（ｔａｂｌｅ［ｉ］．ｉｄ），ａｄｄｒ（ｔａｂｌｅ［ｉ］．ａｄｄｒ）を、それぞれｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ｉｄ，ｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ａｄｄｒと表記する。
【００８４】
ルーティング先のノードＮｏｄｅのＩＤ Ｎｏｄｅ．ｉｄの上位側ｍａｓｋビットは、サブオーバーレイネットワークＩＤ部、つまりｎｗｉｄ（以下、Ｎｏｄｅ．ｎｗｉｄと称する）を表す。
【００８５】
ノードｓｔａｒｔの制御部２６に含まれているルーティング部２９は、ルーティング先のノードＮｏｄｅのＩＤ Ｎｏｄｅ．ｉｄに含まれているサブオーバーレイネットワークＩＤ Ｎｏｄｅ．ｎｗｉｄと当該ノードｓｔａｒｔ自身のＩＤであるｓｔａｒｔ．ｉｄに含まれているサブオーバーレイネットワークＩＤ ｓｔａｒｔ．ｎｗｉｄとを、最上位ビットから順に比較する（ステップＳ２１）。このステップＳ２１においてノードｓｔａｒｔのルーティング部２９は、上記の比較により、Ｎｏｄｅ．ｎｗｉｄとｓｔａｒｔ．ｎｗｉｄとが最上位ビットから連続して一致する最大ビット数ｋをカウントする。この最大ビット数ｋで表されるレベルのサブオーバーレイネットワーク（つまり、第ｋレベルのサブオーバーレイネットワーク）は、ノードｓｔａｒｔ及びノードＮｏｄｅが共に所属しているサブオーバーレイネットワーク（つまりノードｓｔａｒｔ及びノードＮｏｄｅを含むサブオーバーレイネットワーク）のうち最も深いレベルのサブオーバーレイネットワークである。
【００８６】
そこでノードｓｔａｒｔのルーティング部２９は、当該ノードｓｔａｒｔの構成情報記憶部２７に格納された（構成情報５０-t(S)に含まれている）隣接テーブル５２-t(S)のエントリｓｔａｒｔ．ｔａｂｌｅ［ｋ］に保持されている第ｋレベルのサブオーバーレイネットワーク上の隣接ノードの情報を選択する（ステップＳ２２）。つまりノードｓｔａｒｔは、当該ノードｓｔａｒｔが管理する構成情報５０-tの中から、当該ノードｓｔａｒｔ及びルーティング先ノードＮｏｄｅが共に所属しているサブオーバーレイネットワークのうち最も深いレベルのサブオーバーレイネットワークに対応する隣接テーブルの情報を、最短距離でのルーティングを可能にする隣接テーブルの情報（隣接ノードの情報）として選択する。
【００８７】
次にノードｓｔａｒｔのルーティング部２９は、選択された第ｋレベルのサブオーバーレイネットワーク上の隣接ノードの情報に含まれているｉｄ（つまりｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ｉｄ）が、ルーティング先のノードＮｏｄｅのｉｄ（つまりＮｏｄｅ．ｉｄ）に一致するかを判定する（ステップＳ２３）。
【００８８】
もし一致しているならば、ノードｓｔａｒｔのルーティング部２９は、ノードＮｏｄｅが第ｋレベルのサブオーバーレイネットワーク上で当該ノードｓｔａｒｔに隣接するノードであると判断する。するとノードｓｔａｒｔのルーティング部２９は、選択された第ｋレベルのサブオーバーレイネットワーク上の隣接ノードの情報に含まれているａｄｄｒ（つまりｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ａｄｄｒ）を、ノードＮｏｄｅのＩＰアドレスａｄｄｒ（Ｎｏｄｅ．ａｄｄｒ）として取得する（ステップＳ２４）。これによりノードｓｔａｒｔのルーティング部２９は、ノード探索処理（ルーティング）に成功したとして当該処理を完了する（ステップＳ２５）。
【００８９】
一方、ｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ｉｄがＮｏｄｅ．ｉｄに一致していない場合（ステップＳ２３）、ノードｓｔａｒｔのルーティング部２９は、ノードＮｏｄｅが第ｋレベルのサブオーバーレイネットワーク上で当該ノードｓｔａｒｔに隣接するノードでないと判断する。するとノードｓｔａｒｔのルーティング部２９は、ｒｉｎｇ［ｓｔａｒｔ．ｉｄ，Ｎｏｄｅ．ｉｄ，ｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ｉｄ）が正であるか、つまりＮｏｄｅ．ｉｄが、リング上で範囲［ｓｔａｒｔ．ｉｄ，ｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ｉｄ）に収まるという条件を満たした並びであるかを判定する（ステップＳ２６）。
【００９０】
もし、ステップ２６の判定結果が“Ｙｅｓ”であるならば、ノードＮｏｄｅはノードｓｔａｒｔの隣接ノードとなって上記ステップＳ２３の判定結果と矛盾する。この場合、ノードｓｔａｒｔのルーティング部２９は、ルーティング先のノードＮｏｄｅは存在せず、したがってノード探索処理に失敗したとして当該処理を完了する（ステップＳ２７）。
【００９１】
これに対してステップ２５の判定結果が“Ｎｏ”であり、したがって上記ステップＳ２３の判定結果と矛盾しないならば、ノードｓｔａｒｔのルーティング部２９は、第ｋレベルのサブオーバーレイネットワーク上における当該ノードｓｔａｒｔの隣接ノードをルーティング要求先のノードｎとして、当該ノードｎに、ノードＮｏｄｅのＩＰアドレス（Ｎｏｄｅ．ａｄｄｒ）を取得するためのルーティング要求を転送する（ステップＳ２８）。このノードｎのＩＤ ｉｄはｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ｉｄであり、アドレス（ＩＰアドレス）ａｄｄｒはｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ａｄｄｒである。ルーティング要求は、ノードＮｏｄｅのＩＤ ｉｄ（Ｎｏｄｅ．ｉｄ）及びマスクビット数ｍａｓｋ（Ｎｏｄｅ．ｍａｓｋ）、つまりＮｏｄｅ．｛ｉｄ，ｍａｓｋ｝と、ノードｓｔａｒｔのアドレス（ＩＰアドレス）ａｄｄｒ（ｓｔａｒｔ．ａｄｄｒ）を含む。
【００９２】
ノードｎのルーティング部２９は、上記ルーティング要求（ここでは、ノードｓｔａｒｔからのルーティング要求）を受け取ると、図１０のフローチャートに従うノード探索処理を次のように実行する。まず、ノードｎのルーティング部２９は、先のノードｓｔａｒｔにおけるステップＳ２１と同様のステップＳ３１を実行する。即ちノードｎのルーティング部２９は、ルーティング先のノードＮｏｄｅのＩＤ Ｎｏｄｅ．ｉｄに含まれているサブオーバーレイネットワークＩＤ Ｎｏｄｅ．ｎｗｉｄと当該ノードｎ自身のＩＤであるｎ．ｉｄとを、最上位ビットから順に比較する。この比較により、ノードｎのルーティング部２９は、Ｎｏｄｅ．ｎｗｉｄとｎ．ｉｄとが最上位ビットから連続して一致する最大ビット数ｋをカウントする。
【００９３】
次にノードｎのルーティング部２９は、当該ノードｎの構成情報記憶部２７に格納された隣接テーブル５２-t(n)のエントリｎ．ｔａｂｌｅ［ｋ］に保持されている第ｋレベルのサブオーバーレイネットワーク上の隣接ノードの情報を選択する（ステップＳ３２）。そしてノードｎのルーティング部２９は、選択された第ｋレベルのサブオーバーレイネットワーク上の隣接ノードの情報に含まれているｉｄ（つまりｎ．ｔａｂｌｅ［ｋ］．ｉｄ）が、ルーティング先のノードＮｏｄｅのｉｄ（つまりＮｏｄｅ．ｉｄ）に一致するかを判定する（ステップＳ３３）。
【００９４】
もし一致しているならば、ノードｎのルーティング部２９は、先のノードｓｔａｒｔにおけるステップＳ２４と同様に、選択された第ｋレベルのサブオーバーレイネットワーク上の隣接ノードの情報に含まれているａｄｄｒ（つまりｎ．ｔａｂｌｅ［ｋ］．ａｄｄｒ）を、ノードＮｏｄｅのＩＰアドレスａｄｄｒ（Ｎｏｄｅ．ａｄｄｒ）として取得する（ステップＳ３４）。するとノードｎのルーティング部２９は、ノード探索処理に成功したとして、自身が取得したノードＮｏｄｅのＩＰアドレスａｄｄｒ（Ｎｏｄｅ．ａｄｄｒ）を含む応答を、探索要求に含まれているＩＰアドレスｓｔａｒｔ．ａｄｄｒで指定されるノードｓｔａｒｔに返す（ステップＳ３５）。
【００９５】
一方、ｎ．ｔａｂｌｅ［ｋ］．ｉｄがＮｏｄｅ．ｉｄに一致していない場合（ステップＳ３３）、ノードｎのルーティング部２９は、ｒｉｎｇ［ｎ．ｉｄ，Ｎｏｄｅ．ｉｄ，ｎ．ｔａｂｌｅ［ｋ］．ｉｄ）が正であるか、つまりＮｏｄｅ．ｉｄが、リング上で範囲［ｎ．ｉｄ，ｎ．ｔａｂｌｅ［ｋ］．ｉｄ）に収まるという条件を満たした並びであるかを判定する（ステップＳ３６）。
【００９６】
もし、ステップ３６の判定結果が“Ｙｅｓ”であるならば、ノードＮｏｄｅはノードｎの隣接ノードとなって上記ステップＳ３３の判定結果と矛盾する。この場合、ノードｎのルーティング部２９は、ルーティング先のノードＮｏｄｅは存在せず、したがってノード探索処理に失敗したと判断する。そこでノードｎのルーティング部２９は、ノード探索処理の失敗を通知するための応答を、探索要求に含まれているｓｔａｒｔ．ａｄｄｒで指定されるノードｓｔａｒｔに返す（ステップＳ３７）。
【００９７】
これに対してステップ３５の判定結果が“Ｎｏ”であるならば、ノード（旧ノード）ｎのルーティング部２９は、第ｋレベルのサブオーバーレイネットワーク上における当該旧ノードｎの隣接ノードをルーティング要求先の新たなノード（新ノード）ｎとして、当該新ノードｎに、ノードＮｏｄｅのＩＰアドレス（Ｎｏｄｅ．ａｄｄｒ）を取得するためのルーティング要求を転送する（ステップＳ３８）。このルーティング要求は、旧ノードｎが受け取ったルーティング要求に含まれているＮｏｄｅ．｛ｉｄ，ｍａｓｋ｝及びｓｔａｒｔ．ａｄｄｒを含む。旧ノードｎから新ノードｎにルーティング要求が転送された場合、新ノードｎでは、旧ノードｎと同様に図１０のフローチャートに従うノード探索処理が行われる。
【００９８】
さて、ノードｓｔａｒｔの制御部２６は、ノードｎがステップＳ３５またはＳ３７を実行したことにより当該ノードｎから返される応答を確認すると（ステップＳ２９）、ノード探索処理に成功または失敗したとして当該処理を完了する（ステップＳ３０）。
【００９９】
このように本実施形態（第１の実施形態）において、ノードｓｔａｒｔ（またはノードｎ）は、ノードＮｏｄｅに対するルーティングを行うために、最短距離でのルーティングを可能にする隣接テーブル５２-tのエントリを最大ビット数ｋのカウントにより選択する。即ちノードｓｔａｒｔ（またはノードｎ）は、最短距離でのルーティングを行うために、当該ノードｓｔａｒｔ（またはノードｎ）自身が管理している隣接テーブル５２-tから、当該ノードｓｔａｒｔ（またはノードｎ）自身及びルーティング先のノードＮｏｄｅが共に所属しているサブオーバーレイネットワークの中で最も深いレベルのサブオーバーレイネットワークに対応するエントリを選択する。もし、ノードＮｏｄｅがノードｓｔａｒｔ（またはノードｎ）の隣接ノードでないために、選択されたエントリの情報に基づいてノードＮｏｄｅに対するルーティングが行えないならば、ルーティング要求が隣接ノードに転送される。ルーティング要求の転送先では、最短距離でのルーティングを可能にする隣接テーブルのエントリを選択して、当該ルーティング要求の転送元と同様の処理を行う。このようにして、ルーティング要求が隣接ノードに転送される動作が繰り返されることにより、ノードＮｏｄｅに対するルーティングが行われる。このルーティング（ノード探索）方法により、近接性を考慮して、経由するサブオーバーレイネットワークの数を少なくしながらルーティングを行うことができる。
【０１００】
＜ノードの探索の具体例＞
次に、上述した図９及び図１０のフローチャートの示す手順に従うノード探索の具体例について説明する。ここでは、図２に示されるオーバーレイネットワークシステムにおいて、ＩＤ（ＩＤ ｉｄ）＝１１１（マスクビット数ｍａｓｋ＝２），アドレス（ａｄｄｒ）＝１９２．１６８．０．１のノード“１１１”（ノード２０-7）が、ＩＤ＝｛１１０，１０１，００１｝の各ノード“１１０”，“１０１”，“００１”に対するルーティングを行うものとする。ＩＤ（ＩＤ ｉｄ）＝１１１（ｍａｓｋ＝２）のノード“１１１”（ノード２０-7）のサブオーバーレイネットワークＩＤ（ＩＤ ｎｗｉｄ）は“１１”であることに留意する。
【０１０１】
まず、ＩＤ＝１１０のノード“１１０”（ノード２０-6）に対するルーティングについて説明する。ＩＤ＝１１１のノード“１１１”（ノード２０-7）は、ＩＤ＝１１０とＩＤ ｎｗｉｄ＝１１とを最上位ビットから順次比較することにより、最上位ビットから連続して一致するビット数ｋ＝２をカウントする（ステップＳ２１）。これによりノード“１１１”は、自身が管理する隣接テーブル５２-7（ｔ＝７）から、第２レベルのサブオーバーレイネットワーク１１０-1に対応する２番目のエントリ（ｔａｂｌｅ［２］）の情報、つまり第２レベルのサブオーバーレイネットワーク１１０-1上でノード“１１１”に隣接するノードの情報を選択する（ステップＳ２２）。
【０１０２】
選択されたノードの情報は、図２から明らかなように、ＩＤ＝１１０のノード“１１０”（ノード２０-6）の情報、つまり目的とするルーティング先のノード“１１０”の情報である（ステップＳ２３）。この場合、ノード“１１１”は、選択されたノードの情報からノード“１１０”のアドレスａｄｄｒ（ここでは、＝１９２．１６８．１００．３）を取得して（ステップＳ２４）、ノード探索処理を完了する（ステップＳ２５）。つまりノード“１１１”は、ＩＤ＝１１０のノード“１１０”に関しては、第２レベルのサブオーバーレイネットワーク１１０-1を包含する、第１レベルのサブオーバーレイネットワーク１１-1及び第０レベルのサブオーバーレイネットワーク１０を経由することなくルーティングすることができる。
【０１０３】
次に、ＩＤ＝１０１のノード“１０１”に対するルーティングについて説明する。ノード“１１１”は、ＩＤ＝１０１とＩＤ ｎｗｉｄ＝１１とを最上位ビットから順次比較することにより、最上位ビットから連続して一致するビット数ｋ＝１をカウントする（ステップＳ２１）。これによりノード“１１１”（ノード２０-7）は、自身が管理する隣接テーブル５２-7（ｔ＝７）から、第１レベルのサブオーバーレイネットワーク１１-1に対応する１番目のエントリ（ｔａｂｌｅ［１］）の情報、つまり第１レベルのサブオーバーレイネットワーク１１-1上でノード“１１１”に隣接するノードの情報（ここでは、ＩＤ＝１００のノード“１００”の情報）を選択する（ステップＳ２２）。
【０１０４】
選択されたエントリの情報（ノード“１００”の情報）は、ノード“１１１”が目的としているルーティング先のノード“１０１”の情報でない（ステップＳ２３）。つまりノード“１０１”は第１レベルのサブオーバーレイネットワーク１１-1上でノード“１１１”の隣接ノードではない。この場合、ノード“１１１”は、選択されたエントリの情報の示すノード（隣接ノード）にルーティング要求を転送する（ステップＳ２８）。
【０１０５】
この例では、選択されたエントリの情報の示すノードは、図２から明らかなように第１レベルのサブオーバーレイネットワーク１１-1上でノード“１１１”に隣接する、ＩＤ＝１００のノード“１００”（ノード２０-4）である。この場合、上記ステップＳ２８では、ノード“１１１”からノード“１００”にルーティング要求が転送される。ノード“１００”が所属しているサブオーバーレイネットワークのうち最も深いレベルのサブオーバーレイネットワークは第２レベルのサブオーバーレイネットワーク１１０-0である。つまりノード“１００”のサブオーバーレイネットワークＩＤ（ＩＤ ｎｗｉｄ）は、ＩＤ＝１００の上位側２ビット“１０”である。
【０１０６】
ノード“１００”は、ノード“１１１”からルーティング要求を受け取ると、ＩＤ＝１０１とＩＤ ｎｗｉｄ＝１０とを最上位ビットから比較することにより、最上位ビットから連続して一致するビット数ｋ＝２をカウントする（ステップＳ３１）。これによりノード“１００”は、自身が管理する隣接テーブル５２-4（ｔ＝４）から、第２レベルのサブオーバーレイネットワーク１１０-0に対応する２番目のエントリ（ｔａｂｌｅ［２］）の情報、つまり第２レベルのサブオーバーレイネットワーク１１０-0上で当該ノード“１００”に隣接するノードの情報を選択する（ステップＳ３２）。
【０１０７】
選択されたノードの情報は、図２から明らかなように、ノード“１００”自身の情報であり、目的とするルーティング先のノード“１０１”の情報ではない（ステップＳ３３）。しかも、ノード“１０１”のＩＤ＝１０１は、ノード“１００”のＩＤ＝１００と、選択されたノードの情報の示すＩＤ＝１００（つまり第２レベルのサブオーバーレイネットワーク１１０-0上でノード“１００”に隣接する当該ノード“１００”自身のＩＤ＝１００）との間に、リング上で整列する（ステップＳ３６）。この場合、ノード“１００”（ノード２０-4）は、ルーティング要求で指定されたＩＤ＝１０１のノード（ルーティング先ノード）“１０１”は存在しない旨の応答（ノード探索失敗を示す応答）をノード“１１１”（ノード２０-7）に返す（ステップＳ３７）。
【０１０８】
ノード“１１１”は、ノード“１００”に対するルーティング要求（ステップＳ２８）に応じて当該ノード“１００”から返されるノード探索失敗を示す応答を確認すると（ステップＳ２９）、ノード探索処理に失敗したとして当該処理を完了する（ステップＳ３０）。
【０１０９】
次に、ＩＤ＝００１のノード“００１”（ノード２０-1）に対するルーティングについて説明する。ノード“１１１”は、ＩＤ＝００１とＩＤ ｎｗｉｄ＝１１とを最上位ビットから順次比較することにより、最上位ビットから連続して一致するビット数ｋをカウントする（ステップＳ２１）。ここでは、最上位ビットが不一致のため、一致するビット数ｋ＝０である。この場合、ノード“１１１”は、自身が管理する隣接テーブル５２-7（ｔ＝７）から、第０レベルのサブオーバーレイネットワーク１１-1に対応する０番目のエントリ（ｔａｂｌｅ［０］）の情報、つまり第０レベルのサブオーバーレイネットワーク１０上でノード“１１１”に隣接するノードの情報（ここでは、ＩＤ＝０００のノード“０００”の情報）を選択する（ステップＳ２２）。
【０１１０】
選択されたエントリの情報は、目的とするルーティング先のノード“００１”の情報でない（ステップＳ２３）。つまりノード“００１”は第０レベルのサブオーバーレイネットワーク１０上でノード“１１１”の隣接ノードではない。この場合、ノード“１１１”は、選択されたエントリの情報の示すノード（隣接ノード）にルーティング要求を転送する（ステップＳ２８）。
【０１１１】
この例では、選択されたエントリの情報の示すノードは、図２から明らかなように第０レベルのサブオーバーレイネットワーク１０-上でノード“１１１”に隣接する、ＩＤ＝０００のノード“０００”（ノード２０-0）である。この場合、上記ステップＳ２８では、ノード“１１１”からノード“０００”にルーティング要求が転送される。ＩＤ＝０００のノード“０００”が所属しているサブオーバーレイネットワークのうち最も深いレベルのサブオーバーレイネットワークは第１レベルのサブオーバーレイネットワーク１１-0である。つまり、ＩＤ＝０００のノード“０００”のサブオーバーレイネットワークＩＤ（ＩＤ ｎｗｉｄ）は“０”である。
【０１１２】
ＩＤ＝０００のノード“０００”は、ノード“１１１”からルーティング要求を受け取ると、ＩＤ＝００１とＩＤ ｎｗｉｄ＝０とを最上位ビットから比較することにより、最上位ビットから連続して一致するビット数ｋ＝１をカウントする（ステップＳ３１）。これによりノード“０００”は、自身が管理する隣接テーブル５２-0（ｔ＝０）から、第１レベルのサブオーバーレイネットワーク１１-0に対応する１番目のエントリ（ｔａｂｌｅ［１］）の情報、つまり第１レベルのサブオーバーレイネットワーク１１-0上で当該ノード“０００”に隣接するノードの情報を選択する（ステップＳ３２）。
【０１１３】
選択されたノードの情報は、図２から明らかなように、ＩＤ＝００１のノード“００１”の情報、つまり目的とするルーティング先のノード“００１”の情報である（ステップＳ３３）。この場合、ノード“０００”は、選択されたノードの情報からＩＤ＝００１のノード“００１”のアドレスａｄｄｒを取得して（ステップＳ３４）、ノード“１１１”に応答を返す（ステップＳ３５）。これによりノード“１１１”は、ＩＤ＝００１のノード“００１”（ノード２０-1）のアドレスａｄｄｒを取得して（ステップＳ２９）、ノード探索処理を完了する（ステップＳ３０）。
【０１１４】
以上の具体例から理解されるように、ノード探索処理（ルーティング処理）を行うノード（以下、第１のノードと称する）が参加しているサブオーバーレイネットワークにルーティング先のノード（以下、第２のノードと称する）も参加しているのであれば、第１のノードを起点に当該サブオーバーレイネットワーク上の隣接ノードを辿ることにより、他のサブオーバーレイネットワークを経由することなくルーティングすることが可能である。この場合、第１及び第２のノードが共に参加しているサブオーバーレイネットワークのレベルが深いほど、当該サブオーバーレイネットワーク上のノードの数は少なくなるため、高速ルーティングが可能となる。
【０１１５】
また、第１のノードが参加しているサブオーバーレイネットワークに第２のノード（ルーティング先のノード）が参加していない場合であっても、当該両ノードが共通して参加している上位レベルのサブオーバーレイネットワークに包含されている別のサブオーバーレイネットワークにルーティング先のノードが参加しているのであれば、それより更に上位レベルのサブオーバーレイネットワークに包含される別のサブオーバーレイネットワークを経由することなくルーティング可能である。
【０１１６】
［第２の実施形態］
次に本発明の第２の実施形態について説明する。第２の実施形態の特徴は、上記第１の実施形態と比較して、より少ないホップ数でのルーティングを可能にするための仕組みを有している点である。第２の実施形態において、オーバーレイネットワークに参加可能なノード及び当該ノードの基本構成は上記第１の実施形態と同様であるものとする。そこで以下の説明では、図１、図３及び図４を援用する。
【０１１７】
＜ノードが保持する構成情報＞
図１１は、第２の実施形態で適用される構成情報５００-tのデータ構造例を示し、図１２は図１１に示される構成情報５００-tに含まれているスキップテーブル５２３-tのデータ構造例を示す。構成情報５００-tは、図４に示されるノード２０-tの構成情報記憶部２７に格納されるものとする。構成情報５００-tは、ノード情報５１０-tと、隣接テーブル５２１-t及び５２２-tと、スキップテーブル５２３-tとから構成される。ノード情報５１０-tは第１の実施形態で適用された構成情報５０-tと同一構造を有している。
【０１１８】
隣接テーブル５２１-tは、図５に示される隣接テーブル５２-tに相当し、ノード２０-tが参加している第ｍａｓｋレベルのサブオーバーレイネットワーク、及び当該第ｍａｓｋレベルのサブオーバーレイネットワークを包含する全てのサブオーバーレイネットワークのそれぞれのレベルのサブオーバーレイネットワーク上で、ノード２０-tに後続して隣接するノード（後続隣接ノード）の情報（後続隣接ノード情報）を保持するエントリ（後続隣接ノード情報エントリ）ｓｕｃｃｅｓｓｏｒ［ｍａｓｋ］〜ｓｕｃｃｅｓｓｏｒ［０］を有する。そこで隣接テーブル５２１-tを後続隣接テーブル５２１-tと呼ぶこともある。
【０１１９】
隣接テーブル５２２-tは、ノード２０-tが参加している第ｍａｓｋレベルのサブオーバーレイネットワーク、及び当該第ｍａｓｋレベルのサブオーバーレイネットワークを包含する全てのサブオーバーレイネットワークのそれぞれのレベルのサブオーバーレイネットワーク上で、ノード２０-tに先行して隣接するノード（先行隣接ノード）の情報（先行隣接ノード情報）を保持するエントリ（先行隣接ノード情報エントリ）ｐｒｅｄｅｃｅｓｓｏｒ［ｍａｓｋ］〜ｐｒｅｄｅｃｅｓｓｏｒ［０］を有する。そこで隣接テーブル５２２-tを先行隣接テーブル５２２-tと呼ぶこともある。
【０１２０】
後続隣接ノード（successor node）及び先行隣接ノード（predecessor node）とは、各レベルのサブオーバーレイネットワークに所属する全てのノードのｉｄ（ＩＤ ｉｄ）を昇順に整列してリング状に並べたときの、それぞれ、ノード２０-t自身のｉｄから時計回りで隣接しているｉｄを持つノード及び反時計回りで隣接しているｉｄを持つノードを指す。
【０１２１】
後続隣接テーブル５２１-tのエントリｓｕｃｃｅｓｓｏｒ［ｍａｓｋ］〜ｓｕｃｃｅｓｓｏｒ［０］に保持される隣接ノード情報及び先行隣接テーブル５２２-tのエントリｐｒｅｄｅｃｅｓｓｏｒ［ｍａｓｋ］〜ｐｒｅｄｅｃｅｓｓｏｒ［０］に保持される隣接ノード情報は、それぞれ、後続隣接ノード及び先行隣接ノードのＩＤ ｉｄ及びＩＰアドレスａｄｄｒを含む。
【０１２２】
以下の説明では、エントリｓｕｃｃｅｓｓｏｒ［ｉ］に保持されるｉｄ及びａｄｄｒを、それぞれ、ｓｕｃｃｅｓｓｏｒ［ｉ］．ｉｄ及びｓｕｃｃｅｓｓｏｒ［ｉ］．ａｄｄｒと表記し、エントリｐｒｅｄｅｃｅｓｓｏｒ［ｉ］に保持されるｉｄ及びａｄｄｒを、それぞれ、ｐｒｅｄｅｃｅｓｓｏｒ［ｉ］．ｉｄ及びｐｒｅｄｅｃｅｓｓｏｒ［ｉ］．ａｄｄｒと表記することもある。また、エントリｓｕｃｃｅｓｓｏｒ［ｉ］に保持される情報自体をｓｕｃｃｅｓｓｏｒ［ｉ］、エントリｓｕｃｃｅｓｓｏｒ［ｍａｓｋ］〜ｓｕｃｃｅｓｓｏｒ［０］に保持される情報全体、つまり後続隣接テーブル５２１-tに保持される情報全体をｓｕｃｃｅｓｓｏｒと表記することもある。同様に、エントリｐｒｅｄｅｃｅｓｓｏｒ［ｉ］に保持される情報自体をｐｒｅｄｅｃｅｓｓｏｒ［ｉ］、エントリｐｒｅｄｅｃｅｓｓｏｒ［ｍａｓｋ］〜ｐｒｅｄｅｃｅｓｓｏｒ［０］に保持される情報全体、つまり先行隣接テーブル５２２-tに保持される情報全体をｐｒｅｄｅｃｅｓｓｏｒと表記することもある。
【０１２３】
このように、第２の実施形態で適用される構成情報５００-tは、第１の実施形態で適用される構成情報５０-tに先行隣接テーブル５２２-t及びスキップテーブル５２３-tが追加された情報であるといえる。
【０１２４】
スキップテーブル５２３-tは、第１の実施形態と比較して、ルーティングをより少ないホップ数の問い合わせ転送で可能にするためのショートカットパスを記述したテーブルである。スキップテーブル５２３-tは、非特許文献５，６に記載されているフィンガーテーブル（fingertable）に相当する。
【０１２５】
スキップテーブル５２３-tは、ｊ＝｛０，…ｍａｓｋ｝，ｉ＝｛０，…ｍａｓｋ−ｊ｝に関して、以下の情報
ｓｋｉｐ［ｊ］［ｉ］．ｓｔａｒｔ
＝｛ｎｗｉｄ＞＞（ｍａｓｋ−ｊ）＜＜（Ｍ−ｊ）｝
＋（ｎｉｄ＋２i）ｍｏｄ ２M-j
ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓ
＝ｓｋｉｐ［ｊ］［ｉ］．ｓｔａｒｔ（第ｊレベルのサブオーバーレイネットワークに包含される全てのノードの持つｉｄの空間であるＩＤ空間の起点となるＩＤ）
ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｅ
＝ｓｋｉｐ［ｊ］［ｉ＋１ ｍｏｄ（ｍａｓｋ−ｊ＋１）］．ｓｔａｒｔ
ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ
＝第ｊレベルのサブオーバーレイネットワークに包含される全てのノードの持つｉｄを昇順に整列してリング状に並べたときの、ＩＤ ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓから時計回りで最も近いＩＤを持つノード（後続スキップノード）のＩＤ
ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒ
＝ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄで示されるノードのアドレス
を保持する。
【０１２６】
ここで、｛ｎｗｉｄ＞＞（ｍａｓｋ−ｊ）＜＜（Ｍ−ｊ）｝の表記は、ｎｗｉｄを（ｍａｓｋ−ｊ）ビットだけ右にシフトし、この右シフトされたｎｗｉｄを（Ｍ−ｊ）だけ左方向にシフトしたものであることを示す。
【０１２７】
以降の説明では、ｊ＝｛０，…ｍａｓｋ｝，ｉ＝｛０，…ｍａｓｋ−ｊ｝の組み合わせ［ｊ］［ｉ］に対応するスキップテーブル５２３-tのエントリを、ｓｋｉｐ［ｊ］［ｉ］と呼ぶ。
【０１２８】
図１３は、ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓとｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄとの関係を示す。
【０１２９】
＜オーバーレイネットワークの構成＞
次に、第２の実施形態においてオーバーレイネットワークを再構成する場合に必要となる、新しく参加するノードの隣接テーブル及びスキップテーブルを構築する手順について、図１４、図１５Ａ、図１５Ｂ、図１６及び図１７のフローチャートを参照して説明する。ここで、第１の実施形態と同様に、新しく参加するノードがノードＮｏｄｅであり、既にオーバーレイネットワークに参加している任意のノードがノードｎであるものとする。
【０１３０】
また、ノードＮｏｄｅの構成情報記憶部２７に格納される構成情報５００-t、当該構成情報５００-tに含まれているノード情報５１０-t、後続隣接テーブル５２１-t、先行隣接テーブル５２２-t及びスキップテーブル５２３-tを、それぞれ構成情報５００-t(N)、ノード情報５１０-t(N)、後続隣接テーブル５２１-t(N)、先行隣接テーブル５２２-t(N)及びスキップテーブル５２３-t(N)と表現する。同様に、ノードｎの構成情報記憶部２７に格納される構成情報５００-t、当該構成情報５００-tに含まれているノード情報５１０-t、後続隣接テーブル５２１-t、先行隣接テーブル５２２-t及びスキップテーブル５２３-tを、それぞれ構成情報５００-t(n)、ノード情報５１０-t(n)、後続隣接テーブル５２１-t(n)、先行隣接テーブル５２２-t(n)及びスキップテーブル５２３-t(n)と表現する。また、後続隣接テーブル５２１-t(N)に保持される第ｊレベルのサブオーバーレイネットワーク上での隣接ノードのｉｄ（ｓｕｃｃｅｓｓｏｒ［ｊ］．ｉｄ），ａｄｄｒ（ｓｕｃｃｅｓｓｏｒ［ｊ］．ｉｄ）を、それぞれＮｏｄｅ．ｓｕｃｃｅｓｓｏｒ［ｊ］．ｉｄ，Ｎｏｄｅ．ｓｕｃｃｅｓｓｏｒ［ｊ］．ａｄｄｒと表記する。同様に、先行隣接テーブル５２２-t(N)に保持される第ｊレベルのサブオーバーレイネットワーク上での隣接ノードのｉｄ（ｓｕｃｃｅｓｓｏｒ［ｊ］．ｉｄ），ａｄｄｒ（ｐｒｅｄｅｃｅｓｓｏｒ［ｊ］．ｉｄ）を、それぞれＮｏｄｅ．ｐｒｅｄｅｃｅｓｓｏｒ［ｊ］．ｉｄ，Ｎｏｄｅ．ｐｒｅｄｅｃｅｓｓｏｒ［ｊ］．ａｄｄｒと表記する。
【０１３１】
まずノードＮｏｄｅのテーブル管理部２８は、自身の後続隣接テーブル５２１-t(N)及び先行隣接テーブル５２２-t(N)を初期化する（ステップＳ４１）。ここで、ノードＮｏｄｅの構成情報５００-t(N)のノード情報５１０-t(N)に含まれているマスクビット数ｍａｓｋがＮｏｄｅ．ｍａｓｋであるものとすると、後続隣接テーブル５２１-t(N)の初期化は、ｊ＝０〜ｊ＝Ｎｏｄｅ．ｍａｓｋまでの各レベル（第ｊレベル）のサブオーバーレイネットワーク上での後続隣接ノードのｉｄ（つまり、ｓｕｃｃｅｓｓｏｒ［ｊ］．ｉｄ）及び当該後続隣接ノードのａｄｄｒ（つまり、ｓｕｃｃｅｓｓｏｒ［ｊ］．ａｄｄｒ）を、当該ノードＮｏｄｅのｉｄ（つまり、Ｎｏｄｅ．ｉｄ）及びａｄｄｒ（つまり、Ｎｏｄｅ．ａｄｄｒ）に初期設定することにより行われる。同様に、先行隣接テーブル５２２-t(N)の初期化は、ｊ＝０〜ｊ＝Ｎｏｄｅ．ｍａｓｋまでの各レベル（第ｊレベル）のサブオーバーレイネットワーク上での先行隣接ノードのｉｄ（つまり、ｐｒｅｄｅｃｅｓｓｏｒ［ｊ］．ｉｄ）及び当該先行隣接ノードのａｄｄｒ（つまり、ｐｒｅｄｅｃｅｓｓｏｒ［ｊ］．ａｄｄｒ）を、Ｎｏｄｅ．ｉｄ及びＮｏｄｅ．ａｄｄｒに初期設定することにより行われる。
【０１３２】
ノードＮｏｄｅのテーブル管理部２８は、自身の隣接テーブル５２１-t(N)及び５２２-t(N)を初期化すると、ノードｎを介して、当該隣接テーブル５２１-t(N)及び５２２-t(N)を構築するために、当該ノードｎに対してノードＮｏｄｅの参加を要求する（ステップＳ４２）。即ちノードＮｏｄｅのテーブル管理部２８は、ノードｎに対して当該ノードＮｏｄｅの後続隣接ノードｓｕｃｃｅｓｓｏｒ［０，…Ｎｏｄｅ．ｍａｓｋ］及び先行隣接ノードｐｒｅｄｅｃｅｓｓｏｒ［０，…Ｎｏｄｅ．ｍａｓｋ］を通信機構２４経由で問い合わせる。この問い合わせ（参加要求）は、値が初期値０のビット数ｋ（＝０）、及びノードＮｏｄｅの構成情報５００-t(N)中のＮｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ，ｓｕｃｃｅｓｓｏｒ［０，…Ｎｏｄｅ．ｍａｓｋ］，ｐｒｅｄｅｃｅｓｓｏｒ［０，…Ｎｏｄｅ．ｍａｓｋ］｝を含む。ｓｕｃｃｅｓｓｏｒ［０，…Ｎｏｄｅ．ｍａｓｋ］は、ｓｕｃｃｅｓｓｏｒ［０，…Ｎｏｄｅ．ｍａｓｋ］．ｉｄ及びｓｕｃｃｅｓｓｏｒ［０，…Ｎｏｄｅ．ｍａｓｋ］．ａｄｄｒを含む。なお、ｓｕｃｃｅｓｓｏｒ［０，…Ｎｏｄｅ．ｍａｓｋ］及びｐｒｅｄｅｃｅｓｓｏｒ［０，…Ｎｏｄｅ．ｍａｓｋ］を、それぞれｓｕｃｃｅｓｓｏｒ及びｐｒｅｄｅｃｅｓｓｏｒと表すこともある。
【０１３３】
ノードｎのテーブル管理部２８は、ノードＮｏｄｅから上記の問い合わせを受け取ると、図１５Ａ及び図１５Ｂのフローチャートの示す手順で以下の処理を実行する。まずノードｎのテーブル管理部２８は、受け取った問い合わせに含まれているｋ，Ｎｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ，ｓｕｃｃｅｓｓｏｒ［０，…Ｎｏｄｅ．ｍａｓｋ］，ｐｒｅｄｅｃｅｓｓｏｒ［０，…Ｎｏｄｅ．ｍａｓｋ］｝及び自身のＩＤ（ｎ．ｉｄ）に基づき、ｒｉｎｇ［ｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ］．ｉｄ，Ｎｏｄｅ．ｉｄ，ｎ．ｉｄ）が正であるかを判定する（ステップＳ５１）。ここで、ｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ］．ｉｄは第ｋレベルのオーバーレイネットワークにおいてノードｎの先行隣接ノードのＩＤを示す。また、Ｎｏｄｅ．ｉｄ及びｎ．ｉｄは、それぞれ、ノードＮｏｄｅ及びｎのＩＤを示す。ステップＳ５１の判定結果は、例えばノードＮｏｄｅのＩＤが、リング上でノードｎの先行隣接ノードのＩＤ及びノードｎのＩＤの間に位置するならば正となる。つまりノードＮｏｄｅの参加により、当該ノードＮｏｄｅが新たにノードｎの先行隣接ノードとなり、したがって当該ノードＮｏｄｅが参加するまではノードｎの先行隣接ノードであったノード（ｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ］）が新たに当該ノードＮｏｄｅの先行隣接ノードとなるならば、ステップＳ５１の判定結果は正となる。
【０１３４】
ノードｎのテーブル管理部２８は、ステップＳ５１の判定結果が正の場合、ノードＮｏｄｅからの問い合わせに含まれている当該ノードＮｏｄｅの構成情報５００-tの内容を修正する（ステップＳ５２）。具体的には、ノードｎのテーブル管理部２８は、ノードＮｏｄｅの構成情報５００-t(N)におけるＮｏｄｅ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ］．ｉｄ及びＮｏｄｅ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ］．ａｄｄｒを、それぞれｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ］．ｉｄ及びｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ］．ａｄｄｒに修正（更新）する。またノードｎのテーブル管理部２８は、ノードＮｏｄｅの構成情報５００-t(N)におけるＮｏｄｅ．ｓｕｃｃｅｓｓｏｒ［ｋ］．ｉｄ及びＮｏｄｅ．ｓｕｃｃｅｓｓｏｒ［ｋ］．ａｄｄｒを、それぞれｎ．ｉｄ及びｎ．ａｄｄｒに修正（更新）する。またノードｎのテーブル管理部２８は、当該ノードｎ自身の構成情報５００-t(n)におけるｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ］．ｉｄ及びｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ］．ａｄｄｒを、それぞれノードＮｏｄｅのｉｄ及びａｄｄｒ、即ち、Ｎｏｄｅ．ｉｄ及びＮｏｄｅ．ａｄｄｒに修正（更新）する。
【０１３５】
次に、ノードｎのテーブル管理部２８は、第ｋレベルのサブオーバーレイネットワーク上でのノードＮｏｄｅの先行隣接ノードのｉｄ（つまり、Ｎｏｄｅ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ］．ｉｄ）に基づき、当該隣接ノード（Ｎｏｄｅ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ］）に、後続ノードの更新を通知する（ステップＳ５３）。この通知（更新通知）は、ｋ及びＮｏｄｅ．｛ｉｄ，ａｄｄｒ｝を含む。
【０１３６】
ノードＮｏｄｅ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ］（以下ノードｎ’と称する）は、ノードｎからの更新通知を受け取ると、通知されたｋ及びＮｏｄｅ．｛ｉｄ，ａｄｄｒ｝に基づき、自身の構成情報５００-tの後続隣接テーブル５２１-tに含まれている、第ｋレベルのサブオーバーレイネットワーク上での当該ノードｎ’の後続ノードのｉｄ及びａｄｄｒ、即ちｎ’．ｓｕｃｃｅｓｓｏｒ［ｋ］．ｉｄ及びｎ’．ｓｕｃｃｅｓｓｏｒ［ｋ］．ａｄｄｒを、それぞれ、Ｎｏｄｅ．ｉｄ及びＮｏｄｅ．ａｄｄｒに修正（更新）する（ステップＳ７１）。
【０１３７】
ノードｎのテーブル管理部２８はステップＳ５３を実行すると、ｋを１インクリメントして（ステップＳ５４）、そのインクリメント後のｋがＮｏｄｅ．ｍａｓｋを超えているかを判定する（ステップＳ５５）。もし、インクリメント後のｋがＮｏｄｅ．ｍａｓｋを超えていないならば、ノードｎのテーブル管理部２８はＮｏｄｅ．ｉｄの先頭のｋビットとｎ．ｉｄの先頭のｋビットとが一致するかを判定する（ステップＳ５６）。もし、一致しているならば、ノードｎのテーブル管理部２８は、インクリメント後のｋを用いて、ステップＳ５１から始まる処理を再度実行する。
【０１３８】
これに対して、Ｎｏｄｅ．ｉｄの先頭のｋビットとｎ．ｉｄの先頭のｋビットとが一致しないならば（ステップＳ５６）、ノードｎのテーブル管理部２８は、今度はＮｏｄｅ．ｉｄの先頭のｋビットとｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ−１］．ｉｄの先頭のｋビットとが一致するかを判定する（ステップＳ５７）。もし、一致しているならば、ノードｎのテーブル管理部２８は、ＩＤがｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ−１］．ｉｄである第ｋ−１レベルのサブオーバーレイネットワーク上での先行隣接ノード、つまりノードｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ−１］に、ノードＮｏｄｅからの問い合わせを転送して（ステップＳ５８）、処理を終了する。このノードｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ−１］は、ノードＮｏｄｅから問い合わせられた新たなノード（新ノード）ｎとして機能する。新ノードｎに転送される問い合わせは、現在のｋと、ノードＮｏｄｅの構成情報５００-t(N)であるＮｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ，ｓｕｃｃｅｓｓｏｒ，ｐｒｅｄｅｃｅｓｓｏｒ｝とを含む。
【０１３９】
これに対し、Ｎｏｄｅ．ｉｄの先頭のｋビットとｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｋ−１］．ｉｄの先頭のｋビットとが一致していないならば（ステップＳ５７）、ノードｎのテーブル管理部２８は、ステップＳ５９に進む。また、インクリメント後のｋがＮｏｄｅ．ｍａｓｋを超えている場合にも（ステップＳ５５）、ノードｎのテーブル管理部２８はステップＳ５９に進む。このステップＳ５９において、ノードｎのテーブル管理部２８は、ノードＮｏｄｅからの問い合わせに対する応答として、当該ノードＮｏｄｅの後続ノード及び先行ノードに関する情報Ｎｏｄｅ．｛ｓｕｃｃｅｓｓｏｒ，ｐｒｅｄｅｃｅｓｓｏｒ｝を当該ノードＮｏｄｅに返して、処理を終了する。
【０１４０】
また、ステップＳ５１の判定結果が“Ｎｏ”の場合、即ちノードＮｏｄｅのＩＤが、リング上でノードｎの先行隣接ノードのＩＤ及びノードｎのＩＤの間に位置しない場合（ステップＳ５１）、ノードｎのテーブル管理部２８は自身のスキップテーブル５２３-t(n)のエントリｓｋｉｐ［ｋ］［ｉ］（ｉ＝｛０，…Ｎｏｄｅ．ｍａｓｋ−ｋ｝）を参照して、問い合わせ元のノードＮｏｄｅのｉｄ（Ｎｏｄｅ．ｉｄ）が、範囲［ｎ．ｓｋｉｐ［ｋ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓ，ｎ．ｓｋｉｐ［ｋ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｅ）に収まるかを判定する（ステップＳ６０）。ノードｎのテーブル管理部２８は、ステップＳ６０を、ｉを切り替えながら（ｉ＝｛０，…Ｎｏｄｅ．ｍａｓｋ−ｋ｝）、Ｎｏｄｅ．ｉｄが上記の範囲に収まるまで繰り返す。
【０１４１】
もし、あるｉの値で、Ｎｏｄｅ．ｉｄが、上記の範囲に収まったならば、ノードｎのテーブル管理部２８は、ノードｎ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒにノードＮｏｄｅからの問い合わせを転送して（ステップＳ６１）、処理を終了する。このノードノードｎ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒは、ノードＮｏｄｅから問い合わせられた新たなノード（新ノード）ｎとして機能する。新ノードｎに転送される問い合わせは、現在のｋと、ノードＮｏｄｅの構成情報５００-t(N)であるＮｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ，ｓｕｃｃｅｓｓｏｒ，ｐｒｅｄｅｃｅｓｓｏｒ｝とを含む。
【０１４２】
さて、ノードＮｏｄｅのテーブル管理部２８は、ステップＳ４２での問い合わせに対して、問い合わせ先のノードｎから応答を受け取ると（ステップＳ４３）、ｊ＝０〜ｊ＝Ｎｏｄｅ．ｍａｓｋ及びｉ＝０〜ｉ＝Ｎｏｄｅ．ｍａｓｋ−ｊのうちの１つのｊ，ｉの組み合わせについて、当該ノードＮｏｄｅのスキップテーブル５２３-t(N)のＮｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｓｔａｒｔ，Ｎｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓ，Ｎｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｅ，Ｎｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ及びＮｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒを初期化する（ステップＳ４４）。ここでは、Ｎｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｓｔａｒｔは｛Ｎｏｄｅ．ｎｗｉｄ＞＞（Ｎｏｄｅ．ｍａｓｋ−ｊ）＜＜（Ｍ−ｊ）｝＋（Ｎｏｄｅ．ｎｉｄ＋２i）ｍｏｄ ２M-jに、Ｎｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓはＮｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｓｔａｒｔに、そしてＮｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｅはＮｏｄｅ．ｓｋｉｐ［ｊ］［ｉ＋１ ｍｏｄ（Ｎｏｄｅ．ｍａｓｋ−ｊ＋１）］．ｓｔａｒｔに、それぞれ初期設定される。また、Ｎｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄは、Ｎｏｄｅ．ｉｄに、そしてＮｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒはＮｏｄｅ．ａｄｄｒに、それぞれ初期設定される。
【０１４３】
ノードＮｏｄｅのテーブル管理部２８は、自身のスキップテーブル５２３-t(N)を初期化すると、既にオーバーレイネットワークに参加している任意のノードｎを介して、当該スキップテーブル５２３-t(N)を構築するために、当該ノードｎに対してノードＮｏｄｅのｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒを問い合わせる（ステップＳ４５）。この問い合わせは、ｉ，ｊ、及びノードＮｏｄｅの構成情報５００-t(N)中のＮｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ，ｓｋｉｐ［ｊ］［ｉ］｝を含む。
【０１４４】
ステップＳ４４及びＳ４５は、ｊ＝０〜ｊ＝Ｎｏｄｅ．ｍａｓｋ及びｉ＝０〜ｉ＝Ｎｏｄｅ．ｍａｓｋ−ｊの全てのｊ，ｉの組み合わせについて繰り返される。即ち、ステップＳ４５の問い合わせに対する応答が返される都度（ステップＳ４６）、ｊまたはｉが変更されてステップＳ４４及びＳ４５を実行する動作が繰り返される。、
ノードｎのテーブル管理部２８は、ノードＮｏｄｅからステップＳ４５での上記の問い合わせを受け取ると、図１７のフローチャートの示す手順で以下の処理を実行する。まずノードｎのテーブル管理部２８は、受け取った問い合わせに含まれているｉ，ｊ，Ｎｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ，ｓｋｉｐ［ｉ］［ｊ］｝及び自身のＩＤ（ｎ．ｉｄ）に基づき、ｒｉｎｇ（ｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｊ］．ｉｄ，Ｎｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓ，ｎ．ｉｄ］が正であるかを判定する（ステップＳ８１）。ステップＳ８１の判定結果は、Ｎｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓが、例えば第ｊレベルのサブオーバーレイネットワークのリング上でノードｎの先行隣接ノードｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｊ］のＩＤ（ｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｊ］．ｉｄ）及び当該ノードｎのＩＤ（ｎ．ｉｄ）の間に位置するならば正となる。
【０１４５】
ノードｎのテーブル管理部２８は、ステップＳ８１の判定結果が“Ｎｏ”の場合、第ｋレベル（ｋの初期値は０）のサブオーバーレイネットワークについて、Ｎｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓが、範囲［ｎ．ｓｋｉｐ［ｊ］［ｋ］．ｉｎｔｅｒｖａｌ＿ｓ，ｎ．ｓｋｉｐ［ｊ］［ｋ］．ｉｎｔｅｒｖａｌ＿ｅ）に収まるかを判定する（ステップＳ８２）。ノードｎのテーブル管理部２８は、ステップＳ８２を、ｋを切り替えながら（ｋ＝｛０，…Ｎｏｄｅ．ｍａｓｋ−ｊ｝、Ｎｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓが上記の範囲に収まるまで繰り返す。
【０１４６】
もし、あるｋの値で、Ｎｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓが上記の範囲に収まったならば、ノードｎのテーブル管理部２８は、ノードｎ．ｓｋｉｐ［ｊ］［ｋ］．ｓｕｃｃｅｓｓｏｒ（後続スキップノード）にノードＮｏｄｅからの問い合わせを転送して（ステップＳ８３）、処理を終了する。このノードｎ．ｓｋｉｐ［ｊ］［ｋ］．ｓｕｃｃｅｓｓｏｒが、ノードＮｏｄｅから問い合わせられた新たなノード（新ノード）ｎとなって、上記ステップＳ８１から始まる処理を実行する。新ノードｎに転送される問い合わせは、ｉ，ｊ、及びＮｏｄｅ．｛ｉｄ，ｍａｓｋ，ａｄｄｒ，ｓｋｉｐ［ｊ］［ｉ］｝を含む。
【０１４７】
一方、ステップＳ８１の判定結果が正の場合、即ちＮｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓが、第ｊレベルのサブオーバーレイネットワークにおけるノードｎの先行隣接ノードｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｊ］のＩＤ（ｎ．ｐｒｅｄｅｃｅｓｓｏｒ［ｊ］．ｉｄ）及び当該ノードｎのＩＤ（ｎ．ｉｄ）の間に位置する場合、ノードｎのテーブル管理部２８はステップＳ８４に進む。このステップＳ８４において、ノードｎのテーブル管理部２８は、ノードＮｏｄｅのスキップテーブル５２３-t(N)に保持されるべきＮｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ及びＮｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒを、それぞれ当該ノードｎのＩＤ（ｎ．ｉｄ）及びアドレス（ｎ．ａｄｄｒ）に修正（更新）する。ノードｎのテーブル管理部２８は、この修正後の情報Ｎｏｄｅ．ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒをノードＮｏｄｅに通知して（ステップＳ８５）、処理を終了する。
【０１４８】
このように第２の実施形態においては、オーバーレイネットワークに新たに参加するノードＮｏｄｅは、後続隣接テーブル５２１-t(N)及び先行隣接テーブル５２２-t(N)の初期化の後に、既にオーバーレイネットワークに参加している任意のノードｎのアドレスを第１の実施形態と同様の方法により取得し、図１５Ａ及び図１５Ｂのフローチャートに従い、当該ノードｎを経由して後続隣接テーブル５２１-t(N)及び先行隣接テーブル５２２-t(N)を構築する。次にノードＮｏｄｅは、隣接ノードを経由することにより、図１６のフローチャートに従い、スキップテーブル５２３-t(N)を構築する。なお、オーバーレイネットワークに既に参加しているノードでもスキップテーブルを更新する必要があるが、この方法については非特許文献５及び６に示されている。
【０１４９】
＜ノードの探索＞
次に、第１の実施形態と同様に、ノードｓｔａｒｔがノードＮｏｄｅのルーティングを行う場合の手順について、図１８及び図１９のフローチャートを参照して説明する。
【０１５０】
まず、ノードｓｔａｒｔのルーティング部２９は自身が管理するスキップテーブル５２３-tを参照することにより、ｓｔａｒｔ．ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ（ｊ＝｛０，…Ｎｏｄｅ．ｍａｓｋ｝，ｉ＝｛０，…Ｎｏｄｅ．ｍａｓｋ−ｊ｝）がルーティング先のノードＮｏｄｅのＩＤ（Ｎｏｄｅ．ｉｄ）に一致するかを判定する（ステップＳ９１）。
【０１５１】
ノードｓｔａｒｔのルーティング部２９は、ステップＳ９１を、ｊ＝｛０，…ｓｔａｒｔ．ｍａｓｋ｝，ｉ＝｛０，…ｓｔａｒｔ．ｍａｓｋ｝の組み合わせについて、当該ステップＳ９１の判定結果が“Ｙｅｓ”となるまで繰り返す。
【０１５２】
もし、ステップＳ９１の判定結果が“Ｙｅｓ”となったならば、ノードｓｔａｒｔのルーティング部２９はノード探索成功を判定する。この場合、ノードｓｔａｒｔのルーティング部２９は、スキップテーブル５２３-tに基づいて、ルーティング先のノードＮｏｄｅのＩＰアドレスとして、ステップＳ９１の判定結果が“Ｙｅｓ”となった際のｊ，ｉに対応するｓｔａｒｔ．ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒを取得してノード探索処理を完了する（ステップＳ９２）。
【０１５３】
一方、ｊ＝｛０，…ｓｔａｒｔ．ｍａｓｋ｝，ｉ＝｛０，…ｓｔａｒｔ．ｍａｓｋ｝の全ての組み合わせについてステップＳ９１を繰り返しても、当該ステップＳ９１の判定結果が“Ｎｏ”の場合、ノードｓｔａｒｔのルーティング部２９はステップＳ９３に進む。
【０１５４】
ステップＳ９３においてノードｓｔａｒｔのルーティング部２９は、第１の実施形態におけるステップＳ２１と同様に、ルーティング先のノードＮｏｄｅのＩＤ Ｎｏｄｅ．ｉｄに含まれているサブオーバーレイネットワークＩＤ Ｎｏｄｅ．ｎｗｉｄと当該ノードｓｔａｒｔ自身のＩＤであるｓｔａｒｔ．ｉｄに含まれているサブオーバーレイネットワークＩＤ ｓｔａｒｔ．ｎｗｉｄとを、最上位ビットから順に比較する。このステップＳ９３においてノードｓｔａｒｔのルーティング部２９は、上記の比較により、Ｎｏｄｅ．ｎｗｉｄとｓｔａｒｔ．ｎｗｉｄとが最上位ビットから連続して一致する最大ビット数ｋをカウントする。
【０１５５】
次にノードｓｔａｒｔのルーティング部２９は、自身のスキップテーブル５２３-tのエントリｓｋｉｐ［ｋ］［ｉ］（ｉ＝｛０，…ｓｔａｒｔ．ｍａｓｋ−ｋ｝）の内容（ｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓ及びｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｅの対）を参照して、ルーティング先のノードＮｏｄｅのｉｄ（Ｎｏｄｅ．ｉｄ）が、この内容で示される範囲［ｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓ，ｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｅ）に収まるかを判定する（ステップＳ９４）。即ちノードｓｔａｒｔのルーティング部２９は、ルーティング先のノードＮｏｄｅがｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓのｓｕｃｃｅｓｓｏｒ．ｉｄ（ｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）であるかを判定する。ノードｓｔａｒｔのルーティング部２９は、ステップＳ９４を、ｉ＝｛０，…ｓｔａｒｔ．ｍａｓｋ−ｋ｝について、Ｎｏｄｅ．ｉｄが上記の範囲に収まるまで繰り返す。
【０１５６】
もし、あるｉの値で、Ｎｏｄｅ．ｉｄが上記の範囲に収まったならば（ステップＳ９４）、ノードｓｔａｒｔのルーティング部２９は、ｒｉｎｇ［ｓｔａｒｔ．ｉｄ，Ｎｏｄｅ．ｉｄ，ｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）が正であるか、つまりＮｏｄｅ．ｉｄが、第ｉレベルのサブオーバーレイネットワークのリング上で、範囲［ｓｔａｒｔ．ｉｄ，ｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）に収まるという条件を満たした並びであるかを判定する（ステップＳ９５）。ｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄは、Ｎｏｄｅ．ｉｄが上記の範囲［ｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓ，ｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｅ）に収まったとステップＳ９４で判定された際に用いられた、スキップテーブル５２３-tのエントリｓｋｉｐ［ｋ］［ｉ］に格納されている。
【０１５７】
ステップＳ９５の判定結果が“Ｙｅｓ”の場合、Ｎｏｄｅ．ｉｄはｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄではないことになり、上記ステップＳ９４の判定結果と矛盾する。この場合、ノードｓｔａｒｔのルーティング部２９は、ルーティング先のノードＮｏｄｅは存在せず、したがってノード探索処理に失敗したとして当該処理を完了する（ステップＳ９６）。
【０１５８】
これに対してステップ９９の判定結果が“Ｎｏ”であり、したがって上記ステップＳ９４の判定結果と矛盾しないならば、ノードｓｔａｒｔのルーティング部２９は、第ｉレベルのサブオーバーレイネットワーク上におけるノードｓｔａｒｔ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒをルーティング要求先のノードｎとして、当該ノードｎに、ノードＮｏｄｅのＩＰアドレス（Ｎｏｄｅ．ａｄｄｒ）を取得するためのルーティング要求を転送する（ステップＳ９７）。ルーティング要求は、ノードＮｏｄｅのＩＤ ｉｄ（Ｎｏｄｅ．ｉｄ）及びマスクビット数ｍａｓｋ（Ｎｏｄｅ．ｍａｓｋ）、つまりＮｏｄｅ．｛ｉｄ，ｍａｓｋ｝と、ノードｓｔａｒｔのアドレス（ＩＰアドレス）ａｄｄｒ（ｓｔａｒｔ．ａｄｄｒ）を含む。
【０１５９】
ノードｎのルーティング部２９は、上記ルーティング要求（ここでは、ノードｓｔａｒｔからのルーティング要求）を受け取ると、図１９のフローチャートに従うノード探索処理を次のように実行する。まずノードｎのルーティング部２９は、、先のノードｓｔａｒｔにおけるステップＳ９１と同様のステップＳ１０１を実行する。即ちノードｎのルーティング部２９は、自身が管理するスキップテーブル５２３-tを参照することにより、ｎ．ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ（ｊ＝｛０，…ｎ．ｍａｓｋ｝，ｉ＝｛０，…ｎ．ｍａｓｋ−ｊ｝）がルーティング先のノードＮｏｄｅのＩＤ（Ｎｏｄｅ．ｉｄ）に一致するかを判定する（ステップＳ１０１）。
【０１６０】
ノードｎのルーティング部２９は、ステップＳ１０１を、ｊ＝｛０，…ｓｔａｒｔ．ｍａｓｋ｝，ｉ＝｛０，…ｓｔａｒｔ．ｍａｓｋ｝の組み合わせについて、当該ステップＳ１０１の判定結果が“Ｙｅｓ”となるまで繰り返す。
【０１６１】
もし、ステップＳ１０１の判定結果が“Ｙｅｓ”となったならば、ノードｎのルーティング部２９はノード探索成功を判定する。この場合、ノードｎのルーティング部２９は、スキップテーブル５２３-tに基づいて、ルーティング先のノードＮｏｄｅのＩＰアドレスとして、ステップＳ１０１の判定結果が“Ｙｅｓ”となった際のｊ，ｉに対応するｎ．ｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒを取得する（ステップＳ１０２）。このステップＳ１０２において、ノードｎのルーティング部２９は、自身が取得したノードＮｏｄｅのＩＰアドレスｓｋｉｐ［ｉ］［ｊ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒ（Ｎｏｄｅ．ａｄｄｒ）を含む応答を、ルーティング要求に含まれているＩＰアドレスｓｔａｒｔ．ａｄｄｒで指定されるノードｓｔａｒｔに返す。
【０１６２】
一方、ｊ＝｛０，…ｓｔａｒｔ．ｍａｓｋ｝，ｉ＝｛０，…ｓｔａｒｔ．ｍａｓｋ｝の全ての組み合わせについてステップＳ１０１を繰り返しても、当該ステップＳ１０１の判定結果が“Ｎｏ”の場合、ノードｎのルーティング部２９はステップＳ１０３に進む。
【０１６３】
ステップＳ１０３においてノードｎのルーティング部２９は、ステップＳ９３と同様に、ルーティング先のノードＮｏｄｅのＩＤ Ｎｏｄｅ．ｉｄに含まれているサブオーバーレイネットワークＩＤ Ｎｏｄｅ．ｎｗｉｄと当該ノードｎ自身のＩＤであるｎ．ｉｄに含まれているサブオーバーレイネットワークＩＤ ｎ．ｎｗｉｄとを、最上位ビットから順に比較する。このステップＳ１０３においてノードｎのルーティング部２９は、上記の比較により、Ｎｏｄｅ．ｎｗｉｄとｎ．ｎｗｉｄとが最上位ビットから連続して一致する最大ビット数ｋをカウントする。
【０１６４】
次にノードｎのルーティング部２９は、自身のスキップテーブル５２３-tのエントリｓｋｉｐ［ｋ］［ｉ］（ｉ＝｛０，…ｎ．ｍａｓｋ−ｋ｝）を参照して、ルーティング先のノードＮｏｄｅのｉｄ（Ｎｏｄｅ．ｉｄ）が、範囲［ｎ．ｓｋｉｐ［ｋ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓ，ｎ．ｓｋｉｐ［ｋ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｅ）に収まるかを判定する（ステップＳ１０４）。即ちノードｎのルーティング部２９は、ルーティング先のノードＮｏｄｅがｎ．ｓｋｉｐ［ｋ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓのｓｕｃｃｅｓｓｏｒ．ｉｄ（ｎ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）であるかを判定する。ノードｎのルーティング部２９は、ステップＳ１０４を、ｉ＝｛０，…ｎ．ｍａｓｋ−ｋ｝について、Ｎｏｄｅ．ｉｄが上記の範囲に収まるまで繰り返す。
【０１６５】
もし、あるｉの値で、Ｎｏｄｅ．ｉｄが上記の範囲に収まったならば、ノードｎのルーティング部２９は、ｒｉｎｇ［ｎ．ｉｄ，Ｎｏｄｅ．ｉｄ，ｎ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）が正であるか、つまりＮｏｄｅ．ｉｄが、第ｉレベルのサブオーバーレイネットワークのリング上で、範囲［ｎ．ｉｄ，ｎ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）に収まるという条件を満たした並びであるかを判定する（ステップＳ１０５）。
【０１６６】
ステップＳ１０５の判定結果が“Ｙｅｓ”の場合、Ｎｏｄｅ．ｉｄはｎ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄではないことになり、上記ステップＳ１０４の判定結果と矛盾する。この場合、ノードｎのルーティング部２９は、ルーティング先のノードＮｏｄｅは存在せず、したがってノード探索に失敗したとして、ノード探索失敗を通知するための応答を、ルーティング要求に含まれているＩＰアドレスｓｔａｒｔ．ａｄｄｒで指定されるノードｓｔａｒｔに返す（ステップＳ１０６）。
【０１６７】
これに対してステップ１１９の判定結果が“Ｎｏ”であり、したがって上記ステップＳ１０４の判定結果と矛盾しないならば、ノード（旧ノード）ｎのルーティング部２９は、第ｉレベルのサブオーバーレイネットワーク上におけるノードｎ．ｓｋｉｐ［ｋ］［ｉ］．ｓｕｃｃｅｓｓｏｒ（後続スキップノード）をルーティング要求先の新たなノード（新ノード）ｎとして、当該新ノードｎに、ノードＮｏｄｅのＩＰアドレス（Ｎｏｄｅ．ａｄｄｒ）を取得するためのルーティング要求を転送する（ステップＳ１０７）。このルーティング要求は、ステップＳ９７で転送されるルーティング要求と同様に、旧ノードｎが受け取ったルーティング要求に含まれているＮｏｄｅ．｛ｉｄ，ｍａｓｋ｝及びｓｔａｒｔ．ａｄｄｒを含む。旧ノードｎから新ノードｎにルーティング要求が転送された場合、新ノードｎでは、旧ノードｎと同様に図１９のフローチャートに従うノード探索処理を行う。
【０１６８】
さて、ノードｓｔａｒｔのルーティング部２９は、ノードｎがステップＳ１０２またはＳ１０６を実行したことにより当該ノードｎから返される応答を確認すると（ステップＳ９８）、ノード探索処理に成功または失敗したとして当該処理を完了する（ステップＳ９９）。
【０１６９】
このように本実施形態（第２の実施形態）において、ノードｓｔａｒｔ（またはノードｎ）は、ノードＮｏｄｅに対するルーティングを行うために、最短距離でのルーティングを可能にするスキップテーブル５２３-tのエントリを最大ビット数ｋのカウントにより選択する。即ちノードｓｔａｒｔ（またはノードｎ）は、最短距離でのルーティングを行うために、当該ノードｓｔａｒｔ（またはノードｎ）自身が管理しているスキップテーブル５２３-tから、当該ノードｓｔａｒｔ（またはノードｎ）自身及びルーティング先のノードＮｏｄｅが共に参加しているサブオーバーレイネットワークの中で最も深いレベルのサブオーバーレイネットワーク（第ｋサブオーバーレイネットワーク）に対応するエントリを選択する。もし、ノードＮｏｄｅが第ｋサブオーバーレイネットワーク上でノードｓｔａｒｔ（またはノードｎ）の後続スキップノードでないために、ノードＮｏｄｅに対するルーティングが行えないならば、ルーティング要求が後続スキップノードに転送される。ルーティング要求の転送先では、当該ルーティング要求の転送元と同様の処理が行われる。このようにして、ルーティング要求が後続スキップノードに転送される動作が繰り返されることにより、ノードＮｏｄｅに対するルーティングが行われる。上述のルーティング（ノード探索）方法により、近接性を考慮して、経由するサブオーバーレイネットワークの数を少なくしながら、第１の実施形態と比較してより少ないホップ数でルーティングを行うことができる。
【０１７０】
＜ノードの探索の具体例＞
次に、上述した図１８及び図１９のフローチャートの示す手順に従うノード探索の具体例について、図２０のオーバーレイネットワークの階層構造の例を参照して説明する。図２０には、ＩＤ（ＩＤ ｉｄ）＝１１１（マスクビット数ｍａｓｋ＝２），アドレス（ａｄｄｒ）＝１９２．１６８．０．１のノード（ｓｔａｒｔノード）“１１１”（ノード２０-7）が管理する構成情報５００-7（ｔ＝７）のデータ構造例も示されている。
【０１７１】
ここでは、第１の実施形態と同様に、ＩＤ（ＩＤ ｉｄ）＝１１１（ｍａｓｋ＝２）のノード（ｓｔａｒｔノード）“１１１”が、ＩＤ＝｛１１０，１０１，００１｝の各ノード“１１０”，“１０１”，“００１”に対するルーティングを行うものとする。ノード“１１１”のサブオーバーレイネットワークＩＤ（ＩＤ ｎｗｉｄ）は“１１”であることに留意する。
【０１７２】
まず、ＩＤ＝１１０のノード“１１０”（ノード２０-6）に対するルーティングについて説明する。ノード“１１１”（ｓｔａｒｔ）は、自身が管理するスキップテーブル５２３-7（ｔ＝７）のエントリｓｋｉｐ［２］［０］（第２レベルのサブオーバーレイネットワーク１１０-1に対応するエントリ）に格納されている後続スキップノードのＩＤ（ｓｔａｒｔ．ｓｋｉｐ［２］［０］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）がルーティング先のノードＮｏｄｅのＩＤ（Ｎｏｄｅ．ｉｄ）＝１１０に一致することを判定する（ステップＳ９１）。この場合、ノード“１１１”は、スキップテーブル５２３-7（ｔ＝７）のエントリｓｋｉｐ［２］［０］に格納されているｓｔａｒｔ．ｓｋｉｐ［２］［０］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒ＝１９２．１６８．１００．３をルーティング先のノードＮｏｄｅのＩＰアドレスとしてを取得して（ステップＳ９２）、ノード探索処理を完了する。つまりノード“１１１”は、ＩＤ＝１１０のノード“１１０”に関しては、第２レベルのサブオーバーレイネットワーク１１０-1を包含する、第１レベルのサブオーバーレイネットワーク１１-1及び第０レベルのサブオーバーレイネットワーク１０を経由することなくルーティングすることができる。
【０１７３】
次に、ＩＤ＝１０１のノード“１０１”に対するルーティングについて説明する。ノード“１１１”が管理するスキップテーブル５２３-7（ｔ＝７）には、ルーティング先のノードＮｏｄｅのＩＤ（Ｎｏｄｅ．ｉｄ）＝１０１に一致する後続スキップノードのＩＤは存在しない（ステップＳ９１）。この場合、ノード“１１１”は、ＩＤ＝１０１とＩＤ ｎｗｉｄ＝１１とを最上位ビットから順次比較することにより、最上位ビットから連続して一致するビット数ｋ＝１をカウントする（ステップＳ９３）。そしてノード“１１１”（ｓｔａｒｔ）は、自身が管理するスキップテーブル５２３-7（ｔ＝７）のエントリｓｋｉｐ［１］［１］（第１レベルのサブオーバーレイネットワーク１１-1に対応するエントリ）の内容（ｓｔａｒｔ．ｓｋｉｐ［１］［１］．ｉｎｔｅｒｖａｌ＿ｓ＝１０１及びｓｔａｒｔ．ｓｋｉｐ［１］［１］．ｉｎｔｅｒｖａｌ＿ｅ＝１１１の対）を参照する。この場合、ノード“１１１”は、ルーティング先のノードＮｏｄｅのｉｄ（Ｎｏｄｅ．ｉｄ）＝１０１が、参照された内容で示される範囲［ｓｔａｒｔ．ｓｋｉｐ［１］［１］．ｉｎｔｅｒｖａｌ＿ｓ，ｓｔａｒｔ．ｓｋｉｐ［１］［１］．ｉｎｔｅｒｖａｌ＿ｅ）＝［１０１，１１１）に収まることを判定する（ステップＳ９４）。
【０１７４】
するとノード“１１１”（ｓｔａｒｔ）は、ｒｉｎｇ［ｓｔａｒｔ．ｉｄ，Ｎｏｄｅ．ｉｄ，ｓｔａｒｔ．ｓｋｉｐ［１］［１］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）＝ｒｉｎｇ［１１１，１０１，１１０）が正であるかを判定する。ｓｋｉｐ［１］［１］．ｓｕｃｃｅｓｓｏｒ．ｉｄ＝１１０は、Ｎｏｄｅ．ｉｄがステップＳ９４で上記の範囲［１０１，１１１）に収まったと判定された際に用いられた、スキップテーブル５２３-tのエントリｓｋｉｐ［１］［１］に格納されている。ｒｉｎｇ［１１１，１０１，１１０）は正であり、ステップＳ９４の判定結果と矛盾する。この場合、ノード“１１１”はルーティング先のノードＮｏｄｅ（つまりＩＤが１０１のノード）は存在せず、したがってノード探索処理に失敗したとして当該処理を完了する（ステップＳ９６）。
【０１７５】
次に、ＩＤ＝００１のノード“００１”に対するルーティングについて説明する。ノード“１１１”（ｓｔａｒｔ）は、自身が管理するスキップテーブル５２３-7（ｔ＝７）のエントリｓｋｉｐ［０］［１］（第０レベルのサブオーバーレイネットワーク１０に対応するエントリ）に格納されている後続スキップノードのＩＤ（ｓｔａｒｔ．ｓｋｉｐ［０］［１］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）がルーティング先のノードＮｏｄｅのＩＤ（Ｎｏｄｅ．ｉｄ）＝００１に一致することを判定する（ステップＳ９１）。この場合、ノード“１１１”は、スキップテーブル５２３-7（ｔ＝７）のエントリｓｋｉｐ［０］［１］に格納されているｓｔａｒｔ．ｓｋｉｐ［０］［１］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒ＝１９２．１６８．３．１をルーティング先のノードＮｏｄｅのＩＰアドレスとしてを取得して（ステップＳ９２）、ノード探索処理を完了する。
【０１７６】
このように第２の実施形態においては、ノード探索処理を実行するノード（第１のノードと称する）が参加しているサブオーバーレイネットワークの中にルーティング先のノード（第２のノードと称する）も参加しているのであれば、第１のノードは、その他のサブオーバーレイネットワークを経由することなくルーティングすることが可能である。また、第１のノードが参加しているサブオーバーレイネットワークの中に第２のノードが参加していない場合であっても、第２のノードが、第１及び第２のノードに共通する任意の上位レベルのサブオーバーレイネットワークに包含されている別のサブオーバーレイネットワークに参加しているのであれば、それよりさらに上位レベルのサブオーバーレイネットワークで包含される別のサブオーバーレイネットワークを経由することなくルーティング可能である。さらに、この第２の実施形態におけるルーティングは、第２の実施形態と比較して、より少ないホップ数で実現される。
【０１７７】
［第３の実施形態］
次に本発明の第３の実施形態について説明する。
【０１７８】
従来から、オーバーレイネットワークの各ノードに、オブジェクトを配置し、全体で多数のオブジェクトを格納・管理する技術が提案されている。しかし、従来の技術では、近接性と非均質性の課題が考慮されていない。第３の実施形態の特徴は、第１の実施形態で適用されたオーバーレイネットワークの構成手法を利用して、ノードに格納されるオブジェクトに付与するオブジェクトＩＤを格納先のノードのＩＤとすることで、近接性と非均質性の課題を解決するようにしたことにある。
【０１７９】
図２１は第３の実施形態で適用されるノード２００-tの主として機能構成を示す。図２１において、図４と同様の要素には同一符号を付してある。第３の実施形態では、複数のノード２００-tが連携して第１の実施形態で適用されたようなオーバーレイネットワークを構成すると共に、クライアント（クライアント端末）４０からの例えばオブジェクトの格納／取り出しを指示する命令を処理する。オブジェクトとは、コンピュータに記憶させるデータのひとかたまりを指す。
【０１８０】
クライアント４０は、ノード２００-tと例えば通信回線によって接続されている。クライアント４０からの命令は、例えばオブジェクトの格納／取り出しを指示する命令を含む。即ちクライアント４０は、オブジェクトの格納／取り出しをノード２００-tに指示する。クライアント４０は、オブジェクトの格納の場合、後述するオブジェクトＩＤ及びデータを含むオブジェクトをノード２００-tの後述する命令受け付け部３１に渡し、当該命令受け付け部３１からオブジェクトの格納成功／失敗の結果を得る。クライアント４０はまた、オブジェクトの取り出しの場合、オブジェクトＩＤ及び後述するオブジェクトサブＩＤをノード２００-tの命令受け付け部３１に渡し、当該ノード２００-tがオブジェクトの取り出しに成功した場合には当該ノード２００-tの命令受け付け部３１からオブジェクトを得る。クライアント４０はまた、ノード２００-tがオブジェクトの取り出しに失敗した場合には、当該ノード２００-tの命令受け付け部３１から失敗した旨の通知を得る。
【０１８１】
ノード２００-tは、第１の実施形態におけるノード２０-tと同様のハードウェア構成を有するコンピュータである。ノード２００-tは、ノード２０-tと同様に、通信機構２４と制御部２６とを含む。但し制御部２６の構成は、第１の実施形態と一部相違する。制御部２６は、構成情報記憶部２７、テーブル管理部２８及びルーティング部２９に加えてオブジェクトアクセス部３０を含む。構成情報記憶部２７は、第１の実施形態と同様に図５に示すデータ構造の構成情報５０-tを格納する。ノード２００-tはさらに、命令受け付け部３１とオブジェクト格納部３２とを含む。
【０１８２】
命令受け付け部３１は、クライアント４０からの命令を受け付ける。命令受け付け部３１は、受け付けた命令を制御部２６に渡す。命令受け付け部３１はまた、制御部２６に渡した命令（要求）に対する応答を当該制御部２６から受け取ってクライアント４０に返す。
【０１８３】
制御部２６は、第１の実施形態での処理に加えて、命令受け付け部３１から渡される命令を処理する。制御部２６のルーティング部２９は、これらの処理に共通のノード探索処理を、ノード２００-tが管理する構成情報５０-tを利用して行う。例えば、オブジェクトの格納／取り出しを指示する命令を渡された場合、ルーティング部２９は、オブジェクトが格納されるべき／格納されているノードを探索する。即ちルーティング部２９は、オブジェクトが格納されるべき／格納されているノードを、図２１において矢印Ｂ１で示されるように、幾つかのノード２０-tを経由して探索する。制御部２６（ルーティング部２９）は、探索されたノードにオブジェクトの格納／取り出しを要求し、図２１において矢印Ｂ２で示されるように、探索されたノードから応答を受ける。
【０１８４】
オブジェクト格納部３２は、オブジェクトを格納する記憶部である。オブジェクト格納部３２は、図３に示すノード２０-t内の補助記憶装置２３に相当する補助記憶装置の記憶領域を用いて実現される。制御部２６のオブジェクトアクセス部３０は、このオブジェクト格納部３２にオブジェクトを格納する処理及びオブジェクト格納部３２からオブジェクトを取り出す処理を行う。
【０１８５】
＜オブジェクトの構成＞
図２２は、オブジェクト格納部３２に格納されるオブジェクトのデータ構造例を示す。オブジェクトは、ＩＤ ｉｄビット数Ｍ、ＩＤ ｓｕｂｉｄビット数Ｋ、ＩＤ ｉｄ、ＩＤ ｓｕｂｉｄ、マスクビット数ｍａｓｋ及びデータｄａｔａから構成される。
【０１８６】
ＩＤ ｉｄビット数Ｍは、後述するオブジェクトＩＤ ｉｄのビット数を示す。Ｍの値は全オブジェクトで共通である。図２２の例ではＭ＝３である。
【０１８７】
ＩＤ ｓｕｂｉｄビット数Ｋは、後述するオブジェクトサブＩＤ ｓｕｂｉｄのビット数を示す。Ｋの値は全オブジェクトで共通である。図２２の例ではＫ＝５である。
【０１８８】
本実施形態において、全てのオブジェクトは固有のＩＤを持つ。このＩＤは、Ｍビットの長さのオブジェクトＩＤ ｉｄと、Ｋビットの長さのオブジェクトサブＩＤ ｓｕｂｉｄとから構成される。オブジェクトＩＤ ｉｄはオブジェクトの格納先のノード（格納先ノード）を決定するのに用いられ、オブジェクトサブＩＤ ｓｕｂｉｄは格納先ノードでオブジェクトを識別するのに用いられる。
【０１８９】
オブジェクトＩＤ ｉｄは、サブオーバーレイネットワークＩＤ部 ｎｗｉｄと、ノードＩＤ部 ｎｉｄとからなる。サブオーバーレイネットワークＩＤ部 ｎｗｉｄはオブジェクトを格納するノードが参加しているサブオーバーレイネットワークを指定するためのＩＤであり、ノードＩＤ部 ｎｉｄはオブジェクトを格納するノードを指定するためのＩＤである。本実施形態では、ＭビットのＩＤ ｉｄの上位側ｘビットによりサブオーバーレイネットワークＩＤ部 ｎｗｉｄが表され、下位側“Ｍ−ｘ”ビットによりノードＩＤ部 ｎｉｄが表される。このｘは次に述べるマスクビット数ｍａｓｋによって示される。つまり、サブオーバーレイネットワークＩＤ部 ｎｗｉｄはＩＤ ｉｄの上位側“ｍａｓｋ”ビットであり、ノードＩＤ部 ｎｉｄはＩＤ ｉｄの下位側“Ｍ−ｍａｓｋ”ビットである。
【０１９０】
マスクビット数ｍａｓｋは、オブジェクトＩＤ ｉｄからノードＩＤ部 ｎｉｄ及びサブオーバーレイネットワークＩＤ部 ｎｗｉｄを切り出すためのマスクビット数を示す。
【０１９１】
＜オブジェクトの格納先ノードの決定＞
次に、第３の実施形態で適用されるオブジェクトの格納先ノードの決定手法について説明する。本実施形態においてオブジェクトは、オブジェクトＩＤ ｉｄのサブオーバーレイネットワークＩＤ部 ｎｗｉｄで指定されるサブオーバーレイネットワークに所属している全てのノードの中から、当該オブジェクトＩＤ ｉｄのノードＩＤ部 ｎｉｄに最も近いノードＩＤを持つノードに格納される。ここで、「ノードＩＤ部 ｎｉｄに最も近いノードＩＤを持つノード」とは、オブジェクトＩＤ ｉｄのサブオーバーレイネットワークＩＤ部 ｎｗｉｄで指定されるサブオーバーレイネットワークに所属している全てのノードのノードＩＤを昇順に整列してリング状に並べたときに、当該オブジェクトＩＤ ｉｄのノードＩＤ部 ｎｉｄに対して、例えば反時計回りで最も近接しているノードＩＤを持つノードをいう。なお、「反時計回りで最も近接しているノードＩＤ」は、ノードＩＤ部 ｎｉｄと一致するノードＩＤを持つノードを含むものとする。
【０１９２】
例えば、後述する図２７に示すオーバーレイネットワークの環境では、オブジェクトＩＤがそれぞれ“１１０”“１０１”“００１”のオブジェクトは次に示すノード
オブジェクトＩＤ＝１１０のオブジェクト…ＩＤ＝１１０のノード
オブジェクトＩＤ＝１０１のオブジェクト…ＩＤ＝１００のノード
オブジェクトＩＤ＝００１のオブジェクト…ＩＤ＝００１のノード
に格納される。
【０１９３】
このようにしてオブジェクトの格納先ノードを決定することにより、非均質性の課題を解決するための仕組みを提供することができる。
【０１９４】
＜オブジェクトの格納＞
次に、第３の実施形態で適用されるオブジェクトの格納手法について説明する。オブジェクトを格納する処理（オブジェクト格納処理）は、第１及び第２のステップに大別される。
【０１９５】
第１のステップでは、オブジェクトＩＤから、オブジェクトを格納するノード（格納先ノード）の探索（つまりオブジェクトのルーティング）が行われる。  
第２のステップでは、探索された格納先ノードにオブジェクトの格納が要求（依頼）される。
【０１９６】
本実施形態では、第１のステップにおける格納先ノードの探索に、第１の実施形態で適用されたノードの探索（ルーティング）手法を用いることで、近接性を考慮したルーティングを可能にしている。
【０１９７】
以下、オブジェクト格納処理の詳細について図２３乃至図２６のフローチャートを参照して説明する。今、ノード２００-tの命令受け付け部３１が、クライアント４０からオブジェクトＯｂｊを格納する命令（オブジェクト格納命令）を受け付けて、当該オブジェクト格納命令を制御部２６に渡したものとする。この、クライアント４０からオブジェクト格納命令が与えられたノード２００-tをノードｓｔａｒｔ（ノード２００-t(S)）と表現する。また、ノードｓｔａｒｔが管理する構成情報５０-tを構成情報５０-t(S)と表現し、当該構成情報５０-t(S)に含まれている隣接テーブル５２-tを隣接テーブル５２-t(S)と表現する。
【０１９８】
ノードｓｔａｒｔ（の制御部２６に含まれているルーティング部２９）は、クライアント４０からのオブジェクト格納命令を受け取ると、当該命令で指定されたオブジェクトＯｂｊの格納先ノードＯｂｊＮｏｄｅを探索するためのノード探索処理（オブジェクトのルーティング）を行う（ステップＳ１１１）。ノードｓｔａｒｔは、このノード探索処理を、オブジェクトＯｂｊのオブジェクトＩＤ Ｏｂｊ．ｉｄ及びマスクビット数Ｏｂｊ．ｍａｓｋ（つまりＯｂｊ．｛ｉｄ，ｍａｓｋ｝）を入力として、図２４のフローチャートに示す手順で次のように実行する。
【０１９９】
まずノードｓｔａｒｔは、オブジェクトＯｂｊのオブジェクトＩＤ Ｏｂｊ．ｉｄから、マスクビット数Ｏｂｊ．ｍａｓｋに基づいてサブオーバーレイネットワークＩＤ部 Ｏｂｊ．ｎｗｉｄを切り出す（ステップＳ１２１）。このステップＳ１２１において、ノードｓｔａｒｔは、サブオーバーレイネットワークＩＤ部 Ｏｂｊ．ｎｗｉｄと当該ノードｓｔａｒｔ自身のＩＤであるｓｔａｒｔ．ｉｄに含まれているサブオーバーレイネットワークＩＤ ｓｔａｒｔ．ｎｗｉｄとを、最上位ビットから順に比較する（ステップＳ１２１）。このステップＳ１２１においてノードｓｔａｒｔは、上記の比較により、Ｏｂｊ．ｎｗｉｄとｓｔａｒｔ．ｎｗｉｄとが最上位ビットから連続して一致する最大ビット数ｋをカウントする。この最大ビット数ｋで表されるレベルのサブオーバーレイネットワーク（つまり、第ｋレベルのサブオーバーレイネットワーク）は、ノードｓｔａｒｔ及びノードＯｂｊＮｏｄｅが共に所属しているサブオーバーレイネットワークのうち最も深いレベルのサブオーバーレイネットワークである。
【０２００】
そこでノードｓｔａｒｔは、当該ノードｓｔａｒｔの構成情報記憶部２７に格納された隣接テーブル５２-t(S)のエントリｓｔａｒｔ．ｔａｂｌｅ［ｋ］に保持されている第ｋレベルのサブオーバーレイネットワーク上の隣接ノードの情報を選択する（ステップＳ１２２）。つまりノードｓｔａｒｔは、当該ノードｓｔａｒｔが管理する構成情報５０-t(S)の中から、当該ノードｓｔａｒｔ及び格納先ノードＯｂｊＮｏｄｅが共に所属しているサブオーバーレイネットワークのうち最も深いレベルのサブオーバーレイネットワークに対応する隣接テーブル５２-t(S)の情報を、最短距離でのルーティングを可能にする隣接テーブルの情報（隣接ノードの情報）として選択する。
【０２０１】
次にノードｓｔａｒｔは、Ｏｂｊ．ｎｗｉｄとｓｔａｒｔ．ｎｗｉｄとが一致するかを判定する。つまりカウントされたｋビットがマスクビット数ｍａｓｋに一致するかを判定する（ステップＳ１２３）。ステップＳ１２３の判定がＹｅｓの場合、ノードｓｔａｒｔは、ｒｉｎｇ［ｓｔａｒｔ．ｉｄ，Ｏｂｊ．ｉｄ，ｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ｉｄ）が正であるかを判定する（ステップＳ１２４）。ｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ｉｄは、選択された第ｋレベルのサブオーバーレイネットワーク上の隣接ノードの情報に含まれているｉｄである。
【０２０２】
ステップＳ１２４の判定がＹｅｓの場合、ノードｓｔａｒｔは、格納先ノードＯｂｊＮｏｄｅが、当該ノードｓｔａｒｔ自身であると決定する（ステップＳ１２５）。これによりノードｓｔａｒｔは、オブジェクトＯｂｊの格納先ノードＯｂｊＮｏｄｅの探索処理（ルーティング）に成功したとして当該処理を完了する（ステップＳ１２６）。
【０２０３】
一方、ステップＳ１２３の判定がＮｏの場合、即ちＯｂｊ．ｎｗｉｄとｓｔａｒｔ．ｎｗｉｄとが一致しない場合、ノードｓｔａｒｔは当該ノードｓｔａｒｔが参加しているサブオーバーレイネットワークよりも深いレベルのサブオーバーレイネットワークで格納先ノードＯｂｊＮｏｄｅを探索する必要があると判定する。そこでノードｓｔａｒｔは、ｒｉｎｇ［ｓｔａｒｔ．ｉｄk，Ｏｂｊ．ｉｄk，ｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ｉｄk）が正であるかを判定する（ステップＳ１２７）。但し、ｓｔａｒｔ．ｉｄk，Ｏｂｊ．ｉｄk，ｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ｉｄkは、それぞれ、ｓｔａｒｔ．ｉｄ，Ｏｂｊ．ｉｄ，ｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ｉｄの上位ｋビットを示す。
【０２０４】
ステップＳ１２７の判定がＹｅｓとなるためには、ｓｔａｒｔ．ｉｄkがＯｂｊ．ｉｄkに一致する必要がある。この場合、ステップＳ１２３の判定結果と矛盾する。そこで、ステップＳ１２７の判定がＹｅｓの場合、ノードｓｔａｒｔは、格納先ノードＯｂｊＮｏｄｅは存在せず、したがってノード探索処理に失敗したとして当該処理を完了する（ステップＳ１２８）。
【０２０５】
これに対し、ステップＳ１２７の判定がＮｏの場合、ノードｓｔａｒｔはステップＳ１２９に進む。ノードｓｔａｒｔはまた、ステップＳ１２４の判定がＮｏの場合にもステップＳ１２９に進む。ステップＳ１２９においてノードｓｔａｒｔは、第ｋレベルのサブオーバーレイネットワーク上における当該ノードｓｔａｒｔの隣接ノード２００-tをルーティング要求先のノードｎ（ノード２００-t(n)）として、当該ノードｎに、格納先ノードＯｂｊＮｏｄｅを探索するためのための探索要求（ルーティング要求）を転送する。このノードｎのＩＤ ｉｄはｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ｉｄであり、アドレス（ＩＰアドレス）はｓｔａｒｔ．ｔａｂｌｅ［ｋ］．ａｄｄｒである。ルーティング要求は、格納先ノードＯｂｊＮｏｄｅのＩＤ ｉｄ（Ｏｂｊ．ｉｄ）及びマスクビット数ｍａｓｋ（Ｏｂｊ．ｍａｓｋ）、つまりＯｂｊ．｛ｉｄ，ｍａｓｋ｝と、ノードｓｔａｒｔのアドレス（ＩＰアドレス）ａｄｄｒ（ｓｔａｒｔ．ａｄｄｒ）を含む。
【０２０６】
ノードｎ（の制御部２６に含まれているルーティング部２９）は、上記探索要求（ここでは、ノードｓｔａｒｔからの探索要求）を受け取ると、オブジェクトＯｂｊの格納先ノードＯｂｊＮｏｄｅを探索するためのノード探索処理を図２５のフローチャートに示す手順で次のように実行する。
【０２０７】
まずノードｎは、先のノードｓｔａｒｔにおけるステップＳ１２１と同様のステップＳ１３１を実行する。即ちノードｎは、格納先ノード（ルーティング先のノード）ＯｂｊＮｏｄｅのオブジェクトＩＤ Ｏｂｊ．ｉｄに含まれているサブオーバーレイネットワークＩＤ部 Ｏｂｊ．ｎｗｉｄと当該ノードｎ自身のＩＤであるｎ．ｉｄに含まれているサブオーバーレイネットワークＩＤ ｎ．ｎｗｉｄとを、最上位ビットから順に比較する。そしてノードｎは、Ｏｂｊ．ｎｗｉｄとｎ．ｎｗｉｄとが最上位ビットから連続して一致する最大ビット数ｋをカウントする。ノードｎが管理する構成情報５０-tを構成情報５０-t(n)と表現し、当該構成情報５０-t(n)に含まれている隣接テーブル５２-tを隣接テーブル５２-t(n)と表現する。
【０２０８】
ノードｎはステップＳ１３１を実行すると、当該ノードｎの構成情報記憶部２７に格納された隣接テーブル５２-t(n)のエントリｓｔａｒｔ．ｔａｂｌｅ［ｋ］に保持されている第ｋレベルのサブオーバーレイネットワーク上の隣接ノードの情報を選択する（ステップＳ１３２）。つまりノードｎは、当該ノードｎが管理する構成情報５０-t(n)の中から、当該ノードｓｔａｒｔ及び格納先ノードＯｂｊＮｏｄｅが共に所属しているサブオーバーレイネットワークのうち最も深いレベルのサブオーバーレイネットワークに対応する隣接テーブル５２-t(n)の情報を、最短距離でのルーティングを可能にする隣接テーブルの情報（隣接ノードの情報）として選択する。
【０２０９】
次にノードｎは、Ｏｂｊ．ｎｗｉｄとｎ．ｎｗｉｄとが一致するかを判定する。つまりノードｎは、カウントされたｋビットがマスクビット数ｍａｓｋに一致するかを判定する（ステップＳ１３３）。ステップＳ１３３の判定がＹｅｓの場合、ノードｎは、ｒｉｎｇ［ｎ．ｉｄ，Ｏｂｊ．ｉｄ，ｎ．ｔａｂｌｅ［ｋ］．ｉｄ）が正であるかを判定する（ステップＳ１３４）。ｎ．ｔａｂｌｅ［ｋ］．ｉｄは、選択された第ｋレベルのサブオーバーレイネットワーク上の隣接ノードの情報に含まれているｉｄである。
【０２１０】
ステップＳ１３４の判定がＹｅｓの場合、ノードｎは、格納先ノードＯｂｊＮｏｄｅが、当該ノードｎ自身であると決定する（ステップＳ１３５）。するとノードｎは、オブジェクトＯｂｊの格納先ノードＯｂｊＮｏｄｅの探索処理（ルーティング）に成功したとして、自身のＩＰアドレス（ｎ．ａｄｄｒ）をノードＯｂｊＮｏｄｅのＩＰアドレスａｄｄｒ（Ｏｂｊ．ａｄｄｒ）として含む応答を、探索要求に含まれているＩＰアドレスｓｔａｒｔ．ａｄｄｒで指定されるノードｓｔａｒｔに返す（ステップＳ１３６）。
【０２１１】
一方、ステップＳ１３３の判定がＮｏの場合、即ちＯｂｊ．ｎｗｉｄとｎ．ｎｗｉｄとが一致しない場合、ノードｓｔａｒｔは、ｒｉｎｇ［ｎ．ｉｄk，Ｏｂｊ．ｉｄk，ｎ．ｔａｂｌｅ［ｋ］．ｉｄk）が正であるかを判定する（ステップＳ１３７）。ステップＳ１３７の判定がＹｅｓの場合、ノードｎは、格納先ノードＯｂｊＮｏｄｅは存在せず、したがってノード探索処理に失敗したと判定する。この場合、ノードｎは、ノード探索失敗を通知するための応答を、ルーティング要求に含まれているＩＰアドレスｓｔａｒｔ．ａｄｄｒで指定されるノードｓｔａｒｔに返す（ステップＳ１３８）。
【０２１２】
これに対し、ステップＳ１３７の判定がＮｏの場合、ノードｎはステップＳ１３９に進む。ノードｎはまた、ステップＳ１３４の判定がＮｏの場合にもステップＳ１３９に進む。ステップＳ１３９においてノードｎは、第ｋレベルのサブオーバーレイネットワーク上における当該ノードｎ（旧ノードｎ）の隣接ノード２００-tをルーティング要求先の新たなノードｎ（ノード２００-t(n)）として、当該新たなノードｎ（新ノードｎ）に、格納先ノードＯｂｊＮｏｄｅを探索するためのための探索要求（ルーティング要求）を転送する。この新ノードｎのＩＤ ｉｄはｎ．ｔａｂｌｅ［ｋ］．ｉｄであり、アドレス（ＩＰアドレス）はｎ．ｔａｂｌｅ［ｋ］．ａｄｄｒである。ルーティング要求は、Ｏｂｊ．｛ｉｄ，ｍａｓｋ｝と、ノードｓｔａｒｔのアドレス（ＩＰアドレス）ａｄｄｒ（ｓｔａｒｔ．ａｄｄｒ）を含む。旧ノードｎから新ノードｎに探索要求が転送された場合、新ノードｎでは、旧ノードｎと同様に図２５のフローチャートに従うノード探索処理が行われる。
【０２１３】
さて、ノードｓｔａｒｔは、ノードｎがステップＳ１３６またはＳ１３８を実行したことにより当該ノードｎから返される応答を確認すると（ステップＳ１３０）、オブジェクトＯｂｊの格納先ノードＯｂｊＮｏｄｅの探索処理（ルーティング）に成功または失敗したとして当該処理を完了する（ステップＳ１２６）。
【０２１４】
ノードｓｔａｒｔ（のルーティング部２９）は、格納先ノードＯｂｊＮｏｄｅを探索するための、図２４のフローチャートで示されるノード探索処理（オブジェクトのルーティング）を完了すると、即ち図２３のフローチャートにおけるステップＳ１１１のノード探索処理を完了すると、当該ノード探索処理に成功したか否かを判定する（ステップＳ１１２）。もし、ノード探索処理に失敗したならば、ノードｓｔａｒｔは、オブジェクトＯｂｊの格納先ノードＯｂｊＮｏｄｅが存在しないとして、オブジェクト格納処理を終了する。
【０２１５】
これに対し、ノード探索処理に成功したならば、即ちオブジェクトＯｂｊのルーティングに成功したならば、ノードｓｔａｒｔの制御部２６に含まれているオブジェクトアクセス部３０はオブジェクト格納処理手段として機能して、当該オブジェクトＯｂｊが格納されるべきノード（格納先ノード）ＯｂｊＮｏｄｅに対して、当該オブジェクトＯｂｊの格納を要求する（ステップＳ１１３）。ノードＯｂｊＮｏｄｅ（の制御部２６に含まれているオブジェクトアクセス部３０）は、ノードｓｔａｒｔからオブジェクトＯｂｊの格納が要求されると、オブジェクト格納処理を図２６のフローチャートに示す手順で次のように実行する。
【０２１６】
まずノードＯｂｊＮｏｄｅ（のオブジェクトアクセス部３０）は、当該ノードＯｂｊＮｏｄｅが既に格納しているオブジェクトにまだ割り当てられていないユニークなオブジェクトサブＩＤを生成する（ステップＳ１４１）。このステップＳ１４１においてノードＯｂｊＮｏｄｅは、ノードｓｔａｒｔから要求されたオブジェクトＯｂｊに対して、生成されたＩＤを当該オブジェクトＯｂｊのオブジェクトサブＩＤ Ｏｂｊ．ｓｕｂｉｄとして付与する。
【０２１７】
次にノードＯｂｊＮｏｄｅは、Ｏｂｊ．ｓｕｂｉｄが付与されたオブジェクトＯｂｊを、図２２のフォーマットで当該ノードＯｂｊＮｏｄｅのオブジェクト格納部３２に格納する（ステップＳ１４２）。そしてノードＯｂｊＮｏｄｅは、オブジェクトＯｂｊの格納を要求したノードｓｔａｒｔに格納完了の応答を返す（ステップＳ１４３）。この応答は、オブジェクトＯｂｊに付与されたオブジェクトサブＩＤ Ｏｂｊ．ｓｕｂｉｄを含む。つまりノードＯｂｊＮｏｄｅは、オブジェクトＯｂｊの格納を要求したノードｓｔａｒｔにオブジェクトサブＩＤ Ｏｂｊ．ｓｕｂｉｄを返す。
【０２１８】
本実施形態によれば、上述の一連の処理により、格納先のサブオーバーレイネットワークを限定し、かつ経由するサブオーバーレイネットワークの数を少なくしながら、オブジェクトのルーティング（オブジェクトを格納するノードへのルーティング）を行うことができる。
【０２１９】
＜オブジェクトの取り出し＞
次に、第３の実施形態で適用されるオブジェクトの取り出し手法について、クライアント４０からノードｓｔａｒｔ（ノード２００-t(S)）にオブジェクトＯｂｊの取り出しを指示する取り出し命令が与えらた場合を例に、簡単に説明する。
【０２２０】
まずノードｓｔａｒｔ（のルーティング部２９）は、上述したオブジェクトＯｂｊの格納の場合と同様に、オブジェクトＯｂｊのオブジェクトＩＤ Ｏｂｊ．ｉｄとマスクビット数Ｏｂｊ．ｍａｓｋとを入力として、当該ノードＯｂｊＮｏｄｅを探索するためのノード探索処理を行う。これにより、ノードＯｂｊＮｏｄｅのＩＰアドレス（ＯｂｊＮｏｄｅ．ａｄｄｒ）が求められる。
【０２２１】
ノードｓｔａｒｔは、ノードＯｂｊＮｏｄｅを探索すると、当該ノードＯｂｊＮｏｄｅに対して取り出し要求を発行する。この取り出し要求は、オブジェクトＩＤ Ｏｂｊ．ｉｄ及びマスクビット数Ｏｂｊ．ｍａｓｋ、並びにオブジェクトＯｂｊのオブジェクトサブＩＤ Ｏｂｊ．ｓｕｂｉｄを含む。ノードＯｂｊＮｏｄｅのオブジェクトアクセス部３０は、この取り出し要求に従ってオブジェクト取り出し手段として機能して、要求されたオブジェクトＯｂｊを当該ノードＯｂｊＮｏｄｅのオブジェクト格納部３２から取り出し、当該オブジェクトＯｂｊをノードｓｔａｒｔに返す。ノードｓｔａｒｔは、ノードＯｂｊＮｏｄｅから返されたオブジェクトＯｂｊをクライアント４０に返す。
【０２２２】
＜オブジェクトを格納しているノードの探索の具体例＞
次に、上述した図２４及び図２５のフローチャートの示す手順に従うノード探索（オブジェクトを格納しているノードの探索）の具体例について、図２７を参照して説明する。
【０２２３】
図２７は、オーバーレイネットワークシステムの一例を示す。図２７において、オーバーレイネットワーク１０（第０サブオーバーレイネットワーク１０）には、ＩＤ＝｛０００，００１，０１１，１００，１１０，１１１｝の６つのノード２００-0，２００-1，２００-3，２００-4，２００-6，２００-7が参加（所属）している。ノード２００-0，２００-1，２００-3，２００-4，２００-6，２００-7は、それぞれ、図２に示されるノード２０-0，２０-1，２０-3，２０-4，２０-6，２０-7に相当する。
【０２２４】
ノード２００-0，２００-1，２００-3はサブオーバーレイネットワーク１１-0に所属し、ノード２００-4，２００-6，２００-7はサブオーバーレイネットワーク１１-1に所属する。また、ノード２００-4，２００-6，２００-7のうちのノード２００-4はサブオーバーレイネットワーク１１０-0にも所属し、残りのノード２００-6，２００-7はサブオーバーレイネットワーク１１-1にも所属する。つまり、ノード２００-4はサブオーバーレイネットワーク１１０-0に参加しし、ノード２００-6，２００-7はサブオーバーレイネットワーク１１-1に参加している。
【０２２５】
ノード２００-0，２００-1，２００-3，２００-4，２００-6，２００-7が管理する構成情報５０-tは、図２に示されるノード２０-0，２０-1，２０-3，２０-4，２０-6，２０-7が管理する構成情報５０-tと同一であるものとする。そこで図２７には、ＩＤ＝１１１のノード２００-7が管理する構成情報５０-7（ｔ＝７）、ＩＤ＝０１１のノード２００-3が管理する構成情報５０-3（ｔ＝３）、及びＩＤ＝００１のノード２００-1が管理する構成情報５０-1（ｔ＝１）も示されている。
【０２２６】
ここでは、図２７に示すオーバーレイネットワークシステムにおいて、ＩＤ＝１１１（マスクビット数ｍａｓｋ＝２），アドレス１９２．１６８．０．１のノード“１１１”（ノード２００-7）が、オブジェクトＩＤ＝｛１１０，１０１，００１｝の各オブジェクトに対するルーティング行うものとする。ＩＤ（ＩＤ ｉｄ）＝１１１（ｍａｓｋ＝２）のノード“１１１”（ノード２００-7）のサブオーバーレイネットワークＩＤ（ＩＤ ｎｗｉｄ）は“１１”であることに留意する。
【０２２７】
まず、ＩＤ＝１１０のオブジェクト“１１０”に対するルーティングについて説明する。ＩＤ＝１１１のノード“１１１”（ノード２００-7）は、オブジェクト“１１０”のＩＤ＝１１０と当該ノード“１１１”自身のＩＤ ｎｗｉｄ＝１１とを最上位ビットから順次比較することにより、最上位ビットから連続して一致するビット数ｋ＝２をカウントする（ステップＳ１２１）。これによりノード“１１１”は、自身が管理する隣接テーブル５２-7（ｔ＝７）から、第２レベルのサブオーバーレイネットワーク１１０-1に対応する２番目のエントリ（ｔａｂｌｅ［２］）の情報、つまり第２レベルのサブオーバーレイネットワーク１１０-1上で当該ノード“１１１”に隣接するノード“１１０”の情報（ｔａｂｌｅ［２］．ｉｄ＝１１０，ｔａｂｌｅ［２］．ａｄｄｒ＝１９２．１６８．１００．３）を選択する（ステップＳ１２２）。
【０２２８】
ここで、オブジェクト“１１０”のｎｗｉｄ（サブオーバーレイネットワークＩＤ部）は“１１”であり、ノード“１１１”のｎｗｉｄ（サブオーバーレイネットワークＩＤ）“１１”に一致する（ステップＳ１２３）。また、ｒｉｎｇ［ノード“１１１”のｉｄ，オブジェクト“１１０”のｉｄ，ノード“１１１”に隣接するノード“１１０”のｉｄ）、即ちｒｉｎｇ［１１１，１１０，“１１０”）は正とならない（ステップＳ１２４）。
【０２２９】
この場合、ノード“１１１”は、当該ノード“１１１”に隣接するノード“１１０”（ｔａｂｌｅ［２］．ｉｄ＝１１０のノード）にオブジェクト“１１０”の格納先ノードの探索要求を転送する（ステップＳ１２９）
ノード“１１０”（ノード２００-6）は、ノード“１１１”からオブジェクト“１１０”の格納先ノードの探索要求を受け取ると、当該オブジェクト“１１０”のＩＤ＝１１０と当該ノード“１１０”自身のＩＤ ｎｗｉｄ＝１１とを最上位ビットから順次比較することにより、最上位ビットから連続して一致するビット数ｋ＝２をカウントする（ステップＳ１３１）。これによりノード“１１０”は、自身が管理する隣接テーブル５２-t（ｔ＝６）から、第２レベルのサブオーバーレイネットワーク１１０-1に対応する２番目のエントリ（ｔａｂｌｅ［２］）の情報を選択する（ステップＳ１３２）。つまりノード“１１０”は、第２レベルのサブオーバーレイネットワーク１１０-1上でノード“１１０”に隣接するノードの情報を選択する。図２７ではノード“１１０”が管理する隣接テーブル５２-t（ｔ＝６）は省略されている。しかし、図２７のオーバーレイネットワークの構成から、選択されたノードの情報が、第２レベルのサブオーバーレイネットワーク１１０-1上でノード“１１０”に隣接するノード“１１１”の情報（ｔａｂｌｅ［２］．ｉｄ＝１１１，ｔａｂｌｅ［２］．ａｄｄｒ＝１９２．１６８．０．１）であることは明らかである。第２レベルのサブオーバーレイネットワーク１１０-1に参加しているノード“１１１”，“１１０”の中で、オブジェクト“１１０”のノードＩＤ部＝０に最も近いノードＩＤはノード“１１０”のノードＩＤ（＝０）である。
【０２３０】
ここで、オブジェクト“１１０”のｎｗｉｄ（サブオーバーレイネットワークＩＤ部）は“１１”であり、ノード“１１０”のｎｗｉｄ（サブオーバーレイネットワークＩＤ）“１１”に一致する（ステップＳ１３３）。また、ｒｉｎｇ［ノード“１１０”のｉｄ，オブジェクト“１１０”のｉｄ，ノード“１１０”に隣接するノード“１１１”のｉｄ）、即ちｒｉｎｇ［１１０，１１０，“１１１”）は正となる（ステップＳ１３４）。
【０２３１】
この場合、ノード“１１０”は、格納先ノードＯｂｊＮｏｄｅが、当該ノード“１１０”自身であると決定する（ステップＳ１３５）。するとノード“１１０”は、オブジェクト“１１０”の格納先ノードとして、自身のＩＰアドレスを含む応答をノード“１１１”に返す（ステップＳ１３６）。
【０２３２】
このようにして、オブジェクト“１１０”は、第２レベルのサブオーバーレイネットワーク１１０-1に参加しているノード“１１１”，“１１０”の中で、当該オブジェクト“１１０”のノードＩＤ部 ｎｉｄ＝０に最も近いノードＩＤ（＝０）を持つ、ＩＤ＝１１０のノード“１１０”にルーティングされる。ここでは、第２レベルのサブオーバーレイネットワーク１１０-1を包含する、第１レベルのサブオーバーレイネットワーク１１-1及び第０レベルのサブオーバーレイネットワーク１０を経由することなくルーティングすることができる。
【０２３３】
次に、ＩＤ＝１０１のオブジェクト“１０１”に対するルーティングについて説明する。ノード“１１１”（ノード２００-7）は、オブジェクト“１０１”のＩＤ＝１０１と当該ノード“１１１”自身のＩＤ ｎｗｉｄ＝１１とを最上位ビットから順次比較することにより、最上位ビットから連続して一致するビット数ｋ＝１をカウントする（ステップＳ１２１）。これによりノード“１１１”は、自身が管理する隣接テーブル５２-7（ｔ＝７）から、第１レベルのサブオーバーレイネットワーク１１-1に対応する１番目のエントリ（ｔａｂｌｅ［１］）の情報、つまり第１レベルのサブオーバーレイネットワーク１１-1上でノード“１１１”に隣接するノード“１００”の情報（ｔａｂｌｅ［１］．ｉｄ＝１００，ｔａｂｌｅ［１］．ａｄｄｒ＝１９２．１６８．１．５）を選択する（ステップＳ１２２）。
【０２３４】
ここで、オブジェクト“１０１”のｎｗｉｄ（サブオーバーレイネットワークＩＤ部）は“１０”であり、ノード“１１１”のｎｗｉｄ（サブオーバーレイネットワークＩＤ）“１１”に一致しない（ステップＳ１２３）。また、ｒｉｎｇ［ノード“１１１”のｉｄk，オブジェクト“１０１”のｉｄk，ノード“１１１”に隣接するノード“１００”のｉｄk）、即ちｒｉｎｇ［１，１，１）は正とならない（ステップＳ１２４）。この場合、ノード“１１１”は、当該ノード“１１１”に隣接するノード“１００”（ｔａｂｌｅ［１］．ｉｄ＝１００のノード）にオブジェクト“１０１”の格納先ノードの探索要求を転送する（ステップＳ１２９）
ノード“１００”（ノード２００-4）は、ノード“１１１”からオブジェクト“１０１”の格納先ノードの探索要求を受け取ると、当該オブジェクト“１０１”のＩＤ＝１０1と当該ノード“１００”自身のＩＤ ｎｗｉｄ＝１０とを最上位ビットから順次比較することにより、最上位ビットから連続して一致するビット数ｋ＝２をカウントする（ステップＳ１３１）。これによりノード“１００”は、自身が管理する隣接テーブル５２-t（ｔ＝４）から、第２レベルのサブオーバーレイネットワーク１１０-0に対応する２番目のエントリ（ｔａｂｌｅ［２］）の情報を選択する（ステップＳ１３２）。つまりノード“１００”は、第２レベルのサブオーバーレイネットワーク１１０-0上で当該ノード“１００”に隣接するノードの情報を選択する。図２７ではノード“１００”が管理する隣接テーブル５２-t（ｔ＝４）は省略されている。しかし、図２７のオーバーレイネットワークの構成から明らかなように、第２レベルのサブオーバーレイネットワーク１１０-0上で当該ノード“１００”に隣接するのは当該ノード“１００”自身であることから、選択されたノードの情報は当該ノード“１００”の情報（ｔａｂｌｅ［２］．ｉｄ＝１００，ｔａｂｌｅ［２］．ａｄｄｒ＝１９２．１６８．１．５）である。このノード“１００”は、第２レベルのサブオーバーレイネットワーク１１０-0上でオブジェクト“１０１”のノードＩＤ部 ｎｉｄ＝１に最も近いノードＩＤを持つ。
【０２３５】
オブジェクト“１０１”のｎｗｉｄ（サブオーバーレイネットワークＩＤ部）は“１０”であり、ノード“１００”のｎｗｉｄ（サブオーバーレイネットワークＩＤ）“１０”に一致する（ステップＳ１３３）。また、ｒｉｎｇ［ノード“１００”のｉｄ，オブジェクト“１０１”のｉｄ，ノード“１００”に隣接する当該ノード“１００”自身のｉｄ）、即ちｒｉｎｇ［１００，１０１，１００）は、１０１がリング上で範囲［１００，１００）に収まるという条件を満たした並びであることから正となる（ステップＳ１３４）。
【０２３６】
この場合、ノード“１００”は、格納先ノードＯｂｊＮｏｄｅが、当該ノード“１００”自身であると決定する（ステップＳ１３５）。するとノード“１００”は、オブジェクト“１０１”の格納先ノードとして、自身のＩＰアドレスを含む応答をノード“１１１”に返す（ステップＳ１３６）。
【０２３７】
これにより、オブジェクト“１０１”は、第２レベルのサブオーバーレイネットワーク１１０-0に参加している唯一のノード“１００”に、当該オブジェクト“１０１”のノードＩＤ部 ｎｉｄ＝１に最も近いノードＩＤを持つノードとしてルーティングされる。ここでは、第１レベルのサブオーバーレイネットワーク１１-1及び第２レベルのサブオーバーレイネットワーク１１０-0を包含する、第０レベルのサブオーバーレイネットワーク１０を経由することなくルーティングすることができる。
【０２３８】
次に、ＩＤ＝００１のオブジェクト“００１”に対するルーティングについて説明する。ノード“１１１”（ノード２００-7）は、オブジェクト“００１”のＩＤ＝００１と当該ノード“１１１”自身のＩＤ ｎｗｉｄ＝１１とを最上位ビットから順次比較することにより、最上位ビットから連続して一致するビット数ｋをカウントする（ステップＳ１２１）。ここでは一致するビットはない。つまりｋ＝０がカウントされる。これによりノード“１１１”は、自身が管理する隣接テーブル５２-7（ｔ＝７）から、第０レベルのサブオーバーレイネットワーク１０に対応する０番目のエントリ（ｔａｂｌｅ［０］）の情報、つまり第０レベルのサブオーバーレイネットワーク１０上でノード“１１１”に隣接するノード“０００”の情報（ｔａｂｌｅ［０］．ｉｄ＝０００，ｔａｂｌｅ［０］．ａｄｄｒ＝１０．０．１．１）を選択する（ステップＳ１２２）。
【０２３９】
ここで、オブジェクト“００１”のｎｗｉｄ（サブオーバーレイネットワークＩＤ部）は“０”であり、ノード“１１１”のｎｗｉｄ（サブオーバーレイネットワークＩＤ）“１１”に一致しない（ステップＳ１２３）。また、ｒｉｎｇ［ノード“１１１”のｉｄk，オブジェクト“００１”のｉｄk，ノード“１１１”に隣接するノード“０００”のｉｄk）、はｋ＝０であることから正とならない（ステップＳ１２４）。この場合、ノード“１１１”は、当該ノード“１１１”に隣接するノード“０００”（ｔａｂｌｅ［０］．ｉｄ＝０００のノード）にオブジェクト“００１”の格納先ノードの探索要求を転送する（ステップＳ１２９）
ノード“０００”（ノード２００-0）は、ノード“１１１”からオブジェクト“００１”の格納先ノードの探索要求を受け取ると、当該オブジェクト“００１”のＩＤ＝００1と当該ノード“０００”自身のＩＤ ｎｗｉｄ＝０とを最上位ビットから順次比較することにより、最上位ビットから連続して一致するビット数ｋ＝１をカウントする（ステップＳ１３１）。これによりノード“０００”は、自身が管理する隣接テーブル５２-t（ｔ＝０）から、第１レベルのサブオーバーレイネットワーク１１-0に対応する１番目のエントリ（ｔａｂｌｅ［１］）の情報を選択する（ステップＳ１３２）。つまりノード０００”は、第１レベルのサブオーバーレイネットワーク１１-0上で当該ノード“０００”に隣接するノードの情報を選択する。図２７ではノード“０００”が管理する隣接テーブル５２-t（ｔ＝０）は省略されている。しかし、図２７のオーバーレイネットワークの構成から、選択されたノードの情報が、第１レベルのサブオーバーレイネットワーク１１-0上でノード“０００”に隣接するノード“００１”の情報（ｔａｂｌｅ［１］．ｉｄ＝００１，ｔａｂｌｅ［１］．ａｄｄｒ＝１９２．１６８．３．１）であることは明らかである。このノード“００１”は、第１レベルのサブオーバーレイネットワーク１１-0に参加しているノード“０００”，“００１”，“０１１”の中でオブジェクト“００１”のノードＩＤ部 ｎｉｄ＝０１に最も近いノードＩＤを持つ。
【０２４０】
オブジェクト“００１”のｎｗｉｄ（サブオーバーレイネットワークＩＤ部）は“０”であり、ノード“０００”のｎｗｉｄ（サブオーバーレイネットワークＩＤ）“０”に一致する（ステップＳ１３３）。また、ｒｉｎｇ［ノード“０００”のｉｄ，オブジェクト“００１”のｉｄ，ノード“０００”に隣接するノード“００１”のｉｄ）、即ちｒｉｎｇ［０００，００１，００１）は正とならない（ステップＳ１３４）。この場合、ノード“０００”は、当該ノード“０００”に隣接するノード“００１”（ｔａｂｌｅ［１］．ｉｄ＝００１のノード）にオブジェクト“００１”の格納先ノードの探索要求を転送する（ステップＳ１３９）
ノード“００１”（ノード２００-1）は、ノード“０００”からオブジェクト“００１”の格納先ノードの探索要求を受け取ると、当該オブジェクト“００１”のＩＤ＝００1と当該ノード“００１”自身のＩＤ ｎｗｉｄ＝０とを最上位ビットから順次比較することにより、最上位ビットから連続して一致するビット数ｋ＝１をカウントする（ステップＳ１３１）。これによりノード“００１”は、自身が管理する隣接テーブル５２-1（ｔ＝１）から、第１レベルのサブオーバーレイネットワーク１１-0に対応する１番目のエントリ（ｔａｂｌｅ［１］）の情報、つまり第１レベルのサブオーバーレイネットワーク１１-0上で当該ノード“００１”に隣接するノード“０１１”の情報（ｔａｂｌｅ［１］．ｉｄ＝０１１，ｔａｂｌｅ［１］．ａｄｄｒ＝１０．０．０．１）選択する（ステップＳ１３２）。
【０２４１】
ここで、オブジェクト“００１”のｎｗｉｄ（サブオーバーレイネットワークＩＤ部）は“０”であり、ノード“０１１”のｎｗｉｄ（サブオーバーレイネットワークＩＤ）“０”に一致する（ステップＳ１３３）。また、ｒｉｎｇ［ノード“００１”のｉｄ，オブジェクト“００１”のｉｄ，ノード“００１”に隣接するノード“０１１”のｉｄ）、即ちｒｉｎｇ［００１，００１，“０１１”）は正となる（ステップＳ１３４）。
【０２４２】
この場合、ノード“００１”は、格納先ノードＯｂｊＮｏｄｅが、当該ノード“００１”自身であると決定する（ステップＳ１３５）。するとノード“００１”は、オブジェクト“００１”の格納先ノードとして、自身のＩＰアドレスを含む応答をノード“１１１”に返す（ステップＳ１３６）。
【０２４３】
このようにして、オブジェクト“００１”は、第１レベルのサブオーバーレイネットワーク１１-0に参加しているノード“０００”，“００１”，“０１１”の中で、当該オブジェクト“００１”のノードＩＤ部 ｎｉｄ＝０１に最も近いノードＩＤを持つ、ＩＤ＝００１のノード“００１”にルーティングされる。ここでは、第１レベルのサブオーバーレイネットワーク１１-0を包含する第０レベルのサブオーバーレイネットワーク１０を経由することなくルーティングすることができる。
【０２４４】
以上の説明から明らかなように、第３の実施形態においては、オブジェクトのルーティングは必ず指定されたサブオーバーレイネットワークの中で完了する。つまりオブジェクトの格納先を限定することができる。また、参加しているサブオーバーレイネットワークの中にルーティング先のノードも参加しているのであれば、その他のサブオーバーレイネットワークを経由することなくルーティングすることが可能である。参加しているサブオーバーレイネットワークの中にルーティング先のノードが参加していない場合であっても、ルーティング先のノードが、共通する任意の上位レベルのサブオーバーレイネットワークに包含されている別のサブオーバーレイネットワークに参加しているのであれば、それよりさらに上位レベルのサブオーバーレイネットワークで包含される別のサブオーバーレイネットワークを経由することなくルーティング可能である。
【０２４５】
なお、本発明は、上記第１乃至第３の実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記第１乃至第３の実施形態に開示されている複数の構成要素の適宜な組み合わせにより種々の発明を形成できる。例えば、第３の実施形態においてオブジェクトの格納先ノードを探索するのに、第２の実施形態で適用されたようなスキップテーブル５２３-tを用いてもよい。この場合、オブジェクトの格納先ノードの探索を、第３の実施形態と比較して、より少ないホップ数で実現することができる。また、第１乃至第３の実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。
【図面の簡単な説明】
【０２４６】
【図１】本発明の第１の実施形態に係るオーバーレイネットワークシステムにおけるオーバーレイネットワークの階層構造を示す図。
【図２】図１のオーバーレイネットワーク１０に６つのノードが参加している状態を示す図。
【図３】図２に示されるノードのハードウェア構成を示すブロック図。
【図４】図２に示されるノードの主として機能構成を示すブロック図。
【図５】図４に示されるノードの構成情報記憶部に格納される構成情報のデータ構造例を示す図。
【図６】ｉｄと当該ｉｄを構成するｎｉｄ及びｎｗｉｄとの関係、並びにｉｄ，ｎｉｄ及びｎｗｉｄのビット数を示す図。
【図７】第１の実施形態において、新しく参加するノードの隣接テーブルを構築する手順を示すフローチャート。
【図８】第１の実施形態において、新しく参加するノード及び既存のノードの隣接テーブルを更新する手順を示すフローチャート。
【図９】第１の実施形態において、あるノードが任意のノードのルーティングを行う場合の手順を示すフローチャート。
【図１０】第１の実施形態において、ルーティング要求を受け取ったノードでのノード探索処理の手順を示すフローチャート。
【図１１】本発明の第２の実施形態で適用される構成情報のデータ構造例を示す図。
【図１２】図１１に示される構成情報に含まれているスキップテーブルのデータ構造例を示す図。
【図１３】図１２のスキップテーブルに保持されるｓｋｉｐ［ｊ］［ｉ］．ｉｎｔｅｒｖａｌ＿ｓとｓｋｉｐ［ｊ］［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄとの関係を示す図。
【図１４】第２の実施形態においてオーバーレイネットワークを再構成する場合に実行される、新しく参加するノードの隣接テーブル及びスキップテーブルを構築する手順を示すフローチャート。
【図１５Ａ】第２の実施形態において、既にオーバーレイネットワークに参加しているノードにおいて隣接テーブルを構築する手順を示すフローチャート。
【図１５Ｂ】第２の実施形態において、既にオーバーレイネットワークに参加しているノードにおいて隣接テーブルを構築する手順を示すフローチャート。
【図１６】第２の実施形態において、新しく参加するノードに先行して隣接するノードにおいて隣接テーブルを構築する手順を示すフローチャート。
【図１７】第２の実施形態において、既にオーバーレイネットワークに参加しているノードにおいてスキップテーブルを構築する手順の詳細を示すフローチャート。
【図１８】第２の実施形態において、あるノードが任意のノードのルーティングをスキップテーブルを用いて行う場合の手順を示すフローチャート。
【図１９】第２の実施形態において、ルーティング要求を受け取ったノードが要求されたノードのルーティングをスキップテーブルを用いて行う場合の手順を示すフローチャート。
【図２０】第２の実施形態におけるオーバーレイネットワークの階層構造の例を、当該オーバーレイネットワークに参加しているノードの１つが管理する構成情報のデータ構造例と共に示す図。
【図２１】本発明の第３の実施形態で適用されるノードの主として機能構成を示すブロック図。
【図２２】図２１に示されるオブジェクト格納部に格納されるオブジェクトのデータ構造例を示す図。
【図２３】第３の実施形態におけるオブジェクト格納処理の手順を示すフローチャート。
【図２４】第３の実施形態において、あるノードがオブジェクトを格納するノードを探索するためのノード探索処理の手順を示すフローチャート。
【図２５】第３の実施形態において、探索要求を受け取ったノードでのノード探索処理の手順を示すフローチャート。
【図２６】第３の実施形態において、探索されたノードでのオブジェクト格納処理の手順を示すフローチャート。
【図２７】第３の実施形態におけるオーバーレイネットワークの階層構造の例を、当該オーバーレイネットワークに参加しているノードのうちの３つが管理する構成情報のデータ構造例と共に示す図。
【図２８】背景技術を説明するために用いられる、３ビットのリングを示す図。
【図２９】図２８のリングに３つのノードが参加している状態を示す図。
【図３０】図２９に示される３つのノードがそれぞれ格納するオブジェクトの範囲を示す図。
【符号の説明】
【０２４７】
１０…オーバーレイネットワーク（第０レベルのサブオーバーレイネットワーク）、１１-0，１１-1…サブオーバーレイネットワーク（第１レベルのサブオーバーレイネットワーク）、１１０-0，１１０-1…サブオーバーレイネットワーク（第２レベルのサブオーバーレイネットワーク）、２０-t，２０-0，２０-1，２０-3，２０-4，２０-6，２０-7，２００-t，２００-0，２００-1，２００-3，２００-4，２００-6，２００-7…ノード、２６…制御部、２７…構成情報記憶部、２８…テーブル管理部、２９…ルーティング部、３０…オブジェクトアクセス部、３２…オブジェクト格納部、４０…クライアント、５０-t，５０-1，５０-3，５０-7，５００-t，５００-7…構成情報、５１-t，５１-1，５１-3，５１-7，５１０-t，５１０-7…ノード情報、５２-t…隣接テーブル、５２１-t，５２１-7…後続隣接テーブル、５２２-t，５２２-7…先行隣接テーブル、５２３-t，５２３-7…スキップテーブル。
【図１】
0004417997.tif 000002
【図２】
0004417997.tif 000003
【図３】
0004417997.tif 000004
【図４】
0004417997.tif 000005
【図５】
0004417997.tif 000006
【図６】
0004417997.tif 000007
【図７】
0004417997.tif 000008
【図８】
0004417997.tif 000009
【図９】
0004417997.tif 000010
【図１０】
0004417997.tif 000011
【図１１】
0004417997.tif 000012
【図１２】
0004417997.tif 000013
【図１３】
0004417997.tif 000014
【図１４】
0004417997.tif 000015
【図１５Ａ】
0004417997.tif 000016
【図１５Ｂ】
0004417997.tif 000017
【図１６】
0004417997.tif 000018
【図１７】
0004417997.tif 000019
【図１８】
0004417997.tif 000020
【図１９】
0004417997.tif 000021
【図２０】
0004417997.tif 000022
【図２１】
0004417997.tif 000023
【図２２】
0004417997.tif 000024
【図２３】
0004417997.tif 000025
【図２４】
0004417997.tif 000026
【図２５】
0004417997.tif 000027
【図２６】
0004417997.tif 000028
【図２７】
0004417997.tif 000029
【図２８】
0004417997.tif 000030
【図２９】
0004417997.tif 000031
【図３０】
0004417997.tif 000032