TCAM 在高速路由查找中的应用及其FPGA实现

　　摘要：当前随着网络带宽的不断增加，对路由器转发速度的要求也越来越高。如何进行路由的快速查找目前成为限制报文快速转发的瓶颈，为了解决这一问题比较流行的方式是采用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是路由前缀的长度）。

　　在图2的例子中，只需要移动A5、A4、A2三个表项就可以在P1与P2之间腾出空间并且仍 然保持TCAM前缀长度有序。为了进一步提高性能，可以为每一个前缀长度集合块预留一部分 空间，当然空间的分配要根据路由前缀的分布进行，因为一般情况下前缀长度大于24 的情况非常少[4]，所以比较简单通用的方法是假定前缀服从正态分布。

　　4 TCAM功能介绍及其FPGA实现

　　TCAM基本框图如图3所示。与RAM相似，TCAM是将表项存储在一个阵列中。每个表项的宽 度称为字宽，TCAM中表项的个数称为TCAM的深度。字宽和深度可以表征TCAM的容量。TCAM 的优点是它所保存的表项在长度上要求非常灵活，可以保存任意长度的表项。其中每个表项都是以<地址，掩码〉序偶的形式保存。在写TCAM模式时，Wren信号有效，此时通过地址线 Address和数据线Data配合掩码信号线Wrx，掩码信号能使Wrx_used将表项写入目的地址。假 设关键字长度范围是0-6，那么长度为3的关键字110*就可以以<110000,000111>序偶的形式 表示。在查找TCAM模时,Find_start信号表征新的查找开始，直接通过Data送入要查找的关 键字,TCAM判断关键字是否与表项相等，如果相等表示关键字与该表项匹配，信号Mfound为 高，Maddress输出表项地址。否则不匹配。同时表项可以由Wrdelete信号配合Wren和所要删 除的表项地址进行更新。

　　TCAM通过保存关键字掩码的方式使得它可以保存任意长度的关键字表项，因此使用TCAM 非常适合进行长前缀路由的查找，目前不少工业界的厂商都在进行对TCAM的设计研究。由 于可能存在多个表项匹配的情况，因此TCAM需要在这些匹配的表项中选取一个表项作为 的查找结果，TCAM规定在所有匹配的表项中选取地址的表项作为的结果。为了能够 进行长前缀路由的查找，我们就需要保证在TCAM的低地址存储前缀较长的关键字表项，而 在地址高的区域存储前缀较短的关键字表项。

　　在利用FPGA设计TCAM时，我们采用ALTERA 公司的 APEX20K1000E系列芯片。利用VHDL 硬件描述语言借助QUARTUS2开发平台进行设计。TCAM的实现可以利用QUARTUS2中提供的 altcam 宏模块。该模块对CAM的设计包括三个模式：single-match mode，multiple-match mode, fast multiple-match mode。由于TCAM器件允许相同的表项存在，所以选用 multiple-match mode 和 fast multiple-match mode 可以实现TCAM的功能，其中这两种模 式的区别在于查找的速度和所用资源不同。以容量为32x32的TCAM为例，采用multiple-match mode 设计需要1个ESB（embedded system block 嵌入式系统块）和98个LE（logic element 逻 辑单元）；而采用fast multiple -match mode 设计则需要2个ESB和79个LE。但是查找的速度 上后者近似两倍于前者。

　　图4是采用multiple-match mode设计TCAM的仿真图。其中写入表项要两到三个时钟周期 （要求掩码要三个时钟周期），查找需要两个时钟周期。该种模式下由于存在多个匹配的情 况，所以start信号后面的是个匹配的表项（地址），mnext后面的是接下来的一个 表项，此时mnext持续有效时间不能超过两个时钟周期。图中1被写入两个地址1，8；在start 后输出的是低的地址1，mnext后输出的是接下来的地址8。

　　图5是采用fast multiple-match mode 设计TCAM的仿真图，其中查找只需要一个时钟周 期。图中当查找数据000110时，由于存在地址为1，3的两个表项与之匹配，所以送出地址低 的一个表项。

　　从图5中可以看出，当采用fast multiple-match mode 时，时钟频率为50MHZ，所以每秒 钟可以完成50M次查找，完全满足端口速率为10G的oc-192路由接入，适应骨干路由器的高 速查找要求。目前虽然FPGA资源有限，路由器大容量路由表不能完全存储在一片FPGA 中，但可以将FPGA内部实现的TCAM作为cache来加速路由查找。随着技术的进步，FPGA 的容量将不断加大，到那时在一片FPGA上应该可以存储大量的路由表项。

　　5 总结

　　TCAM作为高速查找器件在数据压缩，宽带码分多址,路由表高速查找等多方面有着广泛 的应用，利用FPGA实现TCAM器件具有灵活，高效，简单等设计优势。本文利用FPGA设计的TCAM 可以作为高速路由查找中cache的实现方案，从而加速路由表的查找，提高路由的命中。 该方案已经应用在路由器千兆线卡的设计当中；同样这种设计方法也可以用于其他高速数据 的查找当中。