文章快速检索     高级检索
  重庆邮电大学学报(自然科学版)  2020, Vol. 32 Issue (3): 356-367  DOI: 10.3979/j.issn.1673-825X.2020.03.004
0

引用本文 

李双俐, 李志华, 喻新荣. 基于多目标优化的虚拟机放置方法[J]. 重庆邮电大学学报(自然科学版), 2020, 32(3): 356-367.   DOI: 10.3979/j.issn.1673-825X.2020.03.004.
LI Shuangli, LI Zhihua, YU Xinrong. Virtual machine placement method based on multi-objective optimization[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2020, 32(3): 356-367.   DOI: 10.3979/j.issn.1673-825X.2020.03.004.

基金项目

江苏省科技厅产学研联合创新基金(BY2013015-23)

Foundation item

The Innovations Fund for the Integration of Industry, Education and Research of Jiangsu Province under Grant (BY2013015-23)

作者简介

李双俐(1992-), 女, 河南新乡人, 硕士研究生, 主要研究方向为云计算、资源调度、多目标优化。E-mail:lily_lshl@163.com; 李志华(1969-), 男, 湖南保靖人, 副教授, 博士。主要研究方向为计算机网络、信息安全、数据挖掘。E-mail:wxzhli@aliyun.com; 喻新荣(1992-), 男, 江苏南通人, 硕士。主要研究方向为云计算、并行计算与分布式计算。E-mail:espresso_yu@163.com

通讯作者

李志华  wxzhli@aliyun.com.

文章历史

收稿日期: 2018-12-01
修订日期: 2019-12-30
基于多目标优化的虚拟机放置方法
李双俐1, 李志华1,2, 喻新荣1     
1. 江南大学 物联网工程学院, 江苏 无锡, 214122;
2. 江南大学 物联网应用技术教育部工程研究中心, 江苏 无锡, 214122
摘要: 在虚拟机放置问题中, 传统启发式方法不能完全适用于复杂的云计算环境, 采用智能算法的研究又缺乏对时间开销的考虑。针对上述问题, 提出一种基于Memetic算法的虚拟机放置(Memetic algorithm-based virtual machine placement MAVMP)方法。MAVMP方法针对云数据中心运营情况建立了最小化能耗、最小化运行时服务等级协议违例率(service level agreement violation time per active host, SLATAH)以及最大化资源利用率的多目标优化模型, 将虚拟机按照资源请求情况进行分类, 并利用该分类方法改进了Memetic算法, 利用改进后的Memetic算法求解多目标优化模型, 得到虚拟机放置方案。仿真实验结果表明, 仿真数据中心利用MAVMP方法进行虚拟机放置后, 其在能耗、资源利用率以及服务质量的评价指标上都有着良好表现。并且, MAVMP方法与已有的基于智能算法的虚拟机放置方法相比计算时间也大幅下降。
关键词: 云计算    虚拟机放置    多目标优化    多资源    Memetic算法    
Virtual machine placement method based on multi-objective optimization
LI Shuangli1 , LI Zhihua1,2 , YU Xinrong1     
1. School of Internet of Things Engineering, Jiangnan University, Wuxi 214122, P. R. China;
2. Engineering Research Center of IoT Technology Application Ministry of Education, Wuxi 214122, P. R. China
Abstract: In the virtual machine placement problem, the traditional heuristic methods are not entirely applicable to the complex cloud computing environment, and the researches using intelligent algorithms lack the consideration of time overhead. To solve the above problems, a Memetic algorithm-based virtual machine placement (MAVMP) method is proposed. Firstly, The MAVMP method establishes a multi-objective optimization model for minimizing energy consumption, minimizing the service-level agreement violation times per active host (SLATAH) and maximizing resource utilization according to the operation situation of cloud data centers. Secondly, on the basis of resource requests, virtual machines are classified, improving the Memetic algorithm. Finally, the improved Memetic algorithm is used to solve the multi-objective optimization model, and then obtain the virtual machine placement plan. The results of simulation test show that the simulation data center using the MAVMP method to place virtual machines has good performances in energy consumption, resource utilization and service quality. Moreover, in contrast to the existing intelligent algorithm-based virtual machine placement method, the calculation time of the MAVMP method decreases sharply.
Keywords: cloud computing    virtual machine placement    multi-objective optimization    multiple resources    Memetic algorithm    
0 引言

自21世纪以来,云计算得到了快速发展,并且在商业应用方面取得了巨大成功[1]。微软、IBM、亚马逊等互联网公司纷纷推出了自己的云平台。云计算的发展满足了企业和消费者的计算需求[2]。对于云服务提供商,如何有效降低数据中心运营成本是问题的关键。研究表明,云数据中心每年需要消耗大量电力[3],云服务提供商想要在竞争中获得更大的优势,就需要在保证服务质量的同时降低运营成本,通过更低的服务价格吸引用户。

云计算数据中心利用虚拟化技术管理分配资源。数据中心的负载情况随着用户请求的变化而改变。为了实现负载平衡,数据中心每隔一段时间需要将虚拟机与物理主机重新整合。目前虚拟机整合中待解决的问题主要有:过载物理主机检测、虚拟机选择和虚拟机放置[4]。虚拟机放置是虚拟机整合中的重要部分。虚拟机放置是将从物理主机上迁移出的虚拟机和新创建的虚拟机按照一定的规则放置在适合的物理主机上的过程。文献[4]指出合理的虚拟机放置方案能够降低数据中心能耗,提高数据中心资源利用率和服务质量。为了降低数据中心的能耗,一些研究[4-7]将低负载物理主机上的虚拟机迁移到其他物理主机上,然后关闭或休眠低负载物理主机。由于用户请求是动态的,过多关闭或休眠物理主机容易增加物理主机的过载风险,影响数据中心服务质量。因此,如何在降低能耗的同时保证数据中心服务质量是目前虚拟机放置研究的重点。文献[8]以贝叶斯网络模型为基础提出了迁移与功耗感知的虚拟机放置方法,通过减少虚拟机迁移总量降低由于迁移带来的服务质量的影响。除了虚拟机迁移,物理主机运行时过载也是影响数据中心服务质量的重要因素。文献[9]针对物理主机运行时用户需求不确定的问题,提出一种鲁棒优化模型,并根据用户满意度进行资源分配。Melhem S.B等为了减少物理主机运行时过载情况,将活动物理主机分为低负载、正常、过载3种状态,利用马尔可夫模型预测物理主机的状态转移概率,通过降低物理主机过载概率改善数据中心服务质量[10]。文献[10]虽然考虑了物理主机运行时的过载情况,但未对数据中心能耗进行约束。同时,由于物理主机包含CPU、内存等多种资源,处于CPU过载状态的物理主机可能存在内存资源利用率低的问题。因此,仅用3种状态无法全面描述物理主机运行情况。为了解决目前虚拟机放置研究中存在的问题。本文提出一种基于多资源约束与Memetic算法的虚拟机放置方法。

1 虚拟机放置

虚拟机放置是为迁移虚拟机按照一定的规则挑选适合物理主机的过程。对于数据中心新创建的虚拟机和由于物理主机过载迁出的虚拟机,数据中心会将其加入待放置虚拟机集合。然后,利用虚拟机放置方法为待放置虚拟机挑选适合的物理主机。文献[4, 11]将虚拟机放置问题看作装箱问题。由于装箱问题是NP-hard问题[4],求解装箱问题一般采用启发式算法。例如:首次适应下降(first fit decreasing FFD)算法、最佳适应下降(best fit decreasing BFD)算法[4]。然而,虚拟机放置问题与一般装箱问题不同,虚拟机的资源请求是动态的,在生成放置策略时不仅要考虑虚拟机当前状态,还要考虑虚拟机资源请求的动态变化。由于传统启发式算法忽视了虚拟机资源请求的动态变化,采用FFD等算法进行虚拟机放置容易使物理主机负载不稳定,从而导致数据中心服务质量下降。文献[4]通过改进BFD算法提出了能耗感知最佳适应下降(power aware best fit decreasing PABFD)算法。PABFD算法首先将虚拟机按照资源请求情况进行排序,然后依次将虚拟机放置在能耗增量最小的物理主机上。PABFD算法有效降低了数据中心能耗。

为了从能耗和服务质量等多方面对数据中心进行优化,文献[11-13]结合多目标优化问题与智能算法提出了一系列基于智能算法的多目标求解算法,并将其应用于虚拟机放置问题。文献[11]提出一种基于遗传算法的虚拟机放置方法,首先将虚拟机看作具有内存和CPU 2个维度的物品,物理主机看作具有一定容量的箱子,然后建立一个最小化物理主机数量与最小化资源浪费的多目标优化模型,最后利用遗传算法求解该模型。文献[12]提出一种新的最小化资源浪费,估算模型,并建立一个最小化能耗与资源浪费的优化模型,利用Pareto支配理念结合蚁群算法求解。文献[13]提出最小化数据中心能耗与虚拟机迁移次数的优化模型,利用人工蜂群算法的搜索框架进行求解。上述文献通过智能优化算法求解虚拟机放置问题取得了比传统启发式优化算法更好的效果,但都存在计算时间长、效率低的问题。文献[14]正式提出Memetic算法,算法的核心是meme理论。Memetic算法在局部搜索时利用meme理论优化种群分布,加快了算法的收敛速度。但是,Memetic算法的设计结构决定了其更适用于离散问题的求解,而难以应用于连续型优化问题。

2 系统模型及问题描述

虚拟机放置问题是一个多资源约束的多目标优化问题[13]。建立多目标优化模型能够有效平衡数据中心能耗、资源利用率和服务质量之间的关系。

2.1 数据中心描述

数据中心物理主机可以用集合H={h1, …, hm}表示,hi代表数据中心的第i台物理主机。运行在物理主机上的虚拟机用集合VM={vm1, …, vmm}表示,vmi代表虚拟机i。虚拟机在物理主机上的放置关系用矩阵X ={xi, j}n×m, xi, j∈{0, 1}表示。当xi, j=1时,表示虚拟机vmj放置在物理主机hi上,反之,则表示虚拟机vmj未放置在物理主机hi上。RS代表资源集合,其中包括处理器、内存、带宽,即RS={CPU, RAM, BW}。Cr(vmj)是虚拟机jr类资源需求请求的总量,Cr(hi)是物理主机ir类资源配置总量。Ur(vmj)是虚拟机jr类资源的实际利用率。Dr(hi)是物理主机i上的虚拟机对r类资源的实际请求总量。

2.2 能耗估算

本文使用文献[4]的能耗估算模型。图 1展示了文献[15]所提供的物理主机功率与负载关系。由图 1可知,物理主机功率与CPU负载的关系是线性或亚线性关系。据此,可以将局部负载与功率视为线性相关,并利用(1)—(3)式计算活动物理主机能耗。

图 1 CPU利用率与功率关系 Fig.1 Relation between CPU utilization and host power
$ {{f_{{\rm{ power }}}}({h_i}) = \int_0^T {{P_d}} + k \times (u - {U_d}){\rm{d}}t} $ (1)
$ {k = \frac{{{P_u} - {P_d}}}{{{U_u} - {U_d}}}} $ (2)
$ {u = f(t)} $ (3)

(1)—(3)式中:u表示物理主机的利用率;Pd表示利用率u所处区间下限的功率;Pu表示利用率u所处区间上限的功率;Ud表示负载区间下限;Uu表示负载区间上限,负载u随着时间t变化而改变。

2.3 物理主机服务等级协议违例时间估算

运行时服务等级协议违例率[4](service level agreement violation time per active host, SLATAH)是全部物理主机出现服务协议等级违例时间占物理主机活动时间的百分比的平均值。SLATAH值直接关系到数据中心服务质量,SLATAH值越大,数据中心服务质量受到的负面影响越大。(4)式通过物理主机历史负载估算物理主机hi的SLATAH值。当物理主机hi上的虚拟机任意资源请求量大于该资源总量,则认为物理主机出现服务等级协议违例。

$ {f_{{\rm{ slatah }}}}({h_i}) = \frac{{{T_{si}}({D^r}({h_i}) > {C^r}({h_i}))}}{{{T_{ai}}}}, r{\kern 1pt} {\kern 1pt} \in {\kern 1pt} {\kern 1pt} {\kern 1pt} RS $ (4)

(4) 式中:Tsi是物理主机i出现服务等级协议违例的时间,即物理主机资源请求大于其资源总量的时间;Tai是物理主机i处于活动状态的总时间。

2.4 数据中心资源利用率估算

数据中心资源利用率是数据中心运营中一个重要指标,提高物理主机的资源利用率能够减少活动物理主机数量,降低数据中心能耗。为了更好地优化多资源数据中心的资源利用率,利用(5)式对数据中心的平均资源利用率进行估算。

$ {f_{{\rm{ utilization }}}}({h_i}) = \frac{1}{N}\sum\limits_{r{\kern 1pt} \in {\kern 1pt} {\kern 1pt} RS} {\frac{{{D^r}({h_i})}}{{{C^r}({h_i})}}} , r{\kern 1pt} {\kern 1pt} \in {\kern 1pt} {\kern 1pt} {\kern 1pt} RS $ (5)

(5) 式中,N代表物理主机资源种类的数量,本文中N=3。(5)式利用物理主机hi的实际资源请求和资源总量求得该物理主机所有资源的平均利用率。

2.5 虚拟机放置优化模型

评价数据中心是否高效的关键是能耗与服务质量[15-19]。低能耗意味着能够降低数据中心的运营成本。高服务质量能给用户带来更好的体验。减少物理主机的开启能够有效降低数据中心能耗。然而,如果将过多的虚拟机放置在同一台物理主机上将提高物理主机过载风险,影响数据中心服务质量。因此,在保证服务质量的前提下降低能耗,平衡能耗与服务质量的关系是进行虚拟机整合的重要目标。在数据中心,资源利用率与能耗和服务质量的关系十分密切,提高资源利用率能够降低能耗。但当物理主机的资源利用率超过一定范围时,高资源利用率的物理主机容易出现过载情况,造成数据中心服务质量下降。为了减少对服务质量的影响,在最大化物理主机资源利用率的同时,还应避免物理主机资源过载。根据以上分析,本文提出的虚拟机放置优化目标由(6)—(8)式表示。

$ {{\rm{目标}}:{\rm{min}}{F_{{\rm{ power }}}}(H, X)} $ (6)
$ {{\rm{min}}{F_{{\rm{ slatah }}}}(H, X)} $ (7)
$ {{\rm{max}}{F_{{\rm{ utilization }}}}(H, X)} $ (8)
$ (6) - (8){\rm{ 中 }}:{F_{{\rm{ power }}}}(H, X) = \sum\limits_{i = 1}^n {{f_{{\rm{ power }}}}} ({h_i}) $ (9)
$ {F_{{\rm{ slatah }}}}(H, X) = \frac{1}{n}\sum\limits_{i = 1}^n {{f_{{\rm{ slatah }}}}} ({h_i}) $ (10)
$ {F_{{\rm{ utilization }}}}(H, X) = \frac{1}{n}\sum\limits_{i = 1}^n {{f_{{\rm{ utilizition }}}}} ({h_i}) $ (11)
$ {\rm{约束}}:\sum\limits_{i = 1}^n {{x_{i, j}}} = 1{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} j{\kern 1pt} {\kern 1pt} \in {\kern 1pt} {\kern 1pt} {\kern 1pt} [1, \cdots , m] $ (12)
$ \begin{array}{*{20}{l}} {\sum\limits_{j = 1}^m {{C^r}} (v{m_j}) \times {U^r}(v{m_j}) \times {x_{i, j}} < {C^r}({h_i})}\\ {i{\kern 1pt} {\kern 1pt} {\kern 1pt} \in {\kern 1pt} {\kern 1pt} {\kern 1pt} [1, \cdots , n], r{\kern 1pt} {\kern 1pt} {\kern 1pt} \in {\kern 1pt} {\kern 1pt} {\kern 1pt} RS} \end{array} $ (13)

(6)—(8)式分别代表虚拟机按照矩阵X放置在物理主机集合H上,估算得到的数据中心能耗最低,服务等级协议违例率(service level agreement violation, SLAV)最低以及资源利用率最高几种情况。(9)—(11)式利用(3)—(5)式计算数据中心的能耗、服务等级协议违例率和平均资源利用率。(12)式约束一台虚拟机只能放置在一台物理主机上。(13)式约束放置在一台物理主机上的虚拟机请求资源的总和应该小于物理主机的资源总量。

根据上述分析可以发现,虚拟机放置问题是一个多目标优化问题。目前,在求解多目标优化问题时通常有2种方法:①通过加权求和的方式将多目标转化为单目标;②利用Pareto支配理念求出问题的Pareto集合[20]。加权求和的方式预先设定了权重,所得解单一。利用Pareto支配理念可以求得所有优化目标的折衷解集合,拥有更灵活的决策空间。因此,本文利用Memetic算法和Pareto支配理念求解(6)—(8)式Pareto集合。

3 模型求解

Memetic算法来源于文化算法与基因算法的融合。近年来,许多研究[18-21]表明Memetic算法在多目标优化问题上有着良好的表现。但虚拟机放置问题具有多资源的特性,传统Memetic算法无法同时优化多种资源配置,目前针对多资源虚拟机调度的研究还比较少。

本文通过改进Memetic算法中的局部搜索策略,结合虚拟机放置问题,提出一种基于Memetic算法的虚拟机放置(memetic algorithm-based VM placement MAVMP)方法,具体流程如下。

1) 初始化待放置虚拟机集合、物理主机集合,获取虚拟机的资源请求记录和物理主机的资源利用记录。

