Analysis of a Bloom Filter Algorithm via the Supermarket Model

Details Analysis of a Bloom Filter Algorithm via the Supermarket Model Analysis of a Bloom Filter Algorithm via the Supermarket Model

2009-03-12

arxiv.org/abs/0903.2134v1

Computer Science

Discrete Mathematics

Scientific paper

This paper deals with the problem of identifying elephants in the Internet Traffic. The aim is to analyze a new adaptive algorithm based on a Bloom Filter. This algorithm uses a so-called min-rule which can be described as in the supermarket model. This model consists of joining the shortest queue among d queues selected at random in a large number of m queues. In case of equality, one of the shortest queues is chosen at random. An analysis of a simplified model gives an insight of the error generated by the algorithm on the estimation of the number of the elephants. The main conclusion is that, as m gets large, there is a deterministic limit for the empirical distribution of the filter counters. Limit theorems are proved and the limit is identified. It depends on key parameters. The condition for the algorithm to perform well is discussed. Theoretical results are validated by experiments on a traffic trace from France Telecom and by simulations.

Affiliated with

Also associated with

No associations

Rating

Analysis of a Bloom Filter Algorithm via the Supermarket Model 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 Analysis of a Bloom Filter Algorithm via the Supermarket Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of a Bloom Filter Algorithm via the Supermarket Model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-36225