基于機制設計理論的云計算SLA 響應時間優化*

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

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

1 引言

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

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

2 機制設計相關概念

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

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

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

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

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

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

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

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

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

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

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

4 一種優化響應時間的機制設計

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

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

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

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

4.1 用戶任務分配機制設計

4.1.1 分配函數的設計

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

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

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

因此本文機制的分配函數設計如下：

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

4.1.2 支付函數的設計

4.2 機制的性能分析

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

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

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

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

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

命題2 該機制滿足弱預算均衡性。

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

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

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

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

命題4 該機制是占優策略激勵兼容的。

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

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

5 預算約束下響應時間最短的資源提供商最優組合算法

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

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

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

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

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

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

6 結束語

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

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