(57)【要約】配信システムでは、配信装置はニアビデオオンデマンド配信プロトコルを利用してタイトルを配信する。タイトルのデータブロックは、配信システムのｃ個の等しい容量のチャネルを介し配信される。配信チャネルは、時間逐次的にインタリーブ処理されたサブチャネルを有する。当該タイトルは、複数の連続するデータブロックシーケンスに分割される。各ブロックシーケンスは、各自の１つのサブチャネルに割当てられる。配信装置は、割当てられたサブチャネルの各ブロックシーケンスを繰り返し配信する。配信受信機は、ｒ個のチャネルのすべてのサブチャネルを同時に受信する容量を有する。受信機は、チャネルｉのサブチャネルの受信を終了し、チャネルｒ＋ｉの少なくとも１つのサブチャネルの受信を開始する。
2006509454.tif 000002
【特許請求の範囲】
【請求項１】
複数の配信受信機と配信装置とを有し、ニアビデオオンデマンド配信プロトコルを利用して前記複数の配信受信機にタイトルを配信する配信システムであって、
前記配信装置は、該配信システムのｃ個のパラレルな等しい容量のチャネルを介しタイトルのデータブロックを配信するよう動作し、各配信チャネルは各自の逐次的なチャネル番号に関連付けされ、前記複数の配信チャネルは複数の時間逐次的にインタリーブ処理されたサブチャネルを有し、１つのチャネルのサブチャネル数は前記チャネル番号に関し単調非減少であり、前記サブチャネルは各自の逐次的なサブチャネル番号と関連付けされ、前記タイトルは複数の連続するデータブロックシーケンスに分割され、各ブロックシーケンスは前記チャネル番号とサブチャネル番号に従って各自１つのサブチャネルに割当てられ、前記配信装置は前記割当てられたサブチャネルの各ブロックシーケンスを繰り返し配信するよう動作し、
前記配信受信機は、前記チャネルのｒ（１＜ｒ≦ｃ）個のチャネルのすべてのサブチャネルを同時に受信する容量を有し、逐次的に最下位からｒ個のチャネルのすべてのサブチャネルの受信を開始することによりタイトルを受信するよう動作し、チャネルｉのサブチャネルのブロックシーケンスのすべてのブロックを受信したことに応答するごとに、チャネルｉの前記サブチャネルの受信を終了し、すべてのブロックシーケンスが受信されるまで、チャネルｒ＋ｉの少なくとも１つのサブチャネルの受信を開始することを特徴とするシステム。
【請求項２】
請求項１記載の配信システムであって、
前記配信装置は、等しい期間のタイムスロットを同時に用いて前記パラレルなチャネルに割当てられたデータブロックを配信するよう動作し、チャネルｉの各サブチャネルは、チャネルｉの関連付けされたサブチャネルを配信するのに利用されるタイムスロット中にのみ配信されるブロックを有するチャネルｒ＋ｉの少なくとも１つのサブチャネルと関連付けされ、前記配信受信機は、チャネルｉのサブチャネルのブロックシーケンスのすべてのブロックを受信したことに応答して、チャネルｒ＋ｉ（ｉ≧１）の関連付けされたサブチャネルの受信を開始するよう動作することを特徴とするシステム。
【請求項３】
請求項１記載の配信システムであって、
チャネルｉ＋ｒは、チャネルｉのサブチャネル数のサブチャネルの乗数Ｍｉを有し、チャネルｉの各サブチャネルは、チャネルｉの関連付けされたサブチャネルを配信するのに使用されるタイムスロット中にのみ配信されるブロックを有するチャネルｒ＋ｉのＭｉ個のサブチャネルと関連付けされ、前記配信受信機は、チャネルｉのサブチャネルのブロックシーケンスのすべてのブロックを受信したことに応答して、前記チャネルｒ＋ｉ（ｉ≧１）の関連付けされたＭｉ個のサブチャネルの受信を開始することを特徴とするシステム。
【請求項４】
請求項１記載の配信システムであって、
前記ニアビデオオンデマンドプロトコルは、固定遅延Ｐａｇｏｄａ配信プロトコルであることを特徴とするシステム。
【請求項５】
請求項１記載の配信システムにおいて使用される配信受信機であって、
配信装置は、前記配信システムのｃ個のパラレルな等しい容量のチャネルを介しタイトルのデータブロックを配信するためニアビデオオンデマンド配信プロトコルを利用し、各配信チャネルは各自の逐次的なチャネル番号に関連付けされ、前記複数の配信チャネルは複数の時間逐次的にインタリーブ処理されたサブチャネルを有し、１つのチャネルのサブチャネル数は前記チャネル番号に関し単調非減少であり、前記サブチャネルは各自の逐次的なサブチャネル番号と関連付けされ、前記タイトルは複数の連続するデータブロックシーケンスに分割され、各ブロックシーケンスは前記チャネル番号とサブチャネル番号に従って各自１つのサブチャネルに割当てられ、前記配信装置は前記割当てられたサブチャネルの各ブロックシーケンスを繰り返し配信するよう動作し、
該配信受信機は、前記チャネルのｒ（１＜ｒ≦ｃ）個のチャネルのすべてのサブチャネルを同時に受信する容量を有し、逐次的に最下位からｒ個のチャネルのすべてのサブチャネルの受信を開始することによりタイトルを受信するよう動作し、チャネルｉのサブチャネルのブロックシーケンスのすべてのブロックを受信したことに応答するごとに、チャネルｉの前記サブチャネルの受信を終了し、すべてのブロックシーケンスが受信されるまで、チャネルｒ＋ｉの少なくとも１つのサブチャネルの受信を開始することを特徴とする配信受信機。
【請求項６】
請求項１記載の配信システムにおいて使用される配信受信機において配信データを受信する方法であって、
配信装置は、前記配信システムのｃ個のパラレルな等しい容量のチャネルを介しタイトルのデータブロックを配信するためニアビデオオンデマンド配信プロトコルを利用し、各配信チャネルは各自の逐次的なチャネル番号に関連付けされ、前記複数の配信チャネルは複数の時間逐次的にインタリーブ処理されたサブチャネルを有し、１つのチャネルのサブチャネル数は前記チャネル番号に関し単調非減少であり、前記サブチャネルは各自の逐次的なサブチャネル番号と関連付けされ、前記タイトルは複数の連続するデータブロックシーケンスに分割され、各ブロックシーケンスは前記チャネル番号とサブチャネル番号に従って各自１つのサブチャネルに割当てられ、前記配信装置は前記割当てられたサブチャネルの各ブロックシーケンスを繰り返し配信するよう動作し、
前記配信受信機は、前記チャネルのｒ（１＜ｒ≦ｃ）個のチャネルのすべてのサブチャネルを同時に受信する容量を有し、
該方法は、
逐次的に最下位からｒ個のチャネルのすべてのサブチャネルの受信を開始するステップと、
チャネルｉのサブチャネルのブロックシーケンスのすべてのブロックを受信したことに応答するごとに、チャネルｉの前記サブチャネルの受信を終了し、すべてのブロックシーケンスが受信されるまで、チャネルｒ＋ｉの少なくとも１つのサブチャネルの受信を開始するステップと、
を実行することによってタイトルを受信することを特徴とする方法。
【請求項７】
請求項６記載のステップをプロセッサに実行させるよう動作することを特徴とするコンピュータプログラムプロダクツ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信システムを介し複数の配信受信機にデータストリームを配信する配信システムに関する。本発明はさらに、当該システムに使用される配信受信機に関する。本発明はまた、配信タイトルを受信する方法に関する。
【背景技術】
【０００２】
ケーブルネットワーク、地上波放送ネットワークあるいは衛星ネットワークなどの従来のデジタル放送システムは、１秒あたり１ギガビットのオーダによるダウンストリーム（すなわち、中央配信装置から配信受信機への方向）の容量を有する。この容量の一部は、最も普及したテレビ局などの従来の放送チャネルに用意されている。このようなチャネルは、実際の受信は支払いに応じた限定的なものではあるが、原則的にはすべての受信機により受信可能である（すなわち、すべての同軸ケーブルを介し送信される）。帯域幅の一部は、ネットワークを介した配信受信機からネットワーク外部の対象となる主体へのアップストリーム通信に用意されてもよい。通常、このアップストリーム通信は、ブロードバンドケーブルモデムを利用したインターネットに向かうものである。それはまた、対話的アプリケーションのサービス提供者へのものであってもよい。残りの帯域幅により、タイトルの受信を所望していることをユーザが示した直後に、供給が実質的に開始される効果的なビデオオンデマンドサービスを提供することは、実現不可能ではないが、困難である。これを解消するため、複数の配信チャネルのグループを用いて１つのタイトルが繰り返し配信されるいわゆるニアビデオオンデマンド（ｎｅａｒ−ｖｉｄｅｏ−ｏｎ−ｄｅｍａｎｄ）放送配信プロトコルが開発された。効果的なプロトコルとして、Ｊ．Ｆ．Ｐａｒｉｓの「Ａ  ｆｉｘｅｄ−ｄｅｌａｙ  ｂｒｏａｄｃａｓｔｉｎｇ  ｐｒｏｔｏｃｏｌ  ｆｏｒ  ｖｉｄｅｏ−ｏｎ−ｄｅｍａｎｄ」（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １０ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ｎｅｔｗｏｒｋｓ，ｐａｇｅ４１８−４２３）に開示されるＰａｇｏｄａ配信プロトコルがあげられる。このプロトコルでは、配信システムのｃ本のパラレル配信チャネルを利用して、１つのタイトルが繰り返し配信される。これらのチャネルは、同じ送信容量を有する。第１チャネルは、当該タイトルの第１ブロックのみを繰り返し送信するのに使用される。このようにして、受信機は、当該タイトルの第１ブロックを比較的迅速に受信することができる。以降のチャネルは、当該タイトルの他の以降のブロックを送信するため使用される。各チャネルは、同じシーケンスからのブロックを繰り返し配信する。１つのチャネルに割当てられる異なるブロックの個数は、チャネル数と共に増加する。受信したタイトルの連続再生のため、配信受信機は典型的にはｒ＝２であるｒ個のチャネルに同時にタップ処理（受信）を行う必要がある（１＜ｒ≦ｃ）。配信受信機は、小さなものからｒ個のチャネルをタッピングすることにより開始される。タイトルの再生は、第１ブロックが受信されるとすぐに開始することができる。当該システムがオフセットにより利用されると、受信機は再生を開始する前にオフセットにより指定された追加的時間だけ待機する必要がある。受信機がチャネルｉに割当てられたブロックシーケンスのすべてのブロックを受信するたび、チャネルｉの受信を終了し、当該タイトルのすべてのブロックが受信されるまで、チャネルｒ＋ｉの受信を開始する。受信機は、同時に複数のブロックシーケンスを受信するため、一部のブロックを一時的にバッファリングし、再生時にはそれらを再順序付けする必要がある。チャネルにおいてブロックが送信される順序を最適化するため、チャネルは同じ容量のサブチャネルに分割される。オフセットが利用されない場合、第１及び第２チャネルは１つのみのサブチャネルを有するものとみなすことができる。１つのチャネルにおけるサブチャネル数は、前のチャネルのサブチャネル数以上となる。チャネルは、チャネルのサブチャネルを時間逐次的にインタリーブすることにより構成される。タイトルは、連続するブロックシーケンスに分割される。各シーケンスは、チャネル数及びチャネル内のサブチャネル数に従って各サブチャネルに割当てられる。典型的には、当該シーケンスのブロック数は、チャネル数とサブチャネル数と共に増加する。
【０００３】
Ｐａｇｏｄａシステムの実現のため、チャネル数ｃは、妥当なタイトル数を同時に配信することが可能となるように比較的少なく維持する必要がある（例えば、ｃ＝１１）。配信受信機のコストを低く維持するため、同時に受信可能なチャネル数（従って、バッファサイズ）は、比較的低く維持する必要がある（例えば、ｒ＝２）。Ｐａｇｏｄａ配信プロトコルによると、これにより比較的大きなブロックサイズとなる。これは、システムの反応時間（すなわち、ユーザがタイトルを視聴する指示を与えてからタイトルの再生が実際に開始されるまでの時間）に関して悪影響を及ぼす。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の課題は、良好な反応時間を提供するＰａｇｏｄａタイプの配信プロトコルを利用したニアビデオオンデマンドシステムを提供することである。
【課題を解決するための手段】
【０００５】
本発明の課題を解決するため、複数の配信受信機にタイトルを配信する配信システムは、タイトルのデータブロックが配信システムのｃ個のパラレルな等しい容量のチャネルを介し配信されるニアオンビデオデマンド配信プロトコルを利用し、各配信チャネルは各自の逐次的なチャネル番号に関連付けされ、前記複数の配信チャネルは複数の時間逐次的にインタリーブ処理されたサブチャネルを有し、１つのチャネルのサブチャネル数は前記チャネル番号に関し単調非減少であり、前記サブチャネルは各自の逐次的なサブチャネル番号と関連付けされ、前記タイトルは複数の連続するデータブロックシーケンスに分割され、各ブロックシーケンスは前記チャネル番号とサブチャネル番号に従って各自１つのサブチャネルに割当てられ、前記配信装置は前記割当てられたサブチャネルの各ブロックシーケンスを繰り返し配信するよう動作し、前記配信受信機は、前記チャネルのｒ（１＜ｒ≦ｃ）個のチャネルのすべてのサブチャネルを同時に受信する容量を有し、前記ｒ個のチャネルのすべてのサブチャネルの受信を開始することによりタイトルを受信するよう動作し、チャネルｉのサブチャネルのブロックシーケンスのすべてのブロックを受信したことに応答するごとに、チャネルｉの前記サブチャネルの受信を終了し、すべてのブロックシーケンスが受信されるまで、チャネルｒ＋ｉの少なくとも１つのサブチャネルの受信を開始することを特徴とする。
【０００６】
本発明者は、従来のＰａｇｏｄａスケジュールでは、配信受信機の受付容量が無駄にされていると認識していた。チャネルのすべてのサブチャネルのすべてのブロックが一度に受信されるまで、チャネルはタップ処理される。特に、サブチャネルの長さが増加傾向にあるため、チャネルの最下位サブチャネルのすべてのブロックが、当該チャネルの最上位サブチャネルの最後のブロックが受信される前に、通常は良好に受信される。すべてのサブチャネルは繰り返し送信及びインタリーブ処理されるため、このことは、最下位サブチャネルが受信された後、一部のタイムスロットはもはや新しいデータブロックを含まないということを意味する。既知のシステムでは、チャネルの時間多重化データストリームは、最後のブロックが一度に受信されるまで完全に受信される。本発明によるシステムでは、チャネルｉのサブチャネルのすべてのブロックが受信されるとすぐ、受信機によりチャネルｉ＋ｒの少なくとも１つのサブチャネルのタップ処理が開始される。ここで、チャネルｉのすべてのサブチャネルが受信されない限り、受信機は依然としてチャネルｉのタップ処理を行う。チャネルｉのすでに受信されたサブチャネルのブロックを送信するのに利用されるタイムスロット期間中、受信機は、チャネルｉ＋ｒのサブチャネルのブロックを受信する。従って、受信機は、ｒ個より多くのチャネルのブロックを受信及び格納するという意味で、ｒ個のより多くのチャネルをタップ処理する。しかしながら、任意の時点において、受信機はｒ個のチャネルのブロックのみを受信する。このようにして、受付容量はより良く利用される。ブロックサイズと配信スケジュールが、ｒ個のチャネルのすべてのサブチャネルをタップ処理することにより、再生バッファのアンダーフロー（ｕｎｄｅｒｆｌｏｗ）が発生しないように選択されるため、効果的に増やされた受付容量は、ブロックサイズを減少させることを可能に時間の短縮化を可能にする。ｒ＝２、ｃ＝１１の具体的システムでは、反応時間はほとんど１/２にすることができる。
【０００７】
従属クレーム２の手段によって示されるように、パラレルチャネルに割当てられたデータブロックは、等しい期間のタイムスロットを使用して同時に配信され、チャネルｉの各サブチャネルは、チャネルｉの関連付けされたサブチャネルを配信するのに利用されるタイムスロット中にのみ配信されるブロックを有するチャネルｒ＋ｉの少なくとも１つのサブチャネルと関連付けされ、前記配信受信機は、チャネルｉのサブチャネルのブロックシーケンスのすべてのブロックを受信したことに応答して、チャネルｒ＋ｉ（ｉ≧１）の関連付けされたサブチャネルの受信を開始するよう動作する。チャネルｉのサブチャネル（好ましくは、各サブチャネル）に対して、同じタイムスロットを使用するチャネルｉ＋ｒのサブチャネルが存在する（すなわち、同じフェーズを用いて送信され）ということを保証し、これらのチャネルを関連付けすることにより、チャネルｉのサブチャネルのすべてのブロックが受信されるとすぐに、チャネルｉ＋ｒの関連付けされたサブチャネルの受信を開始することができる。
【０００８】
従属クレーム３の手段により示されるように、チャネルｉ＋ｒは、チャネルｉのサブチャネル数のサブチャネルの乗数Ｍｉを有し、チャネルｉの各サブチャネルは、チャネルｉの関連付けされたサブチャネルを配信するのに使用されるタイムスロット中にのみ配信されるブロックを有するチャネルｒ＋ｉのＭｉ個のサブチャネルと関連付けされ、前記配信受信機は、チャネルｉのサブチャネルのブロックシーケンスのすべてのブロックを受信したことに応答して、前記チャネルｒ＋ｉ（ｉ≧１）の関連付けされたＭｉ個のサブチャネルの受信を開始する。チャネルｉ＋ｒをチャネルｉのサブチャネル数の倍数Ｍｉであるいくつかのサブチャネルに分割することにより、チャネルｉのサブチャネルが完全に受信されるたびに、チャネルｉ＋ｒのＭｉ個のサブチャネルの受信を開始することができる。このようにして、受付容量をフルに活用することができる。
【０００９】
本発明の上記及び他の特徴は、以降に差説明される実施例を参照することにより明らかとなるであろう。
【発明を実施するための最良の形態】
【００１０】
図２は、本発明によるニアビデオオンデマンド（ＮＶｏＤ）プロトコルが利用される配信システムのブロック図を示す。一例となる配信システム１００は、データ配信装置の階層的ネットワークを有する。当該ネットワークのトップは、中央配信装置１１０により形成される。本システムは、少なくとも１つの中間配信装置のレイヤを含む。図面を簡単化するため、各々が分離した地理的エリアをカバーする３つの中間配信装置１２０、１３０及び１４０を有するダウンストリーム配信のための中間レイヤのみが示される。図１は、４つの中間ダウンストリームレイヤ（メトロヘッドエンド、ハブ、ファイバノード、同軸ヘッドエンド）による接続された２００，０００世帯の町に対する典型的な階層的ネットワークを示す。図２はまた、中央配信装置１１０から始まり、中間配信装置１２０、１３０及び１４０を介し行われ、システムの複数の配信受信機において終わるダウンストリームパス１６０を示す。従来、配信装置は階層的に１段低いレイヤ上の受信機/配信装置に配信信号を分割する。典型的には、当該パスは複数のチャネルに分割され、各チャネルはサブチャネルに分割されてもよい。最下位レベルでは、通常は配信受信機に共有される媒体を構成する同軸部分が利用される。同軸上では、チャネルは通常は周波数多重化されている。当該チャネル内のサブチャネルは、時間多重化されてもよい。より上位のレベルでは、典型的には、光ファイバが利用される。このような媒体では、チャネルはまた時間多重化されてもよい。各種メディア及び多重化技術などの任意の適切な送信技術が利用されてもよい。ネットワークを介し複数の配信受信機にデジタルデータストリームを配信するための配信システムが説明される。データストリームは、ＭＰＥＧ２映像符号化などの任意の適切な技術を用いて符号化されていてもよい。配信データは特定の受信機にアドレス指定されるのでなく、原則的には階層的ネットワークのすべての部分における受信機全体に受信可能とされる。データへのアクセスは、支払いによるものであってもよい。本発明による配信システムでは、適切な限定受信機構を用いてアクセスが制御されてもよい。システムの各装置に対して、図２は、配信データの送受信及びすべての必要な処理の実行に必要とされるハードウェア/ソフトウェア機能１１２、１２２、１３２、１４２及び１５２を概略的に示す。このようなハードウェア/ソフトウェアは既知であり、本発明によるシステムに利用可能である。ハードウェア/ソフトウェアは、信号プロセッサなどの適切なプロセッサを利用することにより制御される適切な送受信機（光ファイバ受信機及び/またはケーブルモデムなど）により構成されてもよい。また、ＭＰＥＧエンコーダ/デコーダ、バッファなどの専用ハードウェアが利用されてもよい。
【００１１】
典型的には、すべてのデータストリームが中央配信装置１１０により挿入され、各中間レイヤによりネットワークの最下位部分に無修正でコピーされる。このため、中央配信装置は、映画などの複数のタイトルを格納するストレージ１１５を有するようにしてもよい。中央配信装置はまた、衛星接続などを介しライブの配信を受信する接続１６０を有するようにしてもよい。ストレージ１１５は、ＲＡＩＤシステムなどに基づき適切なサーバプラットフォーム上で実現されてもよい。受信機はまた、ストレージ１５５にアクセスする。このストレージはまた、フラッシュメモリのＲＡＭなどのソリッドステートメモリまたはハードディスクにより構成されるようにしてもよい。このストレージは、タイトル再生前にダウンストリームチャネルを介し受信されるタイトル全体または一部を（一時的または永久的に）格納するのに利用される。図２はまた、中央配信装置へのネットワークのアップストリームチャネルを示す。原則的には、アップストリームチャネルは、中間レベルが上位に移行することから開始するようにしてもよい。好ましくは、アップストリームチャネルは、既に最下位レベルにあり、配信システムの外部との通信を可能にする（例えば、中央配信装置または中間配信装置を介しインターネットに対して）。図１及び２に示されるような多層階層的ネットワークを利用する代わりに、データが中央配信装置から受信機に直接配信されるネットワークが利用されてもよい。有線接続を使用する代わりに、例えば、衛星放送、デジタル地上波放送あるいは高帯域幅通信ネットワークを利用するなどにより、無線接続が利用されてもよいということも理解されるであろう。
【００１２】
本発明によるＮＶｏＤプロトコルが、Ｐａｇｏｄａ配信プロトコルを参照することにより説明される。このため、まず後者のプロトコルがより詳細に説明される。
［固定遅延Ｐａｇｏｄａ配信］
好ましくは、タイトルのデータブロックを配信するためのニアビデオオンデマンドプロトコルとして、固定遅延Ｐａｇｏｄａ配信プロトコルが利用される。このプロトコルは、漸近的に最適であり、限定的なクライアントＩ/Ｏ帯域幅に容易に適応可能である。図３Ａにおいて、これの小さな例が与えられる。図３Ｂは、任意の時点における要求に対し抽出がどのように実行されるか示す。図３の例では、高々２つのチャネルが同時にタップ処理され、すべてのブロックが時間内に到着する。このＮＶｏＤスキームのキーは、チャネルｉがチャネルｉ−２のタッピングが完了した後にタップ処理を開始されるというものであり、これにより、タップ処理されるチャネル数を２に限定することができる。このことは、例えば、チャネル４に対して、受信機は当該チャネルのタップ処理が開始可能となる前に、２時間単位だけ待機する必要があるということを意味するものである。ブロック７は要求後に７時間単位以内で受信される必要があるため、これは、５時間単位のみが受信するのに残され、これにより７でなく高々５期間で送信される必要があるということを意味するものである。実際、それは４期間で送信される。上記配信スキームの一般的構成が、受信可能な所定数ｒのクライアントチャネルと所定数ｃのサーバチャネルに対して説明される。さらに、オフセットｏは、説明されるように、再生前にユーザが追加的ｏ時間単位だけ常に待機するということを意味すると考えられる。チャネルｉの（タップ処理）のセグメントの始まりはｓｉにより表され、終わりはｅｉにより表される。このとき、ユーザが受信可能な最大チャネル数ｒを超えないように、チャネルｉ＝ｒ＋Ｉ，．．．，ｃにおけるタップ処理は、チャネルｉ−ｒのタップ処理が終了した後に開始される。従って、
【００１３】
【数１】
2006509454.tif 000003
次に、チャネルｉにおいて、ブロックｌｉ，．．．，ｈｉが送信される。従って、チャネルｉで送信される相異なるブロック数は、
ｎｉ＝ｈｉ−ｌｉ＋１により与えられる。ただし、
【００１４】
【数２】
2006509454.tif 000004
である。
【００１５】
時間内に各ブロックを受信するため、ブロックｋは、時間単位ｏ＋ｋにおいて、またはそれ以前に送信されるべきである。ブロックｋが時間単位ｓｉで受信を開始するチャネルｉで送信される場合、これは、ブロックｋが高々ｏ＋ｋ−（ｓｉ―１）の期間で配信されるべきであるということを意味する。理想的には、当該期間は各ブロックｋに対し正確に満たされるが、十分近接させるには十分である。
【００１６】
Ｐａｇｏｄａスキームによるチャネルｉの構成は以下のようなものである。まず、チャネルｉは、
【００１７】
【数３】
2006509454.tif 000005
によって、すなわち、最も近い整数に丸められたブロックｌｉの最適期間の平方根によって与えられるｄｉ個のサブチャネルに分割される。各サブチャネルは、ラウンドロビン方式によりブロックを送信するための時間単位の一部１/ｄｉを取得する。言い換えると、時間単位ｔにおいて、サブチャネルｔ  ｍｏｄ  ｄｉは１つのブロックを送信することが可能であり、サブチャネルは０，１，．．．，ｄｉ−１に番号付けされる。
【００１８】
ここで、ブロックｋにチャネルｉのサブチャネル内において期間ｐｋが与えられると、ブロックｋはｐｋｄｉの期間によりチャネルｉにおいて配信される。従って、
ｐｋｄｉ≦ｏ＋ｋ−（ｓｉ―１）
とするため、
【００１９】
【数４】
2006509454.tif 000006
となることを意味する。
【００２０】
各サブチャネル内のすべてのブロックに対して等しい期間をとることにより、衝突を回避することができる。従って、ｌｉｊがチャネルｉのサブチャネルｊにおける最小ブロック番号である場合、これは、チャネルｉのサブチャネルｊ内のすべてのブロックに対して、以下の期間が選ばれることを意味する。
【００２１】
【数５】
2006509454.tif 000007
従って、当該サブチャネルにおいてｎｉｊ＝ｐｉｊ個のブロック（ブロックｌｉｊ，．．．，ｌｉｊ＋ｎｉｊ−１）を送信することが可能となる。ブロック番号ｌｉｊは、
【００２２】
【数６】
2006509454.tif 000008
により与えられる。
【００２３】
チャネルｉで送信されるブロックの総数ｎｉは、
【００２４】
【数７】
2006509454.tif 000009
により与えられ、これにより、
ｈｉ＝ｌｉ＋ｎｉ−１
を計算することができる。
【００２５】
最終的に、あるチャネル内のセグメントのスタート及びエンド時点が参照される。チャネルｉのすべてのサブチャネルは、時点ｓｉにおいて送信を開始する。チャネルｉのサブチャネルｊは、ｎｉｊブロックの後に準備され、チャネルｉ内でｄｉｎｉｊ時間単位を要する。従って、サブチャネルｊの当該セグメントのエンドは、
ｅｉｊ＝ｓｉ−１＋ｄｉｎｉｊにより与えられ、それの最後のサブチャネルが、
【００２６】
【数８】
2006509454.tif 000010
において終了するとき、チャネルｉは終了する。
【００２７】
上記を例示するため、図４は、図３の例に第５チャネルを追加することを示す。第５チャネルに対して、以下の式が成り立つ。すなわち、ｌ５＝１２，ｓ５＝ｅ３＋１＝６及びオフセットｏ＝０である。サブチャネル数は、
【００２８】
【数９】
2006509454.tif 000011
である。サブチャネルｊ＝０に対し、これはｌ５，０＝１２を与え、これにより当該サブチャネルにおいてブロック１２と１３である
【００２９】
【数１０】
2006509454.tif 000012
個のブロックを送信することが可能である。サブチャネルｊ＝１に対し、これはｌ５，１＝１４を与え、これにより当該サブチャネルにおいてブロック１４、１５及び１６である
【００３０】
【数１１】
2006509454.tif 000013
個のブロックを送信することが可能となる。サブチャネルｊ＝２に対し、これはｌ５，２＝１７を与え、これにより当該サブチャネルにおいてブロック１７、１８、１９及び２０である
【００３１】
【数１２】
2006509454.tif 000014
個のブロックを送信することが可能となる。当該サブチャネルのセグメントのエンドは、
ｅ５，０＝５＋３＊２＝１１、
ｅ５，１＝５＋３＊３＝１４及び
ｅ５，２＝５＋３＊４＝１７
により与えられ、これによりｅ５＝１７となる。
【００３２】
ｈｉの値、すなわち、映画が分割可能であるブロック数は、オフセットゼロとｒの各値に対してテーブル１により与えられる。当該系列は、ｒ＝２，３，４及び∞のそれぞれに対し、約１．７５，２．４２，２．６２及び
【００３３】
【数１３】
2006509454.tif 000015
をベースとするべき級数に収束する。
【００３４】
【表１】
2006509454.tif 000016
最後の列は、クライアントチャネル数が無制限であることに対応する。ｈｃの上記値を用いて、最大待機時間は、ｃ個のチャネルを使用するとき、映画の長さの一部１/ｈｃにより与えられる。正のオフセットｏが用いられる場合、最大待機時間の一般的な式は、映画の長さの一部（ｏ＋１）/ｈｃとなる。
【００３５】
以前のセクションでは、チャネルｉのサブチャネルの個数ｄｉは一定とされ、式（１）により与えられる。ここで、映画が分割可能となるブロック数に関してより良い解を得るために、異なる値が用いられるようにしてもよい。このため、チャネルｉごとに式（１）で与えられる目標値近傍のいくつかの異なる値を求め、チャネルｉに適合可能なブロック数を計算し、チャネルｉが最大となるブロック数を有することが可能なサブチャネル数をとることにより、１次最適化が適用可能である。ここで、当該処理は、直接的な実現により指数的な実行時間がかかることを回避するため、個々のチャネルごとに実行される。すなわち、以前のチャネルへのバックトラッキングは発生しない。これは、チャネルｉにおいてより多くのブロックを取得するためチャネルｉにおいて異なる個数のサブチャネルを選択することが、エンド時間ｅｉを増加させ、これによりチャネルｉ＋ｒのスタート時間ｓｉ＋ｒを増加させ、当該チャネルに適合可能なブロック数を減少させるとき、次善解を導くかもしれない。にもかかわらず、この１次最適化は、テーブル２に示されるような良好な結果を与える。オフセットゼロとｒの異なる値に対して、ｈｉの新たな値が与えられる。これらの値は前のテーブルのものより大きいが、べき級数のベースはテーブル１のものと同一である。
【００３６】
【表２】
2006509454.tif 000017
以下では、従来のＰａｇｏｄａプロトコルに対するテーブル１の値が用いられる。
【００３７】
これまでの説明では、タイトルは一定のビットレート（ＣＢＲ）を有すると仮定されていた。しかしながら、この送信スキームは、可変ビットレート（ＶＢＲ）ストリームに対処するよう容易に適応化可能である。ブロックｋが到達しなければならない時点は、ＣＢＲストリームではｏ＋ｋにより与えられ、このとき関数ｏ＋ｔ（ｋ）により与えられる。ここで、ｔ（ｋ）は、当該ストリームが時間内に再生される方法を説明する増加関数である。送信スキームに対する効果は以下の通りである。ブロックｋが時点ｓｉにおいて開始されるチャネルｉにおいて送信される場合、ブロックｋは高々ｏ＋ｔ（ｋ）−（ｓｉ―１）の期間により配信される必要がある。従って、式（１）で与えられるようなサブチャネル数の目標値は、
【００３８】
【数１４】
2006509454.tif 000018
となる。
【００３９】
このとき、チャネルｉのサブチャネルｊにおけるブロック数、すなわち、当該サブチャネル内で用いられる期間は、
【００４０】
【数１５】
2006509454.tif 000019
により与えられる。残りの計算は同様である。
［本発明によるサブチャネルタッピング］
既知のＰａｇｏｄａ配信スキームでは、チャネルｉ−ｒが終了すると、すなわち、チャネルｉ−ｒのすべてのサブチャネルが終了すると、チャネルｉ（ｉ＞ｒ）が開始される。これの問題点は、図５に示されるように、受付容量が常にフル活用されているとは限らないということである。図５において、チャネル３のサブチャネル０は２時間単位のみしかかからないが、チャネル５はチャネル３が開始してから４時間単位で開始される。この結果、チャネル３のサブチャネル０の終了直後のタイムスロットでは１つのブロックしか受信されず（ブロック４は既に受信済みであるため）、このため受付容量はフルには利用されない。本発明による改善されたスキームは、図６に示されるように、チャネル３のサブチャネル０が終了したときにはチャネル５の一部のサブチャネルを既に開始し、チャネル３のサブチャネル１が終了したときにはチャネル５の残りのサブチャネルを開始することにより得られる。この小さな例では、ブロックの総数（従って、待機時間）に対する影響はないが、より大きなスキームに対する影響は、テーブル３から明らかとなるように有意なものとなるであろう。
【００４１】
好適な一実施例では、チャネルｉ（ｉ＞ｒ）のサブチャネル数は、チャネルｉ−ｒのサブチャネル数の整数倍Ｍｉ−ｒとされる。このため、サブチャネル数は、オリジナルのＰａｇｏｄａシステムと比較して変更される必要があるかもしれない。図６の例では、３つの代わりに、４つのサブチャネルがチャネル５に対して用いられる。乗数Ｍｉを用いることにより、チャネルｉ＋ｒのＭｉ個のサブチャネルはチャネルｉの１つのサブチャネルと同一容量を有するということから（等しい容量を有するチャネル）、チャネルｉのサブチャネルのエンドに到達することに応答して、チャネルｉ＋ｒのＭｉ個のサブチャネルを開始することが可能となる。このようにして、受付容量全体がフルに利用されることが可能となる。
【００４２】
好適な一実施例では、チャネルｉ−ｒのその他のサブチャネルにおいて送信されるブロックと競合しないように、チャネルｉ−ｒのサブチャネルの終了後にチャネルｉの新たに開始されたサブチャネルが同一の時間単位（タイムスロット）に属するようなプロトコルが利用される。図６の例では、このことは、チャネル５のサブチャネル０と１がチャネル３のサブチャネル０に割当てられるものと同一の時間単位を使用する必要があるということを意味する。後者の時間単位は偶数時間単位、すなわち、ｘ  ｍｏｄ  ２＝０となる時間単位ｘであり、このため、ｘ  ｍｏｄ  ４＝０となる時間単位ｘはチャネル５のサブチャネル０に割当てられ、ｘ  ｍｏｄ  ４＝２の時間単位ｘはチャネル５のサブチャネル１に割当てられる。このようにして、タップ処理されるチャネル数は、同時にｒを超えることはない。より形式的には、チャネルｉの各サブチャネルｊ＝０，．．．，ｄｉ―１に対して、フェージング
【００４３】
【数１６】
2006509454.tif 000020
が導入される。チャネルｉ＝１，．．．，ｒに対して、チャネル数ｄｉは、追加的な制限なく式（１）の目標値の近傍から選ぶことができる。チャネルｉのサブチャネルのフェージングは、
φｉｊ＝ｊ
により単に割当てられる。
【００４４】
チャネルｉ＝１，．．．，ｒのサブチャネルｊのスタート時間は、もとのＰａｇｏｄａＮＶｏＤスケジュールと同一であり、すなわち、
ｓｉｊ＝ｓｉ＝１
であり、サブチャネルごとのブロック数は、もとの方法により計算される。
【００４５】
チャネルｉ＞ｒに対し、チャネル数ｄｉは、式（１）の目標値の近傍から選ぶことが可能であるが、好ましくはｄｉ−ｒの倍数であるという追加的な制限が加えられる。次に、時間単位ｅｉ−ｊ、ｊ’で発生するチャネルｉ−ｒのサブチャネルｊ’が終了するたび、すべてがスタート時間が
ｓｉｊ＝ｅｉ−ｊ、ｊ’＋１
となるチャネルｉのＭｉ−ｒ＝ｄｉ/ｄｉ−ｒ個の新たなサブチャネル（ｊ＝ｊ’Ｍｉ−ｒ，．．．，（ｊ’＋１）Ｍｉ−ｒ−１）が開始される。
【００４６】
これら新たなサブチャネルのフェージングは、ｊ＝ｊ’Ｍｉ−ｒ＋ｋ（ｋ＝０，．．．，Ｍｉ−ｒ−１）に対し、
φｉｊ＝φｉ−ｒ、ｊ’＋ｋｄｉ−ｒ
により与えられる。これにより、これら新たなサブチャネルは、
φｉｊ  ｍｏｄ  ｄｉ−ｒ＝φｉ−ｒ，ｊ’
として、終了したサブチャネルと同じ時間単位に属するということが与えられる。
【００４７】
次に、サブチャネルｊ＝ｊ’Ｍｉ−ｒ，．．．，（ｊ’＋１）Ｍｉ−ｒ−１におけるブロック数は、もとのスケジュールと同様にして基本的に計算される。すなわち、それは、
【００４８】
【数１７】
2006509454.tif 000021
に設定される。
【００４９】
上記修正の効果は、受信可能なチャネル数ｒが、テーブル３に示されるように、ｒ＝２に対して少ない場合に特に大きなものとなる。この例では、映画を分割するブロック数は、係数４より大きなものとなりうる。さらに、シーケンスが収束するべき級数のベースは、有意に増加する。ｒ＝２に対して、それは１．７５から２．２０に増加する。ｒ＝３に対して、それは２．４２から２．５５に増加し、ｒ＝４に対しては２．６２から２．６６に増加する。わかるように、この影響はｒの小さな値に対して最も大きなものとなり、ｒの小さな値は浪費される受付容量がｒの小さな値に対してより（比較的）深刻なものとなるという事実により生じる。
【００５０】
【表３】
2006509454.tif 000022
ここで、ｄｉはｄｉ−ｒ（ｉ＞ｒ）の整数倍であることが好ましいが、実際にはこのスケジュールは幾分は精緻化することが可能である。例えば、図６の例では、チャネル３のサブチャネル０が終了すると、チャネル５の新たな２つのサブチャネルを、チャネル３のサブチャネル１が終了すると、チャネル５の新たな３つのサブチャネルを開始することが可能である。従って、チャネル５はまた、最初の２つが４の期間とフェージング０と２をそれぞれ有し、最後の３つが６の期間とフェージング１，３及び５をそれぞれ有する５つのサブチャネルを有するようにしてもよい。このようにして、新たに開始されるサブチャネルは、依然としてちょうど終了したサブチャネルと同じ時間単位を占有するが、サブチャネル数に関する制約は緩和される。このように実現されたスケジュールの改良は、単に限界的なものである（実験は、ブロック数の１％のみの増加しか与えないか、全く増加させない）。
【００５１】
ここで、上記実施例は本発明を限定するのでなく例示するものであり、当業者は添付された請求項の範囲から逸脱することなく他の多くの実施例を構成することができるであろう。請求項において、カッコ内の参照符号は、当該請求項を限定するものと解釈されるべきではない。「有する」という用語は、請求項列挙されたもの以外の他の要素またはステップの存在を排除するものでない。本発明は、複数の相異なる要素を有するハードウェアによって、そして適切にプログラムされたコンピュータによって実現することができる。複数の手段を列挙したシステムクレームでは、これらの手段の一部は、同一のハードウェアアイテムにより実現することができる。コンピュータプログラムプロダクツは、光記憶装置などの適切な媒体に格納/配布されてもよいが、配信システムのネットワーク、インターネットまたは無線通信システムを介し配布されるなど、他の形態により配布されてもよい。
【図面の簡単な説明】
【００５２】
【図１】図１は、本発明が利用可能な一例となる階層的配信ネットワークを示す。
【図２】図２は、本発明による配信システムのブロック図を示す。
【図３】図３は、ＰａｇｏｄａＮＶｏＤプロトコルを示す。
【図４】図４は、Ｐａｇｏｄａプロトコルによるチャネルの追加を示す。
【図５】図５は、オリジナルのＰａｇｏｄａプロトコルによる未使用受付容量を示す。
【図６】図６は、本発明による受付スケジュールを示す。
【図１】
2006509454.tif 000023
【図２】
2006509454.tif 000024
【図３】
2006509454.tif 000025
【図４】
2006509454.tif 000026
【図５】
2006509454.tif 000027
【図６】
2006509454.tif 000028
【国際調査報告】
2006509454.tif 000029
2006509454.tif 000030
2006509454.tif 000031