基于改進的Grid_P2P 網絡模型研究

劉洺辛，陳 晶，陳端君

（燕山大學 秦皇島066004）

1 引言

P2P是一種實現資源共享的分布式技術，系統中的各個節點是對等的，可以松散地結合在一起，資源的查詢過程并發進行。因此將P2P技術和網格技術融合，尋找更適用于網格環境下的資源管理是當今研究的熱點。

作為P2P技術與網格技術結合的結果——Super-Peer網絡[1]是近年來新興的一種網絡模型，由2003年B.Yang等人提出，他們把P2P網絡分為純P2P網絡、混合P2P網絡和Super-Peer網絡三種。2005年 Carlo Mastroianni等明確提出大規模網格中的 Super-Peer模型[2]。2006年J.Holliday等人針對大規模網絡環境下如何選擇Super-Peer問題進行了論述[3]。

隨著技術的發展，網格計算和P2P計算也在不斷融合。目前將P2P技術引入網格成為網格研究的一個方向，由此產生一種網絡模模型結構Grid_P2P，Grid_P2P網絡的本質仍屬于一種Super-Peer網絡。參考文獻[4]和參考文獻[5]全面詳細地闡述了Grid與P2P結合的Grid_P2P模型的研究，引入了Super-Peer的概念，同時提出了該模型的結構及一些相關術語。參考文獻[6]則進一步在網格環境里基于P2P提出了網絡覆蓋結構。

2 Grid_P2P模型簡介

Grid_P2P模型將P2P模型中超級節點的思想引入到網格系統，在網格的超級計算機和普通節點之間引入Super-Peer的概念，Super-Peer的選取可以基于地理位置或基于普通節點中某些高性能計算機，在Super-Peer與Super-Peer之間構成一個P2P的中間層，形成如下的網絡模型[7]，如圖1所示。

圖1是一個局部資源管理系統模型，圖中網格資源通過向信息接收器提交資源屬性信息請求注冊資源，信息接收器按資源類別把資源信息轉交給PC管理器、LAN管理器或HPC（high performance computer）管理器。用戶通過用戶界面向任務接收器提交任務，任務接收器響應該任務對資源的請求，并向資源管理器提出資源查找請求。資源管理器通過一定的查找算法搜索所注冊的可用邏輯資源，并把這些可用資源的屬性信息按一定的策略和級別高低順序記錄在可用的資源管理器即資源預留服務器中，同時選擇最佳的資源或資源集合分配給所提交的任務。局部資源管理系統中HPC管理器、PC管理器和LAN管理器除了要管理其中的資源樹的邏輯信息外，還要把資源分為可用資源和正在運行任務的資源，并對這些資源進行監控，實時獲取資源的最新狀態信息，以便資源調度時不至于把任務分配到不能正常運行的計算資源上。信息接收器同時還要及時知道系統中的負載情況，一旦發現系統的負載過重，則把接收的任務及時地轉移到其他最佳的空閑超級Peer，從而保證系統在Grid_P2P環境下的負載平衡。

3 改進的Grid_P2P網絡模型研究

3.1 結構描述

已有的Grid_P2P網絡模型主要涉及如下兩層：在第一層中主要涉及到普通的Peer節點，每一個普通的Peer都從屬于一個Super-Peer，即在一個Super-Peer的域內，所有的Peer都和該Super-Peer相連接。底層Peer需要向Super-Peer注冊信息，Peer既可以是資源的提供者，也可以是資源的請求者。在第二層Super-Peer中，Super-Peer與Super-Peer之間以對等的方式建立無結構的P2P網絡。Super-Peer與同層的Super-Peer節點之間建立鄰居節點關系。

每個超級Peer即Super-Peer構成一個局部的網絡系統，負責處理局部的事務，從而構成了Grid_P2P模型。

改進的Grid_P2P網絡模型分為三層，增加了Manage-Peer(簡寫為 MP)層，加強對 Super-Peer(簡寫為 SP)層的管理，即改進的Grid_P2P網絡模型分為三層：為MP層、SP層和普通節點Peer層，則相應的節點即為功能節點MP、超級節點SP和普通節點Peer。

