[Cake] CAKE set-associative hashing

[Cake] CAKE set-associative hashing

[Adrian Popescu]

[-- Attachment #1: Type: text/plain, Size: 623 bytes --]

The set-associative hashing attempts to allocate one of 7 other queues when
the default queue it hashes to is reserved for another flow. The collision
is accepted for the default queue when the other 7 queues are in use.
Packets will get queued on the default queue where that flow ended up after
hashing. The tag for that index is overwritten for every packet which gets
hashed on this flow which accepted the collisions.

What happens when one of the other 7 queues becomes free and the first of
the flows which accepted collisions gets allocated this other queue? Don't
we have a packet reordering problem in this case?

[-- Attachment #2: Type: text/html, Size: 721 bytes --]

Re: [Cake] CAKE set-associative hashing

[Jonathan Morton]

[-- Attachment #1: Type: text/plain, Size: 400 bytes --]

Yes, in the same way as is caused by SFQ's periodic hash perturbation.

However, in Cake this is a rare condition brought on by exceptional load;
it typically takes hundreds of bulk flows to get an unresolvable
collision.  The use of AQM also means that the extent of reordering is
reduced due to shorter average queues.  Most sane protocols, including
TCP-SACK, should cope fine.

- Jonathan Morton

[-- Attachment #2: Type: text/html, Size: 465 bytes --]

Re: [Cake] CAKE set-associative hashing

[Adrian Popescu]

[-- Attachment #1: Type: text/plain, Size: 700 bytes --]

Thank you Jonathan. I'm going over the code to learn more about CAKE. This
set-associative hashing seems to be pretty useful. I'll ask more questions
about the code as I try to understand it better.

On Sun, Oct 29, 2017 at 12:14 PM, Jonathan Morton <chromatix99@gmail.com>
wrote:

> Yes, in the same way as is caused by SFQ's periodic hash perturbation.
>
> However, in Cake this is a rare condition brought on by exceptional load;
> it typically takes hundreds of bulk flows to get an unresolvable
> collision.  The use of AQM also means that the extent of reordering is
> reduced due to shorter average queues.  Most sane protocols, including
> TCP-SACK, should cope fine.
>
> - Jonathan Morton
>

[-- Attachment #2: Type: text/html, Size: 1112 bytes --]

Re: [Cake] CAKE set-associative hashing

[Dave Taht]

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.

Re: [Cake] CAKE set-associative hashing

[Jonathan Morton]

[-- Attachment #1: Type: text/plain, Size: 591 bytes --]

In CPUs, 4-way is now common in first-level caches, 16-way at last-level.
It is a tradeoff between guaranteed hit latency (necessary in synchronous
hardware) and collision rate.  In software, average hit latency is usually
more relevant, and worst-case throughput otherwise.

IMHO, having a separate qdisc tree per hardware queue is the wrong design.
Better would be a single qdisc (or tree thereof) that can be drained
concurrently into all queues.  That currently seems to be easiest to
arrange by putting the qdiscs in userspace, but theoretically that need not
be so.

- Jonathan Morton

[-- Attachment #2: Type: text/html, Size: 656 bytes --]