基于Pastry改進的P2P模型

吳仲華， 王貴竹

0 引言

有效的資源查詢是P2P應用所面臨的關鍵問題之一。非結構化的P2P基于泛洪搜索容易產生大量的查詢消息，可擴展性差。于是，提出了基于分布式哈希表DHT (Distributed Hash Table)的結構化P2P系統，比如Chord[1]、Pastry[2]、Tapestry[3]等。為了提高P2P網絡資源的查詢性能，研究人員提出了多種改進方案。如：非結構化和結構化相結合的圖像類似查詢方法[4]，基于興趣對節點分組和引導請求轉發的查詢方法[5]，基于節點共享文件形成語義組的查詢方法[6]。

由于Pastry利用了成熟的最大掩碼匹配算法，在實現時可以利用很多現成的軟件算法和硬件框架，可以獲得很好的效果。在Pastry的基礎上，文中提出一種更加有效的查詢方法，將Pastry擴展為主環和子環，主環由性能穩定的超級節點構成，子環由普通節點構成，它們由超級節點相互連接成覆蓋網。仿真結果表明改進后的模型路由性能優于Pastry，更好地適應動態的網絡環境。

1 系統模型

為了降低網絡中因為節點頻繁加入和退出而產生網絡的不穩定性，系統的網絡拓撲結構被設計為兩級。如圖1所示，系統分為主Pastry環和子Pastry環，主環由性能穩定的超級節點Si構成，子環由一個超級節點，一個副本節點和若干個普通節點構成。子環的劃分主要根據節點的物理位置關系，物理位置臨近的節點形成某個子環。其中Si代表超級節點, Ni代表普通節點，超級節點是主環和子環相連的橋梁。節點的加入和離開主要集中在各個子環，因而整個系統的穩定性有所提高。

圖1 系統模型

1.1 節點的加入

節點N根據地理位置臨近關系加入到某個子環內：

① N從bootstrap(所有節點都知道其地址)返回的幾個超級節點地址中隨機選取一個；

② 通過向這幾個超級節點分別發送Ping包，探測與它們之間的距離；

③ 從中選取距離最近的超級節點作為當前節點；

④ 如果當前超級節點有最小距離且小于預先設置的某一閾值，則N向當前節點發送加入請求；

⑤ 如果加入失敗，N探測與當前節點鄰居表中的節點距離，重復步驟③的操作，直到當前節點有最小距離；

⑥ 加入成功后，N獲取子環內部鄰居節點信息，轉移自己需要負責的關鍵字，同時分別在主環和子環上發布共享資源。

為了防止節點加入系統花費太多的時間，可以設置一個TTL值，當時間終止時，則節點自己成為超級節點，創建一個新環，當有其它節點加入后，再重新選取一個性能好的節點作為該環的超級節點。當超級節點變化時通知bootstrap。

1.2 節點的退出

當子環內某個節點退出系統時，進行如下操作：

① 向鄰居節點轉移自己負責存儲的關鍵字；

② 通知鄰居節點更新狀態表；

③ 保存子環內節點路由表信息，作為下一次加入系統時的導入節點。

為了防止節點短期加入和退出系統，造成關鍵字頻繁轉移而增加系統負擔，給每個新加入的節點設立一個時間閾值，只有達到這個時間閾值，才開始向該節點轉移資源。

當主環內某個超級節點退出系統時，進行如下操作：

① 通知副本節點，由副本節點代替超級節點的功能。然后再選擇一個節點作為副本節點，將超級節點的信息拷貝到該節點，更新supernode表；

② 通知鄰居節點更新鄰居表，通知bootstrap；

③ 當超級節點失效時，副本節點定期Ping所在子環的超級節點，如發現超級節點失效后會擔負起本子環內所有的通信任務，同時通知子環內所有節點，由副本節點代替失效的超級節點。

2 查詢機制

系統網絡路由分為兩級：主環路由和子環路由。主環路由是由超級節點完成，子環路由是由普通節點完成，節點要查詢資源首先在子環內進行，當子環內查詢失敗時，再在主環上進行搜索。節點N需要定位某個關鍵字時，具體的查詢過程如下：

① 查看本地鄰居表，如果有需要的內容，直接發送請求信息給鄰居節點。否則，轉向步驟②；

② 節點在子環內通過Pastry路由算法，查詢請求被路由到距離存儲該關鍵字最近的節點，如果查詢成功，返回結果，查詢過程結束。否則，轉入步驟③；

