JP5324766B2 - 分散記憶装置へのマルチメディアデータの割当て方法 - Google Patents

Description

本発明は、通信ネットワークにおけるコンテンツ配信の分野に関する。

本発明は、より詳細には、何れかの装置からの何れからのマルチメディアファイルの効率的なマルチメディア再生を可能にするため、マルチメディアファイルの各部分を分散化された記憶装置に割り当てる方法に関する。それは、共有された通信チャネルが利用可能であり、例えば、装置がＷＩＦＩインタフェースを有し、通信範囲内にあることを仮定している。共有された通信チャネルは、例えば、配信チャネルである可能性がある。

各装置がマルチメディアコンテンツにアクセスすることを可能にするよう協働する記憶装置の各種システムによると、従来技術では、信頼性は欠く装置の信頼性を向上させることによって実現され、グローバルにみなされるシステム全体については実現されていない。本発明は、システムにさらなる信頼性を与えるため、装置間で共有されている通信チャネルの存在に依拠する。装置の不具合に関して信頼性が考慮される。従来のシステムと異なり、劣化した再生体感の発生を最小限にするＱｏＳ（Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ）要求が、本発明では考慮される。
ＥＰ１６３３１１２Ａ Ｌｅｅ Ｊ Ｙ Ｂ ｅｔ ａｌ"Ｄｅｓｉｇｎ ａｎｄ ａｎａｌｙｓｉｓ ｏｆ ａ ｆａｕｌｔ−ｔｏｌｅｒａｎｔ ｍｅｃｈａｎｉｓｍ ｆｏｒ ａ ｓｅｒｖｅｒ−ｌｅｓｓ ｖｉｄｅｏ−ｏｎ−ｄｅｍａｎｄ ｓｙｓｔｅｍ"，Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｙｓｔｅｍｓ，２００２．Ｐｒｏｃｅｅｄｉｎｇｓ．Ｎｉｎｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ １７−２０ Ｄｅｃ．２００２，Ｐｉｓｃａｔａｗａｙ，ＮＪ，ＵＳＡ，ＩＥＥＥ，１７ Ｄｅｃｅｍｂｅｒ ２００２，ｐａｇｅｓ ４８９−４９４

本発明の課題は、装置の不具合が存在したときシステムの所定の信頼性保証を確保するため、各マルチメディアファイルの符号化部分を分散する方法を提案することである。

本発明の他の課題は、最大数のコンカレント装置が各マルチメディアファイルを同時再生することが可能となることを保証するため、マルチメディアファイルの追加的であるが、必ずしも符号化されていない各部分を装置に割り当てる方法を提案することである。これは、各マルチメディアファイルの普及に関する情報が利用可能である場合、このような普及に関する知識を利用するであろう。

本発明が解決しようとする技術的問題は、装置の一部に不具合が存在しても、共有された通信チャネルを利用して、装置が格納されているマルチメディアファイルを効率的に再生することが可能となるように、分散された記憶装置上のマルチメディアファイルからのデータを分散させる方法に関するものである。

本発明は、それのより広範な意味により請求項１に規定される。

効果的な実施例が、従属形式の請求項に与えられる。

再生のための最大のＱｏＳと共有される通信チャネルの最小限の使用によって、各装置へのデータの所望の配置を実現する方法が与えられる。

本発明の他の特徴は、
ｉ）再生処理中の共有された通信チャネルを利用するためのスキームと、
ｉｉ）再生処理中の装置上への格納を管理するスキームと、
を有する。

本発明によると、装置の不具合が存在したときシステムの所定の信頼性保証を確保するため、各マルチメディアファイルの符号化部分を分散する方法を提供することが可能である。

まず、各マルチメディアファイルが、各ウィンドウが与えられた期間における連続的再生のためのデータを表しているウィンドウに分割されると仮定する。

ファイルの各部分の所望の配置は、２つの主要なステップを有する。

第１ステップでは（以降、“フェーズ１”と呼ぶ）、各装置に配置される必要がある各ファイルの固定された部分が決定される。この部分は、特定のローカルな信頼性目標を充足するよう選択される。その詳細は、以下の通りである。

各装置の故障確率が知られており、それがｐにより表されると仮定する。さらに、あるファイルｆを消失する最大確率が与えられ、それがｐ（ｆ）により表されると仮定する。共有された通信チャネルを介し通信可能な装置の総数をｎにより表す。このとき、ファイルｆの“復号化ナンバー”ｋ（ｆ）を以下のように決定する。それは、パラメータ（ｎ，ｐ）による２項ランダム変数が整数ｎ−ｋを超える確率が、目標とする信頼性確率ｐ（ｆ）より大きくならないような最大の整数ｋとして選択される。すなわち、それは、以下の不等式が成り立つような｛０，．．．，ｎ｝の最大の整数である。

