(57)【特許請求の範囲】
【請求項１】
複数のバージョンが利用可能であり各バージョンが異なる品質を有するマルチメディアアイテムを表す、マルチメディアアイテムのセグメントの中間キャッシングを管理するためのキャッシュマネージャ（１００）において、
前記キャッシュマネージャ（１００）は、大容量マルチメディア記憶装置からキャッシュメモリ（１５０）への前記マルチメディアアイテムのセグメントのプリフェッチを制御するように構成されたおよび前記キャッシュメモリ（１５０）からの前記マルチメディアアイテムのセグメントの削除を制御するように構成されたコントローラ（１０１、１０２）を備え、現在消費されているセグメントに続き及び現在消費されている品質レベルに近い品質レベルを有するセグメントである、近い将来に要求される見込みが高いマルチメディアアイテムのセグメントをプリフェッチし、近い将来に要求される見込みが低い前記マルチメディアアイテムのセグメントを除去するために、前記コントローラ（１０１、１０２）が、前記マルチメディアアイテムの複数のバージョンのセグメント間の時間的および品質関連のセグメント相互関係を示す情報（１３１）に応答することを特徴とする、
キャッシュマネージャ（１００）。
【請求項２】
前記マルチメディアアイテムに関連する１つまたは複数のマルチメディアプレゼンテーションディスクリプションファイルから前記情報（１３１）を抽出する手段を備える、
請求項１に記載のキャッシュマネージャ（１００）。
【請求項３】
前記コントローラ（１０１、１０２）が、スタートアップにおいて前記マルチメディアアイテムの人気度情報に応答するようにさらに構成された、
請求項１に記載のキャッシュマネージャ（１００）。
【請求項４】
前記コントローラが、以下、
ユーザプロファイル情報（１３２）、
セグメント人気度情報、
ユーザ履歴情報（１３３）、
セッション履歴情報（１３４）、
コンテンツ履歴情報（１３５）、
コンテンツ所有者／製作者によって供給されたコンテンツ情報、
マルチメディアサーバと前記キャッシュメモリの間のネットワーク負荷（１３６）、
前記キャッシュメモリとエンドユーザ機器の間のネットワーク負荷（１３６）、
クライアント側アルゴリズム情報
のうちの１つまたは複数に応答するようにさらに構成された、
請求項１に記載のキャッシュマネージャ（１００）。
【請求項５】
前記時間的および品質関連のセグメント相互関係を機械学習する手段をさらに備えた、
請求項１に記載のキャッシュマネージャ（１００）。
【請求項６】
前記コントローラが、前記キャッシュメモリ（１５０）に記憶されたセグメントに対して値を保持および／または割り当てるようにさらに構成され、各値が、前記時間的および品質関連のセグメント相互関係を考慮した、マルチメディアアイテムの１つのバージョンの対応するセグメントが要求される見込みを表す、
請求項１に記載のキャッシュマネージャ（１００）。
【請求項７】
第１のキャッシュノードから第２のキャッシュノードにマルチメディアセッションのリダイレクトを指示するように構成されたリダイレクト手段（４０１）をさらに備え、前記リダイレクト手段（４０１）が少なくとも、クライアントを１つまたは複数のキャッシュノードにマップするネットワークトポロジー情報（４０３）に応答する、
請求項１に記載のキャッシュマネージャ（１００）。
【請求項８】
複数のバージョンが利用可能であり各バージョンが異なる品質を有するマルチメディアアイテムを表す、マルチメディアアイテムのセグメントの中間キャッシングを管理する方法において、
現在消費されているセグメントに続き及び現在消費されている品質レベルに近い品質レベルを有するセグメントである、近い将来に要求される見込みが高いマルチメディアアイテムのマルチメディアセグメントをプリフェッチし、近い将来に要求される見込みが低い前記マルチメディアアイテムのセグメントを除去するために、前記マルチメディアアイテムの複数のバージョンのセグメント間の時間的および品質関連のセグメント相互関係を示す情報（１３１）に応答して、大容量マルチメディア記憶装置からキャッシュメモリ（１５０）への前記マルチメディアアイテムのセグメントのプリフェッチを制御しおよび前記キャッシュメモリ（１５０）からの前記マルチメディアアイテムのセグメントの削除を制御するステップを含むことを特徴とする、
方法。
【請求項９】
マルチメディアセッションを第１のキャッシュノードから第２のキャッシュノードにリダイレクトするステップをさらに含み、それによって少なくとも、クライアントを１つまたは複数のキャッシュノードにマップするネットワークトポロジー情報（４０３）を使用する、
請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、複数の品質にて利用可能なセグメント化されたマルチメディアアイテム、たとえば異なるバージョンにおいて異なる分解能で符号化されたＨＴＴＰ適応型ストリーミング（ＨＴＴＰ  Ａｄａｐｔｉｖｅ  Ｓｔｒｅａｍｉｎｇ：ＨＡＳ）ビデオセグメントのキャッシングに関する。本発明は具体的には、マルチメディアサーバとマルチメディアセグメントを要求するクライアントとの間の比較的小さな中間キャッシュのキャッシュヒット率を改善することを試みる。
【背景技術】
【０００２】
既存のハイパーテキスト転送プロトコル（ＨＴＴＰ）キャッシュは、ＨＴＴＰウェブコンテンツと同様なやり方でセグメント化されたビデオを取り扱う。キャッシュメモリからのセグメントの削除、またはキャッシュメモリに記憶するためのコンテンツサーバからのセグメントのプリフェッチのために、キャッシュマネージャによって用いられる通常のアルゴリズムは、最長時間未使用（ｌｅａｓｔ−ｒｅｃｅｎｔｌｙ−ｕｓｅｄ：ＬＲＵ）または最低使用頻度（ｌｅａｓｔ−ｆｒｅｑｕｅｎｔｌｙ−ｕｓｅｄ：ＬＦＵ）機構に基づく。
【０００３】
複数の品質にて利用可能なセグメント化されたマルチメディアに適用されるときのＬＲＵまたはＬＦＵをベースとするキャッシュ管理の主な弱点は、セグメント間の時間依存性および品質ベースの依存性が利用されないことにあり、結果としてキャッシュヒット率は最適化されない。
【０００４】
「Ｖｉｄｅｏ  Ｏｐｔｉｍｉｚｅｄ  Ｍｅｄｉａ  Ｓｔｒｅａｍｅｒ  ｗｉｔｈ  Ｃａｃｈｅ  Ｍａｎａｇｅｍｅｎｔ」という名称の欧州特許第０７０２４９１号は、大容量記憶装置とキャッシュバッファの間の転送をスケジュールするために、ビデオセグメント間の時間依存性を考慮に入れた改良されたビデオキャッシュについて述べている。したがってキャッシュ効率を改善するために、ビデオセグメントをプリフェッチするのに時間的に順序付けられたセグメントを有するビデオストリームの性質が用いられる。
【０００５】
しかし、欧州特許第０７０２４９１号は、単一のビデオアイテムの複数の品質の利用可能性と、たとえばリソースの利用可能性に応じてこれらの品質の間をクライアントが動的に切り換える可能性とを考慮していない。結果として欧州特許第０７０２４９１号で開示されたキャッシュアルゴリズムでは、マルチメディアアイテムを様々な品質で要求することができるとき、および要求される品質がたとえばビデオのＨＴＴＰ適応型ストリーミング（ＨＡＳ）などによるマルチメディアの消費時に動的に変わり得るときには、キャッシュヒット率は最適化されない。
【０００６】
たとえばアクセスノードにおけるＨＴＴＰキャッシュなど、特には、限られた容量を有する中間キャッシュノードの場合、キャッシュアルゴリズムの改善は、キャッシュヒット率、結果的にはこのようなキャッシュを展開したときの便益費用比率を大幅に向上させる可能性がある。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】欧州特許第０７０２４９１号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００８】
したがって本発明の目的は、既存の解決策の上述の弱点を解決するキャッシュマネージャおよび対応するキャッシュ管理方法を開示することである。より具体的には、複数の品質にて利用可能なセグメント化されたマルチメディアに対して改善されたキャッシュヒット率を有するキャッシュマネージャおよび対応するキャッシュ管理方法を開示することが目的である。
【課題を解決するための手段】
【０００９】
本発明によれば、上記に定められた目的は、複数のバージョンが利用可能であり各バージョンが異なる品質を有するマルチメディアアイテムを表す、マルチメディアアイテムのセグメントの中間キャッシングを管理するためのキャッシュマネージャによって実現され、キャッシュマネージャは、マルチメディアアイテムのキャッシュメモリへのセグメントのプリフェッチおよびマルチメディアアイテムのキャッシュメモリからのセグメントの削除を制御する制御手段を備え、これらの制御手段は、マルチメディアアイテムの複数のバージョンのセグメント間の時間的および品質関連のセグメント相互関係を示す情報に応答する。このようなキャッシュマネージャは、請求項１によって定義される。
【００１０】
したがって、本発明の基礎をなす基本的概念は、時間的および品質関連の両方のセグメント相互関係についての特定の知識を利用して、キャッシュ削除およびプリフェッチの効率を改善することである。実際、ユーザがたとえばある時点で品質レベルＱおよびセグメント識別子ＩＤを有するセグメントをダウンロードすることによってビデオを視聴しているときには、ユーザがＱに近い品質レベルを有するセグメントＩＤ＋１を見ることに興味をもつ見込みが比較的高い。より一般的には現在消費されているマルチメディアセグメントのＩＤに続くＩＤを有するセグメントがユーザによって要求される見込みが、現在消費されているセグメントから時間的に離れたセグメントより高い。さらに将来要求されるマルチメディアセグメントの品質レベルは、現在消費されている品質レベルに近くなる見込みが高い。したがって、セグメント間の時間的および品質依存の関係の組合せは、近い将来に要求される見込みが高いマルチメディアセグメントをプリフェッチし、近い将来に要求される見込みが低いセグメントを除去することを可能にする。これは、明らかに結果として改善されたキャッシュヒット率を生じさせ、すなわち要求されたセグメントがキャッシュ内で利用可能となる率が高くなる。
【００１１】
時間的および品質関連のセグメント相互関係は、キャッシュヒット率を最適化するために、人気度、最後の使用の時刻および日付などの従来の基準と組み合わせることができることに留意されたい。以下で述べられるように、時間的および品質関連のセグメント相互関係の知識はさらに、キャッシュヒット率をさらに最適化するために、ユーザプロファイル情報、履歴情報、およびネットワーク負荷情報などのあまり従来にない基準によって補うことができる。さらにシステムは、コンテンツ自体、たとえばスポーツの試合、またはトークショーに結び付けられた情報を用いることができるが、典型的な跳躍時点、たとえばコマーシャルの始まり、インタビューの終わりなどを示す情報も用いることができる。
【００１２】
任意選択で、請求項２によって定義されるように、本発明によるキャッシュマネージャは、マルチメディアアイテムに関連する１つまたは複数のマルチメディアプレゼンテーションディスクリプションファイル、たとえばマニフェストファイルから、時間的および品質関連のセグメント相互関係情報を抽出する手段を備える。
【００１３】
実際、適応型ストリーミング技術を用いたときには、セグメント間の関係は通常、いわゆるマルチメディアプレゼンテーションディスクリプション（ＭＰＤ）ファイル、たとえばマニフェストファイル内に記述される。したがってこのマニフェストまたはＭＰＤファイルは、ＨＴＴＰ適応型ストリーミングセッションにおけるセグメント間の関係についての知識を確立するために、本発明によるキャッシュマネージャによって利用することができる。
【００１４】
さらに任意選択で、請求項３によって定義されるように、制御手段は、スタートアップにおいてマルチメディアアイテムの人気度情報に応答するように構成することができる。
【００１５】
実際、たとえばムービーの始まりにおいては、アクティブなセッションおよびセグメント相互関係についての利用可能な情報は少ない。したがってセグメントのプリフェッチおよび削除を制御するために、この時点では一般的な人気度情報を考慮に入れることができる。
【００１６】
請求項４によって定義される他の任意選択の態様によれば、セグメントのプリフェッチおよび削除を制御する手段は、以下のうちの１つまたは複数に応答するように構成することができる：
−  ユーザプロファイル情報
−  セグメント人気度情報
−  ユーザ履歴情報
−  セッション履歴情報
−  コンテンツ履歴情報
−  コンテンツ所有者／製作者によって供給されたコンテンツ情報
−  マルチメディアサーバと前記キャッシュメモリの間のネットワーク負荷
−  前記キャッシュメモリとエンドユーザ機器の間のネットワーク負荷
−  クライアント側アルゴリズム情報
【００１７】
したがって、追加情報は、セグメントプリフェッチおよび削除アルゴリズムによって考慮に入れることができる。追加の情報は、たとえば所与のユーザに対して利用可能な通常の帯域幅を表すユーザプロファイル、所与のセグメントが要求された回数を示すセグメント人気度情報、たとえば所与のユーザのザッピング行動を表すユーザ履歴、たとえばユーザが所与のマルチメディアアイテムの消費を終了する典型的な時点を表すコンテンツ履歴、たとえば所与のセッションにおいて要求される典型的な（１つまたは複数の）品質レベルを表すセッション履歴、マルチメディアサーバとキャッシュの間のネットワークの部分および／またはキャッシュとクライアントの間のネットワークの部分の負荷または利用可能なリソース、および特定のクライアント側アルゴリズム方策についての知識とすることができる。後者はたとえばクライアント側バッファについての情報を含むことができる。スムースストリーミングのクライアントは、たとえばビデオを見るためのそのバッファ充填レベルが閾値より低いことを認識したときは、中断を避けるためにできる限り低い品質に自動的に切り換えることができる。したがって対応する低い品質セグメントをキャッシュ内に保持することは、このようなクライアントに対してキャッシュヒット率を最適化する有用な方策となり得る。サーバとキャッシュの間のネットワーク部分における負荷または利用可能なリソースについての知識は、どれだけ積極的にセグメントをプリフェッチするかを決定するために利用することができる。
【００１８】
セグメントのプリフェッチおよびセグメントの削除を制御するために、本発明によるキャッシュマネージャは、時間的および品質依存のセグメント相互関係を考慮するだけでなく、キャッシュヒット率、およびマルチメディアキャッシュ配備の費用便益比率をさらに最適化するために、上述の情報タイプの任意の組合せを利用することができる。
【００１９】
請求項５によってさらに規定されるように、本発明によるキャッシュマネージャは、時間的および品質関連のセグメント相互関係を機械学習する手段をさらに備えることができる。
【００２０】
したがって、どのセグメントをキャッシュから除去するか、およびどのセグメントを大容量記憶装置からプリフェッチするかを決定するのに用いられるソフトウェア／ハードウェアは、配備された環境にそれ自体を動的に適応させる機械学習アルゴリズムに基づくものとすることができる。その利点は、既存のクライアントの更新、およびネットワーク内の新しいクライアントの挙動を学習できることである。このようにして中間キャッシュノードのための過大なソフトウェアアップグレードが避けられる。
【００２１】
請求項６によって定義される、本発明によるキャッシュマネージャの一実施形態では、セグメントのプリフェッチおよび削除を制御する手段は、キャッシュメモリに記憶されたセグメントに対して値を保持および／または割り当てるようにさらに構成され、各値は、時間的および品質関連のセグメント相互関係を考慮した、マルチメディアアイテムの１つのバージョンの対応するセグメントが要求される見込みを表す。
【００２２】
実際、本発明を実施する簡単なやり方は、マルチメディアアイテムの各バージョンにおける各セグメントに対して値を保持することにある。これらの値は、セグメントが要求される見込み、およびその結果としてまたキャッシュ内にセグメントを保つ重要性を表す。各値は、同じマルチメディアアイテムの考慮中のセグメントと、最近要求されたセグメントとの間の時間的関係および品質の関係の関数として決定される。最後の追加情報は、値を決定／微調整するために利用することができる。値は、１つまたは複数のセグメントが要求されるたびに更新される。
【００２３】
請求項７によって定義される、本発明の他の有利な態様によればキャッシュマネージャは、第１のキャッシュノードから第２のキャッシュノードにマルチメディアセッションのリダイレクトを指示するように構成されたリダイレクト手段を備えることができ、リダイレクト手段は少なくとも、クライアントを１つまたは複数のキャッシュノードにマップするネットワークトポロジー情報に応答する。
【００２４】
したがって、本発明によるプリフェッチおよびセグメント削除の決定の最適化に用いられる情報はさらに、マルチメディアセッション、たとえばクライアントによるビデオストリームセッションを、ネットワーク内の他のキャッシュノードにリダイレクトするために利用することができる。たとえば同じマルチメディアセッションがすでに他のキャッシュノードによって他のクライアントに送られている状況において、これは有利となり得て、最終的にはわずかな時間的遅延ですむ。キャッシュノードがマルチメディアセッションを処理しており、識別子ＩＤおよび品質レベルＱを有するセグメントを見るときは、そのセッションにおいて識別子ＩＤ＋１および品質レベルＱを有するセグメントに対する要求も発行される見込みが高くなる。したがって、このセッション要求を、すでに同じコンテンツに対するセッションを処理しており、かつセグメント識別子ＩＤ＋１および品質レベルＱを見ている、セッションを処理するキャッシュノードにリダイレクトすることが有利となり得る。
【００２５】
どのキャッシュノードがセッションを処理すべきかを決定するために、従来技術では通常、トポロジー情報が用いられ、ＨＡＳセッションについての専用の情報は考慮されない。結果として従来は、セッションは、近くのキャッシュノードにリダイレクトされる。マルチメディアセッションを効率的にリダイレクトできるように本発明によるキャッシュマネージャは、ネットワークトポロジー情報、たとえばクライアントを近くにある１つまたはいくつかのキャッシュノードにマップしたリストを用いることができる。キャッシュノード、すなわち要求を受けるキャッシュノードおよびセッションがそこにリダイレクトされることになるキャッシュノードの、実際の負荷などの追加情報、ならびに異なるキャッシュノードによって処理されるセッションについての、これらのセッションの時間および品質情報を含む特定の情報は、リダイレクトアルゴリズムの効率を改善するようになる。追加情報としては、セッションの予想される人気度についての事前の知識を含むことができる。ネットワークトポロジー情報、ならびに負荷および異なるキャッシュノードによって処理されるセッションについての最後の追加情報を共有するために、この情報をキャッシュノード間で通信できるようにするプロトコル、またはこの情報を中央プラットフォームの仲介を通して分配できるようにするプロトコルが実装されなければならない。
【００２６】
さらに本発明によるマルチメディアセッションのリダイレクトはセグメントレベルで制御することができ、すなわちセッションの１つまたは複数のセグメントを他のキャッシュノードを通して配信することができ、またはセッションレベルで制御することができ、すなわちマルチメディアセッション全体を他のキャッシュノードにリダイレクトされることに留意されたい。
【００２７】
請求項１によって定義されるキャッシュマネージャに加えて、本発明はまた、複数のバージョンが利用可能であり各バージョンは異なる品質を有するマルチメディアアイテムを表す、マルチメディアアイテムのセグメントの中間キャッシングを管理するための対応する方法に関し、方法は、マルチメディアアイテムの複数のバージョンのセグメント間の時間的および品質関連のセグメント相互関係を示す情報に応答して、マルチメディアアイテムのキャッシュメモリへのセグメントのプリフェッチおよびマルチメディアアイテムのキャッシュメモリからのセグメントの削除を制御するステップを含む。この対応する方法は請求項８によって定義される。
【００２８】
請求項９によって示されるように、本発明による方法は任意選択で、マルチメディアセッションを第１のキャッシュノードから第２のキャッシュノードにリダイレクトするステップを含むことができ、それによって少なくとも、クライアントを１つまたは複数のキャッシュノードにマップするネットワークトポロジー情報を使用する。
【図面の簡単な説明】
【００２９】
【図１】本発明によるキャッシュマネージャ１００の実施形態の機能ブロック図である。
【図２】複数の品質Ｑにて利用可能なマルチメディアアイテムがダウンロードされる、単一のセッションがアクティブであるときの、本発明によるキャッシュマネージャの第２の実施形態の動作を示す図である。
【図３】複数の品質Ｑにて利用可能なマルチメディアアイテムがダウンロードされる、２つのセッションがアクティブであるときの、本発明によるキャッシュマネージャの第３の実施形態の動作を示す図である。
【図４】リダイレクト構成要素を有する、本発明によるキャッシュマネージャの一実施形態の機能ブロック図である。
【発明を実施するための形態】
【００３０】
図１は、セグメント記憶装置またはキャッシュ１５０、セグメントマネージャ１００、および基礎となる伝送レイヤ１６０を示す。
【００３１】
セグメント記憶装置１５０は、いくつかのマルチメディアセグメントを含んだ簡単なメモリ構成要素である。セグメントは、このメモリ構成要素から要求され得、メモリ構成要素に注入され得る。さらにメモリ構成要素は、監視されることが可能であり、利用可能なセグメントについての情報を返すことになる。
【００３２】
セグメントマネージャ１００は、本発明によるキャッシュマネージャの第１の実施形態を表す。セグメントマネージャ１００はクライアントからのセグメントの要求に答える役割をもち、セグメントをプリフェッチしセグメント記憶装置１５０に挿入するためのプリフェッチ構成要素１０２と、セグメント記憶装置１５０からセグメントを削除または除去するための削除構成要素１０１とを含む。さらにセグメントマネージャ１００はまた、セグメントがセグメント記憶装置１５０内に存在しないときは、これらのセグメントを遠隔の構成要素、大容量マルチメディア記憶装置から要求する役割をもち、そうすると決定したときはこれらのセグメントをセグメント記憶装置１５０に記憶する可能性を有することになる。最後にセグメントマネージャ１５０はまた、マルチメディアトラフィック上に関連データを保持する役割をもつ様々な情報構成要素１０３内で調べた、要求についての情報を記憶する。これらの情報構成要素１０３は、セグメントマネージャ１００の内部または外部にあるものとすることができる。
【００３３】
情報構成要素１０３には、本質的に、セグメント削除およびプリフェッチアルゴリズムが決定を行うときの助けとするためのグローバルおよびローカルな情報を捕捉する多様な構成要素を含む。図１に示される例は、どのように所与のセッションのセグメントが時間的および品質的にリンクされるかについての情報を有する（１つまたは複数の）マニフェストファイル１３１、ユーザプロファイル情報１３２、特定のユーザについてのユーザ履歴情報１３３、特定のセッションについてのセッション履歴情報１３４、特定のコンテンツが通常どのように消費されるかについてのコンテンツ履歴情報１３５、および監視されるネットワーク負荷についての情報１３６を含む。しかし、これは、非網羅的なリストであり、本発明の代替実施形態の削除およびプリフェッチアルゴリズムでは、他の追加情報を用いることができる。
【００３４】
削除構成要素１０１は、どのセグメントがセグメントキャッシュ１５０から除去されるべきかを決定する役割をもつ。これを行うために削除構成要素１０１は、情報構成要素１０３内で利用可能な様々なタイプの情報１３１、１３２、１３３、１３４、１３５、および１３６を利用する。
【００３５】
プリフェッチ構成要素１０２は、どのセグメントをマルチメディア大容量記憶装置からプリフェッチするかを決定する役割をもつ。これを行うためにプリフェッチ構成要素１０２も、情報構成要素１０３内で利用可能な様々なタイプの情報１３１、１３２、１３３、１３４、１３５、および１３６を利用する。
【００３６】
要求受信器１６１、要求送信器１６２、応答受信器１６３、および応答送信器１６４は、外界とのメッセージインターフェースを構成する。基本的にはこれらは、伝送レイヤ１６０が、クライアントおよび大容量記憶装置などのネットワーク内の他の構成要素と通信するのを可能にする。
【００３７】
本発明は、ＨＴＴＰ適応型ストリーミング（ＨＡＳ）とスケーラブルビデオ符号化（Ｓｃａｌａｂｌｅ  Ｖｉｄｅｏ  Ｃｏｄｉｎｇ：ＳＶＣ）を組み合わせたシステムに用いることができることに留意されたい。これはたとえば、ＭＰＥＧ  ＤＡＳＨ（（Ｄｙｎａｍｉｃ  Ａｄａｐｔｉｖｅ  Ｓｔｒｅａｍｉｎｇ  ｏｆ  ＨＴＴＰ）ＨＴＴＰの動的適応型ストリーミング）規格仕様において当てはまる。ＳＶＣは、ビデオファイルの異なるバージョンを階層構造化されたレイヤに符号化する。基本レイヤは、ビデオファイルの低い品質のバージョンを表す。基本レイヤ上には、ビデオファイルのより高い品質のバージョンを発生するために拡張レイヤが構築される。このようなシステムでは、本発明によるキャッシュマネージャによってもたらされる恩恵はより大きくなり、なぜなら低位のレイヤたとえば基本レイヤは、セグメントに対して常に必要となるからである。より高い拡張レイヤはキャッシュから除去することができるが、基本レイヤはビデオファイルのすべてのバージョンに必要であるので保持され得る。
【００３８】
図２および図３は、本発明の原理により動作するキャッシュマネージャの第２の実施形態の動作を示す。この第２の実施形態では、各品質レベル（縦軸Ｑ）において、ビデオファイルの各セグメント（横軸Ｔ）に対して値が保持される。図２は、単一のユーザが所与の時点において特定のセグメント、すなわち図２の網掛けされたセグメントをダウンロードする状況を示す。横方向の破線は、ユーザがダウンロードすると想定されるビデオファイルの連続するセグメントを示す。ユーザが網掛けされたセグメントをダウンロードする時点で、本発明によるキャッシュマネージャは、他のセグメントに値を割り当てる。これらの値は、時間的および品質関連のセグメント相互関係に依存し、セグメントがユーザによって要求される見込みに対する尺度を表す。このような値をセグメントに割り当てる簡単な方策は以下の通りとすることができる：
−  現在ダウンロードされているセグメントに続く、同じ品質レベルの最初の３つのセグメントは３だけ増加される
−  それに続く同じ品質レベルの３つのセグメントは２だけ増加される
−  それに続く同じ品質レベルの３つのセグメントは１だけ増加される
−  品質レベル差１と、現在ダウンロードされているセグメント識別子から最大でも５だけ異なるセグメント識別子とを有するセグメントは２だけ増加される
−  それに続く品質レベル差が１の４つのセグメントは１だけ増加される
−  品質レベル差２と、現在ダウンロードされているセグメント識別子から最大でも５だけ異なるセグメント識別子とを有するセグメントは１だけ増加される
【００３９】
網掛けされたセグメントをダウンロードする前はすべてのセグメントの値は０であったと仮定すると、図２は、網掛けされたセグメントをダウンロードした後の異なる品質レベルにおけるセグメントの値を表す。
【００４０】
図３は、第１のユーザが第１の網掛けされたセグメントをダウンロードし、第２のユーザが第２の網掛けされたセグメントをダウンロードする状況における同じ実施形態を示す。第２のユーザによってダウンロードされるセグメントは、後のセグメントに相当し、第２のユーザは、この後のセグメントを第１のユーザが見ているのより高い品質レベルでダウンロードする。この場合もまた、第１および第２のユーザが網掛けされたセグメントをダウンロードする前ではすべてのセグメントの値は、０であったと仮定すると、図３は、ユーザおよびユーザ２がそれらのそれぞれの所望の品質においてそれらのそれぞれのセグメントをダウンロードした後の、異なる品質レベルにおけるセグメントの値を表す。図３の破線はさらに、第１および第２のユーザによってダウンロードされることになるセグメントの想定されるシーケンスを表す。
【００４１】
上記で説明された値の割当ては、すべてのアクティブなセッションに対して繰り返され、セグメントに割り当てられる最終値は正規化される。本発明によるキャッシュマネージャの削除構成要素およびプリフェッチ構成要素は、キャッシュからのセグメントの削除およびキャッシュへのセグメントのプリフェッチに対するそれらの決定を、これらの値に基づいて行うことになる。高い値を有するセグメントは、削除構成要素によってキャッシュから除去される見込みが最も低い。キャッシュ内にまだ存在しない高い値を有するセグメントは、プリフェッチ構成要素によって大容量記憶装置からプリフェッチされることが見込まれる。
【００４２】
やはりセグメントに対する重要度値を保持する代替実施形態では、キャッシュマネージャは、キャッシュ内にある特定のセグメントに値を割り当てる。すべてのセグメントは同じ持続時間を有すると仮定する。セグメントがキャッシュから除去されるときは、キャッシュマネージャ内の削除構成要素は、最低値を有するものを選択する。アルゴリズムではＳ（ｍ）は、ムービーｍのすべてのセグメントの集合を表す。各セグメントはセグメントが通常ダウンロードされる順序を表す整数値ｓによって識別され、Ｑ（ｓ）はセグメントｓに対応する品質を表す。セグメントのキャッシュ重要度は、キャッシュ内にこのセグメントを保持することがどの程度重要であるかを表す値である。第３の実施形態ではこれらの値を割り当てる方式は次の通りである：
ムービーｍを視聴しているすべてのアクティブなユーザｕに対して｛
Ｓ（ｍ）に属するすべてのｉに対して、ただしｉ＞ｓ｛
ｉ＿ｉｍｐｏｒｔａｎｃｅ＝ｉ＿ｉｍｐｏｒｔａｎｃｅ＋ｆ（ｉ，ｓ）；
｝
｝
ここで：
ｍは、ユーザｕによって視聴されているムービーを表し、
ｓは、ユーザｕによって視聴されているムービーｍのセグメントの識別子を表し、
ｑは、セグメントｓの品質を表し、
ｉは、整数インデックスを表し、
ｉ＿ｉｍｐｏｒｔａｎｃｅは、識別子ｉを有するセグメントの重要度値を表し、
ｆ（ｉ，ｓ）は、ユーザｕが現在同じムービーｍのセグメントｓを視聴していることが分かったときに、セグメントｉに対する重要度における増加を計算するために用いられる関数である。
【００４３】
例示の関数ｆ（ｉ，ｓ）は、次式とすることができる：
【００４４】
【数１】
0005747090.tif 000002
この関数ｆ（ｉ，ｓ）は、現在視聴されているセグメントに時間的に近いセグメントに、より高い重要度を割り当てる。この関数ｆ（ｉ，ｓ）はまた、時間的に近いセグメントに対して予想される品質は高いと推定し、時間的に遠いセグメントは、利用可能な品質バージョンに対してより等しい重要度を有することになると仮定することによって、変化する品質を可能にする。
【００４５】
この第３の実施形態では、ビデオストリームに属する最初のセグメントのために、キャッシュメモリの一部を予約しておくことが好ましい。これにより、前のアルゴリズムが用いられたときに、キャッシュ内にある見込みがより低くなる、ムービーの始まりにおけるセグメントが利用可能に保たれることが確実になり得る。
【００４６】
本発明によるキャッシュマネージャの第４の実施形態では、現在視聴されているセグメントに時間においてまたは品質において近いセグメントを要求する見込みを学習するために、学習機構が用いられる。１つの妥当な技法は、様々な履歴上の要求経路に対してマルコフ連鎖を訓練することにある。訓練セットが与えられると、セグメントＱ（ｓ＋１）を要求する確率は、Ｐ（Ｑ（ｓ＋１）｜Ｑ（ｓ），Ｑ（ｓ−１），…，Ｑ（１））と推定することができ、これは近い将来（ｓ＋１）でのＨＴＴＰ適応型ストリーミングによる要求品質は、現在の品質に依存するだけでなく、履歴上の要求品質にも依存すると仮定している。
【００４７】
計算を簡単にし、かつデータの希薄さを避けるために、Ｐ（Ｑ（ｓ＋１）｜Ｑ（ｓ），Ｑ（ｓ−１），…，Ｑ（１））は、Ｐ（Ｑ（ｓ＋１）｜Ｑ（ｓ），Ｑ（ｓ−１），…，Ｑ（ｓ−ｎ））と近似することができ、ただしｎは取り出された品質経路の長さとして示される。パラメータｎは最適化される必要がある。同様に訓練セットから、Ｐ（Ｑ（ｓ＋２），Ｑ（ｓ＋１）｜Ｑ（ｓ），Ｑ（ｓ−１），…，Ｑ（ｓ−ｎ）），…，Ｐ（Ｑ（ｓ＋ｔ），…，Ｑ（ｓ＋１）｜Ｑ（ｓ），Ｑ（ｓ−１），…，Ｑ（ｓ−ｎ））を統計的に推定することができる。
【００４８】
検定においては要求経路Ｑ（ｓ），Ｑ（ｓ−１），…，Ｑ（ｓ−ｎ）を前提として、訓練セットから取得されたマルコフ連鎖に基づいて、最も重要でないセグメントを選択するために最尤基準が用いられる。また新しいネットワーク条件に適合させるためにマルコフ連鎖におけるパラメータを適応的に更新するように、逐次学習を組み込むことができる。この学習はビデオごとに個々に、個々のクライアントに対して行うことができるが、集合体に対して行うこともできる。
【００４９】
図４は、キャッシュマネージャ１００がリダイレクト構成要素４０１を有する、キャッシュノードのブロック図を示す。図１で用いられた参照番号が、図４で同じ機能を実行する機能ブロックを指すために用いられる。図４に示されるキャッシュノードはさらに、ネットワークトポロジーについての情報４０３と、セッション要求をそれにリダイレクトすることができる他のキャッシュノードについての情報４０２とを含む。監視デーモン構成要素４０４は、他のキャッシュノードに監視情報を送出し、他のキャッシュノードから監視情報を取り出すことを受け持つ。例示のアルゴリズムは以下のように動作する、すなわち、図４に示されるキャッシュノードは、要求を発行したクライアントに、より近いキャッシュノードを判定する。次いで、クライアントへの近さに基づいてこれらのノードを順序付けし、クライアントに最も近いキャッシュノードから開始する。下記でｃとして示されるこのノードが、同じコンテンツに対するセッションを処理する場合は、図４のキャッシュノードは、このノードがリダイレクトのための有効な候補となるかどうかを判定する。これは次のように行うことができる。要求Ｓが時間的識別子ＩＤおよび品質識別子Ｑを有するセグメントに対するものであると仮定し、同じコンテンツに対するセッションのすべてを調べる。候補キャッシュノードにおいて利用可能なメモリはＸである。
【００５０】
【数２】
0005747090.tif 000003
【００５１】
初期キャッシュノードはすべての候補キャッシュノードに対してこの手順に従うことができ、リダイレクトの決定に達したノードｃを見出したときは、セッションをリダイレクトする。適当な候補ノードｃが見出されなかった場合は、それ自体で要求を処理する。
【００５２】
本発明について特定の実施形態を参照して示してきたが、当業者には本発明は上記の例示的実施形態の詳細に限定されず、本発明はその範囲から逸脱せずに様々な変形形態および変更形態を用いて具現化できることが明らかであろう。したがって、これらの実施形態は、すべての点において例示的なものであって限定的ではないと見なされるべきであり、本発明の範囲は上記の説明によってではなく、添付の特許請求の範囲によって示され、したがって特許請求の範囲の意味および均等な範囲内に含まれるすべての変更形態は、それらの範囲に包含されることが意図される。言い換えれば、基本的な基礎をなす原理の範囲内に包含されるあらゆる変更形態、変形形態または均等物を包括することが企図され、その本質的な属性は、本特許出願において特許請求される。さらに、「備える（ｃｏｍｐｒｉｓｉｎｇまたはｃｏｍｐｒｉｓｅ）」という語句は他の要素またはステップを除外せず、「ａ」または「ａｎ」という語句は複数を除外せず、コンピュータシステム、プロセッサ、または他の集積化ユニットなどの単一の要素が、特許請求の範囲に記載されたいくつかの手段の機能を達成できることが本特許出願によって理解されよう。特許請求の範囲におけるいずれの参照記号も、それぞれの関係する請求項を限定するものと解釈されるべきではない。「第１」、「第２」、「第３」、「ａ」、「ｂ」、「ｃ」などの用語は、明細書または特許請求の範囲において用いられるときは、同様な要素またはステップを区別するために導入され、必ずしも順次的または時間的な順序を表さない。同様に「上（ｔｏｐ）」、「下（ｂｏｔｔｏｍ）」、「上側（ｏｖｅｒ）」、「下側（ｕｎｄｅｒ）」などの用語は説明のために導入され、必ずしも相対的な位置を示すものではない。このように用いられた用語は、適切な状況下では置き換えが可能であり、本発明の実施形態は、上記で述べられたもの、もしくは示されたものとは別の順序で、または異なる向きにおいて本発明による動作が可能であることが理解されるべきである。
【図１】
0005747090.tif 000004
【図２】
0005747090.tif 000005
【図３】
0005747090.tif 000006
【図４】
0005747090.tif 000007