(57)【特許請求の範囲】
【請求項１】
複数のノードから構成されるオーバーレイネットワークであって、前記複数のノードの各々が、前記オーバーレイネットワーク上での識別子であるｍビットのノードＩＤとアンダーレイネットワーク上での識別子であるアドレスとを持つと共に、前記複数のノードのノードＩＤを当該ノードＩＤの大きさの順序でリング状に整列した際に自身に後続して隣接するノードのノードＩＤ及びアドレス並びに自身に先行して隣接するノードのノードＩＤ及びアドレスを保持する隣接テーブルと、目的のノードＩＤまたはオブジェクトＩＤを入力として、当該入力されたノードＩＤまたはオブジェクトＩＤに最も近いノードＩＤを持つノードのアドレスを逐次問い合わせにより取得するためのショートカットパスの情報として、前記複数のノードのうち、予め定められた規則に従って選択された自身以外のｍ個のノードのノードＩＤ及びアドレスを保持するスキップテーブルとを備えたオーバーレイネットワークを構築・維持するためのオーバーレイネットワーク構築・維持方法において、
前記オーバーレイネットワークに第１のノードが参加する場合に、前記第１のノードが、前記複数のノードのうちの任意のノードである第２のノードに対して、前記リング上で前記第１のノードに第１の方向で隣接するノードである第３のノードのノードＩＤ及びアドレスを取得するための第１の問い合わせを行うステップと、
前記第１の問い合わせに応じて前記第１のノードが前記第３のノードのノードＩＤ及びアドレスを取得した場合、前記第１のノードが前記第３のノードに対して、前記リング上で当該第３のノードに前記第１の方向とは逆の第２の方向で隣接するノードである第４のノードのノードＩＤ及びアドレスを取得するための第２の問い合わせを行うステップと、
前記第２の問い合わせに応じて前記第１のノードが前記第４のノードのノードＩＤ及びアドレスを取得した場合、前記第１のノードが、前記第３のノードのノードＩＤ及びアドレスと前記第４のノードのノードＩＤ及びアドレスとに基づいて、前記第１のノードの隣接テーブルを構築するステップと、
前記第１のノードが前記オーバーレイネットワークに参加する場合に、前記第１のノードが、前記第１のノードのスキップテーブルを初期化するステップと、
目的のノードＩＤまたはオブジェクトＩＤを入力として、当該入力されたノードＩＤまたはオブジェクトＩＤに最も近いノードＩＤを持つノードのアドレスを前記第１のノードが逐次問い合わせにより取得するための参照処理であって、前記第１のノードが前記問い合わせを前記第１のノードの前記スキップテーブルの示すショートカットパスに従って前記複数のノードのうちの自身以外のノードである第５のノードに転送する過程で、当該ショートカットパスを更新するステップを含む参照処理を実行するステップと
を具備することを特徴とするオーバーレイネットワーク構築・維持方法。
【請求項２】
前記第１のノードから前記第５のノードに転送される前記問い合わせには、当該問い合わせの転送に用いられた前記ショートカットパスの情報が付加され、
前記第１のノードから前記第５のノードに前記問い合わせが転送された場合、前記第５のノードが、前記問い合わせに付加されている前記ショートカットパスの情報と自身の前記隣接テーブル及び前記スキップテーブルの情報とを比較することにより、当該ショートカットパスの情報が正しいかを判定するステップを更に具備し、
前記参照処理を実行するステップは、前記第５のノードで前記ショートカットパスの情報が正しくないと判定された場合、前記第１のノードが自身の前記スキップテーブルの当該ショートカットパスの情報を更新するステップを含む
ことを特徴とする請求項１記載のオーバーレイネットワーク構築・維持方法。
【請求項３】
前記ショートカットパスの情報は、当該ショートカットパスを設定する際の基準となる前記リング上の位置を示す基準位置情報を含み、
前記判定するステップでは、前記ショートカットパスの情報に含まれている前記基準位置情報の示す位置に対して、前記第５のノードのノードＩＤの方が当該第５のノードの前記隣接テーブル及び前記スキップテーブルの示す全てのノードＩＤよりも前記リング上で近いかにより、前記ショートカットパスの情報が正しいかが判定される
ことを特徴とする請求項２記載のオーバーレイネットワーク構築・維持方法。
【請求項４】
前記第１のノードが自身のスキップテーブルを定期的に更新するための更新処理を実行するステップを更に具備することを特徴とする請求項１乃至３のいずれかに記載のオーバーレイネットワーク構築・維持方法。
【請求項５】
前記第１のノードの前記スキップテーブルの示すショートカットパスの情報を前回更新してから一定時間が経過した場合に、前記第１のノードが当該ショートカットパスの情報を更新するステップを更に具備することを特徴とする請求項１乃至３のいずれかに記載のオーバーレイネットワーク構築・維持方法。
【請求項６】
前記スキップテーブルは、前記ショートカットパスの情報に対応付けて、当該ショートカットパスの情報が最も最近に更新された際の時刻を表す更新時刻情報を保持し、
前記第１のノードは、前記更新時刻情報の示す時刻から前記一定時間が経過した場合に、当該更新時刻情報に対応する前記ショートカットパスの情報を更新する
ことを特徴とする請求項５記載のオーバーレイネットワーク構築・維持方法。
【請求項７】
複数のノードから構成されるオーバーレイネットワークであって、前記複数のノードの各々が、前記オーバーレイネットワーク上での識別子であるｍビットのノードＩＤとアンダーレイネットワーク上での識別子であるアドレスとを持つと共に、前記複数のノードのノードＩＤを当該ノードＩＤの大きさの順序でリング状に整列した際に自身に後続して隣接するノードのノードＩＤ及びアドレス並びに自身に先行して隣接するノードのノードＩＤ及びアドレスを保持する隣接テーブルと、目的のノードＩＤまたはオブジェクトＩＤを入力として、当該入力されたノードＩＤまたはオブジェクトＩＤに最も近いノードＩＤを持つノードのアドレスを逐次問い合わせにより取得するためのショートカットパスの情報として、前記複数のノードのうち、予め定められた規則に従って選択された自身以外のｍ個のノードのノードＩＤ及びアドレスを保持するスキップテーブルとを備えたオーバーレイネットワークに参加する第１のノードに、
前記第１のノードが前記オーバーレイネットワークに参加する場合に、前記第１のノードから前記複数のノードのうちの任意のノードである第２のノードに対して、前記リング上で前記第１のノードに第１の方向で隣接するノードである第３のノードのノードＩＤ及びアドレスを取得するための第１の問い合わせを行うステップと、
前記第１の問い合わせに応じて前記第１のノードが前記第３のノードのノードＩＤ及びアドレスを取得した場合、前記第１のノードから前記第３のノードに対して、前記リング上で当該第３のノードに前記第１の方向とは逆の第２の方向で隣接するノードである第４のノードのノードＩＤ及びアドレスを取得するための第２の問い合わせを行うステップと、
前記第２の問い合わせに応じて前記第１のノードが前記第４のノードのノードＩＤ及びアドレスを取得した場合、前記第３のノードのノードＩＤ及びアドレスと前記第４のノードのノードＩＤ及びアドレスとに基づいて、前記第１のノードの隣接テーブルを構築するステップと、
前記第１のノードが前記オーバーレイネットワークに参加する場合に、前記第１のノードのスキップテーブルを初期化するステップと、
目的のノードＩＤまたはオブジェクトＩＤを入力として、当該入力されたノードＩＤまたはオブジェクトＩＤに最も近いノードＩＤを持つノードのアドレスを前記第１のノードが逐次問い合わせにより取得するための参照処理であって、前記問い合わせを前記第１のノードの前記スキップテーブルの示すショートカットパスに従って前記複数のノードのうちの自身以外のノードである第５のノードに転送する過程で、当該ショートカットパスを更新するステップを含む参照処理を実行するステップと
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スキップテーブルを用いてオーバーレイネットワークを構築・維持するのに好適なオーバーレイネットワーク構築・維持方法及びプログラムに関する。
【背景技術】
【０００２】
近年、ピアツーピアシステム（Ｐ２Ｐシステム）のオーバーレイネットワークを構築及び維持する手法またはこれを利用したシステムの研究開発が盛んになりつつある。このＰ２Ｐシステムのオーバーレイネットワークを構築及び維持する手法には様々なものがあるが、その中でも特に、カルフォルニア大学バークレー校（ＵＣＢ）を中心としたＴａｐｅｓｔｒｙ（タペストリ）（非特許文献１及び２参照）、マイクロソフト社を中心としたＰａｓｔｒｙ（ペストリ）（非特許文献３及び４参照）、マサチューセッツ工科大学（ＭＩＴ）を中心としたＣｈｏｒｄ（コード）（非特許文献５及び６参照）などが注目されている。
【０００３】
これらの手法に共通するのは、ＩＤ（識別子）の近さをリングで管理するＣｏｎｓｉｓｔｅｎｔＨａｓｈｉｎｇ（コンシステントハッシング）を用いて、オーバーレイネットワークを構築するということである。
【０００４】
ＣｏｎｓｉｓｔｅｎｔＨａｓｈｉｎｇとは、
１）全てのノード（ネットワークに接続したコンピュータ）とオブジェクト（コンピュータに格納されるべき、ファイルのようなひとかたまりのデータ）について、それらが持つネットワーク上でのユニークな識別子（例えばノードならホスト名やＩＰ（Internet Protocol）アドレス、オブジェクトならその名前やデータ自体）をハッシュ関数に投入し、
２）そこから得られたノードの識別子のハッシュ値をノードＩＤ、オブジェクトの識別子のハッシュ値をオブジェクトＩＤとして、
３）オブジェクトを、オブジェクトＩＤに最も「近い」ノードＩＤを持つノードに格納する（近さの定義については後述する）
という技術である。各ノードはハッシュ空間の一部を担い、オーバーレイネットワークを構成するノード全体で１つのハッシュ空間を構成することから、この技術を一般的に、「分散ハッシュテーブル（ＤＨＴ）」と呼ぶ。
【０００５】
オブジェクトの格納のため、或いは格納されたオブジェクトを取り出すためには、オブジェクトＩＤに最も「近い」ノードＩＤを持つノードを探索する必要がある。以下、この、（ノードまたはオブジェクトの）ＩＤに最も近いノードＩＤを持つノードの、ノードＩＤ及び識別子を得る動作を、「参照」と呼ぶことにする。
【０００６】
以下、非特許文献５、６により示されるアルゴリズム“Ｃｈｏｒｄ”での、主としてオーバーレイネットワークの構築方法について説明する。  
Ｃｈｏｒｄでは、ノードのＩＰアドレスのハッシュ値をノードＩＤ、オブジェクトのデータ自体のハッシュ値をオブジェクトＩＤとして、取り得る全てのＩＤ（０からＮ＝２m−１まで２m個のＩＤ、ｍはハッシュ関数の出力ビット数（文献では１６０ビットのＳＨＡ１を使用））を収容できるリング（ｍビットのリング）の上に、それぞれのＩＤが当てはめられる。このリング上で、２つのＩＤが時計回りでどれだけ離れているかによって、当該２つのＩＤの近さが測られる。２m個のＩＤを収容できるリングは、ｍビットのリングと呼ばれる。
【０００７】
図１５はｍが３の場合のリング（いわゆるＣｈｏｒｄリング）、つまり３ビットのリングを示す。図１５において、リング上に配置された８つの丸印はＩＤを示し、当該丸印の近傍に記述された２進数０００〜１１１は、対応するＩＤそれ自体を示す。図１５におけるＩＤ ０００〜ＩＤ １１１の配置は、３ビットのリング上で取り得るＩＤの位置関係を示す。
【０００８】
図１５において、例えばＩＤ ０００に最も近いＩＤはＩＤ ０００自身で、次に近いＩＤはＩＤ ００１である（ＩＤ １１１ではないことに注意）。同様に、ＩＤ １１１に最も近いＩＤはＩＤ １１１自身で、次に近いＩＤはＩＤ ０００である（ＩＤ １１０ではないことに注意）。
【０００９】
図１５に示す３ビットのリング（に対応するオーバーレイネットワーク）に、以下のノードＩＤ
ノードＩＤ ０００／ＩＰアドレス １０．０．１．１
ノードＩＤ ００１／ＩＰアドレス １９２．１６８．３．１
ノードＩＤ ０１１／ＩＰアドレス １０．０．０．１
ノードＩＤ １００／ＩＰアドレス １９２．１６８．１．５
ノードＩＤ １１０／ＩＰアドレス １９２．１６８．１００．３
ノードＩＤ １１１／ＩＰアドレス １９２．１６８．０．１
を持つノードが参加したとする。この場合、リング（に対応するオーバーレイネットワーク）は、図１６に示されるようになる。図１６において、ＩＤ（ノードＩＤ）の近傍には、当該ＩＤを持つノードのＩＰアドレスが表記されている。
【００１０】
ここで、任意のＩＤについて、リング上において時計回りで最初に遭遇する（つまり自身を除いて最も近いノードＩＤを持つ）ノードをｓｕｃｃｅｓｓｏｒ（後続隣接ノード）、反時計回りに最初に遭遇する（つまり自身を除いて最も遠いノードＩＤを持つ）ノードをｐｒｅｄｅｃｅｓｓｏｒ（先行隣接ノード）と呼ぶ。
【００１１】
例えば、ノードＩＤ ０００のノードのｓｕｃｃｅｓｓｏｒはノードＩＤ ００１のノードであり、ｐｒｅｄｅｃｅｓｓｏｒはノードＩＤ １１１のノードである。また、ノードＩＤ １００のノードのｓｕｃｃｅｓｓｏｒはノードＩＤ １１０のノードであり、ｐｒｅｄｅｃｅｓｓｏｒはノードＩＤ ０１１のノードである。
【００１２】
Ｃｈｏｒｄでは、オーバーレイネットワークに参加したノードは自身のｓｕｃｃｅｓｓｏｒ及びｐｒｅｄｅｃｅｓｓｏｒとリンクを形成することで、図１６のようなリングを形成する。各ノードは、自身のｓｕｃｃｅｓｓｏｒ及びｐｒｅｄｅｃｅｓｓｏｒのノードＩＤ及びアドレス（ＩＰアドレス）を保持・管理する。これらのｓｕｃｃｅｓｓｏｒ及びｐｒｅｄｅｃｅｓｓｏｒのノードＩＤ及びアドレスは、隣接テーブルと呼ばれるテーブルを用いて保持・管理される。各ノードが自身のｓｕｃｃｅｓｓｏｒ及びｐｒｅｄｅｃｅｓｓｏｒのＩＤ及びアドレスを知り、それらとリンクを形成することで、図１６のようなリングを形成し、維持する方法については、非特許文献５または６を参照されたい。
【００１３】
Ｃｈｏｒｄでは、オブジェクトは、そのオブジェクトのオブジェクトＩＤに最も近いノードＩＤを持つノードに格納される。
【００１４】
図１７は、図１６の例において、それぞれのノードが格納するオブジェクトのオブジェクトＩＤの範囲を示す。図１７において、オブジェクトＩＤは、矩形の枠内に記述されている。例えば、オブジェクトＩＤ ０００のオブジェクトは、ノードＩＤ ０００のノードに格納され、オブジェクトＩＤ ０１０のオブジェクトは、ノードＩＤ ０１１のノードに格納される。
【００１５】
ここで、参照について説明する。  
参照とは、以下の入力及び出力
入力：（オブジェクトまたはノードの）ＩＤ
出力：入力されたＩＤに最も近いノードＩＤを持つノードのノードＩＤ及びアドレス
を行うための一連の動作を指す。
【００１６】
図１６に示したオーバーレイネットワーク（リング）において参照を実現する方法として、以下の２つ
＜第１の方法＞
オーバーレイネットワークに参加しているノードの各々が、当該ネットワークに参加している他の全てのノードのアドレスを知っておく方法（ブロードキャスト）
＜第２の方法＞
隣接テーブルを辿って探索要求を中継してゆく方法（フルフラッディング：ｆｕｌｌ−ｆｌｏｏｄｉｎｇ）
が知られている。
【００１７】
これらの２つの方法は、それぞれ次のような利点と欠点とを有する。  
＜第１の方法の利点と欠点＞
利点：目標に到達するまで時間がかからず、経路上での障害で全ての探索が中断することがない。  
欠点：オーバーレイネットワークに参加している全ノードの参加状況（参加／離脱／異常停止）を監視する必要がある。
【００１８】
＜第２の方法の利点と欠点＞
利点：各ノードはオーバーレイネットワークに参加している全ノードの参加状況（参加／離脱／異常停止）を監視する必要がない。  
欠点：目標に到達するまで時間がかかり、経路上での障害でフルフラッディングが機能しなくなるので信頼性が低い。  
いずれの方法も、オーバーレイネットワークの規模が大きくなると機能しなくなる可能性がある。
【００１９】
そこでＣｈｏｒｄでは、各ノードがｍ個のショートカットパスを準備しておくことで、高々ｍホップの探索要求転送で、参照が完了するアルゴリズムが適用される。このｍ個のショートカットパスの情報は、スキップテーブル（フィンガーテーブル）と呼ばれるテーブルを用いて保持・管理される。
【００２０】
スキップテーブルには、ｍを上記のようにリングのビット数とすると、ｍ個のショートカットパス（の情報）が記述（保持）される。ｍ個のショートカットパスの各々は、各ノードのＩＤ（ノードＩＤ）を“ｉｄ”、アドレス（ＩＰアドレス）を“ａｄｄｒ”で表すと、以下の生成規則に基づいて生成される。
【００２１】
即ち、ｍ個のショートカットパスの各々は、ｉ＝｛０...ｍ−１｝に関して、
ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstart
＝（ｉｄ＋２i）ｍｏｄ ２m
ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌend
＝ｓｋｉｐ［（ｉ＋１）ｍｏｄ ｍ］．ｉｎｔｅｒｖａｌstart
ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ
＝ＩＤ ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartに最も近いノードＩＤを持つノードのＩＤ
但し、ｓｋｉｐ［０］．ｓｕｃｃｅｓｓｏｒ．ｉｄは、自身のｓｕｃｃｅｓｓｏｒとなるノードのノードＩＤであることに注意
ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒ
＝ＩＤ ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartに最も近いノードＩＤを持つノードのアドレス（ＩＰアドレス）
但し、ｓｋｉｐ［０］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒは、自身のｓｕｃｃｅｓｓｏｒとなるノードのアドレスであることに注意
に基づいて生成される。
【００２２】
Ｃｈｏｒｄでは、上記スキップテーブルを用いた参照が次のよう実現される。  
処理１）
参照を開始するノードは、自身のスキップテーブルに保持されているショートカットパスの情報から、入力されたＩＤに対して最も遠いＩＤを持つノード（つまりｐｒｅｄｅｃｅｓｓｏｒとなるノード）へのショートカットパスの情報を選択し、当該選択された情報の示すノードへ次の問い合わせ先を問い合わせる。
【００２３】
処理２）
問い合わせを受けたノードは、自身のスキップテーブルに保持されているショートカットパスの情報から、入力されたＩＤに対して最も遠いＩＤを持つノードへのショートカットパスの情報を選択し、当該選択された情報の示すノードのアドレスを、参照を開始するノードに回答する。但し、入力されたＩＤに対して最も遠いＩＤを持つノードのノードＩＤよりも、自身のノードＩＤの方が遠い場合には、参照を開始するノードに、到達完了の旨と共に自身のアドレスを回答する。
【００２４】
処理３）
回答を受けたノード、つまり参照を開始するノードは、当該回答で示されるノード、つまり次の問い合わせ先に、問い合わせを行う。これにより処理２が再び実行される。但し、到達完了の旨が回答された場合には、次の処理４）が実行される。
【００２５】
処理４）
参照を開始したノードは、到達先のノードから、その到達先ノードのｓｕｃｃｅｓｓｏｒのノードＩＤ及びアドレスを取得する。取得されたノードＩＤ及びアドレスが参照の出力（結果）となる。
【００２６】
上記スキップテーブルは、参照の高速化のため（つまり隣接テーブルを利用した探索要求転送と比較してより少ないホップ数での参照を可能にするため）に用いられる。しかし、スキップテーブルで管理されるべきリンク数は隣接テーブルに比べて多く、且つ当該スキップテーブルで管理されるべきノードの参加／離脱は非同期に起きる。このため、スキップテーブルで管理されるべきノードを正確に指し示している状態に、当該スキップテーブルを維持することは難しい。Ｃｈｏｒｄではこの点について考慮されており、スキップテーブルが完全でない場合（つまり、最短距離でのルーティングとならない場合）でも、参照は成立する。この詳細は、非特許文献５、６に記載されている。
【００２７】
また、上記のスキップテーブルを構築・維持するため、Ｃｈｏｒｄでは以下のような２種類の方法が提示されている。
【００２８】
＜厳密モデルによる方法＞
ノードは、オーバーレイネットワークに参加する際に、自身のスキップテーブルを構築すると共に、自身が参加することでスキップテーブルの修正が必要となるノードに対して、更新を通知する。
【００２９】
＜非厳密モデルによる方法＞
ノードは、オーバーレイネットワークに参加した後、定期的に、自身のスキップテーブルに記述されているｍ個のショートカットパスのうちの１つを選択して、その選択されたショートカットパスに関してスキップテーブルを更新する。
【００３０】
以上、非特許文献５、６に記載されたＣｈｏｒｄを例に、スキップテーブルを用いた参照と、スキップテーブルの構成・維持とに関する従来技術について説明した。
【特許文献１】特開２００４−２６６７９６号公報
【非特許文献１】ｈｔｔｐ：／／ｐ２ｐ．ｃｓ．ｕｃｓｂ．ｅｄｕ／ｃｈｉｍｅｒａ／
【非特許文献２】Ｂｅｎ Ｙ．Ｚｈａｏ，Ｌｉｎｇ Ｈｕａｎｇ，Ｊｅｒｅｍｙ Ｓｔｒｉｂｌｉｎｇ，Ｓｅａｎ Ｃ．Ｒｈｅａ，Ａｎｔｈｏｎｙ Ｄ．Ｊｏｓｅｐｈ，ａｎｄ Ｊｏｈｎ Ｄ．Ｋｕｂｉａｔｏｗｉｃｚ．，”Ｔａｐｅｓｔｒｙ：Ａ Ｒｅｓｉｌｉｅｎｔ Ｇｌｏｂａｌ−Ｓｃａｌｅ Ｏｖｅｒｌａｙ ｆｏｒ Ｓｅｒｖｉｃｅ Ｄｅｐｌｏｙｍｅｎｔ”，ＩＥＥＥ Ｊｏｕｒｎａｌ ｏｎ Ｓｅｌｅｃｔｅｄ Ａｒｅａｓ ｉｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｖｏｌ ２２，Ｎｏ．１，（２００４）
【非特許文献３】ｈｔｔｐ：／／ｒｅｓｅａｒｃｈ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ／〜ａｎｔｒ／ＰＡＳＴ／ｄｅｆａｕｌｔ．ｈｔｍ
【非特許文献４】Ａ．Ｒｏｗｓｔｒｏｎ ａｎｄ Ｐ．Ｄｒｕｓｃｈｅｌ，”Ｓｔｏｒａｇｅ ｍａｎａｇｅｍｅｎｔ ａｎｄ ｃａｃｈｉｎｇ ｉｎ ＰＡＳＴ，ａ ｌａｒｇｅ−ｓｃａｌｅ，ｐｅｒｓｉｓｔｅｎｔ ｐｅｅｒ−ｔｏ−ｐｅｅｒ ｓｔｏｒａｇｅ ｕｔｉｌｉｔｙ”，１８ｔｈ ＡＣＭ ＳＯＳＰ’０１，Ｌａｋｅ Ｌｏｕｉｓｅ，Ａｌｂｅｒｔａ，Ｃａｎａｄａ，（２００１）
【非特許文献５】ｈｔｔｐ：／／ｐｄｏｓ．ｃｓａｉｌ．ｍｉｔ．ｅｄｕ／ｃｈｏｒｄ／
【非特許文献６】Ｉｏｎ Ｓｔｏｉｃａ，Ｒｏｂｅｒｔ Ｍｏｒｒｉｓ，Ｄａｖｉｄ Ｋａｒｇｅｒ，Ｍ．Ｆｒａｎｓ Ｋａａｓｈｏｅｋ，ａｎｄ Ｈａｒｉ Ｂａｌａｋｒｉｓｈｎａｎ，“Ｃｈｏｒｄ：Ａ Ｓｃａｌａｂｌｅ Ｐｅｅｒ−ｔｏ−ｐｅｅｒ Ｌｏｏｋｕｐ Ｓｅｒｖｉｃｅ ｆｏｒ Ｉｎｔｅｒｎｅｔ Ａｐｐｌｉｃａｔｉｏｎｓ”，ＡＣＭ ＳＩＧＣＯＭＭ ２００１，（２００１）．
【発明の開示】
【発明が解決しようとする課題】
【００３１】
上述のＣｈｏｒｄのように、隣接テーブルとスキップテーブルを利用することでオーバーレイネットワークを構築する方法では、ノードの参加／離脱によりオーバーレイネットワークの構成が変化した際に、隣接テーブル及びスキップテーブルを再構築する必要がある。つまり、オーバーレイネットワークそれ自体を維持するためには隣接テーブルを正しく維持する必要がある。また、参照をより高速に行うためにはスキップテーブルを正しく維持することが望ましい。
【００３２】
このような観点から、Ｃｈｏｒｄのような厳密モデル及び非厳密モデルによるスキップテーブルの構築・維持方法には、それぞれ以下のような課題がある。
【００３３】
＜厳密モデルによる方法＞
ノードが参加する際にスキップテーブルを完成しなければならず、またノードの参加／離脱に伴ってスキップテーブルの更新が必要となるノードに更新を通知し、全ての更新処理の完了を待たなければならない。このため、オーバーレイネットワークへ／からのノードの参加／離脱に時間がかかる。
【００３４】
＜非厳密モデルによる方法＞
各ノードが管理するスキップテーブルの更新が定期的に行われる。したがって、スキップテーブルの更新時より後にオーバーレイネットワークへ／からのノードの参加／離脱があった場合にも、次回更新時までスキップテーブルは更新されない。そのため、スキップテーブルの更新時期が到来するまでの間は、更新前のスキップテーブルを使用し続けなければならない。また、スキップテーブルの更新が必要ないときでも、更新が必要かを定期的に確認しなければならない。つまり、スキップテーブルを利用しないときにも無駄に更新処理が行われる。なお、Ｃｈｏｒｄでは、スキップテーブル中の更新されるべきショートカットパスがランダムに選択されるため、ショートカットパス毎の更新間隔は一定でない）。
【００３５】
本発明は上記事情を考慮してなされたものでその目的は、オーバーレイネットワークを管理するのに用いられるスキップテーブルの更新処理に要するコストを軽減することができるオーバーレイネットワーク構築・維持方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００３６】
本発明の１つの観点によれば、複数のノードから構成されるオーバーレイネットワークであって、前記複数のノードの各々が、前記オーバーレイネットワーク上での識別子であるｍビットのノードＩＤとアンダーレイネットワーク上での識別子であるアドレスとを持つと共に、前記複数のノードのノードＩＤを当該ノードＩＤの大きさの順序でリング状に整列した際に自身に後続して隣接するノードのノードＩＤ及びアドレス並びに自身に先行して隣接するノードのノードＩＤ及びアドレスを保持する隣接テーブルと、目的のノードＩＤまたはオブジェクトＩＤを入力として、当該入力されたノードＩＤまたはオブジェクトＩＤに最も近いノードＩＤを持つノードのアドレスを逐次問い合わせにより取得するためのショートカットパスの情報として、前記複数のノードのうち、予め定められた規則に従って選択された自身以外のｍ個のノードのノードＩＤ及びアドレスを保持するスキップテーブルとを備えたオーバーレイネットワークを構築・維持するためのオーバーレイネットワーク構築・維持方法が提供される。このオーバーレイネットワーク構築・維持方法は、前記オーバーレイネットワークに第１のノードが参加する場合に、前記第１のノードが、前記複数のノードのうちの任意のノードである第２のノードに対して、前記リング上で前記第１のノードに第１の方向で隣接するノードである第３のノードのノードＩＤ及びアドレスを取得するための第１の問い合わせを行うステップと、前記第１の問い合わせに応じて前記第１のノードが前記第３のノードのノードＩＤ及びアドレスを取得した場合、前記第１のノードが前記第３のノードに対して、前記リング上で当該第３のノードに前記第１の方向とは逆の第２の方向で隣接するノードである第４のノードのノードＩＤ及びアドレスを取得するための第２の問い合わせを行うステップと、前記第２の問い合わせに応じて前記第１のノードが前記第４のノードのノードＩＤ及びアドレスを取得した場合、前記第１のノードが、前記第３のノードのノードＩＤ及びアドレスと前記第４のノードのノードＩＤ及びアドレスとに基づいて、前記第１のノードの隣接テーブルを構築するステップと、前記第１のノードが前記オーバーレイネットワークに参加する場合に、前記第１のノードが、前記第１のノードのスキップテーブルを初期化するステップと、目的のノードＩＤまたはオブジェクトＩＤを入力として、当該入力されたノードＩＤまたはオブジェクトＩＤに最も近いノードＩＤを持つノードのアドレスを前記第１のノードが逐次問い合わせにより取得するための参照処理であって、前記第１のノードが前記問い合わせを前記第１のノードの前記スキップテーブルの示すショートカットパスに従って前記複数のノードのうちの自身以外のノードである第５のノードに転送する過程で、当該ショートカットパスを更新するステップを含む参照処理を実行するステップとを具備する。
【発明の効果】
【００３７】
本発明によれば、スキップテーブルは参照（逐次問い合わせ）の過程で利用されことから、参照を行わないのであればスキップテーブルを更新する必要はないことに着目し、オーバーレイネットワークにノードが参加する際にはスキップテーブルを更新せず、スキップテーブルを利用する（参照を行う）過程でスキップテーブルも更新することにより、従来技術と比較してオーバーレイネットワークへのノードの参加に時間がかからず、スキップテーブルの更新処理に要するコストを軽減することができる。また本発明によれば、スキップテーブルを利用するときに当該スキップテーブルを更新することにより、無駄な更新処理が発生するのを防止でき、しかも当該スキップテーブルの更新が必要なときに直ちに当該スキップテーブルの更新が行われる。
【発明を実施するための最良の形態】
【００３８】
以下、本発明の実施の形態につき図面を参照して説明する。  
図１は本発明の一実施形態に係るオーバーレイネットワークシステムのシステム構成を示す。図１のオーバーレイネットワークシステムは、オーバーレイネットワーク１０を含む。オーバーレイネットワーク１０は、３ビットのリング（Ｃｈｏｒｄリング）に対応し、最大８つのノードを収容できるものとする。このオーバーレイネットワーク１０に収容されるノードを、オーバーレイネットワーク１０に参加するノードと表現することもある。オーバーレイネットワーク１０に収容（参加）可能な８つのノードのＩＤ（ノードＩＤ）は、２進数表記で０００，００１，０１０，０１１，１００，１０１，１１０，１１１（１０進数表記で０，１，２，３，４，５，６，７）であるものとする。このＩＤの組をＩＤ＝｛０００，００１，０１０，０１１，１００，１０１，１１０，１１１｝のように表す。このＩＤをｉｄ（またはＩＤ ｉｄ）のように表記することもある。
【００３９】
図１のオーバーレイネットワークシステムの例では、オーバーレイネットワーク１０に、ＩＤ＝｛０００，００１，０１１，１００，１１０，１１１｝の６つのノード２０-0，２０-1，２０-3，２０-4，２０-6，２０-7が参加している。これらのノード２０-0，２０-1，２０-3，２０-4，２０-6，２０-7は実線の丸印で示されている。また、これらの丸印の近傍には、対応するノードのＩＤと共にアドレス（ＩＰアドレス）が表記されている。
【００４０】
図１において、破線の丸印で示される、ＩＤ＝｛０１０，１０１｝の２つのノード２０-2，２０-5は、現在オーバーレイネットワーク１０に参加していないが、当該オーバーレイネットワーク１０に参加可能なノードである。
【００４１】
＜ノードのハードウェア構成＞
図２は、ノード２０-tのハードウェア構成を示す。ノード２０-tは図１に示されるオーバーレイネットワーク１０に参加しているノード２０-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がノード２０-7（ｔ＝７）の場合について示す。構成情報５０-tは、ノード情報５１-t、隣接テーブル５２-t及びスキップテーブル５３-tから構成される。
【００５４】
ノード情報５１-tは、ＩＤ ｉｄビット数ｍ、ＩＤ ｉｄ及びアドレス（ＩＰアドレス）ａｄｄｒから構成される。  
ＩＤ ｉｄビット数ｍは、ノード２０-tのノードＩＤ（ＩＤ ｉｄ）のビット数を示す、つまりＩＤ ｉｄビット数ｍは、オーバーレイネットワーク１０の空間（オーバーレイネットワーク空間、オーバーレイネットワークのハッシュ空間）を表すビット数である。ｍの値は全ノードで共通である。本実施形態ではｍ＝３である。
【００５５】
ＩＤ ｉｄ（ｉｄ）は、ノード２０-tのノードＩＤを示す。ＩＤ ｉｄのビット数は、ＩＤ ｉｄビット数ｍで示される。ＩＤ ｉｄは、ノード２０-tが参加しているオーバーレイネットワーク１０の中で固有のＩＤである。ＩＤ ｉｄには、ノード２０-tのＩＰアドレスのハッシュ値が用いられる。  
アドレスａｄｄｒは、ノード２０-tのＩＰアドレスである。
【００５６】
隣接テーブル５２-tは、ノード２０-tの後続隣接ノードの情報（後続隣接ノード情報）を保持するエントリ（後続隣接ノード情報エントリ）ｓｕｃｃｅｓｓｏｒと、ノード２０-tの先行隣接ノードの情報（先行隣接ノード情報）を保持するエントリ（先行隣接ノード情報エントリ）ｐｒｅｄｅｃｅｓｓｏｒとを有する。ノード２０-tの後続隣接ノード（ｓｕｃｃｅｓｓｏｒ ｎｏｄｅ）及び先行隣接ノード（ｐｒｅｄｅｃｅｓｓｏｒ ｎｏｄｅ）とは、オーバーレイネットワーク１０に参加している（包含される）全てのノードのｉｄ（ＩＤ ｉｄ）を昇順に整列してリング状に並べたときの、それぞれ、ノード２０-t自身のｉｄから時計回りで隣接しているｉｄを持つノード及び反時計回りで隣接しているｉｄを持つノードを指す。つまりノード２０-tの後続隣接ノードは、リング上においてノード２０-tから時計回りで最初に遭遇する（ノード２０-t自身を除いて最も近いノードＩＤを持つ）ノードを指す。また先行隣接ノードは、上記リング上においてノード２０-tから反時計回りに最初に遭遇する（ノード２０-t自身を除いて最も遠いノードＩＤを持つ）ノードを指す。
【００５７】
隣接テーブル５２-tのエントリｓｕｃｃｅｓｓｏｒに保持される後続隣接ノード情報は、後続隣接ノード（ｓｕｃｃｅｓｓｏｒ ｎｏｄｅ）のＩＤ ｉｄ及びＩＰアドレスａｄｄｒを含む。一方、隣接テーブル５２-tのエントリｐｒｅｄｅｃｅｓｓｏｒに保持される先行隣接ノード情報は、先行隣接ノード（ｐｒｅｄｅｃｅｓｓｏｒ ｎｏｄｅ）のＩＤ ｉｄ及びＩＰアドレスａｄｄｒを含む。
【００５８】
なお、以下の説明では、後続隣接ノードをｓｕｃｃｅｓｓｏｒまたはｓｕｃｃｅｓｓｏｒノードと呼び、先行隣接ノードをｐｒｅｄｅｃｅｓｓｏｒまたはｐｒｅｄｅｃｅｓｓｏｒノードと呼ぶこともある。また、エントリｓｕｃｃｅｓｓｏｒに保持されるｉｄ及びａｄｄｒを、それぞれ、ｓｕｃｃｅｓｓｏｒ．ｉｄ及びｓｕｃｃｅｓｓｏｒ．ａｄｄｒと表記し、エントリｐｒｅｄｅｃｅｓｓｏｒに保持されるｉｄ及びａｄｄｒを、それぞれ、ｐｒｅｄｅｃｅｓｓｏｒ．ｉｄ及びｐｒｅｄｅｃｅｓｓｏｒ．ａｄｄｒと表記することもある。また、エントリｓｕｃｃｅｓｓｏｒに保持される情報（後続隣接ノード情報）全体をｓｕｃｃｅｓｓｏｒ、エントリｐｒｅｄｅｃｅｓｓｏｒに保持される情報（先行隣接ノード情報）全体をｐｒｅｄｅｃｅｓｓｏｒと表記することもある。
【００５９】
スキップテーブル５３-tは、ルーティングをより少ないホップ数の問い合わせ転送で可能にするためのショートカットパスを記述したテーブルである。スキップテーブル５３-tは、非特許文献５，６に記載されているフィンガーテーブル（fingertable）に相当する。
【００６０】
スキップテーブル５３-tは、ｉを変数とすると、ｉ＝０からｉ＝ｍ−１までの各ｉ（ｉ＝｛０，...ｍ−１｝）に関して、ショートカットパスの情報を保持する。ショートカットパスの情報は、ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstart、ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌend、ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ及びｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒから構成される。
【００６１】
ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstart、ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌend、ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ及びｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒの各情報は、以下の生成規則に基づいて生成される。
【００６２】
ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstart
＝（ｉｄ＋２i）ｍｏｄ ２m
ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌend
＝ｓｋｉｐ［（ｉ＋１）ｍｏｄ ｍ］．ｉｎｔｅｒｖａｌstart
ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ
＝オーバーレイネットワーク１０に参加している全てのノードのｉｄを昇順に整列してリング状に並べたときの、ＩＤ ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartから時計回りで当該ＩＤ ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartに最も近いＩＤを持つノードのｉｄ（ノードＩＤ）（後述する図５参照）
但し、ｓｋｉｐ［０］．ｓｕｃｃｅｓｓｏｒ．ｉｄは、ノード２０-t自身のｓｕｃｃｅｓｓｏｒ（後続隣接ノード）となるノードのノードＩＤ（ｓｕｃｃｅｓｓｏｒ．ｉｄ）であることに注意。したがって、隣接テーブル５２-tを正しく維持していれば、スキップテーブル５３-tの少なくともこのショートカットパス（ｓｋｉｐ［０］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）は正しく維持されることになる。
【００６３】
ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒ
＝ｉｄ（ノードＩＤ）がｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄのノードのアドレス（ＩＰアドレス）
但し、ｓｋｉｐ［０］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒは、ノード２０-t自身のｓｕｃｃｅｓｓｏｒとなるノードのアドレスであることに注意。したがって、隣接テーブル５２-tを正しく維持していれば、スキップテーブル５３-tの少なくともこのショートカットパス（ｓｋｉｐ［０］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒ）は正しく維持されることになる。
【００６４】
図５は、ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartとｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄとの関係を示す。ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartは、ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄを決定する際のリング上の基準位置を示す基準位置情報である。
【００６５】
再び図１を参照すると、当該図１には、オーバーレイネットワーク１０に参加しているノードＩＤ １１１のノード２０-7（ｔ＝７）が保持する構成情報５０-7（ｔ＝７）の例が示されている。
【００６６】
図１において、ノード２０-7の構成情報５０-7に含まれているノード情報５１-7（ｔ＝７）は、
ａｄｄｒ：ノード２０-7のアドレス（ＩＰｖ４アドレス１９２．１６８．０．１）
ｉｄ：ノード２０-7のノードＩＤ（１１１）
ｍ：オーバーレイネットワーク１０のハッシュ空間を表すビット数（３）
から構成される。
【００６７】
図１において、ノード２０-7の構成情報５０-7に含まれている隣接テーブル５２-7（ｔ＝７）は、
ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝：ノード２０-7の後続隣接ノード（ｓｕｃｃｅｓｓｏｒ）のノードＩＤ及びアドレス（０００及び１０．０．１．１）
ｐｒｅｄｅｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝：ノード２０-7の先行隣接ノード（ｐｒｅｄｅｃｅｓｓｏｒ）のノードＩＤ及びアドレス（１１０及び１９２．１６８．１００．３）
を保持する。
【００６８】
図１において、ノード２０-7の構成情報５０-7に含まれているスキップテーブル５３--7（ｔ＝７）は、ｉ＝｛０...ｍ−１｝＝｛０...２｝に関して、
ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstart：（ｉｄ＋２i）ｍｏｄ ２m
ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌend：ｓｋｉｐ［（ｉ＋１） ｍｏｄ ｍ］．ｉｎｔｅｒｖａｌstart
ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝：ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartに最も近いノードＩＤを持つノードのノードＩＤ及びアドレス
を保持する。
【００６９】
また、図１には、構成情報５０-7に含まれるスキップテーブル５３-７に保持されているショートカットパスの情報によって示される、ノード２０-7からノードＩＤがそれぞれｓｋｉｐ［０］．ｓｕｃｃｅｓｓｏｒ．ｉｄ＝０００，ｓｋｉｐ［１］．ｓｕｃｃｅｓｓｏｒ．ｉｄ＝００１及びｓｋｉｐ［２］．ｓｕｃｃｅｓｓｏｒ．ｉｄ＝０１１のノード（つまりノード２０-0，２０-1及び２０-3）へのショートカットパス１０１，１０２及び１０３も示されている。
【００７０】
＜オーバーレイネットワークの構築・維持＞
次に、オーバーレイネットワーク１０を構築・維持する方法について説明する。  
まず、あるノードＪｏｉｎｅｒがオーバーレイネットワーク１０に参加する際に、当該ノードＪｏｉｎｅｒが実行する処理（主として隣接テーブルの構築とスキップテーブルの初期化）の概要について説明する。ここでは、ノードＪｏｉｎｅｒは、ノードＩＤが０１０または１０１のノード（つまりノード２０-2または２０-5）であるものとする。
【００７１】
１．隣接テーブルの構築
処理１ａ）
ノードＪｏｉｎｅｒ（の探索部２９）は、既にオーバーレイネットワーク１０に参加している任意のノードＩｎｔｒｏｄｕｃｅｒに対し、当該ノードＩｎｔｒｏｄｕｃｅｒのアドレス（Ｉｎｔｒｏｄｕｃｅｒ．ａｄｄｒ）を用いて、リング（Ｃｈｏｒｄリング）上で当該Ｊｏｉｎｅｒのｓｕｃｃｅｓｓｏｒ（後続隣接ノード）となるノードＳｕｃｃｅｓｓｏｒのノードＩＤ（Ｓｕｃｃｅｓｓｏｒ．ｉｄ）及びアドレス（Ｓｕｃｃｅｓｓｏｒ．ａｄｄｒ）を問い合わせる。ここでは、ノードＩｎｔｒｏｄｕｃｅｒは、ノード２０-0，２０-1，２０-3，２０-4，２０-6または２０-7であるものとする。
【００７２】
なお、以下の説明では、ノードをＡとすると、ノードＡのノードＩＤをＡ．ｉｄ、アドレスをＡ．ａｄｄｒと表記し、ノードＡのノードＩＤ（Ａ．ｉｄ）及びアドレス（Ａ．ａｄｄｒ）を、Ａ．｛ｉｄ，ａｄｄｒ｝と表記することもある。したがって、例えばノードＳｕｃｃｅｓｓｏｒのノードＩＤ及びアドレスは、Ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝のように表すことができる。
【００７３】
ノードＩｎｔｒｏｄｕｃｅｒは、ノードＪｏｉｎｅｒのノードＩＤ（Ｊｏｉｎｅｒ．ｉｄ）を入力として、自身のスキップテーブル５３-t（以下、スキップテーブル５３-t(J)と表現する）の更新処理を伴う逐次問い合わせ（再帰的ルーティング：ＲｅｃｕｒｓｉｖｅＲｏｕｔｉｎｇ）でのｓｕｃｃｅｓｓｏｒ（後続隣接ノード）参照処理を行う。このｓｕｃｃｅｓｓｏｒ参照処理については後述する。そしてノードＩｎｔｒｏｄｕｃｅｒは、リング上でＪｏｉｎｅｒ．ｉｄに最も近いノードＩＤを持ったノード（以下、ノードＳｕｃｃｅｓｓｏｒと称する）のノードＩＤ（Ｓｕｃｃｅｓｓｏｒ．ｉｄ）及びアドレス（Ｓｕｃｃｅｓｓｏｒ．ａｄｄｒ）を、ノードＪｏｉｎｅｒに出力（通知）する。このｓｕｃｃｅｓｓｏｒ参照処理を行うノードＩｎｔｒｏｄｕｃｅｒは、後述するノードＮｏｄｅに相当する。また、Ｊｏｉｎｅｒ．ｉｄ及びＳｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝は、それぞれ後述するＴａｒｇｅｔ．ｉｄ及びＴａｒｇｅｔＳｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝に相当する。
【００７４】
なお、ノードＩｎｔｒｏｄｕｃｅｒのアドレス（Ｉｎｔｒｏｄｕｃｅｒ．ａｄｄｒ）は、ノードＪｏｉｎｅｒに対して事前に与えられるものとする。ここでは、ノードＩｎｔｒｏｄｕｃｅｒのアドレスは、ユーザがノードＪｏｉｎｅｒの入出力機構２５を操作することにより、当該ノードＪｏｉｎｅｒに与えられる。
【００７５】
処理１ｂ）
ノードＪｏｉｎｅｒ（の探索部２９）は、ノードＳｕｃｃｅｓｓｏｒに対し、当該ノードＳｕｃｃｅｓｓｏｒのアドレス（Ｓｕｃｃｅｓｓｏｒ．ａｄｄｒ）を用いて、自身が参加する前の状態において当該ノードＳｕｃｃｅｓｓｏｒのｐｒｅｄｅｃｅｓｓｏｒ（先行隣接ノード）となるノードＰｒｅｄｅｃｅｓｓｏｒのノードＩＤ（Ｐｒｅｄｅｃｅｓｓｏｒ．ｉｄ）及びアドレス（Ｐｒｅｄｅｃｅｓｓｏｒ．ａｄｄｒ）を問い合わせる。
【００７６】
処理１ｃ）
ノードＪｏｉｎｅｒ（のテーブル管理部２８）は、ノードＳｕｃｃｅｓｓｏｒに対して当該ノードＪｏｉｎｅｒとの接続（リング上での接続）を要求する。  
ノードＳｕｃｃｅｓｓｏｒ（のテーブル管理部２８）は、自身のｐｒｅｄｅｃｅｓｓｏｒとして、ノードＰｒｅｄｅｃｅｓｓｏｒからノードＪｏｉｎｅｒへの切り替えを自身の隣接テーブル５２-t（隣接テーブル５２-t(S)）上で行う。またノードＳｕｃｃｅｓｓｏｒは、自身のスキップテーブル５３-t（以下、スキップテーブル５３-t(S)）のうち、ノードＪｏｉｎｅｒの追加により影響を受けるエントリの内容（ノードＩＤ及びアドレス）をＪｏｉｎｅｒ（ノードＪｏｉｎｅｒのノードＩＤ及びアドレス）に書き換える。
【００７７】
処理１ｄ）
ノードＪｏｉｎｅｒ（のテーブル管理部２８）は、ノードＰｒｅｄｅｃｅｓｓｏｒに対して当該ノードＪｏｉｎｅｒとの接続（リング上での接続）を要求する。
【００７８】
ノードＰｒｅｄｅｃｅｓｓｏｒ（のテーブル管理部２８）は、自身のｓｕｃｃｅｓｓｏｒとして、ノードＳｕｃｃｅｓｓｏｒからノードＪｏｉｎｅｒへの切り替えを自身の隣接テーブル５２-t（隣接テーブル５２-t(P)）上で行う。またノードＰｒｅｄｅｃｅｓｓｏｒは、自身のスキップテーブル５３-t（スキップテーブル５３-t(P)）のうち、ノードＪｏｉｎｅｒの追加により影響を受けるエントリの内容（ノードＩＤ及びアドレス）をＪｏｉｎｅｒ（ノードＪｏｉｎｅｒのノードＩＤ及びアドレス）に書き換える。
【００７９】
処理１ｅ）
ノードＪｏｉｎｅｒ（のテーブル管理部２８）は、ノードＳｕｃｃｅｓｓｏｒに対して当該ノードＳｕｃｃｅｓｓｏｒのスキップテーブル５３-t(S)の通知を要求する。
【００８０】
処理１ｆ）
ノードＪｏｉｎｅｒ（のテーブル管理部２８）は、ノードＰｒｅｄｅｃｅｓｓｏｒに対して当該ノードＰｒｅｄｅｃｅｓｓｏｒのスキップテーブル５３-t(P)の通知を要求する。
【００８１】
２．スキップテーブルの初期化
ノードＪｏｉｎｅｒ（のテーブル管理部２８）は、自身のスキップテーブル５３-t(J)を構築（初期化）する。この時点においてノードＪｏｉｎｅｒは、スキップテーブル５３-t(J)を使用する訳ではない。このため、この時点においてスキップテーブル５３-t(J)は完全である必要はないことに注意する。ここで、スキップテーブル５３-t(J)が完全とは、当該テーブル５３-t(J)のｍ個のエントリの示すｓｋｉｐ［ｉ…ｍ−１］．ｓｕｃｃｅｓｓｏｒが、オーバーレイネットワーク１０に参加している全ノードのうちでｓｋｉｐ［ｉ…ｍ−１］．ｉｎｔｅｒｖａｌstartに最も近いノードであることをいう。
【００８２】
本実施形態においてノードＪｏｉｎｅｒ（のテーブル管理部２８）は、スキップテーブル５３-t(J)のｍ個のエントリの保持するｓｋｉｐ［ｉ…ｍ−１］．ｓｕｃｃｅｓｓｏｒのノードＩＤ及びアドレスとして、ノードＳｕｃｃｅｓｓｏｒ及びＰｒｅｄｅｃｅｓｓｏｒよりそれぞれ通知を受けたスキップテーブル５３-t(S)及び５３-t(P)に保持されているノードのノードＩＤ及びアドレスの中から、ｓｋｉｐ［ｉ…ｍ−１］．ｉｎｔｅｒｖａｌstartに最も近いノードのノードＩＤ及びアドレスを選択する。
【００８３】
ノードＪｏｉｎｅｒがオーバーレイネットワーク１０に参加した後は、当該ノードＪｏｉｎｅｒは自身のｓｕｃｃｅｓｓｏｒ（後続隣接ノード）及びｐｒｅｄｅｃｅｓｓｏｒ（先行隣接ノード）とのリング上でのリンク（接続）を維持する。
【００８４】
もし、ノードＪｏｉｎｅｒのｓｕｃｃｅｓｓｏｒが、オーバーレイネットワーク１０から何らかの要因で離脱した場合、ノードＪｏｉｎｅｒは、その離脱によって新たにｓｕｃｃｅｓｓｏｒとなるノードとのリンクを直ちに形成するものとする。同様に、もし、ノードＪｏｉｎｅｒのｐｒｅｄｅｃｅｓｓｏｒが、オーバーレイネットワーク１０から何らかの要因で離脱した場合には、ノードＪｏｉｎｅｒは、その離脱によって新たにｐｒｅｄｅｃｅｓｓｏｒとなるノードとのリンクを直ちに形成するものとする。これを実現する方法については、非特許文献５及び６に示されているため、説明を省略する。
【００８５】
３．ノードＪｏｉｎｅｒでの処理の詳細
次に、ノードＪｏｉｎｅｒ（つまり新たにオーバーレイネットワーク１０に参加するノード）でのテーブル初期化処理（隣接テーブルの構築及びスキップテーブルの初期化のための処理）について、図６Ａ及び６Ｂのフローチャートを参照して説明する。
【００８６】
まずノードＪｏｉｎｅｒ（の探索部２９）は、以下の問い合わせ（ステップＳ２）のための入力となるノードＩＤとして、当該ノードＪｏｉｎｅｒ自身のノードＩＤ（Ｊｏｉｎｅｒ．ｉｄ）を設定する（ステップＳ１）。
【００８７】
次にノードＪｏｉｎｅｒ（の探索部２９）は、Ｊｏｉｎｅｒ．ｉｄを入力として、既にオーバーレイネットワーク１０に参加している任意のノードＩｎｔｒｏｄｕｃｅｒに対し、リング（Ｃｈｏｒｄリング）上で当該Ｊｏｉｎｅｒのｓｕｃｃｅｓｓｏｒ（後続隣接ノード）となるノードＳｕｃｃｅｓｓｏｒのノードＩＤ及びアドレス（Ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝）を問い合わせる（ステップＳ２）。このステップＳ２は上記処理１ａに相当する。
【００８８】
ノードＩｎｔｒｏｄｕｃｅｒ（の探索部２９）は、ノードＪｏｉｎｅｒからの問い合わせを受けて、ノードＳｕｃｃｅｓｓｏｒのノードＩＤ及びアドレス（Ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝）を、当該問い合わせに対する応答としてノードＪｏｉｎｅｒに出力する（ステップＳ３）。このノードＩｎｔｒｏｄｕｃｅｒでは、ノードＪｏｉｎｅｒからの問い合わせに対する応答のために、再帰的ルーティングでのｓｕｃｃｅｓｓｏｒ参照処理が行われる。このｓｕｃｃｅｓｓｏｒ参照処理については図１０Ａ及び１０Ｂのフローチャートを参照して後述する。
【００８９】
次にノードＪｏｉｎｅｒ（の探索部２９）は、ノードＩｎｔｒｏｄｕｃｅｒからの応答によって示されるノードＳｕｃｃｅｓｓｏｒに対し、自身が参加する前の状態において当該ノードＳｕｃｃｅｓｓｏｒのｐｒｅｄｅｃｅｓｓｏｒとなるノードＰｒｅｄｅｃｅｓｓｏｒのノードＩＤ及びアドレス（Ｐｒｅｄｅｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝）を問い合わせる（ステップＳ４）。このステップＳ４は上記処理１ｂに相当する。
【００９０】
ノードＳｕｃｃｅｓｓｏｒ（の探索部２９）は、ノードＪｏｉｎｅｒからの問い合わせを受けて、当該ノードＳｕｃｃｅｓｓｏｒのｐｒｅｄｅｃｅｓｓｏｒとなるノードＰｒｅｄｅｃｅｓｓｏｒのノードＩＤ及びアドレス（Ｐｒｅｄｅｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝）を、当該問い合わせに対する応答としてノードＪｏｉｎｅｒに出力する（ステップＳ５）。
【００９１】
次にノードＪｏｉｎｅｒ（のテーブル管理部２８）は、以下の要求（ステップＳ７）のための入力として、当該ノードＪｏｉｎｅｒ自身のノードＩＤ及びアドレス（Ｊｏｉｎｅｒ．｛ｉｄ，ａｄｄｒ｝）を設定する（ステップＳ６）。
【００９２】
そしてノードＪｏｉｎｅｒ（のテーブル管理部２８）は、Ｊｏｉｎｅｒ．｛ｉｄ，ａｄｄｒ｝を入力として、ノードＳｕｃｃｅｓｓｏｒに対して当該ノードＪｏｉｎｅｒとの接続を要求する（ステップＳ７）。このステップＳ７は上記処理１ｃ）に相当する。ノードＳｕｃｃｅｓｓｏｒは、このノードＪｏｉｎｅｒからの要求を受けて、後述する接続処理（図７参照）を実行する。
【００９３】
次にノードＪｏｉｎｅｒ（のテーブル管理部２８）は、以下の要求（ステップＳ９）のための入力として、当該ノードＪｏｉｎｅｒ自身のノードＩＤ及びアドレス（Ｊｏｉｎｅｒ．｛ｉｄ，ａｄｄｒ｝）を設定する（ステップＳ８）。
【００９４】
そしてノードＪｏｉｎｅｒ（のテーブル管理部２８）は、Ｊｏｉｎｅｒ．｛ｉｄ，ａｄｄｒ｝を入力として、ノードＰｒｅｄｅｃｅｓｓｏｒに対して当該ノードＪｏｉｎｅｒとの接続を要求する（ステップＳ９）。このステップＳ９は上記処理１ｄ）に相当する。ノードＰｒｅｄｅｃｅｓｓｏｒは、このノードＪｏｉｎｅｒからの要求を受けて、後述する接続処理（図８参照）を実行する。
【００９５】
次にノードＪｏｉｎｅｒ（のテーブル管理部２８）は、自身の隣接テーブル５２-t(J)上で、自身のｓｕｃｃｅｓｓｏｒ（Ｊｏｉｎｅｒ．ｓｕｃｃｅｓｓｏｒ）のノードＩＤ及びアドレス（Ｊｏｉｎｅｒ．ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝）として、ノードＳｕｃｃｅｓｓｏｒのノードＩＤ及びアドレス（Ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝）を設定する（ステップＳ１０）。このステップＳ１０において、ノードＪｏｉｎｅｒは、隣接テーブル５２-t(J)上で、自身のｐｒｅｄｅｃｅｓｓｏｒ（Ｊｏｉｎｅｒ．ｐｒｅｄｅｃｅｓｓｏｒ）のノードＩＤ及びアドレス（Ｊｏｉｎｅｒ．ｐｒｅｄｅｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝）として、ノードＰｒｅｄｅｃｅｓｓｏｒのノードＩＤ及びアドレス（Ｐｒｅｄｅｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝）を設定する。なお、以下の説明では、Ｊｏｉｎｅｒ．ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝をＪｏｉｎｅｒ．ｓｕｃｃｅｓｓｏｒと表現することもある。
【００９６】
次にノードＪｏｉｎｅｒ（のテーブル管理部２８）は、ノードＳｕｃｃｅｓｓｏｒに対して、当該ノードＳｕｃｃｅｓｓｏｒのスキップテーブル５３-t(S)の通知を要求する（ステップＳ１１）。つまりノードＪｏｉｎｅｒはステップＳ１１において、ノードＳｕｃｃｅｓｓｏｒに対して、当該ノードＳｕｃｃｅｓｓｏｒのスキップテーブル５３-t(S)を問い合わせる。このステップＳ１１は上記処理１ｅ）に相当する。以下の説明では、ノードＳｕｃｃｅｓｓｏｒのスキップテーブル５３-t(S)を、Ｓｕｃｃｅｓｓｏｒ．ｓｋｉｐと表現することもある。
【００９７】
ノードＳｕｃｃｅｓｓｏｒ（のテーブル管理部２８）は、ノードＪｏｉｎｅｒからの問い合わせに応じて、当該ノードＳｕｃｃｅｓｓｏｒのＳｕｃｃｅｓｓｏｒ．ｓｋｉｐを、当該問い合わせに対する応答としてノードＪｏｉｎｅｒに出力する（ステップＳ１２）。これによりノードＪｏｉｎｅｒは、ノードＳｕｃｃｅｓｓｏｒのＳｕｃｃｅｓｓｏｒ．ｓｋｉｐを取得することができる。
【００９８】
次にノードＪｏｉｎｅｒ（のテーブル管理部２８）は、ノードＰｒｅｄｅｃｅｓｓｏｒに対して、当該ノードＰｒｅｄｅｃｅｓｓｏｒのスキップテーブル５３-t(P)を問い合わせる（ステップＳ１３）。このステップＳ１３は上記処理１ｆ）に相当する。以下の説明では、ノードＰｒｅｄｅｃｅｓｓｏｒのスキップテーブル５３-t(P)を、Ｐｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐと表現することもある。
【００９９】
ノードＰｒｅｄｅｃｅｓｓｏｒ（のテーブル管理部２８）は、ノードＪｏｉｎｅｒからの問い合わせに応じて、当該ノードＰｒｅｄｅｃｅｓｓｏｒのＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐを、当該問い合わせに対する応答としてノードＪｏｉｎｅｒに出力する（ステップＳ１４）。これによりノードＪｏｉｎｅｒは、ノードＰｒｅｄｅｃｅｓｓｏｒのＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐを取得することができる。
【０１００】
次にノードＪｏｉｎｅｒ（のテーブル管理部２８）は、以下のスキップテーブル初期化処理（ステップＳ１６）のための入力として、当該ノードＪｏｉｎｅｒ自身のノードＩＤ及びアドレス（Ｊｏｉｎｅｒ．｛ｉｄ，ａｄｄｒ｝）と、隣接テーブル５２-t(J)における自身のｓｕｃｃｅｓｓｏｒのエントリの情報（Ｊｏｉｎｅｒ．ｓｕｃｃｅｓｓｏｒ）とを設定する（ステップＳ１５）。つまりノードＪｏｉｎｅｒは、スキップテーブル初期化処理のための入力として、Ｊｏｉｎｅｒ．｛ｉｄ，ａｄｄｒ，ｓｕｃｃｅｓｓｏｒ｝を設定する。またノードＪｏｉｎｅｒは、ステップＳ１５において、スキップテーブル初期化処理のための入力として、ステップＳ１１及び１３で取得した、ノードＳｕｃｃｅｓｓｏｒのスキップテーブル５３-t(S)及びノードＰｒｅｄｅｃｅｓｓｏｒのスキップテーブル５３-t(P)（つまりＳｕｃｃｅｓｓｏｒ．ｓｋｉｐ及びＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐ）を設定する。
【０１０１】
そしてノードＪｏｉｎｅｒ（のテーブル管理部２８）は、上記入力Ｊｏｉｎｅｒ．｛ｉｄ，ａｄｄｒ，ｓｕｃｃｅｓｓｏｒ｝，Ｓｕｃｃｅｓｓｏｒ．ｓｋｉｐ及びＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐに基づき、自身のスキップテーブル５３-t(J)（つまりＪｏｉｎｅｒ．ｓｋｉｐ）を初期化するための処理（スキップテーブル初期化処理）を実行する（ステップＳ１６）。このステップＳ１６は上記処理２に相当する。ステップＳ１６（スキップテーブル初期化処理）の詳細については図９のフローチャートを参照して後述する。
【０１０２】
＜ノードＳｕｃｃｅｓｓｏｒでの接続処理＞
次に新たにオーバーレイネットワーク１０に参加するノードＪｏｉｎｅｒからの接続要求に応じてノードＳｕｃｃｅｓｓｏｒ（後続隣接ノード）で行われる接続処理の手順について、図７のフローチャートを参照して説明する。
【０１０３】
ノードＪｏｉｎｅｒからの接続要求は、当該ノードＪｏｉｎｅｒのノードＩＤ及びアドレス（Ｊｏｉｎｅｒ．｛ｉｄ，ａｄｄｒ｝）を含む。ノードＳｕｃｃｅｓｓｏｒ（のテーブル管理部２８）は、このＪｏｉｎｅｒ．｛ｉｄ，ａｄｄｒ｝を入力として、以下の手順で接続処理を実行する。
【０１０４】
まずノードＳｕｃｃｅｓｓｏｒは、自身の隣接テーブル５２-t(S)のｐｒｅｄｅｃｅｓｓｏｒ．ｉｄ（つまりＳｕｃｃｅｓｓｏｒ．ｐｒｅｄｅｃｅｓｓｏｒ．ｉｄ）及びｐｒｅｄｅｃｅｓｓｏｒ．ａｄｄｒ（つまりＳｕｃｃｅｓｓｏｒ．ｐｒｅｄｅｃｅｓｓｏｒ．ａｄｄｒ）を、それぞれＪｏｉｎｅｒ．ｉｄ及びＪｏｉｎｅｒ．ａｄｄｒに書き換える（ステップＳ２１）。
【０１０５】
次にノードＳｕｃｃｅｓｓｏｒは、変数ｉ（ｉ＝｛０...ｍ−１｝）に関して、Ｊｏｉｎｅｒ．ｉｄが、リング上で範囲［Ｓｕｃｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstart，Ｓｕｃｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）に収まるかを判定する（ステップＳ２２）。ここで、ｘ＝Ｊｏｉｎｅｒ．ｉｄ、ｙ＝Ｓｕｃｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstart、ｚ＝Ｓｕｃｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄと置くと、範囲［ｙ，ｚ）における“［”は、当該範囲［ｙ，ｚ）にｙを含むことを表し、“）”は、当該範囲［ｙ，ｚ）にｚを含まないことを表す。例えば、ｙ＝２（２進数表記で０１０），ｚ＝５（２進数表記で１０１）とすると、［ｙ，ｚ）の範囲（つまり［２，５）の範囲）に収まるｘの値は、｛２，３，４｝（２進数表記で｛０１０，０１１，１００｝）である。
【０１０６】
もし、ステップＳ２２の判定がＹｅｓであるならば、ノードＳｕｃｃｅｓｓｏｒは、現在のＳｕｃｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄよりも、Ｊｏｉｎｅｒ．ｉｄの方がリング上でＳｕｃｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartに近いと判断する。つまり、ノードＳｕｃｃｅｓｓｏｒは、ノードＪｏｉｎｅｒがオーバーレイネットワーク１０に参加したことにより、スキップテーブル５３-t(S)のエントリＳｕｃｃｅｓｓｏｒ．ｓｋｉｐ．［ｉ］が影響を受けるものと判断する。そこでノードＳｕｃｃｅｓｓｏｒは、エントリＳｕｃｃｅｓｓｏｒ．ｓｋｉｐ．［ｉ］内のＳｕｃｃｅｓｓｏｒ．ｓｋｉｐ．［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ及びＳｕｃｃｅｓｓｏｒ．ｓｋｉｐ．［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒを、それぞれＪｏｉｎｅｒ．ｉｄ及びＪｏｉｎｅｒ．ａｄｄｒに書き換える（ステップＳ２３）。
【０１０７】
一方、ステップＳ２２の判定がＮｏであるならば、ノードＳｕｃｃｅｓｓｏｒは、現在のＳｕｃｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄの方が、Ｊｏｉｎｅｒ．ｉｄよりもリング上でＳｕｃｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartに近いと判断する。つまり、ノードＳｕｃｃｅｓｓｏｒは、ノードＪｏｉｎｅｒがオーバーレイネットワーク１０に参加しても、スキップテーブル５３-t(S)のエントリＳｕｃｃｅｓｓｏｒ．ｓｋｉｐ．［ｉ］は影響を受けないものと判断する。この場合、ノードＳｕｃｃｅｓｓｏｒはステップＳ２３（つまりスキップテーブル５３-t(S)の書き換え処理）をスキップする。
【０１０８】
ノードＳｕｃｃｅｓｓｏｒは、上記ステップＳ２２を、ｉ＝０からｉ＝ｍ−１までの全てのｉについて繰り返す。
【０１０９】
＜ノードＰｒｅｄｅｃｅｓｓｏｒでの接続処理＞
次に新たにオーバーレイネットワーク１０に参加するノードＪｏｉｎｅｒからの接続要求に応じてノードＰｒｅｄｅｃｅｓｓｏｒ（先行隣接ノード）で行われる接続処理について、図８のフローチャートを参照して説明する。
【０１１０】
ノードＪｏｉｎｅｒからの接続要求は、当該ノードＪｏｉｎｅｒのノードＩＤ及びアドレス（Ｊｏｉｎｅｒ．｛ｉｄ，ａｄｄｒ｝）を含む。ノードＰｒｅｄｅｃｅｓｓｏｒ（のテーブル管理部２８）は、このＪｏｉｎｅｒ．｛ｉｄ，ａｄｄｒ｝を入力として、以下の手順で接続処理を実行する。
【０１１１】
まずノードＰｒｅｄｅｃｅｓｓｏｒは、自身の隣接テーブル５２-t(P)のｓｕｃｃｅｓｓｏｒ．ｉｄ（つまりＰｒｅｄｅｃｅｓｓｏｒ．ｓｕｃｃｅｓｓｏｒ．ｉｄ）及びｐｒｅｄｅｃｅｓｓｏｒ．ａｄｄｒ（つまりＰｒｅｄｅｃｅｓｓｏｒ．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒ）を、それぞれＪｏｉｎｅｒ．ｉｄ及びＪｏｉｎｅｒ．ａｄｄｒに書き換える（ステップＳ３１）。
【０１１２】
次にノードＰｒｅｄｅｃｅｓｓｏｒは、変数ｉ（ｉ＝｛０...ｍ−１｝）に関して、Ｊｏｉｎｅｒ．ｉｄが、リング上で範囲［Ｐｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstart，Ｐｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）に収まるかを判定する（ステップＳ３２）。
【０１１３】
もし、ステップＳ３２の判定がＹｅｓであるならば、ノードＰｒｅｄｅｃｅｓｓｏｒは、現在のＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄよりも、Ｊｏｉｎｅｒ．ｉｄの方がリング上でＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartに近いと判断する。つまり、ノードＰｒｅｄｅｃｅｓｓｏｒは、ノードＪｏｉｎｅｒがオーバーレイネットワーク１０に参加したことにより、スキップテーブル５３-t(P)のエントリＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐ．［ｉ］が影響を受けるものと判断する。そこでノードＰｒｅｄｅｃｅｓｓｏｒは、エントリＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐ．［ｉ］内のＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐ．［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ及びＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐ．［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒを、それぞれＪｏｉｎｅｒ．ｉｄ及びＪｏｉｎｅｒ．ａｄｄｒに書き換える（ステップＳ３３）。
【０１１４】
一方、ステップＳ３２の判定がＮｏであるならば、ノードＰｒｅｄｅｃｅｓｓｏｒは、現在のＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄの方が、Ｊｏｉｎｅｒ．ｉｄよりもリング上でＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartに近いに近いと判断する。この場合、ノードＰｒｅｄｅｃｅｓｓｏｒはステップＳ３３（つまりスキップテーブル５３-t(P)の書き換え処理）をスキップする。
【０１１５】
ノードＰｒｅｄｅｃｅｓｓｏｒは、上記ステップＳ３２を、ｉ＝０からｉ＝ｍ−１までの全てのｉについて繰り返す。
【０１１６】
＜ノードＪｏｉｎｅｒでのスキップテーブル初期化処理＞
次にノードＪｏｉｎｅｒでのスキップテーブル初期化処理の手順（つまりステップＳ１６の詳細）について、図９のフローチャートを参照して説明する。
【０１１７】
ノードＪｏｉｎｅｒ（のテーブル管理部２８）は、前述のＪｏｉｎｅｒ．｛ｉｄ，ａｄｄｒ，ｓｕｃｃｅｓｓｏｒ｝、Ｓｕｃｃｅｓｓｏｒ．ｓｋｉｐ及びＰｒｅｄｅｃｅｓｓｏｒ．ｓｋｉｐを入力として、以下の手順でスキップテーブル初期化処理を実行する。
【０１１８】
まずノードＪｏｉｎｅｒは、変数ｉ（ｉ＝｛０...ｍ−１｝）に関して、自身のスキップテーブル５３-t(J)のエントリｓｋｉｐ［ｉ］（つまり、エントリＪｏｉｎｅｒ．ｓｋｉｐ［ｉ］）内のｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝（つまりＪｏｉｎｅｒ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ）を、Ｊｏｉｎｅｒ．ｓｕｃｃｅｓｓｏｒ（つまりＪｏｉｎｅｒ．ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝）に設定する（ステップＳ４１）。このステップＳ４１において、ノードＪｏｉｎｅｒは、スキップテーブル５３-t(J)のエントリＪｏｉｎｅｒ．ｓｋｉｐ［ｉ］）内のｉｎｔｅｒｖａｌstart（つまりＪｏｉｎｅｒ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstart）を、（Ｊｏｉｎｅｒ．ｉｄ＋２i）ｍｏｄ ２mに設定する。
【０１１９】
ノードＪｏｉｎｅｒは、上記ステップＳ４１を、ｉ＝０からｉ＝ｍ−１までの全てのｉ（ｉ＝｛０...ｍ−１｝）について繰り返す。
【０１２０】
次にノードＪｏｉｎｅｒは、ｉ＝｛０...ｍ−１｝に関して、スキップテーブル５３-t(J)のエントリＪｏｉｎｅｒ．ｓｋｉｐ［ｉ］）内のｉｎｔｅｒｖａｌend（つまりＪｏｉｎｅｒ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌend）を、Ｊｏｉｎｅｒ．ｓｋｉｐ．［（ｉ＋１）ｍｏｄ ｍ］．ｉｎｔｅｒｖａｌstartに設定する（ステップＳ４２）。
【０１２１】
ノードＪｏｉｎｅｒは、上記ステップＳ４２を、ｉ＝０からｉ＝ｍ−１までの全てのｉについて繰り返す。
【０１２２】
次にノードＪｏｉｎｅｒは、変数ｉ（ｉ＝｛０...ｍ−１｝）及びｊ（ｊ＝｛０...ｍ−１｝）に関し、Ｓｕｃｃｅｓｓｏｒ．ｓｋｉｐ［ｊ］．ｓｕｃｃｅｓｓｏｒ．ｉｄが、リング上で範囲［Ｊｏｉｎｅｒ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstart，Ｊｏｉｎｅｒ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）に収まるかを判定する（ステップＳ４３）。
【０１２３】
もし、ステップＳ４３の判定がＹｅｓであるならば、ノードＪｏｉｎｅｒは、現在のＪｏｉｎｅｒ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄよりも、Ｓｕｃｃｅｓｓｏｒ．ｓｋｉｐ［ｊ］．ｓｕｃｃｅｓｓｏｒ．ｉｄの方がリング上でＪｏｉｎｅｒ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartに近いと判断する。そこでノードＪｏｉｎｅｒは、エントリＪｏｉｎｅｒ．ｓｋｉｐ．［ｉ］内のＪｏｉｎｅｒ．ｓｋｉｐ．［ｉ］．ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝を、Ｓｕｃｃｅｓｓｏｒ．ｓｋｉｐ［ｊ］．ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝に書き換える（ステップＳ４４）。
【０１２４】
一方、ステップＳ４３の判定がＮｏであるならば、ノードＪｏｉｎｅｒは、現在のＪｏｉｎｅｒ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄの方が、Ｓｕｃｃｅｓｓｏｒ．ｓｋｉｐ［ｊ］．ｓｕｃｃｅｓｓｏｒ．ｉｄよりもリング上でＪｏｉｎｅｒ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartに近いと判断する。この場合、ノードＪｏｉｎｅｒはステップＳ４４（つまりスキップテーブル５３-tの書き換え処理）をスキップする。
【０１２５】
ノードＪｏｉｎｅｒは、上記ステップＳ４３を、ｉ＝０からｉ＝ｍ−１までの全てのｉと、ｊ＝０からｊ＝ｍ−１までの全てのｊの組み合わせについて繰り返す。本実施形態では、上記ステップＳ４３が、あるｉについて、ｊ＝０からｊ＝ｍ−１まで繰り返す動作が、ｉ＝０からｉ＝ｍ−１までの全てについて繰り返される。
【０１２６】
＜ノードＮｏｄｅでの参照処理＞
次に本実施形態において、オーバーレイネットワーク１０に参加しているノード２０-tで実行される参照処理、つまり、あるオブジェクトまたはノードのＩＤを入力として、当該入力されたＩＤに最も近いノードＩＤを持つノードのノードＩＤ及びアドレスを取得する参照処理について、図１０Ａ及び１０Ｂのフローチャートを参照して説明する。この参照処理は、ノード２０-tが入力されたＩＤに最も近いノードＩＤを持つノードのノードＩＤ及びアドレスを取得する必要がある場合に実行される。このため、前記ステップＳ２でノードＪｏｉｎｅｒからノードＩｎｔｒｏｄｕｃｅｒにノードＳｕｃｃｅｓｓｏｒのノードＩＤ及びアドレスが問い合わせられた場合には、当該ノードＩｎｔｒｏｄｕｃｅｒで参照処理が実行される。以下の説明では、参照処理を実行するノード２０-tをノードＮｏｄｅと表記し、ノード２０-tが有するスキップテーブル５３-tをスキップテーブル５３-t(N)と表記することもある。
【０１２７】
本実施形態において、参照処理の入力（ＩＤ）をＴａｒｇｅｔｉｄで表し、参照処理の出力（参照結果、入力されたＩＤに最も近いノードＩＤを持つノードのノードＩＤ及びアドレス）をＳｔａｔｕｓ、Ｔａｒｇｅｔ．Ｓｕｃｃｅｓｓｏｒ．ｉｄ及びＴａｒｇｅｔ．Ｓｕｃｃｅｓｓｏｒ．ａｄｄｒで表す。
【０１２８】
Ｔａｒｇｅｔｉｄには、任意のＩＤ（オブジェクトまたはノードのＩＤ）が設定される。Ｓｔａｔｕｓには、参照結果、即ち参照が成功したか或いは失敗したかを示すステータス情報が設定される。ここでは、Ｓｔａｔｕｓ＝“ＬＯＯＫＵＰ＿ＲＥＡＣＨＥＤ”の場合に成功を示し、Ｓｔａｔｕｓ＝“ＬＯＯＫＵＰ＿ＮＯＰＡＴＨ”の場合に失敗（つまり経路無し）を示す。
【０１２９】
Ｔａｒｇｅｔ．Ｓｕｃｃｅｓｓｏｒ．ｉｄには、Ｔａｒｇｅｔｉｄに最も近いノードＩＤを持つノードのノードＩＤが設定される。但し、失敗の場合、Ｔａｒｇｅｔ．Ｓｕｃｃｅｓｓｏｒ．ｉｄはＮＵＬＬに設定される。Ｔａｒｇｅｔ．Ｓｕｃｃｅｓｓｏｒ．ａｄｄｒには、Ｔａｒｇｅｔｉｄに最も近いノードＩＤを持つノードのアドレス（ＩＰアドレス）が設定される。但し、失敗の場合、Ｔａｒｇｅｔ．Ｓｕｃｃｅｓｓｏｒ．ａｄｄｒは、ＮＵＬＬに設定される。
【０１３０】
前述のノードＩｎｔｒｏｄｕｃｅｒでの参照処理の場合、ノードＮｏｄｅ、Ｔａｒｇｅｔｉｄ、Ｔａｒｇｅｔ．Ｓｕｃｃｅｓｓｏｒ．ｉｄ及びＴａｒｇｅｔ．Ｓｕｃｃｅｓｓｏｒ．ａｄｄｒは、それぞれノードＩｎｔｒｏｄｕｃｅｒ、Ｊｏｉｎｅｒ．ｉｄ、Ｓｕｃｃｅｓｓｏｒ．ｉｄ及びＳｕｃｃｅｓｓｏｒ．ａｄｄｒに相当する。
【０１３１】
さて、Ｎｏｄｅ（の探索部２９）は、入力されたＴａｒｇｅｔｉｄに対して当該ノードＮｏｄｅ自身が最も近いノードＩＤを持つかを判定する（ステップＳ５１）。即ちノードＮｏｄｅは、Ｔａｒｇｅｔｉｄに対して自身のノードＩＤ（つまりＮｏｄｅ．ｉｄ）が最も近いかを判定する。
【０１３２】
ステップＳ５１の判定がＹｅｓの場合、ノードＮｏｄｅ（の探索部２９）は、参照処理の結果を示す出力Ｔａｒｇｅｔ．Ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝として、自身のノードＩＤ及びアドレス、即ちＮｏｄｅ．｛ｉｄ，ａｄｄｒ｝を設定すると共に、出力Ｓｔａｔｕｓとして成功を示す“ＬＯＯＫＵＰ＿ＲＥＡＣＨＥＤ”を設定する（ステップＳ５２）。この場合、ノードＮｏｄｅ（の探索部２９）は、目的ノードに到達したものとして参照処理を完了する。
【０１３３】
一方、ステップＳ５１の判定がＮｏの場合、ノードＮｏｄｅ（の探索部２９）は、入力されたＴａｒｇｅｔｉｄに対してｐｒｅｄｅｃｅｓｓｏｒとなるノード（つまりＴａｒｇｅｔｉｄに対して最も遠いノードＩＤを持つノード）ＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒを探索する（ステップＳ５３）。
【０１３４】
ステップＳ５３での探索は、ノードＮｏｄｅ（の探索部２９）が、当該ノードＮｏｄｅのスキップテーブル５３-t(N)のショートカットパスの中から、Ｔａｒｇｅｔｉｄを超えない範囲でリング上で最も遠いｓｕｃｃｅｓｓｏｒ．ｉｄを示すショートカットパスを選択し、このショートカットパスのリンク先のノードに問い合わせ（つまりＴａｒｇｅｔｉｄに対してｐｒｅｄｅｃｅｓｓｏｒとなるノードＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒの問い合わせ）を転送することで行われる（ステップＳ５３０）。この探索の手法は、前記非特許文献５、６に記載されている。ここで選択されたショートカットパスの示すｓｕｃｃｅｓｓｏｒ．ｉｄが、スキップテーブル５３-t(N)の第ｘエントリｓｋｉｐ［ｘ］のｓｕｃｃｅｓｓｏｒ．ｉｄ（つまり、ｓｋｉｐ［ｘ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）であるものとする。
【０１３５】
本実施形態において非特許文献５、６に記載の探索手法と異なる点は、ＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒを探索する過程において、ノードＮｏｄｅ（の探索部２９）が問い合わせ先のノードに対して、Ｔａｒｇｅｔｉｄだけでなく、使用されたショートカットパスの情報をも転送することにある。ここでは、使用されたショートカットパスの情報として、スキップテーブル５３-t(N)の第ｘエントリｓｋｉｐ［ｘ］のｉｎｔｅｒｖａｌstart（つまり、ｓｋｉｐ［ｘ］．ｉｎｔｅｒｖａｌstart）が用いられる。この使用されたショートカットパスの情報ｓｋｉｐ［ｘ］．ｉｎｔｅｒｖａｌstartをノードＮｏｄｅから問い合わせ先のノードに転送することは、ノードＮｏｄｅが、なぜ当該問い合わせ先のノードに問い合わせを行ったかの根拠を示すことに注意すべきである。
【０１３６】
ここで、ＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒの探索のためにノードＮｏｄｅから問い合わせが転送されたノード（問い合わせ先のノード）での処理の手順について、図１１のフローチャートを参照して説明する。
【０１３７】
問い合わせ先のノード（の探索部２９）は、ノードＮｏｄｅ（問い合わせ元）から転送されたショートカットパスの情報ｓｋｉｐ［ｘ］．ｉｎｔｅｒｖａｌstartに対する自身のノードＩＤの近さ（リング上での近さ）と、当該ｓｋｉｐ［ｘ］．ｉｎｔｅｒｖａｌstartに対する自身が管理する他のノードのＩＤの近さとを比較する（ステップＳ５３０ａ）。ここで、問い合わせ先のノードが管理する他のノードのＩＤとは、問い合わせ先のノードが管理する隣接テーブル５２-tの示す先行隣接ノード（ｐｒｅｄｅｃｅｓｓｏｒノード）のノードＩＤ（ｐｒｅｄｅｃｅｓｓｏｒ．ｉｄ）、及びスキップテーブル５３-tの各エントリｓｋｉｐ［ｉ］（ｉ＝｛０...ｍ−１｝）の示すノード（ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ）のノードＩＤ（ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）である。問い合わせ先のノードは、ステップＳ５３０ａの比較の結果から、ｓｋｉｐ［ｘ］．ｉｎｔｅｒｖａｌstartに対して自身のノードＩＤの方が自身が管理する他の全てのノードのノードＩＤよりも近いかにより、ノードＮｏｄｅから転送されたショートカットパスの情報ｓｋｉｐ［ｘ］．ｉｎｔｅｒｖａｌstartが正しいかを判定する（ステップＳ５３０ｂ）。
【０１３８】
問い合わせ先のノード（の探索部２９）は、ｓｋｉｐ［ｘ］．ｉｎｔｅｒｖａｌstartに対して自身のノードＩＤの方が近い場合、ノードＮｏｄｅから転送されたショートカットパスの情報は正しい、つまりノードＮｏｄｅのスキップテーブル５３-t(N)は正しいと判定する（ステップＳ５３０ｃ）。この場合、問い合わせ先のノード（の探索部２９）は、ノードＮｏｄｅが自身に問い合わせたのは正しいと判断する。そこで問い合わせ先のノード（の探索部２９）は、Ｔａｒｇｅｔｉｄに対してｐｒｅｄｅｃｅｓｓｏｒとなるノードＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒを探索し、その結果を問い合わせ元のノード（ノードＮｏｄｅ）に通知（応答）する（ステップＳ５３０ｄ）。
【０１３９】
これに対し、ｓｋｉｐ［ｘ］．ｉｎｔｅｒｖａｌstartに対して自身以外のノードのノードＩＤの方がリング上で近い場合には、問い合わせ先のノード（の探索部２９）は、ノードＮｏｄｅから転送されたショートカットパスの情報は正しくない、つまりノードＮｏｄｅのスキップテーブル５３-t(N)は正しくないと判定する（ステップＳ５３０ｅ）。この場合、問い合わせ先のノード（の探索部２９）は、ノードＮｏｄｅが自身に問い合わせたのは誤っており、スキップテーブル５３-t(N)の更新が必要である旨をノードＮｏｄｅに通知（応答）する（ステップＳ５３０ｆ）。
【０１４０】
ノードＮｏｄｅ（の探索部２９）は、ステップＳ５３０の問い合わせを行うと、当該問い合わせに対する応答を待つ。ノードＮｏｄｅは、問い合わせ先から問い合わせに対する応答が返されると、当該応答を受信する（ステップＳ５３１）。するとノードＮｏｄｅ（の探索部２９）は、受信された応答が、スキップテーブル５３-t(N)の更新が必要である旨を通知しているかを判定する（ステップＳ５３２）。ステップＳ５３２の判定がＹｅｓの場合、ノードＮｏｄｅ（の探索部２９）はノードＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒの探索を一旦中断して、前記選択（転送）されたショートカットパスの正しいリンク先をスキップテーブル５３-t(N)の更新を伴わない方法で探索する（ステップＳ５３３）。このノードＮｏｄｅでの探索は、当該ノードＮｏｄｅが問い合わせ先に転送したショートカットパスの情報ｓｋｉｐ［ｘ］．ｉｎｔｅｒｖａｌstartをＴａｒｇｅｔｉｄとして行われる。
【０１４１】
スキップテーブル５３-t(N)の更新を伴わない方法での探索は、前記非特許文献５、６に記載されている。ここでは、更新がされていないスキップテーブル５３-t(N)を用いて参照が行われる。このため、非特許文献５、６に記載されているように、ｍホップ（ｍはオーバーレイネットワーク１０の空間のビット数）以上での探索要求転送が必要になる場合があるが、参照は成功することに注意されたい。なお、ｍホップ以上での探索要求転送が必要になるのは、非特許文献５、６に記載のＣｈｏｒｄでの非厳密モデルによる更新でも同様である。
【０１４２】
ノードＮｏｄｅ（の探索部２９）は、ステップＳ５３１での探索で、転送されたショートカットパスの正しいリンク先ノードのノードＩＤ及びアドレス、即ちノードＩＤがＴａｒｇｅｔｉｄ（つまりｓｋｉｐ［ｘ］．ｉｎｔｅｒｖａｌstart）に最も近いノードのノードＩＤ及びアドレスを取得する。するとノードＮｏｄｅ（のテーブル管理部２８）は、取得されたノードＩＤ及びアドレスでショートカットパス（ここでは、エントリｓｋｉｐ［ｘ］のうちのｓｋｉｐ［ｘ］．ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ｓｄｄｒ｝）を更新する（ステップＳ５３４）。
【０１４３】
次にノードＮｏｄｅ（の探索部２９）は、更新後のスキップテーブル５３-t(N)を用いて、先ほど中断した参照（つまりノードＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒの探索）を再開する（ステップＳ５３５）。即ちノードＮｏｄｅ（の探索部２９）は、更新後のスキップテーブル５３-t(N)のショートカットパスの中から、Ｔａｒｇｅｔｉｄを超えない範囲でリング上で最も遠いｓｕｃｃｅｓｓｏｒ．ｉｄを示すショートカットパスを選択し、このショートカットパスのリンク先のノードに問い合わせを転送することで、ノードＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒの探索を再開する。このようにして、ノードＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒの探索（ステップＳ５３）が再帰的に行われる。
【０１４４】
次にノードＮｏｄｅ（の探索部２９）は、ノードＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒの探索（ステップＳ５３）を実行した結果、当該ノードＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒに到達できたかを判定する（ステップＳ５４）。
【０１４５】
ステップＳ５４の判定がＮｏの場合、ノードＮｏｄｅ（の探索部２９）は、参照処理の結果を示す出力Ｔａｒｇｅｔ．Ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝として、ＮＵＬＬを設定すると共に、出力Ｓｔａｔｕｓとして失敗を示す“ＬＯＯＫＵＰ＿ＮＯＰＡＴＨ”を設定する（ステップＳ５５）。この場合、ノードＮｏｄｅ（の探索部２９）は、目的ノードに到達できなかったもの（経路無し）として参照処理を完了する。
【０１４６】
一方、ステップＳ５４の判定がＹｅｓの場合、ノードＮｏｄｅ（の探索部２９）は、探索されたノードＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒに対して、当該ノードＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒのｓｕｃｃｅｓｓｏｒノードであるノードＴａｒｇｅｔＳｕｃｃｅｓｓｏｒを問い合わせる（ステップＳ５６）。
【０１４７】
ノードＮｏｄｅ（の探索部２９）は、ステップＳ５６の問い合わせの結果、ノードＴａｒｇｅｔＳｕｃｃｅｓｓｏｒのノードＩＤ及びアドレス（ＴａｒｇｅｔＳｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝）を取得する。するとノードＮｏｄｅ（のテーブル管理部２８）は、ノードＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒ及びノードＴａｒｇｅｔＳｕｃｃｅｓｓｏｒ各々のノードＩＤ及びアドレスを用いて、自身のスキップテーブル５３-t(N)のショートカットパスを更新する（ステップＳ５７）。即ち、ノードＮｏｄｅ（のテーブル管理部２８）は、スキップテーブル５３-t(N)の各エントリＮｏｄｅ．ｓｋｉｐ［ｉ］（ｉ＝｛０...ｍ−１｝）のｉｎｔｅｒｖａｌstart（つまりＮｏｄｅ．Ｎｏｄｅ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstart）に対して、ノードＮｏｄｅ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒのノードＩＤ（Ｎｏｄｅ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ）よりもノードＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒまたはノードＴａｒｇｅｔＳｕｃｃｅｓｓｏｒのノードＩＤ（ＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒ．ｉｄまたはＴａｒｇｅｔＳｕｃｃｅｓｓｏｒ．ｉｄ）の方がリング上で近い場合に、そのＮｏｄｅ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝を、ＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒ．ｉｄまたはＴａｒｇｅｔＳｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝に更新する。ここでは、Ｎｏｄｅ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄ及びＮｏｄｅ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ａｄｄｒが、ＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒ．ｉｄ及びＴａｒｇｅｔＳｕｃｃｅｓｓｏｒ．ｉｄのうちＮｏｄｅ．Ｎｏｄｅ．ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartに最も近いｉｄ（ノードＩＤ）及び当該ｉｄを持つノードのアドレスに更新される。
【０１４８】
次にノードＮｏｄｅ（の探索部２９）は、出力Ｔａｒｇｅｔ．Ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝として、ノードＴａｒｇｅｔＳｕｃｃｅｓｓｏｒのノードＩＤ及びアドレス（ＴａｒｇｅｔＳｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝）を設定すると共に、出力Ｓｔａｔｕｓとして、成功を示す“ＬＯＯＫＵＰ＿ＲＥＡＣＨＥＤ”を設定する（ステップＳ５８）。この場合、ノードＮｏｄｅは、目的ノードに到達したものとして参照処理を完了する。
【０１４９】
このように、本実施形態においてノードＮｏｄｅは、ＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒを探索する過程において、問い合わせ先のノードに対して使用されたショートカットパスの情報ｓｋｉｐ［ｘ］．ｉｎｔｅｒｖａｌstartを転送（通知）することで、当該ショートカットパスの情報が正しくないか、つまりノードＮｏｄｅのスキップテーブル５３-t(N)の更新が必要であるかを問い合わせ先のノードで判定させるようにしている。もし、スキップテーブル５３-t(N)の更新が必要であると問い合わせ先のノードで判定されたならば、その旨が問い合わせ先からノードＮｏｄｅに通知されるため、当該ノードＮｏｄｅは、ショートカットパスの正しいリンク先をスキップテーブル５３-t(N)の更新を伴わない方法で探索することにより、当該スキップテーブル５３-t(N)（ショートカットパスの正しいリンク先）を更新することができる。
【０１５０】
つまり本実施形態においては、ノードのオーバーレイネットワーク１０への参加時にスキップテーブル５３-tを初期化（更新）せずに、当該ノードでの参照処理時にスキップテーブル５３-tを更新するようにしている。同様に本実施形態では、ノードのオーバーレイネットワーク１０からの離脱時にもスキップテーブル５３-tを初期化（更新）しないようにしている。
【０１５１】
これにより本実施形態においては、次のような効果
１）ノードのオーバーレイネットワーク１０へ／からの参加／離脱時に、スキップテーブル５３-tを更新しないため、ノードの参加／離脱に時間がかからない
２）Ｔａｒｇｅｔｉｄに最も近いノードＩＤを持つノードのノードＩＤ及びアドレス（Ｔａｒｇｅｔ．Ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝）を取得するための参照処理の過程でスキップテーブル５３-tが更新されるため、無駄な更新処理は発生せず、しかも更新が必要なときに直ちに更新が行われる
を得ることができる。
【０１５２】
本実施形態におけるオーバーレイネットワークシステムは、例えば、信頼性と性能の弱点となる集中制御点（メタデータサーバ）のない大規模広域分散ストレージシステムに応用することが可能である。
【０１５３】
［第１の変形例］
次に上記実施形態の第１の変形例について説明する。  
第１の変形例の特徴は、各ノード２０-t（の探索部２９）が、自身の管理するスキップテーブル５３-tを、任意のノードへのルーティングの過程で行われる更新とは独立に、定期的に更新する点にある。そのため、各ノード２０-tは一定時間をカウントするタイマを有している。ノード２０-t（の探索部２９）は、タイマが予め定められた一定時間をカウントする毎に、スキップテーブル５３-tを更新する。
【０１５４】
以下、ノード２０-t（の探索部２９）によるスキップテーブル定期更新処理について、図１２のフローチャートを参照して説明する。  
ノード２０-tは、タイマを起動する（ステップＳ６１）。そしてノード２０-tは、タイマが一定時間をカウントするのを（つまりタイマのタイムアウトを）監視する（ステップＳ６２）。
【０１５５】
もし、タイマが一定時間をカウントしたならば、ノード２０-tは、スキップテーブル５３-tを定期的に更新するための更新時期（定期更新時期）が到来したと判断する。するとノード２０-tは、ｉ＝０からｉ＝ｍ−１までの各ｉ（ｉ＝｛０...ｍ−１｝）で示される、スキップテーブル５３-t内のｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartについて、参照を実行することにより、参照結果を用いてｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝を更新する（ステップＳ６３）。
【０１５６】
ノード２０-tは、全てのｉについてステップＳ６３を実行したならば、再びタイマを起動して（ステップＳ６１）、タイマが一定時間をカウントするのを監視する（ステップＳ６２）。
【０１５７】
なお、タイマを用いる代わりに、最新の定期更新時刻を示す定期更新時刻情報が保持されるフィールドをスキップテーブル５３-tに追加してもよい。ここではノード２０-tは、上記定期更新時刻情報の示す定期更新時刻から一定時間が経過するのを監視することにより、次の定期更新時期の到来を判定することができる。ノード２０-tは、定期更新時期の到来によりスキップテーブル５３-tを更新すると、当該テーブル５３-tに保持されている定期更新時刻情報を現在の時刻（つまり最新の定期更新時刻）を示すように更新する。
【０１５８】
第１の変形例によれば、各ノード２０-tの管理するスキップテーブル５３-tのエントリ（ショートカットパスエントリ）が定期的に更新される。このため、ＴａｒｇｅｔＰｒｅｄｅｃｅｓｓｏｒの問い合わせ（ルーティング要求）を含む参照処理、つまり更新処理を伴う参照処理が実行される回数の少ないノード２０-tにおいて、スキップテーブル５３-tのエントリが古くなってしまうことを防ぐことができる。
【０１５９】
［第２の変形例］
次に上記実施形態の第２の変形例について説明する。  
第２の変形例の特徴は、各ノード２０-t（の探索部２９）が、自身の管理するスキップテーブル５３-tのエントリｓｋｉｐ［ｉ］（ｉ＝｛０...ｍ−１｝）を、当該エントリｓｋｉｐ［ｉ］の最新の更新時刻から一定時間経過後に更新する点にある。そのため、第２の変形例では、上記実施形態で用いられたスキップテーブル５３-tに代えて、図１３に示すデータ構造のスキップテーブル５３０-tが用いられる。スキップテーブル５３０-tの各エントリｓｋｉｐ［ｉ］は、更新時刻フィールド５３１を含む。この更新時刻フィールド５３１は、最新の更新時刻を示す更新時刻情報を保持するのに用いられる。
【０１６０】
以下、ノード２０-t（の探索部２９）によるスキップテーブル更新処理について、図１４のフローチャートを参照して説明する。  
ノード２０-tは、ｉ＝０からｉ＝ｍ−１までの全てのｉ（ｉ＝｛０...ｍ−１｝）について、以下の処理を繰り返す。
【０１６１】
まずノード２０-tは、スキップテーブル５３-t内のエントリｓｋｉｐ［ｉ］に含まれている更新時刻フィールド５３１を参照する（ステップＳ７１）。次にノード２０-tは、参照された更新時刻フィールド５３１の示す最新の更新時刻（つまり前回の更新時刻）を現在時刻と比較することにより、当該更新時刻から一定時間を経過しているかを判定する（ステップＳ７２）。
【０１６２】
もし、前回の更新時刻から一定時間を経過しているならば、ノード２０-tは、スキップテーブル５３-t内のエントリｓｋｉｐ［ｉ］を更新するための更新時期が到来したと判断する。するとノード２０-tは、エントリｓｋｉｐ［ｉ］内のｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartについて参照を実行することにより、参照結果を用いてｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝を更新する（ステップＳ７３）。このときノード２０-tは、エントリｓｋｉｐ［ｉ］内の更新時刻フィールド５３１に設定されている更新時刻情報を、現在時刻を示すように更新する（ステップＳ７４）。
【０１６３】
ノード２０-tはステップＳ７４を実行するとステップＳ７５に進む。また、前回の更新時刻から一定時間を経過していないならば、ノード２０-tはステップＳ７４をスキップしてステップＳ７５に進む。ステップＳ７５においてノード２０-tは、一定時間待機する。
【０１６４】
ノード２０-tは、以上の処理をｉ＝０からｉ＝ｍ−１までの全てのｉ（ｉ＝｛０...ｍ−１｝）について繰り返す。  
第２の変形例では、図１０Ａ及び１０Ｂのフローチャートに従う参照処理でＮｏｄｅ．ｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．｛ｉｄ，ａｄｄｒ｝の更新が実行される際にも、その更新が行われるエントリ（Ｎｏｄｅ．ｓｋｉｐ［ｉ］）の更新時刻フィールド５３１が更新される。
【０１６５】
第２の変形例によれば、各ノード２０-tの管理するスキップテーブル５３-tのエントリ（ショートカットパスエントリ）が前回の更新時より一定時間後に更新される。更新処理を伴う参照処理が実行される回数の少ないノード２０-tにおいて、スキップテーブル５３-tのエントリが古くなってしまうことを防ぐことができる。
【０１６６】
なお、本発明は、上記実施形態またはその変形例そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態またはその変形例に開示されている複数の構成要素の適宜な組み合わせにより種々の発明を形成できる。例えば、実施形態またはその変形例に示される全構成要素から幾つかの構成要素を削除してもよい。
【図面の簡単な説明】
【０１６７】
【図１】本発明の一実施形態に係るオーバーレイネットワークシステムのシステム構成を示す図。
【図２】図１に示されるノードのハードウェア構成を示すブロック図。
【図３】図１に示されるノードの主として機能構成を示すブロック図。
【図４】図３に示されるノードの構成情報記憶部に格納される構成情報のデータ構造例を示す図。
【図５】ｓｋｉｐ［ｉ］．ｉｎｔｅｒｖａｌstartとｓｋｉｐ［ｉ］．ｓｕｃｃｅｓｓｏｒ．ｉｄとの関係を示す図。
【図６Ａ】同実施形態において新たにオーバーレイネットワークに参加するノードで実行されるテーブル初期化処理の手順を示すフローチャート。
【図６Ｂ】同実施形態において新たにオーバーレイネットワークに参加するノードで実行されるテーブル初期化処理の手順を示すフローチャート。
【図７】同実施形態において新たにオーバーレイネットワークに参加するノードからの接続要求に応じて後続隣接ノードで実行される接続処理の手順を示すフローチャート。
【図８】同実施形態において新たにオーバーレイネットワークに参加するノードからの接続要求に応じて先行隣接ノードで実行される接続処理の手順を示すフローチャート。
【図９】図６Ｂにおけるスキップテーブル初期化処理の手順を示すフローチャート。
【図１０Ａ】同実施形態における参照処理の手順を示すフローチャート。
【図１０Ｂ】同実施形態における参照処理の手順を示すフローチャート。
【図１１】同実施形態におけるノード探索のための問い合わせ先での処理の手順を示すフローチャート。
【図１２】同実施形態の第１の変形例におけるスキップテーブル定期更新処理の手順を示すフローチャート。
【図１３】同実施形態の第２の変形例で適用されるスキップテーブルのデータ構造例を示す図。
【図１４】同実施形態の第２の変形例におけるスキップテーブル更新処理の手順を示すフローチャート。
【図１５】リングを説明するための図。
【図１６】リングの一例を示す図。
【図１７】図１６の例において、それぞれのノードが格納するオブジェクトのオブジェクトＩＤの範囲を示す図。
【符号の説明】
【０１６８】
１０…オーバーレイネットワーク、２０-t，２０-0〜２０-7…ノード、２６…制御部、２７…構成情報記憶部、２８…テーブル管理部、２９…探索部、３０…オブジェクトアクセス部、３２…オブジェクト格納部、４０…クライアント、５０-t，５０-7…構成情報、５１-t，５１-7…ノード情報、５２-t，５２-7…隣接テーブル、５３-t，５３-7，５３０-t…スキップテーブル。
【図１】
0004409604.tif 000002
【図２】
0004409604.tif 000003
【図３】
0004409604.tif 000004
【図４】
0004409604.tif 000005
【図５】
0004409604.tif 000006
【図６Ａ】
0004409604.tif 000007
【図６Ｂ】
0004409604.tif 000008
【図７】
0004409604.tif 000009
【図８】
0004409604.tif 000010
【図９】
0004409604.tif 000011
【図１０Ａ】
0004409604.tif 000012
【図１０Ｂ】
0004409604.tif 000013
【図１１】
0004409604.tif 000014
【図１２】
0004409604.tif 000015
【図１３】
0004409604.tif 000016
【図１４】
0004409604.tif 000017
【図１５】
0004409604.tif 000018
【図１６】
0004409604.tif 000019
【図１７】
0004409604.tif 000020