基于分组TCAM实现相交前缀与不相交前缀的分组。目的是实现稀疏路由表分组,其中所有不相交前缀路由项存储在TCAMB,实现稀疏存在的不相交前缀部分的ip能够精确匹配;将相交前缀部分存储于TCAMA,并设定TCAMA长度n,相交前缀若小于n则直接存储在TCAMA中,若大于n则截取前n位存储与TCAMA,后(128-n)位存储与trie树中。
采用16叉trie树存储结合单链表的形式存储,在不能精确匹配的位置采用单链表存储剩余匹配项不足4位的项,并以剩余位数长度降序存储,最终实现相交前缀的精确查找最长匹配。单链表实现部分待更新... 比如说:0010 0010 00xx .... 0010 0010 000x ..... 就需要将这两条记录与mask相与后存储在0010 0010对应trie树节点中
TCAM在一个时钟周期内可以找到所有相匹配的前缀项,具体了解可以网上查找相关资料
原始专利在212的指针含有r个bit,包含2的r次方个trie树。
基于专利:US20140086249A1 进行的拓展优化。