湯景云　張永平

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

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

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

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

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

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

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

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

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

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

(3)高可用性：每?jī)蓚€(gè)節(jié)點(diǎn)之間的不同通訊路徑要多。

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

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

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

圖1 d=3 的超立方體

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

3 算法的改進(jìn)

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

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

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

每個(gè)SN 動(dòng)態(tài)地維護(hù)其NN所擁有數(shù)據(jù)的索引（包括NN本身以及所管理的ON的數(shù)據(jù)），通過(guò)這樣的索引可以提高查詢速度。因?yàn)槊總€(gè)數(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)前后效率對(duì)比

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

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

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

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

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

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

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

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

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

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

(4)得到當(dāng)前節(jié)點(diǎn)的向前鄰居節(jié)點(diǎn)，分別對(duì)其提出查詢請(qǐng)求。若得到有效路由，則保存。更新預(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)過(guò)程，向深一層搜索。

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

例如，在上面的搜索過(guò)程中，0號(hào)超級(jí)節(jié)點(diǎn)發(fā)出搜索某資源請(qǐng)求， 算法生成3 張預(yù)備路由表： Table(0---1) ， Table(0---2)，Table(0---4)。其上沒(méi)有要求的資源，循環(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)過(guò)2 跳就得到了結(jié)果。得到以下關(guān)系：

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

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

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

3.2.2 算法說(shuō)明

RA1算法說(shuō)明：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

本文探討了基于HyperCube 模型的P2P路由算法，對(duì)原有的搜索和路由機(jī)制進(jìn)行了一些改進(jìn)和完善。這種設(shè)計(jì)的最大優(yōu)點(diǎn)在于提高了網(wǎng)絡(luò)的效率，利用“一跳復(fù)制”機(jī)制來(lái)解決網(wǎng)絡(luò)工作時(shí)大量消息傳輸對(duì)網(wǎng)絡(luò)帶寬的占用，同時(shí)在此基礎(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ì)算機(jī)工程,2006,03.

[4]楊斌,孟波.P2P經(jīng)典路由算法的改進(jìn)[Z].計(jì)算機(jī)工程與設(shè)計(jì),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

作者簡(jiǎn)介：湯景云（1984-），女，江西高安人，中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士研究生，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)，信息安全；張永平（1958-），男，遼寧東溝人，中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院碩士生導(dǎo)師，副教授，研究方向：計(jì)算機(jī)網(wǎng)絡(luò)，信息安全。