LayeredTrees: Most specific prefix-based pipelined design for on-chip IP address lookups

Yeim-Kuan Chang, Fang Chen Kuo, Han Jhen Kuo, Cheng Chien Su

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

Multibit trie-based pipelines for IP lookups have been demonstrated to be able to achieve the throughput of over 100 Gbps. However, it is hard to store the entire multibit trie into the on-chip memory of reconfigurable hardware devices. Thus, their performance is limited by the speed of off-chip memory. In this paper, we propose a new pipeline design called LayeredTrees that overcomes the shortcomings of the multibit trie-based pipelines. LayeredTrees pipelines the multi-layered multiway balanced prefix trees based on the concept of most specific prefixes. LayeredTrees is optimized to fit the entire routing table into the on-chip memory of reconfigurable hardware devices. No prefix duplication is needed and each W-bit prefix is encoded in a (W + 1)-bit format to save memory. Assume the minimal packet size is 40 bytes. Our experimental results on Virtex-6 XC6VSX315T FPGA chip show that the throughputs of 33.6 and 120.8 Gbps can be achieved by the proposed single search engine and multiple search engines running in parallel, respectively. Furthermore, the impact of update operations on the search performance is minimal. With the same FPGA device, an IPv6 routing table of 290,503 distinct entries can also be supported.

Original languageEnglish
Article number6514029
Pages (from-to)3039-3052
Number of pages14
JournalIEEE Transactions on Computers
Volume63
Issue number12
DOIs
Publication statusPublished - 2014 Dec 1

All Science Journal Classification (ASJC) codes

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

Fingerprint

Dive into the research topics of 'LayeredTrees: Most specific prefix-based pipelined design for on-chip IP address lookups'. Together they form a unique fingerprint.

Cite this