2) 为虚拟机和物理主机进行编码,并初始化种群,创建Pareto集合。

3) 对种群中个体进行适应度值的评价,更新Pareto集合。

4) 对每个个体进行局部搜索,计算搜索得到个体的适应度函数值,并根据适应度值更新Pareto集合和种群。

5) 判断是否满足终止条件,如果满足则输出Pareto集合中的解,算法结束。

6) 种群中的个体通过交叉变异生成下一代种群,并转到步骤3)。

步骤5)中的终止条件可以是Pareto集合连续未更新次数,或算法迭代次数。接下来本文将详细介绍上述流程中的编码和初始化种群、个体适应度值评价、局部搜索策略和交叉变异操作等内容。

3.1 个体编码与种群初始化

在Memetic算法中,每个个体代表问题的一个解,由不同个体组成的解的集合称为种群。个体利用不同基因组成表示不同的解结构。云计算资源调度中生成一次合理的放置方案需要确定虚拟机与物理主机的映射关系。合理的映射关系必须满足(12)式的约束,即一台虚拟机只能放置在一台物理主机上,同一台物理主机可以放置不同的虚拟机。根据以上条件,可以对个体进行如图 2的编码。其中,个体中基因数量等于待放置的虚拟机数量。个体上第i个基因存储了虚拟机i所放置的物理主机编号。例如,图 2中VM(N-1)放置在编号为10的物理主机上。采用这种编码方式产生的个体显然可以满足(12)式的约束。

