Bloom Filters: Design Innovations and Novel Applications
Bloom filters have been very interesting in networking because they enable the high speed, low cost implementation of various hardware algorithms. The 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.