IPv6 Working Group                                 Nick 'Sharkey' Moore
INTERNET-DRAFT                                   Monash University CTIE
                                                      09 September 2004




            Optimistic Duplicate Address Detection for IPv6
                <draft-ietf-ipv6-optimistic-dad-02.txt>



Status of this Memo


   By submitting this Internet-Draft, I certify that any applicable
   patent or other IPR claims of which I am aware have been disclosed,
   or will be disclosed, and any of which I become aware will be
   disclosed, in accordance with RFC 3668.


   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 to cite them other than as "work in progress."


   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt


   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.


Copyright Notice


   Copyright (C) The Internet Society (2004).  All Rights Reserved.



Abstract


   Optimistic Duplicate Address Detection is an interoperable
   modification of the existing IPv6 Neighbor Discovery (RFC2461) and
   Stateless Address Autoconfiguration (RFC2462) process.  The intention
   is to minimize address configuration delays in the successful case,
   to reduce disruption as far as possible in the failure case and to
   remain interoperable with unmodified hosts and routers.






Nick 'Sharkey' Moore     Expires: 09 April 2005                 [Page 1]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



Table of Contents


   Status of this Memo .........................................  1
   Abstract ....................................................  1
   Table of Contents ...........................................  2
   1. Introduction .............................................  3
           1.1 Problem Statement ...............................  3
           1.2 History .........................................  4
           1.3 Definitions .....................................  4
           1.4 Abbreviations ...................................  5
   2. Optimistic Behaviours ....................................  6
           2.1 Probability of Collision ........................  6
           2.2 Optimistic Address Flag .........................  6
           2.3 Avoiding Disruption .............................  7
           2.4 Router Redirection ..............................  7
   3. Modifications to RFC-compliant behaviour .................  8
           3.1 Modifications to RFC 2461 Neighbor Discovery ....  8
           3.2 Modifications to RFC 2462 SAA ...................  9
   4. Protocol Operation ....................................... 10
           4.1 Simple case ..................................... 10
           4.2 Collision case .................................. 11
           4.3 Interoperation cases ............................ 11
           4.4 Pathological cases .............................. 12
   5. Security Considerations .................................. 12
   6. IANA Considerations ...................................... 12
   Normative References ........................................ 13
   Informative References ...................................... 13
   Author's Address ............................................ 14
   Acknowledgments ............................................. 14
   Full Copyright Statement .................................... 14
   Intellectual Property Statement ............................. 15
   Disclaimer of Validity ...................................... 15




















Nick 'Sharkey' Moore     Expires: 09 April 2005                 [Page 2]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



1. Introduction


   Optimistic Duplicate Address Detection (DAD) is a modification of the
   existing IPv6 Neighbor 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
   Neighbor Discovery while their addresses are still Optimistic.


   It is not the intention of this memo to improve the security,
   reliability or robustness of DAD beyond that of existing standards,
   merely to provide a method to make it faster.



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.









Nick 'Sharkey' Moore     Expires: 09 April 2005                 [Page 3]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



1.2 History



   There is some precedent for this work in previous Internet 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.  An issues
   list was presented at IETF-60.


   Working implementations of draft versions of this memo have been made
   by the author as a freely-available patch to Linux 2.4.18, and by Ed
   Remmel of Elmic Systems.


   An implementation of this version by the author is in progress, and
   will be released as a freely-available patch to Linux 2.6.7.


1.3 Definitions


   Definitions of requirements keywords ('MUST NOT', 'SHOULD NOT',
   'MAY', 'SHOULD', 'MUST') are in accordance with the IETF Best Current
   Practice - RFC2119 [RFC2119]


   Address Resolution - Process defined by [RFC2461] section 7.2.


   Neighbor Unreachability Detection - Process defined by [RFC2461]
        section 7.3.


   Tentative Address - an address for which a node has not yet completed
        DAD is regarded as Tentative: a single Neighbor Solicitation for
        this address or a single Neighbor Advertisement defending this
        address will cause the node to deconfigure the address and cease
        using it.


   Deprecated Address - an address which should not be used if an
        alternative is available.


   Optimistic Address - an address which is available for use despite
        DAD not being fully complete.  This memo places restrictions on
        the use of Optimistic Addresses.


   Preferred Address - an address which is neither Tentative, Deprecated
        or Optimistic.





