idnits 2.17.00 (12 Aug 2021) /tmp/idnits34865/draft-thubert-tree-discovery-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 18 instances of too long lines in the document, the longest one being 2 characters in excess of 72. ** 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 266: '...covery option, the non-MR MUST set the...' RFC 2119 keyword, line 349: '...d definitions that MUST be followed be...' RFC 2119 keyword, line 366: '...y part of a tree MAY move at any time ...' RFC 2119 keyword, line 369: '... MR MUST NOT move down the tree ...' RFC 2119 keyword, line 389: '...ame time, the MR MAY send a Binding Up...' (5 more instances...) 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 (May 2004) is 6580 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) == Unused Reference: '1' is defined on line 552, but no explicit reference was found in the text == Unused Reference: '2' is defined on line 555, but no explicit reference was found in the text == Unused Reference: '4' is defined on line 562, but no explicit reference was found in the text == Unused Reference: '5' is defined on line 566, 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) == Outdated reference: draft-ietf-mobileip-ipv6 has been published as RFC 3775 == Outdated reference: draft-ietf-nemo-basic-support has been published as RFC 3963 == Outdated reference: draft-ietf-nemo-requirements has been published as RFC 4886 ** Downref: Normative reference to an Informational draft: draft-ietf-nemo-requirements (ref. '5') == Outdated reference: draft-ietf-nemo-terminology has been published as RFC 4885 ** Downref: Normative reference to an Informational draft: draft-ietf-nemo-terminology (ref. '6') -- Possible downref: Normative reference to a draft: ref. '7' -- Possible downref: Normative reference to a draft: ref. '8' == Outdated reference: draft-ietf-ipv6-router-selection has been published as RFC 4191 Summary: 10 errors (**), 0 flaws (~~), 11 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 NEMO Working Group P. Thubert 3 Internet-Draft Cisco 4 Expires: octobre 30, 2004 N. Montavont 5 LSIIT - ULP 6 May 2004 8 Nested Nemo Tree Discovery 9 draft-thubert-tree-discovery-00.txt 11 Status of this Memo 13 This document is an Internet-Draft and is in full conformance with 14 all provisions of Section 10 of RFC2026. 16 Internet-Drafts are working documents of the Internet Engineering 17 Task Force (IETF), its areas, and its working groups. Note that other 18 groups may also distribute working documents as Internet-Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-Drafts as reference 23 material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at http:// 26 www.ietf.org/ietf/1id-abstracts.txt. 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 This Internet-Draft will expire on octobre 30, 2004. 33 Copyright Notice 35 Copyright (C) The Internet Society (2004). All Rights Reserved. 37 Abstract 39 The purpose of this paper is to describe a minimum set of features 40 that extends the Nemo basic support in order to avoid loops in the 41 nested Nemo case. As a result, Mobile Routers assemble into a tree 42 that can be optimized based on various metrics. 44 Table of Contents 46 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 48 2. Terms and Abbreviations . . . . . . . . . . . . . . . . . . 3 50 3. Motivations . . . . . . . . . . . . . . . . . . . . . . . . 4 51 3.1 Multihomed nested mobile network . . . . . . . . . . . . . . 4 52 3.2 Loops in nested Nemo . . . . . . . . . . . . . . . . . . . . 5 54 4. Router Advertisement extensions . . . . . . . . . . . . . . 6 55 4.1 Router Advertisement message . . . . . . . . . . . . . . . . 6 56 4.2 Tree Information Option . . . . . . . . . . . . . . . . . . 6 58 5. Tree Discovery . . . . . . . . . . . . . . . . . . . . . . . 8 59 5.1 tree selection . . . . . . . . . . . . . . . . . . . . . . . 9 60 5.2 Tree Hop Timer . . . . . . . . . . . . . . . . . . . . . . . 10 61 5.3 Collisions and stability . . . . . . . . . . . . . . . . . . 11 62 5.3.1 Hold down . . . . . . . . . . . . . . . . . . . . . . . . . 11 63 5.3.2 Instability . . . . . . . . . . . . . . . . . . . . . . . . 11 64 5.3.3 Collision . . . . . . . . . . . . . . . . . . . . . . . . . 12 66 6. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 12 68 References . . . . . . . . . . . . . . . . . . . . . . . . . 13 70 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 14 72 Intellectual Property and Copyright Statements . . . . . . . 15 74 1. Introduction 76 As per Nemo Basic support, a Mobile Router autoconfigures a single 77 Care of Address to register to its Home Agent and terminate its MR-HA 78 tunnel. That CoA is the MR's point of attachment to the nested Nemo. 80 Consequently, if loops are avoided, the nested Nemo assumes the shape 81 of a tree. The nodes of the tree are Mobile Routers, the root is 82 either a fixed or a Mobile Router, called in the latter case the root 83 Mobile Router in NEMO terminology [6]. The leaves are mobile or fixed 84 hosts, called Local Fixed Nodes, Local Mobile Nodes and Visiting 85 Mobile Nodes in the NEMO terminology. 87 This paper provides (1) a minimum extension to IPv6 Neighbour 88 Discovery Router Advertisements in order to ensure that Mobile 89 Routers attaching to one another actually avoid loops and end up 90 forming a tree, and (2) the minimum common part of all MR algorithms 91 that is required to ensure that whatever their specific decisions, 92 loops between MRs will be avoided. 94 The method is based on an autonomous decision by each MR with no 95 global state convergence such as a MANET proactive routing protocol. 96 In fact, MRs may make different decisions from a same input, based on 97 their own configuration and their own algorithms. 99 In order to build trees of Mobile Routers, we propose an extension to 100 the ICMP Router Advertisement (RA) message, the Tree Information 101 Option (TIO). The RA/TIO allows MRs to advertise the tree they belong 102 to, and to select and move to the best location within the available 103 trees. MRs propagate the TIO down the tree, updating some metrics 104 such as the tree depth, leaving alone root information such as the 105 tree identifier, and sending the result in RAs over the ingress 106 interfaces. 108 2. Terms and Abbreviations 110 This document assumes that the reader is familiar with Mobile IPv6 as 111 defined in [3] and with the concept of Mobile Router defined in the 112 Nemo terminology document [6]. 114 For the needs of this paper, the following new definitions are 115 introduced: 117 Nemo Clusterhead: The root of a tree of mobile routers. When the tree 118 of Mobile Routers is attached to the infrastructure, the fixed 119 Access Router may act as cluster head if it supports the Tree 120 Information Option described in this document. If it does not, 121 then the Clusterhead coincides with the root MR in NEMO 122 terminology. A clusterhead is elected even when the tree is not 123 attached to the infrastructuture. A stand-alone MR is a 124 Clusterhead. 126 Floating Tree: A Nested Nemo which Clusterhead is a MR that is not 127 attached to an AR. 129 Grounded Tree: A Nested Nemo whose Clusterhead is attached to the 130 infrastructure. In other words, the clusterhead is either a fixed 131 router that supports RA/TIO or is a MR which attachment router is 132 a fixed router that does not support RA/TIO. 134 Mobile Access Router: A Mobile Router that provides Access Router 135 services to other MRs. 137 Attachment Router: The Router that is selected as Access Router by a 138 Mobile Router, making it its parent in the nested NEMO tree. 140 Propagation: The action by a Mobile Router that consists in receiving 141 a RA/TIO from its Attachment Router, recomputing a few specific 142 fields, removing unknown suboption, and appending the resulting 143 TIO to RAs sent over the ingress interfaces. 145 3. Motivations 147 3.1 Multihomed nested mobile network 149 A nested mobile network that is made of multiple MRs having a direct 150 connection to the Internet is said to be multihomed. Multihoming in 151 Nemo offers useful properties to MNNs. Reference [8] lists potential 152 multihomed configurations for Nemo and explains the different 153 problems and advantages that some configurations may introduce. 154 Multihoming offers three main abilities to the Nemo: it allows route 155 recovery on failure, redundancy and load-sharing between MRs (or 156 between MRs'interfaces). However, for the moment there are no 157 requirements nor protocol defining how to use several egress 158 interfaces inside a Nemo. 160 In a nested Nemo, the hierarchy of MRs increases the complexity of 161 the route and/or router selection for MNNs. Each level of a Nemo 162 implies the usage of a new tunnel between the MR and its home agent. 163 Thus if a MNN connects to a sub-Nemo which is also a sub-Nemo, 164 packets from the MNN will be encapsulated three times. 166 When the Nemo where the MN is connected to is multihomed, the MN may 167 have the choice between several AR to be its default router. 168 Reference [9] introduces new options in Router Advertisement to allow 169 any node on a link to choose between several routers. This option 170 mainly consists of a 2-bits flag that indicates the preference of the 171 router (low, medium or high). Furthermore, the same flag can be set 172 in the Route Information option indicating the preference of a 173 specific prefix. Therefore, any node can determine its best default 174 router(s) according to a given destination and its best router for 175 default, which will be used by default. 177 However this preference is only useful in a flat topology; It gives a 178 way to the node to choose between different access routers 179 advertising prefixes on the node link. But if the node is inside a 180 hierarchical topology (some access routers are not at the same level) 181 the node can not learn the level of each access router. 183 One of the usage of the new option introduced in this document is to 184 distribute information on the hierarchy of MRs. This information can 185 be distributed to ARs, MRs and MNNs as well in order to allow better 186 route selection and to increase the knowledge of the Nemo topology on 187 each node. 189 3.2 Loops in nested Nemo 191 When several MRs attach to each other to form a nested Nemo, loops 192 can be created if they are not explicitely avoided. In the simplest 193 case, when egress and ingress interfaces of an MR are all wireless, a 194 mobile router may be listening to Router Advertisement from its own 195 ingress interface, creating a confliction problem. In the general 196 case, arbitrary attachment of MRs will form graphs that are not 197 exempt of loops. For instance: Assume a nested Nemo where MR1 is 198 connected to the infrastructure, and MR3 is attached to MR2. Say that 199 MR2 can hear both MR3 and MR1 over its wireless egress interface. If 200 MR2 select MR1, the connectivity to the infrastruture is provided for 201 all. But if MR2 selects MR3, MR2 and MR3 end up forming a loop and 202 are disconnected from their Home Agents. 204 With Nemo basic support, a MR uses a single primary CareOf to attach 205 to the nested structure. As a result, if loops are avoided, the 206 nested NEMO end up forming a tree. It is beneficial to be able to 207 form that tree in an optimum fashion for a given set of metrics such 208 as tree depth. 210 The shape of a nested Nemo may change rapidly due to MRs movement. It 211 is thus impractical to expect each MR to be able to maintain states 212 about the whole tree structure in a link state fashion. On the 213 contrary, it is also beneficial to allow each MR to make its own 214 independent selection based on a minimum information about its 215 immediate neighbors, in order to reestablish the tree quickly upon 216 erratic movements. 218 Each MR should be able to make its own attachment router selection 219 based on its own condition (eg battery level), its own set of 220 constraints that may not apply to other MRs in the tree, and in 221 general its own algorithm. As a result, the standardization effort 222 should concentrate on a common minimum set of rules that must be 223 common to all MRs in order to prevent routing loops in the nested 224 NEMO while leaving MRs independent in their AR selection algorithms. 226 4. Router Advertisement extensions 228 New extensions of Router Advertisement are proposed to distribute the 229 knowledge of the MR hierarchy inside a nested Nemo. These extensions 230 are defined in different options/sub-options: a flag bit from the 231 reserved flag field of Router Advertisement message is used to 232 indicate whether the sending router is a MR or not; a new option is 233 defined to transport minimum information on the tree to avoid loops 234 generation; 236 4.1 Router Advertisement message 238 We propose to use a reserved flag of the Router Advertisement message 239 to inform whether the sending router is a MR or not. 241 0 1 2 3 242 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 243 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 244 | Type | Code | Checksum | 245 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 246 | Cur Hop Limit |M|O|H|N|Reservd| Router Lifetime | 247 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 248 | Reachable Time | 249 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 250 | Retrans Timer | 251 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 252 | Options ... 253 +-+-+-+-+-+-+-+-+-+-+-+- 255 Nemo enabled router (N) 257 The Nemo enabled router (N) bit is set when the sending router is a 258 Mobile Router. 260 4.2 Tree Information Option 262 The following option regroups the minimum information that allows a 263 MR to discover a tree and select its point of attachment while 264 avoiding loop generation. It can also be used by MNNs to select their 265 best default router. If the default router of a non-MR sends Router 266 Advertisements with a tree discovery option, the non-MR MUST set the 267 N flag of its own Router Advertisement to 0 and copy the Tree 268 Discovery Option in its own Router Advertisement. 270 0 1 2 3 271 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 272 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 273 | Type | Length |G|H| Reserved | 274 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 275 | Preference | BootTimeRandom | 276 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 277 | TreeDepth | TreePref. | TreeDelay | 278 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 279 | PathDigest | 280 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 281 | | 282 + + 283 | TreeID | 284 + + 285 | | 286 + + 287 | | 288 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 289 | sub-option(s)... 290 +-+-+-+-+-+-+-+-+-+-+-+-+-+ 292 Figure 2. Tree Information Option 294 Type 8-bit unsigned integer set to 10 by the Clusterhead. 296 Length 8-bit unsigned integer set to 4. The length of the option 297 (including the type and length fields) in units of 8 octets. 299 Grounded (G) The Grounded (G) flag is set when the Clusterhead is 300 attached to a fixed network infrastructure (such as the Internet). 302 Home (H) The Home (H) flag is set when the Clusterhead is attached to 303 its home network. 305 Reserved 16-bit unsigned integer set to 0 by the Clusterhead. 307 Preference The administrative preference of that (mobile) Access 308 Router. Default is 0. 255 is the highest possible preference. Set 309 by each MR at propagation time. 311 BootTimeRandom A random value computed at boot time and recomputed in 312 case of a duplication with another AR. The concatenation of the 313 Preference and the BootTimeRandom is a 32-bit extended preference 314 that is used to resolve collisions. It is set by each MR at 315 propagation time. 317 TreeDepth 8-bit unsigned integer. The tree depth of the clusterhead 318 is 0 if it is a fixed router and 1 if it is a Mobile Router. The 319 tree Depth of a tree Node is the depth of its attachment router as 320 received in a TIO, incremented by one. All nodes in the tree 321 advertise their tree depth in the Tree Information Options that 322 they append to the RA messages over their ingress interfaces as 323 part of the propagation process. 325 TreePreference 8-bit unsigned integer set by the Clusterhead to its 326 preference and unchanged at propagation. Default is 0 (lowest 327 preference). 329 TreeDelay 16-bit unsigned integer set by the Clusterhead indicating 330 the delay before changing the tree configuration, in milliseconds. 331 A default value is 128ms. It is expected to be an order of 332 magnitude smaller than the RA-interval so if the clusterhead has a 333 sub-second RA-interval, the Tree delay may be shorter than 100ms. 334 It is also expected to be an order of magnitude longer than the 335 typical propagation delay inside the nested Nemo. 337 PathDigest 32-bit unsigned integer CRC, updated by each MR. This is 338 the result of a CRC-32c computation on a bit string obtained by 339 appending the received value and the MR Care of Address. 340 Clusterheads use a 'previous value' of zeroes to initially set the 341 PathDigest. 343 TreeID 128-bit unsigned integer which uniquely identify a tree set by 344 the Clusterhead. The global IPv6 home address of the Clusterhead 345 can be used. 347 5. Tree Discovery 349 Here follows a set of rules and definitions that MUST be followed be 350 all Mobile Routers: 352 1. An MR that is not attached to an AR is the Nemo Clusterhead of 353 its own, floating tree. 355 2. An MR that is attached to an AR that does not support TIO, is the 356 clusterhead of its own, grounded tree. 358 3. A router sending a RA without TIO is considered a grounded AR at 359 depth 0. Thus, a MR that attaches to an AR that does not include 360 a TIO in its RA becomes a Clusterhead of depth 1. 362 4. The Nemo ClusterHead of a tree exposes the tree in the RA/TIO and 363 MRs propagate the TIO down the tree with the RAs that they 364 forward over their ingress links. 366 5. An MR that is already part of a tree MAY move at any time and 367 with no delay in order to get closer to the clusterhead of its 368 current tree - i.e. in order to reduce its own tree depth. But an 369 MR MUST NOT move down the tree that it is attached to. MRs MUST 370 ignore RAs that are received from other routers located deeper or 371 at the same depth within the same tree. 373 6. An MR may move from its current tree into any different tree at 374 any time and whatever the depth its reaches in the new tree, but 375 it may have to wait for a Tree Hop timer to elapse in order to do 376 so. The MR will join that other tree if it is more preferable for 377 reasons of connectivity, configured preference, size, security, 378 bandwidth, tree depth, or whatever metrics the MR cares to use. 380 7. If a MR has selected a new attachment router but has not moved 381 yet (because it is waiting for Tree Hop timer to elapse), the MR 382 is unstable and refrains from sending RATIOs. 384 8. When an MR joins a tree, moves within its tree, or when it 385 receives a modified TIO from its current access router, the MR 386 sends an unsolicited Router Advertisement message on all its 387 mobile networks (i.e. all its ingress interfaces). The RA 388 contains a TIO that propagates the new tree information. At the 389 same time, the MR MAY send a Binding Update to its home agent or 390 a local proxy of some sort, because the tree it is attached to 391 has changed. If the MR fails to reach its HA, it MAY attempt to 392 roll back the movement or to retry the HA discovery procedure. 394 9. This allows the new higher parts of the tree to take place first 395 eventually dragging their sub-tree with them, and allowing 396 stepped sub-tree reconfigurations, limiting relative movements. 398 5.1 tree selection 400 The tree selection is implementation and algorithm dependent. In 401 order to limit erratic movements, and all metrics being equal, MRs 402 SHOULD stick to their previous selection. Also, MRs SHOULD provide a 403 mean to filter out candidate ARs whose availability is detected as 404 fluctuating, at least when more stable choices are available. For 405 instance, the MR MAY place the failed AR in a Hold Down mode that 406 ensures that the AR will not be reused for a given period of time. 408 The known trees are associated with the AR that advertises them and 409 kept in an ordered list, per order of preference, by extending the 410 Default Router List. DRL entries are extended to store the 411 information received from the last TIO, and a timer ID -and related 412 data- to delay the reaction to a better RA message, the tree hop 413 timer, as described in the next section. 415 When connection to a fixed network is not possible or preferable for 416 security or other reasons, scattered trees should aggregate as much 417 as possible into larger trees in order to allow inner connectivity. 418 How to balance these trees is implementation dependent, and MAY use a 419 specific visitor-counter suboption in the TIO. 421 5.2 Tree Hop Timer 423 The tree Hop timer serves 2 purposes: 425 Delay the reattachment of a subtree that has been forced to 426 detach. This allows to make sure that when a subtree has detached, 427 the RATIO that is initiated by the new clusterhead has spread down 428 the subtree so that two different trees have formed. 430 Limit RA/TIO storms when two trees collide. The idea is that 431 between the nodes from tree A that wish to move to tree B, those 432 that see the highest place in tree B will move first and advertise 433 their new locations before other nodes from tree A actually move. 435 A new tree is discovered upon a router advertisement message with or 436 without a RA/TIO. The MR joins the tree by selecting the source of 437 the RA message as its access router (default gateway) and propagating 438 the TIO accordingly. 440 When a new tree is discovered, the candidate AR that advertises the 441 new tree is placed in a held up state for the duration of a Tree Hop 442 timer. If the new AR is more preferable than the current one, the MR 443 expects to jump and becomes unstable. 445 A MR that is unstable may discover other ARs from the same new tree 446 during the instability phase. It needs to start a new Tree Hop timer 447 for all these. The first timer that elapses for a given new tree 448 clears them all for that tree, allowing the MR to jump to the highest 449 position available in the new tree. 451 The duration of the Tree Hop timer depends on the tree delay of the 452 new tree and on the depth of AR that triggers it: 454 (AR's depth + random) * AR's tree_delay (where 0 <= random < 1). It 455 is randomized in order to limit collisions and synchronizations. 457 5.3 Collisions and stability 459 Attachment routers in the DRL may or may not be usable for roaming 460 depending on runtime conditions. The following states are defined: 462 Current This AR is used for roaming 464 Candidate This AR can be used for roaming. Typically, an initial 465 held-up period is over but the candidate is not preferred over the 466 current AR. 468 Held-Up This AR can not be used till tree hop timer elapses. This 469 does not occur for a fixed AR that does not send a TIO since the 470 tree delay is null in that case.. 472 Held-Down This AR can not be used till hold down timer elapses. At 473 the end of the hold-down period, the router is removed from the 474 DRL, and will be reinserted if it appears again with a RA. 476 Collision This AR can not be used till its next Router Advertisement 478 5.3.1 Hold down 480 When a router is 'removed' from the Default Router List, it is 481 actually held down for a hold down timer period, in order to prevent 482 flapping. This happens when an AR disappears (upon expiration timer), 483 and when an AR is tried but can not reach the HA (upon expiration of 484 another AR, or upon tree hop for that AR). 486 An Attachment Router that is held down is not considered for the 487 purpose of roaming. When the hold down timer elapses, the AR is 488 removed from the DRL. 490 5.3.2 Instability 492 A MR is instable when a Held-Up AR is placed before the current AR. 493 Instability is transient (In the order of tree hop timers). When a MR 494 is instable, it MUST NOT send RAs with TIO. This avoids loops when MR 495 A wishes to attach to MR B and MR B wishes to attach to MR A. Unless 496 RA cross (which is a short window of time), a MR receives TIO from 497 stable ARs, which do not plan to attach to itself, so the MR can 498 safely attach to them. 500 A MR is instable when it is prepared to move shortly to another AR. 502 This happens typically when it discovers a new and more preferred 503 candidate AR, for the duration of the tree hop timer. During that 504 time, the new candidate is placed in Held-up state. Instability may 505 also occur when the current AR is lost and the next best is still 506 held up. Instability is resolved when the tree hop timer of all the 507 AR (s) causing instability elapse. Such AR is changes state to 508 Current or Held-Down. 510 5.3.3 Collision 512 A race condition occurs if 2 MRs send RA/TIO at the same time and 513 wish to join each other. In order to detect the situation, MRs time 514 stamp the sending of RA/TIO. Any RA/TIO received within a short 515 media-dependant period introduces a risk. To divide the risk, A 516 32bits extended preference is added in the TIO. The first byte is the 517 AR own preference (default 0), the rest is a boot time computed 518 random. 520 A MR that decides to join an AR will do so between (AR depth) and (AR 521 depth + 1) times the AR tree delay. But since a MR is unstable as 522 soon as it receives the RA/TIO from the preferred AR, it will 523 restrain from sending a RA/TIO between the time it receives the RA 524 and the time it actually jumps. So the crossing of RA may only happen 525 during the propagation time between the AR and the MR, plus some 526 internal queuing and processing time within each machine. It is 527 expected that one tree delay normally covers that interval, but 528 ultimately it is up to the implementation and the configuration of 529 the AR to define the duration of risk window. 531 There is risk of a collision when a MR receives an RA, for an other 532 mobile router that is more preferable than the current AR, within the 533 risk window. In the face of a potential collision, the Mobile Router 534 with the lowest extended preference processes the RA/TIO normally, 535 while the router with the highest preference places the other in 536 collision state, does not start the tree hop timer, and does not 537 become instable. It is expected that next RAs between the two will 538 not cross anyway. 540 6. Acknowledgments 542 The authors wish to thank Marco Molteni and Patrick Wetterwald 543 (cisco) for their participation to this design and the review of the 544 document, and Massimo Villari (university of Messina), for his early 545 work on simulation and research on the subject. This work is also 546 based on prior publications, in particular HMRA [7] by Hosik Cho and 547 Eun-Kyoung Paik from Seoul National University and other non IETF 548 publications coauthored with Thierry Ernst and Thomas Noel. 550 References 552 [1] Narten, T., Nordmark, E. and W. Simpson, "Neighbor Discovery for 553 IP Version 6 (IPv6)", RFC 2461, December 1998. 555 [2] Thomson, S. and T. Narten, "IPv6 Stateless Address 556 Autoconfiguration", RFC 2462, December 1998. 558 [3] Johnson, D., Perkins, C. and J. Arkko, "Mobility Support in 559 IPv6", draft-ietf-mobileip-ipv6-24 (work in progress), July 560 2003. 562 [4] Devarapalli, V., "Nemo Basic Support Protocol", 563 draft-ietf-nemo-basic-support-02 (work in progress), December 564 2003. 566 [5] Ernst, T., "Network Mobility Support Goals and Requirements", 567 draft-ietf-nemo-requirements-02 (work in progress), February 568 2004. 570 [6] Ernst, T. and H. Lach, "Network Mobility Support Terminology", 571 draft-ietf-nemo-terminology-01 (work in progress), February 572 2004. 574 [7] Cho, H., "Hierarchical Mobile Router Advertisement for nested 575 mobile networks", draft-cho-nemo-hmra-00 (work in progress), 576 January 2004. 578 [8] Ng, C-W., Charbon, J., Paik, E-Y. and T. Ernst, "Analysis of 579 Multihoming in Network Mobility Support", 580 draft-ng-nemo-multihoming-issues-03 (work in progress), February 581 2004. 583 [9] Draves, R. and R. Hinden, "Default Router Preferences and 584 More-Specific Routes", draft-ietf-ipv6-router-selection-03 (work 585 in progress), December 2003. 587 Authors' Addresses 589 Pascal Thubert 590 Cisco Systems 591 Village d'Entreprises Green Side 592 400, Avenue de Roumanille 593 Batiment T3 594 Biot - Sophia Antipolis 06410 595 FRANCE 597 Phone: (33) 4 97 23 26 34 598 EMail: pthubert@cisco.com 600 Nicolas Montavont 601 LSIIT - Univerity Louis Pasteur 602 Pole API, bureau C444 603 Boulevard Sebastien Brant 604 Illkirch 67400 605 FRANCE 607 Phone: (33) 3 90 24 45 87 608 EMail: montavont@dpt-info.u-strasbg.fr 609 URI: http://www-r2.u-strasbg.fr/~montavont/ 611 Intellectual Property Statement 613 The IETF takes no position regarding the validity or scope of any 614 intellectual property or other rights that might be claimed to 615 pertain to the implementation or use of the technology described in 616 this document or the extent to which any license under such rights 617 might or might not be available; neither does it represent that it 618 has made any effort to identify any such rights. Information on the 619 IETF's procedures with respect to rights in standards-track and 620 standards-related documentation can be found in BCP-11. Copies of 621 claims of rights made available for publication and any assurances of 622 licenses to be made available, or the result of an attempt made to 623 obtain a general license or permission for the use of such 624 proprietary rights by implementors or users of this specification can 625 be obtained from the IETF Secretariat. 627 The IETF invites any interested party to bring to its attention any 628 copyrights, patents or patent applications, or other proprietary 629 rights which may cover technology that may be required to practice 630 this standard. Please address the information to the IETF Executive 631 Director. 633 Full Copyright Statement 635 Copyright (C) The Internet Society (2004). All Rights Reserved. 637 This document and translations of it may be copied and furnished to 638 others, and derivative works that comment on or otherwise explain it 639 or assist in its implementation may be prepared, copied, published 640 and distributed, in whole or in part, without restriction of any 641 kind, provided that the above copyright notice and this paragraph are 642 included on all such copies and derivative works. However, this 643 document itself may not be modified in any way, such as by removing 644 the copyright notice or references to the Internet Society or other 645 Internet organizations, except as needed for the purpose of 646 developing Internet standards in which case the procedures for 647 copyrights defined in the Internet Standards process must be 648 followed, or as required to translate it into languages other than 649 English. 651 The limited permissions granted above are perpetual and will not be 652 revoked by the Internet Society or its successors or assignees. 654 This document and the information contained herein is provided on an 655 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 656 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 657 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 658 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 659 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 661 Acknowledgment 663 Funding for the RFC Editor function is currently provided by the 664 Internet Society.