基于Gnutella的LRU查詢算法改進

王春枝，孫 航，陳宏偉

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

近年來P2P已成為互聯網行業非常熱門的技術，它既可以極大緩解傳統集中式網絡架構中服務器壓力過大、單點失效等問題，又能夠利用終端的豐富資源，因此P2P技術廣泛應用于計算機網絡的各個領域［1］.經過數十年的發展，P2P網絡已經從第一代混合式P2P網絡體系發展到現今的純分布式P2P網絡體系［2］.混合式P2P網絡體系主要有集中式和層次式兩種，他們通過一些中心服務器來維護節點信息和數據信息.這樣容易產生單點容錯和性能瓶頸等一些問題.無結構P2P網絡［3］主要是基于消息泛洪的搜索機制［4］，通過節點之間消息的大量轉發實現查詢，從而導致其路由效率不高、可擴展性不高、數據無法準確定位等缺陷.純分布式無結構網絡維護開銷小，但會產生大量的消息轉發和冗余，給系統帶來巨大的開銷，造成網絡流量負擔.

1 常見的幾種無結構化P2P查詢算法

1.1 泛洪算法（Flooding）

該算法的思想是，在網絡中節點相互之間都不知道其他節點的資源，當節點需要搜索某個資源時，查詢節點向它的所有鄰居節點廣播查詢消息，為了限制搜索范圍，發起查詢請求的節點會在消息中設置一個初始的TTL值，消息每經過一個節點TTL都會減1，直到TTL值為0停止搜索.

1.2 隨機漫步（Randon Walker）

該算法是在響應時間和網絡負擔之間做了另一種權衡，Randon Walker方法針對泛洪算法的缺陷，嚴格控制每一步過程中擴散查詢的力度Random Walker方法在每次傳遞查詢消息的時候，只把消息傳遞給隨機選擇的一部分鄰居節點.

1.3 擴展環法（Expanding Ring）

該算法是在初始階段給定TTL一個比較小的值，等待是否查詢到目標資源.如果成功查詢到所需資源則結束查詢，否則增加TTL的值進行新的查詢過程.

2 小世界網絡

小世界網絡模型的聚類系數C（g）和特征路徑長度L（g）的特性都可以看成是重連概率P的函數.規則網絡的P＝0，是一個高度聚類，特征路徑長度大的網絡模型，隨著P趨向1時（0＜P≤1），重連得到的網絡與原始規則網絡的局部屬性只有較小的改變，因此網絡的聚類系數的變化也不大，但是重連網絡的特征路徑長度卻有大幅的下降.這種有較高的聚類系數特征路徑又較短的網絡就是小世界網絡，它是一種介于隨機網絡和規則網絡之間的網絡.小世界網絡模型如圖1所示.

分析圖1的網絡模型可以看到：在規則網絡中，兩個任意節點的連接都是既定的，而隨機網絡中的任意兩個節點是完全隨機連接的，這兩種網絡都不符合小世界現象.經研究表明，Gnutella網絡符合小世界特征，因此在Gnutella網絡中存在大量的高連通節點，且部分節點間存在短鏈，也就是說Gnutella是一種具有局部性的網絡.針對無結構P2P網絡的缺點和Gnutella網絡符合小世界網絡模型的特點，本文提出一種基于LRU的查詢算法來提高無結構P2P網絡的查詢效率.

圖1 小世界網絡模型

3 基于LRU的路由學習查詢算法

3.1 LRU算法

LRU［5］是根據頁面調入內存后使用情況來決策的一種算法.因為頁面的將來使用情況是無法預測的，而頁面已使用的情況是可以控制的.因此LRU替換算法設計中，假定一個最近被訪問過的頁面，很可能在不久后又被訪問，這明顯的是利用局部集的優點.設在t時刻頁面r的后面距離為BWDt（r），它是指頁面訪問流中的同一頁從當前點到以前一個訪問點的距離.后方的距離總是大于0，如果沒有一條訪問記錄，那它就是無限大.在LRU算法中，被替換的頁面是指有最大后方距離的記錄：

LRU算法實質上是根據局部性原理，最近一段時間內被訪問的頁面，在將來的一段時間內會被經常訪問，而把最近最長一段時間內沒有訪問的頁面淘汰.