假設整個網絡 G={MP1，MP2，…，MPL}，其中 MP1，MP2，…，MPL表示各個功能節點MP。

設 Mi={SPi1，SPi2，…，SPim}，其中 SPi1，SPi2，…，SPim表示該MP域內的超級節點SP。

設 Sj={Pj1，Pj2，…，Pjn}，則其中 Pj1，Pj2，…，Pjn表示該 SP域內的普通節點Peer。

下面對一些相關術語描述如下。

·普通節點P（Peer），即普通的P2P節點，既是資源的提供者，也是資源的消費者。如果能夠提供符合要求的計算及存儲資源，則同時將其注冊為網格節點。當P為SP時，它必須首先將自己的資源信息注冊到SP上．并定時向MP發送資源更新信息。

·超級節點SP，一組P2P節點的管理控制點，也是普通節點及網格節點，負責管理所在管理域的節點加入、離開、更新和消息路由。超級節點SP的作用是接收Peer或其他SP的請求并在必要時向MP節點或其他SP節點轉發，SP定時通知MP和其他SP自身資源信息的更新情況。超級節點代理普通節點進行資源搜索，并將結果返回給普通節點。超級節點有緩存機制，保存著最近通信過的節點的信息。

·功能節點MP是改進的管理節點，也可以叫做“管理節點的管理節點”。但是功能節點和管理節點的不同，主要在于：功能節點是被節點管理員設定為只存儲相應某一類服務信息的節點。例如，功能節點可以被設置成只存儲網格中應用軟件的信息，或者只存儲網格中數據資源的信息。換句話說，功能節點的功能類似于現在的水庫或者糧倉，它只能存儲有關“水”或者“糧”的信息。功能節點的定義和選取要求節點有非常高的計算性能和較高的存儲空間，同時也必須能夠相對穩定地存在網格中。若干個功能節點以全連接或者是其他方式形成一個在超級節點之上的第三層．也就是功能節點層。MP負責接收SP和其他MP轉發的請求信息和更新信息，在自身信息庫中進行查詢和更新。

·自治域。超級節點和它的子節點構成一個自治域，自治域可以是地理上相關的節點集合，也可以是有相同的資源共享機制的節點的集合。超級節點為自治域的核心。

3.2 模型結構

改進的Grid_P2P網絡模型如圖2所示，最上層為MP層，中間為Super-Peer層，下層為普通節點Peer層。其中Super-Peer的選取是基于地理位置，每個Super-Peer構成一個局部網格系統。Super-Peer與Super-Peer依次順序連接，形成一個環狀。按照地理位置臨近的程度依次選取一個或若干個Super-Peer使其從屬于一個MP，MP與MP之間也是依次順序連接，形成一個環狀。其中，地理位置臨近程度的選取依具體環境而定。

MP為網格構建過程中的中間節點，對SP進行管理。每個自治域中的SP與一個MP建立聯系。當一個區域中的SP想加入到網格系統中時，該自治域域中的SP與一個MP建立連接并注冊到MP，MP查詢發送請求的SP是否屬于臨近范圍之內，若屬于，則為請求加入的SP選擇一些已經在其上注冊的最臨近的SP，將這些最臨近的SP的地址發送給請求加入的SP，這些SP成為新加入的SP的鄰居節點。當MP節點發生故障時，SP節點依據地理位置的遠近請求加入到臨近的鄰居MP節點。

圖2 改進的Grid_P2P模型結構

3.3 節點的加入與離開

在網格系統中，資源節點的信息是動態變化的，節點可以動態地加入和離開網格系統。為了保證服務的可用性，在大規模的網格系統中進行有效任務調度時必須考慮節點的動態變化。本模型中需要考慮Super-Peer節點和下層普通Peer節點的加入和離開。

（1）SP層中節點的加入和離開

當SP要加入網格系統中時，首先要向MP層的MP節點注冊自己的信息，MP節點查看存儲已在其上注冊的SP的信息，為請求節點選擇最臨近的節點，將這些節點的地址信息返回給請求節點，使這些節點成為請求節點的鄰居節點。

