One of the most important requirements for forwarding engines that support differentiated services is the ability to identify the context of packets and apply the actions necessary to satisfy service requirements. Mechanisms to support the above functions are termed packet filtering or packet classification.
The traditional application of packet filters has been for providing firewall and security functions. However, another important application, in support of differentiated services, is the identification and classification of packets originated by specific sites, customers, or applications so as to provide the resources necessary for meeting customer-specific differentiated services requirements. Large scale packet filtering functionality enables both edge routers, as in [14], and core routers to support differentiated services that are more flexible and customer-specific than those restricted to service offering based on interpretation of the TOS bits alone [38].
Packet filters should parse
a large portion of the packet header, including information
concerning
transport protocols, before forwarding decisions are made
. The parsing
is based on a set of rules that are defined either by
network management software or by real-time reservation
protocols such as RSVP.
The actions that packet filters may apply can include
the traditional security functions, such as dropping
of unauthorized packets, redirection of packets to proxy servers, etc.,
as well as actions related to queueing, scheduling, and routing
decisions using not only destination addresses but also source addresses,
source port numbers, destination port numbers, etc.
Two desirable attributes for packet filtering are:
The general packet classification problem can be viewed as a point location problem in multidimensional space, where given a set of n d-dimensional objects (that represent the filter rules) and a point in a d-dimensional space (that represents the arriving packet) the problem is to find the object that contains the point. This is a classic problem in computational geometry and numerous results have been reported in the literature [9, 10, 16, 40]. When considering the general case of d ;SPMgt;3 dimensions, as is the problem of packet classification, the best algorithms considering time or space have either an complexity with O(n) space, or an O(log n) time-complexity with space. [40]. Though algorithms with these complexity bounds are useful in many applications, they are not directly useful for packet filtering. To illustrate this, let us assume that we would like the router to be able to process 1K rules of 5 dimensions within (to sustain a 1 million packets per second throughput). An algorithm with execution time and O(n) space requires 10K memory accesses per packet. This is impractical with any current technology. If we use an time and space algorithm, then the space requirement becomes prohibitively large since it is in the range of 1000 Gigabytes. Furthermore, none of the above algorithms addresses the problem of arbitrary overlaps.
However, the above results, do not mean that packet filtering cannot be done at high speeds given the constraints of the problem when applied to routers. We now sketch ideas that were used for a prototype implementation. Interested readers are referred to [33] for details of the implemented algorithm.
A simple approach to the problem of multi-dimensional search, as used for packet filtering, is to use decomposable search. Here the idea is to state the original query as the intersection of a few numbers of simpler queries. The challenge in obtaining a poly-logarithmic solution, is to decompose the problem such that the intersection step does not take more time than the required bound. However, as was pointed out before, even a solution for 5 dimensional packet filtering is not practical for our application where n can be in the thousands. Therefore, we need to employ parallelism of some sort. Moreover, we require simple elemental operations to make the algorithm amenable to hardware implementation. Instead of algorithms with the best asymptotic bounds, we are interested in decomposing the queries such that sub-query intersection can be done fast (with memory-access as cost metric) for n in the thousands and memory word-lengths that are feasible with current technology. Rules are represented by 5-dimensional objects that can arbitrarily overlap. The preprocessing step of the algorithm projects the edges of the objects to the corresponding axis. We next associate a set of rules with each dimension. A rule belongs to the set if and only if the corresponding object overlaps with the interval that the set corresponds to. Note that because of the method by which the intervals were created, it is not possible for a rectangle to overlap, say, only with half an interval. During the first on-line step, we locate the intervals in all axes that contain the point that represents the arriving packet. In the second step, we use the sets to locate the highest priority object that covers this point by a simple intersection operation.
The algorithm has been implemented in 5 dimensions in the Bell Labs Router prototype using a single FPGA device and Synchronous SRAMs chips supporting up to 512 rules and processing 1 million packets per second in the worst case. This is achievable despite the device being run at a very low speed of 33 MHz. Since we used the same memory chips as those used in the L2-caches of personal computers, the cost of the memories is low. The device can be used as a co-processor, next to a general purpose processor that handles all the other parts of IP forwarding or firewall functions. An improved algorithm presented in [33] can be used to process 8K filter rules at 1 million packets per second using a 66Mhz clock.
The 2-dimensional classification problem is of increasing importance in the evolving Internet architecture. Although RSVP, or similar reservation protocols, can offer end-to-end service guarantees for specific flows, it is not clear whether such a reservation based model can be scaled for operation over high-speed backbones where a very large number of flows can be concurrently active. An alternative approach that has been proposed is route aggregated flows along specific traffic engineered paths. This directed routing is based not only on the destination address of packets, but on the source address as well [34]. RSVP or similar reservation protocols can be used for setting the aggregation and routing rules [34, 7]. The key mechanism needed to support such a scheme in a high-speed core router is a 2-dimensional classification or lookup scheme that determines the next hop, and the associated resource allocations, for each packet as a function of both the source and destination addresses. Two-dimensional classification is useful not only for setting-up traffic engineered source-destination paths, but also for multicast forwarding which requires lookups based on both the source address and multicast group [20, 55].
The two dimensional look-up problem is a restricted case of the general classification problem where the rules in at least one of the two dimensions (source or destination address) are defined in terms of CIDR prefixes. Rules can still have arbritrary overlaps and priority amongst rules is used to resolve conflicts. For IP routers, we are interested in solutions that can scale to hundreds of thousands of entries. Also, as for all other operations, we are interested in only worst-case performance of the algorithms since we want to avoid queueing for header processing in order to provide service assurances.
A fast algorithm for this problem is presented in [33].
It is shown that for a number of possible prefix lengths
of 32 and 
filter rules, the
number of memory accesses
is about 50 which makes it
possible to process at a million packets per second with a less
than a 100 Mhz clock speed.
Combining fast filtering in many dimensions with source-destination
based routing widens the range
of options feasible for evolving the current best-effort
Internet to the Internet of the future capable of providing
customized differentiated services. Specifically, there may
be no need to restrict filtering to the edges or to very simple
operations such as using only the TOS bits in the IP
packet header.