陳　磊 ,章　兢 ,蔡立軍,孟　濤 ,何庭欽

(1.湖南大學(xué) 電氣與信息工程學(xué)院，湖南 長沙　410082; 2.湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙　410082)

?

基于網(wǎng)絡(luò)感知的兩階段虛擬機分配算法*

陳磊1,章兢1,蔡立軍2?,孟濤2,何庭欽2

(1.湖南大學(xué) 電氣與信息工程學(xué)院，湖南 長沙410082; 2.湖南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙410082)

摘要：提出了一種基于網(wǎng)絡(luò)感知的兩階段虛擬機分配算法(NWTP).首先，針對現(xiàn)代數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)涞碾S機性(樹形、服務(wù)器和光纖混合)，根據(jù)交互對象的不同，將虛擬機的帶寬請求分為網(wǎng)內(nèi)帶寬和網(wǎng)間帶寬兩種.其次，將虛擬機的分配過程分解成帶寬區(qū)域劃分和物理主機分配兩個彼此連續(xù)的階段，建立網(wǎng)絡(luò)感知模型.然后，利用流水線技術(shù)將帶寬區(qū)域劃分和物理主機分配看作兩個連續(xù)的工序，并發(fā)進行分配處理.在帶寬區(qū)域劃分環(huán)節(jié)，利用節(jié)點介數(shù)和聚集系數(shù)動態(tài)感知物理主機的穩(wěn)定性，通過差異化的分配策略為虛擬機子集選擇合適的物理主機區(qū)域.在物理主機分配環(huán)節(jié)，將更多的虛擬機分配到負(fù)載方差最大的物理主機上，提高虛擬機網(wǎng)內(nèi)帶寬的節(jié)約度，均衡物理主機的資源負(fù)載.最后，對NWTP，遺傳GA，模擬退火SA，貪婪GR四種算法進行大量的仿真實驗，從分配時間、延遲、吞吐率、CPU利用率、帶寬利用率和物理主機使用情況六個方面驗證了NWTP算法的性能.

關(guān)鍵詞：流水線技術(shù)；數(shù)據(jù)中心；云計算；網(wǎng)絡(luò)感知；虛擬機分配

數(shù)據(jù)中心[1]是成百上千臺物理主機、存儲通過網(wǎng)絡(luò)設(shè)備彼此互連， 利用互聯(lián)網(wǎng)向社會提供計算和服務(wù)的場所.傳統(tǒng)的數(shù)據(jù)中心存在租用成本高、地域限制等缺陷，僅能為大型企業(yè)和政府機構(gòu)提供計算或存儲服務(wù).隨著云計算[2]的不斷發(fā)展和演變，按需付費的商業(yè)模式和虛擬機技術(shù)給傳統(tǒng)數(shù)據(jù)中心帶來了前所未有的機遇.傳統(tǒng)數(shù)據(jù)中心與云計算結(jié)合的“云數(shù)據(jù)中心”應(yīng)運而生[3-5].用戶能夠通過按需付費的模式，利用Internet輕松租用各種不同類型的虛擬機，進行復(fù)雜計算，并支付相應(yīng)的費用.“云數(shù)據(jù)中心”已經(jīng)由奢侈服務(wù)轉(zhuǎn)向了大眾服務(wù)，給社會發(fā)展提供了強大的動力.

云數(shù)據(jù)中心內(nèi)，虛擬機的分配和調(diào)度[6]是一個長期的挑戰(zhàn)，是影響數(shù)據(jù)中心性能的關(guān)鍵.好的虛擬機分配策略能夠提高底層物理資源的利用率，降低成本，增加收益，給用戶帶來良好的體驗和幫助.反之，則可能增加數(shù)據(jù)中心運營成本，甚至導(dǎo)致整個數(shù)據(jù)中心的崩潰.在云數(shù)據(jù)中心中，所有的虛擬機共享底層物理主機資源.因此，虛擬機分配的核心目標(biāo)就是提高底層物理資源的利用率，增加收益，利用有限的資源向更多用戶提供高效穩(wěn)定的服務(wù).在各種服務(wù)中，無論是計算服務(wù)、存儲服務(wù)、容災(zāi)備份服務(wù)，都需要充足的網(wǎng)絡(luò)帶寬的保障.網(wǎng)絡(luò)是云數(shù)據(jù)中心的核心資源，是連接用戶和其他資源的橋梁.在云數(shù)據(jù)中心內(nèi)，所有的物理資源(物理主機、存儲等)通過網(wǎng)絡(luò)設(shè)備彼此相連，共同組成了網(wǎng)絡(luò)拓?fù)?在網(wǎng)絡(luò)拓?fù)渲校慌_物理主機通過網(wǎng)絡(luò)鏈路與多臺設(shè)備進行連接.網(wǎng)絡(luò)帶寬是衡量物理設(shè)備間鏈路能力強弱的標(biāo)準(zhǔn)，是物理設(shè)備通信能力的表示.數(shù)據(jù)中心內(nèi)，網(wǎng)絡(luò)帶寬大小非常有限.因此，充分利用網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)帶寬利用率，是虛擬機分配的重中之重.

近年來數(shù)據(jù)中心的虛擬機分配問題已經(jīng)被廣泛研究，并取得了較好的成果.成果主要分為物理資源優(yōu)化、能耗優(yōu)化和帶寬優(yōu)化三個方面.①大多數(shù)學(xué)者將研究重點集中于物理資源(CPU、內(nèi)存和存儲)的分配，通過提高物理資源的利用率，增加數(shù)據(jù)中心的收益.Sindelar等人[7]根據(jù)多個虛擬機共享底層物理主機內(nèi)存資源的特性，提出了一種內(nèi)存共享感知的虛擬機分配算法，通過建立層次樹和聚類樹結(jié)構(gòu)存儲虛擬機間相同的內(nèi)存內(nèi)容，避免相同內(nèi)容的反復(fù)存儲，提升內(nèi)存資源的利用率.文獻[8]中提出了Best-fit和Worst-fit兩種分配策略，最大化底層物理資源的利用率.文獻[9]利用多目標(biāo)思想同時考慮資源利用率和多維資源負(fù)載，進一步優(yōu)化了物理資源的分配.以上工作都將目標(biāo)著眼于物理主機資源，對網(wǎng)絡(luò)帶寬的研究較少.②部分學(xué)者試圖在虛擬機分配過程中進行能源優(yōu)化.文獻[10-11]通過遺傳算法和啟發(fā)式算法，在考慮能源優(yōu)化的同時進行虛擬機的分配，降低了底層物理主機的使用數(shù)量，節(jié)約了能耗.然而，能耗優(yōu)化工作大多嘗試著減少物理主機的使用數(shù)量，并未考慮網(wǎng)絡(luò)帶寬的性能.③此外，也有部分學(xué)者開始考慮網(wǎng)絡(luò)帶寬資源的分配.R Wang等人[12]通過觀察網(wǎng)絡(luò)帶寬的峰值變化，提出了一種基于帶寬估計的網(wǎng)絡(luò)感知虛擬機分配算法，利用經(jīng)驗估計優(yōu)化帶寬分配.Y Zhao等人[13]將網(wǎng)絡(luò)拓?fù)浜吞摂M機分配結(jié)合，建立混合整數(shù)規(guī)劃模型，利用拉格朗日松弛分解進行虛擬機和帶寬分配，提升了帶寬的利用率.然而，這些工作僅僅考慮了網(wǎng)絡(luò)帶寬的分配，并未對物理資源的分配做過多的研究.

針對目前帶寬分配研究不夠深入的現(xiàn)狀，結(jié)合網(wǎng)絡(luò)帶寬在虛擬機分配中的關(guān)鍵作用，同時優(yōu)化帶寬分配和物理資源分配成為了本文的動機.首先，本文根據(jù)數(shù)據(jù)中心帶寬作用對象，將網(wǎng)絡(luò)帶寬分為網(wǎng)內(nèi)帶寬和網(wǎng)間帶寬兩種.其次，介紹了網(wǎng)絡(luò)感知的相關(guān)知識，分析了云數(shù)據(jù)中心內(nèi)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的隨機特性，利用節(jié)點介數(shù)和聚集系數(shù)來感知網(wǎng)絡(luò)拓?fù)渲芯W(wǎng)絡(luò)元素的重要性.然后，通過分配資源的不同將整個分配過程分解為帶寬區(qū)域劃分和物理主機分配兩個彼此連續(xù)的階段，建立相應(yīng)的網(wǎng)絡(luò)感知模型.再次，提出了一種基于網(wǎng)絡(luò)感知的兩階段虛擬機分配算法NWTP.利用流水線技術(shù)模擬整個資源分配過程，將帶寬區(qū)域劃分和物理主機分配看作流水線上的兩個連續(xù)環(huán)節(jié)，配合錯誤處理，實現(xiàn)并發(fā)資源的分配.最后，在cloudsim平臺進行大量實驗，將NWTP算法與貪婪(GR)、模擬退火(SA)、遺傳(GA)等算法進行對比，體現(xiàn)了算法性能.本文的主要貢獻如下：

1)根據(jù)作用對象，將用戶帶寬需求分為網(wǎng)內(nèi)帶寬和網(wǎng)間帶寬兩種.網(wǎng)內(nèi)帶寬是指多個虛擬機間相互進行數(shù)據(jù)通信所造成的帶寬.網(wǎng)間帶寬是指用戶通過internet與虛擬機進行數(shù)據(jù)通信所需要的帶寬.

2)根據(jù)分配資源的不同，將虛擬機的分配過程分解為帶寬區(qū)劃劃分和物理主機分配兩個彼此連續(xù)的階段，將復(fù)雜的虛擬機分配問題簡單化.

3)提出了一種基于網(wǎng)絡(luò)感知的兩階段分配算法NWTP.利用流水線技術(shù)模擬虛擬機的分配過程，將帶寬區(qū)域劃分和物理主機分配看作流水線中兩個彼此連續(xù)的環(huán)節(jié).在整個流水線中，不同環(huán)節(jié)采用不同的分配策略，配合錯誤處理，實現(xiàn)虛擬機請求的并行分配.

4)在帶寬區(qū)域劃分環(huán)節(jié)，利用節(jié)點介數(shù)和聚集系統(tǒng)感知網(wǎng)絡(luò)元素在網(wǎng)絡(luò)拓?fù)涞闹朽従佑H密性和網(wǎng)絡(luò)樞紐性.將不同的虛擬機請求按照帶寬類型進行分組，不同分組采用不同的分配策略.高網(wǎng)間帶寬虛擬機組將分配到網(wǎng)絡(luò)拓?fù)渲兄匾臉屑~節(jié)點上，保證用戶交互快速性和可靠性；高網(wǎng)內(nèi)帶寬的虛擬機組將分配到邊界網(wǎng)絡(luò)區(qū)域中，保證彼此交互的虛擬機間擁有區(qū)域集中性，減少通信距離，降低網(wǎng)絡(luò)突發(fā)流造成的擁塞和影響；均衡的虛擬機組將結(jié)合前兩種的優(yōu)點，區(qū)域化的分配到網(wǎng)絡(luò)拓?fù)渲休^重要的節(jié)點上，保證對外通信和對內(nèi)通信的快速性.

5)在物理主機分配環(huán)節(jié)，針對固定的虛擬機組和物理主機區(qū)域，以節(jié)約網(wǎng)內(nèi)帶寬通信、均衡區(qū)域內(nèi)物理主機帶寬負(fù)載為目標(biāo)，進行虛擬機到物理主機的映射，盡可能多地將虛擬機分配到同一物理主機.

本文后續(xù)工作的組織如下：第1節(jié)進行網(wǎng)絡(luò)感知的介紹，對整個分配過程進行建模；基于網(wǎng)絡(luò)感知的兩階段虛擬機分配算法(NWTP)在第2節(jié)被設(shè)計；第3節(jié)進行實驗對比，驗證NWTP算法的性能；第4節(jié)總結(jié)全文.

1基于網(wǎng)絡(luò)感知的分配模型

首先，本節(jié)介紹了網(wǎng)絡(luò)感知的定義和核心知識；然后，對網(wǎng)絡(luò)感知的虛擬機分配過程進行了公式化描述；最后，將整個分配過程分解成帶寬區(qū)劃劃分和物理主機分配兩個彼此連續(xù)的階段，并進行相應(yīng)的建模.

1.1網(wǎng)絡(luò)感知

網(wǎng)絡(luò)感知是對整個網(wǎng)絡(luò)所有元素(網(wǎng)絡(luò)拓?fù)?、路由協(xié)議、網(wǎng)絡(luò)設(shè)備等)使用情況的實時監(jiān)控，對網(wǎng)絡(luò)流量動態(tài)變化的預(yù)防和處理.簡單而言，網(wǎng)絡(luò)感知就是恰當(dāng)?shù)姆峙渚W(wǎng)絡(luò)元素的剩余能力，合理的應(yīng)對和處理網(wǎng)絡(luò)突發(fā)情況.本文的網(wǎng)絡(luò)感知主要監(jiān)控兩個重點和應(yīng)對一種突發(fā)情況.

1)網(wǎng)絡(luò)拓?fù)?網(wǎng)絡(luò)拓?fù)涫蔷W(wǎng)絡(luò)感知監(jiān)控的第一個重點，所有的虛擬機分配請求都將映射到網(wǎng)絡(luò)拓?fù)渲械囊粋€物理主機上，共享物理主機的底層資源，向用戶提供服務(wù).因此，網(wǎng)絡(luò)拓?fù)涫呛侠矸峙涮摂M機，充分利用網(wǎng)絡(luò)帶寬資源和底層物理資源的重要參考.傳統(tǒng)數(shù)據(jù)中心都采用樹形的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如圖1所示.樹形網(wǎng)絡(luò)拓?fù)湟话惴譃槿龑?核心層(core)、聚合層(aggregation)和接入層(access).大量的服務(wù)器則為整個網(wǎng)絡(luò)拓?fù)涞娜~子節(jié)點，通過接入層交換機彼此相連.在三層網(wǎng)絡(luò)拓?fù)渲?，核心層的能力最強，聚合層次之，接入層最?常用的樹形網(wǎng)絡(luò)拓?fù)溆蠪at-Tree，portland，VL2[5].圖2為典型的以服務(wù)器中心的網(wǎng)絡(luò)拓?fù)?，其他常見的服?wù)器為中心的網(wǎng)絡(luò)拓?fù)溆蠦cube，Dcell，F(xiàn)iconn[5].

圖1　數(shù)據(jù)中心典型樹形網(wǎng)絡(luò)拓?fù)?/p>

圖2　數(shù)據(jù)中心典型服務(wù)器網(wǎng)絡(luò)拓?fù)?/p>

2)網(wǎng)絡(luò)元素的重要性.數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)溆稍S多的網(wǎng)絡(luò)設(shè)備(交換機、路由器等)將大量物理服務(wù)器連接而成.每個網(wǎng)絡(luò)元素(交換機、路由器和服務(wù)器)在拓?fù)渲衅鹬煌淖饔?，擁有不同的重要?根據(jù)網(wǎng)絡(luò)元素的重要性和能力，動態(tài)地進行資源分配，保證核心元素的強大服務(wù)能力，提升普通元素的平均利用率，對虛擬機的分配過程至關(guān)重要.例如，在三層樹形結(jié)構(gòu)的網(wǎng)絡(luò)拓?fù)渲?，接入層交換機重要性最差，聚合層次之，核心層最大.在進行資源分配時，必須保證核心層交換機的強大服務(wù)能力和擴展性，盡量少地占用其帶寬.因為，核心層交換機出現(xiàn)故障或擁塞，必然導(dǎo)致整個數(shù)據(jù)中心的癱瘓和崩潰.相反，接入層交換機僅僅影響部分物理主機，所以應(yīng)該更加充分地利用接入層的網(wǎng)絡(luò)帶寬，提升網(wǎng)絡(luò)帶寬的利用率.

3)網(wǎng)絡(luò)突發(fā)流.網(wǎng)絡(luò)突發(fā)流是指網(wǎng)絡(luò)中突然出現(xiàn)超過正常大小的帶寬請求，造成網(wǎng)絡(luò)擁塞和延遲的現(xiàn)象.在數(shù)據(jù)中心中，經(jīng)常出現(xiàn)網(wǎng)絡(luò)突發(fā)流情況.如何預(yù)防網(wǎng)絡(luò)突發(fā)流，減少網(wǎng)絡(luò)突發(fā)流對整個數(shù)據(jù)中心的影響，縮小擁塞范圍，是虛擬機分配的關(guān)鍵問題.

