Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

doi:1005-8885 (2008) 02-0097-05

中国邮电高校学报(英文) ›› 2008, Vol. 15 ›› Issue (2): 97-101.doi: 1005-8885 (2008) 02-0097-05

• Microelectronics • 上一篇下一篇

Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

李奇越屈玉贵赵保华

Department of Computer, University of Science and Technology of China, Hefei 230027,China

收稿日期:2007-09-07 修回日期:1900-01-01 出版日期:2008-06-30
通讯作者: 李奇越

Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

LI Qi-yue, QU Yu-gui, ZHAO Bao-hua

Department of Computer, University of Science and Technology of China, Hefei 230027,China

Received:2007-09-07 Revised:1900-01-01 Online:2008-06-30
Contact: LI Qi-yue

摘要/Abstract

摘要：

In network packet processing, high-performance string lookup systems are very important. In this article, an extended Bloom filter data structure is introduced to support value retrieval string lookup, and to improve its performance, a weighted extended Bloom filter (WEBF) structure is generalized. The optimal configuration of the WEBF is then derived, and it is shown that it outperforms the traditional Bloom filter. Finally, an application-specific integrated circuit (ASIC)-based technique using WEBF is outlined.

关键词:

Bloom;filter,;value;retrieval,;string;lookup,;Hash;function,;ASIC

Abstract:

Key words:

Bloom filter;value retrieval;string lookup;Hash function;ASIC

中图分类号:

TN393

LI Qi-yue, QU Yu-gui, ZHAO Bao-hua. Hardware-based high-performance string lookup with value retrieval using extended Bloom filter[J]. Acta Metallurgica Sinica(English letters), 2008, 15(2): 97-101.

参考文献

1. Young H C, William H M. A pattern matching co-processor for network security. Proceedings of IEEE 42nd Annual Conference on Design Automation, Nov 13-17, 2005, Anaheim, CA, USA: Piscataway, NJ, USA: IEEE, 2005: 234-239

2. Haoyu S, John W L. Efficient packet classification for network intrusion detecting using FPGA. Proceedings of the 2005 ACM/SIGDA 13th International Symposium on Field Program- mable Gate Arrays, Sep 12-16, 2005, Monterey, CA, USA. New York, NY, USA: ACM, 2005: 238-245

3. Waldvogel M, Varghese G. Scalable high speed IP routing lookups. Proceedings of the ACM SIGCOMM’97 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Sep 14-18, 1997, France, ACM, 1997: 2-5

4. Sidhu R, Prasanna V K. Fast regular expression matching using FPGAs. Proceedings of the 9th Annual IEEE Symposium on Field Program-mable Custom Computing Machines, Apr 29-May 2, 2001, Rohnert Park, CA, USA. Los Alamitos, CA, USA: IEEE Computer Society, 2001: 227-238

5. Qu Yu-gui, Li Qi-yue. The research on high-speed hardware decoding based on ABNF. The Chinese Journal of Electronics, 2006, 9 (5): 253-256 (in Chinese)

6. Wang Shuo, Qu Yu-gui. Design of a processor for ABNF pattern matching. The Chinese Journal of Electronics, 2007, 35(5): 172-176 (in Chinese)

7. Burton H B. Space/time trade-offs in Hash coding with allowable errors. Communications of the ACM, 1970, 13(7): 422-426

8. Michael M. Compressed Bloom filters. IEEE/ACM Transactions on Networking, 2002, 10(5): 604-612

9. Sarang H S. Fast packet classification using Bloom filters. Proceedings of 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems, Dec 3-5, 2006, San Jose CA, USA. New York, NY, USA: ACM, 2006: 61-70

10. Sarang D, Praveen K, David E T. Longest prefix matching using Bloom filters. Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Aug 25-29, 2003, Karlsruhe, Germany. New York, USA. ACM, 2003: 201-212

