Article

A Tree Based Router Search Engine Architecture with Single Port Memories

Authors:

Florin Baboescu,

Dean M. Tullsen,

Sumeet SinghAuthors Info & Claims

ISCA '05: Proceedings of the 32nd annual international symposium on Computer Architecture

Pages 123 - 133

https://doi.org/10.1109/ISCA.2005.7

Published: 01 May 2005 Publication History

Abstract

Pipelined forwarding engines are used in core routers to meet speed demands. Tree-based searches are pipelined across a number of stages to achieve high throughput, but this results in unevenly distributed memory. To address this imbalance, conventional approaches use either complex dynamic memory allocation schemes or over-provision each of the pipeline stages. This paper describes the microarchitecture of a novel network search processor which provides both high execution throughput and balanced memory distribution by dividing the tree into subtrees and allocating each subtree separately, allowing searches to begin at any pipeline stage. The architecture is validated by implementing and simulating state of the art solutions for IPv4 lookup, VPN forwarding and packet classification. The new pipeline scheme and memory allocator can provide searches with a memory allocation efficiency that is within 1% of non-pipelined schemes.

References

[1]

{1} Network processor forum. http://www.npforum.org.

[2]

{2} Network processor forum benchmark working group. http://www.npforum.org/benchmarking/index.shtml.

[3]

{3} C. Amerijckx and J. Legat. A low-power multiprocessor architecture for embedded reconfigurable systems.

[4]

{4} F. Baboescu, S. Rajgopal, N. Richardson, and L.-B. Huang. A scalable ip lookup low-power implementation for oc-768 links. Workshop for Application Specific Processors(WASP), 2004.

[5]

{5} F. Baboescu and G. Varghese. Scalable packet classification. In Proc of ACM Sigcomm 2001, september 2001.

Digital Library

[6]

{6} J.-L. Baer, D. Low, P. Crowley, and N. Sidhwaney. Memory hierarchy design for a multiprocessor look-up engine. In IEEE PACT, 2003.

Digital Library

[7]

{7} L. A. Barroso and M. Dubois. The Performance of Cache-Coherent Ring-based Multiprocessors. In 20th Annual International Symposium on Computer Architecture, pages 268-277, May 1993.

Digital Library

[8]

{8} A. Basu and G. Narlikar. Fast incremental updates for pipelined forwarding engines. In Proc. of Infocom, march 2003.

[9]

{9} E. Coffman, L. Flatto, E. N. Gilbert, and A. G. Greenberg. An approximate model of processor communication rings under heavy load. Information Processing Letters, 64(2):61-67, 1997.

Digital Library

[10]

{10} E. Coffman, N. Kahale, and F. T. Leighton. Processor-ring communication: A tight asymptotic bound on packet waiting times. 1996.

[11]

{11} W. Eatherton. Hardware-based internet protocol prefix lookups. In Eatherton, Will. Hardware-Based Internet Protocol Prefix Lookups. Washington University Electrical Engineering Department, MS thesis, may 1999.

[12]

{12} M. R. Garey and D. S. Johnson. Computers and intractability - a guide to the theory of np-completeness. pages 213-224. W.H. Freeman and Company, New York, 1979.

Digital Library

[13]

{13} P. Gupta. Algorithmic search solutions: Features and benefits. In NPC-West 2003, october 2003.

[14]

{14} P. Gupta and N. McKeown. Packet classification on multiple fields. In Proc of ACM Sigcomm 1999, september 1999.

Digital Library

[15]

{15} P. Gupta and N. McKeown. Packet classification using hierarchical intelligent cuttings. In Proc of Hot Interconnects VII, august 1999.

[16]

{16} D. Mayer. University of oregon route views project. 2003. ftp://ftp.routeviews.org/pub/routeviews.

[17]

{17} U. Michigan. Multi-threaded routing toolkit. 2003. http://www.mrtd.net/.

[18]

{18} H. Narayan, R. Govindan, and G. Varghese. The impact of address allocation and routing on the structure and implementation of routing tables. In Proc. of ACM Sigcomm 2003, august 2003.

