專題3-P2P網(wǎng)絡體系結構(2013簡)

1、P2P網(wǎng)絡體系結構 概述n對等網(wǎng)絡(P2P網(wǎng)絡)是分布式系統(tǒng)和計算機網(wǎng)絡相結合的產(chǎn)物，在應用領域和學術界獲得了廣泛的重視和成功，被稱為“改變Internet的新一代網(wǎng)絡技術”。課程信息n教材q對等網(wǎng)絡：結構、應用與設計q陳貴海、李振華著，清華大學出版社，2007.9 P2P網(wǎng)絡的概念、發(fā)展、特點、應用nP2P：Peer to Peer對等網(wǎng)絡npeer指網(wǎng)絡結點在q行為上是自由的任意加入、退出，不受其它結點限制，匿名q功能上是平等的不管實際能力的差異q連接上是互聯(lián)的直接/間接，任兩結點可建立邏輯鏈接，對應物理網(wǎng)上的一條IP路徑n充分利用網(wǎng)絡帶寬、結點資源，提高工作效率從T/H,C/S到P2P-

2、計算模式的輪回實線表示物理連接，虛線表示邏輯連接nP2P的思想1956年提出（為什么今天成為現(xiàn)實？）n1999年Internet上第一個應用Napster，半年發(fā)展了5000萬用戶n其后涌現(xiàn)Gnutella, KaZaA, BitTorrent, eDonkey/eMule, Skypen此后q學術界重視q占據(jù)Internet一半以上的帶寬n不同類型P2P網(wǎng)絡幾乎同時出現(xiàn)，無明確界定，大致分類q混合式P2P網(wǎng)絡：C/S、P2P模式的混合q無結構P2P網(wǎng)絡：分布/松散的結構q結構化P2P網(wǎng)絡：準確、嚴格的結構n設計和實現(xiàn)P2P網(wǎng)絡應解決的基本問題q路由和定位、查詢和搜索、動態(tài)結點算法、容錯性nP

3、2P網(wǎng)絡的增強機制q數(shù)據(jù)復制、緩存、分片；負載均衡；拓撲一致性；匿名、聲譽、信任、安全性P2P網(wǎng)絡的優(yōu)勢一、充分利用網(wǎng)絡帶寬nP2P不通過服務器進行信息交換，無服務器瓶頸，無單點失效，充分利用網(wǎng)絡帶寬，如BT下載多個文件，可接近實際最大帶寬，HTTP及FTP很少有這樣的效果二、提高網(wǎng)絡工作效率n結構化P2P有嚴格拓撲結構，基于DHT，將網(wǎng)絡結點、數(shù)據(jù)對象高效均勻地映射到覆蓋網(wǎng)中，路由效率高三、開發(fā)了每個網(wǎng)絡結點的潛力n結點資源：計算能力及存儲容量n個人計算機并非永久聯(lián)網(wǎng)，是臨時性的動態(tài)結點，稱為“網(wǎng)絡邊緣結點”nP2P使內(nèi)容“位于中心”轉變?yōu)椤拔挥谶吘墶?，計算模式由“服務器集中計算”“分布式協(xié)

4、同計算”四、具有高可擴展性(scalability)n可擴展性衡量，當網(wǎng)絡結點總數(shù)增加時：q結點負載如何改變q為適應規(guī)模擴大而需要增加的額外設備的數(shù)量q任意兩個網(wǎng)絡結點通信效率如何改變，尤其是路由效率nP2P網(wǎng)絡中，結點間分攤通信開銷，無需增加設備，路由跳數(shù)增量小五、良好的容錯性n冗余方法n周期性檢測n結點自適應狀態(tài)維護P2P網(wǎng)絡的各種應用n文件共享：代替ftp，前述典型的P2P模型n多媒體傳輸：Skype（語音），PPLive（視頻）n實時通信：QQ、MSN Messenger、Skype，都支持C/S、P2P模式n協(xié)同工作：Groove虛擬辦公室n分布式數(shù)據(jù)存?。簭V域、海量，CFS、PAS

