一種非線性的分布式網(wǎng)格資源調(diào)價(jià)算法

摘要：針對網(wǎng)格環(huán)境下分布式異步動(dòng)態(tài)調(diào)價(jià)算法存在均衡價(jià)格收斂過程緩慢、調(diào)價(jià)效率較低的缺點(diǎn)，提出了一種基于市場機(jī)制的非線性調(diào)價(jià)算法。該算法結(jié)合了當(dāng)前超額需求和過去超額需求對資源價(jià)格變化的影響，較真實(shí)地刻畫了需求變化后資源價(jià)格的波動(dòng)過程。實(shí)驗(yàn)證明，非線性的調(diào)價(jià)算法明顯地提高了價(jià)格收斂速度，降低了調(diào)價(jià)次數(shù)。關(guān)鍵詞：網(wǎng)格計(jì)算；市場機(jī)制；分布式調(diào)價(jià)；非線性

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)03－0692－03

網(wǎng)格計(jì)算是近年來逐漸興起的一種新型分布式計(jì)算模式。它與傳統(tǒng)分布式計(jì)算的區(qū)別在于關(guān)注大規(guī)模資源共享與革新的應(yīng)用。網(wǎng)格計(jì)算的主要目的是為了在分布、異構(gòu)、自治和動(dòng)態(tài)的網(wǎng)絡(luò)資源環(huán)境上構(gòu)造動(dòng)態(tài)的虛擬組織[1]，并在動(dòng)態(tài)的、多組織協(xié)作中實(shí)現(xiàn)跨自治域的資源共享與問題求解，以有效地開展計(jì)算密集型和數(shù)據(jù)密集型的應(yīng)用。

由于資源、資源的管理策略、用戶和應(yīng)用需求的異構(gòu)性[2]，網(wǎng)格環(huán)境下的資源調(diào)度和任務(wù)調(diào)度是一項(xiàng)非常復(fù)雜的工作。目前，大多數(shù)網(wǎng)格環(huán)境下的資源調(diào)度和分配一般基于某種成本函數(shù)，即由調(diào)度組件根據(jù)既定的成本函數(shù)來決定任務(wù)在哪里執(zhí)行（如Globus、Legion、Condor等）。但這些成本函數(shù)一般都是以系統(tǒng)為中心，目標(biāo)在于提高整個(gè)系統(tǒng)的吞吐量和效率，沒有充分考慮用戶的異構(gòu)需求，也沒有考慮到資源訪問成本的動(dòng)態(tài)性。與此同時(shí)，基于市場機(jī)制[3]的資源調(diào)度方法以用戶為中心，用市場機(jī)制解決用戶需求的異構(gòu)性和資源訪問成本的動(dòng)態(tài)性，兼顧了資源分配的公平和效率，非常適合解決資源調(diào)度問題。

運(yùn)用市場機(jī)制解決網(wǎng)格資源調(diào)度問題可分為兩步：a）通過感知資源的供求狀況進(jìn)行資源的動(dòng)態(tài)調(diào)價(jià)，并最終得到資源的均衡價(jià)格；b)根據(jù)a)得到的資源均衡價(jià)格實(shí)現(xiàn)資源分配。其中a)是運(yùn)用市場機(jī)制解決資源調(diào)度問題的關(guān)鍵所在。目前，確定資源均衡價(jià)格的方法主要有兩大類：a)集中式同步調(diào)價(jià)方法[3]。其優(yōu)點(diǎn)是均衡價(jià)格的收斂速度快、調(diào)價(jià)次數(shù)少；但由于采用集中方式進(jìn)行調(diào)價(jià)，擴(kuò)展性較差，不適合網(wǎng)格環(huán)境。b）分布式異步調(diào)價(jià)方法[4，5]。其擴(kuò)展性較好，同時(shí)不用考慮各種資源價(jià)格的相互影響，復(fù)雜度也較低，很適合網(wǎng)格這一類分布式環(huán)境；但這類方法存在調(diào)價(jià)過于頻繁、調(diào)價(jià)效率低等問題，限制了它在實(shí)際網(wǎng)格系統(tǒng)中的應(yīng)用。

