McGraw-Hill Companies. All rights reserved. Any use is subject to the Terms of Use as given at the website. CLASSIFICATION PROCESSORS CLASSIFICATION PROCESSORS 253 Classification engines Lookup Engines Algorithmic FIGURE 13.8 The conceptual relationship between classification processors and CAM-based lookup and search engines. for multiple-field-based rules. In such a case, a lookup or search engine requires the help of an extra module that performs the parsing function. In order to build a full-fledged classification processor, a lookup engine must be augmented by a parsing engine. This can be accomplished by two types of technologies: a combination of modules for the parsing and lookup functions, which would be performing these functions in two consecutive steps, or pro- grammable state machine (PSM) techniques and methods to implement a classifier that can combine both steps simultaneously. A classifier usually produces two things at its output: a digest and a tag. The processor is programmed to parse the string of the packet and look for specific patterns. When match is found, a numerical identifier (the tag) is calculated and produced at the output for that spe- cific packet. The digest, on the other hand, is a user-defined extraction of the content of specific bit positions and/or bit fields, which are collectively put together in a new bit sequence called the digest in this context. For example, in a DiffServ application, a digest of up to 128 bits is then concatenated with a tag of up to 32 bits. As a result, 160 bits is produced at the output of the classifier. Of course, the choice of algorithm depends on many factors. Various algorithms can be used, but the algorithms that we have encountered in route address and next-hop searches are completely inad- equate here. This is why at higher layers, especially for layer-7-based search and classification prob- lems, character-string-based search and match algorithms are used. Several algorithms have been proposed and are being used in such systems. It may be 