分布式與云計算系統(tǒng)第8章

Chapter8:Peer-to-PeerComputing

andOverlayNetworks

對等計算和覆蓋網(wǎng)絡(luò)

18.1對等計算系統(tǒng)

P2P覆蓋網(wǎng)絡(luò)是構(gòu)建于互聯(lián)網(wǎng)上的虛擬網(wǎng)絡(luò)，由大量的邊緣客戶端計算機(jī)組成。

P2P計算系統(tǒng)已被廣泛應(yīng)用于分布式文件共享、消息傳遞、在線聊天、流媒體和社會網(wǎng)絡(luò)中。與傳統(tǒng)的分布式系統(tǒng)不同，P2P網(wǎng)絡(luò)是由分布在互聯(lián)網(wǎng)邊緣的節(jié)點（peer）或客戶端自由組成的自治和自組織系統(tǒng)。在P2P網(wǎng)絡(luò)中，節(jié)點之間共享計算和數(shù)據(jù)資源，所有節(jié)點按照自愿的方式共同提供豐富的在線服務(wù)。2圖8-1基于應(yīng)用趨勢的互聯(lián)網(wǎng)流量分布3P2P計算系統(tǒng)的基本概念對于端到端通信來說，如果兩個端用戶在功能上是對等、相同的，那么就可以認(rèn)為該通信是P2P通信。按照這個定義，早期的分布式系統(tǒng)都可以認(rèn)為是對等模式的。P2P技術(shù)利用互聯(lián)網(wǎng)邊緣節(jié)點空閑的計算資源（如存儲、CPU和帶寬）和內(nèi)容資源（如內(nèi)容文件）來完成大規(guī)模任務(wù)，比如大規(guī)模內(nèi)容分發(fā)、分布式搜索引擎和CPU受限的計算任務(wù)等。因為網(wǎng)絡(luò)邊緣節(jié)點上的資源在任意時刻都可能增加和移除，所以P2P網(wǎng)絡(luò)中的資源是間斷性可用的。P2P計算無需中央服務(wù)器的協(xié)調(diào)，沒有一個節(jié)點擁有全局的視圖，每個節(jié)點都只有系統(tǒng)的部分視圖。節(jié)點既作為服務(wù)器向其他節(jié)點直接提供服務(wù)，又作為客戶端從其他節(jié)點獲得服務(wù)。4P2P網(wǎng)絡(luò)具有下列共同的特征：去中心化：在純P2P計算系統(tǒng)中，節(jié)點在功能上是對等的，并不存在中央服務(wù)器來協(xié)調(diào)整個系統(tǒng)。每個節(jié)點僅有系統(tǒng)的部分視圖來構(gòu)建覆蓋網(wǎng)絡(luò)，控制其數(shù)據(jù)和資源。自組織：自組織意味著系統(tǒng)無需中央管理器來組織分散在所有節(jié)點上的計算和數(shù)據(jù)資源。P2P計算系統(tǒng)中的資源是動態(tài)或波動的，即資源可以隨時隨意地增加和移除。臨時連接和動態(tài)性：節(jié)點可能隨時加入或者離開，其可用性是不可預(yù)見的。這就導(dǎo)致覆蓋網(wǎng)絡(luò)拓?fù)浜拖到y(tǒng)規(guī)模以較大的幅度變化。

5匿名性：在去中心化的P2P網(wǎng)絡(luò)中，節(jié)點通過迂回路徑來發(fā)送和接收請求（即兩個節(jié)點借助一些中間節(jié)點通信），這個特點保證了發(fā)送者的匿名性。匿名性也可以借助哈希運算來實現(xiàn)?？蓴U(kuò)展性：P2P模型消除了傳統(tǒng)集中式客戶端/服務(wù)器模型中固有的單點失效問題，每個節(jié)點僅僅維護(hù)有限的系統(tǒng)狀態(tài)并和其他節(jié)點直接共享資源。這些特征使得P2P計算系統(tǒng)具有很高的可擴(kuò)展性。容錯：在P2P網(wǎng)絡(luò)中，所有節(jié)點在功能上是對等的，沒有節(jié)點支配整個系統(tǒng)。因此，單個節(jié)點不會造成系統(tǒng)的單點失效問題，資源可以存儲在多個節(jié)點來提高容錯能力。6客戶端/服務(wù)器體系結(jié)構(gòu)和P2P體系結(jié)構(gòu)的區(qū)別傳統(tǒng)的客戶端/服務(wù)器體系結(jié)構(gòu)由一臺服務(wù)器和與其連接的大量客戶端主機(jī)組成。P2P計算系統(tǒng)并不需要一臺中央服務(wù)器，而是由對等主機(jī)按照完全分布式的結(jié)構(gòu)組成的。也就是說，客戶端/服務(wù)器體系結(jié)構(gòu)是面向服務(wù)器的：服務(wù)器把任務(wù)分成多個子任務(wù)，并把子任務(wù)分配給客戶端，客戶端則獨立地完成分配的子任務(wù)；或者客戶端向服務(wù)器請求資源，而服務(wù)器把所請求的資源分發(fā)到客戶端。與此相反，在P2P網(wǎng)絡(luò)中，客戶端（節(jié)點）在功能上是對等的，是自治的、自組織的，它們之間直接交換資源。與客戶端/服務(wù)器系統(tǒng)相比，P2P系統(tǒng)相對松散而沒有結(jié)構(gòu)，安全性和可控性較低。

