For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Incrementally Updatable Bloom Filter and Network Application
IEICE TRANSACTIONS on Communications
Publication Date: 2009/11/01
Online ISSN: 1745-1345
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Fundamental Theories for Communications
Bloom filter, network caching, streaming algorithm,
Full Text: PDF(109.7KB)>>
Bloom filters are widely used for various network applications. Because of the limited size of on-chip memory and the large volume of network traffic, Bloom filters are often required to update their contents incrementally. Two techniques have been used for this purpose: cold cache and double buffering. Cold cache outperforms double buffering in terms of the average cache ratio. However, double buffering works much better than cold cache for the worst-case cache hit ratio. In this paper, we propose a new updating scheme for Bloom filters, which updates the contents of Bloom filter incrementally while the assigned memory space is fully utilized. The proposed scheme works better than cold cache in terms of the average cache hit ratio. At the same time, it outperforms double buffering for the worst-case cache hit ratio.