一种面向云服务提供商的资源分配机制

殷 波 王 颖 邱雪松 孟洛明



一种面向云服务提供商的资源分配机制

殷 波*王 颖 邱雪松 孟洛明

(北京邮电大学网络与交换技术国家重点实验室 北京 100876)

针对用户、服务提供商(SP)和基础设施提供商三者之间的市场行为所带来的收益问题，该文面向服务提供商提出了一种两阶段多虚拟机资源分配机制。首先，建立能力规划模型并引入粒子群算法，决策出服务提供商收益最大化的资源购买方案。然后，提出一种优化用户满意度的服务提供策略，优化了服务提供商的长期收益。最后仿真实验结果表明，该方法有效提高了服务提供商的收益，并取得了较好的用户满意度。

云计算；资源提供；用户满意度；收益优化

1 引言

随着云计算的发展，越来越多的服务提供商(Service Providers, SP)为了节省前期基础设施投入，逐步将服务部署到基础设施提供商(IP)所提供的云环境中。面向云服务提供商的资源分配问题[1]，主要包括两个方面：(1)服务提供商-基础设施提供商(SP-IP)之间的虚拟机提供：SP估计自己的需求量，向IP购买虚拟机，以花费的成本最小为目标，制定虚拟机实例的购买方案；(2)服务提供商-用户(SP-User)之间的服务提供：SP根据用户请求的特点，为请求提供虚拟机，以满足用户需求，以收益最大化为目标，制定虚拟机实例的提供方案。

目前针对SP的资源分配问题，文献[2,3]通过建立合理的定价机制，对SP的应用服务定价，实现SP收益优化。文献[2]通过建立成本分析模型，来降低资源分配的总成本，但该文献的成本分析模型并未充分考虑用户偏好的因素，因此对用户满意度的度量不准确。文献[3]与文献[2]类似，使用进程共享机制设计了一种定价模型，通过应用之间的相关性分析，设计了两种收益驱动的调度算法，但忽略了用户满意度对调度策略的影响。文献[4]通过预测负载的动态特性来解决SP-User以及SP-IP的资源分配问题，提出一种新的收益模型来描述SP在特定服务级别协议(SLA)下的收入，并采用了一种收益驱动的启发式算法来实现SP的收益最大化。但文献[4]中的SLA同样不能充分反映用户偏好，不能有效描述用户满意度。为保证高服务质量，文献[5]设计了基于响应时间的收益模型，通过增加队列响应时间来增加或者降低收益。文献[6,7]提出了基于SP效用函数的服务提供策略，关注用户效用和SP收益的折中来增加SP收益。文献[8]提出了一种基于SLA的服务提供方法，采用启发式算法来获取近似最优解。还有研究通过将多服务系统的服务请求看作M/M/m队列模型[9]，或设计两阶段的多虚拟机规划模型[10]，来解决SP收益优化的资源分配问题。但该方法并未进行SP-IP的虚拟机提供，缺乏对资源提供集合的预判断。上述文献均基于单一虚拟机类型的资源分配，未考虑IP资源类型的多样性。

为此，本文提出一种用户满意度和SP收益折中的两阶段多虚拟机资源提供机制，该机制首先在虚拟机提供阶段，对按需市场和现货市场进行能力规划，制定出满足需求的虚拟机提供方案。随后在服务提供阶段，建立包含用户出价和请求响应时间的用户效用函数，来描述用户对SP服务满意度，并设计用户满意度优化的调度算法，实现SP收益优化基础上用户满意度的提高。

2 SP的虚拟机提供

2.1 问题模型

目前IP提供虚拟资源的方式主要分为3种：按需市场、预约市场和现货市场。按需市场中的资源按小时收费，SP根据应用需求随时增加或减少资源购买数量。预约市场是在使用虚拟资源之前，SP与IP签订合同预定一定数量的资源，并支付定金。现货市场是IP回收SP预约的多余闲置资源重新进行拍卖，其它SP出价高者得到资源使用权，现货实例价格最低，但存在IP可以随时回收现货实例的风险。由于预约市场需要长期预约，本文在SP-IP的虚拟机提供阶段，对实时动态变化的工作负载仅针对按需和现货市场制定资源分配方案。

图1 云环境角色关系图

2.2 SP虚拟机提供模型及算法

通过上述的问题描述，建立虚拟机提供阶段SP收益优化的目标函数为

粒子群优化(PSO)算法首先生成具有位置和速度参数的一群粒子，更新公式如式(4)，式(5):

本文对粒子群优化算法进行了改进，重定义了算法中粒子的位置与速度，根据粒子在迭代过程中适应度值的变化，动态调整粒子速度更新的权重，以此提高粒子群算法的收敛速度。粒子重定义为

基于PSO的虚拟机提供算法(PSOVP)的步骤为：

3 SP的服务提供

3.1 用户效用函数

现有的服务提供策略将用户效用与请求响应时间建立关系，作为用户满意度的评价指标。此外，用户购买应用服务所支付的成本也是影响用户满意度的一个重要方面。本文基于经济学中的效用理论，建立请求响应时间和服务成本的用户效用函数为

