馬 浩 陶 鵬 李 鵬 劉林青 趙 佩

1(國網河北省電力有限公司營銷服務中心 河北 石家莊 050000) 2(國網河北省電力有限公司 河北 石家莊 050000)

0 引 言

作為與信息、軟件和互聯網相關的服務,云計算集成了大量資源和服務,并將其交付到互聯網上。客戶可以根據需要獲得這些資源和服務,而無須考慮硬件的維護和管理。由于其卓越的特性,可以提高客戶工作的效率和體驗,并減少大量的設備開支和人力支出。而云服務供應商為了維持云計算的運行,將按使用付費的定價模型向客戶收取必要的費用[1]。

通常,根據不同參與者的目的,可以將云計算環(huán)境視為三層結構,它由基礎結構提供者、云服務提供者和客戶組成。基礎設施提供商維護物理設備,并通過采用虛擬化技術將其用于構建動態(tài)資源池。云服務供應商從基礎設施提供商那里租用資源,并相應地支付租賃費用,同時,他們構建了用于向客戶提供服務的云計算平臺。客戶根據自身的需求在平臺上搜尋解決方案,并根據數量和質量對提供的服務收費。作為基礎設施提供商和客戶之間的鏈接,云服務供應商非常重要[2]。此外,效益是云計算平臺正常運行的基礎,它包括來自客戶的收入和基礎設施提供商的成本。

研究人員對市場需求、云計算平臺中的參數配置、定價方式等眾多影響云服務供應商效益的因素進行了研究。考慮到以客戶為導向的服務需求是云計算管理機制的基礎,此外,服務質量和服務價格是客戶最關心的問題,因此,在所有這些因素中,云計算平臺中參數的最佳配置和定價模型是最重要的[3]。但是,高質量的服務始終會給云服務供應商帶來高昂的成本,這將迫使他們提高服務價格以賺取效益,相反,低廉的服務價格會導致服務質量下降。因此,對于云服務供應商而言,解決增加服務質量和降低服務價格之間的權衡以最大化效益至關重要。文獻[4]研究了在云計算環(huán)境中實現效益最大化的最佳多服務器配置問題,服務器的數量和執(zhí)行速度被視為確定多服務器系統(tǒng)配置的基本特征。但是,這些方法很少關注單一多服務器系統(tǒng)中的效益最大化方案,只能采用這種方法來滿足一種服務請求。

對于串聯結構下的多級多服務器隊列系統(tǒng),每個系統(tǒng)都被視為M/M/m排隊模型,每個階段可以在唯一的多服務器系統(tǒng)中服務一種類型的服務請求,該請求對應于客戶發(fā)布的子任務。對于耐心有限的客戶,云服務供應商應在云計算平臺中配置參數,以盡可能滿足客戶的需求,但是,由于能源支出和租金成本的增長,成本也會增加。因此,如何優(yōu)化配置參數以在截止時間約束下最大化效益是一個重要的問題。此問題包括三個子問題:如何按照序列結構對多級多服務器隊列系統(tǒng)進行建模;如何確定客戶在多級多服務器隊列系統(tǒng)中等待的總時間;如何通過在截止時間約束下配置云計算平臺來實現效益的最大化。

在考慮多級多服務器系統(tǒng)中的效益最大化問題時,相關研究主要集中在具有并行結構的多服務器系統(tǒng)上。文獻[5]考慮了具有多條并行生產線的制造系統(tǒng)中的生產設計和調度問題,并通過適當配置一些參數(例如建議的生產率、生產時間間隔等),提出了效益最大化方案。文獻[6]解決了相同的并行機器調度問題,其中包含工作截止時間和機器資格約束,以最大限度地減少總的工作完成時間。由于在這些方法中多級多服務器系統(tǒng)以并行結構排列,可以同時滿足多種類型的服務請求。但是,他們忽略了所有服務請求(子任務)之間的內部關系,導致必須成功滿足某些服務請求(子任務)才能滿足客戶發(fā)布的任務。因此,研究串聯結構的多級多服務器排隊系統(tǒng)中的效益最大化問題至關重要。在考慮具有多階段排隊系統(tǒng)時,文獻[7]分析了具有不同服務時間分布的異構服務的兩個階段,這些階段受到隨機故障和帶有一般休假期的強制性服務器休假的影響。討論了隊列中的平均客戶數和平均等待時間。文獻[8]研究了一個多階段隊列系統(tǒng),該系統(tǒng)具有一定數量的獨立并行服務器,并且在所有或某些階段都具有多個隊列,并提供了一種有效的方法來管理隊列,從而在不增加成本的情況下最大化客戶滿意度。所有這些方法主要集中在解決一個階段中具有單個服務器的隊列系統(tǒng)中的問題,而較少集中于一個階段中包含多個服務器的情況。

