IPv6 Working Group Nick 'Sharkey' Moore
INTERNET-DRAFT Monash University CTIE
23 March 2004
Optimistic Duplicate Address Detection
<draft-ietf-ipv6-optimistic-dad-00.txt>
Status of this Memo
This document is an Internet-Draft and is subject to all provisions
of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that other
groups may also distribute working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or cite them other than as "work in progress".
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/lid-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
Definitions of requirements keywords are in accordance with the IETF
Best Current Practice - RFC2119 [RFC2119]
Abstract
Optimistic Duplicate Address Detection is an interoperable
modification of the existing IPv6 Neighbour Discovery (RFC2461) and
Stateless Address Autoconfiguration (RFC2462) process. The intention
is to minimize address configuration delays in the successful case
without greatly increasing disruption in the less likely failure
case, and while remaining interoperable with unmodified nodes.
Nick 'Sharkey' Moore Expires: September 2004 [Page 1]
INTERNET-DRAFT Optimistic DAD 23 March 2004
Table of Contents
Status of this Memo ......................................... 1
Abstract .................................................... 1
Table of Contents ........................................... 2
1. Introduction ............................................. 2
1.1 Problem Statement ............................... 3
1.2 History ......................................... 3
1.3 Definitions ..................................... 4
1.4 Abbreviations ................................... 4
2. Optimistic Behaviours .................................... 5
3. Modifications to RFC-compliant behaviour ................. 7
3.1 Modifications to RFC 2461 Neighbour Discovery ... 7
3.2 Modifications to RFC 2462 SAA ................... 7
3.3 Address Generation............................... 8
3.4 DIID vs DAD ..................................... 9
4. Protocol Operation ....................................... 9
4.1 Simple case ..................................... 10
4.2 Collision case .................................. 10
4.3 Interoperation cases ............................ 11
4.4 Pathological cases .............................. 11
5. Security Considerations .................................. 12
Notes ....................................................... 12
References .................................................. 13
Acknowledgments ............................................. 14
Author's Address ............................................ 14
1. Introduction
Optimistic Duplicate Address Detection (DAD) is a modification of the
existing IPv6 Neighbour Discovery (ND) [RFC2461] and Stateless
Address Autoconfiguration (SAA) [RFC2462] process. The intention is
to minimize address configuration delays in the successful case, and
to reduce disruption as far as possible in the failure case.
Optimistic DAD is a useful optimization because DAD is far more
likely to succeed than fail for a well-distributed random address
[SOTO]. Disruption is minimized by limiting nodes' participation in
Neighbour Discovery while their addresses are still Tentative.
It is not the intention of this draft to improve the security,
reliability or robustness of DAD beyond that of existing standards,
merely to provide a method to make it faster.
Nick 'Sharkey' Moore Expires: September 2004 [Page 2]
INTERNET-DRAFT Optimistic DAD 23 March 2004
1.1 Problem Statement
The existing IPv6 address configuration mechanisms provide adequate
collision detection mechanisms for the static hosts they were
designed for. However, a growing population of nodes need to
maintain continuous network access despite frequently changing their
network attachment. Optimizations to the DAD process are required to
provide these nodes with sufficiently fast address configuration.
An optimized DAD method needs to:
* provide interoperability with nodes using the current standards.
* remove the RetransTimer delay during address configuration.
* ensure the probability of address collision is not increased.
* improve the resolution mechanisms for address collisions.
* minimize disruption in the case of a collision.
It is not sufficient to merely reduce RetransTimer in order to reduce
the handover delay, as values of RetransTimer long enough to
guarantee detection of a collision are too long to avoid disruption
of time-critical services.
1.2 History
There is some precedent for this work in previous drafts [KOODLI],
and in discussions in the MobileIP WG mailing list and at IETF-54.
This version of Optimistic DAD differs somewhat from previous
versions in that it uses no additional flags or message types beyond
those already defined, therefore allowing interoperation between
Optimistic and Standard nodes.
Earlier versions of this work were presented by the author to the
MobileIP WG at IETF-56, and to the IPv6 WG at IETF-59.
Working implementations of earlier versions of this draft have been
made by the author as a freely-available patch to Linux 2.4.18, and
by Ed Remmel of Elmic Systems.
Nick 'Sharkey' Moore Expires: September 2004 [Page 3]
INTERNET-DRAFT Optimistic DAD 23 March 2004
1.3 Definitions
Tentative - an address for which a node has not yet completed DAD is
regarded as Tentative: a single Neighbour Advertisement
defending this address will cause the node to deconfigure the
address and cease using it.
Optimistic - An Optimistic node assumes that DAD will succeed, and
allows higher-layer communications on an address even while that
address is still Tentative.
Standard - A Standard node is one which is compliant with RFCs 2461
and 2462.
Link - A communication facility or medium over which nodes can
communicate at the link layer.
Neighbours - Nodes on the same link, which may therefore be competing
for the same addresses.
1.4 Abbreviations
DAD - Duplicate Address Detection. Technique used for SAA. See
[RFC2462] section 5.4.
ICMP Redirect - See [RFC2461] section 4.5.
NA - Neighbour Advertisement. See [RFC2461] sections 4.4 and 7.
NC - Neighbour Cache. See [RFC2461] section 5.1 and 7.3.
ND - Neighbour Discovery. The process described in [RFC2461]
NS - Neighbour Solicitation. See [RFC2461] sections 4.3 and 7.
ON - Optimistic Node. A node which is behaving according to the
rules of this draft.
RA - Router Advertisement. See [RFC2462] sections 4.2 and 6.
RS - Router Solicitation. See [RFC2461] sections 4.1 and 6.
SAA - Stateless Address Autoconfiguration. The process described in
[RFC2462]
Nick 'Sharkey' Moore Expires: September 2004 [Page 4]
INTERNET-DRAFT Optimistic DAD 23 March 2004
SLLAO - Source Link Layer Address Option - an option to NS, RA and RS
messages, which gives the link layer address of the source of
the message. See [RFC2461] section 4.6.1.
TLLAO - Target Link Layer Address Option - an option to ICMP redirect
messages. See [RFC2461] sections 4.5 and 4.6.1.
2. Optimistic Behaviours
Optimistic DAD is only a useful optimization when the probability of
collision is very small. As such, the Optimistic algorithm SHOULD
NOT be used for manually assigned addresses, where the collision
probability is likely to be much higher than that for random
addresses due to human error.
Modifications are required only to Optimistic nodes -- Optimistic
nodes will interoperate with Standard nodes without significant
advantage or incompatibility.
In order to do this, it is important that an Optimistic node does
not, while Tentative, send any messages which will override its
neighbours' Neighbour Cache (NC) entries for the address it is trying
to configure: doing so would disrupt the rightful owner of the
address in the case of a collision.
This is achieved by:
* clearing the 'Override' flag in Neighbour Advertisements for
Tentative addresses, which prevents neighbours from overriding
their existing NC entries. The 'Override' flag is already
defined [RFC2461] and used for Proxy Neighbour Advertisement.
* Never sending Neighbour Solicitations from a Tentative address.
NSs include a Source Link Layer Address Option (SLLAO), which
may cause Neighbour Cache disruption. NSs sent as part of DAD
are sent from the unspecified address, without a SLLAO.
* Never using a Tentative address as the source address of a Router
Solicitation with an SLLAO. Another address, or the unspecified
address, may be used, or the RS may be sent without an SLLAO.
An address collision with a router may cause neighbours'
IsRouter flags for that address to be cleared, however the RA
sent in response will reset the IsRouter flag.
Nick 'Sharkey' Moore Expires: September 2004 [Page 5]
INTERNET-DRAFT Optimistic DAD 23 March 2004
It may be desirable for a Neighbour, for example the router, to
rapidly establish communication with the newly configured
Optimistic Node (ON). To do so, it must learn of the ON's
arrival as soon as possible. To avoid having to wait for
Neighbour Discovery, the ON may wish to send unsolicited
Neighbour Advertisements (with the Override flag set
appropriately), but for this to be effective the Neighbour must
either:
* be expecting the ON to arrive (eg: due to predictive
mechanisms), and thus already have a NC entry for the peer,
in state INCOMPLETE.
* be willing to cache unsolicited NAs (for a short period of
time), so that an entry will have been created with state
STALE.
These modifications are beyond the scope of this draft.
The ON may choose to send unsolicited NAs to the All Nodes Multicast,
to the All Routers Multicast, or Unicast to the source of the RA
which alerted it to this new prefix. This allows flexibility with
regard to Layer 2 multicast transmission costs.
The case where the ON wants to contact its router is handled by the
SLLAO of the RA, where this is supplied. However, the router may
choose not to include the SLLAO (the example given in RFC2462 is "to
facilitate in-bound load balancing over replicated interfaces"). In
this case, the ON cannot discover its router until it is no longer
Tentative. Routers which do not include the SLLAO are not especially
suitable for use with Optimistic DAD.
When the ON wants to contact another neighbour, but it cannot because
the neighbour is not in its NC, it should instead forward the packet
to the router, relying on the router to forward the packet. The
router should then provide the ON with an ICMP redirect, which may
include a Target Link Layer Address Option (TLLAO). If it does, this
will update the ON's NC, and direct communication can begin.
Because Optimistic DAD allows nodes to communicate despite being
Tentative, RetransTimer may be left at the default 1000ms without
significant penalty. It is also possible to increase
DupAddrDetectTransmits and thus reduce the probability of an
undetected address collision due to packet loss.
Nick 'Sharkey' Moore Expires: September 2004 [Page 6]
INTERNET-DRAFT Optimistic DAD 23 March 2004
3. Modifications to RFC-mandated behaviour
3.1 Modifications to RFC 2461 Neighbour Discovery
* (modifies 6.3.7) A node MUST NOT send a Router Solicitation with
an SLLAO from a Tentative address. Router Solicitations SHOULD
be sent from a non-Tentative or the Unspecified address, however
they MAY be sent from a Tentative address as long as the SLLAO
is not included.
* (modifies 7.2.2) A node MUST NOT use a Tentative address as the
source address of a Neighbour Solicitation.
* (modifies 7.2.2) When a node has a unicast packet to send from a
Tentative address to a neighbour, but does not know the
neighbour's link-layer address, it MUST NOT perform Neighbour
Discovery but instead SHOULD forward the packet to the router of
that network.
* (adds to 7.2.6) The Optimistic node MAY send an unsolicited
Neighbour Advertisement to All Nodes when it first configures an
address. The Override flag on this advertisement MUST be cleared
(O=0).
* (adds to 7.2.6) The Optimistic node MAY send an unsolicited NA to
All Nodes when it completes DAD. The Override flag on this
advertisement SHOULD be set (O=1).
3.2 Modifications to RFC 2462 Stateless Address Autoconfiguration
* (modifies 5.5) When an Optimistic node decides to configure an
address, it appends a suffix generated as per Section 3.3 to a
prefix received from a Router Advertisement.
* (modifies 5.4) As soon as the initial Neighbour Solicitation (and
optional unsolicited Neighbour Advertisement) is sent, the
address is configured on the interface and available for use
immediately.
Nick 'Sharkey' Moore Expires: September 2004 [Page 7]
INTERNET-DRAFT Optimistic DAD 23 March 2004
* (modifies 5.4.3) A node MUST reply to a Neighbour Solicitation for
its address from the unspecified address with a Neighbour
Advertisement to the All Nodes address. If the solicitation is
for an address which is still Tentative, the reply MUST have the
Override flag cleared (O=0).
* (modifies 5.4.3) A node MUST reply to a Neighbour Solicitation for
its address from a unicast address, even while Tentative, but
the reply MUST have the Override flag cleared (O=0).
* (modifies 5.4.5) A Tentative address that is determined to be a
duplicate MUST be deconfigured immediately. If the address is a
link-local address formed from an interface identifier based on
the hardware address (e.g. EUI-64), the interface SHOULD be
disabled. Otherwise, if the address was automatically
configured, DAD SHOULD be restarted with a new address generated
as per "Address Generation" below.
* DupAddrDetectTransmits SHOULD be increased where there is a
significant probability of packet loss.
3.3 Address Generation
In order for Optimistic DAD to be a useful optimization, the
probability of a collision must be very small, as a collision may
cause temporary disruption to the collidee, and will require the
collidor to reconfigure.
Some interfaces (for example, Ethernet [RFC2464]) offer methods to
create an address based on a globally unique Interface Identifier,
however it is conceivable that due to manufacturer or user error that
the generated address may not in fact be unique.
* The Optimistic algorithm SHOULD NOT be used on manually configured
addresses, as the probability of collision for manually
configured addresses is considerably higher than that for other
methods.
* If the interface offers a method to create a globally unique IPv6
address from a unique interface identifier, (eg: an EUI-64
Interface Identifier) this address MAY be used for the first
attempt.
Nick 'Sharkey' Moore Expires: September 2004 [Page 8]
INTERNET-DRAFT Optimistic DAD 23 March 2004
* Otherwise, or when creating a new address in the case of a
collision, a new suffix is created. The algorithm used MUST
have a uniform distribution to minimize the chance of address
collision.
* The suffix MAY be chosen using a random number generator.
(see [RFC1750] for more information on random number
generation),
* The suffix MAY be derived from a hash function, as in [SEND-
CGA].
* The algorithm used MAY be one of those documented in
[RFC3041].
* A randomly generated address SHOULD have the Universal/Local bit
and the Individual/Group bit set to 0 to indicate a Unicast
address which is not globally unique (see [RFC2373]).
* The first time DAD fails, a new suffix is generated and the node
SHOULD retry immediately.
* A delay of at least RETRANS_TIMER (as used in [RFC2461])
milliseconds MUST be introduced between further retries, to
minimize the effect of DoS attacks. An exponential backoff
SHOULD be used.
3.4 DAD vs DIID
This section has been removed as the issue has been reviewed for
RFC2462bis.
4. Protocol Operation
The following cases all consider an Optimistic Node (ON) receiving a
Router Advertisement containing a new prefix and deciding to
autoconfigure a new address on that prefix.
The following cases assume that the RA contains a SLLAO, for reasons
explained in Section 2.
The ON will immediately send out a Neighbour Solicitation to
determine if its new address is already in use, and a Neighbour
Advertisement (with the Override flag cleared) for the address. This
Nick 'Sharkey' Moore Expires: September 2004 [Page 9]
INTERNET-DRAFT Optimistic DAD 23 March 2004
NA allows communication with neighbours to begin immediately.
4.1 Simple case
In the non-collision case, the address being configured by the new
node is unused and not present in the Neighbour Caches of any of its
neighbours.
Therefore, there will be no response to its NS, and the NA with O=0
will be sufficient to create Neighbour Cache entries in already
interested neighbours.
The Optimistic Node already has the link-layer address of the router
(from the RA), and the router either already knows the link-layer
address of the ON from the unsolicited NA, or can determine it
through standard NUD. Communications can begin as soon as the router
and the ON have each others' link-layer addresses.
After the appropriate DAD delay, the address is marked as non-
Tentative, and another NA is sent, this time with O=1. This will
ensure that all Neighbour Caches are up-to-date.
4.2 Collision cases
In the simplest collision case, the address being configured by the
new node is already in use by another node, and present in the
Neighbour Caches (NCs) of neighbours which are communicating with
this node.
Since the Optimistic advertisement has O=0, it will not override
existing NC entries. An NA with O=0,S=0 and with a SLLAO may [Note
1], however cause the NC entry to be set to STALE, causing NUD to be
performed on the address.
Nodes with no interest in communicating with the new address "SHOULD"
silently discard the NA [RFC2461 7.2.5], and so will likely be
undisturbed.
If a neighbour is just preparing to begin communication with the
address, eg: it has a NC entry for the address in state 'INCOMPLETE',
the optimistic advertisement may cause an incorrect NC entry to be
created in state 'STALE' and queued packets to be sent to an
incorrect destination.
Nick 'Sharkey' Moore Expires: September 2004 [Page 10]
INTERNET-DRAFT Optimistic DAD 23 March 2004
In general, the defending NA will have the Override flag set (O=1),
and so this will correct the incorrect entry almost immediately.
However, if the defending NA has the Override flag cleared (for
example when the address is in use by proxy) the defending
advertisement will not override this incorrect NC entry. In any case,
the NC entry will remain in state 'STALE', and thus the disruption
will be recoverable, albeit slowly, by the standard Neighbour
Unreachability Detection mechanism.
Of course, in the meantime the ON may have sent packets which
identify it as the owner of its new Tentative address (for example,
Binding Updates in [MIPV6]). This may incur some penalty to the ON,
in the form of broken connections, and some penalty to the rightful
owner of the address, since it will receive (and potentially reply
to) the misdirected packets. It is for this reason that Optimistic
DAD should only be used where the probability of collision is
exceedingly low.
4.3 Interoperation cases
Once the Optimistic Node has completed DAD, it acts exactly like a
Standard node, and so interoperation cases only arise while an
Optimistic Node is Tentative.
If an Optimistic Node attempts to configure an address currently
Tentatively assigned to a Standard Node, the Standard Node will see
the Neighbour Solicitation and deconfigure the address. In contrast,
if a node attempts to configure an address currently Tentatively
assigned to an Optimistic Node, the Optimistic Node will not
deconfigure the address, and instead defend with a Neighbour
Advertisement, causing the newcomer to reconfigure. This gives the
Optimistic Node a slight advantage over Standard nodes, however this
is justified since the Optimistic node may have already established
connections while Tentative.
4.4 Pathological cases
Optimistic DAD suffers from similar problems to Standard DAD, for
example duplicates are not guaranteed to be detected if packets are
lost, and if two nodes configure simultaneously, they may each miss
the other's NS.
These problems exist, and are not gracefully recoverable, in Standard
DAD. The probability of such a collision is reduced in Optimistic DAD
Nick 'Sharkey' Moore Expires: September 2004 [Page 11]
INTERNET-DRAFT Optimistic DAD 23 March 2004
due to the pair of messages (NS, NA) sent. The probability can be
further reduced by increasing the RFC2462 DupAddrDetectTransmits
variable to greater than 1.
This version of Optimistic DAD is dependant on the details of the
router behaviour, eg: if it includes SLLAOs in RAs, and if it is
willing to redirect traffic for the ON. Where the router does not
behave in this way, the behaviour of Optimistic DAD reverts to that
of Standard DAD.
5. Security Considerations
There are existing security concerns with Neighbour Discovery and
Stateless Address Autoconfiguration, and this draft does not purport
to fix them. However, this draft does not significantly increase
security concerns either.
Further work will be required to integrate Optimistic DAD with Secure
Neighbour Discovery [SEND].
Notes
[Note 1] RFC 2461 is unclear on this, with [RFC2461 7.2.5] specifying
"the advertisement prompts future Neighbour Unreachability
Detection [...] by changing the state in the cache entry"
whereas [RFC2461 Appendix C] specifies the state as "unchanged".
Many arguments have been made on the list (see
<ftp://playground.sun.com/pub/ipng/mail-archive/ipng.199912>)
for one interpretation or the other. For the purposes of this
draft, I have assumed that either behaviour is possible.
This issue is to be addressed in RFC2461bis.
Nick 'Sharkey' Moore Expires: September 2004 [Page 12]
INTERNET-DRAFT Optimistic DAD 23 March 2004
RFC References
[RFC1750] D. Eastlake, S. Crocker, J. Schiller. "Randomness
Recommendation for Security." Request for Comments 1750,
Internet Engineering Task Force, December 1994.
[RFC2119] S. Bradner. "Key words for use in RFCs to Indicate
Requirement Levels." Request for Comments (Best Current
Practice) 2119 (BCP 14), Internet Engineering Task Force, March
1997.
[RFC2373] R. Hinden, S. Deering. "IP Version 6 Addressing
Architecture." Request for Comments (Proposed Standard) 2373,
Internet Engineering Task Force, July 1998.
[RFC2461] T. Narten, E.Nordmark, W. Simpson. "Neighbor Discovery for
IP Version 6 (IPv6)." Request for Comments (Draft Standard)
2461, Internet Engineering Task Force, December 1998.
[RFC2462] S. Thomson, T. Narten. "IPv6 Stateless Address
Autoconfiguration." Request for Comments (Draft Standard) 2462,
Internet Engineering Task Force, December 1998.
[RFC2464] M. Crawford. "Transmission of IPv6 Packets over Ethernet
Networks." Request for Comments (Proposed Standard) 2464,
Internet Engineering Task Force, December 1998.
[RFC3041] T. Narten, R. Draves. "Privacy Extensions for Stateless
Address Autoconfiguration in IPv6." Request for Comments
(Proposed Standard) 3041, Internet Engineering Task Force,
January 2001.
Internet Draft References
[MIPV6] D. Johnson, C. Perkins, J. Arkko. Mobility Support in IPv6,
revision 24 (draft-ietf-mobileip-ipv6-24). June 2003 ...
Expired December 2003.
[KOODLI] R. Koodli, C. Perkins. Fast Handovers in Mobile IPv6,
revision 00 (draft-koodli-mobileip-fastv6-00). October 2000 ...
Expired April 2001.
[SOTO] M. Bagnulo, I. Soto, A. Garcia-Martinez, A. Azcorra. Random
generation of interface identifiers, revision 00. (draft-soto-
mobileip-random-iids-00). January 2002 ... Expired July 2002.
Nick 'Sharkey' Moore Expires: September 2004 [Page 13]
INTERNET-DRAFT Optimistic DAD 23 March 2004
[SEND] J. Arkko, J. Kempf, B. Sommerfeld, B.Zill, P. Nikander.
SEcure Neighbor Discovery (SEND), revision 03. (draft-ietf-
send-ndopt-03). January 2004 ... Expires July 2004.
[SEND-CGA] T. Aura, Cryptographically Generated Addresses (CGA),
revision 01. (draft-ietf-send-cga-01). August 1, 2003.
Acknowledgments
Thanks to Greg Daley, Brett Pentland and Ahmet Sekercioglu at Monash
Uni CTIE for their feedback and encouragement. More information is
available at <http://www.ctie.monash.edu.au/ipv6/>.
Thanks to all the MobileIP and IPng/IPv6 WG members who contributed
to the debate. Especially and alphabetically: Jari Arkko, JinHyeock
Choi, Youn-Hee Han, James Kempf, Thomas Narten, Richard Nelson, Pekka
Nikander, Soohong 'Daniel' Park, Ed Remmel, Pekka Savola, Hesham
Soliman, Ignatious Souvatzis, Jinmei Tatuya, Pascal Thubert,
Vladislav Yasevich and Alper Yegin.
This work has been supported by the Australian Telecommunications
Cooperative Research Centre (ATcrc)
<http://www.telecommunications.crc.org.au/>
Author's Address:
Nick 'Sharkey' Moore
<nick.moore@eng.monash.edu.au> or <sharkey@zoic.org>
Centre for Telecommunications and Information Engineering
Monash University 3800
Victoria, Australia
Nick 'Sharkey' Moore Expires: September 2004 [Page 14]
