Lookup with CAM Aided Hash Table

Hashing is popularly adopted when it comes to a large scale of IP flows. This paper mainly focused on the lookup performance of content addressable memory aided hash table (CAHT). High throughout is available with minimized average memory access number. By rational approximation, the paper provided the lower bound on average memory access number over CAHT. When the hash is perfect hash or nearly to the perfect hash, the lower bound is achieved. Through the analysis of some typical CAHT, the lower bound is validated. Further, simulation is coincidental to the theory model. With this lower bound and the overflow fraction of CAHT, we can evaluate the throughput and the capability of CAM, so chose the proper hashing scheme in the actual applications.