Re: iptables as a state machine

[Thomas Heinz <creatix@hipac.org>]

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

Hi Tobias

You wrote:
> What about using a n-ary PATRICIA trie to solve this problem? That
> would yield O(1)-time matching of rules and the data pointer for each
> node in the tree could be the list of targets that apply to that
> particular IP/subnet? Not sure how ranges would work yet, though if
> they didn't fit into a CIDR block...

Maybe you want to have a look at the following paper.
http://tiny-tera.stanford.edu/~nickm/papers/classification_tutorial_01.pdf

It provides a very good overview of a wide range of different
approaches towards packet classification.

There are two basic trie-based approaches presented in the paper.
1) hierarchical tries
    lookup time:        O(w^d)
    storage complexity: O(n * d * w)

2) set-pruning tries
    lookup time:        O(d * w)
    storage complexity: O(n^d * d * w)

n: number of rules
d: number of dimensions (such as source ip, dest. ip, protocol)
w: bit width of largest header field

As you can see from the performance complexity both approaches
are not desirable for d > 1.


BTW, every range in [0, 2^w - 1] can be expressed by at most
2*(w-1) prefixes. Hence, if you have a single rule with d range
matches, you need at most (2*(w-1))^d rules with prefix matches
to express the _single_ range rule.

Sounds not very promising, does it? ;-)


Regards,

Thomas

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