The H-Density Ratio for Address Assignment Efficiency An Update on the H ratio
A single percentage that says how full an address space is, and how soon the operator will have to renumber
Durand, A. and C. Huitema, "The H-Density Ratio for Address Assignment Efficiency An Update on the H ratio", RFC 3194, DOI 10.17487/RFC3194, November 2001, <https://www.rfc-editor.org/info/rfc3194>.
@misc{rfc3194,
series = {Request for Comments},
number = 3194,
howpublished = {RFC 3194},
publisher = {RFC Editor},
doi = {10.17487/RFC3194},
url = {https://www.rfc-editor.org/info/rfc3194},
author = {A. Durand and C. Huitema},
title = {{The H-Density Ratio for Address Assignment Efficiency An Update on the H ratio}},
pagetotal = 7,
year = 2001,
month = nov,
} RFC text
Contents
Network Working Group A. Durand
Request for Comments: 3194 SUN Microsystems
Updates: 1715 C. Huitema
Category: Informational Microsoft
November 2001
The Host-Density Ratio for Address Assignment Efficiency:
An update on the H ratio
Status of this Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2001). All Rights Reserved.
Abstract
This document provides an update on the "H ratio" defined in RFC
1715. It defines a new ratio which the authors claim is 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 linear function of the size of the
address. If this were 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 North America; the Internet registries have
started to implement increasingly restrictive allocation policies
when there were 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 digits will designate 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 growth 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 into a hierarchical 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 on 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 overall 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 address 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 others; 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 allocatable objects greater
than 1 and any number of allocated objects greater or equal than 1
and less than or equal 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
logarithm 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 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)
* Expanding the number of areas in the US telephone system, making
the phone number 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 objects 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 an HD-ratio value on 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 their networks 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.
4. 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 = 1,000,000
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.
5. Security considerations
This document has no security implications.
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
EMail: Alain.Durand@sun.com
Christian Huitema
Microsoft Corporation
One Microsoft Way Redmond, WA 98052-6399
USA
EMail: 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] Huitema, C., "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.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
ISO Plain Language
On this page
§1Why Address Efficiency Needs a Measure
A naive observer might assume that the number of addressable objects in an addressing plan is a linear function of the size of the address. If that were true, a telephone numbering plan based on 10 digits could number 10 billion telephones, and the IPv4 32-bit addresses would be adequate for numbering 4 billion computers. It is not true: the 10-digit plan is stressed today and handles only a few hundred million telephones in North America, and the Internet registries started implementing increasingly restrictive allocation policies when there were only a few tens of million computers on the Internet.
Addressing plans are organised as a hierarchy. In telephony the first digits designate a region, the next digits an exchange, and the last digits a subscriber within that exchange. In computer networks the most significant bits designate an address range allocated to a network provider, the next bits the network of an organisation served by that provider, and then the subnet the individual computers are connected to. Each level needs some margin, because the number of elements at that level changes over time through growth and mobility. If the current allocation is exceeded, renumbering follows, which is painful and expensive. Squeezing too many objects into a hierarchical address space increases the pain.
The IPNG debates of 1993 asked what ratio of utilisation was acceptable, because such a ratio says how many computers could be connected and helps size the next generation of addresses. The second question has been answered, with 128-bit addresses for IPv6, but the first is still relevant: knowing the capacity of the current plan helps predict the date when that capacity will be exceeded. The earliest attempt at a ratio divided the number of allocated addresses by the size of the address space. That measure depends heavily on the size of the space, and it misses the fact that the loss of efficiency at each level of a hierarchy has a multiplicative effect: 50% efficiency at each stage of a three-level hierarchy results in an overall efficiency of 12.5%. A pain indicator therefore needs a ratio that accounts for those multiplicative effects. The H-Ratio defined in RFC 1715 did this, as the base 10 logarithm of the number of allocated addresses divided by the size of the address in bits. It is independent of address size, but its values run only from 0.0 to 0.30103, typically 0.20 to 0.28, and experience has shown that those numbers are difficult to explain to other people.
Address space is wasted at every level of its hierarchy, and the losses multiply: three levels at 50% each leave only 12.5% usable. A useful measure has to account for that, and the older H-Ratio did but produced numbers nobody could explain. This memo replaces it with a percentage.
§2The HD-Ratio Formula
When considering an addressing plan that allocates objects, the host density ratio HD is defined as the logarithm of the number of allocated objects divided by the logarithm of the maximum number of allocatable objects. The ratio is defined for any maximum number of allocatable objects greater than 1, and any number of allocated objects greater than or equal to 1 and less than or equal to that maximum.
The ratio is usually presented as a percentage, for example 70%. It varies between 0, when there is just one allocation, and 1, when there is one object allocated to each available address. Any base can be used for the logarithm, as long as the same base is used for the numerator and the denominator. In most cases the HD-ratio can be derived from the H ratio by the formula HD = H divided by log10(2).
Divide the logarithm of how many objects are allocated by the logarithm of how many could be. The result is a number between 0 and 1, which is easier to read as a percentage. It can also be worked out from the older H ratio.
§3Reading the HD-Ratio as a Pain Level
To test whether the ratio predicts the pain caused by a given efficiency, the earlier memo used several examples of networks that had reached their capacity limit. These were telephone networks at the point where they decided to add a digit to their numbering plan, and computer networks at the point where their addressing capability was perceived as stretched beyond practical limits. The reasoning was that network managers delay renumbering or changing the network protocol until it becomes too painful, so the ratio just before the change is a good predictor of what can be achieved in practice.
The first example was the French telephone network, which added one digit to all numbers, moving from 8 digits to 9, when the number of phones reached a threshold of 1.0E+7. That is an HD-ratio of 87.5% before the change and 77.8% after it. The second was the US telephone system, which expanded the number of areas, making the phone number effectively 10 digits long instead of 9.2, for about 1.0E+8 subscribers: 87.0% before the change and 80.0% after it. The third was DECnet Phase IV, the globally connected physics and space science network, which stopped growing at about 15K nodes, with new nodes hidden, in a 16-bit address space: 86.7%.
These addressing systems reached their limits at very close values of the HD-ratio. In the same three examples the direct quotients were 10%, 3.2% and 22.8%, three very different numbers that lead to no obvious generalisation, while the HD-ratio puts all three close together. The examples suggest that an HD-ratio value on the order of 85% and above corresponds to a high pain level, at which point operators are ready to make drastic decisions. Looking at the same examples the other way, the operators who renumbered tried to reach a pain level that was easily supported afterwards: the HD-ratio of the French and US networks immediately after renumbering was 78% and 80% respectively, which suggests that values of 80% or less correspond to comfortable trade-offs between pain and efficiency.
The memo checks the measure against three networks that changed when they could bear it no longer. All three were between 86.7% and 87.5% full on the new measure, while the old measure gave them three unrelated answers. A reading of 85% or more means operators are close to making a drastic change.
| Case | Objects allocated | HD-ratio |
|---|---|---|
| French telephone plan, 8 digits, before adding a digit | 1.0E+7 phones | 87.5% |
| French telephone plan, 9 digits, after adding a digit | 1.0E+7 phones | 77.8% |
| US telephone plan, 9.2 digits, before expanding areas | 1.0E+8 subscribers | 87.0% |
| US telephone plan, 10 digits, after expanding areas | 1.0E+8 subscribers | 80.0% |
| DECnet Phase IV, 16-bit address space | 15000 nodes | 86.7% |
§4How Many Objects an Address Plan Can Hold
Using the HD-ratio directly makes it easy to evaluate the density of allocated objects. Evaluating how well an addressing plan will scale requires the reverse calculation. Because an HD-ratio lower than 80% is manageable and ratios higher than 87% are hard to sustain, the acceptable and practical maximum number of objects that can be allocated for a given address size can be computed as the maximum number of allocatable objects raised to the power of the HD-ratio.
The memo gives example values for a 9-digit telephone plan, a 10-digit telephone plan and the 32-bit IPv4 Internet. For a 9-digit plan the numbers run from 16M at 80% to 68M at 87%. For a 10-digit plan they run from 100M to 500M. For 32-bit addresses they run from 51M at 80%, through 154M at 85% and 192M at 86%, to 240M as the practical maximum at 87%. One M is 1,000,000. The practical maximum depends on the level of pain that users and providers are willing to accept, and the authors note that more than 154M allocated IPv4 addresses may well be reached in the next years if that pain is accepted.
The measure works backwards too: raise the size of the address space to the power of the HD-ratio and you get the number of objects that fit. For IPv4 that is 51 million at 80% and 240 million at the practical limit of 87%.
| Address plan | Reasonable HD=80% | Painful HD=85% | Very painful HD=86% | Practical maximum HD=87% |
|---|---|---|---|---|
| 9-digit plan | 16M | 45M | 55M | 68M |
| 10-digit plan | 100M | 316M | 400M | 500M |
| 32-bit addresses THIS RFC | 51M | 154M | 192M | 240M |
§5Security and IANA Considerations
The memo states that the document has no security implications. It also states that it does not request any IANA action, since the HD-ratio is a way of measuring rather than a protocol or a registry.
The references give the sources behind the numbers: the H Ratio for Address Assignment Efficiency in RFC 1715, the IANA registry of the Internet Protocol version 4 address space, the Internet Domain Survey maintained by the Internet Software Consortium, and Netsizer from Telcordia Technologies.
This memo only measures something, so it changes nothing on the network and asks the IANA for nothing. It measures how full an address plan is.