1. 19 Dec, 1998 1 commit
    • 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