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

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

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

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

編輯推薦：

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

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

通信專業實務考試設備與環境教程匯總

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