(57)【要約】【課題】ネットワークのサービスノードを特定する方法を提供する。【解決手段】ネットワークの第１のノード（５０１）から要求が受信される。この要求は、所望のサービスを提供するように動作可能なサービスノードの要求を含む。グローバル情報テーブルが検索され、第１のノード（５０１）のロケーション情報に少なくとも基づいて所望のサービスを提供するように動作可能な少なくとも１つのサービスノード（５０３、５０４）が特定される。グローバル情報テーブルが、所望のサービスを提供するサービスノードを含まない場合、検索が拡大されて、隣接ノード等の他のノードに記憶されているグローバル情報テーブルからの情報が含められる。【選択図】図５
2008516528.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークの第１のノード（５０１）の所望のサービスを提供する、ネットワークの少なくとも１つのサービスノード（５０３、５０４）を特定する方法であって、
所望のサービスを提供するように動作可能なサービスノードの要求を前記第１のノード（５０１）から受信することと、
前記第１のノード（５０１）のロケーション情報に少なくとも基づいて、前記所望のサービスを提供するように動作可能な少なくとも１つのサービスノード（５０３、５０４）を特定することと
を含む方法。
【請求項２】
前記少なくとも１つのサービスノード（５０３、５０４）と前記第１のノード（５０１）との間の利用可能な帯域幅を測定することと、
該利用可能な帯域幅が、前記サービスを提供するのに必要とされる最小帯域幅よりも大きいことに応じて、前記所望のサービスを提供する前記少なくとも１つのサービスノード（５０３）を選択することと
をさらに含む請求項１に記載の方法。
【請求項３】
前記少なくとも１つのサービスノード（５０３、５０４）は、
前記所望のサービスを提供するように動作可能な複数のサービスノード（５０３、５０４）
を含み、
該少なくとも１つのサービスノード（５０３、５０４）を選択することは、
前記複数のサービスノードの１つ（５０３）の前記利用可能な帯域幅が、前記サービスを提供するのに必要とされる最小帯域幅よりも大きいことと、前記複数のサービスノード（５０３、５０４）のそれぞれが前記第１のノード（５０１）にどれだけ近いかの推定値とに少なくとも基づいて、前記所望のサービスを提供する前記１つのサービスノード（５０３）を選択すること
をさらに含む
請求項２に記載の方法。
【請求項４】
前記所望のサービスを提供するように動作可能な少なくとも１つのサービスノード（５０３、５０４）を特定することは、
前記要求を受信する前記ネットワークの第２のノード（５０２）に記憶されている情報が、前記所望のサービスを提供するように動作可能な少なくとも１つのサービスノード（５０３、５０４）の情報を含むかどうかを判断することであって、前記第２のノード（５０２）に記憶されている前記情報は、前記ネットワークの前記第１のノード（５０１）に物理的に近いノードについての情報を含む、判断することと、
前記所望のサービスを提供するように動作可能な少なくとも１つのサービスノード（５０３、５０４）が特定されるまで、前記所望のサービスを提供するように動作可能なサービスノードの検索を拡大することであって、それによって、前記ネットワークの少なくとも１つの他のノード（５０５）に記憶されている情報を含める、検索を拡大することと
をさらに含む
請求項１に記載の方法。
【請求項５】
前記所望のサービスを提供するように動作可能な少なくとも１つのサービスノード（５０３、５０４）を特定することは、
前記少なくとも１つのサービスノード（５０３、５０４）が複数のサービスノード（５０３、５０４）を含むかどうかを判断することと、
前記少なくとも１つのサービスノード（５０３、５０４）が複数のサービスノード（５０３、５０４）を含むことに応じて、クラスタリングアルゴリズムを適用することであって、それによって、前記複数のサービスノード（５０３、５０４）の内の最も近いサービスノードの１つ又は２つ以上（５０３）を特定する、クラスタリングアルゴリズムを適用することと
をさらに含む
請求項１に記載の方法。
【請求項６】
前記クラスタリングアルゴリズムを適用することは、
該クラスタリングアルゴリズムを適用することに基づいて、前記複数のサービスノード（５０３、５０４）をランク付けすること
をさらに含む
請求項５に記載の方法。
【請求項７】
前記第１のノード（５０１）から複数のグローバルランドマークノード（ＧＬ１、ＧＬ２）及び前記ネットワークにおいて前記第１のノード（５０１）に近接して位置する少なくとも１つのローカルランドマークノード（ＬＬ１）までの距離を測定することと、
該測定された距離に基づいて、前記第１のノード（５０１）のロケーション情報を求めることと
をさらに含む請求項１に記載の方法。
【請求項８】
ピアツーピアネットワーク（９００）に接続するように動作可能であり、該ピアツーピアネットワーク（９００）の分散ハッシュテーブル（ＤＨＴ）オーバーレイネットワーク（６００）におけるＤＨＴノードとして機能するように動作可能であるコンピュータシステム（１０００）であって、
前記ネットワークの第１のノード（５０１）に物理的に近い、前記ピアツーピアネットワーク（９００）の複数のノードのロケーション情報を記憶するように動作可能なメモリ（１００６）と、
前記第１のノード（５０１）の所望のサービスを提供するように動作可能な少なくとも１つのサービスノード（５０３、５０４）を特定するように動作可能なプロセッサ（１００２）と
を備えるコンピュータシステム。
【請求項９】
前記プロセッサ（１００２）は、前記所望のサービスを提供するように動作可能な、該プロセッサ（１００２）によって特定された複数のサービスノード（５０３、５０４）にクラスタリングアルゴリズムを適用するようにさらに動作可能である
請求項８に記載のコンピュータシステム。
【請求項１０】
前記複数のノードの前記ロケーション情報は、
該複数のノードのそれぞれから複数のグローバルランドマークノード（ＧＬ１、ＧＬ２）までの測定された距離及び該複数のノードのそれぞれに近接して位置する少なくとも１つのローカルランドマークノード（ＬＬ１）までの測定された距離
を含む
請求項８に記載のコンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的にはネットワークに関する。より詳細には、本発明はネットワークのサービスノードを特定することに関する。
【０００２】
［関連出願］
本願は、Zhichen Xu他によって２００４年１月３０日に出願された、「Selecting Nodes Close To Another Node In A Network Using Location Information For The Nodes」という発明の名称の同時係属中の米国特許出願第１０／７６７，２８５号の部分継続出願である。
【背景技術】
【０００３】
［背景］
インターネットは、サイズ及び人気がかなり拡大したので、さまざまなサービス及びアプリケーションをユーザに提供するのに使用されている。家具の組み立て方法を実演する短編映画のストリーミング、不動産物件又は景勝地のバーチャルツアー巡り、アーティストのライブパフォーマンスの鑑賞、及びネットワーク化されたマルチユーザコンピュータゲーム又は会議の参加等の多様なアプリケーションがすべてインターネットを介してユーザに利用可能である。
【０００４】
重要な傾向は、ユーザが、多くの視聴者を対象としたサービスを受けることにはもはや満足しないということである。ユーザは、自身の個々のニーズに合ったサービスを要求している。個人化サービスの普及に伴って、今後のネットワークインフラストラクチャが直面する重要な課題は、個別化されたサービスを各ユーザに提供することと、ネットワーク資源を効率的に利用することとの間のトレードオフのバランスを保つことである。
【０００５】
ネットワーク資源及びサービスを効率的に利用する際の根本的な課題は、インターネット等の大きなネットワークにおいて、所望の資源／サービスを効率的且つ迅速に突き止めることである。たとえば、ユーザは、ネットワークにおいて利用可能な特定のメディアコンテンツを見つけるためのクエリーを生成することができる。ロケーション及び距離の推定技法を使用して、所望のメディアコンテンツ等の所望のデータ又はサービスを提供する、ネットワークの最も近いキャッシュ又はプロキシを見つけることができる。
【０００６】
ランドマーククラスタリングは、ネットワークのノードまでの距離を求めるための既知のロケーション及び距離の推定技法である。ランドマーククラスタリングは、大きなネットワークのルーティング用に導入されたものである。ネットワークのノードの物理ロケーションは、ネットワークの共通の一組のランドマークノードまでのそのノードの距離を求めることによって推定される。ランドマーククラスタリングは、２つのノードがランドマークノードまでの同様の距離（たとえば、測定された待ち時間）を有する場合に、それら２つのノードは互いに近い可能性があると仮定する。ルータは、ノードの推定された物理ロケーションを記憶し、この位置情報を使用して最も近いノードへのルーティングを行う。
【０００７】
図１３は、ランドマーククラスタリングを使用したネットワーク１３００のノード１３１０及び１３２０の物理位置の推定を示している。クライアントノード１３１０及び１３２０は、ランドマークノードＬ１３０１及びＬ１３０２までの自身の距離を求める。ノード１３１０及び１３２０は、ランドマークノードＬ１３０１及びＬ１３０２までの同様の距離を有するので、互いに近いと判断される。
【０００８】
ランドマーククラスタリングは、ノードの大まかなロケーション情報を求めるための効率的な技法である。しかしながら、現在のランドマーククラスタリング技法は、誤ったクラスタリングとなる傾向があり、この場合、ネットワーク距離が遠く離れたノードが互いに近くにクラスタリングされる。すなわち、ランドマークノードから遠く離れたノードは、実際には、互いにかなりの距離をおいて位置している場合に、互いに近いロケーションを有するものとして推定される傾向がある。第２に、ランドマーククラスタリングは、粒度の粗い近似であり、距離が比較的近いノード間の区別にはあまり有効ではない。
【特許文献１】米国特許出願公開第２００３／１４７３８６号
【非特許文献１】BANERJEE S他, 「Service adaptive multicast for media destribution networks」 INTERNET APPLICATIONS. WIAPP 2003. PROCEEDINGS. THE THIRD IEEE WORKSHOP ON 2003年6月23-24日, PISCATAWAY, NJ, USA, IEEE, 2003年6月23日, XP010643755 ISBN: 0-7695-1972-5
【非特許文献２】BO SHEN他, 「Semantic-enhanced distribution & adaptation networks」 MULTIMEDIA AND EXPO, 2004. ICME '04. 2004 IEEE INTERNATIONAL CONFERENCE ON TAIPEI, TAIWAN 2004年6月27-30日, PISCATAWAY, NJ, USA, IEEE, vol.2, 2004年6月27日, XP010771175 ISBN: 0-7803-8630-5
【非特許文献３】RATNASAMY S他, 「Topologically-aware overlay construction and server selection」 PROCEEDEINGS IEEE INFOCOM 2002. THE CONFERENCE ON COMPUTER COMMUNICATIONS. 21ST. ANNUAL JOINT CONFERENCE OF THE IEEE COMPUTER AND COMMUNICATIONS SOCIETIES. NEW YORK, NY, 2002年6月23-27日, PROCEEDINGS IEEE INFOCOM. THE CONFERENCE ON COMPUTER COMMUNICA, vol. VOL. 1 OF 3. CONF. 21, 2002年6月23日, XP010593685 ISBN: 0-7803-7476-2
【非特許文献４】ZHICHEN XU他, 「Building topology-aware overlays using global soft-state」 PROCEEDINGS OF THE 23RD. INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS. ICDCS 2003. PROVIDENCE, RI, 2003年5月19-22日, INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS, LOS ALAMITOS, CA: IEEE COMP. SOC, US, vol. CONF. 23, 2003年5月19日,  XP010642320 ISBN: 0-7695-1920-2
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明は、ネットワークのサービスノードを特定する方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
［概要］
一実施の形態によれば、第１のノードの所望のサービスを提供する、ネットワークの少なくとも１つのサービスノードを特定する方法は、所望のサービスを提供するように動作可能なサービスノードの要求を第１のノードから受信すること、及び、第１のノードのロケーション情報に少なくとも基づいて、所望のサービスを提供するように動作可能な少なくとも１つのサービスノードを特定することを含む。
【００１１】
実施の形態の以下の詳細な説明を添付図面と共に検討した時、実施の形態のさまざまな特徴は、実施の形態の以下の詳細な説明についてより良く理解されるので、実施の形態のさまざまな特徴をより十分に理解することができる。
【発明を実施するための最良の形態】
【００１２】
［実施の形態の詳細な説明］
簡単化及び例示の目的のために、実施の形態の原理を説明する。しかしながら、当業者は、同じ原理がすべてのタイプのネットワークシステムに等しく適用可能であり、且つ、すべてのタイプのネットワークシステムにおいて実施できること、及び、このようなどの変形も、実施の形態の真の精神及び範囲から逸脱しないことを容易に認識するであろう。さらに、以下の詳細な説明では添付図面が参照される。添付図面は、特定の実施の形態を示している。実施の形態の精神及び範囲から逸脱することなく、電気的、機械的、論理的、及び構造的な変更を実施の形態に対して行うことができる。
【００１３】
一実施の形態によれば、高度化されたランドマーククラスタリング技法が、ネットワークのノードの物理ロケーションを推定するのに使用される。ノードは、ネットワークを介した別のデバイスへのメッセージの送信及び／又は別のデバイスからのメッセージの受信を行うことができる任意のデバイスである。ノードの物理ロケーションは、本明細書では、ネットワークにおけるノードのロケーションとも呼ばれ、ネットワークの他のノードに対する相対的な、ネットワークにおけるノードのロケーションである。たとえば、ノードのロケーション情報は、グローバルランドマークノード及びそのノードに近接して位置するローカルランドマークノード等、ネットワークの他のノードまでの距離を測定することによって求めることができる。このロケーション情報は、ネットワークにおけるノードの物理ロケーションの推定値として使用することができる。ノードまでの距離は、たとえば、ラウンドトリップ時間又はネットワークホップ等のネットワークメトリックを使用して測定することができる。ノード間の距離及びノードのロケーション情報は、ノード間の地理的距離及びノードの地理的ロケーションと同じでない場合がある。その理由は、距離が、ラウンドトリップ時間又はネットワークホップ等のネットワークメトリックに関して測定されるものであり、キロメートル又はマイル等の地理的距離メトリックに関して測定されるものではないからである。
【００１４】
グローバルランドマークノード及びローカルランドマークノードは、ネットワークのノードからランダムに選択することができる。ネットワークのほぼいずれのノードも、グローバルランドマークノード又はローカルランドマークノードとなるように選択することができる。ローカルランドマークノード及びグローバルランドマークノードとなるように選択されたノードの個数は一般に、ネットワークのノードの総数よりもはるかに少ない。また、ネットワークのグローバルランドマークノードの総数は、一般に、ローカルランドマークノードの個数よりも少ない。ネットワークにおいて使用されるグローバルランドマークノード及びローカルランドマークノードの個数は、ロケーション情報の所望の正確度に依存する場合がある。ネットワークトラフィックを最小にするために、ローカルランドマークノードは、ゲートウェイルータの近く等、ネットワークに戦略的に配置することができる。たとえば、ノードからのメッセージがグローバルランドマークへ向かう途中で遭遇するルータをローカルランドマークノードとして使用することができる。
【００１５】
上述したように、ノードのロケーション情報は、グローバルランドマークノード及びそのノードに近接して位置するローカルランドマークノードまでの距離を測定することによって求めることができる。一実施の形態では、ノードは、ネットワークのグローバルランドマークノード及び近接して位置するローカルランドマークノードのそれぞれまでの距離を測定して、ノードのロケーション情報を求める。一例では、近接して位置するローカルランドマークノードは一般に、グローバルランドマークノードの少なくとも１つよりもノードに近い。たとえば、ローカルランドマークノードは、ノードとグローバルランドマークノードとの間のルーティングパス上に存在する場合がある。この例では、ローカルランドマークノードが、ラウンドトリップ時間を測定するためのプローブパケット等の測定トラフィックに応答できる場合に、これらのローカルランドマークノードまでの距離は、メッセージングのオーバーヘッドをほとんど又はまったく追加することなく取得することができる。すなわち、この例は、グローバルランドマークノードへ送信されるプローブパケットを利用して、グローバルランドマークノードへ向かう途中で遭遇したローカルランドマークノードまでの距離を測定することができるので、ローカルランドマークノードへの距離測定トラフィックを追加して生成する必要はない。別の例では、ローカルランドマークノードが、或るノードまでの所定の距離の範囲内に存在する場合に、ローカルランドマークノードは、そのノードに近接して位置する場合がある。この例では、ノードは、グローバル情報テーブルを使用してそのノードに近接するローカルランドマークノードを特定することができ、次に、その特定されたローカルランドマークノードまでの距離を測定することができる。このように、ローカルランドマークノードは、グローバルランドマークノードへのルーティングパス上に存在しない場合があるが、それでもノードのロケーション情報を正確に求めるのに役立つ場合があり、使用することができる。
【００１６】
従来のランドマーククラスタリング技法と比較して、本実施の形態によるランドマーク技法は、比較的少数のグローバルランドマークノード及びローカルランドマークノードまでの距離を求めることによって正確に推定できるノードの物理ロケーションを提供する。また、ローカルランドマークノードは、ローカルネットワーク特性の正確な情報も提供する。したがって、ローカルネットワーク特性に基づいてルーティングするための最適なパスを選択することができる。
【００１７】
ネットワークのノードのロケーション情報は、さまざまな応用形態に使用することができる。一実施の形態によれば、ロケーション情報は、ネットワークのノードの所望のサービスを提供するサービスノードを見つけるのに使用される。サービスは、入力を操作して出力を生成する機能である。サービスの例には、トランスコード、暗号化、画像修復及び画像解析、エラー訂正、コンテンツの異なる言語への変換等が含まれる。いくつかのサービスは可逆的であり、初期サービスの出力を入力に変換して戻すことができるようになっている。たとえば、暗号化サービスは、暗号化解除も提供することができる。サービスノードは、他のノードにサービスを提供する。ノードは、ネットワークを介してメッセージを送信及び／又は受信できる任意のデバイスである。ノードの例には、ルータ、サーバ、及びＰＤＡ、パーソナルコンピュータ、ラップトップ、携帯電話等のエンドユーザデバイスが含まれる。
【００１８】
ノードは、サービスを受けることを所望する場合があり、したがって、所望のサービスを提供できるサービスノードを特定することが必要な場合がある。ノードのロケーション情報は、所望のサービスを提供するように動作でき、且つそのノードに物理的に近い１つ又は２つ以上のサービスノードを特定するのに使用される。物理的に近いノードとは、各ノードのランドマークベクトルを使用して決定されるような、ネットワークにおいて物理的に近いノードをいう。たとえば、或るしきい値よりも大きな類似度を備えたランドマークベクトルを有するノードは、物理的に近いとみなすことができる。ランドマークベクトルの代わりに、他のタイプのロケーション近接（location proximity）技法を使用してロケーション情報を求めることができ、次に、このロケーション情報を使用して、サービスを要求するノードに極めて近接する初期の一組のサービスノードを特定できることが当業者には明らかであろう。ロケーション情報は、サービスを要求するノードとサービスノードとの間の帯域幅を見積もるのに使用することができる。たとえば、ノードが互いに近いほど、それらノード間の利用可能な帯域幅はより高くなるものと仮定される。また、初期の一組のサービスノードが特定された後、帯域幅測定を行って、所望のサービスの帯域幅要件を満たすのに十分な帯域幅を有するサービスノードを特定することもできる。
【００１９】
所望のサービスを提供するように動作可能な複数のサービスノードが特定された場合、クラスタリングアルゴリズムを使用して、各サービスノードがノードにどれだけ近いかに基づきサービスノードを削減又はランク付けすることができる。たとえば、クラスタリングアルゴリズムは、ノード及びサービスノードのロケーション情報を使用して、サービスノードをランク付けする。ここで、最高ランクのサービスノードは、ノードに最も近いサービスノードである。ランク付けされたサービスノードのリストは、サービスを要求するノードへ送信され、サービスノードの１つが、サービスを提供するように選択される。サービスノードの１つを選択することは、サービスノードのそれぞれとサービスを要求するノードとの間の帯域幅を測定することを含むことができる。たとえば、サービスを提供するのに必要とされる最小帯域幅が求められる。次に、利用可能な帯域幅が、サービスを提供するのに必要とされる最小帯域幅よりも大きなサービスノードが選択される。
【００２０】
図１は、ネットワークのグローバルランドマークノード及びローカルランドマークノードを使用したロケーション情報の生成の一例を示している。グローバルランドマークノード並びにノード１０及び２０に近接するローカルランドマークノードまでの距離を測定することによって、ネットワーク１００のノード１０及び２０のロケーション情報が生成される。たとえば、ノード１０については、グローバルランドマークノードＧＬ１及びＧＬ２までの距離が測定される。ローカルランドマークノードＬＬ１及びＬＬ２までの距離も測定される。ノードまでの距離は、ラウンドトリップ時間（ＲＴＴ）又はネットワークホップ等の既知のネットワークメトリックを使用して測定することができる。たとえば、ノード１０は、グローバルランドマークノードＧＬ１へプローブパケットを送信することができ、このプローブパケットのＲＴＴを測定して、グローバルランドマークノードＧＬ１までの距離を求めることができる。プローブパケットは、たとえば、ＲＴＴ等の１つ又は２つ以上の所定のネットワークメトリックを測定するためにノードによって生成されたパケットである。
【００２１】
グローバルランドマークノードＧＬ１及びＧＬ２並びにローカルランドマークノードＬＬ１及びＬＬ４までの距離を含む、ノード１０のロケーション情報を表すランドマークベクトルが生成される。ノード１０のランドマークベクトルは、＜｛ＧＬ１，ｄ（ｎ，ＧＬ１）｝，｛ＬＬ１，ｄ（ｎ，ＬＬ１）｝，｛ＧＬ２，ｄ（ｎ，ＧＬ２）｝，｛ＬＬ４，ｄ（ｎ，ＬＬ４）｝＞として表すことができる。ここで、ｄはノードｎと各ランドマークノードとの間の距離であり、ｎはロケーション情報が生成されているノードを表す。
【００２２】
同様に、ノード２０のロケーション情報を生成することができる。たとえば、グローバルランドマークＧＬ１及びＧＬ２までの距離が測定される。ローカルランドマークノードＬＬ２及びＬＬ３までの距離も測定される。グローバルランドマークノードＧＬ１及びＧＬ２並びにローカルランドマークノードＬＬ２及びＬＬ３までの距離を含む、ノード２０のロケーション情報を表すランドマークベクトルが生成される。ノード２０のランドマークベクトルは、＜｛ＧＬ１，ｄ（ｎ，ＧＬ１）｝，｛ＬＬ２，ｄ（ｎ，ＬＬ２）｝，｛ＧＬ２，ｄ（ｎ，ＧＬ２）｝，｛ＬＬ３，ｄ（ｎ，ＬＬ３）｝＞として表すことができる。
【００２３】
グローバルランドマークＧＬ１及びＧＬ２までの距離のみを考慮するロケーション推定技法は、ノード１０及び２０が、グローバルランドマークＧＬ１及びＧＬ２までの同様の距離を有するので、ノード１０及び２０が、ネットワーク１００において極めて近接していると結論付ける場合がある。これらのタイプの不正確さは、誤ったクラスタリングとして知られている。ローカルランドマークノードＬＬ１〜ＬＬ４までの距離を考慮することによって、誤ったクラスタリングが最小にされ、ノード１０及び２０のロケーションのより正確な推定値が求められる。
【００２４】
ネットワーク１００は、図示しない多くのローカルランドマークノード及びグローバルランドマークノードを含むことができる。ローカルランドマークノード及びグローバルランドマークノードとなるように選択されたノードの個数は、一般に、ネットワークのノードの総数よりもはるかに少ない。また、ネットワーク１００のグローバルランドマークノードの総数は、一般に、ローカルランドマークノードの個数よりも少ない。ネットワーク１００において使用されるグローバルランドマークノード及びローカルランドマークノードの個数は、ロケーション情報の所望の正確度に依存する場合がある。シミュレーションによれば、正確なロケーション情報を生成するには、たとえば、１０，０００個のノードのネットワークについて１５個のグローバルランドマークノードといった比較的少数のグローバルランドマークノードが必要とされることが示されている。ネットワーク１００のほぼいずれのノードも、グローバルランドマークノード又はローカルランドマークノードとなるように選ぶことができる。たとえば、ネットワークの所定の個数のノードを、グローバルランドマークノード及びローカルランドマークノードとなるようにランダムに選択することができ、それによって、グローバルランドマークノードの個数は、ローカルランドマークノードの個数よりも少なくなる。ネットワークトラフィックを最小にするために、ローカルランドマークノードは、ゲートウェイルータの近く等、ネットワーク１００に戦略的に配置することができる。たとえば、ゲートウェイルータの近くのノードをローカルランドマークノードとなるように選択することができる。
【００２５】
上述したように、ノード１０及び２０は、ノード１０及び２０に近接して位置するローカルランドマークノードまでの距離を測定する。一実施の形態では、ローカルランドマークノードがグローバルノードへのルーティングパス上に存在する場合に、それらローカルランドマークノードは、ノードに近接して位置する。たとえば、ノード１０は、プローブパケットをグローバルランドマークノードＧＬ１へ送信する。ローカルランドマークノードＬＬ１は、グローバルランドマークノードＧＬ１へのルーティングパスＲ１上に存在するので、プローブパケットはローカルランドマークノードＬＬ１に遭遇する。ローカルランドマークノードＬＬ１は、受信確認応答（ＡＣＫ）メッセージをノード１０へ返信する。ノード１０は、たとえば、プローブパケット及びＡＣＫメッセージのＲＴＴを使用して、ローカルランドマークノードＬＬ１までの距離を求める。また、ネットワークトラフィックを最小にするために、プローブパケットは、たとえば、生存時間フィールドと類似したパケットヘッダのフィールドを更新することによって、遭遇したローカルランドマークノードの個数の経過を追うことができる。ローカルランドマークノードは、所定の個数のローカルランドマークノードにすでに遭遇したプローブパケットを受信した場合、ＡＣＫメッセージを送信することなく、そのパケットの転送を単に行う。
【００２６】
別の実施の形態では、ローカルランドマークノードのそれぞれは、グローバルランドマークノードまでの自身の距離を測定して、自身のランドマークベクトルを取得する。これらのランドマークベクトルは、ネットワーク１００のノードに記憶されているグローバル情報テーブルに記憶される。グローバル情報テーブルは、或るノードに近接するローカルランドマークノードを特定するために問い合わせを受ける。たとえば、ノード１０は、ノード１０に近接するローカルランドマークノードＬＬ１及びＬＬ４等のローカルランドマークノードを特定するためにグローバル情報テーブルに問い合わせる。これは、ノード１０との所定の類似度を備えるランドマークベクトルを有するローカルランドマークノードを特定することを含むことができる。ここで、この所定の類似度は、そのノードとランドマークノードとの間の距離しきい値に関係するものである。次に、ノード１０は、ローカルランドマークノードＬＬ１及びＬＬ４までの距離を求める。したがって、ローカルランドマークノードは、グローバルランドマークノードへのルーティングパスに存在してノード１０に近接して位置するとみなされる必要はない。
【００２７】
ネットワーク１００の各ノードは、グローバルランドマークノード及び近接して位置するローカルランドマークノードまでの距離を求めることによって、ランドマークベクトル等のロケーション情報を生成することができる。各ノードは、自身のロケーション情報をグローバル情報テーブルに記憶する。したがって、グローバル情報テーブルは、ネットワークのほぼすべてのノードのランドマークベクトルを含むことができる。
【００２８】
一実施の形態によれば、グローバル情報テーブルは、分散ハッシュテーブル（ＤＨＴ）オーバーレイネットワークを使用して実施される。ＤＨＴオーバーレイネットワークは、ネットワーク１００等の基礎となる物理ネットワークの論理表現である。この論理表現は、他のタイプの機能の中でも、データ配置、情報取り出し、及びルーティングを提供する。ＤＨＴオーバーレイネットワークは、スケーラビリティ、フォールトトレランス、低管理コスト等のいくつかの望ましい特性を有する。本発明の実施の形態で使用することができるＤＨＴオーバーレイネットワークのいくつかの例には、コンテンツアドレス指定可能ネットワーク（content-addressable-network）（ＣＡＮ）、ＰＡＳＴＲＹ、ＣＨＯＲＤ、及び、ＣＡＮの階層バージョンである高速ウェイルーティング（expressway routing）ＣＡＮ（ｅＣＡＮ）が含まれる。ｅＣＡＮオーバーレイネットワークは、２００２年８月２９日に出願された「Expressway Routing Among Peers」という発明の名称の米国特許出願第１０／２３１，１８４号（本願と共通の譲受人を有し、その全体が参照により本明細書に援用される）にさらに記載されている。
【００２９】
ＤＨＴオーバーレイネットワークは、鍵を値にマッピングするハッシュテーブル抽象演算子（hash table abstraction）を提供する。たとえば、データは、オーバーレイネットワークにおいて、（Ｋ１，Ｖ１）等の（鍵，値）の対として表される。Ｋ１は、たとえばＰ＝ｈ（Ｋ１）といったハッシュ関数を使用してオーバーレイネットワークの点Ｐに確定的にマッピングされる。ハッシュ関数の一例は、チェックサム、又は、異なる次元の空間にハッシュするときの空間充填曲線（space filling curve）である。鍵の値の対（Ｋ１，Ｖ１）は、次に、オーバーレイネットワークの点Ｐ、すなわち点Ｐが位置するゾーンを所有するノードに記憶される。同じハッシュ関数がデータを取り出すのに使用される。また、ハッシュ関数は、ＤＨＴオーバーレイネットワークからデータを取り出すのにも使用される。たとえば、ハッシュ関数は、Ｋ１から点Ｐを計算するのに使用される。次に、データが点Ｐから取り出される。
【００３０】
一例では、グローバル情報テーブルは、ＣＡＮオーバーレイネットワークに記憶される。しかしながら、他のタイプのＤＨＴオーバーレイネットワークを使用することもできる。この例では、ノードのランドマークベクトル又はランドマークベクトルの一部は、ノードについての情報を記憶するためのＤＨＴオーバーレイネットワークのロケーションを特定する鍵として使用される。ランドマークベクトルを鍵として使用することによって、基礎となる物理ネットワークにおいて互いに物理的に近いノードについての情報は、ＤＨＴオーバーレイネットワークにおいて互いに近くに記憶され、その結果、ネットワークの所与のノードに近い一組のノードを特定する時に、生成されるトラフィック量は最少となる。
【００３１】
図２は、図２に示す２次元ＣＡＮオーバーレイネットワーク２００の一例を示している。この２次元ＣＡＮオーバーレイネットワーク２００は、基礎となる物理ネットワーク１００の論理表現である。図２に示すノード３０〜５０は、図１に示すネットワーク１００には示されていないが、ノード３０〜５０も、ネットワーク１００に存在することができる。ＣＡＮオーバーレイネットワークは、ｄトーラス上のｄ次元デカルト座標空間を使用して、基礎となる物理ネットワークを論理的に表している。図２は、オーバーレイネットワーク２００における２次元［０，１］×［０，１］デカルト座標空間を示している。ゾーン２１０〜２１４の座標が示されている。このデカルト空間は、ノード１０〜５０によってそれぞれ所有されるＣＡＮゾーン２１０〜２１４に区画されている。オーバーレイネットワークの各ＤＨＴノードはゾーンを所有する。ノード３０及び２０は、ノード１０の隣接ノードであり、ノード４０〜５０及び１０は、ノード２０の隣接ノードである。２つのノードのゾーンが、ｄ−１個の次元に沿って重なり合い、且つ１つの次元に沿って境を接している場合、それら２つのノードは隣接ノードである。たとえば、ゾーン２１０及び２１４は、［０，．５］×［．５，０］に沿って境を接している。ゾーン２１０及び２１３は、１つの次元に沿って境を接していないので、隣接ゾーンではない。
【００３２】
ノード１０〜５０は、それぞれ、そのノードのすぐ隣のノードのぞれぞれのＩＰアドレス及びオーバーレイネットワークにおけるゾーン座標を含み得る座標ルーティングテーブルを保持する。ルーティングテーブルは、ＤＨＴオーバーレイネットワーク２００の隣接ノードを通って送信元ノードから宛先ノードへルーティングを行うのに使用される。ノード２０は、ノード３０によって所有されるゾーン２１４の点Ｐからデータを取り出そうとしているものと仮定する。点Ｐは、ゾーン２１１にも存在せず、またゾーン２１１の隣接ゾーンのいずれにも存在しないので、データの要求は、ノード４０によって所有されるゾーン２１３等の隣接ゾーンを通って、点Ｐが位置するゾーン２１４を所有するノード３０へルーティングされて、データが取り出される。したがって、ＣＡＮメッセージは、ルーティングのために、ハッシュ関数を使用して求められた点Ｐの座標等の宛先座標を含む。
【００３３】
グローバル情報テーブルは、ネットワーク１００のノードについての情報を含み、この情報は、ＤＨＴオーバーレイネットワーク２００のノードに記憶される。グローバル情報テーブルのノードについての情報を記憶するために、ネットワークのグローバルランドマークノードまでの距離及び近接して位置するローカルランドマークノードまでの距離を含む、ノードのランドマークベクトルが鍵として使用されて、そのノードについての情報を記憶するためのＤＨＴオーバーレイネットワークのロケーションが特定される。グローバルランドマークノードまでの距離等、ランドマークベクトル又はランドマークベクトルの一部を鍵として使用することによって、ネットワークにおいて互いに物理的に近いノードについての情報は、ＤＨＴオーバーレイネットワークにおいて互いに近くに記憶される。図３は、ノード１０のランドマークベクトル３１０及びノード２０のランドマークベクトル３２０を含むランドマーク空間３００を示している。ランドマーク空間３００は、ネットワーク１００のノードのランドマークベクトルをマッピングするための空間の論理表現である。ランドマーク空間３００は、グローバル情報テーブルに情報を記憶するためのＤＨＴオーバーレイネットワーク２００のロケーションへのランドマークベクトルのマッピングを図解するために示されている。
【００３４】
ノード１０及び２０のランドマークベクトルのグローバルランドマーク部分は、グローバル情報テーブルに情報を記憶するための、ＤＨＴオーバーレイネットワーク１００にマッピングされるランドマーク空間３００の点を特定するのに使用される。ノード１０のグローバルランドマーク部分は、＜｛ＧＬ１，ｄ（ｎ，ＧＬ１）｝，｛ＧＬ２，ｄ（ｎ，ＧＬ２）｝＞である。ここで、ｄはノードｎからグローバルランドマークノードまでの距離であり、ｎはノード１０又は２０である。ネットワーク１００の各ノードは、各ランドマークベクトルのグローバルランドマーク部分を使用してランドマーク空間にマッピングすることができる。また、ランドマーク空間３００は、２つの次元よりもはるかに大きくすることができる。次元の個数は、ネットワーク１００で使用されるグローバルランドマークノードの個数と等しくすることができる。ノード１０及び２０は、それらノードのランドマークベクトルに基づいてランドマーク空間３００の座標に位置付けされる。したがって、ランドマーク空間３００において互いに近いノードは、物理ネットワーク１００においても近い。
【００３５】
ハッシュ関数は、物理ノードロケーション情報（たとえば、ランドマークベクトル）を、ランドマーク空間３００からオーバーレイネットワーク２００へ変換するために使用され、その結果、ランドマーク空間３００における近い点が、ＤＨＴオーバーレイネットワーク２００における近い点にマッピングされるようになる。図４は、ハッシュ関数を使用して、ランドマーク空間３００のノード１０及び２０の点をオーバーレイネットワーク２００へ変換することを示している。ハッシュ関数は、ノード１０及び２０のランドマーク空間３００における点に対応する、オーバーレイネットワーク２００における点１０'及び２０'を求めるのに使用される。ノード１０及び２０の情報は、点１０'及び２０'が位置するゾーンを所有するノードに記憶される。したがって、ランドマークベクトルのグローバルランドマーク部分をハッシュすることによって、グローバル情報テーブルに、完全なランドマークベクトル及びノードに関連する他の情報等の情報を記憶するための、オーバーレイネットワーク２００のノードが特定される。したがって、グローバル情報テーブルは、ＤＨＴオーバーレイネットワーク２００のノード中に記憶される。ＤＨＴオーバーレイネットワークを使用してランドマークベクトルを記憶することは、Tang他による「Utilizing Proximity Information in an Overlay Network」という発明の名称の米国特許出願第１０／６６６，６２１号（本願と共通の譲受人を有し、その全体が参照により本明細書に援用される）にさらに記載されている。
【００３６】
いくつかの例では、ランドマーク空間の次元の個数は、オーバーレイネットワークの次元の個数よりも大きくすることができる。空間充填曲線を備えるハッシュ関数を使用して、大きな次元空間から小さな次元空間へ点をマッピングすることができる。これも、参照により援用される上記特許出願である米国特許出願第１０／６６６，６２１号に記載されている。
【００３７】
グローバルランドマークノード及び近接して位置するローカルランドマークノードまでの距離を含むランドマークベクトル等、ネットワーク１００のノードのロケーション情報を使用して、所与のノードの最も近いノードを特定することができる。たとえば、図１を参照して、ノード１０は、ユーザによって使用されるクライアントノードであり得る。ノード１０は、グローバルランドマークノード及び近接して位置するローカルランドマークノードまでの距離を含む自身のランドマークベクトルを求める。ノード１０は、近いノードを見つける要求をＤＨＴオーバーレイネットワーク１００にサブミットする。たとえば、ノード１０は、グローバルランドマークノードＧＬ１及びＧＬ２までの距離等の自身のランドマークベクトルのグローバル部分をハッシュして、ＤＨＴオーバーレイネットワーク２００の点を特定する。ノード１０は、特定された点が位置するゾーンを所有するＤＨＴオーバーレイネットワーク２００のノードへ要求を送信する。
【００３８】
ＤＨＴオーバーレイネットワーク１００は、ノード１０に最も近い一組の候補ノードを選択する。たとえば、ノード１０は、ノード５０へ要求を送信するものと仮定する。ノード５０は、ノード１０のランドマークベクトルのグローバルランドマーク部分を使用して、ノード１０に最も近い一組の候補ノードを選択する。たとえば、ノード５０は、ノード１０のランドマークベクトルのグローバルランドマーク部分を、ノード５０に存在するグローバル情報テーブルに記憶されているノードのランドマークベクトルのグローバルランドマーク部分と比較する。このノード５０に存在するグローバル情報テーブルは、ノード５０によって所有されるゾーン２１２内のノード及びノード５０の隣接ノードのランドマークベクトルを含むことができる。
【００３９】
ランドマークベクトル間又はランドマークベクトルのグローバル部分間の類似度の１つの尺度は、２つのランドマークベクトル間の角度の余弦である。たとえばノード１０といったノードのランドマークベクトルに最も類似したランドマークベクトルを候補ノードとして選択することができる。選択される候補ノードの個数は、最も近いノードを見つけるための所望の正確度に基づくことができる。
【００４０】
すべての候補ノードの完全なランドマークベクトル及びノード１０の完全なランドマークベクトルを使用して、ノード５０は、クラスタリングアルゴリズムを適用し、ノード１０に最も近い一組の候補ノードのサブセットを特定する。クラスタリングアルゴリズムは、ロケーション情報間の類似度等の所定の特性に基づいて、初期の一組の値から、値のサブセットを特定するのに使用できる任意のアルゴリズムである。限定ではなく例として以下に説明するクラスタリングアルゴリズムの４つの例は、ｍｉｎ＿ｓｕｍ、ｍａｘ＿ｄｉｆ  ｆ、ｏｒｄｅｒ、及びｉｎｎｅｒ  ｐｒｏｄｕｃｔである。
【００４１】
ｍｉｎ＿ｓｕｍクラスタリングアルゴリズムは、２つのノードｎ及びｃが距離を測定する対象のグローバルランドマークノード及びローカルランドマークノードが十分な個数存在する場合に、それらランドマークノードの１つであるＬが、２つのノードｎとノードｃとの間の最短パス上に位置する可能性があるものと仮定する。ここで、ｎはノード１０等の所与のノードであり、ｃはノード１０に近いと判断された初期の一組の候補ノードの中のノードである。ノードＬの一例は、ノード１０とノード２０との間の最短経路上に位置するグローバルランドマークノードＧＬ１である。
【００４２】
ｍｉｎ＿ｓｕｍの場合、ｄｉｓｔ（ｎ，Ｌ）及びｄｉｓｔ（ｃ，Ｌ）の合計が最小になるべきである。ノードｎ、及び、Ｃとして表される、当該ノードｎの初期の一組の候補ノードについて、ｍｉｎ＿ｓｕｍ（ｎ，Ｃ）は、以下のような方程式１を使用して形式的に定義される。
方程式（１）  ｍｉｎc∈C:L∈L(n,C)（ｄｉｓｔ（ｎ，Ｌ）＋ｄｉｓｔ（ｃ，Ｌ））
【００４３】
方程式１において、Ｃは一組の候補ノードであり、ｃは組Ｃの要素であり、Ｌ（ｎ，ｃ）は、ノードｎ及びｃが測定した対象の共通の一組のグローバルランドマークノード及びローカルランドマークノードである。方程式１を使用すると、候補ノードＣからのノードが、ｄｉｓｔ（ｎ，Ｌ）＋ｄｉｓｔ（ｃ，Ｌ）について最小の距離合計を有する場合、それらのノードは、ノードｎに最も近い最有力候補のサブセットに選択される。同様に、ｍａｘ＿ｄｉｆ  ｆの背後にある仮定は、ｎ及びｃの双方が距離を測定する対象のグローバルランドマークノード及びローカルランドマークノードが十分な個数存在する場合に、ｃがｎからＬへの最短パス上に存在するか、又は、ｎがｃとＬとの間の最短パス上に存在するようなランドマークノードＬが存在する可能性が高いというものである。その場合、ノードｎに最も近い候補ノードのサブセットを特定するのに、ＡＢＳ（ｄｉｓｔ（ｎ，Ｌ）−ｄｉｓｔ（ｃ，Ｌ））を使用することができる。関数ＡＢＳ（ｘ）は、ｘの絶対値を返す。ｍａｘ＿ｄｉｆ  ｆ（ｎ，Ｃ）は、以下のような方程式２を使用して形式的に定義される。
方程式（２）  ｍａｘc∈C:L∈L(n,C)ＡＢＳ（ｄｉｓｔ（ｎ，Ｌ）−ｄｉｓｔ（ｃ，Ｌ））
【００４４】
クラスタリングアルゴリズムの別の例であるｏｒｄｅｒの場合、２つのノードが一組の共通ノードまで同様の距離を有する場合に、それら２つのノードは互いに近い可能性があるとの仮定がなされる。ｏｒｄｅｒクラスタリングアルゴリズムを使用すると、ノードは、グローバルランドマークノードまでの自身のＲＴＴを測定し、グローバルランドマークノードをＲＴＴの増加順にソートする。したがって、各ノードは、グローバルランドマークノードの関連した順序を有する。グローバルランドマークノードの順序が同じ又は類似であるノードは、互いに近いとみなされる。しかしながら、この技法は、同じグローバルランドマークの順序を有するノードを区別することができず、したがって、誤ったクラスタリングとなりがちである。
【００４５】
ノードｎ、ｃ及びＬについて、Ｌが、ノードｎ及びｃのランドマークベクトルに共通の一組のグローバルランドマークノード及びローカルランドマークノードの要素であって、Ｌ∈Ｌ（ｎ，ｃ）として表される場合に、ノードｎのランドマークベクトルにおけるグローバルランドマークの順序は、すべてのノードＬ（ｎ，ｃ）の、ノードｎまでの距離に基づくソートされたリストにおけるグローバルランドマークノードの順序として定義される。グローバルランドマークノードの順序も同様に定義される。したがって、ｏｒｄｅｒ（ｎ，ｃ）は、以下のような方程式３で定義される。
方程式（３）  ｍｉｎΣL∈L(n,c)ＡＢＳ（ｏｒｄｅｒ（Ｌ）ｎ−ｏｒｄｅｒ（Ｌ）ｃ）
【００４６】
クラスタリングアルゴリズムｉｎｎｅｒ＿ｐｒｏｄｕｃｔは、ランドマークノードがノードｎに近い場合に、そのランドマークノードは、ネットワークにおけるノードｎのロケーションのより良い表示を与えることができるものと仮定する。たとえば、ノード１０のランドマークベクトルは、＜｛ＧＬ１，ｄ（ｎ，ＧＬ１）｝，｛ＬＬ１，ｄ（ｎ，ＬＬ１）｝，｛ＧＬ２，ｄ（ｎ，ＧＬ２）｝，｛ＬＬ４，ｄ（ｎ，ＬＬ４）｝＞として表すことができる。ここで、ｄはノード間の距離であり、ｎはノード１０を表す。ｄ（ｎ，ＬＬ１）がｄ（ｎ，ＬＬ４）よりも短い場合、ｄ（ｎ，ＬＬ１）は、ノード１０のランドマークベクトルと候補ノードのランドマークベクトルとを比較する時に、ｉｎｎｅｒ＿ｐｒｏｄｕｃｔクラスタリングアルゴリズムによってより大きな重みを与えられる。ｉｎｎｅｒ＿ｐｒｏｄｕｃｔ（ｎ，ｃ）は、以下のような方程式４で定義される。
方程式（４）  ｍａｘΣL∈L(n,ｃ)（（（１．０／（ｄｉｓｔ（ｎ，Ｌ）2））×（（１．０／（ｄｉｓｔ（ｃ，Ｌ）2）））
【００４７】
上述したランドマーククラスタリングアルゴリズムは、図１に示すノード１０等のノードｎに最も近い初期の一組の候補ノードのサブセットを特定するのに使用できるアルゴリズムの例である。ｋ平均法、主成分分析、潜在的意味インデキシング（latent semantic indexing）等の他の既知のクラスタリングアルゴリズムを使用して、候補ノードのサブセットを選択することもできる。
【００４８】
候補ノードのサブセットが特定された後、当該サブセット内のノードのランドマークベクトルを含むことができるノードのサブセットのリスト等の候補ノードのサブセットは、ノード１０へ送信される。ノード１０は、サブセット内のノードのそれぞれまでの距離を測定して、ノード１０に最も近いノードを選択する。この技法を使用することによって、最も近いノードの特定を所望するノードは、少数のランドマークノードまでの距離を測定する。また、ローカルランドマークノードは、ローカルネットワーク特性の正確な情報を提供し、この正確な情報を使用して、最適なルーティングパスを選択することができる。加えて、クラスタリングアルゴリズムを利用した後、ノードは、クラスタリングアルゴリズムを使用して特定された少数の最有力候補ノードまでの距離を測定する。
【００４９】
所与のノードに最も近いノードを選択する１つのアプリケーションは、ネットワークのノードによって提供される所望のデータ又はサービスを特定するものである。これは、図５に関して示されている。図５は、ノード５０１〜５０６を含むネットワーク５００を示している。ネットワーク５００は、図１に示すネットワーク１００と同様であり、グローバル情報テーブルを記憶するＤＨＴオーバーレイネットワークとして表すことができる。ノード５０６は、ネットワーク５００を介してコンテンツをユーザに提供する。たとえば、ノード５０６は、英語のコンテンツを提供する。ノード５０３及び５０４は、ノード５０６からのコンテンツをドイツ語に変換して、そのコンテンツをドイツ語でユーザに利用可能にするサービスノードであり得る。サービスノードは、サービスをユーザに提供するノードである。この場合、サービスは、ノード５０６からのコンテンツをドイツ語で提供することである。
【００５０】
ノード５０１は、たとえば、ノード５０６からのコンテンツをドイツ語で見たいユーザによって使用される。ノード５０１は、自身のランドマークベクトルと共に、サービスの要求をＤＨＴオーバーレイネットワークにサブミットする。ランドマークベクトルは、ノード５０１のロケーション情報であり、グローバルランドマークノード及びローカルランドマークノードまでの距離を含む。要求をオーバーレイネットワークにサブミットすることは、たとえば、ノード５０１がノード５０２へ要求を送信することを含む。ノード５０２は、ノード５０１のハッシュされたランドマークベクトルが位置するゾーンの所有者の場合があり、したがって、要求はノード５０２へ送信される。ノード５０２は、グローバル情報テーブルを検索して、要求を満たす一組の候補ノードを特定する。要求は、所望のサービスのタイプを含むことに加えて、２つのノードを接続するパスの帯域幅、ノードの現在の負荷、ノードの転送容量等のサービス品質（ＱｏＳ）に関係する他の測定された特性又は求められた特性も含むことができる。この例では、グローバル情報テーブルは、ネットワーク５００のノードのランドマークベクトルを含むことに加えて、ノードによって提供されるサービス及びＱｏＳ特性を含む情報も記憶する。グローバル情報テーブルは、ユーザに所望のサービスを提供することを援助できる他のタイプのデータでポピュレートできることが当業者には明らかであろう。
【００５１】
ノード５０２は、要求を満たす一組のサービスノードを選択する。この選択プロセスは、ノード５０１の所望のサービスを提供できる少なくとも１つのサービスノードをグローバル情報テーブルから特定することを含む。グローバル情報テーブルは、ランドマークベクトル及びネットワークのノードによって提供されるサービス等の情報を含む。グローバル情報テーブルは、ネットワークの１つ又は複数のノードに記憶することができる。複数のノードに記憶される場合、それら複数のノードのそれぞれは、ネットワークにおいて物理的に近い一組のノードの情報を記憶する。たとえば、上述したように、ロケーション情報は、ランドマークベクトル又はランドマークベクトルの一部をハッシュして、自身のランドマークベクトルをハッシュしたノードのロケーション情報を記憶するためのＤＨＴオーバーレイネットワークのノードを特定することによって記憶される。その結果、ＤＨＴオーバーレイネットワークのノードは、分散形式で、ＤＨＴオーバーレイネットワークの基礎となるネットワークにおいて物理的に近いノードのロケーション情報をグローバル情報テーブルに記憶する。したがって、ノード５０１が自身のランドマークベクトルをハッシュして、自身の所望のサービス要求を送信するためのＤＨＴオーバーレイネットワークのロケーションを特定することにより、ノード５０１は、ノード５０１に物理的に近いノードのロケーションを記憶するＤＨＴオーバーレイネットワークのノードへ自身の要求を送信することになる。
【００５２】
要求を受信したノード５０２は、グローバル情報テーブルを検索して、所望のサービスを提供するように動作可能な１つ又は２つ以上のサービスノードを特定する。２つ以上のサービスノードが特定された場合、上述したｍｉｎ＿ｓｕｍクラスタリングアルゴリズム、ｍａｘ＿ｄｉｆ  ｆクラスタリングアルゴリズム、ｏｒｄｅｒクラスタリングアルゴリズム、ｉｎｎｅｒ  ｐｒｏｄｕｃｔクラスタリングアルゴリズム等のクラスタリングアルゴリズムは、特定されたサービスノードのそれぞれがノード５０１にどれだけ近いかのさらなる推定値を提供するために使用されうる。クラスタリングアルゴリズムは、各サービスノードがノード５０１にどれだけ近いかに基づいて、サービスノードのそれぞれをランク付けするのに使用することができる。ノード５０２は、ランク付けされた候補ノードのリストをノード５０１へ送信する。
【００５３】
ノード５０２に記憶されているグローバル情報テーブルが、所望のサービスを提供するサービスノードを含まない場合、検索が拡大されて、ノード５０２の隣接ノード等の他のノードに記憶されているグローバル情報テーブルからの情報が含められる。
【００５４】
この例では、所望のサービスを提供するように動作可能な特定されたサービスノードは、ノード５０３及び５０４を含む。ノード５０１は、所望のサービスを提供するためのサービスノード５０３又は５０４の一方を選択する。受信したリストのサービスノードのすべてが、ノード５０１の所望のサービスを提供するように動作可能であり、ノード５０１は、クラスタリングアルゴリズムを使用して決定されるような、所望のサービスを提供するための最も近いサービスノードを選択することができる。利用可能な帯域幅等の他のファクタも考慮することができる。利用可能な帯域幅は、ネットワークトラフィックを考慮に入れて、ネットワークでデータを送信するのに利用可能な帯域幅である。一定のコンテンツ及びサービスは、データを送信するための最小の利用可能な帯域幅を必要とする場合がある。ノード５０１は、ノード５０３及び５０４のそれぞれに利用可能な帯域幅を測定し、サービスに必要とされる最小帯域幅よりも大きな利用可能帯域幅を有するノードの１つを選択する。サービスに必要とされる最小帯域幅は、あらかじめ決定しておくことができ、変換されたマルチメディアコンテンツ又はトランスコードされたマルチメディアコンテンツ等、サービスによって出力されるデータを送信するのに必要とされる帯域幅を含むことができる。最も近い候補ノード、各候補ノードの現在の負荷、各候補ノードの転送容量等の他のファクタも考慮することができる。
【００５５】
図１に示すネットワーク１００及び図５に示すネットワーク５００は、本発明の原理を図解するために提供された例である。本発明の実施の形態は、数万個のノード等、はるかに大きなネットワークにおいて実施できることが当業者には明らかであろう。さらに、ロケーション情報の正確度を改善するために、より多くの個数のグローバルランドマークノード及びローカルランドマークノードを使用して、ノードのロケーション情報を求めることもできる。
【００５６】
図６は、グローバルランドマークノード及びローカルランドマークノードまでの測定距離を含むロケーション情報を使用して、ルーティングのための最も近いノードを特定することの一例を示している。図６は、図５に示すネットワーク５００のＤＨＴオーバーレイネットワーク６００の一例を示している。ＤＨＴオーバーレイネットワーク６００は、領域６１０〜６１５にノード５０１〜５０６を含む、図２に関して説明したようなＣＡＮオーバーレイネットワークとして示されている。しかしながら、他のタイプのＤＨＴオーバーレイネットワークを使用することもできる。ノード５０１〜５０６のロケーション情報は、図３及び図４に関して説明したように、オーバーレイネットワーク６００のノード５０１〜５０６のグローバル情報テーブルに記憶される。ロケーション情報は、グローバルランドマークノード及びローカルランドマークノードまでの距離を含むランドマークベクトルを含むことができる。
【００５７】
ノード５０１は、ドイツ語のコンテンツ等の個人化サービスをノード５０３に要求するためのメッセージをノード５０３へ送信する。ノード５０３は、ノード５０１が位置するゾーン６１０の隣接ゾーンに存在しないので、ノード５０１は、ノード５０３へルーティングするために、領域６１１等の隣接ゾーンにおいて最も近いノードを特定する。ゾーン６１１において最も近いノードを特定するために、ノード５０３は、領域６１１のノードへ要求を送信する。この要求は、ノード５０１のランドマークベクトル等のロケーション情報を含む。ノード５０１のルーティングテーブルは、要求を送信するための領域６１１の少なくとも１つのノードを含むことができる。要求を受信した領域６１１のノードは、ノード５０１に最も近い、領域６１１の一組の候補ノードを求めて自身のグローバル情報テーブルを検索し、クラスタリングアルゴリズムを適用して、ノード５０１に最も近い候補ノードのサブセットを特定する。ノードのこのサブセットは、ノード５０１へ送信される。
【００５８】
ノード５０１は、サブセットの候補ノードのそれぞれまでの距離を求め、ルーティングのためにノード５０２等の最も近いノードを選択する。ノード５０１は、ルーティングのためのノードを特定する時に、物理ロケーション以外のファクタを考慮することができる。たとえば、ノード５０１は、ＱｏＳ特性も評価することができる。一組の候補ノードのＱｏＳ特性をグローバル情報テーブルに記憶することができる。ノード５０１は、一組の候補ノードから、所望のＱｏＳ特性を有する最も近いノードを選択することができる。ノード５０２が選択されるものと仮定すると、ノード５０２は、ノード５０１から、サービスを提供するノード５０３へサービスの要求を転送する。
【００５９】
図７は、一実施の形態による、ノードのロケーション情報を生成するための方法のフローチャートを示している。図７は、限定ではなく例として、図１に示すネットワーク１００及び図２に示すオーバーレイネットワーク２００に関して説明される。ステップ７０１において、ノード１０は、ネットワーク１００のグローバルランドマークノードまでの距離を求める。たとえば、ノード１０は、ＲＴＴ又は別のネットワークメトリックを使用して、グローバルランドマークノードＧＬ１及びＧＬ２までの距離を測定する。
【００６０】
ステップ７０２において、ノード１０は、ノード１０に近接するローカルランドマークノードまでの距離を求める。これは、グローバルランドマークノードＧＬ１及びＧＬ２までのＲＴＴを測定するプローブパケットが遭遇するローカルランドマークノードＬＬ１及びＬＬ４を含むことができる。別の例では、ノードまでの所定の距離の範囲内にあるすべてのローカルランドマークノードまでの距離が、グローバル情報テーブルを使用して求められる。これは、ノードのランドマークベクトルを比較することによって求めることができる。ランドマークベクトルが所定の類似度を有するノードが、グローバル情報テーブルから選択される。
【００６１】
ステップ７０１及び７０２は、同時に実行することができる。たとえば、ローカルランドマークノードがルーティングパス上に存在する場合、グローバルランドマークノードをプローブすることによって、実質的にメッセージングのオーバーヘッドなしに、対応するローカルランドマークまでの距離が得られる。たとえば、ネットワークのほぼすべてのルータをローカルランドマークノードとして選択することができ、トレースルート又は別の同様のネットワークユーティリティを使用して、グローバルランドマークノードへのルーティングパス上のグローバルランドマークノード及びローカルランドマークノードまでの距離が取得される。この例では、ルーティングパス上のあらゆるルータまでの距離が測定されない場合がある。たとえば、生存時間フィールドが利用される場合があり、その結果、プローブパケットを受信する最初の所定の個数のルータまでの距離しか測定されないようになる。或いは、たとえば、第１のルータ、第２のルータ、第４のルータ、第８のルータ、及び第１６のルータまでの距離が測定される。したがって、グローバルランドマークノードへのルーティングパス上のルータの総数よりも少ない個数のルータまでの距離を測定することができる。
【００６２】
ステップ７０３において、ノード１０のロケーション情報が、グローバルランドマークノード及びローカルランドマークノードまでの距離を使用して生成される。たとえば、グローバルランドマークノードＧＬ１及びＧＬ２までの距離並びにローカルランドマークノードＬＬ１及びＬＬ４までの距離を含む、ノード１０のランドマークベクトルが生成される。
【００６３】
ステップ７０４において、ノード１０は、自身のランドマークベクトル等の自身のロケーション情報をグローバル情報テーブルに記憶する。一例では、これは、ランドマークベクトルのグローバルランドマーク部分をハッシュして、図２に示すＤＨＴオーバーレイネットワーク２００におけるロケーションを特定することを含む。このロケーションは、ノード１０についてのロケーション情報、及び場合によっては提供されるサービス、負荷、転送容量等の他の情報をグローバル情報テーブルに記憶するためのものである。
【００６４】
図８は、一実施の形態による、最も近いノードを特定するための方法８００のフローチャートを示している。図８は、限定ではなく例として、図１に示すネットワーク１００及び図２に示すオーバーレイネットワーク２００に関して説明される。ステップ８０１において、グローバルランドマークノード及び近接して位置するローカルランドマークノードまでの距離を含むランドマークベクトル等のロケーション情報が、ノード１０について求められる。
【００６５】
ステップ８０２において、ノード１０は、ノード１０に最も近いノードを特定するための要求をＤＨＴオーバーレイネットワーク２００へ送信する。たとえば、ノード１０は、グローバルランドマークノードＧＬ１及びＧＬ２までの距離等、自身のランドマークベクトルのグローバル部分をハッシュして、ＤＨＴオーバーレイネットワーク２００における点を特定する。ノード１０は、特定された点が位置するゾーンを所有するＤＨＴオーバーレイネットワーク２００のノードへ要求を送信する。
【００６６】
ステップ８０３において、ＤＨＴオーバーレイネットワーク１００は、ノード１０に最も近い一組の候補ノードを選択する。たとえば、ノード１０は、ノード５０へ要求を送信するものと仮定する。ノード５０は、ノード１０のランドマークベクトルのグローバルランドマーク部分を使用して、ノード１０に最も近い一組の候補ノードを選択する。たとえば、ノード５０は、ノード１０のランドマークベクトルのグローバルランドマーク部分を、ノード５０に存在するグローバル情報テーブルに記憶されているノードのランドマークベクトルのグローバルランドマーク部分と比較する。これは、ノード５０によって所有されるゾーン２１２のノード及びノード５０の隣接ノードのランドマークベクトルを含むことができる。ランドマークベクトル又はランドマークベクトルのグローバル部分が比較されて、ノード１０に最も近い一組の候補ノードが特定される。
【００６７】
ステップ８０４において、ノード５０は、クラスタリングアルゴリズムを一組の候補ノードに適用して、ノード１０に最も近い候補ノードのサブセットを特定する。たとえば、ノード１０のランドマークベクトルは、たとえば、クラスタリングアルゴリズムｍｉｎ＿ｓｕｍ、ｍａｘ＿ｄｉｆ  ｆ、ｏｒｄｅｒ、及びｉｎｎｅｒ  ｐｒｏｄｕｃｔの１つを使用して候補ノードのランドマークベクトルと比較される。
【００６８】
ステップ８０５において、ノード１０は、ステップ８０４で求められた候補ノードのサブセットのリストをノード５０から受信し、ＲＴＴ又はネットワークホップ等のネットワークメトリックを使用して、候補ノードのサブセット内のノードのそれぞれまでの距離を求める。ステップ８０６において、ノード１０は、測定された距離に基づいて、最も近いノードを候補ノードのサブセットから選択する。
【００６９】
ネットワークノードを選択する時に、距離以外のファクタを考慮することができる。たとえば、ノード１０が、特定のデータ又はサービスを提供しているネットワーク１００のノードを特定しようと試みている場合、データの送信又はサービスの配信に影響を与える可能性のあるＱｏＳに関係するファクタを考慮することができる。たとえば、帯域幅、データ又はサービスを供給するノードの現在の負荷、及びノードの転送容量を、一組の候補ノード内のノードのそれぞれについて求めることができる。ノード１０は、最も良いＱｏＳを提供する最も近いノード等、自身のニーズを最も良く満たすノードを候補の組から選択する。同様に、ノード１０が、たとえばオーバーレイネットワークの或る領域へのルーティングを行うために、最も近いノードを特定している場合、ノードの候補の組からノードを選択する時に、帯域幅、転送容量、及びネットワークルーティングに関連した他のファクタを考慮することができる。
【００７０】
図９は、一実施の形態による、所望のサービスを提供するサービスノードを選択するためのフローチャート９００を示している。図９は、限定ではなく例として、図５に示すネットワーク５００に関して説明される。ステップ９０１において、ノード５０２は、図５に示すノード５０１からサービスノードの要求を受信する。一例では、ノード５０１は、ノード５０６からドイツ語で提供されるコンテンツを含むサービスの受信を所望する。ノード５０１は、自身のランドマークベクトルと共に、ネットワーク５００のＤＨＴオーバーレイネットワークへサービスの要求をサブミットする。要求をサブミットすることは、ノード５０１のランドマークベクトル又はランドマークベクトルの一部をハッシュして、オーバーレイネットワークのノードを特定すること、及び、所望のサービスの要求をそのノード（この例ではノード５０２）へ送信することを含むことができる。
【００７１】
ステップ９０２において、ノード５０２は、少なくともノード５０１のロケーション情報に基づいて、ノード５０１の所望のサービスを提供できるネットワーク５００の少なくとも１つのサービスノードを特定する。一例では、ロケーション情報は、ノード５０１のランドマークベクトルを含む。このランドマークベクトルは、方法７００に関して上述したように求められる。ノード５０１のロケーション情報は、ネットワーク５００においてノード５０１に物理的に近いノードであって、所望のサービスを提供するように動作可能なノードを特定するのに使用することができる。たとえば、ノード５０１は、自身のランドマークベクトル又はランドマークベクトルの一部をハッシュして、ネットワーク５００のノード５０１に物理的に近いノードについての情報を自身のグローバル情報テーブルに記憶するノード（この例ではノード５０２）を特定する。ノード５０２に記憶されているグローバル情報テーブルは、所望のサービスを提供するように動作可能な少なくとも１つのサービスノードを特定するために検索される。ノード５０２のグローバル情報テーブルが、所望のサービスを提供するように動作可能なサービスノードを含まない場合、検索を、図１０に関して説明するように他のノードに拡大することができる。また、所望のサービスを提供するように動作可能なサービスノードが２つ以上特定された場合、ノード５０１のロケーション情報及び特定されたサービスノードのロケーション情報を使用し、サービスノードのそれぞれがノードにどれだけ近いかの推定値に基づき、クラスタリングアルゴリズムを使用して、特定されたサービスノードをランク付けすることができる。近さは、ネットワーク５００のノードのランドマークベクトルを求めるために測定された距離に関連している。距離は、たとえば、ラウンドトリップ時間、ホップ数等の待ち時間の関数として測定することができる。
【００７２】
図１０Ａ、図１０Ｂは、ロケーション情報及び利用可能な帯域幅に基づいて、サービスを提供するように動作可能な少なくとも１つのサービスノードを特定するための一実施の形態による方法１０００を示している。図１０は、限定ではなく例として、図５に示すネットワーク５００に関して説明される。ステップ１００１において、ノード５０２は、所望のサービスを提供するように動作可能なサービスノードの要求をノード５０１から受信する。一例では、ノード５０１は、ノード５０６からドイツ語で提供されるコンテンツを含むサービスの受信を所望する。ノード５０１は、自身のランドマークベクトルと共に、ネットワーク５００のＤＨＴオーバーレイネットワークへサービスの要求をサブミットする。要求をサブミットすることは、ノード５０１のランドマークベクトル又はランドマークベクトルの一部をハッシュして、オーバーレイネットワークのノードを特定すること、及び所望のサービスの要求をそのノード（この例ではノード５０２）へ送信することを含むことができる。
【００７３】
ステップ１００２において、ノード５０２は、所望のサービスを提供するように動作可能な少なくとも１つのサービスノードが、ノード５０２に記憶されているグローバル情報テーブルから特定できるかどうかを判断する。特定できない場合、ステップ１００３において、検索が、ネットワーク５００のＤＨＴオーバーレイネットワークにおけるノード５０２の隣接ノード等の他のノードに記憶されているグローバル情報テーブルに拡大される。隣接ノードの例には、図６に示すノード５０３及び５０６が含まれる。所望のサービスを提供するように動作可能なサービスノードがそれでも特定できない場合、検索を、ノード５０４及び５０５等の隣接ノードのさらに隣接ノードに拡大することができる。
【００７４】
ステップ１００４において、ノード５０２は、所望のサービスを提供するように動作可能なサービスノードが複数特定されたかどうかを判断する。複数のサービスノードが特定された場合、ノード５０２は、ステップ１００５において、ノード５０１及びそれら複数のサービスノードのロケーション情報を使用してクラスタリングアルゴリズムを適用する。クラスタリングアルゴリズムは、サービスノードのそれぞれがノード５０１にどれだけ近いかの推定値を提供する。クラスタリングアルゴリズムは、複数のサービスノードをランク付けすることができる。たとえば、複数のサービスノードの最も近いものは、最高ランクにランク付けされ、次に近いものは、次に高いランクにランク付けされる。以下同様にランク付けされる。
【００７５】
図１０Ｂに示すステップ１００６において、ノード５０１は、ステップ１００２、１００４、及び１００５の１つ又は２つ以上においてノード５０１により決定されたような、所望のサービスを提供するように動作可能な少なくとも１つのサービスノードを含むリストをノード５０２から受信する。複数のサービスノードがステップ１００４において特定された場合、クラスタリングアルゴリズムを使用してリストをランク付けすることができる。ステップ１００７において、ノード５０１は、利用可能な帯域幅が、所望のサービスに必要とされる帯域幅よりも大きいことに少なくとも基づいて複数のサービスノードの１つを選択する。たとえば、ノード５０２から受信されたリストは、所望のサービスを提供するように動作可能なノード５０３及び５０４を含む。このリストは、ノード５０３がノード５０４よりもノード５０１に近いことを示している。ノード５０１は、既知の帯域幅測定技法を使用してノード５０３とノード５０１との間の利用可能な帯域幅を測定する。また、ノード５０１は、所望のサービスに必要とされる最小帯域幅も求める。ノード５０１とノード５０３との間の利用可能な帯域幅が、必要とされる最小帯域幅よりも大きい場合には、ノード５０１は、所望のサービスを提供するようにノード５０３を選択する。利用可能な帯域幅が、必要とされる最小帯域幅よりも小さい場合には、ノード５０１は、ノード５０４を選択することができる。ノード５０３及び５０４の双方が有する利用可能な帯域幅が、必要とされる最小帯域幅よりも小さい場合、サービスをノード５０１に提供することができないか、又は、ノード５０１は、最も大きな利用可能帯域幅を有するノードを選択することができる。利用可能な帯域幅に加えて、ノード５０１は、リストからサービスノードを選択する時に他のファクタを考慮することもできる。たとえば、ノード５０１は、そのノードの利用可能な帯域幅が、必要とされる最小帯域幅よりも大きいかどうかを判断する時に、ノード５０１に最も近いと推定されたサービスノードを選択して、そのサービスノードから始めることができる。
【００７６】
方法９００及び１０００では、ロケーション情報を使用して、所望のサービスを提供するように動作可能な初期の一組のサービスノードを特定することができる。たとえば、ステップ９０１及び１００１において、サービスを要求するノードのランドマークベクトルを使用して、サービスを要求するノードに極めて近接するサービスノードを特定することができる。ランドマークベクトルの代わりに、他のタイプのロケーション情報を使用して、サービスを要求するノードに極めて近接するサービスノードを特定できることが当業者には明らかであろう。当該技術分野で既知の他のタイプのロケーション近接技法を使用してロケーション情報を求めることができ、次に、このロケーション情報を使用して、サービスを要求するノードに極めて近接する初期の一組のサービスノードを特定することができる。
【００７７】
ロケーション情報は、サービスを要求するノードとサービスノードとの間の帯域幅を見積もるのに使用することができる。たとえば、ノードが互いに近いほど、それらノード間の利用可能な帯域幅はより高くなるものと仮定することができる。また、初期の一組のサービスノードが特定された後、ステップ１００７において実行されるように、帯域幅測定を行って、所望のサービスの帯域幅要件を満たすのに十分な帯域幅を有するサービスノードを特定することもできる。
【００７８】
図１１は、本発明の一実施の形態による、図１に示すネットワーク１００及び図５に示すネットワーク５００等の基礎となる物理ネットワークが使用できるピアツーピア（Ｐ２Ｐ）通信モデルを示している。Ｐ２Ｐネットワークは、図２に示すＣＡＮ  ＤＨＴオーバーレイネットワーク２００及び図６に示すＣＡＮ  ＤＨＴオーバーレイネットワーク６００等のＤＨＴオーバーレイネットワークの基礎となる物理ネットワークとして共通に使用される。Ｐ２Ｐネットワーク１１００は、Ｐ２Ｐシステムのピアとして機能する複数のノード１１１０ａ〜１１１０ｎを含む。ノード１１１０ａ〜１１１０ｎは、ネットワーク１１２０を介してそれらノード間で情報を交換し、また、他のネットワークノードと情報を交換する。ノード１１１０ａ〜１１１０ｎは、どのノード１１１０ａ〜１１１０ｎが、オブジェクトの検索及び取り出し、オブジェクトの配置、グローバル情報テーブルの記憶及び保持等のＰ２Ｐシステムのピアの他の機能を実行するかを決定することもできる。オブジェクトには、ファイル、ＵＲＬ等が含まれ得る。ノード１１１０ａ〜１１１０ｎは、ネットワークインターフェースを有するコンピュータシステム（たとえば、個人情報端末、ラップトップコンピュータ、ワークステーション、サーバ、及び他の同様のデバイス）であり得る。ノード１１１０ａ〜０１０ｎは、さらに、Ｐ２Ｐ形式で情報（たとえば、データ、アプリケーション等）を共有する能力、及び、ＤＨＴオーバーレイネットワークのノードとして動作する能力を含む、１つ又は２つ以上のソフトウェアアプリケーション（図示せず）を実行するように動作可能であり得る。
【００７９】
ネットワーク１１２０は、ノード１１１０ａ〜１１１０ｎ間に通信チャネルを提供するように動作可能とすることができる。ネットワーク１１２０は、ローカルエリアネットワーク、ワイドエリアネットワーク、又はそれらの組み合わせとして実施することができる。ネットワーク１１２０は、イーサネット（登録商標）、トークンリング等の有線プロトコル、セルラーデジタルパケットデータ、Ｍｏｂｉｔｅｘ、ＩＥＥＥ８０２．１１ｂ、Ｂｌｕｅｔｏｏｔｈ、無線アプリケーションプロトコル、モバイル用グローバルシステム等の無線プロトコル、又はそれらの組み合わせを実施することができる。
【００８０】
ノード１１１０ａ〜１１１０ｎに記憶できる情報の一部が、ノード１１１０ａについて示されている。ノード１１１０ａは、ルーティングテーブル１１３１、グローバル情報テーブル１１３２を記憶し、場合によっては、測定されたＱｏＳ特性を記憶する。
【００８１】
図１２は、図１１に示すＰ２Ｐネットワーク１２００のノードとして使用できるコンピュータシステム１０００の一例示のブロック図を示している。このコンピュータシステム１２００は、ソフトウェアを実行するための実行プラットフォームを提供するプロセッサ１２０２等の１つ又は２つ以上のプロセッサを備える。
【００８２】
プロセッサ１２０２からのコマンド及びデータは、通信バス１２０４を介して通信される。また、コンピュータシステム１２００は、ランタイム中にソフトウェアを実行することができる、ランダムアクセスメモリ（ＲＡＭ）等のメインメモリ１２０６と、２次メモリ１２０８とを備える。２次メモリ１２０８は、たとえば、ハードディスクドライブ１２１０、及び／又は、フロッピー（登録商標）ディスケットドライブ、磁気テープドライブ、コンパクトディスクドライブ等を表す着脱可能ストレージドライブ１２１２、すなわちソフトウェアのコピーを記憶できる不揮発性メモリを含む。また、２次メモリ１２０８は、ＲＯＭ（読み出し専用メモリ）、ＥＰＲＯＭ（消去可能プログラマブルＲＯＭ）、ＥＥＰＲＯＭ（電気的消去可能プログラマブルＲＯＭ）も含むことができる。ソフトウェアに加えて、ルーティングテーブル、グローバル情報テーブル、並びに測定されたＱｏＳ特性、測定された利用可能な帯域幅及びサービスに必要とされる帯域幅もメインメモリ１２０６及び／又は２次メモリ１２０８に記憶することができる。着脱可能ストレージドライブ１２１２は、既知の方法で着脱可能ストレージユニット１２１４から読み出しを行い、且つ／又は、着脱可能ストレージユニット１２１４へ書き込みを行う。
【００８３】
ユーザは、キーボード、マウス、スタイラス等の１つ又は２つ以上の入力デバイス１２８を用いてコンピュータシステム１２００とインターフェースする。ディスプレイアダプタ１２２２は、通信バス１２０４及びディスプレイ１２２０とインターフェースし、プロセッサ１２０２から表示データを受信して、その表示データをディスプレイ１２２０の表示コマンドに変換する。ネットワークインターフェース１２３０は、図９に示すネットワーク９２０を介して他のノードと通信するために設けられている。また、センサ１２３２は、転送容量、負荷、帯域幅等を含み得る、ノードのＱｏＳ特性を測定するために設けられている。
【００８４】
方法７００、８００、９００、及び１０００のステップの１つ又は２つ以上は、メモリ１００６及び／又は１００８等のコンピュータ可読媒体に組み込まれたソフトウェアとして実施することができ、たとえばプロセッサ１２０２によってコンピュータシステム１０００で実行することができる。これらのステップは、コンピュータプログラムによって具現することができ、コンピュータプログラムは、アクティブ又は非アクティブの双方のさまざまな形態で存在することができる。たとえば、ステップは、ソースコード、オブジェクトコード、実行可能コード、又はステップのいくつかを実行するための他のフォーマットのプログラムコードのプログラム命令で構成されるソフトウェアプログラム（複数可）として存在することができる。上記のいずれも、圧縮形式又は非圧縮形式のストレージデバイス及び信号を含むコンピュータ可読媒体上に具現することができる。
【００８５】
適したコンピュータ可読ストレージデバイスの例には、従来のコンピュータシステムのＲＡＭ（ランダムアクセスメモリ）、ＲＯＭ（読み出し専用メモリ）、ＥＰＲＯＭ（消去可能プログラマブルＲＯＭ）、ＥＥＰＲＯＭ（電気的消去可能プログラマブルＲＯＭ）、及び磁気ディスク若しくは磁気テープ又は光ディスク若しくは光テープが含まれる。コンピュータ可読信号の例は、搬送波を使用して変調されていようといまいと、インターネット又は他のネットワークを通じてダウンロードされた信号を含めて、コンピュータプログラムをホスティング又は実行するコンピュータシステムがアクセスするように構成され得る信号である。上記の具体例は、ＣＤ  ＲＯＭ上へのプログラムの配布又はインターネットのダウンロードを介したプログラムの配布を含む。或る意味で、抽象的なエンティティとして、インターネット自体がコンピュータ可読媒体である。同じことはコンピュータネットワーク一般にも当てはまる。したがって、以下に列挙される機能は、上述した機能を実行できるどの電子デバイスも実行できることが理解されるべきである。
【００８６】
ソフトウェアが実行できるステップのいくつかの例には、距離を求めてロケーション情報を生成するためのステップが含まれ得る。たとえば、ソフトウェアは、他のハードウェアを使用して、グローバルランドマークノードまでのＲＴＴを測定するためのプローブパケットを生成して距離を求めるようにプロセッサ１００２に指令する。別の例では、ソフトウェアは、所定の近接範囲内のローカルランドマークノードを特定するためのグローバル情報テーブルへの要求を生成して、それらのローカルランドマークノードまでの距離を測定することができる。ソフトウェアは、ＤＨＴオーバーレイネットワークを実施するための命令、及び、ランドマークベクトルをハッシュすることによってＤＨＴオーバーレイネットワークのグローバル情報テーブルに情報を記憶するための命令を含む。また、最も近いノードを特定するための方法８００のステップの一部又は全部も、コンピュータシステム１０００のソフトウェアを使用して実行することができる。方法９００及び１０００では、少なくとも１つのサービスノードの特定をソフトウェアによって実行することができる。加えて、方法９００では、少なくとも１つのサービスノードの検索、クラスタリングアルゴリズムの適用、及びサービスノードの選択も、ソフトウェアによって実行することができる。
【００８７】
本明細書で説明する他のステップもソフトウェアによって実行できることが当業者には容易に明らかであろう。たとえば、図１２に示すコンピュータシステム１２００は、ローカルランドマークノードとして選択された場合、ノードへ返信されるＡＣＫメッセージを生成することによって、受信したプローブパケットに応答することができる。したがって、プローブパケットを送信したノードは、近接して位置するランドマークノードまでの距離を求めることができる。
【００８８】
実施の形態を例に関して説明してきたが、当業者は、真の精神及び範囲から逸脱することなく、説明した実施の形態に対してさまざまな変更を行うことができる。たとえば、本明細書で説明したようにロケーション情報を記憶する利点は、情報記憶、負荷バランシング、輻輳制御、サービス品質（ＱｏＳ）保証の適合、ストレージ容量及び転送容量における不均一性の利用等、多くの応用形態に適用できることが当業者には明らかであろう。本明細書で使用された用語及び説明は、単なる例示としてのみ述べられており、限定を意味するものではない。特に、方法は例によって説明されているが、それら方法のステップは、図示したものとは異なる順序で実行してもよく、又は同時に実行してもよい。当業者は、添付の特許請求の範囲及びその均等物において規定される精神及び範囲内においてこれらの変形及び他の変形が可能であることを認識するであろう。
【図面の簡単な説明】
【００８９】
【図１】一実施の形態による、ネットワークのグローバルランドマークノード及びローカルランドマークノードを使用したロケーション情報の生成を示す図である。
【図２】一実施の形態による、図１に示すネットワークの２次元ＣＡＮオーバーレイネットワークを示す図である。
【図３】一実施の形態による、ランドマークベクトルを含むランドマーク空間を示す図である。
【図４】一実施の形態による、ハッシュ関数を使用して、図３に示すランドマーク空間の点を、図２に示すようなオーバーレイネットワークへ変換することを示す図である。
【図５】一実施の形態による別のネットワークを示す図である。
【図６】一実施の形態による、図５に示すネットワークのオーバーレイネットワークを示す図である。
【図７】一実施の形態による、ネットワークのノードのロケーション情報を求めるための方法のフローチャートである。
【図８】一実施の形態による、所与のノードに最も近いノードを求めるための方法のフローチャートである。
【図９】一実施の形態による、少なくとも１つのサービスノードを特定するための方法のフローチャートである。
【図１０Ａ】一実施の形態による、サービスを要求するノードのロケーション情報及び利用可能な帯域幅の１つ又は２つ以上に基づいて、少なくとも１つのサービスノードを特定するための方法のフローチャートである。
【図１０Ｂ】一実施の形態による、サービスを要求するノードのロケーション情報及び利用可能な帯域幅の１つ又は２つ以上に基づいて、少なくとも１つのサービスノードを特定するための方法のフローチャートである。
【図１１】一実施の形態によるピアツーピアシステムを示す図である。
【図１２】一実施の形態による、図１１に示すピアツーピアシステムのノードとして動作することができるコンピュータシステムを示す図である。
【図１３】従来のランドマーククラスタリング方式を示す図である。
【符号の説明】
【００９０】
１００・・・ネットワーク
１０，２０・・・ノード
２００・・・２次元ＣＡＮオーバーレイネットワーク
２１０〜２１４・・・ゾーン
３０〜５０・・・ノード
３００・・・ランドマーク空間
３１０，３２０・・・ランドマークベクトル
５００・・・ネットワーク
５０１〜５０６・・・ノード
６００・・・ＤＨＴオーバーレイネットワーク
６１０〜６１５・・・領域
１１００・・・Ｐ２Ｐネットワーク
１１１０ａ，１１１０ｂ，１１１０ｃ，１１１０ｄ，１１１０ｎ・・・ノード
１１２０・・・ネットワーク
１１３１・・・ルーティングテーブル
１１３２・・・グローバル情報テーブル
１１３３・・・ＱｏＳ
１２００・・・Ｐ２Ｐネットワーク
１２０２・・・プロセッサ
１２０４・・・通信バス
１２０６・・・メインメモリ
１２１０・・・ハードディスクドライブ
１２１２・・・着脱可能ストレージドライブ
１２１４・・・着脱可能ストレージユニット
１２１８・・・入力デバイス
１２２０・・・ディスプレイ
１２２２・・・ディスプレイアダプタ
１２３０・・・ネットワークインターフェース
１２３２・・・センサ
【図１】
2008516528.tif 000003
【図２】
2008516528.tif 000004
【図３】
2008516528.tif 000005
【図４】
2008516528.tif 000006
【図５】
2008516528.tif 000007
【図６】
2008516528.tif 000008
【図７】
2008516528.tif 000009
【図８】
2008516528.tif 000010
【図９】
2008516528.tif 000011
【図１０Ａ】
2008516528.tif 000012
【図１０Ｂ】
2008516528.tif 000013
【図１１】
2008516528.tif 000014
【図１２】
2008516528.tif 000015
【図１３】
2008516528.tif 000016
【国際調査報告】
2008516528.tif 000017
2008516528.tif 000018
2008516528.tif 000019