Nick 'Sharkey' Moore     Expires: 09 April 2005                 [Page 4]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



   Optimistic Node - An Optimistic Node is one which is compliant with
        the rules specified in this memo.


   Standard Node - 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.


   Neighbors - 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 - Neighbor Advertisement.  See [RFC2461] sections 4.4 and 7.


   NC - Neighbor Cache.  See [RFC2461] section 5.1 and 7.3.


   ND - Neighbor Discovery.  The process described in [RFC2461]


   NS - Neighbor Solicitation.  See [RFC2461] sections 4.3 and 7.


   ON - Optimistic Node.  A node which is behaving according to the
        rules of this memo.


   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]


   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 and Neighbor Advertisements.  See [RFC2461] sections
        4.4, 4.5 and 4.6.1.






Nick 'Sharkey' Moore     Expires: 09 April 2005                 [Page 5]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



2. Optimistic DAD Behaviours



   This section provides some discussion of Optimistic DAD Behaviours.
   Section 3 provides more specific information on changes to RFC-
   mandated behaviours.



2.1 Probability of Collision


   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.



2.2 Optimistic Addresses


   [RFC2462] introduces the concept of Tentative (in 5.4) and Deprecated
   (in 5.5.4) Addresses.  Addresses which are neither are said to be
   Preferred.  Tentative addresses may not be used for communication,
   and Deprecated addresses should not be used for new communications.
   These address states may also be used by other standards documents,
   for example Default Address Selection [RFC3484].


   This memo introduces a new address state, 'Optimistic', which is used
   to mark an address which is available for use but which has not
   completed DAD.  Protocols which do not understand this state should
   treat it equivalently to 'Deprecated', to indicate that the address
   is available for use but should not be used if another suitable
   address is available.  If address states are recorded as individual
   flags, this can easily be achieved by setting 'Deprecated' when
   'Optimistic' is set.  In any case, it is important to note that the
   address lifetime rules of [RFC2462] still apply, and so an address
   may be Deprecated as well as Optimistic.  When DAD completes without
   incident, the address becomes a Preferred or Deprecated address, as
   per [RFC2462].










Nick 'Sharkey' Moore     Expires: 09 April 2005                 [Page 6]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



2.3 Avoiding Disruption


   In order to avoid interference, it is important that an Optimistic
   node does not send any messages from an Optimistic Address which will
   override its neighbors' Neighbor 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 Neighbor Advertisements for
        Optimistic addresses, which prevents neighbors from overriding
        their existing NC entries. The 'Override' flag is already
        defined [RFC2461] and used for Proxy Neighbor Advertisement.


   * Never sending Neighbor Solicitations from an Optimistic Address.
        NSs include a Source Link Layer Address Option (SLLAO), which
        may cause Neighbor Cache disruption.  NSs sent as part of DAD
        are sent from the unspecified address, without a SLLAO.


   * Never using a Optimistic Address as the source address of a Router
        Solicitation with a SLLAO.  Another address, or the unspecified
        address, may be used, or the RS may be sent without a SLLAO.


        An address collision with a router may cause neighboring
        router's IsRouter flags for that address to be cleared.
        However, routers do not appear to use the IsRouter flag for
        anything, and the NA sent in response to the collision will
        reassert the IsRouter flag.



2.4 Router Redirection


   When the ON wants to contact another neighbor, but it cannot because
   the neighbor 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.
   Implementing this behaviour may be difficult and unnecessary, so it
   is left as an option to the implementor.











Nick 'Sharkey' Moore     Expires: 09 April 2005                 [Page 7]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



