IPv6 Working Group Nick 'Sharkey' Moore INTERNET-DRAFT Monash University CTIE 8 September 2003 Optimistic Duplicate Address Detection Status of this Memo This document is an Internet-Draft and is in full conformance with 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 This document is an individual submission to the IETF. Comments should be directed to the author. Definitions of requirements keywords are in accordance with the IETF Best Current Practice - RFC2119 [RFC2119] Abstract Optimistic DAD 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: 8 March 2004 [Page 1] INTERNET-DRAFT Optimistic DAD 8 September 2003 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 2. Optimistic Behaviours .................................... 4 3. Modifications to RFC-compliant behaviour ................. 6 3.1 Modifications to RFC 2461 Neighbour Discovery ... 6 3.2 Modifications to RFC 2462 SAA ................... 7 3.3 Address Generation............................... 7 3.4 DIID vs DAD ..................................... 8 4. Protocol Operation ....................................... 9 4.1 Simple case ..................................... 9 4.2 Collision case .................................. 10 4.3 Interoperation cases ............................ 11 4.4 Pathological cases .............................. 11 5. Security Considerations .................................. 11 Notes / References .......................................... 12 Acknowledgments ............................................. 13 Author's Address ............................................ 13 1. Introduction Optimistic DAD is a 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, 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: 8 March 2004 [Page 2] INTERNET-DRAFT Optimistic DAD 8 September 2003 1.1 Problem Statement IPv6 ND and SAA processes provide adequate collision detection mechanisms for the static hosts they were designed for. However, they do not provide sufficient speed or flexibility for nodes which need to maintain network access despite frequently moving network attachment. An optimized DAD method needs to: * provide interoperability with nodes using the current standards. * remove the RETRANS_TIMER 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 large enough to guarantee detection of a collision are large enough to cause disruption to 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. This work was presented by the author at the MobileIP WG at IETF-56. Working implementations of version -02 of this draft have been made by the author as a patch to Linux 2.4.18, and by Ed Remmel of Elmic Systems. Nick 'Sharkey' Moore Expires: 8 March 2004 [Page 3] INTERNET-DRAFT Optimistic DAD 8 September 2003 1.3 Definitions Tentative - an address for which a node has not 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. Well-Distributed Address - Address suffixes used for Optimistic DAD should be well distributed, eg: there should be an equal probability of any given suffix occuring. This minimizes the probability of an address collision. 2. Optimistic Behaviours Optimistic DAD is only a useful optimisation 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. Nick 'Sharkey' Moore Expires: 8 March 2004 [Page 4] INTERNET-DRAFT Optimistic DAD 8 September 2003 This is achieved by: * clearing the 'Override' bit in Neighbour Advertisements for Tentative addresses, which prevents neighbours from overriding their existing NC entries. The 'Override' bit 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, 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 send 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 reponse will reset the IsRouter flag. It may be desirable for a Neighbour, for example the router, to rapidly establish communication with the newly configured 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 Override 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. however, 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. Nick 'Sharkey' Moore Expires: 8 March 2004 [Page 5] INTERNET-DRAFT Optimistic DAD 8 September 2003 When the MN wants to contact another neighbour, but it cannot because the neighbour is not in the NC, it should instead forward the packet to the router, relying on the router to forward the packet. The router should then provide the MN with a 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. 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. * (modfies 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 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 set to 0. * (adds to 7.2.6) The Optimistic node SHOULD send an unsolicited NA to All Nodes when it completes DAD. The Override flag on this advertisement SHOULD be set to 1. Nick 'Sharkey' Moore Expires: 8 March 2004 [Page 6] INTERNET-DRAFT Optimistic DAD 8 September 2003 3.2 Modifications to RFC 2462 Stateless Address Autoconfiguration * (modifies 5.5) If an initial suffix is not supplied, a new suffix SHOULD be generated as per "Address Generation" below. * (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. * (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 set to 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 set to 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 a fixed interface identifier, 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 for other methods. Nick 'Sharkey' Moore Expires: 8 March 2004 [Page 7] INTERNET-DRAFT Optimistic DAD 8 September 2003 * If the interface offers a method to create a supposedly globally unique IPv6 address, this address MAY be used for the initial attempt. * Otherwise, or when creating a new address in the case of a collision, a well-distributed suffix MUST be chosen, based on a random algorithm (see [RFC1750] for more information on random number generation), or generated cryptographically (see [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 not globally unique Unicast address (see [RFC2373]). * In order to minimize the effect of DoS attacks, a delay of at least RETRANS_TIMER (as used in [RFC2461]) milliseconds MUST be introduced between attempts if DAD has already failed more than once. An exponential backoff SHOULD be used. 3.4 DAD vs DIID Existing standards assume that addresses are generated from unchanging Interface Identifiers, and thus RFC 2462 states: [5.4] Each individual unicast address SHOULD be tested for uniqueness. However, when stateless address autoconfiguration is used, address uniqueness is determined solely by the interface identifier [...] Thus, for a set of addresses formed from the same interface identifier, it is sufficient to check that the link- local address generated from the identifier is unique on the link. However, this approach (generally referred to as 'DIID') has fallen from favour in recent years, in favour of checking individual addresses. In order to minimize the probability of an undetected address collision, it would seem prudent to always configure and check the link-local address for any given suffix as well as checking the actual address being configured. Nick 'Sharkey' Moore Expires: 8 March 2004 [Page 8] INTERNET-DRAFT Optimistic DAD 8 September 2003 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 LLAO. The router "MAY omit this option in order to enable inbound load sharing" [RFC2461 4.2], however, and in this case the ON will be unable to contact the router until the address is no longer Tentative. The ON will immediately send out a Neighbour Solicitation to determine if its new address is already in use, and a Neighbour Advertisement (with Override set to 0) for the address. This 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. Communicatations 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. Nick 'Sharkey' Moore Expires: 8 March 2004 [Page 9] INTERNET-DRAFT Optimistic DAD 8 September 2003 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 no LLAO 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. In general, the defending NA will have Override set to 1, and so this will correct the incorrect entry almost immediately. However, if the defending NA has Override set to 0 (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. Nick 'Sharkey' Moore Expires: 8 March 2004 [Page 10] INTERNET-DRAFT Optimistic DAD 8 September 2003 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 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. Nick 'Sharkey' Moore Expires: 8 March 2004 [Page 11] INTERNET-DRAFT Optimistic DAD 8 September 2003 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 ) for one interpretation or the other. For the purposes of this draft, I have assumed that either behaviour is possible. 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. Nick 'Sharkey' Moore Expires: 8 March 2004 [Page 12] INTERNET-DRAFT Optimistic DAD 8 September 2003 Internet Draft References [MIPV6] D. Johnson, C. Perkins, J. Arkko. Mobility Support in IPv6, revision 18 (draft-ietf-mobileip-ipv6-18). July 2002 ... Expired December 2002. [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. [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 Richard Nelson at CTIE for their feedback and encouragement. More information is available at . Thanks to all the MobileIP and IPng WG members who contributed to the debate. This work has been supported by the Australian Telecommunications Cooperative Research Centre (AT-CRC) Author's Address: Nick 'Sharkey' Moore or Centre for Telecommunications and Information Engineering Monash University 3800 Victoria, Australia Nick 'Sharkey' Moore Expires: 8 March 2004 [Page 13]