|
SIGMETRICS 2001 / Performance 2001Fast Firewall Implementations for Software and Hardware-based Routers |
| Authors |
|
Lili Qiu Microsoft Research
George Varghese
Subhash Suri |
| Abstract |
|
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. |