基于反饋的Ｐ２Ｐ資源定位策略

摘要：提出了一種非結(jié)構(gòu)化P2P網(wǎng)絡(luò)資源定位的新方法，包括基于反饋的查詢轉(zhuǎn)發(fā)策略和擴散控制算法。基于反饋的查詢轉(zhuǎn)發(fā)策略利用已執(zhí)行查詢的反饋進行信息搜索，同時通過在高轉(zhuǎn)發(fā)成功率的節(jié)點上復(fù)制副本來提高搜索命中率；擴散控制算法對消息數(shù)量進行控制，使得網(wǎng)絡(luò)帶寬不被過度消耗，減輕網(wǎng)絡(luò)擁塞。實驗采用Java語言模擬整個策略。結(jié)果表明該方法具有高效性、可靠性，值得在目前的P2P網(wǎng)絡(luò)中推廣。

關(guān)鍵詞：對等網(wǎng)絡(luò)； 資源定位； 信息搜索； 復(fù)制

中圖分類號：TP393文獻標(biāo)志碼：A

文章編號：1001-3695(2007)12-0345-03

0引言

P2P對等網(wǎng)絡(luò)是一種與傳統(tǒng)C/S模式不同的新型網(wǎng)絡(luò)。該網(wǎng)絡(luò)中每個節(jié)點地位對等，既充當(dāng)服務(wù)器，為其他節(jié)點提供服務(wù)；同時也為客戶機，享用其他節(jié)點提供的服務(wù)。P2P技術(shù)使任意兩臺相連接的計算機直接共享文檔、多媒體和其他各種類型的文件成為可能。利用P2P技術(shù)，計算機之間可以進行直接交互，而不需要使用任何一臺中央服務(wù)器。由于大部分處理直接在節(jié)點之間進行，減少了對服務(wù)器的依賴，具有很好的可擴展性。目前，P2P技術(shù)已經(jīng)應(yīng)用于很多領(lǐng)域，如文件共享、即時通信、協(xié)同工作、分布式計算、電子商務(wù)、網(wǎng)絡(luò)游戲以及信息檢索等方面。其中網(wǎng)絡(luò)文件共享應(yīng)用最為廣泛。

P2P網(wǎng)絡(luò)從結(jié)構(gòu)上分為無結(jié)構(gòu)化P2P和結(jié)構(gòu)化P2P。結(jié)構(gòu)化P2P資源定位快，但需要以很高的代價維護既定拓撲，不能很好地適應(yīng)高度動態(tài)的P2P環(huán)境。無結(jié)構(gòu)化P2P資源的查找和定位通過擴散來實現(xiàn)，搜索數(shù)據(jù)幾乎是隨機搜索，容易造成網(wǎng)絡(luò)流量急劇增加，導(dǎo)致網(wǎng)絡(luò)擁塞。因此，無結(jié)構(gòu)化P2P的一個核心問題就是如何進行快速搜索，同時降低網(wǎng)絡(luò)帶寬消耗，保證系統(tǒng)可擴展性和容錯性。本文主要討論無結(jié)構(gòu)P2P網(wǎng)絡(luò)環(huán)境下的搜索策略。

1現(xiàn)有搜索策略分析

現(xiàn)有的搜索策略主要可分為兩大類，即盲目搜索和信息搜索。盲目搜索策略中，查詢消息通常以廣播(flooding)或者隨機選取部分鄰居節(jié)點進行轉(zhuǎn)發(fā)的方式來進行搜索。 盲目搜索算法簡單，但通常會消耗大量網(wǎng)絡(luò)帶寬。為此提出了許多算法，以彌補廣播算法的缺點。最典型的是在random walks算法中設(shè)置k個walker，利用walker在網(wǎng)絡(luò)中漫游遍歷而不是擴散查詢消息來減弱消息擴散，但同時搜索時間大大增加。文獻[1]提出在高帶寬節(jié)點上復(fù)制其他數(shù)個節(jié)點存儲的數(shù)據(jù)索引信息，通過擴大節(jié)點回答查詢的能力以減少搜索需要訪問的節(jié)點數(shù)目，從而減少系統(tǒng)平均搜索長度，但同時容易造成單點過載。

