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

From: Jamie Lokier (
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 bit-subset classifiers. The
> >basic principle and the algorithm are the same.
> Hm, how do you want to solve the d-dimensional 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 multi-dimensional 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

You can build a tree where each node represents a point (a,b,c...) in
prefix-length space, and whose children are other points in that
space, if you choose to see the general problem as matching multiple

At one extreme, a general bit matcher (i.e. no non-power-of-2
numerical ranges) can be treated as a multi-dimensional prefix match
where each prefix is length 0 or 1. You see that, if the input rule
set is _equivalent_ to a longest-prefix single-dimensional rule set,
the optimal multi-dimensional 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 linux-net" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at