WDIFF

draft-ietf-malloc-arch-01.txt --> draft-ietf-malloc-arch-02.txt

INTERNET-DRAFT AT&T Research
April 28,
July 2, 1999 D. Thaler
Expires October 1999 January 2000 Microsoft
D. Estrin
ISI

The Internet Multicast Address Allocation Architecture
<draft-ietf-malloc-arch-01.txt>
<draft-ietf-malloc-arch-02.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.

Expires October 1999 January 2000 [Page 1]

Draft MALLOC Architecture April July 1999

1. Abstract

This document proposes a multicast address allocation architecture
for the Internet. The architecture is modular with three layered, layers,
comprising a host-server protocol, mechanism, an intra-domain server-server protocol,
coordination mechanism, and an inter-domain protocol. mechanism.

2. Introduction

This document proposes a multicast address allocation architecture
for the Internet. This architecture Internet, and is designed intended to scale be generic enough to
allocating a very large proportion of the 270 million apply to
both IPv4
multicast addresses available. It will also perform well in an and 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. 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, 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 olutions 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 of
sessions will cease to be used 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

Expires October 1999 [Page 2]

Draft MALLOC Architecture April 1999
of clashing allocations, and good address space utilization. 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, Correctness, Availability and Address Space Packing 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. However, A top-
down partitioning of the address space would be required to
completely guarantee that no clashes would require a top-down occur.

o Address Space Packing in Scarcity Situations
In situations where address space is scarce, partitioning
of the
address space, and to do this space in a manner that provides
sufficient 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 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 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

Expires October 1999 [Page 3]

Draft MALLOC Architecture April 1999
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] provides for reserves the highest 256 addresses in every
administrative 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

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 permit allow the
address allocation architecture to self-organize be organized 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 sub-optimal
routing.

4. Overview of the Architecture

There are three parts to this 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 October 1999 January 2000 [Page 5]

Draft MALLOC Architecture April July 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

layer can be used by different organizations without adversely
impacting other layers.

There are three layers in use.

o An inter-domain protocol (MASC [6]) this architecture (Figure 1). Note 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 layer numbers are different design tradeoffs. An overview
of how these protocols fit together is shown from the layer numbers in figure 1. the
TCP/IP stack, which describe the path of data packets.

+--------------------------+ +------------------------+
| | | |
| to other peers | | to other peers |
| || // | | || // || |
| MASC3 Prefix | | Prefix Prefix | MASC4 MASC5
| Coordinator | |Coordinator Coordinator|
+------------||------------+ +-------||----//---------+
||MASC TCP peerings
||Layer 3 || //
+------------||------------------------------||--//-----------+
| MASC1===========================MASC2 Prefix Prefix |
| Coordinator=======================Coordinator |
| ^ ^ |
| +----------------+-------------+ |
| | multicast|AAP Layer 2 | | |
| MAAS1<--/ MAAS<---/ | +---> MAAS3 MAAS |
| ^ ^ v ^ |
| . . MAAS2 MAAS . |
| . .MADCAP .Layer 1 ^ .MADCAP .Layer 1 |
| v v .MADCAP .Layer 1 v |
| Client1 Client2 Client Client v Client4 Client |
| Client3 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 October 1999 January 2000 [Page 6]

Draft MALLOC Architecture April 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. We expect that allocation 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, we'll get and address space is scarce, address space
fragmentation may occur 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 AS can instead be treated as part of its provider's
allocation domain, and use AAP directly to talk a Layer 2 protocol/mechanism to
the
coordinate allocation between its MAAS's (if any) and those of its provider, and not cause any additional
fragmentation.
provider. An AS should probably take this course of action if:

o it's it is connected to a single provider. provider,

o it does not provide transit for another AS. AS, and

o it has needs fewer than N (say) 256 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

5. Administrative Scoping

To allocate dynamic addresses within administrative scopes, an address, it becomes the server's
responsibility
MAAS must be able to ensure that this learn about the address is not then reused
elsewhere within range and textual
name(s) identifying the same scope.

4.3. Address Allocation Protocol (AAP)

AAP scope itself, and also must learn what
subrange is used 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 claim multicast addresses that it has
allocated, 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 if necessary big "divisible" scopes. MZAP also identifies which is the
case for each scope.