5、T、OceanStore、Granaryn分布式計算：GPU，Gnutella全球處理單元，計算任務由對等結點而非服務器分配，SETIHome，U.C. Berkeley搜索外星文明nP2P搜索引擎：第三代搜索引擎技術，離實用有差距n其它 第一代P2P網(wǎng)絡混合式P2P體系：Napster與BT內(nèi)容nNapsterP2P網(wǎng)絡的先驅(qū)nBitTorrent分片優(yōu)化的新一代混合式P2P網(wǎng)絡n第一代P2P網(wǎng)絡的特點 Napster：P2P網(wǎng)絡的先驅(qū)n世界上第一個應用性P2P網(wǎng)絡，混合式P2P體系最杰出的代表n1999年波士頓東北大學的Shawn Fanning開發(fā)Napster，用于MP3文件交流，與傳

6、統(tǒng)的提供音樂下載的網(wǎng)站不同，Napster服務器里無歌曲，僅有其它用戶硬盤上的文件的索引nNapster使用的軟件技術都是當時已有的，只是改變了軟件的應用體系，打破了客戶/服務器模式的瓶頸nNapster半年吸引了5000萬注冊用戶，最高時超過6100萬用戶一、Napster網(wǎng)絡的工作原理Napster網(wǎng)絡由兩個部分組成：nNapster用戶(peer)nNapster網(wǎng)站(N)是一個服務器機群q提供統(tǒng)一的用戶訪問接口q各自保存一部分用戶的共享文件索引信息npeer與固定的server相連q加入時，將自身信息（連接帶寬、存儲空間等）以及共享文件信息發(fā)送給server，server記錄信息內(nèi)容及

7、用戶位置（文件索引）q查詢時，peer將查詢消息發(fā)給server，server與其它server協(xié)作后回復表單（包括所有匹配的文件索引）q下載時，peer直接從索引中選取peer并與之建立連接、下載文件nNapster網(wǎng)站的功能q維護所有用戶的共享文件索引q監(jiān)控系統(tǒng)中每個用戶的狀態(tài)（用戶報告的連接帶寬、用戶連入時間、是否掉線）q刪除掉線用戶的索引，保證文件索引的時效性q響應用戶的查詢請求，查詢的返回消息中可包含帶寬等信息，便于用戶選擇連接Napster的性能分析n檢測結果與結論qNapster機群包括大約160臺服務器q每個用戶只與一臺服務器建立連接q新用戶加入網(wǎng)絡時，可以選擇是否報告連接帶寬

8、，但大多不報告，或者故意誤報以減少其他用戶從自己下載(自私性)q結點異構性很強，表現(xiàn)在連接帶寬、時延、連接時長、共享文件性等方面，如25%64Kbps，50%Cable DSL，20%3M以上；超過50%的連接時間6h的不到10%q用戶自私性：20%40%用戶幾乎從不提供文件共享，僅1%結點為文件提供者n因此，類似Napster的P2P網(wǎng)絡在設計、優(yōu)化時應考慮q結點異構性：讓不同能力的結點扮演不同的角色q協(xié)同傳輸:增加并行傳輸連接數(shù)目,避免系統(tǒng)瓶頸.q激勵機制:鼓勵上傳，限制或禁止自私結點使用網(wǎng)絡n進一步的發(fā)展，BitTorrent：q相同架構，但文件分片，使用散列函數(shù)映射q用戶有上傳義務q網(wǎng)

9、絡及用戶信息更新、BT種子維護由server中的Tracker完成，下載同一文件的用戶圍繞Tracker形成獨立子網(wǎng)，不同文件的Tracker在不同server上，將server分散化，成為P2P在國內(nèi)最成功的應用BitTorrent：分片優(yōu)化的新一代混合式P2P網(wǎng)絡nBT體系原理nBT分片機制nBT阻塞算法nBT性能分析nBT體系總結nP2P下載對硬盤的影響B(tài)T體系原理BT網(wǎng)絡的四個組成部分nBT網(wǎng)站：提供BT種子文件(即.torrent文件)搜索的服務器，每個服務器包含部分種子文件的索引n.torrent文件服務器：小型的種子數(shù)據(jù)庫nTracker(跟蹤服務器)：BT網(wǎng)絡和用戶信息的維護者

10、，幫助用戶交互，下載同一個文件的用戶圍繞Tracker形成一個獨立的子網(wǎng)nBT用戶：可同時下載多個文件BT用戶的下載步驟nBT用戶通過某個BT網(wǎng)站搜索文件，該網(wǎng)站將搜索請求重定向到網(wǎng)站鏡像，后者檢索并返回給用戶該文件的.torrent文件列表n用戶選擇列表中的.torrent文件，BT軟件啟動下載任務，并從Tracker獲得當前也在下載該文件的用戶信息nBT軟件與一定數(shù)量的用戶建立連接，下載文件并同時提供上傳n下載過程中每隔一段時間更新一次連接以保持整網(wǎng)的工作效率BT分片機制nBT將文件分為固定大小的分片(典型大小256KB)，每個用戶必須通知其他下載者自己擁有的分片，分片的完整性由散列函數(shù)保

