基于TCAM的K步长多模式匹配算法及硬件实现

对K步长状态机进行改进,消除了各状态的失效链,节省了存储资源,提高了匹配效率;根据TCAM(Ternary Content Addressable Memory)的并行查找和精确查找的特性,设计了一种用FPGA实现TCAM的方法,并以此作为基本匹配单元;最后结合改进的K步长状态机和基本匹配单元设计了一个快速多模式匹配系统.接收网络数据流进行实验,结果证明设计的匹配系统能达到数千兆位的吞吐率.

改进的K步长多模式匹配算法

K步长状态机存在失效函数,一部分存储空间被用来存储失效状态。为了提高K步长状态机的空间性能,该文通过K步长状态机的转移函数和失效函数f构建了新的转移函数,消除了K步长状态机的"失效链"。对改进算法进行性能分析表明,模式串数量和长度越大,改进后算法的空间优化效果越明显。