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