基于流量感知的虛擬機遷移調度算法

朱平哲

(三門峽職業(yè)技術學院 信息傳媒學院，河南 三門峽 472000)

在動態(tài)環(huán)境中，隨著時間的推移，總有新的虛擬機(virtual machine, VM)產生和消亡，不同VM的流量模式是動態(tài)的且隨時間變化。假設每個VM都有一個固定的執(zhí)行時間，即已知的先驗時間，目標是通過減少遷移數量和最小化數據中心(data center, DC)間的流量來優(yōu)化配置和進行遷移決策。因此，希望在保持系統(tǒng)性能穩(wěn)定的基礎上，盡可能地避免可能出現(xiàn)的鏈路擁塞問題。穩(wěn)定性與執(zhí)行的遷移次數成正比[1]，遷移次數越少越能提高系統(tǒng)的性能[2]。目前，學術界有關VM的研究很少涉及VM在配置和遷移決策中具有有限的租用期這一事實。文獻[3]提出了一種將DC總能耗降至最低的方案，文獻[4]提出了一種基于去激活的配置算法和一種周期性碎片整理算法，旨在最大限度地降低DC成本，文獻[5]提出了兩種VM調度算法來優(yōu)化虛擬機到物理機的映射，目的是減少累計的開機時間以節(jié)省能源，文獻[6]和文獻[7]給出了VM再調度的正式定義。然而，從整體上看，針對單臺物理機的閾值設置使數據中心整體負載過大，從而導致過多的VM找不到合適的物理機?；陟o態(tài)閾值的設定，由于物理機負載引起的瞬時峰值容易發(fā)生頻繁遷移導致了VM不必要的遷移，而通過預測模型獲得的預測值與真實值之間存在一定的誤差，可能會導致算法的性能差、系統(tǒng)能耗過高。此外，上述工作均沒有涉及流量感知VM的布局問題。因此，本算法主要提出VM實時遷移調度問題的靜態(tài)配置方案和啟發(fā)式動態(tài)解決方案，研究VM生命周期對遷移決策和系統(tǒng)穩(wěn)定性的影響。

1 問題描述

定義具有流量感知的虛擬機調度問題，涉及以下假設：

(1)時間被劃分為等長的時隙t∈[0…T]。

(2)每個VMi都有一個開始時間si和一個終止時間ei。VM的生命周期εi是固定的，并被視為輸入。需要注意的是，VM的生命周期εi定義為εi=ei-si。

(3)每個請求可能包括多個網絡VM，但VM的請求均是獨立的。

(4)假設VM的資源需求是靜態(tài)的。

(5)考慮一系列可能的遷移。

(6)為不同VM的遷移分配了保留帶寬。

(7)遷移可能需要若干個時隙。

1.1 靜態(tài)配置方案

給出以下決策變量：

假設Oi表示VMi∈V產生的總流量，可得到Oi=∑j∈Vdij,?i∈V。該公式的目標是最小化主干網流量，此流量包括通信流量和VM遷移生成的流量。這里的TS={?t∈T:t≤ei且t≥si}。

(1)

需要滿足以下條件：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

用式(12)替代約束條件(11)，可以得到

(13)

此外，還必須加上以下邏輯約束條件：

(14)

由于涉及大量的變量(O|N|4)，N表示問題的規(guī)模，式(14)顯然需要消耗大量時間和計算資源。因此，本研究提出了一種啟發(fā)式動態(tài)解決方案。

1.2 啟發(fā)式動態(tài)方案

啟發(fā)式動態(tài)算法的主要思想是通過考慮配置算法來減少遷移的次數，并在每個時隙的開始執(zhí)行該算法，以便找到被視為遷移候選的VM，然后將當前的配置方案與配置算法提供的新方案進行比較。事實上，配置算法會產生大量的遷移，而過度遷移將會導致云系統(tǒng)的性能大幅下降[8-9]。對于每個時隙，啟發(fā)式動態(tài)算法選擇到達的VM并刪除離開的VM，然后解決配置算法，可使用文獻[10]中提出的配置算法，該算法已被證明可以高效地在最小化主干流量的同時解決VM配置問題。然而，該算法既沒有考慮遷移成本，也沒有考慮VM的剩余生命周期，所以需要提供新的VM配置方案。啟發(fā)式動態(tài)算法計算了每個候選VM、遷移流量和通信流量，以確保所選VM值得遷移。此外，還對VM遷移是否違反DC容量限制進行了核實，遷移順序對主干網上的流量循環(huán)量也有重要影響。因此，本研究所提出的啟發(fā)式動態(tài)算法通過縮小規(guī)模，對將要遷移的VM列表進行了排序并執(zhí)行了遷移。該算法如下：

(1)ListVMs:所有的VM請求列表；

(2)S:所選擇的VM列表；

(3)L:將要遷移的VM列表；

