基于Gnutella的P2P搜索改進(jìn)算法的研究

吳俊豐，王春枝

（湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢430068）

1 Gnutella協(xié)議

1.1 Gnutella網(wǎng)絡(luò)協(xié)議體系

在以Gnutella網(wǎng)絡(luò)為代表的分布式非結(jié)構(gòu)化對等網(wǎng)絡(luò)模型中，所有的客戶端也是一個(gè)服務(wù)器，同樣反之亦然，因此他們被稱為對等機(jī)（servent）.他們通過相互的連接遍歷整個(gè)網(wǎng)絡(luò).Gnutella協(xié)議定義了這些網(wǎng)絡(luò)中的對等機(jī)的通信方式.這些協(xié)議工作在位于TCP／IP層上的應(yīng)用層.該協(xié)議包括對等機(jī)間通信描述符集（服務(wù)原語集）和相應(yīng)的通信規(guī)則集.一臺新的對等機(jī)通過與當(dāng)前處于Gnutella網(wǎng)絡(luò)中的任何一臺活動對等機(jī)建立一個(gè)連接，從而加入Gnutella網(wǎng)絡(luò)［1］.

1.2 傳統(tǒng)Gnutella協(xié)議的查詢機(jī)制

傳統(tǒng)的Gnutella網(wǎng)絡(luò)采用flooding即洪泛式的查詢機(jī)制.在Gnutella網(wǎng)絡(luò)中存在4種信令消息，包括 PING，PONG，QUERY，QUERYHIT，PUSH消息.各個(gè)消息的說明見表1.

表1 Gnutella網(wǎng)絡(luò)中各種信息的說明

在Gnutella網(wǎng)絡(luò)中，當(dāng)一個(gè)節(jié)點(diǎn)需要查詢數(shù)據(jù)文件時(shí)，會采用泛洪式的查找查詢方式，即該節(jié)點(diǎn)先把查詢消息（Query）發(fā)送到自己的鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)首先查找自己的數(shù)據(jù)列表，如果發(fā)現(xiàn)要查詢的數(shù)據(jù)，就返回一條確認(rèn)消息（QueryHit），否則就把這條信息轉(zhuǎn)發(fā)給自己的直接鄰居.在轉(zhuǎn)發(fā)過程中，節(jié)點(diǎn)會檢查并修改Query消息頭的TTL字段，如果發(fā)現(xiàn)消息的TTL為0，則直接丟棄該消息.當(dāng)首先發(fā)起查詢的節(jié)點(diǎn)收到QueryHit消息后，就可直接與回復(fù)QueryHit消息的主機(jī)建立連接，下載所需的文件.對于在NAT或防火墻后的主機(jī)，可以采用“推送”的方式來下載數(shù)據(jù)文件，即查詢節(jié)點(diǎn)發(fā)送Push請求回復(fù)QueryHit消息的主機(jī)處，受到Push請求的主機(jī)需要主動建立到查詢節(jié)點(diǎn)的連接并將所需數(shù)據(jù)“推送”給查詢節(jié)點(diǎn).

上述查詢機(jī)制是有問題的.泛洪查詢將查詢信息以廣播方式對直接鄰居節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，當(dāng)網(wǎng)絡(luò)規(guī)模不大或是查詢范圍比較小時(shí)，這種泛洪的查詢方式有高度的容錯(cuò)性和查準(zhǔn)率.然而，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，查詢信息的轉(zhuǎn)發(fā)將是海量的.假設(shè)目前有個(gè)比較規(guī)則的網(wǎng)絡(luò)，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)平均有n個(gè)節(jié)點(diǎn)，查詢信息每進(jìn)行一次轉(zhuǎn)發(fā)需要轉(zhuǎn)發(fā)n條信息，隨著查詢范圍的擴(kuò)大（TTL值的增加），查詢消息將以指數(shù)級增長，冗余信息量也會急劇增加［2］.這些冗余信息會使得網(wǎng)絡(luò)流量急劇增加，網(wǎng)絡(luò)負(fù)擔(dān)加重，甚至?xí)斐删W(wǎng)絡(luò)擁塞.如何管理網(wǎng)絡(luò)連接，使用高效的資源定位算法，減少轉(zhuǎn)發(fā)的冗余查詢信息的數(shù)量，提高資源搜索的效率，并提高Gnutella網(wǎng)絡(luò)的擴(kuò)展性，對Gnutella網(wǎng)絡(luò)的發(fā)展極其重要.

