RFC 7695

Distributed Prefix Assignment Algorithm

📅 published November 2015, from ietf

Distributed Prefix Assignment Algorithm 🎀

Okay bestie, first the tea ☕. This is RFC 7695, a Standards Track doc from the Internet Engineering Task Force (IETF), published in November 2015 with ISSN 2070-1721. It was written by P. Pfister and B. Paterson from Cisco Systems, plus J. Arkko from Ericsson 💅. It doesn't list anything it obsoletes or updates, so it's standing on its own. 🧚

Abstract ✨

Okay so this doc is all about a distributed algorithm for splitting up a set of prefixes so that sub-prefixes get assigned automatically, and every one is unique and non-overlapping 🦋. It works together with a protocol that floods information around to a group of participating nodes, and once that's in place, you can automate prefix configuration across a whole network. It's giving automation, no cap 🤖.

Status of This Memo 📜

This is an Internet Standards Track document, bestie 💜.

It's a product of the IETF, which means it represents the consensus of the IETF community. It got public review and was approved for publication by the Internet Engineering Steering Group (IESG). If you want more on Internet Standards, check out Section 2 of RFC 5741 🌸.

For info on the current status of this document, any errata, and how to send feedback, go to http://www.rfc-editor.org/info/rfc7695 🔗.

Copyright (c) 2015 IETF Trust and the persons identified as the document authors. All rights reserved ✨.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents, which you can find at http://trustee.ietf.org/license-info, as they stand on the date this document was published. Please read these carefully, because they spell out your rights and restrictions for this document 📖. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions, and they're provided without warranty as described in the Simplified BSD License 🫶.

Table of Contents 🗂️

1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
2.  Definitions . . . . . . . . . . . . . . . . . . . . . . . . .   3
  2.1.  Subroutine-Specific Terminology . . . . . . . . . . . . .   6
3.  Applicability Statement . . . . . . . . . . . . . . . . . . .   7
4.  Algorithm Specification . . . . . . . . . . . . . . . . . . .   9
  4.1.  Prefix Assignment Algorithm Subroutine  . . . . . . . . .   9
  4.2.  Overriding and Destroying Existing Assignments  . . . . .  12
  4.3.  Other Events  . . . . . . . . . . . . . . . . . . . . . .  13
5.  Prefix Selection Considerations . . . . . . . . . . . . . . .  14
6.  Implementation Capabilities and Node Behavior . . . . . . . .  16
7.  Algorithm Parameters  . . . . . . . . . . . . . . . . . . . .  17
8.  Security Considerations . . . . . . . . . . . . . . . . . . .  17
11. References  . . . . . . . . . . . . . . . . . . . . . . . . .  18
  11.1.  Normative References . . . . . . . . . . . . . . . . . .  18
  11.2.  Informative References . . . . . . . . . . . . . . . . .  18
Appendix A.  Static Configuration Example . . . . . . . . . . . .  19
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  20
Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  20

1. Introduction ✨

Okay bestie, this document specifies a distributed algorithm for automatic prefix assignment 🦋. It's a generic alternative to centralized approaches for assigning network prefixes and addresses, whether that central control is done by a human or by software 💅. It doesn't have to be configured to work properly, but it does support custom configuration through variable priority assignments. So it can run in fully autonomic networks as well as in configured ones, which is iconic 👑.

This doc focuses on the algorithm itself. Context-specific stuff, like how you pick a prefix value and length when making a new assignment, is out of scope 🙈.

The algorithm uses a flooding mechanism that lets participating nodes advertise prefixes. Those prefixes can be assigned to the links they're directly connected to, or used for other purposes, like private assignment or prefix delegation 🌸. So advertising a prefix does two jobs. First, it's a claim that the prefix is in use, which means no other node can advertise an overlapping prefix unless that node has a greater priority 🔥. Second, it's how other nodes find out which prefixes have been assigned to the links they're directly connected to 🫶.

The algorithm takes a set of delegated prefixes and makes sure the following three things are true after a finite convergence period ⏳:

  1. At most one prefix from each delegated prefix is assigned to each link.
  2. Assigned prefixes are non-overlapping (i.e., an assigned prefix never includes another assigned prefix).
  3. Assigned prefixes do not change in the absence of topology or configuration changes.

In the rest of this doc, the first two conditions are called the correctness conditions of the algorithm, and the third one is called its convergence condition 🧠.

