Hashing for Fast IP Address Lookup Utilizing Inter-key Correlation

Hashing algorithms long have been widely adopted to design a fast IP address look-up process which involves a search through a large database to find a record associated with a given key. When the target database has a highly skewed distribution as demonstrated by most of the real-time IP databases, performance delivered by regular hashing algorithms, such as the bit-extraction, bit-wise XOR, etc., usually becomes far from desirable. This research aims at designing a very simple bit-extraction hashing algorithm by exploiting the correlation among non-uniformly distributed key-bits in the database in order to minimize the search time. Application scope of the proposed methodology reaches beyond typical database systems. General computer network routing, high-speed Hardware-based Intrusion Detection Systems (HIDS) are among significant others that could benefit from this result. Pattern matching, identification recognition and all sorts of queries for general database systems would also see their required processing time drastically curtailed.