Proceedings of the Annual IEEE Symposium on High-Performance Interconnects (HOTI), Stanford, CA, August 2008.
The increasingly more stringent performance and power requirements of Internet routers call for scalable IP lookup strategies that go beyond the currently viable TCAM- and trie-based solutions. This paper describes a new hash-based IP lookup scheme that is both storage efficient and highperformance. In order to achieve high storage efficiency, we take a multi-hashing approach and employ an advanced hashing technique that effectively resolves hashing collisions by dynamically migrating IP prefixes that are already in the lookup table as new prefixes are inserted. To obtain high lookup throughput, the multiple hash tables are accessed in parallel (using different hash functions) or in a pipelined manner. We evaluate the proposed scheme using up-to-date core routing tables and discuss how its key design parameters can be determined. When compared with state-of-the-art TCAM designs, our scheme reduces area and power requirements by 60% and 80% respectively, while achieving competitive lookup rates. We expect that the proposed scheme scales well with the anticipated routing table sizes and technologies in the future.