路由器是网络互连的关键设备.随着因特网的快速发展和业务量的迅猛增长,对路由器的吞吐性能提出了更高的要求,尤其是对骨干网核心路由器.在当前的路由机制(包括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滤波器的设计提供指导性的依据.