Bounded prefix expansion and compression in support of fast TCAM updating

As the demand for bandwidth grows, Internet routers must run faster. Ternary Content Addressable Memory (TCAM) has been known as a promising device in composing simple and efficient solutions for fast forwarding table lookups. However, most existing TCAM-based IP lookup solutions suffer from lengthy update durations imposed by TCAM entry shifts for maintaining the prefix order constraint. In this paper, a TCAM-based longest prefix search design is proposed in support of prompt and stable incremental updates. This is achieved by converting a conventional prefix table into multiple Bounded Minimum Independent Prefix Sets (B-MIPS) using a technique called Bounded Prefix Expansion and Compression (BPEC). Experimental results show its significant performance improvement in both the worst and the average cases when compared with previous TCAM-based IP lookup solutions. Additionally, the design exhibits considerable forwarding table size reduction, by more than 25%.