郭 磊 侯維剛

（東北大學(xué)信息科學(xué)與工程學(xué)院，沈陽(yáng)，110819）

引 言

近年來(lái)，Amazon EC2，Microsoft Azure，Infrastructure-asa-service（IaaS）等云數(shù)據(jù)中心平臺(tái)快速發(fā)展，并實(shí)現(xiàn)了多個(gè)應(yīng)用服務(wù)提供商對(duì)底層物理基礎(chǔ)設(shè)施的共享［1］。由于虛擬機(jī)（Virtual machine，VM）的動(dòng)態(tài)生成、重組與下線，云數(shù)據(jù)中心網(wǎng)絡(luò)資源易產(chǎn)生碎片，從而導(dǎo)致較低的資源利用率［2，3］。圖1（a）為產(chǎn)生上述資源碎片的現(xiàn)象舉例，其中服務(wù)器S1和S2承載了3個(gè)VM，且各自的總?cè)萘繛?個(gè)單位資源。VM1和VM3各占用2個(gè)單位資源，而VM2占用3個(gè)單位資源。因此在圖1（a）所示的網(wǎng)絡(luò)狀態(tài)下，若一個(gè)占用7個(gè)單位資源的VM請(qǐng)求到達(dá)，則無(wú)法被此網(wǎng)絡(luò)容納，從而產(chǎn)生資源碎片。

現(xiàn)有云數(shù)據(jù)中心網(wǎng)絡(luò)資源碎片整理方案可歸納為兩大類：基于VM請(qǐng)求到達(dá)的遷移策略，以及服務(wù)器整合策略。在第一種策略中，當(dāng)一個(gè)VM請(qǐng)求到達(dá)后，云數(shù)據(jù)中心網(wǎng)絡(luò)首先判斷自己能否容納這個(gè)VM［4，5］。若不能，它將對(duì)已存放在服務(wù)器內(nèi)的一個(gè)或多個(gè)VM進(jìn)行遷移處理，使其中的一個(gè)服務(wù)器能夠騰出空間來(lái)容納到達(dá)的VM［6］。這是個(gè)可行策略，但是，當(dāng)上百個(gè)VM需要在短時(shí)間內(nèi)置入服務(wù)器中時(shí)，云數(shù)據(jù)中心網(wǎng)絡(luò)將執(zhí)行頻繁的VM遷移，這會(huì)導(dǎo)致嚴(yán)重的服務(wù)中斷和延遲。

第二種策略是服務(wù)器整合技術(shù)，它通過(guò)減少服務(wù)器的使用數(shù)量以騰出更多空閑服務(wù)器來(lái)容納后續(xù)到達(dá)的VM［7-15］。如圖1（b）所示，將VM3遷入服務(wù)器S1后可騰空S2，從而容納即將到達(dá)的、占用7個(gè)單位資源的VM請(qǐng)求。可見，此技術(shù)可在一定程度上減少資源碎片，但騰空服務(wù)器會(huì)產(chǎn)生頻繁且無(wú)效的VM遷移，系統(tǒng)靈活性也較差。仍以圖1（a）為例，若即將到達(dá)的兩個(gè)VM請(qǐng)求分別占用5個(gè)和3個(gè)單位資源，則無(wú)需采用服務(wù)器整合，便可直接將它們放入網(wǎng)絡(luò)中。

因此，一個(gè)更加高效的云數(shù)據(jù)中心網(wǎng)絡(luò)資源碎片整理方案應(yīng)重點(diǎn)關(guān)注兩個(gè)方面的問(wèn)題：（1）何時(shí)執(zhí)行必要的碎片整理操作；（2）在碎片整理進(jìn)程中，哪些VM必須進(jìn)行遷移。針對(duì)上述兩個(gè)關(guān)注點(diǎn)，本文提出了云數(shù)據(jù)中心網(wǎng)絡(luò)中基于預(yù)測(cè)的先應(yīng)式碎片整理算法。首先，本文對(duì)上述問(wèn)題進(jìn)行數(shù)學(xué)定義，在給定網(wǎng)絡(luò)中現(xiàn)有VM集合的條件下，對(duì)后續(xù)即將到達(dá)的VM集合進(jìn)行預(yù)測(cè)，從而求出最大限度避免無(wú)效VM遷移的碎片整理方案（即最優(yōu)解）。由于此問(wèn)題是NP困難的，本文還設(shè)計(jì)了有效的啟發(fā)式方法獲取近似最優(yōu)解。

