A tree based router search engine architecture with single port memories

Florin Baboescu, Dean M. Tullsen, Grigore Rosu, Sumeet Singh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - 32nd International Symposium on Computer Architecture, ISCA 2005
Pages123-133
Number of pages11
DOIs
StatePublished - Nov 10 2005
Event32nd Interntional Symposium on Computer Architecture, ISCA 2005 - Madison, WI, United States
Duration: Jun 4 2005Jun 8 2005

Publication series

NameProceedings - International Symposium on Computer Architecture
ISSN (Print)1063-6897

Other

Other32nd Interntional Symposium on Computer Architecture, ISCA 2005
CountryUnited States
CityMadison, WI
Period6/4/056/8/05

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'A tree based router search engine architecture with single port memories'. Together they form a unique fingerprint.

  • Cite this

    Baboescu, F., Tullsen, D. M., Rosu, G., & Singh, S. (2005). A tree based router search engine architecture with single port memories. In Proceedings - 32nd International Symposium on Computer Architecture, ISCA 2005 (pp. 123-133). (Proceedings - International Symposium on Computer Architecture). https://doi.org/10.1109/ISCA.2005.7