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

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

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

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