1　緒言

1.1?Peer-To-Peer?介紹

最近幾年，對等計算( Peer-to-Peer，簡稱P2P)?迅速成為計算機界關注的熱門話題之一，財富雜志更將P2P列為影響Internet未來的四項科技之一。

目前,在學術界、工業界對于P2P沒有一個統一的定義，下面列舉幾個常用的定義供參考：

定義:1、Peer-to-peer is a type of Internet network allowing a group of computer users with the same networking program to connect with each other for the purposes of directly accessing files from one another's hard drives.

2、Peer-to-peer networking (P2P) is an application that runs on a personal computer and shares files with other users across the Internet. P2P networks work by connecting individual computers together to share files instead of having to go through a central server.

3、P2P是一種分布式網絡，網絡的參與者共享他們所擁有的一部分硬件資源（處理能力、存儲能力、網絡連接能力、打印機等），這些共享資源需要由網絡提供服務和內容，能被其它對等節點(Peer)直接訪問而無需經過中間實體。在此網絡中的參與者既是資源（服務和內容）提供者（Server），又是資源（服務和內容）獲取者（Client）。

雖然上述定義稍有不同，但共同點都是P2P打破了傳統的Client/Server (C/S)模式，在網絡中的每個結點的地位都是對等的。每個結點既充當服務器，為其他結點提供服務，同時也享用其他結點提供的服務。P2P與C/S模式的對比如下圖所示:

Client/Server模式	Peer to Peer 模式

P2P技術的特點體現在以下幾個方面。

• 非中心化（Decentralization）：網絡中的資源和服務分散在所有結點上，信息的傳輸和服務的實現都直接在結點之間進行，可以無需中間環節和服務器的介入，避免了可能的瓶頸。P2P的非中心化基本特點，帶來了其在可擴展性、健壯性等方面的優勢。

• 可擴展性：在P2P網絡中，隨著用戶的加入，不僅服務的需求增加了，系統整體的資源和服務能力也在同步地擴充，始終能較容易地滿足用戶的需要。整個體系是全分布的，不存在瓶頸。理論上其可擴展性幾乎可以認為是無限的。

• 健壯性：P2P架構天生具有耐攻擊、高容錯的優點。由于服務是分散在各個結點之間進行的，部分結點或網絡遭到破壞對其它部分的影響很小。P2P網絡一般在部分結點失效時能夠自動調整整體拓撲，保持其它結點的連通性。P2P網絡通常都是以自組織的方式建立起來的，并允許結點自由地加入和離開。P2P網絡還能夠根據網絡帶寬、結點數、負載等變化不斷地做自適應式的調整。

• 高性能/價格比：性能優勢是P2P被廣泛關注的一個重要原因。隨著硬件技術的發展，個人計算機的計算和存儲能力以及網絡帶寬等性能依照摩爾定理高速增長。采用P2P架構可以有效地利用互聯網中散布的大量普通結點，將計算任務或存儲資料分布到所有結點上。利用其中閑置的計算能力或存儲空間，達到高性能計算和海量存儲的目的。通過利用網絡中的大量空閑資源，可以用更低的成本提供更高的計算和存儲能力。

• 隱私保護:?在P2P網絡中，由于信息的傳輸分散在各節點之間進行而無需經過某個集中環節，用戶的隱私信息被竊聽和泄漏的可能性大大縮小。此外，目前解決 Internet隱私問題主要采用中繼轉發的技術方法，從而將通信的參與者隱藏在眾多的網絡實體之中。在傳統的一些匿名通信系統中，實現這一機制依賴于某些中繼服務器節點。而在P2P中，所有參與者都可以提供中繼轉發的功能，因而大大提高了匿名通訊的靈活性和可靠性，能夠為用戶提供更好的隱私保護。

• 負載均衡:?P2P 網絡環境下由于每個節點既是服務器又是客戶機，減少了對傳統C/S結構服務器計算能力、存儲能力的要求，同時因為資源分布在多個節點，更好的實現了整個網絡的負載均衡。

與傳統的分布式系統相比，P2P技術具有無可比擬的優勢。同時，P2P技術具有廣闊的應用前景。Internt上各種P2P應用軟件層出不窮，用戶數量急劇增加。2004年3月來自www.slyck.com的數據顯示，大量P2P軟件的用戶使用數量分布從幾十萬、幾百萬到上千萬并且急劇增加，并給Internet帶寬帶來巨大沖擊。P2P計算技術正不斷應用到軍事領域，商業領域，政府信息，通訊等領域。

根據具體應用不同，可以把P2P分為以下這些類型：

• 提供文件和其它內容共享的P2P網絡，例如Napster、Gnutella、eDonkey、emule、BitTorrent等；

• 挖掘P2P對等計算能力和存儲共享能力，例如SETI@home?、Avaki、Popular Power等；

• 基于P2P方式的協同處理與服務共享平臺，例如JXTA、Magi、Groove、.NET My Service等；

• 即時通訊交流，包括ICQ、OICQ、Yahoo Messenger等；

• 安全的P2P通訊與信息共享，例如Skype、Crowds、Onion Routing等。

  
  