在已有的分布式調(diào)價(jià)方法[2，4，5]中，價(jià)格是需求（準(zhǔn)確地說是資源需求與供給之差）的線性函數(shù)，也即資源價(jià)格在需求變動(dòng)時(shí)呈線性變化。在現(xiàn)實(shí)世界中，價(jià)格變化往往是非線性的，這種非線性變化既來自于需求的非線性變化，也來自于價(jià)格決策者本身的非線性因素。因而，用非線性方法刻畫價(jià)格的波動(dòng)將更符合實(shí)際，會(huì)帶來更高的調(diào)價(jià)效率。

1基于代理的資源調(diào)價(jià)框架

文獻(xiàn)[5]提出將基于代理的資源調(diào)價(jià)框架分為三層，從下到上分別為資源層、代理層和用戶層。在代理層存在資源和用戶兩種代理。

資源代理管理著網(wǎng)格資源，代表各自所管理的資源的提供者的利益，以最大化資源提供者的利益為目標(biāo)。資源代理與用戶代理進(jìn)行交互，收集用戶代理的最新資源需求，并重新計(jì)算最新需求下的資源價(jià)格。當(dāng)對資源的需求大于供給時(shí)，提高資源的價(jià)格；相反就降低資源的價(jià)格。完成價(jià)格更新后，資源代理會(huì)將最新價(jià)格發(fā)布給請求該資源的用戶代理。

用戶代理代表用戶以某種策略選擇資源，提出資源請求，并在獲得資源的使用后提交用戶任務(wù)到選定的資源上。用戶代理基于資源代理提供的最新資源價(jià)格信息，以最大化用戶的利益為目標(biāo)，更新對資源的需求量，并向資源代理通知自己的最新需求。

在調(diào)價(jià)框架中，還存在網(wǎng)格市場目錄[4]（grid market directory，GMD），主要記錄著資源的動(dòng)態(tài)信息。通常每個(gè)管理域有一個(gè)GMD。當(dāng)有資源加入網(wǎng)格時(shí)，其對應(yīng)的資源代理將向所在管理域的GMD注冊資源；當(dāng)有資源退出網(wǎng)格時(shí)，對應(yīng)的資源代理需要從GMD中注銷資源；當(dāng)資源的屬性（如資源能力、價(jià)格等）發(fā)生變化時(shí)，所屬的資源代理同樣需要在GMD及時(shí)更新。用戶代理也可以隨時(shí)向GMD查詢資源的最新信息（如當(dāng)前資源能力、最新價(jià)格等）。

2資源代理和用戶代理的調(diào)價(jià)算法

在描述調(diào)價(jià)算法前，首先給出幾項(xiàng)假設(shè)：

a）資源的初始價(jià)格可根據(jù)資源過去的價(jià)格、資源本身的成本、處理能力、資源數(shù)量等參數(shù)綜合確定。

b）一旦在調(diào)價(jià)過程中出現(xiàn)資源需求大于供給的情況，資源代理在此后的調(diào)價(jià)過程將不再接受新的資源請求，而只在已有的用戶資源需求中進(jìn)行調(diào)價(jià)。

c）當(dāng)資源的需求小于供給時(shí)，資源的價(jià)格將不斷降低。但是，資源的價(jià)格不會(huì)無限降下去，更不會(huì)最終降到零或負(fù)值。這是符合實(shí)際情況的，加入網(wǎng)格的資源擁有者在需求不足時(shí)，為了吸引更多用戶，可能會(huì)考慮降低價(jià)格，但不會(huì)將價(jià)格降得過低，更不會(huì)免費(fèi)提供資源給用戶。所以，資源的價(jià)格應(yīng)該有一個(gè)事先確定的最低值（這個(gè)值通常由資源擁有者確定，可稱為資源擁有者的最低心理價(jià)位），當(dāng)資源降到最低值時(shí)，就不會(huì)再降。

