文超，胡晓勤（四川大学计算机学院，成都　610065）

基于OpenStack的虚拟机初始放置算法研究

文超，胡晓勤
（四川大学计算机学院，成都610065）

0　引言

近些年来，云计算已经成为一种流行的计算模式，它一般用来在互联网上托管虚拟机和提供服务[1]。云计算最大的贡献在于它改变了硬件物理资源的分配方式，可以根据用户的需求弹性的分配计算、存储、网络等资源。云计算主要分为三种服务类型：基础设施即服务（IaaS），平台即服务（PaaS），和软件即服务（SaaS）。OpenStack是一种开源的IaaS云计算平台，是目前最流行的开源云计算平台，主要将物理资源CPU、内存、磁盘等硬件设施虚拟化为资源池提供给用户分配使用。国内也已经有大型公司如新浪、中国移动等搭建使用OpenStack云平台并进行二次开发，同时，由于其开源性，大大减少了中小企业云平台建设成本，使得Open-Stack得到了广泛的推广，也让云计算真正的走进了企业。

随着云计算突飞猛进的发展，云平台下基础设施的规模也不断扩大。大到数据中心成千上万的物理节点部署在云计算平台中，小到几十上百的物理节点在中小企业中部署。这些都是充分利用云计算来提高物理资源的利用率，但是随着虽然物理节点的增多，不合理的虚拟机放置算法却会降低整个平台的资源利用率。虚拟机的放置是指在初始创建虚拟机的时候，将所要创建的虚拟机映射到某一物理节点上。如果虚拟机放置到不合适的物理节点上，将会造成资源浪费的问题。例如要放置的物理机的CPU资源很充足，内存资源较少，而创建的虚拟机却是需求CPU很少，需求内存很多的情况，物理机的CPU和内存的利用率的差距进一步扩大，这样会造成物理机内存剩余资源不足以创建任何虚拟机时，但CPU资源却有很大的剩余，从而浪费了CPU资源。

由此可以看出虚拟机的放置问题是云基础设施中改善资源利用率的一个重要途径。对于中小企业，物理资源有限，如何高效的利用资源，提高资源的利用率就显得格外重要。

现有的对于云计算虚拟机初始化放置的研究主要分为传统启发式方法如首次匹配算法、最佳匹配算法和生物智能启发式算法如遗传算法、蚁群算法[2]。文献[3]建立了一种基于分组遗传基因的算法,文献[4]建立了基于性能匹配的蚁群算法。以上算法都能在一定应用条件下表现出较好的性能，但是在OpenStack这种没有环境限制的情况下会有不稳定的性能，所以本文在构建了OpenStack私有云平台后[5]，深入研究了虚拟机创建流程，分析负责虚拟机放置的模块，分析该模块使用的虚拟机调度算法原理以及不足，提出了基于交叉装填思想的OpenStack虚拟机放置算法。

1　OpenStack虚拟机放置算法

1.1OpenStack 虚拟机创建流程

创建虚拟机的过程如图1所示，其中nova-sched-uler负责完成虚拟机调度的功能，即通过放置算法选择物理机，完成虚拟机到物理机的映射。

图1　虚拟机创建内部流程图

1.2OpenStack 放置算法

nova-scheduler中内置了2个虚拟机放置算法：

（1）随机放置算法，在物理机当前可用的CPU、内存、磁盘空间资源满足虚拟机需求时，随机选择1个物理机进行放置。该算法默认不使用，没有实用价值。

（2）过滤称重放置算法，如图2所示。

该放置算法主要分为2个步骤，首先根据物理机可用资源与虚拟机资源请求以及配置文件和系统设置的一些条件筛选出满足条件的物理机，然后对筛选出来的物理机根据剩余可用内存指标计算权重，根据权重排序，最后选择的是剩余可用内存最多物理机进行放置。

1.3OpenStack 虚拟机放置算法的不足

OpenStack云平台在默认情况键下只根据剩余可用内存大小做权重计算，也就是说物理主机拥有的剩余内存资源越多，被选中为放置的物理机的几率越大。

这种算法实现非常简单，复杂度低，很容易理解，但是这种单一根据内存来排序并决定物理机选中的方法并不适合在实际的云平台环境中使用。另外，在针对内存进行虚拟机放置时，总是选择剩余内存多的物理机，这样整体上各个物理机的内存利用率都不高。而在实际的生产环境中，需要权衡各种资源的利用率，尽可能多的提高CPU、内存、磁盘、网络带宽四种主要资源的利用率，避免大量资源的浪费。

图2　过滤称重分配过程图

2　OpenStack虚拟机交叉装填放置算法

2.1虚拟机放置的数学模型