7

(a)Client-serverarchitecture(b)P2Pcomputingmodel

圖8-2客戶端/服務(wù)器體系結(jié)構(gòu)和P2P網(wǎng)絡(luò)模型的比較三種P2P網(wǎng)絡(luò)模型

P2P分布式計算系統(tǒng)通常維護(hù)一定數(shù)量的中央服務(wù)器用于任務(wù)管理或與客戶端對等節(jié)點的通信，但是客戶端對等節(jié)點之間卻不需要通信。因此在這種系統(tǒng)中，節(jié)點是貢獻(xiàn)資源的計算系統(tǒng)。P2P平臺作為中間件基礎(chǔ)方便P2P系統(tǒng)的開發(fā)和部署。該平臺提供安全服務(wù)、通信服務(wù)和標(biāo)準(zhǔn)服務(wù)9P2P應(yīng)用AAAAAA最流行的P2P應(yīng)用當(dāng)屬文件共享應(yīng)用，數(shù)據(jù)對象在P2P內(nèi)容網(wǎng)絡(luò)上分發(fā)給所有用戶。10圖8-4Skype體系結(jié)構(gòu)及其主要組件11圖8-5對于志愿者計算，SETI@Home工作負(fù)載的分發(fā)過程12P2P計算面臨的基礎(chǔ)挑戰(zhàn)節(jié)點資源異構(gòu)：對等節(jié)點在硬件、軟件和網(wǎng)絡(luò)方面都是異構(gòu)的系統(tǒng)規(guī)模可擴(kuò)展性：系統(tǒng)的擴(kuò)展性直接與性能和帶寬相關(guān)。所需節(jié)點的高效定位：高效的數(shù)據(jù)或者節(jié)點定位算法的設(shè)計。數(shù)據(jù)局部性和網(wǎng)絡(luò)鄰近性：數(shù)據(jù)局部性和網(wǎng)絡(luò)鄰近性是現(xiàn)代P2P應(yīng)用的兩個主要設(shè)計目標(biāo)。數(shù)據(jù)局部性是指具有相似屬性值的數(shù)據(jù)保存在覆蓋網(wǎng)絡(luò)拓?fù)渲朽徑墓?jié)點上，是實現(xiàn)復(fù)雜查詢操作和快速數(shù)據(jù)定位的有效方法。網(wǎng)絡(luò)鄰近性是由底層物理IP網(wǎng)絡(luò)中兩個節(jié)點的距離來度量的。

13圖8-6構(gòu)建網(wǎng)絡(luò)鄰近性感知的P2P覆蓋網(wǎng)絡(luò)14

路由效率：路由算法直接影響著系統(tǒng)的性能。純P2P系統(tǒng)雖然不存在單點失效問題，但仍然面臨連接中斷、目的不可達(dá)、網(wǎng)絡(luò)圖分割和節(jié)點失效等問題。避免“搭便車”：P2P系統(tǒng)依賴于互聯(lián)網(wǎng)邊緣的資源聚集來提高性能，但是參與節(jié)點可能是自私的，不愿意貢獻(xiàn)任何資源，這就造成了“搭便車”問題。解決該問題的方法是激勵機(jī)制。匿名和隱私：P2P系統(tǒng)中的節(jié)點希望隱藏自己的信息。匿名是節(jié)點的一個選擇，特別是對于P2P通信系統(tǒng)中的節(jié)點。15圖8-7基于“洋蔥式”路由的匿名通信舉例

16

信任和信譽(yù)管理：要求系統(tǒng)提供一種可信的環(huán)境。節(jié)點的信任是可以度量的，而且惡意節(jié)點會受到處罰。然而P2P系統(tǒng)是完全分布式的，節(jié)點之間的交互是直接進(jìn)行的，并不需要經(jīng)過中央服務(wù)器。網(wǎng)絡(luò)威脅和攻擊防御：P2P系統(tǒng)分散和自組織的特點使得實施針對系統(tǒng)的攻擊非常容易。拒絕服務(wù)和分布式拒絕服務(wù)攻擊可以通過對其他節(jié)點宣稱目標(biāo)節(jié)點擁有請求的所有文件并向目標(biāo)節(jié)點泛洪消息來實現(xiàn)，而服務(wù)質(zhì)量攻擊則可以通過以較慢的速度發(fā)送文件或者發(fā)送異于請求的文件來實現(xiàn)。此外，P2P系統(tǒng)匿名特性有利于惡意節(jié)點對外隱藏信息，更不容易被發(fā)現(xiàn)。

17圖8-8P2P網(wǎng)絡(luò)中通過消息泛洪實現(xiàn)的DDoS攻擊舉例18

抗擾動（ChurnResilience）：P2P計算系統(tǒng)中的節(jié)點來自互聯(lián)網(wǎng)邊緣的客戶端，它們可能隨時加入、離開，甚至失效。節(jié)點失效使得容錯成為P2P網(wǎng)絡(luò)面臨的巨大挑戰(zhàn)。抵御共謀盜版：網(wǎng)上盜版阻礙了P2P文件共享系統(tǒng)合法化和商業(yè)化。不合法文件內(nèi)容從擁有合法內(nèi)容的節(jié)點處散播給盜版者，這種行為稱為共謀。共謀盜版是P2P網(wǎng)絡(luò)中知識產(chǎn)權(quán)侵犯的主要來源。

