In-packet Bloom filters: Design and networking applications

Details In-packet Bloom filters: Design and networking applications In-packet Bloom filters: Design and networking applications

2009-08-25

arxiv.org/abs/0908.3574v2

Computer Science

Data Structures and Algorithms

15 pages, 11 figures, preprint submitted to Elsevier COMNET Journal

Scientific paper

The Bloom filter (BF) is a well-known space-efficient data structure that answers set membership queries with some probability of false positives. In an attempt to solve many of the limitations of current inter-networking architectures, some recent proposals rely on including small BFs in packet headers for routing, security, accountability or other purposes that move application states into the packets themselves. In this paper, we consider the design of such in-packet Bloom filters (iBF). Our main contributions are exploring the design space and the evaluation of a series of extensions (1) to increase the practicality and performance of iBFs, (2) to enable false-negative-free element deletion, and (3) to provide security enhancements. In addition to the theoretical estimates, extensive simulations of the multiple design parameters and implementation alternatives validate the usefulness of the extensions, providing for enhanced and novel iBF networking applications.

Affiliated with

Also associated with

No associations

Rating

In-packet Bloom filters: Design and networking applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with In-packet Bloom filters: Design and networking applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and In-packet Bloom filters: Design and networking applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-233098