圖1 資源碎片與服務(wù)器整合技術(shù)示意圖Fig.1 Diagram of resource fragments and server consolidation

1 問(wèn)題定義

給定一個(gè)具有S個(gè)服務(wù)器的云數(shù)據(jù)中心網(wǎng)絡(luò)。其中，對(duì)于服務(wù)器j（1≤j≤S）：Oj為總?cè)萘?；Lj（Lj≤Oj）為占用資源；Fj為可用剩余資源，且Fj＝Oj-Lj。根據(jù)慣例（如 Amazon EC2），假設(shè)云數(shù)據(jù)中心網(wǎng)絡(luò)將受理C種類型VM。每個(gè)VM請(qǐng)求為一個(gè)三元組〈c，ec，rc〉。其中，c為類型索引號(hào)；ec為付費(fèi)；rc為資源需求。為便于討論，假設(shè)rc為一實(shí)數(shù)，且r1＞r2＞…＞rC。資源需求越大，付費(fèi)越高，因此有e1＞e2＞…＞eC。在特定時(shí)間點(diǎn)t，云數(shù)據(jù)中心網(wǎng)絡(luò)內(nèi)可存在先前放置的VM（即現(xiàn)有VM）、一些新到達(dá)或離開此網(wǎng)絡(luò)的VM。此外，可對(duì)特定未來(lái)時(shí)間點(diǎn)t′（t′＞t）的VM到達(dá)與離開狀態(tài)做出預(yù)測(cè)，從而在時(shí)間點(diǎn)t求解有效的VM遷移決策。一些重要的符號(hào)定義如下（以首個(gè)字母表排序）：

A為二維VM放置矩陣；C為類型總數(shù)；ec為容納一個(gè)類型-c的VM所獲得的收入；Fj為第j個(gè)服務(wù)器的可用剩余資源；Gs為存放遷出VM的服務(wù)器集合；Gt為具有可用剩余資源的服務(wù)器集合；i為VM 索引號(hào)；j為服務(wù)器索引號(hào)；lr為遷移成本系數(shù)（0＜lr＜1）；lu為服務(wù)器成本系數(shù)（0＜lu＜1）；Lj為第j個(gè)服務(wù)器的占用資源；mc為網(wǎng)絡(luò)內(nèi)現(xiàn)有類型-c的VM數(shù)；nc為在時(shí)間點(diǎn)t到達(dá)的、類型-c的VM數(shù)；n′為將在時(shí)間點(diǎn)t′到達(dá)的VM總數(shù)；n′c為將在時(shí)間點(diǎn)t′到達(dá)的、類型-c的VM數(shù)；Oj為第j個(gè)服務(wù)器的總?cè)萘?；pc（n′c）為將在時(shí)間點(diǎn)t′到達(dá)的n′c個(gè)類型-c的 VM 的概率；φc為將在時(shí)間點(diǎn)t′到達(dá)的類型-c的 VM比例，且Φ＝｛φc｝c∈［1，C］；rc為類型-c的 VM 的資源需求；S為網(wǎng)絡(luò)內(nèi)服務(wù)器總數(shù)；t為當(dāng)前時(shí)間點(diǎn)；t′為未來(lái)時(shí)間點(diǎn)；Uj為一個(gè)布爾變量，用以記錄第j個(gè)服務(wù)器是否空閑。

1.1 VM遷移的最佳放置

