Internet DRAFT - draft-durand-huitema-h-density-ratio

draft-durand-huitema-h-density-ratio



Internet Engineering Task Force                             Alain Durand
INTERNET-DRAFT                                           SUN Microsystem
August 28, 2001                                        Christian Huitema
Expires March, 1, 2002                                         Microsoft



    The Host-Density Ratio for Address Assignment Efficiency:
                    An update on the H ratio
          <draft-durand-huitema-h-density-ratio-02.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 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
   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 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 = 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.



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