FlashTrie: Hash-based prefix-compressed trie for ip route lookup beyond 100Gbps

Masanori Bando, H. Jonathan Chao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

It is becoming apparent that the next generation IP route lookup architecture needs to achieve speeds of 100-Gbps and beyond while supporting both IPv4 and IPv6 with fast real-time updates to accommodate ever-growing routing tables. Some of the proposed multibit-trie based schemes, such as Tree Bitmap [1], have been used in today's high-end routers. However, their large data structure often requires multiple external memory accesses for each route lookup. A pipelining technique is widely used to achieve high-speed lookup with a cost of using many external memory chips. Pipelining also often leads to poor memory load-balancing. In this paper, we propose a new IP route lookup architecture called FlashTrie that overcomes the shortcomings of the multibit-trie based approach. We use a hash-based membership query to limit off-chip memory accesses per lookup to one and to balance memory utilization among the memory modules. We also develop a new data structure called Prefix-Compressed Trie that reduces the size of a bitmap by more than 80%. Our simulation and implementation results show that FlashTrie can achieve 160-Gbps worst-case throughput while simultaneously supporting 2-M prefixes for IPv4 and 279-k prefixes for IPv6 using one FPGA chip and four DDR3 SDRAM chips. FlashTrie also supports incremental real-time updates.

Original languageEnglish (US)
Title of host publication2010 Proceedings IEEE INFOCOM
DOIs
StatePublished - 2010
EventIEEE INFOCOM 2010 - San Diego, CA, United States
Duration: Mar 14 2010Mar 19 2010

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

OtherIEEE INFOCOM 2010
CountryUnited States
CitySan Diego, CA
Period3/14/103/19/10

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'FlashTrie: Hash-based prefix-compressed trie for ip route lookup beyond 100Gbps'. Together they form a unique fingerprint.

  • Cite this

    Bando, M., & Chao, H. J. (2010). FlashTrie: Hash-based prefix-compressed trie for ip route lookup beyond 100Gbps. In 2010 Proceedings IEEE INFOCOM [5462142] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2010.5462142