Acta Metallurgica Sinica(English letters) ›› 2008, Vol. 15 ›› Issue (2): 97-101.doi: 1005-8885 (2008) 02-0097-05

• Wireless • Previous Articles     Next Articles

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

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

CLC Number: