Re: htb parallelism on multi-core platforms

[Radu Rendec <radu.rendec@ines.ro>]

On Wed, 2009-04-29 at 14:23 +0200, Jarek Poplawski wrote:
> According to the author's(?) comment with hysteresis "The speed gain
> is about 1/6", so not very much here considering htb_dequeue time.

Thought so :)

> Radu, since not only your worst case, but also the real case u32
> lookups are very big I think you should mainly have a look at Calin's
> u32 hash generator or at least his method, and only after optimizing
> it try these other tricks. Btw. I hope Calin made this nice program
> known to networking/admins lists too.

I've just had a look at Calin's approach to optimizing u32 lookups. It
does indeed make a very nice use of u32 hash capabilities, resulting in
a maximum of 4 lookups. The algorithm he uses takes advantage of the
fact that only a (small) subset of the whole ipv4 address space is
actually used in an ISP's network.

Unfortunately his approach makes it a bit difficult to dynamically
adjust the configuration, since the controller (program/application)
must remember the exact hash tables, filters etc in order to be able to
add/remove CIDRs without rewriting the entire configuration. Unused hash
tables also need to be "garbage collected" and reused, otherwise the
hash table id space could be exhausted.

Since I only use IP lookups (and u32 is very generic) I'm starting to
ask myself if a different kind of data structures and classifier were
more appropriate.

For instance, I think a binary search tree that is matched against the
bits in the ip address would result in pretty nice performance. It would
take at most 32 iterations (descending through the tree) with less
overhead than the (complex) u32 rule match.

> Btw. #2: I think you wrote you didn't use iptables...
No, I don't use iptables.

Btw, the e1000e driver seems to have no way to disable NAPI. Am I
missing something (like a global kernel config option that disables NAPI
completely)?

Thanks,

Radu