bloom filter in netfilter?
standel at info.ucl.ac.be
Wed Mar 21 13:45:15 CET 2007
-----BEGIN PGP SIGNED MESSAGE-----
one must read 2^16 buckets and not 216 ... of course.
Sebastien Tandel wrote:
>>>> That wouldn't be a big problem in my opinion, you can freely tune
>>>> the probability.
>>>>> In the specific case I was speaking about, you don't expect to
>>>>> find anything. Therefore, as Patrick says, if you tune the
>>>>> probability of false positives, you should not expect ones really
>>>>> often. If one occurs, of course, you have to verify it in the
>>> But the case in which we don't expect to find anything is the worst
>>> case, eg. someone is generating trash traffic to stress the
>>> conntrack system. So this can be considered as a hardening
> In the case of the traversal of the two lists in "nf_conntrack_confirm"?
> You're not expecting the race from NAT at every call, do you? Or have I
> missed something in the code?
>>> Anyway, we would need to evaluate the impact of such solution in
>>> terms of memory consumption (probably something from 4KB to 16KB)
>>> and extra CPU cycles due to hashing.
> Yes, of course I do not imagine that it will be very useful for people
> at home with only a few connections at a time.
>>> Of course, previously we would have to get some numbers
>>> to know how bad is currently the worst case.
> Indeed, it would be good.
>>> I have some experimental stuff on bloom filters at my people
>>> netfilter place that I needed for some works here at the university,
>>> it can't be used for any productive purposes but you could use it as
>>> a starting point.
> Why? what are your deceptions about these bloomy things?
> I've looked at your bloom-experiments.tgz. Do you think one sha1 is
> slower than this implementation of hash in your modulo.c? Do you really
> think it will be random?
> One sha1 computation should suffice to compute what you need. The digest
> is of 160 bits. If you want 216 buckets, you may generate 10 bits hash.
> Could the sha1 algorithm from the kernel take advantage of cryptography
> dedicated chipset?
> One another nice property of counting bloom filters is that you have the
> opportunity to perform some kind of "repartition" in your hash table.
> But as Patrick has mentioned earlier, the drawback is the memory
> consumption, if you want to avoid this memory consumption, it will take
> much more CPU cycles.
> Sebastien Tandel
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
-----END PGP SIGNATURE-----
More information about the netfilter-devel