Network Working Group Steven Deering (XEROX)
Internet Draft Deborah Estrin (USC)
Dino Farinacci (CISCO)
Mark Handley (UCL)
Ahmed Helmy (USC)
Van Jacobson (LBL)
Chinggung Liu (USC)
Puneet Sharma (USC)
David Thaler (UMICH)
Liming Wei (CISCO)
draft-ietf-idmr-pim-arch-05.txt August 4, 1998
Protocol Independent Multicast-Sparse Mode (PIM-SM): Motivation and
Architecture
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. Internet Drafts may be updated, replaced, or obsoleted by
other documents at any time. It is not appropriate to use Internet
Drafts as reference material or to cite them other than as a
``working'' draft'' or ``work in progress.''
Please check the I-D abstract listing contained in each Internet
Draft directory to learn the current status of this or any other
Internet Draft.
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 1]
Internet Draft PIM-SM Architecture Aug 1998
Abstract
Traditional multicast routing mechanisms (e.g. DVMRP and
MOSPF [1][2]) were intended for use within regions where groups are
widely represented or bandwidth is universally plentiful. When group
members, and senders to those group members, are distributed
sparsely across a wide area, these schemes are not efficient; data
packets or membership report information are periodically sent over
many links that do not lead to receivers or senders, respectively.
This characteristic lead the Internet community to investigate
multicast routing architectures that efficiently establish
distribution trees across wide-area internets, where many groups are
sparsely represented and where bandwidth is not uniformly plentiful
due to the distances and multiple administrations traversed.
Efficiency is evaluated in terms of the state, control message
processing, and data packet processing required across the entire
network in order to deliver data packets to the members of the group.
The Protocol Independent Multicast--Sparse Mode (PIM-SM)
architecture:
(a) maintains the traditional IP multicast service model of
receiver-initiated membership;
(b) uses explicit joins that propagate hop-by-hop from
members' directly connected routers toward the distribution
tree.
(c) builds a shared multicast distribution tree centered at a
Rendezvous Point, and then builds source-specific trees for
those sources whose data traffic warrants it.
(d) is not dependent on a specific unicast routing protocol;
and
(e) uses soft-state mechanisms to adapt to underlying network
conditions and group dynamics.
The robustness, flexibility, and scaling properties of this
architecture make it well suited to large heterogeneous inter-
networks.
This document motivates and describes the PIM-SM architecture.
Companion documents describe the detailed protocol mechanisms
for PIM-SM and PIM-DM, respectively [3][4].
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 2]
Internet Draft PIM-SM Architecture Aug 1998
1 Introduction
This document describes an architecture for efficiently routing
to multicast groups that may span wide-area (and inter-domain)
internets. We refer to the approach as Protocol Independent
Multicast-Sparse Mode (PIM-SM) because it is not dependent on
any particular unicast routing protocol. Throughout this
document we will use the shorter term PIM, to mean PIM-SM. When
we are referring to the PIM Dense Mode protocol we will say
PIM-DM explicitly.
The most significant innovation in this architecture is the
efficient support of sparse, wide area groups. This sparse mode
(SM) of operation complements the traditional dense-mode
approach to multicast routing for campus networks, as developed
by Deering [5][6] and implemented in MOSPF and DVMRP [1][2].
These traditional dense mode multicast schemes were intended for
use within regions where a group is widely represented or
bandwidth is universally plentiful. However, when group members,
and senders to those groups, are distributed sparsely across
a wide area, these schemes are not efficient; data packets (in
the case of DVMRP) or membership report information (in the case
of MOSPF) are occasionally sent over many links that do not
lead to receivers or senders, respectively. The purpose of this
work is to develop a multicast routing architecture that
efficiently establishes distribution trees even when members are
sparsely distributed. Efficiency is evaluated in terms of the
state, control message, and data packet overhead required across
the entire network in order to deliver data packets to the
members of the group.
1.1 Definition of Terms (Glossary):
Following is a list of terms and definitions
used throughout this document, in alphabetical order.
This is a subset of the glossary list that appears in the
protocol specification.
* Asserts. The process of choosing a single router to
forward multicast packets from a particular source onto a
particular LAN segment. The need for Asserts arises when
a LAN segment has multiple directly-connected routers with
routes to the source.
* Bootstrap router (BSR). A BSR is a dynamically elected
router within a PIM domain. It is responsible for
constructing the RP-Set and originating Bootstrap messages.
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 3]
Internet Draft PIM-SM Architecture Aug 1998
* Candidate-BSR (C-BSR). A C-BSR is a router configured to
participate in the BSR election and act as BSRs if elected.
* Dense-mode (DM). A generic term referring to a multicast
routing protocol that is optimized for dense groups. DVMRP,
MOSPF, and Dense-mode PIM are examples.
* Designated Router (DR). The DR is the highest IP
addressed PIM router on a multi-access LAN. Normally, the
DR sets up multicast route entries and sends corresponding
Join/Prune and Register messages on behalf of directly-
connected receivers and sources, respectively. The DR may
or may not be the same router as the IGMP Querier. The DR
may or may not be the long-term, last-hop router for the
group, or a particular source that is sending to the group;
a router on the LAN that has a lower metric route to the
data source, or to the group's RP, may take over that role.
* Incoming interface (iif). The iif of a multicast route
entry indicates the interface from which multicast data
packets are accepted for forwarding. The iif is initialized
when the entry is created.
* Join list. The Join list is one of two lists of IP unicast
addresses that is included in a Join/Prune message; each
address refers to a source or RP. It indicates those
sources or RPs to which downstream receiver(s) wish to
join.
* Last-hop router. The last-hop router is the router which
forwards multicast data packets to directly-connected
member hosts. In general the last-hop router is the DR for
the LAN. However, under various conditions described in
this document a parallel router connected to the same LAN
may take over as the last-hop router in place of the DR.
* Member. A host that desires to receive multicast datagrams
for a group. This host need not be a sender to the group. A
Member is synonymously called a Receiver.
* Outgoing interface (oif) list. Each multicast route
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 4]
Internet Draft PIM-SM Architecture Aug 1998
entry
has an oif list containing the outgoing interfaces to which
multicast packets matching that entry should be forwarded.
* Prune List. The Prune list is the second list of IP
unicast addresses that is included in a Join/Prune message.
It indicates those sources or RPs from which downstream
receiver(s) wish to prune.
* PIM Multicast Border Router (PMBR). A PMBR connects a
PIM domain to other multicast routing domain(s).
* Rendezvous Point (RP). Each multicast group has a
shared-tree via which receivers hear of sources. The RP is
the root of this per-group shared tree, called the RP-Tree.
Candidate-RPs are routers configured to participate as RPs
for some (or all) groups.
* RP-Set. The BSR for a PIM region constructs a set of RP
IP addresses based on Candidate-RP advertisements received.
The RP-Set information is distributed to all PIM routers in
a domain in a Bootstrap message.
* Reverse Path Forwarding (RPF). RPF is used to select the
appropriate incoming interface for a multicast route entry
. The RPF neighbor for an IP address X is the the next-hop
router used to forward packets toward X. The RPF interface
is the interface to that RPF neighbor. In the common case
this is the next hop used by the unicast routing protocol
for sending unicast packets toward X. For example, in cases
where unicast and multicast routes are not congruent, it
can be different.
* Route entry. A multicast route entry is state maintained
in a router along the distribution tree and is created, and
updated based on incoming control messages, and in some
cases data packets. The route entry may be different from
the forwarding entry; the latter is used to forward data
packets in real time. Typically a forwarding entry is not
created until data packets arrive, the forwarding entry's
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 5]
Internet Draft PIM-SM Architecture Aug 1998
iif and oif list are copied from the route entry, and the
forwarding entry may be flushed and recreated at will.
* Shared Tree (RP tree). The set of paths connecting all
receivers of a group to its RP is the RP tree. A receiver
on the RP tree receives packets from all sources of the
group, except those sources that were pruned off the RP
tree.
* Shortest path tree (SPT). The SPT is the multicast
distribution tree created by the merger of all of the
shortest paths that connect receivers to the source (as
determined by unicast routing).
* Source. A host that sends multicast datagrams to a group.
A Source is not required to be a member. A Source is
synonymously called a Sender.
* Sparse Mode (SM). Sparse mode PIM uses explicit
Join/Prune messages and Rendezvous points in place of Dense
Mode PIM's and DVMRP's broadcast and prune mechanism.
* Wildcard (WC) multicast route entry. Wildcard multicast
route entries are those entries that may be used to forward
packets for any source sending to the specified group.
Wildcard bits in the join list of a Join/Prune message
represent either a (*,G) or (*,*,RP) join; in the prune
list they represent a (*,G) prune.
* (S,G) route entry. (S,G) is a source-specific route
entry. It may be created in response to data packets,
Join/Prune messages, or Asserts. The (S,G) state in routers
creates a source-rooted, shortest path (or reverse shortest
path) distribution tree. (S,G)RPT bit entries are source-
specific entries on the shared RP-Tree; these entries are
used to prune particular sources off of the shared tree.
* (*,G) route entry. Group members join the shared RP-Tree
for a particular group. This tree is represented by (*,G)
multicast route entries along the shortest path branches
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 6]
Internet Draft PIM-SM Architecture Aug 1998
between the RP and the group members.
* (*,*,RP) route entry. PMBRs join toward all RPs
supporting non-local groups, within their PIM domain in
order to pull packets generated within the region out to
the borders of the region. The routers along the shortest
path branches between the RP(s) and the PMBRs keep (*,*,RP)
state and use it to determine how to deliver packets toward
the PMBRs if data packets arrive for which there is not a
longer match.
1.2 Background
In the traditional dense-mode IP multicast model, established by
Deering [6], a multicast address is assigned to the collection
of receivers for a multicast group. Senders simply use that
address as the destination address of a packet to reach all
members of the group. The separation of senders and receivers
allows any host, member or non-member, to send to a group. A
group membership protocol (IGMP) [7][8] is used for routers to
learn the existence of members on their directly attached
subnetworks.
This receiver-initiated join procedure has very good scaling
properties; as the group grows, it becomes more likely that a
new receiver will be able to splice onto a nearby branch of the
distribution tree. A multicast routing protocol, in the form of
an extension to existing unicast protocols (e.g. DVMRP, an
extension to a RIP-like distance-vector unicast protocol; or
MOSPF, an extension to the link-state unicast protocol OSPF), is
executed on routers to construct multicast packet delivery paths
and to accomplish multicast data packet forwarding.
In the case of link-state protocols, changes of group membership
on a subnetwork are detected by one of the routers directly
attached to that subnetwork, and that router broadcasts the
information to all other routers in the same routing domain [9].
Each router maintains an up-to-date image of the domain's
topology through the unicast link-state routing protocol. Upon
receiving a multicast data packet, the router uses the topology
information and the group membership information to determine
the shortest-path tree (SPT) from the packet's source subnetwork
to its destination group members. Broadcasting of membership
information is one major factor preventing link-state multicast
from scaling to larger, wide-area, networks --- every router
must receive and store membership information for every group in
the domain. The other major factor is the processing cost of the
Dijkstra shortest-path-tree calculations performed to compute
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 7]
Internet Draft PIM-SM Architecture Aug 1998
the delivery trees for all active multicast sources [10] for all
groups, thus limiting its applicability on an internet-wide
basis.
Distance-vector multicast routing protocols construct multicast
distribution trees using variants of Reverse Path Forwarding
(RPF) [11]. When the first data packet is sent to a group from a
particular source subnetwork, and a router receiving this packet
has no knowledge about the group, the router forwards the
incoming packet out all interfaces except the incoming
interface. (Some schemes reduce the number of outgoing
interfaces further by using unicast routing protocol information
to keep track of child-parent information [6][2].) A special
mechanism is used to avoid forwarding of data packets to leaf
subnetworks with no members in that group (also known as
truncated broadcasting). Also if the arriving data packet does
not come through the interface that the router uses to send
packets to the source of the data packet, the data packet is
silently dropped; thus the term Reverse Path Forwarding [11].
When a router attached to a leaf subnetwork, receives a data
packet addressed to a new group, if it finds no members present
on its attached subnetworks, it sends a prune message upstream
towards the source of the data packet. The prune messages prune
the tree branches not leading to group members, thus resulting
in a source-specific shortest-path tree with all leaves having
members. Pruned branches will ``grow back'' after a time-out
period; these branches will again be pruned if there are still
no multicast members and data packets are still being sent to
the group.
Compared with the total number of destinations within the
greater internet, the number of destinations having group
members of any particular wide-area group is likely to be
small. More importantly, bandwidth limitations, and therefore
data and control message overhead, should not be ignored in a
wide area context. In the case of distance-vector multicast
schemes, routers that are not on the multicast delivery tree
still have to carry the periodic truncated-broadcast of packets,
and process the subsequent pruning of branches for all active
groups. One particular distance-vector multicast protocol,
DVMRP, has been deployed in hundreds of regions connected by the
MBONE [12]. However, its occasional broadcasting behavior
severely limits its capability to scale to larger networks
supporting much larger numbers of groups, many of which are
sparse.
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 8]
Internet Draft PIM-SM Architecture Aug 1998
1.3 Extending multicast to the wide area: scaling issues
The scalability of a multicast protocol can be evaluated in
terms of its overhead growth with the size of the internet,
numbers of receivers or sources per group, number of groups, and
distribution of group receivers and senders. Overhead is
evaluated in terms of resources consumed in routers and links,
i.e., state, processing, and bandwidth.
Existing dense-mode link-state and distance-vector multicast
routing schemes have good scaling properties only when multicast
groups densely populate the network of interest, or when the
overhead of dense-mode operation is negligible relative to the
network resources. When most of the subnets or links in the
(inter)network have group members, then the bandwidth, storage
and processing overhead of broadcasting membership reports
(link-state), or data packets (distance-vector) is warranted,
since the information or data packets are needed in most parts
of the network anyway. The emphasis of our work is to develop
multicast protocols that will also efficiently support the
sparsely distributed groups that are likely to be most prevalent
in wide-area, multi-administration, inter-networks where
resources must be used more conservatively.
1.4 Overhead and tree types
[Figures are present only in the postscript version]
Fig. 1 Example of Multicast Trees
The examples in Figure 1 illustrate the inadequacies of dense-
mode mechanisms when supporting sparse, wide area groups. There
are three domains that communicate via an internet. There is a
member of a particular group, G, located in each of the domains.
There are no other members of this group currently active in the
internet. If a traditional IP multicast routing mechanism such
as DVMRP is used, then when a source in domain
A starts to send to the group, its data packets will be
broadcast throughout the entire internet. Subsequently all those
sites that do not have local members will send prune messages
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 9]
Internet Draft PIM-SM Architecture Aug 1998
and the distribution tree will stabilize to that illustrated
with bold lines in Figure 1(b). However, periodically, the
source's packets will be broadcast throughout the entire
internet when the pruned-off branches times out.
Thus far we have motivated our design by contrasting it to the
traditional dense-mode IP multicast routing protocols. The Core
Based Tree (CBT) protocol [13] was proposed to address similar
scaling problems in support of sparse-mode multicast. CBT uses a
single delivery tree for each group, rooted at one of a small
set of ``core'' routers and shared by all senders to the group.
CBT does not exhibit the occasional broadcasting or flooding
behavior of earlier protocols. However, CBT does so at the cost
of imposing a single shared tree for each multicast group.
If CBT were used to support the example group, then a core might
be defined in domain A, and the distribution tree illustrated in
Figure 1(c) would be established. This distribution tree would
also be used by sources sending from domains B and C. This would
result in concentration of all sources' traffic on the path
indicated with bold lines. We refer to this as traffic
concentration. This is a potentially significant issue with
any protocol that imposes a single shared tree per group. In
addition, the packets traveling from Y to Z will not travel
via the shortest path used by unicast packets between Y and Z.
[Figures are present only in the postscript version]
Fig. 2 Comparison of shortest-path trees and center-based tree
We need to know the kind of degradations a core-based tree can
incur in average networks. David Wall [14] proved that the bound
on maximum delay of an optimal core-based tree (which he called
a center-based tree) is 2 times the shortest-path delay. To
get a better understanding of how well optimal core-based trees
perform in average cases, we simulated an optimal core-based
tree algorithm over large number of different random graphs. We
measured the maximum delay within each group, and experimented
with graphs of different node degrees. We show the ratio of the
CBT maximum delay versus shortest-path tree maximum delay in
Figure 2(a). For each node degree, we tried 500 different 50-
node graphs with 10-member groups chosen randomly. It can be
seen that the maximum delays of core-based trees with optimal
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 10]
Internet Draft PIM-SM Architecture Aug 1998
core placement, are up to 1.4 times greater than shortest-path
trees. Note that although some error bars in the delay graph
extend below 1, there are no real data points below 1 --- the
distribution is not symmetric, for more details see [15]. For
interactive applications where low latency is critical, it is
desirable to use the shortest-path trees to avoid the longer
delays of an optimal core-based tree.
With respect to the potential traffic concentration problem, we
also conducted simulations in randomly generated 50-node
networks. In each network, there were 300 active groups all
having 40 members, of which 32 members were also senders. We
measured the number of traffic flows on each link of the
network, then recorded the maximum number within the network.
For each node degree between three and eight, 500 random
networks were generated, and the measured maximum number of
traffic flows were averaged. Figure 2(b) shows a plot of the
measurements in networks with different node degrees. This
experiment demonstrates situations in which CBT may exhibit
significantly greater traffic concentrations.
It is evident to us that both tree types have their advantages
and disadvantages. One type of tree may perform very well under
one class of conditions, while the other type may be better in
other situations. For example, shared trees may perform very
well for large numbers of low data rate sources (e.g., resource
discovery applications), while SPT(s) may be better suited for
high data rate sources (e.g., real time teleconferencing). It
would be ideal to flexibly support both types of trees within
one multicast architecture, so that the selection of tree types
becomes a configuration decision within a multicast protocol. A
more complete analysis of these tradeoffs can be found in [15].
PIM is designed to address the two issues addressed above: to
avoid the overhead of broadcasting packets when group members
sparsely populate the internet, and to do so in a way that
supports good-quality distribution trees for heterogeneous
applications.
In PIM, a multicast router can choose to use shortest-path trees
or a group-shared tree. The last-hop routers of the receivers
can make this decision independently. A receiver could even
choose different types of trees for different sources. In
general, we recommend that routers be configured to join the
shortest path tree for a source when the source's data rate
exceeds a configured threshold.
The capability to support different tree types is the
fundamental difference between PIM and CBT. There are other
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 11]
Internet Draft PIM-SM Architecture Aug 1998
significant protocol engineering differences as well, the most
significant of which is PIM's use of soft state reliability
mechanisms. CBT uses explicit hop-by-hop mechanisms to achieve
reliable delivery of control messages. As described in the next
section, PIM uses periodic refreshes as its primary means of
reliability. This approach reduces the complexity of the
protocol and covers a wide range of protocol and network
failures in a single simple mechanism. Although soft-state
refreshing can introduce additional message protocol overhead,
we introduce the notion of scalable timers to address such
concerns.
1.5 Document organization
In the remainder of this document we enumerate the specific
design requirements for wide-area multicast routing (section
2), summarize the architectural components and functions
(section 3), enumerate several protocol engineering choices
made in the design of PIM protocols (section 4), and consider
the use of aggregation to address the scalability problem
(section 5). Protocol details can be found in [3].
2 Requirements
We had several design objectives in mind when designing this
architecture:
* Sparse-Mode Regions
We define a sparse mode region as one in which
(a) the number of networks/domains with group members
present is significantly smaller than number of
networks/domains in the region as a whole;
(b) group members span an area that is too large/wide to
rely on scope control; and
(c) the region spanned by the group is not sufficiently
resource rich to ignore the overhead of traditional
schemes.
Groups in sparse-mode regions are not necessarily ``small'';
therefore we must support dynamic groups with large numbers
of participants (i.e. receivers and senders).
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 12]
Internet Draft PIM-SM Architecture Aug 1998
* High-Quality Data Distribution
We wish to support low-delay data distribution when needed
by the application. In particular, we avoid imposing a
single shared tree in which data packets are forwarded to
receivers along a common tree, independent of their source.
Source-specific trees are superior when
(a) multiple sources send data simultaneously and would
experience poor service when the traffic is all
concentrated on a single shared tree, or
(b) the path lengths between sources and destinations in
the shortest-path tree (SPTs) are significantly
shorter than in the shared tree.
* Routing Protocol Independence
The protocol should make use of existing unicast routing
functionality to adapt to topology changes, but at the same
time be independent of the particular protocol employed.
This independence has another advantage that the multicast
domain boundaries may extend beyond unicast domain
boundaries. This allows network designers to take into
consideration the multicast requirements and not to be
burdened with unicast topology restrictions. We accomplish
this by letting the multicast protocol make use of the
unicast routing tables, independent of how those tables are
computed.
* Interoperability with dense mode protocols
We require interoperability with traditional RPF and link-
state multicast routing, both intra-domain and inter-
domain. For example, the intra-domain portion of a
distribution tree may be established by some other IP
multicast protocol, and the inter-domain portion by PIM; or
vice versa. In some cases it will be necessary to impose
some additional protocol or configuration overhead in order
to interoperate with some intra-domain routing protocols.
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 13]
Internet Draft PIM-SM Architecture Aug 1998
* Robustness
The protocol should be able to gracefully adapt to routing
changes. We achieve this by
(a) using soft state refreshment mechanisms,
(b) avoiding a single point of failure by using an RP-
Set, and
(c) adapting along with (and based on) unicast routing
changes to deliver multicast service so long as
unicast packets are being serviced.
* Scalability
We provide mechanisms for scaling with group and network
size. These mechanisms address the forms of overhead:
control messages and state. Bandwidth consumed by data
packets is already minimized through the use of explicit-
join sparse mode. Control message overhead can also be
limited to a fixed percentage of the link bandwidth by
adjusting the frequency of periodic messages on a link by
link basis. This method of controlling overhead was
proposed by Van Jacobson.
State overhead can be managed in such a way that each
router can unilaterally choose its own tradeoff point
between the amount of state maintained and the amount of
bandwidth consumed by unneeded flooding of multicast
packets.
3 PIM Components and Functions: Overview
In this section we describe the architectural components of PIM.
The detailed protocol mechanisms are described in [3]. As
described, traditional multicast routing protocols were
optimized for densely distributed groups or uniformly
bandwidth-rich regions, and rely on data driven actions in all
network routers to establish efficient distribution trees. In
contrast, sparse-mode multicast constrains data distribution so
that packets reach only routers that are on the path to group
members. PIM differs from existing IP multicast schemes in two
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 14]
Internet Draft PIM-SM Architecture Aug 1998
fundamental ways:
* Routers with local (or downstream) members join a sparse-
mode PIM distribution tree by sending explicit Join/Prune
messages; in dense-mode IP multicast membership is assumed
and multicast data packets are sent until routers without
local (or downstream) members send explicit prune messages
to remove themselves from the distribution tree.
* Whereas dense-mode IP multicast tree construction is data
driven, sparse-mode PIM must use per-group Rendezvous
Point for receivers to ``meet'' new sources. Rendezvous
Points (RP) are used by senders to announce their existence
and by receivers to learn about new senders of a group. In
SM, the shared-tree join state is stored in anticipation of
data packets, whereas DM does not create state until a data
packet arrives. The source-specific trees and associate
state are data-driven in PIM, as in PIM-DM.
The shortest-path-tree state maintained in routers is roughly
the same type as the multicast routing information that is
currently maintained by routers running existing IP multicast
protocols such as MOSPF, i.e., source (S), multicast address
(G), outgoing interface set (oif), incoming interface (iif).
We refer to this information as the multicast routing
entry for (S,G). For all routers containing a (S,G) entry, their
oif's and iif together form a shortest-path tree rooted
at S.
An entry for a shared tree can match packets from any source for
its associated group if the packets come through the right
incoming interface, we denote such an entry (*,G). A (*,G) entry
keeps the same information a (S,G) entry keeps, except that it
saves the RP address in place of the source address. There is a
wildcard flag (WC-bit) indicating that this is a wild card
entry, and an RPT-bit indicating that this is a shared tree
entry.
[Figures are present only in the postscript version]
Fig. 3 How senders rendezvous with receivers
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 15]
Internet Draft PIM-SM Architecture Aug 1998
Figure 3 shows a simple scenario of a sender and a receiver
joining a multicast group via an RP. When the receiver wants to
join a multicast group, its last-hop PIM router ( A in fig 3)
sends a Join/Prune message towards the RP for the group. If the
last-hop router does not have RP information, it is considered
an error. Processing of this message by intermediate routers
sets up the multicast tree branch from the RP to the receiver.
When sources start sending to the multicast group, the
designated router ( D in fig 3) sends a PIM-Register message,
encapsulating the data packet, to the RP for that group. If the
source's data rate warrants a source-specific tree, the RP
responds by sending a Join/Prune message towards the source.
Processing of these messages by intermediate routers (there are
no intermediate routers between the RP and the source in fig 3)
sets up a packet delivery path from the source to the RP.
If source-specific distribution trees are desired (based on the
source's data rate or some other configuration parameter), the
last-hop PIM router for each member eventually joins the
source-rooted distribution tree for each source by sending a
Join/Prune message towards the source, including the source in
the Join list. After data packets are received on the new path,
router B in fig 3 sends a PIM-prune message towards the RP,
including the source S in the prune list.
B knows, by checking the incoming interface in it routing
table, that it is at a point where the shortest-path tree and
the RP tree branches diverge. A flag, called SPT-bit, is
included in (S,G) entries to indicate whether the transition
from shared tree to shortest-path tree has completed. This
minimizes the chance of losing data packets during the
transition.
Each PIM router must be able to map a multicast group address to
that group's RP (an IP address). To do so, an RP-Set is
distributed to all PIM routers within a region, and each router
runs the same hash function to map from group address to a
particular RP in the RP-Set. In this way all routers within a
PIM region map a particular group address to the same RP. The
RP-Set is constructed and distributed by a dynamically-elected
bootstrap router (BSR) within the region. Only a single RP is
active for a group at any one point in time, and the BSR is
responsible for keeping the RP-Set up to date. Therefore, all
candidate RPs within the region send periodic advertisements
(liveness indication) to the BSR.
PIM avoids explicit enumeration of receivers. In general, in
many existing and anticipated applications, the number of
receivers is much larger than the number of sources, and when
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 16]
Internet Draft PIM-SM Architecture Aug 1998
the number of sources is very large, the average data rate tends
to be lower (e.g. resource discovery). In any finite capacity
network there is an upper bound on the data rate that any
individual host can send or receive. Therefore there are
fundamental bounds on the number of high data rate sources that
can simultaneously send to the same group. However, there are no
such bounds on the number of low datarate sources that can
simultaneously send to the same group. If there are very large
numbers of sources sending to a group, but the sources' average
data rates are low, then it may be more efficient to support the
group with a shared tree instead which has less per-source
overhead; therefore we suggest triggering Shortest Path Tree
(SPT) Join/Prune messages only after the last hop router has
received a threshold datarate from the particular source. If
sources are low data rate, these Join/Prunes will not be
triggered and receivers will receive packets via the shared tree
instead and no source specific tree state will be constructed.
Issues of group-specific state proliferation and state
aggregation are discussed further in section 5. In summary,
data packets from the source will travel to the RP in Register
messages, and from the RP will travel to receivers via the
distribution paths established by the Join/Prune messages sent
upstream from receivers towards the RP. If the RP and receivers
initiate shortest path tree Join/Prunes, the sources data
packets will longest match on the source specific (S,G) state
instead of traveling via the RP distribution tree. Some data
packets will continue to travel from the sources to the RP in
order to reach new receivers. Similarly, receivers will continue
to receive some data packets via the RP tree in order to pick up
new senders. However, when source-specific tree distribution is
used, most data packets will arrive at receivers over a
shortest-path distribution tree. At times when group
participation is not changing, and all receivers have joined the
shortest path tree(s), the RP can inform source(s) to stop
sending data-encapsulating Register messages.
4 Protocol Engineering Design Features
In this section we describe engineering features embodied in the
PIM protocols: robustness, interaction with other multicast
protocols, and multicast service interfaces.
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 17]
Internet Draft PIM-SM Architecture Aug 1998
4.1 Robustness features
There are several areas in which PIM is designed for robustness.
4.1.1 Lost PIM messages
The protocol is fairly robust to lost control messages. If a
PIM-Register message gets lost then data packets will continue
to be encapsulated in subsequent PIM-Register messages until the
first hop router receives a Register-stop message message from
the RP. If a new Join/Prune message (carrying join information)
is lost over an off-tree link (i.e. a link that is not already
part of the mutlicast distribution tree), then for the remainder
of the refresh period, packets will not be forwarded on the new
path, causing join latency; or in the case of prune information,
packets will continue to be forwarded until the refresh is sent,
causing leave latency.
All outgoing-interface state that is cached is timed out after a
period equal to `3.5' times the refresh period (e.g., default of
210 seconds for the default 60 second refresh interval). As in
other multicast routing protocols, this longer timeout interval
allows individual packets to be lost without adversely affecting
the routing function. When a routing entry has no more outgoing
interfaces it is scheduled to be deleted some time later and a
prune can be sent upstream (if no prune is sent upstream the
upstream state will eventually time out anyway since no
Join/Prunes will be received to refresh the join state.)
Initially PIM messages are configured to be refreshed every 60
seconds. However, in the future a scalable timer mechanism will
be deployed in which the rate is a function of the amount of
state in a router and link bandwidth (i.e., for lower speed
links the rate will be slower and for higher speed links it may
be higher).
4.1.2 Multiple Rendezvous Points and RP failure scenarios
If only a single RP were available to be used for a multicast
group, group communication would be disrupted if the RP became
unreachable. Assigning a set of available RPs greatly increases
the robustness of the system. A small set of PIM routers within
a domain are configured to act as Candidate RPs (C-RPs), and
periodically send C-RP Advertisements to the elected BSR. At any
point in time only a single RP is active for a group. However,
when the BSR detects that a particular RP is no longer
reachable, the BSR deletes the unreachable RP(s) from the RP-Set
next distributed within the periodic Bootstrap message, and all
PIM routers within the region rehash affected groups (i.e.,
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 18]
Internet Draft PIM-SM Architecture Aug 1998
those that were previously hashed to the now-unreachable RP).
4.2 Interaction with other multicast protocols
The basic difference between traditional IP multicast routing
and PIM is that the former is completely data driven; we will
refer to traditional IP multicast routing as ``dense mode'' for
the purposes of this discussion. Four important behavioral
differences result:
* Dense mode sends and stores explicit prune state in
response to unwanted data packets. Sparse mode requires
explicit joining; the default action is to not send data
packets where they have not been requested.
* Sparse mode stores shared-tree join state in anticipation
of data packets; Dense-mode routers do not store any state
until data packets are sent (i.e. for active data sources).
The difference is not very significant for active groups
(i.e., PIM would have one additional tree active); however
for idle groups dense mode has the advantage of having no
state at all, whereas PIM would have state for the one
shared-tree.
* Sparse mode relies on the concept of an RP for data to be
delivered to receivers who request to join the group.
Dense-mode groups do not require an RP; broadcast is used
as the rendezvous mechanism.
* Sparse mode relies on periodic refreshing of explicit
Join/Prune messages. Dense mode does not need to send prune
messages periodically because of its data driven nature.
In simplified terms, the cost of dense mode is the default
broadcast behavior and maintenance of prune state, whereas the
cost of sparse mode is the need for RPs and RP-tree state for
idle groups. If all members of a group are located within a
bandwidth-rich region, the group may be supported in a strictly
dense mode using scope control. However, such groups cannot
include any members beyond the indicated scope, without imposing
broadcast and prune overhead on the larger scope needed to reach
the remote receiver. PIM is designed to address the more general
problem of groups that are not a priori limited to intra-domain
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 19]
Internet Draft PIM-SM Architecture Aug 1998
membership and may therefore span domains.
In the case of multi-access LANs, some interesting issues arise
because of possibility of parallel routers forwarding duplicate
packets onto the LAN. In SM we must be particularly careful with
the operation of the RPtree because the RPF check that prevents
routing loops is dependent on information stored in the router,
and not based on the source address found in the packet header.
As a result it is conceivable that a packet could be routed in
elaborate loops because different routers are using different
criteria for accepting the packet. To solve this problem each
router on a multi-access LAN sends Assert messages when a data
packet from a source arrives on the outgoing interface for the
associated (S,G) or the (*,G) entry. All routers listen to
Assert messages, compare the metrics included therein, and only
one router remains the forwarder for that source to that LAN.
We also wish to interoperate with networks that do not have
routers modified to generate and interpret PIM Join/Prune
messages. We have to address two functions: pulling data out to
the dense-mode cloud, and importing data into the PIM region
from a dense mode region:
* In PIM, joining a distribution tree is not passive, routers
with local members must take explicit join action to
receive data packets. This creates problems when a dense-
mode region, wishes to interoperate with PIM. To do so, one
of two things must happen:
1 Either, PMBR's on the border between PIM and dense
mode regions join to all of the PIM region's RPs to
pull out all packets generated within the PIM region.
Or,
2 The PMBR on the border of a dense mode region must
receive some indication of membership within the dense
mode cloud, and must generate PIM explicit Join/Prune
messages to pull the data down to the dense mode
cloud.
The first of these two approaches is appropriate when the
PIM region is a stub or multihomed and is connected to a
dense mode backbone. The second of these two approaches is
appropriate when the dense mode region is connecting to a
PIM backbone.
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 20]
Internet Draft PIM-SM Architecture Aug 1998
* The PMBRs at the border between PIM and dense mode regions
must act as DRs for the sources external to the PIM-SM
domain. In other words the PMBR sets up source specific
state and sends Registers on behalf of external sources.
The details of these mechanisms are described in [3][19].
4.3 Multicast service interface
The multicast interface for hosts is unchanged. Hosts need only
learn about and communicate their interest in joining to
multicast addresses.
5 Scaling and Aggregation
There are several motivations for aggregating source
information; the most important are PIM message size and the
amount of memory used for multicast routing entries.
One might consider using the highest level aggregate available
for an address when setting up the multicast routing entry. This
is optimal with respect to routing entry space. It is also
optimal with respect to PIM message size. However, PIM messages
will carry very coarse information and when the messages arrive
at routers closer to the source(s) where more specific routes
exist there will be a large fanout and PIM messages will travel
towards all members of the aggregate which would be inefficient
in most/many cases.
Traditional IP multicast routing (dense mode) does not have this
problem since prune messages can carry most fine grain
information which are triggered based on data packets. If the
prune messages are lost, subsequent data triggers the prune. On
the other hand, graft messages may be subject to the fan-out
problem. In this case, they are sent as far as the message
information takes it. The penalty is increased join latency.
If PIM is being used for inter-domain routing, and routers were
able to map from IP address to domain identifier, then one
possibility would be to use the domain level aggregate for a
source in PIM messages (Autonomous System (AS) numbers or
Routing Domain Identifiers (RDIs)). Then the PIM message would
travel to the PMBRs of the domain and the PMBRs can use the
internal multicast protocol's mechanism for propagating the join
within the domain (e.g. send appropriate link-state
advertisement in MOSPF or register a ``local member'' and do not
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 21]
Internet Draft PIM-SM Architecture Aug 1998
prune in the case of RPF). However this approach requires that
it is both possible and efficient to map from IP to domain
address when processing data packets, as well as control
packets.
We address the issues of control traffic and state scaling
separately below. The detailed mechanisms have not yet been
incorporated into the protocol specification as they are still
being designed.
5.1 Containing control traffic overhead
To control the bandwidth consumed by periodic control messages,
we adopt a technique proposed by one of the authors (Jacobson),
called scalable timers. The timers controlling periodic
refreshing of control messages are set such that the total
overhead is a small fixed percentage of the link bandwidth.
Eventually, PIM should use the scalable timer approach; this
approach was initially proposed by Van Jacobson and a detailed
design and analysis was reported in [18]. In this approach the
refresh interval is determined by the sender of the information.
The sender can adjust the frequency of control messages (and
therefore the timeout period at the control message receiver)
depending upon the amount of state that it has to communicate,
or refresh, over a particular link. It can thereby keep the
amount of control traffic to some small percentage of the link
bandwidth. In this case the receiver of the control messages may
infer the appropriate refresh interval based on measurement of
arriving control traffic, and set its timeout values
accordingly.
In the absence of more experimentation with scalable timer
mechanisms, the current PIM protocol specifies that the sender
of control messages communication hold-time values explicitly.
Therefore, a router tells its neighbors how long to keep it
reachable by advertising the holdtime in PIM-Hello messages.
Likewise, Join/Prune messages indicate how long state should be
kept. This allows the sender to change its frequency without the
receivers requiring any special configuration information.
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 22]
Internet Draft PIM-SM Architecture Aug 1998
5.2 Containing state overhead
PIM-SM maintains less source-specific state than do dense mode
protocols. The more important issue faced by all existing
multicast routing schemes is how to reduce the amount of group-
specific state. This remains an open area of investigation.
6 Conclusions
We have presented a solution to the problem of routing multicast
packets in large, wide-area internets. Our approach
(a) uses constrained, receiver-initiated, membership
advertisement for sparsely distributed multicast groups;
(b) supports both shared and shortest path tree types in one
protocol;
(c) does not depend on a particular unicast protocol; and
(d) uses soft state mechanisms to reliably and responsively
maintain multicast trees.
The architecture accommodates graceful and efficient adaptation
to varying types of multicast groups, and to different network
conditions.
7 Acknowledgments
Tony Ballardie, Scott Brim, Jon Crowcroft, Paul Francis, Lixia
Zhang and John Zwiebel provided detailed comments on previous
drafts. The authors of CBT and membership of the IDMR WG
provided many of the motivating ideas for this work and useful
feedback on design details.
References
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 23]
Internet Draft PIM-SM Architecture Aug 1998
1. J.Moy. Multicast extension to ospf.
Internet Draft, September 1992.
2. D.Waitzman S.Deering, C.Partridge. Distance vector multicast
routing protocol, nov 1988. RFC1075.
3. D.Estrin, D.Farinacci, A.Helmy, D.Thaler, S.Deering, M.Handley,
V.Jacobson, C.Liu, P.Sharma, and L.Wei. Protocol independent
multicast - sparse mode (pim-sm): Protocol specification.
Proposed Experimental RFC, September 1996.
4. D.Estrin, D.Farinacci, A.Helmy, V.Jacobson, and L.Wei. Protocol
independent multicast - dense mode (pim-dm): Protocol
specification. Proposed Experimental RFC, September 1996.
5. S.Deering and D.Cheriton. Multicast routing in datagram
internetworks and extended lans.
ACM Transactions on Computer Systems, pages 85--111, May 1990.
6. S.Deering. Multicast Routing in a Datagram Internetwork. PhD
thesis, Stanford University, 1991.
7. S.Deering. Host extensions for ip multicasting, aug 1989.
RFC1112.
8. W.Fenner. Internet group management protocol, version 2.
Internet Draft, May 1996.
9. J.Moy. Ospf version 2, oct 1991. RFC1247.
10. J.Moy. Mospf: Analysis and experience.
Internet Draft, July 1993.
11. Y.K. Dalal and R.M. Metcalfe. Reverse path forwarding of
broadcast packets.
Communications of the ACM, 21(12):1040--1048, 1978.
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 24]
Internet Draft PIM-SM Architecture Aug 1998
12. Ron Frederick. Ietf audio videocast.
Internet Society News, 1(4):19, 1993.
13. A.J. Ballardie, P.F. Francis, and J.Crowcroft. Core based trees.
In Proceedings of the ACM SIGCOMM, San Francisco, 1993.
14. David Wall. Mechanisms for Broadcast and Selective Broadcast.
PhD thesis, Stanford University, June 1980. Technical Report N0.
190.
15. L.Wei and D.Estrin. The trade-offs of multicast trees and
algorithms. In Proceedings of the 1994 international
conference on computer communications and networks, San
Francisco, September 1994.
16. S.Deering, D.Estrin, D.Farinacci, B.Fenner, V.Jacobson,
M.Handley, D.Thaler, L.Wei, and A.Helmy. Interoperability
mechanisms for pim-sm and dvmrp.
Internet Draft, January 1996.
17. D.Estrin, D.Farinacci, A.Helmy, D.Thaler, S.Deering, M.Handley,
V.Jacobson, C.Liu, P.Sharma, and L.Wei. Pim multicast border
router (pmbr) specification for connecting pim-sm domains to a
dvmrp backbone. Internet Draft, September 1996.
18. P.Sharma, D.Estrin, S.Floyd, and V.Jacobson. Scalable timers for
soft state protocols.
Infocom 97, June 1996.
Deering,Estrin,Farinacci,Handley,Helmy,Jacobson,Liu,Sharma,Thaler,Wei [Page 25]
Addresses of Authors:
Deborah Estrin
Computer Science Dept/ISI
University of Southern Calif.
Los Angeles, CA 90089
estrin@usc.edu
Dino Farinacci
Cisco Systems Inc.
170 West Tasman Drive,
San Jose, CA 95134
dino@cisco.com
Ahmed Helmy
Computer Science Dept.
University of Southern Calif.
Los Angeles, CA 90089
ahelmy@catarina.usc.edu
David Thaler
EECS Department
University of Michigan
Ann Arbor, MI 48109
thalerd@eecs.umich.edu
Stephen Deering
Xerox PARC
3333 Coyote Hill Road
Palo Alto, CA 94304
deering@parc.xerox.com
Mark Handley
Department of Computer Science
University College London
Gower Street
London, WC1E 6BT
UK
m.handley@cs.ucl.ac.uk
Van Jacobson
Lawrence Berkeley Laboratory
1 Cyclotron Road
Berkeley, CA 94720
van@ee.lbl.gov
Ching-gung Liu
Computer Science Dept.
University of Southern Calif.
Los Angeles, CA 90089
charley@catarina.usc.edu
Puneet Sharma
Computer Science Dept.
University of Southern Calif.
Los Angeles, CA 90089
puneet@catarina.usc.edu
Liming Wei
Cisco Systems Inc.
170 West Tasman Drive,
San Jose, CA 95134
lwei@cisco.com
