邱建英 劉進(jìn)軍 周 霞

[摘要]研究介紹一種可選擇的Gnutella的搜索算法和數(shù)據(jù)復(fù)制策略。它是一種多次隨機(jī)漫步(multiple random walks)搜索算法，跟洪泛的搜索算法一樣快，但是減少了網(wǎng)絡(luò)的負(fù)載量。

[關(guān)鍵詞]P2P搜索隨機(jī)漫步

中圖分類號(hào)：TP3文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)；1671—7597(2009)1020096--01

Nspster自從1999年出現(xiàn)后在網(wǎng)絡(luò)上快速的流行了起來(lái)，P2P技術(shù)也同時(shí)迅速發(fā)展。由于P2P擺脫了服務(wù)器的限制，用戶可以更廣泛和直接地利用網(wǎng)絡(luò)資源。最新數(shù)據(jù)顯示P2P應(yīng)用技術(shù)的快速增長(zhǎng)強(qiáng)烈沖擊著Internet通信。在Gnutella的基礎(chǔ)上，我們研究了一種更優(yōu)的K-Random walk算法，主要研究搜索和復(fù)制，可以用來(lái)降低每次搜索的負(fù)載量。

一、主要的P2P網(wǎng)絡(luò)模型介紹

現(xiàn)在主要的P2P網(wǎng)絡(luò)模型有以下幾種：

(一)集中式網(wǎng)絡(luò)模型。在集中式P2P中，所有網(wǎng)上提供的共享資源都存放在提供該資源的客戶機(jī)上，服務(wù)器上只保留目錄信息，此外服務(wù)器與客戶機(jī)之間以及客戶機(jī)與客戶機(jī)之間都具有交互能力。這種形式具有中心化的特點(diǎn)。集中式P2P主要缺點(diǎn)為：服務(wù)器具有接入帶寬的瓶頸，一旦中央服務(wù)器的癱瘓容易導(dǎo)致整個(gè)網(wǎng)絡(luò)的崩潰。

(二)分布式非結(jié)構(gòu)化網(wǎng)絡(luò)模型。在分布式非結(jié)構(gòu)化的P2P中，采用洪泛查找機(jī)制?？梢詫⒁环N完全分布的網(wǎng)絡(luò)看成是一組對(duì)等節(jié)點(diǎn)之間的自組織網(wǎng)絡(luò)。節(jié)點(diǎn)在進(jìn)行資源查找時(shí)，首先將需要搜索的信息廣播到它所有的相鄰節(jié)點(diǎn)，然后再?gòu)V播到所有相鄰節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，直到找到需要查找的資源。這種查訊機(jī)制存在網(wǎng)絡(luò)負(fù)荷過(guò)重、難以管理、穩(wěn)定性差、擴(kuò)展困難等缺陷。

(三)分布式結(jié)構(gòu)化網(wǎng)絡(luò)模型。結(jié)構(gòu)化P2P模式是一種采用純分布式的消息傳遞機(jī)制和根據(jù)關(guān)鍵字進(jìn)行查找的定位服務(wù)，目前的主流方法是采用分布式哈希表(DHT)技術(shù)，這也是目前擴(kuò)展性最好的P2P路由方式之一。由于DHT各節(jié)點(diǎn)并不需要維護(hù)整個(gè)網(wǎng)絡(luò)的信息，只在節(jié)點(diǎn)中存儲(chǔ)其臨近的后繼節(jié)點(diǎn)信息，因此較少的路由信息就可以有效地實(shí)現(xiàn)到達(dá)目標(biāo)節(jié)點(diǎn)，同時(shí)又取消了泛洪算法。該模型有效地減少了節(jié)點(diǎn)信息的發(fā)送數(shù)量，從而增強(qiáng)了P2P網(wǎng)絡(luò)的擴(kuò)展性。同時(shí)，出于冗余度以及延時(shí)的考慮，大部分DHT總是在節(jié)點(diǎn)的虛擬標(biāo)識(shí)與關(guān)鍵字最接近的節(jié)點(diǎn)上復(fù)制備份冗余信息，這樣也避免了單一節(jié)點(diǎn)失效的問(wèn)題。

(Du)Gnutel I a P2P系統(tǒng)。Gnutella是一個(gè)P2P文件共享系統(tǒng)，它和Napster最大的區(qū)別在于Gnutella是純粹的P2P系統(tǒng)，沒(méi)有索引服務(wù)器，它采用了基于完全隨機(jī)圖的洪泛(Floodimg)發(fā)現(xiàn)和隨機(jī)轉(zhuǎn)發(fā)(RandomWalker)機(jī)制。為了控制搜索消息的傳輸，通過(guò)TTL(Time To Live)的減值來(lái)實(shí)現(xiàn)。

二、Gnutella的工作原理及更優(yōu)的搜索方法

