Subject: Re: [RFC] High Performance Packet Classifiction for tc framework

From: Michael Bellion and Thomas Heinz <[email-masked]>
Date: Tue, 12 Aug 2003 16:56:20 +0200

Hi Jamal

You wrote:
> Some fires scare even brave firemen. This was a brave fireman until he
> saw the fire ;->

LOL :-)

> I have to go back and read the theory again to fully comprehend it but
> intutively you are right. I claim that if you knew your input well then
> you could construct a hash which will closely approach perfect hashing.
> So if i was to use the example you gave me earlier i could approximate a
> o(1) hash. u32 allows me to do so once i know how things will look like.
> Of course i have to do that mnaully with a pencil and paper.

Apart from the fact that the "pencil and paper" approach is not
feasible for complex examples where there are no strict regularities
in the rule set, you simply cannot avoid the implications when
choosing a certain prefix length for the hash (as described in the
previous posting). So probably in most cases even "pencil and paper"
won't help.

> yes. But note the caveat i put above on knowing the input and being able
> to manually use a pencil to map out the hash. Now automate the pencil
> and paper and let some cpu analyse the traffic patterns as well as
> adjust the hashes ... maybe a thesis for someone.

Yes, maybe someone should dig further but as long as the
assumptions stay the same you have to live with the consequences
stated in our last posting.

> well, with the iptables scheme at least you need to know where to insert
> the rules; so theres some manual labor involved there as well ;->
> Out of curiosity with such a model how do you define a default rule?
> In the prio model(and tc), you can have a default catchall rule in the
> lowest priority, this way should higher prios fail this will catchall.

In theory the default rule has priority "infinity".
In an implementation you can simply choose the priority of the default
rule 1 + max{prio(r) | for all rules r}. So it's increased by 1 for
every insert operation.

> Ok, i see your point, so you are saying that a tcf_result is infact a
> hardcoded action which should probably be called "setclassid".
> Interesting thought.

Yes :-)

>>Each rule can only have one action or return "value"
>>attached to it so if we want to use embedded classifiers
>>(as matches) their classid (= action) must be ignored.
> 
> you want the "continue" action essentially.

Sorry but we don't seem to get your point here.
How is the "continue" action related to having multiple
embedded classifiers in a rule which essentially provides
1 single action?

> I think i finally see your point. Yes, this could be an improvement that
> could be made to tc. Infact you have motivated me to write a
> "setclassid" action which will override the classid defined otherwise.

:-)

Regards,

+-----------------------+----------------------+
|   Michael Bellion     |     Thomas Heinz     |
| <[email-masked]>  |  <[email-masked]> |
+-----------------------+----------------------+
|    High Performance Packet Classification    |
|       nf-hipac: http://www.hipac.org/        |
+----------------------------------------------+