印玉蘭　崔煥慶

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

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

中圖分類號(hào)：TP393.01文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-1098(2008)01-0081-04

收稿日期：2006-11-30

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

作者簡(jiǎn)介：印玉蘭(1976-)，女，江蘇泰興人，講師，碩士，主要研究方向?yàn)榫W(wǎng)格計(jì)算、并行算法等。

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

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

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

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

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

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

(1) 系統(tǒng)的拓?fù)浣Y(jié)構(gòu)比較簡(jiǎn)單，容易構(gòu)建和維護(hù)，而且消耗??；

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

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

同時(shí)，存在的缺點(diǎn)有：

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

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

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

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

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

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

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

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

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

2.1 基本定義

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

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

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

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

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

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

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

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

圖2 a類資源的組織模型

索引信息層中的超節(jié)點(diǎn)主要用來(lái)存放虛擬組織的信息庫(kù)和鄰接表(見(jiàn)圖3～圖4)。

圖3 信息庫(kù)字段

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

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

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

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

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

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

資源發(fā)現(xiàn)整個(gè)過(guò)程中， 第一階段完成對(duì)資源發(fā)現(xiàn)所需信息的準(zhǔn)備，第二階段完成對(duì)需求資源類型的查找并確定查找的虛擬組織，第三階段完成對(duì)需求資源全部信息的查詢，第四階段實(shí)現(xiàn)資源請(qǐng)求的確認(rèn)。

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

輸入：所需資源的信息

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

算法步驟：

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

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

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

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

4.1 該層次模型的特點(diǎn)

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

(2) 每個(gè)虛擬組織具有一個(gè)超節(jié)點(diǎn)；超節(jié)點(diǎn)用于存儲(chǔ)虛擬組織的信息庫(kù)和資源鄰接表。

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

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

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

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

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

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

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

參考文獻(xiàn)：

［1］ 李偉，徐志偉，卜冠英. 網(wǎng)格環(huán)境下一種有效的資源查找方［J］.計(jì)算機(jī)學(xué)報(bào)，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ù)合拓?fù)涞木W(wǎng)格資源發(fā)現(xiàn)機(jī)制［J］.計(jì)算機(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)格計(jì)算技術(shù)［M］.北京：電子工業(yè)出版社，2004.

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

［7］ 金蓓弘.分布式系統(tǒng)［M］.北京：機(jī)械電子工業(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ī)制的研究［J］.計(jì)算機(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é)華)