Online Virtual Machine Assignment Using Multi-Armed Bandit in Cloud Computing

One of essential techniques to increase flexibility and scalability of cloud data centers is virtualization. Several virtual machine applications in cloud computing are delay-sensitive. Therefore, we can exploit virtualization in order to run virtual machines which provide the lowest response time to the users. In prior work, these delays were deterministic and specified, whereas in the real cloud environment, there are generally stochastic. In fact, what seems to be necessary in such a problem is to use an appropriate learning method to observe and learn the cloud computing environment that has not been considered in previous work. Also, a modified algorithm is needed to assign multiple virtual machines to physical machines. This requirement is considered in our solution as well. So, we consider virtual machine assignment as an online optimization problem. In this problem, the network delays of assignments are not specified primarily, but they are measured using appropriate learning method. We formulate the optimization problem with a weighted bipartite matching graph in which the edges' weight between each pair of vertices demonstrates network delay of that assignment. Combinatorial Multi-Armed Bandit strategy is used to solve this minimum weighted matching problem. We will converge to the optimum matching using the best tradeoff between exploration and exploitation. Results show that regret converges effectively over time using combinatorial Multi-Armed Bandit, and polynomially in the number of unknown variables. Also, this strategy just requires storage which grows linearly in the number of unknown variables.