SP要定期檢測其鄰居節點，當其檢測到與其連接的鄰居節點失去通信時，向MP點發出請求，MP為其指派新的鄰居節點來代替該故障節點。當SP離開網格系統時，須向其注冊的MP節點發送退出消息，MP節點刪除其注冊信息。

（2）下層普通節點的加入和離開

在Grid_P2P系統模型中，當普通節點P加入Grid_P2P系統中時，需要向SP點注冊其資源信息。當節點離開系統時，向SP點發送離開信息，SP刪除其注冊的資源信息即可。

在進行任務調度時，采用的是樹形的組織方式，所以當節點加入網絡系統中時，隨機地連接已存在的該自治域節點作為其子節點并在該節點上注冊自己的資源信息。當節點離開網格系統時，向其雙親節點發送離開信息，雙親節點刪除其注冊的資源信息 (包括該節點子樹的資源信息)，如果該節點有子節點，這些子節點選擇出新的節點與其雙親節點建立連接，并注冊其資源信息。

3.4 改進的模型中任務調度及負載平衡

Grid_P2P系統在處理任務時不同于單機。單機系統中計算資源有限，一般是任務等待少量的計算資源，需要調度的是任務；而在Grid_P2P系統中，資源數量非常多，經常會出現資源等待處理任務。另外Grid_P2P系統中的資源是動態變化的，隨著時間的推移，有舊資源退出和新資源加入。任務調度過程為：首先根據提交的任務屬性來決定選擇資源中的哪一類，然后在相應的信息資源管理器中查找初步滿意的資源集，同時，資源調度管理者還需檢查可用資源隊列中的資源。如果可用資源隊列中的具有最高優先級別的資源的優先級別超過了設定的范圍，則可以先選擇這個資源作為此次調度資源；否則，就等待計算從資源管理器中的所發現資源的優先級別。這兩項操作是同時進行的，可以減少資源的相對發現時間。然后，根據資源所在的位置、網絡流量、帶寬、資源的使用率、資源的計算能力等參數，決定資源調度的次序。

在向SP提交任務時，可能會遇到本地系統負載過重，而不能滿足用戶的QoS需求的情況。此時，該SP就要向其他的SP轉移一些任務，這種情況需要查找具有“最佳處理能力”的SP，并把任務遷移到具有“最佳處理能力”的SP，具體描述如下。

當某個P節點提交任務時，首先向其SP節點發出查詢信息，SP節點在自己的當前信息中查找，如果查找到符合條件的資源，則進行任務調度，將任務調度到符合條件的資源。

當P節點的負載過重時，則該P節點發送負載轉移請求給其SP節點，SP節點查找該SP域內的其他P節點的負載信息，并記錄當前負載最輕的P節點的信息。若存在滿足請求的P節點，則返回信息給發送請求的P節點，然后轉移負載給滿足請求的P節點；如果當前沒有符合條件的資源，則發送負載轉移請求給其相鄰的其他SP節點。

當SP節點收到其相鄰的SP節點發送來的請求后，該SP節點查找該SP域內是否有滿足請求的輕負載P節點，若存在，則記錄當前負載最輕的P節點的信息，然后返回信息給發送請求的SP節點；若不存在則繼續將負載轉移請求轉發給其相鄰的SP節點，SP進行任務調度，將任務調度到符合條件的資源。

假設改進的網格模型中有n個Super-Peer節點，即有n個超級節點，進一步假設每個Super-Peer具有m個普通Peer節點。在該網絡模型結構下，每個節點向Super-Peer節點提交任務。在最佳情況下，需求信息提交后，只遍歷一個Super-Peer且一次就能滿足用戶的需求，這種情況下最佳時間復雜度為O(1)。在最壞情況下，需要將網格中的所有Super-Peer都查找一遍，才能確定所需資源是否存在，因此在最壞情況下的時間復雜度為O(n×O(m))。

3.5 改進的模型的優勢

