Daniel Hartmeier a écrit :

>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)
>  
>
most people use few rules. at least, few rules that need state (blocking 
bogons may need a lot of rules, but here, state doesn't help at all).

>  M > 50 (an average connection involves more than 50 packets)
>  
>
>because b is so much larger than a.
>
This really depend on what is implemented and on the implementation.

> 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.
>  
>
a is proportional to that, but not equal to that. revisit search algos.
Also, if the filter is really stateful, it'll also check the sequence 
number, ... but let's ignore this.

>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.
>  
>
so you ask the stateless filter to check a lot of things, but don't ask 
the stateful one to do so?

>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 :)
>  
>

I didn't say stateful is bad. I said that it is not possible for 
stateful to _always_ outperform statefless.
I don't even know of an easy way to see when one outperforms the other. 
this is a cache analysis issue, and it is not easy. of course, the first 
hard thing is to define the "standard" model.