董健康，王洪波，李陽陽，程時端

（北京郵電大學 網(wǎng)絡與交換技術國家重點實驗室，北京 100876）

1 引言

云計算數(shù)據(jù)中心大多采用虛擬化技術，租客訂購一組相互之間通信、放置在不同主機上的虛擬機，并與云提供者簽訂 SLA(service level agreement)。每個虛擬機需要一定數(shù)量的資源，如CPU、內(nèi)存、磁盤、帶寬等，能維護應用之間的性能隔離和安全。同時，虛擬化技術可在同一臺物理機上運行多臺虛擬服務器[1]，提供資源整合和復用，有利于提高資源利用率并節(jié)約設備能耗。這樣，虛擬化技術也可以幫助管理者實現(xiàn)資源的有序、按需調(diào)配，為云計算的資源靈活管理和綠色節(jié)能提供了一種有效的解決辦法。

對于采用虛擬化技術的公共云(public cloud)而言，其提供的主要服務之一是基礎設施即服務(IaaS,infrastructure as a service)，像 Amazon EC2[2]。在 IaaS中，租客向云提供者付費租用所需的虛擬機資源。云提供者按照租客所提出的虛擬機需求，遵守雙方簽訂的SLA，利用虛擬機在物理機上的靈活放置，優(yōu)化數(shù)據(jù)中心的資源配置。由于不同的虛擬機與物理機的映射關系會帶來不同的資源利用率，就云提供者來說，需要關心的一個主要問題是:租客申請的多個虛擬機在云提供者的物理服務器上如何放置，既可以滿足應用的性能要求，又能提高資源利用率和減少能源消耗，從而減少數(shù)據(jù)中心的運營和管理成本。把此類問題定義為虛擬機放置問題，這是當前云計算研究中的熱點問題。

對于虛擬機放置問題，一個主要的研究方向是通過資源的整合，最小化激活物理設備(物理服務器、交換機、鏈路等)的數(shù)目，使空閑設備處于休眠狀態(tài)，從而減少能源消耗。其中，一些研究工作[3~6]利用虛擬機放置，提高物理服務器的利用率，減少應用服務主機的數(shù)目，從而減少能源的消耗。但這些研究較少考慮網(wǎng)絡資源的優(yōu)化，并沒有考慮網(wǎng)絡拓撲和當前網(wǎng)絡流量的影響，而網(wǎng)絡資源是數(shù)據(jù)中心的稀缺資源，直接影響到應用的性能[7]；另一些研究[8~10]利用虛擬機放置來提高網(wǎng)絡設備的利用率，結合路由的優(yōu)化，減少網(wǎng)絡設備的數(shù)目，以此優(yōu)化網(wǎng)絡能源效率。但是，不論是優(yōu)化物理服務器能源效率，還是優(yōu)化網(wǎng)絡設備的能源效率，都會帶來資源的過度聚合，會影響應用的性能，提高了SLA的違反率。特別是網(wǎng)絡流量的聚集，會造成鏈路熱點，帶來網(wǎng)絡擁塞問題。

有鑒于此，云提供者要考慮優(yōu)化物理服務器和網(wǎng)路設備的能耗，整合虛擬機到更少的物理機上，關閉空閑物理機；優(yōu)化網(wǎng)絡總流量，減少流量所用網(wǎng)絡設備（如交換機、鏈路等）的數(shù)目，節(jié)約網(wǎng)絡設備能源；也要考慮資源過度聚合帶來的網(wǎng)絡擁塞問題。使得能源效率與網(wǎng)絡性能達到平衡，在盡量滿足應用的SLA的條件下，最小化能源消耗。

本文提出了一種多資源條件約束的虛擬機放置方案。在滿足物理機多個資源（CPU、Memory等）和網(wǎng)絡鏈路容量約束的情況下，通過對放置在物理機上的虛擬機進行交叉優(yōu)化放置，在盡可能避免網(wǎng)絡擁塞的前提下，優(yōu)化物理服務器和網(wǎng)絡設備的能耗，使得空閑的資源處于休眠狀態(tài)，最小化激活物理服務器和網(wǎng)絡設備的數(shù)目，從而減少數(shù)據(jù)中心的能源代價。

虛擬機放置對于物理機能源的優(yōu)化可以抽象為裝箱問題[11]，最小化激活的物理服務器數(shù)目。而對于網(wǎng)絡資源的優(yōu)化，主要利用網(wǎng)絡拓撲和當前的網(wǎng)絡流量，可以把這一問題抽象為二次分配問題[12]，最小化網(wǎng)絡中的總流量，網(wǎng)絡中總的通信流量較小，所激活的網(wǎng)絡設備的數(shù)目也較少。同時最小化最大鏈路利用率，避免網(wǎng)絡擁塞發(fā)生，保證網(wǎng)絡性能。既要減少激活物理機和網(wǎng)絡設備的數(shù)目，來降低數(shù)據(jù)中心的能源消耗，又要保證應用性能，避免網(wǎng)絡擁塞。這是一個經(jīng)典的多目標優(yōu)化問題[13]。而裝箱問題和二次分配問題是NP難問題，本文設計了一種新的二階段啟發(fā)式算法求解多目標優(yōu)化問題。第一階段，最小割的層次聚類算法與BF(best fit)算法相結合。利用層次聚類算法，用最小割算法把流量相關的虛擬機聚類在一起，使得流量大的虛擬機放置在同一個物理機上或同一個接入交換機下，來減少網(wǎng)絡中的流量。然后，根據(jù)聚類結果，利用BF放置算法來最小化激活物理機數(shù)目。第二階段，利用局部搜索算法再次優(yōu)化虛擬機位置，目的是最小化最大鏈路利用率，從而使得數(shù)據(jù)中心網(wǎng)絡流量分布均衡，減少擁塞鏈路的產(chǎn)生。算法要能適應物理機與虛擬機大小異構的情況。仿真實驗表明，與BFD(best fit decreasing)算法、隨機放置算法相比，取得了良好的效果。

2 相關工作

對于減少能耗的虛擬機放置問題的研究主要集中在2類。一類是降低物理服務器能耗[3~6]。文獻[3]在虛擬化系統(tǒng)中，動態(tài)調(diào)整應用在服務器的位置對能源的影響，考慮應用的遷移成本并能預計出遷移后的能源消耗，使用一種簡單的算法證明了通過動態(tài)遷移技術可以實現(xiàn)數(shù)據(jù)中心能耗成本的節(jié)省。文獻[4]采用負載預測技術，在最小化激活物理機的同時不影響應用性能。文獻[5]是按照用戶設置 max、min、share等虛擬機設置參數(shù)提供一種新的物理機資源分配方法，整合多個虛擬機到物理機，使得被放置物理機的資源利用率高，并且使得物理機的能耗較低。但是，該文只考慮CPU資源進行優(yōu)化，而沒有考慮其他資源的優(yōu)化。文獻[6]是把虛擬機帶寬到物理機帶寬整合問題看成 NP難的隨機裝箱問題，它表明一定尺寸的虛擬機以某種概率分布放置在相應的物理機上，而優(yōu)化目標是物理機數(shù)量最小。這些研究只考慮優(yōu)化物理服務器的能耗，而較少考慮數(shù)據(jù)中心其他資源的優(yōu)化。

另一類是降低網(wǎng)絡設備的能耗[8,9]，文獻[8]通過虛擬機遷移技術和網(wǎng)絡路由的優(yōu)化來減少數(shù)據(jù)中心網(wǎng)絡能源消耗，從而節(jié)約數(shù)據(jù)中心電源損耗。文獻[9]同時優(yōu)化虛擬機位置和流量路由以盡可能多地關閉空閑網(wǎng)絡設備來節(jié)省數(shù)據(jù)中心網(wǎng)絡能耗。這2個方案只假設滿足物理服務器的資源需求，優(yōu)化了數(shù)據(jù)中心網(wǎng)絡資源，沒有優(yōu)化物理服務器能耗。

當前，也有一些研究[10,14~17]利用虛擬機放置技術優(yōu)化應用性能。文獻[10]用流量相關的虛擬機位置來改善數(shù)據(jù)中心網(wǎng)絡的擴展性，通過優(yōu)化虛擬機在物理主機的位置，使虛擬機的流量與它們的網(wǎng)絡物理距離相關，通信流量大的虛擬機對可以放置在距離相近的2個物理主機上，從而減少數(shù)據(jù)中心網(wǎng)絡的總體流量。文獻[17]考慮了最小化所有服務器與終端之間的網(wǎng)絡總負載，提出了一個基于虛擬機遷移的在線算法。文獻[10, 17]都沒有考慮云數(shù)據(jù)中心的能源優(yōu)化。文獻[14]利用虛擬機放置致力于提高物理節(jié)點的利用率，同時通過調(diào)整流量路由優(yōu)化網(wǎng)絡鏈路利用率。但是它們沒有考慮優(yōu)化數(shù)據(jù)中心網(wǎng)絡設備的能耗。文獻[15]提出了一個應用相關的虛擬機分配方案，在滿足SLA需求的條件下，改善硬件資源的利用率，但沒有考慮網(wǎng)絡流量的優(yōu)化。文獻[16]提出了一個新的虛擬機動態(tài)整合自適應啟發(fā)式算法，盡管這個算法在確保SLA不被違反的前提下減少了物理機的能耗，但沒有考慮網(wǎng)絡性能的優(yōu)化。本文的方案是在保證網(wǎng)絡性能的前提下，減少數(shù)據(jù)中心的物理機和網(wǎng)絡設備的能耗。

