王 准， 苏顺开

(1.广州工商学院 计算机科学与工程系，广东 广州 510850;2.中山大学 现代教育技术研究所，广东 广州 510275)

多租户云计算中基于ILP模型的虚拟机放置策略

王 准1*， 苏顺开2

(1.广州工商学院 计算机科学与工程系，广东 广州 510850;2.中山大学 现代教育技术研究所，广东 广州 510275)

针对云计算中多个租户租用计算资源时，分布式数据中心中虚拟机(VM)的优化放置问题，提出一种基于整数线性规划(ILP)模型的VM放置策略.首先，以最小化数据中心之间的通信量为目标，在考虑VM位置和数据中心容量等约束下，构建一个ILP优化模型.然后，提出一种变量聚合方法来简化ILP模型，减少变量数目，提高计算效率.最后，通过求解简化ILP模型来获得VM的最优放置方案.实验结果表明，该方案能有效降低数据中心间的数据通信量，从而降低了通信成本，同时具有较低的计算时间.

云计算；多租户；虚拟机放置；整数线性规划模型；最小化通信量

在基于基础设施即服务(Infrastructure as a Service, IaaS)的云计算系统中，租户可根据自己的需求从云供应商租用相应的资源[1].云供应商以虚拟机(Virtual Machine, VM)的形式为租户提供服务，每一个VM代表一种特定功能的应用程序[2].当大量租户同时租用大量VM时，如何在分布式地理位置的数据中心(Data Center, DC)中合理放置VM成为一个难题.VM放置策略需要根据用户需求放置VM，在保证服务质量(Quality of Service, QoS)的同时，还要降低系统成本[3].其中，VM放置策略的优劣对数据中心间的通信成本影响很大.另外，为了避免较高的传输延迟，还需要考虑数据中心的地理位置与邻近用户的距离[4].目前，学者也提出了一些VM放置策略.例如，[5]提出了基于启发式算法的网络感知VM部署方法，以满足VM和硬件的需求.[6]考虑了DC成本的最小化问题，提出了一种基于聚类方法的优化算法.然而，现有方法大多是针对单个DC中的VM部署问题，没有考虑到多个分布式DC场景.在分布式DC中，当多个租户租用多个VM时，必然存在一个租户租用的VM分布在不同的DC上.那么，DC间则需要进行远距离通信，其影响着整个系统的通信成本和服务延迟[7].因此，需要一种适用于多租户分布式DC场景的VM放置策略，最小化DC间的通信量，以此节约成本，并提高服务响应性能.为此，本文提出一种基于整数线性规划(Integer Linear Program, ILP)模型[8]的虚拟机放置策略.以最小化DC间通信量为目标，在考虑多种约束下构建一种简化的ILP模型，缩小问题规模.该模型可在不同的用户租用需求和VM数量下，求解VM的最优放置方案.实验结果表明，本文简化ILP模型能够达到与经典ILP模型的同等求解能力，同时大大降低了计算复杂度，能够很好地应用于多租户云计算系统中的VM放置优化中.

1 问题描述

在多租户分布式DC的云计算系统中，DC处于不同的地理位置.租户根据需求可以租用1个或多个不同类型的VM，这些VM分布在各DC中.当租户租用多个VM执行其任务时，各VM之间可能需要通信，如果这些VM分布在不同的DC中，那么DC之间则需要进行通信，从而产生通信成本.图1显示了多租户分布式DC的系统架构，其中租户1租用了VM1、VM3、VM4和VM7，图中的虚线表示VM之间的通信，虚线上的数值表示通信量.如果这些VM分布于同一个DC中，那么DC间不要进行通信，如果分布于不同的DC中，则会产生相应的通信量.在多租户且每个租户可以租用多个VM情况下，如何优化放置各种类型的VM到各DC中，实现DC间总通信量的最小化，是一个NP困难问题.分布式DC上VM部署问题类似于网络架构中的Hub位置优化问题，目的是对VM部署进行优化，以减少分布式DC间的数据交换量，从而减少骨干网的总流量和时间延迟.本文设定DC作为中间节点，用来传递VM对之间产生的通信信息.其中，DC数量远少于VM数量.这些有助于构建适用于本文场景的有效模型，并减少了变量数.每个VM都是一个特定的应用程序，具有固定的硬件配置(CPU、内存和存储量)[9].另外，每个VM都具有位置约束，VM可以分配给相邻的两个DC，但同一时刻仅能与其中一个进行有效关联.这个约束确保了在相近终端用户中部署VM，以此保障服务性能并减少延迟时间.

