基于隊(duì)列理論的云資源分配收益最大化算法

鄭宇超 夏學(xué)文 艾冬梅

1(華東交通大學(xué)軟件學(xué)院 江西 南昌 330013) 2(北京科技大學(xué)數(shù)理學(xué)院 北京 100083)

基于隊(duì)列理論的云資源分配收益最大化算法

鄭宇超1夏學(xué)文1艾冬梅2

1(華東交通大學(xué)軟件學(xué)院 江西 南昌 330013)2(北京科技大學(xué)數(shù)理學(xué)院 北京 100083)

為了優(yōu)化資源分配收益，提出基于時間服務(wù)因子TSF資源定價機(jī)制下的資源分配算法。首先，算法將資源分配問題形式化為隊(duì)列模型，并構(gòu)建了收益最大化函數(shù)。然后，通過Lagrange乘子法求解最優(yōu)化函數(shù)的解。利用時間服務(wù)因子，算法分別通過安全滿意度因子ASF和響應(yīng)滿意度因子RSF定義了資源的定價方式，并同步考慮定價、請求到達(dá)率、資源服務(wù)率及可用資源量，得到了使收益最大化的資源分配方式。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的啟發(fā)式資源分配算法比較，該算法得到的收益更高，且尤其在云資源數(shù)量較稀少的場景下，算法將更加具有優(yōu)勢。

隊(duì)列理論 資源分配 云計算 收益最大化

0 引 言

云計算旨在通過虛擬化技術(shù)將IT資源整合成為大規(guī)模可擴(kuò)展的資源池，并且以Internet作為載體提供軟件(SaaS)、平臺(PaaS)及基礎(chǔ)設(shè)施(IaaS)等形式的服務(wù)[1]。以服務(wù)提供者角度來講，云計算可以為終端用戶提供池化的資源，提供者的目標(biāo)是租用各類服務(wù)并獲得收益。云服務(wù)的使用模式通常以預(yù)先支付或即付即用為主，用戶方只需要對請求服務(wù)或消費(fèi)服務(wù)進(jìn)行付費(fèi)[2]。服務(wù)提供過程中，服務(wù)等級協(xié)議SLA供求雙方協(xié)作的重要問題。消費(fèi)者主要通過服務(wù)質(zhì)量QoS參數(shù)明確請求服務(wù)的等級。SLA通常根據(jù)可用性、響應(yīng)時間等對資源分配的責(zé)任、擔(dān)?；蛐阅艿燃夁M(jìn)行具體描述。本文將以定價機(jī)制描述供求雙方需要服從的SLA。

對于服務(wù)提供者，在用戶服務(wù)實(shí)例間進(jìn)行合理資源分配對最終獲得收益是至關(guān)重要的，即使對于相同的資源分配，收益也會隨著不同的分配策略產(chǎn)生極大變化。因此，本文將重點(diǎn)關(guān)注于如何基于SLA和可度量的服務(wù)屬性，管理資源分配并提供可區(qū)分的性能等級，以便最大化收益。

相關(guān)研究中，文獻(xiàn)[3]將云資源配置多目標(biāo)優(yōu)化定義為博弈問題，以服務(wù)質(zhì)量和柔性指標(biāo)多目標(biāo)函數(shù)作為資源方和用戶方博弈雙方的收益函數(shù)，并通過GA算法對收益函數(shù)進(jìn)行了求解。文獻(xiàn)[4]對任務(wù)類型偏好與資源服務(wù)能力差異進(jìn)行了區(qū)分，在此基礎(chǔ)上提出了一種基于區(qū)分服務(wù)的演化博弈調(diào)度算法，可以極大提高用戶QoS。文獻(xiàn)[5]為了實(shí)現(xiàn)總利益最大化，通過建立服務(wù)提供商間的合作關(guān)系，提出了一種云資源分配的協(xié)作博弈模型。文獻(xiàn)[6]采用時間矩陣和費(fèi)用矩陣作為云任務(wù)效益的衡量指標(biāo)，提出一種基于效益博弈的資源動態(tài)可協(xié)調(diào)分配算法，通過構(gòu)建效益博弈模型，以一種動態(tài)協(xié)調(diào)機(jī)制對博弈進(jìn)行了求解。文獻(xiàn)[7]為解決資源競爭問題，提出通過建立用戶聯(lián)盟增加用戶效用，提高資源分配效率，但作者缺乏對模型的實(shí)驗(yàn)驗(yàn)證與分析。

不同于以上工作，本文的研究主要集中于：1)以隊(duì)列理論對云資源分配問題進(jìn)行建模，模型綜合考慮了資源量、請求到達(dá)率、服務(wù)時間及資源定價等QoS參數(shù)。2)基于時間服務(wù)設(shè)計了兩種定價機(jī)制下的資源分配算法，目標(biāo)是最大化資源提供收益。

1 系統(tǒng)模型

1.1 數(shù)學(xué)模型

假設(shè)云數(shù)據(jù)中心的服務(wù)器數(shù)量為N，服務(wù)提供者與m個用戶間以SLAs的形式簽訂服務(wù)協(xié)議，每個用戶(服務(wù)實(shí)例)可以通過服務(wù)器的資源分配獲得相應(yīng)服務(wù)。考慮分配給每個服務(wù)實(shí)例i的ni個服務(wù)器可作為一個超級服務(wù)器，超級服務(wù)器的能力正比于其服務(wù)器數(shù)量。設(shè)系統(tǒng)中的服務(wù)實(shí)例請求服從泊松分布，其平均服務(wù)到達(dá)率為λ，服務(wù)器對其處理時間服從負(fù)指數(shù)分布，其平均服務(wù)率為1/μ，其中，μ表示單位時間內(nèi)處理請求的數(shù)量。服務(wù)器對服務(wù)請求的執(zhí)行由于運(yùn)行環(huán)境的轉(zhuǎn)換需要付出代價，如：花費(fèi)時間從外部存儲中讀取新到用戶的相關(guān)數(shù)據(jù)，因此，與單個服務(wù)實(shí)例相關(guān)的一組服務(wù)器可構(gòu)建為基于FIFO的M/M/1隊(duì)列模型，定義服務(wù)強(qiáng)度ρ為請求到達(dá)率與單個服務(wù)器的服務(wù)率之比。系統(tǒng)模型的相關(guān)參數(shù)說明如表1所示。

(1)

表1 符號說明

1.2 基于定價模型的時間服務(wù)因子TSF

1.2.1 服務(wù)性能指標(biāo)

通常，云服務(wù)通過性能完成情況收取費(fèi)用。為了評估性能，通常有兩種與響應(yīng)時間相關(guān)的常用指標(biāo)：平均響應(yīng)時間MRT與時間服務(wù)因子TSF。其中，MRT是評估服務(wù)性能的常用指標(biāo)，但無法反映響應(yīng)時間出現(xiàn)大范圍波動的情況；而TSF可定義為確定時間間隔(時間槽)內(nèi)的服務(wù)百分比，不僅可以反映響應(yīng)時間，還可以精確描述響應(yīng)時間的分布。本文將TSF定義為一個二元組，其中，r表示響應(yīng)時間，a表示響應(yīng)時間低于r時的服務(wù)百分比，因此，a可視為一個安全因子。

基于用戶需求與TSF，本文設(shè)計了兩種指標(biāo)：安全滿意度因子ASF和響應(yīng)滿意度因子RSF。同時，ASF與RSF均可以反映獲取性能與用戶服務(wù)需求之間的偏差。根據(jù)TSF定義用戶需求為二元組，則需求的服務(wù)實(shí)例的ASF可表示為：

(2)

其中：a表示在響應(yīng)時間要求為R時實(shí)際獲取的安全因子，即響應(yīng)時間小于R時的服務(wù)率，fA表示實(shí)際獲取性能與用戶要求間的偏差。式(2)表明，若fA大于或等于0，獲取性能可滿足用戶要求，若獲取性能無法滿足用戶要求，則fA小于0。

同樣地，根據(jù)TSF定義用戶需求為，需求的服務(wù)實(shí)例的RSF為：

(3)

其中：r表示獲得的安全因子要求為A時的響應(yīng)時間。式(3)表明，若fR大于或等于0，獲取性能可滿足用戶要求，若獲取性能無法滿足用戶要求，則fA小于0。

為了計算在一個時間槽內(nèi)單個服務(wù)實(shí)例的第A個百分位響應(yīng)時間，需要：

1) 記錄單個服務(wù)實(shí)例在一個時間槽內(nèi)所有服務(wù)對應(yīng)所有響應(yīng)時間；

2) 對以上所有記錄進(jìn)行升序排列；

3) 選擇有序序列中第A個記錄作為最終結(jié)果。

1.2.2 定價模型

