On Wed, 1 Oct 2008, Neil Horman wrote:

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

						-Bill
--
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