(57)【要約】  ピアツーピア（Ｐ２Ｐ）システムは、任意の１つの分散ハッシュテーブル（ＤＨＴ）ノードが特定のキーを要求するクエリを受信した場合にクエリされたＤＨＴノードが自身のＤＨＴテーブルと対話して特定のキーを格納するＤＨＴノードを判定し、特定のキーを格納している特定のＤＨＴノードにクエリを１つのネットワークホップで転送するように、各々が各ＤＨＴノードに対する特定のハッシュ範囲を識別する情報を含む完全な分散ＤＨＴハッシュテーブルを有する複数のＤＨＴノードを含むＤＨＴオーバレイネットワークを有するものとして説明される。Ｐ２Ｐシステムは、耐障害性ＤＨＴノードを有効にするブートストラップ機構、複製機構、更新機構及び回復機構を含む１つ以上のデータ関連機構を更に実現できる。
2010519630.tif 000002
【特許請求の範囲】
【請求項１】
ピアツーピア（Ｐ２Ｐ）システムを形成する複数の分散ハッシュテーブル（ＤＨＴ）ノードを有するＤＨＴオーバレイネットワークであって、
各ＤＨＴノードは前記ＤＨＴノードの各々に対する特定のハッシュ範囲を識別する情報を含む完全な分散ＤＨＴハッシュテーブルを有し、
前記ＤＨＴノードのうち任意の１つのＤＨＴノードが特定のキーを要求するクエリを受信した場合に、前記クエリされたＤＨＴノードが自身のＤＨＴテーブルと対話して前記ＤＨＴノードのうち前記特定のキーを格納する１つのＤＨＴノードを判定し、
前記クエリされたＤＨＴノードが前記特定のキーを格納していない場合に、前記クエリされたＤＨＴノードが前記特定のキーを格納している前記特定のＤＨＴノードに前記クエリを１つのネットワークホップで転送する
ことを特徴とするＤＨＴオーバレイネットワーク。
【請求項２】
前記ＤＨＴオーバレイネットワーク及び前記ＤＨＴノードは、各ＤＨＴノードが初めて起動した場合、前記起動するＤＨＴノードが自身の容量を通知するメッセージをブロードキャストし、
前記ＤＨＴオーバレイネットワークがこの時点で動作するＤＨＴノードを有さない場合に、前記起動するＤＨＴノードは、前記ＤＨＴハッシュテーブルの第１の場所が割り当てられるとともに、前記ＤＨＴハッシュテーブルの全てのハッシュ範囲を仮定することと、
前記ＤＨＴオーバレイネットワークがこの時点で１つの動作するＤＨＴノードのみを有する場合に、前記１つの動作するＤＨＴノードは、前記ブロードキャストメッセージを受信すると、前記起動するノードの前記通知された容量を考慮して前記ハッシュ範囲の分割方法を決定するとともに、再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノードに送出することと、
前記ＤＨＴオーバレイネットワークがこの時点で２つ以上の動作するＤＨＴノードを有する場合に、前記ＤＨＴハッシュテーブルの１番目である前記動作するＤＨＴノードは、前記ブロードキャストメッセージを受信すると、前記起動するノード及び前記動作するＤＨＴノードの全ての前記通知された容量を考慮して前記ハッシュ範囲の分割方法を決定するとともに、再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノード及び他の動作するＤＨＴノードに送出することと、
のうち１つを開始するブートストラッピング機構を実現することを特徴とする請求項１記載のＤＨＴオーバレイネットワーク。
【請求項３】
前記動作するノードは、再帰的直接応答ルーティング（ＲＤＤＲ）機能を使用して、前記再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノード及び前記他の動作するＤＨＴノードに送出することを特徴とする請求項２記載のＤＨＴオーバレイネットワーク。
【請求項４】
前記ＤＨＴオーバレイネットワーク及び前記ＤＨＴノードは、前記ＤＨＴノードのうち少なくとも１つのＤＨＴノードが第１のハッシュ範囲に対して主ノードとして動作するとともに、第２のハッシュ範囲に対して複製ノードとして更に動作する複製機構を実現することを特徴とする請求項１記載のＤＨＴオーバレイネットワーク。
【請求項５】
前記ＤＨＴオーバレイネットワーク及び前記ＤＨＴノードは、前記ＤＨＴノードのうち１つのＤＨＴノードがクラッシュした場合、前記クラッシュしたＤＨＴノードに関して認識した前記ＤＨＴノードが、
（１）前記クラッシュしたＤＨＴノードにより先に対応されていた要求が前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルの複製部分を有する前記ＤＨＴノードのうちの１つのＤＨＴノードにより対応されるようにＤＨＴハッシュテーブルを更新し、
（２）前記更新されたＤＨＴハッシュテーブルを残りのＤＨＴノードに再度配信する
ように機能する更新機構を実現することを特徴とする請求項１記載のＤＨＴオーバレイネットワーク。
【請求項６】
前記クラッシュしたＤＨＴノードに関して認識した前記ＤＨＴノードは、トポロジに基づく複製（ＴＲＬ）機能を使用して、前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルの前記複製部分を有する前記ＤＨＴノードのうちの１つのＤＨＴノードを判定し、
前記ＤＨＴノードは、任意の他のＤＨＴノードを調査する必要なく又はスタートアップ時に提供されたデータ以外の任意の余分なデータを受信する必要なく前記ＴＲＬ機能を自律的に実行する
ことを特徴とする請求項５記載のＤＨＴオーバレイネットワーク。
【請求項７】
前記ＤＨＴオーバレイネットワーク及び前記ＤＨＴノードは、クラッシュした前記ＤＨＴノードのうちの１つのＤＨＴノードが復元された場合、前記クラッシュ／復元したＤＨＴノードに対する要求に対応している前記複製ＤＨＴノードが通知され、
（１）前記クラッシュ／復元したＤＨＴノードと関連する全ての受信した書き込み又は削除要求にマークを付与し、
（２）前記復元したＤＨＴノードに関連する複製されたレコードを前記復元したＤＨＴノードに送出し、
（３）前記マークが付与された書き込み又は削除要求の受信に応じて変更されたレコードを前記復元したＤＨＴノードに送信し、
（４）前記復元したＤＨＴノードに関連する次に受信された書き込み又は削除要求を格納して対処せず、
（５）前記復元したＤＨＴノードが現在アクティブであることを示すメッセージを受信し、
（６）前記復元したＤＨＴノードが現在アクティブであることを示すように前記ＤＨＴハッシュテーブルを更新し、
（７）前記復元したＤＨＴノードに関連する前記格納された次に受信された書き込み又は削除要求を前記復元したＤＨＴノードに送出する
ように機能する回復機構を実現することを特徴とする請求項１記載のＤＨＴオーバレイネットワーク。
【請求項８】
ピアツーピア（Ｐ２Ｐ）システムを形成する複数の分散ハッシュテーブル（ＤＨＴ）ノードを有するＤＨＴオーバレイネットワークを構成する方法であって、
各ＤＨＴノードが初めて起動する場合、前記起動するＤＨＴノードに自身の容量を通知するメッセージをブロードキャストするように命令し、
前記ＤＨＴオーバレイネットワークがこの時点で動作するＤＨＴノードを有さない場合に、前記起動するＤＨＴノードに前記ＤＨＴハッシュテーブルの第１の場所を割り当てるとともに、前記起動するＤＨＴノードに前記ＤＨＴハッシュテーブルの全てのハッシュ範囲を仮定させるステップと、
前記ＤＨＴオーバレイネットワークがこの時点で１つの動作するＤＨＴノードのみを有する場合に、前記１つの動作するＤＨＴノードに前記起動するノードの前記通知された容量を考慮して前記ハッシュ範囲の分割方法を決定させるとともに、再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノードに送出させるステップと、
前記ＤＨＴオーバレイネットワークがこの時点で２つ以上の動作するＤＨＴノードを有する場合に、前記ＤＨＴハッシュテーブルの１番目である前記動作するＤＨＴノードに前記起動するノード及び前記動作するＤＨＴノードの全ての前記通知された容量を考慮して前記ハッシュ範囲の分割方法を決定させるとともに、再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノード及び他の動作するＤＨＴノードに送出させるステップと、
のうち１つを開始するブートストラッピング機構を実現するステップを有することを特徴とする方法。
【請求項９】
前記動作するノードは、再帰的直接応答ルーティング（ＲＤＤＲ）機能を使用して、前記再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノード及び前記他の動作するＤＨＴノードに送出するステップを更に含むことを特徴とする請求項８記載の方法。
【請求項１０】
ピアツーピア（Ｐ２Ｐ）システムを形成する複数の分散ハッシュテーブル（ＤＨＴ）ノードを有する構成されたＤＨＴオーバレイネットワークを使用する方法であって、
前記複数のＤＨＴノードのうち１つのＤＨＴノードにおいて特定のキーを要求するクエリを受信するステップと、
前記複数のＤＨＴノードのうち前記特定のキーを格納する１つのＤＨＴノードを判定するために、前記クエリされたＤＨＴノードと関連するＤＨＴテーブルと対話するステップと、
前記特定のキーを格納する前記特定のＤＨＴノードに前記クエリを１つのネットワークホップで転送するステップであって、前記ＤＨＴノードの各々が前記ＤＨＴノードの各々に対する特定のハッシュ範囲を識別する情報を含む同一のＤＨＴハッシュテーブルを有するステップと
を有することを特徴とする方法。
【請求項１１】
前記複数のＤＨＴノードが第１のハッシュ範囲に対して主ノードとして動作するとともに、第２のハッシュ範囲に対して複製ノードとして更に動作する少なくとも１つのＤＨＴノードを有する複製機構を実現するステップを更に含むことを特徴とする請求項１０記載の方法。
【請求項１２】
前記複数のＤＨＴノードのうち１つのＤＨＴノードがクラッシュした場合、前記クラッシュしたＤＨＴノードに関して認識した前記ＤＨＴノードは、
前記クラッシュしたＤＨＴノードにより先に対応されていた要求が前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルにおいて複製部分を有する前記ＤＨＴノードのうちの１つのＤＨＴノードにより対応されるように前記ＤＨＴハッシュテーブルを更新するステップと、
前記更新されたＤＨＴハッシュテーブルを残りのＤＨＴノードに再度配信するステップと
を実現する更新機構を実現するステップを更に含むことを特徴とする請求項１０記載の方法。
【請求項１３】
前記クラッシュしたＤＨＴノードに関して認識した前記ＤＨＴノードは、トポロジに基づく複製（ＴＲＬ）機能を使用して、前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルにおいて前記複製部分を有する前記ＤＨＴノードのうちの前記１つのＤＨＴノードを判定し、
前記ＤＨＴノードは、任意の他のＤＨＴノードを調査する必要なく又はスタートアップ時に提供されたデータ以外の任意の余分なデータを受信する必要なく前記ＴＲＬ機能を自律的に実行する
ことを特徴とする請求項１２記載の方法。
【請求項１４】
前記複数のＤＨＴノードのうちクラッシュした１つのＤＨＴノードが復元された場合、前記クラッシュ／復元したＤＨＴノードに対する要求に対応している前記複製ＤＨＴノードは、
前記クラッシュ／復元したＤＨＴノードに関連する全ての受信した書き込み又は削除要求にマークを付与するステップと、
前記復元したＤＨＴノードに関連する複製されたレコードを前記復元したＤＨＴノードに送出するステップと、
前記マークが付与された書き込み又は削除要求の受信に応答して変更されたレコードを前記復元したＤＨＴノードに送信するステップと、
前記復元したＤＨＴノードに関連する次に受信された書き込み又は削除要求を格納して対処しないステップと、
前記復元したＤＨＴノードが現在アクティブであることを示すメッセージを受信するステップと、
前記復元したＤＨＴノードが現在アクティブであることを示すように前記ＤＨＴハッシュテーブルを更新するステップと、
前記復元したＤＨＴノードに関連する前記格納された次に受信された書き込み又は削除要求を前記復元したＤＨＴノードに送出するステップと
を実現する回復機構を実現するステップを更に含むことを特徴とする請求項１０記載の方法。
【請求項１５】
自身に対する特定のハッシュ範囲を識別する情報を含み、ピアツーピア（Ｐ２Ｐ）システムの分散ハッシュテーブル（ＤＨＴ）オーバレイネットワークの一部である全ての他のＤＨＴノードに対する特定のハッシュ範囲を識別する情報を含むように構成される完全な分散ＤＨＴハッシュテーブルを具備することを特徴とするＤＨＴノード。
【請求項１６】
メッセージがブロードキャストされることを可能にして自身の記憶容量を前記他のＤＨＴノードに通知するブートストラッピング機構を更に具備することを特徴とする請求項１５記載のＤＨＴノード。
【請求項１７】
前記他のＤＨＴノードの全てに対するハッシュ範囲を識別する情報を含む主部分だけでなく、前記他のＤＨＴノードのうち１つ以上のＤＨＴノードに対するハッシュ範囲を識別する情報を含む複製部分も含むように前記ＤＨＴハッシュテーブルを拡張する複製機構を更に具備することを特徴とする請求項１５記載のＤＨＴノード。
【請求項１８】
前記他のＤＨＴノードのうちクラッシュした前記１つのＤＨＴノードについて認識すると、
（１）前記クラッシュしたＤＨＴノードにより先に対応されていた要求が前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルにおいて複製部分を有する前記他のＤＨＴノードのうちの１つのＤＨＴノードにより対応されるように前記ＤＨＴハッシュテーブルを更新し、
（２）前記更新されたＤＨＴハッシュテーブルを残りの他のＤＨＴノードに再度配信する
ように機能する更新機構を更に具備することを特徴とする請求項１５記載のＤＨＴノード。
【請求項１９】
前記更新機構は、トポロジに基づく複製（ＴＲＬ）機能を使用して、前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルにおいて前記複製部分を有する前記他のＤＨＴノードのうちの前記１つのＤＨＴノードを判定することを特徴とする請求項１８記載のＤＨＴノード。
【請求項２０】
クラッシュしたＤＨＴノードが自身を復元しようとしていることを認識すると、
（１）前記クラッシュ／復元したＤＨＴノードに関連する全ての受信した書き込み又は削除要求にマークを付与し、
（２）前記復元したＤＨＴノードに関連する複製されたレコードを前記復元したＤＨＴノードに送出し、
（３）前記マークが付与された書き込み又は削除要求の受信に応答して変更されたレコードを前記復元したＤＨＴノードに送信し、
（４）前記復元したＤＨＴノードに関連する次に受信された書き込み又は削除要求を格納して対処せず、
（５）前記復元したＤＨＴノードが現在アクティブであることを示すメッセージを受信し、
（６）前記復元したＤＨＴノードが現在アクティブであることを示すように前記ＤＨＴハッシュテーブルを更新し、
（７）前記復元したＤＨＴノードに関連する前記格納された次に受信された書き込み又は削除要求を前記復元したＤＨＴノードに送出する
ように機能する回復機構を更に具備することを特徴とする請求項１５記載のＤＨＴノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、整合性のとれた耐障害性分散ハッシュテーブル（ＤＨＴ）オーバレイネットワークを有するピアツーピア（Ｐ２Ｐ）システムに関する。
【背景技術】
【０００２】
Ｐ２Ｐシステムは、各ノード（例えば、ワークステーション、コンピュータ）が同等の又は類似する機能及び役割を有するアーキテクチャを有する。Ｐ２Ｐシステムは、いくつかのノードが他のノードに対応するように割り当てられるクライアント／サーバアーキテクチャとは異なる。過去には、Ｐ２Ｐシステムは、基本的なインターネットルーティング及び１日に何百万もの人がインターネット又は多くのオンラインサービスを介してアクセスする世界的な電子掲示板システムであるユーズネットニュース等のアプリケーションに適用されてきた。より最近では、Ｐ２Ｐシステムは、物理ネットワークに加え、Gnutella、Freenet、Pastry、P-Grid又はDKS等のいわゆるオーバレイネットワークを利用することによりリソースロケーションアプリケーションに適用されている。基本的にそれらの全てのオーバレイネットワークは、データ管理（探索、挿入、更新等）等の種々の分散アプリケーションサービスが実現される物理ネットワークに加え、リソースロケーションサービスを提供する。要望に応じて、それらの分散アプリケーションサービスは、リソースを管理するために物理ネットワークを直接使用できる。しかし、オーバレイネットワークを使用することにより、アプリケーション別識別子空間及びセマンティックルーティングをサポートするという利点が得られ、物理ネットワーク層に組み込むこと及び物理ネットワーク層でサポートすることが非常に困難であるネットワーク保守、認証、信頼等をサポートするような追加の一般的なサービスを提供する可能性が与えられる。従って、オーバレイネットワークの導入（次に詳細に説明する）及びサービスレベルにおける自己管理はＰ２Ｐシステムに対して非常に重要な革新であった。
【０００３】
各オーバレイネットワークは、２つの関数FP: PRI及びFR: RRIを利用するアプリケーション別識別子空間IにP及びRをマッピングすることによりリソースRの集合へのアクセスを可能にするノードPのグループを有する。それらのマッピングにより、アプリケーション別識別子空間I上の近接性計測値を使用してノードPに対するリソースRの関連付けが設定される。任意のノードPから任意のリソースRへのアクセスを可能にするために論理ネットワークが構築される。すなわち、グラフがアプリケーション別識別子空間Iに埋め込まれる。基本的に、特定の各オーバレイネットワークは、以下の６つの重要な設計面に基づいて行なわれる決定により特徴付けられる。
【０００４】
１．識別子空間Iの選択
２．識別子空間IへのリソースR及びノードPのマッピング
３．ノードPによる識別子空間Iの管理
４．グラフ埋め込み（論理ネットワークの構造）
５．ルーティング戦略
６．保守戦略
これらの設計決定を行なう際、オーバレイネットワークと関連付けられる以下の特徴の１つ以上に対処しようとする場合が多い。
【０００５】
効率：ルーティングはオーバレイホップの数を最小（最短の物理的距離）にするのが好ましく、オーバレイネットワークを構成及び保守する帯域幅（メッセージ数及びそれらのサイズを含む）は最小に維持されるのが好ましい。
【０００６】
スケーラビリティ：スケーラビリティの概念は、例えば数的スケーラビリティ等の多くの面を含む。すなわち、大きな性能低下なしで非常に多くの参加ノードが存在できる。
【０００７】
自己組織化：中央制御の欠如及び参加ノードの集合の頻繁な変更は、特定の自己組織化度を必要とする。すなわち、churnが発生する場合、オーバレイネットワークは安定した構成になるように自己再構成するように構成されるのが好ましい。一般に外部からの介入が不可能であるため、この論理的方法は安定化に要求されるものである。
【０００８】
耐障害性：参加ノード及びネットワークリンクはいつでも障害を起こす可能性があるが、全てのリソースは依然として全てのノードからアクセス可能であるのが好ましい。一般に、これはある冗長形式により達成される。基本的に、耐障害性は、オーバレイネットワークの一部が動作を中止した場合でも、オーバレイネットワークが依然として受け入れ可能なサービスを提供できるのが好ましいことを示す。
【０００９】
協働：オーバレイネットワークはノードの協働に依存する。すなわち、ノードは、対話するノードがルーティング、指標情報の交換、サービス品質等に応じて適切に動作することを信頼する必要がある。
【００１０】
今日まで、オーバレイネットワークに対する広範なアルゴリズム、構造及びアーキテクチャが提案され、ネットワーク化、分散システム、データベース、グラフ理論、エージェントシステム、複合システム等の多くの種々のコミュニティからの知識を統合してきた。ＤＨＴオーバレイネットワークは、大規模分散アプリケーションに対する一般的なビルディングブロックとして使用されるように提案された１つのそのようなオーバレイネットワークである。非特許文献１〜６は、従来のＤＨＴオーバレイネットワークを詳細に説明する（これらの文献の内容は、参考として本明細書に取り入れられる）。
【００１１】
従来のＤＨＴオーバレイネットワークの参加ノードの集合が非常に大きく動的であると仮定されるため、参加者の現在の集合のノードの各ビューは、費用がかかり過ぎるため同期されない。その代わり、従来のＤＨＴオーバレイネットワークの方法は、データエントリに対する要求が要求されたデータエントリを管理する役割を果たす特定のノードに到達する前に２つ以上のネットワークホップを必要とすることが多いルーティングオーバレイを単に形成することである。従来のＤＨＴ方式のこの問題については、図１Ａ及び図１Ｂに関して以下に更に詳細に説明する。
【００１２】
図１Ａ（従来技術）を参照すると、図１は、１０個の従来のＤＨＴノードＮ１、Ｎ８．．．Ｎ５６を有するＰ２Ｐシステム１００の一例を示す。ＤＨＴノードＮ１、Ｎ８．．．Ｎ５６の各々は、以下のことを可能にするために使用される別個のＤＨＴハッシュテーブル１０２を有する。すなわち、（１）所定の識別子に対するクエリが、所望の識別子をまたぐ一対のノードを検索するまで後続ポインタを介して所定のトポロジ（この例においては円）の周囲を通過すること及び（２）一対のノードのうち第２のノードが、所望のデータエントリを見つけるためにクエリがマップするノードであることである。この例において、ＤＨＴノードＮ８は、限定された数の範囲のキー値8+20、8+21、8+22．．．8+25（列１０６を参照）をクエリする種々のＤＨＴノードＮ１４、Ｎ２１、Ｎ３２及びＮ４２（列１０４を参照）の参照、アドレス又は識別子を格納するＤＨＴハッシュテーブル１０２を有する。図示されるように、ＤＨＴノードＮ８は、少しの数のＤＨＴノードＮ１４、Ｎ２１、Ｎ３２及びＮ４２のみの参照、アドレス又は識別子を格納するＤＨＴハッシュテーブル１０２を有し、識別子の円上のＤＨＴノードＮ８に近接するＤＨＴノードＮ１４に関して、より遠いＤＨＴノードＮ２１、Ｎ３２及びＮ４２より多くのことを知っている。第２に、ＤＨＴノードＮ８は、全ての可能なキーkの正確な場所を判定するのに十分な情報を含むＤＨＴハッシュテーブル１０２を有していないことが分かる（尚、これらの特定の特徴は、ＤＨＴノードＮ１、Ｎ１４．．．Ｎ５６及びそれぞれのＤＨＴハッシュテーブルにも当てはまる）。
【００１３】
図１Ｂ（従来技術）を参照すると、Ｐ２Ｐシステム１００の一例の別の図が示される。ここで、ＤＨＴノードＮ８は、クエリ１０８（ルックアップキー５４）を受信しており、ＤＨＴハッシュテーブル１０２を使用して、クエリ１０８がＤＨＴノード５６である最終的な宛先により近づくように別のＤＨＴノード４２に転送される必要があると判定する。この例において、ＤＨＴノードＮ８はキー５４の後続を見つけることを要求すると仮定する。キー５４に先行するＤＨＴノードＮ８のＤＨＴハッシュテーブル１０２中の最大エントリはＤＨＴノードＮ４２であるため、ＤＨＴノードＮ８は、ＤＨＴノードＮ４２にクエリ１０８を解決するように要求する（数字「１」を参照）。その結果、ＤＨＴノードＮ４２は、キー５４に先行するＤＨＴハッシュテーブル中の最大エントリ、すなわちＤＨＴノードＮ５１を判定し、ＤＨＴノードＮ４２は、ＤＨＴノード５１にクエリ１０８を解決するように要求する（数字「２」を参照）。次に、ＤＨＴノードＮ５１は、自身のＤＨＴハッシュテーブルをチェック後、自身の後続であるＤＨＴノードＮ５６がキー５４を継承することを発見するため、ＤＨＴノードＮ５６にクエリ１０８を解決するように要求する（数字「３」を参照）。最後に、ＤＨＴノード５６は発信元ＤＨＴノードＮ８に自身のアドレス１１０を返す（数字「４」を参照）。図示されるように、このＤＨＴ要求のルーティングは、ＤＨＴノードＮ８からＤＨＴノードＮ４２、Ｎ５１及びＮ５６までのいくつかのネットワークホップを含んでいた。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】Ion Stoicay他、「Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications」SIGCOMM'01、２００１年８月２７〜３１日、San Diego, California, USA
【非特許文献２】D. Malkhi他、「Viceroy: A scalable and dynamic emulation of the butterfly」Proc. 21st ACM Symposium on Principles of Distributed Computing、２００２年
【非特許文献３】P. Maymounkov他、「Kademlia: A peer-to-peer information system based on the xor metric」Proceedings of International Peer-to-Peer Symposium、２００２年
【非特許文献４】S. Ratnasamy他、「A scalable content addressable network」in Proceedings of ACM SIGCOMM 2001、２００１年
【非特許文献５】Rowstron他、「Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems」Lecture Notes in Computer Science, 第２２１８巻、３２９〜３５０ページ、２００１年
【非特許文献６】Karger, D.他、「Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web」Proceedings of the 29th Annual ACM Symposium on Theory of Computing（El Paso, TX、１９９７年５月）、６５４〜６６３ページ
【発明の概要】
【発明が解決しようとする課題】
【００１５】
クエリ１０８を解決するために利用されるいくつかのネットワークホップは、従来のＤＨＴオーバレイネットワーク１００に関する基本的な問題である。実際には、定常状態モードで動作している従来のＤＨＴオーバレイネットワーク１００において、一般に各ＤＨＴノードは、O(logN)個の他のＤＨＴノードのみに関する情報を維持し、O(logN)個のメッセージ／ホップを介する他のＤＨＴノードへの全てのルックアップを解決する。従って、通信環境等の高信頼環境において使用されるのに更に適するより高速で強力な信頼できるＤＨＴオーバレイネットワークを構築しようとする場合、従来の方法に関連する大量のネットワークホップに関して問題がある。この大量のネットワークホップにより、ノードがネットワーク毎に互いに近接する、すなわち待ち時間が非常に短い専用のセキュリティ上安全な高信頼ネットワーク環境において動作する限定された数の通信ノード（ハードウェア及びソフトウェア）を一般に有する通信環境において性能が低下する可能性がある。従って、例えば通信環境のような高信頼環境においてＤＨＴを実現する場合、従来のＤＨＴオーバレイネットワーク１００に関連する上記問題及び他の問題に対処する必要がある。この要求及び他の要求は、本発明により満たされる。
【課題を解決するための手段】
【００１６】
１つの面において、本発明は、ピアツーピア（Ｐ２Ｐ）システムを形成する複数の分散ハッシュテーブル（ＤＨＴ）ノードを有するＤＨＴオーバレイネットワークを提供する。任意の１つのＤＨＴノードが特定のキーを要求するクエリを受信した場合にクエリされたＤＨＴノードが自身のＤＨＴテーブルと対話してＤＨＴノードのうち特定のキーを格納する１つのＤＨＴノードを判定し、クエリされたＤＨＴノードが特定のキーを格納していない場合にクエリされたＤＨＴノードが特定のキーを格納している特定のＤＨＴノードにクエリを１つのネットワークホップで転送するように、各ＤＨＴノードは各ＤＨＴノードに対する特定のハッシュ範囲を識別する情報を含む完全な分散ＤＨＴハッシュテーブルを有する。Ｐ２Ｐシステムは、１つ以上のデータ関連機構、すなわちブートストラップ機構、複製機構、更新機構及び回復機構を更に含んでもよい。
【００１７】
別の面において、本発明は、Ｐ２Ｐシステムを形成する複数のＤＨＴノードを有するＤＨＴオーバレイネットワークを構成する方法を提供する。方法は、（１）各ＤＨＴノードが初めて起動する場合、起動するＤＨＴノードに自身の容量を通知するメッセージをブロードキャストさせて、（ａ）ＤＨＴオーバレイネットワークがこの時点で動作するＤＨＴノードを有さない場合に、起動するＤＨＴノードにＤＨＴハッシュテーブルの第１の場所を割り当て且つ起動するＤＨＴノードにＤＨＴハッシュテーブルの全てのハッシュ範囲を仮定させるステップと、（ｂ）ＤＨＴオーバレイネットワークがこの時点で１つの動作するＤＨＴノードのみを有する場合に、１つの動作するＤＨＴノードに起動するノードの通知された容量を考慮してハッシュ範囲の分割方法を決定させて且つ再計算されたＤＨＴハッシュテーブルを起動するＤＨＴノードに送出させるステップと、（ｃ）ＤＨＴオーバレイネットワークがこの時点で２つ以上の動作するＤＨＴノードを有する場合に、ＤＨＴハッシュテーブルの１番目である動作するＤＨＴノードに起動するノード及び動作するＤＨＴノードの全ての通知された容量を考慮してハッシュ範囲の分割方法を決定させて且つ再計算されたＤＨＴハッシュテーブルを起動するＤＨＴノード及び他の動作するＤＨＴノードに送出させるステップとのうち１つを開始するブートストラッピング機構を実現するステップを含む。
【００１８】
別の面において、本発明は、Ｐ２Ｐシステムを形成する複数のＤＨＴノードを有する構成されたＤＨＴオーバレイネットワークを使用する方法を提供する。方法は、（１）１つのＤＨＴノードにおいて特定のキーを要求するクエリを受信するステップと、（２）ＤＨＴノードのうち特定のキーを格納する１つのＤＨＴノードを判定するために、クエリされたＤＨＴノードと関連するＤＨＴテーブルと対話するステップと、（３）特定のキーを格納する特定のＤＨＴノードにクエリを１つのネットワークホップで転送するステップであり、各ＤＨＴノードが各ＤＨＴノードに対する特定のハッシュ範囲を識別する情報を含む同一のＤＨＴハッシュテーブルを有するステップとを含む。
【００１９】
更に別の面において、本発明は、自身に対する特定のハッシュ範囲を識別する情報を含み且つＰ２ＰシステムのＤＨＴオーバレイネットワークの一部である全ての他のＤＨＴノードに対する特定のハッシュ範囲を識別する情報を含むように構成される完全な分散ＤＨＴハッシュテーブルを有するＤＨＴノードを提供する。ＤＨＴノードは、１つ以上のデータ関連機構、すなわちブートストラップ機構、複製機構、更新機構及び回復機構を更に実現してもよい。
【００２０】
本発明の追加の面は、以下の詳細な説明、図面及び任意の請求項において部分的に示され、詳細な説明からの部分的な導出、あるいは本発明の実施により理解される。上述の概要の説明及び以下の詳細な説明の双方が説明のための単なる例示であり、開示される本発明を限定するものでないことが理解される。
【図面の簡単な説明】
【００２１】
添付の図面と共に以下の詳細な説明を参照することにより、本発明は更に完全に理解されるだろう。
【図１Ａ】、
【図１Ｂ】ＤＨＴオーバレイネットワークにおいて従来のＤＨＴプロトコルを実現することに関連する１つの問題を説明するのを助長するために使用されるＰ２Ｐシステムの例を示す図である。
【図２】本発明に従って整合性のとれた耐障害性ＤＨＴノードを有効にする１つ以上の新しい機構を実現するＤＨＴオーバレイネットワークを含むＰ２Ｐシステムの一例を示す図である。
【図３Ａ】、
【図３Ｂ】本発明の一実施形態に従って指標範囲管理機構を説明するのを助長するために使用されるＰ２Ｐシステムの例を示す図である。
【図４】本発明の別の実施形態に従ってブートストラップ機構を説明するのを助長するために使用されるＰ２Ｐシステムの一例を示す図である。
【図５】本発明の更に別の実施形態に従って複製機構を説明するのを助長するために使用されるＰ２Ｐシステムの一例を示す図である。
【図６Ａ】、
【図６Ｂ】本発明の更に別の実施形態に従って更新機構を説明するのを助長するために使用されるＰ２Ｐシステムの例を示す図である。
【図７】本発明の更に別の実施形態に従って回復機構を説明するのを助長するために使用される２つのＤＨＴノードを示す図である。
【発明を実施するための形態】
【００２２】
本発明は、整合性のとれた耐障害性ＤＨＴノードＮ１、Ｎ８．．．Ｎ５６を有するように１つ以上の新しい機構２０２、２０４、２０６、２０８及び２１０を実現するＤＨＴオーバレイネットワークを含むＰ２Ｐシステム２００を導入することにより上述の問題及び他の問題に対処する（図２に示すＰ２Ｐシステム２００の一例を参照）。それらの新しい機構２０２、２０４、２０６、２０８及び２１０は、ＤＨＴハッシュテーブル内の指標範囲の分布を改善し且つ整合性のとれたＤＨＴノードＮ１、Ｎ８．．．Ｎ５６を有効にする指標範囲管理機構２０２を含む。この特定の機構２０２を以下に詳細に説明する。これは、
・分散ＤＨＴハッシュテーブル機構２０２
と呼ばれる。
【００２３】
新しい機構２０２、２０４、２０６、２０８及び２１０は、耐障害性ＤＨＴノードＮ１、Ｎ８．．．Ｎ５６を有効にする４つのデータ関連機構２０４、２０６、２０８及び２１０を更に含む。これらの機構２０４、２０６、２０８及び２１０を以下に詳細に説明する。これらは、
・ブートストラップ機構２０４
・複製機構２０６（ＤＨＴデータ修正）
・更新機構２０８（ＤＨＴノードクラッシュ）
・回復機構２１０（ＤＨＴノード復元）
と呼ばれる。尚、データ関連機構２０４、２０６、２０８及び２１０は指標範囲管理機構２０２に関係なく適用可能である。
【００２４】
分散ハッシュテーブル機構２０２
各ＤＨＴノードＮ１、Ｎ８．．．Ｎ５６は、どのＤＨＴノード（列２１４を参照）がどのハッシュ範囲（列２１６を参照）に対応するかを厳密に記述する完全なトポロジを含む完全な分散ＤＨＴハッシュテーブル２１２を有する。特に、各ＤＨＴノードＮ１、Ｎ８．．．Ｎ５６は同一のＤＨＴハッシュテーブル２１２を有する。これに対して、従来の各ＤＨＴノードＮ１、Ｎ８．．．Ｎ５６は「ハッシュ範囲」に関する部分情報を含む異なるＤＨＴハッシュテーブル１０２を有していた（図１Ａ及び図１Ｂを参照）。
【００２５】
図３Ａを参照すると、図３Ａは、本発明の一実施形態に従って、指標範囲管理機構２０２を実現する１０個の従来のＤＨＴノードＮ１、Ｎ８．．．Ｎ５６を有するＰ２Ｐシステム２００の一例を示す。ＤＨＴノードＮ１、Ｎ８．．．Ｎ５６の各々は、所定のハッシュ値を要求するＤＨＴノードＮ１、Ｎ８．．．Ｎ５６に関する直観的知識を有するように、完全な分散ＤＨＴハッシュテーブル２１２を有する（尚、図３ＡはＤＨＴノードＮ８に関連するＤＨＴハッシュテーブル２１２のみを示す）。図３Ｂにおいて、クエリ２１８がＤＨＴノードＮ８に到着してキー５４を要求すると仮定すると、ＤＨＴノードＮ８は、ＤＨＴハッシュテーブル２１２にインタフェースし、51+1〜56の範囲のキーがＤＨＴノード５６に格納されていることを直接認識する。図示されるように、この厳密な情報により、入力要求はＤＨＴノードＮ８（例えば）により所定のハッシュを管理しているＤＨＴノード５６（例えば）に１つのネットワークホップのみで転送可能になり、それにより、要求の対象データに到達するまでに伴う余分なホップがより少なくなる（図１Ａ及び図１Ｂと比較すると）ため性能は向上する。尚、この指標範囲管理機構２０２の動作は、ＤＨＴノード数が既に設定され且つオーバレイネットワークが既に「構築」されて通常動作状態で機能する準備ができていることを前提とする。しかし、ブートストラップ機構２０４に関する以下の説明は、指標範囲管理機構２０２、並びに他の機構２０６、２０８、２１０及び２１２を利用できるＰ２Ｐシステム／ＤＨＴオーバレイネットワークを確立／構築するために使用される１つの方法にすぎない。
【００２６】
ブートストラップ機構２０４
ＤＨＴオーバレイネットワークは、耐障害性ＤＨＴノードＮ１、Ｎ８．．．Ｎ５６を有効にするのを助長するブートストラッピング機構２０４を実現する。一実施形態において、ブートストラッピング機構２０４は以下の３つの異なる要素を考慮して設計された。
【００２７】
１．耐障害性：Ｐ２Ｐシステム２００全体は、保守が行なわれた後最初に又は深刻なクラッシュの後随時、自動的に起動可能にされるのが好ましい。個々のＤＨＴノードＮ１、Ｎ８．．．Ｎ５６は共通ネットワークを共有し、拡散機構（マルチキャスト又はブロードキャストメッセージ）の実行可能性を有効にするために短いネットワーク距離だけ分離されるのが好ましい。
【００２８】
２．特異性なし：Ｐ２Ｐシステム２００の全てのＤＨＴノードＮ１、Ｎ８．．．Ｎ５６は同様であるのが好ましい。これは、Ｐ２Ｐシステム２００の残りのＤＨＴノードと異なる役割を果たすＤＨＴノードが存在しないことを意味する。
【００２９】
３．簡略化：Ｐ２Ｐシステム２００は簡略化を意図して考案された。これは、以下に説明するように、ブートストラップ機構２０４が通常の書き込み動作と実質的に異ならないことを示す。
【００３０】
これらの要素に基づいて、ブートストラッピング機構２０４の一例は以下のように挙動するように設計された。
【００３１】
Ｉ．ＤＨＴノードが起動すると、ＤＨＴノードは自身が有する記憶容量のみを認識する。
【００３２】
II．起動するＤＨＴノードは、ブロードキャストメッセージを送出し、自身の容量を動作するＤＨＴノードに通知する。
【００３３】
ａ．Ｐ２Ｐシステム２００が動作するＤＨＴノードをまだ有さない場合、起動するＤＨＴノードはＤＨＴハッシュテーブル２１２の第１の場所を割り当てられる。更に、起動するＤＨＴノードは、ハッシュ空間の１００％の範囲を仮定する。
【００３４】
ｂ．Ｐ２Ｐシステム２００が動作するＤＨＴノードを１つのみ有する場合、その動作するＤＨＴノードはブロードキャストメッセージを受信し、自身の容量及び起動するＤＨＴノードの容量に従ってＤＨＴテーブル２１２のキー／ハッシュ空間の分割方法を決定する。計算されると、動作するＤＨＴノードは起動するＤＨＴノードに対して更新済みＤＨＴハッシュテーブル２１２により応答する。
【００３５】
ｃ．Ｐ２Ｐシステム２００が２つ以上の動作するＤＨＴノードを有する場合、それらの全ての動作するＤＨＴノードはブロードキャストメッセージを受信するが、ＤＨＴハッシュテーブル２１２の第１の動作するＤＨＴノードのみが主導権を取り、残りの動作するＤＨＴノードは単にブロードキャストメッセージを廃棄する。第１の動作するＤＨＴノードは、新しく起動するＤＨＴノードを含むようにＤＨＴハッシュテーブル２１２を再計算する。それに加えて、第１の動作するＤＨＴノードは、自身の容量、並びに他の動作するＤＨＴノード及び起動するＤＨＴノードの容量に従ってＤＨＴハッシュテーブル２１２のキー／ハッシュ空間の分割方法を決定する。第１の動作するＤＨＴノードは、例えば再帰的直接応答ルーティング（ＲＤＲＲ）機構を使用して、更新済みＤＨＴハッシュテーブル２１２を他の動作するＤＨＴノード及び新しく起動するＤＨＴノードに伝播できる。一実施形態において、ＲＤＤＲ機構は、更新済みＤＨＴハッシュテーブル２１２に基づいて昇順方向に更新済みＤＨＴテーブル２１２を次のＤＨＴノードに再帰的に送出するように機能する（図４を参照）。
【００３６】
更新済みＤＨＴハッシュテーブル２１２が受信されると、起動するＤＨＴノードは「ブートストラップモード」を終了し、この時点で要求の受信を開始できる「動作／通常モード」を開始する。
【００３７】
図４を参照すると、図４は、ＤＨＴノードＮ３２（例えば）が本発明の別の実施形態に従って起動している場合のブートストラップ機構２０４の機能を説明するのを助長するために使用されるＰ２Ｐシステム２００内の４つのＤＨＴノードＮ１、Ｎ８、Ｎ２１及びＮ３２を示す。ステップ「１」において、起動するＤＨＴノードＮ３２が起動すると、そのＤＨＴノードＮ３２は動作するＤＨＴノードＮ１、Ｎ８及びＮ２１（尚、この例においては、簡潔にするためにＤＨＴノードＮ３８、Ｎ４２、Ｎ４８、Ｎ５１及びＮ５６は示さない）にブロードキャストメッセージ４０２（新たな状態及び容量を通知する）を送出する。ステップ「２」において、動作するＤＨＴノードＮ１（ＤＨＴハッシュテーブル２１２の第１のノードである）は、ブロードキャストメッセージ４０２を受信すると、起動するＤＨＴノードＮ３２及び他の動作するＤＨＴノードＮ８及びＮ２１の容量を考慮してＤＨＴハッシュテーブル２１２を更新する役割を有する（尚、ＤＨＴノードＮ８及びＮ２１はブロードキャストメッセージ４０２を廃棄する）。例えば、ＤＨＴノードＮ１、Ｎ８、Ｎ２１及びＮ３２の各々がｋ個のキーの範囲に対して同等の容量を有すると仮定すると、ＤＨＴハッシュテーブル２１２は図４に示すように更新される（元のＤＨＴハッシュテーブル２１２が左側に示され且つ更新済みＤＨＴハッシュテーブル２１２が右側に示される分解図を参照）。ステップ３において、動作するＤＨＴノードＮ１がＤＨＴハッシュテーブル２１２を更新すると、それはリングメンバのＤＨＴノードＮ８、Ｎ２１及びＮ３２にＲＤＤＲ機構を介して再帰的にリダイレクトされる。全てのＤＨＴノードＮ８、Ｎ２１及びＮ３２は、更新済みＤＨＴハッシュテーブル２１２を受信すると、自身の先のＤＨＴハッシュテーブル２１２を更新済みＤＨＴハッシュテーブル２１２に置換する。
【００３８】
尚、Ｐ２Ｐシステム２００へのデータの初期のポピュレートは、ＤＨＴノードに対して書き込み動作を大量に開始する単純なクライアントを実行することにより達成される。このポピュレートは、ＤＨＴハッシュテーブルに書き込まれる初期値をクライアントに供給する外部記憶装置に基づくことが可能である。あるいは、Ｐ２Ｐシステム２００は通常使用している場合に個別の書き込み動作を使用することによりデータをポピュレートされるが、これはＤＨＴノードにデータを供給するために外部記憶装置を使用する時程効率的ではない（尚、Ｐ２Ｐシステム２００のポピュレートは、「構築」ステップの後又は上記例においては最初にＰ２Ｐシステム２００を構成するためにブートストラップ機構２０２が実行された後に実行される）。
【００３９】
複製機構２０６（ＤＨＴデータ修正）
ＤＨＴオーバレイネットワークは、複製機構２０６を更に実現し、データが１つ以上の複製ＤＨＴノードにおいて形式的に複製されることを保証できる。データの形式的な複製を可能にするために、上述のＤＨＴハッシュテーブル２１２は、ハッシュ範囲を処理するＤＨＴノードを見つけるためだけでなくその同一のハッシュ範囲に対する複製を保持するＤＨＴノードを判定するためにも使用される。次に、上述のＰ２Ｐシステム２００を使用して、複製機構２０６に関して詳細に説明する。
【００４０】
図５を参照すると、図５は、本発明の別の実施形態に従って、データが１つ以上の複製ＤＨＴノードにおいて形式的に複製されることを保証する複製機構２０６の機能を説明するのを助長するために使用されるＰ２Ｐシステム２００の一例を示す。この例において、書き込み要求（Ｋ５４）５０２はＤＨＴノードＮ８に到着し、ＤＨＴノードＮ８は、自身のハッシュテーブル２１２と対話し且つキー５４を上書きする要求５０４をＤＨＴノードＮ５６（要求されたキー値を保持している）に転送する。ＤＨＴノードＮ５６は、書き込み要求（Ｋ５４）５０２に対処し、複製機構２０６に従って先行ＤＨＴノードＮ５１に書き込み要求（Ｋ５４）５０２を再転送する（尚、以下に更に詳細に説明するように、書き込み要求（Ｋ５４）５０２は要望に応じて他のＤＨＴノードに転送可能である）。この特定の例において、分散ＤＨＴハッシュテーブル２１２は変更されないが、先行ＤＨＴノード５１（ＤＨＴノードＮ５６と関連付けられる）の場所を特定するために使用される。
【００４１】
先行ＤＨＴノードＮ５１は、書き込み要求（Ｋ５４）５０２を実行すると、ＤＨＴノードＮ５６の複製として効果的に動作する。従って、各ＤＨＴノードＮ１、Ｎ８．．．Ｎ５６は、複製機構２０６を実現すると、別のＤＨＴノードの複製として機能でき、その結果、全てのＤＨＴノードは二重挙動、すなわち（１）キーの範囲に対する主ノード又はアクティブ部分及び（２）主ノードの複製又はパッシブ部分を有する。この例において、ＤＨＴノードＮ５１は、４９〜５１の範囲のキーに対して主ノードとして動作し、５２〜５６の範囲のキーに対して複製として更に動作する。
【００４２】
各Ｐ２Ｐシステム２００の要求を満足するために、各ＤＨＴノードが必要な量の複製を有するように複製機構２０６が繰り返される。従って、任意の所定のＤＨＴノードは、ハッシュ範囲に対する主ノード又はアクティブノードとして動作可能であり、１つ、２つ、３つ又はそれ以上のパッシブ複製を更に有することができる。この例において、複数のパッシブ複製が存在する場合、新しい各複製Ｒ＋１はＤＨＴノード５６として挙動し、先の複製ＲはＤＨＴノード５１として挙動する。ＤＨＴノードに障害が発生した場合、複製チェーンは、ＤＨＴハッシュテーブル２１２から取得され、動作する複製が要求を処理するために見つけられるまでその複製チェーンをたどる。
【００４３】
図５に示す例において、複製ロケーション機能（例えば、トポロジに基づく複製ロケーション（ＴＲＬ）機能）は、この特定に例においては先行ＤＨＴノードである別のＤＨＴノードに対する複製ノードとして動作するＤＨＴノードを判定するために使用された。この場合、ＴＲＬ複製ロケーション機能は、（１）全てのＤＨＴノードが、システムスタートアップ時にＴＲＬ機能を使用することに同意してもよいこと及び（２）ＴＲＬ機能がローカル情報を使用して計算を実行し、事前に設定された情報の使用又はＰ２Ｐシステム２００外で場所が特定される他の特定のノードへの依存を回避することを含むいくつかの特徴を有する。これは、ＤＨＴノードが任意の他のＤＨＴノードを調査する必要なくＴＲＬ機能を自律的に実行できるようにされるか又はスタートアップ時に提供されたデータ以外の任意の余分なデータを受信できるようにされてもよいことを意味する。しかし、書き込み要求が主ＤＨＴノード（又は先の複製ＤＨＴノード）により受信された後にその書き込み要求が再転送されるＤＨＴノードを判定するために、異なるトポロジ又は地理的な計測値が任意の複製ロケーション機能により使用されてもよい。
【００４４】
更新機構２０８（ＤＨＴノードクラッシュ）
ＤＨＴオーバレイネットワークは、ＤＨＴノードがクラッシュした場合に要求が複製ＤＨＴノードにより対応されることを保証する更新機構２０８を更に実現できる。本実施形態において、ＤＨＴノードがクラッシュした場合、ＤＨＴハッシュテーブル２１２が更新され且つ全てのＤＨＴノードに再度配信されるため、クラッシュしたＤＨＴノードにより以前対応された要求はクラッシュしたＤＨＴノードの複製により対処及び対応される。更新機構２０８は、クラッシュしたＤＨＴノードにより要求される動作の種類（読み出し、書き込み等）に関係なく機能できる。
【００４５】
図６Ａを参照すると、図６Ａは、本発明の別の実施形態に従って、ＤＨＴノードがクラッシュした場合に要求が複製により対応されることを保証する更新機構２０８の機能を説明するのを助長するために使用されるＰ２Ｐシステム２００の一例を示す。この例において、ルックアップ／読み出し要求（Ｋ４７）６０２はＤＨＴノードＮ８に到着し、ＤＨＴノードＮ８は、自身のＤＨＴハッシュテーブル２１２（左側）と対話し、キー４７と関連付けられるデータをルックアップするためにその要求をＤＨＴノードＮ４８（要求されたキー値を保持している）に転送する（ステップ「１」を参照）。しかし、ＤＨＴノードＮ４８がクラッシュしているため、ＤＨＴノードＮ８は所定の時間内に有効な応答を得られないか、あるいは同意された肯定応答を受信しない。このような状況下において、ＤＨＴノードＮ８はＴＲＬ機能を適用し、障害があるものとしてＤＨＴノードＮ４８にマークを付与し、所定のトポロジ関係に基づいて対応する複製ＤＨＴノードに読み出し要求６０２を再度送出する（例えばこの例において、このＤＨＴノードは先行ＤＨＴノードＮ４２である）（ステップ「２」を参照）。読み出し要求６０２を複製ＤＨＴノードＮ４２に送出する前に、ＤＨＴノードＮ８はトポロジの動作する全てのＤＨＴノードＮ１、Ｎ１４．．．Ｎ５８にＤＨＴハッシュテーブル２１２に対する変更に関して通知する（ステップ「３」を参照）。この例において、これは、クラッシュしたＤＨＴノードＮ４８のＤＨＴハッシュテーブル２１２における位置が複製ＤＨＴノードＮ４２により置換されることを示す（元のＤＨＴハッシュテーブル２１２が左側に示され且つ更新済みＤＨＴハッシュテーブル２１２が右側に示される分解図を参照）（尚、複製機構２０６により、更新機構２０８が実現可能になる）。
【００４６】
クラッシュしたノードと関連するクエリを複製ＤＨＴノードにリダイレクト（又は直接送出）するようにＤＨＴノードに命令する更新機構２０８は、以下の３つの前提に基づいて設計可能である。
【００４７】
・トポロジがＤＨＴオーバレイネットワークにおいて規定される：これは、ＤＨＴノードの分布から、全てのＤＨＴノードに適用可能な先行又は後続等の基本機能を規定できることを意味する。このように、ＴＲＬ機能は全てのＤＨＴノードにより適用可能である。
【００４８】
・ブロードキャスト／マルチキャスト機構が適用可能である：これは、全てのＤＨＴノードがＰ２Ｐシステム２００の全てのＤＨＴノードに影響を及ぼす特別な制御メッセージを送出可能になることを意味する。それらの制御メッセージは、他の保留中／キュー登録された要求より優先されるのが好ましい。
【００４９】
・ＤＨＴオーバレイネットワークの任意の２つのＤＨＴノード間、例えばＤＨＴノードＡからＤＨＴノードＢに送出される全てのメッセージは、ＤＨＴノードＢからＤＨＴノードＡに送出される確認応答メッセージ（ＡＣＫ）を結果として与えてもよいため、ノードの障害を認識できる。
【００５０】
図６Ｂを参照すると、図６Ｂは、本発明に従って更新機構２０８の機能を説明するのを助長するために使用される３つのＤＨＴノードＡ、Ｂ及びＣを示すシーケンスチャートである。この場合、ＤＨＴノードがクラッシュした場合に従うステップは以下の通りである。
【００５１】
１．ＤＨＴノードＡは、通常の要求（任意の種類の要求）を対応するＤＨＴノードＣに送出する。ＤＨＴノードＣはたまたまクラッシュする。
【００５２】
２．ＤＨＴノードＡは、ある特定の期間後にＤＨＴノードＣから応答をまだ受信していないことを通知した後、ＤＨＴノードＣが故障したことを検出する。このタイムアウト状況は、最大可能遅延を考慮することによりＰ２Ｐシステムにおいてセットアップされる。
【００５３】
３．ＤＨＴノードＡは、ＤＨＴノードＣがクラッシュしたことを認識する最初のノードであるため、ＤＨＴハッシュテーブル２１２を再計算し、ＴＲＬ機能を適用した後にＤＨＴノードＣを複製ＤＨＴノードＢで置換する。
【００５４】
４．新しいＤＨＴハッシュテーブル２１２は、ノードＡから全ての動作するＤＨＴノードにブロードキャストされる。全てのＤＨＴノードは、キュー登録された要求よりブロードキャストメッセージ（制御メッセージ）を優先し、それにより古いＤＨＴハッシュテーブル２１２を新しいＤＨＴハッシュテーブル２１２で迅速に置換することを可能にする。
【００５５】
５．ここで、ＤＨＴノードＡは通常状態に戻り、先に失敗した要求を複製ＤＨＴノードＢに転送する。
【００５６】
回復機構２１０（ＤＨＴノード復元）
クラッシュしたＤＨＴノードが復元されると（その一方で、その複製は要求に応答している）、複製ＤＨＴノード及びクラッシュしたＤＨＴノードの役割を再び交換するための被制御ハンドオーバ処理が存在してもよい。回復機構２１０は、その被制御ハンドオーバ処理を実現するために使用可能である。一例として、ＤＨＴノードＡをクラッシュし且つ現在通常動作モードに戻ろうとしているノードとし、ＤＨＴノードＢをその複製とする。ＤＨＴノードＡが起動した場合、ＤＨＴノードＡは、通常のスタートアップの挙動後に自身の容量をブロードキャストする（尚、Ｐ２Ｐシステムは、「ブートストラッピングモード」ではなく「通常動作モード」であり、これは、ブートストラッピングを調整する役割を果たすＤＨＴノードが存在せず、その代わりに全てのＤＨＴノードが同等に挙動することを意味する）。従って、ＤＨＴノードＡのメッセージに配慮するＤＨＴノードは複製ＤＨＴノードＢである。これは、ＤＨＴノードＡがクラッシュし且つそのようなメッセージを待っているのでメッセージの二重のロードに対する救済を必要としている。これは、スタートアップブロードキャストメッセージ中のＤＨＴノードＡの固有の識別子を認識することにより、回復したことを通知しているＤＨＴノードＡが先にクラッシュした同一の古いＤＨＴノードＡであることをＤＨＴノードＢが認識できるように、ＤＨＴノードが一意に識別される手段（すなわち、固定インターネットプロトコル（ＩＰ）アドレス、媒体アクセス制御（ＭＡＣ）アドレス等）を有することを示す。
【００５７】
図７を参照すると、図７は、本発明に従って回復機構２１０の機能を説明するのを助長するために使用される２つのＤＨＴノードＡ及びＢを示すシーケンスチャートである。この場合、クラッシュしたＤＨＴノードが回復した場合に従うステップは以下の通りである。
【００５８】
１．まず、回復するＤＨＴノードＡは、回復しようとしていることをＤＨＴノードＢに通知する。
【００５９】
２．ＤＨＴノードＢは、全ての入力書き込み又は削除要求（この時点以降）に対するマークの付与を開始するとともに、古いＤＨＴノードＡの全ての複製レコードを回復しているＤＨＴノードＡにバルク送出する（ＤＨＴノードＡがスクラッチから開始していると仮定する）ことにより新しい状況を確認する。
【００６０】
３．ＤＨＴノードＢがＤＨＴノードＡへのバルク転送を終了すると、複製レコードの第１の集合をＤＨＴノードＡに送出する一方で、受信し且つ書き込み／削除動作を実行した結果として、ＤＨＴノードＢはマークが付与されたレコードのみをＤＨＴノードＡに送信する。この第２のリフレッシュ動作は、ステップ２の第１のリフレッシュ動作より非常に短いのが好ましいだろう。
【００６１】
４．この時点で、ＤＨＴノードＢは先にクラッシュしたＤＨＴノードＡに対する入力要求に対処することを停止し、その代わりにそれらの要求をキューに格納する。同時に、ＤＨＴノードＡは、Ｐ２Ｐシステムにブロードキャスト／マルチキャストメッセージを送出し、自身がアクティブであることを示し、分散ＤＨＴハッシュテーブル２１２の以前に複製ＤＨＴノードＢにより処理されていた範囲の集合を管理する。
【００６２】
５．そのメッセージを受信すると、ＤＨＴノードＢは、クエリを再び処理する適切な状態にあるＤＨＴノードＡに対してキューのフラッシュを開始する。
尚、この例は、要求の連続した流れがＰ２Ｐシステム２００、厳密にはアクティブＤＨＴノードＢに到着することを前提とする。
【００６３】
本発明は、離散的な数のＤＨＴノードにわたる指標範囲の分布を改善し、Ｐ２Ｐシステムの常に変化する数の多くの信頼性の低いＤＨＴノードに対して考案された従来のＤＨＴ最新技術とは異なる信頼性のあるデータの複製及び回復を追加することが上述から理解されるべきである。本発明は、主に、参加するＤＨＴノード数が離散的で安定している高信頼環境にＤＨＴを合わせることに重点を置いており、ＤＨＴノードの信頼性及び性能に対する要求は高い。
【００６４】
本発明において、各ＤＨＴノードにおいて見つけられるＤＨＴハッシュテーブルは、「ハッシュ範囲」に関する部分情報を含むのではなく、どのＤＨＴノードがどのハッシュ範囲に対応するかを厳密に記述する完全なトポロジを含む。この修正されたＤＨＴハッシュテーブルにより、各ＤＨＴノードは所定のハッシュ値を要求するＤＨＴノードの直観的知識を有する。この厳密な情報により、入力要求は所定のハッシュを管理するＤＨＴノードに１つのネットワークホップのみで転送可能となり、それにより、要求の対象データに到達するまでに伴うホップがより少なくなるため性能は向上する。
【００６５】
それに加えて、データが形式的にではなく無作為に複製される従来技術の現在の状況を防止するために、複製機構２０６は、複製ＤＨＴノードにデータ修正を自動的に転送し且つＰ２Ｐシステム全体がＤＨＴハッシュテーブルを参照することにより新しい状況に迅速に適応できるようにするために使用されるものとして上述された。ＤＨＴノードがクラッシュした場合、クラッシュしたノードにより先に対応されていた要求が複製ＤＨＴノードにアドレス指定されるように、ＤＨＴハッシュテーブルが更新され且つ全てのＤＨＴノードに再度配信されることを保証するために、更新機構２０８が使用される。
【００６６】
更に本発明は、ＤＨＴノードのクラッシュ後の回復を助長するために使用される回復機構２１０を提示した。上述の回復機構２１０は、データ整合性、すなわちＤＨＴノードが故障して回復している期間にデータが失われないことに重点を置く。これは、処理及び記憶リソースの障害及び復元中に発生したデータに対する変更の同期化を意味する。このように、上述の機構２０２、２０４、２０６及び２０８がデータアクセスに対する中断を防止する一方、回復機構２１０は、クラッシュしたＤＨＴノードが回復し且つ再び機能ＤＨＴノードになった後の状況を復元する処理を提供する。
【００６７】
本発明の複数の実施形態を添付の図面に示し、上記詳細な説明において説明したが、本発明は、開示される実施形態に限定されず、以下の請求の範囲により示され且つ規定される本発明の趣旨の範囲から逸脱せずに多くの再構成、変形及び置換が可能であることが理解されるべきである。
【図１Ａ】
2010519630.tif 000003
【図１Ｂ】
2010519630.tif 000004
【図２】
2010519630.tif 000005
【図３Ａ】
2010519630.tif 000006
【図３Ｂ】
2010519630.tif 000007
【図４】
2010519630.tif 000008
【図５】
2010519630.tif 000009
【図６Ａ】
2010519630.tif 000010
【図６Ｂ】
2010519630.tif 000011
【図７】
2010519630.tif 000012
【手続補正書】
【提出日】平成20年12月22日(2008.12.22)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
【非特許文献１】Ion Stoicay他、「Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications」SIGCOMM'01、２００１年８月２７〜３１日、San Diego, California, USA
【非特許文献２】D. Malkhi他、「Viceroy: A scalable and dynamic emulation of the butterfly」Proc. 21st ACM Symposium on Principles of Distributed Computing、２００２年
【非特許文献３】P. Maymounkov他、「Kademlia: A peer-to-peer information system based on the xor metric」Proceedings of International Peer-to-Peer Symposium、２００２年
【非特許文献４】S. Ratnasamy他、「A scalable content addressable network」in Proceedings of ACM SIGCOMM 2001、２００１年
【非特許文献５】Rowstron他、「Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems」Lecture Notes in Computer Science, 第２２１８巻、３２９〜３５０ページ、２００１年
【非特許文献６】Karger, D.他、「Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web」Proceedings of the 29th Annual ACM Symposium on Theory of Computing（El Paso, TX、１９９７年５月）、６５４〜６６３ページ
【非特許文献７】Leong B他、「Achieving One-Hop DHT Lookup and Strong Stabilization by Passing Tokens」、Networks, 2004, (ICON 2004), Proceedings 12th IEEE International Conference in Singapore, 16-19 November 2004, Piscataway, NJ, USA, IEEE, 16 November 2004.
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
クエリ１０８を解決するために利用されるいくつかのネットワークホップは、従来のＤＨＴオーバレイネットワーク１００に関する基本的な問題である。実際には、定常状態モードで動作している従来のＤＨＴオーバレイネットワーク１００において、一般に各ＤＨＴノードは、O(logN)個の他のＤＨＴノードのみに関する情報を維持し、O(logN)個のメッセージ／ホップを介する他のＤＨＴノードへの全てのルックアップを解決する。従って、通信環境等の高信頼環境において使用されるのに更に適するより高速で強力な信頼できるＤＨＴオーバレイネットワークを構築しようとする場合、従来の方法に関連する大量のネットワークホップに関して問題がある。この大量のネットワークホップにより、ノードがネットワーク毎に互いに近接する、すなわち待ち時間が非常に短い専用のセキュリティ上安全な高信頼ネットワーク環境において動作する限定された数の通信ノード（ハードウェア及びソフトウェア）を一般に有する通信環境において性能が低下する可能性がある。従って、例えば通信環境のような高信頼環境においてＤＨＴを実現する場合、従来のＤＨＴオーバレイネットワーク１００に関連する上記問題及び他の問題に対処する必要がある。この要求及び他の要求は、本発明により満たされる。
非特許文献７は、全てのノードが、ネットワークの変動が過度に大きくない場合に、１ホップのルックアップを実現可能なグローバル・ルックアップ・テーブルを格納する分散ハッシュテーブル（ＤＨＴ）を有することが可能なネットワークを開示している。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
分散ハッシュテーブル（ＤＨＴ）オーバレイネットワーク、方法、及びＤＨＴノードはそれぞれ、独立請求項１、７、及び１３に記載されている。１つの面において、本発明は、ピアツーピア（Ｐ２Ｐ）システムを形成する複数の分散ハッシュテーブル（ＤＨＴ）ノードを有するＤＨＴオーバレイネットワークを提供する。任意の１つのＤＨＴノードが特定のキーを要求するクエリを受信した場合にクエリされたＤＨＴノードが自身のＤＨＴテーブルと対話してＤＨＴノードのうち特定のキーを格納する１つのＤＨＴノードを判定し、クエリされたＤＨＴノードが特定のキーを格納していない場合にクエリされたＤＨＴノードが特定のキーを格納している特定のＤＨＴノードにクエリを１つのネットワークホップで転送するように、各ＤＨＴノードは各ＤＨＴノードに対する特定のハッシュ範囲を識別する情報を含む完全な分散ＤＨＴハッシュテーブルを有する。Ｐ２Ｐシステムは、１つ以上のデータ関連機構、すなわちブートストラップ機構、複製機構、更新機構及び回復機構を更に含んでもよい。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ピアツーピア（Ｐ２Ｐ）システム（２００）を形成する複数の分散ハッシュテーブル（ＤＨＴ）ノード（Ｎ１，Ｎ８．．．Ｎ５６）を有するＤＨＴオーバレイネットワークであって、
各ＤＨＴノードは前記ＤＨＴノードの各々に対する特定のハッシュ範囲を識別する情報（２１４，２１６）を含む完全な分散ＤＨＴハッシュテーブル（２１２）を有し、
前記ＤＨＴノードのうち任意の１つのＤＨＴノードが特定のキーを要求するクエリ（２１８）を受信した場合に、前記クエリされたＤＨＴノードが自身のＤＨＴテーブルと対話して前記ＤＨＴノードのうち前記特定のキー（５４）を格納する１つのＤＨＴノードを判定し、
前記クエリされたＤＨＴノードが前記特定のキーを格納していない場合に、前記クエリされたＤＨＴノードが前記特定のキーを格納している前記特定のＤＨＴノードに前記クエリを１つのネットワークホップで転送し、
前記ＤＨＴオーバレイネットワーク及び前記ＤＨＴノードは、各ＤＨＴノードが初めて起動した場合、前記起動するＤＨＴノード（Ｎ３２）が自身の容量を通知するメッセージ（４０２）をブロードキャストし、
前記ＤＨＴオーバレイネットワークがこの時点で動作するＤＨＴノードを有さない場合に、前記起動するＤＨＴノードは、前記ＤＨＴハッシュテーブルの第１の場所が割り当てられるとともに、前記ＤＨＴハッシュテーブルの全てのハッシュ範囲を仮定することと、
前記ＤＨＴオーバレイネットワークがこの時点でただ１つの動作するＤＨＴノードを有する場合に、前記１つの動作するＤＨＴノードは、前記ブロードキャストメッセージを受信すると、前記起動するノードの前記通知された容量を考慮して前記ハッシュ範囲の分割方法を決定するとともに、再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノードに送出することと、
前記ＤＨＴオーバレイネットワークがこの時点で２つ以上の動作するＤＨＴノード（Ｎ１，Ｎ８，Ｎ２１）を有する場合に、前記ＤＨＴハッシュテーブルの１番目である前記動作するＤＨＴノード（Ｎ１）は、前記ブロードキャストメッセージを受信すると、前記起動するノード及び前記動作するＤＨＴノードの全て（Ｎ８，Ｎ２１）の前記通知された容量を考慮して前記ハッシュ範囲の分割方法を決定するとともに、再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノード及び他の動作するＤＨＴノードに送出することと、
のうち１つを開始するブートストラッピング機構（２０４）を実現する
ことを特徴とするＤＨＴオーバレイネットワーク。
【請求項２】
前記動作するノードは、再帰的直接応答ルーティング（ＲＤＤＲ）機能を使用して、前記再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノード及び前記他の動作するＤＨＴノードに送出することを特徴とする請求項１記載のＤＨＴオーバレイネットワーク。
【請求項３】
前記ＤＨＴオーバレイネットワーク及び前記ＤＨＴノードは、前記ＤＨＴノードのうち少なくとも１つのＤＨＴノードが第１のハッシュ範囲に対して主ノードとして動作するとともに、第２のハッシュ範囲に対して複製ノードとして更に動作する複製機構（２０６）を実現することを特徴とする請求項１記載のＤＨＴオーバレイネットワーク。
【請求項４】
前記ＤＨＴオーバレイネットワーク及び前記ＤＨＴノードは、前記ＤＨＴノードのうち１つのＤＨＴノードがクラッシュした場合、前記クラッシュしたＤＨＴノードに関して認識した前記ＤＨＴノードが、
（１）前記クラッシュしたＤＨＴノードにより先に対応されていた要求が前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルの複製部分を有する前記ＤＨＴノードのうちの１つのＤＨＴノードにより対応されるようにＤＨＴハッシュテーブルを更新し、
（２）前記更新されたＤＨＴハッシュテーブルを残りのＤＨＴノードに再度配信する
ように機能する更新機構（２０８）を実現することを特徴とする請求項１記載のＤＨＴオーバレイネットワーク。
【請求項５】
前記クラッシュしたＤＨＴノードに関して認識した前記ＤＨＴノードは、トポロジに基づく複製（ＴＲＬ）機能を使用して、前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルの前記複製部分を有する前記ＤＨＴノードのうちの１つのＤＨＴノードを判定し、
前記ＤＨＴノードは、任意の他のＤＨＴノードを調査する必要なく又はスタートアップ時に提供されたデータ以外の任意の余分なデータを受信する必要なく前記ＴＲＬ機能を自律的に実行する
ことを特徴とする請求項４記載のＤＨＴオーバレイネットワーク。
【請求項６】
前記ＤＨＴオーバレイネットワーク及び前記ＤＨＴノードは、クラッシュした前記ＤＨＴノードのうちの１つのＤＨＴノードが復元された場合、前記クラッシュ／復元したＤＨＴノードに対する要求に対応している前記複製ＤＨＴノードが通知され、
（１）前記クラッシュ／復元したＤＨＴノードと関連する全ての受信した書き込み又は削除要求にマークを付与し、
（２）前記復元したＤＨＴノードに関連する複製されたレコードを前記復元したＤＨＴノードに送出し、
（３）前記マークが付与された書き込み又は削除要求の受信に応じて変更されたレコードを前記復元したＤＨＴノードに送信し、
（４）前記復元したＤＨＴノードに関連する次に受信された書き込み又は削除要求を格納して対処せず、
（５）前記復元したＤＨＴノードが現在アクティブであることを示すメッセージを受信し、
（６）前記復元したＤＨＴノードが現在アクティブであることを示すように前記ＤＨＴハッシュテーブルを更新し、
（７）前記復元したＤＨＴノードに関連する前記格納された次に受信された書き込み又は削除要求を前記復元したＤＨＴノードに送出する
ように機能する回復機構（２１０）を実現することを特徴とする請求項１記載のＤＨＴオーバレイネットワーク。
【請求項７】
ピアツーピア（Ｐ２Ｐ）システム（２００）を形成する複数の分散ハッシュテーブル（ＤＨＴ）ノード（Ｎ１，Ｎ８．．．Ｎ５６）を有する構成されたＤＨＴオーバレイネットワークを使用する方法であって、
前記ＤＨＴノードの各々は、前記ＤＨＴノードの各々に対する特定のハッシュ範囲を識別する情報（２１４，２１６）を含む完全分散ＤＨＴハッシュテーブル（２１２）を有し、
前記複数のＤＨＴノードのうち１つのＤＨＴノードにおいて特定のキー（５４）を要求するクエリ（２１８）を受信するステップと、
前記複数のＤＨＴノードのうち前記特定のキーを格納する１つのＤＨＴノードを判定するために、前記クエリされたＤＨＴノードと関連するＤＨＴテーブルと対話するステップと、
前記特定のキーを格納する前記特定のＤＨＴノードに前記クエリを１つのネットワークホップで転送するステップと、
各ＤＨＴノードが初めて起動する場合、前記起動するＤＨＴノード（Ｎ３２）に自身の容量を通知するメッセージ（４０２）をブロードキャストするように命令し、
前記ＤＨＴオーバレイネットワークがこの時点で動作するＤＨＴノードを有さない場合に、前記起動するＤＨＴノードに前記ＤＨＴハッシュテーブルの第１の場所を割り当てるとともに、前記起動するＤＨＴノードに前記ＤＨＴハッシュテーブルの全てのハッシュ範囲を仮定させるステップと、
前記ＤＨＴオーバレイネットワークがこの時点でただ１つの動作するＤＨＴノードを有する場合に、前記１つの動作するＤＨＴノードに前記起動するノードの前記通知された容量を考慮して前記ハッシュ範囲の分割方法を決定させるとともに、再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノードに送出させるステップと、
前記ＤＨＴオーバレイネットワークがこの時点で２つ以上の動作するＤＨＴノード（Ｎ１，Ｎ８．．．Ｎ５６）を有する場合に、前記ＤＨＴハッシュテーブルの１番目である前記動作するＤＨＴノード（Ｎ１）に前記起動するノード及び前記動作するＤＨＴノードの全て（Ｎ８，Ｎ２１）の前記通知された容量を考慮して前記ハッシュ範囲の分割方法を決定させるとともに、再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノード及び他の動作するＤＨＴノードに送出させるステップと、
のうち１つを開始するブートストラッピング機構（２０４）を実現するステップと
を有することを特徴とする方法。
【請求項８】
前記動作するノードは、再帰的直接応答ルーティング（ＲＤＤＲ）機能を使用して、前記再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノード及び前記他の動作するＤＨＴノードに送出するステップを更に含むことを特徴とする請求項７記載の方法。
【請求項９】
前記複数のＤＨＴノードが第１のハッシュ範囲に対して主ノードとして動作するとともに、第２のハッシュ範囲に対して複製ノードとして更に動作する少なくとも１つのＤＨＴノードを有する複製機構（２０６）を実現するステップを更に含むことを特徴とする請求項７記載の方法。
【請求項１０】
前記複数のＤＨＴノードのうち１つのＤＨＴノードがクラッシュした場合、前記クラッシュしたＤＨＴノードに関して認識した前記ＤＨＴノードは、
前記クラッシュしたＤＨＴノードにより先に対応されていた要求が前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルにおいて複製部分を有する前記ＤＨＴノードのうちの１つのＤＨＴノードにより対応されるように前記ＤＨＴハッシュテーブルを更新するステップと、
前記更新されたＤＨＴハッシュテーブルを残りのＤＨＴノードに再度配信するステップと
を実現する更新機構（２０８）を実現するステップを更に含むことを特徴とする請求項７記載の方法。
【請求項１１】
前記クラッシュしたＤＨＴノードに関して認識した前記ＤＨＴノードは、トポロジに基づく複製（ＴＲＬ）機能を使用して、前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルにおいて前記複製部分を有する前記ＤＨＴノードのうちの前記１つのＤＨＴノードを判定し、
前記ＤＨＴノードは、任意の他のＤＨＴノードを調査する必要なく又はスタートアップ時に提供されたデータ以外の任意の余分なデータを受信する必要なく前記ＴＲＬ機能を自律的に実行する
ことを特徴とする請求項１０記載の方法。
【請求項１２】
前記複数のＤＨＴノードのうちクラッシュした１つのＤＨＴノードが復元された場合、前記クラッシュ／復元したＤＨＴノードに対する要求に対応している前記複製ＤＨＴノードは、
前記クラッシュ／復元したＤＨＴノードに関連する全ての受信した書き込み又は削除要求にマークを付与するステップと、
前記復元したＤＨＴノードに関連する複製されたレコードを前記復元したＤＨＴノードに送出するステップと、
前記マークが付与された書き込み又は削除要求の受信に応答して変更されたレコードを前記復元したＤＨＴノードに送信するステップと、
前記復元したＤＨＴノードに関連する次に受信された書き込み又は削除要求を格納して対処しないステップと、
前記復元したＤＨＴノードが現在アクティブであることを示すメッセージを受信するステップと、
前記復元したＤＨＴノードが現在アクティブであることを示すように前記ＤＨＴハッシュテーブルを更新するステップと、
前記復元したＤＨＴノードに関連する前記格納された次に受信された書き込み又は削除要求を前記復元したＤＨＴノードに送出するステップと
を実現する回復機構（２１０）を実現するステップを更に含むことを特徴とする請求項７記載の方法。
【請求項１３】
自身に対する特定のハッシュ範囲を識別する情報を含み、ピアツーピア（Ｐ２Ｐ）システム（２００）の分散ハッシュテーブル（ＤＨＴ）オーバレイネットワークの一部である全ての他のＤＨＴノードに対する特定のハッシュ範囲を識別する情報（２１４，２１６）を含むように構成される完全な分散ＤＨＴハッシュテーブル（２１２）と、
メッセージ（４０２）がブロードキャストされることを可能にして自身の記憶容量を前記他のＤＨＴノードに通知するブートストラッピング機構と
を具備することを特徴とするＤＨＴノード（Ｎ１，Ｎ８．．．Ｎ５６）。
【請求項１４】
前記他のＤＨＴノードの全てに対するハッシュ範囲を識別する情報を含む主部分だけでなく、前記他のＤＨＴノードのうち１つ以上のＤＨＴノードに対するハッシュ範囲を識別する情報を含む複製部分も含むように前記ＤＨＴハッシュテーブルを拡張する複製機構（２０６）を更に具備することを特徴とする請求項１３記載のＤＨＴノード。
【請求項１５】
前記他のＤＨＴノードのうちクラッシュした前記１つのＤＨＴノードについて認識すると、
（１）前記クラッシュしたＤＨＴノードにより先に対応されていた要求が前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルにおいて複製部分を有する前記他のＤＨＴノードのうちの１つのＤＨＴノードにより対応されるように前記ＤＨＴハッシュテーブルを更新し、
（２）前記更新されたＤＨＴハッシュテーブルを残りの他のＤＨＴノードに再度配信する
ように機能する更新機構（２０８）を更に具備することを特徴とする請求項１３記載のＤＨＴノード。
【請求項１６】
前記更新機構は、トポロジに基づく複製（ＴＲＬ）機能を使用して、前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルにおいて前記複製部分を有する前記他のＤＨＴノードのうちの前記１つのＤＨＴノードを判定することを特徴とする請求項１５記載のＤＨＴノード。
【請求項１７】
クラッシュしたＤＨＴノードが自身を復元しようとしていることを認識すると、
（１）前記クラッシュ／復元したＤＨＴノードに関連する全ての受信した書き込み又は削除要求にマークを付与し、
（２）前記復元したＤＨＴノードに関連する複製されたレコードを前記復元したＤＨＴノードに送出し、
（３）前記マークが付与された書き込み又は削除要求の受信に応答して変更されたレコードを前記復元したＤＨＴノードに送信し、
（４）前記復元したＤＨＴノードに関連する次に受信された書き込み又は削除要求を格納して対処せず、
（５）前記復元したＤＨＴノードが現在アクティブであることを示すメッセージを受信し、
（６）前記復元したＤＨＴノードが現在アクティブであることを示すように前記ＤＨＴハッシュテーブルを更新し、
（７）前記復元したＤＨＴノードに関連する前記格納された次に受信された書き込み又は削除要求を前記復元したＤＨＴノードに送出する
ように機能する回復機構（２１０）を更に具備することを特徴とする請求項１３記載のＤＨＴノード。
【請求項１８】
当該ＤＨＴノードが前記ＤＨＴオーバレイネットワーク内の最初のＤＨＴノードでないときは、再計算されたＤＨＴハッシュテーブルを受信し、
当該ＤＨＴノードが前記ＤＨＴオーバレイネットワーク内の最初のＤＨＴノードであるときは、再計算されたＤＨＴハッシュテーブルを前記ＤＨＴオーバレイネットワーク内の他のＤＨＴノードに対して提出する
ように構成されることを特徴とする請求項１３に記載のＤＨＴノード。
【手続補正書】
【提出日】平成22年1月21日(2010.1.21)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００３５
【補正方法】変更
【補正の内容】
【００３５】
ｃ．Ｐ２Ｐシステム２００が２つ以上の動作するＤＨＴノードを有する場合、それらの全ての動作するＤＨＴノードはブロードキャストメッセージを受信するが、ＤＨＴハッシュテーブル２１２の第１の動作するＤＨＴノードのみが主導権を取り、残りの動作するＤＨＴノードは単にブロードキャストメッセージを廃棄する。第１の動作するＤＨＴノードは、新しく起動するＤＨＴノードを含むようにＤＨＴハッシュテーブル２１２を再計算する。それに加えて、第１の動作するＤＨＴノードは、自身の容量、並びに他の動作するＤＨＴノード及び起動するＤＨＴノードの容量に従ってＤＨＴハッシュテーブル２１２のキー／ハッシュ空間の分割方法を決定する。第１の動作するＤＨＴノードは、例えば再帰的直接応答ルーティング（ＲＤＲＲ）機構を使用して、更新済みＤＨＴハッシュテーブル２１２を他の動作するＤＨＴノード及び新しく起動するＤＨＴノードに伝播できる。一実施形態において、ＲＤＲＲ機構は、更新済みＤＨＴハッシュテーブル２１２に基づいて昇順方向に更新済みＤＨＴテーブル２１２を次のＤＨＴノードに再帰的に送出するように機能する（図４を参照）。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】変更
【補正の内容】
【００３７】
図４を参照すると、図４は、ＤＨＴノードＮ３２（例えば）が本発明の別の実施形態に従って起動している場合のブートストラップ機構２０４の機能を説明するのを助長するために使用されるＰ２Ｐシステム２００内の４つのＤＨＴノードＮ１、Ｎ８、Ｎ２１及びＮ３２を示す。ステップ「１」において、起動するＤＨＴノードＮ３２が起動すると、そのＤＨＴノードＮ３２は動作するＤＨＴノードＮ１、Ｎ８及びＮ２１（尚、この例においては、簡潔にするためにＤＨＴノードＮ３８、Ｎ４２、Ｎ４８、Ｎ５１及びＮ５６は示さない）にブロードキャストメッセージ４０２（新たな状態及び容量を通知する）を送出する。ステップ「２」において、動作するＤＨＴノードＮ１（ＤＨＴハッシュテーブル２１２の第１のノードである）は、ブロードキャストメッセージ４０２を受信すると、起動するＤＨＴノードＮ３２及び他の動作するＤＨＴノードＮ８及びＮ２１の容量を考慮してＤＨＴハッシュテーブル２１２を更新する役割を有する（尚、ＤＨＴノードＮ８及びＮ２１はブロードキャストメッセージ４０２を廃棄する）。例えば、ＤＨＴノードＮ１、Ｎ８、Ｎ２１及びＮ３２の各々がｋ個のキーの範囲に対して同等の容量を有すると仮定すると、ＤＨＴハッシュテーブル２１２は図４に示すように更新される（元のＤＨＴハッシュテーブル２１２が左側に示され且つ更新済みＤＨＴハッシュテーブル２１２が右側に示される分解図を参照）。ステップ３において、動作するＤＨＴノードＮ１がＤＨＴハッシュテーブル２１２を更新すると、それはリングメンバのＤＨＴノードＮ８、Ｎ２１及びＮ３２にＲＤＲＲ機構を介して再帰的にリダイレクトされる。全てのＤＨＴノードＮ８、Ｎ２１及びＮ３２は、更新済みＤＨＴハッシュテーブル２１２を受信すると、自身の先のＤＨＴハッシュテーブル２１２を更新済みＤＨＴハッシュテーブル２１２に置換する。
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ピアツーピア（Ｐ２Ｐ）システム（２００）を形成する複数の分散ハッシュテーブル（ＤＨＴ）ノード（Ｎ１，Ｎ８．．．Ｎ５６）を有するＤＨＴオーバレイネットワークであって、
各ＤＨＴノードは前記ＤＨＴノードの各々に対する特定のハッシュ範囲を識別する情報（２１４，２１６）を含む完全な分散ＤＨＴハッシュテーブル（２１２）を有し、
前記ＤＨＴノードのうち任意の１つのＤＨＴノードが特定のキーを要求するクエリ（２１８）を受信した場合に、前記クエリされたＤＨＴノードが自身のＤＨＴテーブルと対話して前記ＤＨＴノードのうち前記特定のキー（５４）を格納する１つのＤＨＴノードを判定し、
前記クエリされたＤＨＴノードが前記特定のキーを格納していない場合に、前記クエリされたＤＨＴノードが前記特定のキーを格納している前記特定のＤＨＴノードに前記クエリを１つのネットワークホップで転送し、
前記ＤＨＴオーバレイネットワーク及び前記ＤＨＴノードは、各ＤＨＴノードが初めて起動した場合、前記起動するＤＨＴノード（Ｎ３２）が自身の容量を通知するメッセージ（４０２）をブロードキャストし、
前記ＤＨＴオーバレイネットワークがこの時点で動作するＤＨＴノードを有さない場合に、前記起動するＤＨＴノードは、前記ＤＨＴハッシュテーブルの第１の場所が割り当てられるとともに、前記ＤＨＴハッシュテーブルの全てのハッシュ範囲を仮定することと、
前記ＤＨＴオーバレイネットワークがこの時点でただ１つの動作するＤＨＴノードを有する場合に、前記１つの動作するＤＨＴノードは、前記ブロードキャストメッセージを受信すると、前記起動するノードの前記通知された容量を考慮して前記ハッシュ範囲の分割方法を決定するとともに、再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノードに送出することと、
前記ＤＨＴオーバレイネットワークがこの時点で２つ以上の動作するＤＨＴノード（Ｎ１，Ｎ８，Ｎ２１）を有する場合に、前記ＤＨＴハッシュテーブルの１番目である前記動作するＤＨＴノード（Ｎ１）は、前記ブロードキャストメッセージを受信すると、前記起動するノード及び前記動作するＤＨＴノードの全て（Ｎ８，Ｎ２１）の前記通知された容量を考慮して前記ハッシュ範囲の分割方法を決定するとともに、再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノード及び他の動作するＤＨＴノードに送出することと、
のうち１つを開始するブートストラッピング機構（２０４）を実現する
ことを特徴とするＤＨＴオーバレイネットワーク。
【請求項２】
前記動作するノードは、再帰的直接応答ルーティング（ＲＤＲＲ）機能を使用して、前記再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノード及び前記他の動作するＤＨＴノードに送出することを特徴とする請求項１記載のＤＨＴオーバレイネットワーク。
【請求項３】
前記ＤＨＴオーバレイネットワーク及び前記ＤＨＴノードは、前記ＤＨＴノードのうち少なくとも１つのＤＨＴノードが第１のハッシュ範囲に対して主ノードとして動作するとともに、第２のハッシュ範囲に対して複製ノードとして更に動作する複製機構（２０６）を実現することを特徴とする請求項１記載のＤＨＴオーバレイネットワーク。
【請求項４】
前記ＤＨＴオーバレイネットワーク及び前記ＤＨＴノードは、前記ＤＨＴノードのうち１つのＤＨＴノードがクラッシュした場合、前記クラッシュしたＤＨＴノードに関して認識した前記ＤＨＴノードが、
（１）前記クラッシュしたＤＨＴノードにより先に対応されていた要求が前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルの複製部分を有する前記ＤＨＴノードのうちの１つのＤＨＴノードにより対応されるようにＤＨＴハッシュテーブルを更新し、
（２）前記更新されたＤＨＴハッシュテーブルを残りのＤＨＴノードに再度配信する
ように機能する更新機構（２０８）を実現することを特徴とする請求項１記載のＤＨＴオーバレイネットワーク。
【請求項５】
前記クラッシュしたＤＨＴノードに関して認識した前記ＤＨＴノードは、トポロジに基づく複製（ＴＲＬ）機能を使用して、前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルの前記複製部分を有する前記ＤＨＴノードのうちの１つのＤＨＴノードを判定し、
前記ＤＨＴノードは、任意の他のＤＨＴノードを調査する必要なく又はスタートアップ時に提供されたデータ以外の任意の余分なデータを受信する必要なく前記ＴＲＬ機能を自律的に実行する
ことを特徴とする請求項４記載のＤＨＴオーバレイネットワーク。
【請求項６】
前記ＤＨＴオーバレイネットワーク及び前記ＤＨＴノードは、クラッシュした前記ＤＨＴノードのうちの１つのＤＨＴノードが復元された場合、前記クラッシュ／復元したＤＨＴノードに対する要求に対応している前記複製ＤＨＴノードが通知され、
（１）前記クラッシュ／復元したＤＨＴノードと関連する全ての受信した書き込み又は削除要求にマークを付与し、
（２）前記復元したＤＨＴノードに関連する複製されたレコードを前記復元したＤＨＴノードに送出し、
（３）前記マークが付与された書き込み又は削除要求の受信に応じて変更されたレコードを前記復元したＤＨＴノードに送信し、
（４）前記復元したＤＨＴノードに関連する次に受信された書き込み又は削除要求を格納して対処せず、
（５）前記復元したＤＨＴノードが現在アクティブであることを示すメッセージを受信し、
（６）前記復元したＤＨＴノードが現在アクティブであることを示すように前記ＤＨＴハッシュテーブルを更新し、
（７）前記復元したＤＨＴノードに関連する前記格納された次に受信された書き込み又は削除要求を前記復元したＤＨＴノードに送出する
ように機能する回復機構（２１０）を実現することを特徴とする請求項１記載のＤＨＴオーバレイネットワーク。
【請求項７】
ピアツーピア（Ｐ２Ｐ）システム（２００）を形成する複数の分散ハッシュテーブル（ＤＨＴ）ノード（Ｎ１，Ｎ８．．．Ｎ５６）を有する構成されたＤＨＴオーバレイネットワークを使用する方法であって、
前記ＤＨＴノードの各々は、前記ＤＨＴノードの各々に対する特定のハッシュ範囲を識別する情報（２１４，２１６）を含む完全分散ＤＨＴハッシュテーブル（２１２）を有し、
前記複数のＤＨＴノードのうち１つのＤＨＴノードにおいて特定のキー（５４）を要求するクエリ（２１８）を受信するステップと、
前記複数のＤＨＴノードのうち前記特定のキーを格納する１つのＤＨＴノードを判定するために、前記クエリされたＤＨＴノードと関連するＤＨＴテーブルと対話するステップと、
前記特定のキーを格納する前記特定のＤＨＴノードに前記クエリを１つのネットワークホップで転送するステップと、
各ＤＨＴノードが初めて起動する場合、前記起動するＤＨＴノード（Ｎ３２）に自身の容量を通知するメッセージ（４０２）をブロードキャストするように命令し、
前記ＤＨＴオーバレイネットワークがこの時点で動作するＤＨＴノードを有さない場合に、前記起動するＤＨＴノードに前記ＤＨＴハッシュテーブルの第１の場所を割り当てるとともに、前記起動するＤＨＴノードに前記ＤＨＴハッシュテーブルの全てのハッシュ範囲を仮定させるステップと、
前記ＤＨＴオーバレイネットワークがこの時点でただ１つの動作するＤＨＴノードを有する場合に、前記１つの動作するＤＨＴノードに前記起動するノードの前記通知された容量を考慮して前記ハッシュ範囲の分割方法を決定させるとともに、再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノードに送出させるステップと、
前記ＤＨＴオーバレイネットワークがこの時点で２つ以上の動作するＤＨＴノード（Ｎ１，Ｎ８．．．Ｎ５６）を有する場合に、前記ＤＨＴハッシュテーブルの１番目である前記動作するＤＨＴノード（Ｎ１）に前記起動するノード及び前記動作するＤＨＴノードの全て（Ｎ８，Ｎ２１）の前記通知された容量を考慮して前記ハッシュ範囲の分割方法を決定させるとともに、再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノード及び他の動作するＤＨＴノードに送出させるステップと、
のうち１つを開始するブートストラッピング機構（２０４）を実現するステップと
を有することを特徴とする方法。
【請求項８】
前記動作するノードは、再帰的直接応答ルーティング（ＲＤＲＲ）機能を使用して、前記再計算されたＤＨＴハッシュテーブルを前記起動するＤＨＴノード及び前記他の動作するＤＨＴノードに送出するステップを更に含むことを特徴とする請求項７記載の方法。
【請求項９】
前記複数のＤＨＴノードが第１のハッシュ範囲に対して主ノードとして動作するとともに、第２のハッシュ範囲に対して複製ノードとして更に動作する少なくとも１つのＤＨＴノードを有する複製機構（２０６）を実現するステップを更に含むことを特徴とする請求項７記載の方法。
【請求項１０】
前記複数のＤＨＴノードのうち１つのＤＨＴノードがクラッシュした場合、前記クラッシュしたＤＨＴノードに関して認識した前記ＤＨＴノードは、
前記クラッシュしたＤＨＴノードにより先に対応されていた要求が前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルにおいて複製部分を有する前記ＤＨＴノードのうちの１つのＤＨＴノードにより対応されるように前記ＤＨＴハッシュテーブルを更新するステップと、
前記更新されたＤＨＴハッシュテーブルを残りのＤＨＴノードに再度配信するステップと
を実現する更新機構（２０８）を実現するステップを更に含むことを特徴とする請求項７記載の方法。
【請求項１１】
前記クラッシュしたＤＨＴノードに関して認識した前記ＤＨＴノードは、トポロジに基づく複製（ＴＲＬ）機能を使用して、前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルにおいて前記複製部分を有する前記ＤＨＴノードのうちの前記１つのＤＨＴノードを判定し、
前記ＤＨＴノードは、任意の他のＤＨＴノードを調査する必要なく又はスタートアップ時に提供されたデータ以外の任意の余分なデータを受信する必要なく前記ＴＲＬ機能を自律的に実行する
ことを特徴とする請求項１０記載の方法。
【請求項１２】
前記複数のＤＨＴノードのうちクラッシュした１つのＤＨＴノードが復元された場合、前記クラッシュ／復元したＤＨＴノードに対する要求に対応している前記複製ＤＨＴノードは、
前記クラッシュ／復元したＤＨＴノードに関連する全ての受信した書き込み又は削除要求にマークを付与するステップと、
前記復元したＤＨＴノードに関連する複製されたレコードを前記復元したＤＨＴノードに送出するステップと、
前記マークが付与された書き込み又は削除要求の受信に応答して変更されたレコードを前記復元したＤＨＴノードに送信するステップと、
前記復元したＤＨＴノードに関連する次に受信された書き込み又は削除要求を格納して対処しないステップと、
前記復元したＤＨＴノードが現在アクティブであることを示すメッセージを受信するステップと、
前記復元したＤＨＴノードが現在アクティブであることを示すように前記ＤＨＴハッシュテーブルを更新するステップと、
前記復元したＤＨＴノードに関連する前記格納された次に受信された書き込み又は削除要求を前記復元したＤＨＴノードに送出するステップと
を実現する回復機構（２１０）を実現するステップを更に含むことを特徴とする請求項７記載の方法。
【請求項１３】
自身に対する特定のハッシュ範囲を識別する情報を含み、ピアツーピア（Ｐ２Ｐ）システム（２００）の分散ハッシュテーブル（ＤＨＴ）オーバレイネットワークの一部である全ての他のＤＨＴノードに対する特定のハッシュ範囲を識別する情報（２１４，２１６）を含むように構成される完全な分散ＤＨＴハッシュテーブル（２１２）と、
メッセージ（４０２）がブロードキャストされることを可能にして自身の記憶容量を前記他のＤＨＴノードに通知するブートストラッピング機構と
を具備することを特徴とするＤＨＴノード（Ｎ１，Ｎ８．．．Ｎ５６）。
【請求項１４】
前記他のＤＨＴノードの全てに対するハッシュ範囲を識別する情報を含む主部分だけでなく、前記他のＤＨＴノードのうち１つ以上のＤＨＴノードに対するハッシュ範囲を識別する情報を含む複製部分も含むように前記ＤＨＴハッシュテーブルを拡張する複製機構（２０６）を更に具備することを特徴とする請求項１３記載のＤＨＴノード。
【請求項１５】
前記他のＤＨＴノードのうちクラッシュした前記１つのＤＨＴノードについて認識すると、
（１）前記クラッシュしたＤＨＴノードにより先に対応されていた要求が前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルにおいて複製部分を有する前記他のＤＨＴノードのうちの１つのＤＨＴノードにより対応されるように前記ＤＨＴハッシュテーブルを更新し、
（２）前記更新されたＤＨＴハッシュテーブルを残りの他のＤＨＴノードに再度配信する
ように機能する更新機構（２０８）を更に具備することを特徴とする請求項１３記載のＤＨＴノード。
【請求項１６】
前記更新機構は、トポロジに基づく複製（ＴＲＬ）機能を使用して、前記クラッシュしたＤＨＴノードに対する前記ハッシュ範囲を識別する情報を含む前記ＤＨＴハッシュテーブルにおいて前記複製部分を有する前記他のＤＨＴノードのうちの前記１つのＤＨＴノードを判定することを特徴とする請求項１５記載のＤＨＴノード。
【請求項１７】
クラッシュしたＤＨＴノードが自身を復元しようとしていることを認識すると、
（１）前記クラッシュ／復元したＤＨＴノードに関連する全ての受信した書き込み又は削除要求にマークを付与し、
（２）前記復元したＤＨＴノードに関連する複製されたレコードを前記復元したＤＨＴノードに送出し、
（３）前記マークが付与された書き込み又は削除要求の受信に応答して変更されたレコードを前記復元したＤＨＴノードに送信し、
（４）前記復元したＤＨＴノードに関連する次に受信された書き込み又は削除要求を格納して対処せず、
（５）前記復元したＤＨＴノードが現在アクティブであることを示すメッセージを受信し、
（６）前記復元したＤＨＴノードが現在アクティブであることを示すように前記ＤＨＴハッシュテーブルを更新し、
（７）前記復元したＤＨＴノードに関連する前記格納された次に受信された書き込み又は削除要求を前記復元したＤＨＴノードに送出する
ように機能する回復機構（２１０）を更に具備することを特徴とする請求項１３記載のＤＨＴノード。
【請求項１８】
当該ＤＨＴノードが前記ＤＨＴオーバレイネットワーク内の最初のＤＨＴノードでないときは、再計算されたＤＨＴハッシュテーブルを受信し、
当該ＤＨＴノードが前記ＤＨＴオーバレイネットワーク内の最初のＤＨＴノードであるときは、再計算されたＤＨＴハッシュテーブルを前記ＤＨＴオーバレイネットワーク内の他のＤＨＴノードに対して提出する
ように構成されることを特徴とする請求項１３に記載のＤＨＴノード。
【国際調査報告】
2010519630.tif 000013
2010519630.tif 000014
2010519630.tif 000015