本文基于ASF和RSF設(shè)計了兩種需求驅(qū)動的資源定價模型。將服務(wù)實(shí)例的服務(wù)提供時間劃分為固定步長的時間段，如表示用戶的計劃需求，可以根據(jù)ASF和RSF獲得其服務(wù)性能。若獲得的服務(wù)性能滿足用戶需求，服務(wù)按基準(zhǔn)價格付費(fèi)。若獲得的服務(wù)性能無法滿足需求，服務(wù)提供者將按基準(zhǔn)價格進(jìn)行懲罰?；鶞?zhǔn)價格b由服務(wù)實(shí)例的屬性決定，具體計算方法見下節(jié)。

根據(jù)ASF和RSF定義以下兩種定價模型：

(4)

或

(5)

其中：服務(wù)提供價格B分別表示fA與fR的線性函數(shù)。兩種定價模型如圖1所示。

圖1 基于時間服務(wù)因子的定價模型

1.2.3 基準(zhǔn)價格

根據(jù)M/M/1模型的隊(duì)列理論，服務(wù)滯留時間的累積分布時間為：

w(t)=1-e(λ-μ)t

(6)

假設(shè)需求為的服務(wù)實(shí)例被分配n臺服務(wù)器，將代入式(6)：

A=1-e(λ-nμ)R

(7)

(8)

式(8)表明n臺服務(wù)器可確保用戶性能需求。若假設(shè)c表示單位資源的預(yù)期邊際收益，則b為來自n臺服務(wù)器的預(yù)期收益：

(9)

由于服務(wù)請求到達(dá)率是動態(tài)變化的，可通過采樣統(tǒng)計獲取平均到達(dá)率。

2 資源分配最優(yōu)化

2.1 基于ASF的資源分配最優(yōu)化

假設(shè)服務(wù)實(shí)例i分配ni臺服務(wù)器，其性能需求為，安全因子為服務(wù)請求響應(yīng)時間小于或等于Ri的概率，由式(6)，安全因子ai可表示為：

ai=1-e(λi-niμi)Ri

(10)

將式(10)代入式(2)，服務(wù)實(shí)例i的性能由指標(biāo)ASF表示為：

(11)

根據(jù)定價模型式(4)，服務(wù)實(shí)例i的服務(wù)提供獲得的平均收益為：

(12)

則單位時間內(nèi)服務(wù)實(shí)例i獲得的總收益為：

(13)

因此，最優(yōu)化問題可形式為：

(14)

構(gòu)造Lagrange函數(shù):

(15)

其中：λ表示Lagrange乘子。

令dL/dni=0，i=0,1,2,…,m，則:

(16)

(17)

將式(17)代入式(14)中的約束條件中：

(18)

(19)

將式(19)代入式(17)，則：

(20)

假設(shè)每個服務(wù)實(shí)例的請求到達(dá)率以式(6)建立模型，然而，只有當(dāng)服務(wù)實(shí)例請求到達(dá)率小于服務(wù)處理速率時式(6)才是有效的。否則，基于FIFO隊(duì)列的響應(yīng)時間將無法收斂，且響應(yīng)時間會隨著時間增加。因此，只有當(dāng)?shù)竭_(dá)率小于服務(wù)處理速率時，式(20)才成立。

λi

(21)

ni>ρi

(22)

圖1(a)表明若ai等于Ai，收益將不再增長。因此，一旦響應(yīng)需求被滿足，對于服務(wù)實(shí)例i則無須繼續(xù)增加資源量。由式(8)可知：

(23)

因此，式(22)與式(23)分別表示服務(wù)實(shí)例i對資源請求的下限與上限。

2.2 基于RSF的資源分配最優(yōu)化

假設(shè)服務(wù)實(shí)例i分配ni臺服務(wù)器，其性能需求為，設(shè)服務(wù)實(shí)例i的Ai響應(yīng)時間為ri。根據(jù)式(6)，有：

ai=1-e(λi-niμi)ri

(24)

服務(wù)實(shí)例i的第Ai個響應(yīng)時間為：

(25)

將式(25)代入式(5)，服務(wù)實(shí)例i的性能為：

(26)

根據(jù)定價模型式(5)，服務(wù)實(shí)例i的服務(wù)提供獲得的平均收益為：

(27)

則單位時間內(nèi)服務(wù)實(shí)例i獲得的總收益為：

(28)

因此，最優(yōu)化問題可形式為：

(29)

構(gòu)造Lagrange函數(shù)：

(30)

其中：λ表示Lagrange乘子。

令dL/dni=0，i=0,1,2,…,m，

(31)

(32)

將式(32)代入式(29)中的約束條件：

(33)

(34)

將式(34)代入式(32)，則:

(35)

基于同樣的原因，式(32)與式(35)分別表示服務(wù)實(shí)例i對資源請求的下限與上限。

3 實(shí)驗(yàn)分析

本節(jié)通過仿真實(shí)驗(yàn)對算法性能進(jìn)行分析，實(shí)驗(yàn)工具為CloudSim[9]。實(shí)驗(yàn)中分別以合成數(shù)據(jù)集與追蹤數(shù)據(jù)集作為兩種服務(wù)請求類型進(jìn)行實(shí)驗(yàn)測試。選擇文獻(xiàn)[10]中的Heuristic算法作為比較，服務(wù)收益作為算法性能比較的主要指標(biāo)。ASF與RSF算法分別表示基于ASF與RSF的最優(yōu)分配算法。相關(guān)參數(shù)與取值如表2所示。

表2 合成數(shù)據(jù)集測試參數(shù)

3.1 合成數(shù)據(jù)集測試分析

圖2和圖3表示三種算法在不同的定價機(jī)制下服務(wù)器資源量與收益間的關(guān)系。實(shí)驗(yàn)中時間間隔設(shè)置為1小時。可以看出，ASF與RSF算法均優(yōu)于Heuristic算法。當(dāng)服務(wù)器數(shù)量為70和80時，Heuristic算法得到的收益分別比ASF算法低75.5%和16.2%，服務(wù)器數(shù)據(jù)為70時，RSF算法收益比Heuristic算法高53.4%。同時，隨著服務(wù)器數(shù)量的增加，Heuristic算法的曲線走勢基本與ASF與RSF算法是接近的。當(dāng)服務(wù)器數(shù)量到達(dá)90后，三種算法的收益接近相等，這主要是由于當(dāng)云數(shù)據(jù)中心有充足的服務(wù)器資源提供給服務(wù)實(shí)例時，大多數(shù)服務(wù)實(shí)例將分配以上限值定義的相同資源量。明顯地，當(dāng)資源量相對不充足時，ASF與RSF算法具有更加明顯的優(yōu)勢。因此，當(dāng)資源量較少或服務(wù)實(shí)例量較大時，ASF與RSF算法可以優(yōu)化資源分配得到更大的收益。

圖2 ASF定價下的收益

圖3 RSF定價下的收益

3.2 追蹤數(shù)據(jù)集測試分析

追蹤數(shù)據(jù)集選取文獻(xiàn)[11]中互聯(lián)網(wǎng)HTTP請求WWW服務(wù)器的相關(guān)數(shù)據(jù)集，如表3所示。本文將追蹤時間劃分為時間槽，步長為5 min。執(zhí)行過程中，將每個時間槽中的到達(dá)請求進(jìn)行統(tǒng)計，并根據(jù)先前記錄預(yù)測下一時間槽的平均到達(dá)率，預(yù)測機(jī)制可形式化為：

λpost=λ+(λ-λpre)

(36)

其中：λpost表示下一時間槽的到達(dá)率，λpre和λ分別表示前一個時間槽的測量到達(dá)率和當(dāng)前時間槽的測量到達(dá)率。

表3 追蹤元數(shù)據(jù)

對于每個服務(wù)實(shí)例，服務(wù)器被劃分為10組，每組作為一個FIFO等待隊(duì)列。每個時間槽結(jié)束時，系統(tǒng)根據(jù)下一時間槽預(yù)測的到達(dá)率，重新在服務(wù)實(shí)例間進(jìn)行資源分配。具體參數(shù)如表4所示。

表4 追蹤數(shù)據(jù)集測試參數(shù)

圖4和圖5表明實(shí)驗(yàn)中部署90個服務(wù)器時每5 min收益變化的情況。總體看來，ASF與RSF算法均是優(yōu)于Heuristic算法的。ASF與Heuristic算法每5 min的平均收益約為8.2 k＄和1.6 k＄，ASF算法約是Heuristic算法的4倍。RSF與Heuristic算法每5 min的平均收益約為8.7 k＄和6.6 k＄，前者約比后者高32%。同時可以看出，當(dāng)資源量較少或服務(wù)實(shí)例量較大時，ASF與RSF算法可以優(yōu)化資源分配得到更大的收益。在第47個時間槽時ASF與RSF算法的收益急劇減少，甚至低于Heuristic算法，這主要是由于服務(wù)到達(dá)率極端波動變化導(dǎo)致的。正如圖6中，在第42至45個時間槽時到達(dá)率正在降低，而在46個時間槽又急劇增加。因此，通過式(36)預(yù)測到達(dá)率并非一定準(zhǔn)確，可能會導(dǎo)致資源分配的不合理。同時，由于ASF和RSF算法的準(zhǔn)確性及Heuristic算法可能出現(xiàn)的不合理性，ASF和RSF算法將更加依賴于對到達(dá)率準(zhǔn)確的預(yù)測。

