Show/Hide Menu
Hide/Show Apps
anonymousUser
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Videos
Videos
Thesis submission
Thesis submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Contact us
Contact us
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
9
views
0
downloads
Cite This
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
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
O. Erdem and C. F. Bazlamaçcı, “High-performance IP Lookup Engine with Compact Clustered Trie Search,”
COMPUTER JOURNAL
, vol. 55, no. 12, pp. 1447–1466, 2012, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/56485.