On Sun, Sep 04, 2005 at 01:26:08AM +0200, mouss wrote:

> >there is no overhead - it is faster than stateless filtering, since 
> >state lookups are way faster than ruleset evaluations.
> > 
> >
> hmmmm? this can't be true in the general case. Let's do simple computations:
> assume N active states and K rules.
> for a new connection,
> - the cost of stateful is: a*log(N)+b*K
> - the cost of stateless is: b*K
> for a new connection with M packets, the numbers are
> stateful: M*a*log(N)+b*K
> stateless: M*b*K

It might not be true in all cases, but you can easily observe that
stateful wins in the common case where

  K > 100 (you have more than 100 rules)
  M > 50 (an average connection involves more than 50 packets)

because b is so much larger than a. By observing I mean running very
simple benchmarks of two cases with pf.

a is the cost of one comparison of two keys in the state table, that is
a comparison of two 32-bit and two 16-bit unsigned integers.

b is the cost of evaluating one single rule in the ruleset. This can
involve comparison of many values from the IP and TCP/UDP header, and
the code is not nearly as cheap as that of a state key comparison.

Except for specific cases, like M=2 for UDP DNS queries to different
servers, stateful generally DOES win. And, yes, this includes almost all
cases where N > 100*K. Most people consider N > 100000 a very high load
(imagine each of those connections producing just one packet every 10
seconds, and you end up with a packet rate of 10000 pps). With N=100000,
the a*log(N) is just 17*a, and a is really cheap. 17*a is easily cheaper
than 8*b. That would be 8 rules, most people have lots more.

It can be surprising, but the more controversial it sounds, the more you
have to gain by verifying the claim :)

Daniel