Subject: Re: [dhcwg] Simplification of DNAv4 specification

From: Stuart Cheshire <[email-masked]>
Date: Thu, 13 Oct 2005 15:53:51 -0700

I think the newly pared-down draft is a vast improvement.

One of the things I found myself thinking, as I read various revisions of 
this specification over the last few months, is that it didn't clearly 
describe exactly what problem it was trying to solve, and why, and what 
constraints this implied for the possible solution space.

In the IETF spirit of "provide text", I offer a first cut at this 
analysis and discussion, below.

One surprising conclusion came to me as I was writing this:

All along, I'd thought that the point of this work was to eliminate the 
seven-second delay for address conflict detection; to turn a wait for a 
non-response, which can't be shortened, into a wait for a positive 
acknowledgement from the router, which *can* be made almost arbitrarily 
fast, within the limits of the speed of light.

However, it turns out (I think) that this is not true. Any candidate 
configuration eligible for DNAv4 is also eligible for DHCP INIT-REBOOT, 
and INIT-REBOOT does *not* require that the client perform address 
conflict detection. Thus, all that DNAv4 is accelerating is the DHCP 
INIT-REBOOT REQUEST/ACK cycle.

See proposed text below:

[Section Number xxx] Goals and Constraints

   DHCP is an effective and widely adopted mechanism for a host to
   obtain an IP address for use on a particular network link, or to
   re-validate a previously obtained address via DHCP's INIT-REBOOT
   mechanism [RFC2131].

   In the case of obtaining a new address, DHCP specifies that the
   client SHOULD use ARP to verify that the offered address is not
   already in use. The process of address conflict detection [ACD] can
   take as much as seven seconds. In principle this time interval could
   be shortened, with the obvious trade-off: the less time a host spends
   waiting to see if another host is already using its intended address,
   the greater the risk of inadvertent address conflicts.

   In the case of re-validating a previously obtained address using the
   INIT-REBOOT mechanism, the DHCP specification does not require the
   client to perform address conflict detection, so this seven-second
   delay does not apply. However, the DHCP server may be slow to
   respond, or may be down and not responding at all, so hosts could
   benefit from having an alternative way to quickly determine that a
   previously obtained address is valid for use on this particular link.

   The alternative mechanism specified by this document applies when a
   host has a previously-allocated DHCP address, which was not returned
   to the DHCP server via a DHCP RELEASE message, and which still has
   time remaining on its lease. In this case, the host may determine
   whether it has re-attached to the logical link where this address is
   valid for use, by sending a unicast ARP Request packet to the default
   router previously known for that link (or in the case of a link with
   more than one router, by sending one or more unicast ARP Request
   packets to one or more of those routers).

   The use of unicast ARP has a number of benefits. One benefit is that
   unicast packets impose less burden on the network than broadcast
   packets, particularly on 802.11 networks where a 54Mb/sec 802.11g
   link may have to slow down to 1Mb/sec to send a broadcast packet.
   Another benefit is that in the event of the host not being on the
   link it hoped to find itself on, a broadcast ARP Request could
   pollute the ARP caches of peers on that link. When using private
   addresses [RFC1918] another device could be legitimately using the
   same address, and a broadcast ARP Request could disrupt its
   communications, causing TCP connections to be broken, and similar
   problems. By using a unicast ARP packet instead, addressed to the MAC
   address of the router the host is expecting to find, if the host is
   not on the expected link, then there will be no device with that MAC
   address, and the ARP packet will harmlessly disappear into the void
   without doing any damage.

   These issues that define the applicability of DNAv4 lead us to a
   number of conclusions:

   o DNAv4 is a performance optimization. Its purpose is to take a
     process that is already quite fast (DHCP INIT-REBOOT) and make
     it faster.

   o As a performance optimization, it must not sacrifice correctness.
     In other words, false positives are not acceptable. DNAv4 must not
     conclude that a host has returned to a previously-visited link
     where it has an operable IP address if this is not in fact the
     case.

   o As a performance optimization, false negatives are acceptable.
     It is not an absolute requirement that this optimization correctly
     recognize a previously-visited link in all possible cases.
     For example, if a router ignores unicast ARP Requests then DNAv4
     will not be able to detect that it has returned to the same link
     in future. This is acceptable because it does not affect
     correctness. In this case the host still operates correctly, as it
     did before in a world without DNAv4; it just operates without the
     performance benefit of DNAv4. Users and network operators who
     desire the performance improvement offered by DNAv4 will have an
     incentive to upgrade their router to one that supports DNAv4.

   o As a performance optimization, DNAv4 should not have an adverse
     effect compared to today's status quo. In cases where DNAv4 fails
     to provide a benefit, it should add little or no delay compared to
     today's existing DHCP INIT-REBOOT processing. The practical effect
     of this statement is that DHCP INIT-REBOOT processing needs to
     proceed in parallel with DNAv4 processing. In particular, waiting
     for DNAv4 to fail before beginning DHCP processing has the
     potential to make an operation that is currently very quick into an
     operation that takes dramatically longer, which would be the exact
     opposite of the desired effect of this performance optimization.

   o Trials are cheap. DNAv4 performs its checks using small unicast
     packets. An IPv4 ARP packet on Ethernet is just 42 bytes, including
     Ethernet header. This means that the cost of an unsuccessful
     attempt is small, whereas the cost of a missed opportunity (having
     the right address available as a candidate and choosing not to try
     it for some reason) is large. The conclusion we draw from this
     observation is that the best strategy is likely to be simply to try
     all available candidate configurations, rather than trying to use
     heuristics or hints to determine which candidates, if any, we
     predict may be correct for this link. For a heuristic to usefully
     eliminate a configuration from our list of candidates, it has to
     (a) be fast and cheap to compute, compared to sending a 42-byte
     unicast packet, and (b) have high probability of not falsely
     eliminating a candidate configuration that would in fact have been
     found to be the correct one. For example, eliminating a candidate
     configuration just because it was obtained on a different physical
     interface would not be a safe heuristic. In the case of an Ethernet
     link and an 802.11 wireless link bridged together, an IP address
     and default gateway obtained on the Ethernet link may continue to
     be a perfectly valid and usable configuration if the host loses its
     Ethernet connection and switches to 802.11 wireless.

   o Time is limited. On most networks we can reasonably expect DHCP
     INIT-REBOOT processing to complete in a few hundred milliseconds
     at worst. This means that if DNAv4 is to provide a performance
     benefit compared to DHCP INIT-REBOOT, it needs to begin within
     at most a few tens of milliseconds of DHCP INIT-REBOOT processing.
     Any heuristic used to eliminate candidate configurations needs to
     take at most a few milliseconds to compute. In particular this
     means that any heuristic based on passive observation of passing
     Ethernet-level or IP-level traffic is unlikely to observe any
     useful packets in the time available before DNAv4 needs to decide
     whether it's going to test a candidate configuration or not.

