Bloom filters: Design innovations and novel applications

Yi Lu, Balaji Prabhakar, Flavio Bonomi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Bloom filters have been very interesting in networking because they enable the high speed, low cost implementation of various hardware algorithms. This paper introduces the idea of variable-length signatures, as opposed to the current practice of using fixed-length signatures. This idea naturally enables Bloom filters to perform flow deletions, a well-known problem with standard Bloom filters. Other uses of this idea are also presented and explored. A second contribution of the paper is the use of a bank of Bloom filters to identify the action that must be applied to the packets of a flow, or to dynamically record the state a flow is in. Our work shows that this approach is a promising alternative to expensive CAM or hash table lookups, and suggests a method of building cheap "fuzzy" flow memories.

Original languageEnglish (US)
Title of host publication43rd Annual Allerton Conference on Communication, Control and Computing 2005
PublisherUniversity of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering
Pages1006-1015
Number of pages10
ISBN (Electronic)9781604234916
StatePublished - Jan 1 2005
Externally publishedYes
Event43rd Annual Allerton Conference on Communication, Control and Computing 2005 - Monticello, United States
Duration: Sep 28 2005Sep 30 2005

Publication series

Name43rd Annual Allerton Conference on Communication, Control and Computing 2005
Volume2

Other

Other43rd Annual Allerton Conference on Communication, Control and Computing 2005
CountryUnited States
CityMonticello
Period9/28/059/30/05

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Bloom filters: Design innovations and novel applications'. Together they form a unique fingerprint.

  • Cite this

    Lu, Y., Prabhakar, B., & Bonomi, F. (2005). Bloom filters: Design innovations and novel applications. In 43rd Annual Allerton Conference on Communication, Control and Computing 2005 (pp. 1006-1015). (43rd Annual Allerton Conference on Communication, Control and Computing 2005; Vol. 2). University of Illinois at Urbana-Champaign, Coordinated Science Laboratory and Department of Computer and Electrical Engineering.