lassifier works sometimes needs to be mod- ified. These modifications entail either inserting new entries or deleting old ones. This can either hap- pen incrementally or it may require a radical reconstruction of the data structure (whether it is a table a graph tree). The time needed for that process is called the setup or preprocessing time. As these trade-offs can vary depending on the structure and the choice of algorithm, they must be considered because they spill over on the application itself. For instance, the policy tables on a gate- way are not changed as often. When it happens, the network manager will usually carry them out man- ually. As this process is rarely done, it may be tolerable that a little more time is used than deemed acceptable for an organization. An ISP network edge router may be required to change its classifica- tion policies often based on dynamic conditions. This must be done with special tools without dis- rupting the network for long, which implies that the preprocessing time must be as short as possible. Some approaches justify a naive approach based on a linear search of the rule space. In the sim- pler case of layer 3 lookups, this approach keeps a linked list of prefixes and its performance increases if that linked list is sorted by the prefix length. The concept is straightforward and exhibits acceptable memory requirements and update capabilities, but it can unfortunately sometimes yield a very long (and therefore unacceptable) classification time. Some other interesting ideas have also been proposed. For instance, the concept of cross- producting introduced by V. Srinivasan exhibits powerful multidimensional classification time per- formance, but consumes an inordinately large amount of memory. 13 The idea of using a grid of tries, also proposed in the same work, performs nicely in classification time and provides the necessary storage for handling up to two dimensions of classification; however, it cannot be easily extended to problems in need of higher dimensions. Lakshma