通信專業(yè)互聯(lián)網(wǎng)技術(shù)內(nèi)容尋址網(wǎng)絡(luò)

　　　在線輔導(dǎo)　面授招生　考試大綱　指定教材　試題匯總

1.內(nèi)容尋址網(wǎng)絡(luò)（Content-AddressableNetwork，CAN)
CAN在2001年由加州大學(xué)伯克利分校提出。與Chord-樣，CAN也是DHT的一個(gè)變種。CAN類似于一張大哈希表,CAN的基本操作包括插人、查找和刪除（關(guān)鍵字、值）對(duì)。CAN由大量自治的節(jié)點(diǎn)組成。每個(gè)節(jié)點(diǎn)保存哈希表的一部分,稱為一個(gè)區(qū)（rone）。此外，每個(gè)節(jié)點(diǎn)還保存少量的鄰接區(qū)的信息。對(duì)每個(gè)特定關(guān)鍵字的插人（或查找、刪除）請(qǐng)求由中間的CAN節(jié)點(diǎn)進(jìn)行路由直到到達(dá)包含該關(guān)鍵字的CAN節(jié)點(diǎn)所在的區(qū)。CAN的設(shè)計(jì)完全是分布式的，它不需要任何形式的中央控制點(diǎn)。CAN具有很好的可擴(kuò)展性，節(jié)點(diǎn)只需要維護(hù)少量的控制狀態(tài)而且狀態(tài)數(shù)量獨(dú)立于系統(tǒng)中的節(jié)點(diǎn)數(shù)最。CAN支持容錯(cuò)特性，節(jié)點(diǎn)可以繞過(guò)錯(cuò)誤節(jié)點(diǎn)進(jìn)行路由。
①哈希算法
CAN的哈希算法與一致性哈希有所不同。Chord中，哈希得到的鍵值總是一維的，而在CAN中，哈希的結(jié)果由d維的笛卡爾空間來(lái)表示。d是一個(gè)由系統(tǒng)規(guī)模決定的常量。
②路由算法
CAN的路由査詢將在d維笛卡爾空間中進(jìn)行。這個(gè)坐標(biāo)空間被劃分為數(shù)個(gè)超長(zhǎng)方形，這些超長(zhǎng)方形稱為區(qū)域。每個(gè)節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)區(qū)域,而且用它所在區(qū)域的邊緣作為ID。--個(gè)鍵值映射到一個(gè)坐標(biāo)空間點(diǎn)，它存儲(chǔ)在該點(diǎn)所在區(qū)域的主機(jī)上。圖2-28(a)表示的一個(gè)二維[0，1]X[0，1]CAN有6個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)負(fù)責(zé)維護(hù)存儲(chǔ)有鄰居節(jié)點(diǎn)信息的路由表。鄰居節(jié)點(diǎn)具有d-1個(gè)坐標(biāo)值。