マルチメディアファイルは、所与の期間（１秒など）の連続的な再生のためのデータを表すウィンドウに分離されると仮定する。

ｋ（ｆ）が決定されると、マルチメディアファイルｆの指定された各ウィンドウに対して、ｎ個のシンボルが生成され、何れかｋ（ｆ）個のシンボルからファイルのもとのウィンドウが復元可能となるように、イレイジャコーディング（ｅｒａｓｕｒｅ ｃｏｄｉｎｇ）が用いられる。このとき、ファイルの各ウィンドウについて、ｎ個の対応するシンボルの１つが各装置に割り当てられる。このようなイレイジャコードは一般的なものであり、Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅｓ（ＬＤＰＣ）、Ｒａｐｔｏｒ Ｃｏｄｅｓ（ＲＣ）又はＲｅｅｄ−Ｓｏｌｏｍｏｎ（ＲＳ）コードなどのコードは、当該フェーズにおいて利用可能なイレイジャコードの一例である。当該処理は、ファイルｆの各ウィンドウについて繰り返され、その後、格納されるべきコレクションの各ファイルについて繰り返される。

図３は、本発明によると、各装置、各メディアファイル、各ウィンドウについて１つのシンボルが存在するウィンドウを有するファイルを表す。この図は、所与のファイル及び所与の装置に一意的なシンボルを表している。各ファイルｆの各ウィンドウは、当該ファイル及び当該ウィンドウに対してｋ（ｆ）個のシンボルの何れかのコレクションから再構成することができる。

各装置上に利用可能とされているメモリスペースが、ファイルの追加的部分を格納し、再生品質を最適化するのに利用される。ムービーの第１ウィンドウからスタートするウィンドウの連続するコレクションであるムービーのプリフィックスを格納することを選択する（図５参照）。この選択の理由は、プリフィックスが再生をスタートすることが要求されているということである。

第２ステップは（以降、“フェーズ２”と呼ぶ）、以下のように実行される。フェーズ１のエンドにおいて各装置に残されている格納メモリを決定する。各装置について、当該装置に格納されるファイルｆのサイズＳ（ｆ）を決定する。（簡単化のため、当該サイズは装置から独立したものであると仮定しているが、装置に依存したサイズを扱う拡張がされてもよく、それは各装置が異なる格納メモリを有する場合などに有用である。）これらのサイズＳ（ｆ）は、何れか所与のファイルｆについて、ファイルｆの再生イベントが遅延又は中断される確率を最小化するよう選択される。

より具体的には、複数の再生が行われるとき、再生を実行するのに利用されるスケジューリング戦略を特定する必要がある。

このため、以下のスケジューリング戦略を考える。再生に関する何れかの装置ｄが、共有された通信チャネルを介しさらなるデータを取得しない場合、それが再生可能となることを中止するまでの時間であるＴ（ｄ）により示されるそれのリード（ｌｅａｄ）時間を決定する。その後、共有された通信チャネルは、すべてのリード時間の中で最小のリード時間Ｔ（ｄ）を有する装置ｄによる再生のため必要とされる次のデータウィンドウを優先的に送信する。これは、所望される最適性性質を有することが知られている、いわゆるＥａｒｌｉｅｓｙ−Ｄｅａｄｌｉｎｅ−Ｆｉｒｓｔスケジューリング戦略の一例である。（例えば、ＬｅＢｏｕｄｅｃ及びＴｈｉｒａｎによる“Ｎｅｔｗｏｒｋ Ｃａｌｃｕｌｕｓ，ａ ｔｈｏｅｒｙ ｏｆ ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｑｕｅｕｅｉｎｇ ｓｙｓｔｅｍｓ ｆｏｒ ｔｈｅ Ｉｎｔｅｒｎｅｔ”（Ｓｐｒｉｎｇｅｒ Ｖｅｒｌａｇ，２００１）などを参照されたい。）
このようなスケジューリング戦略の下、何れかの装置に格納されているファイルｆからのさらなるデータＳ（ｆ）が、実際には、再生順序による最初のＳ（ｆ）データウィンドウであるファイルのプリフィックスであることを仮定する。Ｓ（ｆ）の値を十分に指定するため、何れかの装置がファイルｆにアクセスする周波数λ（ｆ）に関する情報が利用可能であると仮定する。

