MALLOC Working Group M. Handley INTERNET-DRAFT AT&T Research April 28, 1999 D. Thaler Expires October 1999 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 October 1999 [Page 1] Draft MALLOC Architecture April 1999 1. Abstract This document proposes a multicast address allocation architecture for the Internet. The architecture is three layered, comprising a host-server protocol, an intra-domain server-server protocol, and an inter-domain protocol. 2. Introduction This document proposes a multicast address allocation architecture for the Internet. This architecture is designed to scale to allocating a very large proportion of the 270 million IPv4 multicast addresses available. It will also perform well in an IPv6 environment where addresses are not a scare resource, but it is not currently clear whether different mechanisms would be more appropriate if good address space packing were not a primary requirement. As with unicast addresses, the usage of any given 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, 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 olutions 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 TTL scoping of sessions will cease to be used 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 Expires October 1999 [Page 2] Draft MALLOC Architecture April 1999 of clashing allocations, and good address space utilization. Where this interacts with multicast routing, it is desirable for multicast addresses to be allocated in a manner that aids aggregation of routing state. 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, Correctness, and Address Space Packing 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. However, to guarantee no clashes would require a top-down partitioning of the address space, and to do this in a manner that provides sufficient 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 achieving good address space packing and constant availability are more important than guaranteeing that address clashes never occur. What we aim for is a high probability that an address clash does not occur, but we accept that there is a finite Expires October 1999 [Page 3] Draft MALLOC Architecture April 1999 probability of this happening. Should a clash occur, either 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] provides for the highest 256 addresses in every scope range to be reserved for relative assignments. Expires October 1999 [Page 4] Draft MALLOC Architecture April 1999 Relative assignments are also made by IANA and consist of an 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 permit the address allocation architecture to self-organize around current 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 There are three parts to this architecture: Expires October 1999 [Page 5] Draft MALLOC Architecture April 1999 o A protocol (MADCAP [4]) that a multicast client uses to request a multicast address from a local multicast address allocation server (MAAS). o An intra-domain protocol (AAP [5]) that MAAS's use to claim multicast addresses and inform their peer MAAS's which addresses are in use. o An inter-domain protocol (MASC [6]) that allocates multicast address sets to domains. Individual addresses are allocated out of these sets by MAAS's. NOTE: need to mention other experiments, including 233/8 here. We have three protocols because they serve slightly different purposes and require different design tradeoffs. An overview of how these protocols fit together is shown in figure 1. +--------------------------+ +------------------------+ | | | | | to other peers | | to other peers | | || // | | || // || | | MASC3 | | MASC4 MASC5 | +------------||------------+ +-------||----//---------+ ||MASC TCP peerings || // +------------||------------------------------||--//-----------+ | MASC1===========================MASC2 | | ^ ^ | | +----------------+-------------+ | | | multicast|AAP | | | MAAS1<--/ | +---> MAAS3 | | ^ ^ v ^ | | . . MAAS2 . | | . .MADCAP ^ .MADCAP | | v v .MADCAP v | | Client1 Client2 v Client4 | | Client3 | +-------------------------------------------------------------+ Figure 1: An Overview of the Multicast Address Allocation Architecture Expires October 1999 [Page 6] Draft MALLOC Architecture April 1999 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. 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 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, we'll get address space fragmentation if the AS is its own allocation domain. Here, there is no real reason why the border router to the site need run MASC, even though it runs BGP. The domain can use AAP directly to talk to the MAAS's of its provider, and not cause any additional fragmentation. An AS should probably take this course of action if: o it's connected to a single provider. o it does not provide transit for another AS. o it has fewer than N multicast addresses of larger than AS scope allocated on average. The strawman value for N is 256. 4.2. Multicast Address Dynamic Client Allocation Protocol (MADCAP) MADCAP is used by a client to request an address from a 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. 4.3. Address Allocation Protocol (AAP) AAP is used by a MAAS to claim multicast addresses that it has allocated, and if necessary to defend these addresses if another MAAS server attempts to allocate the same address. A MAAS keeps Expires October 1999 [Page 7] Draft MALLOC Architecture April 1999 track of all the other multicast addresses in use within the same allocation domain, and when it allocates an address it ensures that the address is not already in use. AAP is also used by nodes running MASC to inform the MAAS's of the address set (consisting of a list of address/mask/lifetime tuples) that is available. Under normal conditions, a MAAS should only allocate an address from the unused addresses in this advertised set. AAP uses multicast, and operates on a timescale of milliseconds to seconds. NOTE: need to update the above to mention the pool method, which doesn't entail any waiting in the typical case. 4.4. Multicast Address Set Claim (MASC) Protocol MASC is used by nodes (typically these nodes are routers) to claim address sets that satisfy the needs of the MAAS's within their allocation domain. Thus when a MASC node discovers that there are close to insufficient multicast addresses available for AAP to perform well, the MASC node claims a larger address set. MASC is hierarchical (matching provider-customer relationships among ISPs), so MASC nodes below the top level see address set advertisements by higher level MASC nodes, and must choose new address sets from those being advertised. Address sets are also claimed with a lifetime, and that lifetime cannot be longer than the lifetime of the parent address set. When the lifetime of an address set expires, that set will normally be given up. At this point AAP should no longer be advertising addresses from the set. However, if there is still sufficient demand, and the parent set is renewed, then the address set may be renewed. Typically each allocation domain will be advertising several address sets with different lifetimes at any time, allowing the MAAS's to choose appropriate addresses for their clients. MASC uses unicast TCP. MASC cannot use multicast since inter- domain multicast routing may rely on the address sets allocated by MASC to build trees of domains. Typically MASC is performed in routers that are running BGP [8], and the TCP connections parallel those used by BGP. Expires October 1999 [Page 8] Draft MALLOC Architecture April 1999 5. Overview of the Allocation Process Assuming that allocation has been performed for some time (the startup conditions for MASC are slightly more complex), then one or more MASC nodes bordering an allocation domain will be advertising address sets into the domain using multicast AAP. MAAS's within the domain receive these address sets and cache them as the currently allowable addresses for that domain. These address sets are unconditionally valid for their advertised lifetime and cannot be revoked before their lifetime has expired. NOTE: also need to mention getting range from MZAP for small scopes, and possibly getting range via other methods, such as 233/8-style configuration. A MAAS also receives individual domain-wide multicast address claims via AAP from other MAAS's within the domain. It also caches these addresses as being in use for their reported lifetime. When a client needs a multicast address, it locally multicasts a request for scope information using MADCAP. Any local MAAS can respond. A responding MAAS provides a list of valid scopes to the client. The client then chooses a scope, and requests an address from that MAAS for a certain time interval. The MAAS then chooses an address from those not currently used in the range for the scope, that satisfies the requested time interval (if possible), and advertises this domain-wide using AAP. If no clashing AAP claim is received within a short time interval, then the address is returned to the client by MADCAP. If a clashing claim is received by the MAAS, then it chooses a different address and tries again. If no address set is long enough to match the requested time interval, then the MAAS truncates the time interval to that of the longest address set available before advertising the address using AAP. Expires October 1999 [Page 9] Draft MALLOC Architecture April 1999 6. TODO o Mention other experiments such as the 233/8 experiment. o Discuss divisible ("big") vs indivisible ("small") scopes. (For small scopes, MAAS's just use the full address range provided by MZAP, whereas for big scopes, MASC is used to subdivide the space.) o Mention stable storage requirement for MAASs but not MASC nodes. 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 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] Patel, B., Shah, M., and S. Hanna, "Multicast Address Dynamic Client Allocation Protocol (MADCAP)", draft-ietf-malloc- madcap-04.txt, February 1999. [5] Handley, M., "Multicast Address Allocation Protocol (AAP)", draft-ietf-malloc-aap-01.txt, August 1998. [6] Estrin, D., Govindan, R., Handley, M., Kumar, S., Radoslavov, P., and D. Thaler, "The Multicast Address-Set Claim (MASC) Protocol", 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. Expires October 1999 [Page 10] Draft MALLOC Architecture April 1999 [9] Handley, M., Thaler, D., and R. Kermode, "Multicast-Scope Zone Announcement Protocol (MZAP)", draft-ietf-mboned-mzap- 03.txt, February 1999. Expires October 1999 [Page 11]