A memory-balanced linear pipeline architecture for trie-based IP lookup

Rapid growth in network link rates poses a strong de-mand on high speed IP lookup engines. Trie-based architec-tures are natural candidates for pipelined implementation to provide high throughput. However, simply mapping a trie level onto a pipeline stage results in unbalanced memory distribution over different stages. To address this problem, several novel pipelined architectures have been proposed. But their non-linear pipeline structure results in some new performance issues such as throughput degradation and de-lay variation. In this paper, we propose a simple and effec-tive linear pipeline architecture for trie-based IP lookup. Our architecture achieves evenly distributed memory while realizing high throughput of one lookup per clock cycle. It offers more freedom in mapping trie nodes to pipeline stages by supporting nops. We implement our design as well as the state-of-the-art solutions on a commodity FPGA and eval-uate their performance. Post place and route results show that our design can achieve a throughput of 80 Gbps, up to twice the throughput of reference solutions. It has con-stant delay, maintains input order, and supports incremen-tal route updates without disrupting the ongoing IP lookup operations