SAX-PAC (Scalable And eXpressive PAcket Classification)
Authors:
Open Access
- 17 August 2014
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 44 (4) , 15-26
Abstract
Efficient packet classification is a core concern for network services. Traditional multi-field classification approaches, in both software and ternary content-addressable memory (TCAMs), entail tradeoffs between (memory) space and (lookup) time. TCAMs cannot efficiently represent range rules, a common class of classification rules confining values of packet fields to given ranges. The exponential space growth of TCAM entries relative to the number of fields is exacerbated when multiple fields contain ranges. In this work, we present a novel approach which identifies properties of many classifiers which can be implemented in linear space and with worst-case guaranteed logarithmic time \emph{and} allows the addition of more fields including range constraints without impacting space and time complexities. On real-life classifiers from Cisco Systems and additional classifiers from ClassBench (with real parameters), 90-95% of rules are thus handled, and the other 5-10% of rules can be stored in TCAM to be processed in parallel.Keywords
Funding Information
- Cisco Systems (A Fog Computing Architecture)
This publication has 33 references indexed in Scilit:
- Compressing IP forwarding tables2013
- Space and speed tradeoffs in TCAM hierarchical packet classificationJournal of Computer and System Sciences, 2013
- A smart pre-classifier to reduce power consumption of TCAMs for multi-dimensional packet classification2012
- TreeCAM2011
- BubbleSearch: A simple heuristic for improving priority-based greedy algorithmsInformation Processing Letters, 2006
- CoPTUA: Consistent Policy Table Update Algorithm for TCAM without lockingIEEE Transactions on Computers, 2004
- The Minimum Equivalent DNF Problem and Shortest ImplicantsJournal of Computer and System Sciences, 2001
- Classifying packets with hierarchical intelligent cuttingsIEEE Micro, 2000
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Range Searching and Point Location among Fat ObjectsJournal of Algorithms, 1996