2 基于ILP的优化模型

VM的部署可表示为一个完全图G=(N,E)，其中N为节点集合(由DC、VM构成)，E为边的集合(边表示通信链路).本文通过完全图G来预估DC对之间的通信量.VM通过虚拟链路与DC互联，通过流量矩阵预测VM对之间的通信量.

本节将分布式DC中VM部署问题公式化为一个整数线性规划(ILP)模型，以此求解不同DC中VM的最优部署方案，最小化DC间的数据流量.同时，对传统ILP模型进行改进，提出一种基于变量聚合的简化模型，以此减少模型中的变量数，提高计算效率.本文模型中各变量如表1所示.

表1 本文模型中符号及其含义

2.1 经典ILP模型(ILP1)

首先，本文通过传统方式构建经典ILP模型，用到的决策变量如下：

定义Oi为VMi产生的总流量：

(1)

那么，经典线性规划模型(ILP1)可表述如下：

(2)

约束于：

(3)

(4)

(5)

(6)

(7)

(8)

上述ILP模型可用于解决大规模云计算系统中分布式DC上的最优VM部署问题，但计算该最优问题所需的时间太长[10]，影响了算法的实时性，也有可能导致计算机内存不足.为此，本文对其进行改进，提出一种聚合变量的方法来减少模型中的变量数，以此减少算法的计算时间.

2.2 基于变量聚合的简化ILP模型(ILP2)

本文通过变量聚合操作，将上文所述经典ILP1模型转变为另一等价模型ILP2，减少变量数量并提高效率.ILP2模型中的决策变量为：

1) 第一个决策变量为由VMi生成并发送到DCh的总流量.

(9)

2) 第二个决策变量为由所有VM生成并发送到骨干网的总流量.

(10)

(11)

约束于：

(12)

新目标函数(11)用于最大限度地减少骨干网流量.在流量约束(12)中，利用新决策变量(9)和(10)替换了ILP1模型中的决策变量.其他约束与ILP1模型中的约束相同.

3 实验及分析

3.1 实验设置

通过仿真实验来验证本文模型的有效性.仿真中构建了不同规模的实例，用以测量程序的执行时间和骨干网流量.所有实验都在配备Intel 酷睿i5 CPU、3.3 GHz主频、8G内存的PC机上执行.采用IBM公司的CPLEX 12.5软件[11]来构建并求解ILP模型，用完全图表示网络拓扑结构.

不同的VM具有不同的硬件配置，文中选择了三类(小型、中型和大型) VM实例.所有的DC都具有相同的硬件设施，每个DC有50个机架，每个机架可部署30个服务器，每个服务器有8个内核、16 GB内存，每个服务器可构建成1个或多个VM.本文以流量矩阵形式表示属于同一租户租用的多个VM之间的通信量，仿真中随机生成流量矩阵，流量值介于0至1 Gb/s之间.

3.2 实验结果

首先，研究了在多租户情况下，不同单租户租用量对ILP模型性能和计算时间的影响.仿真实验中，设置DC数量为6，随机生成20个租户租用申请，每个租户同时租用的VM数量(即单租户租用量)为10～100个.表2给出了当V=2 000时，不同单个租户租用量情况下，ILP1模型与ILP2模型的性能比较.其中，用S表示由CPLEX计算得到的最优VM部署方案下的DC间总通信量，单位为Gb/s.T表示模型求解的计算时间，单位为s.C表示单租户租用量.

表2 ILP1和ILP2模型的性能比较

由表2可以看出，随着单租户租用量的增加，DC间的通信量也增加，但ILP1和ILP2都获得了类似的最优解，这说明本文精简的ILP2模型能够获得与经典ILP1模型同样的求解能力.另外，随着单租户租用量的增加，模型的计算时间也随之增加，但本文ILP2模型的计算时间远低于ILP1模型，且较为稳定.这是因为本文ILP2模型将变量数减少了一个量级，有效减少了计算时间.然后，研究了不同单租户租用量和不同VM数量对本文ILP2模型性能和计算时间的影响.设定DC数量为6，VM数量为1 000、2 000和4 000，单租户租用量为10～100个VM.本文ILP2模型的计算时间曲线如图2(a)所示，最优解值的曲线如图2(b)所示.由图2可知，在相同单租户租用量下，随着网络VM数量的增加，计算时间增加，流量也明显增加.同样，在相同VM数量下，随着单租户租用量的增加，计算时间和最优解值也有所增加.另外，在VM数量为1 000和2 000时，不同的单租户租用量对计算时间的影响不大.但当VM数量为4 000时，计算时间会随着单租户租用量的增加而明显增加.这是因为，在VM数量较小时，ILP2模型中变量数也较小，租用量增加对其影响不是很大.而当VM数量较大时，则影响会逐步增加.

