一种实现无回溯的最长前缀匹配搜索的方法和装置

摘要

本发明公开了一种实现无回溯的最长前缀匹配搜索的装置，包括第一选择器、第二选择器、第三选择器、第一加法器、第二加法器、第一或门、第二或门、第三或门、多路选择器、译码器、掩码生成单元和比较部件，还包括输入信息寄存器组、树结点寄存器组、树结点读取部件、叶索引表读取部件、比较结果寄存器、叶结点信息寄存器组、搜索结果寄存器组和控制信号生成部件。本发明还公开了一种实现无回溯的最长前缀匹配搜索的方法。本发明采用的无回溯的路径压缩的二进制树的结构及搜索方法，可提高搜索效率并降低存储空间消耗；本发明采用叶子索引的机制，可减少实现查找的存储空间开销。

主权项

1、一种实现无回溯的最长前缀匹配搜索的装置，其特征在于，包括第一选择器(10)、第二选择器(11)、第三选择器(12)、第一加法器(14)、第二加法器(15)、第一或门(16)、第二或门(17)、第三或门(18)、多路选择器(19)、译码器(20)、掩码生成单元(21)和比较部件(22)；还包括输入信息寄存器组(1)、树结点寄存器组(2)、树结点读取部件(4)、叶索引表读取部件(5)、比较结果寄存器(6)、叶结点信息寄存器组(7)、搜索结果寄存器组(8)和控制信号生成部件(9)；其中，所述的输入信息寄存器组(1)与所述的多路选择器(19)、第一选择器(10)、第二加法器(15)连接；所述的树结点寄存器组(2)分别与所述的第一选择器(10)、第一加法器(14)、第二加法器(15)、树结点读取部件(4)和译码器(20)电连接；所述的第一选择器(10)还连接到第一加法器(14)上，所述的第一加法器(14)则与所述的多路选择器(19)连接；所述的树结点读取部件(4)与多路选择器(19)和外部的存储器(3)电连接，所述的存储器(3)还与所述的叶索引表读取部件(5)电连接，所述的叶索引表读取部件(5)与所述的第二加法器(15)、叶结点信息寄存器组(7)电连接；所述译码器(20)分别与所述的第一或门(16)、第二或门(17)、第三或门(18)和掩码生成单元(21)电连接，所述的第三或门(18)与所述的多路选择器(19)连接，所述的第一或门(16)与所述的比较结果寄存器(6)电连接，所述的掩码生成单元(21)还与叶结点信息寄存器组(7)、比较部件(22)相连，所述的比较部件(22)分别与所述的输入信息寄存器组(1)、比较结果寄存器(6)、第二选择器(11)和第三选择器(12)电连接，所述的叶结点信息寄存器组(7)分别与第二选择器(11)、第三选择器(12)电连接，所述的第二选择器(11)、第三选择器(12)分别连接到所述的搜索结果寄存器组(8)上。