Re: bloom filter in netfilter?

[Pablo Neira Ayuso <pablo@netfilter.org>]

Hi Sebastien,

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

Yes, I know that work.

> 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.

We can't just get rid of it since bloom filters have false positives, so 
it could happen that we could miss some new connections that are not 
actually in the conntrack table.

-- 
The dawn of the fourth age of Linux firewalling is coming; a time of 
great struggle and heroic deeds -- J.Kadlecsik got inspired by J.Morris