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]