Bloom-bird: a scalable open-source router based on Bloom Filter

[Ondrej Zajicek]

On Fri, Jan 09, 2015 at 06:01:30PM +0000, Bahram BahramBeigy wrote:
> We have accelerated FIB lookups (fib_find() and fib_route()) using a data
> structure named Bloom Filter when number of inserted nodes into FIB becomes
> huge, for example more than 200,000 IPs are inserted into one FIB.
> Consequently, the linked list chains becomes huge, the Bloom filter avoids
> traverse these long chains when an IP cannot be found.
> 
> The paper:
> http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6999678
> 
> Please let me know your opinion about it.
> Or any suggestions ...

Hello

Thanks for your interest and information. I glimpsed at the paper
and have some questions:

1) Are the code modifications available?

2) Do you have the bloom filter integrated in BIRD or just have synthetic
benchmarks for FIB lookup performance? If it as tested integrated in
BIRD, how exactly? I cannot find it described in section IV. A

3) I can't find bloom_hash() code in the paper.

3) In tables 3, 4 on diagonal (marked with (*)) is that just
a time of initial insertions? So there are no results for test
cases with 0 % miss rate?

4) I am not sure what is the exact definition of the speedup in the tables.
Is it (T_old / T_new) - 1? Or is it 1 - (T_new / T_old)?


5) There is (AFAIK) no deep reason why FIB hash tables in BIRD are
limited to 16 bits. This is something that should be fixed to have proper
FIB performance scaling, (there are currently some implementation details
that depends on this so it is not just increasing of the constant, but 
these details should be fixed). If the hash function used in bloom_hash()
has significantly less collisions that one from ipa_hash(), then we also
should fix the hash function in BIRD.

Therefore, the main question is whether there would be a reasonable
advantage when using bloom filters with fixed hash tables compared to
just using fixed hash tables.

-- 
Elen sila lumenn' omentielvo

Ondrej 'Santiago' Zajicek (email: santiago at crfreenet.org)
OpenPGP encrypted e-mails preferred (KeyID 0x11DEADC3, wwwkeys.pgp.net)
"To err is human -- to blame it on a computer is even more so."
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: Digital signature
URL: <http://trubka.network.cz/pipermail/bird-users/attachments/20150110/e253d7d5/attachment.asc>