(57)【要約】多数のＶＢＲビデオ番組が、ＶＯＤ設定における番組の取得を最適化するようにＭＺＲディスクに記憶される。前記番組は、実質的に単調な非増加重み対サイズ比率の系列で外側端から内側端へ前記ディスクに記憶される。番組の重みは、該番組のビットレート、該番組の継続時間及び該番組の人気性に依存する。
2006520509.tif 000002
【特許請求の範囲】
【請求項１】
多数のデータファイルをディスクに記憶する方法であって、
前記データファイルの各々が、前記各々のファイルの対応するサイズの値と、前記各々のファイルの維持可能な再生送出速度、前記各々のファイルの再生送出過程の継続時間及び前記各々のファイルの人気性に依存する対応する重みの値とによって特徴付けられ、
当該方法は、前記各々のファイルが、減少する対応する半径ディスク座標の方向に、前記対応する重みの値の前記対応するサイズの値に対する比率の各々の値の実質的に単調な非増加系列を形成するように、各々の半径ディスク座標を用いて前記ディスクにおける対応する位置に前記各々のデータファイルを収容するステップを有する、
方法。
【請求項２】
請求項１に記載の方法であって、前記データファイルの少なくとも１つが、ビデオコンテンツを有する、方法。
【請求項３】
請求項２に記載の方法であって、ＶＯＤサービスにおいて用いられる、方法。
【請求項４】
請求項１に記載の方法であって、前記ディスクがＭＺＲディスクを含む、方法。
【請求項５】
請求項１に記載の方法であって、前記データファイルの少なくとも１つが、ＶＢＲ符号化コンテンツを有する、方法。
【請求項６】
多数のデータファイルを記録するディスクを有する記憶システムであって、
前記データファイルの各々が、前記各々のファイルの対応するサイズの値と、前記各々のファイルの維持可能な再生送出速度、前記各々のファイルの再生送出過程の継続時間及び前記各々のファイルの人気性に依存する対応する重みの値とによって特徴付けられ、
前記各々のデータファイルは、前記各々のファイルが、減少する対応する半径ディスク座標の方向に、前記対応する重みの値の前記対応するサイズの値に対する比率の各々の値の実質的に単調な非増加系列を形成するように、各々の半径ディスク座標を用いて前記ディスクにおける対応する位置に収容される、
記憶システム。
【請求項７】
請求項６に記載のシステムであって、前記データファイルの少なくとも１つが、ビデオコンテンツを有する、システム。
【請求項８】
請求項６に記載のシステムであって、前記ディスクがＭＺＲディスクを含む、システム。
【請求項９】
請求項６に記載のシステムであって、前記データファイルの少なくとも１つが、ＶＢＲ符号化コンテンツを有する、システム。
【請求項１０】
データファイルをディスクに記憶することを可能にする方法であって、
前記データファイルが、前記ファイルのサイズの値と、前記ファイルの維持可能な再生送出速度、前記ファイルの再生送出過程の継続時間及び前記ファイルの人気性に依存する重みの値とによって特徴付けられ、
前記ディスクが、各々が半径ディスク座標を有する、複数の夫々のセグメントにおいて組織され、
前記セグメントの各々は、対応するパラメータの値を割り当てられ、前記各々の値が、減少する半径ディスク座標の方向において単調系列を形成するようにされ、
当該方法が、前記データファイルを、前記パラメータの値が前記重みの値の前記サイズの値に対する比率と最良に一致する前記セグメントのうちの特定の１つに記憶することを可能にするステップを有する、
方法。
【請求項１１】
請求項１０に記載の方法であって、ＶＯＤサービスにおいて用いられる、方法。
【請求項１２】
データファイルを記憶するディスクを有する記憶システムであって、
前記ディスクが、各々が対応する半径方法ディスク座標を有する、複数の夫々のセグメントにおいて組織され、
前記セグメントの各々は、対応するパラメータの値を割り当てられ、前記各々の値が、減少する半径ディスク座標の方向において単調系列を形成するようにされ、
前記データファイルが、前記ファイルのサイズの値と、前記ファイルの維持可能な再生送出速度、前記ファイルの再生送出過程の継続時間及び前記ファイルの人気性に依存する重みの値とによって特徴付けられ、
当該システムが、前記データファイルを、前記パラメータの値が前記重みの値の前記サイズの値に対する比率と最良に一致する前記セグメントのうちの特定の１つに記憶することを可能にする、
記憶システム。
【請求項１３】
多数のファイルをＭＺＲディスクに記憶する方法であって、
前記ファイルの各々は、対応するサイズと、前記各々のファイルの維持可能な再生送出速度、前記各々のファイルの再生送出過程の継続時間、及び前記各々のファイルの人気性に依存する対応する重みとを有し、
各々のファイルが、対応する重み対サイズ比率の値を有し、
前記ディスクが複数の各々のゾーンを有し、
転送レートの対応する値が、各々のゾーンと関連付けられ、前記転送レートの夫々の値が、減少する半径ディスク座標の方向において単調に減少する系列を形成するようにされ、
当該方法が、前記ゾーンに対して前記ファイルを割り当て、この場合に、実質的に前記ゾーンのうちの特定の１つに割り当てられた前記ファイルの各々が、更なるゾーンに割り当てられた実質的にいかなる更なるファイルの更なる重み対サイズ比率より低くない重み対サイズ比率を有するようにされ、前記更なるゾーンの転送レートの値が、前記特定のゾーンの前記転送レートの値より低い、
方法。
【請求項１４】
多数のファイルがＭＺＲディスクに記憶されている記憶システムであって、
前記ファイルの各々は、対応するサイズと、前記各々のファイルの維持可能な再生送出速度、前記各々のファイルの再生送出過程の継続時間、及び前記各々のファイルの人気性に依存する対応する重みとを有し、
各々のファイルが、対応する重み対サイズ比率の値を有し、
前記ディスクが複数の各々のゾーンを有し、
転送レートの各々の値が、対応するゾーンと関連付けられ、前記転送レートの各々の値が、減少する半径ディスク座標の方向において単調に減少する系列を形成するようにされ、
前記ファイルが、前記ゾーンに対して割り当てられ、この場合に、実質的に前記ゾーンのうちの特定の１つに割り当てられた前記ファイルの各々が、更なるゾーンに割り当てられた実質的にいかなる更なるファイルの更なる重み対サイズ比率より低くない重み対サイズ比率を有するようにされ、前記更なるゾーンの転送レートの値が、前記特定のゾーンの前記転送レートの値より低い、
記憶システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オーディオ／ビジュアル番組のようなデータファイルを例えば磁気ディスクのようなディスクに記録する方法に関する。本発明は、排他的にではないが、特に、ビデオ・オン・デマンド（ＶＯＤ）サービスのサービス提供者に関する。
【背景技術】
【０００２】
ハードディスク駆動装置と呼ばれるような磁気ディスクは、ＶＯＤサーバにおいて多数のビデオ番組を記憶し同時に多数のクライアントによって効率的に取得する用途に適した大容量駆動装置である。１つのディスクの記憶容量は、大量のデジタル化された高品質ＭＰＥＧ符号化可変ビットレート（ＶＢＲ）番組を記憶するのに十分こと足り、データがディスクから読み出され得るレートは、多数の使用者が同時に独立してこれらの番組を視聴することを可能にする。
【０００３】
使用者が番組を視聴しようとする場合、ディスクからこの番組のデータブロックを繰り返し呼び出しをすると共に固体状態メモリバッファに記憶する再生送出（ｐｌａｙ  ｏｕｔ）過程が開始される。このことが起こるべき速度及びデータブロックのサイズの両方は、とりわけ、サーバの特定の設定と同様に番組自体にも依存する。該速度は、バッファがアンダーフロー及び又はオーバーフローするのを防ぐことによって、番組の継続時間において解釈されない再生送出を可能にするのを持続可能であるべきである。バッファは、対応するレートで空にされ、コンテンツは、例えばアクセスネットワーク及び家庭内ネットワークを介して使用者へ送信される。このレートは、通常５〜７Ｍｂｉｔ／ｓのオーダである。リニア視聴、休止及び映画の別のシーン又は部分へのジャンプの他に、逆再生、いずれか一方の方向へスローモーション及びいくつかの速度での早送り／早巻戻しのような、特殊なモードも対応されている。特定の番組の人気性によっては、より多くの使用者が同一の番組を略同時に観ることを望み得る。このことは、この対応する数の個別の再生送出過程を招く。
【０００４】
多数の再生送出過程を同時に維持することは、各々の過程が必要とするサービスの品質を保証するディスクスケジューリング・アルゴリズムを必要とする。ディスクスケジューリング・アルゴリズムの概要に関しては、例えば、１９９８年、Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ２１、頁１３２８〜１３４３における、Ｊａｎ  Ｋｏｒｓｔ  等による「Ｃｏｍｐａｒｉｎｇ  ｄｉｓｋ  ｓｃｈｅｄｕｌｉｎｇ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ＶＢＲ  ｄａｔａ  ｓｔｒｅａｍｓ」を参照されたい。
【０００５】
ディスクの物理特性は、ディスク表面に対する読み出しヘッド又は書き込みヘッドの半径方向位置に応じて、データがディスクから読み出され得る又はディスクに書き込まれ得る変化最大転送レートを生じさせる。ディスク表面の内側端近傍に記憶されたデータは、ディスクが一定角速度で回転するので、外側端近傍に記憶されたデータよりも低レートで読み出される。一般的な値は、現在の最新磁気ディスクに関して、内側端近傍で２００Ｍｂｉｔ／ｓから及び外側端近傍で４００Ｍｂｉｔ／ｓである。
【０００６】
現在商業的に入手可能なディスクは、通常多数のゾーンを利用する。１つのゾーンは、連続するトラックの一群であり、転送レートは、ゾーン毎に一定に保たれる。これら多重ゾーン記録（ＭＺＲ）ディスクは、転送レートが反半径方向にすなわちディスク表面の外側から内側端へ線形的に減少するような、一定密度ディスクの理想状況に近づくことを目指している。ＭＺＲに関する更なる背景的情報に関しては、例えば、１９９４年、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ、Ｖｏｌ．２７、Ｎｏ．３、頁１７〜２９におけるＣ．Ｒｕｅｍｍｌｅｒ及びＪ．Ｗｉｌｋｅｓによる「Ａｎ  ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  ｄｉｓｋ  ｄｒｉｖｅ  ｍｏｄｅｌｉｎｇ」を参照されたい。
【０００７】
いわゆる最小維持可能転送レート（ｍＳＴＲ）は、新たな再生送出過程に関して決定性品質保証（ｄｅｔｅｒｍｉｎｉｓｔｉｃ  ｑｕａｌｉｔｙ  ｇｕａｒａｎｔｅｅｓ）を備えるアドミッション制御を実行するのに頻繁に用いられ得る。ｍＳＴＲは、ディスクの内側端近傍における大きなデータブロックの読出しに対応する。ｍＳＴＲでの読出しは、全ての場合において保証され得る。例として、２００Ｍｂｉｔ／ｓのｍＳＴＲを有するディスクは、各々６Ｍｂｉｔ／ｓの２００／６＝３３再生送出過程を同時に維持することが可能である。参考として、最大維持可能転送レート（ＭＳＴＲ）は、ディスクの外側端近傍の大きなデータブロックを読み出す場合に達成される。
【０００８】
データのディスクからの読出しの効率を向上するために、「トラックペアリング」（ＴＰ）として既知である記憶ストラテジは、各々のデータブロックを２つのサブブロックに分割する。１つのサブブロックは、ディスクの外側端の近くに記憶され、もう１つは、内側端の近くに記憶される。サブトラックのサイズ及びディスクにおける位置は、これらサブトラックが、等しい読み出し時間を必要とし、２つのペアになるサブブロックの読出しが、一定でｍＳＴＲより著しく大きい転送レートになるようにされる。また平均維持転送レート（ＡＳＴＲ）と呼ばれる、これらのペアにされたサブブロックを読み込むレートも、決定性品質保証を与えるのに用いられ得る。ＴＰに関する更なる背景的情報に関しては、例えば、１９９５年、Ｐｒｏｃ．  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ｓｙｓｔｅｍｓ、頁２４８〜２５５におけるＹ．Ｂｉｒｋによる「Ｔｒａｃｋ  ｐａｉｒｉｎｇ：  ａ  ｎｏｖｅｌ  ｄａｔａ  ｌａｙｏｕｔ  ｆｏｒ  ＶＯＤ  ｓｅｒｖｅｒｓ  ｗｉｔｈ  ｍｕｌｔｉ−ｚｏｎｅ  ｒｅｃｏｒｄｉｎｇ  ｄｉｓｋｓ」を参照されたい。
【０００９】
１９９６年、Ｐｒｏｃｅｅｄｉｎｇｓ  ２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂａｌｔｉｃ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｄａｔａｂａｓｅｓ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｙｓｔｅｍｓ、ＢａｌｔｉｃＤＢ’９６、Ｔａｌｌｉｎ、Ｅｓｔｏｎｉａ、頁１〜１４における、Ｓ．Ｇｈａｎｄｅｈａｒｉｚａｄｅｈ等による「Ｐｌａｃｅｍｅｎｔ  ｏｆ  Ｄａｔａ  ｉｎ  Ｍｕｌｔｉ−Ｚｏｎｅ  Ｄｉｓｋ  Ｄｒｉｖｅｓ」において、ＭＺＲディスクの性能を、ゾーンにわたりデータの（オフライン）位置を制御することによって向上する技術が説明されている。更に具体的には、Ｇｈａｎｄｅｈａｒｉｚａｄｅｈ等は、ファイルをアクセスの頻度、すなわち該ファイルの人気性に従い、高いものから低いものへ並べ、ファイルの系列を、最も外側（すなわち最速の）ゾーンで開始して次第に最も内側のゾーンへ移って隣接するようにしてレイアウトすることを提案している。この順序は、ファイル毎の平均転送時間を最小化すると言われる。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
当該発明者は、ディスクリソース使用が最適化されるように、如何にディスクに複数のファイル又は番組を記憶するかに関する問題を考慮する。
【課題を解決するための手段】
【００１１】
この目的のために、各々の番組は、ビットレート、継続時間、サイズ及び人気性によって特徴付けられると考慮される。
【００１２】
番組のビットレートは、維持可能な再生送出速度を示し、通常、比較的小さい数であるような、いかなる数の連続するフレームにおいても計算される、最大平均フレームサイズに基づく。代わりとして、前記ビットレートは、ビットレート平滑化アルゴリズムに基づき得る。ビットレート平滑化アルゴリズムは、ネットワークを介したＶＢＲデータの効率的な伝送を達成するのに用いられる。したがって、番組のビットレートは、ピークレートよりも一般的にずっと小さく、ピークレートは、最大サイズフレームによって規定される。また斯様なビットレートも、平均レートよりも一般的に大きい。ビットレート値は、決定論的品質保証を与えるのに用いられ得る。番組の継続時間は、通常、番組全体の線形再生送出時間を表すが、代わりとして、例えば飛び越し再生及びリプレイ再生のようなトリックモードが頻繁に実行される場合、関連する再生送出過程の平均再生送出時間を表し得る。人気性は、この番組の関する単位時間毎のクライアント要求の全体数の一部分によって代表される。サイズは、番組がディスクにおいて記憶される、ファイルのビット数を与える。可変ビットレート（ＶＢＲ）番組に関して、通常、ビットレートは継続時間に対するサイズの比率よりも大きいこと状態にあることを注意すべきである。番組がディスクにおいて記憶されていた場合、この番組からのデータがディスクから取得される最小レートを表す転送レートＲが、この番組と関連付けられ得る。転送レートＲは、この同じ番組のどの他のデータよりもディスクの内側端の近くに記憶されるこの番組のデータの読出しに一致する転送レートと一致する。複数の番組がディスクに記憶されるべき場合、特定の番組の転送レートＲは、個々の番組に対する記憶空間の全体割当に依存することを注意されるべきである。
【００１３】
例えば磁気ディスクにビデオ番組のようなリアルタイム・データファイルを記憶することは、ディスクリソース使用、例えば転送レート関して最適化され得る。転送レートは、多数の使用者ＶＯＤ設定におけるこれら番組を再生送出する効率を決定する。費用を最小化する最適解決法が発見されるべき費用関数（ｃｏｓｔ  ｆｕｎｃｔｉｏｎ）が定義され得る。ＭＺＲディスクに関して、多数の番組を最適に記憶するオフライン番組は、ＮＰハード（非決定性多項式）問題である。したがって、当該問題の複雑性により、最適又は近最適記憶構成を与える実用的な解決法に関するニーズがある。
【００１４】
当該発明者は、オフライン問題に対する最適又は近最適解決法を得るためのディスクに多数のデータファイルを記憶する方法を以下のように提案する。各々のファイルは重みを割り当てられ、この重みの値は、ファイルのビットレートの値、継続時間の値及び人気性の値並びに可能であれば更なる点に関して依存する。重みは、リソース使用に関する、ディスクシステムに対するこの特定ファイルの負荷を表す。例えば、特定のファイルの重みは、ビットレート、継続時間及び人気性の積に依存するように取られ得る。シミュレーションが強く提案するのは、最適又は近最適記憶が達成されるのは、ファイルがファイルの重みのファイルのサイズに対する比率の非増加値の順序でディスクの外側端から内側端へ配置される場合であるということである。更に具体的には、本発明の実施例は、多数のデータファイルをオフライン設定でディスクに記憶する方法に関する。データファイルの各々は、対応するファイルのサイズの各々の値によって、及び重みの各々の値によって特徴付けられる。重みは、各々のファイルの維持可能再生送出速度、各々のファイルの再生送出過程の継続時間及び各々のファイルの人気性に依存する。当該方法によると、各々のデータファイルは、対応する半径ディスク座標でディスクにおける対応する位置に収容される。この実施例において、各々のファイルは、減少する各々の半径ディスク座標の方向に、各々の重みの値の各々のサイズの値に対する比率の対応する値の実質的に非増加な系列を形成する。本発明の更なる実施例において、データファイルは、ビデオコンテンツを有する。好ましくは、当該方法は、ＶＯＤサービスにおいて用いられる。好ましくは、ディスクは、ＭＺＲディスクを有する。好ましくは、データファイルの少なくとも１つは、ＶＢＲ符号化コンテンツを有する。上記におけるいて用いられた語句「実質的に（ｓｕｂｓｔａｎｔｉａｌｌｙ）」は、重み対サイズの比率の単調な非増加の系列のわずかな偏差が、許容され得る代替案又は更に良い解決法を提供し得ることを示す。更に、追加的な最適化過程が以下に説明される。一群のファイルの可能な順列の数は、各々の次の追加されるファイルにより指数的以上に増加することを注意されるべきである。したがって、例えば１ダースのファイルの順列の極端に小さい準群は、本発明における近最適又は最適構成に対応する。この構成の特徴は、全て又は実質的に全てのファイルが、減少する半径ディスク座標の方向において重み対サイズ比率の単調な非増加系列で記憶される。この傾向を示さない構成は、実用的な目的に関して、最適又は近最適ではない。
【００１５】
また本発明は、ディスクを用いて多数のデータファイルを記憶する記憶システムにも関する。データファイルの各々は、対応するファイルのサイズの各々の値によって、及び重みの各々の値によって特徴付けられる。重みは、各々のファイルの維持可能再生送出速度、各々のファイルの再生送出過程の継続時間及び各々のファイルの人気性に依存する。各々のデータファイルは、ディスクにおける対応する位置に対応する半径ディスク座標で収容される。各々のファイルは、減少する各々の半径ディスク座標の方向に、サイズの各々の値に対する重みの各々の値の比率の対応する値の実質的に単調な非増加系列を形成する。この形式において書き込まれたディスクは、動作時の使用におけるリソース使用に関して最適化される。
【００１６】
本発明の更なる実施例は、多数のファイルをオフライン設定でＭＺＲディスクに記憶する方法に関する。ファイルの各々は、対応するサイズ及び対応する重みを有する。
重みは、各々のファイルの維持可能再生送出速度、各々のファイルの再生送出過程の継続時間及び各々のファイルの人気性に依存する。各々のファイルは、重み対サイズの比率の対応する値を有する。ディスクは、複数の各々のゾーンを有する。転送レートの各々の値は、各々の対応するゾーンに関連付けられ、転送レートの対応する値が、減少する半径ディスク座標の方向に単調な減少系列を形成するようにされる。当該方法は、以下の態様でファイルをゾーンに割り当てるステップを有する。実質的に、ゾーンの特定の１つに割り当てられるファイルの各々の特定の１つは、更なるゾーンに割り当てられる実質的ないかなる更なるファイルの更なる重み対サイズ比率より低くない重み対サイズ比率を有し、前記更なるゾーンの転送レートの値は、前記特定のゾーンの転送レートの値より低い。この実施例は、ＭＺＲディスクのゾーン内に記憶されたファイルの順序の順列が費用関数の値に作用しないことを考慮に入れる。
【００１７】
当該文章中において用いられる語句「ファイル（ｆｉｌｅ）」は、大きなファイル又は番組の一部について言及し得る。すなわち、実用的な目的に関して、データファイルは、多くの場合、比較的大きいかたまりの固定されたサイズでディスクに記憶される。
ＭＺＲディスクに関して、１つのゾーン内に完全に含まれる全てのかたまりの位置は、本発明によると、最適又は近最適リソース使用を妥協することなく恣意的に順列化され得る。大きいファイル又は番組の重み対サイズ比率は、本発明による、大きいファイル又は番組の記憶ステップを制御するより小さい部分へ好ましくは持ち越される制御パラメータである。代わりとして、番組のいくつかの部分が、例えばトリック再生モードを可能にする再生送出過程において、同番組の他の部分より人気があることもあり得るので、他の部分より人気のある部分は、より高い重みの値を与えられ、記憶ステップにおいてより細かい粒状性を可能にし得る。前記部分が全て同じサイズである場合、このことは、同じファイルの部分の重み対サイズの比率が互いに異なり得るということを意味する。
【００１８】
本発明におけるシステムの実施例は、ＭＺＲディスクにおいて記憶された多数のファイルを有する。ファイルの各々は、対応するサイズと、各々のファイルの維持可能な再生送出速度、各々のファイルの再生送出過程の継続時間及び各々のファイルの人気性に依存するような、対応する重みとを有する。各々のファイルは重み対サイズの比率の対応する値を有する。ディスクは、複数の各々のゾーンを有する。転送レートの各々の値は、対応するゾーンと関連付けされ、前記転送レートの各々の値が、減少する半径ディスク座標の方向に単調に減少する系列を形成するようにされる。ファイルは、実質的に、ゾーンのうちの特定の１つに割り当てられたファイルの各々の特定の１つが更なるゾーンに割り当てられた実質的にいかなる更なるファイルの更なる重み対サイズ比率より低くない重み対サイズ比率を有するように、ゾーンに割り当てられ、更なるゾーンの転送レートの値は、前記特定のゾーンの転送レートの値より低い。再び、この実施例は、ＭＺＲディスクの１つのゾーン内に記憶されたファイルまたはファイルのかたまりの順序の順列が、費用関数の値に影響を及ぼさないことを考慮に入れる。
【００１９】
上記のシナリオは、オフライン問題、すなわち一群のファイルが与えられた場合、いかにこれらが動作使用においてリソース使用を最小化するようにディスクに実装するべきかに関する。ここで、当該発明者は、オフライン・シナリオの発見をオンラインの場合に適用する。オンライン設定において、オンザフライで、新しいファイルは記憶されるべきであると共に、古いファイルは削除される必要がある。
【００２０】
オンライン問題を解決するために、当該発明者は、個々のファイル又は番組の代わりにクラスを考慮することを提案する。クラスの各々は、対応するクラスサイズ及び対応するクラス比率値を割り当てられる。クラスサイズの合計は、利用可能又は必要なディスクスペースを作成する。クラス比率値は、以下に更に説明される。収容されるべきファイルの重み対サイズ比率の比較を可能にするのは、エンティティである。クラス比率値及びクラスサイズは、例えばＶＯＤコンテンツの場合における使用者履歴及び使用者プロファイルに基づき決定される。クラス自体は、その後、ディスクの外側端から内側端への方向における単調な非増加系列のクラス値に従い構成される。ひとたびクラスのディスク位置が規定されると、新しいファイル又は番組が特定のクラスでディスクに記憶され、前記特定のクラスの比率値は、ファイル自体の重み対サイズ値に最も一致する。記憶されたファイルは、ディスクにおける該ファイルの位置に応じて該ファイル自身の転送レートを得る。前記特定のクラスにおいて新しいファイルを収容する十分な空きがない場合、１つ又は複数の以前に記憶されたファイルが削除される。その後、適切なクラス管理アルゴリズム、例えば、最も頻繁に使用されない順（ＬＦＵ）又は最も直近に使用されていない順（ＬＲＵ）のようなキャッシュ置き換えアルゴリズムは、削除されるべきファイルを識別する。
【００２１】
上記で紹介されたクラス比率は、オンライン設定でのファイルの記憶の準備において利用可能なディスクスペースをセグメント化することを可能にするエンティティである。クラスの数、これらの比率値及びサイズは、例えば履歴及び使用者プロファイルを元に決定される。例えば、サンプルファイルは、クラスタ化アルゴリズムに従い、個々の重み対サイズ比率値を元にしてクラスタ化される。クラスタ化アルゴリズムは、要素の一集団を多数のサブグループに区分化する。サブグループ内の要素は、一定の類似性を有する。クラスタ化アルゴリズムの１つの範疇は、階層的方法として既知である。これらアルゴリズムは、入力データを所望の数のクラスに２つ以上のステップで区分化する。一連の連続するデータの累積は、最終クラスタ数が得られるまで実行される。別の範疇は、非階層的アルゴリズムとして既知である。これらは、開始から固定数のクラスタを仮定する。要素は、特定のクラスタ化規準が最適化されるようにクラスタのうちに割り当てられる。可能性のある規準は、各々のクラスタの可変性を最小化している。各々のクラスタは、組み合された関連するサンプルファイルのサイズを有する。各々のクラスタは、例えば、可能であれば個々のファイルの重み対サイズ比率値間の変動を考慮するのに重み付けられる、サンプルファイルの重み対サイズ比率値の平均、又はクラスのサイズ等である、クラスタ比率値を割り当てられる。
【００２２】
より一般的に、本発明は、オンライン設定でデータファイルをディスクに記憶することを可能にする方法にも関する。データファイルは、ファイルのサイズの値によって、並びにファイルの維持可能な再生送出速度、ファイルの再生送出過程の（予想）継続時間及びファイルの人気性に依存する重み値によって特徴付けられる。ディスクは、各々の半径ディスク座標によって特徴付けられる複数の対応するセグメントに組織化される。各々のセグメントは、対応する値が、単調な系列を（すなわち単調な非増加又は単調な非減少系列を）減少する半径ディスク座標に形成するように、対応するパラメータの値を割り当てる。更に当該方法は、セグメントの特定の１つにおいてデータファイルを記憶することを可能にするステップであり、前記セグメントのパラメータの値が、ファイルの重みの値のファイルのサイズの値に対する比率と最も一致するようなステップを有する。したがって、セグメントは、上述のクラスと対応する。セグメントを識別するパラメータの例は、上述のように説明され、すなわち、ファイルの重み対サイズ比率と直接比較可能なクラス比率である。別の例は、セグメントに対して、各々の半径ディスク座標の単調に増加する又は減少する系列で前記セグメントの順序を表す数を割り当てている。その後、新しいファイルは、ファイルの重み対サイズ比率又は斯様な一連の比率を番号にマッピングするルックアップ・テーブルに基づき特定のセグメントに割り当てられる。ルックアップ・テーブルは、例えば履歴又はプロファイルに基づき準備され、凝縮された形式で、クラス比率におけるファイルの重み対サイズ比率のマッピングを表すと考慮され得る。したがって、本発明の実施例は、どのセグメントがどのファイルを記憶するのに用いられるべきかに関する案内（例えば、データ処理器、マニュアル、固定された又は使用者プログラマブルなルックアップ・テーブル又はサービス等）と組み合わせた事前セグメント化ディスクに関する。
【００２３】
明瞭性に関して、上述のＧｈａｎｄｅｈａｒｉｚａｄｅｈ等によるアプローチは、ディスクから番組全体を読み出すのに予想される時間を最小化する。実用的な状況において、この対策は、リアルタイム保証を個々の再生送出過程に与えるために、必要とされる又は蓄えておかれるべきリソースを必ずしも表さない。この対策は、より低い限界として用いられ得るが、このより低い限界が達成される又は接近される場合に問題が生じる。アドミッション制御、オンライン再交渉及びディスクスケジュール化アルゴリズムは、リソース必要条件が時間経過により変化し得るので、より複雑になる傾向がある。このことは、ＶＢＲ符号化番組だけでなくゾーン境界線を横切るＣＢＲ番組に関しても適用する。リアルタイム保証を提供するために全体寿命に関して再生送出過程に明確なビットレートを割り当てることによって、本発明におけるように、これらのタスクを大いに簡素化するが、ＮＰハード最適化問題を導く。以下において更に詳記されるようにこの問題に対して最適又は近最適解決法を与えるのは、本発明の発明的アプローチである。
【００２４】
ディスク配列は、本発明の目的に関して単一ディスクであると考慮される。
【００２５】
本発明は、ＣＤ−ＲＯＭ及びＤＶＤ  Ｒ＋Ｗのような光ディスク駆動装置に関すると同様に、上述のように、ＨＤＤに関する。これらの光ディスク駆動装置のより高速な種類は、一定各速度を用いる。その結果、転送速度は、ディスクがＨＤＤを備えているので、ディスク中心からの半径方向距離の関数である。
【００２６】
本発明は、添付の図面を参照にして、例を用いて更に詳細に説明される。
【００２７】
全ての図面にわたり、同じ参照符号は、同様の又は対応する特徴を示す。
【発明を実施するための最良の形態】
【００２８】
当該発明者によって考慮された問題の１つは、ディスクリソース使用が最適化されるような手法で、いかに多数の番組をディスクに記録するかと言う問題である。インデックス「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＜ｎである限りより低い費用を導くかが確認される。より低い費用が存在する場合、この交換ステップは実行され、iは、i＞１である場合１ずつ減らされる。費用がより低くない場合、iは、１ずつ増やされる。このアルゴリズムは、各々のステップがiを増やす又は費用を低くするのいずれかであるので、終了するまで保証される。最も多くてもｎ!である有限数の費用値が存在するので、アルゴリズムは終了する。
【００３５】
該アルゴリズムは、反対方向に動くのに、位置ｉ＋１において、第１候補に関する前方方向を検索するステップと、費用が更により低くされ得なくなるまで反対方向において発見された候補を引きずるステップとの間を行き来する。したがって、このアルゴリズムは、ここにおいて検索／引きずり（ＳＡＤ）として呼ばれる。
【００３６】
図２は、７つの番組を用いたＳＡＤの例における反復を例証する。各々の反復の開始における状態が示される。「＃」の印は、位置i及び位置i＋１の間に位置する。第２反復において、元の位置３における番組、すなわち略して番組３は、発見された第１候補である。その後、番組３は、第３反復において第１位置に引きずられる。その後、反復８において、番組６が、次の発見された候補である、等のことを反復する。
【００３７】
シミュレーションは、ＳＡＤの計算的複雑性は、最大でもＯ（ｎ２）であると示している。ＳＡＤテーマにおける変動は、以下の通りである。位置i＋１における引きずりの後の検索を開始する代わりに、ジャンプは、この引きずりが開始した位置を１ステップ越えた初めに実行される。このジャンプ検索／引きずりアルゴリズム（ＪＳＡＤ）は、最も悪い場合の計算的複雑性のＯ（ｎ２）を有し、最大でｎ個の候補が発見され、各々の候補は、最大で距離ｎにわたり引きずられる。シミュレーションは、ＪＳＡＤがＳＡＤと同様な性能を有することを示す。反復過程における変動は、以下の検索／交換（ＳＡＳ：ｓｅａｒｃｈ  ａｎｄ  ｓｗｉｔｃｈ）であり、一度初期の順序で進めて、いずれかの２つの隣接する番組を、このことが費用関数の値を減らす場合に、交換する。
【００３８】
図３は、オフライン設定におけるディスク３００への複数のファイルの記録を概略的に例証する。ディスク３００は、この例のおいてファイル３０２、３０４、３０６、３０８及び３１０を記憶する。ディスク３００は、外側端３１２及び内側端３１４を有する。外側端３１２から内側端３１４への方向において、ファイル３０２ないし３１０は、ファイル３０２が外側端３１２の近くに記憶され、ファイル３０４が次であり、ファイル３０６がファイル３０４に続くと共にファイル３０８の前にあり、ファイル３１０が内側端３１４の近くに記憶されると共に３０８に続く系列を形成する。ファイル３０２ないし３１０の各々は、上述のように、対応するファイルサイズに対する対応するファイルサイズの重みの比率の対応する値を有する。本発明において、ファイル３０２ないし３１０は、比率値の系列が外側端３１２から内側端３１４への単調な非増加であるように、記憶される。ファイル３０２と関連付けられた比率値は、ファイル３０４と関連付けられた比率より小さくない。ファイル３０４と関連付けられた比率値は、ファイル３０６と関連付けられた比率より小さくない。ァイル３０６と関連付けられた比率値は、ファイル３０８と関連付けられた比率より小さくない。ファイル３０８と関連付けられた比率値は、ファイル３１０と関連付けられた比率より小さくない。
【００３９】
図４は、半径ディスク座標の関数であるＭＺＲディスクの転送レートの図である。ＭＺＲディスクは、複数のゾーン４０２、４０４、４０６、…、４１２に区分化される。半径ディスク座標の各々の範囲及び各々の転送レートは、各々のゾーンと関連付けられる。転送レートは、１つのゾーンにおいて一定である。ゾーン４０２は、ＭＺＲディスクの外側端の近傍にあり、ゾーン４１２は、ＭＺＲディスクの内側端の近傍にある。ここで、図１の費用関数Ｃを考慮する。転送レートＲは、和演算の項の分母において現れる。特定のゾーンにおけるファイルの位置の変更は、費用関数に影響しないことは明らかである。
【００４０】
図５は、オンライン設定におけるディスク５００において多数のファイルの記憶の態様を概略的に例証する。ディスク５００の記憶スペースは、複数のクラス５０２、５０４、５０６、５０８及び５１０にセグメント化される。各々の斯様なクラスは、複数のファイルを記憶することが可能である。オンライン設定においてファイルを記録するのを制御するのに用いられるクラスパラメータの対応する値は、各々のクラス５０２ないし５１０と関連付けられる。クラス５０２ないし５１０に関するクラスパラメータ値は、単調な、例えば外側端３１２から内側端３１４への非増加系列を形成する。該着想は、ファイルの動作的使用におけるリソース使用を最適化するために、クラスパラメータ値が、記憶されるべきファイルの重み対サイズ比率と最良の調和を形成するような、クラス５０２ないし５１０の特定の１つにおけるファイルを記憶することである。例えば、クラスパラメータ値は、上述のような最適又は近最適割当を発見するための、多数の群のファイルを用いて実行された仮定実験において該クラスに割り当てられるファイルのサブセットの重み対サイズ比率の平均値である。
【図面の簡単な説明】
【００４１】
【図１】図１は、費用関数の例を与える。
【図２】図２は、最適順序を発見する反復過程の例を与える。
【図３】図３は、オフライン設定で多数のファイルをディスクに記憶する態様を示す。
【図４】図４は、ＭＺＲディスクの転送レートを示す図である。
【図５】図５は、オンライン設定で多数のファイルをディスクに記憶する態様を示す。
【図１】
2006520509.tif 000003
【図２】
2006520509.tif 000004
【図３】
2006520509.tif 000005
【図４】
2006520509.tif 000006
【図５】
2006520509.tif 000007
【国際調査報告】
2006520509.tif 000008
2006520509.tif 000009