Cuckoo++ hash tables: high-performance hash tables for networking applications
Cuckoo++ hash tables: high-performance hash tables for networking applications
复制标题
Cuckoo 哈希表：用于网络应用程序的高性能哈希表
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Nicolas Le Scouarnec
中科院分区：
文献类型：
--
作者：
Nicolas Le Scouarnec
哈希表是用于联网应用的基本数据结构（例如，连接跟踪、防火墙、网络地址转换器）。其中，cuckoo哈希表通过处理很少的内存访问（每次查找2到3次）来提供出色的性能。然而，它们仍然受内存限制，每次内存访问都会影响性能。在本文中，我们提出了算法改进布谷鸟哈希表，以消除不必要的内存访问，而不改变原有的布谷鸟哈希表的属性，使所有现有的理论分析仍然适用。我们还介绍了一种专为在英特尔至强处理器上高效运行而量身定制的实现，从而支持NFV和软件化趋势，并将其与DPDK的优化实现进行比较。在单个核心上，我们的实现实现了每秒37M的正查找（即，当查找的关键字存在于表中时），每秒60M次负查找，比DPDK提高了45%到70%。
Hash tables are essential data-structures for networking applications (e.g., connection tracking, firewalls, network address translators). Among these, cuckoo hash tables provide excellent performance by processing lookups with very few memory accesses (2 to 3 per lookup). Yet, they remain memory bound and each memory access impacts performance. In this paper, we propose algorithmic improvements to cuckoo hash tables to eliminate unnecessary memory accesses, without altering the properties of the original cuckoo hash table so that all existing theoretical analysis remain applicable. We also present an implementation tailored to run efficiently on Intel Xeon processors, thus supporting NFV and softwarization trends and compare it to the optimized implementation of DPDK. On a single core, our implementation achieves 37M positive lookups per second (i.e., when the key looked up is present in the table), and 60M negative lookups per second, a 45% to 70% improvement over DPDK.
DOI：
--
发表时间：
2018-04
期刊：
--
影响因子：
--
作者：
S. Woo;Justine Sherry;Sangjin Han;S. Moon;Sylvia Ratnasamy;S. Shenker
通讯作者：
S. Woo;Justine Sherry;Sangjin Han;S. Moon;Sylvia Ratnasamy;S. Shenker