http://iet.metastore.ingenta.com
1887

Balanced counting Bloom filters: a space-efficient synoptic data structure for a high-performance network

Balanced counting Bloom filters: a space-efficient synoptic data structure for a high-performance network

For access to this article, please select a purchase option:

Buy article PDF
$19.95
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

A Bloom filter is a simple space-efficient randomised data structure allowing membership queries over data sets. It is widely utilised in peer-to-peer network, traffic measurement and distributed systems. Aiming at the deficiencies of the naïve counting Bloom filters (NCBFs), a novel data structure called balanced counting Bloom filters (BCBFs) is presented. In order to achieve space-efficient storage and effective query, the BCBF adopts the following methods: introducing hash fingerprints, partitioning bucket vectors into equally sized segments and storing elements with the least load bucket. Analytical expressions are deduced in detail based on the theory of differential equations and probability. Besides, simulations are conducted based on the data produced by computer and real network trace. The results demonstrate that the BCBF cannot only serve the same functionality as the NCBF using much less space, but also becomes a valuable tool in hardware to scale the high-speed link.

References

    1. 1)
    2. 2)
    3. 3)
      • Kumar, A., JimXu, J., Wang, J.: `Space-code BF for efficient per-flow traffic measurement', Proc. IEEE INFOCOMM, 2004, Hongkong, p. 315–328.
    4. 4)
      • Estan, C.: `New directions in traffic measurement and accounting', Proc. ACM SIGCOMM, 2002, Oklahoma City, p. 562–574.
    5. 5)
    6. 6)
      • Heeyeol, Y., Mahapatra, R.: `A memory-efficient hashing by multi-predicate BFs for packet classification', Proc. IEEE INFOCOM, 2008, Washington, p. 1795–1803.
    7. 7)
      • Whitaker, A., Wetherall, D.: `Forwarding without loops in Icarus', Proc. IEEE Openarch, 2002, Washington, p. 63–75.
    8. 8)
    9. 9)
    10. 10)
      • Saar, C., Yossi, M.: `Spectral BFs', Proc. ACM SIGMOD Int. Conf. on Management of Data, 2003, San Diego, p. 241–252.
    11. 11)
      • Xie, K., Min, Y., Zhang, D., Xie, G., Wen, J.: `Basket BFs for membership queries', Proc. TENCON, 2005, Melbourne, p. 1–6.
    12. 12)
    13. 13)
    14. 14)
    15. 15)
    16. 16)
      • A. Shwartz , A. Weiss . (1995) Large deviation for performance analysis queues, communication, and computing.
    17. 17)
      • M. Mitzenmacher , E. Upfal . (2005) Probability and computing: randomized algorithm and probabilistic analysis.
    18. 18)
      • http://pma.nlanr.net, accessed January 2006.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com.2011.0961
Loading

Related content

content/journals/10.1049/iet-com.2011.0961
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address