3.2 LRU路由查詢算法的思想

本算法是根據Gnutella網絡［6］符合小世界網絡的特性，利用LRU的思想來更新節點存儲鄰居節點的 SockMap＿t容器的前 Length個元素［7］.SockMap＿t容器使用的是＜NodeAddr＿t，SockEntry＞的鍵值對來存儲鄰居節點.SockEntry類的對象就是鄰居節點對應的信息，為該類添加一個時間變量time，用來控制LRU的替換.初始情況下time賦值為0，當節點與其他節點（設該節點為A）發生查詢關系時，首先判斷容器里是否有相等節點，若有相等節點，則把容器里A節點的time賦0值，然后把容器內所有鄰居節點的time加1；若沒有相等節點，則把容器內time值最大的鄰居節點用節點A替換，同時所有節點time加1.如果在前Length個元素中沒有找到所需資源，那么就向SockMap＿t容器的Length長度后面的鄰居節點發送查詢信息，直到找到資源或者TTL減至0為止，結束整個查詢過程.

3.3 泛洪查詢模型

Gnutella協議是一種純分布式網絡協議，它使用的查詢算法是泛洪算法.當網絡中的某個節點需要查詢資源時，該節點會向它的所有鄰居節點發送查詢信息.當接受到查詢信息的節點包含所需資源時，就會發送一個查詢命中的消息沿查詢路徑返回；否則就向其鄰居節點繼續轉發查詢消息，以此類推，這個過程將不斷進行下去.為了限制搜索的范圍，查詢消息會設置一個初始TTL值，消息每轉發一次TTL值就減一，直到TTL減為0或發現資源，搜索過程終止.

圖2 泛洪查詢模型

圖2 中，當網絡中節點A需要查詢資源S時，它向B、C和D等它的所有鄰居節點發送Query查詢信息.B、C和D等節點搜索本地資源列表發現沒有匹配資源，則繼續向它們的所有鄰居節點轉發Query消息，直到找到資源或者TTL減為0，則停止查詢.圖2中，節點C向它所有鄰居節點轉發Query消息，當Query消息到達節點X時，找到匹配資源，節點X回復QueryHit消息，該消息沿Query消息路徑回到節點A.然后建立連接進行資源下載.在這個查詢過程中，網絡的查詢消息成指數倍增加［9］.

3.4 改進后的LRU查詢模型

本文提出的基于LRU的查詢算法是利用LRU的思想來維護節點存儲鄰居節點的容器SockMap＿t.當需要查詢某資源的時候，首先向SockMap＿t容器中使用LRU維護的鄰居節點發送查詢消息，如果找到資源，則結束查詢（圖3）.

當網絡中節點A需要查詢資源S時，它向其部分鄰居節點B、C和D發送Query查詢信息.B、C和D節點搜索本地資源列表發現沒有匹配資源，則繼續向它們的部分鄰居節點轉發Query消息.這里所說部分鄰居節點就是利用LRU思想更新，存儲在SockMap＿t里的前Length個節點.若TTL減為0還是沒找到所需資源，那么就向SockMap＿t容器中Length長度之后的鄰居節點發送查詢消息［10］（圖4）.

通過以上模型可以知道，基于LRU的查詢算法首先對節點容器Length長度以內的部分鄰居節點發送查詢消息，如果沒找到所需資源則向節點的其他鄰居節點發送查詢消息.因此可以在一定的查詢成功率的基礎上，提高熱門資源查詢的速度，減少網絡中查詢消息的轉發和冗余，在減小網絡開銷的情況下，適應較大的網絡規模和復雜的網絡環境.

4 網絡性能參數分析

4.1 時延抖動

網絡的狀態是隨時變化的，網絡中的流量也是不穩定的，當流量較大的時候，許多數據分組就在節點的隊列中排隊，因此每個數據分組在傳輸中的時延并不一致.時延抖動J（Jitter）描敘的是網絡傳輸時延的變化情況，時延抖動越大，則表示網絡越不穩定.本文將時延抖動定義為以前后兩個不同分組數據之間的不同時延之差，即

