(57)【要約】【課題】コンテンツの優先順位を決める方法及びシステムを提供する。【解決手段】キャッシングプロキシにおいて、第１のコンテンツオブジェクト（２１０）に対する要求が受け取られる。次いで、第１のコンテンツオブジェクト（２１０）の一部に対し、プロキシキャッシュ（１２０）のアクセスログ（２３０）の探索が実行される。プロキシキャッシュ（１２０）における第１のコンテンツオブジェクト（２１０）の一部のサイズが計算され、第１のコンテンツオブジェクト（２１０）のセグメントの標準的に利用されるサイズが導出される。次いで、プロキシキャッシュ（１２０）における第１のコンテンツオブジェクト（２１０）の一部のサイズと、要求された第１のコンテンツオブジェクト（２１０）の標準的に利用されるサイズとが比較される。【選択図】図２
2007510224.tif 000002
【特許請求の範囲】
【請求項１】
コンテンツの優先順位を決める方法であって、
プロキシキャッシュ（１２０）において第１のコンテンツオブジェクト（２１０）に対する要求を受け取ることと、
前記プロキシキャッシュ（１２０）のデータ構造において前記第１のコンテンツオブジェクト（２１０）の一部を探索することと、
前記プロキシキャッシュ（１２０）における前記第１のコンテンツオブジェクト（２１０）の前記一部のサイズを計算することと、
前記要求された第１のコンテンツオブジェクト（２１０）の標準的に利用されるサイズを導出することと、
前記プロキシキャッシュ（１２０）における前記第１のコンテンツオブジェクト（２１０）の前記一部の前記サイズを、前記要求された第１のコンテンツオブジェクト（２１０）の前記標準的に利用されるサイズと比較することと
を含む方法。
【請求項２】
クライアントデバイス（１３０）から、前記第１のコンテンツオブジェクト（２１０）に対する前記要求を受け取ること
を含む請求項１に記載の方法。
【請求項３】
前記プロキシキャッシュ（１２０）における前記第１のコンテンツオブジェクト（２１０）の前記一部の前記サイズを計算することは、
前記プロキシキャッシュ（１２０）にキャッシュされている前記第１のコンテンツオブジェクト（２１０）の前記一部のセグメントの総数をカウントすることと、
前記第１のコンテンツオブジェクト（２１０）の前記一部の前記セグメントの総数の長さを測定することと、
前記セグメントの総数を前記第１のコンテンツオブジェクト（２１０）の前記セグメントの前記長さで乗算することと
を含む
請求項１に記載の方法。
【請求項４】
前記要求された第１のコンテンツオブジェクト（２１０）の前記標準的に利用されるサイズを導出することは、
前記プロキシキャッシュ（１２０）の前記アクセスログを利用することであって、それにより前記第１のコンテンツオブジェクト（２１０）の平均閲覧長さを確立すること
を含む
請求項１に記載の方法。
【請求項５】
前記標準的に利用されるサイズが、前記プロキシキャッシュ（１２０）における前記第１のコンテンツオブジェクト（２１０）の前記一部の前記サイズより小さい場合、前記プロキシキャッシュ（１２０）に対し、前記第１のコンテンツオブジェクト（２１０）の部分をそれ以上受け入れないこと
を含む請求項１に記載の方法。
【請求項６】
前記標準的に利用されるサイズが、前記プロキシキャッシュ（１２０）における前記第１のコンテンツオブジェクト（２１０）の前記一部の前記サイズより大きい場合、前記プロキシキャッシュ（１２０）に対し、前記第１のコンテンツオブジェクト（２１０）の更なるセグメントを受け入れること
を含む請求項１に記載の方法。
【請求項７】
前記プロキシキャッシュ（１２０）における利用可能なキャッシュ空間に、前記第１のコンテンツオブジェクト（２１０）の前記更なるセグメントを受け入れるための空きがあるか検査することと、
前記プロキシキャッシュ（１２０）において、前記第１のコンテンツオブジェクト（２１０）の前記更なるセグメントのために場所を空けることと
を含む請求項６に記載の方法。
【請求項８】
前記プロキシキャッシュ（１２０）において前記場所を空けることは、
前記プロキシキャッシュ（１２０）における他のコンテンツオブジェクトに対し効用値（３２０）を計算することと、
該効用値（３２０）に基づいて前記他のコンテンツオブジェクトの優先順位を決めることと、
最小効用値（３２０）を有する前記他のコンテンツオブジェクトのうちの１つを選択することと、
前記プロキシキャッシュ（１２０）における前記最小効用値（３２０）を有する前記他のコンテンツオブジェクトの最低優先順位部分（３６５）を除去することと、
前記プロキシキャッシュ（１２０）に対し前記第１のコンテンツオブジェクト（２１０）の前記更なるセグメントを受け入れることと
を含む請求項７に記載の方法。
【請求項９】
前記最小効用値（３２０）を有する前記他のコンテンツオブジェクトのうちの前記１つが完全にキャッシュされている場合、
前記最小効用値（３２０）を有する前記他のコンテンツオブジェクトのうちの前記１つを、該最小効用値（３２０）を有する該他のコンテンツオブジェクトのうちの前記１つに対するアクセスの先の持続時間に基づいてセグメント化すること
をさらに含む請求項８に記載の方法。
【請求項１０】
前記最小効用値（３２０）を有する前記他のコンテンツオブジェクトのうちの前記１つが完全にキャッシュされていない場合、
前記最小効用値（３２０）を有する前記他のコンテンツオブジェクトのうちの前記１つのすべてのセグメント（３７０）除去すること
をさらに含む請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施の形態は、コンテンツ配信ネットワークに関する。
より詳細には、本発明の実施の形態は、キャッシングプロキシに関する。
【背景技術】
【０００２】
インターネットにおいてキャッシングの使用が広く行き渡る前、クライアントが要求するコンテンツの項目（コンテンツオブジェクト）は、オリジナルコンテンツサーバ（コンテンツオブジェクトのソース）によって提供される可能性が高かった。
コンテンツソースとクライアントとは、通常、互いからかなりの距離に位置しており、それにより応答時間が遅くなり、帯域幅が狭くなり、損失率が高くなり、スケーラビリティが十分でなくなることが多かった。
応答時間、帯域幅及び損失率はまた、複数のクライアントが同時にコンテンツソースに対してオブジェクトを要求しようと試みる場合にも著しく影響を受ける可能性があった。
【０００３】
コンテンツ配信ネットワーク等、異なる形態のキャッシングが、これらの問題のうちのいくつかを克服するのに役立った。
一般に、コンテンツ配信ネットワークは、より具体的にはキャッシングプロキシと呼んでもよいサーバを、クライアントに対してより近くに配置する。
コンテンツオブジェクトを複製して、キャッシングプロキシの各々においてキャッシュすることができる。
コンテンツをクライアントにより近いキャッシングプロキシにキャッシュすることにより、応答時間の低減、帯域幅の向上、損失率の低下、スケーラビリティの向上及びネットワーク（バックボーン）資源に対する要件の低減を含む、複数の改善がもたらされた。
【０００４】
コンテンツ配信ネットワークは、キャッシュのサイズに比較してコンテンツのサイズが相対的に小さい場合は有効に機能する。
たとえば、ウェブ（Web）ページは、一般に、サイズがメガバイトよりはるかに小さい。
したがって、この種のコンテンツを各キャッシングプロキシにおいて実際的に複製することができる。
ウェブコンテンツの複数のインスタンスを、大量のメモリ資源を必要とすることなく、又は利用可能なメモリの著しいセグメントを消費することなく、各キャッシングプロキシに格納することができる。
【０００５】
しかしながら、マルチメディアコンテンツの急増のため、キャッシングには問題がある可能性がある。
通常のマルチメディアオブジェクトのサイズが大きいため、フルオブジェクトキャッシング戦略は、キャッシュ空間を急速に消耗する。
すなわち、大きいキャッシュであっても、一杯になる前にマルチメディアコンテンツの少数の項目しか保持することができない。
たとえば、ＤＶＤ（デジタルビデオディスク）品質の映像は、サイズが最大で４．７ギガバイト（ＧＢ）に、長さが最大２時間に達する場合がある（ムービングピクチャエキスパートグループ（Moving Picture Expert Group）２圧縮に基づく）。
したがって、５０ＧＢキャッシュは、ＤＶＤ品質の映像を約１０個しか保持することができない。
そのため、キャッシュが一杯になると、到来するオブジェクトに対して場所を空けるために、キャッシュから非アクティブオブジェクトを取り除き始める必要がある。
【０００６】
現在、プレフィックスキャッシング及びセグメントベースキャッシングが、フルプロキシキャッシュの問題を解決するために通常使用される２つの技法である。
一般に、プレフィックスキャッシングは、ほとんどのクライアントがメディアオブジェクトの初期セグメントにアクセスする場合に有効に機能する。
プレフィックスキャッシングはまた、オリジンサーバから後続するセグメントを取り出している間に、キャッシュされたプレフィックスをプロキシからクライアントに直ちに供給することによって、スタートアップレイテンシを低減する。
しかしながら、プレフィックスキャッシングでは、プレフィックスサイズの静的確定がシステムの性能において極めて重大な役割を果たす。
【０００７】
一般に、セグメントベースキャッシング方法は、柔軟性を向上させるために開発された。
これらの方法はまた、メディアオブジェクト全体ではなくメディアオブジェクトのセグメントをキャッシュする。
通常、２つのタイプのセグメンテーション戦略が使用される。
第１のタイプは、サイズが一様であるセグメントを使用する。
たとえば、階層符号化ビデオオブジェクトのサイズが一様であるセグメントのキャッシングである。
第２のタイプは、サイズが指数関数的に決められるセグメントを使用する。
この戦略では、メディアオブジェクトは、長さが増大しながらセグメント化される。
たとえば、セグメント長は２倍となる場合がある。
この戦略は、メディアオブジェクトのセグメントは後になるほどアクセスされる可能性が低くなるという仮定に基づく。
場合によっては、これらの方法の組合せを利用してもよい。
すなわち、一定の長さ及び指数関数的に増大する長さをともに考慮する。
このタイプの方法もまた、メディアオブジェクトの開始セグメントを有利に扱う。
【０００８】
しかしながら、本明細書で論考するプレフィックスキャッシング方法及びセグメンテーションベースキャッシング方法は、以下の考慮事項に対応しない。
第１に、ユーザのメディアオブジェクトに対するアクセスは、通常、偏ったパターンを表し、ほとんどのアクセスが人気のある少数のオブジェクトに対するものであり、これらのオブジェクトは全体として又は略全体として見られる可能性が高い。
これは、会社環境における仮想社内会議及び研修ビデオのムービーコンテンツに対して当てはまることが多い。
すなわち、指数関数的であれ一様であれ事前に定義されたセグメントサイズを用いる発見的セグメントベースキャッシング戦略は、常にメディアオブジェクトの開始セグメントを有利にキャッシュし、ほとんどのアクセスが人気のある少数のオブジェクトをターゲットにするという事実を考慮しない。
【０００９】
第２に、メディアオブジェクトのアクセス特性は動的に変化している。
すなわち、メディアオブジェクトの人気及び最も見られるセグメントは時間とともに変化する可能性がある。
たとえば、オブジェクトによっては、ほとんどのユーザがオブジェクト全体にアクセスする初期期間において人気がある場合がある。
そして、時間が経過すると、これらのオブジェクトに対する要求が少なくなる可能性があり、オブジェクトの後の方のセグメントに対するユーザアクセスはさらに少なくなる可能性がある。
このシナリオでは、いくつかの初期セグメントをキャッシュする固定の戦略を使用することは役立たない可能性がある。
それは、初期期間中は、後のセグメントが頻繁に取り出される必要がある際にネットワークに過負荷を与える可能性があり、後の期間の間は、初期セグメントのすべてをキャッシュすることにより資源が消耗する可能性があるためである。
既存のプロキシキャッシング方式におけるこの適応性の無さが、プロキシキャッシングを無効なものにする可能性がある。
【非特許文献１】CHEN SONGQING ET AL: "Adaptive and lazy segmentation based proxy caching for streaming media delivery" PROCEEDINGS OF THE INTERNATIONAL WORKSHOP ON NETWORK AND OPERATING SYSTEM SUPPORT FOR DIGITAL AUDIO AND VIDEO 2003, 'Online! 1 June 2003 (2003-06-01), pages 22-31, XP002322646 Retrieved from the Internet: URL:http://www.cs.wm.edu/hpcs/WWW/HTML/publications/papers/TR-03-4.pdf'retrieved on 2005-03-29! abstract introduction sections 2, 2.1, 2.2 and 2.3
【非特許文献２】HAO CHEN ET AL: "A new proxy caching scheme for parallel video servers" COMPUTER NETWORKS AND MOBILE COMPUTING, 2003. ICCNMC 2003. 2003 INTERNATIONAL CONFERENCE ON 20-23 OCT. 2003, PISCATAWAY, NJ, USA,IEEE, 20 October 2003 (2003-l0-20), pages 438-441, XP010666172 ISBN: 0-7695-2033-2 the whole document
【非特許文献３】BALAFOUTIS E ET AL: "Proxy caching and video segmentation based on request frequencies and access costs" TELECOMMUNICATIONS, 2003. ICT 2003, 10TH INTERNATIONAL CONFERENCE ON FEB. 23-MAR. 1, 2003, PISCATAWAY, NJ, USA,IEEE, vol. 2, 23 February 2003 (2003-02-23), pages 1367-1372, XP010637996 ISBN: 0-7803-7661-7 abstract sections II.B. and II.C.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
したがって、エンドユーザに対してコンテンツオブジェクトをキャッシュするより効率的な方法が望ましい。
本発明の実施の形態は、こうした改善を提供する。
【課題を解決するための手段】
【００１１】
［発明の開示］
本発明の実施の形態は、コンテンツの優先順位を決める方法及びシステムに関する。
キャッシングプロキシにおいて、第１のコンテンツオブジェクトに対する要求が受け取られる。
そして、第１のコンテンツオブジェクトの一部に対し、プロキシキャッシュのアクセスログの探索が実行される。
プロキシキャッシュにおける第１のコンテンツオブジェクトの一部のサイズが計算され、第１のコンテンツオブジェクトのセグメントの標準的に利用されるサイズが導出される。
そして、プロキシキャッシュにおける第１のコンテンツオブジェクトの一部のサイズと、要求された第１のコンテンツオブジェクトの標準的に利用されるサイズとが比較される。
【００１２】
本明細書に組み込まれ且つその一部を形成する添付図面は、本発明の実施の形態を例示し、その記述とともに、本発明の原理を説明する役割を果たす。
【００１３】
本説明で参照する図面は、特に述べる場合を除き一定比例尺になっていると理解されるべきではない。
【発明を実施するための最良の形態】
【００１４】
ここで、本発明のさまざまな実施形態について詳細に言及する。
それらの例を、添付図面に示す。
本発明を、これらの実施形態に関連して説明するが、それらが本発明をこれらの実施形態に限定するようには意図されていないということが理解されよう。
むしろ、本発明は、添付の特許請求の範囲によって定義される本発明の精神及び範囲内に含まれ得る代替形態、変更形態及び等価形態を包含することが意図されている。
さらに、本発明の以下の詳細な説明では、本発明が完全に理解されるために多数の特定の詳細を示す。
他の場合では、本発明の態様を不必要に不明瞭にしないように、既知の方法、手続き、構成要素及び回路については詳細に説明していない。
【００１５】
本発明の実施形態は、本明細書において概してメディアデータ、マルチメディアデータ、コンテンツ又はコンテンツオブジェクトと呼ぶ、ビデオベースデータ、音声ベースデータ、画像ベースデータ、ウェブページベースデータ、グラフィックスデータ等での使用によく適している。
明確に且つ簡潔にする目的で、以下の論考及び例は、特にコンテンツオブジェクトを扱う場合もある。
しかしながら、本発明の実施形態は、コンテンツオブジェクトで使用するようには限定されない。
【００１６】
概して、本発明の実施形態は、キャッシュにおけるコンテンツの優先順位を決めるためにリアルタイムアクセスに応答的に適応し、可能な限り遅くオブジェクトを遅延して（lazily）セグメント化する、適応的且つ遅延セグメンテーションベースのキャッシング戦略を利用する。
特に、積極的（aggressive）受入れ（admission）ポリシ、遅延セグメンテーション戦略及び／又は２段階（two-phase）反復置換ポリシを利用することにより、プロキシキャッシュをより効率的に利用することができ、それにより、ユーザがコンテンツソースと直接連絡をとる必要が低減される。
【００１７】
本発明の実施形態はまた、所定の期間にわたるオブジェクトアクセスパターンの変化に対して動的に適応する。
たとえば、メディアオブジェクトの人気特性が所定期間にわたって変化する一般的なシナリオを考える。
キャッシュは、アクセスパターンを事前に想定することなくこの状況を自動的に考慮することができる。
すなわち、ユーザが最初にコンテンツオブジェクトの第１の部分にアクセスする場合、キャッシュはその第１の部分のコピーを保持する。
しかしながら、その後、ユーザがコンテンツオブジェクトの第１０の部分を中心に見始めると、キャッシュは、キャッシュにおけるオブジェクトの効用を再計算し、第１の部分から第１０の部分に優先順位を再割当てしてもよい。
このため、キャッシュにさらなる空間が必要である場合、コンテンツオブジェクトの第１の部分を第１０の部分の前に取り除いてもよい。
たとえば、メディアオブジェクトの人気のあるセグメントを、メディアオブジェクト内のそれらの位置に関わらず、有利にキャッシュすることにより、ネットワークトラフィックを低減することができる。
【００１８】
さらに、本発明の実施形態は、異なるタイプのメディアオブジェクトに適応することができる。
すなわち、異なるカテゴリからのメディアオブジェクトを、キャッシング効率を最大化するという目的で公平に扱う。
たとえば、大きいコンテンツオブジェクトとそれより小さいコンテンツオブジェクトとがともにキャッシュに場所をとっている場合、反復置換ポリシにより、サイズに関わらず効用の最も低いオブジェクトが置き換えられる。
したがって、キャッシュは、作業容量を維持しながらも、効用が最も高いコンテンツオブジェクトを保持する。
さらに、効用関数を、キャッシュ空間を最大化するように規定してもよい。
たとえば、人気のあるセグメントが初期セグメントであるか否かに関わらず、キャッシュ空間をそれらの人気のあるセグメントに有利に割り付けてもよい。
【００１９】
コンテンツオブジェクトの効用を評価することに加えて、実施形態はさらに、コンテンツオブジェクトに対する実際のアクセス時間に基づいてコンテンツオブジェクトをさらにセグメント化してもよい。
すなわち、各コンテンツオブジェクトのセグメントサイズを、リアルタイムに記録されるオブジェクトのアクセス履歴に基づいて適応的に決定してもよい。
そのように決定する際、コンテンツオブジェクトのセグメントサイズは、クライアントのアクセス挙動をより正確に反映することができる。
たとえば、オブジェクトに対するアクセス履歴を、セグメンテーションプロセスを遅延させることによって収集してもよい。
それにより、最初にコンテンツオブジェクト全体をキャッシュし、オブジェクトのセグメント化の前に実際のクライアントの使用を待つことにより、より現実的なセグメンテーションサイズを利用することができる。
さらに、セグメント受入れ及び追出し（eviction）ポリシを、これらのアクセス記録に基づいてリアルタイムに適応させることができる。
【００２０】
ここで図１を参照すると、本発明の一実施形態によるコンテンツの優先順位を決めるネットワーク又はシステム１００が示されている。
システム１００は、図示するもの以外の要素を含んでもよい、ということが理解される。
システム１００はまた、図示するさまざまな要素を２つ以上含んでもよい。
これらの要素の各々の機能については後述する。
これらの要素は、論考するもの以外の機能をインプリメントしてもよい、ということが理解される。
【００２１】
本実施形態では、システム１００のさまざまな要素は、図示するように互いと通信する。
すなわち、本実施形態では、コンテンツソース１１０は、キャッシングプロキシ１２０（キャッシュプロキシ又はプロキシキャッシュという用語を使用する場合もある）と通信し、それによりコンテンツソース１１０は、通信チャネル１２５を介してクライアントデバイス１３０と通信する。
一般的に言えば、キャッシングプロキシ１２０は、通常、ネットワーク又はシステム１００の端に配備されることにより、コンテンツソース１１０との間のトラフィックを低減し、クライアントデバイス１３０によって感知されるレイテンシも低減する。
【００２２】
クライアントデバイス１３０は、コンピュータシステム（ラップトップ、デスクトップ又はノートブック）、ハンドヘルドデバイス（個人情報端末等）、携帯電話、又は一般にユーザがコンテンツの項目にアクセスしそれらを実行する（たとえば表示する）ことができるようにする別のタイプのデバイスであってもよい。
上述したように、実際には、キャッシングプロキシ１２０にアクセスすることができる多くのクライアントデバイスがあり得る。
異種ネットワークでは、これらのクライアントデバイスの各々は、異なる属性又はプロファイルを有してもよい。
これらの属性には、限定されないが、さまざまなクライアントデバイスの表示、電力、通信及び計算の能力及び特性が含まれる。
【００２３】
通信は、要素の間で直接行われてもよく、或いは媒介デバイス又はノード（図示せず）を介して間接的に行われてもよい。
また、通信は、有線又は無線、或いは有線及び無線の組合せであってもよい。
一実施形態では、通信は、ワールドワイドウェブ（又はインターネット）上で行われる。
実際には、キャッシングプロキシ１２０の下流に多くの通信チャネルがあってもよい。
異種ネットワークでは、これらの通信チャネル（通信チャネル１２５によって例示される）の各々は、異なる属性を有してもよい。
たとえば、１つのチャネルが、別のチャネルより高い帯域幅（高いデータ転送レート）を有するものとして特徴付けられてもよい。
【００２４】
図２は、本発明の一実施形態による、キャッシュのオブジェクトにアクセスする方法のフローチャート２００である。
フローチャート２００には特定のステップを開示するが、こうしたステップは例示的なものである。
すなわち、本発明の実施形態は、さまざまな他のステップ、又はフローチャート２００に列挙するステップの変形を実行することによく適している。
フローチャート２００のステップを、提示する順序とは異なる順序で実行してもよく、フローチャート２００のステップのすべてを実行しなくてもよい、ということが理解される。
フローチャート２００によって説明される方法のすべて又は一部を、たとえばコンピュータシステム又は同様のデバイスのコンピュータが使用可能な媒体に存在する、コンピュータ読取可能且つコンピュータ実行可能命令を使用してインプリメントしてもよい。
概して、フローチャート２００は、図１のキャッシングプロキシ１２０等のデバイスによってインプリメントされる。
【００２５】
図２のステップ２１０において、本実施形態では、キャッシングプロキシにおいてクライアントデバイス（たとえば図１のキャッシングプロキシ１２０及びクライアントデバイス１３０）からコンテンツオブジェクトに対する要求を受け取る。
この要求は、完全なコンテントオブジェクトに対するものであっても、コンテンツオブジェクトの一部（たとえばセグメント）のみに対するものであってもよい。
本明細書で述べるように、コンテンツオブジェクトは、ビデオクリップ、音声クリップ、ビデオ会議、グラフィックス、メディア等であってもよい。
【００２６】
図２のステップ２１５において、キャッシングプロキシは、そのコンテンツオブジェクトがプロキシによって先にアクセスされたことがあるか否かを評価する。
たとえば、キャッシングプロキシは、要求されたコンテンツオブジェクトに関する先のエントリに対するアクセスログ等のデータ構造を検査（たとえば、探索、外挿、比較等）してもよい。
一実施形態ではオブジェクトという用語を使用するが、オブジェクト（又はコンテンツオブジェクト）という用語は、完全なコンテンツオブジェクト、コンテンツオブジェクトのセグメント、コンテンツオブジェクトの一部等を指してもよい、ということが理解される。
【００２７】
一実施形態では、データ構造は以下を含んでもよい。
Ｔ１：オブジェクトが最初にアクセスされる時刻インスタンス
Ｔｒ：オブジェクト又はセグメントに対する最新参照時刻（これは、オブジェクトが最初にアクセスされる時はＴ１に等しい）
Ｔｃ：現在時刻
Ｌｓｕｍ：オブジェクト又はセグメントに対する各アクセスの持続時間の合計
ｎ：オブジェクト又はセグメントに対するアクセスの数
Ｌｂ：基本セグメントの長さ
ｎｓ：オブジェクトのキャッシュされたセグメントの数
【００２８】
一実施形態では、各アクセス到着時に、量Ｔｒ、Ｌｓｕｍ、ｎ及びｎｓを動的に更新してもよく、各セッション終了時にＬｓｕｍを更新してもよく、オブジェクトが最初にセグメント化される時にＬｂを決定してもよい。
データ構造は、本明細書で列挙する項目より多いか又は少ない項目を含んでもよい、ということが理解される。
本明細書で述べる特定の項目は、本明細書で説明する方法を実行してもよいデータ構造のあり得る項目の一実施形態に過ぎない。
【００２９】
さらに、本明細書で説明するデータエントリから以下の量を導出し、それらをコンテンツオブジェクトのアクセスアクティビティの測定値として利用してもよい。
アクセスの頻度（Ｆ）を、アクセスの数（ｎ）を最新参照時刻（Ｔｒ）から最初のアクセスの時刻インスタンス（Ｔ１）を引いた数で除算した値を利用することによって導出してもよい。
また、平均アクセス持続時間（Ｌａｖｇ）を、各アクセスの持続時間の合計（Ｌｓｕｍ）をアクセスの数（ｎ）で除算した数として定義してもよい。
【００３０】
クライアントデバイス１３０がコンテンツオブジェクトに対する要求を受け取ったのがこの時が初めてである場合、アクセスログは、コンテンツオブジェクトに関する情報をまったく含まない場合があり、図２のステップ２２０において、コンテンツオブジェクトに対してアクセスログエントリを作成してもよい。
アクセスログエントリは、限定されないが、本明細書で述べるデータ構造カテゴリの多くを含んでもよい。
【００３１】
そして、図２のステップ２２５において、キャッシュプロキシは、要求されたコンテンツオブジェクトをキャッシュに受け入れる用意をする。
最初に、各コンテンツオブジェクトを、それが全く初めてアクセスされる場合、完全にキャッシュしてもよい。
そして、完全にキャッシュされたオブジェクトを、本明細書で詳細に説明する置換プロセスによって追出し犠牲者（victim）として選択されるまでキャッシュに維持してもよい。
【００３２】
一般に、キャッシュプロキシは、要求されたコンテンツオブジェクトを受け入れるために、コンテンツオブジェクト全体をキャッシュに直接入れるために空きがあるか否かを判断しなければならない。
すなわち、プロキシがオブジェクトの全長を知ると、十分なキャッシュ空間が割り当てられる必要がある。
プロキシキャッシュに十分な空きスペースがない場合、本明細書において詳細に概説する適応的置換プロセスを通してスペースを作成してもよい。
【００３３】
図２のステップ２３０において、アクセスログがコンテンツオブジェクトに関する何らかの情報を含む場合、それは、コンテンツオブジェクトがキャッシュプロキシによって事前にアクセスされたことがあることを意味する。
その場合、アクセスログを、コンテンツオブジェクトに対する最新の要求を示すように更新してもよい。
【００３４】
図２のステップ２３５において、アクセスログデータ構造の基準を利用して、コンテンツオブジェクトの状態を評価する。
すなわち、コンテンツオブジェクトがプロキシキャッシュに完全にキャッシュされているか否かである。
それが完全にキャッシュされている場合、コンテンツオブジェクトのそれ以上の受入れは必要でなく、ステップ２５０が実行される。
すなわち、そのほかの動作は不要である。
【００３５】
コンテンツオブジェクトが完全にはキャッシュされておらず、代りにセグメントのみがキャッシュにある場合、図２のステップ２４０において、その要求に対してキャッシュのセグメントが十分であるか（又は正しいセグメントであるか）否か、又はコンテンツオブジェクトの更なるセグメントが必要であるか否かを分析する。
たとえば、アクセスログが、ｎｓ個のセグメントがキャッシュされていることを示す場合、システムは、次のセグメント（ｎｓ＋１）をキャッシュする必要があるかを考慮する。
その必要を確定する一方法は、次の式である。
Ｌａｖｇ＞（ｎｓ＋１）Ｌｂ／ａ
ここで、「ａ」は、キャッシュプロキシにどれくらいのオブジェクト（たとえば、いくつのセグメント）が維持されるかを判断するのに役立つように使用される基準又は定数である。
すなわち、「ａ」は、サーバリンクトラフィックを低減するキャッシングプロキシ能力に関する。
オブジェクトに対して或る「ａ」値を利用することにより、ユーザに対するスタートアップ遅延を低減することができる（たとえばバッファサイズ等）。
たとえば、「ａ」＝２である場合、クライアントデバイス１３０が受けるスタートアップ遅延が最小であることを確実にするために、プロキシキャッシュの最低２セグメントが必要である。
【００３６】
このように、上記不等式は、平均アクセス持続時間がコンテンツオブジェクトの平均アクセス長より小さい（すなわち短い）場合、キャッシュに対してそれ以上の受入れは不要であり、プロキシキャッシュはこの場合もまたステップ２５０に進む、ということを示す。
すなわち、それ以上の動作は不要である。
【００３７】
しかしながら、平均アクセス持続時間がコンテンツオブジェクトの平均アクセス長より大きい（すなわち長い）場合、図２のステップ２４５において、さらなるセグメントが必要とされる場合がある。
すなわち、平均アクセス持続時間が、キャッシュされたｎｓ個のセグメントが要求の大部分をカバーすることが出来ない程度まで増大している場合、次のキャッシュされていないセグメントの受入れを考慮すべきである。
【００３８】
図２のステップ３０１において、概して、キャッシュプロキシは、キャッシュに、コンテンツオブジェクトの次のセグメントのための空きがあるかを判断しなければならない。
すなわち、十分なキャッシュ空間が割り付けられる。
十分な空間がない場合、本明細書において詳細に概説する適応的置換プロセスを通して空間を空けてもよい。
【００３９】
ここで図３を参照すると、本発明の一実施形態による、キャッシュにおけるオブジェクト置換の方法のフローチャート３００が示されている。
フローチャート３００には特定のステップを開示するが、こうしたステップは例示的なものである。
すなわち、本発明の実施形態は、さまざまな他のステップ又はフローチャート３００に列挙するステップの変形を実行するようによく適している。
フローチャート３００のステップを、提示した順序とは異なる順序で実行してもよく、フローチャート３００のステップのすべてを実行しなくてもよい、ということが理解される。
フローチャート３００によって説明する方法のすべて又は一部を、たとえばコンピュータシステム又は同様のデバイスのコンピュータが使用可能な媒体に存在するコンピュータ読取可能且つコンピュータ実行可能命令を使用してインプリメントしてもよい。
概して、フローチャート３００は、図１のキャッシングプロキシ１２０等のデバイスによってインプリメントされる。
【００４０】
概して、利用可能なキャッシュ空間がなく、新たなオブジェクトがキャッシュプロキシに置かれる必要があると、遅延セグメンテーション戦略が利用される。
置換ポリシは、各オブジェクトのキャッシング効用を計算し、効用値が最も小さい非アクティブオブジェクトを犠牲者として選択する。
犠牲者オブジェクトが、セグメント化されていないオブジェクトであり目下完全にキャッシュされている場合、プロキシはそのオブジェクトをセグメント化する。
一実施形態では、オブジェクトは、平均アクセス持続時間（Ｌａｖｇ）に基づいて特定の長さ（Ｌｂ）にセグメント化される。
Ｌｂの値が確定されると、それは、特定のコンテンツオブジェクトの各セグメントに対して固定されたままとなる。
セグメンテーションが発生した後、最初のｍ個のセグメントはキャッシュに維持され、残りは追い出される。
そして、キャッシュされたセグメントの数がアクセスログに記録される。
【００４１】
後の要求が、キャッシュされたセグメントの数より多くを必要とする場合、コンテンツソース１１０からプリフェッチされるようにスケジュールされたデータが、より短い可能性のある最後のセグメントを除き、長さＬｂのセグメントにフェッチされる。
たとえば、Ｌｂがサイズ３であり、プリフェッチされることが必要なデータのサイズが５である場合、サイズ３のセグメントとサイズ２のセグメントとがコンテンツソース１１０からフェッチされ、キャッシングプロキシ１２０に格納される。
【００４２】
このように、本方法は、オブジェクトが最初にアクセスされる時にセグメンテーションが実行される他のセグメンテーション戦略とは異なる。
すなわち、遅延セグメンテーションは、可能な限りセグメンテーションプロセスを遅らせることにより、セグメンテーションプロセスの精度に役立つために十分な量のアクセス統計の収集を可能にする。
したがって、遅延セグメンテーションは、リアルタイムユーザアクセス挙動に従って異なるオブジェクトに対して異なるセグメント長を設定することができる。
【００４３】
図３のステップ３１０において、キャッシュプロキシは、コンテンツオブジェクトの次のセグメントに対してキャッシュに空きがあるかを判断しなければならない。
すなわち、コンテンツオブジェクトが追加されるために十分なキャッシュ空間が利用可能であるかである。
コンテンツオブジェクト（図２において詳細に説明したように、一部又はオブジェクト全体のいずれか）を追加するために十分な空きがある場合、図３のステップ３１５が実行される。
すなわち、損害なしに、プロキシキャッシュにコンテンツオブジェクトが追加される。
【００４４】
しかしながら、コンテンツオブジェクトに対してプロキシキャッシュ１２０に十分な空間がない場合、図３のステップ３２０において、適応的置換プロセスを通して空間を空けてもよい。
すなわち、プロキシキャッシュ１２０のオブジェクトの効用（Ｕ）を計算してもよい。
一実施形態では、効用関数は、犠牲者選択プロセスに対する結果を導出するためのいくつかの因子に頼ってもよい。
たとえば、効用計算は、アクセスの数（ｎ）、アクセスの持続時間、キャッシュデータの長さ（ｎｓ×Ｌｂ）（記憶装置のコストである）、及び将来のアクセスの確率を考慮してもよい。
一実施形態では、将来のアクセスの確率は、Ｔｃが現在時刻である場合、新たなアクセスと最近のアクセスとの間の時間間隔（Ｔｃ−Ｔｒ）と、過去に発生しているアクセスに対する平均時間間隔（（Ｔｒ−Ｔ１）／ｎ）とを比較してもよい。
たとえば、（Ｔｃ−Ｔｒ）＞（Ｔｒ−Ｔ１）／ｎである場合、オブジェクトに対して新たな要求がまもなく到着する可能性は小さい。
そうでない場合、要求がまもなく到来する可能性は非常に高い。
【００４５】
一実施形態では、オブジェクト又はセグメントのキャッシング効用は、将来のアクセスの数、アクセスの平均時続時間及びアクセスの確率に比例する。
さらに、それは、オブジェクトサイズ又はセグメントサイズに反比例してもよい。
したがって、効用を、以下のように定義してもよい。
【００４６】
【数１】
2007510224.tif 000003
【００４７】
ここで、
Ｌａｖｇ／ｎ：将来のアクセスの平均時続時間を推定する
（Ｆ）：将来のアクセスの平均数を推定する
ＭＩＮ（１，（（（Ｔｒ−Ｔ１）／ｎ）／（Ｔｃ−Ｔｒ）））：将来のアクセスの確率を示す
（ｎｓ×Ｌｂ）：ディスク記憶装置のコストである。
【００４８】
このように、効用関数は、コンテンツオブジェクト内のセグメントの相対位置に関わらず、それらのセグメントの人気に関するより正確な推定値を提供する。
それが、それほど人気のないセグメントがキャッシュから追い出されるセグメントであることを確実にする助けとなる。
しかしながら、コンテンツオブジェクトに対して効用評価を割り当てるために利用してもよい複数のあり得る計算及び変数がある。
本変数の使用は、多くのあり得る実施形態のうちの１つに過ぎず、簡潔であるために利用する。
【００４９】
図３のステップ３３０において、上述した効用因子に基づいて、プロキシキャッシュのオブジェクトのリストをソートする。
ステップ３４０において、効用因子が最小であるオブジェクト（Ｏ'）を見つけ、ステップ３５０において、２段階のうちのいずれの段階において、キャッシュされたオブジェクトＯ'が格納されているかを確立するために、Ｏ'のアクセスログの分析が実行される。
すなわち、Ｏ'が完全にキャッシュされているか、又はプロキシキャッシュ１２０においてすでにセグメント化されているかである。
【００５０】
コンテンツオブジェクトＯ'が完全にキャッシュされている場合、図３のステップ３５５において、本明細書で説明した遅延セグメンテーションプロセスを開始する。
遅延セグメンテーションで利用されるステップの一実施形態は、図３のステップ３６０〜３６８においてカバーされる。
本明細書で述べる３つのステップは、明確にする目的のためである。
本発明によってより多い又は少ないステップが実行されてもよい、ということが理解される。
【００５１】
図３のステップ３６０において、基本セグメント（Ｌｂ）の長さを決定する。
この長さは、平均アクセス持続時間（Ｌａｖｇ）に基づく。
たとえば、オブジェクトが先に５回アクセスされており、平均アクセス長が７秒であった場合、Ｌａｖｇは７秒であってもよい。
別の実施形態では、それは、７秒の倍数（たとえば、１４、２１等）か又は分数（たとえば、３．５、１．７５等）であってもよく、又はそれを長さではなくサイズ（たとえばバイト）で測定してもよい。
【００５２】
図３のステップ３６５において、Ｏ'の複数（ａ）のセグメントを維持し、Ｏ'のセグメントの残りをキャッシュから追い出す。
一実施形態では、維持されるＯ'のセグメントの数は最高効用計算による数であってもよい。
たとえば、Ｏ'が１．５秒セグメントにセグメント化され中間の３秒が最高効用値を有する場合、キャッシュにはＯ'の２（ａ）個のセグメントが残っていてもよく、Ｏ'の残りは除去される。
【００５３】
次に、図３のステップ３６８において、アクセスログを更新する。
一実施形態では、更新は、オブジェクトのキャッシュされたセグメントの数（ｎｓ）、オブジェクト又はセグメントの最新参照時刻（Ｔｒ）及び基本セグメントの長さ（Ｌｂ）を含むように完成してもよい。
アクセスログが更新された後、プロセスは図３のステップ３１０に戻る。
すなわち、キャッシュを検査して、必要なコンテンツオブジェクトを受け入れるために十分な空き空間が存在するか判断する。
本明細書で述べたように、十分な空きがある場合、オブジェクトは受け入れられ、プロセスは終了し、空きがない場合、図３のステップ３２０に進む。
【００５４】
図３のステップ３５０を再び参照すると、オブジェクトＯ'がプロキシキャッシュ１２０においてすでにセグメント化されている場合、ステップ３７０に進む。
【００５５】
図３のステップ３７０において、コンテンツオブジェクトＯ'がすでにセグメント化されており、それが最小効用値を有することが分っている場合、オブジェクトＯ'の最後の１つ又は複数のセグメントをキャッシュから追い出す。
【００５６】
ステップ３８０において、アクセスログを更新する。
一実施形態では、更新は、キャッシュに残っているオブジェクトのキャッシュされたセグメントの数（ｎｓ）（たとえばゼロ）を含むように完成してもよい。
アクセスログが更新された後、プロセスは図３のステップ３１０に戻る。
すなわち、キャッシュを検査して、必要なコンテンツオブジェクトを受け入れるために十分な空き空間が存在するか判断する。
本明細書で述べたように、十分な空きがある場合、オブジェクトは受け入れられ、プロセスは完了し、空きがない場合、図３のステップ３２０に進む。
【００５７】
このように、オブジェクトが完全に置換された後でさえ、オブジェクトのアクセス履歴はアクセスログに残っていることが可能である。
したがって、メディアオブジェクトに再びアクセスする時、それは完全にキャッシュされるのではなく、キャッシュプロキシは、平均アクセス持続時間としてそのログに示されているオブジェクトコンテンツの量のみを最初にキャッシュすればよい。
【００５８】
図４は、本発明の一実施形態による、コンテンツの優先順位を決める方法のフローチャート４００である。
フローチャート４００には特定のステップを開示するが、このようなステップは例示的なものである。
すなわち、本発明の実施形態は、さまざまな他のステップ又はフローチャート４００に列挙するステップの変形を実行することによく適している。
フローチャート４００のステップを提示した順序と異なる順序で実行してもよく、フローチャート４００のステップのすべてを実行しなくてもよい、ということが理解される。
フローチャート４００によって説明する方法のすべて又は一部を、たとえばコンピュータシステム又は同様のデバイスのコンピュータが使用可能な媒体に存在する、コンピュータ読取可能且つコンピュータ実行可能命令を使用してインプリメントしてもよい。
概して、フローチャート４００は、図１のキャッシングプロキシ１２０等のデバイスによってインプリメントされる。
【００５９】
図４のステップ４０１において、プロキシキャッシュにおいて第１のコンテンツオブジェクトに対する要求を受け取る。
本明細書で述べたように、要求はクライアントデバイス１３０からであってもよい。
さらに、コンテンツオブジェクトは、コンテンツソース１１０から受け取られてもよいメディアオブジェクト又は他の任意のオブジェクトであってもよい。
【００６０】
図４のステップ４０２において、プロキシキャッシュのアクセスログにおいて第１のコンテンツオブジェクトの一部を探索する。
一実施形態では、第１のコンテンツオブジェクトの一部は、アクセスログエントリである。
【００６１】
図４のステップ４０３において、プロキシキャッシュにおける第１のコンテンツオブジェクトの一部のサイズを計算する。
すなわち、キャッシュプロキシは、第１のコンテンツオブジェクトに関するエントリを有しておらず、したがってキャッシュに第１のコンテンツオブジェクトのいずれも存在しない、第１のコンテンツオブジェクトの一部（たとえばセグメント又はセグメントのグループ）が存在する、又はキャッシュにおいてセグメント化されていないオブジェクト全体が存在する可能性がある。
【００６２】
図４のステップ４０４において、第１のコンテンツオブジェクトの標準的に利用されるサイズを導出する。
たとえば、オブジェクトが以前にアクセスされたことがない場合、それはオブジェクトのフルサイズである。
しかしながら、以前にアクセスされたことがある場合、標準的に利用される部分のサイズを、それが閲覧された時間の各々の平均（たとえば平均アクセス持続時間）を取得することによって見つける。
【００６３】
図４のステップ４０５において、プロキシキャッシュにおける第１のコンテンツオブジェクトの一部のサイズを、要求された第１のコンテンツオブジェクトの標準的に利用されるサイズと比較する。
すなわち、ステップ４０３の方が大きいかステップ４０４の方が大きいかを見出すために比較を行う。
ステップ４０３の方が大きい場合、プロキシキャッシュがこの時点でそれ以上又は要求された第１のオブジェクトをインポートする必要はない。
しかしながら、ステップ４０４の方が大きい場合、第１のオブジェクトのさらなる部分（たとえばセグメント）が必要であり、キャッシュプロキシ１２０は、第１のオブジェクトの更なる部分をインポートするためにコンテンツソース１１０にアクセスしなければならない。
【００６４】
このように、適応的且つ遅延セグメンテーション戦略は、指数関数的セグメンテーション方法及び一様セグメンテーション方法の両方に対し、バイトヒット率が平均して約３０％優れている可能性があり、それは、サーバ作業負荷及びネットワークトラフィックが３０％低減することを表す。
【００６５】
要約すると、本発明の実施形態は、コンテンツの優先順位を決める方法及びシステムに関する。
これらの実施形態によれば、プロキシキャッシュのアクセスログを提供することにより、プロキシキャッシュにおける第１のコンテンツオブジェクトの一部のサイズを計算することができ、第１のコンテンツオブジェクトのセグメントの標準的に利用されるサイズを導出することができる。
そして、プロキシキャッシュにおける第１のコンテンツオブジェクトの一部のサイズと要求された第１のコンテンツオブジェクトの標準的に利用されるサイズとの比較を行うことができる。
これにより、キャッシュメモリのより効率的な利用を利用することができる。
【００６６】
このように、本発明の実施形態について説明した。
本発明を特定の実施形態で説明したが、本発明を、こうした実施形態によって限定されるものと解釈すべきではなく、むしろ以下の特許請求の範囲に従って解釈すべきである、ということが理解されるべきである。
【図面の簡単な説明】
【００６７】
【図１】本発明の一実施形態によるコンテンツを配信するシステムを示す。
【図２】本発明の一実施形態によるキャッシュのオブジェクトにアクセスするフローチャートである。
【図３】本発明の一実施形態によるキャッシュにおけるオブジェクトの置換のフローチャートである。
【図４】本発明の一実施形態によるコンテンツの優先順位を決める方法のフローチャートである。
【符号の説明】
【００６８】
１１０・・・コンテンツソース，
１２０・・・キャッシングプロキシ，
１３０・・・クライアントデバイス，
【図１】
2007510224.tif 000004
【図２】
2007510224.tif 000005
【図３】
2007510224.tif 000006
【図４】
2007510224.tif 000007
【国際調査報告】
2007510224.tif 000008
2007510224.tif 000009