Network Working Group P. Pfister Internet-Draft B. Paterson Intended status: Standards Track Cisco Systems Expires: April 27, 2015 J. Arkko Ericsson October 24, 2014 Prefix and Address Assignment in a Home Network draft-ietf-homenet-prefix-assignment-01 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 April 27, 2015. Copyright Notice Copyright (c) 2014 IETF Trust and the persons identified as the document authors. All rights reserved. Pfister, et al. Expires April 27, 2015 [Page 1] Internet-Draft Homenet Prefixes October 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 . . . . . . . . . . . . . . . . . . . . . 6 4.2. Routers' Interfaces . . . . . . . . . . . . . . . . . . . 7 4.3. Obtaining a Delegated Prefix . . . . . . . . . . . . . . 7 4.4. Network Leader . . . . . . . . . . . . . . . . . . . . . 8 4.5. Designated Router . . . . . . . . . . . . . . . . . . . . 8 4.5.1. Sending Router Advertisement . . . . . . . . . . . . 9 4.5.2. DHCP Server Operations . . . . . . . . . . . . . . . 9 4.6. Applying an Assignment on an Interface . . . . . . . . . 10 4.7. DNS Support . . . . . . . . . . . . . . . . . . . . . . . 10 5. Flooding Protocol Requirements . . . . . . . . . . . . . . . 11 5.1. Router ID . . . . . . . . . . . . . . . . . . . . . . . . 11 5.2. Propagation Delay . . . . . . . . . . . . . . . . . . . . 11 5.3. Flooding Assigned Prefixes . . . . . . . . . . . . . . . 12 5.4. Flooding Delegated Prefixes . . . . . . . . . . . . . . . 12 5.5. Flooding Routers' Address Assignments . . . . . . . . . . 12 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 Pfister, et al. Expires April 27, 2015 [Page 2] Internet-Draft Homenet Prefixes October 2014 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 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 not available. 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 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, 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 Pfister, et al. Expires April 27, 2015 [Page 3] Internet-Draft Homenet Prefixes October 2014 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 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 [I-D.arkko-homenet-prefix-assignment]. This document is a continuation and generalization of that draft to any underlying flooding protocol. It also adds support for arbitrary prefix length, IPv4, scarcity avoidance mechanism or manual configuration. 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 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. Pfister, et al. Expires April 27, 2015 [Page 4] Internet-Draft Homenet Prefixes October 2014 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, Pfister, et al. Expires April 27, 2015 [Page 5] Internet-Draft Homenet Prefixes October 2014 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. Pfister, et al. Expires April 27, 2015 [Page 6] Internet-Draft Homenet Prefixes October 2014 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. Pfister, et al. Expires April 27, 2015 [Page 7] Internet-Draft Homenet Prefixes October 2014 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: Pfister, et al. Expires April 27, 2015 [Page 8] Internet-Draft Homenet Prefixes October 2014 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. Pfister, et al. Expires April 27, 2015 [Page 9] Internet-Draft Homenet Prefixes October 2014 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). Pfister, et al. Expires April 27, 2015 [Page 10] Internet-Draft Homenet Prefixes October 2014 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 Pfister, et al. Expires April 27, 2015 [Page 11] Internet-Draft Homenet Prefixes October 2014 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 Pfister, et al. Expires April 27, 2015 [Page 12] Internet-Draft Homenet Prefixes October 2014 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. Pfister, et al. Expires April 27, 2015 [Page 13] Internet-Draft Homenet Prefixes October 2014 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. Pfister, et al. Expires April 27, 2015 [Page 14] Internet-Draft Homenet Prefixes October 2014 o The same priority. o The advertised bit value set as specified by the algorithm. o The applied bit is unset. It is set when the timer elapsed if the entry still exists. 6.6. Making a New Assignment In situations where a router can make an assignment (see Section 6.9), the following rules are used in the following order: 1. If the configuration specifies a custom behavior (e.g. always ignore/accept a particular delegated prefix), use the configuration entry. 2. If the Delegated Prefix Preferred Lifetime is strictly greater than zero, an assignment MUST be made. 3. If no other prefix has a non-zero Preferred Lifetime, and no assignment is made on the link, an assignment SHOULD be made. 4. Otherwise, a new assignment SHOULD NOT be made. When the algorithm decides to make a new assignment, it first needs to specify the desired size of the assigned prefix. Although this algorithm intends to remain generic, the use of 64 bits long prefixes is RECOMMENDED (See [I-D.ietf-6man-why64]). 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 SHOULD first checks its stable storage for an available assignment that was previously applied on the current interface and is part of the current delegated prefix. If no available assignment can be found that way, the new prefix MUST be randomly selected among a subset of available prefixes (if possible, large enough to avoid collisions). Pfister, et al. Expires April 27, 2015 [Page 15] Internet-Draft Homenet Prefixes October 2014 Hardware specific identifiers may be used to seed a pseudo-random generator. If no available prefix is found, the assignment fails. The algorithm leaves much room for implementation specific policies. 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 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. 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, SHALL 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 MAY 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. Pfister, et al. Expires April 27, 2015 [Page 16] Internet-Draft Homenet Prefixes October 2014 o When an authority wants to prevent some prefix from being used, an 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- 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 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 useful when not enough prefixes are available. o PRIORITY_DEFAULT SHOULD be used as default. 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 specified by an authority (by static or dynamic configuration). o Other values are reserved. 6.9. Prefix Assignment Algorithm steps 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 connected link whether it is the designated router, as specified in Section 4.5. The following steps are then executed for every combination of delegated prefixes and interfaces. o If the current interface is external, ignore that interface. o If the Delegated Prefix is strictly included in another Delegated Prefix, ignore that delegated prefix. Pfister, et al. Expires April 27, 2015 [Page 17] Internet-Draft Homenet Prefixes October 2014 o If the Delegated Prefix is equal to another Delegated Prefix, advertised by some router with an higher router ID than the 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 can be made if and only if the router considers itself as the 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 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 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 all the assignments that are marked as invalid are deleted. 6.10. Downstream DHCPv6 Prefix Delegation support If some host or non-Homenet router asks for Delegated Prefixes, a router MAY assign a set of prefixes and give them to the client. Such assignments MUST be advertised as either not assigned on any 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 Pfister, et al. Expires April 27, 2015 [Page 18] Internet-Draft Homenet Prefixes October 2014 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 their associated Delegated Prefix's lifetimes, and associated DHCPv6 data SHOULD be provided to the DHCPv6 PD client. By default, an assigned prefix SHOULD NOT be provided to a DHCPv6 PD client before the apply timeout has elapsed. But in order to allow faster response delay, a lease MAY first be provided with a lifetime of 2*FLOODING_DELAY seconds, even if the private assignments' apply timeout has not elapsed yet. 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 with a fixed address pool, reserved for router's addresses 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. Pfister, et al. Expires April 27, 2015 [Page 19] Internet-Draft Homenet Prefixes October 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 follows: 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 MAY use A/128. Other routers MUST NOT get an address. In the case of IPv4 prefixes, the network address (first address of the address pool) MUST not be used. 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 their stable 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 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 in the 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 has not elapsed yet. Pfister, et al. Expires April 27, 2015 [Page 20] Internet-Draft Homenet Prefixes October 2014 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. o Some other router with a higher router ID is advertising the same address on the same link. 8. Hysteresis Principle The IPv6 Stateless Address Autoconfiguration [RFC4862] states that host addresses can be kept up to 2 hours after a Router Advertisement wit zero lifetime is received. Therefore, routers must be carefull before assigning or deprecating a prefix. 8.1. Prefix and Address assignments 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 has waited 2*FLOODING_DELAY. If the entry is valid during the whole waiting time, it MUST be applied to the link it is assigned. o A router MUST NOT apply an Assigned Address before it has waited 2*FLOODING_DELAY_LL. If the assignment is valid during the whole waiting time, it MUST be applied to the interface it is assigned. 8.2. Delegated Prefixes Some links may be unreliable, causing repetitive connectivity loss. Such links shouldn't cause IP reconfiguration. 8.2.1. Unreliable uplink When a router detects uplink connectivity loss, Delegated Prefixes' lifetimes from prefixes obtained through the uplink MUST be modified in the following way. o The Preferred Lifetime is set to 0. Pfister, et al. Expires April 27, 2015 [Page 21] Internet-Draft Homenet Prefixes October 2014 o The Valid Lifetime is set to the minimum between the current Valid Lifetime and two hours. o The default route associated with the prefix is not advertised anymore. This behavior is similar to [RFC7084] specifications and provides stable host configuration in case of unreliable uplink. 8.2.2. Unreliable in-home link When a router stops advertising a Delegated Prefix, it MUST first deprecate that Delegated Prefix by advertising it for DP_DEPRECATE_FACTOR*FLOODING_DELAY seconds with zero valid and preferred lifetimes. When a router receives a deprecated Delegated Prefix advertisement from the Flooding Protocol, it MUST remove the Delegated Prefix from its Delegated Prefixes list. When a router stops receiving a Delegated Prefix from the Flooding 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 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 ULA prefixes can be randomly generated as specified in [RFC4193], enabling stable in-home IPv6 connectivity. In this section, we say a ULA delegated prefix is 'stable' if it has been the only advertised ULA delegated prefix for at least 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 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. Pfister, et al. Expires April 27, 2015 [Page 22] Internet-Draft Homenet Prefixes October 2014 9.1.1. Choosing the ULA prefix When a stable ULA prefix is advertised, all routers SHOULD remember that prefix alongwith its associated valid and preferred lifetime. 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 lifetime of the prefix was null, a prefix generated as specified in [RFC4193] SHOULD be used. In case the stable storage can't be used or the current date cannot be determined, the prefix MAY be pseudo- randomly generated based on hardware specific values. 9.1.2. Advertising a ULA prefix A router MAY start advertising a ULA prefix whenever the two following conditions are met: o It is the network leader. o There is no other advertised ULA prefix. If no IPv6 prefix is available at all, the network leader SHOULD start advertising a ULA delegated prefix. Additionaly, a router SHOULD start advertising its own ULA prefix whenever the three following conditions are met: o A stable ULA prefix is advertised by another router. o The router owns the advertised stable ULA prefix. o The preferred lifetime of the advertised ULA prefix is below 10 minutes. This allows a router to restart advertising a owned prefix whenever 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 whenever one of the two following condition is met: o A different ULA prefix is being advertised. o The same prefix is advertised by another router, and the router doesn't own that prefix. Pfister, et al. Expires April 27, 2015 [Page 23] Internet-Draft Homenet Prefixes October 2014 9.1.3. Extending prefix lifetime Routers MUST regularly extend the valid and preferred lifetimes of the ULA delegated prefix they advertise and own, so that they never drop to zero. When a router advertises a prefix it doesn't own, lifetimes are never 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 This section doesn't prevent multiple ULA prefixes from existing simultaneously. ULA prefixes may be provided by different means, as 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 generated ULA prefixes are withdrawned. 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. (For instance, 172.16/12 or 192.168/16 can be selected). 10. Manageability Considerations The algorithm leaves much room for implementation specific features. For instance, ULA prefix as well IPv4 prefix generation may be Pfister, et al. Expires April 27, 2015 [Page 24] Internet-Draft Homenet Prefixes October 2014 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 DP_DEPRECATE_FACTOR 3 DP_KEEP_ALIVE_TIME 60 seconds 12. Security Considerations Prefix assignment algorithm security entirely relies on flooding protocol security features. The flooding protocol SHOULD therefore check for the authenticity of advertised information. 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. Pfister, et al. Expires April 27, 2015 [Page 25] Internet-Draft Homenet Prefixes October 2014 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 be 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-Auth [RFC4302] or SeND [RFC3971]) 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. [RFC2131] Droms, R., "Dynamic Host Configuration Protocol", RFC 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., and M. Carney, "Dynamic Host Configuration Protocol for IPv6 (DHCPv6)", RFC 3315, July 2003. [RFC3633] Troan, O. and R. Droms, "IPv6 Prefix Options for Dynamic Host Configuration Protocol (DHCP) version 6", RFC 3633, December 2003. [RFC3646] Droms, R., "DNS Configuration options for Dynamic Host 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. Pfister, et al. Expires April 27, 2015 [Page 26] Internet-Draft Homenet Prefixes October 2014 [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. Pfister, et al. Expires April 27, 2015 [Page 27] Internet-Draft Homenet Prefixes October 2014 [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. Pfister, et al. Expires April 27, 2015 [Page 28] Internet-Draft Homenet Prefixes October 2014 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. Pfister, et al. Expires April 27, 2015 [Page 29] Internet-Draft Homenet Prefixes October 2014 * 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 step 2. This algorithm, defined as a sequence of prefix sets computation, may seem algorithmicaly complex, but it can be efficiently implemented. 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 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 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 implies using DHCPv6 instead of SLAAC, which SHOULD be avoided. A.3. 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 Pfister, et al. Expires April 27, 2015 [Page 30] Internet-Draft Homenet Prefixes October 2014 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 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. A.4. 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 whenever 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 a 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]. Pfister, et al. Expires April 27, 2015 [Page 31] Internet-Draft Homenet Prefixes October 2014 Authors' Addresses Pierre Pfister Cisco Systems Paris France Email: pierre.pfister@darou.fr 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 April 27, 2015 [Page 32]