一種非線性的分布式網格資源調價算法

摘要：針對網格環境下分布式異步動態調價算法存在均衡價格收斂過程緩慢、調價效率較低的缺點，提出了一種基于市場機制的非線性調價算法。該算法結合了當前超額需求和過去超額需求對資源價格變化的影響，較真實地刻畫了需求變化后資源價格的波動過程。實驗證明，非線性的調價算法明顯地提高了價格收斂速度，降低了調價次數。關鍵詞：網格計算；市場機制；分布式調價；非線性

中圖分類號：TP393文獻標志碼：A

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

網格計算是近年來逐漸興起的一種新型分布式計算模式。它與傳統分布式計算的區別在于關注大規模資源共享與革新的應用。網格計算的主要目的是為了在分布、異構、自治和動態的網絡資源環境上構造動態的虛擬組織[1]，并在動態的、多組織協作中實現跨自治域的資源共享與問題求解，以有效地開展計算密集型和數據密集型的應用。

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

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

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

1基于代理的資源調價框架

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

資源代理管理著網格資源，代表各自所管理的資源的提供者的利益，以最大化資源提供者的利益為目標。資源代理與用戶代理進行交互，收集用戶代理的最新資源需求，并重新計算最新需求下的資源價格。當對資源的需求大于供給時，提高資源的價格；相反就降低資源的價格。完成價格更新后，資源代理會將最新價格發布給請求該資源的用戶代理。

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

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

2資源代理和用戶代理的調價算法

在描述調價算法前，首先給出幾項假設：

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

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

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

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

本文的調價算法基于Tatonnement調價原理[7]，即資源供不應求時，價格上升；供過于求時，價格下降。調價過程中價格計算公式如下：

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

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

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

其中：Pold是資源上次調價的價格；δnew是當前最新的價格調整速率；Enew表示資源的最新超額需求；Cnew表示資源的最新供給能力。在接下來的調價算法中，C0表示資源的初始供給能力，資源的供給能力隨著負載的變化是動態變化的。

通過構造李亞普諾夫能量函數可以證明Tatonnement調價過程是穩定且逐步衰減的。所以在調價過程中，資源價格雖然會在均衡價格周圍上下波動，但會逐步收斂到均衡價格。

2．1資源代理的調價算法部分

在調價過程中資源代理執行如下算法：

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

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

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

d）如果|E0|≤ε，那么資源的初始價格P0就是均衡價格，按照當前申請該資源的用戶代理需求進行分配，此次調價過程結束，資源分配完成，返回b）。

e）否則，按如下方式調整資源的價格：

(a)如果是首次進行調價，則Pnew＝P0+P0δ0。

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

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

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

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

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

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

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

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

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

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

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

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

h）收集各個用戶代理返回的在最新價格Pnew下的最優資源需求，并計算最新的資源超額需求Enew。

i）如果|Enew|≤ε，那么資源的最新價格Pnew就是均衡價格，按照當前申請該資源的用戶代理需求進行分配，此次調價過程結束，資源分配完成，返回b）。

j）返回e）。

2．2用戶代理的調價算法部分

在調價過程中用戶代理執行如下算法：

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

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

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

d）對于資源R的最新價格Pnew，用戶代理計算在該價格下的最優資源需求。

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

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

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

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

(c)否則轉d）。

3模擬實驗與結果分析

3．1實驗設置

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

實驗采用GridSim[8]為模擬的網格構建一個分層的網絡拓撲，如圖1所示。頂層由五個頂級路由節點組成，頂級路由節點之間的網絡傳輸速度為1 Gbps，以模擬網格的廣域分布特性。每個頂級路由節點連接一個自治管理域，一共有五個自治管理域，每個自治管理域有2個網格資源（對應有資源代理）和60個網格用戶（對應有用戶代理）。網格資源和網格用戶通過本地路由器連接到頂級路由節點上；網格資源與本地路由器、網格用戶與本地路由器以及本地路由器與頂級路由節點之間的網絡傳輸速度為100 Mbps。每個自治域都有一個GMD；GMD之間定時進行交互，以動態獲取整個網格的資源信息。

實驗中的網格資源模型來源于網格研究項目Gridbus中的一些網格節點，如表1所示。

表1來自Gridbus使用GridSim建模的網格資源

資源名資源屬性（操作系統，PE個數）Gridbus中等價的資源（位置）單個PE速度（MIPS）資源價格（GS，單PE單位時間）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

實驗中模擬了300個網格用戶，每個用戶都帶有網格任務（Gridlet）。在GridSim中，網格任務以Gridlet形式存在，包括網格任務長度（以MIPS為單位）、任務的輸入文件大小和任務的輸出文件大小（以Byte為單位）。

實驗中模擬了五個網格市場目錄（GMD）。網格資源代理在GMD上注冊所代理資源的屬性包括代理ID、資源數量、資源能力、資源的初始價格等。當調價完成后，資源代理需要在GMD公布資源的最新價格；用戶代理需要從GMD尋找合適的資源。

3．2結果分析

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

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

由此可以看出，在相同的網格環境、資源負載、用戶需求下，與線性算法相比，非線性算法降低了調價過程中的調價次數，減少了資源代理與用戶代理的交互次數，進而減少了通信量，同時也降低了調價過程所花時間，提高了調價效率，最終改善了用戶資源請求的實時響應速度。

4結束語

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

參考文獻：

［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］曹鴻強，肖儂，盧錫城，等.一種基于市場機制的計算網格資源分配方法[J].計算機研究與發展， 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］翁楚良，陸鑫達.一種基于市場機制的網格資源調價算法［J］. 計算機研究與發展，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.

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