與盲目搜索不同，信息搜索通常利用一些已有信息來輔助查找，依據(jù)自身已有鄰居節(jié)點信息和資源信息，有區(qū)別地選擇鄰居節(jié)點進行轉(zhuǎn)發(fā)，提高發(fā)現(xiàn)資源的效率。文獻[2]提出了APS算法。該算法根據(jù)節(jié)點有效轉(zhuǎn)發(fā)查詢的次數(shù)賦予節(jié)點相應(yīng)權(quán)值，并依據(jù)該值來選擇轉(zhuǎn)發(fā)節(jié)點。文獻[3]指出APS算法的缺陷：不能適應(yīng)熱點變化；不適合于資源訪問頻率不均的大規(guī)模P2P系統(tǒng)，并提出一種基于歷史信息的查詢轉(zhuǎn)發(fā)策略，以歷史命中率作為路由依據(jù)，并通過自適應(yīng)動態(tài)緩存和索引機制來提高搜索性能。

本文繼續(xù)沿著信息搜索的思路，綜合考慮各方面性能提出了一種改進方案。改進方案由兩部分組成，即基于反饋的查詢消息轉(zhuǎn)發(fā)策略和擴散控制算法。

2基于反饋的查詢消息轉(zhuǎn)發(fā)策略

由前面分析可知，以往搜索通常從單方面對搜索算法進行優(yōu)化。一種是從搜索方入手，即合理選擇查詢轉(zhuǎn)發(fā)節(jié)點；另一種則從被搜索方入手，通過復(fù)制來增加被搜索資源的數(shù)量，從而減少系統(tǒng)平均搜索長度。由簡單的挖隧道原理可知，從隧道的兩端同時開工要比只從一端開工快得多。首先，路徑減半，時間相應(yīng)減半；其次，從兩端開工方向更明確，更不容易走彎路。同理，P2P網(wǎng)絡(luò)中，若從兩端著手，擴散的消息數(shù)會由于路徑縮短而減少，從而降低網(wǎng)絡(luò)開銷；副本的存在，也有利于解決路由熱點問題。

2．1模型假設(shè)

為了控制擴散，發(fā)送的查詢消息采用的結(jié)構(gòu)如表1所示。

2．2基于反饋的查詢消息轉(zhuǎn)發(fā)策略

每個節(jié)點保存以下幾個集合：

a）Neigh(i)，記錄節(jié)點i的鄰居節(jié)點集合，包括到各鄰居節(jié)點的延遲。

b)（FName，TID），資源信息對集合，記錄當(dāng)前一段時間內(nèi)搜索成功的資源以及資源所在節(jié)點信息。TID表示資源所在地址。

c)（SID，MID），查詢信息對集合，記錄當(dāng)前一段時間內(nèi)已接收到的搜索消息。

2．2．1基于反饋的查詢消息轉(zhuǎn)發(fā)策略

文獻[4]指出，實際網(wǎng)絡(luò)呈現(xiàn)冪規(guī)律分布，網(wǎng)絡(luò)中有少數(shù)節(jié)點有較高的度，多數(shù)節(jié)點的度較低。度較高的節(jié)點與其他節(jié)點的聯(lián)系比較多，通過它找到待查信息的概率較高。為此，基于反饋的查詢消息轉(zhuǎn)發(fā)策略在random walks算法的基礎(chǔ)上進行了改進，利用已執(zhí)行查詢的反饋信息進行搜索；同時在高轉(zhuǎn)發(fā)成功率的節(jié)點上復(fù)制副本來提高搜索命中率，進而縮短系統(tǒng)平均搜索長度。基于反饋的查詢消息轉(zhuǎn)發(fā)策略描述如下：

a)對于任一原節(jié)點i，以i為中心節(jié)點，Neigh(i)為選取對象，計算到各鄰居節(jié)點延遲，按延遲從小到大排列得到新的鄰居節(jié)點集合。將延遲作為節(jié)點權(quán)值初值。規(guī)定權(quán)值越小，節(jié)點性能越優(yōu)。

b)根據(jù)網(wǎng)絡(luò)規(guī)模，從Neigh(i)集合中權(quán)值最小的節(jié)點開始選取K個進行轉(zhuǎn)發(fā)。

c)轉(zhuǎn)發(fā)消息，同時修改節(jié)點權(quán)值。每成功轉(zhuǎn)發(fā)一個節(jié)點，就將該節(jié)點權(quán)值遞加一個Δ值。若該條路徑查詢成功，沿原路返回將Δ值遞加回來，同時將（FName，TID）資源信息對復(fù)制保存在沿途經(jīng)過的節(jié)點上。查詢不成功的節(jié)點不予修改。

d）按節(jié)點權(quán)值重新從小到大排列鄰居節(jié)點集。這樣，搜索成功的節(jié)點權(quán)值不變，不成功的節(jié)點權(quán)值變大，在Neigh(i)集合中的位置后移，被選取轉(zhuǎn)發(fā)的概率降低，性能變差。

e）當(dāng)再次發(fā)起查詢，轉(zhuǎn)發(fā)到一個節(jié)點時，首先判斷以前是否查詢過此資源。如果有，則直接利用記載的資源信息對，轉(zhuǎn)發(fā)給目的節(jié)點；否則轉(zhuǎn)發(fā)消息，同時修改節(jié)點權(quán)值。

f）定期更新鄰居節(jié)點表。使用最近最少使用（LRU）算法定期更新信息對。每個節(jié)點最多保持M個信息對。

算法如下：

(a)初始化，計算到各鄰居節(jié)點的延遲，按延遲大小排序（小→大）;

(b)選取K個節(jié)點進行轉(zhuǎn)發(fā)，K由網(wǎng)絡(luò)規(guī)模決定，i∈Neigh(i);

for(i=1; i<=K; i++)

if (exist1=1‖exist2=1)

//判斷是否有所需資源信息對或資源

轉(zhuǎn)c)；

else{value+=data；轉(zhuǎn)b)；}

//無，則修改節(jié)點權(quán)值，轉(zhuǎn)發(fā)到鄰居節(jié)點，遞歸判斷

(c)查找成功，判斷是命中資源還是資源信息對;

if exist1=1 //命中資源對，將value值修改回來，不復(fù)制

{N∈SuccedPath value-=data;}

else //命中資源，將value值修改回來，同時復(fù)制信息對

{N∈SuccedPath value-=data; 復(fù)制信息對;}

(d)定期更新鄰居節(jié)點表，采用最近最少使用算法（LRU）定期更新信息對。

2．2．2轉(zhuǎn)發(fā)策略優(yōu)化

上述策略使延遲小、搜索成功的節(jié)點權(quán)值在執(zhí)行查詢過程中越變越優(yōu)，但同時引發(fā)一個問題：假設(shè)經(jīng)過節(jié)點A成功查詢的次數(shù)很多，那么A的節(jié)點權(quán)值相對較優(yōu)，轉(zhuǎn)發(fā)時選擇A的概率很高；當(dāng)轉(zhuǎn)發(fā)給A的查詢消息數(shù)目達到一定程度時，就會造成網(wǎng)絡(luò)擁塞，A點將成為熱點。為了防止擁塞，解決熱點問題，本文進一步提出了基于消息號、TTL和TS的擴散控制算法，利用消息號、TTL和TS同時對查詢消息進行控制，減少搜索產(chǎn)生的消息數(shù)目。擴散控制算法如下：