Grid_P2P網絡模型將P2P模型中超級節點的思想引入到網格系統，在網格的超級計算機和普通節點之間引入Super-Peer的概念，在Super-Peer與Super-Peer之間構成一個P2P的中間層。Super-Peer的選取可以基于地理位置或基于普通節點中某些高性能計算機，每個Super-Peer實際上是構造Grid_P2P系統的一個局部網格系統。這樣用戶提交的任務絕大多數情況下是提交給其所在的Super-Peer處理，從而大大縮短了通信距離，進一步縮小了通信延遲。局部網格的存在極大地改進了層次調度模型中的不足之處，從而縮短了資源的查找時間。Grid_P2P資源管理模型不需要使用一種新機制來改變新注冊的物理資源的物理網絡鏈接狀況來構造局部網格，局部網格系統根據地理位置的遠近及資源的類別來組織資源，對于地理位置較遠的資源建立其他的局部網格系統。需要注冊的資源只需要向信息接收器提交該資源的屬性信息即可。同時該系統具有良好的可擴充性，新的資源可方便地加入到超級Peer中，新的超級Peer也可方便地加入Grid_P2P系統中。Grid_P2P系統具有如下優點：各局部網格系統可使用不同的網格技術。超級Peer把資源分為三種形式來管理，縮小了資源查找范圍，可以減少資源的查找時間；局部網格系統中的資源一旦被使用后，系統記錄訪問時間和統計訪問的次數連同處理能力等參數信息均被保存到相應的可用資源管理器中，這些資源按照優先級確定其被調度的順序，相對于資源信息管理器中記錄的資源而言被優先調度。

Grid_P2P系統模型雖然具有以上的優點，但是Super-Peer節點的加入和離開將會對整個網格系統造成很大的影響，從而影響網格中的任務調度。改進的Grid_P2P系統模型增加了MP層，從而加強了對SP層的管理。MP為網格構建過程中的中間節點，對SP進行管理。每個自治域中的SP與一個MP建立聯系。當一個區域中的SP想加入到網格系統中時，該自治域中的SP與一個MP建立連接并注冊到MP，MP查詢發送請求的SP是否屬于臨近范圍之內，若屬于，則為請求加入的SP選擇一些已經在其上注冊的最臨近的SP，將這些最臨近的SP的地址發送給請求加入的SP，這些SP成為新加入的SP的鄰居節點。當MP節點發生故障時，SP節點依據地理位置的遠近請求加入到臨近的鄰居MP節點，從而減輕了Super-Peer節點的加入和離開對整個網格系統造成的影響。另外改進的Grid_P2P系統模型中的Super-Peer節點的選取依據地理位置，而且成環狀，這樣的組織可以極大地縮短通信距離，進一步縮小通信延遲，同時也便于網格的擴展。

4 結束語

本文提出了一種改進的Grid_P2P模型，并對該模型的結構進行了簡單介紹，給出了與該模型的相關定義，討論了該模型中節點的加入與離開過程。在改進的Grid_P2P模型上，闡述了任務調度過程和負載平衡過程，并分析了改進的Grid_P2P模型的優勢。本文提出的改進Grid_P2P模型是基于地理位置的臨近的，因此，需要對改進模型在空間上的限制進一步研究。

1 Yang B,Garcia-Molina H.Designing a super-peer network.In:19th International Conferenceon Data Engineering, IEEE Computer Society Press,Los Alamitos,CA,USA,2003

2 Mastroianno C,Talia D,Oreste Vetra.A super-peer model for resource discovery services in large-scale grids. Future Generation Computer Systems,2005(21):1235～1248

3 Holliday J,Dong-Sub C,Su-Hong Min.Optimal super-peer selection for large-scale P2P system.Hybrid Information Technology,International Conference on 2006,2(12):588～593

4 葉從歡，江武漢，孫世新.P2P與Grid的結合：P2P-Grid模型研究.微型機與應用，2005，24(5)

5 任長林，孟東升，阮秀琴.基于P2P技術的網格系統模型的設計與實現.計算機工程與設計,2007,28(8):1848～1851

6 Zhuang Yanyan,Liu Ye,Niu Lin.Construction of overlay network based on P2P technology in grid environment.Journal of Southeast University(English Edition),2007,23(1):57～62

7 楊長興，江海濤.基于P2P機制的網格資源發現的研究.計算機系統應用，2008(2):101～104