3 建模

在當前的云計算中，按需分配資源是云計算的主要特征，虛擬化是實現(xiàn)這一特征的主要技術，而IaaS是云計算主要的應用之一。云提供者給租客提供虛擬機，對于租客而言，最關鍵的一個服務就是租用虛擬機要滿足QoS(quality of service)的需求和應用的性能保障。對于云提供者而言，如何設計虛擬機放置方案來提高資源利用率并能改善網(wǎng)絡性能是一個重要問題。

現(xiàn)在，虛擬機放置研究主要在能源節(jié)省、故障容忍、QoS管理等方面，也大多集中在服務器資源的優(yōu)化，沒有考慮網(wǎng)絡拓撲和當前網(wǎng)絡流量的影響，而網(wǎng)絡資源是數(shù)據(jù)中心的稀缺資源，直接影響到應用的性能。而虛擬機放置可以改變虛擬機的位置，即改變其所屬的物理服務器，從而改變流量的發(fā)送端和接收端，以達到控制和優(yōu)化數(shù)據(jù)中心網(wǎng)絡流量的目的。本文的虛擬機放置方案主要集中在下面2個方面。

1) 能源優(yōu)化。這里的能耗主要包括兩部分：物理服務器和網(wǎng)絡設備。通過虛擬機與物理機的不同映射關系最小化激活物理機和網(wǎng)絡設備的個數(shù)，關閉或休眠空閑的物理設備，減少數(shù)據(jù)中心的能源消耗。

2) 網(wǎng)絡性能優(yōu)化：通過改變數(shù)據(jù)中心虛擬機的位置，從而改變了虛擬機之間的流量路徑，最小化網(wǎng)絡最大鏈路利用率，達到改善網(wǎng)絡性能的目的。

本文的虛擬機放置問題是：從云提供者的角度，根據(jù)不同租客的資源需求，在不違反SLA的前提下，也就是說，在保證網(wǎng)絡性能的前提下，設計一種虛擬機放置策略，提高資源池中的資源利用率，減少激活物理機和網(wǎng)絡設備的數(shù)量。這樣就降低了云計算數(shù)據(jù)中心的硬件投入和能源消耗，且減少了數(shù)據(jù)中心的運營成本。

3.1 數(shù)據(jù)中心能源優(yōu)化

3.1.1 能源模型

建模數(shù)據(jù)中心的能耗主要由以下三部分組成：物理機能耗、網(wǎng)絡設備能耗、其他能耗。在式(1)中，物理機能耗serE 主要由CPU、內(nèi)存、存儲和網(wǎng)絡接口等組成，網(wǎng)絡設備能耗netE 主要包括交換機、鏈路等。其他能耗otherE 主要包括制冷、濕度控制、照明等，像制冷涉及到數(shù)據(jù)中心規(guī)模、室外溫度、周邊環(huán)境、制冷技術（風能、水能）等多種因素。筆者的目的在于利用虛擬機以及網(wǎng)絡流量的整合改進能源效率，關閉/休眠空閑的物理機和網(wǎng)絡設備來節(jié)約能耗。本文聚焦于物理機和網(wǎng)絡設備的能耗，暫不考慮其他能耗。當數(shù)據(jù)中心物理設備能耗下降時，伴隨著發(fā)熱量的下降，相應地也會減少冷卻的能耗，有利于其他能耗的降低。本節(jié)主要符號定義及其意義如表1所示。

表1 主要的符號定義及其意義

3.1.2 物理機能耗優(yōu)化

對物理機能耗的優(yōu)化抽象為多維資源約束的裝箱問題。目的是最小化活動物理服務器的數(shù)目。

其中， N 表示物理機m上的虛擬機個數(shù)。 Emser表示物理機 m 的能耗。式(2-2)表示放置在同一臺物理機上的多個虛擬機資源容量總和小于物理機容量。式(2-3)表示任一虛擬機只能放置在一臺物理機上。

