JP2002335269A - ピアツーピア名前解決プロトコル（ｐｎｒｐ）およびそれと共に使用するためのマルチレベルキャッシュ - Google Patents
ピアツーピア名前解決プロトコル（ｐｎｒｐ）およびそれと共に使用するためのマルチレベルキャッシュInfo
- Publication number
- JP2002335269A JP2002335269A JP2002100287A JP2002100287A JP2002335269A JP 2002335269 A JP2002335269 A JP 2002335269A JP 2002100287 A JP2002100287 A JP 2002100287A JP 2002100287 A JP2002100287 A JP 2002100287A JP 2002335269 A JP2002335269 A JP 2002335269A
- Authority
- JP
- Japan
- Prior art keywords
- node
- address information
- level
- peer
- item
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L67/00—Network arrangements or protocols for supporting network services or applications
- H04L67/01—Protocols
- H04L67/10—Protocols in which an application is distributed across nodes in the network
- H04L67/104—Peer-to-peer [P2P] networks
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L61/00—Network arrangements, protocols or services for addressing or naming
- H04L61/45—Network directories; Name-to-address mapping
- H04L61/4505—Network directories; Name-to-address mapping using standardised directories; using standardised directory access protocols
- H04L61/4511—Network directories; Name-to-address mapping using standardised directories; using standardised directory access protocols using domain name system [DNS]
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L61/00—Network arrangements, protocols or services for addressing or naming
- H04L61/58—Caching of addresses or names
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L67/00—Network arrangements or protocols for supporting network services or applications
- H04L67/01—Protocols
- H04L67/10—Protocols in which an application is distributed across nodes in the network
- H04L67/104—Peer-to-peer [P2P] networks
- H04L67/1061—Peer-to-peer [P2P] networks using node-based peer discovery mechanisms
- H04L67/1065—Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT]
Abstract
(57)【要約】
【課題】 絶えず増加し続けるキャッシュを必要とせ
ず、適切なホップ数によって、ネットワークのサイズに
関わらず収束を保証するサーバレス名前解決プロトコル
を提供すること。 【解決手段】 この収束は、マルチレベルキャッシュお
よび事前対応キャッシュ初期設定戦略によって保証され
る。マルチレベルキャッシュは、円形番号空間に基づい
て構築される。各レベルは、円形空間の様々なレベルの
小域からの情報を含んでいる。ノードが最後のレベルが
満杯であると判断したときに、マルチレベルキャッシュ
にレベルを１つ追加するためのメカニズムが含まれる。
ＰＮＲＰは、ハッシュ関数によって円形番号空間上にマ
ッピングされる名前の解決を可能にするための方法を含
む。さらに、ＰＮＲＰは、各ノードにＤＮＳ構成部分と
一意の番号とを含むＩＤを提供することによってドメイ
ンネームシステムでも動作することができる。
ず、適切なホップ数によって、ネットワークのサイズに
関わらず収束を保証するサーバレス名前解決プロトコル
を提供すること。 【解決手段】 この収束は、マルチレベルキャッシュお
よび事前対応キャッシュ初期設定戦略によって保証され
る。マルチレベルキャッシュは、円形番号空間に基づい
て構築される。各レベルは、円形空間の様々なレベルの
小域からの情報を含んでいる。ノードが最後のレベルが
満杯であると判断したときに、マルチレベルキャッシュ
にレベルを１つ追加するためのメカニズムが含まれる。
ＰＮＲＰは、ハッシュ関数によって円形番号空間上にマ
ッピングされる名前の解決を可能にするための方法を含
む。さらに、ＰＮＲＰは、各ノードにＤＮＳ構成部分と
一意の番号とを含むＩＤを提供することによってドメイ
ンネームシステムでも動作することができる。
Description
【０００１】関連特許出願の相互参照 本特許出願は、その教示および開示を参照により本明細
書に組み込んだ２００１年４月２日出願の米国特許仮出
願第６０／２８０，８９６号の利益を主張するものであ
る。
書に組み込んだ２００１年４月２日出願の米国特許仮出
願第６０／２８０，８９６号の利益を主張するものであ
る。
【０００２】
【発明の属する技術分野】本発明は、一般に、名前解決
プロトコルに関し、より詳細には、ピアツーピア名前解
決プロトコルに関する。
プロトコルに関し、より詳細には、ピアツーピア名前解
決プロトコルに関する。
【０００３】
【従来の技術】ピアツーピア通信および実際にはすべて
のタイプの通信は、選択されたエンティティ間に接続を
確立する可能性に依存するものである。エンティティ
は、１つまたは複数のアドレスを有する場合がある。実
際、これらのアドレスは、エンティティがネットワーク
内を移動する際に変化することがしばしばあるが、これ
はそのトポロジーが変化するか、またはアドレスリース
を更新することができないという理由によるものであ
る。したがって、このアドレッシング問題に対する典型
的なアーキテクチャによる解法は、各エンティティに安
定した名前を割り当てること、および接続が必要なとき
にこの名前を「解決する」ことである。この名前−アド
レス変換は非常に堅固である必要があり、また、簡単で
迅速に更新することができる必要がある。
のタイプの通信は、選択されたエンティティ間に接続を
確立する可能性に依存するものである。エンティティ
は、１つまたは複数のアドレスを有する場合がある。実
際、これらのアドレスは、エンティティがネットワーク
内を移動する際に変化することがしばしばあるが、これ
はそのトポロジーが変化するか、またはアドレスリース
を更新することができないという理由によるものであ
る。したがって、このアドレッシング問題に対する典型
的なアーキテクチャによる解法は、各エンティティに安
定した名前を割り当てること、および接続が必要なとき
にこの名前を「解決する」ことである。この名前−アド
レス変換は非常に堅固である必要があり、また、簡単で
迅速に更新することができる必要がある。
【０００４】名前サービスには２つの典型的なタイプ、
すなわちマルチキャストに基づくものと、集中型サーバ
に基づくものとがある。最近、純粋なピアツーピアネッ
トワークであるＧｎｕｔｅｌｌａおよびＦｒｅｅｎｅｔ
は、分散アルゴリズムを使用した命名機能を実施しよう
とした。残念ながら、これらすべてのアルゴリズムには
限界があり、このためインターネットのサイズに近づき
つつあるネットワーク内において普遍的な解決法を提供
する能力は限定されている。
すなわちマルチキャストに基づくものと、集中型サーバ
に基づくものとがある。最近、純粋なピアツーピアネッ
トワークであるＧｎｕｔｅｌｌａおよびＦｒｅｅｎｅｔ
は、分散アルゴリズムを使用した命名機能を実施しよう
とした。残念ながら、これらすべてのアルゴリズムには
限界があり、このためインターネットのサイズに近づき
つつあるネットワーク内において普遍的な解決法を提供
する能力は限定されている。
【０００５】マルチキャストアーキテクチャでは、要求
は、グループ内のすべての局がリッスンする１つのマル
チキャストアドレスに送信される。ターゲットはその名
前を認識し、応答する。このようなサービスの一例とし
ては、ＳＬＰおよびＳＳＤＰがある。残念ながら、ネッ
トワークはいかなる要求でも複数のコピーを送信するこ
とを必要とするので、マルチキャストサービスは、大き
なネットワーキングオーバーヘッドを伴うものである。
さらに、グループのすべてのメンバーがすべての照会を
受信してそれを処理し、それ自体の名前を認識しない照
会だけを破棄するので、これらのマルチキャストサービ
スは、大きな計算オーバーヘッドをも伴う。これらのオ
ーバーヘッドがあるため、マルチキャストアーキテクチ
ャは、通常、限定された数のノードと少数のリンクを含
んでいる非常に小規模なネットワークでのみ使用され
る。スケールするために、マルチキャストプロトコル
は、集中型サーバ挿入の実現と、サーバが存在するとき
は集中型モードに移行することを含むことがしばしばあ
る。
は、グループ内のすべての局がリッスンする１つのマル
チキャストアドレスに送信される。ターゲットはその名
前を認識し、応答する。このようなサービスの一例とし
ては、ＳＬＰおよびＳＳＤＰがある。残念ながら、ネッ
トワークはいかなる要求でも複数のコピーを送信するこ
とを必要とするので、マルチキャストサービスは、大き
なネットワーキングオーバーヘッドを伴うものである。
さらに、グループのすべてのメンバーがすべての照会を
受信してそれを処理し、それ自体の名前を認識しない照
会だけを破棄するので、これらのマルチキャストサービ
スは、大きな計算オーバーヘッドをも伴う。これらのオ
ーバーヘッドがあるため、マルチキャストアーキテクチ
ャは、通常、限定された数のノードと少数のリンクを含
んでいる非常に小規模なネットワークでのみ使用され
る。スケールするために、マルチキャストプロトコル
は、集中型サーバ挿入の実現と、サーバが存在するとき
は集中型モードに移行することを含むことがしばしばあ
る。
【０００６】このような集中型アーキテクチャでは、要
求は、データベースが名前とアドレスの間のマッピング
を含んでいる集中型サーバによって処理される。現在イ
ンターネットで使用されているドメインネームサービス
（ＤＮＳ）は、集中型ルートとサーバのネットワークを
結合し、階層化された名前を解決するように構成されて
いる。残念ながら、集中型サービスおよび準集中型サー
ビスは、何種類かの弱点があることを証明している。ま
ず、全信頼が中央サーバに掛かっているので、更新情報
は強力な制御を必要とする。実際、集中型サーバは負荷
に対処することが困難であり、照会の大きな部分がキャ
ッシュによって解決される場合だけ動作することができ
る。これらのキャッシュには、名前−アドレス解決の古
いコピーがいつまでも残存しているが、これが迅速な更
新を困難にしている。さらに、集中型サーバは、政治
的、法律的、商業的管理の対象となるものである。これ
らの管理が、サービスの信頼性を干渉する場合がある。
単なるスケーリング問題としてこれらの弱点を排除しよ
うという意向があるかもしれないが、これらは集中型サ
ービスを使用することによって直接的に導かれるもので
あることは非常に明らかである。
求は、データベースが名前とアドレスの間のマッピング
を含んでいる集中型サーバによって処理される。現在イ
ンターネットで使用されているドメインネームサービス
（ＤＮＳ）は、集中型ルートとサーバのネットワークを
結合し、階層化された名前を解決するように構成されて
いる。残念ながら、集中型サービスおよび準集中型サー
ビスは、何種類かの弱点があることを証明している。ま
ず、全信頼が中央サーバに掛かっているので、更新情報
は強力な制御を必要とする。実際、集中型サーバは負荷
に対処することが困難であり、照会の大きな部分がキャ
ッシュによって解決される場合だけ動作することができ
る。これらのキャッシュには、名前−アドレス解決の古
いコピーがいつまでも残存しているが、これが迅速な更
新を困難にしている。さらに、集中型サーバは、政治
的、法律的、商業的管理の対象となるものである。これ
らの管理が、サービスの信頼性を干渉する場合がある。
単なるスケーリング問題としてこれらの弱点を排除しよ
うという意向があるかもしれないが、これらは集中型サ
ービスを使用することによって直接的に導かれるもので
あることは非常に明らかである。
【０００７】Ｇｎｕｔｅｌｌａには中央データベースは
ない。各ノードは、一組の指名されたオブジェクトを
「認識する」。グローバルサーチは、指定した「半径」
内にある近接ノード上で並列検索を実行し、その結果を
併合することによって実施される。この形式による拡大
は、メッセージおよび演算用のメモリすなわち各ノード
におけるデータベースのフットプリントと引き換えに得
られるものである。データベースが例えばＰ個の構成要
素に分割される場合、各要求は少なくともＰ個のメッセ
ージを要求し、少なくともＰ個のノードで検索をトリガ
する。データセットのサイズが限定されている場合、構
成要素数Ｐは、データセットのサイズと、所与のノード
が格納することができる最大サイズＳとの間の関係に完
全に依存するものである。この場合、構成要素数Ｐが基
本的に一定である場合、システムはスケールする。しか
しノード数Ｎが増加するに従い、所与の構成要素のコピ
ー数は０（Ｎ／Ｐ）のように増加するが、これは０
（Ｎ）と等価である。したがって、ノード数０（Ｎ）が
増えるに従ってサーチ数も増加する。したがって、構成
要素の所与のコピーが処理しなければならないサーチ数
は、サーチ数をコピー数で割った解に応じてスケールす
る。両方の数はＮと線形に増加するので、コピー当たり
のサーチ数は一定のままである。
ない。各ノードは、一組の指名されたオブジェクトを
「認識する」。グローバルサーチは、指定した「半径」
内にある近接ノード上で並列検索を実行し、その結果を
併合することによって実施される。この形式による拡大
は、メッセージおよび演算用のメモリすなわち各ノード
におけるデータベースのフットプリントと引き換えに得
られるものである。データベースが例えばＰ個の構成要
素に分割される場合、各要求は少なくともＰ個のメッセ
ージを要求し、少なくともＰ個のノードで検索をトリガ
する。データセットのサイズが限定されている場合、構
成要素数Ｐは、データセットのサイズと、所与のノード
が格納することができる最大サイズＳとの間の関係に完
全に依存するものである。この場合、構成要素数Ｐが基
本的に一定である場合、システムはスケールする。しか
しノード数Ｎが増加するに従い、所与の構成要素のコピ
ー数は０（Ｎ／Ｐ）のように増加するが、これは０
（Ｎ）と等価である。したがって、ノード数０（Ｎ）が
増えるに従ってサーチ数も増加する。したがって、構成
要素の所与のコピーが処理しなければならないサーチ数
は、サーチ数をコピー数で割った解に応じてスケールす
る。両方の数はＮと線形に増加するので、コピー当たり
のサーチ数は一定のままである。
【０００８】残念ながら、名前サーバアプリケーション
では、データベースのサイズとサーチ数の両方がＮすな
わちメンバー数と線形に増加する。このため、スケーリ
ング問題が生じる。具体的には、いかなる構成要素にも
０（Ｎ／Ｐ）のコピーがあり、単位時間当たり０（Ｎ）
サーチがあることになる。したがって、各ノードは、サ
ーチ当たり０（Ｐ）メッセージを送信する必要がある。
各構成要素は０（Ｎ）回サーチされることになるので、
各コピーは（０（Ｎ）／０（Ｎ／Ｐ））＝０（Ｐ）回サ
ーチされることになる。使用可能なメモリによって限定
される、所与の構成要素に対して最大サイズＳがある場
合、Ｐは０（Ｎ／Ｓ）に応じて増加させる必要がある。
Ｓを一定であると仮定すると、Ｐは０（Ｎ）に応じて増
加しなければならない。したがって、各ノードが処理す
るサーチ数と、各ノードが送受信するメッセージ数は、
両方とも０（Ｎ）に応じて増加することになる。要する
に、データセットがノード数に応じて増加する場合、単
純な分割戦略では役立たないということである。実際、
ＮＡＰＳＴＥＲ裁判中にＧｎｕｔｅｌｌａの需要が高ま
り、システムの崩壊を招いた。その後、需要の高まり
が、平均的なトラフィックがモデムリンクの限度を超え
る原因となり、これが原因でＧｎｕｔｅｌｌａシステム
は一組の切断されたネットワーク中で分裂した。
では、データベースのサイズとサーチ数の両方がＮすな
わちメンバー数と線形に増加する。このため、スケーリ
ング問題が生じる。具体的には、いかなる構成要素にも
０（Ｎ／Ｐ）のコピーがあり、単位時間当たり０（Ｎ）
サーチがあることになる。したがって、各ノードは、サ
ーチ当たり０（Ｐ）メッセージを送信する必要がある。
各構成要素は０（Ｎ）回サーチされることになるので、
各コピーは（０（Ｎ）／０（Ｎ／Ｐ））＝０（Ｐ）回サ
ーチされることになる。使用可能なメモリによって限定
される、所与の構成要素に対して最大サイズＳがある場
合、Ｐは０（Ｎ／Ｓ）に応じて増加させる必要がある。
Ｓを一定であると仮定すると、Ｐは０（Ｎ）に応じて増
加しなければならない。したがって、各ノードが処理す
るサーチ数と、各ノードが送受信するメッセージ数は、
両方とも０（Ｎ）に応じて増加することになる。要する
に、データセットがノード数に応じて増加する場合、単
純な分割戦略では役立たないということである。実際、
ＮＡＰＳＴＥＲ裁判中にＧｎｕｔｅｌｌａの需要が高ま
り、システムの崩壊を招いた。その後、需要の高まり
が、平均的なトラフィックがモデムリンクの限度を超え
る原因となり、これが原因でＧｎｕｔｅｌｌａシステム
は一組の切断されたネットワーク中で分裂した。
【０００９】Ｆｒｅｅｎｅｔは、有機的アルゴリズムで
それ自体を編成する「ピアツーピア」ネットワークであ
る。ネットワークの目的は、バイナリ識別子によって識
別される文書を分配することである。文書をサーチする
ことによって、図８に示す要求ノードの近接局に伝播さ
れる要求が生じる。この近接局がその文書のコピーを有
しない場合、この近接局は要求を別の近接局に転送す
る、という具合である。その文書が発見された場合、経
路上の各ノードは、最終的に最初の要求元にコピーが到
着するまでコピーを受け取る。また、コピーが発見され
ないケースもあるが、この場合サーチは失敗する。サー
チを転送するノードは、まったくアトランダムに近接局
を選択するわけではない。これらのノードは、文書識別
子を、既に複数の近接局によって供給され、それら近接
局のルーティングテーブルに格納されている別の識別子
と比較する。格納されている情報は、一意の番号、アド
レス、およびそれら近接局に対する証明を含む。次いで
ノードは、サーチされている識別子に最も類似した識別
子を有する文書を以前に供給した「最も近い」近接局を
選択する。このアルゴリズムの作者によると、類似文書
に対する連続した要求を受信するノードは、そのような
文書の「クラスタ」を蓄積することになる。したがっ
て、最も需要の多い文書が、その文書を必要とする場所
の近くでコピーされる傾向を有することになる。
それ自体を編成する「ピアツーピア」ネットワークであ
る。ネットワークの目的は、バイナリ識別子によって識
別される文書を分配することである。文書をサーチする
ことによって、図８に示す要求ノードの近接局に伝播さ
れる要求が生じる。この近接局がその文書のコピーを有
しない場合、この近接局は要求を別の近接局に転送す
る、という具合である。その文書が発見された場合、経
路上の各ノードは、最終的に最初の要求元にコピーが到
着するまでコピーを受け取る。また、コピーが発見され
ないケースもあるが、この場合サーチは失敗する。サー
チを転送するノードは、まったくアトランダムに近接局
を選択するわけではない。これらのノードは、文書識別
子を、既に複数の近接局によって供給され、それら近接
局のルーティングテーブルに格納されている別の識別子
と比較する。格納されている情報は、一意の番号、アド
レス、およびそれら近接局に対する証明を含む。次いで
ノードは、サーチされている識別子に最も類似した識別
子を有する文書を以前に供給した「最も近い」近接局を
選択する。このアルゴリズムの作者によると、類似文書
に対する連続した要求を受信するノードは、そのような
文書の「クラスタ」を蓄積することになる。したがっ
て、最も需要の多い文書が、その文書を必要とする場所
の近くでコピーされる傾向を有することになる。
【００１０】Ｆｒｅｅｎｅｔのノードは、文書識別子と
文書を受信した近接局のＩＤとを関連付ける「ルーティ
ングテーブル」を維持する。このルーティングテーブル
は、検索プロセスの副産物として更新される。すなわ
ち、要求が達成されると、経路上の各ノードは、テーブ
ルにその文書識別子とその文書を受信した近接ノードと
をリンクする項目を入れる。現実の生活環境では、ルー
ティングテーブルのサイズには限界がある。一旦限界に
達すると、ノードは保存または破棄を意図する項目を選
択する必要がある。限界に達すると、新しい入力は最も
低頻度に使用されている項目と置き換わる。
文書を受信した近接局のＩＤとを関連付ける「ルーティ
ングテーブル」を維持する。このルーティングテーブル
は、検索プロセスの副産物として更新される。すなわ
ち、要求が達成されると、経路上の各ノードは、テーブ
ルにその文書識別子とその文書を受信した近接ノードと
をリンクする項目を入れる。現実の生活環境では、ルー
ティングテーブルのサイズには限界がある。一旦限界に
達すると、ノードは保存または破棄を意図する項目を選
択する必要がある。限界に達すると、新しい入力は最も
低頻度に使用されている項目と置き換わる。
【００１１】文書がサーチされるとき、ノードは、要求
されたキーに最も近いキーをそのルーティングテーブル
内で検索し、対応するノードにその要求を転送する。Ｆ
ｒｅｅｎｅｔでは、キーは１６０ビットの番号である。
ルーティングテーブルは最適の近接局を発見する。この
近接局が既に経路上でリストされている場合は、次の近
接局が選択される等が行われる。ルーティングテーブル
内のサーチが確定的でない場合、また、まだ訪問されて
いない近接局がある場合は、それら近接局のうちの１つ
が選択されることになる。使用可能な近接局がない場
合、要求は経路上の前のノードに返送され、そこでより
良い適合が試される。要求が送信者に循環して戻り、新
しい近接局がない場合、またはホップの最大数を超えた
場合は、失敗が宣言される。
されたキーに最も近いキーをそのルーティングテーブル
内で検索し、対応するノードにその要求を転送する。Ｆ
ｒｅｅｎｅｔでは、キーは１６０ビットの番号である。
ルーティングテーブルは最適の近接局を発見する。この
近接局が既に経路上でリストされている場合は、次の近
接局が選択される等が行われる。ルーティングテーブル
内のサーチが確定的でない場合、また、まだ訪問されて
いない近接局がある場合は、それら近接局のうちの１つ
が選択されることになる。使用可能な近接局がない場
合、要求は経路上の前のノードに返送され、そこでより
良い適合が試される。要求が送信者に循環して戻り、新
しい近接局がない場合、またはホップの最大数を超えた
場合は、失敗が宣言される。
【００１２】各ノードが文書を１つだけ発行する環境に
おいて、最初の接近においてノード当たり名前を１つだ
け含んでいるネットワークにおいて名前サービスを提供
するためにＦｒｅｅｎｅｔアルゴリズムを使用すること
は、その学習効果とその限界を示している。例えば、学
習プロセスは極めて遅い。学習効果は、様々な要因に基
づいて大幅に変動するものである。第１にグラフの形状
はこのプロセスに影響を与える。より結合の強いグラフ
はより良い結果を生じるものである。所与の結果に関し
て許可されているホップ数も、この学習効果に大きな役
割を担っている。ホップ数が少なすぎる場合、結果は劇
的に悪化する。各ノードにおけるキャッシュのサイズ
は、ネットワークのサイズと同様に１つの要因である。
おいて、最初の接近においてノード当たり名前を１つだ
け含んでいるネットワークにおいて名前サービスを提供
するためにＦｒｅｅｎｅｔアルゴリズムを使用すること
は、その学習効果とその限界を示している。例えば、学
習プロセスは極めて遅い。学習効果は、様々な要因に基
づいて大幅に変動するものである。第１にグラフの形状
はこのプロセスに影響を与える。より結合の強いグラフ
はより良い結果を生じるものである。所与の結果に関し
て許可されているホップ数も、この学習効果に大きな役
割を担っている。ホップ数が少なすぎる場合、結果は劇
的に悪化する。各ノードにおけるキャッシュのサイズ
は、ネットワークのサイズと同様に１つの要因である。
【００１３】Ｆｒｅｅｎｅｔアルゴリズムを使用するこ
とによって達成される成功率は、ネットワーク学習のた
めの所要時間を許可した後で、様々なネットワークサイ
ズに応じて変動する。ノード当たりの平均近接局数を５
と仮定した場合、要求は、最高２５６ノードまで訪問す
ることが許可され、各ノードは最高５１２項目までキャ
ッシュすることができ、ネットワークサイズの影響は非
常に劇的なものとなる。一定サイズを超えると、この学
習プロセスは協同で機能することを停止する。例えば１
０，０００ノードのネットワーク上では、成功率は約４
０％落ちる。要するに、Ｆｒｅｅｎｅｔアルゴリズムは
良好にスケールしない。
とによって達成される成功率は、ネットワーク学習のた
めの所要時間を許可した後で、様々なネットワークサイ
ズに応じて変動する。ノード当たりの平均近接局数を５
と仮定した場合、要求は、最高２５６ノードまで訪問す
ることが許可され、各ノードは最高５１２項目までキャ
ッシュすることができ、ネットワークサイズの影響は非
常に劇的なものとなる。一定サイズを超えると、この学
習プロセスは協同で機能することを停止する。例えば１
０，０００ノードのネットワーク上では、成功率は約４
０％落ちる。要するに、Ｆｒｅｅｎｅｔアルゴリズムは
良好にスケールしない。
【００１４】
【発明が解決しようとする課題】したがって、少なくと
も１００億の名前−アドレスマッピングの管理を定義す
ることができる、インターネット規模の命名プロトコル
に関する技術が必要とされている。好ましい解決法は、
十分に分散されており自己調製型で能率的であるべきで
ある。これは、高レベルの機密保護をも提供すべきであ
る。しかし上記の議論から明らかなように、そのような
プロトコルを提供する既存技術は１つもない。
も１００億の名前−アドレスマッピングの管理を定義す
ることができる、インターネット規模の命名プロトコル
に関する技術が必要とされている。好ましい解決法は、
十分に分散されており自己調製型で能率的であるべきで
ある。これは、高レベルの機密保護をも提供すべきであ
る。しかし上記の議論から明らかなように、そのような
プロトコルを提供する既存技術は１つもない。
【００１５】
【課題を解決するための手段】本願で開示する本発明の
概念は、集中型サーバがない状態で演算可能な新たな名
前解決プロトコルを伴う。この新しいピアツーピアの、
サーバレスな名前解決プロトコルは、絶えず増加し続け
るキャッシュを必要とせず、適切なホップ数によって、
ネットワークのサイズに関わらず収束を保証するもので
ある。
概念は、集中型サーバがない状態で演算可能な新たな名
前解決プロトコルを伴う。この新しいピアツーピアの、
サーバレスな名前解決プロトコルは、絶えず増加し続け
るキャッシュを必要とせず、適切なホップ数によって、
ネットワークのサイズに関わらず収束を保証するもので
ある。
【００１６】上記の通り、ＧｎｕｔｅｌｌａおよびＦｒ
ｅｅｎｅｔなどの純粋なピアツーピアネットワークは、
命名機能を実施するために分散アルゴリズムを使用す
る。残念ながら、これらのアルゴリズムは、ネットワー
クサイズが増大するに従い、収束を保証できなくなる。
すなわち、これらのアルゴリズムは、ネットワークサイ
ズに伴ってキャッシュサイズを線形に増大させることな
く、また、不合理な数まで許可されるホップ数を増やす
ことなくして収束を保証することはできないのである。
ｅｅｎｅｔなどの純粋なピアツーピアネットワークは、
命名機能を実施するために分散アルゴリズムを使用す
る。残念ながら、これらのアルゴリズムは、ネットワー
クサイズが増大するに従い、収束を保証できなくなる。
すなわち、これらのアルゴリズムは、ネットワークサイ
ズに伴ってキャッシュサイズを線形に増大させることな
く、また、不合理な数まで許可されるホップ数を増やす
ことなくして収束を保証することはできないのである。
【００１７】本発明によるサーバレスの、すなわちピア
ツーピアの名前解決プロトコルは、これらの問題を解決
し、マルチレベルキャッシュと事前対応キャッシュ初期
設定戦略との２つのメカニズムによって、大規模なネッ
トワーク内における収束を保証するものである。マルチ
レベルキャッシュはプロトコルが様々なサイズのネット
ワークに適合することを可能にし、（従来技術のピアツ
ーピアプロトコルによって要求されるように線形ではな
く）あくまでネットワークサイズの対数だけ増大するも
のである。マルチレベルキャッシュは、基礎となる円形
番号空間（ｃｉｒｃｕｌａｒ ｎｕｍｂｅｒ ｓｐａｃ
ｅ）の概念に基づいて構築されている。キャッシュの各
レベルは、円形空間の様々なレベルの小域（ｓｌｉｖｅ
ｒ）からの情報を含んでいる。キャッシュ内のレベル数
は、それが接続しているネットワークのサイズに依存す
る。しかしこのサイズは知られていないので、最後のレ
ベルが満杯であるとノードが判断したときにマルチレベ
ルキャッシュにレベルを追加するためのメカニズムが含
まれる。このようにして、急速な収束が保証される。
ツーピアの名前解決プロトコルは、これらの問題を解決
し、マルチレベルキャッシュと事前対応キャッシュ初期
設定戦略との２つのメカニズムによって、大規模なネッ
トワーク内における収束を保証するものである。マルチ
レベルキャッシュはプロトコルが様々なサイズのネット
ワークに適合することを可能にし、（従来技術のピアツ
ーピアプロトコルによって要求されるように線形ではな
く）あくまでネットワークサイズの対数だけ増大するも
のである。マルチレベルキャッシュは、基礎となる円形
番号空間（ｃｉｒｃｕｌａｒ ｎｕｍｂｅｒ ｓｐａｃ
ｅ）の概念に基づいて構築されている。キャッシュの各
レベルは、円形空間の様々なレベルの小域（ｓｌｉｖｅ
ｒ）からの情報を含んでいる。キャッシュ内のレベル数
は、それが接続しているネットワークのサイズに依存す
る。しかしこのサイズは知られていないので、最後のレ
ベルが満杯であるとノードが判断したときにマルチレベ
ルキャッシュにレベルを追加するためのメカニズムが含
まれる。このようにして、急速な収束が保証される。
【００１８】ピアツーピア名前解決プロトコルの第１の
拡張として、名前の解決を可能にするメカニズムも提示
される。これらの名前は、ハッシュ関数によって円形番
号空間上にマッピングされる。しかし、単一ハッシュ値
に対して複数の項目（例えば、１０，０００メンバーの
大規模なグループ）がある場合があると認識すると、＜
ハッシュ＞．＜一意の番号＞（＜Ｍ＞．＜Ｎ＞）のよう
に一意の番号が名前のハッシュに関連付けられる。この
拡張子を使用することによって、本発明の中核プロトコ
ルは名前ならびに番号に関して使用することができる。
拡張として、名前の解決を可能にするメカニズムも提示
される。これらの名前は、ハッシュ関数によって円形番
号空間上にマッピングされる。しかし、単一ハッシュ値
に対して複数の項目（例えば、１０，０００メンバーの
大規模なグループ）がある場合があると認識すると、＜
ハッシュ＞．＜一意の番号＞（＜Ｍ＞．＜Ｎ＞）のよう
に一意の番号が名前のハッシュに関連付けられる。この
拡張子を使用することによって、本発明の中核プロトコ
ルは名前ならびに番号に関して使用することができる。
【００１９】本発明の基本プロトコルへの第２の拡張
は、ピアツーピア解決プロトコルとドメインネームシス
テムとの実際の統合を実現するものである。各ノード
に、ＤＮＳ構成要素および一意の番号からなるＩＤを提
供することによって、そのＤＮＳ構成要素に対するサー
バを見つけ出すためにＤＮＳメカニズムを使用すること
ができるが、これは、ＰＮＲＰの知識をも有するローカ
ルＤＮＳリゾルバであってもよく、あるいは指定のＤＮ
Ｓ構成要素を管理する集中型サーバであってもよい。次
いでこのサーバは、特定ノードを発見するために一意の
番号の部分を有する本発明のプロトコルを使用してピア
ツーピア名前解決プロトコル（ＰＮＲＰ）空間に移動
し、その情報を要求側に戻す。個々のノードは、集中型
サーバに乱数と共に要求を送信することによってそのキ
ャッシュをシードするために役立つ近接局を発見するこ
とができる。
は、ピアツーピア解決プロトコルとドメインネームシス
テムとの実際の統合を実現するものである。各ノード
に、ＤＮＳ構成要素および一意の番号からなるＩＤを提
供することによって、そのＤＮＳ構成要素に対するサー
バを見つけ出すためにＤＮＳメカニズムを使用すること
ができるが、これは、ＰＮＲＰの知識をも有するローカ
ルＤＮＳリゾルバであってもよく、あるいは指定のＤＮ
Ｓ構成要素を管理する集中型サーバであってもよい。次
いでこのサーバは、特定ノードを発見するために一意の
番号の部分を有する本発明のプロトコルを使用してピア
ツーピア名前解決プロトコル（ＰＮＲＰ）空間に移動
し、その情報を要求側に戻す。個々のノードは、集中型
サーバに乱数と共に要求を送信することによってそのキ
ャッシュをシードするために役立つ近接局を発見するこ
とができる。
【００２０】本明細書に組み込まれその一部を構成する
添付の図面は、本発明のいくかの態様を示しており、説
明と共に本発明の原理を説明するために役立つ。
添付の図面は、本発明のいくかの態様を示しており、説
明と共に本発明の原理を説明するために役立つ。
【００２１】本発明は特定の好ましい実施形態に関して
説明するが、本発明をこれらの実施形態に限定する意図
はない。むしろ、頭記の特許請求の範囲によって規定さ
れる本発明の趣旨および範囲内に含まれるすべての代替
形態、変形形態、および均等物を対象とすることを意図
するものである。
説明するが、本発明をこれらの実施形態に限定する意図
はない。むしろ、頭記の特許請求の範囲によって規定さ
れる本発明の趣旨および範囲内に含まれるすべての代替
形態、変形形態、および均等物を対象とすることを意図
するものである。
【００２２】
【発明の実施の形態】同様の参照番号が同様の要素を示
す複数の図面を参照して、適切なコンピュータ環境で実
施されているものとして本発明を説明する。必須ではな
いが、本発明は、パーソナルコンピュータによって実行
中のプログラムモジュールなど、コンピュータ実行可能
命令の一般的なコンテキストにおいて説明する。一般
に、プログラムモジュールには、特定タスクを実行し、
または特定抽象データタイプを実施するルーチン、プロ
グラム、オブジェクト、構成要素、データ構造などが含
まれる。さらに、本発明は、ハンドヘルドデバイス、マ
ルチプロセッサシステム、マイクロプロセッサベースの
家庭電化製品またはプログラム可能な家庭電化製品、ネ
ットワークＰＣ、ミニコンピュータ、メインフレームコ
ンピュータなどを含めて、他のコンピュータシステム構
成によって実施することも可能であることを当業者なら
理解するだろう。本発明は、通信ネットワークを介して
リンクされている遠隔処理デバイスによってタスクが実
施される分散型コンピュータ環境において実施すること
も可能である。分散型コンピュータ環境では、プログラ
ムモジュールは、ローカル記憶装置と遠隔記憶装置の両
方に配置することができる。
す複数の図面を参照して、適切なコンピュータ環境で実
施されているものとして本発明を説明する。必須ではな
いが、本発明は、パーソナルコンピュータによって実行
中のプログラムモジュールなど、コンピュータ実行可能
命令の一般的なコンテキストにおいて説明する。一般
に、プログラムモジュールには、特定タスクを実行し、
または特定抽象データタイプを実施するルーチン、プロ
グラム、オブジェクト、構成要素、データ構造などが含
まれる。さらに、本発明は、ハンドヘルドデバイス、マ
ルチプロセッサシステム、マイクロプロセッサベースの
家庭電化製品またはプログラム可能な家庭電化製品、ネ
ットワークＰＣ、ミニコンピュータ、メインフレームコ
ンピュータなどを含めて、他のコンピュータシステム構
成によって実施することも可能であることを当業者なら
理解するだろう。本発明は、通信ネットワークを介して
リンクされている遠隔処理デバイスによってタスクが実
施される分散型コンピュータ環境において実施すること
も可能である。分散型コンピュータ環境では、プログラ
ムモジュールは、ローカル記憶装置と遠隔記憶装置の両
方に配置することができる。
【００２３】図１に、本発明を実施することができる適
切なコンピューティングシステム環境１００の一例を示
す。このコンピューティングシステム環境１００は適切
なコンピューティング環境の一例であるにすぎず、本発
明の使用法または機能性の範囲に関するいかなる限定を
も示唆しようとするものではない。また、コンピューテ
ィング環境１００は、例示的オペレーティング環境１０
０内に示す任意の１つの構成要素または複数構成要素の
組合せに関する依存または要件を有するものと解釈され
るべきではない。
切なコンピューティングシステム環境１００の一例を示
す。このコンピューティングシステム環境１００は適切
なコンピューティング環境の一例であるにすぎず、本発
明の使用法または機能性の範囲に関するいかなる限定を
も示唆しようとするものではない。また、コンピューテ
ィング環境１００は、例示的オペレーティング環境１０
０内に示す任意の１つの構成要素または複数構成要素の
組合せに関する依存または要件を有するものと解釈され
るべきではない。
【００２４】本発明は、他の無数の汎用または専用のコ
ンピュータシステム環境または構成によって操作するこ
とができる。よく知られたコンピューティングシステ
ム、環境および／または構成の態様は、限定はしない
が、パーソナルコンピュータ、サーバーコンピュータ、
ハンドヘルドまたはラップトップデバイス、マルチプロ
セッサシステム、マイクロプロセッサベースのシステ
ム、セットトップボックス、設定可能な家庭電化製品、
ネットワークＰＣ、ミニコンピュータ、メインフレーム
コンピュータ、上記のシステムまたはデバイスのいずれ
かなどを含む分散型コンピューティング環境などを含む
本発明の使用に適する場合がある。
ンピュータシステム環境または構成によって操作するこ
とができる。よく知られたコンピューティングシステ
ム、環境および／または構成の態様は、限定はしない
が、パーソナルコンピュータ、サーバーコンピュータ、
ハンドヘルドまたはラップトップデバイス、マルチプロ
セッサシステム、マイクロプロセッサベースのシステ
ム、セットトップボックス、設定可能な家庭電化製品、
ネットワークＰＣ、ミニコンピュータ、メインフレーム
コンピュータ、上記のシステムまたはデバイスのいずれ
かなどを含む分散型コンピューティング環境などを含む
本発明の使用に適する場合がある。
【００２５】本発明は、コンピュータで実行中のプログ
ラムモジュールなどのコンピュータ実行可能命令の一般
的なコンテキストに関して説明することができる。一般
に、プログラムモジュールは、特定タスクを実行する
か、または特定の抽象データタイプを実施するルーチ
ン、プログラム、オブジェクト、構成要素、データ構造
などを含む。本発明は、通信ネットワークを介してリン
クされている遠隔処理デバイスによってタスクが実施さ
れる分散型コンピューティング環境で実施することもで
きる。分散型コンピューティング環境では、プログラム
モジュールは、記憶装置を含めて、ローカルおよび遠隔
コンピュータの記憶媒体内に配置することができる。
ラムモジュールなどのコンピュータ実行可能命令の一般
的なコンテキストに関して説明することができる。一般
に、プログラムモジュールは、特定タスクを実行する
か、または特定の抽象データタイプを実施するルーチ
ン、プログラム、オブジェクト、構成要素、データ構造
などを含む。本発明は、通信ネットワークを介してリン
クされている遠隔処理デバイスによってタスクが実施さ
れる分散型コンピューティング環境で実施することもで
きる。分散型コンピューティング環境では、プログラム
モジュールは、記憶装置を含めて、ローカルおよび遠隔
コンピュータの記憶媒体内に配置することができる。
【００２６】図１を参照すると、本発明を実施するため
の例示的システムは、コンピュータ１１０の形態による
汎用コンピューティングデバイスを含む。コンピュータ
１１０の構成要素は、限定はしないが、処理ユニット１
２０、システムメモリ１３０、およびシステムメモリを
含む様々なシステム構成要素を処理ユニット１２０に結
合するシステムバス１２１を含む。システムバス１２１
は様々なバスアーキテクチャのいずれかを使用するメモ
リバスまたはメモリコントローラ、周辺バス、およびロ
ーカルバスを含む複数バス構造のうちのどれであっても
よい。限定的ではないが、例示として、このようなアー
キテクチャには、Ｉｎｄｕｓｔｒｙ Ｓｔｎｄａｒｄ
Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＳＡ）バス、Ｍｉｃｒｏ
Ｃｈａｎｎｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ（ＭＣ
Ａ）バス、Ｅｎｈａｎｃｅｄ ＩＳＡ（ＥＩＳＡ）バ
ス、Ｖｉｄｅｏ Ｅｌｅｃｔｒｏｎｉｃｓ Ｓｔａｎｄ
ａｒｄｓ Ａｓｓｏｃｉａｔｅ（ＶＥＳＡ）ローカルバ
ス、およびＭｅｚｚａｎｉｎｅバスとしても知られてい
るＰｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔ
ｅｒｃｏｎｎｅｃｔ（ＰＣＩ）バスが含まれる。
の例示的システムは、コンピュータ１１０の形態による
汎用コンピューティングデバイスを含む。コンピュータ
１１０の構成要素は、限定はしないが、処理ユニット１
２０、システムメモリ１３０、およびシステムメモリを
含む様々なシステム構成要素を処理ユニット１２０に結
合するシステムバス１２１を含む。システムバス１２１
は様々なバスアーキテクチャのいずれかを使用するメモ
リバスまたはメモリコントローラ、周辺バス、およびロ
ーカルバスを含む複数バス構造のうちのどれであっても
よい。限定的ではないが、例示として、このようなアー
キテクチャには、Ｉｎｄｕｓｔｒｙ Ｓｔｎｄａｒｄ
Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＳＡ）バス、Ｍｉｃｒｏ
Ｃｈａｎｎｅｌ Ａｒｃｈｉｔｅｃｔｕｒｅ（ＭＣ
Ａ）バス、Ｅｎｈａｎｃｅｄ ＩＳＡ（ＥＩＳＡ）バ
ス、Ｖｉｄｅｏ Ｅｌｅｃｔｒｏｎｉｃｓ Ｓｔａｎｄ
ａｒｄｓ Ａｓｓｏｃｉａｔｅ（ＶＥＳＡ）ローカルバ
ス、およびＭｅｚｚａｎｉｎｅバスとしても知られてい
るＰｅｒｉｐｈｅｒａｌ Ｃｏｍｐｏｎｅｎｔ Ｉｎｔ
ｅｒｃｏｎｎｅｃｔ（ＰＣＩ）バスが含まれる。
【００２７】コンピュータ１１０は、一般に様々なコン
ピュータ可読媒体を含む。コンピュータ可読媒体は、コ
ンピュータ１１０によってアクセス可能ないかなる使用
可能な媒体であってもよく、揮発性媒体および不揮発性
媒体、取り外し可能媒体および非取り外し可能媒体の両
方を含むものである。限定はしないが例示として、コン
ピュータ可読媒体は、コンピュータ記憶媒体と通信媒体
とを含むことができる。コンピュータ記憶媒体は、コン
ピュータ可読命令、データ構造、プログラムモジュール
または他のデータなどの情報格納用のいかなる方法また
は技術で実施される揮発性および不揮発性、取り外し可
能および非取り外し可能媒体の両方を含む。コンピュー
タ記憶媒体は、限定はしないが、ＲＡＭ、ＲＯＭ、ＥＥ
ＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、Ｃ
Ｄ−ＲＯＭ、デジタル多目的ディスク（ＤＶＤ）または
他の光ディスクストレージ、磁気カセット、磁気テー
プ、磁気ディスクストレージまたは他の磁気記憶装置、
所望の情報を格納するために使用され、またコンピュー
タ１１０によってアクセスすることができる他のいかな
る媒体をも含む。通信媒体は、通常、コンピュータ可読
命令、データ構造、プログラムモジュールまたは搬送波
または他の搬送メカニズムなどの変調されたデータ信号
形式の他のデータを組み込むものであり、いかなる情報
伝達媒体をも含むものである。「変調されたデータ信
号」という用語は、１つまたは複数のその特徴的な設定
を有する信号、または信号中に情報を符号化するような
方法で変更された信号を意味している。限定はしないが
例示として、通信媒体は、有線ネットワークまたは直接
有線接続などの有線媒体と、音波、ＲＦ、赤外線または
他の無線媒体などの無線媒体を含む。コンピュータ可読
媒体の範囲には、上記のいかなる組合せも含まれるべき
である。
ピュータ可読媒体を含む。コンピュータ可読媒体は、コ
ンピュータ１１０によってアクセス可能ないかなる使用
可能な媒体であってもよく、揮発性媒体および不揮発性
媒体、取り外し可能媒体および非取り外し可能媒体の両
方を含むものである。限定はしないが例示として、コン
ピュータ可読媒体は、コンピュータ記憶媒体と通信媒体
とを含むことができる。コンピュータ記憶媒体は、コン
ピュータ可読命令、データ構造、プログラムモジュール
または他のデータなどの情報格納用のいかなる方法また
は技術で実施される揮発性および不揮発性、取り外し可
能および非取り外し可能媒体の両方を含む。コンピュー
タ記憶媒体は、限定はしないが、ＲＡＭ、ＲＯＭ、ＥＥ
ＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、Ｃ
Ｄ−ＲＯＭ、デジタル多目的ディスク（ＤＶＤ）または
他の光ディスクストレージ、磁気カセット、磁気テー
プ、磁気ディスクストレージまたは他の磁気記憶装置、
所望の情報を格納するために使用され、またコンピュー
タ１１０によってアクセスすることができる他のいかな
る媒体をも含む。通信媒体は、通常、コンピュータ可読
命令、データ構造、プログラムモジュールまたは搬送波
または他の搬送メカニズムなどの変調されたデータ信号
形式の他のデータを組み込むものであり、いかなる情報
伝達媒体をも含むものである。「変調されたデータ信
号」という用語は、１つまたは複数のその特徴的な設定
を有する信号、または信号中に情報を符号化するような
方法で変更された信号を意味している。限定はしないが
例示として、通信媒体は、有線ネットワークまたは直接
有線接続などの有線媒体と、音波、ＲＦ、赤外線または
他の無線媒体などの無線媒体を含む。コンピュータ可読
媒体の範囲には、上記のいかなる組合せも含まれるべき
である。
【００２８】システムメモリ１３０は、読み出し専用メ
モリ（ＲＯＭ）１３１およびランダムアクセスメモリ
（ＲＡＭ）１３２などの揮発性および／または不揮発性
メモリ形式のコンピュータ記憶媒体を含む。起動中など
に、コンピュータ１１０内の要素（エレメント）間で情
報を転送するために役立つ基本ルーチンを含んでいる基
本入出力システム１３３（ＢＩＯＳ）は、一般にＲＯＭ
１３１内に格納されている。ＲＡＭ１３２は、一般に、
処理ユニット１２０に即時アクセス可能な、かつ／また
はその時点において処理ユニット１２０により操作され
ているデータおよび／またはプログラムモジュールを含
む。限定はしないが例示として、図１に、オペレーティ
ングシステム１３４、アプリケーションプログラム１３
５、他のプログラムモジュール１３６およびプログラム
データ１３７を示す。
モリ（ＲＯＭ）１３１およびランダムアクセスメモリ
（ＲＡＭ）１３２などの揮発性および／または不揮発性
メモリ形式のコンピュータ記憶媒体を含む。起動中など
に、コンピュータ１１０内の要素（エレメント）間で情
報を転送するために役立つ基本ルーチンを含んでいる基
本入出力システム１３３（ＢＩＯＳ）は、一般にＲＯＭ
１３１内に格納されている。ＲＡＭ１３２は、一般に、
処理ユニット１２０に即時アクセス可能な、かつ／また
はその時点において処理ユニット１２０により操作され
ているデータおよび／またはプログラムモジュールを含
む。限定はしないが例示として、図１に、オペレーティ
ングシステム１３４、アプリケーションプログラム１３
５、他のプログラムモジュール１３６およびプログラム
データ１３７を示す。
【００２９】コンピュータ１１０は、他の取り外し可能
／非取り外し可能、揮発性／不揮発性コンピュータ記憶
媒体を含むこともできる。例示として、図１に、非取り
外し可能な不揮発性磁気媒体に対して読み出しまたは書
込みするハードディスクドライブ１４１、取り外し可能
な不揮発性磁気ディスク１５２に対して読み出しまたは
書込みする磁気ディスクドライブ１５１、取り外し可能
な不揮発性光ディスク１５６に対して読み出しまたは書
込みをする、ＣＤ ＲＯＭまたは他の光学媒体などの光
ディスクドライブ１５５を示す。例示的オペレーティン
グ環境で使用することができる他の取り外し可能／非取
り外し可能な揮発性／不揮発性コンピュータ記憶媒体
は、限定はしないが、磁気テープカセット、フラッシュ
メモリカード、デジタル多目的ディスク、デジタルビデ
オテープ、半導体ＲＡＭ、半導体ＲＯＭなどを含む。ハ
ードディスクドライブ１４１は、一般に、インターフェ
ース１４０などの非取り外し可能なメモリインターフェ
ースを介してシステムバス１２１に接続されており、磁
気ディスクドライブ１５１と光ディスクドライブ１５５
は、一般に、インターフェース１５０などの取り外し可
能なメモリインターフェースによってシステムバス１２
１に接続されている。
／非取り外し可能、揮発性／不揮発性コンピュータ記憶
媒体を含むこともできる。例示として、図１に、非取り
外し可能な不揮発性磁気媒体に対して読み出しまたは書
込みするハードディスクドライブ１４１、取り外し可能
な不揮発性磁気ディスク１５２に対して読み出しまたは
書込みする磁気ディスクドライブ１５１、取り外し可能
な不揮発性光ディスク１５６に対して読み出しまたは書
込みをする、ＣＤ ＲＯＭまたは他の光学媒体などの光
ディスクドライブ１５５を示す。例示的オペレーティン
グ環境で使用することができる他の取り外し可能／非取
り外し可能な揮発性／不揮発性コンピュータ記憶媒体
は、限定はしないが、磁気テープカセット、フラッシュ
メモリカード、デジタル多目的ディスク、デジタルビデ
オテープ、半導体ＲＡＭ、半導体ＲＯＭなどを含む。ハ
ードディスクドライブ１４１は、一般に、インターフェ
ース１４０などの非取り外し可能なメモリインターフェ
ースを介してシステムバス１２１に接続されており、磁
気ディスクドライブ１５１と光ディスクドライブ１５５
は、一般に、インターフェース１５０などの取り外し可
能なメモリインターフェースによってシステムバス１２
１に接続されている。
【００３０】図１に示す上記のドライブおよびそれらに
関連したコンピュータ記憶媒体は、コンピュータ可読命
令、データ構造、プログラムモジュールおよびコンピュ
ータ１１０のための他のデータの記憶装置を提供する。
図１では、例えば、ハードディスクドライブ１４１は、
オペレーティングシステム１４４、アプリケーションプ
ログラム１４５、他のプログラムモジュール１４６およ
びプログラムデータ１４７を格納しているものとして示
されている。これらの構成要素は、オペレーティングシ
ステム１３４、アプリケーションプログラム１３５、他
のプログラムモジュール１３６およびプログラムデータ
１３７と同じであっても異なっていても良いということ
に留意されたい。オペレーティングシステム１４４、ア
プリケーションプログラム１４５、その他のプログラム
モジュール１４６、およびプログラムデータ１４７に
は、最低限、それらが異なるコピーであることを示すた
めに異なる番号が与えられている。ユーザは、キーボー
ド１６２および、一般にマウス、トラックボールまたは
タッチパッドと呼ばれるポインティングデバイス１６１
などの入力デバイスによってコンピュータ１１０にコマ
ンドおよび情報を入力することができる。他の入力デバ
イス（図示せず）は、マイクロフォン、ジョイスティッ
ク、ゲームパッド、衛星放送アンテナ、スキャナなどを
含むことができる。これらのおよび他の入力デバイス
は、システムバスに結合されたユーザ入力インターフェ
ース１６０を介して処理ユニット１２０に接続されるこ
とがしばしばあるが、パラレルポート、ゲームポートま
たはユニバーサルシリアルバス（ＵＳＢ）などの他のイ
ンターフェースおよびバス構造に接続されることもでき
る。モニタ１９１または他のタイプの表示装置も、ビデ
オインターフェース１９０などのインターフェースを介
してシステムバス１２１に接続される。モニタの他に、
コンピュータは、出力周辺インターフェース１９５を介
して接続することができるスピーカ１９７およびプリン
タ１９６など、他の周辺出力装置を含むこともできる。
関連したコンピュータ記憶媒体は、コンピュータ可読命
令、データ構造、プログラムモジュールおよびコンピュ
ータ１１０のための他のデータの記憶装置を提供する。
図１では、例えば、ハードディスクドライブ１４１は、
オペレーティングシステム１４４、アプリケーションプ
ログラム１４５、他のプログラムモジュール１４６およ
びプログラムデータ１４７を格納しているものとして示
されている。これらの構成要素は、オペレーティングシ
ステム１３４、アプリケーションプログラム１３５、他
のプログラムモジュール１３６およびプログラムデータ
１３７と同じであっても異なっていても良いということ
に留意されたい。オペレーティングシステム１４４、ア
プリケーションプログラム１４５、その他のプログラム
モジュール１４６、およびプログラムデータ１４７に
は、最低限、それらが異なるコピーであることを示すた
めに異なる番号が与えられている。ユーザは、キーボー
ド１６２および、一般にマウス、トラックボールまたは
タッチパッドと呼ばれるポインティングデバイス１６１
などの入力デバイスによってコンピュータ１１０にコマ
ンドおよび情報を入力することができる。他の入力デバ
イス（図示せず）は、マイクロフォン、ジョイスティッ
ク、ゲームパッド、衛星放送アンテナ、スキャナなどを
含むことができる。これらのおよび他の入力デバイス
は、システムバスに結合されたユーザ入力インターフェ
ース１６０を介して処理ユニット１２０に接続されるこ
とがしばしばあるが、パラレルポート、ゲームポートま
たはユニバーサルシリアルバス（ＵＳＢ）などの他のイ
ンターフェースおよびバス構造に接続されることもでき
る。モニタ１９１または他のタイプの表示装置も、ビデ
オインターフェース１９０などのインターフェースを介
してシステムバス１２１に接続される。モニタの他に、
コンピュータは、出力周辺インターフェース１９５を介
して接続することができるスピーカ１９７およびプリン
タ１９６など、他の周辺出力装置を含むこともできる。
【００３１】コンピュータ１１０は、遠隔コンピュータ
１８０などの１つまたは複数の遠隔コンピュータへの論
理接続を使用してネットワーク化された環境において動
作することができる。遠隔コンピュータ１８０は、別の
パーソナルコンピュータ、サーバ、ルータ、ネットワー
クＰＣ、ピアデバイスまたは他の共通ネットワークノー
ドであってよく、図１では記憶装置１８１しか示してい
ないが、一般にパーソナルコンピュータ１１０に関して
上記で説明した多くのまたはすべての要素を含む。図１
で示す論理接続は、ローカルエリアネットワーク（ＬＡ
Ｎ）１７１およびワイドエリアネットワーク（ＷＡＮ）
１７３を含むが、他のネットワークを含むこともでき
る。このようなネットワーキング環境は、事務所、企業
全体に巡らされているコンピュータネットワーク、イン
トラネットおよびインターネットでは一般的なことであ
る。
１８０などの１つまたは複数の遠隔コンピュータへの論
理接続を使用してネットワーク化された環境において動
作することができる。遠隔コンピュータ１８０は、別の
パーソナルコンピュータ、サーバ、ルータ、ネットワー
クＰＣ、ピアデバイスまたは他の共通ネットワークノー
ドであってよく、図１では記憶装置１８１しか示してい
ないが、一般にパーソナルコンピュータ１１０に関して
上記で説明した多くのまたはすべての要素を含む。図１
で示す論理接続は、ローカルエリアネットワーク（ＬＡ
Ｎ）１７１およびワイドエリアネットワーク（ＷＡＮ）
１７３を含むが、他のネットワークを含むこともでき
る。このようなネットワーキング環境は、事務所、企業
全体に巡らされているコンピュータネットワーク、イン
トラネットおよびインターネットでは一般的なことであ
る。
【００３２】ＬＡＮネットワーキング環境で使用される
とき、パーソナルコンピュータ１１０は、ネットワーク
インターフェースまたはアダプタ１７０を介してＬＡＮ
１７１に接続される。ＷＡＮネットワーキング環境で使
用されるとき、コンピュータ１１０は、通常、インター
ネットなどのＷＡＮ１７３を介して通信を確立するモデ
ム１７２または他の手段を含む。内部であっても外部で
あってもよいモデム１７２は、ユーザ入力インターフェ
ース１６０または他の適切なメカニズムを介してシステ
ムバス１２１に接続することができる。ネットワーク環
境において、パーソナルコンピュータ１１０に関して示
されたプログラムモジュールまたはその一部は、遠隔記
憶装置に格納することができる。限定はしないが例示と
して、図１に、記憶装置１８１上に常駐するものとして
遠隔アプリケーションプログラム１８５を示す。図示す
るネットワーク接続は一例であり、コンピュータ間で通
信リンクを確立する他の手段を使用することもできるこ
とを理解されたい。
とき、パーソナルコンピュータ１１０は、ネットワーク
インターフェースまたはアダプタ１７０を介してＬＡＮ
１７１に接続される。ＷＡＮネットワーキング環境で使
用されるとき、コンピュータ１１０は、通常、インター
ネットなどのＷＡＮ１７３を介して通信を確立するモデ
ム１７２または他の手段を含む。内部であっても外部で
あってもよいモデム１７２は、ユーザ入力インターフェ
ース１６０または他の適切なメカニズムを介してシステ
ムバス１２１に接続することができる。ネットワーク環
境において、パーソナルコンピュータ１１０に関して示
されたプログラムモジュールまたはその一部は、遠隔記
憶装置に格納することができる。限定はしないが例示と
して、図１に、記憶装置１８１上に常駐するものとして
遠隔アプリケーションプログラム１８５を示す。図示す
るネットワーク接続は一例であり、コンピュータ間で通
信リンクを確立する他の手段を使用することもできるこ
とを理解されたい。
【００３３】以下の説明では、本発明は、特に指摘しな
い限り、１つまたは複数のコンピュータによって実行す
ることができる動作と演算の記号表現とを参照して説明
する。したがって、コンピュータによって実行されると
きに時折表現されることのあるこのような動作および演
算には、コンピュータの処理ユニットによる、構造化形
式のデータを表現する電子信号の操作が含まれることを
理解されたい。この操作はデータを変換するか、または
コンピュータのメモリシステム中の記憶場所にデータを
維持し、そこで、当業者が良く理解している方法でコン
ピュータの演算を再構成あるいは変更する。データが維
持されているデータ構造は、データ形式によって規定さ
れる特定の特性を有するメモリの物理的な記憶場所であ
る。本発明を上記の条件で説明してはいるが、以下で説
明する様々な動作および演算はハードウェアでも実施可
能であることを当業者なら理解するように、この説明は
限定を意図するものではない。
い限り、１つまたは複数のコンピュータによって実行す
ることができる動作と演算の記号表現とを参照して説明
する。したがって、コンピュータによって実行されると
きに時折表現されることのあるこのような動作および演
算には、コンピュータの処理ユニットによる、構造化形
式のデータを表現する電子信号の操作が含まれることを
理解されたい。この操作はデータを変換するか、または
コンピュータのメモリシステム中の記憶場所にデータを
維持し、そこで、当業者が良く理解している方法でコン
ピュータの演算を再構成あるいは変更する。データが維
持されているデータ構造は、データ形式によって規定さ
れる特定の特性を有するメモリの物理的な記憶場所であ
る。本発明を上記の条件で説明してはいるが、以下で説
明する様々な動作および演算はハードウェアでも実施可
能であることを当業者なら理解するように、この説明は
限定を意図するものではない。
【００３４】上記で説明したように、対等の関係を確立
することはＦｒｅｅｎｅｔでは費用の掛かる方法であ
る。これは、既存の関連付けに沿ってのみ要求とファイ
ルを転送することができる比較的静的なグラフを要求す
る。しかし、ピア当たりの関連付け数が増加するに伴
い、応答率は向上した。これは、ピアが即座に関係を構
築することが許可されている場合は、より良い結果を得
ることができるということを示している。別の報告は、
ナレッジテーブルのＬＲＵ管理は逆効果を生じる場合が
あるということである。クラスタリング効果が発生する
場合があるが、これは偶然に発生するものである。照会
の結果による新しい情報の到着は、実際には無用なノイ
ズ中にある有用な情報によって引き出される場合があ
る。本発明のシステムでは、情報管理は、ローカルピア
のキーに最も類似したキーを特に許可する。
することはＦｒｅｅｎｅｔでは費用の掛かる方法であ
る。これは、既存の関連付けに沿ってのみ要求とファイ
ルを転送することができる比較的静的なグラフを要求す
る。しかし、ピア当たりの関連付け数が増加するに伴
い、応答率は向上した。これは、ピアが即座に関係を構
築することが許可されている場合は、より良い結果を得
ることができるということを示している。別の報告は、
ナレッジテーブルのＬＲＵ管理は逆効果を生じる場合が
あるということである。クラスタリング効果が発生する
場合があるが、これは偶然に発生するものである。照会
の結果による新しい情報の到着は、実際には無用なノイ
ズ中にある有用な情報によって引き出される場合があ
る。本発明のシステムでは、情報管理は、ローカルピア
のキーに最も類似したキーを特に許可する。
【００３５】本発明のシステムの一実施形態では、各ノ
ードは、ネットワーク中の他のノードへの参照リストを
含んでいるルーティングテーブルを蓄積する。ノードの
項目ごとに、ノードＩＤを含めることができるアドレス
情報、アドレス、ノードのキー、このノードのキーとロ
ーカルノードのキーとの間の距離を獲得することができ
る。ローカルノードは、遠隔ノードに関して学習する度
に、そのノードを既に知っているか否かを検査し、知ら
ない場合は、項目の１つをルーティングテーブルに入れ
るか否かを検査する。これは、項目数がサイズの限界に
達していない場合は常に行われる。サイズの限界に達す
ると、任意の新しい項目が既存の項目に置き換えられる
ことになるが、それには名前空間中に十分に空間のある
項目を発見しようとする戦略、そのローカルノードに最
も近接した項目を選択しようとする戦略、または置き換
えられるべき既存の項目を単にアトランダムに選択する
戦略など、幾つかの実施態様の戦略がある。このように
して、ルーティングテーブルは、アクティブな近接局を
含むように常に更新される。この置き換え方法は、送信
する近接局に影響を与えるものではない。これらの近接
局項目は、グラフが設定されたときに作成される。ある
程度の接続性を維持するために、一実施形態ではこの制
限が使用される。好ましい実施形態では、この置き換え
戦略は、ユーティリティの基準に基づくのではなく、キ
ャッシュレベルごとにランダムである。各項目は、キャ
ッシュ所有者からのその「距離」によって決定される
「理想的なキャッシュレベル」を有する。新しい項目
は、その項目の「理想的なキャッシュレベル」がまだ破
られていない場合のみ、それら項目の距離に対応するキ
ャッシュレベルに、または最低レベルに追加することが
できる。
ードは、ネットワーク中の他のノードへの参照リストを
含んでいるルーティングテーブルを蓄積する。ノードの
項目ごとに、ノードＩＤを含めることができるアドレス
情報、アドレス、ノードのキー、このノードのキーとロ
ーカルノードのキーとの間の距離を獲得することができ
る。ローカルノードは、遠隔ノードに関して学習する度
に、そのノードを既に知っているか否かを検査し、知ら
ない場合は、項目の１つをルーティングテーブルに入れ
るか否かを検査する。これは、項目数がサイズの限界に
達していない場合は常に行われる。サイズの限界に達す
ると、任意の新しい項目が既存の項目に置き換えられる
ことになるが、それには名前空間中に十分に空間のある
項目を発見しようとする戦略、そのローカルノードに最
も近接した項目を選択しようとする戦略、または置き換
えられるべき既存の項目を単にアトランダムに選択する
戦略など、幾つかの実施態様の戦略がある。このように
して、ルーティングテーブルは、アクティブな近接局を
含むように常に更新される。この置き換え方法は、送信
する近接局に影響を与えるものではない。これらの近接
局項目は、グラフが設定されたときに作成される。ある
程度の接続性を維持するために、一実施形態ではこの制
限が使用される。好ましい実施形態では、この置き換え
戦略は、ユーティリティの基準に基づくのではなく、キ
ャッシュレベルごとにランダムである。各項目は、キャ
ッシュ所有者からのその「距離」によって決定される
「理想的なキャッシュレベル」を有する。新しい項目
は、その項目の「理想的なキャッシュレベル」がまだ破
られていない場合のみ、それら項目の距離に対応するキ
ャッシュレベルに、または最低レベルに追加することが
できる。
【００３６】本発明のシステムでは、ノードは照会を受
信すると、その項目を発見するために、既に訪問済みの
ノード以外の、ターゲットと最も良く一致するキーを有
するルーティングテーブル内をサーチする。次いで照会
は、その項目を公表したノードに直接的に転送される。
適切な項目がない場合、要求はその要求がそこから受信
されたノードに返送され、このノードはそれ自体のルー
ティングテーブル内にある別の項目を試みる。要求がタ
ーゲットにキーが一致している項目に到着した場合、要
求は成功である。ターゲットがステップの最大数まで達
していない場合、または、要求がそこから受信されたノ
ードがすべての可能性のある近接局を試して否定応答を
受信した場合、要求は不成功である。要求が成功した場
合、応答がすべての中間ホップによって中継される。応
答は、そのターゲットキーを保持するノードのアドレス
を伝えるが、この項目は中間ノードのルーティングテー
ブルに挿入することができる。
信すると、その項目を発見するために、既に訪問済みの
ノード以外の、ターゲットと最も良く一致するキーを有
するルーティングテーブル内をサーチする。次いで照会
は、その項目を公表したノードに直接的に転送される。
適切な項目がない場合、要求はその要求がそこから受信
されたノードに返送され、このノードはそれ自体のルー
ティングテーブル内にある別の項目を試みる。要求がタ
ーゲットにキーが一致している項目に到着した場合、要
求は成功である。ターゲットがステップの最大数まで達
していない場合、または、要求がそこから受信されたノ
ードがすべての可能性のある近接局を試して否定応答を
受信した場合、要求は不成功である。要求が成功した場
合、応答がすべての中間ホップによって中継される。応
答は、そのターゲットキーを保持するノードのアドレス
を伝えるが、この項目は中間ノードのルーティングテー
ブルに挿入することができる。
【００３７】一実施形態では、ノード識別子はランダム
に選択された整数であり、二進法の補数として表わされ
る。この表記法において、ｎビット形式では、番号は−
２（ ｎ−１）と２（ｎ−１）−１との間を変動する。距
離関数は、これら２つの整数の間の絶対差を計算する。
これによって、端点−２（ｎ−１）と２（ｎ−１）−１
の間の距離が１である円形空間が提供される。この円形
番号空間１８２の一例を図２に示す。Ｎ個のノードのネ
ットワークでは、その円形番号空間内のランダムに間隔
をおいて配置したＮ個の識別子が選択される。ノード
が、それ自体の識別子に最も近い識別子を有するＫ個の
ノード識別子を含んでいるＫ個の項目のキャッシュを蓄
積している場合、そのキャッシュを、その平均角の大き
さがα＝２πＫ／Ｎであるその円形空間の小域をカバー
するように参照することができる。
に選択された整数であり、二進法の補数として表わされ
る。この表記法において、ｎビット形式では、番号は−
２（ ｎ−１）と２（ｎ−１）−１との間を変動する。距
離関数は、これら２つの整数の間の絶対差を計算する。
これによって、端点−２（ｎ−１）と２（ｎ−１）−１
の間の距離が１である円形空間が提供される。この円形
番号空間１８２の一例を図２に示す。Ｎ個のノードのネ
ットワークでは、その円形番号空間内のランダムに間隔
をおいて配置したＮ個の識別子が選択される。ノード
が、それ自体の識別子に最も近い識別子を有するＫ個の
ノード識別子を含んでいるＫ個の項目のキャッシュを蓄
積している場合、そのキャッシュを、その平均角の大き
さがα＝２πＫ／Ｎであるその円形空間の小域をカバー
するように参照することができる。
【００３８】識別子Ｘのノードが識別子Ｙに対する照会
を受信すると、ＸとＹの角距離はβ＝２π｜Ｘ−Ｙ｜／
２ｎで表わすことができる。βがα／２よりも小さい場
合、そのノードは、以下で議論するように、この近接し
た小域内のピアのほとんどすべてを認識することになる
ので、Ｙはそのローカルキャッシュ中のＫ個の項目のう
ちの１つであるはずである。ターゲットは既に発見され
ている。この他の場合、ノードはＹに最も近い項目を選
択することになる。その項目は小域のエッジの１つにな
るが、これは次のステップ（ホップ）では角距離が平均
でα／２だけ低減されるということである。次のホップ
（識別子Ｘ′を有する）でも、ターゲットが発見される
までこのプロセスが反復される。図２に示すように、所
望のターゲットＹを発見するためには、識別子Ｘ″を有
するノードへのさらなるホップが必要となる。βの最大
値は２（ｎ−１）の距離に対応するπであり、ここでＮ
／２個の項目の平均が発見される。各ステップ（ホッ
プ）は、Ｋ／２個の項目に対応するα／２だけ角度を小
さくする。十分な数のステップ（ホップ）の後、要求は
ターゲットに到着することが保証される。α／２がπＫ
／Ｎに対応し、最大角度がπなので、ステップの最大数
はＨ＝π／（α／２）＝Ｎ／Ｋである。成功すると、各
ノードは、円形番号空間の連続した小域の少なくとも１
つのノードに関する情報を獲得する。この情報は、絶え
ず深まる情報の階層を有するマルチレベルキャッシュ
（下記で説明する）を構築するために使用される。
を受信すると、ＸとＹの角距離はβ＝２π｜Ｘ−Ｙ｜／
２ｎで表わすことができる。βがα／２よりも小さい場
合、そのノードは、以下で議論するように、この近接し
た小域内のピアのほとんどすべてを認識することになる
ので、Ｙはそのローカルキャッシュ中のＫ個の項目のう
ちの１つであるはずである。ターゲットは既に発見され
ている。この他の場合、ノードはＹに最も近い項目を選
択することになる。その項目は小域のエッジの１つにな
るが、これは次のステップ（ホップ）では角距離が平均
でα／２だけ低減されるということである。次のホップ
（識別子Ｘ′を有する）でも、ターゲットが発見される
までこのプロセスが反復される。図２に示すように、所
望のターゲットＹを発見するためには、識別子Ｘ″を有
するノードへのさらなるホップが必要となる。βの最大
値は２（ｎ−１）の距離に対応するπであり、ここでＮ
／２個の項目の平均が発見される。各ステップ（ホッ
プ）は、Ｋ／２個の項目に対応するα／２だけ角度を小
さくする。十分な数のステップ（ホップ）の後、要求は
ターゲットに到着することが保証される。α／２がπＫ
／Ｎに対応し、最大角度がπなので、ステップの最大数
はＨ＝π／（α／２）＝Ｎ／Ｋである。成功すると、各
ノードは、円形番号空間の連続した小域の少なくとも１
つのノードに関する情報を獲得する。この情報は、絶え
ず深まる情報の階層を有するマルチレベルキャッシュ
（下記で説明する）を構築するために使用される。
【００３９】これは、本発明のシステムが成功する１つ
の理由を示している。しかし、ホップ回数を少なく維持
するために、キャッシュのサイズはネットワークのサイ
ズと共に線形に増大する必要があるということも示して
いるが、これは許容できることではない。実用的である
ために、このシステムは線形よりも適した方法でスケー
リングする必要がある。解決法はマルチレベルキャッシ
ュを使用すること、すなわちルーティングキャッシュ
を、１つはローカルキーに最も近いキーを有する項目を
含んでおり、もう１つはアトランダムに選択された項目
を含んでいる２つの部分に分割することである。図のよ
うに、第１のキャッシュはＫ１項目を含んでおり、第２
のキャッシュはＫ２項目を含んでいると仮定する。要求
を処理する第１のノードは、ターゲットに最も近いキー
を有する項目を選択する。その項目がセットＫ１中にあ
る場合（角度αに対応する）、この処理は完了する。こ
の項目がセットＫ２中にある場合、ターゲットＸと選択
された項目Ｙとの間の最大距離は、セットＫ２中の２つ
の項目間の距離の半分以下になる。これらの項目が均等
に間隔を置いて配置されている場合、その距離は２
（ｎ−１）／Ｋ２であり、対応する角度はβ＝π／Ｋ２
となる。次のノードで、照会は上記の要領で処理され
る。各ホップは、α＝２πＫ１／Ｎとして、少なくとも
α／２だけ角度の減少を受けることになる。したがっ
て、ホップのこの数はＨ＝１＋２・β／α＝１＋Ｎ／
（Ｋ１・Ｋ２）である。Ｋ＝Ｋ１＋Ｋ２に対する所与の
合計数に関して、Ｋ１＝Ｋ２＝Ｋ／２である場合、Ｈの
最低数が得られる。この場合はＨ＝１＋Ｎ／（Ｋ／２）
２である。
の理由を示している。しかし、ホップ回数を少なく維持
するために、キャッシュのサイズはネットワークのサイ
ズと共に線形に増大する必要があるということも示して
いるが、これは許容できることではない。実用的である
ために、このシステムは線形よりも適した方法でスケー
リングする必要がある。解決法はマルチレベルキャッシ
ュを使用すること、すなわちルーティングキャッシュ
を、１つはローカルキーに最も近いキーを有する項目を
含んでおり、もう１つはアトランダムに選択された項目
を含んでいる２つの部分に分割することである。図のよ
うに、第１のキャッシュはＫ１項目を含んでおり、第２
のキャッシュはＫ２項目を含んでいると仮定する。要求
を処理する第１のノードは、ターゲットに最も近いキー
を有する項目を選択する。その項目がセットＫ１中にあ
る場合（角度αに対応する）、この処理は完了する。こ
の項目がセットＫ２中にある場合、ターゲットＸと選択
された項目Ｙとの間の最大距離は、セットＫ２中の２つ
の項目間の距離の半分以下になる。これらの項目が均等
に間隔を置いて配置されている場合、その距離は２
（ｎ−１）／Ｋ２であり、対応する角度はβ＝π／Ｋ２
となる。次のノードで、照会は上記の要領で処理され
る。各ホップは、α＝２πＫ１／Ｎとして、少なくとも
α／２だけ角度の減少を受けることになる。したがっ
て、ホップのこの数はＨ＝１＋２・β／α＝１＋Ｎ／
（Ｋ１・Ｋ２）である。Ｋ＝Ｋ１＋Ｋ２に対する所与の
合計数に関して、Ｋ１＝Ｋ２＝Ｋ／２である場合、Ｈの
最低数が得られる。この場合はＨ＝１＋Ｎ／（Ｋ／２）
２である。
【００４０】識別子のサイズはネットワークのサイズに
よって変動する場合があり、２進数の補数として表わす
必要はない。しかし、プロトコルの主要な要件は、ノー
ド識別子を、最小値ＮＭＩＮと最大値ＮＭＡＸとの間を
変動する整数として扱うことができるということであ
る。この空間では、ＤＭＡＸ＝（ＮＭＡＸ−ＮＭＩＮ）
／２というように、ＤＭＡＸは２点間の最大距離と定義
することができる。このように、２つの識別子ＸとＹと
の間の距離Ｄは次のように定義される。（１）Ｘ＜Ｙで
ある場合、ＸとＹを置換する。（２）（（Ｘ−Ｙ）＜Ｄ
ＭＡＸ）の場合はＤ＝Ｘ−Ｙであり、そうでない場合は
Ｄ＝（ＮＭＡＸ＋１−Ｘ）＋（Ｙ−ＮＭＩＮ）である。
上記で指摘したように、番号が２論理の補数を使用して
２進法で格納されている場合、距離はＸとＹとの間の差
の絶対値として計算することができる。
よって変動する場合があり、２進数の補数として表わす
必要はない。しかし、プロトコルの主要な要件は、ノー
ド識別子を、最小値ＮＭＩＮと最大値ＮＭＡＸとの間を
変動する整数として扱うことができるということであ
る。この空間では、ＤＭＡＸ＝（ＮＭＡＸ−ＮＭＩＮ）
／２というように、ＤＭＡＸは２点間の最大距離と定義
することができる。このように、２つの識別子ＸとＹと
の間の距離Ｄは次のように定義される。（１）Ｘ＜Ｙで
ある場合、ＸとＹを置換する。（２）（（Ｘ−Ｙ）＜Ｄ
ＭＡＸ）の場合はＤ＝Ｘ−Ｙであり、そうでない場合は
Ｄ＝（ＮＭＡＸ＋１−Ｘ）＋（Ｙ−ＮＭＩＮ）である。
上記で指摘したように、番号が２論理の補数を使用して
２進法で格納されている場合、距離はＸとＹとの間の差
の絶対値として計算することができる。
【００４１】照会を処理するとき、最も適切な次のホッ
プを発見するためにキャッシュが使用される。これは、
中継リストにまだ列挙されていないアドレスを有するキ
ャッシュ項目のサブセットをまず発見することによって
行われる。そのサブセットが空である場合、失敗の指示
が戻される。しかし、そのサブセットが項目を１つだけ
含んでいる場合、その項目が戻される。そうでない場
合、要求されたターゲットに最も近い識別子を有する２
つの項目が発見される。これらの項目はＡおよびＢと命
名することができ、それぞれのターゲットへの距離はＤ
ＡおよびＤＢと命名することができる。本発明のプロト
コルは、Ａ（重みＤＢを有する）とＢ（重みＤＡを有す
る）との間でアトランダムに選択して、このランダムな
選択が戻される。
プを発見するためにキャッシュが使用される。これは、
中継リストにまだ列挙されていないアドレスを有するキ
ャッシュ項目のサブセットをまず発見することによって
行われる。そのサブセットが空である場合、失敗の指示
が戻される。しかし、そのサブセットが項目を１つだけ
含んでいる場合、その項目が戻される。そうでない場
合、要求されたターゲットに最も近い識別子を有する２
つの項目が発見される。これらの項目はＡおよびＢと命
名することができ、それぞれのターゲットへの距離はＤ
ＡおよびＤＢと命名することができる。本発明のプロト
コルは、Ａ（重みＤＢを有する）とＢ（重みＤＡを有す
る）との間でアトランダムに選択して、このランダムな
選択が戻される。
【００４２】本発明の別の実施形態では、キャッシュを
整除数の任意の数で割ることができる。例えばＰという
整除数がある場合、Ｋ／Ｐ個の項目を含む第１のセット
を有することになる。最大角度は、約β＝Ｐ／２Ｋであ
るべきである。次のホップは、次のレベルセットにおけ
る最適の一致を使用するが、それはＫ／Ｐ個の項目を含
み、Ｐ／Ｋのサイズの角上に拡散されている。そのホッ
プの後、残りの角はｂ′＝Ｐ２／２Ｋ２になる。これ
は、最後のセットに到達するまで続き、最後のセットに
達すると、角度はセット当たりα／２＝Ｋ／（ＰＮ）だ
け減少する。したがって、ホップの最大数はＨ＝Ｐ−１
＋Ｎ／（Ｋ／Ｐ）Ｐとなる。
整除数の任意の数で割ることができる。例えばＰという
整除数がある場合、Ｋ／Ｐ個の項目を含む第１のセット
を有することになる。最大角度は、約β＝Ｐ／２Ｋであ
るべきである。次のホップは、次のレベルセットにおけ
る最適の一致を使用するが、それはＫ／Ｐ個の項目を含
み、Ｐ／Ｋのサイズの角上に拡散されている。そのホッ
プの後、残りの角はｂ′＝Ｐ２／２Ｋ２になる。これ
は、最後のセットに到達するまで続き、最後のセットに
達すると、角度はセット当たりα／２＝Ｋ／（ＰＮ）だ
け減少する。したがって、ホップの最大数はＨ＝Ｐ−１
＋Ｎ／（Ｋ／Ｐ）Ｐとなる。
【００４３】図３に、５００個の項目キャッシュと様々
な値Ｐに対して予測されるホップ数を示す。この図の要
点は、ネットワークサイズが１０１０項目まで増大した
としても、キャッシュが５または６のデータセットに分
割される場合、要求は６以下のホップで解決されること
になるということが予測されることである。より小規模
なネットワークの場合は、より少ない分割で僅かに良い
結果を達成することができる。実際には、分割の最適数
はキャッシュのサイズとネットワークに予想されるサイ
ズによって変動する。上記の計算では、各データセット
においてキーが番号空間に沿って規則的に分配されてい
ると想定される。必ずしもこの通りでないネットワーク
においては、システムは項目数を２倍に増やすことを許
可することによって同様の能率を得ることができる。一
実施形態では、ノードは、要求を送信しているノードの
アドレスと識別子しか学習しない。別の実施形態では、
各要求を処理するノードは、要求側のアドレスと識別子
をも学習する。さらに別の実施形態では、要求が失敗し
た場合、ノードは、ターゲットがそのネットワーク上に
存在しなかったとしても、ターゲットに最も近い識別子
を有する局のアドレスと識別子をも学習する。
な値Ｐに対して予測されるホップ数を示す。この図の要
点は、ネットワークサイズが１０１０項目まで増大した
としても、キャッシュが５または６のデータセットに分
割される場合、要求は６以下のホップで解決されること
になるということが予測されることである。より小規模
なネットワークの場合は、より少ない分割で僅かに良い
結果を達成することができる。実際には、分割の最適数
はキャッシュのサイズとネットワークに予想されるサイ
ズによって変動する。上記の計算では、各データセット
においてキーが番号空間に沿って規則的に分配されてい
ると想定される。必ずしもこの通りでないネットワーク
においては、システムは項目数を２倍に増やすことを許
可することによって同様の能率を得ることができる。一
実施形態では、ノードは、要求を送信しているノードの
アドレスと識別子しか学習しない。別の実施形態では、
各要求を処理するノードは、要求側のアドレスと識別子
をも学習する。さらに別の実施形態では、要求が失敗し
た場合、ノードは、ターゲットがそのネットワーク上に
存在しなかったとしても、ターゲットに最も近い識別子
を有する局のアドレスと識別子をも学習する。
【００４４】マルチレベルキャッシュ１８４は、図４に
示すように視覚化することができる。図から分かるよう
に、キャッシュの各レベルは、そのレベルの限界を示す
ＭＩＮおよびＭＡＸ識別子の指定を含む。このＭＩＮ値
およびＭＡＸ値は、Ｎを番号空間のサイズとし、Ｘをロ
ーカルＩＤとした場合に、初期レベルに関してＭＩＮ＝
Ｘ−Ｎ／２、ＭＡＸ＝Ｘ＋Ｎ／２と決定される。各レベ
ル内にはノードによって知られている項目がある。連続
するレベル内で、Ｌをそのレベルの数とした場合、ＭＩ
ＮおよびＭＡＸは（Ｌ−１）／Ｋと定義される。
示すように視覚化することができる。図から分かるよう
に、キャッシュの各レベルは、そのレベルの限界を示す
ＭＩＮおよびＭＡＸ識別子の指定を含む。このＭＩＮ値
およびＭＡＸ値は、Ｎを番号空間のサイズとし、Ｘをロ
ーカルＩＤとした場合に、初期レベルに関してＭＩＮ＝
Ｘ−Ｎ／２、ＭＡＸ＝Ｘ＋Ｎ／２と決定される。各レベ
ル内にはノードによって知られている項目がある。連続
するレベル内で、Ｌをそのレベルの数とした場合、ＭＩ
ＮおよびＭＡＸは（Ｌ−１）／Ｋと定義される。
【００４５】本発明の一実施形態では、事前対応キャッ
シュ構築戦略が使用されるが、そこでは、各ノードがネ
ットワークに接続されている場合、各ノードは戦略的に
配置された識別子に対する連続した無償要求を送信す
る。１０００個のノードによるシミュレーションでは、
そのような９個の要求はそのキャッシュに入るに十分で
あると証明されており、したがってこのシミュレーショ
ン中に送信されるすべての照会は、平均３から４のホッ
プを使用して即座に対応された。しかし、それ以上の数
またはそれ以下の数のそのような要求を使用することも
できる。
シュ構築戦略が使用されるが、そこでは、各ノードがネ
ットワークに接続されている場合、各ノードは戦略的に
配置された識別子に対する連続した無償要求を送信す
る。１０００個のノードによるシミュレーションでは、
そのような９個の要求はそのキャッシュに入るに十分で
あると証明されており、したがってこのシミュレーショ
ン中に送信されるすべての照会は、平均３から４のホッ
プを使用して即座に対応された。しかし、それ以上の数
またはそれ以下の数のそのような要求を使用することも
できる。
【００４６】マルチレベルキャッシュは一組のＬ個のレ
ベルとして構成され、そのそれぞれは図４に示すように
最高Ｋ個の項目を保持している。キャッシュ内のレベル
数は、ネットワークのサイズおよび各区分内の項目数に
応じて変わる。ノードは、それ自体が接続すべきネット
ワークのサイズを事前に認識していないので、これは問
題を生じる原因となる。この理由から、ノードは「最後
のレベル」が満杯であることを認識すると、そのキャッ
シュに動的にレベルを１つ追加する。キャッシュの最後
のレベル内の項目数は、実際には、ネットワークサイズ
の優れた指針となる。このレベルは、２＊ＤＭＡＸ／
（Ｋ（Ｌ−１））のサイズの間隔内に入る識別子を有す
るノードの完全なサンプリングを含んでいると考えられ
る。キャッシュ内のレベル数が動的である場合、選択さ
れる必要のあるパラメータはキャッシュレベルあたりの
項目数だけである。このパラメータの選択は、照会解決
手順の効率と、キャッシュ内容をセットアップするため
に必要となる補助トラフィックの量との間における妥協
である。図５に、照会を解決するために必要となる平均
ホップ数がキャッシュのサイズに応じてどのように変化
するかを示す。この計算は、データがランダムに分配さ
れるということ、また、レベルごとのキャッシュの範囲
は、本明細書で指定した通りに計算されること、すなわ
ち、カバーしたサイズをレベルごとにＫ／２で割った数
であると想定している。
ベルとして構成され、そのそれぞれは図４に示すように
最高Ｋ個の項目を保持している。キャッシュ内のレベル
数は、ネットワークのサイズおよび各区分内の項目数に
応じて変わる。ノードは、それ自体が接続すべきネット
ワークのサイズを事前に認識していないので、これは問
題を生じる原因となる。この理由から、ノードは「最後
のレベル」が満杯であることを認識すると、そのキャッ
シュに動的にレベルを１つ追加する。キャッシュの最後
のレベル内の項目数は、実際には、ネットワークサイズ
の優れた指針となる。このレベルは、２＊ＤＭＡＸ／
（Ｋ（Ｌ−１））のサイズの間隔内に入る識別子を有す
るノードの完全なサンプリングを含んでいると考えられ
る。キャッシュ内のレベル数が動的である場合、選択さ
れる必要のあるパラメータはキャッシュレベルあたりの
項目数だけである。このパラメータの選択は、照会解決
手順の効率と、キャッシュ内容をセットアップするため
に必要となる補助トラフィックの量との間における妥協
である。図５に、照会を解決するために必要となる平均
ホップ数がキャッシュのサイズに応じてどのように変化
するかを示す。この計算は、データがランダムに分配さ
れるということ、また、レベルごとのキャッシュの範囲
は、本明細書で指定した通りに計算されること、すなわ
ち、カバーしたサイズをレベルごとにＫ／２で割った数
であると想定している。
【００４７】一実施形態では、Ｋの値をネットワークの
サイズ、ホップ数の限度などに応じて他の値に設定する
ことができるが、Ｋの値は２０に設定される。キャッシ
ュの各レベルは、ローカル識別子の最大距離によって特
徴付けられる。この距離は、２つの有効な識別子間の最
大距離であるＤＭＡＸの関数である。ＤＭＡＸは数空間
の関数であり、Ｎ／２に等しい係数Ｐの関数であり、キ
ャッシュレベルの関数である。最後のキャッシュレベル
は、ローカル識別子への距離がＤＭＡＸ／（Ｐ
（Ｌ−１））と同等かまたはそれよりも小さい項目を含
んでいる。最初のキャッシュレベルは、ローカル識別子
への距離がＤＭＡＸ／Ｐよりも大きい項目を含んでい
る。他のキャッシュレベルは、Ｌをレベルの値として、
ローカル識別子への距離がＤＭＡＸ／（ＰＬ）よりも大
きい項目を含んでいる。
サイズ、ホップ数の限度などに応じて他の値に設定する
ことができるが、Ｋの値は２０に設定される。キャッシ
ュの各レベルは、ローカル識別子の最大距離によって特
徴付けられる。この距離は、２つの有効な識別子間の最
大距離であるＤＭＡＸの関数である。ＤＭＡＸは数空間
の関数であり、Ｎ／２に等しい係数Ｐの関数であり、キ
ャッシュレベルの関数である。最後のキャッシュレベル
は、ローカル識別子への距離がＤＭＡＸ／（Ｐ
（Ｌ−１））と同等かまたはそれよりも小さい項目を含
んでいる。最初のキャッシュレベルは、ローカル識別子
への距離がＤＭＡＸ／Ｐよりも大きい項目を含んでい
る。他のキャッシュレベルは、Ｌをレベルの値として、
ローカル識別子への距離がＤＭＡＸ／（ＰＬ）よりも大
きい項目を含んでいる。
【００４８】ノードは、新しい項目に関して学習すると
き、それをキャッシュに挿入しようとする。これを行う
ために、ノードは次のステップを実施する。第１に、そ
の項目が既にキャッシュ内にあれば、その項目の証明
は、新しく学習した値が最新の値である場合は、その新
しく学習した値で置き換えられる。第２に、その項目が
まだキャッシュ内にない場合、その項目とローカル識別
子との間の距離が計算される。これは、その項目がキャ
ッシュされるべきレベルを決定するために使用される。
選択されたレベルが、その時点で存在しているキャッシ
ュの最後のレベルである場合、またそのレベルに対して
そのキャッシュ内にＫ個またはＫ＋１個以上の項目があ
る場合、新しいレベルが追加される（Ｌ＝Ｌ＋１と設定
される）。レベルＬの項目は、ローカル識別子への距離
に応じてこれら２つのレベル間に分割される。次いで、
新しい項目に関して選択されるレベルが再評価される。
このプロセスは必要に応じて反復される。しかしその選
択されたレベルに対するキャッシュ内にある項目数がＫ
個より少ない場合、新しい項目は単に追加されるだけで
ある。選択されたレベルに対するキャッシュ内にＫ個の
項目がある場合、および選択されたレベルがその時点で
存在するキャッシュの最後のレベルでない場合、新しい
項目が既存の項目に置き換えられるべきか否かを判定す
るために置換アルゴリズムが実施され、置き換えられる
べきであると判断された場合、どの項目と置き換えられ
るべきかを判定する。最も単純な置換アルゴリズムは
「ランダム置換」である。すなわち、Ｋキャッシュの項
目からアトランダムに１つの項目を選択し、それを新た
に学習した項目で置き換えることことである。最後に、
最後のレベルに新しい項目が追加された場合、以下で説
明するフラッディングアルゴリズムが実行される。
き、それをキャッシュに挿入しようとする。これを行う
ために、ノードは次のステップを実施する。第１に、そ
の項目が既にキャッシュ内にあれば、その項目の証明
は、新しく学習した値が最新の値である場合は、その新
しく学習した値で置き換えられる。第２に、その項目が
まだキャッシュ内にない場合、その項目とローカル識別
子との間の距離が計算される。これは、その項目がキャ
ッシュされるべきレベルを決定するために使用される。
選択されたレベルが、その時点で存在しているキャッシ
ュの最後のレベルである場合、またそのレベルに対して
そのキャッシュ内にＫ個またはＫ＋１個以上の項目があ
る場合、新しいレベルが追加される（Ｌ＝Ｌ＋１と設定
される）。レベルＬの項目は、ローカル識別子への距離
に応じてこれら２つのレベル間に分割される。次いで、
新しい項目に関して選択されるレベルが再評価される。
このプロセスは必要に応じて反復される。しかしその選
択されたレベルに対するキャッシュ内にある項目数がＫ
個より少ない場合、新しい項目は単に追加されるだけで
ある。選択されたレベルに対するキャッシュ内にＫ個の
項目がある場合、および選択されたレベルがその時点で
存在するキャッシュの最後のレベルでない場合、新しい
項目が既存の項目に置き換えられるべきか否かを判定す
るために置換アルゴリズムが実施され、置き換えられる
べきであると判断された場合、どの項目と置き換えられ
るべきかを判定する。最も単純な置換アルゴリズムは
「ランダム置換」である。すなわち、Ｋキャッシュの項
目からアトランダムに１つの項目を選択し、それを新た
に学習した項目で置き換えることことである。最後に、
最後のレベルに新しい項目が追加された場合、以下で説
明するフラッディングアルゴリズムが実行される。
【００４９】上記の要領で、ノードがキャッシュの最後
のレベル内に項目を１つ追加する際、または既存の項目
をより新しい値で置き換える場合、ノードはフラッディ
ング手順を行う。この手順を達成するために、既にフラ
ッドしているノードの空のリストを有するローカルノー
ドのアドレス証明を含んでいるフラッディングメッセー
ジを作成する。次いでこのメッセージが新しい項目のア
ドレスに送信される。次いで、新しい項目への距離がＤ
ＭＡＸ／（Ｐ（Ｌ−１））よりも小さいキャッシュ内の
ノードのリストが作成される。新しい項目の追加がフラ
ッディングメッセージの結果である場合、既にフラッド
したものとしてマーク付けされているノードがリストか
ら除去される。次いで、ノードは、新しい項目のアドレ
ス証明を含んでいるフラッディングメッセージを準備す
る。既にフラッドしたノードのリストがローカルノー
ド、リスト内のすべてのノード、およびフラッディング
メッセージからの追加結果である場合は、そのメッセー
ジ内で既にフラッドしたものとしてマーク付けされたす
べてのノードを含むように設定される。次いで、このメ
ッセージのコピーがリスト内のすべてのノードに送信さ
れる。容量が限定されているノードは、「フラッディン
グターゲット」のリストのサイズを制限する傾向を持つ
場合がある。制限する場合、これらのノードはそのリス
ト内にローカル識別子に最も近い識別子を有するノード
を保存すべきである。
のレベル内に項目を１つ追加する際、または既存の項目
をより新しい値で置き換える場合、ノードはフラッディ
ング手順を行う。この手順を達成するために、既にフラ
ッドしているノードの空のリストを有するローカルノー
ドのアドレス証明を含んでいるフラッディングメッセー
ジを作成する。次いでこのメッセージが新しい項目のア
ドレスに送信される。次いで、新しい項目への距離がＤ
ＭＡＸ／（Ｐ（Ｌ−１））よりも小さいキャッシュ内の
ノードのリストが作成される。新しい項目の追加がフラ
ッディングメッセージの結果である場合、既にフラッド
したものとしてマーク付けされているノードがリストか
ら除去される。次いで、ノードは、新しい項目のアドレ
ス証明を含んでいるフラッディングメッセージを準備す
る。既にフラッドしたノードのリストがローカルノー
ド、リスト内のすべてのノード、およびフラッディング
メッセージからの追加結果である場合は、そのメッセー
ジ内で既にフラッドしたものとしてマーク付けされたす
べてのノードを含むように設定される。次いで、このメ
ッセージのコピーがリスト内のすべてのノードに送信さ
れる。容量が限定されているノードは、「フラッディン
グターゲット」のリストのサイズを制限する傾向を持つ
場合がある。制限する場合、これらのノードはそのリス
ト内にローカル識別子に最も近い識別子を有するノード
を保存すべきである。
【００５０】上記のように、キャッシュ項目は、有効日
付を含んでいるアドレス証明によって表わされる。ネッ
トワーク内の他のノードに関するその時点における情報
を維持するために、また、古くなったデータの束を低減
するために、本発明の一実施形態では、キャッシュ項目
は有効日付の経過後、キャッシュから除去される。この
実施形態でネットワークに参加している各ノードは、し
たがって、そのアドレス証明を定期的に更新する。更新
の際、ノードがそのキャッシュにおける最後のレベル内
の新しい項目を学習したかのように新しい値がフラッド
される。このプロセスは、他のノードのキャッシュ内の
その項目が古くなったものとして除去されないことを保
証する。
付を含んでいるアドレス証明によって表わされる。ネッ
トワーク内の他のノードに関するその時点における情報
を維持するために、また、古くなったデータの束を低減
するために、本発明の一実施形態では、キャッシュ項目
は有効日付の経過後、キャッシュから除去される。この
実施形態でネットワークに参加している各ノードは、し
たがって、そのアドレス証明を定期的に更新する。更新
の際、ノードがそのキャッシュにおける最後のレベル内
の新しい項目を学習したかのように新しい値がフラッド
される。このプロセスは、他のノードのキャッシュ内の
その項目が古くなったものとして除去されないことを保
証する。
【００５１】定期的な間隔で、ノードはそれらのキャッ
シュの構造を検査し、各キャッシュレベルが適切に完了
していることを確認することが好ましい。最後のキャッ
シュレベルは常に完了しているものとみなされる。ま
た、Ｉをレベルの値とした場合、このレベルにおける２
つのキャッシュ項目間の最大の間隔が２＊ＤＭＡＸ／
（ＰＩ）よりも大きい場合は、他のすべてのキャッシュ
は完了していないものとみなされる。この場合、ノード
は、最大間隔の中間にターゲットが調整されている要求
メッセージをフォーマットし、この要求の標準的な処理
に従事することになる。
シュの構造を検査し、各キャッシュレベルが適切に完了
していることを確認することが好ましい。最後のキャッ
シュレベルは常に完了しているものとみなされる。ま
た、Ｉをレベルの値とした場合、このレベルにおける２
つのキャッシュ項目間の最大の間隔が２＊ＤＭＡＸ／
（ＰＩ）よりも大きい場合は、他のすべてのキャッシュ
は完了していないものとみなされる。この場合、ノード
は、最大間隔の中間にターゲットが調整されている要求
メッセージをフォーマットし、この要求の標準的な処理
に従事することになる。
【００５２】上記で説明したように、本発明のシステム
は任意のサイズのネットワークを取り扱うことができ
る。しかし、各ノードは正確に初期化されたキャッシュ
を有する必要がある。Ｆｒｅｅｎｅｔのように、ノード
は、要求の規則的な処理の副次的な作用として他のノー
ドに関して学習する。残念ながら、信頼できる性能を達
成するには自然な学習プロセスに単純に依存するだけで
は十分でない。したがって、本発明のシステムは、送信
する近接局との同期、レベル１更新のフラッディング、
およびノードの存在を効果的に通知することの３つの明
示的な手順によってこの自然学習を補う。近接局同期手
順は、ネットワークに接続しているノードのキャッシュ
を迅速に初期化するように設計されている。この手順
は、２つのノードが形式的に接続するときにも使用する
ことができる。これはスプリットを修復する簡単な方法
である。フラッディング手順は、キャッシュの最後のレ
ベルが一貫しているよう保証する。サーチが実際に完了
することを保証するためにこれは必須である。最後に、
ノードは、固有の識別子に非常に近いが等しくはない識
別子を探すことによってその存在を通知する。この要求
は、既存の近接局に転送される。これを実行することに
よって、ホストがいくつかの関係サイトによって認識さ
れることが保証される。これによって、フラッディング
手順がトリガされることも保証される。
は任意のサイズのネットワークを取り扱うことができ
る。しかし、各ノードは正確に初期化されたキャッシュ
を有する必要がある。Ｆｒｅｅｎｅｔのように、ノード
は、要求の規則的な処理の副次的な作用として他のノー
ドに関して学習する。残念ながら、信頼できる性能を達
成するには自然な学習プロセスに単純に依存するだけで
は十分でない。したがって、本発明のシステムは、送信
する近接局との同期、レベル１更新のフラッディング、
およびノードの存在を効果的に通知することの３つの明
示的な手順によってこの自然学習を補う。近接局同期手
順は、ネットワークに接続しているノードのキャッシュ
を迅速に初期化するように設計されている。この手順
は、２つのノードが形式的に接続するときにも使用する
ことができる。これはスプリットを修復する簡単な方法
である。フラッディング手順は、キャッシュの最後のレ
ベルが一貫しているよう保証する。サーチが実際に完了
することを保証するためにこれは必須である。最後に、
ノードは、固有の識別子に非常に近いが等しくはない識
別子を探すことによってその存在を通知する。この要求
は、既存の近接局に転送される。これを実行することに
よって、ホストがいくつかの関係サイトによって認識さ
れることが保証される。これによって、フラッディング
手順がトリガされることも保証される。
【００５３】本発明のこれらのプロトコルの実際の処理
に関して議論する前に、本発明のプロトコルにおける例
示的な適切なメッセージとデータ形式を議論することが
有益である。例えば、ネットワーク内の各ノードは、ノ
ード識別子、ノードアドレス、証明が有効とされる期
日、キーおよび署名情報を含んでいるアドレス証明によ
って記述される。キーおよび署名情報の形式は、特定の
実施態様によって変化する。重要な点は、この情報は、
そのノードがピアーツーピアネットワークのメンバーで
あること、およびそのノードと識別子との間の関係が本
物であることを証明するのに十分であるということであ
る。上記のように、キャッシュ項目の古さに関して、こ
の情報が最新のものであることを確認するために日付フ
ィールドが使用される。
に関して議論する前に、本発明のプロトコルにおける例
示的な適切なメッセージとデータ形式を議論することが
有益である。例えば、ネットワーク内の各ノードは、ノ
ード識別子、ノードアドレス、証明が有効とされる期
日、キーおよび署名情報を含んでいるアドレス証明によ
って記述される。キーおよび署名情報の形式は、特定の
実施態様によって変化する。重要な点は、この情報は、
そのノードがピアーツーピアネットワークのメンバーで
あること、およびそのノードと識別子との間の関係が本
物であることを証明するのに十分であるということであ
る。上記のように、キャッシュ項目の古さに関して、こ
の情報が最新のものであることを確認するために日付フ
ィールドが使用される。
【００５４】要求メッセージは、メッセージコード、Ｒ
ＥＱＵＳＥＳＴ、要求のターゲット、要求の起点のアド
レス証明、このメッセージに許可される最大中継数、お
よび要求を処理した各ノードに関してそのノードのアド
レスと、ノードが要求を受理したか拒否したかの指示と
を含む経過リストを含んでいる。要求を発信する際、要
求しているノードはメッセージコード、ターゲット値、
起点のアドレス証明を設定する。ノード数は１に設定さ
れており、経過リストは、起点のアドレスと要求が受理
されたという指示と共に項目を１つだけ含むように初期
化されている。ＲＥＱＵＥＳＴは、完全一致が発見され
ていない場合、最も近い一致が戻されることを保証する
ように「最適マッチ」証明を含むこともできる。
ＥＱＵＳＥＳＴ、要求のターゲット、要求の起点のアド
レス証明、このメッセージに許可される最大中継数、お
よび要求を処理した各ノードに関してそのノードのアド
レスと、ノードが要求を受理したか拒否したかの指示と
を含む経過リストを含んでいる。要求を発信する際、要
求しているノードはメッセージコード、ターゲット値、
起点のアドレス証明を設定する。ノード数は１に設定さ
れており、経過リストは、起点のアドレスと要求が受理
されたという指示と共に項目を１つだけ含むように初期
化されている。ＲＥＱＵＥＳＴは、完全一致が発見され
ていない場合、最も近い一致が戻されることを保証する
ように「最適マッチ」証明を含むこともできる。
【００５５】応答メッセージは、メッセージコード、Ｒ
ＥＳＰＯＮＳＥ、要求のターゲット、要求に最もよく一
致するノードのアドレス証明、要求を受理したが応答を
まだ処理していない各ノードに対してノードのアドレス
を含んでいる経過リストを含んでいる。メッセージが最
初の要求元に向かう過程でノードは応答リストから除外
される。フラッディングメッセージは、メッセージコー
ド、ＦＬＯＯＤＩＮＧ、フラッド中のアドレス証明、そ
の証明のコピーを受信済みの、各ノードに関するノード
のアドレスを含むすべてのノードのリストを含んでい
る。フラッディングが進行するに従いノードがそのリス
トに追加される。近接局同期要求は、メッセージコー
ド、ＳＹＮＣＨＲＯＮＩＺＥ、ノード識別子として表わ
される要求のターゲット、近接局を求めるノードのアド
レス証明を含んでいる。近接局公示メッセージは、メッ
セージコード、ＡＤＶＥＲＴＩＳＥ、ノード識別子とし
て表わされる公示の上限、公示を送信するノードのアド
レス証明、および、項目ごとにその項目の識別子を含ん
でいる証明が入手可能な項目リストを含んでいる。最後
に、近接局同期要求は、メッセージコード、ＳＯＬＩＣ
ＩＴ、請求（ｓｏｌｉｃｉｔａｔｉｏｎ）のターゲッ
ト、および近接局を求めているノードのアドレス証明を
含んでいる。
ＥＳＰＯＮＳＥ、要求のターゲット、要求に最もよく一
致するノードのアドレス証明、要求を受理したが応答を
まだ処理していない各ノードに対してノードのアドレス
を含んでいる経過リストを含んでいる。メッセージが最
初の要求元に向かう過程でノードは応答リストから除外
される。フラッディングメッセージは、メッセージコー
ド、ＦＬＯＯＤＩＮＧ、フラッド中のアドレス証明、そ
の証明のコピーを受信済みの、各ノードに関するノード
のアドレスを含むすべてのノードのリストを含んでい
る。フラッディングが進行するに従いノードがそのリス
トに追加される。近接局同期要求は、メッセージコー
ド、ＳＹＮＣＨＲＯＮＩＺＥ、ノード識別子として表わ
される要求のターゲット、近接局を求めるノードのアド
レス証明を含んでいる。近接局公示メッセージは、メッ
セージコード、ＡＤＶＥＲＴＩＳＥ、ノード識別子とし
て表わされる公示の上限、公示を送信するノードのアド
レス証明、および、項目ごとにその項目の識別子を含ん
でいる証明が入手可能な項目リストを含んでいる。最後
に、近接局同期要求は、メッセージコード、ＳＯＬＩＣ
ＩＴ、請求（ｓｏｌｉｃｉｔａｔｉｏｎ）のターゲッ
ト、および近接局を求めているノードのアドレス証明を
含んでいる。
【００５６】本発明のプロトコルに適用可能な一組のメ
ッセージを説明したが、次に、上記で説明した解決手順
に関心を戻す。具体的には、照会解決手順は、アドレス
指定するために一意の番号が解決されるプロセスであ
る。解決を要求するノードは、上記で説明した指定に従
って要求メッセージをフォーマットし、そのメッセージ
を最適な近接局に転送する。要求を受信したノードはそ
れを処理し、応答を返送することも、別のノードに要求
を転送ことも、あるいはその要求を処理できない場合は
拒絶を返送することもできる。
ッセージを説明したが、次に、上記で説明した解決手順
に関心を戻す。具体的には、照会解決手順は、アドレス
指定するために一意の番号が解決されるプロセスであ
る。解決を要求するノードは、上記で説明した指定に従
って要求メッセージをフォーマットし、そのメッセージ
を最適な近接局に転送する。要求を受信したノードはそ
れを処理し、応答を返送することも、別のノードに要求
を転送ことも、あるいはその要求を処理できない場合は
拒絶を返送することもできる。
【００５７】ノードは、要求メッセージを受信すると、
まず起点の証明が有効であることを検査する。その証明
が無効である場合、要求は拒絶される。証明が有効であ
る場合、ノードは上記で指定した規則に従って起点のア
ドレス証明でそのキャッシュ情報を更新する。次いで、
以下のステップに従ってメッセージを続行する。第１
に、要求のターゲットがローカル識別子と比較される。
２つの値が同一である場合、最後の値は既に発見済みで
ある。次いで手順はステップ４に進むか、あるいは第２
のステップに進む。第２に、中継リストが既にホストに
関する項目を含んでいるか否かが検査される。含んでい
る場合、プロセスはステップ４に進む。第３に、中継リ
スト中のノード数が許可されている中継数よりも少ない
か否かが検査される。多い場合、プロセスはステップ４
に進む。しかし少ない場合は、ノードのアドレスと、そ
のノードが照会を受け付けたという指示を含むリストに
項目が１つ追加される。一旦これが完了すると、次いで
プロセスはステップ４に進む。
まず起点の証明が有効であることを検査する。その証明
が無効である場合、要求は拒絶される。証明が有効であ
る場合、ノードは上記で指定した規則に従って起点のア
ドレス証明でそのキャッシュ情報を更新する。次いで、
以下のステップに従ってメッセージを続行する。第１
に、要求のターゲットがローカル識別子と比較される。
２つの値が同一である場合、最後の値は既に発見済みで
ある。次いで手順はステップ４に進むか、あるいは第２
のステップに進む。第２に、中継リストが既にホストに
関する項目を含んでいるか否かが検査される。含んでい
る場合、プロセスはステップ４に進む。第３に、中継リ
スト中のノード数が許可されている中継数よりも少ない
か否かが検査される。多い場合、プロセスはステップ４
に進む。しかし少ない場合は、ノードのアドレスと、そ
のノードが照会を受け付けたという指示を含むリストに
項目が１つ追加される。一旦これが完了すると、次いで
プロセスはステップ４に進む。
【００５８】ステップ４では、識別子がターゲットと一
致した場合、または中継しているノード数が既に許可さ
れた数に達している場合、ノードはメッセージコードを
ＲＥＳＰＯＮＳＥに更新し、その固有のアドレス証明を
最適一致ノードとして認識する。中継リストがホストに
対する項目を既に含んでいる場合、メッセージコードも
応答に変更されるが、ホストは最適一致ノードの証明を
更新しない。応答の中継リストは、要求を受け付けた中
継ノードだけを含む。ローカルノードが要求の起点であ
る場合、処理は完了しているが、そうでない場合、メッ
セージは中継リスト中でそのローカルノードの前にあ
り、それが要求を受け付けたことを示すコードを有する
第１の項目に中継される。
致した場合、または中継しているノード数が既に許可さ
れた数に達している場合、ノードはメッセージコードを
ＲＥＳＰＯＮＳＥに更新し、その固有のアドレス証明を
最適一致ノードとして認識する。中継リストがホストに
対する項目を既に含んでいる場合、メッセージコードも
応答に変更されるが、ホストは最適一致ノードの証明を
更新しない。応答の中継リストは、要求を受け付けた中
継ノードだけを含む。ローカルノードが要求の起点であ
る場合、処理は完了しているが、そうでない場合、メッ
セージは中継リスト中でそのローカルノードの前にあ
り、それが要求を受け付けたことを示すコードを有する
第１の項目に中継される。
【００５９】ノードは、中継リストにそのアドレスがま
だ列挙されていない、適切な次のホップを発見するため
にそのキャッシュ情報を使用する。適切な次のホップが
ある場合、メッセージはそのホストに中継される。しか
し適切な次のホップがない場合、中継ノードに対応する
項目は要求が受け付けられなかったことを示すように変
更される。そのノードが要求の起点である場合、その要
求は失敗している。そうでない場合、そのメッセージは
中継リスト中でそのローカルノードの前にあり、それが
要求を受け付けたことを示すコードを有する第１の項目
に中継される。この手順は、メッセージ中のすべてのト
ランザクション状態を認識するように設計されている。
したがって、中間ノードが進行中のトランザクションリ
ストを保存する必要はない。
だ列挙されていない、適切な次のホップを発見するため
にそのキャッシュ情報を使用する。適切な次のホップが
ある場合、メッセージはそのホストに中継される。しか
し適切な次のホップがない場合、中継ノードに対応する
項目は要求が受け付けられなかったことを示すように変
更される。そのノードが要求の起点である場合、その要
求は失敗している。そうでない場合、そのメッセージは
中継リスト中でそのローカルノードの前にあり、それが
要求を受け付けたことを示すコードを有する第１の項目
に中継される。この手順は、メッセージ中のすべてのト
ランザクション状態を認識するように設計されている。
したがって、中間ノードが進行中のトランザクションリ
ストを保存する必要はない。
【００６０】ノードは、要求メッセージを受信すると、
まず最適マッチの証明が有効であることを検査する。証
明が無効である場合、要求は拒絶される。証明が有効で
ある場合、ノードは、上記で説明した手順に従ってその
キャッシュ情報を最適マッチのアドレス証明で更新す
る。次いでノードは、以下のステップに従ってメッセー
ジを進める。第１に、最適マッチ識別子が要求のターゲ
ットと同じでない場合、および、そのローカル識別子が
最適マッチ識別子よりもターゲットにより近い場合、ノ
ードは最適マッチ証明をローカル証明で置き換える。第
２に、そのノードの項目が中継リストから除去される。
そのローカルノードが中継リスト中の第１の項目である
場合、要求は完了する。そうでない場合、リスト中の残
りのノードの最後のノードに応答が中継される。このプ
ロトコルを正確に実行するために、中間中継は状態を維
持する必要はない。
まず最適マッチの証明が有効であることを検査する。証
明が無効である場合、要求は拒絶される。証明が有効で
ある場合、ノードは、上記で説明した手順に従ってその
キャッシュ情報を最適マッチのアドレス証明で更新す
る。次いでノードは、以下のステップに従ってメッセー
ジを進める。第１に、最適マッチ識別子が要求のターゲ
ットと同じでない場合、および、そのローカル識別子が
最適マッチ識別子よりもターゲットにより近い場合、ノ
ードは最適マッチ証明をローカル証明で置き換える。第
２に、そのノードの項目が中継リストから除去される。
そのローカルノードが中継リスト中の第１の項目である
場合、要求は完了する。そうでない場合、リスト中の残
りのノードの最後のノードに応答が中継される。このプ
ロトコルを正確に実行するために、中間中継は状態を維
持する必要はない。
【００６１】以上、本発明の中核的なピアーツーピア名
前解決プロトコル（ＰＮＲＰ）を説明したが、次にＰＮ
ＲＰによって名前の解決を許可するメカニズムについて
議論する。要約すれば、上記でハッシュ関数、例えばＭ
Ｄ５、によって説明した円形番号空間上にそれらの名前
がマッピングされる。しかし１つのハッシュ値に対して
複数の項目がある場合がある（例えば、１０，０００メ
ンバーを有する大規模なグループ）。したがって、この
グループは図６に示すように、円形番号空間１８２上
に、それに関連付けられた大規模なグループ１８８を有
する単一項目１８６として位置付けられる。これが名前
−番号解決の唯一のメカニズムである場合、そのハッシ
ュに対応する各ノードは、そのサーチを十分に解決する
ために、グループ内のすべてのメンバーの膨大なキャッ
シュを有する必要がある。この制約を克服するために
は、＜ハッシュ＞．＜一意の番号＞（＜Ｍ＞．＜Ｎ＞）
として名前のハッシュに一意の番号が関連付けられる。
この追加の実際的な結果は、各グループのメンバーのマ
ッピングを含めるために円形番号空間１９０を拡張する
ことである。この拡張子によって、名前ならびに番号の
ために前述の中核プロトコルを使用することができ、大
規模なグループにスケールすることができる。
前解決プロトコル（ＰＮＲＰ）を説明したが、次にＰＮ
ＲＰによって名前の解決を許可するメカニズムについて
議論する。要約すれば、上記でハッシュ関数、例えばＭ
Ｄ５、によって説明した円形番号空間上にそれらの名前
がマッピングされる。しかし１つのハッシュ値に対して
複数の項目がある場合がある（例えば、１０，０００メ
ンバーを有する大規模なグループ）。したがって、この
グループは図６に示すように、円形番号空間１８２上
に、それに関連付けられた大規模なグループ１８８を有
する単一項目１８６として位置付けられる。これが名前
−番号解決の唯一のメカニズムである場合、そのハッシ
ュに対応する各ノードは、そのサーチを十分に解決する
ために、グループ内のすべてのメンバーの膨大なキャッ
シュを有する必要がある。この制約を克服するために
は、＜ハッシュ＞．＜一意の番号＞（＜Ｍ＞．＜Ｎ＞）
として名前のハッシュに一意の番号が関連付けられる。
この追加の実際的な結果は、各グループのメンバーのマ
ッピングを含めるために円形番号空間１９０を拡張する
ことである。この拡張子によって、名前ならびに番号の
ために前述の中核プロトコルを使用することができ、大
規模なグループにスケールすることができる。
【００６２】このピアーツーピア名前解決プロトコル
（ＰＮＲＰ）によって、ピアは大域的に一意のＩＤをピ
アアドレス証明に変換することができる。大域的に一意
のピアＩＤは、１２８ビットのＩＤであることが好まし
い。ピアＩＤは、ピアＩＤ番号空間中にランダムに分散
されることが理想的である。ピアアドレス証明（ＰＡ
Ｃ）は、ピアＩＤに関連付けられているデータの集合で
あり、公開鍵および公開鍵の派生物を除いて、ピアＩ
Ｄ、ピアインスタンスアドレス、ピアフレンドリーな名
前、完全な公開鍵、および証明全体の保全性を証明する
署名を含んでいる。必要に応じてＰＡＣには他のデータ
を含めることもできる。下記で説明するように、本発明
のシステムは、ピアＩＤと、ピア資源のクラスの任意の
インスタンスを捜し出すために有用な範疇ピアＩＤ接頭
部（ｃａｔｅｇｏｒｙ ｐｅｅｒ ＩＤｐｒｅｆｉｘ）
とを使用する。
（ＰＮＲＰ）によって、ピアは大域的に一意のＩＤをピ
アアドレス証明に変換することができる。大域的に一意
のピアＩＤは、１２８ビットのＩＤであることが好まし
い。ピアＩＤは、ピアＩＤ番号空間中にランダムに分散
されることが理想的である。ピアアドレス証明（ＰＡ
Ｃ）は、ピアＩＤに関連付けられているデータの集合で
あり、公開鍵および公開鍵の派生物を除いて、ピアＩ
Ｄ、ピアインスタンスアドレス、ピアフレンドリーな名
前、完全な公開鍵、および証明全体の保全性を証明する
署名を含んでいる。必要に応じてＰＡＣには他のデータ
を含めることもできる。下記で説明するように、本発明
のシステムは、ピアＩＤと、ピア資源のクラスの任意の
インスタンスを捜し出すために有用な範疇ピアＩＤ接頭
部（ｃａｔｅｇｏｒｙ ｐｅｅｒ ＩＤｐｒｅｆｉｘ）
とを使用する。
【００６３】ピアＩＤ方式のための理想的な特性には、
ランダム分散、導出可能性（Ｄｅｒｉｖａｂｉｌｉｔ
ｙ）、セキュリティイネーブラ、インスタス生成可能性
（ｉｎｓｔａｎｔｉａｂｉｌｉｔｙ）が含まれる。ラン
ダム分散によって、インスタンス化されたピアＩＤが上
記で説明したピアＩＤ空間中にランダム分散を有するこ
とが好ましい。ＩＤのクラスタ化が進んでいないほど、
ＰＮＲＰ解決はよりよく機能する。導出可能性によっ
て、共通の一意のフレンドリーな名前からピアＩＤを生
成する機能が意味される。導出可能性は、事前に認識せ
ずにピアＩＤを獲得することを可能にする。番号による
ピアＩＤよりも、電子メールアドレスなどのより直感的
な名前の方が覚えやすいのでこれは有利である。セキュ
リティイネーブラとは、個人情報窃盗を諦めさせるよう
なピアＩＤ構成のことである。すなわち、好ましい実施
形態では、本発明のシステムの個人情報の所有権は証明
可能である。最後に、本発明のＰＮＲＰには、ピアＩＤ
の活動状態にある複数のインスタンス、例えば２つのマ
シン上で同時に活動状態にあるユーザのピアＩＤを許可
するための明確なメカニズムが含まれる。
ランダム分散、導出可能性（Ｄｅｒｉｖａｂｉｌｉｔ
ｙ）、セキュリティイネーブラ、インスタス生成可能性
（ｉｎｓｔａｎｔｉａｂｉｌｉｔｙ）が含まれる。ラン
ダム分散によって、インスタンス化されたピアＩＤが上
記で説明したピアＩＤ空間中にランダム分散を有するこ
とが好ましい。ＩＤのクラスタ化が進んでいないほど、
ＰＮＲＰ解決はよりよく機能する。導出可能性によっ
て、共通の一意のフレンドリーな名前からピアＩＤを生
成する機能が意味される。導出可能性は、事前に認識せ
ずにピアＩＤを獲得することを可能にする。番号による
ピアＩＤよりも、電子メールアドレスなどのより直感的
な名前の方が覚えやすいのでこれは有利である。セキュ
リティイネーブラとは、個人情報窃盗を諦めさせるよう
なピアＩＤ構成のことである。すなわち、好ましい実施
形態では、本発明のシステムの個人情報の所有権は証明
可能である。最後に、本発明のＰＮＲＰには、ピアＩＤ
の活動状態にある複数のインスタンス、例えば２つのマ
シン上で同時に活動状態にあるユーザのピアＩＤを許可
するための明確なメカニズムが含まれる。
【００６４】ＰＮＲＰキーは、本発明の実施形態では１
２８ビット数のオブジェクトの識別子と、通常はその項
目が入手可能なＩＰｖ６アドレスである、本発明の実施
形態では別の１２８ビット数であるインスタンスの識別
子との２つの構成部分を有する。各ＰＮＲＰ項目は、こ
のキーの他にその項目の発行者がＩＤを発行する資格を
有しているか否かを検査し、かつ、その項目に関する情
報がその発行者の意思に反して発行されることができな
いようにするために使用することができる「プルーフ」
を含む。
２８ビット数のオブジェクトの識別子と、通常はその項
目が入手可能なＩＰｖ６アドレスである、本発明の実施
形態では別の１２８ビット数であるインスタンスの識別
子との２つの構成部分を有する。各ＰＮＲＰ項目は、こ
のキーの他にその項目の発行者がＩＤを発行する資格を
有しているか否かを検査し、かつ、その項目に関する情
報がその発行者の意思に反して発行されることができな
いようにするために使用することができる「プルーフ」
を含む。
【００６５】項目の最も単純な形式では、オブジェクト
識別子は項目に関連付けられた公開鍵のセキュアハッシ
ュであり、インスタンス識別子はオブジェクトがそこで
入手可能なＩＰｖ６である。識別子およびインスタンス
と、この公開鍵に関連付けられている秘密鍵との組合せ
を示すことによってプルーフが得られる。
識別子は項目に関連付けられた公開鍵のセキュアハッシ
ュであり、インスタンス識別子はオブジェクトがそこで
入手可能なＩＰｖ６である。識別子およびインスタンス
と、この公開鍵に関連付けられている秘密鍵との組合せ
を示すことによってプルーフが得られる。
【００６６】グループベースの識別子は、そのグループ
に関連付けられている公開鍵のセキュアハッシュであ
り、インスタンス識別子はグループメンバーが存在する
ＩＰｖ６アドレスである。識別子およびインスタンス
と、グループメンバーの公開鍵との組合せを示し、次い
で、グループに対するグループメンバーの公開鍵のリン
クを評価するグループの公開鍵で署名した証明を開示す
ることによってプルーフが得られる。
に関連付けられている公開鍵のセキュアハッシュであ
り、インスタンス識別子はグループメンバーが存在する
ＩＰｖ６アドレスである。識別子およびインスタンス
と、グループメンバーの公開鍵との組合せを示し、次い
で、グループに対するグループメンバーの公開鍵のリン
クを評価するグループの公開鍵で署名した証明を開示す
ることによってプルーフが得られる。
【００６７】ユーザベースの識別子は、命名機関のセキ
ュアキーを有する、電子メールアドレスで表される、請
求されたユーザの識別のセキュアハッシュである。識別
子およびインスタンスと、ユーザの秘密鍵との組合せを
示し、次いでユーザ名を対応する公開鍵にリンクしてい
る命名機関によって署名された証明を開示することによ
ってプルーフが得られる。電子メールアドレスは大域的
に一意のアドレスであるはずなので、このハッシュ手順
は、抽出したもの同士が衝突する確率が５０％になる前
に、２６４の一意のピアを考慮に入れている。
ュアキーを有する、電子メールアドレスで表される、請
求されたユーザの識別のセキュアハッシュである。識別
子およびインスタンスと、ユーザの秘密鍵との組合せを
示し、次いでユーザ名を対応する公開鍵にリンクしてい
る命名機関によって署名された証明を開示することによ
ってプルーフが得られる。電子メールアドレスは大域的
に一意のアドレスであるはずなので、このハッシュ手順
は、抽出したもの同士が衝突する確率が５０％になる前
に、２６４の一意のピアを考慮に入れている。
【００６８】本発明の中核ＰＮＲＰに対するこのような
拡張によって、個々のホストのキャッシュ管理はより複
雑化する。すなわち、所与のホスト上に１つ以上のＩＤ
が格納されている場合、キャッシュ管理は、各表記され
たＩＤに対して適切な近接局が維持されることを保証す
る必要がある。理想的な場合は（メモリおよび処理は関
係なく）、このキャッシュは２つのＩＤが同じキャッシ
ュレベルで重複し、次いで上位レベルのキャッシュを共
有した時点まで各ＩＤごとに一意のレベルを含んでい
る。キャッシュされたＰＡＣは、様々な表記されたＩＤ
間に１つ以上のキャッシュレベル内の論理メンバーシッ
プを有することができる。
拡張によって、個々のホストのキャッシュ管理はより複
雑化する。すなわち、所与のホスト上に１つ以上のＩＤ
が格納されている場合、キャッシュ管理は、各表記され
たＩＤに対して適切な近接局が維持されることを保証す
る必要がある。理想的な場合は（メモリおよび処理は関
係なく）、このキャッシュは２つのＩＤが同じキャッシ
ュレベルで重複し、次いで上位レベルのキャッシュを共
有した時点まで各ＩＤごとに一意のレベルを含んでい
る。キャッシュされたＰＡＣは、様々な表記されたＩＤ
間に１つ以上のキャッシュレベル内の論理メンバーシッ
プを有することができる。
【００６９】本発明の基本プロトコルに対する第２の拡
張は、ピアーツーピア解決プロトコルとドメインネーム
システム（ＤＮＳ）との事実上の統合を実現する。各ノ
ードに、ＤＮＳ構成部分と一意の番号とからなるＩＤを
提供することによって、ＤＮＳ構成要素のために集中型
サーバを配置するようにＤＮＳメカニズムを使用するこ
とができる。次いで集中型サーバは、特定のノードを発
見するために一意の番号の部分と共に本発明のプロトコ
ルを使用して、ピアーツーピア名前解決プロトコル（Ｐ
ＮＲＰ）空間に移動し、その情報を要求側に戻すことが
できる。個々のノードは、集中型サーバに乱数と共に要
求を送信することによって、そのキャッシュをシードす
るために役立つ近接局を発見することができる。
張は、ピアーツーピア解決プロトコルとドメインネーム
システム（ＤＮＳ）との事実上の統合を実現する。各ノ
ードに、ＤＮＳ構成部分と一意の番号とからなるＩＤを
提供することによって、ＤＮＳ構成要素のために集中型
サーバを配置するようにＤＮＳメカニズムを使用するこ
とができる。次いで集中型サーバは、特定のノードを発
見するために一意の番号の部分と共に本発明のプロトコ
ルを使用して、ピアーツーピア名前解決プロトコル（Ｐ
ＮＲＰ）空間に移動し、その情報を要求側に戻すことが
できる。個々のノードは、集中型サーバに乱数と共に要
求を送信することによって、そのキャッシュをシードす
るために役立つ近接局を発見することができる。
【００７０】具体的には、ＰＮＲＰ ＤＮＳ結合（ｌｉ
ｎｋａｇｅ）によって、ピア識別子（ＰｒＩＤ）を正式
なアドレス証明に変換することができる。このサービス
によって、加入者は接続したピアの正確なアドレスを獲
得することができる。インターネットはアドレス解決の
ためにＤＮＳを使用する。名前解決のためにＤＮＳとＰ
ＮＲＰを結合することは有利である。このような結合
は、そのクライアントのフレンドリーな名前または符号
化されたＰｒＩＤを使用して、ＤＮＳクライアントがＰ
ＮＲＰクライアントのＩＰアドレスを獲得できるように
するべきである。これは、ＤＮＳリゾルバーが期限切れ
のアドレスをキャッシュする危険性も最小限に抑える。
さらに、いかなるＰＮＲＰ加入者上で実行するにも十分
に軽い。
ｎｋａｇｅ）によって、ピア識別子（ＰｒＩＤ）を正式
なアドレス証明に変換することができる。このサービス
によって、加入者は接続したピアの正確なアドレスを獲
得することができる。インターネットはアドレス解決の
ためにＤＮＳを使用する。名前解決のためにＤＮＳとＰ
ＮＲＰを結合することは有利である。このような結合
は、そのクライアントのフレンドリーな名前または符号
化されたＰｒＩＤを使用して、ＤＮＳクライアントがＰ
ＮＲＰクライアントのＩＰアドレスを獲得できるように
するべきである。これは、ＤＮＳリゾルバーが期限切れ
のアドレスをキャッシュする危険性も最小限に抑える。
さらに、いかなるＰＮＲＰ加入者上で実行するにも十分
に軽い。
【００７１】ＰＮＲＰ ＤＮＳゲートウェイは、ポート
５３上のＴＣＰおよびＵＤＰ接続をリッスンする。これ
は、ＱＣＬＡＳＳ＝ＩＮおよびＱＴＹＰＥ＝ＡＡＡＡま
たはＡ６（ＩＰｖ６アドレス）または＊を有する照会だ
けを受理する。このゲートウェイは、ＱＮＡＭＥをホス
ト名とドメイン接尾部（ｄｏｍａｉｎ ｐｒｅｆｉｘ）
に分割する。ドメイン接頭部は、存在しないか、または
左端の構成部分として「Ｐ２Ｐ」を有する必要がある。
この他のドメイン接尾部では０回答になる。この接尾部
は、一部をパラメータ化可能とし、命名クラウドの定義
とすることが好ましい。
５３上のＴＣＰおよびＵＤＰ接続をリッスンする。これ
は、ＱＣＬＡＳＳ＝ＩＮおよびＱＴＹＰＥ＝ＡＡＡＡま
たはＡ６（ＩＰｖ６アドレス）または＊を有する照会だ
けを受理する。このゲートウェイは、ＱＮＡＭＥをホス
ト名とドメイン接尾部（ｄｏｍａｉｎ ｐｒｅｆｉｘ）
に分割する。ドメイン接頭部は、存在しないか、または
左端の構成部分として「Ｐ２Ｐ」を有する必要がある。
この他のドメイン接尾部では０回答になる。この接尾部
は、一部をパラメータ化可能とし、命名クラウドの定義
とすることが好ましい。
【００７２】ゲートウェイは、有効な照会を受信する
と、ホスト名上で２つのＰＮＲＰサーチを実施する。第
１に、サーチは常に、ディフォルトフレンドリーな名前
−ＰｒＩＤ変換の結果上で実施される。この変換は、フ
レンドリーな名前の１２８ビットのセキュアハッシュで
あることが好ましい。第２に、ホスト名が１６進数のＰ
ｒＩＤの有効なＡＳＣＩＩ表記に対応する場合、そのホ
スト名は、２進法のＰｒＩＤに変換され、そのＰｒＩＤ
のサーチが開始される。より強力な機密保護の必要性を
認識すると、強力なハッシュと秘密の組合せを使用する
ことができる。どのサーチも照会と完全に一致するアド
レス証明を戻す場合、その一致に対してＤＮＳ Ａ記録
が構築される。Ａ記録ＴＴＬは１０分またはそのアドレ
ス証明のＴＴＬの短い方に設定される。応答は、正式の
ものとしてマーク付けされている。
と、ホスト名上で２つのＰＮＲＰサーチを実施する。第
１に、サーチは常に、ディフォルトフレンドリーな名前
−ＰｒＩＤ変換の結果上で実施される。この変換は、フ
レンドリーな名前の１２８ビットのセキュアハッシュで
あることが好ましい。第２に、ホスト名が１６進数のＰ
ｒＩＤの有効なＡＳＣＩＩ表記に対応する場合、そのホ
スト名は、２進法のＰｒＩＤに変換され、そのＰｒＩＤ
のサーチが開始される。より強力な機密保護の必要性を
認識すると、強力なハッシュと秘密の組合せを使用する
ことができる。どのサーチも照会と完全に一致するアド
レス証明を戻す場合、その一致に対してＤＮＳ Ａ記録
が構築される。Ａ記録ＴＴＬは１０分またはそのアドレ
ス証明のＴＴＬの短い方に設定される。応答は、正式の
ものとしてマーク付けされている。
【００７３】ＤＮＳサーバは、次の２つの方法のうちの
一方によってＰＮＲＰ ＤＮＳゲートウェイにリンクす
ることができる。第１に、ＤＮＳサーバの正式ゾーンの
子である新しいゾーンを作成することができる。例え
ば、ＮＴＤＥＶ．ＭＩＣＲＯＳＯＦＴ．ＣＯＭ．の正式
なネームサーバは、ローカルＰＮＲＰ ＤＮＳゲートウ
ェイを指す１つまたは複数のＮＳ記録を有するＰ２Ｐ．
ＮＴＤＥＶ．ＭＩＣＲＯＳＯＦＴ．ＣＯＭ．というゾー
ンを有することができる。第２に、＜Ｐ２Ｐ＞を任意の
値とした場合、例えば「ｐｎｒｐ．ｎｅｔ」または「ｐ
２ｐ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ」のように新しいゾ
ーン＜Ｐ２Ｐ＞を作成することができる。このようなゾ
ーンが、最も近いＰＮＲＰ ＤＮＳゲートウェイを指し
て各ドメインに存在する場合、ピアは、＜ＰｒＩＤ＞．
Ｐ２Ｐを解決することによって、そのローカルＰＮＲＰ
アクセスポイントを発見するためにＤＮＳを使用するこ
とができる。各ＤＮＳサーバは、ローカルＰ２Ｐネット
ワークに対してローカルアクセスおよびグローバルアク
セスの両方を可能にするために、両方のゾーンを定義し
ておくことが理想的である。
一方によってＰＮＲＰ ＤＮＳゲートウェイにリンクす
ることができる。第１に、ＤＮＳサーバの正式ゾーンの
子である新しいゾーンを作成することができる。例え
ば、ＮＴＤＥＶ．ＭＩＣＲＯＳＯＦＴ．ＣＯＭ．の正式
なネームサーバは、ローカルＰＮＲＰ ＤＮＳゲートウ
ェイを指す１つまたは複数のＮＳ記録を有するＰ２Ｐ．
ＮＴＤＥＶ．ＭＩＣＲＯＳＯＦＴ．ＣＯＭ．というゾー
ンを有することができる。第２に、＜Ｐ２Ｐ＞を任意の
値とした場合、例えば「ｐｎｒｐ．ｎｅｔ」または「ｐ
２ｐ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ」のように新しいゾ
ーン＜Ｐ２Ｐ＞を作成することができる。このようなゾ
ーンが、最も近いＰＮＲＰ ＤＮＳゲートウェイを指し
て各ドメインに存在する場合、ピアは、＜ＰｒＩＤ＞．
Ｐ２Ｐを解決することによって、そのローカルＰＮＲＰ
アクセスポイントを発見するためにＤＮＳを使用するこ
とができる。各ＤＮＳサーバは、ローカルＰ２Ｐネット
ワークに対してローカルアクセスおよびグローバルアク
セスの両方を可能にするために、両方のゾーンを定義し
ておくことが理想的である。
【００７４】ＤＮＳへの本発明のＰＮＲＰのこのような
拡張の一例を図７に示す。この図は、ＤＮＳ空間２００
とピアーツーピア空間２０２の２つの空間を示してい
る。これら２つの空間の間の結合は、ｐ２ｐ．ｍｉｃｏ
ｒｓｏｆｔ．ｃｏｍ．という例示的な名前を有するサー
バ２０４によって実現する。ピアーツーピア空間２０２
に存在するノード２０６は、１２３４５０ＡＦ３９．ｐ
ｔｐ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ．という例示的な名
前を有することができる。あるいは、一意の番号ＩＤ
は、中核プロトコルへの名前−番号拡張に関して上記で
説明したフレンドリーな名前で置き換えることができ
る。ＤＮＳ空間２００内のノード２０８がピアーツーピ
ア空間２０２内のノード２０６を発見しようとする場
合、ノード２０８はＤＮＳ照会を．ｃｏｍルートサーバ
２１０に送信し、そこからその照会は．ｍｉｃｒｏｓｏ
ｆｔサーバ２１２に渡され、そこからその照会は．ｐ２
ｐサーバ２０４に渡される。次いでこのサーバは、上記
で説明したようにピアーツーピア空間２０２内にあるタ
ーゲットノード２０６を発見するために、ノードｉｄと
本発明のプロトコルを使用する。ターゲットノード２０
６が発見されると、そのアドレスがＤＮＳ空間にある要
求ノード２０８に戻される。新しいノード２１４は、シ
ステムにプラグインしてそのキャッシュをシードするこ
とを希望する場合、ノード２１４は、＜乱数＞．ｐ２
ｐ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ．の形式でｉｄを有す
るノードに対して要求を送信するだけである。当然、他
の実施態様は、「ｐ２ｐ．ｍｉｃｒｏｓｏｆｔ．ｃｏ
ｍ．」の代わりに、例えば「ｐｎｒｐ．ｎｅｔ」などの
異なるドメイン名を使用することができることを当業者
なら理解するだろう。
拡張の一例を図７に示す。この図は、ＤＮＳ空間２００
とピアーツーピア空間２０２の２つの空間を示してい
る。これら２つの空間の間の結合は、ｐ２ｐ．ｍｉｃｏ
ｒｓｏｆｔ．ｃｏｍ．という例示的な名前を有するサー
バ２０４によって実現する。ピアーツーピア空間２０２
に存在するノード２０６は、１２３４５０ＡＦ３９．ｐ
ｔｐ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ．という例示的な名
前を有することができる。あるいは、一意の番号ＩＤ
は、中核プロトコルへの名前−番号拡張に関して上記で
説明したフレンドリーな名前で置き換えることができ
る。ＤＮＳ空間２００内のノード２０８がピアーツーピ
ア空間２０２内のノード２０６を発見しようとする場
合、ノード２０８はＤＮＳ照会を．ｃｏｍルートサーバ
２１０に送信し、そこからその照会は．ｍｉｃｒｏｓｏ
ｆｔサーバ２１２に渡され、そこからその照会は．ｐ２
ｐサーバ２０４に渡される。次いでこのサーバは、上記
で説明したようにピアーツーピア空間２０２内にあるタ
ーゲットノード２０６を発見するために、ノードｉｄと
本発明のプロトコルを使用する。ターゲットノード２０
６が発見されると、そのアドレスがＤＮＳ空間にある要
求ノード２０８に戻される。新しいノード２１４は、シ
ステムにプラグインしてそのキャッシュをシードするこ
とを希望する場合、ノード２１４は、＜乱数＞．ｐ２
ｐ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ．の形式でｉｄを有す
るノードに対して要求を送信するだけである。当然、他
の実施態様は、「ｐ２ｐ．ｍｉｃｒｏｓｏｆｔ．ｃｏ
ｍ．」の代わりに、例えば「ｐｎｒｐ．ｎｅｔ」などの
異なるドメイン名を使用することができることを当業者
なら理解するだろう。
【００７５】上記で説明した本発明の様々な実施形態
は、例示および説明の目的で提示したものである。これ
は本発明を、開示した実施形態だけを網羅したり、これ
らに限定することを意図したものではない。上記の教示
に鑑みて無数の修正形態または変形形態が可能である。
議論した実施形態は、本発明の原理の最良の例示を提供
するために選択され、説明されたものであり、その事実
上の適用例は、様々な実施形態の形式で、また、考慮さ
れる特定の用途に適した様々な修正形態で当業者が本発
明を使用することを可能にする。このようなすべての修
正形態および変形形態は、公平、合法的、公正に権利を
有する範囲に従って解釈されるとき、頭記の特許請求の
範囲によって規定される本発明の範囲内にあるものであ
る。
は、例示および説明の目的で提示したものである。これ
は本発明を、開示した実施形態だけを網羅したり、これ
らに限定することを意図したものではない。上記の教示
に鑑みて無数の修正形態または変形形態が可能である。
議論した実施形態は、本発明の原理の最良の例示を提供
するために選択され、説明されたものであり、その事実
上の適用例は、様々な実施形態の形式で、また、考慮さ
れる特定の用途に適した様々な修正形態で当業者が本発
明を使用することを可能にする。このようなすべての修
正形態および変形形態は、公平、合法的、公正に権利を
有する範囲に従って解釈されるとき、頭記の特許請求の
範囲によって規定される本発明の範囲内にあるものであ
る。
【００７６】
【発明の効果】以上説明したように、本発明によれば、
絶えず増加し続けるキャッシュを必要とせず、適切なポ
ップ数によって、ネットワークのサイズに関わらず収束
が保証される。
絶えず増加し続けるキャッシュを必要とせず、適切なポ
ップ数によって、ネットワークのサイズに関わらず収束
が保証される。
【図１】本発明が常駐する例示的コンピュータシステム
を全体的に示すブロック図である。
を全体的に示すブロック図である。
【図２】本発明の円形番号空間のグラフである。
【図３】本発明のシステムで収束に期待される平均ホッ
プ数を示すグラフである。
プ数を示すグラフである。
【図４】本発明のマルチレベルキャッシュを簡略化した
図である。
図である。
【図５】本発明のシステムで収束に達するための様々な
ネットワークサイズに対するホップ数対キャッシュ分割
サイズを示すグラフである。
ネットワークサイズに対するホップ数対キャッシュ分割
サイズを示すグラフである。
【図６】本発明による名前対番号マッピングを含めるよ
うに拡張された本発明の円形番号空間を示すグラフであ
る。
うに拡張された本発明の円形番号空間を示すグラフであ
る。
【図７】ドメインネームサービス（ＤＮＳ）とピアツー
ピア空間の２つの空間の間の本発明のシステムのクロス
オーバーアプリケーションを示す図である。
ピア空間の２つの空間の間の本発明のシステムのクロス
オーバーアプリケーションを示す図である。
【図８】ピアツーピア空間を示す図である。
１００ コンピューティングシステム環境 １１０ コンピュータ １２０ 処理ユニット １２１ システムバス １３０ システムメモリ １３１ 読み出し専用メモリ １３２ ランダムアクセスメモリ １３３ 基本入出力システム １３４ オペレーティングモジュール １３５ アプリケーションプログラム １３６ 他のプログラムモジュール １３７ プログラムデータ １４１ ハードディスクドライブ １４４ オペレーティングシステム １４５ アプリケーションプログラム １４６ 他のプログラムモジュール １４７ プログラムデータ １５１ 磁気ディスクドライブ １５２ 取り外し可能な不揮発性磁気ディスク １５５ 光ディスクドライブ １５６ 取り外し可能な不揮発性光ディスク １６０ ユーザ入力インターフェース １６１ ポインティングデバイス １６２ キーボード １７０ アダプタ １７１ ローカルエリアネットワーク（ＬＡＮ） １７２ モデム １７３ ワイドエリアネットワーク（ＷＡＮ） １８０ 遠隔コンピュータ １８１ 記憶装置 １８４ マルチレベルキャッシュ １８５ 遠隔アプリケーションプログラム １９０ ビデオインターフェース １９１ モニタ １９５ 出力周辺インターフェース １９６ プリンタ １９７ スピーカ
フロントページの続き (72)発明者 ジョン エル．ミラー アメリカ合衆国 98007 ワシントン州 ベルビュー 140 プレイス ノースイー スト 1306 Ｆターム(参考） 5K030 GA03 GA13 HA08 HB14 HD10 LA08 LB02 LB05 MD08
Claims (25)
- 【請求項１】 一意の番号がアドレスに変換されるサー
バレス名前解決プロトコルであって、 第１ノードで、一意の番号識別子を有する第２ノードの
アドレス解決を求める要求側ノードから、該要求側ノー
ドのアドレス情報を含む要求メッセージを受信するステ
ップと、 前記第１ノードのルーティングテーブルに前記要求側ノ
ードのアドレス情報を入れるステップと、 前記要求メッセージを分析するステップと、 ３つの条件のうちの１つが満たされたときに、前記第１
ノードのアドレス情報を前記要求メッセージに最も一致
するものと判定する前記要求側ノードへの応答メッセー
ジを生成するステップと、 ３つの条件のうちの１つも満たされないときに、前記要
求に対する適切な次のホップを決定するステップと、 前記要求メッセージを前記適切な次のホップに転送する
ステップとを備えることを特徴とするプロトコル。 - 【請求項２】 前記要求メッセージを分析するステップ
は、前記一意の番号識別子を前記第１ノードのアドレス
情報と比較するステップを備え、３つの条件のうちの１
つが満たされたときに前記第１ノードのアドレス情報を
前記要求メッセージに最も一致するものと判定する前記
要求側ノードへの応答メッセージを生成するステップ
は、前記一意の番号識別子が前記第１ノードのアドレス
情報と同一であるときに、前記第１ノードのアドレス情
報を前記要求メッセージに最も一致するものと判定する
前記要求側ノードへの応答メッセージを生成するステッ
プを備えることを特徴とする請求項１に記載のプロトコ
ル。 - 【請求項３】 前記要求メッセージは、最大ホップ数値
と前記要求メッセージを処理したノードのリストとを含
み、前記要求メッセージを分析するステップは、前記要
求メッセージを既に処理したノード数が前記最大ホップ
数を超えているか否かを判定するステップを備え、 ３つの条件のうちの１つが満たされたときに前記第１ノ
ードのアドレス情報を前記要求メッセージに最も一致す
るものと判定する前記要求側ノードへの応答メッセージ
を生成するステップは、前記要求メッセージを既に処理
したノード数が前記最大ホップ数を超えているときに、
前記第１ノードのアドレス情報を前記要求メッセージに
最も一致するものと判定する前記要求側ノードへの応答
メッセージを生成するステップを備えることを特徴とす
る請求項１に記載のプロトコル。 - 【請求項４】 前記要求メッセージは、該要求メッセー
ジを処理したノードのリストを含み、前記要求メッセー
ジを分析するステップは、前記第１ノードのアドレス情
報が、前記要求メッセージを処理したノードのリストに
入っているか否かを判定するステップを備え、３つの条
件のうちの１つが満たされたときに、前記第１ノードの
アドレス情報を前記要求メッセージに最も一致するもの
と判定する前記要求側ノードへの応答メッセージを生成
するステップは、前記第１ノードのアドレス情報がその
要求メッセージを既に処理したノードのリストに入って
いるときに、前記第１ノードのアドレス情報を前記要求
メッセージに最も一致するものと判定する前記要求側ノ
ードへの応答メッセージを生成するステップを備えるこ
とを特徴とする請求項１に記載のプロトコル。 - 【請求項５】 前記要求メッセージは起点の証明を含
み、前記起点の証明の有効性を判定するために前記起点
の証明を検査するステップと、前記起点の証明が無効な
場合は前記要求メッセージを拒絶するステップとをさら
に備えることを特徴とする請求項１に記載のプロトコ
ル。 - 【請求項６】 前記ルーティングテーブルに入れるステ
ップは、 前記要求側ノードのアドレス情報が前記ルーティングテ
ーブルに既に入っているか否かを判定するステップと、 前記要求側ノードのアドレス情報よりも新しいアドレス
情報が既に前記ルーティングテーブルに格納されている
場合、前記要求側ノードのアドレス情報をリフレッシュ
するステップと、 前記第１ノードと前記要求側ノードのアドレス情報との
間の距離を計算するステップと、 前記距離から、前記要求側ノードのアドレス情報を格納
させる選択されたレベルを判定するステップと、 前記選択されたレベルに前記アドレス情報を格納するス
テップとを備えることを特徴とする請求項１に記載のプ
ロトコル。 - 【請求項７】 前記選択されたレベルは、Ｋ個の項目を
その中に格納している最後のレベルであり、前記選択さ
れたレベルを判定するステップは、項目が置き換えられ
るべきか否かを判定するステップと、前記項目で前記要
求側ノードのアドレス情報を置き換えるステップとを備
えることを特徴とする請求項６に記載のプロトコル。 - 【請求項８】 前記選択されたレベルは最後のレベルで
あり、既にフラッドしたノードのリストを有する前記第
１ノードのアドレス情報を含むフラッディングメッセー
ジを作成するステップと、前記フラッディングメッセー
ジを前記要求側ノードに送信するステップとをさらに備
えることを特徴とする請求項６に記載のプロトコル。 - 【請求項９】 前記要求側ノードへの距離がＤＭＡＸ／
（Ｐ（Ｌ−１））よりも短い前記ルーティングテーブル
内のノードのリストを作成するステップであって、前記
新しい項目の追加がフラッディングメッセージの結果で
あるときに、前記リストから既にフラッドしているもの
としてマーク付けされているノードを除去するステップ
と、前記要求側ノードのアドレス情報を含んでいるフラ
ッディングメッセージを作成するステップであって、前
記フラッディングメッセージを前記リスト中のすべての
ノードに送信するステップとをさらに備えることを特徴
とする請求項８に記載のプロトコル。 - 【請求項１０】 前記選択されたレベルは、Ｋ個または
Ｋ＋１個以上の項目をそこに格納している最後のレベル
であり、前記選択されたレベルを判定するステップは、
新しいレベルを追加するステップと、前記最後のレベル
中の項目を、前記第１ノードのアドレス情報からの距離
に従って前記最後のレベルと前記新しいレベルとの間で
分割するステップとを備えることを特徴とする請求項６
に記載のプロトコル。 - 【請求項１１】 前記ルーティングテーブル内のアドレ
ス情報に関する有効日付を検査するステップと、前記有
効日付が過ぎたアドレス情報を除去するステップとを備
えることを特徴とする請求項１に記載のプロトコル。 - 【請求項１２】 前記要求に適した次のホップを判定す
るステップは、前記要求メッセージにそのアドレスがま
だ列挙されていないルーティングテーブル項目のサブセ
ットを探すステップと、前記サブセットが空のときには
失敗の指示を戻すステップと、特定項目が前記サブセッ
ト内の唯一の項目であるときは前記特定項目を戻すステ
ップとを備えることを特徴とする請求項１に記載のプロ
トコル。 - 【請求項１３】 前記第２ノードに最も近い識別子を有
する２つの項目を探すステップであって、前記２つの項
目のうちの１つをランダムに選択して、該ランダムに選
択した項目を戻すステップをさらに備えることを特徴と
する請求項１２に記載のプロトコル。 - 【請求項１４】 前記第２ノードのアドレス情報と、最
も一致するノードのアドレス情報とを含む応答メッセー
ジを受信するステップと、 前記第２ノードのアドレス情報と、前記最も一致するノ
ードのアドレス情報とを比較するステップと、 前記最も一致するノードのアドレス情報が前記第２ノー
ドのアドレス情報と一致せず、かつ前記最も一致するノ
ードのアドレス情報よりも前記第１ノードのアドレス情
報の方が前記第２ノードのアドレス情報に近いときに、
前記最も一致するノードのアドレス情報を前記第１ノー
ドのアドレス情報で置き換えるステップと、 前記要求側ノードが第１ノードでないときに、前記要求
側ノードに応答メッセージを中継するステップとをさら
に備えることを特徴とする請求項１に記載のプロトコ
ル。 - 【請求項１５】 前記第２ノードの名前のハッシュを計
算することによって、前記第２ノードの一意の番号識別
子を形成するステップをさらに備えることを特徴とする
請求項１に記載のプロトコル。 - 【請求項１６】 前記一意の番号識別子を形成するステ
ップは、＜ハッシュ＞．＜一意の番号＞の形式で前記一
意の番号識別子を形成するために、一意の番号を前記名
前のハッシュに関連付けるステップをさらに備えること
を特徴とする請求項１５に記載のプロトコル。 - 【請求項１７】 前記第２ノードの一意の番号識別子を
ピアツーピアサーバへのＤＮＳ照会によって処理された
一意の番号から抽出するステップであって、前記一意の
名前は＜ピアツーピア識別子＞．＜ＤＮＳサーバアドレ
ス＞の形式をとるステップをさらに備えることを特徴と
する請求項１に記載のプロトコル。 - 【請求項１８】 前記＜ピアツーピア識別子＞は一意の
名前であり、前記第２ノードの名前のハッシュを計算す
ることによって、前記第２ノードの一意の番号識別子を
形成するステップをさらに備えることを特徴とする請求
項１７に記載のプロトコル。 - 【請求項１９】 前記一意の番号識別子を形成するステ
ップは、＜ハッシュ＞．＜一意の番号＞の形式で前記一
意の番号識別子を形成するために、一意の番号を前記名
前のハッシュに関連付けるステップをさらに備えること
を特徴とする請求項１８に記載のプロトコル。 - 【請求項２０】 ピアツーピア名前解決プロトコルで使
用するためのマルチレベルキャッシュであって、一組の
Ｌレベルを備え、各レベルはＫ個の項目を保持するよう
にサイズが調整され、レベルＬの数は動的であり、Ｌ番
目のレベルをＫ個の項目が占有するときにＬ番目のレベ
ルにＫ＋１個の項目が追加される場合、１つだけ増加す
ることを特徴とするキャッシュ。 - 【請求項２１】 ピアツーピア名前解決プロトコルで使
用するためのマルチレベルキャッシュを動的に維持する
方法であって、 前記マルチレベルキャッシュに入れられるべき新しい項
目を受信するステップと、 前記新しい項目がどのレベルに格納されるべきかを決定
するステップと、 前記新しい項目が格納されるべき前記レベルが満杯か否
かを判定するステップと、 前記レベルが満杯でないときに、前記新しい項目を前記
レベルに格納するステップと、 前記レベルが満杯であり、かつ前記レベルがマルチレベ
ルキャッシュの最後のレベルでないときに、前記新しい
項目で別の項目をランダムに置き換えるステップと、 前記レベルが満杯であり、かつ前記レベルがマルチレベ
ルキャッシュの最後のレベルであるときに、新しいレベ
ルを追加して、前記最後のレベルの項目を前記最後のレ
ベルと前記新しいレベルとの間で分類して、新しい項目
を格納するステップとを備えることを特徴とする方法。 - 【請求項２２】 前記項目がどのレベルに格納されるべ
きかを決定するステップは、 前記項目が既に前記マルチレベルキャッシュ内に存在す
るか否かを判定するステップと、アドレス証明がマルチ
レベルキャッシュ内に格納されている前記項目のアドレ
ス証明よりも新しいときに、前記項目のアドレス証明を
置き換えるステップとを備えることを特徴とする請求項
２１に記載の方法。 - 【請求項２３】 前記新しい項目が格納されるべきレベ
ルを決定するステップは、ローカル識別子と項目識別子
との間の距離を計算するステップを備えることを特徴と
する請求項２１に記載の方法。 - 【請求項２４】 ピア名をピアアドレス証明に対して解
決する方法であって、前記ピア名のハッシュ値を計算す
るステップと、それに＜ハッシュ＞．＜一意の番号＞の
形式で一意の番号を関連付けるステップと、要求メッセ
ージをフォーマットするステップと、前記要求メッセー
ジをピアノードに送信するステップとを備えることを特
徴とする方法。 - 【請求項２５】 前記ピアアドレス証明と、最も一致す
るノードのアドレス情報とを含む応答メッセージを受信
するステップと、 前記ピアアドレス証明と、最も一致するノードのアドレ
ス情報とを比較するステップと、 前記最も一致するノードのアドレス情報がピアアドレス
証明と等しくなく、かつ前記最も一致するノードのアド
レス情報よりもローカルノードのアドレス情報の方がピ
アアドレス証明に近いときに、前記最も一致するノード
のアドレス情報を前記ローカルノードのアドレス情報で
置き換えるステップと、 前記要求側ノードが前記ローカルノードでないときに、
前記応答メッセージを前記要求側ノードに中継するステ
ップとをさらに備えることを特徴とする請求項２４に記
載の方法。
Applications Claiming Priority (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US28089601P | 2001-04-02 | 2001-04-02 | |
| US60/280,896 | 2001-08-29 | ||
| US09/942,164 US7065587B2 (en) | 2001-04-02 | 2001-08-29 | Peer-to-peer name resolution protocol (PNRP) and multilevel cache for use therewith |
| US09/942,164 | 2001-08-29 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2002335269A true JP2002335269A (ja) | 2002-11-22 |
| JP4117144B2 JP4117144B2 (ja) | 2008-07-16 |
Family
ID=26960592
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2002100287A Expired - Fee Related JP4117144B2 (ja) | 2001-04-02 | 2002-04-02 | ピアツーピア名前解決プロトコル（ｐｎｒｐ）およびそれと共に使用するためのマルチレベルキャッシュ |
Country Status (5)
| Country | Link |
|---|---|
| US (4) | US7065587B2 (ja) |
| EP (1) | EP1248441B1 (ja) |
| JP (1) | JP4117144B2 (ja) |
| AT (1) | ATE476048T1 (ja) |
| DE (1) | DE60237132D1 (ja) |
Cited By (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2005004777A (ja) * | 2003-06-13 | 2005-01-06 | Microsoft Corp | ピアツーピア名前解決ワイヤプロトコルで使用するデータ構造を格納したコンピュータ可読媒体 |
| JP2005056407A (ja) * | 2003-07-21 | 2005-03-03 | Microsoft Corp | ピアツーピアネットワークでのセキュア階層名前空間 |
| US6912622B2 (en) * | 2002-04-15 | 2005-06-28 | Microsoft Corporation | Multi-level cache architecture and cache management method for peer-to-peer name resolution protocol |
| WO2007060862A1 (ja) * | 2005-11-24 | 2007-05-31 | Brother Kogyo Kabushiki Kaisha | 情報配信システム、情報配信方法、ノード装置、及び記録媒体 |
| JP2008059398A (ja) * | 2006-08-31 | 2008-03-13 | Brother Ind Ltd | 識別情報割当装置及びその情報処理方法並びにそのプログラム |
| US7814214B2 (en) | 2005-04-22 | 2010-10-12 | Microsoft Corporation | Contact management in a serverless peer-to-peer system |
| US7870261B2 (en) | 2003-03-10 | 2011-01-11 | Sony Corporation | Information processing device, an information processing method, and a computer program to securely connect clients on an external network to devices within an internal network |
| US7949996B2 (en) | 2003-10-23 | 2011-05-24 | Microsoft Corporation | Peer-to-peer identity management managed interfaces and methods |
| US8010681B2 (en) | 2002-12-04 | 2011-08-30 | Microsoft Corporation | Communicating between an application process and a server process to manage peer-to-peer identities |
| US8036140B2 (en) | 2005-04-22 | 2011-10-11 | Microsoft Corporation | Application programming interface for inviting participants in a serverless peer to peer network |
| JP2012078902A (ja) * | 2010-09-30 | 2012-04-19 | Brother Ind Ltd | 情報処理装置、情報処理方法及び情報処理プログラム |
| US8688803B2 (en) | 2004-03-26 | 2014-04-01 | Microsoft Corporation | Method for efficient content distribution using a peer-to-peer networking infrastructure |
Families Citing this family (222)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| GB9603582D0 (en) | 1996-02-20 | 1996-04-17 | Hewlett Packard Co | Method of accessing service resource items that are for use in a telecommunications system |
| US6973093B1 (en) | 2000-12-29 | 2005-12-06 | Cisco Technology, Inc. | Switching fabric for interfacing a host processor and a plurality of network modules |
| US7065587B2 (en) * | 2001-04-02 | 2006-06-20 | Microsoft Corporation | Peer-to-peer name resolution protocol (PNRP) and multilevel cache for use therewith |
| DE10143754A1 (de) * | 2001-09-06 | 2003-04-03 | Siemens Ag | Skalierbares Peer-to-Peer-Netzwerk mit einem Verzeichnisdienst |
| US7493363B2 (en) | 2001-09-19 | 2009-02-17 | Microsoft Corporation | Peer-to-peer group management and method for maintaining peer-to-peer graphs |
| US7299351B2 (en) | 2001-09-19 | 2007-11-20 | Microsoft Corporation | Peer-to-peer name resolution protocol (PNRP) security infrastructure and method |
| US7171457B1 (en) * | 2001-09-25 | 2007-01-30 | Juniper Networks, Inc. | Processing numeric addresses in a network router |
| US20030093562A1 (en) * | 2001-11-13 | 2003-05-15 | Padala Chandrashekar R. | Efficient peer to peer discovery |
| US20030126291A1 (en) * | 2001-12-28 | 2003-07-03 | Wang Ben B. | Method and message distributor for routing requests to a processing node |
| US7231463B2 (en) * | 2002-01-04 | 2007-06-12 | Intel Corporation | Multi-level ring peer-to-peer network structure for peer and object discovery |
| EP1343098A1 (en) * | 2002-03-07 | 2003-09-10 | Hewlett-Packard Company | Improvements relating to network environments and location of resources therein |
| US7206862B2 (en) * | 2002-04-24 | 2007-04-17 | Microsoft Corporation | Method and apparatus for efficiently matching responses to requests previously passed by a network node |
| US7051102B2 (en) * | 2002-04-29 | 2006-05-23 | Microsoft Corporation | Peer-to-peer name resolution protocol (PNRP) security infrastructure and method |
| US7721216B2 (en) * | 2002-06-18 | 2010-05-18 | Microsoft Corporation | Visual group interface for group connectivity |
| US7937704B2 (en) | 2002-06-20 | 2011-05-03 | British Telecommunications Public Limited Company | Distributed computer |
| US8320241B2 (en) | 2002-07-30 | 2012-11-27 | Brocade Communications System, Inc. | Fibre channel network employing registered state change notifications with enhanced payload |
| US8438302B2 (en) * | 2002-08-22 | 2013-05-07 | International Business Machines Corporation | Splitting and sharing routing information among several routers acting as a single border router |
| US7289500B1 (en) | 2003-07-17 | 2007-10-30 | Novell, Inc. | Method and system for reliable multicast data transmission |
| US7234117B2 (en) * | 2002-08-28 | 2007-06-19 | Microsoft Corporation | System and method for shared integrated online social interaction |
| US7263560B2 (en) * | 2002-08-30 | 2007-08-28 | Sun Microsystems, Inc. | Decentralized peer-to-peer advertisement |
| US7613796B2 (en) | 2002-09-11 | 2009-11-03 | Microsoft Corporation | System and method for creating improved overlay network with an efficient distributed data structure |
| US7430747B2 (en) * | 2002-12-04 | 2008-09-30 | Microsoft Corporation | Peer-to peer graphing interfaces and methods |
| GB0230331D0 (en) | 2002-12-31 | 2003-02-05 | British Telecomm | Method and apparatus for operating a computer network |
| US7596625B2 (en) | 2003-01-27 | 2009-09-29 | Microsoft Corporation | Peer-to-peer grouping interfaces and methods |
| US7437440B2 (en) * | 2003-01-27 | 2008-10-14 | Microsoft Corporation | Peer-to-peer networking framework application programming interfaces |
| US7139760B2 (en) * | 2003-01-27 | 2006-11-21 | Microsoft Corporation | Peer-to-peer record structure and query language for searching and discovery thereof |
| US8261062B2 (en) | 2003-03-27 | 2012-09-04 | Microsoft Corporation | Non-cryptographic addressing |
| DE602004007064T2 (de) * | 2003-05-23 | 2008-02-21 | Thomson Licensing | Verfahren zur Zuteilung von einem Identifikator zu einer Gruppe von gleichrangigen Knoten in einem gleichrangigen Netz |
| US20040254977A1 (en) * | 2003-06-13 | 2004-12-16 | Microsoft Corporation | Extensible peer-to-peer graphing messages |
| JP3809429B2 (ja) * | 2003-07-25 | 2006-08-16 | キヤノン株式会社 | 管理装置及びその制御方法 |
| US7720006B1 (en) * | 2003-08-06 | 2010-05-18 | Cisco Technology, Inc. | System for determining reachablity of a neighboring node in a network |
| WO2005022397A1 (en) * | 2003-08-28 | 2005-03-10 | Trihedron Co., Ltd. | Method of data synchronization in multiplayer network games |
| DE10345051B4 (de) * | 2003-09-26 | 2009-04-09 | Siemens Ag | Verfahren zum Aufbau einer Kommunikationsverbindung in einem direkt kommunizierenden Kommunikationsnetzwerk |
| US20050080858A1 (en) * | 2003-10-10 | 2005-04-14 | Microsoft Corporation | System and method for searching a peer-to-peer network |
| US8473634B2 (en) * | 2003-10-23 | 2013-06-25 | Microsoft Corporation | System and method for name resolution |
| US8260857B2 (en) * | 2003-10-23 | 2012-09-04 | Microsoft Corporation | One to many data projection system and method |
| US7496648B2 (en) * | 2003-10-23 | 2009-02-24 | Microsoft Corporation | Managed peer name resolution protocol (PNRP) interfaces for peer to peer networking |
| US7567987B2 (en) * | 2003-10-24 | 2009-07-28 | Microsoft Corporation | File sharing in P2P group shared spaces |
| US20050091595A1 (en) * | 2003-10-24 | 2005-04-28 | Microsoft Corporation | Group shared spaces |
| US7716273B2 (en) * | 2003-10-24 | 2010-05-11 | Microsoft Corporation | Systems and methods for projecting content from computing devices |
| US7336623B2 (en) * | 2003-10-30 | 2008-02-26 | Microsoft Corporation | Peer-to-peer cloud-split detection and repair methods |
| KR101129507B1 (ko) * | 2003-11-12 | 2012-07-05 | 아바야 캐나다 코포레이션 | 피어 발견 |
| EP1719325B1 (en) * | 2004-01-23 | 2017-03-29 | Tiversa IP, Inc. | Method for optimally utilizing a peer to peer network |
| US8156175B2 (en) | 2004-01-23 | 2012-04-10 | Tiversa Inc. | System and method for searching for specific types of people or information on a peer-to-peer network |
| US7761569B2 (en) | 2004-01-23 | 2010-07-20 | Tiversa, Inc. | Method for monitoring and providing information over a peer to peer network |
| US20050177715A1 (en) * | 2004-02-09 | 2005-08-11 | Microsoft Corporation | Method and system for managing identities in a peer-to-peer networking environment |
| US7814543B2 (en) * | 2004-02-13 | 2010-10-12 | Microsoft Corporation | System and method for securing a computer system connected to a network from attacks |
| US7603716B2 (en) * | 2004-02-13 | 2009-10-13 | Microsoft Corporation | Distributed network security service |
| US7716726B2 (en) * | 2004-02-13 | 2010-05-11 | Microsoft Corporation | System and method for protecting a computing device from computer exploits delivered over a networked environment in a secured communication |
| US7478120B1 (en) * | 2004-04-27 | 2009-01-13 | Xiaohai Zhang | System and method for providing a peer indexing service |
| JP2005333374A (ja) * | 2004-05-19 | 2005-12-02 | Toshiba Corp | ネットワーク検索システム、情報検索方法、ブリッジ装置及びプログラム |
| US7929689B2 (en) | 2004-06-30 | 2011-04-19 | Microsoft Corporation | Call signs |
| US7317918B2 (en) * | 2004-07-19 | 2008-01-08 | Motorola, Inc. | Method for domain name service (DNS) in a wireless ad hoc network |
| US20060023727A1 (en) * | 2004-07-30 | 2006-02-02 | George David A | Method and apparatus for anonymous data transfers |
| US20060023646A1 (en) * | 2004-07-30 | 2006-02-02 | George David A | Method and apparatus for anonymous data transfers |
| JP2006072432A (ja) * | 2004-08-31 | 2006-03-16 | Onkyo Corp | ピアツーピア型コンテンツ配信システム |
| GB2419199A (en) | 2004-10-18 | 2006-04-19 | Sony Uk Ltd | Storage of content data in a peer-to-peer network |
| US7716727B2 (en) * | 2004-10-29 | 2010-05-11 | Microsoft Corporation | Network security device and method for protecting a computing device in a networked environment |
| CN1934598B (zh) * | 2004-12-24 | 2011-07-27 | 松下电器产业株式会社 | 传感设备、检索设备和中继设备 |
| US8650259B2 (en) * | 2005-02-03 | 2014-02-11 | International Business Machines Corporation | Method and apparatus for increasing the search space or peer-to-peer networks using time-to-live boosting |
| US7647394B2 (en) * | 2005-02-15 | 2010-01-12 | Microsoft Corporation | Scaling UPnP v1.0 device eventing using peer groups |
| US7640329B2 (en) * | 2005-02-15 | 2009-12-29 | Microsoft Corporation | Scaling and extending UPnP v1.0 device discovery using peer groups |
| KR100713145B1 (ko) * | 2005-02-18 | 2007-05-02 | 삼성전자주식회사 | 무선 센서 네트워크에서의 전력소모를 최소화하는 네트워크형성방법 |
| US20060193265A1 (en) * | 2005-02-25 | 2006-08-31 | Microsoft Corporation | Peer-to-peer name resolution protocol with lightweight traffic |
| WO2006093879A2 (en) * | 2005-02-26 | 2006-09-08 | Coco Communications Corporation | Naming system layer |
| US7826396B2 (en) * | 2005-03-07 | 2010-11-02 | Miller John L | System and method for implementing PNRP locality |
| US7912959B2 (en) * | 2005-03-15 | 2011-03-22 | Microsoft Corporation | Architecture for building a peer to peer messaging platform |
| US7656810B2 (en) * | 2005-03-25 | 2010-02-02 | Microsoft Corporation | System and method for monitoring and reacting to peer-to-peer network metrics |
| US7620733B1 (en) * | 2005-03-30 | 2009-11-17 | Cisco Technology, Inc. | DNS anti-spoofing using UDP |
| US7620902B2 (en) * | 2005-04-20 | 2009-11-17 | Microsoft Corporation | Collaboration spaces |
| US7350074B2 (en) * | 2005-04-20 | 2008-03-25 | Microsoft Corporation | Peer-to-peer authentication and authorization |
| US7895270B2 (en) * | 2005-04-21 | 2011-02-22 | Microsoft Corporation | Transport abstraction for multiparty replication |
| US20060239206A1 (en) * | 2005-04-22 | 2006-10-26 | Microsoft Corporation | Apparatus and method for network identification among multiple applications |
| US7817647B2 (en) * | 2005-04-22 | 2010-10-19 | Microsoft Corporation | Flower-petal resolutions for PNRP |
| US20060242236A1 (en) * | 2005-04-22 | 2006-10-26 | Microsoft Corporation | System and method for extensible computer assisted collaboration |
| US7616594B2 (en) * | 2005-04-22 | 2009-11-10 | Microsoft Corporation | Wireless device discovery and configuration |
| US7603482B2 (en) * | 2005-04-22 | 2009-10-13 | Microsoft Corporation | DNS compatible PNRP peer name encoding |
| US7788378B2 (en) * | 2005-04-22 | 2010-08-31 | Microsoft Corporation | Apparatus and method for community relay node discovery |
| US7617281B2 (en) * | 2005-04-25 | 2009-11-10 | Microsoft Corporation | System and method for collaboration with serverless presence |
| US7752253B2 (en) * | 2005-04-25 | 2010-07-06 | Microsoft Corporation | Collaborative invitation system and method |
| US7808971B2 (en) * | 2005-07-01 | 2010-10-05 | Miller John L | Routing cache for distributed hash tables |
| US20070011232A1 (en) * | 2005-07-06 | 2007-01-11 | Microsoft Corporation | User interface for starting presentations in a meeting |
| US20070011231A1 (en) * | 2005-07-06 | 2007-01-11 | Microsoft Corporation | Application and user interface for facilitating a meeting |
| US7660851B2 (en) | 2005-07-06 | 2010-02-09 | Microsoft Corporation | Meetings near me |
| US20070050450A1 (en) * | 2005-08-29 | 2007-03-01 | Microsoft Corporation | Interfacing an applet with a collaboration program |
| US8255546B2 (en) * | 2005-09-30 | 2012-08-28 | Microsoft Corporation | Peer name resolution protocol simple application program interface |
| US8576846B2 (en) | 2005-10-05 | 2013-11-05 | Qualcomm Incorporated | Peer-to-peer communication in ad hoc wireless network |
| US8108548B2 (en) * | 2005-12-22 | 2012-01-31 | Microsoft Corporation | Methodology and system for file replication based on a peergroup |
| US8069208B2 (en) * | 2006-04-21 | 2011-11-29 | Microsoft Corporation | Peer-to-peer buddy request and response |
| US20070250590A1 (en) * | 2006-04-21 | 2007-10-25 | Microsoft Corporation | Ad-hoc proxy for discovery and retrieval of dynamic data such as a list of active devices |
| US8086842B2 (en) | 2006-04-21 | 2011-12-27 | Microsoft Corporation | Peer-to-peer contact exchange |
| US8041942B2 (en) * | 2006-09-05 | 2011-10-18 | Panasonic Corporation | Robust peer-to-peer networks and methods of use thereof |
| AU2007317889B2 (en) * | 2006-11-07 | 2011-05-12 | Kroll Information Assurance, Llc | System and method for enhanced experience with a peer to peer network |
| US8489701B2 (en) * | 2007-01-30 | 2013-07-16 | Microsoft Corporation | Private virtual LAN spanning a public network for connection of arbitrary hosts |
| JP4548441B2 (ja) * | 2007-04-11 | 2010-09-22 | 日本電気株式会社 | コンテンツ利用システム、及びコンテンツ利用方法 |
| EP2149246B1 (en) | 2007-04-12 | 2018-07-11 | Kroll Information Assurance, LLC | A system and method for creating a list of shared information on a peer-to-peer network |
| US7895345B2 (en) * | 2007-04-13 | 2011-02-22 | Microsoft Corporation | Distributed routing table architecture and design |
| US7899188B2 (en) | 2007-05-31 | 2011-03-01 | Motorola Mobility, Inc. | Method and system to authenticate a peer in a peer-to-peer network |
| JP5539863B2 (ja) | 2007-06-11 | 2014-07-02 | タイヴァーサ・インコーポレーテッド | Ｐ２ｐネットワーク上で広告をするためのシステム及び方法 |
| EP2003845B1 (en) * | 2007-06-15 | 2015-07-29 | Alcatel Lucent | Peer chosen as tester for detecting misbehaving peer in structured peer-to-peer networks |
| US7991910B2 (en) * | 2008-11-17 | 2011-08-02 | Amazon Technologies, Inc. | Updating routing information based on client location |
| US8028090B2 (en) | 2008-11-17 | 2011-09-27 | Amazon Technologies, Inc. | Request routing utilizing client location information |
| CN101505262B (zh) | 2008-02-05 | 2011-07-20 | 华为技术有限公司 | 一种构造节点Id的方法和装置 |
| US8533293B1 (en) | 2008-03-31 | 2013-09-10 | Amazon Technologies, Inc. | Client side cache management |
| US7970820B1 (en) | 2008-03-31 | 2011-06-28 | Amazon Technologies, Inc. | Locality based content distribution |
| US8156243B2 (en) | 2008-03-31 | 2012-04-10 | Amazon Technologies, Inc. | Request routing |
| US7962597B2 (en) | 2008-03-31 | 2011-06-14 | Amazon Technologies, Inc. | Request routing based on class |
| US8321568B2 (en) | 2008-03-31 | 2012-11-27 | Amazon Technologies, Inc. | Content management |
| US8447831B1 (en) | 2008-03-31 | 2013-05-21 | Amazon Technologies, Inc. | Incentive driven content delivery |
| US8606996B2 (en) | 2008-03-31 | 2013-12-10 | Amazon Technologies, Inc. | Cache optimization |
| US8601090B1 (en) | 2008-03-31 | 2013-12-03 | Amazon Technologies, Inc. | Network resource identification |
| US7948887B2 (en) | 2008-06-24 | 2011-05-24 | Microsoft Corporation | Network bandwidth measurement |
| US8307093B2 (en) * | 2008-06-25 | 2012-11-06 | Microsoft Corporation | Remote access between UPnP devices |
| US7925782B2 (en) | 2008-06-30 | 2011-04-12 | Amazon Technologies, Inc. | Request routing using network computing components |
| US9407681B1 (en) | 2010-09-28 | 2016-08-02 | Amazon Technologies, Inc. | Latency measurement in resource requests |
| US9912740B2 (en) | 2008-06-30 | 2018-03-06 | Amazon Technologies, Inc. | Latency measurement in resource requests |
| US7930393B1 (en) | 2008-09-29 | 2011-04-19 | Amazon Technologies, Inc. | Monitoring domain allocation performance |
| US7865594B1 (en) | 2008-09-29 | 2011-01-04 | Amazon Technologies, Inc. | Managing resources consolidation configurations |
| US8316124B1 (en) | 2008-09-29 | 2012-11-20 | Amazon Technologies, Inc. | Managing network data display |
| US8286176B1 (en) | 2008-09-29 | 2012-10-09 | Amazon Technologies, Inc. | Optimizing resource configurations |
| US8122124B1 (en) | 2008-09-29 | 2012-02-21 | Amazon Technologies, Inc. | Monitoring performance and operation of data exchanges |
| US8117306B1 (en) | 2008-09-29 | 2012-02-14 | Amazon Technologies, Inc. | Optimizing content management |
| US8219706B2 (en) * | 2008-11-14 | 2012-07-10 | At&T Intellectual Property I, Lp | Interdomain network aware peer-to-peer protocol |
| US8060616B1 (en) | 2008-11-17 | 2011-11-15 | Amazon Technologies, Inc. | Managing CDN registration by a storage provider |
| US8065417B1 (en) | 2008-11-17 | 2011-11-22 | Amazon Technologies, Inc. | Service provider registration by a content broker |
| US8521880B1 (en) | 2008-11-17 | 2013-08-27 | Amazon Technologies, Inc. | Managing content delivery network service providers |
| US8122098B1 (en) | 2008-11-17 | 2012-02-21 | Amazon Technologies, Inc. | Managing content delivery network service providers by a content broker |
| US8732309B1 (en) | 2008-11-17 | 2014-05-20 | Amazon Technologies, Inc. | Request routing utilizing cost information |
| US8073940B1 (en) | 2008-11-17 | 2011-12-06 | Amazon Technologies, Inc. | Managing content delivery network service providers |
| US7917618B1 (en) | 2009-03-24 | 2011-03-29 | Amazon Technologies, Inc. | Monitoring web site content |
| US8412823B1 (en) | 2009-03-27 | 2013-04-02 | Amazon Technologies, Inc. | Managing tracking information entries in resource cache components |
| US8521851B1 (en) | 2009-03-27 | 2013-08-27 | Amazon Technologies, Inc. | DNS query processing using resource identifiers specifying an application broker |
| US8756341B1 (en) | 2009-03-27 | 2014-06-17 | Amazon Technologies, Inc. | Request routing utilizing popularity information |
| US8688837B1 (en) | 2009-03-27 | 2014-04-01 | Amazon Technologies, Inc. | Dynamically translating resource identifiers for request routing using popularity information |
| US8100755B2 (en) | 2009-05-11 | 2012-01-24 | Multimedia Games, Inc. | Method, apparatus, and program product for distributing random number generation on a gaming network |
| US8238538B2 (en) | 2009-05-28 | 2012-08-07 | Comcast Cable Communications, Llc | Stateful home phone service |
| US8782236B1 (en) | 2009-06-16 | 2014-07-15 | Amazon Technologies, Inc. | Managing resources using resource expiration data |
| US8713003B2 (en) | 2009-07-24 | 2014-04-29 | Peer Belt Inc. | System and method for ranking content and applications through human assistance |
| US8352464B2 (en) * | 2009-07-24 | 2013-01-08 | Peer Belt Inc. | System and method for ranking documents through human assistance |
| US8397073B1 (en) | 2009-09-04 | 2013-03-12 | Amazon Technologies, Inc. | Managing secure content in a content delivery network |
| US8433771B1 (en) | 2009-10-02 | 2013-04-30 | Amazon Technologies, Inc. | Distribution network with forward resource propagation |
| JP2011082923A (ja) * | 2009-10-09 | 2011-04-21 | Sony Corp | 端末装置、署名生成サーバ、簡易ｉｄ管理システム、簡易ｉｄの管理方法、及びプログラム |
| US8331371B2 (en) | 2009-12-17 | 2012-12-11 | Amazon Technologies, Inc. | Distributed routing architecture |
| US8331370B2 (en) | 2009-12-17 | 2012-12-11 | Amazon Technologies, Inc. | Distributed routing architecture |
| US9495338B1 (en) | 2010-01-28 | 2016-11-15 | Amazon Technologies, Inc. | Content distribution network |
| US10250678B2 (en) * | 2010-07-07 | 2019-04-02 | Qualcomm Incorporated | Hybrid modes for peer discovery |
| US8402311B2 (en) * | 2010-07-19 | 2013-03-19 | Microsoft Corporation | Monitoring activity with respect to a distributed application |
| US8756272B1 (en) | 2010-08-26 | 2014-06-17 | Amazon Technologies, Inc. | Processing encoded content |
| US8930513B1 (en) | 2010-09-28 | 2015-01-06 | Amazon Technologies, Inc. | Latency measurement in resource requests |
| US10097398B1 (en) * | 2010-09-28 | 2018-10-09 | Amazon Technologies, Inc. | Point of presence management in request routing |
| US8819283B2 (en) | 2010-09-28 | 2014-08-26 | Amazon Technologies, Inc. | Request routing in a networked environment |
| US9712484B1 (en) | 2010-09-28 | 2017-07-18 | Amazon Technologies, Inc. | Managing request routing information utilizing client identifiers |
| US8938526B1 (en) | 2010-09-28 | 2015-01-20 | Amazon Technologies, Inc. | Request routing management based on network components |
| US8577992B1 (en) | 2010-09-28 | 2013-11-05 | Amazon Technologies, Inc. | Request routing management based on network components |
| US9003035B1 (en) | 2010-09-28 | 2015-04-07 | Amazon Technologies, Inc. | Point of presence management in request routing |
| US8924528B1 (en) | 2010-09-28 | 2014-12-30 | Amazon Technologies, Inc. | Latency measurement in resource requests |
| US10958501B1 (en) | 2010-09-28 | 2021-03-23 | Amazon Technologies, Inc. | Request routing information based on client IP groupings |
| US8468247B1 (en) | 2010-09-28 | 2013-06-18 | Amazon Technologies, Inc. | Point of presence management in request routing |
| US8452874B2 (en) | 2010-11-22 | 2013-05-28 | Amazon Technologies, Inc. | Request routing processing |
| US8626950B1 (en) | 2010-12-03 | 2014-01-07 | Amazon Technologies, Inc. | Request routing processing |
| US9391949B1 (en) | 2010-12-03 | 2016-07-12 | Amazon Technologies, Inc. | Request routing processing |
| US8681995B2 (en) * | 2010-12-21 | 2014-03-25 | Microsoft Corporation | Supporting DNS security in a multi-master environment |
| WO2012104666A1 (en) * | 2011-01-31 | 2012-08-09 | Telefonaktiebolaget Lm Ericsson (Publ) | Adaptive service discovery in structured peer-to-peer overlay networks and method |
| US10467042B1 (en) | 2011-04-27 | 2019-11-05 | Amazon Technologies, Inc. | Optimized deployment based upon customer locality |
| WO2011157150A2 (zh) * | 2011-05-31 | 2011-12-22 | 华为技术有限公司 | 数据处理方法、缓存节点、协作控制器及系统 |
| TWI441498B (zh) * | 2011-06-07 | 2014-06-11 | Hon Hai Prec Ind Co Ltd | 終端設備及其交換網路協定語音信令的方法 |
| US20130110999A1 (en) * | 2011-10-28 | 2013-05-02 | LogMeln, Inc. | Creating an optimized distribution network for the efficient transfer of data between endpoints |
| US20140059071A1 (en) * | 2012-01-11 | 2014-02-27 | Saguna Networks Ltd. | Methods, circuits, devices, systems and associated computer executable code for providing domain name resolution |
| US8904009B1 (en) | 2012-02-10 | 2014-12-02 | Amazon Technologies, Inc. | Dynamic content delivery |
| US10021179B1 (en) | 2012-02-21 | 2018-07-10 | Amazon Technologies, Inc. | Local resource delivery network |
| US9172674B1 (en) | 2012-03-21 | 2015-10-27 | Amazon Technologies, Inc. | Managing request routing information utilizing performance information |
| US10623408B1 (en) | 2012-04-02 | 2020-04-14 | Amazon Technologies, Inc. | Context sensitive object management |
| US9154551B1 (en) | 2012-06-11 | 2015-10-06 | Amazon Technologies, Inc. | Processing DNS queries to identify pre-processing information |
| US9336302B1 (en) | 2012-07-20 | 2016-05-10 | Zuci Realty Llc | Insight and algorithmic clustering for automated synthesis |
| US9525659B1 (en) | 2012-09-04 | 2016-12-20 | Amazon Technologies, Inc. | Request routing utilizing point of presence load information |
| US9323577B2 (en) | 2012-09-20 | 2016-04-26 | Amazon Technologies, Inc. | Automated profiling of resource usage |
| US9135048B2 (en) | 2012-09-20 | 2015-09-15 | Amazon Technologies, Inc. | Automated profiling of resource usage |
| US10205698B1 (en) | 2012-12-19 | 2019-02-12 | Amazon Technologies, Inc. | Source-dependent address resolution |
| US9294391B1 (en) | 2013-06-04 | 2016-03-22 | Amazon Technologies, Inc. | Managing network computing components utilizing request routing |
| EP3043620B1 (en) * | 2013-09-02 | 2018-03-28 | Fujitsu Ltd. | Node failure determination based on reference-hop-count in wireless sensor networks |
| CN104598392A (zh) * | 2013-10-31 | 2015-05-06 | 南京思润软件有限公司 | 一种利用多级Hash服务器缓存结构的实现方法 |
| US10033627B1 (en) | 2014-12-18 | 2018-07-24 | Amazon Technologies, Inc. | Routing mode and point-of-presence selection service |
| US10097448B1 (en) | 2014-12-18 | 2018-10-09 | Amazon Technologies, Inc. | Routing mode and point-of-presence selection service |
| US10091096B1 (en) | 2014-12-18 | 2018-10-02 | Amazon Technologies, Inc. | Routing mode and point-of-presence selection service |
| US10225326B1 (en) | 2015-03-23 | 2019-03-05 | Amazon Technologies, Inc. | Point of presence based data uploading |
| US9819567B1 (en) | 2015-03-30 | 2017-11-14 | Amazon Technologies, Inc. | Traffic surge management for points of presence |
| US9887932B1 (en) | 2015-03-30 | 2018-02-06 | Amazon Technologies, Inc. | Traffic surge management for points of presence |
| US9887931B1 (en) | 2015-03-30 | 2018-02-06 | Amazon Technologies, Inc. | Traffic surge management for points of presence |
| US9832141B1 (en) | 2015-05-13 | 2017-11-28 | Amazon Technologies, Inc. | Routing based request correlation |
| US10616179B1 (en) | 2015-06-25 | 2020-04-07 | Amazon Technologies, Inc. | Selective routing of domain name system (DNS) requests |
| US10097566B1 (en) | 2015-07-31 | 2018-10-09 | Amazon Technologies, Inc. | Identifying targets of network attacks |
| US9742795B1 (en) | 2015-09-24 | 2017-08-22 | Amazon Technologies, Inc. | Mitigating network attacks |
| US9774619B1 (en) | 2015-09-24 | 2017-09-26 | Amazon Technologies, Inc. | Mitigating network attacks |
| US9794281B1 (en) | 2015-09-24 | 2017-10-17 | Amazon Technologies, Inc. | Identifying sources of network attacks |
| US10270878B1 (en) | 2015-11-10 | 2019-04-23 | Amazon Technologies, Inc. | Routing for origin-facing points of presence |
| CN105898607A (zh) * | 2015-11-20 | 2016-08-24 | 乐视云计算有限公司 | 网络视频播放方法、装置及系统 |
| US10049051B1 (en) | 2015-12-11 | 2018-08-14 | Amazon Technologies, Inc. | Reserved cache space in content delivery networks |
| US10257307B1 (en) | 2015-12-11 | 2019-04-09 | Amazon Technologies, Inc. | Reserved cache space in content delivery networks |
| US10348639B2 (en) | 2015-12-18 | 2019-07-09 | Amazon Technologies, Inc. | Use of virtual endpoints to improve data transmission rates |
| US10075551B1 (en) | 2016-06-06 | 2018-09-11 | Amazon Technologies, Inc. | Request management for hierarchical cache |
| US10110694B1 (en) | 2016-06-29 | 2018-10-23 | Amazon Technologies, Inc. | Adaptive transfer rate for retrieving content from a server |
| US9992086B1 (en) | 2016-08-23 | 2018-06-05 | Amazon Technologies, Inc. | External health checking of virtual private cloud network environments |
| US10033691B1 (en) | 2016-08-24 | 2018-07-24 | Amazon Technologies, Inc. | Adaptive resolution of domain name requests in virtual private cloud network environments |
| US10469513B2 (en) | 2016-10-05 | 2019-11-05 | Amazon Technologies, Inc. | Encrypted network addresses |
| US11205103B2 (en) | 2016-12-09 | 2021-12-21 | The Research Foundation for the State University | Semisupervised autoencoder for sentiment analysis |
| US10831549B1 (en) | 2016-12-27 | 2020-11-10 | Amazon Technologies, Inc. | Multi-region request-driven code execution system |
| US10372499B1 (en) | 2016-12-27 | 2019-08-06 | Amazon Technologies, Inc. | Efficient region selection system for executing request-driven code |
| US10938884B1 (en) | 2017-01-30 | 2021-03-02 | Amazon Technologies, Inc. | Origin server cloaking using virtual private cloud network environments |
| US10503613B1 (en) | 2017-04-21 | 2019-12-10 | Amazon Technologies, Inc. | Efficient serving of resources during server unavailability |
| US11075987B1 (en) | 2017-06-12 | 2021-07-27 | Amazon Technologies, Inc. | Load estimating content delivery network |
| US10447648B2 (en) | 2017-06-19 | 2019-10-15 | Amazon Technologies, Inc. | Assignment of a POP to a DNS resolver based on volume of communications over a link between client devices and the POP |
| US10742593B1 (en) | 2017-09-25 | 2020-08-11 | Amazon Technologies, Inc. | Hybrid content request routing system |
| CN108366136B (zh) * | 2017-12-29 | 2021-04-06 | 北京世纪互联宽带数据中心有限公司 | 一种域名的解析方法及装置 |
| US10521280B2 (en) | 2017-12-29 | 2019-12-31 | Futurewei Technologies, Inc. | Event-driven serverless function orchestration |
| US10565034B2 (en) | 2017-12-29 | 2020-02-18 | Futurewei Technologies, Inc. | Event-driven serverless function orchestration |
| US10592578B1 (en) | 2018-03-07 | 2020-03-17 | Amazon Technologies, Inc. | Predictive content push-enabled content delivery network |
| US10862852B1 (en) | 2018-11-16 | 2020-12-08 | Amazon Technologies, Inc. | Resolution of domain name requests in heterogeneous network environments |
| US11025747B1 (en) | 2018-12-12 | 2021-06-01 | Amazon Technologies, Inc. | Content request pattern-based routing system |
| US10601806B1 (en) * | 2019-02-22 | 2020-03-24 | Capital One Services, Llc | Runtime identity confirmation for restricted server communication control |
| EP3879781B1 (en) * | 2020-03-13 | 2022-07-27 | Deutsche Telekom AG | Methods and systems for network service management in a distributed architecture |
| US11316947B2 (en) | 2020-03-30 | 2022-04-26 | International Business Machines Corporation | Multi-level cache-mesh-system for multi-tenant serverless environments |
| CN112954049A (zh) * | 2021-02-08 | 2021-06-11 | 上海石锤网络科技有限公司 | 一种域名解析的方法及装置 |
Family Cites Families (80)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US2244082A (en) * | 1937-06-14 | 1941-06-03 | James A Reyniers | Apparatus for and method of maintaining and working with biological specimens in a germfree controlled environment |
| US3302615A (en) * | 1965-04-15 | 1967-02-07 | Becton Dickinson Co | Controlled environmental system for handling and rearing laboratory and research animals |
| DE6911912U (de) * | 1969-03-25 | 1969-07-17 | Burger Eisenwerke Ag | Reinigungsvorrichtung fuer brat-,back- und auftaumuffeln |
| DE2330747C3 (de) * | 1973-06-16 | 1978-06-22 | Euro-Clinic-Schuck & Co, 8000 Muenchen | Desinfektions-Tauchtank |
| US5025491A (en) * | 1988-06-23 | 1991-06-18 | The Mitre Corporation | Dynamic address binding in communication networks |
| WO1993024890A1 (en) | 1992-06-03 | 1993-12-09 | Pitts William R | System for accessing distributed data cache channel at each network node to pass requests and data |
| JPH0646062A (ja) | 1992-07-23 | 1994-02-18 | Hitachi Ltd | 統合ネットワークシステムにおけるアドレス解決方法 |
| US5689679A (en) * | 1993-04-28 | 1997-11-18 | Digital Equipment Corporation | Memory system and method for selective multi-level caching using a cache level code |
| US5586264A (en) * | 1994-09-08 | 1996-12-17 | Ibm Corporation | Video optimized media streamer with cache management |
| JP4008049B2 (ja) | 1995-03-20 | 2007-11-14 | 富士通株式会社 | アドレス送信装置、アドレス送信方法およびアドレス送信システム |
| US5638448A (en) * | 1995-10-24 | 1997-06-10 | Nguyen; Minhtam C. | Network with secure communications sessions |
| AU2343097A (en) * | 1996-03-21 | 1997-10-10 | Mpath Interactive, Inc. | Network match maker for selecting clients based on attributes of servers and communication links |
| JPH09266475A (ja) | 1996-03-28 | 1997-10-07 | Hitachi Ltd | アドレス情報管理装置およびネットワークシステム |
| US6009458A (en) * | 1996-05-09 | 1999-12-28 | 3Do Company | Networked computer game system with persistent playing objects |
| JP3514279B2 (ja) | 1997-02-21 | 2004-03-31 | 日本電信電話株式会社 | 相手選択型アドレス解決方法及びその装置 |
| JP3457493B2 (ja) * | 1997-03-18 | 2003-10-20 | 富士通株式会社 | Ａｒｐサーバ |
| US5933849A (en) * | 1997-04-10 | 1999-08-03 | At&T Corp | Scalable distributed caching system and method |
| US6167438A (en) | 1997-05-22 | 2000-12-26 | Trustees Of Boston University | Method and system for distributed caching, prefetching and replication |
| US6351775B1 (en) | 1997-05-30 | 2002-02-26 | International Business Machines Corporation | Loading balancing across servers in a computer network |
| US5987376A (en) * | 1997-07-16 | 1999-11-16 | Microsoft Corporation | System and method for the distribution and synchronization of data and state information between clients in a distributed processing system |
| US6144959A (en) * | 1997-08-18 | 2000-11-07 | Novell, Inc. | System and method for managing user accounts in a communication network |
| US6134327A (en) * | 1997-10-24 | 2000-10-17 | Entrust Technologies Ltd. | Method and apparatus for creating communities of trust in a secure communication system |
| US6308266B1 (en) * | 1998-03-04 | 2001-10-23 | Microsoft Corporation | System and method for enabling different grades of cryptography strength in a product |
| US6205481B1 (en) * | 1998-03-17 | 2001-03-20 | Infolibria, Inc. | Protocol for distributing fresh content among networked cache servers |
| US6134550A (en) * | 1998-03-18 | 2000-10-17 | Entrust Technologies Limited | Method and apparatus for use in determining validity of a certificate in a communication system employing trusted paths |
| US6532217B1 (en) * | 1998-06-29 | 2003-03-11 | Ip Dynamics, Inc. | System for automatically determining a network address |
| US6615347B1 (en) * | 1998-06-30 | 2003-09-02 | Verisign, Inc. | Digital certificate cross-referencing |
| US6269099B1 (en) * | 1998-07-01 | 2001-07-31 | 3Com Corporation | Protocol and method for peer network device discovery |
| US6304974B1 (en) * | 1998-11-06 | 2001-10-16 | Oracle Corporation | Method and apparatus for managing trusted certificates |
| US6304913B1 (en) * | 1998-11-09 | 2001-10-16 | Telefonaktiebolaget L M Ericsson (Publ) | Internet system and method for selecting a closest server from a plurality of alternative servers |
| US6947398B1 (en) * | 1998-11-13 | 2005-09-20 | Lucent Technologies Inc. | Addressing scheme for a multimedia mobile network |
| US6614774B1 (en) | 1998-12-04 | 2003-09-02 | Lucent Technologies Inc. | Method and system for providing wireless mobile server and peer-to-peer services with dynamic DNS update |
| JP3859385B2 (ja) | 1999-03-30 | 2006-12-20 | 株式会社リコー | ファクシミリ装置 |
| US6363376B1 (en) * | 1999-08-02 | 2002-03-26 | Individual Software, Inc. | Method and system for querying and posting to multiple career websites on the internet from a single interface |
| JP2001053806A (ja) | 1999-08-13 | 2001-02-23 | Fuji Print Kogyo Kk | 経路選択アドレスの自動設定方法および経路選択方法 |
| AU6795100A (en) | 1999-08-21 | 2001-03-19 | Webever, Inc. | Method for content delivery over the internet |
| US6654796B1 (en) * | 1999-10-07 | 2003-11-25 | Cisco Technology, Inc. | System for managing cluster of network switches using IP address for commander switch and redirecting a managing request via forwarding an HTTP connection to an expansion switch |
| US6683865B1 (en) * | 1999-10-15 | 2004-01-27 | Nokia Wireless Routers, Inc. | System for routing and switching in computer networks |
| US6898200B1 (en) * | 1999-10-29 | 2005-05-24 | Nortel Networks Limited | Method for improving signaling efficiency and performing service load balancing in a connection oriented network |
| US6748420B1 (en) * | 1999-11-23 | 2004-06-08 | Cisco Technology, Inc. | Methods and apparatus for providing shared access to an application |
| US20010032258A1 (en) * | 2000-03-31 | 2001-10-18 | Kabushiki Kaisha Free Bit.Com | System for internet connections, system for providing internet user information, method for providing internet user preference information, and method for distributing digital contents using the internet |
| US20020119821A1 (en) * | 2000-05-12 | 2002-08-29 | Sanjoy Sen | System and method for joining a broadband multi-user communication session |
| JP2001326632A (ja) * | 2000-05-17 | 2001-11-22 | Fujitsu Ltd | 分散グループ管理システムおよび方法 |
| US7031268B1 (en) * | 2000-05-17 | 2006-04-18 | Cisco Technology, Inc. | Call optimization in ad-hoc conference calls |
| EP1162788B1 (en) * | 2000-06-09 | 2012-11-21 | Broadcom Corporation | Trunking and mirroring across stacked gigabit switches |
| US20030177187A1 (en) * | 2000-11-27 | 2003-09-18 | Butterfly.Net. Inc. | Computing grid for massively multi-player online games and other multi-user immersive persistent-state and session-based applications |
| US6636854B2 (en) * | 2000-12-07 | 2003-10-21 | International Business Machines Corporation | Method and system for augmenting web-indexed search engine results with peer-to-peer search results |
| US20020073204A1 (en) * | 2000-12-07 | 2002-06-13 | Rabindranath Dutta | Method and system for exchange of node characteristics for DATA sharing in peer-to-peer DATA networks |
| US6826198B2 (en) * | 2000-12-18 | 2004-11-30 | Telefonaktiebolaget Lm Ericsson (Publ) | Signaling transport protocol extensions for load balancing and server pool support |
| US20040213220A1 (en) * | 2000-12-28 | 2004-10-28 | Davis Arlin R. | Method and device for LAN emulation over infiniband fabrics |
| US7197565B2 (en) * | 2001-01-22 | 2007-03-27 | Sun Microsystems, Inc. | System and method of using a pipe advertisement for a peer-to-peer network entity in peer-to-peer presence detection |
| US20020116533A1 (en) * | 2001-02-20 | 2002-08-22 | Holliman Matthew J. | System for providing a multimedia peer-to-peer computing platform |
| US7065587B2 (en) * | 2001-04-02 | 2006-06-20 | Microsoft Corporation | Peer-to-peer name resolution protocol (PNRP) and multilevel cache for use therewith |
| US7272636B2 (en) * | 2001-04-24 | 2007-09-18 | Sun Microsystems, Inc. | Peer group name server |
| US7177950B2 (en) * | 2001-04-26 | 2007-02-13 | Microsoft Corporation | Synchronization and recovery of peers in a peer to peer environment |
| US6961723B2 (en) * | 2001-05-04 | 2005-11-01 | Sun Microsystems, Inc. | System and method for determining relevancy of query responses in a distributed network search mechanism |
| US7380279B2 (en) * | 2001-07-16 | 2008-05-27 | Lenel Systems International, Inc. | System for integrating security and access for facilities and information systems |
| US7383433B2 (en) * | 2001-07-31 | 2008-06-03 | Sun Microsystems, Inc. | Trust spectrum for certificate distribution in distributed peer-to-peer networks |
| US7299351B2 (en) * | 2001-09-19 | 2007-11-20 | Microsoft Corporation | Peer-to-peer name resolution protocol (PNRP) security infrastructure and method |
| US7493363B2 (en) * | 2001-09-19 | 2009-02-17 | Microsoft Corporation | Peer-to-peer group management and method for maintaining peer-to-peer graphs |
| US7068789B2 (en) * | 2001-09-19 | 2006-06-27 | Microsoft Corporation | Peer-to-peer name resolution protocol (PNRP) group security infrastructure and method |
| US6674459B2 (en) * | 2001-10-24 | 2004-01-06 | Microsoft Corporation | Network conference recording system and method including post-conference processing |
| US7177929B2 (en) * | 2002-03-27 | 2007-02-13 | International Business Machines Corporation | Persisting node reputations in transient network communities |
| US7130999B2 (en) * | 2002-03-27 | 2006-10-31 | Intel Corporation | Using authentication certificates for authorization |
| US6912622B2 (en) * | 2002-04-15 | 2005-06-28 | Microsoft Corporation | Multi-level cache architecture and cache management method for peer-to-peer name resolution protocol |
| US7206862B2 (en) * | 2002-04-24 | 2007-04-17 | Microsoft Corporation | Method and apparatus for efficiently matching responses to requests previously passed by a network node |
| US7711847B2 (en) * | 2002-04-26 | 2010-05-04 | Sony Computer Entertainment America Inc. | Managing users in a multi-user network game environment |
| US7051102B2 (en) * | 2002-04-29 | 2006-05-23 | Microsoft Corporation | Peer-to-peer name resolution protocol (PNRP) security infrastructure and method |
| US7139798B2 (en) * | 2002-05-17 | 2006-11-21 | Groove Networks, Inc. | Method and apparatus for connecting a secure peer-to-peer collaboration system to an external system |
| US20030236976A1 (en) * | 2002-06-19 | 2003-12-25 | Microsoft Corporation | Efficient membership revocation by number |
| US7277946B2 (en) * | 2002-06-28 | 2007-10-02 | Microsoft Corporation | Distributed session listing and content discovery |
| US7392375B2 (en) * | 2002-09-18 | 2008-06-24 | Colligo Networks, Inc. | Peer-to-peer authentication for real-time collaboration |
| US7461260B2 (en) | 2002-12-31 | 2008-12-02 | Intel Corporation | Methods and apparatus for finding a shared secret without compromising non-shared secrets |
| US20040181487A1 (en) * | 2003-03-10 | 2004-09-16 | Microsoft Corporation | Digital media clearing house platform |
| US7577750B2 (en) * | 2003-05-23 | 2009-08-18 | Microsoft Corporation | Systems and methods for peer-to-peer collaboration to enhance multimedia streaming |
| US7533184B2 (en) * | 2003-06-13 | 2009-05-12 | Microsoft Corporation | Peer-to-peer name resolution wire protocol and message format data structure for use therein |
| US7397922B2 (en) * | 2003-06-27 | 2008-07-08 | Microsoft Corporation | Group security |
| US7188254B2 (en) * | 2003-08-20 | 2007-03-06 | Microsoft Corporation | Peer-to-peer authorization method |
| US7454465B2 (en) * | 2004-03-26 | 2008-11-18 | Microsoft Corporation | Real-time collaboration and communication in a peer-to-peer networking infrastructure |
| US7350074B2 (en) * | 2005-04-20 | 2008-03-25 | Microsoft Corporation | Peer-to-peer authentication and authorization |
-
2001
- 2001-08-29 US US09/942,164 patent/US7065587B2/en not_active Expired - Fee Related
-
2002
- 2002-03-13 EP EP02005770A patent/EP1248441B1/en not_active Expired - Lifetime
- 2002-03-13 DE DE60237132T patent/DE60237132D1/de not_active Expired - Lifetime
- 2002-03-13 AT AT02005770T patent/ATE476048T1/de not_active IP Right Cessation
- 2002-04-02 JP JP2002100287A patent/JP4117144B2/ja not_active Expired - Fee Related
-
2005
- 2005-06-09 US US11/149,690 patent/US20050267991A1/en not_active Abandoned
- 2005-06-13 US US11/152,588 patent/US7565432B2/en not_active Expired - Fee Related
- 2005-06-13 US US11/152,587 patent/US7962651B2/en not_active Expired - Fee Related
Cited By (16)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6912622B2 (en) * | 2002-04-15 | 2005-06-28 | Microsoft Corporation | Multi-level cache architecture and cache management method for peer-to-peer name resolution protocol |
| US8010681B2 (en) | 2002-12-04 | 2011-08-30 | Microsoft Corporation | Communicating between an application process and a server process to manage peer-to-peer identities |
| US9021106B2 (en) | 2002-12-04 | 2015-04-28 | Microsoft Technology Licensing, Llc | Peer-to-peer identity management interfaces and methods |
| US8756327B2 (en) | 2002-12-04 | 2014-06-17 | Microsoft Corporation | Peer-to-peer identity management interfaces and methods |
| US7870261B2 (en) | 2003-03-10 | 2011-01-11 | Sony Corporation | Information processing device, an information processing method, and a computer program to securely connect clients on an external network to devices within an internal network |
| JP2005004777A (ja) * | 2003-06-13 | 2005-01-06 | Microsoft Corp | ピアツーピア名前解決ワイヤプロトコルで使用するデータ構造を格納したコンピュータ可読媒体 |
| JP2005056407A (ja) * | 2003-07-21 | 2005-03-03 | Microsoft Corp | ピアツーピアネットワークでのセキュア階層名前空間 |
| JP4698180B2 (ja) * | 2003-07-21 | 2011-06-08 | マイクロソフト コーポレーション | ピアツーピアネットワークでのセキュア階層名前空間 |
| US7949996B2 (en) | 2003-10-23 | 2011-05-24 | Microsoft Corporation | Peer-to-peer identity management managed interfaces and methods |
| US8688803B2 (en) | 2004-03-26 | 2014-04-01 | Microsoft Corporation | Method for efficient content distribution using a peer-to-peer networking infrastructure |
| US8036140B2 (en) | 2005-04-22 | 2011-10-11 | Microsoft Corporation | Application programming interface for inviting participants in a serverless peer to peer network |
| US7814214B2 (en) | 2005-04-22 | 2010-10-12 | Microsoft Corporation | Contact management in a serverless peer-to-peer system |
| US8713145B2 (en) | 2005-11-24 | 2014-04-29 | Brother Kogyo Kabushiki Kaisha | Information distribution system, information distributing method, node, and recording medium |
| WO2007060862A1 (ja) * | 2005-11-24 | 2007-05-31 | Brother Kogyo Kabushiki Kaisha | 情報配信システム、情報配信方法、ノード装置、及び記録媒体 |
| JP2008059398A (ja) * | 2006-08-31 | 2008-03-13 | Brother Ind Ltd | 識別情報割当装置及びその情報処理方法並びにそのプログラム |
| JP2012078902A (ja) * | 2010-09-30 | 2012-04-19 | Brother Ind Ltd | 情報処理装置、情報処理方法及び情報処理プログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| ATE476048T1 (de) | 2010-08-15 |
| JP4117144B2 (ja) | 2008-07-16 |
| US20050267993A1 (en) | 2005-12-01 |
| EP1248441A2 (en) | 2002-10-09 |
| US20050267992A1 (en) | 2005-12-01 |
| US7962651B2 (en) | 2011-06-14 |
| US20020143989A1 (en) | 2002-10-03 |
| US20050267991A1 (en) | 2005-12-01 |
| US7565432B2 (en) | 2009-07-21 |
| EP1248441B1 (en) | 2010-07-28 |
| DE60237132D1 (de) | 2010-09-09 |
| US7065587B2 (en) | 2006-06-20 |
| EP1248441A3 (en) | 2005-10-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4117144B2 (ja) | ピアツーピア名前解決プロトコル（ｐｎｒｐ）およびそれと共に使用するためのマルチレベルキャッシュ | |
| US7516482B2 (en) | Secure hierarchical namespaces in peer-to-peer networks | |
| EP1351141B1 (en) | Method and system for managing data records on a computer network | |
| US8166063B2 (en) | Query routing in distributed database system | |
| JP4726604B2 (ja) | リソース要求を対応するリソースに会合させる方法およびシステム | |
| US7478120B1 (en) | System and method for providing a peer indexing service | |
| AU2003203717B2 (en) | Peer-to-peer name resolution protocol (PNRP) security infrastructure and method | |
| JP5049344B2 (ja) | ランデブーフェデレーション内の近傍域間通信 | |
| US20110029688A1 (en) | Logical routing system | |
| Aberer et al. | Efficient, self-contained handling of identity in peer-to-peer systems | |
| KR20090098791A (ko) | 링 일관성을 유지하는 방법, 데이터 액세스 트랜잭션을 수행하는 방법, 연합 인프라 내의 복제 세트로부터 데이터에 액세스하는 시스템, 연합 인프라 내에 일관성있는 복제 세트를 설정 및 유지하는 방법 | |
| JP2009277234A (ja) | コンテンツセントリックネットワークにおける通信を円滑化するための方法 | |
| Karolewicz et al. | On efficient data storage service for IoT | |
| CN114363247A (zh) | 一种构建区块链全分布式节点路由网络的方法 | |
| Liu et al. | Double‐layer P2P networks supporting semantic search and keeping scalability | |
| Chen et al. | P2P overlay networks of constant degree | |
| JP4426183B2 (ja) | 論理経路制御システム | |
| Misra et al. | Dividing PKI in strongest availability zones | |
| Cojocar | BBUFs: A new lookup mechanism based on IPV6 | |
| Song et al. | Cbrbrain: Provide content based routing service over internet backbone | |
| Goodrich et al. | Reliable Resource Searching in P2P Networks | |
| Doval | Self-organizing resource location and discovery | |
| Nguyen et al. | Sens: A scalable and expressive naming system using can routing algorithm | |
| Hauswirth et al. | Efficient, self-contained handling of identity in Peer-to-Peer systems | |
| Peruru | CHOReLLA±A Reliable and Scalable Addressing Scheme for Data Distribution |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20050331 |
|
| RD04 | Notification of resignation of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7424 Effective date: 20050331 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20070307 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20070316 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20070618 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20070921 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20071221 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20080321 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20080421 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110425 Year of fee payment: 3 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110425 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120425 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120425 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130425 Year of fee payment: 5 |
|
| LAPS | Cancellation because of no payment of annual fees |