基于Gnutella的LRU查詢算法改進(jìn)

王春枝，孫 航，陳宏偉

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

近年來(lái)P2P已成為互聯(lián)網(wǎng)行業(yè)非常熱門的技術(shù)，它既可以極大緩解傳統(tǒng)集中式網(wǎng)絡(luò)架構(gòu)中服務(wù)器壓力過(guò)大、單點(diǎn)失效等問(wèn)題，又能夠利用終端的豐富資源，因此P2P技術(shù)廣泛應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)的各個(gè)領(lǐng)域［1］.經(jīng)過(guò)數(shù)十年的發(fā)展，P2P網(wǎng)絡(luò)已經(jīng)從第一代混合式P2P網(wǎng)絡(luò)體系發(fā)展到現(xiàn)今的純分布式P2P網(wǎng)絡(luò)體系［2］.混合式P2P網(wǎng)絡(luò)體系主要有集中式和層次式兩種，他們通過(guò)一些中心服務(wù)器來(lái)維護(hù)節(jié)點(diǎn)信息和數(shù)據(jù)信息.這樣容易產(chǎn)生單點(diǎn)容錯(cuò)和性能瓶頸等一些問(wèn)題.無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)［3］主要是基于消息泛洪的搜索機(jī)制［4］，通過(guò)節(jié)點(diǎn)之間消息的大量轉(zhuǎn)發(fā)實(shí)現(xiàn)查詢，從而導(dǎo)致其路由效率不高、可擴(kuò)展性不高、數(shù)據(jù)無(wú)法準(zhǔn)確定位等缺陷.純分布式無(wú)結(jié)構(gòu)網(wǎng)絡(luò)維護(hù)開(kāi)銷小，但會(huì)產(chǎn)生大量的消息轉(zhuǎn)發(fā)和冗余，給系統(tǒng)帶來(lái)巨大的開(kāi)銷，造成網(wǎng)絡(luò)流量負(fù)擔(dān).

1 常見(jiàn)的幾種無(wú)結(jié)構(gòu)化P2P查詢算法

1.1 泛洪算法（Flooding）

該算法的思想是，在網(wǎng)絡(luò)中節(jié)點(diǎn)相互之間都不知道其他節(jié)點(diǎn)的資源，當(dāng)節(jié)點(diǎn)需要搜索某個(gè)資源時(shí)，查詢節(jié)點(diǎn)向它的所有鄰居節(jié)點(diǎn)廣播查詢消息，為了限制搜索范圍，發(fā)起查詢請(qǐng)求的節(jié)點(diǎn)會(huì)在消息中設(shè)置一個(gè)初始的TTL值，消息每經(jīng)過(guò)一個(gè)節(jié)點(diǎn)TTL都會(huì)減1，直到TTL值為0停止搜索.

1.2 隨機(jī)漫步（Randon Walker）

該算法是在響應(yīng)時(shí)間和網(wǎng)絡(luò)負(fù)擔(dān)之間做了另一種權(quán)衡，Randon Walker方法針對(duì)泛洪算法的缺陷，嚴(yán)格控制每一步過(guò)程中擴(kuò)散查詢的力度Random Walker方法在每次傳遞查詢消息的時(shí)候，只把消息傳遞給隨機(jī)選擇的一部分鄰居節(jié)點(diǎn).

1.3 擴(kuò)展環(huán)法（Expanding Ring）

該算法是在初始階段給定TTL一個(gè)比較小的值，等待是否查詢到目標(biāo)資源.如果成功查詢到所需資源則結(jié)束查詢，否則增加TTL的值進(jìn)行新的查詢過(guò)程.

2 小世界網(wǎng)絡(luò)

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

