Scalable Multi-Match Packet Classification Using TCAM and SRAM
Authors:
- 19 August 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 65 (7) , 2257-2269
Abstract
Packet classification is an enabling technology for various network services. Fast single-match packet classification can be achieved by using ternary content addressable memory (TCAM) because of the superior speed performance. TCAM has some drawbacks including incapability to store arbitrary ranges, confined TCAM capacity and limited choices of entry lengths. Moreover, TCAM only reports the first matching entry to impose a limitation on supporting multi-match packet classification, which requires all matching rules. The existing algorithms deal with the issues of TCAM-based multi-match packet classification by burdening TCAM with extra entries and/or accesses. In this work, we offload the overhead of TCAM to static random access memory (SRAM) to achieve efficient multi-match packet classification. Our scheme synthesizes TCAM compatible entries by using binary decision trees and employs SRAM for further comparisons. Each synthesized entry can be stored in one TCAM entry to significantly reduce TCAM consumption and fulfill low power consumption. The experimental results show that our scheme can lower the demand of TCAM to improve both search latency and energy efficiency. The scalability of TCAM-based multi-match packet classification can thus be improved drastically.Keywords
Funding Information
- Ministry of Science and Technology, Taiwan (MOST103-2221-E-005-061, MOST104-3115-E-002-005)
This publication has 36 references indexed in Scilit:
- Packet Classification Using Dynamically Generated Decision TreesIEEE Transactions on Computers, 2013
- EffiCutsACM SIGCOMM Computer Communication Review, 2010
- Ternary CAM Power and Delay Model: Extensions and UsesIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2008
- $O(\log W)$ Multidimensional Packet ClassificationIEEE/ACM Transactions on Networking, 2007
- NXG05-2: Fast Filter Updates for Packet Classification using TCAMIEEE Globecom 2006, 2006
- CoPTUA: Consistent Policy Table Update Algorithm for TCAM without lockingIEEE Transactions on Computers, 2004
- 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