(57)【要約】  加入コントリビューション認識ピアのピアツーピアネットワークへの加入を許可する方法を説明する。該方法は、システムリソースインデックスを含む複数のシステムパラメータを加入ピアで受信するステップと、加入ピアの有権利着信度数の値を計算するステップとを含み、計算された有権利着信度数は、システムリソースインデックスの値を反映している。また、コントリビューション認識ピアツーピアネットワークのためのブートストラップノードを説明する。該ブートストラップノードは、プロセッサデバイスと、プロセッサデバイスに結合されたネットワークインタフェースデバイスとを含み、該ネットワークインタフェースデバイスは、通信ネットワークに結合されるように適合され、プロセッサデバイスは、潜在的な親ピアの識別情報を求める要求を通信ネットからネットワークインタフェースデバイスを介して受信するように適合され、その一方で、プロセッサデバイスは、複数のデバイスの識別値およびシステムパラメータを用いて応答するように適合される。
2010515113.tif 000002
【特許請求の範囲】
【請求項１】
加入コントリビューション認識ピアのピアツーピアネットワークへの加入を許可する方法であって、
システムリソースインデックスを含む複数のシステムパラメータを、加入ピアで受信するステップと、
前記加入ピアの有権利着信度数の値を計算するステップであって、計算された前記有権利着信度数の値は、前記システムリソースインデックスの値を反映する、計算するステップと
を含むことを特徴とする方法。
【請求項２】
前記システムリソースインデックスは、前記ピアツーピアネットワーク内でリソースフロアを提供するように適合され、さらに前記システムリソースインデックスは、式
【数１】
2010515113.tif 000014
に従って計算されることを特徴とする請求項１に記載の加入コントリビューション認識ピアのピアツーピアネットワークへの加入を許可する方法。
【請求項３】
前記加入ピアの前記有権利着信度数の値を計算するステップは、式
【数２】
2010515113.tif 000015
に従って実行されることを特徴とする請求項２に記載の加入コントリビューション認識ピアのピアツーピアネットワークへの加入を許可する方法。
【請求項４】
前記加入ピアの処理デバイスを使用して前記有権利着信度数の値を計算するステップをさらに含むことを特徴とする請求項１に記載の加入コントリビューション認識ピアのピアツーピアネットワークへの加入を許可する方法。
【請求項５】
確立されたローカルプリエンプションポリシーを遵守する前記加入ピアを信用するステップをさらに含むことを特徴とする請求項１に記載の加入コントリビューション認識ピアのピアツーピアネットワークへの加入を許可する方法。
【請求項６】
前記ピアツーピアネットワークのピアデバイスから意欲情報を定期的に受信するステップをさらに含むことを特徴とする請求項１に記載の加入コントリビューション認識ピアのピアツーピアネットワークへの加入を許可する方法。
【請求項７】
前記ピアツーピアネットワークのピアデバイスにハートビートメッセージを定期的に送信するステップをさらに含むことを特徴とする請求項１に記載の加入コントリビューション認識ピアのピアツーピアネットワークへの加入を許可する方法。
【請求項８】
前記加入ピアは、帯域幅を有する信号を受信するように適合され、前記帯域幅は、前記ピアツーピアネットワークにリソースを提供する前記加入ピアの意欲に関係することを特徴とする請求項１に記載の加入コントリビューション認識ピアのピアツーピアネットワークへの加入を許可する方法。
【請求項９】
前記加入ピアは、信号を受信するように適合され、前記信号は、多重記述符号化信号として構成されることを特徴とする請求項１に記載の加入コントリビューション認識ピアのピアツーピアネットワークへの加入を許可する方法。
【請求項１０】
コントリビューション認識ピアツーピアネットワークのためのブートストラップノードであって、
プロセッサデバイスと、
前記プロセッサデバイスに結合されたネットワークインタフェースデバイスであって、前記ネットワークインタフェースデバイスは、通信ネットワークに結合されるように適合され、前記プロセッサデバイスは、潜在的な親ピアの識別情報を求める要求を前記通信ネットワークから前記ネットワークインタフェースデバイスを介して受信するように適合され、その一方で、前記プロセッサデバイスは、複数のデバイス識別値およびシステムパラメータを用いて応答するように適合される、ネットワークインタフェースデバイスと
を備えることを特徴とするブートストラップノード。
【請求項１１】
前記システムパラメータは、システムリソースインデックスを含むことを特徴とする請求項１０に記載のコントリビューション認識ピアツーピアネットワークのためのブートストラップノード。
【請求項１２】
前記システムリソースインデックスは、式
【数３】
2010515113.tif 000016
に従って計算されることを特徴とする請求項１１に記載のコントリビューション認識ピアツーピアネットワークのためのブートストラップノード。
【請求項１３】
前記ブートストラップノードは、ハートビートメッセージに応答して意欲パラメータの値を定期的に受信することを特徴とする請求項１２に記載のコントリビューション認識ピアツーピアネットワークのためのブートストラップノード。
【請求項１４】
前記ブートストラップノードは、ハートビートメッセージに応答して複数のピアデバイスからパラメータ値を定期的に受信することを特徴とする請求項１０に記載のコントリビューション認識ピアツーピアネットワークのためのブートストラップノード。
【請求項１５】
前記複数のデバイス識別値および前記システムパラメータは、意欲の値、発信度数の実際の貢献、着信接続の実際の数、計算された有権利着信度数、および参加ピアの親のリストを含むことを特徴とする請求項１０に記載のコントリビューション認識ピアツーピアネットワークのためのブートストラップノード。
【請求項１６】
前記潜在的ピア識別情報は、飽和した潜在的な親ピアを識別することを特徴とする請求項１０に記載のコントリビューション認識ピアツーピアネットワークのためのブートストラップノード。
【請求項１７】
潜在的な親ピアの識別情報を求める前記要求は、受信ピアによる要求に応答して前記通信ネットワークから受信され、前記受信ピアは、指数的バックオフ戦略を利用するように適合されることを特徴とする請求項１０に記載のコントリビューション認識ピアツーピアネットワークのためのブートストラップノード。
【請求項１８】
前記指数的バックオフ戦略は、式ｔwait＝ｔminＫ（ｅi＋βret）によって規定されることを特徴とする請求項１７に記載のコントリビューション認識ピアツーピアネットワークのためのブートストラップノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、ピアツーピアネットワーキングに関し、詳細には、ピアツーピアネットワークを介するインセンティブベースのライブストリーミング（ｌｉｖｅ  ｓｔｒｅａｍｉｎｇ）に関する。
【背景技術】
【０００２】
ピアツーピア（Ｐ２Ｐ）ライブストリーミング環境では、２つのタイプのアプローチ、すなわち、ツリーベースとメッシュベースのアプローチがある。ツリーベースのアプローチのためのコントリビューション認識（ｃｏｎｔｒｉｂｕｔｉｏｎ  ａｗａｒｅ）Ｐ２Ｐライブストリーミングを提供することに関して、いくつかの成果があがっている。メッシュベースのアプローチのためのコントリビューション認識Ｐ２Ｐライブストリーミングを提供することに関しては、知られた成果はあがっていない。しかし、メッシュベースのアプローチは、ロバスト性、効率性などに関してツリーベースのアプローチよりも性能が良い。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Nazanin Maghaeri, Reza Rejaie and Yang Guo, "Incorporating Contribution-Awareness into Mesh-Based Peer-to-Peer Streaming Services"
【発明の概要】
【発明が解決しようとする課題】
【０００４】
Ｐ２Ｐライブストリーミングに対するメッシュベースのアプローチにおいて、その環境は、制約された不均一（ｈｅｔｅｒｏｇｅｎｅｏｕｓ）な発信帯域幅（ｏｕｔｇｏｉｎｇ  ｂａｎｄｗｉｄｔｈ）を有するピアによって特徴づけられる。ピアが制約された不均一な発信帯域幅を有するメッシュベースのアプローチのためのコントリビューション認識Ｐ２Ｐライブストリーミングを提供することが望ましい。
【課題を解決するための手段】
【０００５】
本明細書では、ライブストリーミングをビデオに関して説明するが、デジタルオーディオなど任意のタイプのライブストリーミングメディアも含むことができる。本明細書で使用される「／」は、同一または同様のコンポーネントの代替名を示す。本発明の一実施形態では、メッシュベースのピアは、ランダムに接続された有向のオーバレイ／メッシュを維持する。Ｐ２Ｐライブストリーミングのメッシュベースのアプローチでは、ピア／ユーザは、ネットワークに対する貢献意欲（ｗｉｌｌｉｎｇｎｅｓｓ  ｔｏ  ｃｏｎｔｒｉｂｕｔｅ）に比例した異なるレベルのサービスを受け、意欲は、帯域幅毎のフロー（ｂａｎｄｗｉｄｔｈ  ｐｅｒ  ｆｌｏｗ）によって除算された、メッシュオーバレイへのピアのアップリンク帯域幅の貢献によって測定される。
【０００６】
ピアツーピアストリーミングオーバレイは、不均一で非対称かつ制限された帯域幅を有するピアで構成される。そのような環境において個々のピアへの配信品質（ｄｅｌｉｖｅｒｅｄ  ｑｕａｌｉｔｙ）を最大化するための１つのアプローチでは、例示的なシステムは、各ピアへの配信品質がその貢献に比例することを保証する。基本的に、例示的なリソース制約システムにおける配信品質は貢献を認識したものである。本発明の例示的な一実施形態によれば、コントリビューション認識機構は、メッシュベースのピアツーピアライブストリーミングシステムに組み込まれる。
【０００７】
一実施形態では、参加ピア（ｐａｒｔｉｃｉｐａｔｉｎｇ  ｐｅｅｒ）は、子ピア（ｃｈｉｌｄ  ｐｅｅｒ）がその必要パケットを１つまたは複数の親ピアからプル（ｐｕｌｌ）するスウォーミング型コンテンツ配信（ｓｗａｒｍｉｎｇ  ｃｏｎｔｅｎｔ  ｄｅｌｉｖｅｒｙ）を具現化する。オーバレイを形成するため、各ピアは、その必要なコンテンツをそこからプルするある数の親ピアを維持する。各ピアは、特定の数の子ピアの親としても機能し、それらにコンテンツを提供する。
【０００８】
Ｐ２Ｐネットワークへの加入を望むピアは、本明細書では、加入ピア（ｊｏｉｎｉｎｇ  ｐｅｅｒ）または要求ピア（ｒｅｑｕｅｓｔｉｎｇ  ｐｅｅｒ）と呼ばれる。ブートストラップノード（ｂｏｏｔｓｔｒａｐ  ｎｏｄｅ）は、ゲートキーパ（ｇａｔｅｋｅｅｐｅｒ）として振舞うノードである。加入ピアは、Ｐ２Ｐネットワークに加入するために、ブートストラップノードと交信（ｃｏｎｔａｃｔ）する。ブートストラップノードは、Ｐ２Ｐネットワーク内のピア／ユーザの総数を加入ピアに通知する。それと引き換えに、加入ピアは、該加入ピアがＰ２Ｐオーバレイ／ネットワークに貢献する意思のある帯域幅によって測定された貢献意欲をブートストラップノードに報告する。ブートストラップノードによって提供された情報を使用して、加入ピアは、該加入ピアが接続することができる親ピアの数を計算する。本発明の一実施形態では、ブートストラップノードは、すべての参加ピアのステータス情報を維持する。加入／要求ピアからの要求に応答して、ブートストラップノードは、着信要求のための新たな子ピアを受け入れることが可能な、無作為に選択された親／参加ピアのセットを提供する。
【０００９】
各ピアは、オーバレイのステータスおよびピア自身の帯域幅の貢献に基づいて、ある特定の数の有権利親ピア（ｅｎｔｉｔｌｅｄ  ｐａｒｅｎｔ  ｐｅｅｒ）（ｒi）を維持しようと試みる。これにより次に帯域幅が決定され、その結果、ピアが受信できる通信の品質が決定される。各個々のピアは、その意欲および子ピアの利用可能性に基づいて、ある特定の数の他のピアの子として機能する。
【００１０】
ピアツーピアネットワークにおけるライブストリーミングのためのコントリビューション認識の方法およびシステムが説明され、これは、ピアの有権利度数（ｅｎｔｉｔｌｅｄ  ｄｅｇｒｅｅ）および超過度数（ｅｘｃｅｓｓ  ｄｅｇｒｅｅ）を計算するステップと、潜在的な（ｐｏｔｅｎｔｉａｌ）親ピアを識別して交信するステップと、接続ポリシーを実施するステップとを含む。
【００１１】
一実施形態では、参加ピアがオーバレイを形成し、オーバレイ上で、個々のピアが、利用可能コンテンツのサブセットを接続ピアに転送することによって、その発信帯域幅を提供する。ツリーベースのアプローチでは、参加ピアは、１つまたは複数のツリー形状のオーバレイを形成し、各ピアは、ストリーム全体またはその特定の部分（例えば、サブストリームまたは記述（ｄｅｓｃｒｉｐｔｉｏｎ））を各接続ピアにプッシュ（ｐｕｓｈ）する。
【００１２】
本発明のさらなる一実施形態では、コントリビューション認識ピアツーピアシステムは、少なくとも１つの飽和ピア（ｓａｔｕｒａｔｅｄ  ｐｅｅｒ）を含む。飽和ピアは、その有権利度数が最大許容度数より大きいピアとして定義される。ピア度数は、整数値だけを取ることができる。一実施形態では、ピアは、「実際の着信度数（ａｃｔｕａｌ  ｉｎｃｏｍｉｎｇ  ｄｅｇｒｅｅ）および超過度数」を有する。
【００１３】
加入コントリビューション認識ピア（ｊｏｉｎｉｎｇ  ｃｏｎｔｒｉｂｕｔｉｏｎ−ａｗａｒｅ  ｐｅｅｒ）のピアツーピアネットワークへの加入を許可する方法が説明され、該方法は、システムリソースインデックス（ｒｅｓｏｕｒｃｅ  ｉｎｄｅｘ）をさらに含む複数のシステムパラメータを、加入ピアで受信するステップと、加入ピアの有権利着信度数（ｅｎｔｉｔｌｅｄ  ｉｎｃｏｍｉｎｇ  ｄｅｇｒｅｅ）の値を計算するステップとを含み、計算された有権利着信度数は、システムリソースインデックスの値を反映している。また、コントリビューション認識ピアツーピアネットワークのためのブートストラップノードが説明され、該ブートストラップノードは、プロセッサデバイスと、プロセッサデバイスに結合されたネットワークインタフェースデバイスとを含み、ネットワークインタフェースデバイスは、通信ネットワークに結合されるように適合され、プロセッサデバイスは、潜在的な親ピアの識別情報を求める要求を通信ネットワークからネットワークインタフェースデバイスを介して受信するように適合され、その一方で、プロセッサデバイスは、複数のデバイス識別値およびシステムパラメータを用いて応答するように適合される。
【００１４】
本発明の一実施形態では、コントリビューション認識メッシュベースピアツーピアストリーミングのピアは、その貢献に比例した品質を受け取る。本発明の別の実施形態では、コストファクタ（ｃｏｓｔ  ｆａｃｔｏｒ）／タックスレート（ｔａｘ  ｒａｔｅ）に関わらず、リソース利用度は９５％より大きい。本発明のさらに別の実施形態では、追加のプリエンプションポリシー（ｐｒｅｅｍｐｔｉｏｎ  ｐｏｌｉｃｙ）を排除し、（現在の貢献ではなく）ピアの意欲を考慮し、その結果、オーバレイ安定性が著しく向上する。本発明のまたさらなる実施形態では、説明されるコントリビューション認識機構は、スケーラブルであり、望ましくはグループサイズに関わらず機能する。本発明のまた別の実施形態によれば、オーバレイにおける情報配信の頻度の増加は、メッセージのオーバヘッドを減少させるが、存続期間の短いピアの受信品質を低下させる。本発明のまた別の実施形態では、接続の総数によって配信品質が決定され、それらがどの接続であるかではない。
【００１５】
本発明の様々な実施形態が、＿年＿月＿日に＿＿＿に発表された論文（非特許文献１参照）中でさらに説明されている。
【００１６】
本明細書で使用される通信ネットワークは、通信ネットワーク上のオーバレイであるピアツーピアネットワークを含む。本明細書で使用される通信ネットワークは、有線とすることもでき、または無線とすることもできることに留意されたい。
【００１７】
本発明は、以下の詳細な説明を添付の図面ともに読むことで最も良く理解される。図面は、以下で簡潔に説明される以下の図を含む。
【図面の簡単な説明】
【００１８】
【図１】拡散ツリーの概略図である。
【図２】本発明によるシステムの主要なプリミティブを示す図である。
【図３Ａ】集中ピア発見の方法を示す概略図である。
【図３Ｂ】集中ピア発見方法における要求ピアとブートストラップノードの間の通信を示すブロック図である。
【図３Ｃ】図３Ｂの要求ピアの詳細な動作を示す概略図である。
【図３Ｄ】集中ピア発見方法における既存ピアとブートストラップノードの間の通信を示すブロック図である。
【図３Ｅ】図３Ｄの交信ピアの詳細な動作の概略図である。
【図４Ａ】分散ピア発見の方法を示す概略図である。
【図４Ｂ】分散ピア発見方法における要求ピアとブートストラップノードの間の通信を示すブロック図である。
【図４Ｃ】図４Ｂの要求ピアの詳細な動作の概略図である。
【図４Ｄ】図４Ｂの交信ピアの詳細な動作の概略図である。
【図５Ａ】半分散ピア発見の方法を示す概略図である。
【図５Ｂ】半分散ピア発見方法における要求ピアとブートストラップノードの間の通信を示すブロック図である。
【図５Ｃ】図５Ｂの要求ピアの詳細な動作の概略図である。
【図５Ｄ】図５Ｂの交信ピアの詳細な動作の概略図である。
【図６】ピア発見プロセスのフローチャートである。
【図７Ａ】本発明の実施形態による、基本コストファクタ／タックスレート関数のグラフ表示である。
【図７Ｂ】本発明の実施形態による、フロアリング（ｆｌｏｏｒｉｎｇ）を含むタックスレート／コストファクタ関数のグラフ表示である。
【図７Ｃ】本発明の実施形態による、フロアリングおよび飽和を考慮したタックスレート／コストファクタ関数のグラフ表示である。
【図８Ａ】本発明の実施形態による、典型的な低貢献ピアの着信度数の変動のグラフ表示である。
【図８Ｂ】本発明の実施形態による、典型的な高貢献ピアの着信度数の変動のグラフ表示である。
【図８Ｃ】本発明の実施形態による、存続期間に基づいたピアの平均着信度数のグラフ表示である。
【図９Ａ】本発明の実施形態による、タックス値／コストファクタが２である場合の度数の加重平均の分布のグラフ表示である。
【図９Ｂ】本発明の実施形態による、チャーン（ｃｈｕｒｎ）に起因する平均親切断率のグラフ表示である。
【図９Ｃ】本発明の実施形態による、プリエンプションに起因する平均親切断率のグラフ表示である。
【図１０Ａ】本発明の実施形態による、切捨てが施された計算された有権利接続の本発明のグラフ表示である。
【図１０Ｂ】本発明の実施形態による、有権利ピア加重平均のグラフ表示である。
【図１０Ｃ】本発明の実施形態による、着信度数加重平均のグラフ表示である。
【図１０Ｄ】本発明の実施形態による、高帯域幅ピアの平均有権利および超過着信度数のグラフ表示である。
【図１０Ｅ】本発明の実施形態による、低帯域幅ピアの平均有権利および超過着信度数のグラフ表示である。
【図１１Ａ】本発明の実施形態による、加重平均発信度数のグラフ表示である。
【図１１Ｂ】本発明の実施形態による、平均利用度のグラフ表示である。
【図１１Ｃ】本発明の実施形態による、プリエンプションに起因する切断率のグラフ表示である。
【図１２Ａ】本発明の実施形態による、切捨てが施された計算された有権利接続のグラフ表示である。
【図１２Ｂ】本発明の実施形態による、タックスレート／コストファクタに関して取られた有権利加重平均のグラフ表示である。
【図１２Ｃ】本発明の実施形態による、高帯域幅ピアの平均有権利および超過着信度数のグラフ表示である。
【図１２Ｄ】本発明の実施形態による、低帯域幅ピアの平均有権利および超過着信度数のグラフ表示である。
【図１２Ｅ】本発明の実施形態による、加重平均発信度数のグラフ表示である。
【図１２Ｆ】本発明の実施形態による、平均利用度のグラフ表示である。
【図１３Ａ】本発明の実施形態による、加重平均着信度数のグラフ表示である。
【図１３Ｂ】本発明の実施形態による、高帯域幅ピアの平均有権利および超過着信度数のグラフ表示である。
【図１３Ｃ】本発明の実施形態による、低帯域幅ピアの平均有権利および超過着信度数のグラフ表示である。
【図１４Ａ】本発明の実施形態による、加重平均着信度数のグラフ表示である。
【図１４Ｂ】本発明の実施形態による、高帯域幅ピアの平均有権利および超過着信度数のグラフ表示である。
【図１４Ｃ】本発明の実施形態による、低帯域幅ピアの平均有権利および超過着信度数のグラフ表示である。
【図１４Ｄ】本発明の実施形態による、異なる存続期間を有する高帯域幅ピアの平均着信度数のグラフ表示である。
【図１４Ｅ】本発明の実施形態による、異なる存続期間を有する低帯域幅ピアの平均着信度数のグラフ表示である。
【図１４Ｆ】本発明の実施形態による、異なる存続期間を有するピアの正規化チャーン頻度のグラフ表示である。
【発明を実施するための形態】
【００１９】
本発明の一実施形態によれば、参加ピアの間で帯域幅を分配するための選択ポリシーは、Ｐ２Ｐネットワークにおけるピアの貢献に基づいている。Ｎ個のピアが存在し、ピアｉ（ｐi）の意欲がＷiであると仮定すると、本明細書で説明されるヒューリスティックは、ｐiが有することができる有権利親ピア（ｅｎｔｉｔｌｅｄ  ｐａｒｅｎｔ  ｐｅｅｒ）の総数Ｒiを決定する。汎用的なコスト関数（ｃｏｓｔ  ｆｕｎｃｔｉｏｎ）を使用して、各ピアが有することができる有権利の親の数を決定する。
【００２０】
【数１】
2010515113.tif 000003
【００２１】
ここで、Ｒiは（有権利度数（ｅｎｔｉｔｌｅｄ  ｄｅｇｒｅｅ）とも呼ばれる）有権利親ピアであり、Ｎは参加ピアの数であり、Ｗiはｐiの意欲であり、ｔはタックスレート／コストファクタである。１より大きなタックスレート／コストファクタを使用することによって、システム内に追加の帯域幅が存在すると想定される。
【００２２】
親発見プロセスは、有権利親ピアの数ｒiが決定された後に起こる。各ピアは、接続する（接続を形成する）親ピアを少なくともＲi個見つけるべきである。親発見プロセスは、帯域幅を公平かつタイムリーな方法で分散させるべきである。本明細書では、ピアが適切な親ピアを発見することを可能にする、集中（ｃｅｎｔｒａｌｉｚｅｄ）、分散（ｄｉｓｔｒｉｂｕｔｅｄ）、および半分散（ｓｅｍｉ−ｄｉｓｔｒｉｂｕｔｅｄ）の３つの異なるアプローチを説明する。また本明細書では、加入／要求ピアの適切な親ピアを見つけることができるデバイスも説明される。
【００２３】
Ｐ２Ｐオーバレイを介したライブマルチメディアストリームの配信は、インターネット上の１対多のストリーミングをサポートするための有望なアプローチである。このアプローチは一般に、Ｐ２Ｐストリーミングと呼ばれる。Ｐ２Ｐストリーミングでは、参加ユーザ（ピア）は、その利用可能コンテンツを他のピアに転送することによって、そのリソース（帯域幅と記憶空間の両方）を積極的に提供する。利用可能なリソースの総数は、ユーザ／ピアの数（ｐｏｐｕｌａｔｉｏｎ）に対応し、潜在的に任意の数の参加ピアに適合することができる。参加ピアがオーバレイを形成し、それを介して、個々のピアは、その利用可能コンテンツのサブセットを、該個々のピアに接続されたピアに転送することによって、その発信帯域幅を提供する。
【００２４】
Ｐ２Ｐストリーミングプロトコルの設計における努力の大部分は、システム内の大量のリソースが提供される環境に制限されてきた。しかし、概して無視されてきたが現実の展開では重大な一部の重要な側面は、ピアが非対称かつ不均一な帯域幅を有し、オーバレイ内に十分なリソースをもたない点である。本発明は、ホストが、その限られた発信帯域幅または意欲の欠如が原因で一定しない貢献をオーバレイに行う、不均一性の高い環境を考慮することによって、これらの問題に対処する。さらに、これらの環境では、システム内の全リソースは、全ての人が完全な品質のストリームを受信するのに十分でなくてもよい。
【００２５】
システム内のすべてのリソースを有効に利用しながら、ピアがその貢献に比例した品質のストリームを受信できるようにすることが望ましい。これらのポリシーは、高帯域幅ピアの帯域幅をより良く利用することができ、低帯域幅ピアよりも良い品質を提供することができ、より高い品質で受信するためにより多くの貢献をするようピアに促すことができる。集中、分散、および半分散を含む、システムリソース全体をモニタリングする可能な方法を検討する。
【００２６】
ＰＲＩＭＥは、各Ｐ２Ｐストリーミングシステムが、２つの主要なコンポーネント、すなわち、（ｉ）参加ピアをオーバレイに編成するオーバレイ構成と、（ｉｉ）オーバレイを介して個々のピアへのコンテンツの配信を決定するコンテンツ配信とで構成される、ライブストリーミング技法である。本発明の一実施形態によれば、これらの特徴は、コントリビューション認識機構と組み合わされる。
【００２７】
参加ピアは、ランダムに接続されたオーバレイまたはメッシュを形成し、該オーバレイまたはメッシュは有向グラフ（ｄｉｒｅｃｔｅｄ  ｇｒａｐｈ）である。各ピアは、ある特定の数の親ピアと、ある特定の数の子ピアを保持し、該ある特定の数の親ピアからコンテンツを取り出し、該ある特定の数の子ピアにコンテンツを配信する。各ピアについて、親ピアの数および子ピアの数はそれぞれ、そのピアの着信度数（ｉｎｃｏｍｉｎｇ  ｄｅｇｒｅｅ）および発信度数（ｏｕｔｇｏｉｎｇ  ｄｅｇｒｅｅ）と呼ばれる。参加ピアのアクセスリンク帯域幅を有効に利用するため、各ピアの着信度数および発信度数は、利用可能な着信帯域幅ｂdownおよび発信帯域幅ｂupに比例して設定される。着信（または発信）帯域幅の着信（または発信）度数に対する比は、各接続の平均帯域幅を表し、帯域幅毎のフロー（ｂａｎｄｗｉｄｔｈ−ｐｅｒ−ｆｌｏｗ）、すなわちｂｗｐｆと呼ばれる。
【００２８】
ｂｗｐｆは、事前選択され個々のピアに知られている構成パラメータである。具体的には、ピアの着信度数および発信度数はそれぞれ、ｂdown／ｂｗｐｆおよびｂup／ｂｗｐｆとなるように設定される。このような一実施形態では、各接続は、おおよそ同量のデータレートを受信ピアに提供する。したがって、一実施形態によれば、ピアの受信品質は、その着信ピアの数に比例する。
【００２９】
一実施形態では、スウォーミング型に類似の（ｓｗａｒｍ−ｌｉｋｅ）コンテンツ配信機構が、コンテンツ配信に利用される。スウォーミング型コンテンツ配信の主な利点は、参加ピアの発信帯域幅を有効に利用できるその能力と、参加ピアのダイナミクス（またはチャーン（ｃｈｕｒｎ））に対するそのロバスト性にある。スウォーミング型に類似のコンテンツ配信は、プッシュコンテンツ報告（ｐｕｓｈ  ｃｏｎｔｅｎｔ  ｒｅｐｏｒｔｉｎｇ）をプルコンテンツ要求（ｐｕｌｌ  ｃｏｎｔｅｎｔ  ｒｅｑｕｅｓｔｉｎｇ）と組み合わせる。親ピアとして、各ピアは、新たに受信したパケットをその子ピアに定期的に報告する。子ピアとして、各ピアは、各親ピアにおいて報告された利用可能なパケットと、各親ピアから要求している子ピアへの利用可能な帯域幅とに基づいて、要求パケットのサブセットをその親ピアに定期的に要求する。一実施形態では、これらの子ピアの要求は、定期的に行われる。
【００３０】
各親ピアからの要求パケットは、パケットスケジューリングアルゴリズムによって決定される。一実施形態では、ある親ピアは、子ピアから要求パケットのリストを定期的に受信し、要求順にパケットを配信する。各親ピアは、各子ピアによって要求されたパケットを、ＴＣＰまたはＲＡＰなどの輻輳制御機構を介して配信する。一実施形態では、各ピアの情報は、ハートビートメッセージ（ｈｅａｒｔ−ｂｅａｔ  ｍｅｓｓａｇｅ）回毎に、定期的に更新される。
【００３１】
ピア間での帯域幅の不均一性に適合するために、一実施形態において、コンテンツは、ＭＤＣ（ｍｕｌｔｉｐｌｅ  ｄｅｓｃｒｉｐｔｉｏｎ  ｃｏｄｉｎｇ）を用いて符号化される。ＭＤＣは、ストリーミングコンテンツをいくつかのサブストリームに編成し、各サブストリームは、独立に復号される。各ピアに対する配信品質は、受信する独立のサブストリームの数に比例する。ＭＤＣ符号化によって、各ピアは、そのアクセスリンク帯域幅を介して配信される適切な数のサブストリームを受信することができる。
【００３２】
パケットスケジューリングアルゴリズムは、次の２つの目標を達成するべきである。  
（ｉ）各親ピアからの利用可能な帯域幅を十分に利用することと、
（ｉｉ）子ピアによって要求されたパケットの時間内（ｉｎ−ｔｉｍｅ）配信を保証することである。
【００３３】
様々な実施形態では、システムの有効性は、各ピアが適切な数の子ピアを有し、そのリソースが有効に利用されているかどうか、および各ピアが、利用可能なリソースの割り当てに比例した適切な数の親との接続を識別し、確立することができるかどうかに従って決定される。一部の実施形態によれば、コントリビューション認識機構の性能の評価は、専らピア間の生産性に基づき、コンテンツ配信機構および実際の配信品質は考慮されない。一実施形態では、メッシュベースのピアツーピアストリーミングに関するコントリビューション認識機構の性能は、１つまたは複数の個々のピアがそれぞれ着信度数および発信度数を特定の値に維持できる能力に基づいて評価される。
【００３４】
少なくとも一実施形態では、オーバレイメッシュ（ソースから各ピアに到達するためにパケットが辿る経路）を介して個々のパケットを配信するパターンは、すべての参加ピアにおけるパケットスケジューリングアルゴリズムの集団的挙動（ｃｏｌｌｅｃｔｉｖｅ  ｂｅｈａｖｉｏｒ）、およびオーバレイメッシュのトポロジに依存する。様々な実施形態において、各ピアは、（受動測定を通して）利用可能な帯域幅と、（定期的な報告を使用して）各親ピアにおいて利用可能なコンテンツの動向を追跡する。
【００３５】
この情報が与えられると、スケジューリングアルゴリズムが定期的に起動され、各親ピアからの要求パケットが２つのステップで決定される。第１に、スケジューラは、最後の報告期間中に親ピア間に利用可能になった、最高のタイムスタンプを有する新しいパケットを識別する。これらの新しいパケットは常に、子ピアによって親ピアに要求される。第２に、一実施形態では、着信帯域幅を十分に利用するために、他の喪失パケット（ｍｉｓｓｉｎｇ  ｐａｃｋｅｔｓ）のランダムなサブセットを、各親ピアに要求する。負荷平衡を達成するために、あるパケットが２つ以上の親ピアで利用可能である場合、該パケットは、親ピアによってサービスされ得る全パケットに対する要求パケットの比が最も低い親から要求される。
【００３６】
様々な実施形態によれば、ブートストラップノードは、ピア間の接続を暗黙的に調整し、それにより、親発見プロセス中の成功の確率が増大する。少なくとも一実施形態において、親は、交信ピア（ｃｏｎｔａｃｔｅｄ  ｐｅｅｒ）のステータスの最近の変更を理由に要求を拒否できることに留意されたい。一実施形態によれば、交信ピアを親として機能させる要求に先立って、最小限のローカル状態情報（すなわち、Ｗi、ａi、およびＲi）を交換する。
【００３７】
上述のスケジューリングアルゴリズムを利用する一部の実施形態では、コンテンツの各セグメントは、２つのフェーズ、すなわち拡散フェーズ（ｄｉｆｆｕｓｉｏｎ  ｐｈａｓｅ）とスウォーミングフェーズ（ｓｗａｒｍｉｎｇ  ｐｈａｓｅ）で個々の参加ピアに配信される。拡散フェーズでは、各ピアは、より高いレベルの（ソースにより近い）親ピアから新しいセグメントのいずれかの部分を受信する。したがって、新たに生成されたセグメントのいくつかの部分は、異なるレベルのピアによって徐々にプルされる。例えば、新たに生成されたセグメントのいくつかの部分は、１回の周期（ｏｎｅ  ｔｉｍｅ  ｐｅｒｉｏｄ）（Δ）の後、レベル１のピアによってプルされ、次いで２×Δの後、レベル２のピアによってプルされ、それ以降も同様である。ｄ回の周期の後、オーバレイ内のすべてのピアは、新しいセグメントの一部分を有する。
【００３８】
したがって、一部の実施形態では、セグメントの各部分は、ソースによって一度だけ配信される。したがって、拡散フェーズ中にセグメントの部分を受信するピアのグループは、レベル１のピアをルートとするツリーを形成し、拡散ツリー（ｄｉｆｆｕｓｉｏｎ  ｔｒｅｅ）と呼ばれる。図１の影付きノードは、拡散ツリーを形成する。レベルｉのピアからレベルｉ＋１のその子ピアへのすべての接続は、拡散接続（ｄｉｆｆｕｓｉｏｎ  ｃｏｎｎｅｃｔｉｏｎ）と呼ばれる。これらの接続は、拡散ツリー上に配置される。
【００３９】
スウォーミングフェーズでは、各ピアは、同じまたはより低いレベルの（ソースからより遠い）親ピアからセグメントのすべての喪失部分を受信する。これらの親ピアは、スウォーミングペアレント（ｓｗａｒｍｉｎｇ  ｐａｒｅｎｔ）と呼ばれる。スウォーミングペアレントがセグメントのすべての喪失部分をもたないことがあるので、スウォーミングフェーズは、２回以上の周期を要することがある。拡散接続を除いて、オーバレイメッシュにおける他のすべての接続は、スウォーミング接続（ｓｗａｒｍｉｎｇ  ｃｏｎｎｅｃｔｉｏｎ）である。スウォーミング接続のコレクションは、スウォーミングメッシュ（ｓｗａｒｍｉｎｇ  ｍｅｓｈ）と呼ばれる有向メッシュを形成する。スウォーミングメッシュを使用して、各セグメントの異なる部分を異なる拡散ツリーの間で交換する。
【００４０】
要約すると、任意の新しいセグメントの各部分は、そのセグメントの拡散フェーズ中に特定の拡散ツリーを通って拡散される。次いで、利用可能な部分が、そのセグメントのスウォーミングフェーズ中にスウォーミングメッシュを通して異なる拡散ツリー内のピア間で交換される。
【００４１】
システムにおいてピアが、その貢献に比例した品質を受信できるようにするために、上述のＰ２Ｐストリーミング技法は、図２に示される以下の４つの機構を用いて増補される。
１．システムレベルの情報の更新と伝播
２．ピアの有権利および超過接続の計算
３．ピア発見
４．ポリシー
【００４２】
図２を参照すると、ポリシープリミティブ（ｐｏｌｉｃｙ  ｐｒｉｍｉｔｉｖｅ）の「更新」は、システムワイドパラメータである、Ｎ、Ｗi、およびｐiの実際貢献（ｆi）を計算し、該パラメータをネットワーク内のすべてのピアに伝播させる必要があることを表す。有権利（Ｒi）および超過（Ｅi）の着信度数は、以下で与えられる式に従って、各ピアについて計算される。
【００４３】
分散ピア発見の実施形態では、ピアのプール全体からの潜在的ピアと交信することによって、Ｒi＋Ｅi個のアイドル親ピア、または潜在的にプリエンプト可能な（ｐｒｅｅｍｐｔａｂｌｅ）子ピアを有する親ピアを見つける試みが行われる。集中ピア発見の実施形態では、ブートストラップノードによって選択されたピアのセット／リスト／キューを介して、Ｒi＋Ｅi個のアイドル親ピア、または潜在的にプリエンプト可能な子ピアを有する親ピアを見つける試みが行われる。他の実施形態では、集中ピア発見と分散ピア発見の実施形態を組み合わせた特徴を有する実施形態を含む、代替的なアプローチが使用される。すでに接続されている潜在的ピアを見つけた場合、表２によるルールを使用して、該潜在的ピアの子がプリエンプト可能かどうか判断する。子ピアがプリエンプト可能である場合、該子ピアに割り込む。
【００４４】
システムレベルパラメータは、ライブストリーミングの進行中に更新され、伝播される必要がある。これらのパラメータは、表１で定義されるようにＮ、Ｗi、およびｆiを含む。到着時に、一実施形態によれば、加入ピアは、ブートストラップノードと交信し、該ブートストラップノードに他のピアに提供する意欲（Ｗi）を通知する。ほぼ同時に、一実施形態によれば、加入ピアは、該加入ピアが接続できる潜在的親ピアのリストを受信する。ブートストラップノードは、上記一実施形態では、システム内のピアの総数Ｎと、すべてのピアについて集約された意欲Σ（Ｗi）についての情報を有する。
【００４５】
ピアは離脱する（ｄｅｐａｒｔ）とき、ブートストラップノードと交信し、オーバレイから登録抹消（すなわち離脱（ｄｅｐａｒｔｕｒｅ）を登録）されるべきである。クラッシュまたは他の致命的な状態が存在する場合、ピアは、オーバレイからの登録抹消に失敗することがある。それ以外の場合、終了ピア（ｅｘｉｔｉｎｇ  ｐｅｅｒ）は、ブートストラップノードにオーバレイからの離脱を通知すべきである。例えば、本発明の一実施形態によれば、各ピアは、離脱の直前にＢＹＥメッセージをブートストラップノードに送信する。ブートストラップノードは、指定の時間間隔（例えば、２×τ秒、ここで、τはハートビート間隔などの標準時間間隔）の間にピアからハートビートメッセージを受信しない場合、ピアが離脱したと仮定して、そのピアの記録を削除する。ブートストラップノードは、一実施形態では、個々のピアの更新された状態を維持し、したがって、ＮおよびＰＷｉなどのグループレベルの状態の特徴を容易に判断することができる。
【００４６】
【表１】
2010515113.tif 000004
【００４７】
ピアｐiの実際の貢献ｆiは、時間とともに変化する。したがって、システムは、すべてのピアについて集約された貢献Σ（ｆi）を計算するために、この情報を定期的にリフレッシュする必要がある。計算は、以下で説明される２つの例示的な方法を含め、様々な方法で実行することができる。  
・集中更新：このアプローチでは、ピアは、その実際の貢献が変化した場合は常に、ブートストラップノードと交信する。
・分散更新：このアプローチでは、貢献情報は、拡散ツリーに沿って伝播される。ピアは、その現在の貢献に（拡散ツリー内の）後続（子）ピアについて集約された貢献を加算したものに関して、拡散ツリー内の親ピアを定期的に更新する。第１レベルのピアは、更新をグローバルブートストラップノードに送信する。分散更新では、情報は定期的（または実施形態によっては散発的）に更新されるだけなので、Σ（ｆi）の値は、正確でないことがある。しかし、更新の間の時間間隔を調整することによって、十分な正確性が達成される。
【００４８】
Ｎ、Σ（Ｗi）、およびΣ（ｆi）の集約情報も、以下で説明されるように、ピアが有権利および超過着信接続の数を計算するために、すべてのピアに伝播させる必要がある。この伝播も、集中または分散スキーマによって行うことができる。例示的な集中スキーマでは、ブートストラップノードは、すべてのピアにＮ、Σ（Ｗi）、およびΣ（ｆi）の現在の値を定期的に通知する。例示的な分散スキーマでは、情報は、拡散ツリーを通じてルート（ブートストラップノード）からすべてのピアに分配される。
【００４９】
親発見機構の目標は、各ピアが、必要な数の親を見つけて、所望の数の接続を確立できるようにすることである。本発明の一実施形態によれば、各ピアは常に、Ｒi個の有権利接続を確立し、その後、超過接続を確立できる可能性を探る。そのような一実施形態では、ピアｉの有権利度数Ｒiは、以下の式を使用して計算される。
【００５０】
【数２】
2010515113.tif 000005
【００５１】
ここで、ｔは、タックスレート／コストファクタを表すパラメータであり、システム内の追加の帯域幅を保証するために、ｔ＞１である。Ｒiは基本的に、２つの項の和である。第１項は、ピアがＷiの貢献をすることによって受信する権利がある最低帯域幅を表し、第２項は、ピアあたりの残りの平均帯域幅である。ピアｉの計算された超過着信度数は、
Ｅi＝Ｍａｘ−Ｒi    （３）
である。
【００５２】
ピアは、その有権利度数を計算すると、それをサポートする超過度数を有するピアを見つけようと試みる。すなわち、超過度数を有するピアは、超過度数を有するピアが追加的な接続を行う手助けができる親ピアを探す。このようにして、超過度数を有するピアは、その貢献を改善し、それによってその品質を改善する。ピア発見プロセスは、以下で説明される３つの異なるアプローチを使用して行うことができる。
【００５３】
本発明の一実施形態によれば、各子ピアは、親からの着信接続を有権利または超過としてラベル付けしないことに留意されたい。代わりに、子ピアは、接続の実際の数（ａi）と有権利度数Ｒiの動向を追跡するだけである。Ｒiは、ブートストラップノードからの各報告の後、定期的に更新される。本発明の様々な実施形態では、すべての接続は同じ帯域幅を有するので、これが実行可能である。
【００５４】
集中ピア発見では、ブートストラップノードは、システム内のすべてのピアの動向を追跡するテーブルを保持する。各ピアは、例えば、テーブル内に１つのエントリ（ｉｄ，Ｗi，ｆi，ｅi，ｒi）を有し、ここで、ｉｄは、ピアの識別（ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）である。Ｗiとｆiの差は、このピアにおける空スロットの数を示す。一実施形態では、システム内のすべてのピアは、拡散ツリー内のすべての子ピアと、対応するパラメータとのテーブルも保持する。一実施形態によれば、セッション中、各ピアは、τ秒毎に１回（上述したようにτは標準時間間隔である）、ハートビートメッセージをブートストラップノードに送信する。ハートビートメッセージを用いて、ピアは、有権利度数（Ｒi）およびその親のリストとともに、実際の発信度数（ｆi）および着信度数（ａi）を含む、その動的なプロパティの値を報告する。
【００５５】
したがって本発明の一実施形態によれば、ブートストラップノードは、最も最近のグループレベルの状態をすべての参加ピアに定期的に報告する。例示的な一実施形態では、この報告はτ秒毎に行われる。一実施形態では、ピアは、ブートストラップノードから新しい報告を受信すると、上記の式（２）を使用して、その有権利接続の数（Ｒi）を決定する。Ｒiの値が、対応するピアの現在の着信度数より大きい場合、該ピアは、さらに親の発見を継続する。対照的に、ピアは、その有権利着信度数が低下した場合、それに応じてｅiを増加させる。
【００５６】
更新周期τは、したがって、一実施形態ではブートストラップノードにおける状態情報の新しさと信号伝達オーバヘッドの間のトレードオフを決定する構成パラメータである。より具体的には、τの値の増加は、信号伝達オーバヘッドを減少させる。
【００５７】
一実施形態では、ピアは、そのＲiの低下を理由に推測によって着信接続を切断することはなく、むしろ、実際の超過着信度数を増加させることに留意されたい。要求および適切なプリエンプションにおいて、追加の超過接続は親ピアによって切断されることがある。このアプローチは、ブートストラップノードにおける状態情報の正確性がより低下するというコストを払って、状態収集および報告に関連するシステム内のダイナミクスおよび引き起こされるチャーンを減少させる。例えば、一実施形態では、τのデフォルト値は、１０秒である。
【００５８】
様々な実施形態では、各ピアは、離脱する直前にＢＹＥメッセージをブートストラップノードに送信する。ブートストラップノードは、２×τ秒の間にハートビートメッセージをピアから受信しない場合、ピアが離脱したと仮定し、その記録を削除する。本発明の一実施形態によれば、ブートストラップノードは、個々のピアの更新された状態を維持し、したがって、ＮおよびΣＷiなどのグループレベルの状態を容易に決定することができる。本発明の一実施形態によれば、チャーンに起因する、正規化された親の切断率は、ピアの帯域幅に依存しない。
【００５９】
ここで図３Ａ〜図３Ｅを参照すると、有権利または超過接続を確立するために、各ピアは最初に、より多くの子ピアに適合できる可能性のある参加ピアのサブセットについての交信情報を、ブートストラップノードから取得する必要がある。したがって、本発明の一実施形態では、要求ピア（接続できる潜在的ピアの発見を要求するピア）は、要求を、それ自体のパラメータであるｒA、ｅA、ｆAと一緒に、ブートストラップノードに送信する（１）。
【００６０】
一実施形態によれば、ブートストラップノードは、すべての参加ピアの状態（すなわち潜在的な親）を維持しているので、潜在的な親を識別し、該潜在的な親のランダムなサブセットを、より多くの親を探しているピアに提供することができる。したがって、一実施形態では、ブートストラップノードは、要求ピアを潜在的に受け入れて要求ピアの親ピアになることができる、すべての潜在的親ピアのリストを要求ノードに返す（１）。
【００６１】
一実施形態によれば、ブートストラップノードから潜在的な親のリストを与えられると、各ピアは、リスト内の各ピアと順番に交信し、そのローカル状態（すなわち、Ｗi、ａi、およびＲi）を提供し、交信ピアに親として機能するように要求する。ピアは、以下で説明されるようなローカルプリエンプションポリシーに基づいて、親として機能するよう求める要求を受け入れ、または拒否する。
【００６２】
交信ピアが、ピアｐの親として機能することに同意した場合、ピアｐは、その有権利および超過接続の数を相応に更新し、更新された情報を次のハートビートでブートストラップノードに提供する。この場合もやはり、一実施形態によれば、ピアは、そのローカル状態（すなわち、ａiおよびＲi）を、データパケットにピギーバックされる親に送信する。各ピアは、その着信度数が最大値（すなわちＭａｘ）に達するまで、より多くの親への接続を確立し続ける。本発明のさらなる一実施形態では、最初に提供された潜在的な親のリストがすべて使い果たされた場合、ピアは、ブートストラップノードと交信して潜在的な親の新しいリストを取得する。
【００６３】
ローカルプリエンプションポリシーは、親ピアが子ピアからの接続の要求にどのように反応するかを決定する。親ピアの発信度数が、貢献意欲がありかつ貢献可能な最大発信度数より小さい場合（ｒi＜Ｗi）、プリエンプションポリシーに従って、接続要求が受け入れられる。しかし、親ピアの発信度数が十分に利用されている場合、新たな子ピアＡは、子ピアＡへの接続の提供がより高い優先度を有するときのみ、既存の子ピアＢに置き換えられる（すなわちプリエンプトする）ことができる。
【００６４】
一実施形態では、親によって利用されるポリシーと同じローカルプリエンプションポリシーを使用して、適切な親が選択される。別の実施形態では、親ピアと子ピアが、異なるプリエンプションポリシーを使用する。ピアｐがブートストラップノードに潜在的な親のリストを要求すると、ブートストラップノードは、ピアｐがプリエンプトすることができる少なくとも１つの子を有する参加ピアのランダムなサブセットを選択する。基本的に、ブートストラップノードは、ピア間の接続を暗黙的に調整する。これがひいては、親発見プロセス中の成功の確率を増大させる。この調整にもかかわらず、例えば、交信ピアの状態が最近変更された場合のように、親が要求を拒否することが可能であることは注目に値する。
【００６５】
ピアＡとピアＢの間の接続の相対的な優先度は、以下の表２−Ａに示されるように４つのシナリオで決定される。
【００６６】
【表２】
2010515113.tif 000006
【００６７】
表２−Ａは、親ノード／ピアにおいてピアＢによって現在使用されている接続／スロットを使用するために、ピアＡがピアＢをプリエンプトする（ｐｒｅｅｍｐｔ）ことができるかどうかを決定する際に使用される第１の実施形態のポリシーを表している。
【００６８】
現在の接続がプリエンプト可能であるかどうかを判断するために表２−Ａをどのように使用すべきかの例を以下に示す。ピアＢがすでに特定の親ピアに接続されていると仮定する。第１の例では、ピアＡ（ｐa）およびピアＢ（ｐa）がともに有権利度数を有する。ｐaの実際の貢献（発信度数）はｆaである。ｐaの実際の有権利着信度数はｒaである。ｐaの実際の超過着信度数はｅaである。ｐbについても同様である。ｆa＝２０、ｒa＝２、およびｅa＝０である場合、（ｒa＋ｅa）／ｆa＝２／２０＝１／１０である。ｆb＝２０、ｒb＝５、およびｅb＝０である場合、（ｒb＋ｅb）／ｆb＝５／２０＝１／４である。計算はｐa＜ｐbであるので、ｐaはｐbをプリエンプトすることができる。第２の例では、ｐaは有権利度数を有し、ｐbは超過度数を有する。ｐaのパラメータについては同じ値を使用すると、ｐaは今回もやはり、（ｒa＋ｅa）／ｆa＝２／２０＝１／１０という計算値を有する。ｆb＝５、ｒb＝２、およびｅb＝１である場合、（ｒb＋ｅb）／ｆb＝３／５である。今回もやはり、ｐa＜ｐbの計算あるので、ｐbはｐaをプリエンプトすることができる。第３の例では、ｐaは超過度数を有し、ｐbは有権利度数を有する。この場合、ｐaはｐbをプリエンプトすることができない。第４の例では、ｐaおよびｐbがともに超過度数を有する。ｆa＝５、ｒa＝２、およびｅa＝０である場合、ｅa／ｆa＝０／５＝０である。ｆb＝５、ｒb＝２、およびｅb＝２である場合、ｅb／ｆb＝２／５であり、比ｅa／ｆaは比ｅb／ｆbより小さいので、ｐaはｐbをプリエンプトすることができる。この例では、ｒaおよびｒbは使用されないことに留意されたい。
【００６９】
上述したように、要求ピアは、ブートストラップノードからリストを受信すると（２）、リスト内のピアと順番に交信する（２）。交信したピアは、空スロットを有する場合、要求ピアを許可し、該ピアはこの交信したピアの子になる。交信したピアが空スロットをもたない場合、表２−Ａで説明されたポリシーを使用して、要求ピアが、交信したピアの子ピアの１つをプリエンプトすることができるかどうか判断する。要求ピアが、交信ピアの子ピアの１つをプリエンプトすることができる場合、交信ピアは、選択されプリエンプトされる該子ピアを切断して、接続／スロットを要求ピアに割り当てる。それ以外の場合、要求ピアは、許可されないことを通知される。返されたリスト内のすべてのピアは潜在的な親ピアであるが、これらは、以下の理由のために要求ピアを許可できないことがある。  
１．ブートストラップノードで維持されるパラメータは、状態変化とパラメータが更新される時間との間の遅延のために最新でないことがある。  
２．要求ノードがより多くの親ピアを取得するにつれて、ｒA、ｅA、ｆAの値は時間とともに変化する。
【００７０】
リスト内のピア（ピアの子を含む）と交信するプロセスは、要求ピアが必要な数のピアを取得するまで、またはリストが使い果たされるまで続く。後者の場合、要求ピアは、時間Ｔの間スリープし、再び上述のプロセスを開始する。
【００７１】
一実施形態では、ピアＡとピアＢの間の接続の相対的な優先度は、以下の表２−Ｂに示されるように４つのシナリオで決定される。
【００７２】
【表３】
2010515113.tif 000007
【００７３】
本発明の表２−Ｂの実施形態では、接続を求めるピアｉの要求が潜在的な親によって拒否された場合、ピアｉの反応は、以下のように、その現在の状態に依存する。  
・Ｅｎ−Ｅｘシナリオ：ピアＡが有権利接続を探し（ａA＜ＲA）、ピアＢが既にいくつかの超過接続を有している（ａB＞ＲB）場合、Ａによる要求は常に、ピアＢへの既存の接続をプリエンプトすることができる。このポリシーは、新たなピアが、他のピアへの超過接続をプリエンプトすることによって、容易に有権利着信度数に達することを可能にする。  
・Ｅｘ−Ｅｎシナリオ：ピアＡが超過接続を探し（ａA＞ＲA）、ピアＢが有権利接続だけを有している（ａB≦ＲB）場合、Ａによる要求は、ピアＢへの既存の接続をプリエンプトすることができない。  
・Ｅｎ−Ｅｎシナリオ：両方のピアが有権利接続だけを有する場合、Ａの正規化された着信度数がＢよりも小さい、すなわち、ｒA／ＷA＜（ｒB／ＷB−１）という条件が満たされるときのみ、ＡはＢへの接続をプリエンプトすることができる。  
・Ｅｘ−Ｅｘシナリオ：ピアＡが超過接続を探し（ａA＞ＲA）、ピアＢがいくつかの超過接続を有している（ａB＞ＲB）場合、Ａは、より少ない数の超過接続を有するとき（すなわち、ｅA＜ｅB−１）、ピアＢへの既存の接続をプリエンプトすることができる。やはり、この条件も、２つのピアの間のプリエンプションの振動（ｏｓｃｉｌｌａｔｅ）を防止する。
【００７４】
表ＩＩ−Ｂは、新規のピアＡによる既存の子ピアＢへの上記のローカルプリエンプションポリシーを要約したものである。新規のピアがシステムに加入するとき、または既存のピアがプリエンプションに起因して親を失うとき、これらは親発見プロセスを開始し、システム内の別のピアを同様にプリエンプトすることができることに留意されたい。したがって、観測した参加ピア間における親の変更率は、単にチャーンが原因で発生する親の離脱率よりも高い。基本的に、プリエンプションは、オーバレイの不安定性をさらに悪化させる。一実施形態では、オーバレイの安定性は、個々のピアの親の変更率を測定することによって定量化される。別の実施形態では、親の変更は、２つのグループ、すなわち親の離脱が原因の変更と、他の子ピアによるプリエンプションが原因の変更とに分類される。
【００７５】
要求ピアの潜在的な親ピアは、以下のように定義される。  
１．１つのピアが複数の空スロットをもつ場合、それは潜在的親ピアである。  
２．表２−Ｂで定義されたポリシーに基づいて、（ピアＢで示される）ピアを（ピアＡで示される）要求ピアによってプリエンプトすることができる場合、ピアＢの親ピアが潜在的ピアである。
【００７６】
各接続が特定の記述（ｄｅｓｃｒｉｐｔｉｏｎ）を提供するので、ツリーベースのＰ２Ｐストリーミング機構は、各接続を具体的にラベル付けするべきである。ピアｉの現在の親の数がその有権利着信度数より小さい場合（ａi＜Ｒi）、該ピアはまだその有権利着信度数に達しようと試みているところである。したがって、該ピアは直ちに、ブートストラップノードによって提供されたリスト内の次の潜在的な親に要求を送信する。各ピアが有権利着信度数に達し得るように、システム内に十分なリソースが存在しなければならないので、このかなり積極的な発見アプローチは理に適っている。ピアｉの現在の親の数がその有権利度数以上である場合、ピアｉは、既にその有権利度数を確立しており、超過接続を探しているところである。
【００７７】
この場合、拒否された要求は、システム内で超過リソースが制限されていることを示す。したがって、拒否されたピアは、別の接続要求を送信する前に、待機間隔と呼ばれる間隔ｔwaitだけ待機する。待機間隔は、超過接続を求める拒否された各要求についての指数バックオフであり、
ｔwait＝ｔmin×Ｋ×（ｅi＋βret）
である。ここで、ｔminは最小バックオフ時間であり、Ｋはバックオフ係数（ｂａｃｋｏｆｆ  ｆａｃｔｏｒ）である１より大きな乱数であり、ｒｅｔは連続した失敗の数である。一実施形態では、ｔminは５秒に設定され、βは２である。上で示したように、超過リソース量は分からず、チャーンに伴って動的に変化している。待機時間を決定するためのこの適合アプローチは、ピア間の明示的な調整を全く必要とせずに、個々のピアの超過度数（ｅi）および超過接続を求める総需要を調整する。
【００７８】
親発見を、分散方式で実行することができる。例えば、多重ツリーベースＰ２Ｐストリーミングアプローチと同様に、ピアは（ソースから開始して）拡散ツリーをトラバースし、各ピアを検査して、所望のタイプの適切な数の親を見つけることができる。このアプローチは、中央調整ポイントを必要としないが、新たに到着したピアによる持続的な親を求める要求が原因で、参加ピア（特に拡散ツリーのより高いレベルにある参加ピア）に重い負荷を与えることがあり得る。ここで提示される集中アプローチは、そのようなコントリビューション認識機構を適切に表す。
【００７９】
図３Ｂは、集中ピア発見方法における要求ピアとブートストラップノードの間の通信を示すブロック図である。ピア毎に、ピア情報テーブル内に１つのエントリ（ｉｄ，Ｗi，ｆi，ｅi，ｒi）が存在する。要求ピアは、加入要求をブートストラップノード内のピア交信インタフェース３０５に送信する（１）。その後、ピア交信インタフェース３０５は、ピア情報テーブルモジュール３１０にルックアップ要求を転送する（２）。ピア情報テーブルモジュール３１０は、ピア情報テーブルに対してルックアップオペレーションを実行し、潜在的な親ピアリストのリストをピア交信インタフェース３０５に返す（３）。その後、ピア交信インタフェース３０５は、要求されたピア情報を含むリストを要求ピアに返す。
【００８０】
図３Ｃは、図３Ｂの要求ピアの詳細なオペレーションを示す概略図である。要求ピアは、加入要求でブートストラップノードと交信する（１）。ブートストラップノードは、潜在的な親ピアのリストを返す（２）。要求ピアは、潜在的な親ピアのリストを、潜在的／候補（ｃａｎｄｉｄａｔｅ）親ピアのキューに入れる。その後、要求ピアは、各潜在的親ピアをキューから順番に取り出し、要求ピアを許可できるかどうか、および該要求ピアが子ピア（または子ピアの１つ）となることができるかできるかどうかを調べるために、その潜在的な親ピアと交信する（３）。
【００８１】
図３Ｄは、集中ピア発見方法における既存のピアとブートストラップノードの間の通信を示すブロック図である。既存のピアは、更新メッセージをブートストラップノードのピア交信インタフェース３０５に送信することによって（１）、ブートストラップノードに関するその情報を更新する。ピア交信インタフェース３０５は、ピア情報テーブルモジュール３１０に更新情報を転送し（２）、ピア情報テーブルモジュール３１０は、ピア情報テーブルを更新する。ブートストラップノードは、ピア交信インタフェースを介して、情報が更新されたことを示すメッセージを既存のピアに返す（３）。
【００８２】
図３Ｅは、図３Ｄの交信ピアの詳細なオペレーションを示す概略図である。交信ピア（潜在的な親ピア）は、子ピアとして加入することを求める要求を要求ピアから受信する（１）。交信ピアは、その子ピア情報テーブルを検査し、自身が有している空スロットのいずれかを用いて、または現在の子ピアの１つをプリエンプトすることによって、加入要求を満たすことができるかどうかを判断する。交信ピアは、その判断の結果を示す応答を要求ピアに返す（２）。
【００８３】
ここで図４Ａを参照すると、分散発見アプローチでは、要求ピアは最初に、ブートストラップノードと交信する（１）。ブートストラップノードは、すべての拡散ツリーのルートにあるコンテンツソースノードのアドレス／位置を返す（１）。要求ノードは、交信キューを保持しており、コンテンツソースノードをキューに入れ、要求ピアが最初にソースノードと交信し（２）、ソースノードは、その子のリストを要求ピアに返す（２）。コンテンツソースノードおよびシステム内のすべてのピアは、拡散ツリー内の子ピアおよび対応するパラメータのテーブルを保持する。
【００８４】
要求ピアは、１回に１つの潜在的親ピアをキューから取り出し、この潜在的親ピアと交信して、該要求ピアが許可されるかどうか調べる（３）。各交信ピアは、その子ピアリストを返す（４）。許可は、上述のポリシーと同じポリシーに基づく。交信ピアが空スロットを有する場合、該交信ピアは、要求ピアを許可し、要求ピアは、この交信ピアの子になり、交信ピアは、その子ピアのリストを要求ピアに返す（４）。要求ピアは、このようにして、要求ピアが接続可能な必要な数のピアを取得するまで、あるいはリストおよびピアが使い果たされるまで、拡散ツリーのさらに下のピアと交信（５）を続け、その後、要求ピアが許可された各交信ピアの子と交信（６）を続ける。交信ピアが空スロットを有しない場合、表２−Ａで説明したポリシーを使用して、要求ピアが交信ピアの子ピアの１つをプリエンプトすることができるかどうか判断する。
【００８５】
要求ピアが交信子ピアの１つをプリエンプトすることができる場合、交信ピアは、プリエンプトするのに選択された子ピアを切断し、接続／スロットを要求ピアに割り当てる。それ以外の場合、要求ピアは許可されないことを通知される。交信ピアはまた、プロセスの終りに、拡散ツリー内のその子ピアのリストを要求ピアに返す。要求ピアは、返されたリストを交信キューの最後に付加する。プロセスは、要求ピアが必要な数のピアを取得するまで、またはリストが使い果たされるまで継続される。後者の場合、要求ピアは、時間Ｔの間スリープし、再び上述のプロセスを開始する。
【００８６】
第３のアプローチは、半分散（ｓｅｍｉ−ｄｉｓｔｒｉｂｕｔｅｄ）アプローチである。信号伝達のオーバヘッドを減少させるため、ピアは、２ホップ離れた親ピアに関するローカル情報を保持する。各親ピアは、空スロットの数Ｗi、実際の貢献ｆi、および超過接続の数ｅiについての情報を、子ピアへのコンテンツパケット内にピギーバックする。
【００８７】
さらに、親ピアは、その親ピアの情報（Ｗi，ｆi，ｅi）も子ピアに送信する。したがって、ノードは、その親ピアおよびグランドペアレントピアの情報を有する。
【００８８】
図４Ｂは、分散ピア発見方法における要求ピアとブートストラップノードの間の通信を示すブロック図である。要求ピアは、加入要求をブートストラップノードのピア交信インタフェース４０５に送信する（１）。ブートストラップノードは、コンテンツソースノードのアドレス／位置を返す（２）。要求ピアは、コンテンツソースノードと交信する（３）。
【００８９】
図４Ｃは、図４Ｂの要求ピアの詳細なオペレーションを示す概略図である。要求ピアは、ブートストラップノードと交信する（１）。要求ピアは、コンテンツソースノード情報をブートストラップノードから受信する（２）。要求ピアは、コンテンツソースノードと交信し、要求ピアの潜在的な親ピアである子ピアのリスト／キューを受信する（２）。要求ピアは、返された子ピアのリストを、その潜在的／候補親ピアのキューの最後に保存する。その後、要求ピアは、潜在的／候補親ピアのキューからそれぞれの潜在的な親ピアのエントリを取り出し、潜在的な親ピアと交信して、該要求ピアが子ピアになることができるかどうか調べる（４）。交信される潜在的な親ピアは、その子ピアのリスト／キューを返し、要求ピアは、その潜在的／候補親ピアのキューの最後にそれを保存する。
【００９０】
図４Ｄは、図４Ｂの交信ピアの詳細なオペレーションを示す概略図である。要求ピアから加入要求を受信すると（１）、交信ピアは、その子ピア情報のテーブルを検査し、有している空スロットのいずれかを用いて、または現在の子ピアの１つをプリエンプトすることによって、加入要求を満たすことができるかどうかを決定する。交信ピアは、その決定の結果を示す応答を子ピアのリストとともに要求ピアに返す（２）。
【００９１】
ここで図５Ａを参照すると、要求ノードは、ブートストラップノードと交信し（１）、ブートストラップノードは、潜在的ピアの交信キューを返す（１）。ブートストラップノードがシステム内のすべてのピアのリストを有することに留意されたい。しかし、ブートストラップノードは、各ピアのパラメータの経過を追跡するテーブルを保持しない。ブートストラップノードは、所定の数の潜在的親ピアをリストからランダムに選択し、そのリストを交信キューとして要求ノードに返す。
【００９２】
本発明の別の実施形態では、ブートストラップノードは、状態テーブルを保持する。状態テーブルは、ブートストラップノードによる、あるピアのサービスの状態を反映する。要求ピアから許可要求を受信すると、ブートストラップノードは、プリエンプト可能な少なくとも１つの子を有する参加ピアのランダムなサブセットを選択する。一実施形態によれば、許可を要求している子ピアを受け入れ、または拒否するのに親ピアがローカルに使用するものと同じプリエンプションポリシー基準に基づいて、ブートストラップノードによって、状態テーブルに包含するための適切な親が選択される。
【００９３】
その後、要求ノードは、リスト内の各ピアと交信し（２）、その近隣（ｎｅｉｇｈｂｏｒ）のリストを受信する（２）。これらのリストをすべて一緒にして、単一の交信キューを形成する。要求ピアは、１回に１つのピアをキューから取り出し、要求ピアが許可されるかどうかを調べるために、この潜在的ピアと交信する（３）。許可は、上述と同じポリシーに基づく。交信ピアは、空スロットを有する場合、要求ピアの参加を許可し、該ピアは、この交信ピアの子になる。交信ピアが空スロットを有しない場合、表２で説明したポリシーを使用して、要求ピアが交信ピアの子ピアの１つをプリエンプトすることができるかどうかを判断する。
【００９４】
要求ピアが交信子ピアの１つをプリエンプトすることができる場合、交信ピアは、プリエンプトするのに選択された子ピアを切断し、接続／スロットを要求ピアに割り当てる。それ以外の場合、要求ピアは許可されないことを通知される。
【００９５】
プロセスは、要求ピアが必要な数のピアを取得するまで、またはリストが使い果たされるまで継続される。後者の場合、要求ピアは、時間間Ｔの間スリープし、再び上述のプロセスを開始する。
【００９６】
図５Ｂは、半分散ピア発見方法における要求ピアとブートストラップノードの間の通信を示すブロック図である。ピア情報テーブルは、システム内のすべてのピアのリストを保持する。要求ピアは、加入要求をブートストラップノードのピア交信インタフェース５０５に送信する（１）。その後、ピア交信インタフェース５０５は、ルックアップ要求をピア情報テーブルモジュール５１０に転送する（２）。ピア情報テーブルモジュール５１０は、ピア情報テーブル上でルックアップオペレーションを実行し、ランダムに選択された潜在的親ピアのリストをピア交信インタフェース５０５に返す（３）。その後、ピア交信インタフェース５０５は、ランダムに選択された潜在的親ピアのリストと、それらのピアの情報を要求ピアに返す。
【００９７】
図５Ｃは、図５Ｂの要求ピアの詳細なオペレーションを示す概略図である。要求ピアは、ブートストラップノードと交信する（１）。要求ピアは、ランダムに選択された潜在的親ピアのリストを受信し（２）、ランダムに選択された潜在的親ピアを潜在的／候補親ピアのキューに保存する。要求ピアは、潜在的／候補親ピアのキュー内のピアと順番に交信する（３）。その後、要求ピアは、近隣要求メッセージであるメッセージを交信（潜在的な親）ピアに送信する（３）。すべての交信ピアは、近隣ピアのリストを返す。要求ピアは、近隣ピアのリストを潜在的／候補親ピアキューに保存する。要求ピアは、要求ピアが子ピアになることができるかどうかを調べるために、潜在的／候補親ピアキュー上の次の潜在的親ピアと交信する（４）。
【００９８】
図５Ｄは、図５Ｂの交信ピアの詳細なオペレーションを示す概略図である。交信ピアは、要求ノードから近隣要求メッセージを受信すると、その近隣ピアのリストを要求ノードに返す（１）。着信メッセージが空スロットを探すためのものである場合、交信ピアは、その子ピア情報のテーブルを検査し、有している空スロットのいずれかを用いて、または現在の子ピアの１つをプリエンプトすることによって、要求を満たすことができるかどうかを決定する。交信ピアは、その決定の結果を示す応答を要求ピアに返す（２）。
【００９９】
ここで図６を参照すると、図６は、ピア発見プロセスを示すフローチャートである。６０５において、ｐiがブートストラップノードと交信する。６１０において、集中ピア発見が使用されるかどうかを決定するテストが実行される。集中ピア発見が使用される場合、６１５において、空スロット／接続が、潜在的プリエンプト可能な子ピアのリスト／キューとともに、ブートストラップノードによってｐiに与えられる。その後、６３５において、ｐiは、有権利ピアとしてのｒi個の潜在的ピア、および超過ピアとしてのｅi個の潜在的ピアと交信する。集中ピア発見が使用されない場合、６２０において、分散ピア発見が使用されるかどうかを決定するテストが実行される。分散ピア発見が使用される場合、６２５において、ランダムピアのリスト／キューの識別（ｉｄ）がｐiに与えられる。６３０において、ｐiは、空スロット／接続を有するピアおよび潜在的にプリエンプト可能なピアのリスト／キュー内のすべてのピアを調査する。
【０１００】
その後、６３５において、ｐiは、有権利ピアとしてのｒi個の潜在的ピア、および超過ピアとしてのｅi個の潜在的ピアと交信する。分散ピア発見が使用されない場合、デフォルトで半分散ピア発見が使用される。６４０において、ネットワーク内のＮ個のピアがｐiに与えられる。その後、６４５において、ＩはＮ個のピアすべてを調査し、それらＮ個のピアの子またはｐiから１ホップ離れた潜在的ピアの子の中で、空スロットまたは潜在的にプリエンプト可能な子ピアを見つける。その後、６３５において、ｐiは、有権利ピアとしてのｒi個の潜在的ピア、および超過ピアとしてのｅi個の潜在的ピアと交信する。
【０１０１】
本発明では、従来の非コントリビューション認識のピアツーピアストリーミングスキーマよりも長いスタートアップ遅延／待ち時間を有することがあることに留意されたい。親ピアを見つけるプロセスは、より長いスタートアップ遅延の一因となる。また、異なるピア発見スキーマによって、異なる待ち時間が生じる。集中ピア発見スキーマおよび半分散ピア発見スキーマは、ルートから開始する拡散ツリーのトラバースに、分散ピア発見スキーマよりも短いスタートアップ／加入待ち時間を要する。しかし、本発明のコントリビューション認識ピアツーピアライブストリーミング方法は、ＭＤＣ（多重記述符号化：ｍｕｌｔｉｐｌｅ  ｄｅｓｃｒｉｐｔｉｏｎ  ｃｏｄｉｎｇ）を使用して、基礎をなすデータを符号化するので、ピアは、最初の記述を受信するといつでも、再生を開始することができる。これは潜在的に、スタートアップ／待ち時間を短縮することができる。
【０１０２】
本発明では、ピアのプリエンプションポリシーは、追加のピアチャーニングを引き起こすことがある。例えば、要求ピアが、すでに親ピアに接続されている子ピアをプリエンプトする場合、プリエンプトされた子ピアは、別の親ピアへの加入を試みる必要があり、したがって、システムに追加のチャーニングを追加する。このプロセスは、プリエンプトされた子ピアがそれ自体のための空スロットを別の親ピアにおいて見つけるまで継続されることがある。
【０１０３】
プリエンプトされている接続が「超過接続（ｅｘｃｅｓｓ  ｃｏｎｎｅｃｔｉｏｎ）」である場合、ピアはこの接続をまず第１にもつべきとは見なされないので、これはそれほど大きな影響をもたない。この問題を緩和する１つの方法はプリエンプションポリシーを修正することである。本発明のプリエンプションポリシーは、「有権利接続（ｅｎｔｉｔｌｅｄ  ｃｏｎｎｅｃｔｉｏｎ）」が別の「有権利接続」をプリエンプトすることを許可しない。また、ＭＤＣを使用してストリームデータを符号化するため、チャーンの影響はそれほど深刻でないこともある。ピアがいくつかの記述を喪失した場合、表示品質は劣化することになるが、ストリームは依然として視認可能である。
【０１０４】
次に、コントリビューション認識機構をメッシュベースのＰ２Ｐストリーミングに関連して説明する。説明される機構は主に、従来技術のツリーベースのＰ２Ｐストリーミングアプローチに類似したスキーマに端を発するものであるが、いくつかの注目すべき相違が存在する。ツリーベースのアプローチでは、コンテンツの特定の記述は、各ツリーを介して配信される。したがって、各ピアは、適切な数のツリーに加入すべきであり、また１つのツリーにおける内部ノードとして機能すべきである。このアプローチによって、以下のような、メッシュベースのストリーミングには存在しないいくつかの問題が生じる。
【０１０５】
第１に、ツリーベースのアプローチでは、その受信品質を改善するために、各ピアは、新しいツリー内で親を見つける必要があるが、メッシュベースのアプローチでは、任意の新しいピアが、親として機能することができる。第２に、ツリーベースのアプローチのローカルプリエンプションポリシーは、貢献ピア（ｃｏｎｔｒｉｂｕｔｏｒ  ｐｅｅｒ）と非貢献ピア（ｎｏｎ−ｃｏｎｔｒｉｂｕｔｏｒ  ｐｅｅｒ）の有権利接続を区別する必要がある。これが今度は、ポリシーによって対処されるべき新しいシナリオを追加する。第３に、ツリーベースのアプローチでは、各接続は、有権利または超過と具体的にレベル付けされる必要がある。
【０１０６】
これに対して、本発明のメッシュベースのアプローチでは、超過接続の（識別ではなく）数を、単に、ピア毎に接続の実際の数と有権利接続の数の差によって決定する（すなわち、ａi＞Ｒiのとき、ｅi＝ａi−Ｒi）。
【０１０７】
本発明のアプローチとツリーベースのアプローチの別の重要な相違は、実際の貢献（ｆi）の代わりに、意欲（Ｗi）を使用して、式（１）および式（２）におけるピアの有権利着信度数を決定することである。各ピアの実際の貢献が常にその意欲より小さいとすると（すなわち、ｆi＜Ｗi）、実際の貢献の使用には以下の２つの副次的な影響がある。（ｉ）システム内の利用可能なリソースが、式（１）および式（２）の第２項において過小評価される（すなわち、以下である）。
【０１０８】
【数３】
2010515113.tif 000008
【０１０９】
これは、親発見プロセス中に、個々のピアによる、より保守的な（ｃｏｎｓｅｒｖａｔｉｖｅ）挙動をもたらす。（ｉｉ）ピアｉの実際の貢献は、その発信帯域幅を使用する他の参加ピアの能力および需要に依存し、（ｉｉｉ）効果的なチャーン（すなわち、子ピアの離脱）によって、システム内でより大きなダイナミクスをもたらすｆiの一時的な低下が発生する。研究によって、様々な実施形態においてこのアプローチは、親発見の速度を低下させ、ピアの数（したがって、利用可能なリソース）が絶えず変化するダイナミックな環境では不適切であることが示されている。
【０１１０】
上述の汎用的なコスト関数／タックス関数によって、ピアを許可するオペレーションが調整される。この関数のｔパラメータの選択によって、本発明の様々な実施形態の特性を決定することができる。したがって様々な実施形態では、タックスレート（ｔ）が変化するときのコスト関数／タックス関数（すなわち式（１））の異なる挙動、およびその挙動に対する主要パラメータ（例えばＷi）の影響を示す。タックス／コスト関数の挙動の理解は、パラメータ空間にわたって個々のピアが着信度数をどのように決定するかについての決定を可能にし、それは、コントリビューション認識機構の性能を評価する際に非常に有益である。
【０１１１】
図７Ａ〜図７Ｃは、本発明の様々な実施形態による、リソースインデックス（ＲＩ：ｒｅｓｏｕｒｃｅ  ｉｎｄｅｘ）が０．５、Ｍａｘが１６である場合の、異なる値のＷiを有するタックス関数／コスト関数の挙動を示す。
【０１１２】
Ｎ個のピアからなるグループと、それらの貢献意欲のレベル（Ｗi）を与えると、シナリオのＲＩは、リソースの総需要に対する利用可能なリソース（ΣＷi）の比として定義される。様々な実施形態では、すべてのピアは完全な品質のストリームを受信するのに十分な着信帯域幅を有すると仮定し、リソースの総需要は、Ｎ×Ｍａｘとして単純に決定することができる。したがって、所与のシナリオにおけるＲＩの値は、以下である。
【０１１３】
【数４】
2010515113.tif 000009
【０１１４】
この定義を、式（１）に代入することができ、その場合、式は、以下のように書き直すことができる。
【０１１５】
【数５】
2010515113.tif 000010
【０１１６】
式（５）は、ピアｉの有権利度数を、次のパラメータ、すなわち、ピアの意欲（Ｗi）と、オーバレイにおけるリソースインデックス（ＲＩ）と、（ストリーム帯域幅に基づいた）最大度数Ｍａｘとに基づいたタックスレートｔの関数として表している。図７Ａは、ＲＩ＝０．５、ＲＩ×Ｍａｘ＝８のときの異なる値のＷiについて、Ｒi（ｔ）をｔの関数としてプロットしている。この図は、以下のようなタックス関数のいくつかの重要な特性と、異なるパラメータに対するその依存性を明らかにしている。
【０１１７】
第１に、タックスレートが増大するにつれて、すべてのピアの有権利度数は、初期値に関わらず、ＲＩ×Ｍａｘという同じ値に収束する。高帯域幅のピア（Ｗi＞ＲＩ×Ｍａｘ）の場合、有権利度数は、タックスレートにつれて徐々に減少するが、低帯域幅のピア（Ｗi＜ＲＩ×Ｍａｘ）の場合、有権利度数は、タックスレートにつれて徐々に増大する。当業者であれば、ｔが増大するにつれて、式の第１項は急速に減少し、第２項はＲＩ×Ｍａｘに収束することに気づくであろう。
【０１１８】
第２に、タックスレートが増大するときの有権利度数の変化率は、ピアの意欲（すなわちＷi）に依存する。より大きな値のＷiは、図７Ａに示されるように、より速い収束をもたらす。
【０１１９】
第３に、ＲＩ×Ｍａｘの値は、すべてのピアの有権利度数の最終的な値を決定する。したがって、リソースまたはストリーム帯域幅の利用可能性の変化は、この図における収束値をしかるべく上下に単純にシフトさせる。第４に、上で指摘したように、式（５）のｆｌｏｏｒ（Ｒi）の値は、利用可能なリソースの過大評価を防止するために使用される。図７Ｂは、式（５）のｆｌｏｏｒ（Ｒi）を示している。これは、異なる値のＷiについて、ｆｌｏｏｒ（Ｒi）演算が、タックスレート／コストファクタの関数として有権利度数の展開（ｅｖｏｌｕｔｉｏｎ）にどのように影響するかを示している。
【０１２０】
第５に、上述のように、あるピアの有権利度数が完全な品質のストリームを受信するのに必要な最大度数より大きい、すなわち、Ｍａｘ≦Ｒiである場合、該ピアを飽和（ｓａｔｕｒａｔｅ）させることができる。ピアの８０％が高帯域幅を有し、残りのピアが低帯域幅を有する例示的な一実施形態によれば、完全な品質のストリームを受信するのに必要な着信度数は８であり、高帯域幅ピアおよび低帯域幅ピアの意欲の度数は、それぞれ２４および４である。本発明の別の実施形態では、高帯域幅ピアおよび低帯域幅ピアは、それぞれ４０および４の発信接続を提供する。飽和ピアの実際の度数は、Ｍａｘまでに制限される。図７Ｃは、いくつかの高帯域幅ピアが飽和している場合のタックス関数／コスト関数の挙動を示している。所与のシナリオにおいてピア（およびその一部）が飽和するかどうかは（ｉ）受信品質、および（ｉｉ）システム内の超過リソース量に影響するので、該所与のシナリオにおいてピア（およびその一部）が飽和するかどうかを決定することが重要であることは、当業者であれば理解されよう。すなわち、図７Ｃは、ピア参加総数および利用可能なリソースが一定であって知られている静的システム、すなわち、基準静的シナリオ（ｒｅｆｅｒｅｎｃｅ  ｓｔａｔｉｃ  ｓｅｎａｒｉｏ）における、タックス関数／コスト関数の挙動を表している。実際には、ピア参加のダイナミクスと、その結果である利用可能なリソースの変動のため、個々のピアに報告されるグループ状態は、完全に正確ではない。したがって、参加ピアの間の平均挙動は、上記の基準ケースとは異なる可能性がある。以下では、様々なシナリオを調べ、対応する基準静的シナリオと比較して、観測された相違をもたらす背後に潜む原因を特定する。
【０１２１】
様々な実施形態において、ピアは、その着信度数をゼロから速やかに増加させて、有権利度数に達し得ることが示された。少なくとも一実施形態では、高帯域幅ピアは、２０秒未満で有権利度数に達することができ、一方、低帯域幅ピアは、１１秒で有権利度数に達することができる。一実施形態では、すべてのピアは、約６０秒でその目標の着信度数に達する。一実施形態によれば、存続期間が６０秒未満のピアは、有権利着信度数に達しない。様々な実施形態では、ピアの着信度数がいったん有権利度数に達すると、そのピアの着信度数は、利用可能なリソースの僅かな変化と超過接続の数の変動のために、有権利度数値の周囲で振動する傾向がある。
【０１２２】
本発明の様々な実施形態の挙動は、シミュレーションを通して評価された。その評価方法を使用して、提案するコントリビューション認識機構の挙動を検査するが、ここでは、例示的な機構がＰＲＩＭＥと呼ばれるメッシュベースＰ２Ｐストリーミング機構に含まれる。メッシュベースＰ２Ｐストリーミング機構において個々のピアに配信される品質は、
（ｉ）ピアがシステムから離脱／システムに加入するときに適切な数の親を維持する能力と、
（ｉｉ）結果のオーバレイを介して参加ピア間にコンテンツを配信する機構の挙動に依存する。
【０１２３】
オーバレイにおける個々のピアとそれらの親との間の接続性は明らかである。様々な実施形態によれば、コントリビューション認識機構は、親選択の戦略（ｓｔｒａｔｅｇｙ）および子プリエンプションポリシーの両方を導入することによって、主としてピア間の接続性に影響する。オーバレイの接続性およびダイナミクスは、コンテンツ配信の性能に影響を与える可能性が高いが、この影響は、コントリビューション認識機構の性能を示すのではなく、むしろオーバレイ接続性およびダイナミクスに対処するＰＲＩＭＥの能力を示す。オーバレイ接続性に対するコントリビューション認識機構の効果に焦点を当てることによって、パケットレベルダイナミクスからの抽象、およびより大きなグループサイズを用いたシミュレーションも可能になる。
【０１２４】
本発明の様々な実施形態についての以下の評価は、ｐｓｉｍと呼ばれるＰ２Ｐセッションレベルのシミュレータ（Ｐ２Ｐ  ｓｅｓｓｉｏｎ−ｌｅｖｅｌ  ｓｉｍｕｌａｔｏｒ）を使用して行われた。ｐｓｉｍは、参加ピア間に対ネットワーク遅延（ｐａｉｒｗｉｓｅ  ｎｅｔｗｏｒｋ  ｄｅｌａｙ）を組み込む、イベントドリブンシミュレータである。さらに、ｐｓｉｍは、展開されたＰ２Ｐストリーミングシステムに関する従来の実験的研究によって報告されるように、ピアセッション時間については（μ＝４．２９、σ＝１．２８の）対数正規分布（ｌｏｇ−ｎｏｒｍａｌ  ｄｉｓｔｒｉｂｕｔｉｏｎ）を使用し、ピア到着時間間隔（ｉｎｔｅｒ−ａｒｒｉｖａｌ  ｔｉｍｅ）をモデル化するために（ａ＝２．５２、ｂ＝１．５５の）パレート分布（Ｐａｒｅｔｏ  ｄｉｓｔｒｉｂｕｔｉｏｎ）を使用することによって、チャーンの現実的なモデルを提供する。パケットレベルダイナミクスからの抽象によって、ｐｓｉｍは、ピアが多数の、またはピア参加のダイナミクスの度合いが高い、シミュレーションシナリオを可能にする。３つのグループの性能メトリックを使用して、コントリビューション認識機構の性能の異なる側面をキャプチャする。
【０１２５】
各ピアの着信度数および発信度数はともに、セッション中に変化する。したがって加重（ｗｅｉｇｈｔｅｄ）着信度数および発信度数を使用して、各ピアによって観測される有効度数をキャプチャする。加重着信度数または発信度数は、各ピアがセッション中の異なる間隔で経験する度数の平均値であり、各度数値は、その度数が維持される時間間隔によって重み付けされる。例えば、あるピアが、そのセッションの半分について３、別の半分について５の発信度数を有する場合、その加重発信度数は４である。
【０１２６】
各ピアの加重着信度数および発信度数は、セッション中のリソースの使用および貢献を定量化する。ピアの加重平均着信度数はさらに、加重平均有権利度数および超過度数に分割される。
【０１２７】
このメトリックは、コントリビューション認識機構がどれだけ良好に参加ピアの発信帯域幅を利用できるかもキャプチャし、すべてのピアにわたる最大発信度数に対する、すべてのピアにわたる総加重発信度数の比として定義される。２つのメトリックを使用して、オーバレイにおける変化の度合いをキャプチャする。  
（ｉ）親の連続的な喪失の間の平均時間と、
（ｉｉ）親の連続的な変更の間の観測時間が少なくとも６００秒であるピアとして識別される、安定なピアのパーセンテージである。
【０１２８】
観測された親の変更は、２つのグループ、すなわち親の離脱に起因する変更と、他の子ピアによるプリエンプションに起因する変更に分類される。コントリビューション認識機構に関連するすべての信号伝達メッセージ関するオーバヘッドは、メッセージ（またはバイト）毎にピア毎秒でキャプチャされる。
【０１２９】
本発明による例示的なコントリビューション認識機構の性能に対する次の各要因の影響は、以下のように評価される。  
（ｉ）親の切断のダイナミクス、
（ｉｉ）コントリビューション認識機構の利点、
（ｉｉｉ）タックスレート／コストファクタおよびピア貢献の効果、
（ｉｖ）システムにおけるリソースインデックス（ＲＩ）、
（ｖ）グループサイズに関するスケーラビリティ、および
（ｖｉ）更新頻度の効果
【０１３０】
各シミュレーションについて報告された結果は、異なるランダムなシード（ｓｅｅｄ）を用いた多数の試行にわたって平均される。ここで提供される説明的で例示的なシミュレーションでは、次のデフォルトパラメータが使用される。すなわち、ストリームレート＝４００Ｋｂｐｓ、グループサイズ＝５００ピア、高帯域幅ピアおよび低帯域幅ピアのアクセスリンク帯域幅が、それぞれ１Ｍｂｐｓおよび１００Ｋｂｐｓである。他の例示的な実施形態では、６００Ｋｂｐｓのストリームレートが利用される。帯域幅毎フローすなわちｂｗｐｆ（すなわち、各ピアの度数に対する帯域幅の比）の値は、５０Ｋｂｐｓに設定される。すべてのシミュレーションでは現実的なチャーンモデルが組み込まれ、該チャーンモデルでは、ピアセッション時間について（μ＝４：２９、σ＝１．２８の）対数正規分布を有し、ピア到着時間間隔をモデル化するために（ａ＝２：５２、ｂ＝１：５５の）パレート分布を有する。チャーンモデルは、展開されたＰ２Ｐストリーミングシステムに関する最近の実験的研究から導き出される。状態の収集および報告は、１０秒毎に１回実行される。各シミュレーションは６０００秒にわたって実行され、情報は、数が所望の目標に達した安定状態の間に収集される。本発明の一実施形態では、長期間存続する親子の間の接続は、総リソースが変化しない限り、損なわれずに存続する。本発明の別の実施形態では、更新間隔の増大によって、有権利度数に著しい低下が引き起こされ、超過度数には対応する僅かな増加が伴う。
【０１３１】
図８Ａおよび図８Ｂは、一実施形態によれば、存続期間中の典型的な低貢献と高貢献の着信度数をそれぞれ示している。タックスレート／コストファクタは４に設定され、高貢献の発信度数は２４であり、一方、低貢献の発信度数は４である。このシナリオでは、高貢献は１１の権利を有し、低貢献は６の権利を有する。典型的な挙動として、ピアは、ゼロから開始し、短期間（高貢献の場合は２０秒未満、低貢献の場合は１１秒未満）に親の有権利数に達する。図８Ａに示されるように、ピアは、その着信度数を増加させ、いくつかの超過接続を獲得するが、これらの超過接続は安定的ではなく、要求されると、他の有権利接続によってプロエンプトされることがある。
【０１３２】
当業者であれば、ピアが速やかに平均の度数を増加させることを理解されよう。これを説明するため、１０秒間隔以内の存続期間を有するピアの加重平均度数を示す。図８Ｃは、異なる存続期間を有するピアの平均着信度数を示している。
【０１３３】
ピアの加重平均（着信または発信）度数は、ピアがその度数を維持する間隔で各度数を加重することによる、その有効平均度数を表す。例えば、ピアがそのセッション時間の４分の１は３の発信度数を有し、セッション時間の残りは５を有する場合、その加重発信度数は４．５である。本発明の一実施形態によれば、各ピアの加重着信度数および発信度数は、セッション中のリソースの利用および貢献をそれぞれ定量化する。様々な実施形態では、加重平均着信度数は、加重平均有権利度数および平均超過度数に含まれる。
【０１３４】
図８Ｃから明らかなように、存続期間が５０ミリ秒未満の例示的なピアは、有権利接続に基づいた平均数の着信接続を受信するのに十分なほど長くはシステム内に留まらない。
【０１３５】
コントリビューション認識ピアツーピアの許可の利点は、本発明の様々な実施形態によれば、８０％の低帯域幅ピアおよび２０％の高帯域幅ピアからなるグループ内の参加ピア間にリソースを分散させることに対する、コントリビューション認識機構の効果について調べる。タックスレート／コストファクタは２であり、高帯域幅ピアは２４接続まで提供し、一方、低帯域幅ピアは４接続まで提供する。他のすべてのパラメータは、そのデフォルト値である。
【０１３６】
図９Ａは、タックスレート／コストファクタが２であるときに、コントリビューション認識機構を用いた場合（Ｃｏｎｔ．＊とラベル付け）、およびコントリビューション認識機構を用いない場合（Ｎｏ−Ｃｏｎｔ．＊とラベル付け）の高帯域幅ピアおよび低帯域幅ピアの間の加重平均着信度数の累積分布関数（ＣＤＦ：ｃｕｍｕｌａｔｉｖｅ  ｄｉｓｔｒｉｂｕｔｉｏｎ  ｆｕｎｃｔｉｏｎ）を示している。この図は、コントリビューション認識機構が存在しない場合、高帯域幅ピアおよび低帯域幅ピアの着信度数の分布は同様であり、したがって、リソースの割当ては、参加ピアの貢献に依存しないことを示している。対照的に、高帯域幅ピアおよび低帯域幅ピアの度数分布は、明らかに離れているが、各グループ内ではかなり一様であり、すなわち、すべての低帯域幅ピアは６に近い度数を有し、一方、すべての高帯域幅ピアの度数は１５に非常に近い。
【０１３７】
異なるプリエンプションポリシーの重要度を定量化するため、２つの他のシナリオを説明するが、Ｅｘ−ＥｘおよびＥｎ−Ｅｎシナリオでは、プリエンプションは発生しない。図９Ａは、これら２つのシナリオにおける高帯域幅ピアおよび低帯域幅ピアの両方に関する度数分布のＣＤＦを示している。その結果は、Ｅｘ−ＥｘおよびＥｎ−Ｅｎプリエンプションシナリオの執行が、加重平均着信度数の分布に関してどのような性能改善も引き起こさないように見えることを示している。言い換えると、良好な性能を達成するには、Ｅｎ−Ｅｘポリシーで十分である。
【０１３８】
図９Ｂは、チャーンに起因する個々のピアによって観測された接続切断の平均率の分布を示している。各ピアのチャーンに起因する切断率は、その着信度数に直接比例し、正規化された値が、図９Ｂに提示されている。図９Ｂは、チャーンに起因する平均切断率の分布が、ピア帯域幅に依存せず、コントリビューション認識機構を用いても変化しないことを示している。
【０１３９】
図９Ｃは、基本シナリオならびにＥｘ−ＥｘおよびＥｎ−Ｅｎがともに無効にされたシナリオにおける、高帯域幅ピアおよび低帯域幅ピアの間の参加ピア間における親の平均切断率の分布を提示している。この図は、基本ケースでは、ピアの低帯域幅実施形態がより高いプリエンプション率を観測することを示している。この状態は、Ｅｎ−Ｅｎのプリエンプションポリシーを無効にした後であっても持続する。しかし、他のすべてのケースでは、観測される切断率は同様である。このパラメータ設定では、高帯域幅ピアの接続は有権利であり、したがって、それらは重大なプリエンプションを観測しないことに留意されたい。
【０１４０】
図９Ｂと図９Ｃの比較によって、プリエンプションに起因する親の接続切断率は、チャーンに起因する親の接続切断よりもおおよそ２０倍高いことが明らかになる。言い換えると、プリエンプションポリシーは、チャーンのみに起因する観測率を超えて、全体的な切断率を著しく増大させる。観測率は各ピアの超過度数の相対数に依存するので、図９Ｃにおけるプリエンプションに起因する切断率の正規化は意味がないことに留意されたい。
【０１４１】
【表４】
2010515113.tif 000011
【０１４２】
表３は、（原因に関わらず）連続的な切断の間の観測時間が少なくとも６００秒であるピアのパーセンテージを示すことによって、グループレベルの安定性の概要を示す。表の各行は、（プリエンプションポリシーの様々な組合せを含む）コントリビューション認識機構を用いたシナリオ、および用いないシナリオの異なるシナリオを表す。
【０１４３】
表３は、コントリビューション認識機構が存在しない場合、ピアの２９％しか安定ではないことを示している。Ｅｎ−ＥｘおよびＥｘ−Ｅｎポリシーのみを用いるコントリビューション認識機構の使用は、安定ピアのパーセンテージを僅かに低下させ、２４％にする。しかし、他の任意のポリシーの追加は、安定ピアのパーセンテージに著しい低下をもたらす。Ｅｎ−ＥｎおよびＥｘ−Ｅｘポリシーは、コントリビューション認識機構の性能に影響を与えず、オーバレイの非安定性を著しく増大させるので、これらのポリシーは、残りの評価において提示される実施形態では排除される。
【０１４４】
次に、本発明の様々な実施形態では、シナリオを決定する主要パラメータとして、
（ｉ）構成パラメータであるタックスレート／コストファクタの値ｔ、および
（ｉｉ）ピアの貢献意欲の値（Ｗi）
を用いるコントリビューション認識機構の挙動の変化に関して調べる。
【０１４５】
以下の説明は、Ｍａｘ＝１６、リソースインデックス（ＲＩ）が０．５、ｂｗｐｆ＝５０Ｋｂｐｓであり、５００個のピアが８０％の低帯域幅ピアおよび２０％の高帯域幅ピアからで構成されると仮定する。当業者であれば、高帯域幅ピアおよび低帯域幅ピアの発信帯域幅について、以下のような３つの異なるシナリオが（ｂｗｐｆに対する発信度数の比である対応する貢献Ｗiとともに）提示されることが理解されよう。  
シナリオＳ１：８００Ｋｂｐｓおよび３００Ｋｂｐｓ（ＷＨ1＝１６，ＷＬ1＝６）
シナリオＳ２：１．２Ｍｂｐｓおよび２００Ｋｂｐｓ（ＷＨ2＝２４，ＷＬ1＝４）
シナリオＳ３：１．６Ｍｂｐｓおよび１００Ｋｂｐｓ（ＷＨh＝３２，ＷＬ1＝２）
【０１４６】
ここで、ＷＨiおよびＷＬiは、高帯域幅ピアおよび低帯域幅ピアの貢献をそれぞれ表すことに留意されたい。リソース（またはＲＩ）の総量はこれら３つのシナリオで一定のままであるが、帯域幅の不均一性のレベルが、それらの間で著しく変化し、ピア間における最大発信度数の分布を決定することに留意されたい。したがって、これらのシナリオにわたるシステムの性能の検査は、ピア間におけるＷiの分布がどのようにシステム性能に影響するかを明らかにする。
【０１４７】
図１０Ａは、基準とする式（２）に基づいて、異なるタックスレート／コストファクタ値を有する３つのシナリオのすべてにおける、高帯域幅ピアおよび低帯域幅ピアの有権利度数を示している。図１０Ｂは、シミュレーションにおけるタックスレート／コストファクタの関数として、３つのシナリオのすべてにおける、高帯域幅ピアおよび低帯域幅ピアの間の加重平均有権利度数を示している。これら２つの図の比較は、高帯域幅ピアおよび低帯域幅ピアの間の加重平均有権利度数が、興味深いことに、ピア間の接続性におけるダイナミクスの存在にもかかわらず、式（２）によるその推定値に密接に従うことを示している。本発明の一実施形態では、非常に小さなタックス値を除いて、有権利度数および総度数の平均値は、実質的に同様である。例示的な本発明の一態様では、コストファクタ／タックスレートが小さい場合、高帯域幅ピアの有権利度数は飽和し、高帯域幅ピアは超過接続を必要としない。
【０１４８】
一実施形態では、飽和ピアは有権利度数を使用せず、超過リソースがシステム内で利用可能になり、超過リソースの量は（Ｒｉh−Ｍａｘ）に比例する。低帯域幅ピアは、超過接続を形成するために、これらの超過リソースを利用することができる。本発明の一実施形態では、高帯域幅ピアが飽和しない限り、高帯域幅ピアおよび低帯域幅ピアの両方の平均超過度数は、実質的に同じであり、タックスレート／コストファクタおよびピア貢献の分布の変化に実質的に反応しない。一実施形態では、コントリビューション認識機構は、超過リソースを参加ピアの間に実質的に均等に分配する。さらなる一実施形態では、高帯域幅ピアおよび低帯域幅ピアによる貢献リソースの不均一性は、総貢献リソースが実質的に一定に留まるように、比例的に調整される。
【０１４９】
図１０Ｃは、３つのシナリオにおける、高帯域幅ピアおよび低帯域幅ピアの間の総着信度数（有権利および超過の両方）の加重平均を提示している。この図は、有権利度数および総度数の平均値が非常に類似して見えることを示している。ピアの各グループにおける有権利度数および超過度数の変化のダイナミクスをさらに調べる。
【０１５０】
図１０Ｄおよび図１０Ｅは、高帯域幅ピアおよび低帯域幅ピアそれぞれの有権利度数および超過度数の両方の加重平均値を示している。これら２つの図における超過度数の調べることによって、次の点が説明される。第１に、高帯域幅ピアおよび低帯域幅ピアの両方について、加重平均超過度数は、高帯域幅ピアが飽和しない限り（すなわち、ｔ＞３）、ピア貢献の分布に伴って（シナリオ間で）変化しないことである。
【０１５１】
高帯域幅ピアが飽和していない場合、コントリビューション認識機構は、有権利度数を制御することによって、利用可能なリソースを効果的に管理する。したがって、超過リソースの唯一の原因は、（ｆｌｏｏｒ（）に起因する）有権利度数の丸め（ｒｏｕｎｄｉｎｇ）である。これは、制限された量の超過リソースのみを提供し、このことは、すべてのシナリオにわたってこの領域（ｔ＞３）の小さな超過度数を有する理由を説明する。さらに、これらの図は、すべてのピアが同数の超過接続を有するため、コントリビューション認識機構がすべてのピアの間に超過リソースを均等に分配できることを示している。第２に、タックスレート／コストファクタが小さい場合、高帯域幅ピアの有権利度数は飽和し、したがって、該ピアは超過接続を必要としない。飽和ピアは有権利度数を使用しないので、超過リソースがシステム内で利用可能になり、超過リソースの量は（ＷＨi−Ｍａｘ）に比例する。低帯域幅ピアは、図１０Ｅに示されるように、これらの超過リソースを超過接続として利用することができる。
【０１５２】
図１１Ａは、３つのシナリオについて、タックスレートの関数としての高帯域幅ピアおよび低帯域幅ピアの間の平均発信度数を有する、様々な重み付けされた実施形態のシステム利用度を示している。この図は、すべてのシナリオにおけるピアの発信度数が、貢献への意欲（Ｗi）に非常に近いこと、すなわち、コントリビューション認識機構は、ピア間の接続性のダイナミクスに関わらず、リソースの異なる分配に利用可能なリソースを効果的に利用できることを明らかに示している。図１１Ｂは、単一の時間スナップショットにおけるシステムリソースの全体的な利用度、すなわち、オーバレイの１つのスナップショットにおけるすべてのピアの間の発信度数の利用度を提示している。この図は、高帯域幅ピアが飽和していない場合、リソースは実質的に完全に利用されていることを示している。飽和領域では、リソースの全体的な利用度は、超過接続のダイナミクスのために僅かに低下する。飽和領域では、システム内のリソースの相対的に大きな部分が、超過接続によって利用される。超過接続の部分が増大するにつれて、拒否された超過接続の待機時間を適応させる際の指数的バックオフが、未使用リソースおよびより低い利用度をもたらすことがあり得る。本発明の一実施形態によれば、超過リソースの部分が増大するにつれて、超過接続を求める要求が拒否される確率が増大する。これは、拒否された超過接続の待機時間を適応させる際のバックオフが原因で、リソースの利用度を低下させる。
【０１５３】
【表５】
2010515113.tif 000012
【０１５４】
図１１Ｃは、３つのシナリオのすべてにわたる、６のタックスレート／コストファクタの関数としてのプリエンプションに起因する高帯域幅ピアおよび低帯域幅ピアの間の平均切断率を示している。この図は、高帯域幅ピアまたは低帯域幅ピアについて、プリエンプションが引き起こす、親からの接続性のダイナミクスの平均レベルを定量化する。高帯域幅ピアは、飽和領域にある（すなわち、ＷＨi＞Ｍａｘ）間、プリエンプトされ得ない有権利接続だけを確立するので、プリエンプションを全く経験しない。したがって、本発明の一実施形態では、高帯域幅ピアは、プリエンプトされ得ない有権利接続だけを確立するので、プリエンプションを全く経験しない。
【０１５５】
しかし、飽和領域外では、高帯域幅ピアは、タックスレート／コストファクタの増大につれて徐々に低下する、親の間の接続のかなりの切断率を経験する。低帯域幅ピアの場合、リソースのコンテンションがあまりなく、したがってプリエンプションの必要性がないので、飽和領域内において観測される切断率は小さい。異なるシナリオにおいて、タックスレート／コストファクタが増大するにつれて、平均切断率は一定に留まるようになる。さらに、（図１０Ｄおよび図１０Ｅに示されるように飽和領域外では）すべての参加ピアは平均的に同数の超過接続を有するが、図１１Ｃは、高帯域幅ピアが驚くほどより高い切断率を観測することを明らかにする。本発明の一実施形態によれば、飽和領域外では、低帯域幅ピアの間の平均の親切断率は、コストファクタ／タックスレートに実質的に反応しない。
【０１５６】
本発明の一実施形態では、より大きな総ピア度数は、より高い親切断率をもたらす。ダイナミクスのレベルにおいて観測される傾向を説明するため、個々の接続のタイプ（すなわち、有権利と超過）は、本明細書で示されるように、メッシュベースＰ２Ｐストリーミングにおけるコントリビューション認識機構によって明示的に指定されないことに留意されたい。各親ピアは、プリエンプションの決定を行うために（最新の更新に基づいた）現在の子の超過接続および有権利接続の数だけを使用するので、２つの親が、共通の子の最新の更新を利用し、この子に対する接続を同時にプリエンプトする（すなわち切断する）可能性が高い。そのようなイベントの可能性は、子ピアの着信度数に比例する。したがって、一般に、飽和領域外では、より大きな数の着信度数を有するピア（高帯域幅ピア）は、より高頻度のプリエンプションを観測し、これは、着信度数が減少するにつれてタックスレート／コストファクタだけ減少する。
【０１５７】
次に、ＲＩの変化が、システムの様々な実施形態の主要な性能メトリックにどのように影響するかを調べる。ここで使用される例示的なパラメータは、表４に要約されている。Ｍａｘ＝１６、ｂｗｐｆ＝２５Ｋｂｐｓ、グループサイズが５００であると仮定する。各ＲＩについての高帯域幅ピアおよび低帯域幅ピアの分布は、従来技術で知られているこれまでの現世界のトレースから導き出される。
【０１５８】
図１２Ａは、基準として式（２）に基づいて計算された、異なるＲＩを有する高帯域幅ピアおよび低帯域幅ピアの有権利度数を示している。図１２Ｂは、タックスレート／コストファクタの関数として異なるＲＩを用いるシナリオにおける、高帯域幅ピアおよび低帯域幅ピアの加重平均有権利度数を示している。これら２つの図の比較は、高帯域幅ピアおよび低帯域幅ピアの加重平均有権利度数が、式（２）から導き出された、対応する値に従うことを明らかにする。一実施形態では、切断の頻度は、単一のピアによって観測された連続するプリエンプションの間の平均時間の逆数値であり、それは次に、すべてのピアにわたって平均される。図１２Ａおよび図１２Ｂが示すように、ＲＩ＞０：８であるシナリオにおける高帯域幅ピアの有権利度数は、上限を９とするタックスレート／コストファクタ範囲で飽和する。これは、高帯域幅ピアの飽和領域が拡大し、それが他のメトリックに影響することを示している。
【０１５９】
図１２Ｃおよび図１２Ｄは、高帯域幅ピアおよび低帯域幅ピアの平均有権利度数および超過度数をそれぞれ示している。図１２Ｃに示されるように、高帯域幅ピアは、より高いリソースインデックスシナリオの飽和領域の拡大のために、上限を９とするタックスレート／コストファクタ範囲では超過接続をもたない。他方、図１２Ｄは、低帯域幅ピアが、飽和を補償して利用可能なリソースを利用するために、より多くの超過接続を取得することを明らかにする。
【０１６０】
図１２Ｅは、タックスレート／コストファクタの関数として異なるＲＩを用いるシナリオの高帯域幅ピアおよび低帯域幅ピアの平均発信度数を示している。この図は、タックスレート／コストファクタおよびＲＩにかかわらず、高帯域幅ピアおよび低帯域幅ピアの平均発信度数がその貢献に近いことを明らかに示している。より小さいタックスレート／コストファクタでは、高帯域幅ピアの平均発信度数の僅かな低下が存在する。
【０１６１】
図１２Ｆは、スナップショットにおけるリソースの利用度を示している。この図も、飽和領域ではリソースの全体的な利用度が低下することを明らかにする。上述したように、ＲＩ＞０：８のシナリオでは、高帯域幅ピアは飽和領域にあり、したがって、（図１２Ｄに示される）低帯域幅ピアには多くの超過接続が存在する。
【０１６２】
様々な実施形態のシミュレーションは、より低いタックスレート／コストファクタの効果を明らかにする。拒否された超過接続の待機時間を適応させる際の指数的バックオフは、利用可能なリソースの低い利用度をもたらす可能性がある。
【０１６３】
スケーラブルなコントリビューション認識機構の効果を、以下のように調べる。参加数は１００ピアから１０００ピアまで変化し、異なる性能メトリックの結果が検査される。ＲＩ＝０．５、Ｍａｘ＝１６、ｂｗｐｆ＝５０Ｋｂｐｓであると仮定する。高帯域幅ピアは、最大で２４接続まで貢献し、低帯域幅ピアは、最大で４接続まで貢献する。
【０１６４】
図１３Ａは、タックスレート／コストファクタの関数として異なるグループサイズを有するシナリオの高帯域幅ピアおよび低帯域幅ピアの加重平均着信度数を示している。この図は、グループサイズに関わらず、コントリビューション認識機構が適切に機能することを明らかに示している。図１３Ｂおよび図１３Ｃは、高帯域幅ピアおよび低帯域幅ピアの平均有権利度数および超過度数をそれぞれ示している。これらの図は、異なるグループサイズの低帯域幅ピアおよび高帯域幅ピアの平均有権利度数および超過度数が近いことを明らかに示す。当業者であれば、コントリビューション認識機構がスケーラブルであり、異なるグループサイズを用いたシナリオにおいて機能することを理解されよう。
【０１６５】
全体的な性能に対する更新間隔の効果は以下のようである。更新間隔を、本発明のそれぞれの実施形態によって、１０秒から１２０秒まで変化させる。すべてのシミュレーションにおいて、ＲＩ＝０：５、Ｍａｘ＝１６、ｂｗｐｆ＝５０Ｋｂｐｓである。高帯域幅ピアの度数は２４であり、低帯域幅ピアの度数は４である。
【０１６６】
図１４Ａは、タックスレート／コストファクタの関数として異なる更新間隔を用いたシナリオの高帯域幅ピアおよび低帯域幅ピアの平均着信度数を示している。明らかに、この図は、ピアの平均度数が、更新間隔に関わらず、同じ傾向に従うことを示している。図１４Ａは、更新間隔を増大させることによって、ピアの平均着信度数が最大２０％減少することを明らかにする。
【０１６７】
図１４Ｂおよび図１４Ｃは、高帯域幅ピアおよび低帯域幅ピアの着信度数の有権利接続および超過接続への分離をそれぞれ示している。興味深いことに、これらの図は、更新間隔を増大させることによって、平均有権利接続が著しく減少することを明らかにする。他方、平均超過接続は、更新間隔を増大させることによって僅かに増大する。
【０１６８】
更新間隔を増大させることによって、システムワイドな情報のより長い伝播または収集の結果である、２つの主要な問題が生じることがある。  
（ｉ）ピア毎の情報の収集期間の増大が原因で、ブートストラップノード／ピアは、オーバレイ全体の正確なビューを有することができず、その保存された情報が曖昧になることがある。結果として、ブートストラップノード／ピアは、ピアが新たな子ピアを受け入れるための空スロットを有している、または、ピアがプリエンプトされて別の有権利ピアによって置き換えられる超過接続を有していると誤って仮定することがある。どちらのケースでも、ブートストラップノード／ピアが新たなピアに送信する情報は不正確である。  
（ｉｉ）情報をブートストラップノード／ピアから個々のピアに伝播する長い期間のために、全てのリソース（
【０１６９】
【数６】
2010515113.tif 000013
【０１７０】
）における一時的な変化が、式（２）によって計算された各ピアの有権利接続に誤って影響することがある。したがって、一時的な変化は、より長い時間のピアに影響し、有権利接続の公平な割り当てを取得するその能力を低下させることがある。
【０１７１】
より具体的には、より少数の有権利接続では、ピアは、（図１４Ｂに示されるように平均超過接続の増加によって）より多くの超過接続を確立しようと試みる。超過接続を探しているピアは、他の超過接続をプリエンプトすることができず、総着信度数が低くなることに留意されたい。驚くべきことに、上述の問題はともに、短期存続ピアの実施形態の性能に主として影響する。
【０１７２】
図１４Ｄおよび図１４Ｅは、高帯域幅ピアおよび低帯域幅ピアの加重平均着信度数を存続期間の関数としてそれぞれ示している。１０００秒を超えるとピアの着信度数に変化はないので、ｘ軸を１０００秒のところで切っている。これらの図では、選択されたタックスレート／コストファクタは４であり、この特定の結果について、他のタックスレート／コストファクタとの間に大きな相違は存在しない。これらの図は、以下の２つの重要な点を示している。  
（ｉ）長期存続ピアの平均着信度数は、更新期間が異なっても変化しないこと。
（ｉｉ）短期存続ピアは、更新期間が増大するにつれて、着信度数がより低いこと。
【０１７３】
この現象の説明として、図１４Ｆは、異なる存続期間のすべてのピアに関する正規化されたチャーンの頻度を示している。明らかに、この図は、存続期間がより長いピアがより少ないチャーンを観測することを示している。したがって、最終的に長期存続ピアが互いに接続する傾向にあることは明らかである。したがって、長期存続ピアは、あまり頻繁にはチャーンが原因で親を喪失することがなく、このことは、ブートストラップノードからの曖昧な情報が、それらの接続性に劇的には影響しない傾向にあることを意味する。他方、長期存続ピアは有権利接続の不正確な計算の悪影響を打ち消すほど十分長くシステム内に留まるので、リソースの一時的な変化が、長期存続ピアに著しく影響することはない。
【０１７４】
本発明は、様々な形態のハードウェア、ソフトウェア、ファームウェア、専用プロセッサ、またはそれらの組合せで実装され得ることを理解されたい。好ましくは、本発明は、ハードウェアとソフトウェアの組合せとして実装される。さらに、ソフトウェアは、好ましくは、プログラム記憶装置上に明白に具現化されるアプリケーションプログラムとして実装される。アプリケーションプログラムを、任意の適切なアーキテクチャを備えるマシンにアップロードし、そのマシンによって実行することができる。好ましくは、マシンは、１つまたは複数の中央処理装置（ＣＰＵ）、ランダムアクセスメモリ（ＲＡＭ）、および入出力（Ｉ／Ｏ）インタフェースなどの、ハードウェアを有するコンピュータプラットフォームで実装される。コンピュータプラットフォームは、オペレーティングシステムおよびマイクロ命令コードも含む。本明細書で説明された様々なプロセスおよび機能は、オペレーティングシステムを介して実行される、マイクロ命令コードの一部もしくはアプリケーションプログラムの一部（またはそれらの組合せ）とすることができる。加えて、コンピュータプラットフォームには、追加のデータ記憶装置およびプリント装置など、他の様々な周辺装置を接続することができる。
【０１７５】
添付の図面に示された構成要素であるシステムコンポーネントおよび方法のステップの一部は、好ましくはソフトウェアで実装されるので、システムコンポーネント（またはプロセスステップ）の間の実際の接続は、本発明がプログラムされる方法に応じて異なることがあることをさらに理解されたい。本明細書の教示を与えることで、当業者であれば、本発明の上記および類似の実施形態および構成を考えることができよう。
【図１】
2010515113.tif 000017
【図２】
2010515113.tif 000018
【図３Ａ】
2010515113.tif 000019
【図３Ｂ】
2010515113.tif 000020
【図３Ｃ】
2010515113.tif 000021
【図３Ｄ】
2010515113.tif 000022
【図３Ｅ】
2010515113.tif 000023
【図４Ａ】
2010515113.tif 000024
【図４Ｂ】
2010515113.tif 000025
【図４Ｃ】
2010515113.tif 000026
【図４Ｄ】
2010515113.tif 000027
【図５Ａ】
2010515113.tif 000028
【図５Ｂ】
2010515113.tif 000029
【図５Ｃ】
2010515113.tif 000030
【図５Ｄ】
2010515113.tif 000031
【図６】
2010515113.tif 000032
【図７Ａ】
2010515113.tif 000033
【図７Ｂ】
2010515113.tif 000034
【図７Ｃ】
2010515113.tif 000035
【図８Ａ】
2010515113.tif 000036
【図８Ｂ】
2010515113.tif 000037
【図８Ｃ】
2010515113.tif 000038
【図９Ａ】
2010515113.tif 000039
【図９Ｂ】
2010515113.tif 000040
【図９Ｃ】
2010515113.tif 000041
【図１０Ａ】
2010515113.tif 000042
【図１０Ｂ】
2010515113.tif 000043
【図１０Ｃ】
2010515113.tif 000044
【図１０Ｄ】
2010515113.tif 000045
2010515113.tif 000046
【図１０Ｅ】
2010515113.tif 000047
【図１１Ａ】
2010515113.tif 000048
【図１１Ｂ】
2010515113.tif 000049
【図１１Ｃ】
2010515113.tif 000050
【図１２Ａ】
2010515113.tif 000051
【図１２Ｂ】
2010515113.tif 000052
【図１２Ｃ】
2010515113.tif 000053
【図１２Ｄ】
2010515113.tif 000054
【図１２Ｅ】
2010515113.tif 000055
【図１２Ｆ】
2010515113.tif 000056
【図１３Ａ】
2010515113.tif 000057
【図１３Ｂ】
2010515113.tif 000058
【図１３Ｃ】
2010515113.tif 000059
【図１４Ａ】
2010515113.tif 000060
【図１４Ｂ】
2010515113.tif 000061
【図１４Ｃ】
2010515113.tif 000062
【図１４Ｄ】
2010515113.tif 000063
【図１４Ｅ】
2010515113.tif 000064
【図１４Ｆ】
2010515113.tif 000065
【国際調査報告】
2010515113.tif 000066
2010515113.tif 000067
2010515113.tif 000068