19P2P網(wǎng)絡(luò)系統(tǒng)分類圖8-9按照功能和設(shè)計模式對P2P系統(tǒng)進(jìn)行分類20無結(jié)構(gòu)P2P覆蓋網(wǎng)絡(luò)無結(jié)構(gòu)P2P覆蓋網(wǎng)絡(luò)的鄰居關(guān)系以一種沒有約束的隨機(jī)方式建立。當(dāng)用戶匿名性和低管理開銷是系統(tǒng)設(shè)計目標(biāo)時，無結(jié)構(gòu)覆蓋網(wǎng)絡(luò)是較好的選擇。無結(jié)構(gòu)P2P覆蓋網(wǎng)絡(luò)的特征：數(shù)據(jù)隨機(jī)分布在節(jié)點上。覆蓋網(wǎng)絡(luò)由集中式控制開始，逐漸轉(zhuǎn)移到完全去中心化控制。沒有廣播機(jī)制（即使有，也是非常受限的）。在整個網(wǎng)絡(luò)上的泛洪查詢產(chǎn)生大量網(wǎng)絡(luò)流量。沒有確定性搜索結(jié)果的保障。TTL(timetolive，存活時間)受限的查詢消息可能到達(dá)整個網(wǎng)絡(luò)。21結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)在結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)中，對等節(jié)點按照預(yù)先定義好的結(jié)構(gòu)組織，結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)的一些有用特征：覆蓋網(wǎng)絡(luò)上的結(jié)構(gòu)化路由機(jī)制。在節(jié)點之上增加應(yīng)用層覆蓋網(wǎng)絡(luò)。和基于隨機(jī)圖的覆蓋網(wǎng)絡(luò)相比，路由跳數(shù)低。消除了泛洪和熱點區(qū)域問題。保證搜索結(jié)果。提供對等節(jié)點之間的負(fù)載均衡。提供良好的可擴(kuò)展性和容錯能力。如果需要，可以保持?jǐn)?shù)據(jù)的局部性。在拓?fù)涫芟薜那闆r下提供自組織能力。提供增強(qiáng)的安全保護(hù)。支持節(jié)點異構(gòu)。228．2P2P覆蓋網(wǎng)絡(luò)及其性質(zhì)覆蓋網(wǎng)絡(luò)是建立在物理IP網(wǎng)絡(luò)上的，其中的節(jié)點是來自物理網(wǎng)絡(luò)的主機(jī)，而鏈路則是節(jié)點之間的TCP連接或者是簡單地指向IP地址的指針。這個虛擬鏈路不一定具有相同的權(quán)重，可根據(jù)鏈路的類型來為鏈路賦予不同的權(quán)重。由于終端主機(jī)是動態(tài)的，需要拓?fù)渚S護(hù)協(xié)議來維護(hù)覆蓋網(wǎng)絡(luò)。新節(jié)點借助已經(jīng)在覆蓋網(wǎng)絡(luò)中的節(jié)點來加入覆蓋網(wǎng)絡(luò)，而節(jié)點之間使用周期性心跳消息來探測鄰居是否存活。如果鄰居失效，節(jié)點需要按照維護(hù)協(xié)議選擇其他節(jié)點連接。23

物理IP網(wǎng)絡(luò)中的主機(jī)可以映射到由虛擬鏈路建立的覆蓋網(wǎng)絡(luò)。在圖1-17中，垂直虛線表示了從物理主機(jī)到虛擬節(jié)點（也稱為對等節(jié)點）的映射關(guān)系。覆蓋網(wǎng)絡(luò)不需要額外的物理設(shè)施，因此易于部署和使用，而且其拓?fù)湟部梢愿鶕?jù)應(yīng)用來改變。節(jié)點失效處理較為容易，因為節(jié)點可以選擇其他仍然存活的節(jié)點連接。通信協(xié)議沒有任何限制，應(yīng)用設(shè)計者可以根據(jù)需要設(shè)計任意協(xié)議。底層物理網(wǎng)絡(luò)對于覆蓋網(wǎng)絡(luò)設(shè)計者來說是透明的，但是為了更好地利用網(wǎng)絡(luò)資源（如網(wǎng)絡(luò)鄰近性），設(shè)計者則需要考慮物理網(wǎng)絡(luò)。24圖1-17通過映射物理IP網(wǎng)絡(luò)到一個覆蓋網(wǎng)絡(luò)絡(luò)建立虛擬鏈接的P2P系統(tǒng)結(jié)構(gòu)25P2P網(wǎng)絡(luò)是一種覆蓋網(wǎng)絡(luò)。根據(jù)覆蓋圖的性質(zhì)，P2P網(wǎng)絡(luò)可以分為兩類：無結(jié)構(gòu)覆蓋網(wǎng)絡(luò)和結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)。無結(jié)構(gòu)覆蓋網(wǎng)絡(luò)通常基于隨機(jī)圖來建立，節(jié)點隨機(jī)從覆蓋網(wǎng)絡(luò)中選擇節(jié)點作為鄰居。與其相反，結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)圖則具有事先定義好的結(jié)構(gòu)（比如環(huán)、超立方體等），每個節(jié)點具有唯一的標(biāo)識而且只能和那些標(biāo)識滿足預(yù)先定義條件的節(jié)點連接。有些P2P覆蓋網(wǎng)絡(luò)則是無結(jié)構(gòu)和結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)的混合，具有無結(jié)構(gòu)和結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)的優(yōu)點。26無結(jié)構(gòu)P2P覆蓋網(wǎng)絡(luò)為了構(gòu)建一個好的無結(jié)構(gòu)P2P覆蓋網(wǎng)絡(luò)，節(jié)點的度（即鄰居的數(shù)目）以及從一個節(jié)點到另一個節(jié)點所經(jīng)過的節(jié)點數(shù)目應(yīng)該盡量小。此外，加入或離開操作不能對覆蓋網(wǎng)絡(luò)拓?fù)鋱D造成大的變動。最后，在節(jié)點失效或者意想不到地離開時，覆蓋網(wǎng)絡(luò)仍然可以確定消息轉(zhuǎn)發(fā)路徑?；陔S機(jī)圖的覆蓋網(wǎng)絡(luò)構(gòu)建：ER（ErdosRenyi）隨機(jī)圖可以看做是無結(jié)構(gòu)P2P覆蓋網(wǎng)絡(luò)構(gòu)建的基礎(chǔ)模型。任意兩個頂點（節(jié)點）有一條邊的概率p是相同和獨立的。對于無結(jié)構(gòu)P2P系統(tǒng)來說，ER隨機(jī)圖過于隨機(jī)化，設(shè)計分布式路由算法非常困難。27