Every assignment has a priority set by the node making it, which allows for custom assignment policies 💖. When multiple nodes assign different prefixes from the same delegated prefix to the same link, or when multiple nodes assign overlapping prefixes (to the same link or to different links), the assignment with the greatest priority is kept and the others are removed 💀.

The prefix assignment algorithm needs participating nodes to share information through a flooding mechanism. If the flooding mechanism makes sure every message reaches every node within a given time window, the algorithm also makes sure all assigned prefixes used for networking operations (like host configuration) stay the same. The exception is when another node assigns an overlapping prefix with a higher assignment priority, or when the topology changes and renumbering can't be avoided 🌈.

2. Definitions 💅

Okay, important bit: in this doc, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" are to be interpreted as described in [RFC2119] 📌.

This doc uses the terminology below. The terms are ordered so they avoid forward references, so they aren't sorted alphabetically 🧚.

Node: An entity that runs the algorithm in this doc and can talk to other Nodes using the Flooding Mechanism 🤝.

Flooding Mechanism: A mechanism that lets participating Nodes reliably share information with all the other participating Nodes 📣.

Link: An object that the distributed algorithm assigns prefixes to. A Node can only assign prefixes to Links it's directly connected to. A Link is either Shared or Private 🔗.

Shared Link: A Link that multiple Nodes can be connected to. Most of the time, a Shared Link is a multi-access or point-to-point link, virtual or physical, that needs prefixes assigned to it 🌸.

Private Link: A Private Link is an abstract concept defined just for this doc. It lets Nodes make assignments for their private use or delegation. For example, every DHCPv6-PD [RFC3633] requesting router can be seen as a different Private Link 🦋.

Delegated Prefix: A prefix given to the algorithm and used as a prefix pool for Assigned Prefixes 🍓.

Node ID: A value that identifies a given participating Node. The set of identifiers MUST be strictly and totally ordered (e.g., using the alphanumeric order). The mechanism used to assign Node IDs, whether manual or automated, is out of scope for this document 🔢.

Flooding Delay: A value that MUST be provided by the Flooding Mechanism, and it SHOULD be a deterministic or likely upper bound on the information propagation delay among participating Nodes ⏱️.

Advertised Prefix: A prefix advertised by another Node and delivered to the local Node by the Flooding Mechanism. It has an Advertised Prefix Priority and, when it's assigned to a directly connected Shared Link, it's associated with that Shared Link 📬.

Advertised Prefix Priority: A value that defines the priority of an Advertised Prefix received from the Flooding Mechanism or a published Assigned Prefix. Whenever multiple Advertised Prefixes conflict (i.e., they overlap or come from the same Delegated Prefix and are assigned to the same link), all of them except the one with the greatest priority will eventually be removed. If there's a tie, the assignment advertised by the Node with the greatest Node ID is kept, and the others are removed. To make sure convergence happens, the range of priority values MUST have an upper bound 🏆.

Assigned Prefix: A prefix included in a Delegated Prefix and assigned to a Shared or Private Link. It represents a local decision to assign a given prefix from a given Delegated Prefix to a given Link. The algorithm makes sure there's never more than one Assigned Prefix per Delegated Prefix and Link pair. When it's destroyed, an Assigned Prefix is set as not applied, stops being advertised, and gets removed from the set of Assigned Prefixes 💜.

Applied (Assigned Prefix): When an Assigned Prefix is applied, it MAY be used (e.g., for host configuration, routing protocol configuration, prefix delegation). When it's not applied, it MUST NOT be used for any purpose outside of the prefix assignment algorithm. Each Assigned Prefix is associated with a timer (Apply Timer) that's used to apply the Assigned Prefix. An Assigned Prefix is unapplied when it's destroyed ⚡.

Published (Assigned Prefix): The Assigned Prefix is advertised through the Flooding Mechanism as assigned to its associated Link. A published Assigned Prefix MUST have an Advertised Prefix Priority. Other Nodes see it as an Advertised Prefix once they get it from the Flooding Mechanism 📢.

Destroy (an Assigned Prefix): A local action that removes an Assigned Prefix from the set of Assigned Prefixes. If it was applied, the prefix is unapplied. If it was published, the prefix stops being advertised through the Flooding Mechanism 🗑️.

Prefix Adoption: When an Advertised Prefix that doesn't conflict with any other Advertised Prefix or published Assigned Prefix stops being advertised, any other Node connected to the same Link may, after a random delay, start advertising that same prefix. This is called adoption, and it gives seamless assignment transfer from one Node to another, like when a Node fails 🦋.

