idnits 2.17.00 (12 Aug 2021) /tmp/idnits38177/draft-thubert-tree-discovery-03.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 1011. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 988. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 995. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 1001. ** 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 314: '... Router MUST set the N flag of its o...' RFC 2119 keyword, line 401: '...following values MUST not change durin...' RFC 2119 keyword, line 424: '... receiver MUST silently ignore an...' RFC 2119 keyword, line 437: '... Implementations MUST silently ignore ...' RFC 2119 keyword, line 485: '... MUST be ignored by the receiver....' (12 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 308 has weird spacing: '... option regro...' == 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 (April 20, 2006) is 5875 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 916, but no explicit reference was found in the text == Unused Reference: '5' is defined on line 926, 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: 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') == Outdated reference: draft-ietf-ipv6-router-selection has been published as RFC 4191 == Outdated reference: draft-ietf-nemo-multihoming-issues has been published as RFC 4980 Summary: 10 errors (**), 0 flaws (~~), 10 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: October 22, 2006 C. Bontoux 5 Fortinet 6 N. Montavont 7 LSIIT - ULP 8 April 20, 2006 10 Nested Nemo Tree Discovery 11 draft-thubert-tree-discovery-03.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 October 22, 2006. 38 Copyright Notice 40 Copyright (C) The Internet Society (2006). 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 . . . . . . . . . . . . . . . . . . . . . . . . . 4 53 2. Terms and Abbreviations . . . . . . . . . . . . . . . . . . . 4 55 3. Motivations . . . . . . . . . . . . . . . . . . . . . . . . . 5 56 3.1 Multi-Homed nested mobile network . . . . . . . . . . . . 5 57 3.2 Loops in nested Nemo . . . . . . . . . . . . . . . . . . . 6 59 4. Router Advertisement extensions . . . . . . . . . . . . . . . 8 60 4.1 Router Advertisement message . . . . . . . . . . . . . . . 8 61 4.2 Tree Information Option . . . . . . . . . . . . . . . . . 8 62 4.3 TIO suboption . . . . . . . . . . . . . . . . . . . . . . 11 63 4.3.1 Format . . . . . . . . . . . . . . . . . . . . . . . . 11 64 4.3.2 Pad1 . . . . . . . . . . . . . . . . . . . . . . . . . 11 65 4.3.3 PadN . . . . . . . . . . . . . . . . . . . . . . . . . 12 66 4.3.4 Bandwidth Suboption . . . . . . . . . . . . . . . . . 12 67 4.3.5 Stable time Suboption . . . . . . . . . . . . . . . . 13 68 4.3.6 Tree Group ID Suboption . . . . . . . . . . . . . . . 13 70 5. Tree Discovery . . . . . . . . . . . . . . . . . . . . . . . . 15 71 5.1 tree selection . . . . . . . . . . . . . . . . . . . . . . 16 72 5.2 Sub-tree mobility . . . . . . . . . . . . . . . . . . . . 16 73 5.3 Administrative depth . . . . . . . . . . . . . . . . . . . 17 74 5.4 DRL entries states and stability . . . . . . . . . . . . . 17 75 5.4.1 Held-Up . . . . . . . . . . . . . . . . . . . . . . . 18 76 5.4.2 Held-Down . . . . . . . . . . . . . . . . . . . . . . 19 77 5.4.3 Collision . . . . . . . . . . . . . . . . . . . . . . 19 78 5.4.4 Instability . . . . . . . . . . . . . . . . . . . . . 20 79 5.5 Legacy Routers . . . . . . . . . . . . . . . . . . . . . . 20 81 6. Directed Acyclic Graph Discovery . . . . . . . . . . . . . . . 20 83 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 21 85 8. Security Considerations . . . . . . . . . . . . . . . . . . . 21 87 9. Changes . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 88 9.1 Changes from version 00 to 01 . . . . . . . . . . . . . . 21 89 9.2 Changes from version 01 to 02 . . . . . . . . . . . . . . 21 90 9.3 Changes from version 02 to 03 . . . . . . . . . . . . . . 21 92 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . 21 94 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 23 95 11.1 Normative Reference . . . . . . . . . . . . . . . . . . . 23 96 11.2 Informative Reference . . . . . . . . . . . . . . . . . . 23 97 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 24 99 Intellectual Property and Copyright Statements . . . . . . . . 25 101 1. Introduction 103 As per Nemo Basic support [4], a Mobile Router autoconfigures a 104 single Care of Address (CoA) to register to its Home Agent and 105 terminate its Mobile Router-Home Agent tunnel. That Care of Address 106 is the Mobile Router point of attachment to the nested Nemo. 108 Consequently, if loops are avoided, the nested Nemo assumes the shape 109 of a tree. The nodes of the tree are Mobile Routers, the root is 110 either a fixed or a Mobile Router, called in the latter case the root 111 Mobile Router in NEMO terminology [6]. The leaves are mobile or 112 fixed hosts, called Local Fixed Nodes, Local Mobile Nodes and 113 Visiting Mobile Nodes in the NEMO terminology. 115 This paper provides (1) a minimum extension to IPv6 Neighbor 116 Discovery Router Advertisements in order to ensure that Mobile 117 Routers attaching to one another actually avoid loops and end up 118 forming a tree, and (2) the minimum common part of all Mobile Router 119 algorithms that is required to ensure that whatever their specific 120 decisions, loops between Mobile Routers will be avoided. 122 The method is based on an autonomous decision by each Mobile Router 123 with no global state convergence such as a MANET proactive routing 124 protocol. In fact, Mobile Routers may make different decisions from 125 a same input, based on their own configuration and their own 126 algorithms. 128 In order to build trees of Mobile Routers, we propose an extension to 129 the ICMP Router Advertisement (RA) message, the Tree Information 130 Option (TIO). The TIO allows Mobile Routers to advertise the tree 131 they belong to, and to select and move to the best location within 132 the available trees. Mobile Routers propagate the TIO in RA down the 133 tree, updating some metrics such as the tree depth, leaving alone 134 root information such as the tree identifier, and sending the result 135 in RAs over the ingress interfaces. 137 2. Terms and Abbreviations 139 This document assumes that the reader is familiar with Mobile IPv6 as 140 defined in [3] and with the concept of Mobile Router defined in the 141 Nemo terminology document [6]. 143 For the needs of this paper, the following new definitions are 144 introduced: 146 Nemo clusterhead: The root of a tree of mobile routers. When the 147 tree of Mobile Routers is attached to the infrastructure, the 148 fixed Access Router may act as cluster head if it supports the 149 Tree Information Option described in this document. If it does 150 not, then the clusterhead coincides with the root Mobile Router in 151 NEMO terminology. A clusterhead is elected even when the tree is 152 not attached to the infrastructure. A stand-alone Mobile Router 153 is a clusterhead. 155 Floating Tree: A Nested Nemo which clusterhead is a Mobile Router 156 that is not attached to an Access Router. 158 Grounded Tree: A Nested Nemo whose clusterhead is attached to the 159 infrastructure. In other words, the clusterhead is either a fixed 160 router that supports Router Advertisement - Tree Information 161 Option or is a Mobile Router which attachment router is a fixed 162 router that does not support Router Advertisement - Tree 163 Information Option. 165 Mobile Access Router: A Mobile Router that provides Access Router 166 services to other Mobile Routers. 168 Attachment Router: The Router that is selected as Access Router by a 169 Mobile Router, making it its parent in the nested NEMO tree. 171 Propagation: The action by a Mobile Router that consists in receiving 172 a Router Advertisement Tree Information Option from its Attachment 173 Router, recomputing a few specific fields, removing unknown 174 suboptions, and appending the resulting TIO to RAs sent over the 175 ingress interfaces. 177 3. Motivations 179 3.1 Multi-Homed nested mobile network 181 A nested mobile network that is made of multiple Mobile Routers 182 having a direct connection to the Internet is said to be multi-homed. 183 Multihoming in Nemo offers useful properties to Mobile Network Nodes. 184 The NEMO multihoming issues [9] draft lists potential multi-homed 185 configurations for Nemo and explains the different problems and 186 advantages that some configurations may introduce. Multihoming 187 offers three main abilities to the Nemo: it allows route recovery on 188 failure, redundancy and load-sharing between Mobile Routers (or 189 between interfaces of a given Mobile Router). However, for the 190 moment, there is no requirements nor protocol that would define in 191 interaction between several egress interfaces inside a Nemo. 193 In a nested Nemo, the hierarchy of Mobile Routers increases the 194 complexity of the route and/or router selection for Mobile Network 195 Nodes. Each level of a Nemo implies the usage of a new tunnel 196 between the Mobile Router and its home agent. Thus if a Mobile 197 Network Node connects to a sub-Nemo which is also a sub-Nemo, packets 198 from the Mobile Network Node will be encapsulated three times. 200 When the Nemo where the MN is connected to is multi-homed, the MN may 201 have the choice between several Attachment Router to be its default 202 router. Reference [7] introduces new options in Router Advertisement 203 to allow any node on a link to choose between several routers. This 204 option mainly consists of a 2-bits flag that indicates the preference 205 of the router (low, medium or high). Furthermore, the same flag can 206 be set in the Route Information option indicating the preference of a 207 specific prefix. Therefore, any node can determine its best default 208 router(s) according to a given destination and its best router for 209 default, which will be used by default. 211 However this preference is only useful in a flat topology; It gives a 212 way to the node to choose between different attachment routers 213 advertising prefixes on the node link. But if the node is inside a 214 hierarchical topology the node can not learn the depth of each 215 attachment router, and might not select the most efficient path. 217 One of the usage of the new option introduced in this document is to 218 distribute information on the hierarchy of Mobile Routers. This 219 information can be distributed to Attachment Routers, Mobile Routers 220 and Mobile Network Nodes as well in order to allow better route 221 selection and to increase the knowledge of the Nemo topology on each 222 node. 224 3.2 Loops in nested Nemo 226 When several Mobile Routers attach to each other to form a nested 227 Nemo, loops can be created if they are not explicitly avoided. In 228 the simplest case, when egress and ingress interfaces of A Mobile 229 Router are all wireless, a mobile router may be listening to Router 230 Advertisement from its own ingress interface, creating a confliction 231 problem. In the general case, arbitrary attachment of Mobile Routers 232 will form graphs that are not exempt of loops. For instance: Assume 233 a nested Nemo where Mobile Router1 is connected to the 234 infrastructure, and Mobile Router3 is attached to Mobile Router2. 235 Say that Mobile Router2 can hear both Mobile Router3 and Mobile 236 Router1 over its wireless egress interface. If Mobile Router2 select 237 Mobile Router1, the connectivity to the infrastructure is provided 238 for all. But if Mobile Router2 selects Mobile Router3, Mobile 239 Router2 and Mobile Router3 end up forming a loop and are disconnected 240 from their Home Agents. 242 With Nemo basic support, a Mobile Router uses a single primary Care 243 Of Address to attach to the nested structure. As a result, if loops 244 are avoided, the nested NEMO end up forming a tree. It is beneficial 245 to be able to form that tree in an optimum fashion for a given set of 246 metrics such as tree depth. 248 The shape of a nested Nemo may change rapidly due to Mobile Routers 249 movement. It is thus impractical to expect each Mobile Router to be 250 able to maintain states about the whole tree structure in a link 251 state fashion. On the contrary, it is also beneficial to allow each 252 Mobile Router to make its own independent selection based on a 253 minimum information about its immediate neighbors, in order to 254 reestablish the tree quickly upon erratic movements. 256 Each Mobile Router should be able to make its own attachment router 257 selection based on its own condition (eg battery level), its own set 258 of constraints that may not apply to other Mobile Routers in the 259 tree, and in general its own algorithm. As a result, the 260 standardization effort should concentrate on a common minimum set of 261 rules that must be common to all Mobile Routers in order to prevent 262 routing loops in the nested NEMO while leaving Mobile Routers 263 independent in their Attachment Router selection algorithms. 265 4. Router Advertisement extensions 267 New extensions of Router Advertisement are proposed to distribute the 268 knowledge of the Mobile Router hierarchy inside a nested Nemo. These 269 extensions are defined in different options/sub-options: a flag bit 270 from the reserved flag field of Router Advertisement message is used 271 to indicate whether the sending router is a Mobile Router or not; a 272 new option is defined to transport minimum information on the tree to 273 avoid loops generation; 275 4.1 Router Advertisement message 277 We propose to use a reserved flag of the Router Advertisement message 278 to inform whether the sending router is a Mobile Router or not. 280 0 1 2 3 281 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 282 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 283 | Type | Code | Checksum | 284 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 285 | Cur Hop Limit |M|O|H|N|Reservd| Router Lifetime | 286 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 287 | Reachable Time | 288 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 289 | Retrans Timer | 290 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 291 | Options ... 292 +-+-+-+-+-+-+-+-+-+-+-+- 294 Figure 1: Router Advertisement 296 Nemo enabled router (N) 298 The Nemo enabled router (N) bit is set when the sending router is a 299 Mobile Router. 301 4.2 Tree Information Option 303 The Tree Information Option carries a number of metrics and other 304 information that allows a Mobile Router to discover a tree and select 305 its point of attachment while avoiding loop generation. 307 The option is a container option, which might contain a number of 308 suboptions. The base option regroups the minimum information set 309 that is mandatory in all cases. 311 A TIO can also be used by Mobile Network Nodes to select their best 312 default router. If the default router of a non-Mobile Router sends 313 Router Advertisements with a Tree Information Option, the non-Mobile 314 Router MUST set the N flag of its own Router Advertisement to 0 and 315 copy the Tree Discovery Option in its own Router Advertisement. 317 0 1 2 3 318 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 319 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 320 | Type | Length |G|H|B| Reserved | 321 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 322 | TreePref. | BootTimeRandom | 323 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 324 | MR Preference | TreeDepth | TreeDelay | 325 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 326 | PathDigest | 327 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 328 | | 329 + + 330 | TreeID | 331 + + 332 | | 333 + + 334 | | 335 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 336 | sub-option(s)... 337 +-+-+-+-+-+-+-+-+-+-+-+-+-+ 339 Figure 2: RA Tree Information Option 341 Type: 8-bit unsigned integer set to 10 by the clusterhead. Value is 342 "TBD". 344 Length: 8-bit unsigned integer set to 4 when there is no suboption. 345 The length of the option (including the type and length fields and 346 the suboptions) in units of 8 octets. 348 Grounded (G): The Grounded (G) flag is set when the clusterhead is 349 attached to a fixed network infrastructure (such as the Internet). 351 Home (H): The Home (H) flag is set when the clusterhead is attached 352 to its home network. 354 Battery (B): The Battery (B) flag is indicates that a parent in the 355 tree operates on batteries, an indication of a costly operation. 356 It is set by a mobile router which operates on battery and when 357 set, it is left set as it is propagated down the tree. 359 Reserved: 13-bit unsigned integer set to 0 by the clusterhead. 361 TreePreference: 8-bit unsigned integer set by the clusterhead to its 362 preference and unchanged at propagation. Default is 0 (lowest 363 preference). 365 BootTimeRandom: A random value computed at boot time and recomputed 366 in case of a duplication with another Attachment Router. The 367 concatenation of the Preference and the BootTimeRandom is a 32-bit 368 extended preference that is used to resolve collisions. It is set 369 by each Mobile Router at propagation time. 371 Preference: The administrative preference of that (mobile) Access 372 Router. Default is 0. 255 is the highest possible preference. 373 Set by each Mobile Router at propagation time. 375 TreeDepth: 8-bit unsigned integer. The tree depth of the clusterhead 376 is 0 if it is a fixed router and 1 if it is a Mobile Router. The 377 tree Depth of a tree Node is the depth of its attachment router as 378 received in a TIO, incremented by at least one. All nodes in the 379 tree advertise their tree depth in the Tree Information Options 380 that they append to the RA messages over their ingress interfaces 381 as part of the propagation process. 383 TreeDelay: 16-bit unsigned integer set by the clusterhead indicating 384 the delay before changing the tree configuration, in milliseconds. 385 A default value is 128ms. It is expected to be an order of 386 magnitude smaller than the RA-interval so if the clusterhead has a 387 sub-second RA-interval, the Tree delay may be shorter than 100ms. 388 It is also expected to be an order of magnitude longer than the 389 typical propagation delay inside the nested Nemo. 391 PathDigest: 32-bit unsigned integer CRC, updated by each Mobile 392 Router. This is the result of a CRC-32c computation on a bit 393 string obtained by appending the received value and the Mobile 394 Router Care of Address. clusterheads use a 'previous value' of 395 zeroes to initially set the PathDigest. 397 TreeID: 128-bit unsigned integer which uniquely identify a tree. 398 This value is set by the clusterhead. The global IPv6 home 399 address of the clusterhead can be used. 401 The following values MUST not change during the propagation of the 402 TIO down the tree: Type, Length, G, H, TreePreference, TreeDelay and 403 TreeID. All other fields of the TIO are updated at each hop of the 404 propagation. 406 4.3 TIO suboption 408 In addition to the minimum options presented in the base option, a 409 number of suboptions are defined for the TIO: 411 4.3.1 Format 413 0 1 2 3 414 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 415 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 416 | Subopt. Type | Subopt Length | Suboption Data... 417 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 419 Figure 3: TIO suboption generic format 421 Suboption Type: 8-bit identifier of the type of mobility option. 422 When processing a TIO containing a suboption for which the 423 suboption Type value is not recognized by the receiver, the 424 receiver MUST silently ignore and skip over the suboption, 425 correctly handling any remaining options in the message. 427 Suboption Length: 8-bit unsigned integer, representing the length in 428 octets of the suboption, not including the suboption Type and 429 Length fields. 431 Suboption Data: A variable length field that contains data specific 432 to the option. 434 The following subsections specify the TIO suboptions which are 435 currently defined for use in the Mobility Header. 437 Implementations MUST silently ignore any TIO suboptions options that 438 they do not understand. 440 TIO suboptions may have alignment requirements. Following the 441 convention in IPv6, these options are aligned in a packet so that 442 multi-octet values within the Option Data field of each option fall 443 on natural boundaries (i.e., fields of width n octets are placed at 444 an integer multiple of n octets from the start of the header, for n = 445 1, 2, 4, or 8). 447 4.3.2 Pad1 449 The Pad1 suboption does not have any alignment requirements. Its 450 format is as follows: 452 0 453 0 1 2 3 4 5 6 7 454 +-+-+-+-+-+-+-+-+ 455 | Type = 0 | 456 +-+-+-+-+-+-+-+-+ 458 Figure 4: Pad 1 460 NOTE! the format of the Pad1 option is a special case - it has 461 neither Option Length nor Option Data fields. 463 The Pad1 option is used to insert one octet of padding in the TIO to 464 enable suboptions alignment. If more than one octet of padding is 465 required, the PadN option, described next, should be used rather than 466 multiple Pad1 options. 468 4.3.3 PadN 470 The PadN option does not have any alignment requirements. Its format 471 is as follows: 473 0 1 474 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 475 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - 476 | Type = 1 | Subopt Length | Subopt Data 477 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - - 479 Figure 5: Pad N 481 The PadN option is used to insert two or more octets of padding in 482 the TIO to enable suboptions alignment. For N (N > 1) octets of 483 padding, the Option Length field contains the value N-2, and the 484 Option Data consists of N-2 zero-valued octets. PadN Option data 485 MUST be ignored by the receiver. 487 4.3.4 Bandwidth Suboption 489 This suboption carries the bandwidth available up the tree via a 490 specific parent. The value is expressed in the log base 2 of the 491 speed, expressed in bps. The Bandwidth suboption does not have any 492 alignment requirements. Its format is as follows: 494 0 1 2 495 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 496 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ 497 | Type = 2 | Length = 1 | Bandwidth | 498 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ 499 Figure 6: Bandwidth Suboption 501 Type: Set to 2 for the Bandwidth suboption. 503 Length: Set to 1 for the Bandwidth suboption. 505 Bandwidth: 8-bit unsigned integer. The Log2 of the speed of the path 506 expressed in bps. The clusterhead initializes that field using 507 the speed of the link to the Access Router to which it is attached 508 or 0xFF if it is floating. An attached MR propagates it as the 509 minimum of the Bandwidth as received in the TIO from the parent 510 and the access speed between the MR and the parent. As a result, 511 the value received from a candidate AR is that of the bottleneck 512 between that AR and the wire access. 514 4.3.5 Stable time Suboption 516 This suboption carries an indicator of the stability of a network. 517 This indicator is the time since the branch to which the MR is 518 attached has remained unchanged. The value is expressed in the log 519 base 2 of that duration, expressed in milliseconds. The Stable time 520 suboption does not have any alignment requirements. Its format is as 521 follows: 523 0 1 2 524 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 525 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ 526 | Type = 3 | Length = 1 | Stable time | 527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---------------+ 529 Figure 7: Stable time 531 Type: Set to 3 for the Stable time suboption. 533 Length: Set to 1 for the Stable time suboption. 535 Stable time: 8-bit unsigned integer. The Log2 of the time since the 536 last change in the attachment branch, expressed in milliseconds. 537 This is set by the MR as it propagates the TIO down the tree, 538 indicating for how long the PathDigest in the TIO from its parent 539 has remained unchanged. 541 4.3.6 Tree Group ID Suboption 543 This suboption carries the Group ID for the tree. It is set by the 544 clusterhead and is left unchanged by the MR that propagates the TIO 545 down the tree. The Tree Group ID Suboption has an alignment 546 requirement of 8n+6. Its format is as follows: 548 0 1 2 3 549 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 550 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 551 | Type = 4 | Length = 16 | 552 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 553 | | 554 + + 555 | Tree | 556 + Group ID + 557 | | 558 + + 559 | | 560 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 562 Figure 8: Tree Group ID Suboption 564 Type: 8-bit unsigned integer. Its value is 4 for the Tree Group ID 565 suboption. 567 Length: 8-bit unsigned integer. Its value is 16 for the Tree Group 568 ID suboption. 570 Tree Group ID: 128-bit unsigned integer which identify a group for a 571 tree. This value is set by the clusterhead. It can be set 572 administratively, for instance to an IPv6 multicast group. 574 5. Tree Discovery 576 Here follows a set of rules and definitions that MUST be followed by 577 all Mobile Routers: 579 1. A Mobile Router that is not attached to an Attachment Router is 580 the Nemo clusterhead of its own floating tree. It's depth is 1. 582 2. A Mobile Router that is attached to an Attachment Router that 583 does not support TIO, is the clusterhead of its own grounded 584 tree. It's depth is 1. 586 3. A router sending a RA without TIO is considered a grounded 587 Attachment Router at depth 0. 589 4. The Nemo clusterhead of a tree exposes the tree in the Router 590 Advertisement Tree Information Option and Mobile Routers 591 propagate the TIO down the tree with the RAs that they forward 592 over their ingress links. 594 5. A Mobile Router that is already part of a tree MAY move at any 595 time and with no delay in order to get closer to the clusterhead 596 of its current tree - i.e. in order to reduce its own tree depth. 597 But A Mobile Router MUST NOT move down the tree that it is 598 attached to. Mobile Routers MUST ignore RAs that are received 599 from other routers located deeper or at the same depth within the 600 same tree. 602 6. A Mobile Router may move from its current tree into any different 603 tree at any time and whatever the depth it reaches in the new 604 tree, but it may have to wait for a Tree Hop timer to elapse in 605 order to do so. The Mobile Router will join that other tree if 606 it is more preferable for reasons of connectivity, configured 607 preference, size, security, bandwidth, tree depth, or whatever 608 metrics the Mobile Router cares to use. 610 7. If a Mobile Router has selected a new attachment router but has 611 not moved yet (because it is waiting for Tree Hop timer to 612 elapse), the Mobile Router is unstable and refrains from sending 613 Router Advertisement - Tree Information Options. 615 8. When A Mobile Router joins a tree, moves within its tree, or when 616 it receives a modified TIO from its current attachment router, 617 the Mobile Router sends an unsolicited Router Advertisement 618 message on all its mobile networks (i.e. all its ingress 619 interfaces). The RA contains a TIO that propagates the new tree 620 information. At the same time, the Mobile Router MAY send a 621 Binding Update to its home agent or a local proxy of some sort, 622 because the tree it is attached to has changed. If the Mobile 623 Router fails to reach its Home Agent, it MAY attempt to roll back 624 the movement or to retry the Home Agent discovery procedure. 626 9. This allows the new higher parts of the tree to take place first 627 eventually dragging their sub-tree with them, and allowing 628 stepped sub-tree reconfigurations, limiting relative movements. 630 5.1 tree selection 632 The tree selection is implementation and algorithm dependent. In 633 order to limit erratic movements, and all metrics being equal, Mobile 634 Routers SHOULD stick to their previous selection. Also, Mobile 635 Routers SHOULD provide a mean to filter out candidate Attachment 636 Routers whose availability is detected as fluctuating, at least when 637 more stable choices are available. For instance, the Mobile Router 638 MAY place the failed Attachment Router in a Hold Down mode that 639 ensures that the Attachment Router will not be reused for a given 640 period of time. 642 The known trees are associated with the Attachment Router that 643 advertises them and kept in a list by extending the Default Router 644 List. DRL entries are extended to store the information received 645 from the last TIO. These entries are managed by states and timers 646 described in the next section. 648 When connection to a fixed network is not possible or preferable for 649 security or other reasons, scattered trees should aggregate as much 650 as possible into larger trees in order to allow inner connectivity. 651 How to balance these trees is implementation dependent, and MAY use a 652 specific visitor-counter suboption in the TIO. 654 A Mobile Router SHOULD verify that bidirectional connectivity is 655 available with a candidate Attachment Router before it attaches to 656 that candidate. Some layer 2 such as 802.11 infrastructure mode will 657 provide for this, while others such as 802.11 adhoc mode will not. 658 If the layer 2 does not guarantee the bidirectional connectivity, 659 then the MR needs to make sure that it can reach the AR. This can be 660 achieved using Neighbor Sollicitation and refraining from attaching 661 to an AR for which no neighbor cache exists, or the state is still 662 INCOMPLETE. 664 5.2 Sub-tree mobility 666 It might be perceived as beneficial for a sub-tree to move as a 667 whole. The way it would work is for a Mobile Router to stay 668 clusterhead even if itself is attached into a parent tree. But the 669 loop avoidance is based on the knowledge of the tree that the Mobile 670 Router visit, preventing a Mobile Router to move down a same tree. 671 So without additional support, tree-level loops could form. 673 To avoid this, it is possible to add a path vector suboption to the 674 TIO that reflects the nesting of trees. If a root-Mobile Router 675 joins a parent tree, then it needs to add its treeID to the path 676 vector, but it can not join if the treeID is already listed. 678 A specific case is the root-Mobile Router of a tree that attaches to 679 a fixed Access Router. That root-Mobile Router might omit to 680 consider a TIO that comes from the new Attachment Router and decide 681 to stay root, in order to keep the tree consistency from the nested 682 Mobile Routers standpoint. This does not create loops, even if the 683 path vector is not present 685 5.3 Administrative depth 687 When the tree is formed under a common administration, or when a 688 Mobile Router performs a certain role within a community, it might be 689 beneficial to associate a range of acceptable depth with that MR. 690 For instance, a MR that has limited battery should be a leaf unless 691 there is no other choice, and thus expose an exagerated depth. On 692 the other hane, a MR that is designed for backhaul should operate in 693 a low range of depth. 695 With Tree Discovery, a MR has to expose a depth that is incremented 696 from its parent's depth as receive in the TIO. In particular, a MR 697 might expose a depth which is incremented by more than one from its 698 parent's depth, in order to fit in its own administrative range. So 699 a depth of N does not mean that there is precisely N Mobile Routers 700 on the way, but at most N. 702 5.4 DRL entries states and stability 704 Attachment routers in the DRL may or may not be usable for roaming 705 depending on runtime conditions. The following states are defined: 707 Current This Attachment Router is used for roaming 709 Candidate This Attachment Router can be used for roaming. 711 Held-Up This Attachment Router can not be used till tree hop timer 712 elapses. This does not occur for a fixed Attachment Router that 713 does not send a TIO since the tree delay is null in that case. 715 Held-Down This Attachment Router can not be used till hold down timer 716 elapses. At the end of the hold-down period, the router is 717 removed from the DRL, and will be reinserted if it appears again 718 with a RA. 720 Collision This Attachment Router can not be used till its next RA. 722 5.4.1 Held-Up 724 This state is managed by the tree Hop timer, it serves 2 purposes: 726 Delay the reattachment of a sub-tree that has been forced to 727 detach. This allows to make sure that when a sub-tree has 728 detached, the Router Advertisement - Tree Information Option that 729 is initiated by the new clusterhead has spread down the sub-tree 730 so that two different trees have formed. 732 Limit Router Advertisement - Tree Information Option storms when 733 two trees collide. The idea is that between the nodes from tree A 734 that wish to move to tree B, those that see the highest place in 735 tree B will move first and advertise their new locations before 736 other nodes from tree A actually move. 738 A new tree is discovered upon a router advertisement message with or 739 without a Router Advertisement - Tree Information Option. The Mobile 740 Router joins the tree by selecting the source of the RA message as 741 its attachment router (default gateway) and propagating the TIO 742 accordingly. 744 When a new tree is discovered, the candidate Attachment Router that 745 advertises the new tree is placed in a held up state for the duration 746 of a Tree Hop timer. If the new Attachment Router is more preferable 747 than the current one, the Mobile Router expects to jump and becomes 748 unstable. 750 A Mobile Router that is unstable may discover other Attachment 751 Routers from the same new tree during the instability phase. It 752 needs to start a new Tree Hop timer for all these. The first timer 753 that elapses for a given new tree clears them all for that tree, 754 allowing the Mobile Router to jump to the highest position available 755 in the new tree. 757 The duration of the Tree Hop timer depends on the tree delay of the 758 new tree and on the depth of Attachment Router that triggers it: 760 (AR's depth + random) * AR's tree_delay (where 0 <= random < 1). It 761 is randomized in order to limit collisions and synchronizations. 763 5.4.2 Held-Down 765 When a router is 'removed' from the Default Router List, it is 766 actually held down for a hold down timer period, in order to prevent 767 flapping. This happens when an Attachment Router disappears (upon 768 expiration timer), and when an Attachment Router is tried but can not 769 reach the Home Agent (upon expiration of another Attachment Router, 770 or upon tree hop for that Attachment Router). 772 An Attachment Router that is held down is not considered for the 773 purpose of roaming. When the hold down timer elapses, the Attachment 774 Router is removed from the DRL. 776 5.4.3 Collision 778 A race condition occurs if 2 Mobile Routers send Router Advertisement 779 - Tree Information Option at the same time and wish to join each 780 other. In order to detect the situation, Mobile Routers time stamp 781 the sending of Router Advertisement - Tree Information Option. Any 782 Router Advertisement - Tree Information Option received within a 783 short media-dependant period introduces a risk. To divide the risk, 784 A 32bits extended preference is added in the TIO. The first byte is 785 the clusterhead preference, then the router own preference (default 786 is 0 for both), the remaining 16 bits is a boot time computed 787 random. 789 A Mobile Router that decides to join an Attachment Router will do so 790 between (Attachment Router depth) and (Attachment Router depth + 1) 791 times the Attachment Router tree delay. But since a Mobile Router is 792 unstable as soon as it receives the Router Advertisement - Tree 793 Information Option from the preferred Attachment Router, it will 794 restrain from sending a Router Advertisement - Tree Information 795 Option between the time it receives the RA and the time it actually 796 jumps. So the crossing of RA may only happen during the propagation 797 time between the Attachment Router and the Mobile Router, plus some 798 internal queuing and processing time within each machine. It is 799 expected that one tree delay normally covers that interval, but 800 ultimately it is up to the implementation and the configuration of 801 the Attachment Router to define the duration of risk window. 803 There is risk of a collision when a Mobile Router receives an RA, for 804 an other mobile router that is more preferable than the current 805 Attachment Router, within the risk window. In the face of a 806 potential collision, the Mobile Router with the lowest extended 807 preference processes the Router Advertisement - Tree Information 808 Option normally, while the router with the highest preference places 809 the other in collision state, does not start the tree hop timer, and 810 does not become instable. It is expected that next RAs between the 811 two will not cross anyway. 813 5.4.4 Instability 815 A Mobile Router is instable when it is prepared to move shortly to 816 another Attachment Router. This happens typically when the Mobile 817 Router has selected a more preferred candidate Attachment Router and 818 has to wait for the tree hop timer to elapse before roaming. 819 Instability may also occur when the current Attachment Router is lost 820 and the next best is still held up. Instability is resolved when the 821 tree hop timer of all the Attachment Router (s) causing instability 822 elapse. Such Attachment Router is changes state to Current or Held- 823 Down. 825 Instability is transient (in the order of tree hop timers). When a 826 Mobile Router is unstable, it MUST NOT send RAs with TIO. This 827 avoids loops when Mobile Router A wishes to attach to Mobile Router B 828 and Mobile Router B wishes to attach to Mobile Router A. Unless RA 829 cross (see Collision section), a Mobile Router receives TIO from 830 stable Attachment Routers, which do not plan to attach to itself, so 831 the Mobile Router can safely attach to them. 833 5.5 Legacy Routers 835 A legacy router sends its Router Advertisements without a TIO. 836 Consequently, a legacy router can be mistaken for a fixed Access 837 Router when it is placed within a nested NEMO structure, and defeat 838 the loop avoidance mechanism. Consequently, it is important for the 839 administrator to prevent address autoconfiguration by visiting Mobile 840 Routers from such a legacy router. 842 6. Directed Acyclic Graph Discovery 844 Tree Discovery builds trees, which are a specific form of a Directed 845 Acyclic Graph (DAG). In a more general Fashion, TD can be adapted to 846 form DAGs, oriented towards the clusterhead. This is DAG Discovery. 848 In Section 5.3, TD enables a given MR to expose a depth that is 849 incremented by more than one with regards to its parent. When it 850 does so, a MR can elect a number of alternate parents as feasible 851 successors. A feasible successor belongs to the same tree as the MR 852 parent, and has a depth that is less than that of the MR. 854 The links MR to feasible successors complete the tree as built by TD 855 into a DAG towards the clusterhead. The DAG enables alternate exit 856 paths for a multihomed Mobile Router. 858 7. IANA Considerations 860 Section 4.2. requires the definition of a new option to Neighbor 861 discovery [1] messages, the Router Advertisement - Tree Information 862 Option (RA-TIO). The Router Advertisement - Tree Information Option 863 has been assigned the value TBD within the numbering space for IPv6 864 Neighbor Discovery Option Formats. 866 8. Security Considerations 868 At the current level of this draft, the TIO bears the security level 869 of the RA and the link. Nothing is added to it. A deeper threat 870 analysis would be required to eventually propose additional security. 872 9. Changes 874 9.1 Changes from version 00 to 01 876 Added text on sub-tree mobility from the discussion with Marcelo. 878 Added text on nested legacy routers from the discussion with 879 Marcelo. 881 9.2 Changes from version 01 to 02 883 Improved text on instability 885 Changed the formula for the 4 bytes number used in collision 886 avoidance 888 9.3 Changes from version 02 to 03 890 Added suboptions for tree group, stable time and bandwidth. 892 Added administrative depth and increment by more than 1. 894 Added words on bidirectional check using ND. 896 Added DAG discovery. 898 10. Acknowledgments 900 The authors wish to thank Marco Molteni and Patrick Wetterwald 901 (cisco) for their participation to this design and the review of the 902 document, and Massimo Villari (university of Messina), for his early 903 work on simulation and research on the subject. This work is also 904 based on prior publications, in particular HMRA [8] by Hosik Cho and 905 Eun-Kyoung Paik from Seoul National University and other non IETF 906 publications coauthored with Thierry Ernst and Thomas Noel. Finally, 907 thanks to Marcelo Bagnulo Braun for his constructive review. 909 11. References 911 11.1 Normative Reference 913 [1] Narten, T., Nordmark, E., and W. Simpson, "Neighbor Discovery 914 for IP Version 6 (IPv6)", RFC 2461, December 1998. 916 [2] Thomson, S. and T. Narten, "IPv6 Stateless Address 917 Autoconfiguration", RFC 2462, December 1998. 919 [3] Johnson, D., Perkins, C., and J. Arkko, "Mobility Support in 920 IPv6", RFC 3775, June 2004. 922 [4] Devarapalli, V., Wakikawa, R., Petrescu, A., and P. Thubert, 923 "Network Mobility (NEMO) Basic Support Protocol", RFC 3963, 924 January 2005. 926 [5] Ernst, T., "Network Mobility Support Goals and Requirements", 927 draft-ietf-nemo-requirements-05 (work in progress), 928 October 2005. 930 [6] Ernst, T. and H. Lach, "Network Mobility Support Terminology", 931 draft-ietf-nemo-terminology-05 (work in progress), March 2006. 933 [7] Draves, R. and D. Thaler, "Default Router Preferences and More- 934 Specific Routes", draft-ietf-ipv6-router-selection-07 (work in 935 progress), January 2005. 937 11.2 Informative Reference 939 [8] Cho, H., "Hierarchical Mobile Router Advertisement for nested 940 mobile networks", draft-cho-nemo-hmra-00 (work in progress), 941 January 2004. 943 [9] Ng, C., "Analysis of Multihoming in Network Mobility Support", 944 draft-ietf-nemo-multihoming-issues-05 (work in progress), 945 February 2006. 947 Authors' Addresses 949 Pascal Thubert 950 Cisco Systems 951 Village d'Entreprises Green Side 952 400, Avenue de Roumanille 953 Batiment T3 954 Biot - Sophia Antipolis 06410 955 FRANCE 957 Phone: +33 4 97 23 26 34 958 Email: pthubert@cisco.com 960 Caroline Bontoux 961 Fortinet 962 Sophia Antipolis 963 Biot 06410 964 FRANCE 966 Email: cbontoux@fortinet.com 968 Nicolas Montavont 969 LSIIT - Univerity Louis Pasteur 970 Pole API, bureau C444 971 Boulevard Sebastien Brant 972 Illkirch 67400 973 FRANCE 975 Phone: (33) 3 90 24 45 87 976 Email: montavont@dpt-info.u-strasbg.fr 977 URI: http://www-r2.u-strasbg.fr/~montavont/ 979 Intellectual Property Statement 981 The IETF takes no position regarding the validity or scope of any 982 Intellectual Property Rights or other rights that might be claimed to 983 pertain to the implementation or use of the technology described in 984 this document or the extent to which any license under such rights 985 might or might not be available; nor does it represent that it has 986 made any independent effort to identify any such rights. Information 987 on the procedures with respect to rights in RFC documents can be 988 found in BCP 78 and BCP 79. 990 Copies of IPR disclosures made to the IETF Secretariat and any 991 assurances of licenses to be made available, or the result of an 992 attempt made to obtain a general license or permission for the use of 993 such proprietary rights by implementers or users of this 994 specification can be obtained from the IETF on-line IPR repository at 995 http://www.ietf.org/ipr. 997 The IETF invites any interested party to bring to its attention any 998 copyrights, patents or patent applications, or other proprietary 999 rights that may cover technology that may be required to implement 1000 this standard. Please address the information to the IETF at 1001 ietf-ipr@ietf.org. 1003 Disclaimer of Validity 1005 This document and the information contained herein are provided on an 1006 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 1007 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 1008 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 1009 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 1010 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 1011 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1013 Copyright Statement 1015 Copyright (C) The Internet Society (2006). This document is subject 1016 to the rights, licenses and restrictions contained in BCP 78, and 1017 except as set forth therein, the authors retain all their rights. 1019 Acknowledgment 1021 Funding for the RFC Editor function is currently provided by the 1022 Internet Society.