高任飛，武繼剛，周　瑩，張耀國

1.天津工業(yè)大學 計算機科學與軟件學院，天津 300387 2.廣東工業(yè)大學 計算機科學與技術學院，廣州 510006

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

高任飛1，武繼剛2+，周瑩1，張耀國1

1.天津工業(yè)大學 計算機科學與軟件學院，天津 300387 2.廣東工業(yè)大學 計算機科學與技術學院，廣州 510006

GAO Renfei,WU Jigang,ZHOU Ying,et al.Virtual machine assignment for minimizing data latency.Journal of Frontiers of Computer Science and Technology,2016,10(7)：924-935.

在現(xiàn)代基于虛擬化的數(shù)據(jù)中心上，虛擬機分配是實現(xiàn)云中資源有效調度的首要考慮。在云系統(tǒng)中，大數(shù)據(jù)被劃分成多個數(shù)據(jù)存儲在數(shù)據(jù)中心的數(shù)據(jù)結點上等待虛擬機處理，此時不僅存在虛擬機處理數(shù)據(jù)時的通訊延遲，也存在匯總計算結果時虛擬機之間的通訊延遲。虛擬機分配策略的不同將導致最大通訊延遲的不同。已經(jīng)證明對數(shù)據(jù)結點分配虛擬機，并考慮虛擬機之間的通訊延遲，使得最大通訊延遲最小的問題是NP-hard問題。提出了一種新的虛擬機分配算法。該算法首先判斷在通訊延遲的某一閾值內(nèi)是否存在規(guī)模多于數(shù)據(jù)結點的能夠互相通訊的虛擬機機群。若存在則用有效的回溯法尋找在此閾值下由虛擬機構成的完全子圖，然后采用Hopcroft-Karp算法將完全子圖中的虛擬機分配給數(shù)據(jù)結點。這種方法能夠有效減小解空間，降低虛擬機分配的時間。實驗結果表明，所提算法在Tree、VL2、Fat-Tree和BCube網(wǎng)絡結構中，與當前最新的近似算法相比，平均情況下最大通訊延遲分別降低了10.39%、5.68%、9.09%、5.45%。

數(shù)據(jù)中心；虛擬機分配；通訊延遲；完全子圖

1　引言

隨著越來越多的數(shù)據(jù)密集型應用程序移動到云中去處理，大數(shù)據(jù)的處理成為人們普遍關心的重要問題之一[1-2]。像MapReduce/Hadoop（http://hadoop. apache.org）等處理框架對于執(zhí)行這些密集型應用程序非常適用和高效[3]。云計算是基于虛擬化技術并且通過網(wǎng)絡以按需付費方式獲取計算資源（如存儲資源、服務器資源等）的一種計算模式。用戶可以按需租用云來處理大數(shù)據(jù)，如亞馬遜EC2（http://aws.amazon. com/ec2/）和Cisco數(shù)據(jù)中心（http://goo.gl/Sil548）。虛擬化技術已經(jīng)被證明是數(shù)據(jù)中心內(nèi)一種實現(xiàn)資源共享的有效技術。然而對于云提供商而言，如何實現(xiàn)資源的有效管理仍然是面臨的主要挑戰(zhàn)[4]。虛擬機指通過軟件模擬的具有完整硬件系統(tǒng)功能的、運行在一個隔離環(huán)境中的完整計算機系統(tǒng)[5]。在現(xiàn)代基于虛擬化的數(shù)據(jù)中心上，虛擬機分配是實現(xiàn)云中資源有效調度的首要考慮[6]?？蛻艨梢韵蛟葡到y(tǒng)請求計算資源，如內(nèi)存、硬盤、處理器等，云提供商則根據(jù)客戶的請求情況進一步?jīng)Q定如何分配虛擬機，也就是虛擬機分配問題。有效的分配策略不僅可以減少通訊延遲，降低網(wǎng)絡帶寬消耗，也可以提高資源的利用率[7]。

當一個任務中的大數(shù)據(jù)被劃分后，降低數(shù)據(jù)的總處理時間成為人們的主要目標。若對最大通訊延遲沒有限制，總處理時間就會被延遲[8]。當出現(xiàn)任務或虛擬機負載不平衡，處理器較慢，網(wǎng)絡堵塞時，一個任務的完成時間就會被延長。目前有許多的方法來處理這些問題。有些工作會注重網(wǎng)絡代價和物理機代價的均衡問題[4]，有些則注重虛擬機的調度問題[9]等。由于虛擬機的固有屬性，虛擬機處理數(shù)據(jù)的時間不易被改變，但可以通過合理的虛擬機分配來降低虛擬機處理數(shù)據(jù)的通訊延遲。理想情況是使每個數(shù)據(jù)結點被本地虛擬機處理，這樣數(shù)據(jù)結點和虛擬機之間的通訊延遲為零。然而，由于服務器容量有限，移動數(shù)據(jù)或虛擬機的代價較大等限制，把虛擬機移動到存儲數(shù)據(jù)的服務器上，或者把數(shù)據(jù)移動到放置虛擬機的服務器中來使數(shù)據(jù)被本地虛擬機處理都是不現(xiàn)實的[4]。

然而，僅考慮使用距離數(shù)據(jù)結點較近的虛擬機來處理數(shù)據(jù)達到降低最大通訊延遲的目的是不充分的，因為虛擬機之間也需要通訊，比如在MapReduce云應用中，對最后的結果進行匯總就需要虛擬機之間通訊[3]。把一個大數(shù)據(jù)假設為一個團隊，劃分后的數(shù)據(jù)為團隊中的成員，每個成員擁有一個虛擬機用來處理數(shù)據(jù)，團隊中成員需要互相通訊，這才是團隊合作[4]。最大通訊延遲不僅取決于數(shù)據(jù)與（處理此數(shù)據(jù)的）虛擬機之間的通訊延遲，也取決于（用來處理數(shù)據(jù)的）虛擬機之間的通訊延遲。為數(shù)據(jù)分配虛擬機并使最大通訊延遲最小的問題為NP-hard問題[8]。

文獻[1]考慮了數(shù)據(jù)結點與虛擬機之間的通訊延遲，針對通訊延遲列出了4種目標，并分別給出每種目標下的虛擬機分配方法；文獻[1]還考慮了虛擬機之間的通訊延遲，證明了此虛擬機分配問題的NP-hard性，提出了啟發(fā)式算法，用貪心算法為數(shù)據(jù)結點尋找虛擬機的候選團，并結合匈牙利算法，數(shù)據(jù)結點分配虛擬機。文中使用貪心算法尋找虛擬機的極大團而非最大團，降低了為數(shù)據(jù)結點匹配虛擬機的可能性和容錯性能。文獻[8]在考慮虛擬機之間通訊延遲的基礎上，概括了虛擬機分配問題的數(shù)學模型，通過改變原問題的約束條件將其轉換成為近似問題，然后松弛成線性規(guī)劃問題，并借用線性規(guī)劃解法器來求解，其解空間仍為原問題的解空間。該近似算法閾值取自升序排列后的邊的權值，存在相同閾值下重復處理的問題。

在數(shù)據(jù)中心內(nèi)可利用的虛擬機數(shù)目多于數(shù)據(jù)結點，并且要求處理數(shù)據(jù)結點的虛擬機互相通訊，如此對虛擬機之間通訊的要求比較嚴格。因為虛擬機之間兩兩通訊，所以虛擬機之間的通訊模型所構成的圖是一個完全圖。在完全圖中，每一對不同頂點都有一條邊相連。在一定閾值下將完全圖中大于閾值的邊刪除后所得到的圖則不是一個完全圖（閾值不為圖中最大邊的權值），此時存在簡單圖中最大完全子圖的尋找問題，此問題仍是NP-hard問題[10]。最大完全子圖（也稱為最大團[11]）是一個完全子圖，并且不包含其他任何一個完全子圖[12]。

本文從降低解空間的角度出發(fā)，提出了一種新的虛擬機分配策略：首先，設定閾值并根據(jù)閾值對圖進行變換，在變換后的圖中判斷在此閾值內(nèi)是否存在規(guī)模多于數(shù)據(jù)結點的能夠互相通訊的虛擬機。若存在，則用回溯法遞歸地在解空間中搜索，并且在搜索過程中利用剪枝函數(shù)剪去無用的搜索來有效地尋找此閾值下的完全子圖。若完全子圖中虛擬機的規(guī)模不小于數(shù)據(jù)結點數(shù)目，將用Hopcroft-Karp算法為數(shù)據(jù)結點分配規(guī)模大于數(shù)據(jù)結點的完全子圖中的虛擬機。因為完全子圖中的虛擬機之間互相通訊已經(jīng)符合不超過閾值的要求，所以下一步要解決的問題就是能否找到由（完全子圖中的）虛擬機和數(shù)據(jù)結點構成的二分圖在此閾值下的完備匹配。本文使用Hopcroft-Karp算法來解決此二分圖的匹配問題。

這種虛擬機分配方法能夠有效減小解空間，提高解的質量，并且降低虛擬機的分配時間。同時，進行大量實驗，通過與文獻[1]中的啟發(fā)式算法和文獻[8]中的近似算法進行比較來評估本文算法的性能和效率。文獻[1]中的實驗在一種分層的網(wǎng)絡結構上進行，本文算法與之相比，在區(qū)間[1,64]、[1,256]和[1, 1 024]上最大通訊延遲相同，但運行時間平均改進了7.49%。在文獻[8]的4種網(wǎng)絡拓撲結構中兩種近似算法所得到的最大通訊延遲相同，本文算法在Tree、VL2、Fat-Tree和BCube 4種網(wǎng)絡結構中與當前最新的近似算法相對比，平均情況下最大通訊延遲分別降低了10.39%、5.68%、9.09%和5.45%。

2　虛擬機分配的問題描述

Fig.1　Network topology and corresponding cost matrix for Fat-Tree圖1　Fat-Tree的網(wǎng)絡拓撲結構及其代價矩陣

當前數(shù)據(jù)中心的拓撲結構通常為3層架構，例如Fat-Tree、VL2和Tree，這種3層架構遵循了一般的網(wǎng)絡結構并給予了擴展（Cisco data center infrastructure 2.5）。如圖1所示，結構中的底層為接入層，接入層的交換機連接服務器，頂層為核心層，匯聚層連接核心層和接入層，數(shù)據(jù)中心內(nèi)的數(shù)據(jù)結點（data node，DN）和計算結點分布在底層的服務器中，數(shù)據(jù)結點用來存放數(shù)據(jù)，而計算結點用來處理數(shù)據(jù)，并由許多可利用的虛擬機（virtual machine，VM）構成。用戶將待處理的數(shù)據(jù)存儲在數(shù)據(jù)中心的DN上，并請求一定數(shù)目的VM進行處理。圖1中矩陣表示Fat-Tree結構中兩個服務器之間進行通訊所經(jīng)過的交換機數(shù)目。例如，第一行中前3位數(shù)0 1 3的含義為：第一個服務器內(nèi)的虛擬機與數(shù)據(jù)結點通訊不經(jīng)過交換機；而位于第一個服務器中的虛擬機訪問第二個服務器中的數(shù)據(jù)結點則經(jīng)過1個交換機；當?shù)谝粋€服務器中的虛擬機訪問第三個服務器中的數(shù)據(jù)結點時經(jīng)過3個交換機。

本文使用如下實例來導出虛擬機分配問題。如圖2所示，一個大數(shù)據(jù)在數(shù)據(jù)中心內(nèi)被劃成3塊，分別存儲在DN1、DN2和DN3這3個數(shù)據(jù)結點上，需要3個虛擬機來處理?，F(xiàn)有5個可利用的虛擬機，它們分布在不同服務器上，任意一個虛擬機都可以處理任意一個數(shù)據(jù)結點，但通訊延遲各不相同，任意兩個虛擬機之間通訊延遲也不相同。

Fig.2　3DNs，5 VMs and corresponding access latencies圖2　3個DN與5個VM及其通訊延遲

圖3是兩種虛擬機分配方式。圖3（a）表示第1、2、3個數(shù)據(jù)結點分別用第1、2、5個虛擬機處理，此時最大的通訊延遲是28。圖3（b）表示第1、2、3個數(shù)據(jù)結點分別用第5、2、4個虛擬機處理，最大的通訊延是19。因此，VM的分配方式不同，最大的通訊延遲也不相同。若對最大通訊延遲沒有限制，總處理時間則會被延遲。因此，需要制定一種虛擬機分配策略，使最大的通訊延遲最小。

Fig.3　Two kinds of VMs assignments圖3　兩種虛擬機分配方式

本文遵循已有研究中的基本假設：

（1）一個VM處理一個DN。若一個DN需要k（k>1）個VM進行處理，則把DN復制k-1份存儲在另外k-1個DN上[8]。

（2）通訊延遲滿足三角不等式。兩個結點間的通訊延遲由它們通訊所經(jīng)過的交換機數(shù)目支配[7，13-15]。在數(shù)據(jù)中心的許多網(wǎng)絡結構中，如Fat-Tree、VL2和Tree等[7]，交換機數(shù)目遵循三角不等式原則，因此假設一個數(shù)據(jù)中心內(nèi)通訊延遲滿足三角不等式是合理的[1，16]。

給定一個圖G=(D∪V,E1∪E2)，D表示數(shù)據(jù)中心內(nèi)數(shù)據(jù)結點的集合，V表示數(shù)據(jù)中心內(nèi)可利用的虛擬機的集合。設eij∈E1(i∈D,j∈V)為連接DN與VM的邊，e′ij∈E2(i,j∈V)為連接虛擬機與虛擬機之間的邊。設dij∈R+（R+為正實數(shù)域）(i∈D,j∈V)為DN與VM之間的通訊延遲，d′ij∈R+(i,j∈V)為兩個虛擬機之間的通訊延遲。目標是使最大通訊延遲最小。

定義1最大通訊延遲是指數(shù)據(jù)結點與虛擬機之間，以及處理數(shù)據(jù)結點的虛擬機與虛擬機之間所有通訊延遲的最大者，記作d，即

此時5個虛擬機之間互相通訊的延遲為：

因為最大通訊延遲比每一個DN與處理此DN的VM之間的通訊延遲大，所以有：

對于每個數(shù)據(jù)結點，必存在一個虛擬機來處理，而對于每個虛擬機，它可以處理數(shù)據(jù)結點，也可以不處理數(shù)據(jù)結點，即每個VM至多分配給一個DN，所以有：

因為加入了對虛擬機之間的通訊延遲的考慮，所以最大通訊延遲也要大于處理DN的虛擬機之間的通訊延遲，即：

為數(shù)據(jù)結點分配虛擬機的問題，即虛擬機分配（virtual machine assignment，VMA）問題，可以被歸納為如下混合整數(shù)規(guī)劃問題[8]。

3　虛擬機分配算法

3.1算法思想及算法框架

若不考慮虛擬機之間的通訊，DN與VM之間通訊構成的圖為二分圖，對于二分圖的匹配問題，已經(jīng)有許多經(jīng)典算法來解決，但是僅僅實現(xiàn)二分圖的最優(yōu)匹配是不夠的，這對VM之間的通訊延遲沒有界限控制。虛擬機之間互相通訊意味著任意兩個VM之間存在通訊延遲，即VM之間通訊所抽象出的模型是無向完全圖，在此完全圖中每個頂點的度數(shù)都相同，都為|V|-1。要使最大通訊延遲最小，則要求被分配的虛擬機之間的通訊延遲都不能過大。

若通訊延遲能控制在一定閾值之內(nèi)，在此閾值下能互相通訊的虛擬機的數(shù)目多于DN的數(shù)目，即互相通訊的虛擬機規(guī)模足夠處理數(shù)據(jù)結點，就可以進一步為數(shù)據(jù)結點分配這些虛擬機，稱此閾值下虛擬機規(guī)模滿足數(shù)據(jù)結點。令Z為圖G中邊的權值所組成的集合，因為集合中元素具有無序性和互異性，所以集合Z的規(guī)模為G中邊的種類數(shù)。對G中所有的邊E1與E2進行遍歷，在遍歷過程中，出現(xiàn)不同的邊的權值就記錄在集合Z中。然后使用歸并排序對Z中元素升序排列，設最大邊的權值為Max。

給定一個圖G1=(V,E2)，G1?G，設閾值為t(t∈Z)。通過刪除大于閾值t的邊，將完全圖G1轉換為G1′，在G1′的完全子圖內(nèi)的虛擬機之間互相通訊，其通訊延遲肯定不超過t。具體轉換為：先將G1復制給G1′，再將圖G1′中不大于t的邊的權值設為1（將邊的權值設為1不影響完全子圖的尋找，并且可以避免通訊延遲為0在二分圖匹配時被當作無邊處理的情況發(fā)生），大于t的邊的權值設為0，相當于只保留G1′中權值不大于t的邊。當t為Max時，G1中所有的邊都會被保留，G1′仍然是一個完全圖，其最大完全子圖為|V|階完全子圖；當t小于Max時，轉換后的G1′不再是一個完全圖。要使最大通訊延遲不超過t，只能將完全子圖中的虛擬機分配給數(shù)據(jù)結點。

