(57)【要約】  本発明の方法は、ストリーミングされた先導するコンテンツサブクリップを受信するステップ、必要とされるコンテンツサブクリップのセットを決定するステップ、必要とされるコンテンツサブクリップのセットのうちの１つの場所を特定するステップ、場所が特定されたコンテンツサブクリップをダウンロードするステップを有する。また、本発明は、ピア、サーバおよびトラッカを有する、コンテンツオンデマンドを提供するシステムである。トラッカは、サーバと同じ位置に配置されていてもよい。ピアは、ストリーミングされた先導するコンテンツサブクリップを受信するための手段、必要とされるコンテンツサブクリップを特定するための手段、必要とされるコンテンツサブクリップのセットのうちの１つの場所を特定するための手段、場所が特定されたコンテンツサブクリップをダウンロードするための手段を有する。
2009543182.tif 000002
【特許請求の範囲】
【請求項１】
コンテンツオンデマンドサービスを提供する方法であって：
ストリーミングされた先導するコンテンツサブクリップを受信するステップ；
必要とされるコンテンツサブクリップのセットを決定するステップ；
前記必要とされるコンテンツサブクリップのセットのうちの１つの位置を特定するステップ；および
位置が特定されたコンテンツサブクリップをダウンロードするステップ；
を有する方法。
【請求項２】
コンテンツのユニットを要求するステップ、を更に有する請求項１に記載の方法。
【請求項３】
位置が特定されたコンテンツサブクリップを得るためにピアツーピアネットワークを接続することを更に有する、請求項１に記載の方法。
【請求項４】
位置が特定されたコンテンツサブクリップをダウンロードするためのデッドラインを計算するステップ；
前記位置が特定されたコンテンツサブクリップをダウンロードするための前記デッドラインが満たされるかどうか判断するステップ；および
前記位置が特定されたコンテンツサブクリップのための前記デッドラインが満たされる場合、位置が特定されたコンテンツサブクリップをダウンロードし続けるステップ；
を更に有する請求項１に記載の方法。
【請求項５】
前記位置が特定されたコンテンツサブクリップをダウンロードするための前記デッドラインを超えてしまうと予測される場合、欠落しているデータベクトルを準備するステップ；および
前記デッドラインを超えてしまうと予測される前記位置が特定されたコンテンツサブクリップのブロックのための補完的なストリーミングを起動するステップ；
を更に有する請求項４に記載の方法。
【請求項６】
必要とされるコンテンツサブクリップのブロックをサブブロックに分割するステップ；
前記サブブロックの要求をパイプライン化するステップ；および
ステータスを転送するステップ；  
を更に有する請求項１に記載の方法。
【請求項７】
ステータスは、ダウンロードステータス、ピアツーピアネットワークへの参加のステータス、およびキャッシュされたコンテンツのステータス、を有する請求項６に記載の方法。
【請求項８】
前記位置を特定するステップは：
前記必要とされるコンテンツサブクリップの位置およびステータスを特定するためにサブトラッカに信号を送るステップ；および
位置が特定されたコンテンツサブクリップを要求するために、前記位置を選択するステップ；
を更に有する請求項１に記載の方法。
【請求項９】
前記選択するステップは、最もまれなものを第１とする方式に基づく、請求項８に記載の方法。
【請求項１０】
ダウンロード進行指標を計算するステップ、を更に有する請求項４に記載の方法。
【請求項１１】
前記ダウンロード進行指標は、必要ダウンロードレートおよび実行されたダウンロードレートの比率である、請求項１０に記載の方法。
【請求項１２】
アップロードの重みを計算するステップ、を更に有する請求項４に記載の方法。
【請求項１３】
コンテンツオンデマンドサービスを提供する方法であって：
ストリーミングされた先導するコンテンツサブクリップを受信するステップ；
必要とされるコンテンツサブクリップのセットを決定するステップ；
次に必要とするコンテンツサブクリップへのポインタを設定するステップ；
前記次に必要とするコンテンツサブクリップの位置を特定するステップ；および
前記次に必要とするコンテンツサブクリップをダウンロードするステップ；
を有する方法。
【請求項１４】
前記ポインタをインクリメントするステップを更に有する請求項１３に記載の方法。
【請求項１５】
前記次に必要とされるコンテンツサブクリップを得るためにピアツーピアネットワークを接続することを更に有する請求項１３に記載の方法。
【請求項１６】
コンテンツオンデマンドサービスを提供する方法であって：
コンテンツのユニットの要求を受信するステップ；
許可コントロールを実行するステップ；
前記コンテンツのユニットを複数のコンテンツサブクリップに分割するステップ；
ストリーミングされる先導するコンテンツサブクリップの数を計算するステップ；および
前記先導するコンテンツサブクリップをストリーミングするステップ；
を有する方法。
【請求項１７】
残りのコンテンツサブクリップをダウンロードするステップ、を更に有する請求項１６に記載の方法。
【請求項１８】
前記コンテンツサブクリップは、等しいサイズである、請求項１６に記載の方法。
【請求項１９】
コンテンツオンデマンドサービスを提供するシステムであって：
サーバ；
少なくとも一つのピア、および
トラッカ、を有し、
前記ピアは、
ストリーミングされた先導するコンテンツサブクリップを受信するための手段；
必要とされるコンテンツサブクリップのセットを決定するための手段；
前記必要とされるコンテンツサブクリップのセットのうちの１つの位置を特定するための手段；および
位置が特定されたコンテンツサブクリップをダウンロードするための手段；
を更に有するシステム。
【請求項２０】
前記トラッカおよび前記サーバは、同じ位置に配置されることができる、請求項１９に記載のシステム。
【請求項２１】
前記サーバは、種である、請求項１９に記載のシステム。
【請求項２２】
前記ピアは、ダウンローダである、請求項１９に記載のシステム。
【請求項２３】
前記ピアは、コンテンツのユニットを要求するための手段を更に有する、請求項１９に記載のシステム。
【請求項２４】
前記ピアは、前記位置が特定されたコンテンツサブクリップを得るためにピアツーピアネットワークを接続するための手段、を更に有する請求項１９に記載のシステム。
【請求項２５】
前記ピアは：
位置が特定されたコンテンツサブクリップをダウンロードするためのデッドラインを計算するための手段；
前記位置が特定されたコンテンツサブクリップをダウンロードするための前記デッドラインが満たされる予定かどうか判断するための手段；および
前記位置が特定されたコンテンツサブクリップのための前記デッドラインが満たされる予定の場合、前記位置が特定されたコンテンツサブクリップをダウンロードし続けるための手段；
を更に有する請求項１９に記載のシステム。
【請求項２６】
前記ピアは、
位置が特定されたコンテンツサブクリップをダウンロードするための前記デッドラインを超えてしまうと予想される場合、欠落しているデータベクトルを準備するための手段；および
前記デッドラインを超えてしまうと予想される、位置が特定されたコンテンツサブクリップのブロックのための補完的なストリーミングを起動するための手段；
を更に有する請求項１９に記載のシステム。
【請求項２７】
前記ピアは：
必要とされるコンテンツサブクリップのブロックをサブブロックに分割するための手段；
前記サブブロックの要求をパイプライン化するための手段；および
ステータスを転送するための手段；
を更に有する請求項１９に記載のシステム。
【請求項２８】
前記位置を特定するための手段は：
前記必要とされるコンテンツサブクリップの位置およびステータスを特定するためにサブトラッカに信号を送るための手段；および
位置が特定されたコンテンツサブクリップを要求するために、前記位置を選択するための手段；
を更に有する請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はピアツーピアネットワーク、より具体的には、システム性能を考慮し、ピアビデオダウンロード（ピアツーピアネットワークにおけるピアによるデータ／ビデオのダウンロード）を提供するピアツーピアネットワークを使用した、ビデオオンデマンドサービスの提供に関する。
【背景技術】
【０００２】
従来、クライアントサーバのサービスモデルは、ストリーミングサービスを提供するためにも用いられてきた。クライアントは要求／要請をサーバに送信し、サーバがクライアントの要求／要請を満たすのに十分な資源を備ており、かつ十分なバンド幅がサーバとクライアントの間のパスにある場合、サーバからクライアントにコンテンツが伝送される。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
限られた計算能力および記憶資源、サーバおよびクライアントを接続しているネットワークのサーバおよび限られたバンド幅のため、スケーラビリティは、クライアントサーバでのストリーミングサービスにおける問題点であった。近年では、ピアツーピア技術が、ストリーミングサービスにもたらされた。ピアは、クライアントサーバ能力に基づいてインプリメントされ、サーバに対する負荷の軽減に貢献し、能動的にコンテンツを取り入れて、他のピアに提供することによって、ネットワーク全体のバンド幅要件を分配させる。研究において、ピアツーピア技術がシステムスのケーラビリティを非常に改善することが示されており、より多くのユーザに貢献するシステムの構築を可能としている。
【０００４】
ピアツーピアネットワークを使用したストリーミングメディアサービスにおいて提起されているスケーラビリティ問題に対処する多くの努力がなされている。これらの努力は、２つのカテゴリに分けることができる。すなわち、ピアツーピアのライブストリーミング、およびストア式のビデオストリーミングまたはビデオオンデマンドである。ユーザに良好な表示品質を提供すると共に、両方のサービスがピアツーピア技術を使用している多くのユーザをサポートするよう努める一方、それらは、異なる技術的な課題に直面している。ピアツーピアのライブストリーミングにおいては、システムスケーラビリティを犠牲にすることなく最初の遅延を最小化することが課題である。ピアツーピアのビデオオンデマンドサービスにおいては、非同期ユーザの分担が、課題である。
【０００５】
複数のピアツーピアストリーミング方式も、それぞれの異なる配布技術によって区別できる。データ配布の２つのストリーミング方式が提案されている。すなわち、オーバレイベースの方式およびデータ駆動方式である。オーバレイベースの方式は、ピアがメッシュまたは木構造を形成する。ここでは、ピア間で親子関係が形成される。子のピアはその親からデータを受け取る。これに対して、データ駆動方式のピアは固定した親子関係を持たない。ピアは、欠落しているデータを探して、利用できる場合は欠落しているデータを受け取る。オーバレイベースの方式がピアツーピア技術開発の初期に使われてきた一方、データ駆動方法がより普及するようになってきている。その理由としては、それが効果的にチャーン（ｃｈｕｒｎ：ユーザのプロバイダ乗り換え）および非対称バンド幅問題に対処できるからである。
【０００６】
大部分の先行技術が良いスケーラビリティで、従来のクライアントサーバサービスモデルと比較してより多くのユーザ数をサポートする。しかしながら、先行技術方式は、ベストエフォートを基本としており、システム性能のサポートの条件は、完全には把握されてはいない。
【課題を解決するための手段】
【０００７】
本発明は、効率性のあるピアツーピアビデオオンデマンドサービスを提供することを目的とする。本発明は、ピアツーピアダウンロードを従来のクライアントサーバビデオオンデマンドサービスモデルに組み込むものである。ピアツーピアダウンロードは、大きなデータ転送の負荷を受け持ち、その結果、サーバへの負荷を低下させる。サーバは、性能要件を満たすための緊急のデータの提供のために、その大部分の資源を用いることができる。クライアント側で認識されるパフォーマンスは、高められる。ピアツーピアダウンロードアルゴリズムは、性能要件を満たすことを念頭に置いて設計される。
【０００８】
ビデオオンデマンドサービスは、ユーザがネットワーク上のビデオコンテンツを選択し、望むときはいつでもそれを観ることができる。本発明は、ビデオオンデマンド環境下でのコンテンツシェアリングを有効にするセグメント化されたピアツーピアビデオ共有モデルを有する。性能の問題については、パフォーマンスを重視したピアツーピアデータをダウンロードアルゴリズム、およびサーバの補助による補完的なストリーミングを用いて対処される。この補完的なストリーミングは、従来のクライアントサーバサービスモデルによって提供されるパフォーマンスを総合的にサポートし、かつより多くのユーザ要求／要請をサポートする。
【０００９】
本発明の方法およびシステムは、データ駆動方式を用いて、ピアツーピアビデオオンデマンドサービスを提供することを目的としており、ユーザ側の観る環境を改善するために、かつピアツーピアデータ配布プロセスに、リアルタイムスケジューリングアルゴリズムを組み込んでいる。システム性能は、特に要求されたビデオを、ユーザがタイムリーに観ることができるということが、ユーザの観る評価を上げさせ、全体のビデオ品質が改善されることを意味する点に留意する必要がある。本発明のデータ共有および補完的なサーバストリーミングは、クライアント／ユーザ側における表示品質を改善し、このことがシステム性能の改善につながっている。
【００１０】
ビデオオンデマンドサービスを提供する方法は、ストリーミングされた先導するビデオサブクリップを受信するステップ、必要とされるビデオサブクリップのセットを特定するステップ、必要とされるビデオサブクリップのセットの１つの位置を特定するステップ、および位置が特定されたビデオサブクリップをダウンロードするステップを含んでいる。記載されているビデオオンデマンドを提供するシステムは、ピア、サーバおよびトラッカを有している。トラッカは、サーバと同じ位置に配置されてもよい。ピアは、ストリーミングされた先導するビデオサブクリップを受信するための手段、必要とされるビデオサブクリップのセットを特定するための手段、必要とされるビデオサブクリップのセットのうちの１つの位置を特定するための手段、および位置決めされたビデオサブクリップをダウンロードするための手段を有する。
【００１１】
本発明は、添付の図面を参照しながら、以下の詳細な説明を読むことにより理解される。図面は、同類の符号が付されたものは、同様の要素を表す。
【発明を実施するための最良の形態】
【００１２】
ビデオオンデマンドサービスのユーザは、いかなる所与の瞬間にもビデオの異なる部分を観ている。ユーザ同士のコンテンツ共有を許容し、ピアツーピアネットワークで配信されるコンテンツの量を最大にするために、各ユーザが部分コピーおよび／または再生されたコンテンツの全てのコピーをキャッシュするために記憶容量を有すると仮定する。これは、ビデオ再生装置において急速に記憶容量が増加していることを考慮すると、合理的な仮定である。ビデオ再生装置は、コンピュータ、ラップトップ、パーソナル携帯情報機器（ＰＤＡ）およびモバイル機器を有するが、これに限らずビデオ（録画またはライブ）を受信して、再生することができるいかなる装置をも指す点に留意する必要がある。ピアツーピアネットワークは、有線ネットワークに限らず、ワイヤレス、有線、またはワイヤレスと有線のハイブリッドネットワークでもよい。
【００１３】
本発明のセグメント化されたピアツーピアのビデオオンデマンドの方法および装置において、ビデオクリップは、複数の等しい長さセグメントに分けられており、これをサブクリップと呼ぶ。サブクリップの始まりの再生時刻は、このサブクリップのデッドラインと定義される。ユーザが直ちに再生を始めてもよいように、先導するサブクリップはビデオ再生装置にストリーミングされる。一方、次のサブクリップのデータをプリフェッチするために、ピアツーピアネットワークは、ユーザ間で確立される。本発明のシステム性能を考慮した方式に従って、サブクリップのデータは、そのデッドラインの前にプリフェッチされなければならない。一旦、あるサブクリップの再生が始まると、新しくダウンロードされたデータは古いものとなるため、そのサブクリップのピアツーピアダウンロードは許容されない。オリジナルのサーバからの補完的なストリーミングが、より良好なシステム性能を確保するために、その後開始される。次に、補完的なストリーミングについて説明する。
【００１４】
本実施例を用いて、本発明のセグメント化されたピアツーピアビデオオンデマンドが、どのように到来する要求／要請に答えるかについて説明する。この例では、ユーザがビデオの全てのコピーをキャッシュすることが可能であると仮定する。なお、一部のビデオコピーだけがキャッシュされる場合であっても、同じ技術があてはまる。サーバは、第１のサブクリップをストリームするだけであると更に仮定する。そして、以降のサブクリップのデータはピアツーピアネットワークを使用してダウンロードされると仮定する。ストリーミングされるサブクリップの数を計算するアルゴリズムに関して、以下に説明する。
【００１５】
図１を参照する。クライアント／ユーザ１は、時間ｔ１でサーバからビデオを求める要求／要請を出す。サーバは直ちにサブクリップ１（第１のビデオサブクリップ）をクライアント１にストリームする。その結果、クライアント１は再生をすぐに始めてもよい。同時に、ピアツーピアネットワークの中でサブクリップ２を取り込み／キャッシングするピアの位置を特定する試みが実行される。このときは、ピアツーピアネットワークにおいてサブクリップ２を取り込み／キャッシングする唯一のピアはサーバである。そして、それはピアとして振る舞ってもよい。（少なくとも）クライアント１およびサーバは、ピアツーピアネットワークのメンバである。時刻ｔ２で、クライアント１はサブクリップ１を再生している。その一方で、サブクリップ２はサーバからダウンロードされている（ストリームはされない）。クライアント／ユーザ２は、サーバに対して同じビデオの要求／要請を行うとすぐに、サーバからクライアント２にストリームされたサブクリップ１の再生を始める。サーバおよびクライアント１は、サブクリップ２をクライアント２に対してダウンロードさせることを開始する（ストリーミングではない）。このとき、サーバ、クライアント１およびクライアント２は、ピアツーピアネットワークのピアである。時間ｔ３で、クライアント３はサーバに対して同じビデオの要求／要請を行って、直ちにサーバからストリームされたサブクリップ１の再生を始める。この時点までに、クライアント１は、サブクリップ３を再生していて、サブクリップ４のデータ／ビデオをダウンロードしている。クライアント２は、サブクリップ２を再生していて、サブクリップ３をダウンロードしている。この時に、（少なくとも）サーバ、クライアント１、クライアント２およびクライアント３が、ピアツーピアネットワークのメンバである。クライアント３は、サーバ、クライアント１およびクライアント２からサブクリップ２をダウンロードしてもよい。時間が進むにつれて、ピアビデオ再生は続く。図１に示すように、現在時刻ｔ４において、ピアツーピアダウンロードによって、現在再生されているサブクリップに続くサブクリップのデータをプリフェッチする。時刻ｔ５までに、クライアント１は、すでにそのビデオ再生を終えて、システムから離れたことを示している。クライアント２は最後のサブクリップを再生している、そして、クライアント３はサブクリップ４を再生していて、サブクリップ５をダウンロードしている。サーバおよび第２のクライアントは、サブクリップ５をダウンロードするためのピアツーピアネットワークのピアである。最後に、クライアント２も、ビデオ再生を終えた後に、システムから離れる。クライアント３は、サブクリップ５を見ている／再生しており、サブクリップ５終了後システムを離れる。
【００１６】
図２は、本発明によるピアツーピアネットワークを示している図である。サーバ２０５は、ビデオの全てのコピーを有しており、ビデオからのサブクリップをストリームさせてもよいし、またはピアツーピアネットワークの他のピア２１０に対してピアとして振る舞い、かつサブクリップをダウンロードさせてもよい。一旦ピア２１０がビデオをサーバ２０５に要求／要請すると、それはピアツーピアネットワークを接続して、他のピア２１０から次のサブクリップをダウンロードしてもよく、および／または他のピア２１０に対してサブクリップをダウンロードさせてもよい。サブクリップは、サーバ２０５からストリーミングされるだけである。通常、先導するサブクリップだけはサーバ２０５からピア２１０に、要求／要請しているビデオがストリーミングされる、そして、残りのサブクリップはサーバ２０５または他のピア２１０からダウンロードされる。なお、ピアがデッドラインの前までにダウンロードされるべきサブクリップを受信するために、ダウンロードレートが充分でない場合、サーバからピアに次のサブクリップをストリームすることは可能である。トラッカ２１５は、別に実装されてもよいし、サーバ２０５の一部として実装されてもよい。トラッカ２１５が別個に実装される場合、サーバ２０５とトラッカ２１５の間でシグナリングがなされる。これは、ピアツーピアネットワークに接続し、またピアツーピアネットワークから離れるピアを監視する。加えて、トラッカは、ピアツーピアネットワークのどのピアがどんなダウンロード可能なサブクリップを備えているかというトラックおよびさまざまなピア（ピアが各ピアによってダウンロードされるために必要であるダウンロードできるサブクリップを保持しているかどうか、および他のピアによってダウンロードに利用できるサブクリップ）のステータスを保持する。一旦ピアがサブクリップを受信すると、そのサブクリップを必要とする他のピアに対してそのピアからそのサブクリップをダウンロードすることができるということに解釈される。両側矢印の線は、サブクリップダウンロードを示す。片側矢印の線は、サブクリップのストリーミングを示す（サーバだけは、ストリーミングでもよい）。破線は、シグナリングを示す。
【００１７】
図３は、サーバ側からの許可コントロールの処理のフローチャートである。ビデオに関する新規な要求／要請が、サーバになされる。サーバへの新規な要求／要請によって、許可コントロールの処理３０５が呼び出され、収集した統計に基づいて処理が進行する。要求が３１０で認められた場合、直接サーバからストリームされなければならない先導するサブクリップの数は３１５において見積もられる。ストリーミングされるサブクリップ（先導する）の数は、Ｎで表される。サーバは、３２０でリクエストしたクライアント／ユーザに、先導するサブクリップをストリームし、３２５で要求／要請元のユーザ／クライアントにＮの値を返す。要求／要請が認められない場合、先導するサブクリップの数は初期化されて３３０でイニシャライズ／リセットされる。
【００１８】
図４は、ユーザ／クライアント側から見た許可コントロールの処理を表しているフローチャートである。ユーザ／クライアント側で、一旦クライアントがサーバから応答を受け取ると、Ｎ（サーバからクライアントにストリーミングされる先導するサブクリップの数）の値をテストすることによって、要求／要請が認められたかどうかを検査するために、４０５でチェックされる。Ｎの価がゼロより大である場合、要求／要請は認められたことになり、ユーザは４１０でストリーミングされたＮ個のサブクリップを受信し始める。サーバ側でのＮ＝−１の設定、およびユーザ／クライアント側でのＮ＞０の設定が、インプリメンテーションにおいて取り得る唯一の値である点に留意する必要がある。要求・許可の検査は、例えば、フラグまたは他のいかなる適当な手段によっても行うことができる。現在のサブクリップ番号Ｎｃは、４１５でＮ＋１（次のサブクリップ、ダウンロードされるサブクリップ）にセットされる。さらにサブクリップがダウンロードされるかどうか決定するために、４２０において検査される。要求／要請が認められない、または、ビデオのすべてのサブクリップがユーザによって受け取られた場合、処理は終わる。一方、ピアツーピアネットワーク内のＮ＋１番目のサブクリップを持っている／キャッシュしているピアは、４２５で、Ｎ＋１番目のサブクリップを必要とするピアにアップロードを開始する。４３０において、ダウンロードのための（現在時刻ｔに対して計った）デッドライン（ｄ）に間に合うと判断される場合には、４３５でダウンロードが継続される。４３０において、（現在時刻（ｔ）に対して計った）デッドライン（ｄ）に間に合わないと判断される場合には、欠落しているデータベクトルは、４４０で用意される。実際には、欠落したベクトルは、デッドラインの少し前、またはダウンロードがデッドライン（ｄ）の前に完了することができないと判断されたときに用意される。ダウンロードがデッドラインの前に完了できない場合、補完的なストリーミングが必要かどうか判断するために、４４５で検査がなされる。補完的なストリーミングは、後で更に詳細に述べる。一方、現在のサブクリップカウンタは、４５５でインクリメントされる。補完的なストリーミングがシステム性能を満たすために（デッドラインの前にユーザにサブクリップが到着することが）必要とされる場合、補完的なストリーミングが４５０で呼び出される。Ｎ＋１番目のサブクリップのダウンロードのデッドライン（ｄ）が到来すると、ユーザはＮ＋１番目のサブクリップの再生を開始する。ピアツーピアネットワークの中の次のサブクリップを持っている／キャッシュしているピアが探索され、ビデオサブクリップダウンロードプロセスを開始する。
【００１９】
次に、サーバによってストリーミングされるサブクリップの数の計算について述べる。
【００２０】
要求／要請とともに、クライアント／ユーザは、サーバに推定されたダウンリンクのバンド幅を示す。ユーザが自分自身のダウンリンクバンド幅についてのより良い知識を有していると考えられる。サーバによるビデオストリーミングの初めに、ダウンリンクバンド幅は、ストリーミングおよびピアツーピアダウンロードによって利用される。ユーザｉに対して、ブクリップｎｉが、サーバによってストリーミングされるとした場合、（ｎｉ＋１）番目のサブクリップのコピーは、デッドライン（すなわち、Ｌ＊ｎｉ）の前に、ダウンロードされる必要がある。ここでＬはサブクリップの時間である。ｒｐｌａｙｂａｃｋをビデオの再生レートとし、ｒｄｏｗｎｌｉｎｋをユーザのダウンリンクバンド幅とすると、（ｒｄｏｗｎｌｉｎｋ−ｒｐｌａｙｂａｃｋ）ｎｉＬ＞＝Ｌｒｐｌａｙｂａｃｋとなる。ここで「ｎｉ」は、整数である（完全なサブクリップがストリームされる）とすると、式１となる。
ｎｉ＝ｒｐｌａｙｂａｃｋ／（ｒｄｏｗｎｌｉｎｋ−ｒｐｌａｙｂａｃｋ）      （式１）
上述のように、ピアツーピアダウンロードを従来のサーバ―クライアントビデオオンデマンドサービスに組み込んだ本発明は、セグメント化されたピアツーピアビデオオンデマンドサービスである。ピアツーピアダウンロードは、大部分のデータ／ビデオの伝送荷重を受け持つことになるため、著しくサーバへの負荷を低下させる。全体のシステムスループットを向上させるための従来のピアツーピアファイルダウンロードと比較すると、本発明のピアツーピアダウンロードは、システムパフォーマンスを考慮し（デッドラインの前にサブクリップがユーザに到着する）、サブクリップのデッドラインを満たすことに重点を置いている。次に、単一のサブクリップのためのピアツーピアダウンロードに関して説明する。複数のサブクリップ全体のピアツーピアダウンロードを調整して、どのようにすべてのユーザにデータ／ビデオのタイムリーな配信をするかを説明する。
【００２１】
本発明は、ユーザの中のサブクリップデータを交換するために、データ駆動ピアツーピアダウンロードを使用する。本発明のサブクリップは等しい大きさのブロックに分けられ、ユーザは並行して複数ユーザからブロックをダウンロードする。ブロックは、転送のオーバーヘッドを減らし、リクエストのパイプライン化を有効にするために、サブブロックに更に再分割される。各サブクリップに対応して、現在特定のサブクリップのピアツーピアダウンロードに参加しているユーザの参加状況を把握しているサブトラッカと呼ばれている中心コンポーネントがある。サブトラッカは、ユーザがサブクリップピアツーピアネットワークに加わるかまたは離れるときに、および周期的にユーザから最新状況を受け取る。
【００２２】
ピアツーピアネットワークのピアは、次の２つのカテゴリに分けられる：すなわち、種およびダウンローダである。種は、サブクリップの完全な／部分的なコピーを有しており、他の機器にサブクリップを提供／アップロードするユーザである。種は、それらの種がすでにデータを有するので、それらの種が他のピアにアップロードしているサブクリップデータをダウンロードすることはない。ダウンローダは、データを現在ダウンロードしているユーザであるが、同時に、それらがすでに有するブロックは他に提供する用意がある。新規ユーザユーザクリップをダウンロードし始めるときに、ユーザは現在サブクリップ（または一部のサブクリップ）を有しておりかつサブクリップをアップロードする用意があるピアツーピアネットワーク（種およびダウンローダ）のユーザのリストを得るために対応するサブトラッカにコンタクトする。新規ユーザは、リストに載っているユーザとの接続を確立することを試みる。そして、それは、ユーザに対する隣人となる。ピアは、個々に、ピアがデータをどのユーザに提供し／アップロードするかについて決定するために、分散アルゴリズムを実行する。大部分の（最大数の）ユーザがそれぞれのデッドラインの前にブクリップデータを受信するという可能性を最大にするために、選択過程においていくつかの要因が考慮される。
【００２３】
ユーザがデータを受け取るために、隣（ピア）が選ばれると仮定する、そして、隣には隣がダウンロードすることができる幾つかのブロックの選択肢が存在すると仮定する。隣／ピアは、ダウンロードするブロックを選択する際、局所的に最もまれなものを第１とする（ＬＲＦ）ポリシーを使用する。ピアは、ダウンロードのためにその隣人の中で最も少なく複製されている１ブロックを選択することを試みる。目的は、システムのコンテンツの多様性を最大にして、すなわち、各ブロックのレプリカの数をできるだけ等しくすることである。これは、ブロックが見つからずに、システムが停滞する可能性をなるべく回避できる。ユーザが、隣にあるすべてのデータを有する場合には、隣は、データを提供し／ダウンロードさせるために他のユーザを選択する。
【００２４】
従来のピアツーピアネットワークは、単一ファイルを頒布するように設計されている。本発明においては、ビデオクリップは、複数のサブクリップに分けられる、各サブクリップは、ピアツーピアネットワークを使用して頒布される。このため、本発明の方式では、ユーザは、同時に複数のピアツーピアネットワークに加わってもよい。たとえば、図１において、クライアント３は、時刻ｔ４においてサブクリップ２を再生している。クライアント３は、サブクリップ２をダウンロードし終わって、サブクリップ３をダウンロードしている。この場合、クライアント３は、サブクリップ１、２および３のために、３つのピアツーピアネットワークに参加する。クライアント３は、サブクリップ１のためのピアツーピアネットワークの種であり、サブクリップ２のための（もう一方）ピアツーピアネットワークの種であり、サブクリップ３のためのさらにもう一つのピアツーピアネットワークのためのダウンローダである。クライアント１およびクライアント２は、サブクリップ３のためのクライアント３の種である。時刻ｔ４に、クライアント２はサブクリップ４をダウンロードしている。そして、クライアント１はクライアント２のためのサブクリップ４のための種である。時間ｔ４で最後に、クライアント１はサブクリップ５をダウンロードしている。そして、オリジナルのサーバはサブクリップ５のクライアント１のための唯一の種である。クライアント３は、クライアント１および２の役に立つことができない。
【００２５】
パフォーマンスを考慮したビデオオンデマンドサービスを提供するための本発明のピアツーピアネットワークにおいて、ユーザは、複数のピアツーピアネットワークに加わってもよい（ユーザは、各サブクリップのための異なるピアツーピアネットワークに加わってもよい）。しかしながら、アップロードの合計数は、多数の開いたＴＣＰ接続があることによる性能低下を回避するために、少ない数でなければならない。課題は、全体のパフォーマンス（すなわち、すべてのユーザがそれぞれのデッドラインの前にコンテンツ／サブクリップを読み出すという可能性）が最大になるように、どのように複数のピアツーピアネットワーク全体からアップロードピアを選択するのかということになる。以下は、システム性能に影響を及ぼすと考えられているキーファクタのリストである。
１．デッドラインにどれほどの緊急性があるか。デッドラインがきびしいほど、ダウンローダは、より高い優先順位を確保しなければならない。
２．ダウンロードは、スケジュール通りか？すべてのユーザは、公正に扱われなければならない。ダウンロードは、ダウンロードが始まった時から、ピアがシステムにおいて費やす時間中、比例して進行しなければならない。
３．どれくらいの可能な種が、利用できるか？ユーザがピアビデオ再生を終えると直ちに離脱する場合、利用できる種の数は異なる時間、異なるサブクリップに対して異なる。例えば、図１のクライアント４のためのサブクリップ２のための種の数は、サブクリップ３のための種の数よりも多い。なぜなら、これは、サブクリップ３の種はサブクリップ２の種でもあるという理由からである。しかしながら、種が再生を終えた後にシステムを離れることができるため、サブクリップ２のための種はサブクリップ３のための種ではなくてもよい。一般に、到着プロセスが平均到着率λをもつポアソンである場合、利用できる種の数は、下記の式２に従う。
Ｎｉｓｅｅｄ＝λ（Ｌｖｉｄｅｏ−ｉＬ）  （式２）
ここで、Ｎｉｓｅｅｄは、サブクリップｉのための種の数の平均値、Ｌｖｉｄｅｏは、ビデオの長さ、Ｌはサブクリップの長さを意味する。
４．高いアップロード速度は、システムスループットを改善するため、好ましい。
【００２６】
Ｓはサブクリップのサイズを意味し、ｔは現在時刻を意味する。ｘｊｋを、ユーザｊがｋ番目のサブクリップのダウンロードを開始する時刻とする。そして、ｓｊｋ（ｔ）を時刻ｔにおける取り出されたコンテンツの量とする。さらに、ｄｊｋをユーザｊのｋ番目のサブクリップのデッドラインとし、ρｊｋをユーザｊのｋ番目のサブクリップのダウンロードの進行指標とする。すると、以下の式３が導ける。
ρｊｋ＝Ｓ（ｘｊｋ−ｔ）／［ｓｊｋ（ｔ）（ｘｊｋ−ｄｊｋ）］  （式３）
ρｊｋの値は、ダウンロードの進行状況を反映している。すなわちρｊｋはデータ／ビデオダウンロードがスケジュール通りかどうかを示す。Ｓ／（ｓｊｋ−ｄｊｋ）は、時刻通りに（サブクリップデッドラインまでに）サブクリップを取り出すために、必要なダウンロードレートである。（ｘｊｋ−ｔ）は、経過時間である。ｘｊｋ（ｔ）／（ｘｊｋ−ｔ）は、今までになされたダウンロードレートである。ダウンロード進行指標は、必要ダウンロードレートおよび実行されたダウンロードレートの比率である。もし、ρｊｋ＝１であれば、ダウンロードはスケジュール通りである。もし、ρｊｋ＜１であれば、ダウンロードがスケジュールよりも遅れているということである。また、ρｊｋ＞１であれば、ダウンロードはスケジュールよりも進んでいるということである。
【００２７】
次に、ピアがどの隣のピアにデータを送らなければならないかについて決定するために用いる基準値について説明する。ｗｉｊｋを、ピアｉがピアｊに対してｋ番目のサブクリップを提供／ダウンロードさせる重みを表すとする。値ｗｉｊｋが大きいほど、ピアｉはピアｊに提供する可能性が高いということになる。ｗｉｊｋを式４のように定める。
ｗｉｊｋ＝ｒｉｊ／［ρｊｋ（ｄｊｋ−ｔ）（ｔ−ｄｉｋ）］  （式４）
分子は、ｒｉｊである。これは、ピアｉからｊへのアップロードのスピード／レートである。直感的な説明をすれば、アップロードスピードが早いと、全体のシステムスループットは改善するということである。このため、より大きいアップロードレートが、より良好である。上記の式４においても、このファクタが影響する。式４の分母には、３つの時間的な要素が存在する。式３で定義したように、ρｉｊは、進行指標である。ρｉｊの値が小さければ、ｊはスケジュールに遅れていることになる。したがって、上記ｊに対しては、上記ファクタ２に基づいて、高い優先スケジュールが与えられる。（ｄｊｋ−ｔ）は、デッドラインまでの時間である。（ｄｊｋ−ｔ）の値が小さいほど、上記ファクタ１に基づいて、デッドラインは、タイトになる。タイトなデッドラインに係るリクエストは、高い優先度が与えられる。時刻ｔまで、ｋ∈｛ｋ｜ｄｉｋ＜ｔ｝である全てのサブクリップｋのピアｉは、種である。なお、異なるサブクリップは、式２に示すように異なる数の種を有する。最少の数を有する種を持つユーザーリクエストが優先されなければならない。時間がより長く経過すれば、そのリクエストに対してより多くの種が利用できる。そして、それは分母の最後の時間的要素に関係する（第３のファクタに従う）。
【００２８】
上記のように、性能を担保すること（サブクリップがタイムリーにユーザに到着すること）に配慮したが、ピアツーピアダウンロードの場合、若干のデータはデッドライン（またはデッドラインの少し前）までに、間に合わないことがある。次に、更にピアビデオ再生パフォーマンスを高めるために、欠落しているデータをストリームするためにサーバを使用する方法について説明する。これは、本願明細書において補完的なストリーミングと呼ばれている。デッドラインが近づくと、ピアクライアントは欠落しているデータベクトルＶｍｉｓｓｉｎｇを準備する。それは第１のフラグ（例えばブロックが受け取られたことを示す「１」）および第２のフラグ（例えば１ブロックがまだ受け取られていないことを示す「０」）を使用するビットマップである。欠落しているデータベクトルは、サブクリップがユーザに到達するべきデッドラインと共に、サーバに送信（シグナリング）される。サーバは、デッドラインが近づくと、欠落しているデータをストリームする。これによって、欠落しているデータがピアビデオ再生に間に合うようにすることができる。
【００２９】
本発明のサーバは、以下の三点の責任を受け持っている。
（ｉ）迅速な再生（ストリーミングによって）をサポートするために最初の／先導するサブクリップを供給すること。
（ｉｉ）ユーザへの表示品質（サブクリップが各サブクリップデッドラインの前にユーザに到達することを確保すること）を改善するために補完的なストリーミングを提供すること、および
（ｉｉｉ）ピアツーピアデータ／ビデオダウンロードの種として機能すること。タスク１および２は、タスク３より高い優先度を持つ。
【００３０】
本発明は、ハードウェア、ソフトウェア、ファームウェア、専用プロセッサまたはそれらの組み合わせの様々な形態により実施されてもよいことを理解すべきである。好ましくは、本発明は、ハードウェアおよびソフトウェアの組合せで実施される。さらに、ソフトウェアは、プログラム記憶領域装置に明確に格納されるアプリケーションプログラムとしてインプリメントされる。アプリケーションプログラムは、いかなる適切なアーキテクチャから成るマシンにもアップロードされてもよく、実行されてもよい。好ましくは、マシンは、ハードウェア（例えば一つ以上の中央処理装置（ＣＰＵ）、ランダムアクセスメモリ（ＲＡＭ）および入出力（Ｉ／Ｏ）インタフェース）を有するコンピュータプラットフォームにインプリメントされる。また、コンピュータプラットフォームは、オペレーティングシステムおよびマイクロ命令コードを有する。本願明細書において記載されているさまざまな方法および機能はマイクロ命令コードの一部でもよく、またはアプリケーションプログラム（またはそれらの組み合わせ）でもよい。そして、それはオペレーティングシステムを介して実行される。加えて、さまざまな他の周辺デバイスは、コンピュータプラットフォーム（例えば追加データ記憶機構装置およびプリントデバイス）に接続していてもよい。
【００３１】
添付の図において表したシステムコンポーネントおよび方法ステップの構成要素の一部は、ソフトウェアで実行されるのが好適である。更に、システムコンポーネント（または工程ステップ）間の実際の接続は、本発明がプログラムされる方法によって、異なっていてもよいと理解される。本願明細書における記述によって、関連技術の当業者は、これらおよび同様の実施例または本発明の構成をインプリメントすることが可能である。
【図面の簡単な説明】
【００３２】
【図１】本発明によるピアツーピアネットワークの概要図である。
【図２】本発明によるピアツーピアネットワークを示している図である。
【図３】サーバ側からの許可コントロールの処理のフローチャートである。
【図４Ａ】ユーザ／クライアント側からの許可コントロールの処理を示すフローチャートである。
【図４Ｂ】ユーザ／クライアント側からの許可コントロールの処理を示すフローチャートである。
【図１】
2009543182.tif 000003
【図２】
2009543182.tif 000004
【図３】
2009543182.tif 000005
【図４Ａ】
2009543182.tif 000006
【図４Ｂ】
2009543182.tif 000007
【手続補正書】
【提出日】平成21年1月7日(2009.1.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ストリーミングされた先導するコンテンツサブクリップを受信するステップ；
必要とされるコンテンツサブクリップのセットを決定するステップ；
前記必要とされるコンテンツサブクリップのセットのうちの１つの位置を特定するステップ；および
位置が特定されたコンテンツサブクリップをダウンロードするステップ；
を有する方法。
【請求項２】
コンテンツのユニットを要求するステップ、を更に有する請求項１に記載の方法。
【請求項３】
位置が特定されたコンテンツサブクリップを得るためにピアツーピアネットワークを接続することを更に有する、請求項１に記載の方法。
【請求項４】
位置が特定されたコンテンツサブクリップをダウンロードするためのデッドラインを計算するステップ；
前記位置が特定されたコンテンツサブクリップをダウンロードするための前記デッドラインが満たされるかどうか判断するステップ；および
前記位置が特定されたコンテンツサブクリップのための前記デッドラインが満たされる場合、位置が特定されたコンテンツサブクリップをダウンロードするステップ；
を更に有する請求項１に記載の方法。
【請求項５】
前記位置が特定されたコンテンツサブクリップをダウンロードするための前記デッドラインを超えてしまうと予測される場合、欠落しているデータベクトルを準備するステップ；および
前記デッドラインを超えてしまうと予測される前記位置が特定されたコンテンツサブクリップのブロックのための補完的なストリーミングを起動するステップ；
を更に有する請求項４に記載の方法。
【請求項６】
必要とされるコンテンツサブクリップのブロックをサブブロックに分割するステップ；
前記サブブロックの要求をパイプライン化するステップ；および
ステータスを転送するステップ；  
を更に有する請求項１に記載の方法。
【請求項７】
ステータスが、ダウンロードステータス、ピアツーピアネットワークへの参加のステータス、およびキャッシュされたコンテンツのステータス、を有する請求項６に記載の方法。
【請求項８】
前記位置を特定するステップは：
前記必要とされるコンテンツサブクリップの位置およびステータスを特定するためにサブトラッカに信号を送るステップ；および
位置が特定されたコンテンツサブクリップを要求するために、前記位置を選択するステップ；
を更に有する請求項１に記載の方法。
【請求項９】
前記選択するステップは、最もまれなものを第１とする方式に基づく、請求項８に記載の方法。
【請求項１０】
ダウンロード進行指標を計算するステップ、を更に有する請求項４に記載の方法。
【請求項１１】
前記ダウンロード進行指標は、必要ダウンロードレートおよび実行されたダウンロードレートの比率である、請求項１０に記載の方法。
【請求項１２】
アップロードの重みを計算するステップ、を更に有する請求項４に記載の方法。
【請求項１３】
次に必要とするコンテンツサブクリップへのポインタを設定するステップ、を更に有する請求項１に記載の方法。
【請求項１４】
前記ポインタをインクリメントするステップを更に有する請求項１３に記載の方法。
【請求項１５】
前記次に必要とされるコンテンツサブクリップを得るためにピアツーピアネットワークを接続することを更に有する請求項１３に記載の方法。
【請求項１６】
コンテンツのユニットの要求を受信するステップ；
許可コントロールを実行するステップ；
前記コンテンツのユニットを複数のコンテンツサブクリップに分割するステップ；
ストリーミングされる先導するコンテンツサブクリップの数を計算するステップ；および
前記先導するコンテンツサブクリップをストリーミングするステップ；
を有する方法。
【請求項１７】
残りのコンテンツサブクリップをダウンロードするステップ、を更に有する請求項１６に記載の方法。
【請求項１８】
前記コンテンツサブクリップは、等しいサイズである、請求項１６に記載の方法。
【請求項１９】
サーバ、ピア、およびトラッカ、を有するシステム。
【請求項２０】
前記トラッカおよび前記サーバは、同じ位置に配置されることができる、請求項１９に記載のシステム。
【請求項２１】
前記サーバは、種である、請求項１９に記載のシステム。
【請求項２２】
前記ピアは、ダウンローダである、請求項１９に記載のシステム。
【請求項２３】
前記ピアは、
ストリーミングされた先導するコンテンツサブクリップを受信するための手段；
必要とされるコンテンツサブクリップのセットを決定するための手段；
前記必要とされるコンテンツサブクリップのセットのうちの１つの位置を特定するための手段；および
位置が特定されたコンテンツサブクリップをダウンロードするための手段；
を更に有する、請求項１９に記載のシステム。
【請求項２４】
前記ピアは、コンテンツのユニットを要求するための手段、を更に有する請求項２３に記載のシステム。
【請求項２５】
前記ピアは、前記位置が特定されたコンテンツサブクリップを得るためにピアツーピアネットワークを接続するための手段、を更に有する請求項２３に記載のシステム。
【請求項２６】
前記ピアは：
位置が特定されたコンテンツサブクリップをダウンロードするためのデッドラインを計算するための手段；
前記位置が特定されたコンテンツサブクリップをダウンロードするための前記デッドラインが満たされる予定かどうか判断するための手段；および
前記位置が特定されたコンテンツサブクリップのための前記デッドラインが満たされる予定の場合、前記位置が特定されたコンテンツサブクリップをダウンロードし続けるための手段；
を更に有する請求項２３に記載のシステム。
【請求項２７】
前記ピアは、
位置が特定されたコンテンツサブクリップをダウンロードするための前記デッドラインを超えてしまうと予想される場合、欠落しているデータベクトルを準備するための手段；および
前記デッドラインを超えてしまうと予想される、位置が特定されたコンテンツサブクリップのブロックのための補完的なストリーミングを起動するための手段；
を更に有する請求項２３に記載のシステム。
【請求項２８】
前記ピアは：
必要とされるコンテンツサブクリップのブロックをサブブロックに分割するための手段；
前記サブブロックの要求をパイプライン化するための手段；および
ステータスを転送するための手段；
を更に有する請求項２３に記載のシステム。
【請求項２９】
前記位置を特定するための手段は：
前記必要とされるコンテンツサブクリップの位置およびステータスを特定するためにサブトラッカに信号を送るための手段；および
位置が特定されたコンテンツサブクリップを要求するために、前記位置を選択するための手段；
を更に有する請求項２３に記載のシステム。
【国際調査報告】
2009543182.tif 000008
2009543182.tif 000009