分析圖1的網(wǎng)絡(luò)模型可以看到：在規(guī)則網(wǎng)絡(luò)中，兩個(gè)任意節(jié)點(diǎn)的連接都是既定的，而隨機(jī)網(wǎng)絡(luò)中的任意兩個(gè)節(jié)點(diǎn)是完全隨機(jī)連接的，這兩種網(wǎng)絡(luò)都不符合小世界現(xiàn)象.經(jīng)研究表明，Gnutella網(wǎng)絡(luò)符合小世界特征，因此在Gnutella網(wǎng)絡(luò)中存在大量的高連通節(jié)點(diǎn)，且部分節(jié)點(diǎn)間存在短鏈，也就是說(shuō)Gnutella是一種具有局部性的網(wǎng)絡(luò).針對(duì)無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)的缺點(diǎn)和Gnutella網(wǎng)絡(luò)符合小世界網(wǎng)絡(luò)模型的特點(diǎn)，本文提出一種基于LRU的查詢算法來(lái)提高無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)的查詢效率.

圖1 小世界網(wǎng)絡(luò)模型

3 基于LRU的路由學(xué)習(xí)查詢算法

3.1 LRU算法

LRU［5］是根據(jù)頁(yè)面調(diào)入內(nèi)存后使用情況來(lái)決策的一種算法.因?yàn)轫?yè)面的將來(lái)使用情況是無(wú)法預(yù)測(cè)的，而頁(yè)面已使用的情況是可以控制的.因此LRU替換算法設(shè)計(jì)中，假定一個(gè)最近被訪問(wèn)過(guò)的頁(yè)面，很可能在不久后又被訪問(wèn)，這明顯的是利用局部集的優(yōu)點(diǎn).設(shè)在t時(shí)刻頁(yè)面r的后面距離為BWDt（r），它是指頁(yè)面訪問(wèn)流中的同一頁(yè)從當(dāng)前點(diǎn)到以前一個(gè)訪問(wèn)點(diǎn)的距離.后方的距離總是大于0，如果沒(méi)有一條訪問(wèn)記錄，那它就是無(wú)限大.在LRU算法中，被替換的頁(yè)面是指有最大后方距離的記錄：

LRU算法實(shí)質(zhì)上是根據(jù)局部性原理，最近一段時(shí)間內(nèi)被訪問(wèn)的頁(yè)面，在將來(lái)的一段時(shí)間內(nèi)會(huì)被經(jīng)常訪問(wèn)，而把最近最長(zhǎng)一段時(shí)間內(nèi)沒(méi)有訪問(wèn)的頁(yè)面淘汰.

3.2 LRU路由查詢算法的思想

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

3.3 泛洪查詢模型

Gnutella協(xié)議是一種純分布式網(wǎng)絡(luò)協(xié)議，它使用的查詢算法是泛洪算法.當(dāng)網(wǎng)絡(luò)中的某個(gè)節(jié)點(diǎn)需要查詢資源時(shí)，該節(jié)點(diǎn)會(huì)向它的所有鄰居節(jié)點(diǎn)發(fā)送查詢信息.當(dāng)接受到查詢信息的節(jié)點(diǎn)包含所需資源時(shí)，就會(huì)發(fā)送一個(gè)查詢命中的消息沿查詢路徑返回；否則就向其鄰居節(jié)點(diǎn)繼續(xù)轉(zhuǎn)發(fā)查詢消息，以此類推，這個(gè)過(guò)程將不斷進(jìn)行下去.為了限制搜索的范圍，查詢消息會(huì)設(shè)置一個(gè)初始TTL值，消息每轉(zhuǎn)發(fā)一次TTL值就減一，直到TTL減為0或發(fā)現(xiàn)資源，搜索過(guò)程終止.

圖2 泛洪查詢模型

圖2 中，當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)A需要查詢資源S時(shí)，它向B、C和D等它的所有鄰居節(jié)點(diǎn)發(fā)送Query查詢信息.B、C和D等節(jié)點(diǎn)搜索本地資源列表發(fā)現(xiàn)沒(méi)有匹配資源，則繼續(xù)向它們的所有鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)Query消息，直到找到資源或者TTL減為0，則停止查詢.圖2中，節(jié)點(diǎn)C向它所有鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)Query消息，當(dāng)Query消息到達(dá)節(jié)點(diǎn)X時(shí)，找到匹配資源，節(jié)點(diǎn)X回復(fù)QueryHit消息，該消息沿Query消息路徑回到節(jié)點(diǎn)A.然后建立連接進(jìn)行資源下載.在這個(gè)查詢過(guò)程中，網(wǎng)絡(luò)的查詢消息成指數(shù)倍增加［9］.

