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

[Eric Dumazet <dada1@cosmosbay.com>]

Bill Fink a écrit :
> On Wed, 1 Oct 2008, Neil Horman wrote:
> 
>> Hey all-
>> 	Since Eric mentioned the use of statistical analysis to determine if
>> hash chains were growing improperly, I thought I would take a stab at such an
>> approach.  I'm no statistics expert, but it would seem to me that simply
>> computing the standard deviation of all the non-zero chain lengths would give a
>> good guide point to determine if we needed to invalidate our hash table.  I've
>> written the below implementation.  I've not tested it (I'll be doing that here
>> shortly for the next few days), but I wanted to post it to get feedback from you
>> all on the subject.  The highlights are:
>>
>> 1) We add a counter to rt_hash_bucket structure to track the length of each
>> individual chain.  I realize this is sub-optimal, as it adds potentially lots of
>> memory to hash table as a whole (4 bytes * number of hash buckets).  I'm afraid
>> I've not come up with a better way to track that yet.  We also track the total
>> number of route entries and the number of non-zero length chains.  Lastly we
>> also maintain a global maximum chain length which defines the longest chain we
>> will tolerate in the route table.  This patch defines it as the mean chain
>> length plus one standard deviation.
> 
> I believe the general rule of thumb for something like this is at
> least two standard deviations.  For a normal distribution, one standard
> deviation covers about 68 % of the sample universe, while two standard
> deviations covers about 95 % (three standard deviations covers 99.73 %).
> See the Wikipedia entry:
> 
> 	http://en.wikipedia.org/wiki/Standard_deviation
> 

Thanks Bill for the pointer, this is the trick.

I believe we should target "4σ 99.993666% " case.

But we dont need to really compute Standard deviation at runtime, only find an (upper) approximation of it.

For elasticity=4 and 512*1024 samples (mean < 4), I guess 4σ can be approximated by 20 or something.

Thank you