(57)【要約】  仮想リソース割り当て能力が開示される。仮想リソース割り当て能力は、クラウド環境１１０内での仮想リソースのプロビジョニングをサポートするように構成されている。クラウド環境内での仮想リソースのプロビジョニングは、クラウド環境内での仮想リソースのプロビジョニングを要求するユーザ仮想リソース要求を受信すること、クラウド環境内での仮想リソースの割り当てを指定する仮想リソース割り当て情報を決定すること、および仮想リソース割り当て情報を使用して、クラウド環境内で仮想リソースをプロビジョニングすることを含む。クラウド環境内での要求された仮想リソースの割り当ては、仮想リソースがホストされることになる、クラウド環境のデータセンタ１１１への仮想リソースの割り当てを含み、より詳細には、仮想リソースがホストされることになる、クラウド環境のデータセンタ内での物理リソースへの割り当てを含む。仮想リソースは、仮想プロセッサリソース、仮想メモリリソースなどを含むことができる。物理リソースは、プロセッサリソース１１５、記憶装置リソースなど（たとえば、クラウド環境のデータセンタのラック１１２のブレードサーバ１１４の物理リソース）を含むことができる。
2014522036.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサと、メモリとを含む装置であって、プロセッサが、
要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約を含む、仮想リソースについての要求を受信し、
クラウド環境に関連付けられた管理情報を受信し、
要求された仮想リソースの量、１つまたは複数の仮想リソース割り当て制約、および管理情報を使用して、クラウド環境内での要求された仮想リソースの割り当てを決定するように
構成されている、装置。
【請求項２】
クラウド環境が、複数のデータセンタを含み、管理情報が、
クラウド環境のデータセンタ同士の間のデータセンタ間通信に関連付けられたネットワーク管理情報、および
データセンタのうちの少なくとも１つについての、データセンタに関連付けられた管理情報を含むクラウド管理情報
のうちの少なくとも１つを含む、請求項１に記載の装置。
【請求項３】
１つまたは複数の仮想リソース割り当て制約が、ラックごとに割り当てられるべき仮想リソースの最大量、ラックごとに割り当てられるべき仮想リソースの最小数、データセンタごとに使用されるべきラックの最大数、データセンタごとに使用されるべきラックの最小数、データセンタごとに割り当てられるべき仮想リソースの最大量、データセンタごとに割り当てられるべき仮想リソースの最小量、使用されるべきデータセンタの最大数、および使用されるべきデータセンタの最小数のうちの少なくとも１つを含む、請求項１に記載の装置。
【請求項４】
クラウド環境内での要求された仮想リソースの割り当てを決定することが、
クラウド環境内で利用可能なデータセンタの集合から、仮想リソースが割り当てられることになるデータセンタの集合を決定すること、
仮想リソースが割り当てられることになるデータセンタの集合への仮想リソースの割り当てを決定すること、
仮想リソースが割り当てられることになるデータセンタの集合の少なくとも１つのデータセンタについて、データセンタに割り当てられることになる仮想リソースをホストするためのデータセンタの物理リソースを選択すること、および
仮想リソースのうちの少なくとも１つについて、仮想リソースが割り当てられることになるデータセンタの物理リソースへの仮想リソースの割り当てを決定すること
を含む、請求項１に記載の装置。
【請求項５】
仮想リソースが割り当てられることになるデータセンタの集合を決定することが、
複数の頂点と複数のエッジとを含むグラフとしてクラウド環境を表すことであって、複数の頂点が、利用可能なデータセンタを表し、利用可能なデータセンタに関連付けられた複数の重みを有し、複数のエッジが、利用可能なデータセンタ同士の間の複数の通信パスを表し、利用可能なデータセンタ同士の間の複数の通信パスに関連付けられた複数の長さを有する、グラフとしてクラウド環境を表すこと、
要求された仮想リソースの量に少なくとも等しい重みの総和および最小直径を有する、グラフの部分グラフを決定すること、および
仮想リソースが割り当てられることになるデータセンタの集合を、部分グラフから決定すること
を含む、請求項４に記載の装置。
【請求項６】
仮想リソースが割り当てられることになるデータセンタの集合への仮想リソースの割り当てを決定することが、
仮想リソースを表す複数の頂点と、エッジで接続された仮想リソース同士の間の相対帯域幅を表す複数のエッジとを含むグラフとして、仮想リソースについての要求を表すこと、
分割されたグラフをそれにより形成するために、グラフを複数のパーティションに分割することであって、分割されたグラフの各パーティションが、同じそれぞれのデータセンタにおいてスケジュールされることになる仮想リソースのそれぞれの集合を表し、分割されたグラフの各パーティションが、各パーティションに関連付けられた、それぞれのデータセンタにおいて利用可能な仮想リソースの量によって上に有界であるサイズを有する、グラフを複数のパーティションに分割すること、および
分割されたグラフを使用して、仮想リソースが割り当てられることになるデータセンタの集合への仮想リソースの割り当てを決定すること
を含む、請求項４に記載の装置。
【請求項７】
データセンタに割り当てられることになる仮想リソースをホストするためのデータセンタの物理リソースを選択することが、
データセンタのリソースを表す複数のノードを含むツリー型トポロジとしてデータセンタを表すことであって、ツリー型トポロジのノードの各々が、各々に関連付けられた、ノードに根付いた仮想リソースの量を表す重みを有し、ツリー型トポロジのノードの各々が、各々に関連付けられた、ツリー型トポロジ内のノードの高さを表す高さを有し、複数のノードが、データセンタのそれぞれ複数のラック、ブレードサーバ、またはプロセッサを表す複数の葉ノードを含む、ツリー型トポロジとしてデータセンタを表すこと、
その葉ノードが、データセンタに割り当てられることになる仮想リソースの量に少なくとも等しい累積重み、および最小高さを有する、ツリー型トポロジの部分ツリーを決定すること、ならびに
データセンタに割り当てられることになる仮想リソースをホストするためのデータセンタの物理リソースを、部分ツリーから決定すること
を含む、請求項４に記載の装置。
【請求項８】
仮想リソースが割り当てられることになるデータセンタの物理リソースへの仮想リソースの割り当てを決定することが、
仮想リソースが割り当てられることになるデータセンタのラックを選択すること、
仮想リソースが割り当てられることになるデータセンタの選択されたラックのブレードサーバを選択すること、および
仮想リソースが割り当てられることになるデータセンタの選択されたラックの選択されたブレードサーバの中央処理ユニット（ＣＰＵ）を選択すること
を含む、請求項４に記載の装置。
【請求項９】
コンピュータによって実行されるときにコンピュータに方法を実施させる命令を記憶するコンピュータ可読記憶媒体であって、方法が、
要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約を含む、仮想リソースについての要求を受信するステップと、
クラウド環境に関連付けられた管理情報を受信するステップと、
要求された仮想リソースの量、１つまたは複数の仮想リソース割り当て制約、および管理情報を使用して、クラウド環境内での要求された仮想リソースの割り当てを決定するステップと
を含む、コンピュータ可読記憶媒体。
【請求項１０】
要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約を含む、仮想リソースについての要求を受信するステップ、
クラウド環境に関連付けられた管理情報を受信するステップ、ならびに
要求された仮想リソースの量、１つまたは複数の仮想リソース割り当て制約、および管理情報を使用して、クラウド環境内での要求された仮想リソースの割り当てを決定するステップのために、
プロセッサおよびメモリを使用するステップを含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、仮想リソースの割り当てに関し、限定せずにより詳細には、クラウド環境内での仮想リソースの割り当てに関する。
【背景技術】
【０００２】
クラウド環境を介したクラウドコンピューティングの使用は、普及を伸ばし続けている。クラウド環境は、クラウドコンピューティングユーザのための仮想リソースをホストするために使用される物理リソースを含む。クラウドコンピューティングユーザからの仮想リソース要求に応答して、要求された仮想リソースは、クラウドコンピューティングにおけるユーザによる使用のために、クラウド環境の物理リソース（たとえば、１つまたは複数のデータセンタに設置された１つまたは複数のサーバ）上でプロビジョニングされる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
先行技術におけるさまざまな欠点が、クラウド環境内で仮想リソースを割り当てるための実施形態によって対処される。
【課題を解決するための手段】
【０００４】
一実施形態において、装置が、プロセッサと、メモリとを含み、プロセッサは、要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約を含む、仮想リソースについての要求を受信し、クラウド環境に関連付けられた管理情報を受信し、要求された仮想リソースの量、１つまたは複数の仮想リソース割り当て制約、および管理情報を使用して、クラウド環境内での要求された仮想リソースの割り当てを決定するように構成されている。
【０００５】
一実施形態において、コンピュータ可読記憶媒体が、コンピュータによって実行されるときにコンピュータに方法を実施させる命令を記憶し、方法は、要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約を含む、仮想リソースについての要求を受信するステップと、クラウド環境に関連付けられた管理情報を受信するステップと、要求された仮想リソースの量、１つまたは複数の仮想リソース割り当て制約、および管理情報を使用して、クラウド環境内での要求された仮想リソースの割り当てを決定するステップとを含む。
【０００６】
一実施形態において、方法が、要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約を含む、仮想リソースについての要求を受信するステップ、クラウド環境に関連付けられた管理情報を受信するステップ、ならびに要求された仮想リソースの量、１つまたは複数の仮想リソース割り当て制約、および管理情報を使用して、クラウド環境内での要求された仮想リソースの割り当てを決定するステップのために、プロセッサおよびメモリを使用するステップを含む。
【０００７】
本明細書における教示は、添付の図面と併用して以下の詳細な説明を検討することによって、容易に理解され得るであろう。
【図面の簡単な説明】
【０００８】
【図１】クラウド環境の物理リソースへのＶＭの自動割り当てをサポートするように構成されたシステムの一実施形態を示す図である。
【図２】ＶＭについてのユーザ要求に応答して、クラウド環境のデータセンタ内でＶＭをプロビジョニングするための方法の一実施形態を示す図である。
【図３】クラウド環境のデータセンタ内でＶＭをプロビジョニングするのに使用される、データセンタ内の物理リソースへのＶＭの割り当てを決定するための方法の一実施形態を示す図である。
【図４Ａ】ＶＭが割り当てられることになるデータセンタの集合を決定するように構成された処理を示す図である。
【図４Ｂ】ＶＭが割り当てられることになるデータセンタの集合を決定するように構成された処理を示す図である。
【図５】ＶＭが割り当てられることになるラック、ブレード、およびＣＰＵに対して構成された処理を示す図である。
【図６】本明細書で説明される機能を実施する際の使用に好適なコンピュータの高レベルブロック図である。
【発明を実施するための形態】
【０００９】
理解を容易にするために、可能な限り、同一の参照番号が、各図面に共通である同一の要素を示すために使用されている。
【００１０】
一般に、本明細書では、仮想リソース割り当て能力が示され、説明されているが、さまざまな他の能力がまた、本明細書で提示されてもよい。
【００１１】
少なくともいくつかの実施形態において、仮想リソース割り当て能力は、クラウド環境における物理リソースへの仮想リソースの自動割り当てを提供する。仮想リソースは、仮想コンピューティングリソース、仮想記憶装置リソースなど、ならびにそれらのさまざまな組合せを含むことができる。物理リソースは、プロセッサリソース（たとえば、データセンタのラックのブレードサーバの中央処理ユニット（ＣＰＵ））、記憶装置リソースなどを含むことができる。
【００１２】
少なくともいくつかの実施形態において、仮想リソース割り当て能力は、仮想リソースについてのユーザ要求に応答して、クラウド環境における物理リソースへの仮想リソースの自動割り当てを提供する。少なくともいくつかの実施形態において、仮想リソースについてのユーザ要求が受信され、クラウド環境の物理リソースへの仮想リソースの割り当てが決定され、クラウド環境の物理リソースへの仮想リソースの割り当てに基づいて、仮想リソースがクラウド環境内でプロビジョニングされる。仮想リソースについてのユーザ要求は、仮想リソース要求情報（たとえば、要求された仮想リソースの量、仮想リソース割り当て制約、など）を含むことができ、仮想リソース要求情報は、クラウド環境の物理リソースへの仮想リソースの割り当てを決定するための入力として使用されてよい。クラウド環境の物理リソースへの仮想リソースの決定された割り当ては、仮想リソース割り当て情報（たとえば、要求された仮想リソースが配置されるデータセンタの選択、要求された仮想リソースが配置されるデータセンタ内での機器の選択、など）を使用して、指定されてよい。さまざまな他のタイプの情報（たとえば、データセンタ同士の間の接続性に関連付けられたネットワークトポロジおよび／またはステータス情報、データセンタトポロジおよび／またはステータス情報、など）が、クラウド環境の物理リソースへの仮想リソースの割り当てを決定するために使用されてもよいことに留意されたい。さまざまな他のタイプの情報（たとえば、仮想リソースがホストされることになるラック／ブレードサーバ／ＣＰＵの選択、仮想リソースがホストされることになる特定のラック／ブレードサーバ／ＣＰＵへの特定の仮想リソースのマッピング、など）が、クラウド環境の物理リソースへの仮想リソースの割り当てを指定するために使用されてもよいことに留意されたい。
【００１３】
少なくともいくつかの実施形態において、仮想リソース割り当て能力は、クラウド環境のパフォーマンスを改善することにつながるやり方で（たとえば、ネットワークリソースの利用を改善する）、および仮想リソースを使用するユーザアプリケーションのパフォーマンスを改善することにつながるやり方で（たとえば、通信遅延を削減する、復元力を改善する、など）、クラウド環境における物理リソースへの仮想リソースの自動割り当てを提供する。
【００１４】
本明細書では、仮想リソースが仮想マシン（ＶＭ）であり、物理リソースがブレードサーバのプロセッサである、実施形態のコンテキスト内で主に示され、説明されているが、仮想リソース割り当て能力は、さまざまな他のタイプの仮想リソースの割り当てを決定する、および／またはさまざまな他のタイプの物理リソースへの割り当てを決定するために使用されてもよいことに留意されたい。
【００１５】
図１は、クラウド環境の物理リソースへのＶＭの自動割り当てをサポートするように構成されたシステムの一実施形態を示す。
【００１６】
システム１００は、クラウド環境１１０と、クラウド管理システム（ＣＭＳ）１２０と、ネットワーク管理システム（ＮＭＳ）１３０と、クラウド自動制御システム（ＣＡＳ）１４０と、通信ネットワーク（ＣＮ）１５０とを含む。
【００１７】
クラウド環境１１０は、仮想リソースをホストするように構成された物理リソースを含む。物理リソースは、サーバ、および仮想リソースをホストするように構成された他のタイプの物理リソースを含むことができる。仮想リソースは、仮想マシン（ＶＭ）、仮想記憶装置（ＶＳ）など、ならびにそれらのさまざまな組合せを含むことができる。
【００１８】
クラウド環境１１０は、複数のデータセンタ１１１１−１１１Ｄ（総称してデータセンタ１１１）を含む。
【００１９】
データセンタ１１１は、データセンタリソース（たとえば、コンピューティングリソース、通信リソース、など）を含む。データセンタ１１１は、通信ネットワーク１５０を介して通信するように構成されており、したがって、データセンタ１１１同士が互いに通信することが可能である。データセンタ１１１は、地理的に分散されていてよい。
【００２０】
データセンタ１１１はそれぞれ、仮想リソースをホストするように構成された物理リソースを含む。各データセンタ１１１は、複数のラック１１２１−１１２Ｒ（総称してラック１１２）を含む。各ラック１１２は、複数のブレードサーバ１１４１−１１４Ｂ（総称してブレードサーバ１１４）を含む。各ブレードサーバ１１４は、複数のＣＰＵ１１５１−１１５Ｃ（総称してＣＰＵ１１５）を含む。各ＣＰＵ１１５は、１つまたは複数の関連したＣＰＵコア（明瞭にする目的で省略される）を有していてもよい。ＣＰＵは、ＶＭをホストするように構成されている。データセンタ１１１内のラック１１２、ブレードサーバ１１４、およびＣＰＵ１１５の一般的な配列および動作は、当業者によって理解されるであろう。任意の好適なタイプ、数、および／または配列の、ラック１１２、ブレードサーバ１１４、およびＣＰＵ１１５が、任意のデータセンタ１１１内で使用されてよいことに留意されたい。本明細書では、特定の数のデータセンタ１１１、ラック１１２、ブレードサーバ１１４、およびＣＰＵ１１５に関して主に示され、説明されているが、任意の他の好適な数のデータセンタ１１１、ラック１１２、ブレードサーバ１１４、および／またはＣＰＵ１１５が、クラウド環境１１０において使用されてもよいことに留意されたい（たとえば、クラウド環境１１０は、１つまたは複数のデータセンタ１１１を含むことができ、各データセンタ１１１は、１つまたは複数のラック１１２を含むことができ、各ラックは、１つまたは複数のブレードサーバ１１４を含むことができ、各ブレードサーバ１１４は、１つまたは複数のＣＰＵ１１５を含むことができる）。
【００２１】
データセンタ１１１はそれぞれ、データセンタ内通信およびデータセンタ間通信をサポートするように構成されたデータセンタ通信リソースを含む。
【００２２】
データセンタ１１１のデータセンタ通信リソースは、階層構造に配列される（とはいえ、他のタイプの配列が使用されてもよいことに留意されたい）。
【００２３】
同一ブレードサーバ１１４のＣＰＵ１１５は、（たとえば、いかなるスイッチも通さずに）直接通信することができる。
【００２４】
同一ラック１１２のブレードサーバ１１４のＣＰＵ１１５は、ラック１１２に関連付けられたトップオブラックを介して（ＴＯＲ）スイッチ１１３（説明的に、ラック１１２１−１１２Ｒにそれぞれ関連付けられたＴＯＲスイッチ１１３１−１１３Ｒ）通信することができる。
【００２５】
複数の異なるラック１１２のブレードサーバ１１４のＣＰＵ１１５は、１つまたは複数のスイッチ１１４（一般にアグリゲータスイッチと呼ばれる）、および／またはルータ１１７を介して通信することができる。例示的なデータセンタ１１１１において、たとえば、隣接した対のラック１１２が、アグリゲータスイッチ１１６に結合されている（説明的に、ラック１１２１および１１２２のＴＯＲスイッチ１１３１および１１３２が、アグリゲータスイッチ１１６１に結合され、同様にラック１１２Ｒが、アグリゲータスイッチ１１６Ａに結合されている）。明瞭にする目的で省略されているが、（第１の層のアグリゲータスイッチとして示される）アグリゲータスイッチ１１６は、データセンタにおける第２の層のアグリゲータスイッチに接続されてよいことが認識されるであろう（たとえば、２つ以上の隣接するアグリゲータスイッチ１１６を含む第１の層のアグリゲータスイッチ１１６の組は、それぞれ第２の層のアグリゲータスイッチに結合され、２つ以上の隣接するアグリゲータスイッチ１１６を含む第２の層のアグリゲータスイッチの組は、それぞれ第３の層のアグリゲータスイッチに結合される、など）。この意味において、ラック１１２およびアグリゲータスイッチ１１６は、階層ツリー構造に配列されてよい。結果として、データセンタ１１１内のラック１１２におけるブレードサーバ１１４のＣＰＵ１１５同士の間の待ち時間は、ラック１１２およびアグリゲータスイッチ１１６によって形成される階層ツリー構造内でのラック１１２の位置によって決まる（したがって、ユーザにプロビジョニングされるＶＭ同士の間の通信の待ち時間は、要求されたＶＭがプロビジョニングされるデータセンタ１１１の物理リソースによって決まる）。
【００２６】
データセンタ１１１のデータセンタ通信リソースは、通信の局所性を想定して配列される。各データセンタ１１１内の通信のかなりの部分が、同一ラック１１４のＣＰＵ１１５同士の間にあることになると想定される。データセンタ１１１内でのＣＰＵ１１５同士の間の距離が増加するにしたがって、ＣＰＵ１１５同士の間の利用可能な通信帯域幅は減少する。結果として、データセンタ１１１内でプロビジョニングされる要求されたＶＭ（プロビジョニングされると、データセンタ内通信リソースを介して互いに通信することになる）のための利用可能な通信帯域幅は、少なくとも部分的には、要求されたＶＭがプロビジョニングされるデータセンタ１１１のＣＰＵ１１５によって決まる。同様の意味において、データセンタ１１１の全体効率もまた、少なくとも部分的には、データセンタ１１１内で、要求されたＶＭがプロビジョニングされるＣＰＵ１１５によって決まる。結果として、クラウド環境１１０内でホストするために受け入れられ得るユーザ要求の数もまた、少なくとも部分的には、それぞれ、データセンタ１１１内で、要求されたＶＭがプロビジョニングされるＣＰＵ１１５によって決まる。
【００２７】
データセンタ１１１のラック１１２は、ルータ１１７（およびオプションで、図示されたような１つまたは複数の層のアグリゲータスイッチ１１６）を介して、データセンタ１１１の外部と通信する。
【００２８】
データセンタ通信リソースの一般的な配列および動作は、当業者によって理解されるであろう。
【００２９】
任意の好適なタイプ、数、および／または配列の、スイッチ（たとえば、ＴＯＲスイッチ１１３、アグリゲートスイッチ１１６、など）および／またはルータ（たとえば、ルータ１１７）が、データセンタ１１１のいずれかのうちで、データセンタ内通信およびデータセンタ間通信をサポートするために使用されてよいことに留意されたい。
【００３０】
ＣＭＳ１２０は、クラウド環境１１０を管理するための管理機能を提供するように構成されている。クラウド管理システムによってクラウド環境に一般に提供される管理機能は、当業者によって理解されるであろう。ＣＭＳ１２０は、クラウド環境１１０の管理に関連付けられたクラウド管理情報を維持する。ＣＭＳ１２０は、ユーザ要求に応答して、クラウド環境１１０の物理リソースへのＶＭの割り当てを決定するのに使用されるクラウド管理情報を、ＣＡＳ１４０に提供する。クラウド管理情報は、データセンタ１１１のそれぞれに関連付けられたデータセンタリソース情報（たとえば、現在利用可能なリソース、今後利用可能になることが予想されるリソース、現在のリソースの配分、今後予想されるリソースの配分、リソースのタイプ、リソースの配列、リソースの能力、など）、データセンタ１１１のそれぞれに関連付けられた（たとえば、各ラック内での接続性、ラック同士の間の接続性などに関連付けられた）データセンタトポロジ情報、データセンタ１１１のそれぞれに関連付けられたデータセンタステータス情報（たとえば、リソースステータス情報、接続性ステータス情報、など）その他、ならびにそれらのさまざまな組合せを含むことができる。
【００３１】
ＮＭＳ１３０は、ＣＮ１５０の管理のための管理機能を提供するように構成されている。ネットワーク管理システムによって通信ネットワークに一般に提供される管理機能は、当業者によって理解されるであろう。ＮＭＳ１３０は、ＣＮ１５０の管理に関連付けられたネットワーク管理情報を維持する。ＮＭＳ１３０は、ユーザ要求に応答して、クラウド環境１１０の物理リソースへのＶＭの割り当てを決定するのに使用されるネットワーク管理情報を、ＣＡＳ１４０に提供する。ネットワーク管理情報は、ネットワークトポロジ情報、ネットワークステータス情報など、ならびにそれらのさまざまな組合せを含むことができる。
【００３２】
ＣＡＳ１４０は、ＶＭについてのユーザ要求に応答して、クラウド環境１１０の物理リソースへの要求されたＶＭの割り当てを決定するように構成されている。
【００３３】
ＣＡＳ１４０は、クラウド環境１１０内でのＶＭのプロビジョニングを要求する、ユーザＶＭ要求を受信するように構成されている。ユーザＶＭ要求は、クラウド環境１１０の物理リソースへの要求されたＶＭの割り当てを決定するのに、ＣＡＳ１４０によって使用されるユーザＶＭ要求情報を含む。ユーザＶＭ要求情報は、いくつかの要求されたＶＭを含む。ユーザＶＭ要求情報はまた、要求されたＶＭの中での通信のための通信要件を含むことができる。ユーザＶＭ要求情報はまた、１つまたは複数のＶＭ割り当て制約（たとえば、ＶＭ配置制約、ＶＭ通信制約、ＶＭ復元力制約、ＶＭタイプ制約などのうちの１つまたは複数）を含むことができる。ＶＭ割り当て制約は、ラック１１２ごとに割り当てられるべきＶＭの最大数、ラック１１２ごとに割り当てられるべきＶＭの最小数、（たとえば、ラック間トラフィックを削減するために）データセンタ１１１ごとに使用されるべきラック１１２の最大数、（たとえば、復元力のために）データセンタ１１１ごとに使用されるべきラック１１２の最小数、（たとえば、復元力のために）データセンタ１１１ごとに割り当てられるべきＶＭの最大数、（たとえば、データセンタ間トラフィックを削減するために）データセンタ１１１ごとに割り当てられるべきＶＭの最小数、（たとえば、データセンタ間トラフィックを削減するために）使用されるべきデータセンタ１１１の最大数、（たとえば、復元力のために）使用されるべきデータセンタ１１１の最小数、割り当てられるべきＶＭのタイプに基づいて使用されるべきブレードサーバ１１４のタイプなど、ならびにそれらのさまざまな組合せのうちの１つまたは複数を含むことができる。ユーザＶＭ要求情報は、クラウド環境１１０内での要求されたＶＭの割り当てを決定する際の使用に好適な任意の他の情報を含むことができる。
【００３４】
ＣＡＳ１４０は、クラウド環境１１０の物理リソースへの要求されたＶＭの割り当てを決定するのに、ＣＡＳ１４０によって使用される管理情報を受信するように構成されている。たとえば、ＣＡＳ１４０は、ＣＭＳ１２０からのクラウド管理情報、ＮＭＳ１３０からのネットワーク管理情報などを含む、管理情報を受信することができる。
【００３５】
ＣＡＳ１４０は、ユーザＶＭ要求で受信されたユーザＶＭ要求情報、システム１００の一部に関連付けられた管理情報など、ならびにそれらのさまざまな組合せを使用して、クラウド環境１１０の物理リソースへの要求されたＶＭの割り当てを決定することができる。
【００３６】
ＣＡＳ１４０は、リソース使用量を削減し（たとえば、データセンタ１１１内のラック間通信を削減する、およびデータセンタ１１１同士の間のデータセンタ間通信を削減する）、ＶＭがクラウド環境１１０でプロビジョニングされるとそのＶＭを使用することになるユーザアプリケーションに、改善されたパフォーマンスを提供するようなやり方で、クラウド環境１１０の物理リソースへの要求されたＶＭの割り当てを決定するように構成されていてよい。データセンタ１１１内のラック間通信の削減は、ＶＭが割り当てられるデータセンタ１１１のラック１１２の数を削減し、可能な限り比較的互いに近接したラック１１２にＶＭを割り当てることなどによって、実現されてよい。データセンタ１１１同士の間のデータセンタ間通信の削減は、ＶＭが割り当てられるデータセンタ１１１の数を削減することによって、データセンタ１１１同士の間の通信能力の知識に基づいてＶＭをデータセンタ１１１に割り当てることによって、データセンタ１１１と、ＶＭがクラウド環境１１０でプロビジョニングされるとそのＶＭを使用することになると予想されるクライアントのクライアント場所との間の、トラフィックの知識に基づいてＶＭをデータセンタ１１１に割り当てることなどによって、実現されてよい。
【００３７】
ＣＡＳ１４０は、１つまたは複数のユーザＶＭ要求の他の特性（たとえば、順応性、障害許容力、など）に基づいて、クラウド環境１１０の物理リソースへの要求されたＶＭの割り当てを決定できるように構成されていてよい。たとえば、ＣＡＳ１４０は、（たとえば、ユーザが今後、１つまたは複数の追加のＶＭを加える必要がある、または加えたいと望むことがある場合の）拡張のための余地を確保するようなやり方で、ＶＭを割り当てるように構成されていてよい。たとえば、ＣＡＳ１４０は、結果としてのＶＭの割り当てが、クラウド環境１１０および／またはＣＮ１５０における障害から迅速に回復できるように、障害シナリオを考慮しながらＶＭを割り当てるように構成されていてよい。
【００３８】
ＣＡＳ１４０がクラウド環境１１０の物理リソースへの要求されたＶＭの割り当てを決定するやり方は、図２−図６を参照することによってよりよく理解され得る。
【００３９】
ＣＡＳ１４０は、ＶＭ割り当て情報の観点から、クラウド環境１１０の物理リソースへの要求されたＶＭの割り当てを指定することができる。ＶＭ割り当て情報は、要求されたＶＭが配置されることになるデータセンタの識別情報、要求されたＶＭが配置されることになるデータセンタ内の機器の（たとえば、各ＶＭが配置されることになる、ラック１１２、ブレードサーバ１１４、およびＣＰＵ１１５（およびオプションでコア）の観点からの）識別情報などを含む。ＶＭ割り当て情報はまた、要求されたＶＭ同士の間に接続性をプロビジョニングする際の使用のために構成されたネットワーク構成情報を含むことができる。
【００４０】
ＣＡＳ１４０は、関連したデータベース１４１において、さまざまなタイプの情報を維持することができる。たとえば、ＣＡＳ１４０に関連付けられたデータベース１４１は、ＣＡＳ１４０によって受信された情報（たとえば、ユーザＶＭ要求情報、管理情報、など）、ＣＡＳ１４０によって決定されたＶＭ割り当て情報など、ならびにそれらのさまざまな組合せを記憶することができる。
【００４１】
ＣＡＳ１４０は、ＶＭ割り当て情報に基づいて、クラウド環境１１０内での要求されたＶＭのプロビジョニングに関与するように構成されている。一実施形態において、ＣＡＳ１４０は、ＶＭ割り当て情報に基づいて（たとえば、ＶＭ割り当て情報に基づいた関連したＶＭプロビジョニング要求の生成、およびクラウド環境１１０へのＶＭプロビジョニング要求の伝搬を介して）、クラウド環境１１０内での要求されたＶＭのプロビジョニングを実施するように構成されている。一実施形態において、ＣＡＳ１４０は、ＶＭ割り当て情報に基づいた、クラウド環境１１０内での要求されたＶＭのプロビジョニングの際の１つまたは複数の管理システムによる使用のために、たとえば、ユーザＶＭ要求についてのＶＭ割り当て情報を、１つまたは複数の管理システム（たとえば、ＣＭＳ１２０、ＮＭＳ１３０などのうちの１つまたは複数）に提供することによって、ＶＭ割り当て情報に基づいた、クラウド環境１１０内で要求されたＶＭのプロビジョニングを開始するように構成されている。
【００４２】
ＣＡＳ１４０は、仮想リソース割り当て能力のサポートにおいて、さまざまな他の機能を実施するように構成されていてよい。
【００４３】
ＣＮ１５０は、データセンタ１１１同士の間の通信をサポートするのに好適な任意のタイプの通信ネットワークであってよい。たとえば、ＣＮ１５０は、公共データネットワーク（たとえば、インターネット）、１つまたは複数の私設データネットワークなど、ならびにそれらのさまざまな組合せのうちの１つまたは複数を使用して提供されてよい。
【００４４】
図２は、ＶＭについてのユーザ要求に応答して、クラウド環境のデータセンタ内でＶＭをプロビジョニングするための方法の一実施形態を示す。方法２００のステップは、順番に実施されるものとして示され、説明されているが、ステップは、同時に、および／または提示されているものとは異なる順序で実施されてもよいことに留意されたい。
【００４５】
ステップ２１０で、方法２００が開始される。方法２００は、任意の好適な条件またはトリガに応答して、開始されてよい。
【００４６】
ステップ２２０で、クラウド環境内でのＶＭのプロビジョニングを要求する、ユーザＶＭ要求が受信される。ユーザＶＭ要求は、ユーザＶＭ要求情報を含む。ユーザＶＭ要求情報は、ユーザによって要求された、いくつかのＶＭを含む。ユーザＶＭ要求情報はまた、要求されたＶＭの中で通信するための通信要件を含むことができる。ユーザＶＭ要求情報はまた、１つまたは複数のＶＭ割り当て制約（たとえば、ＶＭ配置制約、ＶＭ通信制約、ＶＭ復元力制約などのうちの１つまたは複数）を含むことができる。ユーザＶＭ要求情報は、データセンタ内で要求されたＶＭの配置を決定する際の使用に好適な任意の他の情報を含むことができる。
【００４７】
ステップ２３０で、データセンタ内での要求されたＶＭの割り当てが決定される。データセンタ内での要求されたＶＭの割り当ては、ユーザＶＭ要求情報、ネットワーク管理情報、データセンタ管理情報など、ならびにそれらのさまざまな組合せを使用して決定される。データセンタ内での要求されたＶＭの割り当ては、ＶＭ割り当て情報の観点から指定されてよい。ＶＭ割り当て情報は、要求されたＶＭが配置されることになるデータセンタの識別情報、要求されたＶＭが配置されることになるデータセンタ内の機器の（たとえば、各ＶＭが配置されることになる、ラック、ブレードサーバ、およびＣＰＵ（およびオプションでコア）の観点からの）識別情報などを含む。ＶＭ割り当て情報はまた、要求されたＶＭ同士の間に接続性をプロビジョニングする際の使用のために構成されたネットワーク構成情報を含むことができる。一実施形態において、データセンタ内での要求されたＶＭの割り当ては、図３に関して示され、説明されるように決定される。
【００４８】
ステップ２４０で、ＶＭ割り当て情報を使用して、要求されたＶＭがクラウド環境内でプロビジョニングされる。クラウド環境内での要求されたＶＭのプロビジョニングは、任意の好適なやり方で（たとえば、要求されたＶＭが割り当てられることになるデータセンタに送られたプロビジョニングメッセージを使用して）実施されてよい。
【００４９】
ステップ２５０で、方法２００が終了する。
【００５０】
図３は、クラウド環境のデータセンタ内でＶＭをプロビジョニングするのに使用される、データセンタ内でのＶＭの割り当てを決定するための方法の一実施形態を示す。方法３００のステップは、順番に実施されるものとして示され、説明されているが、ステップは、同時に、および／または提示されているものとは異なる順序で実施されてもよいことに留意されたい。
【００５１】
ステップ３１０で、方法３００が開始される。
【００５２】
ステップ３２０で、要求されたＶＭのためのデータセンタの集合が決定される。
【００５３】
データセンタの集合は、要求されたＶＭが割り当てられることになる１つまたは複数のデータセンタを含む。データセンタの集合は、クラウド環境の利用可能なデータセンタのうちの１つまたは複数を含む。単一のデータセンタは要求されたＶＭのすべてをホストするのに十分な容量を有していないことがあること、および、さらには、単一のデータセンタに要求されたＶＭのすべてをホストするのに十分な容量がある場合であっても、復元力を改善するために、ユーザが複数のデータセンタにわたって要求されたＶＭを分散させるよう望むことがあることに留意されたい。
【００５４】
データセンタの集合は、ユーザＶＭ要求情報を使用して決定されてよい。データセンタの集合は、ネットワーク管理情報、データセンタ管理情報など、ならびにそれらのさまざまな組合せのうちの１つまたは複数を使用して決定されてよい。データセンタの集合は、データセンタの集合を決定する際の使用に好適な任意の他の情報を使用して決定されてよい。
【００５５】
一実施形態において、データセンタの集合は、（１）データセンタの集合の中のデータセンタの数を最小限にする、および（２）要求されたＶＭの配置に関連付けられたデータセンタ間トラフィックを削減する（およびしたがって、消費されるネットワーク帯域幅を最小限にする）ことにつながるやり方で、決定される。
【００５６】
一実施形態において、データセンタの集合は、（１）任意の２つのデータセンタ間の最大距離（たとえば、ホップカウント）を最小限にし、（２）１つまたは複数の制約（たとえば、所望のＶＭの数の利用可能性、各データセンタに配置されるＶＭの最小数および／または最大数、など）に従う、利用可能なデータセンタの部分集合を選択することによって決定される。これらの条件を満たすデータセンタの部分集合の選択は、以下で説明される、部分グラフ選択問題（本明細書では、データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲとして示される）と見なされてよいことに留意されたい。
【００５７】
利用可能なデータセンタの集合が、グラフ（Ｇ）として表されるとする。グラフＧ＝（Ｖ，Ｅ）は、頂点（Ｖ）およびエッジ（Ｅ）からなる。頂点（Ｖ）は、データセンタに対応する。頂点（Ｖ）は、頂点（Ｖ）に関連付けられた頂点重み（ｗ）を有し、そこで頂点（Ｖ）の重み（ｗ）がデータセンタにおける利用可能なＶＭの数に対応する。グラフは完全グラフであり、ここで、エッジ（Ｅ）は、（たとえば、インターネットおよび／または任意の他の関連したパケットネットワークを介して）データセンタを接続する通信パスに対応する。エッジ（Ｅ）は、エッジ（Ｅ）に関連付けられたエッジ重み、または長さ（ｌ）を有し、そこで２つのデータセンタ間のエッジ（Ｅ）の長さ（ｌ）がデータセンタ同士の間の距離（たとえば、ホップ数）に対応する。
【００５８】
一実施形態において、初期のグラフＧは、ユーザＶＭ要求において指定されてよい１つまたは複数のＶＭ割り当て制約に基づいて、修正されてよい。ユーザＶＭ要求が、データセンタ内に配置され得るＶＭの最大数についての制約を含む場合、頂点（Ｖ）の重みは、その制約を超えることはできない（すなわち、制約よりも大きい重みを有する頂点は、グラフから取り除かれる）。ユーザＶＭ要求が、データセンタ内に配置され得るＶＭの最小数についての制約を含む場合、頂点（Ｖ）の重みは、その制約に満たないことはできない（すなわち、制約よりも小さい重みを有する頂点は、グラフから取り除かれる）。
【００５９】
ｓが、ユーザＶＭ要求において要求されたＶＭの数を表すとする。一実施形態において、データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲは、その重みの総和が少なくともｓであって、最小直径を有する、Ｇの部分グラフ（すなわち、頂点間の任意の最短距離の最大長）を発見することに対応する。オリジナルグラフＧは完全グラフなので、選択された頂点によって誘導された部分グラフもまた、完全であることに留意されたい。したがって、一実施形態において、データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲは、最も長いエッジの長さが最小である、そのような部分グラフを発見することに対応する。
【００６０】
データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲは、ＮＰ困難であり、任意のε＞０の場合、２−ε範囲内で近似値を求めることはできないことに留意されたい。データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲは、問題が最大サイズのクリークを発見することである、最大クリーク問題からは還元され得ないことにさらに留意されたい。還元は、以下の通りである。最大クリーク問題のインスタンスＧ＝（Ｖ，Ｅ）が与えられるとすると、最小直径部分グラフ問題のインスタンスが作成される。新しい完全グラフＧ’＝（Ｖ’，Ｅ’，ｗ，ｌ）が作成される。Ｇ’の頂点は、Ｇの頂点と同じであり、１（１）の重みを有する。Ｇにおいて、２つの頂点ｕとｖとの間にエッジがある場合、Ｇ’の対応する頂点間のエッジの長さは１（１）である。そうでない場合、頂点間のエッジの長さは２（２）である。このグラフにおけるエッジは、三角不等式を満たす。Ｇにおける対応する部分グラフがクリークのとき、かつそのときに限り、Ｇ’の部分グラフは、１（１）の直径を有する。これは、Ｇがサイズｋのクリークを有する場合、Ｇ’の対応する頂点は、重みｋおよび直径１（１）の部分グラフを形成するように取られてよいからである。同様に、Ｇ’が重みｋおよび直径１の部分グラフを有する場合、Ｇの対応する頂点は、サイズｋのクリークを形成する。Ｇにおける対応する部分グラフがクリークのとき、かつそのときに限り、Ｇ’の部分グラフは、１（１）の直径を有する。したがって、最大クリーク問題に対する解は、サイズｓおよび直径１（１）の部分グラフが存在する最大値ｓ∈｛ｎ，ｎ−１，…１｝を発見することによって見出されてよい。
【００６１】
データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲは、Ｐ＝ＮＰでない限り、任意のε＞０の場合、因子２−ε範囲内で近似値を求めることはできないことに再び留意されたい。データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲのための２−ε近似処理が存在する場合、最大クリーク問題は、以下のように解決されてよい。サイズｋのクリークを発見するために、上の還元を使用して、重みｋを有するＭＩＮＤＩＡＭＥＴＥＲ問題を作成する。サイズｋのクリークがある場合、直径１（１）のデータセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲのための部分グラフが存在する。そのようなクリークがない場合、データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲの直径は、少なくとも２（２）である。したがって、データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲのための２−ε処理が、その直径が２（２）未満である部分グラフを返すと、オリジナルグラフＧに、サイズｋのクリークがある。
【００６２】
一実施形態において、近似処理が、最小直径部分グラフ問題（すなわち、データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲ）を解決するために提供される。一実施形態において、処理によって出力される部分グラフの直径は、最適な部分グラフの直径の多くとも２倍である。近似処理では、三角不等式が、グラフにおけるエッジ重みについて成り立つと想定されている。エッジの長さは、対応するデータセンタ同士の間のパス長に対応するので、この問題設定において三角不等式が有効であることに留意されたい。３つのデータセンタ間で三角不等式違反がある場合、より短いエッジで形成されるパスを取るのにより長いエッジを強制することによって、三角不等式への適合がなおも維持され得ることにさらに留意されたい。
【００６３】
一実施形態において、近似処理は、２つの処理として実装される最小直径部分グラフ問題を解決するために提供され、２つの処理は、本明細書では、以下で説明される、ＦｉｎｄＭｉｎＳｔａｒ（Ｇ，ｖ，ｓ）処理（図４Ａで示され、説明されている）、およびＭｉｎＤｉａｍｅｔｅｒＧｒａｐｈ（Ｇ，ｓ）処理（図４Ｂで示され、説明されている）として示される。これらの処理は、別々の処理として主に示され、説明されているが、説明される機能を提供するために実行され得る、より少ない、またはより多い処理として実装されてもよいことに留意されたい。これらの処理は、処理の特定の実装（たとえば、特定の変数、処理のステップの特定の配列、など）に関して示され、説明されているが、説明される機能を提供するのに好適な任意の他のやり方で実装されてもよいことにさらに留意されたい。
【００６４】
本明細書で触れたように、図４ＡのＦｉｎｄＭｉｎＳｔａｒ（Ｇ，ｖ，ｓ）処理４１０、および図４ＢのＭｉｎＤｉａｍｅｔｅｒＧｒａｐｈ（Ｇ，ｓ）処理４２０は、ＶＭが割り当てられることになるデータセンタの集合を決定するために構成されている。
【００６５】
図４Ａに示されるように、ＦｉｎｄＭｉｎＳｔａｒ（Ｇ，ｖ，ｓ）処理４１０は、頂点ｖを含む、重み少なくともｓの部分グラフを発見するように構成されている。頂点ｖを中心としたスター型トポロジは、スター型トポロジの重みが少なくともｓになるまで、ｖまでの長さの昇順に、ノードを加えることによって発見される。最終的な部分グラフは、スター型におけるノードにより誘導されたエッジを加えることによって形成される。ＦｉｎｄＭｉｎＳｔａｒ（Ｇ，ｖ，ｓ）処理４１０はまた、ノードが加えられたときの直径を維持することによって、結果として生じる部分グラフの直径を（ノードが加えられたとき、部分グラフの直径は、そのノードによって誘導されたエッジの長さが現在の直径よりも大きい場合にのみ変化することができる、という制約に従って）計算する。
【００６６】
図４Ｂに示されるように、ＭｉｎＤｉａｍｅｔｅｒＧｒａｐｈ（Ｇ，ｓ）処理４２０は、頂点のそれぞれについてＦｉｎｄＭｉｎＳｔａｒ（Ｇ，ｖ，ｓ）処理４１０を呼び出すことによって、重み少なくともｓの部分グラフを発見するように構成されている。ＭｉｎＤｉａｍｅｔｅｒＧｒａｐｈ（Ｇ，ｓ）処理４２０は次いで、最も小さい直径を有する部分グラフを選択する。
【００６７】
ＦｉｎｄＭｉｎＳｔａｒ（Ｇ，ｖ，ｓ）処理４１０は、ｖに付随する任意のエッジの長さが最小である、重み少なくともｓの部分グラフを発見する。ＦｉｎｄＭｉｎＳｔａｒ（Ｇ，ｖ，ｓ）処理４１０は最初に、頂点ｖを部分グラフに加える。ＦｉｎｄＭｉｎＳｔａｒ（Ｇ，ｖ，ｓ）処理４１０は次いで、部分グラフにおける頂点の重みの総和がｓになるまで、エッジ重みの昇順に、ｖに隣接した頂点を加える。したがって、ＦｉｎｄＭｉｎＳｔａｒ（Ｇ，ｖ，ｓ）処理４１０は、ｖに付随するエッジについて最も小さいエッジ重みを有する部分グラフを発見する。
【００６８】
ＭｉｎＤｉａｍｅｔｅｒＧｒａｐｈ（Ｇ，ｓ）処理４２０は、その直径が最適値の多くとも２倍である、重み少なくともｓの部分グラフを発見する。ＭｉｎＤｉａｍｅｔｅｒＧｒａｐｈ（Ｇ，ｓ）処理４２０は、Ｇの頂点のそれぞれについてＦｉｎｄＭｉｎＳｔａｒ（Ｇ，ｖ，ｓ）処理４１０を呼び出し、最小直径を有する１つを選択する。ｖ’が、ＦｉｎｄＭｉｎＳｔａｒ（Ｇ，ｖ，ｓ）処理４１０によって返されたグラフＧ’の直径が最小であったノードであるとし、ｌ’が、部分グラフＧ’においてｖ’に付随する最も長いエッジの長さであるとする。エッジ長さは三角不等式に従い、Ｇ’は完全グラフであるので、Ｇ’における任意のエッジの長さは多くとも２ｌ’であり、したがって、Ｇ’の直径は、多くとも２ｌ’である。
【００６９】
データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲに関して、データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲを解決するための近似処理は、２−近似処理であることに留意されたい。Ｇｏｐｔが、データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲに対する最適解であるとする。ｌ”が、Ｇｏｐｔの最も長いエッジであるとする。ｕ”およびｖ”が、ｌ”の端点であるとする。Ｇｏｐｔのエッジは、三角不等式を満たすので、ｕ”とｖ”との間のＧｏｐｔにおける最短距離は、ｌ”である。したがって、Ｇｏｐｔの直径は、少なくともｌ”である。次に、ＭｉｎＤｉａｍｅｔｅｒＧｒａｐｈ（Ｇ，ｓ）処理４２０を実行しながら、ＦｉｎｄＭｉｎＳｔａｒ（Ｇ，ｖ，ｓ）処理４１０によって返されたグラフＧ”について検討する。上で触れたように、Ｇ”の上でｖ”に付随するエッジの長さは、多くともｌ”である。Ｇ”の直径は、多くとも２ｌ”であるので、ＭｉｎＤｉａｍｅｔｅｒＧｒａｐｈ処理４２０によって返された部分グラフ（すなわち、Ｇ’）の直径は、多くとも２ｌ”である。したがって、データセンタ選択問題ＭＩＮＤＩＡＭＥＴＥＲを解決するための近似処理は、２−近似処理である。
【００７０】
次に図３に戻ると、要求されたＶＭのためのデータセンタの集合の決定が、他のやり方で（たとえば、他の情報を使用して、他の条件を満たすためのやり方で、他の処理を使用してなど、ならびにそれらのさまざまな組合せで）実施されてもよいことに留意されたい。
【００７１】
ステップ３３０で、データセンタの集合の中のデータセンタへの要求されたＶＭの割り当てが決定される。
【００７２】
データセンタの集合の中のデータセンタへの要求されたＶＭの割り当ては、データセンタの集合のデータセンタごとに、データセンタに割り当てられることになる要求されたＶＭの数を指定する。データセンタの集合の中のデータセンタへの要求されたＶＭの割り当ては、必ずしも、ＶＭが割り当てられることになるデータセンタの機器（これはステップ３４０で決定されてよいので）、またはＶＭのうちのどれがデータセンタのうちのどれに割り当てられることになるか（これはステップ３５０で決定されてよいので）を、指定するものではないことに留意されたい。
【００７３】
要求されたＶＭは、ユーザＶＭ要求情報、ネットワーク管理情報、データセンタ管理情報など、ならびにそれらのさまざまな組合せのうちの１つまたは複数を使用して、データセンタの集合の中のデータセンタに割り当てられてよい。一実施形態において、要求されたＶＭは、データセンタ間トラフィックを最小限にすることにつながるやり方で、データセンタの集合の中のデータセンタに割り当てられる。一実施形態において、要求されたＶＭは、ユーザＶＭ要求において指定された１つまたは複数のＶＭ割り当て制約に従って、データセンタの集合の中のデータセンタに割り当てられる。たとえば、複数の異なるタイプのＶＭを複数の異なるデータセンタに割り当てることに関連付けられたＶＭタイプ制約を、ユーザＶＭ要求情報が含む一実施形態では、要求されたＶＭが、ＶＭタイプ制約に基づいて、データセンタの集合の中のデータセンタに割り当てられる。
【００７４】
一実施形態において、要求されたＶＭは、ＶＭをデータセンタに割り当てるために構成されたＶＭ割り当て処理を使用して、データセンタの集合の中のデータセンタに割り当てられる。概して、ＶＭ割り当て処理の目的は、グラフの断片同士の間にいくつかの関係が存在するように、グラフを均等なサイズの断片に分ける（それにより、要求されたＶＭをサポートするのに必要とされるネットワーク通信リソースを最小限にする）ことである。しかしながら、一般にグラフ二分割問題と呼ばれる、グラフを２つの均等な断片に分ける最も単純なケースでさえ、ＮＰ困難である。加えて、関連した問題は、その目的がグラフをＫ個の断片に分けることであるＫ−カット問題であり、ここで、各断片のサイズはやはり、入力として指定される。
【００７５】
ＶＭ割り当て処理において、ユーザＶＭ要求は、分割されることが必要なグラフとして見なされてよい。グラフのノードは、ＶＭを表し、グラフのリンクは、リンクによって接続された対のＶＭの間で必要とされる相対帯域幅を表す。グラフの各パーティションは、同じデータセンタに割り当てられることが必要なＶＭの集合を表す。各パーティションのサイズは、ＶＭをホストするためにデータセンタにおいて利用可能なリソースの量によって上に有界である必要がある。従来のグラフ分割問題とは異なり、この問題は、各パーティションにおける厳密なノードの数を指定しなくてもよく、代わりに、各パーティションにおける最大ノードのみを指定する。これは、任意の点において、クラウド環境においてＶＭをホストするために利用可能なリソースが、ユーザによって要求されたＶＭの数よりも多い場合があるからである。その結果、ＶＭ割り当て処理は、ＶＭをホストするために利用可能な最大リソースを有するデータセンタ内でＶＭを割り当てることによって、（データセンタ同士の間の）通信を最適化することができる。データセンタへのＶＭの割り当てでは、データセンタ間通信コストは、データセンタ同士の間の通信ルーティングに依存する。したがって、適用する通信コストを最小限にするために、データセンタパーティション同士の間の通信距離が考慮に入れられる。
【００７６】
ＶＭ割り当て処理に関して、問題は以下のように導き出されてよい。エッジ重みｗが割り当てられたグラフＧ＝（Ｖ，Ｅ）：Ｅ→Ｎ、およびパーティションｉとｊとの間の距離をｄ（ｉ，ｊ）としてパーティション容量ｋ１，ｋ２，・・・の集合が与えられるとする。Ｖを、｜Ｃｉ｜≦Ｋｉおよび
【００７７】
【数１】
2014522036.tif 000003
であるような、互いに素な集合Ｃ１，Ｃ２，・・・，Ｃｍに分割する。
【００７８】
ＶＭ割り当て処理に関して、個々のユーザ要求がインクリメント方式で別々に扱われてもよく、または、すべての複数の要求がまとめて結合されて、異なるユーザ要求のノード同士の間にいかなるエッジも含まない大きく分割されたグラフを形成してもよいことに留意されたい。
【００７９】
ＶＭ割り当て処理に関して、グラフ分割問題はＮＰ困難であり、良好な（たとえば、一定の）近似保証を有する処理は存在しないことに留意されたい。
【００８０】
一実施形態において、ＶＭ割り当て処理は、貪欲法に基づく発見的処理として実装される。
【００８１】
一実施形態において、ＶＭ割り当て処理は、一度に１つのデータセンタを選択する。データセンタは、任意の好適な順序で選択されてよく（たとえば、各選択は、ユーザＶＭ要求において指定された１つまたは複数のＶＭ割り当て制約など、ならびにそのさまざまな組合せに基づいて、ＶＭをホストするために利用可能なリソースの最大量を有するデータセンタが選択されるように、実施される）、選択されたデータセンタに、可能な限り多くのＶＭを割り当てる。ＶＭ割り当て処理は、パラメータの最大値（たとえば、着信／発信帯域幅、近傍の数、など）を有するＶＭを選択し、選択されたＶＭを、選択されたデータセンタに割り当てる。選択されたＶＭは、選択されたデータセンタに割り当てられるＶＭの集合である集合Ｃに加えられる。ＶＭ割り当て処理は次いで、Ｃの近傍のすべてを考慮し、Ｃへの／Ｃからの最大トラフィックを有するＶＭを選択し、選択されたＶＭを集合Ｃに加える。この処理は、選択されたデータセンタについて条件が満たされる（たとえば、選択されたデータセンタの利用可能なリソースのすべてが使い尽くされる、選択されたデータセンタについてデータセンタごとのＶＭの最大量の制約が満たされる、など）まで、繰り返されてよい。ＶＭ割り当て処理は次いで、次のデータセンタを選択し、次の選択されたデータセンタ、およびデータセンタにまだ割り当てられていない残りのＶＭ（すなわち、Ｖ−Ｃ）のグラフについて、処理を繰り返す。
【００８２】
一実施形態において、ＶＭ割り当て処理は、特定のノードを交換することによって修正される。ＶＭ割り当て処理は、複数の異なるパーティションに存在する対のノードを考慮する。ＶＭ処理は、考慮されたノードの入れ替えが解を改善するか否か（たとえば、より少ないデータセンタ間帯域幅を使用するか）を判定することができる。ＶＭ処理は、パーティション同士の間でノードを（たとえば、ノードの現在のパーティションから利用可能な容量を有する複数の異なるパーティションへ）移動させることが、解を改善するか否かを判定することができる。ＶＭ割り当て処理は、考慮された移動のうちの１つまたは複数を選択し、選択された移動をコミットする。この処理は、繰り返されてよい（たとえば、閾値の移動の数がコミットされるまで、すべての移動が考慮されてＶＭ割り当てにおいてそれ以上の改善がなくなるまで、など）ことに留意されたい。
【００８３】
ステップ３４０で、データセンタの集合の中のデータセンタごとに、データセンタに割り当てられることになる要求されたＶＭをホストするために使用されることになる、データセンタの物理リソースが選択される。
【００８４】
データセンタ内の物理リソースの選択は、データセンタに割り当てられるＶＭをホストするために使用されることになるデータセンタのラックの選択を含むことができる。データセンタ内の物理リソースの選択は、選択されたラック上のブレードサーバの選択をさらに含むことができる。データセンタ内の物理リソースの選択は、選択されたラックの選択されたブレードサーバ上のＣＰＵの選択をさらに含むことができる。データセンタ内の物理リソースの選択は、選択されたラックの選択されたブレードサーバの選択されたＣＰＵのコアの選択をさらに含むことができる。この意味において、データセンタ内の物理リソースの選択に使用される処理は、本明細書ではより広く、機器選択処理、マシン選択処理、および／または物理リソース選択処理と呼ばれてもよい。物理リソースの選択は、必ずしも、データセンタに割り当てられることになるＶＭの、データセンタの選択された物理リソースへのマッピング（これはステップ３５０で決定されてよいので）を指定するものではないことに留意されたい。
【００８５】
データセンタの物理リソースの選択は、データセンタ内のＶＭ同士の間のラック間トラフィックを最小限にすることにつながるやり方で実施されてよい。これは、データセンタに割り当てられるＶＭ同士の間の長い通信パスを防ぐことにつながることになり、それにより、データセンタ内のＶＭ同士の間の通信における大きな待ち時間を防いで、データセンタ内のリソース（たとえば、通信リソース）の使用量を削減する。
【００８６】
これにより、互いに比較的近接して設置されていないラック同士の間の任意の通信が、さまざまな数／レベルのアグリゲーションスイッチを横断しなければならないことがある、より大規模なデータセンタ（たとえば、数百のラック、数千のラック、またはそれ以上ものラックを有するデータセンタ）において、通信遅延の著しい削減を実現することができる。
【００８７】
データセンタの物理リソースの選択は、順応性を提供することにつながるやり方で実施されてよい。
【００８８】
データセンタの物理リソースの選択は、データセンタの利用、およびＶＭが要求されるユーザアプリケーションのパフォーマンスを改善できることに留意されたい。
【００８９】
一実施形態において、選択されたデータセンタのラックの選択は、ラック選択処理（たとえば、要求されたＶＭのためのラックが選択されるマシン選択処理の実装）を使用して実施される。
【００９０】
一実施形態において、ラック選択処理は、データセンタの選択のために使用されるデータセンタ選択処理の修正版として実装される。この実施形態において、ラック選択処理は、ラック同士の間の最大距離を最小限にするように構成された２−近似処理である。この実施形態において、グラフの頂点がラックを表し、ラックごとに、ラックの関連付けられた重みが、データセンタに割り当てられたＶＭをサポートするためのラックにおいて利用可能なリソースの量を表す。
【００９１】
データセンタのトポロジが階層構造ネットワークである一実施形態において、ラック選択処理は、ラック選択問題に対する最適な解を決定することができる。トポロジは、ツリー型トポロジと考えられてよく、ここでは、ツリーの根ノードが、最も高い層の１つまたは複数のスイッチ（たとえば、データセンタへの／データセンタからの接続性を提供するルータ）を表し、根ノードの子ノードが、スイッチのネットワーク層（たとえば、上位レベルのアグリゲートスイッチ）を表すなどして、ラックを表す葉ノードまで下りてくる。このツリーでは、葉ノードのすべてが同じレベルにあることに留意されたい。ツリーは、データセンタに割り当てられたＶＭをサポートするための利用可能なラックのリソースの量をラックごとに示すラベルを含んで、拡大する。
【００９２】
一実施形態において、ラックのブレードサーバの選択は、ブレードサーバ選択処理（たとえば、要求されたＶＭのためのラックおよびブレードサーバが選択される、マシン選択処理の実装）を使用して実施される。一実施形態において、ブレードサーバ選択処理は、ラック選択処理の修正版として実装され、ここでは、ツリーの葉ノードがブレードサーバのレベルを表し、葉ノードの親ノードがラックを表す。
【００９３】
一実施形態において、ラックのブレードサーバのＣＰＵの選択は、ＣＰＵ選択処理（たとえば、要求されたＶＭのためのラック、ブレードサーバ、およびＣＰＵが選択される、マシン選択処理の実装を使用する）を使用して実施される。一実施形態において、ＣＰＵ選択処理は、ラック選択処理の修正版として実装され、ここでは、ツリーの葉ノードがＣＰＵのレベルを表し、ＣＰＵノードの親ノードがブレードサーバを表し、ブレードサーバノードの親ノードがラックを表す。
【００９４】
上で説明されたように、マシン選択処理は、データセンタに割り当てられるＶＭが割り当てられることになる、データセンタ内でのマシンを選択するための、データセンタについて実行されてよい。
【００９５】
一実施形態において、マシン選択処理は、ＶＭが割り当てられた所与のデータセンタについて、データセンタに割り当てられた任意の２つのＶＭの間の最大通信距離を最小限にするように構成されている。これは、葉のラベルの総和が少なくとも要求されたＶＭのターゲット数である、最小高さの根付き部分ツリーを発見することに変換されてよい。データセンタ選択処理でのように、マシン選択処理は、１つまたは複数のＶＭ割り当て制約（たとえば、ラックごとに割り当てられ得るＶＭの最大数、ラックごとに割り当てられ得るＶＭの最小数、など）を考慮に入れることができる。これらのタイプのＶＭ割り当て制約は、ＶＭ割り当て制約に従ってラックを表すノードの重みを変化させることによって説明されてよい。
【００９６】
一実施形態において、（図５で示され、説明されている）マシン選択処理は、ＦｉｎｄＭｉｎＨｅｉｇｈｔＴｒｅｅ（Ｔ，ｒ，ｓ）処理として実装される。
【００９７】
図５に示されるように、ＦｉｎｄＭｉｎＨｅｉｇｈｔＴｒｅｅ（Ｔ，ｒ，ｓ）処理５００は、所与のデータセンタについて、そのデータセンタに割り当てられたＶＭをホストするために使用されることになる、データセンタの物理リソースを選択するように構成されている。ｓが、データセンタ内で割り当てられることになるＶＭの数であるとする。Ｔが、データセンタリソース（たとえば、コンピューティングリソース、ネットワークリソース、など）のツリー表現であるとする。以下の２つの変数が、Ｔにおける各ノードに関連付けられる：（１）ノードｖに根付いた、ＶＭをサポートするための利用可能なデータセンタリソースの量を表す重み（ｖ）、および（２）ノードの高さを表す高さ（ｖ）。葉ノードのみの重み変数が、初期化される。ＦｉｎｄＭｉｎＨｅｉｇｈｔＴｒｅｅ（Ｔ，ｒ，ｓ）処理５００は、その葉ノードが、少なくともｓの累積重み、およびその最小高さを有する、ｒに根付いた部分ツリーを発見する。ＦｉｎｄＭｉｎＨｅｉｇｈｔＴｒｅｅ（Ｔ，ｒ，ｓ）処理５００は、ツリーの間順走査を実施し、各ノードの高さおよび重み、ならびに重み少なくともｓを有する最小高さ部分ツリーの根を維持する。
【００９８】
次に図３に戻ると、データセンタの物理リソースの選択が、他のやり方で（たとえば、他の情報を使用して、他の条件を満たすためのやり方で、他の処理を使用してなど、ならびにそれらのさまざまな組合せで）実施されてもよいことに留意されたい。
【００９９】
ステップ３５０で、要求されたＶＭごとに、要求されたＶＭが割り当てられたデータセンタの物理リソースへの、要求されたＶＭの割り当てが決定される。
【０１００】
データセンタの物理リソースへのＶＭの割り当ては、ＶＭがホストされることになるラック、ブレードサーバ、ならびにＣＰＵ（およびオプションで、ＣＰＵのコア）へのＶＭの割り当てを含む。
【０１０１】
要求されたＶＭは、ユーザＶＭ要求情報、データセンタ管理情報など、ならびにそれらのさまざまな組合せのうちの１つまたは複数を使用して、ＶＭがホストされることになるデータセンタの物理リソースに割り当てられてよい。一実施形態において、ＶＭがホストされることになるデータセンタの物理リソースへのＶＭの割り当ては、データセンタ内でのラック間トラフィックを最小限にすることにつながるやり方で実施されてよい。一実施形態において、ＶＭがホストされることになるデータセンタの物理リソースへのＶＭの割り当ては、要求されたＶＭは、ユーザＶＭ要求において指定された１つまたは複数のＶＭ割り当て制約に従って、実施されてよい。たとえば、複数の異なるタイプのＶＭを複数の異なるデータセンタに割り当てることに関連付けられたＶＭタイプ制約を、ユーザＶＭ要求情報が含む一実施形態では、ＶＭがホストされることになるデータセンタの物理リソースへのＶＭの割り当てが、ＶＭタイプ制約に基づいて、実施されてよい。
【０１０２】
一実施形態において、ＶＭがホストされることになるデータセンタの物理リソースへのＶＭの割り当ては、ＶＭをデータセンタの物理リソースに割り当てるために構成されたＶＭ割り当て処理を使用して実施される。概して、ＶＭ割り当て処理の目的は、グラフの断片同士の間にいくつかの関係が存在するように、グラフを均等なサイズの断片に分ける（それにより、データセンタ内でホストされることになる要求されたＶＭをサポートするのに必要とされるデータセンタ通信リソースを最小限にする）ことである。しかしながら、一般にグラフ二分割問題と呼ばれる、グラフを２つの均等な断片に分ける最も単純なケースでさえ、ＮＰ困難である。加えて、関連した問題は、その目的がグラフをＫ個の断片に分けることであるＫ−カット問題であり、ここで、各断片のサイズはやはり、入力として指定される。
【０１０３】
ＶＭ割り当て処理において、ユーザＶＭ要求は、分割されることが必要なグラフとして見なされてよい。グラフのノードは、ＶＭを表し、グラフのリンクは、リンクによって接続された対のＶＭの間で必要とされる相対帯域幅を表す。グラフの各パーティションは、同じラックに割り当てられることが必要なＶＭの集合を表す。各パーティションのサイズは、ＶＭをホストするためのラックにおいて利用可能なリソースの量によって上に有界である必要がある。従来のグラフ分割問題とは異なり、この問題は、各パーティションにおける厳密なノードの数を指定しなくてもよく、代わりに、各パーティションにおける最大ノードのみを指定する。これは、任意の点において、クラウド環境においてＶＭをホストするために利用可能なリソースが、ユーザによって要求されたＶＭの数よりも多い場合があるからである。その結果、ＶＭ割り当て処理は、ＶＭをホストするために利用可能な最大リソースを有するラック内でＶＭを割り当てることによって、（ラック同士の間の）通信を最適化することができる。データセンタ内でのＶＭの割り当てでは、ラック同士の間のデータセンタ内通信コストは、データセンタの階層の切り替えにおけるラックの近さに依存してよい。したがって、適用する通信コストを最小限にするために、ラックパーティション同士の間の通信距離が考慮に入れられる。
【０１０４】
ＶＭ割り当て処理に関して、問題は以下のように導き出されてよい。エッジ重みｗ：Ｅ→Ｎが割り当てられたグラフＧ＝（Ｖ，Ｅ）、およびパーティションｉとｊとの間の距離をｄ（ｉ，ｊ）としてパーティション容量ｋ１，ｋ２，・・・の集合が与えられるとする。Ｖを、｜Ｃｉ｜≦Ｋｉおよび
【０１０５】
【数２】
2014522036.tif 000004
であるような、互いに素な集合Ｃ１，Ｃ２，・・・，Ｃｍに分割する。
【０１０６】
ＶＭ割り当て処理に関して、個々のユーザ要求がインクリメント方式で別々に扱われてもよく、または、すべての複数の要求がまとめて結合されて、複数の異なるユーザ要求のノード同士の間にいかなるエッジも含まない大きく分割されたグラフを形成してもよいことに留意されたい。
【０１０７】
ＶＭ割り当て処理に関して、グラフ分割問題はＮＰ困難であり、良好な（たとえば、一定の）近似保証を有する処理は存在しないことに留意されたい。
【０１０８】
一実施形態において、ＶＭ割り当て処理は、貪欲法に基づく発見的処理として実装される。
【０１０９】
一実施形態において、ＶＭ割り当て処理は、一度に１つのラックを選択する。ラックは、任意の好適な順序で選択されてよく（たとえば、各選択は、ユーザＶＭ要求において指定された１つまたは複数のＶＭ割り当て制約など、ならびにそのさまざまな組合せに基づいて、ＶＭをホストするために利用可能なリソースの最大量を有するラックが選択されるように、実施される）、選択されたラックに、可能な限り多くのＶＭを割り当てる。ＶＭ割り当て処理は、パラメータの最大値（たとえば、着信／発信帯域幅、近傍の数、など）を有するＶＭを選択し、選択されたＶＭを、選択されたラックに割り当てる。選択されたＶＭは、選択されたラックに割り当てられるＶＭの集合である集合Ｃに加えられる。ＶＭ割り当て処理は次いで、Ｃの近傍のすべてを考慮し、Ｃへの／Ｃからの最大トラフィックを有するＶＭを選択し、選択されたＶＭを集合Ｃに加える。この処理は、選択されたラックの利用可能なリソースのすべてが使い尽くされるまで、繰り返される。ＶＭ割り当て処理は次いで、（ＶＭをホストするために利用可能なリソースの最大量を有する）次のラックを選択し、次の選択されたラック、およびまだ割り当てられていない残りのＶＭ（すなわち、Ｖ−Ｃ）のグラフについて、処理を繰り返す。
【０１１０】
一実施形態において、ＶＭ割り当て処理は、特定のノードを交換することによって修正される。ＶＭ割り当て処理は、複数の異なるパーティションに存在する対のノードを考慮する。ＶＭ処理は、考慮されたノードの入れ替えが解を改善するか否か（たとえば、より少ないラック間帯域幅を使用するか）を判定することができる。ＶＭ処理は、パーティション同士の間でノードを（たとえば、ノードの現在のパーティションから利用可能な容量を有する複数の異なるパーティションへ）移動させることが、解を改善するか否かを判定することができる。ＶＭ割り当て処理は、考慮された移動のうちの１つまたは複数を選択し、選択された移動をコミットする。この処理は、繰り返されてよい（たとえば、閾値の移動の数がコミットされるまで、すべての移動が考慮されてＶＭ割り当てにおいてそれ以上の改善がなくなるまで、など）ことに留意されたい。
【０１１１】
ステップ３６０で、方法３００が終了する。
【０１１２】
本明細書では、仮想リソースが仮想マシン（ＶＭ）であり、物理リソースがブレードサーバのプロセッサである実施形態のコンテキスト内で主に示され、説明されたが、仮想リソース割り当て能力は、さまざまな他のタイプの仮想リソースの割り当てを決定する、および／またはさまざまな他のタイプの物理リソースへの割り当てを決定するために、使用されてもよいことに留意されたい。したがって、本明細書で使用される、ＶＭの割り当てに固有なさまざまな用語は、仮想リソースの割り当てへの言及として、より広く読まれてもよい。たとえば、本明細書でのＶＭおよびＶＭ割り当てへの言及は、それぞれ仮想リソースおよび仮想リソース割り当てとして、より広く読まれてもよい。たとえば、本明細書でのＶＭ割り当ての間に使用されるＶＭ割り当て制約（たとえば、ＶＭ配置制約、ＶＭ通信制約、ＶＭ復元力制約、ＶＭタイプ制約、など）への言及は、仮想リソース割り当ての間に使用される仮想リソース割り当て制約（たとえば、仮想リソース配置制約、仮想リソース通信制約、仮想リソース復元力制約、仮想リソースタイプ制約、など）として、より広く読まれてもよい。さまざまな他のＶＭ固有の用語もまた、同様のやり方で、より広く読まれてもよいことに留意されたい。
【０１１３】
図６は、本明細書で説明される機能を実施する際の使用に好適なコンピュータの高レベルブロック図を示す。
【０１１４】
図６に示されるように、コンピュータ６００は、プロセッサ要素６０２（たとえば、中央処理ユニット（ＣＰＵ）および／または他の好適なプロセッサ）、およびメモリ６０４（たとえば、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、など）を含む。コンピュータ６００はまた、協働モジュール／処理６０５、および／またはさまざまな入力／出力デバイス６０６（たとえば、ユーザ入力デバイス（キーボード、キーパッド、マウス、その他など）、ユーザ出力デバイス（ディスプレイ、スピーカ、その他など）、入力ポート、出力ポート、受信機、送信機、および記憶デバイス（たとえば、テープドライブ、フロッピー（登録商標）ドライブ、ハードディスクドライブ、コンパクトディスクドライブ、など））を含むことができる。
【０１１５】
本明細書で示され、説明された機能は、ソフトウェアにおいて（たとえば、１つまたは複数のプロセッサ上のソフトウェアの実装を介して）、ならびに／またはハードウェアにおいて（たとえば、汎用コンピュータ、１つまたは複数の特定用途向け集積回路（ＡＳＩＣ）、および／もしくは任意の他のハードウェア均等物を使用して）実装されてもよいことが認識されるであろう。
【０１１６】
本明細書で示され、説明された機能は、専用コンピュータを実装するために、汎用コンピュータで実行するためのソフトウェアにおいて（たとえば、１つまたは複数のプロセッサによる実行を介して）実装されてもよく、ならびに／またはハードウェアにおいて（たとえば、１つまたは複数の特定用途向け集積回路（ＡＳＩＣ）および／もしくは１つまたは複数の他のハードウェア均等物を使用して）実装されてもよいことが認識されるであろう。
【０１１７】
一実施形態において、協働処理６０５は、メモリ６０４にロードされ、プロセッサ６０２によって実行されて、本明細書で論じられた通りの機能を実装することができる。したがって、協働処理６０５（関連したデータ構造を含む）は、コンピュータ可読記憶媒体、たとえば、ＲＡＭメモリ、磁気もしくは光学ドライブ、または磁気もしくは光学ディスケットなどに記憶されてよい。
【０１１８】
図６に示されたコンピュータ６００は、本明細書で説明された機能要素、および／または本明細書で説明された機能要素の部分を実装するために好適な、一般的なアーキテクチャおよび機能性を提供することが認識されるであろう。たとえば、コンピュータ６００は、ブレードサーバ１１４、ＣＭＳ１２０、ＮＭＳ１３０、およびＣＡＳ１４０のうちの１つまたは複数を実装するために好適な、一般的なアーキテクチャおよび機能性を提供する。
【０１１９】
ソフトウェア方法として本明細書で論じられたステップのうちのいくつかは、ハードウェア内で、たとえば、さまざまな方法ステップを実施するためにプロセッサと協働する回路として、実装されてもよいことが企図される。本明細書で説明された機能／要素の部分は、コンピュータ命令が、コンピュータによって処理されるときに、コンピュータの動作を、本明細書で説明された方法および／または技法が呼び出される、または別のやり方で提供されるように適応させる、コンピュータプログラム製品として実装されてもよい。本発明の方法を呼び出すための命令は、固定された、または取り外し可能な媒体に記憶されても、ブロードキャストにおけるデータストリームまたは他の信号ベアリング媒体を介して送信されても、および／または、命令に従って動作するコンピューティングデバイス内のメモリ内に記憶されてもよい。
【０１２０】
さまざまな実施形態の態様は、特許請求の範囲において明記される。さまざまな実施形態のそれらの態様および他の態様は、以下の番号付けされた条項において明記される。
【０１２１】
１．プロセッサと、メモリとを含む装置であって、プロセッサが、
要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約を含む、仮想リソースについての要求を受信し、
クラウド環境に関連付けられた管理情報を受信し、
要求された仮想リソースの量、１つまたは複数の仮想リソース割り当て制約、および管理情報を使用して、クラウド環境内での要求された仮想リソースの割り当てを決定するように
構成されている、装置。
【０１２２】
２．仮想リソースが、仮想マシンおよび仮想記憶装置リソースのうちの少なくとも１つを含む、条項１に記載の装置。
【０１２３】
３．クラウド環境が、複数のデータセンタを含み、管理情報が、
クラウド環境のデータセンタ同士の間のデータセンタ間通信に関連付けられたネットワーク管理情報、および
データセンタのうちの少なくとも１つについての、データセンタに関連付けられた管理情報を含むクラウド管理情報
のうちの少なくとも１つを含む、条項１に記載の装置。
【０１２４】
４．１つまたは複数の仮想リソース割り当て制約が、ラックごとに割り当てられるべき仮想リソースの最大量、ラックごとに割り当てられるべき仮想リソースの最小数、データセンタごとに使用されるべきラックの最大数、データセンタごとに使用されるべきラックの最小数、データセンタごとに割り当てられるべき仮想リソースの最大量、データセンタごとに割り当てられるべき仮想リソースの最小量、使用されるべきデータセンタの最大数、および使用されるべきデータセンタの最小数のうちの少なくとも１つを含む、条項１に記載の装置。
【０１２５】
５．クラウド環境内での要求された仮想リソースの割り当てを決定することが、
クラウド環境内で利用可能なデータセンタの集合から、仮想リソースが割り当てられることになるデータセンタの集合を決定すること、
仮想リソースが割り当てられることになるデータセンタの集合への仮想リソースの割り当てを決定すること、
仮想リソースが割り当てられることになるデータセンタの集合の少なくとも１つのデータセンタについて、データセンタに割り当てられることになる仮想リソースをホストするためのデータセンタの物理リソースを選択すること、および
仮想リソースのうちの少なくとも１つについて、仮想リソースが割り当てられることになるデータセンタの物理リソースへの仮想リソースの割り当てを決定すること
を含む、条項１に記載の装置。
【０１２６】
６．仮想リソースが割り当てられることになるデータセンタの集合を決定することが、
複数の頂点と複数のエッジとを含むグラフとしてクラウド環境を表すことであって、複数の頂点が、利用可能なデータセンタを表し、利用可能なデータセンタに関連付けられた複数の重みを有し、複数のエッジが、利用可能なデータセンタ同士の間の複数の通信パスを表し、利用可能なデータセンタ同士の間の複数の通信パスに関連付けられた複数の長さを有する、グラフとしてクラウド環境を表すこと、
要求された仮想リソースの量に少なくとも等しい重みの総和および最小直径を有する、グラフの部分グラフを決定すること、および
仮想リソースが割り当てられることになるデータセンタの集合を、部分グラフから決定すること
を含む、条項５に記載の装置。
【０１２７】
７．仮想リソースが割り当てられることになるデータセンタの集合への仮想リソースの割り当てを決定することが、
仮想リソースを表す複数の頂点と、エッジで接続された仮想リソース同士の間の相対帯域幅を表す複数のエッジとを含むグラフとして、仮想リソースについての要求を表すこと、
分割されたグラフをそれにより形成するために、グラフを複数のパーティションに分割することであって、分割されたグラフの各パーティションが、同じそれぞれのデータセンタにおいてスケジュールされることになる仮想リソースのそれぞれの集合を表し、分割されたグラフの各パーティションが、各パーティションに関連付けられた、それぞれのデータセンタにおいて利用可能な仮想リソースの量によって上に有界であるサイズを有する、グラフを複数のパーティションに分割すること、および
分割されたグラフを使用して、仮想リソースが割り当てられることになるデータセンタの集合への仮想リソースの割り当てを決定すること
を含む、条項５に記載の装置。
【０１２８】
８．データセンタに割り当てられることになる仮想リソースをホストするためのデータセンタの物理リソースを選択することが、
データセンタのリソースを表す複数のノードを含むツリー型トポロジとしてデータセンタを表すことであって、ツリー型トポロジのノードの各々が、各々に関連付けられた、ノードに根付いた仮想リソースの量を表す重みを有し、ツリー型トポロジのノードの各々が、各々に関連付けられた、ツリー型トポロジ内のノードの高さを表す高さを有し、複数のノードが、データセンタのそれぞれ複数のラック、ブレードサーバ、またはプロセッサを表す複数の葉ノードを含む、ツリー型トポロジとしてデータセンタを表すこと、
その葉ノードが、データセンタに割り当てられることになる仮想リソースの量に少なくとも等しい累積重み、および最小高さを有する、ツリー型トポロジの部分ツリーを決定すること、ならびに
データセンタに割り当てられることになる仮想リソースをホストするためのデータセンタの物理リソースを、部分ツリーから決定すること
を含む、条項５に記載の装置。
【０１２９】
９．仮想リソースが割り当てられることになるデータセンタの物理リソースへの仮想リソースの割り当てを決定することが、
仮想リソースが割り当てられることになるデータセンタのラックを選択すること、
仮想リソースが割り当てられることになるデータセンタの選択されたラックのブレードサーバを選択すること、および
仮想リソースが割り当てられることになるデータセンタの選択されたラックの選択されたブレードサーバの中央処理ユニット（ＣＰＵ）を選択すること
を含む、条項５に記載の装置。
【０１３０】
１０．プロセッサが、
クラウド環境内での要求された仮想リソースの決定された割り当てに基づいて、クラウド環境内で仮想リソースのプロビジョニングを開始するように
さらに構成されている、条項１に記載の装置。
【０１３１】
１１．コンピュータによって実行されるときにコンピュータに方法を実施させる命令を記憶するコンピュータ可読記憶媒体であって、方法が、
要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約を含む、仮想リソースについての要求を受信するステップと、
クラウド環境に関連付けられた管理情報を受信するステップと、
要求された仮想リソースの量、１つまたは複数の仮想リソース割り当て制約、および管理情報を使用して、クラウド環境内での要求された仮想リソースの割り当てを決定するステップと
を含む、コンピュータ可読記憶媒体。
【０１３２】
１２．仮想リソースが、仮想マシンおよび仮想記憶装置リソースのうちの少なくとも１つを含む、条項１１に記載のコンピュータ可読記憶媒体。
【０１３３】
１３．クラウド環境が、複数のデータセンタを含み、管理情報が、
クラウド環境のデータセンタ同士の間のデータセンタ間通信に関連付けられたネットワーク管理情報、および
データセンタのうちの少なくとも１つについての、データセンタに関連付けられた管理情報を含むクラウド管理情報
のうちの少なくとも１つを含む、条項１１に記載のコンピュータ可読記憶媒体。
【０１３４】
１４．１つまたは複数の仮想リソース割り当て制約が、ラックごとに割り当てられるべき仮想リソースの最大量、ラックごとに割り当てられるべき仮想リソースの最小数、データセンタごとに使用されるべきラックの最大数、データセンタごとに使用されるべきラックの最小数、データセンタごとに割り当てられるべき仮想リソースの最大量、データセンタごとに割り当てられるべき仮想リソースの最小量、使用されるべきデータセンタの最大数、および使用されるべきデータセンタの最小数のうちの少なくとも１つを含む、条項１１に記載のコンピュータ可読記憶媒体。
【０１３５】
１５．クラウド環境内での要求された仮想リソースの割り当てを決定するステップが、
クラウド環境内で利用可能なデータセンタの集合から、仮想リソースが割り当てられることになるデータセンタの集合を決定するステップと、
仮想リソースが割り当てられることになるデータセンタの集合への仮想リソースの割り当てを決定するステップと、
仮想リソースが割り当てられることになるデータセンタの集合の少なくとも１つのデータセンタについて、データセンタに割り当てられることになる仮想リソースをホストするためのデータセンタの物理リソースを選択するステップと、
仮想リソースのうちの少なくとも１つについて、仮想リソースが割り当てられることになるデータセンタの物理リソースへの仮想リソースの割り当てを決定するステップと
を含む、条項１１に記載のコンピュータ可読記憶媒体。
【０１３６】
１６．仮想リソースが割り当てられることになるデータセンタの集合を決定するステップが、
複数の頂点と複数のエッジとを含むグラフとしてクラウド環境を表すステップであって、複数の頂点が、利用可能なデータセンタを表し、利用可能なデータセンタに関連付けられた複数の重みを有し、複数のエッジが、利用可能なデータセンタ同士の間の複数の通信パスを表し、利用可能なデータセンタ同士の間の複数の通信パスに関連付けられた複数の長さを有する、グラフとしてクラウド環境を表すステップと、
要求された仮想リソースの量に少なくとも等しい重みの総和および最小直径を有する、グラフの部分グラフを決定するステップと、
仮想リソースが割り当てられることになるデータセンタの集合を、部分グラフから決定するステップと
を含む、条項１５に記載のコンピュータ可読記憶媒体。
【０１３７】
１７．仮想リソースが割り当てられることになるデータセンタの集合への仮想リソースの割り当てを決定するステップが、
仮想リソースを表す複数の頂点と、エッジで接続された仮想リソース同士の間の相対帯域幅を表す複数のエッジとを含むグラフとして、仮想リソースについての要求を表すステップと、
分割されたグラフをそれにより形成するために、グラフを複数のパーティションに分割するステップであって、分割されたグラフの各パーティションが、同じそれぞれのデータセンタにおいてスケジュールされることになる仮想リソースのそれぞれの集合を表し、分割されたグラフの各パーティションが、各パーティションに関連付けられた、それぞれのデータセンタにおいて利用可能な仮想リソースの量によって上に有界であるサイズを有する、グラフを複数のパーティションに分割するステップと、
分割されたグラフを使用して、仮想リソースが割り当てられることになるデータセンタの集合への仮想リソースの割り当てを決定するステップと
を含む、条項１５に記載のコンピュータ可読記憶媒体。
【０１３８】
１８．データセンタに割り当てられることになる仮想リソースをホストするためのデータセンタの物理リソースを選択するステップが、
データセンタのリソースを表す複数のノードを含むツリー型トポロジとしてデータセンタを表すステップであって、ツリー型トポロジのノードの各々が、各々に関連付けられた、ノードに根付いた仮想リソースの量を表す重みを有し、ツリー型トポロジのノードの各々が、各々に関連付けられた、ツリー型トポロジ内のノードの高さを表す高さを有し、複数のノードが、データセンタのそれぞれ複数のラック、ブレードサーバ、またはプロセッサを表す複数の葉ノードを含む、ツリー型トポロジとしてデータセンタを表すステップと、
その葉ノードが、データセンタに割り当てられることになる仮想リソースの量に少なくとも等しい累積重み、および最小高さを有する、ツリー型トポロジの部分ツリーを決定するステップと、
データセンタに割り当てられることになる仮想リソースをホストするためのデータセンタの物理リソースを、部分ツリーから決定するステップと
を含む、条項１５に記載のコンピュータ可読記憶媒体。
【０１３９】
１９．仮想リソースが割り当てられることになるデータセンタの物理リソースへの仮想
リソースの割り当てを決定するステップが、
仮想リソースが割り当てられることになるデータセンタのラックを選択するステップと、
仮想リソースが割り当てられることになるデータセンタの選択されたラックのブレードサーバを選択するステップと、
仮想リソースが割り当てられることになるデータセンタの選択されたラックの選択されたブレードサーバの中央処理ユニット（ＣＰＵ）を選択するステップと
を含む、条項１５に記載のコンピュータ可読記憶媒体。
【０１４０】
２０．方法が、
クラウド環境内での要求された仮想リソースの決定された割り当てに基づいて、クラウド環境内で仮想リソースのプロビジョニングを開始するステップ
をさらに含む、条項１１に記載のコンピュータ可読記憶媒体。
【０１４１】
２１．要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約を含む、仮想リソースについての要求を受信するステップ、
クラウド環境に関連付けられた管理情報を受信するステップ、ならびに
要求された仮想リソースの量、１つまたは複数の仮想リソース割り当て制約、および管理情報を使用して、クラウド環境内での要求された仮想リソースの割り当てを決定するステップのために、
プロセッサおよびメモリを使用するステップを含む、方法。
【０１４２】
本発明の教示を組み込むさまざまな実施形態が、本明細書で詳細に示され、説明されてきたが、当業者は、これらの教示をなおも組み込む多くの他の変化した実施形態を、容易に考案することができる。
【図１】
2014522036.tif 000005
【図２】
2014522036.tif 000006
【図３】
2014522036.tif 000007
【図４Ａ】
2014522036.tif 000008
【図４Ｂ】
2014522036.tif 000009
【図５】
2014522036.tif 000010
【図６】
2014522036.tif 000011
【手続補正書】
【提出日】平成26年3月24日(2014.3.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
プロセッサと、プロセッサに通信可能に接続されたメモリとを含む装置であって、プロセッサが、
仮想リソースをホストするために利用可能な物理リソースのそれぞれの集合を含む利用可能なデータセンタの集合を含むクラウド環境の仮想リソースについての要求であって、要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約を含む、クラウド環境の仮想リソースについての要求を受信し、
要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約に基づいて、クラウド環境内での要求された仮想リソースの割り当てを決定するように
構成されており、
利用可能なデータセンタの集合から、要求された仮想リソースが割り当てられることになる選択されたデータセンタの集合を決定すること、
選択されたデータセンタの集合の中のデータセンタへの、要求された仮想リソースのそれぞれの部分の割り当てを決定すること、
データセンタに割り当てられることになる要求された仮想リソースのそれぞれの部分をホストするための、選択されたデータセンタの集合の中のデータセンタの物理リソースのそれぞれの集合を選択すること、および
選択されたデータセンタの集合の中のデータセンタの物理リソースのそれぞれの集合への、要求された仮想リソースのそれぞれの部分の割り当てを決定することによって、
クラウド環境内での要求された仮想リソースの割り当てを決定するように
プロセッサが構成されている、装置。
【請求項２】
クラウド環境のデータセンタ同士の間のデータセンタ間通信に関連付けられたネットワーク管理情報、および
データセンタのうちの少なくとも１つについての、データセンタに関連付けられた管理情報を含むクラウド管理情報
のうちの少なくとも１つを含む、クラウド環境に関連付けられた管理情報を受信し、
管理情報に基づいて、クラウド環境内での要求された仮想リソースの割り当てを決定するように
プロセッサが構成されている、請求項１に記載の装置。
【請求項３】
１つまたは複数の仮想リソース割り当て制約が、ラックごとに割り当てられるべき仮想リソースの最大量、ラックごとに割り当てられるべき仮想リソースの最小数、データセンタごとに使用されるべきラックの最大数、データセンタごとに使用されるべきラックの最小数、データセンタごとに割り当てられるべき仮想リソースの最大量、データセンタごとに割り当てられるべき仮想リソースの最小量、使用されるべきデータセンタの最大数、および使用されるべきデータセンタの最小数のうちの少なくとも１つを含む、請求項１に記載の装置。
【請求項４】
クラウド環境内での要求された仮想リソースの割り当てを決定することが、
選択されたデータセンタの集合の中のデータセンタ同士の間のパスのパス長を削減することにつながるやり方で、仮想リソースが割り当てられることになる選択されたデータセンタの集合を決定すること、
選択されたデータセンタの集合の中のデータセンタ同士の間のデータセンタ間トラフィックを削減することにつながるやり方で、選択されたデータセンタの集合の中のデータセンタへの、要求された仮想リソースのそれぞれの部分の割り当てを決定すること、
選択されたデータセンタの集合の中のそれぞれのデータセンタ内でのデータセンタ内トラフィックを削減することにつながるやり方で、データセンタに割り当てられることになる要求された仮想リソースのそれぞれの部分をホストするための、選択されたデータセンタの集合の中のデータセンタの物理リソースのそれぞれの集合を選択すること、および
選択されたデータセンタの集合の中のそれぞれのデータセンタ内でのデータセンタ内トラフィックを削減することにつながるやり方で、選択されたデータセンタの集合の中のデータセンタの物理リソースのそれぞれの集合への、要求された仮想リソースのそれぞれの部分の割り当てを決定すること
のうちの少なくとも１つを含む、請求項１に記載の装置。
【請求項５】
複数の頂点と複数のエッジとを含むグラフとしてクラウド環境を表すことであって、複数の頂点が、利用可能なデータセンタを表し、利用可能なデータセンタに関連付けられた複数の重みを有し、複数のエッジが、利用可能なデータセンタ同士の間の複数の通信パスを表し、利用可能なデータセンタ同士の間の複数の通信パスに関連付けられた複数の長さを有する、グラフとしてクラウド環境を表すこと、
要求された仮想リソースの量に少なくとも等しい重みの総和および最小直径を有する、グラフの部分グラフを決定すること、および
仮想リソースが割り当てられることになる選択されたデータセンタの集合を、部分グラフに基づいて決定することによって、
仮想リソースが割り当てられることになる選択されたデータセンタの集合を決定するように
プロセッサが構成されている、請求項１に記載の装置。
【請求項６】
仮想リソースを表す複数の頂点と、対の頂点を接続する複数のエッジとを含むグラフとして仮想リソースについての要求を表すことであって、一対の頂点を接続する１つのエッジが、そのエッジで接続された一対の頂点によって表される仮想リソース同士の間の相対帯域幅を表す、グラフとして仮想リソースについての要求を表すこと、
分割されたグラフをそれにより形成するために、グラフを複数のパーティションに分割することであって、分割されたグラフの各パーティションが、同じそれぞれのデータセンタにおいてスケジュールされることになる仮想リソースのそれぞれの集合を表し、分割されたグラフの各パーティションが、各パーティションに関連付けられた、それぞれのデータセンタにおいて利用可能な仮想リソースの量によって上に有界であるサイズを有する、グラフを複数のパーティションに分割すること、および
分割されたグラフに基づいて、選択されたデータセンタの集合の中のデータセンタへの、要求された仮想リソースのそれぞれの部分の割り当てを決定することによって、
選択されたデータセンタの集合の中のデータセンタへの、要求された仮想リソースのそれぞれの部分の割り当てを決定するように
プロセッサが構成されている、請求項１に記載の装置。
【請求項７】
データセンタのリソースを表す複数のノードを含むツリー型トポロジとしてデータセンタを表すことであって、ツリー型トポロジのノードの各々が、各々に関連付けられた、ノードに根付いた仮想リソースの量を表す重みを有し、ツリー型トポロジのノードの各々が、各々に関連付けられた、ツリー型トポロジ内のノードの高さを表す高さを有し、複数のノードが、データセンタのそれぞれ複数のラック、ブレードサーバ、またはプロセッサを表す複数の葉ノードを含む、ツリー型トポロジとしてデータセンタを表すこと、
その葉ノードが、データセンタに割り当てられることになる仮想リソースの量に少なくとも等しい累積重み、および最小高さを有する、ツリー型トポロジの部分ツリーを決定すること、ならびに
データセンタに割り当てられることになる要求された仮想リソースのそれぞれの部分をホストするためのデータセンタの物理リソースの集合を、部分ツリーに基づいて選択することによって、
選択されたデータセンタの集合の中のデータセンタのうちの少なくとも１つについて、データセンタに割り当てられることになる要求された仮想リソースのそれぞれの部分をホストするための、データセンタの物理リソースのそれぞれの集合を選択するように
プロセッサが構成されている、請求項１に記載の装置。
【請求項８】
仮想リソースが割り当てられることになるデータセンタのラックを選択すること、
仮想リソースが割り当てられることになるデータセンタの選択されたラックのブレードサーバを選択すること、および
仮想リソースが割り当てられることになるデータセンタの選択されたラックの選択されたブレードサーバの中央処理ユニット（ＣＰＵ）を選択することによって、
データセンタのうちの少なくとも１つに割り当てられることになる仮想リソースのうちの少なくとも１つについて、データセンタの物理リソースのそれぞれの集合への、仮想リソースの割り当てを決定するように
プロセッサが構成されている、請求項１に記載の装置。
【請求項９】
コンピュータによって実行されるときにコンピュータに方法を実施させる命令を記憶するコンピュータ可読記憶媒体であって、方法が、
仮想リソースをホストするために利用可能な物理リソースのそれぞれの集合を含む利用可能なデータセンタの集合を含むクラウド環境の仮想リソースについての要求を受信するステップであって、要求が、要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約を含む、クラウド環境の仮想リソースについての要求を受信するステップと、
要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約に基づいて、クラウド環境内での要求された仮想リソースの割り当てを決定するステップと
を含み、
クラウド環境内での要求された仮想リソースの割り当てを決定するステップが、
利用可能なデータセンタの集合から、要求された仮想リソースが割り当てられることになる選択されたデータセンタの集合を決定するステップと、
選択されたデータセンタの集合の中のデータセンタへの、要求された仮想リソースのそれぞれの部分の割り当てを決定するステップと、
データセンタに割り当てられることになる要求された仮想リソースのそれぞれの部分をホストするための、選択されたデータセンタの集合の中のデータセンタの物理リソースのそれぞれの集合を選択するステップと、
選択されたデータセンタの集合の中のデータセンタの物理リソースのそれぞれの集合への、要求された仮想リソースのそれぞれの部分の割り当てを決定するステップと
を含む、コンピュータ可読記憶媒体。
【請求項１０】
仮想リソースをホストするために利用可能な物理リソースのそれぞれの集合を含む利用可能なデータセンタの集合を含むクラウド環境の仮想リソースについての要求を受信するステップであって、要求が、要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約を含む、クラウド環境の仮想リソースについての要求を受信するステップ、ならびに
要求された仮想リソースの量、および１つまたは複数の仮想リソース割り当て制約に基づいて、クラウド環境内での要求された仮想リソースの割り当てを決定するステップのために、
プロセッサおよびメモリを使用するステップを含む、方法であって、
クラウド環境内での要求された仮想リソースの割り当てを決定するステップが、
利用可能なデータセンタの集合から、要求された仮想リソースが割り当てられることになる選択されたデータセンタの集合を決定するステップと、
選択されたデータセンタの集合の中のデータセンタへの、要求された仮想リソースのそれぞれの部分の割り当てを決定するステップと、
データセンタに割り当てられることになる要求された仮想リソースのそれぞれの部分をホストするための、選択されたデータセンタの集合の中のデータセンタの物理リソースのそれぞれの集合を選択するステップと、
選択されたデータセンタの集合の中のデータセンタの物理リソースのそれぞれの集合への、要求された仮想リソースのそれぞれの部分の割り当てを決定するステップと
を含む、方法。
【国際調査報告】
2014522036.tif 000012
2014522036.tif 000013