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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

網(wǎng)絡(luò)感知是對整個網(wǎng)絡(luò)所有元素(網(wǎng)絡(luò)拓?fù)?、路由協(xié)議、網(wǎng)絡(luò)設(shè)備等)使用情況的實(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)控兩個重點(diǎn)和應(yīng)對一種突發(fā)情況.

1)網(wǎng)絡(luò)拓?fù)?網(wǎng)絡(luò)拓?fù)涫蔷W(wǎng)絡(luò)感知監(jiān)控的第一個重點(diǎn)，所有的虛擬機(jī)分配請求都將映射到網(wǎng)絡(luò)拓?fù)渲械囊粋€物理主機(jī)上，共享物理主機(jī)的底層資源，向用戶提供服務(wù).因此，網(wǎng)絡(luò)拓?fù)涫呛侠矸峙涮摂M機(jī)，充分利用網(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é)點(diǎn)，通過接入層交換機(jī)彼此相連.在三層網(wǎng)絡(luò)拓?fù)渲?，核心層的能力最?qiáng)，聚合層次之，接入層最弱.常用的樹形網(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è)備(交換機(jī)、路由器等)將大量物理服務(wù)器連接而成.每個網(wǎng)絡(luò)元素(交換機(jī)、路由器和服務(wù)器)在拓?fù)渲衅鹬煌淖饔?，擁有不同的重要?根據(jù)網(wǎng)絡(luò)元素的重要性和能力，動態(tài)地進(jìn)行資源分配，保證核心元素的強(qiáng)大服務(wù)能力，提升普通元素的平均利用率，對虛擬機(jī)的分配過程至關(guān)重要.例如，在三層樹形結(jié)構(gòu)的網(wǎng)絡(luò)拓?fù)渲校尤雽咏粨Q機(jī)重要性最差，聚合層次之，核心層最大.在進(jìn)行資源分配時，必須保證核心層交換機(jī)的強(qiáng)大服務(wù)能力和擴(kuò)展性，盡量少地占用其帶寬.因?yàn)椋诵膶咏粨Q機(jī)出現(xiàn)故障或擁塞，必然導(dǎo)致整個數(shù)據(jù)中心的癱瘓和崩潰.相反，接入層交換機(jī)僅僅影響部分物理主機(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ù)中心的影響，縮小擁塞范圍，是虛擬機(jī)分配的關(guān)鍵問題.

隨著數(shù)據(jù)中心規(guī)模的不斷擴(kuò)大，地理位置的不斷分散，各種數(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ī)則的半隨機(jī)拓?fù)浣Y(jié)構(gòu)，集合了樹形、服務(wù)器、光纖等多種拓?fù)浣Y(jié)構(gòu)，是一種混合的拓?fù)浣Y(jié)構(gòu)，給虛擬機(jī)的分配帶來了新的困難.

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

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

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

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

1.2分配模型

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

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

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

1.3.1帶寬區(qū)域劃分

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

(4)

在虛擬機(jī)類型確定以后，不同類型虛擬機(jī)分配到不同物理主機(jī)，將對整個網(wǎng)絡(luò)拓?fù)涞姆€(wěn)定性造成不同程度的影響.例如，當(dāng)網(wǎng)內(nèi)流量高的多個虛擬機(jī)分配到核心網(wǎng)絡(luò)節(jié)點(diǎn)上，必然占用核心節(jié)點(diǎn)帶寬資源，導(dǎo)致其他節(jié)點(diǎn)的通信延遲，甚至發(fā)生網(wǎng)絡(luò)突發(fā)流.當(dāng)網(wǎng)間流量高的虛擬機(jī)分配到邊緣網(wǎng)絡(luò)節(jié)點(diǎn)時，則增加了通信距離，降低了響應(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)中可以看出，不同類型虛擬機(jī)映射到不同的物理主機(jī)上，其穩(wěn)定系數(shù)的產(chǎn)生方式不同.對于網(wǎng)間虛擬機(jī)而言，帶寬和QOS需求較高，應(yīng)映射到靠近核心的樞紐節(jié)點(diǎn)，且周圍鄰居應(yīng)越稀疏，從而保證經(jīng)過的路徑越短，交互速度越快，對鄰居的影響越??；對于網(wǎng)內(nèi)虛擬機(jī)而言，主要是虛擬機(jī)間的彼此通信，應(yīng)該映射到邊界節(jié)點(diǎn)上，使得多個通信虛擬機(jī)彼此靠近.同時，遠(yuǎn)離核心節(jié)點(diǎn)，減少對整個網(wǎng)絡(luò)的過多影響；對于均衡虛擬機(jī)而言，應(yīng)該選擇網(wǎng)絡(luò)拓?fù)涞闹虚g區(qū)域，平衡節(jié)點(diǎn)樞紐性和鄰居依賴性，約束網(wǎng)絡(luò)突發(fā)流的影響，保證整個網(wǎng)絡(luò)的穩(wěn)定性.

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

(6)

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

1.3.2物理主機(jī)分配

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

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

(7)

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

(8)

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

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

(9)

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

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

(10)

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

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

2.1帶寬區(qū)域劃分

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

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

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

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

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

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

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

圖3　虛擬機(jī)子集選擇策略示意圖

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

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

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

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

Step 1：初始化.

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

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

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

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

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

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

(11)

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

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

①如果NR不為空，將所有主機(jī)加入到SSl中，進(jìn)入step4.

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

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

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

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

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

2.2物理主機(jī)分配

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

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

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

輸出：未分配的虛擬機(jī)集合NoRSl.

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

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

for riin RSlthen

//遍歷虛擬機(jī)子集

for sjin SSl

then //遍歷物理主機(jī)

//判斷虛擬機(jī)的需求是否滿足

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

endif

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

endfor

ri→NoRSl;

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

endfor

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

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

2.3NWTP算法

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

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

圖4　NWTP算法分配示意圖

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

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

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

輸出：NULL.

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

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

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

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

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

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

3實(shí)驗(yàn)結(jié)果分析

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

3.1實(shí)驗(yàn)環(huán)境

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

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

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

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

本文對決定虛擬機(jī)類型的兩個門限參數(shù)〈α,β〉進(jìn)行仿真測試.在不同虛擬機(jī)數(shù)量(10～300)下，采用不同的〈α,β〉值(α從0.1到1，β從1到10)進(jìn)行實(shí)驗(yàn)，對比網(wǎng)絡(luò)感知分配算法在分配時間和網(wǎng)絡(luò)穩(wěn)定性上的差異.表2描述了在100個虛擬機(jī)請求下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個虛擬機(jī)請求下對算法的延遲率、吞吐率和分配時間的影響.從圖中可以得到表2相似的結(jié)論，隨著α的不斷增加，β的不斷減少，算法的性能先提升后降低.

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

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

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

3.3實(shí)驗(yàn)結(jié)果

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

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

虛擬機(jī)數(shù)量

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

虛擬機(jī)數(shù)量

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

虛擬機(jī)數(shù)量

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

虛擬機(jī)數(shù)量

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

虛擬機(jī)數(shù)量

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

圖10　主機(jī)使用情況對比圖

4結(jié)論

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

參考文獻(xiàn)

[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

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

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

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

收稿日期：2015-09-24

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