通信专业互联网技术内容寻址网络

　　　在线辅导　面授招生　考试大纲　指定教材　试题汇总

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的应用中也是很重要的优点。

返回目录： 通信工程师互联网技术新型网络体系结构汇总

编辑推荐：

中级通信专业实务 互联网技术教程汇总

中级通信专业实务传输与接入教程汇总

通信专业实务考试设备与环境教程汇总

通信专业实务考试交换技术教程汇总