Orbit

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