説明

ピアツーピア接続を制御するシステムおよび方法

本発明は、局所化されたオーバーレイ上で個々のインターネット・サービス・プロバイダ(ISP)ネットワークのピアツーピア(P2P)ストリーミング・アプリケーション内のピアツーピア接続を制御するシステムおよび方法に関する。このシステムは、第1ISPネットワークの局所ピアの中でエッジ・ピアを選択するように構成された第1ISPネットワークに局所的なトラッカを含むことができる。選択されるエッジ・ピアは、第1ISPネットワークへまたはこれからサブストリームを転送するために第1ISPネットワークの外側のピアへの外部接続を有し、エッジ・ピアとして選択されない局所ピアは、局所化されたオーバーレイ上でサブストリームを転送するために第1ISPネットワーク内の他の局所ピアへの内部接続を有する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、局所化されたオーバーレイ上で個々のインターネット・サービス・プロバイダ(ISP)ネットワークのピアツーピア(P2P)ストリーミング・アプリケーション内のピアツーピア接続を制御するシステム及び方法に関する。
【背景技術】
【0002】
ピアツーピア(P2P)ストリーミング・アプリケーションは、比較的少数のサーバが本質的価値をサービスまたはアプリケーションに提供する従来の集中化されたリソースではなく、ネットワーク内の参加者の間での種々の接続性およびネットワーク参加者の累積帯域幅を使用する。P2Pアプリケーションは、通常、たとえばオーディオ、ビデオ、および/またはディジタル・データなどのコンテンツを含むコンテンツ・ファイルをインターネットを介して共有するのに使用される。さらに、P2Pストリーミング・アプリケーションは、インターネットを介するライブ・マルチメディアのスケーラブル・ストリーミングに広く使用されてきた。P2Pストリーミングでは、参加するピアが、オーバーレイを形成し、オーバーレイの上でコンテンツを配送する。
【0003】
従来のライブP2Pストリーミング・アプリケーションは、参加するピアの間のランダムな接続されたオーバーレイを使用する。たとえば、図1に、ランダム接続を含む従来のオーバーレイを示す。図1を参照すると、P2Pストリーミング・アプリケーション内の従来のシステム100は、インターネット・サービス・プロバイダ(ISP)ネットワークA(ISP A)内およびISPネットワークB(ISP B)内の、ランダムに接続されたピア105を含むことができる。たとえば、ISP A 110内のピア105のうちの1つが、ISP A 110(たとえば、内部)内の別のピアに接続し、またはISP B 120(外部)内のピア105のうちの1つに接続することができる。ピア105の間の接続はランダムなので、接続を、内部接続またはISP間接続(すなわち、外部接続)のいずれかとすることができる。用語ISP間接続および外部接続は、交換可能な用語である。しかし、ISP間接続のコストは、通常、内部接続より高い。ランダム・オーバーレイ・システムは、かなりの量のISP間接続を使用するので、そのようなシステムを実施するコストは、相対的に高い可能性がある。
【0004】
ピア105の間のISP間接続を減らすために、従来の手法は、各ISPネットワーク内のオーバーレイ接続性の局所化に焦点を合わせた。P2P局所化は、個々のISPネットワークが、ISP間接続を介するトラフィックを管理し、減らすために、そのポリシおよび他のISPネットワークとのビジネス関係を考慮しながら隣接ピアの選択を制御することを可能にする。
【0005】
局所化の方法の1タイプは、選択された個数のピアを使用するように局所ピアに指示するオラクルを使用する。たとえば、新しい局所ピアは、アンダーレイに参加する候補ピア(または潜在的隣接物)のリストを受信するためにP2PアプリケーションのP2Pブートストラップ・ノードに連絡することができる。次に、局所ピアは、局所ピアに関連するオラクルに候補ピアのリストを送信する。オラクルは、候補ピアのリストをソートすることによって接続プリファレンスを適用し、ソートされたリストを局所ピアに返す。局所ピアは、好ましい隣接物への接続を開始するために、ソートされたリストを使用する。この方法では、ISPは、局所ピアがどのピアを介して接続を試みるのかのいくらかの制御を有する。しかし、P2Pトラフィックの局所化は、潜在的に、局所ピアの各隣接物でのコンテンツの多様性を減らすことによって、P2Pアプリケーションの性能に影響する可能性がある。
【0006】
もう1つのタイプの局所化は、局所化されたオーバーレイを介するファイル・スウォーミング(file swarming)機構を使用する。スウォームベースの手法では、ビデオ・データは、複数のサブストリームに分割され、参加するピアは、ランダム・メッシュ・オーバーレイに編成され、スウォーミングは、各サブストリームの配送に使用される。親子関係が、接続されたピアの間に存在する。親としての各ピアは、サブストリームの可用性について子ピアに通知する。参加するピアのアクセス・リンク帯域幅を効果的に利用するために、ピアの着信度(incoming degree)および発信度(outgoing degree)は、着信帯域幅および発信帯域幅に比例しなければならない。これは、すべての接続がほぼ同一の平均帯域幅を有することを暗示する。スウォーミング・コンテンツ配送は、親ピアによるプッシュ・コンテンツ報告を子ピアによるプル・コンテンツ要求と組み合わせる。各ピアは、その親ピアのすべてからコンテンツを同時に受信し、その子ピアのすべてにコンテンツを提供する。親ピアは、その新しいサブストリームの可用性を子ピアのすべてに漸進的に報告する。親ピアの間の使用可能なサブストリームを考慮して、各ピアは、帯域幅の利用および配送品質を最大にするために、どのブロックが各親ピアからプルされなければならないのかを決定するために、ブロック・スケジューリング方式を周期的に呼び出す。
【0007】
しかし、スウォームベースの手法の従来の実施形態は、ファイル配送アプリケーションの緩和されたタイミング制約を利用し、このタイミング制約は、単一の要件すなわち、すべてのセグメントの配送のみを有する。その結果、ライブ・ビデオ・ストリームの再生が劇的に増え、「ライブ・ストリーミング」の主張が疑わしくなる(たとえば、数十秒、より大きいスウォームについては数分さえ)ことが、調査によって示された。
【発明の概要】
【課題を解決するための手段】
【0008】
本発明は、局所化されたオーバーレイ上で個々のインターネット・サービス・プロバイダ(ISP)ネットワークのピアツーピア(P2P)ストリーミング・アプリケーション内のピアツーピア接続を制御するシステムおよび方法に関する。
【0009】
このシステムは、第1ISPネットワークの局所ピアの中でエッジ・ピアを選択するように構成された第1ISPに局所的なトラッカを含むことができる。選択されるエッジ・ピアは、第1ISPネットワークへまたはこれからサブストリームを転送するために第1ISPネットワークの外側のピアへの外部接続を有し、エッジ・ピアとして選択されない局所ピアは、局所化されたオーバーレイ上でサブストリームを転送するために第1ISPネットワーク内の他の局所ピアへの内部接続を有する。トラッカは、帯域幅に基づいてエッジ・ピアを選択することができる。さらに、トラッカは、既存エッジ・ピアがP2Pストリーミング・アプリケーションから離脱する時に、エッジ・ピアを選択することができる。代替案では、トラッカは、エッジ・ピアの個数が第1しきい値未満であるかどうかに基づいてエッジ・ピアを選択することができる。
【0010】
もう1つの実施形態では、トラッカは、第1タイプのエッジ・ピアおよび第2タイプのエッジ・ピアを選択するように構成される。第1タイプのエッジ・ピアは、着信外部接続を管理し、第2タイプのエッジ・ピアは、発信外部接続を管理する。
【0011】
このシステムは、エッジ・ピアからのアナウンス・メッセージに応答して外部接続を確立するために、エッジ・ピアに潜在的外部ピアのリストを提供するように構成されたセッションレベル・トラッカをさらに含む。エッジ・ピアだけが、第1ISPネットワークの外側の外部ピアに可視の局所ピアである。また、セッションレベル・トラッカは、局所トラッカのリストを提供するようにさらに構成され得る。
【0012】
一実施形態では、トラッカは、外部ピアと第1ISPネットワークのエッジ・ピアとの間の外部接続を介するサブストリームの転送をスケジューリングするようにさらに構成される。トラッカは、外部ピアで使用可能なサブストリームおよび各サブストリームのISPホップ・カウント(ICH)に基づいてサブストリームの転送をスケジューリングする。ICHは、サブストリームがトラバースしたISPネットワークの個数を示す。
【0013】
第1ISPネットワークの局所ピアは、内部親ピアで使用可能なサブストリームおよびピア・ホップ・カウント(PHC)に基づいて、内部接続を介するサブストリームの転送をスケジューリングする。PHCは、それぞれのサブストリームが単一のISPネットワーク内でトラバースした内部ピアの個数を示す。局所ピアは、最小のPHCカウント値を有するサブストリームの転送をスケジューリングする。
【0014】
各サブストリームは、(1)それぞれのサブストリームがトラバースしたISPネットワークの個数を示すISPホップ・カウント(ICH)、(2)それぞれのサブストリームが単一のISPネットワーク内でトラバースした内部ピアの個数を示すピア・ホップ・カウント(PHC)、および(3)それぞれのサブストリームがISPネットワークにかかわりなくトラバースしたピアの総数を示す総ホップ・カウント(OHC)を含む。
【0015】
この方法は、第1ISPネットワークに局所的なトラッカによって、第1ISPネットワークの局所ピアの中でエッジ・ピアを選択することを含む。選択されるエッジ・ピアは、第1ISPネットワークへまたはこれからサブストリームを転送するために第1ISPネットワークの外側のピアへの外部接続を有し、エッジ・ピアとして選択されない局所ピアは、局所化されたオーバーレイ上でサブストリームを転送するために第1ISPネットワーク内の他の局所ピアへの内部接続を有する。選択するステップは、帯域幅に基づいてエッジ・ピアを選択する。さらに、選択するステップは、既存エッジ・ピアがP2Pストリーミング・アプリケーションから離脱する時に、エッジ・ピアを選択する。代替案では、選択するステップは、エッジ・ピアの個数が第1しきい値未満であるかどうかに基づいてエッジ・ピアを選択する。
【0016】
もう1つの実施形態では、選択するステップは、第1タイプのエッジ・ピアおよび第2タイプのエッジ・ピアを選択する。第1タイプのエッジ・ピアは、着信外部接続を管理し、第2タイプのエッジ・ピアは、発信外部接続を管理する。
【0017】
この方法は、エッジ・ピアからのアナウンス・メッセージに応答して外部接続を確立するために、セッションレべル・トラッカによって、エッジ・ピアに潜在的外部ピアのリストを提供することをさらに含む。この方法は、トラッカによって、外部ピアと第1ISPネットワークのエッジ・ピアとの間の外部接続を介するサブストリームの転送をスケジューリングすることをさらに含む。スケジューリングするステップは、外部ピアで使用可能なサブストリームおよび各サブストリームのISPホップ・カウント(ICH)に基づいてサブストリームの転送をスケジューリングする。ICHは、サブストリームがトラバースしたISPネットワークの個数を示す。
【0018】
この方法は、第1ISPネットワークの局所ピアによって、内部親ピアで使用可能なサブストリームおよびピア・ホップ・カウント(PHC)に基づいて、内部接続を介するサブストリームの転送をスケジューリングすることをさらに含む。PHCは、それぞれのサブストリームが単一のISPネットワーク内でトラバースした内部ピアの個数を示す。
【0019】
例の実施形態は、本明細書で下で与えられる詳細な説明および添付図面からより十分に理解されるようになり、ここで、同様の要素は、同様の符号によって表され、詳細な説明および添付図面は、例示として与えられるのみであり、したがって、本発明を限定しない。
【図面の簡単な説明】
【0020】
【図1】ランダム接続を示す従来のオーバーレイを示す図である。
【図2】本発明の実施形態によるピアツーピア接続を制御するシステムを示す図である。
【図3】本発明の実施形態による局所トラッカの構造の例を示す図である。
【図4A】本発明の実施形態による2ティア・スケジューリング方式に従うピアツーピア接続の制御を示す流れ図である。
【図4B】本発明の実施形態によるP2Pストリーミング・アプリケーション内のビデオ・ストリームの構造を示す図である。
【図5】本発明の実施形態によるISP間スケジューリングの例を示す図である。
【発明を実施するための形態】
【0021】
本発明のさまざまな実施形態を、これから添付図面を参照してより十分に説明するが、添付図面には、本発明のいくつかの実施形態が示されている。同様の符号は、図の説明全体を通じて同様の要素を指す。
【0022】
本明細書で使用される時に、単数形「a」、「an」、および「the」は、文脈がそうではないことを明瞭に示さない限り、複数形をも含むことが意図されている。さらに、用語「comprises」、「comprising」、「includes」、および/または「including」は、本明細書で使用される時に、述べられた特徴、整数、ステップ、動作、要素、および/またはコンポーネントの存在を指定するが、1つまたは複数の他の特徴、整数、ステップ、動作、要素、コンポーネント、および/またはその群の存在または追加を除外しないことを理解されたい。
【0023】
いくつかの代替実施形態で、記された機能/行為が図に記された順序から外れて発生してもよいことにも留意されたい。たとえば、連続して示される2つの図が、実際には、用いられる機能性/行為に応じて、実質的に同時に実行されてもよく、あるいは、時々、逆の順序で実行されてもよい。
【0024】
本発明の諸部分および対応する詳細な記述は、ソフトウェアすなわち、コンピュータ・メモリ内のデータ・ビットに対する動作のアルゴリズムおよび記号表現に関して提示される。これらの記述および表現は、当業者がそれによって彼らの作業の実質を他の当業者に効率的に伝える記述および表現である。アルゴリズムは、この用語が本明細書で使用される時に、および一般に使用される時に、所望の結果につながるステップの自己完結的シーケンスと考えられる。ステップは、物理的量の物理的操作を必要とするステップである。必ずではないが通常、これらの量は、格納、転送、組合せ、比較、および他の操作が可能な光信号、電気信号、または磁気信号の形をとる。時々、主に一般的な使用の理由から、これらの信号をビット、値、要素、記号、文字、項、数、または類似物と呼ぶことが便利であることがわかっている。
【0025】
しかし、上記および類似する用語のすべてが、適切な物理的量に関連付けられなければならず、単にこれらの量に適用される便利なラベルであることに留意されたい。そうではないと具体的に述べられない限り、または議論から明白であるように、「selecting(選択)」、「providing(提供)」、「determining(判定)」、「managing(管理)」、「displaying(表示)」、または類似物などの用語は、コンピュータ・システムのレジスタおよびメモリ内の物理的電子量として表されたデータを操作し、コンピュータ・システム・メモリもしくはレジスタまたは他のそのような情報記憶デバイス、情報伝送デバイス、もしくは情報表示デバイス内の物理的量として同様に表された他のデータに変換する、コンピュータ・システムまたは類似する電子コンピューティング・デバイスのアクションおよびプロセスを指す。
【0026】
また、本発明のソフトウェア実施される諸態様が、通常は、ある形のプログラム記憶媒体上で符号化され、またはあるタイプの伝送媒体を介して実施されることに留意されたい。プログラム記憶媒体は、磁気(たとえば、フロッピ・ディスクまたはハード・ドライブ)または光学(たとえば、コンパクト・ディスク読取り専用メモリすなわち「CD ROM」)とすることができ、読取り専用またはランダム・アクセスとすることができる。同様に、伝送媒体は、より対線、同軸ケーブル、光ファイバ、または当技術分野で既知のある他の適切な伝送媒体とすることができる。本発明は、任意の所与の実施態様のこれらの態様によって限定はされない。
【0027】
本発明を、これから、添付図面を参照して説明する。さまざまな構造、システム、およびデバイスが、説明のみのために、また、当業者に周知の詳細で本発明を不明瞭にすることがないように、図面では概略的に示されている。それでも、添付図面は、本発明の例示的な例を記述し、説明するために含まれる。本明細書で使用される単語および句は、当業者によるこれらの単語および句の理解と一貫する意味を有すると理解され、解釈されなければならない。用語または句の特殊な定義すなわち、当業者によって理解される通常の慣例的な意味とは異なる定義が、本明細書での用語または句の一貫した使用によって暗示されることは、意図されていない。用語または句が、特殊な意味すなわち、当業者によって理解されるものとは異なる意味を有することが意図される範囲で、そのような特殊な定義は、用語または句の特殊な定義を直接に明確に提供する定義的な形で本明細書で特に示される。
【0028】
本発明の例の実施形態は、局所化されたオーバーレイを介して個々のインターネット・サービス・プロバイダ(ISP)ネットワークのピアツーピア(P2P)ストリーミング・アプリケーション内のピアツーピア接続を制御するシステムおよび方法に関する。本発明の実施形態は、たとえば高品質ビデオ・ストリーミングを配送するためのスウォームベースの手法について外部接続の個数を制限し、スケジューリング方式を改訂することによって、個々のISPネットワークの外部トラフィックを効果的に制御する。対照的に、オーバーレイ局所化での基本的前提は、ピアが正しい個数の親ピアを識別できる限り、ピアが親ピアの選択におけるプリファレンスを全く有しないことである。同一ISPネットワーク内の他のピアを発見し、これに接続するように同一ISPネットワーク内のピアに指示することによって、各ISPネットワークの外部(着信および発信)接続の個数を減らすことができ、これは、P2Pアプリケーションに関連する外部トラフィック(たとえば、コスト)を比例して減らす。
【0029】
図2に、本発明の実施形態による個々のISPネットワークのP2Pストリーミング・アプリケーション内のP2P接続を制御するシステム200を示す。図2のシステム200は、2つのISPネットワークすなわちISP AおよびISP Bと、ISP間接続のために外部ピアを発見するセッションレベル・トラッカ120と、P2Pストリーミング・アプリケーション内でインターネットを介して接続されたISP A内のピア105およびISP B内のピア125とを示す。P2Pストリーミング・アプリケーションは、ピアの間で、オーディオ、ビデオ、および/またはディジタル・データなどのコンテンツを含むコンテンツ・ファイルをインターネットを介して共有するのに使用される。さらに、P2Pストリーミング・アプリケーションは、インターネットを介するライブ・マルチメディアのストリーミングに使用される。
【0030】
ピア105およびピア125は、パーソナル・コンピュータ、無線電話機、または任意の他の類似するデバイスなど、P2Pアプリケーションを動作させるように構成された任意のタイプのシステムとすることができる。ピア105は、ISP Aに局所的であり、ピア125は、ISP Bに局所的である。あるISPネットワークに局所的なピアを、局所ピアと称する場合がある。図2は、有限の個数のピアを示すが、あるISP内のピアの個数は、P2Pアプリケーションに関連するトラフィックに応じて継続的に変化する。さらに、ISP Aは、エッジ・ピア110を含み、エッジ・ピア110は、ISP Aに局所的なピア105でもあるが、下で説明するようにエッジ・ピアとして選択されている。
【0031】
ISP Aは、局所トラッカ115を含み、局所トラッカ115には、P2Pネットワークに参加するISP Aに局所的なピア(たとえば、ピア105および110)が、それ自体をアナウンスする。局所トラッカ115と各ピア105および110との間の接続は、局所トラッカ115と各ピア105および110との間の点線の接続線によって示されている。応答として、局所トラッカ115は、潜在的な接続に関する候補ピアのリストを各ピア105および110に返す。さらに、局所トラッカ115は、ISP Aの着信外部接続および発信外部接続の総数を判定し、集計着信帯域幅が少なくともストリーム帯域幅と等しいことを保証するように構成される。
【0032】
ISP A内では、ピア105および110の間の実線が、P2Pデータの転送(内部)を示す。また、インターネットからエッジ・ピア110への実線は、下でさらに説明される、外部ピアまたはコンテンツ・プロバイダ(外部)などの外側のソースとのP2Pデータの転送を示す。同様に、ISP B内では、実線が、P2Pデータの転送を示す。しかし、ISP B内では、各ピア125が、内部的および外部的にP2Pを転送する。その結果、P2P外部制御が、ISP B内のピア125の外部接続のすべてについて要求される(点線の矢印によって示されるように)が、P2P外部制御が、ISP A内のエッジ・ピア110の接続についてのみ要求される(点線の矢印によって示されるように)。
【0033】
2つのISPネットワークだけが図2に示されているが、本発明の例の実施形態は、任意の個数のISPネットワークを包含する。ISP Aとは異なって、ISP Bは局所化を使用しない。そうではなく、ISP B内のすべてのピア125は、ISP A内のピア105への外部接続のためにセッションレベル・トラッカ120に連絡する。図2のISP B内のP2Pネットワークは、局所化なしのISPとして図示されているが、ISP Bが局所化を含んでもよい。言い替えると、局所トラッカ115は、ISP Aネットワークの外部の、局所化を含むまたは局所化を含まない(図2に示されているように)ISPネットワークの一部であるピアへの外部接続を制御することができる。
【0034】
図3に、本発明の実施形態による局所トラッカ115の構造の例を示す。局所トラッカ115は、中央処理装置(CPU)321、ランダム・アクセス・メモリ(RAM)322、読取り専用メモリ(ROM)326、ハード・ディスク・ドライブ327、およびネットワーク・インターフェース328を含む。局所トラッカ115は、当業者に周知の、図3に示されたもの以外の他のコンポーネントを含むこともできる。CPU 321、RAM 322、ROM 326、ハード・ディスク・ドライブ327、およびネットワーク・インターフェース328は、バスを介してお互いと通信する。ハード・ディスク・ドライブ327は、当業者に周知の形で動作する。
【0035】
RAM 322は、CPU 321が局所トラッカ115の動作を実行するための命令を提供するオペレーティング・システム323を格納することができる。任意の汎用オペレーティグ・システムを使用することができる。ネットワーク・インターフェース・ユニット328は、CPU 321が、TCP/IPプロトコルを含むさまざまな通信プロトコルと共に使用するために構築された、インターネットまたはある他の通信ネットワークと通信することを可能にする。ネットワーク・インターフェース・ユニット328は、たとえば、トランシーバ(1つまたは複数)、送受信デバイス(1つまたは複数)、および/またはネットワーク・インターフェース・カード(NIC)(1つまたは複数)を含むことができる。ネットワーク・インターフェース・ユニット328は、インターネット、ピア105、110、および125、セッションレベル・トラッカ120、ならびに局所トラッカ115の機能を実行する任意の他のデバイスと通信するように構成される。
【0036】
また、RAM 322は、1つまたは複数のデータ・ストレージ・ユニットを含むことができ、このデータ・ストレージ・ユニットを局所トラッカ115によって利用して、たとえば、とりわけアプリケーションならびにデータベース情報を格納することができる。たとえば、RAM 322は、下で説明される局所トラッカ115の諸機能を実行するのに必要なアプリケーションを格納することができる。
【0037】
図4Aに、本発明の実施形態による2ティア・スケジューリング方式に従うピアツーピア接続の制御の流れ図を示す。局所トラッカ115は、外部接続の個数を制限することによってISP Aの外部トラフィックを制御する。
【0038】
具体的には、S410を参照すると、局所トラッカ115は、ISP Aの局所ピアの中からエッジ・ピア110すなわちピアA1およびピアA2を選択するように構成される。選択されたエッジ・ピア110は、ISP Aにビデオ・ストリームのサブストリームを配送するために、ISP Aネットワークの外側のピア(たとえば、ピア125)への外部接続を維持するが、ISP Aの局所ピアは、ISP Aの局所化されたオーバーレイ上でサブストリームを配送するためにISP A内の他の局所ピアへの内部接続を維持する。言い替えると、エッジ・ピア110は、外部接続を有し、ISP Aの内部のピア(たとえば、ピア105)は、外部接続を有しない。局所トラッカ115によって行われる接続判断は、エッジ・ピア110の帯域幅に基づくものとすることができる。たとえば、比較的高い帯域幅を有するISP Aに局所的なピアは、エッジ・ピア110として選択されるのに好ましい。しかし、選択判断は、潜在的なエッジ・ピアの帯域幅だけに限定されるのではなく、他のタイプの判断基準を、そのような選択判断を行うための基礎として使用することができる。本発明のため、局所トラッカ115は、ISP Aに局所的なピアのすべてより少数をエッジ・ピア110として選択する。エッジ・ピアの個数は、1以上の、ISP Aに局所的なピアの総数より小さい任意の整数とすることができる。さらに、エッジ・ピアがP2Pアプリケーションから離脱した後に、局所トラッカ115は、帯域幅または上で説明した任意の他の判断基準に基づいて、ISP Aに局所的な別のピアをエッジ・ピアとして選択することができる。
【0039】
別の実施形態では、局所トラッカ115は、ISPネットワーク内のエッジ・ピアの個数を判定し、エッジ・ピアの個数が第1しきい値未満であるかどうかに基づいてエッジ・ピアを選択するように構成される。第1しきい値は、ピアの所望の(または、代替案では所定の)個数とすることができる。ピアの所望の個数は、1または1より大きい任意の整数など、ピアの任意の個数とすることができる。
【0040】
別の実施形態では、局所トラッカ115は、局所ピアおよび通常のピアまたはエッジ・ピアのいずれかとしてのその局所ピアの状況を追跡する。たとえば、新しいピアがISP A内でP2Pアプリケーションに参加する時に、局所トラッカ115は、エッジ・ピアおよび局所ピアの個数を新しいピアに送信する。新たに参加するピアは、局所トラッカ115によって報告されたエッジ・ピアの個数に基づいて、エッジ・ピアになると決断する。たとえば、エッジ・ピアの個数が第1しきい値未満である場合に、ピアは、エッジ・ピアになる。
【0041】
エッジ・ピア110が選択された後に、エッジ・ピア110は、下で述べるように、外部親ピアを入手し(S420)、外部ピアに接続し(S430)、ISP間スケジューリング機構に従ってコンテンツ情報を交換し始める(S440)。また、局所ピア(たとえば、ピア105および110)は、ISP Aネットワーク内の他の局所ピアに接続し(S450)、ISP内スケジューリング機構に従ってコンテンツ情報を交換し始める(S460)。局所化されたオーバーレイ上のエッジ・ピア110または局所ピア105のいずれかへのISP Aネットワークのピアの分類は、たとえば、ISP内スケジューリングおよびISP間スケジューリングに従って実行されるビデオ・ストリームの配送のための2ティア・スケジューリング機構を提供する。図4Aの流れ図は、ステップのシーケンスを示すが、これらのステップは、順序から外れてまたは同時に行うことができる。たとえば、通常、ISP内スケジューリングは、ISP間スケジューリングと同時に実行される。
【0042】
S420では、セッションレベル・トラッカ120は、エッジ・ピア110からのアナウンス・メッセージに応答して外部接続を確立するために潜在的な外部ピア(たとえば、ISP B内のピア125)のリストを提供するように構成される。言い替えると、エッジ・ピア110は、セッションレベル・トラッカ120を介して外部ピア(たとえば、ISP B内のピア125)を発見する。エッジ・ピア110は、アナウンス・メッセージを介してセッションレベル・トラッカ120にシグナリングし、返報として、潜在的な外部ピアのリストを受信する。潜在的な外部ピアのリストに基づいて、エッジ・ピア110は、外部ピアのサブセットに接続する(S430)。選択されたエッジ・ピア110だけが、それ自体をセッションレベル・トラッカ120にアナウンスするので、エッジ・ピア110だけが、ISP Aネットワークの外側の外部ピア(たとえば、ISP B内のピア125)に可視の局所ピアである。したがって、エッジ・ピア110以外のピアは、着信クロスISP接続要求を受信せず、これは、着信接続の個数を効果的に制限し、制御する。
【0043】
別の実施形態では、局所トラッカ115は、外部着信接続要求と外部発信接続要求との間で区別するために、2つの異なるクラスのエッジ・ピア110を選択するように構成される。たとえば、局所トラッカ115は、着信外部接続要求を管理する第1タイプのエッジ・ピアと発信外部接続要求を管理する第2タイプのエッジ・ピアとを選択する。局所トラッカ115によって選択される第1タイプのエッジ・ピアは、ISP Aネットワークの外側のピア(たとえば、ピア125)からの着信接続を受け入れ、親ピアとしてISP Aネットワークの外側のピアにサービスする責任を負う。第2タイプのエッジ・ピアは、外部親ピアからISP Aネットワーク(たとえば、局所ピア105および110)にコンテンツ情報を持ってくるために外部親ピアに接続する責任を負う。
【0044】
一実施形態では、第1タイプのエッジ・ピアは、それ自体をセッションレベル・トラッカ120にアナウンスし、したがって、第1タイプのエッジ・ピアを外部ピアに可視にする。第2タイプのエッジ・ピアは、セッションレベル・トラッカ120に連絡し、他のISPネットワークに第1タイプのエッジ・ピアのリストを要求する。
【0045】
別の実施形態では、局所化対応ISPネットワーク(たとえば、ISP A)からのピアは、それ自体をセッションレベル・トラッカ120にアナウンスしない。そうではなく、ISP Aの局所トラッカ115および他の局所化対応ISPネットワークの局所トラッカが、それら自体をセッションレベル・トラッカ120にアナウンスする。外部エッジ・ピア(または局所化されないISPネットワーク内の、たとえばISP Bからの通常のピア)が、セッションレベル・トラッカ120に連絡する時に、外部エッジ・ピアまたは通常のピアは、その要求に対するセッションレベル・トラッカの応答内で局所トラッカを識別する。たとえば、局所トラッカのリストが、ISP Aネットワークの局所トラッカ115を含む場合には、ISP Bからの要求するピアは、その後、ISP Aの局所トラッカ115に連絡する。その後、局所トラッカ115は、発信接続の個数がしきい値未満である場合に、ランダムに選択された/先験的に選択された局所ピアに要求をリダイレクト/転送する。この場合に、外部ピアは、局所ピアに接続し、この局所ピアは、効果的に第2タイプのエッジ・ピアになる。下で述べる実施形態は、単純さのために、第1タイプのエッジ・ピアと第2タイプのエッジ・ピアとの間の区別なしでエッジ・ピア110に言及する。しかし、下で述べる実施形態は、第1タイプのエッジ・ピアおよび第2タイプのエッジ・ピアと共に動作することもできる。
【0046】
S440では、エッジ・ピア110は、下で述べるように、ISP間スケジューリング機構に従って、接続された外部ピアへ/から中継されるビデオ・ストリームに関する情報を交換する。
【0047】
S450では、エッジ・ピア110になるために選択されなかった局所ピア105が、ISP Aネットワークの局所ピアだけに接続する。たとえば、上で説明したように、新しいピアがISP A内のP2Pネットワークに参加する時に、新しいピアは、アナウンスメント・メッセージを介して局所トラッカ115にシグナリングする。返報として、新たに参加するピアは、潜在的ピアのリストを受信する。その後、新たに参加する局所ピアは、潜在的ピアの受信されたリストに基づいて、ISP Aネットワーク内の他の局所ピアに接続する。S460では、局所ピア105が、下でISP間スケジューリング機構の後に述べるISP内スケジューリング機構に従って、ISP Aネットワーク内の他の局所ピアへ/から中継されるビデオ・データに関する情報を交換する。
【0048】
本発明の実施形態は、2つのレベルすなわちソースから個々のISPネットワークへ(ISP間スケジューリングを介する)および各着信エッジ・ピア110からすべての内部ピアへ(ISP内スケジューリングを介する)スケジューリング方式を提供する。ISP間スケジューリングは、たとえば外部ピアからISPネットワークへ中継されるビデオ・ストリームのサブストリームの配送のスケジューリングに関し、ここで、ISPネットワークは、単一のピアとして表される。言い替えると、ISP間スケジューリングは、個々のISPネットワークへの最高品質ビデオ・ストリームの配送に焦点を合わせたものである。その結果、ISP間スケジューリングは、外部接続だけに関係し、したがって、エッジ・ピア110で実施される。対照的に、ISP内スケジューリングは、エッジ・ピア110から個々のISPネットワーク内のすべての内部ピアへの各サブストリームの配送に焦点を合わせたものである。ISP内スケジューリングは、各ISP内の内部接続を管理する責任だけを負い、内部親ピアを有するすべてのピアによって実施される。ISP間スケジューリング・レベルとISP内スケジューリング・レベルとの両方について効果的な配送を達成するために、ビデオ・ストリームは、複数のサブストリームに分割される。
【0049】
図4Bに、本発明の実施形態によるP2Pストリーミング・アプリケーション内のビデオ・ストリーム300の構造を示す。ビデオ・ストリーム300は、n個のサブストリームに分割され、ここで、nは、1以上の任意の整数である。各サブストリームは、ISPホップ・カウント(IHC)、ピア・ホップ・カウント(PHC)、および総ホップ・カウント(OHC)という3つのカウンタを担持する。IHCカウンタは、サブストリームがトラバースしたISPネットワークの個数を記録する。PHCカウンタは、サブストリームが単一のISPネットワーク内でトラバースした内部ピアの個数を記録する。PHCカウンタは、サブストリームがそこでISPネットワークに入る対応するエッジ・ピアによってリセットされる。OHCカウンタは、サブストリームがトラバースしたピア(そのISPに関わりなく)の総数を記録する。
【0050】
図5に、本発明の実施形態によるISP間スケジューリングの例を示す。図5は、2つのサブストリームS1およびS2が、ソース501から6つのISPネットワーク502(ISP1、ISP2、ISP3、ISP4、ISP5、およびISP6)のグループに配送される例を示す。各ISPネットワーク502ならびに個々のピアは、2の着信度および発信度を有する。各ISPネットワーク502は、そのそれぞれのISPネットワークに局所的な複数のピアを含む。
【0051】
ISP1内のピアAは、ISP3内のピアCの親ピアと考えられ、ISP1内のピアBは、ISP4内のピアDの親ピアと考えられる。ISP3内のピアCおよびISP4内のピアDは、エッジ・ピア110である。ISP1内のピアAを参照すると、2つのサブストリームS1およびS2が、ISP3内のピアCから使用可能である。この特定の例では、ピアAでのサブストリームS1とS2との両方が、そのそれぞれのOHC値およびIHC値を示す。サブストリームS1について、OHC=7かつIHC=1である。サブストリームS2について、OHC=5かつIHC=3である。サブストリームS1のIHCは、ISP1がこのサブストリームをソース501から直接に受信するので、1である。その一方で、サブストリームS2は、ISP1内のピアAに到着するために、2つ多いISP(たとえば、ISP 2およびISP 5)をトラバースした。したがって、ピアAのサブストリーム2のIHCは、3である。さらに、ピアBでは、サブストリームS1とS2との両方が、そのそれぞれのOHC値およびIHC値を示す。サブストリームS1について、OHC=6かつIHC=1である。サブストリームS2について、OHC=5かつIHC=3である。
【0052】
すべてのサブストリームが各ISPに配送されることを保証するために、子ピア(たとえば、ISP3内のピアCおよびISP4内のピアD)がそのそれぞれの親ピア(たとえば、ISP1内のピアAおよびISP1内のピアB)からどのサブストリームをプルするのかをスケジューリングするために、局所トラッカ115は、周期的にまたはエッジ・ピアの離脱の後に、対応する外部親ピアで使用可能なサブストリームならびに各サブストリームの関連するIHCを入手するためにすべてのエッジ・ピア110をポーリングすることによって、調整を実行する。この場合に、ISP3の局所トラッカ115は、ピアAでのサブストリームS1およびS2に関する識別する情報およびピアAでのサブストリームのそれぞれのIHC値を入手する。ISP3の局所トラッカ115も、ピアA以外のISP3のエッジ・ピアでの他のサブストリームに関する識別する情報を入手する。
【0053】
局所トラッカ115が、それぞれの親ピアでのサブストリームの可用性およびIHC値に関する情報をエッジ・ピアから受信した後に、局所トラッカ115は、サブストリームのすべてがISPに配送されることを保証するために、エッジ・ピアへのサブストリームの配送を調整する。局所トラッカ115の調整機構は、すべてのサブストリームがISPに配送されることを保証するためにエッジ・ピアへのサブストリームの配送を調整する任意の周知の手段を使用することができる。
【0054】
対照的に、ISP内スケジューリングは、各サブストリームをその対応するエッジ・ピアからISPネットワーク内のすべての他のピアに配送する。各内部ピアは、使用可能なサブストリームおよび内部親ピアと各親ピアでのPHC値とに基づいて、異なるサブストリームを独立にスケジューリングする。言い替えると、各内部ピアは、各親でのPHC値と一緒に使用可能なサブストリームを検討し、最小のPHC(たとえば、ISPへの入口点からの最小距離)を有するサブストリームを選択する。最小PHCを有する複数のサブストリームが特定の親ピアで使用可能である場合には、より短い総ホップ・カウント(OHC)を有するサブストリームが選択される。このスケジューリング方式は、各内部ピアで周期的に(たとえば、Δ秒ごとに1回)呼び出される。
【0055】
ISP内スケジューリングおよびISP間スケジューリングを、上ではすべての接続が同一の帯域幅を有するという仮定の上で説明した。しかし、内スケジューリングと間スケジューリングとの両方が、参加するピアの動力学(または動揺)と、異なる接続にまたがる輻輳制御された帯域幅の短期変動および長期変動とに対処しなければならない場合がある。
【0056】
別の実施形態では、各エッジ・ピアは、そのエッジ・ピアが帯域幅しきい値を越える帯域幅を有する場合に、指定されないサブストリームを識別する。たとえば、指定されないサブストリームは、接続に割り当てられていないサブストリームであり、これは、指定されないサブストリームが、対応するエッジ・ピアまたは通常のピアによって要求されたことがないことを暗示する。その一方で、各エッジ・ピアは、指定されたサブストリームと呼ばれる特定のサブストリームを、その外部親ピアに要求する責任を負う。指定されないサブストリームの中で、エッジ・ピアは、これらのサブストリームの、隣接物内で使用可能ではないブロックを識別し、余分な帯域幅がある場合には、使用可能ではないブロックをその外部親ピアに要求する。