1.2國內外P2P技術研究現狀

1.2.1 P2P網絡中的拓撲結構研究

拓撲結構是指分布式系統中各個計算單元之間的物理或邏輯的互聯關系，結點之間的拓撲結構一直是確定系統類型的重要依據。目前互聯網絡中廣泛使用集中式、層次式等拓撲結構，Interne本身是世界上最大的非集中式的互聯網絡，但是九十年代所建立的一些網絡應用系統卻是完全的集中式的系統、很多Web應用都是運行在集中式的服務器系統上。集中式拓撲結構系統目前面臨著過量存儲負載、Dos攻擊等一些難以解決的問題。

P2P系統一般要構造一個非集中式的拓撲結構，在構造過程中需要解決系統中所包含的大量結點如何命名、組織以及確定結點的加入/離開方式、出錯恢復等問題。

根據拓撲結構的關系可以將P2P研究分為4種形式：中心化拓撲（Centralized Topology）；全分布式非結構化拓撲（Decentralized Unstructured Topology）；全分布式結構化拓撲（Decentralized Structured Topology，也稱作DHT網絡）和半分布式拓撲（Partially Decentralized Topology）。

其中，中心化拓撲最大的優點是維護簡單發現效率高。由于資源的發現依賴中心化的目錄系統，發現算法靈活高效并能夠實現復雜查詢。最大的問題與傳統客戶機/服務器結構類似，容易造成單點故障，訪問的“熱點”現象和法律等相關問題，這是第一代P2P網絡采用的結構模式，經典案例就是著名的MP3共享軟件Napster。

Napster是最早出現的P2P系統之一，并在短期內迅速成長起來。Napster實質上并非是純粹的P2P系統，它通過一個中央服務器保存所有Napster用戶上傳的音樂文件索引和存放位置的信息。當某個用戶需要某個音樂文件時，首先連接到Napster服務器，在服務器進行檢索，并由服務器返回存有該文件的用戶信息；再由請求者直接連到文件的所有者傳輸文件。

Napster首先實現了文件查詢與文件傳輸的分離，有效地節省了中央服務器的帶寬消耗，減少了系統的文件傳輸延時。這種方式最大的隱患在中央服務器上，如果該服務器失效，整個系統都會癱瘓。當用戶數量增加到10⁵或者更高時，Napster的系統性能會大大下降。另一個問題在于安全性上，Napster并沒有提供有效的安全機制。

在Napster 模型中，一群高性能的中央服務器保存著網絡中所有活動對等計算機共享資源的目錄信息。當需要查詢某個文件時，對等機會向一臺中央服務器發出文件查詢請求。中央服務器進行相應的檢索和查詢后，會返回符合查詢要求的對等機地址信息列表。查詢發起對等機接收到應答后，會根據網絡流量和延遲等信息進行選擇，和合適的對等機建立連接，并開始文件傳輸。Napster的工作原理如圖1所示。

這種對等網絡模型存在很多問題，主要表現為：

(1)中央服務器的癱瘓容易導致整個網絡的崩饋，可靠性和安全性較低。

(2)隨著網絡規模的擴大，對中央索引服務器進行維護和更新的費用將急劇增加，所需成本過高。

(3)中央服務器的存在引起共享資源在版權問題上的糾紛，并因此被攻擊為非純粹意義上的P2P網絡模型。對小型網絡而言，集中目錄式模型在管理和控制方面占一定優勢。但鑒于其存在的種種缺陷，該模型并不適合大型網絡應用。

Napster結構	Napster界面

全分布非結構化網絡在重疊網絡（overlay）采用了隨機圖的組織方式，結點度數服從"Power-law"[a][b]規律，從而能夠較快發現目的結點，面對網絡的動態變化體現了較好的容錯能力，因此具有較好的可用性。同時可以支持復雜查詢，如帶有規則表達式的多關鍵詞查詢，模糊查詢等，最典型的案例是Gnutella。

Gnutella是一個P2P文件共享系統，它和Napster最大的區別在于Gnutella是純粹的P2P系統，沒有索引服務器，它采用了基于完全隨機圖的洪泛（Flooding）發現和隨機轉發（Random Walker）機制。為了控制搜索消息的傳輸，通過TTL (Time To Live)的減值來實現。具體協議參照［Gnutella協議中文版］

在Gnutella分布式對等網絡模型N中，每一個聯網計算機在功能上都是對等的，既是客戶機同時又是服務器，所以被稱為對等機(Servent，Server+Client的組合)。

隨著聯網節點的不斷增多，網絡規模不斷擴大，通過這種洪泛方式定位對等點的方法將造成網絡流量急劇增加，從而導致網絡中部分低帶寬節點因網絡資源過載而失效。所以在初期的Gnutella網絡中，存在比較嚴重的分區，斷鏈現象。也就是說，一個查詢訪問只能在網絡的很小一部分進行，因此網絡的可擴展性不好。所以，解決Gnutella網絡的可擴展性對該網絡的進一步發展至關重要。