圖4 ASF算法的收益進(jìn)化過程

圖5 RSF算法的收益進(jìn)化過程

圖6 服務(wù)請求到達(dá)

4 結(jié) 語

為了促進(jìn)終端用戶與服務(wù)提供者之間的協(xié)作關(guān)系，基于SLA形式的時間服務(wù)因子TSF，提出了基于定價機(jī)制的收益最大化算法。算法以隊(duì)列理論建立了服務(wù)到達(dá)與服務(wù)提供模型，并通過Lagrange乘子法構(gòu)建了最優(yōu)化目標(biāo)函數(shù)，并對函數(shù)進(jìn)行了求解。實(shí)驗(yàn)結(jié)果表明，所提算法性能優(yōu)于傳統(tǒng)啟發(fā)式分配算法，尤其在資源短缺的云計算環(huán)境下，算法具有更加明顯的優(yōu)勢。

[1] Cusumano M. Cloud computing and SaaS as new computing platform[J].Communication of the ACM, 2011,53(4):27-29.

[2] Guo L, Zhao S, Shen S,et al. Task scheduling optimization in cloud computing based on heuristic algorithm[J].Journal of Networks, 2012,7(3):547-553.

[3] 蘇凱凱,徐文勝,李建勇. 云制造環(huán)境下基于非合作博弈的資源優(yōu)化配置方法[J].計算機(jī)集成制造系統(tǒng),2015,21(8):2228-2239.

[4] 李陶深,張希翔. 云計算下區(qū)分服務(wù)的演化博弈調(diào)度算法[J]. 北京郵電大學(xué)學(xué)報,2013,36(1):41-45.

[5] 朱匆,劉元君,彭自然,等. 移動云計算中基于協(xié)作式博弈模型的資源分配方案[J].計算機(jī)應(yīng)用研究,2014,31(3):912-916.

[6] 李衛(wèi)平，武海燕，楊杰. 基于效益博弈的云計算資源動態(tài)可協(xié)調(diào)分配策略研究[J].計算機(jī)工程與科學(xué)，2016,38(1):57-61.

[7] Ergu D, Kou G, Peng Y,et al. The analytic hierarchy process: task scheduling and resource allocation in cloud computing environment[J]. The Journal of Supercomputing, 2013,64(3):835-848.

[8] Xu Zhongsheng, Shen Subin. A multi-objective optimization scheduling method in cloud computing[J]. Microcomputer Its Application, 2015,34(13):17-20.

[9] Rodrigo C, Rajiv R, Anton B, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J]. Software: practice and experience, 2011,41(1):23-50.

[10] Mazzucco M. Revenue maximization problems in commecial data centers[D].PhD Thesis,University of Newcastle, Newcastle,UK,2014.

[11] Internet Traffic Archive[OL]. 2011-8-23. Http://ita.ee.lbl.gov/html/traces.html.

PROFITMAXIMIZATIONALGORITHMFORCLOUDRESOURCEALLOCATIONBASEDONQUEUETHEORY

Zheng Yuchao1Xia Xuewen1Ai Dongmei2

1(SchoolofSoftware,EastChinaJiaotongUniversity,Nanchang330013,Jiangxi,China)2(SchoolofMathematicsandPhysics,UniversityofScienceandTechnologyBeijing,Beijing100083,China)

For optimizing the profit of resource allocation, a resource allocation algorithm in resource pricing mechanism based on time service factor is proposed. First, the resource allocation problem was formalized as the queue model, and the profit maximization function was constructed. Then, the profit maximization function was solved by Lagrange multiplier method. Using the time service factor, our algorithm defined the pricing mode respectively by the assurance satisfaction factor and responded satisfaction factor. In addition, resource allocation was maximized by considering pricing, request arrival rates, resource service rates, and available resources. Experimental results show that compared with the traditional heuristic allocation algorithm, our algorithm yields higher returns, especially in the context of the scarcity of cloud resources. The proposed algorithm will have more advantages.

Queue theory Resource allocation Cloud computing Profit maximization

2017-01-09。江西省教育廳科研項(xiàng)目(GJJ150539)。鄭宇超，講師，主研領(lǐng)域：云計算及應(yīng)用。夏學(xué)文，副教授。艾冬梅，高工。

TP393

A

10.3969/j.issn.1000-386x.2017.11.047