Subject: Re: DC meeting: Discussion question #2,

From: Ralph Droms <[email-masked]>
Date: Thu, 18 Nov 1999 12:23:10 -0500 (EST)

(From Thomas Narten)
--------------------
Jim Bound <[email-masked]> writes:

> >Another simplification of this model is that the binding cache (which
> >deals with retransmitted client requests) is no longer needed, as all
> >requests are idempotent. In model B (below) the server (and client in
> >the case of reconfigures) needs to distinguish a first request from
> >subsequent retransmissions and respond appropriately.

> The binding cache in DHCPv6 is there regardless of the model because as
> DHCPv4, DHCPv6 needs to handle retransmission of requests.

> To verify the request is a retransmit so we keep a cache as an
> optimization to avoid a complete client database lookup.  We do not need
> this because of the model.  

That is not what I understand from the draft. The binding cache is
needed not just as an optimization, but for correctness. Specifically,
it is needed so that a server (in the case of Request messages) can
distinguish between an initial (i.e., "new") request and a
retransmission. Request messages are not idempotent in the current
draft due to the the model. If a client makes three requests for
addresses, does the server send back the same three answers, or is
each Request message treated as a separate request requiring a
different set of addresses returned? The document specifically says:

>   While processing the Request, the server MUST first determine whether
>   or not the Request is a retransmission of an earlier DHCP Request
>   from the same client.  This is done by comparing the transaction-ID
>   to all those transaction-IDs in the XID_TIMEOUT binding cache
>   received from the same client during the previous XID_TIMEOUT
>   seconds.  If the transaction-ID is the same as one received during
>   that time, the server MUST take the same action (e.g., retransmit
>   the same DHCP Reply to the client) as it did after processing the
>   previous DHCP Request with the same transaction-ID.

In contrast, in DHCPv4, requests are idempotent and there is no need
(for correctness) for the server to distinguish between
retransmissions and "new" requests. 

Thomas

---

From: Jim Bound <[email-masked]>
Date: Thu, 18 Nov 1999 21:07:00 -0500 (EST)

>different set of addresses returned? The document specifically says:

The purpose of the cache is first to distinguish btw retransmit and
request.  The issue of the model is pure serendipity.
But it is also an optimization to avoid a full database search at least
for XID_TIMEOUT.

Once that TIMEOUT happens the server will reply to the client with the
same information as we treat it as a new DHCPv6 Request so it is
idempotent.

Requests are idempotent in DHCPv6 by design, because we designed a
transaction-based protocol.  You MUST verify it is not a retransmit but
only for XID_TIMEOUT.  This is the norm for transaction based processing
since IBM invented it in 1979 with CICS as far as I am concerned. 
The DHCPv6 request could be reprocessed and an implementation can just
respond again.  But then we are violating the principles of transaction
based systems.  So we don't.

>retransmissions and "new" requests. 

So we built a different protocol!!! But DHCPv4 handles retransmits too.
But I don't agree with your statements about idempotency.                    

We put the above section in the spec as an optimization not because we
had to because the Request can't be idempotent.  You are making
assumptions about the draft but not backing it up with detail in your
response.  So I am not sure how to respond other than if we took this
optimization out the protocol would still work.  But we want the
optimization in the protocol spec.  If you disagree thats fine thats why
we are discussing it on the mailing list.

Any protocol that does not differentiate btw new messages and
retransmits is a bad protocol, it makes no sense to me to have the
processing take place if its a retransmit in the same manner as it would
with a new message in any protocol.  It may be we have a computer
science disagreement here on correct design and behavior. And in fact
the DHCPv6 protocol will act like you want once the XID_TIMEOUT timer
goes off.

thanks
/jim

---

From: Thomas Narten <[email-masked]>
Date: Fri, 19 Nov 1999 08:04:44 -0500 (EST)

Jim,

> request.

Agreed.

> The issue of the model is pure serendipity. But it is also an
> optimization to avoid a full database search at least for
> XID_TIMEOUT.

Disagree.

If the binding cache is just an optimization, then I should be able to
remove it and have the protocol work correctly.

