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

From: jamal (
Date: Mon Aug 11 2003 - 22:00:56 EST


On Mon, 2003-08-11 at 18:39, Michael Bellion and Thomas Heinz wrote:

> > It was very close ;-> The guy looked motivated i felt scared for a while
> > that he will be asking a lot of questions. Then i never heard about it
> > again ;-> I think he left town too.
> Too bad, you should have told the guy about all the fame
> and glory ;-)

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


> This is a fundamental issue related to the use of hashes in this
> context. It shows that it is _impossible_ to create a hash which
> meets the requirement of O(1) rules per bucket in the setting
> described above regardless how clever you choose the hash function.
> What do you think about it? Do you agree?

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.

> >>BTW, this approach can be extended to 2 or more dimensions
> >>where the hash function for each hash has to meet the
> >>requirement. Of course this information is not very helpful
> >>since the problem of defining appropriate hash functions
> >>remains ;)
> >
> > Is that problem even solvable?
> Well, one could argue that the _problem_ is not precisely
> defined to answer this question since "easily (= fast)
> computable hash function" is rather spongy.
> Ignoring the "fast computable" requirement, the problem
> is solvable simply because the hash function is finite ...
> but again this does not help a bit ;-)
> So, do you agree that it is _impossible_ to express arbitrary
> access lists using the hash tree approach if each hash bucket
> is required to hold O(1) rules?
> [You already agreed that this requirement is needed for the
> tree of hashes to perform optimally.]

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.

> > This is why i was wondering how fast your instertions and deletions are.
> > Seems to me you will have to sort the rules everytime.
> No, there is no sorting of rules involved. Each rule insert
> operation inserts the native matches of the rule into the
> (dim)tree.

I will have to cathup with you at some point - i think i understand what
you mean.

> > Dont you think this "dynamic adjustment" is unnecessary. Essentially you
> > enforce a model where every rule is a different priority.
> Well, we consider the model beneficial for the user.
> First of all the requirement is also present in the
> classical PCP definition ;) and secondly it supports
> dynamic rulesets better because using static priorities
> you ran into the problem of redefining a lot of prios
> manually sooner or later.

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.


> >
> > I am not sure i understood the part about ignoring tcf_result.
> If there would be no tcf_result then classifiers are
> simply matches, e.g. like iptables matches. They don't have
> an action associated with them. In iptables, from a technical
> viewpoint you could say that a target is basically the same
> as a match with an action attached to it.

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.


> > But could you not have
> > the filters repeat the same classid for every filter?
> 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.

> The reason why we want to have several non-native
> matches in one rule is to allow the expression of a
> conjunction of these matches. This is not possible using
> several rules.

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.


To unsubscribe from this list: send the line "unsubscribe linux-net" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at