在CAN中，每個(gè)節(jié)點(diǎn)自身的ID經(jīng)由哈希后得到的維向量。經(jīng)過(guò)這樣的映射后，整個(gè)P2P系統(tǒng)將被映射到一個(gè)d維笛卡爾空間中，每個(gè)節(jié)點(diǎn)的位置由其自身ID決定。CAN對(duì)鄰居節(jié)點(diǎn)的定義并不要求成2i的關(guān)系排列，而是改為用在笛卡爾空間上相鄰來(lái)表示：在維笛卡爾空間中，2個(gè)節(jié)點(diǎn)的d維坐標(biāo)中有d-1維是相等的，剩余的一維是相鄰的節(jié)點(diǎn)，稱之為相鄰節(jié)點(diǎn)。
CAN中的節(jié)點(diǎn)僅存儲(chǔ)相鄰節(jié)點(diǎn)表。由于在d維的空間中最多有2d個(gè)相鄰的節(jié)點(diǎn)，因此節(jié)點(diǎn)的相鄰節(jié)點(diǎn)表最多有2d個(gè)表項(xiàng)。
在查詢的過(guò)程中，査詢節(jié)點(diǎn)首先計(jì)算被查詢內(nèi)容的鍵值（d維向量）,然后在節(jié)點(diǎn)列表中查找在笛卡爾空間中與該鍵值最為接近的相鄰節(jié)點(diǎn)，找到后向該節(jié)點(diǎn)發(fā)送査詢請(qǐng)求(這一策略被稱為貪婪策略）。査詢請(qǐng)求中將攜帶被查詢內(nèi)容的鍵值。收到査詢請(qǐng)求的節(jié)點(diǎn)如果發(fā)現(xiàn)自身存儲(chǔ)了被查詢的信息，可以直接回應(yīng)查詢節(jié)點(diǎn)（這與一致性哈希完全相同）；如果被查詢的信息不在本地，就根據(jù)相鄰節(jié)點(diǎn)表將請(qǐng)求轉(zhuǎn)發(fā)到與鍵值最接近的節(jié)點(diǎn)上。這樣的過(guò)程一直持續(xù)到找到相應(yīng)的節(jié)點(diǎn)為止。在查詢過(guò)程中，被查詢節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的笛卡爾空間距離單調(diào)地減少。查詢操作沿幾乎是直線的路徑從消息查詢發(fā)起節(jié)點(diǎn)到鍵值存儲(chǔ)節(jié)點(diǎn)來(lái)推進(jìn)一個(gè)數(shù)據(jù)定位消息。接收到數(shù)據(jù)定位消息，節(jié)點(diǎn)把消息推進(jìn)給它的最近鄰居節(jié)點(diǎn)，直至找到存儲(chǔ)該鍵值的節(jié)點(diǎn)。圖2-28（b）顯示了查詢鍵值（0.8,0.9）的路徑。每個(gè)節(jié)點(diǎn)維護(hù)O（d）個(gè)狀態(tài)，并且這個(gè)査詢成本為OW*N1-d）。如果d=0（logN），CAN的查詢次數(shù)及存儲(chǔ)空間需要是最優(yōu)的。
如果查詢節(jié)點(diǎn)或轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)現(xiàn)鄰居節(jié)點(diǎn)表中無(wú)法找到可用的下一跳節(jié)點(diǎn)，則采用非結(jié)構(gòu)化P2P常用的擴(kuò)展環(huán)搜索（ExpandingRingSearch,使用無(wú)狀態(tài)，受控的泛洪算法在覆蓋網(wǎng)中搜索）以找到合適的（符合貪婪策略）下一節(jié)點(diǎn)。
經(jīng)過(guò)CAN的優(yōu)化后，査詢需要的跳數(shù)由O（N）減少到均值為(d/4)(n1/d）的隨機(jī)制，考慮到d為常數(shù)，這一值可以表示為O（n1/d）或0（d*n1/d）
　?、蹆?yōu)缺點(diǎn)分析
CAN和Chord的主要區(qū)別在于路由算法不同。相比之下,在節(jié)點(diǎn)數(shù)量非常大時(shí),CAN的平均查詢跳數(shù)要比Chord增加得更快。而且CAN查詢過(guò)程中需要的運(yùn)算量也要髙于Chord。但CAN使用的d為預(yù)先設(shè)置的常量，因此，并不假設(shè)系統(tǒng)節(jié)點(diǎn)數(shù)量。在節(jié)點(diǎn)總數(shù)動(dòng)態(tài)變化范圍很大的系統(tǒng)中，CAN的相鄰節(jié)點(diǎn)表結(jié)構(gòu)保持穩(wěn)定，這在P2P的應(yīng)用中也是很重要的優(yōu)點(diǎn)。

返回目錄： 通信工程師互聯(lián)網(wǎng)技術(shù)新型網(wǎng)絡(luò)體系結(jié)構(gòu)匯總

編輯推薦：

中級(jí)通信專業(yè)實(shí)務(wù) 互聯(lián)網(wǎng)技術(shù)教程匯總

中級(jí)通信專業(yè)實(shí)務(wù)傳輸與接入教程匯總

通信專業(yè)實(shí)務(wù)考試設(shè)備與環(huán)境教程匯總

通信專業(yè)實(shí)務(wù)考試交換技術(shù)教程匯總