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

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

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

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

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

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