Ｐ２Ｐ網絡搜索方法剖析

摘要：介紹了P2P的概念和特點，分析了P2P搜索與傳統搜索的不同之處，并從結構角度出發剖析和比較了P2P四種不同的搜索技術，給出了它們的優缺點。

關鍵詞：P2P；網絡搜索

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

Analysis of P2P Networks Search Method

HUANG Xi-ni

(Dept. of Computer Science，Zhanjiang Pedagogical Academy，Zhanjiang 524037，China)

Abstract:In this paper，we firstly introduce the concept and characteristics of P2P， analysis of the difference between the P2P search and the traditional search， and to analysis and compare of the four different P2P search technology， given their advantages and disadvantages.

Key words: peer-to-peer;web searching

1 引言

近幾年來，計算機對等網（peer-to-peer）技術的迅猛發展，P2P的研究得到了國內外學術界和商業組織的廣泛關注，并被《財富》雜志稱為改變因特網未來的四大新技術之一。目前，P2P研究中的一個主要問題就是搜索問題。P2P搜索技術發展迅速，給傳統的web搜索技術帶來了很大的沖擊。

2 P2P概念和特點

對等計算（Peer-to-Peer，簡稱P2P）[1]， P2P是一種分布式網絡，在這種網絡中所有的節點是對等的（稱為對等點），各節點具有相同的責任與能力并協同完成任務。對等點之間通過直接互連共享信息資源、處理器資源、存儲資源甚至高速緩存資源等，無需依賴集中式服務器或資源就可完成。P2P網絡和與當今廣泛使用的客戶端/服務器（C/S）的在通信模式和網絡結構上有很大的不同，C/S模式中服務器是網絡的控制核心，而P2P模式的節點則具有很高的自治性和隨機性。如下圖是P2P模式與C/S模式的比較:

圖1 C/S模式網絡結構

圖2 P2P模式網絡結構

P2P網絡結構無中心化，走向網絡邊沿，使得網絡上的閑置的網絡資源得以充分利用，在一定程度上解決了C/S模式中擴散性差、負載不均衡、健壯性差等方面的缺點，但P2P也帶來了管理難，搜索相對復雜的缺點。

3 P2P搜索與傳統搜索的比較

P2P領域一個很重要的研究就是搜索研究，P2P網絡中的搜索和現在使用的搜索引擎搜索技術有很大的差別。在P2P網絡中，用戶將各自擁有的資源共享出來，搜索無需要通過Wed服務器，不受文檔格式與宿主設備限制，一臺設備的消息對應N臺，搜索的范圍將會在幾秒鐘內以幾何級數增長，可以達到傳統搜索無法比擬的搜索深度。P2P搜索促進了搜索的多元化和權利、義務的分解，使每一臺機器都參與到了搜索過程中去，由普通的接受服務的客戶端向可以提供服務的一方轉變。在一定程度上彌補傳統搜索技術不足。

4 P2P的網絡搜索模型

P2P的檢索方式取決于系統的資源發布模式。P2P搜索技術從結構角度出發可以分為四類：集中式P2P網絡的搜索技術，結構化P2P網絡的搜索技術，非結構化P2P網絡的搜索技術，混合式P2P網絡的搜索技術。

4.1 集中式P2P網絡的搜索技術

P2P集中索引模型是中心化拓撲的網絡，整個系統由目錄服務器和客戶端（對等體）構成。目錄服務器由一臺或多臺有高性能的服務器承擔，主要負責所有活動客戶端共享資源的管理，提供資源查詢服務。對等體加入網絡時向目錄服務器注冊關于自身的信息（其名稱、地址、資源和元數據），當對等體的資源發生變化時，比如資源的增加，修改，刪除等，也向索引服務器提供更新消息，服務器據此修改緩存的資源索引信息。對等體根據服務器返回的消息與對應擁有資源的對等體建立連接，并在對等體之間傳輸文件。這類網絡的代表系統有Napster、eMule，如圖3，Napster網絡模型，P5查找文件S2并下載。

這種模式實現了文件查詢與文件傳輸的分離，有效地節省了中央服務器的帶寬消耗，減少了系統的文件傳輸延時，因此查詢效率高、對等體負載均衡、系統可維護性好。但是由于采用了中心化拓撲結構，所以對索引服務器的處理能力和帶帶寬的要求很高、安全性要求比較高，易遭受Dos（拒絕服務攻擊）等攻擊而癱瘓。P2P系統本質上所不可避免的兩個問題：索引服務器法律版權糾紛問題和資源浪費的問題。集中式P2P網絡，在管理方面有一定的優勢，但是當網絡擴展，維護的成本會很大的提高，這種形式不適合大型網絡使用，這種網絡的搜索形式只適合小型網絡。

4.2 非結構化P2P網絡的搜索技術

圖3Napster（集中式P2P）網絡結構

圖4 Gnutella（分布式P2P）網絡結構

圖5 Chord的搜索過程

