On Sunday 2010-10-24 21:11, Eric Dumazet wrote:
>Le dimanche 24 octobre 2010 Ã 20:25 +0200, Florian Westphal a Ãcrit :
>
>> I'd imagine that the result of ((hash * total) >> 32) is (almost)
>> always zero, especially if total is small (which it is usually).
>
>Absolutely not. total is a 32bit number, using full range.
>
>> Did you test that this change does not affect distribution average?
>
>That would be shocking actually, given we use jhash()
>
>I did same tricks in various parts of network stack in the past, and its
>fine.
I spent the afternoon raking on the impact on the distribution that
using multiplication here would have. Intriguing concourse.
(I looked at Jenkins3, so there is a little gap to what's in the
kernel.) Anyhow, the frequency of Jenkins3 output values (OV) being hit
is:
1591633245x 0
1568275918x 1
784435879x 2
265277962x 3
68188245x 4
14213782x 5
2499352x 6
383550x 7
52243x 8
6340x 9
699x 10
74x 11
5x 12
1x 13
To be read as: one OV is reachable by 13 input values; 5 OVs are each
reachable by 12 input values (IV) (i.e. a group of 60 IV lead to only 5
OV), etc.
With ct's input domain, i.e. ipv4saddr^ipv4daddr, a 32-bit quantity,
~1.59G OVs are never reachable/obtainable ("holes") no matter which IVs
are chosen. The more these 1.59G points agglomerate together, the higher
the chance that some queue will not be used (with the multiplication
approach), of course.
If the 1.59G holes are uniformly distributed across the 32-bit space, a
CDF-like plot would output a straight line. Alternatively, one can
calculate the difference instead for visual output:
http://picpaste.de/jenkins3.png
You can surely agree with me that this looks very much like at least
one queue will be at a disadvantage (getting less packets).
And indeed, with total_queues=4 I get a packet distribution of
24.41404 25.58534 25.00025 25.00037
percent. With more queues, I suspect the variance will go up.
===
Bottom line: modulus is resistant to hole agglomeration, and only
problematic with certain patterns of uniform hole distribution
(which in
turn would be a sign that the hash function is bad).
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
