Leaf-TCAM:一种并行IP路由查找方法及性能分析

分析了互联网路由表和路由更新的特征,提出了一种基于叶子节点进行路由表分区的并行IP路由查找方法Leaf-TCAM,分区子表按照流量特征在K个TCAM芯片中进行均衡分布。分析表明,该路由查找方法在引入0.1*(K-1)冗余的前提下具有K-1倍加速因子。该方法无需进行前缀扩展,90%以上的路由前缀无需排序,可以采用随机更新;同时还具有分区均匀、分区溢出代价小等特点,而功耗只有传统单片方案的12%。

基于TCAM的并行路由查找方案综述

基于三态内容寻址存储器TCAM(Ternary Content-Addressable Memory)的路由查找方案是目前高性能路由器进行路由查找时普遍使用的方案,但这种方案仍存在查找速度、功耗和更新效率方面的挑战。因此,学者们提出了各种并行TCAM的解决方案以提高查找速度、降低功耗和增强更新效率。归类总结目前的并行TCAM路由查找方案,剖析它们的优缺点,指出目前这些方案仍存在的不足,并探索相应的解决方案。

基于并行字符索引的多步长正则表达式匹配算法

深度包检测（deep packet inspection,DPI）是网络入侵检测与防御系统（network intrusion detection and prevention system,NIDPS）的核心.基于三态内容可寻址存储器（ternary content addressable memory,TCAM）的正则表达式匹配算法提高了数据包的处理速度,成为DPI技术的一个重要研究方向.TCAM具有查找速度快、存储空间小等特性,且能耗与存储空间成正比.由于DFA的存储空间开销比较大,且存储空间大小随着DFA步长数的增加而指数倍增,基于TCAM的DFA面临高能耗的问题,特别是多步长DFA.提出一种基于并行字符索引的多步长正则表达式匹配算法（multi-stride parallel character-indexed DFA,PCIDFA）,对确定型有限自动机（deterministic finite automaton,DFA）构造并行字符索引,通过比特位图取交集,减少匹配时激活的TCAM块数,显著降低TCAM能耗.实验结果表明：与多步长DFA相比,多步长PCIDFA在TCAM能耗上减少了99.8%以上,在TCAM存储空间开销上减少了48.5%-65.3%,在吞吐量上提高了1.9-2.6倍.

建立高效的网络安全设备IP数据包转发机制

因为网络安全设备对数据包转发的特殊需求,需要比一般设备更高效稳定的数据包转发机制。通过对IP数据包转发机制研究,针对特殊需求,提出了一种基于(IFPLUT+TCAM)的IP数据包转发机制。该机制将查找表根据输出端口分割为若干个小查找表,并允许查找引擎对每个小查找表进行并行处理,有效地将寻找“最长前缀匹配”的复杂问题简化为“第1前缀匹配”问题。

一种高效的网络安全设备IP数据包转发机制

通过对IP数据包转发机制研究,针对网络安全设备对数据包转发的特殊需求,提出了一种基于(IFPLUT+TCAM)的IP数据包转发机制。该机制将查找表根据输出端口分割为若干个小查找表,并允许查找引擎对每个小查找表进行并行处理,有效地将寻找“最长前缀匹配”的复杂问题简化为“第一前缀匹配”问题。

基于SRAM的并行路由算法搜索芯片设计

针对三态内容可寻址存储器(TCAM)高成本、高功耗、路由表更新维护复杂以及搜索结果返回单一等问题,提出了一种使用静态随机存储器(SRAM)和自适应矩阵硬件算法逻辑的搜索芯片设计新技术。该技术使用SRAM快速存储路由表项等信息,使用硬件逻辑实现软件算法逻辑功能以提高芯片处理速度。搜索芯片基于UMC 40 nm低功耗1P8M CMOS工艺制造,核心电压为1.1 V,I/O电压为3.3 V,总体芯片面积为200 mm^2。测试结果表明,芯片路由查找时可以快速命中和返回12个并行搜索结果,单搜索性能为500 Msps(million search per second),并行搜索性能为6 Bsps(billion search per second),可用于骨干网络建设和通信领域。