??? 摘? 要： 根據(jù)資源在網(wǎng)絡(luò)上的分布特性，在混合式P2P結(jié)構(gòu)的基礎(chǔ)上設(shè)計(jì)了P2P-Grid物理結(jié)構(gòu)模型。實(shí)驗(yàn)證明，基于這種資源組織模式的資源查找所消耗的時(shí)間相對(duì)單一資源目錄樹(shù)而言，查找時(shí)間明顯縮短。
??? 關(guān)鍵詞： P2P-Grid模型? Grid-Peer? 資源組織? 資源發(fā)現(xiàn)? 資源組
?
??? 目前，對(duì)網(wǎng)格和P2P環(huán)境下資源發(fā)現(xiàn)進(jìn)行研究的論文很多，也提出了一些有效的解決辦法。而對(duì)真正決定資源查找效率的資源組織方法的研究則很少，結(jié)合P2P與Grid兩種新型網(wǎng)絡(luò)結(jié)構(gòu)的P2P-Grid方面的研究更少。P2P-Grid結(jié)構(gòu)是作者在考慮到現(xiàn)階段不同地區(qū)網(wǎng)絡(luò)之間的通信速度遠(yuǎn)遠(yuǎn)低于集群或局域網(wǎng)內(nèi)部的通信速度以及網(wǎng)絡(luò)環(huán)境下資源分布不均勻而在混合式P2P結(jié)構(gòu)的基礎(chǔ)上提出來(lái)的。雖然兩者都涉及到對(duì)虛擬社區(qū)內(nèi)共享資源的組織，且都采用較為先進(jìn)的技術(shù)，但二者有明顯不同。網(wǎng)格強(qiáng)調(diào)結(jié)構(gòu)健壯性，而P2P則恰好相反；網(wǎng)格系統(tǒng)整合的資源功能更加強(qiáng)大，而P2P更能夠有效地提高互聯(lián)網(wǎng)邊緣普通PC的利用率，這也恰恰是網(wǎng)格的最終目標(biāo)；網(wǎng)格動(dòng)態(tài)性的本質(zhì)需要容錯(cuò)機(jī)制，在執(zhí)行高度分布的程序時(shí)，需要一種可靠性和容錯(cuò)機(jī)制保證程序的正確運(yùn)行，而P2P系統(tǒng)具有廣泛分布性，可能會(huì)避免一些關(guān)鍵性的失敗。在局部范圍內(nèi)把地理位置彼此相近的資源構(gòu)造成規(guī)模適當(dāng)?shù)木W(wǎng)格系統(tǒng)。全局上把這些網(wǎng)格系統(tǒng)看作是P2P-Grid的Grid-Peer（相當(dāng)于混合式P2P結(jié)構(gòu)中的Super-Peer），并使用P2P技術(shù)組織這些Grid-Peer資源，從而充分體現(xiàn)兩者的優(yōu)點(diǎn)。在局部網(wǎng)格系統(tǒng)集中的高效率搜索和Grid-Peer之間健壯的分布式搜索之間達(dá)成一種平衡機(jī)制，且可有效地避免單一網(wǎng)格系統(tǒng)的瓶頸產(chǎn)生。
1? 相關(guān)工作
??? Gondor的匹配器[1]使用集中式組織方式組織資源，負(fù)責(zé)資源提供者和資源請(qǐng)求者之間需求的匹配。Adriana Iamnitchi等人使用P2P模式分布式組織資源[2]，并使用請(qǐng)求向前搜索的策略發(fā)現(xiàn)資源。中科院的織女星網(wǎng)格項(xiàng)目研究了基于路由轉(zhuǎn)發(fā)模型的資源發(fā)現(xiàn)方法[3]和面向資源發(fā)現(xiàn)的VEGA體系結(jié)構(gòu)[4]。
2? P2P-Grid模型研究與設(shè)計(jì)
2.1 P2P-Grid模型研究
??? 根據(jù)網(wǎng)絡(luò)環(huán)境下資源的廣泛分布性及其最終面向普通計(jì)算機(jī)用戶(hù)提供計(jì)算機(jī)能力的目標(biāo)，為避免單一網(wǎng)格系統(tǒng)上產(chǎn)生瓶頸，基于P2P和Grid的互補(bǔ)性，采用P2P-Grid模型[7]來(lái)組織網(wǎng)絡(luò)環(huán)境下的資源。根據(jù)銀行系統(tǒng)的運(yùn)作模式，采用“分而治之”的思想，把“單一網(wǎng)格系統(tǒng)”分割成若干個(gè)處于對(duì)等地位的“小規(guī)模網(wǎng)格”系統(tǒng)，本文稱(chēng)為Grid-Peer。這些Grid-Peer可以采用不同的網(wǎng)格技術(shù)來(lái)組織本系統(tǒng)內(nèi)部的資源，其交互方式采用分布式P2P技術(shù)。整個(gè)Grid-Peer具備較強(qiáng)的處理能力，可以完成本系統(tǒng)中絕大部分任務(wù)的資源需求。若任務(wù)在某個(gè)Grid-Peer中不能完成，則可以通過(guò)P2P技術(shù)轉(zhuǎn)移到可完成該任務(wù)的Grid-Peer中。
2.2 Grid-Peer系統(tǒng)地理位置的選擇
??? 網(wǎng)絡(luò)環(huán)境下的資源種類(lèi)眾多，數(shù)量龐大。相對(duì)于要調(diào)度的任務(wù)而言，需要對(duì)這些資源進(jìn)行有序的組織，并采取合理的措施進(jìn)行管理，根據(jù)任務(wù)需求對(duì)它們進(jìn)行調(diào)度。為提高資源的利用率，可采用類(lèi)似于銀行系統(tǒng)建立或新增分行的模式，在資源密集的地方優(yōu)先建立Grid-Peer。本文的Grid-Peer實(shí)際上是一個(gè)網(wǎng)格系統(tǒng)。但是相對(duì)于P2P系統(tǒng)而言，只是其中的一個(gè)Peer。在P2P-Grid系統(tǒng)中，最具有超級(jí)處理能力的Super-Peer管理一定數(shù)目的資源。例如，銀行系統(tǒng)優(yōu)先在人流量比較集中的地方建立分行，既能有效聚集閑散資金，提高其業(yè)務(wù)處理能力，又可方便附近的居民。這種思想同樣可應(yīng)用于P2P-Grid系統(tǒng)。P2P-Grid系統(tǒng)中的Grid-Peer優(yōu)先建立在網(wǎng)絡(luò)資源密集的地方，可以在本地范圍內(nèi)合理地整合資源，減少共同處理一個(gè)任務(wù)的資源之間通信所消耗的時(shí)間。同時(shí)本地用戶(hù)也可用更短的時(shí)間完成任務(wù)提交。當(dāng)系統(tǒng)返回結(jié)果時(shí)，其平均通信時(shí)間也比較短。
2.3 Grid-Peer系統(tǒng)層次功能模型研究
??? Grid-Peer相對(duì)于單獨(dú)的網(wǎng)格系統(tǒng)而言，需要一個(gè)和其他Grid-Peer進(jìn)行交互的接口，代理被用來(lái)充當(dāng)這個(gè)角色。實(shí)際上，代理可以作為本地Grid-Peer的代理，其功能是接受用戶(hù)提交的任務(wù)，與其他Grid-Peer系統(tǒng)中的代理交互，實(shí)現(xiàn)不同Grid-Peer之間的資源共享，負(fù)責(zé)任務(wù)在Grid-Peer系統(tǒng)之間的遷移，從而達(dá)到多個(gè)Grid-Peer系統(tǒng)之間的負(fù)載均衡。圖1為Grid-Peer系統(tǒng)功能模型（PC：個(gè)人計(jì)算機(jī)，HPC：高性能計(jì)算機(jī)，LAN：局域網(wǎng)）。
?
??? 網(wǎng)格用戶(hù)可以向任何一個(gè)代理提出資源請(qǐng)求。代理接受網(wǎng)格用戶(hù)的抽象任務(wù)信息包后，查看其所需的資源信息，把它交給相應(yīng)的資源管理器處理。資源管理器查詢(xún)某資源組隊(duì)列，發(fā)現(xiàn)了多個(gè)資源后，選擇最適合的資源分配給任務(wù)。若沒(méi)有在資源組中查到任務(wù)需求的資源，則查找性能較高的資源組或向代理返回“查找失敗”消息。代理收到“查找失敗”消息后，向其他的代理傳送該任務(wù)的需求信息，直到找到相應(yīng)的資源，或經(jīng)過(guò)一段的時(shí)間后，以失敗結(jié)束這次資源查找過(guò)程。
3? Grid-Peer中的資源組織
3.1 Grid-Peer與單一網(wǎng)格系統(tǒng)的區(qū)別
??? Grid-Peer與單一網(wǎng)格系統(tǒng)在規(guī)模和系統(tǒng)資源的組成上有很大區(qū)別。Grid-Peer的規(guī)模比單一網(wǎng)格系統(tǒng)小。其主要特點(diǎn)是在系統(tǒng)的核心部分很少出現(xiàn)瓶頸現(xiàn)象，它管理的資源在性能上很普通，可能是許許多多的PC機(jī)。另外一個(gè)顯著的區(qū)別就是具有和其他Grid-Peer進(jìn)行交互的接口。Grid-Peer整合的資源地理位置之間的平均距離也比單一網(wǎng)格系統(tǒng)中的短，它組織的資源可以是高校中的某幢樓層里或整個(gè)校園中并包括其附近地區(qū)里的計(jì)算機(jī)，或其他設(shè)備。
3.2 基本概念
??? 定義1 資源屬性值域R為某資源任一屬性值所有可能取值為實(shí)數(shù)的集合，R上的值域定義為VA＝{x|r1≤x≤r2，x∈R，r1∈R，r2∈R}，則令VA＝[r1，r2]，VA為R的子集，表示VA由所有介于r1(可以等于r1)和r2之間的實(shí)數(shù)組成。
??? 定義2 資源組：資源屬性值在某個(gè)資源屬性值域范圍內(nèi)的資源集合。
??? 定義3 計(jì)算能力：計(jì)算資源在單位時(shí)間內(nèi)運(yùn)算的次數(shù)。
??? 定義4 CPU==[1G，2G]，CPU的主頻取值在1GB～2GB的范圍內(nèi)。
??? 定義5 Mem(內(nèi)存)＝＝[64M，128M]內(nèi)存容量取值在64MB～128MB之間。
??? 性質(zhì)1 同一資源組中的資源具有的計(jì)算能力屬于規(guī)定該資源組CPU屬性值域的集合。
??? 性質(zhì)2 同一資源組中的資源具有的存儲(chǔ)容量屬于規(guī)定該資源組的內(nèi)存屬性值域的集合。
3.3 資源組目錄樹(shù)
??? 資源的組織方式?jīng)Q定資源發(fā)現(xiàn)、資源匹配和資源調(diào)度等其他資源管理技術(shù)。而資源管理器為用戶(hù)選擇資源、匹配資源請(qǐng)求與具體資源的方法有很多種，不同方法會(huì)影響資源的利用率和系統(tǒng)開(kāi)銷(xiāo)。P2P-Grid環(huán)境下的資源組織會(huì)影響到Grid-Peer的資源管理系統(tǒng)內(nèi)部模塊之間以及Grid-Peer系統(tǒng)之間的通信模式，也會(huì)決定P2P-Grid資源管理系統(tǒng)是否可擴(kuò)充。通常有集中式和分布式兩種資源組織方式。由于P2P-Grid系統(tǒng)本身是P2P技術(shù)與Grid技術(shù)的融合，整體上可看做是一種分布的集中式系統(tǒng)。本文采用分布式與層次式結(jié)合的資源組織方式組織P2P-Grid環(huán)境下的資源。為了共享接入Grid-Peer中的資源，應(yīng)注意資源接入到互聯(lián)網(wǎng)中的不同方式和不同種類(lèi)：有的計(jì)算機(jī)通過(guò)其所在的局域網(wǎng)接入互聯(lián)網(wǎng)，而另外一些則直接接入互聯(lián)網(wǎng)；有的是普通工作站，另外的計(jì)算資源則是一些高性能計(jì)算機(jī)，資源使用方式很不相同。按照資源被接入到互聯(lián)網(wǎng)的方式，把主要執(zhí)行計(jì)算的計(jì)算資源分為高性能計(jì)算機(jī)、PC和LAN中的計(jì)算機(jī)三個(gè)大類(lèi)，分別用三個(gè)不同的服務(wù)器對(duì)這些資源進(jìn)行管理。局部網(wǎng)格中還包括對(duì)這三大類(lèi)資源屬性信息進(jìn)行管理的高性能計(jì)算資源管理器、PC資源管理器和LAN資源管理器。Grid-Peer系統(tǒng)中使用分類(lèi)的層次式資源組目錄樹(shù)記錄資源屬性信息。資源組由計(jì)算能力相當(dāng)?shù)馁Y源聚集而成。
??? 分類(lèi)層次式資源組目錄樹(shù)的邏輯組織是根據(jù)物理資源實(shí)際拓?fù)浣Y(jié)構(gòu)由資源向Grid-Peer注冊(cè)建立起來(lái)的。資源組目錄樹(shù)第一層主干節(jié)點(diǎn)充當(dāng)三種不同類(lèi)別的資源信息管理器。
??? 資源的組織形式如圖2和圖3所示。用戶(hù)作業(yè)請(qǐng)求計(jì)算資源時(shí)，一般會(huì)指定所需資源的CPU、內(nèi)存和OS(操作系統(tǒng))的具體的屬性值所在的范圍，在對(duì)計(jì)算資源分類(lèi)時(shí)（如圖2中的PC、LAN和HPC），可再細(xì)分多個(gè)子目錄，分別由CPU、內(nèi)存和操作系統(tǒng)的屬性值范圍確定。資源組目錄樹(shù)的葉子節(jié)點(diǎn)是屬于某資源組的資源，其某些屬性值都在指定的范圍內(nèi)。查找資源時(shí)可快速準(zhǔn)確地找到某一屬性值范圍內(nèi)的資源集合，從而減少資源搜索的時(shí)間。
?
?
??? 從圖2中可以看出，Grid-Peer系統(tǒng)中的資源分為PC資源(一般是通過(guò)寬帶技術(shù)直接訪(fǎng)問(wèn)互聯(lián)網(wǎng))、LAN資源(作為一個(gè)小型的局域網(wǎng)絡(luò)實(shí)體通過(guò)局域網(wǎng)訪(fǎng)問(wèn)互聯(lián)網(wǎng))和HPC資源。圖2中的LAN 管理器的資源子樹(shù)如圖3所示。由于HPC 管理器的資源子樹(shù)和LAN管理器的資源子樹(shù)大同小異，本文不再加以描述。
??? 圖3與圖2顯著的區(qū)別是把LAN當(dāng)作一個(gè)整體，并且每個(gè)LAN擁有工作站的數(shù)目不同，具有相同數(shù)量工作站的LAN都屬于同一個(gè)LAN資源組。由于LAN中工作站之間可能出現(xiàn)的異構(gòu)性，確定了某個(gè)LAN中具體的工作站數(shù)目后，繼續(xù)采用PC資源管理器中的PC資源組的組織方法。其優(yōu)點(diǎn)是：一旦PC資源管理器太過(guò)忙碌，LAN資源管理器中工作站同樣可以當(dāng)作PC資源來(lái)運(yùn)行任務(wù)。
4? 資源發(fā)現(xiàn)
??? 把單一網(wǎng)格系統(tǒng)分割成許多Grid-Peer，組成P2P-Grid系統(tǒng)。每個(gè)Grid-Peer系統(tǒng)管理資源的數(shù)目變少，可以避免單一網(wǎng)格系統(tǒng)中出現(xiàn)的瓶頸現(xiàn)象。當(dāng)某個(gè)Grid-Peer系統(tǒng)規(guī)模大到一定程度時(shí)，可以把該Grid-Peer系統(tǒng)分割成兩個(gè)Grid-Peer系統(tǒng)。P2P-Grid系統(tǒng)中的許多Grid-Peer不僅可以同時(shí)工作，而且，由于Grid-Peer規(guī)模適中，在任務(wù)處理、資源發(fā)現(xiàn)、資源調(diào)度等方面能夠縮短處理時(shí)間，可進(jìn)一步提高整個(gè)P2P-Grid系統(tǒng)的效率。
??? 采用分類(lèi)的層次式資源組目錄樹(shù)模式組織Grid-Peer系統(tǒng)中的資源時(shí)，資源首先被分為三類(lèi)：PC資源、LAN資源和HPC資源。在每類(lèi)資源構(gòu)成的子樹(shù)中，把計(jì)算能力相當(dāng)?shù)馁Y源聚集起來(lái)保存在同一個(gè)資源組中，彼此之間可互為備份資源。一旦運(yùn)行任務(wù)的資源出錯(cuò)，備份資源馬上可以接收遷移過(guò)來(lái)的任務(wù)并進(jìn)行工作，以保證用戶(hù)的QoS需求。系統(tǒng)進(jìn)行資源查找時(shí)，其時(shí)間復(fù)雜度主要體現(xiàn)在對(duì)資源樹(shù)進(jìn)行層次遍歷上。由于資源各個(gè)屬性值的變化范圍不大（操作系統(tǒng)類(lèi)型種類(lèi)有限，硬件中組件屬性取值一般都是相對(duì)應(yīng)的，例如CPU主頻高，內(nèi)存容量也比較大），所以在資源樹(shù)的某一層進(jìn)行遍歷時(shí)，比較次數(shù)較少，資源查找范圍相對(duì)于單一的資源樹(shù)而言縮小了。
??? 對(duì)Grid-Peer系統(tǒng)中的PC資源和LAN資源的發(fā)現(xiàn)也進(jìn)行了研究。試驗(yàn)環(huán)境采用Globus Toolkit 3.2建立了小型網(wǎng)格平臺(tái)，其中有3臺(tái)IBM品牌機(jī)， CPU為2.66GHz，內(nèi)存為256MB，1臺(tái)兼容機(jī)，CPU為266MHz，內(nèi)存160MB。每臺(tái)計(jì)算機(jī)模擬成一個(gè)管理Grid-Peer系統(tǒng)中資源信息的服務(wù)器，即資源管理器。該資源管理器中保存有記錄資源屬性信息的資源組目錄樹(shù)，對(duì)Grid-Peer系統(tǒng)中的資源信息進(jìn)行管理，主要就是對(duì)該資源組目錄樹(shù)進(jìn)行操作。在這個(gè)模擬平臺(tái)上，對(duì)在資源組目錄樹(shù)和單一資源目錄樹(shù)中資源查找所消耗的時(shí)間進(jìn)行了研究。圖4和圖5分別為查找單個(gè)資源和多個(gè)資源所消耗的時(shí)間。
?
?
??? 圖4是針對(duì)資源組目錄樹(shù)和資源目錄樹(shù)（就是資源沒(méi)有進(jìn)行分類(lèi)聚合）兩種不同模式的資源組織方式查找單個(gè)PC資源所消耗的時(shí)間。從中可以看出，資源組目錄樹(shù)這種資源組織方式在Grid-Peer系統(tǒng)中的資源比較多的情況下，其資源查找所消耗的時(shí)間相對(duì)資源目錄樹(shù)而言比較短。但是，兩種資源組織方式隨著系統(tǒng)中注冊(cè)的資源數(shù)量的增加、系統(tǒng)規(guī)模的變大，其資源查找時(shí)間也明顯增加。
??? 圖5是查找資源組目錄樹(shù)中含有5個(gè)工作站的LAN資源所消耗的時(shí)間與在單一資源目錄樹(shù)中查找5個(gè)資源所消耗時(shí)間的比較。隨著Grid-Peer系統(tǒng)規(guī)模的變大，發(fā)現(xiàn)5個(gè)資源所消耗的時(shí)間也隨著增加，這與發(fā)現(xiàn)單個(gè)資源的情況是相同的。從圖5可知，在增加相同資源數(shù)目的情況下，資源組目錄樹(shù)中資源發(fā)現(xiàn)時(shí)間的增加量要小于在單一資源目錄樹(shù)中資源發(fā)現(xiàn)時(shí)間的增加量。這是由于LAN資源被當(dāng)作一個(gè)整體時(shí)，LAN資源的數(shù)目增加相對(duì)單一資源目錄樹(shù)中把LAN中的每個(gè)工作站作為一個(gè)資源時(shí)資源數(shù)目增加得要少。
5? 結(jié)? 論
??? 隨著網(wǎng)格技術(shù)和P2P技術(shù)的成熟，結(jié)合P2P和Grid的P2P-Grid也將成為高性能計(jì)算研究中的一個(gè)熱點(diǎn)。在研究了P2P-Grid的資源組織模型后發(fā)現(xiàn)，采取層次式資源組模式的資源組目錄樹(shù)組織資源時(shí)，由于資源發(fā)現(xiàn)時(shí)間查找范圍縮小了，其查找時(shí)間大大縮短，這無(wú)疑將會(huì)提高整個(gè)P2P-Grid的性能。
參考文獻(xiàn)
1?? Raman R，Livny M，Solomon M.Matchmaking：distributed resource management for high throughput computing.In：Proc.of the 7th IEEE Int′l Symp.on High Performance?Distributed Computing.Chicago，IL，USA，1998
2?? Iamnitchi A，F(xiàn)oster I.On Fully Decentralized Resource Discovery in Grid Environments.In：Craig A.Lee.Grid?Computing-Grid 2001，Germany：Springer，2001
3?? Li W，Xu ZW，Dong FP et al.Grid Resource Discovery? Based on a Routing-transgerring model.In：Manish?Parashar，Grid Computing-Grid 2002，Germany：Springer，2002
4?? Gong Y l，Dong F P，Li W et al.VEGA Infrastructure for? Resource Discovery in Grids.J Computu Sci.&Technol， 2003；18(4)
5?? 徐志偉，馮百明，李偉.網(wǎng)格計(jì)算技術(shù).北京：電子工業(yè)出版社，2004
6?? 周曉，陳鳴.基于散列值的廣域網(wǎng)服務(wù)發(fā)現(xiàn).軟件學(xué)報(bào)，2004；15(10)
7?? 葉從歡，江武漢，孫世新.P2P與Grid的結(jié)合：P2P-Grid模型研究.微型機(jī)與應(yīng)用，2005；24(5)