節(jié)點擁有自己獨立的消息號，每發(fā)送一個新消息，就給該消息分配一個消息號；消息號在每次發(fā)送新消息時加1。接收消息節(jié)點記下一段時間T內(nèi)它所接收的所有查詢信息對（SID，MID）。當(dāng)一個新消息到達時，它先檢查消息是否已經(jīng)收到過。首先比較源節(jié)點SID。如果是新SID，則是新消息，先在本地查看是否有目標(biāo)文件；如果沒有，則選取除進入線路之外的K個節(jié)點進行轉(zhuǎn)發(fā)。如果與已有信息對SID相同，則比較同一SID先行到達的其他查詢消息號。若相等，則是重復(fù)消息，丟棄；若該消息號比目前為止已到達的最大消息號還小，則認為已過時而丟棄；若該消息號比已到達的最大消息號還大，則進行轉(zhuǎn)發(fā)。

TTL和TS同時控制過時消息及時丟棄。每發(fā)送一個新消息，就為其設(shè)置一個適當(dāng)?shù)腡TL值和TS值。TTL值在每經(jīng)過一個節(jié)點時減1；TS值每毫秒遞減1。當(dāng)TTL或TS值變?yōu)?時，消息就被丟棄。利用TTL和TS同時控制比單用TTL更優(yōu)：當(dāng)網(wǎng)絡(luò)出現(xiàn)擁塞時，消息遲遲不能轉(zhuǎn)發(fā)到新的節(jié)點。TTL不能遞減，若擁塞時間過長，此時消息實際上已經(jīng)超時，由于TTL值沒有遞減為0而消息不能被丟棄，不能緩解擁塞。加上TS字段，到一定時間消息就被丟棄，避免了長時間擁塞。加入了擴散控制算法的查詢消息轉(zhuǎn)發(fā)策略算法如下：

(a)初始化TTL、TS、Num，計算到各鄰居節(jié)點的延遲，按從小到大順序排列。

(b)選取K個節(jié)點進行轉(zhuǎn)發(fā)。K由網(wǎng)絡(luò)規(guī)模決定，i∈Neigh(i)。比較（源節(jié)點ID，消息號）查詢信息對。舊消息丟棄，不作處理；新信息作如下處理：

for (i=1; i<=K; i++)

if (NewMeg=1) //新消息

{if (exist1=1‖exist2=1)

//判斷是否有所需資源信息對或資源

轉(zhuǎn)c)；

else //無，則判斷消息是否過時；過時則丟棄，不予轉(zhuǎn)發(fā)

{if (TTL＞0 TS＞0)

value+=data; 轉(zhuǎn)b)；//轉(zhuǎn)發(fā)到鄰居節(jié)點，遞歸判斷}}

(c)查找成功，判斷是命中資源還是資源信息對;

if exist1=1 //命中資源對，將value值修改回來，不復(fù)制

{N∈SuccedPath value-=data;}

else //命中資源，將value值修改回來，同時復(fù)制信息對

{N∈SuccedPath value-=data; 復(fù)制信息對;}

(d)定期更新鄰居節(jié)點表，采用最近最少使用算法（LRU）定期更新信息對。

加入了擴散控制算法的查詢轉(zhuǎn)發(fā)策略解決了本節(jié)開頭提出的問題。此時若有一個消息轉(zhuǎn)發(fā)給A，由于控制算法存在，當(dāng)TTL或TS遞減為0時將拋棄消息，從而緩解擁塞。由于此時轉(zhuǎn)發(fā)不成功，A的節(jié)點權(quán)值增加，多次反復(fù)，A的節(jié)點權(quán)值將逐漸變得相對較大，成為性能中等的節(jié)點，轉(zhuǎn)發(fā)給A的概率就降低了，使熱點熱度降低，解決了熱點問題。可見，加入了擴散控制算法的轉(zhuǎn)發(fā)策略不僅能夠促使延遲小、搜索成功的節(jié)點權(quán)值越變越優(yōu)，且當(dāng)熱點過熱時，基于反饋的算法能夠使原成功路徑上的節(jié)點權(quán)值降低，成為次選擇的節(jié)點，引導(dǎo)節(jié)點改變搜索路徑，找到另一條成功路徑，使熱點熱度降低，解決了擁塞和路由熱點問題。

