netdev
[Top] [All Lists]

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

To: Michael Bellion and Thomas Heinz <nf@xxxxxxxxx>
Subject: Re: [RFC] High Performance Packet Classifiction for tc framework
From: Jamie Lokier <jamie@xxxxxxxxxxxxx>
Date: Fri, 15 Aug 2003 15:28:13 +0100
Cc: "David S. Miller" <davem@xxxxxxxxxx>, hadi@xxxxxxxxxx, linux-net@xxxxxxxxxxxxxxx, netdev@xxxxxxxxxxx
In-reply-to: <3F390A23.3050409@xxxxxxxxx>
References: <3F16A0E5.1080007@xxxxxxxxx> <1059934468.1103.41.camel@xxxxxxxxxxxxxxxx> <3F2E5CD6.4030500@xxxxxxxxx> <1060012260.1103.380.camel@xxxxxxxxxxxxxxxx> <3F302E04.1090503@xxxxxxxxx> <1060286331.1025.73.camel@xxxxxxxxxxxxxxxx> <3F381B3E.6080807@xxxxxxxxx> <20030811224050.59bc36fe.davem@xxxxxxxxxx> <20030812142913.GB18802@xxxxxxxxxxxxxxxxxx> <3F390A23.3050409@xxxxxxxxx>
Sender: netdev-bounce@xxxxxxxxxxx
User-agent: Mutt/1.4.1i
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
matching.

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
prefixes.

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

<Prev in Thread] Current Thread [Next in Thread>