(57)【要約】コンテンツ配信システムは、いくつかのクライアント要求に応じる少なくとも１つのコンテンツ・サーバを備える。このコンテンツ・サーバは、スレショルド・ベース・ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ＴＢ−ＮＲＥＤＦ）スケジューラを使用する。ＴＢ−ＮＲＥＤＦスケジューラは、再スケジューリングする要求の数にしきい値すなわち制限を加える。
2009536498.tif 000002
【特許請求の範囲】
【請求項１】
サービスの供給に使用される方法であって、
前記サービスを求める少なくとも１つの新しい要求を受け取るステップと、
再スケジューリングされる古い要求の数がしきい値に制限されるように前記少なくとも１つの新しい要求および任意の古い要求の配信をスケジューリングするステップと、
を含む前記方法。
【請求項２】
前記スケジューリングするステップが、
前記少なくとも１つの新しい要求の配信をスケジューリングするステップと、
古い要求の数Ｋを求めるステップと、
前記古い要求の数が前記しきい値より大きい場合に、最大で前記しきい値の数だけの古い要求の配信を再スケジューリングするステップと、
を含む、請求項１に記載の方法。
【請求項３】
前記少なくとも１つの新しい要求および古い要求が要求セットを形成し、
前記スケジューリングするステップが、
ルックバック要求が前記要求セット内に設定されているかどうかを判定するステップと、
ルックバック要求が設定されていない場合に、全ての古い要求が再スケジューリングされるようにスケジューリング・セットを決定するステップと、
ルックバック要求が設定されており、前記ルックバック要求が未だ配信されていない場合に、最大で前記しきい値の数だけの古い要求の配信を再スケジューリングするステップと、を含む、請求項１に記載の方法。
【請求項４】
前記スケジューリングするステップが、しきい値に基づくスレショルド・ベース・ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ＴＢ−ＮＲＥＤＦ）を実行する、請求項１に記載の方法。
【請求項５】
前記サービスがコンテンツの配信である、請求項１に記載の方法。
【請求項６】
前記コンテンツがファイルである、請求項５に記載の方法。
【請求項７】
前記コンテンツがストリーミング・ビデオである、請求項５に記載の方法。
【請求項８】
要求クライアントへのサービスの供給に使用される装置であって、
前記サービスを求める少なくとも１つの新しい要求をスケジューリングし、再スケジューリングされる古い要求の数がしきい値に制限されるように古い要求の配信を再スケジューリングすることによって、要求側クライアントにサービスを配信するためのスケジューリング・セットを形成するプロセッサと、
前記形成されたスケジューリング・セットを記憶するメモリと、
を含む前記装置。
【請求項９】
前記プロセッサが、（ａ）前記少なくとも１つの新しい要求の配信をスケジューリングし、（ｂ）古い要求の数Ｋを求め、（ｃ）古い要求の数が前記しきい値より大きい場合に、最大で前記しきい値の数だけの古い要求の配信を再スケジューリングする、請求項８に記載の装置。
【請求項１０】
前記少なくとも１つの新しい要求および古い要求が要求セットを形成し、前記プロセッサが、（ａ）ルックバック要求が前記要求セット内に設定されているかどうかを判定し、（ｂ）ルックバック要求が設定されていない場合に、全ての古い要求が再スケジューリングされるようにスケジューリング・セットを決定し、（ｃ）ルックバック要求が設定されており、前記ルックバック要求が未だ配信されていない場合に、最大で前記しきい値の数だけの古い要求の配信を再スケジューリングする、請求項８に記載の装置。
【請求項１１】
前記プロセッサが、しきい値に基づくスレショルド・ベース・ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ＴＢ−ＮＲＥＤＦ）を実行する、請求項８に記載の装置。
【請求項１２】
前記サービスがコンテンツの配信である、請求項８に記載の装置。
【請求項１３】
前記コンテンツがファイルである、請求項１２に記載の装置。
【請求項１４】
前記コンテンツがストリーミング・ビデオである、請求項１２に記載の装置。
【請求項１５】
実行されたときにプロセッサ・ベース・システムが１つまたは複数のサービスを求める要求に応答して配信をスケジューリングする方法を実行するプロセッサ・ベース・システム用のコンピュータ実行可能命令を有するコンピュータが読取り可能な媒体であって、前記方法が、
前記サービスを求める少なくとも１つの新しい要求を受け取るステップと、
再スケジューリングされる古い要求の数がしきい値に制限されるように前記少なくとも１つの新しい要求および古い要求の配信をスケジューリングするステップと、
を含む、前記コンピュータが読取り可能な媒体。
【請求項１６】
前記スケジューリングするステップが、
前記少なくとも１つの新しい要求の配信をスケジューリングするステップと、
古い要求の数Ｋを求めるステップと、
古い要求の数が前記しきい値より大きい場合に、最大で前記しきい値の数だけの古い要求の配信を再スケジューリングするステップと、
を含む、請求項１５に記載のコンピュータが読取り可能な媒体。
【請求項１７】
前記少なくとも１つの新しい要求および古い要求が要求セットを形成し、
前記スケジューリングするステップが、
ルックバック要求が前記要求セット内に設定されているかどうかを判定するステップと、
ルックバック要求が設定されていない場合に、全ての古い要求が再スケジューリングされるようにスケジューリング・セットを決定するステップと、
ルックバック要求が設定されており、前記ルックバック要求が未だ配信されていない場合に、最大で前記しきい値の数だけの古い要求の配信を再スケジューリングするステップと、
を含む、請求項１５に記載のコンピュータが読取り可能な媒体。
【請求項１８】
前記スケジューリングするステップが、しきい値に基づくスレショルド・ベース・ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ＴＢ−ＮＲＥＤＦ）を実行する、請求項１５に記載のコンピュータが読取り可能な媒体。
【請求項１９】
前記１つまたは複数のサービスがコンテンツの配信である、請求項１５に記載のコンピュータが読取り可能な媒体。
【請求項２０】
前記コンテンツがファイルである、請求項１９に記載のコンピュータが読取り可能な媒体。
【請求項２１】
前記コンテンツがストリーミング・ビデオである、請求項１９に記載のコンピュータが読取り可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に通信システムに関し、より詳細には、コンテンツ配信／配布ネットワーク、ならびに例えばコンテンツ・サーバなど、その構成要素に関する。
【背景技術】
【０００２】
コンテンツ配信システムでは、コンテンツ・サーバは、例えばファイルやストリーミング・ビデオなど様々なタイプのコンテンツを、インターネットなどの分散型通信ネットワークを介して様々なクライアントに配布することができる。通常、このプロセスは、特定のコンテンツを求める要求を各クライアントがコンテンツ・サーバに送信することによって開始される。コンテンツ・サーバは、それぞれの要求を受信すると、要求されたコンテンツを要求したクライアントに分散型通信ネットワークを介して送る配信のスケジューリングを行う。
【０００３】
分散型通信ネットワークを介したコンテンツのクライアント（またはユーザ）への配信をスケジューリングする１つの手法は、「ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ｎｏｒｍａｌｉｚｅｄ  ｒａｔｅ  ｅａｒｌｉｅｓｔ  ｄｅｌｉｖｅｒｙ  ｆｉｒｓｔ）（ＮＲＥＤＦ）」手法である（より簡潔にＮＲＥＤと呼ぶこともある）。この手法では、コンテンツ・サーバは、コンテンツ・サーバと各要求側クライアントとの間の推定「最短経路」を用いて、特定のコンテンツの配信の正規化速度を計算する。この「最短経路」は、要求されたコンテンツを要求側クライアントに送る最も早い配信時刻を与える分散型通信ネットワーク内の経路である。このプロセスの一部として、コンテンツ・サーバは、要求されたコンテンツを配信用に供給することができるネットワーク内のその他のサーバを識別することができる。次いで、コンテンツ・サーバは、それぞれに関連する算出された正規化速度の高い順に、全ての受信したクライアント要求の配信をスケジューリングする。従って、算出された正規化速度の高い要求側クライアントへの配信は、算出された正規化速度の低い要求側クライアントより前になるようにスケジューリングされる。しかし、コンテンツ配信サーバがそれまでに受信した（すなわち古い）クライアント要求のスケジューリングを終了した後にも、新たなクライアント要求が引き続き到着することもある。このような状況では、新しいクライアント要求が到着するにつれて、新しいクライアント要求と一緒に未配信の古いクライアント要求を再スケジューリングして、コンテンツ・サーバが応じることができる要求の数が最大になるようにする。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
残念ながら、クライアント要求速度が増大するにつれて、コンテンツ・サーバは、実際にコンテンツを配信するより、正規化速度を計算し、古い要求を再スケジューリングするのに費やす時間を増やすようになる。この挙動により、ＮＲＥＤＦ手法の多数のクライアントに対応するスケーラビリティが損なわれている。
【課題を解決するための手段】
【０００５】
発明者等は、ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ＮＲＥＤＦ）スケジューラを用いたコンテンツ・サーバが、クライアント要求速度が増大するにつれて、新しい要求を受け入れながら古い要求を再スケジューリングする計算オーバヘッドも増大するために、うまくスケーリングしなくなることに気がついた。従って、本発明の原理によれば、ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ＮＲＥＤＦ）スケジューラを用いたコンテンツ・サーバは、再スケジューリングされる古い要求の数をしきい値に制限する。
【０００６】
本発明の例示的な実施形態では、コンテンツ配信システムは、いくつかのクライアント要求に応じる少なくとも１つのコンテンツ・サーバを含む。このコンテンツ・サーバは、スレショルド・ベース・ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ＴＢ−ＮＲＥＤＦ）スケジューラを使用する。このＴＢ−ＮＲＥＤＦスケジューラは、再スケジューリングする要求の数にしきい値すなわち制限を加える。従って、コンテンツ・サーバは、再スケジューリング・オーバヘッドを制限する機能を有し、これにより、コンテンツ・サーバは、スケーラビリティとシステム性能をトレードオフすることができる。
【０００７】
本発明の別の例示的な実施形態では、スレショルド・ベース・ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ＴＢ−ＮＲＥＤＦ）手法で、再スケジューリングされる古い要求の最大数を表すルックバックしきい値Ｔを定義する。例えば、Ｒ（ｔ）が、時点ｔにおける任意の未終了の古いクライアント要求と、時点ｔに到着した任意の新しいクライアント要求とを含む要求セットを表すものとする。また、ＱがＲ（ｔ）内の要求の総数、ＫがＲ（ｔ）内の古い要求の総数を表すものとする。ＴＢ−ＮＲＥＤＦ手法では、最大でＴ個の古い要求を再スケジューリングする。ここで、Ｔ＜Ｋ＜Ｑである。従って、残りのＫ−Ｔ個の古い要求のスケジュールは不変である。
【発明を実施するための最良の形態】
【０００８】
本発明の概念を除く図面に示す要素は周知であり、それらについて詳細には説明しない。また、ネットワーキング（およびそのなかで用いられるプロトコル）に精通していることを前提とし、それらについても本明細書では詳細には説明しない。例えば、本発明の概念を除いて、インターネット・プロトコル（ＩＰ）、リアルタイム・トランスポート・プロトコル（ＲＴＰ）、および伝送制御プロトコル（ＴＣＰ）に精通していることを前提としている。また、本発明の概念を除いて、サーバ、エッジ・ノード、およびクライアントなどのネットワーク構成要素に精通していることを前提としている。同様に、本発明の概念を除いて、ＭＰＥＧ−２システム標準（ＩＳＯ／ＩＥＣ１３８１８−１）や国際電気通信連合のＨ．２６４（ＩＴＵ−Ｔ勧告Ｈ．２６４「オーディオビジュアル・サービス全般のための高度ビデオ符号化方式」ＩＴＵ−Ｔ、２００３年）など、ビット・ストリームを生成するためのフォーマット化および符号化の方法も周知であり、本明細書では説明しない。これに関して、既知のサーバ／クライアント・システムとは異なる本発明の概念の部分のみを以下では説明し、図面に示してあることに留意されたい。また、本発明の概念は、従来のプログラミング技術、つまり本明細書には記載していないプログラミング技術を用いて実施することができることにも留意されたい。最後に、図面内の同じ参照番号は、同じ要素を指している。
【０００９】
本発明の概念について説明する前に、まず、ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ＮＲＥＤＦ）スケジューリング・プロセスについて簡単に説明する。これに関して、ＮＲＥＤＦスケジューリング・プロセスを用いるコンテンツ配信システムを、図１に示す。このコンテンツ配信システムは、コンテンツ・サーバ２０と、通信ネットワーク１０と、クライアント５０−１および５０−２として表す１つまたは複数のクライアントとを含む。コンテンツ・サーバ２０、クライアント５０−１およびクライアント５０−２は、格納プログラム制御式プロセッサ・プラットフォームを表している。例えば、クライアント５０−１がマイクロプロセッサ型デスクトップ・パーソナル・コンピュータ、クライアント５０−２が携帯電話、コンテンツ・サーバ２０がマルチ・プロセッサ型（高性能）サーバとすることもできる。例えば、通信ネットワーク１０はインターネットを表し、当技術分野で既知のように交換機能および非交換機能の両方を含み、ルータやエッジ・ノード装置などを含む（全て図１には示していない）。この例では、図１から分かるように、コンテンツ・サーバ２０は、あるインターネット・プロトコル（ＩＰ）アドレス（図示せず）と関連づけられた、インターネット上のある箇所に位置するものとして表されている。さらに、図１に示すように、通信ネットワーク１０は、コンテンツ配信ネットワーク（ＣＤＮ）１５を含むこともできる。当技術分野で既知のように、ＣＤＮは、コストを抑え、且つクライアント（エンド・ユーザ）のスピードを高めながら、コンテンツ・サーバ（プロバイダ）からクライアントに安全にコンテンツを配信するように設計されたオーバレイ・ネットワーク（公共または私設）である。従って、ＣＤＮ内の他のサーバが、コンテンツ・サーバ２０の制御下で要求されたコンテンツを供給することができることもある。このコンテンツのフォーマットは、静的コンテンツ（例えばウェブ・サイト・コンテンツやファイル）または動的コンテンツ（すなわち素早く変化するコンテンツ）および／あるいはストリーミング・オーディオ／ビデオとすることができる。図１に示す状況では、クライアント５０−１および５０−２が、コンテンツを求める要求をコンテンツ・サーバ２０に送る。これらの要求に応答して、コンテンツ・サーバ２０は、ＮＲＥＤＦスケジューリング・プロセスを用いて配信をスケジューリングし、通信ネットワークを通る経路を介して要求されたコンテンツをそれぞれのクライアントに配信または送信する。例えば、クライアント５０−１から要求された例えばファイルなどのコンテンツは、例示的な経路１１を介してクライアント５０−１に供給される。例示的な経路１１は、この例では、ＣＤＮ１５も通過している。経路１１は、要求されたコンテンツがクライアント５０−１まで搬送される際に通過する通信ネットワーク１０の任意の機構および装置を表す。
【００１０】
次に図２を参照すると、コンテンツ・サーバ２０のハイレベル・ブロック図が示してある。コンテンツ・サーバ２０は、コンテンツ・サーバ２０をインターネット１０に結合する接続１９を介してクライアント要求５９を受け取る。コンテンツ・サーバ２０は、受け取ったクライアント要求５９を処理し、要求側クライアントに要求されたコンテンツを供給するためのスケジューリング・セットＳ（ｔ）７０を生成する、ＮＲＥＤＦスケジューラ６０を含む。コンテンツ・サーバ２０が使用するＮＲＥＤＦスケジューリング・プロセスを表す例示的な流れ図を、図３および図４に示す。ＮＲＥＤＦスケジューリング・プロセスでは、以下の定義を使用する。
Ｎ＝｛ｎｊ、ｊ＝０、…、Ｊ｝は、ネットワーク・ノード・セットであり、１つのコンテンツ・サーバ（ｊ＝０）と、Ｉ個のエッジ・サーバ（ｊ＝１、…、Ｉ）と、Ｕ個のクライアント（ｊ＝Ｉ＋１、…、Ｉ＋Ｕ＝Ｊ）とを含む。
ｃｉ（ｔ）は、ｊ番目のノードにおけるキャッシュ容量であり、時間変化関数である。
Ｃｉ（ｔ）は、時点ｔにおけるｊ番目のノードのキャッシュ状態セット、すなわちキャッシュされたコンテンツのリストである。
Ｌ＝｛（ｊ１，ｊ２）、ｊ１ｊ２∈Ｎ｝は、ネットワーク・リンク・セットであり、（ｊ１、ｊ２）はノードｊ１からノードｊ２までのリンクである。
ｂ（ｉ，ｊ，ｔ）は、（ｉ，ｊ）のリンク容量であり、時間変化関数である。
Ｂ（ｉ，ｊ，ｔ）は、時点ｔにおける（ｉ，ｊ）のリンク状態であり、伝送するコンテンツのリストである。
Ｒ（ｔ０）＝｛ｒｑ、ｑ＝１…Ｑ｝は、要求セットであり、時点ｔ＝ｔ０までにクライアントからコンテンツ・サーバに対してなされた全ての要求を表す。ここで、
ｒｑ＝（ｍｑ，ｄｑ，ｕｑ）は、コンテンツＩＤ、配信予定時刻および要求クライアントＩＤで表される要求であり、
ｍｑは、コンテンツ・サイズ｜ｍｑ｜およびリアルタイム・ストリーミング速度｜｜ｍｑ｜｜を有するコンテンツＩＤであり、
ｄｑは、要求ｒｑの配信予定時刻であり、
ｕｑは、そこから地理的位置を識別することができる、要求を行ったクライアント（要求クライアント）のクライアントＩＤである。
Ｓ（ｔ０）＝｛ｓｑ（ｊ１、ｊ２）、（ｊ１、ｊ２）∈Ｌ｝は、要求セットＲ（ｔ０）のスケジューリング・セットである。ここで、
ｓｑ（ｊ１、ｊ２）は、（ｊ１、ｊ２）のトランスポートする要求ｒｑのスケジュール（開始）時刻であり、これは値０に初期化され、
ｅｑ（ｊ１、ｊ２）は、（ｊ１、ｊ２）のトランスポートする要求ｒｑのスケジュール（終了）時刻であり、要求されたコンテンツが速度｜｜ｍｑ｜｜で伝送される場合には、ｅｑ（ｊ１、ｊ２）＝ｓｑ（ｊ１、ｊ２）＋｜ｍｑ｜／｜｜ｍｑ｜｜である。
要求ｒｑの正規化速度はｖ＊ｑ（ｔ）である。ここで、
ｖ＊ｑ（ｔ）＝｜ｍｑ｜／（ｄｑ−ｔ）  （１）
である。
【００１１】
図３のステップ２０５で、要求セットＲ（ｔ０）内の時点ｔ０における各クライアント要求について、コンテンツ・サーバ２０は、上記の数式（１）により正規化速度を計算する。ステップ２１０で、コンテンツ・サーバ２０は、計算した正規化速度の高い順にクライアント要求をソートし、ソート済みクライアント要求リストを生成する。ステップ２１５で、コンテンツ・サーバ２０は、ソート済みクライアント要求リスト内に示される順序に従ってコンテンツの配信をスケジューリングする。次に図４を参照すると、ステップ２１５のさらに詳細な流れ図が示してある。図４のステップ２５５からステップ２７５は、図３のステップ２１０で決定されたソート済みクライアント要求リストに従って要求セットＲ（ｔ０）内の各要求ｒｑについて実行される。その結果、特定の要求ｒｑのスケジュール｛ｓｑ（ｊ，ｋ）、（ｊ，ｋ）∈Ｌ｝は、以前に作成されたスケジューリング・ベクトル｛ｓｘ（ｊ，ｋ）；ｘ＝０、…、ｑ−１｝に基づいて作成される。具体的には、図４のステップ２５５では、コンテンツ・サーバ２０は、ソート済みクライアント要求リストから次にスケジューリングする要求ｒｑ＝（ｍｑ，ｄｑ，ｕｑ）を選択する。ステップ２６０で、コンテンツ・サーバ２０は、要求ｒｑで要求されたコンテンツの供給に利用できるサーバのセットＨｑを識別する。ここで、このサーバのセットは、少なくとも１つのサーバ、例えばコンテンツ・サーバ２０を含む。（コンテンツ・サーバがクライアント要求のコンテンツの供給に利用できるサーバのセットを識別する機能については当技術分野で既知であり、本明細書では説明しない。）このサーバのセットＨｑにおいて、各サーバｉは、要求ｒｑのコンテンツｍｑのソース、ｍｑ∈Ｍｉ（ｔｉ）を有する。ここで、ｔｉはサーバｉのキャッシュが最後に更新された時刻であり、ｔｉ＝ｍａｘ［ｓｐ（ｊ，ｉ）、ｐ＜ｑ］である。ステップ２６５で、コンテンツ・サーバ２０は、要求されたコンテンツｍｑの宛先ｕｑまでの最も早い配信時刻を与える最短経路を求める。例えば、コンテンツ・サーバ２０は、マルチ・ソース最短経路アルゴリズム（例えば当技術分野で既知のダイクストラ法など）を使用して、任意のサーバｉ∈Ｈｑからｕｑまでの最短経路を求める。ステップ２７０で、コンテンツ・サーバ２０は、選択した経路上のリンクのスケジュール｛ｓｑ（ｊ，ｋ）、（ｊ，ｋ）∈Ｌ｝を求め、選択した経路上のサーバのキャッシュ｛Ｍｉ（ｔ）、ｉ∈Ｎ｝を更新し、当技術分野で既知のようにリンク容量およびキャッシュ容量に制約を加える。（ｍａｘ［ｓｑ（ｊ，ｋ）、（ｊ，ｋ）∈Ｌ］＞ｄｑである場合には、スケジューリングを試みてもＲ（ｔ０）に対するスケジューリング・セットを求めることができず、プロセスが中止されることに留意されたい。）最後に、ステップ２７５で、全ての要求が処理されたかどうか、すなわちｑ＝Ｑであるかどうかを確認する。スケジューリングすべき要求がさらにある場合、すなわちｑ＜Ｑである場合には、ｑの値を増分し、すなわちｑ＝ｑ＋１とし、ステップ２５５に戻ってソート済みクライアント要求リストの次の要求について処理を実行する。しかし、全ての要求が既にスケジューリングされている場合には、処理を終了する。
【００１２】
要求セットＲ（ｔ０）内の要求をスケジューリングした結果、コンテンツ・サーバ２０は、要求されたコンテンツの配信のスケジューリング・セットを生成する。時点ｔ０におけるＱ個の要求に対するスケジューリング・セット８１の例を、図５に示す。次いで、コンテンツ・サーバ２０は、スケジューリング・セット８１に従ってコンテンツを配信していくことになる。スケジューリング・セット８１において、個々の要求には、矢印８４で示すように算出された正規化速度に応じて優先順位がつけられている。矢印８４は降順の方向を示している。
【００１３】
しかし、時点ｔ０の後、時点ｔにおいて新たなクライアント要求が到着する可能性もある。さらに、この時点ｔにおいて、コンテンツ・サーバ２０がそれ以前に要求されたコンテンツの一部の配信を既に終了し、残りのクライアント要求がまだ保留状態、すなわち「古い」要求となる可能性もある。こうした１つまたは複数の新しい要求の一部が、古い要求の一部よりも早い配信予定時刻または大きな要求ファイル・サイズを有することもある。このように、時点ｔにおける新しい要求の１つまたは複数の正規化速度が、古い要求の一部のそれより大きい場合もあり得る。コンテンツ・サーバ２０が供給できる要求の数を最大にするために、これらＫ個の古い要求と、時点ｔにおける任意の新しい要求とを一緒にして、上述のＮＲＥＤＦプロセスを用いて再スケジューリングする。従って、時点ｔにおける新しい要求セットＲ（ｔ）が決定され、図３および図４に示すプロセスが繰り返されて、コンテンツを配信するための新しいスケジューリング・セット８３が生成される。これを図６に示す。図６では、１つまたは複数の新しい要求８２が既にスケジューリングされており、Ｋ個の古い要求が新しいスケジューリング・セット８３の中に保留状態で残っている。例示のみを目的として、以前にスケジューリングされたクライアント要求の配信も破線で図６に示してある。破線で示したのは、それらのクライアント要求が新しいスケジューリング・セット８３には載らないためである。
【００１４】
残念ながら、クライアント要求速度が増大するにつれて、コンテンツ・サーバ２０は、実際にコンテンツを配信するより、正規化速度を計算し、古い要求を再スケジューリングするのに費やす時間を増やすようになる。従って、新しい要求を受け入れるのに必要な計算時間も比例して増加する。この挙動により、ＮＲＥＤＦ手法の多数のクライアントに対応するスケーラビリティが損なわれる。従って、本発明の原理によれば、ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ＮＲＥＤＦ）スケジューラを用いたコンテンツ・サーバは、再スケジューリングする古い要求の数をしきい値に制限する。
【００１５】
図７を参照すると、本発明の原理による例示的なコンテンツ配信システムが示してある。このコンテンツ配信システムは、コンテンツ・サーバ３００と、通信ネットワーク３１０と、クライアント５０−１および５０−２として表す１つまたは複数のクライアントとを含む。コンテンツ・サーバ３００、クライアント５０−１およびクライアント５０−２は、格納プログラム制御式プロセッサ・プラットフォームを表している。例えば、クライアント５０−１がマイクロプロセッサ型デスクトップ・パーソナル・コンピュータ、クライアント５０−２が携帯電話、コンテンツ・サーバ３００がマルチ・プロセッサ型（高性能）サーバとすることもできる。例えば、通信ネットワーク３１０はインターネットを表し、当技術分野で既知のように交換機能および非交換機能の両方を含み、ルータやエッジ・ノード装置などを含む（全て図７には示していない）。この例では、図７から分かるように、コンテンツ・サーバ３００は、あるインターネット・プロトコル（ＩＰ）アドレス（図示せず）と関連づけられた、インターネット上のある箇所に位置するものとして表されている。さらに、図７に示すように、通信ネットワーク３１０は、コンテンツ配信ネットワーク（ＣＤＮ）３１５を含むこともできる。本発明の概念を除けば、ＣＤＮは、当技術分野で既知のように、コストを抑え、且つクライアント（エンド・ユーザ）のスピードを高めながら、コンテンツ・サーバ（プロバイダ）からクライアントに安全にコンテンツを配信するように設計されたオーバレイ・ネットワーク（公共または私設）である。従って、ＣＤＮ内の他のサーバが、コンテンツ・サーバ３００の制御下で要求されたコンテンツを供給することができることもある。このコンテンツのフォーマットは、静的コンテンツ（例えばウェブ・サイト・コンテンツやファイル）または動的コンテンツ（すなわち素早く変化するコンテンツ）および／あるいはストリーミング・オーディオ／ビデオとすることができる。図７に示す状況では、クライアント５０−１および５０−２が、コンテンツを求める要求をコンテンツ・サーバ３００に送る。これらの要求に応答して、本発明の原理に従って、コンテンツ・サーバ３００は、スレショルド・ベース・ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ｔｈｒｅｓｈｏｌｄ−ｂａｓｅｄ  ｎｏｒｍａｌｉｚｅｄ  ｒａｔｅ  ｅａｒｌｉｅｓｔ  ｄｅｌｉｖｅｒｙ  ｆｉｒｓｔ）（ＴＢ−ＮＲＥＤＦ）スケジューラを用いて配信をスケジューリングする。ＴＢ−ＮＲＥＤＦスケジューラは、再スケジューリングする要求の数にしきい値、すなわち制限を加える。従って、コンテンツ・サーバ３００は、再スケジューリング・オーバヘッドを制限する機能を有し、これにより、コンテンツ・サーバは、システム性能とスケーラビリティをトレードオフすることができる。ＴＢ−ＮＲＥＤＦスケジューリング・プロセスに従い、コンテンツ・サーバ３００は、通信ネットワーク内の経路を介してそれぞれのクライアントに要求されたコンテンツを配信する。例えば、クライアント５０−１から要求された例えばファイルなどのコンテンツは、例示的な経路３１１を介してクライアント５０−１に供給される。例示的��経路３１１は、この例では、ＣＤＮ３１５も通過している。経路３１１は、要求されたコンテンツがクライアント５０−１まで搬送される際に通過する通信ネットワーク３１０の任意の機構および装置を表す。
【００１６】
本発明の原理によるコンテンツ・サーバ３００のハイレベル・ブロック図を、図８に示す。例えば、コンテンツ・サーバ３００は、図８に破線の枠で示すプロセッサ３９０およびメモリ３９５で表されるソフトウェア型プロセッサである。この状況では、コンピュータ・プログラムまたはソフトウェアは、メモリ３９５に格納され、プロセッサ３９０によって実行される。プロセッサ３９０は、１つまたは複数の格納プログラム制御プロセッサを表し、ＴＢ−ＮＲＥＤＦスケジューラ機能の専用でなくてもよい。例えば、プロセッサ３９０は、コンテンツ・サーバ３００のその他の機能を制御することもできる。メモリ３９５は、例えばランダム・アクセス・メモリ（ＲＡＭ）や読み取り専用メモリ（ＲＯＭ）など任意の記憶装置を表し、プロセッサ３９０に内蔵且つ／または外付けすることができ、必要に応じて揮発性且つ／または不揮発性である。コンテンツ・サーバ３００は、コンテンツ・サーバ３００をインターネット３１０に結合する接続３１９を介してクライアント要求５９を受け取る。本発明の原理によれば、コンテンツ・サーバ３００は、受け取ったクライアント要求５９を処理し、要求側クライアントに要求されたコンテンツを供給するためのスケジューリング・セットＳ（ｔ）３７０を生成する、ＴＢ−ＮＲＥＤＦスケジューラ３６０を含む。
【００１７】
最初に、時点ｔ０において、コンテンツ・サーバ３００は、上述の図３および図４の流れ図に示したＮＲＥＤＦプロセスに従って要求の配信をスケジューリングする。ただし、最初の要求セットをスケジューリングした後は、本発明の原理に従い、コンテンツ・サーバ３００は再スケジューリングする要求の数を制限する。例えば、時点ｔにおいて、１つまたは複数の新しい要求８２が到着しており、Ｋ個の古い要求が未配信で残っている。スレショルド・ベース・ノーマライズド・レート・アーリエスト・デリバリ・ファースト（ＴＢ−ＮＲＥＤＦ）プロセスでは、再スケジュールされることになる古い要求の最大数を表すルックバックしきい値Ｔを定義する。従って、ＴＢ−ＮＲＥＤＦ手法では、最大でＴ個の古い要求を再スケジュールする。ここで、Ｔ＜Ｋである。従って、残りのＫ−Ｔ個の古い要求のスケジュールは不変である。これを、時点ｔにおけるスケジューリング・セット３８１として図９に示す。ただし、ｔ＞ｔ０である。Ｔの具体的な値は、システムに応じて経験的に決定することができる。
【００１８】
本発明の原理によるＴＢ−ＮＲＥＤＦプロセスの例示的な流れ図を、図１０に示す。ステップ４０５で、ＴＢ−ＮＲＥＤＦスケジューラ３６０は、時点ｔにおける全ての古い要求の総数Ｋがしきい値Ｔを超えるかどうかを判定する。全ての古い要求の総数Ｋがしきい値Ｔを越えない場合には、ステップ４１０で、ＴＢ−ＮＲＥＤＦスケジューラ３６０は時点ｔにおける全ての新しい要求（すなわちまだスケジューリングされていないクライアント要求）をスケジューリングし、総数Ｋ個の古い要求全てを再スケジューリングする。しかし、時点ｔにおける全ての古い要求の総数Ｋがしきい値Ｔを超える場合には、ステップ４１５で、ＴＢ−ＮＲＥＤＦスケジューラ３６０は、時点ｔにおける全ての新しい要求をスケジューリングし、古い要求のうちＴ個を再スケジューリングする。その結果、古い要求のうちＫ−Ｔ個は再スケジューリングされない。
【００１９】
本発明の原理の別の例示的な実施形態を、図１１、図１２および図１３に示す。この場合も、時点ｔ０において、最初の要求セットＲ（ｔ０）の配信がスケジューリングされ、関連するスケジューリング・セットが生成されているものと仮定する。その後の時点ｔにおいて、Ｋ個の古い要求が依然として残り、１つまたは複数の新しい要求が到着している。要求セットＲ（ｔ）内の要求の総数は、新しい要求の数に古い要求の数Ｋを加えた数に等しいＱである。この例では、コンテンツ・サーバ３００は、２つの追加のパラメータ、ｒｌｏｏｋ−ｂａｃｋおよびＳＴＡＴＥｌｏｏｋ−ｂａｃｋを使用する。パラメータｒｌｏｏｋ−ｂａｃｋは、それを超える古い要求が再スケジューリングされることになる、スケジューリング・セット内の境界を表す要求として定義される。本明細書ではこれをルックバック（ｌｏｏｋ−ｂａｃｋ）要求と呼ぶ。ルックバック要求より下の要求は、再スケジューリング不能要求として定義され、ルックバック要求より上の要求は、再スケジューリング可能要求として定義される。再スケジューリング可能要求は、新しい要求が到着したときにそれらと共に再スケジューリングされるが、再スケジューリング不能要求はスケジュールが固定され、再スケジューリングされることはない。パラメータｒｌｏｏｋ−ｂａｃｋの値がＮＵＬＬである場合は、ルックバック要求が設定されていないことを意味し、このパラメータの値がＮＵＬＬでない場合には、ルックバック要求が設定されていることを表す。そこから、パラメータＳＴＡＴＥｌｏｏｋ−ｂａｃｋは、関連するルックバック・システム状態として定義される。具体的には、パラメータＳＴＡＴＥｌｏｏｋ−ｂａｃｋは、ｒｌｏｏｋ−ｂａｃｋが実行された後のリンクおよびエッジ・サーバの状態を含む。従って、ＳＴＡＴＥｌｏｏｋ−ｂａｃｋ＝｛｛ｃｊ｝，｛Ｃｊ｝，｛ｂ（ｉ，ｊ）｝，｛Ｂ（ｉ，ｊ）｝｝である（上記で定義済み）。
【００２０】
ここで図１１を参照すると、この図は、時点ｔにおけるスケジューリング・セット３８３を示している。図１１から分かるように、要求の１つがｒｌｏｏｋ−ｂａｃｋとして示され、これが、再スケジューリングされない要求と再スケジューリングされる古い要求との間の境界８６を示している。本発明の原理によるＴＢ−ＮＲＥＤＦプロセスの別の例示的な流れ図を、図１２に示す。ステップ５０５で、ＴＢ−ＮＲＥＤＦスケジューラ３６０は、任意の新しい要求を再スケジュール可能要求としてマークする。ステップ５１０で、ＴＢ−ＮＲＥＤＦスケジューラ３６０は、全ての再スケジューリング可能要求を含む要求セットＲ（ｔ）を構成する。ステップ５１５で、ＴＢ−ＮＲＥＤＦスケジューラ３６０は、ｒｌｏｏｋ−ｂａｃｋの現在の値を決定する。パラメータｒｌｏｏｋ−ｂａｃｋの値がＮＵＬＬである場合には、ルックバック要求が設定されていないことを意味する。この場合には、ＴＢ−ＮＲＥＤＦプロセスは通常のＮＲＥＤＦに戻り、ステップ５３０で、ＴＢ−ＮＲＥＤＦスケジューラ３６０は、時点ｔにおける全ての新しい要求（すなわちまだスケジューリングされていないクライアント要求）をスケジューリングし、Ｋ個全ての古い要求を再スケジューリングする。しかし、パラメータｒｌｏｏｋ−ｂａｃｋの値がＮＵＬＬでない場合には、ステップ５２０で、ＴＢ−ＮＲＥＤＦスケジューラ３６０は、指定されたルックバック要求が既に配信されているかどうか、すなわちそのサービスが終了しているかどうかを判定する。指定されたルックバック要求が既に配信されている場合には、ステップ５３０で、全ての新しい要求をスケジューリングし、全ての古い要求を再スケジューリングする。指定されたルックバック要求が終了しているので、未終了の古い要求の数はＴ未満になることに留意されたい。一方、ステップ５２０で、指定されたルックバック要求が終了していないとＴＢ−ＮＲＥＤＦスケジューラ３６０が判定した場合には、ＴＢ−ＮＲＥＤＦスケジューラ３６０は、この要求セットを処理する。具体的には、ステップ５２５で、ＴＢ−ＮＲＥＤＦスケジューラ３６０は、要求ｒｌｏｏｋ−ｂａｃｋから開始するためにＳＴＡＴＥｌｏｏｋ−ｂａｃｋを現在のシステム状態として設定し、ステップ５３０で、ＴＢ−ＮＲＥＤＦスケジューラ３６０は、時点ｔにおける全ての新しい要求をスケジューリングし、古い要求のうちＴ個を再スケジューリングする。その結果として、古い要求のうちＫ−Ｔ個は再スケジューリングされない。
【００２１】
図１２の流れ図のさらなる説明として、擬似コードを図１３に示す。図１３の擬似コードのステップ１３、ステップ１４およびステップ１５から分かるように、要求の総数Ｑ（新しい要求に古い要求を加えた数）がしきい値Ｔより大きく、現在の要求値ｑが（Ｑ−Ｔ）以下である場合には、ステップ１４で、要求がルックバック要求として指定され、ステップ１５で、それに対応する状態が記憶される。
【００２２】
上述のように、コンテンツ・サーバは、再スケジューリングする要求の数を制限し、それにより、より高いクライアント要求速度に応じる機能を実現する。上記の説明では、コンテンツ・サーバがＴＢ−ＮＲＥＤＦプロセスを用いるという状況において、このことを示した。この例では、ＴＢ−ＮＲＥＤＦプロセスを用いたコンテンツ・サーバは、図１から図６に示す制限を行わないＮＲＥＤＦプロセスを用いたコンテンツ・サーバより高いクライアント要求速度に応じる機能を実現する。ただし、ＴＢ−ＮＲＥＤＦプロセスは、新しい要求より正規化速度の低いいくつかの古い要求が再スケジューリングされない可能性があるので、ＮＲＥＤＦプロセスより受け入れる要求が少なくなり、それによりシステム性能が低下する可能性があることに留意されたい。それでも、ＴＢ−ＮＲＥＤＦによってコンテンツ・サーバは再スケジューリング・オーバヘッドを制限できるようになり、それにより、コンテンツ・サーバはシステム性能とスケーラビリティをトレードオフすることもできるようになる。
【００２３】
上記に鑑みて、以上の説明は、本発明の原理の単なる例示に過ぎず、従って、当業者なら、本発明の原理を実施し、本発明の趣旨および範囲内に含まれる、本明細書には明示しない多数の代替構成を考案することができることを理解されたい。例えば、別々の機能要素の状況として説明したが、これらの機能要素は、１つまたは複数の集積回路（ＩＣ）内に実施することもできる。同様に、別々の要素として説明したが、これらの要素の任意の一部または全てを、例えば図１０、図１２および図１３に示すステップの１つまたは複数に対応する関連するソフトウェアを実行する例えばディジタル信号プロセッサなどの格納プログラム制御プロセッサ内に実装することもできる。さらに、本発明の原理は、例えば衛星、Ｗｉｒｅｌｅｓｓ  Ｆｉｄｅｌｉｔｙ（Ｗｉ−Ｆｉ）、携帯電話、Ｂｌｕｅｔｏｏｔｈやそれらの組合せなど、その他のタイプの通信システムにも適用することができる。例えば、分散型通信ネットワークは、有線接続および無線接続を両方とも含むことができる。実際には、本発明の概念は、据え置き型コンテンツ・サーバにも、可動コンテンツ・サーバにも適用することができる。従って、上記の例示的な実施形態に多数の修正を加えることができること、また添付の特許請求の範囲によって定義する本発明の趣旨および範囲を逸脱することなくその他の構成を考案することができることを理解されたい。
【図面の簡単な説明】
【００２４】
【図１】ノーマライズド・レート・アーリエスト・デリバリ・ファースト・スケジューリング・プロセスを使用する従来技術のコンテンツ配信システムを説明する図である。
【図２】ノーマライズド・レート・アーリエスト・デリバリ・ファースト・スケジューリング・プロセスを使用する従来技術のコンテンツ配信システムを説明する図である。
【図３】ノーマライズド・レート・アーリエスト・デリバリ・ファースト・スケジューリング・プロセスを使用する従来技術のコンテンツ配信システムを説明する図である。
【図４】ノーマライズド・レート・アーリエスト・デリバリ・ファースト・スケジューリング・プロセスを使用する従来技術のコンテンツ配信システムを説明する図である。
【図５】ノーマライズド・レート・アーリエスト・デリバリ・ファースト・スケジューリング・プロセスを使用する従来技術のコンテンツ配信システムを説明する図である。
【図６】ノーマライズド・レート・アーリエスト・デリバリ・ファースト・スケジューリング・プロセスを使用する従来技術のコンテンツ配信システムを説明する図である。
【図７】本発明の原理によるコンテンツ配信システムを示す例示的なブロック図である。
【図８】本発明の原理を実施するコンテンツ・サーバを示す例示的なブロック図である。
【図９】本発明の原理による例示的なスケジューリング・セットを示す図である。
【図１０】本発明の原理によるコンテンツ・サーバで使用される例示的な流れ図を示す図である。
【図１１】本発明の原理によるコンテンツ・サーバで使用される別の例示的な実施形態を示す図である。
【図１２】本発明の原理によるコンテンツ・サーバで使用される上記別の例示的な実施形態を示す図である。
【図１３】本発明の原理によるコンテンツ・サーバで使用される上記別の例示的な実施形態を示す図である。
【図１】
2009536498.tif 000003
【図２】
2009536498.tif 000004
【図３】
2009536498.tif 000005
【図４】
2009536498.tif 000006
【図５】
2009536498.tif 000007
【図６】
2009536498.tif 000008
【図７】
2009536498.tif 000009
【図８】
2009536498.tif 000010
【図９】
2009536498.tif 000011
【図１０】
2009536498.tif 000012
【図１１】
2009536498.tif 000013
【図１２】
2009536498.tif 000014
【図１３】
2009536498.tif 000015
【手続補正書】
【提出日】平成21年4月23日(2009.4.23)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
サービスの供給に使用される方法であって、
前記サービスを求める新しい要求を受け取るステップと、
再スケジューリングされる古い要求の数がしきい値に制限されるように前記新しい要求および任意の古い要求の配信をスケジューリングするステップと、
を含む前記方法。
【請求項２】
前記スケジューリングするステップが、
前記新しい要求の配信をスケジューリングするステップと、
古い要求の数Ｋを求めるステップと、
前記古い要求の数が前記しきい値より大きい場合に、最大で前記しきい値の数だけの古い要求の配信を再スケジューリングするステップと、
を含む、請求項１に記載の方法。
【請求項３】
前記新しい要求および古い要求が要求セットを形成し、
前記スケジューリングするステップが、
ルックバック要求が前記要求セット内に設定されているかどうかを判定するステップと、
ルックバック要求が設定されていない場合に、全ての古い要求が再スケジューリングされるようにスケジューリング・セットを決定するステップと、
ルックバック要求が設定されており、前記ルックバック要求が未だ配信されていない場合に、最大で前記しきい値の数だけの古い要求の配信を再スケジューリングするステップと、を含む、請求項１に記載の方法。
【請求項４】
前記スケジューリングするステップが、しきい値に基づくスレショルド・ベース・ノーマライズド・レート・アーリエスト・デリバリ・ファーストを実行する、請求項１に記載の方法。
【請求項５】
前記サービスがコンテンツの配信である、請求項１に記載の方法。
【請求項６】
前記コンテンツがファイルである、請求項５に記載の方法。
【請求項７】
前記コンテンツがストリーミング・ビデオである、請求項５に記載の方法。
【請求項８】
要求クライアントへのサービスの供給に使用される装置であって、
前記サービスを求める新しい要求をスケジューリングし、再スケジューリングされる古い要求の数がしきい値に制限されるように古い要求の配信を再スケジューリングすることによって、要求側クライアントにサービスを配信するためのスケジューリング・セットを形成するプロセッサと、
前記形成されたスケジューリング・セットを記憶するメモリと、
を含む前記装置。
【請求項９】
前記プロセッサが、（ａ）前記新しい要求の配信をスケジューリングし、（ｂ）古い要求の数Ｋを求め、（ｃ）古い要求の数が前記しきい値より大きい場合に、最大で前記しきい値の数だけの古い要求の配信を再スケジューリングする、請求項８に記載の装置。
【請求項１０】
前記新しい要求および古い要求が要求セットを形成し、前記プロセッサが、（ａ）ルックバック要求が前記要求セット内に設定されているかどうかを判定し、（ｂ）ルックバック要求が設定されていない場合に、全ての古い要求が再スケジューリングされるようにスケジューリング・セットを決定し、（ｃ）ルックバック要求が設定されており、前記ルックバック要求が未だ配信されていない場合に、最大で前記しきい値の数だけの古い要求の配信を再スケジューリングする、請求項８に記載の装置。
【請求項１１】
前記プロセッサが、しきい値に基づくスレショルド・ベース・ノーマライズド・レート・アーリエスト・デリバリ・ファーストを実行する、請求項８に記載の装置。
【請求項１２】
前記サービスがコンテンツの配信である、請求項８に記載の装置。
【請求項１３】
前記コンテンツがファイルである、請求項１２に記載の装置。
【請求項１４】
前記コンテンツがストリーミング・ビデオである、請求項１２に記載の装置。
【請求項１５】
実行されたときにプロセッサ・ベース・システムがサービスを求める要求に応答して配信をスケジューリングする方法を実行するプロセッサ・ベース・システム用のコンピュータ実行可能命令を有するコンピュータが読取り可能な媒体であって、前記方法が、
前記サービスを求める新しい要求を受け取るステップと、
再スケジューリングされる古い要求の数がしきい値に制限されるように前記新しい要求および古い要求の配信をスケジューリングするステップと、
を含み、
前記新しい要求および古い要求が要求セットを形成し、
前記スケジューリングするステップが、
ルックバック要求が前記要求セット内に設定されているかどうかを判定するステップと、
ルックバック要求が設定されていない場合に、全ての古い要求が再スケジューリングされるようにスケジューリング・セットを決定するステップと、
ルックバック要求が設定されており、前記ルックバック要求が未だ配信されていない場合に、最大で前記しきい値の数だけの古い要求の配信を再スケジューリングするステップと、
を含む、前記コンピュータが読取り可能な媒体。
【国際調査報告】
2009536498.tif 000016
2009536498.tif 000017
2009536498.tif 000018