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

湯景云　張永平

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

關(guān)鍵詞：一跳復(fù)制； RA1算法；路由表

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：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 引言

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

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

首先對P2P網(wǎng)絡(luò)中的重要概念進(jìn)行定義：

P2P系統(tǒng)中的一臺主機(jī)稱為一個節(jié)點(diǎn)。如果兩個節(jié)點(diǎn)互知對方的IP地址，則稱在這兩個節(jié)點(diǎn)之間存在一個連接。延遲是指，一次通信過程中，消息從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)所經(jīng)過的連接數(shù)，用跳數(shù)(hop)來描述。為了實(shí)現(xiàn)P2P網(wǎng)絡(luò)，每個節(jié)點(diǎn)上需要保存一個與其有連接關(guān)系的節(jié)點(diǎn)的IP地址列表，稱為鄰居列表。同時，為了支持通信，每個節(jié)點(diǎn)還需要保存一個建立在IP地址列表基礎(chǔ)上的消息轉(zhuǎn)發(fā)目標(biāo)表，稱為路由表。

一個好的P2P路由算法必須具備如下幾個特點(diǎn)：

(1)高可擴(kuò)展性：每個節(jié)點(diǎn)的鄰居節(jié)點(diǎn)IP列表要小。

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

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

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

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

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

圖1 d=3 的超立方體

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

3 算法的改進(jìn)

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

現(xiàn)有模型是通過廣播方式完成搜索的。當(dāng)多個節(jié)點(diǎn)同時發(fā)送查詢請求和要求消息路由時，會導(dǎo)致傳輸效率變低，甚至使網(wǎng)絡(luò)不可用。要解決的問題是：搜索和路由時要盡可能減少消息的傳遞次數(shù)，平均消息延遲要小，即跳數(shù)要小。

3.1.1“一跳復(fù)制”策略描述

每個SN 動態(tài)地維護(hù)其NN所擁有數(shù)據(jù)的索引（包括NN本身以及所管理的ON的數(shù)據(jù)），通過這樣的索引可以提高查詢速度。因?yàn)槊總€數(shù)據(jù)的索引被“復(fù)制”到了離自己“一跳”的鄰居中，所以稱為“一跳復(fù)制”策略。如圖1，節(jié)點(diǎn)0存有節(jié)點(diǎn) 1、2、4 的數(shù)據(jù)索引，；同理，節(jié)點(diǎn)1、2、4 上也存有節(jié)點(diǎn)0的數(shù)據(jù)索引。

3.1.2 改進(jìn)前后效率對比

改進(jìn)后，通過“一跳復(fù)制”,節(jié)點(diǎn)0 要得到節(jié)點(diǎn)7 上的數(shù)據(jù)，搜索結(jié)果實(shí)際需要的查詢請求是9 條，經(jīng)過2 跳，同時將會得到6 條不同的搜索路徑。

而改進(jìn)前，不進(jìn)行“一跳復(fù)制”，節(jié)點(diǎn)0 則要經(jīng)過3 跳才能得到搜索結(jié)果，同時由于搜索是通過廣播來實(shí)現(xiàn)的，且消息在傳輸過程中的不同步性，這樣實(shí)際需要的查詢請求就是15 條，可以得到3 條不同的搜索路徑。

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

3.2 建立查詢路由表提高網(wǎng)絡(luò)效率

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

3.2.1 改進(jìn)的路由算法RA1

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

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

(2)查詢源節(jié)點(diǎn)的鄰居列表，統(tǒng)計鄰居節(jié)點(diǎn)(n 個)，生成n 張預(yù)備路由表。設(shè)置預(yù)備路由表的屬性：鄰居節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)，設(shè)置鄰居節(jié)點(diǎn)號為子查詢id 號。將預(yù)備路由表分別發(fā)送給相應(yīng)的鄰居節(jié)點(diǎn)。

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

(4)得到當(dāng)前節(jié)點(diǎn)的向前鄰居節(jié)點(diǎn)，分別對其提出查詢請求。若得到有效路由，則保存。更新預(yù)備路由表。