2 基于資源推薦策略的路由算法與改進(jìn)

2.1 現(xiàn)有的基于資源推薦策略的路由算法

現(xiàn)有的資源推薦策略在返回查詢消息時(shí)緩存查詢信息來為后續(xù)的查詢作出指導(dǎo)［3－5］.這些緩存的查詢信息包括通過本節(jié)點(diǎn)成功到達(dá)具有請求資源的目標(biāo)節(jié)點(diǎn)的次數(shù)：從本節(jié)點(diǎn)到達(dá)具有請求資源的節(jié)點(diǎn)的最少跳數(shù)［6－8］.為了實(shí)現(xiàn)以上的2個(gè)功能，前人通過使用本地資源索引表（LIT）和本地路由索引表（RIT）來對節(jié)點(diǎn)的信息進(jìn)行管理.

表2 節(jié)點(diǎn)A的本地路由索引表（RIT）

表2中，行所表示的是查詢信息的關(guān)鍵字：列表示的是本節(jié)點(diǎn)A的鄰居節(jié)點(diǎn).Ki為節(jié)點(diǎn)A在過去一段時(shí)間內(nèi)所查詢的信息的關(guān)鍵字.其中（Ki，B）表示關(guān)鍵字為Ki的查詢信息通過B節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢成功的次數(shù)為mi.例如，（K1，B）為4表示關(guān)鍵字為K1的查詢信息通過B節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢成功的次數(shù)為4次.“通過B節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢成功”包含有2層含義：一是在B節(jié)點(diǎn)自身的本地資源索引表里找到；二是B節(jié)點(diǎn)也是查詢的中間節(jié)點(diǎn)，查詢信息通過B節(jié)點(diǎn)后將按照同樣的原理進(jìn)行轉(zhuǎn)發(fā).這個(gè)方法雖然能夠指導(dǎo)查詢消息向更加有效的鄰居節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，但當(dāng)查詢的TTL值低于到達(dá)具有請求資源的最近節(jié)點(diǎn)的TTL值時(shí)，查詢消息將不會到達(dá)資源節(jié)點(diǎn).

在傳統(tǒng)的路由索引機(jī)制中，還存在一個(gè)查詢準(zhǔn)確率的問題.查詢消息每經(jīng)過一個(gè)節(jié)點(diǎn)都會參考一次該節(jié)點(diǎn)的RIT，通過比對決定優(yōu)先向哪個(gè)直接的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢消息.事實(shí)上，通過該節(jié)點(diǎn)轉(zhuǎn)發(fā)查詢成功的次數(shù)多并不一定代表最短的查詢路徑一定通過該節(jié)點(diǎn).最糟糕的情況就是通過查詢成功次數(shù)最多的節(jié)點(diǎn)轉(zhuǎn)發(fā)所得到的查詢結(jié)果都是路徑最長、所需跳數(shù)最多的.

表3 路由緩存表

如表3所示，通過B節(jié)點(diǎn)查詢成功的次數(shù)最多，為4次，但通過B節(jié)點(diǎn)查詢成功的路徑最少也要4跳才能找到具有請求資源的節(jié)點(diǎn)G，而通過D節(jié)點(diǎn)查詢成功次數(shù)最少，但是通過D節(jié)點(diǎn)卻能最快找到最短路徑的具有請求資源的節(jié)點(diǎn)H.而且，每經(jīng)過這樣1次對鄰居節(jié)點(diǎn)的參考選擇，就可能有一些可靠的查詢路徑被輕視.查詢信息進(jìn)行路由選擇的次數(shù)越多，有效的查詢消息被忽略的可能就越大，選擇查詢所忽略的有效信息的百分比

公式中，n為節(jié)點(diǎn)的平均度數(shù)，k為在某一節(jié)點(diǎn)參考RIT進(jìn)行節(jié)點(diǎn)選擇的次數(shù)，i為查詢轉(zhuǎn)發(fā)的次數(shù)，t為查詢消息的生命周期值，每通過一次RIT查詢，就需要在n個(gè)節(jié)點(diǎn)里選擇一個(gè)節(jié)點(diǎn)，整個(gè)查詢就像是在一個(gè)完全k叉樹里進(jìn)行搜索.在最糟糕的情況下，可能要廣度優(yōu)先遍歷整個(gè)完全n叉樹，那樣會有很大的查詢延遲.最多的查詢次數(shù)

