A Bloom Filter Bank Based Hash Table for High Speed Packet Processing

摘要

The use of hash tables in high speed packet processing applications is widely adopted and many different variants of such structures have been proposed in the literature. Nonetheless, the extremely variegated scenarios of application call for new specialized solutions, to best satisfy their possibly peculiar requirements. In this paper, we propose a randomized approach to the design of compact hash tables for network applications that need to frequently store and access short valued data. The approach is based on the use of a bank of Bloom filters and proves to be very effective both in terms of space occupancy and complexity, at the obvious cost of a non zero error probability.