Subject: RE: Discussion: client identifier [collisions]

From: Bernie Volz <[email-masked]>
Date: Sat, 14 Oct 2000 20:15:24 -0400

>Ultimately, I think we only care about UUID collisions to the extent that
>they result in address collisions, right? Assuming that we have a mechanism
>to detect address collisions, does this solve the problem?

I don't think so. Duplicate Address Detection at the link layer would likely
act to avoid two clients using the same addresses if they use the same UUID.
But weird events would happen (something like the following):
	Client A gets addresses
	Client B gets same addresses, DAD finds they are in use.
	Client B gets new addresses from server.
	Client A renews addesses.
	Client A gets same addresses, DAD finds they are in use.
	Client A gets new addresses from server.
	<Client A/B keep switching addresses ...>

If duplicate UUID's are rare and if we assume that lease times are
reasonable, perhaps the above isn't that bad? And, perhaps there is some
value in considering having a client generate a new UUID if the above
situation happens several times in a row?

>I'm not sure I'm ready to give up yet.

Good. I agree it would be useful to have a UUID.

- Bernie Volz

-----Original Message-----
From: Bernard Aboba [mailto:[email-masked]]
Sent: Saturday, October 14, 2000 1:54 AM
To: DHCPv6 discussion list
Subject: RE: Discussion: client identifier [collisions]

>...while I think it is relatively difficult to define a universally unique
>identifier, I believe we can define something that is relatively close,
then
>the collision detection mechanism (which I believe is a MUCH easier
problem)
>can be specified, if not algorithmically, at least by its characteristics

Ultimately, I think we only care about UUID collisions to the extent that
they result in address collisions, right? Assuming that we have a mechanism
to
detect address collisions, does this solve the problem?

> 3) The more we talk about this, the more I think this is too big
> a problem to resolve in the short time we have to get the DHCPv6
> draft out.  Unless we can find some prior art in this area --
> anyone located any?
>

I'm not sure I'm ready to give up yet.

---

From: Bernie Volz <[email-masked]>
Date: Mon, 16 Oct 2000 13:52:49 -0400

How about we consider a UUID timestamp or some such thing (either separately
or as a part of the UUID)?

Here's what happens ... when a client boots and no UUID exists, it first
(solicits and) awaits an ADVERTISE from a DHCP Server. In this ADVERTISE we
have a server time stamp or UUID generation key. When the client receives
this (unicast) ADVERTISE, it then generates a UUID consisting of (a)
hardware information of some type (either NIC or manufacturer/serial, etc),
(b) the timestamp, and (c) a random number. It then saves this UUID and uses
it 'forever' (it if has no stable storage, then it would generate a new UUID
at each boot).

Assuming the timestamp is at least 32-bits and the random number is also at
least 32-bits, and the hardware information is also 48-bits, we should have
an extremely small probility of a collison. The only issue is if there are
multiple servers and they happen to send out the same timestamp in
ADVERTISEs. But, if the ADVERTISE that is used is for the server that will
be contacted, then you're at least assured that for that server there will
never be two clients with the same UUID.

- Bernie Volz

-----Original Message-----
From: Barr Hibbs [mailto:[email-masked]]
Sent: Monday, October 16, 2000 1:17 PM
To: DHCPv6 discussion list
Subject: RE: Discussion: client identifier [collisions]

> From: Jim Bound
> Sent: Sunday, October 15, 2000 9:13 PM
>
>
> Ralph,
>
> prefix + link-local won't work now regardless of the nic issue.
> The reason is the security benefits from UUIDs.  So I forget that.
>
> OUI - I just checked the IEEE page and that won't work cause you have to
> buy it and order it and whatever and that is not good as we want nodes
> to be able to have multiple IAs if they desire, and this will put just
> to much administrative complexity on the end user site.
>
> But we do need to nail down the UUID.  Maybe Barr's idea will work for
> version 1?
>
>

...wow!  this is all very interesting, but seems to have strayed from my
original point, which was meant to cover the following case:

  +------------+     +-----+
  |   Host A   |     |     |
  | Client ID: +-----+  N  |
  |    1023    |     |  E  |     +========+
  +------------+     |  T  |     |  DHCP  |
                     |  W  +-----+ Server |
  +------------+     |  O  |     |        |
  |   Host B   |     |  R  |     +========+
  | Client ID: +-----+  K  |
  |    1023    |     |     |
  +------------+     +-----+

