Flash trie: Beyond 100-Gb/s IP route lookup using hash-based prefix-compressed trie

Masanori Bando, Yi Li Lin, H. Jonathan Chao

Research output: Contribution to journalArticle

Abstract

It is becoming apparent that the next-generation IP route lookup architecture needs to achieve speeds of 100 Gb/s and beyond while supporting IPv4 and IPv6 with fast real-time updates to accommodate ever-growing routing tables. Some of the proposed multibit-trie-based schemes, such as TreeBitmap, have been used in today's high-end routers. However, their large data structures often require multiple external memory accesses for each route lookup. A pipelining technique is widely used to achieve high-speed lookup with the 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 approaches. We use a hash-based membership query to limit off-chip memory accesses per lookup and to balance memory utilization among the memory modules. By compacting the data structure size, the lookup depth of each level can be increased. 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 80-Gb/s worst-case throughput while simultaneously supporting 2 M prefixes for IPv4 and 318 k prefixes for IPv6 with one lookup engine and two Double-Data-Rate (DDR3) SDRAM chips. When implementing five lookup engines on a state-of-the-art field programmable gate array (FPGA) chip and using 10 DDR3 memory chips, we expect FlashTrie to achieve 1-Gpps (packet per second) throughput, equivalent to 400 Gb/s for IPv4 and 600 Gb/s for IPv6. FlashTrie also supports incremental real-time updates.

Original languageEnglish (US)
Article number6169962
Pages (from-to)1262-1275
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume20
Issue number4
DOIs
StatePublished - 2012

Fingerprint

Data storage equipment
Data structures
Throughput
Engines
Routers
Resource allocation
Field programmable gate arrays (FPGA)
Costs

Keywords

  • DRAM
  • field programmable gate array (FPGA)
  • FlashTrie
  • hash
  • IPv4
  • IPv6
  • longest prefix match
  • membership query
  • next-generation network
  • PC-Trie
  • Prefix Compressed Trie
  • route lookup

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Software
  • Computer Science Applications
  • Computer Networks and Communications

Cite this

Flash trie : Beyond 100-Gb/s IP route lookup using hash-based prefix-compressed trie. / Bando, Masanori; Lin, Yi Li; Chao, H. Jonathan.

In: IEEE/ACM Transactions on Networking, Vol. 20, No. 4, 6169962, 2012, p. 1262-1275.

Research output: Contribution to journalArticle

@article{114a0680df0946088f4bb17e97d36996,
title = "Flash trie: Beyond 100-Gb/s IP route lookup using hash-based prefix-compressed trie",
abstract = "It is becoming apparent that the next-generation IP route lookup architecture needs to achieve speeds of 100 Gb/s and beyond while supporting IPv4 and IPv6 with fast real-time updates to accommodate ever-growing routing tables. Some of the proposed multibit-trie-based schemes, such as TreeBitmap, have been used in today's high-end routers. However, their large data structures often require multiple external memory accesses for each route lookup. A pipelining technique is widely used to achieve high-speed lookup with the 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 approaches. We use a hash-based membership query to limit off-chip memory accesses per lookup and to balance memory utilization among the memory modules. By compacting the data structure size, the lookup depth of each level can be increased. 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 80-Gb/s worst-case throughput while simultaneously supporting 2 M prefixes for IPv4 and 318 k prefixes for IPv6 with one lookup engine and two Double-Data-Rate (DDR3) SDRAM chips. When implementing five lookup engines on a state-of-the-art field programmable gate array (FPGA) chip and using 10 DDR3 memory chips, we expect FlashTrie to achieve 1-Gpps (packet per second) throughput, equivalent to 400 Gb/s for IPv4 and 600 Gb/s for IPv6. FlashTrie also supports incremental real-time updates.",
keywords = "DRAM, field programmable gate array (FPGA), FlashTrie, hash, IPv4, IPv6, longest prefix match, membership query, next-generation network, PC-Trie, Prefix Compressed Trie, route lookup",
author = "Masanori Bando and Lin, {Yi Li} and Chao, {H. Jonathan}",
year = "2012",
doi = "10.1109/TNET.2012.2188643",
language = "English (US)",
volume = "20",
pages = "1262--1275",
journal = "IEEE/ACM Transactions on Networking",
issn = "1063-6692",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",

}

TY - JOUR

T1 - Flash trie

T2 - Beyond 100-Gb/s IP route lookup using hash-based prefix-compressed trie

AU - Bando, Masanori

AU - Lin, Yi Li

AU - Chao, H. Jonathan

PY - 2012

Y1 - 2012

N2 - It is becoming apparent that the next-generation IP route lookup architecture needs to achieve speeds of 100 Gb/s and beyond while supporting IPv4 and IPv6 with fast real-time updates to accommodate ever-growing routing tables. Some of the proposed multibit-trie-based schemes, such as TreeBitmap, have been used in today's high-end routers. However, their large data structures often require multiple external memory accesses for each route lookup. A pipelining technique is widely used to achieve high-speed lookup with the 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 approaches. We use a hash-based membership query to limit off-chip memory accesses per lookup and to balance memory utilization among the memory modules. By compacting the data structure size, the lookup depth of each level can be increased. 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 80-Gb/s worst-case throughput while simultaneously supporting 2 M prefixes for IPv4 and 318 k prefixes for IPv6 with one lookup engine and two Double-Data-Rate (DDR3) SDRAM chips. When implementing five lookup engines on a state-of-the-art field programmable gate array (FPGA) chip and using 10 DDR3 memory chips, we expect FlashTrie to achieve 1-Gpps (packet per second) throughput, equivalent to 400 Gb/s for IPv4 and 600 Gb/s for IPv6. FlashTrie also supports incremental real-time updates.

AB - It is becoming apparent that the next-generation IP route lookup architecture needs to achieve speeds of 100 Gb/s and beyond while supporting IPv4 and IPv6 with fast real-time updates to accommodate ever-growing routing tables. Some of the proposed multibit-trie-based schemes, such as TreeBitmap, have been used in today's high-end routers. However, their large data structures often require multiple external memory accesses for each route lookup. A pipelining technique is widely used to achieve high-speed lookup with the 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 approaches. We use a hash-based membership query to limit off-chip memory accesses per lookup and to balance memory utilization among the memory modules. By compacting the data structure size, the lookup depth of each level can be increased. 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 80-Gb/s worst-case throughput while simultaneously supporting 2 M prefixes for IPv4 and 318 k prefixes for IPv6 with one lookup engine and two Double-Data-Rate (DDR3) SDRAM chips. When implementing five lookup engines on a state-of-the-art field programmable gate array (FPGA) chip and using 10 DDR3 memory chips, we expect FlashTrie to achieve 1-Gpps (packet per second) throughput, equivalent to 400 Gb/s for IPv4 and 600 Gb/s for IPv6. FlashTrie also supports incremental real-time updates.

KW - DRAM

KW - field programmable gate array (FPGA)

KW - FlashTrie

KW - hash

KW - IPv4

KW - IPv6

KW - longest prefix match

KW - membership query

KW - next-generation network

KW - PC-Trie

KW - Prefix Compressed Trie

KW - route lookup

UR - http://www.scopus.com/inward/record.url?scp=84865339428&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84865339428&partnerID=8YFLogxK

U2 - 10.1109/TNET.2012.2188643

DO - 10.1109/TNET.2012.2188643

M3 - Article

AN - SCOPUS:84865339428

VL - 20

SP - 1262

EP - 1275

JO - IEEE/ACM Transactions on Networking

JF - IEEE/ACM Transactions on Networking

SN - 1063-6692

IS - 4

M1 - 6169962

ER -