图 2 个体编码示意图 Fig.2 Individual coding

种群初始化时需要确定待放置的物理主机集合。为了缩小解空间,提高算法效率,首先将资源利用率不超过70%的物理主机加入可用物理主机集合。为了避免出现物理主机不能满足虚拟机资源请求的情况,再将一部分空闲主机加入可用物理主机集合。空闲物理主机的数量应保证可以满足所有待放置虚拟机的资源请求。然后,对集合中的物理主机进行编号。对于个体上的每个基因,利用随机的方法为其选择物理主机,判断随机得到的物理主机是否满足(13)式的约束。如果满足约束则将该物理主机编号填入基因位,否则重新选择物理主机。智能算法中种群规模一般与问题规模相当。但由于Memetic框架的特性,使得Memetic算法相比其他智能集群算法种群规模小。本文将种群规模设置为20。

3.2 适应度值评价与Pareto集合更新

在利用Memetic算法求解多目标问题的过程中,适应度值评价是决定最终解质量的关键步骤。在用于求解单目标问题的Memetic算法中,通常先将个体按照适应度函数的值排序,然后存储适应度值最优的个体。多目标优化问题中存在多个适应度函数,无法直接将个体直接进行排序。因此,本文利用Pareto支配理念评价多目标优化问题中的个体。根据(6)—(8)式所提出的优化目标,个体适应度值定义为

