基于機(jī)制設(shè)計(jì)理論的云計(jì)算SLA 響應(yīng)時(shí)間優(yōu)化*

王翠娥,顧永跟,吳小紅,陶 杰

(1.杭州電子科技大學(xué)計(jì)算機(jī)應(yīng)用研究所 杭州 310018；2.湖州師范學(xué)院信息與工程學(xué)院 湖州 313000）

1 引言

云計(jì)算SLA是云服務(wù)質(zhì)量的重要保證[1]。針對(duì)云計(jì)算SLA中的響應(yīng)時(shí)間，將在充分保障QoS[2]的前提下，最小化用戶任務(wù)的完成時(shí)間定義為響應(yīng)時(shí)間。云計(jì)算雙市場(chǎng)模型中將云資源提供商和云服務(wù)提供商[3]分別作為資源代理和用戶代理，在雙市場(chǎng)中對(duì)資源需求和服務(wù)需求進(jìn)行協(xié)商和匹配。在用戶某項(xiàng)工作的預(yù)算確定以及違例賠償明確的情況下，云服務(wù)提供商會(huì)考慮如何優(yōu)化服務(wù)的響應(yīng)時(shí)間，尋求一組能在最短時(shí)間內(nèi)完成任務(wù)的資源組合。

機(jī)制設(shè)計(jì)是博弈規(guī)則設(shè)計(jì)的主要方法，即使博弈中的代理都是自利的，也可以通過機(jī)制設(shè)計(jì)獲得一個(gè)最佳結(jié)果[4,5]。本文假設(shè)云資源提供商是自治﹑理性﹑智能的，設(shè)計(jì)的機(jī)制中，不論其他資源提供商的報(bào)價(jià)如何，真實(shí)報(bào)價(jià)是其占優(yōu)策略。對(duì)于一個(gè)機(jī)制設(shè)計(jì)問題，需要考慮兩個(gè)方面：一個(gè)是機(jī)制中每個(gè)代理人的目標(biāo)，另一個(gè)是機(jī)制的目標(biāo)[6]。在本文所設(shè)計(jì)的機(jī)制中，云服務(wù)提供商在SLA條款中預(yù)算值和違例賠償值一定的情形下，尋求一種用戶完成工作時(shí)間最短的方法。在各云資源提供商都追逐最大效用的情況下，該機(jī)制為云服務(wù)提供商尋求用戶工作的最短響應(yīng)時(shí)間創(chuàng)建了一個(gè)真實(shí)的資源成本顯示環(huán)境。那么如何在理性﹑智能﹑自治的云資源提供商之間制定一種交互的協(xié)議，以促成各云資源提供商顯示資源的真實(shí)成本，正是本文設(shè)計(jì)的機(jī)制要解決的問題。

2 機(jī)制設(shè)計(jì)相關(guān)概念

為了后文敘述方便，將機(jī)制設(shè)計(jì)理論中相關(guān)符號(hào)和幾個(gè)重要概念列舉如下。

θ：參與用戶任務(wù)競(jìng)爭(zhēng)的云資源提供商的一種類型組合，θ=θ1×…×θn。

θ-i：云資源提供商i除外的其他參與用戶任務(wù)競(jìng)爭(zhēng)的資源提供商的一種類型組合，θ-i=θ1×…×θi-1×θi+1×…×θn。

Θ：參與用戶任務(wù)競(jìng)爭(zhēng)的云資源提供商的所有類型組合，Θ=Θ1×…×Θn。

Θ-i：云資源提供商除外的其他參與用戶任務(wù)競(jìng)爭(zhēng)的資源提供商的所有類型組合，Θ-i=Θ1×…×Θi-1×Θi+1×…×Θn。

定義1 （社會(huì)選擇函數(shù)在占優(yōu)策略上的實(shí)現(xiàn)）如果一個(gè)機(jī)制M=((Si)i∈N,g(·))所導(dǎo)出的貝葉斯博弈 Γb有一個(gè)弱占優(yōu)策略均衡，且使得那么稱該機(jī)制在占優(yōu)策略均衡上滿足社會(huì)選擇函數(shù)f(·)。

定義2 （占優(yōu)策略激勵(lì)兼容）如果一個(gè)直接顯示機(jī)制D=((Θi)i∈N,f(·))所導(dǎo)出的貝葉斯博弈有一個(gè)弱占優(yōu)策略均衡，其中N，那么社會(huì)選擇函數(shù)f:Θ1×…×Θn→X是占優(yōu)策略激勵(lì)兼容的。社會(huì)選擇函數(shù)激勵(lì)兼容的充分必要條件為ui(f(θi,θ-i),，坌i∈N，坌θi∈Θi，坌θ-i∈Θ-i即無論其他代理人報(bào)價(jià)如何，代理人i報(bào)的真實(shí)類型θi總是其最優(yōu)反應(yīng)。

3 不完全信息資源成本報(bào)價(jià)模型

對(duì)于云計(jì)算任務(wù)分配，本文構(gòu)建了一個(gè)不完全信息的非合作博弈模型。以博弈論的觀點(diǎn)，假設(shè)云資源提供商是自治﹑理性﹑智能的。云資源提供商的自治性是指其策略不受云用戶和其他資源提供商的影響和控制；理性是指其所選的策略是為追求自己的效用最大化；智能性是指云資源提供商知道博弈規(guī)則，并且會(huì)在選擇策略時(shí)充分考慮其他資源提供商的可能行為。

在云計(jì)算中，一個(gè)用戶提交的工作可以被分為多個(gè)任務(wù)，這些任務(wù)可以在云數(shù)據(jù)中心獨(dú)立并行地執(zhí)行。假設(shè)用戶的某一項(xiàng)工作被劃分成m個(gè)相同的任務(wù)，數(shù)據(jù)中心現(xiàn)有Y個(gè)云資源提供商，n為參與用戶任務(wù)競(jìng)爭(zhēng)的云資源提供商。云資源提供商i有一個(gè)任務(wù)處理速率μi，μi由資源提供商代理的服務(wù)器處理速率決定，可以視為常數(shù)，ti=1/μi表示單個(gè)任務(wù)的處理時(shí)間。此外，每個(gè)云資源提供商有一個(gè)可接受的任務(wù)數(shù)qi及處理單個(gè)任務(wù)的資源成本ci，ci為資源提供商i的私有信息，θi(ci,qi)為云資源提供商的真實(shí)類型，θ^i(c^i,qi)為云資源提供商i所報(bào)的類型。每個(gè)理性的云資源提供商都追逐各自效用的最大值，其效用記為ui(k(·)，p1(·),…,pn(·),θi)，價(jià)值函數(shù)vi(k(·),θi)=-ki(θ)×ci，則：

其中，k(·)和pi(θ)是機(jī)制設(shè)計(jì)的分配函數(shù)和支付函數(shù)。云服務(wù)提供商的目標(biāo)是在預(yù)算值和違例賠償值一定的情形下，為用戶在SLA條款中尋找min(maxti)。

4 一種優(yōu)化響應(yīng)時(shí)間的機(jī)制設(shè)計(jì)

在理性參與人的假設(shè)下，Neumann和Morgenstern提出并證明了期望效用最大化理論[7]。理性的資源提供商都追求效用最大化，因此對(duì)于響應(yīng)時(shí)間的優(yōu)化問題，云服務(wù)提供商必須考慮各資源提供商對(duì)所提供資源報(bào)價(jià)的真實(shí)性，即希望在所有資源提供商提供真實(shí)資源成本的前提下，尋找任務(wù)響應(yīng)時(shí)間最短的云資源提供商。本著這一目標(biāo)，作為機(jī)制設(shè)計(jì)者的云服務(wù)提供商必須設(shè)計(jì)該機(jī)制下的支付函數(shù)和分配函數(shù)，使得參與該機(jī)制的資源提供商都愿意報(bào)出真實(shí)的資源成本。

為了更準(zhǔn)確地分析機(jī)制設(shè)計(jì)問題，需要定義一個(gè)機(jī)制設(shè)計(jì)環(huán)境，下面介紹本文機(jī)制設(shè)計(jì)的準(zhǔn)線性環(huán)境[8]，在準(zhǔn)線性環(huán)境下，可以找到一個(gè)激勵(lì)兼容但非獨(dú)裁的社會(huì)選擇函數(shù)f(·)。

定義3 (機(jī)制設(shè)計(jì)的準(zhǔn)線性環(huán)境)代理集N={1,2,…,n}；可選結(jié)果集0}；代理i具有類型 θi∈Θi，Θi定義為參與用戶任務(wù)競(jìng)爭(zhēng)的云資源提供商i的類型空間，類型是與決策制定有關(guān)的所有私有信息；社會(huì)選擇函數(shù)f(θ)=(k(θ),p1(θ),…,pn(θ))；效用函數(shù)ui(x,θ)=ui((k(·),p1(·),…,pn(·))，θi）=vi(k,θi)+pi。

其中，分配向量k(θ)=(k1(θ),k2(θ),…,kn(θ))，ki(θ)定義為云服務(wù)提供商對(duì)云資源提供商i(i=1,2,…,n)的分配函數(shù)；支付向量p(θ)=((p1(θ),p2(θ),…,pn(θ)),pi(θ)定義為云服務(wù)提供商對(duì)云資源提供商i的支付函數(shù)。

4.1 用戶任務(wù)分配機(jī)制設(shè)計(jì)

4.1.1 分配函數(shù)的設(shè)計(jì)

一個(gè)有效的用戶任務(wù)分配方案k(θ)=(k1(θ),k2(θ),…,kn(θ))必須滿足以下條件。

·非負(fù)性：ki(·)≥0,i=1,2,…,n；

·ki(·)≤qi,i=1,2,…,n。

因此本文機(jī)制的分配函數(shù)設(shè)計(jì)如下：

其中，[i]表示所報(bào)的處理任務(wù)相關(guān)資源成本升序排列處于第i位的云資源提供商，]被定義為具有下列特點(diǎn)的云資源提供商：

4.1.2 支付函數(shù)的設(shè)計(jì)

4.2 機(jī)制的性能分析

命題1 該機(jī)制滿足分配有效性。

證明 首先驗(yàn)證該機(jī)制驅(qū)使下的云資源提供商i的占優(yōu)策略（報(bào)告其真實(shí)資源成本ci），分以下兩種情形。

綜合上述兩種情形，可知云資源提供商i在效用驅(qū)使下，令其報(bào)價(jià)i等于真實(shí)資源成本ci是其占優(yōu)策略。

有了上述結(jié)論，就很容易驗(yàn)證本文設(shè)計(jì)的分配規(guī)則滿足代理（云資源提供商）效用函數(shù)最大化，即對(duì)于被分配任務(wù)的云資源提供商，其整體資源成本是最小的。

已知價(jià)值函數(shù)vi(k(·),θi)=-ki(θ)×ci，在上述分析的基礎(chǔ)上可將其記為vi(k(·),θi)=ki(θ)×i，將其代入k*(θ)證畢。

命題2 該機(jī)制滿足弱預(yù)算均衡性。

命題3 該機(jī)制滿足個(gè)體理性。

個(gè)體理性也被稱作自愿參與性，社會(huì)選擇函數(shù)的個(gè)體理性暗含如果一個(gè)機(jī)制實(shí)現(xiàn)了該社會(huì)選擇函數(shù)，則參與該機(jī)制的每個(gè)代理都將有非負(fù)的效用，一般假設(shè)不參與機(jī)制時(shí)的效用i(θi)=0，即 ui(f(θi,θ-i),θi)≥i(θi),?(θi,θ-i)∈Θ。

如果云資源提供商i在該機(jī)制下競(jìng)標(biāo)到了任務(wù)，則完成用戶任務(wù)的總成本降低，因此在i參與的情況下它的效用ui(f(θ),θi)>0；如果云資源提供商 i沒有競(jìng)標(biāo)到任務(wù)或者自動(dòng)退出該機(jī)制，那么

由以上分析可知，云資源提供商參與該機(jī)制的效用總是不小于退出該機(jī)制的效用，具備自愿參與該機(jī)制的意向，于是該機(jī)制的個(gè)體理性得證。

命題4 該機(jī)制是占優(yōu)策略激勵(lì)兼容的。

下面采用反證法加強(qiáng)驗(yàn)證結(jié)論的正確性。如果一個(gè)機(jī)制是占優(yōu)策略激勵(lì)兼容的，那么定有下式成立：

如果本文設(shè)計(jì)的機(jī)制不是占優(yōu)策略激勵(lì)兼容的，那么至少存在一個(gè)代理i使得式（5）不成立，即對(duì)于代理i,云資源提供商效用函數(shù)該機(jī)制的支付函數(shù)與 θi無關(guān)，于是可以得到下式：

5 預(yù)算約束下響應(yīng)時(shí)間最短的資源提供商最優(yōu)組合算法

在各資源提供商真實(shí)顯示資源成本的前提下，本節(jié)提出了一種預(yù)算約束下響應(yīng)時(shí)間最短的資源提供商最優(yōu)組合算法，描述如下：

·各云資源提供商對(duì)用戶提交的工作標(biāo)示出任務(wù)的處理時(shí)間和可處理的任務(wù)數(shù)，記為（ti,qi）；

·云服務(wù)提供商接收云資源提供商所報(bào)的信息（ti,qi）；

·云服務(wù)提供商對(duì)云資源提供商所報(bào)信息的任務(wù)處理時(shí)間ti進(jìn)行升序排列；

·按任務(wù)處理時(shí)間ti的升序，從第[1]個(gè)云資源提供商到第]個(gè)云資源提供商依次選出m個(gè)任務(wù)數(shù)，滿足并把相應(yīng)的資源提供商添加進(jìn)列表L，同時(shí)令

·e>E時(shí)，從列表中移除最大 （或剩余信息中最大）ti的相關(guān)信息；繼續(xù)尋找第個(gè)云資源提供商，并添加進(jìn)列表L，最后選出列表中的資源提供商。這組云資源提供商正是滿足預(yù)算約束下任務(wù)響應(yīng)時(shí)間最短的最優(yōu)組合。

6 結(jié)束語

本文提出了一種基于機(jī)制設(shè)計(jì)理論的云計(jì)算SLA響應(yīng)時(shí)間優(yōu)化方案，設(shè)計(jì)了一種DSIC機(jī)制。假設(shè)云資源提供商是自治﹑理性﹑智能的，那么在這個(gè)機(jī)制中不論其他資源提供商的報(bào)價(jià)如何，真實(shí)報(bào)價(jià)是其占優(yōu)策略。該機(jī)制能夠保證各云資源提供商顯示真實(shí)的資源成本，因此為云用戶尋找到一組滿足用戶預(yù)算約束下響應(yīng)時(shí)間最短的資源提供商是可能的，這也是本文機(jī)制設(shè)計(jì)的目標(biāo)。本文的云資源報(bào)價(jià)機(jī)制為云計(jì)算SLA的設(shè)計(jì)提供了一個(gè)有利環(huán)境，在資源成本真實(shí)顯示的環(huán)境下云服務(wù)提供商能優(yōu)化用戶服務(wù)需求的響應(yīng)時(shí)間，同時(shí)在一定程度上提升了用戶對(duì)云資源提供商的信任度。后續(xù)筆者將在雙市場(chǎng)云模型中對(duì)云計(jì)算SLA中的其他參數(shù)的優(yōu)化（如服務(wù)花費(fèi)、違例賠償?shù)葯C(jī)制）設(shè)計(jì)問題作進(jìn)一步探討。此外，對(duì)于參與人多維私有類型信息的情況，如何設(shè)計(jì)既有較低計(jì)算復(fù)雜性又有激勵(lì)兼容性的機(jī)制也有待進(jìn)一步研究。