由此本文提出計及等待時長的云計算效益模型,考慮以串聯結構排列的多級多服務器隊列系統(tǒng),分析每級多服務器系統(tǒng)中云服務供應商的收入和成本模型,并建立效益最大化模型。根據客戶可以等待的最大容忍度,在截止期限約束下定義效益最大化問題,并采用啟發(fā)式算法來求解這一模型,從而實現效益最大化和客戶等待時間的多目標優(yōu)化。通過算例仿真,分析了效益和已執(zhí)行服務請求的百分比隨期限和服務請求到達率的增加而變化。

1 數學模型

1.1 云計算架構

為了研究云計算環(huán)境中服務和應用程序的供求關系,需要考慮服務器提供商、云服務供應商和客戶的行為特征。對于服務器提供商,他們采用虛擬化技術來聚合各種IT資源(計算、網絡、存儲等),并將其提供給遠程互聯網客戶的需求。此外,此類IT資源具有可伸縮性,因此可以根據客戶的需求進行調整。典型的情況是服務器的數量和執(zhí)行速度,這對于不同的應用程序是可變的。

對于云服務供應商,他們致力于在服務器提供商和客戶之間建立渠道,從而使客戶無須關注服務請求的具體實施細節(jié)。實際上,云服務供應商從基礎設施提供商那里租用資源,并構建云計算平臺以向客戶提供服務。對于客戶,他們將服務請求提交給云服務供應商,并根據指定的服務級別協議為所提供的服務付費。

1.2 多級多服務器隊列系統(tǒng)模型

通常,當客戶發(fā)布任務時,可以始終將其分為多個子任務,并且這些子任務的執(zhí)行順序應遵循連續(xù)的邏輯關系。本文假設每個子任務對應一種服務請求,可以在唯一的多服務器系統(tǒng)中進行服務。在此基礎上,我們考慮一個云計算平臺,多級多服務器隊列系統(tǒng)由nM/M/m排隊模型組成,它們以串聯結構排列。對于每級多服務器系統(tǒng)Si,它具有速度為si的多臺服務器,其中i=1,2,…,n。一旦客戶發(fā)布任務,則當某些服務器可用時,第一個子任務(或第一類服務請求)將立即在第一級多服務器系統(tǒng)中得到服務。當完成第一階段時,在第一階段之后的多服務器系統(tǒng)將在隨后的階段中依次服務于后者的子任務(服務請求)。不失一般性地,我們將多級多服務器隊列系統(tǒng)視為簡化形式,其中此類系統(tǒng)只有兩個級,即n=2,而這種簡化形式可以很容易地推廣到一般情況。

(1)

(2)

由于兩級多服務器系統(tǒng)是按串聯結構排列的,因此只有在第一級中服務第一類服務請求時,客戶才能將第二類服務請求發(fā)送到后者中的多服務器系統(tǒng)。那么我們可以發(fā)現第一級多服務器系統(tǒng)的起飛時間等于第二級多服務器系統(tǒng)的起飛時間,因此,可以認為后階段服務請求的到達率等于前階段服務請求的平均服務率,據此將平均服務費率描述為期望形式,如式(3)所示。

(3)

