基于層次模式的網(wǎng)格資源發(fā)現(xiàn)研究

印玉蘭　崔煥慶

摘 要：網(wǎng)格被普遍認為是下一代網(wǎng)絡(luò)，而資源發(fā)現(xiàn)是網(wǎng)格資源管理的基本組成部分。完全集中式資源發(fā)現(xiàn)機制和完全分布式資源發(fā)現(xiàn)機制都存在若干優(yōu)點和缺點，因此，在集中式和分布式資源發(fā)現(xiàn)方法的基礎(chǔ)上，提出了基于層次模式的資源發(fā)現(xiàn)方法。將網(wǎng)格中的資源分成三層結(jié)構(gòu)，其中包括物理網(wǎng)絡(luò)層、資源信息層和索引信息層，在此分層的基礎(chǔ)上提出了基于層次模式的資源發(fā)現(xiàn)方法。最后對該方法進行模擬，并對模擬結(jié)果進行分析，該方法有較好的時間擴展性和性能，同時，在這種方法中能通過并行的方法發(fā)現(xiàn)需要的資源。

關(guān)鍵詞：網(wǎng)格；資源發(fā)現(xiàn)；資源組織；虛擬組織；層次模型

中圖分類號：TP393.01文獻標識碼：A文章編號：1672-1098(2008)01-0081-04

收稿日期：2006-11-30

基金項目：安徽理工大學(xué)青年科學(xué)研究基金資助項目；安徽理工大學(xué)博、碩基金資助項目

作者簡介：印玉蘭(1976-)，女，江蘇泰興人，講師，碩士，主要研究方向為網(wǎng)格計算、并行算法等。

Grid Resource Discovery Method Based on Hierarchical Model

YIN Yu-lan1,CUI Huan-qing2

（1. School of Science, Anhui University of Science and Technology, Huainan Anhui 232001, China; 2. College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao Shandong 266510, China）

Abstract:Grid is commonly considered as next generation network, and resource discovery is a basic component of grid resource management. There are some disadvantages in totally-centering and totally-distributed resource discovery method. Base on centering resource discovery and distributed resource discovery methods，a hierarchical resource discovery method is proposed, in which resource in grid is divided into 3 structure layers, including physical network layer, resource information layer and index information layer. Based on the layers resource discovery method based on hierarchical model was put forward. The simulation results indicate that the method has good time extensibility and performance. Furthermore, in the method required resource can be discovered by collateral way.

Key words:grid; resource discovery; resource organization; virtual organization; hierarchical model

隨著高性能應(yīng)用要求的不斷提高，單臺高性能計算機已經(jīng)不能滿足一些超大規(guī)模應(yīng)用問題的解決。這就需要將地理上分布、系統(tǒng)異構(gòu)的資源通過高速網(wǎng)絡(luò)連接起來，協(xié)同解決一些大型應(yīng)用問題［1］。而網(wǎng)格的本質(zhì)特征就是：分布與資源共享。

如何在動態(tài)異構(gòu)的網(wǎng)格環(huán)境下實現(xiàn)資源的有效管理是網(wǎng)格計算面對的根本問題。網(wǎng)格計算下的資源管理是針對資源的分布性、存取的普適性，進行跨多個管理域的資源管理，以及資源的定位、查詢、更新。在傳統(tǒng)的單計算機系統(tǒng)和機群系統(tǒng)中，計算資源比較集中，在使用資源之前可以快速、可靠地進行資源定位，資源查找操作對計算性能的影響很小。而在網(wǎng)格計算中，由于資源的廣域分布、現(xiàn)有Internet存在的帶寬和延遲限制以及網(wǎng)絡(luò)的不可靠性，資源查找將在很大程度上影響計算性能［2］。因此，需要一種有效的資源發(fā)現(xiàn)方法來解決廣域資源的快速定位問題。

如不特別說明，本文假設(shè)在資源節(jié)點的描述中，有關(guān)資源節(jié)點中的資源的類型、數(shù)量、對外共享的優(yōu)先關(guān)系以及資源節(jié)點的有效生命期等屬性信息都已描述清楚。

1 現(xiàn)有的資源發(fā)現(xiàn)機制

已有的資源發(fā)現(xiàn)機制主要分為兩種：一種是集中式的；一種是分布式的。

傳統(tǒng)的集中式資源發(fā)現(xiàn)機制有一定優(yōu)點［3］：

(1) 系統(tǒng)的拓撲結(jié)構(gòu)比較簡單，容易構(gòu)建和維護，而且消耗??；

(2) 不存在資源信息不一致的問題，在小范圍內(nèi)的發(fā)現(xiàn)效率較高；

(3) 服務(wù)集中，易于資源共享并發(fā)控制，而且系統(tǒng)的安全性比較好。

同時，存在的缺點有：

(1) 可靠性比較差，當中心服務(wù)器出現(xiàn)故障時，系統(tǒng)將不能正常工作，系統(tǒng)沒有容錯功能；

(2) 系統(tǒng)的可擴展性比較差，受限于中央信息節(jié)點的能力，因為系統(tǒng)中資源節(jié)點的信息必須存儲在中心服務(wù)節(jié)點，并且所有的服務(wù)也必須通過中心服務(wù)節(jié)點，使得系統(tǒng)不能容易的增加大量資源。

然而，完全分布式資源發(fā)現(xiàn)機制與集中式資源發(fā)現(xiàn)機制的特點幾乎正好相反，主要缺點是［3］：

(1) 資源信息空間的無序性和無結(jié)構(gòu)性使得資源發(fā)現(xiàn)具有一定的盲目性；

(2) 節(jié)點可隨時加入或離開使得系統(tǒng)的安全性比較難以控制。

但完全分布式資源發(fā)現(xiàn)機制的優(yōu)點是其可擴展性和可靠性，節(jié)點可隨時加入網(wǎng)絡(luò)并將自己的資源共享給其它的用戶；同時任何節(jié)點的離開或故障都不會影響系統(tǒng)中其它節(jié)點的正常工作。

采用完全的集中式或者完全分布式的資源發(fā)現(xiàn)方法都不是很理想，都存在一些缺陷，而基于層次模式的網(wǎng)格資源發(fā)現(xiàn)集中了集中式和分布式發(fā)現(xiàn)方法的優(yōu)點。

2 基于層次模式的網(wǎng)格資源模型

網(wǎng)格資源發(fā)現(xiàn)是網(wǎng)格資源管理核心內(nèi)容之一，如何根據(jù)網(wǎng)格的特點，有效地監(jiān)控網(wǎng)格資源信息和狀態(tài)并查找網(wǎng)格資源，是要解決的核心問題。

2.1 基本定義

定義1 為了便于資源或資源信息的管理，對資源或資源信息進行分割而形成的若干個整體，稱為虛擬組織（Virtual Organization）。

定義2 為了便于虛擬組織中資源信息的查找，用來存放虛擬組織信息庫和鄰接表以概述虛擬組織資源信息的節(jié)點，稱為該虛擬組織的超節(jié)點［4］（Super Node）。

定義3 為了避免訪問擁塞，資源節(jié)點向網(wǎng)格注冊時，為其提供共享的每種資源設(shè)置一定的優(yōu)先關(guān)系，其中優(yōu)先權(quán)最高的資源，稱為這個資源節(jié)點的局部興趣（Local Interest）。

資源有三層組織結(jié)構(gòu)（見圖1），第一層為資源節(jié)點的物理網(wǎng)絡(luò)層（Physical Network Layer）；第二層為由若干個虛擬組織組成的資源信息層（Resource Information Layer）；第三層為索引信息層（Index Information Layer）。

圖1 基于層次結(jié)構(gòu)的資源組織模型

物理網(wǎng)絡(luò)層是提供資源共享的資源節(jié)點,而資源信息層是網(wǎng)格中注冊資源節(jié)點對應(yīng)的信息節(jié)點，在該層中，資源信息節(jié)點根據(jù)對應(yīng)物理網(wǎng)絡(luò)層中資源節(jié)點的IP地址和地理位置的相近原則，將資源信息節(jié)點分成若干個虛擬組織，并對虛擬組織中資源信息節(jié)點的數(shù)量設(shè)置上界和下界。索引信息層是每個虛擬組織對應(yīng)超節(jié)點組成的一個環(huán)形網(wǎng)絡(luò)。

2.2 資源信息層與索引信息層的組織形式

