Dynamic multiway segment tree for IP lookups and the fast pipelined search engine

Yeim Kuan Chang, Yung Chieh Lin, Cheng Chien Su

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)

Abstract

A dynamic multiway segment tree (DMST) is proposed for IP lookups in this paper. DMST is designed for dynamic routing tables that can dynamically insert and delete prefixes. DMST is implemented as a B-tree that has all distinct end points of ranges as its keys. The complexities of search, insertion, deletion, and memory requirement are the same as the existing multiway range tree (MRT) and prefix in B-tree (PIBT) for prefixes. In addition, a pipelined DMST search engine is proposed to further speed up the search operations. The proposed pipelined DMST search engine uses off-chip SRAMs instead of on-chip SRAMs because the capacity of the latter is too small to hold large routing tables and the cost of the latter is too expensive. By utilizing current FPGA and off-chip SRAM technologies, our proposed five-stage pipelined search engine can achieve the worst case throughputs of 33.3 and 41.7 million packets per second (Mpps) with 144-bit and 288-bit wide SRAM blocks, respectively. Furthermore, a straightforward extension of the pipelined search engine with multiple independent off-chip SRAMs can achieve the throughput of 200 Mpps which is equivalent to 102 Gbps for minimal Ethernet packets of size 64 bytes.

Original languageEnglish
Article number5278660
Pages (from-to)492-506
Number of pages15
JournalIEEE Transactions on Computers
Volume59
Issue number4
DOIs
Publication statusPublished - 2010

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Dynamic multiway segment tree for IP lookups and the fast pipelined search engine'. Together they form a unique fingerprint.

Cite this