郝平

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

關(guān)鍵詞：網(wǎng)絡(luò)資源調(diào)度；QoS驅(qū)動；分組調(diào)度；云經(jīng)濟模型

DOI：10.3969/j.issn.1005-5517.2016.1.011

引言

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

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

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

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

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

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

（2）各種資源有不同的處理能力；

（3）一個資源在同一時刻只能處理一個任務(wù)；

（4）一個任務(wù)不能同時在兩個資源上處理；

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

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

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

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

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

（1）隨時接收客戶端的資源申請（客戶端申請中給出了資源需求）：

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

（a）按規(guī)劃進行任務(wù)刻錄；

（b）用戶需求為調(diào)度范疇，進行資源調(diào)度比對；

（c）按最佳匹配原則進行匹配；

（d）在調(diào)度周期內(nèi)確認有多少資源可以進行調(diào)度；

（e）計入運算結(jié)果；

（f）反饋給客戶。

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

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

3 仿真實驗

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

本文采用NS2仿真平臺進行仿真實驗、詳細仿真結(jié)果如表2所示。

3.2實驗結(jié)果對比

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

4 結(jié)束語

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

參考文獻：

[1]Gounder V.Prakash R，Abu-Amara H Micheline data miming：date and techniques[Cl.Wireless Communications and Systems，2014：1-6

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

[3]Ngai EWT.Hu Y.The application of data mining techniques in financial fraud detection：A dassification framework and an academic review of literature[J].Decision Support System，2011.50（3）：559-569

[4]Thelwall.Wilkinson D.Data mimng emotion in social network communication：Gender differences in MySpace[J].Journal of the American Sodety for Information Society for Information Science and Technology，2010，61（1）：190-199

[5]lcala-Fdez J.KEEL Data-Mining Software TooI：Data Set Repositoty .Integration of Algorithms and EXperimental Analysis Framework[Jl.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 Sdences 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 l，Kessdman C. Globus：A Metacomputing Infrastructure Toolkit. Intl J.Supercomputer Apphcations.1997，11（2）：115-128

[11]LEE W.A data mning 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 mimng[C]. Proc Int Conf Very Large Databases，1997：186-195