Network Working Group                                         P. Pfister
Internet-Draft                                               B. Paterson
Intended status: Standards Track                           Cisco Systems
Expires: April 27, July 9, 2015                                           J. Arkko
                                                                Ericsson
                                                        October 24, 2014
                                                         January 5, 2015

                Distributed Prefix and Address Assignment in a Home Network
                draft-ietf-homenet-prefix-assignment-01 Algorithm
                draft-ietf-homenet-prefix-assignment-02

Abstract

   This memo describes document specifies a home network prefix and address assignment distributed algorithm running on top for automatic prefix
   assignment.  Given a set of any 'flooding protocol' that fulfills the
   specified requirements.  It is expected that home border routers are
   allocated delegated prefixes, it ensures at most
   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 prefix is assigned and private addresses be
   used with NAT from each delegated prefix to provide IPv4 connectivity.  In both cases, provided each link.
   Nodes may assign available prefixes need to be efficiently divided among the multiple links, and
   routers need to obtain addresses.  This document describes a
   distributed algorithm links they are directly
   connected to, or for IPv4 other private purposes.  The algorithm
   eventually converges and IPv6 ensures that all assigned prefixes division, assignment
   and router's address assignment, and specifies how hosts can be given
   addresses and configuration options using DHCP or SLAAC. do not
   overlap.

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, July 9, 2015.

