MALLOC Working Group M. Handley INTERNET-DRAFT AT&T Research July 2, 1999 D. Thaler Expires January 2000 Microsoft D. Estrin ISI The Internet Multicast Address Allocation Architecture Status of this Memo This document is an Internet-Draft and 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/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Copyright Notice Copyright (C) The Internet Society (1999). All Rights Reserved. Expires January 2000 [Page 1] Draft MALLOC Architecture July 1999 1. Abstract This document proposes a multicast address allocation architecture for the Internet. The architecture is modular with three layers, comprising a host-server mechanism, an intra-domain server-server coordination mechanism, and an inter-domain mechanism. 2. Introduction This document proposes a multicast address allocation architecture for the Internet, and is intended to be generic enough to apply to both IPv4 and IPv6 environments. As with unicast addresses, the usage of any given multicast address is limited in two dimensions: Lifetime: an address has a start time and a (possibly infinite) end time, between which it is valid. Scope: an address is valid over a specific area of the network. For example, it may be globally valid and unique, or it may be a private address which is valid only within a local area. This architecture assumes that the primary scoping mechanism in use is administrative scoping, as described in RFC 2365 [1]. While solutions that work for TTL scoping are possible, they introduce significant additional complication for address allocation [2]. Moreover, TTL scoping is a poor solution for multicast scope control, and our assumption is that usage of TTL scoping will decline before this architecture is widely used. 3. Requirements >From a design point of view, the important properties of multicast allocation mechanisms are robustness, timeliness, low probability of clashing allocations, and good address space utilization in situations where space is scare. Where this interacts with multicast routing, it is desirable for multicast addresses to be allocated in a manner that aids aggregation of routing state. Expires January 2000 [Page 2] Draft MALLOC Architecture July 1999 o Robustness The robustness requirement is that an application requiring the allocation of an address should always be able to obtain one, even in the presence of other network failures. o Timeliness From a timeliness point of view, a short delay of up to a few seconds is probably acceptable before the client is given an address with reasonable confidence in its uniqueness. If the session is defined in advance, the address should be allocated as soon as possible, and should not wait until just before the session starts. It is acceptable to change the multicast addresses used by the session up until the time when the session actually starts, but this should only be done when it averts a significant problem such as an address clash that was discovered after initial session definition. o Availability and Correctness A multicast address allocation scheme should always be available, and always able to allocate an address that can be guaranteed not to clash with that of another session. A top- down partitioning of the address space would be required to completely guarantee that no clashes would occur. o Address Space Packing in Scarcity Situations In situations where address space is scarce, partitioning the address space in a manner that provides enough spare space in a partition to give a reasonable degree of assurance that an addresses can still be allocated for a significant time in the event of a network partitioning would result in significant fragmentation of the address space. In addition, providing backup allocation servers in such a hierarchy, so that fail- over (including partitioning of a server and its backup from each other) does not cause collisions would add further to the address space fragmentation. Given that we cannot achieve constant availability, guarantee no clashes, and achieve good address space usage, we must prioritize these properties. We believe that, when address space is scarce, achieving good address space packing and constant availability are more important than guaranteeing that address clashes never occur. What we aim for in these situations is a very high probability that an address clash does not occur, but we accept that there is a finite probability of this happening. Should a clash occur, either Expires January 2000 [Page 3] Draft MALLOC Architecture July 1999 the clash can be detected and addresses changed, or hosts receiving additional traffic can prune that traffic using source-specific prunes available in IGMP version 3, and so we do not believe that this is a disastrous situation. In summary, tolerating the possibility of clashes is likely to allow allocation of a very high proportion of the address space in the presence of network conditions such as those observed in [3]. We believe that we can get good packing and good availability with very good collision avoidance, while we would have to compromise packing and availability significantly to avoid all collisions. 3.1. Address Dynamics Multicast addresses may be allocated in any of three ways: Static: Statically allocated addresses are allocated by IANA for specific protocols that require well-known addresses to work. Examples of static addresses are 224.0.1.1 which is used for the Network Time Protocol and 224.2.127.255 which is used for global scope multicast session announcements. Applications that use multicast for bootstrap purposes should not normally be given their own static multicast address, but should bootstrap themselves using a well-known service location address which can be used to announce the binding between local services and multicast addresses. Static addresses typically have a permanent lifetime, and a scope defined by the scope range in which they reside. As such, a static address is valid everywhere (although the set of receivers may be different depending on location), and may be hard-coded into applications, devices, embedded systems, etc. Static addresses are also useful for devices which support sending but not receiving multicast IP datagrams (Level 1 conformance as specified in RFC 1112 [7]), or even are incapable of receiving any data at all, such as a wireless broadcasting device. Scope-relative: RFC 2365 [1] reserves the highest 256 addresses in every administrative scope range for relative assignments. Relative assignments are made by IANA and consist of an Expires January 2000 [Page 4] Draft MALLOC Architecture July 1999 offset which is valid in every scope. Relative addresses are reserved for infrastructure protocols which require an address in every scope, and this offset may be hard-coded into applications, devices, embedded systems, etc. Such devices must have a way (e.g. via MZAP [9] or via MADCAP [4]) to obtain the list of scopes in which they reside. The offsets assigned typically have a permanent lifetime, and are valid in every scope and location. Hence, the scope- relative address in a given scope range has a lifetime equal to that of the scope range in which it falls. Dynamic: For most purposes, the correct way to use multicast is to obtain a dynamic multicast address. These addresses are provided on demand and have a specific lifetime. An application should request an address only for as long as it expects to need the address. Under some circumstances, an address will be granted for a period of time that is less than the time that was requested. This will occur rarely if the request is for a reasonable amount of time. Applications should be prepared to cope with this when it occurs. At any time during the lifetime of an existing address, applications may also request an extension of the lifetime, and such extensions will be granted when possible. When the address extension is not granted, the application is expected to request a new address to take over from the old address when it expires, and to be able to cope with this situation gracefully. As with unicast addresses, no guarantee of reachability of an address is provided by the network once the lifetime expires. These restrictions on address lifetime are necessary to allow the address allocation architecture to be organized around address usage patterns in a manner that ensures addresses are aggregatable and multicast routing is reasonably close to optimal. In contrast, statically allocated addresses may be given sub-optimal routing. 4. Overview of the Architecture The architecture is modular so that each layer may be used, upgraded, or replaced independently of the others. Layering also provides isolation, in that different mechansisms at the same Expires January 2000 [Page 5] Draft MALLOC Architecture July 1999 layer can be used by different organizations without adversely impacting other layers. There are three layers in this architecture (Figure 1). Note that these layer numbers are different from the layer numbers in the TCP/IP stack, which describe the path of data packets. +--------------------------+ +------------------------+ | | | | | to other peers | | to other peers | | || // | | || // || | | Prefix | | Prefix Prefix | | Coordinator | |Coordinator Coordinator| +------------||------------+ +-------||----//---------+ ||Layer 3 || // +------------||------------------------------||--//-----------+ | Prefix Prefix | | Coordinator=======================Coordinator | | ^ ^ | | +----------------+-------------+ | | | Layer 2 | | | | MAAS<---/ | +---> MAAS | | ^ ^ v ^ | | . . MAAS . | | . .Layer 1 ^ .Layer 1 | | v v .Layer 1 v | | Client Client v Client | | Client | +-------------------------------------------------------------+ Figure 1: An Overview of the Multicast Address Allocation Architecture Layer 1 A protocol or mechanism that a multicast client uses to request a multicast address from a multicast address allocation server (MAAS). When the server grants an address, it becomes the server's responsibility to ensure that this address is not then reused elsewhere within the same scope during the lifetime granted. Examples of protocols or mechanisms at this layer include MADCAP [4], HTTP to access a web page for allocation, and IANA static address assignments. Expires January 2000 [Page 6] Draft MALLOC Architecture July 1999 An abstract API for applications to use for dynamic allocation, independent of the Layer 1 protocol/mechanism in use, is given in [11]. Layer 2 An intra-domain protocol or mechanism that MAAS's use to coordinate allocations with the domain to ensure they do not allocate duplicate addresses. Furthermore, a MAAS must have stable storage, or some equivalent robustness mechanism, to ensure that uniqueness is preserved across MAAS failures and reboots. MAASs also use the Layer 2 protocol/mechanism to acquire (from "Prefix Coordinators") the ranges of multicast addresses out of which they may allocate addresses. Examples of protocols or mechanisms at this layer include AAP [5], and manual configuration of MAAS's. Layer 3 An inter-domain protocol or mechanism that allocates multicast address ranges (with lifetimes) to Prefix Coordinators. Individual addresses may then be allocated out of these ranges by MAAS's inside domains as described above. Examples of protocols or mechanisms at this layer include MASC [6] (in which Prefix Coordinators are typically routers without any stable storage requirement), and static allocations by AS number as described in [10]. Each of the three layers serves slightly different purposes and as such, protocols or mechanisms at each layer may require different design tradeoffs. 4.1. Allocation Domains In this document we use the term allocation domain. An allocation domain is an administratively scoped multicast-capable region of the network, within which a multicast address range assigned by Layer 3 is relevant. We expect that allocation domains will normally coincide with unicast Autonomous Systems (AS's). If an AS is too large, or the network administrator wishes to run Expires January 2000 [Page 7] Draft MALLOC Architecture July 1999 different intra-domain multicast routing in different parts of an AS, that AS can be split by manual setup of a multicast boundary that is not a BGP unicast boundary. This is done by setting up a multicast boundary dividing the unicast AS into two or more multicast allocation domains. If an AS is too small, and address space is scarce, address space fragmentation may occur if the AS is its own allocation domain. Here, the AS can instead be treated as part of its provider's allocation domain, and use a Layer 2 protocol/mechanism to coordinate allocation between its MAAS's (if any) and those of its provider. An AS should probably take this course of action if: o it is connected to a single provider, o it does not provide transit for another AS, and o it needs fewer than (say) 256 multicast addresses of larger than AS scope allocated on average. 5. Administrative Scoping To allocate dynamic addresses within administrative scopes, an MAAS must be able to learn about the address range and textual name(s) identifying the scope itself, and also must learn what subrange is valid for dynamic allocation by the MAAS. The former task, learning the address range and name(s) of a scope, is provided by MZAP [9]. An MAAS may simply passively listen to MZAP messages to acquire this information. For determine the subrange for dynamic allocation, there are two cases for each scope, corresponding to small "indivisible" scopes, and big "divisible" scopes. MZAP also identifies which is the case for each scope. (1) For small scopes, the allocation domain corresponds to the entire topology within the administrative scope. Hence, all MAASs inside the scope may use the entire address range (minus the last 256 addresses reserved as scope-relative addresses), and use the Layer 2 mechanism/protocol to coordinate allocations. For small scopes, Prefix Coordinators are not involved. Expires January 2000 [Page 8] Draft MALLOC Architecture July 1999 Hence, for small scopes, the effective "allocation domain" area may be different for each scope. (2) For big scopes (including the global scope), the area inside the scope may be large enough that simply using a Layer 2 mechanism/protocol may be inefficient or otherwise undesirable. In this case, the scope spans multiple allocation domains, and the Layer 3 mechanism/protocol must be used to divvy up the scoped address space among the allocation domains. Hence, an MAAS may learn of the scope via MZAP, but must acquire a subrange from which to allocate from a Prefix Coordinator. 6. Overview of the Allocation Process Once Layer 3 allocation has been performed for large, divisible scopes, and each Prefix Coordinator has acquired one or more prefixes, then those prefixes are passed to all MAAS's within the Prefix Coordinator's domain via a Layer 2 mechanism/protocol. MAAS's within the domain receive these prefixes and store them as the currently allowable addresses for that domain. Each prefix is valid for a given lifetime (also acquired via the Layer 3 mechanism/protocol) and is not revoked before the lifetime has expired. MAAS's also learn of small scopes (e.g., via MZAP) and store the prefixes associated with them. Using the Layer 2 mechanism/protocol, each MAAS ensures that it will exclude any addresses which have been or will be allocated by other MAAS's within its domain. When a client needs a multicast address, it first needs to decide what the scope of the intended session should be, and locate a MAAS capable of allocating addresses within that scope. To pick a scope, the client will either simply choose a well-known scope, such as the global scope, or it will enumerate the available scopes (e.g., via multicasting a MADCAP query, or by listening to MZAP messages over time) and allow a user to select one. Locating a MAAS can be done via a variety of methods, including manual configuration, using a service location protocol such as SLP [12], or via a mechanism provided by a Layer 1 protocol Expires January 2000 [Page 9] Draft MALLOC Architecture July 1999 itself. MADCAP, for instance, includes such a facility. For example, when enumerating scopes, the client learns of MAASs as they respond with the scope information. Once the client has chosen a scope and located a MAAS, it then requests an address in that scope from the MAAS located. Along with the request it also passes the acceptable range for the lifetimes of the allocation it desires. For example, if the Layer 1 protocol in use is MADCAP, the client sends a MADCAP REQUEST message to the MAAS, and waits for a NAK message or an ACK message containing the allocated information. Upon receiving a request from a client, the MAAS then chooses an unused address in a prefix for the specified scope, with a lifetime which both satisfies the acceptable range specified by the client, and is within the lifetime of the actual prefix. The MAAS uses the Layer 2 mechanism/protocol to ensure that such an address does not clash with any addresses allocated by other MAASs. For example, if Layer 2 uses manual configuration of non- overlapping prefixes, then this simply consists of adhering to the range configured in the local MAAS. If, on the other hand, AAP is used at Layer 2 to provide less address space fragmentation, the MAAS advertises the proposed allocation domain-wide using AAP. If no clashing AAP claim is received within a short time interval, then the address is returned to the client via the Layer 1 protocol/mechanism. If a clashing claim is received by the MAAS, then it chooses a different address and tries again. AAP also allows each MAAS to pre-reserve a small "pool" of addresses for which it need not wait to detect clashes. If a domain ever begins to run out of available multicast addresses, a Prefix Coordinator in that domain uses the Layer 3 protocol/mechanism to acquire more space. 7. References [1] D. Meyer, "Administratively Scoped IP Multicast", BCP 23, RFC 2365, July 1998. [2] Mark Handley, "Multicast Session Directories and Address Allocation", Chapter 6 of PhD Thesis entitled "On Scalable Expires January 2000 [Page 10] Draft MALLOC Architecture July 1999 Multimedia Conferencing Systems", University of London, 1997. http://north.east.isi.edu/ mjh/thesis.ps.gz [3] Mark Handley, "An Analysis of Mbone Performance", Chapter 4 of PhD Thesis entitled "On Scalable Multimedia Conferencing Systems", University of London, 1997. http://north.east.isi.edu/ mjh/thesis.ps.gz [4] Hanna, S., Patel, B., and M. Shah, "Multicast Address Dynamic Client Allocation Protocol (MADCAP)", Work in progress, draft-ietf-malloc-madcap-05.txt, May 1999. [5] Handley, M., "Multicast Address Allocation Protocol (AAP)", Work in progress, draft-ietf-malloc-aap-00.txt, June 1999. [6] Estrin, D., Govindan, R., Handley, M., Kumar, S., Radoslavov, P., and D. Thaler, "The Multicast Address-Set Claim (MASC) Protocol", Work in progress, draft-ietf-malloc-masc-01.txt, August 1998. [7] Deering, S., "Host Extensions for IP Multicasting", RFC 1112, August 1989. [8] Yekhter, Y., and T. Li, "A Border Gateway Protocol 4 (BGP- 4)", RFC 1771, March 1995. [9] Handley, M., Thaler, D., and R. Kermode, "Multicast-Scope Zone Announcement Protocol (MZAP)", Work in progress, draft- ietf-mboned-mzap-04.txt, June 1999. [10] Meyer, D., and P. Lothberg, "Static Allocations in 233/8", Work in progress, draft-ietf-mboned-static-allocation-00.txt, May 1999. [11] R. Rinlayson, "Abstract API for Multicast Address Allocation", Work in progress, draft-ietf-malloc-api-06.txt, June 1999. [12] Veizades, J., Guttman, E., Perkins, C., and S. Kaplan, "Service Location Protocol", RFC 2165, June 1997. Expires January 2000 [Page 11]