bloom filter in netfilter?
kaber at trash.net
Tue Mar 20 16:20:30 CET 2007
Sebastien Tandel wrote:
> I'm wondering if bloom filters could not improve performance of the
> conntracker. For a quick overwiew of bloom filters see
> 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
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.
More information about the netfilter-devel