1 Armbrust M,Fox A,Grith R,et al.Above the Clouds:Aberkeley View of Cloud Computing.Technical Report UCB/EECS-2009-28,EECS Department,University of California,Berkeley,2009

2 Buyya R,Yeo C S,Venugopal S,et al.Cloud computing and emerging IT platforms:vision,hype,and reality for delivering computing asthe 5th utility.Future Generation Computer Systems,Elsevier Science,2009,25(6):599～616

3 Yonggen Gu,XiaohongWu,Jie Tao.Building an open cloud dual-market for cloud computing service.Proceedings of the 2nd International Symposium on ComputerNetwork and Multimedia Technology (CNMT’10),IEEE,2010:691～694

4 Nisan N,Ronen A.Algorithmic mechanism design.Games and Economic Behavior,2001,35(1):166～196

5 Nisan N,Roughgarden T,Tardos E,et al.Algorithmic Game Theory.Cambridge University Press,New York,2007

6 Garg D,Narahari Y,Gujar S.Foundations of mechanism design:a tutorial-part 1:key concepts and classical results.Sadhana—Indian Academy Proceedings in Engineering Sciences,2008,33(2):83～130

7 Neumann J V,Morgenstern O.Theory of Games and Economic Behavior.Princeton University Press,1944

8 Narahari Y,Garg D,Narayanam R,et al.Game Theoretic Problems in NetworkEconomicsandMechanismDesignSolutions.Springer,2009