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

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

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

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

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

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

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

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

(二)分布式非結(jié)構(gòu)化網(wǎng)絡(luò)模型。在分布式非結(jié)構(gòu)化的P2P中，采用洪泛查找機(jī)制?？梢詫⒁环N完全分布的網(wǎng)絡(luò)看成是一組對等節(jié)點之間的自組織網(wǎng)絡(luò)。節(jié)點在進(jìn)行資源查找時，首先將需要搜索的信息廣播到它所有的相鄰節(jié)點，然后再廣播到所有相鄰節(jié)點的相鄰節(jié)點，直到找到需要查找的資源。這種查訊機(jī)制存在網(wǎng)絡(luò)負(fù)荷過重、難以管理、穩(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é)點并不需要維護(hù)整個網(wǎng)絡(luò)的信息，只在節(jié)點中存儲其臨近的后繼節(jié)點信息，因此較少的路由信息就可以有效地實現(xiàn)到達(dá)目標(biāo)節(jié)點，同時又取消了泛洪算法。該模型有效地減少了節(jié)點信息的發(fā)送數(shù)量，從而增強了P2P網(wǎng)絡(luò)的擴(kuò)展性。同時，出于冗余度以及延時的考慮，大部分DHT總是在節(jié)點的虛擬標(biāo)識與關(guān)鍵字最接近的節(jié)點上復(fù)制備份冗余信息，這樣也避免了單一節(jié)點失效的問題。

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

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

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

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

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

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

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

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

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

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