P2P網絡的拓撲結構

拓撲結構是指分布式系統中各個計算單元之間的物理或邏輯的互聯關系，結點之間的拓撲結構一直是確定系統類型的重要依據。目前互聯網絡中廣泛使用集中式、層次式等拓撲結構。Internet本身是世界上最大的非集中式的互聯網絡，但是九十年代所建立的一些網絡應用系統卻是完全的集中式的系統，許多Web應用都是運行在集中式的服務器系統上。集中式拓撲結構系統目前面臨著過量存儲負載、DOS（Denial of Service，拒絕服務）攻擊，網絡帶寬限制等一些難以解決的問題。Peer-to-Peer (簡稱P2P) 系統主要采用非集中式的拓撲結構，一般來說不存在上述這些難題。根據結構關系可以將P2P系統細分為四種拓撲形式：

• 中心化拓撲（Centralized Topology）；
• 全分布式非結構化拓撲（Decentralized Unstructured Topology）；
• 全分布式結構化拓撲（Decentralized Structured Topology，也稱作DHT網絡）；
• 半分布式拓撲（Partially Decentralized Topology）。

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

Napster是最早出現的P2P系統之一，并在短期內迅速成長起來。它實質上并非是純粹的P2P系統，而是通過一個中央索引服務器保存所有Napster用戶上傳的音樂文件索引和存放位置的信息。它的工作原理如圖1所示。當某個用戶需要某個音樂文件時，首先連接到Napster中央索引服務器，在服務器上進行檢索，服務器返回存有該文件的用戶信息，再由請求者直接連到文件的所有者傳輸文件。Napster首先實現了文件查詢與文件傳輸的分離，有效地節省了中央服務器的帶寬消耗，減少了系統的文件傳輸延時。

圖1 Napster的拓撲結構

然而，這種對等網絡模型存在以下這些問題：

• 中央索引服務器的癱瘓容易導致整個網絡的崩潰，因此可靠性和安全性較低。
• 隨著網絡規模的擴大，對中央索引服務器進行維護和更新的費用將急劇增加，所需成本較高。
• 中央索引服務器的存在常引起版權問題上的糾紛，服務提供商容易被追究法律責任。

綜合上述優缺點，對小型網絡而言，中心化拓撲模型在管理和控制方面占一定優勢。但鑒于其存在的上述缺陷，該模型并不適合大型網絡應用。

全分布式非結構化拓撲的P2P網絡是在重疊網絡（Overlay Network）(見標注1)采用了隨機圖的組織方式，結點度數服從Power-law規律（冪次法則）[2]，從而能夠較快發現目的結點，面對網絡的動態變化體現了較好的容錯能力，因此具有較好的可用性。同時可以支持復雜查詢，如帶有規則表達式的多關鍵詞查詢，模糊查詢等，采用這種拓撲結構最典型的案例便是Gnutella（音譯：紐特拉）。準確地說，Gnutella不是特指某一款軟件，而是指遵守Gnutella協議[3]的網絡以及客戶端軟件的統稱。目前基于Gnutella網絡的客戶端軟件非常多，著名的有Shareaza、LimeWire和BearShare等。

圖2Gnutella的拓撲結構和文件檢索方法

Gnutella和Napster最大的區別在于Gnutella是更加純粹的P2P系統，因為它沒有中央索引服務器，每臺機器在Gnutella網絡中是真正的對等關系，既是客戶機同時又是服務器，所以被稱為對等機(Servent，Server+Client的組合)。在文件檢索方面，它與Napster也不相同。在Gnutella網絡的發展初期，它主要采用基于完全隨機圖的Flooding搜索算法。圖2 顯示了Flooding的工作流程：當一臺計算機要下載一個文件，它首先以文件名或者關鍵字生成一個查詢，并把這個查詢發送給與它相連的所有計算機，這些計算機如果存在這個文件，則與查詢的機器建立連接，如果不存在這個文件，則繼續在自己相鄰的計算機之間轉發這個查詢，直到找到文件為止。為了控制搜索消息不至于永遠這樣傳遞下去，一般通過TTL (Time To Live)的減值來控制查詢的深度。

