Re: [RFC] High Performance Packet Classifiction for tc framework
From: Jamie Lokier (jamie@shareable.org)
Date: Fri Aug 15 2003  11:09:32 EST
Michael Bellion and Thomas Heinz wrote:
> >This generalises to multiple dimensions e.g. for doing multiple
> >prefixes on source+target + different combinations of other bits such
> >as protocol, TOS etc.  i.e. arbitrary bitsubset classifiers. The
> >basic principle and the algorithm are the same.
>
> Hm, how do you want to solve the ddimensional PCP by
> doing binary search for each dimension? Remember that
> PCP is not related to longest prefix matching. Instead
> priorities are used.
I don't know what you mean by "PCP", so can't answer the question.
> Maybe you should describe in little more detail what you mean
> by "This generalises to multiple dimensions ...".
I mean that the lookup algorithm works for multidimensional searches.
Creating the search tree can be a little more involved, and I am not
sure how much (if any) node duplication is needed when some kinds of
rule priorities are used.
It may help to say that you don't have to do binary search for each
dimension separately, although that is a possible strategy for prefix
matching.
You can build a tree where each node represents a point (a,b,c...) in
prefixlength space, and whose children are other points in that
space, if you choose to see the general problem as matching multiple
prefixes.
At one extreme, a general bit matcher (i.e. no nonpowerof2
numerical ranges) can be treated as a multidimensional prefix match
where each prefix is length 0 or 1. You see that, if the input rule
set is _equivalent_ to a longestprefix singledimensional rule set,
the optimal multidimensional search tree is trivally found and it
does not do binary search on each dimension separately.
 Jamie

To unsubscribe from this list: send the line "unsubscribe linuxnet" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomoinfo.html