隨著數(shù)據(jù)中心規(guī)模的不斷擴大，地理位置的不斷分散，各種數(shù)據(jù)中心拓?fù)浣Y(jié)構(gòu)不斷涌現(xiàn).傳統(tǒng)數(shù)據(jù)中心的樹形拓?fù)?，如圖1，已經(jīng)不能滿足需求.以服務(wù)器為中心、以光纖為中心[5]的網(wǎng)絡(luò)拓?fù)湓絹碓蕉?如圖2.因此，目前數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)錇椴煌耆?guī)則的半隨機拓?fù)浣Y(jié)構(gòu)，集合了樹形、服務(wù)器、光纖等多種拓?fù)浣Y(jié)構(gòu)，是一種混合的拓?fù)浣Y(jié)構(gòu)，給虛擬機的分配帶來了新的困難.

1.1.1節(jié)點介數(shù)和聚集系數(shù)

在現(xiàn)代的拓?fù)浣Y(jié)構(gòu)中，網(wǎng)絡(luò)元素在拓?fù)渲械闹匾愿用黠@，本文引入了聚集系數(shù)和節(jié)點介數(shù)兩個參數(shù)來衡量網(wǎng)絡(luò)元素的重要性.

定義1節(jié)點鄰居和節(jié)點度：節(jié)點鄰居是指與網(wǎng)絡(luò)節(jié)點i直接相連的節(jié)點集合.定義如下：

(1)

節(jié)點i的度ki就是節(jié)點的鄰居個數(shù).

定義2 聚集系數(shù)：聚集系數(shù)是網(wǎng)絡(luò)聚集特性的度量指標(biāo)[5]，表示節(jié)點與鄰居間的親疏程度.在網(wǎng)絡(luò)拓?fù)渲?，第i個網(wǎng)絡(luò)節(jié)點的聚集系數(shù)Ci定義如下：

(2)

在公式(2)中，節(jié)點的度為Ki，表示有Ki個鄰居，Ei表示節(jié)點i與Ki個鄰居間的實際連接邊的數(shù)量，Ti表示節(jié)點i與Ki個鄰居間可能形成的最大連接邊的數(shù)量.當(dāng)Ci=1時，表示節(jié)點i與所有鄰居節(jié)點互相連接，形成全局耦合網(wǎng)絡(luò)，連接非常緊密.

定義3節(jié)點介數(shù)(node betweenness)：節(jié)點介數(shù)是網(wǎng)絡(luò)拓?fù)涞囊粋€重要度量[5].節(jié)點介數(shù)是衡量網(wǎng)絡(luò)拓?fù)渲型ㄟ^該網(wǎng)絡(luò)節(jié)點的最短路徑數(shù)量，反應(yīng)了節(jié)點在網(wǎng)絡(luò)流通中的樞紐性.節(jié)點介數(shù)Bi的定義如下：

(3)

在公式(3)中，dst表示節(jié)點s與節(jié)點t間的最短路徑數(shù)量，dsit表示過節(jié)點i的節(jié)點s與節(jié)點t間的最短路徑數(shù)量，N(N-1)/2表示節(jié)點s與節(jié)點t的所有可能組合數(shù).節(jié)點介數(shù)越大說明節(jié)點在網(wǎng)絡(luò)中的樞紐性越強，刪除節(jié)點(節(jié)點故障)會造成大量節(jié)點對間的最短路徑變長，從而增加整個網(wǎng)絡(luò)的壓力，造成網(wǎng)絡(luò)擁塞，甚至是網(wǎng)絡(luò)崩潰.

節(jié)點聚集系數(shù)和節(jié)點介數(shù)能夠很好地反應(yīng)網(wǎng)絡(luò)元素在整個網(wǎng)絡(luò)拓?fù)渲械闹匾潭龋奂禂?shù)體現(xiàn)了節(jié)點與鄰居間的親密程度，介數(shù)反應(yīng)了節(jié)點對整個網(wǎng)絡(luò)流的樞紐性.通過聚集系數(shù)和節(jié)點介數(shù)，能夠輕松感知整個網(wǎng)絡(luò)的資源情況和動態(tài)變化，為虛擬機的分配提供了強有力的支撐.

1.1.2網(wǎng)內(nèi)帶寬和網(wǎng)間帶寬

通過仔細(xì)分析數(shù)據(jù)中心的網(wǎng)絡(luò)帶寬使用情況，根據(jù)使用對象的不同，可以將網(wǎng)絡(luò)帶寬分成兩種：網(wǎng)間帶寬和網(wǎng)內(nèi)帶寬.

1)網(wǎng)間帶寬.網(wǎng)間帶寬是指數(shù)據(jù)中心的外部用戶通過互聯(lián)網(wǎng)獲取虛擬機中計算數(shù)據(jù)所造成的帶寬，也就是用戶與虛擬機間的通信所產(chǎn)生的網(wǎng)絡(luò)流量.網(wǎng)間帶寬必須通過核心交換機與外界用戶進行交互，需要占用整個網(wǎng)絡(luò)拓?fù)涞墓歉删W(wǎng)絡(luò)資源.網(wǎng)間帶寬是用戶服務(wù)的基礎(chǔ)，是保證服務(wù)SLA等級的關(guān)鍵.因此，網(wǎng)間帶寬應(yīng)該盡量接近核心交換機，更快速地與用戶進行交互.

2)網(wǎng)內(nèi)帶寬.網(wǎng)內(nèi)帶寬是指用戶的多臺虛擬機間進行數(shù)據(jù)通信所造成的帶寬.當(dāng)用戶的多臺虛擬機為流量密集型虛擬機時，則虛擬機間需要頻繁快速地進行數(shù)據(jù)交互，保證虛擬機間的及時通信和運行.網(wǎng)內(nèi)帶寬可能占用過多網(wǎng)絡(luò)資源，造成網(wǎng)絡(luò)突發(fā)流的現(xiàn)象，導(dǎo)致整個數(shù)據(jù)中心網(wǎng)絡(luò)的崩潰.根據(jù)網(wǎng)內(nèi)帶寬的內(nèi)部通信特性，多個相互通信的虛擬機應(yīng)該盡快靠近，保證較小的通信距離.此外，為了避免網(wǎng)內(nèi)帶寬造成的網(wǎng)絡(luò)突發(fā)流問題，應(yīng)該將流量密集型虛擬機分配到邊界節(jié)點上，避免核心節(jié)點和骨干網(wǎng)絡(luò)受到影響，約束網(wǎng)絡(luò)突發(fā)流造成的破壞.

網(wǎng)間帶寬與網(wǎng)內(nèi)帶寬的分解使得網(wǎng)絡(luò)感知能夠更加精確地進行虛擬機分配，保證整個數(shù)據(jù)中心網(wǎng)絡(luò)的可靠和穩(wěn)定，減少網(wǎng)絡(luò)突發(fā)流的產(chǎn)生和嚴(yán)重的破壞.

1.2分配模型

在虛擬機的分配過程中，每個虛擬機ri需要映射到數(shù)據(jù)中心的一臺物理主機si上.物理主機si的CPU，MEM和BW剩余資源必須大于虛擬機ri的請求大小.一個虛擬機只能映射到一臺物理主機上.同一物理主機上的多個虛擬機共享物理主機資源(CPU，MEM和BW).每個用戶可能有多個彼此通信的虛擬機.數(shù)據(jù)中心的物理主機是異構(gòu)的，存在不同CPU、MEM和BW大小的物理主機.網(wǎng)絡(luò)拓?fù)鋱DG中的所有交換機、路由器等網(wǎng)絡(luò)設(shè)備不具有計算能力，只有通信能力，不能將虛擬機映射到網(wǎng)絡(luò)設(shè)備上.

1.3兩階段分配目標(biāo)

基于網(wǎng)絡(luò)感知的虛擬機分配過程同時考慮帶寬資源和物理資源.當(dāng)多個用戶提交一組虛擬機請求時，其分配過程就是在網(wǎng)絡(luò)拓?fù)渲羞x擇物理主機進行映射的過程.整個過程可以簡單地分為兩個連續(xù)的階段.第一個階段，根據(jù)一組虛擬機的總體請求帶寬大小，在網(wǎng)絡(luò)拓?fù)渲羞x擇滿足帶寬要求一塊合適的區(qū)域，保證選擇區(qū)域的穩(wěn)定性和可靠性，降低網(wǎng)絡(luò)突發(fā)流的產(chǎn)生概率.第二個階段，在選擇的區(qū)域中，根據(jù)用戶需求尋找最合適的物理主機進行分配，保證物理主機的資源利用率和負(fù)載.因此，本文將整個網(wǎng)絡(luò)感知的虛擬機分配過程分解成帶寬區(qū)域劃分和物理主機分配兩個階段.

