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

Versions: 00 01 02 03 04 draft-ietf-ipv6-optimistic-dad

IPv6 Working Group                                 Nick 'Sharkey' Moore
INTERNET-DRAFT                                   Monash University CTIE
                                                       14 November 2002



                 Optimistic Duplicate Address Detection
                <draft-moore-ipv6-optimistic-dad-01.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.








Nick 'Sharkey' Moore      Expires: 14 June 2003                 [Page 1]


INTERNET-DRAFT               Optimistic DAD             14 November 2002


Table of Contents

   Status of this Memo..........................................  1
   Abstract.....................................................  1
   Table of Contents............................................  2
   1. Introduction..............................................  2
           1.1 Definitions......................................  3
   2. Modifications to RFC-compliant behaviour..................  3
           2.1 Modifications to RFC 2461 Neighbour Discovery....  4
           2.2 Modifications to RFC 2462 SAA....................  5
           2.3 Address Generation...............................  5
   3. Protocol Operation........................................  6
           3.1 Simple case......................................  7
           3.2 Collision case...................................  7
           3.3 Interoperation cases.............................  8
           3.4 Pathological cases...............................  8
   4. Security Considerations...................................  9
   Notes / References ..........................................  9
   Acknowledgments.............................................. 10
   Author's Address............................................. 10


1. Introduction


   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.

   Optimistic DAD is a useful optimization because for a DAD is far more
   likely to succeed than fail for randomly autoconfigured addresses, by
   a factor of at least 10,000,000,000 to one [SOTO].  This makes it
   worth a little disruption in the failure case to provide faster
   handovers in the successful case, as long as the disruption is easily
   recoverable.

   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.

   There is some precedent for this work in previous drafts [KOODLI],
   and in discussions in the mobile-ip 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 'normal' nodes.



Nick 'Sharkey' Moore      Expires: 14 June 2003                 [Page 2]


INTERNET-DRAFT               Optimistic DAD             14 November 2002


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

   Normal - A Normal 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.


2. Modifications to RFC-compliant behaviour


   Optimistic DAD is only an optimisation where the probability of
   collision is extremely small.  As such, the Optimistic algorithm
   SHOULD NOT be used for manually assigned addresses, where the
   collision probability is likely to be much higher due to human error.

   Modifications are required only to Optimistic nodes -- Optimistic
   nodes will interoperate with Normal 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' 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.





Nick 'Sharkey' Moore      Expires: 14 June 2003                 [Page 3]


INTERNET-DRAFT               Optimistic DAD             14 November 2002


   * Never attaching a Source Link-Layer Address Option to NSs or RSs
        sent from a Tentative address. This will cause some extra
        signalling if an Optimistic node attempts to establish a
        connection with a neighbour while Tentative, but it prevents the
        overriding of neighbours' NC entries in the collision case.

   For a Neighbour to rapidly establish communication with the newly
   configured ON, 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 All Nodes, or
   specifically to the source of the RA which alerted it to this new
   prefix.


2.1 Modifications to RFC 2461 Neighbour Discovery


   * (modifies 7.2.2)  When a Optimistic node sends a Neighbour
        Solicitation or Router Solicitation while Tentative, it MUST NOT
        include the Source Link Layer Address Option.

   * (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: 14 June 2003                 [Page 4]


INTERNET-DRAFT               Optimistic DAD             14 November 2002


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


2.3 Address Generation


   In order for Optimistic DAD to be a useful optimization, the
   probability of a collision must be very small, and the probability of
   multiple collisions even smaller.

   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 MUST 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: 14 June 2003                 [Page 5]


INTERNET-DRAFT               Optimistic DAD             14 November 2002


   * 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 suffix MUST be chosen based on a strongly random
        algorithm (see [RFC1750] for more information on random number
        generation).

   * 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. 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 extra NS/NA messages would
   have to be sent.


   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.













Nick 'Sharkey' Moore      Expires: 14 June 2003                 [Page 6]


INTERNET-DRAFT               Optimistic DAD             14 November 2002


3.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 now has the link-layer address of the
   Optimistic Node (or at least, can find it through standard NUD).
   Communications can begin immediately.

   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.


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



Nick 'Sharkey' Moore      Expires: 14 June 2003                 [Page 7]


INTERNET-DRAFT               Optimistic DAD             14 November 2002


   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 Optimisitc
   DAD should only be used where the probability of collision is
   exceedingly low.


3.3 Interoperation cases


   Once the Optimistic Node has completed DAD, it acts exactly like a
   Normal 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 Normal Node, the Normal 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 Normal nodes, however this is
   justified since the Optimistic node may have already established
   connections while Tentative.



3.4 Pathological cases


   Optimistic DAD suffers from similar problems to Normal 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 Normal
   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.




Nick 'Sharkey' Moore      Expires: 14 June 2003                 [Page 8]


INTERNET-DRAFT               Optimistic DAD             14 November 2002


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



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.





Nick 'Sharkey' Moore      Expires: 14 June 2003                 [Page 9]


INTERNET-DRAFT               Optimistic DAD             14 November 2002


   [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 18 (draft-ietf-mobileip-ipv6-18). July 2002 ...
        Expires 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.


Acknowledgments

   Thanks to Greg Daley and Richard Nelson at CTIE for their feedback
   and encouragement.

   Thanks to all the mobile-ip list members who contributed to the
   debate, especially Pekka Savola, Hesham Soliman, Ignatious Souvatzis
   and Vladislav Yasevich for their constructive criticism.

   This work has been supported by the Australian Telecommunications
   Cooperative Research Centre (AT-CRC) <http://www.atcrc.com/>


Author's Address:

   <nick.moore@monash.edu>   <http://www.ctie.monash.edu.au/ipv6/>

   Nick 'Sharkey' Moore
   Centre for Telecommunications and Information Engineering
   Monash University 3800
   Victoria, Australia




Nick 'Sharkey' Moore      Expires: 14 June 2003                [Page 10]


Html markup produced by rfcmarkup 1.129b, available from https://tools.ietf.org/tools/rfcmarkup/