High-performance IP Lookup Engine with Compact Clustered Trie Search

Date

2012-12-01

Author

Erdem, Oguzhan
Bazlamaçcı, Cüneyt Fehmi

Metadata

Show full item record

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

Item Usage Stats

192
views

0
downloads

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 from all PEs at the boundary of the array. We propose a novel data structure called compact clustered trie (CCT), which is better than traditional binary trie in terms of memory requirement and number of memory accesses. We develop novel approaches including a CCT forwarding table construction method, a mapping strategy and a suitable IP lookup algorithm. Our new lookup engine achieves a much higher average case throughput and a much lower average delay compared with existing IP lookup solutions making, for example, an 8 Tbps high-speed router front end possible. The engine is also well suited for the IPv6 addressing scheme.

Subject Keywords

Trie, Dual input/output SRAM, Pipeline, IP lookup, Terabit routers, Packet switching networks

URI

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

Journal

COMPUTER JOURNAL

DOI

https://doi.org/10.1093/comjnl/bxs008

Collections

Department of Electrical and Electronics Engineering, Article

Suggestions

OpenMETU
Core

High Performance IP Lookup on FPGA with Combined Length-Infix Pipelined Search Yang, Yi-Hua E.; Erdem, Oguzhan; Prasanna, Viktor K. (2011-05-03) 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 th...
A NOVEL FLEXIBLE ON-CHIP SWITCH ARCHITECTURE FOR RECONFIGURABLE HARDWARE ACCELERATORS Yazıcı, Fatih; Schmidt, Şenan Ece; Department of Electrical and Electronics Engineering (2021-8-13) This thesis work proposes ReFlex Switch, a novel, scalable on-chip packet switch architecture, that is designed to interconnect heterogeneous IP cores at high speeds. One target application for ReFlex switch is hardware accelerated cloud computing where the cloud servers feature FPGA cards with reconfigurable regions to implement accelerators demanded by the users. In this setting, the increasing data rates call for line-speed operation of the on-chip switch to maintain scalability. The first requirement o...
MIPS Extension for a TCAM Based Parallel Architecture for Fast IP Lookup Erdem, Oguzhan; Bazlamaçcı, Cüneyt Fehmi (2009-09-16) This paper discusses the feasibility of the use of minimum independent prefix set (MIPS) algorithm in a ternary content addressable memory (TCAM) based parallel architecture proposed for high speed packet switching. MIPS algorithm is proposed earlier to transform a forwarding table into one that contains the minimum independent prefix set. In this paper we propose MIPS algorithm to be integrated into a TCAM based parallel IP lookup engine. We first analyze the table compression performance of the MIPS algor...
Efficient User Grouping for Hybrid Beamforming in Single Carrier Wideband Massive MIMO Channels Kilcioglu, Emre; Güvensen, Gökhan Muzaffer (2021-01-01) In this paper, three types of user grouping algorithms in which our own performance metric is utilized are investigated for single carrier downlink wideband spatially correlated massive MIMO channels by using hybrid beamforming structure motivated by the joint spatial division and multiplexing (JSDM) framework. The user grouping procedure consists of two stages. Internally, our own metric called as the achievable information rate (AIR) is calculated given a user grouping input by considering both inter-grou...
Efficient Edge-Preserving Stereo Matching Cigla, Cevahir; Alatan, Abdullah Aydın (2011-11-13) A computationally efficient stereo matching algorithm is introduced providing high precision dense disparity maps via local aggregation approach. The proposed algorithm exploits a novel paradigm, namely separable successive weighted summation (SWS) among horizontal and vertical directions with constant operational complexity, providing effective connected 2D support regions based on local color similarities. The intensity adaptive aggregation enables crisp disparity maps which preserve object boundaries and...

Citation Formats

O. Erdem and C. F. Bazlamaçcı, “High-performance IP Lookup Engine with Compact Clustered Trie Search,” COMPUTER JOURNAL, pp. 1447–1466, 2012, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/56485.