面向成本优化的包簇机制虚拟化资源分配

王 磊，陈世平,2，卢浩洋

(1.上海理工大学 光电信息与计算机工程学院，上海 200093;2.上海理工大学 信息化办公室，上海 200093)

面向成本优化的包簇机制虚拟化资源分配

王 磊1，陈世平1,2，卢浩洋1

(1.上海理工大学 光电信息与计算机工程学院，上海 200093;2.上海理工大学 信息化办公室，上海 200093)

现阶段，以虚拟机为中心的云数据中心在资源分配的成本控制方面仍需改进。针对此问题，文中以验证基于包簇分配机制在成本控制方面要优于现有的基于虚拟机机制为目的。对分配问题所涉及的成本因素进行了优化，同时考虑在某个簇上对一个单位的资源使用一个时间槽的成本及使用成本随时间的变化,而从得到了基于包簇框架下的成本函数。采用仿真数据，通过整数规划得到一组基于包簇分配的营运成本数据,并且使其与传统的基于虚拟机分配的成本进行对比，从而验证了包簇分配机制下成本函数的可用性及有效性。

云计算；数据中心；资源分配；虚拟机；包-簇

虚拟数据中心化指通过虚拟技术[1]来对数据中心进行管理。然而数据中心的资源弹性分配特征，使得企业和组织在部署应用时能够根据实际业务需求分配虚拟化资源，从而减少资源浪费[2]。因此，在按需付费的云计算环境中部署应用时，如何在保证应用提供商和应用使用者之间的服务等级协议(Service Level Agreement，SLA)的基础上优化分配虚拟化资源，从而尽可能降低应用的资源使用成本，是目前解决资源浪费的关键途径。

与已有研究不同，本文针对基于包-簇的资源分配。并通过这种新型的分配机制提出一种以最小化资源使用成本为目标的总体成本函数，使用动态规划来得出包-簇分配机制的最优解，并将其最优解与基于虚拟机的资源分配的成本最优解进行比较，从而来解决在数据中心使用时的资源利用最大化和合理化。

1 相关研究

现在流行的数据中心资源管理方式是以虚拟机(VM)为中心，每个用户必须指明所需的虚拟机数量及每个虚拟机的资源要求[3]。

(1)可扩展性(Scalability)挑战。现有的研究工作将资源分配(虚拟机-服务器映射)视为约束优化问题来解(如Non-linear Mixed-integer Programming)[4-5]。其它工作通过一些假设将资源分配简化成多维装箱问题(Bin-Packing)[6-7],但那仍然是NP-hard。一般而言，资源分配优化可被视为计算一个最优的资源分配矩阵

(1)

(2)灵活性挑战。在一个面向虚拟机(VM-Centric)的资源管理系统中，用户需要明确指定每个虚拟机的资源要求[8-9]，有时还包括虚拟机间的流量矩阵，以对数据中心的网络性能进行优化[10-11]。而现实中的用户可能并不清楚每个虚拟机在将来的每个时刻有怎样的资源要求。如果允许资源共享，则对每一个个体虚拟机就没有固定的资源承诺，这种共享式的资源分配形式对于当下实际使用的虚拟机资源分配模型而言是根本的背离，因而，对灵活性的追求将要求现阶段进行不同于现有技术的基础性研究。

以虚拟机为中心(VM-Centric)来设计资源分配模型，使用扁平、细颗粒度的资源分配方式。这样细颗粒度的管理模型导致所要解决的计算问题规模巨大，对虚拟机固定的资源分配也不利于资源共享。

2 基于包-簇分配机制模型

为解决上述问题，本文将使用一种全新的基于包簇分配机制[12]的模型。首先介绍包和簇的概念，以对用户需求和云资源给出多级抽象的递归定义。

2.1 包的构造

定义1“包”为虚拟机或其他包的集合(注：这是个递归定义，一个大包可以是许多小包的集合，而这些小包可能是虚拟机的集合，也可能是更小包的集合)。该递归定义允许用户以一种层次结构形式组织自己的资源要求。

如图1所示，一个资源共享的虚拟机组合被模块化为需求包，而多个包又进一步被抽象成一个更高级别的包，进而由虚拟机与包构成一个层次化组织构架。灵活性将由基于包的资源管理而获得，因为包内允许资源共享。

图1 包层次结构

2.2 簇的构造

定义2“簇”为数据中心拓扑中位置相近的服务器或更低级别的簇的集合。簇所拥有的资源是其组成部分的资源之和。

图2用肥胖树(Fat-tree)[13]来说明簇的概念，图2(a)是一个肥胖树拓扑，当用簇代表每个机架上的服务器后，其拓扑结构简化为图2(b)。当将低级别簇聚合成高级别簇后，其拓扑又简化为图2(c)。需要注意的是，每一个低级别簇实际上包含了大量的服务器，而每一个更高级别簇又包含了相当数量的低级别簇。显然，簇的概念比pod更具一般性，因为簇的层次结构是可以依据包的递归层次结构来随意构造的。更重要的是，在本文中簇的意义并不在于其定义本身，而在于包簇共同使用来降低数据中心资源管理的复杂度，这是过去研究所没有的。

