(57)【特許請求の範囲】
【請求項１】
局所化されたオーバーレイ上で個々のインターネット・サービス・プロバイダ（ＩＳＰ）ネットワークのピアツーピア（Ｐ２Ｐ）ストリーミング・アプリケーション内のピアツーピア接続を制御するシステムであって、
第１ＩＳＰネットワークの局所ピアの中でエッジ・ピアを選択するように構成された前記第１ＩＳＰに局所的なトラッカであって、前記選択されるエッジ・ピアは、前記第１ＩＳＰネットワークへまたはこれからサブストリームを転送するために前記第１ＩＳＰネットワークの外側のピアへの外部接続を有し、エッジ・ピアとして選択されない前記局所ピアは、前記局所化されたオーバーレイ上で前記サブストリームを転送するために前記第１ＩＳＰネットワーク内の他の局所ピアへの内部接続を有する、トラッカ
を含み、
前記トラッカは、第１タイプの前記エッジ・ピアおよび第２タイプの前記エッジ・ピアを選択するように構成され、前記第１タイプの前記エッジ・ピアは、前記外側のピアからの着信外部接続を管理し、前記第２タイプの前記エッジ・ピアは、前記外側のピアへの発信外部接続を管理するシステム。
【請求項２】
前記トラッカは、帯域幅に基づいて前記エッジ・ピアを選択する、請求項１に記載のシステム。
【請求項３】
前記トラッカは、既存エッジ・ピアが前記Ｐ２Ｐストリーミング・アプリケーションから離脱する時に、エッジ・ピアを選択するようにさらに構成される、請求項１に記載のシステム。
【請求項４】
前記トラッカは、第１タイプのエッジ・ピアおよび第２タイプのエッジ・ピアを選択するように構成され、前記第１タイプの前記エッジ・ピアは、着信外部接続を管理し、前記第２タイプの前記エッジ・ピアは、発信外部接続を管理する、請求項１に記載のシステム。
【請求項５】
前記エッジ・ピアからのアナウンス・メッセージに応答して前記外部接続を確立するために、前記エッジ・ピアに潜在的外部ピアのリストを提供するように構成されたセッションレベル・トラッカであって、前記エッジ・ピアだけが、前記第１ＩＳＰネットワークの外側の外部ピアに可視の局所ピアである、セッションレベル・トラッカ
をさらに含む、請求項１に記載のシステム。
【請求項６】
前記セッションレベル・トラッカは、局所トラッカのリストを提供するようにさらに構成される、請求項５に記載のシステム。
【請求項７】
前記トラッカは、前記外部ピアと前記第１ＩＳＰネットワークの前記エッジ・ピアとの間の前記外部接続を介する前記サブストリームの前記転送をスケジューリングするようにさらに構成される、請求項１に記載のシステム。
【請求項８】
前記トラッカは、前記外部ピアで使用可能なサブストリームおよび各サブストリームのＩＳＰホップ・カウント（ＩＣＨ）に基づいて前記サブストリームの前記転送をスケジューリングし、前記ＩＣＨは、サブストリームがトラバースしたＩＳＰネットワークの個数を示す、請求項７に記載のシステム。
【請求項９】
前記第１ＩＳＰネットワークの前記局所ピアは、前記第１ＩＳＰネットワーク内で前記局所ピアに接続されている内部親ピアで使用可能なサブストリームおよびピア・ホップ・カウント（ＰＨＣ）に基づいて、前記内部接続を介する前記サブストリームの前記転送をスケジューリングし、前記ＰＨＣは、それぞれのサブストリームが単一のＩＳＰネットワーク内でトラバースした内部ピアの個数を示す、請求項１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、局所化されたオーバーレイ上で個々のインターネット・サービス・プロバイダ（ＩＳＰ）ネットワークのピアツーピア（Ｐ２Ｐ）ストリーミング・アプリケーション内のピアツーピア接続を制御するシステム及び方法に関する。
【背景技術】
【０００２】
ピアツーピア（Ｐ２Ｐ）ストリーミング・アプリケーションは、比較的少数のサーバが本質的価値をサービスまたはアプリケーションに提供する従来の集中化されたリソースではなく、ネットワーク内の参加者の間での種々の接続性およびネットワーク参加者の累積帯域幅を使用する。Ｐ２Ｐアプリケーションは、通常、たとえばオーディオ、ビデオ、および／またはディジタル・データなどのコンテンツを含むコンテンツ・ファイルをインターネットを介して共有するのに使用される。さらに、Ｐ２Ｐストリーミング・アプリケーションは、インターネットを介するライブ・マルチメディアのスケーラブル・ストリーミングに広く使用されてきた。Ｐ２Ｐストリーミングでは、参加するピアが、オーバーレイを形成し、オーバーレイの上でコンテンツを配送する。
【０００３】
従来のライブＰ２Ｐストリーミング・アプリケーションは、参加するピアの間のランダムな接続されたオーバーレイを使用する。たとえば、図１に、ランダム接続を含む従来のオーバーレイを示す。図１を参照すると、Ｐ２Ｐストリーミング・アプリケーション内の従来のシステム１００は、インターネット・サービス・プロバイダ（ＩＳＰ）ネットワークＡ（ＩＳＰ  Ａ）内およびＩＳＰネットワークＢ（ＩＳＰ  Ｂ）内の、ランダムに接続されたピア１０５を含むことができる。たとえば、ＩＳＰ  Ａ  １１０内のピア１０５のうちの１つが、ＩＳＰ  Ａ  １１０（たとえば、内部）内の別のピアに接続し、またはＩＳＰ  Ｂ  １２０（外部）内のピア１０５のうちの１つに接続することができる。ピア１０５の間の接続はランダムなので、接続を、内部接続またはＩＳＰ間接続（すなわち、外部接続）のいずれかとすることができる。用語ＩＳＰ間接続および外部接続は、交換可能な用語である。しかし、ＩＳＰ間接続のコストは、通常、内部接続より高い。ランダム・オーバーレイ・システムは、かなりの量のＩＳＰ間接続を使用するので、そのようなシステムを実施するコストは、相対的に高い可能性がある。
【０００４】
ピア１０５の間のＩＳＰ間接続を減らすために、従来の手法は、各ＩＳＰネットワーク内のオーバーレイ接続性の局所化に焦点を合わせた。Ｐ２Ｐ局所化は、個々のＩＳＰネットワークが、ＩＳＰ間接続を介するトラフィックを管理し、減らすために、そのポリシおよび他のＩＳＰネットワークとのビジネス関係を考慮しながら隣接ピアの選択を制御することを可能にする。
【０００５】
局所化の方法の１タイプは、選択された個数のピアを使用するように局所ピアに指示するオラクルを使用する。たとえば、新しい局所ピアは、アンダーレイに参加する候補ピア（または潜在的隣接物）のリストを受信するためにＰ２ＰアプリケーションのＰ２Ｐブートストラップ・ノードに連絡することができる。次に、局所ピアは、局所ピアに関連するオラクルに候補ピアのリストを送信する。オラクルは、候補ピアのリストをソートすることによって接続プリファレンスを適用し、ソートされたリストを局所ピアに返す。局所ピアは、好ましい隣接物への接続を開始するために、ソートされたリストを使用する。この方法では、ＩＳＰは、局所ピアがどのピアを介して接続を試みるのかのいくらかの制御を有する。しかし、Ｐ２Ｐトラフィックの局所化は、潜在的に、局所ピアの各隣接物でのコンテンツの多様性を減らすことによって、Ｐ２Ｐアプリケーションの性能に影響する可能性がある。
【０００６】
もう１つのタイプの局所化は、局所化されたオーバーレイを介するファイル・スウォーミング（ｆｉｌｅ  ｓｗａｒｍｉｎｇ）機構を使用する。スウォームベースの手法では、ビデオ・データは、複数のサブストリームに分割され、参加するピアは、ランダム・メッシュ・オーバーレイに編成され、スウォーミングは、各サブストリームの配送に使用される。親子関係が、接続されたピアの間に存在する。親としての各ピアは、サブストリームの可用性について子ピアに通知する。参加するピアのアクセス・リンク帯域幅を効果的に利用するために、ピアの着信度（ｉｎｃｏｍｉｎｇ  ｄｅｇｒｅｅ）および発信度（ｏｕｔｇｏｉｎｇ  ｄｅｇｒｅｅ）は、着信帯域幅および発信帯域幅に比例しなければならない。これは、すべての接続がほぼ同一の平均帯域幅を有することを暗示する。スウォーミング・コンテンツ配送は、親ピアによるプッシュ・コンテンツ報告を子ピアによるプル・コンテンツ要求と組み合わせる。各ピアは、その親ピアのすべてからコンテンツを同時に受信し、その子ピアのすべてにコンテンツを提供する。親ピアは、その新しいサブストリームの可用性を子ピアのすべてに漸進的に報告する。親ピアの間の使用可能なサブストリームを考慮して、各ピアは、帯域幅の利用および配送品質を最大にするために、どのブロックが各親ピアからプルされなければならないのかを決定するために、ブロック・スケジューリング方式を周期的に呼び出す。
【０００７】
しかし、スウォームベースの手法の従来の実施形態は、ファイル配送アプリケーションの緩和されたタイミング制約を利用し、このタイミング制約は、単一の要件すなわち、すべてのセグメントの配送のみを有する。その結果、ライブ・ビデオ・ストリームの再生が劇的に増え、「ライブ・ストリーミング」の主張が疑わしくなる（たとえば、数十秒、より大きいスウォームについては数分さえ）ことが、調査によって示された。
【発明の概要】
【課題を解決するための手段】
【０００８】
本発明は、局所化されたオーバーレイ上で個々のインターネット・サービス・プロバイダ（ＩＳＰ）ネットワークのピアツーピア（Ｐ２Ｐ）ストリーミング・アプリケーション内のピアツーピア接続を制御するシステムおよび方法に関する。
【０００９】
このシステムは、第１ＩＳＰネットワークの局所ピアの中でエッジ・ピアを選択するように構成された第１ＩＳＰに局所的なトラッカを含むことができる。選択されるエッジ・ピアは、第１ＩＳＰネットワークへまたはこれからサブストリームを転送するために第１ＩＳＰネットワークの外側のピアへの外部接続を有し、エッジ・ピアとして選択されない局所ピアは、局所化されたオーバーレイ上でサブストリームを転送するために第１ＩＳＰネットワーク内の他の局所ピアへの内部接続を有する。トラッカは、帯域幅に基づいてエッジ・ピアを選択することができる。さらに、トラッカは、既存エッジ・ピアがＰ２Ｐストリーミング・アプリケーションから離脱する時に、エッジ・ピアを選択することができる。代替案では、トラッカは、エッジ・ピアの個数が第１しきい値未満であるかどうかに基づいてエッジ・ピアを選択することができる。
【００１０】
もう１つの実施形態では、トラッカは、第１タイプのエッジ・ピアおよび第２タイプのエッジ・ピアを選択するように構成される。第１タイプのエッジ・ピアは、着信外部接続を管理し、第２タイプのエッジ・ピアは、発信外部接続を管理する。
【００１１】
このシステムは、エッジ・ピアからのアナウンス・メッセージに応答して外部接続を確立するために、エッジ・ピアに潜在的外部ピアのリストを提供するように構成されたセッションレベル・トラッカをさらに含む。エッジ・ピアだけが、第１ＩＳＰネットワークの外側の外部ピアに可視の局所ピアである。また、セッションレベル・トラッカは、局所トラッカのリストを提供するようにさらに構成され得る。
【００１２】
一実施形態では、トラッカは、外部ピアと第１ＩＳＰネットワークのエッジ・ピアとの間の外部接続を介するサブストリームの転送をスケジューリングするようにさらに構成される。トラッカは、外部ピアで使用可能なサブストリームおよび各サブストリームのＩＳＰホップ・カウント（ＩＣＨ）に基づいてサブストリームの転送をスケジューリングする。ＩＣＨは、サブストリームがトラバースしたＩＳＰネットワークの個数を示す。
【００１３】
第１ＩＳＰネットワークの局所ピアは、内部親ピアで使用可能なサブストリームおよびピア・ホップ・カウント（ＰＨＣ）に基づいて、内部接続を介するサブストリームの転送をスケジューリングする。ＰＨＣは、それぞれのサブストリームが単一のＩＳＰネットワーク内でトラバースした内部ピアの個数を示す。局所ピアは、最小のＰＨＣカウント値を有するサブストリームの転送をスケジューリングする。
【００１４】
各サブストリームは、（１）それぞれのサブストリームがトラバースしたＩＳＰネットワークの個数を示すＩＳＰホップ・カウント（ＩＣＨ）、（２）それぞれのサブストリームが単一のＩＳＰネットワーク内でトラバースした内部ピアの個数を示すピア・ホップ・カウント（ＰＨＣ）、および（３）それぞれのサブストリームがＩＳＰネットワークにかかわりなくトラバースしたピアの総数を示す総ホップ・カウント（ＯＨＣ）を含む。
【００１５】
この方法は、第１ＩＳＰネットワークに局所的なトラッカによって、第１ＩＳＰネットワークの局所ピアの中でエッジ・ピアを選択することを含む。選択されるエッジ・ピアは、第１ＩＳＰネットワークへまたはこれからサブストリームを転送するために第１ＩＳＰネットワークの外側のピアへの外部接続を有し、エッジ・ピアとして選択されない局所ピアは、局所化されたオーバーレイ上でサブストリームを転送するために第１ＩＳＰネットワーク内の他の局所ピアへの内部接続を有する。選択するステップは、帯域幅に基づいてエッジ・ピアを選択する。さらに、選択するステップは、既存エッジ・ピアがＰ２Ｐストリーミング・アプリケーションから離脱する時に、エッジ・ピアを選択する。代替案では、選択するステップは、エッジ・ピアの個数が第１しきい値未満であるかどうかに基づいてエッジ・ピアを選択する。
【００１６】
もう１つの実施形態では、選択するステップは、第１タイプのエッジ・ピアおよび第２タイプのエッジ・ピアを選択する。第１タイプのエッジ・ピアは、着信外部接続を管理し、第２タイプのエッジ・ピアは、発信外部接続を管理する。
【００１７】
この方法は、エッジ・ピアからのアナウンス・メッセージに応答して外部接続を確立するために、セッションレべル・トラッカによって、エッジ・ピアに潜在的外部ピアのリストを提供することをさらに含む。この方法は、トラッカによって、外部ピアと第１ＩＳＰネットワークのエッジ・ピアとの間の外部接続を介するサブストリームの転送をスケジューリングすることをさらに含む。スケジューリングするステップは、外部ピアで使用可能なサブストリームおよび各サブストリームのＩＳＰホップ・カウント（ＩＣＨ）に基づいてサブストリームの転送をスケジューリングする。ＩＣＨは、サブストリームがトラバースしたＩＳＰネットワークの個数を示す。
【００１８】
この方法は、第１ＩＳＰネットワークの局所ピアによって、内部親ピアで使用可能なサブストリームおよびピア・ホップ・カウント（ＰＨＣ）に基づいて、内部接続を介するサブストリームの転送をスケジューリングすることをさらに含む。ＰＨＣは、それぞれのサブストリームが単一のＩＳＰネットワーク内でトラバースした内部ピアの個数を示す。
【００１９】
例の実施形態は、本明細書で下で与えられる詳細な説明および添付図面からより十分に理解されるようになり、ここで、同様の要素は、同様の符号によって表され、詳細な説明および添付図面は、例示として与えられるのみであり、したがって、本発明を限定しない。
【図面の簡単な説明】
【００２０】
【図１】ランダム接続を示す従来のオーバーレイを示す図である。
【図２】本発明の実施形態によるピアツーピア接続を制御するシステムを示す図である。
【図３】本発明の実施形態による局所トラッカの構造の例を示す図である。
【図４Ａ】本発明の実施形態による２ティア・スケジューリング方式に従うピアツーピア接続の制御を示す流れ図である。
【図４Ｂ】本発明の実施形態によるＰ２Ｐストリーミング・アプリケーション内のビデオ・ストリームの構造を示す図である。
【図５】本発明の実施形態によるＩＳＰ間スケジューリングの例を示す図である。
【発明を実施するための形態】
【００２１】
本発明のさまざまな実施形態を、これから添付図面を参照してより十分に説明するが、添付図面には、本発明のいくつかの実施形態が示されている。同様の符号は、図の説明全体を通じて同様の要素を指す。
【００２２】
本明細書で使用される時に、単数形「ａ」、「ａｎ」、および「ｔｈｅ」は、文脈がそうではないことを明瞭に示さない限り、複数形をも含むことが意図されている。さらに、用語「ｃｏｍｐｒｉｓｅｓ」、「ｃｏｍｐｒｉｓｉｎｇ」、「ｉｎｃｌｕｄｅｓ」、および／または「ｉｎｃｌｕｄｉｎｇ」は、本明細書で使用される時に、述べられた特徴、整数、ステップ、動作、要素、および／またはコンポーネントの存在を指定するが、１つまたは複数の他の特徴、整数、ステップ、動作、要素、コンポーネント、および／またはその群の存在または追加を除外しないことを理解されたい。
【００２３】
いくつかの代替実施形態で、記された機能／行為が図に記された順序から外れて発生してもよいことにも留意されたい。たとえば、連続して示される２つの図が、実際には、用いられる機能性／行為に応じて、実質的に同時に実行されてもよく、あるいは、時々、逆の順序で実行されてもよい。
【００２４】
本発明の諸部分および対応する詳細な記述は、ソフトウェアすなわち、コンピュータ・メモリ内のデータ・ビットに対する動作のアルゴリズムおよび記号表現に関して提示される。これらの記述および表現は、当業者がそれによって彼らの作業の実質を他の当業者に効率的に伝える記述および表現である。アルゴリズムは、この用語が本明細書で使用される時に、および一般に使用される時に、所望の結果につながるステップの自己完結的シーケンスと考えられる。ステップは、物理的量の物理的操作を必要とするステップである。必ずではないが通常、これらの量は、格納、転送、組合せ、比較、および他の操作が可能な光信号、電気信号、または磁気信号の形をとる。時々、主に一般的な使用の理由から、これらの信号をビット、値、要素、記号、文字、項、数、または類似物と呼ぶことが便利であることがわかっている。
【００２５】
しかし、上記および類似する用語のすべてが、適切な物理的量に関連付けられなければならず、単にこれらの量に適用される便利なラベルであることに留意されたい。そうではないと具体的に述べられない限り、または議論から明白であるように、「ｓｅｌｅｃｔｉｎｇ（選択）」、「ｐｒｏｖｉｄｉｎｇ（提供）」、「ｄｅｔｅｒｍｉｎｉｎｇ（判定）」、「ｍａｎａｇｉｎｇ（管理）」、「ｄｉｓｐｌａｙｉｎｇ（表示）」、または類似物などの用語は、コンピュータ・システムのレジスタおよびメモリ内の物理的電子量として表されたデータを操作し、コンピュータ・システム・メモリもしくはレジスタまたは他のそのような情報記憶デバイス、情報伝送デバイス、もしくは情報表示デバイス内の物理的量として同様に表された他のデータに変換する、コンピュータ・システムまたは類似する電子コンピューティング・デバイスのアクションおよびプロセスを指す。
【００２６】
また、本発明のソフトウェア実施される諸態様が、通常は、ある形のプログラム記憶媒体上で符号化され、またはあるタイプの伝送媒体を介して実施されることに留意されたい。プログラム記憶媒体は、磁気（たとえば、フロッピ・ディスクまたはハード・ドライブ）または光学（たとえば、コンパクト・ディスク読取り専用メモリすなわち「ＣＤ  ＲＯＭ」）とすることができ、読取り専用またはランダム・アクセスとすることができる。同様に、伝送媒体は、より対線、同軸ケーブル、光ファイバ、または当技術分野で既知のある他の適切な伝送媒体とすることができる。本発明は、任意の所与の実施態様のこれらの態様によって限定はされない。
【００２７】
本発明を、これから、添付図面を参照して説明する。さまざまな構造、システム、およびデバイスが、説明のみのために、また、当業者に周知の詳細で本発明を不明瞭にすることがないように、図面では概略的に示されている。それでも、添付図面は、本発明の例示的な例を記述し、説明するために含まれる。本明細書で使用される単語および句は、当業者によるこれらの単語および句の理解と一貫する意味を有すると理解され、解釈されなければならない。用語または句の特殊な定義すなわち、当業者によって理解される通常の慣例的な意味とは異なる定義が、本明細書での用語または句の一貫した使用によって暗示されることは、意図されていない。用語または句が、特殊な意味すなわち、当業者によって理解されるものとは異なる意味を有することが意図される範囲で、そのような特殊な定義は、用語または句の特殊な定義を直接に明確に提供する定義的な形で本明細書で特に示される。
【００２８】
本発明の例の実施形態は、局所化されたオーバーレイを介して個々のインターネット・サービス・プロバイダ（ＩＳＰ）ネットワークのピアツーピア（Ｐ２Ｐ）ストリーミング・アプリケーション内のピアツーピア接続を制御するシステムおよび方法に関する。本発明の実施形態は、たとえば高品質ビデオ・ストリーミングを配送するためのスウォームベースの手法について外部接続の個数を制限し、スケジューリング方式を改訂することによって、個々のＩＳＰネットワークの外部トラフィックを効果的に制御する。対照的に、オーバーレイ局所化での基本的前提は、ピアが正しい個数の親ピアを識別できる限り、ピアが親ピアの選択におけるプリファレンスを全く有しないことである。同一ＩＳＰネットワーク内の他のピアを発見し、これに接続するように同一ＩＳＰネットワーク内のピアに指示することによって、各ＩＳＰネットワークの外部（着信および発信）接続の個数を減らすことができ、これは、Ｐ２Ｐアプリケーションに関連する外部トラフィック（たとえば、コスト）を比例して減らす。
【００２９】
図２に、本発明の実施形態による個々のＩＳＰネットワークのＰ２Ｐストリーミング・アプリケーション内のＰ２Ｐ接続を制御するシステム２００を示す。図２のシステム２００は、２つのＩＳＰネットワークすなわちＩＳＰ  ＡおよびＩＳＰ  Ｂと、ＩＳＰ間接続のために外部ピアを発見するセッションレベル・トラッカ１２０と、Ｐ２Ｐストリーミング・アプリケーション内でインターネットを介して接続されたＩＳＰ  Ａ内のピア１０５およびＩＳＰ  Ｂ内のピア１２５とを示す。Ｐ２Ｐストリーミング・アプリケーションは、ピアの間で、オーディオ、ビデオ、および／またはディジタル・データなどのコンテンツを含むコンテンツ・ファイルをインターネットを介して共有するのに使用される。さらに、Ｐ２Ｐストリーミング・アプリケーションは、インターネットを介するライブ・マルチメディアのストリーミングに使用される。
【００３０】
ピア１０５およびピア１２５は、パーソナル・コンピュータ、無線電話機、または任意の他の類似するデバイスなど、Ｐ２Ｐアプリケーションを動作させるように構成された任意のタイプのシステムとすることができる。ピア１０５は、ＩＳＰ  Ａに局所的であり、ピア１２５は、ＩＳＰ  Ｂに局所的である。あるＩＳＰネットワークに局所的なピアを、局所ピアと称する場合がある。図２は、有限の個数のピアを示すが、あるＩＳＰ内のピアの個数は、Ｐ２Ｐアプリケーションに関連するトラフィックに応じて継続的に変化する。さらに、ＩＳＰ  Ａは、エッジ・ピア１１０を含み、エッジ・ピア１１０は、ＩＳＰ  Ａに局所的なピア１０５でもあるが、下で説明するようにエッジ・ピアとして選択されている。
【００３１】
ＩＳＰ  Ａは、局所トラッカ１１５を含み、局所トラッカ１１５には、Ｐ２Ｐネットワークに参加するＩＳＰ  Ａに局所的なピア（たとえば、ピア１０５および１１０）が、それ自体をアナウンスする。局所トラッカ１１５と各ピア１０５および１１０との間の接続は、局所トラッカ１１５と各ピア１０５および１１０との間の点線の接続線によって示されている。応答として、局所トラッカ１１５は、潜在的な接続に関する候補ピアのリストを各ピア１０５および１１０に返す。さらに、局所トラッカ１１５は、ＩＳＰ  Ａの着信外部接続および発信外部接続の総数を判定し、集計着信帯域幅が少なくともストリーム帯域幅と等しいことを保証するように構成される。
【００３２】
ＩＳＰ  Ａ内では、ピア１０５および１１０の間の実線が、Ｐ２Ｐデータの転送（内部）を示す。また、インターネットからエッジ・ピア１１０への実線は、下でさらに説明される、外部ピアまたはコンテンツ・プロバイダ（外部）などの外側のソースとのＰ２Ｐデータの転送を示す。同様に、ＩＳＰ  Ｂ内では、実線が、Ｐ２Ｐデータの転送を示す。しかし、ＩＳＰ  Ｂ内では、各ピア１２５が、内部的および外部的にＰ２Ｐを転送する。その結果、Ｐ２Ｐ外部制御が、ＩＳＰ  Ｂ内のピア１２５の外部接続のすべてについて要求される（点線の矢印によって示されるように）が、Ｐ２Ｐ外部制御が、ＩＳＰ  Ａ内のエッジ・ピア１１０の接続についてのみ要求される（点線の矢印によって示されるように）。
【００３３】
２つのＩＳＰネットワークだけが図２に示されているが、本発明の例の実施形態は、任意の個数のＩＳＰネットワークを包含する。ＩＳＰ  Ａとは異なって、ＩＳＰ  Ｂは局所化を使用しない。そうではなく、ＩＳＰ  Ｂ内のすべてのピア１２５は、ＩＳＰ  Ａ内のピア１０５への外部接続のためにセッションレベル・トラッカ１２０に連絡する。図２のＩＳＰ  Ｂ内のＰ２Ｐネットワークは、局所化なしのＩＳＰとして図示されているが、ＩＳＰ  Ｂが局所化を含んでもよい。言い替えると、局所トラッカ１１５は、ＩＳＰ  Ａネットワークの外部の、局所化を含むまたは局所化を含まない（図２に示されているように）ＩＳＰネットワークの一部であるピアへの外部接続を制御することができる。
【００３４】
図３に、本発明の実施形態による局所トラッカ１１５の構造の例を示す。局所トラッカ１１５は、中央処理装置（ＣＰＵ）３２１、ランダム・アクセス・メモリ（ＲＡＭ）３２２、読取り専用メモリ（ＲＯＭ）３２６、ハード・ディスク・ドライブ３２７、およびネットワーク・インターフェース３２８を含む。局所トラッカ１１５は、当業者に周知の、図３に示されたもの以外の他のコンポーネントを含むこともできる。ＣＰＵ  ３２１、ＲＡＭ  ３２２、ＲＯＭ  ３２６、ハード・ディスク・ドライブ３２７、およびネットワーク・インターフェース３２８は、バスを介してお互いと通信する。ハード・ディスク・ドライブ３２７は、当業者に周知の形で動作する。
【００３５】
ＲＡＭ  ３２２は、ＣＰＵ  ３２１が局所トラッカ１１５の動作を実行するための命令を提供するオペレーティング・システム３２３を格納することができる。任意の汎用オペレーティグ・システムを使用することができる。ネットワーク・インターフェース・ユニット３２８は、ＣＰＵ  ３２１が、ＴＣＰ／ＩＰプロトコルを含むさまざまな通信プロトコルと共に使用するために構築された、インターネットまたはある他の通信ネットワークと通信することを可能にする。ネットワーク・インターフェース・ユニット３２８は、たとえば、トランシーバ（１つまたは複数）、送受信デバイス（１つまたは複数）、および／またはネットワーク・インターフェース・カード（ＮＩＣ）（１つまたは複数）を含むことができる。ネットワーク・インターフェース・ユニット３２８は、インターネット、ピア１０５、１１０、および１２５、セッションレベル・トラッカ１２０、ならびに局所トラッカ１１５の機能を実行する任意の他のデバイスと通信するように構成される。
【００３６】
また、ＲＡＭ  ３２２は、１つまたは複数のデータ・ストレージ・ユニットを含むことができ、このデータ・ストレージ・ユニットを局所トラッカ１１５によって利用して、たとえば、とりわけアプリケーションならびにデータベース情報を格納することができる。たとえば、ＲＡＭ  ３２２は、下で説明される局所トラッカ１１５の諸機能を実行するのに必要なアプリケーションを格納することができる。
【００３７】
図４Ａに、本発明の実施形態による２ティア・スケジューリング方式に従うピアツーピア接続の制御の流れ図を示す。局所トラッカ１１５は、外部接続の個数を制限することによってＩＳＰ  Ａの外部トラフィックを制御する。
【００３８】
具体的には、Ｓ４１０を参照すると、局所トラッカ１１５は、ＩＳＰ  Ａの局所ピアの中からエッジ・ピア１１０すなわちピアＡ１およびピアＡ２を選択するように構成される。選択されたエッジ・ピア１１０は、ＩＳＰ  Ａにビデオ・ストリームのサブストリームを配送するために、ＩＳＰ  Ａネットワークの外側のピア（たとえば、ピア１２５）への外部接続を維持するが、ＩＳＰ  Ａの局所ピアは、ＩＳＰ  Ａの局所化されたオーバーレイ上でサブストリームを配送するためにＩＳＰ  Ａ内の他の局所ピアへの内部接続を維持する。言い替えると、エッジ・ピア１１０は、外部接続を有し、ＩＳＰ  Ａの内部のピア（たとえば、ピア１０５）は、外部接続を有しない。局所トラッカ１１５によって行われる接続判断は、エッジ・ピア１１０の帯域幅に基づくものとすることができる。たとえば、比較的高い帯域幅を有するＩＳＰ  Ａに局所的なピアは、エッジ・ピア１１０として選択されるのに好ましい。しかし、選択判断は、潜在的なエッジ・ピアの帯域幅だけに限定されるのではなく、他のタイプの判断基準を、そのような選択判断を行うための基礎として使用することができる。本発明のため、局所トラッカ１１５は、ＩＳＰ  Ａに局所的なピアのすべてより少数をエッジ・ピア１１０として選択する。エッジ・ピアの個数は、１以上の、ＩＳＰ  Ａに局所的なピアの総数より小さい任意の整数とすることができる。さらに、エッジ・ピアがＰ２Ｐアプリケーションから離脱した後に、局所トラッカ１１５は、帯域幅または上で説明した任意の他の判断基準に基づいて、ＩＳＰ  Ａに局所的な別のピアをエッジ・ピアとして選択することができる。
【００３９】
別の実施形態では、局所トラッカ１１５は、ＩＳＰネットワーク内のエッジ・ピアの個数を判定し、エッジ・ピアの個数が第１しきい値未満であるかどうかに基づいてエッジ・ピアを選択するように構成される。第１しきい値は、ピアの所望の（または、代替案では所定の）個数とすることができる。ピアの所望の個数は、１または１より大きい任意の整数など、ピアの任意の個数とすることができる。
【００４０】
別の実施形態では、局所トラッカ１１５は、局所ピアおよび通常のピアまたはエッジ・ピアのいずれかとしてのその局所ピアの状況を追跡する。たとえば、新しいピアがＩＳＰ  Ａ内でＰ２Ｐアプリケーションに参加する時に、局所トラッカ１１５は、エッジ・ピアおよび局所ピアの個数を新しいピアに送信する。新たに参加するピアは、局所トラッカ１１５によって報告されたエッジ・ピアの個数に基づいて、エッジ・ピアになると決断する。たとえば、エッジ・ピアの個数が第１しきい値未満である場合に、ピアは、エッジ・ピアになる。
【００４１】
エッジ・ピア１１０が選択された後に、エッジ・ピア１１０は、下で述べるように、外部親ピアを入手し（Ｓ４２０）、外部ピアに接続し（Ｓ４３０）、ＩＳＰ間スケジューリング機構に従ってコンテンツ情報を交換し始める（Ｓ４４０）。また、局所ピア（たとえば、ピア１０５および１１０）は、ＩＳＰ  Ａネットワーク内の他の局所ピアに接続し（Ｓ４５０）、ＩＳＰ内スケジューリング機構に従ってコンテンツ情報を交換し始める（Ｓ４６０）。局所化されたオーバーレイ上のエッジ・ピア１１０または局所ピア１０５のいずれかへのＩＳＰ  Ａネットワークのピアの分類は、たとえば、ＩＳＰ内スケジューリングおよびＩＳＰ間スケジューリングに従って実行されるビデオ・ストリームの配送のための２ティア・スケジューリング機構を提供する。図４Ａの流れ図は、ステップのシーケンスを示すが、これらのステップは、順序から外れてまたは同時に行うことができる。たとえば、通常、ＩＳＰ内スケジューリングは、ＩＳＰ間スケジューリングと同時に実行される。
【００４２】
Ｓ４２０では、セッションレベル・トラッカ１２０は、エッジ・ピア１１０からのアナウンス・メッセージに応答して外部接続を確立するために潜在的な外部ピア（たとえば、ＩＳＰ  Ｂ内のピア１２５）のリストを提供するように構成される。言い替えると、エッジ・ピア１１０は、セッションレベル・トラッカ１２０を介して外部ピア（たとえば、ＩＳＰ  Ｂ内のピア１２５）を発見する。エッジ・ピア１１０は、アナウンス・メッセージを介してセッションレベル・トラッカ１２０にシグナリングし、返報として、潜在的な外部ピアのリストを受信する。潜在的な外部ピアのリストに基づいて、エッジ・ピア１１０は、外部ピアのサブセットに接続する（Ｓ４３０）。選択されたエッジ・ピア１１０だけが、それ自体をセッションレベル・トラッカ１２０にアナウンスするので、エッジ・ピア１１０だけが、ＩＳＰ  Ａネットワークの外側の外部ピア（たとえば、ＩＳＰ  Ｂ内のピア１２５）に可視の局所ピアである。したがって、エッジ・ピア１１０以外のピアは、着信クロスＩＳＰ接続要求を受信せず、これは、着信接続の個数を効果的に制限し、制御する。
【００４３】
別の実施形態では、局所トラッカ１１５は、外部着信接続要求と外部発信接続要求との間で区別するために、２つの異なるクラスのエッジ・ピア１１０を選択するように構成される。たとえば、局所トラッカ１１５は、着信外部接続要求を管理する第１タイプのエッジ・ピアと発信外部接続要求を管理する第２タイプのエッジ・ピアとを選択する。局所トラッカ１１５によって選択される第１タイプのエッジ・ピアは、ＩＳＰ  Ａネットワークの外側のピア（たとえば、ピア１２５）からの着信接続を受け入れ、親ピアとしてＩＳＰ  Ａネットワークの外側のピアにサービスする責任を負う。第２タイプのエッジ・ピアは、外部親ピアからＩＳＰ  Ａネットワーク（たとえば、局所ピア１０５および１１０）にコンテンツ情報を持ってくるために外部親ピアに接続する責任を負う。
【００４４】
一実施形態では、第１タイプのエッジ・ピアは、それ自体をセッションレベル・トラッカ１２０にアナウンスし、したがって、第１タイプのエッジ・ピアを外部ピアに可視にする。第２タイプのエッジ・ピアは、セッションレベル・トラッカ１２０に連絡し、他のＩＳＰネットワークに第１タイプのエッジ・ピアのリストを要求する。
【００４５】
別の実施形態では、局所化対応ＩＳＰネットワーク（たとえば、ＩＳＰ  Ａ）からのピアは、それ自体をセッションレベル・トラッカ１２０にアナウンスしない。そうではなく、ＩＳＰ  Ａの局所トラッカ１１５および他の局所化対応ＩＳＰネットワークの局所トラッカが、それら自体をセッションレベル・トラッカ１２０にアナウンスする。外部エッジ・ピア（または局所化されないＩＳＰネットワーク内の、たとえばＩＳＰ  Ｂからの通常のピア）が、セッションレベル・トラッカ１２０に連絡する時に、外部エッジ・ピアまたは通常のピアは、その要求に対するセッションレベル・トラッカの応答内で局所トラッカを識別する。たとえば、局所トラッカのリストが、ＩＳＰ  Ａネットワークの局所トラッカ１１５を含む場合には、ＩＳＰ  Ｂからの要求するピアは、その後、ＩＳＰ  Ａの局所トラッカ１１５に連絡する。その後、局所トラッカ１１５は、発信接続の個数がしきい値未満である場合に、ランダムに選択された／先験的に選択された局所ピアに要求をリダイレクト／転送する。この場合に、外部ピアは、局所ピアに接続し、この局所ピアは、効果的に第２タイプのエッジ・ピアになる。下で述べる実施形態は、単純さのために、第１タイプのエッジ・ピアと第２タイプのエッジ・ピアとの間の区別なしでエッジ・ピア１１０に言及する。しかし、下で述べる実施形態は、第１タイプのエッジ・ピアおよび第２タイプのエッジ・ピアと共に動作することもできる。
【００４６】
Ｓ４４０では、エッジ・ピア１１０は、下で述べるように、ＩＳＰ間スケジューリング機構に従って、接続された外部ピアへ／から中継されるビデオ・ストリームに関する情報を交換する。
【００４７】
Ｓ４５０では、エッジ・ピア１１０になるために選択されなかった局所ピア１０５が、ＩＳＰ  Ａネットワークの局所ピアだけに接続する。たとえば、上で説明したように、新しいピアがＩＳＰ  Ａ内のＰ２Ｐネットワークに参加する時に、新しいピアは、アナウンスメント・メッセージを介して局所トラッカ１１５にシグナリングする。返報として、新たに参加するピアは、潜在的ピアのリストを受信する。その後、新たに参加する局所ピアは、潜在的ピアの受信されたリストに基づいて、ＩＳＰ  Ａネットワーク内の他の局所ピアに接続する。Ｓ４６０では、局所ピア１０５が、下でＩＳＰ間スケジューリング機構の後に述べるＩＳＰ内スケジューリング機構に従って、ＩＳＰ  Ａネットワーク内の他の局所ピアへ／から中継されるビデオ・データに関する情報を交換する。
【００４８】
本発明の実施形態は、２つのレベルすなわちソースから個々のＩＳＰネットワークへ（ＩＳＰ間スケジューリングを介する）および各着信エッジ・ピア１１０からすべての内部ピアへ（ＩＳＰ内スケジューリングを介する）スケジューリング方式を提供する。ＩＳＰ間スケジューリングは、たとえば外部ピアからＩＳＰネットワークへ中継されるビデオ・ストリームのサブストリームの配送のスケジューリングに関し、ここで、ＩＳＰネットワークは、単一のピアとして表される。言い替えると、ＩＳＰ間スケジューリングは、個々のＩＳＰネットワークへの最高品質ビデオ・ストリームの配送に焦点を合わせたものである。その結果、ＩＳＰ間スケジューリングは、外部接続だけに関係し、したがって、エッジ・ピア１１０で実施される。対照的に、ＩＳＰ内スケジューリングは、エッジ・ピア１１０から個々のＩＳＰネットワーク内のすべての内部ピアへの各サブストリームの配送に焦点を合わせたものである。ＩＳＰ内スケジューリングは、各ＩＳＰ内の内部接続を管理する責任だけを負い、内部親ピアを有するすべてのピアによって実施される。ＩＳＰ間スケジューリング・レベルとＩＳＰ内スケジューリング・レベルとの両方について効果的な配送を達成するために、ビデオ・ストリームは、複数のサブストリームに分割される。
【００４９】
図４Ｂに、本発明の実施形態によるＰ２Ｐストリーミング・アプリケーション内のビデオ・ストリーム３００の構造を示す。ビデオ・ストリーム３００は、ｎ個のサブストリームに分割され、ここで、ｎは、１以上の任意の整数である。各サブストリームは、ＩＳＰホップ・カウント（ＩＨＣ）、ピア・ホップ・カウント（ＰＨＣ）、および総ホップ・カウント（ＯＨＣ）という３つのカウンタを担持する。ＩＨＣカウンタは、サブストリームがトラバースしたＩＳＰネットワークの個数を記録する。ＰＨＣカウンタは、サブストリームが単一のＩＳＰネットワーク内でトラバースした内部ピアの個数を記録する。ＰＨＣカウンタは、サブストリームがそこでＩＳＰネットワークに入る対応するエッジ・ピアによってリセットされる。ＯＨＣカウンタは、サブストリームがトラバースしたピア（そのＩＳＰに関わりなく）の総数を記録する。
【００５０】
図５に、本発明の実施形態によるＩＳＰ間スケジューリングの例を示す。図５は、２つのサブストリームＳ１およびＳ２が、ソース５０１から６つのＩＳＰネットワーク５０２（ＩＳＰ１、ＩＳＰ２、ＩＳＰ３、ＩＳＰ４、ＩＳＰ５、およびＩＳＰ６）のグループに配送される例を示す。各ＩＳＰネットワーク５０２ならびに個々のピアは、２の着信度および発信度を有する。各ＩＳＰネットワーク５０２は、そのそれぞれのＩＳＰネットワークに局所的な複数のピアを含む。
【００５１】
ＩＳＰ１内のピアＡは、ＩＳＰ３内のピアＣの親ピアと考えられ、ＩＳＰ１内のピアＢは、ＩＳＰ４内のピアＤの親ピアと考えられる。ＩＳＰ３内のピアＣおよびＩＳＰ４内のピアＤは、エッジ・ピア１１０である。ＩＳＰ１内のピアＡを参照すると、２つのサブストリームＳ１およびＳ２が、ＩＳＰ３内のピアＣから使用可能である。この特定の例では、ピアＡでのサブストリームＳ１とＳ２との両方が、そのそれぞれのＯＨＣ値およびＩＨＣ値を示す。サブストリームＳ１について、ＯＨＣ＝７かつＩＨＣ＝１である。サブストリームＳ２について、ＯＨＣ＝５かつＩＨＣ＝３である。サブストリームＳ１のＩHCは、ＩＳＰ１がこのサブストリームをソース５０１から直接に受信するので、１である。その一方で、サブストリームＳ２は、ＩＳＰ１内のピアＡに到着するために、２つ多いＩＳＰ（たとえば、ＩＳＰ  ２およびＩＳＰ  ５）をトラバースした。したがって、ピアＡのサブストリーム２のＩＨＣは、３である。さらに、ピアＢでは、サブストリームＳ１とＳ２との両方が、そのそれぞれのＯＨＣ値およびＩＨＣ値を示す。サブストリームＳ１について、ＯＨＣ＝６かつＩＨＣ＝１である。サブストリームＳ２について、ＯＨＣ＝５かつＩＨＣ＝３である。
【００５２】
すべてのサブストリームが各ＩＳＰに配送されることを保証するために、子ピア（たとえば、ＩＳＰ３内のピアＣおよびＩＳＰ４内のピアＤ）がそのそれぞれの親ピア（たとえば、ＩＳＰ１内のピアＡおよびＩＳＰ１内のピアＢ）からどのサブストリームをプルするのかをスケジューリングするために、局所トラッカ１１５は、周期的にまたはエッジ・ピアの離脱の後に、対応する外部親ピアで使用可能なサブストリームならびに各サブストリームの関連するＩＨＣを入手するためにすべてのエッジ・ピア１１０をポーリングすることによって、調整を実行する。この場合に、ＩＳＰ３の局所トラッカ１１５は、ピアＡでのサブストリームＳ１およびＳ２に関する識別する情報およびピアＡでのサブストリームのそれぞれのＩＨＣ値を入手する。ＩＳＰ３の局所トラッカ１１５も、ピアＡ以外のＩＳＰ３のエッジ・ピアでの他のサブストリームに関する識別する情報を入手する。
【００５３】
局所トラッカ１１５が、それぞれの親ピアでのサブストリームの可用性およびＩＨＣ値に関する情報をエッジ・ピアから受信した後に、局所トラッカ１１５は、サブストリームのすべてがＩＳＰに配送されることを保証するために、エッジ・ピアへのサブストリームの配送を調整する。局所トラッカ１１５の調整機構は、すべてのサブストリームがＩＳＰに配送されることを保証するためにエッジ・ピアへのサブストリームの配送を調整する任意の周知の手段を使用することができる。
【００５４】
対照的に、ＩＳＰ内スケジューリングは、各サブストリームをその対応するエッジ・ピアからＩＳＰネットワーク内のすべての他のピアに配送する。各内部ピアは、使用可能なサブストリームおよび内部親ピアと各親ピアでのＰＨＣ値とに基づいて、異なるサブストリームを独立にスケジューリングする。言い替えると、各内部ピアは、各親でのＰＨＣ値と一緒に使用可能なサブストリームを検討し、最小のＰＨＣ（たとえば、ＩＳＰへの入口点からの最小距離）を有するサブストリームを選択する。最小ＰＨＣを有する複数のサブストリームが特定の親ピアで使用可能である場合には、より短い総ホップ・カウント（ＯＨＣ）を有するサブストリームが選択される。このスケジューリング方式は、各内部ピアで周期的に（たとえば、Δ秒ごとに１回）呼び出される。
【００５５】
ＩＳＰ内スケジューリングおよびＩＳＰ間スケジューリングを、上ではすべての接続が同一の帯域幅を有するという仮定の上で説明した。しかし、内スケジューリングと間スケジューリングとの両方が、参加するピアの動力学（または動揺）と、異なる接続にまたがる輻輳制御された帯域幅の短期変動および長期変動とに対処しなければならない場合がある。
【００５６】
別の実施形態では、各エッジ・ピアは、そのエッジ・ピアが帯域幅しきい値を越える帯域幅を有する場合に、指定されないサブストリームを識別する。たとえば、指定されないサブストリームは、接続に割り当てられていないサブストリームであり、これは、指定されないサブストリームが、対応するエッジ・ピアまたは通常のピアによって要求されたことがないことを暗示する。その一方で、各エッジ・ピアは、指定されたサブストリームと呼ばれる特定のサブストリームを、その外部親ピアに要求する責任を負う。指定されないサブストリームの中で、エッジ・ピアは、これらのサブストリームの、隣接物内で使用可能ではないブロックを識別し、余分な帯域幅がある場合には、使用可能ではないブロックをその外部親ピアに要求する。
【図１】
0005591350.tif 000002
【図２】
0005591350.tif 000003
【図３】
0005591350.tif 000004
【図４Ａ】
0005591350.tif 000005
【図４Ｂ】
0005591350.tif 000006
【図５】
0005591350.tif 000007