idnits 2.17.00 (12 Aug 2021) /tmp/idnits32752/draft-thubert-tree-discovery-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 16. -- Found old boilerplate from RFC 3978, Section 5.5 on line 689. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 666. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 673. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 679. ** Found boilerplate matching RFC 3978, Section 5.4, paragraph 1 (on line 695), which is fine, but *also* found old RFC 2026, Section 10.4C, paragraph 1 text on line 38. ** 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 : ---------------------------------------------------------------------------- ** 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 274: '...tree discovery option, the non-MR MUST...' RFC 2119 keyword, line 357: '...d definitions that MUST be followed be...' RFC 2119 keyword, line 374: '...y part of a tree MAY move at any time ...' RFC 2119 keyword, line 377: '... an MR MUST NOT move down the tr...' RFC 2119 keyword, line 378: '... MUST ignore RAs that are receiv...' (6 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 (October 11, 2004) is 6431 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 599, but no explicit reference was found in the text == Unused Reference: '2' is defined on line 602, but no explicit reference was found in the text == Unused Reference: '4' is defined on line 609, but no explicit reference was found in the text == Unused Reference: '5' is defined on line 613, 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' == Outdated reference: draft-ietf-nemo-multihoming-issues has been published as RFC 4980 ** Downref: Normative reference to an Informational draft: draft-ietf-nemo-multihoming-issues (ref. '8') == Outdated reference: draft-ietf-ipv6-router-selection has been published as RFC 4191 Summary: 16 errors (**), 0 flaws (~~), 12 warnings (==), 8 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: April 11, 2005 N. Montavont 5 LSIIT - ULP 6 October 11, 2004 8 Nested Nemo Tree Discovery 9 draft-thubert-tree-discovery-01.txt 11 Status of this Memo 13 By submitting this Internet-Draft, I certify that any applicable 14 patent or other IPR claims of which I am aware have been disclosed, 15 and any of which I become aware will be disclosed, in accordance with 16 RFC 3668. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as 21 Internet-Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at 29 http://www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This Internet-Draft will expire on April 11, 2005. 36 Copyright Notice 38 Copyright (C) The Internet Society (2004). All Rights Reserved. 40 Abstract 42 The purpose of this paper is to describe a minimum set of features 43 that extends the Nemo basic support in order to avoid loops in the 44 nested Nemo case. As a result, Mobile Routers assemble into a tree 45 that can be optimized based on various metrics. 47 Table of Contents 49 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 51 2. Terms and Abbreviations . . . . . . . . . . . . . . . . . . . 3 53 3. Motivations . . . . . . . . . . . . . . . . . . . . . . . . . 4 54 3.1 Multihomed nested mobile network . . . . . . . . . . . . . 4 55 3.2 Loops in nested Nemo . . . . . . . . . . . . . . . . . . . 5 57 4. Router Advertisement extensions . . . . . . . . . . . . . . . 6 58 4.1 Router Advertisement message . . . . . . . . . . . . . . . 6 59 4.2 Tree Information Option . . . . . . . . . . . . . . . . . 6 61 5. Tree Discovery . . . . . . . . . . . . . . . . . . . . . . . . 8 62 5.1 tree selection . . . . . . . . . . . . . . . . . . . . . . 9 63 5.2 Subtree mobility . . . . . . . . . . . . . . . . . . . . . 10 64 5.3 Tree Hop Timer . . . . . . . . . . . . . . . . . . . . . . 10 65 5.4 Collisions and stability . . . . . . . . . . . . . . . . . 11 66 5.4.1 Hold down . . . . . . . . . . . . . . . . . . . . . . 12 67 5.4.2 Instability . . . . . . . . . . . . . . . . . . . . . 12 68 5.4.3 Collision . . . . . . . . . . . . . . . . . . . . . . 12 69 5.5 Legacy Routers . . . . . . . . . . . . . . . . . . . . . . 13 71 6. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 72 6.1 Changes from version 00 to 01 . . . . . . . . . . . . . . 14 74 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 14 76 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 15 78 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 15 80 Intellectual Property and Copyright Statements . . . . . . . . 17 82 1. Introduction 84 As per Nemo Basic support, a Mobile Router autoconfigures a single 85 Care of Address to register to its Home Agent and terminate its MR-HA 86 tunnel. That CoA is the MR's point of attachment to the nested Nemo. 88 Consequently, if loops are avoided, the nested Nemo assumes the shape 89 of a tree. The nodes of the tree are Mobile Routers, the root is 90 either a fixed or a Mobile Router, called in the latter case the root 91 Mobile Router in NEMO terminology [6]. The leaves are mobile or 92 fixed hosts, called Local Fixed Nodes, Local Mobile Nodes and 93 Visiting Mobile Nodes in the NEMO terminology. 95 This paper provides (1) a minimum extension to IPv6 Neighbour 96 Discovery Router Advertisements in order to ensure that Mobile 97 Routers attaching to one another actually avoid loops and end up 98 forming a tree, and (2) the minimum common part of all MR algorithms 99 that is required to ensure that whatever their specific decisions, 100 loops between MRs will be avoided. 102 The method is based on an autonomous decision by each MR with no 103 global state convergence such as a MANET proactive routing protocol. 104 In fact, MRs may make different decisions from a same input, based on 105 their own configuration and their own algorithms. 107 In order to build trees of Mobile Routers, we propose an extension to 108 the ICMP Router Advertisement (RA) message, the Tree Information 109 Option (TIO). The RA/TIO allows MRs to advertise the tree they 110 belong to, and to select and move to the best location within the 111 available trees. MRs propagate the TIO down the tree, updating some 112 metrics such as the tree depth, leaving alone root information such 113 as the tree identifier, and sending the result in RAs over the 114 ingress interfaces. 116 2. Terms and Abbreviations 118 This document assumes that the reader is familiar with Mobile IPv6 as 119 defined in [3] and with the concept of Mobile Router defined in the 120 Nemo terminology document [6]. 122 For the needs of this paper, the following new definitions are 123 introduced: 125 Nemo Clusterhead: The root of a tree of mobile routers. When the 126 tree of Mobile Routers is attached to the infrastructure, the 127 fixed Access Router may act as cluster head if it supports the 128 Tree Information Option described in this document. If it does 129 not, then the Clusterhead coincides with the root MR in NEMO 130 terminology. A clusterhead is elected even when the tree is not 131 attached to the infrastructuture. A stand-alone MR is a 132 Clusterhead. 134 Floating Tree: A Nested Nemo which Clusterhead is a MR that is not 135 attached to an AR. 137 Grounded Tree: A Nested Nemo whose Clusterhead is attached to the 138 infrastructure. In other words, the clusterhead is either a fixed 139 router that supports RA/TIO or is a MR which attachment router is 140 a fixed router that does not support RA/TIO. 142 Mobile Access Router: A Mobile Router that provides Access Router 143 services to other MRs. 145 Attachment Router: The Router that is selected as Access Router by a 146 Mobile Router, making it its parent in the nested NEMO tree. 148 Propagation: The action by a Mobile Router that consists in receiving 149 a RA/TIO from its Attachment Router, recomputing a few specific 150 fields, removing unknown suboption, and appending the resulting 151 TIO to RAs sent over the ingress interfaces. 153 3. Motivations 155 3.1 Multihomed nested mobile network 157 A nested mobile network that is made of multiple MRs having a direct 158 connection to the Internet is said to be multihomed. Multihoming in 159 Nemo offers useful properties to MNNs. The NEMO multihoming issues 160 [8] draft lists potential multihomed configurations for Nemo and 161 explains the different problems and advantages that some 162 configurations may introduce. Multihoming offers three main 163 abilities to the Nemo: it allows route recovery on failure, 164 redundancy and load-sharing between MRs (or between MRs'interfaces). 165 However, for the moment there are no requirements nor protocol 166 defining how to use several egress interfaces inside a Nemo. 168 In a nested Nemo, the hierarchy of MRs increases the complexity of 169 the route and/or router selection for MNNs. Each level of a Nemo 170 implies the usage of a new tunnel between the MR and its home agent. 171 Thus if a MNN connects to a sub-Nemo which is also a sub-Nemo, 172 packets from the MNN will be encapsulated three times. 174 When the Nemo where the MN is connected to is multihomed, the MN may 175 have the choice between several AR to be its default router. 176 Reference [9] introduces new options in Router Advertisement to allow 177 any node on a link to choose between several routers. This option 178 mainly consists of a 2-bits flag that indicates the preference of the 179 router (low, medium or high). Furthermore, the same flag can be set 180 in the Route Information option indicating the preference of a 181 specific prefix. Therefore, any node can determine its best default 182 router(s) according to a given destination and its best router for 183 default, which will be used by default. 185 However this preference is only useful in a flat topology; It gives a 186 way to the node to choose between different access routers 187 advertising prefixes on the node link. But if the node is inside a 188 hierarchical topology (some access routers are not at the same level) 189 the node can not learn the level of each access router. 191 One of the usage of the new option introduced in this document is to 192 distribute information on the hierarchy of MRs. This information can 193 be distributed to ARs, MRs and MNNs as well in order to allow better 194 route selection and to increase the knowledge of the Nemo topology on 195 each node. 197 3.2 Loops in nested Nemo 199 When several MRs attach to each other to form a nested Nemo, loops 200 can be created if they are not explicitely avoided. In the simplest 201 case, when egress and ingress interfaces of an MR are all wireless, a 202 mobile router may be listening to Router Advertisement from its own 203 ingress interface, creating a confliction problem. In the general 204 case, arbitrary attachment of MRs will form graphs that are not 205 exempt of loops. For instance: Assume a nested Nemo where MR1 is 206 connected to the infrastructure, and MR3 is attached to MR2. Say 207 that MR2 can hear both MR3 and MR1 over its wireless egress 208 interface. If MR2 select MR1, the connectivity to the infrastruture 209 is provided for all. But if MR2 selects MR3, MR2 and MR3 end up 210 forming a loop and are disconnected from their Home Agents. 212 With Nemo basic support, a MR uses a single primary CareOf to attach 213 to the nested structure. As a result, if loops are avoided, the 214 nested NEMO end up forming a tree. It is beneficial to be able to 215 form that tree in an optimum fashion for a given set of metrics such 216 as tree depth. 218 The shape of a nested Nemo may change rapidly due to MRs movement. 219 It is thus impractical to expect each MR to be able to maintain 220 states about the whole tree structure in a link state fashion. On 221 the contrary, it is also beneficial to allow each MR to make its own 222 independent selection based on a minimum information about its 223 immediate neighbors, in order to reestablish the tree quickly upon 224 erratic movements. 226 Each MR should be able to make its own attachment router selection 227 based on its own condition (eg battery level), its own set of 228 constraints that may not apply to other MRs in the tree, and in 229 general its own algorithm. As a result, the standardization effort 230 should concentrate on a common minimum set of rules that must be 231 common to all MRs in order to prevent routing loops in the nested 232 NEMO while leaving MRs independent in their AR selection algorithms. 234 4. Router Advertisement extensions 236 New extensions of Router Advertisement are proposed to distribute the 237 knowledge of the MR hierarchy inside a nested Nemo. These extensions 238 are defined in different options/sub-options: a flag bit from the 239 reserved flag field of Router Advertisement message is used to 240 indicate whether the sending router is a MR or not; a new option is 241 defined to transport minimum information on the tree to avoid loops 242 generation; 244 4.1 Router Advertisement message 246 We propose to use a reserved flag of the Router Advertisement message 247 to inform whether the sending router is a MR or not. 249 0 1 2 3 250 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 251 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 252 | Type | Code | Checksum | 253 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 254 | Cur Hop Limit |M|O|H|N|Reservd| Router Lifetime | 255 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 256 | Reachable Time | 257 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 258 | Retrans Timer | 259 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 260 | Options ... 261 +-+-+-+-+-+-+-+-+-+-+-+- 263 Nemo enabled router (N) 265 The Nemo enabled router (N) bit is set when the sending router is a 266 Mobile Router. 268 4.2 Tree Information Option 270 The following option regroups the minimum information that allows a 271 MR to discover a tree and select its point of attachment while 272 avoiding loop generation. It can also be used by MNNs to select 273 their best default router. If the default router of a non-MR sends 274 Router Advertisements with a tree discovery option, the non-MR MUST 275 set the N flag of its own Router Advertisement to 0 and copy the Tree 276 Discovery Option in its own Router Advertisement. 278 0 1 2 3 279 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 280 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 281 | Type | Length |G|H| Reserved | 282 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 283 | Preference | BootTimeRandom | 284 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 285 | TreeDepth | TreePref. | TreeDelay | 286 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 287 | PathDigest | 288 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 289 | | 290 + + 291 | TreeID | 292 + + 293 | | 294 + + 295 | | 296 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 297 | sub-option(s)... 298 +-+-+-+-+-+-+-+-+-+-+-+-+-+ 300 Figure 2. Tree Information Option 302 Type 8-bit unsigned integer set to 10 by the Clusterhead. 304 Length 8-bit unsigned integer set to 4. The length of the option 305 (including the type and length fields) in units of 8 octets. 307 Grounded (G) The Grounded (G) flag is set when the Clusterhead is 308 attached to a fixed network infrastructure (such as the Internet). 310 Home (H) The Home (H) flag is set when the Clusterhead is attached to 311 its home network. 313 Reserved 16-bit unsigned integer set to 0 by the Clusterhead. 315 Preference The administrative preference of that (mobile) Access 316 Router. Default is 0. 255 is the highest possible preference. 317 Set by each MR at propagation time. 319 BootTimeRandom A random value computed at boot time and recomputed in 320 case of a duplication with another AR. The concatenation of the 321 Preference and the BootTimeRandom is a 32-bit extended preference 322 that is used to resolve collisions. It is set by each MR at 323 propagation time. 325 TreeDepth 8-bit unsigned integer. The tree depth of the clusterhead 326 is 0 if it is a fixed router and 1 if it is a Mobile Router. The 327 tree Depth of a tree Node is the depth of its attachment router as 328 received in a TIO, incremented by one. All nodes in the tree 329 advertise their tree depth in the Tree Information Options that 330 they append to the RA messages over their ingress interfaces as 331 part of the propagation process. 333 TreePreference 8-bit unsigned integer set by the Clusterhead to its 334 preference and unchanged at propagation. Default is 0 (lowest 335 preference). 337 TreeDelay 16-bit unsigned integer set by the Clusterhead indicating 338 the delay before changing the tree configuration, in milliseconds. 339 A default value is 128ms. It is expected to be an order of 340 magnitude smaller than the RA-interval so if the clusterhead has a 341 sub-second RA-interval, the Tree delay may be shorter than 100ms. 342 It is also expected to be an order of magnitude longer than the 343 typical propagation delay inside the nested Nemo. 345 PathDigest 32-bit unsigned integer CRC, updated by each MR. This is 346 the result of a CRC-32c computation on a bit string obtained by 347 appending the received value and the MR Care of Address. 348 Clusterheads use a 'previous value' of zeroes to initially set the 349 PathDigest. 351 TreeID 128-bit unsigned integer which uniquely identify a tree set by 352 the Clusterhead. The global IPv6 home address of the Clusterhead 353 can be used. 355 5. Tree Discovery 357 Here follows a set of rules and definitions that MUST be followed be 358 all Mobile Routers: 360 1. An MR that is not attached to an AR is the Nemo Clusterhead of 361 its own, floating tree. 363 2. An MR that is attached to an AR that does not support TIO, is the 364 clusterhead of its own, grounded tree. 366 3. A router sending a RA without TIO is considered a grounded AR at 367 depth 0. Thus, a MR that attaches to an AR that does not include 368 a TIO in its RA becomes a Clusterhead of depth 1. 370 4. The Nemo ClusterHead of a tree exposes the tree in the RA/TIO and 371 MRs propagate the TIO down the tree with the RAs that they 372 forward over their ingress links. 374 5. An MR that is already part of a tree MAY move at any time and 375 with no delay in order to get closer to the clusterhead of its 376 current tree - i.e. in order to reduce its own tree depth. But 377 an MR MUST NOT move down the tree that it is attached to. MRs 378 MUST ignore RAs that are received from other routers located 379 deeper or at the same depth within the same tree. 381 6. An MR may move from its current tree into any different tree at 382 any time and whatever the depth its reaches in the new tree, but 383 it may have to wait for a Tree Hop timer to elapse in order to do 384 so. The MR will join that other tree if it is more preferable 385 for reasons of connectivity, configured preference, size, 386 security, bandwidth, tree depth, or whatever metrics the MR cares 387 to use. 389 7. If a MR has selected a new attachment router but has not moved 390 yet (because it is waiting for Tree Hop timer to elapse), the MR 391 is unstable and refrains from sending RATIOs. 393 8. When an MR joins a tree, moves within its tree, or when it 394 receives a modified TIO from its current access router, the MR 395 sends an unsolicited Router Advertisement message on all its 396 mobile networks (i.e. all its ingress interfaces). The RA 397 contains a TIO that propagates the new tree information. At the 398 same time, the MR MAY send a Binding Update to its home agent or 399 a local proxy of some sort, because the tree it is attached to 400 has changed. If the MR fails to reach its HA, it MAY attempt to 401 roll back the movement or to retry the HA discovery procedure. 403 9. This allows the new higher parts of the tree to take place first 404 eventually dragging their sub-tree with them, and allowing 405 stepped sub-tree reconfigurations, limiting relative movements. 407 5.1 tree selection 409 The tree selection is implementation and algorithm dependent. In 410 order to limit erratic movements, and all metrics being equal, MRs 411 SHOULD stick to their previous selection. Also, MRs SHOULD provide a 412 mean to filter out candidate ARs whose availability is detected as 413 fluctuating, at least when more stable choices are available. For 414 instance, the MR MAY place the failed AR in a Hold Down mode that 415 ensures that the AR will not be reused for a given period of time. 417 The known trees are associated with the AR that advertises them and 418 kept in an ordered list, per order of preference, by extending the 419 Default Router List. DRL entries are extended to store the 420 information received from the last TIO, and a timer ID -and related 421 data- to delay the reaction to a better RA message, the tree hop 422 timer, as described in the next section. 424 When connection to a fixed network is not possible or preferable for 425 security or other reasons, scattered trees should aggregate as much 426 as possible into larger trees in order to allow inner connectivity. 427 How to balance these trees is implementation dependent, and MAY use a 428 specific visitor-counter suboption in the TIO. 430 5.2 Subtree mobility 432 It might be perceived as beneficial for a subtree to move as a whole. 433 The way it would work is for a MR to stay root-MR even if itself is 434 attached into a parent tree. But the loop avoidance is based on the 435 knowledge of the tree that the MR visit, preventing a MR to move down 436 a same tree. So without additional support, tree-level loops could 437 form. 439 To avoid this, it is possible to add a path vector suboption to the 440 TIO that reflects the nesting of trees. If a root-MR joins a parent 441 tree, then it needs to add its treeID to the path vector, but it can 442 not join if the treeID is already listed. 444 A specific case is the root-MR of a tree that attaches to a fixed 445 Access Router. That root-MR might omit to consider a TIO that comes 446 from the new AR and decide to stay root, in order to keep the tree 447 consistency from the nested MRs standpoint. This does not create 448 loops, even if the path vector is not present 450 5.3 Tree Hop Timer 452 The tree Hop timer serves 2 purposes: 454 Delay the reattachment of a subtree that has been forced to 455 detach. This allows to make sure that when a subtree has 456 detached, the RATIO that is initiated by the new clusterhead has 457 spread down the subtree so that two different trees have formed. 459 Limit RA/TIO storms when two trees collide. The idea is that 460 between the nodes from tree A that wish to move to tree B, those 461 that see the highest place in tree B will move first and advertise 462 their new locations before other nodes from tree A actually move. 464 A new tree is discovered upon a router advertisement message with or 465 without a RA/TIO. The MR joins the tree by selecting the source of 466 the RA message as its access router (default gateway) and propagating 467 the TIO accordingly. 469 When a new tree is discovered, the candidate AR that advertises the 470 new tree is placed in a held up state for the duration of a Tree Hop 471 timer. If the new AR is more preferable than the current one, the MR 472 expects to jump and becomes unstable. 474 A MR that is unstable may discover other ARs from the same new tree 475 during the instability phase. It needs to start a new Tree Hop timer 476 for all these. The first timer that elapses for a given new tree 477 clears them all for that tree, allowing the MR to jump to the highest 478 position available in the new tree. 480 The duration of the Tree Hop timer depends on the tree delay of the 481 new tree and on the depth of AR that triggers it: 483 (AR's depth + random) * AR's tree_delay (where 0 <= random < 1). It 484 is randomized in order to limit collisions and synchronizations. 486 5.4 Collisions and stability 488 Attachment routers in the DRL may or may not be usable for roaming 489 depending on runtime conditions. The following states are defined: 491 Current This AR is used for roaming 493 Candidate This AR can be used for roaming. Typically, an initial 494 held-up period is over but the candidate is not preferred over the 495 current AR. 497 Held-Up This AR can not be used till tree hop timer elapses. This 498 does not occur for a fixed AR that does not send a TIO since the 499 tree delay is null in that case.. 501 Held-Down This AR can not be used till hold down timer elapses. At 502 the end of the hold-down period, the router is removed from the 503 DRL, and will be reinserted if it appears again with a RA. 505 Collision This AR can not be used till its next Router Advertisement 507 5.4.1 Hold down 509 When a router is 'removed' from the Default Router List, it is 510 actually held down for a hold down timer period, in order to prevent 511 flapping. This happens when an AR disappears (upon expiration 512 timer), and when an AR is tried but can not reach the HA (upon 513 expiration of another AR, or upon tree hop for that AR). 515 An Attachment Router that is held down is not considered for the 516 purpose of roaming. When the hold down timer elapses, the AR is 517 removed from the DRL. 519 5.4.2 Instability 521 A MR is instable when a Held-Up AR is placed before the current AR. 522 Instability is transient (In the order of tree hop timers). When a 523 MR is instable, it MUST NOT send RAs with TIO. This avoids loops 524 when MR A wishes to attach to MR B and MR B wishes to attach to MR A. 525 Unless RA cross (which is a short window of time), a MR receives TIO 526 from stable ARs, which do not plan to attach to itself, so the MR can 527 safely attach to them. 529 A MR is instable when it is prepared to move shortly to another AR. 530 This happens typically when it discovers a new and more preferred 531 candidate AR, for the duration of the tree hop timer. During that 532 time, the new candidate is placed in Held-up state. Instability may 533 also occur when the current AR is lost and the next best is still 534 held up. Instability is resolved when the tree hop timer of all the 535 AR (s) causing instability elapse. Such AR is changes state to 536 Current or Held-Down. 538 5.4.3 Collision 540 A race condition occurs if 2 MRs send RA/TIO at the same time and 541 wish to join each other. In order to detect the situation, MRs time 542 stamp the sending of RA/TIO. Any RA/TIO received within a short 543 media-dependant period introduces a risk. To divide the risk, A 544 32bits extended preference is added in the TIO. The first byte is 545 the AR own preference (default 0), the rest is a boot time computed 546 random. 548 A MR that decides to join an AR will do so between (AR depth) and (AR 549 depth + 1) times the AR tree delay. But since a MR is unstable as 550 soon as it receives the RA/TIO from the preferred AR, it will 551 restrain from sending a RA/TIO between the time it receives the RA 552 and the time it actually jumps. So the crossing of RA may only 553 happen during the propagation time between the AR and the MR, plus 554 some internal queuing and processing time within each machine. It is 555 expected that one tree delay normally covers that interval, but 556 ultimately it is up to the implementation and the configuration of 557 the AR to define the duration of risk window. 559 There is risk of a collision when a MR receives an RA, for an other 560 mobile router that is more preferable than the current AR, within the 561 risk window. In the face of a potential collision, the Mobile Router 562 with the lowest extended preference processes the RA/TIO normally, 563 while the router with the highest preference places the other in 564 collision state, does not start the tree hop timer, and does not 565 become instable. It is expected that next RAs between the two will 566 not cross anyway. 568 5.5 Legacy Routers 570 A legacy router sends its Router Advertisements without a TIO. 571 Consequently, a legacy router can be mistaken for a fixed Access 572 Router when it is placed within a nested NEMO structure, and defeat 573 the loop avoidance mechanism. Consequently, it is important for the 574 administrator to prevent address autoconfiguration by visiting MRs 575 from such a legacy router. 577 6. Changes 579 6.1 Changes from version 00 to 01 581 Added text on subtree mobility from the discussion with Marcelo. 583 Added text on nested legacy routers from the discussion with 584 Marcelo. 586 7. Acknowledgments 588 The authors wish to thank Marco Molteni and Patrick Wetterwald 589 (cisco) for their participation to this design and the review of the 590 document, and Massimo Villari (university of Messina), for his early 591 work on simulation and research on the subject. This work is also 592 based on prior publications, in particular HMRA [7] by Hosik Cho and 593 Eun-Kyoung Paik from Seoul National University and other non IETF 594 publications coauthored with Thierry Ernst and Thomas Noel. Finally, 595 thanks to Marcelo Bagnulo Braun for his constructive review. 597 8 References 599 [1] Narten, T., Nordmark, E. and W. Simpson, "Neighbor Discovery for 600 IP Version 6 (IPv6)", RFC 2461, December 1998. 602 [2] Thomson, S. and T. Narten, "IPv6 Stateless Address 603 Autoconfiguration", RFC 2462, December 1998. 605 [3] Johnson, D., Perkins, C. and J. Arkko, "Mobility Support in 606 IPv6", draft-ietf-mobileip-ipv6-24 (work in progress), July 607 2003. 609 [4] Devarapalli, V., "Network Mobility (NEMO) Basic Support 610 Protocol", draft-ietf-nemo-basic-support-03 (work in progress), 611 June 2004. 613 [5] Ernst, T., "Network Mobility Support Goals and Requirements", 614 draft-ietf-nemo-requirements-02 (work in progress), February 615 2004. 617 [6] Ernst, T. and H. Lach, "Network Mobility Support Terminology", 618 draft-ietf-nemo-terminology-01 (work in progress), February 619 2004. 621 [7] Cho, H., "Hierarchical Mobile Router Advertisement for nested 622 mobile networks", draft-cho-nemo-hmra-00 (work in progress), 623 January 2004. 625 [8] Ernst, T., "Analysis of Multihoming in Network Mobility 626 Support", draft-ietf-nemo-multihoming-issues-00 (work in 627 progress), July 2004. 629 [9] Draves, R. and R. Hinden, "Default Router Preferences and 630 More-Specific Routes", draft-ietf-ipv6-router-selection-03 (work 631 in progress), December 2003. 633 Authors' Addresses 635 Pascal Thubert 636 Cisco Systems 637 Village d'Entreprises Green Side 638 400, Avenue de Roumanille 639 Batiment T3 640 Biot - Sophia Antipolis 06410 641 FRANCE 643 Phone: +33 4 97 23 26 34 644 EMail: pthubert@cisco.com 646 Nicolas Montavont 647 LSIIT - Univerity Louis Pasteur 648 Pole API, bureau C444 649 Boulevard Sebastien Brant 650 Illkirch 67400 651 FRANCE 653 Phone: (33) 3 90 24 45 87 654 EMail: montavont@dpt-info.u-strasbg.fr 655 URI: http://www-r2.u-strasbg.fr/~montavont/ 657 Intellectual Property Statement 659 The IETF takes no position regarding the validity or scope of any 660 Intellectual Property Rights or other rights that might be claimed to 661 pertain to the implementation or use of the technology described in 662 this document or the extent to which any license under such rights 663 might or might not be available; nor does it represent that it has 664 made any independent effort to identify any such rights. Information 665 on the procedures with respect to rights in RFC documents can be 666 found in BCP 78 and BCP 79. 668 Copies of IPR disclosures made to the IETF Secretariat and any 669 assurances of licenses to be made available, or the result of an 670 attempt made to obtain a general license or permission for the use of 671 such proprietary rights by implementers or users of this 672 specification can be obtained from the IETF on-line IPR repository at 673 http://www.ietf.org/ipr. 675 The IETF invites any interested party to bring to its attention any 676 copyrights, patents or patent applications, or other proprietary 677 rights that may cover technology that may be required to implement 678 this standard. Please address the information to the IETF at 679 ietf-ipr@ietf.org. 681 Disclaimer of Validity 683 This document and the information contained herein are provided on an 684 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 685 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 686 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 687 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 688 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 689 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 691 Copyright Statement 693 Copyright (C) The Internet Society (2004). This document is subject 694 to the rights, licenses and restrictions contained in BCP 78, and 695 except as set forth therein, the authors retain all their rights. 697 Acknowledgment 699 Funding for the RFC Editor function is currently provided by the 700 Internet Society.