Scalable High Throughput and Power Efficient IP-Lookup on FPGA
Authors:
- Hoang LeHLHoang Le
- Viktor K. PrasannaVPViktor K. Prasanna
- 1 January 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 167-174
Abstract
Most high-speed Internet Protocol (IP) lookup implementations use tree traversal and pipelining. Due to the available on-chip memory and the number of I/O pins of Field Programmable Gate Arrays (FPGAs), state-of-the-art designs cannot support the current largest routing table(consisting of 257 K prefixes in backbone routers). We propose a novel scalable high-throughput, low-power SRAM-based linear pipeline architecture for IP lookup. Using a single FPGA, the proposed architecture can support the current largest routing table, or even larger tables of up to 400 K prefixes. Our architecture can also be easily partitioned, so as to use external SRAM to handle even larger routing tables (up to 1.7 M prefixes). Our implementation shows a high throughput (340 mega lookups per second or 109 Gbps), even when external SRAM is used. The use of SRAM (instead of TCAM) leads to an order of magnitude reduction in power dissipation. Additionally, the architecture supports power saving by allowing only a portion of the memory to be active on each memory access. Our design also maintains packet input order and supports in-place non-blocking route updates.Keywords
This publication has 16 references indexed in Scilit:
- A Memory-Balanced Linear Pipeline Architecture for Trie-based IP Lookup2007
- Efficient Construction of Pipelined Multibit-Trie Router-TablesIEEE Transactions on Computers, 2006
- A novel reconfigurable hardware architecture for IP address lookup2005
- Scalable, memory efficient, high-speed IP lookup algorithmsIEEE/ACM Transactions on Networking, 2005
- A Tree Based Router Search Engine Architecture with Single Port Memories2005
- O(log n) dynamic router-tables for prefixes and rangesIEEE Transactions on Computers, 2004
- An O(log n) dynamic router-table designIEEE Transactions on Computers, 2004
- Fast incremental updates for pipelined forwarding engines2004
- A New Hardware Algorithm for Fast IP Routing Targeting Programmable Routers2003
- Fast address lookups using controlled prefix expansionACM Transactions on Computer Systems, 1999