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

1、TCAM 在高速路由查找中的应用及其 FPG 故现2010-09-1418:46:34摘要：当前随着网络带宽的不断增加，对路由器转发速度的要求也越来越高。如何进行路由的速查找目前成为限制报文快速转发的瓶颈，为了解决这一问题比较流行的方式是采用 TCAMS 件这路由的快速查找。本文详细介绍了 TCAMS 件在高速路由查找中的应用及其管理算法，同时重点给了TCAMS 件的 FPGAS 现。1 引言路由器转发 IP 分组时，转发引擎需要在路由表中查找该 IP 报文中目的地址所对应的路由勺息，从而决定 IP 报文的转发方式。目前设计快速的路由查找方法已经成为提高路由器整体性能 I键之一1。随着网络速率

2、的提高，传统的基于软件的路由查找机制已经不能满足要求，目前工中使用最多的硬件路由查找方法是使用内容寻址存储器(CAMo 但由于路由查找具有最长前缀匹的特点2,人们又提出了另一种 CAMfi 现机制一 ternaryCAM(TCAM,TCAMS 件相对于 CAM 点是它所保存的表项在长度要求上非常灵活，可以在同一个 TCAM5 片中保存任意长度的关键字表项。但是它也有不足之处：第一、TCAME 为昂贵，而且容量相对较小；第二、TCAMK 用并行匹 g 较方式，功耗较大。第三、TCAMS 要保证前缀较长的关键字保存在前缀较短的关键字之前，这种序关系使得TCA岷键字更新更为复杂。 本文介绍了TCAM

3、fc路由快速查找中的应用及其管理算法同时利用FPGAg计实现了 TCAM,使得路由查找更为灵活，系统设计更加简单。2 利用 TCAMtt 行路由查找图 1 是使用 TCAM4 行路由查找的示意图。表项长度是按路由前缀的长度降序排列。假设为地址101.11.3.10 的 ip 报文查找转发路径。TCAM)时将它保存的所有表项与关键字 101.11.3.10 行匹配查找，表项 A1,A2 都与关键字匹配，但是 TCAMS 回地址最小的表项，即 A1。路由表是动态的，也就是说路由表项会随着网络拓扑结构的不断变化而相应的增加或者删阙一般来说，在路由更新的同时，路由查找是不能够进行的，在这段时间内报文需

4、要缓存在报文缓区内等待路由更新的完成，因此慢的路由更新对系统报文缓冲区的容量有很大的要求，同时也会长报文转发的时间。所以要尽可能的减小路由更新的时间。由于 TCAM8 要维持所有的路由表项按照前缀长度有序，所以对于路由的动态更新来说，效:会比较低。以图 1 为例，假设现在需要在转发表中增加新的表项 101.11.128/18,按照表项组织式，新的表项应该保存在表项 101.11.3/24(A1)和表项 101.11/16(A2)之间，但是目前在这 P 表项之间没有空闲的表项空间，所以需要通过移动其它表项为新表项腾出空间。下一小节我们给一种较好的表项管理算法，可以有效降低表项更新的开销。3Pre

5、fix-lengthorderingconstraintalgorithmTCAMS 求所有的路由按照前缀长度降序排列，令 Pj 代表的是前缀长度为 j 的所有路由集合果 jk,那么所有 Pj 中的路由表项都应该保存在 Pk 中的路由表项之前。TCAMR 要求前缀长度集块之间的顺序关系，对于每个前缀长度集合块内部各个路由前缀之间的顺序关系没有严格规定。用这一思想，文献3提出了 PLO_OP 算法，算法实现如图 2 所示。当需要在 TCAM 中加入长度为(20k32)的路由前缀时，首先从长度 21 的前缀块开始，将前缀块的第一项移动到最后一项（即 TCAM 勺空闲表项区域），这样在长度为 22

6、的前缀块处就有了一个空闲表项；然后将长度为前缀(PLO_OPT 表项管理算法块中的第一项移动到这一个空闲表项处， 使得长度为 23 前缀块中出现了空闲表项；以此类推直到新加入表项所在的前缀块为止，那时就只需要将该新表项加入到分配处的空闲表项处就可以（8k20 时情况类似）。显然，这种算法的复杂度为 W/2（其中 W 是路由前缀的长度）。在图 2 的例子中， 只需要移动 A5、 A4A2 三个表项就可以在 P1 与 P2 之间腾出空间并且仍持 TCAMt缀长度有序。为了进一步提高性能，可以为每一个前缀长度集合块预留一部分空间，空间的分配最好要根据路由前缀的分布进行，因为一般情况下前缀长度大于 2

7、4 的情况非常少4以比较简单通用的方法是假定前缀服从正态分布。4TCAMft 能介名及其 FPGAS 现TCAMS 本框图如图 3 所示。 与 RAMf 似， TCAM1 将表项存储在一个阵列中。 每个表项的宽为字宽，TCAW 表项的个数称为 TCAM 勺深度。字宽和 7 知麦可以表征 TCAM 勺容量。TCAM 的优点责所保存的表项在长度上要求非常灵活，可以保存任意长度的表项。其中每个表项都是以地址，推码序偶的形式保存。在写 TCAM 奠式时，Wren 信号有效，此时通过地址线 Address 和数据线 D 配合掩码信号线 Wrx,掩码信号能使 Wrx_used 将表项写入目的地址。假设关键

8、字长度范围是 0-（那么长度为3 的关键字 110*就可以以110000,000111序偶的形式表示。在查找 TCAMK时,Find_start 信号表征新的查找开始，直接通过 Data 送入要查找的关键字,TCAMR 断关键字是与表项相等，如果相等表示关键字与该表项匹配，信号 Mfound 为高，Maddress 输出表项地址。不匹配。同时表项可以由 Wrdelete 信号配合 Wren 和所要删除的表项地址进行更新。TCAMS 过保存关键字掩码的方式使得它可以保存任意长度的关键字表项，因此使用 TCAWP 合进行最长前缀路由的查找，目前不少工业界的厂商都在进行对 TCAM 勺设计研究。由于

9、可能存彳个表项匹配的情况，因此 TCAM8 要在这些匹配的表项中选取一个表项作为最后的查找结果，TC 定在所有匹配的表项中选取地址最低的表项作为最后的结果。为了能够进行最长前缀路由的查找我们就需要保证在TCAM 勺低地址存储前缀较长的关键字表项，而在地址高的区域存储前缀较短的键字表项。在禾 I 用 FPGAS 计 TCAM 寸， 我彳门采用 ALTERA 公司的 APEX20K1000 舔歹芯片。 禾用 VHDL硬述语言借助 QUARTUS2 发平台进行设计。TCAM 勺实现可以利用 QUARTUS2 提供的 altcam 宏模该模块对 CAM 勺设计包括三个模式：single-matchmo

10、de,multiple-matchmode,fastmultiplematchmode。由于 TCAMS 件允许相同的表项存在，所以选用 multiple-matchmode 和 fastmultiple-matchmode 可以实现 TCAM 勺功能，其中这两种模式的区别在于查找的速度和所用资源同。以容量为 32x32 的 TCAMfc 例，采用 multiple-matchmode 设计需要 1 个 ESB（embeddedsyblock 嵌入式系统块）和 98 个 LE（logicelement 逻辑单元）；而采用 fastmultiple-matchmode 设计则需要 2 个 ES街

11、口 79 个 LE。但是查找的速度上后者近似两倍于前者。图 4 是采用 multiple-matchmode 设计 TCAM 勺仿真图。其中写入表项要两到三个时钟周期求掩码要三个时钟周期），查找需要两个时钟周期。start 信号后面的是第一个匹配的表项（地址最低）mnext 持续有效时间不能超过两个时钟周期。 图中地址 1,mnext 后输出的是接下来的地址 8。该种模式下由于存在多个匹配的情况，所以,mnext 后面的是接下来的一个表项，此时1 被写入两个地址 1,8;在 start 后输出的是图 5 是采用 fastmultiple-matchmode 设计 TCAM 勺仿真图，其中查找只需要一个时钟周图中当查找数据 000110 时，由于存在地址为 1,3 的两个表项与之匹配，所以送出地址低的一 4项。从图 5 中可以看出，当采用 fastmultiple-matchmode 时，时钟频率为 50MHz 所以每秒以完成 50M次查找，完全满足端口速率为 10G 的 oc-192 路由接入，适应骨干路由器的高速查找工求。目前虽然 FPG%源有限，核心路由器大容量品&由表不能完全存储在一片 FPGA 中，但可以将FPGAJ 部实现的 TCAM为 cache 来加速路由查找。随着技术的进步，FPGA 的容量将不断加大，时在一片 FPGAh 应该可以存储大量的路由表