(57)【特許請求の範囲】
【請求項１】
複数のアプリケーションから複数のリクエストを受信するためのバッファと、
複数の物理サーバであって、前記複数の物理サーバのそれぞれのサーバが、
それぞれの仮想マシンが複数のアプリケーションのうちの異なる１つに関するリクエストを処理する、前記それぞれのサーバ上の１つ又は複数の仮想マシンに対して割り当て可能な１つ又は複数のサーバリソース、及び、
前記それぞれのサーバ上で実行される前記１つ又は複数の仮想マシンに前記１つ又は複数のリソースを割り当てるリソース割り当て決定をシステムパラメータの少なくとも一部に基づいて生成するための、前記それぞれのサーバ上でそれぞれ実行されるローカルリソースマネージャ、
を備える、当該複数の物理サーバと、
前記複数のサーバの中の個々のサーバへの前記複数のリクエストのそれぞれのルーティングを制御するための、前記複数のサーバに通信可能に連結されたルータと、
前記複数のリクエストが前記バッファに入ることを許可するかどうかを前記システムパラメータの少なくとも一部に基づいて決定するためのアドミッションコントローラと、
前記複数のサーバのうちのどのサーバがアクティブであるかを前記システムパラメータの少なくとも一部に基づいて決定するための集中リソースマネージャであって、前記集中リソースマネージャの決定が、前記複数のサーバのそれぞれ及び前記ルータにおけるアプリケーション毎のバックログ情報に依存する、集中リソースマネージャと、
を備え、
さらに、前記アドミッションコントローラによってなされるアドミッションコントロールに関する決定、前記複数のサーバのそれぞれにおける各ローカルリソースマネージャによってローカルで行われる、リソース割り当てに関してなされる決定、及び、前記ルータによる、複数のサーバ間の、アプリケーションに関するリクエストのルーティングに関する決定は、互いに切り離され、前記システムパラメータの少なくとも一部に基づいてそれぞれ決定される、
システム。
【請求項２】
前記アドミッションコントローラが、それぞれのアプリケーションについて許可するリクエストの数を、前記アプリケーションについて受信されるパケットの数と前記アドミッションコントローラにおける前記アプリケーションに関する前記バックログと前記システムパラメータと前記アプリケーションの優先度とに基づいて、選択する、請求項１に記載のシステム。
【請求項３】
前記システムパラメータが、集中リソースマネージャによって設定される、請求項２に記載のシステム。
【請求項４】
前記アドミッションコントローラが、それぞれのアプリケーションについて許可するリクエストの前記数を、前記アプリケーションについて受信されるパケットの前記数と前記アドミッションコントローラにおける前記アプリケーションに関する前記バックログから前記システムパラメータと前記アプリケーションの前記優先度との積を減じた数に等しい量との積に基づいて、選択する、請求項２に記載のシステム。
【請求項５】
前記アドミッションコントローラが、それぞれのアプリケーションについて許可するリクエストの前記数を、前記アプリケーションについて受信されるパケットの前記数と前記アドミッションコントローラにおける前記アプリケーションに関する前記バックログから前記システムパラメータと前記アプリケーションの前記優先度との積を減じた数に等しい量との積を最小化することに基づいて、選択する、請求項４に記載のシステム。
【請求項６】
前記アドミッションコントローラが、前記アドミッションコントローラにおける前記アプリケーションに関する前記バックログが、前記システムパラメータと前記アプリケーションの前記優先度との積以下である限り、すべての新しいリクエストを許可し、前記アドミッションコントローラにおける前記アプリケーションに関する前記バックログが、前記システムパラメータと前記アプリケーションの前記優先度との前記積より大きい場合、前記新しいリクエストを許可しない、請求項５に記載のシステム。
【請求項７】
前記ルータが、アプリケーションに関する前記リクエストのうちの１つに対するルーティング決定を、前記アプリケーションをサポートするどの仮想マシンが最も短い処理すべきリクエストのバックログを有するかに基づいて、行う、請求項１に記載のシステム。
【請求項８】
前記ローカルリソースマネージャが、リソース割り当てを、前記サーバ上の前記アプリケーションの前記バックログと前記アプリケーションに関するリクエストを記憶するキューに関連する処理速度と前記システムパラメータとアプリケーションの優先度と前記アプリケーションに関連する電力消費とに基づいて、選択する、請求項１に記載のシステム。
【請求項９】
前記ローカルリソースマネージャが、前記リソース割り当てを、前記サーバ上の前記複数のアプリケーションのそれぞれのアプリケーションの前記バックログと前記サーバ上の前記アプリケーションの前記バックログを記憶する前記キューの前記処理速度との積の総和から、前記システムパラメータと前記アプリケーションの優先度と前記アプリケーションに関連する前記電力消費との積の総和を、減じた数に基づいて選択する、請求項８に記載のシステム。
【請求項１０】
前記ローカルリソースマネージャが、前記リソース割り当てを、前記サーバ上の前記複数のアプリケーションのそれぞれのアプリケーションの前記バックログと前記サーバ上の前記アプリケーションの前記バックログを記憶する前記キューの前記処理速度との積の総和から、前記システムパラメータと前記アプリケーションの優先度と前記アプリケーションに関連する前記電力消費との積の総和を、減じた数を最大化することに基づいて選択する、請求項９に記載のシステム。
【請求項１１】
前記アドミッションコントローラが、前記集中リソースマネージャからの制御決定及びシステムパラメータに応じて、及び前記複数のアプリケーションのそれぞれのための各サーバ上のキューの報告されたバッファバックログに応じて、動作する、請求項１に記載のシステム。
【請求項１２】
前記集中リソースマネージャが、前記複数のサーバのうちのどれがアクティブであるかに基づいて、１つ又は複数のアプリケーションのリクエストを再ルーティングする指示を前記ルータに送信するように動作可能である、請求項１に記載のシステム。
【請求項１３】
前記集中リソースマネージャが、仮想マシンのバックログモニタによって報告されたバックログに基づいて、どのサーバがアクティブであるべきかを決定するように動作可能である、請求項１に記載のシステム。
【請求項１４】
前記ルータが、アプリケーションのリクエストを記憶するバッファのバッファバックログを、前記集中リソースマネージャに報告するように動作可能である、請求項１２に記載のシステム。
【請求項１５】
前記それぞれのサーバが、複数のキューをさらに備え、各キューが、１つの仮想マシンに関連付けられ、前記複数のアプリケーションのうちの１つに関するリクエストを記憶する、請求項１に記載のシステム。
【請求項１６】
前記それぞれのサーバが、１つ又は複数のバックログモニタを備え、前記１つ又は複数のバックログモニタのそれぞれが、前記１つ又は複数の仮想マシンのうちの１つのためのリソースに関するバックログを監視する、請求項１に記載のシステム。
【請求項１７】
前記リソースは、ＣＰＵリソース、メモリリソース、及びネットワーク帯域幅リソースのうちの１つ又は複数を含む、請求項１に記載のシステム。
【請求項１８】
前記それぞれのサーバが、ローカルリソースを制御する１つ又は複数のローカルリソースコントローラをさらに備え、さらに、前記ローカルリソースマネージャが、前記ローカルリソースを制御する１つ又は複数のローカルリソースコントローラに制御決定を送信する、請求項１に記載のシステム。
【請求項１９】
複数のアプリケーションから複数のリクエストを受信するためのバッファと、
複数のサーバであって、前記複数の物理サーバのそれぞれのサーバが、
それぞれの仮想マシンが複数のアプリケーションのうちの異なる１つに関するリクエストを処理する、前記それぞれのサーバ上の１つ又は複数の仮想マシンに対して割り当て可能な１つ又は複数のサーバリソース、及び、
前記１つ又は複数の仮想マシンに前記１つ又は複数のリソースを割り当てるリソース割り当て決定をシステムパラメータの少なくとも一部に基づいて生成するためのローカルリソースマネージャ、
を備える、当該複数のサーバと、
前記複数のサーバの中の個々のサーバへの前記複数のリクエストのそれぞれのルーティングを制御するための、前記複数のサーバに通信可能に結合されたルータと、
前記複数のリクエストがデータセンターに入ることを許可するかどうかを前記システムパラメータの少なくとも一部に基づいて決定するためのアドミッションコントローラであって、それぞれのアプリケーションについて許可するリクエストの数を、前記アプリケーションについて受信されるパケットの数と、前記アドミッションコントローラにおける前記アプリケーションに関するリクエストのバックログからシステムパラメータと前記アプリケーションの優先度との積を減じた数に等しい量と、の積を最小化することに基づいて選択する、アドミッションコントローラと、
を備える、システム。
【請求項２０】
前記アドミッションコントローラが、前記アドミッションコントローラにおける前記アプリケーションに関する前記バックログが、前記システムパラメータと前記アプリケーションの前記優先度との積以下である限り、すべての新しいリクエストを許可し、前記アドミッションコントローラにおける前記アプリケーションに関する前記バックログが、前記システムパラメータと前記アプリケーションの前記優先度との前記積より大きい場合、新しいリクエストを許可しない、請求項１９に記載のシステム。
【請求項２１】
前記ローカルリソースマネージャが、前記リソース割り当てを、前記サーバ上の前記複数のアプリケーションのそれぞれのアプリケーションの前記バックログと前記サーバ上の前記アプリケーションの前記バックログを記憶するキューの処理速度との積の総和から、前記システムパラメータと前記アプリケーションの優先度と前記アプリケーションに関連する電力消費との積の総和を、減じた数を最大化することに基づいて選択する、請求項２０に記載のシステム。
【請求項２２】
複数のアプリケーションから複数のリクエストを受信するためのバッファと、
複数のサーバであって、前記複数のサーバのそれぞれのサーバが、
それぞれの仮想マシンが複数のアプリケーションのうちの異なる１つに関するリクエストを処理する、前記それぞれのサーバ上の１つ又は複数の仮想マシンに対して割り当て可能な１つ又は複数のサーバリソース、及び、
前記１つ又は複数の仮想マシンに前記１つ又は複数のリソースを割り当てるリソース割り当て決定をシステムパラメータの少なくとも一部に基づいて生成するためのローカルリソースマネージャであり、リソース割り当てを、前記サーバ上の前記複数のアプリケーションのそれぞれのアプリケーションのバックログと前記サーバ上の前記アプリケーションの前記バックログを記憶するキューの処理速度との積の総和から、前記システムパラメータと前記アプリケーションの優先度と前記アプリケーションに関連する電力消費との積の総和を、減じた数を最大化することに基づいて選択する、ローカルリソースマネージャ、
を備える、当該複数のサーバと、
前記複数のサーバの中の個々のサーバへの前記複数のリクエストのそれぞれのルーティングを制御するための、前記複数のサーバに通信可能に結合されたルータと、
前記複数のリクエストがデータセンターに入ることを許可するかどうかを前記システムパラメータの少なくとも一部に基づいて決定するためのアドミッションコントローラと、
を備える、システム。
【請求項２３】
複数のアプリケーションから複数のリクエストをバッファにより受信するステップと、
複数のアプリケーションのうちの異なる１つに関するリクエストを処理するそれぞれの仮想マシン、及び、それぞれのサーバ上で実行される１つ又は複数の仮想マシンに１つ又は複数のリソースを割り当てるリソース割り当て決定をシステムパラメータの少なくとも一部に基づいて生成するための、前記それぞれのサーバ上で実行されるローカルリソースマネージャ、を含む複数の物理サーバのそれぞれの前記１つ又は複数の仮想マシンに対して割り当て可能な前記１つ又は複数のサーバリソースを割り当てるステップと、
前記複数のサーバの中の個々のサーバへの前記複数のリクエストのそれぞれのルーティングを制御するステップと、
前記複数のリクエストが前記バッファに入ることを許可するかどうかをアドミッションコントローラが前記システムパラメータの少なくとも一部に基づいて決定するステップと、
前記複数のサーバのうちのどのサーバがアクティブであるかを集中リソースマネージャが前記システムパラメータの少なくとも一部に基づいて決定するステップであって、前記集中リソースマネージャの決定が、前記複数のサーバのそれぞれ及びルータにおけるアプリケーション毎のバックログ情報に依存する、ステップと、
を含み、
さらに、前記アドミッションコントローラによってなされるアドミッションコントロールに関する決定、前記複数のサーバのそれぞれにおける各ローカルリソースマネージャによってローカルで行われる、リソース割り当てに関してなされる決定、及び前記ルータによる、複数のサーバ間の、アプリケーションに関するリクエストのルーティングに関する決定は、互いに切り離され、前記システムパラメータの少なくとも一部に基づいてそれぞれ決定される、
方法。
【請求項２４】
前記アドミッションコントローラが、それぞれのアプリケーションについて許可するリクエストの数を、前記アプリケーションについて受信されるパケットの数と前記アドミッションコントローラにおける前記アプリケーションに関する前記バックログと前記システムパラメータと前記アプリケーションの優先度とに基づいて、選択するステップ、
をさらに含む、請求項２３に記載の方法。
【請求項２５】
前記アドミッションコントローラが、それぞれのアプリケーションについて許可するリクエストの数を、前記アプリケーションについて受信されるパケットの数と、前記アドミッションコントローラにおける前記アプリケーションに関する前記バックログから前記システムパラメータと前記アプリケーションの優先度との積を減じた数に等しい量と、の積に基づいて選択するステップ、
をさらに含む、請求項２３に記載の方法。
【請求項２６】
前記ローカルリソースマネージャが、リソース割り当てを、前記サーバ上の前記アプリケーションの前記バックログと前記アプリケーションに関するリクエストを記憶するキューに関連する処理速度と前記システムパラメータとアプリケーションの優先度と前記アプリケーションに関連する電力消費とに基づいて、選択するステップ、
をさらに含む、請求項２３に記載の方法。
【請求項２７】
前記システムパラメータは、
前記システムにおける電力効率とアプリケーション処理の遅延との間のトレードオフを定義する構成可能なパラメータである、請求項１に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
（優先権）
[0001]本特許出願は、２００９年９月１１日に出願された、「Ａ  Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｄａｔａ  Ｃｅｎｔｅｒ  Ａｕｔｏｍａｔｉｏｎ  ｗｉｔｈ  Ｂａｃｋｐｒｅｓｓｕｒｅ  Ａｌｇｏｒｉｔｈｍｓ  ａｎｄ  Ｌｙａｐｕｎｏｖ  Ｏｐｔｉｍｉｚａｔｉｏｎ」と題された、対応する特許仮出願第６１／２４１，７９１号の優先権を主張し、当該特許仮出願を参照することにより組み込む。
【０００２】
（発明の分野）
[0002]本発明は、データセンター、自動化、仮想化、及び確率制御の分野に関し、より具体的には、本発明は、分離されたアドミッションコントロール、リソース割り当て、及びルーティングを用いるデータセンターに関する。
【背景技術】
【０００３】
（発明の背景）
[0003]データセンターは、同じ物理サーバ上で複数のアプリケーション／サービスをホストすることができるコンピューティング設備を提供する。一部のデータセンターは、ＣＰＵパワー、メモリ、及びハードディスクサイズを含む決まった構成の物理マシン又は仮想マシンを提供する。例えばＡｍａｚｏｎ（登録商標）のＥＣ２クラウドなどの一部のケースでは、大まかな地理的位置を選択するためのオプションも与えられる。その様式では、データセンターのユーザ（例えば、アプリケーション、サービスプロバイダ、企業、個人ユーザなど）は、それらのユーザの需要を見積もり、追加的な／既存の物理マシン又は仮想マシンを要求／解放する責任を負う。データセンターは、電力管理、ラック管理、フェイルセーフプロパティ（ｆａｉｌ−ｓａｆｅ  ｐｒｏｐｅｒｔｙ）などのそれらのデータセンターの運用上のニーズを統計的に独立に（ｏｒｔｈｏｇｏｎａｌｌｙ）決定し、それらを実行する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
[0004]実行を物理マシンの場所から分離し、リソースを自由に移動させる仮想マシン技術に頼ることによって、データセンターにおいて、スケールイン及びスケールアウトの決定、電力管理、帯域幅のプロビジョニングを含むリソースの割り当て及び管理を自動化するように試みる多くの研究が存在する。しかし、データ自動化に関する既存の研究は、予測不可能な負荷に対する堅牢性を示すための厳密性に欠けており、構成可能なノブ（ｋｎｏｂ）を有する同じ最適化フレームワーク内でロードバランシング、電力管理、及びアドミッションコントロールを分離しない。
【課題を解決するための手段】
【０００５】
（発明の概要）
[0005]データセンターの自動化のための方法及び装置が、本明細書において開示される。一実施形態において、仮想化されたデータセンターアーキテクチャは、複数のアプリケーションから複数のリクエストを受信するためのバッファと、複数の物理サーバであって、それぞれのサーバが、それぞれの仮想マシンが複数のアプリケーションのうちの異なる１つに関するリクエストを処理する、前記それぞれのサーバ上の１つ又は複数の仮想マシンに対して割り当て可能な１つ又は複数のサーバリソース、及び、前記それぞれのサーバ上で実行される１つ又は複数の仮想マシンに１つ又は複数のリソースを割り当てるリソース割り当て決定を生成するための、前記それぞれのサーバ上でそれぞれ実行されるローカルリソースマネージャを備える、複数の物理サーバと、複数のサーバの中の個々のサーバへの複数のリクエストのそれぞれのルーティングを制御するための、複数のサーバに通信可能に連結されたルータと、複数のリクエストがバッファに入ることを許可するかどうかを決定するためのアドミッションコントローラと、複数のサーバのうちのどのサーバがアクティブであるかを決定するための集中リソースマネージャであって、集中リソースマネージャの決定は、複数のサーバのそれぞれ及びルータにおけるアプリケーション毎のバックログ情報に依存する、集中リソースマネージャと、を備える。
【０００６】
[0006]本発明は、以下に与えられる詳細な説明から、及び本発明の種々の実施形態の添付の図面からより完全に理解されることになるが、それらの詳細な説明及び図面は本発明を特定の実施形態に限定すると解釈されるべきではなく、説明及び理解のみを目的とする。
【図面の簡単な説明】
【０００７】
【図１】データセンターの自動化のための高レベルアーキテクチャの一実施形態を示す図である。
【図２】本発明の一実施形態におけるアーキテクチャ上のコンポーネントの役割と、それらのコンポーネント間に存在するシグナリングとを示す例示的な構成図である。
【図３】コンピュータシステムの構成図である。
【発明を実施するための形態】
【０００８】
（発明の詳細な説明）
[0007]複数のアプリケーションをホストする複数の物理マシン（例えば、サーバ）を有する仮想化されたデータセンターが、開示される。一実施形態において、それぞれの物理マシンは、その物理マシン上でホストされるすべてのアプリケーションに対して仮想マシンを与えることによってアプリケーションのサブセットにサービスを提供することができる。アプリケーションは、データセンターの異なる仮想マシンのあちこちで実行される複数のインスタンスを有してもよい。概して、アプリケーションは、多階層化される可能性があり、アプリケーションのインスタンスに対応する異なる階層が、異なる物理マシン上で実行される異なる仮想マシンに位置付けられ得る。本明細書の目的のために、用語「サーバ」及び「マシン」は、交換可能に使用される。
【０００９】
[0008]一実施形態において、それぞれのアプリケーションに関するジョブは、そのジョブ（すなわち、リクエスト）を許可又は拒絶することを決定する、データセンターの入り口にあるアドミッションコントローラによって、初めに処理される。一実施形態において、分散制御アルゴリズムにおけるアドミッションコントロール決定は、単純な閾値に基づく解である。
【００１０】
[0009]ジョブが許可されると、それらのジョブは、それらのジョブのそれぞれのアプリケーションのルーティング／ロードバランシングキューにバッファリングされる。ロードバランサ／ルータは、同じアプリケーションをサポートする複数の仮想マシン（ＶＭ）が存在する場合に、特定のアプリケーションのどのジョブがどのＶＭに転送されるべきかを決定する。
【００１１】
[0010]一実施形態において、それぞれのジョブはアトミックである、すなわち、それらのジョブは、所与のＶＭにおいて独立に処理されることができ、１つのジョブの拒否／拒絶は、その他のジョブに影響しない。ウェブサービスにおいて、例えば、ジョブは、ｈｔｔｐリクエストである可能性がある。分散／並列コンピューティングにおいて、ジョブは、出力が計算のその他の部分に依存しない、より大きな計算の一部分である可能性がある。ストリーミングにおいて、ジョブは、初期セッション設定リクエストである可能性がある。ジョブ及びデータプレーン（ｄａｔａ  ｐｌａｎｅ）は統計的に独立（ｏｒｔｈｏｇｏｎａｌ）であり、例えば、ビデオストリーミングセッションにおいて、ジョブはビデオリクエストであり、サーバとセッションが確立されると、そのセッションはそのサーバからサービスを提供され、後続のメッセージ交換は、アドミッションコントローラ又はロードバランサを通る必要がないことに留意されたい。
【００１２】
[0011]一実施形態において、それぞれのＶＭで、監視システムが、そのＶＭのサービスバックログ（すなわち、未終了のジョブの数）を追跡する。一実施形態において、データセンターにおけるリソース割り当て決定は、（ｉ）大域的最適化問題を解くことによって、比較的大きな時間的尺度で、アクティブである必要がある物理サーバを決定する（サーバの残りはスリープ／待機／省電力モードにされる）集中型エンティティによって、並びに（ｉｉ）それぞれのＶＭのジョブのバックログと電力消費とのバランスを取るように試みる最適化決定の結果としてのクロックスピード及び電圧の選択によって、比較的短い時間的尺度で（及びローカルでその他のサーバとは独立に）個々の物理サーバによって処理される。アクティブなマシンの一部が省電力のためにオフにされ得ると集中型エンティティが決定する場合、それらのマシンでキューに入れられたアプリケーションのジョブは、（ｉ）保留され、後で当該サーバが再び元に戻るときにサービスを提供される、（ｉｉ）ロードバランサ／ルータを用いて、同じアプリケーションのＶＭのうちの１つに再ルーティングされる、（ｉｉｉ）ＶＭのマイグレーションによってその他の物理マシンに移動される（したがって、同じ物理マシン上の複数のＶＭが同じアプリケーションにサービスを提供している可能性がある）、及び／又は（ｉｖ）ジョブの喪失に対処するためのアプリケーションレイヤに頼ることによって破棄される可能性がある。一実施形態において、集中型エンティティがより多くのサーバをアクティブにすることを決定する場合、ロードバランサは、ロードバランサのキューで待っているジョブがこれらの新しい場所にルーティングされ得るように、そのような決定について知らされる。このことは、（休止モードで待機しているアプリケーションのＶＭがまだ存在しない場合に）新しい場所にインスタンス化されるべきそのようなＶＭに対するクローニング動作を引き起こす可能性がある。
【００１３】
[0012]以下の説明において、多数の詳細が、本発明のより完全な説明を与えるために記載される。しかし、本発明がこれらの特定の詳細なしに実施され得ることは当業者に明らかであろう。その他の場合、本発明を曖昧にすることを避けるために、よく知られた構造及びデバイスは詳細にではなく構成図の形態で示される。
【００１４】
[0013]以下に続く詳細な説明の一部は、コンピュータメモリ内のデータビットに対する操作のアルゴリズム及び記号的表現によって表される。これらのアルゴリズム的な記述及び表現は、データ処理技術に精通した者によって、それらの者の研究の内容を当該技術に精通したその他の者に最も効果的に伝えるために使用される手段である。ここで、及び概して、アルゴリズムは、所望の結果をもたらす自己矛盾のない一連のステップであると考えられる。ステップとは、物理量の物理的操作を必要とするステップである。必ずではないが通常は、これらの量は、記憶、転送、組み合わせ、比較、及びその他の操作を行われ得る電気的又は磁気的信号の形態を取る。これらの信号をビット、値、要素、シンボル、文字、語、数などと呼ぶことが、主に共通使用の理由で便利な場合があることが分かっている。
【００１５】
[0014]しかし、これらの及び同様の用語のすべては、適切な物理量に関連付けられるべきであり、これらの量に付される便宜的なラベルであるに過ぎないことに留意されたい。以下の検討から明らかなように、別途具体的に示されない限り、この説明の全体を通じて、「処理する」、「計算する」、「算出する」、「判定する」、又は「表示する」などの用語を利用する検討は、コンピュータシステムのレジスタ及びメモリ内で物理（電子的）量として表されるデータを操作し、コンピュータシステムのメモリ、レジスタ、その他のそのような情報記憶、送信、若しくは表示デバイス内で同様に物理量として表されるその他のデータに変換するコンピュータシステム、又は同様の電子的コンピューティングデバイスの動作及びプロセスに言及することが理解される。
【００１６】
[0015]本発明は、本明細書の操作を実行するための装置にも関する。この装置は、必要な目的のために専用に構築されることができるか、又はこの装置は、コンピュータに記憶されたコンピュータプログラムによって選択的に起動又は再構成される汎用コンピュータを備えることができる。そのようなコンピュータプログラムは、フロッピー（登録商標）ディスク、光ディスク、ＣＤ−ＲＯＭ、及び光磁気ディスクを含む任意の種類のディスク、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気式若しくは光学式カード、又は電子的命令を記憶するのに好適であり、それぞれがコンピュータのシステムバスに連結された任意の種類の媒体などであるがこれらに限定されないコンピュータ可読記憶媒体に記憶され得る。
【００１７】
[0016]本明細書において示されるアルゴリズム及び表示は、任意の特定のコンピュータ又はその他の装置と本質的に無関係である。さまざまな汎用システムが本明細書の教示によるプログラムと共に使用され得るか、又は必要な方法のステップを実行するためにより特化した装置を構築することが便利であることが判明する可能性がある。さまざまなこれらのシステムのための必要な構造は、以下の説明から明らかになるであろう。さらに、本発明は、任意の特定のプログラミング言語に関連して説明されない。本明細書において説明される本発明の教示を実装するためにさまざまなプログラミング言語が使用され得ることが理解されるであろう。
【００１８】
[0017]機械可読媒体は、機械（例えば、コンピュータ）によって読まれることができる形態で情報を記憶又は送信するための任意のメカニズムを含む。例えば、機械可読媒体は、読み出し専用メモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイスなどを含む。
【００１９】
（システムモデル）
[0018]一実施形態において、仮想化されたデータセンターは、Ｎ個のアプリケーションの組をホストするＭ個のサーバを有する。サーバの組は、本明細書においてはＳで表され、アプリケーションの組は、本明細書においてはＡで表される。それぞれのサーバｊ∈Ｓは、アプリケーションのサブセットをホストする。それぞれのサーバｊは、そのサーバｊ上でホストされるすべてのアプリケーションに対して仮想マシンを与えることによって、それを行う。アプリケーションは、データセンターの異なる仮想マシンのあちこちで実行される複数のインスタンスを有する可能性がある。以下の指示変数が、ｉ∈｛１，２，．．．，Ｎ｝，ｊ∈｛１，２，．．．，Ｍ｝に対して定義される：
アプリケーションｉがサーバｊ上でホストされる場合  ａｉｊ＝１；
その他の場合  ａｉｊ＝０。
【００２０】
[0019]簡単にするために、以下の説明において、すべてのｉ，ｊに対してａｉｊ＝１、すなわち、それぞれのサーバがすべてのアプリケーションをホストすることができると仮定される。これは、例えば、当技術分野でよく知られているライブ仮想マシンマイグレーション／クローニング／レプリケーションのような方法を使用することによって実現され得る。概して、アプリケーションは、多階層化される可能性があり、アプリケーションのインスタンスに対応する異なる階層が、異なるサーバ及び仮想マシンに位置付けられ得る。簡単にするために、それぞれのアプリケーションが単一の階層からなるケースが、以下で説明される。
【００２１】
[0020]必須ではないが、一実施形態において、データセンターは、一実施形態としてタイムスロットシステム（ｔｉｍｅ−ｓｌｏｔｔｅｄ  ｓｙｓｔｅｍ）として動作する。すべてのスロットで、新しいリクエストが、それぞれのアプリケーションｉについて、時間平均レートλｉのリクエスト／スロットであるランダム到着プロセスＡｉ（ｔ）にしたがって、到着する。このプロセスは、システム内の未終了の作業の現在の量とは独立であり、有限の二次モーメントを有するものと仮定される。しかし、Ａｉ（ｔ）の統計のいかなる知識に関する仮定も存在しない。換言すれば、本明細書で説明されるフレームワークは、いかなる時点の作業負荷のモデル化及び予測にも依存しない。例えば、Ａｉ（ｔ）は、異なる状態間の遷移確率が未知である、時間によって変わる瞬間的なレートを有するマルコフ変調プロセスである可能性がある。
【００２２】
[0021]図１は、データセンターのための制御アーキテクチャの一実施形態を示す。図１を参照すると、制御アーキテクチャは、３つのコンポーネントからなる。図１を参照すると、到着するジョブは、アドミッションコントローラ１０１によって許可又は拒否される。それらのジョブが許可されると、それらのジョブは、ルーティングバッファ１０２に記憶される。ルーティングバッファ１０２から、ルータ１０５が、それらのジョブをサーバ１０４１−Ｍのうちの特定の１つにルーティングする。ルータ１０５は、ロードバランシングを実行することができ、したがって、ロードバランサとして動作することができる。サーバ１０４１−Ｍのそれぞれは、異なるアプリケーションのリクエストのためのキューを含む。一実施形態において、サーバ１０４１−Ｍのうちの１つが、特定のアプリケーションに関するリクエストを処理するためのＶＭを有する場合、当該サーバは、そのＶＭに関するリクエストを記憶するための別個のキューを含む。
【００２３】
[0022]図２は、データセンターの一実施形態のそれぞれのアーキテクチャ上のコンポーネントの役割と、コンポーネント間のシグナリングとを示す構成図である。図２を参照すると、物理マシン１０４などのそれぞれのサーバは、ローカルリソースマネージャ２１０、１つ又は複数の仮想マシン（ＶＭ）２２１、リソース２１２（例えば、ＣＰＵ、メモリ、ネットワーク帯域幅（例えば、ＮＩＣ））、リソースコントローラ／スケジューラ２１３、及びバックログ監視モジュール２１１を含む。アーキテクチャ上のコンポーネントの残りは、アドミッションコントローラ１０１、ルータ／ロードバランサ１０５、及び集中リソースマネージャ／エンティティ２０１を含む。
【００２４】
[0023]一実施形態において、ルータ１０５は、データセンターのバッファのバッファバックログを集中リソースマネージャ２０１及びアドミッションコントローラ１０１の両方に報告する。アドミッションコントローラ１０１は、少なくとも１つのシステムパラメータ（例えば、Ｖ）と共に制御決定も受信し、これらの入力に応答してアドミッションコントロールを実行する。ルータ１０５は、どのジョブを再ルーティングするべきか、及びどのサーバがアクティブセットに入っているか（すなわち、どのサーバがアクティブであるか）の指示を含む、集中リソースマネージャ２０１からの入力に基づいて、ルーティングバッファ１０２からのジョブのルーティングを行う。
【００２５】
[0024]集中リソースマネージャ２０１は、サーバに接続する。一実施形態において、集中リソースマネージャ２０１は、サーバ１０４のそれぞれのローカルリソースマネージャ２１０からＶＭのバックログの報告を受信し、サーバ１０４に、それらのサーバ１０４がオフにされるべきか、それともオンにされるべきかの指示を送信する。一実施形態において、集中リソースマネージャ２０１は、サーバ１０４のうちのどれがオン／アクティブであるべきか、ということのみを決定する。この決定は、それぞれの仮想マシン及びルータバッファのためのバックログモニタによって報告されるバックログによって決まる。どのサーバがアクティブであるかについての決定がなされると、集中リソースマネージャ２０１は、最適な構成の決定にしたがってサーバ１０４のサーバをオン又はオフにし、アクティブな物理サーバ（すなわち、アクティブな物理サーバ上で実行されるバーチャルマシン（ＶＭ））にのみジョブがルーティングされるように、新しい構成についてルータ１０５に知らせる。この最適な構成が設定されると、ルータ１０５及びローカルマネージャ２１０は、互いに独立に何をなすべきかをローカルで決定することができる（すなわち、互いに分離される）。
【００２６】
[0025]集中リソースマネージャ２０１は、ＶＭに対するジョブが再ルーティングされる必要があるかどうかを決定し、再ルーティングが必要な場合にはルータ１０５に知らせる。これは、例えば、ＶＭがオフにされることになる場合に発生し得る。また、これは、集中リソースマネージャ２０１が、データセンターの最適な構成を決定し、１つ若しくは複数のＶＭ及び／又はサーバがもはや必要ない、又はさらに必要であると決定する場合に発生し得る。一実施形態において、集中リソースマネージャ２０１は、ＶＭをサーバ１０４のそれぞれにクローニング及び／又はマイグレーションするべきかどうかの指示も送信する。
【００２７】
[0026]ローカルリソースマネージャ２１０は、ローカルリソース２１２をそのサーバ内の各ＶＭに割り当てる役割を担う。これは、ローカルリソースマネージャ２１０が、それぞれのＶＭのバックログをチェックし、どのＶＭがどのリソースを受け取るべきかを示す制御決定を行うことによってなされる。ローカルリソースマネージャ２１０は、これらの制御決定を、リソース２１２を制御するリソースコントローラ２１３に送信する。一実施形態において、ローカルリソースマネージャ２１０は、それぞれの仮想化されたサーバのホストオペレーティングシステム（ＯＳ）上に存在する。バックログ監視モジュール２１１は、ＶＭ２２１のそれぞれに関するバックログを監視し、バックログをローカルリソースマネージャ２１０に報告し、ローカルリソースマネージャ２１０は、その情報を集中リソースマネージャ２０１に転送する。一実施形態において、ＶＭのそれぞれに対してバックログ監視ユニットが存在する。別の実施形態において、リソース毎にＶＭ毎のバックログ監視モジュールが存在する。バックログモニタの一実施形態の機能が、特定の例を用いて説明される。同じ物理サーバ上で実行される２つのＶＭ、つまりＶＭ１及びＶＭ２が存在し、ＣＰＵ及びネットワーク帯域幅が監視されている場合、ＶＭ毎にＣＰＵのバックログを監視する１つのバックログモニタと、ネットワークのバックログを監視するもう１つのバックログモニタとの２つのバックログモニタが存在することになる。ＣＰＵのバックログに関して、ＶＭ１のためのモニタは、所与の期間にＶＭ１のＣＰＵの需要がどうであったか、及び同じ期間にＶＭ１に対するＣＰＵの割り当てはどうであったかを見積もる必要がある。需要−割り当て＜０である場合、バックログは減少する。需要−割り当て＞０である場合、バックログはその期間に増加する。同様に、ＶＭ１のモニタは、バックログキューを構築するために、各期間において、ＶＭ１に対して受信されたパケットの数と、ＶＭ１に渡されるパケットの数とを見積もる必要がある。これらのモニタは、ハイパーバイザレベル又はホストＯＳで、ＶＭの外で実行されている。異なるリソースのこれらのバックログは、単位に合わせるために、異なる重み付け、又は異なるスケーリングをされ得る。
【００２８】
[0027]より具体的には、すべてのスロットで、それぞれのアプリケーションｉ∈Ａについて、アドミッションコントローラ１０１が、新たなジョブ（例えば、リクエスト）を許可すべきか、それとも拒絶すべきかを決定する。許可されるリクエストは、そのアプリケーションをホストするサーバ１０４のうちの１つにルータ１０５によってルーティングされる前に、ルータバッファ１０２に記憶される。ｊ∈Ｓのサーバ１０４のそれぞれは、リソースコントローラにしたがって、そのサーバ上でホストされるアプリケーションに割り当てられるリソースの組Ｗｊ（例えば、ＣＰＵ、ディスク、メモリ、ネットワークリソースなどであるが、これらに限定されない）を有する。リソースコントローラが利用可能な制御オプションが、以下で詳細に検討される。説明の残りの部分においては、組Ｗｊは１つのリソースのみを含むと仮定されるが、特に、ネットワーク帯域幅及びメモリなどの複数リソースへの拡張は容易であるので、複数のリソースが割り当てられ得ることに留意されたい。とりわけ、ＣＰＵがボトルネックリソースである場合に焦点を当てる。これは、例えば、サーバ上で実行されるすべてのアプリケーションが、計算量が多いものである場合に起こり得る。データセンターのＣＰＵは、それらのＣＰＵに割り当てられる電力を調整することによって異なる速度で動作させられ得る。この関係は、ネットワークコントローラに知られている電力−速度曲線によって示され、当技術分野でよく知られている。これは、当技術分野でよく知られている方法で、いくつかの既存のモデルのうちの１つを使用してモデル化され得ることに留意されたい。それぞれの物理マシンに関するデータは、オフライン測定によって、及び／又は製造元から提供されたデータシートを用いて取得され得ることにも留意されたい。
【００２９】
[0028]一実施形態において、データセンターのすべてのサーバは、リソースが制約されている。とりわけ、以下では、電力の制約に焦点を当てる。最新のＣＰＵは、当技術分野でよく知られており、以下でより詳細に説明される技術を用いて、実行時に異なる速度で動作させられ得る。一実施形態において、ＣＰＵは、ローカルリソースコントローラに知られている非線形の電力−周波数の関係にしたがうものと仮定される。ＣＰＵは、関連する電力消費［Ｐｍｉｎ，Ｐｍａｘ］を有する区間［ｆｍｉｎ，ｆｍａｘ］内の有限個の動作周波数で実行され得る。これは、性能と電力コストとの間の折り合いをつけることを可能にする。一実施形態において、データセンターのすべてのサーバは、同一のＣＰＵリソースを有し、同じ方法で制御され得る。
【００３０】
[0029]サーバは、エネルギーコストを抑えるために、現在の作業負荷が低い場合、非アクティブモード（省電力（例えば、Ｐ−ｓｔａｔｅ）、待機、オフ、又はＣＰＵハイバネーション）で動作させられ得る。同様に、非アクティブなサーバは、潜在的に作業負荷の増加に対処するためにアクティブにされ得る。非アクティブなサーバは、そのサーバ上でホストされるアプリケーションにいかなるサービスも提供することができない。さらに、一実施形態において、すべてのスロットで、新しいリクエストは、アクティブなサーバにのみルーティングされ得る。
【００３１】
[0030]サーバを頻繁にＯＮ／ＯＦＦすることは、（例えば、ハードウェアの信頼性の問題により）一部の実施形態において望ましくない可能性があるので、以下では、時間がＴ個のスロットの長さのフレームに分割されるフレームに基づく制御ポリシーの種類に焦点を当てる。一実施形態において、アクティブなサーバの組は、各フレームの初めに選択され、そのフレームの間、変更されずに維持される。この組は、潜在的に、作業負荷の変化にともなって次のフレームで変わる可能性がある。この制御決定が比較的遅い時間尺度で行われる一方で、その他のリソース割り当て決定（アドミッションコントロール、ルーティング、及びそれぞれのアクティブなサーバにおけるリソース割り当てなど）は、すべてのスロットで行われることに留意されたい。
【００３２】
[0031]Ａｉ（ｔ）は、スロットｔにおけるアプリケーションｉに関する新しいリクエストの数を表すものとする。言い換えると、Ａｉ（ｔ）は、到着率を表す。Ｒｉ（ｔ）は、Ａｉ（ｔ）のうち、アドミッションコントローラ１０１によって、アプリケーションｉのためのルータバッファ１０２に入ることを許可されるリクエストの数であるとする。このバッファは、Ｗｉ（ｔ）と表され、そのアプリケーションのためのルーティングバッファのバックログを示す。アドミッションコントローラ１０１によって許可されないすべての新しいリクエストは拒絶され、その結果、すべてのｉ、ｔに対して以下の制約、すなわち、
【数１】
0005584765.tif 000002
が適用され、この制約は、直ちに受け入れられない到着が将来のアドミッション決定のためにバッファに記憶される場合に容易に一般化され得る。
【００３３】
[0032]Ｒｉｊ（ｔ）は、スロットｔにおいてルータバッファ１０２からサーバｊにルーティングされる、アプリケーションｉに関するリクエストの数であるものとする。そのとき、Ｗｉ（ｔ）に関するキューの変化規則は、
【数２】
0005584765.tif 000003
によって与えられる。Ｗｉ（ｔ）は、ルータに保有されるジョブキューであり、Ｗｉ（ｔ）は、アプリケーションｉのためのルータキューの現在のバックログである。
【００３４】
[0033]Ｓ（ｔ）は、スロットｔにおけるアクティブなサーバの組を表すものとする。それぞれのアプリケーションｉについて、許可されたリクエストのみが、アプリケーションｉをホストし、スロットｔにおいてアクティブであるサーバにルーティングされ得る。したがって、ルーティング決定Ｒｉｊ（ｔ）は、すべてのスロットにおいて以下の制約、すなわち、
【数３】
0005584765.tif 000004
を満たす。
【００３５】
[0034]それぞれのサーバのリソースコントローラは、すべてのスロットに対して、そのサーバ上で実行されるアプリケーションをホストする仮想マシン（ＶＭ）内で、それぞれのサーバのリソースを割り当てる。一実施形態において、この割り当ては、利用可能な制御オプションに依存する。例えば、それぞれのサーバのリソースコントローラは、ＣＰＵの異なる割合（又は、マルチコアプロセッサの場合には異なる数のコア）をそのスロットにおいて仮想マシンに割り当てる可能性がある。このリソースコントローラは、電力割り当てを変えることによってＣＰＵの速度を調整するために、動的周波数制御（ｄｙｎａｍｉｃ  ｆｒｅｑｕｅｎｃｙ  ｓｃａｌｉｎｇ）（ＤＦＳ）、動的電圧制御（ｄｙｎａｍｉｃ  ｖｏｌｔａｇｅ  ｓｃａｌｉｎｇ）、又は動的電圧及び周波数制御（ｄｙｎａｍｉｃ  ｖｏｌｔａｇｅ  ａｎｄ  ｆｒｅｑｕｅｎｃｙ  ｓｃａｌｉｎｇ）などの技術を用いることもできる。文字Ｉｊは、サーバｊにおいて利用可能なすべてのそのような制御オプションの組を表すために使用される。これは、電力が全く消費されないようにサーバｊを非アクティブにするオプションも含む。Ｉｊ（ｔ）∈Ｉｊは、サーバｊにおいて任意のポリシーの下でスロットｔでなされた特定の制御決定を表すものとし、Ｐｊ（ｔ）は対応する電力割り当てであるものとする。そのとき、サーバｊのアプリケーションｉのリクエストに関するキューの変化規則は、
【数４】
0005584765.tif 000005
によって与えられ、ここで、μｉｊ（Ｉｊ（ｔ））は、制御アクションＩｊ（ｔ）を行うことによってスロットｔにおいてサーバｊ上のアプリケーションｉにもたらされる（リクエスト／スロットを単位とする）サービスレートを表す。リソース割り当てに応じたサービスレートの期待される値は、オフラインでのアプリケーションの分析、又はオンラインでの学習によって分かる。
【００３６】
[0035]したがって、すべてのスロットｔにおいて、制御ポリシーは、以下の決定を行わせる。
【００３７】
１）ｔ＝ｎＴ（すなわち、新しいフレームの始まり）の場合、アクティブなサーバの新しい組Ｓ（ｔ）を決定し、それ以外の場合、現在のフレームに対して既に計算されたアクティブセットを使用し続ける。一実施形態において、この決定は、集中リソースマネージャ２０１によってなされる。
【００３８】
２）すべてのアプリケーションｉに対するアドミッションコントロール決定Ｒｉ（ｔ）。一実施形態において、これは、アドミッションコントローラ１０１によって実行される。
【００３９】
３）許可されたリクエストに関するルーティング決定Ｒｉｊ（ｔ）。一実施形態において、これは、ルータ１０５によって実行される。
【００４０】
４）それぞれのアクティブなサーバにおけるリソース割り当て決定Ｉｊ（ｔ）（これは、電力割り当てＰｊ（ｔ）及びリソース分配を含む）。一実施形態において、これは、ローカルリソースマネージャ２１０によって実行される。
【００４１】
[0036]一実施形態において、オンライン制御ポリシーは、利用可能な制御オプション、及びこのモデルによって課される構造的制約にしたがって、アプリケーションの合計スループットとサーバのエネルギーコストとの複合的な有用性を最大化する。時間によって変わる作業負荷に自動的に適応する柔軟で堅牢なリソース割り当てアルゴリズムを使用することが望ましい。一実施形態において、リアプノフ最適化の技術が、そのようなアルゴリズムを設計するために使用される。この技術は、このアルゴリズムの分析的な性能保証を確立することを可能にする。さらに、一実施形態において、作業負荷のいかなる明確なモデル化も必要とされず、予測に基づくリソースのプロビジョニングは使用されない。
【００４２】
（制御目的の例）
[0037]スロットｔにおいてすべてのｉ，ｊに対して制御決定
【数５】
0005584765.tif 000006
を行うこのモデルに関する任意のポリシーηを考える。任意の実行可能なポリシーηの下で、これらの制御決定は、すべてのｉ，ｊに対してすべてのスロットで、アドミッションコントロール制約（１）、ルーティング制約（３）、及びリソース割り当て制約
【数６】
0005584765.tif 000007
を満たす。
【００４３】
[0038]
【数７】
0005584765.tif 000008
は、ポリシーηの下でアプリケーションｉに関する許可されるリクエストの時間平均の期待されるレートを表すものとし、すなわち、
【数８】
0005584765.tif 000009
である。
【００４４】
[0039]ｒ＝（ｒ１，．．．，ｒＮ）は、これらの時間平均レートのベクトルを表すものとする。同様に、
【数９】
0005584765.tif 000010
は、ポリシーηの下でのサーバｊの時間平均の期待される電力消費を表すものとし、すなわち、
【数１０】
0005584765.tif 000011
である。
【００４５】
[0040]上記の期待は、ポリシーηが行い得るランダム化される可能性がある制御アクションに対するものである。
【００４６】
[0041]αｉ及びβは、一群の非負の重みであるものとし、ここで、αｉはアプリケーションに関連する優先度を表し、βはエネルギーコストの優先度を表す。そのとき、一実施形態における目的は、以下の確率的最適化問題、すなわち、
【数１１】
0005584765.tif 000012
を解くポリシーηを設計することであり、ここで、Λは、上述のように、データセンターモデルの容量範囲を表す。Λは、任意の実行可能なリソース割り当て戦略の下で達成され得るすべての有り得る長期的スループットの値の集合として定義される。一実施形態において、αｉ及びβは、データセンターのオペレータによって設定され、αｉは、一時間に達成されるスループットあたりの金銭的価値を示し、βは、キロワット時（ｋＷｈｒ）あたりの金銭的コストを示す。一実施形態において、それらは１に設定され、ＶＭあたりの計算／時コストが、ＶＭあたりのｋＷｈｒと同じであるとみなされることを意味する。
【００４７】
[0042]問題（７）の目的は、データセンターにおけるアプリケーションの合計スループットと平均電力使用との一般的な重み付けされた線形結合である。この定式化は、いくつかのシナリオを考慮することを可能にする。とりわけ、この定式化は、時間によって変わる作業負荷に適応するポリシーの設計を可能にする。例えば、現在の作業負荷が瞬間的な容量範囲の中にある場合、この目的は、省エネルギーを実現するために、（一部のサーバを非アクティブにすることによって）瞬間的な容量を削減することを促す。同様に、現在の作業負荷が瞬間的な容量範囲の外にある場合、この目的は、（一部のサーバをアクティブにすること及び／又はＣＰＵをより速い速度で実行することによって）瞬間的な容量を増やすことを促す。最後に、作業負荷が非常に高いため、すべての利用可能なリソースを使用しても作業負荷がサポートされ得ない場合、この目的は、さまざまなアプリケーションの間の優先度付けを可能にする。また、この目的は、αｉ及びβの適切な値を選択することによって、優先度を、さまざまなアプリケーションに、並びにスループットとエネルギーとの間に割り当てることを可能にする。
【００４８】
[0043]（７）が実行可能であり、すべてのｉ，ｊに対して、ある任意のポリシーによって実現され得る目的関数の最適値を表すと仮定する。すべてのスロットで現在のキューのバックログとは無関係な制御決定を行う静的でランダム化されたポリシーの種類のみを考えれば十分である。しかし、最適な静的でランダム化されたポリシーを明確に計算することは、すべてのシステムパラメータ（作業負荷統計のような）及び容量範囲を前もって知っていることを必要とするために難しい可能性があり、しばしば非現実的であることがある。たとえ、このポリシーが所与の作業負荷に対して計算可能であったとしても、このポリシーは、作業負荷の予測不可能な変化に対して適応的でなく、再計算されなければならない。次に、これらの困難のすべてを克服するオンライン制御アルゴリズムが、開示される。
【００４９】
（最適制御アルゴリズムの実施形態）
[0044]一実施形態において、リアプノフ最適化のフレームワークが、このモデルのための最適制御アルゴリズムを開発するために使用される。具体的には、すべてのｉ，ｊについて最適解を得るための、確率的最適化問題（７）に対する動的制御アルゴリズムが、示され得る。Ｓの部分集合の以下の集合Ｏが、定義される。
【数１２】
0005584765.tif 000013
[0045]次に示される制御アルゴリズムは、すべてのＴスロットフレームの始めにこの集合からアクティブなサーバの組を選択する。
【００５０】
（データセンター制御アルゴリズム（ＤＣＡ）の例）
[0046]Ｖ≧０は、入力される制御パラメータであるものとする。このパラメータは、アルゴリズムに入力され、有用性−遅延の折り合いをつけることを可能にする。一実施形態において、Ｖパラメータは、データセンターのオペレータによって設定される。
【００５１】
[0047]すべてのｉ，ｊに対するＷｉ（ｔ）、Ｕｉｊ（ｔ）は、スロットｔにおけるキューのバックログの値であるものとする。一実施形態において、これらは０に初期化される。
【００５２】
[0048]すべてのスロットに対して、ＤＣＡアルゴリズムは、そのスロットにおけるバックログの値を用いて、複合的なアドミッションコントロール決定、ルーティング決定、及びリソース割り当て決定を行う。バックログの値は、時間の経過と共に変化規則（２）及び（４）にしたがって展開するので、ＤＣＡによってなされる制御決定は、これらの変化に適応する。しかし、一実施形態において、これは、現在のバックログの値の知識のみを用いて実施され、未来についての知識／到着の統計などに依存しない。したがって、ＤＣＡは、時間の経過と共に一連の最適化問題を満足することによって（７）の目的を解く。キューのバックログ自体は、当技術分野でよく知られている方法で確率的最適化を可能にする動的なラグランジュ乗数とみなされ得る。
【００５３】
[0049]一実施形態において、ＤＣＡアルゴリズムは、以下のように動作する。
【００５４】
[0050]（アドミッションコントロール）：それぞれのアプリケーションｉについて、許可する新しいリクエストの数Ｒｉ（ｔ）を以下の問題、すなわち、
【数１３】
0005584765.tif 000014
の解として選択する。
【００５５】
[0051]この問題は、簡単な閾値に基づく解を有する。特に、アプリケーションｉに関する現在のルータバッファのバックログがＷｉ（ｔ）＞Ｖ・αｉの場合、Ｒｉ（ｔ）＝０であり、新しいリクエストは許可されない。そうではなく、Ｗｉ（ｔ）≦Ｖ・αｉである場合、Ｒｉ（ｔ）＝Ａｉ（ｔ）であり、すべての新しいリクエストが許可される。一実施形態において、このアドミッションコントロール決定は、それぞれのアプリケーションについて別々に実行され得る。また、別の実施形態において、アドミッションコントロールは、この式中のＷｉ（ｔ）とＶ・αｉの位置を入れ替えた上記の量を最小化することに基づくこともできる。
【００５６】
[0052]（ルーティング及びリソース割り当て）：Ｓ（ｔ）は、現在のフレームに対するアクティブなサーバの組であるものとする。一実施形態において、ｔ≠ｎ・Ｔである場合、サーバの同じアクティブセットが、使用され続ける。ルーティング決定及びリソース割り当て決定は、以下のように与えられる。
【００５７】
[0053]（ルーティング）：アクティブなサーバの組が与えられると、ルーティングは、単純な最短待ち行列選択（Ｊｏｉｎ  ｔｈｅ  Ｓｈｏｒｔｅｓｔ  Ｑｕｅｕｅ）ポリシーにしたがう。特に、任意のアプリケーションｉに対して、ｊ｀∈Ｓ（ｔ）は、最も少ないキューのバックログＵｉｊ｀（ｔ）を有するアクティブなサーバであるものとする。Ｗｉ（ｔ）＞Ｕｉｊ｀（ｔ）である場合、Ｒｉｊ｀（ｔ）＝Ｗｉ（ｔ）、すなわち、アプリケーションｉのためのルータバッファ１０２内のすべてのリクエストが、サーバｊ｀にルーティングされる。そうでない場合、すべてのｊに対してＲｉｊ（ｔ）＝０であり、リクエストは、アプリケーションｉのためのいかなるサーバにもルーティングされない。これらの決定を行うために、ルータ１０５は、キューのバックログ情報を必要とする。このルーティング決定は、それぞれのアプリケーションについて別々に実行され得ることに留意されたい。
【００５８】
[0054]（リソース割り当て）：それぞれのアクティブなサーバｊ∈Ｓ（ｔ）において、ローカルリソースマネージャが、以下の問題、すなわち、
【数１４】
0005584765.tif 000015
を解くリソース割り当てＩｊ（ｔ）を選択し、ここで、Ｕｉｊはサーバｊ上のアプリケーションｉのバックログであり、μｉｊは特定のキューの処理速度であり、Ｖはシステムパラメータであり、βは優先度であり、Ｐｊ（ｔ）はサーバｊの電力消費である。Ｐｍｉｎは、この物理サーバがオンであるが、アイドル状態にあるときの、このサーバの最小電力消費である。Ｐｍｉｎは、物理マシン毎に測定され得る。
【００５９】
[0055]上記の問題は、任意のアプリケーションに与えられるサービスレートがそのアプリケーションの現在のキューのバックログによって重み付けされる一般化された最大重み問題（ｍａｘ−ｗｅｉｇｈｔ  ｐｒｏｂｌｅｍ）である。したがって、最適解は、最もバックログがたまっているアプリケーションのサービスレートを最大化するようにリソースを割り当てる。
【００６０】
[0056]この問題の複雑性は、サーバｊで利用可能な制御オプションＩｊの大きさに依存する。実際には、利用可能なＤＶＦＳの状態、ＣＰＵの配分などの制御オプションの数は、少ない／有限であり、したがって、上記の最適化は、リアルタイムで実施され得る。一実施形態において、それぞれのサーバ（例えば、ローカルリソースマネージャ）は、そのサーバ上でホストされるアプリケーションのキューのバックログの値を用いて独立にそのサーバ自身のリソース割り当て問題を解き、これは、完全に分散された形で実施され得る。
【００６１】
[0057]一実施形態において、ｔ＝ｎ・Ｔである場合、現在のフレームに対する新しいアクティブセットＳ＊（ｔ）が、以下を解くことによって決定される。
【数１５】
0005584765.tif 000016
及び制約（１），（３）。
[0058]上記の最適化は、以下のように理解され得る。最適なアクティブセットＳ＊（ｔ）を決定するために、アルゴリズムは、集合Ｏの中のすべての有り得るアクティブなサーバの組について、括弧内の式に対する最適コストを計算する。アクティブセットが与えられると、上記の最大化は、それぞれのアプリケーションに対するルーティング決定と、それぞれのアクティブなサーバにおけるリソース割り当て決定とに分割可能である。この計算は、ｔ≠ｎＴの場合のルーティング及びリソース割り当てのための上述の手順を用いて容易に実行される。Ｏは大きさＭを有するので、このステップの最悪の複雑性は、Ｍの多項式である。しかし、計算は、以下のように大幅に簡単化され得る。任意のサーバｊ上の最大のキューのバックログ＞Ｕｔｈｒｅｓｈである場合、そのサーバは、確実にアクティブセットの一部であることが示され得る。したがって、これらのサーバを含むＯの部分集合のみが、考慮される必要がある。
【００６２】
[0059]アクティブなマシンの一部がそれらのマシンがもはやアクティブセットに入っていないためにオフにされなければならない場合、それらのマシンでキューに入れられたアプリケーションのジョブは、（ｉ）保留され、後で当該サーバが再び元に戻るときにサービスを提供される、（ｉｉ）ロードバランサ／ルータを用いて、同じアプリケーションのＶＭのうちの１つに再ルーティングされる、（ｉｉｉ）ＶＭのマイグレーションによってその他の物理マシンに移動される（したがって、同じ物理マシン上の複数のＶＭが同じアプリケーションにサービスを提供している可能性がある）、（ｉｖ）ジョブの喪失に対処するためのアプリケーションレイヤに依存することによって破棄される、といった可能性がある。最適化の段階がＴスロットフレームの終わりにより多くのサーバをアクティブにすることを決定する場合、ロードバランサは、ロードバランサのキューで待っているジョブがこれらの新しい場所にルーティングされ得るように、そのような決定について知らされる。このことは、（休止モードで待機しているアプリケーションのＶＭがまだ存在しない場合に）新しい場所にインスタンス化されるアプリケーションＶＭに対するクローニング動作を引き起こす可能性がある。
【００６３】
（コンピュータシステムの例）
[0060]図３は、本明細書に記載の操作のうちの１つ又は複数を実行することができる例示的なコンピュータシステムの構成図である。図３を参照すると、コンピュータシステム３００は、例示的なクライアント又はサーバコンピュータシステムを含み得る。コンピュータシステム３００は、情報を伝達するための通信メカニズム又はバス３１１と、情報を処理するための、バス３１１に連結されたプロセッサ３１２とを備える。プロセッサ３１２は、マイクロプロセッサを含むが、例えば、Ｐｅｎｔｉｕｍ（登録商標）、ＰｏｗｅｒＰＣ（登録商標）、Ａｌｐｈａ（登録商標）などのマイクロプロセッサに限定されない。
【００６４】
[0061]システム３００は、情報、及びプロセッサ３１２によって実行される命令を記憶するための、バス３１１に連結されたランダムアクセスメモリ（ＲＡＭ）又はその他のダイナミックストレージデバイス３０４（メインメモリと呼ばれる）をさらに備える。メインメモリ３０４は、プロセッサ３１２による命令の実行中に、一時的な変数又はその他の中間的な情報を記憶するために使用されることもある。
【００６５】
[0062]コンピュータシステム３００は、プロセッサ３１２のための静的な情報及び命令を記憶するための、バス３１１に連結された読み出し専用メモリ（ＲＯＭ）及び／又はその他のスタティックストレージデバイス３０６と、磁気ディスク又は光ディスク及びその対応するディスクドライブなどのデータストレージデバイス３０７とをさらに備える。情報及び命令を記憶するためのデータストレージデバイス３０７が、バス３１１に連結される。
【００６６】
[0063]コンピュータシステム３００は、コンピュータのユーザに情報を表示するための、バス３１１に連結されたブラウン管（ＣＲＴ）又は液晶ディスプレイ（ＬＣＤ）などのディスプレイデバイス３２１にさらに連結され得る。英数字キー及びその他のキーを含む英数字入力デバイス３２２も、プロセッサ３１２に情報及び命令の選択を伝達するために、バス３１１に連結され得る。追加的なユーザ入力デバイスは、プロセッサ３１２に方向の情報及び命令の選択を伝達するための、並びにディスプレイ３２１上のカーソルの動きを制御するための、バス３１１に連結されたマウス、トラックボール、トラックパッド、スタイラス、又はカーソル方向キーなどのカーソルコントロール３２３である。
【００６７】
[0064]バス３１１に連結される可能性がある別のデバイスは、紙、フィルム、又は同様の種類の媒体などの媒体上に情報を描くために使用され得るハードコピーデバイス３２４である。バス３１１に連結される可能性がある別のデバイスは、電話又はハンドヘルドパームデバイスと通信するための有線／無線通信機能３２５である。
【００６８】
[0065]システム３００のコンポーネント及び関連するハードウェアのうちの任意のもの又はすべてが、本発明で使用され得ることに留意されたい。しかし、コンピュータシステムのその他の構成が、これらのデバイスのうちの一部又はすべてを含む可能性があることが理解され得る。
【００６９】
[0066]本発明の多くの変更形態及び修正形態が、上述の説明を読んだ後の当業者に、間違いなく明らかになるであろうが、説明されたどの特定の実施形態も、例として示され、限定とみなされるようには全く意図されていないことを理解されたい。したがって、さまざまな実施形態の詳細に関する言及は、本発明に必須と考えられる特徴だけをそれ自体で記載する特許請求の範囲を限定するように意図されていない。
【図１】
0005584765.tif 000017
【図２】
0005584765.tif 000018
【図３】
0005584765.tif 000019