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

徐忠勝，沈蘇彬

（南京郵電大學(xué)計算機(jī)學(xué)院，江蘇南京210003）

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

徐忠勝，沈蘇彬

（南京郵電大學(xué)計算機(jī)學(xué)院，江蘇南京210003）

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

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

0 引言

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

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

1 相關(guān)工作分析

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

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

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

2.1 數(shù)學(xué)模型

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

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

圖1 虛擬機(jī)資源分配實例

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

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

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

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

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

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

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

3.1 綜合權(quán)衡值

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

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

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

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

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

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

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

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

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

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

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

圖2 虛擬機(jī)資源初始化分配過程

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

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

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

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

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

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

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

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

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

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

4.1 仿真建立

本節(jié)采用CloudSim[9]云計算仿真平臺進(jìn)行多目標(biāo)優(yōu)化的資源調(diào)度算法的驗證，并提供了多目標(biāo)優(yōu)化的資源調(diào)度算法與其他不同算法相比較的結(jié)果。CloudSim是由澳大利亞墨爾本大學(xué)的網(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ā)工具。在多目標(biāo)優(yōu)化資源調(diào)度算法中設(shè)置門限值為80%，物理主機(jī)節(jié)點監(jiān)測的周期為3 s，對系統(tǒng)資源的采樣間隔為4 s，一次監(jiān)測過程的時間長度為1 min，即一次監(jiān)測過程中有20次歷史監(jiān)測數(shù)據(jù)。當(dāng)超過門限值的次數(shù)大于等于10次就觸發(fā)告警。任務(wù)的數(shù)量分三種情況模擬：200個、400個、600個。

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

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

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

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

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

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

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

5 總結(jié)

本文針對多目標(biāo)優(yōu)化的資源調(diào)度問題，提出了多目標(biāo)資源優(yōu)化的資源調(diào)度策略。多目標(biāo)優(yōu)化資源調(diào)度的策略能夠在多個相互沖突的目標(biāo)之間實現(xiàn)最優(yōu)權(quán)衡。通過仿真實驗驗證了多目標(biāo)資源優(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-），通信作者，男，碩士研究生，主要研究方向：計算機(jī)網(wǎng)絡(luò)。E-mail：xuzhongsheng722@sina.com。

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

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