非結構化P2P網絡不存在中心目錄服務器，所有的服務及相關信息完全散布在各個P2P結點中，因此其最顯著的特點就是“完全去中心化” [3]。這是一種純的P2P網絡，每個peer既可以作為客戶端又可以作為服務器，并且它和相鄰的Peer有相同的能力。搜索技術主要采取的是泛洪（Flooding）。非結構化P2P網絡的典型代表就是Gnutella，采取基于隨機圖的泛洪算法，如圖4所示。每個結點都將自己收到的消息轉發出去，這種查找方式使得網絡流量的幾何式增長，一般通過TTL（Time To Live）機制來控制查詢的深度。節點的查詢消息時設置TLL初值，如TLL=4，消息傳播一次TLL減1，TLL=0時停止傳播，控制消息永遠循環。但隨著聯網節點的不斷增多，網絡規模不斷擴大，通過這種Flooding方式定位對等點的方法將造成網絡流量急劇增加，從而導致網絡中部分低帶寬節點因網絡資源過載而失效。

4.3 結構化P2P網絡的搜索技術

結構化P2P網絡是純的P2P網絡，采用分布式哈希表（Distributed Hash，Table簡稱DHT）結構，使用分布式哈希表索引對資源和節點進行搜索。在結構化P2P網絡中，客戶端主機稱為節點，文件數據稱為對象。首先，將搜索空間對應到一個散列（Hash）空間，對各個節點（基于節點的IP地址）也進行相應散列如N=HASH（IP），每個節點各負責一部分散列空間。當一個節點發布一個資源（例如文件），需要對該資源的唯一標識（如文件名）進行散列K=HASH（文件的名字），而根據該散列值可以確定負責管理該資源的節點。代表軟件有Chord，CAN，Tapestry， Pastry等。如圖5為Chord的搜索過程。Chord誕生于美國的麻省理工學院。它的目標是提供一個適合于P2P環境的分布式資源發現服務，它通過使用DHT技術使得發現指定對象只需要維護O（logN）長度的路由表。chord的主要貢獻是提出了一個分布式查找協議，該協議可將指定的關鍵字（Key）映射到對應的節點（Node）搜索時源節點的請求發送到與資源標識符最接近的節點上。收到查詢請求的節點如果發現自身存儲了被查詢的信息，可以直接回應源節點，不在則將請求轉發到與鍵值最接近的節點上。這樣的過程一直持續到找到相應的節點為止。搜索過程實際上就是折半查找的過程。

DHT類結構能夠自適應結點的動態加入/退出，有著良好的可擴展性、魯棒性、結點ID分配的均勻性和自組織能力。由于重疊網絡采用了確定性拓撲結構，DHT可以提供精確的發現。

4.4 混合式P2P網絡的搜索技術

在混合P2P網絡中，選擇性能較高（處理、存儲、帶寬等方面性能）的節點作為超級節點（Super-peer），在各個超級節點上存儲了系統中其他部分節點的信息，發現算法僅在超級節點之間轉發，超級節點再將查詢請求轉發給適當的端點。其代表就是KaZaA，其搜索過程如圖6所示。混合式P2P網絡搜索的優點是性能、可擴展性較好，較容易管理，但對超級節點依賴性大，易于受到攻擊，容錯性也受到影響，實現上比較困難，為了能夠利用這種模式的優點，需要提供能夠有效組織對等體間關系的搜索網絡，這里所說的組織關系，包括超級節點間的組織模式、客戶對等體與超級節點間的組織模式、超級節點間的負載平衡等。

4.5 四種網絡搜索技術性能分析

綜上所述， P2P網絡搜索的四種性能比較可歸納為下表1。

表1 P2P網絡性能比較

5 P2P搜索技術研究的挑戰

P2P搜索技術中最重要的研究成果應該是基于Small World理論的非結構化搜索算法和基于DHT的結構化搜索算法。但是P2P在實際的應用中，以下因素影響了搜索的效率：

5.1 網絡節點異質性

物理網絡中影響路由的一些因素開始影響P2P發現算法的效率。P2P由于客戶機/服務器模式在Internet和分布式領域十幾年的應用和大量種類的電子設備的普及，如手提電腦、移動電話或PDA。這些設備在計算能力、存儲空間和電池容量上差別很大。在通信基礎方面，P2P必須提供在現有硬件邏輯和底層通信協議上的端到端定位（尋址）和握手技術，建立穩定的連接。實際網絡被路由器和交換機分割成不同的自治區域，體現出嚴密的層次性。

5.2 網絡的波動程度

網絡波動（Churn）包括結點的加入、退出、失敗、遷移、并發加入過程、網絡分割等。網絡的波動的影響節點發現算法的效率。

5.3 復查查詢的需求

復雜的查詢，如關鍵詞、內容查詢等，DHT精確關鍵詞映射的特性阻礙了DHT在復雜查詢方面的應用。

P2P搜索方法一直是研究的熱點。但是與傳統的搜索技術還有很大的差距，研究搜索速度快、成本低、分布性好、支持多關鍵詞搜索、帶寬要求小的P2P搜索方法，可以使搜索技術大步向前邁進，走出搜索形式多樣化的道路

6 小結

本文對P2P網絡模式與傳統的c/s模式的分析比較，主要研究了P2P的四種網絡模式和其搜索方法的剖析，對P2P將來的應用進行了展望。

參考文獻：

[1] 張炤峰.P2P搜索技術研究[D].沈陽.沈陽工業大學，2007:8-10.

[2] 楊天路，劉宇宏，張文，等.P2P網絡技術原理與系統開發案例[M].北京:人民郵電出版社，2007:37-63.

[3] 楊再晗，陳建二，王建新.P2P計算研究現狀及關鍵技術[J].現代電子技術，2004(1):1.

[4] 《電信新技術新業務新要點解讀叢書》編寫組.對等網絡（P2P）[M].北京:人民郵電出版社，2007:17-35.