B-树和bloom filter相结合的IPv6路由查找算法

来源：计算机应用研究杂志2019年第9期北京时间：

作者：姚明,赵晶晶,贺兴亚,杨云,

单位：扬州大学信息工程学院,江苏扬州225005；

摘要：为了提高IPv6的路由查找效率，针对IPv6路由前缀分布不均匀的问题，提出了一种基于B-树和bloom filter相结合的IPv6路由查找算法（BTBF）。BTBF分为B-树和bloom filter查找两部分，利用B-树查找路由前缀的前16 bit值，然后通过B-树节点中位向量的映射，将下一步链接到bloom filter，再利用bloom filter位数组的值映射提取下一跳。实验结果表明，BTBF算法与其他树型和bloom filter类算法相比有效减少了空间和时间占用，在路由表项数变化较大的情况下也能维持稳定的查找性能。

关键词：路由查找算法,B-树,bloomfilter,IPv6骨干路由表,

基金资助：江苏省产学研前瞻性资助项目(BY2016069)；；