中国邮电高校学报(英文) ›› 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

李奇越 屈玉贵 赵保华   

  1. 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   

  1. 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

摘要:

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:

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.

Key words:

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

中图分类号: