分布式非結構化P2P網絡中的搜索技術優化

邱建英 劉進軍 周 霞

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

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

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

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

一、主要的P2P網絡模型介紹

現在主要的P2P網絡模型有以下幾種：

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

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

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

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

二、Gnutella的工作原理及更優的搜索方法

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

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

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

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

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

1、適度的中止是非常重要的。基于TTL的機構不再工作，任何動態的中止將避免搜索的內部爆炸。

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

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