1.3.1帶寬區(qū)域劃分

在帶寬區(qū)域劃分階段，首先需要按類型對虛擬機進行分組.虛擬機類型Type_BW是指虛擬機ri的帶寬請求對鄰居依賴性和網(wǎng)絡(luò)樞紐性的側(cè)重程度，其具體定義如下：

(4)

在虛擬機類型確定以后，不同類型虛擬機分配到不同物理主機，將對整個網(wǎng)絡(luò)拓?fù)涞姆€(wěn)定性造成不同程度的影響.例如，當(dāng)網(wǎng)內(nèi)流量高的多個虛擬機分配到核心網(wǎng)絡(luò)節(jié)點上，必然占用核心節(jié)點帶寬資源，導(dǎo)致其他節(jié)點的通信延遲，甚至發(fā)生網(wǎng)絡(luò)突發(fā)流.當(dāng)網(wǎng)間流量高的虛擬機分配到邊緣網(wǎng)絡(luò)節(jié)點時，則增加了通信距離，降低了響應(yīng)時間(QOS)，導(dǎo)致整個網(wǎng)絡(luò)的不穩(wěn)定.因此，本文使用穩(wěn)定系數(shù)R_C(reliable coefficient)來描述網(wǎng)絡(luò)拓?fù)涞姆€(wěn)定，定義如下：

(5)

從公式(5)中可以看出，不同類型虛擬機映射到不同的物理主機上，其穩(wěn)定系數(shù)的產(chǎn)生方式不同.對于網(wǎng)間虛擬機而言，帶寬和QOS需求較高，應(yīng)映射到靠近核心的樞紐節(jié)點，且周圍鄰居應(yīng)越稀疏，從而保證經(jīng)過的路徑越短，交互速度越快，對鄰居的影響越?。粚τ诰W(wǎng)內(nèi)虛擬機而言，主要是虛擬機間的彼此通信，應(yīng)該映射到邊界節(jié)點上，使得多個通信虛擬機彼此靠近.同時，遠(yuǎn)離核心節(jié)點，減少對整個網(wǎng)絡(luò)的過多影響；對于均衡虛擬機而言，應(yīng)該選擇網(wǎng)絡(luò)拓?fù)涞闹虚g區(qū)域，平衡節(jié)點樞紐性和鄰居依賴性，約束網(wǎng)絡(luò)突發(fā)流的影響，保證整個網(wǎng)絡(luò)的穩(wěn)定性.

因此，帶寬區(qū)域劃分階段的目標(biāo)就是將P臺虛擬機映射到M臺物理主機構(gòu)成的多個區(qū)域內(nèi)，實現(xiàn)網(wǎng)絡(luò)穩(wěn)定性的最大化，其目標(biāo)模型如下：

(6)

在目標(biāo)模型(6)中，xij是一個二進制變量，表示虛擬機i是否分配到物理主機j上.每個虛擬機只能映射到一臺物理主機.

1.3.2物理主機分配

1.2.5 體育鍛煉 對問題“周末或節(jié)假日，你主要安排什么活動？”，各年級有26%～40%的學(xué)生選擇“健身、戶外運動”；對問題“你每天用于鍛煉身體、做有氧運動的時間約為多少”，約37%的回答“不足1 h”，約40%回答“1～2 h”。

在P個虛擬機集合RS中，同一用戶的多個虛擬機屬于相同的類型，且多個虛擬機間通常彼此通信，需要較大的網(wǎng)內(nèi)帶寬.若將多個虛擬機映射到同一物理主機，可大大節(jié)約數(shù)據(jù)中心帶寬的使用.因為，同一物理主機內(nèi)，多個虛擬機的通信不需要占用帶寬.為了描述這種網(wǎng)內(nèi)帶寬的節(jié)約度，本文定義了同用戶同物理主機的虛擬機分配集，表示分配到同一物理主機上的相同用戶的虛擬機請求集合，定義如下：

(7)

根據(jù)公式(7)，u表示虛擬機i的用戶屬性，U表示RS中的用戶屬性數(shù)量.xij表示虛擬機i是否分配到物理主機j.根據(jù)公式(7)可得，物理主機j的網(wǎng)內(nèi)帶寬節(jié)約度為：

(8)

在公式(8)中，網(wǎng)內(nèi)帶寬節(jié)約度就是相同用戶的網(wǎng)內(nèi)帶寬節(jié)約均值之和與總物理主機消耗帶寬的比值，其值域為[0,1).

此外，在節(jié)約網(wǎng)內(nèi)帶寬的同時，需要盡量均衡各個物理主機的帶寬負(fù)載，保證網(wǎng)絡(luò)突發(fā)流情況下所有物理主機擁有相同的抵御程度和擴展性，從而提升數(shù)據(jù)中心網(wǎng)絡(luò)的可靠性.因此，本文定義了帶寬負(fù)載方差，衡量主機區(qū)域的各物理主機的帶寬負(fù)載情況，物理主機j的帶寬負(fù)載方差如下：

(9)

在公式(9)中，物理主機負(fù)載方差的值域同樣為 [0,1).

因此，物理主機分配階段的目標(biāo)模型是最大化網(wǎng)內(nèi)帶寬節(jié)約度和最小化負(fù)載方差，定義如下：

(10)

2基于網(wǎng)絡(luò)感知的兩階段分配算法

根據(jù)上節(jié)的分配模型，本節(jié)提出了一種基于網(wǎng)絡(luò)感知的兩階段虛擬機分配算法，簡稱NWTP算法.NWTP算法將網(wǎng)絡(luò)感知的虛擬機分配過程看作一個流水線作業(yè)過程.虛擬機請求集合為流水線的加工原料，帶寬區(qū)域劃分和物理主機分配為流水線的兩個連續(xù)工序(環(huán)節(jié)).2.1節(jié)將詳細(xì)介紹帶寬區(qū)域劃分的流程和策略，為虛擬機子集選擇物理主機區(qū)域.2.2節(jié)將介紹物理主機分配的流程和相應(yīng)策略，更多地節(jié)約網(wǎng)內(nèi)帶寬和均衡區(qū)域主機帶寬負(fù)載.2.3節(jié)將整體介紹NWTP算法的詳細(xì)流程.

2.1帶寬區(qū)域劃分

在多個用戶提交的虛擬機請求集合RS中，根據(jù)虛擬機類型和用戶屬性，可將RS分解成多個虛擬機子集.帶寬區(qū)域劃分的目標(biāo)就是根據(jù)每個虛擬機子集的虛擬機類型，在網(wǎng)絡(luò)拓?fù)渲羞x擇合適的物理主機區(qū)域.在虛擬機子集中，所有虛擬機都擁有相同的類型和相同的用戶屬性.一次帶寬區(qū)域劃分只為一個虛擬機子集進行主機區(qū)域選擇.此外，為了保證物理主機分配的成功率，帶寬區(qū)域劃分中的物理主機數(shù)量將會多于虛擬機子集的虛擬機數(shù)量.本文默認(rèn)物理主機數(shù)量為虛擬機數(shù)量的1.2倍，可根據(jù)需要進行調(diào)整.

根據(jù)虛擬機子集內(nèi)虛擬機的類型，可將虛擬機子集分成網(wǎng)內(nèi)子集、網(wǎng)間子集和均衡子集三類.三類不同的子集，其區(qū)域選擇的目標(biāo)是不同的、動態(tài)變化的.

1)網(wǎng)間子集.網(wǎng)間子集內(nèi)的虛擬機都是網(wǎng)間帶寬遠(yuǎn)大于網(wǎng)內(nèi)帶寬的虛擬機集合.這類虛擬機的目標(biāo)是對外與用戶交互，保證交互質(zhì)量，提升交互速度是虛擬機分配的要點.在NWTP算法中，網(wǎng)間子集虛擬機將映射到具有核心樞紐性的物理主機上.根據(jù)節(jié)點介數(shù)的定義，核心物理主機必然在通往外網(wǎng)的核心路徑上.這種分配方式，能夠大大減少用戶與物理主機交互的通信距離，降低網(wǎng)絡(luò)成本，增加網(wǎng)絡(luò)帶寬的資源利用率.當(dāng)網(wǎng)間流量虛擬機出現(xiàn)突發(fā)流時，會造成核心節(jié)點的延遲和擁塞.但是，由于網(wǎng)內(nèi)流量的邊界化分配策略，核心節(jié)點的帶寬能力將會最大化，擴展性較強，受到突發(fā)流的影響也會越小.同樣，網(wǎng)內(nèi)流量虛擬機被分配到邊界區(qū)域的節(jié)點和鏈路，且節(jié)點間交互彼此靠近，核心節(jié)點的突發(fā)流不會過多影響網(wǎng)內(nèi)流量的虛擬機.

