FPGA Europe Conference Presentation

A Cuckoo Hash-Based CAM Architecture for FPGA and ASIC Implementations

This presentation introduces a Content-Addressable Memory (CAM) architecture which is based on Cuckoo hash-based algorithm and is tailored for FPGA and ASIC implementations. The proposed architecture is a constituent part for many network applications, such as high-speed IP filtering and flow classification. The architecture of the proposed Cuckoo hash-based architecture is demonstrated, and FPGA implementation details are presented. Furthermore, the employment of the proposed CAM architectures in the context of TCPIP network stacks is also discussed. Efficient CAM designs are of particular research and practical interest for several reasons. CAMs are a fundamental part of hardware network stacks, and they serve various objectives. Furthermore, they usually lie in the maximum-delay critical path of hardware implementations, reserve a considerable area budget, and contribute substantially to power dissipation. CAM operations closely resemble those in hash tables. Hash tables are commonly employed for retrieving a value that is associated with a related key, forming a key-value pair. The key is used as an index to locate the relevant value. The challenge in this process lies to the fact that multiple keys may lead to the same memory position, leading to collisions during the saving process. If the first memory position is occupied by another pair, the subsequent position is examined until an empty position is found. The second position is determined by a hash that is generated by a different hash function. The alternative position may lie in the same or another memory block. In the general case, a memory position can include multiple slots. In this context, there is a trade-off between the complexity of save operations vs. the complexity of the search/erase operations. Hash-based schemes reduce the latency of search and erase operations at a corresponding cost of save operations. Most of the proposed hash-based designs employ two or multiple hash functions that generate the memory addresses to be checked for potential empty slots. To reduce latency and area, hash values are produced by non-cryptographic hash functions. Typical implementations include the Murmur, Jenkin, or XOR-based hash functions.