虚拟机在物理机中的放置问题，是典型的装箱问题（Bin Packing Problem，BPP）[6]。其数学模型可以描述为：

云平台中物理机集合表示为 P=（p1，p2，…，pn），虚拟机集合表示为 V=（v1，v2，…，vM）,其中n和m表示为物理机数目和虚拟机数目。假设一个物理机共有（1，2，…，h）中资源（例如CPU、内存等），则1个物理机pi可以表示为pi=pi（si1，si2，si3，…，sih），s表示第i个物理机上资源的提供量，即剩余可用资源。同理一个虚拟机vj=可以表示为vj=（rJ1，rj2，rj3，…，rjh），r表示第j个虚拟机对资源的需求量。目标函数为云平台物理机总资源利用率最高，即所使用的物理机数目最少，表示为：

约束条件为:

其中，约束式（2）保证了虚拟机各种资源的总需求量不会超过物理机提供的对应资源总量，q是一个系统阈值，通常设置为0.9，该值是除去虚拟化的系统开销后物理机可以提供的资源比例，即物理机资源的90%能够提供给虚拟机分配；约束式（3）保证每一个虚拟机最多只能被放置到一个物理机上；约束式（4）和（5）是决策变量。

2.2基于交叉装填的虚拟机放置算法

OpenStack虚拟机放置是一个四维向量的装箱问题（四维资源：CPU、内存、磁盘空间、网络带宽）。本文通过将该四维的装箱问题转化为一维装箱问题来降低复杂度。本文采用的方法是将四维向量通过距离公式，转换为一维的欧氏距离。

距离公式为：

其中，P代表当前物理机的剩余可用资源，v代表虚拟机的请求资源。

文献[7]提出了一种解决一维装箱问题的近似算法——交叉装填算法，并证明了该算法能达到装箱问题最优的近似值3/2，同时算法的复杂度能达到非线性最优O（nlogn），因此适用于虚拟机放置问题。本文根据交叉装填算法的思想，结合物理机与虚拟机性能的欧氏距离，得出OpenStack虚拟机放置算法。算法具体流程如下：

输入：物理机集合P（具有相同的配置），虚拟机集合V。

输出：实际使用的物理机数目Pused。

①由公式（6）计算所有要创建的虚拟机与物理机的欧氏距离，将v1，v2，…，vm的按dpv大小进行非减排序，不妨设dpv≤dpv≤…dpv。（距离越小，说明虚拟机请

12m求的资源数越多，虚拟机越“大”）

②首先把排序好的虚拟机队列头部v1放入物理机p1中，将v1从队列中删除，然后尝试从队列尾部将vm放入p1。如果vm能够放入物理机p1中，则将放入物理机p1中，并将vm从队列中删除，然后 执行③；如果不能则执行④。

③从队列头部开始往后找出第一个能放置在当前物理机上pi的虚拟机vj，如果能找到，则将vj放入pi，b并将vj从队列中删除，再按照②中方法处理尾部虚拟机；如果不能找到，则执行④。

④开启新的物理机pk，然后按照②、③的方式处理，直到所有虚拟机放置完成。

⑤输出Pused。

3　仿真实验与结果分析

为了验证该基于欧氏距离交叉装填放置算法在OpenStack云计算虚拟机放置的实际应用中的效果，本文通过对算法进行仿真实验，并且与OpenStack内置的放置算法进行对比，证明了本文算法的有效性与优越性。

3.1CloudSim 云计算仿真平台

由于实验环境计算机资源有限，无法满足企业级至少几十台物理节点的生产环境，所以本文采用在CloudSim云计算仿真平台[8]上实现该算法。CloudSim是澳大利亚墨尔本大学的网格实验室和Gridbus项目推出的云计算仿真软件。它是在离散事件模拟包SimJava上开发的函数库，是一个通用、可扩展的仿真框架。这个仿真框架具有以下几个特性：（1）支持在单个主机上进行大规模云计算基础设施的仿真和实例化；（2）CloudSim的CIS（Cloud Information Service）和DataCen-terBroker实现资源发现和信息交互，是模拟调度的核心，用户自行开发的调度算法可在DataCenterBroker的方法中实现，从而实现调度算法的模拟。

3.2仿真实验结果分析

本次仿真实验设置的物理节点的为100台，每台的CPU大小为1.6GHz，内存大小为1.6GMB，磁盘空间大小为2000GB,网络带宽为500Mbps。

虚拟机共设置10种不同配置，来模拟实际环境中各种类型，这10种虚拟机配置如表1所示。

表1　虚拟机配置表

实验中，虚拟机以这10个类型为一组，实验创建虚拟机数从10台开始，每次增加10台，直到200台为止，来对比OpenStack默认的放置算法和本文得出的基于距离的交叉装填放置算法所需要开启的物理机数量。实验结果如表2，图3所示：