2)網(wǎng)內(nèi)子集.網(wǎng)內(nèi)子集的所有虛擬機網(wǎng)內(nèi)交互帶寬遠(yuǎn)大于網(wǎng)間通信.這類虛擬機分配的目標(biāo)就是彼此盡量靠近，減少通信距離.在NWTP算法中，網(wǎng)內(nèi)子集的分配策略為：將虛擬機集合分配到網(wǎng)絡(luò)拓?fù)涞倪吔绻?jié)點區(qū)域，增加邊界節(jié)點的資源利用率，減少虛擬機對網(wǎng)絡(luò)拓?fù)渲袠屑~節(jié)點的消耗.此外，通過區(qū)域性的分配，能充分保證虛擬機間的通信距離，減少通信跳數(shù)，提高通信速率.

當(dāng)網(wǎng)內(nèi)子集出現(xiàn)突發(fā)流時，由于分配策略的邊界化，網(wǎng)間虛擬機受到的影響較少.因為，突發(fā)流發(fā)生在網(wǎng)絡(luò)拓?fù)涞倪吔?，其蔓延的范圍有限，不會過多蔓延到網(wǎng)絡(luò)拓?fù)渲械暮诵臉屑~節(jié)點.邊界區(qū)域化分配方式增加了數(shù)據(jù)中心網(wǎng)絡(luò)的擴展性.此外，對于網(wǎng)內(nèi)虛擬機而言，由于其分配策略的區(qū)域化，網(wǎng)絡(luò)突發(fā)流的發(fā)生將被限制在固定區(qū)域內(nèi)，造成區(qū)域內(nèi)的延遲和擁塞，影響區(qū)域較小，不會受到其他虛擬機的干擾，突發(fā)流的消亡周期會大大縮減.此外，通過邊界區(qū)域化的虛擬機分配，能夠很好地平衡整個網(wǎng)絡(luò)的負(fù)載，增加網(wǎng)絡(luò)的穩(wěn)定性.

3)均衡子集.均衡子集內(nèi)的虛擬機其網(wǎng)間帶寬和網(wǎng)內(nèi)帶寬相對均衡.這類虛擬機應(yīng)該同時兼顧網(wǎng)內(nèi)子集和網(wǎng)間子集的分配策略.在NWTP算法中，均衡子集的虛擬機將被區(qū)域化地分配到網(wǎng)絡(luò)拓?fù)涞闹虚g區(qū)域.在保證用戶對外交互的同時，區(qū)域化地捆綁多個虛擬機節(jié)點，減少虛擬機間的通信距離.

圖3展示了不同虛擬機子集的不同帶寬區(qū)域的選擇策略.整個網(wǎng)絡(luò)拓?fù)淇煽醋饕粋€圓，圓的中心點為網(wǎng)絡(luò)中的核心樞紐點.整個拓?fù)鋱A以核心點為中心，可分為3個圈：核心圈、中間圈和邊界圈，圖中用藍(lán)色虛線劃分.不同的虛擬機子集將劃分到不同的拓?fù)淙?nèi)，從而均衡整個網(wǎng)絡(luò)拓?fù)涞呢?fù)載，保證網(wǎng)絡(luò)的穩(wěn)定性和可靠性.在圖3中，網(wǎng)內(nèi)子集將被分配到最外層邊界圈內(nèi).網(wǎng)內(nèi)子集的虛擬機將分配到彼此鄰居的物理主機上，縮小虛擬機間的通信距離；網(wǎng)間子集的虛擬機將被分配到最內(nèi)層的核心圈內(nèi)，以最快的速度與外界用戶進行交互；均衡子集的虛擬機則映射到中間圈內(nèi)，結(jié)合前兩種策略的優(yōu)點，保證網(wǎng)絡(luò)的擴展性.當(dāng)某類型虛擬機出現(xiàn)突發(fā)流時，區(qū)域化的分配策略必然降低突發(fā)流的破壞性，減少虛擬機間的干擾性，保障網(wǎng)絡(luò)的穩(wěn)定性.

圖3　虛擬機子集選擇策略示意圖

根據(jù)圖3的示意，NWTP中帶寬區(qū)域劃分的基本思想如下：根據(jù)虛擬機子集的類型(網(wǎng)間子集、網(wǎng)內(nèi)子集和均衡子集)，選擇相應(yīng)的劃分策略.網(wǎng)間子集劃分到更加接近核心樞紐節(jié)點的物理主機上，減少通信距離，增加交互速率；網(wǎng)內(nèi)子集區(qū)域性地分配到邊界網(wǎng)絡(luò)節(jié)點上，充分利用邊界節(jié)點能力，降低核心節(jié)點和帶寬壓力；網(wǎng)間子集劃分到中間區(qū)域，均衡前兩種策略的優(yōu)點.算法1展示了帶寬區(qū)域劃分的主要流程.

算法1帶寬區(qū)域劃分過程

輸入：虛擬機子集RSl,網(wǎng)絡(luò)拓?fù)銰,穩(wěn)定系數(shù)矩陣RCl.

輸出：虛擬機子集和物理主機區(qū)域?qū)Α碦Sl,SSl〉.

Step 1：初始化.

①初始化區(qū)域物理主機數(shù)量上限SN,SN是子集中虛擬機數(shù)量的1.2倍.

②初始化錯誤核心集ES為空集,ES表示鄰居區(qū)域內(nèi)找不到足夠物理主機數(shù)量(SN)的節(jié)點集合.

③初始化SSl，鄰居集N，合理鄰居集NR為空集.

④初始化最小資源需求MIN_CPU，MIN_MEM，MIN_BW,最小資源需求是所有虛擬機的資源請求最小值.

//在初始化過程中，穩(wěn)定系數(shù)矩陣RCl與虛擬機子集RSl相對應(yīng)，穩(wěn)定系數(shù)矩陣是根據(jù)虛擬機子集類型按照公式(5)計算而來，并已經(jīng)排好序.

Step 2：判斷合理性.遍歷穩(wěn)定系數(shù)矩陣RCl，選擇區(qū)域核心點si，判斷核心點的合理性.核心點不合理的判斷標(biāo)準(zhǔn)如下：

(11)

如果si不滿足標(biāo)準(zhǔn)，將核心點si加入物理主機區(qū)域SSl和NR集中，進入step3.否則，si屬于錯誤核心集ES，或si的剩余資源小于最小資源需求.將si加入錯誤核心集ES.開始下一個核心點的判斷.

Step 3：尋找NR的鄰居點N(NR).根據(jù)公式(11)計算N(NR)中合理的主機節(jié)點集合，并替換NR.

①如果NR不為空，將所有主機加入到SSl中，進入step4.

②如果NR為空，則將N(NR)加入錯誤集ES.返回Step2,判斷下一核心點.

Step 4：判斷RCl是否遍歷完成，且SSl中物理主機的數(shù)量是否大于SN.

①遍歷未完成，且主機數(shù)量小于SN.返回step3，尋找更多的物理主機節(jié)點.

②遍歷未完成，主機數(shù)量大于或等于SN.終止程序，返回虛擬機子集和物理區(qū)域?qū)Α碦Sl,SSl〉.

③RCl遍歷完成.終止程序，返回虛擬機子集和物理區(qū)域?qū)Α碦Sl,?〉.

2.2物理主機分配

物理主機分配環(huán)節(jié)是整個流水線的第二個環(huán)節(jié)，負(fù)責(zé)對帶寬區(qū)域劃分形成的虛擬機子集和物理區(qū)域?qū)Α碦Sl,SSl〉進行主機映射.帶寬區(qū)域劃分和物理主機分配兩個環(huán)節(jié)彼此連續(xù).

