Fast Layer-4 Packet Classification Using Space Decomposition Techniques


Packet classification is the problem of matching each incoming packet at a router against a database of filters, which specify forwarding rules for the packets. The filters are a powerful and uniform way to implement new network services such as firewalls, Network Address Translation (\NAT ), Virtual Private Networks (\VPN ), and per-flow or class-based Quality of Service (\QoS ) guarantees \cite{Kumar98}. While several schemes have been proposed recently that can perform packet classification at high speeds, none of them achieves fast worst-case time for adding or deleting filters from the database \cite{RouterPlugins,Cheenu98,Lakshman98}. In this paper, we present a new scheme, based on space decomposition, whose search time is comparable to the best existing schemes, but which also offers fast worst-case filter update time. The three key ideas in this algorithm are as follows: (1) innovative data-structure based on quadtrees for a hierarchical representation of the recursively decomposed search space, (2) fractional cascading and pre-computation to improve packet classification time, and (3) prefix partitioning to improve update time. Depending on the actual requirements of the system this algorithm is deployed in, a single parameter $\alpha$ can be used to tradeoff search time for update time. Also, this algorithm is amenable to fast software and hardware implementation.