TaPaC: A TCAM-Assisted Algorithmic Packet Classification with Bounded Worst-Case Performance
Authors:
- Xianfeng LiXLXianfeng Li
- Yuanxin LinYLYuanxin Lin
- 1 December 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Abstract
Packet classification is an indispensable yet challenging functionality of modern network devices. Despite more than fifteen years of research, algorithmic solutions still fall short of meeting the line-speed of high performance routers or switches. As a result, the industry is still relying on TCAMbased hardware solutions for parallel lookups. SAX-PAC, a recently proposed hybrid framework, uses a TCAM much smaller than pure TCAM-based technique to accommodate part of the classification rules, and handles the rest of rules with algorithmic lookups. However, the worst- case performance of SAX-PAC is O(logN), which scales with the size of the rule set, thus the line-speed requirement cannot be guaranteed. In this paper, we propose TaPaC, an algorithmic framework assisted by two very small TCAMs, which are used for handling two difficult problems observed by this work. Under this framework, we are able to bound the worst-case performance irrespective of the rule sets. In the meantime, TaPaC is also more memory efficient than existing techniques. Our experimental results show that using ClassBench, the TCAM requirement of TaPaC is two orders of magnitude less than a pure TCAM-based solution, and an order of magnitude less than what SAX- PAC needs. Furthermore, the decisiontrees generated all have short and bounded heights, leading to bounded worst-case performance. Compared to state-of-the-art algorithmic solutions, TaPaC achieves a memory reduction over 200% on average. In essence, TaPaC provides a new algorithmic packet classification technique with the performance comparable to a pure TCAM-based solution, but without the problems of TCAM- based solutions.Keywords
This publication has 16 references indexed in Scilit:
- GreenTCAM: A memory- and energy-efficient TCAM-based packet classification2016
- HybridCuts: A Scheme Combining Decomposition and Cutting for Packet Classification2013
- High-Throughput and Memory-Efficient Multimatch Packet Classification Based on Distributed and Pipelined Hash TablesIEEE/ACM Transactions on Networking, 2013
- A smart pre-classifier to reduce power consumption of TCAMs for multi-dimensional packet classificationACM SIGCOMM Computer Communication Review, 2012
- ParaSplit: A Scalable Architecture on FPGA for Terabit Packet Classification2012
- Survey and taxonomy of packet classification techniquesACM Computing Surveys, 2005
- Packet classification using multidimensional cutting2003
- Scalable packet classificationACM SIGCOMM Computer Communication Review, 2001
- Fast and scalable layer four switchingACM SIGCOMM Computer Communication Review, 1998
- High-speed policy-based packet forwarding using efficient multi-dimensional range matching1998