Overview

In this chapter, we discuss the problem of packet classification in network processing. The fundamental notion of classifying the ever-changing dynamic outcome of various events into categories implies that consecutive events of this outcome must be distinguished from one another, some context-specific rules must be applied to these event outcomes, and some rational decisions must be taken based on specific criteria. If the dynamic event is extremely unpredictable, as is the case when packets arrive at a network node where a switching/routing device is located, then the shape and form of the outcome (in this case, the packet content) is hard to profile.

Consequently, several rules may be needed to cope with all the possible combinations of factors and parameters that lead to a classification decision. These rules must be stored somewhere in a lookup table or a rule database. They must be made available on an ongoing basis and be accessible at very high speeds in order to facilitate the process. This rule database must then be searched every time an event in need of classification arises. In network processing, the arrival of a new packet is an example of a dynamic event in need of classification. When network gear receives a packet among billions of other packets per second, it must decide within a very short time (a few nanoseconds) whether and how to forward each individual packet, how to process it, and so on. This constitutes the underlying realm of the classification problem. The combination...