Re: iptables as a state machine

[Thomas Heinz <creatix@hipac.org>]

[-- Attachment #1: Type: text/plain, Size: 2633 bytes --]

Hi David

Your statement about the algorithmic approach of nf-hipac
is wrong.

You wrote:
> nf-hipac is what I was indirectly referring to when I
> said "B-Tree based schemes". :-)
> 
> nf-hipac is fast for lookups, but it does so at a huge
> cost in memory usage.

There are indeed cases where the memory consumption of
the currently implemented scheme grows huge. Nevertheless,
your explanation of why this is the case is wrong.
 From your explanation, one must conclude that nf-hipac
is not even capable of handling _any_ real world rule set.

> It uses B-Trees and prefix
> expansion, which is a well known technique for this
> task.
> 
> How prefix expansion works is basically like the following.
> Say you had a rule which matches on address "10.0.0.0/24"
> Prefix expansion would duplicate this rule 256 times, one
> for every address in that prefix'd range.
> 
> 	10.0.0.1
> 	10.0.0.2
> 	...
> 	10.0.0.255
> 
> Then you can use whatever data structure you wish to do
> an exact match lookup.  The nf-hipac folks choose a B-Tree
> although at this point you could simply use a plain hash
> as well.

Sorry David, but that is completely wrong. Doing packet
classification this way would _not_ scale, even for the
simplest rule bases.

nf-hipac views the rules geometrically. Each rule is a
hypercube in d-dimensional space (d = number of matches).
This representation is powerful enough to express each
"iptables-like" rule as one "nf-hipac" rule.
The classification is based on solving one-dimensional
problems and thus recursively reducing the d-dimensional
problem to a (d-1)-dimensional one (and so on).

> It is a classic example, in fact, of a memory usage vs.
> lookup performance tradeoff.

Its indeed a tradeoff but it's a big difference if your
rules are simply points in d-dimensional space (as you
described) or hypercubes. The latter is obviously more
expressive.

> I warn you if you go looking at the existing nf-hipac, it's
> big and complex :-)  My dislike of nf-hipac's approach is
> one of the reasons I went looking for other possible schemes.

It's of course fine to think about alternative approaches.
Did I get you right that you intend to model packet
classification as regular expression matching on the packet
header and then compute the minimal automata to represent
the expression rule base?

This approach was already considered very early in history
of packet classification. Even more complex matchings as
context free grammars have been used. Nonetheless, even
regular expressions have been found to not being able to
cope with high performance demands of todays rule bases.


Regards,

Thomas

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 251 bytes --]