基于Ｈｙｐｅｒｃｕｂｅ模型的Ｐ２Ｐ路由算法的改進

湯景云　張永平

摘要：基于Hypercube模型的P2P資源搜索策略和路由策略，是以單純廣播方式進行的，搜索和路由效率比較低.因此提出了“一跳復制”技術以及改進算法RA1，提高了搜索和路由的效率，同時增強了P2P網絡的效率和健壯性。

關鍵詞：一跳復制； RA1算法；路由表

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)18-2pppp-0c

Improvement of P2P Routing Algorithm Based on Hypercube Model

TANG Jing-yun,ZHANG Yong-ping

(Department of Computer Science and Technology,China University of Mining and Technology,Xuzhou 221008,China)

Abstract:The P2P resource searching and routing strategy based on Hypercube Model depend the pure broadcast way,and are very inefficient.So, an "one-hop replication " technology and RA1 algorithmare adopt in this thesis which would enhance the efficiency of searching and routing, and also increase the efficiency and haleness of P2P-based network.

Key words:one-hop replication;RA1 algorithm;Table of routing

1 引言

對等網絡（P2P）技術是最近研究的熱點技術之一，它是分布式系統和計算機網絡相結合的產物。與傳統的基于C/S 方式的Internet相比，P2P采用一種既不排斥，也不固有的依賴中心控制節點的、基于網絡的計算方式，它最大的特點是網絡資源不再集中存放于服務器，而是分布于邊緣計算機中，具有較好的擴展性、容錯性、自主性。

在P2P網絡中，其基本問題就是網絡路由問題?，F有的P2P路由算法假設網絡中所有的節點的帶寬、存儲能力以及處理能力等屬性都是相等的。而實際的網絡中情況并非如此,P2P網絡存在著極大的節點異構性，用戶之間在帶寬、處理能力、存儲容量、NAT訪問方式等方面存在著很大的差異性。一部分節點擁有較強的處理能力和較大的帶寬，而部分節點的能力卻很有限。

首先對P2P網絡中的重要概念進行定義：

P2P系統中的一臺主機稱為一個節點。如果兩個節點互知對方的IP地址，則稱在這兩個節點之間存在一個連接。延遲是指，一次通信過程中，消息從源節點到目標節點所經過的連接數，用跳數(hop)來描述。為了實現P2P網絡，每個節點上需要保存一個與其有連接關系的節點的IP地址列表，稱為鄰居列表。同時，為了支持通信，每個節點還需要保存一個建立在IP地址列表基礎上的消息轉發目標表，稱為路由表。

一個好的P2P路由算法必須具備如下幾個特點：

(1)高可擴展性：每個節點的鄰居節點IP列表要小。

(2)高效：消息傳遞平均延遲要小。

(3)高可用性：每兩個節點之間的不同通訊路徑要多。

接下來介紹基于Hypercube 超立方體模型的路由算法以及改進算法。

2 基于Hypercube 超立方體模型的路由算法描述

基于Hypercube協議的P2P網絡將節點組織成確定、對稱的圖形拓撲結構。該協議根據篩選算法和域分組策略把加入網絡中的節點分成兩類：超級節點（SuperNode，SN）和普通節點(OrdianryNode,ON)；一個SN管理若干個ON。ON與SN通過星型拓撲連接起來。SN間則形成HyperCube超立方體結構。下面是一個維數d=3時的結構，如圖1所示。

圖1 d=3 的超立方體

該協議構造出的模型使每個SN都可以看成由所有SN組成的生成樹的根節點。由這個節點出發可以遍歷整個樹?？紤]到模型中SN的拓撲結構比較簡單，廣播方式可以高效率地完成查詢工作，所以Hypercube 模型的消息路由策略是利用單純廣播方式進行的。如節點0 要搜索資源，利用廣播的形式，把搜索請求發給它的所有鄰居節點（NeighborNode,NN）1、2、4。這些節點收到請求后首先查看本節點上否是有目標資源，如果有則發布回應；如果沒有則檢查TTL（Time To Live，生存時間），如果不超時，則繼續將請求發給自己的NN。

3 算法的改進

3.1 利用“一跳復制”策略提高消息路由效率

現有模型是通過廣播方式完成搜索的。當多個節點同時發送查詢請求和要求消息路由時，會導致傳輸效率變低，甚至使網絡不可用。要解決的問題是：搜索和路由時要盡可能減少消息的傳遞次數，平均消息延遲要小，即跳數要小。

