%0 Journal Article %A 周舟 %A 付文亮 %A 嵩天 %A 刘庆云 %T 一种基于并行Bloom Filter的高速URL查找算法 %D 2015 %R 10.3969/j.issn.0372-2112.2015.09.023 %J 电子学报 %P 1833-1840 %V 43 %N 9 %X

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

%U https://www.ejournal.org.cn/CN/10.3969/j.issn.0372-2112.2015.09.023