可靠性感知下的虛擬數據中心映射算法
網絡與通信
作者：左成 虞紅芳
摘要：介紹現階段虛擬數據中心（VDC）映射的研究進展，根據租戶對VDC可靠性的需求，提出一種可靠性感知下的VDC映射啟發式算法。對於每個VDC，該算法通過限製能放置在同一個服務器上的最大虛擬機數目來保證租戶VDC可靠性需求，然後以降低數據中心網絡帶寬消耗和服務器能耗為主要目標進行VDC映射。其具體做法是：首先將相互之間帶寬需求量大的虛擬機合並部署來降低數據中心網絡帶寬的消耗；然後把合並後的虛擬機優先部署到已開啟的服務器上，從而減少開啟的服務器數目，降低數據中心的服務器能耗。利用基於胖樹結構的數據中心拓撲對提出的算法進行了仿真，結果表明，與2EM算法相比，該算法能夠滿足租戶VDC的可靠性需求，能在不增加額外能耗的前提下最多減少數據中心網絡約30%的帶寬消耗。
關鍵詞：可靠性；帶寬消耗；虛擬數據中心映射；能耗；胖樹
中圖分類號： TP393.01 文獻標誌碼：A
Abstract： By introducing the current research progress of Virtual Data Center （VDC） embedding， and in accordance with the reliability requirement of VDC， a new heuristic algorithm to address reliabilityaware VDC embedding problem was proposed. It restricted the number of Virtual Machines （VMs） which can be embedded onto the same physical server to guarantee the VDC reliability， and then regarded reduction of the bandwidth consumption and energy consumption as main objective to embed the VDC. Firstly， it reduced bandwidth consumption of data center by consolidating the virtual machines， which had high communication services， into the same group and placed them onto the same physical server. Secondly， the consolidated groups were mapped onto the powered physical servers to decrease the number of powered servers， thus reducing the power consumption of servers. The results of experiment conducted on fat tree topology show that， compared with 2EM algorithm， the proposed algorithm can satisfy VDC reliability requirement， and effectively reduce a maximum of 30% bandwidth consumption of data center without increasing extra energy consumption.
Key words： reliability； bandwidth consumption； virtual data center embedding； power consumption； fat tree
0 引言
在雲計算時代，隨著社會對計算需求的不斷擴大，數據中心的規模也在迅速變大。但是，在龐大的數據中心背後，其資源的平均利用率卻相對較低，大部分設備空閑，給數據中心增加了巨大的能耗負擔[1]。目前，數據中心中使用虛擬化技術，可以有效提高數據中心資源利用率。在這種新趨勢下，每個租戶的資源請求可抽象為一組虛擬機（Virtual Machine，VM）構成的虛擬數據中心（Virtual Data Center，VDC）[2]，每個VM對應一定的計算資源（包括CPU、內存以及硬盤等）；同時為了傳遞數據和中間文件，VM之間需要建立具有帶寬保障的通信鏈路，以滿足VM之間的通信需求。由於VM放置與VM間通信帶寬的路由的緊耦合，使得把VDC映射到數據中心的這個過程變得非常複雜。
虛擬網絡（Virtual Network，VN）映射問題[3]與VDC映射問題很類似，在VN映射上已有許多研究，但VDC映射的研究還較少。VDC映射與VN映射不同的是：在映射VN時，每個物理服務器上隻能映射一個VM，而映射VDC時，每個物理服務器上可以同時映射多個VM。因此現有的VN映射算法並不能直接用於解決VDC映射問題[4]。
Guo等[4]提出的SecondNet算法解決了VDC映射的帶寬保障問題，它可以在一定程度上提高數據中心網絡的利用率；但是由於SecondNet算法在一個服務器上隻能映射一個VM，所以網絡資源利用率仍然較低，VM之間的帶寬需求會造成數據中心帶寬的巨大消耗。Fuerst等[5]提出的LOCO算法利用對VM進行自動分組的方式來提高網絡資源利用率。與SecondNet算法相比，LOCO算法提高了數據中心網絡的利用率和VDC的映射成功率；但是由於LOCO算法把VDC中的VM盡可能合並映射，所以VDC的可靠性無法得到保障。Luo等[6]提出的2EM算法首次以節能為目標來進行VDC映射。2EM算法對LOCO算法進行了優化，使得能關閉的空閑服務器和鏈路盡可能多；但是2EM也是把VM盡可能合並映射，所以VDC的可靠性也無法保障。
從前麵分析可知，現有的VDC映射算法還未涉及可靠性問題。本文提出一個可靠性感知的VDC（ReliabilityAware Virtual Data Center，RAVDC）映射算法來解決可靠性感知下的VDC映射問題。RAVDC算法會首先保證VDC的可靠性需求，然後以減少帶寬消耗和降低能耗為主要目標進行VDC映射。
1 問題描述
1.1 可靠性感知下的VDC映射問題
VDC是一係列虛擬資源的組合，主要包括：虛擬機、虛擬交換機、虛擬路由器以及虛擬鏈路[2]。在雲數據中心中的主要挑戰是VDC映射問題，其主要目標是找到虛擬資源到物理資源的映射來提高數據中心的資源利用率。除此之外，VDC映射還需要考慮可靠性、帶寬保障和能耗等其他目標，以便VDC算法能應用於實際生產環境。
VDC映射問題中的可靠性是指在有單個服務器失效時，VDC中仍然有效的虛擬機數目占VDC中總虛擬機數目的百分比。
可靠性給VDC映射增加了新的挑戰，提高可靠性要求VDC映射時VM盡量分散部署，而減少帶寬消耗則要求VDC中的VM盡量集中部署，所以可靠性和帶寬消耗是相互矛盾的目標。
降低能耗要求開啟的服務器數目少，這就要求盡可能集中放置VM。
所以減少帶寬消耗和降低能耗的實現方式都是盡可能集中放置VM，從而使得如果能減少帶寬消耗，就能相應降低能耗。降低能耗不是本文的主要目標，本文的研究重點是解決可靠性和帶寬消耗之間的矛盾。
本文用G（V，A）表示數據中心，其中：V表示數據中心的節點集合，A表示數據中心網絡的鏈路集合；
節點分為交換機和服務器，交換機集合用W表示，服務器集合用S表示。
用Gk（Vk，Ak）表示第k個VDC請求，其中：Vk表示VDC的VM集合，Ak表示VDC中VM之間的虛擬鏈路集合。
對於每個VDC請求，VM的需求為一定數量的虛擬CPU（virtual CPU，vCPU），虛擬鏈路的需求為一定數量的帶寬。
1.2 可靠性模型
數據中心中的失效域[7]有多種類型，主要包括服務器、櫃頂（Top of Rack， TOR）交換機、彙聚交換機和供電設備等，本文隻考慮服務器失效，並使用最壞情況有效率作為可靠性指標。最壞情況有效率是指在最壞情況下發生單個失效時，VDC中仍然有效的VM數目占VM總數目的百分比。
1.3 帶寬消耗模型
當有帶寬需求的VM映射到同一物理服務器上時，這些VM間的通信可以由物理服務器的hypervisor完成，不需要占用額外的數據中心網絡帶寬資源。隻有在不同物理服務器上的VM間需要通信時，才會占用網絡帶寬資源。本文將使用一個簡單的模型來衡量VDC映射方案的帶寬消耗。
顯然，從帶寬消耗角度看，VM應該盡可能多地整合放置到同一物理服務器。但這樣會導致這個物理服務器失效時，有大量的VM失效，從而無法保障租戶的可靠性需求。因此，如何協調可靠性和帶寬消耗間的矛盾是本文要解決的關鍵問題。
2 RAVDC算法
由於單純的VDC映射已經是NPHard問題，因此本文針對可靠性感知下的VDC映射問題提出了啟發式算法RAVDC。
RAVDC算法采用迭代的方式，首先從VDC所有未映射的VM中找出帶寬資源節約最多的K個VM（K是虛擬機整合門限，這K個VM與VDC中其他VM之間的總帶寬需求最小）作為一組，然後把這一組作為一個整體放置到某個物理服務器上，直到VDC被成功映射時停止迭代。
RAVDC算法需要使用兩個重要的數據結構：M和U，M表示VDC中已映射的VM集合，U表示VDC中待映射的VM集合。在完成一個VM u（u∈U）映射到服務器的工作之後，需要映射VM u和已映射VM v（v∈M）之間的所有虛擬鏈路。映射虛擬鏈路時，是找u和v所在服務器之間的一條滿足虛擬鏈路帶寬需求的路徑。當把所有的虛擬鏈路映射完成之後，RAVDC算法會把u加入到M之中。初始時，M=，U=Ak。