基于交叉链表的多关键字匹配硬件实现算法

摘要：

本文在“基于交叉链表的快速匹配算法”的基础上，针对其存在的操作串行性、访存地址离散性和空间复杂度大等不适合硬件实现的特征，提出了一系列算法改进——减小基本处理单位和增加双引擎间的协同判定逻辑，并给出相应的理论证明和实际测试结果。与原算法直接移植到硬件平台实现相比，新算法将匹配速度提高了一个数量级，空间复杂度降低了一个数量级，并且保留了原算法结构简单，硬件代价小，性能不受关键字集影响等优点.新算法适用于千兆网络环境下实现低成本、大关键字集的多关键字匹配引擎。

关键词： 多关键字匹配 交叉链表 硬件实现算法 千兆网络

作者: 李卫 张克农 林海

作者单位: 西安交通大学计算机系、网络化系统与信息安全研究中心,西安 710049 西安交通大学电气工程学院,西安 710049

会议类型: 国内会议

会议名称: 2005全国网络与信息安全技术研讨会

会议地点: 北京

会议语种:中文

页码: 149-155

在线出版日期: 2005-08-30（万方平台首次上网日期，不代表论文的发表时间）