Thus my two questions:
(1) can we reliably detect that Client ID 1023 has been chosen by DIFFERENT
hosts?
(2) can we SUGGEST ways to resolve this collision that don't create other
problems?

(1) arises because I'm not convinced that it is possible to guarantee
uniqueness of any identifier, so, better to be prepared to deal with its
occurrence

(2) arises because of similar problems with the DHCPv4 client identifier

--Barr Hibbs

---

From: Bernie Volz <[email-masked]>
Date: Mon, 16 Oct 2000 13:56:54 -0400

Oh ... we could also have the SOLICIT request a UUID from a server and have
the server return the UUID in the ADVERTISE. And, the UUID would have some
server identifier included in it - so that hopefully no two servers ever
have the same identifier. This could be something like the server's hardware
address or some unique identifier. At least that makes the problem more
manageable - keeping the server identifiers unique. The only other problem
of course is if a server looses its stable storage (since it no longer has a
record of the UUIDs given out or the 'next UUID number').

- Bernei Volz

-----Original Message-----
From: Bernie Volz 
Sent: Monday, October 16, 2000 1:53 PM
To: [email-masked]'
Subject: RE: Discussion: client identifier [collisions]

- Bernie Volz

-----Original Message-----
From: Barr Hibbs [mailto:[email-masked]]
Sent: Monday, October 16, 2000 1:17 PM
To: DHCPv6 discussion list
Subject: RE: Discussion: client identifier [collisions]

  +------------+     +-----+
  |   Host A   |     |     |
  | Client ID: +-----+  N  |

Thus my two questions:

--Barr Hibbs

---

From: Bernie Volz <[email-masked]>
Date: Mon, 16 Oct 2000 15:16:42 -0400

>So, let's come back to the earlier scenario, where nodes A and B are 
>sharing IA (123, 1).  We need to define the server behavior in the case 
>where and IA moves from one subnet to another.  This is an area of some 
>unclarity in DHCPv4.  If we make an assumption that all UUIDs or IA 
>identifiers are unique, do we want to specify that a DHCP server MUST, 
>SHOULD or MAY release any previously assigned addresses when an IA moves to

>a new subnet?  Perhaps there's another alternative - the server adds some 
>more addresses to the IA (leaving the old [presumably now unusable] 
>addresses in the IA)?

I personally have never been confortable with removing the addresses on
other subnets. For multi-homed hosts, how do you know that those addresses
aren't in use? I would recommend that the server keep the addresses on file
until the lifetimes expire. You could easily have:

     UUID 123
     +--------+          /----\
     |        |         /      \
     | Host A +-------+ Subnet X +-\
     |        |         \      /    \---\  +-------------+
     +---+----+          \----/          \-+             |
         |                                 | DHCP server |
         |               /----\          /-+             |
         |              /      \    /---/  +-------------+
         +------------+ Subnet Y +-/
                        \      /
                         \----/

Perhaps we'd assume that in this case the two IAs would be different, but
I'm not sure why that has to be a requirement.

- Bernie Volz

-----Original Message-----
From: Ralph Droms [mailto:[email-masked]]
Sent: Sunday, October 15, 2000 3:12 PM
To: DHCPv6 discussion list
Subject: RE: Discussion: client identifier [collisions]

Executive summary:  There are two types of name collisions possible in the 
address model we've been discussing: collisions between IA identifiers and 
collisions between UUIDs.  The two types of collisions may have different 
outcomes.  Collisions between IA identifiers from hosts on different 
subnets may cause duplicate address assignment...

=====

At 02:08 PM 10/13/00 -0700, Bernard Aboba wrote:
>In terms of collisions, I think that we only care about hosts with
>identical UUIDs on the same LAN.

Bernard - your "only" in the sentence prompted me to do a little thinking 
about name collisions...

I think we need to clarify exactly what we mean by a collision - a 
collision between UUIDs will have one kind of impact on client-server 
operations while a collision between IA identifiers will have a different 
kind of impact.

I'm working here from our current working definition of an IA identifier as 
(UUID, binding-id), where UUID is a unique identifier for a host and a 
binding-id is an opaque cookie used to differentiate between IAs associated 
with one host.  In other words, IAs (123, 1), (123, 2) and (456, 1) all 
represent different IAs, and the first two IAs come from the same host.

