基于ＱｏＳ的網(wǎng)格計算經(jīng)濟模型

摘 要：提出了基于經(jīng)濟模型的網(wǎng)格QoS控制機制，刻畫了基于經(jīng)濟模型的網(wǎng)格QoS管理結(jié)構(gòu)。用生產(chǎn)—消費模型給出基于多QoS指標的全局QoS優(yōu)化模型，用整數(shù)規(guī)劃中的背包問題形式化描述了以用戶QoS效用函數(shù)為導向的資源分配問題。這種形式化描述將用戶的QoS需求、資源稀缺以及服務成本等網(wǎng)格關(guān)鍵因素統(tǒng)一在一個框架中分析，提出用價格和契約來控制網(wǎng)格QoS的策略。

關(guān)鍵詞：網(wǎng)格； 服務質(zhì)量； 計算經(jīng)濟模型

中圖法分類號：TP311 文獻標識碼：A 文章編號：1001-3695(2006)10-0050-02

QoSaware Grid Computing Economics Model

LIU Li1， YANG Yang1， CHEN Donge1，2

(1.College of Information Engineering， Beijing University of Science Technology， Beijing 100083， China; 2.Computer Center， Hebei University of Economics Business， Shijiazhuang Hebei 050061， China)

Abstract:Economicsbased QoS control mechanism is proposed in grid environment. Firstly， economic grid QoS architecture is presented. Secondly， apply/supply demand model of microeconomics to optimize objectives of multiple dimension QoS. A simple integer program formulation， which generalizes wellknown knapsack problems， describe QoSaware resource allocation problem.This formulation allows us to incorporate factors such as resource scarcity， users’ demand， and operating cost in a unified framework. Finally， price service and QoS contract are put forward.

Key words:Grid; Quality of Service(QoS); Computing Economics Model

隨著計算機科學的發(fā)展，網(wǎng)格技術(shù)已經(jīng)成為當前國內(nèi)外研究的一個熱點和前沿領(lǐng)域，而服務質(zhì)量（Quality of Service， QoS）作為網(wǎng)格資源管理研究的重要內(nèi)容之一，也逐漸成為網(wǎng)格研究的焦點。Ian Foster提出判斷網(wǎng)格的三個準則之一就是“提供非凡的服務質(zhì)量”[1]。開放網(wǎng)格體系結(jié)構(gòu)（Open Grid Service Architecture，OGSA）的目標就是通過跨分布式異構(gòu)平臺管理資源來交付無縫的服務質(zhì)量。QoS在多媒體和網(wǎng)絡(luò)通信領(lǐng)域中得到廣泛的研究。多媒體QoS研究關(guān)注如何以一定級別的服務質(zhì)量保證來存取和傳輸媒體文件。網(wǎng)絡(luò)QoS主要關(guān)注于如何提供更可靠的網(wǎng)絡(luò)傳輸服務，滿足應用的傳輸延時、延時抖動、分組丟失等質(zhì)量保證。IETF提出了兩種不同的Internet QoS體系結(jié)構(gòu)，即綜合服務IntServ[2]和區(qū)分服務DiffServ[3]。網(wǎng)格運行在互聯(lián)網(wǎng)絡(luò)之上，為滿足高性能網(wǎng)格應用端到端QoS保證的要求，除了網(wǎng)絡(luò)層次外，還需在網(wǎng)格系統(tǒng)結(jié)構(gòu)上實現(xiàn)相應的QoS保證。網(wǎng)格QoS問題的焦點在于網(wǎng)格能夠提供端到端QoS的程度，而不是僅提供網(wǎng)絡(luò)QoS。目前的大多數(shù)網(wǎng)格實現(xiàn)均只能提供部分的QoS功能。