(5)檢查搜索的深度是否已經(jīng)達(dá)到了TTL 的限制。如果達(dá)到了TTL的限制則停止搜索，將得到的預(yù)備路由表中有效路由進(jìn)行反相路由，復(fù)制到源節(jié)點(diǎn)的路由表中。否則分別將鄰居節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，調(diào)用(4)過程，向深一層搜索。

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

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

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

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

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

3.2.2 算法說明

RA1算法說明：

(1)路徑優(yōu)先級確定機(jī)制

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

(1)每一個節(jié)點(diǎn)都認(rèn)為它的鄰居是優(yōu)先級最高的；

(2)在1）的基礎(chǔ)上再依據(jù)節(jié)點(diǎn)收到消息回應(yīng)的速度來確定優(yōu)先級。消息回應(yīng)速度快的路徑優(yōu)先級高，反之，消息回應(yīng)速度低的路徑優(yōu)先級低。

例如：節(jié)點(diǎn)0發(fā)出一個查詢請求，如果在節(jié)點(diǎn)2 和節(jié)點(diǎn)3上都有它所請求的資源，因?yàn)楣?jié)點(diǎn)2是節(jié)點(diǎn)0的鄰居，所以路由r=h( 0 , 2)的優(yōu)先級就比r=h (0,2 )+h( 2,3) 高，前一條路經(jīng)應(yīng)該被優(yōu)先選擇。如果是節(jié)點(diǎn)3和5上的資源，則依據(jù)消息查詢回應(yīng)的速度來決定。

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

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

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

(3)路由環(huán)路的問題

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

解決的方法：當(dāng)每一個查詢請求開始，分配一個唯一的查詢qid,每個節(jié)點(diǎn)檢查自己的預(yù)備路由表，是否已經(jīng)接收過此請求。接收請求的超級節(jié)點(diǎn)會自動檢查以前是否接收過此查詢qid，若接收過則拒絕請求。

(4)查詢率統(tǒng)計策略

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

3.2.3 改進(jìn)后算法分析

(1)通過改進(jìn)的RA1算法，節(jié)點(diǎn)在進(jìn)行資源查找的同時保存了路由信息，在確定資源所在位置的同時也確定了消息傳輸?shù)淖顑?yōu)路徑。而前者部分工作是路由器來承擔(dān)的，但是，基于HyperCube 模型的相對簡單的拓?fù)浣Y(jié)構(gòu)使人們可以將這部分工作放到每個節(jié)點(diǎn)上完成。這將大大提高網(wǎng)絡(luò)的效率，基本上可以節(jié)省消息路由的時間。

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

4 結(jié)束語

本文探討了基于HyperCube 模型的P2P路由算法，對原有的搜索和路由機(jī)制進(jìn)行了一些改進(jìn)和完善。這種設(shè)計的最大優(yōu)點(diǎn)在于提高了網(wǎng)絡(luò)的效率，利用“一跳復(fù)制”機(jī)制來解決網(wǎng)絡(luò)工作時大量消息傳輸對網(wǎng)絡(luò)帶寬的占用，同時在此基礎(chǔ)上的RA1算法增強(qiáng)了網(wǎng)絡(luò)的安全性和健壯性。

參考文獻(xiàn)：

[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的路由選擇技術(shù)的研究[Z].計算機(jī)工程,2006,03.

[4]楊斌,孟波.P2P經(jīng)典路由算法的改進(jìn)[Z].計算機(jī)工程與設(shè)計,2004,02.

[5]孫珊珊.P2P網(wǎng)絡(luò)路由算法的研究及Chord協(xié)議算法的改進(jìn)[D].工學(xué)碩士,吉林大學(xué),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-），女，江西高安人，中國礦業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院碩士研究生，研究方向：計算機(jī)網(wǎng)絡(luò)，信息安全；張永平（1958-），男，遼寧東溝人，中國礦業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院碩士生導(dǎo)師，副教授，研究方向：計算機(jī)網(wǎng)絡(luò)，信息安全。