一種云計算資源的多目標優(yōu)化的調(diào)度方法*

徐忠勝，沈蘇彬

（南京郵電大學計算機學院，江蘇南京210003）

一種云計算資源的多目標優(yōu)化的調(diào)度方法*

徐忠勝，沈蘇彬

（南京郵電大學計算機學院，江蘇南京210003）

云計算通過虛擬化技術將基礎設施硬件資源虛擬化，以動態(tài)可縮放的方式提供給用戶。云計算基礎設施規(guī)模不斷增加導致資源調(diào)度系統(tǒng)負載不均衡，從而造成資源浪費等問題。提出多目標優(yōu)化資源調(diào)度策略和相應的算法，試圖同時滿足多個資源調(diào)度優(yōu)化目標，如減少資源浪費，降低服務等級約定（SLA）違背率、保持系統(tǒng)負載均衡等。通過仿真實驗，驗證了多目標優(yōu)化資源調(diào)度的策略能夠在多個相互沖突的目標之間實現(xiàn)最優(yōu)權衡。

云計算；多目標優(yōu)化；虛擬機；資源調(diào)度

0 引言

云計算是一種新的計算服務模式，可以在不同的抽象級別實現(xiàn)，這取決于云提供商提供的特定服務，如存儲、計算等。本文主要研究基礎設施作為服務（IaaS）[1]的云的資源調(diào)度，IaaS云主要通過虛擬化技術[2]將基礎設施提供給用戶，包括以虛擬機方式的計算服務、虛擬磁盤方式的存儲服務、虛擬機交換機的網(wǎng)絡服務。隨著計算機與網(wǎng)絡技術的高速發(fā)展，互聯(lián)網(wǎng)用戶不斷增多，計算機基礎設施規(guī)模也不斷擴大，導致資源浪費不斷增加，數(shù)據(jù)中心的負載失衡嚴重。云環(huán)境的動態(tài)特性使得云提供商向用戶提供的云服務不能嚴格滿足服務等級約定（SLA）。而大多數(shù)的解決方案只涉及某一方面的目標優(yōu)化，比如通過服務器的整合降低數(shù)據(jù)中心的能源消耗，但是降低了用戶需求的滿意度。有的研究工作為了減少SLA違背率，將虛擬機分散放在盡可能多的服務器上，降低了資源的利用率，這是因為不同的優(yōu)化目標之間是相互沖突的。

針對以上問題，本文提出了多目標優(yōu)化的資源調(diào)度策略，該方法在多個相互沖突的目標之間實現(xiàn)最優(yōu)權衡，如降低服務等級協(xié)議違背率、減少資源浪費和負載均衡等。

1 相關工作分析

在云計算基礎設施中，虛擬機資源的分配是一個重要研究課題。目前已有一系列研究成果，比如參考文獻[3-4]通過服務器的整合來降低數(shù)據(jù)中心的能源消耗，但是增加了服務等級約定違背率。參考文獻[5]中提出了一種基于遺傳算法的負載均衡調(diào)度策略，該算法計算出在部署請求的虛擬機資源之后對系統(tǒng)的影響，并選擇最小影響的解決方案，避免進行在線遷移，但是在資源分配過程中存在資源浪費的問題。Wood[6]描述了動態(tài)監(jiān)測系統(tǒng)中CPU、內(nèi)存資源、網(wǎng)絡帶寬的利用率，提出了白盒測試與黑盒測試的方法，并重點研究了通過虛擬機遷移進行重映射解決負載失衡的問題，但是增加了SLA違背率。參考文獻[7]中提出通過在虛擬機之間轉(zhuǎn)移工作負載，優(yōu)化各個虛擬機的資源需求，在任務執(zhí)行之后減少虛擬機的遷移，避免系統(tǒng)性能的降低，但是同樣存在資源浪費的問題。

現(xiàn)有研究中很少將資源浪費、保證服務等級約定和負載均衡進行綜合考慮，實現(xiàn)虛擬機資源調(diào)度的多目標優(yōu)化。大部分的研究只是將多目標優(yōu)化問題轉(zhuǎn)化為若干個單目標優(yōu)化問題分階段解決，很少是同時對多個目標進行優(yōu)化的。

2 資源優(yōu)化調(diào)度建模

2.1 數(shù)學模型

IaaS中虛擬機資源分配問題可以描述成在動態(tài)云環(huán)境中多維裝箱問題。本文構建了數(shù)學模型，使用元組q=＜t，VMSET，ts＞表示各個虛擬機資源調(diào)度請求，其中t表示虛擬機資源請求到達的時刻，VMSET表示要申請的虛擬機集，ts表示虛擬機的生命周期。

