Re: [Fwd: [ANNOUNCE] Layer-7 Filter for Linux QoS]

[Werner Almesberger <wa@almesberger.net>]

Ethan Sommer wrote:
> I take it back, it is regular (kinda) but you can't to it with a 
> deterministic finite atomaton. If there is a cycle in pattern1, off of 
> which pattern2 has a branch, then you would need to count how many times 
> you have gone around the cycle to know where to jump to in pattern2 if 
> it fails to match pattern1

You mean things like

a*b -> 1
ac -> 2

? You can still express this with a DFA, i.e.

a(c|a*b)

Of course, if you have patterns that match the same string, you
need to decide at some point whether you want longest or shortest
match.

For the idea of using regexps for all types of classification: 
this is definitely something I'd love to see. The problem I've
encountered is that it seems prohibitively expensive to
construct an efficient DFA from human-friendly input.

I experimented a bit with this in tcng, but never got to a
usable solution. (tcng can handle arbitrary expressions, but
it does this by following a collection of rules for rewriting
the expression into a canonical and possibly redundant form.
Basically, it does what a human being would do if given the
task of simplifying a Boolan expression. This is usually quick,
but has very ugly worst-case overhead.)

I never thought of viewing this as a regexp, though. For this,
one would need to be able to introduce positions, e.g. through
the ability of putting "^" in the middle of an expression.
Example:

^(A|B|C)(^D)|^(E|D)

where A ... E would be strings containing 0, 1, or .

Example:

ip_tos == 0xb8:   ^........10111000

Now, how to turn such expressions with embedded ^ efficiently
into a DFA ?

- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
/_http://www.almesberger.net/____________________________________________/