So, suppose we have a network like this:

     UUID 123
     +--------+          /----\
     |        |         /      \
     | Host A +-------+ Subnet X +-\
     |        |         \      /    \---\  +-------------+
     +--------+          \----/          \-+             |
                                           | DHCP server |
     +--------+          /----\          /-+             |
     |        |         /      \    /---/  +-------------+
     | Host B +-------+ Subnet Y +-/
     |        |         \      /
     +--------+          \----/
     UUID 123

where hosts A and B have both chosen to use the same UUID.  Now suppose 
hosts A and B ask for IAs (123, 1) and (123,2).  The DHCP server will 
assign some address from subnet X (IP.X) to (123,1) and some address from 
subnet Y (IP.Y) to (123,2).  The server will treat the two IAs as 
independent.  For the purposes of assigning other parameters, the server 
may treat the two IAs as being associated with a dual-homed host.  So, in 
this scenario I see that the DHCP server won't make any incorrect IP 
address assignments, but may make some errors in assigning other parameters 
because the server has reason to believe the two IAs are from the same host.

Now, suppose hosts A and B both contact the DHCP server for addresses for 
the same IA, (123, 1) and A goes first.  The DHCP server will assign IP.X 
to the IA and return that IA to A.  Later, when B contacts the DHCP server, 
the server will assign IP.Y to the IA and, presumably, release IP.X from 
the IA (more about this later!).  When A contacts the server to extend the 
assignment for (123,1), the server will assign an address from subnet X 
(perhaps IP.X again).  The net effect is that A and B each get an 
appropriate address, while the DHCP server bounces the IA back and forth 
between IP.X and IP.Y.  No specific problems, yet, but it sure doesn't feel 
right to have the IA out of sync with some of the address assignments.

Well, perhaps there is a potential problem.  In this diagram:

     UUID 123
     +--------+          /----\
     |        |         /      \
     | Host A +-------+ Subnet X +-\
     |        |         \      /    \---\  +-------------+
     +--------+          \----/          \-+             |
                                           | DHCP server |
     +--------+          /----\          /-+             |
     |        |         /      \    /---/  +-------------+
     | Host B +-------+ Subnet Y +-/
     |        |      ---\      //
     +--------+     /    \----/
     UUID 123      /
                  /
     +--------+  /
     |        | /
     | Host C +/
     |        |
     +--------+
     UUID 456

suppose hosts A and B, sharing IA (123, 1) have been assigned IP.X and 
IP.y.  Now, host C contacts the DHCP server for an address for IA (456, 
1).  If the DHCP server has IP.X assigned to (123, 1), presumably IP.Y is 
free and may be assigned to host C.  Of course, host B is still using IP.Y, 
so there's a duplicate assignment of IP.Y to both B and C (more about this 
later, as well).

So, let's come back to the earlier scenario, where nodes A and B are 
sharing IA (123, 1).  We need to define the server behavior in the case 
where and IA moves from one subnet to another.  This is an area of some 
unclarity in DHCPv4.  If we make an assumption that all UUIDs or IA 
identifiers are unique, do we want to specify that a DHCP server MUST, 
SHOULD or MAY release any previously assigned addresses when an IA moves to 
a new subnet?  Perhaps there's another alternative - the server adds some 
more addresses to the IA (leaving the old [presumably now unusable] 
addresses in the IA)?

At the end of the second example of shared IAs, I noted the case in which 
IP.Y might be assigned to both nodes B and C.  Will the DHCP server 
(through ping or some other remote DAD mechanism) or the nodes themselves 
(doing DAD) notice the problem?  Given that the server or the nodes have 
noticed the problem, is there anything the server or the nodes or an 
administrator can do about it?

- Ralph

---

From: Ralph Droms <[email-masked]>
Date: Mon, 16 Oct 2000 15:43:29 -0400

At 03:16 PM 10/16/00 -0400, Bernie Volz wrote:
> >If we make an assumption that all UUIDs or IA
> >a new subnet?

I think this is exactly the situation Ted talked about in one of the first 
messages in this thread (9/6):

>Having one identity association per network
>interface avoids this problem - if you are multiply attached, you'll
>have multiple identity associations, and if you're singly attached, I
>can nuke your old lease when you change networks.

I agree with Ted...

- Ralph