A smart pre-classifier to reduce power consumption of TCAMs for multi-dimensional packet classification
Authors:
Open Access
- 13 August 2012
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 42 (4) , 335-346
Abstract
Ternary Content-Addressable Memories (TCAMs) has become the industrial standard for high-throughput packet classification. However, one major drawback of TCAMs is their high power consumption, which is becoming critical with the boom of data centers, the growing classifiers and the deployment of IPv6. In this paper, we propose a practical and efficient solution which introduces a smart pre-classifier to reduce power consumption of TCAMs for multi-dimensional packet classification. We reduce the dimension of the problem through the pre-classifier which pre-classifies a packet on two header fields, source and destination IP addresses. We then return to the high dimension problem where only a small portion of a TCAM is activated and searched for a given packet. The smart pre-classifier is built in a way such that a given packet matches at most one entry in the pre-classifier, which make commodity TCAMs sufficient to implement the pre-classifier. Furthermore, each rule is stored only once in one of the TCAM blocks, which avoids rule replication. The presented solution uses commodity TCAMs, and the proposed algorithms are easy to implement. Our scheme achieves a median power reduction of 91% and an average power reduction of 88% on real and synthetic classifiers respectively.Keywords
This publication has 20 references indexed in Scilit:
- Space-Efficient TCAM-Based Classification Using Gray CodingIEEE Transactions on Computers, 2010
- TCAM Razor: A Systematic Approach Towards Minimizing Packet Classifiers in TCAMsIEEE/ACM Transactions on Networking, 2009
- DRES: Dynamic Range Encoding Scheme for TCAM CoprocessorsIEEE Transactions on Computers, 2008
- Algorithms for advanced packet classification with ternary CAMs2005
- Packet classification in large ISPs2005
- Coolcams: power-efficient TCAMs for forwarding engines2004
- Packet classification using multidimensional cutting2003
- Classifying packets with hierarchical intelligent cuttingsIEEE Micro, 2000
- High-speed policy-based packet forwarding using efficient multi-dimensional range matching1998
- Optimal Point Location in a Monotone SubdivisionSIAM Journal on Computing, 1986