物理機能耗 Emser與其承載的虛擬機數(shù)量、虛擬機的負載情況等均有關系。而物理機所承載的虛擬機數(shù)量、虛擬機的負載情況都會歸結到對物理機負載的影響。所承載的虛擬機數(shù)量多，虛擬機本身的負載大，物理機的負載就大。采用式(3)和式(4)來建模物理機能耗 Em。在式(3)中，Psermax是物理機滿負載的最大功耗，k的一般取值為0.7，也就是說，空閑物理機的功耗達到最大功耗的70%左右。這說明物理機在空負載的情況下，如果不關閉或休眠物理機，物理機的能耗還是很大的。u是資源利用率，由于現(xiàn)在的物理服務器只有CPU采用DVFS (dynamic voltage and frequency scaling)技術，而其他部件并沒有采用這項技術，所以u主要是指CPU利用率。在這里利用率u與功耗采用線性關系。

3.1.3 網(wǎng)絡設備能耗優(yōu)化

對于網(wǎng)絡資源的優(yōu)化，目標是最小化數(shù)據(jù)中心的通信總流量，通信總流量的最小化如式(5)所示，把此問題抽象為二次分配問題。利用虛擬機放置，把相互之間流量大的虛擬機盡量整合到同一個物理機上，或放在同一個網(wǎng)絡交換機下。對于數(shù)據(jù)中心的對分帶寬拓撲，通信總流量小，那么所需活動的網(wǎng)絡設備（交換機、鏈路等）的數(shù)目就會減少。使得空閑的網(wǎng)絡設備處于休眠狀態(tài)，從而降低能源的開銷。采用這種方案，既可以節(jié)省網(wǎng)絡設備的能源，也可以節(jié)省網(wǎng)絡帶寬。

其中， Esiwi表示交換機 i的能耗， Nswi表示活動交換機的數(shù)目， Ei表示鏈路i的功耗， Nlinklink表示活動鏈路的數(shù)目。Nswi和 Nlink的計算，利用Elastictree方案提出的背包算法[18]，對于每條流，用貪婪背包算法選擇一個滿足容量的靠左鏈路。在數(shù)據(jù)中心層次化拓撲中，每一層的路徑選擇采用從左至右，而不是采用平均分配流的隨機選擇策略。當所有的流都被分配后，算法返回一個有流量經(jīng)過的網(wǎng)絡設備子集，而沒有流量經(jīng)過的網(wǎng)絡設備可以處于休眠狀態(tài)或關閉。通過虛擬機放置技術和流路徑的結合，使得流量使用較少的網(wǎng)絡設備。

3.2 網(wǎng)絡性能優(yōu)化

從流量工程的角度來看，最小化最大鏈路利用率是網(wǎng)絡性能優(yōu)化的主要目標。 fi,j表示分配到鏈

s,t路(s, t)上虛擬機對(i, j)的流量， Cs,t表示鏈路(s, t)的容量。

網(wǎng)絡鏈路利用率可用 ls,t表示為

要使得,stl盡可能小，問題可表示為

3.3 總體目標

本文的總體目標是最小化能耗以及最小化最大鏈路率，可形式化為

其中，r是正常數(shù)，g是能耗與最大鏈路利用率的加權和。這是經(jīng)典的多目標優(yōu)化問題。

4 算法

對于多目標優(yōu)化和NP難問題，一般求解采用啟發(fā)式智能算法，如遺傳算法、蟻群算法等，但此類算法存在算法時間性能較差、結果不穩(wěn)定等問題，本文設計了一種新的兩階段啟發(fā)式算法求解多目標優(yōu)化問題，首先，在虛擬機放置過程中，在不發(fā)生網(wǎng)絡擁塞的情況下，以優(yōu)化能耗為主。提出了一種基于最小割的層次聚類算法與BF算法相結合來求解多目標優(yōu)化問題。進行層次聚類算法，用最小割算法把相關的虛擬機聚類在一起，最小化網(wǎng)絡中的總流量；根據(jù)聚類結果，利用BF放置算法來減少物理機的能源消耗。其次，在虛擬機放置過程中，如果有網(wǎng)絡擁塞，采用最小化網(wǎng)絡最大鏈路率，以優(yōu)化性能為主?；据斎霝椋壕W(wǎng)路拓撲、鏈路容量、流量路由、虛擬機之間流量需求、虛擬機需求向量組和物理機向量組?；镜妮敵鰹椋禾摂M機在物理機上的映射關系。

4.1 基于最小割的層次聚類算法