图2 针对不同需求构建不同的簇层次结构

具体地说，使用包和簇来将虚拟机-服务器映射问题转换成一系列小得多的包-簇映射问题：首先，将最上层的大型包映射给最上层的大型簇，每个簇应有足够的资源来支持映射的包的总需求。然后，对于每一个簇及所支持的包，并且在进一步将其下一级别的包映射到下一级别的簇，这个过程递归重复，直到虚拟机被映射到服务器。该方法将一个指数级复杂度的问题分解为一些小问题，而这些小问题每个计算规模都不大，可以逐个利用动态规划方法[14]来解决。

3 基于包-簇分配成本函数

以簇层次结构中任意一个簇ρ来描述资源分配问题，该簇具有N个子簇(或服务器)，以p为子簇标号，1≤p≤N。假设已分配给ρ的包由M个子包(或虚拟机)组成，标号为v，1≤v≤M。要解决的问题是如何最优地将这M个子包分配给ρ中的N个子簇，应该强调的是同一个算法又可以递归调用来把子包的子包映射到子簇的子簇，直至最终的虚拟机到服务器的映射。假设存在J种资源，以1,2,…,J为序。每个子包均对应一个描述所需资源总量的向量，其中每一项表示一个资源类型。每一个子簇p，1≤p≤N，也对应一个描述可资分配的资源总量的向量。

3.1 优化分配问题所涉及的变量

3.2 资源约束

每个簇p的资源使用量不能超过可用资源量。在时间t，对任何资源i而言，给定分配矩阵x，簇p上对资源i的总用量是∑v∈VRv,i[t]xv,p[t]。因此，要求

∑v∈VRv,i[t]xv,p[t]≤Ap,i[t]
1≤p≤N,1≤i≤J,1≤t≤T

(2)

1≤p≤N，1≤i≤J，1≤t≤T

3.3 营运成本

假设在某个子簇p上对一个单位的资源i使用一个时间槽的成本是ep,i[t]，包括设备折旧、管理开支、能源开支等。为了反映不同簇的异质性，允许不同簇上对每个资源的使用成本不同。同时为了反映能源价格与时间的关联，也允许使用成本随时间而变化。在时间t时，把包v分配给簇p的成本为

(3)

因而，簇p在时间t的营运总成本为

∑v∈VCv,p[t]xv,p[t]

(4)

(5)

其中，yp[t]是一个0-1变量，当且仅当存在有包被分配给簇p时，其值为1。为此，可以增加一个约束条件

yp[t]≤∑vxv,p[t],Byp[t]≥∑vxv,p[t]

(6)

其中，B为一个给定的足够大的常数。这样，yp[t]=1当且仅当存在某个v，使xv,p[t]=1。设定y为向量yp[t])，1≤p≤N，1≤t≤T。

综上所述，总体成本目标函数U(x,y)定义如下

(7)

在包-簇框架下，簇资源分配问题就是找到最优的分配矩阵来把成本目标函数U(x,y)最小化。而云资源分配问题就是依据包簇的层次结构来求解一系列的簇资源分配规划问题。

4 实验与分析

4.1 实验设置

验证基于包-簇分配机制下成本函数的可用性和合理化，所以只使用仿真数据即可。在云计算中物理主机的取值为10,15,20,25,30,35,40,45,50。并且各个物理主机中每一个资源的数量在一定的范围之内随机变化，表1给出了可用资源的单位(unit)、价格(price)以及可用范围(range)。

表1 物理机可用资源和单位价格

4.2 与基于虚拟机的成本函数对比

该组实验通过物理机的数量在10～50台之间变化，根据包簇分配过程首先根据式(3)计算出Cv,p[t],其中t∈[1,T]，接着找到Cv,p[t]的第一个和最后一个局部最小点对应的时间T1和TK。最后使t在[1～T1],[T1～TK],[TK～T]的情况下分别求解式(7)并由此求出最优解。

根据式(9)及包簇分配算法，求解出基于包簇分配机制下云数据中心资源分配营运成本，如表2所示。

表2 包簇营运分配成本表

基于包-簇分配成本函数与基于虚拟机的成本函数所需求的最小资源使用成本做对比[15]，如图3所示。

图3 资源使用成本对比

