【文章內(nèi)容簡(jiǎ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)分配給其網(wǎng)絡(luò)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)負(fù)責(zé)一塊，每個(gè)數(shù)據(jù)對(duì)象被映射到一個(gè)點(diǎn)，由負(fù)責(zé)該點(diǎn)所在區(qū)域的結(jié)點(diǎn)保持索引n 每個(gè) CAN結(jié)點(diǎn)維護(hù)一個(gè)路由表，記錄它在多維空間上的鄰居信息， d維 CAN的定位效率為n CAN的高容錯(cuò)性體現(xiàn)在其路由選擇的靈活性上：即任意兩個(gè)結(jié)點(diǎn)間存在多條路徑，部分鄰居信息的失效對(duì)定位效率影響很小n 新結(jié)點(diǎn)加入 CAN分三步：自舉、尋找區(qū)域、加入路由表，從其加入?yún)^(qū)域中劃分一半進(jìn)行接管，采用 “背景區(qū)域重分配 ”方法調(diào)整區(qū)域?qū)拵襟w服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n CAN采用多種增強(qiáng)機(jī)制提高系統(tǒng)性能，包括多維度、多空間、多散列、區(qū)域超載技術(shù)n 綜上所述， CAN簡(jiǎn)單、容錯(cuò)性好，可擴(kuò)展，高效率寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò) Tapestry與 OceanStore：廣域的超立方體結(jié)構(gòu) P2P網(wǎng)絡(luò)n 嚴(yán)格講，是基于 Plaxton Mesh[1997]的網(wǎng)格形結(jié)構(gòu)， Pastry也基于此n 特點(diǎn)：構(gòu)建覆蓋網(wǎng)時(shí)考慮了拓?fù)湟恢滦詥?wèn)題n 00年 3月 UC Berkeley的 Ben Y. Zhao等成立Tapestry研究組， 03年 6月發(fā)布 n 應(yīng)用廣泛，著名的 OceanStore廣域存儲(chǔ)系統(tǒng)寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)Tapestry的應(yīng)用Bayeux 提供高效、容錯(cuò)的應(yīng)用層多播Brocade 提供界標(biāo)路由（ Landmark Routing）Cashmere 提供匿名路由FaultTolerant Overlay Routing基于 Tapestry開(kāi)發(fā)路由的冗余性，從而提供容錯(cuò)的覆蓋網(wǎng)路由OceanStore 提供全球范圍內(nèi)廣域的、持久性數(shù)據(jù)存取服務(wù)SpamWatch 基于 Tapestry，使用基于內(nèi)容相似度的搜索引擎，提供分布式的 SpamFilteringWarp 通過(guò)類型重定向提供快速移動(dòng)服務(wù)架構(gòu)寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)一、 Tapestry路由和定位n 每個(gè)結(jié)點(diǎn)有 nodeID，數(shù)據(jù)對(duì)象有 objectID，也稱為 GUID（ globally unique ID），每條消息有其特定應(yīng)用的 AID（ application ID），類似于 TCP協(xié)議中的端口號(hào)n Tapestry為每個(gè)數(shù)據(jù)對(duì)象分配一個(gè)負(fù)責(zé)結(jié)點(diǎn)，稱為該對(duì)象的根（ root）， root(objectID)=最接近 objectID的 nodeIDn Tapestry中也采用了多散列以提高對(duì)象可用性與持久性寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n Tapestry采用逐位匹配的后綴路由，每一跳匹配更多的后綴，如 xxx8xx98x5984598n 為適應(yīng)這種路由，每個(gè) Tapestry結(jié)點(diǎn)維護(hù)一個(gè)層次化的路由表（鄰居表），每一層代表與自身 nodeID匹配一定位數(shù)后綴的結(jié)點(diǎn)n 路由的第 n跳所到達(dá)的結(jié)點(diǎn)通常與目的結(jié)點(diǎn) ID至少匹配 n位后綴，為找到下一跳結(jié)點(diǎn)，需要在當(dāng)前結(jié)點(diǎn)的路由表的第 n+1層中，查找與目的結(jié)點(diǎn) ID匹配更多位后綴的結(jié)點(diǎn)，若找不到，則意味著定位即將完成寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)結(jié)點(diǎn) 0642的狀態(tài)信息，包括其對(duì)象索引、熱點(diǎn)數(shù)據(jù)管理器、對(duì)象存儲(chǔ)空間、路由表寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)Tapestry路由示例，結(jié)點(diǎn) 0325要發(fā)送一條消息給結(jié)點(diǎn) 4598，粗線標(biāo)明了路由的每一跳寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n Tapestry的路由表項(xiàng)有 logBN層，每層 B項(xiàng)n Tapestry的路由機(jī)制可以保證在 N個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)中，任何一次定位一般都能在 logBN跳之內(nèi)完成，其中 B為 ID編碼的進(jìn)制（ base，也稱 “基 ”）寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n Tapestry結(jié)點(diǎn) S向網(wǎng)絡(luò)插入數(shù)據(jù)對(duì)象 O時(shí)，要將其索引放到 O的根結(jié)點(diǎn)上，為此， S向鄰居發(fā)送一條以 objectID為目的地的消息，其中包含有對(duì)象索引信息如 objectID(O)，serverID(s)，該消息逐步匹配對(duì)象 ID直到?jīng)]有更多匹配位，此時(shí)即找到根結(jié)點(diǎn)，消息路徑上的所有結(jié)點(diǎn)都保存 O的索引信息寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n Tapestry結(jié)點(diǎn)查詢數(shù)據(jù)對(duì)象 O時(shí)，也發(fā)送一條以 objectID為目的地的定位消息，按后綴匹配方法逐步路由，若中間結(jié)點(diǎn)保存了索引，則定位結(jié)束，否則必將到達(dá) O的根結(jié)點(diǎn)（根結(jié)點(diǎn)可確保對(duì)象定位成功，也稱為對(duì)象的 “代理 ”結(jié)點(diǎn)）n 由于一個(gè) Tapestry結(jié)點(diǎn)可能保存 O的多個(gè)副本的索引，查詢時(shí)可從中找出自己認(rèn)為最近、最合適的來(lái)獲取數(shù)據(jù)，即 Tapestry可以自動(dòng)幫助用戶獲取最鄰近副本寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)二、 Tapestry動(dòng)態(tài)結(jié)點(diǎn)算法n 利用反向指針和心跳消息保持路由表的更新和定位的容錯(cuò)性q 反向指針： back pointer，指向那些把自己作為路由表項(xiàng)的結(jié)點(diǎn)（反向結(jié)點(diǎn)）q 周期性發(fā)送 Heartbeat消息至反向結(jié)點(diǎn)，確認(rèn)存在n 結(jié)點(diǎn)發(fā)現(xiàn)路由表某項(xiàng)失敗后并不立即替換它，而是過(guò)一段時(shí)間再檢測(cè)一次它是否在線，如果還不在才替換，稱為 “二次機(jī)會(huì) ”，防止 “閃斷 ”n 路由表中每項(xiàng)保存一個(gè) “主項(xiàng) ”和兩個(gè) “次要項(xiàng) ”，以提高可用性寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n 新結(jié)點(diǎn)加入：初始化自己的路由表、更新相關(guān)結(jié)點(diǎn)的路由表、從相關(guān)結(jié)點(diǎn)移交對(duì)象索引n JOIN STEP1：初始化路由表q 新結(jié)點(diǎn) N聯(lián)系到一個(gè)現(xiàn)存結(jié)點(diǎn) G，通過(guò) G發(fā)送以 N為目的地的消息q 假設(shè)第 i步路由到達(dá)結(jié)點(diǎn) Hi，根據(jù)后綴匹配路由算法， N和 Hi應(yīng)該共享長(zhǎng)度 i的后綴，則 N從 Hi那里獲得路由表的第 i+1層項(xiàng)是合適的q N對(duì)復(fù)制來(lái)的項(xiàng)進(jìn)行優(yōu)化，將更好的次要項(xiàng)結(jié)點(diǎn)改為主項(xiàng)，再查找新主項(xiàng)結(jié)點(diǎn)的路由表，比較 N到每項(xiàng)的距離，迭代優(yōu)化至收斂寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)n JOIN STEP2：更新其它結(jié)點(diǎn)路由表q N通過(guò) G發(fā)送往 N自己的消息，在 logN跳之內(nèi)到達(dá) N的根結(jié)點(diǎn) Rq R首先計(jì)算它和 N匹配的后綴位數(shù) p，然后通過(guò)自己路由表中的 “反向指針 ”，告訴那些與 R也匹配 p位后綴