通信專業(yè)互聯網技術內容尋址網絡

　　　在線輔導　面授招生　考試大綱　指定教材　試題匯總

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

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

返回目錄： 通信工程師互聯網技術新型網絡體系結構匯總

編輯推薦：

中級通信專業(yè)實務 互聯網技術教程匯總

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

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

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