Towards Practical Architectures for SRAM-Based Pipelined Lookup Engines

Lookup engines for various network protocols can be implemented as tree-like search structures. Mapping such search structures onto static random addressable memory (SRAM) -based pipeline architectures has been studied as a promising alternative to ternary content addressable memory (TCAM) for high performance lookup engines in next generation routers. Incremental update and memory balancing are identified as two of the major challenges for the SRAM-based pipelined solutions to be practical. Although these two challenges have been separately addressed in some previous work, whether they can be solved simultaneously remains a question. Most of the existing mapping schemes to achieve balanced memory distribution across pipeline stages are static, where the entire search structure needs to be re-mapped to the pipeline once the lookup table has been updated. This paper takes IP lookup as a case study and proposes the incremental mapping scheme to support incremental updates while preserving balanced memory distribution across stages in a linear pipeline. We discuss two variants of the scheme and evaluate their performance in terms of memory balancing and update cost. Furthermore, we optimize the scheme to enable interfacing with external SRAMs so that even larger routing table can be supported using a single chip with limited on-chip memory. Simulation using real-life routing tables validates our schemes. Prototype on a state-of-the-art field programmable gate array (FPGA) shows that our architecture can sustain 80 Gbps throughput for minimum size packets while supporting the currently largest routing table. We believe the proposed schemes can be applied to other SRAM-based pipelined lookup engines for various network protocols.