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

From: "David S. Miller" <[email-masked]>
Date: Mon, 11 Aug 2003 22:40:50 -0700

On Tue, 12 Aug 2003 00:39:58 +0200
Michael Bellion and Thomas Heinz <[email-masked]> wrote:

> 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?

The ipv4 FIB hash tables tackle exactly this problem.  The resulting
worse cast complexity is O(n_bits_in_prefix_mask).

The problem you've described is exactly the same as trying to use
hashing for routing tables.