由于沒有確定拓撲結構的支持，非結構化網絡無法保證資源發現的效率。即使需要查找的目的結點存在發現也有可能失敗。由于采用TTL（Time-to-Live）、洪泛（Flooding）、隨機漫步或有選擇轉發算法，因此直徑不可控，可擴展性較差。

因此發現的準確性和可擴展性是非結構化網絡面臨的兩個重要問題。目前對此類結構的研究主要集中于改進發現算法和復制策略以提高發現的準確率和性能。

最初的Gnutella采用的Flooding搜索算法示意圖	采用第二代Gnutella協議最經典的軟件-Bearshare

由于非結構化網絡將重疊網絡認為是一個完全隨機圖，結點之間的鏈路沒有遵循某些預先定義的拓撲來構建。這些系統一般不提供性能保證，但容錯性好，支持復雜的查詢，并受結點頻繁加入和退出系統的影響小。但是查詢的結果可能不完全，查詢速度較慢，采用廣播查詢的系統對網絡帶寬的消耗非常大，并由此帶來可擴展性差等問題。

另外，由于非結構化系統中的隨機搜索造成的不可擴展性，大量的研究集中在如何構造一個高度結構化的系統。目前研究的重點放在了如何有效地查找信息上，最新的成果都是基于DHT的分布式發現和路由算法。這些算法都避免了類似Napster的中央服務器，也不是像Gnutella那樣基于廣播進行查找，而是通過分布式散列函數，將輸入的關鍵字惟一映射到某個結點上，然后通過某些路由算法同該結點建立連接。

最新的研究成果體現在采用分布式散列表（DHT）[a]的完全分布式結構化拓撲網絡。

分布式散列表（DHT）實際上是一個由廣域范圍大量結點共同維護的巨大散列表。散列表被分割成不連續的塊，每個結點被分配給一個屬于自己的散列塊，并成為這個散列塊的管理者。DHT的結點既是動態的結點數量也是巨大的，因此非中心化和原子自組織成為兩個設計的重要目標。通過加密散列函數，一個對象的名字或關鍵詞被映射為128位或160位的散列值。一個采用DHT的系統內所有結點被映射到一個空間，如果散列函數映射一個位的名字到一個散列值，則有。

分布式散列表起源于SDDS（Scalable Distribute Data Structures）[a]研究，Gribble等實現了一個高度可擴展，容錯的SDDS集群。

最近的研究集中在采用新的拓撲圖構建重疊路由網絡，以減少路由表容量和路由延時。這些新的拓撲關系的基本原理是在DHT表一維空間的基礎上引入更多的拓撲結構圖來反映底層網絡的結構。

DHT類結構能夠自適應結點的動態加入/退出，有著良好的可擴展性、魯棒性、結點ID分配的均勻性和自組織能力。由于重疊網絡采用了確定性拓撲結構，DHT可以提供精確的發現。只要目的結點存在于網絡中DHT總能發現它，發現的準確性得到了保證，最經典的案例是Tapestry，Chord,CAN,和Pastry。

Tapestry提供了一個分布式容錯查找和路由基礎平臺，在此平臺基礎之上，可以開發各種P2P應用(OceanStore即是此平臺上的一個應用)?。Tapestry的思想來源于Plaxton。在Plaxton中，結點使用自己所知道的鄰近結點表，按照目的ID來逐步傳遞消息。Tapestry基于Plaxtion的思想，加入了容錯機制，從而可適應P2P的動態變化的特點。OceanStore是以Tapestry為路由和查找基礎設施的P2P平臺。它是一個適合于全球數據存儲的P2P應用系統。任何用戶均可以加入OceanStore系統，或者共享自己的存儲空間，或者使用該系統中的資源。通過使用復制和緩存技術，OceanStore可提高查找的效率。最近，Tapstry為適應P2P網絡的動態特性，作了很多改進，增加了額外的機制實現了網絡的軟狀態（soft state），并提供了自組織、魯棒性、可擴展性和動態適應性，當網絡高負載且有失效結點時候性能有限降低，消除了對全局信息的依賴、根結點易失效和彈性（resilience）差的問題。

Pastry是微軟研究院提出的可擴展的分布式對象定位和路由協議，可用于構建大規模的P2P系統。在Pastry中，每個結點分配一個128位的結點標識符號(nodeID)?，所有的結點標識符形成了一個環形的nodeID空間，范圍從0到2¹²⁸?- 1?，結點加入系統時通過散列結點IP地址在128位nodeID空間中隨機分配。

在MIT，開展了多個與P2P相關的研究項目：Chord，GRID和RON。Chord項目的目標是提供一個適合于P2P環境的分布式資源發現服務，它通過使用DHT技術使得發現指定對象只需要維護O(logN)長度的路由表。

在DHT技術中，網絡結點按照一定的方式分配一個唯一結點標識符(Node ID)?，資源對象通過散列運算產生一個唯一的資源標識符(Object ID)?，且該資源將存儲在結點ID與之相等或者相近的結點上。需要查找該資源時，采用同樣的方法可定位到存儲該資源的結點。因此，Chord的主要貢獻是提出了一個分布式查找協議，該協議可將指定的關鍵字(Key)?映射到對應的結點(Node)?。從算法來看，Chord是相容散列算法的變體。MIT的GRID和RON項目則提出了在分布式廣域網中實施查找資源的系統框架。

AT&T ACIRI中心的CAN(Content Addressable Networks)?項目獨特之處在于采用多維的標識符空間來實現分布式散列算法。CAN將所有結點映射到一個n維的笛卡爾空間中，并為每個結點盡可能均勻的分配一塊區域。CAN采用的散列函數通過對(key, value)?對中的key進行散列運算，得到笛卡爾空間中的一個點，并將(key, value)?對存儲在擁有該點所在區域的結點內。CAN采用的路由算法相當直接和簡單，知道目標點的坐標后，就將請求傳給當前結點四鄰中坐標最接近目標點的結點。CAN是一個具有良好可擴展性的系統，給定N個結點，系統維數為d，則路由路徑長度為O(n^1/d)?，每結點維護的路由表信息和網絡規模無關為O(d)?。

DHT類結構最大的問題是DHT的維護機制較為復雜，尤其是結點頻繁加入退出造成的網絡波動（Churn）會極大增加DHT的維護代價。DHT所面臨的另外一個問題是DHT僅支持精確關鍵詞匹配查詢，無法支持內容/語義等復雜查詢。

Chord的Identifier Circle	Pastry的消息路由

半分布式結構（有的文獻稱作 Hybrid Structure）吸取了中心化結構和全分布式非結構化拓撲的優點，選擇性能較高（處理、存儲、帶寬等方面性能）的結點作為超級點（英文文獻中多稱作：SuperNodes, Hubs)，在各個超級點上存儲了系統中其他部分結點的信息，發現算法僅在超級點之間轉發，超級點再將查詢請求轉發給適當的葉子結點。半分布式結構也是一個層次式結構，超級點之間構成一個高速轉發層，超級點和所負責的普通結點構成若干層次。最典型的案例就是KaZaa。

KaZaa是現在全世界流行的幾款p2p軟件之一。根據CA公司統計，全球KaZaa的下載量超過2.5億次。使用KaZaa軟件進行文件傳輸消耗了互聯網40%的帶寬。之所以它如此的成功，是因為它結合了Napster和Gnutella共同的優點。從結構?上來說，它使用了Gnutella的全分布式的結構，這樣可以是系統更好的擴展，因為它無需中央索引服務器存儲文件名，它是自動的把性能好的機器成為SuperNode，它存儲著離它最近的葉子節點的文件信息，這些SuperNode,再連通起來形成一個Overlay Network.?由于SuperNode的索引功能，使搜索效率大大提高。

半分布式結構（含有SuperNode）	kaZaa界面

半分布式結構的優點是性能、可擴展性較好，較容易管理，但對超級點依賴性大，易于受到攻擊，容錯性也受到影響。下表比較了4種結構的綜合性能，比較結果如表1-1所示。

表1：4種結構的性能比較

　

比較標準／拓撲結構	中心化拓撲	全分布式非結構化拓撲	全分布式結構化拓撲	半分布式拓撲
可擴展性	差	差	好	中
可靠性	差	好	好	中
可維護性	最好	最好	好	中
發現算法效率	最高	中	高	中
復雜查詢	支持	支持	不支持	支持

1.2.2?國內的P2P研究現狀

學術機構研發

• 北京大學—Maze

　　　Maze 是北京大學網絡實驗室開發的一個中心控制與對等連接相融合的對等計算文件共享系統，在結構上類似Napster，對等計算搜索方法類似于 Gnutella。網絡上的一臺計算機，不論是在內網還是外網，可以通過安裝運行Maze的客戶端軟件自由加入和退出Maze系統。每個節點可以將自己的一個或多個目錄下的文件共享給系統的其他成員，也可以分享其他成員的資源。Maze支持基于關鍵字的資源檢索，也可以通過好友關系直接獲得。

• 清華大學—Granary

　　　Granary是清華大學自主開發的對等計算存儲服務系統。它以對象格式存儲數據。另外，Granary設計了專門的結點信息收集算法PeerWindow的結構化覆蓋網絡路由協議Tourist。

• 華中科技大學—AnySee

　　　AnySee是華中科大設計研發的視頻直播系統。它采用了一對多的服務模式，支持部分NAT和防火墻的穿越，提高了視頻直播系統的可擴展性；同時，它利用近播原則、分域調度的思想，使用Landmark路標算法直接建樹的方式構建應用層上的組播樹，克服了ESM等一對多模式系統由聯接圖的構造和維護帶來的負載影響。?

　　更詳細介紹見［中國計算機學會通訊　Page 38-51　鄭緯民等　對等計算研究概論］

企業研發產品

• 廣州數聯軟件技術有限公司-Poco

??? POCO 是中國最大的 P2P用戶分享平臺 , 是有安全、流量控制力的，無中心服務器的第三代 P2P 資源交換平臺 , 也是世界范圍內少有的盈利的 P2P 平臺。目前已經形成了 2600 萬海量用戶，平均在線 58.5 萬，在線峰值突破 71 萬，并且全部是寬帶用戶的用戶群。 成為中國地區第一的 P2P 分享平臺。[a]

