極小通訊延遲的虛擬機(jī)分配算法.pdf

1、近年來，隨著數(shù)據(jù)中心的快速發(fā)展和Mapreduce/Hadoop框架的日益重要，越來越多的大數(shù)據(jù)被放到云系統(tǒng)中處理。在現(xiàn)代基于虛擬化的數(shù)據(jù)中心上，虛擬機(jī)分配是實(shí)現(xiàn)云中資源有效調(diào)度的首要考慮。在云系統(tǒng)中，大數(shù)據(jù)被劃分成多個數(shù)據(jù)存儲在數(shù)據(jù)中心的數(shù)據(jù)結(jié)點(diǎn)上等待虛擬機(jī)處理。此時，不僅存在虛擬機(jī)處理數(shù)據(jù)時的通訊延遲，也存在匯總計算結(jié)果時虛擬機(jī)之間的通訊延遲。虛擬機(jī)分配策略的不同將導(dǎo)致最大通訊延遲的不同。已經(jīng)證明對數(shù)據(jù)結(jié)點(diǎn)分配虛擬機(jī)并考慮虛擬機(jī)之間

2、的通訊延遲，使得最大通訊延遲最小的問題是NP-hard問題。
　　本文提出了三種新的虛擬機(jī)分配算法。前兩種算法首先判斷在通訊延遲的某一閾值內(nèi)是否存在規(guī)模多于數(shù)據(jù)結(jié)點(diǎn)的能夠互相通訊的虛擬機(jī)機(jī)群。若存在則用有效的回溯法或分枝界限算法尋找在此閾值下由虛擬機(jī)構(gòu)成的完全子圖，然后采用Hopcroft-Karp算法將完全子圖中的虛擬機(jī)分配給數(shù)據(jù)結(jié)點(diǎn)。這種方法能夠有效減小解空間，提高解的質(zhì)量。實(shí)驗(yàn)結(jié)果表明，本文提出的算法在Tree，VL2，F(xiàn)a

3、t-Tree和BCube四種網(wǎng)絡(luò)結(jié)構(gòu)中，與當(dāng)前最新的近似算法相比，平均情況下最大通訊延遲分別降低了10.39％，5.68％，9.09％，5.45％。
　　本文從降低時間復(fù)雜度的角度考慮提出了另一種虛擬機(jī)分配算法，該算法首先尋找一組在通訊延遲的某一閾值內(nèi)互相通訊的虛擬機(jī)，然后采用本文提出的有效啟發(fā)式算法從這組虛擬機(jī)中尋找虛擬機(jī)的團(tuán)，再采用Hopcroft-Karp算法為數(shù)據(jù)結(jié)點(diǎn)匹配團(tuán)中虛擬機(jī)。實(shí)驗(yàn)結(jié)果表明，這種算法與當(dāng)前最新的啟發(fā)式