董健康，王洪波，李陽陽，程時(shí)端

（北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，北京 100876）

1 引言

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

3 建模

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

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

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

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

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

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

3.1.1 能源模型

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

表1 主要的符號(hào)定義及其意義

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

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

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

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

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

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

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

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

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

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

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

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

3.3 總體目標(biāo)

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

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

4 算法

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

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

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

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

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

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

4.2 基于BF的虛擬機(jī)放置算法

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

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

圖4 結(jié)合流量層次聚類的最佳適應(yīng)算法

4.3 局部搜索算法

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

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

圖3 基于BF的虛擬機(jī)放置算法

4.4 算法分析

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

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

5 實(shí)驗(yàn)仿真及結(jié)果分析

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

數(shù)據(jù)中心采用層次化拓?fù)浣Y(jié)構(gòu)，如多根樹[7]、VL2[20]、Fat-tree[21]等，本文選用當(dāng)前數(shù)據(jù)中心中最常見的樹型拓?fù)洌约皩頂?shù)據(jù)中心可能用到的Fat-tree拓?fù)洹?/p>

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

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

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

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

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

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

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

圖8 顯示了在Fat-tree拓?fù)湎?，這3類算法對(duì)網(wǎng)絡(luò)最大鏈路利用率的影響?？梢钥闯鲭S機(jī)算法由于流量分布較為平均，最大鏈路利用率較低。而BF-HC算法比BFD算法的最大鏈路利用率低，平均下降了12%左右。

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

本文主要研究的是利用虛擬機(jī)放置技術(shù)，使得云計(jì)算數(shù)據(jù)中心網(wǎng)絡(luò)性能與能耗達(dá)到平衡。而云計(jì)算數(shù)據(jù)中心的虛擬機(jī)放置完畢后，隨著負(fù)載的變化，虛擬機(jī)大小以及虛擬機(jī)與物理機(jī)的映射關(guān)系也隨之發(fā)生變化，這就要考慮虛擬機(jī)遷移的問題。在不影響業(yè)務(wù)性能的前提下，如何最小化虛擬機(jī)遷移代價(jià)實(shí)現(xiàn)虛擬機(jī)的動(dòng)態(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.