MBONE Deployment Working Group David Meyer
Internet Draft University of Oregon
Expiration Date: August 1997 February 1997
Some Issues for an Inter-domain Multicast Routing Protocol
draft-ietf-mboned-imrp-some-issues-00.txt
1. Status Of This Memo
This document is an Internet-Draft. 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.''
To learn the current status of any Internet-Draft, please check the
``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast).
2. Introduction
The IETF's Inter-Domain Multicast Routing (IDMR) working group has
produced several multicast routing protocols, including Core Based
Trees [CBT] and Protocol Independent Multicasting [PIMARCH]. In
addition, the IDMR WG has formalized the specification of the
Distance Vector Multicast Routing Protocol [DVMRP]. Various
specifications for protocol inter-operation have also been produced
(see, for example, [THALER96] and [PIMMBR]). However, none of these
protocols seems ideally suited to the inter-domain routing case; that
is, while these protocols are appropriate for the intra-domain
routing environment, they break down in various ways when applied in
to the multi-provider inter-domain case.
This document considers some of the scaling, stability and policy
issues that are of primary importance in a inter-domain, multi-
David Meyer FORMFEED[Page 1]
Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997
provider multicast environment.
3. Forwarding State Requirements
Any scalable protocol will have to minimize forwarding state
requirements. In the case of dense mode protocols [DVMRP][PIM-DM],
routers may carry forwarding or prune state for every (S,G) pair in
the Internet. This is true even for routers that may not be on any
delivery tree. It seems likely that as multicast deployment scales to
the size of the Internet, maintenance of (S,G) state will become
intractable.
Shared tree protocols, on the other hand, have the advantage of
maintaining a single (*,G) entry for a group's receivers (thus
relaxing the requirement of maintaining (S,G) for the entire
Internet). However, this is not without its own disadvantages; see
the section on "Third-party Resource Dependencies" below.
4. Forwarding State Distribution
The objective of a multicast forwarding state distribution mechanism
is to ensure that multicast traffic is efficiently distributed to
those parts of the topology where there are receivers. Dense and
sparse mode protocols will accept differing overheads based on design
tradeoffs. In the dense mode case, the data-driven nature state
distribution has disadvantage that data is periodically distributed
to branches of the distribution tree which don't have receivers
("Flood and Prune" behavior). It seems unlikely that this mechanism
will be scalable to Internet-wide case.
On the other hand, sparse mode protocols use receiver-initiated,
explicit joins to establish a forwarding path along a shared
distribution tree. While the on-demand nature of sparse mode
protocols have favorable properties with respect to distribution of
forwarding state, it also has the possible disadvantage of creating
dependencies on shared resources (again, see the section on "Third-
Party Resource Dependencies" below).
David Meyer FORMFEED[Page 2]
Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997
5. Forwarding State Maintenance
The many current multicast protocols attempt to accurately and
rapidly maintain distribution trees that are as close to optimal as
possible. This means that the shape of a distribution tree can be
rapidly changing. In addition, since distribution trees can be
global, they can be subject to high frequency control traffic.
In contrast, the focus in the inter-domain unicast routing
environment is on minimizing routing traffic (see, for example,
[VILLAM95]), and controlling stability [LABOV97]. The implication is
that protocol overhead and stability must be controlled if we hope
multicast to scale to Internet sizes. Thus it seems likely that
Inter-domain multicast routing protocols will have to do less
forwarding state maintenance, and hence be less aggressive in
reshaping distribution trees. Note that this reshaping is related to
what has been termed "routing flux" (again, see [LABOV97]), since the
routing traffic does not directly affect path selection. Rather, the
primary effect is to require significant processing resources in a
border router. Finally, note that unlike the unicast case, we do not
have good data characterizing this effect for multicast routers.
5.1. Bursty Source Problem
The "Bursty Source Problem" can be described as those cases in which
sources loose data because there is very long join latency and/or
initial send latency. The current set of multicast routing protocols
attempt, where possible, to avoid this problem (i.e., maximize
response to bursty sources). Further, the combination of long
latencies with flooding joins can become a problem where a large
number of groups are joined and left at high frequency.
6. Mixed Control
Mixing control of topology discovery and distribution tree
construction can lead to efficiencies but also imposes various
constraints on topology discovery mechanisms. For example, DVMRP
[DVMRP] uses topology discovery facilities ("split horizon with
poison reverse") to eliminate duplicate packets on a LAN, and to
detect non-leaf networks (an upstream router uses this information
when pruning downstream interfaces).
On the other hand, PIM [PIM-DM] does not use any topology discovery
algorithm features when building delivery trees. However, this
independence is not without cost: PIM-DM accepts some duplicates on
multi-access LANs as a tradeoff for reduced protocol complexity.
David Meyer FORMFEED[Page 3]
Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997
7. Neighbor Model
The current inter-domain unicast routing model has some key
differences with proposed inter-domain multicast routing models with
respect to neighbor (peer) discovery. In particular, the current set
of multicast protocols depend heavily on dynamic neighbor discovery.
This is analogous to the situation with intra-domain unicast routing,
but is unlike current inter-domain unicast routing, where neighbors
are typically statically configured.
The static neighbor configuration model has several benefits for
inter-domain routing. First, neighbors are predefined, which is a
policy requirement in most cases. In addition, the set of peers in
the inter-domain unicast routing system defines the set of possible
inter-domain topologies (with the current active topology represented
by the collection of AS paths).
Another important difference relates to how inter-domain regions are
modeled. For purposes of this document, consider an inter-domain
region defined to be a part of an arbitrary topology in which a
higher level (inter-domain) routing protocol is used to calculate
paths between regions. In addition, each pair of adjacent regions is
connected by one or more multicast border routers. Current IDMR
proposals (e.g., [HDVMRP], [THALER96]) model an inter-domain region
as a routing domain. That is, border routers internetwork between one
or more intra-domain regions and an inter-domain region (again,
possibly more than one). In this model, inter-networking occurs
"inside" router. However, the inter-provider unicast routing model in
use today is quite different. In particular, the "peering" between
two providers occurs in neither of the provider's routing domains,
nor does it occur in some shared "inter-domain" routing domain. The
separation provides the administrative and policy control that is
required in today's Internet.
8. Unicast Topology Dependency
Ideally, unicast and multicast topologies are congruent in the
Internet. However, since it is frequently difficult to field new
facilities (such as IP multicast) in the "core" the Internet
infrastructure, there will continue to be many cases in which unicast
and multicast topologies are not congruent (either because a region
is not multicast capable at all, or because the region is not
natively forwarding multicast traffic). Thus, it is unlikely that the
entire IPv4 Internet will be able to carry native multicast traffic
in the foreseeable future. In addition, various policy requirements
will in certain cases cause to topologies to further diverge. The
David Meyer FORMFEED[Page 4]
Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997
implication is that a successful IDMR will need a topology discover
mechanism, or have other mechanisms for dealing with those cases in
which unicast and multicast topologies are not congruent.
9. Third-Party Resource Dependencies
Shared tree protocols require one or more globally shared Rendezvous
Points (RPs) [PIM-SM] or Cores [CBT]. The RP or Core effectively
serves as the root of a group specific shared tree. Data is sent to
the RP/Core for delivery on the shared tree. This means that some
groups may have an RP (or core) that is fielded by a third party. For
example, if providers A, B and C share a PIM-SM inter-domain region,
then there will exist an RP that is mapped to C's multicast border
router. In this case, C is hosting a kind of "transit RP" for A and B
(A and B register to C to communicate between themselves, even if C
has no receivers for the group(s) served by the RP.
10. Traffic Concentration Problem
Traffic can be "concentrated" on a shared tree. This can lead to
increased latency or packet loss. However, this is less of a problem
in the shared-media exchange point environment.
11. Distant RP/Core Problem
In the shared tree model, if the RP or Core is distant
(topologically), then joins will travel to the distant RP/Core, even
if the data is being delivered locally. Note that this problem is
exacerbated by the global nature of the RP/Core space; if a router is
registering to a RP/Core that is not in the local domain (say,
fielded by the site's direct provider), then the routing domain is
flat.
David Meyer FORMFEED[Page 5]
Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997
12. Multicast Internal Gateway Protocol (MIGP) Independence
A shared tree, explicit join protocol inter-domain routing protocol
may require modification to a leaf domain's internal multicast
routing mechanism. The problem arises when a domain is running a
"flood and prune" protocol such as DVMRP or PIM-DM internally while
participating in a shared tree inter-domain protocol. In this case,
those areas of the (internal) topology where there are no sources
will not receive inter-domain traffic. It has been suggested that
these protocols be modified to use Domain Wide Reports [HDVMRP] to
communication domain-wide group membership to a domain's border
routers.
13. Encapsulations
An IDMRP should minimize encapsulations where ever possible. PIM-SM
encapsulates packets sent to the shared tree in PIM Register messages
(data can be delivered natively if the last hop router or the RP
switches to the shortest path tree). HDVMRP requires every inter-
domain packet to be rewritten with an additional level of
encapsulation for inter-domain forwarding. Further, the number of
encapsulations/decapsulations for paths that traverse N
administrative domains is O(N); each border border router "registers"
to a group specific RP, which then decapsulates the packet for
distribution on the shared tree.
14. Policy Provisions
Current inter-domain unicast routing protocols have a rich and well
developed policy model. In contrast, multicast routing protocols
have little or no provision for implementing routing policy
(administrative scoping is one major exception). A concrete example
of this need is the various problems with inadvertent injection of
unicast routing tables into the MBONE, coupled with our inability to
propagate the resultant large DVMRP routing tables, point out the
need for such policy oriented controls.
A simple example illustrates why a successful inter-domain multicast
routing protocol will need to have a well developed policy model:
Consider three providers, A, B, and C, that have connections to a
shared-media exchange point. Assume that connectivity is non-
transitive due to some policy (the common case, since bi-lateral
agreements are a very common form of peering agreement). That is, A
and B are peers, B and C are peers, but A and C are not peers. Now,
consider a source prefix P, where P belongs to a customer of A (i.e.,
David Meyer FORMFEED[Page 6]
Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997
P is advertised by A). Now, multicast packets forwarded by A's
border router will be correctly accepted by B, since B sees the RPF
interface for P to be the shared-media of the exchange. Likewise,
C's border router will reject the packets forwarded by A's border
router because, by definition, C does not have A's routes through its
interface on the exchange (so packets sourced "inside" A fail the RPF
check in C's border router).
In the example above, RPF is a powerful enough mechanism to inform C
that it should not accept packets sourced in P from A over the
exchange. However, consider the common case in which P is multi-
homed to both A and B. C now sees a route for P from B though its
interface on the exchange. Without some form of multi-provider
cooperation and/or packet filtering, C could accept multicast packets
from A across the exchange, even though A and C don't peer. Clearly,
this is an unintended consequence. In addition, note that RPF itself
is essentially a packet filtering technology, and as such has
qualitatively different resource requirements than the route filters
that are commonly deployed in border routers.
14.1. Today's MBONE
Another way to view the policy issues described above is to consider
the perspective of unicast reachability. Today's MBONE is comprised
of a single flat AS. Further, this AS running a simple distance
vector topology discovery protocol. This arrangement is unlikely to
scale gracefully or provide the same rich policy control that we find
in the unicast Internet. There are additional problems with a flat AS
model: the flat AS model fits neither the operational or
organizational models commonly found in Internet today.
15. Equal Cost Multipath
A common way to incrementally scale available bandwidth is to provide
parallel equal cost paths. It would be an advantage if a multicast
routing protocol could support this. However, this would seem
difficult to achieve when using Reverse Path Forwarding, so it is
unclear whether this goal is achievable.
David Meyer FORMFEED[Page 7]
Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997
16. Conclusion
Deployment of a general purpose IP multicast infrastructure for the
Internet has been slowed by various factors. One of the primary
reasons, however, is the lack of a true inter-domain Multicast
Routing Protocol. Several proposals have been advanced to solve this
problem, including PIM-SM [PIM-SM], DVMRP [PIMMBR], and Hierarchical
DVMRP [HDVMRP]. However, the concerns outlined above have prevented
any of these protocols from being adopted as the standard inter-
domain multicast routing protocol. Finally, it is worth noting that
DVMRP, since it is the common denominator among router vendor
offerings, is currently the de-facto inter-domain routing protocol.
17. Security Considerations
Security considerations are not discussed in this memo.
18. References
[CBT] A. Ballardie, et. al., "Core Based Trees (CBT)
Multicast -- Protocol Specification --",
draft-ietf-idmr-cbt-spec-06.txt, September, 1996.
[DVMRP] T. Pusateri, "Distance Vector Multicast Routing
Protocol", draft-ietf-idmr-dvmrp-v3-03, September,
1996.
[HDVMRP] Ajit S.. Thyagarajan and Steve Deering, "
Hierarchical Distance-Vector Multicast Routing for
the MBone", In Proceedings of the ACM SIGCOMM, pages
60-66, October, 1995.
[LABOV97] Labovitz, Craig, et. al., "Internet Routing
Instability", Submitted to SIGCOMM97.
[PIMARCH] Estrin, D, et. al., "Protocol Independent Multicast
Sparse Mode (PIM-SM): Motivation and Architecture",
draft-ietf-idmr-pim-arch-04.ps , October, 1996.
[PIM-DM] Estrin, D, et. al., "Protocol Independent Multicast
Dense Mode (PIM-DM): Protocol Specification",
draft-ietf-idmr-PIM-DM-spec-04.ps, September, 1996.
[PIMMBR] Estrin, D, et. al., "PIM Multicast Border Router
(PMBR) specification for connecting PIM-SM domains
to a DVMRP Backbone", draft-ietf-idmr-PIMBR-spec-01.ps,
David Meyer FORMFEED[Page 8]
Internet Draft draft-ietf-mboned-imrp-some-issues-00.txt February 1997
September, 1996.
[PIM-SM] Estrin, D, et. al., "Protocol Independent Multicast
Sparse Mode (PIM-SM): Protocol Specification",
draft-ietf-idmr-PIM-SM-spec-09.ps, October, 1996.
[THALER96] D. Thaler, "Interoperability Rules for Multicast
Routing Protocols", draft-thaler-interop-00.ps,
November, 1996.
[VILLAM95] C Villamizar, Ravi Chandra, and Ramesh Govindan,
"Controlling BGP/IDRP Routing Overhead",
draft-ietf-idr-rout-dampen-00.ps, July, 1995.
19. Acknowledgments
Dino Farinacci and Dave Thaler provided several insightful comments
on earlier drafts of this document.
20. Author Information
David Meyer
University of Oregon
1225 Kincaid St.
Eugene, OR 97403
Phone: (541) 346-1747
e-mail: meyer@antc.uoregon.edu
David Meyer FORMFEED[Page 9]