一個簡單的例子如圖1所示。涉及到7個虛擬機資源請求，如虛擬機請求{2，{1，2}，6}表示請求在時刻2到達，申請了序號為1與2兩個虛擬機，虛擬機的生命周期為6個時間單元。在時刻15時虛擬機6、7還在運行，1～5號虛擬機被刪除了。

圖1 虛擬機資源分配實例

本文考慮一個云數(shù)據(jù)中心的基礎設施由M個不同的物理主機組成，每個物理主機由K種資源表示（如CPU，內(nèi)存，網(wǎng)絡帶寬，磁盤等）。每個物理主機j對每種資源k有一個已知容量Cjk，其中j∈{1…M}，k∈{1…K}。例如規(guī)定CPU資源由索引值1表示，即k=1時表示為CPU資源。

2.2 資源調(diào)度的優(yōu)化目標

（1）減少資源浪費：不同的虛擬機資源調(diào)度策略對物理主機的剩余資源影響程度不同?？紤]到將來虛擬機資源請求，各個物理主機上的剩余資源應該在不同維度資源之間保持均衡。否則，可能會阻止未來的虛擬機資源請求，從而造成浪費資源。

（2）降低服務等級約定（SLA）違背率：滿足用戶服務質(zhì)量是衡量云計算服務的重要指標。服務質(zhì)量請求通常表示為服務等級約定（SLA），在云系統(tǒng)中服務等級約定由最大響應時間或者最小吞吐量決定。

（3）負載均衡：在云環(huán)境中將資源分配給虛擬機，要使得所有物理主機上的資源利用率均衡。

3 多目標優(yōu)化的資源調(diào)度算法

多目標優(yōu)化資源調(diào)度算法由兩個資源調(diào)度過程組成：虛擬機資源初始化分配與虛擬機動態(tài)遷移。

3.1 綜合權衡值

在提出多目標優(yōu)化算法之前，本文引入多目標優(yōu)化算法核心的計分函數(shù)，稱為“綜合權衡值”，其目的是為了衡量在過去的TM時間內(nèi)服務等級約定（SLA）違背率程度、資源浪費的程度與數(shù)據(jù)中心負載均衡度。所以“綜合權衡值”主要由服務等級約定（SLA）違背率、資源浪費的程度以及數(shù)據(jù)中心負載均衡度三部分的效用函數(shù)組成。

第一個是服務等級約定違背率的效用函數(shù)，在一個給定的時刻，定義函數(shù)U衡量服務等級約定的違背率，公式（1）表示當虛擬機集合V部署在物理主機h上時，函數(shù)U（H，V，T）衡量在t時刻對于物理主機h的CPU資源需求的不滿意度。

式中，ri（t）表示虛擬機i請求的CPU資源量，ai（t）表示物理主機分配給虛擬機i請求的CPU資源量。它的范圍值在[0，1]。

第二個是資源浪費程度的效用函數(shù)，如公式（2）所示，在一個給定的時刻，定義函數(shù)L衡量虛擬機集合V部署在物理主機h上時，物理主機h上的資源浪費程度。

式中，Rk代表第k種資源的歸一化的剩余資源，即剩余資源占總資源的比率；用下標z表示多維資源中最小歸一化的剩余容量的資源。在服務器上浪費的剩余資源被計算為最小的歸一化剩余資源與其他剩余資源差異的總和，它的值范圍為[0，1]。

最后一個是數(shù)據(jù)中心的負載均衡效用函數(shù)。更具體地說，就是數(shù)據(jù)中心中物理主機之間資源負載的均衡程度。在一個給定的時刻，定義函數(shù)B衡量數(shù)據(jù)中心的負載均衡度，如公式（3）表示虛擬機集V部署在物理主機h上時，數(shù)據(jù)中心的負載均衡程度。

式中，M為所有物理主機節(jié)點的數(shù)量，CPUj（t）表示物理主機j在t時刻的CPU利用率，CPUavg為M個物理主機節(jié)點的CPU利用率均值。

本文使用DR表示“綜合權衡值”，如公式（4），表示

式中α1+α2+α3=1，α1、α2、α3是各個子目標的權衡值，通過設置α1、α2、α3的大小可以權衡各個子目標實現(xiàn)的程度。

3.2 虛擬機資源初始化調(diào)度算法

虛擬機資源調(diào)度初始化分配算法過程如圖2所示。在過去的TM時間內(nèi)多目標優(yōu)化的綜合效用函數(shù)性能指標。

圖2 虛擬機資源初始化分配過程

