On Wed, Oct 16, 2002 at 12:24:11PM -0400, Paul Robertson wrote: > > In my experience (our stuff), ruleset lookup hits on stateless packet > > forwarding rules at the _very top_ of the ruleset is comparable to > > keeping state. > > Hmmm, is this because "normal" rules aren't optimized or hashed, but state > tables were kind of pre-assumed to be a performance issue, and therefore > given performance attention at the design stage? Maybe it's just because > the state information is easy to do a boolean comparison on? In case of pf, it's because states are stored in a binary search tree, which means you find a matching state entry in O(log n) (n being the number of state entries), since you can skip half of the non-matching entries in each comparison (like searching for a name in a phone book). Rule sets, on the other hand, are usually evaluated linearly (or in tree form), but you can't generally find the relevant/deciding rule as efficiently as in a binary search. Rule sets can be as complex as a programming language, and evaluation actually 'executes' the rules from start to end (or until the 'program' aborts, returning the decision), and you can't just jump to the last instruction to get the result (because the results depends on how previous rules applied). There are simpler forms of rules which _can_ be hashed, and those are of course faster than even a state lookup. But they only allow to specify address and port combinations to block or drop. So, while the number of entries is relevant in both data structures, the alogrithm used to access it defines how it scales. Of course, the constant cost of a state lookup and a rule evaluation may shift the point where keeping state starts to pay off. > Have any kind of feel for where the line is? Daniel's 5000 to 100 mention > has me wondering if we can codify the sorts of places where this can be an > easy performance win for folks who are in high utilization scenerios. I think it depends largely on the product and rules you have, so I wouldn't speculate about a general number for the break-even point. But I recommend to anyone with a (stateful) firewall busy filtering statelessy to try and keep state and compare. If you're running a packet filter on a BSD system, for instance, you can easily find the bottlenecks running kernel profiling. If the function doing rule evaluation uses up 95% cpu while the state lookup one is rarely called, keeping state is worth a try. :) Daniel _______________________________________________ firewall-wizards mailing list firewall-wizardsat_private http://honor.icsalabs.com/mailman/listinfo/firewall-wizards
This archive was generated by hypermail 2b30 : Wed Oct 16 2002 - 10:49:16 PDT