相對帶寬區(qū)域劃分而言，物理主機的分配過程較簡單.其核心目標(biāo)就是最大化的虛擬機網(wǎng)內(nèi)流量的節(jié)約度，均衡物理主機區(qū)域內(nèi)的帶寬負(fù)載，增加主機區(qū)域?qū)W(wǎng)絡(luò)突發(fā)流的免疫力，保證數(shù)據(jù)中心的穩(wěn)定性和擴展性.物理主機分配的詳細(xì)流程如算法2所示.

算法2 物理主機分配過程輸入：虛擬機子集和物理主機區(qū)域?qū)Α碦Sl,SSl〉.

輸出：未分配的虛擬機集合NoRSl.

Step 1：初始化.將RSl,SSl按網(wǎng)內(nèi)帶寬和剩余內(nèi)存的大小進行降序排列.初始化未分配的虛擬機集合NoRSl為空集.

Step 2：遍歷RSl，分配虛擬機ri到物理主機si.具體過程如下：

for riin RSlthen

//遍歷虛擬機子集

for sjin SSl

then //遍歷物理主機

//判斷虛擬機的需求是否滿足

j++;next sj; //不滿足開始下一個主機判斷

endif

i++;next ri; //開始下一個虛擬機的分配

endfor

ri→NoRSl;

i++;next ri; //開始下一個虛擬機的分配

endfor

Step 3：返回未分配的虛擬機集合NoRSl.

在物理主機的分配過程中，虛擬機子集將首先分配到剩余資源多的物理主機，從而保證更多的虛擬機分配到同一物理主機上，增加網(wǎng)內(nèi)流量的節(jié)約度公式(8).此外，剩余資源最多的物理主機通常就是負(fù)載方差最大的主機，將更多的虛擬機分配到物理主機，可以均衡帶寬負(fù)載公式(9).

2.3NWTP算法

帶寬區(qū)域劃分和物理主機分配是虛擬機分配過程的兩個連續(xù)階段.NWTP算法將整個分配過程看作流水線處理過程，兩個分配階段就是流水線中兩個連續(xù)的工序(環(huán)節(jié)).NWTP算法的基本思想就是：根據(jù)公式(4)定義的虛擬機類型和用戶屬性，將虛擬機集合RS分解成L個虛擬機子集.將每個虛擬機子集看作原材料，在兩個連續(xù)的工序中進行加工，最終完成虛擬機的分配.NWTP算法是一個并行處理算法，帶寬區(qū)域的劃分與物理主機的分配兩個工序并行工作，加快了虛擬機分配的速度.圖4為NWTP算法的分配過程示意圖.

從圖4可以看出，NWTP算法的流水線共有三個工序(環(huán)節(jié))，帶寬區(qū)域劃分、物理主機分配和錯誤處理.三個環(huán)節(jié)間并行進行虛擬機的分配過程.在t1時刻，虛擬機子集RS1開始進行帶寬區(qū)域劃分.t2時刻，虛擬機子集RS1進行主機分配的同時,RS2開始進行帶寬區(qū)域劃分.依次類推，直到所有虛擬機子集分配完成.因此，NWTP算法能夠并行進行多個虛擬機子集的分配處理，加快分配速度.

圖4　NWTP算法分配示意圖

在NWTP算法的整個流水線中，錯誤處理是非常重要的環(huán)節(jié).當(dāng)帶寬劃分中虛擬機子集無法找到合適的物理主機時，當(dāng)物理主機分配中某些虛擬機無法進行分配時，都要進行錯誤處理.錯誤處理的流程如下：將未分配虛擬機集合，分割成兩個虛擬機子集，重新投入流水線進程處理.若虛擬機集合中只有一個虛擬機，則等待固定周期T，再次進行虛擬機的分配.因此，NWTP的詳細(xì)過程如算法3所示.

算法3NWTP并發(fā)分配過程

輸入：虛擬機集合RS，網(wǎng)絡(luò)拓?fù)銰.

輸出：NULL.

Step 1：初始化.根據(jù)網(wǎng)絡(luò)拓?fù)銰，為每個物理主機節(jié)點生成穩(wěn)定系數(shù)矩陣RC.在RC中，每個物理主機將有3種類型的穩(wěn)定系數(shù)，因為不同類型的虛擬機分配物理主機上，其穩(wěn)定系數(shù)是不同的.

Step 2：根據(jù)公式(4)中虛擬機的類型和用戶屬性，將RS分解成L個虛擬機子集集合RSL.

Step 3：遍歷RSL，根據(jù)虛擬機的類型為每個虛擬機子集RSl求得相應(yīng)的RCl.根據(jù)RSl，G，RCl，按照算法1進行帶寬區(qū)域的劃分，獲得虛擬子集與物理主機區(qū)域?qū)Α碦Sl,SSl〉.將虛擬子集與物理主機區(qū)域?qū)Α碦Sl,SSl〉輸入到step4，并開始下一個虛擬機子集的帶寬區(qū)域劃分.

Step 4：根據(jù)輸入的虛擬子集與物理主機區(qū)域?qū)Α碦Sl,SSl〉，按照算法2，進行虛擬機到物理主機的分配.獲取未分配的虛擬機集合NoRSl.將NoRSl輸入到step5，等待下一個輸入，繼續(xù)執(zhí)行.

Step 5：判斷NoRSl的虛擬機數(shù)量.若大于1，分裂成兩個虛擬機子集，重新加入RSL中等待分配.否則，等待周期T，重新開始分配.

Step 6：當(dāng)RSL中所有虛擬機分配完成，算法結(jié)束.

3實驗結(jié)果分析

本文利用云計算仿真平臺CloudSim3.5[14]作為仿真工具，將NWTP算法與遺傳算法GA[17]，貪婪算法GR[15]，模擬退火算法SA[16]進行對比，從分配時間、網(wǎng)絡(luò)延遲、吞吐率、CPU利用率、帶寬利用率、主機使用情況等六個方面對NWTP算法進行驗證.

3.1實驗環(huán)境

在CloudSim平臺中，利用隨機方式產(chǎn)生物理機資源和虛擬機分配請求，通過DataCenter，Host，Vm，DataCenteBoker等多個類，實現(xiàn)底層物理機和虛擬機的仿真.利用多線程思想優(yōu)化了CloudSim仿真平臺，實現(xiàn)了流水線式的虛擬機分配過程.在仿真環(huán)境中隨機產(chǎn)生了500個物理主機，包含[〈2core-4g〉,〈4core-6g〉,〈4core-12g〉,〈8core-24g〉]四種類型，詳細(xì)的物理主機參數(shù)見表1.為了模擬網(wǎng)絡(luò)拓?fù)涞碾S機性，使用brite拓?fù)渖善麟S機生成500個節(jié)點的網(wǎng)絡(luò)拓?fù)洌ㄟ叺膸挻笮『脱舆t幾率等信息.虛擬機同樣采用隨機策略生成，數(shù)量范圍為[3～400].每個虛擬機的CPU需求從[1～4]隨機生成，內(nèi)存需求從[1～10]*512M隨機生成，網(wǎng)間和網(wǎng)內(nèi)帶寬需求從[1～10]M隨機生成.

表1　物理主機參數(shù)表

3.2虛擬機類型門限參數(shù)測試

虛擬機類型是整個網(wǎng)絡(luò)感知分配算法的基礎(chǔ)，是虛擬機帶寬請求對鄰居依賴性和網(wǎng)絡(luò)樞紐性的偏好.在公式(4)中，α和β是兩個虛擬機類型的門限參數(shù)，表示虛擬機網(wǎng)間帶寬和網(wǎng)內(nèi)帶寬需求的比值大小.在不同的門限參數(shù)下，同一虛擬機將被視作不同的類型，從而采用不同的分配策略，占用網(wǎng)絡(luò)拓?fù)渲胁煌巧木W(wǎng)絡(luò)節(jié)點，對整個網(wǎng)絡(luò)產(chǎn)生不同程度的影響.

