郭 磊 侯維剛

（東北大學信息科學與工程學院，沈陽，110819）

引 言

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

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

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

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

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

1 問題定義

給定一個具有S個服務(wù)器的云數(shù)據(jù)中心網(wǎng)絡(luò)。其中，對于服務(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。每個VM請求為一個三元組〈c，ec，rc〉。其中，c為類型索引號；ec為付費；rc為資源需求。為便于討論，假設(shè)rc為一實數(shù)，且r1＞r2＞…＞rC。資源需求越大，付費越高，因此有e1＞e2＞…＞eC。在特定時間點t，云數(shù)據(jù)中心網(wǎng)絡(luò)內(nèi)可存在先前放置的VM（即現(xiàn)有VM）、一些新到達或離開此網(wǎng)絡(luò)的VM。此外，可對特定未來時間點t′（t′＞t）的VM到達與離開狀態(tài)做出預測，從而在時間點t求解有效的VM遷移決策。一些重要的符號定義如下（以首個字母表排序）：

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

1.1 VM遷移的最佳放置

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

其中，?j∈［1，S］

對現(xiàn)有VM的放置應遵循以下約束

新到達的VM的放置以及對現(xiàn)有VM的遷移應遵循以下約束

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

1.2 基于預測的先應式碎片整理

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

則基于預測的先應式碎片整理問題描述如下

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

相應地，遵循式（6，11，12）約束，將可預測的總收入化簡為

則基于預測的先應式碎片整理問題可描述為

2 算法描述

在時間點t，本文所提出的基于預測的先應式碎片整理（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′個VM均已成功放置then

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

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

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

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

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

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

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

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

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

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

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

若滿足上述條件，采用首次命中（First-fit，F(xiàn)F）方法將服務(wù)器j＊中的VM遷出；否則使Gs＝Gs-｛j＊｝，進行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，從而將一個類型-2的VM從服務(wù)器6遷移到服務(wù)器7后，將一個類型-1的VM放入服務(wù)器6中，如圖2（b）所示。采用類似方法，可確定j＊＝2，并通過將一個類型-2的VM從服務(wù)器2遷移到服務(wù)器8，同時將一個類型-3的VM從服務(wù)器2遷移到服務(wù)器3，進一步將一個類型-1的VM放入服務(wù)器2中，如圖2（c）所示。

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

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

采用異構(gòu)云數(shù)據(jù)中心網(wǎng)絡(luò)，即服務(wù)器總?cè)萘靠蓮模?0，60，80｝中隨機選取。引入時間軸，該軸被等分為24個時隙。VM請求在某一時隙的起始端到達，且服務(wù)持續(xù)時間占用時隙數(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｝和以下仿真場景。

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

場景2S∈｛35，40，45，50，55｝，lr＝0.01，均值從150增長到300，即每5個時隙后n增長50，但n′＝230（即存在預測誤差）。

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

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

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

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

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

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

4 結(jié)束語

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

［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.