基于SLA的網格計算資源分配框架

摘要：資源最優分配問題是最優化理論中的一個經典問題。它的目標是：在一個特定的應用環境中，滿足某種需求（時間限制、資源總數限制、服務自量限制等），使用有限的資源，最大程度完成多個任務，使得代價總和（通常是費用總和）最小。本文將給出在SLA限制下網格應用程序資源分配框架，同時給出最優分配的啟發式算法。

關鍵詞：網格；最優分配；SLA

1．最優分配問題模型

問題的基本模型：有資源集合RS，在任務集合TR中分配，使得系統性能量度（目標函數）達到最優化。其中K種資源指代不同資源類型，例如計算資源(Computing Resource)、服務提供商資源（Service Providers Resource）、網絡資源（Network Resource）、數據存儲資源（Data Storage Resource）等，每種資源都是集合，所以RS通常為一矩陣，該矩陣有K個列向量代表有K種類型的資源，每個列向量表示某種資源的集合。即RSi表示第i種資源集合。

用ST表示一個可行的資源分配集合，則Map(TR，RS1)∈ST（i∈[1，K]）。“可行”意味著分配能滿足基本要求，例如：滿足不同服務質量（QoS）要求或者時間要求，完成任務。用Costrainti(ST)表示與資源分配矩陣ST相關的，完成任務TRi的限制條件；用Costi(ST)表示與資源分配矩陣ST相關的，完成任務TRi的所需的代價，這樣，剩余資源分配問題可刻化如下：

在滿足條件下，其中Con表示應用環境中的限制條件；剩余資源分配的目標函數可形式化為：

式(1)是一個非線性整數編程問題，也是一個NP-hard問題。在某些時候，有效的算法還取決于目標函數的形式。如果不能預先知道問題結構信息，就需要使用某種形式的搜索算法。為了清晰的描述問題，使用圖1描述一個使用場景。

對圖1的解釋：用戶通過Web UI使用網絡資源，用戶發送請求，根據請求的不同，選擇不同的計算模型（Computing Model）（1）每種類型的用戶請求實例包含一種限制，反映用戶的需求，例如時間限制，換句話說，請求實例伴隨著模型的選擇和限制（也就是上文中的Con，Con可以根據要求進行擴展）。當Computing Model Provider接收到用戶的請求時，創建Computing Model實例（2）每種計算模型需要從不同數據庫集合里面選擇數據進行計算，這些數據由服務提供商提供（3）這些數據被組裝并被存儲起來，這項服務由數據庫提供商提供（4）Computing Model實例請求獲取數據（5）并使用這些數據（6）進行計算，最后，將計算結果返回給用戶（7）

2．網格應用與資源

為了進一部描述問題，假設只存在四種類型的資源：計算資源（compute resources），服務提供商資源（Service provider resources），網絡資源（network resources），數據存儲資源（data storage resource）。計算資源負責計算任務；SP是網絡環境中提供基于請求的服務的節點（例如財政數據，法律數據，信用數據，健康數據等）；網絡資源提供網絡環境下，節點之間數據傳輸的帶寬；數據存儲負責網格計算中數據的存儲。此外，服務提供商提供不同SLA（Service Level Agreement）限制下實現相同功能的服務。SAL是網絡服務商和客戶之間的協議，它詳細定義了不同服務質量（QoS）的服務，通常不同等級的服務的費用是不同的。

使用圖2來表示基于假設條件下的網格應用程序，它可以根據具體需求進行擴展。應用程序被形式化的定義成包含弧和節點的圖形（類似于圖2）。圖2包含三種類型的節點：

計算結點。這些結點處理計算任務，主要是完成計算模型所給出的計算任務。這些結點在圖中用圓形表示。

服務結點。這些結點在圖中使用矩形表示，它們被計算結點調用。

邏輯數據存儲結點。這些結點在圖中使用圓柱形表示，它們表示計算數據的存儲。這些邏輯數據存儲元素必須通過網絡映射到物理數據存儲設備。

圖2包含三種類型的弧：

優先級弧。從任務ti到任務tj的弧意味著tj只能等待ti執行完，并向它傳輸完所有數據后才能開始執行。弧上的標簽表示ti向tj傳輸的數據量。

服務請求弧。從任務ti到服務sj的弧意味著在執行ti時調用服務sj。弧上的標簽表示每次執行任務ti是調用服務tj的次數。任務ti可以按次序或并發地調用任意一種服務集合。為了表示按次序地調用服務，可以刻化從ti到si再到任務sk的弧，這意味著，ti先調用si，隨后再調用sk。

邏輯數據存儲弧。這種弧線可以從任務ti到邏輯數據存儲結點dj，也可以從邏輯數據存儲結點dj到任務ti。從任務ti到邏輯數據存儲結點dj的弧表示ti生成數據dj；從邏輯數據存儲結點dj到任務ti表示ti使用dj中的數據。弧上的標簽表示數據從邏輯數據存儲中讀取或者向其寫入。