本文對決定虛擬機類型的兩個門限參數(shù)〈α,β〉進行仿真測試.在不同虛擬機數(shù)量(10～300)下，采用不同的〈α,β〉值(α從0.1到1，β從1到10)進行實驗，對比網(wǎng)絡(luò)感知分配算法在分配時間和網(wǎng)絡(luò)穩(wěn)定性上的差異.表2描述了在100個虛擬機請求下7種不同〈α,β〉值對網(wǎng)絡(luò)延遲率、網(wǎng)絡(luò)吞吐率和分配時間的影響.從表中可以看出，隨著α的不斷增加(0.1～0.5)，β的不斷減少(10～2)，網(wǎng)絡(luò)感知算法的延遲率、吞吐率和分配時間逐漸減少；當(dāng)α和β在〈0.5,2〉時，算法的性能較好；隨著α的繼續(xù)增加(0.5～1)，β的繼續(xù)減少(2～1)，算法的延遲率、吞吐率和分配時間又逐漸增加.同樣，表3展示了7種不同〈α,β〉值在200個虛擬機請求下對算法的延遲率、吞吐率和分配時間的影響.從圖中可以得到表2相似的結(jié)論，隨著α的不斷增加，β的不斷減少，算法的性能先提升后降低.

表2　100個虛擬機下門限參數(shù)性能對比表

表3　200個虛擬機下門限參數(shù)性能對比表

通過表2和表3的分析，虛擬機類型的門限參數(shù)值〈α,β〉在〈0.5,2〉時，整個算法的延遲率、吞吐率和分配時間的性能最佳，算法擁有較好的網(wǎng)絡(luò)穩(wěn)定性和分配效率.因此，在后續(xù)的實驗對比中，基于網(wǎng)絡(luò)感知的兩階段虛擬機分配算法內(nèi)虛擬機類型的門限參數(shù)值，公式(4)，默認(rèn)設(shè)置為〈0.5,2〉.

3.3實驗結(jié)果

本次實驗從分配時間、延遲率、吞吐率、CPU利用率、帶寬利用率、主機使用情況等六個方面對NWTP算法進行驗證，體現(xiàn)了NWTP算法的性能.

圖5為4種算法的分配時間對比.從圖中可以看出，隨著虛擬機請求數(shù)量的不斷增加，分配時間不斷增大.在虛擬機數(shù)量較小時(10～30)，4種算法的分配時間相近.但是，隨著虛擬機數(shù)據(jù)的不斷增加(30～300)，NWTP算法的分配時間明顯優(yōu)于SA和GA算法，僅次于GR算法.因為，GR算法采用隨機分配策略，不要考慮其他的分配指標(biāo)，尋求局部解，分配時間很快.NWTP，SA和GA算法都在尋找較優(yōu)解，同時考慮負(fù)載均衡等其他目標(biāo)，需要不斷迭代，分配時間較多.然而，在不斷迭代中，NWTP算法采用流水線技術(shù)，并發(fā)進行多個階段的分配，提升了分配效率.

虛擬機數(shù)量

圖6展示了4種算法在不同虛擬機請求下平均延遲率的對比.延遲率是指通信中延遲時間與正常通信時間的比值.從圖中可以看出，隨著虛擬機數(shù)量的不斷增加，4種算法的延遲率呈上升趨勢,GR算法的延遲率最大，GA和SA的延遲率相近，NWTP算法延遲率最優(yōu).當(dāng)虛擬機請求數(shù)量較小時(0～100)，4種算法的延遲率都較小且頻繁波動.其中，GR延遲率最大，波動最劇烈.SA的延遲率其次，波動比較頻繁.GA延遲率與SA近似，但是波動最小.NWTP的延遲率最小，波動與SA近似.因為，當(dāng)虛擬機請求較小時，整個網(wǎng)絡(luò)的吞吐量較小，虛擬機間的通信彼此不會過多干擾，延遲率較小.但是，GR算法的貪婪分配原則，會將虛擬機快速分配到高性能物理主機上，造成虛擬機的地理位置較分散，延遲率的波動最大.SA和GA算法都通過反復(fù)迭代尋求較優(yōu)的分配位置，其延遲率優(yōu)于GR，波動程度也較小.NWTP則將虛擬機按照帶寬請求進行分類，然后區(qū)域性地進行不同類型的虛擬機分配，保證虛擬機分配到底層彼此靠近的某幾臺物理主機上，減少了通信距離.但是，由于底層占用的物理主機位置比較集中，虛擬機間的沖突將增大，導(dǎo)致延遲率有所波動.隨著虛擬機請求數(shù)量的增加(100～300)，4種算法的延遲率逐漸增加，波動程度逐漸趨于平緩.其中，NWTP和GA的延遲率最小，NWTP和SA波動最均衡.因為，隨著虛擬機數(shù)量的增加，4種算法占用的物理主機數(shù)量快速增加，虛擬機間的通信可能跨越多個節(jié)點，增加了網(wǎng)絡(luò)的平均延遲率，降低了四種算法對應(yīng)的延遲波動.但是，GR，SA和GA算法的物理主機分散性，必然導(dǎo)致通信的延遲率加大，其性能差于NWTP算法.

虛擬機數(shù)量

圖7為4種算法在不同虛擬機請求下平均吞吐率的對比圖.從圖中可以看出，隨著虛擬機請求數(shù)量的不斷增加，4種算法的平均吞吐率逐漸上升.其中，NWTP算法的吞吐率最大，其次是GA和SA，GR的吞吐率最小.當(dāng)虛擬機請求數(shù)量較小時(0～40)，NWTP算法的吞吐率明顯高于其他3種算法.因為，NWTP將虛擬機分配到相對集中的物理主機區(qū)域，減少了虛擬機間的通信距離，降低了虛擬機的通信延遲，增加了吞吐量.GR算法隨機選擇高性能主機進行分配，虛擬機位置比較分散.SA和GA通過迭代選擇較優(yōu)物理主機，虛擬機的位置同樣較分散，通信距離較長，延遲較大，吞吐率較差.隨著虛擬機數(shù)量的增加(50～300)，其他3種算法的吞吐率逐漸逼近NWTP算法.其中，SA和GA比較接近，GR吞吐率最差.因為，隨著虛擬機數(shù)量增加，占用底層物理主機資源數(shù)量增大，網(wǎng)絡(luò)的通信負(fù)載加大，虛擬機間的相互干擾增加，平均的通信延遲加大，4種算法間的吞吐量彼此靠近.較其他3種算法，NWTP算法的區(qū)域性集中分配策略，能夠減少通信距離，降低延遲，提升吞吐率.

虛擬機數(shù)量

圖8展示了4種算法占用底層物理主機的平均CPU利用率.從圖中可以看出，不同數(shù)量的虛擬機請求下(10～300)，4種算法占用底層物理主機的平均CPU利用率波動較大.NWTP算法和SA算法的波動情況相對均衡，GA算法次之，GR算法最差.NWTP算法通過區(qū)域化的分配物理主機，使得區(qū)域內(nèi)物理主機的CPU使用相對均衡，從而提升了整體網(wǎng)絡(luò)中物理主機的平均CPU利用率.GR算法的隨機分配策略，必然造成高性能的物理主機優(yōu)先分配，隨著虛擬數(shù)據(jù)的不斷增加，浪費的虛擬機資源不斷增加，平均CPU利用率的波動變化明顯.

虛擬機數(shù)量

圖9是4種算法平均帶寬利用率的對比圖，展示了承載虛擬機的物理主機在多次實驗過程中平均帶寬利用率.從圖中可以看出，隨著虛擬機數(shù)量的不斷變化(從10～300)，4種算法占用底層物理主機的帶寬資源快速變化.GR算法變化最快，GA算法次之，NWTP算法穩(wěn)定性最好.此外，從圖中還可知，較GR和GA兩種算法，NWTP算法在整個分配過程中，具有較高的帶寬利用率，符合提高底層資源利用率的目標(biāo).因為，GR算法的隨機分配策略，未考慮任務(wù)資源的負(fù)載情況，很容易造成資源負(fù)載的不均衡.GA算法的不斷迭代，選擇不同類型的物理主機組合，造成主機間帶寬通信較頻繁，從而造成帶寬負(fù)載的巨大波動.NWTP算法將帶寬分解成網(wǎng)間帶寬、網(wǎng)內(nèi)帶寬，并根據(jù)虛擬機的帶寬類型，分配到網(wǎng)絡(luò)拓?fù)渲械牟煌瑓^(qū)域，減少網(wǎng)內(nèi)帶寬的同時，均衡了區(qū)域物理主機的帶寬負(fù)載，增加了區(qū)域帶寬的利用率，提升了數(shù)據(jù)中心的穩(wěn)定性，對網(wǎng)絡(luò)突發(fā)流有較強的擴展性和適應(yīng)性.

虛擬機數(shù)量