小世界（Small-World）模型：有兩個顯著的特性：平均最短路徑小和聚類系數(shù)高。前者可以減少節(jié)點之間的跳數(shù)，而后者有利于處理大量用戶或者任務(wù)同時到來的問題。在小世界模型的P2P網(wǎng)絡(luò)中，每個節(jié)點有兩類鄰居，即近鄰居和遠(yuǎn)鄰居。無標(biāo)度圖：節(jié)點的度服從冪律分布，即一個節(jié)點的度為k的概率與k-α成正比，其中α是一個介于(2,3)的常數(shù)。當(dāng)圖的規(guī)模增大時，直徑變化并不大。

P2P分布式文件共享系統(tǒng)：無結(jié)構(gòu)P2P網(wǎng)絡(luò)最流行的應(yīng)用當(dāng)屬P2P文件共享系統(tǒng)。數(shù)據(jù)隨機(jī)分布在節(jié)點上，使用泛洪算法來查找所需的文件。為了減少泛洪產(chǎn)生的大量流量，查找消息帶有TTL以限制泛洪的范圍。而且系統(tǒng)并不對搜索結(jié)果進(jìn)行保證。2829圖8-10Gnutella系統(tǒng)中的泛洪搜索機(jī)制，用于搜索能提供數(shù)字內(nèi)容文件的節(jié)點圖8-11Gnutella數(shù)據(jù)包描述符格式30分布式哈希表（DHT）分布式哈希表作為中間件為分布式系統(tǒng)（特別是P2P系統(tǒng)）提供信息搜索或者表查詢服務(wù)。哈希表由（鍵，值）對組成，DHT把這種哈希對存儲在標(biāo)識空間。圖8-12分布式哈希表的鍵值映射31圖8-13DHT在快速、安全搜索和其他互聯(lián)網(wǎng)應(yīng)用中的運用

DHT部署：DHT作為基礎(chǔ)提供兩種原語，其核心思想是把節(jié)點和鍵映射到標(biāo)識空間并把鍵分配給近距離的節(jié)點。DHT能夠?qū)崿F(xiàn)快速搜索，而且這種搜索具有可證明的搜索時間上限。此外，DHT覆蓋網(wǎng)絡(luò)避免了泛洪造成的大量搜索成本，具有更好的可擴(kuò)展性。

32結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)是基于DHT的.

使用全局統(tǒng)一的協(xié)議來保證任何節(jié)點都能夠高效路由搜到擁有所需文件的節(jié)點，無論文件是稀缺的還是擁有大量副本，這就要求覆蓋網(wǎng)絡(luò)鏈接具有更多結(jié)構(gòu)化模式。最常見的結(jié)構(gòu)化P2P網(wǎng)絡(luò)是DHT覆蓋網(wǎng)絡(luò)。分布式哈希表：使用分布式哈希實現(xiàn)鍵查詢，失去了數(shù)據(jù)的局部性，但避免了泛洪查詢。樹狀結(jié)構(gòu)系統(tǒng)：樹狀結(jié)構(gòu)的層次化數(shù)據(jù)訪問維持了數(shù)據(jù)的局部性。基于跳躍表的系統(tǒng)：通過鍵排序而不是鍵查找來加快查詢處理。33AAAAAA34圖8-14使用16個鍵搜索空間組成的Chord網(wǎng)絡(luò)的例子。指針表建立了位于不同區(qū)域節(jié)點之間的鏈接35圖8-15通過重復(fù)分割二維坐標(biāo)空間而構(gòu)成的CAN網(wǎng)絡(luò)及其路由過程36混合式覆蓋網(wǎng)絡(luò)混合式P2P覆蓋網(wǎng)絡(luò)同時具有無結(jié)構(gòu)和結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)的特征。通常有兩種方法來建立混合覆蓋網(wǎng)絡(luò)。第一種是在無結(jié)構(gòu)覆蓋網(wǎng)絡(luò)上增加結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)?；旌螾2P覆蓋網(wǎng)絡(luò)通常保留每種覆蓋網(wǎng)絡(luò)的主要組件，而次要組件則以無開銷方法獲得。Pastry節(jié)點的路由表由基于興趣的覆蓋網(wǎng)絡(luò)的集群來提供，而基于興趣的覆蓋網(wǎng)絡(luò)中的全局隨機(jī)節(jié)點信息由Pastry的葉子節(jié)點集提供。37圖8-16構(gòu)建混合P2P覆蓋網(wǎng)絡(luò)：保持主要組件而借助無開銷的方法構(gòu)建次要組件38圖8-18Gnutella和Chord的混合P2P體系結(jié)構(gòu)39圖8-17由超級節(jié)點構(gòu)成骨干覆蓋網(wǎng)絡(luò)的KaZaA體系結(jié)構(gòu)第二種是使用超級節(jié)點構(gòu)造骨干覆蓋網(wǎng)絡(luò)