首先根據(jù)圖中所有邊的權值確定閾值的取值集合Z，將Z中元素升序排列后依次設為閾值；其次在不同閾值下尋找合適的最大完全子圖，若最大完全子圖中VM規(guī)模不小于DN的規(guī)模，則在此閾值下為DN分配完全子圖中的虛擬機，否則在此閾值下無解，繼續(xù)增大閾值尋找合適的最大完全子圖。直到完全子圖中的VM規(guī)模滿足DN，并且在此閾值下所有的DN都被匹配。本文提出的虛擬機分配算法（NEW-VMA）可形式化描述如下：

Algorithm NEW-VMA

Input：A graphG=(D∪V,E1∪E2)with weightsd′abanddabassociated with alle′ab∈E2and eab∈E1

begin

用Z記錄E1與E2中邊的不同權值，對Z中元素升序排列后并從1開始順序標記;

fori←1 to|Z|do

t←the value of thei-th element inZ;

G1′←G1;

for each pair of edgesa∈Vandb∈Vdo

ifd′ab≤ tanda≠bthend′ab←1 inG1′;

elsed′ab←0 inG1′;

end if

end for

ift=Maxthen

The maximum access latency isMax;

else if DFC找到規(guī)模多于數(shù)據(jù)結點的由虛擬機構成的完全子圖

Call BipartMatch to find the match;

if the number of matched DNs=|D|

break;

end if

end if

end if

end for

end

其中子過程DFC為尋找合適的完全子圖過程，將在3.2節(jié)詳細描述，子過程BipartMatch為二分圖匹配過程，此二分圖由數(shù)據(jù)結點與完全子圖中的虛擬機構成的，將在3.3節(jié)描述。

3.2尋找合適的完全子圖

若閾值t取值過小，則最大完全子圖的規(guī)模過小，不足以處理DN；若t取值過大，雖然可以使最大完全子圖中的VM規(guī)模滿足DN，但是最大通訊延遲也伴隨增大。本文提出的尋找合適的完全子圖方法如下：

（1）在設定閾值后，根據(jù)圖G1′中頂點的度數(shù)和邊數(shù)以及相關定理判斷是否存在規(guī)模多于數(shù)據(jù)結點的虛擬機的完全子圖。

（2）根據(jù)判斷結果決定是否尋找完全子圖。若G1′中存在規(guī)模大于數(shù)據(jù)結點的虛擬機的完全子圖，則用有效的回溯法尋找完全子圖。

在圖論中，存在這樣的定理，即使不知道一個簡單圖中頂點之間的具體連接情況，根據(jù)圖中邊數(shù)也可以判斷出圖中至少存在多少階的完全子圖。

圖蘭（Turán）定理[17]：對于n個頂點的簡單圖，若圖中邊數(shù)l>M(n,p)，那么它必包含 p階完全子圖。

由圖蘭定理可知，當n個頂點的簡單圖中的邊數(shù)達到M(n,p)時，此圖中一定存在p階完全子圖。設l 為G1′中的邊數(shù)，可以根據(jù)l判斷G1′中是否存在規(guī)模大于數(shù)據(jù)結點的虛擬機的完全子圖。若存在，則進一步尋找完全子圖。根據(jù)圖蘭定理可以判斷當l>M(n,p)時，一定存在 p階完全圖。但是當l≤M(n,p)時，p階完全圖則不一定不存在。然而，可以知道，當度數(shù)不小于p-1的頂點數(shù)少于p時，p階完全子圖是一定不存在的。因為若存在p階完全子圖，則至少存在p個度數(shù)大于p-1的頂點。若度數(shù)大于或等于p-1的頂點數(shù)不少于p，則有可能存在p階完全子圖，即：

Procedure DFC/*Detect-and-Find-the-Clique*/

Input:AgraphG1′with weightsd′ij(i,j∈V)

begin

Calculate linG1′;

ifl>M(||V,||D)then

Call MaxClique to find the clique;

else

Calculatesjof each node inG1′;

Continue;

else

Call MaxClique to find the clique;

if the number of VMs in the clique<||Dthen

Continue;

end if

end if

end if

end

