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

["David S. Miller" <davem@redhat.com>]

On 07 Aug 2003 15:58:51 -0400
jamal <hadi@cyberus.ca> wrote:

> > Yes, it does. Still the question is how to solve this
> > generally. Consider the following example ruleset:
> > 
> > 1) src ip 10.0.0.0/30 dst ip 20.0.0.0/20
> > 2) src ip 10.0.0.0/28 dst ip 20.0.0.0/22
> > 3) src ip 10.0.0.0/26 dst ip 20.0.0.0/24
> > 4) src ip 10.0.0.0/24 dst ip 20.0.0.0/26
> > 5) src ip 10.0.0.0/22 dst ip 20.0.0.0/28
> > 6) src ip 10.0.0.0/20 dst ip 20.0.0.0/30
> > 
> > So you have 1 src ip hash and #buckets(src ip hash) many
> > dst ip hashes. In order to achieve maximum performance
> > you have to minimize the number of collisions in the
> > hash buckets. How would you choose the hash function
> > and what would the construction look like?
> > 
> 
> It can be done by using the masks - but it would look really ugly. I
> suppose just providing a good user interface is valuable.

If you input all the keys into the Jenkins hash, how does
it perform?  Has anyone even tried that and compared it
to all of these fancy multi-level tree like hash things?

I think Jenkins would work very well for exactly this kind
of application.  And it's fully available to the entire kernel
via linux/jhash.h and already in use by other things such
as the routing cache and the netfilter conntrack code.