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 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