Re: iptables as a state machine

[Thomas Heinz <creatix@hipac.org>]

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

You wrote:
> Thanks for the correction.

You're welcome.

>>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.
> 
> Any pointers to papers on this topic?

http://citeseer.ist.psu.edu/rd/0%2C56411%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/compress/0/papers/cs/364/http:zSzzSzwww.cs.wustl.eduzSzcszSztechreportszSz1995zSzwucs-95-21.ps.gz/jayaram95efficient.ps
This paper describes the use of an optimized LR parser
for packet classification. Note that it's from 1995.

As for regular expressions, any theoretical computer
science textbook describes the way how to construct
deterministic finite automata from regular expressions
and how to compute the equivalent minimal automaton.
This approach is for example also implemented by flex.

One of the first approaches towards packet
classification was the design of dedicated virtual
machines similar to what is used in compiler
technology.

As the demand for high performance packet classification
grew, one came up with the so-called packet classification
problem which is the foundation of todays firewalling
rule sets.


Regards,

Thomas

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