Michal Kazior <michal.kaz...@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 -- To unsubscribe from this list: send the line "unsubscribe linux-wireless" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
