基于Gnutella的P2P搜索改進算法的研究

吳俊豐，王春枝

（湖北工業大學計算機學院，湖北 武漢430068）

1 Gnutella協議

1.1 Gnutella網絡協議體系

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

1.2 傳統Gnutella協議的查詢機制

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

表1 Gnutella網絡中各種信息的說明

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

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

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

2.1 現有的基于資源推薦策略的路由算法

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

表2 節點A的本地路由索引表（RIT）

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

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

表3 路由緩存表

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

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

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

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

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

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

表4 資源推薦路由表

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

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

2.3 改進后算法描述

推薦路由查詢全局步驟描述如下：

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

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

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

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

Main（）＃主函數，輸入和輸出

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

Input Query（Ki，TTL）＃client C

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

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

Routing＿Select（）

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

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

else if（TTL＜hop）TTL＝hop；

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

else Routing＿Pi（）：

｝｝

每當查詢信息Query到達一個節點時，首先將自身與RPT表中的關鍵字Ki匹配，若存在Ki的記錄項，則進一步查看到達資源節點的跳數.若到達Ki資源的hop＝0，則說明資源存在于本節點；若Query消息不能到達資源節點，則將通往該資源節點的最短路徑的hop值賦予查詢信息的TTL，使Query能到達該資源節點.需要說明的是，查詢信息將依次沿所有推薦路由查詢，不同路由中，TTL將會被賦予相應的hop值

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

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

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

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

Iterative＿Flooding（）；｝ ＃繼續進行迭代泛洪查詢

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

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

｛if（Match＿Ki（）＝＝False）Create＿Ki（）；＃創建 Ki的路由緩存

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

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

3 算法性能分析

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

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

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

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

4 結束語

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

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

［2］郭大江，陳閎中.Gnutella網絡搜索算法的改進［J］.計算機工程與應用，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半結構化自適應拓撲方案［J］.計算機工程2009.9（17）：112－114.

［5］吳 綺.基于節點流行度的Gnutella路由查詢策略［J］.計算機與網絡，2009（2）：192－193.

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

［7］董西廣，張治國，張文欣.Gnutella網絡中基于消息跳數的分段搜索策略［J］.河南工程學院學報，2011，6（2）：34－38.

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

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