計(jì)算總遷移和服務(wù)器成本如下

其中，?j∈［1，S］

對(duì)現(xiàn)有VM的放置應(yīng)遵循以下約束

新到達(dá)的VM的放置以及對(duì)現(xiàn)有VM的遷移應(yīng)遵循以下約束

式（4，6）確保VM不被分割；式（7）表明采用遷移后，某些VM請(qǐng)求仍可能被阻塞；式（5，8）表明可容納的VM數(shù)受限于服務(wù)器的總?cè)萘?。則考慮VM遷移的最佳放置問(wèn)題可描述為

1.2 基于預(yù)測(cè)的先應(yīng)式碎片整理

由于遷移成本只與現(xiàn)有VM有關(guān)，仍可根據(jù)式（2）計(jì)算總遷移和服務(wù)器成本。類似地，未來(lái)到達(dá)VM的放置及對(duì)現(xiàn)有VM的遷移遵循以下約束

則基于預(yù)測(cè)的先應(yīng)式碎片整理問(wèn)題描述如下

實(shí)際上，任一時(shí)間點(diǎn)新到達(dá)VM請(qǐng)求數(shù)均是一個(gè)有限值。因此，假定可得到未來(lái)時(shí)間點(diǎn)t′新到達(dá)的VM 數(shù)預(yù)測(cè)值為n′。給定向量Φ＝｛φc｝c∈［1，C］（其中φc為在未來(lái)時(shí)間點(diǎn)t′到達(dá)的、類型-c的 VM 比例），從而有

相應(yīng)地，遵循式（6，11，12）約束，將可預(yù)測(cè)的總收入化簡(jiǎn)為

則基于預(yù)測(cè)的先應(yīng)式碎片整理問(wèn)題可描述為

2 算法描述

在時(shí)間點(diǎn)t，本文所提出的基于預(yù)測(cè)的先應(yīng)式碎片整理（Provident resource defragmentation，PRD）算法主流程描述如下：

輸入：At-＝｛At-（c）｝c∈［1，C］，Φ＝｛φc｝c∈［1，C］，n′

輸出 ：At，α，At′，β′

（1）At，α（0，0）＝At-；（At′，β′（0，0），nt）←BVF（At-，Φ，n′）

（2）If所有n′個(gè)VM均已成功放置then

（3）forc＝1，2，…，Cdo

首先，初始化n′×S空矩陣At′，β′（0，0）。隨后以類型索引號(hào)的升序?qū)?VM 進(jìn)行初始放置：對(duì)于某種類型VM，遍歷所有服務(wù)器以獲取能夠容納此類型VM的數(shù)量。

圖2 BVF子算法舉例示意圖Fig.2 Diagram of illustration of BVF sub-algorithm

如圖3所示，執(zhí)行BVF子算法后，隨著后續(xù)放入服務(wù)器中某類型VM數(shù)的增加，收入將提升。但由于遷移成本的引入，整體利潤(rùn)不一定呈線性增長(zhǎng)趨勢(shì)。因此采用MaxPD子算法為某類型VM尋求能取得最大利潤(rùn)的值。

執(zhí)行BVF子算法后，若后續(xù)容納了k（0≤k≤n′c-）個(gè)類型c的 VM，采用矩陣At，α（c，k）和At′，β′（c，k）分別記錄現(xiàn)有VM的遷移狀態(tài)，以及新到達(dá)的、類型-c的VM 分配情況。根據(jù)矩陣At，α（c，k）和At′，β′（c，k）的記錄，可分別計(jì)算出收入和成本κc，k

圖3 PRD算法舉例示意圖Fig.3 Diagram of illustration of PRD algorithm

MinCM子算法：為避免遷移的乒乓效應(yīng)，采用單向遷移技術(shù)保證遷移后的VM不再遷回原服務(wù)器，則有以下兩個(gè)引理成立。

引理2 執(zhí)行BVF子算法后，若存在未能成功放置的VM，則有?j（1≤j≤S），F(xiàn)j＜rc＊。

導(dǎo)出c＊后，初始化兩種服務(wù)器集合：（1）存放遷出VM的服務(wù)器集合Gs；（2）具有可用剩余資源的服務(wù)器集合Gt。引入遷移控制，即僅有類型-c′（c＊＜c′≤C）的VM可被遷移，從而有

如圖2（b）所示，有c＊＝1，且每個(gè)服務(wù)器的可用剩余資源均小于16。因此，Gs＝｛1，2，3，4，5，6｝，Gt＝｛2，3，6，7，8｝。

為進(jìn)一步容納一個(gè)類型-c的VM，在Gs中確定一個(gè)服務(wù)器，通過(guò)將其內(nèi)VM以最小的開銷遷移到Gt中其他服務(wù)器，以騰出更多空間。具體地，首先在Gs中確定具有最大空閑空間的服務(wù)器j＊，若j＊∈Gt，更新G′t＝Gt-｛j＊｝。其次判斷服務(wù)器j＊能否通過(guò)VM遷移后騰出空間容納一個(gè)類型-c的VM：（1）計(jì)算服務(wù)器j＊中類型-c′的 VM 數(shù)fc′（j＊），c＊＜c′≤C；（2）采用BVF方法計(jì)算G′t內(nèi)所有服務(wù)器可用剩余資源最多可容納的類型-c′的 VM 數(shù)fc′（G′t），c＊＜c′≤C；（3）確定從服務(wù)器j＊中最多能夠遷出的、類型-c′的 VM 數(shù)fc′＝min［fc′（j＊），fc′（G′t）］，c＊＜c′≤C；（4）確定能夠容納一個(gè)類型-c的 VM 的條件為

若滿足上述條件，采用首次命中（First-fit，F(xiàn)F）方法將服務(wù)器j＊中的VM遷出；否則使Gs＝Gs-｛j＊｝，進(jìn)行while循環(huán)直到Gs為空。例如，圖2（b）中可確定j＊＝6。根據(jù)上述定義可得f2（6）＝2，f3（6）＝0。由于服務(wù)器6屬于Gt，則更新G′t＝｛2，3，7，8｝，因此有f2（G′t）＝2，f3（G′t）＝4。顯然，f2＝2且f3＝0。由于F6＋f2·r2＝8＋8×2＝24＞r1＝16，從而將一個(gè)類型-2的VM從服務(wù)器6遷移到服務(wù)器7后，將一個(gè)類型-1的VM放入服務(wù)器6中，如圖2（b）所示。采用類似方法，可確定j＊＝2，并通過(guò)將一個(gè)類型-2的VM從服務(wù)器2遷移到服務(wù)器8，同時(shí)將一個(gè)類型-3的VM從服務(wù)器2遷移到服務(wù)器3，進(jìn)一步將一個(gè)類型-1的VM放入服務(wù)器2中，如圖2（c）所示。

PRD算法時(shí)間復(fù)雜度主要取決于運(yùn)行FF方法的次數(shù)，而每運(yùn)行一次FF方法的時(shí)間復(fù)雜度為C2·S。在MinCM子算法中最多調(diào)用S次FF方法，而在主算法中最多調(diào)用n′次MinCM子算法，因此，PRD算法時(shí)間復(fù)雜度約為O（n′·C2·S2）。

3 仿真實(shí)現(xiàn)與性能分析

采用異構(gòu)云數(shù)據(jù)中心網(wǎng)絡(luò)，即服務(wù)器總?cè)萘靠蓮模?0，60，80｝中隨機(jī)選取。引入時(shí)間軸，該軸被等分為24個(gè)時(shí)隙。VM請(qǐng)求在某一時(shí)隙的起始端到達(dá)，且服務(wù)持續(xù)時(shí)間占用時(shí)隙數(shù)滿足均勻整數(shù)分布［1，4］。網(wǎng)絡(luò)內(nèi)存在C＝3種類型 VM：r1＝16，r2＝8，r3＝2且ec＝rc，c＝1，2，3。給定Φ＝｛0.2，0.5，0.3｝和以下仿真場(chǎng)景。