$ \Delta {F_{{\rm{ power }}}}(indiv) = \sum\limits_{i = 0}^m {{f_{{\rm{ power }}}}} ({h_i} + v{m_{{\rm{ mig }}}}) - {f_{{\rm{ power }}}}({h_i}) $ (14)
$ \Delta {F_{{\rm{ slatah }}}}({\rm{ }}indiv{\rm{ }}) = \sum\limits_{i = 0}^m {{f_{{\rm{ slatah }}}}} ({h_i} + v{m_{{\rm{ mig }}}}) - {f_{{\rm{ slatah }}}}({h_i}) $ (15)
$ \begin{array}{*{20}{c}} {\Delta {F_{{\rm{ utilization }}}}({\rm{ }}indiv{\rm{ }}) = \sum\limits_{i = 0}^m {{f_{{\rm{ utilization }}}}} ({h_i} + v{m_{mig}}) - }\\ {{f_{{\rm{ utilization }}}}({h_i})} \end{array} $ (16)

(14)—(16)式分别估算了将待迁移的虚拟机按照个体进行放置后数据中心能耗增量、服务等级协议违例率增量与资源利用率增量。ΔFpower(indiv)的值越小,表示将虚拟机按照个体indiv放置后,数据中心能耗增量越小。由于对于不同个体数据中心的初始能耗相同,故而ΔFpower(indiv)越小,数据中心能耗越小。同理,ΔFslatah(indiv)值越小数据中心SLATAH值就越小。ΔFutilization(indiv)的值越大数据中心的资源利用率值越高。结合Pareto支配理念与(14)—(16)式,个体之间支配情况判断如下。

设indiv1, indiv2代表 2个个体,当且仅当满足下式条件时,indiv1支配indiv2成立。记作indiv1>indiv2

$ \begin{array}{*{20}{l}} {\Delta {F_{{\rm{ power }}}}({\rm{ }}indi{v_1}) \le \Delta {F_{{\rm{ power }}}}({\rm{ }}indi{v_2}) \wedge \Delta {F_{{\rm{ slatah }}}}({\rm{ }}indi{v_1}) \le }\\ {\Delta {F_{{\rm{ slatah }}}}({\rm{ }}indi{v_2}) \wedge \Delta {F_{{\rm{ utilization }}}}({\rm{ }}indi{v_1}) \ge }\\ {\Delta {F_{{\rm{ utilization }}}}({\rm{ }}indi{v_2})} \end{array} $
$ \begin{array}{*{20}{l}} {\Delta {F_{{\rm{ power }}}}({\rm{ }}indi{v_1}) < \Delta {F_{{\rm{ power }}}}({\rm{ }}indi{v_2}) \vee \Delta {F_{{\rm{ power }}}}({\rm{ }}indi{v_1}) < }\\ {\Delta {F_{{\rm{ slatah }}}}({\rm{ }}indi{v_2}) \vee \Delta {F_{{\rm{ utilization }}}}({\rm{ }}indi{v_1}) > }\\ {\Delta {F_{{\rm{ utilization }}}}({\rm{ }}indi{v_2}{\rm{ ) }}} \end{array} $

个体选择时,首先建立集合Pareto_Set用于存储符合Pareto支配理念的个体,其中Pareto_indivPareto_Set。初始化Pareto_Set=Ø。设在局部搜索中得到的个体的集合为Search_Set,其中Search_indivSearch_Set。根据Pareto支配理念,利用下面3种规则更新Pareto_Set

1) 如果$\exists $Pareto_indivPareto_Set,使得Search_indiv>Pareto_indiv成立, 则有Pareto_indiv=Search_indiv

