-
-
手机阅读
TCAM路由更新的硬件优化 |
| 摘 要：现代核心路由器对查找速率、表项更新速度、查找表容量等提出越来越高的要求。目前工业厂商大多采用基于TCAM（三态内容关联存储器）的解决方案。TCAM最大特点是查找速度快，但其更新算法会浪费很大的存储空间。针对这个问题该文提出一种利用FPGA提供硬件支持的路由更新方法，增加新表项时，只需对新增表项进行一次预处理，转发表无需按前缀长度排序，消除了预留空闲表项造成的存储空间浪费。 关键词：路由器;三态内容关联存储器;前缀 ;转发表 1 前言  图1 PLO-OPT算法图示 快速路由查找一直是一个热门研究项目。近年来人们提出很多基于软件[1]或硬件[2-5]的实现方法，随着路由器接口速度的不断提高，使用软件方法实现高速路由查找已经越来越困难了。目前工业界使用最多的硬件路由查找方法是使用TCAM。TCAM的优点是它所保留的表项在长度要求上非常灵活，可以在同一个TCAM芯片中保存任意长度的关键字表项[6]，因此TCAM非常适用于最长前缀路由的查找。但由于TCAM仅简单地将地址最低的匹配表项的存储地址作为结果（索引）输出，要保障最长前缀匹配，表项的存储必须按前缀长度相对地址降序排列，即低地址存储前缀较长的表项，高地址存储前缀较短的表项。这种存储顺序关系使得TCAM的更新操作变得复杂。当加入一条新的前缀表项时，为了能仍然保持表项间的顺序关系，就需要移动一些前缀表项。现有的针对IPV4的PLO-OPT算法（prefix length ordering constraint algorithm）[5]是目前处理TCAM表项更新的最优算法。该算法从低地址到高地址，依次存放由长到短的不同长度前缀的表项，并将空闲的TCAM表项集中于前缀表项所存储地址区的中间位置，构成一个空闲池，如图1。当有新表项加入时则加入位置以上或以下的各表项依次向中间的空闲池移动一个地址，以创建一个空闲空间。假设TCAM中存储了N条路由信息，则空闲空间的大小必须保持在N/2个表项，这在具有几十万个表项的骨干路由器上显然代价过高。 2 更新表项预处理 为了提高TCAM存储空间利用率，我们希望表项更新时无关项能避免移动，以消除构造空闲池的必要。如果低地址的表项能确保不包含高地址表项即低地址表项的前缀不是高地 址表项前缀的前缀，则搜索TCAM得到的结果就一定是具有最长前缀匹配的表项。为了使低地址表项不包含高地址表项，本文提出如下算法： 1，构建一个存放前缀长度的RAM，深度与TCAM一致，宽度为5位（适合IPV4），当表项插入时将其前缀长度保存在RAM中，存放位置与其在TCAM的位置一致，以方便查询。 2，以更新表项中的地址部分（更新表项以〈地址、掩码〉序偶形式出现）为关键字对TCAM进行读操作。 3，若有匹配项存在，则根据TCAM输出结果读取存放在RAM中的前缀长度，设为a。若无匹配项则可将更新表项写入TCAM中最后一个表项的下一个地址。 4，在存在匹配项的情况下，设更新表项前缀长度为b（b>=a恒成立）则将匹配表项扩展为2b-a个子项。例：若TCAM中有表项01011＊（5位前缀）插入表项为0101110＊（7位前缀）则01011＊为匹配表项，并扩展为0101100＊、0101101＊、0101110＊、0101111＊4个子项。 5，将生成子项作为关键字对TCAM进行查找操作，若某个子项找到匹配项，则该子项即覆盖匹配项的存储位置，若无匹配项则存入TCAM中最后一个表项。子项插入列表的过程中可能出现多个子项匹配同一个表项的情况，但只需一个子项覆盖匹配项即可，且不需要再次进行匹配项扩展，因为以子项为关键字进行查询后的匹配结果一定出现在第一个匹配项的低地址位置，再次进行扩展后生成的子项必定被包含在上一次扩展的结果中。 经过上述预处理，即可确保更新表项不会被低地址中任何一个表项所包含。通过这种方式组成的TCAM路由表在更新时不需要为更新项腾出表项空间，从而可避免构造空闲池造成的空间损失。  图 2前缀预处理电路结构示意图 3 前缀预处理电路原理 图2是预处理电路的结构示意图，更新表项在输入接口中被分离为地址部分和掩码部分。先将地址部分与取反后的掩码相与，然后作为关键字送入TCAM中。若无匹配，则直接将更新表项写入TCAM中，同时将掩码译码后得到的前缀长度b存入RAM中相同的位置。若有匹配，则根据匹配结果从RAM中读出相应表项的前缀长度a,将a编码成掩码并取反然后与更新表项中的地址部分相与，这个值即是所生成的第一个子项。再以此值为基数，做2b-a-1次加1运算即得到所有子项。最后将所有子项作为关键字，在TCAM中查找匹配项，若某个子项搜索到匹配项，则以该子项覆盖匹配项，若某子项未搜索到匹配项，则将此子项写入地址寄存器所指向的地址即TCAM中最后一个表项的下一个地址，然后将该地址加1后写回地址寄存器（Datain是TCAM查找关键字的输入端口，wrx是TCAM更新的写入端口，address是输入TCAM更新的地址端口，matchaddress、 matchfound是TCAM输出端口,TCAM的其他端口未一一列出）。  图 3控制状态机状态转移示意图 其中控制状态机通过对数据路径的控制，决定整个电路运行状态,其状态转移如图3所示。初始为idle状态;当有更新表项到达时，状态由idle进入lookup1，在这个状态下将更新表项的地址部分释放到TCAM的datain端口进行匹配查找;如果matchfound=0,表明无匹配项则进入renew1状态，释放更新项到TCAM的wrx端口、释放地址寄存器中的地址（初始化时写入的TCAM中最后一个路由表项的地址）到TCAM的address端口;然后进入writeram1状态，将ram置为写状态，释放地址寄存器中的地址到ram的addr端口，将前缀长度写入ram中;若matchfound=1，表明存在匹配项，则进入readram状态，这个状态下将ram置为读状态，释放matchaddress到ram的addr端口读出匹配项前缀长度a;然后进入judge状态，判断2b-a-n是否为0，且将n加1;若2b-a-n不为0，则进入lookup2状态，否则进入idle状态;lookup2状态释放生成的子项到TCAM的data端口进行匹配查询;若matchfound=1,则进入renew2状态否则进入renew3状态;renew2状态下控制状态机释放生成的子项到TCAM的wrx端口，释放matchaddress到TCAM的address端口（生成的子项将覆盖匹配项）;renew2状态后进入writeram2状态，置ram为写状态，释放matchaddress到ram的address端口（ram中这个地址的前缀长度将被改写）;writeram2状态后进入judge状态，继续判断;若进入remew3状态，状态机释放子项到TCAM的wrx端口，释放地址寄存器中的地址到TCAM的address端口;接着进入writeram3状态，置ram为写状态，释放地址寄存器中地址到ram的addr端口，并将地址寄存器中的数加1;随后进入judge状态，继续判断。 4 用FPGA实现前缀预处理电路  图4 四个子表项扩展的仿真波形 随着当前互联网的快速发展，路由器的端口速率从OC3（155.52Mbps）、OC12（622.08Mbps）、OC48（2.448Gbps）到OC192（10Gbps），甚至OC768（40Gbps）。路由器内部对路由更新的处理速度也必须越来越快。本文中提出的前缀预处理电路做为路由器中的辅助设备同样需要满足一定的数据处理速度。FPGA由于具有速率高、面积小、性能可靠、费用低廉且可移植性强等特点，成为高速数字电路设计的首选方案，本文即采用FPGA实现前缀预处理电路的设计。 设计中所用的硬件描述语言是Verilog HDL，在ModelSimXE5.7下进行编译仿真，综合工具是Synplicity公司专用于FPGA/CPLD的逻辑综合工具Synplify pro7.1。选用的器件是Xilinx公司的Virtex2系列，型号XC2V500，速度-6，封装FG256。电路的描述语言编译完成后，通过顶层文件建立一个测试平台，平台中包括预处理电路模块、信号源模块以及TCAM模块，其中预处理电路模块是可综合的，信号源模块和TCAM模块是行为级虚拟模块不可综合为门级网表。仿真时，信号源模块向预处理电路输入需要更新的路由表项（地址/掩码序偶），经预处理电路处理后生成新的更新项（原前缀或者原前缀扩展子项）并输出到TCAM模块中。TCAM模块中路由前缀存放于存储器中，仿真前存储器本身无路由信息，仿真时首先需要通过$readmemb系统命令从本地磁盘中读入一个路由表。如图4是表项扩展的仿真波形，由图可见输入的更新表项被扩展为4个子项，其中有2个子项也在TCAM中查询到匹配项。功能仿真和综合后仿真通过后，使用Xilinx公司的布局布线工具ISE5.2对前缀预处理电路进行布局布线。过程中采用的约束频率为80MHz。由ISE静态时序分析报告可知，所有路径都满足80MHz的约束。布局布线完成后，在ModelSim中将标准延时文件反标注到仿真模型上，通过施加各种情况的激励仿真可知，预处理电路完全符合设计要求。 结论 本文作者创新点：通过对更新的路由表项进行预处理，保证了更新表项不被低地址的表项所包含，无需将所有表项按前缀长度排列，从而可避免POL-OPT算法中保持一个深度为N/2的空闲池的做法，节约了宝贵的TCAM存储空间。整个电路方案合理可行，最高运行频率可达到80MHz。 |