【手続補正書】
【提出日】平成20年4月17日(2008.4.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データオーバーレイをデータ構造として、ピアツーピアシステムのための分散ハッシュテーブルＤＨＴ内に含まれた論理空間の上に構築するステップであって、前記論理空間は、関連付けられた複数のＤＨＴゾーンを有する複数のＤＨＴノードを含むステップと、
前記データオーバーレイ内で、各前記ＤＨＴノードに関連付けられた１つまたは複数のツリーノードをそれぞれ含む、複数のレベルを有するツリーのトポロジを構築するステップであって、
前記ツリーの第１のレベルは、前記ＤＨＴの前記論理空間の全体の範囲に対応し、複数のツリーノードゾーンに論理的に分割される、単一のツリーノードゾーンを有する単一のツリーノードを含み、複数の前記ツリーノードゾーンはそれぞれ、
前記ツリーの各レベルの前記ツリーノードと、
前記ＤＨＴの前記論理空間の部分とに対応し、
各前記ツリーノードは、その各ツリーノードゾーンに関連付けられたキーを識別するキーメンバを含むステップと、
複数のマシンを前記ＤＨＴの前記論理空間にマップするステップとを有し、
各マシンは、１つまたは複数の前記ツリーノードゾーンに対応する方法において、
各マシンはその代表ノードとして、それに対応する前記１つまたは複数のツリーノードゾーンから、最大サイズのツリーノードゾーンに対応する前記ツリーノードを選択し、
各前記代表ノードはその親ノードとして、より大きいサイズを有する隣接した前記ツリーノードゾーンのための前記代表ノードである、もう１つの前記代表ノードを選択するステップと
を備えることを特徴とする方法。
【請求項２】
メタデータを各前記マシンで収集するステップと、
前記マシンで収集された前記メタデータを、対応する代表ノードに送信するステップと、
各前記代表ノードによって受信された前記メタデータを収集し、各前記代表ノードによって収集された前記メタデータを、対応する親ノードに送信するステップと、
前記ツリーの第１のレベルの前記単一のツリーノードで受信されたメタデータを収集するステップと
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記ツリーの第１のレベルの前記単一のツリーノードで収集されたメタデータを処理するステップと、
処理されたメタデータを、前記ツリーの第１のレベルの前記単一のツリーノードから、各前記マシンへ、各親および代表ノードを介して送信するステップと
をさらに備えることを特徴とする請求項２に記載の方法。
【請求項４】
前記メタデータは、各前記マシンのオペレーションに関する情報を備え、
前記処理されたメタデータは、各前記マシンのオペレーションを管理することができる命令を備えることを特徴とする請求項３に記載の方法。
【請求項５】
前記ＤＨＴの前記論理空間の全体の範囲に対応する前記単一のツリーノードゾーンは、ｋ個のツリーノードゾーンに均等に分割され、
ｋは、前記ツリーの第１のレベルのツリーノードの数であり、
前記ツリーのレベルｉのｊ番目のツリーノードは、
［ｊ／ｋｉ，（ｊ＋１）／ｋｉ］のサイズと、
（２ｊ＋１）／２ｋｉであって、（０≦ｊ＜２ｉ）であるキーとを有するツリーノードゾーンを有する
ことを特徴とする請求項１に記載の方法。
【請求項６】
各前記キーは、各ツリーノードゾーンの中心を識別する座標の関数である値を有し、
前記ツリーのｉ番目のレベルは、ｋｉ個のツリーノードを含み、
各ツリーノードの前記ツリーノードゾーンは１／ｋｉのサイズを有する
ことを特徴とする請求項５に記載の方法。
【請求項７】
各前記マシンについて、前記マシンのための各代表および親ノードの各キーを計算するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項８】
各キーを計算する前記ステップは、前記マシンにより、ルックアップを前記ＤＨＴ内で使用して情報を得るステップをさらに備え、前記マシンは前記情報を、対応する前記代表ノードの前記キーにより使用して、前記代表ノードに対応する前記マシンとの通信を確立することを特徴とする請求項７に記載の方法。
【請求項９】
各前記マシンで、ハートビート送信を、隣接する前記ツリーノードゾーン内の各前記マシンから受信するステップと、
いずれかの前記ハートビート送信がタイムリーに受信されない場合、前記隣接する前記ツリーノードゾーン内の対応する前記マシンの不在を、
前記ＤＨＴの提供を繰り返すステップと、
前記データオーバーレイを前記データ構造として、前記ＤＨＴの前記論理空間の上に構築する前記ステップを繰り返すステップと、
マルチレベルツリーを、再構築されたデータオーバーレイ内で構築するステップを繰り返すステップと、
前記複数のマシンを前記ＤＨＴの前記論理空間にマップする前記ステップを繰り返すステップと
を行うことによって、計上するステップと
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項１０】
各前記代表ノードおよび各前記親ノードは、リソースの可用性の最適化関数として選択されることを特徴とする請求項１に記載の方法。
【請求項１１】
前記最適化関数は、ネットワーク座標、帯域幅ボトルネック、最大レイテンシ、およびレイテンシの変化からなる１つのグループから選択された基準に基づき、それにより、最もリソースを必要とするタスクは、前記ピアツーピアシステム内で最もリソースを利用可能なマシンによって実行されることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記ＤＨＴは、前記ピアツーピアシステムへのオブジェクトの挿入、および前記ピアツーピアシステムからのオブジェクトの検索を管理し、
前記論理空間は、関連付けられた複数のＤＨＴゾーンを有する複数のＤＨＴノードを含み、
前記ＤＨＴの前記データオーバーレイは、
前記データ構造内のオブジェクトを前記ＤＨＴノードに関連付けるステップと、
前記データ構造内の前記オブジェクトの間でリンクを確立するステップとによって構築される
ことを特徴とする請求項１に記載の方法。
【請求項１３】
各リンクは、
第１のオブジェクトから第２のオブジェクトへポイントする、ハードワイヤードポインタを提供する第１のフィールドと、
前記第１のオブジェクトから、前記第２のオブジェクトをホストするＤＨＴノードへポイントする、ソフトステートポインタを提供する第２のフィールドと
を含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記データオーバーレイを構築する前記ステップは、
前記ＤＨＴ内のオブジェクトへのポインタを確立する参照を設定するための第１のプリミティブと、
ポインタによって参照されたオブジェクトを戻すための第２のプリミティブと、
ポインタによって参照されたオブジェクトを削除するための第３のプリミティブと
を使用することを特徴とする請求項１２に記載の方法。
【請求項１５】
前記データオーバーレイ内の各ツリーノードは、前記ツリーノードを通過させられるデータ上で実行されるオペレーションを定義する、オペレーションメンバを含むことを特徴とする請求項１に記載の方法。
【請求項１６】
前記データオーバーレイ内の各ツリーノードは、前記ツリーノードを使用して生成されるレポートタイプを定義する、レポートメンバを含むことを特徴とする請求項１に記載の方法。
【請求項１７】
前記ツリーの第１のレベルは、前記ツリーのためのルートノードである前記ツリーノードを含み、
前記ルートノードは、前記ＤＨＴの前記論理空間の全体の範囲に対応する前記ツリーノードゾーンに対応する
ことを特徴とする請求項１に記載の方法。
【請求項１８】
請求項１２に記載の方法による、前記データオーバーレイ内のオブジェクトの構築を実施するためのマシン可読命令を含むことを特徴とするコンピュータ可読媒体。
【請求項１９】
請求項１に記載の方法により作成されたデータオーバーレイをその上に格納していることを特徴とするコンピュータ可読媒体。
【請求項２０】
データオーバーレイを、ピアツーピアシステムのための分散ハッシュテーブルＤＨＴ内に含まれた論理空間の上のデータ構造として備える、データ構造を格納しているコンピュータ可読媒体であって、
前記ＤＨＴは、ピアツーピアシステムへのオブジェクトの挿入、およびピアツーピアシステムからのオブジェクトの検索を管理し、
前記論理空間は、関連付けられた複数のＤＨＴゾーンを有する複数のＤＨＴノードを含み、
前記ＤＨＴの前記データオーバーレイは、
前記データ構造内のオブジェクトを前記ＤＨＴノードに関連付けるステップと、
前記データ構造内の前記オブジェクトの間でリンクを確立するステップとによって構築され、
前記データオーバーレイは、複数のレベルを有するツリーのトポロジを有し、
前記ツリーは、各前記ＤＨＴノードに関連付けられた複数のツリーノードを含み、
前記ツリーノードは、前記ＤＨＴの前記論理空間に対応するツリーノードゾーンを有するルートノードを含み、
前記ルートノードの前記ツリーノードゾーンは、複数のツリーノードゾーンに論理的に分割され、前記複数のツリーノードゾーンはそれぞれ、
前記ツリーの各レベルのツリーノードの数と、
分散ハッシュテーブルの前記論理空間の部分とに対応し、
各前記ツリーノードは、その各ツリーノードゾーンに関連付けられたキーを識別するキーメンバを含み、
前記ＤＨＴの前記論理空間は複数のマシンにマップされ、
各マシンは、１つまたは複数の前記ツリーノードゾーンに対応するコンピュータ可読媒体において、
各マシンはその代表ノードとして、それに対応する前記１つまたは複数のツリーノードゾーンから、最大サイズのツリーノードゾーンに対応する前記ツリーノードを選択し、
各前記代表ノードはその親ノードとして、より大きいサイズを有する隣接した前記ツリーノードゾーンのための前記代表ノードである、もう１つの前記代表ノードを選択する
ことを特徴とするコンピュータ可読媒体。
【請求項２１】
前記ルートノードの前記ツリーノードゾーンは、ｋ個のツリーノードゾーンに均等に分割され、ｋは、前記ツリーの第１のレベルのツリーノードの数であり、
前記ツリーのレベルｉのｊ番目のツリーノードは、
［ｊ／ｋｉ，（ｊ＋１）／ｋｉ］のサイズと、
（２ｊ＋１）／２ｋｉであって、（０≦ｊ＜２ｉ）であるキーと
を有するツリーノードゾーンを有することを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２２】
各前記キーは、各ツリーノードゾーンの中心を識別する座標の関数である値を有し、
前記ツリーのｉ番目のレベルは、ｋｉ個のツリーノードを含み、
各ツリーノードの前記ツリーノードゾーンは１／ｋｉのサイズを有することを特徴とする請求項２１に記載のコンピュータ可読媒体。
【請求項２３】
前記ＤＨＴは、前記ピアツーピアシステムへのオブジェクトの挿入、および前記ピアツーピアシステムからのオブジェクトの検索を管理し、
前記論理空間は、関連付けられた複数のＤＨＴゾーンを有する複数のＤＨＴノードを含み、
前記ＤＨＴの前記データオーバーレイは、
前記ＤＨＴに関連付けられた、前記データ構造内のオブジェクトを有し、
前記データ構造内の前記オブジェクトの間で確立されたリンクを有する
ことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２４】
各リンクは、
第１のオブジェクトから第２のオブジェクトへポイントする、ハードワイヤードポインタを提供する第１のフィールドと、
前記第１のオブジェクトから、前記第２のオブジェクトをホストするＤＨＴノードへポイントする、ソフトステートポインタを提供する第２のフィールドと
を含むことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２５】
第１のプリミティブは、前記ＤＨＴ内のオブジェクトへのポインタを確立する参照を設定し、
第２のプリミティブは、ポインタによって参照されたオブジェクトを戻し、
第３のプリミティブは、ポインタによって参照されたオブジェクトを削除する
ことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２６】
前記データオーバーレイ内の各ツリーノードは、前記ツリーノードを通過させられるデータ上で実行することができるオペレーションを定義する、オペレーションメンバを含むことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２７】
前記データオーバーレイ内の各ツリーノードは、前記ツリーノードを使用して生成されるレポートタイプを定義する、レポートメンバを含むことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２８】
前記ツリーの第１のレベルは、前記ツリーのためのルートノードである前記ツリーノードを含み、
前記ルートノードは、前記ＤＨＴの前記論理空間の全体の範囲に対応する前記ツリーノードゾーンに対応する
ことを特徴とする請求項２０に記載のコンピュータ可読媒体。
【請求項２９】
ピアツーピア方法で対話する複数のマシンを含むピアツーピアシステムであって、
複数の関連付けられたＤＨＴゾーンを有する複数のＤＨＴノードを含む分散ハッシュテーブルＤＨＴの論理空間と、
なお、前記ＤＨＴは、前記ピアツーピアシステムへのオブジェクトの挿入、および前記ピアツーピアシステムからのオブジェクトの検索を管理し、
前記ＤＨＴの前記論理空間の上のデータ構造としてのデータオーバーレイを構築する手段と、
なお、前記ＤＨＴの前記データオーバーレイは、
前記ＤＨＴノードに関連付けられた前記データ構造内のオブジェクトを有し、
前記データ構造内の前記オブジェクトの間で確立されたリンクを有し、
前記データオーバーレイにおけるツリーのトポロジーを構築する手段であって、前記ツリーは複数のレベルおよび各前記ＤＨＴノードに関連付けられた複数のツリーノードを含む手段と、
なお、前記ツリーノードは、前記ＤＨＴの前記論理空間全体に対応するツリーノードゾーンを有するルートノードを含み、
前記ルートノードの前記ツリーノードゾーンは、複数のツリーノードゾーンに論理的に分割され、前記複数のツリーノードゾーンはそれぞれ、
前記ツリーの各レベルのツリーノードの数と、
分散ハッシュテーブルの前記論理空間の部分とに対応し、
各前記ツリーノードは、その各ツリーノードゾーンに関連付けられたキーを識別するキーメンバを含み、
前記ＤＨＴの前記論理空間を複数のマシンにマップする手段と
を有し、各マシンは、１つまたは複数の前記ツリーノードゾーンに対応するピアツーピアシステムにおいて、
各マシンはその代表ノードとして、それに対応する前記１つまたは複数のツリーノードゾーンから、最大サイズのツリーノードゾーンに対応する前記ツリーノードを選択するように構成され、
各前記代表ノードはその親ノードとして、より大きいサイズを有する隣接した前記ツリーノードゾーンのための前記代表ノードである、もう１つの前記代表ノードを選択するように構成されていることを特徴とするピアツーピアシステム。
【請求項３０】
データを前記ツリーノード中に通過させることによって、前記データオーバーレイを通じて前記データをルーティングするように構成されたルーティングロジックをさらに備えることを特徴とする請求項２９に記載のシステム。
【請求項３１】
前記ルーティングロジックは、データをＤＨＴノードから収集すること、および、前記データを前記ツリーの前記ルートノードへと前記ツリーノード中に通過させることによって、前記データオーバーレイを通じて前記データをルーティングするように構成されることを特徴とする請求項３０に記載のシステム。
【請求項３２】
前記ルーティングロジックは、前記ツリーの前記ルートノードから、前記ツリーノードを通じて、前記ＤＨＴノードへデータを配布することによって、前記データオーバーレイを通じてデータをルーティングするように構成されることを特徴とする請求項３０に記載のシステム。
【請求項３３】
ピアツーピアシステムを構築するための装置であって、
データオーバーレイをデータ構造として、ピアツーピアシステムのための分散ハッシュテーブルＤＨＴ内に含まれた論理空間の上に構築する手段と、
なお、前記ＤＨＴは、ピアツーピアシステムへのオブジェクトの挿入、およびピアツーピアシステムからのオブジェクトの検索を管理し、
前記論理空間は、関連付けられた複数のＤＨＴゾーンを有する複数のＤＨＴノードを含み、
前記ＤＨＴの前記データオーバーレイは、
前記データ構造内のオブジェクトを前記ＤＨＴノードに関連付けること、および
前記データ構造内の前記オブジェクトの間でリンクを確立することによって構築され、
前記データオーバーレイ内でツリーのトポロジを構築する手段と、
なお、前記ツリーは複数のレベルを有し、各前記ＤＨＴノードに関連付けられた複数のツリーノードを含み、
前記ツリーノードは、前記ＤＨＴの前記論理空間に対応するツリーノードゾーンを有するルートノードを含み、
前記ルートノードの前記ツリーノードゾーンは、複数のツリーノードゾーンに論理的に分割され、前記複数のツリーノードゾーンはそれぞれ、
前記ツリーの各レベルのツリーノードの数と、
前記分散ハッシュテーブルの前記論理空間の部分とに対応し、
各前記ツリーノードは、その各ツリーノードゾーンに関連付けられたキーを識別するキーメンバを含み、
複数のマシンを前記ＤＨＴの前記論理空間にマップする手段であって、各マシンは、１つまたは複数の前記ツリーノードゾーンに対応する手段とを有する装置において、
その代表ノードとして、各前記マシンに対応する前記１つまたは複数のツリーノードゾーンから、最大サイズのツリーノードゾーンに対応する前記ツリーノードを選択する手段と、
各前記代表ノードについて、その親ノードとして、より大きいサイズを有する隣接した前記ツリーノードゾーンのための前記代表ノードである、もう１つの前記代表ノードを選択する手段と
を備えることを特徴とする装置。
【請求項３４】
メタデータを各前記マシンで収集する手段と、
前記マシンで収集された前記メタデータを、対応する代表ノードに送信する手段と、
各前記代表ノードによって受信された前記メタデータを収集する手段と、
各前記代表ノードによって収集された前記メタデータを、対応する親ノードに送信する手段と、
前記ツリーの第１のレベルの単一のツリーノードで受信されたメタデータを収集する手段と
をさらに備えることを特徴とする請求項３３に記載の装置。
【請求項３５】
前記ツリーの第１のレベルの単一のツリーノードで収集されたメタデータを処理する手段と、
処理されたメタデータを、前記ツリーの第１のレベルの単一のツリーノードから、各前記マシンへ、各親および代表ノードを介して送信する手段と
をさらに備えることを特徴とする請求項３４に記載の装置。
【請求項３６】
前記メタデータは、各前記マシンのオペレーションに関する情報を備え、
前記処理されたメタデータは、各前記マシンのオペレーションを管理することができる命令を備える
ことを特徴とする請求項３５に記載の装置。
【請求項３７】
マシンで、ハートビート送信を、隣接する前記ツリーノードゾーン内の各前記マシンから受信する手段と、
いずれかの前記ハートビート送信がタイムリーに受信されない場合、前記隣接する前記ツリーノードゾーン内の対応する前記マシンの不在を、
前記ＤＨＴの提供を繰り返すこと、
前記データオーバーレイを前記データ構造として、前記ＤＨＴの前記論理空間の上に構築することを繰り返すこと、および
マルチレベルツリーを、再構築されたデータオーバーレイ内で構築することを繰り返すことによって、計上する手段と
をさらに備えることを特徴とする請求項３３に記載の装置。
【請求項３８】
前記計上する手段は、前記複数のマシンを前記ＤＨＴの前記論理空間にマップすることを繰り返す手段をさらに備え、
各前記代表ノードおよび各前記親ノードを、対応するマシンのリソースの可用性の最適化関数として選択する手段をさらに備える
ことを特徴とする請求項３７に記載の装置。
【請求項３９】
前記最適化関数は、ネットワーク座標、帯域幅ボトルネック、最大レイテンシ、およびレイテンシの変化からなるグループから選択された基準に基づき、それにより、最もリソースを必要とするタスクは、前記ピアツーピアシステム内で最もリソースを利用可能なマシンによって実行されることを特徴とする請求項３８に記載の装置。
【請求項４０】
データを前記ツリーノード中に通過させることによって、前記データオーバーレイを通じて前記データをルーティングする手段をさらに備えることを特徴とする請求項３３に記載の装置。
【請求項４１】
前記ルーティングする手段は、データをＤＨＴノードから収集すること、および、前記データを前記ツリーの前記ルートノードへと前記ツリーノード中に通過させることによって、前記データオーバーレイを通じて前記データをルーティングする手段を含むことを特徴とする請求項４０に記載の装置。
【請求項４２】
前記ルーティングする手段は、前記ツリーの前記ルートノードから、前記ツリーノードを通じて、前記ＤＨＴノードへデータを配布することによって、前記データオーバーレイを通じてデータをルーティングする手段を含むことを特徴とする請求項４０に記載の装置。