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

A Hardware-Based PATRICIA Algorithm for Fixed-Length Match

作　　者：李鑫[1] 胡铭曾[1] 季振洲[1] 

机构地区：[1]哈尔滨工业大学计算机科学与工程系,哈尔滨150001

出　　处：《计算机研究与发展》2005年第6期951-957,共7页Journal of Computer Research and Development

基　　金："十五"国防预研基金项目(41316.3.3)

摘　　要：PATRICIA算法是一种经典的信息检索算法,但是插入性能差、硬件实现困难.研究发现,PATRICIA算法在用于定长匹配时如果不保持NBT值的有序性,可以有效地降低硬件设计复杂度,提高插入性能.提出了一种易于硬件实现的定长匹配PATRICIA算法,证明了该算法是时间性能最优的二叉trie算法.针对状态检测技术中的状态表操作,设计了专用硬件结构实现该算法.理论和实验结果表明,该算法易于硬件实现,能够有效地对千兆网络环境的状态表进行操作.PATRICIA algorithm has become a classic method for information retrieval. But PATRICIA insertion is time-consuming. By analyzing PATRICIA, it is discovered that not keeping the order of NBTs(next bit to test) in PATRICIA trie can improve the performance of PATRICIA insertion and decrease hardware design complexity. A new PATRICIA algorithm for fixed-length match is proposed. It is proved that this algorithm is an optimal binary trie-based algorithm. An ASIC (application specific integrated circuit) for this algorithm is implemented for the application of state table of stateful inspection. The theoretical and experimental results show that this algorithm can work very well for the application of state table in gigabit network.

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

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]