40418．3路由、鄰近性和容錯

P2P系統(tǒng)的兩個基本技術(shù)，即路由和局部性感知。路由算法計算如何從一個節(jié)點到達(dá)另一個節(jié)點，應(yīng)該是分布式的且僅依賴于整個系統(tǒng)本地視圖中的節(jié)點。局部性感知又稱為網(wǎng)絡(luò)鄰近性感知，它使得對等節(jié)點與其物理上鄰近的節(jié)點相連，以便減小平均覆蓋網(wǎng)絡(luò)鏈路延遲和骨干網(wǎng)帶寬消耗。

P2P覆蓋網(wǎng)絡(luò)是非正式的。因此，系統(tǒng)需要相應(yīng)的機(jī)制來容忍和恢復(fù)節(jié)點的失效和斷開。42P2P覆蓋網(wǎng)絡(luò)的路由在無結(jié)構(gòu)P2P覆蓋網(wǎng)絡(luò)中，因為節(jié)點的鄰居是不受任何限制而隨機(jī)選擇的，所以無法定位一個特定的節(jié)點，而其中的路由算法通常是基于泛洪的。當(dāng)一個節(jié)點A從鄰居節(jié)點B收到消息后，它簡單地把消息轉(zhuǎn)給發(fā)除B以外的所有鄰居。在一個由n個平均度（鄰居的數(shù)目）為k的節(jié)點組成的覆蓋網(wǎng)絡(luò)中，定位一個節(jié)點平均需要使用n(k-1)個消息。因為消息是按照最短路徑從源到達(dá)目的節(jié)點的，所以路由復(fù)雜度（即從任意節(jié)點到達(dá)某個特定節(jié)點所需的覆蓋網(wǎng)絡(luò)跳數(shù)）直接由覆蓋網(wǎng)絡(luò)圖的直徑?jīng)Q定?；谛∈澜鐖D的覆蓋網(wǎng)絡(luò)直徑小，路由復(fù)雜度低。Freenet就是這樣一種覆蓋網(wǎng)絡(luò)。43圖8-19Freenet中節(jié)點的數(shù)據(jù)存儲棧舉例44圖8-20Chord覆蓋網(wǎng)絡(luò)中的表查詢路由舉例

基于DHT的結(jié)構(gòu)化覆蓋網(wǎng)絡(luò)有嚴(yán)格的、事先定義好的結(jié)構(gòu)，這有利于消息的路由。路由的過程就是逐漸減少消息處理節(jié)點到目的節(jié)點在標(biāo)識空間上的距離。盡管不同結(jié)構(gòu)的覆蓋網(wǎng)絡(luò)有不同的路由協(xié)議，但路由復(fù)雜度通常在O(logn)跳，其中n是節(jié)點的數(shù)目。基于DHT的Chord網(wǎng)絡(luò)的表查詢路由:45P2P覆蓋網(wǎng)絡(luò)中的網(wǎng)絡(luò)鄰近性

P2P覆蓋網(wǎng)絡(luò)是構(gòu)建于IP網(wǎng)絡(luò)上的邏輯結(jié)構(gòu)，盡管基于隨機(jī)圖的覆蓋網(wǎng)絡(luò)具有良好的容錯能力和較低的直徑，但這樣的覆蓋網(wǎng)絡(luò)忽略了IP網(wǎng)絡(luò)上的網(wǎng)絡(luò)鄰近信息，從而導(dǎo)致物理上鄰近的節(jié)點在覆蓋網(wǎng)絡(luò)上彼此相距很遠(yuǎn)，而覆蓋網(wǎng)絡(luò)上鄰近的節(jié)點在物理網(wǎng)絡(luò)上彼此也相距很遠(yuǎn)。這種現(xiàn)象稱為拓?fù)洳黄ヅ洌Y(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)同樣存在該問題對于結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)來說，節(jié)點的鄰居選擇是嚴(yán)格受其結(jié)構(gòu)限制的，507根據(jù)網(wǎng)絡(luò)鄰近性感知原則優(yōu)化它們是比較難的。在結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)中，有三種方法來實現(xiàn)網(wǎng)絡(luò)鄰近性：地理布局、鄰近路由和鄰近鄰居選擇。46容錯和失效恢復(fù)

