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

[Tom Talpey <tom@talpey.com>]

[-- Attachment #1: Type: text/plain, Size: 12014 bytes --]

On 2/18/2020 9:16 AM, Tom Talpey wrote:
> On 2/15/2020 1:27 AM, Mark Zhang wrote:
>> 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
> 
> Good data! It certainly indicates an issue with the simple
> binary modulus for treuncating 32->20 bits. But the extremely
> narrow testing range limits the conclusions considerably:
> 
>  >> 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.
> 
> This hash is intended to provide entropy across the entire port
> range and we should evaluate it as such. At a minimum, the source
> port can vary much more widely, from Alex's original message it's
> 0xC000 - 0xFFFF.
> 
>> UDP source port selection must adhere IANA port allocation ranges. 
>> Thus we will
>> be using IANA recommendation for Ephemeral port range of: 49152-65535, 
>> or in
>> hex: 0xC000-0xFFFF.
> 
> I'm not certain what the range of the destination port might be, but
> as a Service ID, a good assumption is the full range of 0x1 - 0xBFFF.
> 
> Any chance you could scale up your test, to measure the original
> proposed hash across these broader ranges?
> 
>>   u32 hash = DstPort * SrcPort;
>>   hash ^= (hash >> 16);
>>   hash ^= (hash >> 8);
>>   AH_ATTR.GRH.flow_label = hash AND IB_GRH_FLOWLABEL_MASK;

I did an even quicker-and-dirtier test, with the attached. Both
the folding and non-folding methods display, to me, pretty much
the same behavior. And there's a fairly significant periodicity
with a doubling of the hash collision rate, every 8 or so buckets.

The "folding" version has higher spikes at these points than the
non-folding, in fact. As you mentioned, there are a few more "zero"
hashes, but that's expected, and not that different for both.

Assuming you agree with my C000-FFFF and 1-BFFF port ranges, there
are 800M possible permutations, and of course 1M hash buckets. So,
an 800:1 collision rate is expected. But the numbers range from
the mid-300's to several-1000's. That variance seems high to me.

I really think there needs to be a flatter spectrum, here. These
collisions can cause significant congestion effects at scale. I
suggested trying a CRC-20 of the 32-bit src<<16|dst, but it's going
to take me a little time to find that.


> Folding hash
> bucket  hits
> 0       3840
> 1       407
> 2       798
> 3       426
> 4       1137
> 5       409
> 6       711
> 7       372
> 8       1595
> 9       349
> 10      751
> 11      385
> 12      1164
> 13      375
> 14      747
> 15      406
> 16      1952
> 17      382
> 18      766
> 19      390
> 20      1139
> 21      372
> 22      792
> 23      419
> 24      1543
> 25      393
> 26      777
> 27      403
> 28      1123
> 29      356
> 30      773
> 31      363
> 32      2340
> 33      397
> 34      785
> 35      393
> 36      1154
> 37      415
> 38      744

Versus...

> Non-folding hash
> bucket  hits
> 0       4469
> 1       480
> 2       684
> 3       567
> 4       990
> 5       465
> 6       697
> 7       650
> 8       1279
> 9       453
> 10      671
> 11      556
> 12      989
> 13      499
> 14      653
> 15      812
> 16      1603
> 17      478
> 18      694
> 19      559
> 20      1015
> 21      506
> 22      675
> 23      659
> 24      1317
> 25      476
> 26      644
> 27      555
> 28      953
> 29      475
> 30      738
> 31      927
> 32      2047
> 33      456
> 34      726
> 35      537
> 36      952
> 37      472
> 38      665

Tom.

[-- Attachment #2: hashtest.c --]
[-- Type: text/plain, Size: 755 bytes --]

#include <stdio.h>

int data[1024 * 1024];

int main(int argc, char **argv)
{
        unsigned short src, dst;
        unsigned long hash;
        printf("%s hash\nbucket\thits\n", argc > 1 ? "Non-folding" : "Folding");
        for (src = 1; src < 0xBFFF; src++)
                for (dst = 0xC000; dst <= 0xFFFE; dst++) {
                        hash = src * dst;
                        if (argc > 1) {
                                hash ^= hash >> 16;
                                hash ^= hash >> 8;
                        }
                        hash &= 0xFFFFF;
                        data[hash]++;
                }
        int i;
        for (i = 0; i < 1024 * 1024; i++)
                printf("%d\t%d\n", i, data[i]);
        return 0;
}