隨著P2P應用的蓬勃發(fā)展，作為P2P應用中核心問題的發(fā)現(xiàn)技術(shù)除了遵循技術(shù)本身的邏輯以外，也受到某些技術(shù)的發(fā)展趨勢、需求趨勢的深刻影響。
P2P協(xié)議概述
P2P打破了傳統(tǒng)的Client/Server (C/S)模式，在網(wǎng)絡(luò)中的每個結(jié)點的地位都是對等的。每個結(jié)點既充當服務器，為其他結(jié)點提供服務，同時也享用其他結(jié)點提供的服務。P2P與C/S模式的對比如下圖所示:
P2P技術(shù)的特點體現(xiàn)在以下幾個方面：
非中心化（Decentralization）：網(wǎng)絡(luò)中的資源和服務分散在所有結(jié)點上，信息的傳輸和服務的實現(xiàn)都直接在結(jié)點之間進行，可以無需中間環(huán)節(jié)和服務器的介入，避免了可能的瓶頸。P2P的非中心化基本特點，帶來了其在可擴展性、健壯性等方面的優(yōu)勢。
可擴展性：在P2P網(wǎng)絡(luò)中，隨著用戶的加入，不僅服務的需求增加了，系統(tǒng)整體的資源和服務能力也在同步地擴充，始終能較容易地滿足用戶的需要。整個體系是全分布的，不存在瓶頸。理論上其可擴展性幾乎可以認為是無限的。
健壯性：P2P架構(gòu)天生具有耐攻擊、高容錯的優(yōu)點。由于服務是分散在各個結(jié)點之間進行的，部分結(jié)點或網(wǎng)絡(luò)遭到破壞對其它部分的影響很小。P2P網(wǎng)絡(luò)一般在部分結(jié)點失效時能夠自動調(diào)整整體拓撲，保持其它結(jié)點的連通性。P2P網(wǎng)絡(luò)通常都是以自組織的方式建立起來的，并允許結(jié)點自由地加入和離開。P2P網(wǎng)絡(luò)還能夠根據(jù)網(wǎng)絡(luò)帶寬、結(jié)點數(shù)、負載等變化不斷地做自適應式的調(diào)整。
高性能/價格比：性能優(yōu)勢是P2P被廣泛關(guān)注的一個重要原因。隨著硬件技術(shù)的發(fā)展，個人計算機的計算和存儲能力以及網(wǎng)絡(luò)帶寬等性能依照摩爾定理高速增長。采用P2P架構(gòu)可以有效地利用互聯(lián)網(wǎng)中散布的大量普通結(jié)點，將計算任務或存儲資料分布到所有結(jié)點上。利用其中閑置的計算能力或存儲空間，達到高性能計算和海量存儲的目的。通過利用網(wǎng)絡(luò)中的大量空閑資源，可以用更低的成本提供更高的計算和存儲能力。
隱私保護:在P2P網(wǎng)絡(luò)中，由于信息的傳輸分散在各節(jié)點之間進行而無需經(jīng)過某個集中環(huán)節(jié)，用戶的隱私信息被竊聽和泄漏的可能性大大縮小。此外，目前解決 Internet隱私問題主要采用中繼轉(zhuǎn)發(fā)的技術(shù)方法，從而將通信的參與者隱藏在眾多的網(wǎng)絡(luò)實體之中。在傳統(tǒng)的一些匿名通信系統(tǒng)中，實現(xiàn)這一機制依賴于某些中繼服務器節(jié)點。而在P2P中，所有參與者都可以提供中繼轉(zhuǎn)發(fā)的功能，因而大大提高了匿名通訊的靈活性和可靠性，能夠為用戶提供更好的隱私保護。
負載均衡:P2P 網(wǎng)絡(luò)環(huán)境下由于每個節(jié)點既是服務器又是客戶機，減少了對傳統(tǒng)C/S結(jié)構(gòu)服務器計算能力、存儲能力的要求，同時因為資源分布在多個節(jié)點，更好的實現(xiàn)了整個網(wǎng)絡(luò)的負載均衡。
根據(jù)具體應用不同，可以把P2P分為以下這些類型：
提供文件和其它內(nèi)容共享的P2P網(wǎng)絡(luò)，例如Napster、Gnutella、eDonkey、emule、BitTorrent等；
挖掘P2P對等計算能力和存儲共享能力，例如SETI@home?、Avaki、Popular Power等；
基于P2P方式的協(xié)同處理與服務共享平臺，例如JXTA、Magi、Groove、.NET My Service等；
即時通訊交流，包括ICQ、OICQ、Yahoo Messenger等；
安全的P2P通訊與信息共享，例如Skype、Crowds、Onion Routing等。
P2P網(wǎng)絡(luò)中的拓撲結(jié)構(gòu)研究
拓撲結(jié)構(gòu)是指分布式系統(tǒng)中各個計算單元之間的物理或邏輯的互聯(lián)關(guān)系，結(jié)點之間的拓撲結(jié)構(gòu)一直是確定系統(tǒng)類型的重要依據(jù)。目前互聯(lián)網(wǎng)絡(luò)中廣泛使用集中式、層次式等拓撲結(jié)構(gòu)，Interne本身是世界上最大的非集中式的互聯(lián)網(wǎng)絡(luò)，但是九十年代所建立的一些網(wǎng)絡(luò)應用系統(tǒng)卻是完全的集中式的系統(tǒng)、很多Web應用都是運行在集中式的服務器系統(tǒng)上。集中式拓撲結(jié)構(gòu)系統(tǒng)目前面臨著過量存儲負載、Dos攻擊等一些難以解決的問題。
P2P系統(tǒng)一般要構(gòu)造一個非集中式的拓撲結(jié)構(gòu)，在構(gòu)造過程中需要解決系統(tǒng)中所包含的大量結(jié)點如何命名、組織以及確定結(jié)點的加入/離開方式、出錯恢復等問題。
根據(jù)拓撲結(jié)構(gòu)的關(guān)系可以將P2P研究分為4種形式：
中心化拓撲（Centralized Topology）
全分布式非結(jié)構(gòu)化拓撲（Decentralized Unstructured Topology）
全分布式結(jié)構(gòu)化拓撲（Decentralized Structured Topology，也稱作DHT網(wǎng)絡(luò)）
半分布式拓撲（Partially Decentralized Topology）
中心化拓撲
中心化拓撲最大的優(yōu)點是維護簡單發(fā)現(xiàn)效率高。由于資源的發(fā)現(xiàn)依賴中心化的目錄系統(tǒng)，發(fā)現(xiàn)算法靈活高效并能夠?qū)崿F(xiàn)復雜查詢。最大的問題與傳統(tǒng)客戶機/服務器結(jié)構(gòu)類似，容易造成單點故障，訪問的“熱點”現(xiàn)象和法律等相關(guān)問題，這是第一代P2P網(wǎng)絡(luò)采用的結(jié)構(gòu)模式，經(jīng)典案例就是著名的MP3共享軟件Napster。
Napster實質(zhì)上并非是純粹的P2P系統(tǒng)，它通過一個中央服務器保存所有Napster用戶上傳的音樂文件索引和存放位置的信息。當某個用戶需要某個音樂文件時，首先連接到Napster服務器，在服務器進行檢索，并由服務器返回存有該文件的用戶信息；再由請求者直接連到文件的所有者傳輸文件。
Napster首先實現(xiàn)了文件查詢與文件傳輸?shù)姆蛛x，有效地節(jié)省了中央服務器的帶寬消耗，減少了系統(tǒng)的文件傳輸延時。這種方式最大的隱患在中央服務器上，如果該服務器失效，整個系統(tǒng)都會癱瘓。當用戶數(shù)量增加到105或者更高時，Napster的系統(tǒng)性能會大大下降。另一個問題在于安全性上，Napster并沒有提供有效的安全機制。
在Napster 模型中，一群高性能的中央服務器保存著網(wǎng)絡(luò)中所有活動對等計算機共享資源的目錄信息。當需要查詢某個文件時，對等機會向一臺中央服務器發(fā)出文件查詢請求。中央服務器進行相應的檢索和查詢后，會返回符合查詢要求的對等機地址信息列表。查詢發(fā)起對等機接收到應答后，會根據(jù)網(wǎng)絡(luò)流量和延遲等信息進行選擇，和合適的對等機建立連接，并開始文件傳輸。Napster的工作原理如圖1所示。
這種對等網(wǎng)絡(luò)模型存在很多問題，主要表現(xiàn)為：
中央服務器的癱瘓容易導致整個網(wǎng)絡(luò)的崩饋，可靠性和安全性較低。
隨著網(wǎng)絡(luò)規(guī)模的擴大，對中央索引服務器進行維護和更新的費用將急劇增加，所需成本過高。
中央服務器的存在引起共享資源在版權(quán)問題上的糾紛，并因此被攻擊為非純粹意義上的P2P網(wǎng)絡(luò)模型。對小型網(wǎng)絡(luò)而言，集中目錄式模型在管理和控制方面占一定優(yōu)勢。但鑒于其存在的種種缺陷，該模型并不適合大型網(wǎng)絡(luò)應用。
全分布非結(jié)構(gòu)化網(wǎng)絡(luò)
全分布非結(jié)構(gòu)化網(wǎng)絡(luò)在重疊網(wǎng)絡(luò)（overlay）采用了隨機圖的組織方式，結(jié)點度數(shù)服從”Power-law”[a][b]規(guī)律，從而能夠較快發(fā)現(xiàn)目的結(jié)點，面對網(wǎng)絡(luò)的動態(tài)變化體現(xiàn)了較好的容錯能力，因此具有較好的可用性。同時可以支持復雜查詢，如帶有規(guī)則表達式的多關(guān)鍵詞查詢，模糊查詢等，最典型的案例是Gnutella。
Gnutella是一個P2P文件共享系統(tǒng)，它和Napster最大的區(qū)別在于Gnutella是純粹的P2P系統(tǒng)，沒有索引服務器，它采用了基于完全隨機圖的洪泛（Flooding）發(fā)現(xiàn)和隨機轉(zhuǎn)發(fā)（Random Walker）機制。為了控制搜索消息的傳輸，通過TTL (Time To Live)的減值來實現(xiàn)。具體協(xié)議參照［Gnutella協(xié)議中文版］
在Gnutella分布式對等網(wǎng)絡(luò)模型N中，每一個聯(lián)網(wǎng)計算機在功能上都是對等的，既是客戶機同時又是服務器，所以被稱為對等機(Servent，Server+Client的組合)。
隨著聯(lián)網(wǎng)節(jié)點的不斷增多，網(wǎng)絡(luò)規(guī)模不斷擴大，通過這種洪泛方式定位對等點的方法將造成網(wǎng)絡(luò)流量急劇增加，從而導致網(wǎng)絡(luò)中部分低帶寬節(jié)點因網(wǎng)絡(luò)資源過載而失效。所以在初期的Gnutella網(wǎng)絡(luò)中，存在比較嚴重的分區(qū)，斷鏈現(xiàn)象。也就是說，一個查詢訪問只能在網(wǎng)絡(luò)的很小一部分進行，因此網(wǎng)絡(luò)的可擴展性不好。所以，解決Gnutella網(wǎng)絡(luò)的可擴展性對該網(wǎng)絡(luò)的進一步發(fā)展至關(guān)重要。
由于沒有確定拓撲結(jié)構(gòu)的支持，非結(jié)構(gòu)化網(wǎng)絡(luò)無法保證資源發(fā)現(xiàn)的效率。即使需要查找的目的結(jié)點存在發(fā)現(xiàn)也有可能失敗。由于采用TTL（Time-to-Live）、洪泛（Flooding）、隨機漫步或有選擇轉(zhuǎn)發(fā)算法，因此直徑不可控，可擴展性較差。
因此發(fā)現(xiàn)的準確性和可擴展性是非結(jié)構(gòu)化網(wǎng)絡(luò)面臨的兩個重要問題。目前對此類結(jié)構(gòu)的研究主要集中于改進發(fā)現(xiàn)算法和復制策略以提高發(fā)現(xiàn)的準確率和性能。
由于非結(jié)構(gòu)化網(wǎng)絡(luò)將重疊網(wǎng)絡(luò)認為是一個完全隨機圖，結(jié)點之間的鏈路沒有遵循某些預先定義的拓撲來構(gòu)建。這些系統(tǒng)一般不提供性能保證，但容錯性好，支持復雜的查詢，并受結(jié)點頻繁加入和退出系統(tǒng)的影響小。但是查詢的結(jié)果可能不完全，查詢速度較慢，采用廣播查詢的系統(tǒng)對網(wǎng)絡(luò)帶寬的消耗非常大，并由此帶來可擴展性差等問題。
另外，由于非結(jié)構(gòu)化系統(tǒng)中的隨機搜索造成的不可擴展性，大量的研究集中在如何構(gòu)造一個高度結(jié)構(gòu)化的系統(tǒng)。目前研究的重點放在了如何有效地查找信息上，最新的成果都是基于DHT的分布式發(fā)現(xiàn)和路由算法。這些算法都避免了類似Napster的中央服務器，也不是像Gnutella那樣基于廣播進行查找，而是通過分布式散列函數(shù)，將輸入的關(guān)鍵字惟一映射到某個結(jié)點上，然后通過某些路由算法同該結(jié)點建立連接。
最新的研究成果體現(xiàn)在采用分布式散列表（DHT）[a]的完全分布式結(jié)構(gòu)化拓撲網(wǎng)絡(luò)。
分布式散列表（DHT）
DHT分布式散列表實際上是一個由廣域范圍大量結(jié)點共同維護的巨大散列表。散列表被分割成不連續(xù)的塊，每個結(jié)點被分配給一個屬于自己的散列塊，并成為這個散列塊的管理者。DHT的結(jié)點既是動態(tài)的結(jié)點數(shù)量也是巨大的，因此非中心化和原子自組織成為兩個設(shè)計的重要目標。通過加密散列函數(shù)，一個對象的名字或關(guān)鍵詞被映射為128位或160位的散列值。一個采用DHT的系統(tǒng)內(nèi)所有結(jié)點被映射到一個空間，如果散列函數(shù)映射一個位的名字到一個散列值，則有。
分布式散列表起源于SDDS（Scalable Distribute Data Structures）[a]研究，Gribble等實現(xiàn)了一個高度可擴展，容錯的SDDS集群。
最近的研究集中在采用新的拓撲圖構(gòu)建重疊路由網(wǎng)絡(luò)，以減少路由表容量和路由延時。這些新的拓撲關(guān)系的基本原理是在DHT表一維空間的基礎(chǔ)上引入更多的拓撲結(jié)構(gòu)圖來反映底層網(wǎng)絡(luò)的結(jié)構(gòu)。
DHT類結(jié)構(gòu)能夠自適應結(jié)點的動態(tài)加入/退出，有著良好的可擴展性、魯棒性、結(jié)點ID分配的均勻性和自組織能力。由于重疊網(wǎng)絡(luò)采用了確定性拓撲結(jié)構(gòu)，DHT可以提供精確的發(fā)現(xiàn)。只要目的結(jié)點存在于網(wǎng)絡(luò)中DHT總能發(fā)現(xiàn)它，發(fā)現(xiàn)的準確性得到了保證，最經(jīng)典的案例是Tapestry，Chord,CAN,和Pastry。
Tapestry提供了一個分布式容錯查找和路由基礎(chǔ)平臺，在此平臺基礎(chǔ)之上，可以開發(fā)各種P2P應用(OceanStore即是此平臺上的一個應用) 。Tapestry的思想來源于Plaxton。在Plaxton中，結(jié)點使用自己所知道的鄰近結(jié)點表，按照目的ID來逐步傳遞消息。Tapestry基于Plaxtion的思想，加入了容錯機制，從而可適應P2P的動態(tài)變化的特點。
在DHT技術(shù)中，網(wǎng)絡(luò)結(jié)點按照一定的方式分配一個唯一結(jié)點標識符(Node ID) ，資源對象通過散列運算產(chǎn)生一個唯一的資源標識符(Object ID) ，且該資源將存儲在結(jié)點ID與之相等或者相近的結(jié)點上。需要查找該資源時，采用同樣的方法可定位到存儲該資源的結(jié)點。因此，Chord的主要貢獻是提出了一個分布式查找協(xié)議，該協(xié)議可將指定的關(guān)鍵字(Key) 映射到對應的結(jié)點(Node) 。從算法來看，Chord是相容散列算法的變體。MIT的GRID和RON項目則提出了在分布式廣域網(wǎng)中實施查找資源的系統(tǒng)框架。
AT&T ACIRI中心的CAN(Content Addressable Networks) 項目獨特之處在于采用多維的標識符空間來實現(xiàn)分布式散列算法。CAN將所有結(jié)點映射到一個n維的笛卡爾空間中，并為每個結(jié)點盡可能均勻的分配一塊區(qū)域。CAN采用的散列函數(shù)通過對(key, value) 對中的key進行散列運算，得到笛卡爾空間中的一個點，并將(key, value) 對存儲在擁有該點所在區(qū)域的結(jié)點內(nèi)。CAN采用的路由算法相當直接和簡單，知道目標點的坐標后，就將請求傳給當前結(jié)點四鄰中坐標最接近目標點的結(jié)點。CAN是一個具有良好可擴展性的系統(tǒng)，給定N個結(jié)點，系統(tǒng)維數(shù)為d，則路由路徑長度為O(n1/d) ，每結(jié)點維護的路由表信息和網(wǎng)絡(luò)規(guī)模無關(guān)為O(d) 。
DHT類結(jié)構(gòu)最大的問題是DHT的維護機制較為復雜，尤其是結(jié)點頻繁加入退出造成的網(wǎng)絡(luò)波動（Churn）會極大增加DHT的維護代價。DHT所面臨的另外一個問題是DHT僅支持精確關(guān)鍵詞匹配查詢，無法支持內(nèi)容/語義等復雜查詢。
半分布式結(jié)構(gòu)
半分布式結(jié)構(gòu)（有的文獻稱作 Hybrid Structure）吸取了中心化結(jié)構(gòu)和全分布式非結(jié)構(gòu)化拓撲的優(yōu)點，選擇性能較高（處理、存儲、帶寬等方面性能）的結(jié)點作為超級點（英文文獻中多稱作：SuperNodes, Hubs)，在各個超級點上存儲了系統(tǒng)中其他部分結(jié)點的信息，發(fā)現(xiàn)算法僅在超級點之間轉(zhuǎn)發(fā)，超級點再將查詢請求轉(zhuǎn)發(fā)給適當?shù)娜~子結(jié)點。半分布式結(jié)構(gòu)也是一個層次式結(jié)構(gòu)，超級點之間構(gòu)成一個高速轉(zhuǎn)發(fā)層，超級點和所負責的普通結(jié)點構(gòu)成若干層次。最典型的案例就是KaZaa。
KaZaa是現(xiàn)在全世界流行的幾款p2p軟件之一。根據(jù)CA公司統(tǒng)計，全球KaZaa的下載量超過2.5億次。使用KaZaa軟件進行文件傳輸消耗了互聯(lián)網(wǎng)40%的帶寬。之所以它如此的成功，是因為它結(jié)合了Napster和Gnutella共同的優(yōu)點。從結(jié)構(gòu) 上來說，它使用了Gnutella的全分布式的結(jié)構(gòu)，這樣可以是系統(tǒng)更好的擴展，因為它無需中央索引服務器存儲文件名，它是自動的把性能好的機器成為SuperNode，它存儲著離它最近的葉子節(jié)點的文件信息，這些SuperNode,再連通起來形成一個Overlay Network. 由于SuperNode的索引功能，使搜索效率大大提高。
半分布式結(jié)構(gòu)的優(yōu)點是性能、可擴展性較好，較容易管理，但對超級點依賴性大，易于受到攻擊，容錯性也受到影響。
P2P中的核心技術(shù)
度數(shù)和直徑的折衷關(guān)系（tradeoff）對發(fā)現(xiàn)算法的影響
DHT發(fā)現(xiàn)技術(shù)完全建立在確定性拓撲結(jié)構(gòu)的基礎(chǔ)上，從而表現(xiàn)出對網(wǎng)絡(luò)中路由的指導性和網(wǎng)絡(luò)中結(jié)點與數(shù)據(jù)管理的較強控制力。但是，對確定性結(jié)構(gòu)的認識又限制了發(fā)現(xiàn)算法效率的提升。研究分析了目前基于DHT的發(fā)現(xiàn)算法，發(fā)現(xiàn)衡量發(fā)現(xiàn)算法的兩個重要參數(shù)度數(shù)（表示鄰居關(guān)系數(shù)、路由表的容量）和鏈路長度（發(fā)現(xiàn)算法的平均路徑長度）之間存在漸進曲線的關(guān)系。
研究者采用圖論中度數(shù)(Degree)和直徑(Diameter)兩個參數(shù)研究DHT發(fā)現(xiàn)算法，發(fā)現(xiàn)這些DHT發(fā)現(xiàn)算法在度數(shù)和直徑之間存在漸進曲線關(guān)系，如下圖所示。在N個結(jié)點網(wǎng)絡(luò)中，圖中直觀顯示出當度數(shù)為N時，發(fā)現(xiàn)算法的直徑為O(1)；當每個結(jié)點僅維護一個鄰居時，發(fā)現(xiàn)算法的直徑為O(N)。這是度數(shù)和直徑關(guān)系的2種極端情況。同時，研究以圖論的理論分析了O(d)的度和O(d)的直徑的算法是不可能的。
從漸進曲線關(guān)系可以看出，如果想獲得更短的路徑長度，必然導致度數(shù)的增加；而網(wǎng)絡(luò)實際連接狀態(tài)的變化造成大度數(shù)鄰居關(guān)系的維護復雜程度增加。另外，研究者證明O(logN)甚至O(logN/loglogN)的平均路徑長度也不能滿足狀態(tài)變化劇烈的網(wǎng)絡(luò)應用的需求。新的發(fā)現(xiàn)算法受到這種折衷關(guān)系制約的根本原因在于DHT對網(wǎng)絡(luò)拓撲結(jié)構(gòu)的確定性認識。
Small world 理論對P2P發(fā)現(xiàn)技術(shù)的影響
Small-world模型的特性：網(wǎng)絡(luò)拓撲具有高聚集度和短鏈的特性。在符合small world特性的網(wǎng)絡(luò)模型中，可以根據(jù)結(jié)點的聚集度將結(jié)點劃分為若干簇(Cluster)，在每個簇中至少存在一個度最高的結(jié)點為中心結(jié)點。大量研究證明了以Gnutella為代表的P2P網(wǎng)絡(luò)符合small world特征，也就是網(wǎng)絡(luò)中存在大量高連通結(jié)點，部分結(jié)點之間存在“短鏈”現(xiàn)象。
因此，P2P發(fā)現(xiàn)算法中如何縮短路徑長度的問題變成了如何找到這些“短鏈”的問題。尤其是在DHT發(fā)現(xiàn)算法中，如何產(chǎn)生和找到“短鏈”是發(fā)現(xiàn)算法設(shè)計的一個新的思路。small world特征的引入會對P2P發(fā)現(xiàn)算法產(chǎn)生重大影響。
非結(jié)構(gòu)化P2P系統(tǒng)中發(fā)現(xiàn)技術(shù)一直采用洪泛轉(zhuǎn)發(fā)的方式，與DHT的啟發(fā)式發(fā)現(xiàn)算法相比，可靠性差，對網(wǎng)絡(luò)資源的消耗較大。最新的研究從提高發(fā)現(xiàn)算法的可靠性和尋找隨機圖中的最短路徑兩個方面展開。也就是對重疊網(wǎng)絡(luò)的重新認識。其中，small world特征和冪規(guī)律證明實際網(wǎng)絡(luò)的拓撲結(jié)構(gòu)既不是非結(jié)構(gòu)化系統(tǒng)所認識的一個完全隨機圖，也不是DHT發(fā)現(xiàn)算法采用的確定性拓撲結(jié)構(gòu)。
實際網(wǎng)絡(luò)體現(xiàn)的冪規(guī)律分布的含義可以簡單解釋為在網(wǎng)絡(luò)中有少數(shù)結(jié)點有較高的“度”，多數(shù)結(jié)點的“度”較低。度較高的結(jié)點同其他結(jié)點的聯(lián)系比較多，通過它找到待查信息的概率較高。
語義查詢和DHT的矛盾
現(xiàn)有DHT算法由于采用分布式散列函數(shù)，所以只適合于準確的查找，如果要支持目前Web上搜索引擎具有的多關(guān)鍵字查找的功能，還要引入新的方法。主要的原因在于DHT的工作方式。
基于DHT的P2P系統(tǒng)采用相容散列函數(shù)根據(jù)精確關(guān)鍵詞進行對象的定位與發(fā)現(xiàn)。散列函數(shù)總是試圖保證生成的散列值均勻隨機分布，結(jié)果兩個內(nèi)容相似度很高但不完全相同的對象被生成了完全不同的散列值，存放到了完全隨機的兩個結(jié)點上。因此，DHT可以提供精確匹配查詢，但是支持語義是非常困難的。
目前在DHT基礎(chǔ)上開展帶有語義的資源管理技術(shù)的研究還非常少。由于DHT的精確關(guān)鍵詞映射的特性決定了無法和信息檢索等領(lǐng)域的研究成果結(jié)合，阻礙了基于DHT的P2P系統(tǒng)的大規(guī)模應用。[a]
P2P發(fā)現(xiàn)技術(shù)研究的成果與不足
P2P發(fā)現(xiàn)技術(shù)中最重要的研究成果應該是基于small world理論的非結(jié)構(gòu)化發(fā)現(xiàn)算法和基于DHT的結(jié)構(gòu)化發(fā)現(xiàn)算法。尤其是DHT及其發(fā)現(xiàn)技術(shù)為資源的組織與查找提供了一種新的方法。
隨著P2P系統(tǒng)實際應用的發(fā)展，物理網(wǎng)絡(luò)中影響路由的一些因素開始影響P2P發(fā)現(xiàn)算法的效率。一方面，實際網(wǎng)絡(luò)中結(jié)點之間體現(xiàn)出較大的差異，即異質(zhì)性。由于客戶機/服務器模式在Internet和分布式領(lǐng)域十幾年的應用和大量種類的電子設(shè)備的普及，如手提電腦、移動電話或PDA。這些設(shè)備在計算能力、存儲空間和電池容量上差別很大。另外，實際網(wǎng)絡(luò)被路由器和交換機分割成不同的自治區(qū)域，體現(xiàn)出嚴密的層次性。
另一方面，網(wǎng)絡(luò)波動的程度嚴重影響發(fā)現(xiàn)算法的效率。網(wǎng)絡(luò)波動（Churn、fluctuation of network）包括結(jié)點的加入、退出、失敗、遷移、并發(fā)加入過程、網(wǎng)絡(luò)分割等。DHT的發(fā)現(xiàn)算法如Chord、CAN、Koorde等都是考慮網(wǎng)絡(luò)波動的最差情況下的設(shè)計與實現(xiàn)。由于每個結(jié)點的度數(shù)盡量保持最小，這樣需要響應的成員關(guān)系變化的維護可以比較小，從而可以快速恢復網(wǎng)絡(luò)波動造成的影響。但是每個結(jié)點僅有少量路由狀態(tài)的代價是發(fā)現(xiàn)算法的高延時，因為每一次查找需要聯(lián)系多個結(jié)點，在穩(wěn)定的網(wǎng)絡(luò)中這種思路是不必要的。
同時，作為一種資源組織與發(fā)現(xiàn)技術(shù)必然要支持復雜的查詢，如關(guān)鍵詞、內(nèi)容查詢等。盡管信息檢索和數(shù)據(jù)挖掘領(lǐng)域提供了大量成熟的語義查詢技術(shù)，由于DHT精確關(guān)鍵詞映射的特性阻礙了DHT在復雜查詢方面的應用。
P2P網(wǎng)絡(luò)拓撲模型
Internet作為當今人類社會信息化的標志,其規(guī)模正以指數(shù)速度高速增長.如今Internet的“面貌”已與其原型ARPANET大相徑庭,依其高度的復雜性,可以將其看作一個由計算機構(gòu)成的“生態(tài)系統(tǒng)”.雖然Internet是人類親手建造的,但卻沒有人能說出這個龐然大物看上去到底是個什么樣子,運作得如何.Internet拓撲建模研究就是探求在這個看似混亂的網(wǎng)絡(luò)之中蘊含著哪些還不為我們所知的規(guī)律.發(fā)現(xiàn)Internet拓撲的內(nèi)在機制是認識Internet的必然過程,是在更高層次上開發(fā)利用Internet的基礎(chǔ).然而,Internet與生俱來的異構(gòu)性動態(tài)性發(fā)展的非集中性以及如今龐大的規(guī)模都給拓撲建模帶來巨大挑戰(zhàn).Internet拓撲建模至今仍然是一個開放性問題,在計算機網(wǎng)絡(luò)研究中占有重要地位.
Internet拓撲作為Internet這個自組織系統(tǒng)的“骨骼”,與流量協(xié)議共同構(gòu)成模擬Internet的3個組成部分,即在拓撲網(wǎng)絡(luò)中節(jié)點間執(zhí)行協(xié)議,形成流量.Internet拓撲模型是建立Internet系統(tǒng)模型的基礎(chǔ),由此而體現(xiàn)的拓撲建模意義也可以說就是Internet建模的意義,即作為一種工具,人們用其來對Internet進行分析預報決策或控制.Internet模型中的拓撲部分刻畫的是Internet在宏觀上的特征,反映一種總體趨勢,所以其應用也都是在大尺度上展開的.對Internet拓撲模型的需求主要來自以下幾個方面:
許多新應用或?qū)嶒灢贿m合直接應用于Internet,其中一些具有危害性,如蠕蟲病毒在大規(guī)模網(wǎng)絡(luò)上的傳播模擬;
對于一些依賴于網(wǎng)絡(luò)拓撲的協(xié)議(如多播協(xié)議),在其研發(fā)階段,當前Internet拓撲只能提供一份測試樣本,無法對協(xié)議進行全面評估,需要提供多個模擬拓撲環(huán)境來進行實驗;
從國家安全角度考慮,需要在線控制網(wǎng)絡(luò)行為,如美國國防高級研究計劃局(DARPA)的NMS(network modeling and simulation)項目.
1、隨機網(wǎng)絡(luò)與拓撲模型
隨機網(wǎng)絡(luò)是由N個頂點構(gòu)成的圖中，可以存在條邊，我們從中隨機連接M條邊所構(gòu)成的網(wǎng)絡(luò)。還有一種生成隨機網(wǎng)絡(luò)的方法是，給一個概率p，對于中任何一個可能連接，我們都嘗試一遍以概率p的連接。如果我們選擇M = p，這兩種隨機網(wǎng)絡(luò)模型就可以聯(lián)系起來。對于如此簡單的隨機網(wǎng)絡(luò)模型，其幾何性質(zhì)的研究卻不是同樣的簡單。隨機網(wǎng)絡(luò)幾何性質(zhì)的研究是由Paul，Alfréd Rényi和Béla Bollobás在五十年代到六十年代之間完成的。隨機網(wǎng)絡(luò)在Internet的拓撲中占有很重要的位置。
2、隨機網(wǎng)絡(luò)參數(shù)
描述隨機網(wǎng)絡(luò)有一些重要的參數(shù)。一個節(jié)點所擁有的度是該節(jié)點與其他節(jié)點相關(guān)聯(lián)的邊數(shù)，度是描述網(wǎng)絡(luò)局部特性的基本參數(shù)。網(wǎng)絡(luò)中并不是所有節(jié)點都具有相同的度，系統(tǒng)中節(jié)點度的分布情況，可以用分布函數(shù)描述，度分布函數(shù)反映了網(wǎng)絡(luò)系統(tǒng)的宏觀統(tǒng)計特征。理論上利用度分布可以計算出其他表征全局特性參數(shù)的量化數(shù)值。
聚集系數(shù)是描述與第三個節(jié)點連接的一對節(jié)點被連接的概率。從連接節(jié)點的邊的意義上，若為第i個節(jié)點的度，在由k.個近鄰節(jié)點構(gòu)成的子網(wǎng)中，實際存在的邊數(shù)E(i)與全部k.個節(jié)點完全連接時的總邊數(shù)充的比值定義為節(jié)點i的聚集系數(shù)
3、拓撲模型
Internet拓撲模型可分為兩類:
描述Internet拓撲特征,包括Waxman模型,Tiers,Transit -Stub和冪律;
描述拓撲特征形成的機理,包括Barabási與Albert提出的BA和ESF以及一種改進模型GLP.
由于第二類模型對Internet冪律形成機理的描述還不成熟,更多的是作為一種產(chǎn)生冪律的圖生成算法。對于第1類模型來說,Internet拓撲特征的發(fā)現(xiàn),實際上就是刻畫該特征的度量(metric)的發(fā)現(xiàn).一個屬于第一類的拓撲模型就是包含若干已存在的或新發(fā)現(xiàn)的度量,然后根據(jù)實際的Internet拓撲數(shù)據(jù)求出這些度量的值.因此,對這類模型進行評價需要從兩方面入手:
對它所采用的拓撲數(shù)據(jù)進行評價;
對其度量進行評價.
在所有已經(jīng)發(fā)現(xiàn)的Internet拓撲度量中,最為基本的就是節(jié)點出度頻率fd.其分布是判斷一幅拓撲圖是否與Internet拓撲相類似的最重要的依據(jù).在研究早期,研究人員或者認為Internet節(jié)點出度是完全隨機的(如Waxman模型),或者認為節(jié)點出度是正規(guī)的(如Tiers模型).而冪律的發(fā)現(xiàn)證明了Internet拓撲結(jié)構(gòu)介于兩者之間,呈冪率分布.根據(jù)對出度頻率分布的刻畫,可將Internet拓撲模型分為以下3類:
隨機型,即認為Internet拓撲圖處于一個完全無序的狀態(tài),在大尺度上是均一的.Waxman模型，是一種類似于Erds-Rényi模型的隨機模型,出度頻率呈泊松分布.這個模型有兩個版本:RG1,先將節(jié)點隨機布置在直角坐標網(wǎng)格中,節(jié)點間的距離就是其歐幾里德距離;RG2,依據(jù)(0,L)均勻隨機分布為節(jié)點對指定距離.兩個版本中,節(jié)點間相接的概率P(u,v)與其距離相關(guān),服從泊松分布,距離越近,概率越大.
其中,d(u,v)表示節(jié)點u與v之間的距離,L為節(jié)點間最長距離,á與a取值范圍是(0,1).
?層次型,來自對Internet結(jié)構(gòu)所具有的層次特征的認識,在同一層上的節(jié)點出度接近,不同層間節(jié)點出度差別很大.對同一層上的節(jié)點布置借用Waxman模型方法.Tiers(等級)模型將Internet劃分為LAN(局域網(wǎng)),MAN(城域網(wǎng))和WAN(廣域網(wǎng))3個層次.在該模型中,WAN只有一個,通過指定LAN和MAN數(shù)量以及各自內(nèi)部所包含節(jié)點的數(shù)量來構(gòu)造拓撲圖.Transit-Stub模型將AS域劃分為Transit類和Stub類.在該模型中,Transit節(jié)點彼此互聯(lián)構(gòu)成一個節(jié)點群,一個或多個Transit節(jié)點群構(gòu)成拓撲圖的核心,而Stub節(jié)點分布在Transit節(jié)點群四周與Transit節(jié)點相連.Transit -Stub是GT-ITM(georgia tech Internetwork topology models)軟件包的一部分,有時GT-ITM也就是指Transit-Stub模型.
冪率型.1999年,Faloutsos等人對NLANR(National Lab for Applied Network Research)在1997~1998年間的3份BGP數(shù)據(jù)以及1995年的一份traceroute測量數(shù)據(jù)進行分析,發(fā)現(xiàn)Internet拓撲中存在著4條冪律.
冪律是指形如的方程,對于兩個變量X和Y,存在一個常數(shù)C,使得Y與X的C次冪成比例.有兩個聲明:(1) 節(jié)點v的等級為,v是在按出度降序排列序列中的索引值;(2) 鄰接矩陣特征值按降序排列,第i個特征值為li.冪律1(等級指數(shù)R):節(jié)點出度dv與該節(jié)點等級rv的R次冪成比例.冪律2(出度指數(shù)O):出度頻率fd與該出度d的O次冪成比例.
近似冪律(hop-plot指數(shù)H):h跳內(nèi)節(jié)點對(pairs of nodes)的數(shù)量與h的H次冪成比例.冪律3(特征指數(shù)E):特征值li與其次序i的E次冪成比例.
Small World網(wǎng)絡(luò)
在現(xiàn)實的Internet環(huán)境中，網(wǎng)絡(luò)拓撲并不完全滿足隨機網(wǎng)絡(luò)拓撲。Watt和Strogatz發(fā)現(xiàn)，只需要在規(guī)則網(wǎng)絡(luò)上稍作隨機改動就可以同時具備以上兩個性質(zhì)。改動的方法是，對于規(guī)則網(wǎng)絡(luò)的每一個頂點的所有邊，以概率p斷開一個端點，并重新連接，連接的新的端點從網(wǎng)絡(luò)中的其他頂點里隨機選擇，如果所選的頂點已經(jīng)與此頂點相連，則再隨機選擇別的頂點來重連。當p = 0時就是規(guī)則網(wǎng)絡(luò)，p = 1則為隨機網(wǎng)絡(luò)，對于0 < p < 1的情況，存在一個很大的p的區(qū)域，同時擁有較大的集聚程度和較小的最小距離。Small World網(wǎng)絡(luò)的幾何性質(zhì)如圖所示
平均路徑。圖中被隨機選擇又重新連結(jié)后的線稱為捷徑，它對整個網(wǎng)絡(luò)的平均路徑有著很大影響，分析表明:當p>=21(NK)，即在保證系統(tǒng)中至少出現(xiàn)一條捷徑的情況下，系統(tǒng)的平均路徑開始下降。即使是相當少的捷徑也能夠顯著地減小網(wǎng)絡(luò)的平均路徑長度。這是因為每出現(xiàn)一條捷徑，它對整個系統(tǒng)的影響是非線性的，它不僅影響到被這條線直接連著的兩點，也影響到了這兩點的最近鄰、次近鄰，以及次次近鄰等。
WS網(wǎng)絡(luò)的集團系數(shù)。r1初始固定的節(jié)點數(shù)可計算t1{ p=0時規(guī)則網(wǎng)絡(luò)的聚集系數(shù)為C(0), C(0)取決于網(wǎng)絡(luò)結(jié)構(gòu)而與尺寸N無關(guān)，因此有相對較大的值。隨著邊按一定的概率p隨機化，聚集系數(shù)在CYO}的附近變化。
度分布。WS模型是介于規(guī)則網(wǎng)絡(luò)和隨機網(wǎng)絡(luò)
來源文章：
P2P協(xié)議概述www.jouypub.com/2019/8f7e24e90c9f563030fa55be2957365d/
P2P中的核心技術(shù)www.jouypub.com/2019/8d6820c66a1b868b668b837d9ee3f6f2/
轉(zhuǎn)載本站文章《再談P2P技術(shù)：網(wǎng)絡(luò)拓撲結(jié)構(gòu)、核心技術(shù)分析》,
請注明出處：https://www.zhoulujun.cn/html/theory/ComputerScienceTechnology/network/2020_0125_8253.html