但是，隨著聯網節點的不斷增多，網絡規模不斷擴大，通過這種Flooding方式定位對等點的方法將造成網絡流量急劇增加，從而導致網絡中部分低帶寬節點因網絡資源過載而失效。所以在初期的Gnutella網絡中，存在比較嚴重的分區，斷鏈現象。也就是說，一個查詢訪問只能在網絡的很小一部分進行，因此網絡的可擴展性不好。所以，后來許多研究人員在Flooding的基礎上作了許多改進，例如采用Random work [4]、Dynamic Query[5]等方法。

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

全分布式結構化拓撲的P2P網絡主要是采用分布式散列表（Distributed Hash Table, 簡寫成DHT）技術來組織網絡中的結點。DHT是一個由廣域范圍大量結點共同維護的巨大散列表。散列表被分割成不連續的塊，每個結點被分配給一個屬于自己的散列塊，并成為這個散列塊的管理者。通過加密散列函數，一個對象的名字或關鍵詞被映射為128位或160位的散列值。分布式散列表起源于SDDS（Scalable Distribute Data Structures）[6]研究，Gribble等實現了一個高度可擴展，容錯的SDDS集群。DHT類結構能夠自適應結點的動態加入/退出，有著良好的可擴展性、魯棒性、結點ID分配的均勻性和自組織能力。由于重疊網絡采用了確定性拓撲結構，DHT可以提供精確的發現。只要目的結點存在于網絡中DHT總能發現它，發現的準確性得到了保證，最經典的案例是Tapestry，Pastry，Chord和CAN。

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

Pastry 是微軟研究院提出的可擴展的分布式對象定位和路由協議，可用于構建大規模的P2P系統。如圖3 所示，在Pastry中，每個結點分配一個128位的結點標識符號(nodeID) ，所有的結點標識符形成了一個環形的nodeID空間，范圍從0到2128 - 1 ，結點加入系統時通過散列結點IP地址在128位nodeID空間中隨機分配。網絡結點的加入與退出，資源查詢的過程可以參考文獻[9]。

圖3Pastry的消息路由

Chord [10]項目誕生于美國的麻省理工學院。它的目標是提供一個適合于P2P環境的分布式資源發現服務，它通過使用DHT技術使得發現指定對象只需要維護O(logN)長度的路由表。在DHT技術中，網絡結點按照一定的方式分配一個唯一結點標識符(Node ID) ，資源對象通過散列運算產生一個唯一的資源標識符(Object ID) ，且該資源將存儲在結點ID與之相等或者相近的結點上。需要查找該資源時，采用同樣的方法可定位到存儲該資源的結點。因此，Chord的主要貢獻是提出了一個分布式查找協議，該協議可將指定的關鍵字(Key) 映射到對應的結點(Node) 。從算法來看，Chord是相容散列算法的變體。

圖4 Chord的拓撲形狀

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

上述四種基于DHT的P2P系統的性能比較可以參照[12]。DHT這類結構最大的問題是DHT的維護機制較為復雜，尤其是結點頻繁加入退出造成的網絡波動（Churn）會極大增加DHT的維護代價。DHT所面臨的另外一個問題是DHT僅支持精確關鍵詞匹配查詢，無法支持內容/語義等復雜查詢。

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

圖5 半分布式拓撲結構（網絡中包含Super Node）

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

圖6 KaZaa的軟件界面

半分布式結構的優點是性能、可擴展性較好，較容易管理，但對超級點依賴性大，易于受到攻擊，容錯性也受到影響。

在實際應用中，每種拓撲結構的P2P網絡都有其優缺點，下表從可擴展性、可靠性、可維護性、發現算法的效率、復雜查詢等方面比較了這四種拓撲結構的綜合性能。

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

我還是比較看好chord...雖然目前還有不少問題沒有解決....
順便附上一篇經典的chord論文: Chord: A Scalable Peertopeer Lookup Service for Internet Applications
http://www.aygfsteel.com/Files/heiyuchuanxia/chord_sigcomm.rar