d）調(diào)價(jià)過程中，當(dāng)資源的當(dāng)前價(jià)格與下一次價(jià)格的預(yù)測值之差的絕對值小于某一閾值（由資源擁有者事先確定）時(shí)，可視為價(jià)格不再變化，調(diào)價(jià)過程結(jié)束。同樣，當(dāng)資源的需求與供給之差的絕對值低于某一閾值（也由資源擁有者事先確定）時(shí)，可視為資源的供求達(dá)到近似平衡，調(diào)價(jià)過程將結(jié)束。

本文的調(diào)價(jià)算法基于Tatonnement調(diào)價(jià)原理[7]，即資源供不應(yīng)求時(shí)，價(jià)格上升；供過于求時(shí)，價(jià)格下降。調(diào)價(jià)過程中價(jià)格計(jì)算公式如下：

Pnew＝(|Emin|Pmax+|Emax|Pmin）/（|Emin|+|Emax|)(1)

其中：Pnew是調(diào)價(jià)后最新的資源價(jià)格；Pmax和Pmin是上一輪價(jià)格波動(dòng)中資源的最高價(jià)和最低價(jià)；Emax和Emin分別是資源在最高價(jià)Pmax和最低價(jià)Pmin時(shí)的超額需求（資源的需求與供給之差），它們一個(gè)記錄當(dāng)前的超額需求，另一個(gè)記錄上一次的超額需求。式（1）結(jié)合了當(dāng)前超額需求和過去超額需求對資源價(jià)格變化的影響，較真實(shí)地刻畫了需求變化后資源價(jià)格的波動(dòng)過程。式（1）用于在資源價(jià)格出現(xiàn)最高價(jià)和最低價(jià)后的價(jià)格計(jì)算。在調(diào)價(jià)起始階段，資源價(jià)格可能會(huì)持續(xù)上升或下降，這時(shí)價(jià)格計(jì)算公式如下：

Pnew＝Pold+Poldδnew＝Pold+PoldEnew/Cnew(2)

其中：Pold是資源上次調(diào)價(jià)的價(jià)格；δnew是當(dāng)前最新的價(jià)格調(diào)整速率；Enew表示資源的最新超額需求；Cnew表示資源的最新供給能力。在接下來的調(diào)價(jià)算法中，C0表示資源的初始供給能力，資源的供給能力隨著負(fù)載的變化是動(dòng)態(tài)變化的。

通過構(gòu)造李亞普諾夫能量函數(shù)可以證明Tatonnement調(diào)價(jià)過程是穩(wěn)定且逐步衰減的。所以在調(diào)價(jià)過程中，資源價(jià)格雖然會(huì)在均衡價(jià)格周圍上下波動(dòng)，但會(huì)逐步收斂到均衡價(jià)格。

2．1資源代理的調(diào)價(jià)算法部分

在調(diào)價(jià)過程中資源代理執(zhí)行如下算法：

a）資源代理向網(wǎng)格市場目錄（GMD）注冊所代理資源的信息，包括代理ID、資源的能力、價(jià)格等。

b）初次收集用戶代理的資源請求，并根據(jù)資源能力得到初次超額需求E0。

c）確定資源的價(jià)格調(diào)整速率初值δ0＝E0/C0、超額需求中止參數(shù)ε（ε＞0）、價(jià)格差中止參數(shù)σ（σ＞0）和資源的最低價(jià)格ρ，并令Pmax＝Pmin＝P0。

d）如果|E0|≤ε，那么資源的初始價(jià)格P0就是均衡價(jià)格，按照當(dāng)前申請?jiān)撡Y源的用戶代理需求進(jìn)行分配，此次調(diào)價(jià)過程結(jié)束，資源分配完成，返回b）。

e）否則，按如下方式調(diào)整資源的價(jià)格：

(a)如果是首次進(jìn)行調(diào)價(jià)，則Pnew＝P0+P0δ0。