本文针对多租户分布式DC场景的云计算系统，提出一种基于ILP模型的VM放置策略.根据用户的需求和相关约束，将VM放置到各个DC中，以此实现最小化主干网的通信量，提高用户任务的响应时间.另外，本文对传统ILP模型进行了改进，在保证求解能力的情况下简化了计算过程，减少了参数数量，大大提高了计算效率.实验结果证明了本文方案在计算时间和求解能力方面的高效性，在VM放置领域具有较高的实用性.

[1] 李强, 郝沁汾, 肖利民,等. 云计算中虚拟机放置的自适应管理与多目标优化[J]. 计算机学报, 2011, 34(12): 2253-2264.

[2] GAO Y, GUAN H, QI Z, et al. A multi-objective ant colony system algorithm for virtual machine placement in cloud computing[J]. Journal of Computer & System Sciences, 2013, 79(8): 1230-1242.

[3] TANG Z, MO Y, LI K, et al. Dynamic forecast scheduling algorithm for virtual machine placement in cloud computing environment[J]. Journal of Supercomputing, 2014, 70(3): 1279-1296.

[4] 刘丹, 隋欣, 李莉. 基于云计算的虚拟机放置节能优化算法[J]. 长春理工大学学报:自然科学版, 2015, 38(6): 150-153.

[5] BIRAN O, CORRADI A, FANELLI M, et al. A stable network-aware VM placement for cloud systems[C]// International Symposium on Cluster, Cloud and Grid Computing.Piscataway, NJ: IEEE, 2012: 498-506.

[6] ZHANG B, QIAN Z, HUANG W, et al. Minimizing communication traffic in data centers with power-aware VM placement[C]// Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing.Piscataway, NJ: IEEE, 2012: 280-285.

[7] GOUDARZI H, PEDRAM M. Geographical load balancing for online service applications in distributed datacenters[C]// IEEE Sixth International Conference on Cloud Computing. Piscataway, NJ: IEEE, 2013.

[8] 宋俊锋. 基于 MILP 的云计算数据中心扩张策略优化模型[J]. 湘潭大学自然科学学报, 2015, 37(4): 105-110.

[9] 黄纬, 温志萍, 程初. 云计算中基于K-均值聚类的虚拟机调度算法研究[J]. 南京理工大学学报, 2013,37(6): 807-812.

[10] REZVANI M, AKBARI M K, JAVADI B. Resource allocation in cloud computing environments based on integer linear programming[J]. Computer Journal, 2014, 58(2): 300-314.

[11] ZUO L, ZHANG X, WU C, et al. Unit commitment for a compressor station by mixed integer linear programming[J]. Journal of Natural Gas Science & Engineering, 2016, 30(3): 338-342.

责任编辑：龙顺潮

Virtual Machine Placement Strategy Based on ILP Model in Multitenant Cloud Computing Environment

WANGZhun1*,SUShun-kai2

(1.Department of Computer Science and Engineering,Guangzhou College of Technology and Business, Guangzhou 510850; 2.Institute of Modern Educational Technology, Sun Yat-Sen University, Guangzhou 510275 China)

For the issue that the placement optimization of virtual machine (VM) in distributed data centers when multiple tenants lease computing resources，a VM placement strategy based on integer linear programming (ILP) model is proposed. Firstly, to minimize the traffic between data center as the goal, a ILP optimization model is constructed by considering the constraints of VM location and data center capacity. Then, a variable aggregation method is proposed to simplify the ILP model, to reduce the number of variables, and improve the computational efficiency. Finally, the optimal placement scheme of VM is obtained by solving the simplified ILP model. Experimental results show that the proposed scheme can effectively reduce the amount of data communication between DC, which can reduce the communication cost, and has lower computation time.

cloud computing; multitenant; virtual machine placement; integer linear programming model; minimize the traffic

2016-03-14

广东省青年创新人才类项目(2015KQNCX196)；2016年广东省高等教育学会高职高专云计算与大数据专业委员会课题(GDYJSKT16-06)

王准(1983—)，男，湖南 长沙人，讲师.E-mail:wangzhungzgs@126.com

TP312

A

1000-5900(2016)04-0071-05