But consider two request messages from a client requesting additional
addresses. If they are unrelated (i.e., the second is not a
retransmission but a different request), the server would respond with
different answers to the two requests. If the second message was a
retransmission, the server would need to respond to the retransmission
with exactly the same information as it responded to the first
message.

My understanding of what idempotent means is that if you reexecute the
same request multiple times, you get the right answer. But in the case
of requesting additional addresses, the answer you get very much
depends on what previous requests have already been processed. So it
is very important for the server to distinguish original requests from
retransmissions and process them differently.

Consider DHCPv4 as a comparison. No binding cache is needed because if
a client asks for an address from the server 3 times, it gets back the
same 3 answers. The server doesn't need to check whether a request is
new or a retransmission, it processes it in the same way and gives
back the proper answer. (It might want a cache as a performance
optimization, but it is not required for correctness.)

Thus, I assert that removal of the binding cache in DHCPv6 would
result in the server returning differnt answers than it would
otherwise. Hence, it is not just a performance optimization, it is
needed for correctness.

> same information as we treat it as a new DHCPv6 Request so it is

It seems to me that the addition of the transaction ID and the binding
cache is what makes the transaction idempotent. My point is that the
address allocation model makes the high-level request itself
non-idempotent. I agree that the cache takes care of the problem with
this model (but that it is required, not optional).

> with a new message in any protocol.

I don't agree with this as a blanket statement. Consider a time of day
server. The cost of looking up the time on most machines is trivial,
and the cost of reexecuting retransmitted requests is small. Having a
cache of recent response also has complexity and cost (e.g., requires
memory), and this cost is not necessarily lower than reexecuting a
retransmitted request.

Thomas

---

From: Jim Bound <[email-masked]>
Date: Fri, 19 Nov 1999 11:55:29 -0500 (EST)

Thomas,

>Disagree.

Do you disagree it optimizes retransmission?

Or do you disagree that I am telling you that we did not put this in
here because the protocol would not work?  Thats not what charlie and I
did..

>remove it and have the protocol work correctly.

It will work and I rechecked that last night.

>with exactly the same information as it responded to the first

Not true.  If we had no binding cache the server would return the same
information simply because it had the information stored on the
database.  If the client requested new information we did not give it
previously the server would provide new information.

>retransmissions and process them differently.

Agree on idempotent.  1 OR 1 does not change 1.  

If the client provides 3 address extensions and in the database the
server has given them 3 then 3 will be returned.

if the client asks for 4 addresses and in the database the server only
has 3 addresses and the client can have 4 addresses the server will
return the original 3 addresses and an additional address. 

But now we head into the area I was waiting to come up and the real
issue for this multiple addresses and I think we do have a bug in the
spec we did not fix since our holding pattern since minneapolis meeting.
but I will bring it up now but was hoping you would directly.

If the client requests 1 address now continuing the discussion I would
return the client one of the addresses I have already given it as a
server implementor.  But this is not clear in the spec and if I don't do
it (implement) this way the REQUEST would not be idempotent if I give
the client a new address.

That is why we need to do one of the following things as I see it in the
protocol:
  
  1.  Add a bit in the request that is a "pure" request for a brand 
      new address or addresses and addr extentions would follow.

  2.  The client must ask  for all its addresses back and an additional
      extension if it wants a new one.  This would be done by the 
      client providing multiple addr extentions in the request.

  3.  Or we don't permit this behavior and all the client does
      is have a bit set in the request header "give me my addresses"
      an no addr extensions are provided by the client request msg.

I would like to see us adopt #2 above and is the compromise.

>optimization, but it is not required for correctness.)

We did not build the binding cache for this reason but I see your point.
See my above statements.  What I am saying is a correct server
implementor would not permit the idempotent problem. But there is a bug
and it could.  But its an implementation protocol clarification we need
or do as DHCPv4 does which I find to limiting for DHCPv6. 
 
>otherwise. Hence, it is not just a performance optimization, it is

I don't agree see above.  Also the once the binding cache times out the
problem happens anyway.  We don't keep the cache forever.  

>this model (but that it is required, not optional).