(b)如果上次價(jià)格上升且Enew＞ε，則δnew＝Enew / Cnew。

如果Pmax＝Pmin，則Pold＝Pnew，按式(2)更新價(jià)格Pnew；

如果Pmax＞Pmin，則Pold＝Pnew，Pmin＝Pold，Emin＝Enew，按式(1)更新價(jià)格Pnew。

(c)如果上次價(jià)格上升且Enew＜-ε，則Pold＝Pnew，Pmax＝Pold，Emax＝Enew，按式(1)更新價(jià)格Pnew。

(d)如果上次價(jià)格下降且Enew＞ε，則Pold＝Pnew，Pmin＝Pold，Emin＝Enew，按式(1)更新價(jià)格Pnew。

(e)如果上次價(jià)格下降且Enew＜-ε，則δnew＝Enew / Cnew。

如果Pmax＝Pmin，則Pold＝Pnew，按式(2)更新價(jià)格Pnew；

如果Pmax＞Pmin，則Pold＝Pnew，Pmax＝Pold，Emax＝Enew，按式(1)更新價(jià)格Pnew。

f）按如下方式檢查資源新價(jià)格Pnew：

(a)如果Pnew＜ρ，則Pnew＝ρ；

(b)如果|Pnew-Pold|＜σ，則此次調(diào)價(jià)過程結(jié)束，資源分配完成，返回b）。

g）將最新資源價(jià)格Pnew通知請求該資源的用戶代理。

h）收集各個(gè)用戶代理返回的在最新價(jià)格Pnew下的最優(yōu)資源需求，并計(jì)算最新的資源超額需求Enew。

i）如果|Enew|≤ε，那么資源的最新價(jià)格Pnew就是均衡價(jià)格，按照當(dāng)前申請?jiān)撡Y源的用戶代理需求進(jìn)行分配，此次調(diào)價(jià)過程結(jié)束，資源分配完成，返回b）。

j）返回e）。

2．2用戶代理的調(diào)價(jià)算法部分

在調(diào)價(jià)過程中用戶代理執(zhí)行如下算法：

a）用戶代理向GMD發(fā)布自己的資源請求。

b）GMD 向用戶代理返回能滿足任務(wù)資源需求的資源列表，包括所有資源的代理ID、能力、價(jià)格等。

c）用戶代理根據(jù)一定的資源選擇策略[2]，選擇滿足預(yù)算和期限約束的資源R。

d）對于資源R的最新價(jià)格Pnew，用戶代理計(jì)算在該價(jià)格下的最優(yōu)資源需求。

e）用戶代理向資源R的代理發(fā)布新的資源需求。

f）從資源R的代理接受最新的價(jià)格Pnew：

(a)如果|Pnew-Pold|＜σ，則調(diào)價(jià)結(jié)束，Pnew為此次調(diào)價(jià)過程的均衡價(jià)格；

(b)如果在新價(jià)格Pnew下，用戶預(yù)算不夠，則轉(zhuǎn)c），以尋找新的滿足預(yù)算約束的資源；

(c)否則轉(zhuǎn)d）。

3模擬實(shí)驗(yàn)與結(jié)果分析

3．1實(shí)驗(yàn)設(shè)置

通過模擬實(shí)驗(yàn)，將對已有的線性分布式調(diào)價(jià)算法與本文提出的非線性的分布式調(diào)價(jià)算法進(jìn)行比較，主要比較它們在均衡價(jià)格收斂速度方面的性能和效率。下面將用線性算法表示已有的線性分布式調(diào)價(jià)算法，非線性算法表示本文提出的非線性分布式調(diào)價(jià)算法。