11、證n分片流水作業(yè)：構架在TCP之上的應用層協(xié)議，同時發(fā)送多個請求，以避免在兩個分片發(fā)送之間的延遲，進一步，分片可以劃分為子分片(典型16KB)，BT一直保持幾個請求（通常是5個）被流水式地同時發(fā)送。流水作業(yè)選擇同時發(fā)送的請求數(shù)目的依據(jù)，是使大多數(shù)連接變得飽和以充分利用帶寬分片選擇策略n嚴格的優(yōu)先級（一個分片的下載）q一旦請求了某個分片的子分片，那么該分片的所有子分片具有更高優(yōu)先級，以盡可能快地獲得一個完整的分片n最少者優(yōu)先（中間階段/平穩(wěn)期）q盡量選擇所知用戶擁有數(shù)最少的分片作為下一個下載分片，以使網(wǎng)絡中最稀少的分片盡快擁有多個復制q下載者從Tracker了解哪些分片較少分片選擇策略n隨機的第

12、一個片段（文件下載最初階段）q當最少的分片只有一個用戶擁有時，為避免并發(fā)沖突，第一個分片先隨機選擇，完成下載后再切換到“最少者優(yōu)先”策略n最后階段模式（文件下載最后階段）q為加速最后階段下載，下載者向他所連接的所有用戶都發(fā)送某分片的子分片請求，一旦某個子分片到了，下載者就會向其他用戶發(fā)送cancel消息，以避免浪費帶寬BT阻塞算法nBT并不是由Tracker服務器集中分配資源，每個用戶自己有責任盡可能地提高自己的下載速率n下載者根據(jù)連接用戶提供的下載速率給予同等的上傳回報(tit-for-tat)；對合作者提供上傳服務，對不合作者進行臨時阻塞n一個好的阻塞算法應該利用所有可用的資源，為所有下載

13、者提供一致、可靠的下載速率，并適當懲罰只下載而不上傳的用戶nBT的阻塞算法(choking algorithm)q每隔20秒進行一次輪詢：前10秒計算出哪個用戶要被阻塞，然后將阻塞狀態(tài)保持10秒q10秒內(nèi)足夠TCP調(diào)整傳輸速率n最優(yōu)疏通(optimistic unchoking)q為發(fā)現(xiàn)更好的空閑連接，不能只向為自己提供最高下載速率的用戶提供上傳，而是每隔30秒，重新計算一次哪個連接應該是“最優(yōu)疏通”n反對冷落(anti-snubbing)q某個下載者可能被所連接的所有用戶阻塞，為緩解該問題，當從某個用戶那里一個分片也沒有得到，下載者認為被對方“冷落”，不再為對方提供上傳?！胺磳渎洹背３?/p>

14、致多個并發(fā)的“最優(yōu)疏通”，從而更快恢復下載速率n僅僅上傳q用戶完成下載后，優(yōu)先選擇可從自己得到更高上傳速率的用戶或剛好被所有人阻塞的用戶BT性能分析 Pouwelse et al., 2004,2005論文n流行性：應用廣泛，但BT網(wǎng)站、.torrent文件服務器及Tracker故障率較高，限制了網(wǎng)絡規(guī)模n可用性：同上，取決于服務器的可用性。實際較低，只有一半的BT網(wǎng)站鏡像可正常工作超過2.1天，種子服務器更少n下載性能：當時統(tǒng)計平均速度30KB/sn文件生命周期q該文件的種子生命期，由于服務器故障及用戶行為不確定性，差別很大q約17%的用戶下載完成后做種時間超過1小時，僅3%用戶做種時間超過

15、10小時n污染等級q加入到BT網(wǎng)絡中的共享文件的真實性q審查系統(tǒng)(moderation system)，三種角色：需要審查的提交者；不需要審查的提交者；審查者?？芍鸺壧嵘T體系總結nBT是混合式結構的P2P網(wǎng)絡，以BT網(wǎng)站、.torrent文件服務器和Tracker為核心，控制和幫助用戶共享文件n下載同一文件的用戶圍繞Tracker形成一個獨立的子網(wǎng)nBT限定用戶在下載的同時必須提供上傳，既提高了網(wǎng)絡效率，又杜絕了P2P網(wǎng)絡中的自私結點現(xiàn)象nBT將文件分片，分片又被劃分成子分片，子分片流水作業(yè)，并在文件下載的不同階段有不同的分片選擇策略以優(yōu)化性能。這是BT最大的特點，也是它高效的最本質(zhì)原因

16、nBT基于經(jīng)濟學規(guī)律的阻塞算法，優(yōu)化了網(wǎng)絡資源配置，增強了用戶間的協(xié)作nBT通過對文件和分片生成散列值，保證文件的完整性nBT提供了一定的安全機制，如文件審查、輸入驗證碼nBT服務器故障率高，導致可用性降低，且網(wǎng)絡規(guī)模受限，文件無持久性保證第一代P2P網(wǎng)絡的特點n拓撲結構q混合式(C/S+P2P)q星型拓撲結構，以服務器為核心n查詢與路由q用戶向服務器發(fā)出查詢請求，服務器返回文件索引q用戶根據(jù)索引與其它用戶進行數(shù)據(jù)傳輸q路由跳數(shù)為O(1)，即常數(shù)跳n容錯性：取決于服務器的故障概率（實際網(wǎng)絡中，由于成本原因，可用性較低）n自適應：靠服務器監(jiān)控實現(xiàn)自組織與自適應，只要服務器正常工作即可有效維護網(wǎng)絡

17、和結點信息n匿名性：一般不提供，但支持n增強機制：BT的文件分片、雙向傳輸、防范攻擊第二代P2P網(wǎng)絡無結構P2P體系Gnutella、KaZaA、eDonkey、FreenetGnutella：純分布式無結構P2PnGnutella的歷史qNullsoft公司，MP3播放軟件WinAmp的發(fā)明人Justin Frankel、Tom Pepper開發(fā)q2000年3月14日在網(wǎng)站上公開Gnutella軟件一個半小時后，母公司AOL(American Online)擔心步Napster后塵，關閉了網(wǎng)站q數(shù)千名MP3迷下載了軟件并公開與改造q其純分布式無結構P2P網(wǎng)絡思想廣泛流傳qGnutella已不

18、單純對應具體軟件，而是當作一種典型的無結構P2P網(wǎng)絡協(xié)議一、Gnutella體系的工作原理nGnutella協(xié)議0.4版(0.6版加入了超結點Ultrapeer，結構有變化)n協(xié)議開發(fā)者稱Peer為Servent(Server +Client)，網(wǎng)絡中只有peer，沒有servernGnutella覆蓋網(wǎng)上每個結點對應一臺實際的計算機n每條連接對應一條點到點的鏈路n覆蓋網(wǎng)上的連接由每個peer保存的“鄰居結點”信息確定，有一個鄰居結點即對應有一條邊n新結點加入時，必須首先連接到“眾所周知”幾乎總是在線的Gnutella結點(稱為“自舉”結點、“入口結點”)nGnutella網(wǎng)中的消息可以被廣播

19、或回播(back-propagate，沿廣播的反向路徑回傳消息)，協(xié)議設計的支持機制：q每條消息具有一個隨機產(chǎn)生的全局唯一標識符GUID(16字節(jié))以互相區(qū)分q每個結點緩存最近路由的消息以支持回播并阻止不必要的重廣播q每條消息都有TTL以避免過度消耗網(wǎng)絡資源Gnutella的典型消息n組成員消息：PING，PONGq新結點加入時廣播PING消息，或用來探測其它結點是否仍然存在(心跳)q結點收到PING消息后，可以決定是否回播PONG消息，以及是否將PING轉發(fā)給鄰居，PONG消息包含結點IP,port,共享文件數(shù)量大小n查詢消息：QUERY，QUERY RESPONSEqQUERY消息用來查詢