3.4 改進(jìn)后的LRU查詢模型

本文提出的基于LRU的查詢算法是利用LRU的思想來(lái)維護(hù)節(jié)點(diǎn)存儲(chǔ)鄰居節(jié)點(diǎn)的容器SockMap＿t.當(dāng)需要查詢某資源的時(shí)候，首先向SockMap＿t容器中使用LRU維護(hù)的鄰居節(jié)點(diǎn)發(fā)送查詢消息，如果找到資源，則結(jié)束查詢（圖3）.

當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)A需要查詢資源S時(shí)，它向其部分鄰居節(jié)點(diǎn)B、C和D發(fā)送Query查詢信息.B、C和D節(jié)點(diǎn)搜索本地資源列表發(fā)現(xiàn)沒(méi)有匹配資源，則繼續(xù)向它們的部分鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)Query消息.這里所說(shuō)部分鄰居節(jié)點(diǎn)就是利用LRU思想更新，存儲(chǔ)在SockMap＿t里的前Length個(gè)節(jié)點(diǎn).若TTL減為0還是沒(méi)找到所需資源，那么就向SockMap＿t容器中Length長(zhǎng)度之后的鄰居節(jié)點(diǎn)發(fā)送查詢消息［10］（圖4）.

通過(guò)以上模型可以知道，基于LRU的查詢算法首先對(duì)節(jié)點(diǎn)容器Length長(zhǎng)度以內(nèi)的部分鄰居節(jié)點(diǎn)發(fā)送查詢消息，如果沒(méi)找到所需資源則向節(jié)點(diǎn)的其他鄰居節(jié)點(diǎn)發(fā)送查詢消息.因此可以在一定的查詢成功率的基礎(chǔ)上，提高熱門資源查詢的速度，減少網(wǎng)絡(luò)中查詢消息的轉(zhuǎn)發(fā)和冗余，在減小網(wǎng)絡(luò)開(kāi)銷的情況下，適應(yīng)較大的網(wǎng)絡(luò)規(guī)模和復(fù)雜的網(wǎng)絡(luò)環(huán)境.

4 網(wǎng)絡(luò)性能參數(shù)分析

4.1 時(shí)延抖動(dòng)

網(wǎng)絡(luò)的狀態(tài)是隨時(shí)變化的，網(wǎng)絡(luò)中的流量也是不穩(wěn)定的，當(dāng)流量較大的時(shí)候，許多數(shù)據(jù)分組就在節(jié)點(diǎn)的隊(duì)列中排隊(duì)，因此每個(gè)數(shù)據(jù)分組在傳輸中的時(shí)延并不一致.時(shí)延抖動(dòng)J（Jitter）描敘的是網(wǎng)絡(luò)傳輸時(shí)延的變化情況，時(shí)延抖動(dòng)越大，則表示網(wǎng)絡(luò)越不穩(wěn)定.本文將時(shí)延抖動(dòng)定義為以前后兩個(gè)不同分組數(shù)據(jù)之間的不同時(shí)延之差，即

4.2 吞吐量

網(wǎng)絡(luò)吞吐量（Throughput）是網(wǎng)絡(luò)性能的一個(gè)重要參數(shù)，是指沒(méi)有丟包的情況下單位時(shí)間內(nèi)節(jié)點(diǎn)接受的數(shù)據(jù)量.端到端的吞吐量與網(wǎng)絡(luò)狀況有很大的關(guān)系，如果網(wǎng)絡(luò)中的吞吐量過(guò)大，會(huì)導(dǎo)致網(wǎng)絡(luò)的擁塞、分片等一系列問(wèn)題.本文定義吞吐量為

式中，TB（i）是指到第i個(gè)分組被目的節(jié)點(diǎn)接受時(shí)，已經(jīng)傳輸?shù)臄?shù)據(jù)量；RT（i）則是第i個(gè)數(shù)據(jù)包接受的時(shí)間；i＞m，表示計(jì)算從第m個(gè)分組到第i個(gè)分組的吞吐量，當(dāng)且僅當(dāng)m＝1時(shí)，TH（i）m是平均吞吐量.

