基于架构负载感知的虚拟机聚簇部署算法

摘要：

针对云计算中虚拟机部署问题，提出了一种基于架构负载感知的虚拟机聚簇部署算法。首先计算云数据中心各层架构的负载，并在架构内对主机进行聚簇。虚拟机进行部署时，先按照相应的规则进行虚拟机间的聚簇，并优先选择负载较低的架构进行部署，架构选择后，进行虚拟机簇与主机簇的匹配以选择最优的主机簇进行部署。最后通过CloudSim进行仿真验证，将其与贪婪算法及基于架构负载感知的基本部署算法进行比较，证明了算法在部署时间方面有明显的优越性，并提高了网络资源的利用率。

关键词：

云计算；虚拟机；架构负载感知；聚簇；可获得性限制

0引言

计算机软件与硬件技术的飞速发展导致了计算模型的不断演化。继分布式计算、并行计算和网格计算等模型之后，计算机工业界提出了云计算模型[1]。云计算通过互联网将超大规模的计算存储资源整合起来，形成一个虚拟的计算资源池，并以服务的形式按需提供给用户。

虚拟化技术[2]是云计算的关键技术，它通过将一台物理服务器分割为若干个相互隔离的虚拟服务器，实现对于物理资源的动态分割，提高系统的资源利用率，降低管理难度，同时屏蔽了底层硬件资源的异构性。虚拟化技术的应用使得云计算服务部署从复杂的构建服务器集群，转换为更为快捷简便的对于虚拟机的部署。随着虚拟化成为了云计算的核心技术，虚拟机部署问题也成为了云计算的一个关键问题。

随着云计算的日益成熟，虚拟机的部署也从单个虚拟机的部署转变成虚拟机簇的部署，虚拟机簇即为属于某个用户应用程序的具有通信需求和部署限制的多个虚拟机的集合。为了提高服务质量，云基础设施提供者需要有效地部署用户的虚拟机簇，使之既能满足可靠性要求，又具有较高的应用性能，而且虚拟机的部署时间应该合理。这样的部署为NPhard[3]问题，目前还没有多项式最优解算法。

研究者大多采用启发式方法进行全局优化搜索，解决虚拟机部署下的约束满足问题[4-5]。文献[6]提出了基于图分解的启发式部署算法，但是只考虑了在一台主机上部署一个虚拟机的情况；文献[7]提出了一种基于聚簇的启发式算法，但是只考虑了服务器无负载时的情况；文献[8]提出了一种分解解决方案，某些相互连接的物理资源首先被确认为部署的目标机器，而不是在整个系统中进行搜索，但是该方案只考虑了网络因素；文献[9]研究了确定虚拟机部署的最优簇问题；文献[10]则进行了实际的测试实施。

本文主要解决云计算数据中心中虚拟机簇的部署问题，对物理主机和虚拟机进行聚簇，提高部署效率和对资源的利用率，同时考虑用户的可获得性要求。

1相关研究

1.1虚拟机簇

虚拟机簇是由多个具有紧密联系的虚拟机组成的集合，它通常构成某个应用程序的部署单元。在云计算环境下，应用程序提供者通常在租用的物理资源中部署某些虚拟机向终端用户提供服务，这些虚拟机就组成了一个虚拟机簇。为了达到用户服务质量（Quality of Service，QoS）[11]，应满足虚拟机簇的部署要求，如虚拟机的资源需求、虚拟机间的带宽需求及虚拟机的可获得性要求等。

考虑如图1所示的虚拟机簇P，簇P为一个通用的3层交互模式的虚拟机簇，每层分别包含{2，3，2}个虚拟机，第1层和第2层虚拟机之间的带宽需求为1，而第2层与第3层虚拟机之间的带宽需求为2。

聚簇算法具体步骤如下：

1）获取排序后的主机列表；

2）取出主机列表中的第一台主机形成一个簇；

3）判断其是否为主机列表中的最后一台主机，若是则跳转到7）；

4）依次取出主机列表中的剩余主机，计算其与簇中主机的chance，若chance≤thresholdPM，主机加入到簇中；

5）更新主机列表，更新后的列表仍为降序排列；