20、文件,包含查詢內(nèi)容與最小響應速度等附加信息,但不包含源結點信息qRESPONSE消息包含文件下載的必須信息及該結點的nodeID，沿QUERY消息路徑回播n文件傳輸消息：GET，PUSHq結點收到QUERY RESPONSE消息后用GET消息請求獲得文件q對處于防火墻后因而不能直接響應文件請求的結點，使用PUSH消息請求防火墻后的文件擁有者主動建立到自己的連接Gnutella的文件檢索過程n泛洪式搜索(flooding search)， 系統(tǒng)開銷大n有限深度TTL(Time to Live)， 不保證一定查詢到已有文件nGnutella網(wǎng)絡的維護q各結點使用PING、PONG消息探測其他結點存

21、在與否，在收到PING消息后，可以自主決定是否回播PONG，并根據(jù)TTL數(shù)值決定是否繼續(xù)廣播PING消息q具有一定的自組織和自適應性Gnutella網(wǎng)絡的性能分析nRipeanu,2001,2002、Saroiu et al., 2002,2003、Adar & Huberman, 2002nGnutella用戶的連接帶寬僅在Query response消息中作為輔助信息回播，因此，Gnutella網(wǎng)絡中不共享文件的用戶或其共享的文件與查詢請求一直不匹配的用戶，不會主動發(fā)布帶寬nGnutella網(wǎng)絡中結點功能平等，但能力有差異（異構性），如連接帶寬n在無組織的Gnutella網(wǎng)絡組織方

22、式下，70%的結點承受較高時延(280ms)n用戶連接時間與Napster類似，超過50%的用戶連接時間6hn25%的用戶不共享任何文件，75%的用戶共享文件數(shù)低于100，僅7%共享文件超過1000，即文獻中的Free-Riding(搭便車)現(xiàn)象，對網(wǎng)絡的高效工作不利nGnutella網(wǎng)絡相當于社會網(wǎng)絡，可用冪律(Power-law)分布網(wǎng)絡近似，擁有連接數(shù)L的結點占網(wǎng)絡總結點的份額正比于L-a,a是取決于網(wǎng)絡本身的常數(shù)因子，Gnutella網(wǎng)絡a=2.3，容錯性較高n采用Gnutella協(xié)議的P2P網(wǎng)絡應解決：q結點異構性：充分利用結點能力qFree-Riding：鼓勵上傳，限制或剝奪Fre

23、e-Rider的權利q保持高容錯性：高效的機制檢測和恢復網(wǎng)絡分割q繼續(xù)優(yōu)化查詢機制，TTL的取值q拓撲一致性nGnutella協(xié)議0.6版q層次化的無結構P2P網(wǎng)絡路由和定位方法nRouting、location含義接近，此處路由指消息走過的路徑上的每一跳選擇，定位看成是由多次路由組成的n無結構網(wǎng)絡沒有全局路由表，不可能預先知道要找的數(shù)據(jù)在哪里，只能隨機路由，通常以洪泛法為基礎，通過TTL限制搜索半徑n四種典型的P2P隨機路由方法：洪泛法、擴展環(huán)、隨機走、超結點路由n洪泛法q絕大多數(shù)現(xiàn)存無結構P2P網(wǎng)絡實際采用q路由覆蓋范圍是一個以TTL為半徑的圓q不保證找到實際存在的文件n擴展環(huán)（expan

24、ding ring）q試探性的洪泛法q逐步增加TTL，直至查詢成功或者達到上限，從而形成一個個環(huán)q效率稍高n隨機走（random walks）q結點收到查詢消息時只隨機選擇一個鄰居結點發(fā)送該消息，直到數(shù)據(jù)被找到或TTL用完q因網(wǎng)絡開銷僅隨跳數(shù)增加線性增加，故TTL可以較大q改進方法：帶檢測的隨機走，行者IDq前途較為光明n超結點路由（supernode routing）q超結點自組織成一個網(wǎng)絡，普通結點向其發(fā)起查詢q可以在超結點網(wǎng)絡中采用洪泛法qeDonkey、KaZaA的流行，證明可行性第三代P2P網(wǎng)絡 結構化P2P體系Chord、CAN、Tapestry、PastryChord與CFS：簡

25、單、精確的環(huán)形P2P網(wǎng)絡nMIT與Berkeley的研究者01年正式發(fā)表/chord/nChord作為一個P2P網(wǎng)絡，是基于帶弦環(huán)拓撲結構的分布式系統(tǒng)，提供對象的存儲、查詢、復制、緩存，在其上可以架構更高層的分布式數(shù)據(jù)存儲系統(tǒng)如協(xié)同文件系統(tǒng)CFSnChord作為一個分布式散列表，只支持結構化P2P最簡單的功能：將結點和數(shù)據(jù)對象映射到覆蓋網(wǎng)中，但具有幾乎最優(yōu)的路由效率、確定性的對象查詢、負載均衡、高可靠性以及良好的容錯性與自適應，最主要的是：簡單、優(yōu)美nChord的技術特點q基于安全的一致性散列函數(shù)來分配結點ID和對象IDq在一個有N個結點的網(wǎng)絡中

