| 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. |
| Previous by Date: | Re: [PATCH] Duplicate access_ok in sunrpc, David S. Miller |
|---|---|
| Next by Date: | Re: [PATCH] Update bpqether for 2.6, David S. Miller |
| Previous by Thread: | Re: [RFC] High Performance Packet Classifiction for tc framework, jamal |
| Next by Thread: | Re: [RFC] High Performance Packet Classifiction for tc framework, Michael Bellion and Thomas Heinz |
| Indexes: | [Date] [Thread] [Top] [All Lists] |