通信与网络中的通信与网络中的TCAM 在高速路由查找中的应用及其在高速路由查找中的应用及其FPGA实实
现现
摘要：当前随着网络带宽的不断增加，对路由器转发速度的要求也越来越高。如何进行路由的快速查找目前成
为限制报文快速转发的瓶颈，为了解决这一问题比较流行的方式是采用TCAM器件进行路由的快速查找。本文详
细介绍了TCAM器件在高速路由查找中的应用及其管理算法，同时重点给出了TCAM器件的FPGA实现。 1
引言 路由器转发IP分组时，转发引擎需要在路由表中查找该IP报文中目的地址所对应的路由 信息，从而决
定IP报文的转发方式。目前设计快速的路由查找方法已经成为提高路由器整体 性能的关键之一[1]。随着网络速
率的提高，传统的基于软件的路由查找机制已经不能满足 要求，目前工业界中使用最多的硬件
摘要：当前随着网络带宽的不断增加，对路由器转发速度的要求也越来越高。如何进行路由的快速查找目前成为限制报文
快速转发的瓶颈，为了解决这一问题比较流行的方式是采用TCAM器件进行路由的快速查找。本文详细介绍了TCAM器件在高
速路由查找中的应用及其管理算法，同时重点给出了TCAM器件的FPGA实现。
1 引言
路由器转发IP分组时，转发引擎需要在路由表中查找该IP报文中目的地址所对应的路由 信息，从而决定IP报文的转发方
式。目前设计快速的路由查找方法已经成为提高路由器整体 性能的关键之一[1]。随着网络速率的提高，传统的基于软件的路
由查找机制已经不能满足 要求，目前工业界中使用最多的硬件路由查找方法是使用内容寻址存储器（CAM）。但由于 路由查
找具有最长前缀匹配的特点[2]，人们又提出了另一种CAM实现机制—ternary CAM （TCAM），TCAM器件相对于CAM的优
点是它所保存的表项在长度要求上非常灵活，可以在同 一个TCAM芯片中保存任意长度的关键字表项。但是它也有不足之
处：第一、TCAM更为昂贵， 而且容量相对较小；第二、TCAM使用并行匹配比较方式，功耗较大。第三、TCAM需要保证前
缀较长的关键字保存在前缀较短的关键字之前，这种顺序关系使得TCAM关键字更新更为复 杂。本文介绍了TCAM在路由快速
查找中的应用及其管理算法，同时利用FPGA设计实现了TCAM, 使得路由查找更为灵活，系统设计更加简单。
2 利用TCAM进行路由查找
图1是使用TCAM进行路由查找的示意图。表项长度是按路由前缀的长度降序排列。假设 为目的地址101.11.3.10的ip报文
查找转发路径。TCAM同时将它保存的所有表项与关键字101.11.3.10进行匹配查找，表项A1，A2都与关键字匹配，但是
TCAM返回地址最小的表项， 即A1。
路由表是动态的，也就是说路由表项会随着网络拓扑结构的不断变化而相应的增加或者 删除。一般来说，在路由更新的
同时，路由查找是不能够进行的，在这段时间内报文需要缓 存在报文缓冲区内等待路由更新的完成，因此慢的路由更新对系
统报文缓冲区的容量有很大 的要求，同时也会延长报文转发的时间。所以要尽可能的减小路由更新的时间。
由于TCAM需要维持所有的路由表项按照前缀长度有序，所以对于路由的动态更新来说， 效率就会比较低。以图1为例，
假设现在需要在转发表中增加新的表项101.11.128/18，按照 表项组织的方式，新的表项应该保存在表项101.11.3/24（A1）
和表项101.11/16（A2）之间， 但是目前在这两个表项之间没有空闲的表项空间，所以需要通过移动其它表项为新表项腾出
空间。下一小节我们给出一种较好的表项管理算法，可以有效降低表项更新的开销。
3 Prefix-length ordering constraint algorithm（PLO_OPT） 表项管理算法
TCAM要求所有的路由按照前缀长度降序排列，令Pj代表的是前缀长度为j的所有路由集 合，如果j>k，那么所有Pj中的路
由表项都应该保存在Pk中的路由表项之前。TCAM只要求前缀 长度集合块之间的顺序关系，对于每个前缀长度集合块内部各
个路由前缀之间的顺序关系没 有严格规定。利用这一思想，文献[3]提出了PLO_OPT算法，算法实现如图2所示。当需要在
TCAM中加入长度为k（20≤k≤32）的路由前缀时，首先从长度21的前缀块开始，将前缀块的 第一项移动到最后一项（即
TCAM的空闲表项区域），这样在长度为22的前缀块处就有了一个 空闲表项；然后将长度为22前缀块中的第一项移动到这一
个空闲表项处，使得长度为23前缀 块中出现了空闲表项；以此类推，直到新加入表项所在的前缀块为止，那时就只需要将该
新 表项加入到分配处的空闲表项处就可以了（8 ≤ k ≤ 20时情况类似）。显然，这种算法的复杂 度为W/2（其中W是路由前缀
的长度）。
