基于Bloom滤波器的缓存路由表快速查找算法

摘要

路由器是网络互连的关键设备.随着因特网的快速发展和业务量的迅猛增长,对路由器的吞吐性能提出了更高的要求,尤其是对骨干网核心路由器.在当前的路由机制(包括IPv4和IPv6)中,路由表查找是实现高性能路由器(吞吐能力达100Mpps)的主要瓶颈之一.近年来,为提高IP路由表的查找速度,人们已提出了许多解决方案.影响路由表查找速度的因素很多,如基础软硬件的处理速度、路由表的大小、最长前缀匹配、路由更新频率等,其中最长前缀匹配是关键因素.传统路由表查找算法可大致分为两类:基于CAM(内容可寻址存储器)和基于RAM(随机寻址存储器)的路由表查找.这两类算法各有优劣,CAM算法的主要缺点是内存访问速度慢,而RAM算法的平均内存访问次数过多.2003年,D.Sarang等人首次把Bloom滤波器应用于路由表查找.Bloom滤波器是一种随机化的数据结构,可为信息检索提供高效的计算算法,并具有实现简单和节约存储空间等优点.但是Bloom滤波器存在一定的正向误检(false positive)概率.尽管Bloom滤波器在70年代就已经被发明,然而只在近几年才得到重视和应用.Sarang等人的方案,通过扩展前缀的方式,利用了2个并行Bloom滤波器计算匹配前缀位长,并结合Hash查找技术,可使平均RAM内存访问次数接近于1.该文在Sarang方案的基础上,进一步考虑了因特网实际业务流所具有的临时集中性特点,引入了缓存机制.通过在Hash表中添加补充前缀的手段,消除同一前缀查找重复出现误检的缺点,以期更大地提高路由表查找的计算性能.针对该文所设计的缓存算法,采用VHDL语言模拟仿真Bloom滤波器功能,并测试滤波器的各项参数.依据实际观察,模拟生成具有强突发性的IP业务流.结合多个核心路由器的实际统计数据,对算法的性能进行了仿真分析.结果得到,引入缓存机制,可使Bloom滤波器的正向误检概率降低80％以上.研究表明,加入缓存机制,不仅可提高路由表查找速度,还可为简化Bloom滤波器的设计提供指导性的依据.

目录

文摘

英文文摘

南京邮电学院学位论文独创性声明和南京邮电学院学位论文使用授权声明

第一章引言

第二章路由表查找原理

2.1路由器基本原理

2.2路由协议

2.2.1 RIP协议

2.2.2 OSPF协议

2.2.3 BGP协议

2.3 IP地址分类技术

2.4 IP路由表查找技术

2.4.1路由表查找的重要性

2.4.2最长前缀匹配

2.4.3 IP路由表查找算法设计要求

第三章传统路由表查找算法

3.1路由表查找算法分类

3.2基于CAM的路由表查找算法

3.3基于RAM的路由表查找算法

3.3.1基于前缀值的路由表查找算法

3.3.2基于前缀长度的路由表查找算法

3.3.3基于协议的路由表查找

3.4算法性能对比

第四章采用Bloom滤波器的路由表查找算法

4.1Bloom滤波器

4.1.1基本结构

4.1.2查找计算过程

4.1.3正向误检性质

4.2应用Bloom滤波器的快速路由表查找算法

4.2.1基本配置

4.2.2优化配置

第五章缓存前缀的LPMBF算法

5.1流量因素对路由表查找性能的影响

5.2缓存前缀算法

5.2.1流量因素对LPMBF算法性能的影响

5.2.2算法及设计方案

5.2.3查找性能的理论分析

第六章算法的仿真研究

6.1 Bloom滤波器的性能分析

6.2 Bloom滤波器的模拟仿真

6.3缓存路由前缀的LPMBF算法性能分析

6.3.1实际BGP表中的前缀扩展分析

6.3.2实际前缀对Bloom滤波器特性的影响

6.3.3业务流生成模型

6.3.4算法性能测试方案

6.3.5测试结果和性能对比

6.4 Hash表查找性能分析

总结

参考文献

致谢

作者研究生阶段发表的论文