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]