（1）首先根據(jù)指定的過濾方法（例如物理主機剩余資源不能滿足用戶需求）對所有可用的物理主機節(jié)點進行過濾，得到滿足過濾條件的物理主機節(jié)點集合。

（2）計算出過濾后所有物理主機“綜合權衡值”，然后將所有過濾后的物理主機節(jié)點按照“綜合權衡值”的大小進行升序排列。

（3）選擇“綜合權衡值”最小的物理主機給用戶分配虛擬機資源。

3.3 虛擬機動態(tài)遷移算法

虛擬機的遷移涉及到確定遷移的時機、虛擬機的選擇和虛擬機的放置問題。

通過實時監(jiān)測物理主機，確定虛擬機遷移的時機。為了防止暫時的越界而發(fā)生的虛擬機遷移，在資源監(jiān)測過程中可以設定一個固定大小的時間段，并且資源利用率在這個時間段內(nèi)按照固定的時間間隔采樣，如果在采樣結(jié)果中資源利用率超過門限值的次數(shù)大于設定的次數(shù)，則開始預測下一次的資源利用率，當下一次資源利用率也超過了門限值時觸發(fā)虛擬機的遷移。本文使用了時間序列預測技術[8]里的自回歸模型AR（n），此模型可以預測未來的資源利用率。

在確定哪個物理主機需要遷移虛擬機后，系統(tǒng)會選擇將該物理主機上的虛擬機遷移出去。此時，需要討論虛擬機的選擇與虛擬機的放置策略。關于虛擬機的選擇以及放置，可以通過以下算法獲得。

虛擬機動態(tài)遷移算法：

算法思路：在確定哪個物理主機需要遷移虛擬機之后，考慮該物理主機上哪一個虛擬機需要遷移，然后確定遷移到哪一個物理主機上。算法中第一層循環(huán)為遍歷遷移源物理主機上的所有虛擬機，第二層循環(huán)是遍歷除了遷移源物理主機之外的所有物理主機節(jié)點。經(jīng)過兩次循環(huán)，首先計算出在遷移之前，遷移源物理主機與遷移目的物理主機的綜合權衡值的和值，然后計算出遷移之后源物理主機與目的物理主機的綜合權衡值的和值，最后計算出虛擬機從源物理主機遷移到目的物理主機的遷移值。遷移值被定義為兩個綜合權衡和值之間的差異。最后，取出所有遷移值中的最高值，只有遷移值為正時才會考慮進行遷移。

4 測試及結(jié)果分析

4.1 仿真建立

本節(jié)采用CloudSim[9]云計算仿真平臺進行多目標優(yōu)化的資源調(diào)度算法的驗證，并提供了多目標優(yōu)化的資源調(diào)度算法與其他不同算法相比較的結(jié)果。CloudSim是由澳大利亞墨爾本大學的網(wǎng)格實驗室和Gridbus項目推出的云計算仿真軟件。

仿真實驗的硬件環(huán)境：Intel Core i5，CPU主頻為2.66 GHz，內(nèi)存4 GB，硬盤500 GB。軟件環(huán)境：Windows 7操作系統(tǒng)，MyEclipse 10.7和CloudSim-3.0.3，以及Java1.8.0開發(fā)工具。在多目標優(yōu)化資源調(diào)度算法中設置門限值為80%，物理主機節(jié)點監(jiān)測的周期為3 s，對系統(tǒng)資源的采樣間隔為4 s，一次監(jiān)測過程的時間長度為1 min，即一次監(jiān)測過程中有20次歷史監(jiān)測數(shù)據(jù)。當超過門限值的次數(shù)大于等于10次就觸發(fā)告警。任務的數(shù)量分三種情況模擬：200個、400個、600個。

這個實驗主要分析本文提出的多目標優(yōu)化算法的有效性，比較了以下4種算法：（1）單目標減少資源浪費算法；（2）單目標降低SLA違背率算法；（3）單目標負載均衡算法；（4）多目標優(yōu)化資源調(diào)度算法。

4.2 仿真結(jié)果與分析

如圖3、圖4、圖5所示描述了在不同的資源調(diào)度算法下的資源浪費程度、SLA違背率以及數(shù)據(jù)中心的不均衡度。資源浪費程度越高，表示各種資源利用的差距越大。SLA違背率越低說明用戶的服務質(zhì)量越高。數(shù)據(jù)中心負載均衡度越低代表負載均衡效果越好。由圖可知采用減少資源浪費的算法時資源浪費的程度最低，使用減少SLA違背率算法時SLA違背率最低，使用負載均衡算法時數(shù)據(jù)中心不均衡度是最低的，這是因為在執(zhí)行單目標優(yōu)化問題時，單目標優(yōu)化算法能得出最優(yōu)解。由圖3、圖4、圖5可知，雖然單目標優(yōu)化算法在各自的優(yōu)化目標上取得最優(yōu)解，但是單目標算法在其他目標實現(xiàn)的效果上比較差，如雖然使用減少SLA算法時SLA違背率最低，但是資源利用率很低。這是因為在多目標優(yōu)化的問題中，各個子目標之間有時是沖突的，一個解不能同時使所有的子目標達到最優(yōu)，所以需要在各個目標之間做好協(xié)調(diào)權衡。

