Network Working Group P. Pfister
Internet-Draft B. Paterson
Intended status: Standards Track Cisco Systems
Expires: August 10, 2014 J. Arkko
Ericsson
February 6, 2014
Prefix and Address Assignment in a Home Network
draft-pfister-homenet-prefix-assignment-00
Abstract
This memo describes a home network prefix and address assignment
algorithm running on top of any 'flooding protocol' that fulfills the
specified requirements. It is expected that home border routers are
allocated one or multiple IPv6 prefixes through DHCPv6 Prefix
Delegation (PD) or that prefixes are made available through other
means. An IPv4 address can also be assigned and private addresses be
used with NAT to provide IPv4 connectivity. In both cases, provided
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
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on August 10, 2014.
Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the
document authors. All rights reserved.
Pfister, et al. Expires August 10, 2014 [Page 1]
Internet-Draft Homenet Prefixes February 2014
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Requirements language . . . . . . . . . . . . . . . . . . . . 4
3. Prefix and Address Assignment Algorithms' Outline . . . . . . 4
4. Router Behavior . . . . . . . . . . . . . . . . . . . . . . . 5
4.1. Data structures . . . . . . . . . . . . . . . . . . . . . 5
4.2. Routers' Interfaces . . . . . . . . . . . . . . . . . . . 7
4.3. Obtaining a Delegated Prefix . . . . . . . . . . . . . . 7
4.4. Designated Router . . . . . . . . . . . . . . . . . . . . 8
4.4.1. Sending Router Advertisement . . . . . . . . . . . . 8
4.4.2. Being the DHCP Server . . . . . . . . . . . . . . . . 8
4.5. Applying an Assignment on an Interface . . . . . . . . . 9
4.6. DNS Support . . . . . . . . . . . . . . . . . . . . . . . 10
5. Flooding Protocol Requirements . . . . . . . . . . . . . . . 10
5.1. Router ID . . . . . . . . . . . . . . . . . . . . . . . . 10
5.2. Propagation Delay . . . . . . . . . . . . . . . . . . . . 10
5.3. Flooding Assigned Prefixes . . . . . . . . . . . . . . . 11
5.4. Flooding Delegated Prefixes . . . . . . . . . . . . . . . 11
5.5. Flooding Routers' Addresse Assignments . . . . . . . . . 12
6. Prefix Assignment Algorithm . . . . . . . . . . . . . . . . . 12
6.1. When to execute the Prefix Assignment Algorithm . . . . . 12
6.2. Assignment Precedence . . . . . . . . . . . . . . . . . . 13
6.3. Testing Assignment's validity . . . . . . . . . . . . . . 13
6.4. Testing Assignment's availability . . . . . . . . . . . . 13
6.5. Accepting an Assigned Prefix . . . . . . . . . . . . . . 13
6.6. Making a New Assignment . . . . . . . . . . . . . . . . . 14
6.7. Using Authoritative Prefix Assignments . . . . . . . . . 15
6.8. Choosing the Assignment's Priority . . . . . . . . . . . 15
6.9. Prefix Assignment Algorithm steps . . . . . . . . . . . . 16
7. Address Assignment Algorithm . . . . . . . . . . . . . . . . 17
7.1. Router's address pools . . . . . . . . . . . . . . . . . 18
7.2. Address Assignment Algorithm . . . . . . . . . . . . . . 18
8. Hysteresis Principle . . . . . . . . . . . . . . . . . . . . 19
9. ULA and IPv4 Prefixes Generation . . . . . . . . . . . . . . 19
9.1. ULA Prefix Generation . . . . . . . . . . . . . . . . . . 19
9.2. IPv4 Private Prefix Generation . . . . . . . . . . . . . 20
10. Manageability Considerations . . . . . . . . . . . . . . . . 20
Pfister, et al. Expires August 10, 2014 [Page 2]
Internet-Draft Homenet Prefixes February 2014
11. Documents Constants . . . . . . . . . . . . . . . . . . . . . 20
12. Security Considerations . . . . . . . . . . . . . . . . . . . 21
13. References . . . . . . . . . . . . . . . . . . . . . . . . . 21
13.1. Normative References . . . . . . . . . . . . . . . . . . 21
13.2. Informative References . . . . . . . . . . . . . . . . . 22
Appendix A. Scarcity Avoidance Mechanism . . . . . . . . . . . . 23
A.1. Increasing Assigned Prefix Length . . . . . . . . . . . . 23
A.2. Foreseeing Prefixes Exaustion . . . . . . . . . . . . . . 23
A.3. Cutting an Existing Assignment . . . . . . . . . . . . . 24
Appendix B. Acknowledgments . . . . . . . . . . . . . . . . . . 24
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 24
1. Introduction
This memo describes a fully distributed prefix and address assignment
algorithm for home networks, running on top of any 'flooding
protocol' that fulfills the specified requirements. It is expected
that home border routers are allocated one or multiple IPv6 prefixes
through DHCPv6 Prefix Delegation (PD) [RFC3633] or that prefixes are
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 lost.
Obtained IPv6 or IPv4 prefixes need to be efficiently divided among
the multiple links. For the purposes of this document, we refer to
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 DHCP or SLAAC.
Although this document recommends the use of 64 bits long prefixes,
the algorithm do not require routers to assign prefixes of particular
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
usual keywords, Section 3 outlines the algorithms functioning and
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
Pfister, et al. Expires August 10, 2014 [Page 3]
Internet-Draft Homenet Prefixes February 2014
and IPv4 prefixes, Section 10 explains what administrative interfaces
are useful for advanced users that wish to manually interact with the
mechanisms, Section 12 discusses the security aspects and finally,
Appendix A provides implementation guidelines for the optional
scarcity avoidance mechanism.
The Prefix Assignment Algorithm functioning was first detailed in
[I-D.arkko-homenet-prefix-assignment]. This document is a
continuation and generalization of that draft to any underlying
flooding protocol. It also adds a some features like arbitrary
lengths prefixes support, IPv4 support, scarcity avoidance mechanism
support or manual configuration support.
2. Requirements language
In this document, the key words "MAY", "MUST, "MUST NOT", "OPTIONAL",
"RECOMMENDED", "SHOULD", and "SHOULD NOT", are to be interpreted as
described in [RFC2119].
3. Prefix and Address Assignment Algorithms' Outline
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 start to 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 selects Chosen
Prefixes (CPs).
4. Once a link is given an assignment, routers may get addresses in
specified address pools and hosts may be configured by the per-
link elected DHCP server.
This algorithm, which intends to fulfill requirements specified in
[I-D.ietf-homenet-arch], have the following features:
o Each delegated prefix is efficiently subdivided so that each link
is given a prefix for each available delegated prefix. If the
Pfister, et al. Expires August 10, 2014 [Page 4]
Internet-Draft Homenet Prefixes February 2014
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 and
leave as well as Delegated Prefixes be added or deleted at any
time.
o IPv4 connectivity is provided whenever a home router gets an IPv4
address. To do so, a private IPv4 delegated prefix is generated
and prefixes are assigned just like for 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, or any upcoming
options may be attached to each prefixes 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
In a home network, all routers that want to participate in the prefix
assignment algorithm MUST fulfill the requirements defined in this
document. They MUST also use the same flooding protocol and routing
protocol. The presence of an internal router that do not implement
the flooding protocol and prefix assignment algorithm will not
prevent the network from working as long as:
o It doesn't act as a DHCP server on a link which is considered as
internal by any other router.
o It doesn't use any prefix that may be used by the prefix
assignment algorithm.
4.1. Data structures
The 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.
Pfister, et al. Expires August 10, 2014 [Page 5]
Internet-Draft Homenet Prefixes February 2014
The router MUST maintain a list of all the Assigned Prefixes
advertised by other routers. They are learnt through the mechanisms
described in Section 5.3 and MUST contain the following information:
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 (DHCP PD, manual configuration,
etc...).
Assignment's Priority: A value between PRIORITY_MIN and
PRIORITY_MAX, quantifying 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 called Chosen Prefixes (CPs)
and MUST contain the following information:
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 (DHCP PD, manual configuration,
etc...).
Assignment's Priority: A value between PRIORITY_MIN and
PRIORITY_MAX, quantifying the assignment's priority.
Advertised: Whether that assignment is being advertised by the
flooding protocol Section 5.3.
Applied: Whether that assignment is applied on link's configuration
Section 4.5.
Chosen Prefixes that are marked as 'Advertised' are sent to other
routers through the flooding protocol, and are therefore considered
as Assigned Prefixes by other routers. The Prefix Assignment
Algorithm goal is to make sure that all routers, on each link, select
the same set of Chosen Prefixes.
Pfister, et al. Expires August 10, 2014 [Page 6]
Internet-Draft Homenet Prefixes February 2014
The router MUST maintain a database of all its own address
assignments, and address assignments made by other routers on
connected links. The latter are learned through the mechanisms
described in Section 5.5.
4.2. Routers' Interfaces
Each router's interface MUST either be considered as internal or
external. Prefixes or addresses are only assigned to internal
interfaces. The way an interface is selected as internal or external
is out of the scope of this document.
If an internal interface's state is changed to external, all prefixes
and addresses assigned on the considered interface MUST be deleted,
and the prefix assignment algorithm MUST be run.
If an external interface's state is changed to internal, the prefix
assignment algorithm MUST be run.
4.3. Obtaining a Delegated Prefix
A Delegated Prefix can be obtained or generated through different
means:
o They can be dynamically delegated, for instance using DHCPv6 PD.
o They can be created statically, specified in router's
configuration.
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. When
the delegated prefix is IPv6, the options MUST be encoded as DHCPv6
options. When the delegated prefix is IPv4, the options MUST be
encoded as DHCPv4 options.
As DHCP options are numerous and new one 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 entirety of the provided options.
Pfister, et al. Expires August 10, 2014 [Page 7]
Internet-Draft Homenet Prefixes February 2014
o A router MUST NOT make or accept any assignment associated to a
delegated prefixe if it doesn't understand the entirety of the
DHCP options advertised along-with the delegated prefix.
4.4. 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 as a designated router on a given link
if one of the two following conditions is true:
o The router's Assigned Prefixes list is empty. i.e. no other router
is advertising assignments 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 is motivated by the few cases where
a router may volunteerly override an existing assignment by
advertising an assignment of higher priority. In such a case,
the designated router needs to remain the same.
4.4.1. Sending Router Advertisement
On a given link, the designated router MUST send router
advertisements including Prefix Information Options for all the
Chosen Prefixes associated to that link. SLAAC MAY be enabled
depending on the router's configuration and assignments prefix
length. The valid and preferred lifetimes MUST be set to values
lower or equal to the associated Delegated Prefix's valid and
preferred lifetimes.
4.4.2. Being the DHCP Server
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 on the given link and serve
addresses for all assignments on the given link. A router MUST stop
Pfister, et al. Expires August 10, 2014 [Page 8]
Internet-Draft Homenet Prefixes February 2014
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.5. 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). Once the timeout is
elapsed and no collision is detected, the prefix is applied by
executing the following steps:
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.4.1.
o If the router is the designated router on the considered link, it
starts behaving as a DHCP server, as defined in Section 4.4.2, for
the considered assigned prefix.
When a prefix assignment is removed, the previous steps MUST be
undone in the reverse order. 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 lifetime set to 0 [RFC4861] for the considered prefix.
Hosts that support DHCP reconfigure extension and that have been
given leases MUST be reconfigured as well [RFC3203].
Pfister, et al. Expires August 10, 2014 [Page 9]
Internet-Draft Homenet Prefixes February 2014
4.6. DNS Support
DHCP options attached to each delegated prefixes and propagated
through the flooding protocol SHOULD contain the DHCP DNS option
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 DHCPv6 option ([RFC3646]) along-with
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 OSPF
or ISIS, could be extended in order to fulfill the requirements, as
well as new dedicated and optimized protocols could be proposed.
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. IDs collisions within the network
MUST be rare and, when a collision occurs, the conflict 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
Pfister, et al. Expires August 10, 2014 [Page 10]
Internet-Draft Homenet Prefixes February 2014
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: DHCPv6 encoded 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.
Pfister, et al. Expires August 10, 2014 [Page 11]
Internet-Draft Homenet Prefixes February 2014
5.5. Flooding Routers' Addresse Assignments
Routers addresses are dynamically allocated, picked in defined pools,
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 as internal by at least one connected router. The
algorithm itself makes no difference whether the delegated prefix is
global IPv6, ULA or IPv4. IPv4 prefixes are written in 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. If
a delegated prefix contains another delegated prefix, it is ignored.
For the purpose of this discussion, the Aggregated Prefix will be
referred to as the current Aggregated Prefix, and the interface will
be referred to as the current Interface.
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.
Pfister, et al. Expires August 10, 2014 [Page 12]
Internet-Draft Homenet Prefixes February 2014
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 that do
not include any other 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 is not included and does not
include any other assignment made by any 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, 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.
o The same priority.
o The advertised bit value set as specified by the algorithm.
Pfister, et al. Expires August 10, 2014 [Page 13]
Internet-Draft Homenet Prefixes February 2014
o The applied bit is unset. It is set when the timer elapsed if the
entry still exists.
6.6. Making a New Assignment
When the algorithm decides to make a new assignment, it first needs
to specify the desired size of the assigned prefix. Although that
choice is completely implementation specific, prefixes of size 64 are
RECOMMENDED. The following table MAY be used as default values,
where X is the length of the delegated prefix.
If X < 64: Prefix length = 64
If X >= 64 and X < 104: Prefix length = X + 16 (up to 2^16 links)
If X >= 104 and X < 112: Prefix length = 120 (2^8 addresses per link
and more than 2^8 links)
If X >= 112 and X <= 128: Prefix length = 120 + (X - 112)/2 (Link Vs
Addresses tradeoff)
When the algorithm decides to make a new assignment, it looks in the
stable storage for an available assignment that was previously
applied on the current interface and that is included in the current
delegated prefix. If no available assignment can be found this way,
the new prefix MUST be randomly selected among prefixes in the
current Delegated Prefix that are still available. Implementing a
uniform selection among all available prefixes may be challenging,
but an implementation SHOULD at least be able to make an exhaustive
search when the address space is small, and make multiple tentatives
when the address space is too big.
If no available prefix is found, the assignment fails. If
implemented, the router MAY decide to execute the Prefix Scarcity
Avoidance mechanisms, as proposed in Appendix A.
When a new assignment is made, a new Chosen Prefix entry is created.
o The prefix value is set to the chosen prefix.
o The link ID is the ID of the link on which the assignment is made.
o The authoritative bit is set to false.
o The priority is set to a value between PRIORITY_AUTO_MIN and
PRIORITY_AUTO_MAX (Section 6.8).
o The advertised bit is set.
Pfister, et al. Expires August 10, 2014 [Page 14]
Internet-Draft Homenet Prefixes February 2014
o The applied bit is unset. It is set when the timer elapsed if the
entry still exists.
A new assignment is always marked as advertised when created and
therefore immediately provided to the flooding protocol.
6.7. Using Authoritative Prefix Assignments
When some authority (Delegating router, system admin, etc...) wants
to manually enforce some behavior, it may ask some router to make an
Authoritative Prefix Assignment. Such assignments have their
Authoritative bit set, CAN NOT be overridden, and will appear in
other router's database as Assigned Prefixes with the Authoritative
bit set.
There are two kinds of Authoritative Prefix Assignments.
o When an authority wants to assign some particular prefix to some
interface, an Authoritative Prefix Assignment CAN be created and
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
Authoritative Assignment CAN 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 DHCP PD with a non-null
excluded prefix, as specified in [RFC6603], an Authoritative Prefix
Assignment MUST be created with the excluded prefix.
Note: If the router doesn't know the excluded prefix DHCPv6
option, the delegated prefix is ignored, as specified in
Section 4.3.
6.8. Choosing the Assignment's Priority
When either a new Prefix Assignment is made, or an Authoritative
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
an interesting feature when not enough prefixes are available.
o PRIORITY_DEFAULT SHOULD be used as default.
Pfister, et al. Expires August 10, 2014 [Page 15]
Internet-Draft Homenet Prefixes February 2014
o Other values between PRIORITY_AUTO_MIN and PRIORITY_AUTO_MAX MAY
be dynamically chosen by the implementation.
o Other values between PRIORITY_AUTHORITY_MIN and
PRIORITY_AUTHORITY_MAX MUST NOT be used if not stated by an
authority (by static or dynamic configuration).
o Other values are reserved.
6.9. Prefix Assignment Algorithm steps
In this section are detailed the steps of the Prefix Assignment
Algorithm.
At the beginning of the algorithm, all assignments that do not have
their Authoritative bit set are marked as 'invalid', and the router
computes for each link whether it is the designated router.
The following steps are then executed for every combination of
delegated prefix and interface.
o If the current interface is external, ignore that interface.
o If the delegated prefix strictly contains another delegated
prefix, ignore that delegated prefix.
o If the delegated prefix is equal to an already considered
delegated prefix, ignore that delegated prefix.
o Look for a valid Assigned Prefix, advertised by another router on
the current interface and included in the current Delegated
Prefix.
o Look for a Chosen Prefix associated to the current interface and
included in the current Delegated Prefix.
o There are four possibilities at this stage.
1. If no AP is found, and no CP is found, a new assignment MUST
be made if and only if the router considers itself as the
designated router. See Section 6.6.
2. If an AP is found, and no CP is found, the AP MUST be
accepted. The new CP's advertised bit MUST be set if and only
if the router considers itself as the designated router.
3. If no AP is found, and a CP is found, the router MUST check if
the CP's assignment is valid. If it is, the local assignment
Pfister, et al. Expires August 10, 2014 [Page 16]
Internet-Draft Homenet Prefixes February 2014
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
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 of the algorithm, all the assignments that are marked as
invalid are deleted.
7. Address Assignment Algorithm
IPv6 routers always get at least one link-local address per link.
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
synchronization, etc...).
o The router needs connectivity within the home network (For
management, DNS communications, etc...).
o IPv4 addresses are needed (DHCPv4, v4 link-local connectivity,
etc...).
When possible, SLAAC MUST be used. In other cases a different
mechanism is necessary for routers to get addresses. This document
proposes an Address Assignment Algorithm that extends the Prefix
Assignment Algorithm and works as follows. Each prefix assignment is
associated a fixed address pool, reserved for router's addresses
assignment. The address pool is a prefix whose value is
deterministically function of the assigned prefix. A router CAN, 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.
Pfister, et al. Expires August 10, 2014 [Page 17]
Internet-Draft Homenet Prefixes February 2014
7.1. Router's address pools
Given an assigned prefix A/X (where all A's latest '128 - X'th bits
are set to 0), the routers reserved address pool is defined as
following:
If X < 64: SLAAC MUST be used
If X > 64 and X <= 110: The pool is A/112 (2^16 addresses)
If X > 110 and X <= 126: The pool is A/(X + 2) (One quarter of the
available addresses)
If X > 126: Only the designated router CAN use A/128. Other routers
MUST NOT get an address.
7.2. Address Assignment Algorithm
In this section, we say an address assignment is made by some router
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 stable storage and
reuse the same addresses whenever possible. At least the five
previously applied addresses should be stored.
For a given prefix assignment, an address is said to be available if
it is within the router's address pool associated to the prefix
assignment, and it is not being advertised by any other router. If
the flooding protocol provides interface identifier along-with
address assignments, looking for collisions on considered link is
enough.
A new address assignment MUST be chosen randomly among available
addresses. An address assignment MUST NOT be applied when one of the
following condition is true.
o The associated Chosen Prefix is not applied.
o The timer specified in Section 8 did not elapsed yet.
An address assignment must be deleted whenever one of the following
condition becomes true.
o The associated Chosen Prefix is deleted or moved to another link.
Pfister, et al. Expires August 10, 2014 [Page 18]
Internet-Draft Homenet Prefixes February 2014
o Some other router, with an higher router ID, is advertising the
same address on the same link.
8. Hysteresis Principle
When the flooding protocol is started, the router MUST wait
FLOODING_DELAY before executing the prefix assignment algorithm for
the first time.
Prefix and address assignment algorithms are distributed. Collisions
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 waited
2*FLOODING_DELAY. If, during the whole waiting time, the entry is
still valid, it MUST be applied to the link it is assigned.
o A router MUST NOT apply an Assigned Address before it waited
2*FLOODING_DELAY_LL. If, during the whole waiting time, the
assignment is still valid, it MUST be applied to the interface it
is assigned.
9. ULA and IPv4 Prefixes Generation
Although DHCPv6 PD and static configuration are regular means of
obtaining IPv6 prefixes, routers MAY, in some cases, autonomously
decide to generate a delegated prefix. In this section are specified
when and how IPv6 ULA prefixes and IPv4 private prefixes may be
autonomously generated.
9.1. ULA Prefix Generation
A router MAY generate a ULA prefix when the two following conditions
are met.
o It is the network leader.
o No other ULA delegated prefix is advertised by any other router.
A router MUST stop advertising a spontaneously generated ULA prefix
whenever another router is advertising a ULA delegated prefix.
The more recently used ULA prefix SHOULD be stored in stable storage
by all routers and reused whenever choosing a new ULA delegated
prefix. If no ULA prefix can be found in stable storage, it MUST be
randomly generated, or generated from hardware specific values.
Pfister, et al. Expires August 10, 2014 [Page 19]
Internet-Draft Homenet Prefixes February 2014
9.2. IPv4 Private Prefix Generation
A router MAY generate an IPv4 prefix when the two following
conditions are met.
o It has an IPv4 address with global connectivity.
o No other IPv4 delegated prefix is advertised by any other router.
A router MUST stop advertising an IPv4 prefix whenever another router
with an higher router ID is advertising an IPv4 Delegated Prefix.
The IPv4 private prefix must be included in one of the private
prefixes defined in [RFC1918]. The prefix 10/8 SHOULD be used by
default but it SHOULD be configurable. In the case the address
provided by the ISP is already a private address, a different private
prefix SHOULD be used. For instance, if the ISP is giving the
address 10.1.2.3, 10/8 or any sub-prefix included in 10/8 SHOULD NOT
be used. 172.16/12 MAY be selected instead.
10. Manageability Considerations
The algorithm leaves much place to implementation specific features.
For instance, ULA prefix as well IPv4 prefix generation may be
disabled whenever a global IPv6 is made available. This section
details a few other possible configuration options.
The implementation MAY allow each internal interface to be configured
with a custom priority value. The specified priority SHOULD then be
used when creating new assignments on the given interface. If not
specified, the default priority SHOULD be used.
The implementation SHOULD allow manual assignments on given links.
When specified, and whenever such an assignment is valid, it MUST be
advertised as Authoritative Assignments on the given interface.
11. Documents Constants
PRIORITY_MIN 0
PRIORITY_AUTHORITY_MIN 4
PRIORITY_AUTO_MIN 6
PRIORITY_DEFAULT 8
PRIORITY_AUTO_MAX 10
PRIORITY_AUTHORITY_MAX 12
PRIORITY_MAX 15
Pfister, et al. Expires August 10, 2014 [Page 20]
Internet-Draft Homenet Prefixes February 2014
12. Security Considerations
Prefix assignment algorithm security entirely relies on flooding
protocol security features. The flooding protocol SHOULD therefore
check for advertised information's authenticity. Security modes may
be classified in three categories.
1. The flooding protocol is not protected.
2. The flooding protocol's protection is binary: An allowed router
may send any type of packets in the name of other routers.
3. All advertised messages are individually signed by the sender.
Whenever a malicious router attacks an unprotected network, or
whenever a malicious router is able to authenticate itself to a
network as stated in the second case, it may for example:
o Prevent other routers to get a stable router ID.
o Prevent other routers from making assignments by claiming the
whole available address space.
o Redirect traffic to some router on the network.
If a malicious router is able to authenticate itself in a network
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
identified.
In any case, in order to protect the network, the routing protocol as
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 or
SeND) security solutions.
13. References
13.1. Normative References
[RFC1918] Rekhter, Y., Moskowitz, R., Karrenberg, D., Groot, G., and
E. Lear, "Address Allocation for Private Internets", BCP
5, RFC 1918, February 1996.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
Pfister, et al. Expires August 10, 2014 [Page 21]
Internet-Draft Homenet Prefixes February 2014
[RFC3203] T'Joens, Y., Hublet, C., and P. De Schrijver, "DHCP
reconfigure extension", RFC 3203, December 2001.
[RFC3646] Droms, R., "DNS Configuration options for Dynamic Host
Configuration Protocol for IPv6 (DHCPv6)", RFC 3646,
December 2003.
[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.
[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
[RFC3633] Troan, O. and R. Droms, "IPv6 Prefix Options for Dynamic
Host Configuration Protocol (DHCP) version 6", RFC 3633,
December 2003.
[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.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.
[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.
Pfister, et al. Expires August 10, 2014 [Page 22]
Internet-Draft Homenet Prefixes February 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.
Appendix A. Scarcity Avoidance Mechanism
When not enough addresses are available, 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 implementation. They are optional and are
compatible with routers that only support basic requirements defined
in this document.
A.1. Increasing Assigned Prefix Length
When a new assignment can't be created, and if not forbidden by the
router's configuration, the router MAY increase the size of the
desired prefix. For instance, if an available /64 can't be found,
the router may look for a /80. Nevertheless, this imply using DHCPv6
instead of SLAAC, which SHOULD be avoided.
A.2. Foreseeing Prefixes Exaustion
The previously proposed solution may be useful in some particular
cases, but won't work when no more prefixes are available. A router
MAY try to detect when default length prefixes are becoming rare. In
such a situation, it MAY decide to allocate a longer prefix, part of
an available shorter prefix. For instance, if A/64 is available, but
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 as dynamic. The Authoritative bit
MUST NOT be set and the priority MUST be among values authorized as
dynamically chosen in Section 6.8.
When different prefixes lengths are being used, the random prefix
selection MUST NOT be uniform among all possibilities. Instead, it
SHOULD privilege prefixes contained in bigger prefixes that cannot be
allocated. For instance, if 2001::/56 is the DP, and 2001:0:0:0:1::/
80 is an assigned prefix, other /80 should be randomly chosen in
2001:0:0:0:1::/64 before being chosen in other /64s.
Pfister, et al. Expires August 10, 2014 [Page 23]
Internet-Draft Homenet Prefixes February 2014
A.3. Cutting an Existing Assignment
When specifically required by an authority (configuration or DHCP), a
router MAY decide to un-assign one of its own assignment, in order to
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 as much as possible.
Such allocation are considered as required by an authority. The
Authoritative bit MAY be set and the priority MUST be among values
authorized as specified by an authority in Section 6.8.
As an example, if a router can't find a /64 for a link that, with a
high priority, must be given a /64, it chooses a prefix assigned by
some other router, to another link, with a lower priority, and
creates a new Chosen Prefix with an higher priority. The other
router will be forced to remove its own assignment, hence making the
new assignment valid.
Appendix B. Acknowledgments
This document is the continuation of the work being done in
[I-D.arkko-homenet-prefix-assignment]. The authors would like to
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
Pierre Pfister
Cisco Systems
Paris
France
Email: pierre@darou.fr
Pfister, et al. Expires August 10, 2014 [Page 24]
Internet-Draft Homenet Prefixes February 2014
Benjamin Paterson
Cisco Systems
Paris
France
Email: benjamin@paterson.fr
Jari Arkko
Ericsson
Jorvas 02420
Finland
Email: jari.arkko@piuha.net
Pfister, et al. Expires August 10, 2014 [Page 25]