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

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