基于Bloom滤波器的快速路由查找算法研究

摘要

近几年，互联网的发展日新月异，利用互联网进行通信成为越来越多人的选择，这使得网络业务急剧攀升。统计表明，每半年时间Internet的网络业务流量和带宽以及路由器的接口速度就会增加一倍，因而骨干网路由器每秒钟需要转发的数据包数量也随之增加，这给路由器带来了极大的挑战。在路由器的工作过程中，查找路由表是最为耗时的一步，路由查找算法的好坏直接影响到路由器的性能。因此，路由查找算法一直是近几年研究的热点问题。
　　首先，对路由查找算法的相关基础技术进行了研究，主要内容包括:(1)分析了无类域间路由技术的产生背景及实现方法;(2)对IPv6技术与IPv4技术进行了详细的对比，并对IPv6技术中与路由查找技术密切相关的地址结构问题进行了深入分析;(3)研究了Bloom滤波器的基本工作原理和性能评价指标，并对几种典型的改进型Bloom滤波器进行了分析。
　　其次，提出了一种基于Bloom滤波器的快速最长前缀匹配路由查找算法。该算法涉及一张根据路由表信息构造的首字节索引表、一组用于存储和查询不同长度前缀的Bloom滤波器，以及一组基于IP地址前缀进行报文转发的选路索引表。对于待查询的目的IP地址，首先提取首字节信息，并在首字节索引表中进行匹配，找出所有可能的前缀长度;然后在相应前缀长度的Bloom滤波器中进行匹配查找;最后根据匹配查找结果在选路索引表中选择相应的路由进行报文转发。针对探测时间和空间复杂度等指标对算法进行了性能分析。数值分析和实验结果表明，算法可以实现每次路由查找仅需接近一次选路索引表探测，时间性能较之现有的算法有明显提升。
　　最后，针对骨干网中IPv6路由器的全球可聚合单播地址提出了一种基于Bloom滤波器和可控前缀扩展的路由查找算法。算法首先根据全球可聚合单播IPv6地址的前缀分布特点，将IPv6地址进行可控前缀扩展，分别扩展至24bits、32bits、48bits和64bits;采用含有三个Bloom滤波器的滤波器组分别存储和查询扩展后为32bits、48bits和64bits的前缀信息，采用一个直接索引数组存储和查找扩展后为24bits的前缀信息。对于待查询的目的IP地址，在存储查找相应前缀长度的Bloom滤波器和直接索引数组中进行匹配查找;根据匹配查找结果在选路索引表中选择相应的路由进行报文转发。针对算法的查找时间和选路索引表探测次数，对算法进行了性能分析。数值分析和实验结果表明，算法在合理选取Bloom滤波器组参数时，能取得很好的时间和空间性能。

目录

声明

摘要

1 绪论

1．1 研究背景

1．2 路由查找算法的研究现状

1．3 主要研究内容

1．4 论文章节安排

2 路由查找算法的相关技术基础

2．1 无类域问路由技术

2．2 IPv6技术

2．3 Bloom滤波器的技术

2．3．1 基本原理

2．3．2 主要技术指标

2．3．3 改进型Bloom滤波器

2．4 本章小结

3 基于Bloom滤波器的IPv4快速路由查找算法

3．1 概述

3．2 算法基本原理

3．3 算法的关键过程

3．3．1 算法的查找过程

3．3．2 算法对更新的支持

3．4 算法性能分析

3．4．1 选路索引表探测次数研究

3．4．2 算法参数选择

3．5 实验与结果分析

3．5．1 基于Matlab的数值仿真及结果分析

3．5．2 针对实际路由数据的实验及结果分析

3．6 本章小结

4 基于Bloom滤波器的IPv6快速路由查找算法

4．1 概述

4．2 算法基本原理

4．3 算法的关键过程

4．3．1 算法的查找过程

4．3．2 算法对更新的支持

4．4 性能分析

4．5 实验验证

4．6 本章小结

结论

参考文献

攻读硕士学位期间发表学术论文情况

致谢