Subject: Re: LL24: Weaken the PRN requirement

From: "s. goswami" <[email-masked]>
Date: Sat, 1 Mar 2003 18:45:52 -0500 (EST)

Well, that was just one example of an alternative algorithm
to PRN. There are many such algorithms, some are deterministic
versus the probabilistic algorithm inherent in PRN.

I am trying to say that leave the choice of selection
of the LLv4 address to the implementation. PRN can be the
Zeroconf suggested algorithm.

Subrata

On Fri, 28 Feb 2003, Robert Elz wrote:

>     Date:        Thu, 27 Feb 2003 08:43:15 -0800
>     From:        "Subrata Goswami" <[email-masked]>
>     Message-ID:  <004b01c2de7f$537da030$1bc0140a@SGOSWAMIPCL>
>
>   | Actually I am trying to say that if there is a way for a LL nodes to
>   | determine the  other LL nodes' LLv4 addresses, then it does not need
>   | to use the PRN.
>
> Even given that there was a way, this doesn't work, as we want 20 or 30
> (or 200 or 300) nodes all running the algorithm at the same time to start
> at (mostly) different values - if they all somehow just knew what LL
> addresses were assigned currently, and just picked some unallocated one
> algorithmically, then they're all likely to pick the same one (given that
> most of them will be running the same code on the same kind of processor).
>
> When that happens, at most one of them can succeed to obtain that address,
> after which they all have to start again, now knowing (perhaps) one more
> address that has been allocated, and all allocating the next one in their
> sequence.
>
> This just doesn't work.
>
> What's more ..
>
>   | An alternative algorithm is provided below - although it is somewhat
>   | extreme it would work.
>
> Work in the sense that it would find out what is in use, currently,
> perhaps yes.   Work in that the network would survive such an attack
> I doubt ...  Up to 64K broadcast packets from every host as it starts
> is not something that you'd want to see happening on your net.
>
> Using random numbers avoids these problems (given a big enough range,
> which we have here).   It is a common technique, and works well.
> What's more, it is enormously cheaper for the node, and the net, than
> attempting to find everything that is allocated.   There is no reason
> to even allow different methods (except perhaps, for real random numbers
> instead of PRNs).
>
> kre
>

---

From: Robert Elz <[email-masked]>
Date: Sun, 02 Mar 2003 20:10:34 +0700

Date:        Sat, 1 Mar 2003 18:45:52 -0500 (EST)
    From:        "s. goswami" <[email-masked]>
    Message-ID:  <[email-masked]>

  | There are many such algorithms, some are deterministic
  | versus the probabilistic algorithm inherent in PRN.

The problem is that any deterministic algorithm will, in some
environments, result in hundreds of nodes running the exact same
thing, at the same time, and producing the exact same answers.

That produces a mess, which just doesn't work (following the
rules of the draft, no nodes would ever get a LL address that
way, as they'd all see the other nodes' attempts abandon their
own, and move on, in step, to the next chocie).

kre

---

From: "Subrata Goswami" <[email-masked]>
Date: Mon, 3 Mar 2003 09:50:08 -0800

No, deterministic algorithms can produce unique LLv4 addresses for each
node.
In a deterministic algorithm, every not does not need to produce the
same
output - only the algorithm is same, the input to the algorithm are
different
for each node.

"..no nodes would ever get a LL address that way, as they'd all see the
other 
nodes' attempts abandon "

On this I would say, it is not relevant. See the first paragraph.

".. result in hundreds of nodes running .."

Are LLv4 networks expected to be hundreds of nodes large ?

Subrata

> -----Original Message-----
> From: Robert Elz [mailto:[email-masked]] 
> Sent: Sunday, March 02, 2003 5:11 AM
> To: s. goswami
> Cc: [email-masked]
> Subject: Re: LL24: Weaken the PRN requirement 
> 
> 
>     Message-ID:  
> <[email-masked]>
> 
> environments, result in hundreds of nodes running the exact 
> same thing, at the same time, and producing the exact same answers.
> 
> way, as they'd all see the other nodes' attempts abandon 
> their own, and move on, in step, to the next chocie).
> 
> kre
>

