Internet Engineering Task Force Alain Durand
INTERNET-DRAFT SUN Microsystem
March 1, 2001 Christian Huitema
Expires Sept. 1, 2001 Microsoft
The High Density ratio for address assignment efficiency
An update on the H ratio
<draft-durand-huitema-high-density-ratio-01.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 some update on the "H ratio" defined
in RFC1715. It defines a new ratio which the authors claim
to be easier to understand.
1. Background
A substantive part of the debate around the choice of IPv6
was about the address size. The consensus was to choose
128 bit fixed length addresses. In the discussion on
address architecture and the address allocation with
the different registries, the "H ratio" defined in RFC1715
was used to analyze various policies. However, this
"H ratio" provides values that are in the range of
0.0 to 0.3, with typical values ranging from 0.20 to 0.26.
Those values are somehow difficult to interpret and the
authors introduce in this document a new formula that
provides results ranging from 0.0 to 1.0 that are easier
to understand.
2. The high density ratio
2.1 Definition of the HD ratio
When considering an addressing plan to allocate objects,
the high 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.
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.
2.2 Variation of the HD ratio
The theoretical minimum value for the HD ratio is:
log( 1 )
HDmin = ------------------------------------------ = 0
log(maximum number allocatable of objects)
The theoretical maximum value for D is obtained when the
number of allocated objects is equal to the maximum
number of allocatable objects. Thus:
log(maximum number allocatable of objects)
HDmax = ------------------------------------------ = 1
log(maximum number allocatable of objects)
So, the ratio HD varies in the interval [0..1], which
make it simple to interpret.
2.3 calculation examples
In 1994, the estimated number of node in the IPv4 Internet
was 3.5 millions. 32 bits of address space covers 2^32 nodes,
so:
log(3 500 000)
HD(1994InternetIPv4) = -------------- = 0.6793
log(2^32)
In 2000, an estimate of the number of allocated IPv4 addresses
is 200 millions.
log(200 000 000)
HD(2000InternetIPv4) = ---------------- = 0.8617
log(2^32)
The following examples are taken from RFC1715:
* 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
log(1.0E+8)
log(1.0E+7)
HD(FrenchTelephone9digit) = ----------- = 0.7777
log(1.0E+9)
* Expending the number of areas in the US telephone system, making it
effectively 10 digits long, for about 1.0 E+8 subscribers.
log(1.0E+8)
HD(USTelephone10digit) = ------------ = 0.7000
log(1.0E+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
log(2^16)
* In 1994, there were about 200 million IEEE 802 nodes in a 48 bit space.
One should note that, in 19994, that space was not saturated.
log(2.0E+8)
HD(IEEE 802) = ----------- = 0.5744
log(2^48)
From those example, we can note that address plans which
HD were greater than 0.80 suffered serious problems.
3. Issues with previously defined ratios
3.1 Issues with a linear ratio
Address assignment are most of the time done in a hierarchical
way. This hierarchy introduce important waste, and the theoretical
maximum of items to be addressed can never be achieved.
A linear ratio L can be defined as:
number of addressed objects
L = -------------------------------------
maximum number of addressable objects
Using a linear scale to measure address efficiency,
typically provides results around or below 1%
and are difficult to interpret.
Computing the linear ratio L on the above examples, we get:
3 500 000
L(1994InternetIPv4) = --------- = .0008 = 0.08 %
2^32
200 000 000
L(2000InternetIPv4) = ----------- = .0465 = 4.65 %
2^32
1.0E+7
L(FrenchTelephone8digit) = ------ = 0.1000 = 10.00 %
1.0E+8
1.0E+7
L(FrenchTelephone9digit) = ------ = 0.0100 = 1.00 %
1.0E+9
1.0E+8
L(USTelephone10digit) = ------- = 0.0100 = 1.00 %
1.0E+10
15000
L(DecNET IV) = ----- = 0.2288 = 22.88 %
2^16
2.0E+8
L(IEEE 802) = ------ = 0.0000007 = 0.00007 %
2^48
3.2 Issues with the H ratio
RFC1715 introduce the H ratio, a logarithmic scale, where
log10(number of objects)
H = ------------------------
available bits
The "available bits" are in fact:
log2(maximum number of addressable items )
so:
log10(number of allocated objects )
H = -------------------------------------------
log2(maximum number of allocatable objects)
log10(X)
But as, for all X > 0, log2(X) = --------
log10(2)
log10(number of allocated objects ) x log10(2)
H = ----------------------------------------------
log10(maximum number of allocatable objects)
log(X)
and as, for all X > 0, log10(X) = -------, we also have:
log(10)
log(number of allocated objects ) x log10(2)
H = --------------------------------------------
log(maximum number of allocatable objects)
Thus, H = HD x log10(2)
As HD varies in the interval [0..1],
H varies in the interval [0..log10(2)].
So we have:
Hmin = 0
Hmax = log10(2) = 0.3010
This makes the H ratio somehow difficult to interpret.
Using the H ratio on the previous examples, we have:
log10(3 500 000)
H(1994InternetIPv4) = ---------------- = 0.2045
32
log10(200 000 000)
H(2000InternetIPv4) = ------------------ = 0.2594
32
log10(1.0E+7)
H(FrenchTelephone8digit) = ------------- = 0.2661
3.3 x 8
log10(1.0E+7)
H(FrenchTelephone9digit) = ------------- = 0.2356
3.3 x 9
log10(1.0E+8)
H(USTelephone10digit) = ------------- = 0.2424
3.3 * 10
log10(15000)
H(DecNET IV) = ------------ = 0.2610
16
log10(2.0E+8)
H(IEEE 802) = ------------- = 0.1729
48
4. Using the HD ratio to evaluate addressing plan
Directly using the HD ratio makes it easy to evaluate
the density of allocated objects.
However, when one want to evaluate how well an
addressing plan will scale, one has to do a reverse
calculation, that is, set a density he is comfortable
with, then compute how many object he could then address.
number allocatable of objects
= exp( HD x log(maximum number allocatable of objects))
= (maximum number allocatable of objects)^HD
One can then trace this function by varying HD
in the rage [0..1] on a semi-logarithm scale
and would plot a straight line.
5. Security considerations
Security issues are not discussed in this memo.
6. Year 2000 compliance
The computation of logarithms are not affected by the Y2K problem.
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 of Poitiers for
his kind support during the elaboration of the HD formula.
9. References
RFC1715, The H Ratio for Address Assignment Efficiency,
Christian Huitema, 1994