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