2014 · 83 citations · 36 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureComputer NetworksMachine LearningNetwork ArchitectureNetwork ProtocolsConstraintsContent-addressable MemoryContent-addressable Memory (Cam)Exponential SpaceMemory-bounded AlgorithmsPacket ClassificationTraffic Classification
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.
36
A threshold of ln <i>n</i> for approximating set cover
Uriel Feige · Journal of the ACM · 1998 · 3.1K citations · Full text
Packet classification using multidimensional cutting
Sumeet Singh, Florin Baboescu, George Varghese et al. · 2003 · 536 citations · Full text
Packet classification using tuple space search
V. Srinivasan, Subhash Suri, George Varghese · 1999 · 489 citations
Fast and scalable layer four switching
V. Srinivasan, George Varghese, Subhash Suri et al. · 1998 · 479 citations · Full text
Classifying packets with hierarchical intelligent cuttings
Pankaj Gupta, Nick McKeown · IEEE Micro · 2000 · 319 citations