實(shí)驗(yàn)采用GridSim[8]為模擬的網(wǎng)格構(gòu)建一個(gè)分層的網(wǎng)絡(luò)拓?fù)洌鐖D1所示。頂層由五個(gè)頂級(jí)路由節(jié)點(diǎn)組成，頂級(jí)路由節(jié)點(diǎn)之間的網(wǎng)絡(luò)傳輸速度為1 Gbps，以模擬網(wǎng)格的廣域分布特性。每個(gè)頂級(jí)路由節(jié)點(diǎn)連接一個(gè)自治管理域，一共有五個(gè)自治管理域，每個(gè)自治管理域有2個(gè)網(wǎng)格資源（對應(yīng)有資源代理）和60個(gè)網(wǎng)格用戶（對應(yīng)有用戶代理）。網(wǎng)格資源和網(wǎng)格用戶通過本地路由器連接到頂級(jí)路由節(jié)點(diǎn)上；網(wǎng)格資源與本地路由器、網(wǎng)格用戶與本地路由器以及本地路由器與頂級(jí)路由節(jié)點(diǎn)之間的網(wǎng)絡(luò)傳輸速度為100 Mbps。每個(gè)自治域都有一個(gè)GMD；GMD之間定時(shí)進(jìn)行交互，以動(dòng)態(tài)獲取整個(gè)網(wǎng)格的資源信息。

實(shí)驗(yàn)中的網(wǎng)格資源模型來源于網(wǎng)格研究項(xiàng)目Gridbus中的一些網(wǎng)格節(jié)點(diǎn)，如表1所示。

表1來自Gridbus使用GridSim建模的網(wǎng)格資源

資源名資源屬性（操作系統(tǒng)，PE個(gè)數(shù)）Gridbus中等價(jià)的資源（位置）單個(gè)PE速度（MIPS）資源價(jià)格（GS，單PE單位時(shí)間）R0Linux， 10Canberra， Australia5885.45

R1Linux， 6Brisbane， Australia7377.83

R2Linux， 12Melbourne， Australia6014.89

R3Linux， 18Penang， Malaysia6637.90

R4Linux， 16Bangkok， Thailand5037.68

R5Linux， 16Southampton， UK5644.41

R6Linux， 9HP， Houston， USA5307.05

R7SunOS， 16Hanover， USA7336.80

R8AIX， 16Illinois， USA7254.88

R9Linux， 14Barcelona， Spain5945.36

實(shí)驗(yàn)中模擬了300個(gè)網(wǎng)格用戶，每個(gè)用戶都帶有網(wǎng)格任務(wù)（Gridlet）。在GridSim中，網(wǎng)格任務(wù)以Gridlet形式存在，包括網(wǎng)格任務(wù)長度（以MIPS為單位）、任務(wù)的輸入文件大小和任務(wù)的輸出文件大小（以Byte為單位）。

實(shí)驗(yàn)中模擬了五個(gè)網(wǎng)格市場目錄（GMD）。網(wǎng)格資源代理在GMD上注冊所代理資源的屬性包括代理ID、資源數(shù)量、資源能力、資源的初始價(jià)格等。當(dāng)調(diào)價(jià)完成后，資源代理需要在GMD公布資源的最新價(jià)格；用戶代理需要從GMD尋找合適的資源。

3．2結(jié)果分析

圖2為線性算法與非線性算法在調(diào)價(jià)過程中調(diào)價(jià)次數(shù)的比較圖。實(shí)驗(yàn)中，對兩種算法都完成了10次重復(fù)實(shí)驗(yàn)，結(jié)果取平均值。從圖2可以看到，在每一個(gè)資源上，非線性算法調(diào)價(jià)次數(shù)均低于線性算法。以R9為例，線性算法的平均調(diào)價(jià)次數(shù)為10.4次，而非線性算法減少到6．9次，減少了36．7%。

圖3為線性算法與非線性算法在資源R9上的價(jià)格收斂過程比較圖。不失一般性，以資源R9為例，在其他資源上兩種算法有類似的價(jià)格收斂過程。從圖3可以看到，現(xiàn)行算法在調(diào)價(jià)過程中價(jià)格波動(dòng)較大，而非線性算法價(jià)格波動(dòng)相對平緩，導(dǎo)致線性算法需要更長的時(shí)間才能達(dá)到均衡價(jià)格。在資源R9上，線性算法需要60個(gè)仿真單位時(shí)間才能達(dá)到均衡價(jià)格，而非線性算法只需要35個(gè)仿真單位時(shí)間就達(dá)到了均衡價(jià)格，時(shí)間上減少了41.67%。