此外，為了避免弧之間的交錯，上圖多次使用相同的邏輯數據存儲結點。

使用上述邏輯表示的方法描述的網格應用程序可以根據具體需求映射成物理表示包括計算資源集、物理數據存儲資源、網絡資源以及具體的服務提供商等。

3．資源分配的形式化描述

在給出形式化的公式之前需給出如下的參數定義。

TR：應用程序任務集

T：應用程序執行時間（seconds），

NCi：任務i請求的計算量（millions of cycles），

Ci：任務i的執行時間（seconds），

Vi，s：任務i調用邏輯服務提供商s的平均次數，

xi，j：從任務i到任務j傳輸的數據總量（Mbits），

Tki，J：任務i使用網絡資源k傳輸數據到任務j所花費的時間(seconds)，

wi，m：從任務i到邏輯數據存儲m所傳輸的數據量（Mbits），

rm，i：從邏輯數據存儲m到任務i所傳輸的數據量（Mbits），

Wi，m：從任務i到邏輯數據存儲m所傳輸的數據所花費的時間(seconds)，

Rm，i：從邏輯數據存儲m到任務i所傳輸的數據所花費的時間(seconds)，

NLDS：應用程序使用邏輯存儲結點的次數，

NLSP：應用程序調用邏輯服務提供商的次數。

定義資源集合及其相關的參數：

C：計算資源集合，

S：物理服務提供商資源集合，

N ：網絡資源集合，，

D ：物理數據存儲資源，

sk：計算資源k (k＝1，……，|C|) 的處理速度（millions of cycles per second），

Rk：服務提供商k (k＝1，……，|S|) 對服務請求的響應時間(second)，

Bk：網絡資源k (k＝1，……，|N|) 的網絡帶寬(Mbps)，

Lk：網絡資源k (k＝1，……，|N|) 的網絡延遲時間(second)，

Xk：物理存儲資源k (k＝1，……，|D|) 的數據傳輸速度(Mbytes/sec)。

定義代價參數：

cck：使用計算資源k (k＝1，……，|C|) 的代價($/sec)，

cbk：使用網絡資源k (k＝1，……，|N|) 的代價($/Mbps)，

cdk：使用物理存儲資源k (k＝1，……，|D|) 的代價($/Mbps)，

csk：使用服務提供商k (k＝1，……，|S|) 的代價（$）。物理服用提供商提供不同SLA下的服務。

利用上述定義的參數，很容易計算出一個網格應用程序的執行時間。

任務執行時間。運行于計算資源k上的任務ti的執行時間：

其中，Ks為任務ti所調用的服務提供商集，KsS，這種調用過程是按次序的；Sp(ti)為任務ti所調用的服務提供商集，Sp(ti)S，這種調用過程是并發的，II(ti)為任務ti所調用的所有并發集的集合，所以Sp(ti)II(ti)，說明不同的Sp(ti)調用又是按次序的。

網絡時間。 是由任務i使用網絡資源k傳輸數據xi，j到任務j所花費的時間所決定的。它近似的等于：

數據傳輸時間。邏輯數據存儲資源被映射到具體的物理數據資源k，用于數據讀寫所花費的時間為：

4．資源映射

上一節定義了四種資源，那么RS矩陣僅僅包含四個列向量，則RS=(C，S，N，D)，而TR=(t1，……，tN)，根據Map(TR，RSi)∈ST(i∈[1，K])，那么資源映射產生如下四類矩陣：

TC：計算資源映射矩陣。這是一個( |TR|，|C| )矩陣， 表示任務i被分配到計算資源K，否則為0。

CN：網絡資源映射矩陣。這是一個( |TR|，|TR| )矩陣，如果xi，j≠0，且使用了網絡資源k(k＝1，……，|N|)，則 CNi，j≠k，否則為0。

須 SPA：網絡服務提供商資源映射矩陣集合。每個SPAi表示與任務i相對應，SPAi是一個(NLSP，|S|)矩陣，(SAPi)s，k=1表示邏輯服務提供商s可以映射到具體的物理服務提供商k，否則為0。

ST：存儲資源映射矩陣。這是一個(NLDS，|D|)矩陣， 表示邏輯存儲資源m可以被映射為物理邏輯存儲資源，否則為0。

一旦得知Map(TR，RSi)∈ST(i∈s∈[1，K])的結果，那么執行時間T可以被輕易的求解出來。圖2中T的值如下：

其中*表示網絡資源Tki，j中實際的k值，這個值可以在CN中獲取。

5．最優問題

假設執行時間T就是表達式中的Con，即限制條件。那么如何得到成為最優問題中的關鍵。使用C(A，M)表示網格應用程序A根據映射M時所需要的代價。那么，根據上述的模型可得：

上式第一項為使用計算資源的總代價，第二項為使用網絡資源的總代價，第三項為使用不同服務提供商提供的數據存儲資源的總代價。

