吳俊豐，王春枝

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

1 Gnutella協(xié)議

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

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

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

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

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

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

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

2 基于資源推薦策略的路由算法與改進

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

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

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

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

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

表3 路由緩存表

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

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

2.2 改進后的基于路由索引機制算法

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

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

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

表4 資源推薦路由表

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

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

2.3 改進后算法描述

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

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

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

3）若在進行第1次迭代查詢后，既沒有查詢到請求資源也沒有Ki的緩存路由信息返回，則進行下一次迭代查詢，查詢的處理轉(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é)點是查詢的源節(jié)點或是轉(zhuǎn)發(fā)節(jié)點；算法的輸出是 Queryhit（Ki＿IP，Ki＿Info），Ki＿IP是查詢信息的IP地址，Ki＿Info是查詢所得資源的特征信息，輸出信息的節(jié)點是資源節(jié)點.

Routing＿Select（）

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

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

else if（TTL＜hop）TTL＝hop；

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

else Routing＿Pi（）：

｝｝

每當查詢信息Query到達一個節(jié)點時，首先將自身與RPT表中的關(guān)鍵字Ki匹配，若存在Ki的記錄項，則進一步查看到達資源節(jié)點的跳數(shù).若到達Ki資源的hop＝0，則說明資源存在于本節(jié)點；若Query消息不能到達資源節(jié)點，則將通往該資源節(jié)點的最短路徑的hop值賦予查詢信息的TTL，使Query能到達該資源節(jié)點.需要說明的是，查詢信息將依次沿所有推薦路由查詢，不同路由中，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ù)進行迭代泛洪查詢

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

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

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

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

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

3 算法性能分析

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

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

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

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

4 結(jié)束語

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

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

［2］郭大江，陳閎中.Gnutella網(wǎng)絡(luò)搜索算法的改進［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)拓撲方案［J］.計算機工程2009.9（17）：112－114.

［5］吳 綺.基于節(jié)點流行度的Gnutella路由查詢策略［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é)報，2011，6（2）：34－38.

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

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