Internet Engineering Task Force Alain Durand
INTERNET-DRAFT SUN Microsystem
June 8, 2001 Christian Huitema
Expires December, 9, 2001 Microsoft
The H-Density ratio for address assignment efficiency
An update on the H ratio
<draft-durand-huitema-h-density-ratio-00.txt>
Status of this memo
This memo provides information to the Internet community. It does no specify an
Internet standard of any kind. This memo is in full conformance with all
provisions of Section 10 of RFC2026
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
Abstract
This document provide an update on the "H ratio" defined in RFC1715. It defines
a new ratio which the authors claim to be easier to understand.
1. Evaluating the efficiency of address allocation
A nave observer might assume that the number of addressable objects in an
addressing plan is a direct function of the size of the address. If this was
true, a telephone numbering plan based on 10 digits would be able to number 10
billion telephones, and the IPv4 32 bit addresses would be adequate for
numbering 4 billion computers (using the American English definition of a
billion, i.e. one thousand millions.) We all know that this is not correct: the
10 digit plan is stressed today, and it handles only a few hundred million
telephones in the USA; the Internet registries have started to implement
increasingly restrictive allocation policies when there where only a few tens of
million computers on the Internet.
Addressing plans are typically organized as a hierarchy: in telephony, the first
digits will designate a region, the next digits will designate an exchange, and
the last digit will designed a subscriber within this exchange; in computer
networks, the most significant bits will designate an address range allocated to
a network provider, the next bits will designate the network of an organization
served by that provider, and then the subnet to which the individual computers
are connected. At each level of the hierarchy, one has to provide some margins:
one has to allocate more digits to the region code than the current number of
regions would necessitate, and more bits in a subnet than strictly required by
the number of computers. The number of elements in any given level of the
hierarchy will change over time, due to grow and mobility. If the current
allocation is exceeded, one has to engage in renumbering, which is painful and
expensive. In short, trying to squeeze too many objects in a fixed size address
space increases the level of pain endured by operators and subscribers.
Back in 1993, when we were debating the revision of the Internet Protocol, we
wondered what the acceptable ratio of utilization was of a given addressing
plan. Coming out with such a ratio was useful to assess how many computers could
be connected to the Internet with the current 32 bit addresses, as well as to
decide the size of the next generation addresses. The second point is now
decided, with 128 bits addresses for IPv6, but the first question is still
relevant: knowing the capacity of the current address plan will help us predict
the date at which this capacity will be exceeded.
Participants in the IPNG debates initially measured the efficiency of address
allocation by simply dividing the number of allocated addresses by the size of
the address space. This is a simple measure, but it is largely dependent of the
size of the address space. Loss of efficiency at each level of a hierarchical
plan has a multiplicative effect; for example, 50% efficiency at each stage of a
three level hierarchy results in a global efficiency of 12.5%. If we want a
ôpain level indicatorö, we have to use a ratio that takes into account these
multiplicative effects.
The ôH-Ratioö defined in RFC 1715 proposed to measure the efficiency of address
allocation as the ratio of the base 10 logarithm of the number of allocated
addresses to the size of the addresses in bits. This provides an address size
independent ratio, but the definition of the H ratio results in values in the
range of 0.0 to 0.30103, with typical values ranging from 0.20 to 0.28.
Experience has shown that these numbers are difficult to explain to third
parties; it would be easier to say that "your address bits are used to 83% of
their H-Density", and then explain what the H-Density is, than to say "you are
hitting a H ratio of 0.25" and then explain what exactly the range is.
This memo introduces the Host Density ratio or ôHD-Ratioö, a proposed
replacement for the H-Ratio defined in RFC 1715. The HD values range from
0 to 1, and are generally expressed as percentage points; the authors believe
that this new formulation is easier to understand and more expressive than the
H-Ratio.
2. Definition of the HD ratio
When considering an addressing plan to allocate objects, the host density ratio
HD is defined as follow:
log(number of allocated objects)
HD = ------------------------------------------
log(maximum number of allocatable objects)
This ratio is defined for any number of allocated objects greater than 1 and
lower or equal to the maximum number of allocatable objects. The ratio is
usually presented as a percentage, e.g. 70%. It varies between 0 (0%), when
there is just one allocation, and 1 (100%), when there is one object allocated
to each available address. Note that for the calculation of the HD ratio, one
can use any base for the logaritm as long as it is the same for both the
numerator and the denominator.
3. Using the HD-ratio
3.1 HD-Ratio as an indicator of the pain level
In order to assess whether the H-Ratio was a good predictor of the ôpain levelö
caused by a specific efficiency, RFC1715 used several examples of networks that
had reached their capacity limit. These could be for example telephone networks
at the point when they decided to add digits to their numbering plans, or
computer networks at the point when their addressing capabilities were perceived
as stretched beyond practical limits. The idea behind these examples is that
network managers would delay renumbering or changing the network protocol until
it became just too painful; the ratio just before the change is thus a good
predictor of what can be achieved in practice. The examples were the following:
* Adding one digit to all French telephone numbers, moving from 8 digits to 9,
when the number of phones reached a threshold of 1.0 E+7.
log(1.0E+7)
HD(FrenchTelephone8digit) = ----------- = 0.8750 = 87.5%
log(1.0E+8)
log(1.0E+7)
HD(FrenchTelephone9digit) = ----------- = 0.7778 = 77.8%
log(1.0E+9)
* Expending the number of areas in the US telephone system, making it
effectively 10 digits long instead of ô9.2ö (the second digit of area
codes used to be limited to 0 or 1) for about 1.0 E+8 subscribers.
log(1.0E+8)
HD(USTelephone9.2digit) = ------------ = 0.8696 = 87.0 %
log(9.5E+9)
log(1.0E+8)
HD(USTelephone10digit) = ------------ = 0.8000 = 80.0 %
log(1E+10)
* The globally-connected physics/space science DECnet (Phase IV) stopped
growing at about 15K nodes (i.e. new nodes were hidden) in a 16 bit address
space.
log(15000)
HD(DecNET IV) = ---------- = 0.8670 = 86.7 %
log(2^16)
From those examples, we can note that these addressing systems reached their
limits for very close values of the HD-ratio. We can use the same examples to
confirm that the definition of the HD-ratio as a quotient of logarithms results
in better prediction than the direct quotient of allocated object over size of
the address space. In our three examples, the direct quotients were 10%, 3.2%
and 22.8%, three very different numbers that donÆt lead to any obvious
generalization. The examples suggest that value of the HD-ratio of the order of
85% and above correspond to a high pain level, at which operators are ready to
make drastic decisions.
We can also examine our examples and hypothesize that the operators who
renumbered they network tried to reach after the renumbering a pain level that
was easily supported. The HD ratio of the French or US network immediately after
renumbering was 78% and 80%, respectively. This suggests that values of 80% or
less corresponds to comfortable trade-offs between pain and efficiency.
3.2 Using the HD ratio to evaluate the capacity of addressing plans
Directly using the HD ratio makes it easy to evaluate the density of allocated
objects. Evaluating how well an addressing plan will scale requires the reverse
calculation. We have seen in section 3.1 that an HD-ratio lower than 80% is
manageable, and that HD ratios higher than 87% are hard to sustain. This should
enable us to compute the acceptable and ôpractical maximumö number of objects
that can be allocated given a specific address size, using the formula:
number allocatable of objects
= exp( HD x log(maximum number allocatable of objects))
= (maximum number allocatable of objects)^HD
The following table provides example values for a 9 digit telephone plan, a 10
digit telephone plan, and the 32 bit IPv4 Internet:
Very Practical
Reasonable Painful Painful Maximum
HD=80% HD=85% HD=86% HD=87%
---------------------------------------------------------
9 digits plan 16 M 45 M 55 M 68 M
10 digits plan 100 M 316 M 400 M 500 M
32 bits addresses 51 M 154 M 192 M 240 M
Note: 1M = 1E6
Indeed, the practical maximum depends on the level of pain that the users and
providers are willing to accept ¡ we may very well end up with more than 154M
allocated IPv4 addresses in the next years, if we are willing to accept the
pain.
3.3. Evolution of the pain level in the IPv4 Internet
The allocation of IPv4 addresses went through several phases that correspond to
growing levels of pains. This included the transfer of the registry functions
from IANA to the Internic in 1991, the definition of CIDR in 1992 and its
practical introduction in 1993, the generalization of variable length subnets in
the same period, the delegation of address allocation to regional registries
between 1992 and 1996, the arrival of NAT around 1996. Logically, we should
observe over the years an evolution of the HD ratio that reflects this growing
level of pain.
The following table shows the value of the HD ratio before and after the
allocation of new /8 prefixes to the registries. The date of allocation and the
number of /8 open for allocation is derived from the INTERNET PROTOCOL V4
ADDRESS SPACE maintained by the IANA [IANAV4]; the number of /8 includes all the
prefixes open for the allocation of global IPv4 addresses, excluding the 16
domains used for multicast (224/4), the 16 domains used for experiments (240/4),
the unspecified addresses (0/8), the local addresses (10/8) and the loop back
addresses (127/8). The number of hosts in the Internet is extrapolated from the
Internet Domain Name Surveys [DOMSRV] for values before 1997, and from
TelcordiaÆs Netsizer [NETSZR] for values after January 1997.
Allocation HD-Ratio HD-ratio
Date Hosts /8 (before) /8 (after)
Jan-94 2217000 97 68.89% 98 68.86%
Feb-94 2387414 98 69.21% 99 69.17%
Mar-94 2541337 99 69.47% 101 69.40%
Apr-94 2711751 101 69.71% 102 69.67%
May-94 2876669 102 69.95% 105 69.86%
Jun-94 3047083 105 70.13% 109 70.00%
Aug-94 3655772 109 70.86% 110 70.83%
Sep-94 4099543 110 71.36% 111 71.33%
Oct-94 4529000 111 71.80% 112 71.77%
Nov-94 4972772 112 72.21% 113 72.18%
Jan-95 5846000 113 72.94% 115 72.88%
Apr-95 7016497 115 73.73% 118 73.64%
May-95 7406663 118 73.89% 122 73.78%
Jun-95 7809834 122 74.03% 124 73.97%
Jul-95 8200000 124 74.20% 126 74.14%
Nov-95 12312478 126 76.04% 127 76.01%
Apr-96 15540500 127 77.09% 128 77.06%
Jun-96 16337187 128 77.30% 131 77.21%
Apr-97 20000000 131 78.15% 134 78.07%
Mar-98 32424000 134 80.31% 135 80.29%
Apr-98 33568300 135 80.45% 136 80.42%
Mar-99 50470600 136 82.31% 137 82.28%
Apr-99 53457700 137 82.55% 138 82.52%
Jul-99 59278500 138 83.00% 139 82.98%
Jun-00 82854000 139 84.53% 140 84.50%
Jul-00 85820100 140 84.66% 141 84.63%
Dec-00 99215800 141 85.31% 142 85.28%
Apr-01 119411000 142 86.14% 144 86.08%
May-01 122098000 144 86.18% 145 86.16%
log(number of hosts)
Note: HD = ------------------------
log(number of /8 x 2^24)
The table lists the number of prefixes and the corresponding HD-ratio before and
after allocation. We notice that the HD ratio grows continuously, which reflects
continuous efficiency gains; it is also clearly the picture of a growing pain
level. We have already reached a level of 86%, which according to our analysis
is define as very painful level.
3.4. Available capacity with IPv6
Applying the HD ratio to a 128 bit address space predicts that we could
comfortably number 6.6 E+30 addresses with an HD-ratio of 80%. This is quite
satisfying, but we should conduct a more specific analysis that takes into
account the structure of IPv6 global addresses. The ôfirst waveö of
specifications only define the structure for the 001 binary /3 prefix.
The addresses are composed in practice of a 64 bit subnet prefix and
a 64 bit host identifier; we expect ôsitesö to be identified by a 48 bit prefix.
As the network prefix for those global unicast addresses starts by the 3 bits
ô001ö, there are in practice 61 bits available to number the subnets and
45 to number the sites. This leads to the following numbers:
Very Practical
Reasonable Painful Painful Maximum
HD=80% HD=85% HD=86% HD=87%
-------------------------------------------------------
Sites (45 bits) 70 B 330 B 450 B 610 B
Subnets (61 bits) 490 T 4 Q 6 Q 10 Q
Note: 1M = 1E6, 1B= 1E9, 1T=1E12, 1Q=1E15
The numbers clearly show that even when we take into account the constraints
imposed to the IPv6 numbering plan, there is plenty of capacity. In practice, we
could allocate 10 site identifiers to each human person, and still have a
reasonably low level of pain!
5. Security considerations
Security issues are not discussed in this memo.
6. IANA Considerations
This memo does not request any IANA action.
7. Author addresses
Alain Durand
SUN Microsystems, Inc
901 San Antonio Road MPK17-202
Palo Alto, CA 94303-4900
USA
Mail: Alain.Durand@sun.com
Christian Huitema
Microsoft Corporation
One Microsoft Way Redmond, WA 98052-6399
USA
Mail: huitema@microsoft.com
8. Acknowledgment
The authors would like to thank Jean Daniau for his kind support
during the elaboration of the HD formula.
9. References
[RFC1715] C. Huitema, ôThe H Ratio for Address Assignment Efficiency.ö RFC 1715,
November 1994.
[IANAV4] INTERNET PROTOCOL V4 ADDRESS SPACE, maintained by the IANA,
http://www.iana.org/assignments/ipv4-address-space
[DMNSRV] Internet Domain Survey, Internet Software Consortium,
http://www.isc.org/ds/
[NETSZR] Netsizer, Telcordia Technologies, http://www.netsizer.com/