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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

3 不完全信息資源成本報價模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 機制的性能分析

命題1 該機制滿足分配有效性。

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

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

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

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

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

命題3 該機制滿足個體理性。

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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