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

Yeim Kuan Chang, Yung Chieh Lin, Cheng Chien Su

研究成果: Article同行評審

18 引文 斯高帕斯(Scopus)


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.

頁(從 - 到)492-506
期刊IEEE Transactions on Computers
出版狀態Published - 2010

All Science Journal Classification (ASJC) codes

  • 軟體
  • 理論電腦科學
  • 硬體和架構
  • 計算機理論與數學


深入研究「Dynamic multiway segment tree for IP lookups and the fast pipelined search engine」主題。共同形成了獨特的指紋。