Digital Library

[19]

{19} Ravindran and Stumm. A performance comparison of hierarchical ring- and mesh-connected multiprocessor networks. In 3rd International Symposium on High-Performance Computer Architecture. IEEE Computer Society, 1997.

Digital Library

[20]

{20} E. Rosen and Y. Rekhter. BGP/MPLS VPNs. RFC 2547, 1999.

[21]

{21} RRC. Routing information service raw data. 2003. http://data.ris.ripe.net/.

[22]

{22} M. Sanchez, E. Biersack, and W. Dabbous. Survey and taxonomy of ip address lookup algorithms. In IEEE Network Magazine, vol. 15, no. 2, 2001.

Digital Library

[23]

{23} T. Sherwood, G. Varghese, and B. Calder. A pipelined memory architecture for high throughput network processors. 2003. 30th Annual International Symposium on Computer Architecture.

Digital Library

[24]

{24} P. Shivakumar and N. Jouppi. Cacti. http://research.compaq.com/wrl/people/jouppi/CACTI.html.

[25]

{25} S. Sikka and G. Varghese. Memory-efficient state lookups with fast updates. In Proc of ACM Sigcomm 2000, september 2000.

Digital Library

[26]

{26} S. Singh, F. Baboescu, G. Varghese, and J. Wang. Packet classification using multidimensional cutting. In Proc. of ACM Sigcomm 2003, august 2003.

Digital Library

[27]

{27} V. Srinivasan and al. Fast and scalable layer 4 switching. In Proc of ACM Sigcomm 1998, september 1998.

Digital Library

[28]

{28} T. Woo. A modular approach to packet classification: Algorithms and results. In Proc. of Infocom, 2000.

Cited By

Yang TXie GLi YFu QLiu ALi QMathy L(2014)Guarantee IP lookup performance with FIB explosionACM SIGCOMM Computer Communication Review10.1145/2740070.262629744:4(39-50)Online publication date: 17-Aug-2014
https://dl.acm.org/doi/10.1145/2740070.2626297
Yang TXie GLi YFu QLiu ALi QMathy LBustamante FHu YKrishnamurthy ARatnasamy S(2014)Guarantee IP lookup performance with FIB explosionProceedings of the 2014 ACM conference on SIGCOMM10.1145/2619239.2626297(39-50)Online publication date: 17-Aug-2014
https://dl.acm.org/doi/10.1145/2619239.2626297
Erdem OCarus ALe H(2014)Large-scale SRAM-based IP lookup architectures using compact trie search structuresComputers and Electrical Engineering10.1016/j.compeleceng.2013.10.01140:4(1186-1198)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1016/j.compeleceng.2013.10.011
Show More Cited By

Recommendations

A Tree Based Router Search Engine Architecture with Single Port Memories
ISCA 2005

Pipelined forwarding engines are used in core routers to meet speed demands. Tree-based searches are pipelined across a number of stages to achieve high throughput, but this results in unevenly distributed memory. To address this imbalance, conventional ...
Tree Search in Major/Minor Loop Magnetic Bubble Memories

In this paper we analyze various search schemes in a major/minor loop bubble memory. Specifically, we study balanced tree search, one-sided height-balanced tree search, and one-sided K-Keight-balanced tree search. Two parameters are of interest in the ...
Consequences of port restrictions on testing two-port memories
ITC '98: Proceedings of the 1998 IEEE International Test Conference

Testing two-port memories requires the useof single-port tests as well as special two-port tests; thetest strategy determines which tests to be used. Manytwo-port memories have ports which are read-only orwrite-only; this impacts the possible fault ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISCA '05: Proceedings of the 32nd annual international symposium on Computer Architecture

June 2005

541 pages

ISBN:076952270X

ACM SIGARCH Computer Architecture News Volume 33, Issue 2
ISCA 2005
May 2005
531 pages
ISSN:0163-5964
DOI:10.1145/1080695
Issue’s Table of Contents

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 May 2005

Check for updates

Qualifiers