26、，每個Chord結點保存O(logN)個其他結點的信息q查詢數(shù)據(jù)對象需要的覆蓋網(wǎng)路由跳數(shù)也為O(logN)q當結點加入或者離開網(wǎng)絡時，為了維持網(wǎng)絡結構、保持自適應性所需要的消息數(shù)在O(log2N)Chord基礎工作原理nChord使用安全散列函數(shù)（如SHA-1）為每個網(wǎng)絡結點和數(shù)據(jù)對象分配唯一的IDqnodeID=H(node屬性)，屬性可以是結點IP、port、公鑰、隨機數(shù)或它們的組合qobjectID=H(object屬性)，屬性可以是數(shù)據(jù)對象的名稱、內(nèi)容、大小、發(fā)布者或者它們的組合qH是散列函數(shù)，SHA系列散列函數(shù)的Hash值長度160，保證ID的唯一性nChord按照如下方法將數(shù)據(jù)對象

27、（只是其索引）分配到網(wǎng)絡結點中q所有的結點按照nodeID從小到大順時針排列在一個環(huán)上q數(shù)據(jù)對象k（ObjectID）被分配到環(huán)上順時針方向緊隨k（包括與k相等）的第一個結點，該結點稱為對象k的后繼，記做successor(k)nChord結點n的后繼是環(huán)上緊隨n（不等于不等于n）的第一個結點，記做n.successor一個簡單的Chord環(huán)（m=3）n當Chord中有新結點n加入時，為保持正確、一致的對象放置，原本由n的后繼結點負責的對象，其中一部分必須分配給nn當Chord中有舊結點n離開時，原本由n負責的所有對象，必須分配給n的后繼。除此以外，對象不需要再做移動，這正是一致性散列函數(shù)所追

28、求的性質(zhì)n例：圖中新加入結點7n單純的環(huán)可以工作，但效率太低n為此，結點維護一個有m（ID位數(shù)）項的路由表，也稱“指向表”（finger table），其中第i項指向結點s，s=successor(n+2i-1)，1im，即s是在順時針方向到n的距離至少為2i-1的第一個結點，記做n.fingeri.nodenChord路由表的特點：q每個結點只保存很少的其它結點信息，并且對離它越遠的結點所知越少qChord結點不能從自己的路由表中看出對象k的后繼n為確定對象k的后繼（k所在的結點）,結點n在自己的路由表中查找在k之前且離k最近的結點j，讓j去找離k最近的結點，遞歸查找，最終可以找到對象k的前

29、驅(qū)（在k之前離k最近的結點，記做predecessor(k)，類似，結點n的前驅(qū)記做n.predecessor）n前驅(qū)中必然有后繼的路由表項，定位成功nChord結點n的路由表各項屬性及其定義屬性定義fingerk.start(n+2k-1)mod2m, 1ervalfingerk.start, fingerk+1.start).noden.fingerk.start的第一個結點successor后繼結點，即finger1.nodepredecessor前驅(qū)結點Chord路由表的簡單示例假設結點3要找到對象1的后繼n在結點3的路由表中，1屬于3.erval即7

30、,3)n結點3讓3.finger3.node即結點0去找1n結點0在路由表中發(fā)現(xiàn)自己的后繼1恰好是對象1的后繼，因此將1返回給結點3n結點3由此知道對象1放在結點1中Chord結點加入算法nChord的自適應需要保持兩個不變的屬性q每個結點的后繼始終正確q對每個對象k，結點successor(k)始終負責k的索引n為此，新結點n的加入需要完成三個任務q初始化n的前驅(qū)和路由表項q更新網(wǎng)絡其他結點的前驅(qū)和路由表項q告訴其后繼將應該由n負責的數(shù)據(jù)對象索引傳遞給nChord容錯性和復制、緩存nChord中正確的后繼關系是一切工作的基礎n無論機制如何完善，網(wǎng)絡的動態(tài)性和不確定性都可以導致單后繼失效n因此