2) 如果∀Pareto_indivPareto_Set,使得Search_indivPareto_indiv互不支配,则Pareto_Set=Pareto_Set∪{Search_indiv}。

3) 如果$\exists $Pareto_indivPareto_Set,使得Pareto_indiv>Search_indiv成立,则Search_indiv不是Pareto解。

在迭代过程中,当Pareto_Set连续2次不进行更新操作,则结束迭代。此时,Pareto_Set中的解为目标函数(6)—(8)式的Pareto最优解。

3.3 多资源约束的局部搜索策略

局部搜索过程是Memetic算法区别于其他智能算法的关键步骤[17]。虚拟机放置问题是离散型优化问题。对于离散型优化问题通常采用邻域搜索策略进行局部搜索。传统的邻域搜索策略需要将物理主机进行排序。在多资源虚拟机放置问题中,由于存在多种资源相互约束导致无法直接对物理主机进行排序。因此,本文提出一种基于多资源约束的局部搜索策略。

假设云数据中心虚拟机请求资源为3种,处理器(CPU)、内存(RAM)、带宽(BW)。由于多种资源的存在,在进行虚拟机迁移时,迁移请求资源类型不同的虚拟机将对物理主机造成不同的影响。如果一台虚拟机需要较多CPU资源,但内存使用量较低,此时如果将其放置在CPU利用率高的物理主机上则有可能导致该物理主机出现过载情况,而如果将其放置在CPU利用率低但内存利用率较高的物理主机上,不仅能够避免物理主机过载,而且还能提高该主机的资源利用率。因此,如果在虚拟机放置时能够考虑虚拟机资源的请求情况,那么将能得到更好的放置结果。

根据上述分析,本文将虚拟机按照资源请求量进行分类。如果一台虚拟机其CPU利用率(虚拟机实际CPU请求量除以虚拟机的CPU总量)最高,则将其称为以CPU为主要资源的虚拟机。同理,也可以将虚拟机分为以RAM或BW为主要资源的虚拟机。在局部搜索过程中,针对不同类型的虚拟机,可以制定不同的搜索策略。

本文将物理主机分别以3种资源的剩余可用量降序排列。物理主机的3种序列使得局部搜索时有3种不同的搜索策略。不同的搜索策略对局部搜索性能有着重要的影响。图 3展示了一台以CPU为主要资源的虚拟机按照不同的搜索策略产生的搜索路径。图 3标示了物理主机各个资源的剩余量和虚拟机各个资源的实际请求量以及当前利用率,图中上方物理主机按照CPU资源降序排列,下方物理主机按照RAM资源降序排列。由图 3可知,该虚拟机按照CPU资源序列进行搜索只需进行一次尝试,而利用RAM资源进行搜索时则需进行4次尝试。根据分析,如果将虚拟机分类融入到局部搜索过程,那么局部搜索的效率能够得到改善。

图 3 局部搜索示意图 Fig.3 Local search

本文利用虚拟机分类思想改进了Memetic算法的局部搜索策略,多资源约束的Memetic局部搜索策略如算法1。该策略针对个体中的每个基因,首先判断该基因位所代表的虚拟机的主要资源,然后将待放置物理主机按照主要资源的可用量降序排列,最后将序列中第1个满足虚拟机资源请求的物理主机编号存入该基因位。

算法1   基于多资源的Memetic局部搜索策略。

输入:vmlist,hostlist,individual

输出:NewIndiv

for (gene in individual)

Begin

  vm=vmlist.get(gene.id)

  将hostlist按照主要资源降序排列

  For (host inhostlist)

  Begin

    If (虚拟机vm能够放置在物理主机host) then

    Begin

      将NewIndividual上vm对应的物理主机设置为host

      Break

    End If

  End For

End For

If (NewIndiv==null) then NewIndiv=individual

3.4 交叉变异

交叉与变异操作是Memetic算法中的重要环节。通过交叉、变异操作能够实现算法的全局搜索。交叉操作首先选取父代个体,将选出的父代个体按照一定的策略进行交叉,从而生成子代个体。子代个体与父代个体不同,但又遗传了父代个体的基因特性,因此交叉操作能够在保留父代特性的前提下探索解空间。变异操作是保证种群多样性的重要部分。针对Memetic算法种群规模小的特点,变异操作能够避免算法陷入局部最优解。

进行交叉操作时,首先将种群中的个体两两配对作为交叉操作中的父代,然后保留父个体的前一半基因,将配对父个体的后一半基因位中的值互换得到子代。为了种群的多样性,对生成的子代个体进行变异操作。子代中每个基因位的值以一定概率随机变异。交叉、变异过程如图 4

图 4 个体交叉变异 Fig.4 Individual cross and variation

Parent 1与Parent2经过交叉、变异操作得到Child 1与Child 2。Child 1中有一位基因发生了变异。Child 2中有2位基因发生了变异。将经过变异的子代个体插入种群,同时移除其父代个体,生成新种群。

3.5 算法复杂度分析

在算法复杂度方面,MAVMP与传统的Memetic算法相比主要区别在局部搜索部分。传统的Memetic算法一次迭代的时间复杂度可以表示为O(XNM)。X是种群数量,N是个体上的基因数量,M是局部搜索所用时间,在虚拟机放置问题中M代表物理主机数量。

MAVMP对局部搜索过程改进后,其局部搜索部分的时间复杂度由维护物理主机序列和按序搜索O(Q) 2部分组成。一次局部搜索中最多有2台物理主机受到影响,将2台物理主机重新插入有序物理主机序列的时间复杂度为O(logM)。由于分类后的虚拟机按照有序的物理主机序列能够快速找到合适物理主机,按需搜索所用时间远远小于物理主机维护时间,即Q < < logM,因此,MAVMP一次迭代的时间复杂度可以表示为O(XNlogM),小于传统Memetic算法时间复杂度O(XNM)。由此可知,MAVMP方法能有效提高Memetic算法的时间效率。

4 实验设置 4.1 实验环境

