Re: [RFC/RFT] mac80211: implement fq_codel for software queuing

["Toke Høiland-Jørgensen" <toke@toke.dk>]

Michal Kazior <michal.kazior@tieto.com> writes:

>> With large values for flows_cnt, fq, dominates, for small values, aqm
>> does. We did quite a lot of testing at 16 and 32 queues in the early
>> days, with pretty good results, except when we didn't. Cake went whole
>> hog with an 8 way set associative hash leading to "near perfect" fq,
>> which, at the cost of more cpu overhead, could cut the number of
>> queues down by a lot, also. Eric did "perfect" fq with sch_fq...
>
> Out of curiosity - do you have any numbers to compare against
> fq_codel? Like hash collision probability vs number of active flows?

Basically, the analytical expression for hash collisions is fairly
straight forward (though I can't take credit for coming up with it
myself):

Given N bins with M items being hashed into them by a hypothetical
perfectly uniform hash, you get:

  Expected number of bins with x items = N * (1/N)^x * (1 - 1/N) ^ (M - x) * C(M, x)

where C(M, x) is the combinatorial function = M! / (x! * (M-x)!).

By expanding this expression for x=1 and dividing by M, you get the
probability that one of your M items is in its own bin. Subtract this
from 1 and you get the collision probability.

I have a neat spreadsheet to compute this for arbitrary numbers; but for
a 1024-bin FQ-Codel this gives a collision probability of just under 1%
for 10 flows, and just over 9% for 100 flows. This is not too far off
from actual values in a real-world hashing function.

Now, to add to the confusion, you also have to take into account that an
active flow (from an end-to-end perspective) does not necessarily
translate into an active flow from the queue perspective. And that in
fact the number of active flows in a router can be significantly less
than the number of active end-to-end flows, and scales sub-linearly...
There has been at least one paper demonstrating this, but right now I
can't recall who wrote it.

-Toke