• 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