IPv6融合树结构存储及快速查找

作者：张沛; 陈文龙; 唐晓岚

来源：小型微型计算机系统, 2018, 39(12): 2640-2645.

• IPv6
• 主干路由
• 回溯指针
• 融合存储

IPv6具有128位的超大地址空间,但地址容量的增加也给路由存储及查找带来极大困难,传统的存储结构(如Trie树)无法直接适用于IPv6.分析IPv6主干网路由的特征,包括:路由前16位取值极少、前缀长度为32及48位的路由数量较多等.由此,提出了一种多比特Trie树的变化结构来实现IPv6路由的存储.根据IP前缀前16位的不同取值划分不同的路由Trie树;每一棵Trie树包括2层节点(不包含树根),分别对应掩码长度为32和48的路由;其它掩码长度的路由则根据前缀取值相同的原则,作为附加信息依附在对应节点.路由查找时,直接定位树节点,并通过回溯指针确保快速完成最长前缀匹配.为了避免耗费较大的存储空间,在Trie树第三层节点进行融合存储,极大地提升了路由存储效率.相比于其它路由存储方式,本机制能实现IPv6路由的快速查找,极大提高转发速度.

• 单位
  首都师范大学