交换技术基于CAM的路由查找算法

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

1.基于CAM的路由查找算法
1）CAM及TCAM路由查找原理
目前路由查找使用最多的硬件实现方法是使用内容寻址存储器（ContentAddressableMemory,CAM)来进行快速路由查找，CAM能够在一个硬件时钟周期内完成关键字的精确匹配查找。常用的随机存储器（RAM)通过输人地址来返回该地址处所对应的表项信息，但是CAM的访问方式不同，因为一个CAM表项包含两部分：査找域（Seareh-Field)和返回域（Retum-Field)。查找域是和查找内容相匹配的部分（一般含有已知的目的地址）；返回域含有相关信息或一个索引。这样，CAM就会将输人分组关键字与CAM中的所有表项同时进行匹配比较，最后返回匹配表项返回域所包含的信息。
CAM的主要操作有3种：在空闲位置写人新表项；査找四配表项；读取匹配表项包含的相关信息。
如果相关信息童很小，可以直接存储在CAM表项返回域中。这种直接访问速度快，复杂度低，但是因为成本因素，CAM表项不能太大，所以相关信息量必须尽量小。当相关信息量很大时，CAM表项不能直接存储，而是存储一个索引号，可以直接访问该索引号，用来读取索引号所指示的RAM表项中的信息。这种间接访问比直接访问速度慢，复杂度髙，但是对相关信息量没有限制。
传统CAM只能执行精确匹配，一般不适用于IP路由表。如果要使用CAM来进行最长前缀匹配路由查找，可以让每一类可能的地址前缀长度使用一个CAM,每个CAM保存对应长度的所有前缀的集合。对于IPv4来说，则一共需要使用32个CAM。这种方法有一个明显缺点，即在对地址前缀长度具体分布没有准确了解之前，为了保证能够存储"个前缀的表项，每个CAM都需要有W个表项的空间，因此，CAM存储空间的利用率较低。

为了克服上述方法的缺点，提出了另一种CAM实现机制TCAM(TernaryCAM)0TCAM-242-与传统CAM的区别是，后者表项的各个比特位只能是0或1，而前者的则有三个状态：0，1或X。X是一种无关态，可以是“0”或“1”，它由局部掩码来实现，而且可以表示可变长前缀。TCAM中前缀表示如图7-46所示，当局部掩码的某位为“0”时，则对应的前缀位为无关位，如前5位为“11111”或“11110”的关键字将匹配图7-46中的第0项（项0)。TCAM的另外一个非常有用的特点是不要求掩码中的“1”和“0”连续，如图7-46中的第n-m,其中前缀的第2位因为局部掩码为0而表示为无关位，则前3位为“110”和“100”的关键字都可以匹配第1项。可以利用此性质对路由表进行压缩，减少对TCAM的占用。

返回目录： 通信专业交换技术非连接型快速分组交换汇总

编辑推荐

通信专业实务考试终端与业务教程汇总

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

通信工程师考试培训交换理论基确汇总