Backoff Timer: Every Delegated Prefix and Link pair is associated with a timer that counts down to zero. By delaying the creation of new Assigned Prefixes, or the advertisement of adopted Assigned Prefixes, by a random amount of time, it lowers the chance of colliding assignments made by multiple Nodes 🎲.

Renumbering: An event that happens when an Assigned Prefix that was applied gets destroyed. Renumbering is undesirable, because it usually means reconfiguring routers or hosts 🙃.

2.1. Subroutine-Specific Terminology ✨

bestie, these are the extra terms for the subroutine in Section 4, on top of everything from Section 2 🫶

Current Assignment: for a given Delegated Prefix and Link, this is the Assigned Prefix (if there is one) that's inside that Delegated Prefix and assigned to that Link by the Node running the algorithm. 🦋 Different Nodes can have different Current Assignments for a while, but the algorithm gets them all to agree eventually, so every Node directly connected to a Shared Link ends up with the same Current Assignment for any given Delegated Prefix. Main character glow-up 💅

Precedence: an Advertised Prefix takes precedence over an Assigned Prefix if and only if one of these is true:

  • The Assigned Prefix is not published.
  • The Assigned Prefix is published, and the Advertised Prefix Priority of the Advertised Prefix is strictly greater than the Advertised Prefix Priority of the Assigned Prefix.
  • The Assigned Prefix is published, the priorities are identical, and the Node ID of the Node advertising the Advertised Prefix is strictly greater than the local Node ID.

Best Assignment: for a given Delegated Prefix and Link, the Best Assignment is the one unique Advertised Prefix (if there is one) that:

  • Includes or is included in the Delegated Prefix. So the Advertised Prefix is a sub-prefix of the Delegated Prefix, or the Delegated Prefix is a sub-prefix of the Advertised Prefix. 🌸
  • Is assigned on the given Link.
  • Has the greatest Advertised Prefix Priority among the Advertised Prefixes that meet the two conditions above. If there's a tie, it's the prefix advertised by the Node with the greatest Node ID among all the prefixes with the greatest priority. Tiebreaker drama 😭
  • Takes precedence over the Current Assignment associated with the same Link and Delegated Prefix (if there is one).

Valid (Assigned Prefix): an Assigned Prefix is valid if and only if both of these are met:

  • No Advertised Prefix that includes or is included in the Assigned Prefix takes precedence over the Assigned Prefix.
  • No Advertised Prefix that includes or is included in the same Delegated Prefix as the Assigned Prefix, and is assigned to the same Link, takes precedence over the Assigned Prefix.

3. Applicability Statement

okay so the algorithm was mainly built as an autonomic prefix assignment tool for home networks 🏠, but it's giving versatility, because it works in other places too 🧚 It can run with zero configuration, and it can also use fancy advanced prefix assignment rules. It can be applied to any address space, and it can even manage several address spaces at the same time. For example, an implementation can use IPv4-mapped IPv6 addresses [RFC4291] to manage both IPv4 and IPv6 prefix assignment with one single prefix space. Iconic 👑