現(xiàn)在數(shù)據(jù)中心大多是三層體系結構[7]，考慮數(shù)據(jù)中心網(wǎng)絡拓撲特征和當前的虛擬機之間的網(wǎng)絡流量，把流量大的虛擬機對盡可能放置在同一個物理機上或同一個交換機下，來減少網(wǎng)絡中的流量總量。這樣保證了應用的性能，也減少了流量所用網(wǎng)絡設備的個數(shù)。建模網(wǎng)絡流量的優(yōu)化為二次分配問題。這里，可以考慮采用基于虛擬機流量的層次聚類算法來解決二次分配問題。建模圖G=(V,E)，其中，V是虛擬機的集合，E是虛擬機之間的流量，利用圖G的最小割算法來實現(xiàn)層次聚類。圖是一無向圖，給定節(jié)點集合，而δ(Q)表示邊的集合，這些邊的一個頂點在集合Q中，另一個頂點屬于VQ。當或中的邊就組成一個割集，表示為

如圖 1所示，把圖 G最小割的結果用二叉樹T(V)表示，建一個二叉樹T(V)，左子樹TL為Q里的節(jié)點，權重為Q中邊值的和右子樹TR為V/Q的節(jié)點，權重為V/Q中邊值的總和，，如果 W(TL)

圖1 基于最小割的層次聚類算法

圖2 基于最小割的層次聚類算法

4.2 基于BF的虛擬機放置算法

對于MC-BF得到的BT(V)，先序遍歷樹中的所有葉子節(jié)點放在向量VMlist里，VMlist里節(jié)點就是要放置的所有虛擬機節(jié)點，從前面的論述中可以看出：1) 在VMlist里，排在前面的節(jié)點一般是流量較大的虛擬機；2) 在VMlist里，每個節(jié)點(虛擬機)的前后鄰居就是跟它通信流量的虛擬機，與當前節(jié)點的位置距離越遠，說明它們之間的通信流量越小。

如圖3所示，把VMlist里大小不一的虛擬機節(jié)點放置到對應的物理機上，采用最佳適應算法。從VMlist中按序開始依次放置虛擬機。當放置某個新到來的虛擬機時，從已使用的第一臺物理機開始依次搜索，找到一臺與虛擬機大小最匹配的物理機進行放置，只有當所有的物理機都不能容納這個虛擬機時，啟用一臺新的物理機。將這個算法稱為結合流量層次聚類的最佳適應（BF-HC）算法。算法描述如圖4所示。

圖4 結合流量層次聚類的最佳適應算法

4.3 局部搜索算法

如當前網(wǎng)絡不發(fā)生擁塞，只采用BF-HC算法優(yōu)化云計算數(shù)據(jù)中心的資源能耗。當網(wǎng)絡出現(xiàn)熱點鏈路時，在BF-HC算法的基礎上，則只采用局部搜索算法優(yōu)化鏈路利用率，避免擁塞的出現(xiàn)。本文稱這個算法為BF-HC-LS算法，算法描述如圖5所示。選擇產(chǎn)生擁塞鏈路的流量最大的虛擬機，隨機與左右鄰居交換機下的虛擬機交換，計算目標函數(shù)：最大鏈路利用率或熱點鏈路數(shù)目。如果目標函數(shù)值減小，則接受此次交換，如沒有減少，也可按一定概率接受。依次重復，直至循環(huán)到設定的迭代次數(shù)結束。

圖5 局部搜索優(yōu)化最大鏈路利用率

圖3 基于BF的虛擬機放置算法

4.4 算法分析

上述的虛擬機放置問題把對物理機能源資源的優(yōu)化抽象為裝箱問題，把物理機抽象為箱子，虛擬機抽象為物品。對于大小不一的虛擬機映射到大小不同的物理機上，使得所需物理機的個數(shù)最少。另外，在虛擬機放置過程中，要考慮CPU、內(nèi)存、存儲、接入帶寬、輸出帶寬等各個類型資源的約束，因此，把此類問題抽象為多資源約束的裝箱問題。眾所周知，裝箱問題是NP難問題[11]。它的時間復雜度為 O (nn)，進一步地，考慮網(wǎng)絡拓撲和當前的網(wǎng)絡流量，進行網(wǎng)絡資源的優(yōu)化，虛擬機放置問題可以抽象為二次分配問題，最小化網(wǎng)絡通信流量，使得流量通過網(wǎng)絡設備的數(shù)量減少優(yōu)化網(wǎng)絡資源能源。二次分配問題也是NP難問題[12]。它的時間復雜度為 O (nn)。把數(shù)據(jù)中心能耗優(yōu)化問題抽象為裝箱問題和二次分配問題的結合。而對網(wǎng)絡性能的改進，利用最小化最大鏈路利用率實現(xiàn)，從流量工程的角度來看，這也是NP難問題。這個問題是經(jīng)典的多目標組合優(yōu)化問題，而求解此類問題的難點是如何降低時間復雜度和如何使得結果更接近最優(yōu)解。本文設計兩階段貪婪算法求解此問題，較好地解決了這兩者之間的平衡。

基于最小割的層次聚類算法的時間復雜度為O(n3)，基于BF的虛擬機放置算法的時間復雜度為O(n2)，解決虛擬機放置算法的總體時間復雜度為O(n3)。

5 實驗仿真及結果分析

本文用C++開發(fā)了BF-HC算法、BF-HC-LS算法的仿真程序，解決裝箱問題的最常見近似算法有NFD(next fit decreasing)算法、FFD(first fit decreasing)算法、BFD 算法等[19]。因為 BF-HC和BF-HC-LS算法是按照流量聚集之后，采用最佳適應（BF）的放置方法，所以選取與同樣采用按虛擬機大小排序BF放置的BFD算法進行比較。另外，再選取流量分布較為平均的隨機算法進行比較。

數(shù)據(jù)中心采用層次化拓撲結構，如多根樹[7]、VL2[20]、Fat-tree[21]等，本文選用當前數(shù)據(jù)中心中最常見的樹型拓撲，以及將來數(shù)據(jù)中心可能用到的Fat-tree拓撲。

仿真的基本輸入主要包括三部分：虛擬機資源向量組、物理機資源向量組、虛擬機之間的流量矩陣。對于虛擬機資源向量組，Amazon EC2[22]提供了靈活的選擇不同虛擬機的實例大小來滿足不同的應用需求，參考選取Amazon EC2所提出的虛擬機大小和配置。對于虛擬機流量矩陣，本文的實驗參照文獻[10,23]的流量模式。通過它們的測量和估算，流量在較長的間隔期間內(nèi)是相對穩(wěn)定的。

能耗的計算方法基于式(1)。由于虛擬機整合，激活的物理機大多利用率較高，運行在高負載的情況下。為了便于計算和實驗，把物理機能耗參數(shù)簡化為高負載的功耗。網(wǎng)絡設備的功耗也采用同樣的處理方式。對于物理機和網(wǎng)絡設備的具體功耗參數(shù)，可以根據(jù)設備的功耗說明來確定。在本實驗中，物理機的功耗為750 W。每個交換機的功耗有80 W。網(wǎng)絡帶寬的容量為1 000 M，交換機為三層交換機。

5.1 無網(wǎng)絡擁塞情況

如果網(wǎng)絡中無擁塞發(fā)生，本文的方案主要考慮以優(yōu)化能耗為主，運行 BF-HC算法減少數(shù)據(jù)中心的能耗，沒必要運行BF-HC-LS算法。仿真實驗根據(jù)數(shù)據(jù)中心作業(yè)所對應虛擬機數(shù)目的規(guī)模不同，選取了100、200、300個虛擬機各為一組實例，它們有不同的 CPU大小、內(nèi)存容量、磁盤空間、帶寬等，在給定的一批物理機資源大小相同的情況下，對這3批虛擬機需求分別在Tree拓撲、Fat-tree拓撲下用各類算法計算數(shù)據(jù)中心能耗和網(wǎng)絡最大鏈路利用率。

在Fat-tree拓撲下，圖6顯示了BF-HC 算法、BFD算法以及隨機算法對數(shù)據(jù)中心能耗的比較結果，可以看出不同的虛擬機與物理機的映射關系對數(shù)據(jù)中心的能耗影響是不一樣的。由于隨機算法所需的激活物理機數(shù)目和網(wǎng)絡設備數(shù)目都比較多，所以數(shù)據(jù)中心能源消耗是最大的。BF-HC算法所消耗的能源是最少的，BFD算法次之。這里，BF-HC算法與 BFD算法所需的物理機個數(shù)是差不多的。BF-HC算法的能耗之所以優(yōu)于 BFD算法，在于BF-HC算法對于網(wǎng)絡總流量的優(yōu)化使得其所需的激活網(wǎng)絡設備的數(shù)目較少。圖 7列出了在 Fat-tree拓撲下，這3種算法對數(shù)據(jù)中心網(wǎng)絡總流量優(yōu)化的結果，BF-HC算法對于網(wǎng)絡總流量的優(yōu)化相比較BFD算法和隨機算法有明顯的優(yōu)勢。BF-HC算法平均比BFD算法減少網(wǎng)絡流量29%，比隨機算法減少41%。而在Tree拓撲下，BF-HC算法平均比BFD算法減少網(wǎng)絡流量 65% ，比隨機算法減少 81%。BF-HC算法效果更明顯，由于篇幅所限，這里沒有列出Tree拓撲的仿真結果。

圖6 無擁塞情況下能耗比較