(1) For small scopes, the allocation domain corresponds to defend these the
entire topology within the administrative scope. Hence, all
MAASs inside the scope may use the entire address range
(minus the last 256 addresses if another
MAAS server attempts to allocate reserved as scope-relative
addresses), and use the same address. A MAAS keeps Layer 2 mechanism/protocol to
coordinate allocations. For small scopes, Prefix
Coordinators are not involved.

Expires October 1999 January 2000 [Page 7] 8]

Draft MALLOC Architecture April July 1999

track of all the other multicast addresses in use within

Hence, for small scopes, the same
allocation domain, and when it allocates an address it ensures
that effective "allocation domain"
area may be different for each scope.

(2) For big scopes (including the address is not already in use. AAP is also used by nodes
running MASC to inform global scope), the MAAS's of area inside
the address set (consisting
of a list of address/mask/lifetime tuples) scope may be large enough that is available.
Under normal conditions, simply using a MAAS should only allocate an address
from the unused addresses in Layer 2
mechanism/protocol may be inefficient or otherwise
undesirable. 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 case, the MAAS's within their scope spans multiple
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, domains, and the Layer 3 mechanism/protocol 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 used to divvy up the lifetime of an scoped 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 space among 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 domains. Hence, an MAAS may rely on the address sets allocated by
MASC to build trees learn 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. scope
via MZAP, but must acquire a subrange from which to allocate
from a Prefix Coordinator.

6. Overview of the Allocation Process

Assuming that

Once Layer 3 allocation has been performed for some time (the
startup conditions for MASC are slightly more complex), then large, divisible
scopes, and each Prefix Coordinator has acquired one or more MASC nodes bordering an allocation domain will be
advertising address sets into
prefixes, then those prefixes are passed to all MAAS's within the
Prefix Coordinator's domain using multicast AAP. via a Layer 2 mechanism/protocol.

MAAS's within the domain receive these address sets prefixes and cache store them as
the currently allowable addresses for that domain. These
address sets are unconditionally Each prefix is
valid for their advertised a given lifetime (also acquired via the Layer 3
mechanism/protocol) and cannot be is not revoked before their the lifetime has
expired.

NOTE: MAAS's also need to mention getting range from MZAP for learn of small
scopes, and possibly getting range scopes (e.g., via other methods, such as
233/8-style configuration.

A MZAP) and
store the prefixes associated with them.

Using the Layer 2 mechanism/protocol, each MAAS also receives individual domain-wide multicast address
claims via AAP from ensures that it
will exclude any addresses which have been or will be allocated by
other MAAS's within the its 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 first needs to decide
what the scope information using MADCAP. Any local MAAS can
respond. A responding MAAS provides of the intended session should be, and locate a list
MAAS capable of valid 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. The client then chooses sends a scope, MADCAP REQUEST
message to the MAAS, and requests waits for a NAK message or an address ACK message
containing the allocated information.

Upon receiving a request from that MAAS for a certain time interval.

The client, the MAAS then chooses an
unused address from those not currently used in
the range a prefix for the specified scope, that with a
lifetime which both satisfies the requested time
interval (if possible), acceptable range specified by
the client, and advertises 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 by MADCAP. via the Layer 1
protocol/mechanism. 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 AAP also
allows each 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 pre-reserve a small scopes, MAAS's just use the full address range
provided by MZAP, whereas "pool" of addresses for big scopes, MASC is used
which it need not wait to detect clashes.

If a domain ever begins to
subdivide run out of available multicast
addresses, a Prefix Coordinator in that domain uses the space.)

o Mention stable storage requirement for MAASs but not MASC
nodes. 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., Shah, M., and S. Hanna, M. Shah, "Multicast Address Dynamic
Client Allocation Protocol (MADCAP)", draft-ietf-malloc-
madcap-04.txt, February Work in progress,
draft-ietf-malloc-madcap-05.txt, May 1999.

[5] Handley, M., "Multicast Address Allocation Protocol (AAP)",
draft-ietf-malloc-aap-01.txt, August 1998.
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.

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 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 October 1999 January 2000 [Page 11]
----