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

研究成果: Article同行評審

7 引文 斯高帕斯(Scopus)

摘要

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.

原文English
文章編號6514029
頁(從 - 到)3039-3052
頁數14
期刊IEEE Transactions on Computers
63
發行號12
DOIs
出版狀態Published - 2014 十二月 1

All Science Journal Classification (ASJC) codes

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

指紋

深入研究「LayeredTrees: Most specific prefix-based pipelined design for on-chip IP address lookups」主題。共同形成了獨特的指紋。

引用此