IPv6 Lookups using Distributed and Load Balanced Bloom Filters for 100Gbps Core Router Line Cards

Internet line speeds are expected to reach 100Gps in a few years. To match line rates, a single router line card will have to forward 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 from 16 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 longest IP prefix-match algorithms have been proposed. While these algorithms can take advantages of hardware parallelisim 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 addresses these drawbacks. we develop the practicle IP lookup algorithm for use in 100Gbps line cards. The regular and modular hardware architecture of our schemes 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.