(57)【特許請求の範囲】
【請求項１】
特定の顧客のためにデータセンターがサービスを提供するための、前記データセンターの費用を表すデータセンター顧客費用を決定するためのデータセンター管理システムであって、
プロセッサと、
前記プロセッサに通信可能に接続されたメモリと、
を備え、
前記プロセッサは、
前記データセンターの顧客に対応し且つデータセンター資源使用量モデルおよびサービス・レベル・アグリーメントを含むデータセンター顧客プロファイルに少なくとも部分的に基づいて、前記データセンターの顧客に対するデータセンター資源配分を決定することと、
前記データセンター顧客費用を決定することと、
を含む方法を実行し、
前記データセンター顧客費用を決定することは、
前記データセンターの各顧客のための前記サービス・レベル・アグリーメントのタイプに基づいて、各顧客をグループに分類することと、
前記特定の顧客と前記特定の顧客を含むグループとに基づいて、前記特定の顧客のために前記データセンター顧客費用を計算することと、
を含み、
前記計算は、次式を計算することにより行うデータセンター管理システム。
【数１】
0005890629.tif 000010
ここで、
Ａは、前記データセンターの全ての顧客の組を表し、
ａは、前記特定の顧客を表し、
Ａ１は、前記特定の顧客ａを含むグループを表し、
ｓ（Ａ, a∈Ａ1）は、前記データセンター顧客費用を表し、
ｎは、前記データセンターの顧客の数を表し、
ｉは、前記データセンターの顧客の組み合わせのための、前記特定の顧客を含まない、各グループの前記データセンターの顧客の数を表し、
ｎｉは、ｉ番目のグループの前記データセンターの顧客の数を表し、
Ｎは、グループの総数を表し、
ｉ*は、前記特定の顧客以外の前記データセンターの顧客のすべての数を表し、
ｉｉは、前記データセンターの顧客の特別な組み合わせのための前記ｉ番目のグループの前記データセンターの顧客の数を表し、
ｍ（ｉ，ａ）は、前記データセンターの顧客の前記特別な組み合わせにおける他のデータセンターの顧客に関する前記特定の顧客ａの限界費用を表す。
【請求項２】
特定の顧客のためにデータセンターがサービスを提供するための、前記データセンターの費用を表すデータセンター顧客費用を決定するためのデータセンター管理システムであって、
プロセッサと、
前記プロセッサに通信可能に接続されたメモリと、
を備え、
前記プロセッサは、
前記データセンターの顧客に対応し且つデータセンター資源使用量モデルおよびサービス・レベル・アグリーメントを含むデータセンター顧客プロファイルに少なくとも部分的に基づいて、前記データセンターの顧客に対するデータセンター資源配分を決定することと、
前記データセンター顧客費用を決定することと、
を含む方法を実行し、
前記データセンター顧客費用を決定することは、
各顧客をグループに分類することと、
前記特定の顧客、前記特定の顧客を含むグループ、及び、他のグループからランダムに選択された他の顧客に関しての前記特定の顧客の限界費用に基づいて、前記データセンター顧客費用を計算することと、
を含み、
前記計算は、次式を計算することにより行うデータセンター管理システム。
【数２】
0005890629.tif 000011
ここで、
Ａは、前記データセンターの全ての顧客の組を表し、
ａは、前記特定の顧客を表し、
Ａ１は、前記特定の顧客ａを含むグループを表し、
ｓ（Ａ, a∈Ａ1）は、前記データセンター顧客費用を表し、
ｎは、前記データセンターの顧客の数を表し、
ｉは、インデックスを示し、
Ｓは、前記特定の顧客ａ以外の前記データセンターの全ての顧客の組を示し、
Ａｉは、前記データセンターの顧客のｉ番目のグループを示し、
Ｓｉは、特定の顧客ａを除いた前記データセンターの顧客の前記ｉ番目のグループを示し、
Ｎは、グループの総数を示し、
ｍ（ｉ，ａ）は、前記データセンターの顧客の特別な組み合わせにおける他のデータセンターの顧客に関する前記特定の顧客ａの限界費用を表す。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示技術は、データセンターの分野に関し、さらに詳しくはデータセンター運用に関連して実装することができる、データセンター顧客費用決定メカニズムに関連する種々の技術に関する。
【背景技術】
【０００２】
典型的なデータセンターは、マシン資源（またはマシンリソース）をデータセンターの顧客にリースすることによって、数百あるいは数千にも上る、種々のデータセンター顧客のために機能する。各データセンター顧客は、一般にデータセンター自体の一定の費用を顧客と関連付けた、あるレベルのデータセンター資源要件を有する。データセンター資源要件は、典型的には、メモリ、ディスク空き容量、プロセッサ、およびバンド幅などのコンピュータ資源への要求を含む。例えば、同一のデータセンター内の他のデータセンター顧客よりも記憶しようとするデータ量が著しく多いデータセンター顧客は、典型的にはデータセンターからメモリなどのデータ記憶資源の量を著しく多く必要とすることになる。
【０００３】
データセンターをさらに効率的に管理するためには、データセンターが、このようなデータセンター顧客費用情報を、例えばデータセンター管理部を経由して可能な限り正確に提供されることが重要である。このような情報は、起こりうる価格設定変更、料金請求、およびサービス・レベル・アグリーメント（ＳＬＡ＝ｓｅｒｖｉｃｅ  ｌｅｖｅｌ  ａｇｒｅｅｍｅｎｔ：サービス品質保証契約）設計に関係する決定を行うデータセンター管理部によって使用することができる。データセンターが、例えばデータセンター顧客によるデータセンター資源の期待使用量よりも多い量を経験する状況では、データセンター管理部は、料金を上げることによって、費用をデータセンター顧客に配分するように決定してもよい。残念ながら、データセンター顧客費用に関する現在の理解では、計算するのは困難である。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
したがって、データセンター自体に対して、データセンターの顧客の費用を実用的に計算する効率的で拡張可能な方法に対する必要性が、依然として存在する。
【図面の簡単な説明】
【０００５】
【図１】図１は、データセンター管理インターフェース、データセンター顧客登録モジュール、資源最適化モジュール、データセンター顧客費用決定モジュール、運用センター、および資源使用量モデル更新モジュールを含む、データセンター最適化システムの一例を図示する。
【図２】図２は、本開示技術の実施の形態に従って、複数のデータセンター顧客から成る部分集合コレクションを使用して、データセンター顧客費用を決定する方法の第１の例を図示するフローチャートである。
【図３】図３は、本開示技術の実施の形態に従って、順列（または置換）コレクションを使用して、データセンター顧客費用を決定する方法の第２の例を図示するフローチャートである。
【図４】図４は、本開示技術の実施の形態に従って、データセンター顧客グループ分け技術を使用して、データセンター顧客費用を決定する方法の第１の例を図示するフローチャートである。
【図５】図５は、本開示技術の実施の形態に従って、データセンター顧客費用決定モジュールによって特定することができる、データセンター顧客グループの２つの集合のグラフィック表現の一例を図示する。
【図６】図６は、本開示技術の実施の形態に従って、概算技術を使用して、一グループ分け内のデータセンター顧客に対するシャープレイ（Ｓｈａｐｌｅｙ）値の概算を決定するグラフィック表現の一例を図示する。
【図７】図７は、本開示技術の実施の形態に従って、データセンター顧客グループ分け技術を使用して、データセンター顧客費用を決定する方法７００の第２の例を図示するフローチャートである。
【図８】図８は、図７に図示されたデータセンター顧客費用決定方法に関連して実行される、データセンター顧客グループから成る部分集合コレクションを作り出すために、順列で組み合わせられたシャッフルのグラフィック表現の一例を図示する。
【発明を実施するための形態】
【０００６】
図１は、本開示技術の実施の形態に従って、データセンター最適化システム１００の一例を図示する。この例では、データセンター最適化システム１００は、データセンター管理モジュール１０２、データセンター顧客登録モジュール１０４、データセンター資源最適化モジュール１０６、およびデータセンター顧客費用決定モジュール１０８を含む。本明細書では、データセンター管理モジュール１０２は、一部の意思決定プロセスにおいて、価格設定、料金請求、およびＳＬＡ設計職務に関連する人々などの人間のデータセンター管理部（データセンター管理者）の関与を含むことができる。この例では、データセンター最適化システム１００は、例えば複数のデータ・センター・サーバから成るグループなどの運用センター１１０、およびデータセンター資源使用量モデル更新モジュール１１２も含む。
【０００７】
この例では、データセンター顧客登録モジュール１０４は、データセンター顧客特定の、データセンターとのサービス・レベル・アグリーメント（ＳＬＡ）の実施を容易にするとともに、データセンター顧客に対するデータセンター資源使用量モデルを確立することによって、新たな各データセンター顧客を登録するのに使用することができ、ここで、データセンター資源使用量モデルは、一般にデータセンター顧客によって頼まれた特定のデータセンター資源を数値化することを含んでいる。例えば、データセンター顧客登録モジュール１０４は、メモリ、ディスク空き容量、およびＣＰＵバンド幅などの特定の各データセンター資源を、データセンター顧客がどのくらい頼みたいかについて、データセンター顧客に問い合わせを行うことができる。次いでデータセンター最適化システム１００は、データセンター顧客用のデータセンター顧客プロファイルを作り出すとともに、データセンター顧客に対するＳＬＡおよびデータセンター資源使用量モデルを、データセンター顧客プロファイルの一部として、ともに記憶することができる。
【０００８】
データセンター資源最適化モジュール１０６は、例えばデータセンター顧客のＳＬＡおよびデータセンター資源使用量モデルに基づいて、所与のデータセンター顧客に対する初期のおよび／または最適なデータセンター資源配分を決定し、次いでこのデータセンター資源配分を運用センター１１０に割り当てることができ、運用センター１１０は、運用センター１１０によって実行する複数のデータ・センター・サーバから成るグループを含むことができる。一部の実施の形態では、データセンター資源最適化モジュール１０６は、名称が「データセンターにおける資源要件の統計的パッキング（ＳＴＡＴＩＳＴＩＣＡＬ  ＰＡＣＫＩＮＧ  ＯＦ  ＲＥＳＯＵＲＣＥ  ＲＥＱＵＩＲＥＭＥＮＴＳ  ＩＮ  ＤＡＴＡ  ＣＥＮＴＥＲＳ）」で、出願日が２００８年１０月１６日である、同時係属中の米国特許出願第１２／２５３，１１１号明細書に記載された技術などの統計的パッキング技術を使用することができ、上述した明細書は参照することによって本明細書内に全面的に援用される。しかしながら、種々の他のデータセンター資源最適化技術が、データセンター資源最適化モジュール１０６によって用いることができることを、当業者は理解するだろう。
【０００９】
典型的なデータセンター資源最適化モジュールによって決定された、初期のデータセンター資源配分は、データセンターに属する多数の顧客のニーズを満たすのに最適なデータセンター資源の使用量を表すという点で最適かもしれないが、しかしながらこの資源配分は、データセンター内の個々の顧客のプロビジョニング費用に関する情報を必ずしも提供してはいない。本開示技術の実施の形態では、データセンター資源最適化モジュール１０６は、データセンター顧客費用決定モジュール１０８とやり取りすることができ、この決定モジュール１０８は、特定のデータセンター顧客へメモリを提供し資源を処理するなどのサービスを提供するための、データセンターの費用を決定するまたは見積もることができる。
【００１０】
一部の実施の形態では、データセンター管理モジュール１０２は、特定のデータセンター顧客に対するデータセンター顧客費用を決定するための依頼書を、データセンター顧客費用決定モジュール１０８へ送ることができる。代わりの構成としては、データセンター資源管理モジュール１０２は、複数のデータセンター顧客から成る特定のグループに対応するデータセンター顧客費用を決定するための依頼書を、データセンター顧客費用決定モジュール１０８へ送ることができる。
【００１１】
データセンター顧客費用決定モジュール１０８は、特定のデータセンター顧客または複数のデータセンター顧客から成る特定のグループの、データセンターの費用を決定するために、本明細書で説明される技術のいずれかを使用することができる。所与のデータセンター顧客または複数のデータセンター顧客から成る所与のグループに対するデータセンター顧客費用の決定は、価格設定、料金請求、ＳＬＡ設計または再設計などに関連する業務上に、種々のフィードバックをもたらすことができる。例えば、データセンター管理部は、データセンター資源に関するデータセンター顧客の使用量が、データセンター顧客のプロファイルに基づいてデータセンターが期待した使用量のレベルを越えるときのように、費用が期待値よりも高い状況にある、特定のデータセンター顧客または複数のデータセンター顧客から成る特定のグループに対して、価格設定条件を調査するように望むことができる。したがって、妥当で公平な原価計算メカニズムを提供することによって、データセンター管理部および業務部門が、彼らの運用費用の理解、彼らのサービス提供の価格設定、および彼らのデータセンター顧客への料金請求の仕事を、公正なやり方でより良好に行うことが可能となる。
【００１２】
本明細書で説明された技術は、正確な費用情報を生成してデータセンター管理部へ提供するのに、使用することができる。データセンターが、例えば、内部の顧客を有する社内データセンターおよび経費センターなどにおいて、直接に顧客に請求するために、このような費用情報を使用することができるというシナリオがある。例えば、請求書を理解する簡単なやり方を必要としている外部の顧客を含む代わりのシナリオは、より簡単な料金請求式が、例えば複数のＳＬＡおよび実際に使用された複数の資源から成る１つ以上のカテゴリーに基づくという実装を含むことができる。このような簡単な料金請求式が使用される状況では、本明細書で説明された正確な費用フィードバック技術の適用によって、データセンター管理部が、簡単な料金請求式を調整して、データセンター顧客にサービスを提供する費用の正確な理解を反映することが可能となる。
【００１３】
データセンター資源使用量モデル更新モジュール１１２は、運用センター１１０を監視し、隠れマルコフモデリングまたはヒストグラム計算などのモデリング技術を用いることができる。システムは、データセンター顧客登録モジュール１０４を経由して最初に提供されるモデル顧客資源ニーズに対して、このようなモデリング技術を使用して、データセンター資源最適化モジュール１０６に動的負荷予測を提供することができる。運用センター１１０の監視に基づいて、データセンター資源使用量モデル更新モジュール１１２は、データセンター顧客登録モジュール１０４へ勧告を与えることができる。例えば、運用センター１１０に関する、特定のデータセンター顧客の一定期間にわたる使用量が与えられたとすると、データセンター顧客登録モジュール１０４が、このデータセンター顧客用のデータセンター顧客プロファイルを改訂することを、データセンター資源使用量モデル更新モジュール１１２は勧めることができる。代わりの実施の形態では、データセンター資源使用量モデル更新モジュール１１２は、直接にデータセンター顧客プロファイルを改訂するか、それとも新たに作り出されたデータセンター顧客プロファイルを提供するかして、データセンター顧客用の現在のデータセンター顧客プロファイルを置き換えることができる。
【００１４】
（個々の顧客費用）
最適化アルゴリズムが適用される状況において、個々のデータセンター顧客の費用を計算して、例えば、実行しなければならないサーバの数などの資源プロビジョニングが決定されていたが、複数のデータセンター顧客の全体は問題が多いからである。例えば、データセンター顧客が今後の負荷用に適正な資源を有することを保証するのに使用される、追加のプロビジョニングのうちの少なくとも一部は、多数のデータセンター顧客間で共有することができる。したがって、このようなシナリオにおいて、費用を個々のデータセンター顧客と直接に関連付けることは、一般には起こりえない。
【００１５】
個々のデータセンター顧客を、複数のデータセンター顧客から成る現在のグループに追加する限界費用を簡単に計算すると、個々のデータセンター顧客の費用をおそらく低く評価することになるが、なぜなら全体としてこのグループに対する資源プロビジョニングが、予約されたが未使用のかなりの量の、偶発事象要件を満たす資源をすでに含むことがあり、その結果、グループに対してメンバーが、ＳＬＡに従って必要な資源を有することができるからである。このような状況では、新たなデータセンター顧客に対する限界費用は、典型的には低い。新たな顧客のＳＬＡ要件が低いような一部の状況では、複数のデータセンター顧客から成るグループに予約された資源はすでに足りていて、結果としてデータセンターに対する新たなデータセンター顧客の限界費用はゼロとなることがある。
【００１６】
複数のデータセンター顧客から成る共同で最適化されたグループにわたる費用分配に対処するために、本開示技術の実装は、シャープレイ値などの協力ゲームから導き出された技術の適用を含むことができる。これらの技術は、データセンター顧客費用を配分する、原則に基づいたやり方を提供することができる。複数のデータセンター顧客から成る一グループ全体をさらに公正に扱うために、これらの技術は、複数の顧客から成るこのグループに属するすべての部分集合にわたって計算することを含むことができる。このような技術は、少数の顧客に対して効果的であるものの、多数の顧客に対しては法外な計算量となることがある。
【００１７】
データセンター費用計算を加速し概算する方法が、本明細書で説明されるが、この方法は、複数の顧客から成る複数の部分集合の全部にわたっては計算せず、代わりに複数の顧客に関する費用およびグループ分けの定義の構造を利用して、考慮される複数の顧客から成る複数の部分集合を体系的に削減し、結果として計算を拡張可能かつ効率的にする。本明細書で説明される技術は、一般にシャープレイ値に関連してはいるが、このような技術は、仁（Ｎｕｃｌｅｏｌｕｓ）またはコア（Ｃｏｒｅ）などの協力ゲームにおける他の解概念、およびこれらの概念の他の変形例であって、複数のデータセンター顧客から成る複数の部分集合にわたる計算を含む変形例に対しても、適用することができる。
【００１８】
データセンター顧客費用を決定する、種々の拡張可能で効率的な方法が、本明細書で説明される。一部の実施の形態では、所与のデータセンター顧客に対するデータセンター顧客費用の決定は、データセンター顧客に対するデータセンター費用の概算を実行することによって行うことができる。一部の実施の形態では、データセンター顧客費用を決定する際に、シャフリングなどのランダム化技術を使用することができる。代わりの実施の形態では、クラスタリングなどのグループ分け技術を使用することができる。このような技術は、例えばＳＬＡによって、複数のデータセンター顧客を複数のグループにグループ分けする技術を含むことができ、多数のデータセンター顧客に対して実行される計算量を大きく削減することができる。
【００１９】
（シャープレイ値として表されたデータセンター顧客費用）
本明細書では、データセンター顧客費用は、一般にデータセンター顧客にサービスを提供するための、データセンターの費用を反映する、決定または見積もりを指す。本開示技術の一部の実施の形態では、所与のデータセンター顧客に対するデータセンター顧客費用は、シャープレイ値として表される。「Ｓの後のａ」に対する限界費用の次の定義を考察し、ここで「ａ」は、すべてのデータセンター顧客から成る集合「Ａ」、例えばサイズが「ｎ」のデータセンター顧客から成る一集合「Ａ」、の中の特定のデータセンター顧客であり、「Ｓ」は、「Ａ」内の他の複数のデータセンター顧客から成る一部分集合を表し、「ν（Ｓ）」は、部分集合「Ｓ」に対する最適なデータセンター資源総使用量の数値化、例えば部分集合「Ｓ」に対する費用を表す：
【００２０】
【数１】
0005890629.tif 000002
【００２１】
したがって、特定のデータセンター顧客「Ｓの後のａ」に対する限界費用の大きさが、他の複数のデータセンター顧客から成る部分集合「Ｓ」の最適なデータセンター資源総使用量を、データセンター顧客「ａ」および部分集合「Ｓ」の最適なデータセンター資源総使用量から減算することによって定義できることを、当業者は認識するだろう。
【００２２】
方程式１内の最適なデータセンター資源総使用値のうちのいずれかまたは両方は、図１のデータセンター顧客費用決定モジュール１０８などのデータセンター顧客費用決定モジュールによる決定の依頼に応じて、例えば図１のデータセンター資源最適化モジュール１０６などのデータセンター資源最適化部によって計算することができる。システムは、仮定の部分集合「Ｓ」に対する値であって、図１の運用センター１１０に対して最適化している全体集合「Ａ」とは異なる値を計算するように、データセンター資源最適化モジュール１０６に頼むことができる。代わりの構成としては、システムは、方程式１内の限界費用「ｍ（Ｓ，ａ）」を直接に計算するように、データセンター資源最適化モジュール１０６に頼むことができる。しかしながら、複数の最適なデータセンター資源総使用値の決定は、データセンター資源最適化モジュールに限定されているのではなく、むしろデータセンター資源最適化モジュールは、複数の最適なデータセンター資源総使用値を決定することができる種々のタイプのメカニズムのうちの１つにすぎない。
【００２３】
所与のデータセンター顧客「ａ」の限界費用または増分費用が、顧客「ａ」が「Ｓ」のサイズと同様にグループ分けされた、他の複数のデータセンター顧客「Ｓ」から成る特定の部分集合に依存することを、当業者は理解するだろう。例えば、データセンター顧客「ａ」を小さい部分集合「Ｓ」に追加すると、しばしば新たな資源の予約が必要となり、他方でデータセンター顧客を大きい部分集合に追加することは、資源予約を共有するために、より容易に成し遂げられる。さらにその上、集合「Ｓ」内の複数の異質のデータセンター顧客から成る所与の集合は、最適な資源総使用量に与える正味の影響に関して、複雑なやり方で「ａ」とやり取りすることができる。それで「Ａ」に属するすべての元（以下、断らない限り集合の「げん」を指す）の限界費用が、「Ｓ」に元を１つずつ追加することによって計算される場合、結果は著しくバイアスをかけられる可能性がある。シャープレイ値は、元が集合体「Ａ」に対する「Ｓ」に追加されながら、元に関する起こりうるすべての順序にわたって平均することによって、このようなシナリオに対処する。
【００２４】
この例では、データセンター顧客「ａ」のシャープレイ値は、「ｓ（Ａ，ａ）」によって表され、「Ａ」内の他の複数のデータセンター顧客のうち、起こりうるすべてのグループ分け「Ｓ」にわたって取られる、データセンター顧客「ａ」の平均限界費用として定義される。シャープレイ値の計算は、次のように記述される。
【００２５】
【数２】
0005890629.tif 000003
【００２６】
しかしながら、「Ａ」から成るすべての部分集合「Ｓ」にわたる総和には、式「ｍ（Ｓ，ａ）」の２ｎ−１回の見積もりが必要であり、一定のサイズよりも大きな、例えば１０を超えるデータセンター顧客から成る複数のグループのような、複数のデータセンター顧客から成る複数のグループに対するデータセンター資源費用を実用的に見積もることが、法外なものとなる可能性があることに、当業者は留意するだろう。
【００２７】
（ランダム化技術を使用するデータセンター顧客費用の決定）
データセンター顧客「ａ」に対するシャープレイ値「ｓ（Ａ，ａ）」の代わりの、しかしこれと等価な定義は、次のように記述される。
【００２８】
【数３】
0005890629.tif 000004
【００２９】
最初の総和内の式が、サイズ「ｉ」のすべての部分集合にわたって取られる限界費用の平均を表すことに、当業者は留意するだろう。この解釈は、データセンター顧客「ａ」に対するシャープレイ値の概算「∧ｓ（Ａ，ａ）」を決定する自然なやり方を示唆し、このやり方では、サイズ「ｉ」のすべての集合に対して限界費用「ｍ（Ｓ，ａ）」を見積もるよりも、むしろ「Ａ」に属する部分集合「Ｓ」のコレクション（例えば、「かなり代表的な」コレクション）にわたって、平均が取られる。
【００３０】
一部の実施の形態では、ランダム化技術が使用されて、例えばサイズ「ｉ」の「ｍ」個のランダムサンプル集合「Ｓ」を生成することができ、残りのデータセンター顧客のそれぞれは、同等の機会で選択される。各サイズが「ｉ」の複数の部分集合のランダムサンプルの数は、結果の正確さを改善するために調整することができる。このような技術は、方程式３内の総計に、概算を加えることができる。さらに、部分集合「Ｓ」に対して任意のデータセンター顧客を選択する可能性が同等であるので、これらの技術は、特定の個々の任意のデータセンター顧客の取り扱いにおいて、公正であるとみなすことができる。
【００３１】
ランダム化がその結果内に変動を作り出し、それゆえに個々のデータセンター顧客のすべてに対するシャープレイ値の合計が総費用「ν（Ａ）」に正確には等しくできないので、さらに構造化されたパターンが使用されて、「Ａ」に属する部分集合コレクション「Ｓ」を選択する。これらの構造化されたコレクションは、方程式１において「ν（．．．）」の著しく少ない見積もりを計算することによって、計算を削減することができ、いくつかの場合には、計算された見積もりが、１つの限界計算を超えて使用される。
【００３２】
一部の実施の形態では、複数のサンプル集合「Ｓ」から成る構造化されたコレクションが、複数の元「Ａ」から成る順列「π」から生成することができる。以下では「ａｊ」は、「ｊ」が集合「Ａ」内の元「ａ」の添え字であることを示すのに使用される。集合「Ｓ」は、順列のプレフィックスとして定義することができる。
【００３３】
【数４】
0005890629.tif 000005
【００３４】
この表記法を使用することによって、「ａｊ」に対するシャープレイ値は、次のようにすべての順列にわたる平均として表される。
【数５】
0005890629.tif 000006
【００３５】
大きい「ｎ」にとって、すべての順列を計算すると、法外に費用のかかる可能性がある。しかしながら単一の順列では、不正確になりかねない。例えば、順列内の早期に現れる顧客は、典型的には最後に現れる顧客よりも高い費用を払うはずである。単一の順列の巡回順列（または巡回置換）であり、その結果、各元は順列内の異なる位置に、同等に高頻度で現れる順列ファミリー（複数の順列から成るファミリー＝順列族（または置換族））「π（１），π（２），．．．」を使用して、シャープレイ値を概算することによって、システムはこれらの問題に対処することができる。シャッフル順列（またはシャッフル置換）などの他の順列が、巡回順列に加えてまたは置き換えて使用され、シャープレイ値を概算するのに有益な順列ファミリーを生成することができる。
【００３６】
小さい構造化された順列ファミリーがシャープレイ値を概算するのに使用される状況では、方程式５内の因数「１／ｎ！」は、使用された順列の数に適応することができる。本明細書では、このことは再正規化方程式５と呼ばれることになる。構造化された順列ファミリーは、方程式４に従って、構造化された部分集合ファミリー（複数の部分集合から成るファミリー＝部分集合族）にも対応することができ。これらの部分集合がシャープレイ値を概算するのに使用される場合、方程式３内の正規化因数は、使用された実際の多数の部分集合（およびサイズ「ｉ」）に適応することができる。本明細書では、このことは再正規化方程式３と呼ばれることになる。これらのアプローチが、少数の構造化されたサンプルを使用して、指数関数的な数の加数を概算することに類似しているものの、正規化する各アプローチが異なることを、当業者は理解するだろう。
【００３７】
上述した一部のこれらの計算が、単一のデータセンター顧客に対する費用を計算するように説明されたが、多くのまたはすべてのデータセンター顧客に対する費用を同時に計算するように、他の実装を構成することができる。例えば、構造化された順列ファミリーを列挙するとき、システムは、再正規化方程式５を使用して、すべてのデータセンター顧客に対する概算シャープレイ値を計算することができる。
【００３８】
シャープレイ値の概算にバイアスをかけることができる効果は、一顧客「ａｊ」に対する限界費用「ｍ（Ｓ，ａｊ）」を計算すると、集合「Ｓ」内の別の顧客「ａｋ」の存在を感知できることであり、こういう訳で「ａｊ」を除いて複数の元の巡回順列から成るファミリー「Π（−ｊ）」を最初に構成し、次いで「Π（−ｊ）」内の各順列の起こりうる各位置に「ｊ」を挿入することによって、「Π（−ｊ）」を全順列「Π」から成るファミリーへ拡大することが有益な場合がある。
【００３９】
一部の実施の形態では、ランダム化技術は、上述した構造化されたアプローチと組み合わせられて、複数の部分集合を生成することができる。例えば、いくつかのランダム順列（またはランダム置換）を最初に選択することができる。次いで、各ランダム順列は、例えば各ランダム順列のすべての巡回順列を仕上げることによって、上述した方法のいずれかに従って一順列ファミリーへ仕上げることができる。
【００４０】
複数のデータセンター顧客から成る「かなり代表的な」集合がどのように見えるかについて、典型的なデータセンター管理部はしばしば良好な考えを有するので、彼または彼女は、複数の代表的顧客から成る小さいコレクションおよび複数のデータセンター顧客の複数の代表的部分集合から成るコレクションを構成し、これらのコレクションを使用して、シャープレイ値の概算を計算することができる。より少数の代表的顧客およびより少数の代表的部分集合が、方程式３内の最初の合計の内部の式をさらに効率的に概算するのに使用することができる。一部の実装は、巡回順列などの上述した構造化技術を使用して、複数のデータセンター顧客から成る代表的集合から、複数の代表的部分集合から成るファミリーを導き出すことができる。
【００４１】
図２は、ランダム化、代表的顧客、または顧客もしくは代表的顧客の順列のファミリー、を使用して導き出された、複数のデータセンター顧客から成るコレクションを使用して、データセンター顧客費用を決定する方法２００の第１の例を図示するフローチャートである。
【００４２】
２０２において、例えば図１のデータセンター顧客費用決定モジュール１０８などのデータセンター顧客費用決定モジュールは、一部のまたはすべてのデータセンター顧客を特定する。例えば、データセンター顧客費用決定モジュールは、リースが消滅していないデータセンター顧客などの複数の有効なデータセンター顧客のみを特定することができる。複数のデータセンター顧客は、初期の配列または順序を有することができる。例えば、複数のデータセンター顧客は、リース開始日または終了日などの日付によって、初期のまたは現在のデータセンター資源配分の量などのサイズによって、アルファベット順にデータセンター顧客名によって、または複数のデータセンター顧客から成るグループを順に並べる事実上任意の他のやり方によって、順に並べることができる。
【００４３】
２０４において、データセンター顧客費用決定モジュールは、複数のデータセンター顧客から成る部分集合コレクションを選択する。データセンター顧客費用決定モジュールは、相当数の異なるやり方のうちのいずれかで、部分集合コレクションを選択することができる。例えば、データセンター顧客費用決定モジュールは、ランダムに、または複数の代表的部分集合から成るコレクションとしてもしくは順列ファミリーから導き出された部分集合コレクションとして、部分集合コレクションを選択することができる。
【００４４】
次いで２０６において、データセンター顧客費用決定モジュールは、本明細書で説明される技術に従って選択された部分集合コレクションに基づいて、データセンター顧客に対するシャープレイ値の概算を決定する。
【００４５】
２０８において、データセンター顧客費用決定モジュールは、データセンター顧客に対して生成された概算シャープレイ値を、例えば図１のデータセンター管理モジュール１０２などのデータセンター管理インターフェースへ送る。
【００４６】
図３は、データセンター顧客ランダム化技術を使用して、データセンター顧客費用を決定する方法３００の第２の例を図示するフローチャートである。３０２において、例えば図１のデータセンター顧客費用決定モジュール１０８などのデータセンター顧客費用決定モジュールは、一部のまたはすべてのデータセンター顧客を特定する。このステップは、図２のステップ２０２と同様である。
【００４７】
３０４において、データセンター顧客費用決定モジュールは、複数のデータセンター顧客から成る順列コレクションを選択する。３０６において、データセンター顧客費用決定モジュールは、３０４において選択されたような順列コレクションに基づいて、シャープレイ値の概算を決定する。
【００４８】
３０８において、データセンター顧客費用決定モジュールは、データセンター顧客に対して生成された概算シャープレイ値を、例えば図１のデータセンター管理モジュール１０２などのデータセンター管理インターフェースへ送る。
【００４９】
同質のデータセンター顧客から成るグループ分けを使用したデータセンター顧客費用の決定
【００５０】
一部の状況では、複数のデータセンター顧客から成る総集合「Ａ」は、サイズが「ｎｉ」の「Ｎ」個の互いに素なグループ「Ａｉ」内へ分配することができ、ここで各グループ「Ａｉ」内の複数のデータセンター顧客は、計算の目的にとって同一として扱うことができる。これは、例えばＳＬＡ契約のうちの少数のカテゴリーから顧客が選択するように、データセンターが動作している状況において生じることができる。同一のＳＬＡを共有する顧客のデータセンター資源のニーズは、一般に十分に類似しているので、各グループの複数のメンバーが、グループを代表する同一の特徴を有すると仮定することによって、システムは費用計算の概算を考慮することができる。限界費用「ｍ（Ｓ，ａ）」の計算は、「Ｓ」内の特定の顧客よりも「Ｓ」内のＳＬＡの種類にもっと感知しそうである。
【００５１】
登録が、「Ｓ」内における、各グループからのデータセンター顧客の数であるような、複数のデータセンター顧客から成る部分集合「Ｓ」が与えられたとすると、対応するベクトル「ｉ：＝（ｉ１，．．．，ｉＮ）」は、「ｉ＊」が「ｉ」のすべての登録の合計を表す（すなわち、「ｉ＊＝｜Ｓ｜」）ように、定義することができる。各グループ内の複数のデータセンター顧客が同一であるので、各グループからの同一数のデータセンター顧客を含む、任意の２つの集合「Ｓ１」および「Ｓ２」は、同一の最適な費用を有することになる。言い換えれば、「ν（Ｓ１）」、「ν（Ｓ２）」、および「ν（ｉ）」は、すべて等しい。それゆえに、限界費用も等しくなり、すなわち、「ｍ（Ｓ１，ａ）」と「ｍ（Ｓ２，ａ）」とは等しい。一般化することの損失なしに、「ａ」が、グループ「Ａ１」内にあると仮定することができる。データセンター顧客「ａ」の費用に対するシャープレイ値は、次のように表すことができる。
【００５２】
【数６】
0005890629.tif 000007
【００５３】
上述した定義では、「ｍ（ｉ，ａ）：＝ν（ｉ＋ｅ１）−ν（ｉ）」、および「ｅ１＝（１，０，．．．，０）」である。シャープレイ値の定義が、「ｍ（ｉ，ａ）」のうちの「О（ｎ１×．．．×ｎＮ）」の見積もりだけを含むことを、当業者は理解するだろう。言い換えれば、シャープレイ費用は、データセンター顧客および顧客から成る各サブグループの数に依存し、ここで各サブグループ「Ａｋ」内のすべてのデータセンター顧客は、顧客が最適化に対してそれぞれ同一のデータセンター資源ニーズおよび予約要件を示す、という点で同一である。方程式６は、限界費用を元「ａ」と関連付けて考慮し、「ａ」に対するシャープレイ値が計算されていて、「ａ」が属するグループの残りのメンバーとは異なるようにしている。言い換えれば、顧客から成る各グループは、同一の、代表的顧客によって追加されると仮定することができ、一方で「ａ」は、「ａ」が属するグループの代表とは異なることができる。
【００５４】
したがって計算の複雑性は、データセンター顧客の数において指数関数的に急増することからは削減されて、グループの数においてだけ指数関数的に急増し、典型的なデータセンターが、数百のデータセンター顧客を有することができるが、しかし５つ未満のデータセンター顧客グループを有してもよいので、通常は、計算の複雑性は著しく小さくなる。データセンター顧客費用決定モジュールによってデータセンター資源最適化モジュールへ送られようとする依頼の数も、データセンター顧客費用決定モジュールが、データセンター資源最適化モジュールへ、より少数の組み合わせで問い合わせを行うことしか必要としないので、著しく削減することができる。
【００５５】
一部の実施の形態では、複数のデータセンター顧客が一部のグループ内で同質である場合、顧客グループサイズ「ｎ：＝（ｎ１，．．．，ｎＮ）」に比例するという意味で代表的な「ｉ：＝（ｉ１，．．．，ｉＮ）」の部分集合だけを考慮することが公正であることを認識することによって、計算をさらに削減する可能性がある。理想的には「ｉ＝αｎ」であるが、これらが離散的ベクトルであるので、システムは、「ｉ」をほぼ「ｎ」に比例するように制約することができる。これは、「Ｎ」個の別個のグループから成る平衡シャフリングと呼ぶことができ、ここで各グループは、区別できない複数の元を含んでいる。平衡シャッフルでは、各プレフィックスは、グループサイズに大略比例して表される各グループを有する。平衡シャッフルを生成するのに使用することができる、いくつかの方法がある。例えば一方法では、例えばもっとも大きい差分「（ｉ＊／ｎ＊）ｎｋ−ｉｋ」を有するグループ「ｋ」のようなプレフィックス内で、もっとも少数に表された複数の顧客から成る１つのグループから、元を引くことができる。別の方法では、より少数に表されたグループを好意的に扱う確率分布に従って、元を引くことができる。
【００５６】
システムは、１つ以上の平衡シャッフルから成る集合「Ｈ」を使用し、複数の部分集合から成る構造化されたファミリーを決定して、「ａ」に対する費用を計算し、集合「Ｈ」内の各平衡シャッフル「ｈｉ」を取り込み、および「ｎ１」個のシャッフルを生成することができ、各シャッフルは、「Ａ１」の元によってすでに占有された「ｈｉ」内の異なる位置に「ａ」を配置することによって、生成することができる。これにより、シャッフル「Ｈ＊」の拡大された集合が作り出されて、因数「ｎ１」によって「Ｈ」が拡大される。複数の部分集合から成る構造化されたファミリーは、例えば順列、手順「ａ」のようなシャッフル内の複数の元である。「ａ」に対する概算シャープレイ値を計算するために、方程式５の再正規化版は、構造化された順列ファミリー「Ｈ＊」に適用することができ、または方程式３の再正規化版は、複数の部分集合から成る構造化されたファミリーに適用することができる。
【００５７】
図４は、データセンター顧客グループ分け技術を使用して、データセンター顧客費用を決定する方法４００の第１の例を図示するフローチャートである。４０２において、例えば図１のデータセンター顧客費用決定モジュール１０８などのデータセンター顧客費用決定モジュールは、複数のデータセンター顧客から成る２つ以上のグループを特定する。例えば、データセンター顧客費用決定モジュールは、複数のデータセンター顧客のデータセンター資源使用量モデルが少なくとも実質的に類似し、その結果それらが同一の代表によって置き換えることができるという点で同一の複数のデータセンター顧客を、同一のグループにグループ分けすることができる。例えば、データセンター顧客費用決定モジュールは、例えばサービス・レベル・アグリーメントが少なくとも実質的に類似しているような、同一の複数のデータセンター顧客を、同一のグループにグループ分けすることができる。図５は、データセンター顧客費用決定モジュールによって特定することができる、データセンター顧客グループ５０２および５０４の２つの集合のグラフィック表現の一例を図示する。
【００５８】
４０４において、データセンター顧客費用決定モジュールは、図５に図示されるように、データセンター顧客５０２および５０４の２つのグループ上で、両グループのデータセンター顧客を単一のグループ分け５０６内へ組み合わせることによって、シャッフル操作を実行する。
【００５９】
４０６において、データセンター顧客費用決定モジュールは、シャフリングに基づく概算ストラテジーを用いることによって、データセンター顧客に対するシャープレイ値の概算を決定する。図６は、一シャッフル内の最初のグループのすべての位置に体系的に顧客「ａ」を挿入することにより、一順列ファミリーを作り出すことによって、および例えば再正規化方程式５などの本明細書で説明される概算技術を使用することによって、１つ以上のシャッフル５０６内でデータセンター顧客「ａ」に対するシャープレイ値の概算を決定するグラフィック表現の一例を図示する。
【００６０】
４０８において、データセンター顧客費用決定モジュールは、生成された概算シャープレイ値を、例えば図１のデータセンター管理モジュール１０２などのデータセンター管理インターフェースへ送る。
【００６１】
（異質のデータセンター顧客から成るグループ分けを使用したデータセンター顧客費用の決定）
一部の状況では、複数のデータセンター顧客は、各グループ内の複数のデータセンター顧客が類似しているが同一ではないように、「Ｎ」個の互いに素なグループ「｛Ａｉ｝」内へグループ分けすることができる。一グループ内の複数のデータセンター顧客が十分に類似している場合、データセンター顧客費用決定モジュールは、「Ｎ」個の同質のグループによって、システムを簡単に概算することができ、これらの同質のグループにおいて各グループは、元（もと）のグループ内の実際に同一でないデータセンター顧客の平均に等しい、同一のデータセンター顧客を有している。「理にかなった類似点」は、相当数の種々のやり方で決定することができる。例えば、１０のデータセンター顧客から成るグループなどの一定数のデータセンター顧客のテストテンプレートは、テストテンプレートに対して、新たなデータセンター顧客の限界費用または全シャープレイ費用を、テストテンプレートの費用と比較することによって、新たなデータセンター顧客をテストするのに使用することができる。
【００６２】
しかしながら、各グループ内の複数のデータセンター顧客が十分に異なる場合、分配「Ａ１」内にデータセンター顧客「ａ」に対するシャープレイ値の定義を次のように記述することができる。
【００６３】
【数７】
0005890629.tif 000008
【００６４】
次いで、データセンター顧客費用決定モジュールは、ランダム化されたアプローチを使用して、集合「Ｓ」を選択することができる。次の正規化因数：
【数８】
0005890629.tif 000009
は、概算で使用される、サイズが「ｉ」のサンプル集合の実際の数に適応することができる。ランダムサンプルは、各サイズ「ｉ」について選択されたサンプル集合の数に適応することによって、改善することができる。サンプルは、各グループから選択された数が、各グループのサイズを比例的に代表している場合、例えば「｜Ｓ１｜〜｜Ａ１−１｜｜Ｓ｜／（｜Ａ｜−１）」および「ｋ＞１に対して、｜Ｓｋ｜〜｜Ａｋ｜｜Ｓ｜／（｜Ａ｜−１）」である場合、集合「Ｓ」を選択することによっても、改善することができる。
【００６５】
別のアプローチでは、上述した平衡シャフリングアプローチを、上述した順列から成る構造化されたファミリーと組み合わせることができる。１つ以上の平衡シャッフルは、図８に図示されるように、順列内に各グループの位置を決定するのに使用することができる。次いで各平衡シャッフルに対して、顧客グループの順列から成る構造化されたファミリーは、より大きいシャッフル内のグループ位置内に、個々のグループメンバーの位置を決定するのに使用することができる。
【００６６】
図７は、データセンター顧客グループ分け技術を使用して、データセンター顧客費用を決定する方法７００の第２の例を図示するフローチャートであり、図８は、図７に図示されたデータセンター顧客費用決定方法に関連して実行される、データセンター顧客グループ８０２から成る部分集合コレクションのシャッフルのグラフィック表現の一例を図示する。
【００６７】
７０２において、例えば図１のデータセンター顧客費用決定モジュール１０８などのデータセンター顧客費用決定モジュールは、２つのデータセンター顧客グループを特定する。
【００６８】
７０４において、データセンター顧客費用決定モジュールは、複数のデータセンター顧客から成る２つのグループ上で、両グループのデータセンター顧客を単一のグループ分け８０２内へ組み合わせることよって、シャッフル順列操作を実行する。
【００６９】
７０６において、データセンター顧客費用決定モジュールは、シャッフル８０４に属する複数のグループ内の順列と組み合わせられた１つ以上の平衡シャッフル８０２を使用して、データセンター顧客に対するシャープレイ値の概算を決定する。その結果としてもたらされる順列コレクションは、再正規化された方程式５を使用して、または部分集合コレクションを作り出す方程式４を使用しておよび再正規化方程式７を使用して、シャープレイ値を概算するのに使用することができる。
【００７０】
７０８において、データセンター顧客費用決定モジュールは、データセンター顧客に対して生成された概算シャープレイ値を、例えば図１のデータセンター管理モジュール１０２などのデータセンター管理インターフェースへ送る。
【００７１】
次の説明は、本開示技術の一部の実施の形態を実装することができる適切なマシンについての、簡潔で一般的な説明を提供するように意図されている。本明細書では、用語「マシン」は、通信可能なように結合されるとともにいっしょに動作するマシンもしくは装置から成る、単一のマシンまたはシステムを広く包含するように意図される。典型的なマシンは、パーソナルコンピュータ、ワークステーション、サーバ、ポータブルコンピュータ、携帯用装置、タブレット装置、および同類のものなどのコンピューティング装置を含むことができる。
【００７２】
典型的には、マシンはシステムバスを含み、このシステムバスには、プロセッサ、メモリ（例えば、ランダム・アクセス・メモリ（ＲＡＭ）、リード・オンリー・メモリ（ＲＯＭ）、および他の状態保存媒体）、記憶装置、ビデオインターフェース、および入出力インターフェースポートを取り付けることができる。マシンはエンベデッドコントローラーも含むことができ、このエンベデッドコントローラーには、プログラム可能もしくはプログラム可能でないロジックデバイスまたはロジックアレイ、アプリケーション特定集積回路（ＡＳＩＣ）、エンベデッド（組み込み）コンピュータ、スマートカード、および同類のものなどがある。マシンは、従来の入力装置（例えば、キーボードおよびマウス）からの入力によって、および別のマシンから受ける指示、バーチャルリアリティ（ＶＲ）環境とのやり取り、生体フィードバック、または他の入力信号によって、少なくとも部分的に制御することができる。
【００７３】
マシンは、ネットワークインターフェース、モデム、または他の通信結合を通じて、１つ以上の遠隔マシンへの１つ以上の接続を利用することができる。マシンは、イントラネット、インターネット、ローカル・エリア・ネットワーク、広域ネットワークなどの、物理的および／または論理的なネットワーク経由で、相互接続することができる。ネットワーク通信が、種々の有線および／または無線の、短距離用または長距離用の搬送波およびプロトコルであって、無線周波数（ＲＦ）、衛星、マイクロ波、米国電気電子学会（ＩＥＥＥ＝アイ・トリプル・イー）５４５．１１、ブルートゥース（Ｂｌｕｅｔｏｏｔｈ：登録商標）、可視光、赤外線、ケーブル、レーザなどを含む、搬送波およびプロトコルを利用することができることを、当業者は理解するだろう。
【００７４】
本開示技術の実施の形態は、関数、手続き、データ構造、アプリケーションプログラム、命令などを含む関連データであって、マシンによってアクセスされると、マシンがタスクを実行し、または抽象データ型もしくは低レベルのハードウェアコンテキストを定義することができるようになる、データを参照することによりまたはデータと連動して、説明することができる。関連データは、例えば、揮発性および／もしくは不揮発性メモリ（例えば、ＲＡＭおよびＲＯＭ）または他の記憶装置および関連した記憶媒体内に記憶することができ、これらの記憶装置および記憶媒体は、ハードディスク、フロッピーディスク、光学ストレージ、テープ、フラッシュメモリ、メモリスティック（登録商標）、デジタル・ビデオ・ディスク、生物学的ストレージ、および他の有形の物理的記憶媒体を含むことができる、
【００７５】
関連データは、パケット、シリアルデータ、パラレルデータ、伝搬信号などの形をした物理的および／または論理的ネットワークを含む伝送環境を通じて配信することができ、圧縮または暗号化されたフォーマットで使用することができる。関連データは、分散環境で使用することができ、マシンのアクセスのために、ローカルでおよび／または遠隔的に記憶することができる。
【００７６】
上述のように開示されたおよび他の種々の特徴ならびに機能、またはこれらの代替策は、所望のように多くの他の異なるシステムまたは応用例へと組み合わせられてもよいことが、理解されるだろう。上述した実施の形態について、現在は予見もしくは予想されない種々の代替策、修正例、変形例、または改善策が、当業者によって引き続いて形成することができるが、これらもまた、次の請求項によって包含されるように意図されている。
【図１】
0005890629.tif 000012
【図２】
0005890629.tif 000013
【図３】
0005890629.tif 000014
【図４】
0005890629.tif 000015
【図５】
0005890629.tif 000016
【図６】
0005890629.tif 000017
【図７】
0005890629.tif 000018
【図８】
0005890629.tif 000019