錯誤和節(jié)點失效:節(jié)點失效將導(dǎo)致該節(jié)點的覆蓋網(wǎng)絡(luò)連接中斷，嚴(yán)重影響P2P覆蓋網(wǎng)絡(luò)連接性。節(jié)點失效對覆蓋網(wǎng)絡(luò)連通性影響的程度依賴于覆蓋網(wǎng)絡(luò)圖的性質(zhì)和失效節(jié)點的度。例如，在基于冪律圖的P2P覆蓋網(wǎng)絡(luò)中，部分節(jié)點的隨機(jī)失效并不會將覆蓋網(wǎng)絡(luò)分割為不連接的幾個部分。然而一些度高的節(jié)點失效很容易損害覆蓋網(wǎng)絡(luò)，從而導(dǎo)致覆蓋網(wǎng)絡(luò)分割為若干個不連接部分。47

失效恢復(fù)分析：由于失效是經(jīng)常發(fā)生的，P2P系統(tǒng)需要有效的從節(jié)點失效恢復(fù)，如Chord借助周期性穩(wěn)定操作來解決節(jié)點失效。另一種方法是讓節(jié)點周期性地從指針表中隨機(jī)選擇鄰居來檢測是否活躍。容錯技術(shù)：和傳統(tǒng)的基于客戶端/服務(wù)器模型的分布式系統(tǒng)不同，在P2P系統(tǒng)中沒有一個節(jié)點擁有全局視圖，節(jié)點依賴局部視圖來發(fā)現(xiàn)錯誤并以完全分散的方式從失效中恢復(fù)。P2P覆蓋網(wǎng)絡(luò)通過冗余來保證穩(wěn)定的吞吐量。錯誤分析：容錯方面的工作需要考慮鄰近信息感知的覆蓋網(wǎng)絡(luò)中的容錯。48抗擾動與失效

P2P網(wǎng)絡(luò)經(jīng)常面臨由節(jié)點擾動帶來的問題，節(jié)點擾動來源于非預(yù)期節(jié)點加入、離開或者失效。

節(jié)點失效或者突然離開對網(wǎng)絡(luò)性能有非常不利的影響，因為失效節(jié)點上存儲的數(shù)據(jù)將變得不再可用，而正在從失效節(jié)點請求服務(wù)的節(jié)點需要重新定位服務(wù)。

P2P覆蓋網(wǎng)絡(luò)應(yīng)該具有容錯能力和抗擾動能力。

49圖8-21基于CRP的覆蓋網(wǎng)絡(luò)設(shè)計舉例50圖8-22P2P網(wǎng)絡(luò)中的5種數(shù)據(jù)分發(fā)機(jī)制的平均分發(fā)時間比較518．4信任、信譽(yù)和安全管理對等節(jié)點的匿名性和動態(tài)性導(dǎo)致P2P網(wǎng)絡(luò)容易受到自私和惡意節(jié)點的攻擊。大多數(shù)P2P文件共享網(wǎng)絡(luò)由利己自治節(jié)點組成，目前并沒有有效的辦法來阻止惡意節(jié)點加入P2P這種開放的網(wǎng)絡(luò)。為了鼓勵節(jié)點貢獻(xiàn)資源并抵御惡意節(jié)點的行為，信任和信譽(yù)管理對P2P網(wǎng)絡(luò)變得異常重要。如果沒有信任，節(jié)點向其他節(jié)點貢獻(xiàn)資源的動機(jī)會很小。因為擔(dān)心接收到被毀壞或污染的文件或者被惡意軟件利用，節(jié)點可能不愿意和不熟悉的節(jié)點交互。為了識別出可信任的節(jié)點，商用P2P應(yīng)用（如在線商店、拍賣、內(nèi)容分發(fā)和每次交易付費的應(yīng)用等）需要信譽(yù)系統(tǒng)的支持。52節(jié)點信任和信譽(yù)系統(tǒng)節(jié)點信任特征有兩種方法來模型化節(jié)點之間的信任或者不信任，即信任和信譽(yù)。信任指的是一個節(jié)點根據(jù)自己對某個節(jié)點的直接經(jīng)驗而產(chǎn)生的對該節(jié)點的信賴程度，而信譽(yù)則是根據(jù)其他節(jié)點推薦而產(chǎn)生的對某個節(jié)點的信賴。為了更好地應(yīng)對P2P開放網(wǎng)絡(luò)實際情況，必須假設(shè)P2P系統(tǒng)的參與節(jié)點互相并不信任，除非信任得到了證明。為了建立節(jié)點之間的信任或者不信任關(guān)系，需要構(gòu)建一個根據(jù)節(jié)點過去行為記錄而形成的信譽(yù)系統(tǒng)。系統(tǒng)的目的是通過一個科學(xué)的篩選過程把“好”節(jié)點和“壞”節(jié)點區(qū)分開來。信譽(yù)系統(tǒng)的性能主要由其周期性更新中的準(zhǔn)確性和效率來衡量。530000.20.80.60000.4TrustMatrix

M(t)=00.7000.3000000.9000.10計算信譽(yù)所使用的信任矩陣54圖8-23P2P網(wǎng)絡(luò)中5個節(jié)點的信任關(guān)系有向圖55信譽(yù)系統(tǒng)可以構(gòu)建一個評估系統(tǒng)來測量節(jié)點的信譽(yù)。在每次交易后，參與交易的節(jié)點互評對方，給出誠實的分?jǐn)?shù)，這和我們目前在eBay等在線拍賣系統(tǒng)所做的一樣。但是并不是每個節(jié)點都是可信的，惡意節(jié)點給出的分?jǐn)?shù)是沒有意義的，而越可信的節(jié)點給出的分?jǐn)?shù)越有意義。這說明需要根據(jù)節(jié)點的信譽(yù)來為反饋分?jǐn)?shù)給予不同的權(quán)重。節(jié)點的信譽(yù)可能和別的節(jié)點不同，信譽(yù)可以用一個信譽(yù)矩陣來表示。56全局信譽(yù)聚集

ReputationVector

V(t)

={v1(t),v2(t),v3(t),v4(t),v5(t)}

={0.32,0.001,0.009,0.04,0.63}v5(t+1)=m15(t)×v1(t)+m25(t)×v2(t)+m35(t)×v3(t)

=0.8×0.32+0.4×0.001+0.3×0.009=0.2573GlobalReputationScoreofNode5V(t+1)

={v1(t+1),v2(t+1),v3(t+1),v4(t+1),v5(t+1}={0.5673,0.0063,0,0.1370,0.2573}

GlobalReputationVectorNormalizedGlobalReputationVector

V(t+1)

={v1(t+1),v2(t+1),v3(t+1),v4(t+1),v5(t+1)}={0.5862,0.0065,0,0.1416,0.2657}57信譽(yù)系統(tǒng)的設(shè)計目標(biāo)高準(zhǔn)確性：系統(tǒng)計算所得的信譽(yù)分?jǐn)?shù)需要盡量和節(jié)點真實的可信度一致?？焖偈諗浚汗?jié)點的信譽(yù)是隨時間變化的，信譽(yù)集群化應(yīng)該快速收斂以反映節(jié)點行為的真實變化。低開銷：為了監(jiān)測和評估節(jié)點的信譽(yù)，系統(tǒng)只應(yīng)該消耗有限的計算和帶寬資源。自適應(yīng)節(jié)點動態(tài)性：信譽(yù)系統(tǒng)都應(yīng)該能夠適應(yīng)節(jié)點的動態(tài)性，而不是依賴于預(yù)先確定的節(jié)點。針對惡意節(jié)點的魯棒性：系統(tǒng)應(yīng)該具有良好的魯棒性?？蓴U(kuò)展性：就準(zhǔn)確性、收斂速度和節(jié)點額外開銷等指標(biāo)評價來說，信譽(yù)系統(tǒng)應(yīng)該能夠擴(kuò)展到包含大量節(jié)點的P2P系統(tǒng)。5859信任覆蓋網(wǎng)絡(luò)和DHT實現(xiàn)

信任覆蓋網(wǎng)絡(luò)（TON）建立在P2P系統(tǒng)之上的虛擬網(wǎng)絡(luò)。該網(wǎng)絡(luò)用有向圖表示的，其中TON圖中的節(jié)點對應(yīng)P2P系統(tǒng)中的節(jié)點。有向邊或者連接的權(quán)重是兩個交互節(jié)點的反饋分?jǐn)?shù)。該分?jǐn)?shù)是由連接的源節(jié)點生成的，用來評估與其交互的節(jié)點（連接的目的）所提供的服務(wù)。例如，節(jié)點N5在從N2和N7下載完音樂文件后對兩個文件提供節(jié)點分別生成值為0.7和0.3的反饋分?jǐn)?shù)。如果一個節(jié)點從同一提供商處獲得多個服務(wù)，那么該節(jié)點在每次交易后產(chǎn)生更新后的分?jǐn)?shù)。60圖8-24用于P2P信任管理的信任覆蓋網(wǎng)絡(luò)，其中邊的權(quán)重是節(jié)點對所提供服務(wù)的反饋分?jǐn)?shù)。一個節(jié)點的全局信譽(yù)值是所有入邊代表的本地（局部）信任值的加權(quán)和61DHT實現(xiàn)分布式信譽(yù)排名需要兩個不同的哈希覆蓋網(wǎng)絡(luò)，一個把節(jié)點分配給它們的信譽(yù)分?jǐn)?shù)管理者，另一個根據(jù)節(jié)點的全局信譽(yù)分?jǐn)?shù)對節(jié)點排序。

圖8-25分布式信譽(yù)排名，使用了建立在基于DHT的P2P系統(tǒng)之上的局部性保持哈希函數(shù)62圖8-26PowerTrust系統(tǒng)功能模塊，系統(tǒng)用來聚集信任分?jǐn)?shù)并計算全局信譽(yù)值PowerTrust：可擴(kuò)展的信譽(yù)系統(tǒng)

63圖8-27P2P網(wǎng)絡(luò)中兩個信譽(yù)系統(tǒng)的收斂開銷比較信譽(yù)系統(tǒng)的收斂開銷64圖8-28兩種信譽(yù)系統(tǒng)比較：分布式文件系統(tǒng)中的查詢成功率查詢成功率65加強(qiáng)覆蓋網(wǎng)絡(luò)安全，抵御DDoS攻擊當(dāng)對等節(jié)點惡意攻擊其他無辜節(jié)點時，P2P網(wǎng)絡(luò)的安全性將存在問題。經(jīng)常發(fā)生的有4種網(wǎng)絡(luò)攻擊：如果大量的節(jié)點快速或者隨機(jī)地加入和離開，那么P2P系統(tǒng)將進(jìn)入擾動模式。針對目標(biāo)節(jié)點的泛洪攻擊導(dǎo)致的分布式拒絕服務(wù)攻擊（DDoS）。路由攻擊試圖重新路由消息以竊取內(nèi)容或者實施DDoS攻擊。攻擊者阻止請求數(shù)據(jù)的傳輸將導(dǎo)致存儲/檢索攻擊。為了抵御網(wǎng)絡(luò)擾動帶來的問題，可以強(qiáng)制節(jié)點簽名所有消息。為了處理DDoS攻擊，可以復(fù)制內(nèi)容并把內(nèi)容散播在網(wǎng)絡(luò)上。668.5P2P文件共享和版權(quán)保護(hù)