このとき、サイズＳ（ｆ）を以下のように決定する。上述されたＥａｒｌｉｅｓｙ−Ｄｅａｄｌｉｎｅ−Ｆｉｒｓｔスケジューリングポリシーの下、実行中のリクエストを中断しないようにするため、ファイルｆを再生するリクエストが遅延される必要がある周波数をｆａｉｌ（ｆ）により表す。ｆａｉｌ（ｆ）の最大値が、

の制約条件の下で最小化されるようにＳ（ｆ）を選択する。ただし、Ｍは、フェーズ１のエンド後のすべてのファイルについて所与の装置に残されているメモリスペースである。リクエストに関する標準的な仮定の下、ｆａｉｌ（ｆ）の値についてクローズド形式の表現は存在しないことに留意している。これらの評価をシミュレーションを介して、又は文献などにおいて利用可能な近似式を利用することを介して行うことが提案される。（特に、Ｅａｒｌｉｅｓｙ−Ｄｅａｄｌｉｎｅ−Ｆｉｒｓｔスケジューラのパフォーマンスのヘビートラフィック近似が利用可能であり、例えば、Ｐｅｔｅｒ Ｋｅｙ、Ｌａｕｒｅｎｔ Ｍａｓｓｏｕｌｉｅ及びＪｏｎａｔｈａｎ Ｓｈａｐｉｒｏによる“Ｓｅｒｖｉｃｅ−Ｄｉｆｆｅｒｅｎｔｉａｔｉｏｎ ｆｏｒ Ｄｅｌａｙ−Ｓｅｎｓｉｔｉｖｅ Ａｐｐｌｉｃａｔｉｏｎｓ：Ａｎ Ｏｐｔｉｍｉｓａｔｉｏｎ−Ｂａｓｅｄ Ａｐｐｒｏａｃｈ”（Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＦＩＰ Ｐｅｒｆｏｍａｎｃｅ ２００２ Ｃｏｎｆｅｒｅｎｃｅ）などを参照されたい。）
図４は、フェーズ１のデータがムービー（ファイル）１、２、３及び４について求めることが可能であり、Ｍがフェーズ２のデータについての予備のメモリスペースとなる所与の装置におけるメモリスペースを表す。

図５は、プリフィックスウィンドウとフェーズ１の符号化データのムービー毎のデータを示す。

図６は、本発明による再生中のプリフィックスウィンドウを示す。特に、当該ファイルに関して“フェーズ２データ”を構成するイニシャルプリフィックスと呼ばれる第１ウィンドウセットが存在する。このとき、再生開始後にダウンロードされた他のいくつかの連続するウィンドウが存在する。これらのうち、すでに再生されたデータと再生予定のデータとが区別される。再生予定のデータのデータ量は、装置がさらなるデータを取得しない場合、再生中断までの時間である“リード時間”を決定する。

上述した理想的なファイル配置戦略の新規性は、ｉ）信頼性と、ｉｉ）遅延した再生に関して測定されるＱｏＳとを併せて最適化するため、イレイジャ符号化データ配置を必ずしも必要でないデータ配置と組み合わせることである。

このアプローチの他の効果は、何れの装置からデータが抽出される必要があるか選択する際に、特別な考慮が不要であるということである。実際、十分多くの装置のランダムな選択が実行される。

本方法の他の重要な特徴は、再生中の格納管理に関するものである。ここでは、現在再生されていないファイルからのフェーズ２データを、現在再生中のファイルからのダウンロードされたデータにより上書きし、これを何れかの装置上で行うことを提案する。信頼性に影響を与えないように、フェーズ１データを上書きすることは許されない。アイドル期間中、装置は他の装置から再生中に上書きされたデータを復元することが可能である。これは、可能性のある最も低い優先度において実行される。（あるいは、もとのデータの割当ての何れかを上書きしない間、再生予定のデータをバッファリングすることに専用に使用されるメモリを節約するかもしれない。）
データの上書きは、効果的には、マルチメディアファイル（ムービーなど）の普及を利用することによって実行可能である。商業的にヒットした人気のあるムービーは上書きされず、よりコンフィデンシャルなムービーを上書きすることができる。

本方法の他の特徴は、各ファイルについて２つのパラメータｋ（ｆ）とＳ（ｆ）が決定されると、実際に配置が効果的にどのように行われるかに関する。以下のアプローチが提案される。共有された通信チャネルが、各ファイルを配信するのに利用される。所与のファイルｆの配信中、何れかの装置がサイズＳ（ｆ）の所望のプリフィックスを格納する。このプリフィックスを超えて、それはファイルｆのため維持する符号化データをウィンドウ毎に生成する。これは、ランダムにイレイジャコードをローカルに生成することによって実行することができる。

