(57)【要約】  システム及び方法は、キャッシュサーバを介しコンテンツサーバからクライアントへのコンテンツのダウンロードをスケジューリングする。ユーザは、ホットスポットなどのある場所であるサービス時間に以降の配信のためのコンテンツファイルをリクエストすることができる。キャッシュサーバは、これらのリクエストを受信し、相対的なサービス時間に依存した順序によりそれらを整理し、キャッシュサーバにまだ格納されていないコンテンツファイルのみをダウンロードすることによって冗長さを解消する。スケジューリングアルゴリズムは、キャッシュストレージキャパシティの制約の下で遅延を最小化する。
2007529072.tif 000002
【特許請求の範囲】
【請求項１】
ダウンロードシステムのためのダウンロードをスケジューリングする方法であって、
サービス時間と指定されたキャッシュサーバとを有するコンテンツファイルに対するリクエストを受信するステップと、
前記リクエストをジョブリストの先頭にあるコンテンツファイルに対するリクエストに初期化されたスケジューリングポインタを有するジョブリストにサービス時間による時間順にリストするステップと、
前記スケジューリングポインタにおける前記リクエストに対して求められるコンテンツファイルが、前記指定されたキャッシュサーバ上に格納されているか判断するステップと、
前記スケジューリングポインタにおける前記リクエストに対して求められるコンテンツファイルが、前記指定されたキャッシュサーバ上に格納されていないと判断されると、前記指定されたキャッシュサーバ上にフリースペースが存在するとき、前記スケジューリングポインタにおける前記リクエストに対して求められるコンテンツファイルを前記指定されたキャッシュサーバにダウンロードするステップと、
から構成される方法。
【請求項２】
請求項１記載の方法であって、さらに、
前記ダウンロードが完了すると、前記スケジューリングポインタを前記ジョブリストの次のリクエストに移行するステップを有する方法。
【請求項３】
請求項１記載の方法であって、さらに、
前記スケジューリングポインタにおけるリクエストに対して求められるコンテンツファイルが、前記指定されたキャッシュサーバに格納されていると判断すると、前記スケジューリングポインタにおけるリクエストを前記格納されているコンテンツファイルにリンクさせ、前記スケジューリングポインタを前記ジョブリストの次のリクエストに移行するステップを有する方法。
【請求項４】
請求項１記載の方法であって、
前記コンテンツファイルは、コンテンツサーバから前記指定されたキャッシュサーバにダウンロードされる方法。
【請求項５】
請求項１記載の方法であって、
前記ジョブリストは、前記指定されたキャッシュサーバに格納され、実行される方法。
【請求項６】
請求項１記載の方法であって、
前記ジョブリストは、新たなリクエストと受信すると、動的に更新される方法。
【請求項７】
請求項１記載の方法であって、さらに、
前記ジョブリスト上の他のすべてのリクエストより早期のサービス時間を有する新たなリクエストを受信すると、前記スケジューリングポインタにおけるリクエストの前で前記新たなリクエストを前記ジョブリストに挿入するステップと、
前記スケジューリングポインタを前記新たなリクエストに後方移動するステップと、
を有する方法。
【請求項８】
請求項１記載の方法であって、
前記指定されたキャッシュサーバは、ホットスポットキャッシュサーバである方法。
【請求項９】
請求項１記載の方法であって、
前記リクエストは、ユーザ装置によって生成される方法。
【請求項１０】
請求項１記載の方法であって、
前記リクエストは、コンテンツサーバによって受信され、前記指定されたキャッシュサーバを介しわたされる方法。
【請求項１１】
ジョブリストを有するキャッシュサーバと、
コンテンツファイルがサービス時間に前記キャッシュサーバ上で利用可能となるユーザリクエストを処理する手段と、
前記リクエストを前記ジョブリストに追加し、前記ジョブリストの先頭にあるコンテンツファイルに対するリクエストに初期化されるスケジューリングポインタを有する前記ジョブリストをサービス時間による時間順に編集する手段と、
前記スケジューリングポインタにおける前記リクエストによって求められるコンテンツファイルが、前記キャッシュサーバ上に格納されているか判断する手段と、
前記キャッシュサーバ上にフリースペースが存在し、前記スケジューリングポインタにおける前記リクエストによって求められるコンテンツファイルが、前記キャッシュサーバ上に格納されていないと判断されると、前記スケジューリングポインタにおける前記リクエストによって求められるコンテンツファイルを前記キャッシュサーバにダウンロードするリクエストをコンテンツソースに送信する手段と、
前記キャッシュサーバからのダウンロードリクエストを付与する手段と、
から構成されるシステム。
【請求項１２】
請求項１１記載のシステムであって、さらに、
前記スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルがダウンロードされると、前記スケジューリングポインタを前記ジョブリスト上で前方に移動する手段を有するシステム。
【請求項１３】
請求項１２記載のシステムであって、さらに、
前記スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルが、前記キャッシュサーバ上に格納されていると判断されると、前記スケジューリングポインタを前記ジョブリスト上で前方に移動する手段を有するシステム。
【請求項１４】
請求項１１記載のシステムであって、さらに、
前記スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルが、前記キャッシュサーバ上に格納されていると判断されると、前記スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルを前記スケジューリングポインタにおけるリクエストとリンクさせる手段を有するシステム。
【請求項１５】
請求項１１記載のシステムであって、さらに、
当該コンテンツソースからコンテンツファイルが前記キャッシュサーバにダウンロードされるコンテンツソースを有するシステム。
【請求項１６】
請求項１１記載のシステムであって、さらに、
新たなリクエストの受信により、前記ジョブリストを動的に更新する手段を有し、
前記ジョブリスト上の他のすべてのリクエストより早期のサービス時間を有する新たなリクエストが受信されると、前記新たなリクエストは、前記スケジューリングポインタにおけるリクエストの前に挿入され、前記スケジューリングポインタは、前記新たなリクエストに後方に移動されるシステム。
【請求項１７】
請求項１１記載のシステムであって、
前記キャッシュサーバは、ホットスポットキャッシュサーバであるシステム。
【請求項１８】
請求項１１記載のシステムであって、
前記コンテンツソースは、前記コンテンツファイルが格納されているコンテンツサーバ又は他のキャッシュサーバであるシステム。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
［発明の技術分野］
本発明は、一般にデータ通信及びコンテンツ配信ネットワークの技術分野に関し、特にコンテンツ配信ネットワークにおけるファイルのダウンロードをスケジューリングするシステム及び方法に関する。
［発明の背景］
映画などのサイズの大きなコンテンツについて、コンテンツクライアントは通常は、より良いクオリティと引き替えに配信遅延を容認することができる。しばしば、クライアントは、低いクオリティのストリーミング映像を即時に視聴するより、スケジュールされた時間に高いクオリティのダウンロード映像を視聴することを選択する。例えば、モバイルユーザは、セルラーモバイルネットワーク上にいる間に、予め映像をオーダーすることが可能であり、そして、ユーザが無線ＬＡＮホットスポットにアクセスしている間に、以降において映画をダウンロードすることが可能である。このように、モバイルユーザは、高い帯域幅と低いコストによりコンテンツを享受することができる。
【０００２】
近年、コンテンツ配信ネットワーク（ＣＤＮ）技術の利用がインターネットに拡がり、ウェブページのダウンロードが向上している。ＣＤＮは、異なる地理的位置において複数のキャッシュサーバを有する。ＣＤＮ技術の基本的な前提は、キャッシュサーバとクライアントとの間の低コストかつ高い帯域幅のリンクに依存する。クライアントがウェブページをリクエストするとき、リクエストされたウェブページが近くのキャッシュサーバのキャッシュに存在する場合、ダウンロードが迅速に行われる。そうでない場合、クライアントは遅延を受けるかもしれない。
【０００３】
典型的には、クライアントは、クライアントがコンテンツファイルを抽出することを所望する時間として指定する予想されるサービス時間を超えては遅延が延長されない場合、サイズの大きなコンテンツファイルをダウンロードするのに遅延を容認する可能性がある。従って、要求されたコンテンツファイルが現在クライアントの近傍のキャッシュサーバに存在しなくても、ダウンロードシステムが予想されるサービス時間前にコンテンツファイルをキャッシュサーバに転送する限り、クライアントは遅延を被ることはない。しかしながら、コンテンツサーバがコンテンツファイルを特定のキャッシュサーバにダウンロードするため、いくつかのクライアントリクエストを受信すると、スケジューリングアルゴリズムは、コンテンツサーバ、ネットワークリンク及びキャッシュサーバのリソースを最適化するのに使用されねばならない。
【０００４】
無線技術の進歩とリモートサイトダウンロードの導入は、コンテンツサーバ、ネットワークリンク及びキャッシュサーバのリソースを最適化するスケジューリングアルゴリズムに対する要求を増大させた。例えば、これらのスケジューリング問題は、これらの問題があらゆるタイプのＣＤＮに存在するという理解の下、無線及びリモートサイトダウンロード技術を利用したＣＤＮに関して説明されるが、本発明はそれに限定されるものではない。
【０００５】
無線技術の進歩によって、携帯情報端末（ＰＤＡ）、携帯電話とＰＤＡのハイブリッド、ラップトップコンピュータなどのモバイル／ワイヤレス装置は、セルラーモバイルネットワークを利用して、電子メールを送受信し、ウェブサービスを取得し、マルチメディアファイルをダウンロードすることができる。しかしながら、このようなセルラーネットワークを利用することは、映画、音楽、テレビプログラム、他のマルチメディアファイルなどの大きなコンテンツファイルをダウンロード又はストリーミングするのに効率的ではない。配信されるマルチメディアのビットあたりのコスト及びスピードは、モバイル装置のユーザがケーブルブロードバンド、ＤＳＬ、電話モデム又は他の有線ネットワーク接続などのより高い帯域幅の接続を利用してコンテンツウェブサーバからこのようなコンテンツファイルをダウンロードすることをよりコスト効率的なものとする。
【０００６】
移動時、モバイル装置のユーザは、しばしばセルラーネットワーク（すなわち、低い帯域幅ネットワーク）などのコスト効率性の低いネットワークのみにアクセスする。セルラーネットワークを介し大きなコンテンツファイルをダウンロードすることに関する問題や制約を軽減するため、コンテンツ配信ネットワーク（ＣＤＮ）としても知られているキャッシュサーバネットワークがより一般的になりつつある。ＣＤＮは、ウェブサイトのコンテンツファイルをキャッシュサーバから入手可能とするため、ウェブサイトオペレータとコンタクトし、これにより、ウェブサイトコンテンツサーバへのユーザリクエストは、ＣＤＮのキャッシュサーバより迅速、効率的及び／又は地理的に近傍で実現又は配信することが可能となる。例えば、ダウンロードシステムは、ユーザが第１時点において第１ネットワーク上のある一にいる間にコンテンツサーバからコンテンツファイルをリクエストし、第２の位置において、第２ネットワークを介し、及び／又は以降の第２時点に当該コンテンツファイルをダウンロードすることを可能にする。これは、リモートサイトダウンロード機能として知られる。リモートサイトダウンロード機能は、ＣＤＮ又はコンテンツサーバによって提供されるかもしれない。
【０００７】
これらの要求を満足するため、「ホットスポット」として知られ、キャッシュサーバの使用を通じてコスト効率的なダウンロードを容易にするパブリックアクセスポイントが開発された。ここで使用されるように、ホットスポットは、パブリックスペースの無線ブロードバンドコンピュータネットワークなどのワイヤレスローカルエリアネットワーク（ＷＬＡＮ）が確立された場所である。ホットスポットは、ＩＥＥＥ８０２．１１ｂ（Ｗｉ−Ｆｉ）規格を利用して毎秒１１メガビットの、又はＩＥＥＥ８０２．１１ｇを利用して毎秒５５メガビットの接続スピードを現在提供し、コーヒーショップ、レストラン、ホテル、空港、書店、コピーショップ、コンベンションセンター、他の公的にアクセス可能な場所などに配置されるかもしれない。ホットスポットでは、ＰＤＡ、ラップトップコンピュータ、携帯電話、ハイブリッドＰＤＡ携帯電話など、Ｗｉ−Ｆｉ対応モバイル装置がインターネットにアクセスし、大変コスト効率的に大きなコンテンツファイルをダウンロード又はストリーミングすることが可能である。
【０００８】
ホットスポットのインターネットアクセスは、一般にはワイヤレスカードを有するモバイル装置と通信する無線トランシーバを備えるワイヤレスルータによってユーザのモバイル装置に提供される。Ｗｉ−Ｆｉ対応でないモバイルユーザは、将来的にはすべてのモバイル装置がＷｉ−Ｆｉ対応となることが要素されるが、有線接続の場合にホットスポットインターネットサーバに接続してもよい。
【０００９】
現在、無線モバイル装置のユーザは、迅速なダウンロードのため、リモートコンテンツウェブサーバからコンテンツファイルを選択、リクエスト及び購入するため、ホットスポットにおいてインターネットにアクセスすることができる。しかしながら、モバイルユーザはしばしば、セルラー又は他の低スピードネットワークを介しコンテンツプロバイダウェブサイトからコンテンツファイルを選択し、モバイルユーザがコンテンツファイルを取得するための訪問中にコンテンツサーバウェブサイトに接続する必要なくホットスポットに訪れるとき、迅速なアクセスのため予めコンテンツファイルをダウンロードさせることが便利であるとわかるであろう。この状況では、モバイルユーザは、コンテンツが送信されるホットスポット／キャッシュサーバと、ユーザがコンテンツにアクセス及び受信することを所望する推定時間（すなわち、サービス時間）とを指定するコンテンツファイルに対するリクエストを自分のモバイル／ワイヤレス装置を介し生成する。
【００１０】
ホットスポットキャッシュサーバにダウンロードするためのファイルをリクエストすることはある効果を有するが、ユーザは現在のネットワークによりいくつかの問題に直面し、そのうちの１つは、指定されたキャッシュサーバにリクエストされたコンテンツファイルが到着することに関する遅延である。しばしば、ユーザはキャッシュサーバにアクセス可能となるため、リクエストされたコンテンツについて推定されたサービス時間以上待機しなければならない。この問題は、キャッシュネットワークのダウンロードが増えるに従って、悪化しつつある。
【００１１】
大部分のインターネットサービスにおけるダウンロードプロセスは、一般には、サーバ、ネットワーク及びクライアント状態に関係なくほとんど瞬時に行われる。瞬時のダウンロードシステムには、あったとしてもわずかしかスケジューリング問題は存在しない。このようなシステムのスケジューラは、コンテンツサーバの処理能力に基づき動作し、ファイルに対するリクエストの処理は、このようなリクエストが受信される順番に行われる。しかしながら、サービス時間情報による予めのリクエストが多くなるに従って、当該ネットワークに存在する特別な制約を考慮したキャッシュネットワーク（ＣＤＮ）環境においてコンテンツファイルをダウンロードするスケジューラを設計する必要がある。
［発明の開示］
本発明の課題は、ダウンロードシステムのためジョブのダウンロードをスケジューリングする方法及びシステムを提供することである。
【００１２】
他の課題は、サービス時間に関するダウンロード遅延を減少させるダウンロードシステムにおいてダウンロードをスケジューリングする方法及びネットワークを提供することである。
【００１３】
さらなる他の課題は、キャッシュサーバの利用を最大化するダウンロードシステムにおいてダウンロードをスケジューリングする方法及びネットワークを提供することである。
【００１４】
さらなる他の課題は、重複したコンテンツファイルをキャッシュサーバに格納することを回避するダウンロードシステムにおけるダウンロード方法及びネットワークを提供することである。
【００１５】
本発明の他の課題は、コンテンツサーバとキャッシュサーバ能力の両方を考慮したダウンロードシステムにおけるダウンロードをスケジューリングする方法及びネットワークを提供することである。
【００１６】
上記及び他の課題が、本発明によって満足される。ダウンロードシステムでは、コンテンツファイルをダウンロードするリクエストがコンテンツサービス時間（すなわち、コンテンツ利用時間）前になされるため、システムのスループットを向上させるダウンロードをスケジューリングする方法及びネットワークが考案可能であることが発見された。当該課題は、サーバ、ネットワーク及びキャッシュ能力の制約の下、ネットワークスループットを最大化することである。本発明は、有線と無線両方のネットワーク環境において利用可能である。
【００１７】
一特徴では、本発明は、ダウンロードシステム環境のためのダウンロードをスケジューリングする方法であって、指定されたキャッシュサーバにおけるサービス時間を有するコンテンツファイルに対するリクエストを受信するステップと、サービス時間による時間順に前記リクエストをジョブリストにリストするステップとを有する方法である。リクエストはまた、コンテンツファイルＵＲＬのデータセットとコンテンツファイルサイズとを有することが可能である。
【００１８】
リストの先頭に初期化されたスケジューリングポインタがある。ジョブリストは、好ましくは、コンテンツファイルに対する新たなリクエストが受信されると動的に更新され、新たなリクエストがスケジューリングポインタによって現在示されるリクエストの前に挿入される場合、スケジューリングポインタが後方に移動される。ジョブリストが生成及び編集されると、スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルが、すでに指定されたキャッシュサーバ上に格納されているか判断される。スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルが、すでに指定されたキャッシュサーバ上に格納されていないと判断される場合、フリースペースが利用可能になると、当該コンテンツファイルがキャッシュサーバにダウンロードされるよう要求される。このダウンロードが完了すると、ダウンロードされたコンテンツは、スケジューリングポインタにおけるリクエストとのリンクを有し、スケジューリングポインタは、ジョブリスト上の次のリクエストに前方に移動される。
【００１９】
しかしながら、スケジューリングポインタによって指示されるリクエストによって求められるコンテンツファイルがキャッシュサーバ上に存在する場合、当該リクエストは、好ましくは、格納されているコンテンツにリンクされ、スケジューリングポインタは、ジョブリスト上の次のリクエストに前方に移動される。これは、コンテンツファイルが同じキャッシュサーバ上に重複して格納されることを回避し、キャッシュサーバのストレージ使用を最大化する。
【００２０】
本発明は、コンテンツサーバ処理キャパシティを考慮するだけでなく、ストレージスペースなどのキャッシュサーバキャパシティを考える。キャッシュサーバは、ファイルを保持するためのフリーなスペースを有しない場合、リスト上の次のジョブを処理することはできない（すなわち、リクエストされたコンテンツファイルをダウンロードする）。キャッシュサーバフリースペースが、リクエストの予想されるサービス時間でなくクライアントのランダムピックアップに依存しているため、キャッシュサーバフリースペースが連続的にモニタされることが好ましい。本発明は、サーバ及びキャッシュキャパシティの制約の下でスループットを最大化する。
【００２１】
好ましくは、コンテンツファイルが、コンテンツソースから指定されたキャッシュサーバにダウンロードされる。ここで使用されるように、コンテンツソースは、所望のコンテンツファイルを含む指定されていないキャッシュサーバ又はコンテンツウェブサーバを有する。ジョブリストは、指定されたキャッシュサーバ上に格納され、実行することが可能である。さらに、指定されたチャックサーバはホットスポットキャッシュサーバであることが好ましい。リクエストは、ＰＤＡ、携帯電話、ラップトップなどのモバイル電子装置又はデスクトップコンピュータなどの固定された装置を含む無線又は有線ユーザ装置によって生成可能である。
【００２２】
他の特徴では、本発明は、ジョブリストとコンテンツストレージスペースとを有するキャッシュサーバと、コンテンツファイルがキャッシュサーバ上に利用可能とされるサービス時間を有するリクエストを生成するよう構成されるユーザ装置と、サービス時間による時間順に編集され、ジョブリストの先頭において初期化されるスケジューリングポインタを有するジョブリストにリクエストを追加する手段と、スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルが、キャッシュサーバ上に格納されているか判断する手段と、キャッシュサーバ上にフリースペースが検出され、スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルがキャッシュサーバ上に格納されていないと判断されると、スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルをキャッシュサーバにダウンロードする手段とを有するシステムである。
【００２３】
好ましくは、本システムは、スケジューリングポインタによって指示されるリクエストによって求められるコンテンツがダウンロードされるとき、スケジューリングポインタをジョブリスト上の次のリクエストに前方に移動する手段を有するべきである。さらに、本システムは、好ましくは、スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルがキャッシュサーバ上に存在するとき、スケジューリングポインタをジョブリスト上の次のリクエストに前方に移動する手段を有する。何れの実施例でも、本システムは、スケジューリングポインタをジョブリスト上の次のリクエストに移動する前に、スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルからリクエストへのリンクを生成する手段を有することが可能である。
【００２４】
本発明のシステムはさらに、コンテンツをキャッシュサーバにダウンロードするコンテンツソースを有することが可能である。コンテンツソースは、コンテンツサーバ又は他のキャッシュサーバとすることが可能である。
［発明を実行するためのモード］
図１は、ダウンロードシステム１００を示す。ダウンロードシステム１００は、ユーザ装置１０（矩形のボックスにより一般的に示される）と、コンテンツサーバ２０と、キャッシュサーバ３０とを有する。ユーザ装置１０は、本例では、比較的低スピード（すなわち、低い帯域幅）により動作するワイヤレスセルラーネットワークから構成される第１ネットワークａを介しコンテンツサーバと通信し、データを送受信する。コンテンツサーバ２０は、高スピード（すなわち、高い帯域幅）を有するインターネットなどの第２ネットワークｂを介しキャッシュサーバ３０と通信し、データを送受信する。キャッシュサーバ３０とユーザ装置１０は、互いに通信し、例えば、コーヒーショップや空港などの無線又は有線接続を提供可能なホットスポットｃにおいてローカルにデータを送受信する。
【００２５】
本例では、ユーザ装置１０は、ウェブ対応ＰＤＡや携帯電話などのワイヤレス装置を有する。本例では、コンテンツサーバ２０は、映画を購入及びダウンロード可能なウェブサイトを有する。本例では、キャッシュサーバ３０は、複数のユーザによってアクセス可能なホットスポットキャッシュサーバを有する。
【００２６】
図２は、本発明の一実施例によるダウンロードシステム１００の動作方法のフローチャートを示す。図２は、図１のダウンロードシステム１００に関して説明されるが、様々な実施例及びハードウェアに代替可能であるということが理解される。
【００２７】
ユーザが以降においてコンテンツファイルを取得することを決定するが、コンテンツファイルを即時にリクエストすることを所望するとき、ユーザは、第１リモート一においてユーザ装置１０を介し所望のコンテンツファイルに対するリクエストを生成する。このリクエストは、ユーザがファイルを取得することを所望するサービス時間を含む。当該リクエストはまた、ユーザがコンテンツファイルを直接的に又は間接的に抽出することを所望するキャッシュサーバを指定する。あるいは、当該リクエストは、ダウンロードシステム１００による抽出のため、特定のキャッシュサーバに割り当てることができる。ユーザ装置１０により当該リクエストを生成すると、リクエストはキャッシュサーバ３０に直接わたされるか、あるいは、コンテンツサーバ２０を介し間接的にわたされる。
【００２８】
キャッシュサーバ３０は、図２のステップ２００において、コンテンツファイルに対するリクエストを受け取る。当該リクエストを受信すると、ステップ２１０において、キャッシュサーバ３０は、リクエストに関するサービス時間を決定し、当該リクエストを以前のリクエストを含むジョブリストに追加する。このジョブリストは、処理のためキャッシュサーバ３０によって受信されるコンテンツファイルに対するリクエストのすべてのリストから構成される。キャッシュサーバ３０は、ステップ２２０において、サービス時間に従ってリクエストが時間順に現れるようにジョブリストを構成する。キャッシュサーバ３０は、ジョブリストの先頭に初期化されたスケジューリングポインタを有する。新たなリクエストはしばしばキャッシュサーバ３０に定期的に到着するため、キャッシュサーバは、ジョブリストを動的に更新し、スケジューリングポインタによってそれ以前に特定されるリクエストの前に新たなリクエストを挿入すると、スケジューリングポインタを後方に移動させる。適切にプログラムされたプロセッサと従来のハードウェア（図示せず）は、すべてのプロセスステップと決定を実行する。
【００２９】
ジョブリストが更新及び編集されるとき、スケジューリングポインタは、スケジューリングされるリクエストであるジョブリストのリクエストを指示する。ステップ２３０において、キャッシュサーバ３０は、ジョブリスト上でスケジューリングポインタによって現在特定されるリクエストが、キャッシュサーバ３０のメモリ内にすでに格納されているコンテンツファイルをリクエストしているか判断する。そうである場合、キャッシュサーバ３０はステップ２４０に移行する。ステップ２４０において、キャッシュサーバは、当該コンテンツファイルをスケジューリングポインタによって特定されるリクエストにリンクし、これにより、対応するユーザは、ホットスポット位置への到着に続くユーザ装置１０によるキャッシュサーバへのアクセスにより、所望のコンテンツファイルを抽出することができる。ステップ２４０が終了すると、ステップ２５０において、スケジューリングポインタはジョブリスト上の次のリクエストに移行する。これは、キャッシュサーバ３０のメモリ内に重複したコンテンツファイルを格納することを回避し、これにより、キャッシュサーバの限定されたメモリスペースを節約及び最大化する。
【００３０】
しかしながら、ステップ２３０において、リクエストされたコンテンツがキャッシュサーバ３０のチェックにより存在しない場合、ステップ２６０が実行され、キャッシュサーバ３０上にスケジューリングポインタによって特定されるリクエストに指定されるコンテンツファイルをダウンロードするのに十分なフリースペースが存在するか判断される。ここで使用されるように、キャッシュサーバ３０上にリンクされたコンテンツファイルを上書きすることなくスケジューリングポインタに当該リクエストに係るコンテンツファイルを格納するための適切なメモリスペースが存在するとき、フリースペースは存在する。この状況は、キャッシュサーバメモリ上に十分なエンプティスペースが存在するとき、又は、メモリに格納されるコンテンツファイルが置換可能であるときに存在する。メモリに格納されているコンテンツファイルは、当該ファイルに対するリクエストにリンクが存在しないとき、置換可能である。リクエストへのリンクは、当該リクエストに対する対応するユーザが当該コンテンツファイルをユーザ装置１０に抽出（すなわち、ダウンロード）するとき、又は、当該リクエストが期限切れとなるとき（すなわち、推定されるサービス時間を超えて所定の時間が経過したとき）、削除される。
【００３１】
ステップ２６０の実行中に十分なスペースが存在しない場合、そのときステップ２７０が実行され、キャッシュサーバ３０は、ステップ２６０を再実行する前にフリースペースが利用可能になるまで、既存のリンクされたジョブを処理する。
【００３２】
ステップ２６０において十分なスペースが存在するとき、ステップ２８０が実行され、キャッシュサーバ３０は、スケジューリングポインタによってジョブリスト上で指定されるリクエストによって求められているコンテンツファイルをリクエストする信号をコンテンツサーバ２０に送信する。ステップ２８０において、コンテンツサーバ２０は、スケジューリングポインタによって指示されるリクエストによってリクエストされるコンテンツファイルをダウンロードする信号に対してキャッシュサーバに与えられた時間により応答し、コンテンツファイルは、格納のために与えられた時間にキャッシュサーバ３０にダウンロードされる。ダウンロードが完了すると、スケジューリングポインタにおけるリクエストは、ステップ２９０において、ダウンロードされたファイルにリンクされる。その後、スケジューリングポインタは、ステップ２２０に戻る前に、ステップ３００においてジョブリスト上の次のリクエストに移行する。
【００３３】
本発明は、その目的の１つとして、ダウンロードシステムへの遅延ペナルティと考えられている予想されるサービス時間以降に延長されるジョブ数を最小化することである。通常のコンピュータクライアントは、いわゆる早着（ｅａｒｌｉｎｅｓｓ）ペナルティなくサーバがキャパシティを有するのと同程度に早期にダウンロードをリクエストすることが可能である一方、ＣＤＮでは、キャッシュサーバは、サーバがキャパシティを有するのと同程度に早期にダウンロードをリクエストことはできない。これは、早着ペナルティを意味する。キャッシュサーバストレージの利用は、早着のペナルティである。トータルのキャッシュサーバストレージが一定のストレージキャパシティを有すると仮定することは、
問題を簡単化するであろう。従って、早着ペナルティは、早着制約となる。本発明の１つの課題は、一定の早着制約により遅延ペナルティ数を最小化することである。
【００３４】
新たなリクエストの到着を処理する（ダウンロードのためなど）リクエストがリクエスト処理をトリガーする必要がないことに留意されたい。リクエスト到着及びリクエスト処理は互いに直交して存在する可能性があり、新たなリクエストの挿入がリクエストリストに挿入され、リクエスト到着とリクエスト処理との間で行われる接続のみを構成する。
【００３５】
説明のため、図２に示されるスケジューリングアルゴリズムは、上記目的と制約に基づき「ＥＴＳＯ（Ｅａｒｌｉｅｓｔ  Ｔｒａｎｓｍｉｓｓｉｏｎ  ｉｎ  Ｓｅｒｖｉｃｅ  Ｏｒｄｅｒ）」と呼ばれる。ＥＴＳＯスケジューリングアルゴリズムは、送信キャパシティとキャッシュサーバキャパシティの双方の利用を最大化するため、キャッシュサーバ制約の下で可能な限り早期にコンテンツファイルを送信しようとする。ＥＴＳＯアルゴリズムは、リアルタイムとオフラインの両方により動作可能である。リアルタイムのケースは、リクエスト処理が進捗するに従って、新たなリクエストが到着するときに行われる。オフラインのケースは、それらの予想されるサービス時間によるすべてのリクエストが、リクエスト処理を開始する前に利用可能になることを仮定している。オフラインのケースでは、ＥＴＳＯアルゴリズムは、コンテンツサイズが一定の場合には、自らを最適なアルゴリズムとして証明する。可変のコンテンツサイズの場合には、最適化の目的は、遅延ジョブ数又は遅延レートだけでなく、すなわち、それらのデッドラインを逃すことだけでなく、遅延ジョブのコンテンツのトータルサイズに関するものである。このような目的関数は、サーバが目的を満足するため、以降の予想されるサービス時間によりより大きな又はより小さなコンテンツを処理する必要がある可能性があるため、予想されるサービス時間順序ではない送信をときどき要求しうる。これは、ジョブがそれの予想されるサービス時間の近傍で処理するときに発生する。システム構成が低い遅延レートを与える可能性がある場合、これはそれほど頻繁には発生しない。従って、サービスオーダー（ＥＴＳアルゴリズムの早期の送信はもはや最適ではないが、キャッシュ制約による早期の送信の原理は、依然として有効であり、可変コンテンツサイズシステムにおいて使用可能である。
【００３６】
本発明におけるスケジューリング問題は、以下のように定義することができる。すなわち、コンテンツサーバ上では、Ｋ個の異なるコンテンツファイルが存在する。すべてのコンテンツファイルは等しいサイズを有し、キャッシュサーバにダウンロードするのに同じ時間ｐを要する。キャッシュサーバ上では、時間ＴのサイズＮのリクエストセットＲ＝｛ｒｉ｝が存在する。キャッシュサイズはＣである。各リクエストｒｉ＝（ｋｉ，ｄｉ）はコンテンツｋｉに対するものであり、予想されるサービス時間ｄｉを有する。一般性を失うことなく、Ｎ個のリクエストに対する予想されるサービス時間の順序は、ｉ＜ｊの場合に、ｄｉ＜ｄｊとされる。スケジューリング問題は、時間シーケンスＳ＝｛ｓｉ｝を求めることであり、ここで、ｓｉはリクエストｉがスケジューリングされる時間である。「スケジューリングされた」とは、リクエストされたコンテンツがキャッシュサーバにダウンロードされる時間、すなわち、送信スタートの代わりに送信エンドとして定義することができる。最小のサービス遅延数、すなわち、ｓｉ＞ｄｉの出現数をもたらすスケジュールＳが検索される。
【００３７】
適切なＥＴＳＯスケジュールＳＥＴＳＯは、以下のステップに従う。
１．リクエストｒ１がｓ１＝ｄ１においてスケジューリングされ、ｄ１’＝ｄ１とされ、ｄｉ’は、ｋｉがキャッシュに存在しなければならないときまでの時間である。現在のスケジュール時間をｔ＝ｓ１とする。
２．ｉ＝２〜Ｎ（リクエスト数）について、
Ａ．コンテンツファイルｋｉがキャッシュに存在する場合、ｓｉ＝ｔ、ｄｊ’＝ｔ−ｐとし（ただし、ｊはコンテンツファイルｋｉに対する直近のリクエストである）、
Ｂ．そうでない場合には、ｔ’≧ｔとなるまで待機し、この結果、ｄｉ≧ｔ’＋ｐとなる場合、ＧＳ（ｔ’）＜Ｃ／ｐとなり、ｓｉ＝ｔ’＋ｐ、ｄｉ’＝ｄｉ、及びｔ＝ｔ’＋ｐとされ、
Ｃ．そうでない場合には、ｓｉ＝∞（スケジューリング失敗、遅延＋＋）となる。
【００３８】
ＧＳ（ｔ）＝Σｉｐ［Θ（ｔ−ｓｉ＋ｐ）−Θ（ｔ−ｄｉ’）］は、現在時点ｔにおけるキャッシュに保持されねばならないコンテンツのトータルサイズであり、Θ（ｘ）は、ユニットステップ関数であり、すなわち、ｘ＞０である場合には、Θ（ｘ）＝１とされ、そうでない場合には、Θ（ｘ）＝０となる。Θ（ｔ−ｓｉ＋ｐ）−Θ（ｔ−ｄｉ’）は、それの送信スタート（ｓｉ−ｐ）からそれのサービス時間（ｄｉ）又は次の同じコンテンツリクエスト（ｄｉ’）の送信スタートまでのリクエストｉのキャッシュ要求を意味する。
【００３９】
第１ステップは初期化であり、第２ステップは、ｒＮまですべてのリクエストをスケジューリングするためのループである。当該ループ内の各ステップは、以下のように説明することができる。
【００４０】
ステップ２Ａ：リクエストされたコンテンツは、キャッシュ内にある。現在時点でリクエストｒｉをスケジューリングせよ。リクエストｒｉは、ｊ＜ｉに対してｄｉ≧ｄｊとなるまで、コンテンツｋｉをキャッシュに格納することを求めるため、リクエストｒｊがコンテンツｋｉ（＝ｋｊ）をｓｉ−ｐより多く格納することを求める必要はない。ｄ’を導入することは、キャッシュストレージをカウントすることを回避するためであり、すなわち、ＧＳ（ｔ）におけるｄ’の使用は、同一コンテンツについて重複したキャッシュ期間を有しなくなる。
【００４１】
ステップ２Ｂ：キャッシュがフルである場合、すべてのそれのスケジューリングされたリクエストを有する少なくとも１つのコンテンツがサービスされるとき、ｔ’まで待機する必要がある。まだダウンロードする時間がある場合、すなわち、ｄｉ≧ｔ’＋ｐとなる場合、ｓｉ＝ｔ’＋ｐにおいてリクエストｒｉをスケジューリングする。それは新たにキャッシュされたコンテンツであり、そのため、ｋｉはｄｉ’＝ｄｉとなるまで格納されなければならない。時間はｔ＝ｔ’＋ｐに進捗する。
【００４２】
ステップ２Ｃ：ダウンロードする時間がない場合、ｓｉ＝∞とされる。スケジューリングの失敗が発生する。
【００４３】
ＥＴＳＯスケジューリングアルゴリズムは、キャッシュ制約の下、可能な限り早期にリクエストを送信しようとする。それは、送信キャパシティとキャッシュキャパシティの両方の使用を最大化する。ＥＴＳＯアルゴリズムが与えられた目的関数、すなわち、遅延発生数の最小化のための最適なアルゴリズムであるということは証明可能である。ｉ個のリクエストまで、最適なスケジューリングは、（１）最小遅延数と、（２）直近のスケジュールｓｉの最も早期のスケジュール時間によるスケジュールである。
【００４４】
第１リクエストは一定のスケジュールｓ１＝ｄ１を有し、それは時間がｔ＝ｄ１−ｐにおいてスタートすることを意味すると仮定する。第２リクエストは、ＥＴＳＯにより最適であると証明可能である。すなわち、最も早い時間は、ｔ＋ｐである。ｔ＋ｐ＞ｄ２である場合、ｓ２＝ｔ＋ｐは遅延し、これにより、第３リクエスト以降をスケジューリングする必要がある。一般性を失うことなく、ｄ２≧ｄ１＋ｐを仮定する。Ｓ２＝｛ｓ１＝ｄ１，ｓ２＝ｄ１＋ｐ｝が上記２つの基準による最適なスケジュールであることは明らかである。
【００４５】
帰納法を用いて、リクエストｒｉまで、ＥＴＳＯアルゴリズムがスケジュールＳｉ＝｛ｓ１，．．．，ｓｉ｝により最適であると仮定する。リクエストｒｉ＋１に対するコンテンツｋｉ＋１が現在時点ｔ＝ｓｉにおいてキャッシュに存在する場合、ｔ’＝ｔ＝ｓｉとなる。この場合、Ｓｉ＋１＊は、等しい遅延と等しい直近のスケジュール時間を有する。従って、Ｓｉ＋１＝｛Ｓｉ，ｓｉ＋１＝ｓｉ｝は最適である。リクエストｒｉ＋１に対するコンテンツｋｉ＋１がキャッシュなく、ＥＴＳＯアルゴリズムに従って、ｒｉ＋１が以前のリクエストの後にスケジューリングされる場合、Ｓｉ＋１＊＝｛Ｓｉ，ｓｉ＋１＝ｔ’＋ｐ｝は、ｒｉ＋１に対する最も速いスケジュールであり、ここで、ｔ’≧ｓｉは、ＧＳｉ（ｔ’）＜Ｃ／ｐを満たす最小値である。キャッシュ状態ＧＳｉ（ｔ）は、ｔ’まで影響を受けない。ＥＴＳＯアルゴリズムは、ｓｉ後の可能な最も早いｓｉ＋１を選択する。この場合、スケジュールＳｉ＋１＊＝｛ｓ１，．．．，ｓｉ＋１｝もまた最適とならなければならない。
【００４６】
しかしながら、以前のｉ個のスケジュール間でリクエストｒｉ＋１をスケジューリングすることは可能であるか。スケジュールＳｉ＋１＝｛ｓａ，．．．，ｓｉ＋１＝ｔ１，ｓｂ＝ｔ２，．．．，ｓｌ＝ｔｍ｝が存在すると仮定すると、すべての可能なＳｉ＋１に対する遅延数は、Ｓｉ＋１＊以上となることが証明可能である。
【００４７】
ｄｉ＋１≧ｄｌ≧ｓｌであるため、有効なスケジュールＳｉ＋１はキャッシュ制約ＧＳ（ｔ）を満足しなければならない。リクエストｒｂとｒｉ＋１についてスケジュールＳを交換するスケジュールＳｉ＋１’＝｛ｓａ，．．．，ｓｂ＝ｔ１，ｓｉ＋１＝ｔ２，．．．，ｓｌ＝ｔｍ｝を考える。そのとき、リクエストｒｂについて、キャッシュ占有の差は、［Θ（ｔ−ｔｌ＋ｐ）−Θ（ｔ−ｄｂ’）］−［Θ（ｔ−ｔ２＋ｐ）−Θ（ｔ−ｄｂ’）］＝［Θ（ｔ−ｔｌ＋ｐ）−Θ（ｔ−ｔ２＋ｐ）］となる。リクエストｒｉ＋１について、キャッシュ占有の差は、［Θ（ｔ−ｔ２＋ｐ）−Θ（ｔ−ｄｉ＋１）］−［Θ（ｔ−ｔ１＋ｐ）−Θ（ｔ−ｄｉ＋１）］＝［Θ（ｔ−ｔ２＋ｐ）−Θ（ｔ−ｔ１＋ｐ）］となる。従って、ＧＳ’（ｔ）＝ＧＳ（ｔ）≦Ｃ／ｐとなる。
【００４８】
ｓｂに対するキャッシュの増加は、ｓｉ＋１に対するキャッシュの減少によって相殺される。リクエストｒｂが早期にスケジューリングされるため、遅延を招くことはない。ｓｉ＋１＝ｔ２＜ｓｌ≦ｄｌ≦ｄｉ＋ｌであるため、リクエストｒｉ＋１についてもまた遅延を招かない。直近のスケジュールは、依然としてｓｌ＝ｔｍである。これは、Ｓｉ＋１’がＳｉ＋１と同様であることを証明する。同様にして、Ｓｉ＋１における直近のスケジュールによりスワップするまで、リクエストｒｂの後の次にスケジューリングされるリクエストとリクエストｒｉ＋１とをスワップすることが可能である。これは、以前のｉ個のリクエストの直近のスケジュールの後のリクエストｒｉ＋１をスケジューリングすることが、ｉ個のリクエストに対する以前のスケジュールの間のスケジューリングすることと少なくとも同様であることを証明する。
【００４９】
以前のｉ個のリクエストの直近のスケジュールの後、リクエストｒｉ＋１がスケジューリングされる場合、ＥＴＳＯアルゴリズムが可能な最も早期のｓｉ＋１を与えることは以前に示された。
【００５０】
ｉ＝１，２であるとき、Ｓ２が最適であることを示す。最初のｉ個のリクエストについて、Ｓｉが最適であると仮定すると、Ｓｉ＋１＊＝｛Ｓｉ，ｓｉ＋１＝ｔ’｝が最初の（ｉ＋１）個のリクエストについて最適なスケジュールであることを示す。これは、ＥＴＳＯアルゴリズムに基づくスケジュールが、他の何れのスケジュールと少なくとも同程度良好である、すなわち、最適なスケジュールであることを証明する。
【００５１】
本発明が当業者が容易にそれを構成及び使用することが可能な程度まで十分詳細に説明及び図示されたが、本発明の趣旨及び範囲から逸脱することなく、様々な代替、改良及び改善が容易に明らかであろう。特に、本発明は、リモートサイトダウンロード機能を利用したＣＤＮに限定されるものではない。本発明は、すべてのキャッシュネットワーク環境に適用可能である。
【図面の簡単な説明】
【００５２】
【図１】図１は、本発明の一実施例によるコンテンツリクエスト及びコンテンツダウンロードが異なるネットワークを使用するダウンロードシステムの概略を示す。
【図２】図２は、本発明の一実施例によるリモートダウンロードシステムにおけるダウンロードをスケジューリングする方法のフローチャートを示す。
【図１】
2007529072.tif 000003
【図２】
2007529072.tif 000004
【手続補正書】
【提出日】平成17年8月25日(2005.8.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ダウンロードシステムのためのダウンロードをスケジューリングする方法であって、
サービス時間と指定されたキャッシュサーバとを有するコンテンツファイルに対するリクエストを受信するステップと、
前記リクエストをジョブリストの先頭にあるコンテンツファイルに対するリクエストに初期化されたスケジューリングポインタを有するジョブリストにサービス時間による時間順にリストするステップと、
前記スケジューリングポインタにおける前記リクエストに対して求められるコンテンツファイルが、前記指定されたキャッシュサーバ上に格納されているか、そして前記指定されたキャッシュサーバ上に、前記リクエストに対して求められるコンテンツファイルを格納するフリースペースが存在するか判断するステップと、
前記スケジューリングポインタにおける前記リクエストに対して求められるコンテンツファイルが、前記指定されたキャッシュサーバ上に格納されておらず、前記指定されたキャッシュサーバ上に、前記リクエストに対して求められるコンテンツファイルを格納するフリースペースが存在すると判断されると、前記スケジューリングポインタにおける前記リクエストに対して求められるコンテンツファイルを前記指定されたキャッシュサーバにダウンロードするステップと、
から構成される方法。
【請求項２】
請求項１記載の方法であって、さらに、
前記ダウンロードが完了すると、前記スケジューリングポインタを前記ジョブリストの次のリクエストに移行するステップを有する方法。
【請求項３】
請求項１記載の方法であって、さらに、
前記スケジューリングポインタにおけるリクエストに対して求められるコンテンツファイルが、前記指定されたキャッシュサーバに格納されていると判断すると、前記スケジューリングポインタにおけるリクエストを前記格納されているコンテンツファイルにリンクさせ、前記スケジューリングポインタを前記ジョブリストの次のリクエストに移行するステップを有する方法。
【請求項４】
請求項１記載の方法であって、
前記コンテンツファイルは、コンテンツサーバから前記指定されたキャッシュサーバにダウンロードされる方法。
【請求項５】
請求項１記載の方法であって、
前記ジョブリストは、前記指定されたキャッシュサーバに格納され、実行される方法。
【請求項６】
請求項１記載の方法であって、
前記ジョブリストは、新たなリクエストと受信すると、動的に更新される方法。
【請求項７】
請求項１記載の方法であって、さらに、
前記ジョブリスト上の他のすべてのリクエストより早期のサービス時間を有する新たなリクエストを受信すると、前記スケジューリングポインタにおけるリクエストの前で前記新たなリクエストを前記ジョブリストに挿入するステップと、
前記スケジューリングポインタを前記新たなリクエストに後方移動するステップと、
を有する方法。
【請求項８】
請求項１記載の方法であって、
前記指定されたキャッシュサーバは、ホットスポットキャッシュサーバである方法。
【請求項９】
請求項１記載の方法であって、
前記リクエストは、ユーザ装置によって生成される方法。
【請求項１０】
請求項１記載の方法であって、
前記リクエストは、コンテンツサーバによって受信され、前記指定されたキャッシュサーバを介しわたされる方法。
【請求項１１】
ジョブリストを有するキャッシュサーバと、
コンテンツファイルがサービス時間に前記キャッシュサーバ上で利用可能となるユーザリクエストを処理する手段と、
前記リクエストを前記ジョブリストに追加し、前記ジョブリストの先頭にあるコンテンツファイルに対するリクエストに初期化されるスケジューリングポインタを有する前記ジョブリストをサービス時間による時間順に編集する手段と、
前記スケジューリングポインタにおける前記リクエストによって求められるコンテンツファイルが、前記キャッシュサーバ上に格納されているか、そして前記指定されたキャッシュサーバ上に、前記リクエストに対して求められるコンテンツファイルを格納するフリースペースが存在するか判断する手段と、
前記スケジューリングポインタにおける前記リクエストによって求められるコンテンツファイルが、前記キャッシュサーバ上に格納されておらず、前記指定されたキャッシュサーバ上に、前記リクエストに対して求められるコンテンツファイルを格納するフリースペースが存在すると判断されると、前記スケジューリングポインタにおける前記リクエストによって求められるコンテンツファイルを前記キャッシュサーバにダウンロードするリクエストをコンテンツソースに送信する手段と、
前記キャッシュサーバからのダウンロードリクエストを付与する手段と、
から構成されるシステム。
【請求項１２】
請求項１１記載のシステムであって、さらに、
前記スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルがダウンロードされると、前記スケジューリングポインタを前記ジョブリスト上で前方に移動する手段を有するシステム。
【請求項１３】
請求項１２記載のシステムであって、さらに、
前記スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルが、前記キャッシュサーバ上に格納されていると判断されると、前記スケジューリングポインタを前記ジョブリスト上で前方に移動する手段を有するシステム。
【請求項１４】
請求項１１記載のシステムであって、さらに、
前記スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルが、前記キャッシュサーバ上に格納されていると判断されると、前記スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルを前記スケジューリングポインタにおけるリクエストとリンクさせる手段を有するシステム。
【請求項１５】
請求項１１記載のシステムであって、さらに、
当該コンテンツソースからコンテンツファイルが前記キャッシュサーバにダウンロードされるコンテンツソースを有するシステム。
【請求項１６】
請求項１１記載のシステムであって、さらに、
新たなリクエストの受信により、前記ジョブリストを動的に更新する手段を有し、
前記ジョブリスト上の他のすべてのリクエストより早期のサービス時間を有する新たなリクエストが受信されると、前記新たなリクエストは、前記スケジューリングポインタにおけるリクエストの前に挿入され、前記スケジューリングポインタは、前記新たなリクエストに後方に移動されるシステム。
【請求項１７】
請求項１１記載のシステムであって、
前記キャッシュサーバは、ホットスポットキャッシュサーバであるシステム。
【請求項１８】
請求項１１記載のシステムであって、
前記コンテンツソースは、前記コンテンツファイルが格納されているコンテンツサーバ又は他のキャッシュサーバであるシステム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
［発明の技術分野］
本発明は、一般にデータ通信及びコンテンツ配信ネットワークの技術分野に関し、特にコンテンツ配信ネットワークにおけるファイルのダウンロードをスケジューリングするシステム及び方法に関する。
［発明の背景］
映画などのサイズの大きなコンテンツについて、コンテンツクライアントは通常は、より良いクオリティと引き替えに配信遅延を容認することができる。しばしば、クライアントは、低いクオリティのストリーミング映像を即時に視聴するより、スケジュールされた時間に高いクオリティのダウンロード映像を視聴することを選択する。例えば、モバイルユーザは、セルラーモバイルネットワーク上にいる間に、予め映像をオーダーすることが可能であり、そして、ユーザが無線ＬＡＮホットスポットにアクセスしている間に、以降において映画をダウンロードすることが可能である。このように、モバイルユーザは、高い帯域幅と低いコストによりコンテンツを享受することができる。
【０００２】
近年、コンテンツ配信ネットワーク（ＣＤＮ）技術の利用がインターネットに拡がり、ウェブページのダウンロードが向上している。ＣＤＮは、異なる地理的位置において複数のキャッシュサーバを有する。ＣＤＮ技術の基本的な前提は、キャッシュサーバとクライアントとの間の低コストかつ高い帯域幅のリンクに依存する。クライアントがウェブページをリクエストするとき、リクエストされたウェブページが近くのキャッシュサーバのキャッシュに存在する場合、ダウンロードが迅速に行われる。そうでない場合、クライアントは遅延を受けるかもしれない。
【０００３】
典型的には、クライアントは、クライアントがコンテンツファイルを抽出することを所望する時間として指定する予想されるサービス時間を超えては遅延が延長されない場合、サイズの大きなコンテンツファイルをダウンロードするのに遅延を容認する可能性がある。従って、要求されたコンテンツファイルが現在クライアントの近傍のキャッシュサーバに存在しなくても、ダウンロードシステムが予想されるサービス時間前にコンテンツファイルをキャッシュサーバに転送する限り、クライアントは遅延を被ることはない。しかしながら、コンテンツサーバがコンテンツファイルを特定のキャッシュサーバにダウンロードするため、いくつかのクライアントリクエストを受信すると、スケジューリングアルゴリズムは、コンテンツサーバ、ネットワークリンク及びキャッシュサーバのリソースを最適化するのに使用されねばならない。
【０００４】
無線技術の進歩とリモートサイトダウンロードの導入は、コンテンツサーバ、ネットワークリンク及びキャッシュサーバのリソースを最適化するスケジューリングアルゴリズムに対する要求を増大させた。例えば、これらのスケジューリング問題は、これらの問題があらゆるタイプのＣＤＮに存在するという理解の下、無線及びリモートサイトダウンロード技術を利用したＣＤＮに関して説明されるが、本発明はそれに限定されるものではない。
【０００５】
無線技術の進歩によって、携帯情報端末（ＰＤＡ）、携帯電話とＰＤＡのハイブリッド、ラップトップコンピュータなどのモバイル／ワイヤレス装置は、セルラーモバイルネットワークを利用して、電子メールを送受信し、ウェブサービスを取得し、マルチメディアファイルをダウンロードすることができる。しかしながら、このようなセルラーネットワークを利用することは、映画、音楽、テレビプログラム、他のマルチメディアファイルなどの大きなコンテンツファイルをダウンロード又はストリーミングするのに効率的ではない。配信されるマルチメディアのビットあたりのコスト及びスピードは、モバイル装置のユーザがケーブルブロードバンド、ＤＳＬ、電話モデム又は他の有線ネットワーク接続などのより高い帯域幅の接続を利用してコンテンツウェブサーバからこのようなコンテンツファイルをダウンロードすることをよりコスト効率的なものとする。
【０００６】
移動時、モバイル装置のユーザは、しばしばセルラーネットワーク（すなわち、低い帯域幅ネットワーク）などのコスト効率性の低いネットワークのみにアクセスする。セルラーネットワークを介し大きなコンテンツファイルをダウンロードすることに関する問題や制約を軽減するため、コンテンツ配信ネットワーク（ＣＤＮ）としても知られているキャッシュサーバネットワークがより一般的になりつつある。ＣＤＮは、ウェブサイトのコンテンツファイルをキャッシュサーバから入手可能とするため、ウェブサイトオペレータとコンタクトし、これにより、ウェブサイトコンテンツサーバへのユーザリクエストは、ＣＤＮのキャッシュサーバより迅速、効率的及び／又は地理的に近傍で実現又は配信することが可能となる。例えば、ダウンロードシステムは、ユーザが第１時点において第１ネットワーク上のある一にいる間にコンテンツサーバからコンテンツファイルをリクエストし、第２の位置において、第２ネットワークを介し、及び／又は以降の第２時点に当該コンテンツファイルをダウンロードすることを可能にする。これは、リモートサイトダウンロード機能として知られる。リモートサイトダウンロード機能は、ＣＤＮ又はコンテンツサーバによって提供されるかもしれない。
【０００７】
これらの要求を満足するため、「ホットスポット」として知られ、キャッシュサーバの使用を通じてコスト効率的なダウンロードを容易にするパブリックアクセスポイントが開発された。ここで使用されるように、ホットスポットは、パブリックスペースの無線ブロードバンドコンピュータネットワークなどのワイヤレスローカルエリアネットワーク（ＷＬＡＮ）が確立された場所である。ホットスポットは、ＩＥＥＥ８０２．１１ｂ（Ｗｉ−Ｆｉ）規格を利用して毎秒１１メガビットの、又はＩＥＥＥ８０２．１１ｇを利用して毎秒５５メガビットの接続スピードを現在提供し、コーヒーショップ、レストラン、ホテル、空港、書店、コピーショップ、コンベンションセンター、他の公的にアクセス可能な場所などに配置されるかもしれない。ホットスポットでは、ＰＤＡ、ラップトップコンピュータ、携帯電話、ハイブリッドＰＤＡ携帯電話など、Ｗｉ−Ｆｉ対応モバイル装置がインターネットにアクセスし、大変コスト効率的に大きなコンテンツファイルをダウンロード又はストリーミングすることが可能である。
【０００８】
ホットスポットのインターネットアクセスは、一般にはワイヤレスカードを有するモバイル装置と通信する無線トランシーバを備えるワイヤレスルータによってユーザのモバイル装置に提供される。Ｗｉ−Ｆｉ対応でないモバイルユーザは、将来的にはすべてのモバイル装置がＷｉ−Ｆｉ対応となることが要素されるが、有線接続の場合にホットスポットインターネットサーバに接続してもよい。
【０００９】
現在、無線モバイル装置のユーザは、迅速なダウンロードのため、リモートコンテンツウェブサーバからコンテンツファイルを選択、リクエスト及び購入するため、ホットスポットにおいてインターネットにアクセスすることができる。しかしながら、モバイルユーザはしばしば、セルラー又は他の低スピードネットワークを介しコンテンツプロバイダウェブサイトからコンテンツファイルを選択し、モバイルユーザがコンテンツファイルを取得するための訪問中にコンテンツサーバウェブサイトに接続する必要なくホットスポットに訪れるとき、迅速なアクセスのため予めコンテンツファイルをダウンロードさせることが便利であるとわかるであろう。この状況では、モバイルユーザは、コンテンツが送信されるホットスポット／キャッシュサーバと、ユーザがコンテンツにアクセス及び受信することを所望する推定時間（すなわち、サービス時間）とを指定するコンテンツファイルに対するリクエストを自分のモバイル／ワイヤレス装置を介し生成する。
【００１０】
ホットスポットキャッシュサーバにダウンロードするためのファイルをリクエストすることはある効果を有するが、ユーザは現在のネットワークによりいくつかの問題に直面し、そのうちの１つは、指定されたキャッシュサーバにリクエストされたコンテンツファイルが到着することに関する遅延である。しばしば、ユーザはキャッシュサーバにアクセス可能となるため、リクエストされたコンテンツについて推定されたサービス時間以上待機しなければならない。この問題は、キャッシュネットワークのダウンロードが増えるに従って、悪化しつつある。
【００１１】
米国特許出願公報ＵＳ２００２／０１９８９６３は、指定された間隔により指定された期間に指定された時間においてネットワーク環境のソースサーバＵＲＬ（Ｕｎｉｆｏｒｍ  Ｒｅｓｏｕｒｃｅ  Ｌｏｃａｔｏｒ）のリストから文書のダウンロードをスケジューリングするためブラウザアプリケーションにおいて使用されるスキームを開示する。ダウンロードされた文書は、ローカルストレージ、ローカルネットワークにおけるストレージ又はリモートストレージ上に保存されるかもしれない。
【００１２】
米国特許出願公報ＵＳ２００２／００１０７５３は、ソースサーバからの情報をリクエストすることを含むコンピュータネットワークから情報を取得し、当該情報がソースサーバのサーバにより制御されたキャッシュに予め格納されているか判断する方法及び装置を開示する。
【００１３】
欧州特許出願ＥＰ１２３３３４８は、コンテンツサーバが、データターミナル装置（ＤＴＥ）に接続されるデータ回路ターミネーティング装置（ＤＣＥ）への格納のため、コンテンツ予約リクエストによって指定されるコンテンツデータをＤＴＥから第１又は第２通信回路に送信するデータ送信システムを開示する。
【００１４】
大部分のインターネットサービスにおけるダウンロードプロセスは、一般には、サーバ、ネットワーク及びクライアント状態に関係なくほとんど瞬時に行われる。瞬時のダウンロードシステムには、あったとしてもわずかしかスケジューリング問題は存在しない。このようなシステムのスケジューラは、コンテンツサーバの処理能力に基づき動作し、ファイルに対するリクエストの処理は、このようなリクエストが受信される順番に行われる。しかしながら、サービス時間情報による予めのリクエストが多くなるに従って、当該ネットワークに存在する特別な制約を考慮したキャッシュネットワーク（ＣＤＮ）環境においてコンテンツファイルをダウンロードするスケジューラを設計する必要がある。
［発明の開示］
本発明の課題は、ダウンロードシステムのためジョブのダウンロードをスケジューリングする方法及びシステムを提供することである。
【００１５】
他の課題は、サービス時間に関するダウンロード遅延を減少させるダウンロードシステムにおいてダウンロードをスケジューリングする方法及びネットワークを提供することである。
【００１６】
さらなる他の課題は、キャッシュサーバの利用を最大化するダウンロードシステムにおいてダウンロードをスケジューリングする方法及びネットワークを提供することである。
【００１７】
さらなる他の課題は、重複したコンテンツファイルをキャッシュサーバに格納することを回避するダウンロードシステムにおけるダウンロード方法及びネットワークを提供することである。
【００１８】
本発明の他の課題は、コンテンツサーバとキャッシュサーバ能力の両方を考慮したダウンロードシステムにおけるダウンロードをスケジューリングする方法及びネットワークを提供することである。
【００１９】
上記及び他の課題が、本発明によって満足される。ダウンロードシステムでは、コンテンツファイルをダウンロードするリクエストがコンテンツサービス時間（すなわち、コンテンツ利用時間）前になされるため、システムのスループットを向上させるダウンロードをスケジューリングする方法及びネットワークが考案可能であることが発見された。当該課題は、サーバ、ネットワーク及びキャッシュ能力の制約の下、ネットワークスループットを最大化することである。本発明は、有線と無線両方のネットワーク環境において利用可能である。
【００２０】
一特徴では、本発明は、ダウンロードシステム環境のためのダウンロードをスケジューリングする方法であって、指定されたキャッシュサーバにおけるサービス時間を有するコンテンツファイルに対するリクエストを受信するステップと、サービス時間による時間順に前記リクエストをジョブリストにリストするステップとを有する方法である。リクエストはまた、コンテンツファイルＵＲＬのデータセットとコンテンツファイルサイズとを有することが可能である。
【００２１】
リストの先頭に初期化されたスケジューリングポインタがある。ジョブリストは、好ましくは、コンテンツファイルに対する新たなリクエストが受信されると動的に更新され、新たなリクエストがスケジューリングポインタによって現在示されるリクエストの前に挿入される場合、スケジューリングポインタが後方に移動される。ジョブリストが生成及び編集されると、スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルが、すでに指定されたキャッシュサーバ上に格納されているか判断される。スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルが、すでに指定されたキャッシュサーバ上に格納されていないと判断される場合、フリースペースが利用可能になると、当該コンテンツファイルがキャッシュサーバにダウンロードされるよう要求される。このダウンロードが完了すると、ダウンロードされたコンテンツは、スケジューリングポインタにおけるリクエストとのリンクを有し、スケジューリングポインタは、ジョブリスト上の次のリクエストに前方に移動される。
【００２２】
しかしながら、スケジューリングポインタによって指示されるリクエストによって求められるコンテンツファイルがキャッシュサーバ上に存在する場合、当該リクエストは、好ましくは、格納されているコンテンツにリンクされ、スケジューリングポインタは、ジョブリスト上の次のリクエストに前方に移動される。これは、コンテンツファイルが同じキャッシュサーバ上に重複して格納されることを回避し、キャッシュサーバのストレージ使用を最大化する。
【００２３】
本発明は、コンテンツサーバ処理キャパシティを考慮するだけでなく、ストレージスペースなどのキャッシュサーバキャパシティを考える。キャッシュサーバは、ファイルを保持するためのフリーなスペースを有しない場合、リスト上の次のジョブを処理することはできない（すなわち、リクエストされたコンテンツファイルをダウンロードする）。キャッシュサーバフリースペースが、リクエストの予想されるサービス時間でなくクライアントのランダムピックアップに依存しているため、キャッシュサーバフリースペースが連続的にモニタされることが好ましい。本発明は、サーバ及びキャッシュキャパシティの制約の下でスループットを最大化する。
【００２４】
好ましくは、コンテンツファイルが、コンテンツソースから指定されたキャッシュサーバにダウンロードされる。ここで使用されるように、コンテンツソースは、所望のコンテンツファイルを含む指定されていないキャッシュサーバ又はコンテンツウェブサーバを有する。ジョブリストは、指定されたキャッシュサーバ上に格納され、実行することが可能である。さらに、指定されたチャックサーバはホットスポットキャッシュサーバであることが好ましい。リクエストは、ＰＤＡ、携帯電話、ラップトップなどのモバイル電子装置又はデスクトップコンピュータなどの固定された装置を含む無線又は有線ユーザ装置によって生成可能である。
【００２５】
他の特徴では、本発明は、ジョブリストとコンテンツストレージスペースとを有するキャッシュサーバと、コンテンツファイルがキャッシュサーバ上に利用可能とされるサービス時間を有するリクエストを生成するよう構成されるユーザ装置と、サービス時間による時間順に編集され、ジョブリストの先頭において初期化されるスケジューリングポインタを有するジョブリストにリクエストを追加する手段と、スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルが、キャッシュサーバ上に格納されているか判断する手段と、キャッシュサーバ上にフリースペースが検出され、スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルがキャッシュサーバ上に格納されていないと判断されると、スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルをキャッシュサーバにダウンロードする手段とを有するシステムである。
【００２６】
好ましくは、本システムは、スケジューリングポインタによって指示されるリクエストによって求められるコンテンツがダウンロードされるとき、スケジューリングポインタをジョブリスト上の次のリクエストに前方に移動する手段を有するべきである。さらに、本システムは、好ましくは、スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルがキャッシュサーバ上に存在するとき、スケジューリングポインタをジョブリスト上の次のリクエストに前方に移動する手段を有する。何れの実施例でも、本システムは、スケジューリングポインタをジョブリスト上の次のリクエストに移動する前に、スケジューリングポインタにおけるリクエストによって求められるコンテンツファイルからリクエストへのリンクを生成する手段を有することが可能である。
【００２７】
本発明のシステムはさらに、コンテンツをキャッシュサーバにダウンロードするコンテンツソースを有することが可能である。コンテンツソースは、コンテンツサーバ又は他のキャッシュサーバとすることが可能である。
［発明を実行するためのモード］
図１は、ダウンロードシステム１００を示す。ダウンロードシステム１００は、ユーザ装置１０（矩形のボックスにより一般的に示される）と、コンテンツサーバ２０と、キャッシュサーバ３０とを有する。ユーザ装置１０は、本例では、比較的低スピード（すなわち、低い帯域幅）により動作するワイヤレスセルラーネットワークから構成される第１ネットワークａを介しコンテンツサーバと通信し、データを送受信する。コンテンツサーバ２０は、高スピード（すなわち、高い帯域幅）を有するインターネットなどの第２ネットワークｂを介しキャッシュサーバ３０と通信し、データを送受信する。キャッシュサーバ３０とユーザ装置１０は、互いに通信し、例えば、コーヒーショップや空港などの無線又は有線接続を提供可能なホットスポットｃにおいてローカルにデータを送受信する。
【００２８】
本例では、ユーザ装置１０は、ウェブ対応ＰＤＡや携帯電話などのワイヤレス装置を有する。本例では、コンテンツサーバ２０は、映画を購入及びダウンロード可能なウェブサイトを有する。本例では、キャッシュサーバ３０は、複数のユーザによってアクセス可能なホットスポットキャッシュサーバを有する。
【００２９】
図２は、本発明の一実施例によるダウンロードシステム１００の動作方法のフローチャートを示す。図２は、図１のダウンロードシステム１００に関して説明されるが、様々な実施例及びハードウェアに代替可能であるということが理解される。
【００３０】
ユーザが以降においてコンテンツファイルを取得することを決定するが、コンテンツファイルを即時にリクエストすることを所望するとき、ユーザは、第１リモート一においてユーザ装置１０を介し所望のコンテンツファイルに対するリクエストを生成する。このリクエストは、ユーザがファイルを取得することを所望するサービス時間を含む。当該リクエストはまた、ユーザがコンテンツファイルを直接的に又は間接的に抽出することを所望するキャッシュサーバを指定する。あるいは、当該リクエストは、ダウンロードシステム１００による抽出のため、特定のキャッシュサーバに割り当てることができる。ユーザ装置１０により当該リクエストを生成すると、リクエストはキャッシュサーバ３０に直接わたされるか、あるいは、コンテンツサーバ２０を介し間接的にわたされる。
【００３１】
キャッシュサーバ３０は、図２のステップ２００において、コンテンツファイルに対するリクエストを受け取る。当該リクエストを受信すると、ステップ２１０において、キャッシュサーバ３０は、リクエストに関するサービス時間を決定し、当該リクエストを以前のリクエストを含むジョブリストに追加する。このジョブリストは、処理のためキャッシュサーバ３０によって受信されるコンテンツファイルに対するリクエストのすべてのリストから構成される。キャッシュサーバ３０は、ステップ２２０において、サービス時間に従ってリクエストが時間順に現れるようにジョブリストを構成する。キャッシュサーバ３０は、ジョブリストの先頭に初期化されたスケジューリングポインタを有する。新たなリクエストはしばしばキャッシュサーバ３０に定期的に到着するため、キャッシュサーバは、ジョブリストを動的に更新し、スケジューリングポインタによってそれ以前に特定されるリクエストの前に新たなリクエストを挿入すると、スケジューリングポインタを後方に移動させる。適切にプログラムされたプロセッサと従来のハードウェア（図示せず）は、すべてのプロセスステップと決定を実行する。
【００３２】
ジョブリストが更新及び編集されるとき、スケジューリングポインタは、スケジューリングされるリクエストであるジョブリストのリクエストを指示する。ステップ２３０において、キャッシュサーバ３０は、ジョブリスト上でスケジューリングポインタによって現在特定されるリクエストが、キャッシュサーバ３０のメモリ内にすでに格納されているコンテンツファイルをリクエストしているか判断する。そうである場合、キャッシュサーバ３０はステップ２４０に移行する。ステップ２４０において、キャッシュサーバは、当該コンテンツファイルをスケジューリングポインタによって特定されるリクエストにリンクし、これにより、対応するユーザは、ホットスポット位置への到着に続くユーザ装置１０によるキャッシュサーバへのアクセスにより、所望のコンテンツファイルを抽出することができる。ステップ２４０が終了すると、ステップ２５０において、スケジューリングポインタはジョブリスト上の次のリクエストに移行する。これは、キャッシュサーバ３０のメモリ内に重複したコンテンツファイルを格納することを回避し、これにより、キャッシュサーバの限定されたメモリスペースを節約及び最大化する。
【００３３】
しかしながら、ステップ２３０において、リクエストされたコンテンツがキャッシュサーバ３０のチェックにより存在しない場合、ステップ２６０が実行され、キャッシュサーバ３０上にスケジューリングポインタによって特定されるリクエストに指定されるコンテンツファイルをダウンロードするのに十分なフリースペースが存在するか判断される。ここで使用されるように、キャッシュサーバ３０上にリンクされたコンテンツファイルを上書きすることなくスケジューリングポインタに当該リクエストに係るコンテンツファイルを格納するための適切なメモリスペースが存在するとき、フリースペースは存在する。この状況は、キャッシュサーバメモリ上に十分なエンプティスペースが存在するとき、又は、メモリに格納されるコンテンツファイルが置換可能であるときに存在する。メモリに格納されているコンテンツファイルは、当該ファイルに対するリクエストにリンクが存在しないとき、置換可能である。リクエストへのリンクは、当該リクエストに対する対応するユーザが当該コンテンツファイルをユーザ装置１０に抽出（すなわち、ダウンロード）するとき、又は、当該リクエストが期限切れとなるとき（すなわち、推定されるサービス時間を超えて所定の時間が経過したとき）、削除される。
【００３４】
ステップ２６０の実行中に十分なスペースが存在しない場合、そのときステップ２７０が実行され、キャッシュサーバ３０は、ステップ２６０を再実行する前にフリースペースが利用可能になるまで、既存のリンクされたジョブを処理する。
【００３５】
ステップ２６０において十分なスペースが存在するとき、ステップ２８０が実行され、キャッシュサーバ３０は、スケジューリングポインタによってジョブリスト上で指定されるリクエストによって求められているコンテンツファイルをリクエストする信号をコンテンツサーバ２０に送信する。ステップ２８０において、コンテンツサーバ２０は、スケジューリングポインタによって指示されるリクエストによってリクエストされるコンテンツファイルをダウンロードする信号に対してキャッシュサーバに与えられた時間により応答し、コンテンツファイルは、格納のために与えられた時間にキャッシュサーバ３０にダウンロードされる。ダウンロードが完了すると、スケジューリングポインタにおけるリクエストは、ステップ２９０において、ダウンロードされたファイルにリンクされる。その後、スケジューリングポインタは、ステップ２２０に戻る前に、ステップ３００においてジョブリスト上の次のリクエストに移行する。
【００３６】
本発明は、その目的の１つとして、ダウンロードシステムへの遅延ペナルティと考えられている予想されるサービス時間以降に延長されるジョブ数を最小化することである。通常のコンピュータクライアントは、いわゆる早着（ｅａｒｌｉｎｅｓｓ）ペナルティなくサーバがキャパシティを有するのと同程度に早期にダウンロードをリクエストすることが可能である一方、ＣＤＮでは、キャッシュサーバは、サーバがキャパシティを有するのと同程度に早期にダウンロードをリクエストことはできない。これは、早着ペナルティを意味する。キャッシュサーバストレージの利用は、早着のペナルティである。トータルのキャッシュサーバストレージが一定のストレージキャパシティを有すると仮定することは、
問題を簡単化するであろう。従って、早着ペナルティは、早着制約となる。本発明の１つの課題は、一定の早着制約により遅延ペナルティ数を最小化することである。
【００３７】
新たなリクエストの到着を処理する（ダウンロードのためなど）リクエストがリクエスト処理をトリガーする必要がないことに留意されたい。リクエスト到着及びリクエスト処理は互いに直交して存在する可能性があり、新たなリクエストの挿入がリクエストリストに挿入され、リクエスト到着とリクエスト処理との間で行われる接続のみを構成する。
【００３８】
説明のため、図２に示されるスケジューリングアルゴリズムは、上記目的と制約に基づき「ＥＴＳＯ（Ｅａｒｌｉｅｓｔ  Ｔｒａｎｓｍｉｓｓｉｏｎ  ｉｎ  Ｓｅｒｖｉｃｅ  Ｏｒｄｅｒ）」と呼ばれる。ＥＴＳＯスケジューリングアルゴリズムは、送信キャパシティとキャッシュサーバキャパシティの双方の利用を最大化するため、キャッシュサーバ制約の下で可能な限り早期にコンテンツファイルを送信しようとする。ＥＴＳＯアルゴリズムは、リアルタイムとオフラインの両方により動作可能である。リアルタイムのケースは、リクエスト処理が進捗するに従って、新たなリクエストが到着するときに行われる。オフラインのケースは、それらの予想されるサービス時間によるすべてのリクエストが、リクエスト処理を開始する前に利用可能になることを仮定している。オフラインのケースでは、ＥＴＳＯアルゴリズムは、コンテンツサイズが一定の場合には、自らを最適なアルゴリズムとして証明する。可変のコンテンツサイズの場合には、最適化の目的は、遅延ジョブ数又は遅延レートだけでなく、すなわち、それらのデッドラインを逃すことだけでなく、遅延ジョブのコンテンツのトータルサイズに関するものである。このような目的関数は、サーバが目的を満足するため、以降の予想されるサービス時間によりより大きな又はより小さなコンテンツを処理する必要がある可能性があるため、予想されるサービス時間順序ではない送信をときどき要求しうる。これは、ジョブがそれの予想されるサービス時間の近傍で処理するときに発生する。システム構成が低い遅延レートを与える可能性がある場合、これはそれほど頻繁には発生しない。従って、サービスオーダー（ＥＴＳアルゴリズムの早期の送信はもはや最適ではないが、キャッシュ制約による早期の送信の原理は、依然として有効であり、可変コンテンツサイズシステムにおいて使用可能である。
【００３９】
本発明におけるスケジューリング問題は、以下のように定義することができる。すなわち、コンテンツサーバ上では、Ｋ個の異なるコンテンツファイルが存在する。すべてのコンテンツファイルは等しいサイズを有し、キャッシュサーバにダウンロードするのに同じ時間ｐを要する。キャッシュサーバ上では、時間ＴのサイズＮのリクエストセットＲ＝｛ｒｉ｝が存在する。キャッシュサイズはＣである。各リクエストｒｉ＝（ｋｉ，ｄｉ）はコンテンツｋｉに対するものであり、予想されるサービス時間ｄｉを有する。一般性を失うことなく、Ｎ個のリクエストに対する予想されるサービス時間の順序は、ｉ＜ｊの場合に、ｄｉ＜ｄｊとされる。スケジューリング問題は、時間シーケンスＳ＝｛ｓｉ｝を求めることであり、ここで、ｓｉはリクエストｉがスケジューリングされる時間である。「スケジューリングされた」とは、リクエストされたコンテンツがキャッシュサーバにダウンロードされる時間、すなわち、送信スタートの代わりに送信エンドとして定義することができる。最小のサービス遅延数、すなわち、ｓｉ＞ｄｉの出現数をもたらすスケジュールＳが検索される。
【００４０】
適切なＥＴＳＯスケジュールＳＥＴＳＯは、以下のステップに従う。
１．リクエストｒ１がｓ１＝ｄ１においてスケジューリングされ、ｄ１’＝ｄ１とされ、ｄｉ’は、ｋｉがキャッシュに存在しなければならないときまでの時間である。現在のスケジュール時間をｔ＝ｓ１とする。
２．ｉ＝２〜Ｎ（リクエスト数）について、
Ａ．コンテンツファイルｋｉがキャッシュに存在する場合、ｓｉ＝ｔ、ｄｊ’＝ｔ−ｐとし（ただし、ｊはコンテンツファイルｋｉに対する直近のリクエストである）、
Ｂ．そうでない場合には、ｔ’≧ｔとなるまで待機し、この結果、ｄｉ≧ｔ’＋ｐとなる場合、ＧＳ（ｔ’）＜Ｃ／ｐとなり、ｓｉ＝ｔ’＋ｐ、ｄｉ’＝ｄｉ、及びｔ＝ｔ’＋ｐとされ、
Ｃ．そうでない場合には、ｓｉ＝∞（スケジューリング失敗、遅延＋＋）となる。
【００４１】
ＧＳ（ｔ）＝Σｉｐ［Θ（ｔ−ｓｉ＋ｐ）−Θ（ｔ−ｄｉ’）］は、現在時点ｔにおけるキャッシュに保持されねばならないコンテンツのトータルサイズであり、Θ（ｘ）は、ユニットステップ関数であり、すなわち、ｘ＞０である場合には、Θ（ｘ）＝１とされ、そうでない場合には、Θ（ｘ）＝０となる。Θ（ｔ−ｓｉ＋ｐ）−Θ（ｔ−ｄｉ’）は、それの送信スタート（ｓｉ−ｐ）からそれのサービス時間（ｄｉ）又は次の同じコンテンツリクエスト（ｄｉ’）の送信スタートまでのリクエストｉのキャッシュ要求を意味する。
【００４２】
第１ステップは初期化であり、第２ステップは、ｒＮまですべてのリクエストをスケジューリングするためのループである。当該ループ内の各ステップは、以下のように説明することができる。
【００４３】
ステップ２Ａ：リクエストされたコンテンツは、キャッシュ内にある。現在時点でリクエストｒｉをスケジューリングせよ。リクエストｒｉは、ｊ＜ｉに対してｄｉ≧ｄｊとなるまで、コンテンツｋｉをキャッシュに格納することを求めるため、リクエストｒｊがコンテンツｋｉ（＝ｋｊ）をｓｉ−ｐより多く格納することを求める必要はない。ｄ’を導入することは、キャッシュストレージをカウントすることを回避するためであり、すなわち、ＧＳ（ｔ）におけるｄ’の使用は、同一コンテンツについて重複したキャッシュ期間を有しなくなる。
【００４４】
ステップ２Ｂ：キャッシュがフルである場合、すべてのそれのスケジューリングされたリクエストを有する少なくとも１つのコンテンツがサービスされるとき、ｔ’まで待機する必要がある。まだダウンロードする時間がある場合、すなわち、ｄｉ≧ｔ’＋ｐとなる場合、ｓｉ＝ｔ’＋ｐにおいてリクエストｒｉをスケジューリングする。それは新たにキャッシュされたコンテンツであり、そのため、ｋｉはｄｉ’＝ｄｉとなるまで格納されなければならない。時間はｔ＝ｔ’＋ｐに進捗する。
【００４５】
ステップ２Ｃ：ダウンロードする時間がない場合、ｓｉ＝∞とされる。スケジューリングの失敗が発生する。
【００４６】
ＥＴＳＯスケジューリングアルゴリズムは、キャッシュ制約の下、可能な限り早期にリクエストを送信しようとする。それは、送信キャパシティとキャッシュキャパシティの両方の使用を最大化する。ＥＴＳＯアルゴリズムが与えられた目的関数、すなわち、遅延発生数の最小化のための最適なアルゴリズムであるということは証明可能である。ｉ個のリクエストまで、最適なスケジューリングは、（１）最小遅延数と、（２）直近のスケジュールｓｉの最も早期のスケジュール時間によるスケジュールである。
【００４７】
第１リクエストは一定のスケジュールｓ１＝ｄ１を有し、それは時間がｔ＝ｄ１−ｐにおいてスタートすることを意味すると仮定する。第２リクエストは、ＥＴＳＯにより最適であると証明可能である。すなわち、最も早い時間は、ｔ＋ｐである。ｔ＋ｐ＞ｄ２である場合、ｓ２＝ｔ＋ｐは遅延し、これにより、第３リクエスト以降をスケジューリングする必要がある。一般性を失うことなく、ｄ２≧ｄ１＋ｐを仮定する。Ｓ２＝｛ｓ１＝ｄ１，ｓ２＝ｄ１＋ｐ｝が上記２つの基準による最適なスケジュールであることは明らかである。
【００４８】
帰納法を用いて、リクエストｒｉまで、ＥＴＳＯアルゴリズムがスケジュールＳｉ＝｛ｓ１，．．．，ｓｉ｝により最適であると仮定する。リクエストｒｉ＋１に対するコンテンツｋｉ＋１が現在時点ｔ＝ｓｉにおいてキャッシュに存在する場合、ｔ’＝ｔ＝ｓｉとなる。この場合、Ｓｉ＋１＊は、等しい遅延と等しい直近のスケジュール時間を有する。従って、Ｓｉ＋１＝｛Ｓｉ，ｓｉ＋１＝ｓｉ｝は最適である。リクエストｒｉ＋１に対するコンテンツｋｉ＋１がキャッシュなく、ＥＴＳＯアルゴリズムに従って、ｒｉ＋１が以前のリクエストの後にスケジューリングされる場合、Ｓｉ＋１＊＝｛Ｓｉ，ｓｉ＋１＝ｔ’＋ｐ｝は、ｒｉ＋１に対する最も速いスケジュールであり、ここで、ｔ’≧ｓｉは、ＧＳｉ（ｔ’）＜Ｃ／ｐを満たす最小値である。キャッシュ状態ＧＳｉ（ｔ）は、ｔ’まで影響を受けない。ＥＴＳＯアルゴリズムは、ｓｉ後の可能な最も早いｓｉ＋１を選択する。この場合、スケジュールＳｉ＋１＊＝｛ｓ１，．．．，ｓｉ＋１｝もまた最適とならなければならない。
【００４９】
しかしながら、以前のｉ個のスケジュール間でリクエストｒｉ＋１をスケジューリングすることは可能であるか。スケジュールＳｉ＋１＝｛ｓａ，．．．，ｓｉ＋１＝ｔ１，ｓｂ＝ｔ２，．．．，ｓｌ＝ｔｍ｝が存在すると仮定すると、すべての可能なＳｉ＋１に対する遅延数は、Ｓｉ＋１＊以上となることが証明可能である。
【００５０】
ｄｉ＋１≧ｄｌ≧ｓｌであるため、有効なスケジュールＳｉ＋１はキャッシュ制約ＧＳ（ｔ）を満足しなければならない。リクエストｒｂとｒｉ＋１についてスケジュールＳを交換するスケジュールＳｉ＋１’＝｛ｓａ，．．．，ｓｂ＝ｔ１，ｓｉ＋１＝ｔ２，．．．，ｓｌ＝ｔｍ｝を考える。そのとき、リクエストｒｂについて、キャッシュ占有の差は、［Θ（ｔ−ｔｌ＋ｐ）−Θ（ｔ−ｄｂ’）］−［Θ（ｔ−ｔ２＋ｐ）−Θ（ｔ−ｄｂ’）］＝［Θ（ｔ−ｔｌ＋ｐ）−Θ（ｔ−ｔ２＋ｐ）］となる。リクエストｒｉ＋１について、キャッシュ占有の差は、［Θ（ｔ−ｔ２＋ｐ）−Θ（ｔ−ｄｉ＋１）］−［Θ（ｔ−ｔ１＋ｐ）−Θ（ｔ−ｄｉ＋１）］＝［Θ（ｔ−ｔ２＋ｐ）−Θ（ｔ−ｔ１＋ｐ）］となる。従って、ＧＳ’（ｔ）＝ＧＳ（ｔ）≦Ｃ／ｐとなる。
【００５１】
ｓｂに対するキャッシュの増加は、ｓｉ＋１に対するキャッシュの減少によって相殺される。リクエストｒｂが早期にスケジューリングされるため、遅延を招くことはない。ｓｉ＋１＝ｔ２＜ｓｌ≦ｄｌ≦ｄｉ＋ｌであるため、リクエストｒｉ＋１についてもまた遅延を招かない。直近のスケジュールは、依然としてｓｌ＝ｔｍである。これは、Ｓｉ＋１’がＳｉ＋１と同様であることを証明する。同様にして、Ｓｉ＋１における直近のスケジュールによりスワップするまで、リクエストｒｂの後の次にスケジューリングされるリクエストとリクエストｒｉ＋１とをスワップすることが可能である。これは、以前のｉ個のリクエストの直近のスケジュールの後のリクエストｒｉ＋１をスケジューリングすることが、ｉ個のリクエストに対する以前のスケジュールの間のスケジューリングすることと少なくとも同様であることを証明する。
【００５２】
以前のｉ個のリクエストの直近のスケジュールの後、リクエストｒｉ＋１がスケジューリングされる場合、ＥＴＳＯアルゴリズムが可能な最も早期のｓｉ＋１を与えることは以前に示された。
【００５３】
ｉ＝１，２であるとき、Ｓ２が最適であることを示す。最初のｉ個のリクエストについて、Ｓｉが最適であると仮定すると、Ｓｉ＋１＊＝｛Ｓｉ，ｓｉ＋１＝ｔ’｝が最初の（ｉ＋１）個のリクエストについて最適なスケジュールであることを示す。これは、ＥＴＳＯアルゴリズムに基づくスケジュールが、他の何れのスケジュールと少なくとも同程度良好である、すなわち、最適なスケジュールであることを証明する。
【００５４】
本発明が当業者が容易にそれを構成及び使用することが可能な程度まで十分詳細に説明及び図示されたが、本発明の趣旨及び範囲から逸脱することなく、様々な代替、改良及び改善が容易に明らかであろう。特に、本発明は、リモートサイトダウンロード機能を利用したＣＤＮに限定されるものではない。本発明は、すべてのキャッシュネットワーク環境に適用可能である。
【図面の簡単な説明】
【００５５】
【図１】図１は、本発明の一実施例によるコンテンツリクエスト及びコンテンツダウンロードが異なるネットワークを使用するダウンロードシステムの概略を示す。
【図２】図２は、本発明の一実施例によるリモートダウンロードシステムにおけるダウンロードをスケジューリングする方法のフローチャートを示す。
【国際調査報告】
2007529072.tif 000005
2007529072.tif 000006
2007529072.tif 000007
2007529072.tif 000008