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

作     者：李鑫 胡铭曾 季振洲 Li Xin;Hu Mingzeng;Ji Zhenzhou

作者机构：哈尔滨工业大学计算机科学与工程系哈尔滨150001 

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

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2005年第42卷第6期

页      码：951-957页

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

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

学科分类：0839[0839] 08[工学] 

核心收录：

D　O　I：10.1360/crad20050608

馆 藏 号：203525601...