圖7 無擁塞情況下網(wǎng)絡通信總流量比較

圖8 顯示了在Fat-tree拓撲下，這3類算法對網(wǎng)絡最大鏈路利用率的影響。可以看出隨機算法由于流量分布較為平均，最大鏈路利用率較低。而BF-HC算法比BFD算法的最大鏈路利用率低，平均下降了12%左右。

圖8 無擁塞情況下最大鏈路利用率比較

在本節(jié)的仿真實驗中，相比較BFD算法，BF-HC算法在優(yōu)化網(wǎng)絡總流量和最大鏈路利用率上有明顯的優(yōu)勢，而且優(yōu)化了數(shù)據(jù)中心的能源消耗。

5.2 有網(wǎng)絡擁塞情況

如果有擁塞發(fā)生，筆者主要考慮以優(yōu)化網(wǎng)絡性能為主，在保證網(wǎng)絡性能的前提下，最小化數(shù)據(jù)中心能耗。采用BF-HC-LS算法進行優(yōu)化。選用熱點鏈路數(shù)（HLN, hotspot link number）作為網(wǎng)絡性能的衡量參數(shù)。

圖 9~圖 11分別顯示了在 Fat-tree拓撲下，BF-HC-LS算法、BF-HC算法、BFD算法和隨機算法對能耗、網(wǎng)絡總流量、HLN數(shù)目的比較結果。5.1節(jié)已經(jīng)比較了BF-HC算法、BFD算法和隨機算法對能耗、總流量的影響，本節(jié)主要比較 BF-HC-LS算法和BF-HC算法。在圖9中，對于能耗的優(yōu)化，BF-HC-LS 算法比BF-HC算法要差一些，平均增加了6%，但差距不是很明顯。同樣，在圖10中，對于總流量的優(yōu)化，BF-HC-LS 算法比BF-HC算法也要差一些，平均增加了 8%。這是由于BF-HC-LS算法為了優(yōu)化網(wǎng)絡鏈路利用率，使得虛擬機之間的流量分布更為平均，使用了更多的物理機和交換機。

圖9 有擁塞情況下能耗比較

圖10 有擁塞情況下網(wǎng)絡通信總流量比較

然而，在圖11中，在優(yōu)化HLN方面，BF-HC-LS算法明顯具有優(yōu)勢，例如，在200個虛擬機的情況下，相比較BF-HC算法，BF-HC-LS 算法的HLN減少了8條。雖然BF-HC-LS算法不能完全避免擁塞，但有效地減少了擁塞數(shù)。

圖11 有擁塞情況下熱點鏈路數(shù)比較

從這個仿真可以看出，相比較 BF-HC算法、BFD算法、隨機算法，BF-HC-LS 算法在能耗沒有增加太多的前提下，優(yōu)化了網(wǎng)絡性能，盡量避免了網(wǎng)絡擁塞，在虛擬機放置過程中，較好地實現(xiàn)了能耗與網(wǎng)絡性能的平衡。

6 結束語

虛擬機放置問題是目前云數(shù)據(jù)中心虛擬化技術研究的熱點。本文提出了一種虛擬機在物理機上的放置方法，在物理機大小和網(wǎng)絡鏈路容量的約束下，優(yōu)化物理機與網(wǎng)絡設備的資源利用率和能耗，并盡可能使得網(wǎng)絡流量分布均衡，減少網(wǎng)絡擁塞。提出了一種新的二階段啟發(fā)式算法。首先，如果沒有產(chǎn)生擁塞，算法以優(yōu)化能耗為主，利用最小割的層次聚類算法與 BFD算法相結合來優(yōu)化物理機和網(wǎng)絡設備的能耗。第二，如果發(fā)生網(wǎng)絡擁塞，以優(yōu)化網(wǎng)絡性能為主。利用局部搜索算法來最小化最大鏈路利用率，減少擁塞鏈路數(shù)目。仿真實驗表明，相比較 BFD算法、隨機算法，在能耗變化不大的情況下，所提算法優(yōu)化了網(wǎng)絡流量分布，降低了網(wǎng)絡的擁塞數(shù)目。

本文主要研究的是利用虛擬機放置技術，使得云計算數(shù)據(jù)中心網(wǎng)絡性能與能耗達到平衡。而云計算數(shù)據(jù)中心的虛擬機放置完畢后，隨著負載的變化，虛擬機大小以及虛擬機與物理機的映射關系也隨之發(fā)生變化，這就要考慮虛擬機遷移的問題。在不影響業(yè)務性能的前提下，如何最小化虛擬機遷移代價實現(xiàn)虛擬機的動態(tài)調(diào)整是下一步的研究工作。