在Gnutella的工作過(guò)程中，對(duì)等結(jié)點(diǎn)A在初始化時(shí)有在Gnutella網(wǎng)絡(luò)中的對(duì)等結(jié)點(diǎn)B的IP地址，當(dāng)^和B連接后，^可以獲得B所知道的所有系統(tǒng)結(jié)點(diǎn)信息，這樣A就可以選擇某一結(jié)點(diǎn)建立直接的TCP／IP連接。每個(gè)Gnutella節(jié)點(diǎn)都定義了本地的共享文件夾，它們可以根據(jù)文件名的部分匹配或完全匹配進(jìn)行查找。查找按照簡(jiǎn)單洪泛(flooding)方式進(jìn)行，首先傳播到所有相鄰結(jié)點(diǎn)，再傳播到相鄰節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，直到達(dá)到預(yù)先確定的層次為止。每條查找消息都帶有全局而惟一的標(biāo)識(shí)符，防止對(duì)同樣的查找消息進(jìn)行多次響應(yīng)。用戶可以基于查找結(jié)果，選擇合適的文件進(jìn)行下載并可以和每個(gè)文件所有者結(jié)點(diǎn)建立類{~ITTP的連接。

Gnutella系統(tǒng)采用Flooding查詢。在網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都不知道其他節(jié)點(diǎn)的資源，當(dāng)從某一節(jié)點(diǎn)要尋找某個(gè)文件，就把這個(gè)查詢信息傳遞給它的相鄰節(jié)點(diǎn)，如果相鄰節(jié)點(diǎn)含有這個(gè)資源，就返回一個(gè)QueryHit的信息給Requester。如果它相鄰的節(jié)點(diǎn)都沒(méi)有命中這個(gè)被查詢文件。就把這條消息轉(zhuǎn)發(fā)給自己的相鄰節(jié)點(diǎn)。這種方式像洪水在網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)流動(dòng)一樣，所以叫做Flooding搜索，由于這種搜索策略是首先遍歷自己的鄰接點(diǎn)，然后再向下傳播，所以又稱為寬度優(yōu)先搜索方法(BFS)。很顯然，F(xiàn)looding搜索有一定的盲目性。

Gnutella用基于TTL的洪泛方法來(lái)搜索目標(biāo)。這種方法會(huì)產(chǎn)生很多冗余的信息，特別是在高連通的路徑中。同時(shí)，由于受到網(wǎng)絡(luò)重疊的拓樸結(jié)構(gòu)和復(fù)制率的影響，很難找到合適的TTL，為了解決TTL的設(shè)置問(wèn)題，可以用連續(xù)的洪泛并使TTL的值不斷增加。這種搜索策略是在初始階段，給TTL(Time To Live)一個(gè)很小的值，如果在TTL減為0時(shí)，還沒(méi)有搜索到資源，則給TTL重新賦更高的值，直到找到目標(biāo)為止。這個(gè)方法叫做反復(fù)加深深度搜尋法，這種方法的好處是：相對(duì)于比較冷的資源，比較熱的資源能被大范圍的復(fù)制。這種策略可以減少搜索的半徑，但是在最壞的情況下，延遲很長(zhǎng)。

然而，擴(kuò)大半徑并不能解決洪泛固有的復(fù)制問(wèn)題，所以可以采取另一種方法：Random Walk(隨機(jī)轉(zhuǎn)發(fā))。在隨機(jī)轉(zhuǎn)發(fā)中。請(qǐng)求者發(fā)出查詢請(qǐng)求給隨機(jī)挑選的相鄰節(jié)點(diǎn)。然后每個(gè)查詢信息在以后的轉(zhuǎn)發(fā)過(guò)程中直接與請(qǐng)求者保持聯(lián)系，詢問(wèn)是否還耍繼續(xù)下一步。如果請(qǐng)求者同意繼續(xù)轉(zhuǎn)發(fā)，則又開(kāi)始隨機(jī)選擇下一步轉(zhuǎn)發(fā)的節(jié)點(diǎn)，否則中止搜索。我們叫這個(gè)消息為步，標(biāo)準(zhǔn)的隨機(jī)漫步僅用一步，這大大減少了消息量，但是會(huì)增加延遲。為了減少延遲，我們?cè)黾恿瞬綌?shù)。請(qǐng)求者發(fā)出K個(gè)查詢請(qǐng)求給隨機(jī)挑選的K個(gè)相鄰節(jié)點(diǎn)，然后每個(gè)查詢信息在以后的轉(zhuǎn)發(fā)過(guò)程中直接與請(qǐng)求者保持聯(lián)系。詢問(wèn)是否還要繼續(xù)下一步。如果請(qǐng)求者同意繼續(xù)轉(zhuǎn)發(fā)，則又開(kāi)始隨機(jī)選擇下一步轉(zhuǎn)發(fā)的節(jié)點(diǎn)，否則中止搜索，這就是k-walker random walk算法。

在非結(jié)構(gòu)化的網(wǎng)絡(luò)中，加快搜索的方法是在盡可能短的時(shí)間里找到對(duì)的節(jié)點(diǎn)，但是在找到要求的節(jié)點(diǎn)前，我們需要考慮以下三點(diǎn)：適度的中止，減少消息的復(fù)制量，和小范圍的粒度。

1、適度的中止是非常重要的?；赥TL的機(jī)構(gòu)不再工作，任何動(dòng)態(tài)的中止將避免搜索的內(nèi)部爆炸。

2、消息的復(fù)制應(yīng)該要減到最小。每次搜索應(yīng)該只對(duì)某一節(jié)點(diǎn)訪問(wèn)一次。過(guò)多訪問(wèn)在消息管理方面會(huì)造成浪費(fèi)。

3、粒度的范圍應(yīng)該要小。在搜索中，每一個(gè)步的增加不要求增加大量的節(jié)點(diǎn)訪問(wèn)。這可能就是反復(fù)加深深度搜尋法和多步隨機(jī)轉(zhuǎn)發(fā)的區(qū)別。