Copyright Notice

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

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (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
   2.  Requirements language . . .  Terminology . . . . . . . . . . . . . . . . .   4
   3.  Prefix and Address Assignment Algorithms' Outline . . . . . .   4
   4.  Router Behavior . . . .   3
   3.  Applicability statement . . . . . . . . . . . . . . . . . . .   5
     4.1.  Data structures . .
   4.  Algorithm Specification . . . . . . . . . . . . . . . . . . .   6
     4.2.  Routers' Interfaces .
     4.1.  Algorithm Terminology . . . . . . . . . . . . . . . . . .   7
     4.3.  Obtaining a Delegated   6
     4.2.  Prefix  . . . Assignment Algorithm Routine . . . . . . . . . . .   7
     4.4.  Network Leader  . . . . . . . . .
     4.3.  Overriding and Destroying Existing Assignments  . . . . .  10
     4.4.  Other Events  . . . . . . .   8
     4.5.  Designated Router . . . . . . . . . . . . . . .  11
   5.  Prefix Selection Considerations . . . . .   8
       4.5.1.  Sending Router Advertisement . . . . . . . . . .  11
   6.  Implementation Capabilities and Node Behavior . .   9
       4.5.2.  DHCP Server Operations . . . . . .  13
   7.  Algorithm Parameters  . . . . . . . . .   9
     4.6.  Applying an Assignment on an Interface . . . . . . . . .  10
     4.7.  DNS Support . .  14
   8.  Security Considerations . . . . . . . . . . . . . . . . . . .  15
   9.  IANA Considerations . .  10
   5.  Flooding Protocol Requirements . . . . . . . . . . . . . . .  11
     5.1.  Router ID . . . .  16
   10. Acknowledgments . . . . . . . . . . . . . . . . . . . .  11
     5.2.  Propagation Delay . . .  16
   11. References  . . . . . . . . . . . . . . . . .  11
     5.3.  Flooding Assigned Prefixes . . . . . . . .  16
     11.1.  Normative References . . . . . . .  12
     5.4.  Flooding Delegated Prefixes . . . . . . . . . . .  16
     11.2.  Informative References . . . .  12
     5.5.  Flooding Routers' Address Assignments . . . . . . . . . .  12
   6.  Prefix Assignment Algorithm . . .  16
   Appendix A.  Static Configuration Example . . . . . . . . . . . .  16
   Authors' Addresses  . .  13
     6.1.  When to execute the Prefix Assignment Algorithm . . . . .  13
     6.2.  Assignment Precedence . . . . . . . . . . . . . . . . . .  14
     6.3.  Testing Assignment's validity . . . . . . . . . . . . . .  14
     6.4.  Testing Assignment's availability . . . . . . . . . . . .  14
     6.5.  Accepting an Assigned Prefix  . . . . . . . . . . . . . .  14
     6.6.  Making a New Assignment . . . . . . . . . . . . . . . . .  15
     6.7.  Using Authoritative Prefix Assignments  . . . . . . . . .  16
     6.8.  Choosing the Assignment's Priority  . . . . . . . . . . .  17
     6.9.  Prefix Assignment Algorithm steps . . . . . . . . . . . .  17
     6.10. Downstream DHCPv6 Prefix Delegation support . . . . . . .  18
   7.  Address Assignment Algorithm  . . . . . . . . . . . . . . . .  19
     7.1.  Router's address pools  . . . . . . . . . . . . . . . . .  20
     7.2.  Address Assignment Algorithm  . . . . . . . . . . . . . .  20
   8.  Hysteresis Principle  . . . . . . . . . . . . . . . . . . . .  21
     8.1.  Prefix and Address assignments  . . . . . . . . . . . . .  21
     8.2.  Delegated Prefixes  . . . . . . . . . . . . . . . . . . .  21
       8.2.1.  Unreliable uplink . . . . . . . . . . . . . . . . . .  21
       8.2.2.  Unreliable in-home link . . . . . . . . . . . . . . .  22
   9.  ULA and IPv4 Prefixes Generation  . . . . . . . . . . . . . .  22
     9.1.  ULA Prefix Generation . . . . . . . . . . . . . . . . . .  22
       9.1.1.  Choosing the ULA prefix . . . . . . . . . . . . . . .  23
       9.1.2.  Advertising a ULA prefix  . . . . . . . . . . . . . .  23
       9.1.3.  Extending prefix lifetime . . . . . . . . . . . . . .  24
       9.1.4.  Authoritative ULAs  . . . . . . . . . . . . . . . . .  24
     9.2.  IPv4 Private Prefix Generation  . . . . . . . . . . . . .  24
   10. Manageability Considerations  . . . . . . . . . . . . . . . .  24
   11. Documents Constants . . . . . . . . . . . . . . . . . . . . .  25
   12. Security Considerations . . . . . . . . . . . . . . . . . . .  25
   13. References  . . . . . . . . . . . . . . . . . . . . . . . . .  26
     13.1.  Normative References . . . . . . . . . . . . . . . . . .  26
     13.2.  Informative References . . . . . . . . . . . . . . . . .  27
   Appendix A.  Scarcity Avoidance Mechanism . . . . . . . . . . . .  28
     A.1.  Prefix Wasts Avoidance  . . . . . . . . . . . . . . . . .  29
     A.2.  Increasing Assigned Prefix Length . . . . . . . . . . . .  30
     A.3.  Foreseeing Prefixes Exaustion . . . . . . . . . . . . . .  30
     A.4.  Cutting an Existing Assignment  . . . . . . . . . . . . .  31
   Appendix B.  Acknowledgments  . . . . . . . . . . . . . . . . . .  31
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  32

1.  Introduction

   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
   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.

   3.  Routers internally check for AP's validity and select Chosen
       Prefixes (CPs).

   4.  Once a link is given an assignment, routers may get addresses
       from specified address pools and hosts may be configured using
       SLAAC or by the per-link elected DHCP server.

   This algorithm, which intends to fulfill requirements specified in
   [I-D.ietf-homenet-arch], has the following features:

   o  Each delegated prefix is effectively divided so that each link is
      assigned a reasonable part.  If the delegated prefix is too small
      given the size of the network, prefixes of arbitrary lengths may
      be used.

   o  The algorithm is completely distributed.  Routers may join or
      leave and DPs may be added or removed at any time.

   o  IPv4 connectivity is provided when a home router acquires an IPv4
      address and default route from an external source.  In this case a
      private IPv4 delegated prefix is generated and prefixes are
      assigned similarly to IPv6.

   o  The network may spontaneously generate and use a Unique Local
      Address (ULA) prefix.

   o  Assignments are stable across reboots and some network changes
      (e.g. adding or removing routers).

   o  DHCP options like DNS servers, prefix colors
      [I-D.bhandari-dhc-class-based-prefix], or any upcoming options may
      be attached to each prefix and may be relayed down to the host
      when it is given addresses.

   o  The user can manually assign prefixes to links.  Such assignments
      will take precedence over automatically assigned prefixes.

   o  Assignments and interfaces can be given priorities.  When a
      delegated prefix is too small, such values may be used to
      prioritize prefix assignment to certain links.

4.  Router Behavior

   All home routers participating in the prefix assignment algorithm
   MUST fulfill the requirements defined in this document and use a
   common flooding protocol and routing protocol.  Classic CPE routers
   [RFC7084] are supported as downstream routers and dowstream DHCPv6-PD
   enabled routers are supported as both downstream and uplink routers,
   but problems may occur when such router is connected to the home
   network on both WAN and LAN side.  In the later case, finer external
   interface detection algorithm or static configuration can be used to
   solve the issue, but these are out of the scope of this document.

4.1.  Data structures

   Each router MUST maintain a list of all the Delegated Prefixes.
   These prefixes may be locally generated, as described in Section 4.3,
   or come from other routers as described in Section 5.4.

   Each router MUST maintain a list of all the Assigned Prefixes
   advertised by other routers.  Each AP is learnt through the
   mechanisms described in Section 5.3 and is defined as a tuple of:

   Prefix:  The assigned prefix.

   Router ID:  The identifier of the advertising router.

   Link ID:  If the assignment is made on a connected link, an interface
         identifier of the interface connected to that link.

   Authoritative bit:  A boolean that tells whether the assignment comes
         from a network authority (DHCPv6 PD, manual configuration,
         etc...).

   Assignment's Priority:  A value between PRIORITY_MIN and
         PRIORITY_MAX, specifying the assignment's priority.

   The AP list is the result of the information provided by the flooding
   protocol, as specified in Section 5.3.

   The router MUST maintain a list of all prefixes currently chosen to
   be applied on connected links.  They are Chosen Prefixes (CPs) and
   described by a tuple of:

   Prefix:  The assigned prefix.

   Link ID:  An interface identifier of the interface connected to the
         link on which the assignment is made.

   Authoritative bit:  A boolean that tells whether the assignment comes
         from a network authority (DHCPv6 PD, manual configuration,
         etc...).

   Assignment's Priority:  A value between PRIORITY_MIN and
         PRIORITY_MAX, specifying the assignment's priority.

   Advertised:  Whether that assignment is being advertised by the
         flooding protocol (see Section 5.3).

   Applied:  Whether that assignment is applied on link's configuration
         (see Section 4.6).

   Chosen Prefixes that are marked as 'Advertised' are distributed to
   other routers using the flooding protocol and are therefore
   considered as Assigned Prefixes by other routers.  The goal of the
   Prefix Assignment Algorithm is to ensure that all routers have a
   consistent view of Assigned Prefixes on each link.

   The router MUST maintain a database of its own address assignments,
   and address assignments made by other routers on connected links as
   learnt through means described in Section 5.5.

4.2.  Routers' Interfaces

   Each interface MUST either be considered as internal or external.
   Prefixes and addresses are only assigned to internal interfaces.  The
   criteria to make this distinction are out of the scope of this
   document.

   If an internal interface becomes external, all prefixes and addresses
   assigned on the considered interface MUST be deleted and no longer
   announced, and the prefix assignment algorithm MUST be run.

   If an external interface becomes internal, the prefix assignment
   algorithm MUST be run (see Section 6.1).

   Whenever two or more interfaces are connected to the same link, all
   but one of them SHOULD be ignored by the prefix assignment algorithm.
   A mechanism to detect such situation SHOULD be provided by the
   flooding algorithm.

4.3.  Obtaining a Delegated Prefix

   Delegated Prefixes (Of any kind: Global, ULA, IPv4...) can be
   obtained or generated through different means:

   o  It can be delegated by a service provider (DHCPv6 PD, 6rd
      [RFC5969], etc..).

   o  It can be provisioned by an administrative authority (user
      configuration, netconf [RFC6241], etc... ).

   o  A ULA prefix may be spontaneously generated as defined in
      Section 9.1.

   o  An IPv4 private prefix may be spontaneously generated as defined
      in Section 9.2.

   DHCP options MAY be attached to a delegated prefix by the router that
   either generated the prefix or received it through DHCPv6 PD.  IPv6
   delegated prefix options MUST be encoded as DHCPv6 options.  IPv4
   delegated prefix options MUST be encoded as DHCPv4 options.

   As DHCP options are numerous and new ones may be defined, specifying
   routers' behavior regarding each option is out of the scope of this
   document.  In order to avoid misconfiguration, routers must follow
   the two following general rules:

   o  A router MUST NOT advertise a prefix obtained through DHCPv6 PD if
      it doesn't understand the all of the provided options.

   o  A router MUST NOT make or accept any assignment associated to a
      delegated prefix if it doesn't understand the all of the DHCP
      options advertised with the delegated prefix.

   The mif working group may provide useful inputs concerning the way
   the home network should handle different prefixes associated with
   heterogeneous uplinks.

4.4.  Network Leader

   A router considers itself as the Network Leader if and only if its
   router ID is greater than all other router IDs in received Prefix
   Assignments and Delegated Prefixes.

4.5.  Designated Router

   On a link where custom host configuration must be provided, or
   whenever SLAAC cannot be used, a DHCP server must be elected.  That
   router is called designated router and is dynamically chosen by the
   prefix assignment algorithm.

   A router MUST consider itself designated router on a given link if
   either one of the following conditions holds:

   o  The link's Assigned Prefixes list is empty. i.e. no other router
      is advertising assignments on the considered link.  And, if such
      information is provided by the flooding protocol, the router has
      the highest id on the link.

   o  Considering all APs and advertised CPs on the given link, the
      router is advertising the one with:

      1.  The lowest authoritative bit.

      2.  In case of tie, the lowest priority.

      3.  In case of tie, the highest router ID.

         Note: That particular order (inverted compared to assignments'
         priority) is motivated by the few cases where a router may
         override an existing assignment by advertising an assignment of
         higher priority.  In such a case, the designated router should
         remain the same.

         Example: A new router is powered on and connected to another
         router that was already there (doing DHCP).  It sees the
         assigned prefix for their common link, but also has, in its own
         configuration, an authoritative assignment for the link.  It
         starts advertising the authoritative assignment, which causes
         the second router to remove its previous assignment.  Thanks to
         the inverted order, the DHCP server will remain the same.

4.5.1.  Sending Router Advertisement

   On a given link, the designated router MUST send router
   advertisements (RAs) including Prefix Information Options for all the
   Chosen Prefixes associated to that link.  SLAAC SHOULD be enabled
   when possible, unless the configuration states otherwise.  Prefixes
   valid and preferred lifetimes MUST be set to values lower or equal to
   the associated Delegated Prefix's valid and preferred lifetimes.

   Whenever an IPv6 default route is present in the RIB, the designated
   router MUST advertise itself as default router by specifying a
   strictly positive valid lifetime.  Whenever the last default route is
   removed, the designated router MUST send an RA with the valid and
   preferred lifetimes set to zero.

   The designated router MUST advertise itself as a router for all IPv6
   delegated prefixes using Route Information Options [RFC4191],
   independently of whether there is a default route or not.

4.5.2.  DHCP Server Operations

   On a given link, whenever SLAAC can't be used for all assignments, or
   DHCP configuration options must be provided to hosts, the designated
   router MUST act as a DHCP server and serve addresses on the given
   link.  A router MUST stop behaving as a DHCP server whenever it is
   not the link's designated router anymore.

   Routers's addresses pool, specified in Section 7, MUST be excluded
   from DHCP hosts pools.

   The valid and preferred lifetimes MUST be set to values lower or
   equal to the associated Delegated Prefix's valid and preferred
   lifetimes.

4.6.  Applying an Assignment on an Interface

   Once a Chosen Prefix is created, a router first waits some time in
   order to detect possible collisions (Section 8).  Afterwards and if
   no collision is detected, the prefix is applied as follows:

   o  The router updates its interface configuration so that the prefix
      is assigned to the considered link.

   o  The router updates the routing protocol configuration so that it
      starts advertising the prefix.  Depending on the implementation,
      this step may not be needed as the routing protocol directly gets
      its configuration information from the interfaces configuration.

   o  If necessary, the router starts selecting an address for itself as
      defined in Section 7.

   o  If the router is the designated router on the considered link, it
      starts sending the Prefix Information Option with the considered
      prefix, as specified in Section 4.5.1.

   o  If the router is the designated router on the considered link and
      if the prefix requires DHCP configuration, it starts behaving as a
      DHCP server, as defined in Section 4.5.2, for the considered
      assigned prefix.

   When a prefix assignment is removed, the previous steps MUST be
   undone.  The router MUST also deprecate the prefix, if it had been
   advertised in Router Advertisements on an interface.  The prefix is
   deprecated by sending Router Advertisements with the PIO's preferred
   lifetime set to 0 [RFC4861].  Hosts that support DHCP reconfigure
   extension ([RFC3203], [RFC3315]) and that have been given leases MUST
   be reconfigured as well.

4.7.  DNS Support

   DHCP options attached to each delegated prefixes and propagated
   through the flooding protocol SHOULD contain the DHCP DNS options
   provided by the ISP (when provided).

   Whenever the router knows which DNS server to use, or is acting as a
   DNS relay, it SHOULD include DNS DHCP options ([RFC3646]) within
   host's configuration messages and include the Router Advertisement
   DNS options ([RFC6106]) when sending RAs.

   DNS server selection in multi-homed networks is a complex issue that
   this document doesn't intend to solve.  One should look at IETF's mif
   working-group documents in order to obtain guidelines concerning DNS
   server selection.  It is RECOMMENDED that designated routers turns on
   a local DNS relay that fetches information from provided DNS servers.

5.  Flooding Protocol Requirements

   In this document, the Flooding Protocol (FP) refers to a protocol
   enabling information propagation to the whole network.  It was not
   specified in order to allow the working group to independently decide
   which routing protocol, configuration protocol, and prefix assignment
   method to use within the home network.  Routing protocol, like OSPFv3
   [RFC5340] (With its autoconf extension
   [I-D.ietf-ospf-ospfv3-autoconfig]) or IS-IS [RFC5308], could be
   extended in order to fulfill the requirements.  An independent
   protocol, for instance HNCP [I-D.ietf-homenet-hncp], could be used as
   well.

   The specified algorithm can use any protocol that fulfills the
   requirements specified in this section.

5.1.  Router ID

   The FP MUST provide a router ID.  ID collisions within the network
   MUST be rare and any conflicts MUST be resolved by the flooding
   protocol.  When the router ID is changed, the FP MUST immediately
   provide the new ID to the Prefix Assignment Algorithm, which will in
   turn be run again, without requiring the current state to be flushed.

   In the absence of collisions, the router ID MUST NOT be changed, and
   it SHOULD be stable across reboots, power cycling and router software
   updates.

5.2.  Propagation Delay

   The FP MUST provide an approximate upper bound of the time it takes
   for an update to be propagated to the whole network.  This value is
   referred to as the FLOODING_DELAY.  The algorithm ensures that, as
   long as the upper bound is respected, two identical prefixes will
   never be applied to different links, and two different prefixes will
   never be applied to the same link.  The algorithm and the network
   will recover when the upper bound is exceeded, but collisions may
   appear in the routing protocol and errors may be propagated to upper
   layers.

   If the FP supports link-local flooding, which is used for router's
   address assignments, it SHOULD provide an approximate upper bound of
   the time it takes for an update to be propagated to a single link.
   This value is referred to as the FLOODING_DELAY_LL.  If link-local
   flooding is not available, or the value is not provided, the
   assignment algorithm MUST use the FLOODING_DELAY value instead.

5.3.  Flooding Assigned Prefixes

   The FP MUST provide a way to flood Chosen Prefixes marked as
   advertised and retrieve prefixes assigned by other routers (APs).
   Retrieved APs MUST contain all the information specified in
   Section 4.1.

5.4.  Flooding Delegated Prefixes

   The FP must provide a way to flood Delegated Prefixes and retrieve
   prefixes delegated to other routers.  Retrieved entries must contain
   the following information.

   Prefix:  The delegated prefix.

   Router ID:  The router ID of the router that is advertising the
         delegated prefix.

   Valid until:  A time value, in absolute local time, specifying the
         prefix validity time.

   Preferred until:  A time value, in absolute local time, specifying
         the prefix preferred time.

   DHCP information:  DHCP options attached to the delegated prefix.

   The FP MUST make sure time values are consistent throughout the
   network (i.e. differences are small compared to Delegated Prefixes
   lifetimes).  If no time synchronization protocol is used, the FP MUST
   keep track of prefix age across the network and within its database.

5.5.  Flooding Routers' Address Assignments

   Routers addresses are dynamically allocated, picked from a defined
   pool, and collisions must be detected using the FP.  The FP MUST
   provide a way to flood routers' addresses.  The flooding scope of
   those values SHOULD be link-local, but as addresses are unique within
   the home network, this is not mandatory.  For each address
   assignment, the FP SHOULD provide the identifier of the interface
   connected to the link the address assignment was advertised on.

6.  Prefix Assignment Algorithm

   The Prefix Assignment Algorithm is a distributed algorithm that
   assigns one prefix from each available Delegated Prefix on every link
   that is considered to be internal by at least one connected router.
   The algorithm itself does not distinguish between global IPv6, ULA or
   IPv4 prefixes.  IPv4 prefixes are encoded as their IPv4-mapped IPv6
   form, as defined in [RFC4291] (i.e. ::ffff:A.B.C.D/X with X >= 96).

   When the Prefix Assignment Algorithm is executed, combinations of
   Delegated Prefixes and internal interfaces are being considered.  For
   the purpose of this discussion, the Delegated Prefix will be referred
   to as the current Delegated Prefix, and the interface will be
   referred to as the current Interface.  If a delegated prefix is
   included inside another delegated prefix, it is ignored.  This rule
   intends to ignore prefixes delegated from non-Homenet routers that
   previously obtained their larger prefix from one of Homenet's
   routers.

   The algorithm is specified here for the sake of clarity.  It can be
   optimized in some cases.  For instance Prefix Assignment deletion
   might not need to trigger algorithm's execution if all internal
   interfaces already have assignements associated to the same Delegated
   Prefix.  Similarly, when an ignored Delegated Prefix is deleted, it
   is not necessary to run the algorithm.  An implementation may work
   differently than specified here as long as the resulting behavior is
   identical to the behavior a router implementing this exact algorithm
   would have.

6.1.  When to execute the Prefix Assignment Algorithm

   The algorithm MUST be run whenever one of the following event occurs:

   o  A Delegated Prefix is created or deleted (A DP must be deleted
      when its lifetime is exceeded).

   o  A Prefix Assignment is created, deleted or modified.

   o  The router ID is modified.

   o  An external link becomes internal, or an internal link becomes
      external.

   It is not required that the algorithm is synchronously run each time
   such an event occurs.  But the delay between the event and the  17

1.  Introduction

   This document specifies a distributed 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 for automatic prefix
   assignment.  Given a Chosen Prefix is said set of delegated prefixes, nodes may assign
   available prefixes to be valid if all links they are directly connected to, or for
   their private use.  The algorithm ensures that the following conditions
   assertions are met: eventually true:

   1.  Its  At most one prefix is included in an advertised Delegated Prefix.

   2.  The from each delegated prefix is not included or does not include any other assigned to each
       link.

   2.  Assigned
       Prefix with a higher precedence.

   3.  No other assignment which prefix is prefixes are not 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 do not overlap with any
   other assignment by any include other router in the network.

6.5.  Accepting an
       assigned prefixes.

   3.  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.

   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 prefixes do not change in the
      entry still exists.

6.6.  Making a New Assignment absence of topology or
       configuration changes.

   In situations where a router can make an assignment (see
   Section 6.9), the following rules are used in rest of this document the following order:

   1.  If two first conditions are referred to
   as the configuration specifies a custom behavior (e.g. always
       ignore/accept a particular delegated prefix), use correctness conditions of the
       configuration entry.

   2.  If algorithm while the Delegated Prefix Preferred Lifetime third
   condition is strictly greater
       than zero, an referred to as its convergence condition.

   Each assignment MUST be made.

   3.  If no other prefix has a non-zero Preferred Lifetime, and no
       assignment is made on priority specified by the link, an assignment SHOULD be made.

   4.  Otherwise, a new node making the
   assignment, allowing for more advanced assignment SHOULD NOT be made. policies.  When
   multiple nodes assign different prefixes from the algorithm decides to make a new assignment, it first needs same delegated
   prefix to specify the desired size of same link, or when multiple nodes assign overlapping
   prefixes, the assigned prefix.  Although this
   algorithm intends to remain generic, assignment with the use of 64 bits long prefixes highest priority is RECOMMENDED (See [I-D.ietf-6man-why64]). kept and other
   assignments are removed.

   The following table MAY
   be used as default values, where X is the length of the delegated
   prefix.

   If X <= 64:  Prefix length = 64 prefix assignment algorithm requires that participating nodes
   share information through a flooding mechanism.  If X >= 64 and X < 104:  Prefix length = X + 16 (up the flooding
   mechanism ensures that all messages are propagated to 2^16 links)

   If X >= 104 and X < 112:  Prefix length = 120 (2^8 addresses per link
         and more all nodes
   faster than 2^8 links)

   If X >= 112 and X <= 128:  Prefix length = 120 + (X - 112)/2 (Link Vs
         Addresses tradeoff)

   When a given timing upper bound, the algorithm decides to make a new assignment, it SHOULD first
   checks its stable storage also ensures
   that all assigned prefixes used for networking operations (e.g., host
   configuration) remain unchanged, unless another node assigns an available
   overlapping prefix with a higher assignment that was
   previously applied on the current interface and is part of priority, or the
   current delegated prefix.  If no available assignment can topology
   changes and renumbering cannot be found
   that way, avoided.

2.  Terminology

   In this document, the new prefix MUST key words "MAY", "MUST, "MUST NOT", "OPTIONAL",
   "RECOMMENDED", "SHOULD", and "SHOULD NOT", are to be randomly selected among a subset interpreted as
   described in [RFC2119].

   This document makes use of
   available the following terminology:

   Link:   An object the distributed algorithm will assign prefixes (if possible, large enough to avoid collisions).

   Hardware specific identifiers to.
      A Node may be used only assign prefixes to seed a pseudo-random
   generator.

   If no available prefix Links it is found, directly connected
      to.  A Link is either Shared or Private.

   Private Link:   A Private Link is an abstract concept defined for the assignment fails.

   The algorithm leaves much room
      sake of this document.  It allows nodes to make assignments for implementation specific policies.
      their private use or delegation.  For instance, static prefixes may every DHCPv6-PD
      [RFC3633] client MAY be configured considered as specified in
   Section 10.  If implemented, the router MAY also decide to execute a different Private Link.

   Shared Link:   A Link multiple nodes are connected to.  Most of the Prefix Scarcity Avoidance mechanisms, as proposed
      time, a Shared Link would consist in Appendix A.

   If an available prefix is found, a new assignment is made multi-access link or point-
      to-point link, virtual or physical, requiring prefixes to be
      assigned to.

   Delegated Prefix:   A prefix provided to the algorithm and used as a new
   Chosen Prefix entry is created.

   o  The
      prefix pool for Assigned Prefixes.

   Node ID:   A value is identifying a given participating node.  The set
      of identifiers MUST be strictly and totally ordered (e.g.,
      alphanumeric order).

   Flooding Mechanism:   A mechanism implementing reliable broadcast and
      used to advertise published Assigned Prefixes.

   Flooding Delay:   Optional value provided by the chosen prefix.

   o  The link ID is the ID Flooding Mechanism
      indicating a deterministic or likely upper bound of the link on which
      information propagation delay.  When the assignment is made.

   o  The authoritative bit is set to false.

   o  The priority is set to Flooding Mechanism does
      not provide 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 value, it is set when the timer elapsed if the
      entry still exists. to DEFAULT_FLOODING_DELAY
      (Section 7).

   Advertised Prefix:   A new assignment is always marked as prefix advertised when created by another node and
   therefore immediately provided
      delivered to the flooding protocol.

6.7.  Using Authoritative local node by the Flooding Mechanism.  It has an
      Advertised Prefix Assignments

   When some authority (Delegating router, system admin, etc...) wants
   to manually enforce some behavior, it may ask some router Priority and, when assigned to make a directly
      connected Shared Link, is associated with a Shared Link.

   Advertised Prefix Priority:   A value that defines the priority of an
   Authoritative
      Advertised Prefix Assignment.  Such assignments have their
   Authoritative bit set, SHALL NOT be overridden, and will appear in
   other router's database as received from the Flooding Mechanism or a
      published Assigned Prefix.  Whenever multiple Advertised Prefixes
      are conflicting, all Advertised Prefixes but the one with the Authoritative
   bit set.

   There
      greatest priority will eventually be removed.  In case of tie, the
      assignment advertised by the node with the greatest Node ID is
      kept and others are two kinds removed.  In order to ensure convergence, the
      range of Authoritative Prefix Assignments.

   o  When priority values MUST have an authority wants upper bound.

   Assigned Prefix:   A prefix included in a Delegated Prefix and
      assigned to a Shared or Private Link.  It represents a local
      decision to assign some particular a given prefix from a given Delegated Prefix to some
      interface, an Authoritative
      a given Link.  The algorithm ensures that there never is more than
      one Assigned Prefix per Delegated Prefix Assignment MAY be created and
      consists in a Chosen Link pair.  When
      destroyed, an Assigned Prefix which have its Authoritative bit is set as not applied, ceases to be
      advertised, and which is advertised.  Just like normal assignments, it MUST
      NOT be applied before removed from the delay specified in Section 8 elapsed.

   o set of Assigned Prefixes.

   Applied (Assigned Prefix):   When an authority wants to prevent some prefix from being used, an
      Authoritative Assignment Assigned Prefix is applied, it
      MAY be advertised.  Such assignments MUST
      NOT be applied and MUST be advertised through the flooding used (e.g., for host configuration, routing protocol as assigned to either no-interface, or a fake interface
      (Depending on the flooding protocol's capabilities).

   When a delegated
      configuration, prefix is obtained through DHCPv6 PD with a non-
   empty excluded prefix, as specified in [RFC6603], an Authoritative
   Prefix Assignment delegation).  When not applied, it MUST NOT
      be created with the excluded prefix.

      Note: If the router doesn't understand the excluded prefix DHCPv6
      option, used for any other purposes than the delegated prefix assignment
      algorithm.  Each Assigned Prefix is ignored, as specified in
      Section 4.3.

6.8.  Choosing the Assignment's Priority

   When either associated with a new timer (Apply
      Timer) used to apply the Assigned Prefix.  An Assigned Prefix Assignment is made, or an Authoritative
      unapplied when destroyed.

   Published (Assigned Prefix):   The Assigned Prefix Assignment is created, advertised
      through the creating router needs Flooding Mechanism as assigned to choose
   which priority value its associated Link.
      A published Assigned Prefix MUST have an Advertised Prefix
      Priority.  It will appear as an Advertised Prefix to use.  The assignment priority is kept by the
   designated router when it starts advertising other nodes,
      once received through the assignment, Flooding Mechanism.

   Backoff Timer:   Every Delegated Prefix and Link pair is associated
      with a timer counting down to zero.  It 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 to avoid multiple
      nodes from making colliding assignments by delaying 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 creation
      of new Assigned Prefixes or dynamic configuration).

   o  Other values are reserved.

6.9.  Prefix Assignment Algorithm steps

   At the beginning advertisement 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 adopted Assigned
      Prefixes by a random amount of time.

   Renumbering:   Event occuring when an Assigned Prefix which was
      applied is the designated router, destroyed.  It is undesirable as specified in Section 4.5.

   The following steps are then executed for every combination it usually implies
      reconfiguring routers or hosts.

3.  Applicability statement

   Each node MUST have a set of
   delegated prefixes disjoint Delegated Prefixes.  It MAY
   change over time and interfaces.

   o  If the current interface is external, ignore that interface.

   o  If be different from one node to another at some
   point, but nodes MUST eventually agree on the same set of disjoint
   Delegated Prefixes.

   Given this set of disjoint Delegated Prefixes, nodes may assign
   available prefixes from each Delegated Prefix is strictly included in another Delegated
      Prefix, ignore that delegated prefix.

   o  If to the Links they are
   directly connected to.  The algorithm ensures that at most one prefix
   from a given Delegated Prefix is equal assigned to another Delegated Prefix,
      advertised by some router with a given Link.

   The algorithm can be applied to any address space and can be used to
   manage multiple address spaces simultaneously.  For instance, an higher router ID than
   implementation can make use of IPv4-mapped IPv6 addresses [RFC4291]
   in order to manage both IPv4 and IPv6 prefix assignment
   simultaneously.

   The algorithm supports dynamically changing topologies:

   o  Nodes may join or leave the
      considered delegated prefix, ignore that delegated prefix. set of participating nodes.

   o  Look for  Nodes may join or leave Links.

   o  Links may be joined or split.

   All nodes MUST run a valid common Flooding Mechanism in order to share
   published Assigned Prefix, advertised by another router on Prefixes.  The set of participating nodes is
   defined as the current interface and included set of nodes participating in the current Delegated
      Prefix. Flooding Mechanism.

   The Flooding Mechanism MUST:

   o  Look for  Provide a Chosen Prefix associated way to the current interface flood Assigned Prefixes assigned to a directly
      connected Link along with their respective Advertised Prefix
      Priority and
      included in the current Delegated Prefix. Node ID of the node which advertises it.

   o  There are four possibilities at this stage.

      1.  If no AP is found,  Specify whether an Advertised Prefix was assigned to a directly
      connected Shared Link, and no CP is found, if so, on which one.

   In addition, a new assignment can Flooding Delay SHOULD be
          made if specified and only if the router considers itself as the
          designated router.  Whether respected in
   order to create an assignment avoid undesired renumbering.  If not specified, or not,
          and which prefix whenever
   the Flooding Mechanism is unable to respect the provided delay,
   renumbering may happen.  As such delay often depends on the size of
   the network, it MAY change over time and MAY be different from one
   node to use, is specified in Section 6.6.

      2.  If an AP another.

   The algorithm ensures that whenever the Flooding Delay is found, provided
   and no CP is found, respected, and in the AP MUST be
          accepted.  The new CP's advertised bit absence of topology change or delegated
   prefix removal, renumbering never happens.

   Each node MUST be set if have a Node ID.  Node IDs MAY change over time and only
          if the router considers itself as be
   the designated router.

      3.  If no AP is found, and same on multiple nodes at some point, but each node MUST
   eventually have a CP Node ID which is found, unique among the router MUST check if set of
   participating nodes.

4.  Algorithm Specification

   This section specifies the CP's assignment is valid.  If it is, behavior of nodes implementing the local prefix
   assignment
          is marked as valid and advertised.  If it isn't, it is
          destroyed and the algorithm.

4.1.  Algorithm Terminology

   The algorithm applies case 1.

      4.  If both an AP and makes use of the following terms:

   Current Assignment:   For a CP are found, given Delegated Prefix and Link, the router must check if
      Current Assignment is the
          prefixes are Assigned Prefix (if any) included in the same.  If they are different
      Delegated Prefix and if assigned to the given Link.

   Best Assignment:   For a given Delegated Prefix and Link, the CP's
          Authoritative bit Best
      Assignment is not set, (if any) the CP MUST be deleted and Advertised Prefix:

      *  Including or included in the
          algorithm applies Delegated Prefix.

      *  Assigned on the given Link.

      *  Having the greatest Advertised Prefix Priority among Advertised
         Prefixes (and, in case 2.  If of tie, the prefixes are prefix advertised by the same,
         node with the
          CP must be updated greatest Node ID among all prefixes with greatest
         priority).

      *  Taking precedence over the AP's priority value, marked as
          valid, Current Assignment (if any)
         associated with the same Link and advertised Delegated Prefix.

   Precedence:   An Advertised Prefix takes precedence over an Assigned
      Prefix if and only if if:

      *  The Assigned Prefix is not published.

      *  The Assigned Prefix is published and the router considers
          itself as designated on Advertised Prefix
         Priority from the link.

   In Advertised Prefix is strictly greater than
         the Advertised Prefix Priority from the end all Assigned Prefix.

      *  The Assigned Prefix is published, the assignments that are marked as invalid priorities 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 equal, 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 Node ID from the router,
   depending on node advertising the Flooding Protocol capabilities.  By default
   assignments priorities MUST be between PRIORITY_AUTO_MIN and
   PRIORITY_AUTO_MAX, SHOULD be lower Advertised Prefix is
         strictly greater than PRIORITY_DEFAULT, and the
   authoritative bit MUST not be set.  Whenever such an assignment
   becomes invalid, DHCPv6 Reconfigure SHOULD be used in order to remove the prefix from DHCPv6 DP client's lease.  If DHCPv6 Reconfigure local Node ID.

   Valid (Assigned Prefix)  An Assigned Prefix is
   not supported, leases lifetimes SHOULD be significantly small.

   Provided DPs' valid if 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 only 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 two following conditions are able to run with these
   addresses.  In some cases though, a router may need to take one met:

      *  No Advertised Prefix including or
   multiple addresses among one included in the Assigned
         Prefix takes precedence over the Assigned Prefix.

      *  No Advertised Prefix including or multiple available Delegated
   Prefixes.  For example:

   o  The router needs connectivity to included in the internet (For management, NTP
      synchronization, etc...).

   o  The router needs connectivity within same
         Delegated Prefix as 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 Assigned Prefix and assigned to get addresses.  This document
   proposes an Address Assignment Algorithm that extends the
         same Link takes precedence over the considered Assigned Prefix.

4.2.  Prefix Assignment Algorithm and works as follows.  Each Routine

   This section specifies the prefix assignment algorithm routine.  It
   is
   associated with a fixed address pool, reserved defined for router's addresses
   assignment.  The address pool is a prefix which value is
   deterministically function of given Delegated Prefix/Link pair and may be run
   either as triggered by 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 Backoff Timer, or not.

   For a given Delegated Prefix and collisions are detected.  Routers Link pair, the routine MUST keep track of Address Assignments made by other routers on
   connected links by using information provided be run
   as not triggered by the flooding
   algorithm, as defined Backoff Timer whenever:

   o  An Advertised Prefix including or included in Section 5.5.

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 considered
      Delegated Prefix is defined as
   follows:

   If X <= 64:  SLAAC MUST added or removed.

   o  An Assigned Prefix included in the considered Delegated Prefix and
      associated with a different Link than the considered Link was
      destroyed, while there is no Current Assignment associated with
      the given pair.  This case MAY be used

   If X > 64 and X <= 110: ignored if the creation of a new
      Assigned Prefix associated with the considered pair is not
      desired.

   o  The pool considered Delegated Prefix is A/112 (2^16 addresses)

   If X >= 110 and X <= 126: added.

   o  The pool considered Link is A/(X + 2) (One quarter of the
         available addresses)

   If X >= 126:  Only added.

   o  The Node ID is modified.

   Additionaly, for a given Delegated Prefix and Link pair, the designated router MAY use A/128.  Other
         routers routine
   MUST NOT get be run as triggered by the Backoff Timer whenever:

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

   When such an address.

   In event occurs, a node MAY delay the case execution of IPv4 prefixes, the network address (first address
   routine instead 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 executing it intends to use, immediately, e.g. while receiving an
   update from the Flooding Mechanism, or is using for security reasons (see
   Section 8).  Even though other events occur in the address specified by this
   assignment.  An assignment, made by some router, meantime, the
   routine MUST be advertised
   on the link on which the assignment run only once.  It is made.  Similarly, an address
   assignment also assumed that, whenever one
   of these events is said to be applied when the address Backoff Timer firing, the routine is pushed executed
   as triggered by the Backoff Timer.

   In order to execute the
   router's interface configuration.  It is unapplied otherwise.

   Routers MUST store applied address assignments in their stable
   storage routine for a given Delegated Prefix/Link
   pair, first look for the Best Assignment and reuse Current Assignment
   associated with the same addresses whenever possible.  At least Delegated Prefix/Link pair, then execute the
   five previously applied addresses SHOULD be stored for each
   interface.

   For
   corresponding case:

   1.  If there is no Best Assignment and no Current Assignment: Decide
       whether the creation of a new assignment for the given prefix assignment, an address Delegated
       Prefix/Link pair is said to desired (As any result would be available if
   it is within valid, the router's address pool associated to
       way the prefix
   assignment, decision is taken is out of the scope of this document)
       and do the following:

       *  If it is not being advertised by any other router.  If desired, stop the flooding protocol provides interface identifier in execution of the address
   assignments, looking for collisions on considered link routine.

       *  Else if the Backoff Timer is enough.

   A new address assignment MUST be chosen randomly among available
   addresses.  An address assignment MUST NOT be applied when one running, stop the execution of
          the
   following condition is true.

   o  The associated Chosen Prefix is routine.

       *  Else if the routine was not applied.

   o  The timer specified in executed as triggered by the
          Backoff Timer, set the Backoff Timer to some random delay
          between ADOPT_MAX_DELAY and BACKOFF_MAX_DELAY (see Section 8 has not elapsed yet.

   An address 7)
          and stop the execution of the routine.

       *  Else, continue the execution of the routine.

       Select a prefix for the new assignment must (see Section 5 for
       guidance regarding prefix selection).  This prefix MUST be
       included in or be deleted whenever one of equal to the following
   condition becomes true.

   o  The associated Chosen considered Delegated Prefix is deleted and
       MUST NOT include or moved to another link.

   o  Some other router with be included in any Advertised Prefix.  If a higher router ID
       suitable prefix is advertising the same
      address on found, use it to create a new Assigned Prefix:

       *  Assigned to the same link.

8.  Hysteresis Principle considered Link.

       *  Not applied.

       *  The IPv6 Stateless Address Autoconfiguration [RFC4862] states that
   host addresses can be kept up Apply Timer set 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. '2 * Flooding Delay'.

       *  Published with some selected Advertised Prefix and Address assignments

   When the flooding protocol Priority.

   2.  If there is started, a Best Assignment but no Current Assignment: Cancel
       the router MUST wait
   FLOODING_DELAY before executing Backoff Timer and use 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 the Best Assignment to
       create a new Assigned Prefix:

       *  Assigned to the considered Link.

       *  Not applied.

   o  A router MUST NOT apply

       *  The Apply Timer set to '2 * Flooding Delay'.

       *  Not published.

   3.  If there is a Chosen Prefix before it has waited
      2*FLOODING_DELAY. Current Assignment but no Best Assignment:

       *  If the entry Current Assignment is valid during not valid, destroy it, and
          execute the whole waiting
      time, it MUST be applied to routine again, as not triggered by the link it is assigned.

   o  A router MUST NOT apply an Assigned Address before it has waited
      2*FLOODING_DELAY_LL. Backoff
          Timer.

       *  If the assignment Current Assignment is valid during and published, stop the whole
      waiting time, it MUST be applied to
          execution of the interface it routine.

       *  If the Current Assignment 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 valid and not published, the uplink MUST be modified
   in node
          MAY either:

          +  Adopt the following way.

   o  The Preferred Lifetime is prefix by cancelling the Apply Timer and set the
             Backoff Timer to 0.

   o  The Valid Lifetime some random delay between 0 and
             ADOPT_MAX_DELAY (see Section 7).  This procedure is set used to
             avoid renumbering when the minimum between node advertising the current Valid
      Lifetime prefix left
             the Shared Link.

          +  Destroy it and execute case 1 in order to create a
             different assignment.

   4.  If there is a Current Assignment and a Best Assignment:

       *  Cancel the Backoff Timer.

       *  If the two hours.

   o  The default route associated with prefixes are identical, set the prefix Current Assignment
          as not published.  If the Current Assignment is not advertised
      anymore.

   This behavior applied
          and the Apply Timer is similar not set, set the Apply Timer to [RFC7084] specifications '2 *
          Flooding Delay'.

       *  If the two prefixes are not identical, destroy the Current
          Assignment and provides
   stable host configuration in go to 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. 2.

   When a router receives a deprecated Delegated the prefix assignment algorithm routine requires an assignment
   to be created or adopted, any Advertised Prefix advertisement
   from Priority value can be
   used.  Other documents MAY provide restrictions over this value
   depending on the Flooding Protocol, it MUST remove context the Delegated Prefix from
   its Delegated Prefixes list. algorithm is operating in, or leave it
   as implementation-specific.

   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 assignment algorithm routine requires an assignment
   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 created or adopted, the chosen Advertised Prefix Generation

   ULA prefixes can Priority is
   unspecified (any value would be randomly generated as specified valid).  The values to be used in [RFC4193],
   enabling stable in-home IPv6 connectivity.
   such situations MAY be specified by other documents making use of the
   prefix assignment algorithm or be left as an implementation specific
   choice.

4.3.  Overriding and Destroying Existing Assignments

   In this section, we say a ULA delegated prefix is 'stable' if it has
   been addition to the only advertised ULA delegated prefix for at least
   2*FLOODING_DELAY seconds.  The behaviour behavior specified in Section 4.2, the following
   sections tend
   procedures MAY be used in order to reuse provide more advanced behavior
   (Section 6):

   Overriding Existing Assignments:   For any given Link and Delegated
      Prefix, a stable ULA prefix as long as its preferred
   lifetime is not null.

   Additionaly, we say node MAY create a router is the owner of new Assigned Prefix using a spontaneously
   generated ULA chosen
      prefix if it randomly created the and Advertised Prefix Priority such that:

      *  The chosen prefix is included in or is equal to the first
   place.  A router SHOULD NOT create more than one prefix this way, and
   MUST remember considered
         Delegated Prefix.

      *  The Current Assignment, if any, as well as all existing
         Assigned Prefixes which include or are included inside the prefixes they own.  As stated in the following
   sections, only the owner of a prefix can extend its lifetimes.

9.1.1.  Choosing the ULA prefix

   When a stable ULA
         chosen prefix are destroyed.

      *  It is advertised, all routers SHOULD remember
   that prefix alongwith its associated valid and preferred lifetime.
   If this prefix stops being advertised (e.g. due not applied.

      *  The Apply Timer set to a network split)
   while its preferred lifetime '2 * Flooding Delay'.

      *  It is not null, the same ULA prefix SHOULD
   be selected using published.

      *  The Advertised Prefix Priority is greater than the same valid and preferred lifetimes.

   If there was no stable ULA prefix advertised, Advertised
         Prefix Priority from all Advertised Prefixes which include or if the preferred
   lifetime of
         are included in the prefix chosen prefix.

      In order to ensure algorithm convergence:

      *  Such overriding assignments MUST NOT be created unless there
         was null, a prefix generated as specified change 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 node configuration, a ULA prefix whenever Link was added, or an
         Advertised Prefix was added or removed.

      *  The chosen Advertised Prefix Priority for the two
   following conditions are met:

   o  It is new Assigned
         Prefix SHOULD be greater than all priorities from the network leader.

   o  There is no other advertised ULA prefix. destroyed
         Assigned Prefixes.  If no IPv6 prefix is available at all, the network leader SHOULD
   start advertising a ULA delegated prefix.

   Additionaly, not, simple topologies with only two
         nodes may not converge.  Nodes which do not respect this rule
         MUST implement a router SHOULD start advertising its own ULA prefix
   whenever mechanism which detects whether the three following conditions are met:

   o  A stable ULA prefix is advertised by another router.

   o  The router owns
         distributed algorithm do not converge and, whenever this would
         happen, stop creating overriding Assigned Prefixes causing the advertised stable ULA prefix.

   o
         destruction of other Assigned Prefixes.  The preferred lifetime specifications for
         such safety procedures are out of the advertised ULA prefix scope of this document.

   Removing an Assigned Prefix:   A node MAY destroy any Assigned Prefix
      which is below 10
      minutes.

   This allows published.  Such an event reflects the desire from a router node
      to restart advertising not assign a owned prefix whenever
   the preferred lifetime is approaching zero.  Which later allows him from a given Delegated Prefix to extend the lifetime of the prefix.

   A router a given
      Link anymore.  In order to ensure algorithm convergence, such
      procedure MUST stop advertising NOT be executed unless there was a spontaenously generated ULA prefix
   whenever one of change in the two following condition is met:

   o  A different ULA prefix is being advertised.

   o  The same prefix
      node configuration.  Additionally, whenever an Assigned Prefix is advertised by another router, and
      destroyed this way, the router
      doesn't own that prefix.

9.1.3.  Extending prefix lifetime

   Routers assignment algorithm routine MUST regularly extend
      be run for the valid and preferred lifetimes of Delegated Prefix/Link pair associated with the ULA delegated
      deleted Assigned Prefix.

   These procedures are optional.  They could be used for diverse
   purposes, e.g., for providing custom prefix they advertise and own, so that they never
   drop assignment configuration
   or reacting to zero.

   When a router advertises a prefix it doesn't own, lifetimes are never
   extended. space exhaustion (by overriding short Assigned
   Prefixes and assigning longer ones).

4.4.  Other Events

   When the preferred lifetime of the prefix approaches zero,
   either the owner of Apply Timer fires, the associated prefix will start advertising MUST be applied.

   When the prefix Backoff Timer associated with a non-zero preferred lifetime, or given Delegated Prefix/Link
   pair fires while there is a new Current Assignment associated with the
   same pair, the Current Assignment MUST be published with some
   associated Advertised Prefix Priority and, if the prefix will is not
   applied, the Apply Timer MUST be generated.

9.1.4.  Authoritative ULAs

   This section doesn't prevent multiple ULA prefixes set to '2 * Flooding Delay'.

   When a Delegated Prefix is removed from existing
   simultaneously.  ULA prefixes may be provided by different means, as
   specified the set of Delegated
   Prefixes, all Assigned Prefixes included in Section 4.3. the removed Delegated prefixes that are delegated by a
   service provider or provisioned by an authority differ from
   'spontaneously' generated prefixes.  They
   Prefix MUST NOT be withdrawn if
   another ULA delegated prefix is observed. destroyed.

   When at least one of such ULA prefixes Delegated Prefix is used, spontaneously
   generated ULA prefixes replaced by another one that includes or
   is included in the deleted Delegated Prefix, all Assigned Prefixes
   which were included in the deleted Delegated Prefix but are withdrawned.

9.2.  IPv4 Private not
   included in the added Delegated Prefix Generation

   A router MUST be destroyed.  Others 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
   be kept.

   When a Link is advertised by any other router.

   A router removed, all Assigned Prefixes assigned to that Link
   MUST stop advertising an IPv4 be destroyed.

5.  Prefix Selection Considerations

   When the prefix whenever another router
   with an higher router ID is advertising an IPv4 Delegated Prefix.

   The IPv4 private assignment algorithm routine specified in Section 4.2
   requires a new prefix must to be included in one of selected, the private prefix MUST be selected
   either:

   o  Among prefixes defined which were previously assigned and applied on the
      considered Link.

   o  Randomly, picked in [RFC1918].  The prefix 10/8 SHOULD a set of at least RANDOM_SET_SIZE (see
      Section 7) candidate prefixes.  If less than RANDOM_SET_SIZE
      candidates can be used by
   default but it SHOULD found, the prefix MUST be configurable.  In picked among all
      candidates.

   o  Based on some custom selection process specified in the case
      configuration.

   A simple implementation MAY randomly pick the prefix among all
   available prefixes, but this strategy is inefficient in terms of
   address
   provided by space use as a few long prefixes may exhaust the ISP is already pool of
   available short prefixes.

   The rest of this section describes a private address, more efficient approach which
   MAY be applied any time a node needs to pick a different private prefix SHOULD be used.  For instance, for a new
   assignment.  The two following definitions are used:

   Available prefix:   The prefix A/N is available if the ISP and only if A/N
      does not include and is giving the
   address 10.1.2.3, 10/8 or not included in any sub-prefix Assigned or Advertised
      Prefix but A/(N-1) does include or is included in 10/8 SHOULD NOT
   be used.  (For instance, 172.16/12 an Assigned 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
      Advertised Prefix (or N equals 0 and there is no Assigned or
      Advertised Prefixes at all).

   Candidate prefix:   A prefix generation may be
   disabled whenever a global IPv6 which is made available.  This section
   details a few other possible configuration options.

   The implementation MAY allow each internal interface included in or is equal to be configured
   with a custom priority value. an
      available prefix.

   The specified priority SHOULD then be
   used when creating new assignments on the given interface.  If not
   specified, procedure described in this section takes the default priority SHOULD be used.

   The implementation SHOULD allow manual assignments on given links.
   When specified, and whenever such an assignment is valid, three following
   criteria into account:

   Stability:   In some cases, it MUST be
   advertised as Authoritative Assignments on is desirable that 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 selected prefix
      remains the same across executions and reboots.  For this purpose,
      prefixes previously applied on flooding
   protocol security features.  The flooding protocol SHOULD therefore
   check for the authenticity of advertised information.  Security modes Link or pseudo-random prefixes
      generated based on node and Link specific values may be classified in three categories.

   1.  The flooding protocol
      considered.

   Randomness:   When no stored or pseudo-random prefix is not protected.

   2.  The flooding protocol's protection chosen, a
      prefix may be randomly picked among RANDOM_SET_SIZE candidates of
      desired length.  If less than RANDOM_SET_SIZE candidates can be
      found, the prefix is binary: An allowed router picked among all candidates.

   Addressing-space usage efficiency:   In the process of assigning
      prefixes, a small set of badly chosen long prefixes may send easily
      prevent any type shorter prefix from being assigned.  For this reason,
      the set of packets in RANDOM_SET_SIZE candidates is created from the name set of other routers.

   3.  All advertised messages are individually signed by
      available prefixes with longest prefix lengths and, in case of
      tie, prefer small prefix values.

   When executing the sender.

   Whenever a malicious router attacks an unprotected network, or
   whenever a malicious router is able to authenticate itself to a
   network procedure, do as stated follows:

   1.  For each prefix stored in stable-storage, check if the second case, it prefix is
       included in or equal to an available prefix.  If so, pick that
       prefix and stop.

   2.  For each prefix length, count the number of available prefixes of
       the given length.

   3.  If the desired prefix length was not specified, select one.  The
       available prefixes count computed previously may for example:

   o  Prevent other routers be used to get help
       picking a stable router ID.

   o  Prevent other routers from making assignments by claiming prefix length such that:

       *  There is at least one candidate prefix.

       *  The prefix length is chosen great enough to not exhaust the
      whole available
          address space.

   o  Redirect traffic to some router on

       Let N be the network.

   If chosen prefix length.

   4.  Iterate over available prefixes starting with prefixes of length
       N down to length 0 and create a malicious router set of RANDOM_SET_SIZE candidate
       prefixes of length exactly N included in or equal to available
       prefixes.  The end goal here is able to authenticate itself in create a network
   protected as in the third case, most set of the previously listed attacks
   may still be performed, but traffic could only be redirected toward
   the origination
       RANDOM_SET_SIZE candidate prefixes of the attack, and the source length N included in a set
       of the attack could be
   identified. available prefixes of maximized prefix length.  In any case, in order to protect the network, the routing protocol as
   well as case of a
       tie, smaller prefix values (as defined by the way hosts bit-wise
       lexicographical order) 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 preferred.

   5.  For each pseudo-random prefix, check if the prefix is equal 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.

   [RFC4291]  Hinden, R. and S. Deering, "IP Version 6 Addressing
              Architecture", RFC 4291, February 2006.

   [RFC4861]  Narten, T., Nordmark, E., Simpson, W., and H. Soliman,
              "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,
              September 2007.

   [RFC4862]  Thomson, S., Narten, T., and T. Jinmei, "IPv6 Stateless
              Address Autoconfiguration", RFC 4862, September 2007.

   [RFC6106]  Jeong, J., Park, S., Beloeil, L., and S. Madanapalli,
              "IPv6 Router Advertisement Options for DNS Configuration",
              RFC 6106, November 2010.

   [RFC6603]  Korhonen, J., Savolainen, T., Krishnan, S., and O. Troan,
              "Prefix Exclude Option for DHCPv6-based Prefix
              Delegation", RFC 6603, May 2012.

13.2.  Informative References

   [RFC3971]  Arkko, J., Kempf, J., Zill, B., and P. Nikander, "SEcure
              Neighbor Discovery (SEND)", RFC 3971, March 2005.

   [RFC4302]  Kent, S., "IP Authentication Header", RFC 4302, December
              2005.

   [RFC5308]  Hopps, C., "Routing IPv6 with IS-IS", RFC 5308, October
              2008.

   [RFC5340]  Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF
              for IPv6", RFC 5340, July 2008.

   [RFC5969]  Townsley, W. and O. Troan, "IPv6 Rapid Deployment on IPv4
              Infrastructures (6rd) -- Protocol Specification", RFC
              5969, August 2010.

   [RFC6241]  Enns, R., Bjorklund, M., Schoenwaelder, J., and A.
              Bierman, "Network Configuration Protocol (NETCONF)", RFC
              6241, June 2011.

   [RFC7084]  Singh, H., Beebee, W., Donley, C., and B. Stark, "Basic
              Requirements for IPv6 Customer Edge Routers", RFC 7084,
              November 2013.

   [I-D.ietf-homenet-arch]
              Chown, T., Arkko, J., Brandt, A., Troan, O., and J. Weil,
              "IPv6 Home Networking Architecture Principles", draft-
              ietf-homenet-arch-11 (work in progress), October 2013.

   [I-D.ietf-homenet-hncp]
              Stenberg, M. and S. Barth, "Home Networking Control
              Protocol", draft-ietf-homenet-hncp-00 (work in progress),
              April 2014.

   [I-D.ietf-ospf-ospfv3-autoconfig]
              Lindem, A. and J. Arkko, "OSPFv3 Auto-Configuration",
              draft-ietf-ospf-ospfv3-autoconfig-06 (work in progress),
              February 2014.

   [I-D.ietf-6man-why64]
              Carpenter, B., Chown, T., Gont, F., Jiang, S., Petrescu,
              A., a
       candidate prefix.  If so, pick that prefix and A. Yourtchenko, "Analysis stop.

   6.  Choose a random prefix from the set of selected candidates.

   The complexity of this procedure is equivalent to the 64-bit Boundary complexity of
   iterating over available prefixes.  Such operation may be
   accomplished 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 linear time, e.g., by storing Advertised and Assigned
   Prefixes 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. binary trie.

6.  Implementation Capabilities and A. Williams, "Autoconfiguration Node Behavior

   Implementations 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 prefix assignment algorithm may vary from very
   basic to highly customisable, enabling different types of fully
   interoperable behaviors.  The three following behaviors are given as
   examples:

   Listener:   The node only acts upon assignments made by other nodes,
      i.e, it never creates new assignments nor adopt existing ones.
      Such behavior does not require the implementation of the
      considerations specified in Section 5 or Section 4.3.  The node
      never checks existing assignments validity, which makes this
      behavior particularly suited to lightweight devices which can rely
      on more capable neighbors to make assignments on directly
      connected Shared Links.

   Basic:   The node is made, capable of assigning new prefixes or adopting
      prefixes which do not conflict with any other existing assignment.
      Such behavior does not require the implementation of the
      considerations specified in Section 4.3.  It is suited to
      situations where there is no preference over which prefix should
      be selected amongst a set assigned to which Link, and there is no priority between
      different Links.

   Advanced:   The node is capable of
   prefixes so that prefix waste assigning new prefixes, adopting
      existing ones, making overriding assignments and destroying
      existing ones.  Such behavior requires the implementation of the
      considerations specified in Section 5 and Section 4.3.  It is minimized.  Then, a router may
   decide
      suited when the administrator desires some particular prefix to execute procedures intended be
      assigned on a given Link, or some Links to avoid prefix scarcity.
   Different approaches are possible. be assigned prefixes
      with a higher priority.

7.  Algorithm Parameters

   This section intends to document does not provide
   guidelines values for such procedures.  They are optional ADOPT_MAX_DELAY,
   BACKOFF_MAX_DELAY and RANDOM_SET_SIZE.  The algorithm ensures
   convergence and correctness for any chosen values, even when these
   are compatible
   with routers that only support basic requirements defined in this
   document.

A.1.  Prefix Wasts Avoidance

   Given a Delegated Prefix, different routers may try from node to assign
   prefixes of different lengths.  Particularly, node.  They MAY be adjusted depending on
   the context, providing a non-homenet
   downstream router may ask for tradeoff between convergence time, efficient
   addressing, low verbosity (less traffic is generated by the Flooding
   Mechanism), and low collision probability.

   ADOPT_MAX_DELAY (respectively BACKOFF_MAX_DELAY) represents the
   maximum backoff time a delegated prefix of significant size,
   as specified in Section 8.2.  Some other routers, like sensors, node may
   also require small prefixes.  When randomly selected, wait before adopting an assignment
   (respectively making a few /80s may
   easily prevent new assignment).  BACKOFF_MAX_DELAY MUST be
   greater than or equal to ADOPT_MAX_DELAY.  The greater
   ADOPT_MAX_DELAY and (BACKOFF_MAX_DELAY - ADOPT_MAX_DELAY), the assignment lower
   the collision probability and the verbosity, but the longer the
   convergence time.

   RANDOM_SET_SIZE represents the desired size of bigger prefixes.  Small prefixes
   should therefore be selected in neighboring areas.

   For instance, given the set a delegated random
   prefix 2001::/56 will be picked from.  The greater RANDOM_SET_SIZE, the better
   the convergence time and an assigned
   prefix 2001::/64, the best prefix choice in order to reduce prefix
   space waste lower the collision probability, but the
   worse the addressing-space usage efficiency.

   When the Flooding Mechanism does not provide a Flooding Delay, it is 2001:0:0:1::/64.  Other choices are then
   set to DEFAULT_FLOODING_DELAY.  As participating nodes do not need to
   agree on a common Flooding Delay value, this default value MAY be taken
   different from one node to another.  If the context in 2001:0:0:2::/63, 2001:0:0:4::/62, 2001:0:0:8::/61, etc...

   Creating an efficient prefix selection which the
   algorithm may is used does not suffer from renumbering, the value 0 MAY
   be challenging
   as used.  Otherwise it needs to fullfill somehow contradictory requirements:

   1.  The prefix MUST be chosen amongst available prefixes, which
       implies that other routers may interfere with depends on the process.

   2. Flooding Mechanism properties
   and the desired renumbering probability, and is therefore out of
   scope of this document.

8.  Security Considerations

   The prefix MUST be chosen randomly in a subset assignment algorithm functions on top of available
       prefixes.  When possible, two distinct
   mechanisms, the subset must be big enough Flooding Mechanism and the Node ID assignment
   mechanism.  In order to avoid
       collisions.

   3.  The prefix SHOULD be selected amongst prefixes that reduces operate securely:

      An attacker able to publish Advertised Prefixes through the
      flooding mechanism may perform the
       prefix space waste.

   4.  The prefix SHOULD be selected pseudo-randomly.

   The following algorithm offers attacks:

      *  Publish a satisfying tradeoff.  Given single overriding assignment for a whole Delegated
         Prefix and the desired prefix length:

   1.  Compute or for the minimal subset of available whole address space, thus preventing any node
         from assigning 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 to Links.

      *  Quickly publish and remove Advertised Prefixes, generating
         traffic at the set of prefixes Flooding Mechanism layer and causing multiple
         executions 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. prefix assignment algorithm in all
         participating nodes.

      *  Publish and remove Advertised Prefixes are picked in order to prevent the prefixes
         convergence of the execution.

      An attacker able to prevent other nodes from accessing a portion
      or the minimal subset whole set of
          available prefixes which lengths are the highest.

       *  When multiple subsets are possible, privelege lexicographicaly
          lowest prefixes.

       If RANDOM_SUBSET_SIZE equals 10, Advertised Prefixes may compromise 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,
      correctness of the 3 first /64s in 2001:0:0:8::/61}.

   3.  First try PSEUDO_RANDOM_TENTATIVE pseudo-random prefixes,
       computed execution.

      An attacker able to cause repetitive Node ID changes may induce
      traffic generation from the DP, with Flooding Mechanism and multiple
      executions of 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 assignment algorithm in the set computed at step 2 is chosen.  If no prefix is
       found, try next step.

   4.  Choose all participating
      nodes.

      An attacker able to publish Advertised Prefixes using a prefix randomly among prefixes in Node ID
      used by another node may prevent the subset computed at
       step 2.

   This algorithm, defined as a sequence correctness and convergence
      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 execution.

   Whenever the security of the Flooding Mechanism and Node ID
   assignment mechanism could not be ensured, the available prefixes.

   RANDOM_SUBSET_SIZE should provide sufficiently low collision
   probability.  A value convergence of 256 should the
   execution may be enough in most cases.
   PSEUDO_RANDOM_TENTATIVE is purely implementation dependent, but
   shouldn't prevented.  In environments where such attacks may
   be too high as performed, the probability execution 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 prefix assignment can't algorithm
   routine SHOULD be created, and if not forbidden by the
   router's configuration, rate limited, as specified in Section 4.2.

9.  IANA Considerations

   This document has no actions for IANA.

10.  Acknowledgments

   The authors would like to thank those who participated in the router MAY increase
   previous document's version development as well as the size of present one.
   In particular, the
   desired prefix.  For instance, if authors would like to thank Tim Chown, Fred Baker,
   Mark Townsley, Lorenzo Colitti, Ole Troan, Ray Bellis, Markus
   Stenberg, Wassim Haddad, Joel Halpern, Samita Chakrabarti, Michael
   Richardson, Anders Brandt, Erik Nordmark, Laurent Toutain, Ralph
   Droms, Acee Lindem and Steven Barth for interesting discussions and
   document review.

11.  References

11.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

11.2.  Informative References

   [RFC4291]  Hinden, R. and S. Deering, "IP Version 6 Addressing
              Architecture", RFC 4291, February 2006.

   [RFC3633]  Troan, O. and R. Droms, "IPv6 Prefix Options for Dynamic
              Host Configuration Protocol (DHCP) version 6", RFC 3633,
              December 2003.

Appendix A.  Static Configuration Example

   This section describes an available /64 can't be found, example of how custom configuration of the router
   prefix assignment algorithm may look for be implemented.

   The node configuration is specified as a /80.  Nevertheless, this implies using
   DHCPv6 instead finite set of SLAAC, rules.  A rule
   is defined as:

   o  A prefix to be used.

   o  A Link on which SHOULD be avoided.

A.3.  Foreseeing Prefixes Exaustion

   The previously proposed solution the prefix 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, assigned.

   o  An Assigned Prefix Priority (smallest possible Assigned Prefix
      Priority if A/64 is available, but
   there are the rule may not many override other available /64, Assigned Prefixes).

   o  A rule priority (0 if the router can try rule may not override existing
      Advertised Prefixes).

   In order to
   allocate A/80.  If ensure the allocation doesn't raise any collision, this
   procedure will prevent A/64 from being used by other hosts, hence
   creating a large set convergence of smaller available prefixes to be used.

   Such an allocation is considered dynamic.  The Authoritative bit the execution, the Assigned
   Prefix Priority MUST
   NOT be set and an increasing function (not necessarily
   strictly) of the configuration rule priority MUST be among values authorized (i.e. the greater is the
   configuration rule priority, the greater the Assigned Prefix Priority
   must be).

   Each Assigned Prefix is associated with a rule priority.  Assigned
   Prefixes which are created as
   dynamically chosen specified in Section 6.8.

   When different prefixes lengths 4.2 are being used, given a
   rule priority of 0.

   Whenever 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 configuration is changed or the DP, and 2001:0:0:0:1::/
   80 prefix assignment
   algorithm routine 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, run: For each Link/Delegated Prefix pair, look
   for the configuration rule with the highest configuration rule
   priority such that:

   o  The prefix specified in order to
   cut it the configuration rule is included in smaller prefixes, or to send an overriding assignment the
      considered Delegated Prefix.

   o  The Link specified 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 configuration rule is the considered as required by an authority.  The
   Authoritative bit MAY be set and
      Link.

   o  All the priority MUST Assigned Prefixes which would need to be among values
   authorized as destroyed in case
      a new Assigned Prefix is created from that configuration rule (as
      specified by an authority in Section 6.8.

   As 4.3) have an example, if a router can't find a /64 for a link that, with a
   high priority, must associated rule priority which
      is strictly lower than the one of the considered configuration
      rule.

   o  The assignment would be given a /64, it chooses a prefix assigned by
   some other router, to another link, valid when published with an Advertised
      Prefix Priority equal to the one specified in the configuration
      rule.

   If a lower priority, and
   creates rule is found, a new Chosen Assigned Prefix is created based on that
   rule in conformance with a higher priority. Section 4.3.  The other router
   will be forced to remove its own assignment, hence making the new
   assignment valid.

Appendix B.  Acknowledgments

   This document Assigned Prefix is
   associated with the continuation of Advertised Prefix Priority and the work being done rule priority
   specified in
   [I-D.arkko-homenet-prefix-assignment].  The authors would like to
   thank all the people considered configuration rule.

   Note that participated in the previous document's
   development as well as use of rule priorities ensures the present one.  In particular, convergence of 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].
   execution.

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