电子学报 ›› 2015, Vol. 43 ›› Issue (9): 1833-1840.DOI: 10.3969/j.issn.0372-2112.2015.09.023

• 学术论文 • 上一篇    下一篇

一种基于并行Bloom Filter的高速URL查找算法

周舟1, 付文亮2, 嵩天2, 刘庆云1   

  1. 1. 中国科学院信息工程研究所信息内容安全技术国家工程实验室, 北京 100093;
    2. 北京理工大学计算机学院, 北京 100081
  • 收稿日期:2014-03-16 修回日期:2014-07-11 出版日期:2015-09-25
    • 通讯作者:
    • 刘庆云
    • 作者简介:
    • 周舟 男,1983年生,湖南长沙人,博士,助理研究员.主要研究方向为网络安全、高性能网络.E-mail:zhouzhou@iie.ac.cn;付文亮 男,1984年生,河北邯郸人,博士研究生.主要研究方向为网络安全、节能网络.E-mail:fuwenl@bit.edu.cn;嵩天 男,1980年生,辽宁沈阳人,博士,副教授.主要研究方向为网络安全、计算机体系结构.E-mail:songtian@bit.edu.cn
    • 基金资助:
    • 国家高技术研究发展计划 ("863"计划)基金 (No.2011AA010703); 中国科学院战略性先导科技专项基金 (No.XDA06030200); 国家自然科学基金 (No.61402474)

Fast URL Lookup Using Parallel Bloom Filters

ZHOU Zhou1, FU Wen-liang2, SONG Tian2, LIU Qing-yun1   

  1. 1. National Engineering Laboratory for Information Security Technologies Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China;
    2. School of Computer Science, Beijing Institute Engineering, Chinese Acadenmy of Sciences, Beijing 100081, China
  • Received:2014-03-16 Revised:2014-07-11 Online:2015-09-25 Published:2015-09-25
    • Supported by:
    • Foundation of National High-tech R&D Program of China  (863 Program) (No.2011AA010703); Chinese Academy of Sciences Strategic Pilot Project Fund (No.XDA06030200); National Natural Science Foundation of China (No.61402474)

摘要:

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

关键词: URL查找, 布鲁姆过滤器, 最长前缀匹配, 现场可编程门阵列

Abstract:

URL lookup is fundamental to numerous networking systems,including URL filters,web caches,etc.With the explosive development of the Internet,the main challenge in implementing URL lookup operation is to achieve fast lookup speed and accommodate large URL sets while keeping memory and power consumption low.This paper presents a new URL lookup scheme based on parallel Bloom Filters.It can adapt to set cardinality and perform fast longest prefix matching(LPM)with large URL sets in a highly parallel fashion.The theoretical analysis and experiments on real-life data traces show that the proposed approach leads to reduced false positive probability for up to an order of magnitude(or reduced memory and hardware logic resources with the same false positive probability guaranteed)compared with the existing methods.Moreover,the architecture can be easily mapped to the state-of-the-art FPGAs with moderate resource consumption to provide over 150M lookups per second.

Key words: URL lookup, Bloom filter, longest prefix matching, FPGA

中图分类号: