idnits 2.17.1 draft-ietf-ipv6-optimistic-dad-07.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 14. -- Found old boilerplate from RFC 3978, Section 5.5 on line 690. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 667. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 674. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 680. ** Found boilerplate matching RFC 3978, Section 5.4, paragraph 1 (on line 652), which is fine, but *also* found old RFC 2026, Section 10.4C, paragraph 1 text on line 34. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (22 December 2005) is 6693 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 2461 (Obsoleted by RFC 4861) ** Obsolete normative reference: RFC 2462 (Obsoleted by RFC 4862) -- Obsolete informational reference (is this intentional?): RFC 3041 (Obsoleted by RFC 4941) -- Obsolete informational reference (is this intentional?): RFC 3315 (Obsoleted by RFC 8415) -- Obsolete informational reference (is this intentional?): RFC 3484 (Obsoleted by RFC 6724) -- Obsolete informational reference (is this intentional?): RFC 3775 (Obsoleted by RFC 6275) Summary: 6 errors (**), 0 flaws (~~), 3 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 IPv6 Working Group Nick 'Sharkey' Moore 3 INTERNET-DRAFT Monash University CTIE 4 22 December 2005 6 Optimistic Duplicate Address Detection for IPv6 7 9 Status of this Memo 11 By submitting this Internet-Draft, each author represents that any 12 applicable patent or other IPR claims of which he or she is aware 13 have been or will be disclosed, and any of which he or she becomes 14 aware will be disclosed, in accordance with Section 6 of BCP 79. 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note that 18 other groups may also distribute working documents as Internet- 19 Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six months 22 and may be updated, replaced, or obsoleted by other documents at any 23 time. It is inappropriate to use Internet-Drafts as reference 24 material or to cite them other than as "work in progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html. 32 Copyright Notice 34 Copyright (C) The Internet Society (2005). All Rights Reserved. 36 Abstract 38 Optimistic Duplicate Address Detection is an interoperable 39 modification of the existing IPv6 Neighbor Discovery (RFC2461) and 40 Stateless Address Autoconfiguration (RFC2462) process. The intention 41 is to minimize address configuration delays in the successful case, 42 to reduce disruption as far as possible in the failure case and to 43 remain interoperable with unmodified hosts and routers. 45 Table of Contents 47 Status of this Memo ......................................... 1 48 Abstract .................................................... 1 49 Table of Contents ........................................... 2 50 1. Introduction ............................................. 3 51 1.1 Problem Statement ............................... 3 52 1.2 Definitions ..................................... 4 53 1.3 Address Types ................................... 4 54 1.4 Abbreviations ................................... 5 55 2. Optimistic Behaviours .................................... 6 56 2.1 Optimistic Addresses ............................ 6 57 2.2 Avoiding Disruption ............................. 6 58 2.3 Router Redirection .............................. 7 59 2.4 Contacting the Router ........................... 7 60 3. Modifications to RFC-compliant behaviour ................. 8 61 3.1 General ......................................... 8 62 3.2 Modifications to RFC 2461 Neighbor Discovery .... 8 63 3.3 Modifications to RFC 2462 SLAAC ................. 9 64 4. Protocol Operation ....................................... 10 65 4.1 Simple case ..................................... 10 66 4.2 Collision case .................................. 11 67 4.3 Interoperation cases ............................ 12 68 4.4 Pathological cases .............................. 12 69 5. Security Considerations .................................. 13 70 6. IANA Considerations ...................................... 13 71 Appendix A: Probability of Collision ........................ 14 72 A.1 The Birthday Paradox ............................ 14 73 A.2 Individual Moving Nodes ......................... 15 74 Normative References ........................................ 16 75 Informative References ...................................... 16 76 Author's Address ............................................ 17 77 Acknowledgments ............................................. 17 78 Full Copyright Statement .................................... 17 79 Intellectual Property Statement ............................. 18 80 Disclaimer of Validity ...................................... 18 82 1. Introduction 84 Optimistic Duplicate Address Detection (DAD) is a modification of the 85 existing IPv6 Neighbor Discovery (ND) [RFC2461] and Stateless Address 86 Autoconfiguration (SLAAC) [RFC2462] process. The intention is to 87 minimize address configuration delays in the successful case, and to 88 reduce disruption as far as possible in the failure case. 90 Optimistic DAD is a useful optimization because in most cases DAD is 91 far more likely to succeed than fail. This is discussed further in 92 Appendix A. Disruption is minimized by limiting nodes' participation 93 in Neighbor Discovery while their addresses are still Optimistic. 95 It is not the intention of this memo to improve the security, 96 reliability or robustness of DAD beyond that of existing standards, 97 merely to provide a method to make it faster. 99 1.1 Problem Statement 101 The existing IPv6 address configuration mechanisms provide adequate 102 collision detection mechanisms for the fixed hosts they were designed 103 for. However, a growing population of nodes need to maintain 104 continuous network access despite frequently changing their network 105 attachment. Optimizations to the DAD process are required to provide 106 these nodes with sufficiently fast address configuration. 108 An optimized DAD method needs to: 110 * provide interoperability with nodes using the current standards. 112 * remove the RetransTimer delay during address configuration. 114 * ensure the probability of address collision is not increased. 116 * improve the resolution mechanisms for address collisions. 118 * minimize disruption in the case of a collision. 120 It is not sufficient to merely reduce RetransTimer in order to reduce 121 the handover delay, as values of RetransTimer long enough to 122 guarantee detection of a collision are too long to avoid disruption 123 of time-critical services. 125 1.2 Definitions 127 Definitions of requirements keywords ('MUST NOT', 'SHOULD NOT', 128 'MAY', 'SHOULD', 'MUST') are in accordance with the IETF Best Current 129 Practice - RFC2119 [RFC2119] 131 Address Resolution - Process defined by [RFC2461] section 7.2. 133 Neighbor Unreachability Detection - Process defined by [RFC2461] 134 section 7.3. 136 Optimistic Node - An Optimistic Node is one that is compliant with 137 the rules specified in this memo. 139 Standard Node - A Standard Node is one which is compliant with RFCs 140 2461 and 2462. 142 Link - A communication facility or medium over which nodes can 143 communicate at the link layer. 145 Neighbors - Nodes on the same link, which may therefore be competing 146 for the same IP addresses. 148 1.3 Address Types 150 Tentative address - an address whose uniqueness on a link is being 151 verified, prior to its assignment to an interface. A Tentative 152 address is not considered assigned to an interface in the usual 153 sense. An interface discards received packets addressed to a 154 Tentative address, but accepts Neighbor Discovery packets 155 related to Duplicate Address Detection for the Tentative 156 address. 158 Optimistic address - an address which is assigned to an interface and 159 available for use, subject to restrictions, while its uniqueness 160 on a link is being verified. This memo introduces the 161 Optimistic state and defines its behaviours and restrictions. 163 Preferred address - an address assigned to an interface whose use by 164 upper layer protocols is unrestricted. Preferred addresses may 165 be used as the source (or destination) address of packets sent 166 from (or to) the interface. 168 Deprecated address - An address assigned to an interface whose use is 169 discouraged, but not forbidden. A Deprecated address should no 170 longer be used as a source address in new communications, but 171 packets sent from or to Deprecated addresses are delivered as 172 expected. A Deprecated address may continue to be used as a 173 source address in communications where switching to a Preferred 174 address causes hardship to a specific upper-layer activity 175 (e.g., an existing TCP connection). 177 Valid Address - a Preferred, Optimistic or Deprecated address. A 178 valid address may appear as the source or destination address of 179 a packet, and the internet routing system is expected to deliver 180 packets sent to a valid address to their intended recipients. 182 1.4 Abbreviations 184 DAD - Duplicate Address Detection. Technique used for SLAAC. See 185 [RFC2462] section 5.4. 187 ICMP Redirect - See [RFC2461] section 4.5. 189 NA - Neighbor Advertisement. See [RFC2461] sections 4.4 and 7. 191 NC - Neighbor Cache. See [RFC2461] section 5.1 and 7.3. 193 ND - Neighbor Discovery. The process described in [RFC2461] 195 NS - Neighbor Solicitation. See [RFC2461] sections 4.3 and 7. 197 ON - Optimistic Node. A node which is behaving according to the 198 rules of this memo. 200 RA - Router Advertisement. See [RFC2462] sections 4.2 and 6. 202 RS - Router Solicitation. See [RFC2461] sections 4.1 and 6. 204 SLAAC - StateLess Address AutoConfiguration. The process described 205 in [RFC2462] 207 SLLAO - Source Link Layer Address Option - an option to NS, RA and RS 208 messages, which gives the link layer address of the source of 209 the message. See [RFC2461] section 4.6.1. 211 TLLAO - Target Link Layer Address Option - an option to ICMP Redirect 212 messages and Neighbor Advertisements. See [RFC2461] sections 213 4.4, 4.5 and 4.6.1. 215 2. Optimistic DAD Behaviours 217 This non-normative section discusses Optimistic DAD behaviours. 219 2.1 Optimistic Addresses 221 [RFC2462] introduces the concept of Tentative (in 5.4) and Deprecated 222 (in 5.5.4) Addresses. Addresses which are neither are said to be 223 Preferred. Tentative addresses may not be used for communication, 224 and Deprecated addresses should not be used for new communications. 225 These address states may also be used by other standards documents, 226 for example Default Address Selection [RFC3484]. 228 This memo introduces a new address state, 'Optimistic', that is used 229 to mark an address which is available for use but which has not 230 completed DAD. 232 Unless noted otherwise, components of the IPv6 protocol stack should 233 treat addresses in the Optimistic state equivalently to those in the 234 Deprecated state, indicating that the address is available for use 235 but should not be used if another suitable address is available. For 236 example, Default Address Selection [RFC3484] uses the address state 237 to decide which source address to use for an outgoing packet. 238 Implementations should treat an address in state Optimistic as if it 239 were in state Deprecated. If address states are recorded as 240 individual flags, this can easily be achieved by also setting 241 'Deprecated' when 'Optimistic' is set. 243 It is important to note that the address lifetime rules of [RFC2462] 244 still apply, and so an address may be Deprecated as well as 245 Optimistic. When DAD completes without incident, the address becomes 246 either a Preferred or a Deprecated address, as per [RFC2462]. 248 2.2 Avoiding Disruption 250 In order to avoid interference, it is important that an Optimistic 251 node does not send any messages from an Optimistic Address which will 252 override its neighbors' Neighbor Cache (NC) entries for the address 253 it is trying to configure: doing so would disrupt the rightful owner 254 of the address in the case of a collision. 256 This is achieved by: 258 * clearing the 'Override' flag in Neighbor Advertisements for 259 Optimistic Addresses, which prevents neighbors from overriding 260 their existing NC entries. The 'Override' flag is already 261 defined [RFC2461] and used for Proxy Neighbor Advertisement. 263 * Never sending Neighbor Solicitations from an Optimistic Address. 264 NSs include a Source Link Layer Address Option (SLLAO), which 265 may cause Neighbor Cache disruption. NSs sent as part of DAD 266 are sent from the unspecified address, without a SLLAO. 268 * Never using an Optimistic Address as the source address of a Router 269 Solicitation with a SLLAO. Another address, or the unspecified 270 address, may be used, or the RS may be sent without a SLLAO. 272 An address collision with a router may cause neighboring router's 273 IsRouter flags for that address to be cleared. However, routers do 274 not appear to use the IsRouter flag for anything, and the NA sent in 275 response to the collision will reassert the IsRouter flag. 277 2.3 Router Redirection 279 Neighbor Solicitations cannot be sent from Optimistic Addresses, and 280 so an ON cannot directly contact a neighbor which is not already in 281 its Neighbor Cache. Instead, the ON forwards packets via its default 282 router, relying on the router to forward the packets to their 283 destination. In accordance with RFC2461, the router should then 284 provide the ON with an ICMP Redirect, which may include a Target Link 285 Layer Address Option (TLLAO). If it does, this will update the ON's 286 NC, and direct communication can begin. If it does not, packets 287 continue to be forwarded via the router until the ON has a non- 288 Optimistic address from which to send an NS. 290 2.4 Contacting the Router 292 Router Solicitations cannot be sent from Optimistic Addresses, and 293 thus a node which only has Optimistic Addresses cannot contact a 294 router unless it already knows its Link-Layer Address. This 295 information is generally included in the RA, but this option "MAY be 296 omitted to facilitate in-bound load balancing over replicated 297 interfaces." [RFC2461]. In this case, the ON will be unable to 298 communicate with the router until at least one of its addresses in no 299 longer Optimistic. 301 3. Modifications to RFC-mandated behaviour 303 All normative text in this memo is contained in this section. 305 3.1 General 307 * Optimistic DAD SHOULD only be used when the implementation is aware 308 that the address is based on a most likely unique interface 309 identifier (such as in [RFC2464]), generated randomly [RFC3041] 310 or by a well-distributed hash function [RFC3972] or assigned by 311 DHCPv6 [RFC3315]. Optimistic DAD SHOULD NOT be used for 312 manually entered addresses. 314 3.2 Modifications to RFC 2461 Neighbor Discovery 316 * (modifies 6.3.7) A node MUST NOT send a Router Solicitation with a 317 SLLAO from an Optimistic Address. Router Solicitations SHOULD 318 be sent from a non-Optimistic or the Unspecified Address, 319 however they MAY be sent from an Optimistic Address as long as 320 the SLLAO is not included. 322 * (modifies 7.2.2) A node MUST NOT use an Optimistic Address as the 323 source address of a Neighbor Solicitation. 325 * If the ON isn't told the SLLAO of the router in an RA, and it 326 cannot determine this information without breaching the rules 327 above, it MUST leave the address Tentative until DAD completes 328 despite being unable to send any packets to the router. 330 * (modifies 7.2.2) When a node has a unicast packet to send from an 331 Optimistic Address to a neighbor, but does not know the 332 neighbor's link-layer address, it MUST NOT perform Address 333 Resolution. It SHOULD forward the packet to a default router on 334 the link in the hope that the packet will be redirected. 335 Otherwise it SHOULD buffer the packet until DAD is complete. 337 3.3 Modifications to RFC 2462 Stateless Address Autoconfiguration 339 * (modifies 5.5) A host MAY choose to configure a new address as an 340 Optimistic Address. A host which does not know the SLLAO of its 341 router SHOULD NOT configure a new address as Optimistic. A 342 router SHOULD NOT configure an Optimistic Address. 344 * (modifies 5.4.2) The host MUST join the all-nodes multicast address 345 and the solicited-node multicast address of the tentative 346 address. The host SHOULD NOT delay before sending Neighbour 347 Solicitation messages. 349 * (modifies 5.4) The Optimistic Address is configured and available 350 for use on the interface immediately. The address MUST be 351 flagged as 'Optimistic'. 353 * When DAD completes for an Optimistic Address, the address is no 354 longer Optimistic and it becomes Preferred or Deprecated 355 according to the rules of RFC2462. 357 * (modifies 5.4.3) The node MUST NOT reply to a Neighbor Solicitation 358 for an Optimistic Address from the unspecified address. Receipt 359 of such an NS indicates that the address is a duplicate, and it 360 MUST be deconfigured as per the behaviour specified in RFC2462 361 for Tentative addresses. 363 * (modifies 5.4.3) The node MUST reply to a Neighbor Solicitation for 364 an Optimistic Address from a unicast address, but the reply MUST 365 have the Override flag cleared (O=0). 367 4. Protocol Operation 369 This non-normative section provides clarification of the interactions 370 between Optimistic Nodes, and between Optimistic Nodes and Standard 371 Nodes. 373 The following cases all consider an Optimistic Node (ON) receiving a 374 Router Advertisement containing a new prefix and deciding to 375 autoconfigure a new Optimistic Address on that prefix. 377 The ON will immediately send out a Neighbor Solicitation to determine 378 if its new Optimistic Address is already in use. 380 4.1 Simple case 382 In the non-collision case, the Optimistic Address being configured by 383 the new node is unused and not present in the Neighbor Caches of any 384 of its neighbors. 386 There will be no response to its NS (sent from ::), and this NS will 387 not modify the state of neighbors' Neighbor Caches. 389 The ON already has the link-layer address of the router (from the 390 RA), and the router can determine the link-layer address of the ON 391 through standard Address Resolution. Communications can begin as 392 soon as the router and the ON have each others' link-layer addresses. 394 After the appropriate DAD delay has completed, the address is no 395 longer Optimistic, and becomes either Preferred or Deprecated as per 396 RFC2462. 398 4.2 Collision case 400 In the collision case, the Optimistic Address being configured by the 401 new node is already in use by another node, and present in the 402 Neighbor Caches (NCs) of neighbors which are communicating with this 403 node. 405 The NS sent by the ON has the unspecified source address, ::, and no 406 SLLAO. This NS will not cause changes to the NC entries of 407 neighboring hosts. 409 The ON will hopefully already know all it needs to about the router 410 from the initial RA. However, if it needs to it can still send an RS 411 to ask for more information, but it may not include a SLLAO. This 412 forces an all-nodes multicast response from the router, but will not 413 disrupt other nodes' NCs. 415 In the course of establishing connections, the ON might have sent NAs 416 in response to received NSs. Since NAs sent from Optimistic 417 Addresses have O=0, they will not have overridden existing NC 418 entries, although they may have resulted in a colliding entry being 419 changed to state STALE. This change is recoverable through standard 420 NUD. 422 When an NA is received from the collidee defending the address, the 423 ON immediately stops using the address and deconfigures it. 425 Of course, in the meantime the ON may have sent packets which 426 identify it as the owner of its new Optimistic Address (for example, 427 Binding Updates in Mobile IPv6 [RFC3775]). This may incur some 428 penalty to the ON, in the form of broken connections, and some 429 penalty to the rightful owner of the address, since it will receive 430 (and potentially reply to) the misdirected packets. It is for this 431 reason that Optimistic DAD should only be used where the probability 432 of collision is very low. 434 4.3 Interoperation cases 436 Once the Optimistic Address has completed DAD, it acts exactly like a 437 normal address, and so interoperation cases only arise while the 438 address is Optimistic. 440 If an ON attempts to configure an address currently Tentatively 441 assigned to a Standard Node, the Standard Node will see the Neighbor 442 Solicitation and deconfigure the address. 444 If a node attempts to configure an ON's Optimistic Address, the ON 445 will see the NS and deconfigure the address. 447 4.4 Pathological cases 449 Optimistic DAD suffers from similar problems to Standard DAD, for 450 example duplicates are not guaranteed to be detected if packets are 451 lost. 453 These problems exist, and are not gracefully recoverable, in Standard 454 DAD. Their probability in both Optimistic and Standard DAD can be 455 reduced by increasing the RFC2462 DupAddrDetectTransmits variable to 456 greater than 1. 458 This version of Optimistic DAD is dependant on the details of the 459 router behaviour, e.g.: that the router includes SLLAOs in RAs, and 460 that the router is willing to redirect traffic for the ON. Where the 461 router does not behave in this way, the behaviour of Optimistic DAD 462 inherently reverts to that of Standard DAD. 464 5. Security Considerations 466 There are existing security concerns with Neighbor Discovery and 467 Stateless Address Autoconfiguration, and this memo does not purport 468 to fix them. However, this memo does not significantly increase 469 security concerns either. 471 Secure Neighbor Discovery [RFC3971] provides protection against the 472 threats to Neighbor Discovery described in [RFC3756]. Optimistic 473 Duplicate Address Detection does not introduce any additional threats 474 to Neighbor Discovery if SEND is used. 476 Optimistic DAD takes steps to ensure that if another node is already 477 using an address, the proper link-layer address in existing Neighbor 478 Cache Entries is not replaced with the link-layer address of the 479 Optimistic node. However, there are still scenarios where incorrect 480 entries may be created, if only temporarily. For example, if a 481 router (while forwarding a packet) sends out a Neighbor Solicitation 482 for an address, the optimistic node may respond first, and if the 483 router has no pre-existing link-layer address for that IP address, it 484 will accept the response and (incorrectly) forward any queued packets 485 to the optimistic node. The optimistic node may then respond in an 486 incorrect manner (e.g., sending a TCP RST in response to an unknown 487 TCP connection). Such transient conditions should be short-lived, in 488 most cases. 490 Likewise, an Optimistic node can still inject IP packets into the 491 Internet that will in effect be "spoofed" packets appearing to come 492 from the legitimate node. In some cases, those packets may lead to 493 errors or other operational problems, though one would expect that 494 upper layer protocols would generally treat such packets robustly, in 495 the same way they must treat old and other duplicate packets. 497 6. IANA Considerations 499 This document has no actions for IANA. 501 Appendix A: Probability of Collision 503 In assessing the usefulness of Duplication Address Detection, the 504 probability of collision must be considered. Various mechanisms such 505 as SLAAC [RFC2462] and DHCPv6 [RFC3315] attempt to guarantee the 506 uniqueness of the address. The uniqueness of SLAAC depends on the 507 reliability of the manufacturing process (so that duplicate L2 508 addresses are not assigned) and human factors if L2 addresses can be 509 manually assigned. The uniqueness of DHCPv6 assigned addresses 510 relies on the correctness of implementation to ensure that no two 511 nodes can be given the same address. 513 Privacy Extensions to SLAAC [RFC3041] avoids these potential error 514 cases by picking an Interface Identifier (IID) at random from 2^62 515 possible 64-bit IIDs (allowing for the reserved U and G bits). No 516 attempt is made to guarantee uniqueness, but the probability can be 517 easily estimated, and as the following discussion shows, probability 518 of collision is exceedingly small. 520 A.1 The Birthday Paradox 522 When considering collision probability, the Birthday Paradox is 523 generally mentioned. When randomly selecting k values from n 524 possibilities, the probability of two values being the same is: 526 Pb(n,k) = 1-( n! / [ (n-k)! . n^k] ) 528 Calculating the probability of collision with this method is 529 difficult, however, as one of the terms is n!, and (2^62)! is an 530 unwieldy number. We can, however, calculate an upper bound for the 531 probability of collision: 533 Pb(n,k) <= 1-( [(n-k+1)/n] ^ [k-1] ) 535 which lets us calculate that even for large networks the probability 536 of any two nodes colliding is very small indeed: 538 Pb(2^62, 500) <= 5.4e-14 539 Pb(2^62, 5000) <= 5.4e-12 540 Pb(2^62, 50000) <= 5.4e-10 541 Pb(2^62, 500000) <= 5.4e-08 543 The upper bound formula used above was taken from 'draft-soto- 544 mobileip-random-iids-00' by M. Bagnulo, I. Soto, A. Garcia-Martinez 545 and A. Azcorra and is used with the kind permission of the authors. 547 A.2 Individual Nodes 549 When considering the effect of collisions on an individual node, we 550 do not need to consider the Birthday Paradox. When a node moves into 551 a network with K existing nodes, the probability that it will not 552 collide with any of the distinct addresses in use is simply 1-K/N. 553 If it moves to such networks M times, the probability that it will 554 not cause a collision on any of those moves is (1-K/N)^M, thus the 555 probability of it causing at least one collision is: 557 Pc(n,k,m) = 1-[(1-k/n)^m] 559 Even considering a very large number of moves (m = 600000, slightly 560 more than one move per minute for one year) and rather crowded 561 networks (k=50000 nodes per network), the odds of collision for a 562 given node are vanishingly small: 564 Pc(2^62, 5000, 600000) = 6.66e-10 565 Pc(2^62, 50000, 600000) = 6.53e-09 567 Each such collision affects two nodes, so the probability of being 568 effected by a collision is twice this. Even if the node moves into 569 networks of 50000 nodes once per minute for 100 years, the 570 probability of it causing or suffering a collision at any point are a 571 little over 1 in a million. 573 Pc(2^62, 50000, 60000000) * 2 = 1.3e-06 575 Normative References 577 [RFC2119] S. Bradner. "RFC 2119: Key words for use in RFCs to 578 Indicate Requirement Levels." 580 [RFC2461] T. Narten, E.Nordmark, W. Simpson. "RFC 2461: Neighbor 581 Discovery for IP Version 6 (IPv6)." 583 [RFC2462] S. Thomson, T. Narten. "RFC 2462: IPv6 Stateless Address 584 Autoconfiguration." 586 Informative References 588 [RFC2464] M. Crawford. "RFC 2464: Transmission of IPv6 Packets over 589 Ethernet Networks." 591 [RFC3041] T. Narten, R. Draves. "RFC 3041: Privacy Extensions for 592 Stateless Address Autoconfiguration in IPv6." 594 [RFC3315] R. Droms (Ed.), J. Bound, B. Volz, T. Lemon, C. Perkins, M. 595 Carney. "RFC 3315: Dynamic Host Configuration Protocol for IPv6 596 (DHCPv6)." 598 [RFC3484] R. Draves. "RFC 3484: Default Address Selection for 599 Internet Protocol version 6 (IPv6)." 601 [RFC3756] P. Nikander, J. Kempf, E. Nordmark. "RFC 3756: IPv6 602 Neighbor Discovery (ND) Trust Models and Threats." 604 [RFC3775] D. Johnson, C. Perkins, J. Arkko. "RFC 3775: Mobility 605 Support in IPv6." 607 [RFC3971] J. Arkko (Ed.), J. Kempf, B.Zill, P. Nikander. "RFC 3971: 608 SEcure Neighbor Discovery (SEND)." 610 [RFC3972] T. Aura. "RFC 3972: Cryptographically Generated Addresses 611 (CGA)." 613 Author's Address: 615 Nick 'Sharkey' Moore 616 Centre for Telecommunications and Information Engineering 617 Monash University 3800 618 Victoria, Australia 620 Comments should be sent to and/or the IPv6 Working 621 Group mailing list. 623 Acknowledgments 625 There is some precedent for this work in previous Internet Drafts and 626 in discussions in the MobileIP WG mailing list and at IETF-54. A 627 similar concept occurs in the 'Optimistic' bit used by R. Koodli and 628 C. Perkins in the now expired 'draft-koodli-mobileip-fastv6-00.txt'. 630 Thanks to Greg Daley, Richard Nelson, Brett Pentland and Ahmet 631 Sekercioglu at Monash University CTIE for their feedback and 632 encouragement. More information is available at: 633 635 Thanks to all the MobileIP and IPng/IPv6 WG members who have 636 contributed to the debate. Especially and alphabetically: Jari 637 Arkko, Marcelo Bagnulo, JinHyeock Choi, Youn-Hee Han, James Kempf, 638 Thomas Narten, Pekka Nikander, Erik Nordmark, Soohong 'Daniel' Park, 639 Ed Remmel, Pekka Savola, Hesham Soliman, Ignatious Souvatzis, Jinmei 640 Tatuya, Dave Thaler, Pascal Thubert, Christian Vogt, Vladislav 641 Yasevich and Alper Yegin. 643 This work has been supported by the Australian Telecommunications 644 Cooperative Research Centre (ATcrc): 645 647 Funding for the RFC Editor function is currently provided by the 648 Internet Society. 650 Full Copyright Statement 652 Copyright (C) The Internet Society (2005). 654 This document is subject to the rights, licenses and restrictions 655 contained in BCP 78, and except as set forth therein, the authors 656 retain all their rights. 658 Intellectual Property Statement 660 The IETF takes no position regarding the validity or scope of any 661 Intellectual Property Rights or other rights that might be claimed to 662 pertain to the implementation or use of the technology described in 663 this document or the extent to which any license under such rights 664 might or might not be available; nor does it represent that it has 665 made any independent effort to identify any such rights. Information 666 on the procedures with respect to rights in RFC documents can be 667 found in BCP 78 and BCP 79. 669 Copies of IPR disclosures made to the IETF Secretariat and any 670 assurances of licenses to be made available, or the result of an 671 attempt made to obtain a general license or permission for the use of 672 such proprietary rights by implementers or users of this 673 specification can be obtained from the IETF on-line IPR repository at 674 http://www.ietf.org/ipr. 676 The IETF invites any interested party to bring to its attention any 677 copyrights, patents or patent applications, or other proprietary 678 rights that may cover technology that may be required to implement 679 this standard. Please address the information to the IETF at ietf- 680 ipr@ietf.org. 682 Disclaimer of Validity 684 This document and the information contained herein are provided on an 685 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 686 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 687 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 688 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 689 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 690 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.