3.2 用户满意度优化算法

图2 用户效用的无差异曲线

式(10)可化简为

因此，SP执行用户请求所获得总收益的计算公式为

本文设计了一种服务提供算法(SPAP)对上述问题模型进行求解。算法基于贪婪思想，为不同的用户请求提供合理的虚拟机映射方案，一方面保证SP的收益，另一方面保障用户的满意度。服务提供算法(SPAP)的具体步骤如下：

输出：虚拟机分配方案

4 SP资源分配框架

为部署上述虚拟机提供和服务提供方法，本文提出了一种SP资源分配框架，如图3所示。资源监测模块用来采集IP的实例信息，包括可用的虚拟机实例的类型和价格。用户信息采集模块用来获取用户请求、偏好参数等信息。规划分析模块由虚拟机提供模块和服务提供模块组成，监测模块采集到的数据传递给规划分析模块后，虚拟机提供模块针对用户的能力需求以及可用的虚拟机资源类型，制定虚拟机提供方案，对应于PSOVP算法。服务提供模块对每个用户请求进行用户满意度优化的请求调度，制定将请求分配到虚拟机实例的分配方案，对应于SPAP算法。决策执行模块根据规划分析模块制定的资源分配策略执行IP的虚拟机实例的购买或租用操作。

图3 SP自主资源分配框架

5 实验验证

5.1 仿真环境

根据上述模型，本文基于Visual Studio2005设计了实验的仿真模拟环境。本文所提算法作为SP决策模块的主体调度，将用户请求和实例数据作为输入，而将购买/分配方案作为输出。

本文参照亚马逊的实例类型和价格作为实验数据。采用国内某互联网公司一段时间内的任务量作为输入数据。表1为亚马逊EC2在US East (N. Virginia)按需市场的实例类型和价格。实验采用的硬件配置是Xeon E5620(2.4 G)4核8线程的处理器，30 GB DDR的内存，SAS 1 TB RAID5硬盘，物理服务器使用Windows Server 2008R2 SP1操作系统。实验平台为虚拟机分配的相应参数与亚马逊EC2实例配置相同。为测定亚马逊EC2各类型实例的能力差异，将一段1024-frame 1080p的视频加密任务在4种实例上运行，运行时间如表1所示。表2中为本实验用到的参数值。表3~表6中统计的值为近两年内现货市场采用相应价格区间的概率。实验从SP收益、单位收益、虚拟机实例利用率等方面对算法进行了仿真实验，并与文献[7]中的算法进行了对比。

表1亚马逊EC2按需市场的实例价格及基准程序测试的能力值

实例类型Windows价格(h)平均时间(s)方差(s) 小型实例(Small)0.115506.13.2 中型实例(Medium)0.230387.42.1 大型实例(Large)0.460113.51.7 超大型实例(Extra Large)0.920 40.61.3

表2实验中用到的参数值

参数取值 粒子群迭代次数100 用户偏好比7.0, 4.0, 1.0, 0.5 现货市场购买比例0.8 按需市场购买比例0.2

5.2结果分析

图4所示是国内某搜索企业一年内平均每天随时间到达的请求量，本文对原始数据进行了初步的归一化处理，实验将该数据作为所提方法的输入数据。实验的评价指标如下：

SP总收益 图5为不同算法获得的SP总收益对比图，从图5可得，随着任务量的增加，SP获得的收益逐渐增高，SP收益较之对比方法[7]提高了近20%。主要原因在于，本文方法针对一段时间内的请求量进行资源规划，首先PSOVP算法以节省成本为目标使得SP在购买虚拟机过程中的支出更加合理。而在SPAP算法中，则进一步考虑了用户满意度，从长期来说，用户满意度的提升会对SP的总体收益带来正面影响。PSOVP算法以成本最小化为目标进行多类型虚拟机资源分配是保证SP能够获得更多收益的主要原因。

表3现货市场小型实例的价格

价格区间[0, 0.038)[0.038, 0.040)[0.040, 0.042)[0.042, ) 2011年的概率(%)0.0349.6041.269.11 2012年的概率(%)0.0358.7440.211.36

表4现货市场中型实例的价格

价格区间[0, 0.225)[0.225, 0.240)[0.240, 0.400)[0.400, ) 2011年的概率(%)0.0146.8548.264.88 2012年的概率(%)0.0257.6440.212.37

表5 现货市场大型实例的价格

价格区间[0,0.370)[0.370,0.460)[0.460,0.660)[0.042, ) 2011年的概率(%)6.1751.7139.682.44 2012年的概率(%)5.2847.1146.970.64

表6现货市场超大型实例的价格

价格区间[0, 0.50)[0.50, 0.79)[0.79, 0.90)[0.90, ) 2011年的概率(%)0.7539.8542.1617.24 2012年的概率(%)0.1232.4650.2117.21

6 总结

