Internet Engineering Task Force Alain Durand
INTERNET-DRAFT SUN Microsystem
June 12, 2001 Christian Huitema
Expires December, 11, 2001 Microsoft
The H-Density ratio for address assignment efficiency
An update on the H ratio
<draft-durand-huitema-h-density-ratio-01.txt>
Status of this memo
This memo provides information to the Internet community. It
does not specify an Internet standard of any kind. This memo
is in full conformance with all provisions of Section 10 of
RFC2026
Internet-Drafts are working documents of the Internet
Engineering Task Force (IETF), its areas, and its working
groups. Note that other groups may also distribute working
documents as Internet-Drafts.
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."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/1id-abstracts.html
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 naive 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.
The HD ratio can, in most cases, be derived from the H ratio
by the formula:
H
HD = --------
log10(2)
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/
10. Full Copyright Statement
"Copyright (C) The Internet Society (2001). All Rights
Reserved.
This document and translations of it may be copied and
furnished to others, and derivative works that comment on or
otherwise explain it or assist in its implementation may be
prepared, copied, published and distributed, in whole or in
part, without restriction of any kind, provided that the above
copyright notice and this paragraph are included on all such
copies and derivative works. However, this document itself
may not be modified in any way, such as by removing the
copyright notice or references to the Internet Society or
other Internet organizations, except as needed for the purpose
of developing Internet standards in which case the procedures
for copyrights defined in the Internet Standards process must
be followed, or as required to translate it into languages
other than English.
The limited permissions granted above are perpetual and will
not be revoked by the Internet Society or its successors or
assigns.
This document and the information contained herein is provided
on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE
USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR
ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A
PARTICULAR PURPOSE.