Fast hash table lookup using extended bloom filter: an aid to network processing

By Haoyu Song, Sarang Dharmapurikar, Jonathan S. Turner, John W. Lockwood. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2005

416 citations recorded by the source corpus.

Hash tables are fundamental components of several network processing algorithms and applications, including route lookup, packet classification, per-flow state management and network monitoring. These applications, which typically occur in the data-path of high-speed routers, must process and forward packets with little or no buffer, making it important to maintain wire-speed throughout. A poorly designed hash table can critically affect the worst-case throughput of an application, since the number of memory accesses required for each lookup can vary. Hence, high throughput applications require hash tables with more predictable worst-case lookup performance. While published papers often assume that hash table lookups take constant time, there is significant variation in the number of items that must be accessed in a typical hash table search, leading to search times that vary by a factor of four or more.We present a novel hash table data structure and lookup algorithm which improves the performance over a naive hash table by reducing the number of memory accesses needed for the most time-consuming lookups. This allows designers to achieve higher lookup performance for a given memory bandwidth, without requiring large amounts of buffering in front of the lookup engine. Our algorithm extends the multiple-hashing Bloom Filter data structure to support exact matches and exploits recent advances in embedded memory technology. Through a combination of analysis and simulations we show that our algorithm is significantly faster than a naive hash table using the same amount of memory, hence it can support better throughput for router applications that use hash tables.

View Paper: https://www.semanticscholar.org/paper/6bc97c31f94ad51bac505541df50497ff9e7f539

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Accelerometer: Understanding Acceleration Opportunities for Data Center Overheads at Hyperscale (2020, background): “We conclude many microservices can beneft from optimizing vector operations [72], string computations [49, 107], and hash table look-ups [108, 118].”
Invertible bloom lookup tables (2011, result): “[35] store elements in a Bloom-like hash table in a fashion that is somewhat similar to that of a cuckoo hash table [15, 26, 29].”
FlowRadar: A Better NetFlow for Data Centers (2016, background): “There are many hash-based data structures that can keep per-flow state with small memory [15, 42, 36, 43].”
Cuckoo Filter: Practically Better Than Bloom (2014, methodology): “Counting Bloom filters [12] have been suggested for multiple applications [24, 25, 9], but they generally use 3–4× space to retain the same false positive rate as a space-optimized Bloom filter.”