idnits 2.17.1 draft-thubert-tree-discovery-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 18. -- Found old boilerplate from RFC 3978, Section 5.5 on line 771. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 748. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 755. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 761. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The abstract seems to contain references ([4]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. ** 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 298: '...on-Mobile Router MUST set the N flag o...' RFC 2119 keyword, line 380: '...following values MUST not change durin...' RFC 2119 keyword, line 387: '...d definitions that MUST be followed by...' RFC 2119 keyword, line 405: '...already part of a tree MAY move at any...' RFC 2119 keyword, line 408: '...an Mobile Router MUST NOT move down th...' (8 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: The following values MUST not change during the propagation of the TIO down the tree: Type, Length, G, H, TreePreference, TreeDelay and TreeID. All other fields of the TIO are updated at each hop of the propagation. -- 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 (July 15, 2005) is 6853 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: '2' is defined on line 675, but no explicit reference was found in the text == Unused Reference: '5' is defined on line 685, 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 3775 (ref. '3') (Obsoleted by RFC 6275) == Outdated reference: A later version (-06) exists of draft-ietf-nemo-requirements-04 ** Downref: Normative reference to an Informational draft: draft-ietf-nemo-requirements (ref. '5') == Outdated reference: A later version (-06) exists of draft-ietf-nemo-terminology-03 ** Downref: Normative reference to an Informational draft: draft-ietf-nemo-terminology (ref. '6') == Outdated reference: A later version (-07) exists of draft-ietf-nemo-multihoming-issues-02 Summary: 10 errors (**), 0 flaws (~~), 8 warnings (==), 7 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: January 16, 2006 C. Bontoux 5 Fortinet 6 N. Montavont 7 LSIIT - ULP 8 July 15, 2005 10 Nested Nemo Tree Discovery 11 draft-thubert-tree-discovery-02.txt 13 Status of this Memo 15 By submitting this Internet-Draft, each author represents that any 16 applicable patent or other IPR claims of which he or she is aware 17 have been or will be disclosed, and any of which he or she becomes 18 aware will be disclosed, in accordance with Section 6 of BCP 79. 20 Internet-Drafts are working documents of the Internet Engineering 21 Task Force (IETF), its areas, and its working groups. Note that 22 other groups may also distribute working documents as Internet- 23 Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six months 26 and may be updated, replaced, or obsoleted by other documents at any 27 time. It is inappropriate to use Internet-Drafts as reference 28 material or to cite them other than as "work in progress." 30 The list of current Internet-Drafts can be accessed at 31 http://www.ietf.org/ietf/1id-abstracts.txt. 33 The list of Internet-Draft Shadow Directories can be accessed at 34 http://www.ietf.org/shadow.html. 36 This Internet-Draft will expire on January 16, 2006. 38 Copyright Notice 40 Copyright (C) The Internet Society (2005). 42 Abstract 44 The purpose of this paper is to describe a minimum set of features 45 that extends the Nemo basic support [4] in order to avoid loops in 46 the nested Nemo case. As a result, Mobile Routers assemble into a 47 tree that can be optimized based on various metrics. 49 Table of Contents 51 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 53 2. Terms and Abbreviations . . . . . . . . . . . . . . . . . . . 3 55 3. Motivations . . . . . . . . . . . . . . . . . . . . . . . . . 4 56 3.1 Multi-Homed nested mobile network . . . . . . . . . . . . 4 57 3.2 Loops in nested Nemo . . . . . . . . . . . . . . . . . . . 5 59 4. Router Advertisement extensions . . . . . . . . . . . . . . . 6 60 4.1 Router Advertisement message . . . . . . . . . . . . . . . 6 61 4.2 Tree Information Option . . . . . . . . . . . . . . . . . 7 63 5. Tree Discovery . . . . . . . . . . . . . . . . . . . . . . . . 9 64 5.1 tree selection . . . . . . . . . . . . . . . . . . . . . . 11 65 5.2 Sub-tree mobility . . . . . . . . . . . . . . . . . . . . 11 66 5.3 DRL entries states and stability . . . . . . . . . . . . . 11 67 5.3.1 Held-Up . . . . . . . . . . . . . . . . . . . . . . . 12 68 5.3.2 Held-Down . . . . . . . . . . . . . . . . . . . . . . 13 69 5.3.3 Collision . . . . . . . . . . . . . . . . . . . . . . 13 70 5.3.4 Instability . . . . . . . . . . . . . . . . . . . . . 14 71 5.4 Legacy Routers . . . . . . . . . . . . . . . . . . . . . . 14 73 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 75 7. Security Considerations . . . . . . . . . . . . . . . . . . . 15 77 8. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 78 8.1 Changes from version 00 to 01 . . . . . . . . . . . . . . 16 79 8.2 Changes from version 01 to 02 . . . . . . . . . . . . . . 16 81 9. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16 83 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 17 84 10.1 Normative Reference . . . . . . . . . . . . . . . . . . . 17 85 10.2 Informative Reference . . . . . . . . . . . . . . . . . . 17 87 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 18 89 Intellectual Property and Copyright Statements . . . . . . . . 19 91 1. Introduction 93 As per Nemo Basic support [4], a Mobile Router autoconfigures a 94 single Care of Address (CoA) to register to its Home Agent and 95 terminate its Mobile Router-Home Agent tunnel. That Care of Address 96 is the Mobile Router point of attachment to the nested Nemo. 98 Consequently, if loops are avoided, the nested Nemo assumes the shape 99 of a tree. The nodes of the tree are Mobile Routers, the root is 100 either a fixed or a Mobile Router, called in the latter case the root 101 Mobile Router in NEMO terminology [6]. The leaves are mobile or 102 fixed hosts, called Local Fixed Nodes, Local Mobile Nodes and 103 Visiting Mobile Nodes in the NEMO terminology. 105 This paper provides (1) a minimum extension to IPv6 Neighbor 106 Discovery Router Advertisements in order to ensure that Mobile 107 Routers attaching to one another actually avoid loops and end up 108 forming a tree, and (2) the minimum common part of all Mobile Router 109 algorithms that is required to ensure that whatever their specific 110 decisions, loops between Mobile Routers will be avoided. 112 The method is based on an autonomous decision by each Mobile Router 113 with no global state convergence such as a MANET proactive routing 114 protocol. In fact, Mobile Routers may make different decisions from 115 a same input, based on their own configuration and their own 116 algorithms. 118 In order to build trees of Mobile Routers, we propose an extension to 119 the ICMP Router Advertisement (RA) message, the Tree Information 120 Option (TIO). The RA-TIO allows Mobile Routers to advertise the tree 121 they belong to, and to select and move to the best location within 122 the available trees. Mobile Routers propagate the TIO down the tree, 123 updating some metrics such as the tree depth, leaving alone root 124 information such as the tree identifier, and sending the result in 125 RAs over the ingress interfaces. 127 2. Terms and Abbreviations 129 This document assumes that the reader is familiar with Mobile IPv6 as 130 defined in [3] and with the concept of Mobile Router defined in the 131 Nemo terminology document [6]. 133 For the needs of this paper, the following new definitions are 134 introduced: 136 Nemo clusterhead: The root of a tree of mobile routers. When the 137 tree of Mobile Routers is attached to the infrastructure, the 138 fixed Access Router may act as cluster head if it supports the 139 Tree Information Option described in this document. If it does 140 not, then the clusterhead coincides with the root Mobile Router in 141 NEMO terminology. A clusterhead is elected even when the tree is 142 not attached to the infrastructure. A stand-alone Mobile Router 143 is a clusterhead. 145 Floating Tree: A Nested Nemo which clusterhead is a Mobile Router 146 that is not attached to an Access Router. 148 Grounded Tree: A Nested Nemo whose clusterhead is attached to the 149 infrastructure. In other words, the clusterhead is either a fixed 150 router that supports Router Advertisement - Tree Information 151 Option or is a Mobile Router which attachment router is a fixed 152 router that does not support Router Advertisement - Tree 153 Information Option. 155 Mobile Access Router: A Mobile Router that provides Access Router 156 services to other Mobile Routers. 158 Attachment Router: The Router that is selected as Access Router by a 159 Mobile Router, making it its parent in the nested NEMO tree. 161 Propagation: The action by a Mobile Router that consists in receiving 162 a Router Advertisement - Tree Information Option from its 163 Attachment Router, recomputing a few specific fields, removing 164 unknown suboption, and appending the resulting TIO to RAs sent 165 over the ingress interfaces. 167 3. Motivations 169 3.1 Multi-Homed nested mobile network 171 A nested mobile network that is made of multiple Mobile Routers 172 having a direct connection to the Internet is said to be multi-homed. 173 Multihoming in Nemo offers useful properties to Mobile Network Nodes. 174 The NEMO multihoming issues [9] draft lists potential multi-homed 175 configurations for Nemo and explains the different problems and 176 advantages that some configurations may introduce. Multihoming 177 offers three main abilities to the Nemo: it allows route recovery on 178 failure, redundancy and load-sharing between Mobile Routers (or 179 between interfaces of a given Mobile Router). However, for the 180 moment, there is no requirements nor protocol that would define in 181 interaction between several egress interfaces inside a Nemo. 183 In a nested Nemo, the hierarchy of Mobile Routers increases the 184 complexity of the route and/or router selection for Mobile Network 185 Nodes. Each level of a Nemo implies the usage of a new tunnel 186 between the Mobile Router and its home agent. Thus if a Mobile 187 Network Node connects to a sub-Nemo which is also a sub-Nemo, packets 188 from the Mobile Network Node will be encapsulated three times. 190 When the Nemo where the MN is connected to is multi-homed, the MN may 191 have the choice between several Attachment Router to be its default 192 router. Reference [7] introduces new options in Router Advertisement 193 to allow any node on a link to choose between several routers. This 194 option mainly consists of a 2-bits flag that indicates the preference 195 of the router (low, medium or high). Furthermore, the same flag can 196 be set in the Route Information option indicating the preference of a 197 specific prefix. Therefore, any node can determine its best default 198 router(s) according to a given destination and its best router for 199 default, which will be used by default. 201 However this preference is only useful in a flat topology; It gives a 202 way to the node to choose between different attachment routers 203 advertising prefixes on the node link. But if the node is inside a 204 hierarchical topology the node can not learn the depth of each 205 attachment router, and might not select the most efficient path. 207 One of the usage of the new option introduced in this document is to 208 distribute information on the hierarchy of Mobile Routers. This 209 information can be distributed to Attachment Routers, Mobile Routers 210 and Mobile Network Nodes as well in order to allow better route 211 selection and to increase the knowledge of the Nemo topology on each 212 node. 214 3.2 Loops in nested Nemo 216 When several Mobile Routers attach to each other to form a nested 217 Nemo, loops can be created if they are not explicitly avoided. In 218 the simplest case, when egress and ingress interfaces of an Mobile 219 Router are all wireless, a mobile router may be listening to Router 220 Advertisement from its own ingress interface, creating a confliction 221 problem. In the general case, arbitrary attachment of Mobile Routers 222 will form graphs that are not exempt of loops. For instance: Assume 223 a nested Nemo where Mobile Router1 is connected to the 224 infrastructure, and Mobile Router3 is attached to Mobile Router2. 225 Say that Mobile Router2 can hear both Mobile Router3 and Mobile 226 Router1 over its wireless egress interface. If Mobile Router2 select 227 Mobile Router1, the connectivity to the infrastructure is provided 228 for all. But if Mobile Router2 selects Mobile Router3, Mobile 229 Router2 and Mobile Router3 end up forming a loop and are disconnected 230 from their Home Agents. 232 With Nemo basic support, a Mobile Router uses a single primary Care 233 Of Address to attach to the nested structure. As a result, if loops 234 are avoided, the nested NEMO end up forming a tree. It is beneficial 235 to be able to form that tree in an optimum fashion for a given set of 236 metrics such as tree depth. 238 The shape of a nested Nemo may change rapidly due to Mobile Routers 239 movement. It is thus impractical to expect each Mobile Router to be 240 able to maintain states about the whole tree structure in a link 241 state fashion. On the contrary, it is also beneficial to allow each 242 Mobile Router to make its own independent selection based on a 243 minimum information about its immediate neighbors, in order to 244 reestablish the tree quickly upon erratic movements. 246 Each Mobile Router should be able to make its own attachment router 247 selection based on its own condition (eg battery level), its own set 248 of constraints that may not apply to other Mobile Routers in the 249 tree, and in general its own algorithm. As a result, the 250 standardization effort should concentrate on a common minimum set of 251 rules that must be common to all Mobile Routers in order to prevent 252 routing loops in the nested NEMO while leaving Mobile Routers 253 independent in their Attachment Router selection algorithms. 255 4. Router Advertisement extensions 257 New extensions of Router Advertisement are proposed to distribute the 258 knowledge of the Mobile Router hierarchy inside a nested Nemo. These 259 extensions are defined in different options/sub-options: a flag bit 260 from the reserved flag field of Router Advertisement message is used 261 to indicate whether the sending router is a Mobile Router or not; a 262 new option is defined to transport minimum information on the tree to 263 avoid loops generation; 265 4.1 Router Advertisement message 267 We propose to use a reserved flag of the Router Advertisement message 268 to inform whether the sending router is a Mobile Router or not. 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 | Code | Checksum | 274 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 275 | Cur Hop Limit |M|O|H|N|Reservd| Router Lifetime | 276 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 277 | Reachable Time | 278 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 279 | Retrans Timer | 280 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 281 | Options ... 282 +-+-+-+-+-+-+-+-+-+-+-+- 284 Figure 1: Router Advertisement 286 Nemo enabled router (N) 288 The Nemo enabled router (N) bit is set when the sending router is a 289 Mobile Router. 291 4.2 Tree Information Option 293 The following option regroups the minimum information that allows a 294 Mobile Router to discover a tree and select its point of attachment 295 while avoiding loop generation. It can also be used by Mobile 296 Network Nodes to select their best default router. If the default 297 router of a non-Mobile Router sends Router Advertisements with a tree 298 discovery option, the non-Mobile Router MUST set the N flag of its 299 own Router Advertisement to 0 and copy the Tree Discovery Option in 300 its own Router Advertisement. 302 0 1 2 3 303 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 304 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 305 | Type | Length |G|H| Reserved | 306 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 307 | TreePref. | Preference | BootTimeRandom | 308 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 309 | TreeDepth | Reserved | TreeDelay | 310 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 311 | PathDigest | 312 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 313 | | 314 + + 315 | TreeID | 316 + + 317 | | 318 + + 319 | | 320 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 321 | sub-option(s)... 322 +-+-+-+-+-+-+-+-+-+-+-+-+-+ 324 Figure 2: Tree Information Option 326 Type 8-bit unsigned integer set to 10 by the clusterhead. Value is 327 "TBD". 329 Length 8-bit unsigned integer set to 4. The length of the option 330 (including the type and length fields) in units of 8 octets. 332 Grounded (G) The Grounded (G) flag is set when the clusterhead is 333 attached to a fixed network infrastructure (such as the Internet). 335 Home (H) The Home (H) flag is set when the clusterhead is attached to 336 its home network. 338 Reserved 16-bit unsigned integer set to 0 by the clusterhead. 340 TreePreference 8-bit unsigned integer set by the clusterhead to its 341 preference and unchanged at propagation. Default is 0 (lowest 342 preference). 344 Preference The administrative preference of that (mobile) Access 345 Router. Default is 0. 255 is the highest possible preference. 346 Set by each Mobile Router at propagation time. 348 BootTimeRandom A random value computed at boot time and recomputed in 349 case of a duplication with another Attachment Router. The 350 concatenation of the Preference and the BootTimeRandom is a 32-bit 351 extended preference that is used to resolve collisions. It is set 352 by each Mobile Router at propagation time. 354 TreeDepth 8-bit unsigned integer. The tree depth of the clusterhead 355 is 0 if it is a fixed router and 1 if it is a Mobile Router. The 356 tree Depth of a tree Node is the depth of its attachment router as 357 received in a TIO, incremented by one. All nodes in the tree 358 advertise their tree depth in the Tree Information Options that 359 they append to the RA messages over their ingress interfaces as 360 part of the propagation process. 362 TreeDelay 16-bit unsigned integer set by the clusterhead indicating 363 the delay before changing the tree configuration, in milliseconds. 364 A default value is 128ms. It is expected to be an order of 365 magnitude smaller than the RA-interval so if the clusterhead has a 366 sub-second RA-interval, the Tree delay may be shorter than 100ms. 367 It is also expected to be an order of magnitude longer than the 368 typical propagation delay inside the nested Nemo. 370 PathDigest 32-bit unsigned integer CRC, updated by each Mobile 371 Router. This is the result of a CRC-32c computation on a bit 372 string obtained by appending the received value and the Mobile 373 Router Care of Address. clusterheads use a 'previous value' of 374 zeroes to initially set the PathDigest. 376 TreeID 128-bit unsigned integer which uniquely identify a tree. This 377 value is set by the clusterhead. The global IPv6 home address of 378 the clusterhead can be used. 380 The following values MUST not change during the propagation of the 381 TIO down the tree: Type, Length, G, H, TreePreference, TreeDelay and 382 TreeID. All other fields of the TIO are updated at each hop of the 383 propagation. 385 5. Tree Discovery 387 Here follows a set of rules and definitions that MUST be followed by 388 all Mobile Routers: 390 1. An Mobile Router that is not attached to an Attachment Router is 391 the Nemo clusterhead of its own floating tree. It's depth is 1. 393 2. An Mobile Router that is attached to an Attachment Router that 394 does not support TIO, is the clusterhead of its own grounded 395 tree. It's depth is 1. 397 3. A router sending a RA without TIO is considered a grounded 398 Attachment Router at depth 0. 400 4. The Nemo clusterhead of a tree exposes the tree in the Router 401 Advertisement - Tree Information Option and Mobile Routers 402 propagate the TIO down the tree with the RAs that they forward 403 over their ingress links. 405 5. An Mobile Router that is already part of a tree MAY move at any 406 time and with no delay in order to get closer to the clusterhead 407 of its current tree - i.e. in order to reduce its own tree depth. 408 But an Mobile Router MUST NOT move down the tree that it is 409 attached to. Mobile Routers MUST ignore RAs that are received 410 from other routers located deeper or at the same depth within the 411 same tree. 413 6. An Mobile Router may move from its current tree into any 414 different tree at any time and whatever the depth its reaches in 415 the new tree, but it may have to wait for a Tree Hop timer to 416 elapse in order to do so. The Mobile Router will join that other 417 tree if it is more preferable for reasons of connectivity, 418 configured preference, size, security, bandwidth, tree depth, or 419 whatever metrics the Mobile Router cares to use. 421 7. If a Mobile Router has selected a new attachment router but has 422 not moved yet (because it is waiting for Tree Hop timer to 423 elapse), the Mobile Router is unstable and refrains from sending 424 Router Advertisement - Tree Information Options. 426 8. When an Mobile Router joins a tree, moves within its tree, or 427 when it receives a modified TIO from its current attachment 428 router, the Mobile Router sends an unsolicited Router 429 Advertisement message on all its mobile networks (i.e. all its 430 ingress interfaces). The RA contains a TIO that propagates the 431 new tree information. At the same time, the Mobile Router MAY 432 send a Binding Update to its home agent or a local proxy of some 433 sort, because the tree it is attached to has changed. If the 434 Mobile Router fails to reach its Home Agent, it MAY attempt to 435 roll back the movement or to retry the Home Agent discovery 436 procedure. 438 9. This allows the new higher parts of the tree to take place first 439 eventually dragging their sub-tree with them, and allowing 440 stepped sub-tree reconfigurations, limiting relative movements. 442 5.1 tree selection 444 The tree selection is implementation and algorithm dependent. In 445 order to limit erratic movements, and all metrics being equal, Mobile 446 Routers SHOULD stick to their previous selection. Also, Mobile 447 Routers SHOULD provide a mean to filter out candidate Attachment 448 Routers whose availability is detected as fluctuating, at least when 449 more stable choices are available. For instance, the Mobile Router 450 MAY place the failed Attachment Router in a Hold Down mode that 451 ensures that the Attachment Router will not be reused for a given 452 period of time. 454 The known trees are associated with the Attachment Router that 455 advertises them and kept in a list by extending the Default Router 456 List. DRL entries are extended to store the information received 457 from the last TIO. These entries are managed by states and timers 458 described in the next section. 460 When connection to a fixed network is not possible or preferable for 461 security or other reasons, scattered trees should aggregate as much 462 as possible into larger trees in order to allow inner connectivity. 463 How to balance these trees is implementation dependent, and MAY use a 464 specific visitor-counter suboption in the TIO. 466 5.2 Sub-tree mobility 468 It might be perceived as beneficial for a sub-tree to move as a 469 whole. The way it would work is for a Mobile Router to stay root- 470 Mobile Router even if itself is attached into a parent tree. But the 471 loop avoidance is based on the knowledge of the tree that the Mobile 472 Router visit, preventing a Mobile Router to move down a same tree. 473 So without additional support, tree-level loops could form. 475 To avoid this, it is possible to add a path vector suboption to the 476 TIO that reflects the nesting of trees. If a root-Mobile Router 477 joins a parent tree, then it needs to add its treeID to the path 478 vector, but it can not join if the treeID is already listed. 480 A specific case is the root-Mobile Router of a tree that attaches to 481 a fixed Access Router. That root-Mobile Router might omit to 482 consider a TIO that comes from the new Attachment Router and decide 483 to stay root, in order to keep the tree consistency from the nested 484 Mobile Routers standpoint. This does not create loops, even if the 485 path vector is not present 487 5.3 DRL entries states and stability 489 Attachment routers in the DRL may or may not be usable for roaming 490 depending on runtime conditions. The following states are defined: 492 Current This Attachment Router is used for roaming 494 Candidate This Attachment Router can be used for roaming. 496 Held-Up This Attachment Router can not be used till tree hop timer 497 elapses. This does not occur for a fixed Attachment Router that 498 does not send a TIO since the tree delay is null in that case. 500 Held-Down This Attachment Router can not be used till hold down timer 501 elapses. At the end of the hold-down period, the router is 502 removed from the DRL, and will be reinserted if it appears again 503 with a RA. 505 Collision This Attachment Router can not be used till its next RA. 507 5.3.1 Held-Up 509 This state is managed by the tree Hop timer, it serves 2 purposes: 511 Delay the reattachment of a sub-tree that has been forced to 512 detach. This allows to make sure that when a sub-tree has 513 detached, the Router Advertisement - Tree Information Option that 514 is initiated by the new clusterhead has spread down the sub-tree 515 so that two different trees have formed. 517 Limit Router Advertisement - Tree Information Option storms when 518 two trees collide. The idea is that between the nodes from tree A 519 that wish to move to tree B, those that see the highest place in 520 tree B will move first and advertise their new locations before 521 other nodes from tree A actually move. 523 A new tree is discovered upon a router advertisement message with or 524 without a Router Advertisement - Tree Information Option. The Mobile 525 Router joins the tree by selecting the source of the RA message as 526 its attachment router (default gateway) and propagating the TIO 527 accordingly. 529 When a new tree is discovered, the candidate Attachment Router that 530 advertises the new tree is placed in a held up state for the duration 531 of a Tree Hop timer. If the new Attachment Router is more preferable 532 than the current one, the Mobile Router expects to jump and becomes 533 unstable. 535 A Mobile Router that is unstable may discover other Attachment 536 Routers from the same new tree during the instability phase. It 537 needs to start a new Tree Hop timer for all these. The first timer 538 that elapses for a given new tree clears them all for that tree, 539 allowing the Mobile Router to jump to the highest position available 540 in the new tree. 542 The duration of the Tree Hop timer depends on the tree delay of the 543 new tree and on the depth of Attachment Router that triggers it: 545 (AR's depth + random) * AR's tree_delay (where 0 <= random < 1). It 546 is randomized in order to limit collisions and synchronizations. 548 5.3.2 Held-Down 550 When a router is 'removed' from the Default Router List, it is 551 actually held down for a hold down timer period, in order to prevent 552 flapping. This happens when an Attachment Router disappears (upon 553 expiration timer), and when an Attachment Router is tried but can not 554 reach the Home Agent (upon expiration of another Attachment Router, 555 or upon tree hop for that Attachment Router). 557 An Attachment Router that is held down is not considered for the 558 purpose of roaming. When the hold down timer elapses, the Attachment 559 Router is removed from the DRL. 561 5.3.3 Collision 563 A race condition occurs if 2 Mobile Routers send Router Advertisement 564 - Tree Information Option at the same time and wish to join each 565 other. In order to detect the situation, Mobile Routers time stamp 566 the sending of Router Advertisement - Tree Information Option. Any 567 Router Advertisement - Tree Information Option received within a 568 short media-dependant period introduces a risk. To divide the risk, 569 A 32bits extended preference is added in the TIO. The first byte is 570 the clusterhead preference, then the router own preference (default 571 is 0 for both), the remaining 16 bits is a boot time computed 572 random. 574 A Mobile Router that decides to join an Attachment Router will do so 575 between (Attachment Router depth) and (Attachment Router depth + 1) 576 times the Attachment Router tree delay. But since a Mobile Router is 577 unstable as soon as it receives the Router Advertisement - Tree 578 Information Option from the preferred Attachment Router, it will 579 restrain from sending a Router Advertisement - Tree Information 580 Option between the time it receives the RA and the time it actually 581 jumps. So the crossing of RA may only happen during the propagation 582 time between the Attachment Router and the Mobile Router, plus some 583 internal queuing and processing time within each machine. It is 584 expected that one tree delay normally covers that interval, but 585 ultimately it is up to the implementation and the configuration of 586 the Attachment Router to define the duration of risk window. 588 There is risk of a collision when a Mobile Router receives an RA, for 589 an other mobile router that is more preferable than the current 590 Attachment Router, within the risk window. In the face of a 591 potential collision, the Mobile Router with the lowest extended 592 preference processes the Router Advertisement - Tree Information 593 Option normally, while the router with the highest preference places 594 the other in collision state, does not start the tree hop timer, and 595 does not become instable. It is expected that next RAs between the 596 two will not cross anyway. 598 5.3.4 Instability 600 A Mobile Router is instable when it is prepared to move shortly to 601 another Attachment Router. This happens typically when the Mobile 602 Router has selected a more preferred candidate Attachment Router and 603 has to wait for the tree hop timer to elapse before roaming. 604 Instability may also occur when the current Attachment Router is lost 605 and the next best is still held up. Instability is resolved when the 606 tree hop timer of all the Attachment Router (s) causing instability 607 elapse. Such Attachment Router is changes state to Current or Held- 608 Down. 610 Instability is transient (in the order of tree hop timers). When a 611 Mobile Router is unstable, it MUST NOT send RAs with TIO. This 612 avoids loops when Mobile Router A wishes to attach to Mobile Router B 613 and Mobile Router B wishes to attach to Mobile Router A. Unless RA 614 cross (see Collision section), a Mobile Router receives TIO from 615 stable Attachment Routers, which do not plan to attach to itself, so 616 the Mobile Router can safely attach to them. 618 5.4 Legacy Routers 620 A legacy router sends its Router Advertisements without a TIO. 621 Consequently, a legacy router can be mistaken for a fixed Access 622 Router when it is placed within a nested NEMO structure, and defeat 623 the loop avoidance mechanism. Consequently, it is important for the 624 administrator to prevent address autoconfiguration by visiting Mobile 625 Routers from such a legacy router. 627 6. IANA Considerations 629 Section 4.2. requires the definition of a new option to Neighbor 630 discovery [1] messages, the Router Advertisement - Tree Information 631 Option (RA-TIO). The Router Advertisement - Tree Information Option 632 has been assigned the value TBD within the numbering space for IPv6 633 Neighbor Discovery Option Formats. 635 7. Security Considerations 637 At the current level of this draft, the TIO bears the security level 638 of the RA and the link. Nothing is added to it. A deeper threat 639 analysis would be required to eventually propose additional security. 641 8. Changes 643 8.1 Changes from version 00 to 01 645 Added text on sub-tree mobility from the discussion with Marcelo. 647 Added text on nested legacy routers from the discussion with 648 Marcelo. 650 8.2 Changes from version 01 to 02 652 Improved text on instability 654 Changed the formula for the 4 bytes number used in collision 655 avoidance 657 9. Acknowledgments 659 The authors wish to thank Marco Molteni and Patrick Wetterwald 660 (cisco) for their participation to this design and the review of the 661 document, and Massimo Villari (university of Messina), for his early 662 work on simulation and research on the subject. This work is also 663 based on prior publications, in particular HMRA [8] by Hosik Cho and 664 Eun-Kyoung Paik from Seoul National University and other non IETF 665 publications coauthored with Thierry Ernst and Thomas Noel. Finally, 666 thanks to Marcelo Bagnulo Braun for his constructive review. 668 10. References 670 10.1 Normative Reference 672 [1] Narten, T., Nordmark, E., and W. Simpson, "Neighbor Discovery 673 for IP Version 6 (IPv6)", RFC 2461, December 1998. 675 [2] Thomson, S. and T. Narten, "IPv6 Stateless Address 676 Autoconfiguration", RFC 2462, December 1998. 678 [3] Johnson, D., Perkins, C., and J. Arkko, "Mobility Support in 679 IPv6", RFC 3775, June 2004. 681 [4] Devarapalli, V., Wakikawa, R., Petrescu, A., and P. Thubert, 682 "Network Mobility (NEMO) Basic Support Protocol", RFC 3963, 683 January 2005. 685 [5] Ernst, T., "Network Mobility Support Goals and Requirements", 686 draft-ietf-nemo-requirements-04 (work in progress), 687 February 2005. 689 [6] Ernst, T. and H. Lach, "Network Mobility Support Terminology", 690 draft-ietf-nemo-terminology-03 (work in progress), 691 February 2005. 693 [7] Draves, R. and D. Thaler, "Default Router Preferences and More- 694 Specific Routes", draft-ietf-ipv6-router-selection-07 (work in 695 progress), January 2005. 697 10.2 Informative Reference 699 [8] Cho, H., "Hierarchical Mobile Router Advertisement for nested 700 mobile networks", draft-cho-nemo-hmra-00 (work in progress), 701 January 2004. 703 [9] Ernst, T., "Analysis of Multihoming in Network Mobility 704 Support", draft-ietf-nemo-multihoming-issues-02 (work in 705 progress), February 2005. 707 Authors' Addresses 709 Pascal Thubert 710 Cisco Systems 711 Village d'Entreprises Green Side 712 400, Avenue de Roumanille 713 Batiment T3 714 Biot - Sophia Antipolis 06410 715 FRANCE 717 Phone: +33 4 97 23 26 34 718 Email: pthubert@cisco.com 720 Caroline Bontoux 721 Fortinet 722 Sophia Antipolis 723 Biot 06410 724 FRANCE 726 Email: cbontoux@fortinet.com 728 Nicolas Montavont 729 LSIIT - Univerity Louis Pasteur 730 Pole API, bureau C444 731 Boulevard Sebastien Brant 732 Illkirch 67400 733 FRANCE 735 Phone: (33) 3 90 24 45 87 736 Email: montavont@dpt-info.u-strasbg.fr 737 URI: http://www-r2.u-strasbg.fr/~montavont/ 739 Intellectual Property Statement 741 The IETF takes no position regarding the validity or scope of any 742 Intellectual Property Rights or other rights that might be claimed to 743 pertain to the implementation or use of the technology described in 744 this document or the extent to which any license under such rights 745 might or might not be available; nor does it represent that it has 746 made any independent effort to identify any such rights. Information 747 on the procedures with respect to rights in RFC documents can be 748 found in BCP 78 and BCP 79. 750 Copies of IPR disclosures made to the IETF Secretariat and any 751 assurances of licenses to be made available, or the result of an 752 attempt made to obtain a general license or permission for the use of 753 such proprietary rights by implementers or users of this 754 specification can be obtained from the IETF on-line IPR repository at 755 http://www.ietf.org/ipr. 757 The IETF invites any interested party to bring to its attention any 758 copyrights, patents or patent applications, or other proprietary 759 rights that may cover technology that may be required to implement 760 this standard. Please address the information to the IETF at 761 ietf-ipr@ietf.org. 763 Disclaimer of Validity 765 This document and the information contained herein are provided on an 766 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 767 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 768 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 769 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 770 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 771 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 773 Copyright Statement 775 Copyright (C) The Internet Society (2005). This document is subject 776 to the rights, licenses and restrictions contained in BCP 78, and 777 except as set forth therein, the authors retain all their rights. 779 Acknowledgment 781 Funding for the RFC Editor function is currently provided by the 782 Internet Society.