5 仿真實(shí)驗(yàn)

本實(shí)驗(yàn)從節(jié)點(diǎn)的數(shù)量和查詢消息數(shù)量的關(guān)系，以及網(wǎng)絡(luò)時(shí)延抖動(dòng)和吞吐量?jī)蓚€(gè)方面對(duì)提出的LRU的查詢算法和泛洪算法進(jìn)行比較.本實(shí)驗(yàn)在Linux Redhat操作系統(tǒng)中安裝NS－2仿真軟件，然后集成Gnutella協(xié)議，利用OTCL腳本編寫的代碼對(duì)實(shí)驗(yàn)進(jìn)行仿真，并對(duì)仿真實(shí)驗(yàn)所產(chǎn)生的實(shí)驗(yàn)trace文件數(shù)據(jù)利用gawk進(jìn)行分析和計(jì)算，最后使用gnuplot進(jìn)行畫(huà)圖，從而比較泛洪查詢和基于LRU的查詢的吞吐量和時(shí)延抖動(dòng).由圖5可以看到，使用了LRU查詢算法的Gnutella網(wǎng)絡(luò)中，網(wǎng)絡(luò)的吞吐量有明顯下降，事實(shí)上在基于LRU查詢算法的Gnutella網(wǎng)絡(luò)中，可以有效地控制泛濫的查詢消息的轉(zhuǎn)發(fā)，提高熱門資源的查詢效率以及降低消息的冗余度.圖6顯示了Gnutella網(wǎng)絡(luò)的時(shí)延抖動(dòng)，在使用泛洪搜索的Gnutella網(wǎng)絡(luò)中，因網(wǎng)絡(luò)查詢消息以指數(shù)倍增長(zhǎng)，使得網(wǎng)絡(luò)的某些時(shí)刻會(huì)產(chǎn)生很大的時(shí)延，從而網(wǎng)絡(luò)可能會(huì)出現(xiàn)斷鏈等不穩(wěn)定的現(xiàn)象，因而網(wǎng)絡(luò)中的延時(shí)抖動(dòng)幅度較大，并且不穩(wěn)定.而在采用LRU控制的Gnutella網(wǎng)絡(luò)中，因其吞吐量的減少，使得基于LRU查詢的Gnutella的網(wǎng)絡(luò)趨于一個(gè)比較小的穩(wěn)定的區(qū)間內(nèi).

6 結(jié)束語(yǔ)

本文針對(duì)無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)中Gnutella協(xié)議的泛洪查詢算法的查詢效率低和消息泛濫的問(wèn)題，提出了利用LRU的思想來(lái)更新存儲(chǔ)鄰居節(jié)點(diǎn)信息的SockMap＿t容器，可以使網(wǎng)絡(luò)中的查詢消息有效減少，同時(shí)可以改善熱門資源的查詢效率，并且網(wǎng)絡(luò)趨于一種比較穩(wěn)定的狀態(tài).

［1］楊 艦.對(duì)等網(wǎng)絡(luò)有效搜索機(jī)制研究［D］.上海：復(fù)旦大學(xué)圖書(shū)館.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］夏啟志，謝高崗，無(wú)結(jié)構(gòu)P2P網(wǎng)絡(luò)搜索方法及其改進(jìn)［J］.計(jì)算機(jī)應(yīng)用研究，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網(wǎng)絡(luò)的拓?fù)涮匦愿倪M(jìn)其可擴(kuò)展性［J］.計(jì)算機(jī)工程與應(yīng)用，2003，39（26）：58－60.

［9］楊東峰，莊 雷.基于稠密P2P網(wǎng)絡(luò)搜索機(jī)制的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2006，42（24）：111－114.

［10］莊 雷，董西廣，常玉存.非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中基于連接度的分段搜索策略［J］.計(jì)算機(jī)應(yīng)用，2008，28（3）：549－552.