多目標優(yōu)化算法就很好地解決了多個目標之間相互沖突的問題，雖然多目標優(yōu)化算法不能使數(shù)據(jù)中心取得最低的資源浪費程度、最低的服務等級約定違背率與最低的不均衡度，但是在各個目標優(yōu)化的效果比較好。如圖5所示，多目標優(yōu)化資源調(diào)度算法的數(shù)據(jù)中心的不均衡度比負載均衡算法的值高，但是低于減少SLA違背率算法與減少資源浪費算法的值。

圖3 不同資源調(diào)度算法下資源浪費程度

圖4 不同資源調(diào)度算法下SLA違背率

圖5 不同資源調(diào)度算法下數(shù)據(jù)中心不均衡度

5 總結(jié)

本文針對多目標優(yōu)化的資源調(diào)度問題，提出了多目標資源優(yōu)化的資源調(diào)度策略。多目標優(yōu)化資源調(diào)度的策略能夠在多個相互沖突的目標之間實現(xiàn)最優(yōu)權衡。通過仿真實驗驗證了多目標資源優(yōu)化的資源調(diào)度策略的有效性。

[1]BHARDWAJ S，JAIN L，JAIN S.Cloud computing：a study of infrastructure as a service（IAAS）[J].International Journal of Engineering and Information Technology，2010，2（1）：60-63.

[2]UHLIG R，NEIGER G，RODGERS D，et al.Intel virtualization technology[J].Computer，2005，38（5）：48-56.

[3]CHEN Y，DAS A，QIN W，et al.Managing server energy and operational costs in hosting centers[C].ACM SIGMETRICS Performance Evaluation Review，ACM，2005，33（1）：303-314.

[4]KUSIC D，KEPHART J O，HANSON J E，et al.Power and performance management of virtualized computing environments via lookaheadcontrol[J].Cluster Computing，2009，12（1）：1-15.

[5]HU J，GU J，SUN G，et al.A scheduling strategy on load balancing of virtual machine resources in cloud computing environment[C].Parallel Architectures，Algorithms and Programming（PAAP），2010 Third International Symposium on.IEEE，2010：89-96.

[6]WOOD T，SHENOY P J，VENKATARAMANI A，et al. Black-box and Gray-box strategies for virtual machine migration[C].NSDI，2007：17-17.

[7]TANG C，STEINDER M，SPREITZER M，et al.A scalable application placement controller for enterprise data centers[C].Proceedings of the 16th International Conference on World Wide Web，ACM，2007：331-340.

[8]BOX G E P，JENKINS G M，REINSEL G C.Time series analysis：forecasting and control[M].New York：John Wiley &Sons，2013.

[9]CALHEIROS R N，RANJAN R，BELOGLAZOV A，et al. CloudSim：a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software：Practice and Experience，2011，41（1）：23-50.

A multi-objective optim ization scheduling method in Cloud com puting

Xu Zhongsheng，Shen Subin
（School of Computer，Nanjing University of Posts and Telecommunications，Nanjing 210003，China）

Cloud computing infrastructure virtualizes hardware resource by virtualization technology，and provides it to users in scalable way.The increasing size of cloud computing infrastructure results in the waste of resources because of system load imbalance and other issues.This paper proposes a multi-objective optimization of resource scheduling policies and a related algorithm that can simultaneously achieve multiple objectives，such as reducing the waste of resources，reducing the service level agreement（SLA）and keep the system load balance.Simulation results show that the multi-objective optimization of resource scheduling method can achieve the optimal trade-offs among multiple conflicting goals.

Cloud computing；multi-objective optimization；virtual machine；resource scheduling

TP393

A

1674-7720（2015）13-0017-04

2015-03-02）

徐忠勝（1989-），通信作者，男，碩士研究生，主要研究方向：計算機網(wǎng)絡。E-mail：xuzhongsheng722@sina.com。

江蘇省未來網(wǎng)絡前瞻性研究資助項目（BY2013095-1-08）

沈蘇彬（1964-），男，研究員，博士生導師，主要研究方向：計算機網(wǎng)絡、下一代電信網(wǎng)及網(wǎng)絡安全。