______________________________________________________________________

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>