2.2 改進(jìn)后的基于路由索引機(jī)制算法

為了論述改進(jìn)的路由索引機(jī)制算法，先引述相似查詢的概念：兩個(gè)查詢消息所查詢的資源具有給定的相似度的查詢就是相似查詢［9］.筆者在總結(jié)原有路由索引機(jī)制算法和自身分析研究的基礎(chǔ)上，所做的改進(jìn)工作主要包括兩個(gè)方面.

1）在現(xiàn)有的基于緩存的節(jié)點(diǎn)推薦路由策略的基礎(chǔ)上加以改進(jìn).在表2中的通過鄰居節(jié)點(diǎn)成功查詢到關(guān)鍵字的次數(shù)對相似查詢確實(shí)具有一定的指導(dǎo)作用，但是，由于沒有記錄通過該鄰居節(jié)點(diǎn)到達(dá)資源節(jié)點(diǎn)的最少跳數(shù)，這樣，查詢信息有可能不能夠到達(dá)具有請求信息的資源節(jié)點(diǎn).為了記錄從該節(jié)點(diǎn)到達(dá)請求資源所在節(jié)點(diǎn)的最少跳數(shù)，本文引入了Hops項(xiàng).當(dāng)查詢信息的TTL值小于Hops時(shí)，該算法自動將此TTL值修改為與Hops等同的值然后進(jìn)行查詢，保證了查詢信息能夠到達(dá)推薦的資源節(jié)點(diǎn).

2）為了減少查詢信息的數(shù)量，本文引入了查詢路由表（RPT）來記錄資源查詢過程中返回的路由信息.當(dāng)查詢節(jié)點(diǎn)發(fā)出了Query消息后，如果被查詢節(jié)點(diǎn)里有所請求的資源，該節(jié)點(diǎn)將會沿查詢信息Query的路由原路返回一個(gè)QueryHit消息.這時(shí)，途經(jīng)的這些節(jié)點(diǎn)將會記錄下這些QueryHit中的返回資源的路徑和其他信息.并對某類相似查詢的路由進(jìn)行排名，存儲其中跳數(shù)較少的路由（本文推薦是前3條跳數(shù)最少的路由），以指導(dǎo)后續(xù)的相似或重復(fù)查詢，加快重復(fù)查詢的效率，減少冗余查詢信息，從而減少網(wǎng)絡(luò)流量，緩解網(wǎng)絡(luò)負(fù)擔(dān).改進(jìn)的路由見表4.

表4 資源推薦路由表

表4中，B，C，D為查詢消息所在節(jié)點(diǎn)A的直接鄰居節(jié)點(diǎn)，P1，P2，P3為通過鄰居節(jié)點(diǎn)返回路由信息中跳數(shù)最少的3條路由.查詢信息到達(dá)鄰居節(jié)點(diǎn)就將按推薦的路徑進(jìn)行.以對鄰居節(jié)點(diǎn)B路線上的查詢?yōu)槔?，依次首先令Hops＝2（即P1的跳數(shù)），逐個(gè)調(diào)整Hops值（對應(yīng)的是P2，P3的跳數(shù)），依次按照推薦路由進(jìn)行查詢.若指定資源的RPT表為空或通過所有推薦路由查詢均失敗，則繼續(xù)進(jìn)行迭代洪泛查詢，查詢的結(jié)果填充RPT表.以便為后續(xù)的相似查詢做出指導(dǎo).本文選擇對既定資源存儲最短三條路由信息有兩個(gè)目的，一是綜合考慮了查詢的查準(zhǔn)率，如果保留的路由信息過少，那么沿推薦路由查詢可能因P2P網(wǎng)絡(luò)中的節(jié)點(diǎn)隨時(shí)退出網(wǎng)絡(luò)或是出現(xiàn)其他異常而失?。旱?個(gè)原因是盡量減輕本地緩存的負(fù)擔(dān)，過多的路由信息對查詢的指導(dǎo)效率的提高意義不大，他們會使得節(jié)點(diǎn)緩存所占的存儲空間增大，存儲他們需要占用本節(jié)點(diǎn)的硬件資源.

本算法中的RPT將傳統(tǒng)算法的RIT吸納在其中，如果節(jié)點(diǎn)本身包含所查詢的資源，則從該節(jié)點(diǎn)到達(dá)請求資源所在節(jié)點(diǎn)的最小跳數(shù)為0，到達(dá)請求資源所在節(jié)點(diǎn)的路由就是節(jié)點(diǎn)本身.

