淺析P2P系統的拓撲

宋靜靜

摘 要：Napster、Gnutella和Freenet等P2P系統的初始設計存在顯著的可擴展性問題。近年來，一些研究小組獨立地提出了新一代的感知拓撲P2P系統，以支持可擴展的路由和位置方案。隨著P2P體系結構的流行和越來越多的系統引入，我們認為有必要提出一個抽象的、通用的拓撲模型來捕捉P2P體系結構的本質。這種模式應該有助于為更新穎的P2P系統開發新的設計空間。

關鍵詞：P2P系統;覆蓋網絡;路由;定位算法

一、引言

互聯網的普及使得一個通用的存儲空間成為可能，它分布在互聯網上參與的終端計算機（對等機）上。所有對等方都具有相同的角色，并且空間中沒有集中式服務器。這種體系結構被統稱為對等（P2P）系統。盡管P2P系統僅僅在幾年前才被引入，但它現在已經成為最流行的互聯網應用之一，并成為互聯網流量的主要來源。它們的快速和廣泛的預部署表明P2P系統有其優勢。P2P文件共享可能會為軟件分發、分布式文件系統、搜索網絡和靜態Web內容交付等應用帶來新的內容分發模型，P2P系統最突出的初始設計包括Napster[1]、Gnutella[2]和freenet[3]。不幸的是，它們都有明顯的縮放問題。例如，在Napster中心服務器存儲Napster用戶社區中所有可用文件的索引。要檢索文件，用戶使用所需文件的已知名稱查詢此中心服務器，并獲取存儲所需文件的用戶計算機的IP地址。

一個可擴展的P2P文件分發系統可以做嗎？已經認識到，任何對等系統的中心是用于將文件名映射到系統中的位置的索引方案。也就是說，P2P文件傳輸過程本質上是可擴展的，但最困難的部分是從誰到誰中找到對等方來檢索文件。因此，一個可擴展的P2P系統至少需要一個查找索引機制。針對這些可擴展性問題，出現了支持可擴展路由和定位方案的第二代P2P系統。與前面的系統不同，它們保證在有限數量的網絡跳數中對查詢作出明確的回答，同時保持有限的路由信息量，其中包括Tapestry、Pastry、Chord和CAN。

通過進一步的研究，我們發現所有這些新一代P2P系統都有一個共同的特點，即節點在應用層上連接成一個有規則的網絡，例如一個環、一個網格或一個通常被稱為覆蓋網絡的超立方體。隨著P2P體系結構的日益流行和系統的不斷引入，我們認為需要一個抽象的、通用的拓撲模型來捕捉P2P體系結構的本質。這種模式應該反過來促進新的P2P系統設計空間的開發。

二、拓撲模型

在開發抽象模型時，我們做了兩個觀察。首先，在任何P2P系統中，我們可以看到有多個節點分布在整個互聯網上，并將其部分本地存儲貢獻給全局存儲空間。因特網可以被模擬成一個物理上連接這些節點的通用互連網絡。其次，我們注意到P2P系統中節點的主要功能除了存儲和緩存數據外，還包括消息路由和數據定位。路由功能在源節點和目標節點之間路由給定的請求/回復消息。數據定位試圖在路由表的幫助下找到數據項的位置或主節點。所有對等節點都以某種規則的方式以邏輯方式連接為一個覆蓋網絡，從而顯著地導出路由表大小和路由路徑。在這樣的系統中，路由表的條目（例如鄰居的IP地址）充當到其他相鄰節點的邏輯鏈路，因此被視為覆蓋網絡的邊緣。

覆蓋網絡的復雜性常常決定了可以構建的P2P系統的大小。同樣，P2P系統的可達到性能最終受到覆蓋網絡特性的限制。顯然，選擇覆蓋網絡是P2P系統設計的第一步，也是最關鍵的一步。

在我們定義并描述了以下術語之后，各組成部分將變得清晰：

數據ID和密鑰空間：為每個文件或數據分配一個密鑰或全局唯一標識，該標識對應于文件的文本名、所有者的公鑰/隨機的加密散列。注意，有序密鑰空間是覆蓋網絡的第一個必要特性。

節點ID：節點的標識符與文件的密鑰空間相同。它可以被計算為節點IP地址或公鑰的加密散列。

數據放置：數據ID和節點ID屬于同一空間。理想情況下，數據存儲在與數據ID具有相同ID的節點上，但活動節點或對等節點的數量通常比數據的數量少很多。每個節點負責在密鑰空間中存儲一定范圍的密鑰。數據存儲在最近的節點上，最近的ID為節點ID。

分布式哈希表：所有數據或節點通過哈希映射到同一個密鑰空間中的一個點。Hash的功能應該保證密鑰空間內數據或節點的均勻隨機分布。

覆蓋網絡：所有的活動對等節點通過路由表在應用層進行邏輯連接，每個路由表條目包含一個鄰居的IP地址，由于所有活動節點上的數據聯合應該覆蓋整個密鑰空間，因此邏輯連接的網絡稱為覆蓋網絡。任何傳統的互連網絡，如環網、網格網和超立方體，都不能直接用作覆蓋網絡。

路由表：每個節點維護由系統中的一小部分節點組成的路由表。由于所有對等節點都以某種規則的拓撲結構連接，因此路由表可以顯著縮小。路由表的大小（或條目數）相當于覆蓋網絡的傳出程度。它是覆蓋網絡的空間復雜度。

基本操作：一個基本操作是查找（key），它返回存儲該密鑰的節點的標識（例如IP地址）。此操作允許節點根據其密鑰放置和獲取數據。

路由和定位算法：當發出或接收到查找（密鑰）時，查找將通過覆蓋網絡路由到負責該密鑰的主節點。每個躍點在解決查找方面都取得了最大的進展。不同算法的進程標記不同，但是任何路由算法都應該在每個跳的意義上收斂，使得當前節點ID和主節點ID之間的距離越來越小。注意，收斂路由算法是覆蓋網絡的第二個必要特征。

路由表大小：由于所有對等節點都以某種規則的拓撲結構連接，因此路由表可以顯著減少。路由表的大小（或條目數）由規則網絡的程度決定。它是覆蓋網絡的空間復雜度。

路徑長度：是覆蓋網絡中消息需要經過的躍點數。它是覆蓋網絡的時間復雜度。

鄰近性：實際距離性能不僅取決于路徑長度，還取決于網絡中每個跳的通信延遲。雖然互聯網是完全自治的，但進一步的調查表明，互聯網仍然具有一定的規律性。如果P2P系統的支持網絡被限制在一個區域或校園范圍內，這種規律性就更加明顯。

容錯性：首先，根據路由算法，如果下一個節點當前未加入網絡，則應將路由消息發送到路由表中更新的另一個節點;其次，如果節點在沒有通知的情況下突然崩潰，則活節點應能夠檢測并更新路由表。

自組織：為了使P2P系統完全分布式，當一個節點加入或離開系統時，路由表應該自動重新配置。節點可能由于崩潰而突然離開，或者通過通知鄰居并提交密鑰而優雅地離開，前一種情況通常稱為節點失敗。在這種情況下，節點應該有方法檢測節點加入或節點離開以重新配置其路由表狀態。在一些節點離開后，剩余的活動節點根據拓撲連接模式自組織。注意，自組織是覆蓋網絡的第三個必要特性。

數據可用性：存儲同一數據的多個副本，以提高查找效率和容錯性。當請求的數據發送到請求者時，它們通常沿著從目標到源的反向路徑存儲。

可擴展性：一般來說，P2P是可擴展的，前提是可以在不明顯降低性能的情況下增加對等點的數量。目前，它主要是通過空間時間復雜度來評估的，即路由表大小乘以路徑長度。顯然，可擴展性并不是一個標準。實際上，它是由上面討論的幾乎每一個方面所決定的總體評估。例如，為了提高可擴展性，路由和自組織都應該只使用本地信息。

上述標準并非詳盡無遺，而是與拓撲相關，其中包括一致哈希、智能代理、分布式數據結構、查詢合成、安全性、匿名性和與拓撲無關的社會計量學。我們對拓撲分析的關注并不意味著這些其他問題是次要的。

三、總結

P2P系統最大的特點就是用戶之間直接共享資源，其核心技術就是分布式對象的定位機制，這也是提高網絡可擴展性、解決網絡帶寬被吞噬的關鍵所在。迄今為止，P2P網絡已經歷了不同網絡模型，各種模型各有優缺點，有點還存在著本身難以克服的缺陷。因此在目前P2P技術還遠未成熟的階段，各種網絡結構依然能夠共存，甚至呈現相互借鑒的形式。

在結構化P2P系統中，每個節點只存儲特定的信息或特定信息的索引。當用戶需要在P2P系統中獲取信息時，它們必須知道這些信息可能存在哪些節點中。由于用戶預先知道應該搜索哪些節點，這就避免了非結構化P2P系統中使用的泛洪式查找，因此提高了信息搜索的效率。