3.1.1“一跳復制”策略描述

每個SN 動態地維護其NN所擁有數據的索引（包括NN本身以及所管理的ON的數據），通過這樣的索引可以提高查詢速度。因為每個數據的索引被“復制”到了離自己“一跳”的鄰居中，所以稱為“一跳復制”策略。如圖1，節點0存有節點 1、2、4 的數據索引，；同理，節點1、2、4 上也存有節點0的數據索引。

3.1.2 改進前后效率對比

改進后，通過“一跳復制”,節點0 要得到節點7 上的數據，搜索結果實際需要的查詢請求是9 條，經過2 跳，同時將會得到6 條不同的搜索路徑。

而改進前，不進行“一跳復制”，節點0 則要經過3 跳才能得到搜索結果，同時由于搜索是通過廣播來實現的，且消息在傳輸過程中的不同步性，這樣實際需要的查詢請求就是15 條，可以得到3 條不同的搜索路徑。

通過對比兩組數據可以得出，利用“一跳復制”策略可以很好地減少跳數從而縮短查詢時間,降低網絡負載量，有效地提高了網絡帶寬的利用率。

3.2 建立查詢路由表提高網絡效率

現有很多協議為了提高資源搜索的速度，在節點上建立了基于關鍵字或資源描述框架的語義索引。隨之而來的問題是怎樣快速而且準確地在源節點和目的節點之間進行消息傳輸。要求是：每兩個非直連節點間的可達通信路徑要多，同時保證這些是最優路徑。

3.2.1 改進的路由算法RA1

為了解決以上問題， 我們提出了改進的路由算法RA1。

(1)普通節點將搜索請求qid發送給自己的超級節點(源節點)，超級節點收到搜索請求，查詢本節點上是否存在請求的資源。由“一跳復制”策略可知，此超級節點上會存儲有本身和其鄰居節點的資源索引。所以此查詢可確定n＋1 個(n 是維數)超級節點上是否有請求資源。有則直接將有效路由加入路由表中。

(2)查詢源節點的鄰居列表，統計鄰居節點(n 個)，生成n 張預備路由表。設置預備路由表的屬性：鄰居節點為當前節點，設置鄰居節點號為子查詢id 號。將預備路由表分別發送給相應的鄰居節點。

(3)鄰居節點收到預備路由表后，按照表中資源請求搜索本節點。搜索范圍涉及到n個超級節點（本節點及n個鄰居節點，除去源節點）。若有請求資源，則將有效路由保存并計算查詢時間。檢查TTL，決定是否繼續向前搜索。

(4)得到當前節點的向前鄰居節點，分別對其提出查詢請求。若得到有效路由，則保存。更新預備路由表。

(5)檢查搜索的深度是否已經達到了TTL 的限制。如果達到了TTL的限制則停止搜索，將得到的預備路由表中有效路由進行反相路由，復制到源節點的路由表中。否則分別將鄰居節點作為當前節點，調用(4)過程，向深一層搜索。

(6)搜索完畢，刪除預備路由表。

例如，在上面的搜索過程中，0號超級節點發出搜索某資源請求， 算法生成3 張預備路由表： Table(0---1) ， Table(0---2)，Table(0---4)。其上沒有要求的資源，循環依次得到當前節點的鄰居，修改當前節點，并不斷更新預備路由表， 1---3，1---5；2---3，2---6；4---5，4---6；經過2 跳就得到了結果。得到以下關系：

r(s,d)=h (s,n) + rs(n,d)

其中：s 代表源節點，n 代表源節點的鄰居，也是第一個當前節點，d 代表目標節點，h (s,n)代表直連可得，rs (n,d)表示遞歸得到剩余的路徑信息。

如果搜索的資源就在鄰居上，則通過r=h (s,n) 能夠表示出這條路由是直連，否則通過得到鄰居節點作為當前節點遞歸調用生成算法。如上搜索過程可以得到路由消息索引為： r=h ( 0,1 )+( 1,3 )+(3,7 ) ；r=h (0,4 )+( 4,5 )+(5,7)等。

3.2.2 算法說明

RA1算法說明：

(1)路徑優先級確定機制

通過RA1算法生成查詢路由表，一般有多于一條的路由信息。那么這幾條路經的優先級如何來確定呢，本文提出了以下的優先級確定機制。

(1)每一個節點都認為它的鄰居是優先級最高的；

(2)在1）的基礎上再依據節點收到消息回應的速度來確定優先級。消息回應速度快的路徑優先級高，反之，消息回應速度低的路徑優先級低。

