采用隨機規(guī)劃模型的云資源分配算法①

陳俊杰

(南通大學 電子信息學院,南通 226019)

近年來,云計算技術發(fā)展迅速,涌現(xiàn)出了一大批成熟的云計算服務平臺.基礎設施即服務(IaaS)、平臺即服務(PaaS)和軟件即服務(SaaS)是云計算的三種主要的服務模式,其中IaaS應用最廣泛.IaaS采用虛擬化技術將物理服務器抽象成虛擬機,并且通過互聯(lián)網提供給云消費者使用,云消費者采用按使用付費的方式租用虛擬機.

云提供商(Amazon EC2)向云消費者提供了兩種計費策略,按需實例和預留實例.對于按需實例,云消費者根據當前的工作負載動態(tài)獲取,按照實際使用情況付費.對于預留實例,云消費者需要預付部分費用,并且在預留期間不管是否使用都需要付費.通過權衡按需實例和預留實例的使用,可以有效降低云消費者的資源使用成本.因此,云資源預留問題即為: 確定預留資源的數量,以最小化云消費者的資源使用成本.

虛擬機整合問題旨在通過虛擬機的在線遷移,在滿足云消費者資源需求的前提下,最小化所使用的物理服務器的數量,以降低能耗,實現(xiàn)綠色云計算.師雪霖等人借鑒網絡效用最大化模型,提出了虛擬機放置的效用最大化模型,并且將原始問題轉化為拉格朗日對偶問題,采用次梯度算法進行求解[1].趙君等人同時考慮物理資源的浪費和網絡總流量,將虛擬機放置問題建模為多目標優(yōu)化問題,并且提出了一種基于多目標蟻群優(yōu)化的虛擬機放置算法[2].Xiao等人提出了一種虛擬機放置的啟發(fā)式算法,引入了偏度的概念度量服務器中多種資源利用的不均衡性,通過最小化偏度,可以有效整合不同類型的工作負載,提高服務器資源的整體利用率[3].Zhang等人考慮了服務器和負載的異構性,提出了異構感知的云資源提供算法[4].

本文從云消費者的角度研究云資源提供問題.Chaisiri等人考慮了需求和價格的不確定性,將云資源提供問題建模為多階段隨機整數規(guī)劃問題,并且使用Benders分解算法進行求解[5].冉泳屹等人使用大偏差理論在線估計過載概率,根據過載概率動態(tài)調整按需實例的數量,同時采用自回歸模型確定預留實例的數量,進一步降低云消費者的資源使用成本[6].然而,冉泳屹等人并沒有給出云資源預留問題的數學描述,并且在確定預留實例的數量時,僅僅考慮了單一的實例類型.Hwang等人將云資源提供問題分成兩個階段,在資源預留階段,通過一個啟發(fā)式方法確定資源預留方案,在按需分配階段,采用卡爾曼濾波器預測當前的資源需求[7].Hwang等人雖然給出了云資源預留問題的數學描述,但是所提出的啟發(fā)式算法僅僅考慮了一種虛擬機類型,以確定最優(yōu)的虛擬機預留數量的上界和下界.在先前的研究中,我們將云資源提供問題建模為兩階段的隨機整數規(guī)劃問題,并轉化為確定性的整數線性規(guī)劃問題,利用CPLEX軟件進行求解,但是其計算復雜度較高,不適用于在線應用[8].

本文從云消費者的角度研究云資源提供問題,提出了一種采用隨機規(guī)劃模型的云資源分配算法.首先,同時考慮按需實例和預留實例,采用兩階段隨機整數規(guī)劃對云資源提供問題進行建模.然后,采用抽樣平均近似方法減少資源提供問題的場景數量,降低計算復雜度,并且提出了一種基于階段分解的混合進化算法求解資源提供問題.在仿真實驗中,基于真實的工作負載數據及Amazon EC2的定價模型評估所提出的云資源分配算法,驗證了所提出算法的有效性.

1 云資源提供問題

1.1 云計算環(huán)境

