Hash tables are an essential data-structure for numerous networking applications (e.g., connection tracking, firewalls, network address translators). Among these, cuckoo hash tables provide excellent performance by allowing lookups to be processed with very few memory accesses (2 to 3 per lookup). Yet, for large tables, cuckoo hash tables remain memory bound and each memory access impacts performance. In this paper, we propose algorithmic improvements to cuckoo hash tables allowing to eliminate some unnecessary memory accesses; these changes are conducted without altering the properties of the original cuckoo hash table so that all existing theoretical analysis remain applicable. On a single core, our hash table achieves 37M lookups per second for positive lookups (i.e., when the key looked up is present in the table), and 60M lookups per second for negative lookups, a 50 improvement over the implementation included into the DPDK. On a 18-core, with mostly positive lookups, our implementation achieves 496M lookups per second, a 45 improvement over DPDK.
An alternative solution to store association between connections and state is perfect hashing, as used in ScaleBricks @cite_25 . Perfect hashing allows a compact memory representation and very efficient lookups. The downsides are that it does not answers negatively to lookups but gives a random value, and that insert are more costly. In the context of high-performance packet processing, ScaleBricks @cite_25 achieves 520M lookups per second on 16 cores. Thus, Cuckoo++, at 460M lookups per second on 16 cores, provides an interesting, more flexible, alternative to ScaleBricks whenever the insertion update rate is higher, or when perfect hashing does not satisfy the requirements of the application (e.g., firewall NAT must identify non-existing connection, and require to frequently create new associations).
@cite_25
1966127114
This paper presents ScaleBricks, a new design for building scalable, clustered network appliances that must "pin" flow state to a specific handling node without being able to choose which node that should be. ScaleBricks applies a new, compact lookup structure to route packets directly to the appropriate handling node, without incurring the cost of multiple hops across the internal interconnect. Its lookup structure is many times smaller than the alternative approach of fully replicating a forwarding table onto all nodes. As a result, ScaleBricks is able to improve throughput and latency while simultaneously increasing the total number of flows that can be handled by such a cluster. This architecture is effective in practice: Used to optimize packet forwarding in an existing commercial LTE-to-Internet gateway, it increases the throughput of a four-node cluster by 23 , reduces latency by up to 10 , saves memory, and stores up to 5.7x more entries in the forwarding table.