【正文】 ，是 logN的一半，原因是 Chord路由表的指數(shù)構(gòu)造，使其每次查找都能將目的 ID與當(dāng)前結(jié)點(diǎn) ID之間的差距減小至少一半，可推導(dǎo)出平均路徑長(zhǎng)度正好是 logN的一半寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)為 212寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)七、 Chord總結(jié)n Chord采用帶弦環(huán)拓?fù)浣Y(jié)構(gòu)，通過(guò)一致性散列函數(shù)將結(jié)點(diǎn)、數(shù)據(jù)對(duì)象映射到覆蓋網(wǎng)上，數(shù)據(jù)對(duì)象（索引）由其后繼結(jié)點(diǎn)負(fù)責(zé)，簡(jiǎn)單、精確正是 Chord最大的特點(diǎn)n 每個(gè) Chord結(jié)點(diǎn)維護(hù)一個(gè)很小的路由表，后繼關(guān)系是Chord定位的基礎(chǔ)，路由表可以將定位路徑長(zhǎng)度縮短為 O(logN)跳n Chord需要保持兩個(gè)不變的屬性才能正確工作：后繼正確、后繼對(duì)對(duì)象的索引正確n Chord采用周期性的穩(wěn)定算法和路由表更新算法檢查和修正后繼關(guān)系及路由表項(xiàng)寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n 為保持高容錯(cuò)性， Chord采用后繼列表避免單后繼失效，此時(shí)可以對(duì)數(shù)據(jù)對(duì)象進(jìn)行復(fù)制和緩存，提高網(wǎng)絡(luò)效率寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)八、 CFS（ Cooperative file system）n CFS協(xié)同文件系統(tǒng)是以 Chord為基礎(chǔ)的 P2P協(xié)同只讀文件存儲(chǔ)系統(tǒng)，文件分塊存儲(chǔ)n CFS由三層構(gòu)件組成q Chord，底層定位散列表：維護(hù)路由表，定位數(shù)據(jù)塊所在的服務(wù)器q DHash，分布式數(shù)據(jù)塊散列表：中間層，分布和緩存數(shù)據(jù)塊以平衡負(fù)載，復(fù)制數(shù)據(jù)塊以容錯(cuò)，并通過(guò)服務(wù)器選擇來(lái)減少時(shí)延；使用 Chord定位數(shù)據(jù)塊q FS， File System，文件系統(tǒng)：高層，從 DHash層獲得數(shù)據(jù)塊并轉(zhuǎn)換為文件，給更高的應(yīng)用提供文件系統(tǒng)接口寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n CFS文件系統(tǒng)類似 UNIX文件目錄結(jié)構(gòu)，只是以根塊代替根目錄、以元數(shù)據(jù)塊代替子目錄、以數(shù)據(jù)塊代替文件，而以塊標(biāo)識(shí)代替文件地址n CFS對(duì) Chord的改進(jìn)：采用前驅(qū)列表定位以提高定位容錯(cuò)性，使用服務(wù)器選擇減少定位時(shí)延，對(duì)結(jié)點(diǎn) ID認(rèn)證以防止 ID偽造和 IP虛報(bào)n CFS對(duì)數(shù)據(jù)塊采用后繼復(fù)制以提高數(shù)據(jù)可用性，同時(shí)減少了客戶獲取數(shù)據(jù)的時(shí)延；采用路徑緩存提高系統(tǒng)工作效率，同時(shí)避免熱點(diǎn)數(shù)據(jù)的后繼結(jié)點(diǎn)負(fù)載過(guò)重；采用 “虛擬結(jié)點(diǎn) ”和 “限額 ”方法提供負(fù)載均衡寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò) CAN：簡(jiǎn)單、容錯(cuò)的多維空間 P2P網(wǎng)絡(luò)n Content Addressable Network，內(nèi)容可尋址網(wǎng)絡(luò)，采用多維 Torus環(huán)面拓?fù)浣Y(jié)構(gòu)，典型采用的二維空間網(wǎng)格，類似于笛卡爾平面，其結(jié)點(diǎn)編址方式也類似于點(diǎn)的編址n 01年 [Ratnasamy et al.]在 ACM SIGCOMM會(huì)議發(fā)表正式論文（與 Chord同年同會(huì)）寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n CAN的多維空間被動(dòng)態(tài)地分配給其網(wǎng)絡(luò)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)占有一個(gè)屬于自己的方塊并負(fù)責(zé)該方塊中所有的 “點(diǎn) ”（數(shù)據(jù)對(duì)象索引）寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n 每個(gè)結(jié)點(diǎn)維護(hù)一個(gè)路由表，記錄多維空間上的鄰居信息，如圖中結(jié)點(diǎn) D可以記錄 B、 C、 E的ID和地址n CAN采用逐步定位，每一步挑選當(dāng)前結(jié)點(diǎn)路由表中離目的結(jié)點(diǎn)最 “近 ”的鄰居作為下一跳n 對(duì)一個(gè) d維 CAN來(lái)說(shuō)，若維護(hù)一個(gè)有 2d項(xiàng)的路由表，其定位效率為 ，取 d=logN，即為 O(logN)，其定位效率與其它結(jié)構(gòu)化 P2P網(wǎng)絡(luò)一致寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n 以 2維 CAN為例，新結(jié)點(diǎn)加入時(shí)，被映射到一個(gè)點(diǎn)，其所在的方塊將一分為二，一半分給新結(jié)點(diǎn)負(fù)責(zé)，一半留給原來(lái)負(fù)責(zé)的結(jié)點(diǎn)；當(dāng)舊結(jié)點(diǎn)離開(kāi) CAN時(shí)，某個(gè)鄰居必須接管它原來(lái)負(fù)責(zé)的區(qū)域，相當(dāng)于方塊合并n CAN的容錯(cuò)性體現(xiàn)在路由選擇的靈活性上，由于其多維空間的拓?fù)浣Y(jié)構(gòu)， CAN不需要維護(hù)一些嚴(yán)格的不變屬性，每個(gè)鄰居對(duì)結(jié)點(diǎn)來(lái)說(shuō)都是同等地位的；在 CAN中任意兩個(gè)點(diǎn)間存在多條路徑，即使很多鄰居失效，仍能以較快的速度定位目的結(jié)點(diǎn)n 目前還沒(méi)有基于 CAN的應(yīng)用系統(tǒng)寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)一、 CAN網(wǎng)絡(luò)構(gòu)建n 結(jié)點(diǎn)加入步驟：自舉、尋找區(qū)域、加入路由表n JOIN STEP1：自舉（ bootstrap）q 新結(jié)點(diǎn)通過(guò) CAN的 DNS域名獲得一個(gè)眾所周知結(jié)點(diǎn)（自舉結(jié)點(diǎn)、入口結(jié)點(diǎn)），后者提供一個(gè)列表，其中包含一些 CAN現(xiàn)存結(jié)點(diǎn)的信息n JOIN STEP2：尋找區(qū)域q 新結(jié)點(diǎn) n隨機(jī)選擇 CAN空間中的一個(gè)點(diǎn) P并向 P發(fā)送一個(gè)加入請(qǐng)求消息，該消息可通過(guò)列表中任意一個(gè)現(xiàn)存結(jié)點(diǎn)發(fā)送到 CAN網(wǎng)絡(luò)中，并被逐步路由到 P所在的區(qū)域，最終到達(dá)負(fù)責(zé) P所在區(qū)域的結(jié)點(diǎn) n’， n’按某種規(guī)則將負(fù)責(zé)區(qū)域分一半給 n負(fù)責(zé)寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n JOIN STEP3：加入路由表q 獲得自己的區(qū)域后， n從 n’獲得其鄰居的 IP地址等信息，并通知每個(gè)鄰居更新其路由表以反映 n的存在q CAN也采用了自適應(yīng)的周期性方法，每個(gè)結(jié)點(diǎn)定期向鄰居發(fā)送自己所負(fù)責(zé)的區(qū)域和自己的路由表信息，當(dāng)發(fā)現(xiàn)不一致時(shí)更新q 由于結(jié)點(diǎn)插入、離開(kāi)或周期性更新時(shí)只需要通知鄰居結(jié)點(diǎn)，而每個(gè)結(jié)點(diǎn)的路由表記錄 O(d)個(gè)鄰居，因此其自適應(yīng)開(kāi)銷是 O(d)的，通常比 Chord和大多數(shù)P2P系統(tǒng)小得多寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)簡(jiǎn)單的 CAN結(jié)點(diǎn)加入示例寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n 當(dāng)結(jié)點(diǎn)離開(kāi) CAN時(shí)，通常應(yīng)顯式地將其區(qū)域及所負(fù)責(zé)數(shù)據(jù)交給一個(gè)鄰居，如果該鄰居可以合并一個(gè)規(guī)整的單區(qū)域，則完成合并，否則，離開(kāi)結(jié)點(diǎn)只能將其區(qū)域交給占有最小區(qū)域的鄰居，由其暫時(shí)負(fù)責(zé)兩塊區(qū)域，但并不合并n 當(dāng)結(jié)點(diǎn) n失效時(shí)，依靠周期性檢測(cè)由鄰居結(jié)點(diǎn)接管其區(qū)域，解決沖突的方法：每個(gè)鄰居做完接管工作以后，向 n的其它鄰居發(fā)送 TAKEOVER消息，其中包括消息源的區(qū)域信息，收到該消息的結(jié)點(diǎn)比較消息源的區(qū)域和自己的區(qū)域，如果前者大，則回發(fā) TAKEOVER消息表明自己接管更合適，否則取消接管工作寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n 問(wèn)題：隨著結(jié)點(diǎn)不斷加入、離開(kāi)， CAN網(wǎng)絡(luò)的區(qū)域劃分將變得支離破碎，而且由一個(gè)結(jié)點(diǎn)負(fù)責(zé)多個(gè)結(jié)點(diǎn)的情況將越來(lái)越多，直到負(fù)載超過(guò)結(jié)點(diǎn)能力上限n CAN采用 “背景區(qū)域重分配 ”（ background zone reassignment）方法合并支離破碎的區(qū)域，并盡量讓一個(gè)結(jié)點(diǎn)只負(fù)責(zé)一塊區(qū)域，詳見(jiàn)論文 [Ratnasamy et al.,2023]寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)二、 CAN增強(qiáng)機(jī)制：多維、多空間、多散列n 多維： d接近 logN，路由效率高，容錯(cuò)性強(qiáng)n 多空間：使用多個(gè)不同的 CAN空間，每個(gè)空間稱為一個(gè) “現(xiàn)實(shí) ”（ reality）；一個(gè)真實(shí)的網(wǎng)絡(luò)結(jié)點(diǎn)在每個(gè) CAN空間中都會(huì)被分配一塊區(qū)域，同一個(gè)數(shù)據(jù)對(duì)象的在每個(gè)空間中都會(huì)被分配給一個(gè)結(jié)點(diǎn)，從而起到復(fù)制作用，提高數(shù)據(jù)可用性；定位時(shí)，結(jié)點(diǎn)可以比較多個(gè)空間的鄰居，效率更高n 多散列：?jiǎn)慰臻g可以使用多散列，效果類似多空間寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)三、 CAN的 “區(qū)域超載 ”n 區(qū)域超載：將一個(gè)區(qū)域分給多個(gè)結(jié)點(diǎn)負(fù)責(zé)n 一個(gè)結(jié)點(diǎn)除了維護(hù)原來(lái)的路由表，還需要維護(hù)一個(gè) “區(qū)域超載列表 ”，保存和自己共同負(fù)責(zé)同一區(qū)域的結(jié)點(diǎn)信息n 新結(jié)點(diǎn) A加入時(shí)，如果它所映射到的點(diǎn)原先由結(jié)點(diǎn) B負(fù)責(zé)， B首先檢查該區(qū)域的結(jié)點(diǎn)數(shù)是否超過(guò)上限，如未超過(guò)則不分割區(qū)域，而是將該區(qū)域也給 A負(fù)責(zé)，同時(shí) A從 B那里獲得 “區(qū)域超載列表 ”；若超過(guò)上限，則進(jìn)行分割寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n 區(qū)域超載的好處q 減少定位跳數(shù)：讓多個(gè)結(jié)點(diǎn)負(fù)責(zé)同一區(qū)域等效于減少系統(tǒng)結(jié)點(diǎn)數(shù)q 減少每跳時(shí)延：在選擇下一跳時(shí)，由于鄰居區(qū)域由多個(gè)結(jié)點(diǎn)負(fù)責(zé)，可以從這多個(gè)結(jié)點(diǎn)中選出時(shí)延最短的作為下一跳q 提高容錯(cuò)性和可用性：一個(gè)區(qū)域只有在負(fù)責(zé)它的所有結(jié)點(diǎn)都失效時(shí)才不可達(dá)，且該區(qū)域的數(shù)據(jù)相當(dāng)于被復(fù)制到多個(gè)結(jié)點(diǎn)中寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n CAN中的復(fù)制與緩存q 三種隱式復(fù)制：多空間、多散列、區(qū)域超載q 對(duì)熱點(diǎn)數(shù)據(jù)， CAN采用顯式復(fù)制到鄰居區(qū)域q 在定位路徑上放置熱點(diǎn)數(shù)據(jù)的緩存副本寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)四、 CAN總結(jié)n CAN采用多維空間拓?fù)浣Y(jié)構(gòu)，簡(jiǎn)單、直觀， CAN空間被動(dòng)態(tài)分配給其