• 深圳市點石軟件有限公司-OP

???? OP-又稱為Openext Media Desktop，一個網絡娛樂內容平臺，Napster的后繼者，它可以最直接的方式找到您想要的音樂、影視、軟件、游戲、圖片、書籍以及各種文檔，隨時在線共享文件容量數以億計“十萬影視、百萬音樂、千萬圖片”。OP整合了Internet Explorer、Windows Media Player、RealOne Player和ACDSee ，是國內的網絡娛樂內容平臺。[a]

• 基于P2P的在線電視直播-PPLive

??? PPLive是一款用于互聯網上大規模視頻直播的共享軟件。它使用網狀模型，有效解決了當前網絡視頻點播服務的帶寬和負載有限 問題，實現用戶越多，播放越流暢的特性，整 體服務質量大大提高！（2005年的超級女聲決賽期間，這款軟件非常的火爆，同時通過它看湖南衛視的有上萬觀眾）

?? 其他商業軟件這里不一一列舉，請訪問P2P門戶網站?http://www.ppcn.net/

1.2.3 P2P技術的應用研究

　　國外開展P2P研究的學術團體主要包括P2P工作組(P2PWG)^?、全球網格論壇(Global Grid Forum?，GGF)^?。P2P工作組成立的主要目的是希望加速P2P計算基礎設施的建立和相應的標準化工作。P2PWG成立之后，對P2P計算中的術語進行了統一，也形成相關的草案，但是在標準化工作方面工作進展緩慢。目前P2PWG已經和GGF合并，由該論壇管理P2P計算相關的工作。GGF負責網格計算和P2P計算等相關的標準化工作。

從國外公司對P2P計算的支持力度來看，Microsoft公司、Sun公司和Intel公司投入較大。Microsoft公司成立了Pastry項目組，主要負責P2P計算技術的研究和開發工作。目前Microsoft公司已經發布了基于Pastry的軟件包SimPastry/ VisPastry。Rice大學也在Pastry的基礎之上發布了FreePastry軟件包。

在2000年8月，Intel公司宣布成立P2P工作組，正式開展P2P的研究。工作組成立以后，積極與應用開發商合作，開發P2P應用平臺。2002年Intel發布了. Net基礎架構之上的Accelerator Kit (P2P加速工具包)?和P2P安全API軟件包，從而使得微軟. NET開發人員能夠迅速地建立P2P安全Web應用程序。

Sun公司以Java技術為背景，開展了JXTA項目。JXTA是基于Java的開源P2P平臺，任何個人和組織均可以加入該項目。因此，該項目不僅吸引了大批P2P研究人員和開發人員，而且已經發布了基于JXTA的即時聊天軟件包。JXTA定義了一組核心業務：認證、資源發現和管理。在安全方面，JXTA加入了加密軟件包，允許使用該加密包進行數據加密，從而保證消息的隱私、可認證性和完整性。在JXTA核心之上，還定義了包括內容管理、信息搜索以及服務管理在內的各種其它可選JXTA服務。在核心服務和可選服務基礎上，用戶可以開發各種JXTA平臺上的P2P應用。

P2P實際的應用主要體現在以下幾個方面：

P2P分布式存儲

P2P分布式存儲系統是一個用于對等網絡的數據存儲系統，它可以提供高效率的、魯棒的和負載平衡的文件存取功能。這些研究包括：OceanStore，Farsite等。其中，基于超級點結構的半分布式P2P應用如Kazza、Edonkey、Morpheus、Bittorrent等也是屬于分布式存儲的范疇，并且用戶數量急劇增加。

計算能力的共享

加入對等網絡的結點除了可以共享存儲能力之外，還可以共享CPU處理能力。目前已經有了一些基于對等網絡的計算能力共享系統。比如SETI@home?。目前SETI@home?采用的仍然是類似于Napster的集中式目錄策略。Xenoservers向真正的對等應用又邁進了一步。這種計算能力共享系統可以用于進行基因數據庫檢索和密碼破解等需要大規模計算能力的應用。

P2P應用層組播。

應用層組播，就是在應用層實現組播功能而不需要網絡層的支持。這樣就可以避免出現由于網絡層遲遲不能部署對組播的支持而使組播應用難以進行的情況。應用層組播需要在參加的應用結點之間實現一個可擴展的，支持容錯能力的重疊網絡，而基于DHT的發現機制正好為應用層組播的實現提供了良好的基礎平臺。

Internet間接訪問基礎結構（Internet Indirection Infrastructure）。

為了使Internet更好地支持組播、單播和移動等特性，Internet間接訪問基礎結構提出了基于匯聚點的通信抽象。在這一結構中，并不把分組直接發向目的結點，而是給每個分組分配一個標識符，而目的結點則根據標識符接收相應的分組。標識符實際上表示的是信息的匯聚點。目的結點把自己想接收的分組的標識符預先通過一個觸發器告訴匯聚點，當匯聚點收到分組時，將會根據觸發器把分組轉發該相應的目的結點。Internet間接訪問基礎結構實際上在Internet上構成了一個重疊網絡，它需要對等網絡的路由系統對它提供相應的支持。

