@inproceedings{a8c93eaa78b443c6aa35d1a9b2bc3a25,
title = "FlashTrie: Hash-based prefix-compressed trie for ip route lookup beyond 100Gbps",
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.",
author = "Masanori Bando and Chao, {H. Jonathan}",
year = "2010",
doi = "10.1109/INFCOM.2010.5462142",
language = "English (US)",
isbn = "9781424458363",
series = "Proceedings - IEEE INFOCOM",
booktitle = "2010 Proceedings IEEE INFOCOM",
note = "IEEE INFOCOM 2010 ; Conference date: 14-03-2010 Through 19-03-2010",
}