摘 要: 在混合云計算環(huán)境下,如何合理地劃分工作量是每個理性的用戶所需要考慮的問題。構(gòu)建了混合云計算工作量分解博弈模型,在用戶通??紤]響應(yīng)時間的情況下把花費(fèi)也納入考慮,即將以響應(yīng)時間和花費(fèi)為變量的函數(shù)作為效用函數(shù),通過求解納什均衡的方法分析用戶的策略行為,從而決定用戶的最優(yōu)策略。通過仿真給出了不同響應(yīng)時間和花費(fèi)比率對用戶均衡策略的影響并做出了比較分析。
關(guān)鍵詞: 混合云;工作量分解;博弈;納什均衡
0 引言
云計算服務(wù)作為一種新型的商業(yè)計算服務(wù)逐漸成為企業(yè)和個人用戶計算應(yīng)用的主要方式,如亞馬遜的EC2、谷歌的AppEngine及微軟的Azure等云平臺[1]。隨著云計算的興起,近幾年來云計算用戶穩(wěn)定增長。根據(jù)美國國家標(biāo)準(zhǔn)與技術(shù)研究院(NIST)的定義,云計算服務(wù)模式可分為基礎(chǔ)設(shè)施即服務(wù)(IaaS)、平臺即服務(wù)(PaaS)及軟件即服務(wù)(SaaS)[2]。云計算發(fā)展至今,云服務(wù)方式出現(xiàn)了公有云、私有云、混合云等,混合云是由公有云和私有云組成的。公有云平臺是整合自己的資源為第三方提供服務(wù)的計算平臺,私有云平臺則是整合企業(yè)內(nèi)部的資源為企業(yè)自己服務(wù)的云計算平臺,而混合云平臺則是指整合公有云和私有云共同為用戶提供服務(wù)[3]。隨著云計算技術(shù)的發(fā)展,由公有云和私有云共同組成的混合云是未來發(fā)展的趨勢。在Ganter對全球270家企業(yè)的調(diào)查中,有46%的企業(yè)決策者考慮基于現(xiàn)有自建方案進(jìn)行云協(xié)作應(yīng)用的延伸部署計劃,這說明混合云將成為相當(dāng)一段時間內(nèi)的主流模式。
目前云計算一般有兩種類型的分析:性能類型分析和市場類型分析[4]。性能類型分析以“最優(yōu)化”執(zhí)行性能為目標(biāo),例如針對響應(yīng)時間性能,通常不會考慮花費(fèi);而市場類型分析就要考慮花費(fèi)的因素。用戶通過提交工作量到公有云上能很好地降低工作量的響應(yīng)時間,從響應(yīng)時間角度能夠提高用戶的效用水平,但同時公有云是按用戶的消費(fèi)量收費(fèi)的,從用戶的花費(fèi)角度降低了用戶的效用水平。當(dāng)用戶急需縮短處理任務(wù)的響應(yīng)時間時,用戶愿意繳納費(fèi)用來獲得更好的效用水平,而隨著響應(yīng)時間的逐步縮短,用戶對執(zhí)行單位工作量愿意的花費(fèi)逐漸減小,因此在考慮響應(yīng)時間和花費(fèi)的情況下,用戶如何做出合理的工作量分解決策正是本文研究的問題。
本文把響應(yīng)時間和花費(fèi)納入考慮,建立了混合云工作量分解博弈模型,通過求解納什均衡的方法給出用戶的最優(yōu)任務(wù)分解決策。本文首先對相關(guān)工作進(jìn)行了綜述;然后建立了混合云計算工作量分解問題博弈模型;接著對用戶策略均衡分析,得出納什均衡策略向量,并針對不同參數(shù)進(jìn)行了仿真比較分析。
1 相關(guān)工作
參考文獻(xiàn)[5]介紹了云計算產(chǎn)生的時代背景以及為什么會成為當(dāng)下熱點的課題,并以谷歌的云計算技術(shù)為例,歸納了云計算關(guān)鍵技術(shù),如數(shù)據(jù)存儲技術(shù)、數(shù)據(jù)管理技術(shù)等。參考文獻(xiàn)[6]介紹了云計算是一種新型的計算模式,用戶的任務(wù)被分配到一個混合云的服務(wù)器和設(shè)備上,相當(dāng)于為私有云構(gòu)建了一個外加的計算方式,使得用戶能夠執(zhí)行工作量,也就是說,如何分流用戶的工作量負(fù)載到公有云和私有云上。參考文獻(xiàn)[7]從用戶目前采用公有云的服務(wù)可靠性、安全性等疑慮出發(fā),提出了混合云的解決方案,能夠充分利用公有云資源以補(bǔ)充本地私有云資源的不足。
博弈論的思想建模能夠很好地分析每個參與者的策略,隨著云計算的興起,越來越多的學(xué)者開始著手從博弈論的視角去分析工作量分解[8]。參考文獻(xiàn)[9]建議在非合作的參與者共享資源時,以最壞可能的納什均衡和社會最優(yōu)之間的比率作為衡量系統(tǒng)的效率標(biāo)準(zhǔn)。參考文獻(xiàn)[10]提出了一個具體的新型的云服務(wù)提供視頻點播系統(tǒng),介紹了劃分用戶的點播視頻需求量到云計算服務(wù)上以及尋求最優(yōu)的劃分策略。參考文獻(xiàn)[11]給出了在混和云環(huán)境下,求解大任務(wù)和小任務(wù)兩類用戶的納什均衡的方法,并通過仿真給出了在不同參數(shù)情況下云用戶的最優(yōu)策略。綜上所述,對于在綜合考慮用戶的響應(yīng)時間和花費(fèi)的情況下,用戶如何決定工作量分解的最優(yōu)策略問題尚未研究,這也是本文的主要工作。
2 模型
在混合云計算環(huán)境下存在的用戶博弈是一個三元組:G=<N,(si),(i)>,其中N={1,2,…,n}為參與者的集合,表示有n個用戶。用戶i策略集表示為Si,Si={i|i∈[0,1]},其中i表示用戶i劃分到公有云計算上執(zhí)行的任務(wù)量占總?cè)蝿?wù)量的比例,從而1-i表示為用戶i劃分到私有云上執(zhí)行的任務(wù)量占總?cè)蝿?wù)量的比例。ui=f(ti,ci)表示用戶i的效用,它是關(guān)于任務(wù)的響應(yīng)時間ti和花費(fèi)ci的函數(shù)。私有云一般是在企業(yè)內(nèi)部部署的,對企業(yè)用戶不收取費(fèi)用。工作量執(zhí)行的時間是取公有云和私有云上執(zhí)行時間較大者,即,其中 表示工作量劃分到私有云上執(zhí)行的時間,TiP為工作量劃分到公有云上執(zhí)行的時間。本文對建立的混合云計算工作量分解模型有如下假設(shè):(1)公有云計算資源無限,私有云計算資源有限,即公有云的處理速度遠(yuǎn)大于私有云;(2)每個用戶工作量相同且表示為?棕。因為對于用戶i來說私有云執(zhí)行時間大于公有云執(zhí)行時間,所以用戶i的工作量執(zhí)行的時間可以表示為:ti=max。本文和參考文獻(xiàn)[4]處理連續(xù)的任務(wù)時間一樣,,其中L表示私有云上執(zhí)行任務(wù)的速度。因為還有其他用戶提交工作量到私有云上執(zhí)行,所以私有云上執(zhí)行時間應(yīng)該是所有用戶任務(wù)在私有云上的執(zhí)行時間,可以表示為:。對于用戶來說,隨著工作量劃分任務(wù)量比例的增大,花費(fèi)增大效用會變小,但時間逐漸減少,使得效用因為時間減小而帶來效用增大,因此有。
3 均衡分析和模擬仿真
3.1 均衡分析
每個用戶的效用都和其他用戶提交到公有云的策略有關(guān),如果把每個用戶視為理性的參與者,用戶i的策略為i,ti和ci都為i的函數(shù),用戶i的效用就可表示為ui(i,-i),即f(ti,ci)=ui(i,-i),用戶策略的范圍為i∈[0,1)。由于所有用戶同時行動,因此這個博弈是一個完全信息靜態(tài)博弈。用戶的效用分別為u1(1,-1),…,ui(i,-i),…,un(n,-n),隨著i的增大,用戶的邊際效用遞減。ui(i,-i)是凹函數(shù),即:。
0,即當(dāng)其他用戶是最優(yōu)時,用戶i的策略也是它的最優(yōu)策略,即互為最優(yōu)反應(yīng)策略,那么(i*,*-i)就是該博弈的納什均衡。
參照參考文獻(xiàn)[9]中效用函數(shù)的形式并更一般化,選擇用戶i的效用函數(shù)為:
其中,是花費(fèi)前的系數(shù);是響應(yīng)時間前的系數(shù);是花費(fèi)和響應(yīng)時間的冪,可以表明時間和花費(fèi)是可以互相轉(zhuǎn)換的;?茲是表達(dá)式的冪;a是表達(dá)式比例系數(shù)。
性質(zhì)1 式(1)有花費(fèi)和時間的無差異曲線滿足凹函數(shù)關(guān)系。
證明:
當(dāng)效用是一個給定的正常數(shù)時,式(2)為一正常數(shù),設(shè),則:
在實際應(yīng)用中會經(jīng)常考慮到邊際效用遞減規(guī)律,在混合云計算環(huán)境下,用戶如何合理地劃分工作量比例是每個理性的云用戶關(guān)心的問題。由前面云用戶的效用表達(dá)式ui=f(ti,ci),其中用戶i花費(fèi)的函數(shù)為ci=p?滓i?棕,可得用戶i執(zhí)行工作量分解響應(yīng)時間的表達(dá)式為:。在用戶混合云工作量分解博弈模型中,用戶之間存在的博弈是一個完全信息靜態(tài)博弈,,可以得到用戶i反應(yīng)函數(shù)。在完全信息靜態(tài)博弈中,因考慮用戶所有任務(wù)量相同時,最終可得一致性的策略結(jié)果。當(dāng)i∈[0,1)時,
3.2 模擬分析
價格、響應(yīng)時間和花費(fèi)有關(guān)。
圖1有3條曲線,分別表示用戶數(shù)為100、1 000和10 000三種不同的情形;橫坐標(biāo)為單位流量價格,在0到10之間取值;其他參數(shù)已設(shè)定。當(dāng)n=100時,隨著公有云提供商定價的提高,用戶放在公有云上的比例就越少。當(dāng)用戶的總數(shù)n增加到1 000時,隨著定價從0到10變化,用戶提交到公有云上的工作任務(wù)明顯提高了許多,也就是說當(dāng)用戶數(shù)量增大時,本地資源很難滿足用戶的需求,用戶將更多的任務(wù)提交到公有云上。當(dāng)用戶的總數(shù)增加到10 000時,可以看到用戶的均衡策略是幾乎把所有的任務(wù)量都劃分到公有云上,這體現(xiàn)出公有云處理多用戶多任務(wù)的必要性和優(yōu)越性。
圖2和圖3分別為參數(shù)下呈現(xiàn)出的對應(yīng)關(guān)系,表明時間和花費(fèi)比率對用戶效用的影響程度,隨著單位任務(wù)量價格p的變化,在不同和下用戶的均衡策略也發(fā)生了變化。從圖2可以看到,用戶隨著價格增加,因為花費(fèi)多,更快地降低了用戶效用,用戶就不愿意把更多工作量放到公有云執(zhí)行;而從圖3可以看到,隨著單位任務(wù)量的價格變化,用戶的均衡策略變化較緩,也就是說花費(fèi)相對少,使得用戶效用降低的速率較慢。
4 結(jié)論
本文提出了混合云環(huán)境下云用戶在公有云和私有云之間如何進(jìn)行工作量分解的問題,把響應(yīng)時間和花費(fèi)納入考慮,建立了混合云工作量分解博弈模型,通過求解納什均衡的方法給出用戶的最優(yōu)任務(wù)分解決策。根據(jù)相關(guān)研究選用花費(fèi)和時間的效用函數(shù)進(jìn)行了仿真模擬,分析了在不同參數(shù)情況下用戶均衡策略隨著價格的變化情況,為用戶更好地決策提供了理論依據(jù)。對于給定不同用戶工作量的分析更加復(fù)雜,這些問題將是下一步研究的方向。
參考文獻(xiàn)
[1] Wang Xu, Wang Beizhan, Huang Jing. Cloud computing and its key techniques[C]. 2011 IEEE International Conference on Computer Science and Automation Engineering (CSAE), 2011:404-410.
[2] BHARDWAJ S, JAIN L, JAIN S. Cloud computing: a study of infrastructure as a service(IAAS)[J]. International Journal of Engineering and Information Technology, 2010, 2(1): 60-63.
[3] Zhang Hong, Li Bo, Jiang Hongbo, et al. A framework for truthful online auctions in cloud computing with heterogeneous user demands[C]. INFOCOM 2013 Proceedings IEEE, 2013:1510-1518.
[4] NAHIR A, ORDA A, RAZ D. Workload Factoring with the cloud: a game-theoretic perspective[C]. INFOCOM, 2012 Proceedings IEEE, 2012:2566-2570
[5] OSTERMANN S, IOSUP A, YIGITBASI N, et al. A performance analysis of EC2 cloud computing services for scientific computing[C]. Cloud Computing[A]. Berlin Heidelberg Springer, 2010,34:115-131.
[6] JAIN N, MENACHE I, NAOR J S, et al. A truthful mechanism for value-based scheduling in cloud computing[C]. Algorithmic Game Theory[A]. Berlin Heidelberg Springer, 2011,6982:178-189.
[7] HU Y, WONG J, ISZLAI G, et al. Resource provisioning for cloud Computing[C]. Proceedings of the 2009 Conference of the Center for Advanced Studies on Collaborative Research, ACM, 2009: 101-111.
[8] Niu Di, Feng Chen, Li Baochun. A theory of cloud bandwidth pricing for video-on-demand providers[C]. INFOCOM, 2012 Proceedings IEEE, 2012:711-719.
[9] Wei Guiyi, VASILAKOS A V, Zheng Yao, et al. A game-theoretic method of fair resource allocation for cloud computing services[J]. Journal of Supercomputing, 2010, 54(2): 252-269.
[10] KOUTSOUPIAS E, PAPADIMITRIOU C. Worst-case equilibria[C]. STACS 99, Berlin Heidelberg:Springer, 1999,1563: 404-413.
[11] 陶杰,吳小紅.基于博弈的云計算任務(wù)分解研究[J].科學(xué)技術(shù)與工程,2013,13(5):87-92.