針對特定的服務,云提供商提供了多種可供選擇虛擬機類型,令V={V1,V2,···,VN}表示云提供商所提供的一組虛擬機類型,N為虛擬機類型的總數.假設一個Vi類型的虛擬機的資源配置為Ri=[ri1,ri2,···,riM],M為虛擬機所擁有的資源類型的總數.令Ci表示一個Vi類型的虛擬機的服務容量,定義為在給定的服務質量約束條件下,一個Vi類型的虛擬機所能支持的最大并發(fā)用戶數或服務請求到達速率.

云提供商(Amazon EC2)提供了兩種計費策略,按需實例和預留實例.對于按需實例,云消費者根據當前的工作負載動態(tài)獲取,按照實際使用情況付費.對于預留實例,云消費者需要預付部分費用,并且在預留期間不管是否使用都需要付費.令按需實例的計費周期(短期規(guī)劃周期)為TS,預留實例的計費周期(長期規(guī)劃周期)為TL,令T=TL/TS.假設一個Vi類型的預留實例預付費用為PRi,令pRi=PRi/T,在預留期間每時間TS費用為pri,一個Vi類型的按需實例每時間TS費 用為poi,通常假設poi＞pri+pRi.

1.2 基于隨機規(guī)劃的云資源提供問題

假設在第t(1≤t≤T)個短期規(guī)劃周期,云消費者的工作負載為dt.令R={n1,···,nN}表示長期規(guī)劃周期的資源預留方案,其中ni為Vi類型的預留實例的數量,預留的服務容量為預留實例的使用成本為在短期規(guī)劃周期,若預留的服務容量能夠滿足工作負載需求,則不需要動態(tài)分配按需實例,否則,需要動態(tài)分配按需實例,按需實例的使用成本為

其中,xi表 示Vi類型的按需實例的數量.問題(1)是短期規(guī)劃周期的按需資源分配問題,即給定資源預留方案和當前的工作負載,動態(tài)分配按需實例,在滿足工作負載需求的條件下,最小化按需實例的使用成本.

云資源提供問題可以描述為

其中目標函數為長期規(guī)劃周期中預留實例和按需實例總的使用成本.問題(2)依賴于長期規(guī)劃周期的工作負載情況,使用云消費者的工作負載歷史數據,可以對工作負載的概率分布pD(Dk)進 行估計,其中Dk,k=1,2,···,K,(D1＜D2＜···＜DK)為工作負載所有可能的取值.因此,問題(2)可以轉化為

其中目標函數為每個短期規(guī)劃周期中預留實例和按需實例的平均使用成本.問題(3)是一個兩階段的隨機整數規(guī)劃問題.在資源預留階段,需要根據長期規(guī)劃周期的工作負載情況,確定預留實例的類型和數量,在按需分配階段,需要根據當前的工作負載,確定動態(tài)分配的按需實例的類型和數量.

問題(3)可以轉化為一個確定性的整數線性規(guī)劃問題,

問題(4)被稱為問題(3)的確定性等價問題,可以通過CPLEX軟件進行求解.

2 云資源分配算法

2.1 抽樣平均近似問題

當工作負載D取值(隨機規(guī)劃問題的場景)的數量很大,甚至可能是一個連續(xù)的隨機變量時,問題(3)中的隨機規(guī)劃問題將不易求解.為了求解這個復雜的問題,可以使用抽樣平均近似方法.抽樣平均近似方法對場景進行抽樣,減少場景數量,降低求解復雜度.常用的抽樣方法包括蒙特卡羅方法、擬蒙特卡羅方法和均勻離散化方法等.因為工作負載D是一個一維的隨機變量,所以這里使用均勻離散化方法[9].

在均勻離散化方法中,將整個概率區(qū)間[ 0,1]均勻離散化,生成NS個等間隔的離散概率點pj=(2j-1)/(2NS),j=1,…,NS,對于每一個pj,找到最小的kj(1≤kj≤K),使得則Dkj為工作負載D的第j個抽樣.由D的NS個抽樣,問題(3)可以近似表示為

上述問題被稱為問題(3)的抽樣平均近似問題,該問題仍然是一個兩階段的隨機整數規(guī)劃問題,可以轉化為一個確定性的整數線性規(guī)劃進行求解,并且樣本容量NS越大,抽樣平均近似問題的近似精度越高.

2.2 混合進化算法

