基于Ｇｎｕｔｅｌｌａ協議的Ｐ２Ｐ搜索改進算法
2008-01-01 00:00:00熊忠陽劉玉龍張玉芳劉君
計算機應用研究 2008年1期
摘要：在分析了前人提出的基于索引機制的路由算法的基礎上，對該算法進行改進，彌補了原算法在指引查詢時不能保證查詢消息可達性的缺點。采用緩存查詢返回消息的策略來提高重復查詢的效率，從而提高了搜索的效率和效果。
關鍵詞：對等網;非結構化;Gnutella
中圖分類號：TP391; TP301．6文獻標志碼：A
文章編號：1001－3695(2008)01－0108－03
1Gnutella協議
1．1Gnutella 網絡協議體系
在Gnutella分布式對等網絡模型中，每一個聯網計算機既是客戶機同時又是服務器，因此被稱為對等機（servent）[1]。它通過與相鄰對等機之間的連接遍歷整個網絡。Gnutella協議定義了網絡中這些對等機間通信的方式，是工作于TCP協議之上的應用層協議。該協議包括對等機間通信描述符集（服務原語集）和相應的通信規則集。一臺新對等機通過與當前處于Gnutella網絡中的另一臺活動對等機建立一個連接，從而將自己連入Gnutella網絡。
1．2傳統Gnutella協議的查詢機制
傳統的Gnutella網絡采用洪泛式（flooding）的查詢機制[2]。Gnutella網絡的查詢機制總結如下:
a)Gnutella 網絡上的任一臺主機在需要查詢資源時，先根據查詢的內容形成一條查詢消息（query消息）。
b)查詢源主機將該query消息發送給網絡上與其直接相連的其他主機。
c)收到query消息的主機搜索自身的資源。如果有與查詢消息相匹配的資源，則形成一個queryHit消息，按照query消息來時的路徑發送給源查詢主機；如果沒有，則不發送。
d)收到query消息的主機將該消息轉發至除發送消息的主機以外的其他主機。
e)重復步驟c)d)。
舉例說明，如圖1所示。當Gnutella網絡中某一主機節點A想要查詢abc.doc資源時，首先生成查詢消息query（abc.doc）。節點A會將該查詢請求發送至與它直接相連的主機B、C、D。主機B、C、D收到該查詢后，檢查到自己沒有符合該查詢的資源則再將該查詢消息轉發給主機E、F。主機E、F收到該查詢消息后，E主機檢查到自己有符合該查詢所需的資源，則形成一個queryHit消息，按（E、C、A）的路徑返回給主機A；然后再將查詢消息query（abc.doc）轉發至除C以外的其他鄰居節點，達到繼續搜索資源的目的。
Gnutella傳統的查詢機制是存在問題的。由于其采用洪泛機制傳遞消息，隨著網絡規模擴大，流量急劇增加，導致網絡擁塞。根據Clip2 公司最近的研究顯示，56 kbps modem 用戶最多處理查詢消息20個/s。當網絡節點大于1 000 時，處理極限被突破。隨著這部分節點失效，Gnutella 網絡被分片，使查詢訪問只能在網絡很小一部分進行，導致網絡可擴展性下降。
如何管理網絡連接，實施高效的搜索算法，減少冗余消息，提高搜索的查準率，解決Gnutella 網絡的可擴展性，對Gnutella網絡的進一步發展至關重要。
2基于索引機制的路由算法及其改進
2．1傳統索引機制路由算法
傳統算法使節點在傳播查詢消息期間積累經驗來為以后傳播查詢提供指導。其經驗值[3~6]主要包括：通過此節點成功到達的資源的次數；資源到此節點為止所經過的路徑節點，用來指導下次查詢。
為了實現以上功能，引入本地資源索引表（LIT）和路由索引表(RIT)對節點進行管理。圖2所示的網絡拓撲圖對應的路由索引表如表1所示。
表1中，行表示關鍵字；列表示節點A的鄰居節點。Ki為節點A過去一段時間內所查詢的關鍵字。其中(Ki，B)的值為m1，表示通過節點B成功查詢到Ki的次數為m1。例如(K1，B)的值為4，表示通過節點B成功查詢到K1的次數為4。這里“通過節點B成功查詢到K”有兩種情況：一是節點B本身是查詢的目標節點；二是節點B是查詢的中間節點。此方法雖然能夠指導查詢消息向更加有效的鄰居節點進行轉發，但當查詢消息的TTL值低于該路徑到達資源節點的TTL值時，查詢消息將不能到達資源節點。
2．2改進后的路由索引機制算法
為了方便說明，給出相似查詢的定義，即兩個查詢消息所要請求的資源相似。這樣的查詢為相似查詢。
本文在上述工作的基礎上，所做的改進工作主要包括兩個方面：
a）在傳統算法提出的路由索引表的基礎上進行改進。由于原表僅記錄了通過鄰居節點成功查詢到關鍵字的次數，沒有記錄通過該鄰居節點到達資源節點最小的距離，查詢消息很可能到達不了資源節點，從而導致查詢失敗。為了解決原表不能保證查詢目標可達性的缺點，在表中引入最小跳數hop，從而保證查詢起碼能夠達到最近的資源目標節點。
b）為了減少相似查詢造成的網絡流量，引入返回路徑表（RPT），對queryHit消息的返回路徑進行記錄，并對該消息內容進行緩存，用來指引直接回應相似查詢。同時對RIT表的相關選項(通過該節點成功查詢的次數、最小跳數)進行更新，不斷學習，更好地指引下一次查詢。
改進后節點A的RIT表如表2所示。其增加了hop字段，用于記錄節點A通過鄰居節點（B，C，D）到達資源目的節點的最小跳數。
表2中，Ki為節點A過去一段時間內所查詢的關鍵字。其中(Ki，B)的值為(m1，m2)，表示通過節點B成功查詢到Ki的次數為m1，能達到該資源的最小跳數為m2。例如(K1，B)的值為4/4，表示通過節點B成功查詢到K1的次數為4，最小需要4跳能到達該資源節點。在此表的指引下，查詢消息就能按照最節省跳數，也是最準確的節點轉發，最終找到所要查詢的資源節點。當消息到達此節點的TTL值小于該節點距資源的最小跳數時，將對TTL進行重新賦值，從而保證一條查詢消息能最大限度地返回查詢結果，彌補了改進前方法的缺陷。
RPT表的設計如表3所示。
表3中，Ki為資源標志符；min hop表示此節點距該條路徑到達該資源的最小跳數；peer list 表示到達此資源的路徑列表，即queryHit消息的返回路徑列表。由于queryHit消息是按query消息的原路徑返回告知查詢源節點資源所在，則查詢源節點直接與之建立連接下載資源。
如圖2和表3所示。當查詢資源K1的消息到達節點A時，A檢索自己的RPT表，發現自己能到達K1的所在節點，依次經過節點B和D，所以節點A不會再將該條查詢消息向鄰居節點B轉發，而是直接回應一個queryHit消息給查詢源節點；同時更新節點A的RIT表，使A通過節點B成功查詢關鍵字K1的次數加1，并更新最小跳數。回應的消息攜帶了能夠到達該資源的足夠信息。這樣通過緩存queryHit消息，為相似的查詢提供指引，從而減輕了網絡負載，節省了查詢時間，提高了查詢效率。
2．3改進后算法描述
對改進算法的說明如下：
Routing select
Input query Q， client C
Output query answers，query forwards
算法輸入的參數是查詢Q和Q的源節點C，輸出的是查詢結果和查詢傳播的路由節點。其中：LIT是本地資源列表；RIT為路由索引表；RPT為返回路徑表。
函數match用于查詢LIT表或RIT表中的項是否與Q匹配；集合routeSelectNode用于記錄查詢投遞的節點；函數TTL用于比較當前查詢的TTL值和當前節點到達資源所在節點的最小跳數之比；函數updateTTL更新查詢消息Q的TTL值；函數RPTmatch用來在本地的RPT表中查找該資源標志符，找到其最近的目的節點，將緩存內容回復給查詢源節點C；函數updateSuccess用來更新RIT表中該節點通過特定節點找到最近資源的成功查找次數。
當查詢消息Q到達時，無論Q來自節點自身還是其他節點，算法都要運行，以便返回結果給Q的源節點C。
a）For match (Q，LIT. keys[i])
b）Send local answers for Q to C
c）If StopCondition () return
d）RouteSelectNode =
當節點收到查詢，首先查詢本地資源。如果有符合要求的資源，則將此結果發送給查詢源節點C，然后查找RIT表。
e）For match (Q， RIT. Key[i])
f）If max(Q，N)
g）IF RPTmatch（Q，RPT.Keys）
h）Send answers For Q to C
i）UpdateSuccess(RIT，Q)
j）ELSE routeSelectNode.Add(N)
如果在RIT表中有符合條件的記錄，則取幾條成功次數較多的記錄，對這些記錄首先查找RPT表。如果存在該節點到達具有該資源節點的記錄，將該結果直接返回給查詢源節點。如果在RPT表中不存在相關記錄，則將該RIT記錄涉及的節點存入routeSelectNode記錄集，等待投遞。
k）For each node in RouteSelectNode
l）IF TTL(Node.TTL，QNode.TTL)
m）UpdateTTL(Node，QNode)
判斷到達routeSelectNode集合中節點所需要的最小跳數。當查詢消息Q到達這些節點的最小跳數大于Q的TTL值時，更新Q的TTL值，從而增大Q到達目標節點的可能性，提高系統查準率。
n）RouteSelectNode.Add(randomNode())
最后隨機再選擇一部分節點來轉發查詢消息。這樣做是為了避免查詢集中在少數節點，從而造成系統熱點；同時也是為了發現新的資源節點。
o）Send Q to routeSelectNode
將查詢消息路由到選擇的節點。
p）If stopCondition() return
……
當節點第一次參與查詢時，RIT和RPT表為空。這時將采用隨機漫步[4]的方法向該節點的鄰居節點轉發查詢，并記錄查詢關鍵字Ki。將通過各鄰居節點成功查詢的次數初始化為0，最小跳數初始化為一個較大的數值。之后對RPT和RIT表不斷進行豐富。如果查詢成功，則更新RIT和RPT表。通過不斷更新，慢慢完善該表，即可用來指導以后的查詢。
3實驗數據分析
為了驗證改進算法的有效性，使用NS2建立了仿真環境，對原始算法和改進后的算法進行比較。
實驗首先比較兩種算法運行返回的結果數和網絡流量的關系。結果如圖3所示。其中：橫坐標（R）表示返回的結果數；縱坐標（F）表示產生的網絡流量，單位為KB。從圖3中可看出，隨著返回的結果數增多，改進后算法的網絡流量明顯少于改進前的算法。
其次，比較了TTL值與查找成功率的關系，結果如圖4所示。其中：橫坐標為TTL值；縱坐標為查找成功率。可以看出，當TTL值較小時，改進后的算法明顯優于改進前的算法。這主要是由于算法在得知查詢消息的TTL值小于到達資源的最小跳數時會更新TTL值，從而保證在TTL值較小時，仍然能保證查詢消息的命中率。
最后比較了隨著查詢時間的增長，返回結果數的變化，如圖5所示。隨著時間的增長，改進前算法的查詢結果數增長基本停止；而改進后的算法隨著查詢時間的增長。返回結果仍在增長。這是因為改進后的算法能夠保證查詢消息的可達性。
4結束語
本文對非結構化P2P系統進行了介紹，對Gnutella協議進行了研究。在對前人提出的路由搜索算法進行透徹分析的基礎上，提出了改進的路由搜索算法。該算法在克服了原算法不能保證查詢消息召回率的缺點的同時，引入了緩存返回消息的思想，用來指導相似查詢，從而節省了相似查詢的時間，減少了網絡流量。仿真實驗表明，改進算法在查詢召回率和查詢結果返回速度上得到了改善。
參考文獻：
[1]The Gnutella protocol specification v0.4[EB/OL].[2006－09－09].http://www.securitytechnet.com/resource/hot topic/p2p/gnutellaprotocol04.pdf.
[2]JIANG H，JIN S D.Exploiting dynamic querying like flooding techniques in unstructurted peer to peer networks[C]//Proc of the 13th IEEE International Conference on Network Protocols(ICNP’05).2005.
[3]YANG B，GARCIA MOLINA H. Efficient search in peer to peer networks[C]//Proc ofICDCS’02.Vienna:[s.n.]，2002.
[4]GKANTSIDIS C，MIHAIL M，SABERI A.Random walks in peer to peer networks[C]//Proc of IEEE International Conference on Network Protocols.2004.
[5]GKANTSIDIS C，MIHAIL M，SABERI A.Hybrid search schemes for unstructured peer to peer networks[C]//Proc of IEEE International Conference on Network Protocols.2005.
[6]PMARKATOS E.Tracing a larger scale peer to peer system:an hour in the life of Gnutella[C]//Proc of the 2nd IEEE/ACM Interational Symposiumon Cluster Computing and the Grid.2002.
［7］羅杰文.Peer to peer綜述[EB/OL].[2006－09－09].http://www.intsci.ac.cn/users/luojw/papers/p2p.htm.
[8]SIAKC N.Peer clustering and firework query model[C]//Proc of the 11th World Wide Web Conference.2002.
[9]KWOK S H，CHAN K Y.An enhanced Gnutella P2P protocol[C]//Proc ofthe 18th International Conference on Advanced Information Networking and Application(AINA’04).2004.
“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