Stuart Cheshire <[email-masked]>
 * Wizard Without Portfolio, Apple Computer, Inc.
 * www.stuartcheshire.org

_______________________________________________
dhcwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/dhcwg

---

From: Stuart Cheshire <[email-masked]>
Date: Thu, 13 Oct 2005 16:09:12 -0700

I propose the following technical edits relative to
<http://www.drizzle.com/~aboba/DNA/draft-ietf-dhc-dna-ipv4-17.txt>

2 lines changed at 189
(INIT-REBOOT does not actually require the host to do Duplicate Address 
Detection)
-- OLD TEXT --
   network, without needing to re-acquire it, allowing the host to
   bypass Duplicate Address Detection (DAD).
-- NEW TEXT --
   network, without needing to re-acquire it.
--------------

5 lines changed at 201
(DNAv4 does in fact slightly increase the likelihood of an address 
conflict)
-- OLD TEXT --
   DNAv4 does not increase the likelihood of an address conflict.  The
   reachability test is only carried out for a network when the host has
   previously completed duplicate address detection and obtained an
   operable IPv4 configuration on that network.  Restrictions on sending
   ARP Requests and Responses are described in Section 2.1.1.
-- NEW TEXT --
   DNAv4 does not significantly increase the likelihood of an address
   conflict.  The reachability test is only carried out for a network
   when the host has previously completed address conflict detection
   [ACD] and obtained an operable IPv4 configuration on that network.
   Restrictions on sending ARP Requests and Responses are described in
   Section 2.1.1.

   One case where DNAv4 does increase the likelihood of an address
   conflict is when:

   o a DHCP server hands out an address lease

   o the host with that lease leaves the network

   o the DHCP server is power-cycled, or crashes and is rebooted

   o the DHCP server, having failed to save its lease table to
     persistent storage, assigns that same address to some other host

   o the first host returns, and having a still-valid lease with time
     remaining, proceeds to use its assigned address, conflicting with
     the new host that is now using that same address

   DHCP servers are supposed to save their lease tables in persistent
   storage, but almost no consumer-grade NAT gateway does so. Use of
   short DHCP lease lifetimes can mitigate this risk, though use of
   short DHCP lease lifetimes also limits the situations where DNAv4
   has operable candidate configurations available to try.
