Vectored-Bloom Filter for IP Address Lookup: Algorithm and Hardware Architectures
Source abstract
Abstract
The Internet Protocol (IP) address lookup is one of the most challenging tasks for Internet routers, since it requires to perform packet forwarding at wire-speed for tens of millions of incomming packets per second. Efficient IP address lookup algorithms have been widely studied to satisfy this requirement. Among them, Bloom filter-based approach is attractive in providing high performance. This paper proposes a high-speed and flexible architecture based on a vectored-Bloom filter (VBF), which is a space-efficient data structure that can be stored in a fast on-chip memory. An off-chip hash table is infrequently accessed, only when the VBF fails to provide address lookup results. The proposed architecture has been evaluated through both a behavior simulation with C language and a timing simulation with Verilog. The hardware implementation result shows that the proposed architecture can achieve the throughput of 5 million packets per second in a field programmable gate array (FPGA) operated at 100 MHz.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Network Packet Processing and Optimization · Network Security and Intrusion Detection · Caching and Content Delivery
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Electronic and Electrical Engineering, Ewha Womans University, Seoul 03760, Korea
Funding
National Research Foundation of Korea
References (33)
Show source-provided references
1. Next Generation Routers10.1109/JPROC.2002.802001 ↗
2. Survey and Proposal on Binary Search Algorithms for Longest Prefix Match
3. Yang, T., Xie, G., Li, Y., Fu, Q., Liu, A., Li, Q., and Mathy, L. (2014, January 17–22). Guarantee IP Lookup Performance with FIB Explosion. Proceedings of the ACM SIGCOMM, Chicago, IL, USA.10.1145/2619239.2626297 ↗
4. Vagionas, C., Maniotis, P., Pitris, S., Miliou, A., and Pleros, N. (2017). Integrated Optical Content Addressable Memories (CAM) and Optical Random Access Memories (RAM) for Ultra-Fast Address Look-Up Operations. Appl. Sci., 7.10.3390/app7070700 ↗
5. Gupta, P., Lin, S., and Mckeown, N. (April, January 29). Routing Lookups in Hardware at Memory Access Speed. Proceedings of the IEEE INFOCOM ’98, the Conference on Computer Communications. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Gateway to the 21st Century, San Francisco, CA, USA.
6. Longest Prefix Matching Using Bloom Filters10.1109/TNET.2006.872576 ↗
7. On Adding Bloom Filters to Longest Prefix Matching Algorithms10.1109/TC.2012.193 ↗
8. On-Chip vs. Off-Chip Memory: The Data Partitioning Problem in Embedded Processor-Based Systems10.1145/348019.348570 ↗
9. Sequence-preserving parallel IP lookup using multiple SRAM-based pipelines10.1016/j.jpdc.2009.04.001 ↗
10. Array Design for Trie-based IP Lookup10.1109/LCOMM.2010.08.100398 ↗
11. Pérez, K., Yang, X., Scott-Hayward, S., and Sezer, S. (2014, January 10–14). Optimized packet classification for Software-Defined Networking. Proceedings of the 2014 IEEE International Conference on Communications (ICC), Sydney, Australia.10.1109/ICC.2014.6883427 ↗
12. Song, H., and Lockwood, J. (2005, January 20–22). Efficient packet classification for network intrusion detection using FPGA. Proceedings of the 2005 ACM/SIGDA 13th International Symposium on Field-Programmable Gate Arrays, Monterey, CA, USA.10.1145/1046192.1046223 ↗
13. Sanny, A., Ganegedara, T., and Prasanna, V.K. (2013, January 20–24). A Comparison of Ruleset Feature Independent Packet Classification Engines on FPGA. Proceedings of the IEEE International Symposium on Parallel and Distributed Processing, Workshops and PhD Forum (IPDPSW), Cambridge, MA, USA.10.1109/IPDPSW.2013.249 ↗
14. Towards an Energy-Efficient Anomaly-Based Intrusion Detection Engine for Embedded Systems10.1109/TC.2016.2560839 ↗
15. Gidansky, J., Stefan, D., and Dalal, I. (2009, January 5–8). FPGA-based SoC for real-time network intrusion detection using counting Bloom filters. Proceedings of the IEEE Southeastcon, Atlanta, GA, USA.
16. Hieu, T., Thinh, T., Vu, T., and Tomiyama, S. (December, January 30). Optimization of Regular Expression Processing Circuits for NIDS on FPGA. Proceedings of the Second International Conference on Networking and Computing, Osaka, Japan.
17. Space/time tradeoffs in in hash coding with allowable errors10.1145/362686.362692 ↗
18. Waldvogel, M., Varghese, G., Turner, J., and Plattner, B. (1997, January 14–18). Scalable High Speed IP Routing Lookups. Proceedings of the ACM SIGCOMM ’97 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Cannes, France.10.1145/263105.263136 ↗
19. Binary Search on Prefix Lengths for IP Address Lookup10.1109/LCOMM.2006.1638626 ↗
20. New Approach for Efficient IP Address Lookup Using a Bloom Filter in Trie-Based Algorithms10.1109/TC.2015.2444850 ↗
21. Byun, H., and Lim, H. (2019). A New Bloom Filter Architecture for FIB Lookup in Named Data Networking. Appl. Sci., 9.10.3390/app9020329 ↗
22. Moralis-Pegios, M., Terzenidis, N., Mourgias-Alexandris, G., and Vyrsokinos, K. (2018). Silicon Photonics towards Disaggregation of Resources in Data Centers. Appl. Sci., 8.10.3390/app8010083 ↗
23. Realizing a Sub-Linear Time String-Matching Algorithm With a Hardware Accelerator Using Bloom Filters10.1109/TVLSI.2008.2012011 ↗
24. A High-Performance Double-Layer Counting Bloom Filter for Multicore Systems10.1109/TVLSI.2014.2370761 ↗
25. A Synergetic Use of Bloom Filters for Error Detection and Correction10.1109/TVLSI.2014.2311234 ↗
26. Reconfigurable Accelerator for the Word-Matching Stage of BLASTN10.1109/TVLSI.2012.2196060 ↗
27. Theory and practice of Bloom filters for distributed systems10.1109/SURV.2011.031611.00024 ↗
28. Lu, J., Yang, T., Wang, Y., Dai, H., Jin, L., Song, H., and Liu, B. (2015, January 15–16). One-Hashing Bloom Filter. Proceedings of the IEEE 23rd International Symposium on Quality of Service (IWQoS), Portland, OR, USA.10.1109/IWQoS.2015.7404748 ↗
29. Qiao, Y., Li, T., and Chen, S. (2011, January 10–15). One Memory Access Bloom Filters and Their Generalization. Proceedings of the IEEE INFOCOM, Shanghai, China.10.1109/INFCOM.2011.5934972 ↗
30. Constant IP Lookup With FIB Explosion10.1109/TNET.2018.2853575 ↗
31. IP Address Lookup Algorithm Using a Vectored Bloom Filter10.5370/KIEE.2016.65.12.2061 ↗
32. Byun, H., Li, Q., and Lim, H. (2019, January 22–25). Vectored-Bloom Filter Implemented on FPGA for IP Address Lookup. Proceedings of the ICEIC 2019, Auckland, New Zealand.10.23919/ELINFOCOM.2019.8706399 ↗
33. (2019, October 29). Prefix Names. Available online: http://www.potaroo.net.