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

Fast IPv6 routing lookup combining B-tree and bloom filter

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

In order to improve the efficiency of IPv6 routing lookup,this paper put forward an IPv6 routing lookup algorithm( BTBF) based on the combination of B-tree and bloom filter for the uneven distribution of IPv6 routing prefix. BTBF included two parts,namely,B-tree and bloom filter lookup: firstly,this paper looked up the first 16 bit value of routing prefix with Btree,and linked the next step to bloom filter through the mapping of middle bit vector of B-tree node;then,it extracted the next hop through the value mapping of bloom filter bit array. The experimental results show that,compared with other tree and bloom filter algorithms,BTBF algorithm can effectively reduce space and time,and maintain stable routing performance under the condition of larger changes in routing-table entries.