(57)【要約】【課題】データセンタの過負荷を防ぐとともに、データセンタの計算資源を効率良く使用する。このため、複数のサービスの複数のデータセンタへの最適な配置計画を作成する。【解決手段】複数のデータセンタによって運用される複数のトランザクション型サービスに対して、トランザクション計画部１１０の予測部１１１が原始サービスの負荷予測を行い、派生サービス生成部１１２が派生サービスを生成し、最適解探索部１１５が派生サービスに対する最適な資源計画を作成する。また、複数のデータセンタによって運用される複数のバッチ型サービスに対して、バッチ計画部１２０の負荷量算出部１２１が原始サービスの負荷予測を行い、バッチ型派生サービス生成部１２２が派生サービスを生成し、バッチ型最適解探索部１２５が派生サービスに対する最適な資源計画を作成する。【選択図】        図４
2005293048.tif 000002
【特許請求の範囲】
【請求項１】
複数の計算機から構成される計算機クラスタが複数接続されて構成される計算機クラスタシステムが運用する複数のサービスを該複数の計算機クラスタへ配置する資源計画を作成する資源計画作成プログラムであって、
運用される計算機クラスタが定められたサービスである原始サービスから該原始サービスの負荷予測に基づいて各計算機クラスタから他の計算機クラスタへ運用の一部が移される派生サービスを生成する派生サービス生成手順と、
前記派生サービス生成手順により生成された派生サービス群を前記複数の計算機クラスタへ最適配置する資源計画を所定の評価指標に基づいて作成する計画作成手順と、
をコンピュータに実行させることを特徴とする資源計画作成プログラム。
【請求項２】
前記派生サービス生成手順は、前記負荷予測の予測期間を所定の時間間隔で複数のタイムスロットに分割したタイムスロット毎に派生サービス集合を生成し、
前記計画作成手順は、前記タイムスロット毎の派生サービス集合の配置計画であるタイムスロット配置計画を該タイムスロットの時刻順に並べた配置計画系列を前記資源計画として作成することを特徴とする請求項１に記載の資源計画作成プログラム。
【請求項３】
前記計画作成手順は、互いに競合する複数の最適化指標に基づいて派生サービス集合を前記複数の計算機クラスタへ最適配置する資源計画をPareto最適性理論に基づいて作成することを特徴とする請求項２に記載の資源計画作成プログラム。
【請求項４】
前記派生サービス生成手順は、
指定されたデッドライン時刻までに、サービスを構成する全てのジョブが処理完了されていれば、個々のジョブはいつ何時処理されても構わないことを特徴とするような非リアルタイム性のバッチ型サービスが計算機クラスタの集合で運用されている場合に、リアルタイム性を要求されるトランザクション型のサービスに対して計算機クラスタの資源を優先的に割り当て、残った余剰資源をバッチ型サービスに割り当てるために、トランザクション型サービスに対して資源計画の生成を行い、その後、割り当て対象とならなかった余剰資源についてバッチ型サービスの資源計画の生成を行う事を特徴とする請求項１に記載の資源計画作成プログラム。
【請求項５】
前記計画作成手順は、
各バッチ型原始サービスを構成する全てのジョブを、その投入時刻がデッドライン時刻に近いものから順に実行計画の対象とし、いかなるサービスによっても使用されていない余剰計算資源の量の計算機クラスタ集合全体にわたる総和が最大となる期間に当該スケジューリング対象となったジョブの実行計画を生成することを特徴とする請求項１に記載の資源計画作成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の計算機から構成される計算機クラスタが複数接続されて構成される計算機クラスタシステムが運用する複数のサービスの該複数の計算機クラスタへの配置計画を作成する資源計画作成プログラムに関し、特に、各計算機クラスタが過負荷になることを防ぐとともに、計算機クラスタの計算資源を効率的に使用することができる資源計画の作成プログラムに関するものである。
【背景技術】
【０００２】
近年のデータセンタは、一つのデータセンタ内において、複数のサービスプロバイダ事業者から運用を委託された複数のネットワーク・サービスを同時に運用するようになってきており、それと共に、同時運用する複数のサービスの中で負荷の増加しているサービスに対しては、データセンタ内の計算資源の割当量を動的に増やし、負荷の減少しているサービスにはデータセンタ内の計算資源の割当量を動的に減らすユーティリティ方式に基づく資源割当制御を行っている（例えば、特許文献１参照）。
【０００３】
しかし、データセンタで運用している一部のサービスが一時的に過負荷となり、このサービスに対する資源割当を大幅に増やす必要が生じたときに、新たに追加割当すべき遊休資源がデータセンタ内で不足し、資源追加が出来ない事態が発生する場合がある。
【０００４】
このような事態の発生を防ぐためには、データセンタでの全ての運用サービスの負荷の合計がピークになる時の必要資源量を予測し、データセンタに恒常的にピーク時必要資源量を用意することが考えられるが、この場合には、ピーク時以外の期間中は大半の資源量が遊休資源として使われないままになり、データセンタ全体としてコストパフォーマンスや計算資源利用効率が低下してしまう。
【０００５】
そこで、国際特許出願ＪＰ０３／０３２７３では、後方支援データセンタを用いる方式が提案されている。この方式では、通常、各サービスはサービスの運用を依頼したサービスプロバイダ事業者が指定した特定のデータセンタ（以下「オリジナル・センタ」という。）で恒常的に運用される（以下、このようなサービスを「原始サービス」という。）。
【０００６】
そして、原始サービスが負荷の時間変動によって一時的に過負荷になり、それによってオリジナル・センタ自体もセンタ全体として過負荷状態になった場合、オリジナル・センタ上の過負荷になった原始サービスの一部を、後方支援センタと呼ぶ別異のデータセンタで処理するため、後方支援センタ上に当該原始サービスに対応する補助的サービス（以下「派生サービス」という。）を発生させて後方支援センタ上で運用を開始する。
【０００７】
これによって、過負荷になった原始サービスが負担していた負荷の一部を後方支援センタ上の派生サービスが肩代わりすることができ、オリジナル・センタのセンタ全体としての過負荷状態を解消できる。
【０００８】
ここで、各サービスに到着したユーザ・リクエスト量の原始サービスと派生サービスへの分配比率はネットワーク内の負荷分散装置またはリダイレクタに設定され、当該負荷分散装置等は設定された比率に基づいて、サービスに到着したユーザ・リクエスト量を原始サービスと派生サービスの間で振り分ける。
【０００９】
このような従来のデータセンタ運用形態においては、オリジナル・センタは一般に複数個あり、後方支援センタは一つであることが多い。また、オリジナル・センタと後方支援センタの役割分担は明確であり、後方支援センタは専ら派生サービスの運用のためだけに用いられていた。
【００１０】
【特許文献１】特開２００２−２４１９２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、特定のデータセンタを後方支援センタとして定め、全ての派生サービスを専らそのデータセンタでのみ運用する従来の技術には、複数のオリジナル・センタ上の多数の原始サービスから同時に一つの後方支援センタに対して派生サービスの発生要求が集中した場合、後方支援センタがセンタ全体として過負荷状態になるという問題がある。
【００１２】
また、派生サービスの発生要求の集中がピークになる時に後方支援センタで必要となる資源量を予測し、後方支援センタに恒常的に当該ピーク時必要資源量を用意するとなると、ピーク時以外は後方支援センタの計算資源の大半は使われないこととなり、資源利用効率が低下する。
【００１３】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、データセンタを典型例とするような計算機資源の集合体である計算機クラスタの各々が過負荷になることを防ぐとともに、計算機クラスタの計算資源を効率的に使用することができる資源計画作成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上述した課題を解決し、目的を達成するため、本発明は、複数の計算機から構成される計算機クラスタが複数接続されて構成される計算機クラスタシステムが運用する複数のサービスを該複数の計算機クラスタへ配置する資源計画を作成する資源計画作成プログラムであって、運用される計算機クラスタが定められたサービスである原始サービスから該原始サービスの負荷予測に基づいて各計算機クラスタから他の計算機クラスタへ運用の一部が移される派生サービスを生成する派生サービス生成手順と、前記派生サービス生成手順により生成された派生サービス群を前記複数の計算機クラスタへ最適に配置する資源計画を所定の評価指標に基づいて作成する計画作成手順と、をコンピュータに実行させることを特徴とする。
【００１５】
この発明によれば、運用される計算機クラスタが定められたサービスである原始サービスから原始サービスの負荷予測に基づいて各計算機クラスタから他の計算機クラスタへ運用の一部が移される派生サービスを生成し、生成した派生サービスを複数の計算機クラスタへ配置する資源計画を所定の評価指標に基づいて作成するよう構成したので、過負荷の計算機クラスタが運用するサービスの一部を計算機クラスタシステム全体で肩代わりすることができる。
【発明の効果】
【００１６】
本発明によれば、過負荷の計算機クラスタが運用するサービスの一部を計算機クラスタシステム全体で肩代わりするので、各計算機クラスタが過負荷になることを防ぐとともに、計算機クラスタの計算資源を効率的に使用することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１７】
以下に添付図面を参照して、この発明に係る資源計画作成プログラムの好適な実施例を詳細に説明する。なお、ここでは、本発明を複数のデータセンタの計算資源を複数のサービスに割り当てる資源計画の作成に適用した場合を中心に説明する。
【実施例】
【００１８】
まず、本実施例に係る資源計画の概念について説明する。図１は、本実施例に係る資源計画の概念を説明するための説明図である。図１の左側のグラフには、ＸＸチケット販売会社の提供するＷＥＢサービスに関する年間の負荷変動予測がプロットされている。
【００１９】
このグラフ内の水平の点線で示した高さがＸＸチケット販売会社の自社センタの保有資源量で処理できる負荷の量を表している。このグラフの負荷変動は２箇所のピークを持ち、いずれのピークにおいても自社センタ資源で処理できる負荷量（点線の高さ）を超えてしまっている。そこで、本実施例に係る資源計画では、ピーク時に自社センタ以外のデータセンタに派生サービスを発生させて点線を超えた分の負荷を肩代わりさせる。
【００２０】
ここで、左側のピークの発生期間においては、データセンタＸでは資源が殆ど消費されていないのに対し、データセンタＹでは大半の資源が他のサービスなどによって消費されている。従って、左側のピーク時にはデータセンタＸに派生サービスを配置する。
【００２１】
一方、右側のピークの発生期間においては、データセンタＸの大半の資源が他のサービスなどによって消費されており、データセンタＹでは資源が殆ど消費されていないので、データセンタＹに派生サービスを配置する。
【００２２】
すなわち、本実施例に係る資源計画では、複数個あるオリジナル・センタの内、運用中の原始サービスが低負荷となったことにより一時的に遊休資源が大量に余っているオリジナル・センタを選んで臨時の後方支援センタとして扱い、当該臨時の後方支援センタで、派生サービスを運用する。
【００２３】
このような運用形態に基づくならば、オリジナル・センタと後方支援センタの役割分担は各データセンタに固有のものではなく、データセンタＸが原始サービスＡを恒常的に運用しており、データセンタＹが原始サービスＢを恒常的に運用している場合、データセンタＸは、原始サービスＡにとっては常にオリジナル・センタとしての役割を持ち、原始サービスＢにとっては後方支援センタとしての役割を持つ場合がある。以後、ここでは、オリジナル・センタと後方支援センタの役割分担は上記のようにサービスとの相対関係で決まるものとする。
【００２４】
ここで、多数のデータセンタがネットワークで繋がった環境で多数の原始サービスを運用しようとする際には、ある原始サービスが将来において過負荷になった際、どのデータセンタを派生サービス運用のための後方支援センタとして選択すればよいかが問題となる。つまり、将来発生することが予想される各派生サービスを各々どのデータセンタにいつ何時に配置すべきかが問題となる。
【００２５】
ただし、ある将来時点で発生している各派生サービスを各計算機クラスタへどのように配置するかについての最適解の探索については、計算量と計算時間を考慮する必要がある。例えば、データセンタが３個あり、ある将来時点で３０個の派生サービスが同時に発生しているとすると、ある１個の派生サービスは、発生元の原始サービスのオリジナル・センタ以外の二つのデータセンタのどちらかに配置可能だから、３０個の派生サービスの３個のデータセンタへの配置の仕方は２の３０乗（１０億以上）通りあることになる。
【００２６】
従って、これら全てを単純探索により評価するのは膨大な時間の無駄となり、派生サービス集合のデータセンタ集合への配置の最適解を発見するに当たっては、探索ステップ数ができるだけ少なく抑えられるような最適解探索手法が必要となる。
【００２７】
具体的には、データセンタ群と原始サービスの集合が与えられ、各原始サービスを運用するオリジナル・センタが指定された場合、派生サービスの将来発生時点を予め予測し、全てのデータセンタの計算資源利用効率が改善されるように、様々な時点で発生する各派生サービスを各々どのデータセンタで運用するか（派生サービスのセンタ配置）を最適化する必要がある（図２）。
【００２８】
また、派生サービス集合の構成や各派生サービスの処理する負荷量、各データセンタの資源消費状況などは時々刻々と変化するので、時間の経過に従って、派生サービス集合のデータセンタ群への配置の最適化を定期的にやり直す必要がある。上記の配置の最適化を定期的にやり直す際は、時間軸をタイムスロットと呼ぶ周期に分割し、各タイムスロット毎に最適な派生サービス配置を求める（図３）。
【００２９】
従って、最終的には、派生サービス集合のデータセンタ群への配置パターンの最適候補を一定時間周期毎（各タイムスロット毎）に求めて、それをタイムスロットの時刻順に時系列として並べた情報を出力する必要がある。この出力情報のことを以後、データセンタ群の資源計画と呼ぶ。
【００３０】
また、最適な派生サービス配置の時系列を探索するに当たって、同時発生する派生サービスの個数によっては、探索空間が巨大となり、単純探索では膨大な時間がかかるので、それを防ぐために、本実施例に係る資源計画では、以下の工夫をする。
【００３１】
探索対象の解は一般に複数個の指標によって評価され、それら全ての指標をなるべく最適にする解が最終的に選ばれなくてはならないが、探索空間の中から少なくとも一つの指標が最適であるような解から構成される集合（Pareto解集合）を絞り込み、そのPareto解集合の中から特定の基準によって任意の解を選び、その解を暫定解とする。
【００３２】
そして、後述するＮＤＣ入れ替え操作により、暫定解を漸近的に真の最適解に近づけてゆき、暫定解の評価値が一定の収束半径に入ったらその暫定解を最終的な最適解として出力する。
【００３３】
なお、データセンタが運用するサービスには、ＷＥＢサービスのようにユーザ・リクエストを受け付けてから数秒以内に応答を返さなくてはならないようなリアルタイム性を要求されるトランザクション型のサービスと、毎日、毎月といった一定の周期で決められた時刻に投入された複数のジョブ群を、予め定められたデッドライン時刻までに全て処理完了する必要のあるバッチ型のサービスがある。
【００３４】
バッチ型のサービスは複数個のジョブによって構成され、一般に複数回に分けて、各々決められた時刻に、複数個ずつのジョブがまとめてデータセンタに投入される。このジョブの投入スケジュールは一日周期や１ヶ月周期等の一定周期毎に繰り返される。ジョブの投入スケジュールは、そのバッチ型サービスの運用を委託した委託元業者によって事前に指定される。
【００３５】
バッチ型サービスに関しては、投入されたジョブ群が指定されたデッドライン時刻までに全て処理完了するのであれば、個々のジョブは、いつ何時処理されてもよく、いわばリアルタイム性を必要としない。
【００３６】
従って、データセンタ群で運用する原始サービス集合がトランザクション型のサービスとバッチ型のサービスの２種類のサービスから構成されている場合は、トランザクション型サービスがリアルタイム性を要求されるサービスであることを考慮し、データセンタ群の持つ計算資源は、トランザクション型サービスに優先的に割り当てる。
【００３７】
その後、トランザクション型サービスに割り当てられなかった余剰計算資源をバッチ型サービスの処理に割り当てるような資源計画の生成を行う必要がある。従って、データセンタ群の資源計画を生成するには、まず、トランザクション型の原始サービスのみを当該データセンタ群で運用したと仮定して資源計画の生成を行い、その資源計画においてトランザクション型サービスに割り当てられていない余剰計算資源に対し、バッチ型サービスの資源計画の生成を行う。
【００３８】
また、バッチ型原始サービスの負荷変動予測に関しては、バッチ型サービスのジョブ投入スケジュールが予め既知であることから、ARIMAモデル手法のような数理的な予測アルゴリズムによってサービスの将来負荷変動を予測するのではなく、将来の負荷変動の推移を特定のジョブ・スケジューリング・アルゴリズムによって計画することが出来る。
【００３９】
従って、バッチ型原始サービスの集合に関する資源計画の生成では、バッチ型原始サービスの将来の負荷変動は予測するのではなく、ジョブ・スケジューリング・アルゴリズムによって事前に計画されたものを用いるという形をとる。
【００４０】
具体的なジョブ・スケジューリング・アルゴリズムは、後述するが、当該スケジューリング・アルゴリズムの特徴は、バッチ型原始サービスを構成する各ジョブを、投入時刻の遅い順にスケジューリングしてゆき、スケジューリング対象となったジョブを、当該ジョブの投入時刻からデッドライン時刻までの間の時間帯の中でデータセンタ群の余剰計算資源の最も多い時刻に当該ジョブをスケジューリングするというものである。
【００４１】
このようなジョブ・スケジューリング・アルゴリズムを採用する理由は、バッチ型サービスの負荷の処理は、なるべくトランザクション型サービスによる負荷が空いている時を選んで行わせることにある。
【００４２】
次に、本実施例に係る資源計画作成装置の構成について説明する。図４は、本実施例に係る資源計画作成装置の構成を示す機能ブロック図である。同図に示すように、この資源計画作成装置１００は、トランザクション計画部１１０と、バッチ計画部１２０と、資源計画送信部１３０とを有する。
【００４３】
トランザクション計画部１１０は、トランザクション型サービスに対して資源計画を作成する処理部であり、予測部１１１と、派生サービス生成部１１２と、ＤＣ生成部１１３と、ＮＤＣ生成部１１４と、最適解探索部１１５とを有する。
【００４４】
なお、以下のトランザクション計画部１１０の説明において、サービス、原始サービスおよび派生サービスについては、特に断らない限り、トランザクション型のサービスを意味する。また、トランザクション型サービスの資源計画の生成においては、タイムスロットの長さはデータセンタ群の運営業者によって、データセンタ群全体で一意の値が手動で決定されるものとする。
【００４５】
予測部１１１は、運用すべき全ての原始サービスの負荷変動の将来予測を行う処理部である。ここで、予測の対象となる期間を以後、予測期間と呼び、その長さは、１日、１ヶ月、１年などである。
【００４６】
派生サービス生成部１１２は、予測部１１１による負荷変動予測とオリジナル・センタの保有資源量に基づいて、派生サービスの発生時刻、発生個数、各派生サービスと原始サービスとの間の負荷分配比率を求める処理部である。
【００４７】
派生サービスの発生条件としては以下のようなものが例として挙げられる。図５−１および図５−２は、派生サービスの発生条件を説明するための説明図（１）および（２）である。図５−１は、データセンタ内に配置された原始サービスのリソース使用率が９０％を超えたときに派生サービスを発生させる場合を示している。
【００４８】
また、図５−２は、三つのデータセンタＸ、ＹおよびＺのリソース使用率の平均を算出し、各データセンタのリソース使用率が平均の１．２倍以上になったときに派生サービスを発生させる場合を示している。
【００４９】
実際には、派生サービス生成部１１２は、各データセンタ毎に原始サービスによるリソース使用率の標準偏差を計算し、その値が一定の閾値を超えた時に派生サービスを発生させるという発生条件を採用している。
【００５０】
ＤＣ生成部１１３は、予測期間を一定周期のタイムスロットに分割し、各タイムスロット毎にタイムスロット内で発生する派生サービスをどのデータセンタに配置するかを定める配置組合せパターンの候補全てを生成する処理部である。
【００５１】
ここで、生成される配置組合せパターンの各候補のことをＤＣ(Deployment Candidate)と呼び、タイムスロット(ｔ)について生成したＤＣの集合に属するＤＣのことを、タイムスロット(ｔ)に属するＤＣと呼ぶ。
【００５２】
ＮＤＣ生成部１１４は、各タイムスロットに属するＤＣからＶＤＣ(Violating ＤＣ)を除外したＮＤＣ(Normal ＤＣ)を作成する処理部である。ここで、ＶＤＣとは、複数の評価指標m1, …, mkによる評価結果e1, …, ekが所定の条件に違反するＤＣであり、ＮＤＣとは、それ以外のＤＣである。
【００５３】
評価指標は、評価指標を用いて派生サービス群のデータセンタ群への配置組合せの最適化をすることにより、データセンタ群全体の資源利用効率が改善されるようなものであり、例えば、負荷の均等度（図６−１）、ＮＤＣの類似度（図６−２）などがある。なお、ここでは、評価値の値が小さいほど評価が良いものとする。
【００５４】
図６−１は、三つのデータセンタＸ、ＹおよびＺにおいて負荷の配置が均等でなく悪い配置と負荷の配置が均等で良い配置とを示しており、配置が良いほど負荷の均等度の値は小さいものとする。
【００５５】
図６−２は、四つのデータセンタＷ、Ｘ、ＹおよびＺの間での、タイムスロット(Ｋ−１)からタイムスロット(Ｋ)に移る際の派生サービスの移動およびタイムスロット(Ｋ)からタイムスロット(Ｋ＋１)に移る際の派生サービスの移動を示しており、ここでは、時間の経過に伴うタイムスロットの遷移時におけるサービス移動個数が多いほどＮＤＣの類似度の値は大きいものとする。
【００５６】
最適解探索部１１５は、Pareto最適性理論に基づいて最適なＮＤＣ系列を作成する処理部である。ここで、ＮＤＣ系列とは、各タイムスロットからＮＤＣを一つずつ選んでタイムスロット順に時系列に並べたものである。すなわち、最適なＮＤＣ系列を作成することが最適な資源計画を作成することとなる。
【００５７】
具体的には、この最適解探索部１１５は、ＮＤＣ系列毎に、それを構成する各ＮＤＣのｋ個の評価値e1, …, ekの各々をＮＤＣ系列全体にわたって合計して系列評価値E1, …, Ekとする。
【００５８】
そして、ｋ個の系列評価値E1, …, Ekの中で、いずれか一つ以上の系列評価値が最小の値となるものを全て選び出し、初期系列集合とする。この初期系列集合は、ＮＤＣ系列の集合を解空間とし、ｋ個の系列評価値E1, …, Ekの各々を目的関数とした時の多目的最適化問題におけるPareto解集合に相当する。
【００５９】
そして、求めた初期系列集合の中から系列評価関数ξの値が最小となるようなＮＤＣ系列を選び出し、準最適ＮＤＣ系列とする。そして、各タイムスロット毎に、準最適ＮＤＣ系列を構成する各ＮＤＣを、当該ＮＤＣと同一のタイムスロットに属する他の全てのＮＤＣと比較し、以下の入れ替え条件が成り立つ場合には、前者のＮＤＣを後者のＮＤＣと入れ替える操作を行う。
【００６０】
ここで、ei(Tp,c)は準最適ＮＤＣ系列内のタイムスロットTpに属するＮＤＣについてのeiの値であり、ei(Tp,o)はタイムスロットTpに属するＮＤＣであって準最適ＮＤＣ系列に含まれないＮＤＣについてのeiの値と定義する。
【００６１】
そして、タイムスロットTpに属する準最適ＮＤＣ系列内のＮＤＣのｋ個の全ての評価値について、ei(Tp,c) ≧ ei(Tp,o) (1 ≦ i ≦ k)となる場合はＮＤＣの入れ替えを行う。つまり、ＮＤＣの入れ替えの結果、ｋ個の評価値の組を構成する全ての評価値に関して評価値が改善される場合はＮＤＣの入れ替えを行う。
【００６２】
また、次の場合にもＮＤＣの入れ替えを行う。ｋ個の評価値の組を構成する評価値の中で、一部の評価値が入れ替えにより改善され、その他の評価値が改悪される場合、改善される評価値の改善量に入れ替え制御関数を適用した値の重み付け平均が、改悪される評価値の改悪量に入れ替え制御関数を適用した値の重み付け平均より上回るならば入れ替えを行うというものである。
【００６３】
つまり、整数の集合Ｉ=[i|1≦i≦k]が二つの部分集合I1とI2に分割でき、i ∈ I1の場合にei(Tp,c) ≦ ei(Tp,o)であり、i ∈ I2の場合にei(Tp,c)>ei(Tp,o)であるとき、以下の式（１）
【数１】
2005293048.tif 000003
が成り立つならば、ＮＤＣ入れ替え操作を実行する。ここで、φiは重み係数、Δei(T
p) = ei(Tp,c)−ei(Tp,o)、δei(Tp) = ei(Tp,o)−ei(Tp,c)、Λiおよびλiは評価値eiに関する入れ替え制御関数である。
【００６４】
そして、ＮＤＣの入れ替えによって修正された準最適ＮＤＣ系列を系列評価関数ξで評価し、ＮＤＣ入れ替え操作を行う以前の準最適ＮＤＣ系列のξで評価した値と比較し、改善率が一定の閾値を下回ったら準最適ＮＤＣ系列をデータセンタ群の資源計画とし、そうでなければ、ＮＤＣ入れ替えによって修正されたＮＤＣ系列を新たな準最適ＮＤＣ系列としてＮＤＣの入れ替えを繰り返す。
【００６５】
ここで、図７〜図１２を用いてこの最適解探索部１１５の処理の具体例について説明する。図７は、最適解探索部１１５による最適化手順の概略を説明するための説明図である。なお、ここでは、評価指標として負荷の均等度とＮＤＣの類似度を用いる。
【００６６】
同図に示すように、この最適解探索部１１５は、最適化ステップ（１）として、ＮＤＣの類似度に基づいて暫定解の初期候補群を生成し、最適化ステップ（２）として、暫定解の初期候補群を負荷の均等度とＮＤＣの類似度を用いて評価し、評価値が最小のものを暫定解とする。
【００６７】
そして、最適化ステップ（３）として、暫定解に対するＮＤＣの入れ替えによってより良い暫定解を生成し、最適化ステップ（４）として、収束条件を満たすか否かを判定し、収束条件を満たす場合には、暫定解を最終解として出力し、収束条件を満たさない場合には、最適化ステップ（３）に戻って収束条件を満たすまでＮＤＣの入れ替えを繰り返す。
【００６８】
図８は、最適化手順の説明に用いるＮＤＣテーブルの概念を説明するための説明図である。同図に示すように、ＮＤＣテーブルとは、各タイムスロットに属するＮＤＣを負荷均等度の良い順に並べたものである。以下、このＮＤＣテーブルを用いて各最適化ステップを説明する。
【００６９】
図９は、最適化ステップ（１）を説明するための説明図である。同図に示すように、この最適化ステップでは、隣接するタイムスロット間で「ＮＤＣの類似度＝０」となるＮＤＣ同士を接続して類似ＮＤＣ系列を生成する。例えば、図９では、タイムスロット（０）のＮＤＣ（１）を先頭とする類似ＮＤＣ系列、タイムスロット（０）のＮＤＣ（２）を先頭とする類似ＮＤＣ系列などの複数の類似ＮＤＣ系列が得られる。
【００７０】
なお、ＮＤＣ同士を接続する場合に、「ＮＤＣの類似度＝０」となるＮＤＣがない場合には、ＮＤＣの類似度が最も小さいＮＤＣを選択する。この結果、生成された類似ＮＤＣ系列は、ＮＤＣの類似度を評価指標とし、この評価指標の値が最も小さいＮＤＣ系列であり、これらを暫定解の初期候補群とする。また、各タイムスロットで最小の負荷均等度を持つＮＤＣから構成されるＮＤＣ系列は、系列全体としての負荷均等度の合計が最小のＮＤＣ系列であり、これも暫定解の初期候補群に含める。
【００７１】
図１０は、最適化ステップ（２）を説明するための説明図である。同図に示すように、この最適化ステップでは、負荷均等度およびＮＤＣの類似度を評価指標として全ての類似ＮＤＣ系列を評価し、系列評価値Ｅcが最小の最良類似ＮＤＣ系列を暫定解とする。
【００７２】
図１１−１は、最適化ステップ（３）を説明するための説明図である。同図に示すように、この最適化ステップでは、暫定解の各タイムスロットにおいて、暫定解に含まれるＮＤＣ以外のＮＤＣが所定の条件を満たす場合に、ＮＤＣを入れ替える。
【００７３】
ここで、所定の条件とは、図１１−２に示すように、負荷均等度およびＮＤＣの類似度を同時に改善するＮＤＣがある場合には、そのタイムスロットでの評価値Ｅiの値が最小のものを選んで入れ替えを行う。
【００７４】
また、どちらか一方だけが改善する場合には、以下のようにする。負荷均等度だけが改善するときは、ＮＤＣの類時度の悪化量ΔＳを所定の関数で評価した値ＢＬ(ΔＳ)よりも、負荷均等度の改善量ΔＬの方が大きいＮＤＣの中でΔＬ−ＢＬ(ΔＳ)の値が最大のものを選び、類似度だけが改善するときは、類似度の改善量ΔＳを所定の関数で評価した値ＢＬ(ΔＳ)よりも、負荷均等度の悪化量ΔＬの方が大きいＮＤＣの中でＢＬ(ΔＳ)−ΔＬの値が最大のものを選んで入れ替えを行う。
【００７５】
図１２は、最適化ステップ（４）を説明するための説明図である。同図に示すように、この最適化ステップでは、ＮＤＣ入れ替え処理を施した最良類似ＮＤＣ系列の系列評価値Ｅcの改善率を調べ、改善率が例えば３％以内であれば収束条件を満たしたものとして最終解を出力し、収束条件を満たさない場合には、最適化ステップ（３）に戻って、入れ替え処理を繰り返す。
【００７６】
このように、ＮＤＣの類似度に基づいてＮＤＣ系列の初期候補群を生成し、初期候補群から系列評価値Ｅcが最小の最良類似ＮＤＣ系列を暫定解とし、ＮＤＣの入れ替えによって暫定解を改善することによって、最適なＮＤＣ系列を求めることができる。なお、ここでは、負荷均等度およびＮＤＣの類似度の二つの評価指標を用いたが、一般には、任意の個数の評価指標を用いることができる。また、収束条件に用いる改善率も３％以外の他の値を用いることができる。
【００７７】
バッチ計画部１２０は、バッチ型の原始サービス集合について資源計画の生成を行う処理部であり、負荷量算出部１２１と、バッチ型派生サービス生成部１２２と、バッチ型ＤＣ生成部１２３と、バッチ型ＮＤＣ生成部１２４と、バッチ型最適解探索部１２５とを有する。
【００７８】
なお、以下のバッチ計画部１２０の説明では、ジョブの投入スケジュールは１日周期で繰り返され、予測期間の長さが１日のトランザクション型サービスについての資源計画が得られていると仮定して説明する。
【００７９】
また、あるバッチ型サービスの１個のジョブを標準的な性能のサーバ１台で処理するのに必要な時間を「ターンアラウンド時間」と呼び、この時間の長さはバッチ型サービス毎に一意に定まる。
【００８０】
また、標準的な性能のサーバ１台が捌くことの出来る負荷量を「単位サーバ性能」と呼ぶ。デッドライン時刻とターンアラウンド時間は各バッチ型原始サービス毎に一意の値が定まる。また、バッチ型サービスの個々のジョブの投入時刻と予測期間の開始時刻の時間差は当該バッチ型サービスのターンアラウンド時間の整数倍とする。
【００８１】
負荷量算出部１２１は、将来の負荷量を算出する処理部である。具体的には、この負荷量算出部１２１は、以下の手順で将来の負荷量を算出する。まず、全てのバッチ型原始サービスのターンアラウンド時間の最小公倍数を求め、この値を新たなタイムスロットの長さとする。
【００８２】
そして、各データセンタ毎、各計測周期毎に、当該計測周期において当該データセンタに存在する（トランザクション型サービスに割り当てられなかった）余剰資源量で捌くことの出来る負荷量を単位サーバ性能で除算し、余剰資源量を標準性能サーバ台数の表現に換算する（以後これを、余剰サーバ台数と呼ぶ）。
【００８３】
そして、予測期間内における各バッチ型原始サービスの将来負荷変動を０で初期化する。その後、各バッチ型原始サービス毎に、各バッチ型サービスのジョブ投入スケジュールが、「時刻t1にn1件のジョブを投入、t2にn2件を投入、…、tkにnk件を投入」となっている時、1≦i≦kである各整数iについて以下の（Ｓ１）〜（Ｓ５）を実行する。ただしt1>t2>…>tkとする。
【００８４】
（Ｓ１）時刻tiから当該バッチ型原始サービスのデッドライン時刻までの期間（これをスケジュール期間と呼ぶ）を当該バッチ型原始サービスのターンアラウンド時間の長さを持つタイム・クォンタムに分割する。
（Ｓ２）各データセンタの各タイム・クォンタム毎に余剰サーバ台数が最小となる計測周期を求め、その時の余剰サーバ台数をそのタイム・クォンタムの余剰サーバ台数とする。
【００８５】
（Ｓ３）各タイム・クォンタムにおいて、余剰サーバ台数が最大であるデータセンタを検索し、当該データセンタをそのタイム・クォンタムにおける最大センタとし、各タイム・クォンタム毎に全データセンタにわたって余剰サーバ台数を合計し、その合計値を、当該タイム・クォンタムのＲ値とする。
【００８６】
（Ｓ４）Ｒ値が最大となるタイム・クォンタムを検索し、当該タイム・クォンタムにおける最大センタの余剰サーバ台数の値を１だけ減算し、当該タイム・クォンタムについて最大センタとＲ値を求めなおすとともに、当該バッチ型原始サービスの将来負荷変動の当該タイム・クォンタムに対応する部分の負荷量に、単位サーバ性能と等しい負荷量を加算する。
（Ｓ５）niから１を減算し、ni>0なら（Ｓ３）に戻る。
【００８７】
バッチ型派生サービス生成部１２２は、負荷量算出部１２１により算出された将来負荷変動を表す負荷量に基づいてバッチ型派生サービスを発生させる処理部である。具体的には、このバッチ型派生サービス生成部１２２は、各バッチ型原始サービスについて、将来負荷変動を表す負荷量に基づいて、当該バッチ型原始サービスからバッチ型派生サービスが発生する時刻を定める。
【００８８】
その際、当該バッチ型原始サービスから適切な個数のバッチ型派生サービスを発生させ、バッチ型原始サービスの負荷量をそれらのバッチ型派生サービスの間で適切に分配するものとする。そして、各タイムスロット毎に、そのタイムスロット内で発生するバッチ型派生サービスの集合を生成する。
【００８９】
バッチ型ＤＣ生成部１２３は、各タイムスロット毎に、そのタイムスロットで発生するバッチ型派生サービス集合のデータセンタ群への配置組合せパターンの全ての候補（ＤＣ）を生成する処理部である。
【００９０】
バッチ型ＮＤＣ生成部１２４は、ＤＣからＶＤＣを除いたＮＤＣを作成する処理部である。すなわち、このバッチ型ＮＤＣ生成部１２４は、各タイムスロット毎に、評価指標m1,…,mkに基づいて、当該タイムスロットに属する各ＤＣを評価し、各ＤＣについての評価値e1,…,ekを計算する。
【００９１】
そして、各タイムスロット毎に、そのタイムスロットに属する各ＤＣを評価値e1,…,ekに基づいてＮＤＣとＶＤＣに分類し、ＶＤＣを当該タイムスロットに属するＤＣの集合から除く。
【００９２】
バッチ型最適解探索部１２５は、バッチ型資源計画を作成する処理部である。すなわち、このバッチ型最適解探索部１２５は、ＮＤＣ系列の集合から、トランザクション型サービスの場合と同様の手法でPareto解集合（初期系列集合）を生成し、初期系列集合の中から系列評価関数の値の最小となるＮＤＣ系列を選び、準最適ＮＤＣ系列とする。
【００９３】
そして、準最適ＮＤＣ系列内の各タイムスロットに対応するＮＤＣをＮＤＣの入れ替え操作（トランザクション型サービスの場合と同様）によって入れ替え、ＮＤＣ入れ替え操作の前後の準最適ＮＤＣ系列の系列評価関数の値を比較し、改善率が３％以下なら準最適ＮＤＣ系列をバッチ型資源計画とし、そうでなければＮＤＣの入れ替えを繰り返す。
【００９４】
資源計画送信部１３０は、作成した資源計画をインターネット２０を介して接続されるｎ個のデータセンタ１０1〜１０nに送信する処理部である。各データセンタは、この資源計画送信部１３０により送信された資源計画にしたがってサービスの運用を行う。
【００９５】
次に、図３に示したトランザクション計画部１１０の処理手順について説明する。なお、以下では、トランザクション型サービスの例としてＸＭＬベースのＷＥＢサービスを仮定し、原始サービスは全てＷＥＢサービスであるとする。
【００９６】
また、原始サービスの負荷変動予測の対象となった予測期間を表す時間軸は一定周期のタイムスロットに分割され、各タイムスロットは原始サービスの負荷を計測する周期である計測周期に分割される。そして、予測期間に含まれるタイムスロットの全数をNt、予測期間内の（時間軸上の時刻の早いほうから数えて）i番目のタイムスロットをTiと表す。
【００９７】
また、時刻ｔにおけるサービスの負荷量は、時刻ｔに当該サービスに到着する毎秒当りのユーザ・リクエスト数とする。ここで、データセンタの集合をC=[ci|1≦i≦Nc]、原始サービスの集合をP=[pi|1≦i≦Np]、タイムスロットTiの期間内において発生している全ての派生サービスの集合をD(Ti)=[d(Ti,j)|1≦j≦n(Ti)]、ＤＣを評価するためのｋ個の評価指標の組を[m1, m2, …, mk]、ｋ個の評価指標でＤＣを評価したｋ個の評価値の組を[e1, e2,…, ek]、ＮＤＣ系列を構成する各ＮＤＣのeiをＮＤＣ系列全体にわたって合計したものを系列評価値Ei、タイムスロットTiに属するＮＤＣの集合をΓ(Ti)=[γ(Ti,j)|1≦j≦ν(Ti)]、ＮＤＣ系列全体の集合をＳとする。
【００９８】
また、あるＮＤＣ系列ｓ∈Ｓを構成するＮＤＣでタイムスロットTiに属するＮＤＣを
γs(Ti,j)と書き、またＮＤＣγ(Ti,j)について計算した評価値eiの値をei(γ(Ti,j))と書く。従って、ＮＤＣ系列の一つのインスタンスｓ∈Ｓは、s = ＜γs(T1,j1), γs(T2,j2), γs(T3,j3), … , γs(TNt-1,jNt-1), γs(TNt,jNt)＞と表わされる。
【００９９】
また、データセンタciが原始サービスpjのオリジナル・センタであることをpj ⇒ ci等と表し、ciの全資源量を使って捌くことが出来る負荷量（毎秒リクエスト数）をR(ci)と表す。
【０１００】
また、ここでは、ＤＣを評価する評価指標として以下に定義する三つの指標m1,m2,m3を採用した。ここで、m1は派生サービスを評価対象のＤＣに従って配置した場合のデータセンタ群全体の負荷の均等度合いを表す。データセンタ群の各データセンタで用意しておくべきピーク時必要資源量を最小化するには、予測期間全体にわたって、全てのデータセンタの間で負荷量を均等に分散すればよいからである。
【０１０１】
また、m2は派生サービス間通信量を表す。各原始サービスがＸＭＬベースのＷＥＢサービスである場合、原始サービス同士がSOAPプロトコルによって互いに通信しあうケースが考えられる。このような場合、それらの原始サービスから発生した派生サービス同士もSOAP通信を行うことになる。
【０１０２】
従って、あるＤＣに従って各派生サービスを配置先データセンタに配置した際、互いに頻繁に大量のデータをSOAP通信でやり取りするような複数の派生サービスの各々が異なるデータセンタに配置されることとなった場合、データセンタ間の通信量が大幅に増大する。
【０１０３】
そして、通信路の帯域幅が不足することによりSOAP通信の通信遅延が増大すると、結果として各データセンタに対して不必要な負荷をかけることになる。そのため、ＤＣの評価指標として派生サービス間通信量m2を採用した。
【０１０４】
また、m3はＮＤＣの類似度を表す。タイムスロットTiに属するＮＤＣ γ(Ti,j1)の類似度の定義は次の通りである。あるＮＤＣ系列が定められたとき、ＮＤＣ系列を構成するＮＤＣで、タイムスロットTi-1に対応するＮＤＣ をγ(Ti-1,j0) 、タイムスロットTiに対応するＮＤＣ をγ(Ti,j1)、タイムスロットTi+1に対応するＮＤＣ をγ(Ti+1,j2)としたとき、時間の経過に従ってタイムスロットがTi-1からTiに遷移する際には、派生サービス集合のデータセンタ群への配置がγ(Ti-1,j0)からγ(Ti,j1)へと変更になるに伴って、派生サービス集合[D(Ti-1)∩D(Ti)]に属する幾つかの派生サービスは、あるデータセンタから別のデータセンタへ移動させられる場合がある。
【０１０５】
また、タイムスロットがTiからTi+1に遷移する際にも同様に派生サービス配置がγ(Ti,j1)からγ(Ti+1,j2)へと変更になるに伴い、[D(Ti)∩D(Ti+1)]に属する幾つかの派生サービスがデータセンタ間を移動させられる場合がある。
【０１０６】
そこで、タイムスロットTiに対応するＮＤＣ系列内のＮＤＣ γ(Ti,j1)の類似度は、タイムスロットがTi-1からTiに遷移する時に上記の理由によりデータセンタ間を移動させられる派生サービスの個数とタイムスロットがTiからTi+1に遷移する時にデータセンタ間を移動させられる派生サービスの個数を合計したものとする。
【０１０７】
すなわち、あるＮＤＣの類似度が大きいということは、そのＮＤＣに従って派生サービスを配置すると、タイムスロットの遷移に伴う派生サービスの移動回数が多くなり、その分だけデータセンタ群に対してサービス移動のための制御負荷をかけることになる。
【０１０８】
その結果、各データセンタが本来なら処理する必要のない負荷まで大量に担わされることになってしまうため、ＮＤＣの類似度をＮＤＣの評価指標の一つとして採用する必要がある。なお、m3はm1,m2と異なり、ＮＤＣ単体では評価できず、ＮＤＣ系列が指定されて初めて評価することができる。
【０１０９】
図１３は、図３に示したトランザクション計画部１１０の処理手順を示すフローチャートである。同図に示すように、このトランザクション計画部１１０は、まず、予測部１１１が、1≦i≦Npとなる全ての整数iについて、piの予測期間全体にわたる負荷変動予測をARIMAモデル予測などの既存の予測手法を用いて予測する（ステップＳ１０１）。なお、piの負荷変動予測はpiの負荷量の時間関数として表され、時刻ｔにおけるpiの負荷量は
θi(t)と表すことにする。
【０１１０】
そして、派生サービス生成部１１２が、負荷変動予測およびオリジナル・センタの資源量に基づいて派生サービスを発生させる（ステップＳ１０２）。なお、負荷変動予測に基づく派生サービスの発生のさせ方の詳細については後述する。そして、1≦i≦Ntとなる各整数iについてTiの期間中に発生すると予測された派生サービスの集合D(Ti)を生成する（ステップＳ１０３）。
【０１１１】
そして、ＤＣ生成部１１３が、1≦i≦Ntとなる各整数iについて、D(Ti)に属する各派生サービスのデータセンタ群Ｃへの可能な配置組合せの全ての候補（ＤＣ）を木探索アルゴリズムによって生成し、タイムスロットTiについて生成した配置組合せの候補の集合をΓ(Ti)とする（ステップＳ１０４）。
【０１１２】
そして、ＮＤＣ生成部１１４が、1≦i≦Ntとなる各整数i、1≦j≦ν(Ti)となる各整数jの全ての組み合わせについてγ(Ti,j)∈Γ(Ti)を評価指標m1,m2で評価し、評価値e1,e2を求める（ステップＳ１０５）。なお、γ(Ti,j)についてe1およびe2を計算する手順の詳細は後述する。
【０１１３】
そして、1≦i≦Ntとなる各整数i、1≦j≦ν(Ti)となる各整数jの全ての組み合わせについて、e1(γ(Ti,j)) > 0.7またはe2(γ(Ti,j)) > 0.8ならばγ(Ti,j)をＶＤＣとし、集合Γ(Ti)から取り除く。そうでなければ、γ(Ti,j)をＮＤＣとし集合Γ(Ti)に残す（ステップＳ１０６）。
【０１１４】
そして、最適解探索部１１６が、ＮＤＣ系列集合Ｓを定義し（ステップＳ１０７）、ＮＤＣ系列集合Ｓに含まれるＮＤＣ系列でｋ個の系列評価値E1(s),E2(s),E3(s)のいずれか一つ以上が最小値をとるＮＤＣ系列ｓを全て探し出し、初期系列集合の要素とする（ステップＳ１０８）。
【０１１５】
ただし、
【数２】
2005293048.tif 000004
とする。なお、ＮＤＣ系列集合Ｓから初期系列集合(Pareto集合）を抽出する手順の詳細は後述する。
【０１１６】
そして、初期系列集合に属するＮＤＣ系列を系列評価関数ξ(s)で評価し、その評価値が最小となるＮＤＣ系列を準最適ＮＤＣ系列σとする（ステップＳ１０９）。ただし、k=3で
【数３】
2005293048.tif 000005
とする。また、K1=1.0, K2=1.0, K3=0.1とした。
【０１１７】
そして、1≦i≦Ntとなる各整数iに対応するタイムスロットTiついてＮＤＣの入れ替え処理を行い（ステップＳ１１０）、ＮＤＣの入れ替えを行う前の準最適ＮＤＣ系列をσ'、ＮＤＣ入れ替え後の準最適ＮＤＣ系列をσとして改善率｜ξ(σ')−ξ(σ)｜／ξ(σ')を算出する（ステップＳ１１１）。なお、ＮＤＣの入れ替え処理の詳細については後述する。
【０１１８】
そして、改善率が０．０３以下であるか否かを判定し（ステップＳ１１２）、改善率が０．０３以下である場合には、σをデータセンタ群Ｃの資源計画として出力し、全ての処理を終える（ステップＳ１１３）。そうでなければ、σを新たなσ'としてステップＳ１１０に戻る。
【０１１９】
このように、派生サービス生成部１１２が生成した派生サービスに対して最適解探索部１１５がPareto最適化理論に基づいて最適ＮＤＣ系列を生成することによって、データセンタ群に対する最適な資源計画を作成することができる。
【０１２０】
次に、派生サービス生成部１１２による派生サービス生成の詳細について説明する。派生サービス生成部１１２は、全ての計測周期について、各計測周期毎に次の（Ｓ１）〜（Ｓ３）を行う。
【０１２１】
（Ｓ１）計測周期の中心時刻ｔ、1≦i≦Ncとなる整数iについて、pj ⇒ ciとなる全てのｊについて
【数４】
2005293048.tif 000006
を求め、集合[Θi / R(ci)|1≦i≦Nc ]を標本分布と見なした時の標準偏差を計算し、当該標準偏差が0.1以下であれば（Ｓ３）へ、そうでなければ（Ｓ２）へ行く。
【０１２２】
（Ｓ２）1≦i≦Ncとなる各整数iについてpiの時刻ｔにおける負荷量の一部を派生サービスとして分割する。ここで、派生サービスへの負荷量の分割のしかたは次の通りである。
【０１２３】
各原始サービスから派生サービスがNc-1個ずつ発生したと仮定し、各派生サービスの仮のセンタ配置を定める。仮定した派生サービスと原始サービスの負荷量の分配比率は次のようにして求める。
【０１２４】
線形計画法を用いて上記の分配比率を最適化し、次の条件が満たされるようにする。各派生サービスを上記の仮のセンタ配置で配置した際、各データセンタci(1≦i≦Nc)について、そこで運用している原始サービスと派生サービスの負荷量の合計をgiとした時の、標本集合[gi / R(ci)|1≦i≦Nc]の標準偏差が0.1以下になるようにする。
【０１２５】
もし整数計画法によって上記の条件を充足する分割比率が得られなかった場合は、各派生サービスの仮のセンタ配置をランダムに変更して、再び整数計画法による分割比率の最適化を行うことを繰り返すことにより、各原始サービスについて派生サービスに分割する負荷量の分割比率を求める。
【０１２６】
ただし、Nc>5であった場合でも一つの原始サービスから同時に発生可能な派生サービスの個数の上限は４個とする。ある派生サービスについて上記の方法で決定した分配比率が０であった場合、その派生サービスは存在しないものとして扱う。
（Ｓ３）次の計測周期に移り、新たな計測周期について（Ｓ１）を開始する。
【０１２７】
次に、γ(Ti,j)についてe1を計算する手順の詳細について説明する。タイムスロットTi内に含まれる計測周期の中心時刻の集合を[tih|1≦h≦Nm]とする。すなわち、タイムスロットTiの開始時点からｈ番目の計測周期の中心時刻をtihとし、一つのタイムスロット内にはNm個の計測周期が含まれるとする。
【０１２８】
データセンタcr(1≦r≦Nc)に配置されている全サービスの時刻ｔにおける負荷量合計をgr(t)とすると、γ(Ti,j)に対するeiの値は以下のようにして求まる。
【０１２９】
まず、1≦r≦Ncである各整数ｒについてセンター毎負荷量合計値の時系列[gr(tih)| 1≦h≦Nm ]を求め、1≦r≦Ncである各整数ｒについて時系列[gr(tih)/R(cr)| 1≦h≦Nm ]の時間軸上の平均値
【数５】
2005293048.tif 000007
を求める。
【０１３０】
そして、集合[μ(0,i), μ(1,i), μ(2,i), …,μ(Nc,i)]を標本分布と見なした時の標準偏差を計算し、この標準偏差をγ(Ti,j)に対するeiの値とする。
【０１３１】
次に、γ(Ti,j)についてe2を計算する手順の詳細について説明する。まず、評価対象ＮＤＣの属するタイムスロットＴ内の各計測周期について各データセンタ毎に、サービス間のSOAP通信による通信量をbpsの単位で見積もる。
【０１３２】
そして、データセンタ毎に、その見積もり通信量を、当該データセンタと外部ネットワークを繋ぐ通信路の帯域幅の値（bps単位）で除算した値（以下、通信路占有率と呼ぶ）を求める。
【０１３３】
そして、計測周期毎の通信路占有率をタイムスロットＴ全体にわたって平均した値を各データセンタについて計算する。当該平均値が最大となるデータセンタでの当該平均値をe2の値とする。
【０１３４】
なお、互いに通信しあう原始サービス同士の関係が、図１４に示すようなものであるとき、データセンタciにおける計測周期がｔの時の、サービス間のSOAP通信の通信量の見積もり手順の例を以下に示す。
【０１３５】
ここで、e2による評価対象となっているＮＤＣにおいて配置先データセンタが指定されている派生サービスの集合をD=[dk|1≦k≦Nd]、dkの配置先データセンタがciであることをdk ⇒ ci等と表す。また、サービスＸの負荷量を毎秒リクエスト数で表した値をL(X,t)と表す。また、原始サービスpjがdkの派生元の原始サービスであることを、pj↑dk等と表す。
【０１３６】
まず、図１４の１段目と２段目の間の通信量の見積もりで、計測周期ｔの時のデータセンタciにおける値B1(ci,t)を求める。まず、B1(ci,t)を０で初期化し、以下の四つの場合に分けて考える。
【０１３７】
(1) p1 ⇒ ciかつp2 ⇒ ciの場合
B1(ci,t)= B1(ci,t)+|L(p1,t)×ω1 − L(p2,t)|とする。
【０１３８】
(2) p1 ⇒ ciであり、p2 ⇒ ciでない場合
(p2↑dh)∧(dh⇒ci)となる全ての添字ｈの集合をＨとすると
【数６】
2005293048.tif 000008
【０１３９】
(3) p2 ⇒ ciであり、p1 ⇒ ciでない場合
(p1↑dh)∧(dh⇒ci)となる全ての添字ｈの集合をＨとすると
【数７】
2005293048.tif 000009
【０１４０】
(4) p1 ⇒ ciでなく、p2 ⇒ ciでもない場合
(p1↑dh)∧(dh⇒ci) となる全ての添字ｈの集合をＨとし、(p2↑dk)∧(dk⇒ci)となる全ての添字kの集合をKとすると
【数８】
2005293048.tif 000010
【０１４１】
その次に、図１４の２段目と３段目の間の通信量の見積もりで、計測周期ｔの時のデータセンタciにおける値B2(ci,t)を求める。まず、B1(ci,t)を０で初期化し、以下の四つの場合に分けて考える。
【０１４２】
(1) p2 ⇒ ciかつp3 ⇒ ciの場合
B2(ci,t)= B2(ci,t)+|L(p2,t)×ω2 − L(p3,t)|とする。
【０１４３】
(2) p2 ⇒ ciであり、p3 ⇒ ciでない場合
(p3↑dh)∧(dh⇒ci)となる全ての添字ｈの集合をＨとすると
【数９】
2005293048.tif 000011
【０１４４】
(3) p3 ⇒ ciであり、p2 ⇒ ciでない場合
(p2↑dh)∧(dh⇒ci)となる全ての添字ｈの集合をＨとすると
【数１０】
2005293048.tif 000012
【０１４５】
(4) p2 ⇒ ciでなく、p3 ⇒ ciでもない場合
(p2↑dh)∧(dh⇒ci) となる全ての添字ｈの集合をＨとし、(p3↑dk)∧(dk⇒ci)となる全ての添字kの集合をKとすると
【数１１】
2005293048.tif 000013
【０１４６】
ここで、ω(ci,t)=ω1(ci,t)+ω2(ci,t)とすることで、計測周期ｔの時のデータセンタciにおける見積もり通信量ω(ci,t)が得られる。
【０１４７】
次に、ＮＤＣ系列集合Ｓから初期系列集合(Pareto集合）を抽出する手順の詳細について説明する。まず、系列評価値E1(s)を最小にするようなｓ∈Ｓを求める。このようなｓは一般に複数個存在する。
【０１４８】
具体的には、1≦i≦Ntとなる各整数iについてΓ(Ti)に属する全てのＮＤＣを配列に格納して、e1の値をキーとしてその配列をソーティングし、Γ(Ti)内でe1の値が最小となるＮＤＣの集合Γb(Ti)を生成する。そして、直積集合Γb(T0)×Γb(T1)×…×Γb(TNt)に属する各ＮＤＣ系列を系列評価値E1(s)を最小にするようなｓ∈Ｓとする。
【０１４９】
その次に、系列評価値E2(s)を最小にするようなｓ∈Ｓを求める。すなわち、1≦i≦Ntとなる各整数iについてΓ(Ti)に属する全てのＮＤＣを配列に格納して、e2の値をキーとしてその配列をソーティングし、Γ(Ti)内でe2の値が最小となるＮＤＣの集合Γb(Ti)を生成する。そして、直積集合Γb(T0)×Γb(T1)×…×Γb(TNt)に属する各ＮＤＣ系列を系列評価値E2(s)を最小にするようなｓ∈Ｓとする。
【０１５０】
その次に、系列評価値E3(s)を最小にするようなｓ∈Ｓを求める。ここで時間軸全体にわたるＮＤＣの集合Γを以下のように定義する。
【数１２】
2005293048.tif 000014
【０１５１】
そして、1≦k≦NAとなる各整数ｋと1≦i≦Ntとなる各整数iの全ての組合せについて以下の処理を行う。集合Γ(Ti)内のＮＤＣを検索して、γ(Ti,j)∈Γ(Ti),1≦j≦ν(Ti)で、γkとγ(Ti,j)を比較した時の相対類似度が最小となるような添字jkiの値を求める。
【０１５２】
ここで、相対類似度とは、二つのＮＤＣを比較した時、二つのＮＤＣの指定する派生サービス配置の両方に共通に含まれている派生サービスの中で、一方のＮＤＣで指定されている配置先データセンタと他方のＮＤＣで指定されている配置先データセンタが異なるような派生サービスの個数を表す。
【０１５３】
そして、1≦k≦NAとなる各整数ｋについて以下のように表されるＮＤＣ系列s(k) = <γ(T0,jk0),γ(T1,jk1),…,γ(TNt,jkNt)>を求める。
【０１５４】
最後に、集合[s(k)|1≦k≦NA]に含まれるＮＤＣ系列s(k)の内E2(s(k))の値が最小となるものを選び出す。
【０１５５】
上記のようにしてE1(s),E2(s),E3(s)の内のいずれかが最小値となるＮＤＣ系列を全てＳの中から選び出し、Pareto集合（初期系列集合）の要素とする。
【０１５６】
次に、ＮＤＣの入れ替え処理の詳細について説明する。ＮＤＣの入れ替え処理としては以下の（Ｓ１）〜（Ｓ３）を行う。
（Ｓ１）集合Γ(Ti)内を探索して、γσ(Ti,j1)とγ(Ti,j2)（ただしj1≠j2とする）の間に以下の関係が成り立つようなj2を求める。
e1(γσ(Ti,j1)) ＞ e1(γ(Ti,j2))
e2(γσ(Ti,j1)) ＞ e2(γ(Ti,j2))
e3(γσ(Ti,j1)) ＞ e3(γ(Ti,j2))
【０１５７】
上記の条件を満たすj2が見つかった場合は、γσ(Ti,j1)とγ(Ti,j2)を入れ替えることにより、γ(Ti,j2)をＮＤＣ系列σ内のタイムスロットTiに対応するＮＤＣとし、（Ｓ３）に進む。上記の条件を満たすj2が見つからないときには（Ｓ２）に進む。
【０１５８】
（Ｓ２）集合Γ(Ti)内を探索して、γσ(Ti,j1)とγ(Ti,j2)（ただしj1≠j2とする）の間に以下の関係が成り立つようなj2を求める。
【数１３】
2005293048.tif 000015
【０１５９】
ここで、I1,I2は整数集合[h|1≦h≦3]を共通部分の無い２つに分割した部分集合でh ∈ I1の時にeh(γσ(Ti,j1)) ≦ eh(γ(Ti,j2))であり、h ∈ I2の時にeh(γσ(Ti,j1)) ＞ eh(γ(Ti,j2))であり、また、Δeh = eh(γσ(Ti,j1))−eh(γ(Ti,j2))，δeh= eh(γ(Ti,j2))−eh(γσ(Ti,j1))である。
【０１６０】
上記の条件を満たすj2が見つかった場合は、γσ(Ti,j1)とγ(Ti,j2)を入れ替えることにより、γ(Ti,j2)をＮＤＣ系列σ内のタイムスロットTiに対応するＮＤＣとする。上記条件を満たすj2が見つからない場合は、タイムスロットTiについてはＮＤＣの入れ替えを行わない。ここで、λ1,λ2,λ3,Λ1,Λ2,Λ3の定義及び、φ1,φ2,φ3の値は以下の通りとする。
【０１６１】
λ1(x)＝x  λ2(x)＝x  λ3(x)＝0.1×exp(1.3x)
Λ1(x)＝x  Λ2(x)＝x  Λ3(x)＝0.1×exp(1.3x)
φ1＝1.0  φ2＝1.0  φ3＝1.0 
ただし、exp( )は自然対数の底を基数とする指数関数である。
【０１６２】
（Ｓ３）i = i+1として次のタイムスロットに移り、（Ｓ１）に戻る。
【０１６３】
次に、図３に示したバッチ計画部１２０の処理手順について説明する。バッチ型サービスの例としては、コンビニエンス・ストアの各店舗の売り上げ情報の集計処理のための計算サービスなどが考えられる。
【０１６４】
以下、ここでは、バッチ型原始サービスの集合をP=[pi|1≦i≦Np]、piの各ジョブのターンアラウンド時間をτi、データセンタciにおいて、ciに配置されている全サービスの負荷量の合計がピークとなる時の、ciの必要資源量を毎秒リクエスト数で表したものをRmax(ci)、データセンタciの資源の内、時刻ｔにおいてＷＥＢサービスに割り当てられずに残っている余剰計算資源量をR(ci,t)、単位サーバ性能の値をｆとし、他の記号の定義などはトランザクション計画部１１０の処理手順の説明に用いた時と同様とする。
【０１６５】
また、ここでは、piの各ジョブの投入時刻と予測期間の開始時刻との時間差はτiの整数倍であるとし、τiはトランザクション型サービスの負荷の計測周期の整数倍であるとする。
【０１６６】
また、バッチ型サービスに関する資源計画の生成では、ＮＤＣを評価する指標として、ＷＥＢサービスの資源計画生成で採用した評価指標の内、m1とm3のみを採用する。何故なら、バッチ型サービス同士がSOAP通信を行うことは通常はありえないので、サービス間のSOAP通信量に関する評価指標であるm2は考慮する意義がないからである。
【０１６７】
図１５は、図３に示したバッチ計画部１２０の処理手順を示すフローチャートである。同図に示すように、このバッチ計画部１２０は、まず、負荷量算出部１２１が、τ1,τ2,…,τNpの最小公倍数を求め、その値をタイムスロットの長さとする（ステップＳ２０１）。
【０１６８】
そして、時間軸をタイムスロットに分割し、1≦i≦Ncとなる各整数iについて、η(ci,t)=R(ci,t) / fとし、後述するジョブ・スケジューリング・アルゴリズムにより、各バッチ型原始サービスpi(1≦i≦Np)について、将来負荷変動を計画する（ステップＳ２０２）。なお、piに関する将来負荷変動は時系列データとして生成され、将来時刻ｔにおけるpiの負荷量をθ(i,t)と表す。
【０１６９】
そして、バッチ型派生サービス生成部１２２が負荷量算出部１２１が算出した負荷量に基づいてバッチ型派生サービスを発生させる（ステップＳ２０３）。なお、バッチ型派生サービス生成部１２２によるバッチ型派生サービス発生の詳細については後述する。
【０１７０】
そして、1≦i≦Ntとなる各整数iについて、Tiの期間中に発生すると予測された派生サービスの集合D(Ti)を生成する（ステップＳ２０４）。
【０１７１】
そして、バッチ型ＤＣ生成部１２３が、1≦i≦Ntとなる各整数iについて、D(Ti)に属する各派生サービスのデータセンタ群Ｃへの可能な配置組合せの全ての候補（ＤＣ）を木探索アルゴリズムによって生成し（ステップＳ２０５）、タイムスロットTiについて生成した配置組合せの候補の集合をΓ(Ti)とする。
【０１７２】
そして、バッチ型ＮＤＣ生成部１２４が、1≦i≦Ntとなる各整数i、1≦j≦ν(Ti)となる各整数jの全ての組み合わせについてγ(Ti,j)∈Γ(Ti)を評価指標m1で評価し、評価値e1を求める（ステップＳ２０６）。
【０１７３】
そして、1≦i≦Ntとなる各整数i、1≦j≦ν(Ti)となる各整数jの全ての組み合わせについて、e1(γ(Ti,j)) > 0.7ならばγ(Ti,j)をＶＤＣとし、集合Γ(Ti)から取り除く。そうでなければ、γ(Ti,j)をＮＤＣとし集合Γ(Ti)に残す（ステップＳ２０７）。
【０１７４】
そして、バッチ型最適解探索部１２５が、ＮＤＣ系列集合Ｓを作成し（ステップＳ２０８）、ＮＤＣ系列集合Ｓに含まれるＮＤＣ系列でｋ個の系列評価値E1(s),E3(s)のいずれか一つ以上が最小値をとるＮＤＣ系列ｓを全て探し出し、初期系列集合の要素とする（ステップＳ２０９）。
【０１７５】
ただし、
【数１４】
2005293048.tif 000016
とする。
【０１７６】
そして、初期系列集合に属するＮＤＣ系列を系列評価関数ξ(s)で評価し、その評価値が最小となるＮＤＣ系列を準最適ＮＤＣ系列σとする（ステップＳ２１０）。ただし、ξ(s)＝Ｋ1Ｅ1(s)＋Ｋ2Ｅ2(s)とする。また、K1=1.0, K3=0.1とした。
【０１７７】
そして、1≦i≦Ntとなる各整数iに対応するタイムスロットTiついて後述するＮＤＣの入れ替え処理を行う（ステップＳ２１１）。そして、ＮＤＣの入れ替えを行う前の準最適ＮＤＣ系列のξ( )での評価値と、ＮＤＣ入れ替え後の準最適ＮＤＣ系列のξ( )での評価値を用いて改善率を算出する（ステップＳ２１２）。
【０１７８】
そして、改善率が３％以下であるか否かを判定し（ステップＳ２１３）、改善率が３％以下なら現在の準最適ＮＤＣ系列を資源計画として出力し（ステップＳ２１４）、全ての処理を終える。そうでなければステップＳ２１１に戻る。
【０１７９】
次に、バッチ型原始サービスの将来負荷変動を計画するためのジョブ・スケジューリング・アルゴリズムについて説明する。各バッチ型原始サービスpi(1≦i≦Np)のジョブ投入スケジュールとターンアラウンド時間、デッドライン時刻が図１６の様であるとき、各バッチ型原始サービスpi(1≦i≦Np)について以下の（Ｓ１）〜（Ｓ９）を実行する。
【０１８０】
ただし、予測期間の開始時刻をt0とすると、任意のiとjについて、t(i,j)−t0 = TA(i)×Ｎ、TD(i)−t0 = TA(i)×N'（ただしＮおよびN'は整数）の関係が有り、TA(i)は計測周期の長さの整数倍であるものとする。また、単位サーバ性能をｆとする。
【０１８１】
（Ｓ１）j=ρ(i)とする。また、予測期間内の各時刻ｔにおいてθi(t)=0とする。
（Ｓ２）予測期間内の各時刻ｔにおいて、トランザクション型およびバッチ型のいかなるサービスにも割り当てられていないデータセンタck内の余剰資源量をR(ck,t)とした時のη(ck,t)=R(ck,t) / fを求める。
【０１８２】
（Ｓ３）時刻t(i,j)から時刻TD(i)までの時間帯を、TA(i)の長さのタイム・クォンタムに分割し、時刻t(i,j)から開始時刻の早い順に数えてｈ番目のタイム・クォンタムをQ(i,j,h)とする。またNQ(i,j)=(TD(i)−t(i,j))/TA(i)とする。
【０１８３】
（Ｓ４）1≦h≦NQ(i,j)となる各整数ｈと1≦k≦Ncとなる各整数ｋの組合せについて次の処理を行う。タイム・クォンタムQ(i,j,h)に含まれる複数の計測周期の中で計測周期の中心時刻ｔにおけるη(ck,t)の値が最小となる計測周期を求め、当該計測周期の中心時刻ｔの時のη(ck,t)の値をQ(i,j,h)における余剰資源量η(Q(i,j,h),ck)とする。
【０１８４】
（Ｓ５）1≦h≦NQ(i,j)となる各整数ｈについて、次の処理を行う。η(Q(i,j,h),ck)が最大となるような添字ｋの値を求め、これをk(i,j,h)とし、
【数１５】
2005293048.tif 000017
を計算する。
【０１８５】
（Ｓ６）η(i,j,h)の値を最大にするような添字ｈの値を求め、η(ck(i,j,h),t)から１を減算し、R(ck(i,j,h),t)からｆを減算する。
（Ｓ７） t(i,j)+TA(i)×ｈ ≦ t ≦ t(i,j)+TA(i)×(ｈ+1)となる各時刻ｔについてθi(t)= θi(t)＋ｆとする。
【０１８６】
（Ｓ８）n(i,j)から１を減算してn(i,j)>0なら（Ｓ５）へ戻る。
（Ｓ９）ｊが１なら処理を終了。そうでなければj = j−1として（Ｓ２）に戻る。
以上の手順実行の結果得られたθi(t)の値がバッチ型原始サービスpiの将来時刻ｔの時の将来負荷である。
【０１８７】
次に、バッチ型派生サービス生成部１２２によるバッチ型派生サービス生成の詳細について説明する。バッチ型派生サービス生成部１２２は、1≦i≦Ncとなる各整数iについて、以下の（Ｓ１）および（Ｓ２）を実行する。ここで、時刻ｔにおけるデータセンタciのWEBサービスによる負荷量の合計をg(ci,t)と表す。
【０１８８】
（Ｓ１）予測期間内の各計測周期において、次の処理を実行する。当該計測周期の中心時刻ｔにおいて、pj ⇒ ciとなる全ての添字ｊの集合をＪとした時に
【数１６】
2005293048.tif 000018
ならば、ph ⇒ ciとなるphの時刻ｔでの負荷量θ'(h,t)を
【数１７】
2005293048.tif 000019
とする。
【０１８９】
ただし、
【数１８】
2005293048.tif 000020
である。
【０１９０】
（Ｓ２）予測期間内の各計測周期において次の処理を実行する。当該計測周期の中心時刻をｔとした場合、pj ⇒ ciとなる全ての添字ｊの集合をＪとした時に
【数１９】
2005293048.tif 000021
ならば、ph⇒ciとなる各バッチ型原始サービスphから時刻ｔにおいてNc-1個のバッチ型派生サービスを発生させ、当該各バッチ型派生サービスの時刻ｔでの負荷量を以下のようにする。
【数２０】
2005293048.tif 000022
【０１９１】
次に、ＮＤＣの入れ替え処理の詳細について説明する。ＮＤＣの入れ替え処理としては、以下の（Ｓ１）〜（Ｓ３）を行う。
（Ｓ１）集合Γ(Ti)内を探索して、γσ(Ti,j1)とγ(Ti,j2)（ただしj1≠j2とする）の間に以下の関係が成り立つようなj2を求める。
e1(γσ(Ti,j1)) ＞ e1(γ(Ti,j2))
e3(γσ(Ti,j1)) ＞ e3(γ(Ti,j2))
【０１９２】
上記の条件を満たすj2が見つかった場合は、γσ(Ti,j1)とγ(Ti,j2)を入れ替えることにより、γ(Ti,j2)をＮＤＣ系列σ内のタイムスロットTiに対応するＮＤＣとし、（Ｓ３）に進む。上記の条件を満たすj2が見つからないときには（Ｓ２）に進む。
【０１９３】
（Ｓ２）集合Γ(Ti)内を探索して、γσ(Ti,j1)とγ(Ti,j2)（ただしj1≠j2とする）の間に以下の式（Ｓ２）または式（Ｓ３）のいずれか一方の関係が成り立つようなj2を求める。
【数２１】
2005293048.tif 000023
【数２２】
2005293048.tif 000024
【０１９４】
ただし、λ(x)=0.1×exp(1.3×ｘ)とした。上記の条件を満たすj2が見つかった場合は、γσ(Ti,j1)とγ(Ti,j2)を入れ替えることにより、γ(Ti,j2)をＮＤＣ系列σ内のタイムスロットTiに対応するＮＤＣとする。上記条件を満たすj2が見つからない場合は、タイムスロットTiについてはＮＤＣの入れ替えを行わない。
（Ｓ３）i = i+1として次のタイムスロットに移り、（Ｓ１）に戻る。
【０１９５】
次に、本実施例に係る資源計画作成装置１００による資源計画作成のシミュレーション結果について説明する。図１７は、本実施例に係る資源計画作成装置１００による資源計画作成のシミュレーション結果を示す図である。
【０１９６】
同図に示すように、データセンタＸのConsumerトラフィックが朝と夜の高負荷時に３分割されて、データセンタＹおよびデータセンタＺでも処理が行われている。また、データセンタＺの商店トラフィックが朝晩のピーク時に３分割されて、データセンタＸおよびデータセンタＹでも処理が行われている。
【０１９７】
上述してきたように、本実施例では、複数のデータセンタによって運用される複数のトランザクション型サービスに対して、トランザクション計画部１１０の予測部１１１が原始サービスの負荷予測を行い、派生サービス生成部１１２が予測部１１１による負荷予測およびデータセンタの計算資源量に基づいて派生サービスを生成し、最適解探索部１１５が派生サービス生成部１１２により生成された派生サービスに対する最適な資源計画を作成する。
【０１９８】
また、複数のデータセンタによって運用される複数のバッチ型サービスに対して、負荷量算出部１２１が原始サービスの負荷予測を行い、バッチ計画部１２０のバッチ型派生サービス生成部１２２が負荷量算出部１２１による負荷予測およびトランザクション型サービスの処理に使用されない計算資源量に基づいて派生サービスを生成し、バッチ型最適解探索部１２５が派生サービス生成部１２２により生成された派生サービスに対する最適な資源計画を作成する。
【０１９９】
従って、各データセンタに対して計算資源に応じた最適な負荷割り当てを行うことができるので、データセンタの過負荷を防ぐとともに、データセンタの計算資源を効率良く使用することができる。
【０２００】
また、このような資源計画の生成処理により、各派生サービスと発生元となった原始サービスとの間の負荷分配比率、および各派生サービスの発生時刻とその時の配置先データセンタが定まるので、データセンタ毎に予測期間内における原始サービス負荷と派生サービス負荷の合計量の時間変動推移が得られる。
【０２０１】
これを基に、各データセンタ毎に、負荷の変動に応じて派生サービスの発生を適切に行った場合の、当該データセンタのピーク時負荷量を見積もることができ、この見積もり負荷量は、派生サービスの発生を全く行わない場合や、各派生サービスの配置が不適切である場合の各データセンタのピーク時負荷量より小さい値とすることができる。
【０２０２】
また、本実施例では、資源計画作成装置１００だけで負荷予測、最適資源計画の作成および資源計画のデータセンタへの送信まで行う場合について説明したが、本発明はこれに限定されるものではなく、例えば負荷予測部１１１を他の装置で行う場合にも同様に適用することができる。
【０２０３】
また、本実施例では、資源計画作成装置について説明したが、この資源計画作成装置が有する構成をソフトウェアによって実現することで、同様の機能を有する資源計画作成プログラムを得ることができる。そこで、この資源計画作成プログラムを実行するコンピュータシステムについて説明する。
【０２０４】
図１８は、本実施例に係る資源計画作成プログラムを実行するコンピュータシステムを示す図である。同図に示すように、このコンピュータシステム２００は、本体部２０１と、本体部２０１からの指示により表示画面２０２ａに情報を表示するディスプレイ２０２と、このコンピュータシステム２００に種々の情報を入力するためのキーボード２０３と、ディスプレイ２０２の表示画面２０２ａ上の任意の位置を指定するマウス２０４と、ＬＡＮ２０６または広域エリアネットワーク（ＷＡＮ）に接続するＬＡＮインタフェースと、公衆回線２０７に接続するモデムとを有する。ここで、ＬＡＮ２０６は、他のコンピュータシステム（ＰＣ）２１１、サーバ２１２、プリンタ２１３などとコンピュータシステム２００とを接続している。
【０２０５】
また、図１９は、図１８に示した本体部２０１の構成を示す機能ブロック図である。同図に示すように、この本体部２０１は、ＣＰＵ２２１と、ＲＡＭ２２２と、ＲＯＭ２２３と、ハードディスクドライブ（ＨＤＤ）２２４と、ＣＤ−ＲＯＭドライブ２２５と、ＦＤドライブ２２６と、Ｉ／Ｏインタフェース２２７と、ＬＡＮインタフェース２２８と、モデム２２９とを有する。
【０２０６】
そして、このコンピュータシステム２００において実行される資源計画作成プログラムは、フロッピィディスク（ＦＤ）２０８、ＣＤ−ＲＯＭ２０９、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの可搬型記憶媒体に記憶され、これらの記憶媒体から読み出されてコンピュータシステム２００にインストールされる。
【０２０７】
あるいは、この資源計画作成プログラムは、ＬＡＮインタフェース２２８を介して接続されたサーバ２１２のデータベース、他のコンピュータシステム（ＰＣ）２１１のデータベースなどに記憶され、これらのデータベースから読み出されてコンピュータシステム２００にインストールされる。
【０２０８】
そして、インストールされた資源計画作成プログラムは、ＨＤＤ２２４に記憶され、ＲＡＭ２２２、ＲＯＭ２２３などを利用してＣＰＵ２２１により実行される。
【０２０９】
また、本実施例では、データセンタにサービスを配置する場合について説明したが、本発明はこれに限定されるものではなく、他の計算機クラスタにサービスを配置する場合にも同様に適用することができる。
【０２１０】
例えば、各データセンタの内部を構成する計算資源の集合が複数の区画に分割され、各区画毎に独立した運用管理がなされている場合である。この場合、各区画毎に、どの派生サービスをいつ何時配置するかについて最適化したり、どの区画で恒常的にどの原始サービスを運用するか定め、区画毎に、そこで運用する原始サービスから派生サービスを発生させる将来時点を決定するといったことも可能である。
【０２１１】
（付記１）複数の計算機から構成される計算機クラスタが複数接続されて構成される計算機クラスタシステムが運用する複数のサービスを該複数の計算機クラスタへ配置する資源計画を作成する資源計画作成プログラムであって、
運用される計算機クラスタが定められたサービスである原始サービスから該原始サービスの負荷予測に基づいて各計算機クラスタから他の計算機クラスタへ運用の一部が移される派生サービスを生成する派生サービス生成手順と、
前記派生サービス生成手順により生成された派生サービス群を前記複数の計算機クラスタへ配置する資源計画を所定の評価指標に基づいて作成する計画作成手順と、
をコンピュータに実行させることを特徴とする資源計画作成プログラム。
【０２１２】
（付記２）前記派生サービス生成手順は、前記負荷予測の予測期間を所定の時間間隔で複数のタイムスロットに分割したタイムスロット毎に派生サービスを生成し、
前記計画作成手順は、前記タイムスロット毎の派生サービスの配置計画であるタイムスロット配置計画を該タイムスロットの時刻順に並べた配置計画系列を前記資源計画として作成することを特徴とする付記１に記載の資源計画作成プログラム。
【０２１３】
（付記３）前記計画作成手順は、派生サービス群を前記複数の計算機クラスタへ最適に配置する資源計画をPareto最適性理論に基づいて作成することを特徴とする付記２に記載の資源計画作成プログラム。
【０２１４】
（付記４）前記計画作成手順は、計算機クラスタ間の負荷均等度と、時間軸上で隣接するタイムスロット間の前記タイムスロット配置計画の類似度とを評価指標として用いることを特徴とする付記３に記載の資源計画作成プログラム。
【０２１５】
（付記５）前記計画作成手順は、前記類似度と負荷均等度を評価指標とした場合に評価が最も良い配置計画系列を初期系列集合とし、該初期系列集合に含まれる配置計画系列に対して前記負荷均等度の評価がより良くなるような補正を行うことによって前記資源計画を作成することを特徴とする付記４に記載の資源計画作成プログラム。
【０２１６】
（付記６）前記計画作成手順により作成された資源計画を各計算機クラスタに送信する資源計画送信手順をさらにコンピュータに実行させることを特徴とする付記１〜５のいずれか一つに記載の資源計画作成プログラム。
【０２１７】
（付記７）前記計算機クラスタはデータセンタであり、前記計算機クラスタシステムは複数のデータセンタがネットワークを介して接続されたシステムであることを特徴とする付記１〜６のいずれか一つに記載の資源計画作成プログラム。
【０２１８】
（付記８）前記派生サービス生成手順は、
指定されたデッドライン時刻までに、サービスを構成する全てのジョブが処理完了されていれば、個々のジョブはいつ何時処理されても構わないことを特徴とするような非リアルタイム性のバッチ型サービスが計算機クラスタの集合で運用されている場合に、リアルタイム性を要求されるトランザクション型のサービスに対して計算機クラスタの資源を優先的に割り当て、残った余剰資源をバッチ型サービスに割り当てるために、トランザクション型サービスに対して資源計画の生成を行い、その後、割り当て対象とならなかった余剰資源についてバッチ型サービスの資源計画の生成を行う事を特徴とする付記１に記載の資源計画作成プログラム。
【０２１９】
（付記９）前記計画作成手順は、各バッチ型原始サービスを構成する全てのジョブを、その投入時刻がデッドライン時刻に近いものから順に実行計画の対象とし、いかなるサービスによっても使用されていない余剰計算資源の量の計算機クラスタ集合全体にわたる総和が最大となる期間に当該スケジューリング対象となったジョブの実行計画を生成する
ことを特徴とする付記１に記載の資源計画作成プログラム。
【０２２０】
（付記１０）複数の計算機から構成される計算機クラスタが複数接続されて構成される計算機クラスタシステムが運用する複数のサービスを該複数の計算機クラスタへ配置する資源計画を作成する資源計画作成プログラムを記録したコンピュータ読み取り可能な記録媒体であって、
運用される計算機クラスタが定められたサービスである原始サービスから該原始サービスの負荷予測に基づいて各計算機クラスタから他の計算機クラスタへ運用が移される派生サービスを生成する派生サービス生成手順と、
前記派生サービス生成手順により生成された派生サービスを前記複数の計算機クラスタへ配置する資源計画を所定の評価指標に基づいて作成する計画作成手順と、
をコンピュータに実行させる資源計画作成プログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【０２２１】
（付記１１）複数の計算機から構成される計算機クラスタが複数接続されて構成される計算機クラスタシステムが運用する複数のサービスを該複数の計算機クラスタへ配置する資源計画を作成する資源計画作成方法であって、
運用される計算機クラスタが定められたサービスである原始サービスから該原始サービスの負荷予測に基づいて各計算機クラスタから他の計算機クラスタへ運用の一部が移される派生サービスを生成する派生サービス生成工程と、
前記派生サービス生成工程により生成された派生サービス群を前記複数の計算機クラスタへ最適に配置する資源計画を所定の評価指標に基づいて作成する計画作成工程と、
を含んだことを特徴とする資源計画作成方法。
【０２２２】
（付記１２）複数の計算機から構成される計算機クラスタが複数接続されて構成される計算機クラスタシステムが運用する複数のサービスを該複数の計算機クラスタへ配置する資源計画を作成する資源計画作成装置であって、
運用される計算機クラスタが定められたサービスである原始サービスから該原始サービスの負荷予測に基づいて各計算機クラスタから他の計算機クラスタへ運用の一部が移される派生サービスを生成する派生サービス生成手段と、
前記派生サービス生成手段により生成された派生サービス群を前記複数の計算機クラスタへ最適に配置する資源計画を所定の評価指標に基づいて作成する計画作成手段と、
を備えたことを特徴とする資源計画作成装置。
【産業上の利用可能性】
【０２２３】
以上のように、本発明に係る資源計画作成プログラムは、複数のデータセンタへのサービス割り当てに有用であり、特に、過負荷をなくし、計算資源を有効利用する必要があるデータセンタに適している。
【図面の簡単な説明】
【０２２４】
【図１】本実施例に係る資源計画の概念を説明するための説明図である。
【図２】派生サービス発生と配置最適化を説明するための説明図である。
【図３】タイムスロット毎の派生サービスの配置最適化を説明するための説明図である。
【図４】本実施例に係る資源計画作成装置の構成を示す機能ブロック図である。
【図５−１】派生サービスの発生条件を説明するための説明図（１）である。
【図５−２】派生サービスの発生条件を説明するための説明図（２）である。
【図６−１】負荷の均等度合を説明するための説明図である。
【図６−２】ＮＤＣの類似度を説明するための説明図である。
【図７】最適化手順概略を説明するための説明図である。
【図８】ＮＤＣテーブルの概念を説明するための説明図である。
【図９】最適化ステップ（１）を説明するための説明図である。
【図１０】最適化ステップ（２）を説明するための説明図である。
【図１１−１】最適化ステップ（３）を説明するための説明図である。
【図１１−２】入れ替え条件を示す図である。
【図１２】最適化ステップ（４）を説明するための説明図である。
【図１３】図３に示したトランザクション計画部の処理手順を示すフローチャートである。
【図１４】互いにSOAP通信するサービス集合の例を示す図である。
【図１５】図３に示したバッチ計画部の処理手順を示すフローチャートである。
【図１６】バッチ型原始サービスのジョブ投入スケジュールの例を示す図である。
【図１７】本実施例に係る資源計画作成装置１００による資源計画作成のシミュレーション結果を示す図である。
【図１８】本実施例に係る資源計画作成プログラムを実行するコンピュータシステムを示す図である。
【図１９】図１８に示した本体部の構成を示す機能ブロック図である。
【符号の説明】
【０２２５】
１０1〜１０n    データセンタ
２０      インターネット
１００    資源計画作成装置
１１０    トランザクション計画部
１１１    予測部
１１２    派生サービス生成部
１１３    ＤＣ生成部
１１４    ＮＤＣ生成部
１１５    最適解探索部
１２０    バッチ計画部
１２１    負荷量算出部
１２２    バッチ型派生サービス生成部
１２３    バッチ型ＤＣ生成部
１２４    バッチ型ＮＤＣ生成部
１２５    バッチ型最適解探索部
１３０    資源計画送信部
２００，２１１    コンピュータシステム
２０１    本体部
２０２    ディスプレイ
２０２ａ    表示画面
２０３    キーボード
２０４    マウス
２０６    ＬＡＮ
２０７    公衆回線
２０８    フロッピィディスク
２０９    ＣＤ−ＲＯＭ
２１２    サーバ
２１３    プリンタ
２２１    ＣＰＵ
２２２    ＲＡＭ
２２３    ＲＯＭ
２２４    ハードディスクドライブ
２２５    ＣＤ−ＲＯＭドライブ
２２６    フロッピィディスクドライブ
２２７    Ｉ／Ｏインタフェース
２２８    ＬＡＮインタフェース
２２９    モデム
【図１】
2005293048.tif 000025
【図２】
2005293048.tif 000026
【図３】
2005293048.tif 000027
【図４】
2005293048.tif 000028
【図５−１】
2005293048.tif 000029
【図５−２】
2005293048.tif 000030
【図６−１】
2005293048.tif 000031
【図６−２】
2005293048.tif 000032
【図７】
2005293048.tif 000033
【図８】
2005293048.tif 000034
【図９】
2005293048.tif 000035
【図１０】
2005293048.tif 000036
【図１１−１】
2005293048.tif 000037
【図１１−２】
2005293048.tif 000038
【図１２】
2005293048.tif 000039
【図１３】
2005293048.tif 000040
【図１４】
2005293048.tif 000041
【図１５】
2005293048.tif 000042
【図１６】
2005293048.tif 000043
【図１７】
2005293048.tif 000044
【図１８】
2005293048.tif 000045
【図１９】
2005293048.tif 000046