1. 27 Jul, 2013 1 commit
2. 29 Apr, 2013 1 commit
3. 16 Nov, 2012 1 commit
4. 07 Aug, 2012 1 commit
5. 22 Mar, 2012 1 commit
6. 20 Jan, 2012 1 commit
7. 10 Oct, 2011 1 commit
8. 04 Sep, 2011 1 commit
9. 08 Jul, 2011 1 commit
10. 02 May, 2011 1 commit
11. 30 Mar, 2011 1 commit
12. 31 May, 2010 1 commit
13. 09 Apr, 2010 1 commit
14. 10 Feb, 2010 1 commit
15. 06 Jan, 2010 1 commit
16. 19 Dec, 2009 1 commit
17. 19 Nov, 2009 1 commit
18. 02 Nov, 2009 1 commit
19. 28 Oct, 2009 1 commit
20. 30 Sep, 2009 1 commit
21. 12 Aug, 2009 1 commit
22. 25 Jun, 2009 1 commit
23. 22 May, 2009 1 commit
24. 07 Jun, 2004 1 commit
25. 06 Jun, 2004 1 commit
26. 09 Jun, 2001 1 commit
27. 09 Sep, 2000 1 commit
28. 04 Sep, 2000 1 commit
29. 03 Sep, 2000 1 commit
30. 25 Aug, 2000 1 commit
31. 24 Aug, 2000 1 commit
32. 19 Dec, 1998 2 commits
• Variance estimation fixed. · 29ad2c9e
Martin Mareš authored
• Added several tools for fib hashing function analysis. It turned out · 87b60bf7
Martin Mareš authored
```we can use very simple function which is monotonic with respect
to re-hashing:

n ^= n >> 16;
n ^= n << 10;
h = (n >> (16 - o)) & ((1 << o) - 1);

where o is table order. Statistical analysis for both backbone routing
table and local OSPF routing tables gives values near theoretical
optimum for uniform distribution (see ips.c for formulae).

The trick is very simple: We always calculate a 16-bit hash value n and
use o most significant bits (this gives us monotonity wrt. rehashing
if we sort the chains by the value of n). The first shift/xor pair
reduces the IP address to a 16-bit one, the second pair makes higher
bits of the 16-bit value uniformly distributed even for tables containing
lots of long prefixes (typical interior routing case with 24-bit or even
longer prefixes).```