ピアツーピアリレーネットワークにおけるアイランドの復旧
ピアツーピアリレーを実装するための方法ならびに装置である。一実施形態では、ピアツーピアリレーネットワーク内のピアシステムにおけるアイランドの復旧方法は、ピアツーピアリレーネットワークにおいて、少なくとも1つのピアシステムを有するアイランドの存在を2つ以上検出するステップと、第1のアイランド内のピアシステムを第2のアイランド内のピアシステムに接続することによって、検出された2つのアイランドを結合するステップと、を有し、異なるアイランド内のピアシステム同士は接続されていない。
【発明の詳細な説明】
【技術分野】
【0001】
本願は、2003年10月20日に出願された米国仮特許出願第60/513,098号(「ピアツーピアリレーネットワーク(PEER-TO-PEER RELAY NETWORK)」の利益を主張し、本開示の内容を参照によりここに援用する。
【背景技術】
【0002】
代表的なクライアント−サーバネットワークにおいては、ネットワーク内の各クライアントが中央サーバとの接続を確立している。クライアントは、サーバからサービスおよびデータを要求する。クライアントは、別のクライアントと通信するために、サーバに要求を送信する。一般に、クライアントは、直接接続を相互に確立することはない。N台のクライアントを有するクライアント−サーバネットワークでは、各クライアントはサーバへの接続を1つ有し、サーバは各クライアントそれぞれへの接続をNつ有する。例えば、図31Aに示すように、6台のクライアントを有するクライアント−サーバネットワークでは、各クライアントはサーバへの接続を1つ有し、サーバは各クライアントそれぞれへの接続を6つ有する。
【発明の開示】
【発明が解決しようとする課題】
【0003】
代表的なピアツーピアネットワーク(または「P2Pネットワーク」)においては、ピアツーピアネットワークの各メンバ(またはピア)は、ほかのメンバそれぞれと接続を確立する。メンバは、中央サーバを用いる代わりに、(例えば、メンバがサーバを介して対話する代表的なクライアント−サーバネットワークと対比すると)この直接のピアツーピア接続を用いて、直接他のメンバにデータを送信したり、他のメンバからデータを要求する。通常、ネットワーク内の各メンバはネットワークにおいて同じ役目を担っており、メンバは(ネットワークメンバとして)一般に同等であるとみなされる。Nのピアを有するピアツーピアネットワークでは、各ピアは、他のピアへの接続をN−1個有する。例えば、図31Bに示すように、6つのピアを有するピアツーピアネットワークでは、各ピアは、他のピアへの接続を5つ有する。
【0004】
一部のピアツーピアネットワークでは、サーバも、アドレス発見などの一部の集中サービスのために(例えば、ピアツーピアネットワークを構築するために接続を確立するために)メンバによって使用される)。
【課題を解決するための手段】
【0005】
本発明は、ピアツーピアリレーを実装するための方法ならびに装置を提供する。一実施形態では、ピアツーピアリレーネットワーク内のピアシステムにおけるアイランドの復旧方法は、ピアツーピアリレーネットワークにおいて、少なくとも1つのピアシステムを有するアイランドの存在を2つ以上検出するステップと、第1のアイランド内のピアシステムを第2のアイランド内のピアシステムに接続することによって、検出された2つのアイランドを結合するステップと、を有し、異なるアイランド内のピアシステム同士は接続されていない。
【0006】
一実施形態では、ピアツーピアリレーネットワーク内のサーバは、ピアツーピアリレーネットワークにおいて、少なくとも1つのピアシステムを有するアイランドの存在を2つ以上検出する手段と、第1のアイランド内のピアシステムを第2のアイランド内のピアシステムに接続することによって、検出された2つのアイランドを結合する手段と、を有し、異なるアイランド内のピアシステム同士は接続されていない。
【発明を実施するための最良の形態】
【0007】
本発明は、ピアツーピアリレーを実装するための方法ならびに装置を提供する。一実施形態では、ピアツーピアネットワークを形成するために複数のコンピュータシステムが接続される。各コンピュータシステムは、所定の台数まで他のコンピュータシステムに接続される。コンピュータシステムは、通信を行うために、接続されたシステムの各々にメッセージを送信する。
【0008】
あるコンピュータシステムが別のコンピュータシステムからメッセージを受信すると、受信したコンピュータシステムは、そのピアツーピアリレーネットワークのリレー手順またはルールに従って、他のコンピュータシステムにメッセージを送信またはリレーする。メッセージは、リレールールに従って、ネットワーク全体にわたり、全メンバコンピュータシステムに伝達される。
【0009】
図1は、ピアツーピアリレーネットワーク100の一実施形態の表現を示す。ピアツーピアリレーネットワークは、グリッドとも呼ばれることがある。図1では、ピアツーピアリレーネットワークを形成するために、10つのピアシステム105A…J(「ピア」とも呼ばれる)のグループが接続されている。各ピアシステム105は、ソニー・コンピュータエンタテインメント株式会社が販売しているプレイステーション2(登録商標)ゲームコンソールなどのネットワーク対応ゲームコンソールであり、ネットワークアダプタを備えている。ピアシステム105は、直接接続されている(有線接続または無線接続など)か、あるいは(例えば、イントラネットまたはインターネット等の公共IPネットワークを介して)間接的に接続されている。一実施形態では、ピアシステム105は、UDP接続またはTCP接続を使用して接続されている。ピアシステム105は、チャット環境またはオンラインゲームなどのネットワークの環境または活動を支援するためにデータを交換する。
【0010】
各ピア105は、インターネットを介したUDP接続またはTCP接続などの中央サーバ110への接続も有する(サーバ110への接続は図1に図示されていない)。サーバ110は、接続されているピアシステム105に集中サービスを提供しているサーバコンピュータシステムである。一実施形態では、サーバは、ピアシステムのアドレスディレクトリを提供しており、どのピアシステム同士が接続されているかをトラッキングしている。ほかのサーバサービスの例には、認証、プレーヤのマッチング、およびピアシステムのアドレスのトラッキングなどがあるが、これらに限定されない。後述するように、一部の実装では、サーバは、複数の独立したピアツーピアリレーネットワークまたは関連するピアツーピアリレーネットワークに対応している。一実施形態では、サーバは、クライアントを環境に分割または分類して、データを適切にフィルタリングする複数の環境またはワールドに対応している。一実施形態では、サーバは、同時係属中かつ譲受人が共通する、 に出願された米国特許出願番号第10/ 号「構成スイッチング:ネットワーク通信アーキテクチャ間の動的変更(Configuration Switching:Dynamically Changing Between Network Communication Architectures)」、ならびに に出願された米国特許出願番号第10/ 号「マルチユーザアプリケーションプログラミングインタフェース(Multi-User Application Programming Interface)」に記載されているサーバの1つ以上の態様を含む。これらの開示を参照によりここに援用する。別の実施形態では、ピアは、中央サーバを使用しない(例えば、直接通信によってグリッドを構築し、データをリレーする)。
【0011】
ネットワーク100の接続上限は3である。接続上限は、サーバによって設定され、各ピア105がグリッド内で持つことができる接続の最大数を定義している。別の実施形態では、1つのピア(例えばグリッドを確立するピア)が接続上限を設定するか、または複数のピアが接続上限を協議して決定する。図1では、接続上限は3であり、各ピア105は接続を3つ有している。ピアシステムA〜Jは、それぞれ他のピアへの接続を3つ有する(ピアシステム105Aは、ピアシステムAまたはピアAとも呼ばれる)。ネットワーク100は3接続ピアツーピアリレーネットワークであり、このため各ピア105は他のピアへの接続を3つ有する。
【0012】
ピア105は、メッセージをネットワーク100全体にブロードキャストすることによって通信を行う。ピア105は、ネットワーク100のリレールールに従って、接続されたピア105に受信メッセージをリレーすることによってメッセージを伝達する。この実装では、リレールールにより、ピア105はピア105に接続されているピア105のそれぞれにメッセージをリレーすることが規定されている。この例外に、(i)ピア105は、ピア105が既にリレーしているメッセージをリレーしない、(ii)ピア105は、そのリレーピア105がそこからメッセージを受信したピア105にメッセージを返さない、の2つがある。また、一実施形態では、ピア105は、そのリレーピア105がそこから既にメッセージを受信しているピア105にそのメッセージをリレーしない(リレーピア105がメッセージをリレーする前に、そのリレーピア105が複数のピア105からメッセージを受信する場合など)。別の実施形態では、別のルールまたは追加のルールが使用されてもよい。リレールール(およびその他のルール)は、サーバによって規定されるか、あるいはピアシステム(またはそのシステムソフトウェア)によって予め設定されている。別の実施形態では、例えばルールの更新情報が含まれるメッセージをグリッド全体に伝達することによって、ルールが動的に変更されうる。
【0013】
ネットワーク100の一アプリケーションでは、ピア105はネットワークゲームをプレイしている。ゲームの進行中に、ピア105は、ピア105が発生させる動作または事象を表す更新メッセージを生成する。例えば、プレーヤのコンピュータシステム(ピアAなど)でゲームソフトウェアを実行中に、コンピュータシステムは、ほかのプレーヤのコンピュータシステムによって使用される、移動または発射などのゲーム中の動作を表す(例えば、プレーヤの位置を更新する)更新データを生成する。更新が有効となるには、各ピア105が、更新を行うピア105から更新を受信することが必要である。ピア105は、ネットワーク100全体に更新メッセージをリレーして、各ピア105にメッセージを伝達する。
【0014】
一例では、ピアAは、他のピアに送信する更新を有している。ピアAは、更新データ、ピアAが更新の発信元であることを示す識別子、およびこのメッセージを、ピアAが送出する他のメッセージと区別し、相対シーケンスを提供するシーケンス識別子を有する更新メッセージを作成する。ピアAは、ピアAの被接続ピアB,C,Dにメッセージを送信する。ピアBは、ピアAから受信したメッセージをピアD,Eに送信する。ピアBはピアAからメッセージを受信したため、ピアBはピアAにメッセージを送信しない。同様に、ピアCは、ピアAからのメッセージをピアG,Hに送信し、ピアDは、ピアAからのメッセージをピアB,Gに送信する。ピアBがピアDからメッセージを受信すると、ピアBは、(メッセージの識別子を使用して)同じメッセージであると認識するため、ピアBは再度メッセージをリレーしない。同様に、ピアDは、ピアBから受信したメッセージをリレーしない。ピア間でメッセージを転送するのに要する時間の点で、ピア間の接続が実質的に同じであると仮定すると、リレーの次の組において、ピアEは、ピアBからのメッセージをピアF,Iにリレーし、ピアGは、ピアCからのメッセージをピアD,Fにリレーし(またはいずれのメッセージがピアCに最初に到着したかによってはピアDからのメッセージをピアC,Fにリレーし)、ピアHは、ピアCからのメッセージをピアI,Jにリレーする。この時点で、全てのピアは、ピアAからの更新メッセージを受信している。しかし、ピアF,I,Jはメッセージを受信したばかりであるため、これらのピアはメッセージをリレーする。ピアFは、ピアEからのメッセージをピアG,Jにリレーし(またはいずれが最初に到着したかによってはピアGからのメッセージをピアE,Jにリレーし)、ピアIは、ピアEからのメッセージをピアH,Jにリレーし(またはいずれが最初に到着したかによってはピアHからのメッセージをピアE,Jにリレーし)、ピアJは、ピアHからのメッセージをピアF,Iにリレーする。この時点までに、全ピアは、メッセージを送信またはリレーしている。ピアは再度同じメッセージをリレーしないため、このメッセージの伝達が終了する。
【0015】
このようにして、メッセージがピアツーピアネットワーク100全体を伝達していく。ゲームに参加しているピアシステム105間でこのように更新情報が伝達されることが、ゲームおよびゲーム環境を支援している。ピアシステム105は、分散のために中央サーバ110を使用せずに、データをネットワーク100全体に配信することができる。さらに、各ピア105がほかのピア105の全てに直接接続されているというわけではなく、資源の節約が図られる。この結果、グリッド100は、(限られた数の他のクライアントと通信しさえすればよいため)各ピアのネットワーク帯域幅の必要条件を抑える一方で、任意の1台のクライアントからのデータを、(例えば、UDPソケットを使用して)グリッド内のほかの全ピアに迅速に伝達させることが可能となる。
【0016】
別の実施形態では、ピアツーピアリレーネットワークに含まれるピアシステムの数は上下してもよく、ネットワークの接続上限が異なっていてもよい。ピアの台数、接続上限、および接続を確立するためのルールによっては、全てのピアの全接続が使用されるわけではないこともあり、このため、利用可能な接続を有するピアが1つ(またはそれ以上)存在することもある。
【0017】
別の実施形態では、接続上限は可変である。一実施形態では、接続上限は各ピアシステムに固有であり、その場合、一部または全てのピアの接続上限が異なっていても、接続上限が異なるピアが存在しなくてもよい。各ピアは、自身の接続上限を設定するか、またはサーバによって接続上限を割り当てられる。一例では、ピアX,Yのそれぞれの接続上限が5であり、ピアZの接続上限が4であり、残りのピアの接続上限はそれぞれ3である。別の実施形態では、接続上限は動的である。この場合、サーバが、ネットワーク性能に基づくなどして、ピアの接続上限を調整する(例えば、ネットワークトラフィックが低い場合には、接続上限数が低く設定される)。別の実施形態では、ピアシステムの1つ以上が、それぞれ動的にそれぞれの接続上限を調整する。別の実施形態では、サーバが、特定のピアシステムの接続上限を動的に調整する(例えば、全ピアではなく一部のピアを調整する)。
【0018】
図2は、メッセージ205の一実施形態のブロック図を示す。メッセージ205は、ピアシステムによって、ピアツーピアリレーネットワーク内の他のピアに送信するために生成される。例えば、図1を参照すると、ピアAが他のピアに送信する更新メッセージを有する場合、ピアAはメッセージ205などのメッセージを作成する。メッセージ205には、アドレッシングデータ210、発信元識別子215、シーケンス値220、およびペイロードデータ230が含まれる。アドレッシングデータ210は、メッセージ205をそのピアから別のピアに送信するためのネットワークアドレッシング情報を含む。一実施形態では、アドレッシングデータ210は、送信側ピアのIPアドレスと、指定する受信側ピアのIPアドレスを含む。発信元識別子215は、メッセージ205を作成したピアを識別する。この識別子215は、ピアツーピアリレーネットワーク全体のピアに対し、ネットワークを介して伝達されているメッセージの発信元を示す。メッセージ205を受信するピアは、発信元識別子215を用いて、メッセージ205がネットワーク内のどのピアから送信されたかを決定することができる。シーケンス値220は、特定のメッセージ205を識別して、相対シーケンス情報を提供する。メッセージ205を受信するピアは、シーケンス値220を用いて、特定のメッセージを既に受信済みであるかを決定することができると共に、発信元識別子215が示すピアから送信されたメッセージの順序またはシーケンスを決定することができる。データ230は、メッセージ205のペイロードデータである。(例えば、ゲームにおける)更新メッセージの場合、ペイロードデータ230は、受信側ピアが使用する更新データである。代替の実装では、異なるタイプのメッセージが使用されてもよく、図2に示すものとは異なるフォーマットのメッセージが使用されてもよい(例えば、異なる情報や追加の情報を有する)。例えば、メッセージに、グリッドのメンバに発行(publish)しようとしているファイルまたはファイルの一部、ゲームデータのフレームなどのデータのフレーム、フレーム、または音声ファイルの一部が含まれていてもよい。受信ピアは、メッセージの各々に含まれるシーケンス値を使用して、ファイル全体を再構築することができる。別の例では、メッセージには、例えば、複数のグリッドに属しているピアによってリレーを行うために、メッセージが属しているグリッドを示す識別子などの付加的な識別情報が含まれてもよい。
【0019】
図3は、ピアツーピアリレーネットワークにおいて、ピアがメッセージをリレーする一実施形態のフローチャート300を示す。初期状態では、このピアは、ピアツーピアリレーネットワークにおいて1つ以上の他のピアシステムに接続されている。
【0020】
ブロック305において、ピアは、このピアと送信側ピア間の接続を介して、送信側ピアからメッセージを受信する。このメッセージには、図2のメッセージに示すように、発信元識別子、シーケンス値、およびペイロードデータ(更新データなど)が含まれる。
【0021】
ブロック310において、ピアは、受信メッセージをリレーする接続を選択する。ピアは、ピアツーピアリレーネットワークのリレールールに従って、ピアの利用可能な接続から接続を選択する。リレールールを適用した後、ピアが、ピアの接続の一部または全てを選択している場合もあれば、接続を1つも選択していない場合もある。
【0022】
ブロック315において、ピアは、選択した接続の各々にメッセージをリレーする。ピアは、選択した各接続のためにメッセージを作成する。ピアは、受信メッセージを使用するが、送信する各メッセージのアドレッシング情報を適宜更新する(例えば、接続のために送信側をこのピアに変更し、受信側を受信ピアに変更する)。したがって、ペイロードデータは変更されない。別の実施形態では、ピアは、メッセージにデータを追加するか、あるいはメッセージ内のデータを変更しうる。ピアは、作成したメッセージを適切な受信者に送信する。
【0023】
図4は、ピアツーピアリレーネットワークにおいて、ピアがリレールールの組に従ってメッセージをリレーする一実施形態のフローチャート400を示す。図4で使用するリレールールは、リレールールの組の例である。別の実施形態では、異なるリレールールまたは追加のリレールールを使用してもよい。初期状態では、リレーピアは、ピアツーピアリレーネットワークにおいてNの他のピアシステムに接続されている。例えば、図1に示すネットワークでは、ピアDは、3つの他のピアに接続されている(この場合N=3)。メッセージをリレーするための図4のリレールールは、以下の通りである。
1.メッセージを2回リレーしない
2.送信元にメッセージを返さない。
3.発信元ピアにメッセージをリレーしない
4.ルール1および2を適用した後に、利用可能な接続上のピアにメッセージをリレーする
【0024】
ブロック405において、リレーピアはメッセージを受信する。ブロック410において、リレーピアは、リレーピアが以前にこのメッセージを受信しているかどうかを決定する。リレーピアは、メッセージの識別データを、リレーピアが記憶している、以前に受信しているメッセージのデータと比較する。一実施形態では、各ピアは、受信済みのメッセージの発信元識別子およびシーケンス値の受信メッセージテーブルを維持している。リレーピアは、受信メッセージから発信元識別子およびシーケンス値を取得して、この情報を、リレーピアの受信メッセージテーブルに記憶されているデータと比較する。リレーピアが、リレーピアがこの受信メッセージを以前に受信していると決定した場合(例えば、ピアが、受信メッセージの発信元識別子およびシーケンス値を記憶している受信メッセージテーブルにエントリをみつけた場合など)、リレーピアは受信メッセージをリレーしない。別の実施形態では、リレーピアは、リレーピアが受信メッセージを以前にリレー済みであるかを確認して決定する。
【0025】
リレーピアがこの受信メッセージを以前に受信していないとリレーピアが決定した場合、ブロック412において、リレーピアは、このメッセージが受信されたことを記録する。一実施形態では、リレーピアは、リレーピアの受信メッセージテーブルに、受信メッセージの発信元識別子およびシーケンス値に対するエントリを追加する。この発信元識別子およびシーケンス値のエントリがテーブルに既に存在する場合、リレーピアはテーブルを変更しない。
【0026】
このメッセージが受信されたことを記録したら、ブロック415において、リレーピアはカウンタをセットする。リレーピアは、カウンタを使用して、リレーピアの利用可能な接続を1つずつ調べる。一実施形態では、リレーピアは、整数カウンタiを1にセットする。
【0027】
ブロック420において、リレーピアは、リレーピアが、カウンタが示す接続に接続されたピアからメッセージを受信したかどうかを決定する。受信メッセージには、受信メッセージの送信元を示すアドレッシング情報が含まれる。カウンタは接続を示しており、このため、接続されたピアとそのピアのアドレッシング情報を示すことになる。例えば、図1のピアDは3つの接続を有しており、ピアDは、各接続に数字を割り当ており、接続1にピアAが接続され、接続2にピアBが接続され、接続3にピアGが接続されている。このため、カウンタiが1の場合、ピアDは、受信メッセージのアドレッシング情報(送信元)を、ピアDに記憶されているピアAのアドレッシング情報と比較することによって、受信メッセージがピアAによって送信されたかどうかを調べる。受信メッセージが、カウンタが示す接続に接続されたピアによってリレーピアに送信された場合、リレーピアは、そのピアにメッセージをリレーしない。
【0028】
受信メッセージが、カウンタが示す接続に接続されたピアによってリレーピアに送信されたものではない場合、ブロック422において、リレーピアは、カウンタが示す接続に接続されたピアが受信メッセージの発信元ピアシステムであるかどうかを決定する。受信メッセージには、受信メッセージの発信元であるピア(メッセージのデータを最初に生成したピア、図2の発信元識別子215を思い出されたい)を示す情報が含まれる。カウンタが示す接続に接続されたピアが受信メッセージの発信元ピアシステムである場合、リレーピアはそのピアにメッセージをリレーしない。
【0029】
受信メッセージが、カウンタが示す接続に接続されたピアによってリレーピアに送信されたものではなく、かつカウンタが示す接続に接続されたピアが受信メッセージの発信元ピアシステムではない場合、ブロック425において、リレーピアは、その接続ピアにメッセージをリレーする。リレーピアは、示された接続のためにメッセージを作成する。リレーピアは受信メッセージのコピーを作成して、アドレッシング情報を適宜更新する(例えば、送信元をリレーピアに変更し、受信者を、示された接続に接続されているピアに変更する)。したがって、ペイロードデータは変更されない。リレーピアは、作成したメッセージを、示された接続を介して接続されたピアに送信する。
【0030】
ブロック430において、リレーピアは、全ての接続を確認したかどうかを決定する。リレーピアは、カウンタを、ピアツーピアリレーネットワーク内でリレーピアによって確立された接続の数と比較する。例えば、リレーピアは、カウンタiを値N(リレーピアが保持している接続の数)と比較する。リレーピアが全ての接続をチェックしている場合、リレーピアはこの受信メッセージのリレーを完了している。
【0031】
リレーピアが全ての接続のチェックを終えていない場合、ブロック435において、リレーピアはカウンタをインクリメントする。例えば、リレーピアは、カウンタiをi+1に設定する。リレーピアは、カウンタをインクリメントしたら、ブロック420に戻り、リレーピアが、インクリメントしたカウンタが示す接続に接続されたピアから受信メッセージを受け取ったかどうかを決定する。
【0032】
前述のように、別の実施形態では、異なるルールまたは追加のルールを使用しても、使用するリレールールがこれより少なくてもよい。一実施形態では、リレーピアは、送信元にメッセージを返す(例えば、これにより、送信元は、リレーピアがデータを変更しなかったことを確認することができる)。別の実施形態では、リレーピアは、メッセージの発信元であると示される(例えば、メッセージの発信元識別子によって示される)ピアにメッセージをリレーしない。別の実施形態では、リレーピアは、同じ被接続ピアに再度同じメッセージをリレーしない。別の実施形態では、リレーピアは、メッセージをリレーするために、利用可能な接続のサブセットを選択し、例えば、応答時間が最短のピアおよび応答時間が最長のピアなどを選択する。別の実施形態では、メッセージが一定回数しかリレーされないように、各ピアは、メッセージに格納されているホップカウントに従って全てのピアの被接続ピアにメッセージをリレーする。別の実施形態では、ピアは、限られた回数(2回以上)だけ同じメッセージをリレーする。
【0033】
図5は、ピアツーピアリレーネットワークを確立する一実施形態のフローチャート500を示す。初期状態では、図1のピアAおよびサーバ110などのピアシステムおよびサーバが配置されている。ブロック505において、ピアシステムはサーバへの接続をオープンする。ピアシステムは、ピアツーピアリレーネットワーク(またはグリッド)を確立するためにサーバに接続しようとしており、このピアシステムは、「確立ピア」と呼ぶことができる。サーバへの接続は、直接ネットワーク接続または間接ネットワーク接続でありえる。一実施形態では、ピアは、サーバが維持しているスペースのサブセクションあるいは複数のワールドまたは環境のうちの1つに割り当てられるか、あるいはそこに参加および登録する。サーバは、ピアが対話を続けるのを許可する前に、ピアを認証する。ブロック510において、ピアシステムはグリッド作成要求をサーバに送る。グリッド作成要求は、ピアの識別情報と、ピアが新しいピアツーピアリレーネットワークの確立をサーバに対して要求していることを示している。一実施形態では、この要求には、ピアがサーバに対して適用を要求する条件(例えばグリッドに参加するうえでの制約)も含まれる。別の実施形態では、この要求は、グリッドにおいて使用する接続上限およびルールの組(リレールールおよび接続ルールなど)を示している。ブロック515において、サーバは新しいグリッドを登録する。サーバは、確立済みのグリッドをトラッキングしているデータのテーブルまたはリストを保持している。サーバは、新しいグリッドのために新たにテーブルを作成し、このテーブルに要求元のピアを追加する。ブロック520において、サーバは、グリッドが確立されたという確認をピアに送信する。この確認には、ピアがグリッドにアクセスするうえで必要なあらゆる識別情報またはアクセス情報が含まれる。一実施形態では、この確認には、接続上限およびグリッドのルール(リレールールなど)が含まれる。
【0034】
図6は、ピアツーピアリレーネットワークにピアを接続する一実施形態のフローチャート600を示す。初期状態では、図1のピアAおよびサーバ110などのピアシステムおよびサーバによってピアツーピアリレーネットワークが確立されている。
【0035】
ブロック605において、ピアシステムがサーバに接続する。ピアシステムは、ピアツーピアリレーネットワーク(またはグリッド)に参加するためにサーバに接続しようとしており、このピアシステムは、「新規ピア」または「参加ピア」と呼ぶことができる。サーバへの接続は、直接ネットワーク接続または間接ネットワーク接続でありえる。一実施形態では、ピアは、サーバが維持しているスペースのサブセクションあるいは複数のワールドまたは環境のうちの1つに割り当てられるか、あるいはそこに参加および登録する。サーバは、ピアが対話を続けるのを許可する前に、ピアを認証する。
【0036】
ブロック610において、ピアは、サーバの利用可能なグリッドのうちからグリッドを選択する。一実施形態では、ピアは、利用可能なグリッドのリストを要求し、そのリストの中から選択する。別の実施形態では、ピアがサーバに接続すると、サーバは利用可能なグリッドのリストを自動的に提供する。一実施形態では、サーバは、ピアが登録しているワールドに対し、利用可能なグリッドのリストを提供する。また、サーバは、選択を支援する追加情報(既に各グリッドのメンバになっているピアなど)を提供してもよい。ピアはグリッドの選択をサーバに送る。
【0037】
ブロック615において、サーバは、選択されたグリッドに既に参加しているピアのアドレスを送信する。このアドレスは、グリッドメンバと通信する方法(例えばIPアドレス)を示している。アドレスは、サーバを介した接続でなく、グリッドメンバとのピア接続を確立するためのものである。選択されたグリッドがアクセスを制限しており、新しいピアが選択されたグリッドへの参加を許されない場合、サーバはピアにアドレスを提供せずに、ピアに別のグリッドを選択するように提案する。一実施形態では、サーバは、新しいピアへのアドレスと共に、選択されたグリッドの接続上限およびルールを提供する。
【0038】
ブロック620において、新規ピアは、グリッドの各メンバに参加メッセージを送信する。参加メッセージは、新規ピアのアドレスと、そのピアがグリッドに新規に加入することを示している。別の実施形態では、新規ピアは、ピアのアドレスおよびピアが利用可能な接続の数を示す接続利用可能メッセージを送信する(これは、後述するようにピアが切断する場合と同様である)。別の実施形態では、新規ピアは1つのグリッドメンバに参加メッセージを送信し、そのグリッドメンバがグリッドを介して参加メッセージをリレーし始める。
【0039】
ブロック625において、グリッドメンバは、参加メッセージを受信して、それぞれ新規ピアに参加応答を返信する。参加応答は、応答したピアが利用可能な接続を有するかどうかを示している。肯定応答は、応答したピアが利用可能な接続を有することを示している。否定応答は、応答したピアが利用可能な接続を有さないことを示している。応答したピアは、参加メッセージから得た新規ピアノアドレスを記録して、そのアドレスを使用して参加応答を送信する。新規ピアは参加応答を受信する。
【0040】
ブロック630において、新規ピアは、接続するグリッドメンバを選択する。新規ピアは、接続ルールの組を使用して、接続するピアを選択する。例えば、一実施形態では、新規ピアは、肯定応答を送信したピアを、新規ピアが肯定応答を受信した順に、グリッドの接続上限に達するまで選択する(例えば、接続上限が3の場合、新規ピアは、最初に受信した3つの肯定応答に対応するピアを選択する)。実装によって、異なる接続ルールの組が使用されてもよい。新規ピアは、選択したピアのそれぞれの応答時間を記憶する。別の実施形態では、新規ピアは、全応答(肯定応答および否定応答)の応答時間を記憶する。
【0041】
新規ピアは、接続するピアを選択したら、ブロック635において、選択したピアへの接続をオープンする。新規ピアは選択したピアのそれぞれに接続要求を送信して、選択されたピアは要求を確認し、接続をオープンする(選択されたピアで接続が利用不可となった場合を除く)。ピア間の接続は、直接であっても間接的(例えば、インターネット等のネットワークを介するなど)であってもよい。一実施形態では、ピアが接続をオープンすると、各ピアはこの接続をサーバに通知する。
【0042】
別の実施形態では、サーバは、1つ以上の接続を強制的に確立させることによってグリッドに参加し易くする。サーバは、あるピアに接続をクローズさせて、指定した別のピアに接続をオープンさせうる。また、サーバは、ピアにそのピアの接続の1つ以上をクローズさせうる。
【0043】
図7は、図6のブロック630などにおいて、ピアツーピアリレーネットワークに参加するためにピアを選択する一実施形態のフローチャート700を示す。初期状態では、新規ピアがグリッドを選択しており、そのグリッドのメンバピアに参加メッセージを送出している。新規ピアは、メンバピアから返された参加応答を受信している。
【0044】
ブロック705において、新規ピアは、最初に受信した肯定応答に対応するピアを選択する。この肯定応答は、ほかの肯定応答より先に受信され、利用可能な接続のうち最も高速なものを示している。ブロック710において、新規ピアは、最後に受信した肯定応答に対応するピアを選択する。この肯定応答は、ほかの肯定応答より後に受信され、利用可能な接続のうち最も低速なものを示している。最後の応答を決定するために、新規ピアは、全ての応答を受信するまで待機するか、あるいは定義された期間待機し、その期間に最後に受信した応答を最後の応答とする。ブロック715において、新規ピアは、新規ピアが選択した接続の数が接続上限に等しくなるまで、残りの肯定応答からピアを無作為に選択する。このような選択により、グリッドを通る高速な接続と低速な接続が均等に散らばるようになる。
【0045】
前述のように、様々な実装において、異なる接続ルールまたは追加の接続ルールが使用されてもよい。一実施形態では、新規ピアは、最初の肯定応答および最後の肯定応答に対応するピアを選択し、次に、(最初の肯定応答に続いて)応答時間の短い順の肯定応答に対応するピアから順に選択していく。別の実施形態では、新規ピアは、待機してからピアの選択を開始するのではなく、応答が到着し次第ピアを選択する(例えば、最後に受信する肯定応答のために1つの接続を残しておく)。別の実施形態では、新規ピアは、応答時間のしきい値を使用してピアを選択する(例えば、応答時間がある許容値を超えるピアを選択しない)。別の実施形態では、新規ピアは、記憶容量、演算速度、アクセスレベルまたは利用可能な機能などのピアの特性に基づいて(参加応答内に提供された情報を使用して)ピアを選択する。
【0046】
一実施形態では、ピアシステムは、接続の選択に使用する選択処理(selection process)に従って、接続を分類する。例えば、ピアは、オープンしている接続のうち、最短の応答時間で受信した参加応答に対応する接続と、最長の応答時間で受信した参加応答に対応する接続とを示す情報を記憶する。グリッドから切断するピアおよびグリッドに参加する新規ピアのために接続が調整されると、ピアは記憶している接続の分類を調整しうる。
【0047】
別の実施形態では、新規ピアは、接続のオープンを支援するサーバを使用する。一実施形態では、サーバは、利用可能な接続を有するグリッドメンバと、そのメンバピアのアドレスとを記載したリストを提供する。新規ピアは、提示されたグリッドメンバに参加メッセージを直接送信する。
【0048】
肯定応答の数が接続上限よりも少ない場合、新規ピアの利用可能な接続が余っている。一実施形態では、新規ピアは、別のピアに強制的に既に確立されている接続をクローズさせて、新規ピアとの接続をオープンさせることができる。
【0049】
図8は、ピアツーピアリレーネットワークにおいて、ピアに、新しいピアへの接続を強制的に付与させる一実施形態のフローチャート800を示す。初期状態では、新規ピアがグリッドを選択しており、グリッドのメンバピアに参加メッセージを送出している。新規ピアは、メンバピアから返された参加応答を受信している。しかし、新規ピアは、全肯定応答に対応するピアを選択した後も、利用可能な接続をまだ有している。
【0050】
ブロック805において、新規ピアは、否定応答に対応するピアを選択する。新規ピアは、肯定応答と同じ接続ルールを使用して、否定応答を選択する(例えば図7のルールに従って、最初に受信した否定応答を選択する)。別の態様では、新規ピアは、異なる強制接続ルールの組を使用する。新規ピアは、その新規ピアに既に接続されているピアを選択しない。
【0051】
ブロック810において、新規ピアは、選択したピアに強制接続要求を送信する。強制接続要求は、新規ピアが少なくとも1つの利用可能な接続を有すること(またはその具体的な数)と、受信側ピアが新規ピアとの接続をオープンすべきこととを示している。
【0052】
ブロック815において、新規ピアは強制接続要求を受信して、クローズする接続を選択する。受信側ピアは、接続ルールを逆に使用して、クローズする接続を選択する。応答時間に基づいた接続ルールを使用する場合、受信側ピアは、参加応答(および後述するように接続利用可能応答)から取得して記憶した応答時間を使用する。一実施形態では、受信側ピアは、無作為に選択されたピアから選択するために、最後に選択したピアを選択するか、またはピアを再度無作為に選択する。別の実施形態では、受信側ピアは、別の強制切断ルールの組を使用する。
【0053】
ブロック820において、受信側ピアは選択した接続をクローズする。受信側ピアは、選択した接続に接続されているピアにクローズメッセージを送信して、この2つのピアは接続をクローズする。選択した接続に接続されているピアは、この段階で、利用可能な接続を有しており、後述するように、グリッドに接続利用可能メッセージを送出する。
【0054】
ブロック825において、受信側ピアは新規ピアに確認を送信して、この2つのピアは新しい接続をオープンする。この段階で、新規ピアの利用可能な接続が1つ減っている。新規ピアが利用可能な接続をほかに有する場合、新規ピアは、ブロック805に戻って、別の否定応答を選択する処理を繰り返す。
【0055】
別の実施形態では、新規ピアが少なくとも2つの利用可能な接続を有さない限り、新規ピアは別のピアに強制的に接続をオープンさせることはない。別の態様では、別のしきい値(3など)が使用されてもよい。別の実施形態では、新規ピアの接続数が、少なくともある数(接続最低数[connection floor])に達していない場合、新規ピアは強制接続メッセージを送信する。
【0056】
別の実施形態では、強制接続メッセージの受信側ピアは、(例えば、ネットワークの負荷分散の状況によっては)これを拒否することができる。拒否された場合、新規ピアは、新しい強制接続メッセージを送信する別のピアを選択する。
【0057】
別の実施形態では、新規ピアが利用可能な接続を2つ以上有しており、かつ強制接続メッセージを送信する場合、新規ピアは、この新規ピアが利用可能な接続を2つ有することを示す情報をこのメッセージに含める。受信側ピアがクローズする接続を選択すると、受信側ピアは、選択した接続の被接続ピア(リモートピア)に対して、新規ピアが別の利用可能な接続を有することを示す(適宜新規ピアのアドレスを含める)。受信側ピアがリモートピアとの接続をクローズしたら、リモートピアは、(新規ピアがリモートピアに既に接続されている場合を除いて)新規ピアに接続利用可能メッセージを直接送信する。新規ピアは、(新規ピアが選択した)受信側ピアとの新しい接続と、(受信側ピアが選択した)リモートピアとの別の新しい接続とをオープンする。このようにして、新規ピアは、2つの接続を迅速に確立することができる。新規ピアが利用可能な接続をまだ2つ有する場合、新規ピアは、利用可能な接続を2つ有することを示す強制接続メッセージを、選択した別の受信側ピアに再度送信しうる。
【0058】
ピアシステムが別のピアシステムから切断すると、これらのピアはそれぞれ利用可能な接続を有することになる。これらのピアのうちの1つ(または両方)がまだグリッドに留まっている(すなわち、グリッドから切断されていない)場合、ピアは、そのピアの残りの被接続ピアに接続利用可能メッセージを送出して、グリッドを介してグリッド内のほかの全ピアにメッセージをリレーさせる。
【0059】
図9は、ピアツーピアリレーネットワークにおける切断の一実施形態のフローチャート900を示す。初期状態では、ピアシステム(被切断ピア)が、ピアツーピアリレーネットワークにおいて少なくとも2つの他のピアシステムに接続されている。
【0060】
ブロック905において、被切断ピアは、被切断ピアが最初に接続されていたピアの1つから切断される。この切断は、一方の末端での自発的な切断か、あるいは接続自体の障害(例えば、ピア間の経路の一部に障害が発生したなど)が原因で発生する。例えば、自発的な切断は、(後述のように)接続されたピアが応答しない場合、または(前述のように)ピアが新規ピアとの接続のオープンを強制される場合に発生しうる。一実施形態では、サーバが、ピアに1つ以上の接続をクローズさせ、これを受けて切断が発生することがある。
【0061】
ブロック910において、被切断ピアは、この被切断ピアに接続されているピアに接続利用可能メッセージを送信する。接続利用可能メッセージは、被切断ピアが現在、利用可能な接続を有していることを示している。別の実施形態では、接続利用可能メッセージは、ピアが利用できる接続数を示している。
【0062】
ブロック915において、被切断ピアに接続されたピアは、接続利用可能メッセージをリレーする。ブロック920において、グリッド内のピアは、被切断メンバに、接続利用可能応答を返信する。接続利用可能応答は、応答したピアが利用可能な接続を有するかどうかを示している。肯定応答は、応答したピアが利用可能な接続を有することを示している。否定応答は、応答したピアが利用可能な接続を有さないことを示している。応答したピアは、参加メッセージから得た新規ピアノアドレスを記録して、そのアドレスを使用して参加応答を送信する。別の態様では、応答したピアは、グリッドを介して応答を返信し、これが被切断ピアにリレーされる。被切断ピアは、接続利用可能応答を受信する。
【0063】
ブロック925において、被切断ピアは、グリッドメンバの1つから接続するメンバを選択する。被切断ピアは、接続ルールを使用して接続するピアを選択するが、被切断ピアは、その被切断ピアに既に接続されているピアを選択しない。例えば、一実施形態では、被切断ピアは、接続利用可能応答の応答時間と、被切断ピアにまだ接続されているピアの記憶している応答時間を使用して、失った接続を補充するためのピアを選択する。実装によって、異なる接続ルールの組が使用されてもよい。被切断ピアは、選択したピアの応答時間を記憶する。別の実施形態では、被切断ピアは、全応答(肯定応答および否定応答)の応答時間を記憶する。一実施形態では、被切断ピアは、その被切断ピアが一定の期間内に切断されたピアから選択することはない。
【0064】
接続するピアを選択したら、ブロック930において、被切断ピアは、選択したピアへの接続をオープンする。被切断ピアが選択したピアに接続要求を送信して、選択されたピアは要求を確認し、接続をオープンする(選択されたピアで接続が利用不可となった場合を除く)。ピア間の接続は、直接であっても間接的(例えば、インターネット等のネットワークを介するなど)であってもよい。一実施形態では、接続されたピアは、接続を確認する更新をサーバに送信する。
【0065】
図8を参照して前述したグリッドに参加するための実装に同様に、一実施形態では、被切断ピアは、接続利用可能メッセージを使用して接続のオープンを試みた後も、(例えば、全ての接続利用可能応答が否定応答であったため)利用可能な接続をまだ有する場合、被切断ピアは、前述のように強制接続メッセージを送出しうる。
【0066】
別の実施形態では、被切断ピアは、新しい接続のオープンを支援するサーバを使用する。一実施形態では、サーバは、利用可能な接続を有するグリッドメンバと、そのメンバピアのアドレスを記載したリストを提供する。被切断ピアは、提示されたグリッドメンバに接続利用可能メッセージを直接送信する。
【0067】
グリッド内のピアシステムは、定期的にポーリングし合うことによって、グリッドを維持している。一実施形態では、接続されたピアは、接続と、接続されたピアがまだ機能していることとを確認するために定期的にメッセージを送信し合う。
【0068】
図10は、ピアツーピアリレーネットワークを維持する一実施形態のフローチャート1000を示す。初期状態では、グリッド内に複数のピアシステムが接続されている。
【0069】
ブロック1005において、あるピアが、そのピアに接続されている各ピアに、維持メッセージを送信する。維持メッセージは、受信側に対して、維持メッセージを受信したことを示す確認を提供するように求める要求である。一実施形態では、ピアは、接続された各ピアにpingメッセージを送信する(またはpingを行う)。ブロック1010において、ピアは、維持メッセージに対して受信した応答を評価する。ピアは、応答が良好かどうかを決定する。一実施形態では、接続されたピアから応答を受信できない場合、ピアは、ピアの接続に障害が発生している(接続あるいは接続されたピアのいずれかが原因となる)と決定する。制限時間までに応答を受信できない場合、ピアは、ピアの接続に障害が発生していると決定する。ブロック1015において、ピアは、障害が発生しているとピアが決定した接続の接続をクローズする。ピアは、障害のある接続の被接続ピアに接続クローズ要求を送信する。ピアは、確認を受信すると、接続をクローズする。ピアが障害のある接続の被接続ピアと通信できない場合、または制限時間内に確認を受信しなかった場合は、ピアは、確認なしで接続をクローズする。別の実施形態では、接続が、所定時間の間、または所定の障害の回数だけ、障害が発生していると判定されるまで、ピアは接続をクローズするのを待機する。一実施形態では、ピアは、クローズされた接続について確認する更新をサーバに送信する。
【0070】
ピアが接続をクローズしていると、ピアは、(例えば、図9を参照して前述したように)1つ以上のピアから自発的に切断して、適切な接続利用可能メッセージを送出する。
【0071】
別の実施形態では、ピアは、サーバを使用して、障害のある接続を評価する。例えば、ピアが接続に障害が発生していると決定すると、ピアは支援を求めてサーバに要求を送信する。サーバは、障害のある接続のもう一方の末端に存在するピアにメッセージを送信して、ピアに障害が発生しているか、あるいは接続に障害が発生しているかを決定する。次に、サーバは、ピアに通知して、適宜新しい接続のオープンまたはネットワークの調整を容易に行えるようにする。
【0072】
図11〜18は、グリッドを構築、調整および維持する一実施形態の例を示す。
【0073】
図11では、ピアシステム1105A(ピアA)が、サーバ1110を使用して、ピアツーピアリレーネットワーク(グリッド)1100を確立している(ピアAとサーバ1110間の接続は図示されていない)。このグリッドの接続上限は3であるため、ピアAは利用可能な接続を3つ有する。図12では、第2のピアシステム1105B(ピアB)がグリッド1100に参加している。ピアBが参加する際に、ピアBはピアAに参加メッセージを送信し、ピアAは、ピアBに肯定参加応答を送信する。ピアAとピアBは接続をオープンする。
【0074】
図13では、さらに2つのピアシステム1105C,1105D(ピアCおよびピアD)が既にグリッド1100に参加している。4つのグリッドメンバピアA〜Dのそれぞれは、グリッド1100内の他のピアと3つの接続を確立している。新しいピアシステム1105E(ピアE)がグリッドに参加する。しかし、ピアEが他のピアに参加メッセージを送信しても、各ピアA〜Dは、既にグリッド1100の接続上限によって許される最大接続数に達しているため、参加応答は全て否定応答となる。図14で、ピアEは、強制的に接続をオープンさせている。ピアEは、(例えば、ピアEがピアBの応答を最初に受信したなどの理由により)否定応答の中からピアBを選択し、ピアBに強制接続メッセージを送信する。ピアBは、接続をクローズするためにピアDを選択し、ピアDとの接続をクローズする。ピアBは、ピアEとの接続を確認し、ピアBとピアEは新しい接続をオープンする。ピアBがピアDとの接続をクローズすると、ピアDは利用可能な接続を有することになる。ピアDはピアA,Cに接続利用可能メッセージを送信し、ピアがこのメッセージをグリッド1100全体にリレーする。ピアA,B,Cは、利用可能な接続を有しておらず、このため、ピアDに否定応答を送信する。ピアEは、利用可能な接続を2つ有しており、ピアDに肯定応答を送信する。ピアDは、ピアEとの接続をオープンする。ピアEは、利用可能な接続をまだ有しており、接続利用可能メッセージを送出する。しかし、応答は全て否定応答である。ピアEは確立済みの接続を2つ有しており、利用可能な接続を1つしか有さないため、ピアEは強制的に別の接続をオープンさせることはない。
【0075】
図15では、ピアAがグリッド1100から切断する。ピアAは、ピアB,C,Dにそれぞれ接続されていた。ピアAが切断すると、ピアB,C,Dはそれぞれ利用可能な接続を有することになる。ピアB,C,Dは、接続利用可能メッセージを送出し、ピアB,C,D,Eはそれぞれ肯定応答を送信する。ピアB〜Eは、接続利用可能応答に対する応答を評価し、既存の接続のピアを除外してから、図16に示すような接続を確立する。ピアB〜Eの各々は、この段階で接続を3つ有する。
【0076】
図17では、3つの新しいピアシステム1105F,1105G,1105H(ピアF,G,H)がグリッド1100に参加し、接続を確立している。ピアB〜Hは、グリッドを維持する定期的な活動の一環として、それぞれ、自身に接続されているピアにpingメッセージを送信する。例えば、ピアBは、ピアD,E,Gを定期的にpingする。ピアDは、ピアBのpingメッセージに対して、ピアBに良好な応答を返さない(例えば、ピアDからの応答が遅すぎるか、あるいは応答がピアBに届かない)。図18で、ピアBは、ピアDの接続をクローズしている。ピアBが接続をクローズすると、ピアBおよびピアDは利用可能な接続を有することになる。ピアB,Dは、接続利用可能メッセージを送出し、これがグリッド1100を介してリレーされる。ピアBは、ピアG,Dから肯定応答を受信する。ピアBは、ピアGに既に接続されているため、新しい接続にピアGを選択しない。ピアBは、障害のある接続のためピアDから切断したばかりであるため、新しい接続にピアDを選択しない。ピアBは、新しい接続をオープンしない(ピアBはオープンされている接続2つを有しており、利用可能な接続を1つしか有さないため、ピアBは強制的に接続を確立しようとしないが、別の実施形態ではピアBがこれを行ってもよい)。ピアDは、ピアB,Gから肯定応答を受信する。ピアBは、障害のある接続のためピアDから切断したばかりであるため、ピアDは新しい接続にピアBを選択しない(またはピアBが新しい接続要求を拒否する)。ピアDは、ピアGを選択し、ピアGとの接続をオープンする。
【0077】
図11〜18に示した例では、グリッド1100のピアは、接続の管理にサーバ1110に依存することなく、接続をオープンおよびクローズして、グリッドを作成および調整している(しかし、サーバ1110は、グリッドの現在のメンバピアのアドレスを新規ピアに提供する支援を行っている)。
【0078】
冗長リスト
一実施形態では、グリッド内のピアは、グリッド内の現在の経路に基づいて、冗長であると決定されたメッセージの送信を回避することにより、冗長メッセージのトラフィックを削減している。
【0079】
この実装では、ピアツーピアリレーネットワーク内の各ピアは、冗長リストを記憶している。ピアの冗長リストは、このピアが、指定されたピアを発信元するメッセージを送信しない他のピアを指定している。したがって、冗長リストの各エントリは、発信元ピアと、(リレーピアに接続された)宛先ピアとを指定している。ピアが、そのピアの冗長リストに存在する発信ピアを示すメッセージを受信した場合、そのピアは、冗長リストの対応するエントリが示す被接続ピアに、そのメッセージをリレーしない。別の実施形態では、ピアは、(例えば、セキュリティの問題が発生したことが判明した後など、サーバからの要求により)冗長リスト機能のオン/オフを切り替えうる。
【0080】
図19は、ピアツーピアリレーネットワークにおいて冗長リストを作成する一実施形態のフローチャート1900を示す。初期状態では、複数のピアシステムが接続され、ピアツーピアリレーネットワークが形成されている。受信側ピアは、少なくとも2つの他のピアに接続されている。
【0081】
ブロック1905において、受信側ピアが、接続されたピアから冗長メッセージを受信する。受信側ピアが同じメッセージを既に受信しているため、この冗長メッセージは冗長である。受信側ピアは、受信メッセージにある情報を使用して、冗長メッセージが同一であると識別する。前述のように、一部の実装では、各ピアは、同じメッセージを2回リレーしないように、受信したメッセージのリストを維持している。受信側ピアは、冗長メッセージを特定するためにも、このリストを使用することができる。
【0082】
ブロック1910において、受信側ピアは、冗長更新メッセージを作成する。受信側ピアは、冗長更新メッセージに、メッセージの発信元を特定する情報と受信側ピアを特定する情報とを含める。例えば、受信側ピアは、冗長メッセージから発信元識別子を取得して(例えば、図2に示したメッセージを思い出されたい)、この発信元識別子を冗長更新メッセージに記憶させる。
【0083】
ブロック1915において、受信側ピアは、冗長メッセージの送信元に冗長更新メッセージを送信する。冗長メッセージは、そのアドレス情報に、冗長メッセージの送信元のアドレス情報を含んでいる。
【0084】
ブロック1920において、冗長メッセージの送信元は、冗長更新メッセージを受信して、送信元の冗長リストを更新する。送信元は、冗長メッセージの発信元および冗長メッセージの受信側(受信側ピア)を特定する情報を、冗長更新メッセージから取得する。送信元は、送信元の冗長リストに、送信元が、指定されている発信者を発信元とするメッセージを受信側ピアに送信すべきではないと指定するエントリを追加する。
【0085】
例えば、図1に示すグリッド100を参照すると、ピアBは、ピアCを発信元とするメッセージを、ピアA,D,Eのそれぞれから受信する。ピアBがピアCを発信元とするメッセージを、ピアAから最初に受信したと仮定すると、ピアCを発信元とし、ピアD,Eから受信するメッセージは、冗長メッセージである。ピアBは、ピアCを発信元、およびピアBを受信側に指定する、ピアD,Eに送信する冗長更新メッセージを作成する。ピアBは、ピアDに冗長更新メッセージを送信する。ピアDは、ピアDがピアCを発信元とするメッセージをピアBにリレーしないことを示すために、自身の冗長リストを更新する。ピアEは、ピアBから同様の冗長更新メッセージを受信して、同じように自身の冗長リストを更新する。
【0086】
ピアがグリッドに接続したりグリッドから切断すると、クライアント間の経路が変化し、このため冗長リストが不正確となりうる。したがって、ピアがグリッドから切断したときに、残りのピアは冗長リストを更新する。
【0087】
図20は、ピアツーピアリレーネットワークにおいて切断ピアのために冗長リストを更新する一実施形態のフローチャート2000を示す。初期状態では、複数のピアシステムが接続され、ピアツーピアリレーネットワークが形成されている。切断しようとしているピアは、少なくとも2つの他のピアに接続される。
【0088】
ブロック2005において、切断ピアがグリッドから切断する。以前にこの切断ピアに接続されていたピアは、この時点で被切断ピアとなる。被切断ピアのそれぞれは、下記の同じ処理を取る。
【0089】
ブロック2010において、被切断ピアは冗長解除メッセージを作成する。冗長解除メッセージは、被切断ピアを特定する情報を示している。ブロック2015において、被切断ピアは、被切断ピアにまだ接続されているピアに冗長解除メッセージを送信する。ブロック2020において、被切断ピアから冗長解除メッセージを受信したピアは、自身の冗長リストを更新する。冗長解除メッセージを受信したピアは、ピアの冗長リスト内のエントリを削除し、冗長解除メッセージが指定する被切断ピアへのメッセージのリレーを変える。
【0090】
図1,19を参照して上述した例に戻ると、ピアDは、ピアCを発信元とするメッセージを、ピアBにリレーすべきではないと指定するエントリを、自身の冗長リストに持っている。ピアAがグリッドから切断すると、ピアBはピアAの切断を認識し、冗長解除メッセージを作成する。ピアBは、ピアD,Eに冗長解除メッセージを送信する。ピアDは、ピアBから冗長解除メッセージを受信し、ピアDが、ピアCを発信元とするメッセージを、ピアBにリレーすべきではないことを指定している、ピアDの冗長リスト内のエントリを解除する。したがって、次にピアDがピアCを発信元とするメッセージを受信すると、ピアDはピアBにメッセージを再びリレーするようになる。ピアEも、同様に自身の冗長リストを更新する。
【0091】
複数のグリッド
一実施形態では、ピアシステムは、複数のピアツーピアリレーネットワークに属することができる。各グリッドは、関連しているか、あるいは独立しうる。各グリッドに従って確立された接続は、独立でありうる。したがって、ピアはあるグリッド内の1つのピアに接続されるが、別のグリッドにおいて(2つのピアの両方が両方のグリッドに存在する場合であっても)接続されないことがある。一実施形態では、2つのピアが2つのグリッドにおいて接続されている場合、ピアは1つの接続を使用する。メッセージには、そのメッセージが属するグリッドを示す情報が含まれる。ピアは、受信メッセージの指定されたグリッドに対応して確立された接続に従って、そのメッセージをリレーする。
【0092】
一実施形態では、ピアツーピアリレーネットワークのメンバは、ピアツーピアリレーネットワーク内でサブネットワークを作成することができる。この場合、サブネットワーク内の各メンバは、大きなグリッドのメンバでもある。例えば、ピアツーピアリレーネットワークは、ピアシステムとしてゲームの全プレーヤを有しており、(全プレーヤのサブセットを含む)各チームは、(例えば、ゲーム内での専用通信のために)ピアシステムのサブネットワークを有する。このようにして、ピアは、データを好適に配信および受信するためのマルチチャネル環境を確立することができる。
【0093】
別の実施形態では、ピアツーピアリレーネットワークは、独立しているが、1つ以上のメンバピアシステムを共有している。例えば、あるピアのグループが、ロビーまたはチャット環境に対応するためにグリッドを確立し、この第1のグループに属するピアを少なくとも1つ含む別のピアのグループが、特定のゲームに対応するためにグリッドを確立しうる。別の例では、あるピアのグループが、クラン(組織)のためにグリッドを形成し、そのピアの一部が、ゲームをプレイするために別のグリッドに参加するかまたは別のグリッドを作成する。
【0094】
例えば、オンライン環境では、この環境内の全ピアが1つのメイングリッドに接続されている。メイングリッドは、一般的なアナウンスメントおよび一般的なサービスに用いられる。ピアは、チャットルームやゲームなどのオンラインサービスにアクセスするために、追加の小規模なグリッドを作成したり、これに参加したり、これから離脱する。ピアは、新しいピアがグリッドへの参加を希望している場合など、小規模なグリッドを確立する前に、メイングリッドを使用して通信を行いうる(サーバを使用することはない)。全ての制御メッセージがメイングリッドを介してブロードキャスト可能であるため、全てのピアは、利用可能なグリッドのリストと、各グリッドにおいてアクティブなピアのリストを独立して維持することができる。一実施形態では、ピアは中央サーバを使用しない。
【0095】
図21は、複数のグリッドに属しているピアシステムからメッセージをリレーする一実施形態のフローチャート2100を示す。初期状態では、複数のピアシステムが接続され、2つのピアツーピアリレーネットワークが形成されている。リレーピアは、両方のグリッドのメンバであり、各グリッドのそれぞれの接続およびリレールールを有する。
【0096】
ブロック2105において、リレーピアがメッセージを受信する。このメッセージには、そのメッセージが属するグリッドを示すグリッド識別子が含まれる。
【0097】
ブロック2110において、リレーピアは、受信メッセージが指定するグリッドを選択する。各グリッドは、それぞれの接続の組とそれぞれのリレールールの組とを有する。リレーピアは、グリッドを選択することによって、受信メッセージのリレーに使用する接続の組と、使用するリレールールの組とを選択する。
【0098】
ブロック2115において、リレーピアは選択したグリッドとその対応のリレールールに従って接続を選択する。リレーピアは、選択したグリッドのリレールールを使用して、受信メッセージをリレーするための任意の適切な接続を選択する。
【0099】
ブロック2120において、リレーピアは、選択したピアに受信メッセージを送信する。リレーピアは、メッセージをリレーする前に、選択した各ピアのために受信メッセージを調整する。この際、例えば、受信メッセージのアドレス情報を更新して、受信メッセージがリレーピアから選択したピアにリレーされようとしていることを示す。
【0100】
観客
一実施形態では、グリッド内のピアは、参加者または観客に分けられる。参加者ピアは、グリッド全体にリレーさせるための新しいメッセージを生成する。観客ピアは、新しいメッセージを生成せず、グリッド内で通過ノードとして機能する。参加者および観客の両方は、グリッドのリレールールに従って、自身の被接続ピアにメッセージをリレーする。一部のアプリケーションでは、各参加者に対して観客が多数存在しうる。複数の参加者を有する一実施形態では、各参加者は、他の参加者への接続を少なくとも1つ有する。
【0101】
一例においては、参加者のグループがオンラインゲームをプレイしている間に、観客がこれを観戦する(ゲームのデータを変化させずにデータを観察する)。観客の数は、(数千など)非常に多いことがある。別の例には、パフォーマンス(音楽など)、スピーチおよび教育などがある。一部のアプリケーションでは、ピアがデータをリレーすることによって分散を処理しているため、観客の数が増加しても、分散に要するサーバの負荷が必ずしも増加するわけではない。
【0102】
一実施形態では、ピアがグリッドに参加すると、そのピアは参加者または観客としてグリッドに参加する。ピアが観客としてグリッドに参加した場合、そのピアは、新しいメッセージを作成したり、新しいメッセージをグリッドに送信してグリッド全体にリレーさせる許可を与えられない。観客が新しいメッセージを生成して、観客に接続されたピアに新しいメッセージを送信した場合、観客から新しいメッセージを受信したピアは、受信メッセージを転送またはリレーしない。一実施形態では、観客の一部または全てが、(例えば、第1のグリッドで観察しているゲームについて話し合うなどのために)参加者として別の関連グリッドを形成してもよい。
【0103】
図22は、観客および参加者に対応しているグリッドにおいてメッセージをリレーする一実施形態のフローチャート2200を示す。初期状態では、複数のピアシステムが接続され、参加者および観客に対応しているピアツーピアリレーネットワークが形成されている。
【0104】
各ピアシステムは、参加者であるピアのリストを記憶している。一実施形態では、参加者ピアは、どのピアが参加者であるかを示すメッセージを定期的にブロードキャストする。別の実施形態では、サーバが、参加者の識別を支援している。
【0105】
ブロック2205において、リレーピアがメッセージを受信する。このメッセージには、このメッセージを作成したピアを示す発信元識別子が含まれる。
【0106】
ブロック2210において、リレーピアは、受信メッセージの発信元が参加者ピアであることを確認する。リレーピアは、参加者ピアのリストを記憶している。リレーピアは、受信メッセージの発信元として識別されたピアを、参加者ピアのリストと比較する。受信メッセージの発信元ピアが参加者でない(すなわち観客である)場合、リレーピアは受信メッセージをリレーしない。
【0107】
受信メッセージの発信元ピアが参加者である場合、ブロック2215において、リレーピアはグリッドのリレールールに従って接続を選択する。リレーピアは、リレールールを使用して、受信メッセージをリレーするための任意の適切な接続を選択する。
【0108】
ブロック2220において、リレーピアは、選択したピアに受信メッセージを送信する。リレーピアは、メッセージをリレーする前に、選択した各ピアのために受信メッセージを調整する。この際、例えば、受信メッセージのアドレス情報を更新して、受信メッセージがリレーピアから選択したピアにリレーされようとしていることを示す。
【0109】
別の実施形態では、観客は、参加者と同じグリッドに存在しない。観客は、参加者グリッドにリンクされ、並行して存在する観客グリッドを形成している。観客は、参加者からデータを受信し、観客グリッドにおいてデータをリレーする。グリッド間のリンクは、サーバまたはゲートウェイによって、または各グリッドから選択したピア同士の接続によって提供されうる。
【0110】
別の実施形態では、観客は条件付き観客になることができる。条件付き観客は、グリッド全体にリレーされるデータを生成するための権限を要求することができる。観客が権限を受けている場合、観客は、グリッド内でピアがリレーするメッセージを送信することができる(例えば、メッセージに許可フラグが含まれる)。この権限は、サーバによって、調停者としての選択されたピアによって、または(1つ以上の)参加者によって付与されうる。例えば、教育の環境では、参加者が講師であり、観客は、全ピアにリレーされる質問を尋ねるための権限を要求しうる。
【0111】
アイランドの復旧
一実施形態では、ピアツーピアリレーネットワーク内のサーバおよびピアは、アイランドの形成を回避するかまたはこれから復旧するために、グリッド内の接続の調整に対応している。グリッド内で隔離されたピアのグループは、アイランドと呼ばれる。複数のピアがほぼ同時に切断すると、アイランドがグリッド内で形成されることがある。前述の切断処理においては、残ったピアが、利用可能な接続を示すメッセージを送信するが、複数の切断が同時発生した場合、残ったピアが、グリッド内で隔離されたグループを形成することがある。アイランド同士の間にピアツーピア接続がないため、あるアイランド内のピアは別のアイランド内のピアにメッセージを送信することができない。サーバはアイランドの形成を検出し、ピアと対話してアイランドを除去させる。
【0112】
図23は、グリッド内でアイランドを検出する一実施形態のフローチャート2300を示す。初期状態では、複数のピアシステムが接続され、ピアツーピアリレーネットワークまたはグリッドが形成されている。ピアが接続をオープンおよびクローズするか、または切断されると、ピアは、グリッドのサーバに、この接続の変更を通知する。このようにして、サーバは、グリッド内の全接続をトラッキングしている。サーバは、グリッド内のピアの順序付きリストも維持している。
【0113】
ブロック2305において、サーバはアイランドカウンタをセットする。アイランドカウンタは、アイランドの数を表している。一実施形態では、サーバはカウンタiを1にセットする。
【0114】
ブロック2310において、サーバは開始ピアを選択する。アイランドカウンタが1の場合、サーバは、ピアの順序付きリスト内で先頭のピアを開始ピアとして選択する。アイランドカウンタが1を超える場合、サーバは、最も最近発見された未マークのピア(これについては後述する)を開始ピアとして選択する。
【0115】
ブロック2315において、サーバは、開始ピアに接続されているピアのそれぞれを、開始ピアと同じアイランドに属するものとしてマークする。サーバは、開始ピアに直接接続されているピアと、他のピアを介して開始ピアに間接的に接続されているピアとをマークする(例えば開始ピアから被接続ピアへ、この被接続ピアに接続されたピアへ、…と処理を進めていく)。サーバは、ピアが属しているアイランドを示すために、アイランドカウンタの現在の値によってピアをマークする。
【0116】
開始ピアに接続されたピアの全てをマークしたら、ブロック2320において、サーバは、グリッドに未マークのピアが残っているかどうかを決定する。一実施形態では、サーバは、ピアの順序付きリストを順に処理して、未マークのピアを検索する。
【0117】
サーバが未マークのピアを発見した場合、ブロック2325において、サーバはアイランドカウンタをインクリメントする。サーバは、アイランドカウンタをインクリメントして、追加のアイランドが検出されたことを示す。アイランドカウンタをインクリメントしたら、サーバはブロック2310に戻り、発見された未マークのピアを開始ピアとして使用する。
【0118】
サーバが未マークのピアを発見できない場合、ブロック233において、サーバは検出されたアイランドの数を求める。サーバは、アイランドが検出されたたびにアイランドカウンタをインクリメントしたため、アイランドカウンタは、検出されたアイランドの数を表している。アイランドカウンタが1の場合、発見されたアイランドは1つであり、このためグリッドが複数のアイランドに分割されていない。アイランドカウンタが1より大きい場合、複数のアイランドが発見されており、グリッドはアイランドに分割されている。
【0119】
図24は、ピアツーピアリレーネットワークにおいてアイランドを除去する一実施形態のフローチャート2400を示す。初期状態では、複数のピアシステムが、ピアツーピアリレーネットワークまたはグリッドにおいて接続されている。グリッドが、2つのピアのアイランドに分割されており、一方のアイランド内のピアは、もう一方のアイランド内のピアへの接続経路を有していない。サーバは、図23に示した処理を使用するなどによって、この2つのアイランドを検出している。
【0120】
ブロック2405において、サーバは、各アイランドからピアを選択する。サーバは、様々な方法によって、第1アイランドのピアと第2のアイランドのピアを選択することができる。一実施形態では、サーバは、利用可能な接続を有するピアを選択する。別の実施形態では、サーバは、アイランドから無作為にピアを選択する。
【0121】
第1アイランドのピアが利用可能な接続を有さない場合、ブロック2410において、サーバは、第1アイランドのピアに接続クローズメッセージを送信して、接続をクローズする。第1アイランドのピアは、サーバからメッセージを受信し、前述のように、強制接続メッセージを受信したときにピアがクローズする接続を選択する場合と同様に、クローズする接続を選択する。第1アイランドのピアは、接続をクローズし、利用可能な接続を有するようになる。
【0122】
ブロック2415において、サーバは、第1アイランドのピアに強制接続開始メッセージを送信する。強制接続開始メッセージには、第2のアイランドのピアのアドレスが含まれる。第1アイランドのピアは、サーバからこのメッセージを受信し、第2のアイランドのピアに強制接続メッセージを送信する。
【0123】
ブロック2420において、第2のアイランドのピアは、第1アイランドのピアから強制接続メッセージを受信し、クローズする接続を選択して、選択した接続をクローズする。第2のアイランドのピアは、強制接続メッセージの受信側に関して前述したのと同様の方法で、クローズする接続を選択する。接続のクローズ前に、第2のアイランドのピアが利用可能な接続を有する場合、第2のアイランドのピアは自身の接続をクローズしない。
【0124】
ブロック2425において、第1アイランドのピアは第2のアイランドのピアに接続オープン要求を送信し、この2つのピアが接続をオープンする。ひとたび接続がオープンされると、アイランドが結合され、1つのアイランドが形成される。ピアは、この接続を確認する更新をサーバに送信する。前述のように検出したように、さらにアイランドが残っている場合、サーバはブロック2405に戻り、残りのアイランドの2つ以上を接続する。
【0125】
図25,26は、アイランドの検出および結合の例を示す。図25では、図11のグリッド1100と同様のグリッド2500は、ピアC,G,Fが同時に切断したために、2つのアイランドに分割されている。第1アイランドにはピアA,B,D,Eが含まれる。第1アイランドにはピアH,I,Jが含まれる。図26で、サーバは、ピアDにピアIとの接続をオープンさせ、2つのアイランドを結合させている。
【0126】
セキュリティ
一実施形態では、ピアツーピアリレーネットワークは、不正行為違反またはセキュリティ違反、またはこの両方の検出、およびこれらからの復旧に対応している。不正行為違反では、例えばゲームの進行を変えるため、データの操作が行われて、オンライン活動の処理の結果が変更される。セキュリティ違反では、グリッドに損害を与えるか、グリッドに障害を発生させるために、不正なデータが使用されたり、データが不適切に使用される。
【0127】
図27は、ピアツーピアリレーネットワークにおいて不正行為違反を検出する一実施形態のフローチャート2700を示す。初期状態では、複数のピアシステムが接続され、ピアツーピアリレーネットワークまたはグリッドが形成されている。
【0128】
ブロック2705において、ピアは、その被接続ピアの各々からメッセージを受信する。前述のように、グリッド内のピアは、グリッド全体にメッセージをリレーする。ピアは、他のピアとの各接続を介して、同じメッセージ(内容データは同じであるが、アドレス情報が異なることがある)を受信する。例えば、ピアがオープンされている接続を3つ有する場合、このピアは3つのピアから、同じメッセージを3回受信する。ピアは、メッセージ内の、発信元およびシーケンス値を示す情報(図2のメッセージ205に示した発信元識別子215およびシーケンス値220など)を使用して、メッセージが同じであると特定する。異なるピアから受信した同じメッセージは、同じ発信元とシーケンス情報を有する。
【0129】
ブロック2710において、ピアは、被接続ピアの各々から受信したメッセージを比較する。ピアは、図2のメッセージ205に示すデータ230などの、メッセージのデータ部分を比較する。ピアは、受信メッセージのいずれかについて、メッセージのデータ部分が異なっているかどうかを決定する。一実施形態では、ある被接ピアから受信したメッセージのデータ部分が、別の被接続ピアから受信した同じメッセージのデータ部分と異なる場合、ピアは、不正行為違反が発生したと決定する。ピアは、データが異なっているメッセージを送信したピアが不正行為違反の原因であると決定する。別の態様では、ピアは、異なる技術を使用して、不正行為違反を検出するか、または不正行為違反の原因ピアを特定する。適宜、ピアは、データ部分が異なるメッセージをリレーしない。
【0130】
不正行為違反が発生している場合、ブロック2715において、ピアは不正行為警告を送信する。不正行為警告は不正行為違反が発生していることと、不正行為違反の原因であるピアを示している。ピアは、接続されたピアに不正行為警告を送信し、グリッド全体に警告をリレーさせる。別の実施形態では、ピアは、サーバに不正行為警告を送信して、適切な処置を求める。
【0131】
ブロック2720において、ピアが不正行為警告を受信すると、ピアは侵害に対する復旧措置をとる。ピアは、不正行為を行っているピアがグリッドの活動に影響し続けるのを阻止するための処置をとる。一実施形態では、ピアは、不正行為を行っているピアからのメッセージを無視する。別の実施形態では、ピアは、不正行為を行っているピアをグリッドから強制的に切断させる。ピアは、異なるデータが含まれるメッセージの影響を是正するための処置もとり、これには、例えば、不正行為メッセージの特定に用いた他のメッセージのデータが示す正しいデータを有する代替メッセージを送出することなどがある。別の態様では、ピアのうちの1つが正しいデータを推定して、この正しいデータをグリッド全体にリレーする。別の実施形態では、ピアは、サーバに通知することによって、不正行為警告に対応する。この場合、サーバは、例えば不正行為違反の原因となっているピアを切断することによって、不正行為違反に対処する。
【0132】
別の実施形態では、ピアがメッセージを送信する際に、その受信者は送信ピアにメッセージを返す。送信ピアは、送信メッセージのコピーを保持している。送信ピアは、受信側から返信されたメッセージを受信すると、送信ピアは、送信メッセージのデータを受信メッセージのデータと比較する。ピアは、違いを発見して不正行為違反を検出する。ピアは、受信側がメッセージを変更したと決定し、不正行為警告を送出する。一実施形態では、複数の侵害が報告される(これは、例えば、サーバによってトラッキングされている)まで、不正行為を行っているピアに対する復旧または是正措置がとられることはない。別の実施形態では、不正行為を検出するこの返信検査(send-back check)は、不正行為の検出の最初のレイヤであり、ひとたび問題の可能性が特定されると、より複雑な手順がとられる。
【0133】
別の実施形態では、ピアは、受信メッセージ内のデータを、そのピアが生成した予測のデータの組と比較することによって、不正行為違反を検出する。ピアが、受信メッセージ内のデータが、ピアが生成したものとは異なると決定すると、ピアは、受信メッセージの送信元が不正行為違反の原因であると決定し、警告を発する。
【0134】
図1に示すグリッド100において不正行為違反を検出する例では、ピアBが、ピアA,D,Eの各々から同じメッセージを受信する。ピアBは、発信元識別子およびシーケンス値を比較することによって、メッセージが同じであると特定する。ピアBが、ピアAからのメッセージに異なるデータ部分があると検出した場合、ピアBは、ピアAが不正行為ピアであることを示す不正行為警告を送る。ピアBは、不正行為警告をピアD,Eに(および任意選択でピアAにも)送信する。ピアは、全ピアが警告を受信するまで、不正行為警告をリレーする。ピアは、この警告に対応して、ピアAからそれ以降送られてくる全メッセージを無視する。この結果、ピアB,C,Dは、ピアAからのメッセージをリレーしなくなる。
【0135】
図28は、ピアツーピアリレーネットワークにおいてセキュリティ違反を検出する一実施形態のフローチャート2800を示す。初期状態では、複数のピアシステムが接続され、ピアツーピアリレーネットワークまたはグリッドが形成されている。
【0136】
ブロック2805において、ピアは、その被接続ピアの1つからメッセージを受信する。ブロック2810において、ピアはこのメッセージを解析して、セキュリティ違反を検出する。ピアは、メッセージが無効であるかまたは無効なデータを含むことを認識して、このメッセージがセキュリティ違反であると決定する。別の実施形態では、ピアは、メッセージがそのピアにどのように送信されたかを解析することによって、メッセージがセキュリティ違反であると決定する。例えば、メッセージが、何回も繰り返し送信される同じメッセージの1つとして送信された(例えば、サービス不能攻撃にみられるように)場合、ピアは、メッセージがセキュリティ違反であると認識する。一実施形態では、メッセージが一連のパケットとして送信され、ピアは、メッセージ全体よりも下位のレベル(パケットレベルなど)でセキュリティ違反を検出する。ピアは、セキュリティ違反のメッセージの送信元がセキュリティ違反の原因であることも決定する。別の態様では、ピアは、異なる技術を使用して、セキュリティ違反を検出するか、または不正行為違反の原因ピアを特定する。ピアは、セキュリティ違反のメッセージまたはデータをリレーしない。
【0137】
セキュリティ違反が発生している場合、ブロック2815において、ピアはセキュリティ警告を送信する。セキュリティ警告はセキュリティ違反が発生していることと、セキュリティ違反の原因であるピアを示している。ピアは、接続されたピアにセキュリティ警告を送信し、グリッド全体に警告をリレーさせる。別の実施形態では、ピアは、サーバにセキュリティ警告を送信して、適切な処置を求める。
【0138】
ブロック2820において、ピアがセキュリティ警告を受信すると、ピアは侵害に対し復旧するための措置をとる。ピアは、セキュリティに違反しているピアが、グリッドに影響または損害を与え続けるのを阻止するための処置をとる。一実施形態では、ピアは、セキュリティ違反の原因であるピアからのメッセージを無視する。別の実施形態では、ピアは、セキュリティ違反の原因であるピアをグリッドから強制的に切断させる。ピアは、セキュリティ違反により発生した損害を復旧するための適切な措置もとる。別の実施形態では、ピアは、サーバに通知することによって、セキュリティ警告に対応する。この場合、サーバは、例えば違反の原因となっているピアを切断すると共に、グリッドに生じた損害を是正するための措置をとることによって、セキュリティ違反に対処する。
【0139】
図29,30は、サーバ2905およびピアシステム3005の一実施形態のブロック図をそれぞれ示す。別の実施形態では、サーバまたはピアは、図29,30に示すよりも構成要素が少なくても、異なる構成要素または追加の構成要素を含んでいてもよい。
【0140】
サーバ2905は、前述のように動作し、上記した機能を提供するための構成要素を有する。この構成要素には、グリッドの確立2910、ピアの追加2915、ピアの接続2920、ピアの切断2925、グリッドの維持2930、グリッドのデータ(接続、メンバ、接続上限など)およびルール(リレールール、接続ルールなど)の記憶および生成2935、複数のワールドの管理2940、冗長リストの管理およびその支援2940、複数のグリッドの管理2950、グリッドにおける参加者および観客の管理2955、アイランドの検出および復旧の処理2960、不正行為違反およびセキュリティ違反の管理およびそれらへの対処2965、ならびにサーバの中央サービス2970(例えば、ネットワーク通信、およびアドレッシング、プレーヤのマッチング、チャット機構、データバックのアップ等)などを行う構成要素がある。
【0141】
ピアシステム3005は前述のように動作し、上記した機能を提供するための構成要素を有する。この構成要素には、グリッドの確立3010、グリッドの参加3015、ピアの接続3020、ピアの切断3025、グリッドの維持3030、グリッドのデータ(接続、メンバ、接続上限など)およびルール(リレールール、接続ルールなど)の記憶および生成3035、冗長リストの作成、更新および使用3040、複数のグリッドにおける動作3045、グリッドにおける参加者および観客との動作およびこれらとしての動作3050、アイランドの検出および復旧の処理3055、不正行為違反およびセキュリティ違反の管理、検出およびそれらへの対処3060、ピアシステムのサービス3065(例えば、ネットワーク通信、およびアドレッシング、プレーヤのマッチング、チャット機構、データバックのアップ等)などを行う構成要素がある。
【0142】
ピアツーピアリレーネットワークの様々な実装が望ましい利点を提供する。グリッドは、オンラインの巨大なマルチプレイヤコンピュータゲームなど、多くのネットワークアプリケーションにおいて非常に有用でありえる。オンラインゲームアプリケーションは、1つの共通のデータセットを共有および維持しているという1つの点を共通に持つネットワークアプリケーションの大きなグループの一例に過ぎない。1つのピアでデータセットが更新されると、この情報が他のピアのグループに送信されて、グリッド全体にリレーされ、このため、各ピアが更新されたデータセットを有するようになる。リレーグリッドによって、接続されたピアが、(データ分散のために)中央サーバを介することなく、限られたネットワーク帯域幅でデータを相互に交換できるようになる。このネットワークは、ゲームデータ、ゲームに関連するほかの情報、メディアファイル、ストリーミングオーディオまたはストリーミングビデオの交換に使用することができる。
【0143】
例えば、一実施形態では、ピアがファイル発行(file publishing)のためにグリッドを使用する。グリッド内のピアは、この発行元に接続されたピアにファイルを送信することによってファイル(1つのメッセージかまたは複数のメッセージに分割されている)を発行し、グリッドのメンバピアは、グリッド全体にファイルを全メンバにリレーする。このようにして、グリッドの全メンバは、サーバを使用せず、かつ発行元から全てのピアへの直接接続を使用せずに、発行されたファイルを受信することができる。様々な実装において、どのような種類のファイルでも発行することができる。ファイルは、データ、メディアまたは実行可能なソフトウェアアプリケーションであってよい。グリッドを介して発行されるファイルの例には、ストリーミングメディア(オーディオおよび/またはビデオ等)、メディアファイル、ゲームまたは他のアプリケーションの再生データ、地図、アナウンスメント、メッセージ、アプリケーションのデータおよびモジュール(地図、テンプレート、テクスチャ、音声等)などがあるが、これらに限定されない。
【0144】
本発明の各種実装は、電子ハードウェア、コンピュータソフトウェアまたはこれらの技術の組合せとして実現される。大部分の実装は、プログラム可能なコンピュータによって実行される1つ以上のコンピュータプログラムを含む。例えば、一実施形態では、各ピアシステムおよびサーバは、ピアツーピアリレーネットワークの機能を実装するソフトウェアを実行している1台以上のコンピュータを有する。一般に、各コンピュータは、1つ以上のプロセッサと、1つ以上のデータ記憶要素(例えば、揮発性または不揮発性のメモリモジュール、およびハードディスクドライブ、フロッピーディスクドライブ、CD−ROMドライブ、磁気テープドライブなどの永続的な光学記憶装置および磁気記憶装置)と、1つ以上の入力装置(例えばマウス、キーボード)と、1つ以上の出力装置(例えばディスプレイコンソール、プリンタ)を有する。
【0145】
コンピュータプログラムは、通常は永続的な記憶媒体に記憶されており、その後実行時にメモリにコピーされる実行可能コードを含む。プロセッサは、メモリから実行可能命令を所定の順序で取得することによって、このコードを実行する。プログラムコードの実行時には、コンピュータは入力装置および/または記憶装置からデータを受け取って、データに対して処理を実行し、得られたデータを出力装置および/または記憶装置に送る。
【0146】
本発明の説明のための各種実装を記載した。しかし、当業者は、ほかの実装も可能であり、本発明の範囲に含まれるということを理解するであろう。例えば、上記の説明では、ゲームアプリケーションに対応する例を説明してピアツーピアリレーネットワークのいくつかの実装について記載したが、ファイル共有やどの他のデータ配布アプリケーションなど、他のアプリケーションも可能である。
【0147】
したがって、本発明は、前述したこれらの実施形態のみに限定されるものではない。
【図面の簡単な説明】
【0148】
【図1】ピアツーピアリレーネットワークの一実施形態の説明図。
【図2】メッセージの一実施形態のブロック図。
【図3】ピアツーピアリレーネットワークにおいて、ピアがメッセージをリレーする一実施形態のフローチャート。
【図4】ピアツーピアリレーネットワークにおいて、ピアがリレールールの組に従ってメッセージをリレーする一実施形態のフローチャート。
【図5】ピアツーピアリレーネットワークを確立する一実施形態のフローチャート。
【図6】ピアツーピアリレーネットワークにピアを接続する一実施形態のフローチャート。
【図7】ピアツーピアリレーネットワークに参加するためにピアを選択する一実施形態のフローチャート。
【図8】ピアツーピアリレーネットワークにおいて、ピアに、新しいピアへの接続を強制的に付与させる一実施形態のフローチャート。
【図9】ピアツーピアリレーネットワークにおける切断の一実施形態のフローチャート。
【図10】ピアツーピアリレーネットワークを維持する一実施形態のフローチャート。
【図11】グリッドを構築、調整および維持する一実施形態の説明図。
【図12】グリッドを構築、調整および維持する一実施形態の説明図。
【図13】グリッドを構築、調整および維持する一実施形態の説明図。
【図14】グリッドを構築、調整および維持する一実施形態の説明図。
【図15】グリッドを構築、調整および維持する一実施形態の説明図。
【図16】グリッドを構築、調整および維持する一実施形態の説明図。
【図17】グリッドを構築、調整および維持する一実施形態の説明図。
【図18】グリッドを構築、調整および維持する一実施形態の説明図。
【図19】ピアツーピアリレーネットワークにおいて冗長リストを作成する一実施形態のフローチャート。
【図20】ピアツーピアリレーネットワークにおいて切断ピアのために冗長リストを更新する一実施形態のフローチャート。
【図21】複数のグリッドに属しているピアシステムからメッセージをリレーする一実施形態のフローチャート。
【図22】観客および参加者に対応しているグリッドにおいてメッセージをリレーする一実施形態のフローチャート。
【図23】グリッド内でアイランドを検出する一実施形態のフローチャート。
【図24】ピアツーピアリレーネットワークにおいてアイランドを除去する一実施形態のフローチャート。
【図25】アイランドの検出および結合の説明図。
【図26】アイランドの検出および結合の説明図。
【図27】ピアツーピアリレーネットワークにおいて不正行為違反を検出する一実施形態のフローチャート。
【図28】ピアツーピアリレーネットワークにおいてセキュリティ違反を検出する一実施形態のフローチャート。
【図29】サーバ一実施形態のブロック図。
【図30】ピアシステムの一実施形態のブロック図。
【図31A】代表的なクライアント−サーバおよびピアツーピアのアーキテクチャの説明図。
【図31B】代表的なクライアント−サーバおよびピアツーピアのアーキテクチャの説明図。
【技術分野】
【0001】
本願は、2003年10月20日に出願された米国仮特許出願第60/513,098号(「ピアツーピアリレーネットワーク(PEER-TO-PEER RELAY NETWORK)」の利益を主張し、本開示の内容を参照によりここに援用する。
【背景技術】
【0002】
代表的なクライアント−サーバネットワークにおいては、ネットワーク内の各クライアントが中央サーバとの接続を確立している。クライアントは、サーバからサービスおよびデータを要求する。クライアントは、別のクライアントと通信するために、サーバに要求を送信する。一般に、クライアントは、直接接続を相互に確立することはない。N台のクライアントを有するクライアント−サーバネットワークでは、各クライアントはサーバへの接続を1つ有し、サーバは各クライアントそれぞれへの接続をNつ有する。例えば、図31Aに示すように、6台のクライアントを有するクライアント−サーバネットワークでは、各クライアントはサーバへの接続を1つ有し、サーバは各クライアントそれぞれへの接続を6つ有する。
【発明の開示】
【発明が解決しようとする課題】
【0003】
代表的なピアツーピアネットワーク(または「P2Pネットワーク」)においては、ピアツーピアネットワークの各メンバ(またはピア)は、ほかのメンバそれぞれと接続を確立する。メンバは、中央サーバを用いる代わりに、(例えば、メンバがサーバを介して対話する代表的なクライアント−サーバネットワークと対比すると)この直接のピアツーピア接続を用いて、直接他のメンバにデータを送信したり、他のメンバからデータを要求する。通常、ネットワーク内の各メンバはネットワークにおいて同じ役目を担っており、メンバは(ネットワークメンバとして)一般に同等であるとみなされる。Nのピアを有するピアツーピアネットワークでは、各ピアは、他のピアへの接続をN−1個有する。例えば、図31Bに示すように、6つのピアを有するピアツーピアネットワークでは、各ピアは、他のピアへの接続を5つ有する。
【0004】
一部のピアツーピアネットワークでは、サーバも、アドレス発見などの一部の集中サービスのために(例えば、ピアツーピアネットワークを構築するために接続を確立するために)メンバによって使用される)。
【課題を解決するための手段】
【0005】
本発明は、ピアツーピアリレーを実装するための方法ならびに装置を提供する。一実施形態では、ピアツーピアリレーネットワーク内のピアシステムにおけるアイランドの復旧方法は、ピアツーピアリレーネットワークにおいて、少なくとも1つのピアシステムを有するアイランドの存在を2つ以上検出するステップと、第1のアイランド内のピアシステムを第2のアイランド内のピアシステムに接続することによって、検出された2つのアイランドを結合するステップと、を有し、異なるアイランド内のピアシステム同士は接続されていない。
【0006】
一実施形態では、ピアツーピアリレーネットワーク内のサーバは、ピアツーピアリレーネットワークにおいて、少なくとも1つのピアシステムを有するアイランドの存在を2つ以上検出する手段と、第1のアイランド内のピアシステムを第2のアイランド内のピアシステムに接続することによって、検出された2つのアイランドを結合する手段と、を有し、異なるアイランド内のピアシステム同士は接続されていない。
【発明を実施するための最良の形態】
【0007】
本発明は、ピアツーピアリレーを実装するための方法ならびに装置を提供する。一実施形態では、ピアツーピアネットワークを形成するために複数のコンピュータシステムが接続される。各コンピュータシステムは、所定の台数まで他のコンピュータシステムに接続される。コンピュータシステムは、通信を行うために、接続されたシステムの各々にメッセージを送信する。
【0008】
あるコンピュータシステムが別のコンピュータシステムからメッセージを受信すると、受信したコンピュータシステムは、そのピアツーピアリレーネットワークのリレー手順またはルールに従って、他のコンピュータシステムにメッセージを送信またはリレーする。メッセージは、リレールールに従って、ネットワーク全体にわたり、全メンバコンピュータシステムに伝達される。
【0009】
図1は、ピアツーピアリレーネットワーク100の一実施形態の表現を示す。ピアツーピアリレーネットワークは、グリッドとも呼ばれることがある。図1では、ピアツーピアリレーネットワークを形成するために、10つのピアシステム105A…J(「ピア」とも呼ばれる)のグループが接続されている。各ピアシステム105は、ソニー・コンピュータエンタテインメント株式会社が販売しているプレイステーション2(登録商標)ゲームコンソールなどのネットワーク対応ゲームコンソールであり、ネットワークアダプタを備えている。ピアシステム105は、直接接続されている(有線接続または無線接続など)か、あるいは(例えば、イントラネットまたはインターネット等の公共IPネットワークを介して)間接的に接続されている。一実施形態では、ピアシステム105は、UDP接続またはTCP接続を使用して接続されている。ピアシステム105は、チャット環境またはオンラインゲームなどのネットワークの環境または活動を支援するためにデータを交換する。
【0010】
各ピア105は、インターネットを介したUDP接続またはTCP接続などの中央サーバ110への接続も有する(サーバ110への接続は図1に図示されていない)。サーバ110は、接続されているピアシステム105に集中サービスを提供しているサーバコンピュータシステムである。一実施形態では、サーバは、ピアシステムのアドレスディレクトリを提供しており、どのピアシステム同士が接続されているかをトラッキングしている。ほかのサーバサービスの例には、認証、プレーヤのマッチング、およびピアシステムのアドレスのトラッキングなどがあるが、これらに限定されない。後述するように、一部の実装では、サーバは、複数の独立したピアツーピアリレーネットワークまたは関連するピアツーピアリレーネットワークに対応している。一実施形態では、サーバは、クライアントを環境に分割または分類して、データを適切にフィルタリングする複数の環境またはワールドに対応している。一実施形態では、サーバは、同時係属中かつ譲受人が共通する、 に出願された米国特許出願番号第10/ 号「構成スイッチング:ネットワーク通信アーキテクチャ間の動的変更(Configuration Switching:Dynamically Changing Between Network Communication Architectures)」、ならびに に出願された米国特許出願番号第10/ 号「マルチユーザアプリケーションプログラミングインタフェース(Multi-User Application Programming Interface)」に記載されているサーバの1つ以上の態様を含む。これらの開示を参照によりここに援用する。別の実施形態では、ピアは、中央サーバを使用しない(例えば、直接通信によってグリッドを構築し、データをリレーする)。
【0011】
ネットワーク100の接続上限は3である。接続上限は、サーバによって設定され、各ピア105がグリッド内で持つことができる接続の最大数を定義している。別の実施形態では、1つのピア(例えばグリッドを確立するピア)が接続上限を設定するか、または複数のピアが接続上限を協議して決定する。図1では、接続上限は3であり、各ピア105は接続を3つ有している。ピアシステムA〜Jは、それぞれ他のピアへの接続を3つ有する(ピアシステム105Aは、ピアシステムAまたはピアAとも呼ばれる)。ネットワーク100は3接続ピアツーピアリレーネットワークであり、このため各ピア105は他のピアへの接続を3つ有する。
【0012】
ピア105は、メッセージをネットワーク100全体にブロードキャストすることによって通信を行う。ピア105は、ネットワーク100のリレールールに従って、接続されたピア105に受信メッセージをリレーすることによってメッセージを伝達する。この実装では、リレールールにより、ピア105はピア105に接続されているピア105のそれぞれにメッセージをリレーすることが規定されている。この例外に、(i)ピア105は、ピア105が既にリレーしているメッセージをリレーしない、(ii)ピア105は、そのリレーピア105がそこからメッセージを受信したピア105にメッセージを返さない、の2つがある。また、一実施形態では、ピア105は、そのリレーピア105がそこから既にメッセージを受信しているピア105にそのメッセージをリレーしない(リレーピア105がメッセージをリレーする前に、そのリレーピア105が複数のピア105からメッセージを受信する場合など)。別の実施形態では、別のルールまたは追加のルールが使用されてもよい。リレールール(およびその他のルール)は、サーバによって規定されるか、あるいはピアシステム(またはそのシステムソフトウェア)によって予め設定されている。別の実施形態では、例えばルールの更新情報が含まれるメッセージをグリッド全体に伝達することによって、ルールが動的に変更されうる。
【0013】
ネットワーク100の一アプリケーションでは、ピア105はネットワークゲームをプレイしている。ゲームの進行中に、ピア105は、ピア105が発生させる動作または事象を表す更新メッセージを生成する。例えば、プレーヤのコンピュータシステム(ピアAなど)でゲームソフトウェアを実行中に、コンピュータシステムは、ほかのプレーヤのコンピュータシステムによって使用される、移動または発射などのゲーム中の動作を表す(例えば、プレーヤの位置を更新する)更新データを生成する。更新が有効となるには、各ピア105が、更新を行うピア105から更新を受信することが必要である。ピア105は、ネットワーク100全体に更新メッセージをリレーして、各ピア105にメッセージを伝達する。
【0014】
一例では、ピアAは、他のピアに送信する更新を有している。ピアAは、更新データ、ピアAが更新の発信元であることを示す識別子、およびこのメッセージを、ピアAが送出する他のメッセージと区別し、相対シーケンスを提供するシーケンス識別子を有する更新メッセージを作成する。ピアAは、ピアAの被接続ピアB,C,Dにメッセージを送信する。ピアBは、ピアAから受信したメッセージをピアD,Eに送信する。ピアBはピアAからメッセージを受信したため、ピアBはピアAにメッセージを送信しない。同様に、ピアCは、ピアAからのメッセージをピアG,Hに送信し、ピアDは、ピアAからのメッセージをピアB,Gに送信する。ピアBがピアDからメッセージを受信すると、ピアBは、(メッセージの識別子を使用して)同じメッセージであると認識するため、ピアBは再度メッセージをリレーしない。同様に、ピアDは、ピアBから受信したメッセージをリレーしない。ピア間でメッセージを転送するのに要する時間の点で、ピア間の接続が実質的に同じであると仮定すると、リレーの次の組において、ピアEは、ピアBからのメッセージをピアF,Iにリレーし、ピアGは、ピアCからのメッセージをピアD,Fにリレーし(またはいずれのメッセージがピアCに最初に到着したかによってはピアDからのメッセージをピアC,Fにリレーし)、ピアHは、ピアCからのメッセージをピアI,Jにリレーする。この時点で、全てのピアは、ピアAからの更新メッセージを受信している。しかし、ピアF,I,Jはメッセージを受信したばかりであるため、これらのピアはメッセージをリレーする。ピアFは、ピアEからのメッセージをピアG,Jにリレーし(またはいずれが最初に到着したかによってはピアGからのメッセージをピアE,Jにリレーし)、ピアIは、ピアEからのメッセージをピアH,Jにリレーし(またはいずれが最初に到着したかによってはピアHからのメッセージをピアE,Jにリレーし)、ピアJは、ピアHからのメッセージをピアF,Iにリレーする。この時点までに、全ピアは、メッセージを送信またはリレーしている。ピアは再度同じメッセージをリレーしないため、このメッセージの伝達が終了する。
【0015】
このようにして、メッセージがピアツーピアネットワーク100全体を伝達していく。ゲームに参加しているピアシステム105間でこのように更新情報が伝達されることが、ゲームおよびゲーム環境を支援している。ピアシステム105は、分散のために中央サーバ110を使用せずに、データをネットワーク100全体に配信することができる。さらに、各ピア105がほかのピア105の全てに直接接続されているというわけではなく、資源の節約が図られる。この結果、グリッド100は、(限られた数の他のクライアントと通信しさえすればよいため)各ピアのネットワーク帯域幅の必要条件を抑える一方で、任意の1台のクライアントからのデータを、(例えば、UDPソケットを使用して)グリッド内のほかの全ピアに迅速に伝達させることが可能となる。
【0016】
別の実施形態では、ピアツーピアリレーネットワークに含まれるピアシステムの数は上下してもよく、ネットワークの接続上限が異なっていてもよい。ピアの台数、接続上限、および接続を確立するためのルールによっては、全てのピアの全接続が使用されるわけではないこともあり、このため、利用可能な接続を有するピアが1つ(またはそれ以上)存在することもある。
【0017】
別の実施形態では、接続上限は可変である。一実施形態では、接続上限は各ピアシステムに固有であり、その場合、一部または全てのピアの接続上限が異なっていても、接続上限が異なるピアが存在しなくてもよい。各ピアは、自身の接続上限を設定するか、またはサーバによって接続上限を割り当てられる。一例では、ピアX,Yのそれぞれの接続上限が5であり、ピアZの接続上限が4であり、残りのピアの接続上限はそれぞれ3である。別の実施形態では、接続上限は動的である。この場合、サーバが、ネットワーク性能に基づくなどして、ピアの接続上限を調整する(例えば、ネットワークトラフィックが低い場合には、接続上限数が低く設定される)。別の実施形態では、ピアシステムの1つ以上が、それぞれ動的にそれぞれの接続上限を調整する。別の実施形態では、サーバが、特定のピアシステムの接続上限を動的に調整する(例えば、全ピアではなく一部のピアを調整する)。
【0018】
図2は、メッセージ205の一実施形態のブロック図を示す。メッセージ205は、ピアシステムによって、ピアツーピアリレーネットワーク内の他のピアに送信するために生成される。例えば、図1を参照すると、ピアAが他のピアに送信する更新メッセージを有する場合、ピアAはメッセージ205などのメッセージを作成する。メッセージ205には、アドレッシングデータ210、発信元識別子215、シーケンス値220、およびペイロードデータ230が含まれる。アドレッシングデータ210は、メッセージ205をそのピアから別のピアに送信するためのネットワークアドレッシング情報を含む。一実施形態では、アドレッシングデータ210は、送信側ピアのIPアドレスと、指定する受信側ピアのIPアドレスを含む。発信元識別子215は、メッセージ205を作成したピアを識別する。この識別子215は、ピアツーピアリレーネットワーク全体のピアに対し、ネットワークを介して伝達されているメッセージの発信元を示す。メッセージ205を受信するピアは、発信元識別子215を用いて、メッセージ205がネットワーク内のどのピアから送信されたかを決定することができる。シーケンス値220は、特定のメッセージ205を識別して、相対シーケンス情報を提供する。メッセージ205を受信するピアは、シーケンス値220を用いて、特定のメッセージを既に受信済みであるかを決定することができると共に、発信元識別子215が示すピアから送信されたメッセージの順序またはシーケンスを決定することができる。データ230は、メッセージ205のペイロードデータである。(例えば、ゲームにおける)更新メッセージの場合、ペイロードデータ230は、受信側ピアが使用する更新データである。代替の実装では、異なるタイプのメッセージが使用されてもよく、図2に示すものとは異なるフォーマットのメッセージが使用されてもよい(例えば、異なる情報や追加の情報を有する)。例えば、メッセージに、グリッドのメンバに発行(publish)しようとしているファイルまたはファイルの一部、ゲームデータのフレームなどのデータのフレーム、フレーム、または音声ファイルの一部が含まれていてもよい。受信ピアは、メッセージの各々に含まれるシーケンス値を使用して、ファイル全体を再構築することができる。別の例では、メッセージには、例えば、複数のグリッドに属しているピアによってリレーを行うために、メッセージが属しているグリッドを示す識別子などの付加的な識別情報が含まれてもよい。
【0019】
図3は、ピアツーピアリレーネットワークにおいて、ピアがメッセージをリレーする一実施形態のフローチャート300を示す。初期状態では、このピアは、ピアツーピアリレーネットワークにおいて1つ以上の他のピアシステムに接続されている。
【0020】
ブロック305において、ピアは、このピアと送信側ピア間の接続を介して、送信側ピアからメッセージを受信する。このメッセージには、図2のメッセージに示すように、発信元識別子、シーケンス値、およびペイロードデータ(更新データなど)が含まれる。
【0021】
ブロック310において、ピアは、受信メッセージをリレーする接続を選択する。ピアは、ピアツーピアリレーネットワークのリレールールに従って、ピアの利用可能な接続から接続を選択する。リレールールを適用した後、ピアが、ピアの接続の一部または全てを選択している場合もあれば、接続を1つも選択していない場合もある。
【0022】
ブロック315において、ピアは、選択した接続の各々にメッセージをリレーする。ピアは、選択した各接続のためにメッセージを作成する。ピアは、受信メッセージを使用するが、送信する各メッセージのアドレッシング情報を適宜更新する(例えば、接続のために送信側をこのピアに変更し、受信側を受信ピアに変更する)。したがって、ペイロードデータは変更されない。別の実施形態では、ピアは、メッセージにデータを追加するか、あるいはメッセージ内のデータを変更しうる。ピアは、作成したメッセージを適切な受信者に送信する。
【0023】
図4は、ピアツーピアリレーネットワークにおいて、ピアがリレールールの組に従ってメッセージをリレーする一実施形態のフローチャート400を示す。図4で使用するリレールールは、リレールールの組の例である。別の実施形態では、異なるリレールールまたは追加のリレールールを使用してもよい。初期状態では、リレーピアは、ピアツーピアリレーネットワークにおいてNの他のピアシステムに接続されている。例えば、図1に示すネットワークでは、ピアDは、3つの他のピアに接続されている(この場合N=3)。メッセージをリレーするための図4のリレールールは、以下の通りである。
1.メッセージを2回リレーしない
2.送信元にメッセージを返さない。
3.発信元ピアにメッセージをリレーしない
4.ルール1および2を適用した後に、利用可能な接続上のピアにメッセージをリレーする
【0024】
ブロック405において、リレーピアはメッセージを受信する。ブロック410において、リレーピアは、リレーピアが以前にこのメッセージを受信しているかどうかを決定する。リレーピアは、メッセージの識別データを、リレーピアが記憶している、以前に受信しているメッセージのデータと比較する。一実施形態では、各ピアは、受信済みのメッセージの発信元識別子およびシーケンス値の受信メッセージテーブルを維持している。リレーピアは、受信メッセージから発信元識別子およびシーケンス値を取得して、この情報を、リレーピアの受信メッセージテーブルに記憶されているデータと比較する。リレーピアが、リレーピアがこの受信メッセージを以前に受信していると決定した場合(例えば、ピアが、受信メッセージの発信元識別子およびシーケンス値を記憶している受信メッセージテーブルにエントリをみつけた場合など)、リレーピアは受信メッセージをリレーしない。別の実施形態では、リレーピアは、リレーピアが受信メッセージを以前にリレー済みであるかを確認して決定する。
【0025】
リレーピアがこの受信メッセージを以前に受信していないとリレーピアが決定した場合、ブロック412において、リレーピアは、このメッセージが受信されたことを記録する。一実施形態では、リレーピアは、リレーピアの受信メッセージテーブルに、受信メッセージの発信元識別子およびシーケンス値に対するエントリを追加する。この発信元識別子およびシーケンス値のエントリがテーブルに既に存在する場合、リレーピアはテーブルを変更しない。
【0026】
このメッセージが受信されたことを記録したら、ブロック415において、リレーピアはカウンタをセットする。リレーピアは、カウンタを使用して、リレーピアの利用可能な接続を1つずつ調べる。一実施形態では、リレーピアは、整数カウンタiを1にセットする。
【0027】
ブロック420において、リレーピアは、リレーピアが、カウンタが示す接続に接続されたピアからメッセージを受信したかどうかを決定する。受信メッセージには、受信メッセージの送信元を示すアドレッシング情報が含まれる。カウンタは接続を示しており、このため、接続されたピアとそのピアのアドレッシング情報を示すことになる。例えば、図1のピアDは3つの接続を有しており、ピアDは、各接続に数字を割り当ており、接続1にピアAが接続され、接続2にピアBが接続され、接続3にピアGが接続されている。このため、カウンタiが1の場合、ピアDは、受信メッセージのアドレッシング情報(送信元)を、ピアDに記憶されているピアAのアドレッシング情報と比較することによって、受信メッセージがピアAによって送信されたかどうかを調べる。受信メッセージが、カウンタが示す接続に接続されたピアによってリレーピアに送信された場合、リレーピアは、そのピアにメッセージをリレーしない。
【0028】
受信メッセージが、カウンタが示す接続に接続されたピアによってリレーピアに送信されたものではない場合、ブロック422において、リレーピアは、カウンタが示す接続に接続されたピアが受信メッセージの発信元ピアシステムであるかどうかを決定する。受信メッセージには、受信メッセージの発信元であるピア(メッセージのデータを最初に生成したピア、図2の発信元識別子215を思い出されたい)を示す情報が含まれる。カウンタが示す接続に接続されたピアが受信メッセージの発信元ピアシステムである場合、リレーピアはそのピアにメッセージをリレーしない。
【0029】
受信メッセージが、カウンタが示す接続に接続されたピアによってリレーピアに送信されたものではなく、かつカウンタが示す接続に接続されたピアが受信メッセージの発信元ピアシステムではない場合、ブロック425において、リレーピアは、その接続ピアにメッセージをリレーする。リレーピアは、示された接続のためにメッセージを作成する。リレーピアは受信メッセージのコピーを作成して、アドレッシング情報を適宜更新する(例えば、送信元をリレーピアに変更し、受信者を、示された接続に接続されているピアに変更する)。したがって、ペイロードデータは変更されない。リレーピアは、作成したメッセージを、示された接続を介して接続されたピアに送信する。
【0030】
ブロック430において、リレーピアは、全ての接続を確認したかどうかを決定する。リレーピアは、カウンタを、ピアツーピアリレーネットワーク内でリレーピアによって確立された接続の数と比較する。例えば、リレーピアは、カウンタiを値N(リレーピアが保持している接続の数)と比較する。リレーピアが全ての接続をチェックしている場合、リレーピアはこの受信メッセージのリレーを完了している。
【0031】
リレーピアが全ての接続のチェックを終えていない場合、ブロック435において、リレーピアはカウンタをインクリメントする。例えば、リレーピアは、カウンタiをi+1に設定する。リレーピアは、カウンタをインクリメントしたら、ブロック420に戻り、リレーピアが、インクリメントしたカウンタが示す接続に接続されたピアから受信メッセージを受け取ったかどうかを決定する。
【0032】
前述のように、別の実施形態では、異なるルールまたは追加のルールを使用しても、使用するリレールールがこれより少なくてもよい。一実施形態では、リレーピアは、送信元にメッセージを返す(例えば、これにより、送信元は、リレーピアがデータを変更しなかったことを確認することができる)。別の実施形態では、リレーピアは、メッセージの発信元であると示される(例えば、メッセージの発信元識別子によって示される)ピアにメッセージをリレーしない。別の実施形態では、リレーピアは、同じ被接続ピアに再度同じメッセージをリレーしない。別の実施形態では、リレーピアは、メッセージをリレーするために、利用可能な接続のサブセットを選択し、例えば、応答時間が最短のピアおよび応答時間が最長のピアなどを選択する。別の実施形態では、メッセージが一定回数しかリレーされないように、各ピアは、メッセージに格納されているホップカウントに従って全てのピアの被接続ピアにメッセージをリレーする。別の実施形態では、ピアは、限られた回数(2回以上)だけ同じメッセージをリレーする。
【0033】
図5は、ピアツーピアリレーネットワークを確立する一実施形態のフローチャート500を示す。初期状態では、図1のピアAおよびサーバ110などのピアシステムおよびサーバが配置されている。ブロック505において、ピアシステムはサーバへの接続をオープンする。ピアシステムは、ピアツーピアリレーネットワーク(またはグリッド)を確立するためにサーバに接続しようとしており、このピアシステムは、「確立ピア」と呼ぶことができる。サーバへの接続は、直接ネットワーク接続または間接ネットワーク接続でありえる。一実施形態では、ピアは、サーバが維持しているスペースのサブセクションあるいは複数のワールドまたは環境のうちの1つに割り当てられるか、あるいはそこに参加および登録する。サーバは、ピアが対話を続けるのを許可する前に、ピアを認証する。ブロック510において、ピアシステムはグリッド作成要求をサーバに送る。グリッド作成要求は、ピアの識別情報と、ピアが新しいピアツーピアリレーネットワークの確立をサーバに対して要求していることを示している。一実施形態では、この要求には、ピアがサーバに対して適用を要求する条件(例えばグリッドに参加するうえでの制約)も含まれる。別の実施形態では、この要求は、グリッドにおいて使用する接続上限およびルールの組(リレールールおよび接続ルールなど)を示している。ブロック515において、サーバは新しいグリッドを登録する。サーバは、確立済みのグリッドをトラッキングしているデータのテーブルまたはリストを保持している。サーバは、新しいグリッドのために新たにテーブルを作成し、このテーブルに要求元のピアを追加する。ブロック520において、サーバは、グリッドが確立されたという確認をピアに送信する。この確認には、ピアがグリッドにアクセスするうえで必要なあらゆる識別情報またはアクセス情報が含まれる。一実施形態では、この確認には、接続上限およびグリッドのルール(リレールールなど)が含まれる。
【0034】
図6は、ピアツーピアリレーネットワークにピアを接続する一実施形態のフローチャート600を示す。初期状態では、図1のピアAおよびサーバ110などのピアシステムおよびサーバによってピアツーピアリレーネットワークが確立されている。
【0035】
ブロック605において、ピアシステムがサーバに接続する。ピアシステムは、ピアツーピアリレーネットワーク(またはグリッド)に参加するためにサーバに接続しようとしており、このピアシステムは、「新規ピア」または「参加ピア」と呼ぶことができる。サーバへの接続は、直接ネットワーク接続または間接ネットワーク接続でありえる。一実施形態では、ピアは、サーバが維持しているスペースのサブセクションあるいは複数のワールドまたは環境のうちの1つに割り当てられるか、あるいはそこに参加および登録する。サーバは、ピアが対話を続けるのを許可する前に、ピアを認証する。
【0036】
ブロック610において、ピアは、サーバの利用可能なグリッドのうちからグリッドを選択する。一実施形態では、ピアは、利用可能なグリッドのリストを要求し、そのリストの中から選択する。別の実施形態では、ピアがサーバに接続すると、サーバは利用可能なグリッドのリストを自動的に提供する。一実施形態では、サーバは、ピアが登録しているワールドに対し、利用可能なグリッドのリストを提供する。また、サーバは、選択を支援する追加情報(既に各グリッドのメンバになっているピアなど)を提供してもよい。ピアはグリッドの選択をサーバに送る。
【0037】
ブロック615において、サーバは、選択されたグリッドに既に参加しているピアのアドレスを送信する。このアドレスは、グリッドメンバと通信する方法(例えばIPアドレス)を示している。アドレスは、サーバを介した接続でなく、グリッドメンバとのピア接続を確立するためのものである。選択されたグリッドがアクセスを制限しており、新しいピアが選択されたグリッドへの参加を許されない場合、サーバはピアにアドレスを提供せずに、ピアに別のグリッドを選択するように提案する。一実施形態では、サーバは、新しいピアへのアドレスと共に、選択されたグリッドの接続上限およびルールを提供する。
【0038】
ブロック620において、新規ピアは、グリッドの各メンバに参加メッセージを送信する。参加メッセージは、新規ピアのアドレスと、そのピアがグリッドに新規に加入することを示している。別の実施形態では、新規ピアは、ピアのアドレスおよびピアが利用可能な接続の数を示す接続利用可能メッセージを送信する(これは、後述するようにピアが切断する場合と同様である)。別の実施形態では、新規ピアは1つのグリッドメンバに参加メッセージを送信し、そのグリッドメンバがグリッドを介して参加メッセージをリレーし始める。
【0039】
ブロック625において、グリッドメンバは、参加メッセージを受信して、それぞれ新規ピアに参加応答を返信する。参加応答は、応答したピアが利用可能な接続を有するかどうかを示している。肯定応答は、応答したピアが利用可能な接続を有することを示している。否定応答は、応答したピアが利用可能な接続を有さないことを示している。応答したピアは、参加メッセージから得た新規ピアノアドレスを記録して、そのアドレスを使用して参加応答を送信する。新規ピアは参加応答を受信する。
【0040】
ブロック630において、新規ピアは、接続するグリッドメンバを選択する。新規ピアは、接続ルールの組を使用して、接続するピアを選択する。例えば、一実施形態では、新規ピアは、肯定応答を送信したピアを、新規ピアが肯定応答を受信した順に、グリッドの接続上限に達するまで選択する(例えば、接続上限が3の場合、新規ピアは、最初に受信した3つの肯定応答に対応するピアを選択する)。実装によって、異なる接続ルールの組が使用されてもよい。新規ピアは、選択したピアのそれぞれの応答時間を記憶する。別の実施形態では、新規ピアは、全応答(肯定応答および否定応答)の応答時間を記憶する。
【0041】
新規ピアは、接続するピアを選択したら、ブロック635において、選択したピアへの接続をオープンする。新規ピアは選択したピアのそれぞれに接続要求を送信して、選択されたピアは要求を確認し、接続をオープンする(選択されたピアで接続が利用不可となった場合を除く)。ピア間の接続は、直接であっても間接的(例えば、インターネット等のネットワークを介するなど)であってもよい。一実施形態では、ピアが接続をオープンすると、各ピアはこの接続をサーバに通知する。
【0042】
別の実施形態では、サーバは、1つ以上の接続を強制的に確立させることによってグリッドに参加し易くする。サーバは、あるピアに接続をクローズさせて、指定した別のピアに接続をオープンさせうる。また、サーバは、ピアにそのピアの接続の1つ以上をクローズさせうる。
【0043】
図7は、図6のブロック630などにおいて、ピアツーピアリレーネットワークに参加するためにピアを選択する一実施形態のフローチャート700を示す。初期状態では、新規ピアがグリッドを選択しており、そのグリッドのメンバピアに参加メッセージを送出している。新規ピアは、メンバピアから返された参加応答を受信している。
【0044】
ブロック705において、新規ピアは、最初に受信した肯定応答に対応するピアを選択する。この肯定応答は、ほかの肯定応答より先に受信され、利用可能な接続のうち最も高速なものを示している。ブロック710において、新規ピアは、最後に受信した肯定応答に対応するピアを選択する。この肯定応答は、ほかの肯定応答より後に受信され、利用可能な接続のうち最も低速なものを示している。最後の応答を決定するために、新規ピアは、全ての応答を受信するまで待機するか、あるいは定義された期間待機し、その期間に最後に受信した応答を最後の応答とする。ブロック715において、新規ピアは、新規ピアが選択した接続の数が接続上限に等しくなるまで、残りの肯定応答からピアを無作為に選択する。このような選択により、グリッドを通る高速な接続と低速な接続が均等に散らばるようになる。
【0045】
前述のように、様々な実装において、異なる接続ルールまたは追加の接続ルールが使用されてもよい。一実施形態では、新規ピアは、最初の肯定応答および最後の肯定応答に対応するピアを選択し、次に、(最初の肯定応答に続いて)応答時間の短い順の肯定応答に対応するピアから順に選択していく。別の実施形態では、新規ピアは、待機してからピアの選択を開始するのではなく、応答が到着し次第ピアを選択する(例えば、最後に受信する肯定応答のために1つの接続を残しておく)。別の実施形態では、新規ピアは、応答時間のしきい値を使用してピアを選択する(例えば、応答時間がある許容値を超えるピアを選択しない)。別の実施形態では、新規ピアは、記憶容量、演算速度、アクセスレベルまたは利用可能な機能などのピアの特性に基づいて(参加応答内に提供された情報を使用して)ピアを選択する。
【0046】
一実施形態では、ピアシステムは、接続の選択に使用する選択処理(selection process)に従って、接続を分類する。例えば、ピアは、オープンしている接続のうち、最短の応答時間で受信した参加応答に対応する接続と、最長の応答時間で受信した参加応答に対応する接続とを示す情報を記憶する。グリッドから切断するピアおよびグリッドに参加する新規ピアのために接続が調整されると、ピアは記憶している接続の分類を調整しうる。
【0047】
別の実施形態では、新規ピアは、接続のオープンを支援するサーバを使用する。一実施形態では、サーバは、利用可能な接続を有するグリッドメンバと、そのメンバピアのアドレスとを記載したリストを提供する。新規ピアは、提示されたグリッドメンバに参加メッセージを直接送信する。
【0048】
肯定応答の数が接続上限よりも少ない場合、新規ピアの利用可能な接続が余っている。一実施形態では、新規ピアは、別のピアに強制的に既に確立されている接続をクローズさせて、新規ピアとの接続をオープンさせることができる。
【0049】
図8は、ピアツーピアリレーネットワークにおいて、ピアに、新しいピアへの接続を強制的に付与させる一実施形態のフローチャート800を示す。初期状態では、新規ピアがグリッドを選択しており、グリッドのメンバピアに参加メッセージを送出している。新規ピアは、メンバピアから返された参加応答を受信している。しかし、新規ピアは、全肯定応答に対応するピアを選択した後も、利用可能な接続をまだ有している。
【0050】
ブロック805において、新規ピアは、否定応答に対応するピアを選択する。新規ピアは、肯定応答と同じ接続ルールを使用して、否定応答を選択する(例えば図7のルールに従って、最初に受信した否定応答を選択する)。別の態様では、新規ピアは、異なる強制接続ルールの組を使用する。新規ピアは、その新規ピアに既に接続されているピアを選択しない。
【0051】
ブロック810において、新規ピアは、選択したピアに強制接続要求を送信する。強制接続要求は、新規ピアが少なくとも1つの利用可能な接続を有すること(またはその具体的な数)と、受信側ピアが新規ピアとの接続をオープンすべきこととを示している。
【0052】
ブロック815において、新規ピアは強制接続要求を受信して、クローズする接続を選択する。受信側ピアは、接続ルールを逆に使用して、クローズする接続を選択する。応答時間に基づいた接続ルールを使用する場合、受信側ピアは、参加応答(および後述するように接続利用可能応答)から取得して記憶した応答時間を使用する。一実施形態では、受信側ピアは、無作為に選択されたピアから選択するために、最後に選択したピアを選択するか、またはピアを再度無作為に選択する。別の実施形態では、受信側ピアは、別の強制切断ルールの組を使用する。
【0053】
ブロック820において、受信側ピアは選択した接続をクローズする。受信側ピアは、選択した接続に接続されているピアにクローズメッセージを送信して、この2つのピアは接続をクローズする。選択した接続に接続されているピアは、この段階で、利用可能な接続を有しており、後述するように、グリッドに接続利用可能メッセージを送出する。
【0054】
ブロック825において、受信側ピアは新規ピアに確認を送信して、この2つのピアは新しい接続をオープンする。この段階で、新規ピアの利用可能な接続が1つ減っている。新規ピアが利用可能な接続をほかに有する場合、新規ピアは、ブロック805に戻って、別の否定応答を選択する処理を繰り返す。
【0055】
別の実施形態では、新規ピアが少なくとも2つの利用可能な接続を有さない限り、新規ピアは別のピアに強制的に接続をオープンさせることはない。別の態様では、別のしきい値(3など)が使用されてもよい。別の実施形態では、新規ピアの接続数が、少なくともある数(接続最低数[connection floor])に達していない場合、新規ピアは強制接続メッセージを送信する。
【0056】
別の実施形態では、強制接続メッセージの受信側ピアは、(例えば、ネットワークの負荷分散の状況によっては)これを拒否することができる。拒否された場合、新規ピアは、新しい強制接続メッセージを送信する別のピアを選択する。
【0057】
別の実施形態では、新規ピアが利用可能な接続を2つ以上有しており、かつ強制接続メッセージを送信する場合、新規ピアは、この新規ピアが利用可能な接続を2つ有することを示す情報をこのメッセージに含める。受信側ピアがクローズする接続を選択すると、受信側ピアは、選択した接続の被接続ピア(リモートピア)に対して、新規ピアが別の利用可能な接続を有することを示す(適宜新規ピアのアドレスを含める)。受信側ピアがリモートピアとの接続をクローズしたら、リモートピアは、(新規ピアがリモートピアに既に接続されている場合を除いて)新規ピアに接続利用可能メッセージを直接送信する。新規ピアは、(新規ピアが選択した)受信側ピアとの新しい接続と、(受信側ピアが選択した)リモートピアとの別の新しい接続とをオープンする。このようにして、新規ピアは、2つの接続を迅速に確立することができる。新規ピアが利用可能な接続をまだ2つ有する場合、新規ピアは、利用可能な接続を2つ有することを示す強制接続メッセージを、選択した別の受信側ピアに再度送信しうる。
【0058】
ピアシステムが別のピアシステムから切断すると、これらのピアはそれぞれ利用可能な接続を有することになる。これらのピアのうちの1つ(または両方)がまだグリッドに留まっている(すなわち、グリッドから切断されていない)場合、ピアは、そのピアの残りの被接続ピアに接続利用可能メッセージを送出して、グリッドを介してグリッド内のほかの全ピアにメッセージをリレーさせる。
【0059】
図9は、ピアツーピアリレーネットワークにおける切断の一実施形態のフローチャート900を示す。初期状態では、ピアシステム(被切断ピア)が、ピアツーピアリレーネットワークにおいて少なくとも2つの他のピアシステムに接続されている。
【0060】
ブロック905において、被切断ピアは、被切断ピアが最初に接続されていたピアの1つから切断される。この切断は、一方の末端での自発的な切断か、あるいは接続自体の障害(例えば、ピア間の経路の一部に障害が発生したなど)が原因で発生する。例えば、自発的な切断は、(後述のように)接続されたピアが応答しない場合、または(前述のように)ピアが新規ピアとの接続のオープンを強制される場合に発生しうる。一実施形態では、サーバが、ピアに1つ以上の接続をクローズさせ、これを受けて切断が発生することがある。
【0061】
ブロック910において、被切断ピアは、この被切断ピアに接続されているピアに接続利用可能メッセージを送信する。接続利用可能メッセージは、被切断ピアが現在、利用可能な接続を有していることを示している。別の実施形態では、接続利用可能メッセージは、ピアが利用できる接続数を示している。
【0062】
ブロック915において、被切断ピアに接続されたピアは、接続利用可能メッセージをリレーする。ブロック920において、グリッド内のピアは、被切断メンバに、接続利用可能応答を返信する。接続利用可能応答は、応答したピアが利用可能な接続を有するかどうかを示している。肯定応答は、応答したピアが利用可能な接続を有することを示している。否定応答は、応答したピアが利用可能な接続を有さないことを示している。応答したピアは、参加メッセージから得た新規ピアノアドレスを記録して、そのアドレスを使用して参加応答を送信する。別の態様では、応答したピアは、グリッドを介して応答を返信し、これが被切断ピアにリレーされる。被切断ピアは、接続利用可能応答を受信する。
【0063】
ブロック925において、被切断ピアは、グリッドメンバの1つから接続するメンバを選択する。被切断ピアは、接続ルールを使用して接続するピアを選択するが、被切断ピアは、その被切断ピアに既に接続されているピアを選択しない。例えば、一実施形態では、被切断ピアは、接続利用可能応答の応答時間と、被切断ピアにまだ接続されているピアの記憶している応答時間を使用して、失った接続を補充するためのピアを選択する。実装によって、異なる接続ルールの組が使用されてもよい。被切断ピアは、選択したピアの応答時間を記憶する。別の実施形態では、被切断ピアは、全応答(肯定応答および否定応答)の応答時間を記憶する。一実施形態では、被切断ピアは、その被切断ピアが一定の期間内に切断されたピアから選択することはない。
【0064】
接続するピアを選択したら、ブロック930において、被切断ピアは、選択したピアへの接続をオープンする。被切断ピアが選択したピアに接続要求を送信して、選択されたピアは要求を確認し、接続をオープンする(選択されたピアで接続が利用不可となった場合を除く)。ピア間の接続は、直接であっても間接的(例えば、インターネット等のネットワークを介するなど)であってもよい。一実施形態では、接続されたピアは、接続を確認する更新をサーバに送信する。
【0065】
図8を参照して前述したグリッドに参加するための実装に同様に、一実施形態では、被切断ピアは、接続利用可能メッセージを使用して接続のオープンを試みた後も、(例えば、全ての接続利用可能応答が否定応答であったため)利用可能な接続をまだ有する場合、被切断ピアは、前述のように強制接続メッセージを送出しうる。
【0066】
別の実施形態では、被切断ピアは、新しい接続のオープンを支援するサーバを使用する。一実施形態では、サーバは、利用可能な接続を有するグリッドメンバと、そのメンバピアのアドレスを記載したリストを提供する。被切断ピアは、提示されたグリッドメンバに接続利用可能メッセージを直接送信する。
【0067】
グリッド内のピアシステムは、定期的にポーリングし合うことによって、グリッドを維持している。一実施形態では、接続されたピアは、接続と、接続されたピアがまだ機能していることとを確認するために定期的にメッセージを送信し合う。
【0068】
図10は、ピアツーピアリレーネットワークを維持する一実施形態のフローチャート1000を示す。初期状態では、グリッド内に複数のピアシステムが接続されている。
【0069】
ブロック1005において、あるピアが、そのピアに接続されている各ピアに、維持メッセージを送信する。維持メッセージは、受信側に対して、維持メッセージを受信したことを示す確認を提供するように求める要求である。一実施形態では、ピアは、接続された各ピアにpingメッセージを送信する(またはpingを行う)。ブロック1010において、ピアは、維持メッセージに対して受信した応答を評価する。ピアは、応答が良好かどうかを決定する。一実施形態では、接続されたピアから応答を受信できない場合、ピアは、ピアの接続に障害が発生している(接続あるいは接続されたピアのいずれかが原因となる)と決定する。制限時間までに応答を受信できない場合、ピアは、ピアの接続に障害が発生していると決定する。ブロック1015において、ピアは、障害が発生しているとピアが決定した接続の接続をクローズする。ピアは、障害のある接続の被接続ピアに接続クローズ要求を送信する。ピアは、確認を受信すると、接続をクローズする。ピアが障害のある接続の被接続ピアと通信できない場合、または制限時間内に確認を受信しなかった場合は、ピアは、確認なしで接続をクローズする。別の実施形態では、接続が、所定時間の間、または所定の障害の回数だけ、障害が発生していると判定されるまで、ピアは接続をクローズするのを待機する。一実施形態では、ピアは、クローズされた接続について確認する更新をサーバに送信する。
【0070】
ピアが接続をクローズしていると、ピアは、(例えば、図9を参照して前述したように)1つ以上のピアから自発的に切断して、適切な接続利用可能メッセージを送出する。
【0071】
別の実施形態では、ピアは、サーバを使用して、障害のある接続を評価する。例えば、ピアが接続に障害が発生していると決定すると、ピアは支援を求めてサーバに要求を送信する。サーバは、障害のある接続のもう一方の末端に存在するピアにメッセージを送信して、ピアに障害が発生しているか、あるいは接続に障害が発生しているかを決定する。次に、サーバは、ピアに通知して、適宜新しい接続のオープンまたはネットワークの調整を容易に行えるようにする。
【0072】
図11〜18は、グリッドを構築、調整および維持する一実施形態の例を示す。
【0073】
図11では、ピアシステム1105A(ピアA)が、サーバ1110を使用して、ピアツーピアリレーネットワーク(グリッド)1100を確立している(ピアAとサーバ1110間の接続は図示されていない)。このグリッドの接続上限は3であるため、ピアAは利用可能な接続を3つ有する。図12では、第2のピアシステム1105B(ピアB)がグリッド1100に参加している。ピアBが参加する際に、ピアBはピアAに参加メッセージを送信し、ピアAは、ピアBに肯定参加応答を送信する。ピアAとピアBは接続をオープンする。
【0074】
図13では、さらに2つのピアシステム1105C,1105D(ピアCおよびピアD)が既にグリッド1100に参加している。4つのグリッドメンバピアA〜Dのそれぞれは、グリッド1100内の他のピアと3つの接続を確立している。新しいピアシステム1105E(ピアE)がグリッドに参加する。しかし、ピアEが他のピアに参加メッセージを送信しても、各ピアA〜Dは、既にグリッド1100の接続上限によって許される最大接続数に達しているため、参加応答は全て否定応答となる。図14で、ピアEは、強制的に接続をオープンさせている。ピアEは、(例えば、ピアEがピアBの応答を最初に受信したなどの理由により)否定応答の中からピアBを選択し、ピアBに強制接続メッセージを送信する。ピアBは、接続をクローズするためにピアDを選択し、ピアDとの接続をクローズする。ピアBは、ピアEとの接続を確認し、ピアBとピアEは新しい接続をオープンする。ピアBがピアDとの接続をクローズすると、ピアDは利用可能な接続を有することになる。ピアDはピアA,Cに接続利用可能メッセージを送信し、ピアがこのメッセージをグリッド1100全体にリレーする。ピアA,B,Cは、利用可能な接続を有しておらず、このため、ピアDに否定応答を送信する。ピアEは、利用可能な接続を2つ有しており、ピアDに肯定応答を送信する。ピアDは、ピアEとの接続をオープンする。ピアEは、利用可能な接続をまだ有しており、接続利用可能メッセージを送出する。しかし、応答は全て否定応答である。ピアEは確立済みの接続を2つ有しており、利用可能な接続を1つしか有さないため、ピアEは強制的に別の接続をオープンさせることはない。
【0075】
図15では、ピアAがグリッド1100から切断する。ピアAは、ピアB,C,Dにそれぞれ接続されていた。ピアAが切断すると、ピアB,C,Dはそれぞれ利用可能な接続を有することになる。ピアB,C,Dは、接続利用可能メッセージを送出し、ピアB,C,D,Eはそれぞれ肯定応答を送信する。ピアB〜Eは、接続利用可能応答に対する応答を評価し、既存の接続のピアを除外してから、図16に示すような接続を確立する。ピアB〜Eの各々は、この段階で接続を3つ有する。
【0076】
図17では、3つの新しいピアシステム1105F,1105G,1105H(ピアF,G,H)がグリッド1100に参加し、接続を確立している。ピアB〜Hは、グリッドを維持する定期的な活動の一環として、それぞれ、自身に接続されているピアにpingメッセージを送信する。例えば、ピアBは、ピアD,E,Gを定期的にpingする。ピアDは、ピアBのpingメッセージに対して、ピアBに良好な応答を返さない(例えば、ピアDからの応答が遅すぎるか、あるいは応答がピアBに届かない)。図18で、ピアBは、ピアDの接続をクローズしている。ピアBが接続をクローズすると、ピアBおよびピアDは利用可能な接続を有することになる。ピアB,Dは、接続利用可能メッセージを送出し、これがグリッド1100を介してリレーされる。ピアBは、ピアG,Dから肯定応答を受信する。ピアBは、ピアGに既に接続されているため、新しい接続にピアGを選択しない。ピアBは、障害のある接続のためピアDから切断したばかりであるため、新しい接続にピアDを選択しない。ピアBは、新しい接続をオープンしない(ピアBはオープンされている接続2つを有しており、利用可能な接続を1つしか有さないため、ピアBは強制的に接続を確立しようとしないが、別の実施形態ではピアBがこれを行ってもよい)。ピアDは、ピアB,Gから肯定応答を受信する。ピアBは、障害のある接続のためピアDから切断したばかりであるため、ピアDは新しい接続にピアBを選択しない(またはピアBが新しい接続要求を拒否する)。ピアDは、ピアGを選択し、ピアGとの接続をオープンする。
【0077】
図11〜18に示した例では、グリッド1100のピアは、接続の管理にサーバ1110に依存することなく、接続をオープンおよびクローズして、グリッドを作成および調整している(しかし、サーバ1110は、グリッドの現在のメンバピアのアドレスを新規ピアに提供する支援を行っている)。
【0078】
冗長リスト
一実施形態では、グリッド内のピアは、グリッド内の現在の経路に基づいて、冗長であると決定されたメッセージの送信を回避することにより、冗長メッセージのトラフィックを削減している。
【0079】
この実装では、ピアツーピアリレーネットワーク内の各ピアは、冗長リストを記憶している。ピアの冗長リストは、このピアが、指定されたピアを発信元するメッセージを送信しない他のピアを指定している。したがって、冗長リストの各エントリは、発信元ピアと、(リレーピアに接続された)宛先ピアとを指定している。ピアが、そのピアの冗長リストに存在する発信ピアを示すメッセージを受信した場合、そのピアは、冗長リストの対応するエントリが示す被接続ピアに、そのメッセージをリレーしない。別の実施形態では、ピアは、(例えば、セキュリティの問題が発生したことが判明した後など、サーバからの要求により)冗長リスト機能のオン/オフを切り替えうる。
【0080】
図19は、ピアツーピアリレーネットワークにおいて冗長リストを作成する一実施形態のフローチャート1900を示す。初期状態では、複数のピアシステムが接続され、ピアツーピアリレーネットワークが形成されている。受信側ピアは、少なくとも2つの他のピアに接続されている。
【0081】
ブロック1905において、受信側ピアが、接続されたピアから冗長メッセージを受信する。受信側ピアが同じメッセージを既に受信しているため、この冗長メッセージは冗長である。受信側ピアは、受信メッセージにある情報を使用して、冗長メッセージが同一であると識別する。前述のように、一部の実装では、各ピアは、同じメッセージを2回リレーしないように、受信したメッセージのリストを維持している。受信側ピアは、冗長メッセージを特定するためにも、このリストを使用することができる。
【0082】
ブロック1910において、受信側ピアは、冗長更新メッセージを作成する。受信側ピアは、冗長更新メッセージに、メッセージの発信元を特定する情報と受信側ピアを特定する情報とを含める。例えば、受信側ピアは、冗長メッセージから発信元識別子を取得して(例えば、図2に示したメッセージを思い出されたい)、この発信元識別子を冗長更新メッセージに記憶させる。
【0083】
ブロック1915において、受信側ピアは、冗長メッセージの送信元に冗長更新メッセージを送信する。冗長メッセージは、そのアドレス情報に、冗長メッセージの送信元のアドレス情報を含んでいる。
【0084】
ブロック1920において、冗長メッセージの送信元は、冗長更新メッセージを受信して、送信元の冗長リストを更新する。送信元は、冗長メッセージの発信元および冗長メッセージの受信側(受信側ピア)を特定する情報を、冗長更新メッセージから取得する。送信元は、送信元の冗長リストに、送信元が、指定されている発信者を発信元とするメッセージを受信側ピアに送信すべきではないと指定するエントリを追加する。
【0085】
例えば、図1に示すグリッド100を参照すると、ピアBは、ピアCを発信元とするメッセージを、ピアA,D,Eのそれぞれから受信する。ピアBがピアCを発信元とするメッセージを、ピアAから最初に受信したと仮定すると、ピアCを発信元とし、ピアD,Eから受信するメッセージは、冗長メッセージである。ピアBは、ピアCを発信元、およびピアBを受信側に指定する、ピアD,Eに送信する冗長更新メッセージを作成する。ピアBは、ピアDに冗長更新メッセージを送信する。ピアDは、ピアDがピアCを発信元とするメッセージをピアBにリレーしないことを示すために、自身の冗長リストを更新する。ピアEは、ピアBから同様の冗長更新メッセージを受信して、同じように自身の冗長リストを更新する。
【0086】
ピアがグリッドに接続したりグリッドから切断すると、クライアント間の経路が変化し、このため冗長リストが不正確となりうる。したがって、ピアがグリッドから切断したときに、残りのピアは冗長リストを更新する。
【0087】
図20は、ピアツーピアリレーネットワークにおいて切断ピアのために冗長リストを更新する一実施形態のフローチャート2000を示す。初期状態では、複数のピアシステムが接続され、ピアツーピアリレーネットワークが形成されている。切断しようとしているピアは、少なくとも2つの他のピアに接続される。
【0088】
ブロック2005において、切断ピアがグリッドから切断する。以前にこの切断ピアに接続されていたピアは、この時点で被切断ピアとなる。被切断ピアのそれぞれは、下記の同じ処理を取る。
【0089】
ブロック2010において、被切断ピアは冗長解除メッセージを作成する。冗長解除メッセージは、被切断ピアを特定する情報を示している。ブロック2015において、被切断ピアは、被切断ピアにまだ接続されているピアに冗長解除メッセージを送信する。ブロック2020において、被切断ピアから冗長解除メッセージを受信したピアは、自身の冗長リストを更新する。冗長解除メッセージを受信したピアは、ピアの冗長リスト内のエントリを削除し、冗長解除メッセージが指定する被切断ピアへのメッセージのリレーを変える。
【0090】
図1,19を参照して上述した例に戻ると、ピアDは、ピアCを発信元とするメッセージを、ピアBにリレーすべきではないと指定するエントリを、自身の冗長リストに持っている。ピアAがグリッドから切断すると、ピアBはピアAの切断を認識し、冗長解除メッセージを作成する。ピアBは、ピアD,Eに冗長解除メッセージを送信する。ピアDは、ピアBから冗長解除メッセージを受信し、ピアDが、ピアCを発信元とするメッセージを、ピアBにリレーすべきではないことを指定している、ピアDの冗長リスト内のエントリを解除する。したがって、次にピアDがピアCを発信元とするメッセージを受信すると、ピアDはピアBにメッセージを再びリレーするようになる。ピアEも、同様に自身の冗長リストを更新する。
【0091】
複数のグリッド
一実施形態では、ピアシステムは、複数のピアツーピアリレーネットワークに属することができる。各グリッドは、関連しているか、あるいは独立しうる。各グリッドに従って確立された接続は、独立でありうる。したがって、ピアはあるグリッド内の1つのピアに接続されるが、別のグリッドにおいて(2つのピアの両方が両方のグリッドに存在する場合であっても)接続されないことがある。一実施形態では、2つのピアが2つのグリッドにおいて接続されている場合、ピアは1つの接続を使用する。メッセージには、そのメッセージが属するグリッドを示す情報が含まれる。ピアは、受信メッセージの指定されたグリッドに対応して確立された接続に従って、そのメッセージをリレーする。
【0092】
一実施形態では、ピアツーピアリレーネットワークのメンバは、ピアツーピアリレーネットワーク内でサブネットワークを作成することができる。この場合、サブネットワーク内の各メンバは、大きなグリッドのメンバでもある。例えば、ピアツーピアリレーネットワークは、ピアシステムとしてゲームの全プレーヤを有しており、(全プレーヤのサブセットを含む)各チームは、(例えば、ゲーム内での専用通信のために)ピアシステムのサブネットワークを有する。このようにして、ピアは、データを好適に配信および受信するためのマルチチャネル環境を確立することができる。
【0093】
別の実施形態では、ピアツーピアリレーネットワークは、独立しているが、1つ以上のメンバピアシステムを共有している。例えば、あるピアのグループが、ロビーまたはチャット環境に対応するためにグリッドを確立し、この第1のグループに属するピアを少なくとも1つ含む別のピアのグループが、特定のゲームに対応するためにグリッドを確立しうる。別の例では、あるピアのグループが、クラン(組織)のためにグリッドを形成し、そのピアの一部が、ゲームをプレイするために別のグリッドに参加するかまたは別のグリッドを作成する。
【0094】
例えば、オンライン環境では、この環境内の全ピアが1つのメイングリッドに接続されている。メイングリッドは、一般的なアナウンスメントおよび一般的なサービスに用いられる。ピアは、チャットルームやゲームなどのオンラインサービスにアクセスするために、追加の小規模なグリッドを作成したり、これに参加したり、これから離脱する。ピアは、新しいピアがグリッドへの参加を希望している場合など、小規模なグリッドを確立する前に、メイングリッドを使用して通信を行いうる(サーバを使用することはない)。全ての制御メッセージがメイングリッドを介してブロードキャスト可能であるため、全てのピアは、利用可能なグリッドのリストと、各グリッドにおいてアクティブなピアのリストを独立して維持することができる。一実施形態では、ピアは中央サーバを使用しない。
【0095】
図21は、複数のグリッドに属しているピアシステムからメッセージをリレーする一実施形態のフローチャート2100を示す。初期状態では、複数のピアシステムが接続され、2つのピアツーピアリレーネットワークが形成されている。リレーピアは、両方のグリッドのメンバであり、各グリッドのそれぞれの接続およびリレールールを有する。
【0096】
ブロック2105において、リレーピアがメッセージを受信する。このメッセージには、そのメッセージが属するグリッドを示すグリッド識別子が含まれる。
【0097】
ブロック2110において、リレーピアは、受信メッセージが指定するグリッドを選択する。各グリッドは、それぞれの接続の組とそれぞれのリレールールの組とを有する。リレーピアは、グリッドを選択することによって、受信メッセージのリレーに使用する接続の組と、使用するリレールールの組とを選択する。
【0098】
ブロック2115において、リレーピアは選択したグリッドとその対応のリレールールに従って接続を選択する。リレーピアは、選択したグリッドのリレールールを使用して、受信メッセージをリレーするための任意の適切な接続を選択する。
【0099】
ブロック2120において、リレーピアは、選択したピアに受信メッセージを送信する。リレーピアは、メッセージをリレーする前に、選択した各ピアのために受信メッセージを調整する。この際、例えば、受信メッセージのアドレス情報を更新して、受信メッセージがリレーピアから選択したピアにリレーされようとしていることを示す。
【0100】
観客
一実施形態では、グリッド内のピアは、参加者または観客に分けられる。参加者ピアは、グリッド全体にリレーさせるための新しいメッセージを生成する。観客ピアは、新しいメッセージを生成せず、グリッド内で通過ノードとして機能する。参加者および観客の両方は、グリッドのリレールールに従って、自身の被接続ピアにメッセージをリレーする。一部のアプリケーションでは、各参加者に対して観客が多数存在しうる。複数の参加者を有する一実施形態では、各参加者は、他の参加者への接続を少なくとも1つ有する。
【0101】
一例においては、参加者のグループがオンラインゲームをプレイしている間に、観客がこれを観戦する(ゲームのデータを変化させずにデータを観察する)。観客の数は、(数千など)非常に多いことがある。別の例には、パフォーマンス(音楽など)、スピーチおよび教育などがある。一部のアプリケーションでは、ピアがデータをリレーすることによって分散を処理しているため、観客の数が増加しても、分散に要するサーバの負荷が必ずしも増加するわけではない。
【0102】
一実施形態では、ピアがグリッドに参加すると、そのピアは参加者または観客としてグリッドに参加する。ピアが観客としてグリッドに参加した場合、そのピアは、新しいメッセージを作成したり、新しいメッセージをグリッドに送信してグリッド全体にリレーさせる許可を与えられない。観客が新しいメッセージを生成して、観客に接続されたピアに新しいメッセージを送信した場合、観客から新しいメッセージを受信したピアは、受信メッセージを転送またはリレーしない。一実施形態では、観客の一部または全てが、(例えば、第1のグリッドで観察しているゲームについて話し合うなどのために)参加者として別の関連グリッドを形成してもよい。
【0103】
図22は、観客および参加者に対応しているグリッドにおいてメッセージをリレーする一実施形態のフローチャート2200を示す。初期状態では、複数のピアシステムが接続され、参加者および観客に対応しているピアツーピアリレーネットワークが形成されている。
【0104】
各ピアシステムは、参加者であるピアのリストを記憶している。一実施形態では、参加者ピアは、どのピアが参加者であるかを示すメッセージを定期的にブロードキャストする。別の実施形態では、サーバが、参加者の識別を支援している。
【0105】
ブロック2205において、リレーピアがメッセージを受信する。このメッセージには、このメッセージを作成したピアを示す発信元識別子が含まれる。
【0106】
ブロック2210において、リレーピアは、受信メッセージの発信元が参加者ピアであることを確認する。リレーピアは、参加者ピアのリストを記憶している。リレーピアは、受信メッセージの発信元として識別されたピアを、参加者ピアのリストと比較する。受信メッセージの発信元ピアが参加者でない(すなわち観客である)場合、リレーピアは受信メッセージをリレーしない。
【0107】
受信メッセージの発信元ピアが参加者である場合、ブロック2215において、リレーピアはグリッドのリレールールに従って接続を選択する。リレーピアは、リレールールを使用して、受信メッセージをリレーするための任意の適切な接続を選択する。
【0108】
ブロック2220において、リレーピアは、選択したピアに受信メッセージを送信する。リレーピアは、メッセージをリレーする前に、選択した各ピアのために受信メッセージを調整する。この際、例えば、受信メッセージのアドレス情報を更新して、受信メッセージがリレーピアから選択したピアにリレーされようとしていることを示す。
【0109】
別の実施形態では、観客は、参加者と同じグリッドに存在しない。観客は、参加者グリッドにリンクされ、並行して存在する観客グリッドを形成している。観客は、参加者からデータを受信し、観客グリッドにおいてデータをリレーする。グリッド間のリンクは、サーバまたはゲートウェイによって、または各グリッドから選択したピア同士の接続によって提供されうる。
【0110】
別の実施形態では、観客は条件付き観客になることができる。条件付き観客は、グリッド全体にリレーされるデータを生成するための権限を要求することができる。観客が権限を受けている場合、観客は、グリッド内でピアがリレーするメッセージを送信することができる(例えば、メッセージに許可フラグが含まれる)。この権限は、サーバによって、調停者としての選択されたピアによって、または(1つ以上の)参加者によって付与されうる。例えば、教育の環境では、参加者が講師であり、観客は、全ピアにリレーされる質問を尋ねるための権限を要求しうる。
【0111】
アイランドの復旧
一実施形態では、ピアツーピアリレーネットワーク内のサーバおよびピアは、アイランドの形成を回避するかまたはこれから復旧するために、グリッド内の接続の調整に対応している。グリッド内で隔離されたピアのグループは、アイランドと呼ばれる。複数のピアがほぼ同時に切断すると、アイランドがグリッド内で形成されることがある。前述の切断処理においては、残ったピアが、利用可能な接続を示すメッセージを送信するが、複数の切断が同時発生した場合、残ったピアが、グリッド内で隔離されたグループを形成することがある。アイランド同士の間にピアツーピア接続がないため、あるアイランド内のピアは別のアイランド内のピアにメッセージを送信することができない。サーバはアイランドの形成を検出し、ピアと対話してアイランドを除去させる。
【0112】
図23は、グリッド内でアイランドを検出する一実施形態のフローチャート2300を示す。初期状態では、複数のピアシステムが接続され、ピアツーピアリレーネットワークまたはグリッドが形成されている。ピアが接続をオープンおよびクローズするか、または切断されると、ピアは、グリッドのサーバに、この接続の変更を通知する。このようにして、サーバは、グリッド内の全接続をトラッキングしている。サーバは、グリッド内のピアの順序付きリストも維持している。
【0113】
ブロック2305において、サーバはアイランドカウンタをセットする。アイランドカウンタは、アイランドの数を表している。一実施形態では、サーバはカウンタiを1にセットする。
【0114】
ブロック2310において、サーバは開始ピアを選択する。アイランドカウンタが1の場合、サーバは、ピアの順序付きリスト内で先頭のピアを開始ピアとして選択する。アイランドカウンタが1を超える場合、サーバは、最も最近発見された未マークのピア(これについては後述する)を開始ピアとして選択する。
【0115】
ブロック2315において、サーバは、開始ピアに接続されているピアのそれぞれを、開始ピアと同じアイランドに属するものとしてマークする。サーバは、開始ピアに直接接続されているピアと、他のピアを介して開始ピアに間接的に接続されているピアとをマークする(例えば開始ピアから被接続ピアへ、この被接続ピアに接続されたピアへ、…と処理を進めていく)。サーバは、ピアが属しているアイランドを示すために、アイランドカウンタの現在の値によってピアをマークする。
【0116】
開始ピアに接続されたピアの全てをマークしたら、ブロック2320において、サーバは、グリッドに未マークのピアが残っているかどうかを決定する。一実施形態では、サーバは、ピアの順序付きリストを順に処理して、未マークのピアを検索する。
【0117】
サーバが未マークのピアを発見した場合、ブロック2325において、サーバはアイランドカウンタをインクリメントする。サーバは、アイランドカウンタをインクリメントして、追加のアイランドが検出されたことを示す。アイランドカウンタをインクリメントしたら、サーバはブロック2310に戻り、発見された未マークのピアを開始ピアとして使用する。
【0118】
サーバが未マークのピアを発見できない場合、ブロック233において、サーバは検出されたアイランドの数を求める。サーバは、アイランドが検出されたたびにアイランドカウンタをインクリメントしたため、アイランドカウンタは、検出されたアイランドの数を表している。アイランドカウンタが1の場合、発見されたアイランドは1つであり、このためグリッドが複数のアイランドに分割されていない。アイランドカウンタが1より大きい場合、複数のアイランドが発見されており、グリッドはアイランドに分割されている。
【0119】
図24は、ピアツーピアリレーネットワークにおいてアイランドを除去する一実施形態のフローチャート2400を示す。初期状態では、複数のピアシステムが、ピアツーピアリレーネットワークまたはグリッドにおいて接続されている。グリッドが、2つのピアのアイランドに分割されており、一方のアイランド内のピアは、もう一方のアイランド内のピアへの接続経路を有していない。サーバは、図23に示した処理を使用するなどによって、この2つのアイランドを検出している。
【0120】
ブロック2405において、サーバは、各アイランドからピアを選択する。サーバは、様々な方法によって、第1アイランドのピアと第2のアイランドのピアを選択することができる。一実施形態では、サーバは、利用可能な接続を有するピアを選択する。別の実施形態では、サーバは、アイランドから無作為にピアを選択する。
【0121】
第1アイランドのピアが利用可能な接続を有さない場合、ブロック2410において、サーバは、第1アイランドのピアに接続クローズメッセージを送信して、接続をクローズする。第1アイランドのピアは、サーバからメッセージを受信し、前述のように、強制接続メッセージを受信したときにピアがクローズする接続を選択する場合と同様に、クローズする接続を選択する。第1アイランドのピアは、接続をクローズし、利用可能な接続を有するようになる。
【0122】
ブロック2415において、サーバは、第1アイランドのピアに強制接続開始メッセージを送信する。強制接続開始メッセージには、第2のアイランドのピアのアドレスが含まれる。第1アイランドのピアは、サーバからこのメッセージを受信し、第2のアイランドのピアに強制接続メッセージを送信する。
【0123】
ブロック2420において、第2のアイランドのピアは、第1アイランドのピアから強制接続メッセージを受信し、クローズする接続を選択して、選択した接続をクローズする。第2のアイランドのピアは、強制接続メッセージの受信側に関して前述したのと同様の方法で、クローズする接続を選択する。接続のクローズ前に、第2のアイランドのピアが利用可能な接続を有する場合、第2のアイランドのピアは自身の接続をクローズしない。
【0124】
ブロック2425において、第1アイランドのピアは第2のアイランドのピアに接続オープン要求を送信し、この2つのピアが接続をオープンする。ひとたび接続がオープンされると、アイランドが結合され、1つのアイランドが形成される。ピアは、この接続を確認する更新をサーバに送信する。前述のように検出したように、さらにアイランドが残っている場合、サーバはブロック2405に戻り、残りのアイランドの2つ以上を接続する。
【0125】
図25,26は、アイランドの検出および結合の例を示す。図25では、図11のグリッド1100と同様のグリッド2500は、ピアC,G,Fが同時に切断したために、2つのアイランドに分割されている。第1アイランドにはピアA,B,D,Eが含まれる。第1アイランドにはピアH,I,Jが含まれる。図26で、サーバは、ピアDにピアIとの接続をオープンさせ、2つのアイランドを結合させている。
【0126】
セキュリティ
一実施形態では、ピアツーピアリレーネットワークは、不正行為違反またはセキュリティ違反、またはこの両方の検出、およびこれらからの復旧に対応している。不正行為違反では、例えばゲームの進行を変えるため、データの操作が行われて、オンライン活動の処理の結果が変更される。セキュリティ違反では、グリッドに損害を与えるか、グリッドに障害を発生させるために、不正なデータが使用されたり、データが不適切に使用される。
【0127】
図27は、ピアツーピアリレーネットワークにおいて不正行為違反を検出する一実施形態のフローチャート2700を示す。初期状態では、複数のピアシステムが接続され、ピアツーピアリレーネットワークまたはグリッドが形成されている。
【0128】
ブロック2705において、ピアは、その被接続ピアの各々からメッセージを受信する。前述のように、グリッド内のピアは、グリッド全体にメッセージをリレーする。ピアは、他のピアとの各接続を介して、同じメッセージ(内容データは同じであるが、アドレス情報が異なることがある)を受信する。例えば、ピアがオープンされている接続を3つ有する場合、このピアは3つのピアから、同じメッセージを3回受信する。ピアは、メッセージ内の、発信元およびシーケンス値を示す情報(図2のメッセージ205に示した発信元識別子215およびシーケンス値220など)を使用して、メッセージが同じであると特定する。異なるピアから受信した同じメッセージは、同じ発信元とシーケンス情報を有する。
【0129】
ブロック2710において、ピアは、被接続ピアの各々から受信したメッセージを比較する。ピアは、図2のメッセージ205に示すデータ230などの、メッセージのデータ部分を比較する。ピアは、受信メッセージのいずれかについて、メッセージのデータ部分が異なっているかどうかを決定する。一実施形態では、ある被接ピアから受信したメッセージのデータ部分が、別の被接続ピアから受信した同じメッセージのデータ部分と異なる場合、ピアは、不正行為違反が発生したと決定する。ピアは、データが異なっているメッセージを送信したピアが不正行為違反の原因であると決定する。別の態様では、ピアは、異なる技術を使用して、不正行為違反を検出するか、または不正行為違反の原因ピアを特定する。適宜、ピアは、データ部分が異なるメッセージをリレーしない。
【0130】
不正行為違反が発生している場合、ブロック2715において、ピアは不正行為警告を送信する。不正行為警告は不正行為違反が発生していることと、不正行為違反の原因であるピアを示している。ピアは、接続されたピアに不正行為警告を送信し、グリッド全体に警告をリレーさせる。別の実施形態では、ピアは、サーバに不正行為警告を送信して、適切な処置を求める。
【0131】
ブロック2720において、ピアが不正行為警告を受信すると、ピアは侵害に対する復旧措置をとる。ピアは、不正行為を行っているピアがグリッドの活動に影響し続けるのを阻止するための処置をとる。一実施形態では、ピアは、不正行為を行っているピアからのメッセージを無視する。別の実施形態では、ピアは、不正行為を行っているピアをグリッドから強制的に切断させる。ピアは、異なるデータが含まれるメッセージの影響を是正するための処置もとり、これには、例えば、不正行為メッセージの特定に用いた他のメッセージのデータが示す正しいデータを有する代替メッセージを送出することなどがある。別の態様では、ピアのうちの1つが正しいデータを推定して、この正しいデータをグリッド全体にリレーする。別の実施形態では、ピアは、サーバに通知することによって、不正行為警告に対応する。この場合、サーバは、例えば不正行為違反の原因となっているピアを切断することによって、不正行為違反に対処する。
【0132】
別の実施形態では、ピアがメッセージを送信する際に、その受信者は送信ピアにメッセージを返す。送信ピアは、送信メッセージのコピーを保持している。送信ピアは、受信側から返信されたメッセージを受信すると、送信ピアは、送信メッセージのデータを受信メッセージのデータと比較する。ピアは、違いを発見して不正行為違反を検出する。ピアは、受信側がメッセージを変更したと決定し、不正行為警告を送出する。一実施形態では、複数の侵害が報告される(これは、例えば、サーバによってトラッキングされている)まで、不正行為を行っているピアに対する復旧または是正措置がとられることはない。別の実施形態では、不正行為を検出するこの返信検査(send-back check)は、不正行為の検出の最初のレイヤであり、ひとたび問題の可能性が特定されると、より複雑な手順がとられる。
【0133】
別の実施形態では、ピアは、受信メッセージ内のデータを、そのピアが生成した予測のデータの組と比較することによって、不正行為違反を検出する。ピアが、受信メッセージ内のデータが、ピアが生成したものとは異なると決定すると、ピアは、受信メッセージの送信元が不正行為違反の原因であると決定し、警告を発する。
【0134】
図1に示すグリッド100において不正行為違反を検出する例では、ピアBが、ピアA,D,Eの各々から同じメッセージを受信する。ピアBは、発信元識別子およびシーケンス値を比較することによって、メッセージが同じであると特定する。ピアBが、ピアAからのメッセージに異なるデータ部分があると検出した場合、ピアBは、ピアAが不正行為ピアであることを示す不正行為警告を送る。ピアBは、不正行為警告をピアD,Eに(および任意選択でピアAにも)送信する。ピアは、全ピアが警告を受信するまで、不正行為警告をリレーする。ピアは、この警告に対応して、ピアAからそれ以降送られてくる全メッセージを無視する。この結果、ピアB,C,Dは、ピアAからのメッセージをリレーしなくなる。
【0135】
図28は、ピアツーピアリレーネットワークにおいてセキュリティ違反を検出する一実施形態のフローチャート2800を示す。初期状態では、複数のピアシステムが接続され、ピアツーピアリレーネットワークまたはグリッドが形成されている。
【0136】
ブロック2805において、ピアは、その被接続ピアの1つからメッセージを受信する。ブロック2810において、ピアはこのメッセージを解析して、セキュリティ違反を検出する。ピアは、メッセージが無効であるかまたは無効なデータを含むことを認識して、このメッセージがセキュリティ違反であると決定する。別の実施形態では、ピアは、メッセージがそのピアにどのように送信されたかを解析することによって、メッセージがセキュリティ違反であると決定する。例えば、メッセージが、何回も繰り返し送信される同じメッセージの1つとして送信された(例えば、サービス不能攻撃にみられるように)場合、ピアは、メッセージがセキュリティ違反であると認識する。一実施形態では、メッセージが一連のパケットとして送信され、ピアは、メッセージ全体よりも下位のレベル(パケットレベルなど)でセキュリティ違反を検出する。ピアは、セキュリティ違反のメッセージの送信元がセキュリティ違反の原因であることも決定する。別の態様では、ピアは、異なる技術を使用して、セキュリティ違反を検出するか、または不正行為違反の原因ピアを特定する。ピアは、セキュリティ違反のメッセージまたはデータをリレーしない。
【0137】
セキュリティ違反が発生している場合、ブロック2815において、ピアはセキュリティ警告を送信する。セキュリティ警告はセキュリティ違反が発生していることと、セキュリティ違反の原因であるピアを示している。ピアは、接続されたピアにセキュリティ警告を送信し、グリッド全体に警告をリレーさせる。別の実施形態では、ピアは、サーバにセキュリティ警告を送信して、適切な処置を求める。
【0138】
ブロック2820において、ピアがセキュリティ警告を受信すると、ピアは侵害に対し復旧するための措置をとる。ピアは、セキュリティに違反しているピアが、グリッドに影響または損害を与え続けるのを阻止するための処置をとる。一実施形態では、ピアは、セキュリティ違反の原因であるピアからのメッセージを無視する。別の実施形態では、ピアは、セキュリティ違反の原因であるピアをグリッドから強制的に切断させる。ピアは、セキュリティ違反により発生した損害を復旧するための適切な措置もとる。別の実施形態では、ピアは、サーバに通知することによって、セキュリティ警告に対応する。この場合、サーバは、例えば違反の原因となっているピアを切断すると共に、グリッドに生じた損害を是正するための措置をとることによって、セキュリティ違反に対処する。
【0139】
図29,30は、サーバ2905およびピアシステム3005の一実施形態のブロック図をそれぞれ示す。別の実施形態では、サーバまたはピアは、図29,30に示すよりも構成要素が少なくても、異なる構成要素または追加の構成要素を含んでいてもよい。
【0140】
サーバ2905は、前述のように動作し、上記した機能を提供するための構成要素を有する。この構成要素には、グリッドの確立2910、ピアの追加2915、ピアの接続2920、ピアの切断2925、グリッドの維持2930、グリッドのデータ(接続、メンバ、接続上限など)およびルール(リレールール、接続ルールなど)の記憶および生成2935、複数のワールドの管理2940、冗長リストの管理およびその支援2940、複数のグリッドの管理2950、グリッドにおける参加者および観客の管理2955、アイランドの検出および復旧の処理2960、不正行為違反およびセキュリティ違反の管理およびそれらへの対処2965、ならびにサーバの中央サービス2970(例えば、ネットワーク通信、およびアドレッシング、プレーヤのマッチング、チャット機構、データバックのアップ等)などを行う構成要素がある。
【0141】
ピアシステム3005は前述のように動作し、上記した機能を提供するための構成要素を有する。この構成要素には、グリッドの確立3010、グリッドの参加3015、ピアの接続3020、ピアの切断3025、グリッドの維持3030、グリッドのデータ(接続、メンバ、接続上限など)およびルール(リレールール、接続ルールなど)の記憶および生成3035、冗長リストの作成、更新および使用3040、複数のグリッドにおける動作3045、グリッドにおける参加者および観客との動作およびこれらとしての動作3050、アイランドの検出および復旧の処理3055、不正行為違反およびセキュリティ違反の管理、検出およびそれらへの対処3060、ピアシステムのサービス3065(例えば、ネットワーク通信、およびアドレッシング、プレーヤのマッチング、チャット機構、データバックのアップ等)などを行う構成要素がある。
【0142】
ピアツーピアリレーネットワークの様々な実装が望ましい利点を提供する。グリッドは、オンラインの巨大なマルチプレイヤコンピュータゲームなど、多くのネットワークアプリケーションにおいて非常に有用でありえる。オンラインゲームアプリケーションは、1つの共通のデータセットを共有および維持しているという1つの点を共通に持つネットワークアプリケーションの大きなグループの一例に過ぎない。1つのピアでデータセットが更新されると、この情報が他のピアのグループに送信されて、グリッド全体にリレーされ、このため、各ピアが更新されたデータセットを有するようになる。リレーグリッドによって、接続されたピアが、(データ分散のために)中央サーバを介することなく、限られたネットワーク帯域幅でデータを相互に交換できるようになる。このネットワークは、ゲームデータ、ゲームに関連するほかの情報、メディアファイル、ストリーミングオーディオまたはストリーミングビデオの交換に使用することができる。
【0143】
例えば、一実施形態では、ピアがファイル発行(file publishing)のためにグリッドを使用する。グリッド内のピアは、この発行元に接続されたピアにファイルを送信することによってファイル(1つのメッセージかまたは複数のメッセージに分割されている)を発行し、グリッドのメンバピアは、グリッド全体にファイルを全メンバにリレーする。このようにして、グリッドの全メンバは、サーバを使用せず、かつ発行元から全てのピアへの直接接続を使用せずに、発行されたファイルを受信することができる。様々な実装において、どのような種類のファイルでも発行することができる。ファイルは、データ、メディアまたは実行可能なソフトウェアアプリケーションであってよい。グリッドを介して発行されるファイルの例には、ストリーミングメディア(オーディオおよび/またはビデオ等)、メディアファイル、ゲームまたは他のアプリケーションの再生データ、地図、アナウンスメント、メッセージ、アプリケーションのデータおよびモジュール(地図、テンプレート、テクスチャ、音声等)などがあるが、これらに限定されない。
【0144】
本発明の各種実装は、電子ハードウェア、コンピュータソフトウェアまたはこれらの技術の組合せとして実現される。大部分の実装は、プログラム可能なコンピュータによって実行される1つ以上のコンピュータプログラムを含む。例えば、一実施形態では、各ピアシステムおよびサーバは、ピアツーピアリレーネットワークの機能を実装するソフトウェアを実行している1台以上のコンピュータを有する。一般に、各コンピュータは、1つ以上のプロセッサと、1つ以上のデータ記憶要素(例えば、揮発性または不揮発性のメモリモジュール、およびハードディスクドライブ、フロッピーディスクドライブ、CD−ROMドライブ、磁気テープドライブなどの永続的な光学記憶装置および磁気記憶装置)と、1つ以上の入力装置(例えばマウス、キーボード)と、1つ以上の出力装置(例えばディスプレイコンソール、プリンタ)を有する。
【0145】
コンピュータプログラムは、通常は永続的な記憶媒体に記憶されており、その後実行時にメモリにコピーされる実行可能コードを含む。プロセッサは、メモリから実行可能命令を所定の順序で取得することによって、このコードを実行する。プログラムコードの実行時には、コンピュータは入力装置および/または記憶装置からデータを受け取って、データに対して処理を実行し、得られたデータを出力装置および/または記憶装置に送る。
【0146】
本発明の説明のための各種実装を記載した。しかし、当業者は、ほかの実装も可能であり、本発明の範囲に含まれるということを理解するであろう。例えば、上記の説明では、ゲームアプリケーションに対応する例を説明してピアツーピアリレーネットワークのいくつかの実装について記載したが、ファイル共有やどの他のデータ配布アプリケーションなど、他のアプリケーションも可能である。
【0147】
したがって、本発明は、前述したこれらの実施形態のみに限定されるものではない。
【図面の簡単な説明】
【0148】
【図1】ピアツーピアリレーネットワークの一実施形態の説明図。
【図2】メッセージの一実施形態のブロック図。
【図3】ピアツーピアリレーネットワークにおいて、ピアがメッセージをリレーする一実施形態のフローチャート。
【図4】ピアツーピアリレーネットワークにおいて、ピアがリレールールの組に従ってメッセージをリレーする一実施形態のフローチャート。
【図5】ピアツーピアリレーネットワークを確立する一実施形態のフローチャート。
【図6】ピアツーピアリレーネットワークにピアを接続する一実施形態のフローチャート。
【図7】ピアツーピアリレーネットワークに参加するためにピアを選択する一実施形態のフローチャート。
【図8】ピアツーピアリレーネットワークにおいて、ピアに、新しいピアへの接続を強制的に付与させる一実施形態のフローチャート。
【図9】ピアツーピアリレーネットワークにおける切断の一実施形態のフローチャート。
【図10】ピアツーピアリレーネットワークを維持する一実施形態のフローチャート。
【図11】グリッドを構築、調整および維持する一実施形態の説明図。
【図12】グリッドを構築、調整および維持する一実施形態の説明図。
【図13】グリッドを構築、調整および維持する一実施形態の説明図。
【図14】グリッドを構築、調整および維持する一実施形態の説明図。
【図15】グリッドを構築、調整および維持する一実施形態の説明図。
【図16】グリッドを構築、調整および維持する一実施形態の説明図。
【図17】グリッドを構築、調整および維持する一実施形態の説明図。
【図18】グリッドを構築、調整および維持する一実施形態の説明図。
【図19】ピアツーピアリレーネットワークにおいて冗長リストを作成する一実施形態のフローチャート。
【図20】ピアツーピアリレーネットワークにおいて切断ピアのために冗長リストを更新する一実施形態のフローチャート。
【図21】複数のグリッドに属しているピアシステムからメッセージをリレーする一実施形態のフローチャート。
【図22】観客および参加者に対応しているグリッドにおいてメッセージをリレーする一実施形態のフローチャート。
【図23】グリッド内でアイランドを検出する一実施形態のフローチャート。
【図24】ピアツーピアリレーネットワークにおいてアイランドを除去する一実施形態のフローチャート。
【図25】アイランドの検出および結合の説明図。
【図26】アイランドの検出および結合の説明図。
【図27】ピアツーピアリレーネットワークにおいて不正行為違反を検出する一実施形態のフローチャート。
【図28】ピアツーピアリレーネットワークにおいてセキュリティ違反を検出する一実施形態のフローチャート。
【図29】サーバ一実施形態のブロック図。
【図30】ピアシステムの一実施形態のブロック図。
【図31A】代表的なクライアント−サーバおよびピアツーピアのアーキテクチャの説明図。
【図31B】代表的なクライアント−サーバおよびピアツーピアのアーキテクチャの説明図。
【特許請求の範囲】
【請求項1】
ピアツーピアリレーネットワーク内のピアシステムにおけるアイランドの復旧方法であって、
ピアツーピアリレーネットワークにおいて、少なくとも1つのピアシステムを有するアイランドの存在を2つ以上検出するステップと、
第1のアイランド内のピアシステムを第2のアイランド内のピアシステムに接続することによって、検出された2つのアイランドを結合するステップと、を有し、
異なるアイランド内のピアシステム同士は接続されていない方法。
【請求項2】
アイランドの存在を2つ以上検出するステップは、
アイランドカウンタを1にセットするステップと、
前記ピアツーピアリレーネットワーク内の全てのピアシステムがマークされるまで、
(a)未マークのピアシステムを開始ピアシステムとして選択するステップと、
(b)前記アイランドカウンタの値に従って、現在の開始ピアシステムに接続されたピアシステムをマークするステップと、
(c)前記ピアツーピアリレーネットワーク内に未マークのピアシステムが残っているかどうかを決定するステップと、
(d)未マークのピアシステムが残っている場合、前記アイランドカウンタをインクリメントするステップと、のステップ(a)〜(d)を繰り返すステップと、
前記アイランドカウンタの現在の値を使用して、存在するアイランドの数を決定するステップと、を有する、
請求項1に記載の方法。
【請求項3】
検出された2つのアイランドを結合するステップは、
検出された前記2つのアイランドのそれぞれからピアシステムを選択し、第1のアイランド内の前記ピアシステムおよび第2のアイランド内の前記ピアシステムとするステップと、
第1のアイランド内の前記ピアシステムに、前記第1のアイランド内の別のピアシステムとの接続をクローズさせるステップと、
第2のアイランド内の前記ピアシステムに、前記第2のアイランド内の別のピアシステムとの接続をクローズさせるステップと、
第1のアイランド内の前記ピアシステムに、第2のアイランド内の前記ピアとの接続をオープンさせるステップと、を有する、
請求項1に記載の方法。
【請求項4】
前記ピアツーピアリレーネットワーク内の各ピアシステムは、当該ピアシステムが接続を許可される他のピアシステムの最大数を定義している接続上限を記憶しており、
各ピアシステムは、当該ピアシステムに接続された他のピアシステムにデータをリレーするための1つ以上のリレールールの組を記憶している、
請求項1に記載の方法。
【請求項5】
ピアシステムによってリレーされるデータは、ネットワーク環境用の更新データである、
請求項1に記載の方法。
【請求項6】
ピアシステムによってリレーされるデータは、オンラインゲーム用の更新データである、
請求項1に記載の方法。
【請求項7】
少なくとも1つのピアシステムがネットワーク対応ゲームコンソールである、
請求項1に記載の方法。
【請求項8】
少なくとも2つのピアシステムが前記インターネットを介して接続されている、
請求項1に記載の方法。
【請求項9】
ピアツーピアリレーネットワークにおけるサーバであって、
ピアツーピアリレーネットワークにおいて、少なくとも1つのピアシステムを有するアイランドの存在を2つ以上検出する手段と、
第1のアイランド内のピアシステムを第2のアイランド内のピアシステムに接続することによって、検出された2つのアイランドを結合する手段と、を有し、
異なるアイランド内のピアシステム同士は接続されていないサーバ。
【請求項10】
アイランドの存在を2つ以上検出する前記手段は、
アイランドカウンタを1にセットする手段と、
前記ピアツーピアリレーネットワーク内の全てのピアシステムがマークされるまで、
(a)未マークのピアシステムを開始ピアシステムとして選択するステップと、
(b)前記アイランドカウンタの値に従って、現在の開始ピアシステムに接続されたピアシステムをマークするステップと、
(c)前記ピアツーピアリレーネットワーク内に未マークのピアシステムが残っているかどうかを決定するステップと、
(d)未マークのピアシステムが残っている場合、前記アイランドカウンタをインクリメントするステップと、のステップ(a)〜(d)を繰り返す手段と、
前記アイランドカウンタの現在の値を使用して、存在するアイランドの数を決定する手段と、を有する、
請求項9に記載のサーバ。
【請求項11】
検出された2つのアイランドを結合する手段は、
検出された前記2つのアイランドのそれぞれからピアシステムを選択し、第1のアイランド内の前記ピアシステムおよび第2のアイランド内の前記ピアシステムとする手段と、
第1のアイランド内の前記ピアシステムに、前記第1のアイランド内の別のピアシステムとの接続をクローズさせる手段と、
第2のアイランド内の前記ピアシステムに、前記第2のアイランド内の別のピアシステムとの接続をクローズさせる手段と、
第1のアイランド内の前記ピアシステムに、第2のアイランド内の前記ピアとの接続をオープンさせる手段と、を有する、
請求項9に記載のサーバ。
【請求項12】
前記ピアツーピアリレーネットワーク内の各ピアシステムは、当該ピアシステムが接続を許可される他のピアシステムの最大数を定義している接続上限を記憶しており、
各ピアシステムは、当該ピアシステムに接続された他のピアシステムにデータをリレーするための1つ以上のリレールールの組を記憶している、
請求項9に記載のサーバ。
【請求項13】
有形の記憶媒体に記憶され、ピアツーピアリレーネットワークにおいてアイランドの復旧に使用されるコンピュータプログラムであって、前記プログラムは、コンピュータに、
ピアツーピアリレーネットワークにおいて、少なくとも1つのピアシステムを有するアイランドの存在を2つ以上検出し、
第1のアイランド内のピアシステムを第2のアイランド内のピアシステムに接続することによって、検出された2つのアイランドを結合させるようにさせる実行可能命令を有し、
異なるアイランド内のピアシステム同士は接続されていないコンピュータプログラム。
【請求項14】
アイランドの存在を2つ以上検出することは、
アイランドカウンタを1にセットし、
前記ピアツーピアリレーネットワーク内の全てのピアシステムがマークされるまで、
(a)未マークのピアシステムを開始ピアシステムとして選択するステップと、
(b)前記アイランドカウンタの値に従って、現在の開始ピアシステムに接続されたピアシステムをマークするステップと、
(c)前記ピアツーピアリレーネットワーク内に未マークのピアシステムが残っているかどうかを決定するステップと、
(d)未マークのピアシステムが残っている場合、前記アイランドカウンタをインクリメントするステップと、のステップ(a)〜(d)を繰り返し、
前記アイランドカウンタの現在の値を使用して、存在するアイランドの数を決定する、
請求項13に記載のコンピュータプログラム。
【請求項15】
検出された2つのアイランドを結合することは、
検出された前記2つのアイランドのそれぞれからピアシステムを選択し、第1のアイランド内の前記ピアシステムおよび第2のアイランド内の前記ピアシステムとし、
第1のアイランド内の前記ピアシステムに、前記第1のアイランド内の別のピアシステムとの接続をクローズさせ、
第2のアイランド内の前記ピアシステムに、前記第2のアイランド内の別のピアシステムとの接続をクローズさせ、
第1のアイランド内の前記ピアシステムに、第2のアイランド内の前記ピアとの接続をオープンさせる、
請求項13に記載のコンピュータプログラム。
【請求項16】
前記ピアツーピアリレーネットワーク内の各ピアシステムは、当該ピアシステムが接続を許可される他のピアシステムの最大数を定義している接続上限を記憶しており、
各ピアシステムは、当該ピアシステムに接続された他のピアシステムにデータをリレーするための1つ以上のリレールールの組を記憶している、
請求項13に記載のコンピュータプログラム。
【請求項1】
ピアツーピアリレーネットワーク内のピアシステムにおけるアイランドの復旧方法であって、
ピアツーピアリレーネットワークにおいて、少なくとも1つのピアシステムを有するアイランドの存在を2つ以上検出するステップと、
第1のアイランド内のピアシステムを第2のアイランド内のピアシステムに接続することによって、検出された2つのアイランドを結合するステップと、を有し、
異なるアイランド内のピアシステム同士は接続されていない方法。
【請求項2】
アイランドの存在を2つ以上検出するステップは、
アイランドカウンタを1にセットするステップと、
前記ピアツーピアリレーネットワーク内の全てのピアシステムがマークされるまで、
(a)未マークのピアシステムを開始ピアシステムとして選択するステップと、
(b)前記アイランドカウンタの値に従って、現在の開始ピアシステムに接続されたピアシステムをマークするステップと、
(c)前記ピアツーピアリレーネットワーク内に未マークのピアシステムが残っているかどうかを決定するステップと、
(d)未マークのピアシステムが残っている場合、前記アイランドカウンタをインクリメントするステップと、のステップ(a)〜(d)を繰り返すステップと、
前記アイランドカウンタの現在の値を使用して、存在するアイランドの数を決定するステップと、を有する、
請求項1に記載の方法。
【請求項3】
検出された2つのアイランドを結合するステップは、
検出された前記2つのアイランドのそれぞれからピアシステムを選択し、第1のアイランド内の前記ピアシステムおよび第2のアイランド内の前記ピアシステムとするステップと、
第1のアイランド内の前記ピアシステムに、前記第1のアイランド内の別のピアシステムとの接続をクローズさせるステップと、
第2のアイランド内の前記ピアシステムに、前記第2のアイランド内の別のピアシステムとの接続をクローズさせるステップと、
第1のアイランド内の前記ピアシステムに、第2のアイランド内の前記ピアとの接続をオープンさせるステップと、を有する、
請求項1に記載の方法。
【請求項4】
前記ピアツーピアリレーネットワーク内の各ピアシステムは、当該ピアシステムが接続を許可される他のピアシステムの最大数を定義している接続上限を記憶しており、
各ピアシステムは、当該ピアシステムに接続された他のピアシステムにデータをリレーするための1つ以上のリレールールの組を記憶している、
請求項1に記載の方法。
【請求項5】
ピアシステムによってリレーされるデータは、ネットワーク環境用の更新データである、
請求項1に記載の方法。
【請求項6】
ピアシステムによってリレーされるデータは、オンラインゲーム用の更新データである、
請求項1に記載の方法。
【請求項7】
少なくとも1つのピアシステムがネットワーク対応ゲームコンソールである、
請求項1に記載の方法。
【請求項8】
少なくとも2つのピアシステムが前記インターネットを介して接続されている、
請求項1に記載の方法。
【請求項9】
ピアツーピアリレーネットワークにおけるサーバであって、
ピアツーピアリレーネットワークにおいて、少なくとも1つのピアシステムを有するアイランドの存在を2つ以上検出する手段と、
第1のアイランド内のピアシステムを第2のアイランド内のピアシステムに接続することによって、検出された2つのアイランドを結合する手段と、を有し、
異なるアイランド内のピアシステム同士は接続されていないサーバ。
【請求項10】
アイランドの存在を2つ以上検出する前記手段は、
アイランドカウンタを1にセットする手段と、
前記ピアツーピアリレーネットワーク内の全てのピアシステムがマークされるまで、
(a)未マークのピアシステムを開始ピアシステムとして選択するステップと、
(b)前記アイランドカウンタの値に従って、現在の開始ピアシステムに接続されたピアシステムをマークするステップと、
(c)前記ピアツーピアリレーネットワーク内に未マークのピアシステムが残っているかどうかを決定するステップと、
(d)未マークのピアシステムが残っている場合、前記アイランドカウンタをインクリメントするステップと、のステップ(a)〜(d)を繰り返す手段と、
前記アイランドカウンタの現在の値を使用して、存在するアイランドの数を決定する手段と、を有する、
請求項9に記載のサーバ。
【請求項11】
検出された2つのアイランドを結合する手段は、
検出された前記2つのアイランドのそれぞれからピアシステムを選択し、第1のアイランド内の前記ピアシステムおよび第2のアイランド内の前記ピアシステムとする手段と、
第1のアイランド内の前記ピアシステムに、前記第1のアイランド内の別のピアシステムとの接続をクローズさせる手段と、
第2のアイランド内の前記ピアシステムに、前記第2のアイランド内の別のピアシステムとの接続をクローズさせる手段と、
第1のアイランド内の前記ピアシステムに、第2のアイランド内の前記ピアとの接続をオープンさせる手段と、を有する、
請求項9に記載のサーバ。
【請求項12】
前記ピアツーピアリレーネットワーク内の各ピアシステムは、当該ピアシステムが接続を許可される他のピアシステムの最大数を定義している接続上限を記憶しており、
各ピアシステムは、当該ピアシステムに接続された他のピアシステムにデータをリレーするための1つ以上のリレールールの組を記憶している、
請求項9に記載のサーバ。
【請求項13】
有形の記憶媒体に記憶され、ピアツーピアリレーネットワークにおいてアイランドの復旧に使用されるコンピュータプログラムであって、前記プログラムは、コンピュータに、
ピアツーピアリレーネットワークにおいて、少なくとも1つのピアシステムを有するアイランドの存在を2つ以上検出し、
第1のアイランド内のピアシステムを第2のアイランド内のピアシステムに接続することによって、検出された2つのアイランドを結合させるようにさせる実行可能命令を有し、
異なるアイランド内のピアシステム同士は接続されていないコンピュータプログラム。
【請求項14】
アイランドの存在を2つ以上検出することは、
アイランドカウンタを1にセットし、
前記ピアツーピアリレーネットワーク内の全てのピアシステムがマークされるまで、
(a)未マークのピアシステムを開始ピアシステムとして選択するステップと、
(b)前記アイランドカウンタの値に従って、現在の開始ピアシステムに接続されたピアシステムをマークするステップと、
(c)前記ピアツーピアリレーネットワーク内に未マークのピアシステムが残っているかどうかを決定するステップと、
(d)未マークのピアシステムが残っている場合、前記アイランドカウンタをインクリメントするステップと、のステップ(a)〜(d)を繰り返し、
前記アイランドカウンタの現在の値を使用して、存在するアイランドの数を決定する、
請求項13に記載のコンピュータプログラム。
【請求項15】
検出された2つのアイランドを結合することは、
検出された前記2つのアイランドのそれぞれからピアシステムを選択し、第1のアイランド内の前記ピアシステムおよび第2のアイランド内の前記ピアシステムとし、
第1のアイランド内の前記ピアシステムに、前記第1のアイランド内の別のピアシステムとの接続をクローズさせ、
第2のアイランド内の前記ピアシステムに、前記第2のアイランド内の別のピアシステムとの接続をクローズさせ、
第1のアイランド内の前記ピアシステムに、第2のアイランド内の前記ピアとの接続をオープンさせる、
請求項13に記載のコンピュータプログラム。
【請求項16】
前記ピアツーピアリレーネットワーク内の各ピアシステムは、当該ピアシステムが接続を許可される他のピアシステムの最大数を定義している接続上限を記憶しており、
各ピアシステムは、当該ピアシステムに接続された他のピアシステムにデータをリレーするための1つ以上のリレールールの組を記憶している、
請求項13に記載のコンピュータプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図25】
【図26】
【図27】
【図28】
【図29】
【図30】
【図31A】
【図31B】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図25】
【図26】
【図27】
【図28】
【図29】
【図30】
【図31A】
【図31B】
【公表番号】特表2007−509405(P2007−509405A)
【公表日】平成19年4月12日(2007.4.12)
【国際特許分類】
【出願番号】特願2006−536556(P2006−536556)
【出願日】平成16年7月15日(2004.7.15)
【国際出願番号】PCT/US2004/022991
【国際公開番号】WO2005/046171
【国際公開日】平成17年5月19日(2005.5.19)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.フロッピー
【出願人】(500551079)ソニー・コンピュータ・エンタテインメント・アメリカ・インク (95)
【Fターム(参考)】
【公表日】平成19年4月12日(2007.4.12)
【国際特許分類】
【出願日】平成16年7月15日(2004.7.15)
【国際出願番号】PCT/US2004/022991
【国際公開番号】WO2005/046171
【国際公開日】平成17年5月19日(2005.5.19)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.フロッピー
【出願人】(500551079)ソニー・コンピュータ・エンタテインメント・アメリカ・インク (95)
【Fターム(参考)】
[ Back to top ]