Longest-First Search Using Bloom Filter: Algorithm and FPGA Implementation

Due to the surge in Internet traffic and the rapid increase in forwarding table entries, achieving wire-speed packet forwarding in Internet routers demands both algorithmic enhancements and hardware innovations. In this paper, we propose the longest-first search algorithm with a Bloom filter that stores prefixes in a leaf-pushing trie. Our approach utilizes an on-chip Bloom filter to indicate the presence of prefixes within the trie, while an off-chip hash table stores the corresponding output port information for each prefix. For each incoming IP address, the Bloom filter query begins from the longest length, reducing the queried number of bits by one for each negative result. The off-chip hash table is only accessed when the query to the Bloom filter produces a positive result. Therefore, access to the slower off-chip memory is minimized to once, given a reasonable Bloom filter size. The proposed approach is simulated using C++ and constructed with Verilog for field programmable gate array (FPGA) implementation. The experimental results indicate that the proposed approach achieves the throughput of 0.8 million packets per second at a clock frequency of 100MHz.