實際上,可以發(fā)現平均服務速率也等于同一階段的到達速率。給定條件ρ1<1以確保隊列系統(tǒng)的遍歷性,從長遠來看,無須等待就可以響應第一級多服務器系統(tǒng)的傳入服務請求。但是,這樣的點在很小的時間間隔內是不正確的,這導致傳入的服務請求本質上是一種隨機流,這可能導致偶爾的流量突發(fā)暫時使服務器不堪重負。在此基礎上,當多服務器系統(tǒng)中的所有服務器都被執(zhí)行的服務請求占用時,則新到達的服務請求必須在等待隊列中等待。在這種情況下,將其概率表示如下:

(4)

令Wi為第i類服務請求的等待時間,相應的概率分布函數可以描述如下[8]:

(5)

u(t)是脈沖函數:

(6)

令z→∞,則有:

(7)

1.3 效益模型

在本文中,我們選擇等待時間來表示服務質量的差異,對于第一和第二多服務器系統(tǒng)中服務請求的服務收費函數定義如下:

(8)

(9)

式中:a1、a2是常數,代表每單位服務的服務費用;D是服務請求可以等待的最大可允許時間。

本文中假定當等待時間不超過最大值時,云服務供應商向客戶收取一定的費用。對于給定的兩階段多服務器系統(tǒng),可以將這種假設分為三種情況。首先,如果在前臺花費的第一類服務請求的等待時間超過了最后期限,那么即使他們的服務請求沒有得到服務,客戶也將離開兩階段多服務器系統(tǒng),并且他們當然不應該為它們付費。其次,如果在截止期限內滿足了第一類服務請求,而總等待時間超過了,那么即使第二類服務請求尚未得到滿足,客戶也將離開第二臺多服務器系統(tǒng)。在這種情況下,他們將只為第一類服務請求付費。最后,如果總等待時間超過了期限,則客戶發(fā)布的任務成功完成,則客戶將為這兩種服務請求付費。基于式(8)和式(9),多服務器系統(tǒng)S1和S2中對服務請求的預期費用分別為:

(10)

(11)

式中:FW1(D)和FW(D)表示分別可在第一階段和第二階段內服務的服務請求的百分比。

由于截止時間的限制,第一種類型的服務請求只能在前階段提供服務,這將導致到達后階段的服務請求到達率下降。因此,當服務請求進入多服務器系統(tǒng)S1時,到達率為λ1,但是當服務請求進入多服務器系統(tǒng)S2時,到達率變?yōu)镕W1(D)λ2,原因是在截止時間D之前多服務器系統(tǒng)S1中只能處理百分之FW1(D)的傳入服務請求,而其余的將不提供服務而離開。因此,由云服務供應商在多服務器系統(tǒng)S1和S2中獲得的總收入可表示為:

(12)

(13)

1.4 成本模型

服務提供商的成本包括兩個主要部分,即基礎設施租賃成本和能源消耗的公用事業(yè)成本?；A設施提供商維護大量的服務器以供租賃,云服務供應商根據要求對其進行租賃并支付相應的租賃費用。假設每單位時間一臺服務器的租用價格為β,則具有mi臺服務器系統(tǒng)的服務器租用價格為miβ。作為服務提供商成本的另一部分,能源消耗的公用事業(yè)成本由電價和能源消耗量組成。本文采用如下動態(tài)功率模型[9]:

Pd=NswCLV2f

(14)

式中:Nsw是每個時鐘周期的平均柵極開關因子;CL是負載電容;V是電源電壓;f是時鐘頻率。在理想情況下,對于某個常數0<φ≤1,電源電壓V與時鐘頻率f之間的關系可以描述為V∝fφ。服務器的執(zhí)行速度si與時鐘頻率f呈線性比例,即si∝f,因此動態(tài)功率模型可以轉化為Pd∝NswCLs(2φ+1)i,為簡單起見,假設Pd=bNswCLs(2φ+1)i=ξsαi,其中:ξ=bNswCL;α=2φ+1;b為常數。本文設置NswCL=7,b=1.345 6,φ=0.5。由此可得α=2,ξ=9.419 2。

除了動態(tài)功耗之外,服務器空閑時也會消耗靜態(tài)功率,假設能源價格為每瓦特δ,則多服務器系統(tǒng)每單位時間的總成本可描述為:

(15)

1.5 問題描述

云服務供應商從基礎設施提供商處租用服務器并支付費用,同時,它們根據需要向客戶提供服務并獲得收入。從以上分析可以看出,客戶可以忍受的最大等待時間對每級多服務器系統(tǒng)中云服務供應商的成本模型和收益模型都有影響。因此,對于由多級多服務器隊列系統(tǒng)組成的云計算平臺,必須研究一種適當的方法以在截止期限約束下最大化云服務供應商的總效益。云服務供應商的總效益分別由多服務器系統(tǒng)S1和S2中獲得的每個部分組成。在本文中,我們致力于優(yōu)化租賃服務器的數量m,并優(yōu)化執(zhí)行速度,從而獲得最佳收益。

G(m1,m2,s1,s2)=G1(m1,s1)+G2(m1,m2,s1,s2)

(16)

注意G1僅由S1本身的特性決定,而G2由S1和S2的特性共同決定,由于在后階段執(zhí)行第二種服務請求要比在前階段執(zhí)行第一類服務請求滯后,因此第二臺多服務器系統(tǒng)中的參數與獲得的效益無關,但是由于第二種服務請求的執(zhí)行受到第一類服務請求的等待時間的影響,因此,該點不能正確地相反。在前階段花費的等待時間越多,在后階段花費的等待時間就越少,這將導致第二級多服務器系統(tǒng)獲得的效益下降,反之亦然,由此云服務供應商的總效益可以描述如下:

G(m1,m2,s1,s2)=ε1-C1+ε2-C2

(17)

2 求解算法

本節(jié)提出一種啟發(fā)式算法,以找到m1、s1和m2、s2的最佳組合方案。首先,在多服務器系統(tǒng)S1中分析了效益G1與m1以及s1之間的關系,并采用梯度下降算法來配置最優(yōu)服務器參數以獲得最優(yōu)效益。其次,根據前階段獲得的服務器參數,分析了效益G2與m2以及s2之間的關系,并建立了一個具有約束的最優(yōu)模型,以同時最大化G2和FW(D)。

2.1 第一級服務器系統(tǒng)效益最大化

2.1.1規(guī)模最優(yōu)

為了在S1中獲得最大效益,首先討論服務器數量m1對G1的影響,G1對m1的偏導數為:

(18)

(19)

(20)

由圖1中所繪制的特征關系圖可以發(fā)現其為減函數,因此可采用二分法來獲得最優(yōu)的m1值。計算得到不同λ1取值下的m1分別為1.991 1、2.337 5、2.681 8、3.024 7,相應的效益G1為27.621、33.312、39.007、44.707。

圖1 效益G1隨m1和λ1變化曲線

可以看出,當m1較低時,云服務供應商只能從S1中獲得極低的效益,甚至是負效益,這是因為服務請求的等待時間非常長,導致在截止時間D僅有很少的需求被響應。隨著服務器數量的增長,越來越多的服務器允許在截止時間之前滿足越來越多的服務請求,從而增加了收入和效益。當FW1(D)等于1時,收入達到最大值,但是隨著m1的進一步增加,服務器數量超過了執(zhí)行服務請求所需的最大數量,成本將繼續(xù)增長,導致效益下降。

2.1.2速度最優(yōu)

同樣地,為了獲得速度最優(yōu)的配置方案,令G1對s1求偏導數:

(21)

(22)

(23)

由圖2可以發(fā)現其特征關系也為遞減函數,采用標準的二等分法求得不同λ1取值下的最優(yōu)s1分別為0.201 44、0.235 78、0.269 87、0.303 79,相應的效益G1為-0.064 63、13.766、27.408和40.862。

圖2 效益G1隨s1和λ1變化曲線

可以看出,當s1較低時,云服務供應商只能在S1中獲得極低的效益,甚至是負效益,這是因為每單位時間只能滿足很少的服務請求,而其余的服務請求則由于過多而偏離了系統(tǒng)。隨著s1的增加,每單位時間可以滿足越來越多的服務請求,這將為云服務供應商帶來越來越多的收入和效益。此外,當FW1(D)等于1時,收入達到最大值,但是成本將繼續(xù)增長,隨著s1進一步增加,這將導致效益下降。這是因為服務器的執(zhí)行速度超過了執(zhí)行服務請求所需的最大速度。