本文针对SP资源分配过程中的收益优化问题，提出了一个两阶段的多虚拟机资源分配机制。首先针对按需市场和现货市场对应用需求进行能力规划，决策出满足服务提供商收益优化的资源提供方案。之后使用经济学中的效用理论，建立与请求响应时间和用户出价相关的用户效用模型，用来度量用户满意度。并提出了一种用户满意度与收益优化折中服务提供算法，该方法有效提高了用户满意度，有利于实现服务提供商的长期收益优化。最后，实验利用了亚马逊EC2的实例数据和国内某搜索企业的请求数据进行仿真。仿真结果表明，所提方法有效提高了SP收益，并实现了用户满意度的优化。

图4 任务量随时间分布图

图5 SP总收益对比图

图6 单位收益示意图

图7 虚拟机实例利用率示意图

图8 用户偏好和单位收益的关系图

[1] Chen Wei, Qiao Xiao-qiang, and Wei Jun. A profit-aware virtual machine deployment optimization framework for cloud platform providers[C]. 2012 IEEE 5th International Conference on Cloud Computing (CLOUD), Honolulu, 2012: 17-24.

[2] Thanakornworakij T, Nassar R, Leangsuksun C B,.. An economic model for maximizing profit of a cloud service provider[C]. 2012 Seventh International Conference on Availability, Reliability and Security (ARES),Prague, 2012: 274-279.

[3] Lee Y C, Wang C, Zomaya A Y,.. Profit-driven service request scheduling in clouds[C]. 2010 10th IEEE/ACM International Conference on Cloud and Grid Computing (CCGrid),Melbourne, 2010: 15-24.

[4] Goudarzi H and Pedram M. Maximizing profit in cloud computing system via resource allocation[C]. 2011 31st International Conference on Distributed Computing Systems Workshops (ICDCSW), Minneapolis, 2011: 1-6.

[5] Li J, Wang Q Y, Deepal J,.. Profit-based experimental analysis of IaaS cloud performance: impact of software resource allocation[C]. 2012 IEEE Ninth International Conference on Services Computing (SCC), Honolulu, 2012: 344-351.

[6] Mazzucco M, Vasar M, and Dumas M. Squeezing out the cloud via profit-maximizing resource allocation policies[C]. 2012 IEEE 20th International Symposium on Modeling, Analysis & Simulation of Computer and Telecommunication Systems (MASCOTS),Washington, DC, 2012: 19-28.

[7] Chen Jun-liang, Chen Wang, Zhou Bing-bing,.. Tradeoffs between profit and customer satisfaction for service provisioning in the cloud[C]. Proceedings of the 20th International Symposium on High Performance Distributed computing, ACM,San Jose, 2011: 229-238.

[8] Hyun J M, Yun C, Hacigu X,.. SLA-aware profit optimization in cloud services via resource scheduling[C]. 2010 6th World Congress on Services (SERVICES-1), Minneapolis, 2010: 152-153.

[9] Cao Jun-wei, Hwang Kai, Li Ke-qin,.. Optimal multiserver configuration for profit maximization in cloud computing[J]., 2012, 24(6): 1087-1096.

[10] Chaisiri S, Bu-Sung L, and Niyato D. Profit maximization model for cloud provider based on Windows Azure platform[C]. 2012 9th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON), Phetchaburi, 2012: 1-4.

[11] Stage A, Setzer T, and Bichler M. Automated capacity management and selection of infrastructure-as-a-service providers[C]. IEEE Symposium Intergrated Network Management, New York, 2009: 20-23.

[12] Poli R, Kennedy J, and Blackwell T. Particle swarm optimization[J]., 2007, 1(1): 33-57.

殷 波： 女，1984年生，博士生，研究方向为云计算.

王 颖： 女，1976年生，副教授，硕士生导师，研究方向为云计算、通信软件与网络管理.

邱雪松： 男，1973年生，教授，博士生导师，研究领域为网络与业务管理.

孟洛明： 男，1955年生，教授，博士生导师，研究领域为通信网、网络管理、通信软件.

A Resource Provisioning Mechanism for Service Providers in Cloud

Yin Bo Wang Ying Qiu Xue-song Meng Luo-ming

(,,100876,)

Considering Service Providers (SP) revenue optimization issue, a two-stage multi-virtual machine resource provisioning mechanism is proposed in this paper. Firstly, a capacity planning model is proposed and the particle swarm algorithm is used to make resource purchase set, which can gain the maximize profit for SP. Then, a utility function to measure customer’s satisfaction is proposed to optimize SP’s profit in the long way. Simulation experimental results show that the proposed method improves effectively SP’s profit, and gains better user’s satisfaction.

Cloud computing; Resource provisioning; User’s satisfaction; Profit optimization

TP393

A

1009-5896(2014)01-0015-07

10.3724/SP.J.1146.2013.00427

2013-04-01收到，2013-08-15改回

国家863计划项目(2013AA013502), 国家自然科学基金创新研究群体科学基金(61121061)和国家科技支撑计划(2012BAH06B02)资助课题

殷波 yinbo@bupt.edu.cn