(57)【特許請求の範囲】
【請求項１】
データのライブストリーミングを行う方法であって、
下位レベルのクラスタ内のピアが、複数の上位レベルのクラスタ内の複数のクラスタヘッドのピアからデータを受信するステップであって、前記下位レベルのクラスタは、メンバとして複数のクラスタヘッドのピアを有し、前記下位レベルのクラスタ内の前記クラスタヘッドのピアの各々は、前記下位レベルのクラスタと、前記複数の上位レベルのクラスタのうちのひとつとの双方のメンバであり、前記下位レベルのクラスタ内の前記ピアは完全接続され、前記上位レベルのクラスタ内の前記クラスタヘッドのピアは完全接続される、ステップと、
前記下位レベルのクラスタ内の前記ピアが、前記データを、前記下位レベルのクラスタ内の他のピアに転送するステップと、
を備える、前記方法。
【請求項２】
前記下位レベルのクラスタ内の前記ピアが、前記データを再生バッファに格納するステップと、
前記下位レベルのクラスタ内の前記ピアが、前記格納されたデータをレンダリングするステップと、
をさらに備える、請求項１に記載の方法。
【請求項３】
前記下位レベルのクラスタ内の前記ピアは、同じクラスタのメンバである、請求項１に記載の方法。
【請求項４】
データのライブストリーミングを行う装置であって、
下位レベルのクラスタのピアにより、複数の上位レベルのクラスタ内の複数のクラスタヘッドのピアからデータを受信する手段であって、前記下位レベルのクラスタは、メンバとして複数のクラスタヘッドのピアを有し、前記下位レベルのクラスタ内の前記クラスタヘッドのピアの各々は、前記下位レベルのクラスタと、前記複数の上位レベルのクラスタのうちのひとつとの双方のメンバであり、前記下位レベルのクラスタ内の前記ピアは完全接続され、前記上位レベルのクラスタ内の前記クラスタヘッドのピアは完全接続される、手段と、
前記下位レベルのクラスタ内の前記ピアにより、前記データを、前記下位レベルのクラスタ内の他のピアに転送する手段と、
を備える、前記装置。
【請求項５】
前記下位レベルのクラスタ内の前記ピアにより、前記データを再生バッファに格納する手段と、
前記下位レベルのクラスタ内の前記ピアにより、前記再生バッファからの前記格納されたデータをレンダリングする周辺機器と、
をさらに備える、請求項４に記載の装置。
【請求項６】
前記下位レベルのクラスタ内の前記ピアは、同じクラスタのメンバである、請求項４に記載の装置。
【請求項７】
クラスタ内の複数のクラスタヘッドのピアによってデータのライブストリーミングを行う方法であって、
前記クラスタ内のクラスタヘッドのピアが、サーバからのデータのサブストリームを受信するステップと、
前記クラスタヘッドのピアが、前記クラスタ内の他のクラスタヘッドのピアからの複数のデータのサブストリームを受信するステップであって、前記複数のデータのサブストリームは、前記サーバから受信された前記データのサブストリームとは異なる、ステップと、
下位レベルのクラスタのメンバである前記クラスタヘッドのピアが、前記下位レベルのクラスタのメンバである他のピアへ、前記クラスタヘッドのピアにより受信された前記データのサブストリームまたは前記データの一部を送信する速度を計算するステップであって、前記下位レベルのクラスタは複数のクラスタヘッドのピアを有し、前記下位レベルのクラスタ内の前記クラスタヘッドのピアの各々は、前記下位レベルのクラスタと、前記複数の上位レベルのクラスタのうちのひとつとの双方のメンバであり、前記下位レベルのクラスタ内の前記ピアは完全接続され、前記上位レベルのクラスタ内の前記クラスタヘッドのピアは完全接続される、ステップと、
前記クラスタヘッドのピアが、前記データのサブストリームを複数のデータの小ユニットに分割するステップと、
前記クラスタヘッドのピアが、前記複数のデータの小ユニットを対応する前記クラスタヘッドの送信キューに押し込むステップと、
を備える、前記方法。
【請求項８】
クラスタ内の複数のクラスタヘッドのピアによってデータのライブストリーミングを行う装置であって、
前記クラスタ内のクラスタヘッドのピアにより、サーバからデータのサブストリームを受信する手段と、
前記クラスタヘッドのピアにより、前記クラスタ内の他のクラスタヘッドのピアから複数のデータのサブストリームを受信する手段であって、前記複数のデータのサブストリームは、前記サーバから受信した前記データのサブストリームとは異なる、手段と、
前記下位レベルのクラスタのメンバである前記クラスタヘッドのピアにより、前記クラスタヘッドのピアにより受信された前記データのサブストリームを、前記下位レベルのクラスタのメンバである他のピアに送信するサブストリーム速度を計算する手段であって、前記下位レベルのクラスタは、複数のクラスタヘッドのピアを有し、前記下位レベルのクラスタ内の前記クラスタヘッドのピアの各々は、前記下位レベルのクラスタと、前記複数の上位レベルのクラスタのうちのひとつとの双方のメンバであり、前記下位レベルのクラスタ内の前記ピアは完全接続され、前記上位レベルのクラスタヘッドは完全接続される、手段と、
前記クラスタヘッドのピアにより、データの前記サブストリームを複数のデータの小ユニットに分割する手段と、
前記クラスタヘッドのピアにより、前記複数のデータの小ユニットを対応する前記クラスタヘッドの送信キューに押し込む手段と、
を備える、前記装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ピアが階層的にクラスタ化されて、さらに各クラスタが複数のクラスタヘッドを有する、ピアツーピア（Ｐ２Ｐ）ライブストリーミングシステムに関する。
【背景技術】
【０００２】
先行技術研究では、システムが許容する最大ストリーミング速度を達成する「完全な」スケジューリングアルゴリズムについて説明した。システム内にｎ個のピアが存在すると仮定する。ｒmaxは、システムが許容する最大ストリーミング速度を示すものとして、次のようになる。
【０００３】
【数１】
0005497752.tif 000002
【０００４】
ここで、ｕsは、サーバのアップロード帯域幅を示し、ｕiは、合計ｎ個のノードの中からｉ番目のノードの帯域幅を示す。つまり、最大ビデオストリーミング速度は、ビデオソースサーバの容量、システム内のピア数、およびすべてのピアの総アップロード容量によって決まる。各ピアは、ビデオソースサーバから直接得たビデオ／コンテンツをシステム内の他のすべてのピアにアップロードする。すべてのピアに対してアップロード容量の完全な使用を保証するために、異なるピアは、サーバから異なるコンテンツをダウンロードし、ピアがサーバからコンテンツをダウンロードする速度は、ピアのアップロード容量に比例する。
【０００５】
図１は、先行技術の「完全な」スケジューリングアルゴリズムを使用して、３つの異種ノード間でデータの異なる部分がスケジュールされる例示的な方法を示す。システム内には３つのピアが存在する。サーバの容量は６である。ａ1、ａ2およびａ3のアップロード容量は、それぞれ２，４および６である。すべてのピアが十分なダウンロード容量を有すると仮定して、システム内でサポートすることができる最大ビデオ速度は６である。この速度を達成するために、サーバは、ビデオチャンクを６つのグループに分割する。ａ1は各グループから１チャンクをアップロードする責任を負い、ａ2およびａ3は各グループからそれぞれ２および３チャンクをアップロードする責任を負う。このようにして、すべてのピアは、最大速度６でビデオをダウンロードすることができる。このような「完全な」スケジューリングアルゴリズムを実装するために、各ピアは、システム内の他のすべてのピアとの接続を維持して、それらとビデオコンテンツを交換する必要がある。さらに、サーバは、ビデオストリームをピアごとに速度が異なる複数のサブストリームに分割する必要がある。現実のＰ２Ｐライブストリーミングシステムでは、数千ものピアに容易になり得る。現在のオペレーティングシステムでは、標準／普通のピアが数千の同時接続を維持するのは非現実的である。また、サーバが実時間でビデオストリームを数千のサブストリームに分割することも困難である。ここで使用する「／」は、同じまたは同様のコンポーネントまたは動作を示す。つまり、「／」は、同じまたは同様のコンポーネントまたは動作に対する代替語を示すものと見なすことができる。
【０００６】
単一の大きいメッシュを形成する代わりに、階層的にクラスタ化されたＰ２Ｐストリーミングスキーム（ＨＣＰＳ）は、ピアをクラスタにグループ化する。クラスタ内のピア数は比較的少ないので、完全なスケジューリングをクラスタレベルにおいて首尾よく適用することができる。クラスタ内のあるピアは、クラスタヘッドとして選択され、そのクラスタのソースとして機能する。クラスタヘッドは、システム階層内の上位レベルのクラスタに入ることによってストリーミングコンテンツを受信する。
【０００７】
図２は、ＨＣＰＳシステムの単純な例を示す。図２において、ピアは２つのレベルの階層で組織される。ベース／最下位レベルにおいて、ピアは小さいサイズのクラスタにグループ化される。それらのピアは、クラスタ内で完全接続される。つまり、それらのピアは、メッシュを形成する。最大アップロード容量を有するピアが、クラスタヘッドとして選択される。最上レベルにおいて、すべてのクラスタヘッドおよびビデオサーバは、２つのクラスタを形成する。ビデオサーバ（ソース）は、最上レベルにおいて「完全な」スケジューリングアルゴリズムを使用してコンテンツをすべてのクラスタヘッドに分散する。ベース／最下位レベルにおいて、各クラスタヘッドは、そのクラスタ内のビデオサーバとして機能し、再度「完全な」スケジューリングアルゴリズムを使用して、ダウンロードされたビデオを同じクラスタ内の他のピアに分散する。各普通のピアの接続数は、そのピアのクラスタのサイズによって制限される。クラスタヘッドは、上位レベルのクラスタ内で接続を付加的に維持する。
【０００８】
以前の出願では、出願人は、ＨＣＰＳの最大ストリーミング速度を最適化問題として定式化していた。次の３つの基準は、クラスタ間でリソースを動的に調整するのに当時使用されていたものである。
１ピア当たりの個々のクラスタの平均アップロード容量の不一致を最小限にしなければならない。
各クラスタヘッドのアップロード容量をできるだけ大きくしなければならない。ボトルネックになるのを防ぐために、ベースレイヤ容量に割り付けられたクラスタヘッドの容量を平均アップロード容量よりも大きくしなければならない。さらに、クラスタヘッドも上位レイヤのクラスタに入れる。理想的には、クラスタヘッドの速度≧２ｒHCPSでなければならない。
クラスタ内のピア数は、上記から比較的少数に制限されなければならない。クラスタ内のピア数でピアの出次数(outdegree)が決まり、大きいサイズのクラスタは、完全なスケジューリングを使用してクラスタが適切に行われるのを邪魔する。
【０００９】
理論的上限に近いＨＣＰＳのストリーミング速度を達成するために、クラスタヘッドのアップロード容量を十分大きくしなければならない。これは、クラスタヘッドが２つのクラスタ、すなわち（１）ヘッドとしてふるまう下位レベルのクラスタと、（２）普通のピアとしてふるまう上位レベルのクラスタと、に参入しているという事実による。例えば、図２において、ピアａ１は、クラスタ３のクラスタヘッドである。ピアａ１はまた、普通のピアとしてふるまう上位レベルのクラスタ１のメンバーでもある。
【００１０】
ｒHCPSは、ＨＣＰＳシステムのストリーミング速度を示す。クラスタヘッドとしては、そのアップロード容量を少なくともｒHCPSにしなくてはならない。さもなければ、（ノードがクラスタヘッドである）下位レベルのクラスタのストリーミング速度は、ｒHCPSよりも遅くなり、そのクラスタがボトルネックになる。それによってシステム全体のストリーミング速度を弱める。クラスタヘッドはまた、上位レベルのクラスタ内の普通のピアでもある。クラスタヘッドがさらに、上位レベルにおいてあるアップロード容量を提供(contribute)して、上位レベルのクラスタ内にｒHCPSをサポートするのに十分なアップロード容量リソースになることが望ましい。
【００１１】
ＨＣＰＳは、従って、完全なスケジューリングが直面するスケーラビリティ問題に対処する。ＨＣＰＳは、ピアをクラスタに分割して、「完全な」スケジューリングアルゴリズムを個々のクラスタ内で適用する。そのシステムは、典型的には、２つのレベルを有する。ボトム／最下位レベルにおいて、各クラスタは、上位レベルからコンテンツをフェッチする１つのクラスタヘッドを有し、コンテンツをクラスタ内のノードに分散するソースとして機能する。クラスタヘッドはその後、上位レベルにおいてクラスタを形成して、ストリーミングソースからコンテンツをフェッチする。「完全な」スケジューリングアルゴリズムは、すべてのクラスタ内で使用される。このようにして、そのシステムは、理論的上限に近いストリーミング速度を達成することができる。
【００１２】
実際には、ピアの激動（churn）のために、クラスタは、動的にリバランスされる(re-balanced)。従って、クラスタ内でクラスタヘッドにするのに十分大きいアップロード容量を有するピアを１つも識別することができない状況に遭遇し得る。複数のクラスタヘッドを使用することによって、クラスタヘッドのアップロード容量についての要件が弱まり、システムがさらに理論的上限に近いストリーミング速度を達成することができる。Ｐ２Ｐライブストリーミングにとって、ベース／最下位レベルのクラスタが複数のクラスタヘッドを有するシステムを有することは有利である。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】国際公開第２００８／１１５２２１号パンフレット
【特許文献２】米国仮出願第６０／９１９０３５号明細書
【発明の概要】
【００１４】
本発明は、ピアが階層的にクラスタ化されて、さらに各クラスタが複数のヘッドを有するＰ２Ｐライブストリーミングの方法およびシステムを対象としている。本発明のＰ２Ｐライブストリーミングの方法およびシステムにおいて、ソースサーバは、コンテンツ／データを階層的にクラスタ化されたピアに供給する。コンテンツは、オーディオ、ビデオ、マルチメディア等を含むデータの任意の形式を含む。ビデオという用語は、ここではコンテンツと同じ意味で使用されるが、それに限定されることを意図しない。さらにここで使用されるように、ピアという用語は、ノードと同じ意味で使用され、コンピュータ、ラップトップ、パーソナルデジタルアシスタント（ＰＤＡ）、モバイル端末、モバイルデバイス、デュアルモードスマートフォン、セットトップボックス（ＳＴＢ）等を含む。
【００１５】
複数のクラスタヘッドを有することによってクラスタヘッドの選択が容易になり、クラスタヘッドのアップロード容量が比較的小さい場合でもＨＣＰＳシステムが高度にサポートできるストリーミング速度を達成できるようにする。複数のクラスタヘッドの使用はまた、システムのロバスト性も改善する。
【００１６】
複数のクラスタヘッドからデータを受信して、そのデータをピアに転送することを含む方法および装置について説明する。また、サブストリーム速度を計算し、データを複数のデータサブストリームに分割し、複数のデータサブストリームを対応する送信キューに押し込むことを含む方法および装置についても説明する。さらに、ソースデータを複数の同じ速度のデータサブストリームに分割し、同じ速度のデータサブストリームをサブサーバのコンテンツバッファに格納し、バッファされたデータを複数のデータサブストリームに分割し、複数のサブストリーム速度を計算し、データサブストリームを対応する送信キューに押し込むことを含む方法および装置についても説明する。
【図面の簡単な説明】
【００１７】
本発明は、次の詳細な説明が添付図面とともに読まれる場合に最もよく理解される。図面は、以下に簡潔に説明された次の図を含む。
【図１】先行技術の「完全な」スケジューリングアルゴリズムを使用して、３つの異種ノード間でデータの異なる部分がスケジュールされる例示的な方法の図である。
【図２】先行技術によるＨＣＰＳシステムの単純な例を示す図である。
【図３】１クラスタ当たり２つのヘッドを有する本発明の例示的なｅＨＣＰＳシステムの図である。
【図４】ｅＨＣＰＳシステムのピアのアーキテクチャを示す図である。
【図５】ピアのデータハンドリング処理のフローチャートである。
【図６】クラスタヘッドのアーキテクチャを示す図である。
【図７】クラスタヘッドの下位レベルのデータハンドリング処理のフローチャートである。
【図８】コンテンツ／ソースサーバのアーキテクチャを示す図である。
【図９】サブサーバのデータハンドリング処理を示すフローチャートである。
【発明を実施するための形態】
【００１８】
本発明は、１クラスタ当たり複数のヘッドを有する拡張ＨＣＰＳであり、ｅＨＣＰＳと呼ばれる。元のコンテンツストリームはいくつかのサブストリームに分割される。各クラスタヘッドは１つのサブストリームを処理する。ｅＨＣＰＳが１クラスタ当たりＫ個のヘッドをサポートすると仮定すると、サーバはコンテンツをＫ個のサブストリームに分割する必要がある。図３は、１クラスタ当たり２つのヘッドを有する例示的なｅＨＣＰＳを示す。この例において、ｅＨＣＰＳは、同じストリーミング速度でコンテンツを２つのサブストリームに分割する。１つのクラスタの２つのヘッドは、異なる上位レベルのクラスタに入って、データ／コンテンツの１つのサブストリームをフェッチした後、クラスタヘッドが受信したコンテンツを、ボトム／ベース／最下位レベルのクラスタ内の標準／普通のノードに分散する。ｅＨＣＰＳは１ノード当たりの接続数を増やさない。
【００１９】
図３に示すように、ソースストリームがＫ個のサブストリームに分割されると仮定する。これらのＫ個のサブストリームは、Ｋ個の最上レベルのクラスタを通じてクラスタヘッドに配信される。さらにＣ個のボトムレベルのクラスタおよびＮ個のピアが存在すると仮定する。クラスタｃはｎc個のピアを有し、ｃ＝１，２，．．Ｃである。ピアｉのアップロード容量をｕiで示す。ピアは、上位レイヤクラスタ内の普通のピアかクラスタヘッドのどちらかとして、およびベースレイヤクラスタ内の普通のピアとしてＨＣＰＳメッシュに参入することができる。次の１クラスタ当たりＫ個のクラスタヘッドを有するｅＨＣＰＳシステムが最適化問題として定式化され、ｒを最大化することを目的とする。ストリーミング速度は、再生速度に等しい。以下の表１は、主要な符号の一部を記載している。
【００２０】
【表１】
0005497752.tif 000003
【００２１】
最適化問題を次のように定式化することができる。
最大化  ｒ                            （２）
制約条件式：
【００２２】
【数２】
0005497752.tif 000004
【００２３】
【数３】
0005497752.tif 000005
【００２４】
【数４】
0005497752.tif 000006
【００２５】
【数５】
0005497752.tif 000007
【００２６】
【数６】
0005497752.tif 000008
【００２７】
【数７】
0005497752.tif 000009
【００２８】
【数８】
0005497752.tif 000010
【００２９】
ソースサーバは、ソースデータをＫ個のサブストリームに等しく分割し、各サブストリームの速度をｒ／Ｋにする。式（３）の右側は、ボトムレベルのクラスタｃのｊ番目のサブストリーム内のすべてのノードの平均アップロード帯域幅を表す。ｊ番目のサブストリームのクラスタヘッドをソースとして機能させる一方で、他のサブストリームのクラスタヘッドは、それら自身でビデオ全体を再生するためにｊ番目のサブストリームをフェッチする必要がある。式（３）は、クラスタの平均アップロード帯域幅が、すべてのクラスタ内のすべてのサブストリームのサブストリーム速度よりも大きくなければならないことを示す。具体的には、（不等式の右辺の）分子の第１項は、ｊ番目のサブストリームを分散するクラスタ内のすべてのピアのアップロード容量である。（不等式の右辺の）分子の第２項は、ｊ番目のサブストリームを分散する際に消費されるクラスタヘッドのアップロード容量である。（不等式の右辺の）分子の２項の合計は、（クラスタヘッドを含まない）クラスタｎc内のノード数とクラスタヘッド数Ｋから１を差し引いたものとを足したもので割られる。式（８）は、どのサブストリームヘッドのアップロード帯域幅も、サブストリーム速度よりも大きくなければならないことを示す。同様に、最上レベルのクラスタの場合、サーバは、各サブストリームにクラスタを１つずつにして、Ｋ個のクラスタをサポートするように要求される。ｊ番目の最上レベルのクラスタ内で消費されるソースサーバのアップロード容量と個々のクラスタの平均アップロード帯域幅の両方は、サブストリーム速度よりも大きくする必要がある。具体的には、式（４）に関して、（不等式の右辺の）分子は、ｊ番目の最上レベルのクラスタ内で消費されるソースサーバのアップロード容量の合計とｊ番目の最上レベルのクラスタ内で消費されるＫ個のクラスタヘッドのアップロード容量の合計である。これらの合計は、個々のクラスタの平均アップロード容量に達するクラスタヘッド数で割られる。式（９）に関して、ｊ番目の最上レベルのクラスタ内で消費されるソースサーバのアップロード容量は、サブストリーム速度よりも大きくする必要がある。これは、式（４）および（９）で説明している。最後に、式（５）（６）および（７）が表すように、ソースサーバを含むすべてのノードは、ノード自身の容量よりも大きい帯域幅を消費することができない。具体的には、式（５）は、クラスタｃのｋ番目のヘッドのアップロード容量が、最上レベルのクラスタと第２レベルのクラスタの両方で消費される帯域幅の総量よりも大きいまたはそれに等しくなければならないことを示す。第２レベルのクラスタにおいて、クラスタｃのｋ番目のヘッドは、すべてのサブストリームの分散に参入する。式（６）は、ソースサーバのアップロード容量が、ソースサーバが最上レベルのクラスタ内で消費する総アップロード容量よりも大きいまたはそれに等しいことを示す。式（７）は、クラスタｃ内のノードｖのアップロード容量が、すべてのサブストリームに消費されるノードｖの総アップロード帯域幅よりも大きいまたはそれに等しいことを示す。１つのクラスタに複数のヘッドを使用することは、単一のクラスタヘッドを使用する��りも容易に最適なストリーミング速度を達成することができる。ｅＨＣＰＳは、クラスタヘッドの帯域幅の要件を緩和する。
【００３０】
Ｎ個のノードを有するクラスタｃが存在すると仮定する。ノードｐは、ヘッドである。ノードｑは、ＨＣＰＳ内の普通のピアであり、複数のヘッドがあるＨＣＰＳ（ｅＨＣＰＳ）内の別のヘッドになる。ＨＣＰＳ手法では、サポートできる速度は、次のようになる。
【００３１】
【数９】
0005497752.tif 000011
【００３２】
ここで、ｕkは、標準ノードｋのアップロード容量を示し、ｕpは、ヘッドｐのアップロード容量を示し、
【００３３】
【数１０】
0005497752.tif 000012
【００３４】
は、ｕp−δに等しく、ヘッドｐが上位レベル上で消費するアップロード帯域幅の量である。式（１０）の第２項は、クラスタが、帯域幅の量δを上位レベルのクラスタに提供するヘッドを用いて達成することができる最大速度である。ｒpを、式（１０）の右辺の第２項を示すのに使用する。
【００３５】
【数１１】
0005497752.tif 000013
【００３６】
最適なストリーミング速度を達成するために、クラスタヘッドをボトルネックにしてはならない。即ち次のようにする。
【００３７】
【数１２】
0005497752.tif 000014
【００３８】
次に、ｅＨＣＰＳ手法が、クラスタヘッドのアップロード容量の要件を弱めることを示す。同じクラスタを、今から１クラスタ当たり２つのヘッド（ｐおよびｑ）を有するｅＨＣＰＳに切り替えると仮定する。上位レベル内で消費される帯域幅δの量は同じである。完全なスケジューリングアルゴリズムを使用して、各クラスタヘッドは、１つのサブストリームをクラスタ内に分散する（ｐはサブストリーム１を処理し、ｑはサブストリーム２を処理する）。
【００３９】
【数１３】
0005497752.tif 000015
【００４０】
は、ヘッドｐがホストする第１サブストリーム内で消費されるノードｋのアップロード容量を示し、
【００４１】
【数１４】
0005497752.tif 000016
【００４２】
は、ヘッドｑがホストする第２サブストリームをノードｋが使用するアップロード容量を示すと仮定する。従って、サポートできるサブストリーム速度は次のようになる。
【００４３】
【数１５】
0005497752.tif 000017
【００４４】
【数１６】
0005497752.tif 000018
【００４５】
ここで、
【００４６】
【数１７】
0005497752.tif 000019
【００４７】
は、サブストーム１のクラスタヘッドｐのアップロード容量であり、
【００４８】
【数１８】
0005497752.tif 000020
【００４９】
は、サブストリーム２のクラスタヘッドｐのアップロード容量である。同様に、
【００５０】
【数１９】
0005497752.tif 000021
【００５１】
は、サブストーム１のクラスタヘッドｑのアップロード容量であり、
【００５２】
【数２０】
0005497752.tif 000022
【００５３】
は、サブストリーム２のクラスタヘッドｑのアップロード容量である。その容量が均等に分割された場合、標準／普通のノードに対して、
【００５４】
【数２１】
0005497752.tif 000023
【００５５】
となり、２つのクラスタヘッドに対して、
【００５６】
【数２２】
0005497752.tif 000024
【００５７】
となる。クラスタヘッドは、上位レベル上で帯域幅δを共有する。式（１８）および（２１）の各々は、２つのサブストリームに対して個々に追加の帯域幅δ／２を上位レベル上で消費する必要がある。上記の帯域幅分割を適用すると、式（１６）および（１７）の第２項が同じであり、それらはｒp／２に等しいことを示すことができる。クラスタヘッドのアップロード容量がボトルネックでない限り、ｒ1＋ｒ2＝ｒpとなる。サブストリーム１の場合、ボトルネックにならないクラスタヘッドｐの条件は次のようになる。
【００５８】
【数２３】
0005497752.tif 000025
【００５９】
同様に、ボトルネックにならないクラスタヘッドｑの条件は次のようになる。
【００６０】
【数２４】
0005497752.tif 000026
【００６１】
式（２４）（２５）を式（１３）と比較すると、クラスタヘッドのアップロード容量の要件が緩和されたことを示すことができる。
【００６２】
ｅＨＰＣＳが３つのクラスタヘッドｐ、ｑ、およびｔで３つのサブストリームをサポートする場合、分割方法を次のようにすることができる。標準ノードに対して、
【００６３】
【数２５】
0005497752.tif 000027
【００６４】
となり、クラスタヘッドに対して、
【００６５】
【数２６】
0005497752.tif 000028
【００６６】
となる。クラスタヘッドがボトルネックにならないようにするために、クラスタヘッドの帯域幅は次を満たさなければならない。
【００６７】
【数２７】
0005497752.tif 000029
【００６８】
同様に、クラスタヘッドｑおよびｔに対して、ｕq≧δ／３＋ｒp／３およびｕt≧δ／３＋ｒp／３となる。
【００６９】
Ｋ個のクラスタヘッドを有するｅＨＣＰＳに同様の分割方法を用いると、各クラスタヘッドの要件が次のようになると推定することができる。
【００７０】
【数２８】
0005497752.tif 000030
【００７１】
ＨＣＰＳにおいて、クラスタヘッドの離脱(departure)またはクラッシュがコンテンツ配信を中断した。クラスタ内のピアは、離脱したクラスタヘッドによってデータの受信が妨げられるので、コンテンツを他のピアに供給することができない。従ってピアは、再生中にあるデータを逃し、表示品質が低下する。
【００７２】
各ヘッドが１つずつサブストリームに供給する責任を負う複数のヘッドでは、ｅＨＣＰＳによって、クラスタヘッドの離脱／クラッシュの影響を緩和することができる。１つのヘッドがクラッシュしても他のヘッドに影響がないので、他のサブストリームの分散に影響を与えない。ピアは、残りのクラスタヘッドから部分的にストリームを受信し続ける。レイヤ符号化または多重記述符号化（ＭＤＣ：multiple description coding）等の最新の符号化技術を使用することによって、ピアは、離脱したクラスタヘッドが置き換えられるまで、受信したデータを用いて再生し続けることができる。ＨＣＰＳと比較すると、クラスタヘッドがそのように離脱するときに、ｅＨＣＰＳがより多くの記述を転送することができるので、よりロバストである。
【００７３】
ｅＨＣＰＳは、ソースビデオストリーミングを複数の同じ速度のサブストリームに分割する。「完全な」スケジューリング機構を使用して、各ソースサブストリームは最上レベルのクラスタ内のクラスタヘッドに配信される。「完全な」スケジューリング機構は、本発明の発明者による２００７年１２月１４日出願の「ＨＩＥＲＡＲＣＨＩＣＡＬＬＹ  ＣＬＵＳＴＥＲＥＤ  Ｐ２Ｐ  ＳＴＲＥＡＭＩＮＧ  ＳＹＳＴＥＭ」と題する国際特許出願ＰＣＴ／ＵＳ０７／０２５６５６（特許文献１）に記載され、国際特許出願ＰＣＴ／ＵＳ０７／０２５６５６は、２００７年３月２０日出願の米国仮出願第６０／９１９０３５号（特許文献２）に基づいて優先権を主張している。これらのクラスタヘッドは、下位レベルのクラスタ内のソースとして機能する。図３は、ｅＨＣＰＳシステムのレイアウトを示す。
【００７４】
図４は、ｅＨＣＰＳ内のピアのアーキテクチャを示す。ピアは、着信キュー(incoming queue)経由で、同じクラスタ内の他のピアだけでなく、複数のクラスタヘッドからもデータコンテンツを受信する。データハンドラ(data handler)は、着信キュー経由でクラスタ内のクラスタヘッドおよび他のピアからコンテンツを受信する。データハンドラによって受信されたデータは、再生バッファに格納される。クラスタヘッドからのデータストリームはその後、データを中継しなければならないピアの送信キューに押し込まれる。クラスタ情報データベースは、各サブストリームのクラスタメンバーシップ情報を含む。クラスタメンバーシップは、本発明の一元化された方法によってグローバルに分かる。例えば、図３の第１クラスタにおいて、ノードａ１は、サブストリーム１に責任を負うクラスタヘッドである。クラスタａ２は、サブストリーム２に責任を負うクラスタヘッドである。他の３つのノードは、ａ１とａ２の両方からデータを受信するピアである。クラスタ情報を、データハンドラが利用できる。
【００７５】
図５のフローチャートは、ピアのデータハンドリング処理を示す。５０５において、ピアは、着信キューによって同じクラスタ内の複数のクラスタヘッドおよびピアから着信データを受信する。５１０において、受信されたデータは、受信されたデータを再生バッファ／キューに格納する、ピアのデータハンドラに転送される。５１５において、クラスタ情報データベースから利用できるクラスタ情報を使用することによって、データハンドラは、再生バッファに格納されたデータを送信キューに押し込んで、同じクラスタ内の他のピアに中継されるようにする。
【００７６】
図６は、クラスタヘッドのアーキテクチャを示す。クラスタヘッドは、２つのクラスタ、即ち、上位レベルのクラスタと下位レベルのクラスタに参入する。上位レベルのクラスタにおいて、クラスタヘッドは、コンテンツサーバから１つのサブストリームを読み出す。下位レベルのクラスタにおいて、クラスタヘッドは、コンテンツサーバから読み出されたサブストリームのソースとして機能する。それと同時に、クラスタヘッドは、同じクラスタ内の普通のピアとして、他のクラスタヘッドからサブストリームも得る。コンテンツサーバから読み出されたサブストリームと上位レベルのクラスタ内の他のピアから受信されたサブストリームとが組み合わされて、完全なストリームを形成する。上位レベルのデータハンドリング処理は、ピアのデータハンドリング処理と同じである（図５を参照）。クラスタヘッドの上位レベルのデータハンドラは、着信キュー経由で、同じクラスタ内の他のピアだけでなく、コンテンツサーバからもデータコンテンツを受信する。クラスタヘッドが、そのクラスタヘッドがデータ／コンテンツをレンダリングする再生バッファである場合、データハンドラによって受信されたデータは、コンテンツバッファに格納される。サーバから読み出されたデータストリームはその後、データを中継しなければならない他の上位レベルのピアの送信キューに押し込まれる。上位レベルのデータハンドラは、受信されたデータをコンテンツバッファに格納する。その後コンテンツバッファに格納されたデータ／コンテンツを、２つの下位レベルのデータハンドラのうち１つが利用できる。下位レベルのデータハンドリング処理は、２つのデータハンドラおよび「完全な」スケジューリングエグゼキュタ(scheduling executor)を含む。このようなクラスタヘッドがサーバとして機能するサブストリームの場合、「完全な」スケジューリングアルゴリズムがその後実行されて、個々のピアに対してストリーム速度が計算される。「完全な」スケジューリングアルゴリズムの出力に基づいて、上位レベルのコンテンツバッファからのデータがストリームに分割される。データはその後、対応する下位レベルのピアの送信キューに押し込まれて、下位レベルのピアに送信される。クラスタヘッドはまた、同じクラスタ内の他のクラスタヘッドによって供給されるサブストリームの普通のピアとしてふるまう。クラスタヘッドが別のクラスタヘッドからデータを受信する場合、クラスタヘッドは、そのデータを他の下位レベルのピアに中継する。同じクラスタ内の他のピア（他のサブストリームのクラスタヘッド）によって中継されたデータの場合、データは、コンテンツバッファに格納されて、これ以上の動作は要求されない。なぜならば、他のサブストリームのクラスタヘッドがすでにそのコンテンツをクラスタ内の他のピアに供給しているからである。
【００７７】
クラスタヘッドの下位レベルのデータハンドリング処理のフローチャートを図７に示す。クラスタヘッドのコンテンツバッファに格納されたデータ／コンテンツを、クラスタヘッドの下位レベルのデータハンドラが利用できる。７０５において、「完全な」スケジューリングアルゴリズムが実行されて、個々の下位レベルのピアに対してストリーム速度を計算する。７１０において、中間のデータハンドラは、コンテンツバッファから読み出されたコンテンツをサブストリームに分割して、データを下位レベルのピアの送信キューに押し込む。７１５において、コンテンツは、同じクラスタ内の他のクラスタヘッドおよびピアから受信される。クラスタヘッドは、クラスタヘッドが責任を負うサブストリームのサーバであることに留意されたい。同時に、クラスタヘッドは、同じクラスタ内の他のクラスタヘッドおよびピアから他のサブストリームを読み出す必要がある。クラスタヘッドは、すべてのサブストリーム分散に参入する。７２５において、他のクラスタヘッドからのデータが送信キューに押し込まれて、他の下位レベルのピアに中継される。
【００７８】
図８は、コンテンツ／ソースサーバのアーキテクチャを示す。ソースサーバは、元のストリームをｋと同じ速度ストリームに分割する。ｋは所定の構成パラメータである。典型的には、ｋは２に設定されるが、１クラスタ当たりのクラスタヘッドが２以上になることもある。最上レベルにおいて、各ストリームに１つずつクラスタが形成される。ソースサーバは、各最上レベルのクラスタに供給する１つのサブサーバを有する。データハンドリング処理の各サブサーバは、コンテンツバッファ、データハンドラ、および「完全な」ストリーミングエグゼキュタを含む。コンテンツバッファ内のサーバによってソース／コンテンツが格納される。データハンドラは、格納されたコンテンツにアクセスして、「完全な」ストリーミングエグゼキュタによって決められたストリーム分割に従って、データハンドラは、コンテンツを送信キューに押し込んで、上位レベルのクラスタヘッドに中継されるようにする。Ｋは、クラスタヘッド数である。Ｋは、最上レベルのクラスタ数でもある。
【００７９】
図９は、サブサーバのデータハンドリング処理を示すフローチャートである。９０５において、ソース／コンテンツサーバは、ストリームを同じ速度のサブストリームに分割する。単一のサブサーバは、各サブストリームに責任を負う。例えば、サブサーバｋは、ｋ番目のサブストリームに責任を負う。９１０において、サブストリームは、対応するサブストリームのコンテンツバッファに格納される。９１５において、各サーバのデータハンドラは、コンテンツにアクセスして、「完全な」ストリーミングアルゴリズムを実行して、最上レベルのクラスタ内の個々のピアに対してサブストリーム速度を決める。コンテンツバッファ内のコンテンツ／データは、サブストリームに分割されて、対応する最上レベルのピアの送信キューに押し込まれる。送信処理によって、コンテンツ／データは、ピアに送信される。
【００８０】
本発明を、ハードウェア、ソフトウェア、ファームウェア、専用プロセッサ、またはそれらの組み合わせのさまざまな形式に実装できることを理解されたい。好適には、本発明は、ハードウェアとソフトウェアの組み合わせとして実装される。さらに、ソフトウェアは、好適には、プログラムストレージデバイス上で明示的に実施されるアプリケーションプログラムとして実装される。任意の適したアーキテクチャを備えるマシンによって、アプリケーションプログラムをアップロードして実行できる。好適には、マシンは、１または複数の中央処理装置（ＣＰＵ）、ランダムアクセスメモリ（ＲＡＭ）、および１または複数の入力／出力（Ｉ／Ｏ）インタフェース等のハードウェアを有するコンピュータプラットフォーム上で実装される。コンピュータプラットフォームは、オペレーティングシステムおよびマイクロインストラクションコードも含む。本明細書で説明されたさまざまな処理および機能を、オペレーティングシステム経由で実行される、マイクロインストラクションコードの部分か、またはアプリケーションプログラム（またはそれらの組み合わせ）の部分にできる。さらに、さまざまな他の周辺デバイスを、付加的なデータストレージデバイスおよび印刷デバイス等のコンピュータプラットフォームに接続にできる。
【００８１】
添付図面で示した構成要素であるシステムコンポーネントおよび方法ステップの一部は、好適にはソフトウェアに実装されているために、システムコンポーネント（または処理ステップ）間の実際の接続は、本発明がプログラムされる方法によって異なってよいこともさらに理解されたい。本明細書の教示で、当業者は、本発明によるこれらおよび同様の実装または構成を考えることができる。
【図１】
0005497752.tif 000031
【図２】
0005497752.tif 000032
【図３】
0005497752.tif 000033
【図４】
0005497752.tif 000034
【図５】
0005497752.tif 000035
【図６】
0005497752.tif 000036
【図７】
0005497752.tif 000037
【図８】
0005497752.tif 000038
【図９】
0005497752.tif 000039