[發(fā)明專利]一種基于混合云調(diào)度模型的自動伸縮、費用優(yōu)化的內(nèi)容分發(fā)服務(wù)方法

在審

• 申請?zhí)枺?/td>: 201410306179.3
• 申請日: 2014-07-01
• 公開（公告）號: CN104065663A
• 公開（公告）日: 2014-09-24
• 發(fā)明（設(shè)計）人: 呂智慧;鄧達;吳杰
• 申請（專利權(quán)）人: 復(fù)旦大學(xué)
• 主分類號: H04L29/06
• 分類號: H04L29/06;H04L29/08
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;盛志范

1.一種基于混合云調(diào)度模型的自動伸縮、費用優(yōu)化的內(nèi)容分發(fā)服務(wù)方法，其特征在于具體步驟為：

第一步: 資源長期租用和預(yù)留

首先建立針對應(yīng)用的位置感知的資源租用模型，將整個問題轉(zhuǎn)換成一個帶限制條件的最優(yōu)化問題；然后針對模型，提出一個資源優(yōu)化租用算法，以降低系統(tǒng)運行的時間復(fù)雜度；

(1) 建立位置感知的資源租用模型

參考亞馬遜的EC2在全球不同地區(qū)的租用價格函數(shù)，將世界劃分成不同地區(qū)，滿足同一個地區(qū)的租用價格函數(shù)是相同的；一個地區(qū)可以是一個小的國家，或者是一個大的省；將A定義為所有地區(qū)的集合；假設(shè)全世界所有地區(qū)一共有N個數(shù)據(jù)中心，而他們的虛擬機、存儲以及網(wǎng)絡(luò)的租用價格函數(shù)分別是，，和，；

將每一個內(nèi)容文件的塊，記做一個內(nèi)容單元；假設(shè)應(yīng)用服務(wù)提供商可以提供的內(nèi)容一共有M個內(nèi)容單元；使用向量 ，記錄每一個內(nèi)容單元的存儲大小；另外，引入流的概念，定義流表示從地區(qū)發(fā)起的，請求內(nèi)容單元m的用戶請求數(shù)；算法的目標(biāo)是，在將每一道流分配給一個或多個云系統(tǒng)虛擬機的同時，保證服務(wù)的質(zhì)量，優(yōu)化租用成本；

引入來記錄流的性能，用來體現(xiàn)用戶接受到的服務(wù)情況；設(shè)表示一個時間比例，這個比例是數(shù)據(jù)中心n，能夠向地區(qū)，提供傳輸內(nèi)容單元m的時間，占整個傳輸時間的比例，并且在傳輸過程中，必須滿足一定的用戶體驗度；數(shù)據(jù)中心與用戶之間的距離越遠，越低；這樣，用一個人為設(shè)定的閾值，將所有的數(shù)據(jù)中心針對地區(qū)和內(nèi)容單元m劃分為兩個集合；定義，表示一個可行的數(shù)據(jù)中心集合，在中的數(shù)據(jù)中心，都可以向地區(qū)提供內(nèi)容單元m的服務(wù)，且服務(wù)的性能超過閾值；

定義N維向量為數(shù)據(jù)中心n向流提供的服務(wù)比例，希望找到每一個的值，滿足一定的用戶體驗，并且最小化整體成本；根據(jù)，分配各個用戶請求到不同虛擬機進行服務(wù)，并租用相應(yīng)的公有云資源；

為了建立更公式化的問題定義，引入一個指示隨機變量：當(dāng)數(shù)據(jù)中心n有內(nèi)容單元m時，為1，否則為0；

定義問題如下：

（1）

其中，，，分別計算每一個數(shù)據(jù)中心n所對應(yīng)的存儲大小，請求數(shù)，以及網(wǎng)絡(luò)流量；總代價C是各個數(shù)據(jù)中心的租用代價總和；

(2) 位置感知的資源租用計算

目標(biāo)是設(shè)計位置感知資源租用算法來最小化代價C；

問題(1)中，有一種賦值方法，使不是0就是1，并且這種賦值方法可以取得最小的C；

于是將原先的最小化問題轉(zhuǎn)化成一個賦值問題，即僅需要尋找一種0,1賦值方法，使得整個C最小；

目標(biāo)函數(shù)是凹函數(shù)，根據(jù)凸優(yōu)化理論，只需要評估在凸包的一些極值點的目標(biāo)函數(shù)值即可；為此引入一些數(shù)據(jù)結(jié)構(gòu)：

首先，引入一個映射函數(shù)AS，表示流與數(shù)據(jù)中心的映射；如果流f被分配給數(shù)據(jù)中心n服務(wù)，那么AS(f)=n，用一個的矩陣F來表示一個流，F(xiàn)的行表示地區(qū)，三列分別表示內(nèi)容單元索引，請求數(shù)以及網(wǎng)絡(luò)流量；使用表示內(nèi)容單元平均被下載的比例，一個請求數(shù)為r的流的矩陣表示如下形式：

流的矩陣F表示

將所有的內(nèi)容單元依據(jù)他們的塊大小進行排序，并用序號標(biāo)識，這樣，隨著內(nèi)容單元序號的遞增，其大小也是遞增的；

定義為一個的矩陣，只有第i個的矩陣是單位陣，其余均為0，矩陣：

定義是一個的矩陣，第n個的矩陣是F，其余都是0；代表將流F分配給數(shù)據(jù)中心n服務(wù)的結(jié)果，矩陣：

有了這些數(shù)據(jù)結(jié)構(gòu)后，位置感知的資源租用算法，記為 LARB，具體步驟為：

