## Revision 87b60bf7

ID | 87b60bf7e8ad12b3efd3d6f37df0d029f50d2d91 |

Parent | 02933ddb |

Child | 29ad2c9e |

Added several tools for fib hashing function analysis. It turned out

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).

### Files

- added
- modified
- copied
- renamed
- deleted