--------------

10 lines changed at 268
(remove special-case distinction for "private addresses")
-- OLD TEXT --
   Duplicate Address Detection on the former network does not provide
   assurance against an address conflict on the new network.  Until a
   host with a private address has confirmed the operability of its IPv4
   configuration, it SHOULD NOT respond to ARP Requests, and SHOULD NOT
   broadcast ARP Requests containing its address within the sender
   protocol address field (ar$spa).  However, where the host has an
   operable routable non-private address on a network, it MAY send ARP
   Requests using its address within the sender protocol address field
   (ar$spa) prior to confirming its IPv4 configuration, and MAY respond
   to ARP Requests.
-- NEW TEXT --
   address conflict detection [ACD] on the former network does not provide
   assurance against an address conflict on the new network. Until a
   host has confirmed the operability of its IPv4 configuration by
   recipt of the expected ARP response from the gateway, it SHOULD NOT
   respond to ARP Requests, and SHOULD NOT broadcast ARP Requests
   containing its address within the sender protocol address field
   (ar$spa).
--------------

---

From: Stuart Cheshire <[email-masked]>
Date: Thu, 13 Oct 2005 16:23:03 -0700

I propose the following typographical edits relative to
<http://www.drizzle.com/~aboba/DNA/draft-ietf-dhc-dna-ipv4-17.txt>

1 line changed at 9
-- OLD TEXT --
               Detecting Network Attachment (DNA) in IPv4
-- NEW TEXT --
               Detecting Network Attachment in IPv4 (DNAv4)
--------------

1 line changed at 98
-- OLD TEXT --
   [RFC2119].
-- NEW TEXT --
   "Key words for use in RFCs to Indicate Requirement Levels" [RFC2119].

--------------

1 line changed at 159
-- OLD TEXT --
     private addresses as specified in [RFC1918].
-- NEW TEXT --
     private addresses as specified in "Address Allocation for Private
     Internets" [RFC1918].
--------------

1 line changed at 164
-- OLD TEXT --
     not been relinquished, and whose lease has not yet expired.
-- NEW TEXT --
     not been returned to the DHCP server via a DHCP RELEASE message,
     and whose lease has not yet expired.
--------------

3 lines changed at 197
-- OLD TEXT --
   DHCPREQUEST from the INIT-REBOOT state, as described in [RFC2131]
   Section 3.2 and 4.3.2 completes more quickly than the reachability
   test(s).
-- NEW TEXT --
   DHCPREQUEST from the INIT-REBOOT state, as described in Section 3.2
   and 4.3.2 of the DHCP specification [RFC2131], completes more quickly
   than the reachability test(s).
--------------

1 line changed at 219
-- OLD TEXT --
   [b] The host does not know the default gateway(s) on
-- NEW TEXT --
   [b] The host does not know the addresses of any gateway(s) on
--------------

5 lines changed at 238
-- OLD TEXT --
   Note that it's not possible to get more than one reachability test
   response on a given link, because the first one is the only one that
   should be accepted.  Once a valid reachability test response is
   received, validation is complete, and additional responses (if any)
   should be discarded.
-- NEW TEXT --
   Once a valid reachability test response is received, validation is
   complete, and any additional responses should be discarded.
--------------

