(57)【要約】      （修正有）【課題】装置の不具合が存在したときシステムの所定の信頼性保証を確保するため、各マルチメディアファイルの符号化部分を分散する方法を提供する。【解決手段】装置数が整数ｎである分散されている記憶装置にマルチメディアファイルの各部分を割り当てる方法であって、所与の期間の連続的再生のためのデータを表すウィンドウに各ファイルを分割するステップと、各ファイルについて、ファイルの何れか下のウィンドウが何れかｋ個のシンボルから復元可能となるような数ｋを決定するステップと、各ファイルの各ウィンドウについて、イレイジャコーディングを利用して生成されるｎ個の対応するシンボルを、各装置について１つを割り当てるステップと、ファイルのプリフィックスウィンドウによって、第１ステップの後に各装置に残された格納メモリを部分的又は完全に充填するステップとを有する方法。【選択図】図１
2008118623.tif 000002
【特許請求の範囲】
【請求項１】
装置数が整数ｎである分散されている記憶装置にマルチメディアファイルの各部分を割り当てる方法であって、
（ａ）所与の期間の連続的再生のためのデータを表すウィンドウに各マルチメディアファイルを分割するステップと、
（ｂ）各マルチメディアファイルについて、ファイルの何れか下のウィンドウが何れかｋ個のシンボルから復元可能となるような数ｋを決定するステップと、
（ｃ）前記各マルチメディアファイルの各ウィンドウについて、イレイジャコーディングを利用して生成されるｎ個の対応するシンボルを前記装置に、各装置について１つを割り当てるステップと、
（ｄ）前記マルチメディアファイルのプリフィックスウィンドウによって、前記第１ステップの後に各装置に残された格納メモリを部分的又は完全に充填するステップと、
を有する方法。
【請求項２】
各ファイルを配信するステップをさらに有する、請求項１記載の方法。
【請求項３】
装置に格納される前記ファイルの各部分のサイズが、何れか所与のファイルについて、該ファイルの再生イベントが遅延又は中断される確率を最小化するよう選択される、請求項１又は２記載の方法。
【請求項４】
再生されていないファイルからのステップ（ｄ）に対応するデータが、再生されているファイルからのダウンロードされたデータによって上書きされる、請求項１乃至３何れか一項記載の方法。
【請求項５】
ファイルの配信中、何れかの装置が該装置に格納されるファイルのサイズに等しいサイズを有する所望のプリフィックスを格納し、
前記プリフィックスを超えて、前記ファイルについて維持する前記符号化データをウィンドウ毎に生成する、請求項２記載の方法。
【請求項６】
イレイジャコードの第１ステージにより増大されたもとのファイルが配信され、
前記装置がランダムコードを生成する、請求項２記載の方法。
【請求項７】
ステップ（ｄ）が、前記マルチメディアファイルの普及の指標を用いて実行される、請求項１乃至６何れか一項記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークにおけるコンテンツ配信の分野に関する。
【背景技術】
【０００２】
本発明は、より詳細には、何れかの装置からの何れからのマルチメディアファイルの効率的なマルチメディア再生を可能にするため、マルチメディアファイルの各部分を分散化された記憶装置に割り当てる方法に関する。それは、共有された通信チャネルが利用可能であり、例えば、装置がＷＩＦＩインタフェースを有し、通信範囲内にあることを仮定している。共有された通信チャネルは、例えば、配信チャネルである可能性がある。
【０００３】
各装置がマルチメディアコンテンツにアクセスすることを可能にするよう協働する記憶装置の各種システムによると、従来技術では、信頼性は欠く装置の信頼性を向上させることによって実現され、グローバルにみなされるシステム全体については実現されていない。本発明は、システムにさらなる信頼性を与えるため、装置間で共有されている通信チャネルの存在に依拠する。装置の不具合に関して信頼性が考慮される。従来のシステムと異なり、劣化した再生体感の発生を最小限にするＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）要求が、本発明では考慮される。
【特許文献１】ＥＰ１６３３１１２Ａ
【非特許文献１】Ｌｅｅ  Ｊ  Ｙ  Ｂ  ｅｔ  ａｌ“Ｄｅｓｉｇｎ  ａｎｄ  ａｎａｌｙｓｉｓ  ｏｆ  ａ  ｆａｕｌｔ−ｔｏｌｅｒａｎｔ  ｍｅｃｈａｎｉｓｍ  ｆｏｒ  ａ  ｓｅｒｖｅｒ−ｌｅｓｓ  ｖｉｄｅｏ−ｏｎ−ｄｅｍａｎｄ  ｓｙｓｔｅｍ”，Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ，２００２．Ｐｒｏｃｅｅｄｉｎｇｓ．Ｎｉｎｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  １７−２０  Ｄｅｃ．２００２，Ｐｉｓｃａｔａｗａｙ，ＮＪ，ＵＳＡ，ＩＥＥＥ，１７  Ｄｅｃｅｍｂｅｒ  ２００２，ｐａｇｅｓ  ４８９−４９４
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の課題は、装置の不具合が存在したときシステムの所定の信頼性保証を確保するため、各マルチメディアファイルの符号化部分を分散する方法を提案することである。
【０００５】
本発明の他の課題は、最大数のコンカレント装置が各マルチメディアファイルを同時再生することが可能となることを保証するため、マルチメディアファイルの追加的であるが、必ずしも符号化されていない各部分を装置に割り当てる方法を提案することである。これは、各マルチメディアファイルの普及に関する情報が利用可能である場合、このような普及に関する知識を利用するであろう。
【０００６】
本発明が解決しようとする技術的問題は、装置の一部に不具合が存在しても、共有された通信チャネルを利用して、装置が格納されているマルチメディアファイルを効率的に再生することが可能となるように、分散された記憶装置上のマルチメディアファイルからのデータを分散させる方法に関するものである。
【課題を解決するための手段】
【０００７】
本発明は、それのより広範な意味により請求項１に規定される。
【０００８】
効果的な実施例が、従属形式の請求項に与えられる。
【０００９】
再生のための最大のＱｏＳと共有される通信チャネルの最小限の使用によって、各装置へのデータの所望の配置を実現する方法が与えられる。
【００１０】
本発明の他の特徴は、
ｉ）再生処理中の共有された通信チャネルを利用するためのスキームと、
ｉｉ）再生処理中の装置上への格納を管理するスキームと、
を有する。
【発明の効果】
【００１１】
本発明によると、装置の不具合が存在したときシステムの所定の信頼性保証を確保するため、各マルチメディアファイルの符号化部分を分散する方法を提供することが可能である。
【発明を実施するための最良の形態】
【００１２】
まず、各マルチメディアファイルが、各ウィンドウが与えられた期間における連続的再生のためのデータを表しているウィンドウに分割されると仮定する。
【００１３】
ファイルの各部分の所望の配置は、２つの主要なステップを有する。
【００１４】
第１ステップでは（以降、“フェーズ１”と呼ぶ）、各装置に配置される必要がある各ファイルの固定された部分が決定される。この部分は、特定のローカルな信頼性目標を充足するよう選択される。その詳細は、以下の通りである。
【００１５】
各装置の故障確率が知られており、それがｐにより表されると仮定する。さらに、あるファイルｆを消失する最大確率が与えられ、それがｐ（ｆ）により表されると仮定する。共有された通信チャネルを介し通信可能な装置の総数をｎにより表す。このとき、ファイルｆの“復号化ナンバー”ｋ（ｆ）を以下のように決定する。それは、パラメータ（ｎ，ｐ）による２項ランダム変数が整数ｎ−ｋを超える確率が、目標とする信頼性確率ｐ（ｆ）より大きくならないような最大の整数ｋとして選択される。すなわち、それは、以下の不等式が成り立つような｛０，．．．，ｎ｝の最大の整数である。
【００１６】
【数１】
2008118623.tif 000003
マルチメディアファイルは、所与の期間（１秒など）の連続的な再生のためのデータを表すウィンドウに分離されると仮定する。
【００１７】
ｋ（ｆ）が決定されると、マルチメディアファイルｆの指定された各ウィンドウに対して、ｎ個のシンボルが生成され、何れかｋ（ｆ）個のシンボルからファイルのもとのウィンドウが復元可能となるように、イレイジャコーディング（ｅｒａｓｕｒｅ  ｃｏｄｉｎｇ）が用いられる。このとき、ファイルの各ウィンドウについて、ｎ個の対応するシンボルの１つが各装置に割り当てられる。このようなイレイジャコードは一般的なものであり、Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｃｏｄｅｓ（ＬＤＰＣ）、Ｒａｐｔｏｒ  Ｃｏｄｅｓ（ＲＣ）又はＲｅｅｄ−Ｓｏｌｏｍｏｎ（ＲＳ）コードなどのコードは、当該フェーズにおいて利用可能なイレイジャコードの一例である。当該処理は、ファイルｆの各ウィンドウについて繰り返され、その後、格納されるべきコレクションの各ファイルについて繰り返される。
【００１８】
図３は、本発明によると、各装置、各メディアファイル、各ウィンドウについて１つのシンボルが存在するウィンドウを有するファイルを表す。この図は、所与のファイル及び所与の装置に一意的なシンボルを表している。各ファイルｆの各ウィンドウは、当該ファイル及び当該ウィンドウに対してｋ（ｆ）個のシンボルの何れかのコレクションから再構成することができる。
【００１９】
各装置上に利用可能とされているメモリスペースが、ファイルの追加的部分を格納し、再生品質を最適化するのに利用される。ムービーの第１ウィンドウからスタートするウィンドウの連続するコレクションであるムービーのプリフィックスを格納することを選択する（図５参照）。この選択の理由は、プリフィックスが再生をスタートすることが要求されているということである。
【００２０】
第２ステップは（以降、“フェーズ２”と呼ぶ）、以下のように実行される。フェーズ１のエンドにおいて各装置に残されている格納メモリを決定する。各装置について、当該装置に格納されるファイルｆのサイズＳ（ｆ）を決定する。（簡単化のため、当該サイズは装置から独立したものであると仮定しているが、装置に依存したサイズを扱う拡張がされてもよく、それは各装置が異なる格納メモリを有する場合などに有用である。）これらのサイズＳ（ｆ）は、何れか所与のファイルｆについて、ファイルｆの再生イベントが遅延又は中断される確率を最小化するよう選択される。
【００２１】
より具体的には、複数の再生が行われるとき、再生を実行するのに利用されるスケジューリング戦略を特定する必要がある。
【００２２】
このため、以下のスケジューリング戦略を考える。再生に関する何れかの装置ｄが、共有された通信チャネルを介しさらなるデータを取得しない場合、それが再生可能となることを中止するまでの時間であるＴ（ｄ）により示されるそれのリード（ｌｅａｄ）時間を決定する。その後、共有された通信チャネルは、すべてのリード時間の中で最小のリード時間Ｔ（ｄ）を有する装置ｄによる再生のため必要とされる次のデータウィンドウを優先的に送信する。これは、所望される最適性性質を有することが知られている、いわゆるＥａｒｌｉｅｓｙ−Ｄｅａｄｌｉｎｅ−Ｆｉｒｓｔスケジューリング戦略の一例である。（例えば、ＬｅＢｏｕｄｅｃ及びＴｈｉｒａｎによる“Ｎｅｔｗｏｒｋ  Ｃａｌｃｕｌｕｓ，ａ  ｔｈｏｅｒｙ  ｏｆ  ｄｅｔｅｒｍｉｎｉｓｔｉｃ  ｑｕｅｕｅｉｎｇ  ｓｙｓｔｅｍｓ  ｆｏｒ  ｔｈｅ  Ｉｎｔｅｒｎｅｔ”（Ｓｐｒｉｎｇｅｒ  Ｖｅｒｌａｇ，２００１）などを参照されたい。）
このようなスケジューリング戦略の下、何れかの装置に格納されているファイルｆからのさらなるデータＳ（ｆ）が、実際には、再生順序による最初のＳ（ｆ）データウィンドウであるファイルのプリフィックスであることを仮定する。Ｓ（ｆ）の値を十分に指定するため、何れかの装置がファイルｆにアクセスする周波数λ（ｆ）に関する情報が利用可能であると仮定する。
【００２３】
このとき、サイズＳ（ｆ）を以下のように決定する。上述されたＥａｒｌｉｅｓｙ−Ｄｅａｄｌｉｎｅ−Ｆｉｒｓｔスケジューリングポリシーの下、実行中のリクエストを中断しないようにするため、ファイルｆを再生するリクエストが遅延される必要がある周波数をｆａｉｌ（ｆ）により表す。ｆａｉｌ（ｆ）の最大値が、
【００２４】
【数２】
2008118623.tif 000004
の制約条件の下で最小化されるようにＳ（ｆ）を選択する。ただし、Ｍは、フェーズ１のエンド後のすべてのファイルについて所与の装置に残されているメモリスペースである。リクエストに関する標準的な仮定の下、ｆａｉｌ（ｆ）の値についてクローズド形式の表現は存在しないことに留意している。これらの評価をシミュレーションを介して、又は文献などにおいて利用可能な近似式を利用することを介して行うことが提案される。（特に、Ｅａｒｌｉｅｓｙ−Ｄｅａｄｌｉｎｅ−Ｆｉｒｓｔスケジューラのパフォーマンスのヘビートラフィック近似が利用可能であり、例えば、Ｐｅｔｅｒ  Ｋｅｙ、Ｌａｕｒｅｎｔ  Ｍａｓｓｏｕｌｉｅ及びＪｏｎａｔｈａｎ  Ｓｈａｐｉｒｏによる“Ｓｅｒｖｉｃｅ−Ｄｉｆｆｅｒｅｎｔｉａｔｉｏｎ  ｆｏｒ  Ｄｅｌａｙ−Ｓｅｎｓｉｔｉｖｅ  Ａｐｐｌｉｃａｔｉｏｎｓ：Ａｎ  Ｏｐｔｉｍｉｓａｔｉｏｎ−Ｂａｓｅｄ  Ａｐｐｒｏａｃｈ”（Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＦＩＰ  Ｐｅｒｆｏｍａｎｃｅ  ２００２  Ｃｏｎｆｅｒｅｎｃｅ）などを参照されたい。）
図４は、フェーズ１のデータがムービー（ファイル）１、２、３及び４について求めることが可能であり、Ｍがフェーズ２のデータについての予備のメモリスペースとなる所与の装置におけるメモリスペースを表す。
【００２５】
図５は、プリフィックスウィンドウとフェーズ１の符号化データのムービー毎のデータを示す。
【００２６】
図６は、本発明による再生中のプリフィックスウィンドウを示す。特に、当該ファイルに関して“フェーズ２データ”を構成するイニシャルプリフィックスと呼ばれる第１ウィンドウセットが存在する。このとき、再生開始後にダウンロードされた他のいくつかの連続するウィンドウが存在する。これらのうち、すでに再生されたデータと再生予定のデータとが区別される。再生予定のデータのデータ量は、装置がさらなるデータを取得しない場合、再生中断までの時間である“リード時間”を決定する。
【００２７】
上述した理想的なファイル配置戦略の新規性は、ｉ）信頼性と、ｉｉ）遅延した再生に関して測定されるＱｏＳとを併せて最適化するため、イレイジャ符号化データ配置を必ずしも必要でないデータ配置と組み合わせることである。
【００２８】
このアプローチの他の効果は、何れの装置からデータが抽出される必要があるか選択する際に、特別な考慮が不要であるということである。実際、十分多くの装置のランダムな選択が実行される。
【００２９】
本方法の他の重要な特徴は、再生中の格納管理に関するものである。ここでは、現在再生されていないファイルからのフェーズ２データを、現在再生中のファイルからのダウンロードされたデータにより上書きし、これを何れかの装置上で行うことを提案する。信頼性に影響を与えないように、フェーズ１データを上書きすることは許されない。アイドル期間中、装置は他の装置から再生中に上書きされたデータを復元することが可能である。これは、可能性のある最も低い優先度において実行される。（あるいは、もとのデータの割当ての何れかを上書きしない間、再生予定のデータをバッファリングすることに専用に使用されるメモリを節約するかもしれない。）
データの上書きは、効果的には、マルチメディアファイル（ムービーなど）の普及を利用することによって実行可能である。商業的にヒットした人気のあるムービーは上書きされず、よりコンフィデンシャルなムービーを上書きすることができる。
【００３０】
本方法の他の特徴は、各ファイルについて２つのパラメータｋ（ｆ）とＳ（ｆ）が決定されると、実際に配置が効果的にどのように行われるかに関する。以下のアプローチが提案される。共有された通信チャネルが、各ファイルを配信するのに利用される。所与のファイルｆの配信中、何れかの装置がサイズＳ（ｆ）の所望のプリフィックスを格納する。このプリフィックスを超えて、それはファイルｆのため維持する符号化データをウィンドウ毎に生成する。これは、ランダムにイレイジャコードをローカルに生成することによって実行することができる。
【００３１】
あるいは、本発明の他の実施例では、より効率的なアプローチは、イレイジャコードの第１ステージにより増大されたもとのファイルを配信することから構成され、装置に格納されているコードが実際にＲａｐｔｏｒコードとなるように、装置にこれらすべての入力からＬｕｂｙのＬＴ符号化スキームに従ってランダムコードを生成させる。（Ｍ．Ｌｕｂｙによる“Ｒａｐｔｏｒ  Ｆｏｒｗａｒｄ  Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ  Ｓｃｈｅｍｅ  ｆｏｒ  Ｏｂｊｅｃｔ  Ｄｅｌｉｖｅｒｙ（ＩＥＴＦ  ｄｒａｆｔ，２００６−６−２３）を参照されたい。）
より一般的には、本実施例について、ＬＴ、Ｒａｐｔｏｒコード又はＬＤＰＣなどの何れかのファウンテンコード（ｆｏｕｎｔａｉｎ  ｃｏｄｅ）が利用可能である。
【００３２】
興味のある１つの事例は、装置が飛行機の座席に割り当てられ、座席グループがＷＩＦＩを用いて通信する機内のエンターテイメントのものである。この事例では、最終的な目標は、何れかの座席からハイパフォーマンスなビデオ・オン・デマンドを可能にすることである。
【００３３】
他の興味のある事例は、ネットワーク全体においてコンテンツが当該ネットワーク上に分散されている分散格納システムのものである。このようなシステムは、コンテンツが複数の場所にあるだけでなく、それがローカルにアクセスされる必要がある新たな場所に一時的にコピーされるため、信頼性を付加する。
【００３４】
本明細書、実施例及び図面は、本発明による方法の完全な記載を提供する。本発明の多数の実施例が本発明の趣旨及び範囲から逸脱することなく可能であるため、本発明は、添付された請求項により規定される。
【図面の簡単な説明】
【００３５】
【図１】図１は、本発明による方法の各ステップを示す。
【図２】図２は、本発明によるファイル及びウィンドウを表す。
【図３】図３は、本発明によるウィンドウを示す。
【図４】図４は、本発明の方法による装置のメモリの状態を示す。
【図５】図５は、本発明によるプリフィックスウィンドウ及び符号化データのムービー毎のデータを表す。
【図６】図６は、本発明による再生中のプリフィックスウィンドウを示す。
【図１】
2008118623.tif 000005
【図２】
2008118623.tif 000006
【図３】
2008118623.tif 000007
【図４】
2008118623.tif 000008
【図５】
2008118623.tif 000009
【図６】
2008118623.tif 000010