あるいは、本発明の他の実施例では、より効率的なアプローチは、イレイジャコードの第１ステージにより増大されたもとのファイルを配信することから構成され、装置に格納されているコードが実際にＲａｐｔｏｒコードとなるように、装置にこれらすべての入力からＬｕｂｙのＬＴ符号化スキームに従ってランダムコードを生成させる。（Ｍ．Ｌｕｂｙによる“Ｒａｐｔｏｒ Ｆｏｒｗａｒｄ Ｅｒｒｏｒ Ｃｏｒｒｅｃｔｉｏｎ Ｓｃｈｅｍｅ ｆｏｒ Ｏｂｊｅｃｔ Ｄｅｌｉｖｅｒｙ（ＩＥＴＦ ｄｒａｆｔ，２００６−６−２３）を参照されたい。）
より一般的には、本実施例について、ＬＴ、Ｒａｐｔｏｒコード又はＬＤＰＣなどの何れかのファウンテンコード（ｆｏｕｎｔａｉｎ ｃｏｄｅ）が利用可能である。

興味のある１つの事例は、装置が飛行機の座席に割り当てられ、座席グループがＷＩＦＩを用いて通信する機内のエンターテイメントのものである。この事例では、最終的な目標は、何れかの座席からハイパフォーマンスなビデオ・オン・デマンドを可能にすることである。

他の興味のある事例は、ネットワーク全体においてコンテンツが当該ネットワーク上に分散されている分散格納システムのものである。このようなシステムは、コンテンツが複数の場所にあるだけでなく、それがローカルにアクセスされる必要がある新たな場所に一時的にコピーされるため、信頼性を付加する。

本明細書、実施例及び図面は、本発明による方法の完全な記載を提供する。本発明の多数の実施例が本発明の趣旨及び範囲から逸脱することなく可能であるため、本発明は、添付された請求項により規定される。

図１は、本発明による方法の各ステップを示す。 図２は、本発明によるファイル及びウィンドウを表す。 図３は、本発明によるウィンドウを示す。 図４は、本発明の方法による装置のメモリの状態を示す。 図５は、本発明によるプリフィックスウィンドウ及び符号化データのムービー毎のデータを表す。 図６は、本発明による再生中のプリフィックスウィンドウを示す。

Claims (7)

1. 装置数が整数ｎである分散されている記憶装置にマルチメディアファイルの各部分を割り当てる方法であって、
   （ａ）所与の期間の連続的再生のためのデータを表すウィンドウに各マルチメディアファイルを分割するステップと、
   （ｂ）各マルチメディアファイルについて、前記ファイルの何れかのウィンドウが何れかｋ個の異なるシンボルから復元可能となるような数ｋ（ただし、ｋ＜ｎ）を決定するステップであって、前記シンボルはｋに従うイレイジャコーディングを利用して生成される、前記決定するステップと、
   （ｃ）前記マルチメディアファイルのそれぞれの各ウィンドウについて、前記イレイジャコーディングを利用してｎ個の異なるシンボルを生成し、前記ｎ個の異なるシンボルを前記記憶装置に格納するステップであって、各記憶装置に１つのシンボルを格納する、前記格納するステップと、
   （ｄ）前記１以上のマルチメディアファイルのそれぞれの少なくとも第１ウィンドウによって、前記ステップ（ａ），（ｂ）及び（ｃ）の後に各装置に残された格納メモリを部分的又は完全に充填するステップであって、前記少なくとも第１ウィンドウはイレイジャコーディングを利用して符号化されず、前記少なくとも第１ウィンドウは前記１以上のマルチメディアファイルのそれぞれの再生を開始するのに必要とされるプリフィックスを表す、前記充填するステップと、
   を有する方法。
2. 各ファイルを配信するステップをさらに有する、請求項１記載の方法。
3. 記憶装置に格納されるマルチメディアファイルの数ｋは、マルチメディアファイルの異なるシンボルを格納する記憶装置の失敗の確率に従って選択される、請求項１又は２記載の方法。
4. 再生されていないファイルからのステップ（ｄ）に対応するデータが、再生されているファイルからのダウンロードされたデータによって上書きされる、請求項１乃至３何れか一項記載の方法。
5. ファイルの配信中、何れかの装置が格納されるファイルのサイズに等しいサイズを有する所望のプリフィックスを格納し、
   前記プリフィックスを過ぎて、格納される前記ファイルについて維持する符号化データをウィンドウ毎に生成する、請求項２記載の方法。
6. イレイジャコードにより増大されたもとのファイルが配信され、
   前記装置が、前記配信されたファイルを用いてランダムコードを生成する、請求項２記載の方法。
7. ステップ（ｄ）が、前記マルチメディアファイルの普及の指標を用いて実行される、請求項１乃至６何れか一項記載の方法。

Images