(57)【要約】【課題】複数のサービスプロバイダに対して、複数の時点において最適な仮想資源を割り当てる。【解決手段】仮想資源を用いたネットワークサービスを提供する複数のサービスプロバイダからの複数の時点にわたる仮想資源の利用要求の中から、前記ネットワークサービスのサービス時間に応じて前記利用要求を選択する第１の選択部と、前記第１の選択部が選択した前記利用要求に応じた仮想資源を、所定の最適化問題における総コストの増加量が最小となるように物理資源に割り当てる割当部と、を有する。【選択図】図１
2018181117.tif 000002
【特許請求の範囲】
【請求項１】
仮想資源を用いたネットワークサービスを提供する複数のサービスプロバイダからの複数の時点にわたる仮想資源の利用要求の中から、前記ネットワークサービスのサービス時間に応じて前記利用要求を選択する第１の選択部と、
前記第１の選択部が選択した前記利用要求に応じた仮想資源を、所定の最適化問題における総コストの増加量が最小となるように物理資源に割り当てる割当部と、
を有する仮想資源割当装置。
【請求項２】
前記割当部が前記利用要求に応じた仮想資源を割り当てることができなかった場合、前記第１の選択部が選択した前記利用要求の前記サービス時間を第１のサービス時間と第２のサービス時間とに分割する分割部を有し、
前記割当部は、
前記第１のサービス時間に対応する第１の仮想資源と、前記第２のサービス時間に対応する第２の仮想資源とを、前記最適化問題における総コストの増加がそれぞれ最小となるように前記物理資源に割り当てる、請求項１に記載の仮想資源割当装置。
【請求項３】
前記第１の選択部は、
前記複数のサービスプロバイダからの複数の時点にわたる仮想資源の利用要求の中から、前記割当部が前記物理資源を割り当てていない前記利用要求であって、前記サービス時間が最大の前記利用要求を選択する、請求項１又は２に記載の仮想資源割当装置。
【請求項４】
前記割当部により前記利用要求に応じた仮想資源が前記物理資源に割り当てられた前記利用要求の中から、一の前記利用要求を選択する第２の選択部と、
前記第２の選択部が選択した前記利用要求の前記サービス時間を第３のサービス時間と第４のサービス時間とに分割し、該第３のサービス時間に対応する第３の仮想資源と、前記第４のサービス時間に対応する第４の仮想資源とを、前記最適化問題における総コストの増加がそれぞれ最小となるように前記物理資源に割り当てた場合に、前記総コストが減少するか否かを検証する検証部と、を有し、
前記割当部は、
前記検証部により前記総コストが減少すると検証された場合、前記第３のサービス時間に対応する第３の仮想資源と、前記第４のサービス時間に対応する第４の仮想資源とを、前記最適化問題における総コストの増加がそれぞれ最小となるように前記物理資源に割り当てる、請求項１乃至３の何れか一項に記載の仮想資源割当装置。
【請求項５】
仮想資源を用いたネットワークサービスを提供する複数のサービスプロバイダからの複数の時点にわたる仮想資源の利用要求の中から、前記ネットワークサービスのサービス時間に応じて前記利用要求を選択する選択手順と、
前記選択手順が選択した前記利用要求に応じた仮想資源を、所定の最適化問題における総コストの増加量が最小となるように物理資源に割り当てる割当手順と、
をコンピュータが実行する仮想資源割当方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想資源割当装置及び仮想資源割当方法に関する。
【背景技術】
【０００２】
近年、データセンタに設置された物理マシン（ＰＭ：Physical Machine）を仮想化して、物理マシン上で仮想マシン（ＶＭ：Virtual Machine）を稼働させることが行われている。また、データセンタに設置された物理マシン上で稼働する仮想マシンを地理的に離れた地点から利用して、各種演算サービスをユーザに提供するクラウドコンピューティングサービスが広く普及している。
【０００３】
このようなクラウドコンピューティングサービスを用いることで、ユーザは、必要なときだけ仮想マシンを起動して演算処理を行うことができるため、演算の需要に応じた経済的なマシン利用が可能となる。また、地理的に分散された複数のデータセンタで稼働する仮想マシンを利用することで、災害等によりサービスが利用できなくなる事態等を回避することができ、高いロバスト性も期待される。
【０００４】
また、近年では、複数のデータセンタ間を繋ぐネットワーク（ＮＷ：Network）のノード装置（例えばルータ等）やリンク設備をも仮想化する仮想化ＮＷ技術も知られている。そこで、物理マシンやネットワーク等の物理資源を構築して運用するインフラ事業者（ＩｎＰ：Infrastructure Provider）から、仮想マシンに加えて、複数のデータセンタ間やルータ間の仮想化ＮＷ資源も借り受けて、エンドユーザに対して様々なＮＷサービス（例えば、ＣＤＮ（Content Delivery Network）や情報セキュリティサービス、ＳＮＳ（Social Networking Service）等）を提供するサービスプロバイダ（ＳＰ：Service Provider）が普及することが予想される。インフラ事業者がサービスプロバイダに対して仮想マシンや仮想化ＮＷ資源等を提供するようなサービスの形態は、Ｂ２Ｂ２Ｘ型のサービスとも称される。
【０００５】
Ｂ２Ｂ２Ｘ型のサービスを実現するためには、インフラ事業者は、サービスプロバイダからの仮想マシンの利用要求（以下、「ＶＭデマンド」と表す。）に対して、仮想マシンを実際に稼働させる物理マシンと、物理マシン間や物理マシンとエンドユーザとの間を結ぶ物理ＮＷ資源とを割り当てる必要がある。サービスプロバイダは、インフラ事業者から借り受けた仮想マシンや仮想化ＮＷ資源を用いて、ビジネスとして様々なＮＷサービスをエンドユーザに提供する。このため、インフラ事業者には、例えばネットワーク遅延や仮想マシンのスペック等の各種品質に対して高い水準が要求され、仮想マシンの割り当て時にはサービスプロバイダが要求する条件を考慮する必要がある。
【０００６】
ここで、地理的に分散配置された複数のデータセンタ上に複数の物理マシンが設置されている場合に、或るデータセンタの或る物理マシン上で稼働中の仮想マシンを、他のデータセンタの他の物理マシン上に移動させるＶＭマイグレーションと呼ばれる技術が知られている。ＶＭマイグレーションにより、高負荷の物理マシン上の仮想マシンを、低負荷の物理マシン上に移動させることができる。これにより、物理マシンや物理ＮＷ資源の平準化を図ることができ、システム全体で収容可能な仮想マシン数の増加が期待される。
【０００７】
しかしながら、ＶＭマイグレーションを行うためには、稼働中の仮想マシンの処理を一旦中断させ、移動先の物理マシン上で新たに仮想マシンを起動した上で、仮想マシンのデータを移動させる必要がある。このため、ＶＭマイグレーションが行われた場合、インフラ事業者によるサービスは、一時的に中断する。一方で、仮想マシンをインフラ事業者から借り受けて、ビジネスとしてＮＷサービスをエンドユーザに提供するサービスプロバイダにとっては、仮想マシンの継続した高い稼働性が必要であることから、ＶＭマイグレーションの発生回数が少ないことが望ましい。
【０００８】
また、仮想マシンが割り当てられた物理マシンの位置と、当該仮想マシンを利用してＮＷサービスを提供するユーザ（サービスプロバイダ）の位置とが遠く離れている場合、サービス提供に際して、ネットワーク上の遅延時間が無視できない量となることがある。このため、例えば、リアルタイム性が高く、高いレスポンス性能が要求されるＮＷサービスを提供するサービスプロバイダにとっては、仮想マシンの割当ノードとユーザノードとの間の伝播遅延時間が小さなことが望ましい。
【０００９】
したがって、インフラ事業者は、ビジネスとしてＮＷサービスを提供するサービスプロバイダに対して、仮想マシン及び仮想ＮＷ資源を物理インフラ（物理マシン及び物理ＮＷ資源）上に割り当てる際には、各サービスプロバイダが要求するＶＭマイグレーション回数及びＮＷ伝播遅延の許容上限値を満たすような割り当てを行う必要がある。
【００１０】
これに対して、ＶＭマイグレーションの発生回数を最小化するＶＭ割当方式が知られている。また、単一の時点における総消費電力量を最小化したり、単一の時点における収容ＶＭ数を最大化したりするＶＭ割当方式が知られている。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】W. Shi, et al., An Online Mechanism for Dynamic Virtual Cluster Provisioning in Geo-Distributed Clouds, IEEE INFOCOM 2016.
【非特許文献２】T. Kuo, et al., Deploying Chains of Virtual Network Functions: On the Relation Between Link and Server Usage, INFOCOM 2016.
【非特許文献３】A. Beloglazob, et al., Managing Overloaded Hosts for Dynamic Consolidation of Virtual Machines in Cloud Data Centers under Quality of Service Constraints, IEEE Trans. Parallel and Distributed Systems, 24 (7), July 2013.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、上記のＶＭ割当方式では、複数のサービスプロバイダが存在する場合に、これら複数のサービスプロバイダそれぞれに対して、ＶＭマイグレーション回数の許容上限値を満たすような割り当てを行うことはできない。
【００１３】
また、上記のＶＭ割当方式では、システム全体のＶＭマイグレーション回数を最小化できるものの、例えば、或るサービスプロバイダについては多数のＶＭマイグレーションが発生する一方で、別の或るサービスプロバイダについてはＶＭマイグレーションがほとんど発生しないといった事態が発生し得る。このため、各サービスプロバイダ間の公平性が損なわれると共に、ＶＭマイグレーション回数の許容上限値を満たさないサービスプロバイダが発生し得る。
【００１４】
更に、上記のＶＭ割当方式では、単一の時点における総消費電力量の最小化や収容ＶＭ数の最大化といった観点で割り当てが行われるため、複数の時点にわたって最適な割り当てが行われるとは限らない。
【００１５】
本発明の実施の形態は、上記の点に鑑みてなされたもので、複数のサービスプロバイダに対して、複数の時点において最適な仮想資源を割り当てることを目的とする。
【課題を解決するための手段】
【００１６】
上記課題を解決するため、本発明の実施の形態における仮想資源割当装置は、仮想資源を用いたネットワークサービスを提供する複数のサービスプロバイダからの複数の時点にわたる仮想資源の利用要求の中から、前記ネットワークサービスのサービス時間に応じて前記利用要求を選択する第１の選択部と、前記第１の選択部が選択した前記利用要求に応じた仮想資源を、所定の最適化問題における総コストの増加量が最小となるように物理資源に割り当てる割当部と、を有する。
【発明の効果】
【００１７】
複数のサービスプロバイダに対して、複数の時点において最適な仮想資源を割り当てることができる。
【図面の簡単な説明】
【００１８】
【図１】本発明の実施の形態におけるＶＭ割当装置の構成の一例を示す図である。
【図２】本発明の実施の形態におけるＶＭ割当装置のハードウェア構成の一例を示す図である。
【図３】ＶＭが生成するトラヒック量の一例を説明する図である。
【図４】本発明の実施の形態におけるＶＭ割当処理の一例を示すフローチャートである。
【図５】本発明の実施の形態におけるＶＭ割当の更新処理の一例を示すフローチャートである。
【発明を実施するための形態】
【００１９】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００２０】
＜ＶＭ割当装置１０の構成＞
まず、本発明の実施の形態におけるＶＭ割当装置１０の構成について、図１を参照しながら説明する。図１は、本発明の実施の形態におけるＶＭ割当装置１０の構成の一例を示す図である。
【００２１】
図１に示すＶＭ割当装置１０は、複数のサービスプロバイダ２０からのＶＭデマンドに対して、当該ＶＭデマンドに応じた仮想マシンを物理マシンに割り当てるコンピュータである。ＶＭ割当装置１０は、例えば、インフラ事業者のシステム環境に設置等される。なお、仮想マシンは、仮想資源の一例である。
【００２２】
以降では、サービスプロバイダ２０の数を「Ｓ」であるものとし、Ｓ個のサービスプロバイダ２０のうちの任意の１つのサービスプロバイダ２０を表す場合、「サービスプロバイダ２０ｓ」（ｓ＝１，２，・・・，Ｓ）と表す。
【００２３】
図１に示すＶＭ割当装置１０は、ＶＭ割当処理部１００を有する。ＶＭ割当処理部１００は、ＶＭ割当装置１０にインストールされた１以上のプログラムが、後述するＣＰＵ（Central Processing Unit）１６に実行させる処理により実現される。
【００２４】
また、図１に示すＶＭ割当装置１０は、ＶＭデマンドデータ記憶部１１０と、ＳＰ要件データ記憶部１２０と、ＮＷデータ記憶部１３０と、ＰＭ・ＶＭデータ記憶部１４０と、ＶＭ割当データ記憶部１５０とを有する。これら各記憶部は、例えば、後述する補助記憶装置１８を用いて実現可能である。
【００２５】
ＶＭデマンドデータ記憶部１１０は、各サービスプロバイダ２０が仮想マシンを利用する拠点（ユーザ拠点）毎のＶＭデマンドを示すＶＭデマンドデータが記憶されている。ＶＭデマンドデータ記憶部１１０には、各サービスプロバイダ２０から送信されたＶＭデマンドデータが記憶されている。
【００２６】
ＳＰ要件データ記憶部１２０は、各サービスプロバイダ２０が許容するＶＭマイグレーション回数及びＮＷ遅延に関する制約上限を示すＳＰ要件データが記憶されている。ＳＰ要件データ記憶部１２０には、各サービスプロバイダ２０から送信されたＳＰ要件データが記憶されている。
【００２７】
ＮＷデータ記憶部１３０は、ネットワークのノードやリンクに関する情報を示すＮＷデータが記憶されている。
【００２８】
ＰＭ・ＶＭデータ記憶部１４０は、データセンタに設置されている物理マシンに関する情報や仮想マシンに関する情報を示すＰＭ・ＶＭデータが記憶されている。物理マシンに関する情報としては、例えば、物理マシンが有する物理資源（ＣＰＵや記憶装置等）の演算能力や記憶容量等の情報が挙げられる。また、仮想マシンに関する情報としては、例えば、物理マシンが有する物理資源の消費量を示す情報が挙げられる。なお、データセンタは、ネットワークのノードを構成する。
【００２９】
ＶＭ割当データ記憶部１５０は、ＶＭ割当処理部１００による割当結果（ＶＭデマンドに応じた仮想マシンの物理マシンへの割当結果）を示すＶＭ割当データが記憶される。
【００３０】
ＶＭ割当処理部１００は、各サービスプロバイダ２０からのＶＭデマンドに対して、複数の時点において物理マシンを割り当てる。すなわち、ＶＭ割当処理部１００は、ＶＭデマンドデータと、ＳＰ要件データと、ＮＷデータと、ＰＭ・ＶＭデータとに基づいて、各時点において、各サービスプロバイダ２０からのＶＭデマンドに対して、当該ＶＭデマンドに応じた仮想マシンを物理マシンに割り当てて、割当結果を示すＶＭ割当データをＶＭ割当データ記憶部１５０に記憶する。
【００３１】
これにより、各サービスプロバイダ２０は、各時点において仮想マシンが利用可能となる。言い換えれば、各サービスプロバイダ２０に対して、各時点における仮想マシンが割り当てられる。しかも、このとき、各時点において、各サービスプロバイダ２０が要求する制約条件等を満たした上で、最適な仮想マシンが割り当てられる。
【００３２】
なお、図１に示すＶＭ割当装置１０の構成は、一例であって、他の構成であっても良い。例えば、ＶＭ割当装置１０は、複数台のコンピュータで構成されていても良い。特に、ＶＭ割当処理部１００と、ＶＭデマンドデータ記憶部１１０と、ＳＰ要件データ記憶部１２０と、ＮＷデータ記憶部１３０と、ＰＭ・ＶＭデータ記憶部１４０と、ＶＭ割当データ記憶部１５０とが、それぞれ異なる装置で構成されていても良い。
【００３３】
＜ＶＭ割当装置１０のハードウェア構成＞
次に、本発明の実施の形態におけるＶＭ割当装置１０のハードウェア構成について、図２を参照しながら説明する。図２は、本発明の実施の形態におけるＶＭ割当装置１０のハードウェア構成の一例を示す図である。
【００３４】
図２に示すＶＭ割当装置１０は、入力装置１１と、表示装置１２と、外部Ｉ／Ｆ１３と、ＲＡＭ（Random Access Memory）１４と、ＲＯＭ（Read Only Memory）１５と、ＣＰＵ１６と、通信Ｉ／Ｆ１７と、補助記憶装置１８とを有する。これら各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。
【００３５】
入力装置１１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置１２は、例えばディスプレイ等であり、ＶＭ割当装置１０の処理結果を表示する。なお、ＶＭ割当装置１０は、入力装置１１及び表示装置１２の少なくとも一方を有していなくても良い。
【００３６】
外部Ｉ／Ｆ１３は、外部装置とのインタフェースである。外部装置には、記録媒体１３ａ等がある。ＶＭ割当装置１０は、外部Ｉ／Ｆ１３を介して、記録媒体１３ａ等の読み取りや書き込みを行うことができる。記録媒体１３ａには、ＶＭ割当処理部１００を実現する１以上のプログラム等が記録されていても良い。
【００３７】
記録媒体１３ａには、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等がある。
【００３８】
ＲＡＭ１４は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ１５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ１５には、例えば、ＯＳ（Operating System）設定やネットワーク設定等が格納されている。
【００３９】
ＣＰＵ１６は、ＲＯＭ１５や補助記憶装置１８等からプログラムやデータをＲＡＭ１４上に読み出して処理を実行する演算装置である。
【００４０】
通信Ｉ／Ｆ１７は、ＶＭ割当装置１０をネットワークに接続するためのインタフェースである。ＶＭ割当処理部１００を実現する１以上のプログラムは、通信Ｉ／Ｆ１７を介して、所定のサーバ装置等から取得（ダウンロード）されても良い。
【００４１】
補助記憶装置１８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置１８に格納されているプログラムやデータには、例えば、ＯＳ、当該ＯＳ上において各種機能を実現するアプリケーションプログラム、ＶＭ割当処理部１００を実現する１以上のプログラム等がある。
【００４２】
本発明の実施の形態におけるＶＭ割当装置１０は、図２に示すハードウェア構成を有することにより、後述する各種処理を実現することができる。
【００４３】
＜前提条件＞
本実施形態では、時間を固定長のタイムスロット（ＴＳ：Time Slot）に分割し、１≦ｔ≦ＴのＴ個の各タイムスロットにおいて、各サービスプロバイダ２０に対して、最適な仮想マシンを割り当てるものとする。また、各ＶＭデマンドデータは、各サービスプロバイダ２０の各タイムスロットｔにわたるＶＭデマンドであるものとする。更に、ネットワーク上を流れるパケットの遅延時間としては、経由ノードでの待ち時間と、経由ノードでの処理時間とは考慮せず、リンクの伝播遅延のみを考慮するものとする。
【００４４】
＜ネットワーク定義＞
ネットワークは、Ｎ個のノードと、Ｅ本のリンクとで構成されているものとする。また、各ノードｎの位置と、各リンクｅが接続する両端のノードＩＤと、各ノードのペア間に固定的に設定されたパケットの転送経路とが既知であるものとする。これらの情報は、ＮＷデータとして、ＮＷデータ記憶部１３０に記憶されている。
【００４５】
このとき、各リンクｅの距離に比例する電波遅延時間をｄｅ、リンクｅの伝送容量をＣｌｋ，ｅ、リンクｅの利用率ｘの関数として与えられるコスト関数をＫｌｋ（ｘ）とする。また、ノードｉからノードｊへの経路がリンクｅを経由する場合に「１」、当該リンクｅを経由しない場合に「０」となる二値関数をｒｉ，ｊ（ｅ）とする。
【００４６】
＜物理マシン及び仮想マシンの定義＞
全ての物理マシンは同一スペックであるものとし、各物理マシンは、Ｒ種類の物理資源を有するものとする。各物理マシンが有する物理資源の情報は、ＰＭ・ＶＭデータとして、ＰＭ・ＶＭデータ記憶部１４０に記憶されている。
【００４７】
このとき、各物理資源ｒの容量をＣｐｍ，ｒ、各物理資源ｒの利用率ｘｒの関数として与えられる物理マシンのコスト関数をＫｐｍ（ｘ１，・・・，ｘＲ）とする。
【００４８】
また、上記のＲ種類の各物理資源ｒの消費量が異なるＨ種類の仮想マシンが存在するものとし、各仮想マシンｈの物理資源ｒの消費量をＺｈ，ｒとする。各仮想マシンｈの物理資源ｒの消費量Ｚｈ，ｒを示す情報は、ＰＭ・ＶＭデータとして、ＰＭ・ＶＭデータ記憶部１４０に記憶されている。
【００４９】
＜ＶＭデマンド＞
地理的に分散配置されたＮ個のユーザ拠点（サービスプロバイダ２０が仮想マシンを利用する拠点）を考え、ユーザ拠点ｕに収容されたサービスプロバイダ２０ｓのエンドユーザの集合をＵｓ（ｕ）とする。
【００５０】
このとき、サービスプロバイダ２０ｓが各ユーザ拠点ｕのエンドユーザ集合Ｕｓ（ｕ）に対してサービスを提供するためのＶＭデマンドの集合をＭｓ（ｕ）とする。そして、ＶＭデマンド集合Ｍｓ（ｕ）に含まれる各ＶＭデマンドｋは、開始タイムスロット
【００５１】
【数１】
2018181117.tif 000003
と、終了タイムスロット
【００５２】
【数２】
2018181117.tif 000004
と、仮想マシン種別Ｈｓ（ｕ，ｋ）とで表されるものとする。各ＶＭデマンドｋを示す情報は、ＶＭデマンドデータとして、ＶＭデマンドデータ記憶部１１０に記憶されている。
【００５３】
また、各タイムスロットｔにおいて、種別ｈの各仮想マシンからエンドユーザに対して発生するサービスプロバイダ２０ｓのトラヒック量をＲｓ，ｈとする。更に、各タイムスロットｔにおいて、ノードｖ１とノードｖ２との間で発生するサービスプロバイダ２０ｓのトラヒック量をＱｓ，ｈ（ｖ１，ｖ２，ｔ）とする。
【００５４】
このとき、サービスプロバイダ２０ｓの仮想マシンが生成するトラヒック量は、Ｒｓ，ｈと、Ｑｓ，ｈ（ｖ１，ｖ２，ｔ）とで表される。
【００５５】
例えば、図３に示すように、ノードｖａに収容されたエンドユーザの集合をＵｓ（Ａ）、当該Ｕｓ（Ａ）に対してサービスを提供するための仮想マシンを「ＶＭ１」、「ＶＭ２」及び「ＶＭ３」とする。このとき、ノードｖａのＶＭ１と、ノードｖｂのＶＭ２との間のトラヒック量はＱｓ，ｈ（ｖａ，ｖｂ，ｔ）となる。同様に、ノードｖａのＶＭ１と、ノードｖｃのＶＭ３との間のトラヒック量はＱｓ，ｈ（ｖａ，ｖｃ，ｔ）となる。また、同様に、ノードｖｂのＶＭ２と、ノードｖｃのＶＭ３との間のトラヒック量はＱｓ，ｈ（ｖｂ，ｖｃ，ｔ）となる。
【００５６】
＜ＳＰ要件＞
サービスプロバイダ２０ｓに割り当てられた種別ｈの仮想マシンからエンドユーザに対するトラヒックの転送遅延時間の制約上限をＤｓ，ｈとする。また、サービスプロバイダ２０ｓに割り当てられた種別ｈの仮想マシンのタイムスロットｔ＝１〜ＴにわたるＶＭマイグレーション回数（総ＶＭマイグレーション回数）の制約上限をＬｓとする。これらの制約上限を示す情報は、ＳＰ要件データとして、ＳＰ要件データ記憶部１２０に記憶されている。
【００５７】
＜ＶＭ割当問題の定式化＞
以降では、各サービスプロバイダ２０ｓのＶＭマイグレーション回数の制約上限Ｌｓと、転送遅延時間の制約上限Ｄｓ，ｈと、リンク及び物理マシンの容量制約とを満たす条件の下で、Ｔ個のタイムスロットｔにおける総コストが最小となるように、各タイムスロットｔにおいて、Ｓ個のサービスプロバイダ２０ｓからの各ＶＭデマンドに対して、当該ＶＭデマンドに応じた仮想マシンを物理マシンに割り当てる問題を定式化する。
【００５８】
まず、タイムスタンプｔ内において、Ｍｓ（ｕ）に含まれるＶＭデマンドｋに応じた仮想マシンｋ（すなわち、ＶＭデマンドｋに応じて稼働する仮想マシンｋ）が利用する物理マシンを、ノードｘ１（ｓ，ｕ，ｋ，ｔ）の物理マシンｘ２（ｓ，ｕ，ｋ，ｔ）と表す。当該ＶＭデマンドｋに対して、これらｘ１（ｓ，ｕ，ｋ，ｔ）及びｘ２（ｓ，ｕ，ｋ，ｔ）を設定することが、仮想マシンｋを物理マシンに割り当てることに相当する。
【００５９】
このとき、タイムスタンプｔ内において、ノードｎ＝ｘ１（ｓ，ｕ，ｋ，ｔ）の物理マシンｍ＝ｘ２（ｓ，ｕ，ｋ，ｔ）における資源ｒの使用量Ｙ１（ｎ，ｍ，ｒ，ｔ）は、次の（式１）で表すことができる。
【００６０】
【数３】
2018181117.tif 000005
ただし、Ｍｓ，ｕは、Ｍｓ（ｕ）に含まれるＶＭデマンド数である。また、δ（ｃ）は、条件ｃを満たす場合に「１」、条件ｃを満たさない場合に「０」となる二値関数である。
【００６１】
ここで、ノードｎの仮想マシンからノードｕのエンドユーザにタイムスタンプｔ内で送信される総トラヒック量をＧ１（ｎ，ｕ，ｔ）とする。このとき、Ｇ１（ｎ，ｕ，ｔ）は、以下の（式２）で表すことができる。
【００６２】
【数４】
2018181117.tif 000006
また、ノードａの仮想マシンからノードｂの仮想マシンに対してタイムスロットｔ内で送信される総トラヒック量をＧ２（ｎ，ｕ，ｔ）とする。このとき、Ｇ２（ｎ，ｕ，ｔ）は、以下の（式３）で表すことができる。
【００６３】
【数５】
2018181117.tif 000007
また、上記のＧ１とＧ２とを用いて、タイムスロットｔ内において、リンクｅ上で発生するトラヒック量Ｙ２（ｅ，ｔ）は、以下の（式４）で表すことができる。
【００６４】
【数６】
2018181117.tif 000008
上記の（式１）〜（式４）を用いて、以下の（式５）〜（式９）の最適化問題を定義することができる。
【００６５】
【数７】
2018181117.tif 000009
ただし、Δ（ａ，ｂ）は、ａ＝ｂの場合に「０」、ａ≠ｂの場合に「１」となる二値関数である。上記の（式６）は、各物理マシンの各物理資源の使用量がその容量以下となることを示す制約式である。上記の（式７）は、各リンクの使用量がその容量以下となることを示す制約式である。上記の（式８）は、各仮想マシンからエンドユーザへのトラヒック転送遅延が制約上限以下となることを示す制約式である。上記の（式９）は、各サービスプロバイダ２０の総ＶＭマイグレーション回数が制約上限以下となることを示す制約式である。
【００６６】
＜処理の詳細＞
次に、本発明の実施の形態におけるＶＭ割当装置１０の処理の詳細について説明する。本発明の実施の形態におけるＶＭ割当装置１０の処理では、貪欲算法により、上記の（式５）〜（式９）で定義した最適化問題の解を得ることで、ＶＭデマンドに応じた仮想マシンが物理マシンに割り当てられる。当該処理は、全てのＶＭデマンドが未割当の状態において各ＶＭデマンドに応じた仮想マシンを物理マシンに割り当てる「ＶＭ割当処理」と、ＶＭ割当処理後の割当状態から総コストを更に低減するために当該割当状態を更新する「ＶＭ割当処理の更新処理」とで構成される。
【００６７】
≪ＶＭ割当処理≫
まず、各ＶＭデマンドに応じた仮想マシンを物理マシンに割り当てる処理について、図４を参照しながら説明する。図４は、本発明の実施の形態におけるＶＭ割当処理の一例を示すフローチャートである。
【００６８】
まず、ＶＭ割当処理部１００は、初期状態として、全てのＶＭデマンドを未割当の状態に設定する（ステップＳ１０１）。すなわち、ＶＭ割当処理部１００は、初期状態として、ＶＭデマンドデータ記憶部１１０に記憶されている全てのＶＭデマンドデータがそれぞれ示すＶＭデマンドの割当状態を未割当とする。
【００６９】
次に、ＶＭ割当処理部１００は、未割当のＶＭデマンドの中から、サービス時間が最大のＶＭデマンドをランダムに１つ選択する（ステップＳ１０２）。ここで、サービス時間とは、ＶＭデマンドの終了タイムスロットと開始タイムスロットとの差である。
【００７０】
次に、ＶＭ割当処理部１００は、上記の（式５）〜（式９）で定義した最適化問題の総コストＣの増加量が最小となるように、上記のステップＳ１０２で選択されたＶＭデマンドに応じた仮想マシンを物理マシンに割り当てる（ステップＳ１０３）。
【００７１】
すなわち、ＶＭ割当処理部１００は、当該選択されたＶＭデマンドに応じた仮想マシンを、当該最適化問題の総コストＣの増加量が最小となる解が示すノードの物理マシンに割り当てる。そして、ＶＭ割当処理部１００は、割当結果を示すＶＭ割当データをＶＭ割当データ記憶部１５０に記憶する。
【００７２】
次に、ＶＭ割当処理部１００は、上記のステップＳ１０３で仮想マシンが物理マシンに割り当てられたか否かを判定する（ステップＳ１０４）。なお、仮想マシンが物理マシンに割り当てることができない場合とは、例えば、物理資源の空き容量が不足している場合等である。
【００７３】
ステップＳ１０４において、仮想マシンが割り当てられたと判定された場合、ＶＭ割当処理部１００は、後述するステップＳ１０９に進む。
【００７４】
一方で、ステップＳ１０４において、仮想マシンが割り当てられなかったと判定された場合、ＶＭ割当処理部１００は、上記のステップＳ１０２で選択されたＶＭデマンドのサービス時間を任意の時点ｔで分割する（ステップＳ１０５）。すなわち、ＶＭ割当処理部１００は、当該選択されたＶＭデマンドの開始タイムスロットと、終了タイムスロットとの間の任意の時点ｔでサービス時間を分割する。
【００７５】
次に、ＶＭ割当処理部１００は、上記の（式５）〜（式９）で定義した最適化問題の総コストＣの増加量が最小となるように、上記のステップＳ１０５で分割されたＶＭデマンドそれぞれに応じた仮想マシンを物理マシンに割り当てる（ステップＳ１０６）。
【００７６】
すなわち、分割後のＶＭデマンドを「ＶＭデマンド１」及び「ＶＭデマンド２」とした場合、ＶＭ割当処理部１００は、ＶＭデマンド１に応じた仮想マシン１を、当該最適化問題の総コストＣの増加量が最小となる解が示すノードの物理マシンに割り当てると共に、ＶＭデマンド２に応じた仮想マシン２を、当該最適化問題の総コストＣの増加量が最小となる解が示すノードの物理マシンに割り当てる。そして、ＶＭ割当処理部１００は、割当結果を示すＶＭ割当データをＶＭ割当データ記憶部１５０に記憶する。
【００７７】
次に、ＶＭ割当処理部１００は、上記のステップＳ１０６で仮想マシンが共に物理マシンに割り当てられたか否かを判定する（ステップＳ１０７）。
【００７８】
ステップＳ１０７において、仮想マシンが共に物理マシンに割り当てられたと判定された場合、ＶＭ割当処理部１００は、後述するステップＳ１０９に進む。
【００７９】
ステップＳ１０７において、少なくとも１つの仮想マシンが割り当てられなかったと判定された場合、ＶＭ割当処理部１００は、上記のステップＳ１０２で選択されたＶＭデマンドの割当をスキップする（ステップＳ１０８）。この場合、ＶＭ割当処理部１００は、割当をスキップしたことを示すＶＭ割当データをＶＭ割当データ記憶部１５０に記憶する。
【００８０】
なお、ＶＭデマンドの割当がスキップされた場合、当該ＶＭデマンドに応じた仮想マシンは物理マシンに割り当てられない。これは、例えば、当該ＶＭデマンドのＳＰ要件（ネットワーク遅延等）を満足することができない場合や当該ＶＭデマンドが要求する種別の物理マシンを割り当てることができない場合（例えば、当該物理マシンへの経路が輻輳している場合等）が挙げられる。また、例えば、当該ＶＭデマンドが極端に大量の物理資源を要求するような場合も同様となることが有り得る。
【００８１】
次に、ＶＭ割当処理部１００は、全てのＶＭデマンドを選択されたか否かを判定する（ステップＳ１０９）。すなわち、ＶＭ割当処理部１００は、全てのＶＭデマンドについて割当が試行されたか否かを判定する。
【００８２】
ステップＳ１０９において、全てのＶＭデマンドが選択されたと判定された場合、ＶＭ割当処理部１００は、処理を終了する。一方で、ステップＳ１０９において、全てのＶＭデマンドが選択されたと判定されなかった場合、ＶＭ割当処理部１００は、ステップＳ１０２に戻る。これにより、ＶＭ割当処理部１００により、未割当の全てのＶＭデマンドに対して、物理マシンの割り当て又は割り当てのスキップのいずれかが行われる。
【００８３】
以上により、本発明の実施の形態におけるＶＭ割当装置１０は、各サービスプロバイダ２０からのＶＭデマンドに応じて、複数の時点にわたるＶＭ収容率の最大化や総消費電力の最小化等の単一の目的関数を最適化するように、仮想マシンを物理マシンに割り当てることができる。
【００８４】
≪ＶＭ割当の更新処理≫
次に、上記で説明したＶＭ割当処理が行われた後の割当状態に対して、総コストを更に低減するために、当該割当状態を更新する処理について、図５を参照しながら説明する。図５は、本発明の実施の形態におけるＶＭ割当の更新処理の一例を示すフローチャートである。以降では、各ＶＭデマンドの割当状態は、図４に示すＶＭ割当処理が実行された後の状態であるものとする。
【００８５】
まず、ＶＭ割当処理部１００は、図４に示すＶＭ割当処理が実行された後の割当状態のＶＭデマンドの中から、ＶＭデマンドをランダムに１つ選択する（ステップＳ２０１）。このとき、ＶＭ割当処理部１００は、図４に示すＶＭ割当処理が実行された後の割当状態のＶＭデマンドの中から、割り当てがスキップされたＶＭデマンドを除くＶＭデマンドをランダムに選択すれば良い。ただし、これに限られず、ＶＭ割当処理部１００は、割り当てがスキップされたＶＭデマンドも含めて、ＶＭデマンドをランダムに選択しても良い。
【００８６】
次に、ＶＭ割当処理部１００は、上記のステップＳ２０１で選択されたＶＭデマンドのサービス時間を任意の時点ｔで分割し、上記の（式５）〜（式９）で定義した最適化問題の総コストＣの増加量が最小となるように、分割したＶＭデマンドに応じた仮想マシンを物理マシンに割り当てた場合に、総コストＣが減少するか否かを検証する（ステップＳ２０２）。
【００８７】
すなわち、ＶＭ割当処理部１００は、当該選択されたＶＭデマンドのサービス時間を任意の時点ｔで分割したＶＭデマンドを「ＶＭデマンド１」及び「ＶＭデマンド２」と仮定したとする。このとき、ＶＭ割当処理部１００は、ＶＭデマンド１に応じた仮想マシン１を、当該最適化問題の総コストＣの増加量が最小となる解が示すノードの物理マシンに割り当てたと仮定すると共に、ＶＭデマンド２に応じた仮想マシン２を、当該最適化問題の総コストＣの増加量が最小となる解が示すノードの物理マシンに割り当てたと仮定する。この場合に、ＶＭ割当処理部１００は、図４に示すＶＭ割当処理が実行された後の割当状態に対して、総コストＣが減少するか否かを検証する。
【００８８】
次に、ＶＭ割当処理部１００は、上記のステップＳ２０２における検証結果が、総コストが減少することを示す検証結果であるか否かを判定する（ステップＳ２０３）。
【００８９】
ステップＳ２０３において、総コストが減少しないことを示す検証結果であると判定された場合、ＶＭ割当処理部１００は、後述するステップＳ２０５に進む。
【００９０】
一方で、ステップＳ２０３において、総コストが減少することを示す検証結果であると判定された場合、ＶＭ割当処理部１００は、上記のステップＳ２０２で仮定した分割及び割り当てを実際に実行する（ステップＳ２０４）。そして、ＶＭ割当処理部１００は、上記のステップＳ２０１で選択されたＶＭデマンドに対応するＶＭ割当データを、ステップＳ２０４で実行した割当結果を示すＶＭ割当データに更新する。これにより、総コストの更なる低減を図ることができる。
【００９１】
次に、ＶＭ割当処理部１００は、予め設定された所定の回数、上記のステップＳ２０１〜ステップＳ２０４の処理を実行したか否かを判定する（ステップＳ２０５）。
【００９２】
ステップＳ２０５において、予め設定された所定の回数、上記のステップＳ２０１〜ステップＳ２０４の処理を実行したと判定された場合、ＶＭ割当処理部１００は、処理を終了する。一方で、ステップＳ２０５において予め設定された所定の回数、上記のステップＳ２０１〜ステップＳ２０４の処理を実行したと判定されなかった場合、ＶＭ割当処理部１００は、ステップＳ２０１に戻る。これにより、ＶＭ割当処理部１００により、予め設定された所定の回数、上記のステップＳ２０１〜ステップＳ２０４の処理が実行される。
【００９３】
以上により、本発明の実施の形態におけるＶＭ割当装置１０は、図４に示すＶＭ割当処理が実行された後の割当状態を更新することで、総コストを更に削減した割り当てを行うことができるようになる。
【００９４】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【００９５】
１０        ＶＭ割当装置
２０        サービスプロバイダ
１００      ＶＭ割当処理部
１１０      ＶＭデマンドデータ記憶部
１２０      ＳＰ要件データ記憶部
１３０      ＮＷデータ記憶部
１４０      ＰＭ・ＶＭデータ記憶部
１５０      ＶＭ割当データ記憶部
【図１】
2018181117.tif 000010
【図２】
2018181117.tif 000011
【図３】
2018181117.tif 000012
【図４】
2018181117.tif 000013
【図５】
2018181117.tif 000014