(57)【特許請求の範囲】
【請求項１】
強化学習を用いて仮想マシンのリソースを管理するリソース管理装置であって、
仮想マシンへのリソースの割り当てを行う制御を行動とし、該行動によってリソースが割り当てられた割り当て状態における当該仮想マシンの性能に基づく報酬値を用いた強化学習によって、前記割り当て状態における前記制御の評価値である制御評価値を求める状態管理部を備え、
前記状態管理部は、
前記割り当て状態が適当か否かを前記制御評価値に基づいて判定する判定機能と、
適当でないと判定された前記割り当て状態を分割して新たな割り当て状態を生成する分割機能と、
適当であると判定された前記割り当て状態のうちのリソースに対する前記行動が一致する複数の割り当て状態を１つの割り当て状態に集約する集約機能と、
を備え、
前記集約機能は、１つのリソースのみが異なる２つの割り当て状態が存在し、前記２つの割り当て状態で異なる前記１つのリソースのうちの一方の割り当て状態のリソースの下限と他方の割り当て状態のリソースの上限とが一致する場合に、前記２つの割り当て状態を１つの割り当て状態に集約する、リソース管理装置。
【請求項２】
強化学習を用いて仮想マシンのリソースを管理するリソース管理装置が実行するリソース管理方法であって、
仮想マシンへのリソースの割り当てを行う制御を行動とし、該行動によってリソースが割り当てられた割り当て状態における当該仮想マシンの性能に基づく報酬値を用いた強化学習によって、前記割り当て状態における前記制御の評価値である制御評価値を求める状態管理手順を有し、
前記状態管理手順は、
前記割り当て状態が適当か否かを前記制御評価値に基づいて判定する判定手順と、
適当でないと判定された前記割り当て状態を分割して新たな割り当て状態を生成する分割手順と、
適当であると判定された前記割り当て状態のうちのリソースに対する前記行動が一致する複数の割り当て状態を１つの割り当て状態に集約する集約手順と、
を含み、
前記集約手順では、１つのリソースのみが異なる２つの割り当て状態が存在し、前記２つの割り当て状態で異なる前記１つのリソースのうちの一方の割り当て状態のリソースの下限と他方の割り当て状態のリソースの上限とが一致する場合に、前記２つの割り当て状態を１つの割り当て状態に集約する、リソース管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、１台のサーバ上にて、仮想化基盤（ｅ．ｇ．ハイパーバイザ）上に起動している複数の仮想マシン（ｅ．ｇ．ＶＭ）に対して、各仮想マシン毎に設定されたＳＬＡ（Ｓｅｒｖｉｃｅ  Ｌｅｖｅｌ  Ａｇｒｅｅｍｅｎｔ）や優先度をもとに、刻々と変化する各仮想マシンに対する負荷に対応して、ＣＰＵやメモリのリソースを割り当てる手法に関する。
【背景技術】
【０００２】
汎用サーバ性能の向上、および、仮想化技術の台頭により、単なるパケット転送機能だけでなく、ＩＤＳやファイアウォール、ロードバランサーといった、特殊なハードウェア機器（ミドルボックス）を用いなければ実現できなかった機能が、ソフトウェア化され、汎用サーバ上の仮想マシン（以下ＶＭ）にて実現されようとしている。ミドルボックスをＶＭにて管理することで、ハードウェア機器への設備投資を削減することができるだけでなく、ネットワークの管理ポリシーを変更する場合でも、マイグレーション機能を用いて、ＶＭの移動や複製を行うことで、容易にポリシーを反映できると考えられている［例えば、非特許文献１、２参照。］。こうした利点がある一方、仮想環境を用いたミドルボックスの運用では、その挙動や性能（ｅ．ｇ．スループット）やＳＬＡ（Ｓｅｒｖｉｃｅ  Ｌｅｖｅｌ  Ａｇｒｅｅｍｅｎｔ）が保証されていないという問題点がある［例えば、非特許文献３参照。］。例えば、ＶＭの性能は、割り当てられたリソース（ｅ．ｇ．コア、メモリなど。）以外にも、ＶＭが動作する物理サーバの構造や、他に稼働しているＶＭの状態、ＶＭ毎に設定される優先度に依存することが知られており、ＶＭがどの程度のスループットがどの程度出るか、未知数となっている［例えば、非特許文献４参照。］。また、ミドルボックスを稼働しているＶＭへのリソース割り当ては慎重に行わなければならないという問題点もある。なぜなら、ミドルボックスは、ネットワークの根幹となる機能であり、ＶＭ間のリソース割り当てを正しく行わなければ、ネットワーク全体の可用性に影響を与える可能性がある［例えば、非特許文献５参照。］。例えば、Ｇｏｏｇｌｅのデータセンタにて、ネットワーク資源割り当てを行うミドルボックスの故障により、最大で４０％のユーザに対する複数のサービスが停止した例も存在する［例えば、非特許文献６参照。］。ミドルボックスの仮想化が進むにつれ、膨大な数のミドルボックスが仮想環境下で動作することが予想されている［例えば、非特許文献１参照。］。その運用は人手では到底できなくなってきており、高信頼かつ高可用性を持つ、自律的なリソース割り当て方法が必要であると考えられている。
【０００３】
汎用サーバ上の複数のＶＭに対して、物理リソース（ＣＰやメモリ）を割り当てる方法は膨大に存在しており、ＶＭのＣＰＵ利用率やメモリ使用量に応じたリソース割り当て手法が多数提案されている。中でも、割り当てたリソースと、当該リソース割り当てにて達成されたスープットの関係をマルコフ遷移にて表現することで、強化学習と呼ばれる機械学習を用いて、ＶＭのスループットが高くＳＬＡ違反の少ない時に最大値をとる目的関数を全てのＶＭにて最大化するリソース割り当て手法が発見されており、強化学習を用いたリソース割り当てが注目されるようになった［例えば、非特許文献７、８参照。］。強化学習では、各ＶＭに対するリソース割り当てと、各割り当てにおいて新たな割り当てを行った際のＶＭのスループットとＳＬＡ違反の値（回数）を全て記憶しておく必要があり、各状態における最適な割り当て方法を一意に決定するまでに、膨大な時間と物理メモリが必要となる。
【０００４】
非特許文献７、８の強化学習を用いた手法では、あらかじめ設定された目的関数を各状態にて最大化するために、リソース割り当て状態を入力とし、教師信号としてスループットの変化量やＳＬＡ違反率を用いたニューラルネットワークを適用する手法が提案されている［例えば、非特許文献８参照。］。また、当該目的関数を線形モデルや多項式モデルに帰着し、当該モデルの係数をスループットの最大化やＳＬＡ違反率を最小化するように最適化する手法を提案されている［例えば、非特許文献９参照。］。これらの手法は、各ＶＭへのリソース割り当て状態とその状態におけるスループット等を記録する必要がないため、省メモリにてリソース割り当ての自動化を達成することができる。しかしながら、全ての状態に対して、高いスループットを達成する保証はなく、特定の状態にて、ミドルボックスの機能停止を起こすようなリソース割り当てを行う可能性がある［例えば、非特許文献１０参照。］。これらの可能性を排除するためには、全ての状態におけるリソース割り当て方針を検証する必要があるため、その検証時間が膨大になるという問題がある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｖ．  Ｓｅｋａｒ，  Ｎ．  Ｅｇｉ，  Ｓ．  Ｒａｔｎａｓａｍｙ，  Ｍ．Ｋ．  Ｒｅｉｔｅｒ，  ａｎｄ  Ｇ．  Ｓｈｉ，  “Ｄｅｓｉｇｎ  ａｎｄ  ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｆ  ａ  ｃｏｎｓｏｌｉｄａｔｅｄ  ｍｉｄｄｌｅｂｏｘ  ａｒｃｈｉｔｅｃｔｕｒｅ，”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ９ｔｈ  ＵＳＥＮＩＸＣｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｎｅｔｗｏｒｋｅｄ  Ｓｙｓｔｅｍｓ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，  ＮＳＤＩ’１２，  Ｂｅｒｋｅｌｅｙ，  ＣＡ，  ＵＳＡ，  ｐｐ．３２３−３３６，  ＵＳＥＮＩＸ  Ａｓｓｏｃｉａｔｉｏｎ，  ２０１２．
【非特許文献２】Ａ．  Ｇｅｍｂｅｒ，  Ｐ．  Ｐｒａｂｈｕ，  Ｚ．  Ｇｈａｄｉｙａｌｉ，  ａｎｄ  Ａ．  Ａｋｅｌｌａ，  “Ｔｏｗａｒｄ  ｓｏｆｔｗａｒｅ−ｄｅｆｉｎｅｄ  ｍｉｄｄｌｅｂｏｘ  ｎｅｔｗｏｒｋｉｎｇ，”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １１ｔｈ  ＡＣＭ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｈｏｔ  Ｔｏｐｉｃｓｉｎ  Ｎｅｔｗｏｒｋｓ，  ＨｏｔＮｅｔｓ−ＸＩ，  Ｎｅｗ  Ｙｏｒｋ，  ＮＹ，  ＵＳＡ，  ｐｐ．７−１２，  ＡＣＭ，  ２０１２．
【非特許文献３】Ｄ．Ｙ．  Ｈｕａｎｇ，  Ｋ．  Ｙｏｃｕｍ，  ａｎｄ  Ａ．Ｃ．Ｓｎｏｅｒｅｎ，  “Ｈｉｇｈ−ｆｉｄｅｌｉｔｙ  ｓｗｉｔｃｈ  ｍｏｄｅｌｓ  ｆｏｒｓｏｆｔｗａｒｅ−ｄｅｆｉｎｅｄ  ｎｅｔｗｏｒｋ  ｅｍｕｌａｔｉｏｎ，”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｓｅｃｏｎｄ  ＡＣＭ  ＳＩＧ−ＣＯＭＭ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｈｏｔ  Ｔｏｐｉｃｓ  ｉｎ  Ｓｏｆｔｗａｒｅ  Ｄｅｆｉｎｅｄ  Ｎｅｔｗｏｒｋｉｎｇ，  ＨｏｔＳＤＮ  ’１３，Ｎｅｗ  Ｙｏｒｋ，  ＮＹ，  ＵＳＡ，  ｐｐ．４３−４８，  ＡＣＭ，  ２０１３．
【非特許文献４】Ｓ．  Ｋｕｎｄｕ，  Ｒ．  Ｒａｎｇａｓｗａｍｉ，  Ａ．  Ｇｕｌａｔｉ，  Ｍ．  Ｚｈａｏ，  ａｎｄ  Ｋ．  Ｄｕｔｔａ，  “Ｍｏｄｅｌｉｎｇ  ｖｉｒｔｕａｌｉｚｅｄ  ａｐｐｌｉｃａｔｉｏｎｓ  ｕｓｉｎｇ  ｍａｃｈｉｎｅ  ｌｅａｒｎｉｎｇ  ｔｅｃｈｎｉｑｕｅｓ，”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ８ｔｈＡＣＭ  ＳＩＧＰＬＡＮ／ＳＩＧＯＰＳ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｖｉｒｔｕａｌ  Ｅｘｅｃｕｔｉｏｎ  Ｅｎｖｉｒｏｎｍｅｎｔｓ，  ＶＥＥ’１２，  Ｎｅｗ  Ｙｏｒｋ，  ＮＹ，  ＵＳＡ，  ｐｐ．３−１４，  ＡＣＭ，  ２０１２．
【非特許文献５】Ｒ．  Ｐｏｔｈａｒａｊｕ  ａｎｄ  Ｎ．  Ｊａｉｎ，  “Ｄｅｍｙｓｔｉｆｙｉｎｇ  ｔｈｅ  ｄａｒｋ  ｓｉｄｅ  ｏｆ  ｔｈｅ  ｍｉｄｄｌｅ：  Ａ  ｆｉｅｌｄ  ｓｔｕｄｙ  ｏｆ  ｍｉｄｄｌｅｂｏｘ  ｆａｉｌｕｒｅｓ  ｉｎ  ｄａｔａｃｅｎｔｅｒｓ，”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２０１３  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｎｔｅｒｎｅｔ  ｍｅａｓｕｒｅｍｅｎｔ  ｃｏｎｆｅｒｅｎｃｅ，  ｐｐ．９−２２，  ＡＣＭ，  ２０１３．
【非特許文献６】Ｐ．  Ｇｉｌｌ，  Ｎ．  Ｊａｉｎ，  ａｎｄ  Ｎ．  Ｎａｇａｐｐａｎ，  “Ｕｎｄｅｒｓｔａｎｄｉｎｇ  ｎｅｔｗｏｒｋ  ｆａｉｌｕｒｅｓ  ｉｎ  ｄａｔａ  ｃｅｎｔｅｒｓ：  ｍｅａｓｕｒｅｍｅｎｔ，  ａｎａｌｙｓｉｓ，  ａｎｄ  ｉｍｐｌｉｃａｔｉｏｎｓ，”  ＡＣＭ  ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｒｅｖｉｅｗ，  ｐｐ．３５０−３６１，  ＡＣＭ，  ２０１１．
【非特許文献７】Ｇ．  Ｔｅｓａｕｒｏ，  Ｎ．Ｋ．  Ｊｏｎｇ，  Ｒ．  Ｄａｓ，  ａｎｄ  Ｍ．Ｎ．  Ｂｅｎｎａｎｉ，  “Ａ  ｈｙｂｒｉｄ  ｒｅｉｎｆｏｒｃｅｍｅｎｔ  ｌｅａｒｎｉｎｇ  ａｐｐｒｏａｃｈ  ｔｏ  ａｕｔｏｎｏｍｉｃ  ｒｅｓｏｕｒｃｅ  ａｌｌｏｃａｔｉｏｎ，”  Ａｕｔｏｎｏｍｉｃ  Ｃｏｍｐｕｔｉｎｇ，２００６．  ＩＣＡＣ’０６．  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ，  ｐｐ．６５−７３，  ＩＥＥＥ，  ２００６．
【非特許文献８】Ｊ．  Ｒａｏ，  Ｘ．  Ｂｕ，  Ｃ．Ｚ．  Ｘｕ，  Ｌ．  Ｗａｎｇ，  ａｎｄ  Ｇ．  Ｙｉｎ，  “Ｖｃｏｎｆ：  Ａ  ｒｅｉｎｆｏｒｃｅｍｅｎｔ  ｌｅａｒｎｉｎｇａｐｐｒｏａｃｈ  ｔｏ  ｖｉｒｔｕａｌ  ｍａｃｈｉｎｅｓ  ａｕｔｏ−ｃｏｎｆｉｇｕｒａｔｉｏｎ，”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ６ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｕｔｏｎｏｍｉｃ  Ｃｏｍｐｕｔｉｎｇ，  ＩＣＡＣ  ’０９，  Ｎｅｗ  Ｙｏｒｋ，  ＮＹ，  ＵＳＡ，ｐｐ．１３７−１４６，  ＡＣＭ，  ２００９．
【非特許文献９】Ｘ．  Ｂｕ，  Ｊ．  Ｒａｏ，  ａｎｄ  Ｃ．Ｚ．  Ｘｕ，  “Ｃｏｏｒｄｉｎａｔｅｄ  ｓｅｌｆ−ｃｏｎｆｉｇｕｒａｔｉｏｎ  ｏｆ  ｖｉｒｔｕａｌ  ｍａｃｈｉｎｅｓ  ａｎｄ  ａｐｐｌｉａｎｃｅｓ  ｕｓｉｎｇ  ａ  ｍｏｄｅｌ−ｆｒｅｅ  ｌｅａｒｎｉｎｇ  ａｐｐｒｏａｃｈ，”  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ，  ｖｏｌ．２４，  ｎｏ．４，  ｐｐ．６８１−６９０，  ２０１３．
【非特許文献１０】Ｌ．  Ｂａｉｒｄ  ｅｔ  ａｌ．，  “Ｒｅｓｉｄｕａｌ  ａｌｇｏｒｉｔｈｍｓ：  Ｒｅｉｎｆｏｒｃｅｍｅｎｔ  ｌｅａｒｎｉｎｇ  ｗｉｔｈ  ｆｕｎｃｔｉｏｎ  ａｐｐｒｏｘｉｍａｔｉｏｎ，”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ｔｗｅｌｆｔｈ  ｉｎｔｅｒｎａｔｉｏｎａｌ  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  ｍａｃｈｉｎｅｌｅａｒｎｉｎｇ，  ｐｐ．３０−３７，  １９９５．
【非特許文献１１】Ａ．  Ｎｏｔｓｕ，  Ｈ．  Ｗａｄａ，  Ｋ．  Ｈｏｎｄａ，  ａｎｄ  Ｈ．  Ｉｃｈｉｈａｓｈｉ，  “Ｃｅｌｌ  ｄｉｖｉｓｉｏｎ  ａｐｐｒｏａｃｈ  ｆｏｒ  ｓｅａｒｃｈ  ｓｐａｃｅ  ｉｎ  ｒｅｉｎｆｏｒｃｅｍｅｎｔ  ｌｅａｒｎｉｎｇ，”  ＩＪＣＳＮＳ，  ｖｏｌ．８，  ｎｏ．６，  ｐｐ．１８−２１，  ２００８．
【非特許文献１２】Ｒ．  Ｍｕｎｏｓ  ａｎｄ  Ａ．  Ｍｏｏｒｅ，  “Ｖａｒｉａｂｌｅ  ｒｅｓｏｌｕｔｉｏｎ  ｄｉｓｃｒｅｔｉｚａｔｉｏｎ  ｉｎ  ｏｐｔｉｍａｌ  ｃｏｎｔｒｏｌ，”Ｍａｃｈ．  Ｌｅａｒｎ．，  ｖｏｌ．４９，  ｎｏ．２−３，  ｐｐ．２９１−３２３，  Ｎｏｖ．  ２００２．
【非特許文献１３】Ｍ．  Ｎａｇａｙｏｓｈｉ，  Ｈ．  Ｍｕｒａｏ，  ａｎｄ  Ｈ．  Ｔａｍａｋｉ，  “Ａ  ｓｔａｔｅ  ｓｐａｃｅ  ｆｉｌｔｅｒ  ｆｏｒ  ｒｅｉｎｆｏｒｃｅｍｅｎｔ  ｌｅａｒｎｉｎｇ−ｃｏｎｃｅｐｔ  ａｎｄ  ａ  ｄｅｓｉｇｎ，”  ＩＥＥＪ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｅｌｅｃｔｒｏｎｉｃｓ，  Ｉｎｆｏｒｍａｔｉｏｎａｎｄ  Ｓｙｓｔｅｍｓ，  ｖｏｌ．１２６，  ｐｐ．８３２−８３９，  ２００６．
【非特許文献１４】“ＶＭｗａｒｅ  Ｎｅｗｓ  Ｒｅｌｅａｓｅｓ．”  ｈｔｔｐｓ：／／ｗｗｗ．ｖｍｗａｒｅ．ｃｏｍ／ｃｏｍｐａｎｙ／ｎｅｗｓ／ｒｅｌｅａｓｅｓ／ｓｐｅｃｗｅｂ２００５．
【非特許文献１５】Ｒ．Ｓ．  Ｓｕｔｔｏｎ  ａｎｄ  Ａ．Ｇ．  Ｂａｒｔｏ，  Ｒｅｉｎｆｏｒｃｅｍｅｎｔ  ｌｅａｒｎｉｎｇ：  Ａｎ  ｉｎｔｒｏｄｕｃｔｉｏｎ，  ＭＩＴｐｒｅｓｓ  Ｃａｍｂｒｉｄｇｅ，  １９９８．
【非特許文献１６】Ｉ．  Ａｋｉｒａ  ａｎｄ  Ｋ．  Ｍｉｔｓｕｒｕ，  “Ｓｐｅｅｄｉｎｇ  ｕｐ  ｍｕｌｔｉ−ａｇｅｎｔ  ｒｅｉｎｆｏｒｃｅｍｅｎｔ  ｌｅａｒｎｉｎｇ  ｂｙ  ｃｏａｒｓｅ−ｇｒａｉｎｉｎｇ  ｏｆ  ｐｅｒｃｅｐｔｉｏｎ：  Ｈｕｎｔｅｒ  ｇａｍｅ  ａｓ  ａｎ  ｅｘａｍｐｌｅ，”  ＩＥＩＣＥ  Ｔｒａｎｓａｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｙｓｔｅｍｓ，  ｖｏｌ．８４，  ｎｏ．３，  ｐｐ．２８５−２９３，  ｍａｒ  ２００１．
【非特許文献１７】Ｔ．  Ｂｅｎｓｏｎ，  Ａ．  Ａｋｅｌｌａ，  ａｎｄ  Ｄ．Ａ．  Ｍａｌｔｚ，  “Ｎｅｔｗｏｒｋ  ｔｒａｆｆｉｃ  ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ  ｏｆ  ｄａｔａ  ｃｅｎｔｅｒｓ  ｉｎ  ｔｈｅ  ｗｉｌｄ，”  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １０ｔｈ  ＡＣＭ  ＳＩＧＣＯＭＭ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎＩｎｔｅｒｎｅｔ  Ｍｅａｓｕｒｅｍｅｎｔ，  ＩＭＣ  ’１０，  Ｎｅｗ  Ｙｏｒｋ，  ＮＹ，  ＵＳＡ，  ｐｐ．２６７−２８０，  ＡＣＭ，  ２０１０．
【非特許文献１８】Ｓ．  Ｋｕｎｄｕ，  Ｒ．  Ｒａｎｇａｓｗａｍｉ，  Ｋ．  Ｄｕｔｔａ，  ａｎｄ  Ｍ．  Ｚｈａｏ，  “Ａｐｐｌｉｃａｔｉｏｎ  ｐｅｒｆｏｒｍａｎｃｅ  ｍｏｄｅｌｉｎｇ  ｉｎ  ａ  ｖｉｒｔｕａｌｉｚｅｄ  ｅｎｖｉｒｏｎｍｅｎｔ，”  Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｃｏｍｐｕｔｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ  （ＨＰＣＡ），  ２００９  ＩＥＥＥ  １６ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ，  ｐｐ．１−１０，  ＩＥＥＥ，２００９．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
前記課題を解決するために、本開示は、刻々と変化する各仮想マシンに対する負荷に対応して、ＣＰＵやメモリのリソースの割り当てを行うことを目的とする。
【課題を解決するための手段】
【０００７】
本開示に係るリソース管理装置は、強化学習を用いて仮想マシンのリソースを管理するリソース管理装置であって、
仮想マシンへのリソースの割り当てを行う制御を行動とし、該行動によってリソースが割り当てられた割り当て状態における当該仮想マシンの性能に基づく報酬値を用いた強化学習によって、前記割り当て状態における前記制御の評価値である制御評価値を求める状態管理部を備え、
前記状態管理部は、
前記割り当て状態が適当か否かを前記制御評価値に基づいて判定する判定機能と、
適当でないと判定された前記割り当て状態を分割して新たな割り当て状態を生成する分割機能と、
適当であると判定された前記割り当て状態のうちのリソースに対する前記行動が一致する複数の割り当て状態を１つの割り当て状態に集約する集約機能と、
を備え、
前記集約機能は、１つのリソースのみが異なる２つの割り当て状態が存在し、前記２つの割り当て状態で異なる前記１つのリソースのうちの一方の割り当て状態のリソースの下限と他方の割り当て状態のリソースの上限とが一致する場合に、前記２つの割り当て状態を１つの割り当て状態に集約する。
【０００８】
本開示に係るリソース管理方法は、強化学習を用いて仮想マシンのリソースを管理するリソース管理装置が実行するリソース管理方法であって、
仮想マシンへのリソースの割り当てを行う制御を行動とし、該行動によってリソースが割り当てられた割り当て状態における当該仮想マシンの性能に基づく報酬値を用いた強化学習によって、前記割り当て状態における前記制御の評価値である制御評価値を求める状態管理手順を有し、
前記状態管理手順は、
前記割り当て状態が適当か否かを前記制御評価値に基づいて判定する判定手順と、
適当でないと判定された前記割り当て状態を分割して新たな割り当て状態を生成する分割手順と、
適当であると判定された前記割り当て状態のうちのリソースに対する前記行動が一致する複数の割り当て状態を１つの割り当て状態に集約する集約手順と、
を含み、
前記集約手順では、１つのリソースのみが異なる２つの割り当て状態が存在し、前記２つの割り当て状態で異なる前記１つのリソースのうちの一方の割り当て状態のリソースの下限と他方の割り当て状態のリソースの上限とが一致する場合に、前記２つの割り当て状態を１つの割り当て状態に集約する。
【発明の効果】
【０００９】
本開示によれば、サーバの性能に応じたコンパクトな状態表現を行うことができるため、刻々と変化する各仮想マシンに対する負荷に対応して、ＣＰＵやメモリのリソースの割り当てを行うことができる。
【図面の簡単な説明】
【００１０】
【図１】実施形態に係るリソース管理装置の一例を示す構成図である。
【図２】状態の分割の一例を示す。
【図３】状態の分割を行った場合の状態の遷移の一例を示す。
【図４】状態の集約の一例を示す。
【図５】ＳＬＡ違反率の比較例を示す。
【図６】状態数の比較例を示す。
【図７】実施形態に係るリソース管理方法を用いた場合の検証時間の測定例を示す。
【発明を実施するための形態】
【００１１】
以下、本開示の実施形態について、図面を参照しながら詳細に説明する。なお、本開示は、以下に示す実施形態に限定されるものではない。これらの実施の例は例示に過ぎず、本開示は当業者の知識に基づいて種々の変更、改良を施した形態で実施することができる。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００１２】
既存手法の問題点は、リソースの割り当て状態を保存しないことに起因するものである。実施形態は、リソース割り当て状態を全て保存する一般的な強化学習を拡張し、状態の分割と集約を用いて、状態数を削減する方法を利用する［例えば、非特許文献１１〜１３参照。］。
【００１３】
具体的には、各リソース割り当て状態にて最適な再割り当て方針が決定しているかどうか（学習結果が収束しているかどうか）を判定し、収束しているならば、当該状態と類似する収束した状態同士を集約し１つの状態として表現する。また、収束していない状態については、当該状態が複数の状態を包含しているとみなし、状態分割を試みる。状態の分割と集約を繰り返すことにより、サーバの性能に応じたコンパクトな状態表現ができるため、各状態への状態遷移確率を求めたり、リソース割て当てが正しく動作するか、学習が収束しているかどうかを検証することが可能となる。なお、既存手法は、各ＶＭに割り当てられるリソースは独立かつ制約がないことを仮定しているため、リソースに制約がある場合にも適用できるように改良した。
【００１４】
１．実施形態に係る機能の詳細
図１に、実施形態に係るサーバの構成例を示す。実施形態に係るサーバ９１は、仮想マシン（ＶＭ）を管理するリソース管理装置として機能し、リソース制御部、状態管理部、およびＶＭの状態ＤＢを備える。リソース制御部、状態管理部、および状態ＤＢは、サーバ９１のハイパーバイザ上に設けられる。ハイパーバイザは、任意の仮想化基盤を用いることが可能であり、例えば、Ｘｅｎが例示できる。
【００１５】
ＶＭの状態ＤＢは、割り当てたコア数やメモリ量に対して、どの程度のスループットが出たか、ＳＬＡ違反率はどの程度かを記憶している。状態管理部は、概容で述べた状態の分割と集約によって、状態ＤＢに記憶されている状態を制御する。リソース制御部は、状態ＤＢから現在のリソース割り当て状態を読み込み、状態に応じて、各ＶＭ８１へのリソース割り当てを行う。
【００１６】
実施形態に係るリソース管理装置は、コンピュータを、リソース制御部、状態管理部、および状態ＤＢとして機能させることで実現してもよい。この場合、サーバ９１内のＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）が、記憶部（不図示）に記憶されたコンピュータプログラムを実行することで、各構成を実現する。
【００１７】
２．状態ＤＢ
状態ＤＢは、以下の形式で表現される各ＶＭへのリソース割り当て状態をＫｅｙとし、Ｋｅｙを指定した際に、返り値として、当該状態における制御評価値を出力するデータベースである。Ｋｅｙとなる状態ｓは、以下のとおりである。
【数２１】
0006602252.tif 000002
【００１８】
ｍｍａｘ１はＶＭ１に割り当てられているリソースの上限値を示し、ｍｍｉｎ１は下限を示しており、ＣＰＵリソースに関しても同様に表現を用いる。ｎは状態ｓの数であり、合計でｎ台のＶＭが稼働していることを示す。なお、各下限が上限を上回ることはないものとしｍｍｉｎｉ≦ｍｍａｘｉ、ｃｍｉｎｉ≦ｃｍａｘｉ、ｉ≦ｎを満たしているものとする。初期値として、各リソースの下限値は０、上限値は物理リソースの上限と一致させる（最初の状態数は１）。
【００１９】
返り値となる制御評価値は上記の状態において、各制御指針の評価値を意味している。具体的には、各ＶＭにおけるサーバリソースのパラメータに対して、ｉｎｃｒｅａｓｅ、ｄｅｃｒｅａｓｅ、ｎｏｏｐｅｒａｔｉｏｎの３つの制御を行う。なお、メモリに対する行動：ｉｎｃｒｅａｓｅはメモリを一定単位（ｅ．ｇ．６４ＭＢ）でＶＭに対して割り当てすることとし、ｄｅｃｒｅａｓｅは同様の単位でメモリの割り当てを減らすこととする。ＣＰＵに対する行動：ｉｎｃｒｅａｓｅはコアを１つ単位で割り当てることとし、行動：ｄｅｃｒｅａｓｅはコアの割り当てを同様の単位で減らすこととする。行動：ｎｏｏｐｅｒａｔｉｏｎは、何も行動を起こさないこととする。
【００２０】
なお、各ＶＭ８１に対するリソース割り当ては、サーバ９１の物理リソースの上限（メモリ：Ｍ、コア数：Ｃ）を超えないものとする。すなわち、次式を満たす範囲にて、リソース制御部はＶＭ８１へのリソース割り当てを行うものとする。
【数２２】
0006602252.tif 000003
なお、ｎはＶＭの数、ｍｉはＶＭｉに割り当てているメモリ量、ｃｉはＶＭｉに割り当てているＣＰＵ数を意味している。
【００２１】
また、各ＶＭ８１が稼働していることを前提とし、その割り当てリソースは０にならないことにする。即ち、返り値となる評価値は、各ＶＭ８１における２つのリソースに対して３つの制御の合計６ｎ要素を持つ配列となる。なお、６ｎ個の要素内の値については、状態管理部が更新する。
【００２２】
３．リソース制御部
リソース制御部は、各ＶＭ８１におけるサーバリソースのパラメータに対して、ｉｎｃｒｅａｓｅ、ｄｅｃｒｅａｓｅ、ｎｏｏｐｅｒａｔｉｏｎの３つの制御を行う。どのリソースをどのＶＭ８１に割り当てるかは、現在のリソース割り当てをＫｅｙとして状態ＤＢに入力し、返り値として得られる各ＶＭ８１に対するリソース割り当てに対する評価値をもとに決定する。具体的には、返り値として、各ＶＭ８１における２つのリソースに対して３つの制御の合計６ｎ要素を持つ配列を得て、各要素の値が高い制御ほど高い確率で選択し、当該制御を行うことにする。
【００２３】
４．状態管理部
リソース制御部にて制御を行った後、状態管理部は、各ＶＭ８１におけるスループットやＳＬＡ違反を次の制御を行うまでに観測し、制御後のリソース割り当て状態の制御評価値を更新する。その際、状態ＤＢ内に保存されているリソース割り当て状態と当該状態における制御評価値に対して、類似度を計算し、類似性が高い状態同士を一つの状態にまとめることを行う。
【００２４】
最初に、リソース制御後のリソース割り当て状態における制御評価値の更新方法について述べる。制御評価値に対して、状態管理部は、計測したＳＬＡ違反率とスループット平均値を利用し、以下の式で表現される報酬値を算出し、更新に利用する。
【数４１】
0006602252.tif 000004
【００２５】
報酬値は、ＶＭｗａｒｅ（登録商標）やＩＢＭ（登録商標）が自社サーバの性能を公開する際に利用している性能指標と、各ＶＭの優先度の積によって表現する［例えば、非特許文献１４参照。］。ｗｉはＶＭｉ（ｉ≦ｎ）の優先度を示しており、
【数４２】
0006602252.tif 000005
を満たすものとする。
【００２６】
ｔｈｒｐｔｉはＶＭｉの単位時間当たりのタスクの完了数を示し、ｒｅｆ＿ｔｈｒｐｔｉは、最大限のリソースを割り当てた際のスループット、もしくは学習中に得たスループットの最大値を示す。タスクの完了数は、アプリケーションによって異なり、例えば、データベースの役割を持つＶＭ８１ではトランザクションの完了数を意味する。エージェントは、行動を実施すると同時に、次の行動までの単位時間当たりの平均スループットを計算し、当該報酬値を用いて、学習を行うものとする。ｒｅｓｐおよびｓｌａは、１タスクあたりの完了時間と、そのＳＬＡを示しており、ｒｅｓｐがＳＬＡの値を満たさない場合は、報酬値にペナルティが課される。これらにより、スループットが高く違反が少ない行動ほど高い報酬値が割り当てられるようになる。
【００２７】
次に、上記の式で求めた報酬値をもとに、当該リソース割縦状態における制御評価値を更新する。ここで、時刻ｔにおけるリソース割り当て状態をｓｔ、当該状態における制御方針をａｔ、状態ｓｔにおける制御ａｔの評価値（制御評価値）をＱ（ｓｔ，ａｔ）とすると、上記で求めた報酬値Ｒａｔｓｔ，ｓｔ＋１をもとに、以下のように制御評価値を更新する。
【数４３】
0006602252.tif 000006
【００２８】
α（０＜α≦１）は学習率を示し、γ（０＜γ≦１）は割引率を示している。αが大きい場合には最新の報酬を重視し、αが１の場合には、過去の報酬を全く考慮しない。また、γは遷移先の状態に対する制御評価値が現在の制御評価値に与える影響を表し、γが０の時は遷移先の状態ｓｔ＋１に対する制御評価値が現在の状態ｓｔの制御評価値に依存しない。本更新式は、Ｑ学習［例えば、非特許文献１５参照。］と呼ばれており、上記の更新を再帰的に行うことで、最も報酬値を得られることのできる制御の評価値Ｑ（ｓ，ａ）が、最大になることが理論的にわかっている。
【００２９】
次に、状態ＤＢ内に保存されているリソース割り当て状態と当該状態における制御評価値に対して、類似度を計算し、類似性が高い状態同士を一つの状態に集約する方法について述べる。状態管理部は、Ｑ（ｓｔ，ａｔ）の更新後、当該Ｑ（ｓｔ，ａｔ）が十分に学習したかどうかを判定し、当該状態と隣接する状態に対して、類似度を計算し、類似度が高ければ、一つの状態に集約することにする。強化学習では、状態の学習が収束した場合、当該状態の最適行動の制御評価値だけが、突出して高くなる性質がある。一方で、収束していない場合は、各行動の値にバラつきはあるが、どれも突出して高くない値をとる性質がある。本性質を利用し、非特許文献１６では、状態ｓの収束度合いを、ｓにおける各制御評価値のエントロピーＩ（ｓ）と、状態ｓへの遷移回数にて判定している。
【００３０】
具体的な制御評価値のエントロピーＩ（ｓ）の式は下記の通りである。
【数４４】
0006602252.tif 000007
【００３１】
状態管理部は、判定機能を有し、判定手順を実行する。もし、状態ｓへの遷移が十分に行われ、かつ制御評価値のエントロピーＩ（ｓ）が十分に低ければ、割り当て状態が適当であり、学習は収束していると判定することができる。一方で、状態ｓへの遷移が十分に行われているにも関わらず、制御評価値のエントロピーＩ（ｓ）が高い値のままであれば、割り当て状態が適当でなく、状態ｓの状態表現（リソースの範囲）が正しく設定されていないことになる。
【００３２】
本実施形態でＱ学習を用いたが、管理装置に用いる学習は任意である。例えば、Ｓａｒｓａ、ＴＤ学習法、Ａｃｔｏｒ−ｃｉｒｃｕｉｔ法（例えば、非特許文献１５参照。）を用いることができる。
【００３３】
５．状態分割
状態管理部は、分割機能を有し、分割手順を実行する。状態ｓへの遷移が十分に行われているにも関わらず、制御評価値のエントロピーＩ（ｓ）が高い場合、当該状態の範囲を分割し、状態を細かく区切る必要がある。状態ｓの区切り方は、例えば、各範囲を二等分する。これにより、状態ｓから２ｎの新たな割り当て状態が生成される。例えば、ｎ＝２の場合、図２に示すように、学習が収束した状態ｓ１から状態ｓ２へ移行するに際し、４つの状態Ｒ２１，Ｒ２２，Ｒ２３，Ｒ２４が生成される。このときの深さは、ｌｏｇ２｜Ｓｔａｔｅ／２！｜で近似されうる。
【００３４】
図３に、状態の遷移の一例を示す。例えば、状態Ｒ１は状態Ｒ２１，Ｒ２２，Ｒ２３，Ｒ２４に分割され、状態Ｒ２１は状態Ｒ３１，Ｒ３２，Ｒ３３に分割され、状態Ｒ２４は状態Ｒ３４，Ｒ３５に分割される。
【００３５】
分割によって生成された状態の中には、割り当てリソースの下限値が物理リソースを超える範囲を持つ状態が存在する可能性がある。本状態は学習段階で遷移するはずがないため、当状態は生成しないことにする。例えば、図３に示すように、状態Ｒ２２に割り当てるリソースの下限値が物理リソースを超える範囲を持つ場合、状態Ｒ２２は生成しない。
【００３６】
なお、生成後の状態が満たすべき条件は以下のとおりである。
【数５１】
0006602252.tif 000008
【００３７】
これは全ＶＭ８１に割り当てられたＣＰＵとメモリのリソースの範囲の下限値の総和が、物理リソース以下であるかどうかを判断している。上記の式を満たさなければ、当該状態は破棄されるため、状態数を削減することができる。なお、分割後の状態における各行動のＱ値は分割前の状態のＱ値と一致させることにする。
【００３８】
６．状態集約
状態管理部は、集約機能を有し、集約手順を実行する。状態ｓへの遷移が十分に行われ、かつ制御評価値のエントロピーＩ（ｓ）が十分に低けれれば、当該状態における学習が収束したと判断できる。この時、状態ｓに隣接する状態で、最適な行動が状態ｓと一致するものがあれば、両状態を一つの状態に集約する。例えば、図２に示す分割を行ったときに、学習が収束した状態Ｒ２１及びＲ２２における最適な行動が一致する場合、図４に示すように、状態Ｒ２１及びＲ２２を１つの状態Ｒ２５に集約する。
【００３９】
なお、二つの状態ｓ及びｓ′が隣り合うことの定義は、両状態におけるＮ−１個のリソースの範囲が一致しており、範囲が一致しない１リソースについて、ｓにおける当該リソースの下限とｓ′の当該リソースの上限が一致する、或いは、ｓ′における当該リソースの下限とｓの当該リソースの上限が一致することを意味する。
【００４０】
状態ｓと状態ｓ′を集約し、新たな状態ｓ′′を生成する場合、状態ｓ′′における各行動のＱ値は、状態ｓと状態ｓ′における各行動のＱ値の平均値とする。もし、状態ｓが収束しているにも関わらず、上記の条件を満たす隣接する状態が見つからない場合は、当該状態が出現するまで、状態ｓを記録しておく。
【００４１】
７．実施形態によって生じる効果
汎用サーバ上にて３台から５台のＶＭ８１を運用し、各ＶＭにおけるＳＬＡ違反率、生成された状態の数、全状態における収束具合の検証時間をシミュレーションを通して評価した。汎用サーバはメモリ１６ＧＢと８コアのＣＰＵを有し、エージェントの各行動は、メモリを１２８ＭＢ単位で割り当てる（削除する）かＣＰＵを１コア単位で割り当てる（削除する）かである。各ＶＭに対するリクエストの到着頻度と、各リクエストに対する処理時間は、実データセンタの解析結果に基づくモデルを利用した［例えば、非特許文献１７参照。］。また、割り当てたリソースに応じてスループットが線形で増加するものとし、各ＶＭのＳＬＡは全てのリソースを当該ＶＭに割り当てた際のスループット５０％を下回る場合に、ＳＬＡ違反と見なす［例えば、非特許文献１８参照。］。
【００４２】
７．１  ＳＬＡ  Ｖｉｏｌａｔｉｏｎ
上記の設定を利用し、実施形態の各ＶＭ８１のＳＬＡ違反率を計測した。図５に、ＳＬＡ違反率の比較結果の一例を示す。なお、非特許文献８のＶＣＯＮＦを同等の設定にてＳＬＡ違反率を評価し、その値を比較例として示す。各ＶＭの優先度は、ＶＭの番号が小さいほど高くし、番号の増加と共に各重みが指数的に減少するように設定した。実験結果より、実施形態は、ＶＣＯＮＦと類似したＳＬＡ違反率となっており、有意な差は見られなかった。なお、ＳＬＡの平均違反率は、実施形態のほうが非特許文献８のＶＣＯＮＦと比べ５％−１１％程度低かった。
【００４３】
７．２  状態数と検証時間
ＶＭの台数を５台とし、実施形態における２つのパラメータ（収束判定に利用する、遷移回数と制御評価値のエントロピーの閾値）を変化させ、上記と同様の実験を行った。実験終了後に、生成された状態数を計測し、さらに、各状態が収束しているか否かを検証した際に費やした時間を計測した。図６に、生成された状態数の比較結果の一例を示す。図７に、検証時間の計測結果の一例を示す。
【００４４】
遷移回数の閾値を高く設定すればするほど、状態が分割されにくくなるため、状態数は少なくなり（図６）、検証時間も短時間（２２０秒以下）で済む（図７）ことが分かった。制御評価値のエントロピーの閾値を変化させた結果では、状態数と検証時間がエントロピーの閾値にあまり依存しない結果となった。しかしながら、閾値が０．５の結果では０．９および０．９９の結果よりも２０秒程度遅かった。
【００４５】
８．検証時間と状態数
ＶＭの台数を５台とし、実施形態における２つのパラメータ（収束判定に利用する、遷移回数とＱ値のエントロピーの閾値）を変化させ、上記と同様の実験を行った。実験終了後に、生成された状態数を計測し、さらに、各状態が収束しているか否かを検証した際に費やした時間を計測した（図６及び図７）。遷移回数の閾値を高く設定すればするほど、状態が分割されにくくなるため、状態数は少なくなり検証時間も短時間（２２０秒以下）で済むことが分かった。Ｑ値のエントロピーの閾値を変化させた結果では、状態数と検証時間がエントロピーの閾値にあまり依存しない結果となった。しかしながら閾値が０．５の結果では０．９および０．９９の結果よりも２０秒程度遅かった。
【産業上の利用可能性】
【００４６】
本開示は情報通信産業に適用することができる。
【符号の説明】
【００４７】
８１：仮想マシン
９１：サーバ
【図１】
0006602252.tif 000009
【図２】
0006602252.tif 000010
【図３】
0006602252.tif 000011
【図４】
0006602252.tif 000012
【図５】
0006602252.tif 000013
【図６】
0006602252.tif 000014
【図７】
0006602252.tif 000015