(57)【要約】【解決手段】複数のノードを含むピアツーピアネットワークにおいて各ノードは他のノードと通信する。各ピアノードは、キー値によって表されるアイテムのサーチリクエストを受信または開始し、アイテムをキー値の順にしたがってリストに配列し、リストを略均等なサイズの部分に分割し、各部分における第１キー値に最も近いフィンガーノードをフィンガーテーブルにおいてルックアップし、各部分に対して、対応するフィンガーノードからその部分にあるアイテムをリクエストする。または、各ノードは、ノードをキー値の順にしたがってリストに配列することにより、アイテムを複数のピアノードにブロードキャストし、リストを略均等なサイズの２以上の部分に分割し、リストの各部分とアイテムをリストの当該部分における第１キーに対応するノードに転送する。【選択図】図１
2010531020.tif 000002
【特許請求の範囲】
【請求項１】
複数のピアノードを含むピアツーピアネットワークであって、
各ピアノードは前記ピアツーピアネットワーク上の１以上の他のピアノードと通信するように構成されており、各ピアノードは、
Ａ）各アイテムがキー値によって表される複数のアイテムをサーチするリクエストを受信または開始し、前記複数のアイテムをキー値の順にしたがってリストに配列し、前記リストを略均等のサイズの２以上の部分に分割し、各部分における第１キー値に最も近いフィンガーノードをフィンガーテーブルにおいてルックアップし、当該部分にある前記アイテムに対するリクエストを対応するフィンガーノードに転送する機能、および／または
Ｂ）複数のピアノードをキー値の順にしたがってリストに配列することにより、１以上のアイテムを前記複数のピアノードにブロードキャストし、前記リストを略均等のサイズの２以上の部分に分割し、前記リストの各部分と前記１以上のアイテムを前記リストの当該部分における第１キーに対応するピアノードに転送する機能を有することを特徴とするピアツーピアネットワーク。
【請求項２】
各ピアノードは、複数のピアノードの内、他のピアノードの選択された部分集合と直接通信するように構成されており、与えられたノードに対して選択された部分集合の各ノードは、前記与えられたノード上のフィンガーテーブルに格納されたキー値と関連づけられる請求項１のピアツーピアネットワーク。
【請求項３】
前記ピアノードは分散ハッシュテーブルにしたがって編成される請求項１のピアツーピアネットワーク。
【請求項４】
前記分散ハッシュテーブルは均一なランダム分布によって特徴づけられる請求項３のピアツーピアネットワーク。
【請求項５】
前記ピアノードは、ラップトップまたはポータブルコンピュータ、サーバコンピュータ、デスクトップコンピュータおよびワークステーション、携帯コンピューティングデバイス、携帯電話、携帯情報端末、携帯型デジタルメディアプレーヤ、携帯型または手持ち式ゲーム機、ホーム娯楽デバイス、ビデオゲーム機、デジタルメディアプレーヤ、セットトップボックス、メディアセンターコンピュータ、およびストレージデバイスのグループから選択された１以上のデバイスを含む請求項１のピアツーピアネットワーク。
【請求項６】
ピアノードであって、プロセッサ、当該ピアノードをネットワークに接続する機能を有するネットワークインタフェース、およびプログラム命令とフィンガーテーブルを格納する機能を有するメモリを含み、
前記プログラム命令は、ピアツーピアネットワーク上の１以上のピアノードと通信するように前記プロセッサによって実行可能であり、
前記ピアノードは、
Ａ）各アイテムがキー値によって表される複数のアイテムをサーチするリクエストを受信または開始し、前記複数のアイテムをキー値の順にしたがってリストに配列し、前記リストを略均等のサイズの２以上の部分に分割し、各部分における第１キー値に最も近いフィンガーノードをフィンガーテーブルにおいてルックアップし、当該部分にある前記アイテムに対するリクエストを対応するフィンガーノードに転送する機能、および／または
Ｂ）複数のピアノードをキー値の順にしたがってリストに配列することにより、１以上のアイテムを前記複数のピアノードにブロードキャストし、前記リストを略均等のサイズの２以上の部分に分割し、前記リストの各部分と前記１以上のアイテムを前記リストの当該部分における第１キーに対応するピアノードに転送する機能を有することを特徴とするピアノード。
【請求項７】
前記プロセッサはマルチコアプロセッサである請求項６のピアノード。
【請求項８】
前記プロセッサはセルプロセッサである請求項６のピアノード。
【請求項９】
前記プロセッサ、メモリおよびネットワークインタフェースは、ラップトップまたはポータブルコンピュータ、サーバコンピュータ、デスクトップコンピュータおよびワークステーション、携帯コンピューティングデバイス、携帯電話、携帯情報端末、携帯型デジタルメディアプレーヤ、携帯型または手持ち式ゲーム機、ホーム娯楽デバイス、ビデオゲーム機、デジタルメディアプレーヤ、セットトップボックス、メディアセンターコンピュータ、およびストレージデバイスの構成要素である請求項６のピアノード。
【請求項１０】
前記フィンガーテーブルは、ピアツーピアオーバレイネットワークにおけるノードの部分集合に関連づけられた複数のノードキーを含む請求項６のピアノード。
【請求項１１】
前記フィンガーテーブルは複数のデータキーを含み、複数のデータキーは複数のデータキーグループに分割されており、各キーグループは対応するノードキーに関連づけられている請求項１０のピアノード。
【請求項１２】
ピアツーピアオーバレイネットワークにおけるサーチ方法であって、
各アイテムがキー値によって表される複数のアイテムをサーチするリクエストをピアノードにおいて受信または開始するステップと、
ａ）前記複数のアイテムをキー値の順にしたがってリストに配列するステップと、
ｂ）前記リストを略均等のサイズの２以上の部分に分割するステップと、
ｃ）各部分に対するフィンガーノードを当該部分における第１キー値にもとづいてフィンガーテーブル内でルックアップするステップと、
ｄ）各部分に対応する前記アイテムに対するリクエストを対応するフィンガーノードに転送するステップとを含むことを特徴とする方法。
【請求項１３】
各部分に対する前記フィンガーノードは、当該部分における前記第１キー値に最も近いキー値に対応する請求項１２の方法。
【請求項１４】
当該部分に対する前記対応するフィンガーノードにおいて、前記２以上の部分の少なくとも１つに対応する前記アイテムに対するリクエストを受けて、ａ）からｄ）までを実行するステップをさらに含む請求項１２の方法。
【請求項１５】
前記ｄ）ステップは、前記リクエストとともに、前記リクエストを始めたピアノードに関連づけられたネットワークアドレスを転送するステップを含む請求項１２の方法。
【請求項１６】
前記フィンガーテーブルのキー値に対応する１以上のノードに対して利用可能な帯域幅の量を決定するステップをさらに含む請求項１２の方法。
【請求項１７】
前記ｃ）ステップは、前記フィンガーテーブルのキー値に対応する１以上のノードに対する帯域幅の利用できる度合いにもとづいて前記２以上の部分の少なくとも１つに対する前記キー値を優先的に選択するステップを含む請求項１６の方法。
【請求項１８】
前記ｃ）ステップは、前記フィンガーテーブルのキー値に対応する前記１以上のノードに対する帯域幅の利用できる度合いにもとづいて前記２以上の部分のそれぞれに対する前記キー値を優先的に選択するステップを含む請求項１２の方法。
【請求項１９】
ピアツーピアオーバレイネットワークにおいて、１以上のアイテムのデータをピアツーピアオーバレイネットワークに編成された複数のピアノードにブロードキャストする方法であって、各ピアノードはキーに関連づけられており、当該方法は、
複数のピアノードをキー値の順にしたがってリストに配列するステップと、
前記リストを略均等のサイズの２以上の部分に分割するステップと、
前記リストの各部分と前記１以上のアイテムを前記リストの当該部分における第１キーに対応するピアノードに転送するステップとを含むことを特徴とする方法。
【請求項２０】
前記複数のノードの１以上のノードに対して利用可能な帯域幅の量を決定するステップをさらに含む請求項１９の方法。
【請求項２１】
前記リストの各部分を転送するステップは、前記第１キーに対応する前記ノードに対して利用可能な帯域幅の量にしたがって前記２以上の部分の少なくとも１つにおける第１キーを優先的に選択するステップを含む請求項２０の方法。
【請求項２２】
前記第１キーは、前記複数のピアの大部分を含むアドレス空間に責任をもつノードに対応するフィンガーテーブルのメンバである請求項２１の方法。
【請求項２３】
前記リストのある部分に対する前記第１キーに対応する前記ピアノードは、前記リストの別の部分に対する前記第１キーに対応する前記ピアノードよりも前に位置する先行者に対応する請求項２２の方法。
【請求項２４】
プログラム命令を含む有形のコンピュータアクセス可能なストレージ媒体であって、前記プログラム命令は、ピアノード上でコンピュータ実行可能であり、
ａ）前記複数のアイテムをキー値の順にしたがってリストに配列する機能と、
ｂ）前記リストを略均等のサイズの２以上の部分に分割する機能と、
ｃ）各部分に対するフィンガーノードを当該部分における第１キー値にもとづいてフィンガーテーブル内でルックアップする機能と、
ｄ）各部分に対応する前記アイテムに対するリクエストを対応するフィンガーノードに転送する機能とを実現することを特徴とする媒体。
【請求項２５】
プログラム命令を含む有形のコンピュータアクセス可能なストレージ媒体であって、前記プログラム命令は、ピアノード上でコンピュータ実行可能であり、
１以上のアイテムがブロードキャストされるべき複数のピアノードをキー値の順にしたがってリストに配列する機能と、
前記リストを略均等のサイズの２以上の部分に分割する機能と、
前記リストの各部分と前記１以上のアイテムを前記リストの当該部分における第１キーに対応するピアノードに転送する機能とを実現することを特徴とする媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
［優先権主張］
本願は、２００７年６月１８日に出願された同一出願人による米国特許出願第１１／７６４，６８０号の優先権の利益を主張し、その開示内容全体を参照によりここに組み入れる。
【０００２】
［技術分野］
本発明はピアツーピアネットワークに関し、特にピアツーピアネットワーク上でのコンテンツ配信の負荷分散に関する。
【背景技術】
【０００３】
分散型コンピューティング環境は、互いに通信するように相互結合した多数のコンピューティングシステムによって定義される。ここで、各コンピューティングシステムはクライアント機能とサーバ機能の両方を実行することができる。ピアツーピア（Ｐ２Ｐ）ネットワークは、Ｐ２Ｐネットワーク内の各コンピューティングシステムが当該ネットワーク内の他のすべてのコンピューティングシステムのピアとして定義される分散型コンピューティングシステムを表す。議論の目的のため、Ｐ２Ｐネットワーク内の各ピアコンピューティングシステムをノードと呼ぶ。また、Ｐ２Ｐネットワーク内の各ノードは、実質的に等価な機能性を有するソフトウェアを実行するように構成される。したがって、各ノードは、Ｐ２Ｐネットワーク上でデータとサービスのプロバイダおよびユーザの両方として動作する。ピアツーピアネットワークは、集中型の階層や組織をもたない分散データネットワークである。ピアツーピアネットワークは、一般にノードと呼ばれる多数のコンピュータまたは他の情報デバイス間で情報を通信する頑強で柔軟な手段を提供する。
【０００４】
Ｐ２Ｐネットワークは、比較的少ない数のサーバに計算能力と帯域幅を集中させるのではなく、主としてネットワークの参加者の計算能力と帯域幅に頼る。Ｐ２Ｐネットワークは、主としてアドホックなコネクションを介してノードを接続するために通常は用いられる。そのようなネットワークは多くの目的のために有用である。Ｐ２Ｐネットワークは、たとえば、オーディオ、ビデオ、データまたはデジタルフォーマットの任意のものを含むコンテンツファイルを共有するために使われる。電話のトラフィックのようなリアルタイムデータもまたＰ２Ｐ技術を用いて転送することができる。
【０００５】
オーバレイ・ネットワークとは、１つ以上のタイプの下位の物理的ネットワーク接続によって接続されたノードに課された、論理または仮想ネットワーク組織である。オーバレイ・ネットワークでは、ノードは仮想または論理リンクによって接続され、それらの各々は、下位の物理的ネットワークにおける１つ以上の経路に一致し得る。オーバレイ・ネットワークは典型的には、ＯＳＩネットワークスタックまたは他のタイプのネットワーキングプロトコルのアプリケーション層または他の上位層で動作するハードウェアおよび／またはソフトウェアによって実現される。
【０００６】
ピアツーピア・オーバレイ・ネットワークの１クラスは、分散ハッシュテーブル・ネットワークと呼ばれる。分散ハッシュテーブル・オーバレイ・ネットワークは、ハッシュ関数を用いて１つ以上のキー値を生成し、一意的なノードに割当てる。すべての可能なキー値の組は、ハッシュ空間と呼ばれる。ノードはハッシュ空間において、それらの割当てられたキー値に従って組織化される。ハッシュ関数は、ハッシュ空間全体にわたってノードがほぼ均一に分散されるように選択される。分散ハッシュテーブル・オーバレイ・ネットワークは典型的には、非常に拡張性が高いためしばしば何百万ものノードをサポートし、頑強なためノードが頻繁に加入または離脱することを可能とし、また、効率的なためメッセージを単一の宛先ノードに迅速にルーティングする。
【０００７】
分散ハッシュテーブルオーバレイネットワークには多数の異なるタイプがある。ピアツーピアのオーバレイネットワークのあるタイプは、Ｃｈｏｒｄ（コード）ネットワークとして知られる。Ｃｈｏｒｄオーバレイネットワークプロトコルは、"Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications", Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan, IEEE/ACM Transactions on Networking, Vol. 11, No. 1, pp. 17-32, February 2003に詳細に記載されており、参照によりここに組み入れる。別のタイプの分散ハッシュテーブル・オーバレイ・ネットワークは、Ｐａｓｔｒｙであり、"Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems," A. Rowstron and P. Druschel. IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Germany, pages 329-350, November, 2001に記載されており、参照によりここに組み入れる。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
Ｃｈｏｒｄオーバレイネットワークは、メッセージの「漸近的複雑性」から生じる対数的性質を示すことがある。たとえば、ＣｈｏｒｄリングにＮ個のノードがあり、第１ノードが第２ノードにメッセージを送信したい場合、第１ノードは通常、ノードＢを探すためにＮ個のノードの部分集合と通信しなければならない。Ｃｈｏｒｄオーバレイネットワークでは、第１ノードは一般に、すべてのＮ個のノード内、非常に小さい部分集合、具体的にはｌｏｇ２Ｎ個と通信しなければならない。この性質のおかげでＣｈｏｒｄオーバレイネットワークは、非常に大きい数Ｎのノードに対しても比較的速いメッセージングが可能である。しかしながら、Ｃｈｏｒｄオーバレイネットワークがこのｌｏｇ２Ｎのメッセージングの性質を保証できるのは、ノードのＩＤがＣｈｏｒｄリングの周りに完全にランダムに分散されている場合だけである。
【０００９】
現在の最先端のＣｈｏｒｄオーバレイネットワークはしばしばノードＩＤを分散ハッシュテーブルに均一でランダムに分散させることに頼ることで、ピアツーピアネットワークにおいてクエリとメッセージのルーティングの負荷分散を提供する。しかしながら、ノードＩＤを均一かつランダムに分散させたとしても、Ｐ２Ｐネットワークのグローバルアドレス空間内のメッセージまたはクエリの受信者のクラスタリングがボトルネックになることがある。たとえば、ピアが複数のピアノードに同じメッセージを送ろうとするとき、ある中間ノードが受信者のアドレス空間に責任をもつ場合、それらの中間ノードはメッセージを送るにつれて過負荷になることがある。
本発明の実施の形態はこのようなコンテキストで考えられた。
【課題を解決するための手段】
【００１０】
複数のノードを含むピアツーピアネットワークにおいて各ノードは他のノードと通信する。各ピアノードは、キー値によって表されるアイテムのサーチリクエストを受信または開始し、アイテムをキー値の順にしたがってリストに配列し、リストを略均等なサイズの部分に分割し、各部分における第１キー値に最も近いフィンガーノードをフィンガーテーブルにおいてルックアップし、各部分に対して、対応するフィンガーノードからその部分にあるアイテムをリクエストする。または、各ノードは、ノードをキー値の順にしたがってリストに配列することにより、アイテムを複数のピアノードにブロードキャストし、リストを略均等なサイズの２以上の部分に分割し、リストの各部分とアイテムをリストの当該部分における第１キーに対応するノードに転送する。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施の形態で使用するのに適したＣｈｏｒｄオーバレイネットワーク例を説明する図である。
【図２】本発明のある実施の形態に係るＣｈｏｒｄオーバレイに対するサーチ方法を説明するフロー図である。
【図３】本発明のある実施の形態に係るサーチを実装するＣｈｏｒｄオーバレイネットワークの一例を説明する図である。
【図４】本発明のある実施の形態に係るピアツーピアネットワークにおけるデータ分散の例を説明する図である。
【図５】本発明のある実施の形態に係るファイル分散方法を説明するフロー図である。
【図６】本発明のある実施の形態に係るＣｈｏｒｄオーバレイネットワークにおけるファイル分散の例を説明する図である。
【図７】本発明のある実施の形態に係るオーバレイネットワークを実装するのに適した一組の情報処理装置を説明する図である。
【図８】本発明のある実施の形態に係るオーバレイネットワークを実装するのに適した一組の情報処理装置を説明する図である。
【図９】本発明のある実施の形態に係るオーバレイネットワークのノードを実装するのに適した一組の情報処理装置の構成要素を説明する図である。
【発明を実施するための形態】
【００１２】
以下の詳細な説明には、説明のための多くの具体的な詳細事項が含まれるが、それらに対する多くの変更や修正も本発明の技術範囲に含まれることは、当業者であれば誰でも理解するであろう。したがって、以下に説明する本発明の好適な実施形態は、クレームされた発明の普遍性をなんら損なうことなく、また限定も行うことなく記載されている。
【００１３】
本発明の実施の形態は、ピアツーピアネットワーク上の複数の受信者に対して、ファイルまたはデータブロックのサーチもしくは配信を負荷分散させることについての問題を解決するものであり、特に受信者がグローバルアドレス空間内に均一に分散していない場合を扱う。
【００１４】
本発明の実施の形態の利点を理解するには、従来のＣｈｏｒｄサーチを理解することが役に立つ。典型的なＰ２Ｐ実装において、インターネットに接続された多数のピアは、図１に示すように、ピアツーピアネットワーク１００を形成するリングに編成される。この例では、ネットワーク１００は、ピアノード１０２、１０４、１０６、１０８、１１０、１１２、１１４、１１６、１１８、１２０、１２２、１２４、１２６および１２８を含む。簡単のため、ネットワーク１００に接続されたノードをすべて図示することはしない。各ピアノードはキーとして参照されるユニークな識別子を割り当てられる。これらの識別子は均一にランダムに分散される。しかしこのことは、本発明のすべての実施の形態に対して厳密に要求されることではない。例示の目的で、ネットワーク１００のピアノードへのキーの割り当てを表１に示す。
【００１５】
【表１】
2010531020.tif 000003
【００１６】
さらに、ネットワーク１００上の各共有ファイル（斜線で表される）もまたユニークなキーを割り当てられる。新しいピアまたはファイルをサークルに追加したり、ピアについて新しい情報が生成されるとき、その情報は、あるハッシュ関数にしたがって生成されたハッシュ番号としてハッシュテーブルに発行される。このように、ハッシュテーブルは、各データベースエントリがハッシュ番号をもつデータベースとみなすことができる。ハッシュ番号は、十分に大きな範囲の数にわたる識別子（ＩＤ）空間から選択されるため、二つのエントリが同じ識別子番号にハッシュされる見込みはきわめて小さい。たとえば、よく知られたＳＨＡ−１ハッシュ関数は１６０ビットを有し、（２８）２０個の異なる番号を表現する。ピアはＩＤ空間からランダムに識別子を選択し、自分自身をサークル内に編成する。ハッシュテーブルに発行された各オブジェクトは、そのオブジェクトをもつ特定のピアに戻るポインタである。ネットワーク１００の各ピアノードがハッシュテーブルを構成する異なる範囲のキーを追跡することに責任をもつという意味において、ハッシュテーブルは分散されていると言える。
【００１７】
ピアがハッシュテーブルに参加するとき、ハッシュテーブルのＩＤ空間において特定の範囲のキーに対する責任を割り当てられる。各ピアは、メモリに格納された、リングへの速いルックアップを提供するフィンガーテーブルを保持する。オーバレイネットワークにおけるノードのトポロジーは動的であってもよい。ノードはいつでもオーバレイネットワークに参加または離脱することができる。ノードがオーバレイネットワーク１００から離脱するとき、離脱ノードと任意の関連するノードの間のリンクを更新しなければならない。一般に、この更新は、他のノードのフィンガーテーブルまたは有効ノードに対する他のノード参照において、離脱ノードへのリンクを変更しなければならない。さらに、離脱ノードのフィンガーテーブルまたは他のノード参照によって以前にリンクされていたノードに対して、新しいリンクを構築しなければならない。それに加えて、離脱ノードに対してフィンガーテーブルまたは他のリンクを構築しなければならない。オーバレイネットワークに参加または離脱するノードを処理するためのプロトコル例は、上に引用した文献に詳細が議論されている。
【００１８】
一般的に、ネットワーク１００における各ピアノードは、フィンガーテーブルにあるあらゆるノードと直接通信することができる必要がある。これは固定接続によって実装することができるが、要求されるものではない。固定接続は、たいていのＣｈｏｒｄ実装が使うことを選ぶ最適化であるが、Ｃｈｏｒｄネットワークのオペレーションにとって基本的には必要なものではない。ネットワーク１００のノードは、他の任意のノードとの間で利用可能な直接的な通信を有する。典型的には、非フィンガーテーブルノードに対する接続性は、ある種の固定サイズのキャッシュを用いて実装してもよい。たとえば、ノードはＫ個の非フィンガーテーブルノードに対してオープンなコネクションを維持してもよい。これもまた、フィンガーテーブルを用いてＣｈｏｒｄルックアップを実行することを避けるために使うことのできる最適化に過ぎない。
【００１９】
特定のノードが、Ｃｈｏｒｄルックアッププロトコルと呼ばれるピアツーピアのサーチ技術を用いて他のノードに格納されたファイルや他の情報を探す。Ｃｈｏｒｄにより、分散された参加者の集合は、中央による調整を経ないで、与えられたキーに対する連絡（ランデブー）ポイントとしての単一のノードに合意することができる。特に、Ｃｈｏｒｄはｓｕｃｃｅｓｓｏｒ（ＩＤ）の分散評価を提供する。ここで、キーＩＤの識別子が与えられたとき、ｓｕｃｃｅｓｓｏｒ関数は、循環識別子空間においてそのＩＤの最も近くに続く識別子をもつノードのアドレスを返す。識別子空間は典型的には１６０ビットの番号である。Ｃｈｏｒｄアルゴリズムは、ノード数が時間とともに増加するとき、このマッピングの調整を行う。Ｎ個のノードのピアツーピアネットワークにおいてＣｈｏｒｄサーチを用いていずれかのキーを見つけるために、ピアは典型的にはｌｏｇ２Ｎノードと通信しなければならない。仮にＮ＝３億ノードであれば、ピアは典型的にはネットワーク上でいずれかのキーまたはピアを見つけるために約２８ノードと通信しなければならない。
【００２０】
Ｐ２Ｐネットワークでは、各ピアまたはファイル識別子をルックアップするための通信負荷を分散することが望ましい。Ｃｈｏｒｄサーチでは、ファイルをリクエストするノードが自分のフィンガーテーブルにおいてルックアップを行い、いずれのノードに対応するキーがファイルに対応するキーに最も近いかを判定する。たとえば、再び図１を参照して、ノード１０２がキー３０に対応するファイルをサーチしており、ノード１０２のフィンガーテーブルがキー５０、２５、１７、９、４、２および１をもつノードについての情報をもっているとする。具体的には、ノード１０２は、キー５０、２５、１７、９、４、２および１に対応する各ノードがどのデータキーに責任があるかについて自分のフィンガーテーブルに情報をもっている。従来のＣｈｏｒｄサーチでは、ノード１０２は自分のフィンガーテーブルにおいてルックアップを行い、キー２５をもつノード１０８がキー３０にもっとも近いと判定する。ノード１０２はキー３０に対するリクエストをノード１０８に送信する。ノード１０８がキー３０に対して責任をもつ場合、対応するファイルをノード１０２に送り返す。ノード１０８がキー３０に対して責任をもたない場合、ノード１０８は自分のフィンガーテーブルにおいてルックアップを行い、どのノードがキー３０に対する責任をもつ可能性があるかを判定する。この処理はキー３０に対して責任をもつノードが見つかるまで繰り返す。見つかった時点で、キー３０に対して責任があるノードが対応するファイルをノード１０２に送信する。
【００２１】
ノード１０２がファイルのグループを探している場合、上述のＣｈｏｒｄサーチは各ファイルに対して繰り返される。たとえば、ノード１０２がキー３０、３２、３３、５５、６６、８９および９３に対応するファイル１３０、１３２、１３４、１３６、１３８、１４０および１４２を見つけたいとする。先の例から、ノード１０２のフィンガーテーブルはキー５０、２５、１７、９、４、２および１を割り当てられたノードについての情報を含む。変更されていないＣｈｏｒｄサーチを用いるなら、ノード１０２はキー３０、３２および３３についてノード１０８に問い合わせし、キー５５、６６、８９および９３についてノード１１６（キー５０に対応する）に問い合わせして終わるであろう。ノード１０８が自分のフィンガーテーブルから、キー２９（ノード１１０）に対応するノードがキー３０、３２および３３に対して責任があると判定したとする。ノード１０８はノード１１０にこれらのファイルに対するリクエストを送るであろう。その間、ノード１１６は自分のフィンガーテーブルを調べて、キー５５、６６、８９および９３に対してどのノードが責任をもつか判定するであろう。たとえば、ノード１１８がキー５５に対して責任をもち、ノード１２０がキー６６に対して責任をもち、ノード１２６がキー８９および９３に対して責任をもつとする。この場合、キー５５、６６、８９および９３に対するサーチは、これらのファイルのほとんどすべてに対して同じ経路を取る。具体的には、すべての４つのリクエストはノード１１６を通過し、キー８９および９３に対するリクエストはノード１１６、１２４および１２６を通過する。これは、これらの経路上のノード、特にノード１１６および１２４に過大な負荷をかけることになる。ノード１０２からノード１０８および１１６に特に複数のリクエスト（矢印で示す）があることに留意する。
【００２２】
本発明の実施の形態によれば、上述のサーチに対する負荷を分散するために、ノード１０２は、キーにしたがってリクエストされたファイルのリストを並べ替え、リストを２以上の部分に分け、各部分におけるファイルに対する要求をリストの対応する部分の最初のキーに対応するノードに送信する。この実施の形態は、図２のフローチャートと図３のダイアグラムを参照することにより理解される。図２は、本発明の実施の形態に係る改良されたＣｈｏｒｄサーチの方法２００を説明する。符号２０２で示すように、Ｃｈｏｒｄオーバレイネットワークにおけるノードはファイルに対するリクエストを受信するか、開始する。上述の例のように、ノード１０２は、キー３０、３２、３３、５５、６７、８０および９３に対応するファイル１３０、１３２、１３４、１３６、１３８、１４０および１４２に対するリクエストを開始するか、受信する。符号２０４で示すように、リストをキー値にしたがう順に並べた上で、符号２０６で示すように２以上の部分に分割する。一例として、リクエスト２０２は、キー３０、３２および３３が第１部分２０８にあり、ファイル５５、６７、８０および９３が第２部分２１０にあるように分割される。ルックアップ２１２、２１４をフィンガーテーブル２１６において実行し、どのノードキーが各部分における第１キーにもっとも近いかを判定する。これらのキーに対応するノードをここではリストの各部分に対するフィンガーノードと呼ぶ。たとえば、符号２１２においてノード１０２は、キー３０にもっとも近いノードキーを見つけるためにフィンガーテーブル２１６においてルックアップを実行し、符号２１４においてノード１０２はキー５５に最も近いノードキーに対するルックアップを実行する。この例では、ノードキー２５（ノード１０８に対応）がキー３０にもっとも近く、ノードキー５０（ノード１１６に対応）がキー５５に最も近い。このようにして、ノード１０８が第１部分２０８に対するフィンガーノードになり、ノード１１６がリストの第２部分に対するフィンガーノードになる。
【００２３】
いったんフィンガーノードがリストの各部分に対して決定されると、リストの当該部分にあるファイルに対するリクエストは、符号２１８、２２０において対応するフィンガーノードに送信される。具体的には、符号２１８において、ノード１０２は、キー３０、３２および３３に対するルックアップを実行するためにリクエスト２２２をノード１０８に送信する。同様に、符号２２０において、ノード１０２は、キー３０、３２および３３に対するルックアップを実行するためにリクエスト２２４をノード１１６に送信する。
【００２４】
ネットワーク１００における各ノードは、たとえば適当なプログラミングによって、方法２００を実装するように構成される。結果として、図２について上述した方法は各フィンガーノードで繰り返される。たとえば、ノード１０８は、キー７５、５０、４２、３４、２９、２７および２６をもつノードへのキーの割り当てに関する情報をもつように構成されたフィンガーテーブルをもつ。ノード１０８はこのフィンガーテーブルから、どのノードがファイル３０、３２および３３にもっとも近いかを判定する。この例では、３０および３２の両方に最も近いノードはキー２９であり、これはノード１１０に対応する。ノード１０２が比較的大きな数のキーに対するリクエストをノード１０８に送信していた場合、ノード１０８は、ａ）ノード１０２から受信したリクエストを２以上の部分に分け、図２について上述した手続きを繰り返す。あるいは、リクエストされたキーの数が比較的小さい場合、ノード１０８は、ｂ）どのノードがリクエストにおける残りのキーに責任をもつかを調べる。一例として、ノード１０８はアクションａを常に実行するように構成される。アクションｂは最適化とみなすことができる。アクションｂを実行することを決定する際、多くのファクタを考慮に入れる。ありうるファクタとして、リストに残されたノードの数、ノードへの既存の通信チャネル、または、当該ノードはリストされたノードのいくつかまたは全部に対して高い帯域幅をもつことが知られているか否かがある。たとえば、残りのノードの数が小さい（たとえば４以下）ならば、ノード１０８がそれらに直接メッセージを出す方がより効率的である。あるいは、受信者がノード１０８のフィンガーテーブルにあるなら、ノード１０８はその受信者に直接メッセージを送信する一方で、リストの残りに対してはアクションａを用いることを選択してもよい。さらに、特定のノードに対する帯域幅についての情報を集めて、ある種のキャッシュを用いて、他のノードとの以前の相互作用の記憶を利用することができる。
【００２５】
ここで、帯域幅という用語は、ネットワーク上のデータ伝送レート（たとえば、１秒あたりのビット数または１秒あたりのメッセージパケット数）をいい、ネットワークスループットとネットワークレイテンシによって決定される。ネットワークスループットとは、データ伝送が行われている間のデータ転送レートのことであり、ネットワークレイテンシとは、データ伝送が始まる前に発生する遅延の期間のことである。一般論として、ネットワークスループットが増えると、帯域幅が増える傾向があり、ネットワークレイテンシが増えると、帯域幅が減る傾向がある。
【００２６】
この例では、ノード１０８は、ノード１１０がキー３０、３２および３３に対して責任があると判定し、キー３０、３２および３３に対応するファイルに対するリクエストをノード１１０に送信する。ノード１１０は次に結果（ファイル１３０、１３２および１３４）を直接ノード１０２に送信するか、ノード１０８に返信し、ノード１０８がその結果をノード１０２に中継する。ある実施の形態では、リクエストしているノードのアドレスを自分のクエリと、他のノードが自分の代わりに送信したすべてのクエリの中に埋め込んでもよい。その結果、これらのクエリに対する回答はリクエストを出しているノードに直接返信することができる。
【００２７】
リクエスト２０２の第２部分２１０に対して、ノード１１６は、ノードキー７５、６７、５９、５４、５２および５１をもつノードへのキーの割り当てに関する情報が格納されたフィンガーテーブルをもつ。ノード１１６はこのフィンガーテーブルから、ノードキー５４（ノード１１８に対応）はキー５５にもっとも近いことを判定する。次にノード１１６はキー５５と６６に対するリクエストをもってノード１１８にコンタクトする。一例として、ノード１１８はキー５５に対して責任があるがキー６６には責任がない。ノード１１８は、自分のフィンガーテーブルを調べ、キー６２をもつノード（この例ではノード１２０）がキー６６（ファイル１３８に対応）に対して責任があると判定する。次にノード１１８はファイル１３８をノード１１６、ノード１０８またはノード１０２に返し、キー６６に対するリクエストをノード１２０に転送する。その間、ノード１１６はノード１２４（それにはキー７５が割り当てられている）にキー８９と９３に対するリクエストを送信する。ノード１２４は次にキー８９と９３に対するリクエストをノード１２６に転送する。ノード１２６はファイル１４０および１４２を返す。図１を参照して説明した従来のＣｈｏｒｄサーチとは対照的に、図３に示したＣｈｏｒｄサーチはサーチ負荷をより均一に分散する。特に、図３を見ればわかるように、ノード１０２とノード１０８間、ノード１０２とノード１１６間のトラフィックはかなり少なくなっている。
【００２８】
上述のＣｈｏｒｄサーチをさらに最適化することができる。たとえば、符号２０４において、ノードはリクエストを２以上の部分にわけてもよい。先の例ではリクエストを二つに分けることを説明したが、リクエストを２を超える部分に分けることが有利となる条件も存在する。たとえば、Ｃｈｏｒｄサーチを実装するアプリケーションは、特定の高い帯域幅の接続を生かすやり方で受信者を集めてクラスタにするように構成してもよい。したがって、リクエストを２つのグループに分けることが、本発明の実施の形態の範囲内のただ一つの可能性のある実装というわけではないことを理解すべきである。
【００２９】
さらに、ノードは、自分のフィンガーテーブルのメンバに利用可能なネットワーク帯域幅をモニタするように構成してもよく、その結果、リクエストの部分をもっと利用可能なリソースをもっているノードに優先的に転送できるようにしてもよい。一例として、ノードがフィンガーテーブルに最初に追加されるときに帯域幅を計測することができる。瞬間的な利用可能帯域幅を判定することは一般に難しいが、一般的なリンク能力であればかなり即座に判定することができる。たとえば、２８．８ボーのモデムとＴ１コネクションの違いを判定するのはきわめて容易である。もう一つの重要なネットワーク性能の測定基準はレイテンシであり、これもノードをフィンガーテーブルに追加するときに測定することができる。本発明の実施の形態の目的としては、これらのタイプの決定を実行するにはおおざっぱな知識で十分である。たとえば、宛先ノードがブロードバンドコネクションをもっていることを知っている場合、ノードは異なる行動を取ることを選んでもよい。メッセージの配信により多くの責任をもつことを主張することにより、より少ないリソースをもつノードは、相手に応える形で実行を続けることができる。
【００３０】
上述の変更されたＣｈｏｒｄサーチは、特にリクエストに２より多いアイテムがある場合に、従来のＣｈｏｒｄサーチと比べて有利であることに留意する。リクエストに１個または２個のアイテムがある場合、２つの技術は多かれ少なかれ同じである。しかし、３以上のアイテムがある場合は、この新しい技術は有利である。メッセージを送りたいノードは、従来のＣｈｏｒｄサーチの場合のように３つすべてに送る代わりに、１回の分割を行う上述の技術を用いて２つのノードにコンタクトするだけでよい。
【００３１】
本発明の実施の形態にしたがって、図２および図３に関して上述したＣｈｏｒｄサーチは、一つのピアノードから他の複数のピアノードにデータをブロードキャストすることを実装するように構成される。中間ノードの過負荷を減らすために、ブロードキャストデータ４０４の元の送信者４０２は、図４に示すように、データ４０４に対する受信者のリスト４０６を２以上の部分に分割する。送信者４０２は上述したタイプのピアツーピアネットワークにおけるピアである。リスト４０６は受信者に対応するキー値の順に並べ替えられる。リスト４０６の各部分はデータ４０４といっしょに、当該リストのその部分にある第１キーに対応するピアノードへ送信される。一例として、リスト４０６は第１部分４０８と第２部分４１２に分割される。データ４０４は受信者リスト４０６の第１部分４０８といっしょに、送信者のフィンガーテーブル４１０から選択された第１フィンガーノードＡに送信される。たとえば、リスト４０６を二つの部分に分割するべきであると判定される場合、第１フィンガーノードＡは、リスト４０６上の受信者の大部分を含むアドレス空間に対して責任がある、送信者のフィンガーテーブルのメンバであろう。リスト４０６の第２部分４１２はデータ４０４とともに、たとえば、Ｃｈｏｒｄサーチ方法２００として上述したのと同じような方法を用いて、送信者のフィンガーテーブル４１０から選択された第２フィンガーノードＤに送信される。一例として、第２フィンガーノードＤは、第１フィンガーノードＡよりも先に位置する先行者（ｐｒｅｄｅｃｅｓｓｏｒ）であってもよい。分散ハッシュテーブルのｌｏｇ２Ｎ分散のおかげで、先行者は、多くの受信者の位置も知っていることが期待され、さらなるルーティングをすることなく、メッセージを送信できる可能性が高い。次に受信者ノードＤおよびＡは、直接のピアツーピアコネクションがある任意のノードにメッセージを配信する。この処理はリスト４０６にある残りのエントリに対して繰り返される。具体的には、第１フィンガーノードＡはデータ４０４をノードＢ、Ｃに送信し、第２フィンガーノードＤはデータ４０４をノードＥ、Ｆに転送する。ある実施の形態では、もっと利用可能なリソースをもつノードがファイルをブロードキャストする負荷のより大きな部分を引き受けるように受信者ノードを選択してもよい。
【００３２】
図５および図６は、上述のオーバレイネットワーク上のデータブロードキャスト方法５００の実装例を説明する。図５および図６に示すようにネットワーク１００上のノード１０２は、データファイル５０２と受信者リスト５０４を作り出すか受信する。この例では、受信者リストは、ノード１０４、１０８、１１２、１１６、１２０、１２４および１２６に対応するキー１２、２５、３７、５０、６２、７５および８７を含む。受信者リスト５０４を符号５０６で示すようにキーによって配列することにより、キー順に並べられたリスト５０８が生成される。符号５１０においてこのリストは二つ以上の部分、たとえば第１部分５１２と第２部分５１４に分割される。この例では、第１部分５１２はキー１２、２５および３７を含み、第２部分５１４はキー５０、６２、７５および８７を含む。この例では、各リストの第１キーを用いて第１および第２フィンガーノードを選択する。たとえば、第１部分５１２およびデータ５０２は、符号５１６においてノード１０４（キー１２に対応する）に送信される。同様に第２部分５１４とデータ５０２は符号５１８においてノード１１６（キー５０に対応する）に送信される。
【００３３】
方法５００はノード１０４および１１６で繰り返される。具体的にはノード１０４は第１部分５１２を二つに分けてデータ５０２をノード１０８とノード１１４に転送する。同様にノード１１６はデータ５０２をノード１２０と１２４に転送する。ノードはまたリスト５０４の残りの部分（キー８７）をノード１２４に送信する。そして、ノード１２４はデータ５０２をノード１２６に転送する。この例では、いずれのノードも２を超える他のノードにデータ５０２を送る必要はない。リスト５０８がＫ個の部分（Ｋ＞２）に分けられるより一般的な場合では、いずれのノードもＫを超えるノードにデータを送信する必要はない。
【００３４】
前述のことからわかるように、本発明のある実施の形態では、ブロードキャストメッセージを送信するノードは、たくさんのピアにメッセージを送信することで過度に負荷がかかることはない。従来のＣｈｏｒｄ実装では、これとは対照的に、送信者は個別にメッセージを各受信者に送信する。ここに述べたブロードキャスト技術を用いて、送信者は、意図する受信者の数に関係なく、限定されたＫ個のメッセージだけを送信するだけでよい。リスト５０８がＫ＝２の部分に分けられた場合、送信者はオーバレイネットワークの２つの異なる受信者にメッセージを送信する必要があるだけである。オーバレイネットワーク全体が、受信者全体のリストにメッセージを配信するべく協力する。これにより条件が平等になり、ネットワークリソースをあまり多く持たないノードであっても、オーバレイネットワークに参加する他のピアとより対等に実行することが可能になる。
【００３５】
図７は、この発明の一実施例に従った、オーバレイ・ネットワーク７００を実現するのに好適な１組の情報処理装置を示す。オーバレイ・ネットワーク７００のノードは、ラップトップまたはポータブルコンピュータ７０５と、サーバコンピュータ７１０と、デスクトップコンピュータおよびワークステーション７１５と、携帯電話、携帯情報端末、携帯型デジタルメディアプレーヤ、および携帯型または手持ち式ゲーム機といった携帯コンピューティング装置７２０と、ビデオゲーム機、デジタルメディアプレーヤ、セットトップボックス、メディアセンターコンピュータ、および記憶装置といった家庭用娯楽機器７２５とを含む。オーバレイ・ネットワーク７００は、他のタイプの装置の数とは独立した任意の数の各タイプの装置を含み得る。各装置は、オーバレイ・ネットワーク７００の１つ以上のノードの機能性を実現する。各装置について、１つ以上のノードの機能性は、ハードウェア、ソフトウェア、ファームウェア、またはそれらの任意の組み合わせとして実現可能である。ソフトウェアにおけるノード機能性は、アプリケーション、ライブラリ、アプリケーション・プログラミング・インターフェイス、および／またはオペレーティングシステムの一部であり得る。さらに、オーバレイ・ネットワーク７００の各ノードは、任意のタイプの電気、光学、無線または他の通信手段を取入れた任意のタイプの有線または無線ネットワーク接続を介して、他のノードと接続可能である。オーバレイ・ネットワーク７００は、ローカルエリアネットワークと、インターネットなどの広域ネットワークとの双方を包含し得る。
【００３６】
さらに別の実施例では、オーバレイ・ネットワーク７００のいくつかの装置は、制限された能力を有していてもよい。たとえば、オーバレイ・ネットワーク７００のノードの限られた一部だけが、同報通信メッセージを開始することを許可されてもよい。残りのノードは、同報通信メッセージを転送および／または処理することだけが許可される。さらに別の実施例では、オーバレイ・ネットワーク７００のノードのすべてまたは一部は、同報通信メッセージを認証することができる。この実施例は、不正な同報通信メッセージの拡散を防止する。同報通信メッセージを受信すると、ノードはまず、その同報通信メッセージが真正のものかどうかを、たとえば暗号シグネチャをチェックすることによって判断する。同報通信メッセージが真正のものである場合、それは上述のように処理され、他のノードに潜在的に転送される。その他の場合、その同報通信メッセージは無視される。
【００３７】
図８は、この発明の一実施例に従った、オーバレイ・ネットワーク８００を実現するのに好適な１組の情報処理装置を示す。オーバレイ・ネットワーク８００は、データバス８０１を通して接続されたプロセッサが効率的な態様で同報通信メッセージを送受信できるようにする。データバス８０１は、集積回路内および／または集積回路間でデータを搬送可能な任意の電気、光学または他のタイプのデータ通信手段を使用可能である。
【００３８】
オーバレイ・ネットワーク８００は、プロセッサ８０５、８１０、８１５、および８２０を含む。さらに別の実施例では、オーバレイ・ネットワーク８００は、何千または何百万ものプロセッサを含み得る。各プロセッサは、マイクロプロセッサ、マイクロコントローラ、システム・オン・チップ・プロセッサ、デジタル信号プロセッサ、ＡＳＩＣ、プログラム可能論理装置、および／または任意の他のタイプの情報処理装置であり得る。各プロセッサはさらに、情報処理命令のシーケンスを独立して実行すること、または固定されたアルゴリズムに従って情報を処理することが可能な１つ以上の処理ユニットを含み得る。各プロセッサは、ローカルデータストレージと、共通または共有データストレージへのアクセスとを含み得る。
【００３９】
図９は、本発明の実施の形態に係るオーバレイネットワークのピアノードを実装するのに適した情報処理装置の構成要素を説明するブロック図である。一例として、一般性を損なうことなく、情報処理装置は、本発明の実施の形態を実施するのにふさわしい、パーソナルコンピュータ、ビデオゲーム機、パーソナルデジタル情報機器、または他のデジタルデバイスのようなコンピュータシステム９００として実装される。コンピュータシステム９００は、ソフトウェアアプリケーションとオプションとしてオペレーティングシステムを実行するように構成された中央演算処理装置（ＣＰＵ）９０５を含む。ＣＰＵ９０５は、１以上のプロセッサコアを含んでもよい。一例として限定するわけではないが、ＣＰＵ９０５は、セルプロセッサのような並列プロセッサモジュールであってもよい。セルプロセッサアーキテクチャの例は、「セルブロードバンドエンジンアーキテクチャ」に詳細が記述されている。これは、ＩＢＭ、ソニー・コンピュータエンタテインメント、東芝の２００５年８月８日付けの著作権で保護されており、コピーはｈｔｔｐ：／／ｃｅｌｌ．ｓｃｅｉ．ｃｏ．ｊｐ／からダウンロード可能であり、その内容全体を参照によってここに組み入れる。
【００４０】
メモリ９０６はＣＰＵ９０５に接続されており、メモリ９０６はＣＰＵ９０５によって使用されるアプリケーションとデータを格納する。メモリ９０６は、ＲＡＭ、ＤＲＡＭ、ＲＯＭ等の集積回路の形態であってもよい。コンピュータプログラム９０３はプロセッサ９０５上で実行可能な命令の形態でメモリ９０６に格納される。プログラム９０３の命令は、たとえば、図２に関して上述したようなＣｈｏｒｄサーチ方法や、図５に関して上述したようなブロードキャスト方法を実装するように構成される。コンピュータシステム９００はまた、入出力（Ｉ／Ｏ）装置９１１、電源（Ｐ／Ｓ）９１２、クロック（ＣＬＫ）９１３およびキャッシュ９１４などの公知のサポート機能９１０を備えてもよい。システム９００はさらに、アプリケーションおよびデータ用の不揮発性のストレージを提供するストレージデバイス９１５を備えてもよい。一例としてストレージデバイス９１５は、固定ディスクドライブ、リムーバブルディスクドライブ、フラッシュメモリデバイス、テープドライブ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ブルーレイ（商標または登録商標）、ＨＤ−ＤＶＤ、ＵＭＤ、その他の光学式ストレージデバイスであってもよい。
【００４１】
メモリ９０６にはまたフィンガーテーブル９０７が含まれる。フィンガーテーブルには、ノード９００が責任をもつキーに関する情報が含まれる。これらのキーは、たとえば、ストレージ９１５に格納される共有ファイルのようなデータに関連づけられたデータキーを含む。さらに、フィンガーテーブル９０７には、他のピアノードに関連づけられたノードキーが含まれてもよい。そのようなノードには、ピアノード９００がピアツーピアコネクションを介して直接コンタクトすることができるネットワーク１００のノードの部分集合が含まれてもよい。データキーはキーグループへ配列され、各キーグループは異なるノードキーに関連づけられる。
【００４２】
１以上のユーザからのユーザ入力をコンピュータシステム９００に伝えるために１以上のユーザ入力デバイス９２０が用いられてもよい。たとえば、１以上のユーザ入力デバイス９２０が、入出力装置９１１を介してシステム９００に接続されてもよい。適当な入力デバイス９２０の例には、キーボード、マウス、ジョイスティック、タッチパッド、タッチスクリーン、ライトペン、スチル／ビデオカメラ、および／またはマイクロホンが含まれる。ネットワークインタフェース３２５は、コンピュータシステム９００が電子通信ネットワーク９２７を介した他のコンピュータシステムと通信することを可能にする。ネットワークインタフェース９２５は、ローカルエリアネットワークおよびインターネットのようなワイドエリアネットワーク上の有線または無線通信を含んでもよい。システム９００はネットワーク９２７上で１以上のメッセージパケット９２６を用いて、データおよび／またはファイルに対するリクエストを送受信することができる。
【００４３】
コンピュータシステム９００は、グラフィックプロセッシングユニット（ＧＰＵ）９３５とグラフィックスメモリ９４０とを有するグラフィックス・サブシステム９３０を更に含む。グラフィックスメモリ９４０は、出力イメージの各画素に対する画素データを格納するために使われるディスプレイメモリ（例えばフレーム・バッファ）を含む。グラフィックスメモリ９４０は、ＧＰＵ９３５と同じデバイス内に統合されてもよく、別のデバイスとしてＧＰＵ９３５に結合されてもよく、メモリ９０６内に実装されてもよい。画素データは、ＣＰＵ９０５から直接グラフィックスメモリ９４０に提供される。あるいは、ＣＰＵ９０５は、所望の出力イメージを定めるデータやインストラクションをＧＰＵ９３５に提供する。ＧＰＵ９３５はそれを用いて出力イメージの画素データを生成する。所望出力イメージを定めるデータやインストラクションは、メモリ９１０やグラフィックスメモリ９４０に格納される。ある実施の形態では、ＧＰＵ９３５は、例えば、適当なプログラミングまたはハードウェア・コンフィギュレーションによって構成され、シーンのためにジオメトリ、ライティング（照明）、シェーディング、テクスチャリング、モーション、および／またはカメラパラメータを定めるインストラクションとデータから出力イメージに対する画素データを生成するための３Ｄレンダリング機能をもつ。ＧＰＵ９３５は、シェーダプログラムを実行することができるプログラム可能な実行ユニットを更に含む。
【００４４】
グラフィックス・サブシステム９３０は、表示装置９５０で表示されるべきグラフィックスメモリ９４０からのイメージに対する画素データを周期的に出力する。表示装置９５０は、コンピュータシステム９００からの信号に応じてビジュアル情報を表示することができる任意のデバイスであり、ＣＲＴ、ＬＣＤ、プラズマ、およびＯＬＥＤディスプレイを含む。コンピュータシステム９００は、表示装置９５０にアナログまたはデジタル信号を提供する。一例として、表示装置９５０は、テキスト、数字、グラフィカルシンボル、または画像を表示するＣＲＴまたはフラットパネルスクリーンを含む。さらに、ディスプレイ９５０は、可聴もしくは検知可能な音を出すオーディオスピーカーを含んでもよい。そのような音の生成を容易にするために、システム９００は、ＣＰＵ９０５、メモリ９０６、および／またはストレージ９１５によって提供されたインストラクションおよび／またはデータからアナログまたはデジタル音声出力を生成するために適したオーディオプロセッサ９５５を更に含む。
【００４５】
ＣＰＵ９０５、メモリ９０６、支援機能９１０、データストレージデバイス９１５、ユーザ入力デバイス９２０、ネットワークインターフェース９２５、およびオーディオプロセッサ９５５を含むコンピュータシステム９００の構成要素は、データバス９６０を介して互いに機能的に接続されている。これらの構成要素は、ハードウェア、ソフトウェアまたはファームウェア、あるいはこれらのうちの２つ以上の組合せで実装される。
【００４６】
本発明の好ましい実施の形態を完全な形で説明してきたが、いろいろな代替物、変形、等価物を用いることができる。したがって、本発明の範囲は、上記の説明を参照して決められるものではなく、請求項により決められるべきであり、均等物の全範囲も含まれる。ここで述べた特徴はいずれも、好ましいかどうかを問わず、他の特徴と組み合わせてもよい。請求項において、明示的に断らない限り、各項目は１またはそれ以上の数量である。請求項において「〜のための手段」のような語句を用いて明示的に記載する場合を除いて、請求項がミーンズ・プラス・ファンクションの限定を含むものと解してはならない。
【図１】
2010531020.tif 000004
【図２】
2010531020.tif 000005
【図３】
2010531020.tif 000006
【図４】
2010531020.tif 000007
【図５】
2010531020.tif 000008
【図６】
2010531020.tif 000009
【図７】
2010531020.tif 000010
【図８】
2010531020.tif 000011
【図９】
2010531020.tif 000012
【国際調査報告】
2010531020.tif 000013