netdev - Re: [RFC/RFT] mac80211: implement fq

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <87d1r5tgog.fsf@toke.dk>
Date:	Tue, 08 Mar 2016 11:19:59 +0100
From:	Toke Høiland-Jørgensen <toke@...e.dk>
To:	Michal Kazior <michal.kazior@...to.com>
Cc:	Dave Taht <dave.taht@...il.com>,
	linux-wireless <linux-wireless@...r.kernel.org>,
	Johannes Berg <johannes@...solutions.net>,
	"netdev\@vger.kernel.org" <netdev@...r.kernel.org>,
	Eric Dumazet <eric.dumazet@...il.com>,
	Emmanuel Grumbach <emmanuel.grumbach@...el.com>,
	Felix Fietkau <nbd@...nwrt.org>,
	Tim Shepard <shep@...m.mit.edu>
Subject: Re: [RFC/RFT] mac80211: implement fq_codel for software queuing

Michal Kazior <michal.kazior@...to.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