idnits 2.17.1 draft-ietf-homenet-prefix-assignment-07.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document date (June 15, 2015) is 3239 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) -- Obsolete informational reference (is this intentional?): RFC 3633 (Obsoleted by RFC 8415) Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group P. Pfister 3 Internet-Draft B. Paterson 4 Intended status: Standards Track Cisco Systems 5 Expires: December 17, 2015 J. Arkko 6 Ericsson 7 June 15, 2015 9 Distributed Prefix Assignment Algorithm 10 draft-ietf-homenet-prefix-assignment-07 12 Abstract 14 This document specifies a distributed algorithm for automatic prefix 15 assignment. Thus it provides an alternative to manual or centralized 16 prefix and address assignment techniques. Given a set of delegated 17 prefixes, it ensures that at most one prefix is assigned from each 18 delegated prefix to each link. Nodes may assign available prefixes 19 to the links they are directly connected to, or for other private 20 purposes. The algorithm eventually converges and ensures that all 21 assigned prefixes do not overlap. 23 Status of This Memo 25 This Internet-Draft is submitted in full conformance with the 26 provisions of BCP 78 and BCP 79. 28 Internet-Drafts are working documents of the Internet Engineering 29 Task Force (IETF). Note that other groups may also distribute 30 working documents as Internet-Drafts. The list of current Internet- 31 Drafts is at http://datatracker.ietf.org/drafts/current/. 33 Internet-Drafts are draft documents valid for a maximum of six months 34 and may be updated, replaced, or obsoleted by other documents at any 35 time. It is inappropriate to use Internet-Drafts as reference 36 material or to cite them other than as "work in progress." 38 This Internet-Draft will expire on December 17, 2015. 40 Copyright Notice 42 Copyright (c) 2015 IETF Trust and the persons identified as the 43 document authors. All rights reserved. 45 This document is subject to BCP 78 and the IETF Trust's Legal 46 Provisions Relating to IETF Documents 47 (http://trustee.ietf.org/license-info) in effect on the date of 48 publication of this document. Please review these documents 49 carefully, as they describe your rights and restrictions with respect 50 to this document. Code Components extracted from this document must 51 include Simplified BSD License text as described in Section 4.e of 52 the Trust Legal Provisions and are provided without warranty as 53 described in the Simplified BSD License. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 58 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 59 2.1. Subroutine Specific Terminology . . . . . . . . . . . . . 5 60 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 6 61 4. Algorithm Specification . . . . . . . . . . . . . . . . . . . 8 62 4.1. Prefix Assignment Algorithm Subroutine . . . . . . . . . 8 63 4.2. Overriding and Destroying Existing Assignments . . . . . 10 64 4.3. Other Events . . . . . . . . . . . . . . . . . . . . . . 12 65 5. Prefix Selection Considerations . . . . . . . . . . . . . . . 12 66 6. Implementation Capabilities and Node Behavior . . . . . . . . 14 67 7. Algorithm Parameters . . . . . . . . . . . . . . . . . . . . 15 68 8. Security Considerations . . . . . . . . . . . . . . . . . . . 16 69 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 70 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 17 71 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 17 72 11.1. Normative References . . . . . . . . . . . . . . . . . . 17 73 11.2. Informative References . . . . . . . . . . . . . . . . . 17 74 Appendix A. Static Configuration Example . . . . . . . . . . . . 17 75 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 18 77 1. Introduction 79 This document specifies a distributed algorithm for automatic prefix 80 assignment. The algorithm provides a generic alternative to 81 centralized (human or software based) approaches for network prefixes 82 and addresses assignment. Although it does not require to be 83 configured to operate properly, it supports custom configuration by 84 means of variable priority assignments, and can therefore be used in 85 fully autonomic as well as professionally managed networks. 87 Given a set of delegated prefixes, Nodes may assign available 88 prefixes to links they are directly connected to, or for their 89 private use. The algorithm ensures that the following assertions are 90 satisfied after a finite convergence period: 92 1. At most one prefix from each delegated prefix is assigned to each 93 link. 95 2. Assigned prefixes are non-overlapping (i.e., an assigned prefix 96 never includes another assigned prefix). 98 3. Assigned prefixes do not change in the absence of topology or 99 configuration changes. 101 In the rest of this document the two first conditions are referred to 102 as the correctness conditions of the algorithm while the third 103 condition is referred to as its convergence condition. 105 Each assignment has a priority specified by the Node making the 106 assignment, allowing for custom assignment policies. When multiple 107 Nodes assign different prefixes from the same delegated prefix to the 108 same link, or when multiple Nodes assign overlapping prefixes (to the 109 same link or to different links), the assignment with the greatest 110 priority is kept and other assignments are removed. 112 The prefix assignment algorithm requires that participating Nodes 113 share information through a flooding mechanism. If the flooding 114 mechanism ensures that all messages are propagated to all Nodes 115 within a given time window, the algorithm also ensures that all 116 assigned prefixes used for networking operations (e.g., host 117 configuration) remain unchanged, unless another Node assigns an 118 overlapping prefix with a higher assignment priority, or the topology 119 changes and renumbering cannot be avoided. 121 2. Terminology 123 In this document, the key words "MAY", "MUST, "MUST NOT", "OPTIONAL", 124 and "SHOULD", are to be interpreted as described in [RFC2119]. 126 This document makes use of the following terminology. The terms 127 defined here are ordered in such a way as to avoid forward 128 references, and therefore are not sorted alphabetically. 130 Node: An entity executing the algorithm specified in this document 131 and able to communicate with other Nodes using the Flooding 132 Mechanism. 134 Flooding Mechanism: A mechanism allowing participating Nodes to 135 reliably share information with all other participating Nodes. 137 Link: An object the distributed algorithm will assign prefixes to. 138 A Node may only assign prefixes to Links it is directly connected 139 to. A Link is either Shared or Private. 141 Shared Link: A Link multiple Nodes may be connected to. Most of 142 the time, a Shared Link is a multi-access link or point-to-point 143 link, virtual or physical, requiring prefixes to be assigned to 144 it. 146 Private Link: A Private Link is an abstract concept defined for the 147 sake of this document. It allows Nodes to make assignments for 148 their private use or delegation. For instance, every DHCPv6-PD 149 [RFC3633] requesting router MAY be considered as a different 150 Private Link. 152 Delegated Prefix: A prefix provided to the algorithm and used as a 153 prefix pool for Assigned Prefixes. 155 Node ID: A value identifying a given participating Node. The set 156 of identifiers MUST be strictly and totally ordered (e.g., using 157 the alphanumeric order). 159 Flooding Delay: A value which MUST be provided by the Flooding 160 Mechanism and SHOULD be a deterministic or likely upper bound on 161 the information propagation delay among participating Nodes. 163 Advertised Prefix: A prefix advertised by another Node and 164 delivered to the local Node by the Flooding Mechanism. It has an 165 Advertised Prefix Priority and, when assigned to a directly 166 connected Shared Link, is associated with that Shared Link. 168 Advertised Prefix Priority: A value that defines the priority of an 169 Advertised Prefix received from the Flooding Mechanism or a 170 published Assigned Prefix. Whenever multiple Advertised Prefixes 171 are conflicting (i.e., overlapping or from the same Delegated 172 Prefix and assigned to the same link), all Advertised Prefixes but 173 the one with the greatest priority will eventually be removed. In 174 case of a tie, the assignment advertised by the Node with the 175 greatest Node ID is kept and others are removed. In order to 176 ensure convergence, the range of priority values MUST have an 177 upper bound. 179 Assigned Prefix: A prefix included in a Delegated Prefix and 180 assigned to a Shared or Private Link. It represents a local 181 decision to assign a given prefix from a given Delegated Prefix to 182 a given Link. The algorithm ensures that there is never more than 183 one Assigned Prefix per Delegated Prefix and Link pair. When 184 destroyed, an Assigned Prefix is set as not applied, ceases to be 185 advertised, and is removed from the set of Assigned Prefixes. 187 Applied (Assigned Prefix): When an Assigned Prefix is applied, it 188 MAY be used (e.g., for host configuration, routing protocol 189 configuration, prefix delegation). When not applied, it MUST NOT 190 be used for any purpose outside of the prefix assignment 191 algorithm. Each Assigned Prefix is associated with a timer (Apply 192 Timer) used to apply the Assigned Prefix. An Assigned Prefix is 193 unapplied when destroyed. 195 Published (Assigned Prefix): The Assigned Prefix is advertised 196 through the Flooding Mechanism as assigned to its associated Link. 197 A published Assigned Prefix MUST have an Advertised Prefix 198 Priority. It will appear as an Advertised Prefix to other Nodes, 199 once received through the Flooding Mechanism. 201 Prefix Adoption: When an Advertised Prefix which does not conflict 202 with any other Advertised Prefix or published Assigned Prefix 203 stops being advertised, any other Node connected to the same Link 204 MAY, after some random delay, start advertising the same prefix. 205 This procedure is called adoption and provides seamless assignment 206 transfer from a Node to another, e.g., in case of Node failure. 208 Backoff Timer: Every Delegated Prefix and Link pair is associated 209 with a timer counting down to zero. It is used to reduce the 210 probability of colliding assignments made by multiple Nodes by 211 delaying the creation of new Assigned Prefixes or the 212 advertisement of adopted Assigned Prefixes by a random amount of 213 time. 215 Renumbering: Event occurring when an Assigned Prefix which was 216 applied is destroyed. Renumbering is undesirable as it usually 217 implies reconfiguring routers or hosts. 219 2.1. Subroutine Specific Terminology 221 In addition to the terms defined in Section 2, the subroutine 222 specified in Section 4 makes use of the following terms. 224 Current Assignment: For a given Delegated Prefix and Link, the 225 Current Assignment is the Assigned Prefix (if any) included in the 226 Delegated Prefix and assigned to the given Link by the Node 227 executing the algorithm. At some point in time, the Current 228 Assignment from different Nodes may differ, but the algorithm 229 ensures that eventually, all Nodes directly connected to a Shared 230 Link have the same Current Assignment for any given Delegated 231 Prefix. 233 Precedence: An Advertised Prefix takes precedence over an Assigned 234 Prefix if and only if one of the following conditions is met: 236 * The Assigned Prefix is not published. 238 * The Assigned Prefix is published and the Advertised Prefix 239 Priority from the Advertised Prefix is strictly greater than 240 the Advertised Prefix Priority from the Assigned Prefix. 242 * The Assigned Prefix is published, the priorities are identical, 243 and the Node ID from the Node advertising the Advertised Prefix 244 is strictly greater than the local Node ID. 246 Best Assignment: For a given Delegated Prefix and Link, the Best 247 Assignment is the unique Advertised Prefix (if any) that: 249 * Includes or is included in the Delegated Prefix (i.e., the 250 Advertised Prefix is a sub-prefix of the Delegated Prefix, or 251 the Delegated Prefix is a sub-prefix of the Advertised Prefix). 253 * Is assigned on the given Link. 255 * Has the greatest Advertised Prefix Priority among Advertised 256 Prefixes fulfilling the two preceding conditions (and, in case 257 of a tie, the prefix advertised by the Node with the greatest 258 Node ID among all prefixes with greatest priority). 260 * Takes precedence over the Current Assignment associated with 261 the same Link and Delegated Prefix (if any). 263 Valid (Assigned Prefix): An Assigned Prefix is valid if and only if 264 the following two conditions are met: 266 * No Advertised Prefix including or included in the Assigned 267 Prefix takes precedence over the Assigned Prefix. 269 * No Advertised Prefix including or included in the same 270 Delegated Prefix as the Assigned Prefix and assigned to the 271 same Link takes precedence over the Assigned Prefix. 273 3. Applicability Statement 275 Each Node MUST have a set of non-overlapping Delegated Prefixes 276 (i.e., which do not include each other). This set MAY change over 277 time and be different from one Node to another at some point, but 278 Nodes MUST eventually have the same set of disjoint Delegated 279 Prefixes. 281 Given this set of disjoint Delegated Prefixes, Nodes may assign 282 available prefixes from each Delegated Prefix to the Links they are 283 directly connected to. The algorithm ensures that at most one prefix 284 from a given Delegated Prefix is assigned to any given Link. 286 The algorithm can be applied to any address space and can be used to 287 manage multiple address spaces simultaneously. For instance, an 288 implementation can make use of IPv4-mapped IPv6 addresses [RFC4291] 289 in order to manage both IPv4 and IPv6 prefix assignment using a 290 single prefix space. 292 The algorithm supports dynamically changing topologies: 294 o Nodes may join or leave the set of participating Nodes. 296 o Nodes may join or leave Links. 298 o Links may be joined or split. 300 All Nodes MUST run a common Flooding Mechanism in order to share 301 published Assigned Prefixes. The set of participating Nodes is 302 defined as the set of Nodes participating in the Flooding Mechanism. 304 The Flooding Mechanism MUST: 306 o Provide a way to flood Assigned Prefixes assigned to a directly 307 connected Link along with their respective Advertised Prefix 308 Priority and the Node ID of the Node which is advertising them. 310 o Specify whether an Advertised Prefix was assigned to a directly 311 connected Shared Link, and if so, on which one. 313 o Provide a Flooding Delay value, which SHOULD represent a 314 deterministic or likely upper bound on the information propagation 315 delay among participating Nodes. Whenever the Flooding Mechanism 316 is unable to adhere to the provided Flooding Delay, renumbering 317 may happen. As such a delay often depends on the size of the 318 network, it MAY change over time and MAY be different from one 319 Node to another. Furthermore, the process of selecting this value 320 is subject to a tradeoff between convergence speed and lower 321 renumbering probability (e.g., the value 0 may be used when 322 renumbering is harmless), and is therefore out of scope of this 323 document. 325 The algorithm ensures that whenever the Flooding Delay is provided 326 and respected, and in the absence of any topology change or Delegated 327 Prefix removal, renumbering only happens when a Node deliberately 328 overrides an existing assignment. 330 Each Node MUST have a Node ID. Node IDs MAY change over time and be 331 the same on multiple Nodes at some point, but each Node MUST 332 eventually have a Node ID which is unique among the set of 333 participating Nodes. 335 4. Algorithm Specification 337 This section specifies the behavior of Nodes implementing the prefix 338 assignment algorithm. The terms 'Current Assignment', 'Precedence', 339 'Best Assignment' and 'Valid' are used as defined in Section 2.1. 341 4.1. Prefix Assignment Algorithm Subroutine 343 This section specifies the prefix assignment algorithm subroutine. 344 It is defined for a given Delegated Prefix and Link pair and takes a 345 BackoffTriggered boolean as parameter (indicating whether the 346 subroutine execution was triggered by the Backoff Timer or by another 347 event). 349 For a given Delegated Prefix and Link pair, the subroutine MUST be 350 run with the BackoffTriggered boolean set to false whenever: 352 o An Advertised Prefix including or included in the considered 353 Delegated Prefix is added or removed. 355 o An Assigned Prefix included in the considered Delegated Prefix and 356 associated with a different Link than the considered Link was 357 destroyed, while there is no Current Assignment associated with 358 the given pair. This case MAY be ignored if the creation of a new 359 Assigned Prefix associated with the considered pair is not 360 desired. 362 o The considered Delegated Prefix is added. 364 o The considered Link is added. 366 o The Node ID is modified. 368 Furthermore, for a given Delegated Prefix and Link pair, the 369 subroutine MUST be run with the BackoffTriggered boolean set to true 370 whenever: 372 o The Backoff Timer associated with the considered Delegated Prefix 373 and Link pair fires while there is no Current Assignment 374 associated with the given pair. 376 When such an event occurs, a Node MAY delay the execution of the 377 subroutine instead of executing it immediately, e.g., while receiving 378 an update from the Flooding Mechanism, or for security reasons (see 379 Section 8). Even if other events occur in the meantime, the 380 subroutine MUST be run only once. It is also assumed that, whenever 381 one of these events is the Backoff Timer firing, the subroutine is 382 executed with the BackoffTriggered boolean set to true. 384 In order to execute the subroutine for a given Delegated Prefix and 385 Link pair, first look for the Best Assignment and Current Assignment 386 associated with the Delegated Prefix and Link pair, then execute the 387 corresponding case: 389 1. If there is no Best Assignment and no Current Assignment: Decide 390 whether the creation of a new assignment for the given Delegated 391 Prefix and Link pair is desired (As any result would be valid, 392 the process of making this decision is out of the scope of this 393 document) and do the following: 395 * If it is not desired, stop the execution of the subroutine. 397 * Else if the Backoff Timer is running, stop the execution of 398 the subroutine. 400 * Else if the BackoffTriggered boolean is set to false, set the 401 Backoff Timer to some random delay between ADOPT_MAX_DELAY and 402 BACKOFF_MAX_DELAY (see Section 7) and stop the execution of 403 the subroutine. 405 * Else, continue the execution of the subroutine. 407 Select a prefix for the new assignment (see Section 5 for 408 guidance regarding prefix selection). This prefix MUST be 409 included in or be equal to the considered Delegated Prefix and 410 MUST NOT include or be included in any Advertised Prefix. If a 411 suitable prefix is found, use it to create a new Assigned Prefix: 413 * Assigned to the considered Link. 415 * Set as not applied. 417 * The Apply Timer set to '2 * Flooding Delay'. 419 * Published with some selected Advertised Prefix Priority. 421 2. If there is a Best Assignment but no Current Assignment: Cancel 422 the Backoff Timer and use the prefix from the Best Assignment to 423 create a new Assigned Prefix: 425 * Assigned to the considered Link. 427 * Set as not applied. 429 * The Apply Timer set to '2 * Flooding Delay'. 431 * Set as not published. 433 3. If there is a Current Assignment but no Best Assignment: 435 * If the Current Assignment is not valid, destroy it, and 436 execute the subroutine again with the BackoffTriggered boolean 437 set to false. 439 * If the Current Assignment is valid and published, stop the 440 execution of the subroutine. 442 * If the Current Assignment is valid and not published, the Node 443 MUST either: 445 + Adopt the prefix by canceling the Apply Timer and set the 446 Backoff Timer to some random delay between 0 and 447 ADOPT_MAX_DELAY (see Section 7). This procedure is used to 448 avoid renumbering when the Node advertising the prefix left 449 the Shared Link. 451 + Destroy it and go to case 1. 453 4. If there is a Current Assignment and a Best Assignment: 455 * Cancel the Backoff Timer. 457 * If the two prefixes are identical, set the Current Assignment 458 as not published. If the Current Assignment is not applied 459 and the Apply Timer is not set, set the Apply Timer to '2 * 460 Flooding Delay'. 462 * If the two prefixes are not identical, destroy the Current 463 Assignment and go to case 2. 465 When the prefix assignment algorithm subroutine requires an 466 assignment to be created or adopted, any Advertised Prefix Priority 467 value can be used. Other documents MAY provide restrictions over 468 this value depending on the context the algorithm is operating in, or 469 leave it as implementation-specific. 471 4.2. Overriding and Destroying Existing Assignments 473 In addition to the behaviors specified in Section 4.1, the following 474 procedures MAY be used in order to provide additional behavior 475 options (Section 6): 477 Overriding Existing Assignments: For any given Link and Delegated 478 Prefix, a Node MAY create a new Assigned Prefix using a chosen 479 prefix and Advertised Prefix Priority such that: 481 * The chosen prefix is included in or is equal to the considered 482 Delegated Prefix. 484 * The Current Assignment, if any, as well as all existing 485 Assigned Prefixes which include or are included inside the 486 chosen prefix, are destroyed. 488 * It is not applied. 490 * The Apply Timer is set to '2 * Flooding Delay'. 492 * It is published. 494 * The Advertised Prefix Priority is greater than the Advertised 495 Prefix Priority from all Advertised Prefixes which include or 496 are included in the chosen prefix. 498 * The Advertised Prefix Priority is greater than the Advertised 499 Prefix Priority from all Advertised Prefixes which include or 500 are included in the considered Delegated Prefix and are 501 assigned to the considered Link. 503 In order to ensure algorithm convergence: 505 * Such overriding assignments MUST NOT be created unless there 506 was a change in the Node configuration, a Link was added, or an 507 Advertised Prefix was added or removed. 509 * The chosen Advertised Prefix Priority for the new Assigned 510 Prefix SHOULD be greater than all priorities from the destroyed 511 Assigned Prefixes. If not, simple topologies with only two 512 Nodes may not converge. Nodes which do not adhere to this rule 513 MUST implement a mechanism which detects whether the 514 distributed algorithm does not converge and, whenever this 515 would happen, stop creating overriding Assigned Prefixes which 516 do not adhere to this rule. The specifications for such safety 517 procedures are out of the scope of this document. 519 Removing an Assigned Prefix: A Node MAY destroy any Assigned Prefix 520 which is published. Such an event reflects the desire of a Node 521 to not assign a prefix from a given Delegated Prefix to a given 522 Link anymore. In order to ensure algorithm convergence, such a 523 procedure MUST NOT be executed unless there was a change in the 524 Node configuration. Furthermore, whenever an Assigned Prefix is 525 destroyed in this way, the prefix assignment algorithm subroutine 526 MUST be run for the Delegated Prefix and Link pair associated with 527 the destroyed Assigned Prefix. 529 The two procedures specified in this section are OPTIONAL. They 530 could be used for various purposes, e.g., for providing custom prefix 531 assignment configuration or reacting to prefix space exhaustion (by 532 overriding short Assigned Prefixes and assigning longer ones). 534 4.3. Other Events 536 When the Apply Timer fires, the associated Assigned Prefix MUST be 537 applied. 539 When the Backoff Timer associated with a given Delegated Prefix and 540 Link pair fires while there is a Current Assignment associated with 541 the same pair, the Current Assignment MUST be published with some 542 associated Advertised Prefix Priority and, if the prefix is not 543 applied, the Apply Timer MUST be set to '2 * Flooding Delay'. 545 When a Delegated Prefix is removed from the set of Delegated Prefixes 546 (e.g., when the Delegated Prefix expires), all Assigned Prefixes 547 included in the removed Delegated Prefix MUST be destroyed. 549 When one Delegated Prefix is replaced by another one that includes or 550 is included in the deleted Delegated Prefix, all Assigned Prefixes 551 which were included in the deleted Delegated Prefix but are not 552 included in the added Delegated Prefix MUST be destroyed. Others MAY 553 be kept. 555 When a Link is removed, all Assigned Prefixes assigned to that Link 556 MUST be destroyed. 558 5. Prefix Selection Considerations 560 When the prefix assignment algorithm subroutine specified in 561 Section 4.1 requires a new prefix to be selected, the prefix MUST be 562 selected either: 564 o Among prefixes included in the considered Delegated Prefix which 565 were previously assigned and applied on the considered Link. For 566 that purpose, Applied Prefixes may be stored in stable storage 567 along with their associated Link. 569 o Randomly, picked in a set of at least RANDOM_SET_SIZE (see 570 Section 7) prefixes included in the considered Delegated Prefix 571 and not including or included in any Assigned or Advertised 572 Prefix. If less than RANDOM_SET_SIZE candidates are found, the 573 prefix MUST be picked among all candidates. 575 o Based on some custom selection process specified in the 576 configuration. 578 A simple implementation MAY randomly pick the prefix among all 579 available prefixes, but this strategy is inefficient in terms of 580 address space use as a few long prefixes may exhaust the pool of 581 available short prefixes. 583 The rest of this section describes a more efficient approach which 584 MAY be applied any time a Node needs to pick a prefix for a new 585 assignment. The two following definitions are used: 587 Available prefix: The prefix of the form Prefix/PrefixLength is 588 available if and only if it satisfies the three following 589 conditions: 591 * It is included in the considered Delegated Prefix. 593 * It does not include and is not included in any Assigned or 594 Advertised Prefix. 596 * It is equal to the considered Delegated Prefix or Prefix/ 597 (PrefixLength-1) includes an Assigned or Advertised Prefix. 599 Candidate prefix: A prefix of desired length which is included in 600 or is equal to an available prefix. 602 The procedure described in this section takes the three following 603 criteria into account: 605 Prefix Stability: In some cases, it is desirable that the selected 606 prefix should remain the same across executions and reboots. For 607 this purpose, prefixes previously applied on the Link or pseudo- 608 random prefixes generated based on Node- and Link-specific values 609 may be considered. 611 Randomness: When no stored or pseudo-random prefix is chosen, a 612 prefix may be randomly picked among RANDOM_SET_SIZE candidates of 613 desired length. If less than RANDOM_SET_SIZE candidates can be 614 found, the prefix is picked among all candidates. 616 Addressing-space usage efficiency: In the process of assigning 617 prefixes, a small set of badly chosen long prefixes may prevent 618 any shorter prefix from being assigned. For this reason, the set 619 of RANDOM_SET_SIZE candidates is created from available prefixes 620 with longest prefix lengths and, in case of a tie, preferring 621 numerically small prefix values. 623 When executing the procedure, do as follows: 625 1. For each prefix stored in stable storage, check if the prefix is 626 included in or equal to an available prefix. If so, pick that 627 prefix and stop. 629 2. For each prefix length, count the number of available prefixes of 630 the given length. 632 3. If the desired prefix length was not specified, select one. The 633 available prefixes count computed previously may be used to help 634 pick a prefix length such that: 636 * There is at least one candidate prefix. 638 * The prefix length is chosen large enough to not exhaust the 639 address space. 641 Let N be the chosen prefix length. 643 4. Iterate over available prefixes starting with prefixes of length 644 N down to length 0 and create a set of RANDOM_SET_SIZE candidate 645 prefixes of length exactly N included in or equal to available 646 prefixes. The end goal here is to create a set of 647 RANDOM_SET_SIZE candidate prefixes of length N included in a set 648 of available prefixes of maximized prefix length. In case of a 649 tie, smaller prefix values (as defined by the bit-wise 650 lexicographical order) are preferred. 652 5. Generate a set of prefixes of desired length, which are pseudo- 653 randomly chosen based on Node- and Link-specific values. For 654 each pseudo-random prefix, check if the prefix is equal to a 655 candidate prefix. If so, pick that prefix and stop. 657 6. Choose a random prefix from the set of selected candidates. 659 The complexity of this procedure is equivalent to the complexity of 660 iterating over available prefixes. Such operation may be 661 accomplished in linear time, e.g., by storing Advertised and Assigned 662 Prefixes in a binary trie. 664 6. Implementation Capabilities and Node Behavior 666 Implementations of the prefix assignment algorithm may vary from very 667 basic to highly customizable, enabling different types of fully 668 interoperable behaviors. The three following behaviors are given as 669 examples: 671 Listener: The Node only acts upon assignments made by other Nodes, 672 i.e, it never creates new assignments nor adopts existing ones. 674 Such behavior does not require the implementation of the 675 considerations specified in Section 5 or Section 4.2. The Node 676 never checks the validity of existing assignments, which makes 677 this behavior particularly suited to lightweight devices which can 678 rely on more capable neighbors to make assignments on directly 679 connected Shared Links. 681 Basic: The Node is capable of assigning new prefixes or adopting 682 prefixes which do not conflict with any other existing assignment. 683 Such behavior does not require the implementation of the 684 considerations specified in Section 4.2. It is suited to 685 situations where there is no preference over which prefix should 686 be assigned to which Link, and there is no priority between 687 different Links. 689 Advanced: The Node is capable of assigning new prefixes, adopting 690 existing ones, making overriding assignments and destroying 691 existing ones. Such behavior requires the implementation of the 692 considerations specified in Section 5 and Section 4.2. It is 693 suited when the administrator desires some particular prefix to be 694 assigned on a given Link, or some Link to be assigned prefixes 695 with a greater priority when there are not enough prefixes 696 available for all Links. 698 Note that if all Nodes directly connected to some Link are listener 699 Nodes or none of these Nodes are willing to make an assignment from a 700 given Delegated Prefix to the given Link, no prefix from the given 701 Delegated Prefix will ever be assigned to the Link (and such existing 702 prefixes will be removed). This situation may be detected by 703 watching whether no prefix from a given Delegated Prefix has been 704 assigned to the Link for longer than BACKOFF_MAX_DELAY plus the 705 Flooding Delay. 707 7. Algorithm Parameters 709 This document does not provide values for ADOPT_MAX_DELAY, 710 BACKOFF_MAX_DELAY and RANDOM_SET_SIZE. The algorithm ensures 711 convergence and correctness for any chosen values, even when these 712 are different from Node to Node. They MAY be adjusted depending on 713 the context, providing a tradeoff between convergence time, efficient 714 addressing, reduced control traffic (generated by the Flooding 715 Mechanism), and low collision probability. 717 ADOPT_MAX_DELAY (respectively BACKOFF_MAX_DELAY) represents the 718 maximum backoff time a Node may wait before adopting an assignment 719 (respectively making a new assignment). BACKOFF_MAX_DELAY MUST be 720 greater than or equal to ADOPT_MAX_DELAY. The greater 721 ADOPT_MAX_DELAY and (BACKOFF_MAX_DELAY - ADOPT_MAX_DELAY), the lower 722 the collision probability and the lesser the amount of control 723 traffic, but the greater the convergence time. 725 RANDOM_SET_SIZE represents the desired size of the set a random 726 prefix will be picked from. The greater RANDOM_SET_SIZE, the better 727 the convergence time and the lower the collision probability, but the 728 worse the addressing-space usage efficiency. 730 8. Security Considerations 732 The prefix assignment algorithm functions on top of two distinct 733 mechanisms, the Flooding Mechanism and the Node ID assignment 734 mechanism. 736 An attacker able to publish Advertised Prefixes through the 737 Flooding Mechanism may perform the following attacks: 739 * Publish a single overriding assignment for a whole Delegated 740 Prefix or for the whole address space, thus preventing any Node 741 from assigning prefixes to Links. 743 * Quickly publish and remove Advertised Prefixes, generating 744 traffic at the Flooding Mechanism layer and causing multiple 745 executions of the prefix assignment algorithm in all 746 participating Nodes. 748 * Publish and remove Advertised Prefixes in order to prevent the 749 convergence of the algorithm. 751 An attacker able to prevent other Nodes from accessing a portion 752 or the whole set of Advertised Prefixes may compromise the 753 correctness of the algorithm. 755 An attacker able to cause repetitive Node ID changes may cause 756 traffic to be generated in the Flooding Mechanism and multiple 757 executions of the prefix assignment algorithm in all participating 758 Nodes. 760 An attacker able to publish Advertised Prefixes using a Node ID 761 used by another Node may prevent the correctness and convergence 762 of the algorithm or cause the result to violate the correctness 763 conditions. 765 Whenever the security of the Flooding Mechanism and Node ID 766 assignment mechanism cannot be ensured, the convergence of the 767 algorithm may be prevented. In environments where such attacks may 768 be performed, the execution of the prefix assignment algorithm 769 subroutine SHOULD be rate limited, as specified in Section 4.1. 771 9. IANA Considerations 773 This document has no actions for IANA. 775 10. Acknowledgments 777 The authors would like to thank those who participated in the 778 previous document's version development as well as the present one. 779 In particular, the authors would like to thank Tim Chown, Fred Baker, 780 Mark Townsley, Lorenzo Colitti, Ole Troan, Ray Bellis, Markus 781 Stenberg, Wassim Haddad, Joel Halpern, Samita Chakrabarti, Michael 782 Richardson, Anders Brandt, Erik Nordmark, Laurent Toutain, Ralph 783 Droms, Acee Lindem and Steven Barth for interesting discussions and 784 document review. 786 11. References 788 11.1. Normative References 790 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 791 Requirement Levels", BCP 14, RFC 2119, March 1997. 793 11.2. Informative References 795 [RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing 796 Architecture", RFC 4291, February 2006. 798 [RFC3633] Troan, O. and R. Droms, "IPv6 Prefix Options for Dynamic 799 Host Configuration Protocol (DHCP) version 6", RFC 3633, 800 December 2003. 802 Appendix A. Static Configuration Example 804 This section describes an example of how custom configuration of the 805 prefix assignment algorithm may be implemented. 807 The Node configuration is specified as a finite set of rules. A rule 808 is defined as: 810 o A prefix to be used. 812 o A Link on which the prefix may be assigned. 814 o An Assigned Prefix Priority (smallest possible Assigned Prefix 815 Priority if the rule may not override other Assigned Prefixes). 817 o A rule priority (0 if the rule may not override existing 818 Advertised Prefixes). 820 In order to ensure the convergence of the algorithm, the Assigned 821 Prefix Priority MUST be an increasing function (not necessarily 822 strictly) of the configuration rule priority (i.e., the greater is 823 the configuration rule priority, the greater the Assigned Prefix 824 Priority must be). 826 Each Assigned Prefix is associated with a rule priority. Assigned 827 Prefixes which are created as specified in Section 4.1 are given a 828 rule priority of 0. 830 Whenever the configuration is changed or the prefix assignment 831 algorithm subroutine is run: For each Link/Delegated Prefix pair, 832 look for the configuration rule with the greatest configuration rule 833 priority such that: 835 o The prefix specified in the configuration rule is included in the 836 considered Delegated Prefix. 838 o The Link specified in the configuration rule is the considered 839 Link. 841 o All the Assigned Prefixes which would need to be destroyed in case 842 a new Assigned Prefix is created from that configuration rule (as 843 specified in Section 4.2) have an associated rule priority which 844 is strictly lower than the one of the considered configuration 845 rule. 847 o The assignment would be valid when published with an Advertised 848 Prefix Priority equal to the one specified in the configuration 849 rule. 851 If a rule is found, a new Assigned Prefix is created based on that 852 rule as specified in Section 4.2. The new Assigned Prefix is 853 associated with the Advertised Prefix Priority and the rule priority 854 specified in the considered configuration rule. 856 Note that the use of rule priorities ensures the convergence of the 857 algorithm. 859 Authors' Addresses 861 Pierre Pfister 862 Cisco Systems 863 Paris 864 France 866 Email: pierre.pfister@darou.fr 867 Benjamin Paterson 868 Cisco Systems 869 Paris 870 France 872 Email: paterson.b@gmail.com 874 Jari Arkko 875 Ericsson 876 Jorvas 02420 877 Finland 879 Email: jari.arkko@piuha.net