真实数据中心的负载情况处于动态变化。在真实环境下复现数据中心负载情况会浪费大量的时间、人力和资源成本。因此,本文采用CloudSim工具模拟数据中心环境进行实验。CloudSim可以按照时间变化利用工作负载重现虚拟机资源请求,即模拟了数据中心负载的真实变化情况。本文实验中CloudSim每5分钟进行一次虚拟机迁移,一天的仿真实验中共进行了288次迁移,每次迁移都根据数据中心的实时负载变化进行。为了评价本文提出的算法,我们采用了文献[22]中记录的物理主机配置。虚拟机配置与亚马逊EC2平台相似。实验设置数据中心异构物理主机数量共为800台。虚拟机数量根据数据中心任务提交情况动态变化。表 1记录了实验中物理主机的详细配置情况。表 2记录了虚拟机的详细配置情况。

表 1 物理主机配置表 Tab.1 Physical machine instances
表 2 虚拟机配置表 Tab.2 Virtual machine instances

CloudSim仿真平台的运行环境对算法的时间开销有着重要影响,为了公平对比各个算法的时效性,本文中所有仿真实验均在相同环境下进行,下面将对仿真平台所运行的环境进行具体介绍。实验所用机型为DELL inspiron 15-5577笔记本电脑,操作系统为WINDOWS 10,CPU型号为Intel Core i7-7700HQ 2.8 GHz,内存为8 GB。

4.2 工作负载

仿真实验的工作负载数据来自真实数据中心BitBrains[23]。BitBrains是一家典型的中型云数据中心管理商,为众多企业提供业务计算服务。本文将BitBrains公开的数据集称为BitBrains数据集。BitBrains数据集中记录了数据中心CPU、内存、带宽3种类型的资源,符合本文对多资源数据中心的要求,因此本文选择BitBrains作为工作负载。BitBrains数据集中包含2013年8月全部数据中心的工作负载情况。为了公平展示各算法在不同负载情况下的虚拟机放置能力,本文随机选取其中10天进行实验,并通过表 3展示了BitBrains数据集10天工作负载数据的特征。

表 3 BitBrains的工作负载特征 Tab.3 Properties of BitBrains trace
4.3 评价指标

为了评价算法性能,本文使用文献[4]提出的6种性能评价指标:SLAV、能源消耗(energy consumption, EC)、虚拟机迁移次数(virtual machine migrations, VMM)、服务质量和能耗综合评价指标(energy and SLA violation, ESV)、由于迁移导致的服务下降(performance degradation due to migration, PDM)、SLATAH

SLATAH指由于活动物理主机在运行时资源过载导致的违反服务等级协议,定义如(4)式。PDM代表由于虚拟机迁移导致的服务质量下降,定义式为

$ PDM = \frac{1}{m}\sum\limits_{j = 1}^m {\frac{{C_j^d}}{{C_j^r}}} $ (17)

(17) 式中:Cjd代表虚拟机vmj由于迁移导致的未被满足的CPU资源请求量;Cjr代表虚拟机vmj的CPU资源总量;m代表虚拟机数量。

SLAV是用来评价单日内数据中心服务质量的综合指标,定义如(18)式。SLAV的值受当日数据中心SLATAHPDM的综合影响。当日数据中心的SLATAHPDM值越低则综合值SLAV越小,数据中心服务质量越高。

$ SLAV = SLATAH \times PDM $ (18)

EC代表数据中心一天的能源消耗。定义如(1)式。根据综合数据中心对低能耗和高服务质量的要求,定义服务质量和能耗综合评价指标ESV,如(19)式。ESV的值越低意味着当日数据中心的能耗和服务质量越平衡。

$ ESV = EC \times SLAV $ (19)

在数据中心资源调度中虚拟机的迁移会造成虚拟机的短暂停机,影响数据中心服务质量,因此, 虚拟机迁移量VMM是评价数据中心服务质量的重要指标。VMM值越低数据中心迁移虚拟机越少。

5 实验结果及分析

为了证明本文提出优化模型的有效性和高效性,本节对MAVMP方法和文献[4]提出的FFD放置方法,PABFD放置方法、文献[12]提出的基于蚁群系统的虚拟机放置(ant colony system algorithm for virtual machine, VMPACS)方法,文献[13]提出的能耗和过载概率感知的虚拟机放置(energy-aware and overloaded probability-estimation VM placement, EOPVMP)方法进行对比。对比试验中的参数设置采用了原文献中的参数设置,本文实验中对其参数未作调整。为了获得有效的对比结果,实验中利用不同的虚拟机放置方法和相同的虚拟机选择方法。物理主机过载检测方法联合实验,采用随机选择(random select, RS)法[4]作为虚拟机选择方法,绝对中位偏差(median absolute deviation, MAD)方法[4]进行物理主机过载概率估算。在相同过载检测算法和虚拟机选择算法的情况下使用不同的虚拟机放置算法进行实验能够反映出不同放置方法对数据中心的影响。

5.1 有效性

本节主要对比各个方法在BitBrains数据集上的各项评价指标。首先对各个算法的ECSLAVVMM以及ESV指标进行对比。表 4记录了5种虚拟机放置方法在不同指标上的表现。

表 4 BitBrains数据集测试结果 Tab.4 Simulation results using BitBrains trace

EC指标能够反映出不同方法对数据中心能耗的影响。通过表 4可以发现MAVMP方法的EC值最低,EOPVMP与PABFD方法略高于MAVMP方法,这说明了MAVMP方法能够有效优化数据中心能耗。由于VMPACS方法在放置虚拟机时缺乏对数据中心的能耗考虑,因此,VMPACS方法的EC值最高。

SLAV值代表了数据中心的服务质量(QoS),SLAV值越低数据中心的QoS越能得到保障。根据表 4可以发现MAVMP方法的SLAV值最小。这说明在5种不同的虚拟机放置方法中,采用MAVMP方法能够充分保障数据中心的QoS。FFD和PABFD方法的SLAV值较高,这是因为FFD与PABFD方法在进行虚拟机放置时忽视了虚拟机请求的变化。EOPVMP和ACS方法的SLAV值虽然高于MAVMP方法,但其对改善服务质量也有一定作用。