根据图3可知，当物理机数量在10～30台时，基于包簇分配与基于虚拟机分配的资源使用代价几乎相同并且趋于降低。在35台之后，基于包簇分配仍然在减少，并在45台之后呈现出稳定的趋势，而基于虚拟机的资源使用代价出现了增长的趋势，这正是因为现在云数据中心中基于虚拟机的资源分配策略是扁平化设计的，当物理机数量增多时资源使用代价将呈指数级增长。根据实验结果，对于不同的物理机数量的逐渐增加，两者的资源使用代价都逐渐减少，但随着物理机数量越来越多，包-簇框架的减少幅度更大。当物理机的数量越来越多时，基于包-簇框架资源分配机制在成本控制上要比基于虚拟机的分配机制更有效，并且成本更低。

5 结束语

对基于虚拟机机制的数据中心的管理问题进行了分析，并就此问题提出了新的包簇框架的分配机制，将虚拟机机制中需要将所有虚拟机映射到服务器转换为包簇机制中的将用户所需的包资源映射到簇上。在复杂的云系统中计算、存储、带宽等资源限制条件下，满足所有用户要求，并对包簇分配机制进行分析，从中提取出基于包簇分配机制的成本函数。实验验证了基于包簇分配机制在成本控制方面要优于现有的虚拟机机制。

[1] Ian Foster,Zhao Yong,Ioan Raicu,et al.Cloud computing and grid computing 360-degree compared[C].Beijing:IEEE International Conference,2008.

[2] Durao F,Carvalho J F S,Fonseka A,et al.A systematic review on cloud computing [J].The Journal of Supercomputing,2014,68(3):1321-1346.

[3] Rodrigues H,Santos J R,Turner Y,et al. Gatekeeper: supporting bandwidth guarantees for multi-tenant datacenter networks[C].Berlin:Proceeding of ACM SIGCOMM,2011.

[4] 李菡薏.云计算环境下任务调度算法的研究[J].电子科技,2015,28(11):43-47.

[5] Xu J,Fortes J.Optimization in autonomic data center resource and performance management[R].Florida,USA:University of Florida,2012.

[6] Chen M,Zhang H,Su Y Y,et al.Effective VM sizing in virtualized data centers[C].Macro:Proceeding of ACM SIGCOMM,2011.

[7] Ajiro Y,Tanaka A.Improving packing algorithms for server consolidation[C]. MA,USA:Proceeding of Computer Measurement Group Conference,2007.

[8] Xu J,Fortes J A B.Multi-objective virtual machine placement in virtualized data center environments[C].Beijing:IEEE International Conference,2010.

[9] Mehta S,Neogi A.Recon: a tool to recommend dynamic server consolidation in multicluster data centers[C].Beijing:IEEE International Conference,2008.

[10] Guo C,Lu G,Wang H J,et al.Secondnet: a data center network virtualization architecture with bandwidth guarantees[C].Nanjing:Proceeding of ACM SIGCOMM,2010.

[11] Meng X,Pappas V,Zhang L.Improving the scalability of data center networks with trafficaware virtual machine placement[C].Beijing:IEEE International Conference,2010.

[12] 卢浩洋,陈世平.基于包簇映射的云计算资源分配框架[J].计算机应用,2016,36(10):2704-2709.

[13] Al-Fares M,Loukissas A,Vahdat A.A scalable,commodity data center network architecture[C].Paris:Proceeding of ACM SIGCOMM,2008.

[14] 宛楠,张义.动态规划算法分析[J].长江大学学报,2013,10(7):34-38.

[15] 张斌,朱孟笑,赵秀涛,等.面向成本优化的SBS虚拟化资源分配[J].东北大学学报,2015,36(10):929-932.

Cost Oriented Virtualized Resource Optimization Allocation for Package-Cluster

WANG Lei1，CHEN Shiping1，2，LU Haoyang1

(1.School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China；2.Network and Information Center Office,University of Shanghai for Science and Technology,Shanghai 200093,China)

At this stage,the virtual machine as the center of the cloud data center in the cost control of resource allocation still need to improve. In order to solve this problem,this paper is based on the cluster allocation mechanism in order to better control the cost of the existing virtual machine mechanism for the purpose of. The cost factors involved in the allocation problem are optimized,taking into account the time and cost of using a time slot for a unit of resources on a cluster. The cost function based on the clustering framework is obtained. The simulation data are used to obtain a set of operating cost data based on cluster assignment by integer programming. Compared with the traditional cost allocation based on virtual machine,the availability and effectiveness of the cost function under the cluster allocation mechanism are verified.

cloud computing; data center; resource allocation; VM; package-cluster

TP391

A

1007-7820(2017)11-085-05

2017- 01- 05

国家自然科学基金(61472256)；上海市教委科研创新重点项目(12zz137)；上海市一流学科建设项目(S1201YLXK)。

王磊(1991-)，男，硕士研究生。研究方向：云计算。陈世平(1964-)，男，博士，教授，博士生导师。研究方向：云计算,分布式计算。卢浩洋(1991-)，男，硕士研究生。研究方向：云计算。

10.16180/j.cnki.issn1007-7820.2017.11.023