場(chǎng)景1S＝35，lr＝0.01，預(yù)測(cè)未來(lái)到達(dá)VM請(qǐng)求數(shù)采用均值n，依次取為｛150，200，250，300，350｝，且n′＝（即預(yù)測(cè)精確度為100%）。

場(chǎng)景2S∈｛35，40，45，50，55｝，lr＝0.01，均值從150增長(zhǎng)到300，即每5個(gè)時(shí)隙后n增長(zhǎng)50，但n′＝230（即存在預(yù)測(cè)誤差）。

總利潤(rùn)（Total profit，TP）：每個(gè)時(shí)隙產(chǎn)生的利潤(rùn)為相應(yīng)收入與遷移成本之差，總利潤(rùn)為20個(gè)時(shí)隙產(chǎn)生利潤(rùn)總和；平均遷移成本（Average migration cost，AMC）為20個(gè)時(shí)隙產(chǎn)生的總遷移成本與執(zhí)行碎片整理操作的次數(shù)之比。

表1，2分別顯示在場(chǎng)景1和2下可為固定周期的服務(wù)器整合方法找到最佳周期T，使相應(yīng)總利潤(rùn)最大（最大利潤(rùn)為表中粗體數(shù)據(jù)）。在場(chǎng)景2下，各方法的總利潤(rùn)隨著服務(wù)器數(shù)量的增加而升高。同時(shí)，所提PRD算法的總利潤(rùn)高于未采用碎片整理的普通VM放置方法和固定周期的服務(wù)器整合方法，即使在預(yù)測(cè)精度較低情況下，PRD總利潤(rùn)同樣接近于總利潤(rùn)最優(yōu)值，偏差率僅為6%。

表1 場(chǎng)景1下的總利潤(rùn)比較結(jié)果Table 1 Comparative results of TP under scenario 1

表2 場(chǎng)景2下的總利潤(rùn)比較結(jié)果Table 2 Comparative results of TP under scenario 2

本文假設(shè)網(wǎng)絡(luò)內(nèi)服務(wù)器可用資源可整合成連續(xù)的、無(wú)碎片的資源池，即可得到總利潤(rùn)最優(yōu)值。

圖4（a，b）分別顯示在場(chǎng)景1，2下PRD算法有效地降低了平均遷移成本，且PRD平均遷移成本不會(huì)隨著VM請(qǐng)求數(shù)和服務(wù)器數(shù)量的增加而發(fā)生明顯變化。采用固定周期的服務(wù)器整合方法所產(chǎn)生的遷移成本會(huì)隨著服務(wù)器數(shù)量的增加而線性增長(zhǎng)，這意味著PRD算法更加靈活，且適用于大規(guī)模的云數(shù)據(jù)中心網(wǎng)絡(luò)。

4 結(jié)束語(yǔ)

虛擬機(jī)的動(dòng)態(tài)創(chuàng)建和下線會(huì)使云數(shù)據(jù)中心網(wǎng)絡(luò)內(nèi)產(chǎn)生大量的資源碎片，本文給出了針對(duì)云數(shù)據(jù)中心網(wǎng)絡(luò)資源碎片整理的系統(tǒng)闡述和分析。首先提出了在某一時(shí)段最小化無(wú)效VM遷移成本的優(yōu)化問(wèn)題，并對(duì)其進(jìn)行數(shù)學(xué)定義。隨后設(shè)計(jì)了啟發(fā)式算法獲取上述問(wèn)題的近似最優(yōu)解，并通過(guò)仿真結(jié)果驗(yàn)證了所提算法的優(yōu)越性。本文所設(shè)計(jì)的算法只考慮了單一維度的計(jì)算資源。因此在未來(lái)的研究工作中，將重點(diǎn)考慮設(shè)計(jì)面向多維度計(jì)算資源的碎片整理算法。此外，多維度資源（如計(jì)算、內(nèi)存、存儲(chǔ)、帶寬以及I／O等）之間的相關(guān)性也將是未來(lái)設(shè)計(jì)碎片整理算法所要考慮的重要方面。