Not once the cache times out.
If the cache times out and the client retransmits then the server must
respond by whats in the database.  This is probably not likely but could
happen.  Ergo why I say above there is bug here we need to fix and I
provided my view of that fix.

>memory), and this cost is not necessarily lower than reexecuting a

I understand that argument.  But I am biased as you say the memory look
ups is always a cost and has to be re-evaluated often in systems as they
grow and change.  Its also a maintenance headache.  If I can avoid a
lookup its always a good thing IMO.

/jim

---

From: Charles Perkins <[email-masked]>
Date: Fri, 19 Nov 1999 11:54:23 -0500 (EST)

> with exactly the same information as it responded to the first

I don't want to get deeply involved with this discussion, but
I'm worried that the above might be misinterpreted.

It is the transaction ID that allows retransmission to be
idempotent.  The specification requires, I think, that a server
transmit the same DHCP Reply after a retransmitted DHCP Request
from a client.

The binding cache makes that easier to do.  Other possibilities
exist; we couldn't think of any easier way to do it than using
a binding cache.  Strictly speaking, it should be an implementation
choice; at this stage I am not in any way suggesting that we
make changes to the specification for the purpose of reaching
that level of purity.

But it's the transaction ID that is the determinant here.

Regards,
Charlie P.

---

From: Jim Bound <[email-masked]>
Date: Fri, 19 Nov 1999 13:50:32 -0500 (EST)

charlie,

the issue with the transation id is that if it wraps hence they are not
part of the server database entry in section 6.  the reason we did this
was because of the wrapping.  but one can find the client.

once the retransmit is over via XID_TIMEOUT the transaction is looked up
in the database is how had started my prototype.  

as I just stated to thomas we probably need to nail down this multiple
address decision with the working group and relook at the cache.  

as I did not want to search the whole database on a client request and I
timed out and whether it was a retransmit or request is irrelevant ergo
the idempotent issues with addresses.

once the XID_TIMEOUT expires for a transaction a request for the client
is not a retransmit even if it really is.  But the protocol for
retransmission will still work at the client end regardless of the
server behavior.  which was our design principle all along.  I think we
have kept that design priniciple in tact and one we borrowed from
DHCPv4 directly.

at the chicago meeting we discussed this.  this way we do not have to
keep transaction ids as they are essentially volatile as part of the key
to look up clients for requests in the database.

I personally don't believe the protocol will work as well without a
retransmit cache and so far from my prototyping I appear to be right.

but it could be an implementation advantage that we can take out of the
spec and my implementation will be the best and make the most money in
the market -----)..... 

/jim

---

From: Charles Perkins <[email-masked]>
Date: Fri, 19 Nov 1999 16:26:27 -0500 (EST)

Hello Jim,

> was because of the wrapping.

But the XID_TIMEOUT will occur long before transaction-ID wrapping
will make any difference.  And retransmissions will occur long before
XID_TIMEOUT.  If these statements are not true, then we may have to
put more bits into the transaction-ID field.  On the other hand,
I can't think of a client making 100 transactions per second for
600 seconds.  That sounds preposterous; thus, I don't think this is
a problem.  And, I can't think about why it would take 10 minutes
for a server to manage a DHCP Request either.  Thus, the default
values seem to work O.K. to me.

> in the database is how had started my prototype.

The way I parse this means that transactions aren't finished for
10 minutes (600 seconds), and I'm sure that's not the way you
meant it.

> the idempotent issues with addresses.

When a new DHCP Request comes in, the server should naturally look
at the client's binding.  This should happen no matter what extensions
are present, and no matter how often new DHCP Requests arrive.

> server behavior.

While I agree with your statement, I think the situation would
never arise, by the timing considerations I outlined previously
in this note.

> retransmit cache and so far from my prototyping I appear to be right.

While I agree with this as stated, it doesn't imply that a correct
protocol is required to have such a retransmission cache.

> spec and my implementation will be the best and make the most money in

How about if it merely makes a few hundred million $, but not the most?

Regards,
Charlie P.

---

From: Charles Perkins <[email-masked]>
Date: Fri, 19 Nov 1999 17:56:24 -0500 (EST)

