一种基于并行Bloom Filter 的高速URL 查找算法
摘 要:URL 查找是众多网络系统中重要的组成部分,如URL 过滤系统、Web 缓存等.随着互联网的迅速
发展,URL 查找面临的主要挑战是实现大规模URL 集合下的高速查找,同时保证低存储和低功耗.本文提出了
一种基于并行Bloom Filter 的URL 查找算法,CaBF.该算法高度并行化,提供大规模URL 集合下的高速最长前
缀匹配,并很好地适应集合中不同数量的URL 组件.理论分析和真实网络数据集上的实验表明,该算法相比现有
算法可以降低假阳性概率达一个数量级(或者在满足相同假阳性概率的前提下降低存储和硬件逻辑资源消耗).
此外,该方法的体系结构很容易映射到FPGA 等硬件器件上,提供每秒超过150M 次的URL 查找速度.
关键词:URL 查找;布鲁姆过滤器;最长前缀匹配;现场可编程门阵列