通信專業(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的一個變種。CAN類似于一張大哈希表,CAN的基本操作包括插人、查找和刪除（關(guān)鍵字、值）對。CAN由大量自治的節(jié)點組成。每個節(jié)點保存哈希表的一部分,稱為一個區(qū)（rone）。此外，每個節(jié)點還保存少量的鄰接區(qū)的信息。對每個特定關(guān)鍵字的插人（或查找、刪除）請求由中間的CAN節(jié)點進行路由直到到達包含該關(guān)鍵字的CAN節(jié)點所在的區(qū)。CAN的設(shè)計完全是分布式的，它不需要任何形式的中央控制點。CAN具有很好的可擴展性，節(jié)點只需要維護少量的控制狀態(tài)而且狀態(tài)數(shù)量獨立于系統(tǒng)中的節(jié)點數(shù)最。CAN支持容錯特性，節(jié)點可以繞過錯誤節(jié)點進行路由。
①哈希算法
CAN的哈希算法與一致性哈希有所不同。Chord中，哈希得到的鍵值總是一維的，而在CAN中，哈希的結(jié)果由d維的笛卡爾空間來表示。d是一個由系統(tǒng)規(guī)模決定的常量。
②路由算法
CAN的路由査詢將在d維笛卡爾空間中進行。這個坐標(biāo)空間被劃分為數(shù)個超長方形，這些超長方形稱為區(qū)域。每個節(jié)點都對應(yīng)一個區(qū)域,而且用它所在區(qū)域的邊緣作為ID。--個鍵值映射到一個坐標(biāo)空間點，它存儲在該點所在區(qū)域的主機上。圖2-28(a)表示的一個二維[0，1]X[0，1]CAN有6個節(jié)點。每個節(jié)點負責(zé)維護存儲有鄰居節(jié)點信息的路由表。鄰居節(jié)點具有d-1個坐標(biāo)值。

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

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

編輯推薦：

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

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

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

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