2.3 改進(jìn)后算法描述

推薦路由查詢?nèi)植襟E描述如下：

1）從源節(jié)點(diǎn)開始進(jìn)行Ki記錄的探尋，若有Ki信息推薦路由，則沿推薦路由查詢，否則，進(jìn)行迭代洪泛查詢.

2）在迭代洪泛查詢的過程中，若查詢到請求資源，則查詢結(jié)束：如果查不成功，但是有Ki記錄返回，則停止迭代洪泛查詢，從開始沿推薦路由查詢.

3）若在進(jìn)行第1次迭代查詢后，既沒有查詢到請求資源也沒有Ki的緩存路由信息返回，則進(jìn)行下一次迭代查詢，查詢的處理轉(zhuǎn)向（2）.

推薦路由查詢局部過程的偽代碼說明如下：

Main（）＃主函數(shù)，輸入和輸出

｛Routing＿select（）；＃資源路由信息的查詢

Input Query（Ki，TTL）＃client C

Output Queryhit（Ki.IP，Ki＿Info）；｝＃sever S

查詢算法的輸入是 Query（Ki，TTL），Ki為查詢資源的關(guān)鍵字，TTL為查詢信息所余生命周期值，輸入節(jié)點(diǎn)是查詢的源節(jié)點(diǎn)或是轉(zhuǎn)發(fā)節(jié)點(diǎn)；算法的輸出是 Queryhit（Ki＿IP，Ki＿Info），Ki＿IP是查詢信息的IP地址，Ki＿Info是查詢所得資源的特征信息，輸出信息的節(jié)點(diǎn)是資源節(jié)點(diǎn).

Routing＿Select（）

｛if（Match＿Ki（）＝＝True）

｛if hop＝0Queryhit（）；＃請求資源位于本節(jié)點(diǎn)，返回 Queryhit

else if（TTL＜hop）TTL＝hop；

Routing＿Pi（）：＃路由的獲取

else Routing＿Pi（）：

｝｝

每當(dāng)查詢信息Query到達(dá)一個(gè)節(jié)點(diǎn)時(shí)，首先將自身與RPT表中的關(guān)鍵字Ki匹配，若存在Ki的記錄項(xiàng)，則進(jìn)一步查看到達(dá)資源節(jié)點(diǎn)的跳數(shù).若到達(dá)Ki資源的hop＝0，則說明資源存在于本節(jié)點(diǎn)；若Query消息不能到達(dá)資源節(jié)點(diǎn)，則將通往該資源節(jié)點(diǎn)的最短路徑的hop值賦予查詢信息的TTL，使Query能到達(dá)該資源節(jié)點(diǎn).需要說明的是，查詢信息將依次沿所有推薦路由查詢，不同路由中，TTL將會被賦予相應(yīng)的hop值

Routing＿Pi（） ＃從路由緩存記錄里獲得路由信息

｛for（i＝1，i＜n，i＋＋）Pi；＃沿所有推薦路由發(fā)送查詢消息

if（Pi＝S＿IP）QueryHit（）；＃查詢成功，返回 Queryhit（）

else Delete Ki＿RPT（）； ＃沿推薦路由查詢失敗，清空Ki的路由緩存記錄

Iterative＿Flooding（）；｝ ＃繼續(xù)進(jìn)行迭代泛洪查詢

使用Ki記錄的路由Pi，若查詢消息到達(dá)資源節(jié)點(diǎn)，結(jié)束；若通過緩存路由都沒能到達(dá)資源節(jié)點(diǎn)，則刪除Ki記錄，并使用泛洪查詢.

Upadte＿RPT（）；＃更新路由緩存信息

｛if（Match＿Ki（）＝＝False）Create＿Ki（）；＃創(chuàng)建 Ki的路由緩存

else Ki＿RPT（）；｝＃填充 Ki的路由信息

當(dāng)節(jié)點(diǎn)第1次參與查詢或通過所有緩存推薦的路由查詢失敗時(shí)，RPT表中關(guān)于查詢資源的記錄均為空值，這時(shí)將會繼續(xù)采用迭代洪泛的方法進(jìn)行查詢，并記錄查詢關(guān)鍵字為Ki.當(dāng)節(jié)點(diǎn)收到Ki消息的Queryhit信息而節(jié)點(diǎn)緩存里又沒有Ki的緩存路由時(shí)，則創(chuàng)建Ki的記錄項(xiàng)；若有Ki的記錄項(xiàng)而路由信息為空時(shí)則更新路由信息，用來指導(dǎo)后續(xù)相似查詢.

