Re: [RFC v2] RoCE v2.0 Entropy - IPv6 Flow Label and UDP Source Port

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On 2/14/2020 10:23 PM, Mark Zhang wrote:
On 2/13/2020 11:41 PM, Jason Gunthorpe wrote:
On Thu, Feb 13, 2020 at 10:26:09AM -0500, Tom Talpey wrote:

If both src & dst ports are in the high value range you loss those
hash bits in the masking.
If src & dst port are both 0xE000, your masked hash equals 0. You'll
get the same hash if both ports are equal 0xF000.

Sure, but this is because it's a 20-bit hash of a 32-bit object. There
will always be collisions, this is just one example. My concern is the
statistical spread of the results. I argue it's not changed by the
proposed bit-folding, possibly even damaged.

I've always thought that 'folding' by modulo results in an abnormal
statistical distribution

The point here is not collisions but to have a hash distribution which
is generally uniform for the input space.

Alex, it would be good to make a quick program to measure the
uniformity of the distribution..


Hi,

I did some tests with a quick program (hope it's not buggy...), seems the hash without "folding" has a better distribution than hash with fold. The "hash quality" is reflected by the "total_access"[1] below.

I tested only with cma_dport from 18515 (ib_write_bw default) to 18524. I can do more tests if required, for example use multiple cma_dport in one statistic.


[1] https://stackoverflow.com/questions/24729730/measuring-a-hash-functions-quality-for-use-with-maps-assosiative-arrays

$ ./a

max: Say for slot x there are tb[x] items, then 'max = max(tb[x])'; Lower is better; min: Say for slot x there are tb[x] items, then 'min = min(tb[x])'; Likely min is always 0 total_access: The sum of all 'accesses' (for each slot: accesses=n*(n+1)/2); Lower is better
n[X]: How many slots that has X items

cm source port range [32768, 65534], dest port 18515:
Hash with folding:
     flow_label: max 2 min 0 total_access 32766  n[1] = 32514 n[2] = 126
    udp_sport: max 10 min 0 total_access 51740  n[1] = 4420  n[2] = 4670  n[3] = 3112  n[4] = 1433  n[5] = 535   n[6] = 163   n[7] = 31 n[8] = 5     n[9] = 2     n[10] = 1
Hash without folding:
     flow_label: max 1 min 0 total_access 32766  n[1] = 32766
    udp_sport: max 4 min 0 total_access 48618   n[1] = 532   n[2] = 7926  n[3] = 530   n[4] = 3698


cm source port range [32768, 65534], dest port 18516:
Hash with folding:
    flow_label: max 3 min 0 total_access 32774  n[1] = 31214 n[2] = 770   n[3] = 4     udp_sport: max 8 min 0 total_access 50808   n[1] = 4406  n[2] = 4873  n[3] = 3157  n[4] = 1413  n[5] = 509   n[6] = 129   n[7] = 20 n[8] = 4
Hash without folding:
     flow_label: max 1 min 0 total_access 32766  n[1] = 32766
     udp_sport: max 2 min 1 total_access 32766   n[1] = 2     n[2] = 16382


cm source port range [32768, 65534], dest port 18517:
Hash with folding:
     flow_label: max 2 min 0 total_access 32766  n[1] = 32250 n[2] = 258
    udp_sport: max 10 min 0 total_access 54916  n[1] = 4536  n[2] = 4170  n[3] = 2817  n[4] = 1445  n[5] = 622   n[6] = 275   n[7] = 94 n[8] = 22    n[9] = 5     n[10] = 2
Hash without folding:
     flow_label: max 1 min 0 total_access 32766  n[1] = 32766
    udp_sport: max 3 min 1 total_access 38402   n[1] = 2820  n[2] = 10746 n[3] = 2818


cm source port range [32768, 65534], dest port 18518:
Hash with folding:
     flow_label: max 2 min 0 total_access 32766  n[1] = 32066 n[2] = 350
    udp_sport: max 8 min 0 total_access 50018   n[1] = 4435  n[2] = 4970  n[3] = 3294  n[4] = 1376  n[5] = 465   n[6] = 92    n[7] = 16 n[8] = 2
Hash without folding:
     flow_label: max 1 min 0 total_access 32766  n[1] = 32766
     udp_sport: max 2 min 1 total_access 32766   n[1] = 2     n[2] = 16382


cm source port range [32768, 65534], dest port 18519:
Hash with folding:
    flow_label: max 3 min 0 total_access 32774  n[1] = 31816 n[2] = 469   n[3] = 4     udp_sport: max 8 min 0 total_access 51462   n[1] = 4414  n[2] = 4734  n[3] = 3088  n[4] = 1466  n[5] = 508   n[6] = 160   n[7] = 32 n[8] = 4
Hash without folding:
     flow_label: max 1 min 0 total_access 32766  n[1] = 32766
    udp_sport: max 4 min 0 total_access 45490   n[1] = 3662  n[2] = 6360  n[3] = 3660  n[4] = 1351


cm source port range [32768, 65534], dest port 18520:
Hash with folding:
    flow_label: max 6 min 0 total_access 34618  n[1] = 20349 n[2] = 5027  n[3] = 550   n[4] = 164   n[5] = 9     n[6] = 2     udp_sport: max 13 min 0 total_access 82542  n[1] = 549   n[2] = 1167  n[3] = 1635  n[4] = 1706  n[5] = 1341  n[6] = 836   n[7] = 483 n[8] = 223   n[9] = 87    n[10] = 27
Hash without folding:
     flow_label: max 1 min 0 total_access 32766  n[1] = 32766
     udp_sport: max 4 min 0 total_access 65530 n[3] = 2     n[4] = 8190


cm source port range [32768, 65534], dest port 18521:
Hash with folding:
     flow_label: max 2 min 0 total_access 32766  n[1] = 31924 n[2] = 421
    udp_sport: max 9 min 0 total_access 51864   n[1] = 4505  n[2] = 4645  n[3] = 3038  n[4] = 1464  n[5] = 542   n[6] = 154   n[7] = 43 n[8] = 6     n[9] = 2
Hash without folding:
     flow_label: max 1 min 0 total_access 32766  n[1] = 32766
    udp_sport: max 3 min 1 total_access 32810   n[1] = 24    n[2] = 16338 n[3] = 22


cm source port range [32768, 65534], dest port 18522:
Hash with folding:
    flow_label: max 3 min 0 total_access 32768  n[1] = 32197 n[2] = 283   n[3] = 1     udp_sport: max 9 min 0 total_access 50850   n[1] = 4561  n[2] = 4756  n[3] = 3187  n[4] = 1452  n[5] = 453   n[6] = 137   n[7] = 29 n[8] = 2     n[9] = 2
Hash without folding:
     flow_label: max 1 min 0 total_access 32766  n[1] = 32766
     udp_sport: max 2 min 1 total_access 32766   n[1] = 2     n[2] = 16382


cm source port range [32768, 65534], dest port 18523:
Hash with folding:
     flow_label: max 2 min 0 total_access 32766  n[1] = 32514 n[2] = 126
    udp_sport: max 8 min 0 total_access 52208   n[1] = 4426  n[2] = 4609  n[3] = 3069  n[4] = 1435  n[5] = 533   n[6] = 180   n[7] = 50 n[8] = 10
Hash without folding:
     flow_label: max 1 min 0 total_access 32766  n[1] = 32766
    udp_sport: max 4 min 0 total_access 46062   n[1] = 3096  n[2] = 6640  n[3] = 3094  n[4] = 1777


cm source port range [32768, 65534], dest port 18524:
Hash with folding:
    flow_label: max 3 min 0 total_access 32774  n[1] = 31362 n[2] = 696   n[3] = 4     udp_sport: max 8 min 0 total_access 49490   n[1] = 4440  n[2] = 5148  n[3] = 3240  n[4] = 1413  n[5] = 394   n[6] = 97    n[7] = 14 n[8] = 1
Hash without folding:
     flow_label: max 1 min 0 total_access 32766  n[1] = 32766
     udp_sport: max 2 min 1 total_access 32766   n[1] = 2     n[2] = 16382



Another finding is, when cma_dport is multiple of 0x200 (i.e., 0x600, 0x800, ... 0xFE00), the hash distribution is tens of times worse then others. For examples when dport is 18431 and 18432:

cm source port range [32768, 65534], dest port 18431:
Hash with folding:
    flow_label: max 2 min 0 total_access 32766
    udp_sport:  max 8 min 0 total_access 50410
Hash without folding:
    flow_label: max 1 min 0 total_access 32766
    udp_sport:  max 4 min 0 total_access 48126

cm source port range [32768, 65534], dest port 18432(0x4800):
Hash with folding:
flow_label: max 133 min 0 total_access 1072938

udp_sport: max 203 min 0 total_access 2126644

Hash without folding:
flow_label: max 64 min 0 total_access 1048450

    udp_sport:  max 1024 min 0 total_access 16775170


Jason






[Index of Archives]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Photo]     [Yosemite News]     [Yosemite Photos]     [Linux Kernel]     [Linux SCSI]     [XFree86]

  Powered by Linux