P2P技術從出現到各個領域的應用展開，僅用了幾年的時間。從而證明了P2P技術具有非常廣闊的應用前景。

　

1.3　對研究內容有重大影響的幾個方面

　　隨著P2P應用的蓬勃發展，作為P2P應用中核心問題的發現技術除了遵循技術本身的邏輯以外，也受到某些技術的發展趨勢、需求趨勢的深刻影響。　

1.3.1　度數和直徑的折衷關系（tradeoff）對發現算法的影響

　　如上所述，DHT發現技術完全建立在確定性拓撲結構的基礎上，從而表現出對網絡中路由的指導性和網絡中結點與數據管理的較強控制力。但是，對確定性結構的認識又限制了發現算法效率的提升。研究分析了目前基于DHT的發現算法，發現衡量發現算法的兩個重要參數度數（表示鄰居關系數、路由表的容量）和鏈路長度（發現算法的平均路徑長度）之間存在漸進曲線的關系。

　　研究者采用圖論中度數(Degree)和直徑(Diameter)兩個參數研究DHT發現算法，發現這些DHT發現算法在度數和直徑之間存在漸進曲線關系，如下圖所示。在N個結點網絡中，圖中直觀顯示出當度數為N時，發現算法的直徑為O(1)；當每個結點僅維護一個鄰居時，發現算法的直徑為O(N)。這是度數和直徑關系的2種極端情況。同時，研究以圖論的理論分析了O(d)的度和O(d)的直徑的算法是不可能的。

度數和直徑之間的漸進曲線關系

從漸進曲線關系可以看出，如果想獲得更短的路徑長度，必然導致度數的增加；而網絡實際連接狀態的變化造成大度數鄰居關系的維護復雜程度增加。另外，研究者證明O(logN)甚至O(logN/loglogN)的平均路徑長度也不能滿足狀態變化劇烈的網絡應用的需求。新的發現算法受到這種折衷關系制約的根本原因在于DHT對網絡拓撲結構的確定性認識。

1.3.2 Small world?理論對P2P發現技術的影響

?? 非結構化P2P系統中發現技術一直采用洪泛轉發的方式，與DHT的啟發式發現算法相比，可靠性差，對網絡資源的消耗較大。最新的研究從提高發現算法的可靠性和尋找隨機圖中的最短路徑兩個方面展開。也就是對重疊網絡的重新認識。其中，small world特征和冪規律證明實際網絡的拓撲結構既不是非結構化系統所認識的一個完全隨機圖，也不是DHT發現算法采用的確定性拓撲結構。

? 實際網絡體現的冪規律分布的含義可以簡單解釋為在網絡中有少數結點有較高的“度”，多數結點的“度”較低。度較高的結點同其他結點的聯系比較多，通過它找到待查信息的概率較高。

? Small-world[a][b]模型的特性：網絡拓撲具有高聚集度和短鏈的特性。在符合small world特性的網絡模型中，可以根據結點的聚集度將結點劃分為若干簇(Cluster)，在每個簇中至少存在一個度最高的結點為中心結點。大量研究證明了以Gnutella為代表的P2P網絡符合small world特征，也就是網絡中存在大量高連通結點，部分結點之間存在“短鏈”現象。

因此，P2P發現算法中如何縮短路徑長度的問題變成了如何找到這些“短鏈”的問題。尤其是在DHT發現算法中，如何產生和找到“短鏈”是發現算法設計的一個新的思路。small world特征的引入會對P2P發現算法產生重大影響。

1.3.3?語義查詢和DHT的矛盾

?? 現有DHT算法由于采用分布式散列函數，所以只適合于準確的查找，如果要支持目前Web上搜索引擎具有的多關鍵字查找的功能，還要引入新的方法。主要的原因在于DHT的工作方式。

?? 基于DHT的P2P系統采用相容散列函數根據精確關鍵詞進行對象的定位與發現。散列函數總是試圖保證生成的散列值均勻隨機分布，結果兩個內容相似度很高但不完全相同的對象被生成了完全不同的散列值，存放到了完全隨機的兩個結點上。因此，DHT可以提供精確匹配查詢，但是支持語義是非常困難的。

?? 目前在DHT基礎上開展帶有語義的資源管理技術的研究還非常少。由于DHT的精確關鍵詞映射的特性決定了無法和信息檢索等領域的研究成果結合，阻礙了基于DHT的P2P系統的大規模應用。[a]

1.4 P2P發現技術研究的成果與不足

　　P2P發現技術中最重要的研究成果應該是基于small world理論的非結構化發現算法和基于DHT的結構化發現算法。尤其是DHT及其發現技術為資源的組織與查找提供了一種新的方法。

