[sig-policy] IPv6 address space management - informational

  • To: sig-policy at apnic dot net
  • Subject: [sig-policy] IPv6 address space management - informational
  • From: APNIC Secretariat <secretariat at apnic dot net>
  • Date: Mon, 23 Aug 2004 17:19:16 +1000
  • Cc:
  • List-archive: <http://www.apnic.net/mailing-lists/sig-policy>
  • List-help: <mailto:sig-policy-request@lists.apnic.net?subject=help>
  • List-id: APNIC SIG on resource management policy <sig-policy.lists.apnic.net>
  • List-post: <mailto:sig-policy@lists.apnic.net>
  • List-subscribe: <http://mailman.apnic.net/mailman/listinfo/sig-policy>,<mailto:sig-policy-request@lists.apnic.net?subject=subscribe>
  • List-unsubscribe: <http://mailman.apnic.net/mailman/listinfo/sig-policy>,<mailto:sig-policy-request@lists.apnic.net?subject=unsubscribe>

    • Dear Colleagues,

      The following informational paper "IPv6 address space management" is intended to augment the policy proposal [prop-005-v002] "Internet Assigned Numbers Authority (IANA) policy for the allocation of IPv6 blocks to Regional Internet Registries".

      Discussion and comments on both are most welcome.

      Kind regards,



      APNIC Secretariat


      ______________________________________________________________________

      IPv6 address space management
      ______________________________________________________________________

      Written by: Geoff Huston, APNIC Secretariat
      Version: 1.0
      Date: 19 August 2004




      Abstract
      --------

      This document provides a description of the management process that is
      proposed for use by the Regional Internet Registries (RIRs) in managing
      global unicast IPv6 address resources. The document describes the
      proposed process of address allocation that is undertaken by the
      Internet Assigned Numbers Authority (IANA) to an RIR, as well as the
      RIRs' proposed address management process, whereby address allocations
      are made from the managed address block according to a "sparse
      allocation" algorithm. This sparse allocation management process is
      designed to maximise aggregation of address space within the confines of
      each allocated block, ensuring that most ISPs and Local Internet
      Registries (LIRs) retain a single aggregate address prefix as they grow.
      This paper is intended to augment previous work, in particular the
      proposal "Internet Assigned Numbers Authority (IANA) policy for
      allocation of IPv6 blocks to Regional Internet Registries" [1].


      1. Overview
      --------------

      Under the system of management of global IP address space, RIRs are
      responsible for the allocation of address space to organisations within
      their respective geographic regions.

      RIRs receive address space periodically from the IANA, and then manage
      that address space as a local pool from which subsequent allocations are
      made to organisations within their regions. RIRs individually use
      various allocation techniques within their respective pools of address
      space (including sparse allocation techniques), in an attempt to
      maximise the likelihood that the initial and subsequent allocations to
      ISPs are able to be aggregated into a single unit.

      Under this system, aggregation of allocated address space is limited by
      several factors. In the context of management of IPv4 addresses these
      factors include the requirement for RIRs to utilise their existing pool
      of addresses to a level of 80% prior to requesting more address space
      from IANA, as well as the relatively small size of the address pools
      held by RIRs at any one time. Over a period of several years, a single
      large ISP may receive a number of discontiguous allocations from its
      RIR.

      The management system for IPv6 described here avoids these problems of
      undue levels of fragmentation of the IPv6 address space through the
      allocation of address blocks from the IANA to the RIRs that take into
      account both the RIRs' sparse allocation practice and the desire to
      undertake ISP and LIR allocations from an address block that can
      preserve aggregation windows per ISP or LIR for periods of between one
      and two years per allocated entity. The sparse allocation management
      scheme is intended to maximise the room for future expansion of each
      allocation as a single aggregateable block.

      The existing IPv6 address allocations use a threshold metric of address
      utilisation efficiency termed the "HD ratio" [2]. This metric takes into
      account a commonly observed aspect of address deployment that the
      efficiency of a deployment drops as the size of the deployment
      increases.

      It is proposed that IANA allocates address blocks to the RIRs using an
      allocation unit of a /12. Further allocations will be made from IANA to
      the RIRs such that the RIR will have a minimum pool of allocateable
      addresses that allow at least a further 36 months of allocations at the
      average allocation rate of the previous 12 months. The RIR will manage
      each allocated address block according to methods of its own choosing,
      including but not limited to the sparse allocation mechanisms described
      in this document.



      2. IP address allocation framework
      -------------------------------------

      The framework of management of IPv6 address space is described in a
      number of source documents.

      2.1 Global unicast address space
      ----------------------------------

      The range of addresses managed within this framework is the address pool
      termed the "global unicast" IPv6 address pool. This pool is defined in
      RFC 3513 [3] as the address block with the prefix 2000::/3:

      "The rest of the global unicast address space (approximately
      85% of the IPv6 address space) is reserved for future
      definition and use, and is not to be assigned by IANA at
      this time."

      (RFC 3513)

      2.2 IANA allocations to RIRs
      ------------------------------

      Allocations of global unicast address space to RIRs are described by RFC
      2450 [4]. This document uses the terminology of Format Prefix (FP), Top
      Level Aggregation Identifier (TLA), and Sub Top Level Aggregation
      Identifier (Sub-TLA).

      The structure is these fields is defined in RFC 2450 as follows:

      | 3 | 13 | 13 | 19 |
      +----+----------+---------+---------------+
      | FP | TLA | Sub-TLA | NLA |
      | | ID | | ID |
      +----+----------+---------+---------------+

      The IANA-to-RIR allocation framework is as follows:

      "The IANA will assign small blocks (e.g., few hundred) of
      Sub-TLA ID's to registries. The registries will assign the
      Sub-TLA ID's to organizations meeting the requirements
      specified in Section 5.2. When the registries have assigned
      all of their Sub-TLA ID's they can request that the IANA
      give them another block. The blocks do not have to be
      contiguous."

      (RFC 2450, section 5.1)

      A Sub-TLA in this context is a /29 address block, and "a few hundred"
      Sub-TLAs is either 256 or 512 Sub-TLAs if using a bit-aligned address
      management regime. This document appears to propose IANA assignments
      using a /21 prefix (256 Sub-TLAs) or a /20 prefix (512 Sub-TLAs).

      The initial IANA allocations have been documented in RFC 2928 [5]. These
      initial assignments were smaller than that proposed, and the document
      notes that:

      "The initial Sub-TLA ID assignments to IP address registries
      are in blocks of 64 Sub-TLA IDs."

      (RFC2928)

      These initial allocations were in units of /23 address blocks. The IANA
      IPv6 Sub-TLA assignment registry [6] lists these allocations, and also
      all subsequent allocations, with a common allocation unit of a /23 from
      the sub-TLA assignment registry.

      It is noted that the terminology of TLAs and Sub-TLAs has been
      deprecated within the context of the IPv6 addressing architecture
      specifications [3], but the practice of IANA IPv6 allocations to RIRs
      using a /23 address block remains in place.

      2.3 IPv6 address allocation and assignment policy
      ---------------------------------------------------

      IPv6 allocations from RIRs to LIRs and ISPs is described within the
      framework of a coordinated policy across the RIRs [7]. The goals of the
      address management function include an outcome of address aggregation:

      "RIRs should apply practices that maximize the potential
      for subsequent allocations to be made contiguous with past
      allocations currently held."

      (IPv6 address allocation and assignment policy, Section 3.4)

      And in reference to potential conflicts of goals:

      "In IPv6 address policy, the goal of aggregation is
      considered to be the most important."

      (IPv6 address allocation and assignment policy, Section 3.8)

      The document references the minimum size of IPv6 allocations as a /32,
      and proposes that the determination of the allocation will be based on
      the application of the HD ratio metric to the applicant? proposed IPv6
      deployment, with a threshold HD ratio value of 0.8 being specified as a
      means of determining an initial allocation size. However it is envisaged
      within this policy framework that established ISPs would be eligible for
      potentially much larger initial allocations.

      "Where an existing IPv4 service provider requests IPv6 space
      for eventual transition of existing services to IPv6, the
      number of present IPv4 customers may be used to justify a
      larger request than would be justified if based solely on
      the IPv6 infrastructure."

      (IPv6 address allocation and assignment policy, Section 4.4)

      The RIR allocation to LIRs and ISPs uses a doubling function for
      subsequent allocations, namely:

      "When an organization has achieved an acceptable utilization
      for its allocated address space, it is immediately eligible
      to obtain an additional allocation that results in a
      doubling of the address space allocated to it. Where
      possible, the allocation will be made from an adjacent
      address block, meaning that its existing allocation is
      extended by one bit to the left."

      (IPv6 address allocation and assignment policy, Section 5.2.3)



      3. Sparse allocation address pool management
      -----------------------------------------------

      Allocations from the RIRs' IPv6 managed address pools may be determined
      according to a sparse allocation (or "binary-chop") algorithm, designed
      to maximise aggregation of address blocks allocated. In order for this
      method to produce effective results in the long-term, the source address
      block from which allocations are made should be as large as reasonably
      possible.

      3.1 Sparse allocation algorithm
      ---------------------------------

      Under the sparse allocation system, the start addresses for successive
      allocations are generated according to a binary chop algorithm, as
      illustrated below.

      For example, within a 6-bit address space, the first 8 start addresses
      would be as follows:


      Seq# Address Decimal
      ---- ------- -------
      1 000000 00
      2 100000 32
      3 010000 16
      4 110000 38
      5 001000 08
      6 101000 40
      7 011000 24
      8 111000 56


      The following illustration shows this 6-bit address space (comprising 64
      locations), and the location of the first 16 allocations to be made
      (according to their sequence number), according to the above list.


      |-------|-------|-------|-------|-------|-------|-------|-------|
      1 | | | 2 | | |
      | 3 | | 4 |
      5 7 6 8

      The effect of the sparse allocation algorithm is to successively
      subdivide each remaining block of unallocated address space into 2 equal
      parts, the first being left to accommodate growth of an existing
      allocation, and the second being made as a new allocation.

      As more allocations are made from the address block the free space will
      become progressively fragmented, and the maximal size of the free block
      pool will decrease, as the progressive operation of this algorithm
      ensures that the size of the largest free block is at most 1 bit longer
      than the smallest. This implies that a large address pool can become
      excessively fragmented in response to a sustained sequence of minimal
      address allocation requests, leading to an inability to meet a large
      allocation request, or an inability to meet a requirement to undertake
      an additional allocation in an adjacent address block.

      3.2 Avoiding fragmentation
      ----------------------------

      Depending on the rate of allocation, and the rate of growth of
      individual allocations, the avoidance of fragmentation will need to be
      addressed eventually. A technique is proposed here that attempts to
      mitigate the extent to which address pool fragmentation causes
      fragmentary (non-aggregateable) allocations.

      The information used in this approach is the growth rate of each
      allocation. The modified selection algorithm is to perform a binary chop
      allocation such that the allocation maximises the time before the first
      "meeting", where an allocation immediately adjoins the next allocation
      in sequence. Growth rates are derived from reallocation frequency, where
      reallocations have been performed, and where no growth rate information
      is available (in the case of initial allocations) a 100% growth rate per
      2 years is assumed.

      For each allocation address block a growth rate is calculated. The
      associated aggregate allocation lifetime for the block can be calculated
      by dividing the remaining adjacent unallocated space by the growth rate.
      The selection aggregate allocation lifetime can be calculated by
      performing a binary chop on the unallocated space and dividing the
      remaining allocation space by the growth rate.

      To perform an allocation selection each unallocated space is tested by
      performing a binary chop and calculating the selection aggregate
      allocation lifetime on the existing allocated block, and on the created
      initial allocation block. The minimum of these two time values is the
      lifetime for that particular selection position. The selection position
      that offers the maximal lifetime is the one used for this allocation.

      A statement of the rate-controlled sparse allocation algorithm is as
      follows:

      For each allocation A[i] the corresponding expansion slot, X[i],
      is subdivided according the to the binary chop, resulting in a new
      expansion slot X'[i] and an initial allocation window W[i].

      If W[i] is less than the required initial allocation size, A[x]
      then the associated slot lifetime, P[i], is assigned a value of 0.

      Otherwise the growth rate of A[i] , R[i], is used. The lifetime
      for A[i] is calculated as X'[i] / R[i].

      The rate of the new allocation, R[x], is calculated as A[x]/year.
      The lifetime of using W[i] for this new allocation, T[x] is
      calculated as (W[i] ?A[x]) / R[x].

      The lifetime associated with selection of slot i for this new
      allocation, P[i], is the minimum of T[i] and T[x].

      The selected slot is the value of i that maximises the value of
      P[i] over all i.

      In order to ensure that sufficient space is held in reserve for larger
      allocations the address pool may be seeded with a number of large
      allocation reservations, useable only for allocations of a certain
      minimum size.

      The outcomes of this algorithm is that smaller allocations tend to
      cluster together, while larger initial allocations tend to have their
      expansion window held intact for longer periods. This, in turn,
      preserves the ability of the address pool to service expansion windows
      in a more effective manner than a simple binary chop algorithm.



      4. IANA allocation size
      --------------------------

      The requirements relating to the size of the address block allocated by
      IANA to a RIR include that it should be sufficient for the RIR to
      service all forms of allocations, and make reasonable allowance for
      additional allocations that preserve aggregation properties. The
      anticipated timeframe of utility for each allocated block is 36 months,
      using the average assignment rate of the previous 12 months.

      A proposed IANA allocation size of a /12 is reasoned using 2 distinct
      comparisons with the current IPv4 allocation system. The first
      comparison considers the requirement for address space from ISPs and
      LIRs (namely the "demand side"), while the second considers the
      allowable allocations which may be made by IANA from the total available
      space (namely the "supply side").

      4.1 ISP address space requirements the demand side
      ------------------------------------------------------

      The current IANA IPv6 allocation unit of /23 is the equivalent of
      33,554,432 end customer /48 assignments, while the current IPv4
      allocation unit of /8 corresponds to 16,777,216 end customer assignments
      (assuming an end customer assignment unit of /32).

      The consumption rates of these address blocks differ greatly between
      IPv4 and IPv6. IPv4 address management policies assume a constant
      address utilisation rate of 80% as a threshold for further allocations.
      An IPv4 deployment encompassing some 800,000 end customer /32
      assignments, for example, would therefore utilise a /12 allocation, or
      1/16 of the IANA IPV4 allocation unit. The same ISP could request an
      allocation of IPv6 address space based on a deployment of IPv4 that
      entails some 800,000 customer assignments. The HD ratio applied to this
      scenario produces the outcome that the allocation size to the ISP is a
      /23, which is equal the entire IANA allocation to the RIR. In order to
      allow aggregation of a subsequent allocation, the allocating RIR,
      according to this policy would allow for the possibility of a doubling
      of this assignment, so that the RIR would normally reserve the adjacent
      /23 address block in addition to the initial /23.

      In order for the RIR to be able to service the same profile of requests
      that it services from the /8 IPv4 IANA allocation, the equivalent IPv6
      allocation needs to be significantly larger than a /23. The equivalent
      of a /8 allocation in IPv4 using a 80% address utilisation efficiency is
      a /18 allocation in IPv6, using an HD ratio value of 0.8.

      4.2 IANA address space availability ?the supply side
      -----------------------------------------------------

      The current IANA IPv4 allocation to the RIRs is 1/256 of the entire IPv4
      address space, or 1/220 of the IPv4 Global Unicast space. An equivalent
      IPv6 allocation from the currently assigned Global Unicast space is a
      /11 address block.

      The objectives here are to set an allocation size that allows the RIR to
      service allocation requests from the IANA-allocated address blocks
      within the allocation policy framework, allowing each LIR and ISP the
      potential for further allocations within an encompassing aggregate
      address block; and to be able to service such requests without constant
      referral to IANA for further allocations.

      The IPv6 framework is proposed to set an allocation size equivalent to
      at least 36 months expected utilisation, based upon the previous 12
      months RIR allocation activity. The basis for this proposal is to allow
      ISPs and LIRs to achieve very high levels of aggregation within the
      address space, effectively limiting the long term fragmentation-induced
      overheads that would otherwise be placed on the IPv6 inter-domain
      routing system.

      It is notable that the current IPv4 allocation size of /8 corresponds to
      an administrative boundary for delegation of "reverse" DNS zones under
      the in-addr.arpa tree. This allows entire zones to be delegated by the
      IANA to each RIR, without the need for sharing of zones between RIRs.
      This administrative factor should also be considered in determining the
      IPv6 allocation size.

      4.3 Simulation of IPv6 allocations
      ----------------------------------

      Simulation of the operation of an RIR IPv6 registry has been undertaken
      using historical IPv4 allocation data as the seed data. The simulation
      has assumed that the underlying network metrics for IPv4 allocations
      have been based on an 80% uniform host density metric. This has been
      translated to a derived customer count, that, in turn, has been used to
      seed an HD ratio-based allocation with each IPv6 customer receiving a
      /48 and the minimum IPv6 allocation size from the RIRs being a /32. The
      simulation has assumed that in the steady state some 75% of allocations
      are additional address allocations to existing ISPs and LIRs, and that
      the average lifespan for each allocation is 1 year, with a randomised
      range from 6 months to 2 years and 6 months.

      Using IPv4 delegation data published by ARIN, and the above simulation
      conditions a /12 IP address pool managed using rate managed sparse
      allocation over a 36 month period will have 7,269 transactions, with
      3,571 ISPs and LIRS. A /12 IPv6 address block will be 48% allocated,
      with only 135 allocations failing to be allocated from ISP's aggregated
      assignment windows. The average assignment is a /25.5 address block and
      the largest single allocation space available at the end of the
      simulation is a /23. All allocations were serviced from the block, and
      there were no failures to find space.

      A comparable simulation using the RIPE NCC delegation data indicates a
      similar picture, with 4,273 transactions to 2,023 ISPs and LIRS. The
      block was filled to 51% and only 144 allocations failed to be allocated
      from the ISP aggregate allocation window. The average assignment is a
      /24.7 and the largest remaining single window of a /23.

      The simulations indicate that the rate-managed sparse allocation
      mechanism can provide effective aggregation of address blocks over
      extended periods, and, under the current framework of HD ratio-based
      address allocations, a /12 is the minimum address block size that can
      provide an RIR with effectively aggregated allocation outcomes over a
      period of a 36 month operational window.

      4.4 Conclusion
      --------------

      In considering the spectrum of size of current IPv4 network deployments,
      and the requirement to allow reallocations within the same aggregate
      window, the minimum IANA IPv6 allocation size should be in a range of
      between a /10 and a /18. A /10 divides the current IPv6 global unicast
      space into 128 allocation units (or the entire IPv6 space into 1024
      allocation units), while a /18 creates 32,768 such allocation units. The
      midpoint is a /13 or /14, dividing the current IPv6 global unicast
      address space into 1024 or 2048 allocation units.

      An IANA allocation unit of a /13 allows an RIR to service requests that
      include a small number of allocations for large ISPs, as large ISP would
      encompass some 10**7 customers, equating to an initial allocation of a
      /18 with an associated initial expansion window of a further 2 bit
      positions, or a /16. A /13 allocation would allow each RIR, if it
      chooses, to operate a sparse allocation address management system that
      would allow significant capability to ensure aggregateability of
      allocated address blocks. However, using IPv4 allocation data and an
      allocation simulation, it is evident that a /13 would not be adequate
      for 36 months of RIR operation. If effective aggregation is required
      over a 36 month window it is appropriate to propose use of a /12 as the
      IANA allocation unit.

      The issue of administrative management of reverse DNS zones should also
      be considered, particularly considering the importance of stability of
      these zones at points close to the root.

      It is proposed that the IANA allocation unit to RIRs should be equal to
      a /12, which represents the operational of a sparse allocation registry
      with aggregated outcomes over a 36 month window, as well as representing
      the closest administrative boundary for reverse DNS delegation.



      5. IPv6 address space management process
      -------------------------------------------

      It is proposed that:

      - IANA shall allocate address blocks to the RIRs using an
      allocation unit of a /12 address block. Further allocations will
      be made from IANA to the RIRs such that the RIR will have a
      minimum pool of allocateable addresses that encompass at least a
      further 36 months of allocations at the average allocation rate
      of the previous 12 months without compromising the ability to
      service allocation extension requests within aggregateable
      blocks according to the sparse allocation procedure.

      - The RIR may choose to manage each allocated address block using
      sparse allocation mechanisms described in this document. If so,
      each allocation would be performed in a manner such that
      allocation selection preserves the longevity of the usefulness
      of the address block with respect to both servicing initial
      allocations and servicing allocation extensions within
      aggregation block boundaries by using a rate-governed window
      selection algorithm.



      References
      ----------

      [1] [prop-v005-v002] Internet Assigned Numbers Authority (IANA) policy
      for allocation of IPv6 blocks to Regional Internet Registries
      http://www.apnic.net/mailing-lists/sig-policy/archive/2004/08/
      msg00003.html

      [2] RFC 3914, The Host-Density Ratio for Address Assignment Efficiency:
      An update on the H ratio

      [3] RFC 3513, Internet Protocol Version 6 (IPv6) Addressing Architecture

      [4] RFC 2450, Proposed TLA and NLA Assignment Rules

      [5] RFC 2928, Initial IPv6 Sub-TLA Assignments

      [6] IANA IPv6 Top Level Aggregation Identifier Assignments
      http://www.iana.org/assignments/ipv6-tla-assignments

      [7] IPv6 Address Allocation and Assignment Policy
      http://www.iana.org/ipaddress/ipv6-allocation-policy-26jun02