Advanced Hashing Techniques for Non-Uniformly Distributed IP Address Lookup

D. Pandya, C. Martinez, W.-M. Lin, and P. Patel (USA)


Hashing, Computer Networks, Address Lookup, Packet Matching, Internet, Intrusion Detection, Network Security


Hashing algorithms in general involve converting a key in side each target data of a database to a hash value hoping that the hashing would render the database a uniform dis tribution with respect to this new hash value. The close the final distribution is to uniform, the less search time would be required when a query is made. When the database is already key-wise uniformly distributed, any regular hash ing algorithm, such as bit-extraction, bit-group XOR, etc., would easily lead to a statistically perfect uniform distri bution after the hashing. When the target database has a key with a highly skewed distributed value, performance delivered by regular hashing algorithms usually becomes far from desirable. This paper aims at designing a rela tively fast hashing algorithm to achieve a superior hash re sult than known hashing algorithms for a non-uniformly distributed database. An pre-processing step is first per formed on the database to establish a priority order within the key for a better decision making in how the key should be used for hashing. The resulted algorithm is an ad hoc ap proach which essentially undertakes a unique hash function for any given database. This important feature allows the proposed technique to easily adapt to a changing (and/or expanding) database with an irregular non-uniform distri bution. Significant improvement from simulation results is obtained in randomly generated data as well as real IP data.

Important Links:

Go Back