FlashLook: 100-Gbps hash-tuned route lookup architecture

Since the recent increase in the popularity of services that require high bandwidth, such as high-quality video and voice traffic, the need for 100-Gbps equipment has become a reality. In particular, next generation routers are needed to support 100Gbps worst-case IP lookup throughput for large IPv4 and IPv6 routing tables, while keeping the cost and power consumption low. It is challenging for today's state-of-the-art IP lookup schemes to satisfy all of these requirements. In this paper, we propose FlashLook, a low-cost, high-speed route lookup architecture scalable to large routing tables. FlashLook allows the use of low-cost DRAMs, while achieving high throughput. Traditionally, DRAMs are not known for their high throughput due to their high latency. However, FlashLook architecture achieves high throughput with DRAMs by using the DRAM bursts efficiently to hide DRAM latency. FlashLook has a data structure that can be evenly partitioned into DRAM banks, a novel hash method, HashTune to smooth the hash table distribution and a data compaction method called verify bit aggregation to reduce memory usage of the hash table. These features of the FlashLook results in better DRAM memory utilization and less number of DRAM accesses per lookup. FlashLook achieves 100-Gbps worst-case throughput while simultaneously supporting 2M prefixes for IPv4 and 256k prefixes for IPv6 using one FPGA and 9 DRAM chips. FlashLook provides fast real-time updates that can support updates according to real update statistics.