2.1.3規(guī)模和速度最優(yōu)

根據前面的分析,可以合理地認為m1和s1的影響都可以導致最優(yōu)效益的增量比前面小節(jié)中討論的更高。因此,我們的目標是找到m1和s1的最佳組合,以使效益G1最大化。圖3顯示了效益G1的表面作為m1和s1的函數,其中λ1= 5.99。由于曲面是凸面的,我們采用梯度下降算法求出m1和s1,使得式(24)所示的G1(m1,s1)的梯度等于0,從而獲得了最優(yōu)的收益。

圖3 效益G1隨s1和m1變化曲線

請注意,由于使用了梯度下降算法來解決最小化問題,因此在應使ProfitG1最大化的同時,我們將G1(m1,s1)乘以-1作為目標梯度下降算法的功能。此外,為了加快算法的收斂速度,采用了Arjimo搜索方法來自動調整步長[37]。所得最優(yōu)效益為G1= 55.706 6,其中m1= 7.559和s1=0.936 8。通過對λ1= 4.99、6.99、7.99的情況進行相同的綜合,最優(yōu)效益分別為G1= 46.286 0、63.918 4、75.354 8,其中:m1=5.931 2、5.9784、8.909 8,s1=0.987 6、1.322 3、1.003 8。

2.2 第二級服務器系統(tǒng)效益最大化

通過選擇適當的m1和s1,可以在第一級多服務器系統(tǒng)中獲得最佳效益G1。在此基礎上,我們進一步找尋最優(yōu)的m2和s2,以使第二級多服務器系統(tǒng)中的效益G2最大化。

2.2.1規(guī)模最優(yōu)

為了在S2中獲得最大效益,首先討論服務器數量m2對G2的影響。由于G2是m1、m2和s1、s2的函數,在2.1節(jié)中獲得了最優(yōu)m1、s1,進一步采用偏導數來找到最優(yōu)m2:

(25)

(26)

在給定s2和λ1的情況下,效益G2與m1的關系曲線如圖4所示。采用二分法來獲得最優(yōu)的m1,以使G2最大化,得到m1的最優(yōu)值分別為1.768、2.132、2.426、2.766,相應的效益G2分別為27.869 0、33.803 1、39.232 5、44.915 7。

圖4 效益G2隨m1和λ1變化曲線

2.2.2速度最優(yōu)

現在考慮執(zhí)行速度s2對G2的影響,G2相對于s2的偏導數為:

(28)

(29)

在m2和λ1確定下,效益G2隨s2的變化曲線如圖5所示。對于λ1為 4.99、5.99、6.99,通過二分法得到s2的最優(yōu)值分別為0.361 5、0.439 7、0.489 1、0.557 2,相應的效益G2分別為32.835 0、46.081 4、58.071 2、70.286 6。

圖5 效益G2隨s2和λ1變化曲線

2.2.3規(guī)模和速度最優(yōu)

對于云服務供應商而言,在考慮效益的同時,當客戶對服務質量感到滿意時,他們更有可能向其他客戶推薦云計算平臺,那么這些潛在客戶將為云服務供應商帶來更多的效益。但是,如果客戶不滿意,他們不太可能向其他客戶推薦云計算平臺,那么云服務供應商獲得的相應效益將會減少。本文選擇多階段多服務器隊列系統(tǒng)中客戶的總等待時間來衡量客戶滿意度。當等待時間超過最后期限D時,客戶會感到不滿意,反之亦然。因此,為了在盡可能增加截止時間內服務客戶數量的前提下,最大化總效益,本文所構建的云計算效益模型如下:

minf1(X)=-ε2+C2

f2(X)=1-FW(D)

(31)

式中:X=[m2,s2]。本文中采用NSGA-II來求解這一多目標規(guī)劃問題。