2 lines changed at 247
-- OLD TEXT --
   The reachability test is performed by sending an ARP Request.  The
   host MUST set the target protocol address (ar$tpa) to the IPv4
-- NEW TEXT --
   The reachability test is performed by sending a unicast ARP Request.
   The host MUST set the target protocol address (ar$tpa) to the IPv4
--------------

1 line changed at 250
-- OLD TEXT --
   address field (ar$spa) to its own IPv4 address.  The ARP Request MUST
-- NEW TEXT --
   address field (ar$spa) to its own candidate IPv4 address.
   The ARP Request MUST
--------------

2 lines changed at 263
-- OLD TEXT --
   acquisition and expiration behavior described in [RFC2131], Section
   4.4.5.
-- NEW TEXT --
   acquisition and expiration behavior described in
   Section 4.4.5 of the DHCP specification [RFC2131].
--------------

6 lines changed at 280
-- OLD TEXT --
   address does not provide the same level of assurance since this may
   require an ARP Request/Reply exchange.  Where the host has moved
   between two private networks, this could result in ARP cache
   pollution.

   Where a host moves from one private network to another, an ICMP Echo
-- NEW TEXT --
   would not be an acceptable way of testing a candidate configuration
   because sending any IP packet generally requires an ARP Request/Reply
   exchange, and as explained above, ARP packets may not be broadcast
   safely until *after* the operability of the candidate configuration
   has been confirmed. Also, where a host moves from one private network
   to another, an ICMP Echo
--------------

1 line changed at 314
-- OLD TEXT --
   broadcast address as specified in [RFC2131] Section 4.4.2.
-- NEW TEXT --
   broadcast address, as specified in Section 4.4.2 of the DHCP
   specification [RFC2131].
--------------

2 lines changed at 318
-- OLD TEXT --
   packet to the broadcast address, as described in [RFC2131] Section
   4.4.1.  If the host supports the Rapid Commit Option [RFC4039], it is
-- NEW TEXT --
   packet to the broadcast address, as described in Section 4.4.1 of the
   DHCP specification [RFC2131].
   If the host supports the Rapid Commit Option [RFC4039], it is
--------------

2 lines changed at 324
-- OLD TEXT --
   DHCPDISCOVER, then it retransmits as specified in [RFC2131] Section
   4.1.
-- NEW TEXT --
   DHCPDISCOVER, then it retransmits as specified in Section
   4.1 of the DHCP specification [RFC2131].
--------------

1 line changed at 327
-- OLD TEXT --
   As discussed in [RFC2131], Section 4.4.4, a host in INIT or REBOOTING
-- NEW TEXT --
   As discussed in Section 4.4.4 of the DHCP specification [RFC2131], a
   host in INIT or REBOOTING
--------------

2 lines changed at 361
-- OLD TEXT --
   [RFC3927], and MUST NOT attempt to use DNAv4 as a shortcut to bypass
   that process.
-- NEW TEXT --
   "Dynamic Configuration of IPv4 Link-Local Addresses" [RFC3927], and
   MUST NOT attempt to use DNAv4 as a shortcut to bypass that process.
--------------

1 line changed at 367
-- OLD TEXT --
   described in [RFC2131] Section 2.3.  Where a host can confirm that it
-- NEW TEXT --
   described in Section 2.3 of the DHCP specification [RFC2131].  Where
   a host can confirm that it
--------------

1 line changed at 370
-- OLD TEXT --
   Local address is deprecated, as noted in [RFC3927] Section 1.9.
-- NEW TEXT --
   Local address is deprecated, as noted in Section 1.9 of the IPv4
   Link-Local specification [RFC3927].
--------------

1 line changed at 375
-- OLD TEXT --
   retransmission algorithm, [RFC2131] Section 3.2 states that the
-- NEW TEXT --
   retransmission algorithm, Section 3.2 of the DHCP specification
   [RFC2131] states that the
--------------

---

From: Stuart Cheshire <[email-masked]>
Date: Thu, 13 Oct 2005 16:27:28 -0700

Regarding references, I think RFC792 (ICMP), RFC3118 (Authentication), 
and RFC3927 (IPv4LL) should be moved to Informative References (none of 
those are required to implement DNAv4).