A Tree Based Router Search Engine Architecture with Single Port Memories
Authors:
Open Access
- 1 May 2005
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGARCH Computer Architecture News
- Vol. 33 (2) , 123-133
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.Keywords
This publication has 14 references indexed in Scilit:
- Fast incremental updates for pipelined forwarding engines2004
- Packet classification using multidimensional cutting2003
- The impact of address allocation and routing on the structure and implementation of routing tables2003
- A pipelined memory architecture for high throughput network processors2003
- A modular approach to packet classification: algorithms and results2002
- Scalable packet classification2001
- Survey and taxonomy of IP address lookup algorithmsIEEE Network, 2001
- Fast and scalable layer four switching1998
- An approximate model of processor communication rings under heavy loadInformation Processing Letters, 1997
- The performance of cache-coherent ring-based multiprocessors1993