Distributed Prefix Assignment Algorithm
Extracted elements (29)
Naive random prefix selection is inefficient because a few long prefixes can exhaust the pool of available short prefixes. The recommended procedure selects candidates from available prefixes with the longest prefix lengths (maximizing address-space usage efficiency) and uses pseudorandom Node- and Link-specific values to promote stability across reboots.
Nodes joining the participating set do not cause renumbering; Nodes leaving may be handled without renumbering via prefix adoption. However, Links that merge or split may violate correctness conditions and thus force renumbering — this is an inherent limitation of the distributed approach.
Prefix adoption (case 3 of subroutine) allows a Node connected to the same Shared Link to continue advertising a prefix after the original advertiser disappears, providing seamless assignment transfer and avoiding renumbering on Node failure. Adoption SHOULD be preferred over destroying and reassigning.
The algorithm is designed to be fully autonomic (requiring no configuration) while also supporting custom configuration via variable priority assignments. This makes it applicable to both home networks and configured enterprise environments without modification.
The Flooding Delay value represents a tradeoff: a value of 0 may be used when renumbering is harmless, while larger values reduce renumbering probability at the cost of slower convergence. The algorithm guarantees convergence within (2 * Flooding Delay * L) seconds, where L is the number of links.
The algorithm can manage both IPv4 and IPv6 prefix assignment simultaneously by using IPv4-mapped IPv6 addresses (per RFC 4291) so that a single prefix space covers both address families.
All Nodes MUST run a common Flooding Mechanism to share published Assigned Prefixes. The Flooding Mechanism MUST carry the Assigned Prefix, its Advertised Prefix Priority, and the Node ID of the advertising Node.
An Applied Assigned Prefix MAY be used for host configuration, routing, or prefix delegation. When not applied, it MUST NOT be used for any purpose outside of the prefix assignment algorithm.
BACKOFF_MAX_DELAY MUST be greater than or equal to ADOPT_MAX_DELAY. The three parameters ADOPT_MAX_DELAY, BACKOFF_MAX_DELAY, and RANDOM_SET_SIZE MAY differ from Node to Node; the algorithm ensures correctness and convergence for any chosen values.
Each Node MUST have a set of non-overlapping Delegated Prefixes. This set MAY change over time, but Nodes MUST eventually converge on the same set.
Overriding assignments MUST NOT be created unless there was a change in Node configuration, a Link was added, or an Advertised Prefix was added or removed, to ensure algorithm convergence.
The chosen Advertised Prefix Priority for an overriding assignment SHOULD be greater than all priorities from the destroyed Assigned Prefixes; otherwise, Nodes MUST implement convergence-detection and MUST stop creating non-compliant overriding assignments when non-convergence is detected.
The Flooding Delay MUST be provided by the Flooding Mechanism and SHOULD be a deterministic or likely upper bound on information propagation delay among participating Nodes.
The prefix assignment subroutine MUST be run (with BackoffTriggered=false) whenever an Advertised Prefix in the Delegated Prefix is added or removed, the Delegated Prefix or Link is added, the Node ID changes, or a relevant Assigned Prefix is destroyed outside the subroutine.
The range of Advertised Prefix Priority values MUST have an upper bound to ensure convergence when resolving conflicting assignments.
The set of Node IDs MUST be strictly and totally ordered (e.g., using alphanumeric order). The mechanism for assigning Node IDs is out of scope.
When a Delegated Prefix is removed, all Assigned Prefixes included in it MUST be destroyed. When a Link is removed, all Assigned Prefixes assigned to that Link MUST be destroyed.
When creating a new assignment (case 1 of subroutine), the selected prefix MUST be included in or equal to the Delegated Prefix and MUST NOT include or be included in any Advertised Prefix. The Apply Timer is set to (2 * Flooding Delay).
When multiple Nodes have the same Node ID, this situation MUST be transient in order for assignment collisions to be resolved; the algorithm still operates correctly absent colliding assignments.
When selecting a new prefix, it MUST be chosen from previously applied prefixes on the Link (from stable storage), or randomly from a set of at least RANDOM_SET_SIZE candidates, or via a custom configured selection process.
When the Apply Timer fires, the associated Assigned Prefix MUST be applied. When the Backoff Timer fires for a pair with a Current Assignment, that assignment MUST be published and the Apply Timer MUST be set to (2 * Flooding Delay) if not yet applied.
When the Backoff Timer fires for a pair with no Current Assignment, the subroutine MUST be run with BackoffTriggered=true. Even if multiple events occur before execution, the subroutine MUST be run only once.
A Private Link is an abstract concept allowing Nodes to make assignments for private use or delegation (e.g., each DHCPv6-PD requesting router may be treated as a distinct Private Link). A Shared Link is a multi-access or point-to-point link requiring actual prefix assignment.
Advertised Prefix Priority is a value defining the priority of an Advertised Prefix. When multiple prefixes conflict (overlapping or same Delegated Prefix on same link), all but the greatest priority are eventually removed; ties are broken by the Node ID of the advertising node.
Each Delegated Prefix and Link pair is associated with a Backoff Timer that counts down before a new Assigned Prefix is created or an adopted prefix is advertised, reducing collision probability from concurrent assignments by multiple Nodes.
Three interoperable implementation behaviors are defined: Listener (only reacts to others' assignments, suitable for lightweight devices), Basic (can assign and adopt but not override), and Advanced (full capabilities including overriding and destroying assignments per Section 4.2).
An attacker able to cause repetitive Node ID changes generates Flooding Mechanism traffic and multiple subroutine executions. An attacker spoofing another Node's Node ID impedes collision resolution. In environments where such attacks are possible, the subroutine execution SHOULD be rate limited.
An attacker controlling the Flooding Mechanism can publish overriding assignments for an entire Delegated Prefix or address space (preventing all assignment), rapidly toggle Advertised Prefixes to cause excessive algorithm executions, or prevent convergence entirely. Unsecured Flooding Mechanism or Node ID assignment makes the network vulnerable to these denial-of-service attacks.
An Assigned Prefix has two orthogonal state dimensions: applied/not-applied (controlled by the Apply Timer) and published/not-published (controlled by the subroutine). Transitions: Apply Timer fires → applied; destroyed → not-applied and not-published and removed from set.