Article

Conference

ISCA05

Sponsor:

SIGARCH

ISCA05: The 32nd Annual International Symposium on Computer Architecture 2005

June 4 - 8, 2005

Acceptance Rates

ISCA '05 Paper Acceptance Rate 45 of 194 submissions, 23%;

Overall Acceptance Rate 543 of 3,203 submissions, 17%

Upcoming Conference

ISCA '25

Sponsor:
sigarch

The 52nd Annual International Symposium on Computer Architecture

June 21 - 25, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
23
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang TXie GLi YFu QLiu ALi QMathy L(2014)Guarantee IP lookup performance with FIB explosionACM SIGCOMM Computer Communication Review10.1145/2740070.262629744:4(39-50)Online publication date: 17-Aug-2014
https://dl.acm.org/doi/10.1145/2740070.2626297
Yang TXie GLi YFu QLiu ALi QMathy LBustamante FHu YKrishnamurthy ARatnasamy S(2014)Guarantee IP lookup performance with FIB explosionProceedings of the 2014 ACM conference on SIGCOMM10.1145/2619239.2626297(39-50)Online publication date: 17-Aug-2014
https://dl.acm.org/doi/10.1145/2619239.2626297
Erdem OCarus ALe H(2014)Large-scale SRAM-based IP lookup architectures using compact trie search structuresComputers and Electrical Engineering10.1016/j.compeleceng.2013.10.01140:4(1186-1198)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1016/j.compeleceng.2013.10.011
Kim SDe Carli LSankaralingam KEstan CNajjar WYavatkar RRixner S(2013)SWSLProceedings of the ninth ACM/IEEE symposium on Architectures for networking and communications systems10.5555/2537857.2537890(191-202)Online publication date: 21-Oct-2013
https://dl.acm.org/doi/10.5555/2537857.2537890
Nakahara HSasao TMatsuura M(2013)An architecture for IPv6 lookup using parallel index generation unitsProceedings of the 9th international conference on Reconfigurable Computing: architectures, tools, and applications10.1007/978-3-642-36812-7_6(59-71)Online publication date: 25-Mar-2013
https://dl.acm.org/doi/10.1007/978-3-642-36812-7_6
Harris EWasmundt SDe Carli LSankaralingam KEstan CWolf TMoore APrasanna V(2012)LEAPProceedings of the eighth ACM/IEEE symposium on Architectures for networking and communications systems10.1145/2396556.2396595(175-186)Online publication date: 29-Oct-2012
https://dl.acm.org/doi/10.1145/2396556.2396595
Yang YErdem OPrasanna VCompton KHutchings B(2012)Scalable architecture for 135 GBPS IPv6 lookup on FPGA (abstract only)Proceedings of the ACM/SIGDA international symposium on Field Programmable Gate Arrays10.1145/2145694.2145762(272-272)Online publication date: 22-Feb-2012
https://dl.acm.org/doi/10.1145/2145694.2145762
Kumar ADe Carli LKim Sde Kruijf MSankaralingam KEstan CJha SSalapura VGschwind MKnoop J(2010)Design and implementation of the PLUG architecture for programmable and efficient network lookupsProceedings of the 19th international conference on Parallel architectures and compilation techniques10.1145/1854273.1854316(331-342)Online publication date: 11-Sep-2010
https://dl.acm.org/doi/10.1145/1854273.1854316
Jiang WPrasanna V(2009)Energy-efficient multi-pipeline architecture for terabit packet classificationProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811982.1812421(6270-6275)Online publication date: 30-Nov-2009
https://dl.acm.org/doi/10.5555/1811982.1812421
Sourdis IStefanakis Gde Smet RGaydadjiev GOnufryk PRamakrishnan KCrowley PWroclawski J(2009)Range Tries for scalable address lookupProceedings of the 5th ACM/IEEE Symposium on Architectures for Networking and Communications Systems10.1145/1882486.1882520(143-152)Online publication date: 19-Oct-2009
https://dl.acm.org/doi/10.1145/1882486.1882520
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents