Bounded Prefix Expansion and Compression Support of Fast TCAM Updating

Gesan Wang; Nian-Feng Tzeng

4th International IEEE Conference on Broadband Communications, Networks, Systems

Research Article

Bounded Prefix Expansion and Compression Support of Fast TCAM Updating

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/BROADNETS.2007.4550523,
    author={Gesan Wang and Nian-Feng Tzeng},
    title={Bounded Prefix Expansion and Compression Support of Fast TCAM Updating},
    proceedings={4th International IEEE Conference on Broadband Communications, Networks, Systems},
    publisher={IEEE},
    proceedings_a={BROADNETS},
    year={2010},
    month={5},
    keywords={Prefix compression prefix expansion table updates Ternary Content Addressable Memory (TCAM).},
    doi={10.1109/BROADNETS.2007.4550523}
}

Gesan Wang
Nian-Feng Tzeng
Year: 2010
Bounded Prefix Expansion and Compression Support of Fast TCAM Updating
BROADNETS
IEEE
DOI: 10.1109/BROADNETS.2007.4550523

Gesan Wang¹^,*, Nian-Feng Tzeng²^,*

1: EdgeControl Department Akamai Technologies, Inc. Cambridge, Massachusetts, 02142, U.S.A.
2: Center for Advanced Computer University of Louisiana at Lafayette Lafayette, Louisiana, 70504, U.S.A.

*Contact email: gewang@akamai.com, tzeng@cacs.louisiana.ed

Abstract

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%

Keywords: Prefix compression prefix expansion table updates Ternary Content Addressable Memory (TCAM).

Published: 2010-05-16
Publisher: IEEE
Modified: 2010-05-16

: http://dx.doi.org/10.1109/BROADNETS.2007.4550523