专利详情

专利名称	一种实现无回溯的最长前缀匹配搜索的方法和装置
申请号	CN200610165449.9	专利类型	发明专利
公开（公告）号	CN1996953	公开（授权）日	2007.07.11
申请（专利权）人	中国科学院计算技术研究所	发明（设计）人	张飞飞;鄢贵海;付斌章;李华伟;韩银和;刘彤;雷韶华
主分类号	H04L12/56(2006.01)	IPC主分类号	H04L12/56(2006.01);G06F17/30(2006.01)
专利有效期	一种实现无回溯的最长前缀匹配搜索的方法和装置至一种实现无回溯的最长前缀匹配搜索的方法和装置	法律状态	授权
说明书摘要	本发明公开了一种实现无回溯的最长前缀匹配搜索的装置，包括第一选择器、第二选择器、第三选择器、第一加法器、第二加法器、第一或门、第二或门、第三或门、多路选择器、译码器、掩码生成单元和比较部件，还包括输入信息寄存器组、树结点寄存器组、树结点读取部件、叶索引表读取部件、比较结果寄存器、叶结点信息寄存器组、搜索结果寄存器组和控制信号生成部件。本发明还公开了一种实现无回溯的最长前缀匹配搜索的方法。本发明采用的无回溯的路径压缩的二进制树的结构及搜索方法，可提高搜索效率并降低存储空间消耗；本发明采用叶子索引的机制，可减少实现查找的存储空间开销。