Abstract: Due to the popularity and rapid development of cloud computing, many Internet companies have continued to build ultra-large-scale data centers for the past years. When receiving a new virtual machine request, the cloud computing center searches for a suitable physical machine and creates a virtual machine with the corresponding specifications. When the customer finishes using the virtual machine, the cloud computing center will delete the virtual machine and free the corresponding space. As time goes by, the remaining space of each physical machine in the computer room cluster will vary greatly, resulting in the waste of physical machine space and an increase in fragmentation rate. Therefore, the cloud computing center needs to periodically readjust the virtual machine deployment scheme (rescheduling) to improve the utilization of physical machine resources. Since the hot migration operation consumes more communication resources and operation time, it is necessary to minimize the impact of deployment differences on physical machines during rescheduling to achieve optimal adjustment plan.
Many studies have focused on the scheduling of virtual machines in static scenarios, but the frequent creation and deletion of virtual machines in the cloud computing center leads to a waste of physical machine space, which relies on virtual machine rescheduling to improve the operational efficiency of the cloud computing center. After carefully searching, we find that no scholars have studied the virtual machine rescheduling problem. Therefore, considering the important impact of rescheduling in virtual machine scenarios, this paper studies the virtual machine rescheduling problem in cloud computing centers. Given the existing deployment plan of the virtual machine and users’ virtual machine requirements, it readjusts the virtual machine to meet the actual needs of the user. The key lies in minimizing the total cost, including operating costs and deployment variance costs, and improving the efficiency of cloud computing center resource utilization by optimizing the virtual machine rescheduling scheme. The research results of this paper are helpful for improving the flexible deployment capability of cloud computing centers and better coping with the market competitive environment.
We first present the mathematical definitions of placement deviation and then formulate the virtual machine rescheduling problem as a mixed integer mathematical model. The objective is to minimize the total costs including wasted resources, deployment mode preparation costs, and variance costs. The virtual machine rescheduling scheduling problem introduces differential variables compared with the static deployment problem and is more difficult to be solved. According to the characteristics of the problem, we propose an accurate algorithm based on branch and pricing. Firstly, the Dantzig-Wolfe decomposition method is used to rewrite the model of the rescheduling problem, then the column generation is used to obtain the optimal solution of the relaxation problem, and finally the branch and price approach is used to obtain the optimal solution of the problem. The branch and price algorithm can accurately solve the virtual machine rescheduling problem, but it will take a long time to solve large-scale or enterprise instances, which is not suitable for industrial applications. Therefore, we also propose a heuristic search strategy based on column generation to achieve a high-quality rescheduling scheme in a short time.
In this paper, numerical experiments are carried out by randomly generating examples to evaluate the performance of the proposed Branch & Price algorithm and CGH algorithm. For small-scale examples, the Branch & Price algorithm can obtain the optimal solution of all examples, and the average gap of CGH algorithm is 1.02%; For medium and large-scale studies, for some examples, CPLEX can no longer obtain the optimal solution within 1 hour, but the Branch & Price algorithm still finds the optimal solution of all examples, and the gap of CGH algorithm is only 1.98%. Finally, a sensitivity analysis is carried out for different cost parameters to analyze the influence of parameter changes. The results show that the decrease in the pattern setup cost and deviation cost respectively increase the corresponding number of patterns and deviation patterns, but decrease the total cost. The cloud computing center can smooth pattern deviation by acknowledging customers’ demand in advance and improving flexible placement capability, and further promote operation competitiveness.

Key words: cloud computing, virtual machine placement, rescheduling problem, exact algorithm

摘要： 提出云计算中心虚拟机重调度问题。给出部署方案差异的数学定义,建立虚拟机重调度问题的整数规划模型。部署模式约束导致无法直接使用列生成求解松弛问题。基于Dantzig-Wolfe分解方法改写重调度问题模型,设计分支定价(Branch & Price)精确算法,进一步设计启发式搜索策略。数值实验验证算法的有效性;敏感性分析发现降低部署准备成本与差异成本会增加对应的部署模式和差异部署模式,但可以降低总成本。云计算中心可以通过提前感知客户需求和柔性部署能力减少虚拟机部署差异,进而提升云计算运营能力。

关键词: 云计算, 虚拟机部署, 重调度, 精确算法