基于硬件实现的用于定长匹配的PATRICIA算法

摘要：

PATRICIA算法是一种经典的信息检索算法,但是插入性能差、硬件实现困难.研究发现,PATRICIA算法在用于定长匹配时如果不保持NBT值的有序性,可以有效地降低硬件设计复杂度,提高插入性能.提出了一种易于硬件实现的定长匹配PATRICIA算法,证明了该算法是时间性能最优的二叉trie算法.针对状态检测技术中的状态表操作,设计了专用硬件结构实现该算法.理论和实验结果表明,该算法易于硬件实现,能够有效地对千兆网络环境的状态表进行操作.

关键词：状态表、定长匹配、硬件设计复杂度、PATRICIA

所属期刊栏目：42

分类号：TP393.08(计算技术、计算机技术)

资助基金：国防预研基金41316.3.3

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

页数：共7页

页码：951-957