③ N向自己所在子環的超級節點發送查詢請求信息，通知其需要向外查詢；

④ 超級節點收到查詢請求后，查看自己的Cache表和鄰居表，如果存在則返回結果。否則，在主環中轉發查詢消息，被路由到距離存儲該關鍵字最近的超級節點；

⑤ 如果在主環上查詢成功，則返回一條應答消息給N所在子環的超級節點，此超級節點再轉發該消息給N，同時緩存查詢結果，便于子環內的其它節點查詢同樣的內容時，可以立即返回結果，而不用再到主環上查詢，從而提高了查詢效率；

⑥ 節點N與目標節點建立連接下載，查詢過程結束。

3 實驗仿真

仿真實驗采用BRITE[7]網絡拓撲生成器，BRITE生成的網絡結構與實際結構相似。仿真利用兩層分等級的拓撲結構，拓撲生成的方法是自底向上的。路由結構使用Waxman模式，設定標識符空間為 232大小，生成節點個數為 8192，每個節點隨機分配一個128位的標識符ID。隨機生成10000個查詢關鍵字的請求，發起查詢的節點也隨機地從 8192個節點中選取。仿真實驗比較了非結構化P2P網絡Gnutella和結構化的Pastry，以及本文所提出的系統模型。

圖3為三種查詢機制成功率隨時間變化情況，由圖可以看出本文的系統模型查詢成功率最高。主要原因是：本文機制分別在主環和子環上均發布資源，存儲資源的節點數相對增加，從而提高了查詢成功率；另外，超級節點緩存查詢結果也有利于查詢成功率的增加。

圖3 查詢成功率比較

下頁圖4顯示了在1 000秒內查詢平均延遲，從圖中可以看出，本文提出的系統模型查詢延遲最小。由于本文的系統模型采用了分等級結構，各個環內的節點數m明顯少于傳統Pastry環內的節點數N，因而減少了路由跳數（Pastry算法的平均路由跳數為LogBN，其中N為節點數），查詢延遲也隨著降低；系統緩存對減少查詢延遲也有較好作用，經過大量的查詢之后，能夠提供更多或更有效的快速連接，使得查詢延遲有所下將。

下頁圖 5顯示了查詢過程中產生的消息數隨時間變化的情況，由圖可以看出本文的系統模型產生的查詢消息數最少，因為各個環內的節點數m要遠少于傳統Pastry環內的節點數N，因而減少了查詢所產生的路由跳數，導致查詢的消息數量也隨之減少。系統緩存也有利于減少查詢消息的數量。

圖4 查詢延遲比較

圖5 查詢消息數比較

4 結語

通過對Pastry擴展為主環和子環，利用節點的地理位置鄰近性將節點劃分到相應的子環里，以確保網絡中鄰近節點間的路由盡量在子環里完成，從而降低查詢延遲；另外，節點的加入和離開主要限制在局部子環，有利于提高系統的穩定性，更好地適應動態的網絡環境。資源分別在主環和子環上發布，以及超級節點緩存查詢結果，實驗仿真結果表明這些都有利于提高系統查詢效率。

[1] Stoica I, Morris R. Chord： A Scalable Peer-to-peer Lookup Service for Internet Application [J]. IEEE/ACM Trans.2003,11(01)：17-32.

[2] Rowston A, Druschel P. Pastry： Scalable Distributed Object Location and Routing for Large-scale Peer-to-peer Systems[C].Heidelberg：[s.n.],2001：161-172.

[3] Zhao B Y. Tapestry： A Resilient Global-Scale Overlay for Service Deployment [J]. IEEE JSAC, 2004,22(01)：41-53.

[4] Muller W, Boykin P O, Roychowdhury V P, et al. Comparison of Image Similarity Queries in P2P Systems[J]. USA：IEEE,2006：98-105.

[5] Chen Wentsuen, Chao Chihong. An Interested-based Architecture for Peer-to-Peer Network Systems[C]. USA：IEEE,2006：707-712.

[6] Tao Gu, Hung Kengpung, Zhang Daqing. Information Retrieval in Schema-based P2P Systems Using One-dimensional Semantic Space[J]. Elserier North-Holland, 2007,51(16)：4543-4560.

[7] Brite. A Network Topology Generator Website[EB/OL].(2008-02-11)[2009-03-14] http：//www.CS.bu.edu/brite.