31、，實際的Chord給每個結點維護一個后繼列表，其中保存了該結點在Chord環(huán)上的r個后繼，典型地取r=O(logN)，即使結點失效概率為1/2，仍能正確定位n將結點保存的數(shù)據(jù)對象復制到所有后繼中，可提高數(shù)據(jù)的可用性、持久性n在Chord定位過程中，如每個中間結點緩存數(shù)據(jù)對象，可以提高獲取數(shù)據(jù)的速度Chord實驗分析n負載均衡q負載均衡是使用一致性散列函數(shù)的結構化P2P網(wǎng)絡的共同屬性q對于Chord而言，由于數(shù)據(jù)對象被分配到其后繼中，而數(shù)據(jù)對象、結點的ID都是隨機、均勻產(chǎn)生的，因此每個結點所負擔的數(shù)據(jù)對象也應該大致均衡q此外，Chord還采用了“虛擬服務器”的方法，在一臺計算機上運行多個Chor

32、d結點，可以使得結點各盡所能n定位路徑長度q理論量級為O(logN)跳q實驗中網(wǎng)絡結點數(shù)取N=2k，數(shù)據(jù)對象數(shù)取1002k，k從3取到14q測量結果：路徑長度平均約logN/2，是logN的一半，原因是Chord路由表的指數(shù)構造，使其每次查找都能將目的ID與當前結點ID之間的差距減小至少一半，可推導出平均路徑長度正好是logN的一半Chord總結nChord采用帶弦環(huán)拓撲結構，通過一致性散列函數(shù)將結點、數(shù)據(jù)對象映射到覆蓋網(wǎng)上，數(shù)據(jù)對象（索引）由其后繼結點負責，簡單、精確正是Chord最大的特點n每個Chord結點維護一個很小的路由表，后繼關系是Chord定位的基礎，路由表可以將定位路徑長度縮短

33、為O(logN)跳nChord需要保持兩個不變的屬性才能正確工作：后繼正確、后繼對對象的索引正確nChord采用周期性的穩(wěn)定算法和路由表更新算法檢查和修正后繼關系及路由表項n為保持高容錯性，Chord采用后繼列表避免單后繼失效，此時可以對數(shù)據(jù)對象進行復制和緩存，提高網(wǎng)絡效率結構化P2P網(wǎng)絡的特點與分析一、覆蓋網(wǎng)拓撲結構n帶弦環(huán)：q所有結點被組織在一個環(huán)上，環(huán)上只提供兩種功能取得當前結點的前驅(qū)和后繼(單向環(huán)如Chord只提供后繼)，只要后繼關系正確，就能保證正確定位。為加速定位，加入“弦”，即維護一個路由表，指向環(huán)上離自己很遠的結點。采用環(huán)形結構的P2P網(wǎng)絡有Chord、Pastry、Kadem

34、lia、Cycloidn多維空間q所有結點被組織在一個多維笛卡爾空間里（嚴格說是“多維環(huán)面(Torus)”結構），每個結點有自己在空間中的鄰居，典型P2P網(wǎng)絡是CAN，n超立方體（或Plaxton Mesh）q所有結點被組織在一個超立方體中，典型的有Tapestry、Pastry，覆蓋網(wǎng)每層維護匹配nodeID不同長度前綴（或后綴）的結點；Cycloid的基礎CCC則是基于超立方體改造n蝴蝶形q蝴蝶網(wǎng)中，每個結點有“層”，每層的結點通常維護兩個下邊、一個上邊以及兩個同層邊，典型的有Viceroy，基于蝴蝶網(wǎng)，不過每個結點還保存一個前驅(qū)和一個后繼從而組織成一個全局的環(huán)結構nde Bruijn圖q每個節(jié)點有兩條出邊：一條指向結點2m(mod2b)，一條指向結點2m+1(mod2b)，b為ID位數(shù)。Koorde將de Bruijn圖嵌入到Chord環(huán)中，提高了路由效率nCCC（cube-connected-cycles）q一個d維帶環(huán)立方體CCC是每個結點被一個包含d個結點的圓環(huán)所取代的d維超立方體，因此，每個結點度為3。Cycloid是基于CCC結構的常數(shù)度P2P模型n其它形狀（如跳表）q基于跳表SkipList的典型網(wǎng)絡是SkipNet分布式散列表n所有的結構化P2P網(wǎng)絡都使用分布式散列表（DHT）來