隨著P2P系統實際應用的發展，物理網絡中影響路由的一些因素開始影響P2P發現算法的效率。一方面，實際網絡中結點之間體現出較大的差異，即異質性。由于客戶機/服務器模式在Internet和分布式領域十幾年的應用和大量種類的電子設備的普及，如手提電腦、移動電話或PDA。這些設備在計算能力、存儲空間和電池容量上差別很大。另外，實際網絡被路由器和交換機分割成不同的自治區域，體現出嚴密的層次性。

另一方面，網絡波動的程度嚴重影響發現算法的效率。網絡波動（Churn、fluctuation of network）包括結點的加入、退出、失敗、遷移、并發加入過程、網絡分割等。DHT的發現算法如Chord、CAN、Koorde等都是考慮網絡波動的最差情況下的設計與實現。由于每個結點的度數盡量保持最小，這樣需要響應的成員關系變化的維護可以比較小，從而可以快速恢復網絡波動造成的影響。但是每個結點僅有少量路由狀態的代價是發現算法的高延時，因為每一次查找需要聯系多個結點，在穩定的網絡中這種思路是不必要的。

同時，作為一種資源組織與發現技術必然要支持復雜的查詢，如關鍵詞、內容查詢等。盡管信息檢索和數據挖掘領域提供了大量成熟的語義查詢技術，由于DHT精確關鍵詞映射的特性阻礙了DHT在復雜查詢方面的應用。

2復雜P2P網絡拓撲模型

2.1 Internet拓撲模型

Internet作為當今人類社會信息化的標志,其規模正以指數速度高速增長.如今Internet的“面貌”已與其原型ARPANET大相徑庭,依其高度的復雜性,可以將其看作一個由計算機構成的“生態系統”.雖然Internet是人類親手建造的,但卻沒有人能說出這個龐然大物看上去到底是個什么樣子,運作得如何.Internet拓撲建模研究就是探求在這個看似混亂的網絡之中蘊含著哪些還不為我們所知的規律.發現Internet拓撲的內在機制是認識Internet的必然過程,是在更高層次上開發利用Internet的基礎.然而,Internet與生俱來的異構性動態性發展的非集中性以及如今龐大的規模都給拓撲建模帶來巨大挑戰.Internet拓撲建模至今仍然是一個開放性問題,在計算機網絡研究中占有重要地位.

Internet拓撲作為Internet這個自組織系統的“骨骼”,與流量協議共同構成模擬Internet的3個組成部分,即在拓撲網絡中節點間執行協議,形成流量.Internet拓撲模型是建立Internet系統模型的基礎,由此而體現的拓撲建模意義也可以說就是Internet建模的意義,即作為一種工具,人們用其來對Internet進行分析預報決策或控制.Internet模型中的拓撲部分刻畫的是Internet在宏觀上的特征,反映一種總體趨勢,所以其應用也都是在大尺度上展開的.對Internet拓撲模型的需求主要來自以下幾個方面:(1)?許多新應用或實驗不適合直接應用于Internet,其中一些具有危害性,如蠕蟲病毒在大規模網絡上的傳播模擬;(2)?對于一些依賴于網絡拓撲的協議(如多播協議),在其研發階段,當前Internet拓撲只能提供一份測試樣本,無法對協議進行全面評估,需要提供多個模擬拓撲環境來進行實驗;(3)?從國家安全角度考慮,需要在線控制網絡行為,如美國國防高級研究計劃局(DARPA)的NMS(network modeling and simulation)項目.

2.1.1隨機網絡與拓撲模型

隨機網絡是由N個頂點構成的圖中，可以存在條邊，我們從中隨機連接M條邊所構成的網絡。還有一種生成隨機網絡的方法是，給一個概率p，對于中任何一個可能連接，我們都嘗試一遍以概率p的連接。如果我們選擇M?=?p，這兩種隨機網絡模型就可以聯系起來。對于如此簡單的隨機網絡模型，其幾何性質的研究卻不是同樣的簡單。隨機網絡幾何性質的研究是由Paul，Alfréd Rényi和Béla Bollobás在五十年代到六十年代之間完成的。隨機網絡在Internet的拓撲中占有很重要的位置。

2.1.2隨機網絡參數

描述隨機網絡有一些重要的參數。一個節點所擁有的度是該節點與其他節點相關聯的邊數，度是描述網絡局部特性的基本參數。網絡中并不是所有節點都具有相同的度，系統中節點度的分布情況，可以用分布函數描述，度分布函數反映了網絡系統的宏觀統計特征。理論上利用度分布可以計算出其他表征全局特性參數的量化數值。

聚集系數是描述與第三個節點連接的一對節點被連接的概率。從連接節點的邊的意義上，若為第i個節點的度，在由k.個近鄰節點構成的子網中，實際存在的邊數E(i)與全部k.個節點完全連接時的總邊數充的比值定義為節點i的聚集系數

?

　

2.1.3拓撲模型