【特許請求の範囲】
【請求項1】
局所化されたオーバーレイ上で個々のインターネット・サービス・プロバイダ(ISP)ネットワークのピアツーピア(P2P)ストリーミング・アプリケーション内のピアツーピア接続を制御するシステムであって、
第1ISPネットワークの局所ピアの中でエッジ・ピアを選択するように構成された前記第1ISPに局所的なトラッカであって、前記選択されるエッジ・ピアは、前記第1ISPネットワークへまたはこれからサブストリームを転送するために前記第1ISPネットワークの外側のピアへの外部接続を有し、エッジ・ピアとして選択されない前記局所ピアは、前記局所化されたオーバーレイ上で前記サブストリームを転送するために前記第1ISPネットワーク内の他の局所ピアへの内部接続を有する、トラッカ
を含むシステム。
【請求項2】
前記トラッカは、帯域幅に基づいて前記エッジ・ピアを選択する、請求項1に記載のシステム。
【請求項3】
前記トラッカは、既存エッジ・ピアが前記P2Pストリーミング・アプリケーションから離脱する時に、エッジ・ピアを選択するようにさらに構成される、請求項1に記載のシステム。
【請求項4】
前記トラッカは、エッジ・ピアの個数が第1しきい値未満であるかどうかに基づいてエッジ・ピアを選択する、請求項1に記載のシステム。
【請求項5】
前記トラッカは、第1タイプのエッジ・ピアおよび第2タイプのエッジ・ピアを選択するように構成され、前記第1タイプの前記エッジ・ピアは、着信外部接続を管理し、前記第2タイプの前記エッジ・ピアは、発信外部接続を管理する、請求項1に記載のシステム。
【請求項6】
前記エッジ・ピアからのアナウンス・メッセージに応答して前記外部接続を確立するために、前記エッジ・ピアに潜在的外部ピアのリストを提供するように構成されたセッションレベル・トラッカであって、前記エッジ・ピアだけが、前記第1ISPネットワークの外側の外部ピアに可視の局所ピアである、セッションレベル・トラッカ
をさらに含む、請求項1に記載のシステム。
【請求項7】
前記セッションレベル・トラッカは、局所トラッカのリストを提供するようにさらに構成される、請求項6に記載のシステム。
【請求項8】
前記トラッカは、前記外部ピアと前記第1ISPネットワークの前記エッジ・ピアとの間の前記外部接続を介する前記サブストリームの前記転送をスケジューリングするようにさらに構成される、請求項1に記載のシステム。
【請求項9】
前記トラッカは、前記外部ピアで使用可能なサブストリームおよび各サブストリームのISPホップ・カウント(ICH)に基づいて前記サブストリームの前記転送をスケジューリングし、前記ICHは、サブストリームがトラバースしたISPネットワークの個数を示す、請求項8に記載のシステム。
【請求項10】
前記第1ISPネットワークの前記局所ピアは、内部親ピアで使用可能なサブストリームおよびピア・ホップ・カウント(PHC)に基づいて、前記内部接続を介する前記サブストリームの前記転送をスケジューリングし、前記PHCは、それぞれのサブストリームが単一のISPネットワーク内でトラバースした内部ピアの個数を示す、請求項1に記載のシステム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4A】
image rotate

【図4B】
image rotate

【図5】
image rotate


【公表番号】特表2013−514728(P2013−514728A)
【公表日】平成25年4月25日(2013.4.25)
【国際特許分類】
【出願番号】特願2012−544553(P2012−544553)
【出願日】平成22年11月23日(2010.11.23)
【国際出願番号】PCT/US2010/057706
【国際公開番号】WO2011/075291
【国際公開日】平成23年6月23日(2011.6.23)
【出願人】(391030332)アルカテル−ルーセント (1,149)
【Fターム(参考)】