[1] BARHAM P, DRAGOVIC B, FRASER K, et al. Xen and the art of virtualization[J]. ACM SIGOPS Operating Systems Review, 2003, 37(5):164-177.

[2] Amazon EC2[EB/OL]. http://aws.amazon.com/ec2.

[3] VERMA A, AHUJA P, NEOGI A. PMapper: Power and Migration Cost Aware Application Placement in Virtualized Systems[M].Springer, 2008.

[4] BOBROFF N, KOCHUT A, BEATY K. Dynamic placement of virtual machines for managing sla violations[A]. Proc Integrated Network Management, IEEE[C]. Munish,Germany, 2007.119-128.

[5] CARDOSA M, KORUPOLU M R, SINGH A. Shares and utilities based power consolidation in virtualized server environments[A]. Proc Integrated Network Management,IEEE[C]. New York, USA, 2009.[6] 3W2A7-N33G4 .M, MENG X, ZHANG L. Consolidating virtual machines with dynamic bandwidth demand in data centers[A]. INFOCOM 2011,IEEE[C]. Shanghai, China,2011.71-75.

[7] AL-FARES M, LOUKISSAS A, VAHDAT A. A scalable, commodity data center network architecture[J]. ACM SIGCOMM Computer Communication Review, 2008,38(4):63-74.

[8] MANN V, KUMAR A, DUTTA P, et al. VMFlow: Leveraging VM Mobility to Reduce Network Power Costs in Data Centers[M]. Springer:Berlin Heidelberg, 2011. 198-211.

[9] FANG W, LIANG X, LI S, et al. VMPlanner: optimizing virtual machine placement and traffic flow routing to reduce network power costs in cloud data centers[J]. Computer Networks, 2013,57(1):179-196.

[10] MENG X, PAPPAS V, ZHANG L. Improving the scalability of data center networks with traffic-aware virtual machine placement[A].INFOCOM 2010,IEEE[C]. San Diego,CA,USA,2010. 1-9.

[11] MAN JR E C, GAREY M R, JOHNSON D S. Approximation Algorithms for Bin Packing: A Survey[M]. Approximation Algorithms for NP-Hard Problems, 1996.46-93.

[12] WOEGINGER G J. Exact Algorithms for NP-Hard Problems: A Survey[M]. Springer: Combinatorial Optimization-Eureka, 2003.

[13] DEB K. Multi-Objective Optimization[M]. Springer: Multi-Objective Optimization Using Evolutionary Algorithms, 2001.13-46.

[14] JIANG J W, LAN T, HA S, et al. Joint VM placement and routing for data center traffic engineering[A]. INFOCOM 2012, IEEE[C].Orlando,Florida,USA, 2012. 2876-2880.

[15] GUPTA A, KALé L V, MILOJICIC D, et al. HPC-aware VM placement in infrastructure clouds[A]. IEEE Intl Conf on Cloud Engineering[C]. San Francisco,California,USA, 2013. 11-20.ing[C]. San Francisco,California,USA, 2013. 11-20.

[16] BELOGLAZOV A, BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[J]. Concurrency and Computation: Practice and Experience,2012, 24(13): 1397-1420.

[17] BIENKOWSKI M, FELDMANN A, JURCA D, et al. Competitive analysis for service migration in vnets[A]. Proceedings of the Second ACM SIGCOMM Workshop on Virtualized Infrastructure Systems and Architectures[C]. New Delhi, India, 2010.17-24.

[18] HELLER B, SEETHARAMAN S, MAHADEVAN P, et al.ElasticTree: saving energy in data center networks[A]. Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation[C]. San Jose, California, USA, 2010.19-21.

[19] JOHNSON D S, DEMERS A, ULLMAN J D, et al. Worst-case performance bounds for simple one-dimensional packing algorithms[J].SIAM Journal on Computing, 1974, 3(4): 299-325.

[20] GREENBERG A, HAMILTON J R, JAIN N, et al. VL2: a scalable and flexible data center network[J]. ACM SIGCOMM Computer Communication Review, 2009,39(4):51-62.

[21] NIRANJAN MYSORE R, PAMBORIS A, FARRINGTON N, et al.PortLand: a scalable fault-tolerant layer 2 data center network fabric[J].ACM SIGCOMM Computer Communication Review, 2009,39(4):39-50.

[22] Amazon EC2[EB/OL]. http://aws.amazon.com/ec2/instance-types/.

[23] BENSON T, AKELLA A, MALTZ D A. Network traffic characteristics of data centers in the wild[A]. Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement[C]. Melbourne,Australia,2010.267-280.