專題3-P2P網(wǎng)絡(luò)體系結(jié)構(gòu)(2013簡)

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

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

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

4、同計算”四、具有高可擴展性(scalability)n可擴展性衡量，當(dāng)網(wǎng)絡(luò)結(jié)點總數(shù)增加時：q結(jié)點負(fù)載如何改變q為適應(yīng)規(guī)模擴大而需要增加的額外設(shè)備的數(shù)量q任意兩個網(wǎng)絡(luò)結(jié)點通信效率如何改變，尤其是路由效率nP2P網(wǎng)絡(luò)中，結(jié)點間分?jǐn)偼ㄐ砰_銷，無需增加設(shè)備，路由跳數(shù)增量小五、良好的容錯性n冗余方法n周期性檢測n結(jié)點自適應(yīng)狀態(tài)維護P2P網(wǎng)絡(luò)的各種應(yī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全球處理單元，計算任務(wù)由對等結(jié)點而非服務(wù)器分配，SETIHome，U.C. Berkeley搜索外星文明nP2P搜索引擎：第三代搜索引擎技術(shù)，離實用有差距n其它 第一代P2P網(wǎng)絡(luò)混合式P2P體系：Napster與BT內(nèi)容nNapsterP2P網(wǎng)絡(luò)的先驅(qū)nBitTorrent分片優(yōu)化的新一代混合式P2P網(wǎng)絡(luò)n第一代P2P網(wǎng)絡(luò)的特點 Napster：P2P網(wǎng)絡(luò)的先驅(qū)n世界上第一個應(yīng)用性P2P網(wǎng)絡(luò)，混合式P2P體系最杰出的代表n1999年波士頓東北大學(xué)的Shawn Fanning開發(fā)Napster，用于MP3文件交流，與傳

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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