11. Bruck, Jie Gao, Jiang An-xiao. Weighted Bloom filter. The 2006 IEEE International Symposium on Information Theory, Jul 9-14, 2006, Seattle, WA, USA. Piscataway, NJ, USA: IEEE, 2006: 2304-2308

12. Ramakrishna M V, Fu E, Bahcekapili E. A performance study of hashing functions for hardware applications. Journal of Computing and Information, 1994, 1(1): 1621-1636

[1]	Zheng Guangming, Zhou Tianle, Lu Haiwei, Long Yifei, Bai Jing. Study on high-order frequency selective surface with interdigital capacitance loading[J]. 中国邮电高校学报(英文版), 2024, 31(1): 57-63.
[2]	Cai Xiumei, He Ningning, Wu Chengmao, Liu Xiao, Liu Hang. Fractional order distance regularized level set method with bias correction[J]. 中国邮电高校学报(英文版), 2024, 31(1): 64-82.
[3]	杨亚涛, 张若菁, 董辉, 马英杰, 张筱薇. WBZUC: novel white-box ZUC-128 stream cipher[J]. 中国邮电高校学报(英文版), 2023, 30(2): 96-106.
[4]	Guan Sihai, Cheng Qing, Zhao Yong, Liu Fangyao. Variable step-size adaptive filtering algorithm based on an exponent sin function[J]. 中国邮电高校学报(英文版), 2023, 30(1): 56-65.
[5]	韩宇南梁珮云林洋程春悦姚雨辰戴琳金铭. Compact multilayer dual-band bandpass filter design using stepped impedance resonators [J]. 中国邮电高校学报(英文版), 2022, 29(5): 99-104.
[6]	Liu Hailing, Zhang Jie, Qin Sujuan, Gao Fei. Quantum algorithm for soft margin support vector machine with hinge loss function[J]. 中国邮电高校学报(英文版), 2022, 29(4): 32-41.
[7]	Meng Wei, Wang Liting, Lu Meng. Summary of research on recommendation system based on serendipity[J]. 中国邮电高校学报(英文版), 2022, 29(4): 89-105.
[8]	Yang Chao, Li Yimin, Li Tong, Xu Siya, Qi Jun, Zhang Yu. Intelligent Service Function Chain Mapping Framework for Cloud-and-Edge-Collaborative IoT[J]. 中国邮电高校学报(英文版), 2022, 29(3): 54-68.
[9]	Shao Zihao, Qu Tianguang, Wang Huiqiang, Zou Yifan, Lv Hongwu. User selection based on user-union and relative entropy in mobile crowdsensing[J]. 中国邮电高校学报(英文版), 2022, 29(3): 34-42.
[10]	卢莹黄世奇王文庆孙柯. Infrared image enhancement algorithm based on adaptive weighted guided filter[J]. 中国邮电高校学报(英文版), 2022, 29(2): 73-84.
[11]	李鸣邱鸿霖徐泉清宋文鹏 Liu Baixiang. Research on cross-chain and interoperability for blockchain system [J]. 中国邮电高校学报(英文版), 2021, 28(5): 1-17.
[12]	崔岩松白春雨. Dynamic load balancing algorithm for distributed system [J]. 中国邮电高校学报(英文版), 2021, 28(5): 91-101.
[13]	杜绪伟陈东刘华江马兆昆杨倩倩. Real-time hand tracking based on YOLOv4 model and Kalman filter[J]. 中国邮电高校学报(英文版), 2021, 28(3): 86-94.
[14]	季一木, 李可, 刘尚东, 刘强, 尧海昌, 李奎. Collaborative filtering recommendation algorithm based on interactive data classification[J]. 中国邮电高校学报(英文版), 2020, 27(5): 1-12.
[15]	吴青高小凤范九伦张恒昌. Application of smoothing technique on twin support vector hypersphere[J]. 中国邮电高校学报(英文版), 2020, 27(3): 31-41.

Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价