例如：節點0發出一個查詢請求，如果在節點2 和節點3上都有它所請求的資源，因為節點2是節點0的鄰居，所以路由r=h( 0 , 2)的優先級就比r=h (0,2 )+h( 2,3) 高，前一條路經應該被優先選擇。如果是節點3和5上的資源，則依據消息查詢回應的速度來決定。

根據以上的路徑優先級機制，搜索得到的有效路由就可以按照優先級的順序排列在查詢路由表中。

(2)搜索深度限制（TTL）

經過一次搜索能夠得到的有效路由的條數與搜索深度有關。RA1算法規定在搜索時，給定一個參數，由用戶來選擇搜索深度，模型中用TTL 進行度量。搜索深度越大，得到路由的數量也越大，但是需要更長的搜索時間。我們將指定一個默認值以滿足不同用戶的需要。

(3)路由環路的問題

該模型可能存在路由環路的問題。如7-3-2-6-7 就是一個路由回路，形成回路的原因是超級節點2只知道查詢請求是3 發出來的，并不知道6 是否已經接收過查詢請求，所以會將查詢請求發送給它，同樣6 也只知道是2 委托它查詢，同樣會將請求發送給7，這就形成了回路。

解決的方法：當每一個查詢請求開始，分配一個唯一的查詢qid,每個節點檢查自己的預備路由表，是否已經接收過此請求。接收請求的超級節點會自動檢查以前是否接收過此查詢qid，若接收過則拒絕請求。

(4)查詢率統計策略

每個節點的存儲空間有限。隨著時間的推移，節點維護的查詢路由表將會很大。在查詢時對重復查詢率進行統計，將那些經常用的查詢結果放在查詢路由表的開頭，這樣能夠提高查詢速度。同時限制查詢路由表的大小M，超過M時，自動從表最后一條記錄開始刪除。

3.2.3 改進后算法分析

(1)通過改進的RA1算法，節點在進行資源查找的同時保存了路由信息，在確定資源所在位置的同時也確定了消息傳輸的最優路徑。而前者部分工作是路由器來承擔的，但是，基于HyperCube 模型的相對簡單的拓撲結構使人們可以將這部分工作放到每個節點上完成。這將大大提高網絡的效率，基本上可以節省消息路由的時間。

(2) 通過RA1 算法生成的路由表建立了源節點與目標節點間的快速通道，同時保證兩個節點間有多條可達路徑，并且按照優先級排列，當一條或幾條路徑不可達時，仍然可以保證消息傳輸的可靠性。同時這幾條路由都是最優化的路由方式。相反的，如果沒有路由信息引導，則靠硬路由器，將帶來許多的重復工作，也不可能在短時間內保證有多條路徑供選擇。

4 結束語

本文探討了基于HyperCube 模型的P2P路由算法，對原有的搜索和路由機制進行了一些改進和完善。這種設計的最大優點在于提高了網絡的效率，利用“一跳復制”機制來解決網絡工作時大量消息傳輸對網絡帶寬的占用，同時在此基礎上的RA1算法增強了網絡的安全性和健壯性。

參考文獻：

[1]Schlosser M,Sintek M,Decker S.HyperCuP —— Hypercubes,Ontologies and Efficient Search on P2P Networks[Z].Computer Science Department,Stanford University,2002-07.

[2]Wolpers M, Siberski W, Schmitz C.Super-peer-based Routing Strategies for RDF-based Peer-to-peer Networks[Z].Germany Computation and Information Structures Institute,Technical University Berlin,Germany,2003.

[3]莊明,董健全.基于P2P的路由選擇技術的研究[Z].計算機工程,2006,03.

[4]楊斌,孟波.P2P經典路由算法的改進[Z].計算機工程與設計,2004,02.

[5]孫珊珊.P2P網絡路由算法的研究及Chord協議算法的改進[D].工學碩士,吉林大學,2007.

[6]McIlraith S,Son T C,Zeng H.Semantic Web Services[J].IEEE Intelligent Systems,2002,16(2 (Special Issue on the Semantic Web)):46-53.

收稿日期：2008-03-11

作者簡介：湯景云（1984-），女，江西高安人，中國礦業大學計算機科學與技術學院碩士研究生，研究方向：計算機網絡，信息安全；張永平（1958-），男，遼寧東溝人，中國礦業大學計算機科學與技術學院碩士生導師，副教授，研究方向：計算機網絡，信息安全。