1. 25 Nov, 2013 1 commit
  2. 23 Nov, 2013 1 commit
  3. 27 Jul, 2013 1 commit
  4. 29 Apr, 2013 1 commit
  5. 16 Nov, 2012 1 commit
  6. 07 Aug, 2012 1 commit
  7. 22 Mar, 2012 1 commit
  8. 20 Jan, 2012 1 commit
  9. 10 Oct, 2011 1 commit
  10. 04 Sep, 2011 1 commit
  11. 08 Jul, 2011 1 commit
  12. 02 May, 2011 1 commit
  13. 30 Mar, 2011 1 commit
  14. 31 May, 2010 1 commit
  15. 09 Apr, 2010 1 commit
  16. 10 Feb, 2010 1 commit
  17. 06 Jan, 2010 1 commit
  18. 19 Dec, 2009 1 commit
  19. 19 Nov, 2009 1 commit
  20. 02 Nov, 2009 1 commit
  21. 28 Oct, 2009 1 commit
  22. 30 Sep, 2009 1 commit
  23. 12 Aug, 2009 1 commit
  24. 25 Jun, 2009 1 commit
  25. 22 May, 2009 1 commit
  26. 07 Jun, 2004 1 commit
  27. 06 Jun, 2004 1 commit
  28. 09 Jun, 2001 1 commit
  29. 09 Sep, 2000 1 commit
  30. 04 Sep, 2000 1 commit
  31. 03 Sep, 2000 1 commit
  32. 25 Aug, 2000 1 commit
  33. 24 Aug, 2000 1 commit
  34. 19 Dec, 1998 2 commits
    • Martin Mareš's avatar
      Variance estimation fixed. · 29ad2c9e
      Martin Mareš authored
      29ad2c9e
    • Martin Mareš's avatar
      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).
      87b60bf7