基于多維云用戶驅(qū)動(dòng)QOS網(wǎng)絡(luò)資源調(diào)度算法

摘要：本文在云經(jīng)濟(jì)模型的基礎(chǔ)上，提出一種受用戶級QoS驅(qū)動(dòng)的分組調(diào)度算法。該算法基于對云QoS的屬性分析，對經(jīng)濟(jì)云現(xiàn)有的DBC調(diào)度算法進(jìn)行了擴(kuò)展和改進(jìn)。在滿足任務(wù)的截止期限和預(yù)算的范圍內(nèi)，根據(jù)任務(wù)是否具有高網(wǎng)絡(luò)帶寬進(jìn)行分組。通過把基于用戶專有的QoS的需求加入到常規(guī)分組調(diào)度算法中，從而形成了一個(gè)基于網(wǎng)絡(luò)帶寬的分組調(diào)度算法。仿真結(jié)果顯示：在模擬的云環(huán)境下，本文算法擁有較高的吞吐量和任務(wù)完成率。

引言

　　目前大多數(shù)云計(jì)算環(huán)境下的調(diào)度和資源管理問題一般仍使用傳統(tǒng)形式，即由調(diào)度構(gòu)件如Glbous根據(jù)確定的花費(fèi)函數(shù)來決定任務(wù)應(yīng)在哪里執(zhí)行，但這些花費(fèi)函數(shù)一般都以系統(tǒng)為中心的，難以通過用戶的QoS參數(shù)如存取價(jià)格、服務(wù)傳送時(shí)間片等驅(qū)動(dòng)。在經(jīng)濟(jì)管理模型下，不同的系統(tǒng)當(dāng)然不會(huì)花費(fèi)同樣的價(jià)格來存取相同的資源。終端用戶也不一定想要支付最高的價(jià)格來獲得最有效的資源利用，而是有可能基于需求、價(jià)值、優(yōu)先權(quán)和可供使用的預(yù)算協(xié)商一個(gè)特定的價(jià)格^[1]。此外，QoS是一個(gè)綜合指標(biāo)，不同應(yīng)用的側(cè)重不同，在計(jì)算密集型任務(wù)當(dāng)中，QoS往往反映資源的運(yùn)算速度，而在一些數(shù)據(jù)密集型的任務(wù)當(dāng)中，QoS較多地表示節(jié)點(diǎn)之間的帶寬、節(jié)點(diǎn)數(shù)據(jù)的質(zhì)量等指標(biāo)^[2]。在經(jīng)濟(jì)學(xué)方法中，調(diào)度決定不是靜態(tài)地由單個(gè)調(diào)度實(shí)體來完成，而是由終端用戶的要求直接驅(qū)動(dòng)^[2]。一個(gè)常規(guī)的經(jīng)濟(jì)模型，一般關(guān)注的是運(yùn)行應(yīng)用的軟件和硬件花費(fèi)，而經(jīng)濟(jì)模型主要對最終用戶的服務(wù)收取費(fèi)用^[3]。在競爭的經(jīng)濟(jì)市場中，基于用戶需求和可供使用資源的交易是主要驅(qū)動(dòng)力。

　　對此，本文提出了一種面向任務(wù)交易成本和截止期限的分組任務(wù)調(diào)度策略。該策略優(yōu)先選取用戶級具有高網(wǎng)絡(luò)帶寬要求的任務(wù)進(jìn)行調(diào)度，根據(jù)交易價(jià)格和平均價(jià)格的比較將任務(wù)分成兩組，在可用資源列表中對兩組任務(wù)分別進(jìn)行時(shí)間優(yōu)化和花費(fèi)優(yōu)化調(diào)度。最后測試了本文算法的調(diào)度性能。

1 系統(tǒng)模型假設(shè)

　　在競爭的經(jīng)濟(jì)市場中，基于用戶需求和可供使用資源的交易是主要驅(qū)動(dòng)力。因此，我們關(guān)注的是單個(gè)用戶在云中與其它用戶以及云服務(wù)提供者和資源擁有者的競爭。

　　云需要合適的資源管理模型使成員有效地共享資源。本文采用計(jì)算經(jīng)濟(jì)模型與用戶交互的管理方式，向用戶的任務(wù)提供服務(wù)質(zhì)量保證。云環(huán)境中的QoS有一系列的規(guī)范，包括資源響應(yīng)時(shí)間、可用性、安全性、吞吐量等^[6]。本文選擇在費(fèi)用(Cost)，期限(Deadline)和任務(wù)執(zhí)行的可靠性(Reliability)這三維QoS約束下調(diào)用有限的資源來滿足不同云用戶的請求。調(diào)度者和用戶需求被公式化為效用函數(shù)、和，分別代表用戶選擇QoS選擇產(chǎn)生的效益，根據(jù)每一個(gè)效益函數(shù)提供定量計(jì)算QoS的數(shù)學(xué)方法。調(diào)度問題可以推廣為多個(gè)不同長度的任務(wù)在多個(gè)不同資源上的調(diào)度問題。同時(shí)約定：

　　(1)進(jìn)行調(diào)度的一組任務(wù)是互相獨(dú)立，即任務(wù)之間沒有通信和數(shù)據(jù)依賴^[6];

　　(2) 各種資源有不同的處理能力;

　　(3)一個(gè)資源在同一時(shí)刻只能處理一個(gè)任務(wù);

　　(4)一個(gè)任務(wù)不能同時(shí)在兩個(gè)資源上處理;

　　(5)任務(wù)一旦運(yùn)行，運(yùn)行該任務(wù)的資源被獨(dú)占，只能等到任務(wù)完成后，再執(zhí)行別的任務(wù)。

　　對資源的調(diào)用要遵從市場經(jīng)濟(jì)模式，當(dāng)云中有N個(gè)任務(wù)和M個(gè)可用資源時(shí)，網(wǎng)絡(luò)資源調(diào)度策略在N個(gè)任務(wù)和M個(gè)資源之間進(jìn)行匹配，使得既可以滿足用戶的要求和云資源約束，又可以使完成任務(wù)目標(biāo)代價(jià)最優(yōu)或近似最優(yōu)^[7]。提出任務(wù)的客戶端希望找到能夠滿足用戶要求的資源使任務(wù)執(zhí)行的時(shí)間最短而且價(jià)格最低^[8]。提供資源的工作端希望自己的資源能夠充分利用，盡量減少空閑資源的時(shí)間，提高資源的利用率，增加自己的經(jīng)濟(jì)效益^[9]。

　　假設(shè)某一時(shí)刻云用戶向系統(tǒng)提交了N個(gè)任務(wù)，每個(gè)任務(wù)的長度為Li，用指令數(shù)來度量，單位為MI百萬指令，截止期限D(zhuǎn)eadline以及可以支付的最大預(yù)算Budget值(由用戶指定)如下表所示，任務(wù)按照長度從大到小的順序進(jìn)行排序。

　　初始狀態(tài)下云系統(tǒng)中存在的M個(gè)可用資源的處理速度以及各個(gè)資源的性能開銷參數(shù)列表如下，其中Vi表示每個(gè)資源的處理速度，Ci表示資源R每百萬條指令的執(zhí)行開銷(Cost/MI)。資源按照處理速度從大到小的順序進(jìn)行排序。新資源因?yàn)檫€未分配任務(wù)，所以它的任務(wù)列表為空;若某一資源的任務(wù)列表不為空，則稱這個(gè)資源是舊的。將所有到達(dá)的任務(wù)分配給新資源，若此時(shí)沒有新資源可用則將任務(wù)分配給舊資源。初始時(shí)刻，全部資源都是新的，把長度最大的任務(wù)T0分配給處理速度最快的資源R0，計(jì)算執(zhí)行的時(shí)間和開銷是否超出了用戶可以承受的Deadline和Budget，如果未超過則將T0加入R0的任務(wù)列表，否則考慮下一個(gè)可用的新資源。同時(shí)將該資源從新資源列表中刪除，加入舊資源列表，并將其標(biāo)志為舊資源，反復(fù)進(jìn)行此過程，直到全部的任務(wù)都被調(diào)度或調(diào)度失敗。調(diào)度的目標(biāo)是找到能夠在期望的執(zhí)行時(shí)間內(nèi)完成工作任務(wù)、而且所付出的費(fèi)用相對比較廉價(jià)的資源，即時(shí)間和費(fèi)用是最優(yōu)的^[10]。

　　基于多QoS規(guī)劃模型進(jìn)行資源分配和任務(wù)調(diào)度的算法描述如下:

　　(1)隨時(shí)接收客戶端的資源申請(客戶端申請中給出了資源需求);

　　(2)在每一個(gè)長度為T的時(shí)間段內(nèi)開始執(zhí)行以下算法步驟：

　　(a)按規(guī)劃進(jìn)行任務(wù)刻錄;

　　(b)用戶需求為調(diào)度范疇，進(jìn)行資源調(diào)度比對;

　　(c)按最佳匹配原則進(jìn)行匹配;

　　(d)在調(diào)度周期內(nèi)確認(rèn)有多少資源可以進(jìn)行調(diào)度;