SLAV值是SLATAH值与PDM值的综合体现。为了深入分析不同方法对数据中心服务质量的影响,本文通过图 5图 6对比了5种虚拟机放置方法的SLATAH值与PDM值。因为MAVMP方法将最小化运行时服务等级协议违例时间作为优化目标,所以根据图 5可以看出,MAVMP方法的SLATAH值最小。VMPACS方法的SLATAH值与MAVMP相近。根据图 6可以发现在5种放置方法中,MAVMP方法的PDM值最小。这是因为MAVMP通过合理的虚拟机放置稳定了物理负载,从根本上减少了过载物理主机数量。过载物理主机的减少使得虚拟机迁移量下降,因此,MAVMP方法比其他4种方法能够更有效减少虚拟机迁移对数据中心QoS的影响。

图 5 SLATAH指标对比 Fig.5 Comparison of SLATAH
图 6 PDM指标对比 Fig.6 Comparison of PDM

由于虚拟机迁移会造成虚拟机短暂停机影响数据中心的服务质量,并且会增加数据中心的能耗,因此,在虚拟机整合中应尽量减少虚拟机的迁移量。如表 4,MAVMP方法的VMM值比EOPVMP方法高出12%,这是由于EOPVMP方法将减少虚拟机迁移量作为主要优化目标。通过深入分析不难发现,VMM值是数据中心能耗和服务质量在虚拟机迁移中的侧面表现形式,减少VMM是为了优化数据中心能耗和服务质量,因此,MAVMP方法的VMM值虽然略高于EOPVMP方法,但其从根本上优化了数据中心能耗和服务质量。

ESV是体现数据中心能耗与服务质量的综合指标。通过表 4可以看出,MAVMP方法的ESV值在5种方法中最低。这说明了MAVMAP方法能够利用Pareto支配理念在降低能耗和提高服务质量2个目标中找到折衷解,同时进一步说明了MAVMP方法在虚拟机放置过程中的有效性。

经过上文对MAVMP,EOPVMP,VMPACS,PABFD和FFD 5种虚拟机放置方法的分析比较,本文所提出的MAVMP方法有效改善了数据中心能耗和服务质量。

5.2 高效性

本节将从资源利用率、活动物理主机数量和时间开销方面评价MAVMP方法的高效性。因为在实际数据中心中负载具有规律性和周期性,所以本文采用数据中心一天的工作负载作为实验数据。数据中心每隔5分钟进行一次虚拟机整合,一天共整合288次。图 7显示了活动物理主机数量变化情况。图 8图 10显示了活动物理主机各个资源利用率情况。图 7中每组实验包括2个子图,图 7a是虚拟机整合的总体情况;图 7b是虚拟机第180—280次整合的细节展示。图 8图 10分别展示了活动物理主机在处理器、内存和带宽3种资源上的利用率情况。

图 7 活动物理主机数量 Fig.7 Number of running physical host
图 8 物理主机CPU资源利用率 Fig.8 CPU utilization of running physical host
图 9 物理主机内存资源利用率 Fig.9 RAM utilization of running physical host
图 10 物理主机带宽资源利用 Fig.10 BW utilization of running physical host

根据图 7b可以发现,在整合中采用FFD,EOPVMP和VMPACS作为虚拟机放置方法时曲线出现了大幅波动,即活动物理主机的突然增加然后又突然减少。这种现象是因为活动物理主机负载波动大,导致现有活动物理主机不够用,增加主机数量后,主机资源利用率随之下降,又引起了物理主机收缩过程,主机数量又大幅下降。利用MAVMP作为虚拟机放置方法的曲线平稳波动小。这说明MAVMP方法能够有效稳定物理主机负载,避免了负载波动带来的物理主机突增的情况。

资源利用率能够有效的反应数据中心的运营情况。通过图 8图 10可以看出,在过载检测和虚拟机选择方法相同的情况下,MAVMP方法的各个资源利用率最高。根据图 8图 9可知,实验中采用MAVMP方法的CPU利用率在80%~90%,内存利用率在70%~90%。由于数据中心对带宽资源请求量低,所以图 10中各方法的带宽利用率都不到10%。由图 8可以发现MAVMP方法与其他放置方法对比,曲线波动性更小,说明MAVMP方法能够有效稳定数据中心负载。利用MAVMP方法的内存利用率也高于其他方法。这是因为MAVMP方法将最大化资源利用率作为目标,有效平衡了物理主机各个资源利用率,提高了数据中心的平均资源利用率。

算法的时间开销是评价一个算法优劣的重要指标。在云计算环境下,由于数据中心负载随时间动态变化,所以虚拟机放置问题具有实时性。如果放置算法耗时长,那么数据中心的环境可能已经发生了改变。图 11展示了5种不同的方法10天的时间开销情况。由图 11可以发现,MAVMP,EOPVMP和VMPACS方法的时间开销明显大于FFD与PABFD方法。这主要是因为MAVMP,EOPVMP和VMPACS方法是基于智能算法的虚拟机放置方法,而FFD与PABFD方法是基于传统启发式算法的虚拟机放置的方法。虽然基于传统启发式的虚拟机放置方法时间开销小,但是由于其对改善数据中心能耗和服务质量的能力不如基于智能算法的方法,所以在进行虚拟机放置时,智能算法仍具有优势。

图 11 时间开销 Fig.11 Time cost

图 11中MAVMP方法的时间开销明显小于VMPACS方法与EOPVMP方法。这说明了本文提出的MAVMP方法能够有效减少智能算法应用于虚拟机放置的时间开销。

通过本节分析可以发现MAVMP方法不仅能够有效减少活动物理主机数量,提高数据中心资源的利用率,还能够降低智能算法应用于虚拟机放置问题的时间开销。因此, 利用MAVMP方法进行虚拟机放置能够保障数据中心高效运行。

6 总结

本文对云计算数据中心中的虚拟机放置问题进行了研究,根据降低能耗、保证服务质量和提高资源利用率的3个目标,建立了最小化能耗、最小化运行时服务等级协议违例率和最大化资源利用率的优化模型,并提出了MAVMP方法。仿真实验表明,利用MAVMP方法进行虚拟机放置在能耗、资源利用率以及服务质量的评价指标上都有着良好表现,并且减少了智能算法应用于虚拟机放置问题的时间开销。

