Re: [PATCH] net: implement emergency route cache rebulds when gc_elasticity is exceeded

[Eric Dumazet <dada1@cosmosbay.com>]

Neil Horman a écrit :
> On Mon, Oct 06, 2008 at 11:21:38PM +0200, Eric Dumazet wrote:
>> Neil Horman a écrit :
>>> So, I've been playing with this patch, and I've not figured out eactly whats
>>> bothering me yet, since the math seems right, but something doesn't seem right
>>> about the outcome of this algorithm.  I've tested with my local system, and all
>>> works well, because the route cache is well behaved, and the sd value always
>>> works out to be very small, so ip_rt_gc_elasticity is used.  So I've been
>>> working through some scenarios by hand to see what this looks like using larger
>>> numbers.  If i assume ip_rt_gc_interval is 60, and rt_hash_log is 17, my sample
>>> count here is 7864320 samples per run.  If within that sample 393216 (about 4%)
>>> of the buckets have one entry on the chain, and all the rest are zeros, my hand
>>> calculations result in a standard deviation of approximately 140 and an average
>>> of .4.  That imples that in that sample set any one chain could be almost 500
>>> entires long before it triggered a cache rebuld.  Does that seem reasonable?
>>>
>> if rt_hash_log is 17, and interval is 60, then you should scan (60 << 
>> 17)/300 slots. That's 26214 slots. (ie 20% of the 2^17 slots)
>>
>> I have no idea how you can have sd = 140, even if scaled by (1 << 3)
>> with slots being empty or with one entry only...
>>
> I don't either, that was my concern :).
> 
>> If 4% of your slots have one element, then average length is 0.04 :)
>>
> Yes, and the average worked out properly, which is why I was concerned.
> 
> If you take an even simpler case, like you state above (I admit I miseed the
> /300 part of the sample, but no matter).
> 
> samples = 26214
> Assume each sample has a chain length of 1
> 
> sum = 26214 * (1 << 3) = 209712
> sum2 = sum * sum = s09712 * 209712 = 43979122944
> avg = sum / samples = 209712 / 26214 = 8 (correct)
> sd = sqrt(sum2 / samples - avg*avg) = sqrt(43979122944/26214 - 64) = 1295
> sd >> 3 = 1295.23 >> 3 = 161
> 
> 
> Clearly, given the assumption that every chain in the sample set has 1 entry,
> giving us an average of one, the traditional method of computing standard
> deviation should have yielded an sd of 0 exactly, since every sample was
> precisely the average. However, the math above gives us something significantly
> larger.  I'm hoping I missed something, but I don't think I have.  
> 

Famous last sentence ;)

You made some errors in your hand calculations.
sum2 is the sum of squares. Its not sum * sum.

If all slots have one entry, all "lengths" are (1<<3), 
and their 'square scaled by 6' is (1 << 6) . So sum2 = 26214 * (1 << 6) = 1677696
avg = sum / samples = 209712 / 26214 = (1 << 3)
sd = sqrt(sum2 / samples - avg*avg) = sqrt(64 - 64) = 0 (this is what we expected)

Now if you have 4 % of slots with one entry, and 96 % that are empty,
you should have 
/* real maths */
avg = 0.04
sd = sqrt(0.04 - 0.04*0.04) = sqrt(0.0384) = 0.195959
avg + 4*sd = 0.82

/* fixed point math */
sum = 0.04 * 26214 * (1<<3) = 1048 * (1<<3) = 8384 
sum2 = 1048 * (1 << 6) = 67072
avg << 3 = 8384/26214 = 0   (with 3 bits for fractional part, we do have rounding error)
sd << 3 = sqrt(67072/26214 - 0) = 1
(avg + 4*sd) << 3 = 4  -> final result is 4>>3 = 0 (expected)

Now if 50% of slots have one entry, we get :
/* real maths */
avg = 0.5
sd = sqrt(0.5 - 0.5*0.5) = sqrt(0.25) = 0.5
avg + 4*sd = 2.5

/* fixed point math */
sum = 0.5 * 26214 * (1<<3) = 104856
sum2 = 13107 * (1<<6) = 838848
avg << 3 = 104856/26214 = 4
sd << 3 = sqrt(838848/26214 - 4*4) = sqrt(32 - 16) = 4 
(avg + 4*sd) << 3 = 20  -> final result is 20>>3 = 2 (expected)


Hope this helps