表2　实验结果对比

图3　实验效果

可以看出，本文提出的距离交叉装填算法比OpenStack默认的放置算法有效。在申请创建的虚拟机数量较少的时候，两种算法并没有太大的差别，但是随着创建虚拟机数量的增加，距离交叉装填算法的性能优势越来越明显，所需要的物理机数量明显小于OpenStack默认的虚拟机放置算法。说明距离交叉装填算法用于OpenStack的虚拟机放置能够提高云平台的资源利用率。以此证明了本文算法的有效性。

4　结语

本文研究了OpenStack云计算平台的虚拟机创建流程，分析了其虚拟机的放置算法，并提出了基于距离的交叉装填放置算法，并通过CloudSim仿真平台进行了实验，表明距离交叉装填算法提高了OpenStack云计算平台的资源利用率，减少了中小企业部署OpenStack云计算机平台的物理机数量，降低了成本开销，具有实际使用价值。本文的下一步研究工作重点将放在多方面考虑放置策略，在资源利用率，用户服务质量和能耗等几个方面综合权衡，能在大规模数据中心环境下对虚拟机的放置进行优化。

[1]Zhang Q,Cheng L,Boutaba R.Cloud Computing:State-of-the-Art and Research Challenges[J].Journal of Internet Services and Applications,2010,1（1）:7-18.

[2]Dorigo M,Maniezzo,Colorni A.The Ant System:Optimization by a Colony of Cooperating Agents[C].IEEE Trans.System Man Cybernet.1996（B26）:29-41

[3]Agrawal S,Bose S K,Sundarrajan S.Grouping Genetic Algorithm for Solving the Server Consolidation Problem with Conflicts[J].Gec Proceedings of the First Acm/sigevo Summit on Genetic&Evolutionary Computation,2009:1-8.

[4]杨星,马自堂,孙磊.云环境下基于改进蚁群算法的虚拟机批量部署研究[J].计算机科学,2012,39（9）:33-37.

[5]OpenStack Installation Guide for Red Hat Enterprise Linux 7,CentOS 7,and Fedora 20[EB/OL].（2014-10-16）[2015-08-04].http:// docs.openstack.org/juno/install-guide/install/yum/content/.

[6]HYEAR C,MACKEE B,GARDNER R,et al.Autonomic Virtual Machine Placement in the Data Center[J].Hewlett Packard Laboratories,Tech.Rep.HPL-2007-189,2007:2007-189.

[7]孙春玲，陈智斌，李建平.装箱问题的一种新的近似算法[J].云南大学学报:自然科学版,2004,26（5）:392-396.

[8]Calheiros R N,Ranjan R,De Rose C A F,et al.Loudsim:A Novel Framework for Modeling and Simulation of Cloud Computing Infrastructures and Services[R].GRIDS-TR-2009-1,Grid Computing and Distributed Systems Laboratory.The University of Melbourne, Australia,March 13,2009

OpenStack;Cloud Computing;Placement Algorithm;Virtual Machine Scheduling;Resource Utilization Ratio

Research on Virtual Machine Placement Algorithm Based on OpenStack

WEN Chao，HU Xiao-qin
（College of Computer Science,Sichuan University，Chengdu 610065）

1007-1423（2016）07-0003-05

10.3969/j.issn.1007-1423.2016.07.001

文超（1990-），男，四川德阳人，硕士研究生，研究方向为网络与信息安全安全胡晓勤（1977-），男，四川内江人，讲师，硕士研究生导师，研究方向为信息安全收稿日期：2016-01-19修稿日期：2016-02-20

近几年来，云计算技术飞速发展，对IT界以及人们的日常产生活带来越来越大的影响。OpenStack是当今最流行的开源IaaS云平台，研究OpenStack的虚拟机初始放置问题，指出OpenStack在虚拟机放置方面的不足，并且提出距离交叉装填算法作为OpenStack的虚拟机初始放置算法。实验结果表明，该算法比OpenStack默认的虚拟机放置算法性能更好，提高物理机资源利用率。

OpenStack；云计算；放置算法；虚拟机调度；资源利用率

In recent years,cloud computing technology is developing rapidly and it has brought more and more influence on the IT industry and people's daily life.OpenStack is one of today’s most popular open-source IaaS cloud platform,studies the virtual machine initial place-ment algorithm of OpenStack and points out the disadvantages of it,and then comes up with an distance-cross-filling algorithm as the virtual machine placement algorithm of OpenStack.Experimental results show that the proposed algorithm performs better than Open-Stack’s default algorithm,and that the proposed algorithm improves the utilization of physical machine resources.