(57)【特許請求の範囲】
【請求項１】
複数のノードを含むピアツーピア（Ｐ２Ｐ）ネットワーク内でサービスを検索する方法であって、
前記Ｐ２Ｐネットワークの第１ノードで、前記Ｐ２Ｐネットワーク内のサービスを検索する要求を検出するステップであって、前記第１ノードは、前記Ｐ２Ｐネットワークの複数のノードを識別するエントリの集合を含む、ステップと、
前記サービスをサポートする前記Ｐ２Ｐネットワークのアクティブ・ノードの推定平均個数に基づいて、前記Ｐ２Ｐネットワーク内で前記サービスを検索する際に前記第１ノードによって使用される検索範囲のサイズを決定するステップと、
前記Ｐ２Ｐネットワーク内で前記サービスを検索する際に前記第１ノードによって使用される前記検索範囲の前記サイズに基づいて、エントリの前記集合内で識別されるノードの部分集合を選択するステップと、
前記選択されたノードのうちの１つに向かって前記第１ノードからサービス検索要求を開始するステップであって、前記サービス検索要求は、前記サービスをサポートする前記Ｐ２Ｐネットワークの少なくとも１つのノードを識別する要求であり、前記サービス検索要求は、前記サービスおよび前記サービス検索要求がそれに向かって開始される前記ノードによって使用される検索範囲を示す情報を含み、前記サービス検索要求がそれに向かって開始される前記ノードによって使用される前記検索範囲は、前記Ｐ２Ｐネットワークのノード識別子の範囲を指定する、ステップと
を含む方法。
【請求項２】
前記Ｐ２Ｐネットワーク内で前記サービスを検索する際に前記第１ノードによって使用される前記検索範囲の前記サイズは、前記Ｐ２Ｐネットワーク内の前記サービスに対する検索の成功に関連した確率にさらに基づいている、請求項１に記載の方法。
【請求項３】
前記Ｐ２Ｐネットワーク内で前記サービスを検索する際に前記第１ノードによって使用される前記検索範囲の前記サイズは、（Ｌ−１）＊ｌｎ（ｌ−ａ）＜ｌｎ（ｌ／ｂ）に基づき、
“ａ”はアクティブ・ノードが前記サービスをサポートしている確率であり、
“ｂ”は前記サービスに対する検索が否定である確率であり、
“Ｌ”は前記サービスを検索する際に前記第１ノードによって使用される前記検索範囲の前記サイズである、請求項１に記載の方法。
【請求項４】
前記Ｐ２Ｐネットワーク内で前記サービスを検索する際に前記第１ノードによって使用される前記検索範囲の前記サイズに基づいて、エントリの前記集合内で識別されるノードの前記部分集合を選択するステップは、
エントリの前記集合と前記Ｐ２Ｐネットワーク内で前記サービスを検索する際に前記第１ノードによって使用される前記検索範囲の前記サイズに基づいて、前記第１ノードがサービス検索要求をそれに向かって開始すべきエントリの前記集合内のノードの個数（Ｋ）を決定するステップ
を含む、請求項１に記載の方法。
【請求項５】
選択されたノードの前記部分集合はエントリの前記集合からの複数のノードを含み、
複数のサービス検索要求を前記第１ノードから前記複数のノードのそれぞれに向かって並行して開始するステップ
をさらに含む、請求項１に記載の方法。
【請求項６】
肯定の検索応答がノードの前記部分集合の前記ノードのうちの少なくとも１つから受信されないという決定に基づいて、
エントリの前記集合のノードの前記部分集合に含まれないエントリの前記集合の次のエントリに関連する次のノードに向かって、前記Ｐ２Ｐネットワーク内の前記サービスを突き止めるために後続サービス検索要求を開始するステップ
をさらに含む、請求項１に記載の方法。
【請求項７】
前記Ｐ２Ｐネットワーク内で前記サービスを検索する際に前記第１ノードによって使用される前記検索範囲の前記サイズに基づいて、前記サービス検索要求がそれに向かって開始される前記次のノードによって使用される検索範囲を決定するステップ
をさらに含む、請求項６に記載の方法。
【請求項８】
前記第１ノードが、前記サービスをサポートするノードが突き止められたことを示す肯定の検索応答を受信する時に、前記サービスをサポートする前記ノードに向かって前記第１ノードから前記サービスの要求を開始するステップ
をさらに含む、請求項１に記載の方法。
【請求項９】
複数のノードを含むピアツーピア（Ｐ２Ｐ）ネットワーク内でサービスを検索する装置であって、
プロセッサーと、前記プロセッサーに通信可能に接続されたメモリと、を含み、
前記プロセッサーは、
前記Ｐ２Ｐネットワークの第１ノードで、前記Ｐ２Ｐネットワーク内のサービスを検索する要求を検出し、前記第１ノードは、前記Ｐ２Ｐネットワークの複数のノードを識別するエントリの集合を含み、
前記サービスをサポートする前記Ｐ２Ｐネットワークのアクティブ・ノードの推定平均個数に基づいて、前記Ｐ２Ｐネットワーク内で前記サービスを検索する際に前記第１ノードによって使用される検索範囲のサイズを決定し、
前記Ｐ２Ｐネットワーク内で前記サービスを検索する際に前記第１ノードによって使用される前記検索範囲の前記サイズに基づいて、エントリの前記集合内で識別されるノードの部分集合を選択し、
前記選択されたノードのうちの１つに向かって前記第１ノードからサービス検索要求を開始し、前記サービス検索要求は、前記サービスをサポートする前記Ｐ２Ｐネットワークの少なくとも１つのノードを識別する要求であり、前記サービス検索要求は、前記サービスおよび前記サービス検索要求がそれに向かって開始される前記ノードによって使用される検索範囲を示す情報を含み、前記サービス検索要求がそれに向かって開始される前記ノードによって使用される前記検索範囲は、前記Ｐ２Ｐネットワークのノード識別子の範囲を指定する
ように構成された、
装置。
【請求項１０】
コンピュータによって実行される時に、複数のノードを含むピアツーピア（Ｐ２Ｐ）ネットワーク内でサービスを検索する方法を前記コンピュータに実行させる命令が記憶されている、コンピュータで読み取り可能な記憶媒体であって、
前記方法は、
前記Ｐ２Ｐネットワークの第１ノードで、前記Ｐ２Ｐネットワーク内のサービスを検索する要求を検出するステップであって、前記第１ノードは、前記Ｐ２Ｐネットワークの複数のノードを識別するエントリの集合を含む、ステップと、
前記サービスをサポートする前記Ｐ２Ｐネットワークのアクティブ・ノードの推定平均個数に基づいて、前記Ｐ２Ｐネットワーク内で前記サービスを検索する際に前記第１ノードによって使用される検索範囲のサイズを決定するステップと、
前記Ｐ２Ｐネットワーク内で前記サービスを検索する際に前記第１ノードによって使用される前記検索範囲の前記サイズに基づいて、エントリの前記集合内で識別されるノードの部分集合を選択するステップと、
前記選択されたノードのうちの１つに向かって前記第１ノードからサービス検索要求を開始するステップであって、前記サービス検索要求は、前記サービスをサポートする前記Ｐ２Ｐネットワークの少なくとも１つのノードを識別する要求であり、前記サービス検索要求は、前記サービスおよび前記サービス検索要求がそれに向かって開始される前記ノードによって使用される検索範囲を示す情報を含み、前記サービス検索要求がそれに向かって開始される前記ノードによって使用される前記検索範囲は、前記Ｐ２Ｐネットワークのノード識別子の範囲を指定する、ステップと
を含む、
コンピュータで読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本願は、参照によってその全体が本明細書に組み込まれている、２００９年１２月１７日に出願した米国特許出願第１２／６４０，０４９号［弁理士整理番号第ＡＬＵ／８０５５２０号］、名称「ＭＥＴＨＯＤ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  ＤＥＣＯＭＰＯＳＩＮＧ  Ａ  ＰＥＥＲ−ＴＯ−ＰＥＥＲ  ＮＥＴＷＯＲＫ  ＡＮＤ  ＵＳＩＮＧ  Ａ  ＤＥＣＯＭＰＯＳＥＤ  ＰＥＥＲ−ＴＯ−ＰＥＥＲ  ＮＥＴＷＯＲＫ」に関連する。
【０００２】
本発明は、ピアツーピア（Ｐ２Ｐ）ネットワークの分野に関し、排他的にではないがより具体的には、Ｐ２Ｐネットワーク内でサービスを突き止めることに関する。
【背景技術】
【０００３】
ファイル共有は、しばらくの間、激しい研究および草の根使用の焦点であった。ファイル共有は、その目的のために特に設計され、それに関連するファイル共有プロトコルを有する異なるファイル共有システムとして実施された、ファイル共有手法によって使用可能にされる。Ｎａｐｓｔｅｒから始まり、その後、ｇｎｕｔｅｌｌａ、Ｋａｚａａ、ｅＤｏｎｋｅｙ、Ｗｉｎｎｙ、およびＢｉｔＴｏｒｒｅｎｔなどの異なるファイル共有システムの複数の世代を通じて前進する、複数の異なるファイル共有システムが実施されてきた。これらのファイル共有システムに加えて、ＳｈａｒｅおよびＰｅｒｆｅｃｔ  Ｄａｒｋなどの新しいシステムも開発されつつある。集合的に、これらのファイル共有システムおよび関連するプロトコルを、ピアツーピア（Ｐ２Ｐ）ファイル共有システム／プロトコルまたはより単純にＰ２Ｐファイル共有アプリケーションと称する。さらに、Ｐ２Ｐファイル共有アプリケーションに加えて、新しいクラスのＰ２ＰアプリケーションすなわちＰ２Ｐテレビジョン（Ｐ２ＰＴＶ）が現れようとしており、このＰ２ＰＴＶは、アーキテクチャ的にＰ２Ｐファイル共有アプリケーションとは異なる。
【０００４】
Ｐ２Ｐファイル共有の人気は、最近のトラフィック調査から明白である。たとえば、Ｅｌｌａｃｏｙａ  Ｎｅｔｗｏｒｋｓ社による、米国内の百万人のブロードバンド・ユーザの最近のトラフィック調査は、量による主要なトラフィック・タイプの分類が、ウェブ（ＨＴＴＰ）４６％、ピアツーピア（Ｐ２Ｐ）３７％、ニュースグループ９％、非ＨＴＴＰストリーミング・ビデオ３％、ゲーミング２％、ｖｏｉｃｅ−ｏｖｅｒ−ＩＰ（ＶｏＩＰ）１％、その他１％であることを示す。大量のＨＴＴＰトラフィックの主な理由は、ＹｏｕＴｕｂｅからのトラフィックなど、埋込みビデオ・ストリーミング・トラフィックであり、ＹｏｕＴｕｂｅからのトラフィックは、上で述べた調査で総トラフィックの９．８％を占める）。しかし、Ｐ２Ｐファイル共有は、それでも、トラフィックのかなりのパーセンテージの責任を負い、Ｐ２ＰＴＶの登場に伴って、トラフィックの量が劇的に増加すると期待される。
【０００５】
既存のＰ２Ｐアプリケーションの大多数は、ファイル共有を用いるが、ファイル共有を用いる既存Ｐ２Ｐアプリケーションの大部分は、少なくとも当初は、完全にピアツーピアではなかった。そうではなく、ほとんどの既存Ｐ２Ｐアプリケーションは、当初に、Ｐ２Ｐネットワークのメンバの間のアクティビティを調整するために中央サーバを利用した。たとえば、ｂｉｔＴｏｒｒｅｎｔは、情報の異なる部分のダウンロードがピアツーピアであったが、ｂｉｔＴｏｒｒｅｎｔではトラッカと称する集中化サーバが、ｂｉｔＴｏｒｒｅｎｔアプリケーションのアクティビティを調整するのに使用された。同様に、たとえば、ＮａｐｓｔｅｒおよびｅＤｏｎｋｅｙなど、ファイル共有を用いる多数の他のＰ２Ｐアプリケーションも、類似する特性を有した。しかし、中央サーバの使用は、既存Ｐ２Ｐアプリケーションを輻輳および障害に脆弱にし、さらに、既存Ｐ２Ｐアプリケーションをセキュリティ脅威の魅力的なターゲットにする。
【０００６】
しかし、不利なことに、既存Ｐ２Ｐアプリケーションはファイル共有をサポートするが、既存Ｐ２Ｐアプリケーションは、サービスを検索する能力をサポートしない。
【発明の概要】
【課題を解決するための手段】
【０００７】
従来技術のさまざまな不足は、Ｃｈｏｒｄネットワークまたは他の適切なピアツーピア（Ｐ２Ｐ）ネットワークなど、Ｐ２Ｐネットワーク内でサービス・ロケーション能力をサポートする実施形態によって対処される。
【０００８】
一実施形態では、Ｐ２Ｐネットワーク内でサービスを突き止める方法が提供される。Ｐ２Ｐネットワークは、Ｐ２Ｐネットワーク内でサービスを突き止める方法を実行するターゲット・ノードを含む複数のノードを含む。ターゲット・ノードは、Ｐ２Ｐネットワークのそれぞれの複数のノードを識別する複数のエントリを含む検索テーブルを含む。この方法は、Ｐ２Ｐネットワーク内のサービスを検索する要求を検出するステップと、検索テーブルのノードのうちの少なくとも１つに向かってサービス検索要求を開始するステップとを含む。サービス検索要求は、サービスをサポートするＰ２Ｐネットワークの少なくとも１つのノードを識別する要求である。サービス検索要求は、サービスおよびサービス検索要求を受信するノードによって使用される検索範囲を示す情報を含む。
【０００９】
本明細書の教示を、添付図面と共に次の詳細な説明を考慮することによってたやすく理解することができる。
【図面の簡単な説明】
【００１０】
【図１】例示的なＣｈｏｒｄネットワークを示す図である。
【図２】図１の例示的なＣｈｏｒｄネットワークのノードのうちの１つによって開始されたサービス・ロケーション検索に応答して図１の例示的なＣｈｏｒｄネットワーク内で開始されるサービス検索要求メッセージを示す図である。
【図３】サービス・ロケーション要求を開始するノードでサービス検索要求メッセージを生成する方法の一実施形態を示す図である。
【図４】中間ノードでサービス検索要求メッセージを処理する方法の一実施形態を示す図である。
【図５】中間ノードでサービス検索応答メッセージを処理する方法の一実施形態を示す図である。
【図６】例示的なＣｈｏｒｄネットワーク内でサービスの漸進的サービス・ロケーション検索を実行する例を示す、例示的なＣｈｏｒｄネットワークを示す図である。
【図７】図６の例示的なＣｈｏｒｄネットワークでサービスの漸進的サービス・ロケーション検索を実行するための例示的検索範囲を示す図である。
【図８】位置合せされた漸進的検索ロケーション検索を使用して、サービス・ロケーション要求を開始するノードでサービス検索要求メッセージを生成する方法の一実施形態を示す図である。
【図９】図１の例示的なＣｈｏｒｄネットワークでのサービスの位置合せされた漸進的検索ロケーション検索を実行する例を示す、図１の例示的なＣｈｏｒｄネットワークのノードのうちの１つによって開始されたサービス・ロケーション検索に応答して図１の例示的なＣｈｏｒｄネットワーク内で開始されるサービス検索要求メッセージを示す図である。
【図１０】本明細書で説明した機能を実行する際に使用するのに適する汎用コンピュータを示す高水準ブロック図である。
【発明を実施するための形態】
【００１１】
理解を容易にするために、可能な場合には、複数の図に共通する同一の要素を示すのに、同一の符号を使用した。
【００１２】
ピアツーピア（Ｐ２Ｐ）ネットワーク内でサービスを突き止める際に使用されるサービス・ロケーション能力を提供する。
【００１３】
一実施形態によるサービス・ロケーション能力は、Ｐ２Ｐネットワーク内のターゲット・ノードが、たとえばサービスをサポートするＰ２Ｐネットワークの１つまたは複数の他のノードを検索するために、Ｐ２Ｐネットワーク内で特定のサービスのロケーションを検索することを可能にする。サービス・ロケーション能力は、サービス・ロケーション検索を実行するために、Ｐ２Ｐネットワークのノードの既存の検索テーブルを再利用する。サービス検索要求が、検索テーブルのすべてのノードに対して並列に、サービスが突き止められるか検索テーブルが使い果たされるまで検索テーブルのすべてのノードに対して直列に、サービスが突き止められるか検索テーブルが使い果たされるまで検索テーブルのノードの部分集合に対して並列におよびその後に検索テーブルのすべての残りのノードに対して直列に、かつ／または任意の他の適切な方式を使用して開始されるように、ターゲット・ノードによって開始されるサービス・ロケーション検索を実行することができる。サービス・ロケーション検索では、ノードに送信される各サービス検索要求は、要求されるサービス、検索要求を受信するノードによって使用される検索範囲、およびオプションでサービス固有情報を示す情報を含む。サービス検索要求は、他のタイプの情報を含むことができる。ノードによって開始されるサービス・ロケーション検索は、多くともＭ個の検索メッセージを生成し、各ノードが多くともＭ個の応答メッセージを受信するようになっており（ここで、Ｍは、Ｐ２Ｐネットワークのキー空間のビット単位のサイズである）、したがって、Ｐ２Ｐネットワーク全体にまたがる検索は、Ｐ２Ｐネットワークのどの単一のノードも検索要求および／または応答メッセージによって過負荷にならないように分散される。サービス・ロケーション検索能カは、第１Ｐ２Ｐネットワーク内のノードが、第２Ｐ２Ｐネットワークのノードでもある第１Ｐ２Ｐネットワークのノードを識別するのにサービス・ロケーション能力を使用することによって、第２Ｐ２Ｐネットワーク内のオブジェクトを検索することを可能にする。前述の説明が、単に、サービス・ロケーション能力を紹介するために提供されるサービス・ロケーション能力のある種の実施形態の全般的な説明であり、したがって、サービス・ロケーション能力の実施形態が、前述の説明によって限定されることが意図されていないことを了解されたい。
【００１４】
サービス・ロケーション能力は、主に、本明細書では特定のタイプのＰ２ＰネットワークすなわちＣｈｏｒｄネットワークの文脈で図示され、説明される。Ｃｈｏｒｄネットワークでは、Ｃｈｏｒｄネットワークのノードで維持される検索テーブルを、フィンガ・テーブル（ｆｉｎｇｅｒ  ｔａｂｌｅ）と称し、フィンガ・テーブルの各エントリを、それぞれフィンガと称する。サービス・ロケーション能力の原理を他のタイプのＰ２Ｐネットワークにも適用することができ、したがって、本明細書でのフィンガ・テーブルおよび関連するフィンガへの言及を、より一般的に、検索テーブルおよびノードを識別する関連するエントリへの言及と解釈できることを了解されたい。
【００１５】
図１に、例示的なＣｈｏｒｄネットワークの高水準ブロック図を示す。図１に示されているように、Ｃｈｏｒｄネットワーク１００は、論理的にリング構成に配置された複数のノード１１０を含む。ノード１１０は、それぞれ、ノード１１０の間で共有できるファイルを格納する。ノード１１０は、他のノード１１０から使用可能にされ得るサービスをホスティングすることもできる。ノード１１０は、Ｃｈｏｒｄネットワークに参加できるすべてのノードを含む。たとえば、ノード１１０は、コンピュータ、電話機、および類似物を含むことができる。ノード１１０は、それぞれ、サービス・ロケーション能力のさまざまな機能を提供するように構成される。
【００１６】
サービス・ロケーション能力を提供する際のＣｈｏｒｄネットワーク１００の動作は、図１の例示的なＣｈｏｒｄネットワーク１００に関連するＣｈｏｒｄネットワークの全体的な動作をまず考慮することによってよりよく理解することができる。
【００１７】
Ｃｈｏｒｄでは、Ｃｈｏｒｄネットワークのノードは、パケットベースのネットワーク（たとえば、ＩＰネットワークまたは任意の他の適切なネットワークなど）を介するネットワーク接続性を有し、Ｃｈｏｒｄは、基礎になるパケットベースのネットワークの上にオーバーレイ・ネットワークを形成する。Ｃｈｏｒｄネットワークのノードは、論理的に、ノードのノードＩＤの順で円に配置される。ノードのノードＩＤは、ハッシュ関数を使用して割り当てられる。
【００１８】
Ｃｈｏｒｄでは、Ｃｈｏｒｄネットワークに参加できるノードの個数が、Ｃｈｏｒｄネットワークのキー空間（アドレス空間）のサイズに基づく。一般に、キー空間は、Ｍビットであり、Ｍは、任意の適切な数とすることができる。たとえば、Ｃｈｏｒｄネットワークで使用される通常のキー空間は、１６０ビット実施態様を使用して提供され、キー空間のサイズは２１６０すなわち約１．４５＊１０４８と等しくなる。ｃｏｎｓｉｓｔｅｎｔハッシュ関数が、入力を１６０ビット値にマッピングする（すなわち、入力をキー空間にマッピングする）のに使用される。このハッシュ関数からの出力は、キー空間に一様にマッピングされる。Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ（ＳＨＡ−１）、Ｍｅｓｓａｇｅ−Ｄｉｇｅｓｔ  Ａｌｇｏｒｉｔｈｍ  ５（ＭＤ５）、および類似物など、任意の適切なハッシュ関数を使用できることを了解されたい。ハッシュ関数の出力は、キー空間にマッピングされる時に、Ｃｈｏｒｄネットワーク内のノードを論理的に配置するのに使用されるノードＩＤの組を提供する。
【００１９】
Ｃｈｏｒｄでは、アクティブ・ノード（Ｃｈｏｒｄネットワークに参加している既存ノード）およびインアクティブ・ノード（Ｃｈｏｒｄネットワークに参加できる潜在的ノード）が、ノードのノードＩＤの順で論理的に円に配置される。Ｃｈｏｒｄは、ラップ・アラウンドを伴う増加するノードＩＤ値の方向で、円内の順序を押し付ける。Ｃｈｏｒｄネットワークでは、Ｃｈｏｒｄネットワークのアクティブ・ノードの間の接続性は、円内のアクティブ・ノードのうちの隣接するノードの間の論理接続性である（インアクティブ・ノードは、Ｃｈｏｒｄネットワークに接続されず、したがって、単に、アクティブ・ノードとしてＣｈｏｒｄネットワークに参加することができる潜在的ノードである）。この形で、Ｃｈｏｒｄネットワーク内のターゲット・アクティブ・ノードの展望からは、時計回りの方向の円内の次のアクティブ・ノードが、ターゲット・アクティブ・ノードの後継物であり、反時計回りの方向の円上の次のアクティブ・ノードが、ターゲット・アクティブ・ノードの先行物である。
【００２０】
図１では、アクティブ・ノードおよびインアクティブ・ノードが、明瞭さのために表示されている。図１では、Ｃｈｏｒｄネットワークのキー空間は６ビット（または、ノードＩＤ０からノードＩＤ６３まで時計回りの形で連続した番号を付けられた６４個のノード）である。図１では、ノード０、２〜３、５〜７、９、１２〜１３、１６〜２４、２６、２９〜３０、３２、３４〜３５、３７、４１、４３、４５、４９、５１、５３〜５４、５６〜５８、および６２がアクティブであり、残りのノードはインアクティブである。図１では、Ｃｈｏｒｄネットワーク１００のアクティブ・ノードの間の論理接続性は、ノード０がノード２に接続され、ノード２がノード３に接続され、ノード３がノード５に接続され、以下同様に、ノード６２がノード０に接続されて、円を完了することを示す。Ｃｈｏｒｄは、ラップ・アラウンドを伴って時計回りの方向で増加する値を使用して円内の順序を押し付けるので、ノード２を、ノード０の後継物と称し、ノード６２を、ノード０の先行物と称し、ノード３を、ノード２の後継物と称し、ノード０を、ノード２の先行物と称し、以下同様である。
【００２１】
本明細書で説明するように、Ｃｈｏｒｄネットワークは、ファイル共有をサポートし、共有される各ファイルは、Ｃｈｏｒｄネットワークのアクティブ・ノードのうちの１つまたは複数に格納される。Ｃｈｏｒｄでは、ファイルのファイル名は、Ｃｈｏｒｄネットワークのノードを識別するのに使用されるものと同一のハッシュ関数を使用して、Ｃｈｏｒｄネットワークのノードを識別するのに使用されるものと同一のキー空間にハッシュ化される。ファイル名のハッシュ化からのハッシュ化された出力は、ファイルのファイル識別子である。したがって、たとえば１６０ビットのキー空間を有するＣｈｏｒｄネットワークについて、そのＣｈｏｒｄネットワークは、潜在的に１．４５＊１０４８個のファイルに対処することができる。Ｃｈｏｒｄでは、ファイルは、ファイルのファイルＩＤと一致するノードＩＤを有するノードがアクティブである場合にはそのノードに格納され、そのノードがアクティブでない場合には、ファイルは、ファイルＩＤより大きいノードＩＤを有する最初のアクティブ・ノードに格納される。
【００２２】
図１では、Ｃｈｏｒｄネットワーク１００は、合計６４個のファイルに対処することができ、これらのファイルは、次のように格納される。ノード０は、ファイル０および６３を格納し、ノード２は、ファイル１および２を格納し、ノード３は、ファイル３を格納し、ノード５は、ファイル４および５を格納し、ノード６は、ファイル６を格納し、ノード７は、ファイル７を格納し、ノード９は、ファイル８および９を格納し、ノード１２は、ファイル１０、１１、および１２を格納し、ノード１３は、ファイル１３を格納し、ノード１６は、ファイル１４、１５、および１６を格納し、ノード１７は、ファイル１７を格納し、ノード１８は、ファイル１８を格納し、ノード１９は、ファイル１９を格納し、ノード２０は、ファイル２０を格納し、ノード２１は、ファイル２１を格納し、ノード２２は、ファイル２２を格納し、ノード２３は、ファイル２３を格納し、ノード２４は、ファイル２４を格納し、ノード２６は、ファイル２５および２６を格納し、ノード２９は、ファイル２７、２８、および２９を格納し、ノード３０は、ファイル３０を格納し、ノード３２は、ファイル３１および３２を格納し、ノード３４は、ファイル３３および３４を格納し、ノード３５は、ファイル３５を格納し、ノード３７は、ファイル３６および３７を格納し、ノード４１は、ファイル３８、３９、４０、および４１を格納し、ノード４３は、ファイル４２および４３を格納し、ノード４５は、ファイル４４および４５を格納し、ノード４９は、ファイル４６、４７、４８、および４９を格納し、ノード５１は、ファイル５０および５１を格納し、ノード５３は、ファイル５２および５３を格納し、ノード５４は、ファイル５４を格納し、ノード５６は、ファイル５５および５６を格納し、ノード５７は、ファイル５７を格納し、ノード５８は、ファイル５８を格納し、ノード６２は、ファイル５９、６０、６１、および６２を格納する。
【００２３】
最も基本的な実施態様では、任意の所与のファイルの１つのコピーだけが、Ｃｈｏｒｄネットワーク内に格納されるが、異なる方法を使用して、Ｃｈｏｒｄネットワーク内に１つのファイルの複数のコピーを格納することができる（たとえば、ノード障害の場合の弾力性、負荷平衡化、および類似物のために）。
【００２４】
たとえば、一実施形態では、１つのファイルの複数の版を、合意された命名規約を使用してそのファイルの複数のコピーにわずかに異なるファイル名を割り当てることによって、Ｃｈｏｒｄネットワーク内に格納することができる。たとえば、あるファイルの名前が「ａｂｃ」である場合に、「−ｎ」などの拡張を、同一のファイルを表すファイル名に追加することができる。この例では、そのファイルの複数のコピーを、名前「ａｂｃ」、「ａｂｃ−１」、「ａｂｃ−２」などの下で格納することができる。この形で、「ａｂｃ」ファイルの複数のファイル名が同一ではないので、異なるファイル名のハッシュ化は、異なるハッシュ出力をもたらし、したがって異なるファイルＩＤをもたらし、これによって、ファイルの複数のコピーがＣｈｏｒｄネットワークの異なるノードに格納されることを引き起こす。
【００２５】
たとえば、一実施形態では、ファイル名を使用してファイルの複数のファイルＩＤを生成するのに複数の独立のハッシュ関数を使用することによって（単一のｃｏｎｓｉｓｔｅｎｔハッシュ関数が使用される上で説明した実施態様ではなく）、あるファイルの複数の版をＣｈｏｒｄネットワーク内に格納することができる。この実施形態では、Ｃｈｏｒｄネットワークにファイルをシード（ｓｅｅｄ）しようとするノードは、複数のハッシュ関数を使用してファイルの可能なファイルＩＤのそれぞれを決定し、それらのファイルＩＤを使用してＣｈｏｒｄネットワークにファイルの複数のコピーを挿入する。この実施形態では、Ｃｈｏｒｄネットワーク内でファイルを検索しようとするノードは、ファイルの可能なファイルＩＤのすべてを判定し（ハッシュ関数のそれぞれを使用してファイル名をハッシュ化することによって）、その後、順次または並列に、判定されたファイルＩＤを使用してファイルを検索することができる。
【００２６】
Ｃｈｏｒｄネットワーク内でファイルの複数の版を格納することに関して、１つのファイルの複数の版を、任意の他の適切な形でＣｈｏｒｄネットワーク内に格納できることを了解されたい。
【００２７】
本明細書で説明するように、Ｃｈｏｒｄは、ノードがファイルを共有することを可能にする。Ｃｈｏｒｄネットワークのノードがファイルを共有することを可能にするために、Ｃｈｏｒｄネットワークの各ノードは、所望のファイルを入手できるようにするために所望のファイルを検索でき、最終的に所望のファイルのロケーションを判定できる必要がある。
【００２８】
Ｃｈｏｒｄでは、各ノードが検索テーブルを維持する。Ｍビット・キー空間を有するＣｈｏｒｄネットワークについて、各ノードＮは、Ｍ個のエントリを有する検索テーブルを維持し、検索テーブルのエントリを、「フィンガ」と称する。ノードＮの検索テーブル内では、第ｉフィンガが、Ｎから少なくとも２ｉ−１離れた円上の最初のノードを指す。一般に、そうではないと示されない限り、用語「第ｉフィンガ」は、検索テーブルの第ｉエントリによって指されるノードを表す。たとえば、Ｃｈｏｒｄネットワーク１００では、ノード０の第３フィンガは、ノード５である。
【００２９】
ノードの検索テーブルは、集合的に、Ｃｈｏｒｄネットワーク内のオブジェクトのロケーション（１つまたは複数）をそれによって判定できる効率的なグローバル検索アルゴリズムを提供する。
【００３０】
図１では、キー空間が６ビットであり、したがって、各ノードは、その検索テーブル内に６つのフィンガを有する。図１では、ノード０の検索テーブルを、次の表１に示されているように表すことができる。
【００３１】
【表１】
0005567683.tif 000002
【００３２】
Ｃｈｏｒｄでは、ネットワークは動的である。新しいノードがＣｈｏｒｄネットワークに加わり、既存ノードがＣｈｏｒｄネットワークを離脱する時に、Ｃｈｏｒｄネットワークのアクティブ・ノードの検索テーブルが、影響を受ける可能性がある。したがって、Ｃｈｏｒｄでは、各アクティブ・ノードＫは、それに関連する検索テーブルを周期的に更新する。アクティブ・ノードＫは、任意の適切な形でその検索テーブルを更新することができる。たとえば、アクティブ・ノードＫは、ノード（Ｋ＋２ｉ−１）を検索することによってその検索テーブルを更新することができる。というのは、この検索を実行することからの結果が、検索テーブルの第ｉフィンガの値になるからである。Ｃｈｏｒｄネットワークのアクティブ・ノードが、任意の他の適切な形でその検索テーブルを更新できることを了解されたい。
【００３３】
Ｃｈｏｒｄでは、検索テーブルに加えて、各ノードが、リング内のその後継物および先行物のアイデンティティをも格納する。この情報は、新しいノードがネットワークに加わる時および既存ノードがネットワークを離脱する時ならびにノードが障害から回復する時など、リング保守のために使用される。いくつかのＣｈｏｒｄネットワークでは、複数同時ノード障害がある状況に対して保護するために、ノードが、リング内のそのＮ個の後継物およびＮ個の先行物のアイデンティティを格納することができる。
【００３４】
Ｃｈｏｒｄでは、Ｃｈｏｒｄネットワークのノードは、Ｃｈｏｒｄネットワークの他のノードからファイルを検索し、入手することができる。Ｃｈｏｒｄネットワークは、ノードがＣｈｏｒｄネットワーク内の他のノードから入手可能なファイルをそれによって検索できる検索アルゴリズムをサポートする。Ｃｈｏｒｄ検索アルゴリズムの動作を、図１のＣｈｏｒｄネットワーク１００を使用する例を介して示すことができる。この例では、ノード２が、図１のＣｈｏｒｄネットワーク１００内でファイル０を検索することを望むと仮定する。ノード２は、ファイル要求をそこに送信すべき他のノードのうちの１つを選択するために、その検索テーブルにアクセスする。ノード２の展望から、ターゲット・ファイル（すなわち、ファイル０）のファイルＩＤは、ラップ・アラウンドに起因してノード２の最大フィンガ（すなわち、ノード３４）の値より大きいので、ノード２は、ノード３４がファイル０を検索することを要求するファイル要求をノード３４に送信する。ノード３４は、ノード２からファイル要求を受信する。ノード３４は、ファイル０を格納していないので、そのファイル要求を転送すべき他のノードのうちの１つを選択するために、その検索テーブルにアクセスする。ノード３４では、検索テーブルは、ノード３５、３７、４０、４３、５１、および２を指す６つのフィンガを含む。ファイル０のオブジェクトＩＤは、第５フィンガと第６フィンガとの間にある（それぞれノード５１およびノード２）ので、ノード３４は、第５フィンガによって識別されるノード（ノード５１）に検索要求を転送する。ノード５１は、ノード３４からファイル要求を受信する。ノード５１は、ファイル０を格納していないので、そのファイル要求を送信すべき他のノードのうちの１つを選択するために、その検索テーブルにアクセスする。ノード５１では、検索テーブルは、ノード５３、５３、５６、６２、３、および１９を指す６つのフィンガを含む。ファイル０のオブジェクトＩＤは、第４フィンガと第５フィンガとの間にある（それぞれノード６２およびノード３）ので、ノード５１は、第４フィンガによって識別されるノード（ノード６２）に検索要求を転送する。ノード６２は、ノード５１からファイル要求を受信する。ノード６２は、ファイル０を格納していないので、そのファイル要求を送信すべき他のノードのうちの１つを選択するために、その検索テーブルにアクセスする。ノード６２では、検索テーブルは、ノード０、０、２、６、１６、および３０を指す６つのフィンガを含む。ファイル０のオブジェクトＩＤは、第１フィンガと第２フィンガの両方に示されている（ノード０）ので、ノード６２は、ノード０がアクティブであることを知り、検索要求をノード０に転送する。ノード０は、検索要求の受信に応答して、直接にまたは中間ノード（すなわち、ノード６２、ノード５１、ノード３４、およびその後にノード０）を介してのいずれかで、それがファイル０を有することをノード２に応答する。その後、ノード２は、ノード０から直接にファイル０を入手することができる。したがって、この例から、Ｃｈｏｒｄで、Ｃｈｏｒｄ検索アルゴリズムをサポートするために協力するＣｈｏｒｄネットワーク内のノードのすべてが明らかである。
【００３５】
Ｃｈｏｒｄでは、ノードがいつでもＣｈｏｒｄネットワークに参加でき、Ｃｈｏｒｄネットワークを離脱することができるので、Ｃｈｏｒｄネットワークは動的である。ノードがＣｈｏｒｄネットワークに参加し、離脱する時に、ファイルが、ノードの間で転送される。たとえば、参加するノードは、少なくとも、参加するノードのノードＩＤと同一のファイルＩＤを有するファイル（および潜在的に他のファイルも）を格納する責任を引き受けることができ、離脱するノードは、１つまたは複数のファイルを格納する責任を別のノードに転送することができる。Ｃｈｏｒｄネットワークへの参加および離脱に関連する手順を、下でさらに詳細に説明する。
【００３６】
Ｃｈｏｒｄ参加手順では、ノードがＣｈｏｒｄネットワークに参加することを望む時に、参加するノードは、そのノードＩＤを決定する。参加するノードは、その名前をキー値にハッシュ化することによってそのノードＩＤを決定する。たとえば、ノードの名前がｎｏｄｅ−ｘｙｘ＠ｃｏｍｐａｎｙ−ａｂｃ．ｃｏｍである場合には、ノードＩＤは、ＳＨＡ−１（ｎｏｄｅ−ｘｙｘ＠ｃｏｍｐａｎｙ−ａｂｃ．ｃｏｍ）の出力になり、ここで、単純さのために、我々はハッシュ関数がＳＨＡ−１であると仮定している（任意の適切なハッシング関数を使用することができるが）。この例では、ハッシング演算から決定されるこのノードのノードＩＤがＫであるものとする。
【００３７】
Ｃｈｏｒｄ参加手順では、参加するノードＫは、その後、Ｃｈｏｒｄネットワークのアクティブ・ノード（初期化ノードと表される）に連絡する。一見したところでは、この初期化ノードは集中化サーバであるように見える可能性があるが、そうではない。というのは、（ａ）初期化ノードを、Ｃｈｏｒｄネットワーク内の現在アクティブであるどのノードにもすることができ（たとえば、ノードＫ１およびＫ２が同時にＣｈｏｒｄネットワークに参加することを望む場合に、Ｋ１およびＫ２は、ネットワークに参加するためのそれぞれの初期化ノードとして異なるアクティブ・ノードを使用することができ、そうする可能性が高い）、（ｂ）初期化ノードは、基本的な能力に加えて特殊な能力を提供する必要が全くない（すなわち、初期化ノードは、Ｃｈｏｒｄネットワーク内の任意の他のノードと全く同様に振る舞うことができる）からである。ノードＫは、任意の適切な形で潜在的な候補初期化ノードのリストを入手することができる（たとえば、参加するノードＫ上の１つまたは複数の以前の検索テーブル、後継物リストおよび／またはプロセッサ・リストから、参加するノードＫ内で管理的に構成される情報から、ウェブサイトからなど）。この例では、初期化ノードのノードＩＤがＬであるものとする。
【００３８】
Ｃｈｏｒｄ参加手順では、参加するノードＫは、その後、初期化ノードＬが参加するノードＫを検索する（すなわち、ＩＤ＝Ｋを有するオブジェクトを検索する）ことの要求を送信する。この時点で、次の２つのイベントが発生する可能性がある。
（Ａ）ノードＬが、参加するノードにＮの値を用いて応答する。ノードＮは、すべてのアクティブ・ノードの中で、参加するノードＫに関連するＫより少し大きいノードＩＤを有するノードである。したがって、参加するノードＫがＣｈｏｒｄネットワークに参加する場合に、ノードＮは、参加するノードＫの後継ノードでなければならない。その後、ノードＫは、ノードＮに連絡し、ノードＮの先行ノードのアイデンティティをノードＮに要求する。この例では、ノードＮの先行物をノードＮ−と表すものとする。ノードＮは、Ｎ−の値を参加するノードＫに提供する。この情報に基づいて、ノードＫは、それ自体をＣｈｏｒｄネットワーク内でノードＮとノードＮ−との間に挿入しなければならないことを知る。
（Ｂ）ノードＬが、参加するノードにＫの値を用いて応答する。これは、Ｃｈｏｒｄネットワーク内で既にアクティブである、ＫのノードＩＤを有する別のノードがあることを意味する。このケースは、ほとんどのＣｈｏｒｄネットワークで極端に可能性が低い（たとえば、１６０ビット・キー空間であるＣｈｏｒｄネットワーク１００では、この状況が発生する可能性は、１．４５＊１０４８分の１である）が、可能である。この状況には、参加するノードＫにそれ自体の名前をわずかに変更させ（たとえば、タイムスタンプを追加する、数を追加する、および類似物）、その新しいノード名を使用して異なるノードＩＤ（Ｋ’と表す）を生成させることによって対処することができる。参加するノードＫ’は、初期化ノードＬに新しい検索要求（すなわち、初期化ノードＬが参加するノードＫ’を検索することの要求）を送信することによって、このプロセスをもう一度開始することができる。
【００３９】
Ｃｈｏｒｄ参加手順では、参加するノードＫの挿入点の判定の後に、Ｃｈｏｒｄネットワーク内に参加するノードを挿入する処理が実行される。参加するノードＫは、ノードＫ−（Ｋの候補先行物）とノードＫ＋（Ｋの候補後継物）との間に挿入されようとしており、この時に、ノードＫがネットワークに参加する前に、ノードＫ＋はノードＫ−の後継物である。参加するノードＫは、後継ノードＫ＋に連絡し、参加するノードＫがＣｈｏｒｄネットワークに参加したいことを示す。その後、後継ノードＫ＋は、（１）その先行物がノードＫ−であることを参加するノードＫに知らせ、（２）ノードＫが責任を持たなければならないすべてのファイル（すなわち、（Ｋ−）＋１からＫまでのファイルＩＤを有するファイルを参加するノードＫに転送し始め、（３）参加するノードＫがＣｈｏｒｄネットワークに参加するプロセスに入っていることをその先行ノードＫ−に知らせる。ファイル転送が完了した後に、参加するノードＫは、先行ノードＫ−との接続を確立する。参加するノードＫと先行ノードＫ−との間の接続が確立された後に、参加するノードＫは、それがＣｈｏｒｄネットワークに成功して参加したことを後継ノードＫ＋に知らせる。その後、後継ノードＫ＋は、先行ノードＫ−との接続を破壊し、後継ノードＫ＋と先行ノードＫ−との両方が、その先行物リストおよび後継物リストを更新する。
【００４０】
Ｃｈｏｒｄ離脱手順では、離脱するノードＫが制御された形でＣｈｏｒｄネットワークを離脱することを可能にする処理が実行される。離脱しようとしているノードＫは、それに関連する先行ノード（ノードＫ−と表される）および後継ノード（ノードＫ＋と表される）を有する。離脱するノードＫは、先行ノードＫ−と後継ノードＫ＋との両方に連絡し、離脱するノードＫがＣｈｏｒｄネットワークを離脱するつもりであることを両方に知らせ、両方のノードに他方のノードのアイデンティティを提供する。その後、離脱するノードＫは、離脱するノードＫが現在Ｃｈｏｒｄネットワークの代わりに格納しているファイルのすべて（すなわち、（Ｋ−）＋１とＫとの間の、Ｋを含むファイルＩＤを有するすべてのファイル）を後継ノードＫ＋に転送する。ファイルの転送が完了した後に、参加するノードは、先行ノードＫ−および後継ノードＫ＋から切断することによってＣｈｏｒｄネットワークを離脱する。その後、ノードＫ−およびＫ＋は、その間の接続を確立する（この接続は、それらのいずれかによって開始することができる）。ノードＫ−およびＫ＋は、その先行物リストおよび後継物リストも更新する。
【００４１】
Ｃｈｏｒｄネットワークに対する動的変更を可能にするＣｈｏｒｄ参加手順およびＣｈｏｒｄ離脱手順の使用に加えて、Ｃｈｏｒｄは、ノード障害からの回復を可能にするＣｈｏｒｄ回復手順をもサポートする（すなわち、Ｃｈｏｒｄ参加手順およびＣｈｏｒｄ離脱手順は、ノード障害からの回復に使用されない）。Ｃｈｏｒｄネットワークのノードは、それぞれその先行ノードおよび後継ノードに周期的にハートビート・メッセージを送信し、これによって、Ｃｈｏｒｄネットワークのノードがノード障害をすばやく検出することを可能にする。一般に、あるノードからのハートビート・メッセージは、ハートビート・メッセージがそこから発するノードの先行ノードおよび後継ノードのアイデンティティを含む。この形で、あるノードがその後継ノードからハートビート・メッセージを受信する時に、そのノードは、その後継ノードの後継ノードのアイデンティティを知り、したがって、ノードの後継物が障害を発生する時に、そのノードは、その後継ノードの後継ノードへの接続を開始でき、Ｃｈｏｒｄリングが維持される。上で注記したように、いくつかのＣｈｏｒｄネットワークでは、ノードは、ｋ個の先行物およびｋ個の後継物のリストを維持する。この場合に、Ｃｈｏｒｄネットワークは、ｋ−１個の連続するノードの障害から回復することができる。この場合に、ｋの小さい値についても、ｋ個の連続するノードの障害の可能性は、非常に小さい。いくつかのそのようなＣｈｏｒｄネットワークでは、ｋの値を２＊ｌｏｇ２（Ｌ）として決定することができ、Ｌは、ネットワーク内のアクティブ・ノードの平均個数である（すなわち、通常１０００００個のアクティブ・ノードを有するＣｈｏｒｄ、ｋは約３４になる）。
【００４２】
上で説明したＣｈｏｒｄ回復手順は、ノード障害の場合にＣｈｏｒｄネットワークを修復することを可能にするが、障害を発生したノードで格納されるファイルは、失われる。この問題には、複数の形で対処することができ、そのうちの少なくとも２つが、上で説明されている。さらに、別の実施形態では、ファイルを入手するノードが自発的にそのファイルのシード・ノードになることを可能にすることによって、この問題に対処する。１つのそのような実施形態の説明が、これに続く。ファイルは、最初に、ＣｈｏｒｄネットワークのメンバによってＣｈｏｒｄネットワークに導入される（このメンバ・ノードを、そのファイルのシード・ノードと称する）。シード・ノードは、ファイル名のハッシュ化された値（すなわち、ファイルＩＤ）を入手し、ファイルＩＤと同一のノードＩＤを有するノードを検索する。シード・ノードは、ファイルＩＤ以上のノードＩＤを有するＣｈｏｒｄネットワーク内の最初のアクティブ・ノードを突き止める。シード・ノードは、突き止められたノードにそのファイルを送信する。その後、後刻にそのファイルを入手するＣｈｏｒｄネットワークの他のノードは、自発的にそのファイルのシード・ノードになることができる。あるファイルのシード・ノードは、Ｃｈｏｒｄネットワーク内でそのファイルを周期的に検索し、シード・ノードがそのファイルを突き止めることに失敗する場合には、シード・ノードは、上で説明したようにそのファイルを適当なノードに送信する。この形で、「失われた」ファイルが、Ｃｈｏｒｄネットワーク内で回復される。
【００４３】
本明細書で説明するように、ファイルの格納および共有に加えて、Ｃｈｏｒｄネットワークは、サービスをサポートすることもできる。既存のＣｈｏｒｄネットワークは、ファイル共有サービスだけをサポートするが、Ｃｈｏｒｄネットワークは、最終的に、ファイル共有サービスに加えて１つまたは複数の他のサービスをサポートすることができる。サービスを、すべてのノードまたはノードの部分集合から使用可能にすることができ、ノードの小さい部分集合から使用可能であるのみとすることができる。サービスは、ノードのすべてまたは一部について必須とすることができ、あるいは、自発的な基礎でノードによってサポートされ得る。あるサービスをサポートするノード（１つまたは複数）は、アクティブとインアクティブとの間で遷移することができる。Ｃｈｏｒｄネットワーク内でサービスをサポートすることに関連するこれらの特徴のそれぞれが、サポートされるサービスのタイプ、Ｃｈｏｒｄネットワークの実施態様、同様の要因のうちの１つまたは複数に基づいて変化する可能性があることを了解されたい。Ｃｈｏｒｄネットワーク内でのサービスのサポートの可能性に鑑みて、サービス・ロケーション能力は、Ｃｈｏｒｄネットワーク内のノードのそれぞれが特定のサービスを提供するノードを検索し、突き止めることを可能にする。
【００４４】
サービス・ロケーション能力は、少なくとも次の理由から、特定のサービスをサポートするノードを突き止めるのに使用される時に有利である。（１）サービス・ロケーション能力は、Ｃｈｏｒｄネットワークのノード上で維持される既存の検索テーブルを使用する（すなわち、ノード上の新しい検索テーブルは不要である）、（２）検索は分散される（たとえば、サービスを検索する時に、サービス検索を開始する開始ノードは、多くともＭ個のメッセージを開始し、Ｍは、Ｃｈｏｒｄネットワークのキー空間の長さであり、したがって、開始ノードは、多くともＭ個の応答メッセージを受信し、その結果、開始ノードに圧倒的な個数の応答が押し寄せることがなくなる）、かつ（３）サービス検索を、整然とした形でステージで実行することができ、各ステージを、Ｃｈｏｒｄネットワーク内で交換されるメッセージの個数を最小にするように高い成功の確率を有するように構成することができる。サービス・ロケーション能力は、効率的なブロードキャスト（多くのアプリケーションで有用である）を可能にするという利益をも有する。
【００４５】
Ｃｈｏｒｄネットワーク内で突き止めることができるサービスは、Ｃｈｏｒｄネットワークによってサポートされるのに適するすべてのサービスを含む。
【００４６】
Ｃｈｏｒｄネットワークのノードによってサポートできる第１のサービスは、ノードが複数のリンクされたＣｈｏｒｄネットワークにまたがってファイルを検索できる「クロスリング検索」サービスである。一般に、Ｃｈｏｒｄネットワークは、コミュニティから関心を持たれているファイルが格納され、共有される、関心のコミュニティを表す。１つのノードが、複数のＣｈｏｒｄネットワークに属することができる。これは、Ｃｈｏｒｄネットワークに参加できるノードに関連する個々のユーザが、異なる関心を有する可能性が高く、少なくともいくつかのノードが、Ｃｈｏｒｄネットワークの複数の組に属する可能性が高いことの理解から明白である。あるノードが、Ｃｈｏｒｄネットワーク内でファイルを検索する時に、検索するノードは、（ａ）ファイルがネットワーク内に一度も格納されたことがない（たとえば、ファイルが新たに作成され、Ｃｈｏｒｄネットワークのノードのどれもが、まだそのファイルを獲得してない）、（ｂ）ファイルがコミュニティから関心を持たれていない可能性があり、したがってそのＣｈｏｒｄネットワークに格納されていない、（ｃ）Ｃｈｏｒｄネットワーク内の各ノードが、Ｃｈｏｒｄネットワークの代わりに格納できるファイルの数に対する実際上の制限を有するという事実に起因して（たとえば、まれな場合に、ノードとその先行物との間のギャップが大きすぎ、したがって、ノードがファイルのすべてを格納できない、たとえば、Ｃｈｏｒｄネットワークのポリシが、通常は、より古いおよび／またはより人気の低いファイルを格納できず、したがってＣｈｏｒｄネットワーク内で入手可能でないことを指定する）、（ｄ）ノードの障害が、いくつかのファイルをＣｈｏｒｄネットワーク内で入手不能にする可能性がある、および（５）ファイルをＣｈｏｒｄネットワーク内で入手不能にする可能性がある任意の他の理由など、任意の個数の理由から、Ｃｈｏｒｄネットワーク内でファイルを突き止めることに失敗する可能性がある。ファイルを検索しているＣｈｏｒｄネットワークのノードが、複数のＣｈｏｒｄネットワークに属する場合に、そのノードは、それが属するＣｈｏｒｄネットワークのそれぞれでそのファイルを検索することができる。あるＣｈｏｒｄネットワークのノードが、そのノードが属するＣｈｏｒｄネットワーク（１つまたは複数）内でそのファイルを突き止めることができない場合に、そのノードは、１つまたは複数の他のＣｈｏｒｄネットワーク内でそのファイルを検索することを望む可能性がある。この場合に、そのノードは、１つまたは複数の他のＣｈｏｒｄネットワーク（すなわち、既に検索されたＣｈｏｒｄネットワーク（１つまたは複数）以外の）に接続された、Ｃｈｏｒｄネットワーク内の他のノードを突き止めることを望む可能性がある。１つまたは複数の追加のＣｈｏｒｄネットワークへのファイルの検索のこの拡張は、他のＣｈｏｒｄネットワークに属するＣｈｏｒｄネットワークのノードが複数のＣｈｏｒｄネットワークにまたがるファイルの検索での使用のために突き止められる、クロスリング検索サービスを使用して実行される。
【００４７】
Ｃｈｏｒｄネットワークのノードによってサポートできる第２のサービスは、「翻訳」サービスである。翻訳サービスは、言語の間で文書を翻訳するためのものとすることができる。たとえば、Ｃｈｏｒｄネットワークのあるノードが、文書を英語からドイツ語に翻訳することを望む場合があり、Ｃｈｏｒｄネットワーク内のいくつかのノードが、この能力を有する場合がある。同様に、Ｃｈｏｒｄネットワークのあるノードが、文書をイタリア語からフランス語に翻訳することを望む場合があり、Ｃｈｏｒｄネットワーク内のいくつかのノードが、この能力を有する場合がある。このタイプのサービスについて、ノードは、単に翻訳サービスをサポートするノードではなく、より具体的に、検索するノードによって要求される特定の翻訳サービス（すなわち、ある言語から別の言語への翻訳）をサポートするノードを突き止めることを試みることができる。
【００４８】
上で説明した例示的なサービスは、ファイル共有に加えて、Ｃｈｏｒｄネットワークによってサポートできる多数の異なるサービスがあることを示す。したがって、Ｃｈｏｒｄネットワーク内で提供できるサービスの特定の例が、サービス・ロケーション能力を説明する際の明瞭さのために本明細書で説明されるが、サービス・ロケーション能力が、特定のサービスと共に使用されることに限定されないことを了解されたい。
【００４９】
サービス・ロケーション能力は、Ｃｈｏｒｄネットワーク上のノードが特定のサービスをサポートしまたは提供するＣｈｏｒｄネットワーク上の１つまたは複数の他のノードをそれによって突き止めることができるアルゴリズムを提供する。
【００５０】
本明細書で説明されるように、既存のＣｈｏｒｄネットワークは、Ｃｈｏｒｄネットワーク上のノードがＣｈｏｒｄネットワーク上の他のノードを検索しまたはＣｈｏｒｄネットワーク内に格納されたファイルを検索することを可能にする。図示され本明細書で説明されるサービス・ロケーション能力は、Ｃｈｏｒｄネットワークが、Ｃｈｏｒｄネットワーク内での新しいタイプの検索すなわち、Ｃｈｏｒｄネットワーク上のノードがＣｈｏｒｄネットワーク上の特定のサービスのロケーションをそれによって検索できるサービス・ロケーション検索をサポートする（すなわち、サービス検索要求内に固有の特定のサービスをサポートするＣｈｏｒｄネットワーク上の１つまたは複数の他のノードを検索する）ことを可能にする。
【００５１】
サービス・ロケーション能力の説明を単純にするために、用語「検索」は、以下の段落では、そうではないと特に示されまたは説明されない限り、サービス・ロケーション検索を指すが、サービス・ロケーション能力が、Ｃｈｏｒｄネットワークのノード上の既存の検索テーブルを利用するので、以下の段落で使用される用語「検索テーブル」は、それでも、Ｃｈｏｒｄネットワークのノードで維持されるＣｈｏｒｄ「フィンガ」テーブルを指す。
【００５２】
サービス・ロケーション能力を、例を使用して説明し、その後、Ｃｈｏｒｄネットワーク内でサービス・ロケーション能力を提供することに参加するＣｈｏｒｄネットワークの異なるノードで実行される処理を示す方法図を使用してより一般的な言葉で提示する。
【００５３】
図１に示し、上で説明したように、Ｃｈｏｒｄネットワーク１００は、６ビット・キー空間を有し（すなわち、６４個のアドレスをサポートし）、６４個のノードのうちの３６個がアクティブである（すなわち、ノード０、２、３、５、６、７、９、１２、１３、１６、１７、１８、１９、２０、２１、２２、２３、２４、２６、２９、３０、３２、３４、３５、３７、４１、４３、４５、４９、５１、５３、５４、５６、５７、５８、６２）。図１にさらに示されているように、アクティブ・ノードの部分集合（すなわち、ノード７、１９、３０、および５１）は、サービスをサポートし、このサービスは、サービスＡと表される（実例として、サービスＡをサポートするアクティブ・ノードのそれぞれは、サービスＡをサポートしないアクティブ・ノードに使用されるものより暗い陰影を使用して示されている）。
【００５４】
一例として、図１を参照し、ノード０が、サービスＡをサポートする、Ｃｈｏｒｄネットワーク１００のノードのうちの１つを突き止めることを望むと仮定する。この例の説明を単純にするために、我々は、検索を初期化するノードがノード０であると仮定する（同一の議論を、検索を初期化するノードがノードＮである場合に行うことができるので、一般性の喪失がないことを了解されたい。というのは、Ｃｈｏｒｄネットワーク内のノードのすべてのノードＩＤからＮの値を単純に減算することによって、同一のプロセスを実行できるからである）。上で表１（下に繰り返す）で示したように、ノード０の検索テーブルは、次の情報を含む６つのエントリを有する。
【００５５】
【表２】
0005567683.tif 000003
【００５６】
この例では、ノード０は、Ｃｈｏｒｄネットワーク１００内でサービスＡを突き止めるための検索を開始する。ノード０で維持されるこの検索テーブルに基づいて、ノード０は、それぞれ検索テーブルのＭ個のフィンガによって識別されるＭ個のノードにＭ個の検索要求メッセージを送信することによって、サービスＡを突き止める検索を開始する。第ｉフィンガへの検索要求メッセージは、（１）突き止められるサービスの指示および（２）検索範囲すなわち第ｉフィンガが検索しなければならないノードの範囲という情報を含む。
【００５７】
突き止められるサービスの指示を、サービスを指定する任意の適切な判断基準を使用して指定することができる（たとえば、サービス識別子、サービスを記述するのに指定できる１つまたは複数のパラメータ、および類似物、ならびにそのさまざまな組合せ）。
【００５８】
第ｉフィンガが検索しなければならないノードの範囲を識別する検索範囲を、任意の適切な形で指定することができる。検索範囲を記述する際の明瞭さのために、表記［ｍ，ｎ）を使用して、ｍを含むがｎを除外する、ｍからｎまでの範囲を表すものとする。
【００５９】
一実施形態では、第ｉフィンガについて、検索範囲は、［第ｉフィンガ，第ｉ＋１フィンガ）になる。この例では、ノード０は、ノード２、ノード５、ノード９、ノード１６、およびノード３２に検索メッセージを送信し、検索メッセージは、それぞれ［２，５）、［５，９）、［９，１６）、［１６，３２）、および［３２，０）の検索範囲を含む。
【００６０】
もう１つの実施形態では、第ｉフィンガについて、検索範囲を、［第ｉフィンガ，第ｉ＋１フィンガ）から［第ｉフィンガ，２ｉ）にさらに縮小することができる。この例では、ノード５の第３フィンガについて、検索範囲が［５，９）ではなく［５，８）になる。というのは、第（ｉ＋１）フィンガが、２ｉ以上の最初のノードであるからである（すなわち、２ｉと第ｉ＋１フィンガとの間にはアクティブ・ノードがない）。この実施形態は、縮小された範囲を提供するが、この縮小された範囲は、ノード０がその検索テーブルを更新し終える前に［２ｉ，第ｉ＋１フィンガ］の範囲内の新しいノードがネットワークに参加した可能性があるまれなケースを考慮に入れない。この潜在的な問題は、ノード０の第３フィンガを考慮することによって理解することができ、この第３フィンガは、ノード０がその検索テーブルを更新する前にノード８がＣｈｏｒｄネットワーク１００に参加するイベントを表す。
【００６１】
これらの検索範囲実施形態の説明から、両方の実施形態が実際に働くことは明白であるが、［第ｉフィンガ，第ｉ＋１フィンガ）検索範囲に基づく実施形態は、［第ｉフィンガ，２ｉ）検索範囲に基づく実施形態より頑健である。
【００６２】
上で説明したように、ノード０は、それぞれノード２、５、９、１６、および３２にサービス検索要求メッセージを送信することによって、Ｃｈｏｒｄネットワーク１００内でサービスＡを突き止める検索を開始する。それぞれノード２、５、９、１６、および３２によって受信されるサービス検索要求メッセージは、サービス・ロケーション検索を継続するために処理される。
【００６３】
ノード０からサービス検索要求を受信する時に、ノード２、５、９、１６、および３２のそれぞれは、まず、要求されたサービスがローカルにサポートされるかどうかを判定する。ノード０からサービス検索要求メッセージを受信するノード２、５、９、１６、および３２のいずれかが、サービスがローカルにサポートされると判定する場合には、そのノードは、それがそのサービスをサポートすることを示すサービス検索応答メッセージを用いてノード０に応答する。サービスがローカルにサポートされないと判定する、ノード０からサービス検索要求メッセージを受信するノード２、５、９、１６、および３２のそれぞれについて、そのノードは、ノード０によって要求されたサービスを突き止めるために１つまたは複数の他のノードへの１つまたは複数の検索メッセージを開始すべきか否かを判定するために処理を開始する。サービス検索要求メッセージを受信するノードは（そのサービスがローカルにサポートされない場合に）、受信されたサービス検索要求メッセージ内で指定された検索範囲に含まれる、そのローカル検索テーブル内の１つまたは複数のフィンガ（ある場合に）へのサービス検索要求メッセージを開始する。
【００６４】
この例では、ノード０からサービス検索要求メッセージを受信するノード２、５、９、１６、および３２のどれもが、サービスＡをサポートしないので、ノード２、５、９、１６、および３２のそれぞれは、ノード０によって要求されたサービスＡを突き止めるために１つまたは複数の他のノードへの１つまたは複数の検索メッセージを開始すべきか否かを判定する。
【００６５】
ノード０からサービス検索要求メッセージを受信するノードで実行される処理は、ノード０からサービス検索要求メッセージを受信するノードの１つ（すなわち、ノード２、５、９、１６、および３２のうちの１つ）によって実行される処理を考慮することによって、よりよく理解することができる。
【００６６】
この例では、ノード０からサービス検索要求メッセージを受信した時にノード１６で実行される処理を考慮されたい。ノード１６は、［１６，３２）の範囲を有する検索要求をノード０から受信する。上で示したように、ノード１６は、まず、それが要求されたサービスをサポートするか否かを判定する。この例では、ノード１６は、サービスＡをサポートしない。その後、ノード１６は、Ｃｈｏｒｄネットワーク１００の別のノード（１つまたは複数）へのサービス検索要求メッセージ（１つまたは複数）を開始すべきか否かを判定する。ノード１６は、ノード０から受信されたサービス検索要求メッセージに含まれる検索範囲［１６，３２）を使用し、そのローカル検索テーブルを使用して、Ｃｈｏｒｄネットワーク１００の別のノード（１つまたは複数）へのサービス検索要求メッセージ（１つまたは複数）を開始すべきか否かを判定する。ノード１６の検索テーブルを、次の表２に示す。
【００６７】
【表３】
0005567683.tif 000004
【００６８】
この例では、ノード０から受信されたサービス検索要求メッセージに含まれる［１６，３２）という検索範囲および上で指定された検索テーブルに基づいて、ノード１６は、ノード１７、１８、２０、および２４へのサービス検索要求メッセージを生成する。ノード１６によって開始されるサービス検索要求メッセージは、ノード０によって開始されたものに似て、（１）突き止められるサービスの指示および（２）検索範囲すなわち第ｉフィンガが検索しなければならないノードの範囲を含む。この例では、ノード１７、１８、２０、および２４に向けて開始されるサービス検索要求メッセージは、それぞれ、サービスＡを指定し、さらに、それぞれ検索範囲［１７，１８）、［１８，２０）、［２０，２４）、および［２４，３２）を含む。ノード１６は、ノード３２（第５フィンガ）およびノード４８（第６フィンガ）へのサービス検索要求メッセージを開始しない。というのは、これらのノードが、ノード０から受信されたサービス検索要求メッセージで指定された検索範囲の外にあるからである。
【００６９】
図２に、図１の例示的なＣｈｏｒｄネットワーク１００のノード０によって開始されたサービス・ロケーション検索に応答して図１の例示的なＣｈｏｒｄネットワーク１００内で開始されるサービス検索要求メッセージを示す。
【００７０】
図２に示されているように、サービス検索要求メッセージは、次のようにＣｈｏｒｄネットワーク１００内で送信される。ノード０は、ノード２、５、９、１６、および３２にメッセージを送信し、ノード２は、ノード３にメッセージを送信し、ノード５は、ノード６および７にメッセージを送信し、ノード９は、ノード１２および１３にメッセージを送信し、ノード１６は、ノード１７、１８、２０、および２４にメッセージを送信し、ノード１８は、ノード１９にメッセージを送信し、ノード２０は、ノード２１および２２にメッセージを送信し、ノード２２は、ノード２３にメッセージを送信し、ノード２４は、ノード２６および２９にメッセージを送信し、ノード２９は、ノード３０にメッセージを送信し、ノード３２は、ノード３４、３７、４１および４９にメッセージを送信し、ノード３２は、ノード３３にメッセージを送信し、ノード４０は、ノード４２および４５にメッセージを送信し、ノード４９は、ノード５１、５３、および５６にメッセージを送信し、ノード５３は、ノード５４にメッセージを送信し、ノード５６は、ノード５７、５８、および６２にメッセージを送信する。
【００７１】
この形で、ノード０によって開始されるサービスＡに関するサービス・ロケーション要求は、Ｃｈｏｒｄネットワーク１００の各ノードが、それが要求されたサービスをサポートするか否かに関する指示を用いて応答できる（したがって、ノード０がサービスＡをサポートするすべてのノードのアイデンティティを知ることができる）ように、Ｃｈｏｒｄネットワーク１００全体に伝搬される。
【００７２】
上で説明したように、サービスを突き止めるためにＣｈｏｒｄネットワーク内で開始された各サービス検索要求メッセージは、対応するサービス検索応答メッセージの開始をもたらす。サービス検索応答メッセージは、サービス・ロケーション検索を発するノードに向かって戻って伝搬する。この形で、サービス・ロケーション検索を発するノードは、要求されたサービスをサポートするＣｈｏｒｄネットワーク内のノード（１つまたは複数）について知らされる。
【００７３】
サービス検索応答メッセージの伝搬に関して、肯定の応答メッセージおよび否定の応答メッセージの伝搬は、異なって処理される。
【００７４】
アップストリーム・ノードからサービス検索要求メッセージを受信する所与のダウンストリーム・ノードでは、肯定の応答メッセージは、所与のダウンストリーム・ノードからアップストリーム・ノードに向かって即座に伝搬される。たとえば、これは、所与のダウンストリーム・ノードによる、それが要求されたサービスをローカルにサポートするとの判定に応答したもの、または、所与のダウンストリーム・ノードがそのダウンストリーム・ノードのさらにダウンストリームのノード（すなわち、所与のダウンストリーム・ノードがそれに対してサービス検索要求メッセージを開始するダウンストリーム・ノード）から肯定の応答メッセージを受信することに応答したものである可能性がある。
【００７５】
アップストリーム・ノードからサービス検索要求メッセージを受信する所与のダウンストリーム・ノードでは、否定の応答メッセージは、所与のダウンストリーム・ノードがそれに対してサービス検索要求メッセージ（１つまたは複数）を開始する各ダウンストリーム・ノード（１つまたは複数）からの応答メッセージを待った後に限って、所与のダウンストリーム・ノードからアップストリーム・ノードに向かって伝搬される。この形で、所与のダウンストリーム・ノードは、そのダウンストリーム・ノード（１つまたは複数）からの応答を、アップストリーム・ノードに送信される単一の応答メッセージに合併することができる。
【００７６】
サービス検索応答メッセージの伝搬は、図１および図２の例示的なＣｈｏｒｄネットワーク１００を考慮することによってよりよく理解することができる。
【００７７】
この例では、ノード１９が、ノード１８からサービス検索要求メッセージを受信する時に、ノード１９は、ノード１８に即座に応答し、それがサービスＡをサポートすることを示し、ノード１８は、この応答をノード１６に即座に中継し、ノード１６は、その応答を即座に中継してノード０に戻す。
【００７８】
この例では、ノード９が、ノード０からサービス検索要求メッセージを受信する時に、ノード９自体はサービスＡをサポートしないので、ノード９は、それぞれノード１２および１３に２つのサービス検索要求メッセージを送信する。ここで、ノード９が、ノード１３から否定の応答を受信する前にノード１２から否定の応答を受信すると仮定すると、ノード９は、ノード１３からの応答を待っている間に、ノード１２からの否定の応答を格納する。その後、ノード１３から否定の応答を受信する時に、ノード９は、ノード１２および１３からの２つの否定の応答を単一の否定の応答に合併し、その単一の否定の応答をノード０に送信する。
【００７９】
図示され、本明細書で説明されるサービス・ロケーション能力では、メッセージ（および、より具体的には応答メッセージ）への言及が、一般に、アプリケーション・レベル・メッセージへの言及である。この区別の必要は、ノードＮがノードＪにメッセージを送信する時に、ノードＪが、通常、ノードＪがメッセージを受信したことをノードＮに示すためにノードＮに肯定応答を用いて応答することを考慮することによって理解される。ノードＮが、ある時間の後に肯定応答を受信しない場合には、ノードＮは、メッセージを再送信する（たとえば、再試行のある回数まで）。図示され、本明細書で説明されるサービス・ロケーション能力では、この肯定応答プロセスが、バックグラウンド・プロセスになると仮定され、サービス・ロケーション能力の説明を単純にするために、本明細書では無視される。言い替えると、本明細書で言及されるサービス検索応答メッセージは、Ｃｈｏｒｄネットワーク内で動作していてもいなくてもよいこのバックグラウンド・プロセスの肯定応答ではない。
【００８０】
サービス・ロケーション能力の実施形態のよりよい理解を提供するために、サービス・ロケーション能力を提供する際に、発するノードおよび中間ノードによって実行される処理を、図示し、図３〜５に関して説明する。
【００８１】
図３に、発するノードでサービス検索要求メッセージを生成する方法の一実施形態を示す。
【００８２】
ステップ３０２では、方法３００が始まる。
【００８３】
ステップ３０４では、発するノードが、サービス・ロケーション要求を検出する。サービス・ロケーション要求は、Ｐ２Ｐネットワーク内でサービスのロケーション（１つまたは複数）を識別する（たとえば、サービスをサポートするＰ２Ｐネットワーク内の１つまたは複数のノードを識別する）ための、Ｐ２Ｐネットワーク内でサービスを検索する要求である。
【００８４】
サービス・ロケーション要求は、発するノードで必要なまたは望まれるサービスを識別する。サービス・ロケーション要求を、任意の適切な形で検出することができ、この形は、サービス・ロケーション要求が発するノードで開始される形に依存するものとすることができる。サービス・ロケーション要求を、手動で（たとえば、発するノードのユーザによって）または自動的に（たとえば、トリガ条件の検出に応答して発するノードによって）開始することができる。
【００８５】
ステップ３０６では、発するノードが、サービスのサービス・ロケーション検索を開始する。サービス・ロケーション検索は、Ｐ２Ｐネットワーク内でサービスのロケーション（１つまたは複数）を識別するためにＰ２Ｐネットワーク内でサービスを検索するプロセスである。
【００８６】
サービス・ロケーション検索を、発するノード上で維持される検索テーブルを使用して開始することができる。サービス・ロケーション検索を、発するノード上で維持される検索テーブルの１つまたは複数のノードへのサービス検索要求を開始することによって開始することができる。発するノードは、検索テーブルのノードのうちの１つまたは複数に向かって１つまたは複数のサービス検索要求メッセージを伝搬させることによって、サービス検索要求を開始することができる。
【００８７】
発するノードによって生成され、伝搬されるサービス検索要求メッセージは、発するノードが要求されたサービスをサポートするＰ２Ｐネットワークの少なくとも１つのノードを突き止めることを可能にする際の使用に適合された情報を含む。
【００８８】
サービス検索要求メッセージは、サービス検索要求メッセージを受信するノードによる、サービス検索要求メッセージに応答するための使用のための、発するノードのノードＩＤを含む。
【００８９】
サービス検索要求メッセージは、同一のサービス・ロケーション検索の要求メッセージおよび応答メッセージを突き合わせるための、発するノードおよびサービス検索要求メッセージを受信するノードによる使用のための、サービス検索要求メッセージのメッセージＩＤを含む。
【００９０】
サービス検索要求メッセージは、要求されたサービスを識別する際の使用のために適合されたサービス識別情報を含む。たとえば、サービス識別情報は、サービスを識別するサービスＩＤ、サービス記述情報（たとえば、サービスを識別する際の使用のために適合され、かつ／またはサービスを記述する、１つまたは複数のパラメータ、属性、および／または判断基準）、および類似物のうちの１つまたは複数を含むことができる。
【００９１】
サービス検索要求メッセージは、サービス検索要求メッセージがそれに対して開始されたノードによる使用のための、発するノードによって指定された検索範囲を含む。検索範囲は、［Ｋ１，Ｋ２）として表され、Ｋ２は、検索範囲の最大値であり、Ｋ１は、検索範囲の最小値である。サービス検索要求メッセージの検索範囲は、発するノードによって開始されたサービス・ロケーション検索のタイプ（たとえば、フル・ネットワーク検索、ステージド（ｓｔａｇｅｄ）ネットワーク検索、漸進的ネットワーク検索、および類似物）に依存するものとすることができる。
【００９２】
サービス検索要求メッセージ内に含まれる情報を、異なるものとすることができる（たとえば、より少ない情報を含めることができ、より多くの情報を含めることができ、異なる情報を含めることができるなど）ことを了解されたい。
【００９３】
発するノードがサービス・ロケーション検索を開始する形（すなわち、発するノードによって開始されるサービス検索要求メッセージの個数およびこれらのサービス検索要求メッセージのタイミング）は、実行されるサービス・ロケーション検索のタイプ（たとえば、フル・ネットワーク検索、ステージド・ネットワーク検索、漸進的ネットワーク検索、および類似物）に依存する。
【００９４】
フル・ネットワーク検索が発するノードによって開始される一実施形態では、サービス検索要求メッセージは、発するノードからフィンガ・テーブル内のフィンガのそれぞれに向かって並列に伝搬される。
【００９５】
ステージド・ネットワーク検索が発するノードによって開始される一実施形態では、サービス検索要求メッセージは、発するノードからフィンガ・テーブル内の１つまたは複数のフィンガに向かって直列に伝搬される。ステージド・ネットワーク検索の使用は、図示され本明細書で説明される他の図に関連して図６および図７を参照することによってよりよく理解することができる。
【００９６】
漸進的ネットワーク検索が発するノードによって開始される一実施形態では、サービス検索要求メッセージは、発するノードから、初期検索としてフィンガ・テーブル内のフィンガの部分集合に向かって並列に、およびオプションで１つまたは複数の後続検索としてフィンガ・テーブル内の１つまたは複数の後続フィンガに向かって直列に伝搬される。漸進的ネットワーク検索の使用は、図示され本明細書で説明される他の図に関連して図８および図９を参照することによってよりよく理解することができる。
【００９７】
ステップ３０８では、方法３００が終了する。
【００９８】
終了するものとして図示し、説明したが、発するノードによるサービス・ロケーション検索の開始の後に、発するノードは、１つまたは複数のサービス検索要求メッセージが発するノードを開始したことに応答して発するノードによって受信された１つまたは複数のサービス検査応答メッセージを処理するために処理を開始することによって、サービス・ロケーション検索をサポートする処理を実行し続けることができる。
【００９９】
本明細書では主に直列に実行されるものとして図示され、説明されるが、方法３００のステップの少なくとも一部を、同時にまたは図３に関して図示され説明されたものとは異なる順序で実行することができる。本明細書では主に中間ノードでサービス検索要求メッセージ生成を実行するプロセス論理の特定の実施態様に関して図示され、説明されるが、中間ノードでサービス検索要求メッセージ生成を実行するプロセス論理を、本明細書で図示され説明されるサービス・ロケーション能力をサポートしながらさまざまな他の形で実施できることを了解されたい。
【０１００】
図４に、中間ノードでサービス検索要求メッセージを処理する方法の一実施形態を示す。
【０１０１】
ステップ４０２では、方法４００が始まる。
【０１０２】
ステップ４０４では、中間ノード（ノードＪと表される）が、アップストリーム・ノード（ノードＮと表される）からサービス検索要求メッセージを受信し、ノードＮは、サービス・ロケーション検索のイニシエータまたはアップストリーム中間ノードとすることができる。
【０１０３】
サービス検索要求メッセージは、要求されたサービスを検索するのに適切な任意の情報を含む。
【０１０４】
サービス検索要求メッセージは、サービス検索要求メッセージのオリジネータ（すなわち、アップストリーム・ノードＮ）のノードＩＤを含む。
【０１０５】
サービス検索要求メッセージは、サービス検索要求メッセージのメッセージＩＤを含む。
【０１０６】
サービス検索要求メッセージは、要求されたサービスを識別する際の使用のために適合されたサービス識別情報を含む。たとえば、サービス識別情報は、サービスを識別するサービスＩＤ、サービス記述情報（たとえば、サービスを記述し、かつ／またはサービスを識別する際の使用のために適合された、１つまたは複数のパラメータ、属性、および／または判断基準）、および類似物のうちの１つまたは複数を含むことができる。
【０１０７】
サービス検索要求メッセージは、中間ノードＪのためにアップストリーム・ノードＮによって指定された検索範囲を含む。検索範囲は、［Ｋ１，Ｋ２）として表され、Ｋ２は、検索範囲の最大値であり、Ｋ１は、検索範囲の最小値である。
【０１０８】
異なる情報をサービス検索要求メッセージ内に含めることができることを了解されたい。
【０１０９】
ステップ４０６では、中間ノードＪが要求されたサービスをサポートするかどうかに関する判定を行う。この判定は、任意の適切な形で実行することができる（たとえば、サービス識別情報の少なくとも一部を中間ノードＪで入手可能な情報と比較することによって）。
【０１１０】
中間ノードＪが要求されたサービスをサポートする場合には、方法４００は、ステップ４０８に進む（この時点で、中間ノードＪは、アップストリーム・ノードＮへの肯定のサービス検索応答メッセージを開始する）。
【０１１１】
中間ノードＪが要求されたサービスをサポートしない場合には、方法４００は、ステップ４１０に進む（この時点で、中間ノードＪは、サービス検索要求メッセージの検索範囲内のネットワークの他のノードにサービス・ロケーション検索を拡張すべきかどうかを判定する追加処理を開始する）。
【０１１２】
ステップ４０８では、中間ノードＪが、肯定のサービス検索応答メッセージをアップストリーム・ノードＮに送信する。サービス検索応答メッセージは、要求されたサービスが中間ノードＪによってサポートされることを発するノードに知らせ、発するノードが中間ノードＪにサービスを要求することを可能にする際の使用に適切な任意の情報を含むことができる。たとえば、サービス検索応答メッセージは、中間ノードＪの識別子、このメッセージがアップストリーム・ノードＮからのサービス検索要求メッセージに対する応答であることの指示（たとえば、サービス検索要求メッセージのメッセージＩＤ）、中間ノードＪが要求されたサービスをサポートすることの指示、中間ノードＪにサービスを要求する際の発するノードによる使用のための中間ノードＪのネットワーク連絡情報（たとえば、ＩＰアドレス、ポート番号、および類似物）、および類似物を含むことができる。サービス検索応答メッセージが異なる情報を含むことができることを了解されたい。ステップ４０８から、方法４００はステップ４３４に進み、ここで、方法４００は終了する。
【０１１３】
ステップ４１０では、中間ノードＪが、その検索テーブルの最初のフィンガを識別する。
【０１１４】
図４に示されているように、ステップ４１０に関連してまたは任意の他の適切な時に、中間ノードＪは、サービス・ロケーション検索をネットワークの他のノードに拡張すべきかどうかを判定するための追加処理を実行する際に使用するための初期化機能を実行することができる。たとえば、中間ノードｊは、１と等しくなるようにフィンガ・カウンタ（ｉ）を初期化し、中間ノードｊの最初のフィンガと等しくなるように第１フィンガ変数（Ｆ１）をセットし（すなわち、Ｆ１＝最初のフィンガ）、ＮＵＬＬと等しくなるように第２フィンガ変数（Ｆ２）をセットし、ＮＵＬＬと等しくなるように検索リストをセットする（検索リストは、アップストリーム・ノードＮから受信されたサービス検索要求メッセージの代わりに中間ノードＪがサービス検索要求メッセージを送信したノードのリストであり、中間ノードＪによって開始されたすべてのサービス検索要求メッセージに対する応答を管理するのに使用することができる）などを行うことができる。より少数、より多数、および／または異なる変数、リスト、および／または同様のパラメータを、任意の他の適切な形で利用し、かつ／または初期化できることを了解されたい。
【０１１５】
ステップ４１２では、検索範囲の最大値（Ｋ２）が中間ノードＪの最初のフィンガ（Ｆ１）より大きいかどうかに関する判定を行う。中間ノードＪは、その最初のフィンガが検索範囲の外であるかどうかをチェックしている。Ｋ２がＦ１より大きくはない場合には、方法４００はステップ４１４に進む。Ｋ２がＦ１より大きい場合には、方法４００はステップ４１６に進む。
【０１１６】
ステップ４１４では、中間ノードＪが、否定のサービス検索応答メッセージをアップストリーム・ノードＮに送信する。この場合には、サービス検索要求メッセージは、中間ノードＪによって生成されない。サービス検索応答メッセージは、サービスＡをサポートする［Ｆ１，Ｆ２）の範囲内のノードがないことをアップストリーム・ノードＮに知らせる際の使用に適切な任意の情報を含むことができる。ステップ４１２から、方法４００はステップ４３４に進み、ここで、方法４００は終了する。
【０１１７】
ステップ４１６では、中間ノードＪが、その検索テーブルの第（ｉ＋１）フィンガを識別する。方法４００を通る第１パスでは、これは、中間ノードＪの検索テーブルの第２フィンガである。
【０１１８】
ステップ４１８では、検索範囲の最大値（Ｋ２）が、中間ノードＪの第（ｉ＋１）フィンガ（Ｆ２）より大きいかどうかに関する判定を行う。中間ノードＪは、その第（ｉ＋１）フィンガが検索範囲の外にあるかどうかをチェックしている。
【０１１９】
Ｋ２がＦ２より大きい場合には、方法４００はステップ４２８に進む（すなわち、メッセージの検索範囲が、［Ｆ１，Ｋ２）に縮小され、中間ノードＪによって生成される結果のサービス検索要求メッセージは、アップストリーム・ノードＮから受信されたサービス検索要求メッセージに応答して中間ノードＪによって生成される最後のサービス検索要求メッセージである）。
【０１２０】
Ｋ２がＦ２より大きくはない場合には、方法４００はステップ４２０に進む（すなわち、中間ノードＪによって生成される結果のサービス検索要求メッセージは、アップストリーム・ノードＮから受信されたサービス検索要求メッセージに応答して中間ノードＪによって生成される最後のサービス検索要求メッセージである）。
【０１２１】
ステップ４２０では、中間ノードＪが、［Ｆ１，Ｆ２）の検索範囲を有するサービス検索要求メッセージをノードＦ１に送信する。この時点で、Ｆ１とＦ２との両方がＫ２未満であり、したがって、検索範囲［Ｆ１，Ｆ２）は、検索範囲［Ｋ１，Ｋ２）内にある。このサービス検索要求メッセージは、本明細書で説明するように、サービス検索要求メッセージに通常含まれる情報を含む。
【０１２２】
ステップ４２２では、中間ノードＪが、中間ノードＪによって開始された任意のサービス検索要求メッセージに対する応答を管理するための中間ノードＪによる使用のために、検索リストにノードＦ１を追加する。
【０１２３】
ステップ４２４では、中間ノードＪが、第２フィンガ変数（Ｆ２）と等しくなるように第１フィンガ変数（Ｆ１）を更新し、フィンガ・カウンタを増分する（ｉ＝ｉ＋１）。
【０１２４】
ステップ４２６では、フィンガ・カウンタｉがＭ以上であるかどうかに関する判定を行う（２Ｍはキー空間のサイズであり、Ｍは中間ノードＪ上のフィンガ・テーブルのサイズである）。
【０１２５】
フィンガ・カウンタｉがＭ以上ではない場合には、方法４００はステップ４１６に戻る。
【０１２６】
フィンガ・カウンタｉがＭ以上である場合には、方法４００はステップ４２８に進む（すなわち、Ｆ１は最後のフィンガであり、中間ノードＪによって生成される結果のサービス検索要求メッセージは、アップストリーム・ノードＮから受信されたサービス検索要求メッセージに応答して中間ノードＪによって生成される最後のサービス検索要求メッセージである）。
【０１２７】
ステップ４２８では、中間ノードＪが、［Ｆ１，Ｋ２）の検索範囲を有するサービス検索要求メッセージをノードＦ１に送信する。このサービス検索要求メッセージは、本明細書で説明するように、サービス検索要求メッセージに通常含まれる情報を含む。
【０１２８】
ステップ４３０では、中間ノードＪが、中間ノードＪによって開始された任意のサービス検索要求メッセージに対する応答を管理するための中間ノードＪによる使用のために、検索リストにノードＦ１を追加する。
【０１２９】
ステップ４３２では、中間ノードＪが、時間を開始し、中間ノードＪによって開始された１つまたは複数のサービス検索要求メッセージに応答して中間ノードＪによって受信される１つまたは複数のサービス検索応答メッセージを待つ。
【０１３０】
ステップ４３４では、方法４００が終了する。
【０１３１】
終了するものとして図示し、説明したが、方法４００の実行が、中間ノードＪによる１つまたは複数のサービス検索要求メッセージの開始をもたらす場合に、中間ノードＪは、中間ノードＪによって開始された１つまたは複数のサービス検索要求メッセージに応答して中間ノードＪによって受信される１つまたは複数のサービス検索応答メッセージを処理するための処理を開始することによって（たとえば、図５に関して図示され説明される方法５００を実行することによって）、発するノードによって開始されたサービス・ロケーション要求をサポートする処理を実行し続けることができる。
【０１３２】
本明細書では主に直列に実行されるものとして図示され、説明されるが、方法４００のステップの少なくとも一部を、同時にまたは図３に関して図示され説明されたものとは異なる順序で実行することができる。本明細書では主に中間ノードでサービス検索要求メッセージ生成を実行するプロセス論理の特定の実施態様に関して図示され、説明されるが、中間ノードでサービス検索要求メッセージ生成を実行するプロセス論理を、図示され本明細書で説明されるサービス・ロケーション能力をサポートしながらさまざまな他の形で実施できることを了解されたい。
【０１３３】
図５に、中間ノード（ノードＪと表される）でサービス検索応答メッセージを処理する方法の一実施形態を示す。中間ノードＪは、中間ノードＪが１つまたは複数のダウンストリーム・ノードに１つまたは複数の追加サービス検索要求メッセージを送信することをトリガしたサービス検索要求メッセージを中間ノードＪがそこから受信したアップストリーム・ノードにサービス検索応答メッセージを提供するためにサービス検索応答メッセージを処理する方法を実行する。
【０１３４】
ステップ５０２で、方法５００が始まる。
【０１３５】
ステップ５０４では、中間ノードＪが、１つまたは複数のサービス検索応答メッセージを待つ。サービス検索応答メッセージ（１つまたは複数）は、中間ノードＪによって開始された（たとえば、図示され、図４に関して説明された方法４００を実行することによって）１つまたは複数のサービス検索要求メッセージに応答して、中間ノードＪによって期待される。
【０１３６】
ステップ５０６では、中間ノードＪが、サービス検索応答メッセージがダウンストリーム・ノードから受信されるかどうかを判定する。
【０１３７】
サービス検索応答メッセージがダウンストリーム・ノードから受信される場合には、方法５００はステップ５１０に進む（この時点で、サービス検索応答メッセージの処理が始まる）。
【０１３８】
サービス検索応答メッセージがダウンストリーム・ノードから受信されない場合には、方法５００はステップ５０８に進む。
【０１３９】
ステップ５０８では、タイマが満了したかどうかに関する判定を行う。このタイマを、任意の適切な形で（たとえば、方法５００の実行の初期化ステップとして、方法４００の実行の一部として、または任意の他の適切な形で）中間ノードＪによってセットすることができる。このタイマには、任意の適切な長さの時間をセットすることができる。
【０１４０】
タイマが満了していない場合には、方法５００は、ステップ５０４に戻り、ステップ５０４からステップ５０６に（すなわち、その間に中間ノードＪが１つまたは複数のダウンストリーム・ノードからの１つまたは複数のサービス検索応答メッセージを待っている待機状態に）進む。
【０１４１】
タイマが満了している場合には、方法５００はステップ５２２に進む（その点で、中間ノードＪは、割り当てられた時間の長さの間にダウンストリーム・ノードからすべての未解決のサービス検索応答メッセージを受信したのではないので、アップストリーム・ノードへの否定のサービス検索応答メッセージを開始する）。
【０１４２】
ステップ５０４、５０６、および５０８に関して、この機能を他の形で実施できることを了解されたい。たとえば、サービス検索応答メッセージが受信されたかどうかを判定する明示的ステップ（ステップ５０６）およびタイマが満了したかどうかを判定する明示的ステップ（ステップ５０８）が方法５００内で実行されることではなく、はるかに少ないことが特定のシーケンスで方法５００内で実行され、方法５００は、サービス検索応答メッセージが受信されることを検出するまで（その点で方法５００はステップ５１０に進む）またはタイマが満了したことを検出するまで（その点で方法５００はステップ５２２に進む）待機状態（すなわち、ステップ５０４）に留まることができる。たとえば、方法５００内の明示的ステップとしてタイマを監視するのではなく、タイマの監視をバックグラウンド・プロセスとして実行することができ、処理が実行される方法５００内の点に関わりなく、時間が満了したことの中間ノードＪによる検出が、方法５００にステップ５２２に進ませる（たとえば、直接にまたは優雅に（ｇｒａｃｅｆｕｌｌｙ））ことができるようになる。この機能を他の形で実施できることを了解されたい。
【０１４３】
ステップ５１０では、受信されたサービス検索応答メッセージが正当であるかどうかに関する判定を行う。受信されたサービス検索応答メッセージの正当性は、任意の適切な形で判定することができる。たとえば、一実施形態では、受信されたサービス検索応答メッセージの正当性は、サービス検索応答メッセージが中間ノードＪからのサービス検索要求メッセージに応答して提供されつつあることを検証するために、受信されたサービス検索応答メッセージ内に含まれる要求ＩＤをチェックすることによって判定される。
【０１４４】
サービス検索応答メッセージが正当ではない場合には、方法５００はステップ５１２に進む。
【０１４５】
サービス検索応答メッセージが正当である場合には、方法５００はステップ５１４に進む。
【０１４６】
ステップ５１２では、中間ノードＪが、受信されたサービス検索応答メッセージを無視する。ステップ５１２から、方法５００はステップ５０４に戻る（すなわち、中間ノードＪは、１つまたは複数のサービス検索応答メッセージを待ち続ける）。
【０１４７】
ステップ５１４では、受信されたサービス検索応答メッセージが肯定（すなわち、要求されたサービスをサポートするノードが突き止められた）または否定（すなわち、要求されたサービスをサポートするノードが突き止められなかった）のどちらであるのかに関する判定を行う。
【０１４８】
受信された検索応答メッセージが肯定である場合には、方法５００はステップ５１６に進む。
【０１４９】
受信された検索応答メッセージが否定である場合には、方法５００はステップ５１８に進む。
【０１５０】
ステップ５１６では、中間ノードＪが、肯定のサービス検索応答メッセージをアップストリーム・ノードに送信する。
【０１５１】
サービス検索応答メッセージは、要求されたサービスをサポートするものとして識別されたノードの指示をアップストリーム・ノードに提供する際の使用に適切な任意の情報を含むことができる。たとえば、サービス検索応答メッセージは、中間ノードＪの識別子、このメッセージがアップストリーム・ノードからのサービス検索要求メッセージに対する応答であることの指示（たとえば、サービス検索要求メッセージのメッセージＩＤ）、要求されたサービスをサポートするノードの指示、要求されたサービスをサポートするノードにサービスを要求する際の発するノードによる使用のための要求されたサービスをサポートするノードのネットワーク連絡情報（たとえば、ＩＰアドレス、ポート番号、および類似物）、および類似物を含むことができる。サービス検索応答メッセージが異なる情報を含むことができることを了解されたい。ステップ５１６から、方法５００はステップ５２４に進み、ここで方法５００は終了する。
【０１５２】
ステップ５１８では、中間ノードＪが、検索リストからソース・ノードを除去する。ソース・ノードは、中間ノードＪによって受信されたサービス検索応答メッセージのソースである。検索リストは、中間ノードＪがそこからサービス検索応答メッセージを期待している１つまたは複数のノードのリストであり、方法４００に関して説明したように、中間ノードＪによって開始された任意のサービス検索要求メッセージに対する応答を管理するために中間ノードＪによって使用される）。
【０１５３】
ステップ５２０では、検索リストがＮＵＬＬであるかどうかに関する判定を行う。これは、中間ノードＪによって受信されると期待されるサービス検索応答メッセージのすべてが実際に受信された（関連するサービス検索応答メッセージを中間ノードＪからアップストリーム・ノードに送信できるように）かどうかに関する判定である。
【０１５４】
検索リストがＮＵＬＬである（すなわち、すべての期待されるサービス検索応答メッセージが受信された）場合には、方法５００はステップ５２２に進む。
【０１５５】
検索リストがＮＵＬＬではない（すなわち、すべての期待されるサービス検索応答メッセージが受信されたのではない）場合には、方法５００はステップ５０４に戻り、ステップ５０４からステップ５０６に（すなわち、その間に中間ノードＪが１つまたは複数のダウンストリーム・ノードからの１つまたは複数のサービス検索応答メッセージを待っている待機状態に）進む。
【０１５６】
ステップ５２２では、中間ノードＪが、否定のサービス検索応答メッセージをアップストリーム・ノードに送信する。
【０１５７】
サービス検索応答メッセージは、中間ノードＪが要求されたサービスをサポートせず、アップストリーム・ノードの代わりに中間ノードＪによって連絡されたダウンストリーム・ノードのどれもが要求されたサービスをサポートしないことの指示をアップストリーム・ノードに提供する際の使用に適切な任意の情報を含むことができる。ステップ５２２から、方法５００はステップ５２４に進み、ここで方法５００は終了する。
【０１５８】
ステップ５２４では、方法５００が終了する。
【０１５９】
本明細書では主に直列に実行されるものとして図示され、説明されるが、方法５００のステップの少なくとも一部を、同時にまたは図示され図５に関して説明されたものとは異なる順序で実行することができる。本明細書では主に中間ノードでサービス検索応答メッセージ処理を実行するプロセス論理の特定の実施態様に関して図示され、説明されるが、中間ノードでサービス検索応答メッセージ処理を実行するプロセス論理を、図示され本明細書で説明されるサービス・ロケーション能力をサポートしながらさまざまな他の形で実施できることを了解されたい。
【０１６０】
本明細書で示されるように、図５は、主に、中間ノードで実行されるサービス検索応答メッセージ処理に対処する。しかし、図５を、発するノードすなわちサービスに関するサービス・ロケーション要求を開始するノードで実行されるサービス検索応答メッセージ処理を指定するように適合させることもできる。発するノードについて、方法５００は、ステップ５１６および５２２を除去することによって適合される。ステップ５１６およびステップ５２２に関して、これらのステップは、発するノードがサービス・ロケーション要求のソースである（すなわち、発するノードが応答を送信する必要がない）ので、発するノードについては不要である。ステップ５１６の除去に関して、ステップ５１４から、方法５００は、ステップ５２４に進むことができ（たとえば、発するノードが要求されたサービスをサポートするノードのうちの１つを識別した後に、発するノードは、要求するサービスをサポートする他のノードがあるかどうかを気にしない）、あるいは、追加のサービス検索応答メッセージがまだ未解決である場合に、そのサービス検索応答メッセージについて監視し続けることができる（たとえば、発するノードが、要求されたサービスをサポートするネットワークの全ノードのリストを望む可能性がある場合）。ステップ５２２の除去に関して、ステップ５０８（タイマが満了した場合）およびステップ５２０（検索リストがＮＵＬＬである場合）から、方法５００は、ステップ５２４に進む。
【０１６１】
上で説明されたサービス・ロケーション検索では、（１）Ｃｈｏｒｄネットワークのキー空間がＭビットである場合に、サービス・ロケーション検索のソースは、多くともＭ個のサービス検索要求メッセージを送出し、多くともＭ個のサービス検索応答メッセージを受信し、中間ノードは、より少ない要求メッセージを送出し、より少ない応答メッセージを受信し、Ｃｈｏｒｄネットワークのノードのどれもが、メッセージで過負荷にならないようになっており、（２）アップストリーム・ノードからダウンストリーム・ノードに送信されるサービス検索要求メッセージは、１つまたは複数の追加のサービス検索要求メッセージをダウンストリーム・ノードで生成させる場合があり、サービスのサービス・ロケーション検索が、多くともＭ−１個のステップまたはステージまでの、１つまたは複数のステップまたはステージに分散され得る検索のシーケンスを生成する可能性がある。これから、上で説明されたサービス・ロケーション検索で、サービス・ロケーション要求の時にＣｈｏｒｄネットワーク内にＫ個のアクティブ・ノードがある場合に、サービス・ロケーション検索プロセスが最終的にＣｈｏｒｄネットワークの各ノード（サービス・ロケーション要求のソースを除く）に１つのサービス検索要求メッセージを配送するので、サービス・ロケーション要求は、Ｃｈｏｒｄネットワーク内でＫ−１個のメッセージを生成することを理解することができる。これらのメッセージは、ノードのどれもがメッセージによって過負荷にならないようにするためにのすべてのノードを介して分配されるが、一般に、Ｋは大きい数であり、したがって、サービスを突き止めるためにＣｈｏｒｄネットワーク内で生成されるメッセージの個数を減らすことが望ましい。
【０１６２】
一実施形態で、サービスを突き止めるためにＣｈｏｒｄネットワーク内で生成されるメッセージの個数は、円のすべての部分に対して並列にサービスの検索を開始するのではなく、サービスの検索が円の諸部分で複数ステージで直列に開始される漸進的検索を実行することによって減らすことができる。このタイプのサービス・ロケーション検索を、本明細書では、漸進的サービス・ロケーション検索と称する。
【０１６３】
漸進的サービス・ロケーション検索は、まず、サービスを突き止めるためにＣｈｏｒｄネットワーク内で生成されるメッセージの個数を減らす１つの方法が、初期検索で円全体ではなく円の一部だけを検索することであることを考慮することによって、よりよく理解することができる。この場合に、円全体が検索されるのではないので、この検索は、要求されたサービスを提供するノードを突き止めない場合がある。この場合に、円の一部の検索が成功する確率を、サービスを突き止めるために開始されるメッセージの個数に対して（すなわち、円内の検索範囲のサイズに対して）バランスをとることができる。この場合に、検索範囲のサイズを、次のように決定することができる。
【０１６４】
低い検索失敗率を保証するために検索範囲のサイズを決定できる形は、例を考慮することによってよりよく理解することができる。この例では、キー空間が２Ｍであるものとし、平均して、通常はネットワーク内にサービスを提供する２Ｋ個のアクティブ・ノードがあると仮定する。これらの仮定に基づいて、特定のノードＩＤのためにサービスを提供するアクティブ・ノードがある確率は、α＝２Ｋ／２Ｍ＝２−（Ｍ−Ｋ）である。この例では、さらに、ノード０が、［１，Ｌ）の初期検索範囲内でサービスＡを検索していると仮定する。範囲［１，Ｌ）のすべてのノードがサービスＡを提供しない確率は、（１−α）Ｌ−１である。この例では、所望の検索失敗率が、たとえば２％未満であるものとし（任意の所望の検索失敗率を使用することができるが）、これは、式（１−α）Ｌ−１＜１／５０をもたらす。この式を使用し、この式の両辺の対数（底ｅ）をとると、（Ｌ−１）＊ｌｎ（１−α）＜−ｌｎ（５０）になり、ここで、ｌｎ（１−α）＝−α−α２／２−α３／３−α４／４などである。一般に、αは非常に小さい数であり、したがって、高次の項は、非常に小さく、無視することができる。したがって、上の式は、−（Ｌ−１）＊α＜−ｌｎ（５０）もしくはＬ＞（３．９１）＊１／α＋１、またはより単純にＬ＞（３．９１）＊１／α（１を無視する）として近似することができる。
【０１６５】
低い検索失敗率を保証するために検索範囲のサイズを決定できる形を、より例示的な例を考慮することによってよりよく理解することもできる。この例では、１６０ビットのキー空間を有するＣｈｏｒｄネットワークを考慮されたい。平均して、ネットワーク内に１０００００個のアクティブ・ノードがあり、通常、アクティブ・ノードの中に、サービスＡを提供している２１０（すなわち１０２４）個のノード（すなわち、アクティブ・ノードの約１％）があると仮定する。この場合には、α＝２−１５０であり、Ｌは、（３．９１）＊２１５０より大きくなるように選択される。Ｌ＝４＊２１５０＝２１５２であるものとする。このＬの選択を用いると、初期検索は、円の２１５２／２１６０＝１／２８＝１／２５６の部分をカバーする。したがって、この例では、初期検索は、９８％の成功の可能性を有するが、サービスを突き止めるためにネットワーク内で交換されるメッセージの個数は、２５６倍だけ減らされる（すなわち、平均して、初期サービス範囲内のノードの個数は、約４００個であり、したがって、初期検索は、そうではなく初期検索がＣｈｏｒｄネットワーク全体にわたる場合に生成されるはずの１０００００個の検索メッセージではなく、約４００個の検索メッセージだけを生成する）。
【０１６６】
上で説明したように、初期検索がサービスをサポートするノードを突き止めるのに失敗する、ごくわずかな可能性があるだけである可能性が高い。初期検索がサービスをサポートするノードを突き止めるのに失敗する場合には、サービス・ロケーション検索のソースは、円の第２部分への第２の検索を開始することができる（たとえば、上の例では、ノード０は、範囲［Ｌ，２Ｌ）を用いる第２のサービス・ロケーション検索を開始するはずである。第２の検索がサービスをサポートするノードを突き止めるのに失敗する場合には、サービス・ロケーション検索のソースは、円の第３部分への第３の検索を開始することができる（たとえば、上の例では、ノード０は、範囲［２Ｌ，３Ｌ）を用いる第３のサービス・ロケーション検索を開始するはずである。したがって、ソース・ノードは、サービスをサポートするノードが突き止められるか、円全体がサービスをサポートするノードを突き止めずに検索され終えるまで、Ｃｈｏｒｄネットワークの円の複数の部分のそれぞれを検索し続けることができ、これによって、サービスをサポートするノードを突き止めるためにＣｈｏｒｄネットワーク内で交換されるメッセージの個数を大幅に減らすことができる漸進的サービス・ロケーション検索が提供される。
【０１６７】
上で説明した漸進的サービス・ロケーション検索実施形態では、検索弧（したがって、検索範囲）の端点は、Ｌ、２Ｌ、３Ｌ、４Ｌなどである。これを、図６に示す。
【０１６８】
図６に、例示的なＣｈｏｒｄネットワーク内でサービスの漸進的サービス・ロケーション検索を実行する例を示す、例示的なＣｈｏｒｄネットワークを示す。Ｃｈｏｒｄネットワーク６００では、キー空間は６ビット（すなわち、６４個のＩＤ）であり、漸進的サービス・ロケーション検索の各ステージの検索範囲のサイズは、８ノードである。
【０１６９】
上で説明された漸進的サービス・ロケーション検索実施形態では、検索弧の端点は、Ｌ、２Ｌ、３Ｌ、４Ｌなどであり、これは、サービス・ロケーション要求を開始するソース・ノードで維持される検索テーブルと互換でない可能性がある（すなわち、端点は、ソース・ノードで維持される検索テーブルのフィンガではない）。その結果、弧の１つにまたがる（たとえば、［ｎ＊Ｌ，（ｎ＋１）＊Ｌ）にわたる）検索を実行する時に、複数のサービス・ロケーション検索メッセージを生成する必要がある場合がある。これを、図７に示す。
【０１７０】
図７に、図６の例示的なＣｈｏｒｄネットワークでサービスの漸進的サービス・ロケーション検索を実行するための例示的検索範囲を示す。図７に示されているように、第（ｋ＋１）フィンガは、検索範囲内に含まれ（すなわち、ｎ＊Ｌ＜第（ｋ＋１）フィンガ＜（Ｎ＋１）＊Ｌ）、第ｋフィンガおよび第（ｋ＋２）フィンガは、検索範囲の外にある。この場合には、弧にまたがるサービス・ロケーション検索を実行するために、ソース・ノードは、次のように２つのサービス検索要求メッセージを生成するはずである。（ａ）１つの検索要求が、（ｎ＊Ｌ，第（ｋ＋１）フィンガ）の検索範囲と共に第ｋフィンガに送信され、（ｂ）１つの検索要求が、［第（ｋ＋１）フィンガ，（Ｎ＋１）＊Ｌ）の検索範囲と共に第（ｋ＋１）フィンガに送信される。
【０１７１】
一実施形態では、漸進的サービス・ロケーション検索がソース・ノードの検索テーブルと位置合わせされるように、漸進的サービス・ロケーション検索を変更することができ、これによって、１つの弧にまたがる検索が複数のサービス検索要求メッセージを必要とする状況を回避する。
【０１７２】
位置合せされた漸進的サービス・ロケーション検索の例示的実施形態を、図示し、図８および図９に関して説明する。
【０１７３】
図８に、位置合せされた漸進的検索ロケーション検索を使用して、サービス・ロケーション要求を開始するノードでサービス検索要求メッセージを生成する方法の一実施形態を示す。
【０１７４】
ステップ８０２で、方法８００が始まる。
【０１７５】
ステップ８０４では、ノードが、サービスをサポートするアクティブ・ノードの推定平均個数（Ｌと表される）を判定する。
【０１７６】
サービスをサポートするアクティブ・ノードの推定平均個数は、そのような情報の任意の適切なソースから（たとえば、ノードのローカル・メモリから、ウェブ・サーバから、および類似物）判定することができる。
【０１７７】
サービスをサポートするアクティブ・ノードの平均個数を、任意の適切な形で推定することができる。一実施形態では、サービスをサポートするアクティブ・ノードの平均個数を、図示し、図１〜図６に関して説明したサービス・ロケーション検索アルゴリズムの変更された版を使用して推定することができる。図１〜図６に関して説明したサービス・ロケーション検索アルゴリズムでは、中間ノードは、肯定の応答メッセージをダウンストリーム・ノードから受信するや否や、そのメッセージをアップストリーム・ノードに転送する。一実施形態では、図示し、図１〜図６に関して説明したサービス・ロケーション検索アルゴリズムを変更し、各中間ノードが、それがサービス検索要求メッセージを開始したダウンストリーム・ノードの１つから最初の肯定の応答を受信した時にアップストリーム・ノードに肯定の応答を即座に転送するのではなく、それがサービス検索要求メッセージを開始したすべてのダウンストリーム・ノードからのすべての応答メッセージを待ち、その後、合併された応答（サービスをサポートするダウンストリーム・ノードの総数と、これらのノードのうちの少なくとも１つのノードＩＤおよびＩＰアドレスとを含む）をアップストリーム・ノードに転送するようにすることができる。中間ノードは、この変更された処理を任意の適切な形で実行するように指示され得る。たとえば、一実施形態では、サービスをサポートするアクティブ・ノードの平均個数を推定する処理を実行すべきか否かに関して中間ノードに知らせるために、新しいインジケータをサービス検索要求メッセージに追加することができる。１つのそのような実施形態では、新しいインジケータを、少なくとも特定のサービスに関する最初の少数の検索についてＴＲＵＥにセットし、それによってソース・ノードが、サービスをサポートするアクティブ・ノードの平均個数の推定値を判定できるように、サービスをサポートするアクティブ・ノードの個数の少なくとも少数の推定値をノードが受信するようにすることができる。その後、新しいインジケータにＦＡＬＳＥをセットし、その結果、中間ノードがサービスのすべての要求について変更された処理を実行することを要求されないようにすることができる。１つのさらなる実施形態では、ＴＲＵＥをセットされた新しいインジケータと共に、図１〜図６に関して説明したサービス・ロケーション検索アルゴリズムを使用してサービスに関するサービス・ロケーション検索要求を周期的に実行することによって、サービスをサポートするアクティブ・ノードの平均個数の推定値を周期的に更新することができる。サービスをサポートするアクティブ・ノードの平均個数の推定値を判定した後に、ノードは、漸進的サービス・ロケーション検索能力を使用してサービスの後続検索を実行するのに、サービスをサポートするアクティブ・ノードの平均個数の推定値を使用することができる。さらに、上で説明した実施形態に加えて、上で説明した実施形態の多数の変形形態を使用することができる。たとえば、発するノードからネットワークの一部への検索メッセージが、ＴＲＵＥをセットされたインジケータを有することができ、残りの部分について、インジケータにはＦＡＬＳＥがセットされる。この例では、ＴＲＵＥをセットされたインジケータを用いる検索メッセージからの応答を、より低い正確さを伴って、サービスをサポートするアクティブ・ノードの平均個数を推定するのに使用することができるが、ＦＡＬＳＥをセットされたインジケータを伴う検索メッセージは、肯定の応答を待たないので、より高速の応答を生じる。多数の他の方法も可能であることを了解されたい。一般に、異なる方法の間の相違は、推定の正確さ、アルゴリズムの複雑さ、応答時間、生成されるメッセージの個数、および類似物の間のトレードオフを含む。
【０１７８】
ステップ８０６では、ノードが、サービスの初期検索に関するフィンガの個数（Ｋと表される）を決定する。初期検索に関するフィンガの個数は、サービスをサポートするアクティブ・ノードの平均個数を使用して決定される。初期検索に関するフィンガの個数は、式（Ｌ−１）＊ｌｎ（１−ａ）＜ｌｎ（１／ｂ）からＬについて解くことによって決定され、ここで、（ｉ）ａは、あるノードＩＤがサービスをサポートするアクティブ・ノードを有する確率であり、（ｉｉ）ｂは、検索が否定である確率であり、（ｉｉｉ）Ｌは、検索範囲である。
【０１７９】
ステップ８０８では、ノードが、そのノードで維持される検索テーブルの最初のＫ個のフィンガにサービス検索要求メッセージを送信する。サービス検索要求メッセージは、サービス検索要求メッセージのＩＤ、要求されるサービスを識別する際に使用されるように適合されたサービス識別情報、検索範囲、および類似物など、要求されるサービスを検索する際に使用するのに適するすべての情報を含む。第ｉフィンガの検索範囲は、［第ｉフィンガ，第（ｉ＋１）フィンガ）であり、ここで、ｉ＝１、…、Ｋである。異なる情報をサービス検索要求メッセージ内に含めることができることを了解されたい。
【０１８０】
ステップ８１０では、サービスをサポートするノードが識別された（すなわち、ステップ８０８からの初期サービス検索要求メッセージおよびオプションでステップ８１６からの１つまたは複数の後続サービス検索要求メッセージに基づいて）かどうかに関する判定を行う。サービスをサポートするノードが識別された場合には、方法８００は、ステップ８１８に進み、ステップ８１８では、方法８００が終了する。サービスをサポートするノードが識別されていない場合には、方法８００は、ステップ８１２に進む。
【０１８１】
ステップ８１２では、検索テーブル内の最後のフィンガが選択されたかどうか（すなわち、Ｋ＝Ｍであるかどうか）に関する判定を行う。検索テーブル内の最後のフィンガが選択された場合には、方法８００はステップ８１８に進み、ステップ８１８では、方法８００が終了する。検索テーブル内の最後のフィンガが選択されていない場合には、方法８００はステップ８１４に進む。
【０１８２】
ステップ８１４では、Ｋの値を増分する。ステップ８１６では、ノードが、そのノードで維持される検索テーブルの第Ｋフィンガにサービス検索要求メッセージを送信する。ステップ８１６から、方法８００はステップ８１０に戻り、その点で、漸進的検索の現在のステージ中にサービスをサポートするノードが識別されたかどうかに関する判定を行う。
【０１８３】
サービスをサポートするノードが識別される時または検索テーブルのすべてのフィンガが処理された後にサービスをサポートするノードが識別されない時に入るステップ８１６では、方法８００が終了する。
【０１８４】
図８に関して、一実施形態では、第（ｉ＋１）フィンガが第ｉフィンガと同一である場合には、サービス検索要求メッセージは、第（ｉ＋１）フィンガについて送信されず（初期検索内でフィンガに重複したメッセージを送信するのを避けるために）、これによって、複数のサービス検索要求メッセージが同一ノードに送信されることを防ぐ。
【０１８５】
主に直列に実行されるものとして図示され、本明細書で説明されるが、方法８００のステップの少なくとも一部を、同時にまたは図示され、図８に関して説明されたものとは異なる順序で実行することができる。主に中間ノードでサービス検索要求メッセージ生成を実行するプロセス論理の特定の実施態様に関して図示され、本明細書で説明されるが、中間ノードでサービス検索要求メッセージ生成を実行するプロセス論理を、それでも図示され本明細書で説明されるサービス・ロケーション能力をサポートしながら、さまざまな他の形で実施できることを了解されたい。
【０１８６】
図９Ａ〜９Ｄに、図１の例示的なＣｈｏｒｄネットワークでのサービスの位置合せされた漸進的検索ロケーション検索を実行する例を示す、図１の例示的なＣｈｏｒｄネットワークのノードのうちの１つによって開始されたサービス・ロケーション検索に応答して図１の例示的なＣｈｏｒｄネットワーク内で開始されるサービス検索要求メッセージを示す。
【０１８７】
図９Ａ〜９Ｄの例では、ノード０が、サービス・ロケーション要求を開始しつつある。要求されたサービスをサポートするアクティブ・ノードの推定平均個数は、８と等しく（Ｌ＝２３＝８）、これは、サービスの初期検索が、ノード０の検索テーブルの最初の３つのフィンガすなわちノード２、２、および５を含むことを示す。したがって、サービス検索要求メッセージは、それぞれ［２，５）および［５，９）の検索範囲と共にノード２および５に送信される（ノード９は第４フィンガである）。ノード０によるこの初期検索は、図９Ａに示されており、サービス検索要求メッセージは、ノード２および５に送信され、ノード２は、サービス検索要求メッセージを３に送信し、ノード５は、サービス検索要求メッセージをノード６および７に送信する。この例では、ノード７が、要求されたサービスをサポートするアクティブ・ノードであり、したがって、ノード０は、初期検索で要求されたサービスをサポートするノードを突き止め、位置合せされた漸進的サービス・ロケーション検索は完了する。
【０１８８】
しかし、図９Ａ〜９Ｄの例では、例示のために、ノード７がサービスをサポートせず、したがって初期検索が失敗すると仮定する。初期検索が失敗したと判定する時に、ノード０は、その検索テーブル内の次のフィンガすなわちノード９への、サービスの後続検索を開始する。したがって、サービス検索要求メッセージが、［９，１６）の検索範囲と共にノード９に送信される。ノード０によるこの後続検索は、図９Ｂに示されており、サービス検索要求メッセージは、ノード９に送信され、ノード９は、サービス検索要求メッセージをノード１２および１３に送信する。この例では、範囲［９，１６）内に要求されたサービスをサポートするアクティブ・ノードがなく、したがって、位置合せされた漸進的サービス・ロケーション検索は、継続される。
【０１８９】
図９Ａ〜９Ｄの例では、最初の後続検索が失敗したと判定される時に、ノード０は、その検索テーブル内の次のフィンガすなわちノード１６へのサービスの第２の後続検索を開始する。したがって、サービス検索要求メッセージが、［１６，３２）の検索範囲と共にノード１６に送信される。ノード０によるこの後続検索は、図９Ｃに示されており、サービス検索要求メッセージは、ノード１６に送信され、ノード１６は、サービス検索要求メッセージをノード１７、１８、２０、および２４に送信する（ならびに、これらのノードは、追加のサービス検索要求メッセージを伝搬させる）。この例では、ノード１９が、要求されたサービスをサポートするアクティブ・ノードであり、したがって、ノード０は、初期検索で要求されたサービスをサポートするノードを突き止め、位置合せされた漸進的サービス・ロケーション検索は完了する。
【０１９０】
しかし、図９Ａ〜９Ｄの例では、例示のために、ノード１９がサービスをサポートせず、したがって第２の後続の検索が失敗すると仮定する。第２の後続の検索が失敗したと判定する時に、ノード０は、その検索テーブル内の次のフィンガすなわちノード３２へのサービスの第３の後続検索を開始する。したがって、サービス検索要求メッセージが、［３２，０）の検索範囲と共にノード３２に送信される。このノード０による後続検索は、図９Ｄに示されており、サービス検索要求メッセージは、ノード３２に送信され、ノード３２は、サービス検索要求メッセージをノード３４、３７、４０、および４９に送信する（ならびに、これらのノードは、追加のサービス検索要求メッセージを伝搬させる）。この例では、ノード５１が、要求されたサービスをサポートするアクティブ・ノードであり、したがって、ノード０は、初期検索で要求されたサービスをサポートするノードを突き止め、位置合せされた漸進的サービス・ロケーション検索は完了する。
【０１９１】
位置合せされた漸進的サービス・ロケーション検索では、複数のサービス検索要求メッセージが、初期ステージで発するノードによって送信されるが、単一のサービス検索要求メッセージが、後続ステージのそれぞれで発するノードによって送信される。これは、図８の例示的方法および図９Ａ〜９Ｄの例から明白である。一般に、最初の２つの検索の検索範囲は、それぞれがＬ個のノードＩＤをカバーし、その後、後続検索の検索範囲は、すべてのステージで２倍になる（たとえば、第３の検索は、約２＊Ｌ個のノードＩＤをカバーし、第４の検索は、約４＊Ｌ個のノードＩＤをカバーするなど）。
【０１９２】
本明細書で説明されるように、漸進的サービス・ロケーション検索は、要求されたサービスをサポートするノードを突き止めるためにＣｈｏｒｄネットワーク内で交換されるメッセージの個数を減らすための１つの適切な手段である。
【０１９３】
一実施形態では、要求されたサービスをサポートするノードを突き止めるためにＣｈｏｒｄネットワーク内で交換されるメッセージの個数を、ネットワークのノードで、要求されたサービスをサポートするノードとして以前に識別された１つまたは複数のノードのノードＩＤをキャッシングすることによって減らすことができる。この実施形態では、ノードのソース・ノードの展望から、要求されたノードをサポートするノードとしてソース・ノードによって以前に識別された１つまたは複数のノードのノードＩＤを、ソース・ノードでキャッシングすることができる。この実施形態では、サービスを検索する時に、検索メッセージは、ソース・ノードがキャッシングされた情報を進んで受け入れることを示し、したがって、ノードがそのような検索要求を受信する時に、ノードがそのキャッシュからのノードＩＤ（１つまたは複数）を用いて応答できることを示すためにセットできるインジケータを含むことができる。この形で、検索メッセージの個数が減らされ、応答時間はより高速であるが、キャッシングされた情報が古いという危険性がある。一実施形態では、古い情報を防ぐために、最後のＸの長さの時間以内にキャッシングされたノードＩＤだけが応答に含まれ、ここで、Ｘの長さの時間は、必要または望みに応じて構成することができる（たとえば、最後の３０分、最後の４時間、最後の１日、および類似物）。
【０１９４】
一実施形態では、要求されたサービスをサポートするノードを突き止めるためにＣｈｏｒｄネットワーク内で交換されるメッセージの個数を、どのノードがどのサービスをサポートするのかに関する情報を交換するためにＣｈｏｒｄネットワークのノードの間で交換されるハートビート・メッセージ上にピギーバックすることによって、減らすことができる。本明細書で説明されるように、Ｃｈｏｒｄネットワーク内のノードは、その先行ノードおよび後継ノードにハートビート・メッセージを周期的に送信する。あるノードによってその先行物に送信されるハートビート・メッセージは、そのノードの後継物（またはＫ個の後継物）のノードＩＤ（１つまたは複数）を含み、同様に、あるノードによってその後継物に送信されるハートビート・メッセージは、そのノードの先行物（またはＫ個の先行物）のノードＩＤ（１つまたは複数）を含む。この実施形態では、先行物／後継物情報に加えて、ノードによって送信されるハートビート・メッセージは、そのノードによってサポートされるすべてのサービスを示す情報を含み、これによって、これらのノードのそれぞれが、その近傍のサービス能力を知ることを可能にする。この形で、Ｃｈｏｒｄネットワーク内でサービスを突き止めるために交換される必要があるメッセージの個数が、減らされる。
【０１９５】
上で説明したように、Ｃｈｏｒｄネットワークによってサポートできる１つのサービスは、クロスリング検索サービスである。クロスリング検索サービスは、ターゲット・ノードが、ターゲット・ノードがそのメンバではない１つまたは複数の他のＣｈｏｒｄネットワーク上のオブジェクトを検索する要求を開始することを可能にする。
【０１９６】
一般に、Ｃｈｏｒｄネットワークのメンバは、あるタイプの音楽、あるタイプのビデオ、学術研究トピック、および類似物など、ある共通の関心（１つまたは複数）に関するファイルを共有することを望むコミュニティを形成する。１人のユーザが、多数の関心を有する場合があり、したがって、そのユーザのノードが、同時に複数のＣｈｏｒｄネットワークに参加する場合がある。あるファイルを検索しているノードが、それが属するＣｈｏｒｄネットワーク（１つまたは複数）内でそのファイルを突き止めることに失敗する場合に、そのノードは、そのファイルの検索を１つまたは複数の追加のＣｈｏｒｄネットワークに拡張することを望む場合があり、これは、クロスリング検索サービスを使用して達成することができる。
【０１９７】
クロスリング検索サービスを使用して、ファイルを検索している発するノードは、それがメンバであるＣｈｏｒｄネットワーク（１つまたは複数）を検索して、１つまたは複数の他のＣｈｏｒｄネットワークに属するすべてのノード（１つまたは複数）を突き止めることができる。発するノードは、検索要求を開始することができる。その検索要求では、発するノードは、サービスがクロスリング検索サービスであることを指定する。検索要求は、追加のサービス固有情報を含むことができる。
【０１９８】
追加のサービス固有情報は、発するノードが既にファイルを検索したＣｈｏｒｄネットワーク内のＣｈｏｒｄネットワークＩＤのリストである検索禁止リストを含むことができる。この場合に、この要求に応答する時に、これらのＣｈｏｒｄネットワークは、無視されなければならない（すなわち、検索要求を受信するノードは、そのノードが検索禁止リスト内で示されるＣｈｏｒｄネットワーク（１つまたは複数）以外のＣｈｏｒｄネットワーク（１つまたは複数）のメンバである場合に限って、肯定の応答を送信する。
【０１９９】
追加のサービス固有情報は、発するノードがその中でファイルを検索することを望むＣｈｏｒｄネットワークのＣｈｏｒｄネットワークＩＤのリストである特定検索リストを含むことができる。この場合に、この要求に応答する時に、これらのＣｈｏｒｄネットワーク以外のすべてのＣｈｏｒｄネットワークは、無視されなければならない（すなわち、検索要求を受信するノードは、そのノードが特定検索リスト内で示されるＣｈｏｒｄネットワークのうちの１つのメンバである場合に限って肯定の応答を送信する）。
【０２００】
クロスリング検索サービスを使用して、ファイルを検索している発するノードは、検索要求に応答して検索応答を受信する。この場合に、すべての肯定の検索応答は、肯定の検索応答をトリガしたＣｈｏｒｄネットワーク（１つまたは複数）のＣｈｏｒｄネットワークＩＤ（１つまたは複数）を含む。肯定の検索応答を受信する時に、発するノードは、任意の適切な形で、識別されたＣｈｏｒｄネットワーク（１つまたは複数）からそのファイルを入手することを試みることができる。
【０２０１】
一実施形態では、肯定の検索応答を受信する時に、発するノードは、識別されたＣｈｏｒｄネットワーク（１つまたは複数）に参加することによって、識別されたＣｈｏｒｄネットワーク（１つまたは複数）からファイルを入手することを試みることができる。この場合に、ｃｈｏｒｄネットワーク（１つまたは複数）に参加すると、次いで発するノードは、参加されるＣｈｏｒｄネットワーク（１つまたは複数）内でファイルの検索を開始することができる。
【０２０２】
一実施形態では、肯定の検索応答を受信する時に、発するノードは、肯定の検索応答を用いて応答したノードが、発するノードの代わりに識別されたＣｈｏｒｄネットワーク（１つまたは複数）内でファイルの検索を開始することを要求することができる。これは、発するノードが識別されたＣｈｏｒｄネットワーク（１つまたは複数）に参加する許可を有しない場合、発するノードが識別されたＣｈｏｒｄネットワーク（１つまたは複数）に参加し、離脱するのに必要なリソースを振り向けることができないかそうするつもりがない場合（すなわち、ノードがＣｈｏｒｄネットワークに参加する時に、暗黙の仮定は、そのノードが、Ｃｈｏｒｄネットワークの代わりに複数のファイルを格納することであり、Ｃｈｏｒｄネットワークへの参加および離脱は、ファイルがノードの間で転送されるので時間およびネットワーク・リソースを要する）、発するノードが、識別されたＣｈｏｒｄネットワークに技術的に参加できない場合（たとえば、発するノードがＩＰｖ４専用ノードであり、識別されたＣｈｏｒｄネットワーク（１つまたは複数）がＩＰｖ６  Ｃｈｏｒｄネットワークである場合、または発するノードがＩＰｖ６専用ノードであり、識別されたＣｈｏｒｄネットワーク（１つまたは複数）がＩＰｖ４ネットワークである場合）、および類似物など、発するノードが、識別されたＣｈｏｒｄネットワーク（１つまたは複数）に参加できないか参加するつもりがない場合に有用である可能性がある。発するノードは、肯定の検索応答を用いて応答したノードに検索要求メッセージを送信することによって、肯定の検索応答を用いて応答したノードが発するノードの代わりに識別されたＣｈｏｒｄネットワーク（１つまたは複数）内でファイルの検索を開始することを要求することができる。この場合に、発するノードによって送信される検索要求メッセージは、発するノードが検索しようとしているファイルのフル・ネームを含む。というのは、識別されたＣｈｏｒｄネットワーク（１つまたは複数）が、発するノードのＣｈｏｒｄネットワークとは異なるキー空間を有し、かつ／または異なるハッシュ関数を使用する場合があるからである。ファイルが、識別されたＣｈｏｒｄネットワーク（１つまたは複数）内で突き止められない場合には、発するノードは、否定の検索応答を受信する。ファイルが識別されたＣｈｏｒｄネットワーク（１つまたは複数）内で突き止められる場合には、そのファイルを格納しているノードが、そのファイルを発するノードに転送する。ファイルは、発するノードのＣｈｏｒｄネットワークに格納されてもされなくてもよい。
【０２０３】
主にサービス・ロケーション能力が特定のタイプのＰ２Ｐネットワーク内すなわちＣｈｏｒｄネットワーク内で実施される実施形態に関して図示され、本明細書で説明されるが、このＰ２Ｐサービス・ロケーション能力を、サービス検索能力をサポートするのに適する任意の他のタイプのＰ２Ｐネットワーク内で実施することができる。
【０２０４】
一実施形態では、サービス・ロケーション能力がＤＨＴベースのＰ２Ｐネットワーク全般での使用に適するように、サービス・ロケーション能力を適合させることができる。１つのそのような実施形態では、サービス・ロケーション能力がそのために提供されるＰ２Ｐネットワークは、明確に構造化されたジオメトリを有し（たとえば、Ｃｈｏｒｄについて、ジオメトリは円である）、「領域」の概念を、このジオメトリから定義することができる（たとえば、Ｃｈｏｒｄについて、「領域」は円の弧である）。ＤＨＴベースのＰ２Ｐネットワークのソース・ノードが、サービス・ロケーション検索を開始しようとしている時に、ソース・ノードは、そのルーティング・テーブル内のノードにサービス検索要求を送信し、ノードに送信される各サービス検索要求は、検索がサービス検索要求を受信するノードによって制限されなければならない領域の記述を含む。中間物がサービス検索要求を受信する時に、その中間ノードは、要求されたサービスをサポートするノードをローカルに知っているかどうかを判定する（たとえば、その中間ノードは、それ自体、その先行物、その後継物、その中間ノードで使用可能なキャッシングされた情報からの１つまたは複数のノード、および類似物ならびにその組合せを識別することができる）。中間ノードが、要求されたサービスをサポートするノードをローカルに識別する場合には、中間ノードは、肯定の応答を用いて応答する。中間ノードが、要求されたサービスをサポートするノードをローカルに識別できない場合には、中間ノードは、それ自体のルーティング・テーブルに基づいてサービス検索要求を伝搬させる。中間ノードによるサービス検索要求の伝搬は、中間ノードによって受信されたサービス検索要求内に含まれる情報および中間ノードのルーティング・テーブルからの情報によって制限されるスコープを有する。サービスを突き止めるのに使用されるサービス検索要求の検索範囲を、検索の効率を改善するために検索範囲の間のオーバーラップが最小になるように適合させることができるが、いくつかの場合に、オーバーラップが検索範囲記述要件を単純化するならば、少なくともあるオーバーラップが望ましい可能性がある。サービス・ロケーション能力のそのような一般化された実施態様では、Ｃｈｏｒｄネットワークに関して図示され、本明細書で説明される他の能力の多くを利用することもできる（たとえば、検索が領域に制限される時の成功の検索の確率を推定するため、漸進的検索を実行するため、および類似物、ならびにその組合せ）。
【０２０５】
サービス・ロケーション能力が提供される実施形態に関して図示され、本明細書で説明されるが、図示され、本明細書で説明されるサービス・ロケーション能力を、Ｐ２Ｐネットワーク内で情報を分配するための情報分配能力を提供するように適合させることができることを了解されたい。そのような実施形態では、サービス・ロケーション検索能力の文脈で本明細書で説明されるサービス検索要求メッセージを、情報分配能力での情報分配メッセージとしての使用のために適合させることができる。そのような実施形態では、Ｐ２Ｐネットワークのすべてのノード、Ｐ２Ｐネットワークのノードの１つまたは複数の範囲、１つまたは複数の判断基準を満足するＰ２Ｐネットワークの１つまたは複数のノード、および類似物、ならびにそのさまざまな組合せに情報を分配できるように、情報分配能力を実施することができる。
【０２０６】
図１０に、本明細書で説明される機能を実行する際に使用するのに適するコンピュータの高水準ブロック図を示す。図１０に示されているように、コンピュータ１０００は、プロセッサ要素１００２（たとえば、中央処理装置（ＣＰＵ）または他の適切なプロセッサ（１つまたは複数））、メモリ１００４（たとえば、ランダム・アクセス・メモリ（ＲＡＭ）、読取り専用メモリ（ＲＯＭ）、および類似物）、サービス・ロケーション検索モジュール／プロセス１００５、およびさまざまな入出力デバイス１００６（たとえば、ユーザ入力デバイス（キーボード、キーパッド、マウス、および類似物など）、ユーザ出力デバイス（ディスプレイ、スピーカ、および類似物など）、入力ポート、出力ポート、受信器、送信器、ストレージ・デバイス（たとえば、テープ・ドライブ、フロッピ・ドライブ、ハード・ディスク・ドライブ、コンパクト・ディスク・ドライブ、および類似物など））を含む。
【０２０７】
図示され、本明細書で説明された機能を、ソフトウェアでならびに／またはソフトウェアおよびハードウェアの組合せで、たとえば汎用コンピュータ、１つもしくは複数の特定用途向け集積回路（ＡＳＩＣ）、および／または任意の他のハードウェア同等物を使用して実施できることに留意されたい。一実施形態では、サービス・ロケーション検索プロセス１００５をメモリ１００４にロードし、プロセッサ１００２によって実行して、本明細書で上で説明した機能を実施することができる。したがって、サービス・ロケーション検索プロセス１００５（関連するデータ構造を含む）を、コンピュータ可読記憶媒体または担体、たとえば、ＲＡＭメモリ、磁気ドライブ、磁気ディスケット、光ドライブ、または光ディスケット、および類似物に格納することができる。
【０２０８】
ソフトウェアとして実施される、本明細書で議論される機能の諸部分を、任意の適切な形でピアツーピア・ネットワークのノード上で構成できる（たとえば、ノードの製造中に提供する、ノードで管理的にロードする、ウェブ・サーバまたは他の適切なソースからダウンロードする、および類似物、ならびにそのさまざまな組合せ）ことが企図されている。ソフトウェア方法として本明細書で議論されるステップの一部を、ハードウェア内で、たとえばさまざまな方法ステップを実行するためにプロセッサと協力する回路網として実施できることが企図されている。本明細書で説明される機能／要素の諸部分を、コンピュータ・プログラム製品として実施することができ、コンピュータ命令は、コンピュータによって処理される時に、本明細書で説明される方法および／または技法が呼び出されまたは他の形で提供されるように、コンピュータの動作を適合させる。発明的方法を呼び出す命令を、固定媒体または取外し可能媒体内に格納し、放送媒体または他の信号担持媒体内のデータ・ストリームを介して送信し、かつ／または命令に従って動作するコンピューティング・デバイス内のメモリ内に格納することができる。
【０２０９】
本発明の諸態様は、特許請求の範囲で指定される。本発明のこれらおよび他の態様は、次の番号付きの条項で指定される。
【０２１０】
１．複数のノードを含むピアツーピア（Ｐ２Ｐ）ネットワーク内でサービスを検索する方法であって、
Ｐ２Ｐネットワークのターゲット・ノードで、Ｐ２Ｐネットワーク内のサービスを検索する要求を検出するステップであって、ターゲット・ノードは、Ｐ２Ｐネットワークのそれぞれの複数のノードを識別する複数のエントリを含む検索テーブルを含む、ステップと、
検索テーブル内で識別されるノードのうちの少なくとも１つに向かってサービス検索要求を開始するステップであって、サービス検索要求は、サービスをサポートするＰ２Ｐネットワークの少なくとも１つのノードを識別する要求であり、サービス検索要求は、サービスおよびサービス検索要求がそれに向かって開始されるノードによって使用される検索範囲を示す情報を含む、ステップと
を含む方法。
【０２１１】
２．サービス検索要求は、検索テーブル内のノードのすべてに向かって並列に開始される、条項１に記載の方法。
【０２１２】
３．サービス検索要求は、サービスをサポートする少なくとも１つのノードが識別されるまでまたはＰ２Ｐネットワークのノードのいずれもがサービスをサポートしないとの判定が行われるまで、検索テーブルのノードに向かって直列に開始される、条項１に記載の方法。
【０２１３】
４．サービス検索要求は、検索テーブルの第ｉノードから否定の検索応答を受信することに応答して、検索テーブルの第（ｉ＋１）ノードに向かって開始される、条項３に記載の方法。
【０２１４】
５．サービス検索要求は、検索テーブルのノードの部分集合に向かって並列に開始され、検索テーブルのノードの部分集合は、検索テーブルの最初のＫ個のエントリ内で識別されるノードを含む、条項１に記載の方法。
【０２１５】
６．肯定の検索応答が検索テーブルのノードの部分集合のノードのうちの少なくとも１つから受信される場合に、サービスの要求を開始するステップと、
肯定の検索応答が検索テーブルのノードの部分集合のノードのうちの少なくとも１つから受信されない場合に、
検索テーブルのノードの部分集合に含まれない検索テーブルの次のエントリに関連する次のノードに向かって、Ｐ２Ｐネットワーク内のサービスを突き止めるために後続サービス検索要求を開始するステップと
をさらに含む、条項５に記載の方法。
【０２１６】
７．サービスをサポートするＰ２Ｐネットワークのノードの推定平均個数を使用して検索テーブルのノードの部分集合を識別するステップ
をさらに含む、条項５に記載の方法。
【０２１７】
８．検索テーブルのノードの部分集合は、Ｌについて式（Ｌ−１）＊ｌｎ（１−ａ）＜ｌｎ（１／ｂ）を解くことによって識別され、（ｉ）ａは、ノードＩＤがサービスをサポートするアクティブ・ノードを有する確率であり、（ｉｉ）ｂは、検索が否定である確率であり、（ｉｉｉ）Ｌは、検索範囲である、条項７に記載の方法。
【０２１８】
９．サービスをサポートするＰ２Ｐネットワークのノードの推定平均個数は、ノードのローカル・メモリからまたはウェブ・サーバから判定される、条項７に記載の方法。
【０２１９】
１０．サービスをサポートするＰ２Ｐネットワークのノードの推定平均個数は、
検索テーブルのノードのそれぞれに向かって、サービスをサポートするＰ２Ｐネットワークのノードのそれぞれのターゲット・ノードによる識別を可能にするように構成されたそれぞれのサービス検索要求メッセージを開始するステップと、
検索テーブルのノードのそれぞれから、サービスをサポートするノードであるものとしてそのノードによって識別されるＰ２Ｐネットワークのノードの個数の指示またはサービスをサポートするＰ２Ｐネットワークのノードの個数を導出する際の使用のために適合された情報を含むそれぞれのサービス検索応答メッセージを受信するステップと、
サービスをサポートするＰ２Ｐネットワークのノードの推定個数を計算するためにサービス検索応答メッセージを処理するステップであって、サービスをサポートするＰ２Ｐネットワークのノードの推定個数は、サービスをサポートするＰ２Ｐネットワークのノードの推定平均個数を判定する際の使用のために適合される、ステップと
を含む方法によって推定される、条項７に記載の方法。
【０２２０】
１１．サービス検索要求がそれに向かって開始された検索テーブルのノードのうちの少なくとも１つのそれぞれから、ノードがサービスをサポートするか、またはサービスをサポートする別のノードを識別したかどうかを示す検索応答を受信するステップ
をさらに含む、条項１に記載の方法。
【０２２１】
１２．ターゲット・ノードが、サービスをサポートするノードが突き止められたことを示す肯定の検索応答を受信する時に、サービスをサポートするノードに向かってターゲット・ノードからサービスの要求を開始するステップ
をさらに含む、条項１に記載の方法。
【０２２２】
１３．肯定の検索応答は、サービスをサポートするノードのノード識別子およびサービスをサポートするノードのＩＰアドレスを含む、条項１２に記載の方法。
【０２２３】
１４．サービスは、追加のＰ２ＰネットワークのメンバであるＰ２Ｐネットワークの少なくとも１つの他のノードを識別するクロスリング検索サービスである、条項１に記載の方法。
【０２２４】
１５．ターゲット・ノードが、追加のＰ２Ｐネットワークのメンバであるノードが突き止められたことを示す肯定の検索応答を受信する時に、
ターゲット・ノードから、ターゲット・ノードが追加のＰ２Ｐネットワークに参加するプロセスを開始するステップと、
ターゲット・ノードから、追加のＰ２Ｐネットワークのメンバであるノードに向かって、追加のＰ２Ｐネットワークのメンバであるノードが追加のＰ２Ｐネットワーク内でオブジェクトの検索を開始する要求を開始するステップと
のうちの少なくとも１つを実行するステップ
をさらに含む、条項１４に記載の方法。
【０２２５】
１６．複数のノードを含むピアツーピア（Ｐ２Ｐ）ネットワーク内でサービスを検索する装置であって、
Ｐ２Ｐネットワークのそれぞれの複数のノードを識別する複数のエントリを含む検索テーブルを格納するメモリと、
Ｐ２Ｐネットワーク内のサービスを検索する要求を検出し、
検索テーブル内で識別されるノードのうちの少なくとも１つに向かってサービス検索要求を開始し、サービス検索要求は、サービスをサポートするＰ２Ｐネットワークの少なくとも１つのノードを識別する要求であり、サービス検索要求は、サービスおよびサービス検索要求がそれに向かって開始されるノードによって使用される検索範囲を示す情報を含む
ように構成されたプロセッサと
を含む装置。
【０２２６】
１７．複数のノードを含むピアツーピア（Ｐ２Ｐ）ネットワーク内でサービスを突き止める方法であって、
Ｐ２Ｐネットワークのターゲット・ノードでサービス検索要求を受信するステップであって、サービス検索要求は、要求されるサービスおよびターゲット・ノードに関する検索範囲を示す情報を含む、ステップと、
要求されるサービスを示す情報の少なくとも一部を使用して、ターゲット・ノードがサービスをサポートするかどうかを判定するステップと、
ターゲット・ノードがサービスをサポートするとの判定が行われる時に、サービスがターゲット・ノードによってサポートされることを示すサービス検索応答メッセージをターゲット・ノードから開始するステップと、
ターゲット・ノードがサービスをサポートしないとの判定が行われる時に、ターゲット・ノードからＰ２Ｐネットワークの少なくとも１つの他のノードに向かってサービス検索要求を開始すべきかどうかを判定するステップと
を含む方法。
【０２２７】
１８．ターゲット・ノードからＰ２Ｐネットワークの少なくとも１つの他のノードに向かってサービス検索要求を開始すべきではないとの判定が行われる時に、
ターゲット・ノードから、サービスをサポートするノードを検索範囲を使用してターゲット・ノードによって突き止めることができなかったことを示す否定の応答メッセージを開始するステップ
をさらに含む、条項１７に記載の方法。
【０２２８】
１９．Ｐ２Ｐネットワークの少なくとも１つの他のノードに向かってサービス検索要求を開始すべきであるとの判定が行われる時に、
ターゲット・ノードによって開始される新しいサービス検索要求の検索範囲を決定するステップであって、検索範囲は、ターゲット・ノードで受信されたサービス検索要求に含まれる検索範囲およびターゲット・ノード上に格納された検索テーブルを使用して決定される、ステップと、
ターゲット・ノードから新しいサービス検索要求を開始するステップであって、新しいサービス検索要求は、要求されるサービスおよび新しいサービス検索要求について決定された検索範囲を示す情報を含む、ステップと
をさらに含む、条項１７に記載の方法。
【０２２９】
２０．Ｐ２Ｐネットワークの少なくとも１つの他のノードに向かってサービス検索要求を開始すべきかどうかを判定するステップは、
ターゲット・ノードの検索テーブルのいずれかのエントリが、ターゲット・ノードで受信されたサービス検索要求の検索範囲に含まれるノードを識別するかどうかを判定するステップと、
ターゲット・ノードの検索テーブルのすべてのエントリが、サービス検索要求の検索範囲に含まれるノードを識別しない場合に、ターゲット・ノードがサービス検索要求を開始する必要が全くないと判定するステップと、
ターゲット・ノードの検索テーブルの少なくとも１つのエントリが、サービス検索要求の検索範囲に含まれる少なくとも１つのノードを識別する場合に、サービス検索要求の検索範囲に含まれるターゲット・ノードの検索テーブルの少なくとも１つのエントリのそれぞれの少なくとも１つのノードに向かってターゲット・ノードから少なくとも１つのサービス検索要求を開始するステップと
を含む、条項１７に記載の方法。
【０２３０】
２１．Ｐ２Ｐネットワークの少なくとも１つの他のノードに向かってサービス検索要求を開始すべきであるとの判定が行われる時に、
Ｐ２Ｐネットワークの別のノードに向かってターゲット・ノードによって開始されたサービス検索要求に関連するサービス検索応答を受信するステップと、
サービス検索応答が正当な応答ではない場合に、サービス検索応答を無視し、少なくとも１つの追加のサービス検索応答を待ち続けるステップと、
サービス検索応答が正当な応答である場合に、サービス検索応答が肯定の応答または否定の応答のどちらであるのかを判定するステップと、
サービス検索応答が肯定の応答である場合に、サービス検索要求がそこから受信されたノードに向かってターゲット・ノードから肯定のサービス検索応答を開始するステップと、
サービス検索応答が肯定の否定である場合に、すべての期待されるサービス検索応答メッセージがターゲット・ノードによって受信済みであるかどうかを判定するステップと、
期待されるサービス検索応答メッセージの一部がターゲット・ノードによって受信済みではない場合に、少なくとも１つの追加のサービス検索応答を待ち続けるステップと、
期待されるサービス検索応答メッセージのすべてがターゲット・ノードによって受信済みである場合に、サービス検索要求がそこから受信されたノードに向かってターゲット・ノードから否定のサービス検索応答を開始するステップと
をさらに含む、条項１７に記載の方法。
【０２３１】
２２．複数のノードを含むピアツーピア（Ｐ２Ｐ）ネットワーク内でサービスを突き止める装置であって、
Ｐ２Ｐネットワークのターゲット・ノードでサービス検索要求を受信する手段であって、サービス検索要求は、サービスおよびターゲット・ノードに関する検索範囲を示す１つまたは複数の判断基準を含む、手段と、
１つまたは複数のサービス検索判断基準の少なくとも一部を使用して、ターゲット・ノードがサービスをサポートするかどうかを判定する手段と、
ターゲット・ノードがサービスをサポートするとの判定が行われる時に、サービスがターゲット・ノードによってサポートされることを示すサービス検索応答メッセージをターゲット・ノードから開始する手段と、
ターゲット・ノードがサービスをサポートしないとの判定が行われる時に、ターゲット・ノードからＰ２Ｐネットワークの少なくとも１つの他のノードに向かってサービス検索要求を開始すべきかどうかを判定する手段と
を含む装置。
【０２３２】
本発明の教示を組み込まれたさまざまな実施形態を図示し、本明細書で詳細に説明したが、当業者は、それでもこれらの教示を組み込まれた多数の他の変更された実施形態をたやすく考案することができる。
【図１】
0005567683.tif 000005
【図２】
0005567683.tif 000006
【図３】
0005567683.tif 000007
【図４】
0005567683.tif 000008
【図５】
0005567683.tif 000009
【図６】
0005567683.tif 000010
【図７】
0005567683.tif 000011
【図８】
0005567683.tif 000012
【図９】
0005567683.tif 000013
【図１０】
0005567683.tif 000014