ACM Home
SIGMETRICS 2001 / Performance 2001 Home
Call for Papers
Organizing Committee
Technical Program Committee
Registration Information
Advanced Technical Program
Travel Support for Students
Travel Related Information
Other Links of Interest


SIGMETRICS 2001 / Performance 2001

Fast Firewall Implementations for Software and Hardware-based Routers

Lili Qiu
Microsoft Research

George Varghese

Subhash Suri
Washington University in St. Louis

Routers must perform packet classification at high speeds to efficiently implement functions such as firewalls and diffserv. Classification can be based on an arbitrary number of fields in the packet header. Performing classification quickly on an arbitrary number of fields is known to be difficult, and has poor worst-case complexity.

In this paper, we re-examine two basic mechanisms that have been dismissed in the literature as being too inefficient: backtracking search and set pruning tries. We find using real databases that the time for backtracking search is much better than the worst-case bound; instead of $\Omega((logN)^{k-1})$, the search time is only roughly twice the optimal search time\footnote{The height of the multiplane trie is regarded as the optimal search time throughout the paper, unless otherwise specified.}. Similarly, we find that set pruning tries (using a DAG optimization) have much better storage costs than the worst-case bound. We also propose several new techniques to further improve the two basic mechanisms. Our major ideas are (i) backtracking search on a small memory budget, (ii) a novel compression algorithm, (iii) pipelining the search, (iv) the ability to trade-off smoothly between backtracking and set pruning, and (v) algorithms to effectively make use of hardware if hardware is available. We quantify the performance gain of each technique using real databases. We show that on real firewall databases our schemes, with the accompanying optimizations, are close to optimal in time and storage.

[Last updated Fri Mar 23 2001]