Each Node MUST have a set of non-overlapping Delegated Prefixes (meaning they don't include each other). This set MAY change over time, and it MAY be different from one Node to another at some point, but Nodes MUST eventually end up with the same set of non-overlapping Delegated Prefixes. We need everyone on the same page, periodt 💜

Given this set of non-overlapping Delegated Prefixes, Nodes may assign available prefixes from each Delegated Prefix to the Links they're directly connected to. The algorithm makes sure that at most one prefix from a given Delegated Prefix gets assigned to any given Link. Prefixes may also be assigned for private use. For example, an assigned prefix may be delegated to some other entity that doesn't implement this algorithm [RFC3633], or it may be given a high priority so other nodes can't assign any overlapping prefix [RFC6603]. Protecting your space 🛡️✨

The algorithm supports topologies that keep changing, so it will converge if the topology stays unchanged for a long enough time. (How long that is depends on the properties of the Flooding Mechanism.) Some topology changes may cause renumbering, though, while others won't. Nodes joining the set of participating Nodes don't cause renumbering. Similarly, Nodes leaving the network may be handled without renumbering by using the prefix adoption procedure. On the other hand, Links that merge or split may break the correctness conditions, and that can cause renumbering 🙈

All Nodes MUST run a common Flooding Mechanism to share published Assigned Prefixes. The set of participating Nodes is defined as the set of Nodes participating in the Flooding Mechanism. Everybody has to be in the group chat 💬

The Flooding Mechanism MUST:

  • Provide a way to flood Assigned Prefixes assigned to a directly connected Link, along with their respective Advertised Prefix Priority and the Node ID of the Node advertising them.
  • Specify whether an Advertised Prefix is assigned to a directly connected Shared Link, and if so, which one. This information also needs to be updated when Links merge or split.
  • Provide a Flooding Delay value, which SHOULD represent a deterministic or likely upper bound on the information propagation delay among participating Nodes. If the Flooding Mechanism can't stick to the provided Flooding Delay, renumbering may happen. Since a delay often depends on the size of the network, it MAY change over time, and it MAY be different from one Node to another. Also, picking this value is a tradeoff between convergence speed and a lower renumbering probability (for example, the value 0 may be used when renumbering is harmless). That makes it out of scope for this document 🧠

The algorithm makes sure that whenever the Flooding Delay is provided and held, and there's no topology change or Delegated Prefix removal, renumbering only happens when a Node deliberately overrides an existing assignment. Without that kind of deliberate override, the algorithm converges within an absolute worst-case timespan of (2 * Flooding Delay * L) seconds, where L is the number of links. The math ate 🔥

Each Node MUST have a Node ID. If multiple Nodes have the same Node ID, the algorithm won't suffer, as long as there are no colliding assignments. However, for collisions to get resolved, that situation MUST be transient. Don't let the group chat stay confusing for long 😭

Finally, leaving the Flooding Mechanism or Node ID assignment process unsecured makes the network vulnerable to denial-of-service attacks, as detailed in Section 8. Additionally, since this algorithm requires all Nodes to know which Node has made which assignment, it may be unsuitable depending on privacy requirements among participating Nodes. Not the vibe, so lock it down 🔒💀

4. Algorithm Specification

this section spells out how Nodes implementing the prefix assignment algorithm are supposed to behave 🎀 The terms 'Current Assignment', 'Precedence', 'Best Assignment', and 'Valid' are used exactly as defined in Section 2.1 🦋

4.1. Prefix Assignment Algorithm Subroutine 💅✨

okay bestie, this is where we spell out the prefix assignment algorithm subroutine 🎀. It's defined for a given Delegated Prefix and Link pair, and it takes a BackoffTriggered boolean as its parameter. That boolean basically tells us whether the subroutine was kicked off by the Backoff Timer or by some other event 🌸. It also uses two configuration parameters, ADOPT_MAX_DELAY and BACKOFF_MAX_DELAY, which are defined in Section 7 🦋.

For a given Delegated Prefix and Link pair, the subroutine MUST be run with the BackoffTriggered boolean set to false whenever:

  • An Advertised Prefix including or included in the considered Delegated Prefix is added or removed.
  • An Assigned Prefix included in the considered Delegated Prefix and associated with a different Link than the considered Link was destroyed, while there is no Current Assignment associated with the given pair. This case MAY be ignored if the creation of a new Assigned Prefix associated with the considered pair is not desired.
  • The considered Delegated Prefix is added.
  • The considered Link is added.
  • The Node ID is modified.
  • An Assigned Prefix included in the considered Delegated Prefix and associated with the considered Link is destroyed outside of the context of the subroutine, as specified in Section 4.2.

Furthermore, for a given Delegated Prefix and Link pair, the subroutine MUST be run with the BackoffTriggered boolean set to true whenever:

  • The Backoff Timer associated with the considered Delegated Prefix and Link pair fires while there is no Current Assignment associated with the given pair.

When such an event occurs, a Node MAY delay the execution of the subroutine instead of executing it immediately, e.g., while receiving an update from the Flooding Mechanism, or for security reasons (see Section 8). Even if other events occur in the meantime, the subroutine MUST be run only once. It is also assumed that if one of these events is the firing of the Backoff Timer while there is no Current Assignment associated with the given pair, the subroutine is executed with the BackoffTriggered boolean set to true. 🫶

In order to execute the subroutine for a given Delegated Prefix and Link pair, first get the Current Assignment and compute the Best Assignment associated with the Delegated Prefix and Link pair, then execute the steps depending on the following cases:

  1. If there is no Best Assignment and no Current Assignment: Decide whether the creation of a new assignment for the given Delegated Prefix and Link pair is desired. (As any result would be valid, the process of making this decision is out of scope for this document.) And, do the following:
    • If it is not desired, stop the execution of the subroutine.
    • Else if the Backoff Timer is running, stop the execution of the subroutine.
    • Else if the BackoffTriggered boolean is set to false, set the Backoff Timer to some random delay between ADOPT_MAX_DELAY and BACKOFF_MAX_DELAY (see Section 7) and stop the execution of the subroutine.
    • Else, continue the execution of the subroutine.

Select a prefix for the new assignment (see Section 5 for guidance regarding prefix selection). This prefix MUST be included in or be equal to the considered Delegated Prefix and MUST NOT include or be included in any Advertised Prefix. If a suitable prefix is found, use it to create a new Assigned Prefix:

  • Assigned to the considered Link.
  • Set as not applied.
  • The Apply Timer set to (2 * Flooding Delay).
  • Published with some selected Advertised Prefix Priority.
  1. If there is a Best Assignment but no Current Assignment: First, check if the Best Assignment is equal to or included in the Delegated Prefix. If not, stop the execution of the subroutine. Otherwise, cancel the Backoff Timer and use the prefix from the Best Assignment to create a new Assigned Prefix:
    • Assigned to the considered Link.
    • Set as not applied.
    • With the Apply Timer set to (2 * Flooding Delay).
    • Set as not published.
  2. If there is a Current Assignment but no Best Assignment:
    • If the Current Assignment is not valid, destroy it, and execute the subroutine again with the BackoffTriggered boolean set to false.
    • If the Current Assignment is valid and published, stop the execution of the subroutine.
    • If the Current Assignment is valid and not published, the Node MUST either:
      • Adopt the prefix by canceling the Apply Timer and set the Backoff Timer to some random delay between 0 and ADOPT_MAX_DELAY (see Section 7). This procedure is used to avoid renumbering when the Node advertising the prefix left the Shared Link, and it SHOULD therefore be preferred. 🌈
      • Destroy it and go to case 1, allowing a different prefix to be assigned, or the prefix to be removed. When the Current Assignment is applied, this causes renumbering.
  3. If there is a Current Assignment and a Best Assignment:
    • Cancel the Backoff Timer.
    • If the two prefixes are identical, set the Current Assignment as not published. If the Current Assignment is not applied and the Apply Timer is not set, set the Apply Timer to (2 * Flooding Delay).
    • If the two prefixes are not identical, destroy the Current Assignment and go to case 2.

When the prefix assignment algorithm subroutine requires an assignment to be created or adopted, any Advertised Prefix Priority value can be used. Other documents MAY provide restrictions over this value depending on the context in which the algorithm is operating or leave it as implementation specific. ✨

4.2. Overriding and Destroying Existing Assignments 🎀

In addition to the behaviors specified in Section 4.1, the following procedures MAY be used in order to provide additional behavior options (Section 6). 💖

Overriding Existing Assignments: For any given Link and Delegated Prefix, a Node MAY create a new Assigned Prefix using a chosen prefix and Advertised Prefix Priority such that:

  • The chosen prefix is included in or is equal to the considered Delegated Prefix.
  • The Current Assignment, if any, as well as all existing Assigned Prefixes that include or are included inside the chosen prefix are destroyed.
  • It is not applied.
  • The Apply Timer is set to (2 * Flooding Delay).
  • It is published.
  • The Advertised Prefix Priority is greater than the Advertised Prefix Priority from all Advertised Prefixes that include or are included in the chosen prefix.
  • The Advertised Prefix Priority is greater than the Advertised Prefix Priority from all Advertised Prefixes that include or are included in the considered Delegated Prefix and are assigned to the considered Link.

In order to ensure algorithm convergence:

  • Such overriding assignments MUST NOT be created unless there was a change in the Node configuration, a Link was added, or an Advertised Prefix was added or removed.
  • The chosen Advertised Prefix Priority for the new Assigned Prefix SHOULD be greater than all priorities from the destroyed Assigned Prefixes. If not, simple topologies with only two Nodes may not converge. Nodes that do not adhere to this rule MUST implement a mechanism that detects if the distributed algorithm does not converge and, when this occurs, they MUST stop creating overriding Assigned Prefixes that do not adhere to this rule. The specifications for such safety procedures are out of scope for this document. 👑

Removing an Assigned Prefix: A Node MAY destroy any Assigned Prefix that is published. Such an event reflects the desire of a Node to not assign a prefix from a given Delegated Prefix to a given Link anymore. In order to ensure algorithm convergence, such a procedure MUST NOT be executed unless there was a change in the Node configuration. Furthermore, whenever an Assigned Prefix is destroyed in this way, the prefix assignment algorithm subroutine MUST be run for the Delegated Prefix and Link pair associated with the destroyed Assigned Prefix. 🍓

The two procedures specified in this section are OPTIONAL. They could be used for various purposes, e.g., for providing custom prefix assignment configuration or reacting to prefix space exhaustion (by overriding short Assigned Prefixes and assigning longer ones). 🧚

4.3. Other Events 🌸

When the Apply Timer fires, the associated Assigned Prefix MUST be applied.

When the Backoff Timer associated with a given Delegated Prefix and Link pair fires while there is a Current Assignment associated with the same pair, the Current Assignment MUST be published with some associated Advertised Prefix Priority and, if the prefix is not applied, the Apply Timer MUST be set to (2 * Flooding Delay).

When a Delegated Prefix is removed from the set of Delegated Prefixes (e.g., when the Delegated Prefix expires), all Assigned Prefixes included in the removed Delegated Prefix MUST be destroyed.

When one Delegated Prefix is replaced by another one that includes or is included in the deleted Delegated Prefix, all Assigned Prefixes that were included in the deleted Delegated Prefix but are not included in the added Delegated Prefix MUST be destroyed. Others MAY be kept.

When a Link is removed, all Assigned Prefixes assigned to that Link MUST be destroyed. 💜

Okay bestie, picking up right where we left off! 💖 Let's get into the good stuff: how a Node actually picks its prefix ✨

5. Prefix Selection Considerations ✨

5.1. Where the Prefix Can Come From 🎀

Okay so when the prefix assignment algorithm subroutine from Section 4.1 needs a brand new prefix, it MUST be picked in one of these ways, no cap 💅:

  • Among prefixes that are inside the considered Delegated Prefix and that were already assigned and applied on the considered Link before. Applied Prefixes can be stored in stable storage along with their associated Link 🧚
  • Randomly, picked from a set of prefixes that is at least RANDOM_SET_SIZE big (see Section 7) 🎲. Those prefixes are the ones inside the considered Delegated Prefix that do not include or get included in any Assigned or Advertised Prefix. If there are fewer than RANDOM_SET_SIZE candidates, the prefix MUST be picked among ALL the candidates 🫶
  • Based on some custom selection process from the configuration ⚙️

A simple implementation MAY just randomly pick from all available prefixes, but ngl this is inefficient for address space use, because a few long prefixes can totally use up the pool of short ones 😭

The rest of this section is a more efficient approach that MAY be used any time a Node needs to pick a prefix for a new assignment 👑. Here are two definitions you need:

Available prefix: A prefix written as Prefix/PrefixLength is available if and only if it passes all three of these checks 🦋:

  • It is inside the considered Delegated Prefix.
  • It does not include, and is not included in, any Assigned or Advertised Prefix.
  • It is equal to the considered Delegated Prefix, OR Prefix/(PrefixLength-1) includes an Assigned or Advertised Prefix.

Candidate prefix: A prefix of the desired length that is inside or equal to an available prefix 🌸.

The procedure in this section looks at three criteria, and they're all giving main character energy 🌈:

Prefix Stability: Sometimes you want the selected prefix to stay the same across executions and reboots 🔒. For that, prefixes previously applied on the Link or pseudorandom prefixes generated from Node- and Link-specific values may be considered 🍓.

Randomness: When no stored or pseudorandom prefix gets chosen, a prefix may be randomly picked among RANDOM_SET_SIZE candidates of the desired length. If fewer than RANDOM_SET_SIZE candidates can be found, the prefix is picked among all candidates 🎰.

Addressing-space usage efficiency: Here's the tea ☕. A small set of badly chosen long prefixes can block any shorter prefix from ever being assigned 💀. So the set of RANDOM_SET_SIZE candidates is built from available prefixes with the longest prefix lengths, and if there's a tie, numerically small prefix values win 🏆.

5.2. The Step-by-Step Procedure 📝

When you run this, do the following steps in order, bestie 💜:

  1. For each prefix stored in stable storage, check if it is inside or equal to an available prefix. If it is, pick that prefix and stop 🛑.
  2. For each prefix length, count how many available prefixes there are of that length 🔢.
  3. If the desired prefix length wasn't specified, select one. The available prefix count from the previous step can help you pick a prefix length such that:
    • There is at least one candidate prefix.
    • The prefix length is big enough that the address space doesn't get exhausted 🌷.

Let N be the chosen prefix length.

  1. Iterate over available prefixes, starting with prefixes of length N and going down to length 0. Create a set of RANDOM_SET_SIZE candidate prefixes of length exactly N that are inside or equal to available prefixes. The end goal is a set of RANDOM_SET_SIZE candidate prefixes of length N inside a set of available prefixes with maximized prefix length 🎯. If there's a tie, smaller prefix values (by bit-wise lexicographical order) are preferred 🧁.
  2. Generate a set of prefixes of the desired length, pseudorandomly chosen from Node- and Link-specific values. For each pseudorandom prefix, check if it is equal to a candidate prefix. If it is, pick that prefix and stop 🦄.
  3. Choose a random prefix from the set of selected candidates 🎲✨.

Okay but the complexity of this is equal to the complexity of iterating over available prefixes 🤓. It can be done in linear time, for example by storing Advertised and Assigned Prefixes in a binary tree 🌳.

6. Implementation Capabilities and Node Behavior 🧩

Implementations of the prefix assignment algorithm can be anywhere from super basic to highly customizable, and they still get fully interoperable behaviors 🤝. Three behaviors are given as examples:

Listener: The Node only acts on assignments made by other Nodes. It never creates new assignments and never adopts existing ones 👀. This doesn't require the considerations from Section 4.2 or 5. The Node never checks whether existing assignments are valid, which makes this perfect for lightweight devices that can rely on more capable neighbors to make assignments on directly connected Shared Links 🪶.

Basic: The Node can assign new prefixes or adopt prefixes that don't conflict with any other existing assignment 💁. This doesn't require the considerations from Section 4.2. It's a good fit when there's no preference over which prefix goes to which Link, and no priority between different Links 🍭.

Advanced: The Node can assign new prefixes, adopt existing ones, make overriding assignments, and destroy existing ones 🔥. This requires the considerations from Sections 4.2 and 5. It's suitable when the administrator wants a particular prefix assigned on a given Link, or wants some Links to get prefixes with greater priority when there aren't enough prefixes for all Links 👑.

Note that if all Nodes directly connected to some Link are listener Nodes, or none of them are willing to make an assignment from a given Delegated Prefix to the given Link, then no prefix from that Delegated Prefix will ever be assigned to the Link 💀. You can spot this situation by monitoring whether any prefix from a given Delegated Prefix has been assigned to the Link for longer than BACKOFF_MAX_DELAY plus the Flooding Delay 👀.

7. Algorithm Parameters 🎛️

This document doesn't give values for ADOPT_MAX_DELAY, BACKOFF_MAX_DELAY, or RANDOM_SET_SIZE 🙅. The algorithm still ensures convergence and correctness for any chosen values, even when they differ from Node to Node 🫶. They MAY be adjusted depending on context, which is a tradeoff between convergence time, efficient addressing, control traffic (generated by the Flooding Mechanism), and collision probability ⚖️.

ADOPT_MAX_DELAY is the maximum backoff time a Node may wait before adopting an assignment. BACKOFF_MAX_DELAY is the maximum backoff time a Node may wait before making a new assignment. BACKOFF_MAX_DELAY MUST be greater than or equal to ADOPT_MAX_DELAY 📏. The greater ADOPT_MAX_DELAY and (BACKOFF_MAX_DELAY - ADOPT_MAX_DELAY) are, the lower the collision probability and the less control traffic there is, but the longer the convergence time gets 🐢.

RANDOM_SET_SIZE is the desired size of the set a random prefix gets picked from. The greater RANDOM_SET_SIZE, the better the convergence time and the lower the collision probability, but the worse the addressing-space usage efficiency 📉.

8. Security Considerations 🔐

Okay this section is SERIOUS, bestie, so read it carefully 😭🚨

The prefix assignment algorithm runs on top of two separate mechanisms: the Flooding Mechanism and the Node ID assignment mechanism 🧠.

An attacker who can publish Advertised Prefixes through the Flooding Mechanism can do the following:

  • Publish a single overriding assignment for a whole Delegated Prefix, or for the whole address space, which stops any Node from assigning prefixes to Links 🚫.
  • Quickly publish and remove Advertised Prefixes, generating traffic at the Flooding Mechanism layer and causing many executions of the prefix assignment algorithm in all participating Nodes 🌪️.
  • Publish and remove Advertised Prefixes to stop the algorithm from converging 🌀.

An attacker who can stop other Nodes from accessing some or all of the Advertised Prefixes may compromise the correctness of the algorithm 💔.

An attacker who can cause repeated Node ID changes may generate traffic in the Flooding Mechanism and many executions of the prefix assignment algorithm in all participating Nodes 😵.

An attacker who can publish Advertised Prefixes using a Node ID that another Node is using may get in the way of resolving prefix assignment collisions 🥴.

Whenever the security of the Flooding Mechanism and the Node ID assignment mechanism can't be ensured, convergence of the algorithm may be prevented 🙈. In environments where these attacks may happen, the execution of the prefix assignment algorithm subroutine SHOULD be rate limited, as specified in Section 4.1 🚦.

9. References 📚

9.1. Normative References 💜

[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <http://www.rfc-editor.org/info/rfc2119>.

9.2. Informative References 🦋

[RFC3633] Troan, O. and R. Droms, "IPv6 Prefix Options for Dynamic Host Configuration Protocol (DHCP) version 6", RFC 3633, DOI 10.17487/RFC3633, December 2003, <http://www.rfc-editor.org/info/rfc3633>.

[RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing Architecture", RFC 4291, DOI 10.17487/RFC4291, February 2006, <http://www.rfc-editor.org/info/rfc4291>.

[RFC6603] Korhonen, J., Ed., Savolainen, T., Krishnan, S., and O. Troan, "Prefix Exclude Option for DHCPv6-based Prefix Delegation", RFC 6603, DOI 10.17487/RFC6603, May 2012, <http://www.rfc-editor.org/info/rfc6603>.

Appendix A. Static Configuration Example 🎀

Okay bestie, this appendix is all about how you can custom-configure the prefix assignment algorithm 💅 basically you get to be in charge of the vibes ✨

The Node configuration is specified as a finite set of rules. A rule is defined as:

  • A prefix to be used.
  • A Link on which the prefix may be assigned.
  • An Assigned Prefix Priority (the smallest possible Assigned Prefix Priority if the rule may not override other Assigned Prefixes).
  • A rule priority (0 if the rule may not override existing Advertised Prefixes).

So to keep the algorithm converging (aka actually settling down and not spiraling 🌀), the Assigned Prefix Priority MUST be an increasing function (not necessarily strictly) of the configuration rule priority. That means the greater the configuration rule priority is, the greater the Assigned Prefix Priority must be 🔥

Each Assigned Prefix is associated with a rule priority. Assigned Prefixes that are created as specified in Section 4.1 are given a rule priority of 0 🦋

Whenever the configuration is changed or the prefix assignment algorithm subroutine is run, for each Link/Delegated Prefix pair, look for the configuration rule with the greatest configuration rule priority such that:

  • The prefix specified in the configuration rule is included in the considered Delegated Prefix.
  • The Link specified in the configuration rule is the considered Link.
  • All the Assigned Prefixes that would need to be destroyed in case a new Assigned Prefix is created from that configuration rule (as specified in Section 4.2) have an associated rule priority that is strictly lower than the one of the considered configuration rule.
  • The assignment would be valid when published with an Advertised Prefix Priority equal to the one specified in the configuration rule.

If a rule is found, a new Assigned Prefix is created based on that rule as specified in Section 4.2. The new Assigned Prefix is associated with the Advertised Prefix Priority and the rule priority specified in the considered configuration rule 🧚

Note that the use of rule priorities ensures the convergence of the algorithm. This is the whole reason the rule priorities exist, so don't skip it 🙈

Acknowledgments 🫶

The authors would like to thank everyone who helped out with the draft versions of this document as well as this one 🌸 A special shoutout to Tim Chown, Fred Baker, Mark Townsley, Lorenzo Colitti, Ole Troan, Ray Bellis, Markus Stenberg, Wassim Haddad, Joel Halpern, Samita Chakrabarti, Michael Richardson, Anders Brandt, Erik Nordmark, Laurent Toutain, Ralph Droms, Acee Lindem, Steven Barth, and Juliusz Chroboczek for the interesting discussions and document review. Literally the dream team 👑💜

Authors' Addresses 💖

Here's where you can find the authors, bestie 🦋

Pierre Pfister
Cisco Systems
Paris
France

Email: pierre.pfister@darou.fr
Benjamin Paterson
Cisco Systems
Paris
France

Email: paterson.b@gmail.com
Jari Arkko
Ericsson
Jorvas  02420
Finland

Email: jari.arkko@piuha.net
📦 where this page comes from