3策略性能評估與實驗?zāi)M

為了評估本文策略，筆者設(shè)計了系列仿真實驗。實驗所需網(wǎng)絡(luò)拓撲用BRITE^[4]生成，仿真程序用Java編寫。實驗中設(shè)置了一個1 024長度的數(shù)組和60×1 024個字符串；數(shù)組中的每一個元素模擬一個節(jié)點，每一個字符串模擬一個文件，字符串長度為1~50。根據(jù)文獻[5]提供的數(shù)據(jù)設(shè)置每個節(jié)點的延遲如表2所示。

本文主要從搜索成功率和查詢響應(yīng)時間兩方面進行度量，并與random walks算法進行比較。

圖1記錄的是使用不同算法的搜索成功率比較。圖中三條曲線分別表示使用random walks算法、未使用副本的本文策略及使用副本的本文策略。可以看出，與隨機選取鄰居節(jié)點的random walks算法相比，基于歷史查詢反饋和擴散控制策略的搜索成功率提高了一倍。當(dāng)進行副本復(fù)制后，搜索成功率又有了大幅度提高。這是因為在高訪問成功率節(jié)點上放置副本，提高了熱點文件的命中率。

圖2為使用本文策略的查詢響應(yīng)時間。從圖中可以看出，查詢剛開始時，查詢平均響應(yīng)時間較長，但隨著基于反饋的查詢策略和擴散控制算法的執(zhí)行，擴散消息數(shù)目得到控制，副本的使用也使命中率增加，查詢時間迅速下降。由此證明該策略具有自適應(yīng)性，能根據(jù)整個系統(tǒng)資源的流行情況進行調(diào)整。資源越流行，請求人數(shù)越多，系統(tǒng)性能越優(yōu)。

4結(jié)束語

本文提出了一種基于反饋的查詢消息轉(zhuǎn)發(fā)策略和一種擴散控制算法。模擬實驗表明，該策略能有效控制擴散，提高搜索成功率，減少查詢響應(yīng)時間。在目前結(jié)構(gòu)化P2P環(huán)境中，該策略有一定的推廣利用和研究價值。當(dāng)然該策略還存在一些不足，如副本的數(shù)目對系統(tǒng)平均搜索長度也有影響。可以進一步研究如何確定副本數(shù)目以達到最優(yōu)查詢響應(yīng)時間。

參考文獻：

[1]COHEN E， SHENKER S. Replication strategies in unstructured peer－to－peer networks[C]//Proc of ACM SIGCOMM’02. New York: ACM Press， 2002:793-799.

[2]TSOUMAKOS D， ROUSSOPOULOS N. Adaptive probabilistic search(APS) for peer－to－peer networks， CS－TR-4451[R]. Maryland: University of Maryland， 2003:171－180.

[3]馮國富，毛鶯池，陸桑璐，等.PeerRank:一種無結(jié)構(gòu)化P2P資源發(fā)現(xiàn)策略[J].軟件學(xué)報，2006，17(5):1098－1106.

[4]MEDINA A， LAKHINA A， MATTAF I， et al. BRITE: an approach to universal generation[C]//Proc of International Workshop on Mo－deling， Analysis and Simulation of Computer and Telecommunications System－MASCOTS’01. Cincinnati， Ohio:[s.n.]， 2001:399-408.

[5]SAROIU S， GUMMADI P， GRIBBLE S. A measurement study of peer－to－peer file sharing systems， UW-CSE-01-06-02[R]. Washington DC: University of Washington， 2001:113－126.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”