第1步，要找到所有的極值點

LARB搜尋所有解空間中的每一個與垂直的超平面；由于這些超平面可能會有重復(fù)，使用一個超平面集合HPs，將每一個超平面hpCandidate = 歸一化并記錄；如果它沒有重復(fù)，就將其加入到超平面集合；

第2步，計算每一個非重復(fù)超平面的一個內(nèi)部點P，并將它們記錄在集合Ps中；每一個內(nèi)部點將對應(yīng)一個極值點；

第3步，評估每一個可能的賦值解；對于每一個內(nèi)部點，將它分配給一個可行的數(shù)據(jù)中心n，這個數(shù)據(jù)中心將最小化P與的積，的值；當(dāng)賦值操作完成后，評估總體的代價，并選取一個最優(yōu)的賦值作為解；

第二步，資源負載預(yù)測計算

引入一個基于差分自回歸移動平均模型（ARIMA模型）的負載預(yù)測算法，用來預(yù)測每一個VM的使用負載情況以及用戶服務(wù)請求情況；每臺VM的CPU使用率，帶寬使用，以及流請求數(shù)作為模型的輸入，從而預(yù)測未來的情況；

ARIMA模型包括參數(shù)選擇p和q，平均值估計，隨機變量相關(guān)系數(shù)和白噪聲方差；

計算未來的需求一共有五個步驟；

定義和P分別表示在t時刻的觀測值和預(yù)測值；使用T表示預(yù)測的開始時刻，S表示預(yù)測的時長；開始時刻是當(dāng)前時刻；預(yù)測算法是用一系列觀測值 來預(yù)測未來的需求值 ；

首先測試數(shù)據(jù)是否具有平穩(wěn)性和能迅速降低自相關(guān)的函數(shù)；如果有，算法將繼續(xù)下一步；否則，使用差分的方法，將序列平滑化，直到它是變成穩(wěn)定的序列為止；然后，使用一個變換級數(shù)來表示數(shù)據(jù)零均值處理后的結(jié)果，這樣將預(yù)測轉(zhuǎn)化為，基于，預(yù)測；

接下來，針對預(yù)處理后的序列，計算自相關(guān)函數(shù)（ACF）和偏自相關(guān)函數(shù)（PACF），從而辨別采用AR，MA還是ARMA模型；

一旦數(shù)據(jù)被轉(zhuǎn)換到變換后的序列，并且序列可以被應(yīng)用到零均值的ARMA模型進行擬合后，接下來的問題是，面臨著選擇合適的p和q的值；本算法選擇被稱為AIC的 Akaike信息準(zhǔn)則；

在所有的參數(shù)都選擇好之后，做模型檢查以確保預(yù)測的精度；檢查一共有兩步，第一該模型的穩(wěn)定性和可逆性，第二殘差；如果檢查結(jié)果滿足所有的標(biāo)準(zhǔn)，便可以開始預(yù)測，否則，將會回到參數(shù)選擇和估計，并采取更細粒度的方式找到合適的參數(shù)；

當(dāng)所有的數(shù)據(jù)都適合模型后，對整個過程進行預(yù)測；

第三步，資源動態(tài)調(diào)整供應(yīng)

預(yù)測有兩種類型的預(yù)測誤差：估高和估低；估高意味著預(yù)測的值比實際的負載高，系統(tǒng)根據(jù)預(yù)測的負載將向云服務(wù)提供商租用更多的資源，而這些資源將不會被充分的利用，這將導(dǎo)致租賃費用的浪費；估低表示預(yù)測值比實際負載請求量更低，有一部分的請求無法獲得系統(tǒng)及時響應(yīng)，從而造成用戶體驗的下降；

考慮兩個方面，資源預(yù)測的不準(zhǔn)確和內(nèi)容未命中；

引入了虛擬機的三個狀態(tài)，分別是空閑，健康和負載過重即重載；如果虛擬機的CPU或者內(nèi)存使用率超過一個比例，就稱此虛擬機是重載的；如果虛擬機的CPU和內(nèi)存的使用率都低于一個比例，就稱此虛擬機是空閑的；其他情況下，稱此虛擬機是健康的；

在系統(tǒng)運行過程中，每一個虛擬機的狀態(tài)將被監(jiān)控；如果一個數(shù)據(jù)中心中重載的虛擬機比例超過時，算法將自動租用新的虛擬機；相反的，當(dāng)數(shù)據(jù)中心的空閑虛擬機比例超過時，算法會退還多余的虛擬機；

另一方面，當(dāng)用戶請求一個視頻，但所有可行的數(shù)據(jù)中心都沒有用戶請求的內(nèi)容文件，此情況被稱為內(nèi)容未命中；對此，用內(nèi)容的流行程度以及推和拉操作來進行改善：

受傳統(tǒng)的CDN網(wǎng)絡(luò)方法的啟發(fā)，系統(tǒng)給每一個新的內(nèi)容單元標(biāo)記流行程度，并根據(jù)LARB算法中的值來分發(fā)它，這是利用推的方式來防范；當(dāng)真正的內(nèi)容未命中發(fā)生時，還設(shè)計了一種拉的方式來處理，即使用一個貪婪算法，選擇一個對此用戶而言，代價最低的可行的數(shù)據(jù)中心，向這個數(shù)據(jù)中心傳輸用戶請求的內(nèi)容，使下一次不再發(fā)生內(nèi)容未命中情況；在此同時，選取一個對請求用戶而言，具有最高性能的數(shù)據(jù)中心，直接對用戶進行服務(wù)。