淺析P2P系統(tǒng)的拓撲

宋靜靜

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

關(guān)鍵詞：P2P系統(tǒng);覆蓋網(wǎng)絡;路由;定位算法

一、引言

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

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

通過進一步的研究，我們發(fā)現(xiàn)所有這些新一代P2P系統(tǒng)都有一個共同的特點，即節(jié)點在應用層上連接成一個有規(guī)則的網(wǎng)絡，例如一個環(huán)、一個網(wǎng)格或一個通常被稱為覆蓋網(wǎng)絡的超立方體。隨著P2P體系結(jié)構(gòu)的日益流行和系統(tǒng)的不斷引入，我們認為需要一個抽象的、通用的拓撲模型來捕捉P2P體系結(jié)構(gòu)的本質(zhì)。這種模式應該反過來促進新的P2P系統(tǒng)設(shè)計空間的開發(fā)。

二、拓撲模型

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

覆蓋網(wǎng)絡的復雜性常常決定了可以構(gòu)建的P2P系統(tǒng)的大小。同樣，P2P系統(tǒng)的可達到性能最終受到覆蓋網(wǎng)絡特性的限制。顯然，選擇覆蓋網(wǎng)絡是P2P系統(tǒng)設(shè)計的第一步，也是最關(guān)鍵的一步。

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

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

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

數(shù)據(jù)放置：數(shù)據(jù)ID和節(jié)點ID屬于同一空間。理想情況下，數(shù)據(jù)存儲在與數(shù)據(jù)ID具有相同ID的節(jié)點上，但活動節(jié)點或?qū)Φ裙?jié)點的數(shù)量通常比數(shù)據(jù)的數(shù)量少很多。每個節(jié)點負責在密鑰空間中存儲一定范圍的密鑰。數(shù)據(jù)存儲在最近的節(jié)點上，最近的ID為節(jié)點ID。

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

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

路由表：每個節(jié)點維護由系統(tǒng)中的一小部分節(jié)點組成的路由表。由于所有對等節(jié)點都以某種規(guī)則的拓撲結(jié)構(gòu)連接，因此路由表可以顯著縮小。路由表的大?。ɑ驐l目數(shù)）相當于覆蓋網(wǎng)絡的傳出程度。它是覆蓋網(wǎng)絡的空間復雜度。

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

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

路由表大?。河捎谒袑Φ裙?jié)點都以某種規(guī)則的拓撲結(jié)構(gòu)連接，因此路由表可以顯著減少。路由表的大小（或條目數(shù)）由規(guī)則網(wǎng)絡的程度決定。它是覆蓋網(wǎng)絡的空間復雜度。

路徑長度：是覆蓋網(wǎng)絡中消息需要經(jīng)過的躍點數(shù)。它是覆蓋網(wǎng)絡的時間復雜度。

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

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

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

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

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

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

三、總結(jié)

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

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