Re: [Cake] CAKE set-associative hashing

[Dave Taht <dave.taht@gmail.com>]

Much of the queuing literature involving fair queuing to date has
involved either the assumption of a perfect hash, or a one way direct
hash, cake does indeed innovate here.

set associative caches, on the other hand, are well explored in CPU
designs, where a 2 or 4 way set is most common.

An open question is how many levels of associativity relative to
"ideal" and aqm'd queue depth, number of queues, and bandwidth is
"ideal". I suspect 1024 queues is low for 10GigE, high (with 8 way set
associativity) for under a gbit. It would be nice to have a formula to
calculate these relations.

More complicated is that all the 10GigE capable hardware has a low
number (often 64) of built-in direct hash mapped hardware queues,
which does re-introduce the birthday problem at a level that cake
doesn't handle, as on a hardware mq'd device, we end up with 64 cake
instances. Some gigE hardware has 4-8 hardware queues, where the
birthday problem rears it's head almost immediately.