idnits 2.17.1 draft-jinchoi-dna-cpl-01.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 1008. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 985. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 992. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 998. ** Found boilerplate matching RFC 3978, Section 5.4, paragraph 1 (on line 1014), 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 == The page length should not exceed 58 lines per page, but there was 23 longer pages, the longest (page 24) being 72 lines == It seems as if not all pages are separated by form feeds - found 0 form feeds but 26 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 788: '...nt. DNA schemes SHOULD incorporate th...' 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 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 (October 16, 2004) is 7124 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 697 == Unused Reference: '3' is defined on line 911, but no explicit reference was found in the text == Unused Reference: '11' is defined on line 941, but no explicit reference was found in the text == Unused Reference: '12' is defined on line 944, but no explicit reference was found in the text == Unused Reference: '13' is defined on line 948, but no explicit reference was found in the text ** Obsolete normative reference: RFC 2461 (ref. '1') (Obsoleted by RFC 4861) ** Obsolete normative reference: RFC 2462 (ref. '2') (Obsoleted by RFC 4862) ** Obsolete normative reference: RFC 3513 (ref. '3') (Obsoleted by RFC 4291) == Outdated reference: A later version (-04) exists of draft-ietf-dna-goals-03 ** Downref: Normative reference to an Informational draft: draft-ietf-dna-goals (ref. '4') -- Obsolete informational reference (is this intentional?): RFC 3775 (ref. '5') (Obsoleted by RFC 6275) == Outdated reference: A later version (-03) exists of draft-pentland-mobileip-linkid-02 == Outdated reference: A later version (-01) exists of draft-jinchoi-dna-frd-00 == Outdated reference: A later version (-01) exists of draft-daley-dna-det-fastra-00 == Outdated reference: A later version (-06) exists of draft-ietf-dna-link-information-00 Summary: 11 errors (**), 0 flaws (~~), 13 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: April 16, 2005 Erik Nordmark 4 SUN Microsystems 5 October 16, 2004 7 DNA with unmodified routers: Prefix list based approach 8 draft-jinchoi-dna-cpl-01.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 April 16, 2005. 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 currently attached link by 50 consulting the existing prefix list. This memo describes how to 51 generate the complete prefix list and to robustly detect the link 52 identity even in 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 Complete prefix list generation . . . . . . . . . . . . . 7 63 3.2 Link identity detection . . . . . . . . . . . . . . . . . 10 64 4. Protocol Specification . . . . . . . . . . . . . . . . . . . . 13 65 4.1 Conceptual data structures . . . . . . . . . . . . . . . . 13 66 4.2 Merging Candidate Link objects . . . . . . . . . . . . . . 14 67 4.3 Timer handling and Garbage Collection . . . . . . . . . . 14 68 4.4 Receiving link UP indications . . . . . . . . . . . . . . 14 69 4.5 Receiving valid router advertisements . . . . . . . . . . 15 70 4.6 Changing the link in Neighbor Discovery . . . . . . . . . 16 71 5. Performance Analysis . . . . . . . . . . . . . . . . . . . . . 18 72 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 20 73 7. Security Considerations . . . . . . . . . . . . . . . . . . . 21 74 8. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 75 8.1 Example with link-up indication . . . . . . . . . . . . . 22 76 8.2 Example without link-up indication . . . . . . . . . . . . 22 77 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 24 78 9.1 Normative References . . . . . . . . . . . . . . . . . . . . 24 79 9.2 Informative References . . . . . . . . . . . . . . . . . . . 24 80 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 25 81 Intellectual Property and Copyright Statements . . . . . . . . 26 83 1. Introduction 85 When a host establishes a new link-layer connection, it may or may 86 not have a valid IP configuration for the link, such as the subnet 87 prefixes on the attached link or the default router address. Though 88 the host has changed its network attachment point, it may still be at 89 the same link. The term 'link' used in this document is as defined 90 in RFC 2461 [1]. 92 To examine its IP configuration, a host may check for link change, 93 i.e. it verifies whether it is attached to the same or a different 94 link as before [4]. The host can keep current IP configuration if 95 and only if it remains at the same link. 97 Usually a host receives the link information from RA (Router 98 Advertisement) messages. However, as described in 2.2. [4], it's 99 difficult for a host to correctly detect the identity of a link with 100 a single RA. None of the information in an RA can indicate a link 101 change properly. Neither router address nor prefixes will do. 103 It may be better to design a new way to represent the identity of a 104 link, Link Identifier as proposed in [8]. Each link has its unique 105 Link Identifier and all routers in the link advertise the same Link 106 Identifier. In [9], Erik Nordmark proposed a new option, 'Location 107 Indication Option', which can serve as Link Identifier. Also Brett 108 Pentland and all submitted a draft about Link Identifier [10]. 110 However, even if some such new scheme is standardized and 111 implemented, hosts would still need to cope with routers which do not 112 (yet) implement such a scheme. Thus it makes sense to write down the 113 rules for how to robustly detect the link identity without assuming 114 changes to the routers. 116 2. Prefix list based approach 118 2.1 Approach 120 Currently there is one thing which can represent the identify of a 121 link, 123 'The set of all the global prefixes assigned to a link.' 125 If a host has the complete list of all the assigned prefixes, it can 126 properly determine whether a link change has occurred. If the host 127 receives an RA containing one or more prefixes and none of the 128 prefixes in it matches the previously known prefixes for the link, 129 then it is assumed to be a new link. 131 This works because each and every global prefix on a link must not be 132 used on any other link thus the sets of global prefixes on different 133 links must be disjoint. 135 For the purposes of determining the prefixes, this specification uses 136 both 'on-link' and 'addrconf' prefixes [1], that is, prefixes that 137 have either the 'on-link' flag set, the 'autonomous 138 address-autoconfiguration' flag set, or both flags set. This is a 139 safe approach since both the set of on-link and the set of addrconf 140 prefixes must be uniquely assigned to a link. 142 The difficulty lies both in ensuring that the complete prefix list 143 for a single link is known and preventing prefixes from possibly 144 different links to be viewed as the prefixes for a single link. This 145 is challenging given that a single router advertisements is not 146 required to include all prefixes for the link, router advertisements 147 might be subject to packet loss, new routers and new prefixes (due to 148 renumbering) might appear at any time on a link, and the host might 149 attach to a different link at any time. 151 If the prefix list determination is incorrect, there can be two 152 different types of failures. One is detecting a new link when in 153 fact the host remains attached to the same link. The other is 154 failing to detect when the host attaches to a different link. The 155 former failure is undesirable because it might trigger other 156 protocols, such as Mobile IPv6 [5], to do unneeded signaling, thus it 157 is important to minimize this type of failure. The latter type of 158 failure can lead to long outages when the host is not able to 159 communicate at all, thus these failures must be prevented. 161 2.2 Assumptions 163 In this approach, we assume that an interface of a host can not be 164 attached to multiple links at the same time. Though this kind of 165 multiple attachments is allowed in neither Ethernet nor 802.11b, it 166 may be possible in some Cellular System, especially CDMA. 168 2.3 Overview 170 Hints are used to tell a host that a link change might have happened. 171 This hint itself doesn't confirm a link change, but can be used to 172 initiate the appropriate procedures [4]. 174 In order to never view two different links as one it is critical that 175 when the host might have attached to a link, there has to be some 176 form of hint. This hint doesn't imply that a movement to a different 177 link has occurred, but instead, in the absence of such a hint there 178 could not have been an attachment to a different link. 180 If the IP stack is notified by the link layer when a new attachment 181 is established (e.g., when associating to a different access point in 182 802.11), this will serve as the hint. It helps to reduce the risk 183 that the assignment of an additional prefix to a link will be 184 misinterpreted as being attached to a different link. Note that this 185 hint is merely a local indication and does not require any protocol 186 changes. For instance, in many implementations this would be an 187 indication passed from a link-layer device driver to the IP layer. 189 For implementations which do not provide a "link up" indication, the 190 solution is to instead rely on either the receipt of an RA that 191 contains disjoint prefixes from the prefixes that have been collected 192 on the previous link or the lack of scheduled RAs as described in 193 [5], as a hint of an attachment to a possibly different link. 195 Independent of the type of hint used, once a hint is received the 196 host will start to collect a new set of prefixes for the possibly 197 different link, and compare them with the prefixes known from before 198 the hint. If there is one or more common prefixes it is safe to 199 assume that the host is attached to the same link, in which case the 200 prefixes learned after the hint can be merged with the prefixes 201 learned before the hint. But if the sets of prefixes are disjoint, 202 then at some point in time the host will determine that it is 203 attached to a different link. This process starts when the host is 204 powered on and first attaches to a link. 206 Since each router advertisement message isn't guaranteed to contain 207 all prefixes it is a challenge for a host to attain and retain the 208 complete prefix list, especially when packets can be lost on the 209 link. 211 The host has to rely on approximate knowledge of the prefix list 212 using RS/ RA exchanges. Just as specified in [1] the host sends an 213 RS (Router Solicitation) message to All-Router multicast address, 214 then waits for the solicited RAs. If there was no packet loss, the 215 host would receive the RAs from all the routers on the link in a few 216 seconds thereby knowing all the prefixes on the link. Taking into 217 account packet loss, the host may perform RS/ RA exchanges multiple 218 times to corroborate the result. 220 When a hint indicating a possible link change happens, if the host is 221 reasonably sure that its prefix list is complete, it can determine 222 whether it is attached to the same link on the reception of just one 223 RA containing one or more prefixes. 225 Otherwise, to make matters certain, the host may need at least to 226 wait for more RAs than a single one, or additionally perform multiple 227 RS/ RA exchanges after the hint. After each RS transmission, the 228 host waits for all RAs that would have been triggered by the RS as 229 one aspect of trying harder, and then sending multiple RSs (and 230 waiting for the resulting RAs) is a way to try even harder. 232 When hints are received frequently, this means that the host might 233 need to track more than two prefix lists at a time. Essentially, 234 each reception of a hint indicates the start of a new prefix list to 235 track, which may or may not turn out to be disjoint from a previously 236 known prefix list. 238 All tracking of the prefix lists must take the valid lifetime of the 239 prefixes into account, but apart from this limitation there isn't any 240 harm in the host remembering prefix lists from links it has attached 241 to earlier. The prefix list is maintained separately per network 242 interface. 244 3. DNA based on the complete prefix list 246 To each link, the set of prefixes is uniquely assigned. Two separate 247 links have two disjoint sets of prefixes. The two prefix lists of 248 two separate links have no element in common. 250 The identify of a link can be represented by the prefix list if it 251 correctly includes all the assigned prefixes. We denote the complete 252 prefix list as the list of all the prefixes assigned to the link. 253 Each link has its unique complete prefix list. We also say that the 254 prefix list is complete if all the prefixes on the link belong to it. 256 In case that a host has the complete prefix list, it can properly 257 determine whether it is attached to the same link or not, when it 258 receives a hint that a link change might have occurred. 260 This section presents a procedure to generate the complete prefix 261 list and a way to detect the link identity change based on the 262 existing prefix list even in the presence of packet losses. 264 3.1 Complete prefix list generation 266 To efficiently check for link change, a host always maintains the 267 list of all known prefixes on the link. This procedure of attaining 268 and retaining the complete prefix list is initialized when the host 269 is powered on. 271 Usually hosts execute and terminate the process of generating the 272 complete prefix list (of a link) at an old attachment point, before 273 handoff process begins. Though the procedure may take some time, 274 that doesn't matter unless the host moves very fast. A host can 275 generate the complete prefix list with reasonable certainty if it 276 remains attached to a link sufficiently long, approximately 10 277 seconds. 279 To generate the complete prefix list, presently the host has to rely 280 on approximate knowledge based on RS/ RA exchanges as follows. 282 First the host sends an RS to All-Router multicast address. Assuming 283 there is no packet loss, every router on the link would receive the 284 RS and usually reply with an RA containing all the prefixes that the 285 router advertises. 287 After an RS transmission, the host waits for all RAs that would have 288 been triggered by the RS. There is an upper limit on the delay of 289 the RAs. MIN_DELAY_BETWEEN_RAS (3 Sec) + MAX_RA_DELAY_TIME (0.5 Sec) 290 + network propagation delay is the maximum delay between an RS and 291 the resulting RAs [1]. 4 seconds would be a safe number for the host 292 to wait for the resulting RAs. Assuming no packet loss, within 4 293 seconds, the host would receive all the RAs and know all the 294 prefixes. 296 In case of packet loss, things get more complicated. In the above 297 process, there may be a packet loss that results in the generation of 298 the incomplete prefix list, i.e. the prefix list that misses some 299 prefix on the link. To remedy this deficiency, the host may perform 300 multiple RS/ RA exchanges to collect all the assigned prefixes. 302 After one RS/ RA exchange, to corroborate the completeness of the 303 prefix list, the host may send one or more RSs additionally and wait 304 for the resulting RAs. Each RS/ RA exchange produces the set of the 305 prefixes on the link. These sets may or may not be identical 306 depending on whether there happened a packet loss or not. Assuming 307 no packet loss, these sets would be the same. 309 The host takes the union of all these sets to generate the prefix 310 list. The more RS/ RA exchange the host performs, the more probable 311 that the resulting prefix list is complete. Section 4 gives the 312 detailed analysis. 314 By performing multiple (multicast) RS/ RA exchanges and combining the 315 results, the host can reasonably sure that the existing prefix list 316 is complete. 318 To ascertain whether its existing prefix list is complete or not, the 319 host can set its own policy. The host may take into consideration 320 the packet loss rate of the link and the number of RS/ RA exchanges 321 it performed. 323 For example, the host may keep track of how may RS/ RA exchanges it 324 performed on this attachment point, and if this is 3 or more it 325 assumes that the resulting prefix list is complete. But if this is 326 only 1 or 2, the host doesn't assume the completeness of the prefix 327 list. 329 In general, the higher the error rate, the more RS/ RA exchanges are 330 needed to assure the completeness of the prefix list. 332 It may happen that the host fails to generate the complete prefix 333 list. 335 The host may not be sure that the prefix list is complete. Or worse, 336 the host may falsely assume the completeness of the prefix list while 337 it is not. 339 The host may generate either 1) the incomplete prefix list, i.e. the 340 prefix list misses some prefix on the link or 2) the superfluous 341 prefix list, i.e. the prefix list that contains some prefix that is 342 not assigned to the link. 344 It is noted that 1) and 2) is not exclusive. The host may generate 345 the prefix list that misses some prefix on the link but includes the 346 prefix not assigned to the link. 348 Severe packet losses during prefix list generation may cause the 349 incomplete prefix list. Or the host may have undergone a link change 350 before finishing the procedure of the complete prefix list 351 generation. Later we will deal with the case that the host can't be 352 sure of the completeness of the prefix list. 354 Even if the host falsely assumes that the incomplete prefix list is 355 complete, the pain of that assumption is that the host might later 356 think it has moved to a different link when in fact it has not. 358 In case that a link change happens, even if the host has the 359 incomplete prefix list, it will detect a link change. Hence the 360 incomplete prefix list doesn't cause a connection disruption. But it 361 may cause excessive signaling messages, for example Binding Update 362 messages in [5]. 364 The superfluous prefix list presents a more serious problem. 366 Without the notification from the link-layer, the host can't perceive 367 that it has changed its attachment point, i.e. it has torn down an 368 old link-layer connection and established a new one. 370 So while generating the prefix list, without knowing it, the host may 371 be attached to multiple links in turn and accidentally end up with 372 prefixes from multiple links in the prefix list. 374 Here is an example. The host begins to collect the prefixes on a 375 link. But before the prefix list generation is completed, without 376 its knowledge, the host moves to a new link. Unaware that now it is 377 at the different link, the host keeps collecting prefixes with RS/ RA 378 exchanges to generate the prefix list. This results in the prefix 379 list containing prefixes from two different links. If the host uses 380 this prefix list, it fails to detect a link change. 382 Since, in the absence of link-up indications, a RA with a disjoint 383 set of prefixes is treated as a hint, the risk for confusion occurs 384 because the host can not tell from the RAs whether they were 385 solicited by the host. (RFC 2461 recommends that solicited RAs be 386 multicast.) 387 The simplest approach is for the host to assume that any RA received 388 within 4 seconds after sending a RS, assuming no intervening link-up 389 indication, where solicited, that is, the host has not moved to a 390 different link in that time. 392 In case the host moves fast, this assumption may lead to the 393 superfluous prefix list generation. The protocol is robust against 394 such confusion when a link-up indication is delivered to the IP layer 395 any time the host might have changed it's attachment. 397 If the host doesn't have any link-layer event notifications [14], for 398 example link up/down indications, it can't decide whether to use the 399 prefixes it receives for collecting information about the "old" link 400 or about the "new" link. 402 Maybe this is just something that should be stated as an assumption; 403 We may assume that when a host changes its attachment point, it will 404 be notified of the event and can distinguish the RAs arriving from 405 the old attachment point and the RAs from the new attachment point. 407 Thus we think the prefix-based approach has a stronger assumption 408 here than the Link Identifier-based approach, because the latter can 409 operate reliably without any link-layer event notifications [14]. 411 3.2 Link identity detection 413 When a host receives a hint that indicates a possible link change, it 414 initiates DNA procedure to determine whether it still remains at the 415 same link or not. At this time, the complete prefix generation may 416 or may not be finished. 418 First, if the host has finished the complete prefix list generation 419 and can be reasonably sure of its completeness, the receipt of a 420 single RA (with at least one prefix) is enough to detect the identify 421 of the currently attached link. 423 Assume that, after the hint, the host receives an RA that contains at 424 least one prefix. Either by an RS transmission or by an arrival of 425 an unsolicited RA, the host can get an RA. The host compares the 426 prefixes in the RA with those in the existing prefix list. If the RA 427 contains a prefix that is also a member of the existing prefix list, 428 the host is still at the same link. Otherwise, if none of the 429 prefixes in that RA matches the previously known prefixes, it is at a 430 different link. 432 It may happen that the host can not be sure that the prefix list is 433 complete. In this case, the host may use another scheme that makes a 434 decision based on multiple solicited RAs, instead of one RA. 436 Suppose that before finishing the prefix list generation, the host 437 receives the hint that indicates a possible link change. Then the 438 host can't assume the completeness of the prefix list. 440 The host can generate another (complete) prefix list to compensate 441 the uncertainty of the existing prefix list. After the hint, it 442 performs one or more RS/ RA exchanges additionally to collect all the 443 prefixes on the currently attached link. With the resulting 444 prefixes, the host generates the second prefix list. 446 Then the host compares two prefix lists and if the lists are 447 disjoint, i.e. have no prefix in common, it assumes that a link 448 change has occurred. Usually this is done at a new attachment point. 450 For example, assume that the host keeps track of how many RS/ RA 451 exchanges it performed at a link. If this is 3 or more, the host 452 assumes that it have seen all the prefixes. Suppose that the host 453 has done a single RS/RA exchange, then it receives a link up 454 notification that causes it to initiate the DNA procedure. For a 455 better judgment, the host performs new RS/RA exchanges. If the host 456 tracks the list of prefixes received (from all received RAs) before 457 the link up notification and after the one, it can compare the lists 458 to check for link change. In case that the lists are disjoint, the 459 host can assume it has moved. 461 The difference with the previous case is that the host doesn't use 462 the first RA received after the hint to make its decision. Instead 463 it waits for the timeout and then use the received set of prefixes to 464 determine whether a link change has occurred. Though slower, this is 465 more robust. 467 In summary, first a host makes the complete prefix list. When a hint 468 occurs, if the host decides that the prefix list is complete, it will 469 check for link change with just one RA (with a prefix). Otherwise, 470 in case that the host can't be so sure, it will perform additional 471 RS/ RA exchanges to corroborate the decision. 473 When the host is sure that the prefix list is complete, a false 474 movement assumption may happen due to renumbering when a new prefix 475 is introduced in RAs. We may solve the renumbering problem with 476 minor modification like below. 478 1) When a router starts advertising a new prefix, for the time being, 479 every time the router advertises a new prefix in an RA, it includes 480 at least one old prefix in the same RA. The old prefix assures that 481 the host doesn't falsely assume a link change because of a new 482 prefix. After a while, hosts will recognize the new prefix as the 483 one assigned to the current link and update its prefix list. 485 2) To make matters more certain, we may mandate hosts to assume a 486 link change only after a new link-layer connection. It's reasonable 487 to assume that a new link-layer connection precedes a link change. 489 In this way, we may provide a fast and robust solution. If a host 490 can make the complete prefix list with certainty, it can check for 491 link change fast. Otherwise, it can fall back on a slow but robust 492 scheme. It is up to the host to decide which scheme to use. 494 4. Protocol Specification 496 This section provides the actual specification for a host 497 implementing this draft. For generality the specification assumes 498 that the host retains multiple (an unbounded set) of prefix lists 499 until the information times out, while an actual implementation would 500 limit the number of sets maintained. 502 This description assumes that the link layer driver provides a 'link 503 up' indication when the host might have moved to a different link. 505 4.1 Conceptual data structures 507 This section describes a conceptual model of one possible data 508 structure organization that hosts will maintain for the purposes of 509 DNA. The described organization is provided to facilitate the 510 explanation of how the CPL protocol should behave. This document 511 does not mandate that implementations adhere to this model as long as 512 their external behavior is consistent with that described in this 513 document. 515 The basic conceptual data type for the protocol is the Candidate Link 516 object. This is an object which contains all the information learned 517 from router advertisement messages that are known to belong to a 518 single link. In particular, this includes 519 o The prefixes learned from the prefix information options, the A/L 520 bits and their valid and preferred lifetimes. 521 o The default routers and their lifetimes. 522 o Any other option content such as the MTU etc. 524 The lifetimes for the prefixes and default routers in the Candidate 525 Link objects should decrement in real time that is, at any point in 526 time they will be the remaining lifetime. An implementation could 527 handle that by recording the 'expire' time for the information, or by 528 periodically decrementing the remaining lifetime. 530 For each interface, the host maintains a notion of its Current 531 Candidate Link (CCL) object. As we will see below, this might 532 actually be different than the prefix list and default router lists 533 maintained by Neighbor Discovery when the host is in the process of 534 determining whether it has attached to a different link or not. 536 In addition, the host maintains previous Candidate Link objects. It 537 is TBD whether these should be per interface, shared across 538 interfaces of the same L2 type (e.g., all Ethernet interfaces), or be 539 shared across all interfaces of the host. It isn't currently clear 540 if there are any security issues associated with sharing this 541 information across different interfaces. The previous Candidate Link 542 objects can be found by knowing at least one prefix that is part of 543 the object. 545 The operations on Candidate Link objects is to create a new one, 546 discard one, and merge two of them together. The issues with merging 547 are discussed in the next section. 549 For each interface, the host maintains the last time a valid router 550 advertisement was received (called time_last_RA_received in this 551 document), which actually ignores RAs without prefix options, and the 552 last time a link UP indication was received from the link layer on 553 the host (called time_last_linkUP_received in this document). 554 Together these two conceptual variables serve to identify when a RA 555 containing disjoint prefixes can't be due to being attached to a new 556 link, because there was no linkUP indication. 558 4.2 Merging Candidate Link objects 560 When a host has been collecting information about a potentially 561 different link in its Current Candidate Link object, and it discovers 562 that it is in fact the same link as another Candidate Link object, 563 then it needs to merge the information between the two objects. 564 Since the CCL contains the most recent information, any information 565 contained in it will override the information in the old Candidate 566 Link, for example the remaining lifetimes for the prefixes. When the 567 two objects contain different pieces of information, for instance 568 different prefixes or default routers, the union of these are used in 569 the resulting merged object. 571 4.3 Timer handling and Garbage Collection 573 As stated about the lifetimes for the prefixes and default routers in 574 each Candidate Link object must be decremented in real time. When a 575 prefix' valid lifetime has expired, the prefix should be removed from 576 its object. Likewise, when a default router lifetime has expired, it 577 should be removed from its object. When a Candidate Link object 578 contains neither any prefixes nor any default routers, the object, 579 including additional information such as MTU, should be discarded. 581 There is nothing to prevent a host from garbage collecting Candidate 582 Link objects before their expire. However, for performance reason a 583 host must be able to retain at least two of them at any given time. 585 4.4 Receiving link UP indications 587 When the host receives a link UP indication from its link layer, the 588 only action is to set time_last_linkUP_received to the current time. 590 4.5 Receiving valid router advertisements 592 When a host receives a valid router advertisement message (with the 593 validity checks specified in [1]) it performs the following 594 processing in addition to the processing specified in [1] and [2] 596 If the valid router advertisement does not contain any prefix 597 information options, then not further processing is performed. Note 598 that not even the time_last_RA_received is updated. 600 If time_last_RA_received is more recent than 601 time_last_linkUP_received, then the host could not possibly have 602 moved to a different link. Hence the only action needed for DNA is 603 to update the current Candidate Link object with the information in 604 the RA, and set time_last_RA_received to the current time. 606 The remaining processing occurs when a linkUP was received and no RA 607 containing prefix options has yet been received. This is the case 608 when the host needs to perform comparisons of the prefix sets in its 609 Candidate Link objects and the prefix set in the router 610 advertisement. In all these cases time_last_RA_received is set to 611 the current time. 613 Should the received RA contain at least one prefix which is in the 614 prefix list in the CCL, then the host is still attached to the same 615 link, and just needs to update the CCL with any new information in 616 the RA. 618 Otherwise, if received RA contains one or more prefixes which is part 619 of the prefix list in some retained Candidate Link object, then the 620 host has most likely moved to that link. As a result the host will 621 retain the content of the CCL for future matching, but switch the CCL 622 to be that matching object. The now new CCL should be updated based 623 on the information in the RA. Then the DNA module informs the 624 Neighbor Discovery module to replace the old information with the 625 information in the new CCL. 627 It is possible that the above comparison will result in matching 628 multiple Candidate Link objects. For example, if the RA contains the 629 prefixes P1 and P2, and there is one Candidate Link object with P1 630 and P3 and other Candidate Link object with P2 and P4. This should 631 not happen during normal operation, but if links have been renumbered 632 or physical merged into one before the lifetimes in the Candidate 633 Link objects expired, then the host could observe this. The most 634 sensible action would be for the host to merge all such matching 635 Candidate Link objects together with the information in the receive 636 RA and make this the new CCL. Doing this merging correctly probably 637 requires that each Candidate Link object contains the time it was 638 last updated by a RA, so that more recent information can override 639 older information. Note that this case is one reason one needs to be 640 concerned about security issues when Candidate Link objects are 641 shared across multiple interfaces. 643 Above the easy case of determining being on the same link has been 644 handled. The remaining cases show up when the first RA after a link 645 UP indication contains prefixes that are new to the host. In this 646 case it isn't obvious whether the host has moved or not. Thus the 648 host create a new Candidate Link object which it initializes with the 649 information in the received RA, and makes this object the CCL. 650 However, it does not yet treat this as a new link; it is merely a 651 candidate. 653 Then the host waits for more router advertisement messages. At a 654 minimum it waits for 4 seconds, that is, it starts a timer and router 655 advertisements that are received during that time interval are 656 processed as specified above. This processing might result in 657 finding a prefix in common with a Candidate Link object in which case 658 the host knows whether and to which link it has moved. But should 659 the 4 seconds expire without any common prefix, then it will conclude 660 that it has moved to a new link and inform the rest of the host of 661 the movement. Note that the arrival of a new link UP indication 662 during the 4 second timer must prevent the timer from firing. In 663 this case the host might yet again have moved so it is necessary to 664 restart the process of inspecting the router advertisements. 666 Subject to local policy and perhaps the hosts knowledge of the packet 667 loss characteristics of the interface or type of L2 technology, the 668 host can try harder than just waiting for 4 seconds. It is allowed 669 to multicast up to MAX_RTR_SOLICITATIONS [1] router solicitation 670 messages spaced RTR_SOLICITATION_INTERVAL apart. In the most 671 conservative approach this means a 12 second delay until the host 672 will declare that is has moved to a new link. Just as above, this 673 process should be terminated should a new link UP indication arrive 674 during the 12 seconds. 676 4.6 Changing the link in Neighbor Discovery 678 When DNA detects that it has moved to a different link this needs to 679 cause Neighbor Discovery, Address autoconfiguration, and DHCPv6 to 680 take some action. While the full implications are outside of the 681 scope of this document, here is what we know about the impact on 682 Neighbor Discovery. 684 Everything learned from the router advertisements on the interface 685 should be discarded, such as the default router list and the on-link 686 prefix list. Furthermore, all neighbor cache entries, in particular 687 redirects, need to be discarded. Finally the information in the 688 Current Candidate Link object is used to create a new default router 689 list and on-link prefix list. 691 5. Performance Analysis 693 In this section, we compute the probability that a host fails to 694 generate the complete prefix list and consequently assumes a link 695 change erroneously. 697 Suppose, in a link, there are N routers, R[1], R[2],...., R[N]. 699 Each R[i] advertises the Router Advertisement RA[i] with the prefix 700 P[i]. 702 It is the worst case that each router advertises the different 703 prefix. It is necessary to receive all the RA[i] to generate the 704 complete prefix list. 706 We assume there is a host, H, and when the host sends a Router 707 Solicitation, let P be the probability that it fails to receive a 708 RA[i] because of a RA loss. For the simplicity, we disregard RS 709 losses. 711 So when the sends a Router Solicitation, the probability that it will 712 receive all RA[i] is (1-P)^N. 714 Let's assume the host performs RS/ RA exchange T times, 1,2,..,T. 716 Let S[k] be the set of all RAs which the host H successfully receives 717 at k-th RS/RA exchange. The probability that R[i] belongs to S[k] is 718 (1-P). 720 Let PL[k] be the set of prefixes which are made from S[k], i.e. the 721 set of P[j] such that RA[j] belongs to S[k]. Obviously, the 722 probability that P[i] belongs to PL[k] is also (1-P). 724 Let PL be the union of all PL[k], from k=1 to k=T. PL is the prefix 725 list made from performing RS/ RA exchange T times. 727 1) The probability of the complete prefix list generation 729 First the probability that P[i] belongs to PL is 1-P^T. The 730 probability that the prefix list PL is complete is (1-P^T)^N. 732 For example, assume the error rate is 1 % and there are 3 routers in 733 a link, then, with 2 RS/ RA exchanges, the probability of generating 734 an accurate Complete Prefix List is roughly 99.97 %. 736 At this point, assume that the host H receives a hint that a link 737 change might have happened and consequently initiates the procedure 738 of checking a link change. 740 2) The false DNA probability if the host checks for link change with 741 one RA. 743 Assume one RA, whether solicited or unsolicited arrives. If the host 744 H makes a decision based solely on the RA and the prefix list, the 745 probability that it falsely assume a link change is P^T. 747 For example, given the error rate is 1%, with 2 RS/ RA exchanges, the 748 probability of false movement detection is 1/ 10000. 750 3) The false DNA probability if the host checks for link change with 751 additional RS/ RA exchanges. 753 Instead of depending on the single RA, the host H performs additional 754 RS/ RA exchange U times, 1,2...U. Then the probability that H 755 falsely assumes a link change is 757 [P^T + P^U - P^(T+U)]^N. 759 For example, given the error rate is 1 % and there are 3 routers in a 760 link, if the host H performs 2 RS/ RA exchanges before the hint and 1 761 RS/ RA exchange after one, the probability of false movement 762 detection is roughly 1/1000000. 764 In the above formula, the result goes to P^(U*N) as T goes infinity. 765 The term P^(U*N) results from the probability that the host receives 766 no RA during U RS/ RA exchange after the hint. To see that it still 767 remains at the same link, a host needs to receive at least one RA. 769 We think it is reasonable to assume that the RS will be retransmitted 770 until at least one RA arrives. If we take a one more assumption that 771 the host receives at least one RA, the probability will be 773 [[P^T + P^U - P(T+U)]^N - P^(U*N)]/ [1- P^(U*N)] 775 The above converges to zero as T approaches infinity. 777 6. IANA Considerations 779 No new message formats or services are defined in this document. 781 7. Security Considerations 783 Because DNA schemes are based on Neighbor Discovery, its trust models 784 and threats are similar to the ones presented in [7]. Nodes 785 connected over wireless interfaces may be particularly susceptible to 786 jamming, monitoring and packet insertion attacks. Use of [6] to 787 secure Neighbor Discovery are important in achieving reliable 788 detection of network attachment. DNA schemes SHOULD incorporate the 789 solutions developed in IETF SEND WG if available, where assessment 790 indicates such procedures are required. 792 The threats specific to DNA are that an attacker might fool a node to 793 detect attachment to a different link when it is in fact still 794 attached to the same link, and conversely, the attacker might fool a 795 node to not detect attachment to a new link. 797 The first form of attack is not very serious, since at worst it would 798 imply some additional higher-level signaling to register a new 799 (care-of) address. The second form of attack can be more serious, 800 especially if the attacker can prevent a host from detecting a new 801 link. The protocol as specified would require an attacker to be 802 on-link and be authenticated and authorized to send router 803 advertisements when Secure Neighbor Discovery [6] is in use. 804 However, even without SEND, an attacker would need to send router 805 advertisements containing the prefixes to which it wants the host to 806 be unable to detect movement. This can be done for a small number of 807 prefixes, but it isn't possible for the attacker to completely 808 disable DNA for all possible prefixes on other links. 810 8. Examples 812 This section contains some example packet flows showing the operation 813 of prefix based DNA. 815 8.1 Example with link-up indication 817 Assume the host has seen no link-up indication for a long time and 818 that it has the prefixes P1, P2, and P3 in its prefix list for the 819 interface. 821 The IP layer receives a link-up indication. This hint makes it 822 multicast a Router Solicitation and start collecting the received 823 prefixes in a new list of prefixes. 825 The host receives a Router Advertisement containing no prefixes. 826 This has no effect on the algorithm contained in this specification. 828 The host receives a Router Advertisement containing only the prefix 829 P4. This could be due to being attached to a different link or that 830 there is a new prefix on the existing link which is not announced in 831 RAs together with other prefixes, and a spurious hint. In this 832 example the host decides to wait for another RA before deciding. 834 One second later a router advertisement arrives which contains P1 and 835 P2. As a result the "new" prefix list has P1, P2, and P4 hence is 836 not disjoint from the "old" prefix list with P1, P2, and P3. Thus 837 the host concludes it has not moved to a different link and its 838 prefix list is now P1, P2, P3, and P4. 840 Some time later a new link-up indication is received by the IP layer. 841 Triggers sending a RS. 843 A Router Advertisement containing P5 and P6 is received by the host. 844 Based on some heuristic (the assumed frequency of prefixes being 845 added to an existing link) this time the host decides that it is on a 846 new link. 848 One second later a Router advertisement with prefix P7 is received. 849 Thus the prefix list now contains P5, P6, and P7. 851 8.2 Example without link-up indication 853 Assume the host has collected the prefixes P1, P2, and P3 in its 854 prefix list for the interface. 856 The host receives a Router Advertisement containing only prefix P4. 857 The fact that P4 is disjoint from the prefix list makes this be 858 treated as a hint. This hint makes the host multicast a Router 859 Solicitation and start collecting the received prefixes in a new list 860 of prefixes, which is initially set to contain P4. 862 The host receives a Router Advertisement containing no prefixes. 863 This has no effect on the algorithm contained in this specification. 865 The host receives a Router Advertisement containing only the prefix 866 P4. This could be due to being attached to a different link or that 867 there is a new prefix on the existing link which is not announced in 868 RAs together with other prefixes. In this example the host decides 869 to wait for another RA before deciding. 871 One second later a router advertisement arrives which contains P1 and 872 P2. As a result the "new" prefix list has P1, P2, and P4 hence is 873 not disjoint from the "old" prefix list with P1, P2, and P3. Thus 874 the host concludes it has not moved to a different link and its 875 prefix list is now P1, P2, P3, and P4. 877 Some time later the host receives a Router Advertisement containing 878 prefix P7. This is treated as a hint since it is not part of the 879 current set of prefixes. Triggers sending a RS and initializing the 880 new prefix list to P7. 882 A Router Advertisement containing P5 and P6 is received by the host. 883 This is disjoint with both of the previous prefix lists, thus the 884 host might be attached to a 3rd link after very briefly being 885 attached to the link with prefix P7.The host decides to wait for more 886 RAs. 888 One second later a Router advertisement with prefix P7 is received. 889 It still isn't certain whether P5, P6, and P7 are assigned to the 890 same link (and without a link-up indication such uncertainties do 891 exist). 893 A millisecond later a Router Advertisement with prefixes P6 and P7 is 894 received. Now the host knows that P5,P6, and P7 are assigned to the 895 same link. 897 Four seconds after the RS was sent and no RA containing P1, P2, P3, 898 or P4 has been received the host can conclude with high probability 899 that it is no longer attached to the link which had those prefixes. 901 9. References 903 9.1 Normative References 905 [1] Narten, T., Nordmark, E. and W. Simpson, "Neighbor Discovery for 906 IP Version 6 (IPv6)", RFC 2461, December 1998. 908 [2] Thomson, S. and T. Narten, "IPv6 Stateless Address 909 Autoconfiguration", RFC 2462, December 1998. 911 [3] Hinden, R. and S. Deering, "Internet Protocol Version 6 (IPv6) 912 Addressing Architecture", RFC 3513, April 2003. 914 [4] Choi, J., "Detecting Network Attachment in IPv6 Goals", 915 draft-ietf-dna-goals-03 (work in progress), October 2004. 917 9.2 Informative References 919 [5] Johnson, D., Perkins, C. and J. Arkko, "Mobility Support in 920 IPv6", RFC 3775, June 2004. 922 [6] Arkko, J., Kempf, J., Sommerfeld, B., Zill, B. and P. Nikander, 923 "SEcure Neighbor Discovery (SEND)", draft-ietf-send-ndopt-06 924 (work in progress), July 2004. 926 [7] Nikander, P., Kempf, J. and E. Nordmark, "IPv6 Neighbor 927 Discovery (ND) Trust Models and Threats", RFC 3756, May 2004. 929 [8] Choi, J. and E. Nordmark, "DNA solution framework", 930 draft-jinchoi-dna-soln-frame-00 (work in progress), July 2004. 932 [9] Nordmark, E., "MIPv6: from hindsight to foresight?", 933 draft-nordmark-mobileip-mipv6-hindsight-00 (work in progress), 934 November 2001. 936 [10] Pentland, B., "Router Advertisement Link Identification for 937 Mobile IPv6 Movement Detection", 938 draft-pentland-mobileip-linkid-02 (work in progress), July 939 2004. 941 [11] Choi, J., "Fast Router Discovery with RA Caching", 942 draft-jinchoi-dna-frd-00 (work in progress), July 2004. 944 [12] Kempf, J., Khalil, M. and B. Pentland, "IPv6 Fast Router 945 Advertisement", draft-mkhalil-ipv6-fastra-05 (work in 946 progress), July 2004. 948 [13] Daley, G., "Deterministic Fast Router Advertisement 949 Configuration", draft-daley-dna-det-fastra-00 (work in 950 progress), July 2004. 952 [14] Yegin, A., "Link-layer Event Notifications for Detecting 953 Network Attachments", draft-ietf-dna-link-information-00 (work 954 in progress), September 2004. 956 Authors' Addresses 958 JinHyeock Choi 959 Samsung AIT 960 Communication & N/W Lab 961 P.O.Box 111 Suwon 440-600 962 KOREA 964 Phone: +82 31 280 9233 965 EMail: jinchoe@samsung.com 967 Erik Nordmark 968 Sun Microsystems 969 17 Network Circle 970 Menlo Park, CA 94043 971 USA 973 Phone: +1 650 786 2921 974 EMail: erik.nordmark@sun.com 976 Intellectual Property Statement 978 The IETF takes no position regarding the validity or scope of any 979 Intellectual Property Rights or other rights that might be claimed to 980 pertain to the implementation or use of the technology described in 981 this document or the extent to which any license under such rights 982 might or might not be available; nor does it represent that it has 983 made any independent effort to identify any such rights. Information 984 on the procedures with respect to rights in RFC documents can be 985 found in BCP 78 and BCP 79. 987 Copies of IPR disclosures made to the IETF Secretariat and any 988 assurances of licenses to be made available, or the result of an 989 attempt made to obtain a general license or permission for the use of 990 such proprietary rights by implementers or users of this 991 specification can be obtained from the IETF on-line IPR repository at 992 http://www.ietf.org/ipr. 994 The IETF invites any interested party to bring to its attention any 995 copyrights, patents or patent applications, or other proprietary 996 rights that may cover technology that may be required to implement 997 this standard. Please address the information to the IETF at 998 ietf-ipr@ietf.org. 1000 Disclaimer of Validity 1002 This document and the information contained herein are provided on an 1003 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1004 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 1005 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 1006 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 1007 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1008 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1010 Copyright Statement 1012 Copyright (C) The Internet Society (2004). This document is subject 1013 to the rights, licenses and restrictions contained in BCP 78, and 1014 except as set forth therein, the authors retain all their rights. 1016 Acknowledgment 1018 Funding for the RFC Editor function is currently provided by the 1019 Internet Society.