[發(fā)明專利]基于網(wǎng)絡(luò)感知的虛擬機(jī)調(diào)度與再調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201410539326.1
• 申請日: 2014-10-13
• 公開（公告）號: CN104298539B
• 公開（公告）日: 2017-09-22
• 發(fā)明（設(shè)計(jì)）人: 羅剛毅;錢柱中;陸桑璐
• 申請（專利權(quán)）人: 南京大學(xué)
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06F9/50
• 代理公司: 江蘇圣典律師事務(wù)所32237
• 代理人: 賀翔

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)中心中虛擬機(jī)調(diào)度的方法，具體是一種基于網(wǎng)絡(luò)感知的虛擬機(jī)調(diào)度與再調(diào)度方法。

背景技術(shù)

隨著虛擬化技術(shù)的發(fā)展以及云計(jì)算概念的普及，越來越多的用戶選擇通過向數(shù)據(jù)中心租用計(jì)算資源的方式來完成其工作任務(wù)而非自己購買物理設(shè)備。為提高資源利用率，如何高效的將用戶請求的資源合理調(diào)度到各個(gè)物理服務(wù)器上是數(shù)據(jù)中心的管理者需要解決的重要問題之一。高效的虛擬機(jī)調(diào)度策略能夠提高數(shù)據(jù)中心的資源利用率，降低運(yùn)行時(shí)能耗。現(xiàn)有調(diào)度算法綜合考慮了虛擬機(jī)在CPU、內(nèi)存和網(wǎng)絡(luò)方面的需求，合理部署虛擬機(jī)，以期最小化計(jì)算、存儲與網(wǎng)絡(luò)的代價(jià)。然而，當(dāng)前的虛擬機(jī)調(diào)度策略沒有動(dòng)態(tài)的考慮虛擬機(jī)之間網(wǎng)絡(luò)通信流量的變化，也沒有考慮由于虛擬機(jī)退出所造成的資源利用率下降與網(wǎng)絡(luò)延遲上升的問題。

發(fā)明內(nèi)容

本發(fā)明為了解決現(xiàn)有技術(shù)中調(diào)度策略的不足，提供了一種基于網(wǎng)絡(luò)感知的虛擬機(jī)調(diào)度與再調(diào)度方法，通過適當(dāng)?shù)奶摂M機(jī)遷移，提高部署在虛擬機(jī)上任務(wù)的性能以及數(shù)據(jù)中心整體的網(wǎng)絡(luò)通信效率。

本發(fā)明包括虛擬機(jī)的初次調(diào)度和再調(diào)度，所述的初次調(diào)度包括以下步驟：

1)獲取當(dāng)前數(shù)據(jù)中心的全局狀態(tài)和用戶請求的初始狀態(tài)；

2)判斷有無初始通信矩陣T^k,若有初始T^k，則轉(zhuǎn)入步驟3)，否則轉(zhuǎn)入步驟4)；

3)根據(jù)初始通信矩陣T^k進(jìn)行聚類，使用Stoer-Wagner算法將該組虛擬機(jī)分成兩個(gè)小組，使得這兩個(gè)小組之間的通信流量最小，對每個(gè)小組都執(zhí)行步驟4)；其中，Stoer-Wagner算法是一個(gè)計(jì)算圖最小割問題的常用算法，具體算法參見Stoer,Mechthild,and Frank Wagner."A simple min-cut algorithm."Journal of the ACM(JACM)44.4(1997):585-591。

4)將這組或這類虛擬機(jī)部署到能夠容納他們并且網(wǎng)絡(luò)結(jié)構(gòu)樹的高度最低的一組物理機(jī)上,如果部署不成功，則返回步驟3)，進(jìn)行再次聚類。當(dāng)全部的分組都部署成功時(shí)，輸出部署的結(jié)果：一種可行的虛擬機(jī)部署方式

所述的再調(diào)度包括以下步驟：

1)比較當(dāng)前數(shù)據(jù)中心的狀態(tài)與歷史狀態(tài),當(dāng)出現(xiàn)虛擬機(jī)退出或虛擬機(jī)之間的網(wǎng)絡(luò)通信矩陣發(fā)生明顯改變時(shí),進(jìn)入步驟2),否則休息一段時(shí)間,返回步驟1)；

2)計(jì)算每個(gè)用戶/任務(wù)的優(yōu)先值Priority，并按降序排序，存入隊(duì)列P_Queue，進(jìn)入步驟3)；

3)當(dāng)隊(duì)列P_Queue非空時(shí)，依次取出隊(duì)頭元素,記為G_t，進(jìn)入步驟4),當(dāng)P_Queue為空時(shí),進(jìn)入步驟6)；

4)嘗試將G_t中的虛擬機(jī)移動(dòng)至同一機(jī)架的物理機(jī)上,若成功,則返回步驟3),否則，進(jìn)入步驟5)；

5)將G_t中的虛擬機(jī)按照面向機(jī)架的虛擬機(jī)貪心聚集的步驟進(jìn)行調(diào)度,調(diào)度完成后,返回步驟3)；

6)輸出再調(diào)度的結(jié)果返回步驟1)。

所述的再調(diào)度方法的步驟2)中每個(gè)用戶/任務(wù)的優(yōu)先值Priority的計(jì)算方法如下：設(shè)用于部署該任務(wù)的第k組虛擬機(jī)為G_k，其數(shù)量為w_k個(gè)，其中每個(gè)虛擬機(jī)為第k組虛擬機(jī)G_k之間的點(diǎn)對點(diǎn)網(wǎng)絡(luò)通信流量矩陣為T^k，矩陣中的每一項(xiàng)為虛擬機(jī)和虛擬機(jī)通信所經(jīng)過的路由層數(shù)為則其中為數(shù)據(jù)通信所經(jīng)過的路由層數(shù)的函數(shù)，X為虛擬機(jī)當(dāng)前部署方式。

所述的再調(diào)度方法的步驟5)中面向機(jī)架的虛擬機(jī)貪心聚集過程包括以下步驟：

1)對該組虛擬機(jī)按其所在機(jī)架進(jìn)行分組至進(jìn)入步驟2)。

2)對于每個(gè)計(jì)算其中的每個(gè)虛擬機(jī)分別與其他機(jī)架上虛擬機(jī)通信的總和與本機(jī)架上其他虛擬機(jī)通信總和的差對按降序排序，將值大于0的分組存入隊(duì)列Q_j，當(dāng)所有Q都為空時(shí)，過程退出，否則進(jìn)入步驟3)。

3)如果Q_j非空，則取出對頭元素進(jìn)入步驟4),否則返回步驟2)。

4)如果對應(yīng)的小組所在的機(jī)架能夠容納虛擬機(jī)則將遷移至所在的機(jī)架,回到步驟2),否則返回步驟3)。

本發(fā)明有益效果在于：通過實(shí)時(shí)監(jiān)控各組虛擬機(jī)之間的網(wǎng)絡(luò)通信流量、整個(gè)數(shù)據(jù)中心的運(yùn)行狀態(tài)以及分析歷史數(shù)據(jù),調(diào)度控制器對原來的虛擬機(jī)部署進(jìn)行再次調(diào)度，提高了部署在虛擬機(jī)上任務(wù)的性能以及數(shù)據(jù)中心整體的網(wǎng)絡(luò)通信效率。

附圖說明

圖1為虛擬機(jī)初次調(diào)度流程圖