EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Jaeyeong You, Hayoung Byun

Electronics · 11.08.2026 · 15 (16) · 3569

DOI: 10.3390/electronics15163569 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Electronics, online erschienen am 11.08.2026. Verfasst von Jaeyeong You und 1 weiteren Autor:innen. Die Arbeit nennt 31 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ministry of Education.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Ministry of Education

Zitieren

APA

You, J., & Byun, H. (2026). Enhanced Bloom Filter-Based Longest-First Search Algorithms for Longest Prefix Matching. Electronics, 15(16), 3569. https://doi.org/10.3390/electronics15163569

Vancouver

You J, Byun H. Enhanced Bloom Filter-Based Longest-First Search Algorithms for Longest Prefix Matching. Electronics. 2026;15(16):3569. doi:10.3390/electronics15163569

BibTeX
@article{You2026,
  author = {You, Jaeyeong and Byun, Hayoung},
  title = {Enhanced Bloom Filter-Based Longest-First Search Algorithms for Longest Prefix Matching},
  journal = {Electronics},
  year = {2026},
  volume = {15},
  number = {16},
  pages = {3569},
  doi = {10.3390/electronics15163569}
}
Kostenlos starten →