3. Modifications to RFC-mandated behaviour



3.1 Modifications to RFC 2461 Neighbor Discovery



   * (modifies 6.3.7)  A node MUST NOT send a Router Solicitation with a
        SLLAO from an Optimistic Address.  Router Solicitations SHOULD
        be sent from a non-Optimistic or the Unspecified Address,
        however they MAY be sent from an Optimistic Address as long as
        the SLLAO is not included.


   * (modifies 7.2.2)  A node MUST NOT use an Optimistic Address as the
        source address of a Neighbor Solicitation.


   * If the ON isn't told the SLLAO of the router in an RA, and it
        cannot determine this information without breaching the rules
        above, it MUST wait until DAD completes despite being unable to
        send any packets to the router.


   * (modifies 7.2.2)  When a node has a unicast packet to send from an
        Optimistic Address to a neighbor, but does not know the
        neighbor's link-layer address, it MUST NOT perform Address
        Resolution. It SHOULD forward the packet to a default router on
        the link in the hope that the packet will be redirected.
        Otherwise it SHOULD buffer the packet until DAD is complete.


























Nick 'Sharkey' Moore     Expires: 09 April 2005                 [Page 8]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



3.2 Modifications to RFC 2462 Stateless Address Autoconfiguration



   * (modifies 5.5) A host MAY choose to configure a new address as an
        Optimistic Address.  A host which does not know the SLLAO of its
        router SHOULD NOT configure a new address as Optimistic.  A
        router MUST NOT configure an Optimistic Address.


   * (modifies 5.4)  As soon as the initial Neighbor Solicitation is
        sent, the Optimistic Address is configured on the interface and
        available for use immediately.  The address MUST be flagged as
        'Optimistic'.  Protocols which do not understand this state
        SHOULD treat it equivalently to 'Deprecated'.


   * When the DAD completes for an Optimistic Address, the address is no
        longer Optimistic and it becomes Preferred or Deprecated
        according to the rules of [RFC2462].


   * (modifies 5.4.3) The node MUST NOT reply to a Neighbor Solicitation
        for an Optimistic Address from the unspecified address.  This NS
        indicates that the address is a duplicate, and it MUST be
        deconfigured as per the behaviour specified in RFC2462 for
        Tentative addresses.


   * (modifies 5.4.3) The node MUST reply to a Neighbor Solicitation for
        an Optimistic Address from a unicast address, but the reply MUST
        have the Override flag cleared (O=0).

























Nick 'Sharkey' Moore     Expires: 09 April 2005                 [Page 9]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



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 ON will immediately send out a Neighbor Solicitation to determine
   if its new address is already in use.



4.1 Simple case


   In the non-collision case, the address being configured by the new
   node is unused and not present in the Neighbor Caches of any of its
   neighbors.


   There will be no response to its NS (sent from ::), and this NS will
   not modify the state of neighbors' Neighbor Caches.


   The Optimistic Node already has the link-layer address of the router
   (from the RA), and the router can determine the link-layer address of
   the ON through standard Address Resolution.  Communications can begin
   as soon as the router and the ON have each others' link-layer
   addresses.


   After the appropriate DAD delay has completed, the address is no
   longer Optimistic, and becomes either Preferred or Deprecated as per
   RFC2462.























Nick 'Sharkey' Moore     Expires: 09 April 2005                [Page 10]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



4.2 Collision case


   In the collision case, the address being configured by the new node
   is already in use by another node, and present in the Neighbor Caches
   (NCs) of neighbors which are communicating with this node.


   The NS sent by the ON has the unspecified source address, ::, and no
   SLLAO.  This NS will not cause changes to the NC entries of
   neighboring hosts.


   The ON will hopefully already know all it needs to about the router
   from the initial RA.  However, if it needs to it can still send an RS
   to ask for more information, but it may not include a SLLAO.  This
   forces a broadcast response from the router, but will not disrupt
   other nodes' NCs.


   In the course of establishing connections, the ON may send NAs either
   spontaneously or in response to received NSs.  Since these NAs will
   have O=0, they will not override existing NC entries, although they
   may result in a colliding entry being changed to state STALE.  This
   change is recoverable through standard NUD.


   Of course, in the meantime the ON may have sent packets which
   identify it as the owner of its new Optimistic 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 very
   low.



