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

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

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

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

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

0引言

P2P對(duì)等網(wǎng)絡(luò)是一種與傳統(tǒng)C/S模式不同的新型網(wǎng)絡(luò)。該網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)地位對(duì)等，既充當(dāng)服務(wù)器，為其他節(jié)點(diǎn)提供服務(wù)；同時(shí)也為客戶機(jī)，享用其他節(jié)點(diǎn)提供的服務(wù)。P2P技術(shù)使任意兩臺(tái)相連接的計(jì)算機(jī)直接共享文檔、多媒體和其他各種類型的文件成為可能。利用P2P技術(shù)，計(jì)算機(jī)之間可以進(jìn)行直接交互，而不需要使用任何一臺(tái)中央服務(wù)器。由于大部分處理直接在節(jié)點(diǎn)之間進(jìn)行，減少了對(duì)服務(wù)器的依賴，具有很好的可擴(kuò)展性。目前，P2P技術(shù)已經(jīng)應(yīng)用于很多領(lǐng)域，如文件共享、即時(shí)通信、協(xié)同工作、分布式計(jì)算、電子商務(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資源定位快，但需要以很高的代價(jià)維護(hù)既定拓?fù)洌荒芎芎玫剡m應(yīng)高度動(dòng)態(tài)的P2P環(huán)境。無結(jié)構(gòu)化P2P資源的查找和定位通過擴(kuò)散來實(shí)現(xiàn)，搜索數(shù)據(jù)幾乎是隨機(jī)搜索，容易造成網(wǎng)絡(luò)流量急劇增加，導(dǎo)致網(wǎng)絡(luò)擁塞。因此，無結(jié)構(gòu)化P2P的一個(gè)核心問題就是如何進(jìn)行快速搜索，同時(shí)降低網(wǎng)絡(luò)帶寬消耗，保證系統(tǒng)可擴(kuò)展性和容錯(cuò)性。本文主要討論無結(jié)構(gòu)P2P網(wǎng)絡(luò)環(huán)境下的搜索策略。

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

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

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

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

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

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

2．1模型假設(shè)

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

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

每個(gè)節(jié)點(diǎn)保存以下幾個(gè)集合：

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

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

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

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

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

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

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

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

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

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

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

算法如下：

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

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

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

if (exist1=1‖exist2=1)

//判斷是否有所需資源信息對(duì)或資源

轉(zhuǎn)c)；

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

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

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

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

{N∈SuccedPath value-=data;}

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

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

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

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

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

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

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

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

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

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

if (NewMeg=1) //新消息

{if (exist1=1‖exist2=1)

//判斷是否有所需資源信息對(duì)或資源

轉(zhuǎn)c)；

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

{if (TTL＞0 TS＞0)

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

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

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

{N∈SuccedPath value-=data;}

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

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

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

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

3策略性能評(píng)估與實(shí)驗(yàn)?zāi)M

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

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

圖1記錄的是使用不同算法的搜索成功率比較。圖中三條曲線分別表示使用random walks算法、未使用副本的本文策略及使用副本的本文策略?？梢钥闯?，與隨機(jī)選取鄰居節(jié)點(diǎn)的random walks算法相比，基于歷史查詢反饋和擴(kuò)散控制策略的搜索成功率提高了一倍。當(dāng)進(jìn)行副本復(fù)制后，搜索成功率又有了大幅度提高。這是因?yàn)樵诟咴L問成功率節(jié)點(diǎn)上放置副本，提高了熱點(diǎn)文件的命中率。

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

4結(jié)束語

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

參考文獻(xiàn)：

[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é)報(bào)，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)容請(qǐng)以PDF格式閱讀原文”