雖然抽樣平均近似方法可以減少場景數量,有效降低求解復雜度,但是問題(5)轉化為確定性等價的整數規(guī)劃問題之后,規(guī)模仍然很大,不采用分解算法很難求解.本文提出了一種基于階段分解的混合進化算法,使用進化算法對第一階段決策變量進行搜索,對于第二階段子問題使用整數規(guī)劃進行求解.因此,問題(5)可以分解為:

主問題:

子問題:

在主問題中需要確定預留實例的類型和數量,在子問題中需要確定按需實例的類型和數量,子問題的決策依賴于主問題的決策,并且對于主問題中給定的虛擬機預留配置,子問題是NS個小規(guī)模的整數線性規(guī)劃問題.對于第一階段主問題,使用進化算法進行求解,對于第二階段子問題,使用標準的整數線性規(guī)劃求解方法進行求解.

接下來重點研究基于遺傳算法的主問題求解方法.遺傳算法的關鍵是編碼方案、適應度函數及遺傳算子的設計[10].

(1)染色體編碼

在進行遺傳操作之前,首先需要對優(yōu)化問題的可行解進行編碼.常用的編碼方法有二進制編碼、格雷碼編碼和實數編碼等,其中二進制編碼存在漢明懸崖問題,格雷碼編碼在進行交叉操作時會產生更高階的非線性.為了克服這些問題,這里采用實數編碼方案.對于問題(6)的一個可行解(n1,n2,···,nN),ni∈N0且0≤ni≤nmiax,其中nmiax=「Dmax/Ci?,Dmax為工作負載需求的最大值,ni可 以用一個實數變量xi表 示0 ≤xi.因此,可 行 解可以編碼為(x1,x2,···,xN).

(2)適應度函數

適應度函數用于評價種群中個體對環(huán)境的適應程度,也就是可行解的優(yōu)劣,可行解越好,適應度函數值越大.問題(6)是一個最小化問題,以總的資源提供成本最小化為優(yōu)化目標.對于可行解(n1,n2,···,nN),適應度函數f(n1,···,nN)定義為

其中,T(n1,···,nN)是虛擬機預留配置為(n1,···,nN)時總的資源提供成本,Tmin是到目前為止所獲得的目標函數的最小值.為了確定T(n1,···,nN),需要求解NS個子問題(7).

(3)選擇

選擇算子實現(xiàn)種群的優(yōu)勝劣汰,既要保證一定的選擇強度,使得種群向著最優(yōu)解進化,又要保持種群的多樣性,防止未成熟收斂.常用的選擇算子有適應度比例選擇、錦標賽選擇和排序選擇等.根據Blickle等人[11]的研究,指數排序選擇算子能夠在相同的選擇強度條件下,保證較好的種群多樣性,避免算法陷入局部最優(yōu)解,因此本文采用指數排序選擇算子.在指數排序選擇操作中,首先對種群中所有個體按照適應度值升序排列,然后按照個體的順序為其分配相應的選擇概率

其中,c=pi/pi+1(0＜c＜1)是相鄰兩個個體選擇概率的比值,c值越小,選擇算子的選擇強度越大.在確定了每個個體的選擇概率之后,使用輪盤賭采樣法選擇個體.

(4)交叉

交叉操作是遺傳算法的關鍵步驟,決定了遺傳算法的全局搜索能力.本文采用模擬二進制交叉算子(SBX)[12],對于大多數優(yōu)化問題具有良好的全局搜索能力.在SBX操作中,對于兩個父個體βi=(βi1,βi2,···,βiN)和βj=(βj1,βj2,···,βjN),兩個子個體 β′i和 β′j定義為

其中,Bk定義為

其中,u是 [ 0,1]上 均勻分布的隨機數,η取值為2.

(5)變異

變異算子決定了遺傳算法的局部搜索能力,同時也維持了種群的多樣性.常用的變異算子有均勻變異、高斯變異和Breeder變異等.均勻變異和高斯變異的性能依賴于參數的自適應調整,Breeder變異的性能稍差,但是更容易實施.在Breeder變異操作中,

其中,正負號以相等的概率隨機選擇,rangei是ni的取值范圍,θ定義為

其中,a(m)以 概率1 /M取值為1,以概率1 -1/M取值為0.

遺傳算法的流程為:

參數設置: 在遺傳算法中,種群規(guī)模N、交叉概率pc和 變異概率pm與算法的性能密切相關.通常: 種群規(guī)模設置為大于變量數的10倍,交叉概率設置為0.7-0.8之間,變異概率設置為變量數的倒數[10].

步驟1.隨機生成問題(6)的N個可行解作為初始種群;

步驟2.使用指數排序選擇法選擇當前種群中的個體進行復制,執(zhí)行N次,生成N個個體;

步驟3.將選擇-復制操作生成的N個個體進行隨機配對,對每一對個體,以交叉概率pc執(zhí)行SBX操作;

步驟4.對交叉操作生成的每一個個體,以變異概率pm執(zhí)行Breeder變異操作;

步驟5.判斷是否滿足終止條件,若滿足則終止遺傳算法,否則返回步驟2繼續(xù)執(zhí)行遺傳算法.

3 仿真實驗

使用某網站一個月的工作負載歷史數據作為實驗數據,如圖1所示.根據工作負載歷史數據,可以對工作負載的概率分布進行估計,結果如圖2所示.針對Web服務,云提供商(Amazon EC2)提供了4種類型的虛擬機: Small(m1.small),Medium(m1.medium),Large(m1.large),Extra Large(m1.xlarge),它們的計費策略和服務能力[7]如表1所示.

圖1 工作負載

圖2 工作負載的概率分布

表1 每種虛擬機類型的計費策略和服務能力

3.1 資源預留方案對運營成本的影響

首先分析資源預留對云消費者的資源使用成本的影響.研究不同的資源預留方案下云消費者的資源使用成本,結果如圖3所示.從圖中可以看出,最優(yōu)的資源預留方案為{n1=0,n2=0,n3=4,n4=0},預留的服務容量為260請求/秒,資源使用成本為5694美元.隨著預留資源的增加,預留實例的使用成本逐漸增大,按需實例的使用成本逐漸減小,在預留資源太多或者太少時資源使用成本均比較高,這是因為在預留資源太多時,預留實例得不到充分使用,造成資源浪費,在預留資源太少時,需要使用更多的按需實例.

圖3 資源預留方案對運營成本的影響

3.2 抽樣平均近似方法

接下來分析抽樣平均近似方法的性能,比較均勻離散化方法與蒙特卡羅方法及擬蒙特卡羅方法的近似精度,并討論抽樣點數對近似精度的影響,結果如圖4所示.從圖中可以看出,抽樣點數越大,抽樣平均近似方法的近似精度越高,在相同的抽樣點數下,均勻離散化方法比蒙特卡羅方法及擬蒙特卡羅方法的近似精度更高,當抽樣點數NS=10時,均勻離散化方法的近似精度達到99%.因此,選擇均勻離散化方法,并且選取抽樣點數NS=10.

圖4 抽樣平均近似方法的性能

3.3 混合進化算法

最后分析混合進化算法的性能.從圖5可以看出,隨著進化代數的增加,所獲得的資源預留方案逐漸趨向于最優(yōu)的資源預留方案,當進化代數G≥7時,所獲得的資源預留方案即為最優(yōu)的資源預留方案.因此,混合進化算法的終止條件選為G=20.比較本文所提出的混合進化算法和Hwang等人所提出的啟發(fā)式算法的性能,二者均可獲得最優(yōu)的資源預留方案,節(jié)省了超過25%的運營成本,但是Hwang等人的方法需要針對搜索范圍內的每個資源預留方案,確定總的運營成本,所以求解過程所消耗的時間更長,并且當最優(yōu)解不在搜索范圍內時不能獲得最優(yōu)的資源預留方案.

圖5 混合進化算法的進化過程

4 總結

本文針對云資源提供問題,提出了一種采用隨機規(guī)劃模型的云資源分配算法,在滿足云消費者資源需求的條件下,最小化其資源使用成本.首先,同時考慮按需實例和預留實例,采用兩階段隨機整數規(guī)劃對云資源提供問題進行建模.然后,采用抽樣平均近似方法和基于階段分解的混合進化算法求解云資源提供問題.基于真實的工作負載數據及Amazon EC2的定價模型驗證所提出的云資源分配算法.仿真實驗結果表明,所提出的云資源分配算法能夠在較短時間內獲得近似最優(yōu)的云資源預留方案,有效降低了云消費者的資源使用成本.