［1］ Armbrust M，F(xiàn)ox A，Grif?th R，et al.A view of cloud computing［J］.Commun ACM，2010，53（4）：50-58.

［2］ Sridharan M，Calyam P，Venkataraman A，et al.Defragmentation of resources in virtual desktop clouds for cost-aware utility optimal allocation［C］∥Proceedings of IEEE International Conference on Utility and Cloud Computing.Los Alamitos：IEEE Computer Society Press，2011：253-260.

［3］ He S，Guo L，Guo Y.Real time elastic cloud management for limited resources［C］∥Proceedings of IEEE International Conference on Cloud Computing.Los Alamitos：IEEE Computer Society Press，2011：622-629.

［4］ Mishra M，Sahoo A.On theory of VM placement：Anomalies in existing methodologies and their mitigation using a novel vector based approach［C］∥Proceedings of IEEE International Conference on Cloud Computing.Los Alamitos：IEEE Computer Society Press，2011：275-282.

［5］ He S，Guo L，Ghanem M，et al.Improving resource utilisation in the cloud environment using multivariate probabilistic models［C］∥Proceedings of IEEE International Conference on Cloud Computing.Los Alamitos：IEEE Computer Society Press，2012：574-581.

［6］ Calcavecchia N，Biran O，Hadad E，et al.VM placement strategies for cloud scenarios［C］∥Proceedings of IEEE International Conference on Cloud Computing.Los Alamitos：IEEE Computer Society Press，2012：852-859.

［7］ Khanna G，Beaty K，Kar G，et al.Application performance management in virtualized server environments［C］∥Proceedings of Network Operations and Management Symposium.Piscataway：IEEE，2006：373-381.

［8］ Bobroff N，Kochut A，Beaty K.Dynamic placement of virtual machines for managing SLA violations［C］∥Proceedings of International Symposium on Integrated Network Management.Piscataway：IEEE，2007：119-128.

［9］ Speitkamp B，Bichler M.A mathematical programming approach for server consolidation problems in virtualized data centers［J］.IEEE Transactions on Services Computing，2010，3（4）：266-278.

［10］Wang M，Meng X，Zhang L.Consolidating virtual machines with dynamic bandwidth demand in data centers［C］∥Proceedings of IEEE INFOCOM.Los Alamitos：IEEE Computer Society Press，2011：71-75.

［11］Wood T，Shenoy P，Venkataramani A，et al.Black-box and gray-box strategies for virtual machine migration［C］∥Proceedings of the 4th USENIX conference on Networked systems design implementation.Piscataway：IEEE，2007：17-17.

［12］Xu L，Chen W，Wang Z，et al.Smart-DRS：A strategy of dynamic resource scheduling in cloud data center［C］∥Proceedings of International Conference on Cluster Computing Workshops.Piscataway：IEEE，2012：120-127.

［13］Beloglazov A，Buyya R.Managing overloaded hosts for dynamic consolidation of virtual machines in cloud data centers under quality of service constraints［J］.IEEE Transactions on Parallel and Distributed Systems，2013，24（7）：1366-1379.

［14］Deng W，Liu F，Jin H，et al.Lifetime or energy：Consolidating servers with reliability control in virtualized cloud datacenters［C］∥Proceedings of International Conference on Cloud Computing Technology and Science.Los Alamitos：IEEE Computer Society Press，2012：18-25.

［15］Feller E，Morin C，Esnault A.A case for fully decentralized dynamic vm consolidation in clouds［C］∥Proceedings of International Conference on Cloud Computing Technology and Science.Los Alamitos：IEEE Computer Society Press，2012：26-33.