|
Authors: | M Milind, M Buddhikot, S Suri, Marcel Waldvogel |
Group: | Communication Systems |
Type: | Inproceedings |
Title: | Space Decomposition Techniques for Fast Layer-4 Switching |
Year: | 1999 |
Month: | August |
Pub-Key: | BSW99a |
Book Titel: | Proceedings of the IFIP Sixth International Workshop on Protocols for High Speed Networks (PfHSN 99) |
Abstract: | 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. 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. 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 α can be used to tradeoff search time for update time. Also, this algorithm is amenable to fast software and hardware implementation. |
Resources: | [BibTeX] |