(57)【要約】ニアビデオオンデマンド配信プロトコルを利用して、少なくとも１つのタイトルを配信する配信システムは、複数の配信受信機を有する。データ配信装置の階層的ネットワークは、タイトルをデータブロックシーケンスとして配信するため、中央配信装置から少なくとも１つの中間配信装置レイヤを介し配信受信機から構成される。少なくとも１つのフィルタコントローラは、タイトルの供給に対する配信装置からの要求を受信し、少なくとも１つの中間配信装置の階層的に下位の受信機により要求されていないタイトルのデータブロックをフィルタリングするよう当該中間配信装置を制御する。
2006509455.tif 000002
【特許請求の範囲】
【請求項１】
ニアビデオオンデマンド配信プロトコルを利用して、少なくとも１つのタイトルを配信する配信システムであって、
複数の配信受信機と、
前記タイトルをデータブロックシーケンスとして配信するため、中央配信装置から少なくとも１つの中間配信装置レイヤを介し前記複数の配信受信機までのデータ配信装置の階層的ネットワークと、
前記タイトルの供給に対する配信装置からの要求を受信するよう動作し、少なくとも１つの中間配信装置の階層的に下位の受信機により要求されていない前記タイトルのデータブロックをフィルタリングするよう前記少なくとも１つの中間配信装置を制御する少なくとも１つのフィルタコントローラと、
を有することを特徴とするシステム。
【請求項２】
請求項１記載の配信システムであって、
前記タイトルのデータブロックは、前記タイトルの各データブロックに対し、前記タイトルの第１データブロックを配信するのに使用されるタイムスロットに対して前記データブロックを配信するタイムスロットとチャネルを規定するニアビデオオンデマンドスケジュールに従って、複数のチャネルを介し該複数のチャネル内の逐次的タイムスロットを用いて配信され、チャネルに割当てられるデータブロックは前記チャネル内で繰り返し配信され、
前記フィルタコントローラは、
前記タイトルを要求した前記中間配信装置の階層的に下位にあるすべての対象受信機に関する情報を、前記フィルタコントローラが各チャネルに対し前記対象受信機の少なくとも１つが前記チャネルに割当てられたデータブロックを受信する必要があるか判断することが可能となるように格納し、
前記対象受信機の何れもが前記チャネルに割当てられたデータブロックを受信する必要がない場合、チャネルをフィルタリングするよう前記中間配信装置を制御する
よう動作することを特徴とするシステム。
【請求項３】
請求項２記載の配信システムであって、
前記ニアビデオオンデマンドスケジュールは、前記タイトルのデータブロックが前記配信システムのｃ個のパラレルな等しい容量のチャネルを介し配信されることを規定し、各配信チャネルは各自の逐次的チャネル番号に関連付けされ、前記タイトルは複数の連続するデータブロックシーケンスに分割され、各ブロックシーケンスは前記チャネル番号のシーケンスに従って各自１つのチャネルに割当てられ、各チャネルは前記割当てられたブロックシーケンスのブロックを繰り返し配信し、前記配信受信機は前記チャネルのｒ個（１＜ｒ≦ｃ）のチャネルを同時に受信する容量を有し、前記配信受信機は逐次的に最下位からｒ個のチャネルの受信を開始し、チャネルｉのブロックシーケンスのすべてのブロックを受信するたび、チャネルｉの受信を終了し、すべてのブロックシーケンスが受信されるまで、チャネルｒ＋ｉの受信を開始するよう動作することを特徴とするシステム。
【請求項４】
請求項３記載の配信システムであって、
前記ニアビデオオンデマンドスケジュールは、前記タイトルのデータブロックが前記配信システムのｃ個のパラレルな等しい容量のチャネルを介し配信されることを規定し、各配信チャネルは各自の逐次的チャネル番号に関連付けされ、前記複数の配信チャネルは複数の時間逐次的インタリーブ処理されたサブチャネルを有し、チャネルのサブチャネル数は前記チャネル番号に対し単調非減少であり、前記チャネルのサブチャネルは各自の逐次的なサブチャネル番号に関連付けされ、前記タイトルは複数の連続するデータブロックシーケンスに分割され、各ブロックシーケンスは前記チャネル番号及びサブチャネル番号のシーケンスに従って各自１つのサブチャネルに割当てられ、各サブチャネルは前記割当てられたブロックシーケンスのブロックを繰り返し配信し、前記配信受信機は前記チャネルのｒ個（１＜ｒ≦ｃ）のチャネルのすべてのサブチャネルを同時に受信する容量を有し、前記配信受信機は逐次的に最下位からｒ個のチャネルのすべてのサブチャネルの受信を開始し、チャネルｉのサブチャネルのブロックシーケンスのすべてのブロックを受信するたび、チャネルｉのサブチャネルの受信を終了し、すべてのブロックシーケンスが受信されるまで、チャネルｒ＋ｉのサブチャネルの受信を開始するよう動作し、前記フィルタコントローラは前記対象受信機の何れもが前記サブチャネルに割り当てられたデータブロックを受信する必要がある場合、サブチャネルをフィルタリングするよう前記中間配信装置を制御するよう動作することを特徴とするシステム。
【請求項５】
請求項２記載の配信システムであって、
前記フィルタコントローラは、前記格納されている情報を利用して、各チャネルに対し少なくとも１つの対象受信機が前記チャネルの次のタイムスロットのデータブロックを受信する必要があるか判断し、前記対象受信機の何れもが前記次のタイムスロットのデータブロックを受信する必要がない場合、前記データブロックをフィルタリングするよう前記中間配信装置を制御するよう動作することを特徴とするシステム。
【請求項６】
請求項５記載の配信システムであって、
前記チャネルは時間多重化されることを特徴とするシステム。
【請求項７】
請求項３記載の配信システムであって、
前記中間配信装置は、少なくとも１つの対象受信機により受信される前記ｒ個のチャネルを介し配信されるデータブロックを抽出し、前記抽出されたデータブロックを所定のチャネルを介し前記対象受信機に送信するよう動作することを特徴とするシステム。
【請求項８】
請求項１記載の配信システムであって、
前記中間配信装置は、前記フィルタコントローラを有することを特徴とするシステム。
【請求項９】
請求項１記載の配信システムであって、
前記配信受信機の少なくとも１つは、該配信システムのアップストリームチャネルを介し前記フィルタコントローラと通信するよう動作することを特徴とするシステム。
【請求項１０】
ニアビデオオンデマンド配信プロトコルを利用して、中央配信装置から少なくとも１つの中間配信装置レイヤを介し複数の配信受信機までのデータ配信装置の階層的ネットワークを介しデータブロックシーケンスとして少なくとも１つのタイトルを配信する方法であって、
前記タイトルの供給に対する要求を配信受信機から受信するステップと、
少なくとも１つの中間配信装置において、前記中間配信装置の階層的に下位にある受信機により要求されていない前記タイトルのデータブロックをフィルタリングするステップと、
を有することを特徴とする方法。
【請求項１１】
請求項１記載の配信システムにおいて利用される配信受信機であって、
前記配信システムは、ニアビデオオンデマンド配信プロトコルを利用して、前記配信システムのダウンストリームチャネルを介しタイトルをデータブロックシーケンスとして配信するため、中央配信装置から少なくとも１つの中間配信装置レイヤを介し複数の配信受信機までのデータ配信装置の階層的ネットワークを有し、該配信受信機は、フィルタコントローラが該配信受信機の階層的に上位にある少なくとも１つの中間配信装置の階層的に下位にある受信機により要求されていない前記タイトルのデータブロックをフィルタリングするよう前記少なくとも１つの中間配信装置を制御することを可能にするため、前記配信システムのアップストリームチャネルを介し前記フィルタコントローラと通信するよう動作することを特徴とする配信受信機。
【請求項１２】
請求項１記載の配信システムにおいて利用されるフィルタコントローラであって、
前記配信システムは、ニアビデオオンデマンド配信プロトコルを利用して、前記配信システムのダウンストリームチャネルを介しタイトルをデータブロックシーケンスとして配信するため、中央配信装置から少なくとも１つの中間配信装置レイヤを介し複数の配信受信機までのデータ配信装置の階層的ネットワークを有し、該フィルタコントローラは、前記タイトルの供給に対する要求を配信受信機から受信するよう動作し、少なくとも１つの中間配信装置を該中間配信装置の階層的に下位にある受信機により要求されていない前記タイトルのデータブロックをフィルタリングするよう制御することを特徴とするフィルタコントローラ。
【請求項１３】
請求項１記載の配信システムにおいて利用される中間配信装置であって、
前記配信システムは、ニアビデオオンデマンド配信プロトコルを利用して、前記配信システムのダウンストリームチャネルを介しタイトルをデータブロックシーケンスとして配信するため、中央配信装置から少なくとも１つの中間配信装置レイヤを介し複数の配信受信機までのデータ配信装置の階層的ネットワークを有し、該中間配信装置は、該中間配信装置の階層的に下位にある受信機により要求されていない前記タイトルのデータブロックをフィルタリングするよう動作することを特徴とする中間配信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ニアビデオオンデマンド配信プロトコルを利用した少なくとも１つのタイトルを配信し、複数の配信受信機と中央配信装置から少なくとも１つの中間配信装置レイヤを介し複数の配信受信機までのデータ配信装置の階層的ネットワークとを有する配信システムに関する。本発明はまた、データストリームを配信する方法に関する、本発明はさらに、当該システムにおいて利用される配信受信機、配信装置及びフィルタコントローラに関する。
【背景技術】
【０００２】
ケーブルネットワークなどの複数の配信受信機にデータストリームを配信する従来の配信システムは、データ配信装置の階層的ネットワークを利用する。ネットワークのトップは、１つの中央ヘッドエンドにより構成され、最下位の装置レイヤは、宅内の配信受信機により構成される。音声/映像を合計２００，０００世帯に配信するためのシステムは、７つの装置レイヤの階層を利用する。最上位では、マスタヘッドエンドにより各々が離散的な都市域をカバーする５つのメトロポリタンヘッドエンドにデータが供給される。各地域は、メトロポリタンヘッドエンドとハブとの間の直接的なリンクにより、さらに５つ以上のハブに分割される。各ハブは、各々が４つの同軸ケーブルからの２０個のファイバノードに直接接続される。各同軸ケーブルは、１００世帯までの家庭に接続される。
【０００３】
典型的には、同軸ケーブルは、ダウンストリーム（すなわち、配信受信機方向に）に１秒あたり１ギガビットのオーダによる容量を有する。この容量の一部は、最も普及したテレビ局などの従来の放送チャネルに用意されている。このようなチャネルは、実際の受信は支払いに応じた限定的なものであるかもしれないが、原則的にはすべての受信機により受信可能である（すなわち、すべての同軸ケーブルを介し送信される）。帯域幅の一部は、ネットワークを介した配信受信機からネットワーク外部の対象となる主体へのアップストリーム通信に用意されてもよい。通常、このアップストリーム通信は、ブロードバンドケーブルモデムを利用したインターネットに向かうものである。それはまた、対話的アプリケーションのサービス提供者へのものであってもよい。残りの帯域幅により、タイトルの受信を所望していることをユーザが示した直後に供給が実質的に開始され、大部分の受信機が同時にタイトル（映画など）の受信が可能な効果的なビデオオンデマンドサービスを提供することは、実現不可能ではないが、困難である。これを解消するため、複数の配信チャネルのグループを用いて１つのタイトルが繰り返し配信されるいわゆるニアビデオオンデマンド（ｎｅａｒ−ｖｉｄｅｏ−ｏｎ−ｄｅｍａｎｄ）放送配信プロトコルが開発された。効果的なプロトコルとして、Ｊ．Ｆ．Ｐａｒｉｓの「Ａ  ｆｉｘｅｄ−ｄｅｌａｙ  ｂｒｏａｄｃａｓｔｉｎｇ  ｐｒｏｔｏｃｏｌ  ｆｏｒ  ｖｉｄｅｏ−ｏｎ−ｄｅｍａｎｄ」（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １０ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ｎｅｔｗｏｒｋｓ，ｐａｇｅ４１８−４２３）に開示されるＰａｇｏｄａ配信プロトコルがあげられる。このプロトコルでは、例えば、１分間の開始時の遅延の後、配信受信機は、チャネルにおけるブロック送信シーケンスと、ブロックがどのチャネルにおいて送信されるかプロトコルにより規定された複数のチャネルからブロックを抽出することにより、リアルタイムでのタイトルの再生が可能となる。典型的には、受信機は、データのアンダフロー（ｕｎｄｅｒｆｌｏｗ）を回避するため、チャネルグループのいくつか（例えば、２つのチャネル）をタップ処理する必要がある。第１チャネルの繰り返しレートは最大となり、これにより、開始時の遅延は比較的低いものとなる。最後のチャネルの繰り返しレートは最小となる（当該チャネルは、大部分の異なるブロックの送信に利用することができる）。大量のニアビデオオンデマンド映画（例えば、１０００本の映画）の同時送信をサポートするため、配信システムは高帯域幅を必要とする。マスタヘッドエンドとファイバノードとの間のレベルでは、これは、光ファイバベースの配信を利用するなど、適切な専用リンクを用いて容易に実現することができる。特に最も下位のレベルでは、同軸などの共有媒体の利用が最も経済的である。共有媒体の帯域幅は、比較的多数のニアビデオオンデマンドタイトルの配信に十分でない。このことは、上記システムの導入を妨げるものとなる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の課題は、より多くのタイトルの配信をサポートすることが可能なシステムにおいて利用されるニアビデオオンデマンドシステム及び装置を提供することである。
【課題を解決するための手段】
【０００５】
本発明の課題を解決するため、ニアビデオオンデマンド配信プロトコルを利用して少なくとも１つのタイトルを配信する配信システムは、複数の配信受信機と、前記タイトルをデータブロックシーケンスとして配信するため、中央配信装置から少なくとも１つの中間配信装置レイヤを介し前記複数の配信受信機までのデータ配信装置の階層的ネットワークと、前記タイトルの供給に対する配信装置からの要求を受信するよう動作し、少なくとも１つの中間配信装置の階層的に下位の受信機により要求されていない前記タイトルのデータブロックをフィルタリングするよう前記少なくとも１つの中間配信装置を制御する少なくとも１つのフィルタコントローラとを有する。要求されないブロックをフィルタリングすることにより、中間配信装置の下位のネットワークにおける容量が解放される。この容量は、多数のタイトルを配信するため中央配信装置により利用可能となる。フィルタコントローラは、下位のネットワークセグメントによりどのタイトルが必要とされるかモニタし、それに応じてフィルタリングを制御する。
【０００６】
従属クレーム２の手段により示されるように、前記タイトルのデータブロックは、前記タイトルの各データブロックに対し、前記タイトルの第１データブロックを配信するのに使用されるタイムスロットに対して前記データブロックを配信するタイムスロットとチャネルを規定するニアビデオオンデマンドスケジュールに従って、複数のチャネルを介し該複数のチャネル内の逐次的タイムスロットを用いて配信され、チャネルに割当てられるデータブロックは前記チャネル内で繰り返し配信され、前記フィルタコントローラは、前記タイトルを要求した前記中間配信装置の階層的に下位にあるすべての対象受信機に関する情報を、前記フィルタコントローラが各チャネルに対し前記対象受信機の少なくとも１つが前記チャネルに割当てられたデータブロックを受信する必要があるか判断することが可能となるように格納し、前記対象受信機の何れもが前記チャネルに割当てられたデータブロックを受信する必要がない場合、チャネルをフィルタリングするよう前記中間配信装置を制御するよう動作する。フィルタコントローラは、タイトルの受信を開始したタイムスロット、現在のタイムスロット及び/または受信されるデータブロックなどの対象受信機に関する情報を格納する。当該情報は、フィルタコントローラがチャネルを配信する必要があるか判断することを可能にする（チャネルは、少なくとも１つの対象受信機がまだそれをタッピングしている場合、配信される必要がある）。対象受信機の何れもがチャネルをタッピングしていない場合、チャネル全体がフィルタリングされ、他のニアビデオオンデマンドタイトルを配信するためなどの他の目的に使用することができる。
【０００７】
従属クレーム３の手段により示されるように、前記ニアビデオオンデマンドスケジュールは、前記タイトルのデータブロックが前記配信システムのｃ個のパラレルな等しい容量のチャネルを介し配信されることを規定し、各配信チャネルは各自の逐次的チャネル番号に関連付けされ、前記複数の配信チャネルは複数の時間逐次的インタリーブ処理されたサブチャネルを有し、チャネルのサブチャネル数は前記チャネル番号に対し単調非減少であり、前記チャネルのサブチャネルは各自の逐次的なサブチャネル番号に関連付けされ、前記タイトルは複数の連続するデータブロックシーケンスに分割され、各ブロックシーケンスは前記チャネル番号及びサブチャネル番号のシーケンスに従って各自１つのサブチャネルに割当てられ、各サブチャネルは前記割当てられたブロックシーケンスのブロックを繰り返し配信し、前記配信受信機は前記チャネルのｒ個（１＜ｒ≦ｃ）のチャネルのすべてのサブチャネルを同時に受信する容量を有し、前記配信受信機は逐次的に最下位からｒ個のチャネルのすべてのサブチャネルの受信を開始し、チャネルｉのサブチャネルのブロックシーケンスのすべてのブロックを受信するたび、チャネルｉのサブチャネルの受信を終了し、すべてのブロックシーケンスが受信されるまで、チャネルｒ＋ｉのサブチャネルの受信を開始するよう動作し、前記フィルタコントローラは前記対象受信機の何れもが前記サブチャネルに割り当てられたデータブロックを受信する必要がある場合、サブチャネルをフィルタリングするよう前記中間配信装置を制御するよう動作する。このようなＰａｇｏｄａ形式の配信スケジュールは、フィルタコントローラが各チャネルに対し、受信機により使用される第１タイムスロットのみに基づき、データブロックが次のタイムスロットに必要であるか単に判断することを可能にする。特に、フィルタコントローラは、受信開始を知っていれさえすればよく、チャネルレベルでのフィルタリングを制御可能となるように、受信機からの連続的な情報フローを必要としない。
【０００８】
従属クレーム４の手段により示されるように、Ｐａｇｏｄａ形式の配信スケジュールは、チャネルが時間多重化されたサブチャネルに分割されるサブチャネルレベルでのフィルタコントローラによるフィルタリングを可能にする。
【０００９】
同様に、従属クレーム５の手段により示されるように、Ｐａｇｏｄａ形式の配信スケジュールは、データブロックレベルでのフィルタコントローラによるフィルタリングを可能にする。
【００１０】
従属クレーム６の手段により示されるように、チャネルは時間多重化される。チャネルを時間多重化することにより、チャネルの再利用が簡単化される。実際、チャネルをフィルタリングすると、サブチャネルまたは個々のブロックはすべて、他の目的のため再利用可能な１以上のタイムスロットを解放する。
【００１１】
従属クレーム７の手段により示されるように、前記中間配信装置は、少なくとも１つの対象受信機により受信される前記ｒ個のチャネルを介し配信されるデータブロックを抽出し、前記抽出されたデータブロックを所定のチャネルを介し前記対象受信機に送信するよう動作する。特にあるタイトルが異なるタイムスロットを利用して多数の受信機により受信されない場合、Ｎ個のチャネルをｒ個のチャネルのみに減少させることが効果的な方法である。当該タイトルに利用される残りすべての（Ｎ−ｒ）個のチャネルは、フィルタリングすることができる。
【００１２】
従属クレーム８の手段により示されるように、中間配信装置は、フィルタコントローラを有する。これにより、両者の間のやりとりを簡単化することができる。
【００１３】
従属クレーム９の手段により示されるように、前記配信受信機の少なくとも１つは、該配信システムのアップストリームチャネルを介し前記フィルタコントローラと通信するよう動作する。アップストリームチャネルを使用することは、フィルタコントローラと通信する効果的な方法である。特にフィルタコントローラが中間配信装置と一体化されている場合、アップストリーム通信は、配信受信機がネットワークトポロジーに関する情報及び/または配信装置及び/またはフィルタコントローラの位置を必要とすることなく、フィルタコントローラにより単に傍受することが可能である。
【００１４】
本発明の上記及び他の特徴は、以下で説明される実施例を参照することにより明らかとなるであろう。
【発明を実施するための最良の形態】
【００１５】
図２は、本発明による配信システムのブロック図を示す。配信システム１００は、データ配信装置の階層的ネットワークを有する。ネットワークの最上位は、中央配信装置１１０により構成される。本システムは、少なくとも１つの中間配信装置レイヤを有する。図を簡単化するため、各々が離散的な地理的エリアをカバーする３つの中間配信装置１２０、１３０及び１４０によるダウンストリーム配信のための１つのみの中間レイヤが示される。図１は、３つの中間ダウンストリームレイヤ（メトロヘッドエンド、ハブ、ファイバノード）による接続された２００，０００世帯の家庭を有する町に対する典型的な階層的ネットワークを示す。本例では、４つの同軸セグメントが各ファイバノードに接続されている。図２はまた、中央配信装置１１０から始まり、中間配信装置１２０、１３０及び１４０を介し行われ、システムの複数の配信受信機において終わるダウンストリームパス１６０を示す。従来、配信装置は階層的に１段低いレイヤ上の受信機/配信装置に配信信号を分割する。簡単化のため、配信受信機１５０のみが示される。典型的には、当該パスは複数のチャネルに分割され、各チャネルはサブチャネルに分割されてもよい。最下位レベルでは、通常は配信受信機に共有される媒体を構成する同軸セグメントが利用される。同軸上では、チャネルは通常は周波数多重化されている。当該チャネル内のサブチャネルは、時間多重化されてもよい。より上位のレベルでは、典型的には、光ファイバが利用される。このような媒体では、チャネルはまた時間多重化されてもよい。各種メディア及び多重化技術などの任意の適切な送信技術が利用されてもよい。ニアビデオオンデマンド（ＮＶｏＤ）プロトコルを利用して、ネットワークを介し複数の配信受信機にデジタルデータストリームを配信するための配信システムが説明される。データストリームは、ＭＰＥＧ２映像符号化などの任意の適切な技術を用いて符号化されていてもよい。配信データは特定の受信機にアドレス指定されるのでなく、原則的には階層的ネットワークのすべてのセグメントにおける受信機全体に受信可能とされる。データへのアクセスは、支払いによるものであってもよい。本発明による配信システムでは、適切な限定受信機構を用いてアクセスが制御されてもよい。システムの各装置に対して、図２は、配信データの送受信及びすべての必要な処理の実行に必要とされるハードウェア/ソフトウェア機能１１２、１２２、１３２、１４２及び１５２を概略的に示す。このようなハードウェア/ソフトウェアは既知であり、本発明によるシステムに利用可能である。ハードウェア/ソフトウェアは、信号プロセッサなどの適切なプロセッサを利用することにより制御される適切な送受信機（光ファイバ受信機及び/またはケーブルモデムなど）により構成されてもよい。また、ＭＰＥＧエンコーダ/デコーダ、バッファなどの専用ハードウェアが利用されてもよい。
【００１６】
従来、すべてのデータストリームは中央配信装置１１０により挿入され、各中間レイヤによりネットワークの最下位部分に無修正でコピーされていた（すなわち、信号は分割される）。挿入のため、中央配信装置は、映画などの複数のタイトルを格納するストレージ１１５を有するようにしてもよい。中央配信装置はまた、衛星接続などを介しライブの配信を受信する接続１６０を有するようにしてもよい。ストレージ１１５は、ＲＡＩＤシステムなどに基づき適切なサーバプラットフォーム上で実現されてもよい。受信機はまたストレージ１５５にアクセスする。このストレージはまた、フラッシュメモリのＲＡＭなどのソリッドステートメモリまたはハードディスクにより構成されてもよい。ストレージは、タイトル再生前に、ダウンストリームチャネルを介し受信されたタイトルの一部またはすべてを（一時的または恒久的に）格納するのに利用される。図２はまた、中央配信装置へのネットワークのアップストリームチャネル１７０を示す。原則的に、このアップストリームチャネルは、上位に移行する中間レベルにおいて開始されるかもしれない。好ましくは、アップストリームチャネルは、最下位レベルにすでに存在し、配信システムの外部との通信を可能にする（例えば、中央配信装置または中間配信装置を介しインターネットになど）。
［フィルタリング］
多数のニアビデオオンデマンド映画（例えば、１０００本の映画）の同時送信をサポートするため、配信システムは、高帯域幅を必要とする。マスタヘッドエンドとファイバノードとの間のレベルに対し、これは、光ファイバベースの配信を利用するなど、適切な専用リンクを利用することにより容易に実現することができる。特に最下位レベルでは、同軸などの共有媒体の使用が最も経済的である。例えば、光ファイバモードによりデータを選択的にフィルタリングし、少なくとも１つの対象となる受信機が存在するデータ上にわたすことによって、帯域幅を比較的多数の映画の同時配信に十分なものにすることができる。ここで、ネットワークの上位レベルではまた、すでに選択を行うことが可能であり、例えば、ハブはそれのサブツリーの任意のユーザにより使用される映画のブロックのみを転送するだけでよく、その他のものは転送される必要はない。
【００１７】
フィルタリングを可能にするため、本システムは、中間配信装置の階層的に下位にある受信機によって要求されなかったタイトルのデータブロックをフィルタリングするよう少なくとも１つの中間配信装置を制御するよう動作する少なくとも１つのフィルタコントローラを有する。図２は、１つの中央フィルタコントローラ１８０を示す。好ましくは、本システムは、各フィルタコントローラが１つの中間配信装置を効果的に制御し、それと一体とされてもよい複数のフィルタコントローラを有する。フィルタコントローラがタイトルのデータブロックを必要とする受信機が存在するか判断できるようにするため、フィルタコントローラは、タイトルを供給するため、配信受信機から要求を直接的または間接的に受信する。好ましくは、フィルタコントローラは、この情報をネットワークのアップストリームチャネルを介し受信機から直接受信する。使用されているＮＶｏＤプロトコルに依存して、コントローラにより制御されるネットワークセグメントの一部である各受信機による受信開始（例えば、第１ブロックのタイムスロット）をフィルタコントローラが知るには十分であるかもしれない。これは、例えば、Ｐａｇｏｄａなどの固定遅延ＮＶｏＤ配信スケジュールにより場合である。このようなスケジュールは、タイトルの各データブロックに対し、当該タイトルの第１データブロックを配信するのに使用されるタイムスロットに対するデータブロックを配信するためのタイムスロット及びチャネル（及び/またはチャネル内のサブチャネル）を規定する。他のスケジュールでは、フィルタコントローラが受信機により求められるブロックに対しより定期的な更新がなされることが要求されてもよい。フィルタコントローラは、各チャネルに対して、対象となる受信機の少なくとも１つが時間内に各ポイントにおいて当該チャネルに割当てられたデータブロックを受信する必要があるか判断できるようにするため、タイトルを要求した中間配信装置の階層的に下位にあるすべての受信機（「対象受信機」）に関する情報を格納する。説明された固定遅延スケジュールでは、フィルタコントローラは、受信機により使用される第１データブロックのタイムスロットを格納しさえすればよい。これらのスケジュールはブロック送信スケジュール全体を規定しているため、現在使用されているブロックなどの他の情報は、原則的に、次のタイムスロットにおいて、受信機がデータブロックを必要とするか、必要とする場合には、どのチャネル/サブチャネルを介してか判断するのに十分である。フィルタリングは、例えば、チャネルまたはサブチャネルを介した配信が１以上のブロックに対し中断されるなど、いくつかの方法により実行することができる。フィルタリングは各タイムスロット、あるいはチャネルまたはサブチャネルを介し繰り返し配信されるタイトルのブロックシーケンスに対応するタイムスロットシーケンスに対してのみ行われるようにしてもよい。フィルタコントローラは、各タイムスロットに対し、中央配信装置から受信したデータブロックをわたすかどうか中間配信装置に指示する。ブロック（ブロックシーケンス）をフィルタリングすることにより節約される帯域幅が再利用できるということは理解される���あろう。システムのチャネルが時間多重化されている場合、再利用は特に簡単であるかもしれない。このようなシステムでは、典型的には、未使用のタイムスロットは、他の同期チャネル（配信、マルチキャストまたは直接的なアドレス指定）または非同期データのためなど他の目的に利用可能である。周波数多重化チャネルを利用するシステムでは、フィルタコントローラは、（多過ぎる）入力チャネルの少数の出力チャネルへの変換方法を中間配信装置に指示するようにしてもよい。小さなシーケンス（または各ブロックでもよい）のフィルタリングでは、フィルタコントローラは、どの周波数においてチャネルの受信が可能であるか配信受信機に通知する必要があるかもしれない（例えば、直接アドレス指定されたメッセージを介し）。特に固定遅延スケジュールでは、フィルタコントローラは、チャネルと周波数との変換を定期的に計算することができる。フィルタコントローラは、そのようなスケジュールを受信機に配信するようにしてもよい。
【００１８】
好適な一実施例では、中間配信装置は、配信装置から配信されるストリームからの１以上の受信機に対するチャネルを有するようにしてもよい。これは、その時点で当該タイトルに関心のある受信機が比較的少数である場合、及び/またはそれらがほとんど同じシーケンスを見ている場合、特に効果的である。このため、配信装置は、当該タイトルに専用のチャネルグループから受信機により求められるタイトルのデータブロックを抽出し、少数のチャネルを用いて受信機に再配信する。Ｐａｇｏｄａスケジュールに対し以下に与えられる例では、これは、タイトルに割当てられたｃ個のチャネルからブロックを抽出し、ｒ個のチャネルのみを用いてブロックを再配信することに関するものであってもよい。
【００１９】
本発明によるフィルタリングが、ＰａｇｏｄａＮＶｏＤ配信プロトコルを参照して説明される。当業者は、同一の原則を他のスケジュールに適用することも可能であろう。
［固定遅延Ｐａｇｏｄａ配信］
好ましくは、タイトルのデータブロックを配信するためのニアビデオオンデマンドプロトコルとして、固定遅延Ｐａｇｏｄａ配信プロトコルが利用される。このプロトコルは、漸近的に最適であり、限定的なクライアントＩ/Ｏ帯域幅に容易に適応可能である。図３Ａにおいて、これの小さな例が与えられる。図３Ｂは、任意の時点における要求に対し抽出がどのように実行されるか示す。図３の例では、高々２つのチャネルが同時にタップ処理され、すべてのブロックが時間内に到着する。このＮＶｏＤスキームのキーは、チャネルｉがチャネルｉ−２のタッピングが完了した後にタップ処理を開始されるというものであり、これにより、タップ処理されるチャネル数を２に限定することができる。このことは、例えば、チャネル４に対して、受信機は当該チャネルのタップ処理が開始可能となる前に、２時間単位だけ待機する必要があるということを意味するものである。ブロック７は要求後に７時間単位以内で受信される必要があるため、これは、５時間単位のみが受信するのに残され、これにより７でなく高々５期間で送信される必要があるということを意味するものである。実際、それは４期間で送信される。上記配信スキームの一般的構成が、受信可能な所定数ｒのクライアントチャネルと所定数ｃのサーバチャネルに対して説明される。さらに、オフセットｏは、説明されるように、再生前にユーザが追加的ｏ時間単位だけ常に待機するということを意味すると考えられる。チャネルｉの（タップ処理）のセグメントの始まりはｓｉにより表され、終わりはｅｉにより表される。このとき、ユーザが受信可能な最大チャネル数ｒを超えないように、チャネルｉ＝ｒ＋Ｉ，．．．，ｃにおけるタップ処理は、チャネルｉ−ｒのタップ処理が終了した後に開始される。従って、
【００２０】
【数１】
2006509455.tif 000003
次に、チャネルｉにおいて、ブロックｌｉ，．．．，ｈｉが送信される。従って、チャネルｉで送信される相異なるブロック数は、
ｎｉ＝ｈｉ−ｌｉ＋１により与えられる。ただし、
【００２１】
【数２】
2006509455.tif 000004
である。
【００２２】
時間内に各ブロックを受信するため、ブロックｋは、時間単位ｏ＋ｋにおいて、またはそれ以前に送信されるべきである。ブロックｋが時間単位ｓｉで受信を開始するチャネルｉで送信される場合、これは、ブロックｋが高々ｏ＋ｋ−（ｓｉ―１）の期間で配信されるべきであるということを意味する。理想的には、当該期間は各ブロックｋに対し正確に満たされるが、十分近接させるには十分である。
【００２３】
Ｐａｇｏｄａスキームによるチャネルｉの構成は以下のようなものである。まず、チャネルｉは、
【００２４】
【数３】
2006509455.tif 000005
によって、すなわち、最も近い整数に丸められたブロックｌｉの最適期間の平方根によって与えられるｄｉ個のサブチャネルに分割される。各サブチャネルは、ラウンドロビン方式によりブロックを送信するための時間単位の一部１/ｄｉを取得する。言い換えると、時間単位ｔにおいて、サブチャネルｔ  ｍｏｄ  ｄｉは１つのブロックを送信することが可能であり、サブチャネルは０，１，．．．，ｄｉ−１に番号付けされる。
【００２５】
ここで、ブロックｋにチャネルｉのサブチャネル内において期間ｐｋが与えられると、ブロックｋはｐｋｄｉの期間によりチャネルｉにおいて配信される。従って、
ｐｋｄｉ≦ｏ＋ｋ−（ｓｉ―１）
とするため、
【００２６】
【数４】
2006509455.tif 000006
となることを意味する。
【００２７】
各サブチャネル内のすべてのブロックに対して等しい期間をとることにより、衝突を回避することができる。従って、ｌｉｊがチャネルｉのサブチャネルｊにおける最小ブロック番号である場合、これは、チャネルｉのサブチャネルｊ内のすべてのブロックに対して、以下の期間が選ばれることを意味する。
【００２８】
【数５】
2006509455.tif 000007
従って、当該サブチャネルにおいてｎｉｊ＝ｐｉｊ個のブロック（ブロックｌｉｊ，．．．，ｌｉｊ＋ｎｉｊ−１）を送信することが可能となる。ブロック番号ｌｉｊは、
【００２９】
【数６】
2006509455.tif 000008
により与えられる。
【００３０】
チャネルｉで送信されるブロックの総数ｎｉは、
【００３１】
【数７】
2006509455.tif 000009
により与えられ、これにより、
ｈｉ＝ｌｉ＋ｎｉ−１
を計算することができる。
【００３２】
最終的に、あるチャネル内のセグメントのスタート及びエンド時点が参照される。チャネルｉのすべてのサブチャネルは、時点ｓｉにおいて送信を開始する。チャネルｉのサブチャネルｊは、ｎｉｊブロックの後に準備され、チャネルｉ内でｄｉｎｉｊ時間単位を要する。従って、サブチャネルｊの当該セグメントのエンドは、
ｅｉｊ＝ｓｉ−１＋ｄｉｎｉｊにより与えられ、それの最後のサブチャネルが、
【００３３】
【数８】
2006509455.tif 000010
において終了するとき、チャネルｉは終了する。
【００３４】
上記を例示するため、図４は、図３の例に第５チャネルを追加することを示す。第５チャネルに対して、以下の式が成り立つ。すなわち、ｌ５＝１２，ｓ５＝ｅ３＋１＝６及びオフセットｏ＝０である。サブチャネル数は、
【００３５】
【数９】
2006509455.tif 000011
である。サブチャネルｊ＝０に対し、これはｌ５，０＝１２を与え、これにより当該サブチャネルにおいてブロック１２と１３である
【００３６】
【数１０】
2006509455.tif 000012
個のブロックを送信することが可能である。サブチャネルｊ＝１に対し、これはｌ５，１＝１４を与え、これにより当該サブチャネルにおいてブロック１４、１５及び１６である
【００３７】
【数１１】
2006509455.tif 000013
個のブロックを送信することが可能となる。サブチャネルｊ＝２に対し、これはｌ５，２＝１７を与え、これにより当該サブチャネルにおいてブロック１７、１８、１９及び２０である
【００３８】
【数１２】
2006509455.tif 000014
個のブロックを送信することが可能となる。当該サブチャネルのセグメントのエンドは、
ｅ５，０＝５＋３＊２＝１１、
ｅ５，１＝５＋３＊３＝１４及び
ｅ５，２＝５＋３＊４＝１７
により与えられ、これによりｅ５＝１７となる。
【００３９】
ｈｉの値、すなわち、映画が分割可能であるブロック数は、オフセットゼロとｒの各値に対してテーブル１により与えられる。当該系列は、ｒ＝２，３，４及び∞のそれぞれに対し、約１．７５，２．４２，２．６２及び
【００４０】
【数１３】
2006509455.tif 000015
をベースとするべき級数に収束する。
【００４１】
【表１】
2006509455.tif 000016
最後の列は、クライアントチャネル数が無制限であることに対応する。ｈｃの上記値を用いて、最大待機時間は、ｃ個のチャネルを使用するとき、映画の長さの一部１/ｈｃにより与えられる。正のオフセットｏが用いられる場合、最大待機時間の一般的な式は、映画の長さの一部（ｏ＋１）/ｈｃとなる。
【００４２】
以前のセクションでは、チャネルｉのサブチャネルの個数ｄｉは一定とされ、式（１）により与えられる。ここで、映画が分割可能となるブロック数に関してより良い解を得るために、異なる値が用いられるようにしてもよい。このため、チャネルｉごとに式（１）で与えられる目標値近傍のいくつかの異なる値を求め、チャネルｉに適合可能なブロック数を計算し、チャネルｉが最大となるブロック数を有することが可能なサブチャネル数をとることにより、１次最適化が適用可能である。ここで、当該処理は、直接的な実現により指数的な実行時間がかかることを回避するため、個々のチャネルごとに実行される。すなわち、以前のチャネルへのバックトラッキングは発生しない。これは、チャネルｉにおいてより多くのブロックを取得するためチャネルｉにおいて異なる個数のサブチャネルを選択することが、エンド時間ｅｉを増加させ、これによりチャネルｉ＋ｒのスタート時間ｓｉ＋ｒを増加させ、当該チャネルに適合可能なブロック数を減少させるとき、次善解を導くかもしれない。にもかかわらず、この１次最適化は、テーブル２に示されるような良好な結果を与える。オフセットゼロとｒの異なる値に対して、ｈｉの新たな値が与えられる。これらの値は前のテーブルのものより大きいが、べき級数のベースはテーブル１のものと同一である。
【００４３】
【表２】
2006509455.tif 000017
以下では、従来のＰａｇｏｄａプロトコルに対するテーブル１の値が用いられる。
【００４４】
これまでの説明では、タイトルは一定のビットレート（ＣＢＲ）を有すると仮定されていた。しかしながら、この送信スキームは、可変ビットレート（ＶＢＲ）ストリームに対処するよう容易に適応化可能である。ブロックｋが到達しなければならない時点は、ＣＢＲストリームではｏ＋ｋにより与えられ、このとき関数ｏ＋ｔ（ｋ）により与えられる。ここで、ｔ（ｋ）は、当該ストリームが時間内に再生される方法を説明する増加関数である。送信スキームに対する効果は以下の通りである。ブロックｋが時点ｓｉにおいて開始されるチャネルｉにおいて送信される場合、ブロックｋは高々ｏ＋ｔ（ｋ）−（ｓｉ―１）の期間により配信される必要がある。従って、式（１）で与えられるようなサブチャネル数の目標値は、
【００４５】
【数１４】
2006509455.tif 000018
となる。
【００４６】
このとき、チャネルｉのサブチャネルｊにおけるブロック数、すなわち、当該サブチャネル内で用いられる期間は、
【００４７】
【数１５】
2006509455.tif 000019
により与えられる。残りの計算は同様である。
［ネットワーク仮定］
以下において、図１に示されるような階層的ネットワークの例が与えられる。主要なボトルネックは、家庭とファイバノードとの間のアップストリーム及びダウンストリームリンクの容量により与えられると仮定される。この例では、ファイバノードから家庭までのダウンストリームリンクの容量は２０Ｍｂ/ｓであると仮定される。５Ｍｂ/ｓの映像伝送レートを仮定すると、このことは、４つの映像チャネルが各家庭にダウンストリームすることが可能であることを意味する。この例では、ファイバノードの上位の帯域幅には実際的な制限はないと仮定される。さらに、各々が６０００秒（１００分）からなる１０００本の映画を有することが望ましいと仮定される。映画のサイズは、３０Ｇｂ、すなわち、３．７５ＧＢである。約１秒の最大反応時間と、タップ処理されるｒ＝３チャネルの制約を目標として、テーブル１は、映画が６３０８ブロックに分割可能な１１の送信チャネルが利用されるべきであることを示し、実際の最大反応時間は、６０００/６３０８≒０．９５秒となる。１０００本の映画すべての１１の送信チャネルを生成することは、５５Ｇｂ/ｓを利用することになるであろう。これは容量が１．５Ｇｂ/ｓのオーダであるネットワークの最下位レベルの容量を上回るということが明らかである。
［本発明によるフィルタリング］
従来のＰａｇｏｄａＮＶｏＤ配信スキームあるいは他の同様のＮＶｏＤスキームの短所は、すべてのタイトルが大量の帯域幅をフルに占有した状態で連続的に配信されるということである。これは、タイトルを受信する多数の受信機に人気のある映画には大きな問題ではなく、人気のないタイトルに対する帯域幅の浪費である。既知のシステムでは、人気のない映画は人気のある映画に割当てられる帯域幅と同じ大きさの帯域幅を取得する。本発明によると、使用されるチャネル数は、ユーザ要求に供することが求められていないブロックを送信しないことにより減少させる。図５は、矢印により示される３つの初期ユーザ要求に対し、Ｐａｇｏｄａスケジュールを用いて受信機により実際に読み込まれるブロックを示す。これらのブロックはグレイで示されている。他のすべてのブロックは配信されるが使用はされず、帯域幅が浪費される。Ｐａｇｏｄａに類似したスケジュールでは、ある受信機のみが受信機に固有のスタート及びエンド時間との間にチャネルをタッピングしていることが観察される。当該チャネルに割当てられたブロックシーケンスの他のすべての繰り返しは、当該受信機（しかしおそらく他の受信機により）には受信されない。同じ観察がサブチャネルレベルにも当てはまる。すなわち、各サブチャネルは、当該サブチャネルに対する受信機の特定のスタート時間とエンド時間との間で受信機によりタッピングさえされればよい。この結果、ブロックがある要求に対するリードインターバル内に属する場合のみ、ブロックは送信される必要がある（すなわち、少なくとも１つの受信機は、ブロック/サブチャネルまたはチャネルを介し送信されるシーケンスまたはシーケンスのブロックを要求する）。このような要求がない場合、当該ブロックは送信される必要がなく、当該帯域幅は他の目的に使用することが可能である。この結果、同時に使用される平均的なチャネル数は、ワーストケースのチャネル数である１１，０００よりはるかに小さくすることができる。従って、時点ｔにおいて要求が発生する場合、チャネルｉのサブチャネルｊは、時間単位ｔ＋ｓｉからｔ＋ｅｉｊまで、すなわち、時間単位ｘ（ｔ＋ｓｉ≦ｘ≦ｔ＋ｅｉｊ）においてアクティブとされるべきである。他方、時間単位ｘにおいて、サブチャネルｊの順番である場合、時点ｔ（ｘ−ｅｉｊ≦ｔ≦ｘ−ｓｉ）において要求があった場合、かつその場合に限りブロックが送信されなければならない。
【００４８】
ある時間単位において映画ｆに対しユーザが要求する確率は、ｐｆにより示される。ある時間単位において、チャネルｉのサブチャネルｊの順番である場合、ブロックを送信しなければならない確率は、異なる時間単位における要求が独立であると仮定すると、
【００４９】
【数１６】
2006509455.tif 000020
により与えられる。図５の例では、これは、それぞれ２時間単位と４時間単位の間隔で到着する確率に対応するｄ３＝２、ｎ３，０＝１及びｎ３，１＝２として、
【００５０】
【数１７】
2006509455.tif 000021
により与えられる。従って、映画ｆのチャネルｉが送信しなければならないブロックの期待される部分は、
【００５１】
【数１８】
2006509455.tif 000022
により与えられ、映画Ｆに対しブロックを送信しなければならないチャネルの期待合計数は、
【００５２】
【数１９】
2006509455.tif 000023
により与えられる。
【００５３】
パラメータλによるポワソン到着過程を仮定すると、ある時間単位での到着確率は、
【００５４】
【数２０】
2006509455.tif 000024
により与えられる。ここで、ｕは時間単位の長さである。図６は、対数スケールによる１時間あたりの１０ｘ（ｘは、横軸に示される）の受信機の異なる到着レートに対し、１つの映画に使用されるチャネルの期待チャネル数を縦軸に示す。
【００５５】
１０００本の映画を仮定し、そのうち３１、１１５、２００、２８５及び３６９本の映画はそれぞれ０．０１、０．０３１６、０．００１、０．００３１６及び０．０００１の選択確率を有し、６０００秒ごとに２００，０００の要求の到着レートを仮定すると、使用されるチャネルの合計チャネル数の期待値は、１１，０００と比較して約５，５３３となる。この到着レートが係数１０だけ減少すると、例えば、必ずしもすべてのユーザが映画を観るわけではないため、その数値はさらに２，８５８まで減少する。
【００５６】
理想的な状況では、使用される平均チャネル数に関して、ブロックｋの新たな送信が可能な限り遅くにスケジューリングされる。ここで、このスケジュールは使用される平均チャネル数の最小値を与えるが、使用チャネル数の最大値を限定するものでなく、実際の利用にはあまり適していない。従って、それは使用チャネル数の下限を導くためだけに使用される。このことは、新たな要求が時間単位ｔにおいて到達する場合、ブロックｋが時間単位ｔ＋ｏ＋ｋでの送信にスケジューリングされ、当該時間単位において、クロックｋは再生に必要とされる。このようにして、時間単位ｔ＋１，．．．，ｔ＋ｏ＋ｋ−１で到着するすべての要求は、このブロックｋの送信をタッピングすることができ、すなわち、ブロックｋの考慮された送信は、可能な限り多くの他の要求に再利用することができる。新たな要求が時間単位ｔ＋ｏ＋ｋまたは以降において到着したときのみ、ブロックｋの新たな送信がスケジューリングされる。ブロックｋが送信される時間の一部は、λのポワソン到着レートと長さｕの時間単位を再び仮定して決定される。このとき、前に導出したように、ある時間単位において要求が到着する確率は、
【００５７】
【数２１】
2006509455.tif 000025
となる。
【００５８】
上記手続きは、図７に示されるようなマルコフチェーンによりモデル化することができる。このチェーンでは、システムが新たな要求を待機しているとき、状態０が定義される。要求が到着すると、１からｏ＋ｋまでカウントが開始され、状態１，．．，ｏ＋ｋが導入される。システムが状態０にある場合、カウントは要求が到着するとき開始され、それは確率ｐで発生する。これが発生する場合、状態１に遷移され、そうでない場合には、システムは状態０に留まる。システムが状態ｓ＝１，．．．，ｏ＋ｋ−１にいる場合、カウントが継続され、次の状態は確率１で状態ｓ＋１となる。システムが最終状態ｏ＋ｋにいる場合、送信が行われる。これと同じ時間単位において、再び確率ｐで発生する新たな要求が到着すると、カウントが再開され、システムは状態１に再び移行する。そうでない場合、システムは待機状態０に移行する。
【００５９】
平衡状態でシステムが状態ｓにいる確率は、ｐｓにより表される。チェーンを参照して、状態１に到着するたび、状態２，．．．，ｏ＋ｋに到着することが観察でき、従って、
【００６０】
【数２２】
2006509455.tif 000026
が成り立つ。
【００６１】
次に、状態０への遷移と状態０からの遷移を検討すると、
【００６２】
【数２３】
2006509455.tif 000027
が与えられ、これにより、
【００６３】
【数２４】
2006509455.tif 000028
となる。
【００６４】
これらの確率の和は１でなければならないため、
【００６５】
【数２５】
2006509455.tif 000029
となり、これにより、
【００６６】
【数２６】
2006509455.tif 000030
が与えられる。
【００６７】
これは、ブロックｋが送信される時間の一部であり、映画がｎ個のブロックから構成される場合、平均使用チャネル数は、
【００６８】
【数２７】
2006509455.tif 000031
により与えられる。
【００６９】
極めて小さな時間単位のサイズｕを選択すると、最大待機時間をｗ、映画の長さをｌと仮定すると、
【００７０】
【数２８】
2006509455.tif 000032
及び
【００７１】
【数２９】
2006509455.tif 000033
が得られ、これより、
【００７２】
【数３０】
2006509455.tif 000034
により与えられる平均使用チャネル数が与えられる。
【００７３】
十分小さなｕに対して、これは、
【００７４】
【数３１】
2006509455.tif 000035
により近似することができる。
【００７５】
【数３２】
2006509455.tif 000036
であるため、これは、
【００７６】
【数３３】
2006509455.tif 000037
により書き換えることができる。
【００７７】
【数３４】
2006509455.tif 000038
である場合、これは、
【００７８】
【数３５】
2006509455.tif 000039
に収束する。
【００７９】
図８は、１時間あたり１０ｘ（ｘは、横軸に示される）クライアントの到着レートに対し、同じ最大反応時間ｗ＝０．９５と同じ映画の長さｌ＝６０００ｓのための平均使用チャネル数（縦軸）に対する下限を示す。
【００８０】
上記実施例では、送信スケジュールは、ブロックが送信されるかに関する決定が要求が起こったかどうかだけでなく、送信がスケジューリングされる（可能な限り遅くに）時間単位にも依存するという意味で、最大適応的である。他の実施例では、ブロックのスケジューリングは固定化され、ブロックが送信されるかどうかの決定のみがなされる。固定的な送信スケジュールに対し、ブロックｋは、ｏ＋ｋ時間単位ごとに最適に送信される。このとき時間単位ｔにおいて要求が発生すると、時間内に受信可能なブロックｋの送信が１回だけスケジューリングされる。次のものはｏ＋ｋ時間単位後であり、再生には遅延しすぎるため、ブロックｋの送信をスキップし、次のものまで待機することはできない。予めスケジューリングされた時間単位においてブロックｋが送信されるべきかは、
【００８１】
【数３６】
2006509455.tif 000040
の確率により発生する以前のｏ＋ｋ時間単位中に要求が発生するかどうかにのみ依存し、このため、平均使用チャネル数は、
【００８２】
【数３７】
2006509455.tif 000041
により与えられる。
【００８３】
再び、極めて小さな時間単位のサイズｕを選択し、ｗを最大待機時間、ｌを映画の長さと仮定すると、
【００８４】
【数３８】
2006509455.tif 000042
及び
【００８５】
【数３９】
2006509455.tif 000043
が得られ、これにより、平均数
【００８６】
【数４０】
2006509455.tif 000044
が与えられる。
【００８７】
十分小さなｕに対して、これは、
【００８８】
【数４１】
2006509455.tif 000045
により近似可能であり、
ｙ＝ｗ＋ｕｘを用いることにより、
【００８９】
【数４２】
2006509455.tif 000046
となる。
【００９０】
ここで、ｕへの依存性はこの式ではなくなっている。図９において、当該実施例により得られる結果が示される。この図は、１時間あたり１０ｘ（ｘは、横軸に示される）クライアントの到着レートに対し、同じ最大反応時間ｗ＝０．９５と同じ映画の長さｌ＝６０００ｓのための平均使用チャネル数（縦軸）に対する第２の下限を示す。
【００９１】
図１０は、図６、８及び９の平均使用チャネル数のグラフを合成したものである。１番上のラインは使用された選択的Ｐａｇｏｄａスキームに対応し、１番下のラインは完全適応型スキームにより与えられる下限に対応し、中間のラインは最適期間による選択的送信に対応する。図１１は、１番上のラインと下限との間の比と、中間のラインと下限との間の比とを示す。理解されるように、選択的Ｐａｇｏｄａスキームは、下限から３２％以内に常にある。これら２つのライン間の差は、より良いＮＶｏＤスケジュールを選択することにより得られるものを示す。第２ライン以下を得るためには、送信時点もまた適応的にならねばならない。
【００９２】
文献において、人気のない映画の帯域幅要求を低減させるためのいくつかの方法が提案されてきた。１つの方法としては、映画の後半部分に対してのみ配信を利用し、各ユーザの要求に応じて映画の第１（わずかな）部分を送信するというものである。この方法の短所は、人気のある映画が全配信アプローチより大きな帯域幅を要するということである。これを解決するため、映画の人気度を知っているべきであり、第１のオンデマンド部分と広範の配信部分との間の適切なバランスを選択すべきである。他の方法として、ブロック送信を動的にスケジューリングするというものがある。要求に応じて、どのブロックが入力され、欠落したブロックをスケジュールに動的に挿入する。この方法の短所は、発見的アプローチがブロックをスケジューリングするのに用いられ、最適なオフライン配信スキームより良好には実行されないというものである。本発明によるスケジュールの効果は、（漸近的）最適オフライン配信スキームが利用可能であり、ブロックが配信されるべきかどうかがオンラインにのみ判断される必要があるということである。このようにして、要求される帯域幅は、映画の人気度に自動的に適応化され、（近似的）最適解が人気度範囲全体に対して得られる。
【００９３】
ここで、上記実施例は本発明を限定するのでなく例示するものであり、当業者は添付された請求項の範囲から逸脱することなく他の多くの実施例を構成することができるであろう。請求項において、カッコ内の参照符号は、当該請求項を限定するものと解釈されるべきではない。「有する」という用語は、請求項列挙されたもの以外の他の要素またはステップの存在を排除するものでない。本発明は、複数の相異なる要素を有するハードウェアによって、そして適切にプログラムされたコンピュータによって実現することができる。複数の手段を列挙したシステムクレームでは、これらの手段の一部は、同一のハードウェアアイテムにより実現することができる。コンピュータプログラムプロダクツは、光記憶装置などの適切な媒体に格納/配布されてもよいが、配信システムのネットワーク、インターネットまたは無線通信システムを介し配布されるなど、他の形態により配布されてもよい。
【図面の簡単な説明】
【００９４】
【図１】図１は、本発明が利用可能な一例となる階層的配信ネットワークを示す。
【図２】図２は、本発明による配信システムのブロック図を示す。
【図３】図３は、ＰａｇｏｄａＮＶｏＤプロトコルを示す。
【図４】図４は、Ｐａｇｏｄａプロトコルによるチャネルの追加を示す。
【図５】図５は、受信機により実際に読み込まれるブロックを示す。
【図６】図６は、１つの映画に対する使用チャネル数の期待値を示す。
【図７】図７は、最小送信スキームの状態を説明するマルコフチェーンを示す。
【図８】図８は、映画に必要とされるチャネル数の期待値の下限を示す。
【図９】図９は、選択的送信と最適ブロック期間に基づく映画に必要とされるチャネル数の期待値の第２の下限を示す。
【図１０】図１０は、図６、８及び９のグラフを比較する。
【図１１】図１１は、２つの選択的送信スケジュールと下限との間の比を示す。
【図１】
2006509455.tif 000047
【図２】
2006509455.tif 000048
【図３】
2006509455.tif 000049
【図４】
2006509455.tif 000050
【図５】
2006509455.tif 000051
【図６】
2006509455.tif 000052
【図７】
2006509455.tif 000053
【図８】
2006509455.tif 000054
【図９】
2006509455.tif 000055
【図１０】
2006509455.tif 000056
【図１１】
2006509455.tif 000057
【国際調査報告】
2006509455.tif 000058
2006509455.tif 000059
2006509455.tif 000060