---

From: Ted Lemon <[email-masked]>
Date: Mon, 3 Mar 2003 14:16:12 -0600

A pseudo-random number generator is deterministic.   If you use a seed 
that is unique to a particular device, that device will get the same 
address every time, unless some other device's seed is the same, in 
which case they will fight over it and the newcomer will lose.

The problem we are arguing about here is not whether or not the 
algorithm is deterministic, but how likely a collision is, how likely a 
second collision is after a first collision, and whether the algorithm 
actually hits all 65534 possible addresses.   There are PRNGs that have 
this quality, and there are PRNGs that do not.

So, consider these two algorithms: algorithm 1 is a perfect 16-bit 
PRNG, seeded with the two least significant bytes of the MAC address of 
the device (we'll call this 2lsbmac).   Algorithm 2 just takes 2lsbmac 
and uses it as the two least significant bytes of the first IP address 
it tries.   If it gets a collision, it increments the address by one, 
and tries again.

So if you have two nodes on the network that use algorithm 1, both of 
which get the same value for 2lsbmac, then the first one to connect 
will get the first IP address it tries for.   The second to connect 
will get the next IP address in the sequence that algorithm 1 produces. 
   Now if a third device connects to the network with the same value for 
2lsbmac, it will try the IP address of the first station, then the IP 
address of the second station, and then it will try a third IP address 
which has not yet been taken, and acquire that.

This is precisely the same behavior that we get with algorithm 2 - the 
only difference is that the addresses in algorithm 1 will look "random" 
to a casual observer.   But in the case of three stations with three 
different values for 2lsbmac, both algorithms will produce 
random-seeming addresses.

Now consider a third algorithm.   This algorithm uses a perfect 32-bit 
PRNG seeded with 4lsbmac.   The likelihood of a clash with 4lsbmac is 
much less than a clash with 2lsbmac - probably not 64k times less 
likely, but certainly significantly less likely.   The algorithm simply 
takes the two least significant bytes of the output of the PRNG and 
uses those to generate an IP address.   This algorithm has the same 
probability of producing an initial collision as the other two.   
However, the chances that the second try will also produce a collision 
are much lower, because there are 16 extra bits of data being fed into 
the PRNG.

If you use a *bad* PRNG in your algorithm, your likelihood of 
collisions will be quite high even if it's a 32-bit algorithm - there 
are lots of bad PRNGs out there that don't produce a smooth 
distribution in their output, and indeed don't even hit most possible 
output values.   A bad PRNG is probably worse than just adding one.   
So if this draft is going to specify an algorithm, it should probably 
specifically say what the algorithm is; otherwise we will probably wind 
up seeing a lot of implementations that do a really bad job of 
collision avoidance.   I am not sure this will matter on the average 
network, but it might be a bummer for the poor bastard who just happens 
to wind up with set of nodes that happen to have seed values that 
interact badly.

So if you choose the wrong PRNG-based algorithm, it's no better than 
just incrementing the IP address by one.   However, if you use a good 
algorithm from the start, it _is_ better.

---

From: "Subrata Goswami" <[email-masked]>
Date: Tue, 4 Mar 2003 08:27:42 -0800

Ted, that certainly is a good analysis of the issue. The draft SHOULD
certainly
suggest a good PRNG algorithm, at the same time it should be flexible
enough
to include future algorithms. 

On a general note, the draft as it is now does not really say  much more
than the
following:

i)  169.254/16 must not be routed
ii) how LLv4 addresses should be chosen.

Subrata

> From: [email-masked]
> [mailto:[email-masked]] On Behalf Of Ted Lemon
> Sent: Monday, March 03, 2003 12:16 PM
> To: Subrata Goswami
> Cc: 'Robert Elz'; [email-masked]