Routing Table Compaction for TCAM-Based IP Address Lookup

Pi-Chung WANG  Yi-Ting FANG  Tzung-Chian HUANG  

IEICE TRANSACTIONS on Communications   Vol.E93-B   No.5   pp.1272-1275
Publication Date: 2010/05/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E93.B.1272
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Network
ternary content addressable memory,  IP address lookup,  Internet,  

Full Text: PDF(369.6KB)>>
Buy this Article

In this work, we propose a scheme of routing table compaction for IP forwarding engines based on ternary content addressable memory (TCAM). Our scheme transforms the original routing table into a form with only disjoint prefixes. The most prevalent next hop of the routing table is then calculated and the route prefixes corresponding to the next hop are replaced by one TCAM entry. In combination with Espresso-II logic minimization algorithm, the proposed scheme reduces the TCAM storage requirements by more than 75% compared to the original routing tables. We also present an effective approach to support incremental updates.