High Performance IP Lookup on FPGA with Combined Length-Infix Pipelined Search

Date

2011-05-03

Author

Yang, Yi-Hua E.
Erdem, Oguzhan
Prasanna, Viktor K.

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

218
views

0
downloads

We propose a combined length-infix pipelined search (CLIPS) architecture for high-performance IP lookup on FPGA. By performing binary search in prefix length, CLIPS can find the longest prefix match in (log L - c) phases, where L is the IP address length (32 for IPv4) and c > 0 is a small design constant (c = 2 in our prototype design). Each CLIPS phase matches one or more input infixes of the same length against a regular data structure. Various CLIPS phases can be optimized individually: (1) 16 bits of the IP address are used to direct-access a 288-kbit on-chip BRAM in phase 1; (2) 8 additional bits of the IP address are used to search a 1.5-million-entry pipelined dynamic search forest for a match in phase 2; (3) 1 to 8 additional bits of the IP address are used by a 2-stage TreeBitmap for storing another 1 to 8 million routing prefixes in the tail phase. Post place-and-route results show that our CLIPS prototype, utilizing 28 Mbits on-chip BRAM and 4 external SRAM channels, sustains 312 MPPS IPv4 lookup (or 160 Gbps routing thoughput with 64-byte packets) against 9.5 million prefixes on state-of-the-art FPGA.

Subject Keywords

Tree Bitmap, Search trie, Binary search tree, Longest prefix match, Packet forwarding, IP lookup

URI

https://hdl.handle.net/11511/66369

DOI

https://doi.org/10.1109/fccm.2011.61

Collections

Department of Electrical and Electronics Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Efficient processing of category-restricted queries for Web directories Altıngövde, İsmail Sengör; Ulusoy, Oezguer (2008-01-01) We show that a cluster-skipping inverted index (CS-IIS) is a practical and efficient file structure to support category-restricted queries for searching Web directories. The query processing strategy with CS-IIS improves CPU time efficiency without imposing any limitations on the directory size.
High-performance IP Lookup Engine with Compact Clustered Trie Search Erdem, Oguzhan; Bazlamaçcı, Cüneyt Fehmi (2012-12-01) This paper proposes a novel high throughput internet protocol (IP) lookup engine, which is built upon a recently proposed multiple pipeline array architecture that has parallel two-dimensional circular search capabilities on intersecting and variable length pipelines. Our new engine is composed of specially designed processing elements (PEs) including dual input/output static random access memory units and bidirectional links, hence allowing search to proceed in all directions and admitting search requests ...
A low-complexity precoder-decoder design in multiuser downlink MIMO communication systems for common and private information transmission Ortak ve Özel Bilginin Gönderildiǧi Çok Kullanicili ąsaǧi Baǧlantili MIMO Haberlȩsme Sistemlerinde Düsük Karmąsiklikli Bir Ön Kodlayici ve Kod Çözücü Tasarimi Deniz, Umay Ezgi; Candan, Çağatay (2018-07-05) In this paper, an alternative method is proposed instead of the ones using semi-definite programming (SDP) tools in precoder and decoder design to solve max-min fairness (MMF) problem in the multiuser downlink multi-input-multi-output (MIMO) communication systems for common and private information transmission. This is a Hybrid method which is the combination of the two solving total signal-interference plus noise ratio (SINR) maximization (Total-SINR Max) and total MMSE (Joint-TMSE) problems and it is very...
A novel fault tolerant architecture on a runtime reconfigurable FPGA Coşkuner, İbrahim Aydın; Güran, Hasan; Department of Electrical and Electronics Engineering (2006) Due to their programmable nature, Field Programmable Gate Arrays (FPGAs) offer a good test environment for reconfigurable systems. FPGAs can be reconfigured during the operation with changing demands. This feature, known as Runtime Reconfiguration (RTR), can be used to speed-up computations and reduce system cost. Moreover, it can be used in a wide range of applications such as adaptable hardware, fault tolerant architectures. This thesis is mostly concentrated on the runtime reconfigurable architectures. C...
Advanced methods for result and score caching in web search engines Yafay, Erman.; Altıngövde, İsmail Sengör; Department of Computer Engineering (2019) Search engines employ caching techniques in main memory to improve system efficiency and scalability. In this thesis, we focus on improving the cache performance for web search engines where our contributions can be separated into two main parts. Firstly, we investigate the impact of the sample size for frequency statistics for most popular cache eviction strategies in the literature, and show that cache performance improves with larger samples, i.e., by storing the frequencies of all (or, most of) the quer...

Citation Formats

Y.-H. E. Yang, O. Erdem, and V. K. Prasanna, “High Performance IP Lookup on FPGA with Combined Length-Infix Pipelined Search,” 2011, p. 77, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/66369.