所得非支配解作為優(yōu)化問題的帕累托解集,以其中一個最優(yōu)解為例,f1(X)= -57.1,f2(X)=0.001 97,求得最大收益為57.1,并且在截止時間D內響應了99.8%的服務請求。

2.3 一般的n級多服務器隊列系統(tǒng)

以上內容充分討論了具有兩階段多服務器隊列系統(tǒng)的效益最大化方案在云計算平臺上的應用,由此可進一步擴展到具有n級多服務器隊列系統(tǒng)的一般情況。由上述內容,科研發(fā)現每級服務器系統(tǒng)的效益僅取決于當前系統(tǒng)和之前系統(tǒng)的參數,而不取決于之后系統(tǒng)。因為無論客戶處于什么等待階段,一旦他們的總等待時間超過了最后期限,即使他們的任務尚未完全執(zhí)行,他們也會離開多階段多服務器隊列系統(tǒng)。因此,無須為未滿足的服務請求(子任務)付費,那么也無須分析在相應的多服務器系統(tǒng)中獲得的效益。

3 結果分析

根據第2節(jié)的分析,我們發(fā)現截止時間內服務請求的百分比不僅受m1、m2和s1、s2的影響,而且還受服務請求到達率λ1和截止時間D的影響。在我們的第一組模擬中,分析了在不同到達率下,截止時間內服務請求的百分比和總效益隨截止時間的增加而變化的情況,相應的結果如圖6和圖7所示。對于λ1分別為4.99、5.99、6.99、7.99的多級多服務器隊列系統(tǒng),截止時間內服務的服務請求百分比和總效益都隨截止時間而增加。這是因為隨著截止時間的增加,可以滿足更多的服務請求,這將給云服務供應商帶來更多的收入。此外,隨著λ1的減少,總效益減少,而在固定期限內,在期限內提供服務的請求百分比增加。當服務請求的到達率較低時,服務器在多級多服務器隊列系統(tǒng)中僅承受很少的壓力,因此新的服務請求將會在很大程度上有效減少等待時間以滿足截止期限的約束。

圖6 截止時間約束下已執(zhí)行服務請求的完成率

圖7 最佳效益與截止時間

在第二組模擬中,分析了在不同的期限內,期限內服務請求的百分比和總效益隨服務請求到達率的增加而變化,相應的結果如圖8和圖9所示。對于D為1、4、7、10的多級多服務器隊列系統(tǒng),總效益增加λ1,而服務請求的百分比在截止時間之內則朝相反的方向變化。請注意,對于D為4、7、10,總效益的變化和在截止時間之前提供的服務請求的百分比彼此接近。而對于D為1,這種變化具有顯著差異。這是因為在前一種情況下,最后期限足夠長,幾乎不能滿足所有服務請求;而在后一種情況下,這樣的期限太短,無法滿足足夠的服務請求。因此,在后一種情況下,在截止時間之前提供服務的總效益和服務請求的百分比都遠小于在前一種情況下獲得的效益。此外,當D為1時,隨著λ1進一步增加,總效益反而減少,這是因為收入的增加不足以彌補成本的增加,因此,在這種情況下,應該在效益的最大化與在截止時間之前提供的服務請求的百分比之間進行權衡。

圖8 已執(zhí)行服務請求的完成率隨λ1變化特性

圖9 最優(yōu)效益隨λ1變化特性

4 結 語

本文研究在考慮客戶等待時長的基礎上,實現云服務供應商的效益最大化。考慮到每個任務可以通過連續(xù)的執(zhí)行關系分為多個子任務,采用多級多服務器隊列系統(tǒng)組成云服務平臺,每個系統(tǒng)在每一階段只為唯一類型的服務請求提供服務。在此基礎上,由于最大化云服務供應商的效益與最小化由于過多等待時間而造成的客戶損失之間存在矛盾,本文構建了多目標優(yōu)化模型并進行求解。最后,通過算例仿真分析了本文方法所得最優(yōu)方案的性能,結果表明,本文方案的動態(tài)特性隨著客戶等待期限和服務請求到達率的增加而增加。