用戶為了滿足自己的QoS需要，總是貪婪地通過競爭服務資源獲得最好的服務質(zhì)量，這樣造成資源的無效使用，因此需要研究經(jīng)濟的激勵機制和QoS定價策略。本文在QoS相關(guān)研究的基礎(chǔ)上，針對QoS管理和控制問題，結(jié)合經(jīng)濟學生產(chǎn)—消費模型[8，9]，建立基于經(jīng)濟模型的網(wǎng)格QoS管理結(jié)構(gòu)（Economics Grid QoS Architecture， EGQoS），通過經(jīng)濟的激勵機制使得服務提供者愿意根據(jù)質(zhì)量標準來提供區(qū)分服務，同時通過對QoS定價有效地控制資源的分配。

1 相關(guān)研究

網(wǎng)格QoS研究還處于基礎(chǔ)研究階段，主要是針對網(wǎng)格QoS體系結(jié)構(gòu)的研究。代表性研究有基于Globus的預留和分配體系結(jié)構(gòu)（GARA）[4]及網(wǎng)格QoS管理體系結(jié)構(gòu)(GQoSM)[5]。GARA是Ian Foster等人提出的網(wǎng)格QoS體系結(jié)構(gòu)，目標是為請求預留資源的客戶端或應用程序能從資源管理者處獲得特定的QoS提供保障。GQoSM [5]是英國Cardiff大學Rashid等人提出的OGSA環(huán)境下進行資源預留和自適應調(diào)節(jié)的面向服務QoS管理體系結(jié)構(gòu)。提供基于QoS屬性的服務發(fā)現(xiàn)；建立服務等級協(xié)議（Service Level Agreement，SLA），在中間件層和網(wǎng)絡(luò)層提供QoS保證機制，為分配的資源提供自適應調(diào)節(jié)。

國內(nèi)開始重視網(wǎng)格QoS，出現(xiàn)了一些研究文章[6，7]，許多網(wǎng)格平臺也開始加入對QoS的支持，建立起性能監(jiān)控平臺，更多的研究也在進行之中。

2 基于經(jīng)濟模型的網(wǎng)格QoS管理結(jié)構(gòu)

EGQoS結(jié)構(gòu)如圖1所示。EGQoS結(jié)構(gòu)中包括應用QoS層、虛擬組織QoS層和物理資源QoS層。應用QoS層描述了網(wǎng)格服務的QoS要求和用戶效用函數(shù)，如服務響應時間、服務的預算和服務可靠性要求等。虛擬組織QoS層是網(wǎng)格服務市場中間件，包括QoS管理、服務協(xié)商、服務計劃、服務定價以及記賬和收費。QoS管理負責服務發(fā)現(xiàn)、服務注冊，通過QoS協(xié)商決定是否接受用戶的QoS要求，它包括一些與服務有關(guān)的信息，如服務描述、服務等級協(xié)議SLA等；服務描述包括能提供的QoS的級別，如QoS保證服務、可控負載和盡力而為服務；服務計劃估計服務能力和服務執(zhí)行的效用值，根據(jù)QoS需求和效用函數(shù)組織各種資源并進行優(yōu)化配置；服務定價負責對QoS的定價；記賬和收費負責收集服務使用信息并根據(jù)服務的使用收費。物理資源QoS層描述資源節(jié)點的資源能力信息，根據(jù)QoS要求進行資源調(diào)度。

3 網(wǎng)格QoS控制的計算經(jīng)濟模型

將提供QoS保障的網(wǎng)格服務看作服務市場，QoS的生產(chǎn)者是網(wǎng)格服務提供者代理（Grid Service Provider Agent，GSPA），QoS的消費者是用戶或應用的需求代理（Grid Service Require Agent，GSRA），交易對象是具有一定QoS級別的服務，由GSPA以資源為生產(chǎn)要素生產(chǎn)出不同級別的QoS產(chǎn)品。用戶或應用對QoS的偏好由效用函數(shù)確定。優(yōu)化目標通過資源分配提供給用戶QoS保障，使整體效用最大化。

3．1 QoS指標和符號定義

通用的QoS指標屬性分類包括響應時間、成功率、服務可靠性和服務價格，該屬性可以在服務語義中進行描述。響應時間等于服務請求發(fā)出與該請求結(jié)果收到之間的時間延遲，表示為Qt；成功率指成功完成的任務數(shù)與總?cè)蝿諗?shù)的比率，表示為Qs；可靠性指服務可訪問的概率，即服務平均無故障時間與服務時間的比值，表示為Qa；服務價格表示用戶為獲得的服務所付的費用，表示為Qc。

