説明

ピアツーピアネットワークを分解して、分解されたピアツーピアネットワークを使用するための方法および装置

P2Pネットワークを複数のサブネットワークに分解して、分解されたP2Pネットワークをさらに使用するための機能が提供される。P2Pネットワークは、複数のサブネットワークを形成するために分解され、この場合、サブネットワークのそれぞれは、P2Pネットワークである。P2Pネットワークは、1つまたは複数の分解基準(例えば、地理的位置、関心共同体など、ならびにそれらの様々な組合せ)に基づいて、サブネットワークに分解され得る。P2Pネットワークの分解は、ネットワークマップ内で符号化される。ノードは、分解されたP2Pネットワークに参加するために、ネットワークマップを使用することが可能である。ノードは、サブネットワークのうちの1つに参加することが可能であり、それらのうちのいくつかに参加することが可能であり、またはそれらのすべてに参加することも可能である。分解されたP2Pネットワークのサブネットワークは、任意の適切な数の階層レベル内で構成され得る。

【発明の詳細な説明】
【技術分野】
【0001】
本出願は、2009年12月17日に出願され、その全体が参照により本明細書に明示的に組み込まれている、「METHOD AND APPARATUS FOR LOCATING SERVICES WITHIN PEER−TO−PEER NETWORKS」という表題の米国特許出願第12/640,072号(整理番号第Chu19−43号(ALU/130209))に関する。
【0002】
本発明は、ピアツーピア(P2P)ネットワークの分野に関し、より詳細には、排他的ではないが、P2Pネットワークをサブネットワークに分割することに関する。
【背景技術】
【0003】
ファイル共有は、かなりの期間、徹底的な研究および草の根的な使用の焦点であり続けてきた。ファイル共有は、特にそのために設計され、かつそれに関連するファイル共有プロトコルを有する、異なるファイル共有システムとして実施されるファイル共有手法によって可能にされる。Napsterに始まり、次いで、gnutella、Kazaa、eDonkey、Winy、およびBitTorrentなど、異なるファイル共有システムのいくつかの生成に続く、いくつかの異なるファイル共有システムが実施されている。これらのファイル共有システムに加えて、ShareおよびPerfect Darkなどの新しいシステムも開発されている。これらのファイル共有システムおよび関連するプロトコルは、集合的に、ピアツーピア(P2P)ファイル共有システム/ピアツーピア(P2P)ファイル共有プロトコル、または、さらに簡単には、P2Pファイル共有アプリケーションと呼ばれる。さらに、P2Pファイル共有アプリケーションに加えて、構造上、P2Pファイル共有アプリケーションと異なる、新しいクラスのP2Pアプリケーション、すなわち、P2Pテレビジョン(P2PTV)が出現している。
【0004】
P2Pファイル共有の需要は、最近のトラフィック研究から明らかである。例えば、Ellacoya Networkによる、合衆国内のブロードバンドユーザ100万人の最近のトラフィック研究は、主なトラフィックタイプの容量ごとの内訳が以下のようであることを示している:すなわち、ウェブ(HTTP)が46%、ピアツーピア(P2P)が37%、ニュースグループが9%、非HTTPストリーミングビデオが3%、ゲームが2%、ボイスオーバIP(VoIP)が1%、その他が1%である。HTTPトラフィックの量が高い主な理由は、上記の研究における総トラフィックの9.8%を占める、YouTubeからのトラフィックなど、埋込み型ビデオストリーミングトラフィックである。しかし、P2Pファイル共有は、依然としてトラフィックの大きな割合を担当し、P2PTVの出現に伴い、トラフィックの量は劇的に増大することが予測される。
【0005】
既存のP2Pアプリケーションの大部分はファイル共有を必要とするが、ファイル共有を必要とする既存のP2Pアプリケーションの大部分は、少なくとも当初、完全にピアツーピアではなかった。むしろ、大部分の既存のP2Pアプリケーションは、当初、P2Pネットワークのメンバ同士の間の活動を調整するためにセントラルサーバを利用した。例えば、bitTorrentでは、情報の異なる断片のダウンロードはピアツーピアであったが、bitTorrentアプリケーションの活動を調整するために、bitTorrentにおいてトラッカと呼ばれる集中サーバが使用された。同様に、例えば、NapsterおよびeDonkeyなど、ファイル共有を必要とする多くのその他のP2Pアプリケーションは、類似の特性も有していた。しかし、セントラルサーバの使用は、輻輳および障害に対して既存のP2Pアプリケーションを脆弱にし、さらに、セキュリティの脅威に対して既存のP2Pアプリケーションを魅力的なターゲットにする。
【0006】
P2Pアプリケーションにおける集中サーバの使用に関連する課題を取り除くために、P2Pアプリケーションと共に集中サーバを使用する必要を除去するための新しい技術が提案されている。これらの技術のうち最も需要があるのは、分散ハッシュテーブル(DHT)である。DHTでは、それぞれのオブジェクトは、関連するMビットオブジェクト識別子によって識別される。オブジェクトのオブジェクト識別子は、コンシステントハッシュ関数(consistent hash fucntion)を使用したオブジェクト名のハッシュされた値を計算することによって取得される(例えば、オブジェクト識別子=f(オブジェクト名、この場合、fはコンシステントハッシュ関数である)。ハッシュ関数のMビット出力フィールドは、通常、鍵空間と呼ばれ、ハッシュ関数はこの鍵空間を介してオブジェクトを均一にマッピングする。Chord、Pastry、Tapestryなど、DHT技術に基づく、いくつかの異なるP2Pアーキテクチャが存在し、Chordは、最も需要があるDHTベースのP2Pアーキテクチャである。例えば、bitTorrentおよびeDonkeyは両方ともDHTをサポートする。
【0007】
P2Pネットワークでは、設計目標のうちの1つは、多数のノードに対処することであるが、同時に、ノードのそれぞれの探索表は比較的小さくなければならない。DHTを使用すると、この目標は、探索要求が、必要に応じて、いくつかのノードを通じてその最終的な目標に最終的に経路指定されることになるように、ノードのそれぞれにおける探索表が協調的な形で構築される分散型探索方式を使用することによって達成される。一般に、それぞれのDHT技術は、一般に、ノード内の探索表の構成を示し、ノードがどのようにネットワークに参加するか、およびネットワークを退去するかをさらに指定する、その独自のジオメトリを定義する(例えば、Chordネットワークはリングとして構成される)。一般に、ノードがネットワークに参加するとき、ノードはその存在をその近隣ノードに公示して、その探索表を作成して、ポピュレートし(populate)、そのノードが担当するファイルを取得する。一般に、ノードがネットワークを退去するとき、ノードはそのノードの退去を反映するためにその近隣ノードを更新できるように、その近隣ノードに知らせなければならず、そのノードが担当する任意のファイルを転送しなければならない。ノードは、一般に、やはり、そのそれぞれの近隣に管理メッセージおよび制御メッセージを周期的に送信する。
【発明の概要】
【発明が解決しようとする課題】
【0008】
不利なことには、Chordなど、大部分のDHT技術において、ノードの物理的な位置(または、ノード同士の間の距離)は、アーキテクチャにおいて明らかにされない。結果として、メッセージおよび情報、例えば、ノードの参加手順/退去手順に関連する状況メッセージおよびファイル転送、近隣のノード同士の間で交換される状況メッセージおよび制御メッセージ、ファイル探索に関連する探索メッセージなどは、遥かな地理的距離を横断する場合がある。さらに、Pastryなど、少なくともいくつかのDHT技術は、近接性基準(proximity metrics)を使用して、ノード同士の間の「距離」の概念を組み込むことを試みるが、これらのDHT技術は、これらの技術に関連する不利点を依然として有する。すなわち:(1)特に、大型のネットワークの場合、使用しやすい近接性基準を画定することは困難であること、および(2)近接性基準は、三角不等式を満たす距離基準でなければならないが、ネットワークホップなど、需要がある基準の大部分は三角不等式を満たすことができないことである。
【課題を解決するための手段】
【0009】
先行技術の様々な欠陥が、P2Pネットワークが複数のサブネットワークに分解されるピアツーピア(P2P)ネットワーク分解機能をサポートする実施形態によって対処される。複数のサブネットワークを含む、分解されたP2Pネットワークを形成するために、P2Pネットワークを分解して、分解されたP2Pネットワークをさらに使用するための機能が提供される。P2Pネットワークは、複数のサブネットワークを形成するために分解され、この場合、サブネットワークのそれぞれは、P2Pネットワークである。P2Pネットワークは、1つまたは複数の分解基準(例えば、地理的位置、関心共同体(community of interest)など、ならびにそれらの様々な組合せ)に基づいて、サブネットワークに分解され得る。P2Pネットワークの分解は、ネットワークマップ内で符号化される。ノードは、分解されたP2Pネットワークに参加するために、ネットワークマップを使用することも可能である。ノードは、サブネットワークのうちの1つに参加することが可能であり、それらのうちのいくつかに参加することが可能であり、またはそれらのすべてに参加することが可能である。分解されたP2Pネットワークのサブネットワークは、任意の適切な数の階層レベルで構成され得る。
【0010】
本明細書の教示は、添付の図面と共に、以下の詳細な説明を考慮することによって容易に理解されよう。
【図面の簡単な説明】
【0011】
【図1】ある例示的なChordネットワークを示す図である。
【図2】図1の例示的なChordネットワークの制御ネットワークおよび5つのサブネットワークへのある分解を示す図である。
【図3】ファイルを分解されたP2Pネットワーク内に記憶させる際にノードによって使用するための方法の一実施形態を示す図である。
【図4】分解されたP2Pネットワーク内に記憶されたファイルを位置特定する際にノードによって使用するための方法の一実施形態を示す図である。
【図5】分解されたP2Pネットワークのサブネットワークに参加する際にノードによって使用するための方法の一実施形態を示す図である。
【図6】分解されたP2Pネットワークを退去する際にノードによって使用するための方法の一実施形態を示す図である。
【図7】分解されたP2Pネットワークのネットワークマップ内の変更に基づいて、変更を実行する際にノードによって使用するための方法の一実施形態を示す図である。
【図8A】ファイルが第1のサブネットワークから第2のサブネットワークに転送され得るプロセスを示す一例を示す図である。
【図8B】ファイルが第1のサブネットワークから第2のサブネットワークに転送され得るプロセスを示す一例を示す図である。
【図8C】ファイルが第1のサブネットワークから第2のサブネットワークに転送され得るプロセスを示す一例を示す図である。
【図8D】ファイルが第1のサブネットワークから第2のサブネットワークに転送され得るプロセスを示す一例を示す図である。
【図8E】ファイルが第1のサブネットワークから第2のサブネットワークに転送され得るプロセスを示す一例を示す図である。
【図9】分解されたChordネットワーク内でChordサブネットワークを初期化するとき、第1のサブネットワークのノードが第2のサブネットワークからファイルを獲得するのを可能にするための方法の一実施形態を示す図である。
【図10】本明細書で説明される機能を実行する際に使用するのに適した汎用コンピュータのハイレベルブロック図である。
【発明を実施するための形態】
【0012】
理解を促すために、可能な場合、図面に共通の同一の要素を指すために同一の参照番号が使用されている。
【0013】
ピアツーピア(P2P)ネットワーク分解機能が本明細書で示され、説明される。P2Pネットワーク分解機能は、複数のサブネットワークを含む、分解されたP2Pネットワークを形成するために、P2Pネットワークが分解されることを可能にし、この場合、サブネットワークのそれぞれは、P2Pネットワークとしても動作する。P2Pネットワーク分解機能は、分解されたP2Pネットワークを使用することを可能にする。
【0014】
本明細書では、主に、Chordネットワークに関して示され、説明されているが、P2Pネットワーク分解機能は、Pastryネットワーク、Tapestryネットワークなど、ならびにそれらの組合せなど、任意の適切なP2P技術を利用する任意のP2Pネットワークを分解するために利用され得る。
【0015】
図1は、例示的なChordネットワークのハイレベルブロック図を示す。図1に示されるように、例示的なChordネットワーク100は、リング構成で論理的に構成された複数のノード110を含む。ノード110は、それぞれ、ノード110間で共有され得るファイルを記憶する。ノード110は、Chordネットワーク内に参加できる任意の適切なタイプのノードを含む。例えば、ノード110は、コンピュータ、電話などを含むことが可能である。ノード110はそれぞれ、本明細書で示され、説明されるP2Pネットワーク分解機能の様々な機能を提供するように構成される。P2Pネットワーク分解機能を使用した、Chordネットワーク100の分解は、図1の例示的なChordネットワーク100に関して、Chordネットワークの一般的な動作をまず考慮することによってより良好に理解されよう。
【0016】
Chordでは、Chordネットワークのノードは、(例えば、IPネットワークまたは任意のその他の適切なネットワークなど)パケットベースのネットワークを経由したネットワーク接続性を有し、Chordは、基本的なパケットベースのネットワークを介してオーバーレイネットワークを形成する。
【0017】
Chordでは、Chordネットワークに参加できるノードの数は、Chordネットワークの鍵空間(アドレス空間)のサイズに基づく。一般に、鍵空間はMビットであり、この場合、Mは、任意の適切な数であってよい。例えば、Chordネットワークで使用される一般的な鍵空間は、160ビット実装形態を使用して提供され、鍵空間のサイズは、2160または約1.451048に等しくされる。入力を160ビット値にマッピングするために(すなわち、入力を鍵空間にマッピングするために)コンシステントハッシュ関数が使用される。ハッシュ関数からの出力は、鍵空間上に均一にマッピングされる。セキュアハッシュアルゴリズム(SHA−1)、メッセージダイジェストアルゴリズム5(MD5)など、任意の適切なハッシュ関数が使用され得る点を理解されよう。ハッシュ関数の出力は、鍵空間上にマッピングされるとき、Chordネットワーク内のノードを論理的に構成するために使用されるノードIDのセットを提供する。
【0018】
Chordでは、アクティブノード(Chordネットワークに参加している既存のノード)および非アクティブノード(Chordネットワークに参加できる潜在的なノード)は、ノードのノードIDの順序で円形に論理的に構成される。Chordは、ラップアラウンドを伴って、ノードID値が増大する方向に円の形で順序を課す。Chordでは、Chordネットワークのアクティブノード同士の間の接続性は、円内のアクティブノードの隣接するノード同士の間の論理接続性である(非アクティブノードはChordネットワークに接続されないため、したがって、アクティブノードとしてChordネットワークに参加できる潜在的なノードに過ぎない)。このように、Chordネットワーク内のターゲットアクティブノードから見ると、(1)ターゲットノードのノードIDを超えるノードIDを有する、円上の次のアクティブノードがターゲットアクティブノードの後任であり、(2)ターゲットノードのノードID未満のノードIDを有する、円上の次のアクティブノードがターゲットアクティブノードの前任である。
【0019】
図1では、Chordネットワークの鍵空間は(ノードID0からノードID63に、右回りに、連続的に番号付された64個のノードを提供する)6ビットである。図1では、ノード0、2−3、5−7、9、12−13、16−24、26、29−30、32、34−35、37、41、43、45、49、51、53−54、56−58、および62がアクティブであり、残りのノードは非アクティブである(分かりやすくするために、アクティブノードと非アクティブノードの両方が表示されている)。図1では、Chordネットワーク100のアクティブノード同士の論理的な接続性は、ノード0がノード2に接続され、ノード2がノード3に接続され、ノード3がノード5に接続され、以下同様であり、ノード62がノード0に接続されて、円が完了していることを示す。Chordは、ラップアラウンドを伴って、右回り方向に増大値を使用して円の形で順序を課すため、ノード2は、ノード0の後任と呼ばれ、ノード62は、ノード0の前任と呼ばれ、ノード3は、ノード2の後任と呼ばれ、ノード0は、ノード2の前任と呼ばれ、以下同様である。
【0020】
本明細書で説明されるように、Chordネットワークは、ファイル共有をサポートし、この場合、共有されることになるそれぞれのファイルは、Chordネットワークの1つまたは複数のアクティブノード上に記憶される。Chordでは、ファイルのファイル名は、Chordネットワークのノードを識別するために使用される同じハッシュ関数を使用して、Chordネットワークのノードを識別するために使用される同じ鍵空間内にハッシュされる。ファイル名をハッシュすることからハッシュされた出力は、そのファイルに関するファイル識別子である。したがって、160ビットの鍵空間を有するChordネットワークの場合、例えば、Chordネットワークは、1.451048個のファイルに潜在的に対処することが可能である。Chordでは、ファイルは、そのノードがアクティブな場合、そのファイルのファイルIDにマッチするノードIDを有するノードに記憶され、そのノードがアクティブでない場合、そのファイルは、そのファイルIDを超えるノードIDを有する第1のアクティブノードに記憶される。
【0021】
図1では、Chordネットワーク100は、以下に記憶されることになる64個の全ファイルに対処することが可能である:すなわち、ノード0はファイル0および63を記憶し、ノード2はファイル1および2を記憶し、ノード3はファイル3を記憶し、ノード5はファイル4および5を記憶し、ノード6はファイル6を記憶し、ノード7はファイル7を記憶し、ノード9はファイル8および9を記憶し、ノード12はファイル10、11、および12を記憶し、ノード13はファイル13を記憶し、ノード16はファイル14、15、および16を記憶し、ノード17はファイル17を記憶し、ノード18はファイル18を記憶し、ノード19はファイル19を記憶し、ノード20はファイル20を記憶し、ノード21はファイル21を記憶し、ノード22はファイル22を記憶し、ノード23はファイル23を記憶し、ノード24はファイル24を記憶し、ノード26はファイル25および26を記憶し、ノード29はファイル27、28、および29を記憶し、ノード30はファイル30を記憶し、ノード32はファイル31および32を記憶し、ノード34はファイル33および34を記憶し、ノード35はファイル35を記憶し、ノード37はファイル36および37を記憶し、ノード41はファイル38、39、40、および41を記憶し、ノード43はファイル42および43を記憶し、ノード45はファイル44および45を記憶し、ノード49はファイル46、47、48、および49を記憶し、ノード51はファイル50および51を記憶し、ノード53はファイル52および53を記憶し、ノード54はファイル54を記憶し、ノード56はファイル55および56を記憶し、ノード57はファイル57を記憶し、ノード58はファイル58を記憶し、ノード62はファイル59、60、61、および62を記憶する。
【0022】
最も基本的な実装形態では、(ノードIDとファイルIDとを割り当てるために同じハッシュ関数を使用することにより)任意の所与のファイルの1つのコピーだけがChordネットワーク内に記憶されるが、(例えば、ノード障害、ロードバランシングなどの場合の弾性により)Chordネットワーク内にファイルの複数のコピーを記憶するために、異なる方法が用いられてもよい。
【0023】
一実施形態では、例えば、ファイルの複数のバージョンは、合意された命名規則を使用して、若干異なるファイル名をファイルの複数のコピーに割り当てることによって、Chordネットワーク内に記憶され得る。例えば、ファイルの名称が「abc」である場合、「−n」などの拡張子が同じファイルを表すファイル名に追加され得る。この例では、ファイルの複数のコピーは、名称「abc」、「abc−1」、「abc−2」などの下で記憶され得る。このように、「abc」ファイルに関する複数のファイル名は同一ではないため、異なるファイル名のハッシングは、結果として、異なるハッシュ出力、したがって、異なるファイルIDをもたらすことになり、それによって、ファイルの複数のコピーをChordネットワークの異なるノード内に記憶させる。
【0024】
一実施形態では、例えば、(単一のコンシステントハッシュ関数が使用される、上で説明された実装形態ではなく)ファイル名を使用して、ファイルに関する複数のファイルIDを生成するために、複数の独立したハッシュ関数を使用することによって、ファイルの複数のバージョンがChordネットワーク内に記憶され得る。この実装形態では、ファイルをChordネットワーク内にシード処理している(seeding)ノードは、ハッシュ関数を使用して、ファイルの可能なファイルIDのそれぞれを判断して、それらのファイルIDを使用して、ファイルの複数のコピーをChordネットワーク内に挿入する。この実施形態では、Chordネットワーク内のファイルを探索しているノードは、(ハッシュ関数のそれぞれを使用してファイル名をハッシュすることによって)ファイルの可能なファイルIDのすべてを判断することになり、次いで、判断されたファイルIDを使用して、連続的にまたは同時にファイルを探索することが可能である。
【0025】
Chordネットワーク内にファイルの複数のバージョンを記憶することに関して、ファイルの複数のバージョンは、任意のその他の適切な形でChordネットワーク内に記憶され得る点を理解されよう。
【0026】
本明細書で説明されるように、Chordは、ノードがファイルを共有することを可能にする。Chordネットワークのノードがファイルを共有することを可能にするために、Chordネットワークのそれぞれのノードは、所望されるファイルを取得することが可能になるように、所望されるファイルの位置を探索して、それを最終的に判断することが可能である必要がある。
【0027】
Chordでは、それぞれのノードは、探索表を維持する。Mビットの鍵空間を有するChordネットワークの場合、それぞれのノードNは、M個の項目を有する探索表を維持することになり、この場合、探索表の項目は「フィンガ」と呼ばれる。ノードNに関する探索表では、第i番目のフィンガは、Nから少なくとも2i―1離れた、円上の第1のノードを指す。一般に、その他の表示がない限り、「第i番目のフィンガ」という用語は、探索表の第i番目の項目によって指摘されるノードを示すために使用されることになる。例えば、Chordネットワーク100では、ノード0の第3番目のフィンガは、ノード5である。
【0028】
ノードの探索表は、Chordネットワーク内のオブジェクトの(1つまたは複数の)位置が判断され得る効率的なグローバル探索アルゴリズムを集合的に提供する。
【0029】
図1では、鍵空間は6ビットであり、したがって、それぞれのノードは、その探索表内に6個のフィンガを有する。図1では、ノード0に関する探索表は、続く表1に示されるように表現され得る:
【表1】

【0030】
Chordでは、ネットワークは動的である。新しいノードがChordネットワークに参加して、既存のノードがChordネットワークを退去するにつれて、Chordネットワークのアクティブノードにおいて探索表が影響を受ける可能性がある。したがって、Chordでは、それぞれのアクティブノードKは、その関連する探索表を周期的に更新することになる。アクティブノードKは、任意の適切な形でその探索表を更新することが可能である。例えば、この探索を実行する結果は、探索表の第i番目のフィンガに関する値になるため、アクティブノードKは、ノード(K+2i−1)を探索することによって、その探索表を更新することが可能である。Chordネットワークのアクティブノードは、任意のその他の適切な形でその探索表を更新することが可能である点を理解されよう。
【0031】
Chordでは、探索表に加えて、それぞれのノードは、リング内のその後任およびその前任の識別も記憶する。この情報は、新しいノードがネットワークに参加して、既存のノードがネットワークを退去するとき、ならびに、ノードが障害から回復したときなど、リング維持に関して使用される。いくつかのChordネットワークでは、複数の同時ノード障害が存在する状況を防ぐために、ノードは、リング内にN個の後任およびN個の前任の識別を記憶することが可能である。
【0032】
Chordでは、Chordネットワークのノードは、Chordネットワークの他のノードからのファイルを探索して、それらを取得することが可能である。Chordネットワークは、それによって、ノードがChordネットワーク内の他のノードから利用可能なファイルを探索することができる探索アルゴリズムをサポートする。Chord探索アルゴリズムの動作は、図1のChordネットワーク100を使用した一例を介して例示され得る。この例では、ノード2は、図1のChordネットワーク100内のファイル0を探索することを望むと仮定する。ノード2は、ファイル要求の送信先である他のノードのうちの1つを選択するために、その探索表にアクセスすることになる。ノード2の観点から、ターゲットファイル(すなわち、ファイル0)のファイルIDは、ラップアラウンドにより、ノード2(すなわち、ノード34)の最大フィンガの値を超えるため、ノード2は、ノード34がファイル0を探索することを要求するファイル要求をノード34に送信することになる。ノード34は、ノード2からそのファイル要求を受信する。ノード34はファイル0を記憶していないため、ノード34は、そのファイル要求の転送先である他のノードのうちの1つを選択するために、その探索表にアクセスすることになる。ノード34において、探索表は、ノード35、37、40、43、51、および2を指す、6個のフィンガを含む。ファイル0のオブジェクトIDは第5番目のフィンガと第6番目のフィンガ(それぞれ、ノード51およびノード2)との間にあるため、ノード34は、第5番目のフィンガ(ノード51)によって識別されたノードに探索要求を転送する。ノード51は、ノード34からファイル要求を受信する。ノード51はファイル0を記憶していないため、ノード51は、ファイル要求の送信先である他のノードのうちの1つを選択するために、その探索表にアクセスすることになる。ノード51において、探索表は、ノード53、53、56、62、3、および19を指す、6個のフィンガを含む。ファイル0のオブジェクトIDは第4番目のフィンガと第5番目のフィンガ(それぞれ、ノード62およびノード3)との間にあるため、ノード51は、第4番目のフィンガ(ノード62)によって識別されたノードに探索要求を転送する。ノード62は、ノード51からファイル要求を受信する。ノード62はファイル0を記憶していないため、ノード62は、ファイル要求の送信先である他のノードのうちの1つを選択するために、その探索表にアクセスすることになる。ノード62において、探索表は、ノード0、0、2、6、16、および30を指す、6個のフィンガを含む。ファイル0のオブジェクトIDは第1番目のフィンガと第2番目のフィンガの両方(ノード0)において示されるため、ノード62は、ノード0がアクティブであることを知っており、探索要求をノード0に転送する。ファイル0は、次いで、ノード2に戻される。例えば、ファイル0は、次いで、(例えば、探索要求がノード2のIPアドレスを含む場合)ノード0からノード2に直接的に提供されることが可能であり、または、その後にファイル要求が続く経路に沿って(すなわち、ノード0からノード62、ノード51、ノード34、ノード2に)伝搬し戻させることが可能である。したがって、この例から、Chordでは、Chordネットワーク内のノードのすべてがChord検索アルゴリズムをサポートするために協働している点は明らかであろう。
【0033】
Chordでは、ノードは、任意の時点で、Chordネットワークに参加して、Chordネットワークを退去することができるため、Chordネットワークは動的である。ノードがChordネットワークに参加するとき、およびChordネットワークから退去するとき、ファイルはノード同士の間で転送される。例えば、参加ノードは、少なくとも、その参加ノードのノードIDと同じファイルIDを有するファイル(および、潜在的に、その他のファイル)を記憶する責任を負うことができ、一方、退去するノードは、1つまたは複数のファイルを記憶する責任を別のノードに転送することができる。Chordネットワークに参加することおよびChordネットワークから退去することに関連する手順は、以下でさらに詳細に説明される。
【0034】
Chord参加手順において、ノードがChordネットワークに参加することを望むとき、参加ノードはそのノードIDを判断する。参加ノードは、その名称をキー値にハッシュすることによって、そのノードIDを判断する。例えば、ノードの名称がnode−xyz@company−abc.comである場合、ノードIDは、SHA−1(node−xyz@company−abc.com)の出力になり、この場合、分かりやすいように、(任意の適切なハッシング関数が使用され得るが)ハッシュ関数はSHA−1であると仮定する。この例では、このノードに関するノードIDを、ハッシング操作から判断されるように、Kとする。
【0035】
Chord参加手順において、参加ノードKは、次いで、Chordネットワークの(初期化ノードとして示される)アクティブノードと交信する。一見、この初期化ノードは、集中サーバであるように思われるが、そうではなく、その理由は:(a)初期化ノードはChordネットワーク内で現在アクティブな任意のノードであってよく(例えば、ノードK1およびノードK2が同時にChordネットワークに参加することを望む場合、ノードK1およびノードK2はそれが可能であり、そのネットワークに参加するためのそのそれぞれの初期化ノードとして異なるアクティブノードを使用する可能性がある)、(b)初期化ノードは、基本的な機能に加えて、何らの特別な機能も提供する必要がない(すなわち、初期化ノードは、Chordネットワーク内の任意の他のノードと同じ様に行動することができる)ためである。ノードKは、任意の適切な形で(例えば、参加ノードKに関する1つもしくは複数の先の探索表、後任リスト、および/または前任リストから、参加ノード内で管理者によって構成された情報から、ウェブサイトからなど)潜在的な候補初期化ノードのリストを取得することが可能である。この例では、初期化ノードのノードIDをLとする。
【0036】
Chord参加手順において、参加ノードKは、次いで、初期化ノードLが参加ノードKを探索する(すなわち、ID=Kを有するオブジェクトを探索する)要求を送信する。この時点で、2つの事象が発生する可能性がある:
(A)ノードLは、Nの値を用いて、参加ノードKに応答する。ノードNは、すべてのアクティブノードの中でも、参加ノードKに関連するKよりも単により大きなノードIDを有するノードになる。したがって、参加ノードKがChordネットワークに参加するとした場合、ノードNは、参加ノードKに関する後任ノードのはずである。ノードKは、次いで、ノードNと交信して、ノードNの前任ノードの識別をノードNに尋ねる。この例では、ノードNの前任をノードN−として示させる。ノードNは、参加ノードKにN−の値を提供する。この情報に基づいて、ノードKは、次いで、ノードKがChordネットワーク内でノードNとノードN−との間に自らを挿入しなければならないことを知る。
【0037】
(B)ノードLは、Kの値を用いて、参加ノードKに応答する。これは、Chordネットワーク内に既にアクティブなKのノードIDを有する別のノードが存在することを意味する。この事例が大部分のChordネットワークにおいて起こる可能性は極めて低いが(例えば、160ビットの鍵空間であるChordネットワーク100では、この状況が発生する可能性は1.451048中1であるが)、可能ではある。この状況は、参加ノードKに(例えば、タイムスタンプを追加して、数を追加してなど)その独自の名称を若干変更させて、(K’として示される)異なるノードIDを生成するために新しいノード名を使用させることによって対処され得る。参加ノードK’は、新しい探索要求(すなわち、初期化ノードLが参加ノードK’を探索する要求)を初期化ノードLに送信することによって、再度このプロセスを開始することが可能である。
【0038】
Chord参加プロセスでは、参加ノードKに関する挿入点を判断することに続いて、Chordネットワーク内にその参加ノードを挿入するための処理が実行される。参加ノードKは、ノードK−(Kの候補前任)とノードK+(Kの候補後任)との間に挿入されており、この場合、この時点で、ノードKがネットワークに参加する前に、ノードK+は、ノードK−の後任である。参加ノードKは、後任ノードK+と交信して、参加ノードKがChordネットワークに参加することを望む旨を示す。後任ノードK+は、次いで、(1)その前任がノードK−であることを参加ノードKに知らせ、(2)ノードKが担当すべき任意のファイル(すなわち、(K−)+1からKのファイルIDを有するファイル)を参加ノードKに転送し始め、(3)参加ノードKがChordネットワークに参加するプロセスにあることをその前任ノードK−に知らせる。ファイル転送が完了した後で、参加ノードKは、前任ノードK−との接続を確立する。参加ノードKと前任ノードK−との間の接続が確立された後で、参加ノードKは、参加ノードKがChordネットワークに成功裏に参加したことを後任ノードK+に知らせる。後任ノードK+は、次いで、前任ノードK−との接続を中断して、後任ノードK+と前任ノードK−は両方とも、その前任リストおよび後任リストを更新する。
【0039】
Chord退去手順では、退去ノードKが制御された形でChordネットワークを退去することを可能にするための処理が実行される。退去するノードKは、退去ノードKに関連する(ノードK−として示される)前任ノードと(ノードK+として示される)後任ノードとを有する。退去ノードKは、前任ノードK−と後任ノードK+の両方と交信して、退去ノードKがChordネットワークを退去することを意図していることを前任ノードK−と後任ノードK+の両方に知らせて、それら両方のノードに他方の識別を提供する。退去ノードKは、次いで、Chordネットワークに代わって退去ノードKが現在記憶しているファイルのすべて(すなわち、Kを含めて、(K−)+1とKとの間のファイルIDを有するすべてのファイル)を後任ノードK+に転送する。ファイルの転送が完了した後で、参加ノードは、前任ノードK−および後任ノードK+から切断することによって、Chordネットワークを退去する。ノードK−およびK+は、次いで、互いの間に(それらのいずれかによって開始され得る)接続を確立する。ノードK−およびK+は、その前任リストおよび後任リストをやはり更新する。
【0040】
Chordネットワークに対する動的な変更を可能にするためのChord参加手順およびChord退去手順の使用に加えて、Chordは、ノード障害からの回復を可能にするためのChord回復手順もサポートする(すなわち、Chord退去手順およびChord参加手順は、ノード障害から回復するために使用されない)。Chordネットワークのノードは、それぞれ、それらの前任ノードと後任ノードとにハートビートメッセージ(heartbeat messages)を周期的に送信し、それによって、Chordネットワークのノードがノード障害を迅速に検出するのを可能にする。一般に、ノードからのハートビートメッセージは、ハートビートメッセージが生じたノードの前任ノードおよび後任ノードの識別を含むことになる。このように、ノードがその後任ノードからハートビートメッセージを受信するとき、そのノードは、その後任ノードの後任ノードの識別を知り、したがって、ノードの後任に障害が発生したとき、そのノードは、その後任ノードの後任ノードに対する接続を開始することが可能であり、Chordリングが維持される。上記のように、一部のChordネットワークでは、ノードは、k個の前任およびk個の後任のリストを維持する。この場合、Chordネットワークは、k−1個の連続的なノードの障害から回復することが可能である。この場合、kの小さない値の場合ですら、k個の連続的なノードの障害の確率は非常に小さい。一部のそのようなChordネットワークでは、kに関する値は、2log(L)と判断されることが可能であり、式中、Lは、ネットワーク内のアクティブノードの平均数である(すなわち、通常、100、000個のアクティブノードを有するChord、kは34までとなる)。
【0041】
上述のChord回復手順は、ノード障害の場合にChordネットワークが修復されることを可能にするが、障害が発生したノードに記憶されたファイルは失われる。この問題は、いくつかの形で対処され得る。
【0042】
一実施形態では、この問題は、Chordネットワーク内にファイルの複数のコピーを記憶することによって対処される。2つのそのような方法が上で説明されている。この方法は追加の弾性を提供するが、Chordネットワークのノードのそれぞれに関する記憶容量をk倍に増大することを必要とする。
【0043】
別の実施形態では、この問題は、ファイルを取得するノードが自発的にそれらのファイルに関するシードノードになることを可能にすることによって対処される。1つのそのような実施形態の説明が続く。ファイルは、Chordネットワークのメンバによって、当初、Chordネットワーク内に導入される(この場合、メンバノードは、ファイルのシードノードと呼ばれる)。このシードノードは、ファイル名のハッシュされた値(すなわち、ファイルID)を取得して、そのファイルIDと同じノードIDを有するノードを探索する。シードノードは、Chordネットワーク内でそのファイルID以上のノードIDを有する第1のアクティブノードを位置特定することになる。シードノードは、そのファイルを位置特定されたノードに送信する。次いで、後の時点でそのファイルを取得する、Chordネットワークの他のノードは、自発的にそのファイルに関するシードノードになることができる。ファイルに関するシードノードは、Chordネットワーク内のそのファイルを周期的に探索することになり、シードノードがそのファイルを位置特定できない場合、そのシードノードは、上述のように適切なノードにファイルを送信することになる。このように、「失われた」ファイルがChordネットワーク内で回復される。
【0044】
本明細書で説明されるように、P2Pネットワーク分解機能は、P2Pネットワークが複数のサブネットワークに分解されるのを可能にし、それによって、分解されたP2Pネットワークを形成する。分解されたP2Pネットワーク内でサブネットワークのそれぞれはP2Pネットワークとして動作し、これにより、上述のように、P2Pネットワークの機能のうちのいくつかまたはすべてをサポートする。分解されたP2Pネットワークを形成するためのP2Pネットワークの分解と、分解されたP2Pネットワークの使用とに関連する様々な実施形態の説明が続く。
【0045】
図2は、図1の例示的なChordネットワークのサブネットワークへのある例示的な分解を示す。
【0046】
図2に示されるように、Chordネットワーク100の分解されたChordネットワーク200への分解は、制御ネットワーク202と複数のサブネットワーク204−204(集合的に、サブネットワーク204)とを形成することを必要とする。
【0047】
分解されたP2Pネットワークでは、サブネットワークのそれぞれは、同じ鍵空間(Mビット)と(f(x)として示される)同じ鍵空間ハッシュ関数とを使用する。
【0048】
分解されたP2Pネットワークの一実施形態では、分解されたP2Pネットワークは、それに関連するサブネットワーク指標のセットを有する。サブネットワーク指標は、Kビットフィールドであり、分解されたP2Pネットワークのサブネットワーク指標は、入力ストリングをKビット値にマッピングする、(g(x)として示される)サブネットワーク指標ハッシュ関数を使用し、それによって、分解されたP2Pネットワークに関する2個のサブネットワーク指標を生成して判断される。分解されたP2Pネットワークでは、それぞれサブネットワーク指標は、サブネットワークのうちの少なくとも1つに割り当てられ、それぞれのサブネットワークは、割り当てられた少なくとも1つのサブネットワーク指標を有する。サブネットワーク指標ハッシュ関数は、オブジェクト(ノードまたはファイル)のサブネットワーク指標を計算するために使用され、すなわち、ノードのサブネットワーク指標はg(ノード名)として判断され、ファイルのサブネットワーク指標はg(ファイル名)として判断される。
【0049】
分解されたP2Pネットワークの一実施形態では、鍵空間ハッシュ関数f(x)およびサブネットワーク指標ハッシュ関数g(x)は、それらが統計的に無相関であるように選択されるべきである。一実施形態では、鍵空間ハッシュ関数f(x)およびサブネットワーク指標ハッシュ関数g(x)は、Jビットの出力を有する(h(x)として示される)ハッシュ関数を選択することによって構成され、この場合、Jは、M+K以上の整数である。この実施形態では、オブジェクト(ノードまたはファイル)が与えられると、h(オブジェクト名)が計算され、それによって、Jビット値をもたらし、この場合、オブジェクト(g(オブジェクト名))に関するサブネットワークを識別するためにK個の最上位ビットが使用され、サブネットワーク内のオブジェクト(f(オブジェクト名))を識別するために、M個の最下位ビットが使用される。
【0050】
分解されたP2Pネットワークにおいて、分解されたP2Pネットワークに参加する際、分解されたP2Pネットワーク内で動作する(例えば、ファイルを記憶する、ファイルを位置特定するなど)の際、および分解されたP2Pネットワークを退去する際にノードによって使用するように構成された情報を維持するために、ネットワークマップが形成される。
【0051】
一実施形態では、分解されたP2Pネットワークのネットワークマップは、分解されたP2Pネットワークのサブネットワークに対する分解されたP2Pネットワークのサブネットワーク指標のマッピングを含む。ネットワークマップは、サブネットワークのそれぞれに関して、サブネットワークを識別する、少なくとも1つのサブネットワーク指標に対するサブネットワークのマッピングを提供する。
【0052】
一実施形態では、分解されたP2Pネットワークのネットワークマップは、鍵空間ハッシュ関数(f(x))の識別、鍵空間の関連するサイズ、サブネットワーク指標ハッシュ関数(g(x))の識別、およびその指標の関連するサイズなど、ならびにそれらの様々な組合せなど、ハッシング情報を含むことも可能である。
【0053】
一実施形態では、分解されたP2Pネットワークのネットワークマップは、どのサブネットワークに参加するかを判断する際にノードによって使用するための記述子、ネットワークマップを管理するためにネットワークマップの(1人または複数の)管理者によって使用するためのネットワークマップ管理情報など、ならびにそれらの様々な組合せなど、分解されたP2Pネットワークに参加する際、分解されたP2Pネットワーク内で動作する際、および分解されたP2Pネットワークを退去する際にノードによって使用するように構成されたその他の情報を含むことが可能である。
【0054】
分解されたP2Pネットワークでは、制御ネットワークは、分解されたP2Pネットワークのノードがノード、サービス、およびその他の制御情報を探索することを可能にする。したがって、ネットワークのそれぞれのノードに関して、ノードは、サブネットワークのうちのいずれかに参加する前に制御ネットワークに参加しなければならず、同様に、制御ネットワークを退去する前に、そのノードが属する(1つまたは複数の)サブネットワークのそれぞれを退去しなければならない。上で示されたように、制御ネットワークは、サブネットワークのそれぞれと同じ鍵空間を使用する。一般に、制御ネットワークは、任意のオブジェクトまたはファイルを記憶するために使用されないことになり、したがって、制御ネットワークに参加することおよび制御ネットワークを退去することに関連するオーバヘッドは比較的低い。制御ネットワークは、ノードが分解されたP2Pネットワークを介して「サービス」を探索する(例えば、特定のサブネットワークに属するノードに関してなど、特定の基準を満たすノードを探索する)ための能力を提供するのに適した任意のP2P技術を使用して実施され得る。一実施形態では、例えば、制御ネットワークは、Chordネットワークとして実施される。1つのそのような実施形態では、例えば、制御ネットワークは、その全体が参照により本明細書に組み込まれている「METHOD AND APPARATUS FOR LOCATING SERVICES WITHIN PEER−TO−PEER NETWORKS」という表題の米国特許出願第XX/XXX,XXX号(整理番号第Chu19−43号(ALU/130209))で示され、説明されるサービス位置特定機能など、サービス位置特定機能をサポートするChordネットワークとして実施される。その他のタイプのP2P技術がそのようなサービス位置特定機能をサポートする場合、これらのその他のタイプのP2P技術も制御ネットワークを実施するために使用され得る点を理解されよう。
【0055】
上述のように、制御ネットワークは、他のノードを探索するために、サービスを探索するために、他の制御情報を取得するためになど、ならびにそれらの様々な任意の組合せを行うためにノードによって使用され得る。制御ネットワークによって可能にされる機能は、制御ネットワークの以下の例示的な使用を考慮することによって、より良好に理解されよう。
【0056】
一例として、ノードAがノードBと交信することを望むと仮定するが、分解されたネットワークでは、ノードAは、ノードBがメンバである(1つまたは複数の)サブネットワークを知らないことになる。しかし、ノードAは、ノードBの(1つまたは複数の)サブネットワークを知らないが、ノードBがアクティブな限り、ノードBは制御ネットワークの一部になるため、ノードAは制御ネットワーク内のノードBの探索を開始することができる。ノードAが制御ネットワークを使用してノードBを位置特定した後で、ノードAは、次いで、ノードBと交信して、関係する交信情報および機能情報(例えば、ノードBがメンバである(1つまたは複数の)サブネットワーク、ノードBのIPアドレス、ノードB機能など)をノードBから要求することが可能である。
【0057】
一例として、ノードAがサブネットワークXに参加することを望むと仮定する。大部分のP2Pネットワークでは、ノードAは、サブネットワークXに参加するためのプロセスを開始するために、既にサブネットワークXのメンバであるノードと交信することが必要になる。この例では、ノードAは、サブネットワークXのメンバである任意のノードに関する制御ネットワークを探索するためにサービス位置探索機能を使用することが可能である。次いで、ノードのうち、サブネットワークXのメンバである1つを識別するとすぐ、ノードAは、サブネットワークXに参加するプロセスを開始することができる。
【0058】
一例として、ノードAがP2Pネットワークによって提供される特定のサービスを利用することを望むと仮定する。この例では、ノードAは、サービスをサポートする任意のノードに関する制御ネットワークを探索するサービス位置探索機能を使用することが可能である。同様に、この例では、ノードAは、特定のサブネットワーク内のサービスを探索するためにサービス位置探索機能を使用することが可能である。次いで、サービスの利用可能性を識別するとすぐ、ノードAは、そのサービスに関する要求を開始することができる。
【0059】
一例として、ノードAが制御ネットワークに参加すると仮定する。この例では、制御ネットワークに参加した後で、ノードAは、制御ネットワーク内のその近隣ノードとメッセージを交換することになる。(ノードAがネットワークマップの現在のバージョンをまだ有していない場合)交換されたメッセージは、現在のネットワークマップを獲得するためにノードAによって使用され得る。この例では、ノードAは、次いで、分解されたネットワーク内でその他の機能を実行するために、ネットワークマップを使用することが可能である。
【0060】
制御ネットワークの特定の例示的な使用に関して主に説明されているが、分解されたネットワークの制御ネットワークはその他の機能を実行するために使用され得る点を理解されよう。
【0061】
分解されたP2Pネットワークでは、P2Pネットワークのサブネットワークへの分解は、任意の適切な分解基準に基づいてよい。例えば、P2Pネットワークのサブネットワークへの分解は、以下の基準の1つまたは複数に基づいてよい:すなわち、P2Pネットワークのノードの地理的位置、P2Pネットワークのノードのユーザの関心共同体など、ならびにそれらの様々な組合せである。
【0062】
P2Pネットワークのノードの地理的位置に基づくP2Pネットワークの分解は、同じサブネットワークに属するノード同士の間の地理的距離を削減するかまたは最小限に抑える傾向がある形で実行される。これは、分解されたP2Pネットワークのノード同士の間で交換されたメッセージおよび情報によって横断された距離を削減するかまたは最小限に抑え(例えば、ノードがネットワークに参加および退去するとき、ハートビートメッセージ、ファイルが転送されるとき、など)、それによって、メッセージおよび情報を交換することに関連する遅延を削減し、メッセージおよび情報を交換することによって消費されるネットワークリソースを削減し、その他の利点を提供する。これらの利点は、世界中にアクティブノードを有する、ある例示的なグローバルP2Pネットワークの簡単な例を考慮することによって、より良好に理解されよう。
【0063】
この例では、グローバルP2Pネットワークは分解されていないと仮定し、ニューヨーク市に位置特定されるP2Pのノードのうちの1つは東京に位置特定される前任を有し、シドニーに位置特定される後任を有するとさらに仮定する。この例では、ニューヨーク市内のノードがP2Pネットワークに参加するとき、およびP2Pネットワークを退去するとき、いくつかのファイル転送を含むことになる、その前任および後任と交換されたメッセージは、世界中を移動しなければならない。同様に、この例では、ニューヨーク市内のノードがその前任および後任とハートビートメッセージを交換するとき、ハートビートメッセージも世界中を移動しなければならない。同様に、この例では、ニューヨーク市内のノードから探索を実行するとき、探索メッセージが非常に長い距離を移動することができるように、次のノードは東京に位置特定されることが可能であり、次のノードは、ニューヨーク市に戻り、次のノードは南アメリカに位置特定され、以下同様である。
【0064】
この例では、状況は、P2Pネットワークをサブネットワークに分解することによって改善されることが可能であり、この場合、サブネットワークのそれぞれに関して、そのサブネットワークに属するノードは、P2Pネットワークの他のノードに対して互いに地理的に近位である。この例では、P2Pネットワークは、日本に位置特定されるノードに関するサブネットワークと、ニューヨーク市領域に位置特定されるノードに関するサブネットワークとを含めて、複数のサブネットワークに分解されると仮定する。この例では、P2Pネットワークの分解に続いて、東京およびシドニーにその前任と後任とを有するのではなく、ニューヨーク市のノードは、その前任および後任として、ニューヨーク市内に他のノードを有することになる。同様に、この例では、P2Pネットワークの分解に続いて、長距離にわたって探索が実行される何らかの必要が存在する前に、探索は、(ローカルに利用可能なファイルが要求されていると仮定すると)サブネットワーク内に局在化され、かつ(この場合も、利用可能なファイルが要求されていると仮定すると)地理的に隣接するサブネットワーク内に局在化されることが可能である。このように、ニューヨーク市のノードによって交換される任意のメッセージ/情報によって横断される距離は劇的に削減される。
【0065】
P2Pネットワークのノードの地理的位置に基づくP2Pネットワークの分解は、任意の適切な粒度において実行され得る。例えば、グローバルP2Pネットワークの分解は、ノードが位置特定される大陸に基づいて、ノードをサブネットワークにグループ化することによって実行され得る。例えば、国内P2Pネットワークの分解は、国内のノードの位置に基づいて、(例えば、合衆国東部、合衆国中部、および合衆国西部に関して3個のサブネットワークを使用して、50の州に関して50個のサブネットワークを使用してなど、ならびに、それらの様々な組合せを使用して)ノードをサブネットワークにグループ化することによって実行され得る。例えば、ノードがニューヨーク市内に位置特定されていることを含めて、P2Pネットワークの分解は、そのノードが位置特定される区に基づいて、ノードをサブネットワークにグループ化することによって実行され得る。これらの例から、ノードは、任意の適切な粒度を使用して、地理的にサブネットワークにグループ化され得る点を理解されよう。
【0066】
特定の粒度におけるP2Pネットワークのノードの地理的位置に基づくP2Pネットワークの分解は、地理的領域内のノードの数に基づいて実行され得る。例えば、合衆国大陸をカバーするP2Pネットワークを考慮されたい。この例では、より多くのノードを有する、人口密度の高い州(例えば、ニューヨーク、カリフォルニアなど)は、それぞれ複数のサブネットワークに分解されてよく、一方で、より少ないノードを有する、人口密度がより低い州(例えば、ノースダコタ、サウスダコタなど)は、地理的位置に基づいて、組み合わされて単一のサブネットワークにされてよい。この例では、より大きな市(例えば、ニューヨーク、シカゴ、ロサンジェルスなど)のノードは、やはり組み合わされた単一のサブネットワークにされてよい。特定の粒度におけるP2Pネットワークのノードの地理的位置に基づくP2Pネットワークの分解は、任意のその他の適切な要因に基づいて実行され得る点を理解されよう。
【0067】
複数のノードがその地理的位置に基づいて複数のサブネットワークに参加できるように、P2Pネットワークのノードの地理的位置に基づくP2Pの分解が実行され得る。例えば、サブネットワークの多くが個々の州と州のグループとに関して形成され、かつ人口密度の高い領域に関して追加の領域的サブネットワーク(例えば、ニューヨーク、シカゴ、ロサンジェルス、およびその他の市に関するサブネットワーク)が形成される合衆国大陸をカバーするP2Pネットワークを考慮されたい。この例では、ニュージャージのノードは、例えば、ニュージャージに関するサブネットワークとニューヨーク市に関するサブネットワークの両方に参加することが可能である。
【0068】
上で示されたように、(地理的に互いに近いノードがサブネットワークにグループ化される)ノードの地理的位置に基づくP2Pネットワークの分解は、ネットワークリソース使用の改善、パフォーマンスの改善などを含めて、多くの利点を提供する。この場合、ノード同士の間で交換されるハートビートメッセージは、それぞれのサブネットワーク内に残る。同様に、この場合、地理的に遠隔なサブネットワークにおいてファイルを探索するとき、初期の探索メッセージだけがローカルサブネットワークから遠隔のサブネットワークに比較的長い地理的距離を横断しなければならず、すべての後続の探索メッセージは、遠隔サブネットワーク内に残ることになる。同様に、この場合、ノードがサブネットワークに参加するとき、またはノードがサブネットワークを退去するとき、その参加または退去の結果として生じるファイル転送は、サブネットワーク内のノード同士の間である。これらの機能のそれぞれに関して、関連するメッセージ/ファイルは、通常なら、ネットワークの分解前に可能になる距離よりも比較的より短い地理的距離を横断する。
【0069】
P2Pネットワークのノードのユーザの関心共同体に基づくP2Pネットワークの分解は、(やはり、任意の適切な粒度においてであってよい)任意の適切な関心共同体に基づいて実行され得る。例えば、大学のP2Pネットワークは、専門学部/専門領域の関心(例えば、数理学部に関する1つのサブネットワーク、物理学部に関する1つのサブネットワークなど)に基づいて、サブネットワークに分解され得る。例えば、音楽のP2Pネットワークは、(例えば、ブルースミュージックに関する1つのサブネットワーク、カントリーミュージックに関する1つのサブネットワークなど)音楽のタイプに基づいて、サブネットワークに分解され得る。
【0070】
本明細書で説明されるように、P2Pネットワークは、そのような分解基準の組合せを使用して分解されることも可能である。例えば、学問情報を交換するための国内P2Pネットワークは、その国内の大学のそれぞれに関するサブネットワークに分解されることが可能であり、1つまたは複数の大学サブネットワークは、その大学の専門学部のそれぞれに関して関連するサブネットワークにさらに分解され得る。例えば、図書館の書籍を交換するための州P2Pネットワークは、その州内の郡のそれぞれに関するサブネットワークに分解されることが可能であり、1つまたは複数の郡サブネットワークは、その郡内に位置特定される図書館のそれぞれに関して関連するサブネットワークにさらに分解され得る。これらの例から、P2Pネットワークは、分解基準の任意の組合せに基づいて、任意の数の階層レベルで任意の数のサブネットワークに分解され得る点を理解されよう。
【0071】
本明細書では、2つの階層レベルを有する分解されたP2Pネットワークを形成するためのP2Pネットワークの分解に関して主に示され、説明されているが、サブネットワークのうちの1つまたは複数は、P2Pネットワークが任意の適切な数の階層レベルを有する任意の適切な構成に分解され得るように、関連するサブネットワークなどにさらに分解されることが可能である点を理解されよう。
【0072】
分解されたP2Pネットワークを形成するためのP2Pネットワークの分解は、図2の分解されたChordネットワーク200を形成するための、図1のChordネットワーク100の分解を考慮することによってより良好に理解されよう。
【0073】
図2に示されるように、図2の制御ネットワーク202は、図1のChordネットワーク100のアクティブノードのすべてが図2の制御ネットワーク202にも属するという点で、図1のChordネットワーク100と同一である。
【0074】
図2に示されるように、分解されたChordネットワーク200は、3つのサブネットワークを含む。サブネットワーク204は、分解されたChordネットワーク200に関するネットワークマップ内で指定されるように、サブネットワーク204に関連するサブネットワーク指標をそれぞれ有する。図2では、分かりやすくするために、ネットワーク指標は、2ビットフィールドであり、さらに、分解されたChordネットワーク200に関するネットワークマップは、以下の表2に示されるように構成されると仮定する。
【表2】

【0075】
図1に示されるように、Chordネットワーク100の64個のノードのうち36個(すなわち、ノード0、2−3、5−7、9、12−13、16−24、26、29−30、32、34−35、37、41、43、45、49、51、53−54、56−58、および62)はアクティブであり、残りのノードは非アクティブである。
【0076】
図2に示されるように、Chordネットワーク100の36個のアクティブノードのそれぞれは、分解されたChordネットワーク200の制御ネットワーク202のメンバであり、Chordネットワーク100の36個のアクティブノードのサブセットは、それぞれ、サブネットワーク204、204、および204のメンバである。
【0077】
分解されたChordネットワーク200では、ノード0、6、7、13、16、20、21、24、29、35、43、53、56、および58はサブネットワーク204内のアクティブノードであり、ノード3、7、12、16、19、21、22、23、32、37、45、51、53、57、および62は、サブネットワーク204内のアクティブノードであり、ノード2、5、9、12、16、17、18、19、26、29、30、34、41、45、49、54、56、および58は、サブネットワーク204内のアクティブノードである。
【0078】
分解されたChordネットワーク200では、制御ネットワーク202のアクティブノードのうち10個がサブネットワーク204のうちの2つのメンバである:すなわち、ノード7、21、および53は、サブネットワーク204および204の両方のメンバであり、ノード12、19、および45は、サブネットワーク204および204の両方のメンバであり、ノード29、30、56、および58は、サブネットワーク204および204の両方のメンバである。
【0079】
分解されたChordネットワーク200では、制御ネットワーク202のアクティブノードのうちの1つは、3つのサブネットワーク204のそれぞれのメンバ、すなわち、ノード16である。
【0080】
分解されたP2Pネットワークの動作は、分解されたP2Pネットワーク内で機能(例えば、ファイルの記憶、ファイルの検査など)を実行するための方法の様々な実施形態を説明する図3−図9に関してより良好に理解されよう。
【0081】
図3は、ファイルを分解されたP2Pネットワーク内に記憶させる際にノードによって使用するための方法の一実施形態を示す。
【0082】
ステップ302において、方法300が開始する。
【0083】
ステップ304において、ファイルのサブネットワーク指標が計算される。ファイルのサブネットワーク指標は、ハッシュ関数を使用して、ファイルの識別子(例えば、ファイル名またはその他の適切なファイル識別子)をハッシュすることによって計算される。このハッシュ関数は、ファイルのサブネットワーク指標がg(ファイル名)として判断されるようなサブネットワーク指標ハッシュ関数であってよい。このハッシュ関数は、ファイルのサブネットワーク指標がh(ファイル名)の結果のK個の最上位ビットによって表されるように、完全ハッシュであってよく、この場合、ファイルのファイルIDは、h(ファイル名)の結果のM個の最下位ビットによって表される。
【0084】
ステップ306において、ファイルのサブネットワーク指標に関連する(1つまたは複数の)サブネットワークが識別される。サブネットワーク指標に関連する(1つまたは複数の)サブネットワークは、分解されたP2Pネットワークのネットワークマップを使用して識別され得る。識別された(1つまたは複数の)サブネットワークは、ファイルが記憶されるべき(1つまたは複数の)サブネットワークである。
【0085】
ステップ308において、(1つまたは複数の)識別されたサブネットワークに関連する(1つまたは複数の)アクティブノードが識別される。一実施形態では、サブネットワーク指標に関連する1つまたは複数のサブネットワークのそれぞれに関して、サブネットワークの1つまたは複数のアクティブノードが識別される。
【0086】
サブネットワークのアクティブノードは、任意の適切な形で識別される。
【0087】
一実施形態では、サブネットワークのアクティブノードは、方法300を実行して、ノード内にローカルに記憶された情報を使用して判断され得る。
【0088】
一実施形態では、サブネットワークのアクティブノードは、分解されたP2Pネットワークの制御ネットワークを使用して、サブネットワークのアクティブノードを探索することによって識別され得る。1つのそのような実施形態では、サブネットワークのアクティブノードの探索は、その全体が参照により本明細書に組み込まれている「METHOD AND APPARATUS FOR LOCATING SERVICES WITHIN PEER−TO−PEER NETWORKS」という表題の米国特許出願第XX/XXX,XXX号(整理番号第Chu19−43号(ALU/130209)で示され、説明されるサービス位置特定機能など、サービス位置特定機能を使用して実行され得る。
【0089】
ステップ310において、ファイルを識別されたサブネットワークのそれぞれの中に記憶させるためのプロセスが開始される。このプロセスは、ファイルを識別されたサブネットワークのそれぞれに記憶させるのに適した任意のプロセスであってよい。このプロセスは、分解されたP2Pネットワークにおいて使用する際にP2P技術によって指定されるような通常のファイル記憶プロセスであってよい。
【0090】
ステップ312において、オプションのステップ、すなわち、ファイルをノードのローカルサブネットワーク内(または、ノードが分解されたP2Pネットワークの複数のサブネットワークに属する場合、ノードの複数のローカルサブネットワーク内)に記憶させるためのプロセスが開始される。
【0091】
一実施形態では、そうすることが必要である場合、またはそうすることが望ましい場合、ノードは、ファイルをローカルサブネットワーク内に記憶することが可能である。例えば、ファイルがローカルサブネットワークに関係する情報を含む場合、ファイルがローカルサブネットワークのメンバによって頻繁に取り出される需要があるファイルである場合(例えば、ローカルサブネットワークのノードが地理的に互いと近いようにそれらの領域が組織される場合、ローカルサブネットワークからファイルを取り出すことは遠隔のサブネットワークからファイルを取り出すよりも、より効率的である)など、ならびにそれらの様々な組合せの場合、ノードは、ファイルをローカルサブネットワーク内に記憶することが可能である。
【0092】
一実施形態では、ノードにそうする特権が与えられている場合、ノードは、ファイルをローカルサブネットワーク内だけに記憶することが可能である。ファイルをローカルサブネットワーク内だけに記憶する特権がノードに与えられているかどうかに関する判断は、任意の適切な形で実行され得る。1つのそのような実施形態では、例えば、ノードがP2Pネットワークに参加するとき、ユーザを認証するために公開鍵システムが使用され得る(すなわち、公開鍵システムでは、それぞれのユーザに、そのユーザを識別するために使用され得るデジタル証明書が割り当てられ、その証明書は、そのユーザがファイルをローカルサブネットワークに記憶する特権を有するかどうかを示すために使用され得る)。
【0093】
ステップ314において、方法300は終了する。
【0094】
ファイルを分解されたP2Pネットワーク内に記憶させるための方法を説明する際に分かりやすくするために、図3の方法300から省略されているが、一実施形態では、分解されたP2Pネットワーク内のファイルの管理を円滑にするために、分解されたP2Pネットワーク内のファイルの管理を円滑にする際に使用するために、論理コンパニオン(logical companion)として、ファイル管理情報がファイルに提供され得る。このファイル管理情報は、ファイル内に含まれてよく、かつ/またはそのファイルに関連する別個のファイル/メッセージとして提供されてもよい。ファイルに関するファイル管理情報は、分解されたP2Pネットワーク内のファイルの管理を円滑にする際に使用するのに適した任意の情報を含むことが可能である。一実施形態では、例えば、ファイルに関するファイル管理情報は、(1)分解されたP2Pネットワーク内へのファイルの記憶を開始する記憶ノードの識別、および/または分解されたP2Pネットワーク内のファイルの存在を管理することを望んでいる(1つもしくは複数のサブネットワークに関連する)(集合的に、ファイルに関するシード処理ノード(seeding nodes)と呼ばれる場合がある)1つもしく複数の他のノードの識別、(2)ファイルが初めてサブネットワーク内に記憶された時間、(3)個々のサブネットワーク内および/または全体として分解されたネットワーク内でのファイルの失効を可能にするためのタイムスタンプ(例えば、タイムスタンプの失効時に、記憶ノードは、(1つまたは複数の)シード処理ノードに関連する(1つまたは複数の)サブネットワークがファイルを記憶し続けるべきであるかどうかに関して(1つまたは複数の)シード処理ノードに相談することになる、シード処理ノードからの応答が否定的な場合、ファイルはシード処理ノードのサブネットワークから削除され、シード処理ノードからの応答が肯定的な場合、タイムスタンプは更新され得る)、(4)個々のサブネットワークから、および/または全体として分解されたP2Pネットワークからのファイルの知的除去を可能にするためのカウンタ(例えば、この場合、カウンタは、過去n日にわたって、そのファイルが取り出された回数を記録する、この場合、その取出しの頻度が一定のしきい値未満である場合、記憶ノードは、(1つまたは複数の)シード処理ノードの(1つまたは複数の)ローカルサブネットワークがそのファイルを記憶し続けるべきかどうかを確認するために、(1つまたは複数の)シード処理ノードに相談することになる)など、ならびにそれらの様々な組合せのうちの1つまたは複数を含む。ファイル管理情報は、個々のサブネットワーク内および/または全体として分解されたP2Pネットワーク内でファイル管理機能を実行する際に使用するのに適した任意のその他の情報を含むことが可能である点を理解されよう。
【0095】
本明細書では、連続的に実行されているとして主に示され、説明されているが、方法300のステップの少なくとも一部は、同時に実行されてよく、または図3に関して示され、説明されるのと異なる順序で実行されてもよい。本明細書では、分解されたP2Pネットワーク内にファイルを記憶するためのプロセス論理の特定の実装形態に関して示され、説明されているが、分解されたP2Pネットワーク内にファイルを記憶するためのプロセス論理は、P2Pネットワーク分解機能を依然としてサポートしながら、様々な他の形で実施され得る点を理解されよう。
【0096】
図4は、分解されたP2Pネットワーク内に記憶されたファイルを位置特定する際にノードによって使用するための方法の一実施形態を示す。
【0097】
ステップ402において、方法400が開始する。
【0098】
ステップ404において、ファイルのサブネットワーク指標が計算される。ファイルのサブネットワーク指標は、ハッシュ関数を使用して、ファイルの識別子(例えば、ファイル名またはその他の適切なファイル識別子)をハッシュすることによって計算される。このハッシュ関数は、ファイルのサブネットワーク指標がg(ファイル名)として判断されるようなサブネットワーク指標ハッシュ関数であってよい。このハッシュ関数は、ファイルのサブネットワーク指標がh(ファイル名)の結果のK個の最上位ビットによって表されるように、完全ハッシュであってよく、この場合、ファイルのファイルIDは、h(ファイル名)の結果のM個の最下位ビットによって表される。
【0099】
ステップ406において、ファイルのサブネットワーク指標に関連する(1つまたは複数の)サブネットワークが識別される。サブネットワーク指標に関連する(1つまたは複数の)サブネットワークは、分解されたP2Pネットワークのネットワークマップを使用して識別され得る。識別された(1つまたは複数の)サブネットワークは、ファイルが記憶されている(1つまたは複数の)サブネットワークである。ファイルが複数のサブネットワーク内に記憶されている場合、(例えば、ノードが、ファイルを記憶しているサブネットワークのうちの1つの中のファイルを検査することになるか、それらのうちのいくつかの中のファイルを探索することになるか、またはそれらのすべての中のファイルを探索することになるかに応じて)それらのサブネットワークのうちの1つまたは複数は、サブネットワーク指標を使用して識別され得る。
【0100】
ステップ408において、オプションのステップ、すなわち、サブネットワーク指標を使用して、複数のサブネットワークが識別されるとき(すなわち、ファイルが複数のサブネットワーク内に記憶されているとき)、そのファイル関して探索されることになる(1つまたは複数の)サブネットワークとして、識別されたサブネットワークのうちの1つまたは複数が選択される。
【0101】
ステップ410において、識別された(かつ、オプションで、選択された)(1つまたは複数の)サブネットワークに関連する(1つまたは複数の)アクティブノードが識別される。一実施形態では、サブネットワーク指標を使用して識別された(かつ、オプションで、識別されたサブネットワークの中から選択された)1つまたは複数のサブネットワークのそれぞれに関して、サブネットワークの1つまたは複数のアクティブノードが識別される。
【0102】
サブネットワークのアクティブノードは、任意の適切な形で識別され得る。
【0103】
一実施形態では、サブネットワークのアクティブノードは、方法400を実行して、ノード内にローカルに記憶された情報を使用して判断され得る。
【0104】
一実施形態では、サブネットワークのアクティブノードは、分解されたP2Pネットワークの制御ネットワークを使用して、サブネットワークのアクティブノードを探索することによって識別され得る。1つのそのような実施形態では、サブネットワークのアクティブノードの探索は、その全体が参照により本明細書に組み込まれている「METHOD AND APPARATUS FOR LOCATING SERVICES WITHIN PEER−TO−PEER NETWORKS」という表題の米国特許出願第XX/XXX,XXX号(整理番号第Chu19−43号(ALU/130209))で示され、説明されるサービス位置特定機能など、サービス位置特定機能を使用して実行され得る。
【0105】
ステップ412において、(1つまたは複数の)アクティブノードが識別されるそれぞれの(1つまたは複数の)サブネットワーク内のファイルを探索するためのプロセスが開始される。このプロセスは、そのノードがメンバでないP2Pネットワーク内のファイルを探索するのに適した任意のプロセスであってよい。ノードは、(1つまたは複数の)アクティブノードが、分解されたP2Pネットワークにおいて使用する際にP2P技術によって指定されたような通常のファイル探索プロセスを使用して、そのサブネットワーク内のファイルを探索することを要求するために、(1つまたは複数の)アクティブノードと交信することが可能である。サブネットワーク内のファイルの探索は、ファイル識別子をハッシュすることによって判断されるように、ファイルのファイルIDを使用して実行され得る。
【0106】
ステップ414において、方法400は終了する。
【0107】
分かりやすくするために省略されているが、一実施形態では、識別されたサブネットワーク内でファイルを検査することに加えて、ノードは、その(1つまたは複数の)ローカルサブネットワーク内のファイルを探索することも可能である。
【0108】
(分かりやすくするために)終了として示され、説明されているが、方法400の実行が、結果として、ノードによる1つまたは複数のファイル探索要求メッセージの開始をもたらす場合、ノードは、ファイルを記憶しているノードを位置特定するとすぐ、ファイルを記憶しているノードに対してそのファイルの要求を開始することと、そのファイルを記憶しているノードからそのファイルを受信することとを含めて、ノードによって開始されたファイル探索要求をサポートする処理を実行し続けることが可能である。
【0109】
本明細書では、連続的に実行されているとして主に示され、説明されているが、方法400の少なくとも一部は、同時に、または図4に関して示され、説明されるのとは異なる順序で実行されてよい。分解されたP2Pネットワーク内のファイルを探索するためのプロセス論理の特定の実装形態に関して示され、説明されているが、分解されたP2Pネットワーク内のファイルを探索するためのプロセス論理は、P2Pネットワーク分解機能を依然としてサポートしながら、様々な他の形で実施され得る点を理解されよう。
【0110】
別個のプロセスとして主に示され、説明されているが、(図3に示されるような)ファイルを分解されたP2Pネットワーク内に記憶させる際にノードによって使用するためのプロセス、および(図4に示されるような)分解されたP2Pネットワーク内に記憶されたファイルを位置特定する際にノードによって使用するためのプロセスは、それらの2つのプロセスが、以下のステップが実行される単一の方法を使用して実施され得るように、類似のステップを含む点を理解されよう。すなわち、ファイルのサブネットワーク指標を計算するステップ、ファイルのサブネットワーク指標に関連するサブネットワークのうちのの1つ(または複数)のサブネットワークを識別するステップ、サブネットワークのうちの識別された1つ(または複数)のアクティブノードを識別するステップ、および分解されたP2Pネットワーク内でファイルを管理するためにアクティブノードを使用するためのプロセスを開始するステップであって、この場合、ファイルを管理するためにアクティブノードを使用するためのプロセスが、ファイルをネットワーク内に記憶させるためのプロセス、またはネットワーク内のファイルを位置特定するためのプロセスであってよい、開始するステップ、である。
【0111】
一実施形態では、分解されたP2Pネットワークのサブネットワークに参加するために、ノードは、まず、分解されたP2Pネットワークの制御ネットワークに参加しなければならない。ノードが分解されたP2Pネットワークのサブネットワークに開始するのを可能にするための一実施形態による方法が、図5に関して示され、説明される。
【0112】
図5は、分解されたP2Pネットワークのサブネットワークに参加する際にノードによって使用するための方法の一実施形態を示す。
【0113】
ステップ502において、方法500が開始する。
【0114】
ステップ504において、ノードは、分解されたP2Pネットワークの制御ネットワークに参加するための要求を開始する。制御ネットワークに参加するための要求は、P2Pネットワークに参加するための標準プロセスを使用することを含めて、任意の適切な形で開始され得る。
【0115】
ステップ506において、ノードは、参加されることになる1つまたは複数のサブネットワークを判断する。
【0116】
ノードは、参加されることになる(1つまたは複数の)サブネットワークを任意の適切な形で判断することが可能である。一実施形態では、ノードが参加できるか、またはノードが参加すべき(1つもしくは複数の)サブネットワークがノード上で利用可能である(例えば、ノードに関して管理者によって構成される)。一実施形態では、情報に関して別のデバイス(例えば、分解されたP2Pネットワークの制御ネットワーク、ウェブサーバなど)に問い合わせることによって、ノードが参加できるか、または参加すべき(1つもしくは複数の)サブネットワークがノードによって取得される。ノードは、参加されることになる(1つまたは複数の)サブネットワークを任意のその他の形で判断することが可能である。
【0117】
一実施形態では、ノードが参加できるか、または参加すべき(1つもしくは複数の)サブネットワークは、分解されたP2Pネットワークのネットワークマップから判断される。この実施形態では、ネットワークマップは、(例えば、ノードに関してネットワークマップが管理者によって構成されている場合)ノードに関して利用可能であり得るか、または任意の適切な形でノードによって取得され得る。一実施形態では、例えば、ノードが制御ネットワークに参加するとき、ノードは、制御ネットワーク内でその前任および後任とメッセージを交換することになり、ネットワークマップは、交換された情報の一部として含まれることが可能である。一実施形態では、例えば、ノードは、(例えば、その全体が参照により本明細書に組み込まれている「METHOD AND APPARATUS FOR LOCATING SERVICES WITHIN PEER−TO−PEER NETWORKS」という表題の米国特許出願第XX/XXX,XXX号(整理番号第Chu19−43号(ALU/130209))で示され、説明されるサービス位置特定機能など、サービス位置特定機能を使用して)利用可能なネットワークマップを有する制御ネットワークの(1つまたは複数の)アクティブノードを探索することができる。一実施形態では、例えば、ノードは、(例えば、ウェブサーバからネットワークマップを取り出すなど)ウェブ技術を使用して、ネットワークマップを取得することが可能である。ノードは、任意のその他の適切な形で、ネットワークマップを取得することが可能である。
【0118】
ノードがネットワークマップから参加され得るかまたは参加されるべき(1つもしくは複数の)サブネットワークを判断する一実施形態では、ネットワークマップは、参加され得るかまたは参加されるべき(1つもしくは複数の)サブネットワークを判断する際にノードによって使用するのに適した情報を用いて符号化され得る。この実施形態では、ネットワークマップは、任意の適切な情報を用いて、任意の適切な形で符号化され得る。
【0119】
一実施形態では、参加され得るかまたは参加されるべき(1つもしくは複数の)サブネットワークを判断する際にノードによって使用するのに適した情報は、P2Pネットワークの分解が基づく分解基準のタイプ(例えば、地理的位置、関心共同体など、ならびにそれらの様々な組合せ)に依存し得る。
【0120】
異なるタイプのそのような情報、すなわち、参加され得るかまたは参加されるべき(1つもしくは複数の)サブネットワークを判断する際にノードによって使用するのに適した情報の例の記述が続く。
【0121】
一実施形態では、例えば、それぞれのサブネットワークの名称は、ノードが適切な(1つもしくは複数の)サブネットワークを自動的に選択するためにサブネットワーク名を解析できるように、かつ/またはユーザが適切な(1つもしくは複数の)サブネットワークを選択することを可能にするためにサブネットワーク名がノードに表示され得るように、地理的情報を用いて符号化され得る。例えば、サブネットワークは、ニューヨーク領域ネットワーク、またはニュージャージ領域ネットワークなどと名付けられることが可能である。
【0122】
一実施形態では、例えば、サブネットワークのそれぞれは、ノードの地理的位置がサブネットワークの地理的サービスエリア内に包含される場合、ノードが(1つまたは複数の)サブネットワークに参加することになるように、そのサブネットワークに関連する地理的サービスエリア情報を有することが可能である。地理的サービスエリア情報は、任意の適切な手段(例えば、経度および緯度、長方形の四隅、または任意のその他の適切な手段)を使用して指定され得る。異なるサブネットワークの地理的サービスエリアは、領域のいずれも重複しないように、領域の一部が重複し、その他の領域は重複しないように、領域のすべてが何らかのレベルの重複を有するようになどに設定されてよい。ノードの地理的位置が複数のサブネットワークの地理的サービスエリアに包含される場合、ノードは、関連するサブネットワークのうちの1つに参加することが可能であり、それらのうちのいくつかに参加することが可能であり、またはそれらのすべてに参加することも可能である。ノードの地理的位置は、(例えば、ユーザインプット、ネットワーク測定情報、GPSなど)任意の適切な形で判断され得る。
【0123】
一実施形態では、例えば、サブネットワークのそれぞれは、ノードがノードの地理的位置から(1つまたは複数の)サブネットワークの(1つまたは複数の)地理的中心までの(1つまたは複数の)距離に基づいて、(1つまたは複数の)サブネットワークに参加することになるように、そのサブネットワークに関連する地理的中心を有し得る。この地理的中心は、(例えば、緯度および経度を使用して)任意の適切な形で指定され得る。ノードの地理的位置は、(例えば、ユーザインプット、ネットワーク測定情報、GPSなど)任意の適切な形で判断され得る。例えば、ノードは、ノードの地理的位置からサブネットワークのそれぞれの地理的中心までの距離を判断し、次いで、その判断された距離に基づいて、最も近いサブネットワークのうちの1つまたは複数を選択することが可能である。例えば、関連する距離がしいき値を満たす(1つまたは複数の)サブネットワークを見出すまで、ノードは、ノードの地理的距離からサブネットワークの地理的中心までの距離を連続的に判断することが可能である。
【0124】
一実施形態では、例えば、サブネットワークのそれぞれは、ノードのIPアドレスがサブネットワークに関連するIPアドレスプレフィックスのうちのいずれかの中に含まれている場合、ノードが(1つまたは複数の)サブネットワークに参加することになるように、そのサブネットワークに関連するいくつかのIPアドレスプレフィックスを有し得る。例えば、IPv4プリフィックス132.222.x.yに対するサブネットワーク1のマッピング、IPv4プリフィックス133.222.x.yに対するサブネットワーク2のマッピングなど。
【0125】
一実施形態では、例えば、ノードが適切な(1つもしくは複数の)サブネットワークを自動的に選択するためのサブネットワーク名を解析できるように、かつ/またはユーザが適切な(1つもしくは複数の)サブネットワークを選択することを可能にするために、サブネットワーク名がノードに表示され得るように、それぞれのサブネットワークの名称は、コンテンツタイプ情報を用いて符号化され得る。例えば、サブネットワークは、rutgers−physics−network、rutgers−biology−networkなどを名付けられることが可能である。
【0126】
参加され得るかまたは参加されるべき(1つもしくは複数の)サブネットワークを判断する際にノードによって使用するのに適した、異なるタイプの情報の特定の例が上で提供されているが、任意のその他の適切な情報が使用され得る点を理解されよう。
【0127】
参加され得るかまたは参加されるべき(1つもしくは複数の)サブネットワークを判断する際にノードによって使用するのに適した情報のタイプに関して上で提供された例は、そのような情報を相互排他的な形で使用することを主に説明しているが、そのような情報の任意の適切な組合せもノードが参加され得るかまたは参加されるべき(1つもしくは複数の)サブネットワークを判断するのを可能にするために使用され得る点を理解されよう。
【0128】
ステップ508において、ノードは、参加されることになる(1つまたは複数の)サブネットワークに参加するための(1つまたは複数の)要求を開始する。サブネットワークに参加するための要求は、P2Pネットワークに参加するための標準プロセスを使用することを含めて、任意の適切な形で開始され得る。
【0129】
ステップ510において、方法500は終了する。
【0130】
分かりやすくするために省略されているが、ノードは、ノードが制御ネットワークに参加したかどうかを決定するステップを実行することも可能である点を理解されよう。一実施形態では、例えば、(例えば、制御ネットワークから取得された情報を使用して、どの(1つまたは複数の)サブネットワークに参加すべきかを判断する場合)ノードは、ステップ504からステップ506に進む前に、そのノードが制御ネットワークに成功裏に参加したことを確実にすることが可能である。一実施形態では、例えば、(例えば、ノードが、制御ネットワーク以外のソースから取得された情報を使用してどの(1つまたは複数の)サブネットワークに参加すべきかを判断する場合)ノードは、ステップ506からステップ508に進む前に、そのノードが制御ネットワークに成功裏に参加したことを確実にすることが可能である。そのような実施形態では、ノードは、(1つまたは複数の)サブネットワークに参加するための(1つまたは複数の)要求を開始する前に、そのノードが制御ネットワークに成功裏に参加したことを確実にする。
【0131】
分解されたP2Pネットワークに参加するためのプロセス論理の特定の実装形態に関して主に示され、説明されているが、分解されたP2Pネットワークに参加するためのプロセス論理は、P2Pネットワーク分解機能を依然としてサポートしながら、様々なその他の形で実施され得る点を理解されよう。
【0132】
分解されたP2Pネットワークに参加しているノードの観点から書かれているが、関連する処理は、ノードが制御ネットワークに参加するのを可能にするために制御ネットワークの1つまたは複数のノードによって実行されることが可能であり、同様に、ノードが(1つまたは複数の)サブネットワークに参加するのを可能にするためにノードによって参加される(1つまたは複数の)サブネットワークの1つまたは複数のノードによって実行されることも可能である点を理解されよう。
【0133】
図6は、分解されたP2Pネットワークを退去する際にノードによって使用するための方法の一実施形態を示す。
【0134】
ステップ602において、方法600が開始する。
【0135】
ステップ604において、ノードは、分解されたP2Pネットワークの(1つまたは複数の)それぞれのサブネットワーク(すなわち、ノードが現在メンバであるサブネットワークのそれぞれ)を退去するための(1つまたは複数の)要求を開始する。サブネットワークを退去するための要求は、P2Pネットワークを退去するための標準プロセスを使用することを含めて、任意の適切な形で開始され得る。
【0136】
ステップ606において、ノードが分解されたP2Pネットワークのサブネットワークのうちのいずれかのメンバであるかどうかに関して判断が下される。ノードが、依然として、分解されたP2Pネットワークのサブネットワークのうちのいずれかのメンバである場合、方法600は、ステップ606に戻る。ノードがもはや分解されたP2Pネットワークのサブネットワークのうちのいずれかのメンバでない場合、方法600は、ステップ608に進む。
【0137】
ステップ608において、ノードは、分解されたP2Pネットワークの制御ネットワークを退去するための要求を開始する。制御ネットワークを退去するための要求は、P2Pネットワークを退去するための標準プロセスを使用することを含めて、任意の適切な形で開始され得る。
【0138】
ステップ610において、方法600は終了する。
【0139】
分解されたP2Pネットワークを退去するためのプロセス論理の特定の実装形態に関して主に示され、説明されているが、分解されたP2Pネットワークを退去するためのプロセス論理は、P2Pネットワーク分解機能を依然としてサポートしながら、様々なその他の形で実装され得る点を理解されよう。
【0140】
本明細書で説明されるように、分解されたP2Pネットワークのネットワークマップは、分解されたP2Pネットワークの参加、分解されたP2Pネットワーク内のファイルの記録、分解されたP2Pネットワーク内のファイルの探索、および分解されたP2Pネットワークに関連する類似の機能を円滑にする。いくつかの実装形態では、ネットワークマップは比較的に静的である可能性があり、一方、他の実装形態では、ネットワークマップはより動的である可能性があるが、ネットワークマップが変更され得る頻度にかかわらず、ネットワークマップの情報の少なくとも一部が修正され得る時間が存在し得る。
【0141】
ネットワークマップが変更され得る、そのような実装形態では、ネットワークマップは、ネットワークマップに対する修正を管理する際に使用するのに適した情報を含むことも可能である。ネットワークマップに対する修正を管理する際に使用するのに適した情報は、以下のうちの1つまたは複数など、この目的に適した任意の情報を含むことが可能である。すなわち、ネットワークマップの名称、ネットワークマップのバージョン番号、ネットワークマップの現在のバージョンが作成された時を示す作成タイムスタンプ、ネットワークマップの(1つまたは複数の)ネットワーク管理者の管理者識別、ネットワークマップの(1つまたは複数の)ネットワーク管理者のデジタル署名、ネットワークマップの任意の無許可の修正を検出する際に使用するためのメッセージダイジェストなど、ならびにそれらの様々な組合せ、である。
【0142】
一般に、ネットワークマップが変更されるとき、ネットワークマップを変更することによって引き起こされる可能性がある途絶(disruption)を最小限に抑えるために、合理的な期間にわたって遷移が発生すべきである。ネットワークマップが変更され得るそのような実装形態では、ネットワークマップを変更することによって引き起こされる可能性がある、分解されたP2Pネットワークに対する途絶を最小限に抑えるために、ネットワークマップは、本明細書で遷移時間間隔と呼ばれる時間間隔値を含むことも可能である。この遷移時間間隔は、分解されたP2Pネットワークに対する途絶を最小限に抑えるような形でネットワークマップを動的に修正するために使用され得る。
【0143】
一実施形態では、ネットワークマップの遷移時間間隔は、以下のように、分解されたP2Pネットワークに対する途絶を最小限に抑えるためにノードによって使用され得る。ノードは、更新メッセージを受信する。ノードは、ネットワークマップが変更されているかどうかを判断するために、更新メッセージ内のネットワークマップのバージョン番号を(例えば、ノードにおいて受信された最後の更新メッセージからの)ノード上でローカルに記憶されたネットワークマップのバージョン番号と比較する。ノードが、ネットワークマップが変更されたことを検出するとき、ノードは、現在の時間をネットワークマップの現在の(変更された)バージョンが作成された時を示す作成タイムスタンプと比較する。現在の時間と作成時間との間の差異が遷移時間間隔を超える場合、これは、ネットワークがネットワークマップに対する変更からすでに安定化していること、したがって、ノードはできるだけ早く任意の必要とされる変更を実行すべきであることを示す。現在の時間と作成時間との差異が遷移時間間隔未満である場合、これは、ネットワークマップに対する変更により、ネットワークが遷移期間にあること(または、遷移期間にある可能性が高いこと)、したがって、ノードは任意の必要とされる変更を実行するまで待機すべきであることを示す。ノードは、任意の必要とされる変更を実行するまで、(例えば、事前に判断された期間、任意の期間など)任意の適切な期間待機することができる。このように、ネットワークマップに対する変更に起因する分解されたP2Pネットワークに対する途絶は、削減されることが可能であり、最小限に抑えることすら可能である。
【0144】
この遷移時間間隔は、ネットワーク内のノードの数と、ネットワークマップに対する変更によって影響を受けることになるか、または当該変更によって影響を受けることが予測されるノードの数もしくは割合とに依存し得る、任意の適切な形で設定されてよい。
【0145】
上で示されたように、ネットワークマップを変更する際の課題のうちの1つは、ネットワークマップを変更する結果として分解されたP2Pネットワーク内で引き起こされる途絶の量を最小限に抑えるか、または少なくとも削減することである。この文脈で、分解されたP2Pネットワークの途絶は、分解されたP2Pネットワーク内に記憶されたファイルの損失、P2Pネットワークのノード同士の間の(例えば、サブネットワーク内の、および/またはサブネットワーク同士の間の)ファイルの転送など、ならびに類似の活動であると考えることができる。
【0146】
一般に、ネットワークマップの任意の情報が変更され得るが、ネットワークマップの変更情報の望ましさは、ネットワークマップの様々なタイプの情報に関して異なる。
【0147】
例えば、2つのハッシュ関数(すなわち、鍵空間ハッシュ関数f(x)およびサブネットワーク指標ハッシュ関数g(x))は、分解されたP2Pネットワークの動作のために重要であり、したがって、変更されない可能性が大きい(とはいえ、変更が必要とされる場合または所望される場合も存在し得る点を理解されるであろう)。
【0148】
例えば、P2Pネットワークが分解されたP2Pネットワークを形成するために分解される形を指定する分解基準は、変更される可能性がより高い。本明細書で説明されるように、分解基準は、地理的記述子、関心共同体記述子など、ならびにそれらの様々な組合せのうちの1つまたは複数を含むことが可能である。分解記述子に対する変更は、分解されたP2Pネットワークのノード(例えば、サブネットワークから切断しているいくつかのノードおよび/またはサブネットワークに参加しているいくつかのノード)によるサブネットワークメンバーシップの変更を必要とする場合がある。その変更が制御された形で実行される場合、分解されたP2Pネットワークの途絶は、削減されることが可能であるか、または除去されることすら可能である。この場合、多数のノードが短時間の間に、サブネットワークを退去する場合、および/またはサブネットワークに参加する場合、分解されたP2Pネットワークの途絶の高い可能性が存在することは明らかである。したがって、ネットワークマップの変更は、影響を受けたノードのすべてに同時にサブネットワークを退去させること、および/またはサブネットワークに参加させることを回避することを試みる形で実行されるべきである。
【0149】
ネットワークマップを変更することに関して、ネットワークマップ内に含まれ得る情報のタイプのサブセットに関する例が提供されているが、ネットワークマップ内に含まれ得るその他の情報に対する変更も、結果として、分解されたP2Pネットワークの途絶をもたらし得る点は明らかである。
【0150】
分解されたP2Pネットワークの途絶を削減または除去するために、変更は徐々に増分的に実行されるべきである。
【0151】
ネットワークマップの変更に基づいて、ノードが変更を実行する形を制御するための一実施形態による方法が、図7に関して示され、説明されている。
【0152】
図7は、分解されたP2Pネットワークのネットワークマップ内の変更に基づいて、変更を実行する際にノードによって使用するための方法の一実施形態を示す。
【0153】
ステップ702において、方法700が開始する。
【0154】
ステップ704において、ノードは、ネットワークマップ内の変更を検出する。ノードは、ネットワークマップが変更されたことを任意の適切な形で(例えば、バージョン番号、ネットワークマップの解析情報など、ならびにそれらの様々な組合せで)検出することが可能である。ノードは、任意の適切な時点で(例えば、ノードが制御ネットワークを経由して通信するたびに、制御ネットワークと周期的に交信することによってなど、ならびにそれらの様々な組合せで)ネットワークマップ内の変更を検査することができる。
【0155】
ステップ706において、ノードは、ネットワークマップ内で検出された変更がノードに影響を与えるかどうかを判断する。
【0156】
この判断は、変更したネットワークマップの情報のタイプに依存し得る、任意の適切な形で実行されることが可能である。
【0157】
例えば、分解基準がサブネットワークのそれぞれに関連する長方形の地理的領域として指定される地理的記述子を含む場合、ネットワークマップ内で検出された変更がノードに影響を与えるかどうかに関する判断は、ノードの地理的位置を決定するステップと、そのノードがメンバである(1つまたは複数の)サブネットワークが変更される必要があるかどうかを判断するために、ノードのその地理的位置をサブネットワークのそれぞれに関連する長方形の地理的領域と比較するステップとを含むことが可能である。
【0158】
例えば、分解基準がサブネットワークのそれぞれに関連するサブネットワーク名として指定された関心共同体記述子を含む場合、ネットワークマップ内で検出された変更がノードに影響を与えるかどうかに関する判断は、そのノードがメンバである(1つまたは複数の)サブネットワークが変更される必要があるかどうかを判断するために、サブネットワーク名のそれぞれを走査するステップを含むことが可能である。
【0159】
このように、ノードが影響を受ける場合、ネットワークマップ内で検出された変更がノードに影響を与えるかどうかに関する判断は、ノードがノードによって実行されることになる変更を判断することを可能にする。
【0160】
ノードがその変更による影響を受けない場合、方法700は、ステップ712に進み、その時点で、方法700は終了する。
【0161】
ノードがその変更による影響を受ける場合、方法700はステップ708に進む。
【0162】
ステップ708において、変更時間が判断される。この変更時間は、ネットワークマップ内の変更の変更に基づいて変更を実行する前に、ノードが待機することになる時間の量を示す。この変更時間は、(例えば、変更を実行する前に待機すべき期間、将来、変更が実行されるべき時間など)任意の適切な形で指定され得る。この変更時間は、(例えば、事前に判断された待機期間に基づいて、現在の時間に基づいて任意にタイムスタンプを生成することによってなど)任意の適切な形で判断され得る。
【0163】
ステップ710において、ノードは、変更時間によって示された時点で変更を実行する。
【0164】
ステップ712において、方法700は終了する。
【0165】
ノードがネットワークマップに対する変更に基づいて変更を実行することを可能にするためのプロセス論理の特定の実装形態に関して主に示され、説明されているが、ノードがネットワークマップに対する変更に基づいて変更を実行することを可能にするためのプロセス論理は、P2Pネットワーク分解機能を依然としてサポートしながら、様々なその他の形で実施され得る点を理解されよう。
【0166】
ネットワークマップに対する変更に基づく、分解されたP2Pネットワークに対する変更がある期間にわたって実行されるにつれて、図7の方法700が、ネットワークマップが変更する時点で、分解されたP2Pネットワークのメンバであるノードによってだけ必要とされるのは、ネットワークマップが変更する時点の後で、分解されたP2Pネットワークに参加する任意のノードは、ネットワークマップによって示される分解されたP2Pネットワークに参加することになるためである。
【0167】
前述の説明から、徐々に増分的にネットワークマップを変更して、合理的な時間間隔にわたってノード変更を拡散することによって、ネットワークマップに対する変更の結果としてもたらされる分解されたP2Pネットワークの途絶は、削減されることが可能であり、場合によっては、除去されることすら可能である点を理解されよう。
【0168】
本明細書で説明されるように、ネットワークマップ内の変更は、サブネットワーク指標マッピングを含めて、ネットワークマップ内の任意のタイプの情報に対する変更を含むことが可能である。サブネットワーク指標マッピングを変更することに関して、基本的に2つのタイプの増分的変更が存在する:すなわち、(a)サブネットワーク指標をサブネットワークに追加すること、および(b)サブネットワークからサブネットワーク指標を削除することである。サブネットワーク指標が第1のサブネットワークから第2のサブネットワークに移動する事例は、「追加」動作の後に続く「削除」動作として対処され得るが、この事例に関連する付加的な懸念事項が1つ存在する:すなわち、サブネットワーク指標が第2のサブネットワークに追加されるとき、第1のサブネットワークはそのサブネットワーク指標のファイルを第2のサブネットワークに転送する必要がある点である。ファイルが第1のサブネットワークから第2のサブネットワークに転送され得るプロセスを示す例が図8A−8Eに関して示され、説明され、ファイルが第1のサブネットワークから第2のサブネットワークに転送され得る、より一般的なプロセスが図9に関して示され、説明される。
【0169】
図8A−8Eは、ファイルが第1のサブネットワークから第2のサブネットワークに転送され得るプロセスを示す一例を示す。
【0170】
この例では、P2PネットワークをChordネットワークとし、既存のサブネットワークBに、現在、10001のサブネットワーク指標が割り当てられており、ネットワーク管理者は、サブネットワーク指標10001が割り当てられた新しいサブネットワークAを作成することを望むと仮定する。ネットワーク管理者は、新しいサブネットワークAと、新しいサブネットワークAに対するサブネットワーク指標10001の割当てとを反映するためにネットワークマップを更新することになる。ネットワーク管理者は、やはり、(例えば、ネットワークマップのバージョン番号を変更して)、ネットワークマップが更新されていることをChordネットワークのノードに示すようにネットワークマップを更新することになる。ネットワーク管理者は、Chord制御ネットワークを介して、その更新されたネットワークマップをブロードキャストすることになる。その更新されたネットワークマップは、任意の適切な形でChord制御ネットワークを介してブロードキャストされ得る。例えば、Chord制御ネットワークが、その全体が参照により本明細書に組み込まれている「METHOD AND APPARATUS FOR LOCATING SERVICES WITHIN PEER−TO−PEER NETWORKS」という表題の米国特許出願第XX/XXX,XXX号(整理番号第Chu19−43号(ALU/130209))で示され、説明されるサービス位置特定機能など、ブロードキャスト機能を提供するために使用されることも可能なサービス位置特定機能をサポートするChord制御ネットワークとして実施される場合、更新されたネットワークマップは、ブロードキャスト機能を使用してブロードキャストされ得る。更新されたネットワークマップのブロードキャストを経由して、更新されたネットワークマップを学習することに加えて、Chord制御ネットワークのノードは、(例えば、ブロードキャストメッセージのうちのいくつかに故障が発生した場合)Chord制御ネットワークを介してその(1つまたは複数の)前任および(1つまたは複数の)後任と交換されたハートビートメッセージを通じて更新されたネットワークマップを学習することも可能である。このように、Chord制御ネットワークのすべてのノードは、更新されたネットワークマップについて知らされる。
【0171】
この例では、サブネットワーク指標Aが新しいサブネットワークAに新たに割り当てられるとき、新しいサブネットワークAは、サブネットワークA内に記憶されたサブネットワーク指標10001に関連するファイルのすべてを有さない可能性がある。結果として、ノードが新しいサブネットワークAに初めて参加するとき、そのノードは、サブネットワーク指標10001をサポートする別のサブネットワーク(すなわち、この例では、サブネットワークB)からサブネットワーク指標10001に関連するファイルを獲得することを望む可能性がある。この例では、ノード1000は、Chordネットワークに関する通常の参加手順を使用して、新しいサブネットワークAに参加すると仮定する。ノード1000が新しいサブネットワークA内に記憶するために、サブネットワーク指標10001に関連するファイルを獲得することができる手順の説明が続く。
【0172】
図8Aに示されるように、ノード1000は、新しいサブネットワークAに参加し、ノード900は、ノード1000の前任であり、ノード1100は、新しいサブネットワークA内のノードAの後任である。新しいサブネットワークAに参加するとすぐ、後任ノード1100は、901から1000までのファイルIDを有するすべてのファイルをノード1000に転送する(しかし、サブネットワークAは新たに形成されているため、このリストは完全でない可能性がある)。ファイルのこのリストは完全でない可能性があるため、ノード1000は、そのファイルが実際に、ノード1000が新しいサブネットワークAにおいて責任を負う必要なファイルのすべてを有することを確認することを望む場合がある。
【0173】
図8Bに示されるように、ノード1000はサブネットワークBを識別し(すなわち、サブネットワーク指標10001をサポートする別のサブネットワーク、この例では、サブネットワークBを識別し)、ノード1000がサブネットワークBのメンバでない場合、ノード1000は、サブネットワークB内で自らを探索する。図8Bにさらに示されるように、サブネットワークB内で自らを探索する結果として、ノード1000は、サブネットワークB内でノード1000を超えるノードIDを有し、ノード1000に最も近いノード(例示的に、この例では、ノード1050)を識別する。
【0174】
図8Cに示されるように、ノード1000は、次いで、サブネットワークB内のノード900を探索する(すなわち、新しいサブネットワークA内のその独自の前任、それは、この例では、ノード900である)。図8Cにさらに示されるように、サブネットワークB内でその前任を探索した結果として、ノード1000は、サブネットワークB内でノード900よりも大きいノードIDを有し、ノード900に最も近いノード(例示的に、この例では、ノード920)を識別する。
【0175】
図8Dに示されるように、ノード1000は、サブネットワークB内でノード920とノード1050の間のすべてのノードを識別する。(すべてのノードは、それぞれ、その(1つまたは複数の)前任および(1つまたは複数の)後任の識別を知っているため)ノード1000は、それらのノードのそれぞれに問い合わせることによって、それらのノードを判断することができる。図8Dに示されるように、分かりやすくするために、ノード920と1050の間の1つのノードだけ、すなわち、ノード950がサブネットワークB内でアクティブであると仮定する。
【0176】
図8Eに示されるように、ノード1000は、サブネットワークBの識別されたノードから、サブネットワーク指標10001に関連し、かつノード1000がまだ記憶していない、901から1000の間のファイルIDを有する任意のファイルを取得する。ノード1000は、サブネットワーク指標10001に関連し、かつそれらのノードによって記憶されている901から1000の間のファイルIDを有する識別されたノード920、950、および1050のそれぞれにファイルのリストについて問い合わせる。ノード1000は、次いで、それらのファイルリストを、ノード1000が既に記憶しているファイルと比較する。ノード1000は、次いで、サブネットワーク指標10001に関連し、かつノード1000がまだ記憶していない、901から1000の間のファイルIDを有する任意のファイルを取り出す。
【0177】
図9は、分解されたChordネットワーク内でChordサブネットワークを初期化するとき、第1のサブネットワークのノードが第2のサブネットワークからファイルを獲得するのを可能にするための方法の一実施形態を示す。
【0178】
ステップ902において、方法900が開始する。
【0179】
ステップ904において、ノードは第1のサブネットワークに参加する。ノードはNのノードIDを有し、第1のサブネットワークは、Jのサブネットワーク指標を有する。
【0180】
ステップ906において、ノードは、第1のサブネットワーク内のその前任を識別する。この前任ノードは、PのノードIDを有する。
【0181】
ステップ908において、ノードは、(そこからファイルが取得されることになる第2のサブネットワークとして示される)Jのサブネットワーク指標を有する別のサブネットワークを識別する。
【0182】
ステップ910において、ノードは、第2のサブネットワーク内で自らを探索する(NのノードIDを有するノードに関して第2のサブネットワークを探索する)。この探索の結果は、ノードNが、サブネットワーク内の、ノードID Nを超えるノードIDを有し、かつノードID Nに最も近いノードの表示を受信することである。この結果、ノードはノードN1として示される。
【0183】
ステップ912において、ノードは、第2のサブネットワーク内で前任Pを探索する(PのノードIDを有するノードに関して第2のサブネットワークを探索する)。この検索の結果は、ノードNが、サブネットワーク内で、ノードID Pを超えるノードIDを有し、かつノードID Pに最も近いノードの表示を受信することである。この結果、ノードはノードN2として示される。
【0184】
ステップ914において、ノードは、第2のサブネットワーク内のノードN1とノードN2との間のすべてのノード(N)を識別する。
【0185】
ステップ916において、ノードは、識別されたノードN内に記憶された、サブネットワーク指標Jを有するすべてのファイルを識別する。一実施形態では、例えば、ノードは、識別されたノードN内に記憶された、サブネットワーク指標Jを有するすべてのファイルを識別するための問合せを開始して、識別されたノードN内に記憶された、サブネットワーク指標Jを有するすべてのファイルを示す問合せ応答を識別されたノードNから受信する。
【0186】
ステップ918において、ノードは、もしあれば、ノード上に記憶されるべき、識別されたファイルのうちのどれがその現在ノード上に記憶されていないかを判断する。そのノード上に現在記憶されていないが、そのノード上に記憶されるべき、判断されたファイルは、ファイルIDとノードIDとに基づいて判断される(すなわち、Nを含めて、PとNの間のファイルIDを有するファイル)。
【0187】
ステップ920において、ノードは、識別されたノードNから、そのノード上に現在記憶されていない、識別されたファイルのうちのいずれかを取得する。一実施形態では、例えば、ノードは、そのノード上に現在記憶されていない、識別されたファイルのうちのいずれかに関する要求を開始して、識別されたノードNから(1つまたは複数の)要求されたファイルを受信する。
【0188】
ステップ922において、ノードは、取得された(1つまたは複数の)ファイルを第1のサブネットワーク内で利用可能にするためにそれらのファイルを記憶する。
【0189】
ステップ924において、方法900は終了する。
【0190】
ノードが第2のサブネットワークからファイルを獲得するために第1のサブネットワークに参加するのを可能にするためのプロセス論理の特定の実装形態に関して主に示され、説明されているが、ノードが第2のサブネットワークからファイルを獲得するために第1のサブネットワークに参加するのを可能にするためのプロセス論理は、P2Pネットワーク分解機能を依然としてサポートしながら、様々なその他の形で実施され得る。
【0191】
新しいサブネットワークのノードが分解されたChordネットワーク内の既存のサブネットワークからファイルを獲得するのを可能にするための上述の実施形態では、新しいサブネットワークが当初形成されるとき、新しいサブワークには少数のアクティブノードだけが存在する可能性があり、したがって、参加ノードとその前任との間のギャップは大きい可能性がある。結果として、新しいノードがマッチするサブネットワーク指標を有するファイルを既存の(1つまたは複数の)ネットワーク内で探索するとき、新しいノードは、多数のファイルを識別することが可能である。一実施形態では、新しいノードは、識別されたファイルのサブセット(例えば、識別されたノードから降順で限定数のファイル、または任意のその他の適切なサブセット)だけを取り出して記憶することが可能である。この実施形態では、時間が経つにつれて、より多くのノードが新しいサブネットワークAに参加する可能性が高まることになり、そのうちの少なくともいくつかは、新しいノードとその現在の前任との間にある可能性が高く、新しいサブネットワークに参加する新しいノードは、既存の(1つまたは複数の)サブネットワークから予め取得されていないファイルのうちのいずれかを取得するために、類似の手順を実行することが可能である。
【0192】
上述の実施形態では、新しく参加するノードが新しいサブネットワークに関するファイルを獲得するにつれて、新しいサブネットワークは、関連するサブネットワーク指標を有する、そのファイルの大部分を適宜に規則正しい形で獲得する。しかし、新しいサブネットワークと既存のサブネットワークは両方とも、ノードがサブネットワークに参加して、サブネットから退去する動的なネットワークであるため、上述の実施形態を使用して、ファイルのすべてが新しいサブネットワークに転送されことになるとは限らない可能性がある。したがって、一実施形態では、それぞれのファイルに関して、ファイルのシード処理ノードは、(例えば、定期的な間隔で、または任意のその他の適切なタイムフレームで)新しいサブネットワークに関するファイルを検索することになり、シード処理ノードが、そのファイルが欠けていることを判断した場合、シード処理ノードは、そのファイルを記憶する責任を負っている、新しいサブネットワークのノードにそのファイルを転送することが可能である。1つのそのような実施形態では、この手順は、新しいサブネットワークが安定化されると、または新しいサブネットワークが少なくとも比較的安定していると判断されると、実行もしくはアクティブ化されることが可能である。
【0193】
新しいサブネットワークのノードが分解されたP2Pネットワーク内の既存のサブネットワークからファイルを獲得するのを可能にするための上述の実施形態では、分解されたP2Pネットワークは、分解されたChordネットワークである。他のタイプのP2Pネットワーク(例えば、Pastry、Trapestryなど)の原理に従って、上述の実施形態を修正することによって、他のタイプのP2Pネットワークにおいて、類似の機能がサポートされ得る点を理解されよう。
【0194】
一実施形態では、例えば、新しいサブネットワークのノードが分解されたChordネットワーク内の既存のサブネットワークからファイルを獲得するのを可能にするための上述の実施形態は、新しいサブネットワークのノードが分解されたPastryネットワーク内の既存のサブネットワークからファイルを獲得するのを可能にするために修正され得る。一例として、新しいノードxが、10001のサブネットワーク指標が割り当てられた新しいサブネットワークAに参加する、分解されたPastryネットワークの事例を考慮する。新しいノードxは、サブネットワーク指標10001が割り当てられたサブネットワークを識別することになる。新しいノードxは、次いで、識別されたサブネットワークB内で自らを探索する(新しいノードxが既に識別されたサブネットワークBのメンバである場合、探索は必要ないため、この例では、新しいノードxは、識別されたサブネットワークBのメンバでないと仮定する)。この探索は、識別されたサブネットワークB内にノードyをもたらす。Pastryでは、ノードyは、ノードyのノードIDに近いノードのノードIDを含む「リーフセット(leaf set)を維持する(この例では、ノードyのリーフセットのノードをz、z、...、zとする)。新しいノードxは、次いで、ノードy内に記憶され、そのリーフセットがz、z、...、zである、サブネットワーク指標10001を有するファイルを識別する。新しいノードxは、次いで、その新しいノードxがそれらの識別されたファイルのうちどれを現在記憶していないかを識別する。新しいノードxは、次いで、ノードyおよびそのリーフセットz、z、...、zと、新しいノードxが現在記憶していない、識別されたそれらのファイルとを要求して、それらを受信して、受信されたファイルを記憶する。したがって、この例から、図9の方法900は、新しいサブネットワークのノードが分解されたPastryネットワーク内の既存のサブネットワークからファイルを獲得するような形で修正され得る点を理解されよう。
【0195】
新しいサブネットワークのノードが分解されたChordネットワーク内またはPastryネットワーク内の既存のサブネットワークからファイルを獲得するのを可能にするための上述の実施形態から、新しいサブネットワークのノードが既存のサブネットワークからファイルを獲得するのを可能にするためのChord固有の方法およびPastry固有の方法は、任意のタイプのP2Pネットワークに適用可能であるようにさらに一般化され得る点を理解されよう。一実施形態では、新しいサブネットワークのノードが分解されたP2Pネットワーク内の既存のサブネットからファイルを獲得するのを可能にするめの方法は、(1)サブネットワーク指標をサポートする、新しいサブネットワーク内の新しいノードによって、サブネットワーク指標をサポートする、既存のサブネットワーク内の最も近いノードを探索するステップと、(2)識別された最も近いノードの近隣のセットを取得するステップと(例えば、この近隣のセットは、前任/後任の組合せ、リーフセット、または1つもしくは複数のノードの任意のその他の適切なセットであってよい)、(3)近隣のセットの(1つまたは複数の)ノードから、サブネットワーク指標を有するファイルを識別するステップと、(4)新しいノードに現在記憶されていない、識別されたファイルの少なくとも一部を要求、受信、および記憶するステップとを含む。
【0196】
本明細書では、サブネットワークとサブネットワーク指標との間のマッピングが1対1、または少なくとも1対1に比較的近い(例えば、1つまたは複数のサブネットワークには複数のサブネットワーク指標が割り当てられている可能性があるが、依然として、サブネットワーク指標のセット全体のほんの一部である、例えば、サブネットワーク指標のうちの1つまたは複数は、複数のサブネットワークに割り当てられることが可能であるが、依然として、複数のサブネットワーク指標が割り当てられたサブネットワークのセット全体のほんの一部である)実施形態に関して主に示され、説明されているが、その他の実施形態では、サブネットワーク/サブネットワーク指標の割当ての間の重複は増分されてよい。これは、ファイルダウンロードが、ネットワーク間ではなく、ネットワーク内である確率を増大し、したがって、ネットワークリソースの使用、パフォーマンス、および信頼性を改善するが、ネットワークリソースの使用、パフォーマンス、および信頼性の改善は、多数のファイルを複数の異なるサブネットワーク内に複数回記憶するために必要とされる記憶容量に関連する増大を犠牲にして獲得される。一実施形態では、サブネットワーク指標は、サブネットワークのメンバーシップのサイズに比例して割り当てられてよい(例えば、必要とされる記憶容量がサブネットワーク間で公平に分割されるように、より大きなメンバーシップを有するサブネットワークにはより多くのサブネットワーク指標が割り当てられてよい)。一実施形態では、極端な事例、それぞれのサブネットワークが分解されたP2Pネットワークのファイルのすべてを記憶するように、サブネットワーク指標のそれぞれがサブネットワークのそれぞれに割り当てられる。このように、ネットワークリソースの使用、パフォーマンス、および信頼性の改善は、記憶容量の増大のコストとのバランスを保つことができる。
【0197】
本明細書では、ファイルがサブネットワーク指標だけに基づいて、分解されたP2Pネットワークのサブネットワーク内に記憶される実施形態に関して主に示され、説明されているが、その他の実施形態では、ファイルは、需要または任意のその他の適切な基準に基づいてなど、サブネットワーク指標に加えて、その他の基準に基づいて、分解されたP2Pネットワークのサブネットワーク内に記憶されることも可能である。一実施形態では、特定のサブネットワーク内で需要がある(あるいは、特定の数のサブネットワークもしくはサブネットワークの特定のセットを通して、または分解されたP2Pネットワーク全体を通してすら需要があると見なされる)ファイルは、(そのファイルに関連するサブネットワーク指標を有する(1つまたは複数の)サブネットワーク内に記憶されることに加えて)ローカルサブネットワーク内に記憶され得る。1つのそのような実施形態では、ノードがファイルを探索するとき、ノードは、そのローカルサブネットワーク、ならびにそのファイルに関連するサブネットワーク指標を有する(1つまたは複数の)サブネットワークを探索することになる)。この場合、ファイルがローカルサブネットワーク内に記憶されている場合、探索を実行しているノードは、ローカルサブネットワークから、または、そうでない場合、ファイルのサブネットワーク指標をサポートするサブネットワークからそのファイルを取得することになる。分解が(少なくとも一部)地理的基準に基づく、分解されたP2Pネットワークでは、これは、記憶コストの点でより高価な可能性はあるが、ネットワークコストの点で効率的であろう。この実施形態では、ファイルは、ファイルのサブネットワーク指標をサポートする(1つまたは複数の)サブネットワークから依然として利用可能であると同時に、(例えば、ファイルの需要がローカルサブネットワーク内または分解されたP2Pネットワークを通して衰えたときなど、後の時点で)ローカルサブネットワークからパージされることが可能である。そのような実施形態では、需要は任意の適切な形で測定または判断され得る点を理解されよう。
【0198】
本明細書では、サブネットワーク指標がハッシュ関数の出力であるKビットフィールドである実施形態に関して主に示され、説明されているが、その他の実施形態では、分解されたP2Pネットワークのサブネットワークに関連するサブネットワーク指標は、ハッシュ関数を使用せずに判断され得る。1つのそのような実施形態では、例えば、サブネットワークのサブネットワーク指標は、自然指標(natural index)を使用して設定され得る。一例として、P2Pネットワーク内に書籍を電子的に記憶することを望むライブラリの事例を考慮する。この例では、サブネットワークは、数理サブネットワーク、物理サブネットワークなど、学科によって構成され得る。この例では、使用すべき自然指標がデューイ十進法になるのは、デューイ十進法を使用することによって、当然、数理書籍を数理サブネットワーク内に記憶させ、物理書籍を物理サブネットワーク内に記憶させ、以下同様になるためである。加えて、物理学部が数理書籍のうちのいくつかを物理サブネットワーク内にローカルに記憶することを望む場合など、特定の学部にとって関心のある書籍が他のサブネットワーク内に記憶されることも可能である。デューイ十進法に関して主に示され、説明されているが、その他のタイプのアプリケーションにおいて様々な他の自然指標が使用され得る点を理解されよう。
【0199】
P2Pネットワーク分解機能は、P2Pネットワークに多数の利点を提供する。
【0200】
P2Pネットワーク分解機能は、P2Pネットワークをサブネットワークに分解することを可能にすることによって、P2Pネットワークのスケーラビリティを改善する。
【0201】
P2Pネットワーク分解機能は、P2Pネットワーク内のファイル探索パフォーマンスを改善する。ノードがファイルを探査しているとき、ファイルは、そのノードのローカルサブネットワーク以外のサブネットワークに、例えば、そのローカルサブネットワーク以外のターゲットサブネットワークに位置特定される場合がある。第1のファイル探索は、ノードのローカルサブネットワークからターゲットサブネットワークに移動することができるが、そのファイルを位置特定するために必要とされるすべての後続の探索メッセージは、依然として、ターゲットサブネットワーク内にとどまることになる。したがって、P2Pネットワークの分解が「距離」に基づく場合、(ターゲットネットワークの外部の第1の探索メッセージを除いて)探索メッセージのすべてはターゲットサブネットワーク内に位置特定され、したがって、それらの探索メッセージが移動する距離は最小限に抑えられる。これは、(例えば、Chordネットワークなど)そのアーキテクチャにおいて地理的位置が明らかにされないP2Pネットワークのパフォーマンスを改善することになる。位置基準/距離基準はサブネットワーク固有である可能性があるため、これは、位置基準/距離基準の限定された使用をサポートできるP2Pネットワークのパフォーマンスも改善することになる。例えば、近接性基準をサポートするPastryネットワークでは、近接性基準は同じサブネットワーク内のノードに関してだけ画定される必要がある。この例では、サブネットワークが小さな地理的領域をカバーする極端な事例では、そのサブネットワーク内の近接性基準は定数に設定されてよく(すなわち、サブネットワーク内のすべてのノードは同じ距離を有する)、これは、ネットワーク管理者が近接関数を定義する作業を軽減することになる。
【0202】
P2Pネットワーク分解機能は、ノードIDに関して、所与のノードの近接ノードが同じサブネットワークに属するように提供される。結果として、ノードがネットワークに参加するとき、またはネットワークを退去するとき、近接ノード同士の間の更新メッセージおよびファイル転送は、同じサブネットワーク内にとどまる。P2Pネットワークの分解が地形に基づく場合、更新メッセージおよびファイル転送が移動する距離は最小限に抑えられ、それによって、ノード同士の間でそのような情報を伝搬するために必要とされる時間を最小限に抑え、ノード同士の間でそのような情報を伝搬するために消費されるネットワークリソースの量を削減する。分解がその他の分解基準に基づく場合、他の利点が実現される。したがって、P2Pネットワークのパフォーマンスは改善される。
【0203】
P2Pネットワーク分解機能は、P2Pネットワークが地形、関心共同体などのうちの1つまたは複数、ならびにそれらの様々な組合せに基づいてなど、任意の適切な分解基準に基づいて分解されるのを可能にする。これは、P2Pネットワークの効率的かつ頑強な分解を可能にする。
【0204】
P2Pネットワーク分解機能は、それぞれのファイルが指定されたサブネットワークに記憶されることを可能にし、オプションで、ファイルのうちのいくつかまたはすべてが複数のサブネットワーク内に記憶されることも可能にできる(例えば、ファイルの追加のコピーは、指定されたサブネットワークに加えて、1つまたは複数のサブネットワークに記憶され得る)。これは、P2Pネットワークのパフォーマンスと信頼性とを改善する。
【0205】
P2Pネットワーク分解機能は、本明細書で提供されるP2Pネットワーク分解機能の説明を考慮して、当業者に明らかになる多数のその他の利点を提供する。
【0206】
本明細書では、制御ネットワークを使用してP2Pネットワーク分解機能が提供される実施形態に関して主に示され、説明されているが、P2Pネットワーク分解は、制御ネットワークを使用せずに提供されることも可能である。一実施形態では、例えば、制御ネットワークを使用するのではなく、サブネットワークのそれぞれは、1つまたは複数の永続的にアクティブなノードを有するように構成され、この場合、それらの永続的にアクティブなノードの識別は、ノードのそれぞれがノード、サービス、およびその他の制御情報を探索できるように、P2Pネットワークのノードのすべてに利用可能にされる。永続的にアクティブなノードの識別は、ネットワークマップに拡張を提供して、ウェブサーバを経由してなど、任意の適切な形ですべてのノードに利用可能にされ得る。
【0207】
本明細書では、P2PネットワークがChordネットワークである実施形態に関して主に示され、説明されているが、P2Pネットワーク分解機能は、Pastry、Tapestryなど、その他のタイプのP2Pネットワーク内で実施され得る。
【0208】
本明細書では、P2Pネットワーク分解機能が主に示され、説明されているが、P2Pネットワーク分解機能の原理は、併合されたP2Pネットワークを形成するためにコンポーネントP2Pネットワークを併合する目的で、P2Pネットワーク併合機能を提供するために適用されることも可能である。併合されたP2Pネットワークは、併合されたP2Pネットワークのコンポーネントネットワークのそれぞれが分解されたP2Pネットワークのサブネットに類似であるという点で、分解されたP2Pネットワークに類似する。コンポーネントP2Pネットワークは、同じP2P技術のものであってよく、または異なるP2P技術のものであってもよい。P2Pネットワークを分解するとき、(鍵空間およびオブジェクトIDハッシュ関数は分解されている元のP2Pネットワークから引き継がれているため)P2Pネットワークは、サブネットワークのすべてが同じ鍵空間と同じオブジェクトIDハッシュ関数とを使用するように分解され得る。しかし、併合されたP2Pネットワークを形成するためにコンポーネントP2Pネットワークを併合するとき、コンポーネントネットワークは異なる鍵空間と異なるオブジェクトIDハッシュ関数とを使用して併合されている可能性が高い。結果として、併合されたP2Pネットワークを形成するためにコンポーネントP2Pネットワークを併合することは、以下の考慮事項のうちの1つまたは複数を考慮に入れて実行され得る。
【0209】
P2Pネットワーク併合機能の場合、コンポーネントネットワークのすべては、(例えば、コンポーネントネットワークのうちの1つのハッシュ関数を選択すること、またはコンポーネントネットワークによって使用されることになる、いくつかのその他の適切なハッシュ関数を選択することによって)ネットワーク指標を計算する際に同じハッシュ関数を使用すべきである。
【0210】
P2Pネットワーク併合機能の場合、コンポーネントネットワークのすべては、同じファイル命名規則をサポートすべきであり、ノードが別のコンポーネントネットワーク内の別のノードからファイルを要求するとき、異なるコンポーネントネットワークは異なるハッシュ関数を使用する可能性が高いため、ファイル名のハッシュ値ではなく、ファイルのファイル名が使用されるべきである。
【0211】
P2Pネットワーク併合機能の場合、制御ネットワークは、それぞれのノードが特定のコンポーネントネットワーク(例えば、その全体が参照により本明細書に組み込まれている「METHOD AND APPARATUS FOR LOCATING SERVICES WITHIN PEER−TO−PEER NETWORKS」という表題の米国特許出願第XX/XXX,XXX号(整理番号第Chu19−43号(ALU/130209))で示され、説明されるサービス位置特定機能を有するChordネットワーク)に属する他のノードを探索することを可能にするサービス位置特定機能をサポートするP2P技術を使用すべきである。
【0212】
P2Pネットワーク併合機能の場合、コンポーネントネットワークは、異なる鍵空間と異なるハッシュ関数とを使用する可能性が高い。併合されたP2Pネットワークの2つのコンポーネントネットワークが異なる鍵空間とハッシュ関数とを使用するとき、コンポーネントネットワークの両方に参加するノードは、2つの異なるノードIDを有することになり、2つのコンポーネントネットワークに関する異なるファイルを記憶することになり、さらに、1つのコンポーネントネットワーク内の(ノードIDに関して)近接ノードである2つのノードは、別のコンポーネントネットワーク内の近接ノードでない場合がある。結果として、コンポーネントネットワークに新しいネットワーク指標が割り当てられるとき、そのコンポーネントネットワークは、ネットワークに迅速にポピュレートするために、上述の手順を使用することができず、むしろ、ファイルは、関連するシード処理ノードを介してコンポーネントネットワーク内にロードされることになる。
【0213】
図10は、本明細書で説明される機能を実行する際に使用するのに適したコンピュータのハイレベルブロック図を示す。図10に示されるように、コンピュータ1000は、プロセッサ要素1002(例えば、中央処理装置(CPU)または(1つもしくは複数の)他の適切なプロセッサ)と、メモリ1004(例えば、ランダムアクセスメモリ(RAM)、読出し専用メモリ(ROM)など)と、サービス位置検索モジュール/プロセス1005と、様々な入出力装置1006(例えば、(キーボード、キーパッド、マウスなどの)ユーザ入力装置、(ディスプレイ、スピーカなどの)ユーザ出力装置、入力ポート、出力ポート、受信機、送信機、および記憶装置(例えば、テープドライブ、フロッピー(登録商標)ドライブ、ハードディスクドライブ、コンパクトディスクドライブなど))とを含む。
【0214】
本明細書で示され、説明される機能は、ソフトウェアの形で、かつ/あるいは、例えば、汎用コンピュータ、1つもしくは複数の特定用途向け集積回路(ASIC)、および/または任意のその他のハードウェア均等物を使用して、ソフトウェアとハードウェアの組合せの形で実施され得る点に留意されたい。一実施形態では、サービス位置検索プロセス1005は、メモリ1004内にロードされて、本明細書において上で議論された機能を実施するために、プロセッサ1002によって実行されることが可能である。したがって、(関連するデータ構造を含めて)サービス位置検索プロセス1005は、コンピュータ可読記憶媒体またはコンピュータ可読キャリア、例えば、RAMメモリ、磁気ドライブもしくは磁気ディスケットまたは光ドライブもしくは光ディスケットなどの上に記憶され得る。
【0215】
ソフトウェアとして実施される、本明細書で議論された機能の一部は、任意の適切な形で(例えば、ノードの製造の間に提供される、ノードにおいて管理者によってロードされる、ウェブサーバまたはその他の適切なソースからダウンロードされるなど、ならびにそれらの様々な組合せで)ピアツーピアネットワークのノード上で構成され得ることが想到される。ソフトウェア方法として、本明細書で議論されたステップのうちのいくつかは、例えば、様々な方法ステップを実行するために、プロセッサと協働する回路など、ハードウェア内で実施され得ることが想到される。本明細書で説明された機能/要素の一部は、コンピュータプログラム製品として実施されることが可能であり、コンピュータ命令は、コンピュータによって処理されるとき、本明細書で説明された方法および/または技術が起動されるか、または、そうでない場合、提供されるように、コンピュータの動作を適合させる。本発明の方法を起動させるための命令は、固定媒体内もしくは取外し可能媒体内に記憶されることが可能であり、データストリームを経由してブロードキャスト内もしくはその他の単一の信号伝達媒体内で送信されることが可能であり、かつ/またはそれらの命令に従って動作するコンピューティングデバイス内のメモリ内に記憶されることが可能である。
【0216】
本発明の態様は、請求項で指定される。本発明のそれらの態様およびその他の態様は、以下の番号付けされた条項において指定される:
1.ノードが、複数のサブネットワークを含む、分解されたピアツーピア(P2P)ネットワークに参加するのを可能にするための方法であって、
分解されたP2Pネットワークの複数のサブネットワークに対する複数のサブネットワーク指標のマッピングを含むネットワークマップを、分解されたP2Pネットワークに参加することを要求しているノードに向けて伝搬するステップを含む、方法。
2.分解されたP2Pネットワークの分解をネットワークマップ内で符号化するステップ
をさらに含む、第1項に記載の方法。
3.分解されたP2Pネットワークの分解が、少なくとも1つの分解基準に基づく、第1項に記載の方法。
4.少なくとも1つの分解基準が、ノードの地理的位置および関心共同体のうちの少なくとも1つを含む、第3項に記載の方法。
5.サブネットワークのそれぞれに関して、サブネットワークがサブネットワークにマッピングされたサブネットワーク指標のうちの1つまたは複数を有する、第1項に記載の方法。
6.ネットワークマップが、
分解されたP2Pネットワーク内にファイルを記憶するため、または分解されたP2Pネットワーク内でファイルを位置特定するためのオブジェクト識別子を生成する際にノードによって使用するのに適したハッシュ情報、
サブネットワークのそれぞれに関して、サブネットワークのうちのどれに参加するかを決定する際にノードによって使用するのに適した1つまたは複数の記述子、および
ネットワークマップ管理情報のうちの少なくとも1つをさらに含む、第1項に記載の方法。
7.ノードが、複数のサブネットワークを含む、分解されたピアツーピア(P2P)ネットワークに参加するのを可能にするための方法であって、方法が、
分解されたP2Pネットワークのネットワークマップを獲得する際に使用するように構成されたメッセージをノードから開始するステップと、
分解されたP2Pネットワークのネットワークマップをノードにおいて受信するステップとを含み、
ネットワークマップが、分解されたP2Pネットワークの複数のサブネットワークに対する複数のサブネットワーク指標のマッピングを含む、方法。
8.要求が、
分解されたP2Pネットワークの制御ネットワークの少なくとも1つのノード、および
ネットワークデバイスのうちの少なくとも1つに向けて開始される、第7項に記載の方法。
9.要求が分解されたP2Pネットワークの制御ネットワークの少なくとも1つのノードに向けて開始されるとき、要求が制御ネットワーク内のノードの前任ノードまたは制御ネットワーク内のノードの後任ノードに向けて開始される、第8項に記載の方法。
10.分解されたP2Pネットワークの分解が、少なくとも1つの分解基準に基づく、第7項に記載の方法。
11.少なくとも1つの分解基準が、ノードの地理的位置および関心共同体のうちの少なくとも1つを含む、第10項に記載の方法。
12.サブネットワークのそれぞれに関して、サブネットワークが、サブネットワークにマッピングされたサブネットワーク指標のうちの1つまたは複数を有する、第7項に記載の方法。
13.ネットワークマップが、
分解されたP2Pネットワーク内にファイルを記憶するため、または分解されたP2Pネットワーク内でファイルを位置特定するためのオブジェクト識別子を生成する際にノードによって使用されるように構成されたハッシング情報、
サブネットワークのそれぞれに関して、サブネットワークのうちのどれに参加するかを決定する際にノードによって使用するように構成された1つまたは複数の記述子、および
ネットワークマップ管理情報のうちの少なくとも1つをさらに含む、第7項に記載の方法。
14.分解されたP2Pネットワークの制御ネットワークに参加するための要求を開始するステップであって、制御ネットワークがP2Pネットワークである、開始するステップと、
分解されたP2Pネットワークのネットワークマップを獲得する際に使用するように構成されたメッセージを制御ネットワークの少なくとも1つのノードに向けて伝搬するステップと
をさらに含む、第7項に記載の方法。
15.ノードが、複数のサブネットワークを含む、分解されたピアツーピア(P2P)ネットワーク内のファイルを管理することを可能にするための方法であって、
ファイルのサブネットワーク指標を計算するステップと、
ファイルのサブネットワーク指標に関連するサブネットワークのうちの1つを識別するステップと、
サブネットワークのうちの識別された1つのアクティブノードを識別するステップと、
分解されたP2Pネットワーク内のファイルを管理するためにアクティブノードを使用するためのプロセスを開始するステップとを含む、方法。
16.ファイルのサブネットワーク指標が、ハッシュ関数とファイルのファイル名とを使用して計算される、第15項に記載の方法。
17.複数のサブネットワークが、ファイルのサブネットワーク指標に関連しているとして識別されるとき、複数のサブネットワークのそれぞれのアクティブノードが識別されて、ファイルを管理するために複数のサブネットワークの識別されたアクティブノードのそれぞれを使用するような形でファイルを管理するためのプロセスが開始される、第15項に記載の方法。
18.ファイルのサブネットワーク指標に関連するサブネットワークのうちの1つを識別するステップが、
ファイルのサブネットワーク指標を使用して、ネットワークマップを探索するステップを含み、
ネットワークマップが、サブネットワークのそれぞれに関して、1つまたは複数のサブネットワーク指標に対するサブネットワークのマッピングを含む、第15項に記載の方法。
19.ファイルを管理するステップが、分解されたP2Pネットワーク内にファイルを記憶するステップを含む、第15項に記載の方法。
20.ファイルを管理するためのプロセスが、ファイルをサブネットワークのうちの識別された1つの識別されたアクティブノード上に記憶させるためのプロセスを含む、第19項に記載の方法。
21.ファイルをサブネットワークのうちの識別された1つのアクティブノードに向けて伝搬するステップ
をさらに含む、第20項に記載の方法。
22.ファイルをノードがメンバであるサブネットワークのうちの1つの中に記憶させるためのプロセスを開始するステップ
をさらに含む、第19項に記載の方法。
23.ファイルを管理するステップが、分解されたP2Pネットワーク内でファイルを位置特定するステップを含む、第15項に記載の方法。
24.ファイルを管理するステップが、サブネットワークのうちの識別された1つの中のファイルを探索するためにアクティブノードを使用するためのプロセスを含む、第23項に記載の方法。
25.サブネットワークのうちの識別された1つの中のファイルを探査するためにアクティブノードを使用するためのプロセスを開始するステップが、
アクティブノードに対してサブネットワークのうちの識別された1つの中のファイルを探索する要求をアクティブノードに向けて伝搬するステップを含む、第24項に記載の方法。
【0217】
本発明の教示を組み込んだ様々な実施形態が本明細書で示され、説明されているが、当業者は、依然としてこれらの教示を組み込む、多くのその他の様々な実施形態を容易に考案することができる。

【特許請求の範囲】
【請求項1】
ノードが、複数のサブネットワークを含む、分解されたピアツーピア(P2P)ネットワークに参加するのを可能にするための方法であって、
分解されたP2Pネットワークの複数のサブネットワークに対する複数のサブネットワーク指標のマッピングを含むネットワークマップを、分解されたP2Pネットワークに参加することを要求しているノードに向けて伝搬するステップを含む、方法。
【請求項2】
分解されたP2Pネットワークの分解をネットワークマップ内で符号化するステップ
をさらに含む、請求項1に記載の方法。
【請求項3】
分解されたP2Pネットワークの分解が、少なくとも1つの分解基準に基づき、少なくとも1つの分解基準が、ノードの地理的位置および関心共同体のうちの少なくとも1つを含む、請求項1に記載の方法。
【請求項4】
サブネットワークのそれぞれに関して、サブネットワークがサブネットワークにマッピングされたサブネットワーク指標のうちの1つまたは複数を有する、請求項1に記載の方法。
【請求項5】
ネットワークマップが、
分解されたP2Pネットワーク内にファイルを記憶するため、または分解されたP2Pネットワーク内でファイルを位置特定するためのオブジェクト識別子を生成する際にノードによって使用するのに適したハッシュ情報、
サブネットワークのそれぞれに関して、サブネットワークのうちのどれに参加するかを決定する際にノードによって使用するのに適した1つまたは複数の記述子、および
ネットワークマップ管理情報のうちの少なくとも1つをさらに含む、請求項1に記載の方法。
【請求項6】
ノードが、複数のサブネットワークを含む、分解されたピアツーピア(P2P)ネットワークに参加するのを可能にするための方法であって、方法が、
分解されたP2Pネットワークのネットワークマップを獲得する際に使用するように構成されたメッセージをノードから開始するステップと、
分解されたP2Pネットワークのネットワークマップをノードにおいて受信するステップとを含み、
ネットワークマップが、分解されたP2Pネットワークの複数のサブネットワークに対する複数のサブネットワーク指標のマッピングを含む、方法。
【請求項7】
要求が分解されたP2Pネットワークの制御ネットワークの少なくとも1つのノードに向けて開始され、少なくとも1つのノードが、制御ネットワーク内のノードの前任ノードまたは制御ネットワーク内のノードの後任ノードのうちの少なくとも1つを含む、請求項6に記載の方法。
【請求項8】
分解されたP2Pネットワークの分解が、少なくとも1つの分解基準に基づき、少なくとも1つの分解基準が、ノードの地理的位置および関心共同体のうちの少なくとも1つを含む、請求項6に記載の方法。
【請求項9】
ネットワークマップが、
分解されたP2Pネットワーク内にファイルを記憶するため、または分解されたP2Pネットワーク内でファイルを位置特定するためのオブジェクト識別子を生成する際にノードによって使用するように構成されたハッシュ情報、
サブネットワークのそれぞれに関して、サブネットワークのうちのどれに参加するかを決定する際にノードによって使用するように構成された1つまたは複数の記述子、および
ネットワークマップ管理情報のうちの少なくとも1つをさらに含む、請求項6に記載の方法。
【請求項10】
ノードが、複数のサブネットワークを含む、分解されたピアツーピア(P2P)ネットワーク内のファイルを管理するのを可能にするための方法であって、
ファイルのサブネットワーク指標を計算するステップと、
ファイルのサブネットワーク指標に関連するサブネットワークのうちの1つを識別するステップと、
サブネットワークのうちの識別された1つのアクティブノードを識別するステップと、
分解されたP2Pネットワーク内のファイルを管理するためにアクティブノードを使用するためのプロセスを開始するステップとを含む、方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8A】
image rotate

【図8B】
image rotate

【図8C】
image rotate

【図8D】
image rotate

【図8E】
image rotate

【図9】
image rotate

【図10】
image rotate


【公表番号】特表2013−514591(P2013−514591A)
【公表日】平成25年4月25日(2013.4.25)
【国際特許分類】
【出願番号】特願2012−544577(P2012−544577)
【出願日】平成22年12月1日(2010.12.1)
【国際出願番号】PCT/US2010/058480
【国際公開番号】WO2011/075311
【国際公開日】平成23年6月23日(2011.6.23)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.YouTube
【出願人】(391030332)アルカテル−ルーセント (1,149)
【Fターム(参考)】