Advanced hashing schemes for packet forwarding using set associative memory architectures

摘要

Building a high performance IP packet forwarding (PF) engine remains a challenge due to increasingly stringent throughput requirements and the growing size of IP forwarding tables. The router has to match the incoming packet's IP address against all entries in the forwarding table. The matching process has to be done at increasingly higher wire speed; hence, scalability and low power consumption are critical for PF engines. Various hash table based schemes have been considered for use in PF engines. Set associative memory can be used for hardware implementations of hash tables with the property that each bucket of a hash table can be searched in a single memory cycle. However, the classic hashing downsides, such as collisions and worst case memory access time have to be dealt with. While open addressing hash tables, in general, provide good average case search performance, their memory utilization and worst case performance can degrade quickly due to collisions (that lead to bucket overflows). The two standard solutions to the overflow problem are either to use predefined probing (e.g., linear or quadratic probing) or to use multiple hash functions. This work presents two new simple hash schemes that extend both aforementioned solutions to tackle the overflow problem efficiently. The first scheme is a hash probing scheme that is called Content-based HAsh Probing (CHAP). As the name suggests, CHAP, based on the content of the hash table, avoids the classical side effects of predefined hash probing methods (i.e., primary and secondary clustering phenomena) and at the same time reduces the overflow. The second scheme, called Progressive Hashing (PH), is a general multiple hash scheme that reduces the overflow as well. The basic idea of PH is to split the prefixes into groups where each group is assigned one hash function, then reuse some hash functions in a progressive fashion to reduce the overflow. Both schemes are amenable to high-performance hardware implementations with low overflow and constant worst-case memory access time. We show by experimenting with real IP lookup tables and synthetic traces that both schemes outperform other existing hashing schemes.