　　(e)計(jì)入運(yùn)算結(jié)果;

　　(f)反饋給客戶。

2 基于多維云用戶驅(qū)動(dòng)QoS網(wǎng)絡(luò)資源調(diào)度

　　在一個(gè)三維的QoS模型空間中對此調(diào)度問題進(jìn)行研究。模型空間由運(yùn)行費(fèi)用(C)，截止期限(D)和可靠性(R)構(gòu)成。其中C代表花費(fèi)Cost，執(zhí)行云任務(wù)時(shí)的花費(fèi)包括處理計(jì)算資源和網(wǎng)絡(luò)(傳輸帶寬)資源的花費(fèi);D代表截止期限D(zhuǎn)eadline：處理云任務(wù)的全部時(shí)間;R代表可靠性Reliability：完成任務(wù)的概率。

　　云任務(wù)i可以使用資源代理j的計(jì)算資源：(表示資源的處理時(shí)間)，如果j的計(jì)算能力為Cj，則相應(yīng)的資源分配約束條件為 。i執(zhí)的時(shí)間上限。任務(wù)代理i支付給計(jì)算資源代理j的報(bào)酬為，那么代表了第j個(gè)計(jì)算資源代理完成所有任務(wù)獲得的全部報(bào)酬。

　　考慮模型的效益函數(shù)，第一維效益函數(shù)，是和費(fèi)用有關(guān)的：

(1)

：資源預(yù)算，是i為獲得計(jì)算資源付出的總代價(jià);表示第一維QoS的權(quán)重。

　　第二維QoS效益函數(shù)是和執(zhí)行時(shí)間有關(guān)的：

(2)

T_i是i的執(zhí)行截止時(shí)間;b_in是完成第n個(gè)工作需要的計(jì)算資源數(shù)量;D代表延遲時(shí)間;代表分配到第二維QoS的權(quán)重;

　　第三維效益函數(shù)代表調(diào)度的可靠性：

　; (3)

　　g：在截止期限內(nèi)完成調(diào)度的任務(wù)數(shù)，f：在截止期限內(nèi)總共提交的任務(wù)數(shù)。

　　任務(wù)的效用函數(shù)是這三部分的加權(quán)函數(shù)：

(4)

　　整個(gè)系統(tǒng)的效用函數(shù)

(5)

　　網(wǎng)絡(luò)資源調(diào)度者的目標(biāo)是在QoS約束下為i進(jìn)行資源分配，最大化系統(tǒng)效益并滿足：

(6)

　　在經(jīng)濟(jì)模型下最大化任務(wù)代理獲得的效用，使用拉格朗日數(shù)學(xué)方法求得多維QoS約束的網(wǎng)絡(luò)資源調(diào)度問題的最優(yōu)解：在時(shí)間期限內(nèi)，最優(yōu)化任務(wù)代理：

(7)

　　在資源市場上，計(jì)算資源作為資源供應(yīng)者，考慮到任務(wù)代理愿意付出的代價(jià)，試圖最大化它們的收益：。這樣，云資源供應(yīng)者的最優(yōu)化問題可被公式化為，且

　　由以上對QoS進(jìn)行量化的效益函數(shù)表達(dá)式可知，完成時(shí)間和花費(fèi)QoS是負(fù)QoS參數(shù)，其它屬性的QoS參數(shù)是正QoS參數(shù)。所謂的負(fù)QoS參數(shù)是指QoS值越大，其效益函數(shù)值越小，正QoS參數(shù)是指QoS值越大，其效益函數(shù)值越大，見圖1。

　　再利用拉格朗日乘數(shù)法求解在多QoS約束條件下的最優(yōu)解，構(gòu)造以下的輔助函數(shù)：

(8)

　　令，就可以得到最優(yōu)化任務(wù)代理問題的最優(yōu)解，表示任務(wù)代理在約束時(shí)間條件下為了最大化系統(tǒng)效益應(yīng)該付出的價(jià)值;

　　再來考慮對資源代理的優(yōu)化：且，求約束條件下的最優(yōu)解，構(gòu)造拉格朗日函數(shù)：

(9)

　　令，可以求得計(jì)算資源代理優(yōu)化問題的最優(yōu)解，表示計(jì)算資源代理作為資源供應(yīng)者，為了最大化它的收入希望分配給任務(wù)代理的的單元個(gè)數(shù)。

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

3.1 仿真參數(shù)設(shè)置

　　本文采用NS2仿真平臺進(jìn)行仿真實(shí)驗(yàn)，詳細(xì)仿真結(jié)果如表2所示。

3.2 實(shí)驗(yàn)結(jié)果對比

　　圖 2、圖3顯示了本文算法與DBC算法在完成任務(wù)效率上的比較。依圖2可知，滿足要求的任務(wù)個(gè)數(shù)隨著deadline的增加而增加，但DBC算法的deadline增加到2400以后，完成的任務(wù)個(gè)數(shù)保持在一個(gè)數(shù)值不再增加，這是因?yàn)橥瓿傻娜蝿?wù)已經(jīng)用完了用戶提供的budget，增加deadline的值對任務(wù)的完成數(shù)沒有影響，這符合計(jì)算經(jīng)濟(jì)網(wǎng)格中的交易原則;在期限固定的情況下，隨著預(yù)算的增加，對于任務(wù)的完成情況，本文都比傳統(tǒng)DBC優(yōu)化算法有一些提高，說明本文算法提高了截止期限內(nèi)的任務(wù)完成率(任務(wù)的可靠性)。由圖3可知，滿足要求的任務(wù)個(gè)數(shù)隨著budget的增加而增加，但是本文算法的提升速度更快，這是由于本文算法采用拉格朗日計(jì)算方式，在Dealine固定的時(shí)候，能夠更有效地提高資源調(diào)度效率，從而在一定截止時(shí)間內(nèi)完成的任務(wù)數(shù)更多。

4 結(jié)束語

　　本文對基于經(jīng)濟(jì)模型的云網(wǎng)絡(luò)資源調(diào)度問題進(jìn)行了詳細(xì)的介紹，分析了使用經(jīng)濟(jì)原則和交易議價(jià)的優(yōu)點(diǎn)，認(rèn)為它能夠更好地適應(yīng)現(xiàn)代網(wǎng)格的發(fā)展。在對網(wǎng)格傳統(tǒng)的調(diào)度算法進(jìn)行研究的基礎(chǔ)上，根據(jù)現(xiàn)代網(wǎng)格基于市場經(jīng)濟(jì)模型進(jìn)行資源管理的特點(diǎn)，提出了一種基于多維云用戶驅(qū)動(dòng)QoS網(wǎng)絡(luò)資源調(diào)度算法。通過合適的分組機(jī)制有效地降低了經(jīng)濟(jì)代價(jià)，具有一定的部署價(jià)值。

參考文獻(xiàn)：

　　[1]Gounder V, Prakash R, Abu-Amara H. Micheline data miming: date and techniques[C]. Wireless Communications and Systems, 2014: 1-6

　　[2]胡自林,徐云, 毛濤. 基于效益最優(yōu)的云網(wǎng)絡(luò)資源調(diào)度. 計(jì)算機(jī)工程與應(yīng)用, 2014, 7: 69-70

　　[3]Ngai EWT,Hu Y.The application of data mining techniques in financial fraud detection :A classification framework and an academic review of literature[J]. Decision Support System, 2011, 50(3):559-569

　　[4]Thelwall ,Wilkinson D.Data mining emotion in social network communication:Gender differences in MySpace[J].Journal of the American Society for Information Society for Information Science and Technology, 2010, 61(1):190-199

　　[5]lcala-Fdez J.KEEL Data-Mining Software Tool:Data Set Repositoty ,Integration of Algorithms and Experimental Analysis Framework[J].Journal of Multiple -Valued Logic $Soft Computing,2011,12(17):204-209

　　[6]Bal M.Rough Sets Theory as Symbolic Data Mining Method:An Application on Complete Decision Table[J].information Sciences Letters,2013,2(1):111-116.

　　[7]Yang K,Shahabi C.An efficient k nearest neighbor search for multivariate time series[M].Information and Computation,2013: 65-98

　　[8]JolliffeD, Tran T, Nguyen T. Data mining network coding [J]. IEEE Trans. on Vehicular Technology, 2009, 58(2): 914-925

　　[9]Ester P, Sander S.A key efficient way of data mining techniques[C]. Michine and Systems，2014.:74-79

　　[10]Foster I, Kesselman C. Globus: A Metacomputing Infrastructure Toolkit. Intl J. Supercomputer Applications.1997, 11(2):115 - 128

　　[11]LEE W.A data mining framework for constructing features and models for instrusion detection systems[D]. New York Computer Science Department of Columbia University，2012: 33-76

　　[12]Wang W,Yang J. A statistical information grid approach to spatial data mining[C]. Proc Int Conf Very Large Databases，1997:186-195

本文來源于中國科技期刊《電子產(chǎn)品世界》2016年第1期第41頁，歡迎您寫論文時(shí)引用，并注明出處。