Internet拓撲模型可分為兩類:一類是描述Internet拓撲特征,包括Waxman模型,Tiers,Transit -Stub和冪律;另一類是描述拓撲特征形成的機理,包括Barabási與Albert提出的BA和ESF以及一種改進模型GLP.由于后一類模型對Internet冪律形成機理的描述還不成熟,更多的是作為一種產生冪律的圖生成算法。對于第1類模型來說,Internet拓撲特征的發現,實際上就是刻畫該特征的度量(metric)的發現.一個屬于第一類的拓撲模型就是包含若干已存在的或新發現的度量,然后根據實際的Internet拓撲數據求出這些度量的值.因此,對這類模型進行評價需要從兩方面入手:一方面,對它所采用的拓撲數據進行評價;另一方面,對其度量進行評價.在所有已經發現的Internet拓撲度量中,最為基本的就是節點出度頻率fd.其分布是判斷一幅拓撲圖是否與Internet拓撲相類似的最重要的依據.在研究早期,研究人員或者認為Internet節點出度是完全隨機的(如Waxman模型),或者認為節點出度是正規的(如Tiers模型).而冪律的發現證明了Internet拓撲結構介于兩者之間,呈冪率分布.根據對出度頻率分布的刻畫,可將Internet拓撲模型分為以下3類:

(1)?隨機型,即認為Internet拓撲圖處于一個完全無序的狀態,在大尺度上是均一的.Waxman模型，是一種類似于Erds-Rényi模型的隨機模型,出度頻率呈泊松分布.這個模型有兩個版本:RG1,先將節點隨機布置在直角坐標網格中,節點間的距離就是其歐幾里德距離;RG2,依據(0,L)均勻隨機分布為節點對指定距離.兩個版本中,節點間相接的概率P(u,v)與其距離相關,服從泊松分布,距離越近,概率越大.

其中,d(u,v)表示節點u與v之間的距離,L為節點間最長距離,á與a取值范圍是(0,1).

(2)?層次型,來自對Internet結構所具有的層次特征的認識,在同一層上的節點出度接近,不同層間節點出度差別很大.對同一層上的節點布置借用Waxman模型方法.Tiers(等級)模型將Internet劃分為LAN(局域網),MAN(城域網)和WAN(廣域網)3個層次.在該模型中,WAN只有一個,通過指定LAN和MAN數量以及各自內部所包含節點的數量來構造拓撲圖.Transit-Stub模型將AS域劃分為Transit類和Stub類.在該模型中,Transit節點彼此互聯構成一個節點群,一個或多個Transit節點群構成拓撲圖的核心,而Stub節點分布在Transit節點群四周與Transit節點相連.Transit -Stub是GT-ITM(georgia tech Internetwork topology models)軟件包的一部分,有時GT-ITM也就是指Transit-Stub模型.

(3)?冪率型.1999年,Faloutsos等人對NLANR(National Lab for Applied Network Research)在1997~1998年間的3份BGP數據以及1995年的一份traceroute測量數據進行分析,發現Internet拓撲中存在著4條冪律.

冪律是指形如的方程,對于兩個變量X和Y,存在一個常數C,使得Y與X的C次冪成比例.有兩個聲明:(1)?節點v的等級為,v是在按出度降序排列序列中的索引值;(2)?鄰接矩陣特征值按降序排列,第i個特征值為li.冪律1(等級指數R):節點出度dv與該節點等級rv的R次冪成比例.冪律2(出度指數O):出度頻率fd與該出度d的O次冪成比例.

近似冪律(hop-plot指數H):h跳內節點對(pairs of nodes)的數量與h的H次冪成比例.冪律3(特征指數E):特征值li與其次序i的E次冪成比例.

　

2.2 Small World網絡

在現實的Internet環境中，網絡拓撲并不完全滿足隨機網絡拓撲。Watt和Strogatz發現，只需要在規則網絡上稍作隨機改動就可以同時具備以上兩個性質。改動的方法是，對于規則網絡的每一個頂點的所有邊，以概率p斷開一個端點，并重新連接，連接的新的端點從網絡中的其他頂點里隨機選擇，如果所選的頂點已經與此頂點相連，則再隨機選擇別的頂點來重連。當p?= 0時就是規則網絡，p?= 1則為隨機網絡，對于0 <?p?< 1的情況，存在一個很大的p的區域，同時擁有較大的集聚程度和較小的最小距離。Small World網絡的幾何性質如圖所示。

p值不同的small world網絡

(1)平均路徑。圖中被隨機選擇又重新連結后的線稱為捷徑，它對整個網絡的平均路徑有著很大影響，分析表明:當p>=21(NK)，即在保證系統中至少出現一條捷徑的情況下，系統的平均路徑開始下降。即使是相當少的捷徑也能夠顯著地減小網絡的平均路徑長度。這是因為每出現一條捷徑，它對整個系統的影響是非線性的，它不僅影響到被這條線直接連著的兩點，也影響到了這兩點的最近鄰、次近鄰，以及次次近鄰等。

(2) WS網絡的集團系數。r1初始固定的節點數可計算t1{ p=0時規則網絡的聚集系數為C(0), C(0)取決于網絡結構而與尺寸N無關，因此有相對較大的值。隨著邊按一定的概率p隨機化，聚集系數在CYO}的附近變化。

(3)度分布。WS模型是介于規則網絡和隨機網絡

總結

以上是生活随笔為你收集整理的Peer to Peer ( P2P ) 综述的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。