基于多維云用戶(hù)驅動(dòng)QOS網(wǎng)絡(luò )資源調度算法

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

引言

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

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

1 系統模型假設

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　(e)計入運算結果;

　　(f)反饋給客戶(hù)。

2 基于多維云用戶(hù)驅動(dòng)QoS網(wǎng)絡(luò )資源調度

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

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

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

(1)

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

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

(2)

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

　　第三維效益函數代表調度的可靠性：

　; (3)

　　g：在截止期限內完成調度的任務(wù)數，f：在截止期限內總共提交的任務(wù)數。

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

(4)

　　整個(gè)系統的效用函數

(5)

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

(6)

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

(7)

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

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

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

(8)

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

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

(9)

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

3 仿真實(shí)驗

3.1 仿真參數設置

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

3.2 實(shí)驗結果對比

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

4 結束語(yǔ)

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

參考文獻：

　　[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ò )資源調度. 計算機工程與應用, 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

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