(4)CandidateMig:將要遷移的候選VM列表；

(15)

(16)

(17)

2 實驗仿真

為了驗證本算法的有效性，在一臺擁有Intel Xeon 3.3 GHz CPU和8 GB內存的計算機上進行了仿真實驗，并使用商業(yè)解決方案CPLEX 12.5[11]來解決ILP問題。假設DC的數量為6，VM的開始時間和結束時間隨機生成，在24 h內執(zhí)行這些算法，并在每小時開始時進行一次結果采集，流量矩陣的數值為0～100，隨機生成。

2.1 啟發(fā)式動態(tài)算法的性能

為了評估啟發(fā)式動態(tài)算法的質量，將啟發(fā)式動態(tài)算法提供的解與文獻[10]中給出的配置算法提供的解進行了比較：

(18)

式中：Sh為啟發(fā)式動態(tài)算法提供的解；S*為文獻[10]提供的最優(yōu)解；G為兩種解之間的差距。

表1給出了兩種算法間的平均最優(yōu)差距G。不難發(fā)現(xiàn)，當VM數量為1 000、每個租戶占用的VM數量為20和80時，啟發(fā)式動態(tài)配置解決方案與靜態(tài)配置算法提供的解決方案間的差距分別為12.32%和12.00%。隨著VM數量的不斷增加，20個VM/租戶和80個VM/租戶的最優(yōu)差距并未出現(xiàn)等比例增加，相反，當VM數量達到4 000時，20個VM/租戶的差距反而比VM數量為2 000和3 000時要低。縱觀全部數據可知，啟發(fā)式動態(tài)配置解決方案與靜態(tài)配置算法提供的解決方案的差距最大不超過13.57%，這意味著啟發(fā)式動態(tài)配置解決方案與靜態(tài)配置算法提供的解決方案較為接近。然而，與靜態(tài)配置算法相比，啟發(fā)式動態(tài)算法在進行配置決策時考慮了VM生存周期和遷移成本。

表1 平均最優(yōu)差距Tab.1 Average optimality gap

2.2 系統(tǒng)穩(wěn)定性

將啟發(fā)式動態(tài)算法的遷移次數與文獻[10]中提出的最優(yōu)配置算法的遷移次數進行了比較。圖1至圖4給出了文獻[10]的VM配置模型和VM調度啟發(fā)式算法在24 h內執(zhí)行的遷移次數變化情況。不難發(fā)現(xiàn)，與啟發(fā)式算法獲得的遷移數量相比，配置算法產生的遷移數量十分巨大，且執(zhí)行的遷移數量隨著VM數量的增加而增加。在圖1中，當VM數量為2 000、20個VM/租戶時，配置算法產生的遷移數量基本維持在啟發(fā)式算法的4倍以上。在圖3中，配置算法產生的遷移數量相比圖1對應的數量幾乎增加了1倍，而啟發(fā)式算法的對應數值仍維持在較低的水平。在圖2、圖4中，隨著VM數量和每個租戶占用VM數量的增加，啟發(fā)式算法和配置算法的曲線趨勢類似，但在絕對數值上啟發(fā)式算法產生的遷移數量仍占有顯著優(yōu)勢。因此，在遷移決策過程中考慮VM的生存周期有助于提高系統(tǒng)的穩(wěn)定性，并防止執(zhí)行過度遷移。

圖1 兩種算法的VM遷移量(2 000個VM，20個VM/租戶)Fig.1 VM migration of two algorithms(2 000 VM,20 VM/tenant)

圖2 兩種算法的VM遷移量(2 000個VM，80個VM/租戶)Fig.2 VM migration of two algorithms(2 000 VM,80 VM/tenant)

圖3 兩種算法的VM遷移量(4 000個VM，20個VM/租戶)Fig.3 VM migration of two algorithms(4 000 VM,20 VM/tenant)

圖4 兩種算法的VM遷移量(4 000個VM，80個VM/租戶)Fig.4 VM migration of two algorithms(4 000 VM, 80 VM/tenant)

3 結語

通過對虛擬化服務的研究，討論了VM分層結構，并提出了VM的靜態(tài)和啟發(fā)式動態(tài)實例化方法。對啟發(fā)式動態(tài)配置解決方案與靜態(tài)配置算法提供的解決方案間的差距進行仿真實驗，將啟發(fā)式動態(tài)算法的遷移次數與文獻[10]提出的最優(yōu)配置算法的遷移次數進行比較，結果表明本算法具有良好的應用性能。VM動態(tài)實例化的改進方案是下一步努力和研究的方向，未來將嘗試把本研究成果拓展到云間環(huán)境，以優(yōu)化協(xié)作云的整體性能，包括實現(xiàn)或代理實現(xiàn)基礎設施中的管理程序組件以更有效地監(jiān)控模擬時間，并通過使用更高級的調度啟發(fā)式方法和算法來增強調度過程。