Hello Jim,

I would like to suggest that we do not need to add new
behavior for the DHCP server to be able to disambiguate
requests for new addresses from requests to renew lifetimes
for existing addresses.

The main point, as discussed earlier today, is that the DHCP
server has to keep track of what has been assigned to its
clients.  Thus, if a client asks to renew the lifetime of its
assigned address, the server will know that the client already
has the address assigned, so it can do the right thing.

Conversely, if a client sends a request in with an address
extension including an address that has not been assigned to it,
the server can (if desired) make that new address assignment.

If a client sends a request that does NOT have an address
extension, the server has to figure out whether or not to
put an address extension on the DHCP Reply.  I suggest that
this needs to be done by having administrative information
present at the DHCP server that will determine the relevant
address assignment policy for that subnet.  If the subnet
uses stateless address autoconfiguration, the server doesn't
have to send an address.  If the subnet doesn't use stateless,
and the server has no records for the client, then the server
probably should send an address out to the client.

If the client has gotten some addresses from one server, and
then sends a request to another server, then the second server
will not necessarily know about all of the addresses that the client
has received from the first server.  In that case, the client might
still wish to receive another IP address from the second server.
That would typically be the desired behavior when the second
server was administratively configured to provide addresses for
the subnet from which the client made the request.  If the client
has an IP address already assigned, then it would use that IP
address as the source IP address for its DHCP Request packet,
so alternate servers can always know when the client already
has an IP address assigned.

If you have more cases, then we can discuss them to make sure
that our current mechanism handles each case well.  And, if it
turns out that there is a case which isn't yet handled, we can
evaluate whether creating new bits in the DHCP Request message
will solve the problem.  I don't want to create the bit before
I can understand what problem it will be solving.

> the client a new address.

Idempotency has to be judged for messages that all have the same
transaction ID.  I think it would be a mistake to constrain messages
with different transaction IDs to necessarily have the same results.
If I ask for a bowl of ice cream, I don't want somebody telling me that
I already got one bowl.

> I would like to see us adopt #2 above and is the compromise.

As I suggested earlier in this message, I don't yet see the need
for any new bits, nor a change to the specified behavior in the
protocol.

> problem happens anyway.  We don't keep the cache forever.

I think that the behavior with respect to the client is contolled
by the client binding, not by anything that depends strictly on
the transaction ID.  The transaction ID can be part of the client
binding, but if a server allocates an IP address to the client for
50 hours, it has to keep the client binding around for 50 hours.
It might be useful to specify a maximum holding time for
client bindings, but it has to be a lot larger than XID_TIMEOUT.
There isn't any such maximum time specified now in DHCPv6, and
it might just as well be implementation-dependent.

> provided my view of that fix.

Is there anything with using what's in the database?  Is there
ever a circumstance where the database contents could disagree
with the contents of the cache?  I hope not...

Regards,
Charlie P.

---

From: Jim Bound <[email-masked]>
Date: Sat, 20 Nov 1999 22:03:04 -0500 (EST)

Hi Charlie,

>values seem to work O.K. to me.

I seem to have lost track of the issue what your saying I agree with.
My statements above are on a completely different track and response to
another matter so I am confused ???? sorry...

My response above was a reason that was given to the WG why we took the
transaction-id out of the database key binding which is mandatory.
The database I was talking about and section 6. is the server database
for the clients.  For the BINDING cache I agree. 
But it is not listed as a key for the binding as required.
I for one would use it for the binding cache.

Section 6:

 A server maintains a collection of client records, called
   ``bindings''.  Each binding is uniquely identifiable by the ordered
   pair <link-local address, agent-address>, since the link-local
   address is guaranteed to be unique [20] on the link identified by the
  agent-address and prefix.  An implementation MUST support bindings
   consisting of at least a client's link-local address, agent-address,
  preferred lifetime and valid lifetime [20] for each client address.

AND THEN LATER ON: 

   In addition to the client binding a server must maintain an
   XID_TIMEOUT binding cache to determine if a previous transaction-ID
   is being retransmitted by a client.  An implementation of an
   XID_TIMEOUT binding cache MUST support at least a tuple consisting of
  the client's link-local address, agent-address prefix, IPv6 address,
   and XID_TIMEOUT value when the cache entry can be deleted (see
   Section 8).

I would not use it for the servers collection records though.  

>10 minutes (600 seconds), and I'm sure that's not the way you

I am saying if the client does not retransmit until 20 minutes later 
the Request will be looked up in the server client database if
XID_TIMEOUT is at default.  

The point for me wearing my implementor hat is that if a customers
client does this and I am the server I have to write code for that case
in the protocol spec.

This is where the entire issue of idempotency appears from Thomas.  His
question is valid, but we are fine IMO as best I can tell.  But the
multiple address decisions on that thread affects what I will do for and
to keep idempotency in my software as a server.  If the spec don't do it
I have to do it as a product engineer.  So IMO we have to resolve this
issue one way or the other.  I can't guess at it which is what I am
doing now by driving the policy at the set up or something.  

>are present, and no matter how often new DHCP Requests arrive.

My statement implied a "retransmit client request" from previous client
requests, sorry for the terseness, I was quite busy when I wrote the
above.  For a retransmit I would not have to look at the cleint database
but only for the REPLY I must resend.  This is why we have the binding
cache in the spec so I don't have to look up the server database for
retransmits and keep the cache entries small.

>never arise, by the timing considerations I outlined previously

Well I disagree and I think I clearly articulate why and how above. I am
interested where you see a flaw in my above response.  Unless you don't
believe a client will respond later than 600 seconds?  Which I would
disagree with if told it can't happen.

>protocol is required to have such a retransmission cache.

I agree. We could actually put this all in an appendix is your
implication of such a response?

>How about if it merely makes a few hundred million $, but not the most?

That would be fine too.

thanks
/jim

---

From: Jim Bound <[email-masked]>
Date: Sat, 20 Nov 1999 23:09:38 -0500 (EST)

Charlie,

>requests for new addresses from requests to renew lifetimes

I would suggest we need to add text to the spec though it could be
much more clear and its not now as we go thru this excercise.

>has the address assigned, so it can do the right thing.

I don't agree that was the main point of the discussion.  The main point
of the discussion is twofold:

  1.  did we specify clearly what the server must do with the
      combinations of getting addresses.  I think we uncovered a 
      case per the WG mail list discusion which is good.  If I am
      wrong that is great less spec changes.  But I think there 
      is a bug.

  2.  Does the WG support changing the model of DHCPv4 addresses to
      clinent.  I hope so when this discussion ends.

But to get to the other part of your sentence above.  I agree but would
add this means the client also provides the extension in the msg to
renew the lifetimes.

But we should add this set of statements to the spec.

>>the server can (if desired) make that new address assignment.

This is the case where a client now has sent in an address suggesting 
to the client I want to use this address, and the client is telling the
server to add this address to their database.  

This is exactly why we need to specify in the specs what the
combinations of extensisons are and their syntax and semantics so its
clear.  It not now.

I would change the word desire to MAY though as I don't find it to
desirable in the norm to tell servers to get addresses from clients.
But I would not disallow folks from building servers to do this in the
future.

So now we have two cases of interpreting extensions.  

>probably should send an address out to the client.

Your statement above on stateless is not necessarily true.  The
stateless addrconf can be running and when the router sets the M bit it
says go get your addresses or additional addresses from dhcpv6.
So I strongly don't agree with your suggestion.  DHCPv6 and Stateless
will operate together on the same link potentially as Addrconf is realy
just a subset of Neighbor Discovery, so if the M bit is on the dhcpv6
server will be contacted if not then dhcpv6 won't be contacted.

But what if the server has already given the client addresses?

In this case the server should not give the client an address if there
is no address extension.

If the client has no addresses then I agree with you a good citizen
server would do this and no policy is needed as you suggest we just
define the defaults maybe?

But there is another case.

What if the server gets an empty address extension which is permitted
today.

 1.  If the client has no addresses then I think an address 
     can be returneded for each client address extension if the 
     client is permitted to have X addresses.  This is where 
     policy is needed and has nothing to do with stateless addrconf.

 2.  If the client has existing addresses do you give them another 
     one or not.  I would say yes up to the number of addresses
     allowed per client by policy.

