idnits 2.17.1 draft-jinchoi-dna-cpl-00.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 3667, Section 5.1 on line 15. -- Found old boilerplate from RFC 3978, Section 5.5 on line 801. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 778. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 785. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 791. ** Found boilerplate matching RFC 3978, Section 5.4, paragraph 1 (on line 807), which is fine, but *also* found old RFC 2026, Section 10.4C, paragraph 1 text on line 37. ** The document seems to lack an RFC 3978 Section 5.1 IPR Disclosure Acknowledgement -- however, there's a paragraph with a matching beginning. Boilerplate error? ** 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. ** The document uses RFC 3667 boilerplate or RFC 3978-like boilerplate instead of verbatim RFC 3978 boilerplate. After 6 May 2005, submission of drafts without verbatim RFC 3978 boilerplate is not accepted. The following non-3978 patterns matched text found in the document. That text should be removed or replaced: 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. 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 == Line 200 has weird spacing: '... a host to at...' == 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 (June 29, 2004) is 7241 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) -- Looks like a reference, but probably isn't: 'N' on line 493 == Unused Reference: '3' is defined on line 706, but no explicit reference was found in the text == Unused Reference: '5' is defined on line 712, but no explicit reference was found in the text == Unused Reference: '6' is defined on line 715, but no explicit reference was found in the text == Unused Reference: '13' is defined on line 741, but no explicit reference was found in the text == Unused Reference: '14' is defined on line 745, but no explicit reference was found in the text ** Obsolete normative reference: RFC 3667 (ref. '1') (Obsoleted by RFC 3978) ** Obsolete normative reference: RFC 3668 (ref. '2') (Obsoleted by RFC 3979) ** Obsolete normative reference: RFC 2461 (ref. '4') (Obsoleted by RFC 4861) ** Obsolete normative reference: RFC 2462 (ref. '5') (Obsoleted by RFC 4862) ** Obsolete normative reference: RFC 3513 (ref. '6') (Obsoleted by RFC 4291) == Outdated reference: A later version (-04) exists of draft-ietf-dna-goals-00 ** Downref: Normative reference to an Informational draft: draft-ietf-dna-goals (ref. '7') -- Obsolete informational reference (is this intentional?): RFC 3775 (ref. '8') (Obsoleted by RFC 6275) == Outdated reference: A later version (-06) exists of draft-ietf-send-ndopt-05 == Outdated reference: A later version (-03) exists of draft-pentland-mobileip-linkid-00 Summary: 12 errors (**), 0 flaws (~~), 12 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 DNA WG JinHyeock Choi 2 Internet-Draft Samsung AIT 3 Expires: December 28, 2004 Erik Nordmark 4 SUN Microsystems 5 June 29, 2004 7 DNA with unmodified routers: Prefix list based approach 8 draft-jinchoi-dna-cpl-00.txt 10 Status of this Memo 12 By submitting this Internet-Draft, I certify that any applicable 13 patent or other IPR claims of which I am aware have been disclosed, 14 and any of which I become aware will be disclosed, in accordance with 15 RFC 3668. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as 20 Internet-Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on December 28, 2004. 35 Copyright Notice 37 Copyright (C) The Internet Society (2004). All Rights Reserved. 39 Abstract 41 Upon establishing a new link-layer connection, a host determines 42 whether a link change has occurred to examine the validity of its IP 43 configuration. This draft presents a way to robustly check for link 44 change without assuming changes to the routers. Each link can be 45 uniquely identified by the set of prefixes assigned to it. We 46 propose that, at each attached link, the host generates the complete 47 prefix list, that is, the prefix list contains all the prefixes on 48 the link, and when it receives a hint that indicates a possible link 49 change, it detects the identity of the link by consulting the 50 existing prefix list. This memo describes how to generate the 51 complete prefix list and to robustly check for link change even in 52 the presence of packet losses. 54 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 57 2. Prefix list based approach . . . . . . . . . . . . . . . . . . 4 58 2.1 Approach . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 2.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . 4 60 2.3 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 5 61 3. DNA based on the complete prefix list . . . . . . . . . . . . 7 62 3.1 Generating the complete prefix list . . . . . . . . . . . 7 63 3.2 Checking for link change . . . . . . . . . . . . . . . . . 10 64 4. Performance Analysis . . . . . . . . . . . . . . . . . . . . . 13 65 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 15 66 6. Security Considerations . . . . . . . . . . . . . . . . . . . 16 67 7. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 68 7.1 Example with link-up indication . . . . . . . . . . . . . 17 69 7.2 Example without link-up indication . . . . . . . . . . . . 17 70 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 71 8.1 Normative References . . . . . . . . . . . . . . . . . . . . 19 72 8.2 Informative References . . . . . . . . . . . . . . . . . . . 19 73 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 20 74 Intellectual Property and Copyright Statements . . . . . . . . 21 76 1. Introduction 78 When a host establishes a new link-layer connection, it may or may 79 not have a valid IP configuration for the link (for example, the 80 subnet prefixes on the attached link and the default routers). 81 Though the host has changed its network attachment point, it may 82 still be at the same link. The term 'link' used in this document is 83 as defined in [4]. 85 To examine its IP configuration, a host may check for link change, 86 i.e. it verifies whether it is attached to the same or a different 87 link as before [7]. The host can keep current IP configuration if 88 and only if it remains at the same link. 90 Usually a host receives the link information from RA (Router 91 Advertisement) messages. But, as described in 3.2. [7], it's 92 difficult for a host to correctly detect the identify of a link with 93 an RA. None of the information in an RA can indicate a link change 94 properly. Neither router address nor prefixes will do. 96 It may be better to design a new way to represent the identity of a 97 link, Link Identifier. Each link has its unique Link Identifier and 98 all routers in the link advertise the same Link Identifier. In [11], 99 Erik Nordmark proposed a new option, 'Location Indication Option', 100 which can serve as Link Identifier. Also Brett Pentland and all 101 submitted a draft about Link Identifier [12]. 103 However, even if some such new scheme is standardized and 104 implemented, hosts would still need to cope with routers which do not 105 (yet) implement such a scheme. Thus it makes sense to write down the 106 rules for how to robustly detect a changed link without assuming 107 changes to the routers. 109 2. Prefix list based approach 111 2.1 Approach 113 Currently there is one thing which can represent the identify of a 114 link, 116 'The set of all the global prefixes assigned to a link.' 118 If a host has the complete list of all the assigned prefixes, it can 119 properly determine whether a link change has occurred. If the host 120 receives an RA containing one or more prefixes and none of the 121 prefixes in it matches the previously known prefixes for the link, 122 then it is assumed to be a new link. 124 This works because each and every global prefix on a link must not be 125 used on any other link thus the sets of global prefixes on different 126 links must be disjoint. 128 For the purposes of determining the prefixes, this specification uses 129 both 'on-link' and 'addrconf' prefixes [4], that is, prefixes that 130 have either the 'on-link' flag set, the 'autonomous 131 address-autoconfiguration' flag set, or both flags set. This is a 132 safe approach since both the set of on-link and the set of addrconf 133 prefixes must be uniquely assigned to a link. 135 The difficulty lies both in ensuring that the complete prefix list 136 for a single link is known and preventing prefixes from possibly 137 different links to be viewed as the prefixes for a single link. This 138 is challenging given that a single router advertisements is not 139 required to include all prefixes for the link, router advertisements 140 might be subject to packet loss, new routers and new prefixes (due to 141 renumbering) might appear at any time on a link, and the host might 142 attach to a different link at any time. 144 If the prefix list determination is incorrect, there can be two 145 different types of failures. One is detecting a new link when in 146 fact the host remains attached to the same link. The other is 147 failing to detect when the host attaches to a different link. The 148 former failure is undesirable because it might trigger other 149 protocols, such as Mobile IPv6 [4], to do unneeded signaling, thus it 150 is important to minimize this type of failure. The latter type of 151 failure can lead to long outages when the host is not able to 152 communicate at all, thus these failures must be prevented. 154 2.2 Assumptions 156 In this approach, we assume that an interface of a host can not be 157 attached to multiple links at the same time. Though this kind of 158 multiple attachments is allowed in neither Ethernet nor 802.11b, it 159 may be possible in some Cellular System, especially CDMA. 161 2.3 Overview 163 Hints are used to tell a host that a link change might have happened. 164 This hint itself doesn't confirm a link change, but can be used to 165 initiate the appropriate procedures [7]. 167 In order to never view two different links as one it is critical that 168 when the host might have attached to a link, there has to be some 169 form of hint. This hint doesn't imply that a movement to a different 170 link has occurred, but instead, in the absence of such a hint there 171 could not have been an attachment to a different link. 173 If the IP stack is notified by the link layer when a new attachment 174 is established (e.g., when associating to a different access point in 175 802.11), this will serve as the hint. It helps to reduce the risk 176 that the assignment of an additional prefix to a link will be 177 misinterpreted as being attached to a different link. Note that this 178 hint is merely a local indication and does not require any protocol 179 changes. For instance, in many implementations this would be an 180 indication passed from a link-layer device driver to the IP layer. 182 For implementations which do not provide a "link up" indication, the 183 solution is to instead rely on either the receipt of an RA that 184 contains disjoint prefixes from the prefixes that have been collected 185 on the previous link or the lack of scheduled RAs as described in 186 [4], as a hint of an attachment to a possibly different link. 188 Independent of the type of hint used, once a hint is received the 189 host will start to collect a new set of prefixes for the possibly 190 different link, and compare them the prefixes known from before the 191 hint. If there is one or more common prefixes it is safe to assume 192 that the host is attached to the same link, in which case the 193 prefixes learned after the hint can be merged with the prefixes 194 learned before the hint. But if the sets of prefixes are disjoint, 195 then at some point in time the host will determine that it is 196 attached to a different link. This process starts when the host is 197 powered on and first attaches to a link. 199 Since each router advertisement message isn't guaranteed to contain 200 all prefixes it is a challenge for a host to attain and retain the 201 complete prefix list, especially when packets can be lost on the 202 link. 204 The host has to rely on approximate knowledge of the prefix list 205 using RS/ RA exchanges. Just as specified in [4] the host sends an 206 RS (Router Solicitation) message to All-Router multicast address, 207 then waits for the solicited RAs. If there was no packet loss, the 208 host would receive the RAs from all the routers on the link in a few 209 seconds thereby knowing all the prefixes on the link. Taking into 210 account packet loss, the host may perform RS/ RA exchanges multiple 211 times to corroborate the result. 213 When a hint indicating a possible link change happens, if the host is 214 reasonably sure that its prefix list is complete, it can detect 215 whether it is attached to the same link on the reception of just one 216 RA containing one or more prefixes. 218 Otherwise, to make matters certain, the host may need at least wait 219 for more RAs than a single one, or additionally perform multiple RS/ 220 RA exchanges after the hint. After each RS transmission, the host 221 waits for all RAs that would have been triggered by the RS as one 222 aspect of trying harder, and then sending multiple RSs (and waiting 223 for the resulting RAs) is a way to try even harder. 225 When hints are received frequently, this means that the host might 226 need to track more than two prefix lists at a time. Essentially, 227 each reception of a hint indicates the start of a new prefix list to 228 track, which may or may not turn out to be disjoint from a previously 229 known prefix list. 231 All tracking of the prefix lists must take the valid lifetime of the 232 prefixes into account, but apart from this limitation there isn't any 233 harm in the host remembering prefix lists from links it has attached 234 to earlier. The prefix list is maintained separately per network 235 interface. 237 3. DNA based on the complete prefix list 239 To each link, the set of prefixes is uniquely assigned. Two separate 240 links have two disjoint sets of prefixes. The two prefix lists of 241 two separate links have no element in common. 243 The identify of a link can be represented by the prefix list if it 244 correctly includes all the assigned prefixes. We denote the complete 245 prefix list as the the list of all the prefixes assigned to the link. 246 Each link has its unique complete prefix list. We also say that the 247 prefix list is complete if all the prefixes belong to it. 249 In case that a host has the complete prefix list, it can properly 250 determine whether it is attached to the same link or not, when it 251 receives a hint that a link change might have occurred. 253 This section presents a procedure to generate the complete prefix 254 list and a way to check for link change based on the existing prefix 255 list even in the presence of packet losses. 257 3.1 Generating the complete prefix list 259 To efficiently check for link change, a host always maintains the 260 list of all known prefixes on the link. This procedure of attaining 261 and retaining the complete prefix list is initialized when the host 262 is powered on. 264 Usually hosts execute and terminate the process of generating the 265 complete prefix list (of a link) at an old attachment point, before 266 handoff process begins. Though the procedure may take some time, 267 that doesn't matter unless the host moves very fast. A host can 268 generate the complete prefix list with reasonable certainty if it 269 remains attached to a link sufficiently long, approximately 10 270 seconds. 272 To generate the complete prefix list, presently the host has to rely 273 on approximate knowledge based on RS/ RA exchanges as follows. 275 First the host sends an RS to All-Router multicast address. Assuming 276 there is no packet loss, every router on the link would receive the 277 RS and reply with an RA containing all the prefixes that the router 278 advertises. 280 After an RS transmission, the host waits for all RAs that would have 281 been triggered by the RS. There is an upper limit on the delay of 282 the RAs. MIN_DELAY_BETWEEN_RAS (3 Sec) + MAX_RA_DELAY_TIME (0.5 Sec) 283 + network propagation delay is the maximum delay between an RS and 284 the resulting RAs [4]. 4 seconds would be a safe number for the host 285 to wait for the resulting RAs. Assuming no packet loss, within 4 286 seconds, the host would receive all the RAs and know all the 287 prefixes. 289 In case of packet loss, things get more complicated. In the above 290 process, there may be a packet loss that results in the generation of 291 the incomplete prefix list, i.e. the prefix list that misses some 292 prefix on the link. To remedy this deficiency, the host may perform 293 multiple RS/ RA exchanges to collect all the assigned prefixes. 295 After one RS/ RA exchange, to corroborate the completeness of the 296 prefix list, the host may send one or more RSs additionally and wait 297 for the resulting RAs. Each RS/ RA exchange produces the set of the 298 prefixes on the link. These sets may or may not be identical 299 depending on whether there happened a packet loss or not. Assuming 300 no packet loss, these sets would be the same. 302 The host takes the union of all these sets to generate the prefix 303 list. The more RS/ RA exchange the host performs, the more probable 304 that the resulting prefix list is complete. Section 4 gives the 305 detailed analysis. 307 By performing multiple (multicast) RS/ RA exchanges and combining the 308 results, the host can reasonably sure that the existing prefix list 309 is complete. 311 To ascertain whether its existing prefix list is complete or not, the 312 host can set its own policy. The host may take into consideration 313 the packet loss rate of the link and the number of RS/ RA exchanges 314 it performed. 316 For example, the host may keep track of how may RS/ RA exchanges it 317 performed on this attachment point, and if this is 3 or more it 318 assumes that the resulting prefix list is complete. But if this is 319 only 1 or 2, the host doesn't assume the completeness of the prefix 320 list. 322 In general, the higher the error rate, the more RS/ RA exchanges are 323 needed to assure the completeness of the prefix list. 325 It may happen that the host fails to generate the complete prefix 326 list. 328 The host may not be sure that the prefix list is complete. Or worse, 329 the host may falsely assume the completeness of the prefix list while 330 it is not. 332 The host may generate either 1) the incomplete prefix list, i.e. the 333 prefix list misses some prefix on the link or 2) the superfluous 334 prefix list, i.e. the prefix list that contains some prefix that is 335 not assigned to the link. 337 It is noted that 1) and 2) is not exclusive. The host may generate 338 the prefix list that misses some prefix on the link but includes the 339 prefix not assigned to the link. 341 Severe packet losses during prefix list generation may cause the 342 incomplete prefix list. Or the host may have undergone a link change 343 before finishing the procedure of the complete prefix list 344 generation. Later we will deal with the case that the host can't be 345 sure of the completeness of the prefix list. 347 Even if the host falsely assumes that the incomplete prefix list is 348 complete, the pain of that assumption is that the host might later 349 think it has moved to a different link when in fact it has not. 351 In case that a link change happens, even if the host has the 352 incomplete prefix list, it will detect a link change. Hence the 353 incomplete prefix list doesn't cause a connection disruption. But it 354 may cause excessive signaling messages, for example Binding Update 355 messages in [8]. 357 The superfluous prefix list presents a more serious problem. 359 Without the indication from the link-layer, the host can't perceive 360 that it has changed its attachment point, i.e. it has torn down an 361 old link-layer connection and established a new one. 363 So while generating the prefix list, without knowing it, the host may 364 be attached to multiple links in turn and accidentally end up with 365 prefixes from multiple links in the prefix list. 367 Here is an example. The host begins to collect the prefixes on a 368 link. But before the prefix list generation is completed, without 369 its knowledge, the host moves to a new link. Unaware that now it is 370 at the different link, the host keeps collecting prefixes with RS/ RA 371 exchanges to generate the prefix list. This results in the prefix 372 list containing prefixes from two different links. If the host uses 373 this prefix list, it fails to detect a link change. 375 Since, in the absence of link-up indications, a RA with a disjoint 376 set of prefixes is treated as a hint, the risk for confusion occurs 377 because the host can not tell from the RAs whether they were 378 solicited by the host. (RFC 2461 recommends that solicited RAs be 379 multicast.) 380 The safest approach is for the host to assume that any RA received 381 within 4 seconds after sending a RS, assuming no intervening link-up 382 indication, where solicited, that is, the host has not moved to a 383 different link in that time. 385 In case the host moves fast, this assumption may lead to the 386 superfluous prefix list generation. The protocol is robust against 387 such confusion when a link-up indication is delivered to the IP layer 388 any time the host might have changed it's attachment. 390 If the host doesn't have any link layer hints, for example link up/ 391 down indications, it can't decide whether to use the prefixes it 392 receives for collecting information about the "old" link or about the 393 "new" link. 395 Maybe this is just something that should be stated as an assumption; 396 We may assume that when a host changes its attachment point, it will 397 be notified of the event and can distinguish the RAs arriving from 398 the old attachment point and the RAs from the new attachment point. 400 Thus we think the prefix-based approach has a stronger assumption 401 here than the Link Identifier-based approach, because the latter can 402 operate reliably without any link-layer hint. 404 3.2 Checking for link change 406 When a host receives a hint that indicates a possible link change, it 407 initiates DNA procedure to determine whether it still remains at the 408 same link or not. At this time, the complete prefix generation may 409 or may not be finished. 411 First, if the host has finished the complete prefix list generation 412 and can be reasonably sure of its completeness, the receipt of a 413 single RA (with at least one prefix) is enough to detect the identify 414 of the currently attached link. 416 Assume that, after the hint, the host receives an RA that contains at 417 least one prefix. Either by an RS transmission or by an arrival of 418 an unsolicited RA, the host can get an RA. The host compares the 419 prefixes in the RA with those in the existing prefix list. If the RA 420 contains a prefix that is also a member of the existing prefix list, 421 the host is still at the same link. Otherwise, if none of the 422 prefixes in that RA matches the previously known prefixes, it is at a 423 different link. 425 It may happen that the host can not be sure that the prefix list is 426 complete. In this case, the host may use another scheme that makes a 427 decision based on multiple solicited RAs, instead of one RA. 429 Suppose that before finishing the prefix list generation, the host 430 receives the hint that indicates a possible link change. Then the 431 host can't assume the completeness of the prefix list. 433 The host can generate another (complete) prefix list to compensate 434 the uncertainty of the existing prefix list. After the hint, it 435 performs one or more RS/ RA exchanges additionally to collect all the 436 prefixes on the currently attached link. With the resulting 437 prefixes, the host generates the second prefix list. 439 Then the host compares two prefix lists and if the lists are 440 disjoint, i.e. have no prefix in common, it assumes that a link 441 change has occurred. Usually this is done at a new attachment point. 443 For example, assume that the host keeps track of how many RS/ RA 444 exchanges it performed at a link. If this is 3 or more, the host 445 assumes that it have seen all the prefixes. Suppose that the host 446 has done a single RS/RA exchange, then it receives a link up 447 notification that causes it to initiate the DNA procedure. For a 448 better judgment, the host performs new RS/RA exchanges. If the host 449 tracks the list of prefixes received (from all received RAs) before 450 the link up notification and after the one, it can compare the lists 451 to check for link change. In case that the lists are disjoint, the 452 host can assume it has moved. 454 The difference with the previous case is that the host doesn't use 455 the first RA received after the hint to make its decision. Instead 456 it waits for the timeout and then use the received set of prefixes to 457 determine whether a link change has occurred. Though slower, this is 458 more robust. 460 In summary, first a host makes the complete prefix list. When a hint 461 occurs, if the host decides that the prefix list is complete, it will 462 check for link change with just one RA (with a prefix). Otherwise, 463 in case that the host can't be so sure, it will perform additional 464 RS/ RA exchanges to corroborate the decision. 466 When the host is sure that the prefix list is complete, a false 467 movement assumption may happen due to renumbering when a new prefix 468 is introduced in RAs. We may solve the renumbering problem with 469 minor modification like below. 471 1) When a router starts advertising a new prefix, for the time being, 472 every time the router advertises a new prefix in an RA, it includes 473 at least one old prefix in the same RA. The old prefix assures that 474 the host doesn't falsely assume a link change because of a new 475 prefix. After a while, hosts will recognize the new prefix as the 476 one assigned to the current link and update its prefix list. 478 2) To make matters more certain, we may mandate hosts to assume a 479 link change only after a new link-layer connection. It's reasonable 480 to assume that a new link-layer connection precedes a link change. 482 In this way, we may provide a fast and robust solution. If a host 483 can make the complete prefix list with certainty, it can check for 484 link change fast. Otherwise, it can fall back on a slow but robust 485 scheme. It is up to the host to decide which scheme to use. 487 4. Performance Analysis 489 In this section, we compute the probability that a host fails to 490 generate the complete prefix list and consequently assumes a link 491 change erroneously. 493 Suppose, in a link, there are N routers, R[1], R[2],...., R[N]. 495 Each R[i] advertises the Router Advertisement RA[i] with the prefix 496 P[i]. 498 It is the worst case that each router advertises the different 499 prefix. It is necessary to receive all the RA[i] to generate the 500 complete prefix list. 502 We assume there is a host, H, and when the host sends a Router 503 Solicitation, let P be the probability that it fails to receive a 504 RA[i], whether because of a RS loss or a RA loss. 506 So when the sends a Router Solicitation, the probability that it will 507 receive all RA[i] is (1-P)^N. 509 Let's assume the host performs RS/ RA exchange T times, 1,2,..,T. 511 Let S[k] be the set of all RAs which the host H successfully receives 512 at k-th RS/RA exchange. The probability that R[i] belongs to S[k] is 513 (1-P). 515 Let PL[k] be the set of prefixes which are made from S[k], i.e. the 516 set of P[j] such that RA[j] belongs to S[k]. Obviously, the 517 probability that P[i] belongs to PL[k] is also (1-P). 519 Let PL be the union of all PL[k], from k=1 to k=T. PL is the prefix 520 list made from performing RS/ RA exchange T times. 522 1) The probability of the complete prefix list generation 524 First the probability that P[i] belongs to PL is 1-P^T. The 525 probability that the prefix list PL is complete is (1-P^T)^N. 527 For example, assume the error rate is 1 % and there are 3 routers in 528 a link, then, with 2 RS/ RA exchanges, the probability of generating 529 an accurate Complete Prefix List is roughly 99.97 %. 531 At this point, assume that the host H receives a hint that a link 532 change might have happened and consequently initiates the procedure 533 of checking a link change. 535 2) The false DNA probability if the host checks for link change with 536 one RA. 538 Assume one RA, whether solicited or unsolicited arrives. If the host 539 H makes a decision based solely on the RA and the prefix list, the 540 probability that it falsely assume a link change is P^T. 542 For example, given the error rate is 1%, with 2 RS/ RA exchanges, the 543 probability of false movement detection is 1/ 10000. 545 3) The false DNA probability if the host checks for link change with 546 additional RS/ RA exchanges. 548 Instead of depending on the single RA, the host H performs additional 549 RS/ RA exchange U times, 1,2...U. Then the probability that H 550 falsely assumes a link change is 552 [P^T + P^U - P^(T+U)]^N. 554 For example, given the error rate is 1 % and there are 3 routers in a 555 link, if the host H performs 2 RS/ RA exchanges before the hint and 1 556 RS/ RA exchange after one, the probability of false movement 557 detection is roughly 1/1000000. 559 In the above formula, the result goes to P^(U*N) as T goes infinity. 560 The term P^(U*N) results from the probability that the host receives 561 no RA during U RS/ RA exchange after the hint. To see that it still 562 remains at the same link, a host needs to receive at least one RA. 564 We think it is reasonable to assume that the RS will be retransmitted 565 until at least one RA arrives. If we take a one more assumption that 566 the host receives at least one RA, the probability will be 568 [[P^T + P^U - P(T+U)]^N - P^(U*N)]/ [1- P^(U*N)] 570 The above converges to zero as T approaches infinity. 572 5. IANA Considerations 574 No new message formats or services are defined in this document. 576 6. Security Considerations 578 Because DNA schemes are based on Neighbor Discovery, its trust models 579 and threats are similar to the ones presented in [10]. Nodes 580 connected over wireless interfaces may be particularly susceptible to 581 jamming, monitoring and packet insertion attacks. Use of [9] to 582 secure Neighbor Discovery are important in achieving reliable 583 detection of network attachment. DNA schemes SHOULD incorporate the 584 solutions developed in IETF SEND WG if available, where assessment 585 indicates such procedures are required. 587 The threats specific to DNA is that an attacker might fool a node to 588 detect the attachment to a different link when it is in fact still 589 attached to the same link, and conversely, the attacker might fool a 590 node to not detect the change of a link. 592 The first form of attack is not very serious, since at worst it would 593 imply some additional higher-level signaling to register new 594 (care-of) address. The second form of attack can be more serious, 595 especially if the attacker can prevent a host from detecting any new 596 link. The protocol as specified would require an attacker to be 597 on-link and be authenticated and authorized to send router 598 advertisements when Secure Neighbor Discovery [9] is in use. But 599 even without SEND, an attacker would need to send router 600 advertisements containing the prefixes to which it wants the host to 601 be unable to detect movement. This can be done for a small number of 602 prefixes, but it isn't possible for the attacker to completely 603 disable DNA for all possible prefixes on other links. 605 7. Examples 607 This section contains some example packet flows showing the operation 608 of prefix based DNA. 610 7.1 Example with link-up indication 612 Assume the host has seen no link-up indication for a long time and 613 that it has the prefixes P1, P2, and P3 in its prefix list for the 614 interface. 616 The IP layer receives a link-up indication. This hint makes it 617 multicast a Router Solicitation and start collecting the received 618 prefixes in a new list of prefixes. 620 The host receives a Router Advertisement containing no prefixes. 621 This has no effect on the algorithm contained in this specification. 623 The host receives a Router Advertisement containing only the prefix 624 P4. This could be due to being attached to a different link or that 625 there is a new prefix on the existing link which is not announced in 626 RAs together with other prefixes, and a spurious hint. In this 627 example the host decides to wait for another RA before deciding. 629 One second later a router advertisement arrives which contains P1 and 630 P2. As a result the "new" prefix list has P1, P2, and P4 hence is 631 not disjoint from the "old" prefix list with P1, P2, and P3. Thus 632 the host concludes it has not moved to a different link and its 633 prefix list is now P1, P2, P3, and P4. 635 Some time later a new link-up indication is received by the IP layer. 636 Triggers sending a RS. 638 A Router Advertisement containing P5 and P6 is received by the host. 639 Based on some heuristic (the assumed frequence of prefixes being 640 added to an existing link) this time the host decides that it is on a 641 new link. 643 One second later a Router advertisement with prefix P7 is received. 644 Thus the prefix list now contains P5, P6, and P7. 646 7.2 Example without link-up indication 648 Assume the host has collected the prefixes P1, P2, and P3 in its 649 prefix list for the interface. 651 The host receives a Router Advertisement containing only prefix P4. 652 The fact that P4 is disjoint from the prefix list makes this be 653 treated as a hint. This hint makes the host multicast a Router 654 Solicitation and start collecting the received prefixes in a new list 655 of prefixes, which is initially set to contain P4. 657 The host receives a Router Advertisement containing no prefixes. 658 This has no effect on the algorithm contained in this specification. 660 The host receives a Router Advertisement containing only the prefix 661 P4. This could be due to being attached to a different link or that 662 there is a new prefix on the existing link which is not announced in 663 RAs together with other prefixes. In this example the host decides 664 to wait for another RA before deciding. 666 One second later a router advertisement arrives which contains P1 and 667 P2. As a result the "new" prefix list has P1, P2, and P4 hence is 668 not disjoint from the "old" prefix list with P1, P2, and P3. Thus 669 the host concludes it has not moved to a different link and its 670 prefix list is now P1, P2, P3, and P4. 672 Some time later the host receives a Router Advertisement containing 673 prefix P7. This is treated as a hint since it is not part of the 674 current set of prefixes. Triggers sending a RS and initializing the 675 new prefix list to P7. 677 A Router Advertisement containing P5 and P6 is received by the host. 678 This is disjoint with both of the previous prefix lists, thus the 679 host might be attached to a 3rd link after very briefly being 680 attached to the link with prefix P7.The host decides to wait for more 681 RAs. 683 One second later a Router advertisement with prefix P7 is received. 684 It still isn't certain whether P5, P6, and P7 are assigned to the 685 same link (and without a link-up indication such uncertainties do 686 exist). 688 A millisecond later a Router Advertisement with prefixes P6 and P7 is 689 received. Now the host knows that P5,P6, and P7 are assigned to the 690 same link. 692 Four seconds after the RS was sent and no RA containing P1, P2, P3, 693 or P4 has been received the host can conclude with high probability 694 that it is no longer attached to the link which had those prefixes. 696 8. References 698 8.1 Normative References 700 [1] Bradner, S., "IETF Rights in Contributions", BCP 78, RFC 3667, 701 February 2004. 703 [2] Bradner, S., "Intellectual Property Rights in IETF Technology", 704 BCP 79, RFC 3668, February 2004. 706 [3] Bradner, S., "Key words for use in RFCs to Indicate Requirement 707 Levels", BCP 14, RFC 2119, March 1997. 709 [4] Narten, T., Nordmark, E. and W. Simpson, "Neighbor Discovery for 710 IP Version 6 (IPv6)", RFC 2461, December 1998. 712 [5] Thomson, S. and T. Narten, "IPv6 Stateless Address 713 Autoconfiguration", RFC 2462, December 1998. 715 [6] Hinden, R. and S. Deering, "Internet Protocol Version 6 (IPv6) 716 Addressing Architecture", RFC 3513, April 2003. 718 [7] Choi, J., "Detecting Network Attachment in IPv6 Goals", 719 draft-ietf-dna-goals-00 (work in progress), June 2004. 721 8.2 Informative References 723 [8] Johnson, D., Perkins, C. and J. Arkko, "Mobility Support in 724 IPv6", RFC 3775, June 2004. 726 [9] Arkko, J., Kempf, J., Sommerfeld, B., Zill, B. and P. Nikander, 727 "SEcure Neighbor Discovery (SEND)", draft-ietf-send-ndopt-05 728 (work in progress), April 2004. 730 [10] Nikander, P., Kempf, J. and E. Nordmark, "IPv6 Neighbor 731 Discovery (ND) Trust Models and Threats", RFC 3756, May 2004. 733 [11] Nordmark, E., "MIPv6: from hindsight to foresight?", 734 draft-nordmark-mobileip-mipv6-hindsight-00 (work in progress), 735 November 2001. 737 [12] Pentland, B., "Router Advertisement Link Identification for 738 Mobile IPv6 Movement Detection", 739 draft-pentland-mobileip-linkid-00 (work in progress), May 2003. 741 [13] Choi, J., "Router Advertisement Issues for Movement Detection/ 742 Detection of Network Attachment", draft-jinchoi-ipv6-cra-00 743 (work in progress), October 2003. 745 [14] Daley, G. and J. Choi, "Movement Detection Optimization in 746 Mobile IPv6", draft-daley-mobileip-movedetect-01 (work in 747 progress), May 2003. 749 Authors' Addresses 751 JinHyeock Choi 752 Samsung AIT 753 i-Networking Lab 754 P.O.Box 111 Suwon 440-600 755 KOREA 757 Phone: +82 31 280 9233 758 EMail: jinchoe@samsung.com 760 Erik Nordmark 761 Sun Microsystems 762 17 Network Circle 763 Menlo Park, CA 94043 764 USA 766 Phone: +1 650 786 2921 767 EMail: erik.nordmark@sun.com 769 Intellectual Property Statement 771 The IETF takes no position regarding the validity or scope of any 772 Intellectual Property Rights or other rights that might be claimed to 773 pertain to the implementation or use of the technology described in 774 this document or the extent to which any license under such rights 775 might or might not be available; nor does it represent that it has 776 made any independent effort to identify any such rights. Information 777 on the procedures with respect to rights in RFC documents can be 778 found in BCP 78 and BCP 79. 780 Copies of IPR disclosures made to the IETF Secretariat and any 781 assurances of licenses to be made available, or the result of an 782 attempt made to obtain a general license or permission for the use of 783 such proprietary rights by implementers or users of this 784 specification can be obtained from the IETF on-line IPR repository at 785 http://www.ietf.org/ipr. 787 The IETF invites any interested party to bring to its attention any 788 copyrights, patents or patent applications, or other proprietary 789 rights that may cover technology that may be required to implement 790 this standard. Please address the information to the IETF at 791 ietf-ipr@ietf.org. 793 Disclaimer of Validity 795 This document and the information contained herein are provided on an 796 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 797 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 798 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 799 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 800 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 801 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 803 Copyright Statement 805 Copyright (C) The Internet Society (2004). This document is subject 806 to the rights, licenses and restrictions contained in BCP 78, and 807 except as set forth therein, the authors retain all their rights. 809 Acknowledgment 811 Funding for the RFC Editor function is currently provided by the 812 Internet Society.