Fast firewall implementations for software-based and hardware-based routers
Lili Qiu, George Varghese, Subhash Suri · 2001
Routers must perform packet classication at high speeds to eciently implement functions such as rewalls. The classi-cation can be based on an arbitrary number of prex and range elds in the packet header. The classication required for re-walls is beyond the capabilities oered by standard Operating System classiers such as BPF [12], DPF [7], PathFinder [1] and others. In fact, there are theoretical results that show the general rewall classication problem has poor worst case cost: for searching over N arbitrary lters using k packet elds, ei-ther the worst-case search time is ((logN) k1) or the worst-case storage is O(N k In this paper, we re-examine two basic mechanisms that have been dismissed in the literature as being too inecient: back-tracking search and set pruning trees. We nd using real databases that the time for backtracking search is much bet-ter than the worst case bound; instead of ((logN) k1), the search time is only roughly twice the optimal search time 1 Similarly, we nd that set pruning trees (using a DAG opti-mization) have much better storage costs than the worst case bound; it has memory requirements similar to the RFC scheme of Gupta and McKeown [10]. We also propose several new techniques to further improve the two basic mechanisms. Our major ideas are a novel compression algorithm, the ability to trade smoothly between backtracking and set pruning, and algorithms to eectively make use of hardware if hardware is available. We quantify the performance gain of each technique using real databases. We show that on real rewall databases our schemes, with the accompanying optimizations, are close to optimal in time and storage. 1.