[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04

IPv6 Working Group                                 Nick 'Sharkey' Moore
INTERNET-DRAFT                                   Monash University CTIE
                                                            13 Feb 2004



                 Optimistic Duplicate Address Detection
                <draft-moore-ipv6-optimistic-dad-04.txt>


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:  August 2004                 [Page 1]

INTERNET-DRAFT               Optimistic DAD                  13 Feb 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
   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:  August 2004                 [Page 2]

INTERNET-DRAFT               Optimistic DAD                  13 Feb 2004


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:  August 2004                 [Page 3]

INTERNET-DRAFT               Optimistic DAD                  13 Feb 2004


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:  August 2004                 [Page 4]

INTERNET-DRAFT               Optimistic DAD                  13 Feb 2004


   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:  August 2004                 [Page 5]

INTERNET-DRAFT               Optimistic DAD                  13 Feb 2004


   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 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 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:  August 2004                 [Page 6]

INTERNET-DRAFT               Optimistic DAD                  13 Feb 2004


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:  August 2004                 [Page 7]

INTERNET-DRAFT               Optimistic DAD                  13 Feb 2004


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

        + The suffix MAY be chosen using a well-distributed random
             algorithm (see [RFC1750] for more information on random
             number generation),

        + The suffix MAY be derived from a well-distributed 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 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:  August 2004                 [Page 8]

INTERNET-DRAFT               Optimistic DAD                  13 Feb 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 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:  August 2004                 [Page 9]

INTERNET-DRAFT               Optimistic DAD                  13 Feb 2004


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:  August 2004                [Page 10]

INTERNET-DRAFT               Optimistic DAD                  13 Feb 2004


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:  August 2004                [Page 11]

INTERNET-DRAFT               Optimistic DAD                  13 Feb 2004


   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.


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:  August 2004                [Page 12]

INTERNET-DRAFT               Optimistic DAD                  13 Feb 2004


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.

   [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 Richard Nelson at 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 WG members who contributed to the
   debate.

   This work has been supported by the Australian Telecommunications
   Cooperative Research Centre (AT-CRC)
   <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:  August 2004                [Page 13]


Html markup produced by rfcmarkup 1.107, available from http://tools.ietf.org/tools/rfcmarkup/