本文舉例說明判斷虛擬機的完全子圖規(guī)模的過程。如圖4是圖2中5個虛擬機之間互相通訊的圖。圖中邊的權值種類構成了集合Z={10,19,36,28}，當t=10時，轉換后的G1′如圖5（a），度數(shù)大于2的頂點只有一個，則一定不存在一個三階完全子圖。因此t=10時，最大完全子圖中的虛擬機規(guī)模小于數(shù)據(jù)結點規(guī)模。于是增大t，當t=19時，轉換后的G1′如圖5（b），圖中邊數(shù)l=8。根據(jù)圖蘭定理，若5個頂點的圖中邊數(shù)多于M(5,3)時，則一定存在三階完全子圖。因為 l>M(5,3)（此時 p=3，r=5%(p-1)=1,M(5,3)=5.25），滿足圖蘭定理，所以當t=19時G1′中一定存在三階完全子圖?？烧{用MaxClique尋找完全子圖。

Fig.4　Complete graph made by VMs圖4　VM構成的完全圖

Fig.5　Complete graph after transforming圖5　轉換后的完全圖

子過程MaxClique是用回溯法在G1′中尋找完全子圖的過程。訪問到圖G1′中某個頂點時，當該頂點違反問題的約束條件時，就不再訪問其子孫，而回溯到它的父結點，選取下一個兒子為訪問對象。在尋找虛擬機的最大完全子圖過程中，設置剪枝函數(shù)F=Cn+n-k（Cn為當前團的頂點數(shù)，初始值為0，n為圖中頂點數(shù)，k為結點層數(shù)），即當遍歷到該頂點時，若當前完全子圖的頂點個數(shù)與剩下還未遍歷的頂點數(shù)之和小于記錄中最大團的頂點數(shù)，則可剪枝，無需再進一步搜索子樹。

若數(shù)據(jù)中心內(nèi)有n個虛擬機，則把尋找最大完全子圖問題的解表示成n維向量(x1,x2,…,xn)作為解向量，xi對應于第i個虛擬機（頂點的標號與虛擬機的標號相同），其中xi取自有限集合Xi，Xi={0,1}（xi取1表示xi對應的頂點即第i個虛擬機在完全子圖內(nèi)，xi取0表示第i個頂點不在完全子圖中），i=1,2,…,n。結點(x1,x2,…,xk)的含義為：已經(jīng)檢索k個頂點，其中xi=1對應的頂點在當前的完全子圖內(nèi)。用邏輯狀態(tài)樹Pn(x1,x2,…,xn)表達解向量應滿足的性質，即約束條件，表示任意兩個xi取1對應的頂點都有邊相連。用Pk(x1,x2,…,xk)表示部分性質(k

用回溯法尋找最大完全子圖的約束條件是遍歷的頂點與當前完全子圖內(nèi)每個頂點都有邊相連。在搜索過程中利用剪枝函數(shù)F剪去無用的搜索，拋棄不可能導致合法解的候選解，從而使求解時間大大縮短。設當前圖中已經(jīng)檢索到的極大完全子圖的頂點數(shù)為界B，代價函數(shù)F=Cn+n-k為目前的完全子圖擴張為極大完全子圖的頂點數(shù)的上界。當遍歷該結點時，若該結點的代價函數(shù)值不超過B，則回溯，超過B，則進行下一步深度優(yōu)先搜索?；厮莘ㄒ陨疃葍?yōu)先策略遍歷解空間樹，遞歸地在解空間中搜索，并且在搜索過程中利用剪枝函數(shù)剪去無用的搜索，直到回溯到根結點。

通過在圖5（b）中使用有效的回溯法尋找合適的完全子圖來對算法的執(zhí)行過程進行說明，如圖6所示的尋找完全子圖的狀態(tài)樹。

Fig.6　State-tree of finding complete subgraph圖6　尋找完全子圖的狀態(tài)樹

從解空間樹的根結點開始，分枝規(guī)定左子樹為1，右子樹為0。遍歷結點1，P1(1)成立，深度搜索至結點2處，此時P2(1,1)不成立，即結點1和結點2無邊相連，則回溯至結點1處進入右子樹搜索。結點3與當前團內(nèi)頂點無邊相連，P3(1,0,1)不成立，因此回溯并且遍歷結點4，此時，P4(1,0,0,1)成立，結點4滿足約束條件；繼續(xù)深度搜索至葉結點，P5(1,0,0,1,1)成立，如圖6中標記a處，此時得到第一個極大完全子圖{1, 4,5}，頂點數(shù)為3，界B為3。在狀態(tài)樹中結點b處，代價函數(shù)F=2

3.3二分圖匹配

本節(jié)介紹虛擬機分配算法NEW-VMA中使用的子過程BipartMatch。該過程是用Hopcroft-Karp算法[18]為數(shù)據(jù)結點匹配最大完全子圖中的虛擬機，此時最大完全子圖中的虛擬機之間互相通訊已不超過設定閾值，因此為數(shù)據(jù)結點分配完全子圖中的虛擬機時可以不考慮虛擬機之間的通訊問題。

為數(shù)據(jù)結點分配完全子圖中虛擬機的問題為二分圖匹配問題。本文二分圖G2=(D∪P|v|,E1)，G2?G，P|v|∈V，D與P|v|是兩個不相交的子集，D是數(shù)據(jù)結點的集合，P|v|是為數(shù)據(jù)結點分配的完全子圖中的虛擬機。M∈E1，若M滿足當中任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。當圖中某一子集中的頂點都和圖中某條邊關聯(lián)，則為完備匹配[19]。因為最大完全子圖中的虛擬機規(guī)模不小于數(shù)據(jù)結點的規(guī)模（小于則無解），所以完備匹配是指所有的數(shù)據(jù)結點都被虛擬機處理。本文采用Hopcroft-Karp算法來解決此問題。該算法是由Hopcroft與Karp一起提出的，是對Hungarian算法（匈牙利算法）的優(yōu)化，其思想主要是在尋找增廣路徑的同時尋找多條不相交的增廣路徑，形成極大增廣路徑集，然后對極大增廣路徑集進行增廣[18]。NEW-VMA算法在某一閾值下使用回溯法尋找虛擬機的最大完全子圖時，一旦完全子圖的規(guī)模滿足數(shù)據(jù)結點，就及時執(zhí)行Hopcroft-Karp算法為數(shù)據(jù)結點匹配虛擬機，若能達到完備匹配，則終止。增加閾值雖然能使團規(guī)模增加，降低二分圖匹配的閾值，但最大通訊延遲也隨之增大。Hungarian算法的時間復雜度是O(n×m)[20]，n為二分圖中的頂點數(shù)，m為二分圖中的邊數(shù)，而Hopcroft-Karp算法的時間復雜度為O(n1/2×m)。

3.4時間復雜度

以下簡單陳述通訊延遲的計算復雜度。在含有n1個數(shù)據(jù)結點，n2個虛擬機與l條邊的圖中，算法首先確定邊的權值種類，最壞情況下時間復雜度為O(l2)。對于l1種邊的權值進行排序，最壞情況下的時間復雜度為O(l1lbl1)。在某一閾值下使用回溯法尋找最大完全子圖時，最壞情況下時間復雜度為O(n22n2)。因此，算法在最壞情況下的時間復雜度為O(l1n22n2)。通過剪枝函數(shù)可以提前判斷繼續(xù)深度優(yōu)先搜索是否可能得到最優(yōu)解，拋棄不可能導致合法解的候選解，從而使求解時間大大縮短，提高搜索的效率。

4　實驗結果及分析

本文評估不同虛擬機分配算法對于通訊延遲的影響。實驗在Intel?CoreTMi5-4200M CPU@2.50 GHz 2.49 GHz的處理器上進行，實現(xiàn)了與文獻[1]中啟發(fā)式方法的比較，也實現(xiàn)了與文獻[8]中近似算法的比較。實驗中使用了與參考文獻相同的實驗參數(shù)。

4.1與啟發(fā)式算法的比較

在文獻[1]的實驗中，數(shù)據(jù)中心內(nèi)的網(wǎng)絡結構上設置有1 024個服務器，將40個數(shù)據(jù)結點和120個虛擬機隨機放置在1 024個服務器的前64、256和1 024個服務器中，即實驗中數(shù)據(jù)結點與虛擬機的分布區(qū)間為[1,16]、[1,64]和[1,256]。數(shù)據(jù)結點和虛擬機的位置一旦確定，則任何一個虛擬機與任一個數(shù)據(jù)結點或虛擬機之間通訊所經(jīng)過的交換機數(shù)目也就確定。在不同分布區(qū)間上，兩個服務器之間通訊所經(jīng)過的最大交換機數(shù)如表1所示。

Table 1　Maximum number of switches between two racks表1　兩個服務器通訊經(jīng)過的最大交換機數(shù)

兩個服務器之間的通訊延遲由這兩個服務器通訊所經(jīng)過的交換機數(shù)目支配[8]，因此在本文實驗中最大通訊延遲用交換機的個數(shù)表示。經(jīng)過更少的交換機意味著通訊延遲更小[7]。數(shù)據(jù)結點與虛擬機之間或虛擬機與虛擬機之間的通訊延遲為這兩個結點所在的服務器進行通訊所經(jīng)過的交換機數(shù)乘以[0.75, 1.25]中的一個隨機數(shù)。實驗將數(shù)據(jù)結點和虛擬機在每個區(qū)間上隨機分布20次，并求最大通訊延遲和運行時間。圖7、圖8分別為在相同實驗參數(shù)下的最大通訊延遲和運行時間的比較。

Fig.7　Maximum access latencies of two algorithms圖7　兩種算法的最大通訊延遲

Fig.8　Running time of two algorithms圖8　兩種算法的運行時間

圖7實驗結果表明，本文虛擬機分配算法（NEWVMA）與文獻[1]中啟發(fā)式算法（VMA）在3種分布區(qū)間上得到的最大通訊延遲相同。但運行時間平均改進了7.49%，如圖8所示。本文先根據(jù)閾值對最大完全子圖的規(guī)模進行初步判斷，然后再決定是否尋找完全子圖。若判斷得出虛擬機規(guī)模一定不滿足數(shù)據(jù)結點的結論，則不調用回溯法，繼續(xù)對下一個閾值進行判斷，如此可避免閾值過小時對最大完全子圖的尋找，從而降低運行時間。

4.2與近似算法的比較

文獻[8]中的實驗選擇的結構為數(shù)據(jù)中心內(nèi)常用的4種網(wǎng)絡拓撲結構[7]，分別是Tree、VL2、Fat-Tree和BCube[21]。在構造Tree結構時，設置接入層交換機的扇出（fan-out）p0為16，匯聚層交換機扇出p1為4。在VL2結構中，設置接入層交換機扇出p0為32。在Fat-Tree結構中，設置交換機的端口數(shù)k為16。在BCube中，設置階數(shù)k為1，交換機端口數(shù)n為32。根據(jù)設置參數(shù)可以確定該拓撲結構的大小，即可得知每層交換機數(shù)目以及每個接入層的交換機連接的服務器數(shù)目。

例如：在Fat-Tree結構中[22]，一組接入層和匯聚層的交換機成為一組機架（pod），每個機架中的接入層和匯聚層的交換機構成一個完全二分圖。交換機端口數(shù)是決定Fat-Tree結構中機架數(shù)目、每層交換機數(shù)目和連接服務器數(shù)目的唯一參數(shù)。若有k個端口，則此網(wǎng)絡結構中有k個機架，每個機架中有k/2個接入層交換機，k/2個匯聚層交換機，每個機架連接k2/4個核心層交換機和k2/4個服務器。這樣共有5×k2/4個交換機和k3/4個服務器。因此，在Fat-Tree結構中，位于第 j個服務器中的虛擬機處理第i個服務器中的數(shù)據(jù)結點所經(jīng)過的交換機數(shù)Cij為：

在文獻[8]的實驗中，數(shù)據(jù)中心內(nèi)的網(wǎng)絡結構上有1 024個服務器。將40個數(shù)據(jù)結點和120個虛擬機隨機放置在1 024個服務器的前16、64、256和1 024個服務器中，即實驗中數(shù)據(jù)結點和虛擬機的分布區(qū)間為[1,16]、[1,64]、[1,256]和[1,1 024]。在4種網(wǎng)絡結構上的不同分布區(qū)間，兩個服務器之間通訊經(jīng)過的最大交換機數(shù)如表2所示。

通訊延遲大小由經(jīng)過的交換機數(shù)和[0.9,1.1]之間的隨機數(shù)而決定。圖9的實驗結果表明，在VL2上，3-近似算法與2-近似算法所得到的最大通訊延遲相同，當數(shù)據(jù)結點和虛擬機的分布區(qū)間為[1,16]、[1, 256]和[1,1 024]時，NEW-VMA算法與兩種近似算法所得到的最大通訊延遲相同，在[1,64]區(qū)間上的最大通訊延遲降低了18.18%，在4個分布區(qū)間上的平均延遲降低了5.68%。

Table 2　Maximim number of switches between two racks表2　兩個服務器通訊經(jīng)過的最大交換機數(shù)

Fig.9　Maximum access latencies of 3 algorithms on VL2圖9　在VL2結構上3種算法的最大通訊延遲

在圖10中，實驗選擇的網(wǎng)絡結構為Tree結構，當數(shù)據(jù)結點與虛擬機的分布區(qū)間為[1,16]和[1,1 024]時，NEW-VMA算法與兩種近似算法所得到的最大通訊延遲相同；在[1,64]和[1,256]區(qū)間上，NEWVMA算法所得到最大訪問延遲較小。在4個分布區(qū)間上的平均通訊延遲降低了10.39%。

Fig.10　Maximum access latencies of 3 algorithms on Tree圖10　在Tree結構上3種算法的最大通訊延遲

圖11結果表明，在Fat-Tree結構上，當分布區(qū)間為[1,64]，[1,1 024]時，NEW-VMA算法與兩種近似算法所得到的解相同；在[1,16]和[1,256]區(qū)間上，NEW-VMA算法所得到最大訪問延遲較小。在4個分布區(qū)間上的平均通訊延遲降低了9.09%。

Fig.11　Maximum access latencies of 3 algorithms on Fat-Tree圖11　在Fat-Tree結構上3種算法的最大通訊延遲

圖12表明，在BCube中區(qū)間為[1,16]、[1,256]和[1,1 024]時所得到的最大通訊延遲相同，在[1,64]的分布區(qū)間上所得到的解較優(yōu)。在4個分布區(qū)間上的平均延遲降低了5.45%。3-近似算法將虛擬機分配問題松弛成3-近似問題，在求解問題時，即使數(shù)據(jù)結點與虛擬機之間的最大通訊延遲不超過閾值t，但處理數(shù)據(jù)的虛擬機與虛擬機之間的最大通訊延遲控制在2t內(nèi)，使得最大通訊延遲在3t范圍內(nèi)，最后得到的可行解的最大通訊延遲可能較大。

Fig.12　Maximum access latencies of 3 algorithms on BCube圖12　在BCube結構上3種算法的最大通訊延遲

實驗結果表明，在Tree、VL2、Fat-Tree和BCube 這4種網(wǎng)絡拓撲結構中3-近似算法與2-近似算法所得到的最大通訊延遲相同，本文算法在這4種網(wǎng)絡結構上平均情況下最大通訊延遲分別降低了10.39%、5.68%、9.09%和5.45%。

5　結束語

虛擬機分配是實現(xiàn)云中資源有效調度的首要考慮，有效的分配策略不僅可以減少通訊延遲，減少網(wǎng)絡帶寬消耗，還可以提高資源的利用率。本文針對虛擬機分配的最大通訊延遲問題，考慮了虛擬機之間互相通訊存在延遲的情況，提出了一種先判斷后找團再匹配的算法，較現(xiàn)有的算法，在運行時間和解的性能方面得到改進。在未來的工作中，還將考慮虛擬機之間互相通訊的不同模式。

[1]Alicherry M,Lakshman T V.Optimizing data access latencies in cloud systems by intelligent virtual machine placement[C]//Proceedings of the 32nd IEEE Conference on Computer Communications,Turin,Italy,Apr 14-19,2013. Piscataway,USA:IEEE,2013:647-655.

[2]Applying the cloud to big data storage[EB/OL].[2015-04-20].http://www.appistry.com/sites/default/files/downloads/.

[3]DeanJ,GhemawatS.MapReduce:simplifieddataprocessing on large clusters[J].Communications of the ACM,2008,51 (1):107-113.

[4]Li Xin,Wu Jie,Tang Shaojie,et al.Let?s stay together:towards traffic aware virtual machine placement in data centers[C]//Proceedings of the 33rd IEEE Conference on Computer Communications,Toronto,Canada,Apr 27-May 2, 2014.Piscataway,USA:IEEE,2014:1842-1850.

[5]Li Yunfa,Li Wanqing,Jiang Congfeng.A survey of virtual machine system:current technology and future trends[C]// Proceedings of the 3rd International Symposium on Electronic Commerce and Security,Guangzhou,China,Jul 29-31,2010.Piscataway,USA:IEEE,2010:332-336.

[6]Hyser C.McKee B,Gardner R,et al.Autonomic virtual machine placement in the data center[R].HPLaboratories,2008.

[7]Meng Xiaoqiao,Pappas V,Li Zhang.Improving the scalability of data center networks with traffic-aware virtual machine placement[C]//Proceedings of the 2010 IEEE Conference on Computer Communications,San Diego,USA, Mar 14-19,2010.Piscataway,USA:IEEE,2010:1-9.

[8]Kuo J J,Yang H H,Tsai M J.Optimal approximation algo-rithm of virtual machine placement for data latency minimization in cloud systems[C]//Proceedings of the 33rd IEEE ConferenceonComputerCommunications,Toronto,Canada, Apr 27-May 2,2014.Piscataway,USA:IEEE,2014:1303-1311.

[9]ZhengYang,CaiLizhi,HuangShidong,etal.VMscheduling strategies based on artificial intelligence in cloud testing [C]//Proceedings of the 15th IEEE/ACIS International Conference on Software Engineering,Artificial Intelligence,Networking and Parallel/Distributed Computing,Las Vegas, USA,Jun30-Jul2,2014.Piscataway,USA:IEEE,2014:1-7.

[10]Gibbons A.Algorithmic graph theory[M].Cambridge,UK: Cambridge University Press,1985.

[11]Miller G A.WordNet[EB/OL].Princeton University(2009) [2015-04-20].http://wordnet.princeton.edu.

[12]Bron C,Kerbosch J.Finding all cliquese on an undirected graph[J].Communications of theACM,1973,16(9):575-577.

[13]Kurose J F,Ross.K W,Computer networking:a top-down approach[M].5th ed.Boston,USA:Addison-Wesley Publishing Company,2009.

[14]Understanding switch latency[EB/OL].[2015-04-20].http:// www.cisco.com/en/US/prod/collateral/switches/ps9441/ps11541/ white paper c11-661939.html.

[15]Speed reduction by distance[EB/OL].[2015-04-20].http:// www.numion.com/calculators/Distance.html.

[16]Alicherry M,Lakshman T.Network aware resource allocation in distributed clouds[C]//Proceedings of the 2012 IEEE Conference on Computer Communications,Orlando,USA, Mar 25-30,2012.Piscataway,USA:IEEE,2012:963-971.

[17]van Lint J H,Wilson R M.A course in combinatorics[M]. Cambridge,UK:Cambridge University Press,2001.

[18]Hopcroft J E,Karp R M.An5/2algorithm for maximum matchings in bipartite graphs[C]//Proceedings of the 12th Annual Symposium on Switching and Automata Theory, East Lansing,USA,Oct 13-15,1971.Piscataway,USA:IEEE, 1971:122-125.

[19]Kim W Y,Kak A C.3-D object recognition using bipartite matching embedded in discrete relaxation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1991, 13(3):224-251.

[20]Burkard R E,Cela E.Linear assignment problems and extensions[M]//Handbook of Combinatorial Optimization:Supplement VolumeA.Springer US,1999:75-149.

[21]Guo Chuanxiong,Lu Guohan,Li Dan,et al.BCube:a high performance,server-centric network architecture for modular data centers[C]//Proceedings of the 2009 ACM SIGCOMM Conference on Data Communications,Barcelona,Spain,Aug 17-21,2009.NewYork,USA:ACM,2009:63-74.

[22]Leiserson C E,Fat-trees:universal networks for hardwareefficient supercomputing[J].IEEE Transactions on Computers, 1985,100(10):892-901.

GAO Renfei was born in 1990.She is an M.S.candidate at Tianjin Polytechnic University.Her research interests include data center and high performance architecture.

高任飛（1990—），女，河南商丘人，天津工業(yè)大學碩士研究生，主要研究領域為數(shù)據(jù)中心，高性能體系結構。

WU Jigang was born in 1963.He received the Ph.D.degree from University of Science and Technology of China in 2000.Now he is a chair professor at Guangdong University of Technology.His research interests include theoretical computer science and high performance architecture.

武繼剛（1963—），男，江蘇沛縣人，2000年于中國科學技術大學獲得博士學位，現(xiàn)為廣東工業(yè)大學計算機科學與技術學院特聘教授，主要研究領域為理論計算機科學，高性能體系結構。在國際重要學術期刊與會議上發(fā)表200余篇學術論文，主持國家自然科學基金課題、教育部博士點科研基金課題。

ZHOU Ying was born in 1979.She is a Ph.D.candidate at Tianjin Polytechnic University.Her research interests include high performance architecture and faults tolerance.

周瑩（1979—），女，天津人，天津工業(yè)大學博士研究生，主要研究領域為高性能體系結構，容錯設計。

ZHANG Yaoguo was born in 1990.He is an M.S.candidate at Tianjin Polytechnic University.His research interests include data center and faults tolerance.

張耀國（1990—），男，江蘇連云港人，天津工業(yè)大學碩士研究生，主要研究領域為數(shù)據(jù)中心，容錯設計。

Virtual MachineAssignment for Minimizing Data Latency?

GAO Renfei1,WU Jigang2+,ZHOU Ying1,ZHANG Yaoguo1
1.School of Computer Science and Software Engineering,Tianjin Polytechnic University,Tianjin 300387,China 2.School of Computer Science and Technology,Guangdong University of Technology,Guangzhou 510006,China +Corresponding author:E-mail:asjgwucn@outlook.com

In the modern data centers based on virtualization,virtual machine(VM)assignment is the primary research topic to efficiently schedule the cloud resources.In cloud systems,the big data are partitioned and then stored over several data nodes(DNs)for being processed by VMs.Thus,there is access latency among DNs and their assigned VMs.Meanwhile,the access latency among the pairs of assigned VMs also exists for the computing result collection.Different assignment strategies of VMs for DNs result in different maximum access latency.It has been proved that the assignment problem of VMs(VMA)to minimize the maximum access latency is of NP-hard.This paper proposes a new algorithm for VMA.The proposed algorithm initially determines if there exists enough number of VMs which can communicate with each other under a certain threshold limit in access latency.If yes,an efficient backtrack algorithm is then employed to find cliques consisted of VMs under this threshold.After that,the Hopcroft-Karp algorithm is used to assign the VMs in the clique for DNs,in order to save the computing time by significantly reducing the solution space.Extensive experimental results show that the maximum access latency is reduced 10.39%,5.68%,9.09%,5.45%on average,respectively,on the popular four network architectures,Tree,VL2,Fat-Tree and BCube,in comparison to the state-of-the-art approximation algorithms.

data center;virtual machine assignment;access latency;complete subgraph

2015-06,Accepted 2015-08.

10.3778/j.issn.1673-9418.1507043

A

TP302

*The Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20131201110002(高等學校博士學科點專項科研基金).

CNKI網(wǎng)絡優(yōu)先出版:2015-08-28,http://www.cnki.net/kcms/detail/11.5602.TP.20150828.1505.004.html