4.2 吞吐量

網絡吞吐量（Throughput）是網絡性能的一個重要參數，是指沒有丟包的情況下單位時間內節點接受的數據量.端到端的吞吐量與網絡狀況有很大的關系，如果網絡中的吞吐量過大，會導致網絡的擁塞、分片等一系列問題.本文定義吞吐量為

式中，TB（i）是指到第i個分組被目的節點接受時，已經傳輸的數據量；RT（i）則是第i個數據包接受的時間；i＞m，表示計算從第m個分組到第i個分組的吞吐量，當且僅當m＝1時，TH（i）m是平均吞吐量.

5 仿真實驗

本實驗從節點的數量和查詢消息數量的關系，以及網絡時延抖動和吞吐量兩個方面對提出的LRU的查詢算法和泛洪算法進行比較.本實驗在Linux Redhat操作系統中安裝NS－2仿真軟件，然后集成Gnutella協議，利用OTCL腳本編寫的代碼對實驗進行仿真，并對仿真實驗所產生的實驗trace文件數據利用gawk進行分析和計算，最后使用gnuplot進行畫圖，從而比較泛洪查詢和基于LRU的查詢的吞吐量和時延抖動.由圖5可以看到，使用了LRU查詢算法的Gnutella網絡中，網絡的吞吐量有明顯下降，事實上在基于LRU查詢算法的Gnutella網絡中，可以有效地控制泛濫的查詢消息的轉發，提高熱門資源的查詢效率以及降低消息的冗余度.圖6顯示了Gnutella網絡的時延抖動，在使用泛洪搜索的Gnutella網絡中，因網絡查詢消息以指數倍增長，使得網絡的某些時刻會產生很大的時延，從而網絡可能會出現斷鏈等不穩定的現象，因而網絡中的延時抖動幅度較大，并且不穩定.而在采用LRU控制的Gnutella網絡中，因其吞吐量的減少，使得基于LRU查詢的Gnutella的網絡趨于一個比較小的穩定的區間內.

6 結束語

本文針對無結構P2P網絡中Gnutella協議的泛洪查詢算法的查詢效率低和消息泛濫的問題，提出了利用LRU的思想來更新存儲鄰居節點信息的SockMap＿t容器，可以使網絡中的查詢消息有效減少，同時可以改善熱門資源的查詢效率，并且網絡趨于一種比較穩定的狀態.

［1］楊 艦.對等網絡有效搜索機制研究［D］.上海：復旦大學圖書館.2004.

［2］Yang B，Garcia－Molina H.Improving search in peerto－peer networks［J］.In Proceedings of 22nd Int’l Conference，2002，3（9）：5－15.

［3］Liu Y，Xiao L，Liu X.Location awareness in unstructured peer－to－peer system［J］.IEEE Transaction on Parallel and Distributed Systems，2005，16（2）：163－174.

［4］Hongbo Jiang，Shudong jin exploiting dynamic querying like flooding techniques in unstructured peer－topeer networks［C］.Washington DC，USA：IEEE Computer Society，IEEE Computer Society.Proceedings of the 13TH IEEE International Conference on Network Protocols 2005：122－131.

［5］Song Jiang，Lei Guo，Xiaodong Zhang，et al.Light－Flood：Minimizing redundant messages and maximizing scope of peer－to－peer search［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19（5）：601－614.

［6］夏啟志，謝高崗，無結構P2P網絡搜索方法及其改進［J］.計算機應用研究，2005，22（9）：256－260.

［7］Vana Kalogeraki Dimitrios Gunopulos D.Zeinalipour－Yazti.A local search mechanism for peer－to－peer networks CIKM 02［C］.Virginia，USA：Mclean，2002.

［8］黃道穎，劉 剛.利用Gntella網絡的拓撲特性改進其可擴展性［J］.計算機工程與應用，2003，39（26）：58－60.

［9］楊東峰，莊 雷.基于稠密P2P網絡搜索機制的研究［J］.計算機工程與應用，2006，42（24）：111－114.

［10］莊 雷，董西廣，常玉存.非結構化P2P網絡中基于連接度的分段搜索策略［J］.計算機應用，2008，28（3）：549－552.