3 算法性能分析

為了分析改進(jìn)算法的性能，以下將在3個(gè)方面對改進(jìn)算法和現(xiàn)有算法進(jìn)行比較.

首先比較在最短路徑時(shí)的命中率.由于傳統(tǒng)的資源推薦策略只記錄通過該節(jié)點(diǎn)查詢某一資源成功的次數(shù)和所需的最小跳數(shù).而現(xiàn)有的基于緩存的路由指導(dǎo)機(jī)制通過存記錄的先前的成功查詢指定資源的路徑，所以在最短路徑的命中率方面效率明顯會更高.

接下來比較查詢命中率，傳統(tǒng)的資源推薦策略并不能保證在有推薦資源時(shí)請求節(jié)點(diǎn)的查詢能夠到達(dá)推薦策略的資源節(jié)點(diǎn).在已有確定資源的情況下，增加TTL值后僅僅對該資源進(jìn)行查詢，在保證所查詢資源節(jié)點(diǎn)可達(dá)的情況下還不會增加網(wǎng)絡(luò)負(fù)載.

最后比較網(wǎng)絡(luò)負(fù)載.在到達(dá)資源節(jié)點(diǎn)所需的路徑比較短時(shí)，兩種算法產(chǎn)生的網(wǎng)絡(luò)流量相當(dāng).但是隨著到達(dá)資源節(jié)點(diǎn)所需的路徑加長，由于基于緩存的路由推薦策略會針對確定的路徑進(jìn)行查詢，所以產(chǎn)生的網(wǎng)絡(luò)流量會比現(xiàn)有算法低.

4 結(jié)束語

本文對分布式非結(jié)構(gòu)化P2P網(wǎng)絡(luò)以及傳統(tǒng)Gnutella協(xié)議進(jìn)行了概要性闡述.在對現(xiàn)有的資源推薦策略的路由算法進(jìn)一步分析的基礎(chǔ)上，提出了改進(jìn)的基于緩存的路由搜索算法.該算法在能夠保證較高的查詢消息命中率的同時(shí)，通過路由緩存的策略來加速相似查詢和重復(fù)查詢，從而提高查詢效率，減輕網(wǎng)絡(luò)負(fù)載.通過性能分析，在原有的路由搜索算法的基礎(chǔ)上，改進(jìn)算法能夠改善提高查詢命中率和加速相似查詢和熱門資源查詢，從而使得整體的查詢效率有了改善.

［1］張春紅，裘曉峰，弭 偉，等.P2P技術(shù)全面解析［M］.北京：人民郵電出版社，2009：3－5.

［2］郭大江，陳閎中.Gnutella網(wǎng)絡(luò)搜索算法的改進(jìn)［J］.計(jì)算機(jī)工程與應(yīng)用，2005（36）：123－124.

［3］Gkantsidisc， Mihailm，Saberia.Hybrid search schemes for unstructured peer－to－peer networks［C］∥Proc of IEEE International Conference on Network Protocols.2005.

［4］湯景新，李景濤，趙一鳴.Gnutella半結(jié)構(gòu)化自適應(yīng)拓?fù)浞桨福跩］.計(jì)算機(jī)工程2009.9（17）：112－114.

［5］吳 綺.基于節(jié)點(diǎn)流行度的Gnutella路由查詢策略［J］.計(jì)算機(jī)與網(wǎng)絡(luò)，2009（2）：192－193.

［6］劉焱旺，楊小軍.一種基于Chord的緩存路由算法［J］.現(xiàn)代電子技術(shù)，2008（23）：133－138.

［7］董西廣，張治國，張文欣.Gnutella網(wǎng)絡(luò)中基于消息跳數(shù)的分段搜索策略［J］.河南工程學(xué)院學(xué)報(bào)，2011，6（2）：34－38.

［8］葉 飛，劉玉梅，馬偉華.基于DSR協(xié)議的緩存路由選擇與分組搶修算法［J］.應(yīng)用科技，2008，4（4）：61－64.

［9］熊忠陽，劉玉龍，張玉芳，等.基于Gnutella協(xié)議的P2P搜索改進(jìn)算法［J］.計(jì)算機(jī)應(yīng)用研究，2008（1）：108－110.