由此可以看出，在相同的網(wǎng)格環(huán)境、資源負(fù)載、用戶需求下，與線性算法相比，非線性算法降低了調(diào)價(jià)過程中的調(diào)價(jià)次數(shù)，減少了資源代理與用戶代理的交互次數(shù)，進(jìn)而減少了通信量，同時(shí)也降低了調(diào)價(jià)過程所花時(shí)間，提高了調(diào)價(jià)效率，最終改善了用戶資源請求的實(shí)時(shí)響應(yīng)速度。

4結(jié)束語

針對網(wǎng)格環(huán)境下分布式異步動(dòng)態(tài)調(diào)價(jià)算法存在均衡價(jià)格收斂過程緩慢、調(diào)價(jià)效率較低的缺點(diǎn)，提出了一種基于市場機(jī)制的非線性分布式調(diào)價(jià)算法。從實(shí)驗(yàn)結(jié)果可以看出，本文提出的非線性算法明顯地加速了均衡價(jià)格的收斂，降低了調(diào)價(jià)次數(shù)，提高了用戶資源請求的響應(yīng)速度，使得在實(shí)際網(wǎng)格環(huán)境中應(yīng)用基于市場機(jī)制的資源分配思想成為可能。與已有的線性調(diào)價(jià)算法相比，本文算法具有如下優(yōu)點(diǎn)：非線性的價(jià)格計(jì)算方法，更真實(shí)地刻畫了價(jià)格的波動(dòng)；已有的線性調(diào)價(jià)算法調(diào)價(jià)時(shí)只考慮了當(dāng)前的超額需求，而本文的非線性調(diào)價(jià)算法既考慮了當(dāng)前的超額需求，也考慮了過去的超額需求，使得資源價(jià)格在需求變化后能夠迅速收斂到均衡價(jià)格。下一步的工作將考慮結(jié)合已有的理論和實(shí)驗(yàn)成果，研究本文提出的非線性調(diào)價(jià)算法對資源負(fù)載平衡、網(wǎng)格系統(tǒng)整體負(fù)載平衡的影響。

參考文獻(xiàn)：

［1］FOSTER I，KESSELMAN C W，JIN H，et al.The grid 2:blueprint for a new computing infrastructure［M］. San Fransisco: Morgan Kaufmann Publishers，2004.

［2］BUYYA R.Economicbased distributed resource management and scheduling for grid computing［D］. Melbourne:Monash University， 2002.

［3］WOLSKI R，PLANK J，BREVIK J，et al.Analyzing marketbased resource allocation strategies for the computational grid［J］. International Journal of Highperformance Computing Applications，2001，15(3): 258－281.

［4］曹鴻強(qiáng)，肖儂，盧錫城，等.一種基于市場機(jī)制的計(jì)算網(wǎng)格資源分配方法[J].計(jì)算機(jī)研究與發(fā)展， 2002，39(8): 913－916.

［5］CHENG J Q，WELLMAN M P.The WALRAS algorithm:a convergent distributed implementation of general equilibrium outcomes［J］. Computational Economics，1998，12(1): 1－24.

［6］翁楚良，陸鑫達(dá).一種基于市場機(jī)制的網(wǎng)格資源調(diào)價(jià)算法［J］. 計(jì)算機(jī)研究與發(fā)展，2004，41(7): 11511156.［7］VARIAN H R.Microeconomic analysis[M].3rd ed.New York: W W Norton Company， 1992:398－401.

［8］BUYYA R，MURSHED M.GridSim:a toolkit for modeling and simulation of grid resource management and scheduling［J］.Journal of Concurrency and Computation: Practice and Experience，2002，14(1315):11751220.

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