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: "David S. Miller" <davem@xxxxxxxxxx>
Date: Mon, 11 Aug 2003 22:40:50 -0700
Cc: hadi@xxxxxxxxxx, linux-net@xxxxxxxxxxxxxxx, netdev@xxxxxxxxxxx
In-reply-to: <3F381B3E.6080807@xxxxxxxxx>
References: <200307141045.40999.nf@xxxxxxxxx> <1058328537.1797.24.camel@xxxxxxxxxxxxxxxx> <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>
Sender: netdev-bounce@xxxxxxxxxxx
On Tue, 12 Aug 2003 00:39:58 +0200
Michael Bellion and Thomas Heinz <nf@xxxxxxxxx> 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.

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