一種面向云服務提供商的資源分配機制

殷 波 王 穎 邱雪松 孟洛明

?

一種面向云服務提供商的資源分配機制

殷 波*王 穎 邱雪松 孟洛明

(北京郵電大學網絡與交換技術國家重點實驗室 北京 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