6）判断更新后的主机列表是否只有一台主机，若是则自成一簇，否则跳转到2）；

7）退出循环，输出主机簇，而且各主机簇已按照负载和网络因素降序排列。

匹配部署算法的具体步骤如下：

1）获取排序后的主机簇列表；

2）依次取主机簇列表中的主机簇；

3）对主机簇中的主机按照负载高低进行降序排列；

4）将虚拟机簇中的虚拟机按照对资源的需求进行降序排列；

5）依次取出排序后虚拟机簇中的虚拟机，若无虚拟机可取，则转到步骤8）；

6）依次取出排序后主机簇中的主机，若无主机可取，则清空部署列表，转到步骤2）；

7）将虚拟机与主机依次进行匹配，确定主机及主机间的链路带宽是否满足虚拟机的性能需求，若满足则将其加入部署列表，并更新主机资源和虚拟簇，转到步骤3），若不满足则转到步骤6）；

8）退出循环，输出部署列表。

4结语

本文使用基于架构负载感知的虚拟机聚簇部署算法进行虚拟机批量部署，虚拟机进行部署时，将虚拟机进行聚簇，将其与主机簇进行匹配。本文算法同时考虑了系统的负载均衡和网络特性因素，并通过Cloudsim进行仿真验证，将其与贪婪算法及基于架构负载感知的基本部署算法进行比较，证明了本算法的优势。

参考文献：

[1]

ARMBURST M， FOX A， GRIFFITH R，et al. A view of cloud computing[J]. Communications of the ACM， 2010， 53（4）：50-58.

[2]

董耀祖，周正伟.基于X86架构的系统虚拟化技术与应用[J].计算机工程，2006， 32（13）：71-73.

[3]

BENGOETXEA E. Inexact graph matching using estimation distribution algorithm[D]. Pairs：Ecole Nationale Superieure des Telecommunications，2003.

[4]

LI B， LI JX， HUANG JP， et al. EnaCloud： an energysaving application live placement approach for cloud computing environments[C]// 2009 IEEE International Conference on Cloud Computing. Piscataway： IEEE， 2009：17-24.

[5]

GUPTA R， BOSE S.K， SUNDARRAJAN S， et al. A two stage heuristic algorithm for solving the server consolidation problem with itemitem and binitem incompatibility constraints[C]// SCC08：Proceedings of the 2008 IEEE International Conference on Services Computing. Piscataway： IEEE， 2008： 39-46.

[6]

MENG X， PAPPAS V， ZHANG L.Improving the scalability of data center networks with trafficaware virtual machine placement[C]// 2010 Proceedings of IEEE INFOCOM. Piscataway： IEEE， 2010：1-9.

[7]

JAYASINGHE D， PU C， EILAM T， et al.Improving performance and availability of services hosted on IaaS clouds with structural constraintaware virtual machine placement[C]// 2011 IEEE International Conference on Services Computing. Piscataway： IEEE， 2011：72-79.

[8]

ZHU Y， AMMAR M. Algorithms for assigning substrate network resources to virtual network components[C]// The 25th IEEE International Conference on Computer Communications. Piscataway： IEEE， 2006： 1-12.

[9]

MACROPOL K，SINGH A. Scalable discovery of best clusters on large graphs[EB/OL].[2012-10-01]. http：///pvldb/vldb2010/papers/R62.pdf.

[10]

RICCI R， ALFELD C， LEPREAU J. A solver for the network testbed mapping problem[J]. SIGCOMM Computer Communications Review， 2003，33（2）：65-81.

[11]

NATHUJI R， KANSAL A. Qclouds： Managing performance interference effects for QoSaware clouds[C]// Proceedings of the 5th European conference on Computer Systems. New York： ACM， 2010：237-250.

[12]

GRAEPEL T. Statistical physics of clustering algorithms，Technical Report 171822[R]. Kln： Universitt zu Kln， Institut für theoretische Physic， 1998.

[13]

RODRIGO N. CALHEIROS， RAJIV RANJAN， et al.CloudSim： A novel framework for modeling and simulation of cloud computing infrastructures and services， GRIDSTR20091[R]. Melbourne， Australia： The University of Melbourne， Grid Computing and Distributed Systems Laboratory， 2009.