[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
INTERNET DRAFT                                               G. Phillips
Expires: January 1999                                            USC/ISI
draft-phillips-malloc-util-00.txt                              M.Smirnov
                                                               GMD FOKUS
                                                               July 1998

           Address utilization in the MASC/BGMP architecture

Status of this Memo

   This document is an Internet-Draft. 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''.

   To learn the current status of any Internet-Draft, please check the
   ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow
   Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or
   ftp.isi.edu (US West Coast).

   Distribution of this document is unlimited.

                                 Abstract

         This memo provides a simple analysis for the address
         utilization in the MASC architecture and concludes
         that the number of levels in the hierarchy should be
         kept small.  More specifically, we believe that the
         number of levels should not exceed 3 MASC levels.

         The memo also motivates that MASC should not rely on
         hints from applications for future address
         requirements, but should rather guess future address
         demand and allocate addresses pro-actively thereby
         reducing the latency for address requests.

1. Introduction

   The MALLOC Working Group has recognized the need for a multicast
   address allocation scheme that is both hierarchical and dynamic
   [Handley97,Kumar97].  Hierarchy is required because it avoids the
   high communication costs at the servers of flat addressing schemes



                                                                [Page 1]


Address utilization in the MASC architecture     July 1998


   and because it increases the aggregation of routes that are injected
   into BGP. On the other hand, dynamic allocation is required because
   it improves address utilization.

   We now give an overview of the MASC architecture as described in
   [Kumar97]. The MASC servers form a hierarchical structure that is
   based on the structure of the existing Internet topology.  In the
   top-most Internet domains, MASC servers peer with each other to
   compete for multicast addresses.  These MASC servers then receive
   address requests from their MASC children in lower-level domains.
   Within each domain, Multicast Address Allocation Servers (MAAS)
   mediate between applications and the MASC server in that domain.  The
   address request protocol is driven by the applications in a bottom-up
   fashion.  That is, applications request addresses from MAAS servers,
   which in turn request addresses from the MASC server and so on up the
   MASC hierarchy.

   In this memo, we use the term "pre-allocated address" to mean an
   address that is removed from the set of globally available addresses
   but is not given immediately to an application.  Instead, a pre-
   allocated address is temporarily managed by some address server,
   before being given to an application upon request.

2. Motivation for pre-allocation

   Although the need for pre-allocation has already been identified by
   the MALLOC Working Group we include the following motivation for
   pre-allocation for completeness.

   We claim that the MASC architecture should be designed to ensure that
   the latency required to allocate an address is small enough for most
   applications.  However, the MASC architecture cannot strictly
   guarantee that every address request will be honored in a short time
   (because if the demand is high then there might not be any available
   addresses).  Consequently, those applications that cannot rely on the
   latency offered by the MASC architecture, would necessarily have to
   allocate addresses ahead of time.

   There are several approaches for ensuring that the MASC architecture
   can honour addresses quickly.  First, an application might give a
   hint that it will require addresses in the future.  Second, the MASC
   system might guess the future demand and acquire the necessary
   addresses ahead of time.  The first approach has the disadvantages
   that (i) existing applications would require modification to add the
   additional hint functionality and (ii) the application's behaviour
   would change because it would then be necessary to start the
   application earlier (so that it can send a hint to the MASC system in
   good time).



                                                                [Page 2]


Address utilization in the MASC architecture     July 1998


   We argue that the MASC architecture should not rely on hints because
   applications should not be compelled to use a complex address
   allocation model.  Consequently, the MASC architecture should pro-
   actively allocate addresses in order to accommodate these simple
   applications.   As an aside, we note that it may be prudent for the
   MASC architecture to accommodate hints for future address
   requirements whenever applications are capable to provide them.


3. At what level should addresses be pre-allocated?

   Pre-allocation could take place at every level in the hierarchy or
   only at certain levels.  In this section we discuss the advantages
   and disadvantages of pre-allocating address at various levels in the
   MASC hierarchy.

   The advantage of pre-allocating addresses at the leaf servers of the
   hierarchy is that the servers can honour requests without
   communicating about individual requests to parent servers. On the
   other hand, the disadvantage of pre-allocating addresses at the
   leaves is that it leads to low address utilization (because there is
   less sharing of pre-allocated addresses).  Thus, higher utilization
   is achieved if addresses are pre-allocated at the higher levels of
   the MASC hierarchy, for example, several coordinating servers might
   share a pool of pre-allocated addresses. Of course the argument for
   greater sharing is identical to the motivation for building a dynamic
   multicast address architecture in the first place.  Thus, pre-
   allocation should be avoided as much as possible, with the caveat
   that the architecture should not preclude small latencies for address
   requests.

   In summary, we argue that addresses should be pre-allocated at the
   lowest level in the address hierarchy. Whether higher levels also
   participate in pre-allocating addresses, thereby improving address
   utilization, is an open issue.


4. Ensuring fairness

   We claim that the MASC architecture should ensure that one domain
   cannot pre-allocate addresses at the expense of another.  However,
   because address allocation is driven from the bottom-up (by
   application demand), it is unclear from the MASC/BGMP architecture
   how fairness would be enforced [Kumar97].  It would appear that
   fairness can be achieved only by imposing limits in a top-down
   fashion.  Also, because there is no root server, it is unclear how
   the top-level peering arrangement of MASC servers can prevent one
   server from allocating more than its fair share while other servers



                                                                [Page 3]


Address utilization in the MASC architecture     July 1998


   struggle to allocate addresses for their domains.


5. Simple analysis of pre-allocation

   In this section we develop a simple analytical model for the address
   utilization of the MASC architecture.   We show that, given our
   assumptions, the utilization decreases exponentially as the number
   levels in the hierarchy increases. We acknowledge that the model is
   overly simple, but the model is provided as a starting point for
   further analysis.

   We assume that the MASC hierarchy forms a tree with 'L' levels and
   that each node has degree 'd'.  Furthermore, we assume that each leaf
   server has allocated M addresses which are actively used by
   applications. Finally, we assume that each server in the tree, pre-
   allocates an additional 'h * M' addresses.  We call 'h' the pre-
   allocation factor and typically 0 <= h <= 1.

   Let UA be the total number of addresses actively used in the tree and
   let PA be total the number of "pre-allocated" addresses. The address
   utilization for the tree is given by:
                                      UA
                     utilization = ---------
                                    UA + PA

   The number of actively used addresses is:
                            UA = M * d^(L-1)

   As we have mentioned above, we assume that all the servers in the
   tree pre-allocate an additional 'h * M' addresses and therefore:
                           PA = M * d^(L-1) * h

   Therefore the utilization is:
                                      1
                    utilization = -----------
                                  (1+h)^(L-1)

   Note that the utilization is independent of the degree of the
   hierarchy.  Actually this independence is not surprising because it
   is a direct consequence of our assumption that the amount of pre-
   allocated addresses at each node is independent of the node degree.

   The following table shows several values of utilization as a function
   of the number of levels 'L' and the pre-allocation factor 'h'.






                                                                [Page 4]


Address utilization in the MASC architecture     July 1998


                                    L
                +------+--------------------------+
                |      |    2       3       4     |
                +------+--------------------------+
                | 0.20 |   0.83    0.69    0.58   |
             h  | 0.30 |   0.77    0.59    0.46   |
                | 0.33 |   0.75    0.56    0.42   |
                +------+--------------------------+
                    Table of address utilization.


6. Discussion

   Our interpretation of the formula for address utilization is that the
   utilization decreases exponentially as a function of the number of
   levels in the hierarchy.  Consequently, there should be strong
   reasons for using more than three levels in the hierarchy because
   otherwise the advantages of sharing addresses will be lost.

   We briefly compare the results of our analysis with the simulation
   results provided in [Kumar97].   In the simulation, the address
   servers perform pre-allocation by requesting blocks of addresses from
   address servers. The address servers impose a steady-state minimum
   utilization of 75% for each level in the hierarchy.   This
   utilization implies that the address servers impose a maximum value
   of approximately 0.33 for the pre-allocation factor 'h' at each level
   in the hierarchy.  (This value is found by solving the equation
   1/(1+h) = 0.75 for h.) The conclusion from the simulation results in
   [Kumar97] are that the utilization converges to 50% for two levels.
   This result should be compared with the table above for h=0.33 and
   L=3.  Note that in our analysis the lower level represents the level
   of applications, while in the simulation cited above the applications
   are not represented, thus in our model L=3 rather than L=2.


7. Future work

   We acknowledge that the above analysis is overly simple.  However we
   claim that our model does capture the essence of address utilization
   under addresses pre-allocation.  To quote from the Russian Physicist,
   Yakov Frenkel:
         "A good theory of a complex system is merely a good
         caricature of this system, which exaggerates the most
         typical properties of the system and deliberately
         ignores all the other, insignificant, properties."

   The analysis in this memo might be enhanced (i) to study different
   pre-allocation techniques or (ii) to improve the accuracy of the



                                                                [Page 5]


Address utilization in the MASC architecture     July 1998


   model for the real system.  Examples of different pre-allocation
   techniques might be (i) pre-allocating addresses only at leaf servers
   to improve utilization or (ii) dividing each "pre-allocation" pool
   into two pools, one being managed by a single server and the other by
   a collaboration of peer servers.  On the other hand, the accuracy of
   the model might be improved by modelling the dynamic behaviour of the
   system, for example, by taking into account the stream of address
   requests.

8. Bibliography

   [Handley97a]    M.Handley, "On scalable Internet Multimedia
   Conferencing Systems.  PhD Thesis, University of London, 1997.

   [Handley97b]    M. Handley, D. Thaler, D. Estrin, "The Internet
   Multicast Address Allocation Architecture", Internet Draft, draft-
   handley-malloc-arch-00.txt, December 15, 1997

   [Kumar97]       S.Kumar, P. Radoslavov, D. Thaler, C. Alaettinoglu,
   D. Estrin, M. Handley, "The MASC/BGMP Architecture for Inter-domain
   Multicast Routing". To appear in ACM Sigcomm 98, September 1998,
   Vancouver, Canada.

Authors Addresses

   Graham Phillips
   USC Information Sciences Institute
   4676 Admiralty Way, Suite 1001
   Marina del Rey, CA 90292-6695
   USA

   Phone: (+1) (310) 822-1511
   Fax:   (+1) (310) 823-6714
   EMail: graham@isi.edu

   Michael Smirnov
   GMD FOKUS
   Kaiserin-Augusta-Allee 31, Berlin 10589

   Phone: +49 30 34637113
   Fax:   +49 30 34638000
   EMail: smirnow@fokus.gmd.de









                                                                [Page 6]