Hi Carson, State entry lookups don't actually occur in constant time. Daniel posted a very interesting paper on PF architecture and performance. http://www.benzedrine.cx/pf-paper.html Or for a quick summary of his on PF of a hash v. red-black tree here: http://www.qorbit.net/nn/Oct-2002/0092.html Cheers, -- steve ------------------------ Date: Thu, 17 Oct 2002 02:26:12 -0400 From: Carson Gaspar <carsonat_private> To: firewall-wizardsat_private Subject: Re: [fw-wiz] CERT vulnerability note VU# 539363 (fwd) [ Discussion of state table performance vs. ruleset performance ] <Warning: lecture ahead> It is not at all surprising that state table lookups are faster. Given enough memory, it is trivial to implement a state table match as a hash lookup, which occurs in constant time, invariant with the number of state entries. After all, the entire logic is matching a Protocol:SourceIP:SourcePort:DestIP:DestPort 5-tuple. Of course, then you have to do some more checking to determine if the packet is valid, but the lookup is cheap. God, do I feel old (and I'm only 31 ;-). Does anyone else remember Drawbridge from TAMU? It could do packet filtering in constant time, due to the design of its filtering engine. There was a significant memory / speed tradeoff being made, as well as a limited ruleset grammar, but it was _blazingly_ fast. I also recall Lucent having a router capable of stateless filtering of an OC-12 (back when that was more impressive) in constant time, assuming the number of rules was less than about 255. They used some obscure math to convert the ruleset into an equation that could be evaluated in hardware, given the appropriate parts of the test packet as input. Most firewalls, however, implement a linear rule traversal. In some cases, they allow grouping, so it's better than linear, but I know of no firewall currently in production that claims constant time. So, at some point: Frule(n)*Krule > Kstate The exact value of n varies depending on the constants, and what (if any) ruleset optimization is performed (manually or automatically) by the rule search algorithm. -- Carson Gaspar _______________________________________________ firewall-wizards mailing list firewall-wizardsat_private http://honor.icsalabs.com/mailman/listinfo/firewall-wizards
This archive was generated by hypermail 2b30 : Thu Oct 17 2002 - 07:40:04 PDT