(57)【要約】  クラウドコンピューティングネットワークで、データセンタの負荷を他の複数のデータセンタサイトへ再割り当てするための方法。負荷は、各データセンタサイトでのクラウドコンピューティングネットワークのパフォーマンス特性を定義する目的関数の導関数に基づいて、再割り当てされる。この方法では、１組の他のデータセンタサイトのそれぞれの導関数を求め、求めた導関数に基づいて、１組のデータセンタサイトの組の中で、目的関数の増加が最小になるデータセンタサイトを特定し、求めた導関数および特定した他のデータセンタサイトに基づいて、当該データセンタサイトおよび他の複数のデータセンタサイトの間で負荷を再割り当てする。
2015501991.tif 000002
【特許請求の範囲】
【請求項１】
クラウドコンピューティングネットワーク内で、各データセンタサイトでのクラウドコンピューティングネットワークのパフォーマンス特性を定義する目的関数および目的関数の導関数を使用して、データセンタサイトから他のデータセンタサイトに負荷を再割り当てするための方法であって、
１組の他のデータセンタサイトのそれぞれについて導関数を求めるステップと、
求めた導関数に基づいて、１組の適格なデータセンタサイトの中で、負荷の割り当て分が増加したときに目的関数への影響が最小になるデータセンタサイトを特定するステップと、
求めた導関数および特定した他のデータセンタサイトに基づいて、データセンタサイトおよび他のデータセンタサイトの間に負荷を再割り当てするステップと
を含む、方法。
【請求項２】
クラウドコンピューティングネットワーク内で、各データセンタサイトでのクラウドコンピューティングネットワークのパフォーマンス特性を定義する目的関数および目的関数の導関数を使用して、データセンタサイトで他のデータセンタサイトに負荷を再割り当てするための方法であって、
１組の他のデータセンタサイトのそれぞれについて導関数を求めるステップと、
求めた導関数に基づいて、１組の適格なデータセンタサイトの中で、負荷の割り当て分が減少したときに目的関数の改善が最大になるデータセンタサイトを特定するステップと、
求めた導関数および特定した他のデータセンタサイトに基づいて、データセンタサイトと他のデータセンタサイトの間に負荷を再割り当てするステップと
を含む、方法。
【請求項３】
負荷を再割り当てした後に、再割り当てが再割り当ての解に収束したかどうか判定するステップをさらに含む、請求項１および２のいずれかに記載の方法。
【請求項４】
再割り当てが再割り当ての解に収束していない場合に、導関数を求めるステップ、データセンタサイトを特定するステップ、負荷を再割り当てするステップおよび再割り当てが収束したかどうか判定するステップを繰り返す、請求項１から３のいずれかに記載の方法。
【請求項５】
再割り当てが再割り当ての解に収束したかどうか判定するステップが、
特定したデータセンタサイトの導関数と他のデータセンタサイトのそれぞれの導関数との間の複数の差を計算するステップと、
複数の差のそれぞれが閾値より小さいかどうか判定するステップと
を含む、請求項１から３のいずれかに記載の方法。
【請求項６】
データセンタサイトが遅延または稼働率の変化を検出した場合に、導関数を求めるステップ、データセンタサイトを特定するステップ、負荷を再割り当てするステップおよび再割り当てが収束したかどうか判定するステップを繰り返す、請求項１から５のいずれかに記載の方法。
【請求項７】
再割り当て行列が、データセンタサイトと他のデータセンタサイトとの間での負荷の再割り当てを定義し、
負荷を再割り当てするステップが、再割り当て調節行列を計算するステップと、再割り当て行列と再割り当て調節行列を合計するステップとを含む、
請求項１から６のいずれかに記載の方法。
【請求項８】
導関数を求めるステップが、
１組の他のデータセンタサイトのそれぞれから、負荷パラメータを受信するステップと、
１組の他のデータセンタサイトのそれぞれから、サービス率パラメータを受信するステップと、
他のデータセンタサイトのそれぞれについて、データセンタサイトと他のデータセンタサイトのそれぞれとの間の遅延を定義する遅延パラメータを受信するステップとを含み、求められる導関数が、負荷パラメータ、サービス率パラメータおよび遅延パラメータに基づく、
請求項１から７のいずれかに記載の方法。
【請求項９】
データセンタサイトと他のデータセンタサイトとの間での負荷の再割り当てを定義する、初期再割り当て行列を計算するステップをさらに含む、請求項１から８のいずれかに記載の方法。
【請求項１０】
１組の他のデータセンタサイトが、
データセンタサイトから指定の距離の範囲内にある、すべての他のデータセンタサイト、
データセンタサイトの近隣サイトである、すべての他のデータセンタサイト、
ネットワークポリシにより特定される、すべての他のデータセンタサイト、および
すべての他のデータセンタサイト
のうちいずれか１つである、請求項１から９に記載の方法。
【請求項１１】
クラウドコンピューティングネットワーク内で、各データセンタサイトでのクラウドコンピューティングネットワークのパフォーマンス特性を定義する目的関数および目的関数の導関数を使用して、データセンタサイトから他のデータセンタサイトに負荷を再割り当てするための方法であって、
データセンタサイトが過負荷であるかどうか判定するステップであって、
データセンタサイトが過負荷な場合は、続いて、
１組の他のデータセンタサイトのそれぞれについて導関数を求めるステップと、
求めた導関数に基づいて、１組の適格なデータセンタサイトの中で、負荷の割り当て分が減少したときに目的関数の改善が最大になるデータセンタサイトを特定するステップと、
求めた導関数および特定した他のデータセンタサイトに基づいて、データセンタサイトと他のデータセンタサイトの間に負荷を再割り当てするステップとを行い、
データセンタサイトが過負荷でない場合は、続いて、
１組の他のデータセンタサイトのそれぞれについて導関数を求めるステップと、
求めた導関数に基づいて、１組の適格なデータセンタサイトの中で、負荷の割り当て分が増加したときに目的関数への影響が最小になるデータセンタサイトを特定するステップと、
求めた導関数および特定した他のデータセンタサイトに基づいて、データセンタサイトと他のデータセンタサイトの間に負荷を再割り当てするステップとを行う、
判定するステップを含む、方法。
【請求項１２】
データセンタサイトが過負荷でない場合の後続のステップを行う前に、データセンタサイトが過負荷かどうか再度判定するステップをさらに含む、請求項１１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に開示される様々な例示的実施形態は、一般に、地理的に分散されたデータセンタでのレイテンシ短縮および弾力性改善のための最適化機構に関する。
【背景技術】
【０００２】
クラウドコンピューティングとは、コストを削減するために、コンピューティングインフラストラクチャ（サーバ、ストレージおよびシステムソフトウェアなど）の場所を、ネットワーク内の設備に移動するというパラダイムである。サービスはインターネット越しに、または一般的には、他の任意のネットワーク越しに、エンドユーザに提供される。コンピューティングインフラストラクチャを管理する設備は、通常、データセンタといい、クラウドとも呼ばれる。データセンタの利点は、予期せぬ事象のもとにおいても、瞬間的なトラフィック需要に効率的に応答し得るように、コンピューティング資源を大規模に貯蔵し得ることである。弾力性とは、あるユーザのために、リソース（例えば、サーバの数）を、トラフィック負荷に合わせて拡大または縮小する、クラウドプロバイダの能力を説明するために、通常、使用される用語である。エンドユーザに動的に割り当てられる資源は、従量課金モデルにおいて提案され得るので、ユーザの関心は、設備費用ではなく、主として運用費用に向けられ得る。
【０００３】
現在の有力なクラウドプロバイダの例には、Ａｍａｚｏｎ  ＥＣ２、Ｍｉｃｒｏｓｏｆｔ  Ａｚｕｒｅおよび  Ｇｏｏｇｌｅ  Ａｐｐ  Ｅｎｇｉｎｅが含まれる。詳細なデータは公開されていないが、これらのクラウドは普通、異なったサイトに位置する、いくつかの大規模なデータセンタから成る。広い地理的領域（国）全体に散在するいくつかの場所をもつ、このようなデータセンタは、集中型データセンタと呼ばれ得る。通常の配備では、各データセンタは数万またはそれ以上のサーバを管理し得る。これらの集中型データセンタは、統計的多重化を通して、弾力性を達成し、容量が無尽蔵であるかのような知覚を提供し得る。大規模なデータセンタは、ごくわずかしか存在しないので、そのすべてをエンドユーザの近くに置くことはできない。その結果、データセンタから遠く離れた場所にいるユーザは、受け容れ難い遅延を経験することになり得る。多くの、より小規模なデータセンタ（１サイトあたり数千またはそれ未満のサーバ）では、サイトはエンドユーザの非常に近くに置かれ得る。しかし、クラウドプロバイダが予測できない需要の急増が発生したときに、小規模なデータセンタでは、適切なプロビジョニングが不可能であるか、または費用がかかり過ぎ得る。
【発明の概要】
【課題を解決するための手段】
【０００４】
したがって、電話会社および他の類似サービスプロバイダは、既存のインフラストラクチャを使用してクラウドコンピューティングを提供し得るので、電話会社の環境に適した新しいタイプのクラウドコンピューティングシステムを構築するための技法および方法を開発し得る。電話会社および他の類似サービスプロバイダは、「ラストワンマイル」という強みをもち得る。従来のクラウドコンピューティングプロバイダと異なり、電話会社は、数千の中央局（ＣＯ）の多量の不動産を利用して、コンピューティングインフラストラクチャを管理することができる。電話会社のもう１つの強みとして、電話会社は「ラストワンマイル」を所有してもおり、したがって、レイテンシが小さいことが要求されるミッションクリティカルなサービスの提案において、非常に有利であることがあり得る。
【０００５】
さらに、電話会社ベースのクラウドコンピューティングは、低費用な構築によって実装し得る。研究により、ＣＯの様々な構成要素の消費電力が調査されている。これらの研究では、クラス５のＴＤＭ電話交換機が、ＣＯでの消費電力に最も寄与し、機器消費電力全体の４３％を占めることが示されている。これらの交換機はまた、かさが高く、ＣＯの広い面積をとる傾向にある。通常のＣＯの１台の電話交換機の消費電力は、５３ＫＷと概算される。サーバの消費電力が平均で１００Ｗ程度なら、この消費電力は、約５００台のサーバを管理することに等しい。携帯電話の普及が、地上通信電話の衰退に莫大な影響を及ぼしたことは、よく知られている。２００９年１２月時点でのＮａｔｉｏｎａｌ  Ｃｅｎｔｅｒ  ｆｏｒ  Ｈｅａｌｔｈ  Ｓｔａｔｉｓｔｉｃｓ（国立健康統計センタ）のデータによれば、米国人の４人に１人が地上通信電話を手放している。その結果、結局は電話交換機は廃止されてサーバに置き換えられ、ＣＯは、小規模または中規模のデータセンタとしても機能するように変容させられ得ると思われる。
【０００６】
したがって、分散型データセンタは、各データセンタサイトが近くのエンドユーザにサービスを提供し得るので、非常に魅力的な電話会社クラウドソリューションを提供すると思われる。残念なことに、サーバの数が少ないこのようなデータセンタは、大規模なクラウドコンピューティングシステムのような弾力性をもたないことがあり得る。したがって、負荷の再割り当てを伴う分散型データセンタの必要性が残る。あるデータセンタが、ローカルで処理できるより多くの需要を受け取った場合、システムは需要の割り当て分を、１つまたは複数のリモートデータセンタに再割り当てし得る。リモートデータセンタにより処理されるジョブでは、ローカルデータセンタとリモートデータセンタとの間に余分な往復時間が発生することがあるので、システムは、レイテンシ（エンドユーザが知覚する応答時間）を最小化するか、または他の望ましいパフォーマンス特性を得るために、リモートデータセンタの適切な場所の選択も行い得る。
【０００７】
下記に様々な例示的実施形態の簡単な概要を示す。下記の概要では、多少の簡素化および省略がなされている場合があるが、これは、様々な例示的実施形態のいくつかの態様を強調および紹介することが目的であって、本発明の範囲を制限することが目的ではない。当業者が発明概念を構想および使用することができるために十分な、好ましい例示的実施形態の詳細を下記に記載する。
【０００８】
様々な例示的実施形態は、クラウドコンピューティングネットワークで、各データセンタサイトでのクラウドコンピューティングネットワークのパフォーマンス特性を定義する目的関数および目的関数の導関数を使用して、データセンタサイトから他のデータセンタサイトに負荷を再割り当てするための方法に関し、この方法は、１組の他のデータセンタサイトのそれぞれの導関数を求めるステップと、求めた導関数に基づいて、１組の適格なデータセンタサイトの中で、負荷の割り当て分が増加したときに目的関数への影響が最小になるデータセンタサイトを特定するステップと、求めた導関数および特定した他のデータセンタサイトに基づいて、データセンタサイトおよび他のデータセンタサイトの間に負荷を再割り当てするステップとを含む。適格なデータセンタサイト（あるサイトに負荷を送ること、またはあるサイトから負荷を受け取ることを許可されているサイト）は、（１）すべてのサイト、（２）１組の近隣サイト、（３）あらかじめ構成されている１組のサイト、または（４）分散型の方法によって動的に決定される１組のサイトを含むことができる。
【０００９】
様々な例示的実施形態は、クラウドコンピューティングネットワークで、各データセンタサイトでのクラウドコンピューティングネットワークのパフォーマンス特性を定義する目的関数および目的関数の導関数を使用して、データセンタサイトから他のデータセンタサイトに負荷を再割り当てするための方法に関し、この方法は、１組の他のデータセンタサイトのそれぞれの導関数を求めるステップと、求めた導関数に基づいて、１組の適格なデータセンタサイトの中で、負荷の割り当て分が減少したときに目的関数の改善が最大になるデータセンタサイトを特定するステップと、求めた導関数および特定した他のデータセンタサイトに基づいて、データセンタサイトおよび他のデータセンタサイトの間に負荷を再割り当てするステップとを含む。
【００１０】
様々な例示的実施形態は、クラウドコンピューティングネットワークで、各データセンタサイトでのクラウドコンピューティングネットワークのパフォーマンス特性を定義する目的関数および目的関数の導関数を使用して、データセンタサイトから他のデータセンタサイトに負荷を再割り当てするための方法に関し、この方法は、データセンタサイトが過負荷であるかどうか判定すること、および、データセンタサイトが過負荷である場合は、続いて、１組の他のデータセンタサイトのそれぞれについて導関数を求めるステップと、求めた導関数に基づいて、１組の適格なデータセンタサイトの中で、負荷の割り当て分が減少したときに目的関数の改善が最大になるデータセンタサイトを特定するステップと、求めた導関数および特定した他のデータセンタサイトに基づいて、データセンタサイトと他のデータセンタサイトの間に負荷を再割り当てするステップとを行い、データセンタサイトが過負荷でない場合は、続いて、１組の他のデータセンタサイトのそれぞれについて導関数を求めるステップと、求めた導関数に基づいて、１組の適格なデータセンタサイトの中で、負荷の割り当て分が増加したときに目的関数への影響が最小になるデータセンタサイトを特定するステップと、求めた導関数および特定した他のデータセンタサイトに基づいて、データセンタサイトと他のデータセンタサイトの間に負荷を再割り当てするステップとを行うことを含む。
【００１１】
様々な例示的実施形態をよりよく理解するために、添付図面を参照する。
【図面の簡単な説明】
【００１２】
【図１】５つのデータセンタをもつクラウドシステムを示す図である。
【図２】５つのデータセンタをもつクラウドシステムを示す図である。
【図３】別の例のデータセンタトポロジを示す図である。
【図４】３つの代替案についての、稼働率に対する正規化された遅延のグラフを示す図である。
【図５】負荷の変動がある各試行での、３つの代替案の遅延を示す図である。
【図６】上記の方法の動作を示すフローチャートである。
【図７】式（１）に示される目的関数を最適化する方法の、別の実施形態の動作を示すフローチャートである。
【発明を実施するための形態】
【００１３】
理解を容易にするために、同一の参照番号は、ほぼ同じまたは類似した構造、および／もしくは、ほぼ同じまたは類似した機能をもつ要素を示すために使用され得る。
【００１４】
データセンタで、ジョブは、それぞれのアプリケーションに従って異なった処理を施される。一般に、アプリケーションは、資源要件の観点から、（１）処理集約型、（２）帯域幅集約型、または（３）ストレージ集約型として分類され得る。コンテンツ配信は、帯域幅集約型とストレージ集約型の両方であるアプリケーションの例である。インターネット検索は、処理集約型とストレージ集約型の両方であるアプリケーションの例である。コントロールプレーンに見られる電話会社のサービスは、通常、処理集約型である。下記の実施形態では、処理集約型のアプリケーションに注目する。各データセンタｉ（ｉ＝１，．．．Ｎ）が、単位時間ごとに種類ｋのジョブをエンドユーザから受信するとして、ある目的関数を最適化するためにローカルおよびリモートで処理されるべきジョブの割り当て分が決定され得る。異なるアプリケーションには、ユーザとクラウドプロバイダとの間のサービス水準契約（ＳＬＡ）によって、異なる測定基準が伴い得る。レイテンシは、ユーザ経験に影響する重要な測定基準であり得、また、広く文献で考察されてきた。各データセンタの負荷は比較的静的であり、最適化問題の解決にあたるエンティティはその負荷を知っていると仮定され得る。下記には、加重平均遅延を最小化することに向けて、特定の目的関数が記載されているが、１つまたは複数の、なんらかの望ましいパフォーマンス測定基準を最小化または最大化するために、別の目的関数が使用され得る。
【００１５】
問題は、凸な目的関数をもつ非線形プログラムとして提起され得る。決定変数すなわち再割り当て行列
【００１６】
【数１】
2015501991.tif 000003
は、サイトｉからサイトｊに再割り当てされる、種類ｋのジョブの負荷の割り当て分を示す。ジョブは、ローカルデータセンタまたはリモートデータセンタのどちらかでその全体を処理され得ると仮定される。ジョブがリモートデータセンタで処理される場合は、２つのサイトｉとｊとの間に、ジョブを提出して応答を得るための往復遅延が余分に存在し得、τｉ，ｊと表される。加重平均遅延を最小化する最適化問題は、以下のとおりに定義され得る。
【００１７】
【数２】
2015501991.tif 000004
なお、
【００１８】
【数３】
2015501991.tif 000005
【００１９】
【数４】
2015501991.tif 000006
【００２０】
【数５】
2015501991.tif 000007
となるようにし、ここで、
【００２１】
【数６】
2015501991.tif 000008
【００２２】
【数７】
2015501991.tif 000009
【００２３】
【数８】
2015501991.tif 000010
【００２４】
【数９】
2015501991.tif 000011
である。
【００２５】
制約条件（２）は、再割り当てされる負荷の割り当て分は負の値であってはならないという必要条件を反映し、制約条件（３）は、あるサイトｉからすべてのサイト（それ自体を含む）への再割り当ての割り当て分の合計は１でなければならないという当然な条件を示す。制約条件（４）は、過負荷を防ぐために、サイトｊの稼働率は、小さな値ε＞０について、１−εを越えてはならないことを規定する。
【００２６】
【数１０】
2015501991.tif 000012
を、サイトｉに接続されているエンドユーザからの外来の種類ｋのジョブ到着率（負荷とも呼ばれる）の合計とする。式（５）は、これに対応するサイトｉの正規化された到着率を、すべてのサイトの外来のジョブ到着率の合計に対するサイトｉの外来のジョブ到着率の合計の比率として定義する。式（６）は、サイトｊで処理されるジョブの到着率の合計を定義する。これは、サイトｊに接続されているエンドユーザから送られたジョブおよび他のサイトから再割り当てされたジョブに相当する。式（７）はサイトｊの稼働率を定義し、ここで、βｋはサーバでの種類ｋのジョブの１つの平均処理時間であり、Ｋｊはサイトｊのサーバの数である。式（８）は、複数サーバ近似および単一サーバ近似についての、サイトｊでの種類ｋのジョブの平均処理遅延を定義する。この式では、ジョブ到着過程はポアソン過程であると仮定されている。一般に、式（８）はρｊの任意の凸関数で十分である。複数サーバ近似では、各サーバが合計負荷の１／Ｋｊの割り当て分を受け取るように、到着するジョブは、Ｋｊ台のすべてのサーバ間で完全に負荷均衡されるものと仮定される。各サーバで、異なる種類のジョブの間にプロセッサ共有スケジューラが仮定される。単一サーバ近似では、ジョブをサービスするためのスピードアップ係数Ｋｊを提供する。これを使用して、均等なタスクに分割され、データセンタ内の利用可能なサーバ間で並列に処理され得るジョブがモデル化され得る。
【００２７】
式（１）の最適化を目指すことは、複数のサイトで効率的に資源を管理し得るネットワーク運用システムにつながり得る。システムの重要な任務は、ジョブ到着率の測定値を収集し、サービス要件を概算することである。これらの測定値は、負荷のゆらぎに応じた適切な期間の各インターバルの中で更新される。集中型のコンピューテーションエンティティにともなって、測定値情報を集め、各インターバルの中で最適化方法を実行して、動的に負荷を再割り当てする中心的な場所があり得る。代替案として、分散型の方法を使用して負荷の再割り当てを行うことがあり得る。この場合、各サイトが、そのサイト自体にとって有用な測定情報を収集し得る。
【００２８】
図１および図２は、５つのデータセンタをもつクラウドシステムを示す。下記に、負荷の再割り当てのない分散型データセンタ（図１）および負荷の再割り当てのある分散型データセンタ（図２）の２種類の例を記載する。図１は、５つのデータセンタをもつクラウドプロバイダならびに、それらの相互接続および関連する往復遅延（時間単位で）を示す。明確にするため、ジョブの種類は１つであり、各サイトは、時間単位あたり３ジョブの率でジョブを処理できるサーバを１台もつと仮定する。さらに、各サイトｉ（ｉ＝１，２，３，４，５）の外来ジョブの到着率は、時間単位あたり｛λ｝＝（２，１．５，１，１．５，２）ジョブとして与えられると仮定する。
【００２９】
表１は、負荷の再割り当てがない場合の、各サイトｉのジョブ到着率λｉおよび平均サービス率μｉのパラメータ値を示す。すべてのジョブはそれぞれのデータセンタでローカルに処理されるので、負荷を再割り当てするための余分な伝送遅延はなく、τ＝０である。各サイトの平均遅延（ユーザが経験する応答時間）は、最後の列に与えられる。この例では、加重平均遅延は、０．８１２５時間単位である。
【００３０】
【表１】
2015501991.tif 000013
【００３１】
図２は、負荷の再割り当てのある、別の分散型データセンタの例を示す。表２は、パラメータ値と、それに対応する伝送遅延（τ）および全遅延を示す。サイト２、３および４に到着するジョブはそのローカルデータセンタで処理され、サイト１および５に到着するジョブはそのローカルサイトとリモートサイト３との間で分割されることに注目されたい。具体的には、サイト１からの負荷の割り当て分θ１，３＝０．００９３がサイト３に再割り当てされ（再割り当てされる負荷はλ１θ１，３＝０．１８６）、残りはサイト１でローカルに処理される。その結果、サイト１での処理遅延は、第１の例（負荷の再割り当てなし）より減少されて０．８４３２（負荷の再割り当てあり）になる。サイト３は、サイト１および５からの余分のジョブを処理するので、サイト３の処理遅延は、０．５から０．６１４３に増加する。他のサイト２および４は、影響を受けない。負荷の再割り当てがある場合の加重平均遅延は、０．７８４２時間単位であり、これは負荷の再割り当てのない例よりも改善されている。
【００３２】
【表２】
2015501991.tif 000014
【００３３】
下記で、異なるクラウド代替案の別の例でのパフォーマンスを求める。図３は、この別例のデータセンタトポロジを示す。２つのサイト間の平均往復遅延が、ある時間単位の数として示される。集中型クラウドでは、データセンタの場所はＣＨ１にあると仮定される。この場所は、伝送遅延が処理遅延より支配的である場合に、集中型クラウドの最小の加重平均遅延を与える。図３には、３２のデータセンタサイトおよび４４のデータセンタ間相互接続がある。各リンク（ｉ，ｊ）は、そのτｉ，ｊと関連付けられている。
【００３４】
この例では、（１）サーバが１つのサイトに位置する集中型データセンタ、（２）負荷の再割り当てのない分散型データセンタ、および（３）負荷の再割り当てのある分散型データセンタの３つの代替案が比較される。ジョブの種類は１つであり、平均ジョブサービス時間はβ＝１時間単位で、サーバの数は、すべてのｊについてＫｊ＝Ｋであると仮定される。集中型データセンタでは、サーバの数はＮＫで、Ｎ＝３２である。ここでは、評価において、複数サーバ近似を使用する。
【００３５】
図４は、３つの代替案の、稼働率に対する正規化された遅延のグラフを示す。図４から、ジョブの到着率およびサーバの数が一様である場合は、分散型データベースのパフォーマンスは、負荷の再割り当てがあるものもないものも同じであること、つまり、すべてのｉについて、λｉ＝λ、Ｋ＿i＝Ｋであることが容易に推定される。より現実的な非一様の負荷パターンで実験するには、半数のサイトで到着率を小さくして、他の半数で到着率を同じだけ大きくした簡単な負荷パターンが採用され得る。この動機づけは、合計到着率を確かに同じなままになるようにすることである（サイトの数は偶数と仮定する）。例えば、ｉが奇数ならλｉ＝（１＋δ）λ、ｉが偶数ならλｉ＝（１−δ）λである。
【００３６】
負荷の再割り当てのない分散型データベースでは、Ｋｊ＝Ｋかつβ＝１のとき、サイトｊの稼働率は、ρｊ＝λｊβ／Ｋｊ＝λｊ／Ｋである。したがって、負荷が非一様な場合は、異なるサイトの稼働率は変動し得る。負荷の再割り当てがある場合は、サイトｊの稼働率は、式（７）で与えられる。負荷の再割り当てでは加重遅延の最小化を試みるが、異なるサイトの稼働率はほぼ公平に均衡化される。集中型のデータセンタでは、合計到着率は
【００３７】
【数１１】
2015501991.tif 000015
で、合計サービス率は、Ｋｊ＝Ｋかつβ＝１のとき、
【００３８】
【数１２】
2015501991.tif 000016
である。集中型データセンタの稼働率は、λ／Ｋである。すなわち、合計負荷が同じであれば、異なるサイトでの負荷の変動は、集中型サーバの稼働率に影響しない場合がある。
【００３９】
図４は、負荷が非一様（δ＝０．５）な場合の、λの変動に対する加重平均遅延を、３つの代替案について比較したものである。見やすくするために、Ｘ軸の、集中型データセンタの稼働率ρ＝λ／Ｋは、Ｋに依存しない無次元数となるように使用され得る。一般に信じられているように、分散型データセンタは、一般に、エンドユーザの近くにあることから、集中型データセンタよりも小さい遅延を達成できる。集中型の方が有利になるのは、稼働率が非常に高く、処理遅延がサイト間の伝送遅延より支配的な場合のみである。興味深いことに、非常に稼働率が高い場合でも、負荷の再割り当てのある分散型データセンタは、集中型よりも小さい遅延を達成し得ることに注目されたい。一方、負荷の再割り当てのない分散型データセンタは、非常に急速に遅延が無限になるので、パフォーマンスが非常に劣る。
【００４０】
クラウドコンピューティングの最も魅力的な強みの１つは、資源を動的に増減して、クラウドリソースが無尽蔵であるようにユーザに思わせることができることである。弾力性は、明らかに、データセンタ内に多くのサーバを配備するほど改善される。集中型データセンタに多数のサーバを配備することは一般的であり得るが、分散型データセンタでは、サイトの数が多いために、経済的ではなくなり得る。さらに、通常のＣＯに位置する電話会社のデータセンタでは、電力および不動産の制約により、一般に、多数のサーバの配備は不可能である。
【００４１】
３つの代替案の弾力性を評価するために、以下の実験を行う。各試行で、負荷λｉは、［λｍｉｎ，λｍａｘ］上の一様分布に従って、各サイトｉについて独立に生成され得る。各サイトの負荷が生成された後に、ある稼働率について負荷の大きさが変更され得る。
【００４２】
図５は、負荷が変動するとき（λｍｉｎ＝０、λｍａｘ＝１．５）の、各試行における、３つの代替案の遅延を示す。負荷の再割り当てのある分散型データセンタでは、遅延に関して一定のユーザ経験を維持し得るが、他の代替案では、遅延の大きなゆらぎを経験する。集中型データセンタでは、データセンタから遠く離れたサイトでの大きな需要が全遅延に著しく寄与し得るので、大きなゆらぎが経験され得る。負荷の再割り当てのない分散型データセンタでは、ジョブ到着率がサイトのサービス処理容量を超えるときに、偶発的な過負荷の影響を受け得るので、弾力性を提供し得ない。
【００４３】
任意の通常のネットワークで負荷の再割り当てを最適化するために、集中型の方法を使用することが困難であることは、多数のデータセンタのためにネットワークを最適化するには多量の処理が必要なこと、および最適化を行うために各データセンタから情報を収集する必要があることから証明され得る。したがって、他のデータセンタから最小量の情報を使用してデータセンタに実装される、分散型の方法が有益であろう。
【００４４】
式（１）から（８）に概要を示した最適化問題、すなわち、最適な負荷の再割り当ての割り当て分
【００４５】
【数１３】
2015501991.tif 000017
を求める問題を解くための分散型の方法を、次に記載する。便宜上、ジョブの種類がただ１つである場合について記載し、上付き文字ｋは省略するが、この方法は、複数種類のジョブの場合に簡単に拡張できる。実行可能解が確実に存在するように、
【００４６】
【数１４】
2015501991.tif 000018
と仮定し得る。
【００４７】
一般に、この方法は、各データセンタで実行される分散型の方法を使用して、目的関数を最大化または最小化することを目指す。この例では、最小化される目的関数は加重平均遅延である。様々なパラメータに基づく他の目的関数もまた、使用され得る。
【００４８】
一実施形態では、この方法の高度な動作が下記のように記載され得る。各繰り返しにおいて、各サイトｉは、追加の無限小の負荷割り当て分を任意のサイトｊ（サイトｉ自体を含み、これは、サイトｉ自体により多くの負荷を保持することを意味する）に送ると、大域的な目的関数（加重平均遅延）内の増加δｉ，ｊがどれだけになるかを計算し得る。次に、各サイトｉは、大域的な目的関数内の増加が最小になるのは、どのサイトｊかを判定し得る。これを、例えばｊｍｉｎ（ｉ）とする。次に、サイトｉは、ｊｍｉｎ（ｉ）以外のすべてのサイトに再割り当てする負荷割り当て分を、δｉ，ｊに比例し得る「小さな」量だけ減少させ、同時に、サイトｊｍｉｎ（ｉ）に再割り当てする負荷割り当て分を、他のすべてのサイトに再割り当てする負荷の合計減少量に等しい量だけ増加させ得る。その結果、ステップのサイズが「小さすぎない」限り、大域的な目的関数は各繰り返しにおいて減少され得、最終的に最適解に到達し、ステップサイズが減少されてゼロになる。この方法は、「最小規則」法を使用するとして記載され得る。
【００４９】
この方法の動作のより詳細な仕様は、下記のように記載され得る。任意の（実現可能な）初期解θ（０）から始めて、ｔ→∞のときにθ（ｔ）→θ＊となるような数列の解θ（１），θ（２），．．．がこの方法により求まる。θ＊は一意でなくてもよいことに留意されたい。
【００５０】
具体的には、θ（ｔ）からθ（ｔ＋１）を得るために、この方法ではまず、θｉ，ｊに関して式（１）に記載した目的関数の導関数
【００５１】
【数１５】
2015501991.tif 000019
を計算し得る。ここで、複数サーバ近似では、Γｊ≡１、単一サーバ近似では、Γｊ＝１／Ｋｊとし、次に、ｊｍｉｎ（ｉ）＝ａｒｇｍｉｎｊαｉ，ｊを判定し、各ｉについて、γｉ，ｊ＝αｉ，ｊ−αｉ，ｊｍｉｎ（ｉ）を計算し得る。ここでは、表記を簡単にするために、更新時間「ｔ」は省かれる。さらに、この方法は、各ｊ，ｊ＝１，１，．．．，Ｎについて、
【００５２】
【数１６】
2015501991.tif 000020
を計算し得る。ここで、
【００５３】
【数１７】
2015501991.tif 000021
である。
【００５４】
次に、この方法は、すべてのｊ≠ｊｍｉｎ（ｉ）、k＞０について、ηｉ，ｊ（ｔ）＝ｍｉｎ｛θｉ，ｊ（ｔ），δγｉ，ｊ（ｔ）｝、かつ
【００５５】
【数１８】
2015501991.tif 000022
として、θｉ，ｊ（ｔ＋１）＝θｉ，ｊ（ｔ）−ηｉ，ｊ（ｔ）を計算し得る。
ηは、１つのサイトから別のサイトへの負荷の移動を反映する再割り当て調整行列である。方法の全体は図６に示され、図７に、代替の「最大規則」法が示される。
【００５６】
この方法は、大規模に分散された形態で動作し得ることに留意されたい。その理由は、各サイトｊはρｊ（θ）の値をアドバタイズするだけで、次に、各サイトｉが、τｉ，ｊの値と共にこれらの値に基づいて、αｉ，ｊ（ｔ）、ｊｍｉｎ（ｉ）およびηｉ，ｊ（ｔ）の値を判定し得るために十分であるからである。
【００５７】
さらに、一般に、
【００５８】
【数１９】
2015501991.tif 000023
であることに留意されたい。つまり、一般に、サイトｉが、遅延が最小であるサイトにトラフィックを送信することは、最適でない。その理由は、上記の偏導関数の式内の最終項に表されているように、他のノードへの影響の原因となるからである。負荷が小さい場合、つまり、ρｊ＜＜１、ｊ＝１，．．．Ｎの場合は、リンクレイテンシが支配的であり得、ｊｍｉｎ（ｉ）＝ａｒｇｍｉｎｊτｉ，ｊ＝ｉ、つまり、トラフィックはローカルにサービスされ得る。負荷が大きい場合、つまり、
【００５９】
【数２０】
2015501991.tif 000024
の場合は、処理遅延が支配的であり得、
ｊｍｉｎ（ｉ）＝ａｒｇｍｉｎｊρｊ（θ（ｔ））、
つまり、トラフィックは最小の相対負荷をもつサイトにルーティングされ得る。
【００６０】
初期解は、様々な方法で生成し得る。例えば、
【００６１】
【数２１】
2015501991.tif 000025
によって生成し得る。ここで、
【００６２】
【数２２】
2015501991.tif 000026
は、システム全体の平均正規化負荷を表す。
また、
【００６３】
【数２３】
2015501991.tif 000027
によっても生成し得る。ここで、
【００６４】
【数２４】
2015501991.tif 000028
は、ノードｊが合計負荷のうち公平な割り当て分をもっているとき、ローカルなトラフィックより余分の処理容量がノードｊに残っている場合の、その残りの処理容量を表す。
【００６５】
図６は、上記の方法の動作を示すフローチャートである。具体的には、フローチャートに示される方法は、「最小規則」法を使用してコンピューティング負荷を再割り当てする。「最小規則」では、データセンタｉで、各ｊについて導関数αｉ，ｊを計算することを目指す（６１０）。ｊ全体で最小のαｉ，ｊが判定される。次に、各ｊについて、γｉ，ｊ＝αｉ，ｊ−αｉ，ｊｍｉｎ（ｉ）が計算される（６１０）。次に、νｊが計算され得る（６１０）。これらの計算によって、負荷割り当て分の増加による、目的関数の全体的な値への影響が最も小さいサイトｊが特定される。このサイトが特定された後は、他のサイトの「少量の」負荷がサイトｊに移動され得る。これは、ステップ６２０および６３０で行われ得る。ステップ６２０で、ηｉ，ｊが計算され得る。次に、値ηｉ，ｊを使用してθｉ，ｊが更新され（６３０）、その結果、サイト間で負荷が移動する。この処理は、方法がθｉ，ｊの解に収束するまで繰り返され得る（６４０）。解が収束した場合は、方法は、さらに再割り当てが必要になるような変化が遅延および稼働率に起こるときを判定する（６５０）。解が収束していない場合は、新しい測定値が収集され得、次のサイトについて計算が続行される（６６０）。理想的には、適格な組の中の各ｊについてηｉ，ｊの計算が０になったときに解は収束する。測定値には雑音が多いので、通常、収束するために必要な繰り返しの数は、過度に多くなり得る。したがって、この方法では、ηｉ，ｊが非常に小さい閾値に達したときに、解に収束したと判定し得る。データセンタｉで収集する必要のある新しく更新された測定値は、ｉに関する適格なサイトの稼働率ρｊの値およびローカルのジョブ到着率λｉであることに留意されたい。β、Ｋｊ、Γｊおよびτｉ，ｊなどの他の値は、一般に、一度だけ収集されるか、または、値が変化したときに収集されるが、変化が起こることは非常にまれである。
【００６６】
図７は、式（１）に示される目的関数を最適化する方法の、別の実施形態の動作を示すフローチャートである。具体的には、フローチャートに示される方法は、「最大規則」法を使用してコンピューティング負荷を再割り当てする。「最大規則」では、データセンタｉで、各ｊについて導関数αｉ，ｊを計算することを目指す（７１０）。θｉ，ｊ＞０である、ｊ全体で最大のαｉ，ｊが判定される。次に、各ｊについて、γｉ，ｊ＝ｍａｘ｛αｉ，ｊｍａｘ（ｉ）−αｉ，ｊ，０｝が計算される（７１０）。次に、νｊが計算され得る（７１０）。これらの計算によって、負荷割り当て分の減少による、目的関数の全体的な値の増加が最も大きいサイトｊが特定される。このサイトが特定された後は、サイトｊの「少量の」負荷が他のサイトに移動され得る。これは、ステップ７２０および７３０で行われ得る。ステップ７２０で、ηｉ，ｊが計算され得る。次に、値ηｉ，ｊを使用してθｉ，ｊが更新され得（７３０）、その結果、サイト間で負荷が移動する。この処理は、方法がθｉ，ｊの最適解に収束するまで繰り返され得る（７４０）。解が収束した場合は、方法は、さらに再割り当てが必要になるような変化が遅延および稼働率に起こるときを判定する（７５０）。解が収束していない場合は、新しい測定値が収集され得、次のサイトについて計算が続行される（７６０）。理想的には、ηｉ，ｊの計算が０になったときに解は収束するが、実際には、収束するまでに多くの繰り返しが必要になり得る。したがって、この方法では、ηｉ，ｊが非常に小さい閾値に達したときに、解に収束したと判定し得る。
【００６７】
上記の方法では、サイトｉは、他のサイトｊへの、または他のサイトｊからの負荷の再割り当てを目指し得る。上記のとおり、この方法では、他のすべてのサイトｊが負荷の再割り当てに適格であると見なされ得る。別の実施形態では、他のサイトｊの一部のみが負荷の再割り当てに適格であると見なされ得る。例えば、サイトｉで、隣接するデータセンタ、一定距離内のデータセンタまたはネットワークポリシによって規定されたデータセンタのみを、負荷の再割り当ての試みに使用し得る。このことには、サイトｉが収集する必要のある情報の量を減少させること、および再割り当ての処理の量を減少させることという利点があり得る。さらに、遠方のサイトでは搬送時間に起因して遅延が長いので、トラフィックが遠方のサイトへ再割り当てされる可能性は低く、よって不必要な計算が防がれ得る。また、複数種類のジョブも、簡単に上記の方法に組み込むことができる。
【００６８】
上記の記載により、本発明の様々な例示的実施形態がハードウェアおよび／またはファームウェアに実装され得ることは、明らかであろう。さらに、様々な例示的実施形態が、機械読み取り可能な記憶媒体に記憶される命令として実装され得、この命令は、少なくとも１つのプロセッサにより読み取りおよび実行され、本明細書に詳細に記載される動作を行い得る。機械読み取り可能な記憶媒体は、パーソナルコンピュータもしくはラップトップコンピュータ、サーバ、またはその他のコンピューティングデバイスなどの、機械による読み取りが可能な形式の情報を記憶するためのあらゆる機構を含み得る。よって、有形で一時的でない、機械読み取り可能な記憶媒体は、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイス、および類似の記憶媒体を含み得る。
【００６９】
本明細書に記載されるあらゆるブロック線図は、本発明の原理を実施する回路例の概念図を表すということが、当業者には理解されよう。同様に、あらゆるフローチャート、フロー線図、状態遷移図、擬似コードなどは、機械読み取り可能な媒体内に実質的に表現され得、また、コンピュータまたはプロセッサが明示的に示されているかいないかに関わらず、コンピュータまたはプロセッサにより実質的に実行され得る様々な処理を表すということが理解されよう。
【００７０】
様々な例示的実施形態について、いくつかの例示的様態を特に参照して詳細に記載してきたが、本発明には他の実施形態が可能であり、本発明の詳細は様々な明白な点において、修正形態が可能であることが理解されよう。当業者には明らかであるように、変更形態および修正形態は、本発明の趣旨および範囲から逸脱することなく実施することができる。したがって、上記の開示、記載および図は、説明のみを目的とし、本発明をいかなる形でも制限するものではなく、本発明は、特許請求の範囲によってのみ定められる。
【図１】
2015501991.tif 000029
【図２】
2015501991.tif 000030
【図３】
2015501991.tif 000031
【図４】
2015501991.tif 000032
【図５】
2015501991.tif 000033
【図６】
2015501991.tif 000034
【図７】
2015501991.tif 000035
【国際調査報告】
2015501991.tif 000036
2015501991.tif 000037
2015501991.tif 000038