朱平哲

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

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

1 問(wèn)題描述

定義具有流量感知的虛擬機(jī)調(diào)度問(wèn)題，涉及以下假設(shè)：

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

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

(3)每個(gè)請(qǐng)求可能包括多個(gè)網(wǎng)絡(luò)VM，但VM的請(qǐng)求均是獨(dú)立的。

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

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

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

(7)遷移可能需要若干個(gè)時(shí)隙。

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

給出以下決策變量：

假設(shè)Oi表示VMi∈V產(chǎn)生的總流量，可得到Oi=∑j∈Vdij,?i∈V。該公式的目標(biāo)是最小化主干網(wǎng)流量，此流量包括通信流量和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表示問(wèn)題的規(guī)模，式(14)顯然需要消耗大量時(shí)間和計(jì)算資源。因此，本研究提出了一種啟發(fā)式動(dòng)態(tài)解決方案。

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

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

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

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

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

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

(15)

(16)

(17)

2 實(shí)驗(yàn)仿真

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

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

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

(18)

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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