On Mon, Oct 06, 2008 at 11:21:38PM +0200, Eric Dumazet wrote:
quoted text
> 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 :).

quoted text
> 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.  

Neil

quoted text
>
>
>
>
>

-- 
/****************************************************
 * Neil Horman <nhorman@tuxdriver.com>
 * Software Engineer, Red Hat
 ****************************************************/
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html