圖10展示了4種算法使用底層物理主機的情況對比.相同的虛擬機請求使用不同的分配算法，其占用的底層物理主機不同.從圖10中可以看出，GA算法占用了較多的高性能物理主機，SA和GA算法對高性能物理主機的占用情況都明顯高于NWTP算法.在數(shù)據(jù)中心中，高性能的物理主機往往起著非常核心的作用，是網(wǎng)絡(luò)拓?fù)涞臉屑~，成本較高.較差性能的物理主機則屬于邊界節(jié)點，樞紐性差，成本低.NWTP算法的邊界區(qū)域分配策略很好地迎合了這種特性，能夠更加適應(yīng)數(shù)據(jù)中心的現(xiàn)實狀況.

圖10　主機使用情況對比圖

4結(jié)論

針對云數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)涞碾S機性，結(jié)合虛擬機分配很少同時考慮帶寬資源和物理主機資源的現(xiàn)狀，本文提出了一種基于網(wǎng)絡(luò)感知的兩階段虛擬機分配算法,NWTP.首先，根據(jù)交互對象的不同，將虛擬機的帶寬請求分解為網(wǎng)間帶寬和網(wǎng)內(nèi)帶寬兩種.利用節(jié)點介數(shù)和聚集系數(shù)感知節(jié)點在網(wǎng)絡(luò)拓?fù)渲械泥従右蕾囆院途W(wǎng)絡(luò)樞紐性；其次，將整個虛擬機分配過程分解為帶寬區(qū)域劃分和物理主機分配兩個彼此連續(xù)的階段，分別建立網(wǎng)絡(luò)感知模型；然后，利用流水線技術(shù)，將帶寬區(qū)域劃分、物理主機分配和錯誤處理看作彼此連續(xù)的三個工序(環(huán)節(jié))，并為每個環(huán)節(jié)設(shè)計了相應(yīng)的處理算法，并發(fā)進行虛擬機分配.最后，將NWTP算法與遺傳GA，模擬退火SA，貪婪GR算法進行對比，驗證了NWTP算法在分配時間、網(wǎng)絡(luò)延遲、吞吐率、帶寬利用率、CPU利用率和占用主機均衡度等方面的優(yōu)勢.

參考文獻

[1]GREENBERG A, HAMILTON J, MALTZ D A,etal. The cost of a cloud: research problems in data center networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 39(1): 68-73.

[2]PATIDAR S, RANE D, JAIN P. A survey paper on cloud computing[C]//Advanced Computing & Communication Technologies (ACCT). Rohtak: 2012 Second International Conference. IEEE, 2012: 394-398.

[3]BARI M F, BOUTABA R, ESTEVES R,etal. Data center network virtualization: A survey[J]. Communications Surveys & Tutorials, IEEE, 2013, 15(2): 909-928.

[4]ALIZADEH M, GREENBERG A, MALTZ D A,etal. Data center tcp (dctcp)[J]. ACM SIGCOMM Computer Communication Review, 2011, 41(4): 63-74.

[5]QI H, SHIRAZ M, LIU J,etal. Data center network architecture in cloud computing: review, taxonomy, and open research issues[J]. Journal of Zhejiang University Science C, 2014, 15(9): 776-793.

[6]GAHLAWAT M, SHARMA P. Survey of virtual machine placement in federated clouds[C]//Advance Computing Conference (IACC). Gurgaon: 2014 IEEE International. IEEE, 2014: 735-738.

[7]SINDELAR M, SITARAMAN R K, SHENOY P. Sharing-aware algorithms for virtual machine collocation[C]//Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'11). New York: SPAA'11. ACM, 2011: 367-378.

[8]REMESHBABU K R, SAMUEL P. Virtual machine placement for improved quality in IaaS cloud[C]//Advances in Computing and Communications (ICACC). Cochin: 2014 Fourth International Conference. IEEE, 2014: 190-194.

[9]LIU C, SHEN C, LI S,etal. A new evolutionary multi-objective algorithm to virtual machine placement in virtualized data center[C]//Software Engineering and Service Science (ICSESS). Beijing: 2014 5th IEEE International Conference. IEEE, 2014: 272-275.

[10]TANG M, PAN S. A hybrid genetic algorithm for the energy-efficient virtual machine placement problem in data centers[J]. Neural Processing Letters, 2014, 41(2): 211-221.

[11]TENG F, DENG D, YU L,etal. An energy-efficient VM placement in cloud datacenter[C]//High Performance Computing and Communications 2014 IEEE 6th Intl Symp on Cyberspace Safety and Security. Paris: 2014 IEEE 11th Intl Conf on Embedded Software and System (HPCC, CSS, ICESS). IEEE, 2014: 173-180.

[12]WANG R, ESTEVES R, SHI L,etal. Network-aware placement of virtual machine ensembles using effective bandwidth estimation[C]//Network and Service Management (CNSM). Rio de Janeiro: 2014 10th International Conference. IEEE, 2014: 100-108.

[13]ZHAO Y, HUANGY, CHEN K,etal. Joint VM placement and topology optimization for traffic scalability in dynamic datacenter networks[J]. Computer Networks, 2015, 80: 109-123.

[14]BUYYA R, RANJAN R, CALHEIROS R N. Modeling and simulation of scalable cloud computing environments and the CloudSim toolkit: Challenges and opportunities[C]//High Performance Computing & Simulation. Leipzig: International Conference on HPCS'09. IEEE, 2009: 1-11.

[15]MILLS K, FILLIBEN J J, DABROWSKI C. Comparing vm-placement algorithms for on-demand clouds[C]// Cloud Computing Technology and Science (CloudCom). Athens: 2011 IEEE Third International Conference. IEEE, 2011: 91-98.

[16]PANDIT D, CHATTOPADHYAY S, CHATTOPADHYAY M,etal. Resource allocation in cloud using simulated annealing[C]//Applications and Innovations in Mobile Computing (AIMoC). Kolkata: AIMoC 2014. IEEE, 2014: 21-27.

[17]TANG M, PAN S. A hybrid genetic algorithm for the energy-efficient virtual machine placement problem in data centers[J]. Neural Processing Letters, 2014: 1-11.

A Network-aware Two-phase Virtual Machine Allocation Algorithm

CHEN Lei1，ZHANG Jing1， CAI Li-jun2?，MENG Tao2，HE Ting-qin2

( 1.College of Electrical and Information Engineering, Hunan Univ，Changsha，Hunan 410082，China;2.College of Information Science and Engineering, Hunan Univ，Changsha，Hunan410082，China)

Abstract:This paper proposed a two-phase network-aware virtual machine allocation algorithm (NWTP). Firstly, based on the randomness (the mixing of tree topology, servers and fiber) of modern data center network topology, the bandwidth requests of virtual machines were divided into two types of inner-bandwidth and outer-bandwidth according to the difference of interactive objects. Secondly, the virtual machine allocation requests were decomposed into two successive phases, and the corresponding network-aware model was established. Thirdly, pipelining technology was developed to regard the bandwidth region partitioning and physical host allocation as two consecutive steps, and to conduct parallel processing. For bandwidth region partitioning phase, the stability of physical host was dynamically perceived by using node betweenness and clustering coefficient, addressing differential allocation strategy to select the appropriate physical host set for the virtual machines subset. For the physical host allocation phase, more virtual machines were allocated to physical host resources with the largest load variance, which saved inner-bandwidth of data center and balanced physical hosts load. Finally, by comparing with the genetic algorithm GA, the annealing algorithm SA and greedy algorithm GR were simulated. Numerical results have shown the performance of NWTP in allocation time, network delay, network throughput rate, CPU utilization, bandwidth utilization and physical host usage.

Key words:pipelining; data center; cloud computing; network-aware; virtual machine allocation

中圖分類號：TP391

文獻標(biāo)識碼：A

作者簡介：陳磊(1986-)，男，四川眉山人，湖南大學(xué)博士研究生?通訊聯(lián)系人，E-mail:ljcai@hnu.edu.cn

基金項目：國家自然科學(xué)基金資助項目(61174140, 61472127, 61272395)，National Natural Science Foundation of China(61174140, 61472127, 61272395) ；中國博士后科學(xué)基金(2013M540628,2014T70767)；湖南省自然科學(xué)基金資助項目(14JJ3107)；湖南省教育廳科研優(yōu)秀青年項目(15B087)；國家科技支撐計劃課題項目(2012BAH09B02)；長沙市重點科技計劃項目(K1306004-11-1,K1204006￣11-1,K1112001-11)

收稿日期：2015-09-24

文章編號：1674-2974(2016)04-0120-13