Title :
IPv6 Lookups using Distributed and Load Balanced Bloom Filters for 100Gbps Core Router Line Cards
Author :
Song, Haoyu ; Hao, Fang ; Kodialam, Murali ; Lakshman, T.V.
Author_Institution :
Bell Labs., Alcatel-Lucent, Holmdel, NJ
Abstract :
Internet line speeds are expected to reach 100 Gbps in a few years. To match these line rates, a single router line card needs to forward more than 150 million packets per second. This requires a corresponding amount of longest prefix match operations. Furthermore, the increased use of IPv6 requires core routers to perform the longest prefix match on several hundred thousand prefixes varying in length up to 64 bits. It is a challenge to scale existing algorithms simultaneously in the three dimensions of increased throughput, table size and prefix length. Recently, Bloom filter-based IP lookup algorithms have been proposed. While these algorithms can take advantage of hardware parallelism and fast on-chip memory to achieve high performance, they have significant drawbacks (discussed in the paper) that impede their use in practice. In this paper, we present the distributed and load balanced bloom filters to address these drawbacks. We develop the practical IP lookup algorithm for use in 100 Gbps line cards. The regular and modular hardware architecture of our scheme directly maps to the state-of-art ASICs and FPGAs with reasonable resource consumption. Also, our scheme outperforms TCAMs on most metrics including cost, power dissipation, and board footprint.
Keywords :
IP networks; Internet; field programmable gate arrays; parallel architectures; resource allocation; table lookup; telecommunication network routing; transport protocols; FPGA; IPv6 lookup; Internet; bit rate 100 Gbit/s; board footprint; core router line card; distributed-and-load balanced bloom filter; hardware parallel architecture; on-chip memory; power dissipation; resource consumption; Communications Society; Energy consumption; Filters; Hardware; Inspection; Power dissipation; Random access memory; Throughput; Transceivers; USA Councils;
Conference_Titel :
INFOCOM 2009, IEEE
Conference_Location :
Rio de Janeiro
Print_ISBN :
978-1-4244-3512-8
Electronic_ISBN :
0743-166X
DOI :
10.1109/INFCOM.2009.5062180