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

P2P網(wǎng)絡體系結(jié)構(gòu)

概述對等網(wǎng)絡(P2P網(wǎng)絡)是分布式系統(tǒng)和計算機網(wǎng)絡相結(jié)合的產(chǎn)物，在應用領(lǐng)域和學術(shù)界獲得了廣泛的重視和成功，被稱為“改變Internet的新一代網(wǎng)絡技術(shù)”。課程信息教材對等網(wǎng)絡：結(jié)構(gòu)、應用與設(shè)計陳貴海、李振華著，清華大學出版社，2007.9

P2P網(wǎng)絡的概念、發(fā)展、特點、應用P2P：PeertoPeer對等網(wǎng)絡peer指網(wǎng)絡結(jié)點在行為上是自由的——任意加入、退出，不受其它結(jié)點限制，匿名功能上是平等的——不管實際能力的差異連接上是互聯(lián)的——直接/間接，任兩結(jié)點可建立邏輯鏈接，對應物理網(wǎng)上的一條IP路徑充分利用網(wǎng)絡帶寬、結(jié)點資源，提高工作效率從T/H,C/S到P2P-計算模式的輪回實線表示物理連接，虛線表示邏輯連接P2P的思想1956年提出（為什么今天成為現(xiàn)實？）1999年Internet上第一個應用Napster，半年發(fā)展了5000萬用戶其后涌現(xiàn)Gnutella,KaZaA,BitTorrent,eDonkey/eMule,Skype此后學術(shù)界重視占據(jù)Internet一半以上的帶寬不同類型P2P網(wǎng)絡幾乎同時出現(xiàn)，無明確界定，大致分類混合式P2P網(wǎng)絡：C/S、P2P模式的混合無結(jié)構(gòu)P2P網(wǎng)絡：分布/松散的結(jié)構(gòu)結(jié)構(gòu)化P2P網(wǎng)絡：準確、嚴格的結(jié)構(gòu)設(shè)計和實現(xiàn)P2P網(wǎng)絡應解決的基本問題路由和定位、查詢和搜索、動態(tài)結(jié)點算法、容錯性P2P網(wǎng)絡的增強機制數(shù)據(jù)復制、緩存、分片；負載均衡；拓撲一致性；匿名、聲譽、信任、安全性P2P網(wǎng)絡的優(yōu)勢一、充分利用網(wǎng)絡帶寬P2P不通過服務器進行信息交換，無服務器瓶頸，無單點失效，充分利用網(wǎng)絡帶寬，如BT下載多個文件，可接近實際最大帶寬，HTTP及FTP很少有這樣的效果二、提高網(wǎng)絡工作效率結(jié)構(gòu)化P2P有嚴格拓撲結(jié)構(gòu)，基于DHT，將網(wǎng)絡結(jié)點、數(shù)據(jù)對象高效均勻地映射到覆蓋網(wǎng)中，路由效率高三、開發(fā)了每個網(wǎng)絡結(jié)點的潛力結(jié)點資源：計算能力及存儲容量個人計算機并非永久聯(lián)網(wǎng)，是臨時性的動態(tài)結(jié)點，稱為“網(wǎng)絡邊緣結(jié)點”P2P使內(nèi)容“位于中心”轉(zhuǎn)變?yōu)椤拔挥谶吘墶?，計算模式由“服務器集中計算”“分布式協(xié)同計算”四、具有高可擴展性(scalability)可擴展性衡量，當網(wǎng)絡結(jié)點總數(shù)增加時：結(jié)點負載如何改變?yōu)檫m應規(guī)模擴大而需要增加的額外設(shè)備的數(shù)量任意兩個網(wǎng)絡結(jié)點通信效率如何改變，尤其是路由效率P2P網(wǎng)絡中，結(jié)點間分攤通信開銷，無需增加設(shè)備，路由跳數(shù)增量小五、良好的容錯性冗余方法周期性檢測結(jié)點自適應狀態(tài)維護P2P網(wǎng)絡的各種應用文件共享：代替ftp，前述典型的P2P模型多媒體傳輸：Skype（語音），PPLive（視頻）實時通信：QQ、MSNMessenger、Skype，都支持C/S、P2P模式協(xié)同工作：Groove虛擬辦公室分布式數(shù)據(jù)存?。簭V域、海量，CFS、PAST、OceanStore、Granary分布式計算：GPU，Gnutella全球處理單元，計算任務由對等結(jié)點而非服務器分配，SETI@Home，U.C.Berkeley搜索外星文明P2P搜索引擎：第三代搜索引擎技術(shù)，離實用有差距其它第一代P2P網(wǎng)絡——混合式P2P體系：Napster與BT內(nèi)容Napster——P2P網(wǎng)絡的先驅(qū)BitTorrent——分片優(yōu)化的新一代混合式P2P網(wǎng)絡第一代P2P網(wǎng)絡的特點Napster：P2P網(wǎng)絡的先驅(qū)世界上第一個應用性P2P網(wǎng)絡，混合式P2P體系最杰出的代表1999年波士頓東北大學的ShawnFanning開發(fā)Napster，用于MP3文件交流，與傳統(tǒng)的提供音樂下載的網(wǎng)站不同，Napster服務器里無歌曲，僅有其它用戶硬盤上的文件的索引Napster使用的軟件技術(shù)都是當時已有的，只是改變了軟件的應用體系，打破了客戶/服務器模式的瓶頸Napster半年吸引了5000萬注冊用戶，最高時超過6100萬用戶一、Napster網(wǎng)絡的工作原理Napster網(wǎng)絡由兩個部分組成：Napster用戶(peer)Napster網(wǎng)站(N)是一個服務器機群提供統(tǒng)一的用戶訪問接口各自保存一部分用戶的共享文件索引信息peer與固定的server相連加入時，將自身信息（連接帶寬、存儲空間等）以及共享文件信息發(fā)送給server，server記錄信息內(nèi)容及用戶位置（文件索引）查詢時，peer將查詢消息發(fā)給server，server與其它server協(xié)作后回復表單（包括所有匹配的文件索引）下載時，peer直接從索引中選取peer并與之建立連接、下載文件Napster網(wǎng)站的功能維護所有用戶的共享文件索引監(jiān)控系統(tǒng)中每個用戶的狀態(tài)（用戶報告的連接帶寬、用戶連入時間、是否掉線）刪除掉線用戶的索引，保證文件索引的時效性響應用戶的查詢請求，查詢的返回消息中可包含帶寬等信息，便于用戶選擇連接Napster的性能分析檢測結(jié)果與結(jié)論Napster機群包括大約160臺服務器每個用戶只與一臺服務器建立連接新用戶加入網(wǎng)絡時，可以選擇是否報告連接帶寬，但大多不報告，或者故意誤報以減少其他用戶從自己下載(自私性)結(jié)點異構(gòu)性很強，表現(xiàn)在連接帶寬、時延、連接時長、共享文件性等方面，如25%64Kbps，50%CableDSL，20%3M以上；超過50%的連接時間<1h，>6h的不到10%用戶自私性：20%～40%用戶幾乎從不提供文件共享，僅1%結(jié)點為文件提供者因此，類似Napster的P2P網(wǎng)絡在設(shè)計、優(yōu)化時應考慮結(jié)點異構(gòu)性：讓不同能力的結(jié)點扮演不同的角色協(xié)同傳輸:增加并行傳輸連接數(shù)目,避免系統(tǒng)瓶頸.激勵機制:鼓勵上傳，限制或禁止自私結(jié)點使用網(wǎng)絡進一步的發(fā)展，BitTorrent：相同架構(gòu)，但文件分片，使用散列函數(shù)映射用戶有上傳義務網(wǎng)絡及用戶信息更新、BT種子維護由server中的Tracker完成，下載同一文件的用戶圍繞Tracker形成獨立子網(wǎng)，不同文件的Tracker在不同server上，將server分散化，成為P2P在國內(nèi)最成功的應用BitTorrent：分片優(yōu)化的新一代混合式P2P網(wǎng)絡BT體系原理BT分片機制BT阻塞算法BT性能分析BT體系總結(jié)P2P下載對硬盤的影響B(tài)T體系原理BT網(wǎng)絡的四個組成部分BT網(wǎng)站：提供BT種子文件(即.torrent文件)搜索的服務器，每個服務器包含部分種子文件的索引.torrent文件服務器：小型的種子數(shù)據(jù)庫Tracker(跟蹤服務器)：BT網(wǎng)絡和用戶信息的維護者，幫助用戶交互，下載同一個文件的用戶圍繞Tracker形成一個獨立的子網(wǎng)BT用戶：可同時下載多個文件BT用戶的下載步驟BT用戶通過某個BT網(wǎng)站搜索文件，該網(wǎng)站將搜索請求重定向到網(wǎng)站鏡像，后者檢索并返回給用戶該文件的.torrent文件列表用戶選擇列表中的.torrent文件，BT軟件啟動下載任務，并從Tracker獲得當前也在下載該文件的用戶信息BT軟件與一定數(shù)量的用戶建立連接，下載文件并同時提供上傳下載過程中每隔一段時間更新一次連接以保持整網(wǎng)的工作效率BT分片機制BT將文件分為固定大小的分片(典型大小256KB)，每個用戶必須通知其他下載者自己擁有的分片，分片的完整性由散列函數(shù)保證分片流水作業(yè)：構(gòu)架在TCP之上的應用層協(xié)議，同時發(fā)送多個請求，以避免在兩個分片發(fā)送之間的延遲，進一步，分片可以劃分為子分片(典型16KB)，BT一直保持幾個請求（通常是5個）被流水式地同時發(fā)送。流水作業(yè)選擇同時發(fā)送的請求數(shù)目的依據(jù)，是使大多數(shù)連接變得飽和以充分利用帶寬分片選擇策略嚴格的優(yōu)先級（一個分片的下載）一旦請求了某個分片的子分片，那么該分片的所有子分片具有更高優(yōu)先級，以盡可能快地獲得一個完整的分片最少者優(yōu)先（中間階段/平穩(wěn)期）盡量選擇所知用戶擁有數(shù)最少的分片作為下一個下載分片，以使網(wǎng)絡中最稀少的分片盡快擁有多個復制下載者從Tracker了解哪些分片較少分片選擇策略隨機的第一個片段（文件下載最初階段）當最少的分片只有一個用戶擁有時，為避免并發(fā)沖突，第一個分片先隨機選擇，完成下載后再切換到“最少者優(yōu)先”策略最后階段模式（文件下載最后階段）為加速最后階段下載，下載者向他所連接的所有用戶都發(fā)送某分片的子分片請求，一旦某個子分片到了，下載者就會向其他用戶發(fā)送cancel消息，以避免浪費帶寬BT阻塞算法BT并不是由Tracker服務器集中分配資源，每個用戶自己有責任盡可能地提高自己的下載速率下載者根據(jù)連接用戶提供的下載速率給予同等的上傳回報(tit-for-tat)；對合作者提供上傳服務，對不合作者進行臨時阻塞一個好的阻塞算法應該利用所有可用的資源，為所有下載者提供一致、可靠的下載速率，并適當懲罰只下載而不上傳的用戶BT的阻塞算法(chokingalgorithm)每隔20秒進行一次輪詢：前10秒計算出哪個用戶要被阻塞，然后將阻塞狀態(tài)保持10秒10秒內(nèi)足夠TCP調(diào)整傳輸速率最優(yōu)疏通(optimisticunchoking)為發(fā)現(xiàn)更好的空閑連接，不能只向為自己提供最高下載速率的用戶提供上傳，而是每隔30秒，重新計算一次哪個連接應該是“最優(yōu)疏通”反對冷落(anti-snubbing)某個下載者可能被所連接的所有用戶阻塞，為緩解該問題，當從某個用戶那里一個分片也沒有得到，下載者認為被對方“冷落”，不再為對方提供上傳?！胺磳渎洹背３е露鄠€并發(fā)的“最優(yōu)疏通”，從而更快恢復下載速率僅僅上傳用戶完成下載后，優(yōu)先選擇可從自己得到更高上傳速率的用戶或剛好被所有人阻塞的用戶BT性能分析

