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
<draft-ietf-malloc-arch-01.txt>
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]
