Optimized Hash Lookup for Bloom Filter Based Packet Routing

As an efficient data structure for membership testing, the Bloom filter has found wide applications in modern day data networks, including high-speed packet routing for IPbased networks as well as future data-centric networks. In packet routing, Bloom filters are mainly used to pre-process incoming routing queries so as to minimize unnecessary lookups in the main routing table, as the latter is normally stored in slow off chip memory in the form of a hash table due to its large size. In this paper an optimized hash lookup scheme is proposed to utilize the preceding Bloom filter for better forwarding performance and usability. With the help of a ´summary vector´, internal hash calculations of the Bloom filter are reused in the operations of the routing table to get fast single-access table lookup. Compared with previous work, our scheme achieves improved space efficiency, less calculation overhead, more deterministic lookup performance, and simpler update procedures. The performance of our scheme is confirmed by simulations.