Exploiting Degrees of Freedom for Efficient Hashing in Network Applications

Abstract

Hashing has yet to be widely accepted as a component of hard real-time systems and hardware implementations, due to still ex- isting prejudices concerning the unpredictability of space and time re- quirements resulting from collisions. While in theory perfect hashing can provide optimal mapping, in practice, finding a perfect hash function is too expensive, especially in the context of high-speed applications.The introduction of hashing with multiple choices, d-left hashing and Bloom filter-based hash table summaries, has caused a shift towards guaranteed single-DRAM access. However, these guarantees come at a high price. High amounts of rare and expensive high-speed SRAM needs to be traded off for predictability. Moreover, it is infeasible for many applications to provide enough on-chip memory.In this paper we show that previous suggestions suffer from the false pre- condition of full generality. To provide a workable solution, our approach exploits four individual degrees of freedom available in many practical applications, especially hardware and high-speed lookups. This reduces the requirement of on-chip memory up to an order of magnitude at the cost of only minute amounts of additional hardware. Our design makes fast hash table implementations cheaper, more predictable and above all, more practical.