為了提高資源發(fā)現(xiàn)的效率，需要對資源信息層里虛擬組織中的資源信息節(jié)點進行合理的組織。由于資源發(fā)現(xiàn)時是給定的資源屬性，而不是具體的資源，因此根據(jù)資源屬性對資源信息節(jié)點進行組織。對虛擬組織中的資源信息節(jié)點采用局部星型拓撲結(jié)構(gòu)。根據(jù)資源的屬性，將所有相同屬性的資源聚集在一起(見圖2)。

圖2 a類資源的組織模型

索引信息層中的超節(jié)點主要用來存放虛擬組織的信息庫和鄰接表(見圖3～圖4)。

圖3 信息庫字段

圖4 鄰接表的格式在圖3～圖4中，其中MaxNum的值是隨T/F字段的值而變化的：

(1) 若T/F字段的值為T，則MaxNum的值是所有局部興趣為Type類的資源節(jié)點中含Type類資源的最大數(shù)量。

(2) 若T/F字段的值為F，則MaxNum的值是所有資源節(jié)點中含Type類資源的最大數(shù)量。

信息庫中將虛擬組織里含有資源的屬性、資源的數(shù)量以及資源節(jié)點對外共享的優(yōu)先關(guān)系等信息都描述得很清楚，在進行資源發(fā)現(xiàn)時可以很快確定虛擬組織中是否含有所需資源以及所需資源可能存在的概率。

鄰接表的組織是根據(jù)資源的屬性建立，對每一類資源都建立一個鏈表，首先是按照資源的局部興趣進行排列，再按所含該類資源的數(shù)量進行排列，形成有序的資源鏈表。這種方式有利于資源發(fā)現(xiàn)時很快能確定所需資源的大體所在方向。

4 網(wǎng)格資源發(fā)現(xiàn)算法

資源發(fā)現(xiàn)整個過程中， 第一階段完成對資源發(fā)現(xiàn)所需信息的準備，第二階段完成對需求資源類型的查找并確定查找的虛擬組織，第三階段完成對需求資源全部信息的查詢，第四階段實現(xiàn)資源請求的確認。

算法1 層次模式的網(wǎng)格資源發(fā)現(xiàn)算法

輸入：所需資源的信息

輸出：資源發(fā)現(xiàn)結(jié)果

算法步驟：

(1) 提交所需資源的信息，在本地區(qū)域查找是否存在所需資源；若沒有所需資源，則將所需資源信息發(fā)送至索引信息層；

(2) 確定所需資源的類型，將各超節(jié)點中信息庫里對應(yīng)類型資源的信息進行比較，根據(jù)需要進行排序比較，并作存儲；

(3) 根據(jù)排序的結(jié)果，用串行或者并行的方法，對一個或幾個超節(jié)點中的鄰接表進行遍歷，對已遍歷的資源節(jié)點作已遍歷的標志；

(4) 在索引信息層查找到可能存在需求資源的資源節(jié)點的信息傳輸?shù)劫Y源信息層，對該資源節(jié)點的信息進行核查，若滿足需求資源的要求，則返回該資源的地址給請求的用戶。否則，返回未發(fā)現(xiàn)資源的信息至索引信息層，繼續(xù)進行資源的發(fā)現(xiàn)，即重復(fù)(3)。4 評價

4.1 該層次模型的特點

(1) 整個網(wǎng)格沒有一個唯一的中央服務(wù)器，而是把中央服務(wù)器的功能分散在各個虛擬組織中，由各個虛擬組織的超節(jié)點完成，從而避免整個網(wǎng)格的單點失效。

(2) 每個虛擬組織具有一個超節(jié)點；超節(jié)點用于存儲虛擬組織的信息庫和資源鄰接表。

虛擬組織的規(guī)模要在一定范圍之內(nèi)，如果過大則進行分解，過小則進行合并。

4.2 算法時間復(fù)雜度分析

假設(shè)所需資源類型為a，網(wǎng)格中有玭個虛擬組織VO玦（i=1,2,3,…,n），即有n個超節(jié)點，其中m個虛擬組織中有a類資源。進一步，假設(shè)第玦個虛擬組織具有RN玦個資源節(jié)點，該虛擬組織中各個資源節(jié)點存在所需資源的概率相同，即為1RN玦。顯然，時間復(fù)雜性由兩部分組成：

