Skip to content

采用分组TCAM结合trie树+单链表的结构实现ipv6最长前缀匹配

Notifications You must be signed in to change notification settings

jiejie1993/ipv6_longest_prefix_match

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

3 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

ipv6_longest_prefix_match

基于分组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 进行的拓展优化。

About

采用分组TCAM结合trie树+单链表的结构实现ipv6最长前缀匹配

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages