Subject: Re: random ip_id must be configurable
To: Jun-ichiro itojun Hagino <email@example.com>
From: David Laight <firstname.lastname@example.org>
Date: 09/13/2003 00:24:25
On Fri, Sep 12, 2003 at 05:29:58PM -0400, Niels Provos wrote:
> On Fri, Sep 12, 2003 at 11:13:50AM +0100, David Laight wrote:
> > You need to:
> > a) read the code
> > b) understand what it it doing
> That is a good suggestion. So, please let me provide you with my
> own understanding of this source code:
> Out of every 15-bit block you select 30,000 non-repeating numbers.
> Afterwards, we switch to a new number space out of which we select
> another 30,000 non-repeating numbers.
> So, the minimal distance is at least 30,000 IDs before you can expect
> any collision.
Nearly (remember Itojun said that 36000 was twice RU_MAX though).
Look closer and you see that 0 to 3 values are discared from the LCG
before the value that is used as m in the final k ** m mod n sum.
These are counted into the 30,000 - so each id uses 2.5 values from
the LCG and it switches to a new number space at 30000/25 = 12000.
> > RU_MAX itself is 30000, the worst case repeat is after 7500 numbers.
> > The average block contains 12000 numbers, so after that you start
> > getting a chance of a collision with the block before it.
> > On average 150 numbers into a block there is a 50% chance of a repeat
> > in the last 150 numbers of the block before the last.
> > Practically you have to assume repeats after 12000 numbers.
> I have no idea where you are getting these numbers from.
The 150 is from the following:
Take k different numbers from n, then a random number from the same n.
The chance that the random one is different from the k is (n - k)/n
The chance that k random ones are different is ((n - k)/n)**k
For n = 32768 and k 150 this is about 1/2.
(this isn't quite the correct sum, but is close enough and easier to
> Ps: Obviously, I am biased in this discussion, as Itojun is my
> declared open-source hero.
Try a different hero :-)
David Laight: email@example.com