邱建英 劉進軍 周 霞

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

[關鍵詞]P2P搜索隨機漫步

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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