Technical Report Number
Packet classiﬁcation is an enabling function for a variety of Internet applications including Quality of Ser-vice, security, monitoring, and multimedia communications. In order to classify a packet as belonging to a particular ﬂow or set of ﬂows, network nodes must perform a search over a set of ﬁlters using multiple ﬁelds of the packet as the search key. In general, there have been two major threads of research addressing packet classiﬁcation: algorithmic and architectural. A few pioneering groups of researchers posed the problem, provided complexity bounds, and offered a collection of algorithmic solutions. Subsequently, the design space has been vigorously explored by many offering new algorithms and improvements upon existing al-gorithms. Given the inability of early algorithms to meet performance constraints imposed by high speed links, researchers in industry and academia devised architectural solutions to the problem. This thread of research produced the most widely-used packet classiﬁcation device technology, Ternary Content Address-able Memory (TCAM). New architectural research combines intelligent algorithms and novel architectures to eliminate many of the unfavorable characteristics of current TCAMs. We observe that the community appears to be converging on a combined algorithmic and architectural approach to the problem. Using a tax-onomy based on the high-level approach to the problem and a minimal set of running examples, we provide a survey of the seminal and recent solutions to the problem. It is our hope to foster a deeper understanding of the various packet classiﬁcation techniques while providing a useful framework for discerning relationships and distinctions.
Taylor, David E., "Survey and Taxonomy of Packet Classification Techniques" Report Number: WUCSE-2004-24 (2004). All Computer Science and Engineering Research.