Enhanced Bloom Filter-Based Longest-First Search Algorithms for Longest Prefix Matching

Efficient longest prefix matching (LPM) is a fundamental operation in networking applications such as IP lookup, where minimizing unnecessary memory accesses is critical for achieving high performance. Bloom filter (BF)-based approaches have been widely studied to reduce redundant off-chip memory accesses by filtering non-existent prefixes using compact on-chip structures. Recently, longest-first search (LFS) using a single BF has been proposed to further improve lookup efficiency. However, false positives (FPs) in the BF still incur unnecessary off-chip memory accesses, thereby limiting overall lookup performance. In this paper, we propose three enhanced BF-based LFS schemes, specifically length partition-based LFS (LP-LFS), stacked filter-based LFS (SF-LFS), and parent query-based LFS (PQ-LFS), to reduce the false positive rate (FPR) while improving on-chip memory utilization. LP-LFS, SF-LFS, and PQ-LFS reduce unnecessary accesses by lowering the FPR through BF partitioning based on query distributions, frequent FP filtering, and parent-node-based storage, respectively. Experimental results validate the theoretical FPR analysis for the proposed algorithms and demonstrate that the proposed schemes achieve lower FPRs than single-BF-LFS, reducing the FPR by up to 84.26% and the average number of unnecessary off-chip accesses per lookup by up to 91.30%, thereby improving the overall LPM performance. These results confirm the effectiveness of the proposed BF-based designs for efficient prefix lookup.