非結構化對等網絡資源定位機制研究

摘要：非結構化對等網絡是當今P2P的主流，資源搜索定位機制是其核心問題，Gnutella為代表的非結構化對等網絡采用基于BFS和DFS的定位機制。在分析非結構化對等網絡特征的基礎上，提出了改進搜索定位機制的思路和方法。

關鍵詞：對等網絡；非結構化；搜索；定位機制

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)22-652-02

Research on the Resources Search Localization Mechanism in Unstructured P2P Network

CHEN Hua，PING Xiao-yan

(Kangding Nationality Teacher's College，Kangding 626001，China)

Abstract:The unstructured peer-to-peer network is the P2P mainstream， the resources search localization mechanism is now its core question， Gnutella is representative's unstructured peer-to-peer network uses based on BFS and the DFS localization mechanism. In the analysis of the unstructured peer-to-peer network characteristic foundation， proposed the improvement search localization mechanism mentality and the method.

Key words: Peer-to-peer network; unstructured; Search; Localization mechanism

1 引言

Peer-to-peer（對等網絡，簡稱P2P）技術是近年來興起并獲得廣泛研究和應用的技術，是互聯網技術的本質回歸，增強了用戶的網絡體驗。P2P網絡的典型特征有：節點間可以直接訪問資源；節點同時充當client（客戶端）和server（服務器）的角色；節點自治性；整個網絡無集中控制，沒有全局視圖，節點動態地加入和退出網絡。

P2P網絡的應用發展迅速，在眾多領域中得到了廣泛應用。P2P的基本靜態元素是節點，一般指計算機（包含CPU、存儲、網絡帶寬），故P2P技術主要應用在協同計算（共享CPU）、分布式存儲（共享存儲）、內容分發與即時通訊（共享網絡帶寬）等方面；節點的生命周期為加入網絡、搜索、協同工作（如下載）、退出網絡，其中，節點如何加入和退出即網絡的構建是整個P2P網絡術的基礎，而節點的資源搜索定位和協同工作即節點間如何通訊是P2P網絡的核心問題。

2 非結構化對等網絡

在P2P技術中，把有特定邏輯拓撲結構的網絡稱為結構化對等網絡，當前主要是指基于DHT（Distributed Hash Table，分布式哈希表）技術構建的網絡，也常稱為DHT網絡[1]。結構化P2P網絡能為內容定位提供高效支持，但不支持模糊和多關鍵字查詢。典型的結構化P2P網絡包括Chord、CAN、Pastry、Tapestry等。

非結構化對等網絡（Unstructured P2P Network）是指沒有固定邏輯拓撲結構的P2P網絡，是依照隨機方式構造的。非結構化對等網絡的主要特征有：節點ID與其邏輯位置沒有固定約束關系，節點間連接是隨機的，內容與其邏輯存儲位置無固定約束關系，并且節點隨機的加入網絡，可以選擇任意節點作為自己的邏輯鄰居，內容也存儲在任意節點。

相比DHT網絡，非結構化對等網絡支持模糊和復雜關鍵字查詢，能更好的支持節點動態性和異構性，在P2P網絡中，非對等網絡得到了廣泛應用。典型的非結構化網絡包括Gnutella、Freenet等。

3 非結構化對等網絡的搜索策略

在非結構化對等網絡中，內容搜索是指定位資源的過程，定位是預測概率P（N|Q），即給定節點N滿足給定查詢Q的概率[1]。由于沒有全局視圖，任何節點無法知道全部節點的信息，如果節點知道的信息越多，則定位的開銷就越小，查詢成功的概率越大，所以從根本上說P2P搜索是隨機搜索策略，即通過消息擴散機制來定位資源，并獲得網絡的局部視圖。在非結構化對等網絡中，基本的搜索策略包括2大類：DFS類（depth first search，深度優先搜索）和BFS類（breadth first search，寬度優先搜索）。

3.1 基本搜索策略

設節點P2P網絡節點度為N（即每個節點有N個鄰居節點），搜索步長（hop）為TTL，每個節點選擇b（1

■(1)

當b為N時，即選擇所有鄰居節點發送消息，此時的搜索策略即為泛洪搜索（flood），當b為1時，即只選擇一個鄰居發送消息，此時的搜索策略就是深度優先搜索（DFS），發送消息數為TTL，每搜索一步TTL減一，理想結果是在TTL內定位內容，否則，拋棄消息。從公式1可以看出，深度優先搜索類算法復雜度隨著節點數線性增長，定位消息開銷小，但定位的延時長；而寬度優先搜索類算法選擇的鄰居節點多，隨著TTL成指數增長，定位延時短，但定位消息開銷大。

研究者在BFS和DFS的基礎上提出了很多搜索算法。如RBFS（randomBFS，隨機寬度優先搜索），節點隨機選擇一部分鄰居進行定位消息轉發，減少消息數，但此算法存在搜索覆蓋問題。又如漫步者算法（Random Walkers），節點選擇1

3.2 典型代表Gnutella[2]

Gnutella網絡是最早的非結構化P2P網絡，是使用泛洪算法（flood）即寬度優先搜索類算法的典型代表。Gnutella協議中有5類定位消息：Ping、Pong消息用于發現節點，Query、QueryHit、，Push消息用于內容定位，消息有統一的ID，消息的基本格式表1所示：

表1Gnutella0.4消息基本格式

■

當一個節點要加入系統時，首先廣播初始Ping消息（無具體負載），節點收到Ping消息后，如果以前接收過相同ID的消息，放棄處理，否則，將消息TTL減一，并轉發到自己的所有鄰居，同時原路返回Pong消息（具體負載為端口、ip地址、共享文件數、共享千字節數），這一過程持續到TTL等于0結束，此時，初始節點可以與這些節點連接。

當節點定位某文件時，向其所有鄰居發送Query消息（具體負載包含文件描述符等信息），鄰居節點收到此Query消息，對本地文件進行匹配，成功則返回QueryHit或者Push消息（具體負載為命中結果數、端口、ip地址、下載速率、結果集、服務節點ID），并將TTL減一，無論成功與否，轉發此Query消息，此過程直到TTL等于0時結束。

Gnutella的缺點是明顯的，由于采用泛洪算法，存在多條冗余路徑（即大量節點有相同的鄰居），其二，消息開銷大，如若設置TTL為7，用公式1我們得知，若b為8則一次定位產生的消息數為2097152個。在新版本的Gnutella中，采用超級節點部分地解決了這些問題。

4 搜索策略的改進

泛洪算法無需節點知道全局視圖，實現簡單，但有很大的缺點：搜索成功率低，搜索開銷和搜索延遲大。因此研究更高效的搜索算法成為P2P技術研究中的熱點。

我們來看P2P網絡特征對搜索策略的影響。從單個節點看，節點的能力有大有小，表現在節點的計算能力（CPU）、存儲能力、網絡帶寬有差異；其二，節點的行為有差異，表現在節點在線時間、請求資源興趣有所不同。

從整個非結構化P2P網絡來看，其具有冪律特征，是典型的小世界網絡（small world）[3]，研究發現，Gnutella網絡具有冪律特征，且冪律指數為2.3，網絡中存在少量約4%高度數節點，如果移除這些節點，Gnutella網絡將分割成許多孤立的小網絡；20%左右的節點間的延遲比其他節點間延遲小得多。第二，用戶的有限興趣原則，研究發現短時間內多個用戶發出相同的文件請求，受歡迎文件分布類似Zipf分布[3]，第i個受歡迎文件被請求的概率與 成正比。第三，空間局部性原則，即若節點a有節點b感興趣的文件，那么節點a的其它文件也很可能是節點b感興趣的文件。

綜上所述，在P2P網絡中，節點的能力異構和行為異構是普遍的且具有一定的局部性規律，為搜索定位算法的優化和改進指出了方向。

4.1 構建有利于搜索的覆蓋網（overly Network）

1)基于興趣分組。由前面的論述得知，用戶的興趣在短時間內是有限的且具有空間局部性規律，因此第一類想法是基于用戶興趣構建網絡，將興趣相同的節點構成“興趣組”，大部分搜索定位在興趣組內進行，如若沒有成功，才連接到組外的節點。這種方法大大減少了定位消息通信量，并且延遲小。

2)基于能力分組。節點的能力是有差異的，基于“能力越大，責任越大”原則，將節點分為超節點和普通節點，超節點負責一定范圍內的搜索定位，類似實際網絡的路由器，超節點之間又構成分組，共享全局定位消息，按這種方法構成的網絡符合冪律規律。新版的Gnutella就是這類方法。

3)基于物理網絡拓撲分組。P2P網絡是邏輯覆蓋網（overly network），存在與物理網絡拓撲匹配問題，導致定位消息的開銷增大。如果能構建符合物理網絡拓撲的覆蓋網，則將大大減少定位消息開銷和延遲?；镜姆椒ㄊ窃诠濣c本地生成到鄰居節點的時間延遲樹，定位消息優先發往時間延遲小的鄰居節點。

4)分層設計。P2P網絡是動態和異構的，設計P2P可以采取“分而治之“的靈活策略。如在覆蓋網底層部分，使用DHT技術構建，在上層，構建基于興趣分組的超節點網絡。

4.2 輔助定位信息的運用

P2P網絡的動態和異構性使節點無法獲得全局視圖，節點必須通過一定的輔助信息進行搜索定位。在泛洪算法中，節點只是簡單的發送和接收定位消息，并未保存歷史消息，這種方法實現簡單，但缺點明顯，節點對鄰居仍然一無所知；如果能利用這些動態消息，節點獲取的信息就越多，搜索的效率就越高，實際上，這是一種空間換時間的思路。

1)元數據的運用。P2P的基本功能之一是內容的存儲與分發，如果能高效的標識內容，則定位的成功率將大大提高。大部分靜態信息都可以按照一定規律生成元數據，如IP地址、文件、從而形成元數據空間，資源的搜索定位則在元數據空間進行。元數據通常與緩存機制結合，以提高搜索的效率。這一思路和數據索引類似，比如BitTorrent[4]網絡中，將內容進行hash編碼得到全局唯一的內容摘要，資源的搜索定位就變得非常簡單，因為內容摘要在全局是唯一的。

2)動態信息的運用。在節點的生存周期中，有很多動態信息，大部分是統計信息，如能力信息，路徑信息，返回結果信息等。如果能利用這些信息，搜索效率會提高。比如在本地生成攜帶信息的路由表（Routing Table），保存鄰居節點的信息，如時間延遲度，文件擁有度等，在此基礎上，動態更新鄰居信息，以提高定位搜索的效率。

5 結束語

在P2P技術中，非結構化P2P網絡得到了廣泛應用。以BFS和DFS為基礎的資源搜索定位機制是非結構化P2P網絡的核心問題。非結構化對等網絡特征是有規律可循的，在此基礎上，可以有多種思路和方法改進資源搜索定位機制。

參考文獻：

[1] 熊繼平.對等網絡中的路由機制及關鍵技術技術研究[D].合肥:中國科學技術大學，2006.

[2] Gnutella.http://www.gnutella.org

[3] 陳海濤.對等網絡中的內容搜索、定位和下載技術研究[D].長沙:國防科技大學，2005.

[4] BitTorrent Protocol Specification. http://www.bittorrent.org/beps/bep_0003.html.