Pouwelseetal.,2004,2005論文流行性：應用廣泛，但BT網(wǎng)站、.torrent文件服務器及Tracker故障率較高，限制了網(wǎng)絡規(guī)?？捎眯裕和希Q于服務器的可用性。實際較低，只有一半的BT網(wǎng)站鏡像可正常工作超過2.1天，種子服務器更少下載性能：當時統(tǒng)計平均速度30KB/s文件生命周期該文件的種子生命期，由于服務器故障及用戶行為不確定性，差別很大約17%的用戶下載完成后做種時間超過1小時，僅3%用戶做種時間超過10小時污染等級加入到BT網(wǎng)絡中的共享文件的真實性審查系統(tǒng)(moderationsystem)，三種角色：需要審查的提交者；不需要審查的提交者；審查者。可逐級提升。BT體系總結(jié)BT是混合式結(jié)構(gòu)的P2P網(wǎng)絡，以BT網(wǎng)站、.torrent文件服務器和Tracker為核心，控制和幫助用戶共享文件下載同一文件的用戶圍繞Tracker形成一個獨立的子網(wǎng)BT限定用戶在下載的同時必須提供上傳，既提高了網(wǎng)絡效率，又杜絕了P2P網(wǎng)絡中的自私結(jié)點現(xiàn)象BT將文件分片，分片又被劃分成子分片，子分片流水作業(yè)，并在文件下載的不同階段有不同的分片選擇策略以優(yōu)化性能。這是BT最大的特點，也是它高效的最本質(zhì)原因BT基于經(jīng)濟學規(guī)律的阻塞算法，優(yōu)化了網(wǎng)絡資源配置，增強了用戶間的協(xié)作BT通過對文件和分片生成散列值，保證文件的完整性BT提供了一定的安全機制，如文件審查、輸入驗證碼BT服務器故障率高，導致可用性降低，且網(wǎng)絡規(guī)模受限，文件無持久性保證第一代P2P網(wǎng)絡的特點拓撲結(jié)構(gòu)混合式(C/S+P2P)星型拓撲結(jié)構(gòu)，以服務器為核心查詢與路由用戶向服務器發(fā)出查詢請求，服務器返回文件索引用戶根據(jù)索引與其它用戶進行數(shù)據(jù)傳輸路由跳數(shù)為O(1)，即常數(shù)跳容錯性：取決于服務器的故障概率（實際網(wǎng)絡中，由于成本原因，可用性較低）自適應：靠服務器監(jiān)控實現(xiàn)自組織與自適應，只要服務器正常工作即可有效維護網(wǎng)絡和結(jié)點信息匿名性：一般不提供，但支持增強機制：BT的文件分片、雙向傳輸、防范攻擊第二代P2P網(wǎng)絡——無結(jié)構(gòu)P2P體系Gnutella、KaZaA、eDonkey、FreenetGnutella：純分布式無結(jié)構(gòu)P2PGnutella的歷史Nullsoft公司，MP3播放軟件WinAmp的發(fā)明人JustinFrankel、TomPepper開發(fā)2000年3月14日在網(wǎng)站上公開Gnutella軟件一個半小時后，母公司AOL(AmericanOnline)擔心步Napster后塵，關(guān)閉了網(wǎng)站數(shù)千名MP3迷下載了軟件并公開與改造其純分布式無結(jié)構(gòu)P2P網(wǎng)絡思想廣泛流傳Gnutella已不單純對應具體軟件，而是當作一種典型的無結(jié)構(gòu)P2P網(wǎng)絡協(xié)議一、Gnutella體系的工作原理Gnutella協(xié)議0.4版(0.6版加入了超結(jié)點Ultrapeer，結(jié)構(gòu)有變化)協(xié)議開發(fā)者稱Peer為Servent(Server+Client)，網(wǎng)絡中只有peer，沒有serverGnutella覆蓋網(wǎng)上每個結(jié)點對應一臺實際的計算機每條連接對應一條點到點的鏈路覆蓋網(wǎng)上的連接由每個peer保存的“鄰居結(jié)點”信息確定，有一個鄰居結(jié)點即對應有一條邊新結(jié)點加入時，必須首先連接到“眾所周知”幾乎總是在線的Gnutella結(jié)點(稱為“自舉”結(jié)點、“入口結(jié)點”)Gnutella網(wǎng)中的消息可以被廣播或回播(back-propagate，沿廣播的反向路徑回傳消息)，協(xié)議設(shè)計的支持機制：每條消息具有一個隨機產(chǎn)生的全局唯一標識符GUID(16字節(jié))以互相區(qū)分每個結(jié)點緩存最近路由的消息以支持回播并阻止不必要的重廣播每條消息都有TTL以避免過度消耗網(wǎng)絡資源Gnutella的典型消息組成員消息：PING，PONG新結(jié)點加入時廣播PING消息，或用來探測其它結(jié)點是否仍然存在(心跳)結(jié)點收到PING消息后，可以決定是否回播PONG消息，以及是否將PING轉(zhuǎn)發(fā)給鄰居，PONG消息包含結(jié)點IP,port,共享文件數(shù)量大小查詢消息：QUERY，QUERYRESPONSEQUERY消息用來查詢文件,包含查詢內(nèi)容與最小響應速度等附加信息,但不包含源結(jié)點信息RESPONSE消息包含文件下載的必須信息及該結(jié)點的nodeID，沿QUERY消息路徑回播文件傳輸消息：GET，PUSH結(jié)點收到QUERYRESPONSE消息后用GET消息請求獲得文件對處于防火墻后因而不能直接響應文件請求的結(jié)點，使用PUSH消息請求防火墻后的文件擁有者主動建立到自己的連接Gnutella的文件檢索過程泛洪式搜索(floodingsearch)，系統(tǒng)開銷大有限深度TTL(TimetoLive)，不保證一定查詢到已有文件Gnutella網(wǎng)絡的維護各結(jié)點使用PING、PONG消息探測其他結(jié)點存在與否，在收到PING消息后，可以自主決定是否回播PONG，并根據(jù)TTL數(shù)值決定是否繼續(xù)廣播PING消息具有一定的自組織和自適應性Gnutella網(wǎng)絡的性能分析Ripeanu,2001,2002、Saroiuetal.,2002,2003、Adar&Huberman,2002Gnutella用戶的連接帶寬僅在Queryresponse消息中作為輔助信息回播，因此，Gnutella網(wǎng)絡中不共享文件的用戶或其共享的文件與查詢請求一直不匹配的用戶，不會主動發(fā)布帶寬Gnutella網(wǎng)絡中結(jié)點功能平等，但能力有差異（異構(gòu)性），如連接帶寬在無組織的Gnutella網(wǎng)絡組織方式下，70%的結(jié)點承受較高時延(>280ms)用戶連接時間與Napster類似，超過50%的用戶連接時間<1h，不到10%的>6h25%的用戶不共享任何文件，75%的用戶共享文件數(shù)低于100，僅7%共享文件超過1000，即文獻中的Free-Riding(搭便車)現(xiàn)象，對網(wǎng)絡的高效工作不利Gnutella網(wǎng)絡相當于社會網(wǎng)絡，可用冪律(Power-law)分布網(wǎng)絡近似，擁有連接數(shù)L的結(jié)點占網(wǎng)絡總結(jié)點的份額正比于L-a,a是取決于網(wǎng)絡本身的常數(shù)因子，Gnutella網(wǎng)絡a=2.3，容錯性較高采用Gnutella協(xié)議的P2P網(wǎng)絡應解決：結(jié)點異構(gòu)性：充分利用結(jié)點能力Free-Riding：鼓勵上傳，限制或剝奪Free-Rider的權(quán)利保持高容錯性：高效的機制檢測和恢復網(wǎng)絡分割繼續(xù)優(yōu)化查詢機制，TTL的取值拓撲一致性Gnutella協(xié)議0.6版層次化的無結(jié)構(gòu)P2P網(wǎng)絡路由和定位方法Routing、location含義接近，此處路由指消息走過的路徑上的每一跳選擇，定位看成是由多次路由組成的無結(jié)構(gòu)網(wǎng)絡沒有全局路由表，不可能預先知道要找的數(shù)據(jù)在哪里，只能隨機路由，通常以洪泛法為基礎(chǔ)，通過TTL限制搜索半徑四種典型的P2P隨機路由方法：洪泛法、擴展環(huán)、隨機走、超結(jié)點路由洪泛法絕大多數(shù)現(xiàn)存無結(jié)構(gòu)P2P網(wǎng)絡實際采用路由覆蓋范圍是一個以TTL為半徑的圓不保證找到實際存在的文件擴展環(huán)（expandingring）試探性的洪泛法逐步增加TTL，直至查詢成功或者達到上限，從而形成一個個環(huán)效率稍高隨機走（randomwalks）結(jié)點收到查詢消息時只隨機選擇一個鄰居結(jié)點發(fā)送該消息，直到數(shù)據(jù)被找到或TTL用完因網(wǎng)絡開銷僅隨跳數(shù)增加線性增加，故TTL可以較大改進方法：帶檢測的隨機走，行者ID前途較為光明超結(jié)點路由（supernoderouting）超結(jié)點自組織成一個網(wǎng)絡，普通結(jié)點向其發(fā)起查詢可以在超結(jié)點網(wǎng)絡中采用洪泛法eDonkey、KaZaA的流行，證明可行性第三代P2P網(wǎng)絡

——結(jié)構(gòu)化P2P體系Chord、CAN、Tapestry、PastryChord與CFS：簡單、精確的環(huán)形P2P網(wǎng)絡MIT與Berkeley的研究者01年正式發(fā)表http:///chord/Chord作為一個P2P網(wǎng)絡，是基于帶弦環(huán)拓撲結(jié)構(gòu)的分布式系統(tǒng)，提供對象的存儲、查詢、復制、緩存，在其上可以架構(gòu)更高層的分布式數(shù)據(jù)存儲系統(tǒng)如協(xié)同文件系統(tǒng)CFSChord作為一個分布式散列表，只支持結(jié)構(gòu)化P2P最簡單的功能：將結(jié)點和數(shù)據(jù)對象映射到覆蓋網(wǎng)中，但具有幾乎最優(yōu)的路由效率、確定性的對象查詢、負載均衡、高可靠性以及良好的容錯性與自適應，最主要的是：簡單、優(yōu)美Chord的技術(shù)特點基于安全的一致性散列函數(shù)來分配結(jié)點ID和對象ID在一個有N個結(jié)點的網(wǎng)絡中，每個Chord結(jié)點保存O(logN)個其他結(jié)點的信息查詢數(shù)據(jù)對象需要的覆蓋網(wǎng)路由跳數(shù)也為O(logN)當結(jié)點加入或者離開網(wǎng)絡時，為了維持網(wǎng)絡結(jié)構(gòu)、保持自適應性所需要的消息數(shù)在O(log2N)Chord基礎(chǔ)工作原理Chord使用安全散列函數(shù)（如SHA-1）為每個網(wǎng)絡結(jié)點和數(shù)據(jù)對象分配唯一的IDnodeID=H(node屬性)，屬性可以是結(jié)點IP、port、公鑰、隨機數(shù)或它們的組合objectID=H(object屬性)，屬性可以是數(shù)據(jù)對象的名稱、內(nèi)容、大小、發(fā)布者或者它們的組合H是散列函數(shù)，SHA系列散列函數(shù)的Hash值長度≥160，保證ID的唯一性Chord按照如下方法將數(shù)據(jù)對象（只是其索引）分配到網(wǎng)絡結(jié)點中所有的結(jié)點按照nodeID從小到大順時針排列在一個環(huán)上數(shù)據(jù)對象k（ObjectID）被分配到環(huán)上順時針方向緊隨k（包括與k相等）的第一個結(jié)點，該結(jié)點稱為對象k的后繼，記做successor(k)Chord結(jié)點n的后繼是環(huán)上緊隨n（不等于n）的第一個結(jié)點，記做n.successor一個簡單的Chord環(huán)（m=3）當Chord中有新結(jié)點n加入時，為保持正確、一致的對象放置，原本由n的后繼結(jié)點負責的對象，其中一部分必須分配給n當Chord中有舊結(jié)點n離開時，原本由n負責的所有對象，必須分配給n的后繼。除此以外，對象不需要再做移動，這正是一致性散列函數(shù)所追求的性質(zhì)例：圖中新加入結(jié)點7單純的環(huán)可以工作，但效率太低為此，結(jié)點維護一個有m（ID位數(shù)）項的路由表，也稱“指向表”（fingertable），其中第i項指向結(jié)點s，s=successor(n+2i-1)，1≤i≤m，即s是在順時針方向到n的距離至少為2i-1的第一個結(jié)點，記做n.finger[i].nodeChord路由表的特點：每個結(jié)點只保存很少的其它結(jié)點信息，并且對離它越遠的結(jié)點所知越少Chord結(jié)點不能從自己的路由表中看出對象k的后繼為確定對象k的后繼（k所在的結(jié)點）,結(jié)點n在自己的路由表中查找在k之前且離k最近的結(jié)點j，讓j去找離k最近的結(jié)點，遞歸查找，最終可以找到對象k的前驅(qū)（在k之前離k最近的結(jié)點，記做predecessor(k)，類似，結(jié)點n的前驅(qū)記做n.predecessor）前驅(qū)中必然有后繼的路由表項，定位成功Chord結(jié)點n的路由表各項屬性及其定義屬性定義finger[k].start(n+2k-1)mod2m,1≤k≤erval[finger[k].start,finger[k+1].start).node≥n.finger[k].start的第一個結(jié)點successor后繼結(jié)點，即finger[1].nodepredecessor前驅(qū)結(jié)點Chord路由表的簡單示例假設(shè)結(jié)點3要找到對象1的后繼在結(jié)點3的路由表中，1屬于3.finger[3].interval即[7,3)結(jié)點3讓3.finger[3].node即結(jié)點0去找1結(jié)點0在路由表中發(fā)現(xiàn)自己的后繼1恰好是對象1的后繼，因此將1返回給結(jié)點3結(jié)點3由此知道對象1放在結(jié)點1中Chord結(jié)點加入算法Chord的自適應需要保持兩個不變的屬性每個結(jié)點的后繼始終正確對每個對象k，結(jié)點successor(k)始終負責k的索引為此，新結(jié)點n的加入需要完成三個任務初始化n的前驅(qū)和路由表項更新網(wǎng)絡其他結(jié)點的前驅(qū)和路由表項告訴其后繼將應該由n負責的數(shù)據(jù)對象索引傳遞給nChord容錯性和復制、緩存Chord中正確的后繼關(guān)系是一切工作的基礎(chǔ)無論機制如何完善，網(wǎng)絡的動態(tài)性和不確定性都可以導致單后繼失效因此，實際的Chord給每個結(jié)點維護一個后繼列表，其中保存了該結(jié)點在Chord環(huán)上的r個后繼，典型地取r=O(logN)，即使結(jié)點失效概率為1/2，仍能正確定位將結(jié)點保存的數(shù)據(jù)對象復制到所有后繼中，可提高數(shù)據(jù)的可用性、持久性在Chord定位過程中，如每個中間結(jié)點緩存數(shù)據(jù)對象，可以提高獲取數(shù)據(jù)的速度Chord實驗分析負載均衡負載均衡是使用一致性散列函數(shù)的結(jié)構(gòu)化P2P網(wǎng)絡的共同屬性對于Chord而言，由于數(shù)據(jù)對象被分配到其后繼中，而數(shù)據(jù)對象、結(jié)點的ID都是隨機、均勻產(chǎn)生的，因此每個結(jié)點所負擔的數(shù)據(jù)對象也應該大致均衡此外，Chord還采用了“虛擬服務器”的方法，在一臺計算機上運行多個Chord結(jié)點，可以使得結(jié)點各盡所能定位路徑長度理論量級為O(logN)跳實驗中網(wǎng)絡結(jié)點數(shù)取N=2k，數(shù)據(jù)對象數(shù)取100×2k，k從3取到14測量結(jié)果：路徑長度平均約logN/2，是logN的一半，原因是Chord路由表的指數(shù)構(gòu)造，使其每次查找都能將目的ID與當前結(jié)點ID之間的差距減小至少一半，可推導出平均路徑長度正好是logN的一半Chord總結(jié)Chord采用帶弦環(huán)拓撲結(jié)構(gòu)，通過一致性散列函數(shù)將結(jié)點、數(shù)據(jù)對象映射到覆蓋網(wǎng)上，數(shù)據(jù)對象（索引）由其后繼結(jié)點負責，簡單、精確正是Chord最大的特點每個Chord結(jié)點維護一個很小的路由表，后繼關(guān)系是Chord定位的基礎(chǔ)，路由表可以將定位路徑長度縮短為O(logN)跳Chord需要保持兩個不變的屬性才能正確工作：后繼正確、后繼對對象的索引正確Chord采用周期性的穩(wěn)定算法和路由表更新算法檢查和修正后繼關(guān)系及路由表項為保持高容錯性，Chord采用后繼列表避免單后繼失效，此時可以對數(shù)據(jù)對象進行復制和緩存，提高網(wǎng)絡效率結(jié)構(gòu)化P2P網(wǎng)絡的特點與分析一、覆蓋網(wǎng)拓撲結(jié)構(gòu)帶弦環(huán)：所有結(jié)點被組織在一個環(huán)上，環(huán)上只提供兩種功能——取得當前結(jié)點的前驅(qū)和后繼(單向環(huán)如Chord只提供后繼)，只要后繼關(guān)系正確，就能保證正確定位。為加速定位，加入“弦”，即維護一個路由表，指向環(huán)上離自己很遠的結(jié)點。采用環(huán)形結(jié)構(gòu)的P2P網(wǎng)絡有Chord、Pastry、Kademlia、Cycloid多維空間所有結(jié)點被組織在一個多維笛卡爾空間里（嚴格說是“多維環(huán)面(Torus)”結(jié)構(gòu)），每個結(jié)點有自己在空間中的鄰居，典型P2P網(wǎng)絡是CAN，超立方體（或PlaxtonMesh）所有結(jié)點被組織在一個超立方體中，典型的有Tapestry、Pastry，覆蓋網(wǎng)每層維護匹配nodeID不同長度前綴（或后綴）的結(jié)點；Cycloid的基礎(chǔ)CCC則是基于超立方體改造蝴蝶形蝴蝶網(wǎng)中，每個結(jié)點有“層”，每層的結(jié)點通常維護兩個下邊、一個上邊以及兩個同層邊，典型的有Viceroy，基于蝴蝶網(wǎng)，不過每個結(jié)點還保存一個前驅(qū)和一個后繼從而組織成一個全局的環(huán)結(jié)構(gòu)deBruijn圖每個節(jié)點有兩條出邊：一條指向結(jié)點2m(mod2b)，一條指向結(jié)點2m+1(mod2b)，b為ID位數(shù)。Koorde將deBruijn圖嵌入到Chord環(huán)中，提高了路由效率CCC（cube-connected-cycles）一個d維帶環(huán)立方體CCC是每個結(jié)點被一個包含d個結(jié)點的圓環(huán)所取代的d維超立方體，因此，每個結(jié)點度為3。Cycloid是基于CCC結(jié)構(gòu)的常數(shù)度P2P模型其它形狀（如跳表）基于跳表SkipList的典型網(wǎng)絡是SkipNet分布式散列表所有的結(jié)構(gòu)化P2P網(wǎng)絡都使用分布式散列表（DHT）來將結(jié)點、數(shù)據(jù)對象映射到覆蓋網(wǎng)中為使這種映射唯一、均勻、隨機，分布式散列表都使用安全的一致性散列函數(shù)，其中最著名、也被大多數(shù)P2P系統(tǒng)采用的安全散列函數(shù)是SHA-1（安全散列算法），它能產(chǎn)生均勻、隨