论文研究-一种迁移成本可感知的虚拟机整合算法 .pdf

所需积分/C币:9 2019-08-20 12:31:28 521KB .PDF
收藏 收藏
举报

一种迁移成本可感知的虚拟机整合算法,窦晖,齐勇,针对当前IaaS数据中心硬件资源利用率比较低的问题,提出了一种迁移成本可感知的虚拟机整合算法,可以在给定的迁移成本约束下完成��
山国武获论文在丝 http:/www.paper.edu.cn 12多维资源虚拟机整合问题形式化 假设在每个时间槽开始时,IaaS数据中心使用 DotProduct算法进行新创建用户虚拟机 实例的部署。由于只关注新创建的虚拟机实例如何部著,在时间槽t的部署结束后,数据中 80心的服务器开机数可能会达到特定的阙值,需要对数据中心剩余的用户虚拟机实例进行整 假设在时间槽t的部署结束后,数据中心剩余的用户虚拟机实例总数为M(),并用 acm()表小这些虚拟机实例的集合。虚拟机实例与服务器之间的放置关系用二进制变量 x(以)米表示,x(1)=1表示虚拟机实例j被部署在服务器上。当虚拟机整合完成后,所 85有的用户虚拟机实例必须被部署到某一台服务器上: ∑x2()=1,v∈achm() 同时,所有用户虚拟札实例的硬件资源需求都应该得到满足,也就是说部署到同一台服 务器上的虚拟机对每种硬件资源的需求总和必须都不能超过服务器上相应的资源容量 ∑x()≤C,M∈[D]v∈[ (2) jEacrvm(o) 此外,由于虚拟杋迁移亼造成性能和能耗开销,一个可行的虚拟机整合算法必须要考虑 整合过程带来的虚拟机迁移成木。木文用虚拟机实例的迁移次数来代表虚拟机的迁移成木, 因此,虚拟机整合过程中总的虚拟机迁移次数mi()必须要低于迁移成本约束 MaxMiglimes mig(t)≤ Maxmiglimes 95值得注意的是,虚拟机整合过程中的辽移次数很难汁算,凵有的工作也只能尽量减少总的迁 移次数,因此无法直接用来解决带有迁移成本约束的虚拟机整合问题。 众所周知,当所有的用户虚拟机实例被部署到尽量少的服务器上时,IaaS数据中心的硬 件资源利用率最大。本文使用个二进制变量y()表示服务器i是否处于开机状态, y(t)=1表示有一个或多个用户虚拟机实例被部署到服务器计上,而y()=0则表示服务 100尜讠并没有被部署虚拟机,可以关闭服务器或者将服务器调节全低能耗状态以节约运营成 本。由于任意一个用户虚拟机实例被部署到服务器i上都会使y(t)=1成立,所以虚拟机整 合完成后必须满足如下约束: y(t)≥x(t),v∈[1M, dj actim() 此时,laS数据中心服务器的总开机数 OpenHos(1)的计算公式如下 Openllost()=2y(t) 根据以上措述,最终将带有迁移成本约束的多维资源虚拟机整合问题形式化为下面的优 化问题: min OpenHost ( 山国武获论文在丝 http:/www.paper.edu.cn ∑(0)=1camt subject to ∑x(),rk≤Ck,k∈[D],vi∈[,MI mig(t)s MaxMigTimes y(t)≥x(,vic[,N],vcacrwm(t) 110 优化问题(5)实际上是一个NP-hard的组合优化问题。因此,在可行的时间内很难求 出理论上最优的虚拟机整合策略。本文基于模拟退火算法设计并提出了优化问题(5)的一 种启发式算法,能够在满足迁移成本约束的前提下完成IaS数据中心的虚拟机整合。 2基于模拟退火的虚拟机整合算法 21算法的基本设置 115 由于虚拟机迁移成本约束的存在,已有的虚拟机整合算法不能直接用来解决优化问题 (5)。木文基于模拟退火算法设计并提出了一种迁移代价可感知的虚拟机整合算法 SAVMC,可以在给定的迁移成木约束下尽量减少laS数据中心服务器的廾机数、提高硬件 资源利用率。根据模拟退火算法的思想, SAVMO算法的基本设置如下 21.1虚拟机整合问题的解空间 120 优化问题(5)的每一个可行解都代表一种满是迁移成本约束的虚拟机整合策略。因此, 整合之前虚拟机实例的原始部署状态是优化问题(5)的初始可行解。为了实现的筍便,本 文使用一个整数矩阵VoH来表示一个可行解 fhostid je actim(t) (6) 其中acm()是当前时间槽t内用户虚拟机实例的集合,矩阵Wo中每一个元素hoid 125的值代表了用户虚拟机实例j应该被部署到编号为 hostid,的服务器上。 212新解的产生规则 虚拟机整合算法 SAVMC的目标是在优化问题(5)的解空间中不淅寻找到更优的新解, 从而在迁移成本的约束下尽量减少IaS数据中心服务器的开机数。由于迁移成本约束的存 在,算法必狈要能够准确讣算岀每一个新解所造成的虚拟机迁栘次数。为此,算法首先随机 130的从用户虚拟机实例集合achm()中选择个虚拟机实例,然后随机的从满足约条件(1) (2)(4)的服务器集合中选择一个服务器将该虚拟机实例迁移过去,产生优化问题(5) 的个新解oH。因此,除了被随机选出的那个虚拟机实例,新解VtoH中其余用户虚拟 机实例的部署状态与之前完全相同,也就是说新解Vo厂只带来了一次虚拟机迁移。通过迭 代的产生新解并且按照一定规则接受新解,SAVⅥC算法最终能够准确计算出其在虚拟机整 135合过程中总的迁移次数,保证迁移成本约束得到满足。 21.3新解的接受规则 为了尽量减少IaS数据中心服务器的开机数,虚拟机整合算法 SAVMC还需要按照一 定的规则选择是否接受新解,侏证虚拟机整合过程是在向减少开机数的优化目标前进:一方 面,如果新解通过虚拟机迁移可以减少总的廾札数目,那么直接接受该新解:另一方面,如 4 山国武获论文在丝 http:/www.paper.edu.cn 140果虚拟机迁移之后新解并没有减少开机数,那么按照接受概率 Acprob来接受: en AcProb=(Utilor-Utilold)Teminit UilM是被选出的虚拟机实例迁移之前其所在服务器在各维资源上的加权利用率,Ctil 是虚拟机实例迁移之后目标服务器的加权利用率, Tem是模拟退火过程中的当前温度, Tem是为模拟退火过程设置的初始温度。按照上述接受规则, SAVMC算法可以通过一次 145或者多次虚拟机迁移来减少服务器的丌机数,这样可以避免在进行虚拟机整合过程中系统陷 入个局部最优的状态。通过不断按照上述接受规则选择优化问题(5)的新解,虚拟机整 合过程最终会在当前温度下降为0或者虚拟机迁移次数达到约束条件后结束 214算法中控制参数的取值 根据模拟退火算法的思想,虚拟机整合算法 SAVMC中主要有三个比较重要的控制参 150数:初始温度Temm,温度下降的步长Temp和每个温度下新解的迭代次数 lter mun。这 些参数的不冋取值会影响SAVM℃算法寻求最优解的质量和效率:一般来说,初始温度和新 解的迭代次数设置的越大,温度下降的步长设置的越小, SAVMO算法输出的虚拟机整合策 路越理想,但同时算法的执行时间也就越长。因此,在实际应用中必须根据具体的需求对算 法中的控訇参数进行设置。本文根据优化问题(5)和实验配置苎试了几种不同的参数设置 155并最终做出以下设定:初始温度Tem,的值为100,温度下降的步长Tem为10,每个温 度下新解的迭代次数erMm为5*M(t),其中M()为当前时间槽t内的用户虚拟机实例 总数。 2,2算法的工作过程 为了求解优化问题(5),本文基于模拟退火算法设计并提出了一和迁移成本可感知的虚 160拟机整合算法 SAVMO。假设IaS数据中心的服务器开机数在时间槽t达到特定的阙值,需 要使用 SAVMC算法对数据中心剩余的用广虚拟机实例进行整合,算法的具体L作过程如 下:首先,算法在当前温度下,迭代的为优化问题(5)产生新解,并且按照接受规则决定 是否接受新解。如果选择接受新解,则将当前的虚拟机迁移次加1。达代次数由算法的控 制参数 lterNur决定;然后,当迭代完成之后,算法将当前温度降低一个步长Temn;重 165复前面两个步骤直到当前温度下降为0或者当前虚拟机迁移次数达到约束条件,算法终止。 这时, SAVMC算法会为优化问题(5)输出一个有效的可行解,能够在保证虚拟机迁移成 本约束的前提下尽量减少IaS数据中心服务器的开机数,提高哽件资源使用率。 SAVMC算 法的伪代码实现如表1所示。 23算法的复杂度分析 70 根据 SAVMO算法的工作过程可知,算法的时间复尕度与初始温度、温度下降的步长以 及每个温度下新解的迭代次数紧密相关。由于每个温度卜新解的一次迭代所需用的计算时间 Tem 为O(1)级别,SAMC算法的时门复杂度最终可以表示为OeNm 值得注 意的是,由于虚拟机迁移次数约束的存在,上述时间复杂度实际上是一个保守的估计:当虚 山国武获论文在丝 http:/www.paper.edu.cn 拟机整合过程中总的虚拟机迁移次数达到约束条件吋,算法会立刻终止。本文在实验部分对 175实际应用中 SAVMO算法的时间开销及其影响做了详细讨论。 SAVMC: Simulated annealing-based vm consolidation 1.Input: initial vM placement, VM resource requirement, host capacity, maximum migration times 2. Output: policy of VM consolidation 3.em=100,7em2=100 Te step =10 IterNum=5*M(t), mig(t)=0 4. while Temaur >0 and mig(t)< MarMig Times do 5. for i=1. terNum do 6. Randomly generate a new point 7. if The number ofopen hosts is reduced then 8. Accept the new point mig(()=mig(t)+1 10 else 11 Calculate the acceptance probability Acprob of the new point if AcProb>rand ()then Accept the ncw point; 14. mig (a)=mig(0) 15 Drop the new point 17 d end 18. end 19. end 20. Temu=Temeur-Tem e 21.end 表1:虚拟机整合算法 SAVMC的伪代码 Tab.l: Pscudo codc of savmc 3实验结果 31实验设置 180 本文通过模拟实验的方式验证虚拟机整合算法 SAVMC的性能。在模拟的IaS数据中 心环境中,数据中心共有1000台同构的服务器,服务器的硬件资源包括CPU和内存两种, 且每一种硬件资源的最大容量均为1。为了模拟IaS数据屮心用户虚拟机实例的动态创建和 撤销,假设在每个时间槽开始时,新申请创建的虚拟机实例个数服从均值为50的泊松分布, 并且每个虚拟机实例的运行寿命服从均佰为10个时间槽长度的泊松分布。用户虚拟机实例对 185每一种硬件资源的需求都是随机从预定义的集合{0.,0.2,…1}中选取的。模拟实验共运行 100个时问槽,默认的时间槽长度为1个小时 在每个时间槽开始时,aS数据中心使用 DotProduct算法对新创建的用广虚拟机实例 进行部署。由于用户虚拟机实例的动态创建和撤销,只关注新创建的虚拟机实例如何部署会 不可避免降低laS数据中心的使件资源利用率。因此,对于服务器的开机数超出下狠值B 190的比例大于预先设定的阈值TH的时间槽t,使用 SAVMO算法进行虚拟机整合。其中 服务器廾机数的下限值B等」满足所有用户虚拟机实例对任一种硬件资源的需求总量所需 山国武获论文在丝 http:/www.paper.edu.cn 要的服务器数量的最大值,其计算公式如下 B=mx「∑nC.「∑m/C J∈ act() j∈cw(1) 根据模拟的实验环境,将启动虚拟机整合的阈值TH,设置为25%。此外,将时间槽t虚拟 195机的迁移次数约束设置为0.1*M(2),也就是说在虚拟机整合过程中最多只会有10%用户 虚拟机实例会被迁移,遭受可能的性能损失。最后,为了比较 SAVMC算法的性能,在模拟 实验中还使用了 GDotProduct算法在冋同样的时间糟进行用户虚拟机实例的整合。 GDotProduct 算法将时间慒t的所有用户虚拟机实例利用 DotProduct算法重新部署,是一和不考虑迁移成 本约束的虚拟机整合算法。 20032SAⅴMC算法的效果与分析 根据之前的措述,此实验选择在服务器开机数超出下限值比例大于阈值的9个时间槽分 别使用 SAVMO算法和 GOth' roduct算法进行虚拟机整合,以验证 SAVMC算法在模拟实验 环境中的性能。由于 SAVMO算法每次产生的可行解并不完全一样,所以在同一时间槽内将 SAVMC算法运行5次并取其输出结果的均值。 口noFr」”t目 GDotProduct S sAVi 日 GDoIPIO四 SAVMC田 Curislrdinl 50 0000m0 开300 机 17 吋间槽 时间槽 205 图1虚拟机整合前后服务器开机数的比较 图2虚拟机整合过程产生的江移次数的比较 Fig 1 Open host number after VM consolidation Fig2 Migration times after Vm consolidation 虚拟机整合前后IaS数据中心服务器的丌机数如图1所示。从图中可以看出,与 DotProduct算法的初始部署状态相比,使用S^VMC算法进行虚拟机整合之后可以将这9个 210时问槽的服务器开机数平均减少471%。而在第80个时间槽, SAVMO算法可以将开机数减 少多达6.65%。因此,使用 SAVMC算法进行虚拟机整合将有助于降低IaaS服务提供商的基 础设施成本和电力成本。这些突出的改进结果来源于 SAVMC算法可以通过虚拟机迁移逐步 的将原始的虛拟机部署状态向着减少服务器开机数、提髙资源利用率的方向调整。此外,相 比于完全不考虑迁移成本约束的虚拟机整合算法 GDotProduct, SAVMO算法的结果依然要 215賂优于前者。因此,本文提出的虚拟机壟合算法 SAVMO可以有效的减少IaS数据中心服 务器的廾机数。 SAMC算法与凵有的虚拟札整合算法最大的不同之处在于其可以在给定的虚拟机迁移 成本约束下尽量减少服务器的丌机数,以提高laS数据中心的硬件资源利用率。图2分别展 示了 GDot Product算法和 SAVMC算法在上述9个时间槽进行虚拟机整合所产生的迁移次数。 220如图所示,由于完全不考虑虚拟机的迁移成本,GDot! roduct算法的迁移次数无法满足约束 条件。相较而言, SAVMC算法的迁移次数全部都小于(第9个和第99个时间槽)或等于当 前时间糟的虚拟机迁移成本约束。结合图1和图2可以发现,本文提出的虚拟机整合算法 SAVMC确实可以在给定的虚拟机迁移成本约束下有效减少IaS数据中心服务器的开机数 山国武获论文在丝 http:/www.paper.edu.cn 300 293.76 均50 16840711l13 16592 T83863.15 81 100 时间槽 225 图3 SAVMC算法的执行时间 Fig 3 Execution time of SAVMC 最后,图3展示了 SAVMO算法在上述9个时间槽的平均执行时间,并用误差线的形式给 山了执行吋间的最大值与最小值。从图中可以看出,使用 SAVMC算法可以在3分钟之内完 成绝大部分时间槽的虛拟机整合。算法在第9个时间槽和第99个时间槽的执行时问略长,但 230平均也可以在5分钟之内完成。根据之前对算法工作过程的描述,虚拟机整合过程会在系统 温度下降为0或者迁移次数达到给定的约束条件之后终止。因此,如图2所示,由于算法在第 9个时间槽和第99个时间槽产生的迁移次数小于约束条件,算法的执行时间也就比其他时间 槽要长。这与之前对算法的时间复杂度的分析保持一致。考虑刭模拟实验中的时间槽长度为 1个小时,并且程序运行在一台 Dell Optiplex9010( Intel core i7-3770处理器,4GB内存)台 235式机上,算法的执行时间在实际应用中是可以接受的。 33不同的虚拟机资源需求类型下SAMC算法的效果与分析 在真实的IaS数据中心,用户虚拟机实例对各种硬件资源的需求之间可能会存在某种 关联关系此实验选择了 PosCo和 Ncg Cor两利不同的虚拟机资源需求类型来验证 SAVMC 算法的性能。在 PosCo类型下,虚拟机实例对CPU资源的需求量r与对内存资源的需求 240量r∞m之间正相关:r随机从预定义的集合{0.2,0.3,…,0.,7}选取,而rn的值则随机在 m-0.m,cm+0.中产生:在 Neg Cor类型下,cm与m之间负相关:m同样是 随机从预定义的集合90203,07号选取,而m则随机在{09-m,1-m1rm}中 生成。此外,根据模拟的实验环境,分别将 Pos Cor和 Neg Cor类型下使用 SAVMC算法进行 虚拟机整合的阈值设置为12%和18%,模拟实验的其他配置参数则与之前实验设置的描述 245致。 H-Do% Product SAVMO H-Do Product 340 258259251 251251 5+325 250- 246 3132132 的240 的315 310 35 225 290 656683 时间槽 时间槽 图4 PoSCo类型下整合前后服务器开机数的比较图 5 Neg Cor类型下整合前后服务器开机数的比较 Fig 4 Open host number under poscor Fig 5 Open host number under NegCor 由于 SAVMC算法每次产生的可行解并个完全一样,所以在同一时间槽内将 SAVMC算 山国武获论文在丝 http:/www.paper.edu.cn 250法运行5次并取其输出结果的均值。 Pos Cor和 NegCor类型卜虚拟机整合前后laS数据中心 服务器的开机数变化分别如图4和图5所示。从图中可以发现,在 Pos Cor类型下,使用 SAVMC 算法进行虚拟机整合可以将这10个时间槽的服务器开机数平均减少6.10%;在 NegCor类型 下,使用 SAVMO算法则可以将需要进行虚拟机整合的7个时间槽的服务器开机数平均减少 600%,其屮在第73个时间槽,开机数减少多大748%。此外,算法在虚拟机整合过程中产 255生的迁移次数全部都小于或等于当前时间槽的虚拟机迁移成本约束(由于空间限制,这里省 眳了详细的数据)。因此,在不同的虚拟机资源需求类型下, SAVMC算法同样可以在给定 的迁移成本约束下有效的减少laS数据中心的服务器开机数,从而提高硬件资源利用率。 结论 IaS已经成为最为主流的云计算服务模式之一。本文针对当前IaS数据中心硬件资源 260利用率比较低的问题,提岀了一种迁移成木可感知的虚拟机整合算法。该算法基于模拟退火 算法的思想,通过逐次増加虚拟机的迁移次数迭代的生成新解,并能够准确计算岀虚拟机整 合过程所产生的迁移次数,从而可以在给定的迁移成本约束下完成多维资源虚拟机实例的整 合;通过为新解设置一定的接受规则,侏证虚拟杋整合过程冋开机数减少、资源利用率提高 的优化目标前进。模拟实验的结果表明,木文提出的多维资源虚拟机整合算法可以在给定的 265迁移次数约束下将服务器的开机数平均减少471%,有效的提高了laaS数据中心的硬件资 源利用率。此外,该算法在不同的虚拟机资源需求类型下同样有效。该算法有助于降低IaaS 服务提供商的基础设施成本和电力成本。 参考文献]( References) [11 LIU H. A measurement study of server utilization in public clouds C]/Proceedings of the 9th IEEE 270 Intcrnational Confcrcncc on Dcpcndablc, Autonomic and Sccurc Computing Sydncy, NSW, USA: IEEE, 2011 435-442 [2] WEI L, HE B, FOH C H. Towards multi-resource physical machine provisioning for laas clouds [C]/Proceedings of the 2014 IEEE International Conference on Communications. Sydney, NSW USA:IEEE,2014:3469-3472 275 (3)ZIIANG Y, ANSARI N. i heterogeneity aware dominant resource assistant heuristics for virtual machine consolidation[C]/Proceedings of the 2013 IEEE Global Communications Conference, Atlanta, GA, USA: IEEE 2013:1297-1302 14 PANIGIRAITY R, TALWAR K, UYEDA L, et al. Ileuristics for vector bin packingloL]. 201 http://kunaltalwar.org/papers/vbpacking.pdf 280 15 BELOGLAZOV A, BUYYA R. Adaptive threshold-based approach for energy-efficient consolidation of virtual machines in cloud data centers[c]i Proceedings of the 8th International Workshop on Middleware for Grids, Clouds and e-Science. New york. NY. USA: ACM. 2010. 4 [6]李铭大,毕经平,李忠诚.资源调庋等待销感知的虚拟札整合[J.软件学报,2014,25(7):1388-1402 [7 LIU H, JIN H, XU CZ, ct al. Pcrformancc and cncrgy modeling for livc migration of virtual machines[J] 285 Cluster computing, 2013, 16(2 ): 249-264 [8 SUNA X, SUA S, YANGA F. Adaptive virtual machine replacement for multi-dimensional aware server consolidation in data centers[J] Journal of Information Computation Science, 2013, 10(3): 633-643 [9 ZHANG Z, XIAO L, CHEN X, et al. A Scheduling Method for Multiple virtual Machines Migration in Cloud[J] Network and Parallel Computing, 2013: 130-142 290 0] BROOKS S P, MORGAN B J T. Optimization using simulated annealing []. The Statistician, 1995, 44(2) 241-257

...展开详情
试读 9P 论文研究-一种迁移成本可感知的虚拟机整合算法 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_39840924 你的留言是对我莫大的支持
2019-08-20
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
最新推荐
论文研究-一种迁移成本可感知的虚拟机整合算法 .pdf 9积分/C币 立即下载
1/9
论文研究-一种迁移成本可感知的虚拟机整合算法 .pdf第1页
论文研究-一种迁移成本可感知的虚拟机整合算法 .pdf第2页

试读结束, 可继续读1页

9积分/C币 立即下载 >