ABSTRACT
In this chapter, the author introduces the up-to-date hashing algorithms for the Longest Prefix Matching. A hashing table is constructed based on each small table. If the maximum length of the prefix is L, there are L hashing tables. Hashing function is selected based on its hardware simplicity because the proposed scheme requires separate hashings in each prefix. The author describes the concept of multiple hash functions and multiple hashing schemes. An important issue in using hashing for an internet protocol (IP) address lookup is how to minimize the collisions. Border and Michael Mitzenmacher proposed multiple hashing to solve the collision problem and discussed the applicability of multiple hashing to IP routing. Hashing is implemented with cyclic redundancy code (CRC) checker, which is known as a semi-perfect hash function. Multiple hash indices for each prefix length are extracted from a single CRC hardware. Searches in each table are executed in parallel using the hash indices obtained from CRC hash function.
