云数据中心中负载均衡的虚拟机调度方法

A Load-balanced Virtual Machine Scheduling Approach in Cloud Data Center

本文研究在主机之间迁移虚拟机来提高系统负载均衡度(包括2个方面:CPU和disk I/O),同时尽可能地降低迁移代价。因此,目标是寻找主机和虚拟机之间尽可能优的映射方案。本文提出虚拟机的亲和力概念,并且定义了亲和力指数的计算方法,然后建立基于遗传算法的虚拟机调度模型。在这个模型中,交叉操作驱动映射方案的亲和力指数尽可能地增加,变异操作使得主机的CPU和disk I/O的差值趋于收敛。在每一代中,选择策略将亲本个体和子代个体分为一组,并选择较大适应度的个体遗传到下一代,从而使得种群不断地进化,得到最终的映射方案解空间。本文提出基于遗传算法的虚拟机均衡调度算法。该算法选取最终映射方案解空间中的最优解,做到从全局的角度考虑负载均衡问题;提前计算迁移的影响,在得到最优的迁移方案时才进行实质性迁移,从而降低了迁移代价;使用MTALB算法将多类型任务均匀地分配到虚拟机中,系统的负载均衡效果更佳。实验结果表明,就迁移代价和系统负载均衡各项具体指标而言,本文算法相比于首次适应和轮转调度算法以及NABM算法存在全面优势。在任务处理率这一关键指标上,本文算法比首次适应和轮转调度算法及NABM算法分别平均提升了25%和12%。

The paper researches on the migrations of virtual machines among hosts to improve system load balancing degree （ including two aspects： CPU and disk I/O） while reducing the migration cost as much as possible. So, the purpose is to find out the best possible mapping scheme between hosts and virtual machines in the system. This paper puts forward the concept of affinity about virtual machine, and defines the calculation method of affinity index; then builds the virtual machine scheduling model based on genetic algorithm. In the model, the crossover operation drives the affinity index of the mapping scheme increased as much as possible, the mutation operation makes the difference between CPU and disk I/O of host tending to converge. In each generation, selection strategy selects bigger fitness in each pair of parent individuals and child individual, so that the population is constantly evolving, and the final solution space of the mapping scheme is obtained. The paper proposes a VM balanced sched- uling algorithm based on genetic algorithm, the algorithm selects the best solution from the final solution space of the mapping scheme, which considers the load balancing problem from a global perspective ; the algorithm calculates the impact of migration in advance and carries out substantive migration after obtaining the best mapping scheme, therefore, it reduces the migration cost; the algorithm uses MTALB algorithm to allocate multi-type tasks evenly to VMs, the effect of system load balancing is better. Ex- perimental results show that the proposed algorithm has overall advantages over first fit and round robin algorithm and NABM algo- rithm in terms of specific indicators of migration cost and system load balancing. In the key indicator-task processing rate, it is re- spectively improves by 25% and 12% than that of the first fit and round robin scheduling algorithm and NABM algorithm.