bloom filter in netfilter?

[Patrick McHardy]

Sebastien Tandel wrote:
>    I'm wondering if bloom filters could not improve performance of the
> conntracker. For a quick overwiew of bloom filters see
> http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/BloomFilterSurvey.pdf
> 
> In a few words, a bloom filter is a data structure which represents
> concisely a set. When you have a set, you can decide very quickly if an
> element belongs to it.
> 
> I was then wondering if we could not get rid of these two
> list_for_each_entry in the __nf_conntrack_confirm by using the bloom
> filters.


With a properly sizes hash table the buckets should have only
a single entry on average. The problem with bloom filters is
that its quite expensive to calculate enough hash bits for
a large filter with a low probability of false positives.

> You can use it as a key for a hash table as well. And therefore we may
> use them at a later stage for the hash table as well. But let's see
> first if you're interested by the previous idea ;)
> 
> What do you think?


I thought about using them for caching packet classification results
(DROP/ACCEPT) some time ago. Never got around to try it though.