用t={t1，…，tn}表示n類任務或應用集合；用r={r1，…，rm}表示m類資源集合；rmaxk表示第k個資源的最大能力（k=1，…，m）；質(zhì)量空間Qi表示完成任務ti的質(zhì)量指標Qij集合。

3．2 QoS需求模型

假設(shè)對于每一個任務集合t中的一個任務ti，均是有QoS需求集合Qi={Qi1，…，Qidi}（1≤i≤n，di=|Qi|），同時用效用函數(shù)表示用戶從完成任務中獲得的QoS滿意程度，效用函數(shù)ui∶Qi→R+，R+為非負實數(shù)空間。任務集中所有任務或應用的總效用為∑ni=1ui(Qi)，系統(tǒng)優(yōu)化目標是最大化總效用，表示為max∑ni=1ui(Qi)，s.t.piQi≤wi，其中wi表示第i個請求代理的預算。用uij表示用戶對獲得的Qij的滿意程度。圖2描述了不同QoS度量的具有代表性的效用函數(shù)圖形。用戶i的總效用表示為ui=∑dij=1ωijuij(Qij)，其中，ωij為任務ti的不同QoS度量的權(quán)重。

從圖2效用函數(shù)可知，QoS的度量指標包括消極度量和積極度量，Qt和Qc是消極度量，其值越大，效用越低；Qs和Qa是積極度量，其值越大，效用越高。

3．3 QoS生產(chǎn)模型

服務提供者根據(jù)計算能力、用戶對服務質(zhì)量的需求和偏好及服務成本來組織和調(diào)度資源。對某個任務的資源分配是服務提供者的生產(chǎn)要素，以一定的生產(chǎn)函數(shù)生產(chǎn)QoS產(chǎn)品，服務的成本決定于需要多少資源、使用多長時間、服務等級。該生產(chǎn)函數(shù)將資源分配與QoS聯(lián)系在一起，描述了系統(tǒng)的性能模型。

定義服務提供者為任務ti提供第k個QoS級別的服務所需要的資源分配為ri=(rik1，…，rikm)，定義生產(chǎn)函數(shù)hi∶ri→Qi，表示給定資源組合，可以提供什么級別的服務。又根據(jù)Qi與效用的關(guān)系，得到資源分配和效用的關(guān)系，表示為hi(ri)={q∈Qi|arg max ui(q)}，資源分配、QoS與效用三者關(guān)系如圖3所示。

圖3反映出，給定一組資源，生產(chǎn)者可以提供一定級別服務能力（QoS），通過獲得服務能力，實際用或應用可以獲得一定的效用。設(shè)服務提供者為任務ti提供第k個QoS級別的服務的價格為pi=(pi1，…，pik)，l=(l1，…，lm)為資源的價格向量，則服務提供者的目標是追求利潤最大化：

max(pihi(ri))-l(ri))，s.t.∑ni=1∑dij=1rijk≤rmaxk

3．4 優(yōu)化目標

通過對效用和生產(chǎn)函數(shù)的優(yōu)化，可以實現(xiàn)一個合理的分配，達到競爭均衡——帕累托優(yōu)化。Qij=h(rijk)，如果ti使用rijk資源后獲得了Qij級別的QoS，則令xijk=1，否則xijk=0。則系統(tǒng)目標為

max∑ni=1∑dij=1∑mk=1xijku(Qij)

s.t.∑ni=1∑dij=1rijk≤rmaxk，∑dij=1∑mk=1xijk≤1，xijk∈{0，1}

∑dij=1pjQij≤wi

因此QoS控制的資源分配問題可以轉(zhuǎn)換為整數(shù)規(guī)劃中的背包問題，采用動態(tài)規(guī)劃算法求解[10]。

4 服務定價和QoS契約

