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

On Tue, 12 Aug 2003 00:39:58 +0200
Michael Bellion and Thomas Heinz [off-list ref] 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.