But then we are back to that a client must provide an extension for an
address request unless its the clients first request to get an address
per server.  

>has an IP address assigned.

I think this is of benefit for when multiple servers are used.  

>I can understand what problem it will be solving.

I suggested two ways to solve the problem one with bits and one with
extensions.  I would rather not add bits to the protocol here either but
I am not going to not suggest solutions at this point in the WG because
we have to changed the spec in this particular space.  We need to hear
any ideas at this point IMO.

/jim

Regards,
Charlie P.

---

From: Jim Bound <[email-masked]>
Date: Sun, 21 Nov 1999 00:12:47 -0500 (EST)

Charlie,

Now I will respond to the rest of your mail.  I wanted to split it up.

>If I ask for a bowl of ice cream, I don't want somebody telling me that

Then you are saying you want transaction-ids to be mandatory in the
binding for the server client database?

I think in that case it changes the landscape.  But it don't address the
problem documented above.  This must be specified one way or the other.

If we are to add transaction-ids I would claim they are necessary if we
move the binding cache to the appendix.  Otherwise they are not.  Just
treat any request as a request and then all requests are idempotent.
Which I think is a worthwhile and attainable for dhcpv6 with few words
in the specs.  But first we need to address and define the address
logistics which I think we are doing now  and in my previous response to
this mail on the first part.

>for any new bits, nor a change to the specified behavior in the

Well I hope you getting there now after my responses.  It don't have to
be new bits and I said do #2 whihc has no new bits.

A client has to use extensions to request addresses.  If it has 3 and
wants another one it has to provide 4 extensions.  

But if you don't like this idea we still have the problem  as stated in
the previous mail.

>it might just as well be implementation-dependent.

I agree the holding time should be implementation-dependent.

>with the contents of the cache?  I hope not...

Yes.  Of course.  The cache is for the binding for retransmits the
server database is completely different.  If the binding cache times out
the entry is gone.  The binding cache is only there to look for
retransmits so the entire database is not searched.

binding cache entry:

  link-local-address+agent-prefix /*search key*/
  request-transid
  *reply-data-buffer-sent 

server  database:

   link-local-address+agent-prefix /*search key*/
   *client-records
   link-local-address+agent-prefix /*search key*/
   *client-records
   etc. etc...

The binding cached and server database (which could be a cache) are
different.

WHEN_CLIENT_REQUEST_RECEIVED
  If (search_retransmit_binding_cache(*CLIENT_REQUEST))
     return; /* all work for retransmit done in function above */
  else 
     locate_client_in_database(*CLIENT_REQUEST)
     ....process the request and build reply.....
     ....add entry to binding cache for this request....

If the client has been taken out of the binding_cache above then the
request is treated as a non-retransmitted request.  Of if we put the
binding cache in the appendix.  We don't really then differentiate btw
retransmits vs normal requests at the server.

But regardless we need to say what happens when a client requests an
address when the server has already provided them an address and under
what circmustances is that permitted and what are the semantics in the
protocol.  This is a bug in the spec IMO.

The entire binding cache discussion I clain is not relevant nor is
required for correct behavior and does nothing to help with correct
behavior if there is a bug after XID_TIMEOUT and a client retransmits 20
minutes later.  

I don't think its a "big" bug.  It is matter first agreeing if we want
to permit the client to request as many addresses as it wants as long as
the server wants to give them to the client.  Once the client reaches
the policy line where its not allowed more addresses by the
administrator the server tells the client no more addresses are
available.

I think we handle all the cases except for what tells a server what to
do with an empty extension and the server has given the client all but
one more address it allows.  And the case you just defined in other mail
where there are no extensions specified we don't even discuss that case
in the spec and we should.  

We can't resolve the issue if we don't get to the details.  Which I
think we are now?  But there is a problem with the spec in this space
and I agree with Thomas it needs to be resolved.  What the answer is I
don't think Thomas and I agree.  But I think we are on the same page of
the problems?

/jim