(1) 對各信息庫中的信息進行排序，選擇合適的虛擬組織。利用最優(yōu)的排序方法，平均時間復(fù)雜性與最壞時間復(fù)雜性均為O(玬玪n玬)；

(2) 對所選虛擬組織的鄰接表進行遍歷以查找合適資源。如果采用串行查找方法，那么在該虛擬組織中進行查找的最壞時間復(fù)雜性為O(RN玦)，平均時間復(fù)雜性為O(ln㏑N璱)。

因此，整個資源發(fā)現(xiàn)算法的平均時間復(fù)雜性為O(玬玪n玬)+O(ln㏑N璱)。

最佳情況下，資源需求信息提交后，只遍歷一個虛擬組織的鄰接表，且在資源信息層進行信息匹配時一次就能滿足資源用戶的需求， 這種情況下所需的時間為選擇合適的虛擬組織所需要的時間， 因此最佳時間復(fù)雜度為O(O(玬玪n玬)+O(1))＝O(玬玪n玬)。

參考文獻：

［1］ 李偉，徐志偉，卜冠英. 網(wǎng)格環(huán)境下一種有效的資源查找方［J］.計算機學(xué)報，2003，11(26):1 546-1 549.

［2］ FITZBERALD S，F(xiàn)OSTER I，KESSELMAN C，et al.A directory service for configuring high-performance distributed computations［J］. In：Proceedings of the 6th IEEE International Symposium on High Performance Distributed Computing(HPDC 6)，Portland，OR，1997，365-375.

［3］ 劉星，肖衛(wèi)東，徐磊.基于復(fù)合拓撲的網(wǎng)格資源發(fā)現(xiàn)機制［J］.計算機工程與應(yīng)用，2005(9):132-136.

［4］ CARLO MASTROIANNI, DOMENICO TALIA,

ORESTE VERTA. A super-peer model for resource discovery services in large-scale Grids［J］.Future Generation Computer Systems， 2005(21)： 1 235-

1 248.

［5］ 徐志偉，馮百明，李偉.網(wǎng)格計算技術(shù)［M］.北京：電子工業(yè)出版社，2004.

［6］ 金海，袁平鵬，石柯.網(wǎng)格計算［M］.北京：電子工業(yè)出版社，2004.

［7］ 金蓓弘.分布式系統(tǒng)［M］.北京：機械電子工業(yè)出版社，2004.

［8］ 桂小林. 網(wǎng)格技術(shù)導(dǎo)論［M］.北京：北京郵電大學(xué)出版社，2005.

［9］ MORENO MARZOLLAL，MATTEO MORDACC-

HINI， SALVATORE ORLANDO.Resource Discovery in a Dynamic Grid Environment［J］.Proceedings of the 16th International Workshop on Database and Expert Systems Applications (DEXA05)，2005(5):4 159-4 188.

［10］ T N ELLAHI，M T KECHADI.Distributed Resource Discovery in Wide Area Grid Environments［J］,ICCS，2004,LNCS 3038,Springer-Verlag Berlin Heidelberg，2004，210-217.

［11］ CHENG ZHU,ZHONG LIU,WEINING ZHANG.Decentralized Grid Resource Discovery Based on Resource Information Communit［J］.Journal of Grid Computing， 2004(2):261-277.

［12］ MARK A SHEDON， ANDRZEJ DUDA， RON

WEISS，et al.Discover: a Rresource Discovery System Based on Content Routing［J］.Computer Networks and ISDN System，1995(27):953-972.

［13］ WEI LI， ZHIWEI XU， FANGPENG DONG.Grid

Resource Discovery Based on a Routing-Transferring Model，［EB/OL］.2006-05-10 http://www.chinagrid.net/grid/talksanddocs.html

［14］ 董方鵬，龔奕利，李偉.網(wǎng)格環(huán)境中資源發(fā)現(xiàn)機制的研究［J］.計算機研究與發(fā)展，2003，12(40):1 749-

1 754.

［15］ WEI LI，ZHIWEI XU，F(xiàn)ANGPENG DONG.Grid Resource Discovery Based on a Routing-Transferring Model.［EB/OL］.2006-05-10 http://www.chinagrid.net/grid/ talksanddocs.html

(責(zé)任編輯：何學(xué)華)