draft-ietf-homenet-prefix-assignment-01.txt   draft-ietf-homenet-prefix-assignment-02.txt 
Network Working Group P. Pfister Network Working Group P. Pfister
Internet-Draft B. Paterson Internet-Draft B. Paterson
Intended status: Standards Track Cisco Systems Intended status: Standards Track Cisco Systems
Expires: April 27, 2015 J. Arkko Expires: July 9, 2015 J. Arkko
Ericsson Ericsson
October 24, 2014 January 5, 2015
Prefix and Address Assignment in a Home Network Distributed Prefix Assignment Algorithm
draft-ietf-homenet-prefix-assignment-01 draft-ietf-homenet-prefix-assignment-02
Abstract Abstract
This memo describes a home network prefix and address assignment This document specifies a distributed algorithm for automatic prefix
algorithm running on top of any 'flooding protocol' that fulfills the assignment. Given a set of delegated prefixes, it ensures at most
specified requirements. It is expected that home border routers are one prefix is assigned from each delegated prefix to each link.
allocated one or multiple IPv6 prefixes through DHCPv6 Prefix Nodes may assign available prefixes to the links they are directly
Delegation (PD) or that prefixes are made available through other connected to, or for other private purposes. The algorithm
means. An IPv4 address can also be assigned and private addresses be eventually converges and ensures that all assigned prefixes do not
used with NAT to provide IPv4 connectivity. In both cases, provided overlap.
prefixes need to be efficiently divided among the multiple links, and
routers need to obtain addresses. This document describes a
distributed algorithm for IPv4 and IPv6 prefixes division, assignment
and router's address assignment, and specifies how hosts can be given
addresses and configuration options using DHCP or SLAAC.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 27, 2015. This Internet-Draft will expire on July 9, 2015.
Copyright Notice Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the Copyright (c) 2015 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Requirements language . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Prefix and Address Assignment Algorithms' Outline . . . . . . 4 3. Applicability statement . . . . . . . . . . . . . . . . . . . 5
4. Router Behavior . . . . . . . . . . . . . . . . . . . . . . . 5 4. Algorithm Specification . . . . . . . . . . . . . . . . . . . 6
4.1. Data structures . . . . . . . . . . . . . . . . . . . . . 6 4.1. Algorithm Terminology . . . . . . . . . . . . . . . . . . 6
4.2. Routers' Interfaces . . . . . . . . . . . . . . . . . . . 7 4.2. Prefix Assignment Algorithm Routine . . . . . . . . . . . 7
4.3. Obtaining a Delegated Prefix . . . . . . . . . . . . . . 7 4.3. Overriding and Destroying Existing Assignments . . . . . 10
4.4. Network Leader . . . . . . . . . . . . . . . . . . . . . 8 4.4. Other Events . . . . . . . . . . . . . . . . . . . . . . 11
4.5. Designated Router . . . . . . . . . . . . . . . . . . . . 8 5. Prefix Selection Considerations . . . . . . . . . . . . . . . 11
4.5.1. Sending Router Advertisement . . . . . . . . . . . . 9 6. Implementation Capabilities and Node Behavior . . . . . . . . 13
4.5.2. DHCP Server Operations . . . . . . . . . . . . . . . 9 7. Algorithm Parameters . . . . . . . . . . . . . . . . . . . . 14
4.6. Applying an Assignment on an Interface . . . . . . . . . 10 8. Security Considerations . . . . . . . . . . . . . . . . . . . 15
4.7. DNS Support . . . . . . . . . . . . . . . . . . . . . . . 10 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16
5. Flooding Protocol Requirements . . . . . . . . . . . . . . . 11 10. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 16
5.1. Router ID . . . . . . . . . . . . . . . . . . . . . . . . 11 11. References . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.2. Propagation Delay . . . . . . . . . . . . . . . . . . . . 11 11.1. Normative References . . . . . . . . . . . . . . . . . . 16
5.3. Flooding Assigned Prefixes . . . . . . . . . . . . . . . 12 11.2. Informative References . . . . . . . . . . . . . . . . . 16
5.4. Flooding Delegated Prefixes . . . . . . . . . . . . . . . 12 Appendix A. Static Configuration Example . . . . . . . . . . . . 16
5.5. Flooding Routers' Address Assignments . . . . . . . . . . 12 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 17
6. Prefix Assignment Algorithm . . . . . . . . . . . . . . . . . 13
6.1. When to execute the Prefix Assignment Algorithm . . . . . 13
6.2. Assignment Precedence . . . . . . . . . . . . . . . . . . 14
6.3. Testing Assignment's validity . . . . . . . . . . . . . . 14
6.4. Testing Assignment's availability . . . . . . . . . . . . 14
6.5. Accepting an Assigned Prefix . . . . . . . . . . . . . . 14
6.6. Making a New Assignment . . . . . . . . . . . . . . . . . 15
6.7. Using Authoritative Prefix Assignments . . . . . . . . . 16
6.8. Choosing the Assignment's Priority . . . . . . . . . . . 17
6.9. Prefix Assignment Algorithm steps . . . . . . . . . . . . 17
6.10. Downstream DHCPv6 Prefix Delegation support . . . . . . . 18
7. Address Assignment Algorithm . . . . . . . . . . . . . . . . 19
7.1. Router's address pools . . . . . . . . . . . . . . . . . 20
7.2. Address Assignment Algorithm . . . . . . . . . . . . . . 20
8. Hysteresis Principle . . . . . . . . . . . . . . . . . . . . 21
8.1. Prefix and Address assignments . . . . . . . . . . . . . 21
8.2. Delegated Prefixes . . . . . . . . . . . . . . . . . . . 21
8.2.1. Unreliable uplink . . . . . . . . . . . . . . . . . . 21
8.2.2. Unreliable in-home link . . . . . . . . . . . . . . . 22
9. ULA and IPv4 Prefixes Generation . . . . . . . . . . . . . . 22
9.1. ULA Prefix Generation . . . . . . . . . . . . . . . . . . 22
9.1.1. Choosing the ULA prefix . . . . . . . . . . . . . . . 23
9.1.2. Advertising a ULA prefix . . . . . . . . . . . . . . 23
9.1.3. Extending prefix lifetime . . . . . . . . . . . . . . 24
9.1.4. Authoritative ULAs . . . . . . . . . . . . . . . . . 24
9.2. IPv4 Private Prefix Generation . . . . . . . . . . . . . 24
10. Manageability Considerations . . . . . . . . . . . . . . . . 24
11. Documents Constants . . . . . . . . . . . . . . . . . . . . . 25
12. Security Considerations . . . . . . . . . . . . . . . . . . . 25
13. References . . . . . . . . . . . . . . . . . . . . . . . . . 26
13.1. Normative References . . . . . . . . . . . . . . . . . . 26
13.2. Informative References . . . . . . . . . . . . . . . . . 27
Appendix A. Scarcity Avoidance Mechanism . . . . . . . . . . . . 28
A.1. Prefix Wasts Avoidance . . . . . . . . . . . . . . . . . 29
A.2. Increasing Assigned Prefix Length . . . . . . . . . . . . 30
A.3. Foreseeing Prefixes Exaustion . . . . . . . . . . . . . . 30
A.4. Cutting an Existing Assignment . . . . . . . . . . . . . 31
Appendix B. Acknowledgments . . . . . . . . . . . . . . . . . . 31
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 32
1. Introduction 1. Introduction
This memo describes a fully distributed prefix and address assignment This document specifies a distributed algorithm for automatic prefix
algorithm for home networks, running on top of any 'flooding assignment. Given a set of delegated prefixes, nodes may assign
protocol' that fulfills the specified requirements. It is expected available prefixes to links they are directly connected to, or for
that home border routers are allocated one or multiple IPv6 prefixes their private use. The algorithm ensures that the following
through DHCPv6 Prefix Delegation (PD) [RFC3633] or that prefixes are assertions are eventually true:
made available through other means. When an IPv4 address is
assigned, a home private IPv4 prefix may be used with NAT to provide
IPv4 connectivity to the whole home, as well as Unique Local Address
prefixes [RFC4193] may be used in order to provide internal
connectivity whenever global IPv6 connectivity is not available.
Obtained IPv6 or IPv4 prefixes need to be efficiently divided among 1. At most one prefix from each delegated prefix is assigned to each
the multiple links. For the purposes of this document, we refer to link.
this process as prefix assignment. This memo describes an algorithm
for such prefix division, assignment and router's address assignment,
as well as the way hosts can be given addresses and configuration
options using DHCPv4 [RFC2131], DHCPv6 [RFC3315] or SLAAC [RFC4862].
In the rest of this document DHCP refers to both DHCPv4 and DHCPv6.
Although this document recommends the use of 64 bits long prefixes, 2. Assigned prefixes are not included in and do not include other
the algorithm do not require routers to assign prefixes of particular assigned prefixes.
lengths. When a delegated prefix is too small considered the number
of links in the home network, higher priority links may be privileged
or smaller prefixes can be assigned in order to avoid prefix
scarcity.
The rest of this memo is organized as follows. Section 2 defines the 3. Assigned prefixes do not change in the absence of topology or
usual keywords, Section 3 outlines the algorithms functioning and configuration changes.
features, Section 4 describes how a home router behaves when running
the prefix and address assignment algorithm. Requirements for the
underlying flooding protocol are detailed in Section 5. The prefix
assignment algorithm is detailed in Section 6 and Section 7 focuses
on the address assignment algorithm. Section 8 explains the
hysteresis principles applied to both prefix and address assignments,
Section 9 specifies the procedures for automatic generation of ULA
and IPv4 prefixes, Section 10 explains what administrative interfaces
are useful for advanced users that wish to manually interact with the
mechanisms, Section 11 gives values for the constants used in this
document, Section 12 discusses the security aspects and finally,
Appendix A provides implementation guidelines for the optional
scarcity avoidance mechanism.
The Prefix Assignment Algorithm was first detailed in In the rest of this document the two first conditions are referred to
[I-D.arkko-homenet-prefix-assignment]. This document is a as the correctness conditions of the algorithm while the third
continuation and generalization of that draft to any underlying condition is referred to as its convergence condition.
flooding protocol. It also adds support for arbitrary prefix length,
IPv4, scarcity avoidance mechanism or manual configuration.
2. Requirements language Each assignment has a priority specified by the node making the
assignment, allowing for more advanced assignment policies. When
multiple nodes assign different prefixes from the same delegated
prefix to the same link, or when multiple nodes assign overlapping
prefixes, the assignment with the highest priority is kept and other
assignments are removed.
The prefix assignment algorithm requires that participating nodes
share information through a flooding mechanism. If the flooding
mechanism ensures that all messages are propagated to all nodes
faster than a given timing upper bound, the algorithm also ensures
that all assigned prefixes used for networking operations (e.g., host
configuration) remain unchanged, unless another node assigns an
overlapping prefix with a higher assignment priority, or the topology
changes and renumbering cannot be avoided.
2. Terminology
In this document, the key words "MAY", "MUST, "MUST NOT", "OPTIONAL", In this document, the key words "MAY", "MUST, "MUST NOT", "OPTIONAL",
"RECOMMENDED", "SHOULD", and "SHOULD NOT", are to be interpreted as "RECOMMENDED", "SHOULD", and "SHOULD NOT", are to be interpreted as
described in [RFC2119]. described in [RFC2119].
3. Prefix and Address Assignment Algorithms' Outline This document makes use of the following terminology:
Given one or multiple prefixes for the entire network, each prefix is
subdivided by the prefix assignment algorithm so that every link is
given one assignment per available prefix. Assignments are
advertised through the whole network using the underlying flooding
protocol, collisions are detected and valid assignments are chosen
and applied on every link. Once a prefix is applied, hosts and
routers may be given addresses. In summary, the algorithm works in
four steps:
1. The home is given IPv6 or IPv4 prefixes called Delegated Prefixes
(DPs).
2. Each link is provided an Assigned Prefix (AP) from each available
Delegated Prefix.
3. Routers internally check for AP's validity and select Chosen
Prefixes (CPs).
4. Once a link is given an assignment, routers may get addresses
from specified address pools and hosts may be configured using
SLAAC or by the per-link elected DHCP server.
This algorithm, which intends to fulfill requirements specified in
[I-D.ietf-homenet-arch], has the following features:
o Each delegated prefix is effectively divided so that each link is
assigned a reasonable part. If the delegated prefix is too small
given the size of the network, prefixes of arbitrary lengths may
be used.
o The algorithm is completely distributed. Routers may join or
leave and DPs may be added or removed at any time.
o IPv4 connectivity is provided when a home router acquires an IPv4
address and default route from an external source. In this case a
private IPv4 delegated prefix is generated and prefixes are
assigned similarly to IPv6.
o The network may spontaneously generate and use a Unique Local
Address (ULA) prefix.
o Assignments are stable across reboots and some network changes
(e.g. adding or removing routers).
o DHCP options like DNS servers, prefix colors
[I-D.bhandari-dhc-class-based-prefix], or any upcoming options may
be attached to each prefix and may be relayed down to the host
when it is given addresses.
o The user can manually assign prefixes to links. Such assignments
will take precedence over automatically assigned prefixes.
o Assignments and interfaces can be given priorities. When a
delegated prefix is too small, such values may be used to
prioritize prefix assignment to certain links.
4. Router Behavior
All home routers participating in the prefix assignment algorithm
MUST fulfill the requirements defined in this document and use a
common flooding protocol and routing protocol. Classic CPE routers
[RFC7084] are supported as downstream routers and dowstream DHCPv6-PD
enabled routers are supported as both downstream and uplink routers,
but problems may occur when such router is connected to the home
network on both WAN and LAN side. In the later case, finer external
interface detection algorithm or static configuration can be used to
solve the issue, but these are out of the scope of this document.
4.1. Data structures
Each router MUST maintain a list of all the Delegated Prefixes.
These prefixes may be locally generated, as described in Section 4.3,
or come from other routers as described in Section 5.4.
Each router MUST maintain a list of all the Assigned Prefixes
advertised by other routers. Each AP is learnt through the
mechanisms described in Section 5.3 and is defined as a tuple of:
Prefix: The assigned prefix.
Router ID: The identifier of the advertising router.
Link ID: If the assignment is made on a connected link, an interface
identifier of the interface connected to that link.
Authoritative bit: A boolean that tells whether the assignment comes
from a network authority (DHCPv6 PD, manual configuration,
etc...).
Assignment's Priority: A value between PRIORITY_MIN and
PRIORITY_MAX, specifying the assignment's priority.
The AP list is the result of the information provided by the flooding
protocol, as specified in Section 5.3.
The router MUST maintain a list of all prefixes currently chosen to
be applied on connected links. They are Chosen Prefixes (CPs) and
described by a tuple of:
Prefix: The assigned prefix.
Link ID: An interface identifier of the interface connected to the
link on which the assignment is made.
Authoritative bit: A boolean that tells whether the assignment comes
from a network authority (DHCPv6 PD, manual configuration,
etc...).
Assignment's Priority: A value between PRIORITY_MIN and
PRIORITY_MAX, specifying the assignment's priority.
Advertised: Whether that assignment is being advertised by the
flooding protocol (see Section 5.3).
Applied: Whether that assignment is applied on link's configuration
(see Section 4.6).
Chosen Prefixes that are marked as 'Advertised' are distributed to
other routers using the flooding protocol and are therefore
considered as Assigned Prefixes by other routers. The goal of the
Prefix Assignment Algorithm is to ensure that all routers have a
consistent view of Assigned Prefixes on each link.
The router MUST maintain a database of its own address assignments,
and address assignments made by other routers on connected links as
learnt through means described in Section 5.5.
4.2. Routers' Interfaces
Each interface MUST either be considered as internal or external.
Prefixes and addresses are only assigned to internal interfaces. The
criteria to make this distinction are out of the scope of this
document.
If an internal interface becomes external, all prefixes and addresses
assigned on the considered interface MUST be deleted and no longer
announced, and the prefix assignment algorithm MUST be run.
If an external interface becomes internal, the prefix assignment
algorithm MUST be run (see Section 6.1).
Whenever two or more interfaces are connected to the same link, all
but one of them SHOULD be ignored by the prefix assignment algorithm.
A mechanism to detect such situation SHOULD be provided by the
flooding algorithm.
4.3. Obtaining a Delegated Prefix
Delegated Prefixes (Of any kind: Global, ULA, IPv4...) can be
obtained or generated through different means:
o It can be delegated by a service provider (DHCPv6 PD, 6rd
[RFC5969], etc..).
o It can be provisioned by an administrative authority (user
configuration, netconf [RFC6241], etc... ).
o A ULA prefix may be spontaneously generated as defined in
Section 9.1.
o An IPv4 private prefix may be spontaneously generated as defined
in Section 9.2.
DHCP options MAY be attached to a delegated prefix by the router that
either generated the prefix or received it through DHCPv6 PD. IPv6
delegated prefix options MUST be encoded as DHCPv6 options. IPv4
delegated prefix options MUST be encoded as DHCPv4 options.
As DHCP options are numerous and new ones may be defined, specifying
routers' behavior regarding each option is out of the scope of this
document. In order to avoid misconfiguration, routers must follow
the two following general rules:
o A router MUST NOT advertise a prefix obtained through DHCPv6 PD if
it doesn't understand the all of the provided options.
o A router MUST NOT make or accept any assignment associated to a
delegated prefix if it doesn't understand the all of the DHCP
options advertised with the delegated prefix.
The mif working group may provide useful inputs concerning the way
the home network should handle different prefixes associated with
heterogeneous uplinks.
4.4. Network Leader
A router considers itself as the Network Leader if and only if its
router ID is greater than all other router IDs in received Prefix
Assignments and Delegated Prefixes.
4.5. Designated Router
On a link where custom host configuration must be provided, or
whenever SLAAC cannot be used, a DHCP server must be elected. That
router is called designated router and is dynamically chosen by the
prefix assignment algorithm.
A router MUST consider itself designated router on a given link if
either one of the following conditions holds:
o The link's Assigned Prefixes list is empty. i.e. no other router
is advertising assignments on the considered link. And, if such
information is provided by the flooding protocol, the router has
the highest id on the link.
o Considering all APs and advertised CPs on the given link, the
router is advertising the one with:
1. The lowest authoritative bit.
2. In case of tie, the lowest priority.
3. In case of tie, the highest router ID.
Note: That particular order (inverted compared to assignments'
priority) is motivated by the few cases where a router may
override an existing assignment by advertising an assignment of
higher priority. In such a case, the designated router should
remain the same.
Example: A new router is powered on and connected to another
router that was already there (doing DHCP). It sees the
assigned prefix for their common link, but also has, in its own
configuration, an authoritative assignment for the link. It
starts advertising the authoritative assignment, which causes
the second router to remove its previous assignment. Thanks to
the inverted order, the DHCP server will remain the same.
4.5.1. Sending Router Advertisement
On a given link, the designated router MUST send router
advertisements (RAs) including Prefix Information Options for all the
Chosen Prefixes associated to that link. SLAAC SHOULD be enabled
when possible, unless the configuration states otherwise. Prefixes
valid and preferred lifetimes MUST be set to values lower or equal to
the associated Delegated Prefix's valid and preferred lifetimes.
Whenever an IPv6 default route is present in the RIB, the designated
router MUST advertise itself as default router by specifying a
strictly positive valid lifetime. Whenever the last default route is
removed, the designated router MUST send an RA with the valid and
preferred lifetimes set to zero.
The designated router MUST advertise itself as a router for all IPv6
delegated prefixes using Route Information Options [RFC4191],
independently of whether there is a default route or not.
4.5.2. DHCP Server Operations
On a given link, whenever SLAAC can't be used for all assignments, or
DHCP configuration options must be provided to hosts, the designated
router MUST act as a DHCP server and serve addresses on the given
link. A router MUST stop behaving as a DHCP server whenever it is
not the link's designated router anymore.
Routers's addresses pool, specified in Section 7, MUST be excluded
from DHCP hosts pools.
The valid and preferred lifetimes MUST be set to values lower or
equal to the associated Delegated Prefix's valid and preferred
lifetimes.
4.6. Applying an Assignment on an Interface
Once a Chosen Prefix is created, a router first waits some time in
order to detect possible collisions (Section 8). Afterwards and if
no collision is detected, the prefix is applied as follows:
o The router updates its interface configuration so that the prefix
is assigned to the considered link.
o The router updates the routing protocol configuration so that it
starts advertising the prefix. Depending on the implementation,
this step may not be needed as the routing protocol directly gets
its configuration information from the interfaces configuration.
o If necessary, the router starts selecting an address for itself as
defined in Section 7.
o If the router is the designated router on the considered link, it
starts sending the Prefix Information Option with the considered
prefix, as specified in Section 4.5.1.
o If the router is the designated router on the considered link and
if the prefix requires DHCP configuration, it starts behaving as a
DHCP server, as defined in Section 4.5.2, for the considered
assigned prefix.
When a prefix assignment is removed, the previous steps MUST be
undone. The router MUST also deprecate the prefix, if it had been
advertised in Router Advertisements on an interface. The prefix is
deprecated by sending Router Advertisements with the PIO's preferred
lifetime set to 0 [RFC4861]. Hosts that support DHCP reconfigure
extension ([RFC3203], [RFC3315]) and that have been given leases MUST
be reconfigured as well.
4.7. DNS Support
DHCP options attached to each delegated prefixes and propagated
through the flooding protocol SHOULD contain the DHCP DNS options
provided by the ISP (when provided).
Whenever the router knows which DNS server to use, or is acting as a
DNS relay, it SHOULD include DNS DHCP options ([RFC3646]) within
host's configuration messages and include the Router Advertisement
DNS options ([RFC6106]) when sending RAs.
DNS server selection in multi-homed networks is a complex issue that
this document doesn't intend to solve. One should look at IETF's mif
working-group documents in order to obtain guidelines concerning DNS
server selection. It is RECOMMENDED that designated routers turns on
a local DNS relay that fetches information from provided DNS servers.
5. Flooding Protocol Requirements
In this document, the Flooding Protocol (FP) refers to a protocol
enabling information propagation to the whole network. It was not
specified in order to allow the working group to independently decide
which routing protocol, configuration protocol, and prefix assignment
method to use within the home network. Routing protocol, like OSPFv3
[RFC5340] (With its autoconf extension
[I-D.ietf-ospf-ospfv3-autoconfig]) or IS-IS [RFC5308], could be
extended in order to fulfill the requirements. An independent
protocol, for instance HNCP [I-D.ietf-homenet-hncp], could be used as
well.
The specified algorithm can use any protocol that fulfills the
requirements specified in this section.
5.1. Router ID
The FP MUST provide a router ID. ID collisions within the network
MUST be rare and any conflicts MUST be resolved by the flooding
protocol. When the router ID is changed, the FP MUST immediately
provide the new ID to the Prefix Assignment Algorithm, which will in
turn be run again, without requiring the current state to be flushed.
In the absence of collisions, the router ID MUST NOT be changed, and
it SHOULD be stable across reboots, power cycling and router software
updates.
5.2. Propagation Delay
The FP MUST provide an approximate upper bound of the time it takes
for an update to be propagated to the whole network. This value is
referred to as the FLOODING_DELAY. The algorithm ensures that, as
long as the upper bound is respected, two identical prefixes will
never be applied to different links, and two different prefixes will
never be applied to the same link. The algorithm and the network
will recover when the upper bound is exceeded, but collisions may
appear in the routing protocol and errors may be propagated to upper
layers.
If the FP supports link-local flooding, which is used for router's
address assignments, it SHOULD provide an approximate upper bound of
the time it takes for an update to be propagated to a single link.
This value is referred to as the FLOODING_DELAY_LL. If link-local
flooding is not available, or the value is not provided, the
assignment algorithm MUST use the FLOODING_DELAY value instead.
5.3. Flooding Assigned Prefixes
The FP MUST provide a way to flood Chosen Prefixes marked as
advertised and retrieve prefixes assigned by other routers (APs).
Retrieved APs MUST contain all the information specified in
Section 4.1.
5.4. Flooding Delegated Prefixes
The FP must provide a way to flood Delegated Prefixes and retrieve
prefixes delegated to other routers. Retrieved entries must contain
the following information.
Prefix: The delegated prefix.
Router ID: The router ID of the router that is advertising the
delegated prefix.
Valid until: A time value, in absolute local time, specifying the
prefix validity time.
Preferred until: A time value, in absolute local time, specifying
the prefix preferred time.
DHCP information: DHCP options attached to the delegated prefix.
The FP MUST make sure time values are consistent throughout the
network (i.e. differences are small compared to Delegated Prefixes
lifetimes). If no time synchronization protocol is used, the FP MUST
keep track of prefix age across the network and within its database.
5.5. Flooding Routers' Address Assignments
Routers addresses are dynamically allocated, picked from a defined
pool, and collisions must be detected using the FP. The FP MUST
provide a way to flood routers' addresses. The flooding scope of
those values SHOULD be link-local, but as addresses are unique within
the home network, this is not mandatory. For each address
assignment, the FP SHOULD provide the identifier of the interface
connected to the link the address assignment was advertised on.
6. Prefix Assignment Algorithm
The Prefix Assignment Algorithm is a distributed algorithm that
assigns one prefix from each available Delegated Prefix on every link
that is considered to be internal by at least one connected router.
The algorithm itself does not distinguish between global IPv6, ULA or
IPv4 prefixes. IPv4 prefixes are encoded as their IPv4-mapped IPv6
form, as defined in [RFC4291] (i.e. ::ffff:A.B.C.D/X with X >= 96).
When the Prefix Assignment Algorithm is executed, combinations of
Delegated Prefixes and internal interfaces are being considered. For
the purpose of this discussion, the Delegated Prefix will be referred
to as the current Delegated Prefix, and the interface will be
referred to as the current Interface. If a delegated prefix is
included inside another delegated prefix, it is ignored. This rule
intends to ignore prefixes delegated from non-Homenet routers that
previously obtained their larger prefix from one of Homenet's
routers.
The algorithm is specified here for the sake of clarity. It can be
optimized in some cases. For instance Prefix Assignment deletion
might not need to trigger algorithm's execution if all internal
interfaces already have assignements associated to the same Delegated
Prefix. Similarly, when an ignored Delegated Prefix is deleted, it
is not necessary to run the algorithm. An implementation may work
differently than specified here as long as the resulting behavior is
identical to the behavior a router implementing this exact algorithm
would have.
6.1. When to execute the Prefix Assignment Algorithm
The algorithm MUST be run whenever one of the following event occurs:
o A Delegated Prefix is created or deleted (A DP must be deleted
when its lifetime is exceeded).
o A Prefix Assignment is created, deleted or modified.
o The router ID is modified.
o An external link becomes internal, or an internal link becomes
external.
It is not required that the algorithm is synchronously run each time
such an event occurs. But the delay between the event and the
algorithm execution MUST be small compared to FLOODING_DELAY.
6.2. Assignment Precedence
An assignment is said to take precedence over another assignment
when:
o The authoritative bit value is higher.
o In case of tie, the priority value is higher.
o In case of tie, the advertising router's ID is higher.
6.3. Testing Assignment's validity
An Assigned Prefix or a Chosen Prefix is said to be valid if all the
following conditions are met:
1. Its prefix is included in an advertised Delegated Prefix.
2. The prefix is not included or does not include any other Assigned
Prefix with a higher precedence.
3. No other assignment which prefix is included in the same
Delegated Prefix, and with a higher precedence, is being
advertised on the same link.
6.4. Testing Assignment's availability
A prefix is said to be available if it does not overlap with any
other assignment by any other router in the network.
6.5. Accepting an Assigned Prefix
An AP is said to be accepted when the AP is currently being
advertised by a different router on a directly connected link, and
will be used by the accepting router as a new Chosen Prefix. When a
router accepts a neighbor's assignment, it starts a timer as
specified in Section 8. A new CP is created from the AP, with:
o The same prefix.
o The same link ID.
o The authoritative bit set to false. Link: An object the distributed algorithm will assign prefixes to.
A Node may only assign prefixes to Links it is directly connected
to. A Link is either Shared or Private.
o The same priority. Private Link: A Private Link is an abstract concept defined for the
sake of this document. It allows nodes to make assignments for
their private use or delegation. For instance, every DHCPv6-PD
[RFC3633] client MAY be considered as a different Private Link.
o The advertised bit value set as specified by the algorithm. Shared Link: A Link multiple nodes are connected to. Most of the
time, a Shared Link would consist in a multi-access link or point-
to-point link, virtual or physical, requiring prefixes to be
assigned to.
o The applied bit is unset. It is set when the timer elapsed if the Delegated Prefix: A prefix provided to the algorithm and used as a
entry still exists. prefix pool for Assigned Prefixes.
6.6. Making a New Assignment Node ID: A value identifying a given participating node. The set
of identifiers MUST be strictly and totally ordered (e.g.,
alphanumeric order).
In situations where a router can make an assignment (see Flooding Mechanism: A mechanism implementing reliable broadcast and
Section 6.9), the following rules are used in the following order: used to advertise published Assigned Prefixes.
1. If the configuration specifies a custom behavior (e.g. always Flooding Delay: Optional value provided by the Flooding Mechanism
ignore/accept a particular delegated prefix), use the indicating a deterministic or likely upper bound of the
configuration entry. information propagation delay. When the Flooding Mechanism does
not provide a value, it is set to DEFAULT_FLOODING_DELAY
(Section 7).
2. If the Delegated Prefix Preferred Lifetime is strictly greater Advertised Prefix: A prefix advertised by another node and
than zero, an assignment MUST be made. delivered to the local node by the Flooding Mechanism. It has an
Advertised Prefix Priority and, when assigned to a directly
connected Shared Link, is associated with a Shared Link.
3. If no other prefix has a non-zero Preferred Lifetime, and no Advertised Prefix Priority: A value that defines the priority of an
assignment is made on the link, an assignment SHOULD be made. Advertised Prefix received from the Flooding Mechanism or a
published Assigned Prefix. Whenever multiple Advertised Prefixes
are conflicting, all Advertised Prefixes but the one with the
greatest priority will eventually be removed. In case of tie, the
assignment advertised by the node with the greatest Node ID is
kept and others are removed. In order to ensure convergence, the
range of priority values MUST have an upper bound.
4. Otherwise, a new assignment SHOULD NOT be made. 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 ensures that there never is more than
one Assigned Prefix per Delegated Prefix and Link pair. When
destroyed, an Assigned Prefix is set as not applied, ceases to be
advertised, and is removed from the set of Assigned Prefixes.
When the algorithm decides to make a new assignment, it first needs Applied (Assigned Prefix): When an Assigned Prefix is applied, it
to specify the desired size of the assigned prefix. Although this MAY be used (e.g., for host configuration, routing protocol
algorithm intends to remain generic, the use of 64 bits long prefixes configuration, prefix delegation). When not applied, it MUST NOT
is RECOMMENDED (See [I-D.ietf-6man-why64]). The following table MAY be used for any other purposes than the prefix assignment
be used as default values, where X is the length of the delegated algorithm. Each Assigned Prefix is associated with a timer (Apply
prefix. Timer) used to apply the Assigned Prefix. An Assigned Prefix is
unapplied when destroyed.
If X <= 64: Prefix length = 64 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. It will appear as an Advertised Prefix to other nodes,
once received through the Flooding Mechanism.
If X >= 64 and X < 104: Prefix length = X + 16 (up to 2^16 links) Backoff Timer: Every Delegated Prefix and Link pair is associated
with a timer counting down to zero. It is used to avoid multiple
nodes from making colliding assignments by delaying the creation
of new Assigned Prefixes or the advertisement of adopted Assigned
Prefixes by a random amount of time.
If X >= 104 and X < 112: Prefix length = 120 (2^8 addresses per link Renumbering: Event occuring when an Assigned Prefix which was
and more than 2^8 links) applied is destroyed. It is undesirable as it usually implies
reconfiguring routers or hosts.
If X >= 112 and X <= 128: Prefix length = 120 + (X - 112)/2 (Link Vs 3. Applicability statement
Addresses tradeoff)
When the algorithm decides to make a new assignment, it SHOULD first Each node MUST have a set of disjoint Delegated Prefixes. It MAY
checks its stable storage for an available assignment that was change over time and be different from one node to another at some
previously applied on the current interface and is part of the point, but nodes MUST eventually agree on the same set of disjoint
current delegated prefix. If no available assignment can be found Delegated Prefixes.
that way, the new prefix MUST be randomly selected among a subset of
available prefixes (if possible, large enough to avoid collisions).
Hardware specific identifiers may be used to seed a pseudo-random Given this set of disjoint Delegated Prefixes, nodes may assign
generator. available prefixes from each Delegated Prefix to the Links they are
directly connected to. The algorithm ensures that at most one prefix
from a given Delegated Prefix is assigned to a given Link.
If no available prefix is found, the assignment fails. The algorithm can be applied to any address space and can be used to
manage multiple address spaces simultaneously. For instance, an
implementation can make use of IPv4-mapped IPv6 addresses [RFC4291]
in order to manage both IPv4 and IPv6 prefix assignment
simultaneously.
The algorithm leaves much room for implementation specific policies. The algorithm supports dynamically changing topologies:
For instance, static prefixes may be configured as specified in
Section 10. If implemented, the router MAY also decide to execute
the Prefix Scarcity Avoidance mechanisms, as proposed in Appendix A.
If an available prefix is found, a new assignment is made and a new o Nodes may join or leave the set of participating nodes.
Chosen Prefix entry is created.
o The prefix value is set to the chosen prefix. o Nodes may join or leave Links.
o The link ID is the ID of the link on which the assignment is made. o Links may be joined or split.
o The authoritative bit is set to false. All nodes MUST run a common Flooding Mechanism in order to share
published Assigned Prefixes. The set of participating nodes is
defined as the set of nodes participating in the Flooding Mechanism.
o The priority is set to a value between PRIORITY_AUTO_MIN and The Flooding Mechanism MUST:
PRIORITY_AUTO_MAX (Section 6.8).
o The advertised bit is set. o 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 which advertises it.
o The applied bit is unset. It is set when the timer elapsed if the o Specify whether an Advertised Prefix was assigned to a directly
entry still exists. connected Shared Link, and if so, on which one.
A new assignment is always marked as advertised when created and In addition, a Flooding Delay SHOULD be specified and respected in
therefore immediately provided to the flooding protocol. order to avoid undesired renumbering. If not specified, or whenever
the Flooding Mechanism is unable to respect the provided delay,
renumbering may happen. As such delay often depends on the size of
the network, it MAY change over time and MAY be different from one
node to another.
6.7. Using Authoritative Prefix Assignments The algorithm ensures that whenever the Flooding Delay is provided
and respected, and in the absence of topology change or delegated
prefix removal, renumbering never happens.
When some authority (Delegating router, system admin, etc...) wants Each node MUST have a Node ID. Node IDs MAY change over time and be
to manually enforce some behavior, it may ask some router to make an the same on multiple nodes at some point, but each node MUST
Authoritative Prefix Assignment. Such assignments have their eventually have a Node ID which is unique among the set of
Authoritative bit set, SHALL NOT be overridden, and will appear in participating nodes.
other router's database as Assigned Prefixes with the Authoritative
bit set.
There are two kinds of Authoritative Prefix Assignments. 4. Algorithm Specification
o When an authority wants to assign some particular prefix to some This section specifies the behavior of nodes implementing the prefix
interface, an Authoritative Prefix Assignment MAY be created and assignment algorithm.
consists in a Chosen Prefix which have its Authoritative bit set
and which is advertised. Just like normal assignments, it MUST
NOT be applied before the delay specified in Section 8 elapsed.
o When an authority wants to prevent some prefix from being used, an 4.1. Algorithm Terminology
Authoritative Assignment MAY be advertised. Such assignments MUST
NOT be applied and MUST be advertised through the flooding
protocol as assigned to either no-interface, or a fake interface
(Depending on the flooding protocol's capabilities).
When a delegated prefix is obtained through DHCPv6 PD with a non- The algorithm makes use of the following terms:
empty excluded prefix, as specified in [RFC6603], an Authoritative
Prefix Assignment MUST be created with the excluded prefix.
Note: If the router doesn't understand the excluded prefix DHCPv6 Current Assignment: For a given Delegated Prefix and Link, the
option, the delegated prefix is ignored, as specified in Current Assignment is the Assigned Prefix (if any) included in the
Section 4.3. Delegated Prefix and assigned to the given Link.
6.8. Choosing the Assignment's Priority Best Assignment: For a given Delegated Prefix and Link, the Best
Assignment is (if any) the Advertised Prefix:
When either a new Prefix Assignment is made, or an Authoritative * Including or included in the Delegated Prefix.
Prefix Assignment is created, the creating router needs to choose
which priority value to use. The assignment priority is kept by the
designated router when it starts advertising the assignment, and is
useful when not enough prefixes are available.
o PRIORITY_DEFAULT SHOULD be used as default. * Assigned on the given Link.
o Other values between PRIORITY_AUTO_MIN and PRIORITY_AUTO_MAX MAY * Having the greatest Advertised Prefix Priority among Advertised
be dynamically chosen by the implementation. Prefixes (and, in case of tie, the prefix advertised by the
node with the greatest Node ID among all prefixes with greatest
priority).
o Other values between PRIORITY_AUTHORITY_MIN and * Taking precedence over the Current Assignment (if any)
PRIORITY_AUTHORITY_MAX MUST NOT be used if not specified by an associated with the same Link and Delegated Prefix.
authority (by static or dynamic configuration).
o Other values are reserved. Precedence: An Advertised Prefix takes precedence over an Assigned
Prefix if and only if:
6.9. Prefix Assignment Algorithm steps * The Assigned Prefix is not published.
At the beginning of the algorithm, all assignments that do not have * The Assigned Prefix is published and the Advertised Prefix
their Authoritative bit set are marked as 'invalid', and the router Priority from the Advertised Prefix is strictly greater than
computes for each connected link whether it is the designated router, the Advertised Prefix Priority from the Assigned Prefix.
as specified in Section 4.5.
The following steps are then executed for every combination of * The Assigned Prefix is published, the priorities are equal, and
delegated prefixes and interfaces. the Node ID from the node advertising the Advertised Prefix is
strictly greater than the local Node ID.
o If the current interface is external, ignore that interface. Valid (Assigned Prefix) An Assigned Prefix is valid if and only if
the two following conditions are met:
o If the Delegated Prefix is strictly included in another Delegated * No Advertised Prefix including or included in the Assigned
Prefix, ignore that delegated prefix. Prefix takes precedence over the Assigned Prefix.
o If the Delegated Prefix is equal to another Delegated Prefix, * No Advertised Prefix including or included in the same
advertised by some router with an higher router ID than the Delegated Prefix as the Assigned Prefix and assigned to the
considered delegated prefix, ignore that delegated prefix. same Link takes precedence over the considered Assigned Prefix.
o Look for a valid Assigned Prefix, advertised by another router on 4.2. Prefix Assignment Algorithm Routine
the current interface and included in the current Delegated
Prefix.
o Look for a Chosen Prefix associated to the current interface and This section specifies the prefix assignment algorithm routine. It
included in the current Delegated Prefix. is defined for a given Delegated Prefix/Link pair and may be run
either as triggered by the Backoff Timer, or not.
o There are four possibilities at this stage. For a given Delegated Prefix and Link pair, the routine MUST be run
as not triggered by the Backoff Timer whenever:
1. If no AP is found, and no CP is found, a new assignment can be o An Advertised Prefix including or included in the considered
made if and only if the router considers itself as the Delegated Prefix is added or removed.
designated router. Whether to create an assignment or not,
and which prefix to use, is specified in Section 6.6.
2. If an AP is found, and no CP is found, the AP MUST be o An Assigned Prefix included in the considered Delegated Prefix and
accepted. The new CP's advertised bit MUST be set if and only associated with a different Link than the considered Link was
if the router considers itself as the designated router. 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.
3. If no AP is found, and a CP is found, the router MUST check if o The considered Delegated Prefix is added.
the CP's assignment is valid. If it is, the local assignment
is marked as valid and advertised. If it isn't, it is
destroyed and the algorithm applies case 1.
4. If both an AP and a CP are found, the router must check if the o The considered Link is added.
prefixes are the same. If they are different and if the CP's
Authoritative bit is not set, the CP MUST be deleted and the
algorithm applies case 2. If the prefixes are the same, the
CP must be updated with the AP's priority value, marked as
valid, and advertised if and only if the router considers
itself as designated on the link.
In the end all the assignments that are marked as invalid are o The Node ID is modified.
deleted.
6.10. Downstream DHCPv6 Prefix Delegation support Additionaly, for a given Delegated Prefix and Link pair, the routine
MUST be run as triggered by the Backoff Timer whenever:
If some host or non-Homenet router asks for Delegated Prefixes, a o The Backoff Timer associated with the considered Delegated Prefix/
router MAY assign a set of prefixes and give them to the client. Link pair fires while there is no Current Assignment associated
Such assignments MUST be advertised as either not assigned on any with the given pair.
link, or assigned on a stub virtual link connected to the router,
depending on the Flooding Protocol capabilities. By default
assignments priorities MUST be between PRIORITY_AUTO_MIN and
PRIORITY_AUTO_MAX, SHOULD be lower than PRIORITY_DEFAULT, and the
authoritative bit MUST not be set. Whenever such an assignment
becomes invalid, DHCPv6 Reconfigure SHOULD be used in order to remove
the prefix from DHCPv6 DP client's lease. If DHCPv6 Reconfigure is
not supported, leases lifetimes SHOULD be significantly small.
Provided DPs' valid and preferred lifetimes MUST be lower or equal to When such an event occurs, a node MAY delay the execution of the
their associated Delegated Prefix's lifetimes, and associated DHCPv6 routine instead of executing it immediately, e.g. while receiving an
data SHOULD be provided to the DHCPv6 PD client. update from the Flooding Mechanism, or for security reasons (see
Section 8). Even though other events occur in the meantime, the
routine MUST be run only once. It is also assumed that, whenever one
of these events is the Backoff Timer firing, the routine is executed
as triggered by the Backoff Timer.
By default, an assigned prefix SHOULD NOT be provided to a DHCPv6 PD In order to execute the routine for a given Delegated Prefix/Link
client before the apply timeout has elapsed. But in order to allow pair, first look for the Best Assignment and Current Assignment
faster response delay, a lease MAY first be provided with a lifetime associated with the Delegated Prefix/Link pair, then execute the
of 2*FLOODING_DELAY seconds, even if the private assignments' apply corresponding case:
timeout has not elapsed yet.
7. Address Assignment Algorithm 1. If there is no Best Assignment and no Current Assignment: Decide
whether the creation of a new assignment for the given Delegated
Prefix/Link pair is desired (As any result would be valid, the
way the decision is taken is out of the scope of this document)
and do the following:
IPv6 routers always get at least one link-local address per link. * If it is not desired, stop the execution of the routine.
Routing protocols and link DHCP servers are able to run with these
addresses. In some cases though, a router may need to take one or
multiple addresses among one or multiple available Delegated
Prefixes. For example:
o The router needs connectivity to the internet (For management, NTP * Else if the Backoff Timer is running, stop the execution of
synchronization, etc...). the routine.
o The router needs connectivity within the home network (For * Else if the routine was not executed as triggered by the
management, DNS communications, etc...). Backoff Timer, 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 routine.
o IPv4 addresses are needed (DHCPv4, v4 link-local connectivity, * Else, continue the execution of the routine.
etc...).
When possible, SLAAC MUST be used. In other cases a different Select a prefix for the new assignment (see Section 5 for
mechanism is necessary for routers to get addresses. This document guidance regarding prefix selection). This prefix MUST be
proposes an Address Assignment Algorithm that extends the Prefix included in or be equal to the considered Delegated Prefix and
Assignment Algorithm and works as follows. Each prefix assignment is MUST NOT include or be included in any Advertised Prefix. If a
associated with a fixed address pool, reserved for router's addresses suitable prefix is found, use it to create a new Assigned Prefix:
assignment. The address pool is a prefix which value is
deterministically function of the assigned prefix. A router MAY, at
any time, decide to assign itself an address from any of its Chosen
Prefixes. Just like prefix assignments, address assignments are
advertised to other routers and collisions are detected. Routers
MUST keep track of Address Assignments made by other routers on
connected links by using information provided by the flooding
algorithm, as defined in Section 5.5.
7.1. Router's address pools * Assigned to the considered Link.
Given an assigned prefix A/X (where all A's latest '128 - X'th bits * Not applied.
are set to 0), the routers reserved address pool is defined as
follows:
If X <= 64: SLAAC MUST be used * The Apply Timer set to '2 * Flooding Delay'.
If X > 64 and X <= 110: The pool is A/112 (2^16 addresses) * Published with some selected Advertised Prefix Priority.
If X >= 110 and X <= 126: The pool is A/(X + 2) (One quarter of the 2. If there is a Best Assignment but no Current Assignment: Cancel
available addresses) the Backoff Timer and use the prefix from the Best Assignment to
create a new Assigned Prefix:
If X >= 126: Only the designated router MAY use A/128. Other * Assigned to the considered Link.
routers MUST NOT get an address.
In the case of IPv4 prefixes, the network address (first address of * Not applied.
the address pool) MUST not be used.
7.2. Address Assignment Algorithm * The Apply Timer set to '2 * Flooding Delay'.
In this section, we say an address assignment is made by some router * Not published.
when it intends to use, or is using the address specified by this
assignment. An assignment, made by some router, MUST be advertised
on the link on which the assignment is made. Similarly, an address
assignment is said to be applied when the address is pushed to the
router's interface configuration. It is unapplied otherwise.
Routers MUST store applied address assignments in their stable 3. If there is a Current Assignment but no Best Assignment:
storage and reuse the same addresses whenever possible. At least the
five previously applied addresses SHOULD be stored for each
interface.
For a given prefix assignment, an address is said to be available if * If the Current Assignment is not valid, destroy it, and
it is within the router's address pool associated to the prefix execute the routine again, as not triggered by the Backoff
assignment, and it is not being advertised by any other router. If Timer.
the flooding protocol provides interface identifier in the address
assignments, looking for collisions on considered link is enough.
A new address assignment MUST be chosen randomly among available * If the Current Assignment is valid and published, stop the
addresses. An address assignment MUST NOT be applied when one of the execution of the routine.
following condition is true.
o The associated Chosen Prefix is not applied. * If the Current Assignment is valid and not published, the node
MAY either:
o The timer specified in Section 8 has not elapsed yet. + Adopt the prefix by cancelling 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.
An address assignment must be deleted whenever one of the following + Destroy it and execute case 1 in order to create a
condition becomes true. different assignment.
o The associated Chosen Prefix is deleted or moved to another link. 4. If there is a Current Assignment and a Best Assignment:
o Some other router with a higher router ID is advertising the same * Cancel the Backoff Timer.
address on the same link.
8. Hysteresis Principle * 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'.
The IPv6 Stateless Address Autoconfiguration [RFC4862] states that * If the two prefixes are not identical, destroy the Current
host addresses can be kept up to 2 hours after a Router Advertisement Assignment and go to case 2.
wit zero lifetime is received. Therefore, routers must be carefull
before assigning or deprecating a prefix.
8.1. Prefix and Address assignments When the prefix assignment algorithm routine 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 the algorithm is operating in, or leave it
as implementation-specific.
When the flooding protocol is started, the router MUST wait When the prefix assignment algorithm routine requires an assignment
FLOODING_DELAY before executing the prefix assignment algorithm for to be created or adopted, the chosen Advertised Prefix Priority is
the first time. unspecified (any value would be valid). The values to be used in
such situations MAY be specified by other documents making use of the
prefix assignment algorithm or be left as an implementation specific
choice.
Prefix and address assignment algorithms are distributed. Collisions 4.3. Overriding and Destroying Existing Assignments
may occur, but network configuration, routing protocols or upper
layers should not suffer from these collisions. For this reason, all
assignments that could imply collisions are not immediately applied.
o A router MUST NOT apply a Chosen Prefix before it has waited In addition to the behavior specified in Section 4.2, the following
2*FLOODING_DELAY. If the entry is valid during the whole waiting procedures MAY be used in order to provide more advanced behavior
time, it MUST be applied to the link it is assigned. (Section 6):
o A router MUST NOT apply an Assigned Address before it has waited Overriding Existing Assignments: For any given Link and Delegated
2*FLOODING_DELAY_LL. If the assignment is valid during the whole Prefix, a node MAY create a new Assigned Prefix using a chosen
waiting time, it MUST be applied to the interface it is assigned. prefix and Advertised Prefix Priority such that:
8.2. Delegated Prefixes * The chosen prefix is included in or is equal to the considered
Delegated Prefix.
Some links may be unreliable, causing repetitive connectivity loss. * The Current Assignment, if any, as well as all existing
Such links shouldn't cause IP reconfiguration. Assigned Prefixes which include or are included inside the
chosen prefix are destroyed.
8.2.1. Unreliable uplink * It is not applied.
When a router detects uplink connectivity loss, Delegated Prefixes' * The Apply Timer set to '2 * Flooding Delay'.
lifetimes from prefixes obtained through the uplink MUST be modified
in the following way.
o The Preferred Lifetime is set to 0. * It is published.
o The Valid Lifetime is set to the minimum between the current Valid * The Advertised Prefix Priority is greater than the Advertised
Lifetime and two hours. Prefix Priority from all Advertised Prefixes which include or
are included in the chosen prefix.
o The default route associated with the prefix is not advertised In order to ensure algorithm convergence:
anymore.
This behavior is similar to [RFC7084] specifications and provides * Such overriding assignments MUST NOT be created unless there
stable host configuration in case of unreliable uplink. was a change in the node configuration, a Link was added, or an
Advertised Prefix was added or removed.
8.2.2. Unreliable in-home link * 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 which do not respect this rule
MUST implement a mechanism which detects whether the
distributed algorithm do not converge and, whenever this would
happen, stop creating overriding Assigned Prefixes causing the
destruction of other Assigned Prefixes. The specifications for
such safety procedures are out of the scope of this document.
When a router stops advertising a Delegated Prefix, it MUST first Removing an Assigned Prefix: A node MAY destroy any Assigned Prefix
deprecate that Delegated Prefix by advertising it for which is published. Such an event reflects the desire from a node
DP_DEPRECATE_FACTOR*FLOODING_DELAY seconds with zero valid and to not assign a prefix from a given Delegated Prefix to a given
preferred lifetimes. Link anymore. In order to ensure algorithm convergence, such
procedure MUST NOT be executed unless there was a change in the
node configuration. Additionally, whenever an Assigned Prefix is
destroyed this way, the prefix assignment algorithm routine MUST
be run for the Delegated Prefix/Link pair associated with the
deleted Assigned Prefix.
When a router receives a deprecated Delegated Prefix advertisement These procedures are optional. They could be used for diverse
from the Flooding Protocol, it MUST remove the Delegated Prefix from purposes, e.g., for providing custom prefix assignment configuration
its Delegated Prefixes list. or reacting to prefix space exhaustion (by overriding short Assigned
Prefixes and assigning longer ones).
When a router stops receiving a Delegated Prefix from the Flooding 4.4. Other Events
Protocol, it SHOULD keep using that delegating prefix up to a period
of min(remaining Valid Lifetime, DP_KEEP_ALIVE_TIME) seconds.
9. ULA and IPv4 Prefixes Generation When the Apply Timer fires, the associated prefix MUST be applied.
Although DHCPv6 PD and static configuration are regular means of When the Backoff Timer associated with a given Delegated Prefix/Link
obtaining IPv6 prefixes, routers MAY, in some cases, autonomously pair fires while there is a Current Assignment associated with the
decide to generate a delegated prefix. In this section are specified same pair, the Current Assignment MUST be published with some
when and how IPv6 ULA prefixes and IPv4 private prefixes may be associated Advertised Prefix Priority and, if the prefix is not
autonomously generated. applied, the Apply Timer MUST be set to '2 * Flooding Delay'.
9.1. ULA Prefix Generation When a Delegated Prefix is removed from the set of Delegated
Prefixes, all Assigned Prefixes included in the removed Delegated
Prefix MUST be destroyed.
ULA prefixes can be randomly generated as specified in [RFC4193], When one Delegated Prefix is replaced by another one that includes or
enabling stable in-home IPv6 connectivity. is included in the deleted Delegated Prefix, all Assigned Prefixes
which were included in the deleted Delegated Prefix but are not
included in the added Delegated Prefix MUST be destroyed. Others MAY
be kept.
In this section, we say a ULA delegated prefix is 'stable' if it has When a Link is removed, all Assigned Prefixes assigned to that Link
been the only advertised ULA delegated prefix for at least MUST be destroyed.
2*FLOODING_DELAY seconds. The behaviour specified in the following
sections tend to reuse a stable ULA prefix as long as its preferred
lifetime is not null.
Additionaly, we say a router is the owner of a spontaneously 5. Prefix Selection Considerations
generated ULA prefix if it randomly created the prefix in the first
place. A router SHOULD NOT create more than one prefix this way, and
MUST remember all the prefixes they own. As stated in the following
sections, only the owner of a prefix can extend its lifetimes.
9.1.1. Choosing the ULA prefix When the prefix assignment algorithm routine specified in Section 4.2
requires a new prefix to be selected, the prefix MUST be selected
either:
When a stable ULA prefix is advertised, all routers SHOULD remember o Among prefixes which were previously assigned and applied on the
that prefix alongwith its associated valid and preferred lifetime. considered Link.
If this prefix stops being advertised (e.g. due to a network split)
while its preferred lifetime is not null, the same ULA prefix SHOULD
be selected using the same valid and preferred lifetimes.
If there was no stable ULA prefix advertised, or if the preferred o Randomly, picked in a set of at least RANDOM_SET_SIZE (see
lifetime of the prefix was null, a prefix generated as specified in Section 7) candidate prefixes. If less than RANDOM_SET_SIZE
[RFC4193] SHOULD be used. In case the stable storage can't be used candidates can be found, the prefix MUST be picked among all
or the current date cannot be determined, the prefix MAY be pseudo- candidates.
randomly generated based on hardware specific values.
9.1.2. Advertising a ULA prefix o Based on some custom selection process specified in the
configuration.
A router MAY start advertising a ULA prefix whenever the two A simple implementation MAY randomly pick the prefix among all
following conditions are met: available prefixes, but this strategy is inefficient in terms of
address space use as a few long prefixes may exhaust the pool of
available short prefixes.
o It is the network leader. The rest of this section describes a more efficient approach which
MAY be applied any time a node needs to pick a prefix for a new
assignment. The two following definitions are used:
o There is no other advertised ULA prefix. Available prefix: The prefix A/N is available if and only if A/N
does not include and is not included in any Assigned or Advertised
Prefix but A/(N-1) does include or is included in an Assigned or
Advertised Prefix (or N equals 0 and there is no Assigned or
Advertised Prefixes at all).
If no IPv6 prefix is available at all, the network leader SHOULD Candidate prefix: A prefix which is included in or is equal to an
start advertising a ULA delegated prefix. available prefix.
Additionaly, a router SHOULD start advertising its own ULA prefix The procedure described in this section takes the three following
whenever the three following conditions are met: criteria into account:
o A stable ULA prefix is advertised by another router. Stability: In some cases, it is desirable that the selected prefix
remains the same across executions and reboots. For this purpose,
prefixes previously applied on the Link or pseudo-random prefixes
generated based on node and Link specific values may be
considered.
o The router owns the advertised stable ULA prefix. Randomness: When no stored or pseudo-random prefix is chosen, a
prefix may be randomly picked among RANDOM_SET_SIZE candidates of
desired length. If less than RANDOM_SET_SIZE candidates can be
found, the prefix is picked among all candidates.
o The preferred lifetime of the advertised ULA prefix is below 10 Addressing-space usage efficiency: In the process of assigning
minutes. prefixes, a small set of badly chosen long prefixes may easily
prevent any shorter prefix from being assigned. For this reason,
the set of RANDOM_SET_SIZE candidates is created from the set of
available prefixes with longest prefix lengths and, in case of
tie, prefer small prefix values.
This allows a router to restart advertising a owned prefix whenever When executing the procedure, do as follows:
the preferred lifetime is approaching zero. Which later allows him
to extend the lifetime of the prefix.
A router MUST stop advertising a spontaenously generated ULA prefix 1. For each prefix stored in stable-storage, check if the prefix is
whenever one of the two following condition is met: included in or equal to an available prefix. If so, pick that
prefix and stop.
o A different ULA prefix is being advertised. 2. For each prefix length, count the number of available prefixes of
the given length.
o The same prefix is advertised by another router, and the router 3. If the desired prefix length was not specified, select one. The
doesn't own that prefix. available prefixes count computed previously may be used to help
picking a prefix length such that:
9.1.3. Extending prefix lifetime * There is at least one candidate prefix.
Routers MUST regularly extend the valid and preferred lifetimes of * The prefix length is chosen great enough to not exhaust the
the ULA delegated prefix they advertise and own, so that they never address space.
drop to zero.
When a router advertises a prefix it doesn't own, lifetimes are never Let N be the chosen prefix length.
extended. When the preferred lifetime of the prefix approaches zero,
either the owner of the prefix will start advertising the prefix with
a non-zero preferred lifetime, or a new prefix will be generated.
9.1.4. Authoritative ULAs 4. Iterate over available prefixes starting with prefixes of length
N down to length 0 and create a set of RANDOM_SET_SIZE candidate
prefixes of length exactly N included in or equal to available
prefixes. The end goal here is to create a set of
RANDOM_SET_SIZE candidate prefixes of length N included in a set
of available prefixes of maximized prefix length. In case of a
tie, smaller prefix values (as defined by the bit-wise
lexicographical order) are preferred.
This section doesn't prevent multiple ULA prefixes from existing 5. For each pseudo-random prefix, check if the prefix is equal to a
simultaneously. ULA prefixes may be provided by different means, as candidate prefix. If so, pick that prefix and stop.
specified in Section 4.3. Delegated prefixes that are delegated by a
service provider or provisioned by an authority differ from
'spontaneously' generated prefixes. They MUST NOT be withdrawn if
another ULA delegated prefix is observed.
When at least one of such ULA prefixes is used, spontaneously 6. Choose a random prefix from the set of selected candidates.
generated ULA prefixes are withdrawned.
9.2. IPv4 Private Prefix Generation The complexity of this procedure is equivalent to the complexity of
iterating over available prefixes. Such operation may be
accomplished in linear time, e.g., by storing Advertised and Assigned
Prefixes in a binary trie.
A router MAY generate an IPv4 prefix when the two following 6. Implementation Capabilities and Node Behavior
conditions are met.
o It has an IPv4 address with global connectivity. Implementations of the prefix assignment algorithm may vary from very
basic to highly customisable, enabling different types of fully
interoperable behaviors. The three following behaviors are given as
examples:
o No other IPv4 delegated prefix is advertised by any other router. Listener: The node only acts upon assignments made by other nodes,
i.e, it never creates new assignments nor adopt existing ones.
Such behavior does not require the implementation of the
considerations specified in Section 5 or Section 4.3. The node
never checks existing assignments validity, which makes this
behavior particularly suited to lightweight devices which can rely
on more capable neighbors to make assignments on directly
connected Shared Links.
A router MUST stop advertising an IPv4 prefix whenever another router Basic: The node is capable of assigning new prefixes or adopting
with an higher router ID is advertising an IPv4 Delegated Prefix. prefixes which do not conflict with any other existing assignment.
Such behavior does not require the implementation of the
considerations specified in Section 4.3. It is suited to
situations where there is no preference over which prefix should
be assigned to which Link, and there is no priority between
different Links.
The IPv4 private prefix must be included in one of the private Advanced: The node is capable of assigning new prefixes, adopting
prefixes defined in [RFC1918]. The prefix 10/8 SHOULD be used by existing ones, making overriding assignments and destroying
default but it SHOULD be configurable. In the case the address existing ones. Such behavior requires the implementation of the
provided by the ISP is already a private address, a different private considerations specified in Section 5 and Section 4.3. It is
prefix SHOULD be used. For instance, if the ISP is giving the suited when the administrator desires some particular prefix to be
address 10.1.2.3, 10/8 or any sub-prefix included in 10/8 SHOULD NOT assigned on a given Link, or some Links to be assigned prefixes
be used. (For instance, 172.16/12 or 192.168/16 can be selected). with a higher priority.
10. Manageability Considerations 7. Algorithm Parameters
The algorithm leaves much room for implementation specific features. This document does not provide values for ADOPT_MAX_DELAY,
For instance, ULA prefix as well IPv4 prefix generation may be BACKOFF_MAX_DELAY and RANDOM_SET_SIZE. The algorithm ensures
disabled whenever a global IPv6 is made available. This section convergence and correctness for any chosen values, even when these
details a few other possible configuration options. are different from node to node. They MAY be adjusted depending on
the context, providing a tradeoff between convergence time, efficient
addressing, low verbosity (less traffic is generated by the Flooding
Mechanism), and low collision probability.
The implementation MAY allow each internal interface to be configured ADOPT_MAX_DELAY (respectively BACKOFF_MAX_DELAY) represents the
with a custom priority value. The specified priority SHOULD then be maximum backoff time a node may wait before adopting an assignment
used when creating new assignments on the given interface. If not (respectively making a new assignment). BACKOFF_MAX_DELAY MUST be
specified, the default priority SHOULD be used. greater than or equal to ADOPT_MAX_DELAY. The greater
ADOPT_MAX_DELAY and (BACKOFF_MAX_DELAY - ADOPT_MAX_DELAY), the lower
the collision probability and the verbosity, but the longer the
convergence time.
The implementation SHOULD allow manual assignments on given links. RANDOM_SET_SIZE represents the desired size of the set a random
When specified, and whenever such an assignment is valid, it MUST be prefix will be picked from. The greater RANDOM_SET_SIZE, the better
advertised as Authoritative Assignments on the given interface. the convergence time and the lower the collision probability, but the
worse the addressing-space usage efficiency.
11. Documents Constants When the Flooding Mechanism does not provide a Flooding Delay, it is
set to DEFAULT_FLOODING_DELAY. As participating nodes do not need to
agree on a common Flooding Delay value, this default value MAY be
different from one node to another. If the context in which the
algorithm is used does not suffer from renumbering, the value 0 MAY
be used. Otherwise it depends on the Flooding Mechanism properties
and the desired renumbering probability, and is therefore out of
scope of this document.
PRIORITY_MIN 0 8. Security Considerations
PRIORITY_AUTHORITY_MIN 4
PRIORITY_AUTO_MIN 6
PRIORITY_DEFAULT 8
PRIORITY_AUTO_MAX 10
PRIORITY_AUTHORITY_MAX 12
PRIORITY_MAX 15
DP_DEPRECATE_FACTOR 3 The prefix assignment algorithm functions on top of two distinct
DP_KEEP_ALIVE_TIME 60 seconds mechanisms, the Flooding Mechanism and the Node ID assignment
mechanism. In order to operate securely:
12. Security Considerations An attacker able to publish Advertised Prefixes through the
flooding mechanism may perform the following attacks:
Prefix assignment algorithm security entirely relies on flooding * Publish a single overriding assignment for a whole Delegated
protocol security features. The flooding protocol SHOULD therefore Prefix or for the whole address space, thus preventing any node
check for the authenticity of advertised information. Security modes from assigning prefixes to Links.
may be classified in three categories.
1. The flooding protocol is not protected. * Quickly publish and remove Advertised Prefixes, generating
traffic at the Flooding Mechanism layer and causing multiple
executions of the prefix assignment algorithm in all
participating nodes.
2. The flooding protocol's protection is binary: An allowed router * Publish and remove Advertised Prefixes in order to prevent the
may send any type of packets in the name of other routers. convergence of the execution.
3. All advertised messages are individually signed by the sender. An attacker able to prevent other nodes from accessing a portion
or the whole set of Advertised Prefixes may compromise the
correctness of the execution.
Whenever a malicious router attacks an unprotected network, or An attacker able to cause repetitive Node ID changes may induce
whenever a malicious router is able to authenticate itself to a traffic generation from the Flooding Mechanism and multiple
network as stated in the second case, it may for example: executions of the prefix assignment algorithm in all participating
nodes.
o Prevent other routers to get a stable router ID. An attacker able to publish Advertised Prefixes using a Node ID
used by another node may prevent the correctness and convergence
of the execution.
o Prevent other routers from making assignments by claiming the Whenever the security of the Flooding Mechanism and Node ID
whole available address space. assignment mechanism could not be ensured, the convergence of the
execution may be prevented. In environments where such attacks may
be performed, the execution of the prefix assignment algorithm
routine SHOULD be rate limited, as specified in Section 4.2.
o Redirect traffic to some router on the network. 9. IANA Considerations
If a malicious router is able to authenticate itself in a network This document has no actions for IANA.
protected as in the third case, most of the previously listed attacks
may still be performed, but traffic could only be redirected toward
the origination of the attack, and the source of the attack could be
identified.
In any case, in order to protect the network, the routing protocol as 10. Acknowledgments
well as the way hosts are configured also needs to be protected,
hence requiring other link (e.g. WPA) or IP layer (e.g. IPSec-Auth
[RFC4302] or SeND [RFC3971]) security solutions.
13. References The authors would like to thank those who participated in the
previous document's version development as well as the present one.
In particular, the authors would like to thank 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 and Steven Barth for interesting discussions and
document review.
13.1. Normative References 11. References
[RFC1918] Rekhter, Y., Moskowitz, R., Karrenberg, D., Groot, G., and 11.1. Normative References
E. Lear, "Address Allocation for Private Internets", BCP
5, RFC 1918, February 1996.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997. Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2131] Droms, R., "Dynamic Host Configuration Protocol", RFC 11.2. Informative References
2131, March 1997.
[RFC3203] T'Joens, Y., Hublet, C., and P. De Schrijver, "DHCP
reconfigure extension", RFC 3203, December 2001.
[RFC3315] Droms, R., Bound, J., Volz, B., Lemon, T., Perkins, C., [RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing
and M. Carney, "Dynamic Host Configuration Protocol for Architecture", RFC 4291, February 2006.
IPv6 (DHCPv6)", RFC 3315, July 2003.
[RFC3633] Troan, O. and R. Droms, "IPv6 Prefix Options for Dynamic [RFC3633] Troan, O. and R. Droms, "IPv6 Prefix Options for Dynamic
Host Configuration Protocol (DHCP) version 6", RFC 3633, Host Configuration Protocol (DHCP) version 6", RFC 3633,
December 2003. December 2003.
[RFC3646] Droms, R., "DNS Configuration options for Dynamic Host Appendix A. Static Configuration Example
Configuration Protocol for IPv6 (DHCPv6)", RFC 3646,
December 2003.
[RFC4191] Draves, R. and D. Thaler, "Default Router Preferences and
More-Specific Routes", RFC 4191, November 2005.
[RFC4193] Hinden, R. and B. Haberman, "Unique Local IPv6 Unicast
Addresses", RFC 4193, October 2005.
[RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing
Architecture", RFC 4291, February 2006.
[RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman,
"Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
September 2007.
[RFC4862] Thomson, S., Narten, T., and T. Jinmei, "IPv6 Stateless
Address Autoconfiguration", RFC 4862, September 2007.
[RFC6106] Jeong, J., Park, S., Beloeil, L., and S. Madanapalli,
"IPv6 Router Advertisement Options for DNS Configuration",
RFC 6106, November 2010.
[RFC6603] Korhonen, J., Savolainen, T., Krishnan, S., and O. Troan,
"Prefix Exclude Option for DHCPv6-based Prefix
Delegation", RFC 6603, May 2012.
13.2. Informative References
[RFC3971] Arkko, J., Kempf, J., Zill, B., and P. Nikander, "SEcure
Neighbor Discovery (SEND)", RFC 3971, March 2005.
[RFC4302] Kent, S., "IP Authentication Header", RFC 4302, December
2005.
[RFC5308] Hopps, C., "Routing IPv6 with IS-IS", RFC 5308, October
2008.
[RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF
for IPv6", RFC 5340, July 2008.
[RFC5969] Townsley, W. and O. Troan, "IPv6 Rapid Deployment on IPv4
Infrastructures (6rd) -- Protocol Specification", RFC
5969, August 2010.
[RFC6241] Enns, R., Bjorklund, M., Schoenwaelder, J., and A.
Bierman, "Network Configuration Protocol (NETCONF)", RFC
6241, June 2011.
[RFC7084] Singh, H., Beebee, W., Donley, C., and B. Stark, "Basic
Requirements for IPv6 Customer Edge Routers", RFC 7084,
November 2013.
[I-D.ietf-homenet-arch]
Chown, T., Arkko, J., Brandt, A., Troan, O., and J. Weil,
"IPv6 Home Networking Architecture Principles", draft-
ietf-homenet-arch-11 (work in progress), October 2013.
[I-D.ietf-homenet-hncp]
Stenberg, M. and S. Barth, "Home Networking Control
Protocol", draft-ietf-homenet-hncp-00 (work in progress),
April 2014.
[I-D.ietf-ospf-ospfv3-autoconfig]
Lindem, A. and J. Arkko, "OSPFv3 Auto-Configuration",
draft-ietf-ospf-ospfv3-autoconfig-06 (work in progress),
February 2014.
[I-D.ietf-6man-why64]
Carpenter, B., Chown, T., Gont, F., Jiang, S., Petrescu,
A., and A. Yourtchenko, "Analysis of the 64-bit Boundary
in IPv6 Addressing", draft-ietf-6man-why64-06 (work in
progress), October 2014.
[I-D.arkko-homenet-prefix-assignment]
Arkko, J., Lindem, A., and B. Paterson, "Prefix Assignment
in a Home Network", draft-arkko-homenet-prefix-
assignment-04 (work in progress), May 2013.
[I-D.bhandari-dhc-class-based-prefix]
Systems, C., Halwasia, G., Gundavelli, S., Deng, H.,
Thiebaut, L., Korhonen, J., and I. Farrer, "DHCPv6 class
based prefix", draft-bhandari-dhc-class-based-prefix-05
(work in progress), July 2013.
[I-D.chelius-router-autoconf]
Chelius, G., Fleury, E., and L. Toutain, "Using OSPFv3 for
IPv6 router autoconfiguration", draft-chelius-router-
autoconf-00 (work in progress), June 2002.
[I-D.dimitri-zospf]
Dimitrelis, A. and A. Williams, "Autoconfiguration of
routers using a link state routing protocol", draft-
dimitri-zospf-00 (work in progress), October 2002.
Appendix A. Scarcity Avoidance Mechanism
Although an ISP should provide enough addresses, an implementation
must carefully manage the provided address space. First, when a new
assignment is made, the prefix should be selected amongst a set of
prefixes so that prefix waste is minimized. Then, a router may
decide to execute procedures intended to avoid prefix scarcity.
Different approaches are possible. This section intends to provide
guidelines for such procedures. They are optional and are compatible
with routers that only support basic requirements defined in this
document.
A.1. Prefix Wasts Avoidance
Given a Delegated Prefix, different routers may try to assign
prefixes of different lengths. Particularly, a non-homenet
downstream router may ask for a delegated prefix of significant size,
as specified in Section 8.2. Some other routers, like sensors, may
also require small prefixes. When randomly selected, a few /80s may
easily prevent the assignment of bigger prefixes. Small prefixes
should therefore be selected in neighboring areas.
For instance, given a delegated prefix 2001::/56 and an assigned
prefix 2001::/64, the best prefix choice in order to reduce prefix
space waste is 2001:0:0:1::/64. Other choices are then to be taken
in 2001:0:0:2::/63, 2001:0:0:4::/62, 2001:0:0:8::/61, etc...
Creating an efficient prefix selection algorithm may be challenging
as it needs to fullfill somehow contradictory requirements:
1. The prefix MUST be chosen amongst available prefixes, which
implies that other routers may interfere with the process.
2. The prefix MUST be chosen randomly in a subset of available
prefixes. When possible, the subset must be big enough to avoid
collisions.
3. The prefix SHOULD be selected amongst prefixes that reduces the
prefix space waste.
4. The prefix SHOULD be selected pseudo-randomly.
The following algorithm offers a satisfying tradeoff. Given a
Delegated Prefix and the desired prefix length:
1. Compute the minimal subset of available prefixes included in the
Delegated Prefix. In the example given previously, the minimal
subset was {2001:0:0:1::/64, 2001:0:0:2::/63, ..., 2001:0:0:80::/
57}.
2. Compute the set of prefixes of desired length so that:
* It contains exactly RANDOM_SUBSET_SIZE prefixes, or all the
available prefixes if there are less than RANDOM_SUBSET_SIZE
available prefixes.
* Prefixes are picked in the prefixes from the minimal subset of
available prefixes which lengths are the highest.
* When multiple subsets are possible, privelege lexicographicaly
lowest prefixes.
If RANDOM_SUBSET_SIZE equals 10, the subset would be
{2001:0:0:1::/64, 2 /64s in 2001:0:0:2::/63, 4 /64s in
2001:0:0:4::/62, the 3 first /64s in 2001:0:0:8::/61}.
3. First try PSEUDO_RANDOM_TENTATIVE pseudo-random prefixes,
computed from the DP, with the given length, based on interface
specific hardware values (For instance using values generated
like HASH(MAC Address : Counter). The hash function doesn't need
to be cryptographic). The first prefix amongst this set that
also is in the set computed at step 2 is chosen. If no prefix is
found, try next step.
4. Choose a prefix randomly among prefixes in the subset computed at This section describes an example of how custom configuration of the
step 2. prefix assignment algorithm may be implemented.
This algorithm, defined as a sequence of prefix sets computation, may The node configuration is specified as a finite set of rules. A rule
seem algorithmicaly complex, but it can be efficiently implemented. is defined as:
The key element in order to do so is the ability to iterate
efficiently over all the available prefixes.
RANDOM_SUBSET_SIZE should provide sufficiently low collision o A prefix to be used.
probability. A value of 256 should be enough in most cases.
PSEUDO_RANDOM_TENTATIVE is purely implementation dependent, but
shouldn't be too high as the probability of finding an available
prefix that way quickly decreases with the number of used prefixes.
A value of 10 should be sufficient.
A.2. Increasing Assigned Prefix Length o A Link on which the prefix may be assigned.
When a new assignment can't be created, and if not forbidden by the o An Assigned Prefix Priority (smallest possible Assigned Prefix
router's configuration, the router MAY increase the size of the Priority if the rule may not override other Assigned Prefixes).
desired prefix. For instance, if an available /64 can't be found,
the router may look for a /80. Nevertheless, this implies using
DHCPv6 instead of SLAAC, which SHOULD be avoided.
A.3. Foreseeing Prefixes Exaustion o A rule priority (0 if the rule may not override existing
Advertised Prefixes).
The previously proposed solution may be useful in some particular In order to ensure the convergence of the execution, the Assigned
cases, but won't work when no more prefixes are available. A router Prefix Priority MUST be an increasing function (not necessarily
MAY try to detect when default length prefixes are becoming rare. In strictly) of the configuration rule priority (i.e. the greater is the
such a situation, it MAY decide to allocate a longer prefix, part of configuration rule priority, the greater the Assigned Prefix Priority
an available shorter prefix. For instance, if A/64 is available, but must be).
there are not many other available /64, the router can try to
allocate A/80. If the allocation doesn't raise any collision, this
procedure will prevent A/64 from being used by other hosts, hence
creating a large set of smaller available prefixes to be used.
Such an allocation is considered dynamic. The Authoritative bit MUST Each Assigned Prefix is associated with a rule priority. Assigned
NOT be set and the priority MUST be among values authorized as Prefixes which are created as specified in Section 4.2 are given a
dynamically chosen in Section 6.8. rule priority of 0.
When different prefixes lengths are being used, the random prefix Whenever the configuration is changed or the prefix assignment
selection MUST NOT be uniform among all possibilities. Instead, it algorithm routine is run: For each Link/Delegated Prefix pair, look
SHOULD privilege prefixes contained in bigger prefixes that cannot be for the configuration rule with the highest configuration rule
allocated. For instance, if 2001::/56 is the DP, and 2001:0:0:0:1::/ priority such that:
80 is an assigned prefix, other /80 should be randomly chosen in
2001:0:0:0:1::/64 before being chosen in other /64s.
A.4. Cutting an Existing Assignment o The prefix specified in the configuration rule is included in the
considered Delegated Prefix.
When specifically required by an authority (configuration or DHCP), a o The Link specified in the configuration rule is the considered
router MAY decide to un-assign one of its own assignment, in order to Link.
cut it in smaller prefixes, or to send an overriding assignment in
order to force the network to stop using a particular prefix.
Because such a procedure may imply links reconfiguration, it SHOULD
be avoided whenever possible.
Such allocation are considered as required by an authority. The o All the Assigned Prefixes which would need to be destroyed in case
Authoritative bit MAY be set and the priority MUST be among values a new Assigned Prefix is created from that configuration rule (as
authorized as specified by an authority in Section 6.8. specified in Section 4.3) have an associated rule priority which
is strictly lower than the one of the considered configuration
rule.
As an example, if a router can't find a /64 for a link that, with a o The assignment would be valid when published with an Advertised
high priority, must be given a /64, it chooses a prefix assigned by Prefix Priority equal to the one specified in the configuration
some other router, to another link, with a lower priority, and rule.
creates a new Chosen Prefix with a higher priority. The other router
will be forced to remove its own assignment, hence making the new
assignment valid.
Appendix B. Acknowledgments If a rule is found, a new Assigned Prefix is created based on that
rule in conformance with Section 4.3. The new Assigned Prefix is
associated with the Advertised Prefix Priority and the rule priority
specified in the considered configuration rule.
This document is the continuation of the work being done in Note that the use of rule priorities ensures the convergence of the
[I-D.arkko-homenet-prefix-assignment]. The authors would like to execution.
thank all the people that participated in the previous document's
development as well as the present one. In particular, the authors
would like to thank 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 and Steven Barth
for interesting discussions in this problem space. The authors would
also like to point out some past work in this space, such as those in
[I-D.chelius-router-autoconf] or [I-D.dimitri-zospf].
Authors' Addresses Authors' Addresses
Pierre Pfister Pierre Pfister
Cisco Systems Cisco Systems
Paris Paris
France France
Email: pierre.pfister@darou.fr Email: pierre.pfister@darou.fr
Benjamin Paterson Benjamin Paterson
Cisco Systems Cisco Systems
Paris Paris
France France
Email: benjamin@paterson.fr Email: benjamin@paterson.fr
Jari Arkko Jari Arkko
Ericsson Ericsson
Jorvas 02420 Jorvas 02420
 End of changes. 188 change blocks. 
1244 lines changed or deleted 569 lines changed or added

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/