参考文献
[1]
SHANG P J, WANG R J, WANG Q D. A novel power management for CMP systems in data-intensive environment[J]. IEEE Transactions on Computers, 2016, 65(6): 1816-1830. DOI:10.1109/TC.2015.2458854
[2]
ZHOU Z, ABAWAJY J, CHOWDHURY M, et al. Minimizing SLA violation and power consumption in Cloud data centers using adaptive energy-aware algorithms[J]. Future Generation Computer Systems, 2018(86): 836-850.
[3]
MAO Y Y, ZHANG J, LETAIEF K B. A Lyapunov Optimization Approach for Green Cellular Networks with Hybrid Energy Supplies[J]. IEEE Journal on Selected Areas in Communications, 2015, 33(12): 2463-2477. DOI:10.1109/JSAC.2015.2481209
[4]
BELOGLAZOV A, BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[J]. Concurrency and Computation:Practice and Experience, 2012, 24(13): 1397-1420. DOI:10.1002/cpe.1867
[5]
SRIKANTAIAH S, KANSAL A, ZHAO F. Energy aware consolidation for cloud computing[J]. Cluster Computing, 2008, 12(1): 10-10.
[6]
VERMA A, AHUJA P, NEOGI A. Power and migration cost aware application placement in virtualized systems[C]//ACM/IFIP/USENIX 9th International Middleware Conference. Berlin, Germany: Springer-Verlag, 2008: 243-264.
[7]
古英汉, 伊鹏. 多虚拟机动态迁移情景下的服务功能链调整方法[J]. 小型微型计算机系统, 2017, 38(5): 1022-1027.
GU Y H, YI P. Method of Service Function Chain Adjustment Based on Multi-VM Live Migration[J]. Journal of Chinese Computer Systems, 2017, 38(5): 1022-1027. DOI:10.3969/j.issn.1000-1220.2017.05.022
[8]
LI Z H, YAN C Y, YU X R, et al. Bayesian network-based virtual machines consolidation method[J]. Future Generation Computer Systems, 2017(69): 75-87.
[9]
LI Y, LIU J, CAO B, et al. Joint Optimization of Radio and Virtual Machine Resources with Uncertain User Demands in Mobile Cloud Computing[J]. IEEE Transactions on Multimedia, 2018, pp(99): 1-10.
[10]
MELHEM S B, AGARWAL A, GOEL N, et al. Markov prediction model for host load detection and vm placement in live migration[J]. IEEE Access, 2018(6): 7190-7205.
[11]
HALLAWI H, MEHNEN J, HE H M. Multi-capacity combinatorial ordering GA in application to cloud resources allocation and efficient virtual machines consolidation[J]. Future Generation Computer Systems, 2016, 69(4): 1-10.
[12]
FARAHNAKIAN F, ASHRAF A, PAHIKKALA T, et al. Using Ant Colony System to Consolidate VMs for Green Cloud Computing[J]. IEEE Transactions on Services Computing, 2015, 8(2): 187-198. DOI:10.1109/TSC.2014.2382555
[13]
LI Z H, YAN C Y, YU L, et al. Energy-aware and multi-resource overload probability constraint-based virtual machine dynamic consolidation method[J]. Future Generation Computer Systems, 2018(80): 139-156.
[14]
MOSCATO P, PLATA L, NORMAN M. A memetic approach for the traveling salesman problem implementation of a computational ecology for combinatorial optimization on message-passing systems[C]//Proceedings of International Conference on Parallel Computing and Transport.[S.l.]: [s.n.], 1992: 1-10.
[15]
KUSIC D, KEPHART J O, HANSON J E, et al. Power and performance management of virtualized computing environments via lookahead control[J]. Cluster Computing, 2009, 12(1): 1-15.
[16]
LI H J, ZHU G F, ZHAO Y Y, et al. Energy-efficient and QoS-aware model based resource consolidation in cloud data centers[J]. Cluster Computing, 2017, 20(7): 1-11.
[17]
段海滨, 张祥银, 徐春芳.仿生智能计算[M].北京: 科学出版社, 2011: 132-137.
DUAN H B, ZHANG X Y, XU C F. Bionic intelligent computing[M]. Beijing: Science Press, 2011: 132-137.
[18]
SONCCOALVAREZ J, MUNOZ D, AYALA-RINCON M. Opposition-based memetic algorithm and hybrid approach for sorting permutations by reversals[J]. Evolutionary Computation, 2018, 27(2): 1-34.
[19]
陈小娇, 陈世平. 基于DEA的能耗感知虚拟机资源分配算法[J]. 小型微型计算机系统, 2015, 36(1): 167-171.
CHEN X J, CHEN S P. Energy-aware Virtual Machine Resource Allocation Algorithm[J]. Journal of Chinese Computer Systems, 2015, 36(1): 167-171. DOI:10.3969/j.issn.1000-1220.2015.01.031
[20]
李智勇, 陈少淼, 李仁发, 等. 异构云环境多目标Memetic优化任务调度方法[J]. 计算机学报, 2016, 39(2): 377-390.
LI Z Y, CHEN S M, LI R F, et al. Multi-objective memetic algorithm for task scheduling on heterogeneous cloud[J]. Chinese Journal of Computers, 2016, 39(2): 377-390.
[21]
HAVEMANN F, GLASER J, HEINZ M. Memetic search for overlapping topics based on a local evaluation of link communities[J]. Scientometrics, 2017, 111(2): 1089-1118. DOI:10.1007/s11192-017-2302-5
[22]
BELOGLAZOV A, BUYYA R. Openstack neat:a framework for dynamic and energy-efficient consolidation of virtual machines in OpenStack clouds[J]. Concurrency and Computation:Practice and Experience, 2015, 27(5): 1310-1333. DOI:10.1002/cpe.3314
[23]
SHEN SIQI, BEEK V, IOSUP A. Statistical characterization of business-critical workloads hosted in cloud datacenters[C]//IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Shenzhen, China: IEEE, 2015: 465-474.