使用調度算法，經過多次循環，將所有的邏輯實體（任務，任務之間的通訊，邏輯服務提供商，邏輯數據存儲單元等）映射到物理資源（計算資源，網絡資源，物理服務提供商，物理數據存儲單元等）。每次循環時，域選擇（domain selection）程序語句首先確定還未分配的任務及資源子集合，然后進行相應的分配工作。使用TR+，C+，S+，N+，D+分別表示任務域，計算資源域，服務提供商域，網絡資源域，數據存儲資源域。每進行一次映射，就判斷是否滿足限制條件，然后使用域更新（domain update）程序更新每個域。根據task graph（圖2）進行任務域的確定。一個任務t被添加到TR+域中，當且僅當任務t已經準備就緒；從TR+域中刪除任務t，當且僅當調度算法已經將資源分配給任務t。其它物理資源域的更新當且僅當資源被任務t調用或者被任務t釋放。

暫且忽略其它資源分配，僅僅討論計算資源的分配。根據上述調度算法，每當一個任務完成時，對另一個新的任務的資源分配即將開始，這稱之為一個分配實例。分配實例有如下兩個規則：

1. 如果|TR+|=1，則將TR+域中的任務分配給C+域中代價最小的計算資源。

2. 如果|TR+|＞1，則先從C+域中選擇|TR+|個最小代價的計算資源子集，將TR+域中的任務分配給這個子集，TR+域中計算量最大的任務獲得子集中最快的計算資源，其它依次。

每次執行規則1或者2后，根據分配的資源立刻更新代價總值和執行時間總值。如果時間總值大于限定的時間值，從C+域刪除最小代價的網絡資源，分配算法返回到上次的分配實例，然后再重新分配。如果最終C+域為空，則調度算法返回到上次的分配實例。

為了討論其它資源的分配算法，假設存在兩類分配實例：任務開始分配實例和任務完成分配實例。

1．網絡資源的分配。網絡資源分配發生在任務完成分配實例中。如果將要完成的任務與其后繼者之間產生通訊，將執行網絡資源分配。如果僅僅只需一種網絡資源（假如將要完成的任務只有一個后繼者），則從N+域中選擇代價最小的網絡資源。如果需要n>1個網絡資源，則從N+域中選擇n個代價最小的網絡資源，并依次將這個子集中帶寬最大的網絡資源賦值給傳輸量最大的結點對。

2. 網絡服務提供商資源的分配。網絡服務提供商資源的分配發生在任務開始分配實例中。如果任務t使用多個網絡服務提供商資源，則從S+域中依次選擇代價最小的服務提供商資源分配給這個任務。

3. 數據存儲資源的分配。如果任務需要讀取或者寫入數據，那么物理數據存儲資源的分配發生在任務開始分配實例中。像前者一樣，D+域中最小代價的資源優先被分配。但與前者不同的是，物理存儲資源的分配是全局性質的，因此，一旦數據存儲資源的邏輯到物理的映射被確定下來，那些使用相同邏輯存儲資源的任務所映射的物理存儲資源必須被預先保留下來。

特別需要注意的是，當發生“返回到先前的分配實例”時需要判斷是“任務開始分配實例”還是“任務完成分配實例”。如果返回的分配實例是任務完成分配實例，先將最小代價的網絡資源從N+域中移除，然后再嘗試分配。如果返回的分配實例是任務開始分配實例，那么將有三種不同類型的資源需要重新分配計算資源，服務提供商資源和物理數據存儲資源。如果任務沒有調用任何服務提供商資源或物理數據存儲資源，那么僅僅只需要移除C+域中代價最小的資源。如果任務調用了服務提供商資源和/或物理數據存儲資源，那么需要確定與任務相關的計算，I/O處理，或者服務調用。這些資源的分配將基于任務的花費時間。移除最小代價的資源將對任務的執行時間產生最大的影響，同時保證了總代價最小，在此基礎上，繼續嘗試分配直到某種資源為空。

6.總結

企業級網格應用程序資源包括計算資源、網絡、數據存儲和服務提供者等。而網格資源最優分配目標在于在滿足SLA限制的前提下，以最小的代價進行資源分配。目標問題是一個NP-Hard問題，本文僅僅給出服務器企業網格體系結構的資源分配啟發式框架及其算法，更進一步的工作是開發滿足其它網格結構的啟發式框架。

參考文獻

[1]R. Buyya， D. Abramson， J. Giddy， and H. Stockinger， “Economic Models for Resource Management and Scheduling in Grid Computing ，”J. Concurrency and Computation : Practice and Experience， Special issue on Grid computing environments，2002.

[2]I. Foster and C. Kesselman， J. Nick， and S. Tueche， “Grid services for distributed system integration，” IEEE Computer，35(6)， 2002.

[4]I. Foster and C. Kesselman， J. Nick， and S. Tueche， The physiology of the grid: an open grid services architecture for distributed systems integration，2002.

[5]A. Othman， P. Dew， K. Djemame， and I. Gourlay， “Adaptive Grid Resource Brokering，” Proc.IEEE Intl. Conf. Cluster Computing， 2003.