服務定價機制可以有效控制服務過載，當多任務到達某一服務節(jié)點時，服務提供者為了獲得高利潤會抬高價格，高價格使任務轉(zhuǎn)到其他服務節(jié)點。服務價格由服務類型、任務調(diào)用服務開始時間、服務持續(xù)時間決定。為了確保服務質(zhì)量，不能無限制地接收任務，接收任務的能力由QoS目標和服務的能力決定，因此對于保障型服務可以通過價格策略控制QoS的需求和任務的準入。

在競爭的市場環(huán)境下，服務提供者為了獲得更高利潤，總是在超出處理能力的情況下接收更多的任務， 從而延長了任務完成時間，影響了服務質(zhì)量，有些服務提供者甚至會終止低價值任務的執(zhí)行轉(zhuǎn)而執(zhí)行高價值任務，造成不公平。為了避免這些問題保障用戶的QoS，需要用合同契約來約束服務提供者的行為，保證用戶和服務提供者履行雙方的義務。合同內(nèi)容包括服務費、任務完成時間等。合同契約可以用SLA來描述。SLA是一種服務商與用戶之間簽署的，承諾用戶在支付一定服務費后所應得到的服務質(zhì)量（如性能、可靠性、帶寬、響應速度等）的法律性文件。SLA包含的信息包括GSRA和GSPA的唯一身份標志；服務信息的描述；QoS指標描述，包括服務時間、服務費用等。

5 結(jié)論

本文提出了基于計算經(jīng)濟模型的網(wǎng)格QoS控制機制，并給出該模型下的網(wǎng)格QoS管理結(jié)構(gòu)EGQoS；基于生產(chǎn)—消費模型給出QoS控制策略和基于多QoS指標的全局QoS優(yōu)化模型。模型中用戶的QoS偏好由效用函數(shù)描述，服務提供者以其擁有的資源為生產(chǎn)函數(shù)的要素，生產(chǎn)出不同級別的QoS產(chǎn)品，通過形式化描述將QoS管理和控制問題轉(zhuǎn)換為組合優(yōu)化問題，使得可以量化QoS并指導資源分配。最后提出用價格和契約來控制網(wǎng)格QoS的策略。

參考文獻：

[1]Foster I， Kesselman C. The Grid: Blueprint for a Future Computing Infrastructure[M]. USA:Morgan Kaufmann Publishers，1999.

[2]IETF Working Group.Differentiated Services[EB/OL].http://www.ietf.org/html.charters/diffservcharter.html.

[3]Bouch A， Kuchinsky A， Bhatti N. Quality is in the Eye of the Beholder: Meeting User’s Requirements for Internet Quality of Service[C]. Proceedings of ACM Conference on Human Factors in Computing Systems， 2000.297-304.

[4]Foster I， Roy A， Sander V. A Quality of Service Architecture that Combines Resource Reservation and Application Adaptation[C]. The 8th Int’l Workshop on Quality of Service (IWQoS’00)， 2000.181188

[5]AlAli R， Amin K， Laszewski G， et al. An OGSAbased Quality of Service Framework[C]. Proceedings of the 2nd International Workshop on Grid and Cooperative Computing， 2003.529-540.

[6]金海，陳漢華，等.CGSP作業(yè)管理器合成服務的QoS優(yōu)化模型及求解[J].計算機學報，2005，28(4):578-588.

[7]朱穗暉，都志輝，林偉堅.網(wǎng)格環(huán)境合同計算元服務的設(shè)計與應用[J].計算機學報，2005，28(4):486-494.

[8]張金水.數(shù)理經(jīng)濟學——理論與應用[M].北京：清華大學出版社， 1998.

[9]武康平.高級微觀經(jīng)濟學[M].北京：清華大學出版社，2001.

[10]馬振華.運籌學與最優(yōu)化理論[M].北京：清華大學出版社，1997.

作者簡介：

劉麗（1968-），女，高級工程師，主要研究方向為網(wǎng)格資源管理；楊揚（1955-），男，教授，博導，主要研究方向為計算機網(wǎng)絡(luò)和圖像處理。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文