A Tree Based Router Search Engine Architecture with Single Port Memories
Authors:
- 28 July 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636897,p. 123-133
Abstract
Pipelined forwarding engines are used in core router 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 distributor 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 15 references indexed in Scilit:
- 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 performance comparison of hierarchical ring- and mesh-connected multiprocessor networks2002
- A modular approach to packet classification: algorithms and results2002
- Survey and taxonomy of IP address lookup algorithmsIEEE Network, 2001
- Memory-efficient state lookups with fast updatesACM SIGCOMM Computer Communication Review, 2000
- Classifying packets with hierarchical intelligent cuttingsIEEE Micro, 2000
- Packet classification on multiple fieldsACM SIGCOMM Computer Communication Review, 1999
- Fast and scalable layer four switchingACM SIGCOMM Computer Communication Review, 1998