P2P技術(shù)使得節(jié)點之間以一種分布式的方式自由共享文件?？蛻舳耸紫冗M(jìn)行搜索操作以定位擁有所需文件的節(jié)點?？蛻舳酥苯訌奈募峁┕?jié)點下載文件。P2P文件共享的最終目標(biāo)是向所有請求者盡快分發(fā)內(nèi)容。P2P內(nèi)容緩存是提高內(nèi)容下載速度和流量本地化的有效手段?？焖偎阉?、副本和一致性對P2P文件共享應(yīng)用來說，搜索算法扮演著最重要的角色。評價搜索算法的指標(biāo)有兩個：查詢路徑長度和消息開銷。前者用到達(dá)目標(biāo)節(jié)點前查詢消息經(jīng)過的節(jié)點平均數(shù)目衡量，而后者則用搜索操作產(chǎn)生的查詢消息平均數(shù)目來衡量。67

在結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)中，數(shù)據(jù)對象的鍵和節(jié)點映射到同一標(biāo)識空間，節(jié)點保存那些鍵映射到自己所負(fù)責(zé)標(biāo)識區(qū)域的數(shù)據(jù)對象。搜索算法和覆蓋網(wǎng)絡(luò)上的路由算法類似。然而在無結(jié)構(gòu)P2P覆蓋網(wǎng)絡(luò)應(yīng)用中，每個節(jié)點通常僅保存自己共享的數(shù)據(jù)對象信息，查詢消息在到達(dá)目的之前需要訪問大量節(jié)點。結(jié)構(gòu)化P2P覆蓋網(wǎng)絡(luò)中，每個節(jié)點負(fù)責(zé)一部分標(biāo)識空間。無結(jié)構(gòu)P2P覆蓋網(wǎng)絡(luò)所使用的搜索算法基本上可以歸為兩類：盲目搜索和有知識的搜索。盲目搜索適合于節(jié)點僅保存自己共享的文件信息的應(yīng)用，而有知識的搜索適用于節(jié)點保存其他節(jié)點共享的文件信息的應(yīng)用。盲目搜索通常又被稱為泛洪（flooding）算法。泛洪算法節(jié)點第一次收到消息后將轉(zhuǎn)發(fā)消息給k個隨機(jī)選擇的鄰居，直到消息的TTL減為0。查詢消息在覆蓋網(wǎng)絡(luò)中從請求節(jié)點出發(fā)以類似水波傳播的方式一輪接一輪地轉(zhuǎn)發(fā)。泛洪算法不可避免地帶來大量的消息開銷。68圖8-29BitTorrent系統(tǒng)體系結(jié)構(gòu)69圖8-30多個swarm組成的BitTorrent系統(tǒng)流程示意，每個swarm是不同的跟蹤器來協(xié)調(diào)跟蹤的70圖8-31一個副本組的輔助結(jié)構(gòu)副本和一致性副本技術(shù)是提升P2P文件共享應(yīng)用搜索性能的重要手段之一。覆蓋網(wǎng)絡(luò)上的數(shù)據(jù)副本越多，數(shù)據(jù)越容易搜索。與副本技術(shù)相關(guān)的一個重要問題是副本一致性的維護(hù)。71P2P內(nèi)容分發(fā)網(wǎng)絡(luò)

72圖8-32全球CDN概念，CDN使用了位于主要區(qū)域或國家的代理服務(wù)器全球內(nèi)容分發(fā)網(wǎng)絡(luò)

73

三種方法分發(fā)數(shù)據(jù)內(nèi)容：基于泛洪的方法、基于樹的方法和基于swarm的方法。74版權(quán)保護(hù)問題和解決方案

P2P網(wǎng)絡(luò)能夠高效地把大文件分發(fā)給大量節(jié)點。但目前的P2P網(wǎng)絡(luò)由于音樂、游戲、視頻和流行軟件的非法下載而被濫用。這不僅導(dǎo)致媒體和內(nèi)容產(chǎn)業(yè)蒙受了巨大的經(jīng)濟(jì)損失，也阻礙了P2P技術(shù)的商用。系統(tǒng)的目標(biāo)是阻止P2PCDN內(nèi)的共謀盜版行為，傳統(tǒng)CDN需要使用大量分布在WAN上的代理內(nèi)容服務(wù)器。內(nèi)容分發(fā)者需要在大量服務(wù)器上復(fù)制或者緩存內(nèi)容，維護(hù)這樣的CDN所需帶寬和資源是非常昂貴的。P2P內(nèi)容網(wǎng)絡(luò)大幅降低了內(nèi)容分發(fā)的成本，因為它不需要大量的內(nèi)容服務(wù)器，而是利用了開放網(wǎng)絡(luò)。由于每個節(jié)點都可以作為內(nèi)容提供商，因此，P2P網(wǎng)絡(luò)提高了內(nèi)容可用性。75圖8-33針對版權(quán)保護(hù)內(nèi)容分發(fā)的安全P2P平臺7677圖8-34可信P2P網(wǎng)絡(luò)中的預(yù)先污染，合法