4.3 Interoperation cases


   Once the Optimistic Address has completed DAD, it acts exactly like a
   normal address, and so interoperation cases only arise while the
   address is Optimistic.


   If an Optimistic Node attempts to configure an address currently
   Tentatively assigned to a Standard Node, the Standard Node will see
   the Neighbor Solicitation and deconfigure the address.


   If a node attempts to configure an Optimistic Node's Optimistic
   Address, the Optimistic Node will see the NS and deconfigure the
   address.







Nick 'Sharkey' Moore     Expires: 09 April 2005                [Page 11]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



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.


   These problems exist, and are not gracefully recoverable, in Standard
   DAD.  Their probability in both Optimistic and Standard DAD can be
   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: that the router includes SLLAOs in RAs, and
   that the router is willing to redirect traffic for the ON.  Where the
   router does not behave in this way, the behaviour of Optimistic DAD
   inherently reverts to that of Standard DAD.


5. Security Considerations


   There are existing security concerns with Neighbor Discovery and
   Stateless Address Autoconfiguration, and this memo does not purport
   to fix them.  However, this memo does not significantly increase
   security concerns either.


   Further work will be required to integrate Optimistic DAD with Secure
   Neighbor Discovery [SEND].



6. IANA Considerations


   This document has no actions for IANA.





















Nick 'Sharkey' Moore     Expires: 09 April 2005                [Page 12]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



Normative References



   [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.


   [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.



Informative References



   [RFC3484] R. Draves. "Default Address Selection for Internet Protocol
        version 6 (IPv6)".  Request for Comments (Proposed Standard)
        3484, Internet Engineering Task Force, February 2003.


   [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.


   [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.













Nick 'Sharkey' Moore     Expires: 09 April 2005                [Page 13]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



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


   Comments should be sent to either of the above email addresses.



Acknowledgments


   Thanks to Greg Daley, Brett Pentland, Richard Nelson and Ahmet
   Sekercioglu at Monash Uni CTIE for their feedback and encouragement.
   More information is available at:
        <http://www.ctie.monash.edu.au/ipv6/fastho/>


   Thanks to all the MobileIP and IPng/IPv6 WG members who have
   contributed to the debate.  Especially and alphabetically: Jari
   Arkko, JinHyeock Choi, Youn-Hee Han, James Kempf, Thomas Narten,
   Richard Nelson, Pekka Nikander, Erik Nordmark, Soohong 'Daniel' Park,
   Ed Remmel, Pekka Savola, Hesham Soliman, Ignatious Souvatzis, Jinmei
   Tatuya, Dave Thaler, 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/>


   Funding for the RFC Editor function is currently provided by the
   Internet Society.


Full Copyright Statement



   Copyright (C) The Internet Society (2004).  This document is subject
   to the rights, licenses and restrictions contained in BCP 78 and
   except as set forth therein, the authors retain all their rights.













Nick 'Sharkey' Moore     Expires: 09 April 2005                [Page 14]


INTERNET-DRAFT               Optimistic DAD            09 September 2004



Intellectual Property Statement



   The IETF takes no position regarding the validity or scope of any
   intellectual property or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; neither does it represent that it
   has made any effort to identify any such rights. Information on the
   IETF's procedures with respect to rights in IETF Documents can be
   found in BCP 78 and 79.


   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.


   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights which may cover technology that may be required to implement
   this standard. Please address the information to the IETF at ietf-
   ipr@ietf.org.



Disclaimer of Validity



   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
   ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
   INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
   INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
















Nick 'Sharkey' Moore     Expires: 09 April 2005                [Page 15]