Re: bloom filter in netfilter?

[Patrick McHardy <kaber@trash.net>]

Patrick Schaaf wrote:
>>>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.
>>
>>That wouldn't be a big problem in my opinion, you can freely tune the
>>probability.
> 
> 
> Wouldn't two conntrack entries in the hash for the same tuples be
> catastrophic somewhere? (I have no idea, actually)


Yes, but bloom filters only have false positives (already in
hash, so skip confirmation), never false negatives, so that
would still not happen.

> The other thing about bloom filters that worries me, having read
> the wikipedia entry, is that you cannot remove elements. Probability
> of false positives thus increases as conntracks are added. And a
> future repetition of exactly the same tuple would certainly be
> a false positive. Tuples repeat pretty fast with things like BGP,
> and a filter regeneration seems to involve shuffling all current
> conntracks into a fresh bloom filter.
> 
> Either I misunderstand something fundamental, which is not
> unlikely, or that kills the idea.


You're right, tuple reuse is a problem, it seems counting bloom
filters would be needed to deal with that, which are a lot less
memory efficient. The increasing probabilities of false positives
with increasing number of entries could be dealt with by using a
second bloom filter that is filled with new entries once a low
threshold is exceeded and replaces the active one once a high
threshold is exceeded.

I have to admit that I'm a huge fan of bloom filters and always
wanted to use them for something cool :)