n and Stiliadis discuss a bit-level parallelism that is suitable for hardware implementation and that can classify quickly along multiple dimensions; 13. V. Srinivasan, S. Suri, G. Varghese, and M. Waldvogel, "Fast and Scalable Layer 4 Switching," Proceedings of ACM Sigcomm 1998 (September 1998): 203-214. Downloaded from Digital Engineering Library @ McGraw-Hill (www.digitalengineeringlibrary.com) Copyright © 2004 The McGraw-Hill Companies. All rights reserved. Any use is subject to the Terms of Use as given at the website. CLASSIFICATION PROCESSORS 250 NETWORK PROCESSORS however, it suffers from large memory and bandwidth requirements. 14 Gupta and McKeown from Stanford University introduced the hierarchical intelligent cuttings approach, which is based on a heuristics-based partitioning of the problem space and a clever rearrangement of the decision tree in such a way that takes advantage of the classifier structure, thereby expediting classification perform- ance while keeping the lid over the memory requirements. 15 Other applicable efforts Area- based Quad-Tree (AQT), 16 the Fat-Inverted-Segment (FIS) tree, 17 and the bitmap intersection classifier. 18 For more information, refer to the corresponding references as we will not be examining the internals of these algorithms. P. Gupta and N. McKeown provide an excellent tutorial of the most important classification algorithms in their paper "Algorithms for Packet Classification." paper can be a helpful starting point. One of the most important algorithms that deserves to be mentioned separately is the Recursive Flow Classification (RFC), which has been proposed by Gupta and McKeown.20 It looks at the clas- sification problem as a mapping of S bits (composed from the concatenated content of all fields of interest) onto a series of T bits (the classification outcome). It is based on the observation that creat- ing an ideal memory bank of 2s entries with the corresponding class number stored in each entry slot and where only one memory access would be needed to pr