TreeCAM
Authors:
Open Access
- 6 December 2011
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-12
Abstract
Packet Classification is a key functionality provided by modern routers. Previous approaches --- TCAM and algorithmic --- perform well in either lookup efficiency (power and number of accesses) or update effort but not both. To perform well in both, we propose TreeCAM, which employs three novel ideas. (1) Dual versions of TreeCAM's decision tree to decouple lookups and updates: A coarse version with a few thousand rules per leaf achieves efficient lookups and a fine version with a few tens of rules per leaf reduces update effort. (2) Interleaved layout of the rules in the TCAM: Combined with the fine version's few rules per leaf, the layout enables us to bound our worst-case update effort. (3) Path-by-path updates to enable update work to be interspersed with packet lookups (i.e., non-atomic updates), eliminating packet buffering or packet drops during update. Using simulations of 100,000-rule classifiers, we show that TreeCAM performs well in both lookups and updates: (1) 6--8 TCAM subarray accesses per packet, matching modern TCAMs. (2) close to an idealized TCAM in worst-case update effort while requiring little buffering of packets.Keywords
This publication has 17 references indexed in Scilit:
- OpenFlowACM SIGCOMM Computer Communication Review, 2008
- NXG05-2: Fast Filter Updates for Packet Classification using TCAMIEEE Globecom 2006, 2006
- Survey and taxonomy of packet classification techniquesACM Computing Surveys, 2005
- Algorithms for advanced packet classification with ternary CAMs2005
- CoPTUA: Consistent Policy Table Update Algorithm for TCAM without lockingIEEE Transactions on Computers, 2004
- Coolcams: power-efficient TCAMs for forwarding engines2004
- Packet classification using multidimensional cutting2003
- Fast updating algorithms for TCAMIEEE Micro, 2001
- Classifying packets with hierarchical intelligent cuttingsIEEE Micro, 2000
- High-speed policy-based packet forwarding using efficient multi-dimensional range matching1998