Hash algorithm design for a non-uniformly distributed database

Computer networks have continued to make substantial advances in the past couple of decades, through better technologies and methodologies employed. As the usage of the networks continues to increase exponentially, high throughput of the networks has to be maintained with various performance-efficient network algorithms. IP address lookup is one of the processes, the performance of which dearly affects the overall network performance. Hashing has been widely used for fast IP address lookup due to its simplicity, but hashing has commonly assumed an address set with uniformly distributed key values. Performance from these known hashing techniques is far from optimal due to the high non-uniformity in actual IP address distribution. In this dissertation, we present a new methodology to deal with hashing on non-uniform distributed database. The new methodology is based on determining the "bit-wise" distribution" of database bits. With the knowledge of the bit-wise distribution hashing can be improved by being able to calculate how an XOR operator will alter the randomness of the hashing algorithm. We show how our methodology can be applied to an ad-hoc hashing algorithm or a predefined XOR folding hashing algorithm. Bit-duplication techniques are also proposed to further increase the hash randomness. An extensive analysis on correlation among hash keys is also performed to look for the best hash combinations. Simulation results show a very significant improvement in performance on randomly generated addresses and several sample IP address databases over the standard classical approaches to hashing.