Hashing for Fast IP Address Lookup Utilizing Inter-key Correlation

Date
2013
Authors
Sahba, Ramin
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

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.

Description
This item is available only to currently enrolled UTSA students, faculty or staff.
Keywords
Hashing Algorithm, IP Address Lookup, Non-uniform Distribution
Citation
Department
Electrical and Computer Engineering