Request for Comments: 2117 USC
Category: Experimental D. Farinacci
CISCO
A. Helmy
USC
D. Thaler
UMICH
S. Deering
XEROX
M. Handley
UCL
V. Jacobson
LBL
C. Liu
USC
P. Sharma
USC
L. Wei
CISCO
June 1997
Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol
Specification
Status of This Memo
This memo defines an Experimental Protocol for the Internet
community. This memo does not specify an Internet standard of any
kind. Discussion and suggestions for improvement are requested.
Distribution of this memo is unlimited.
Acknowledgements
The author list has been reordered to reflect the involvement in
detailed editorial work on this specification document. The first
four authors are the primary editors and are listed alphabetically.
The rest of the authors, also listed alphabetically, participated in
all aspects of the architectural and detailed design but managed to
get away without hacking the latex!
1 Introduction
This document describes a protocol 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, and because it is designed to
support sparse groups as defined in [1][2]. This document describes
the protocol details. For the motivation behind the design and a
description of the architecture, see [1][2]. Section 2 summarizes
PIM-SM operation. It describes the protocol from a network
perspective, in particular, how the participating routers interact to
create and maintain the multicast distribution tree. Section 3
describes PIM-SM operations from the perspective of a single router
implementing the protocol; this section constitutes the main body of
the protocol specification. It is organized according to PIM-SM
message type; for each message type we describe its contents, its
generation, and its processing.
Sections 3.8 and 3.9 summarize the timers and flags referred to
throughout this document. Section 4 provides packet format details.
The most significant functional changes since the January '95 version
involve the Rendezvous Point-related mechanisms, several resulting
simplifications to the protocol, and removal of the PIM-DM protocol
details to a separate document [3] (for clarity).
2 PIM-SM Protocol Overview
In this section we provide an overview of the architectural
components of PIM-SM.
A router receives explicit Join/Prune messages from those neighboring
routers that have downstream group members. The router then forwards
data packets addressed to a multicast group, G, only onto those
interfaces on which explicit joins have been received. Note that all
routers mentioned in this document are assumed to be PIM-SM capable,
unless otherwise specified.
A Designated Router (DR) sends periodic Join/Prune messages toward a
group-specific Rendezvous Point (RP) for each group for which it has
active members. Each router along the path toward the RP builds a
wildcard (any-source) state for the group and sends Join/Prune
messages on toward the RP. We use the term route entry to refer to
the state maintained in a router to represent the distribution tree.
A route entry may include such fields as the source address, the
group address, the incoming interface from which packets are
accepted, the list of outgoing interfaces to which packets are sent,
timers, flag bits, etc. The wildcard route entry's incoming interface
points toward the RP; the outgoing interfaces point to the
neighboring downstream routers that have sent Join/Prune messages
toward the RP. This state creates a shared, RP-centered, distribution
tree that reaches all group members. When a data source first sends
to a group, its DR unicasts Register messages to the RP with the
source's data packets encapsulated within. If the data rate is high,
the RP can send source-specific Join/Prune messages back towards the
source and the source's data packets will follow the resulting
forwarding state and travel unencapsulated to the RP. Whether they
arrive encapsulated or natively, the RP forwards the source's
decapsulated data packets down the RP-centered distribution tree
toward group members. If the data rate warrants it, routers with
local receivers can join a source-specific, shortest path,
distribution tree, and prune this source's packets off of the shared
RP-centered tree. For low data rate sources, neither the RP, nor
last-hop routers need join a source-specific shortest path tree and
data packets can be delivered via the shared, RP-tree.
The following subsections describe SM operation in more detail, in
particular, the control messages, and the actions they trigger.
2.1 Local hosts joining a group
In order to join a multicast group, G, a host conveys its membership
information through the Internet Group Management Protocol (IGMP), as
specified in [4][5], (see figure 1). From this point on we refer to
such a host as a receiver, R, (or member) of the group G.
Note that all figures used in this section are for illustration and
are not intended to be complete. For complete and detailed protocol
action see Section 3.
[Figures are present only in the postscript version]
Fig. 1 Example: how a receiver joins, and sets up shared tree
When a DR (e.g., router A in figure 1) gets a membership indication
from IGMP for a new group, G, the DR looks up the associated RP. The
DR creates a wildcard multicast route entry for the group, referred
to here as a (*,G) entry; if there is no more specific match for a
particular source, the packet will be forwarded according to this
entry.
The RP address is included in a special field in the route entry and
is included in periodic upstream Join/Prune messages. The outgoing
interface is set to that included in the IGMP membership indication
for the new member. The incoming interface is set to the interface
used to send unicast packets to the RP.
When there are no longer directly connected members for the group,
IGMP notifies the DR. If the DR has neither local members nor
downstream receivers, the (*,G) state is deleted.
2.2 Establishing the RP-rooted shared tree
Triggered by the (*,G) state, the DR creates a Join/Prune message
with the RP address in its join list and the the wildcard bit (WC-
bit) and RP-tree bit (RPT-bit) set to 1. The WC-bit indicates that
any source may match and be forwarded according to this entry if
there is no longer match; the RPT-bit indicates that this join is
being sent up the shared, RP-tree. The prune list is left empty. When
the RPT-bit is set to 1 it indicates that the join is associated with
the shared RP-tree and therefore the Join/Prune message is propagated
along the RP-tree. When the WC-bit is set to 1 it indicates that the
address is an RP and the downstream receivers expect to receive
packets from all sources via this (shared tree) path. The term RPT-
bit is used to refer to both the RPT-bit flags associated with route
entries, and the RPT-bit included in each encoded address in a
Join/Prune message.
Each upstream router creates or updates its multicast route entry for
(*,G) when it receives a Join/Prune with the RPT-bit and WC-bit set.
The interface on which the Join/Prune message arrived is added to the
list of outgoing interfaces (oifs) for (*,G). Based on this entry
each upstream router between the receiver and the RP sends a
Join/Prune message in which the join list includes the RP. The packet
payload contains Multicast-Address=G, Join=RP,WC-bit,RPT-bit,
Prune=NULL.
2.3 Hosts sending to a group
When a host starts sending multicast data packets to a group,
initially its DR must deliver each packet to the RP for distribution
down the RP-tree (see figure 2). The sender's DR initially
encapsulates each data packet in a Register message and unicasts it
to the RP for that group. The RP decapsulates each Register message
and forwards the enclosed data packet natively to downstream members
on the shared RP-tree.
[Figures are present only in the postscript version]
Fig. 2 Example: a host sending to a group
If the data rate of the source warrants the use of a source-specific
shortest path tree (SPT), the RP may construct a new multicast route
entry that is specific to the source, hereafter referred to as (S,G)
state, and send periodic Join/Prune messages toward the source. Note
that over time, the rules for when to switch can be modified without
global coordination. When and if the RP does switch to the SPT, the
routers between the source and the RP build and maintain (S,G) state
in response to these messages and send (S,G) messages upstream toward
the source.
The source's DR must stop encapsulating data packets in Registers
when (and so long as) it receives Register-Stop messages from the RP.
The RP triggers Register-Stop messages in response to Registers, if
the RP has no downstream receivers for the group (or for that
particular source), or if the RP has already joined the (S,G) tree
and is receiving the data packets natively. Each source's DR
maintains, per (S,G), a Register-Suppression-timer. The Register-
Suppression-timer is started by the Register-Stop message; upon
expiration, the source's DR resumes sending data packets to the RP,
encapsulated in Register messages.
2.4 Switching from shared tree (RP-tree) to shortest path tree (SP-
tree)
A router with directly-connected members first joins the shared RP-
tree. The router can switch to a source's shortest path tree (SP-
tree) after receiving packets from that source over the shared RP-
tree. The recommended policy is to initiate the switch to the SP-tree
after receiving a significant number of data packets during a
specified time interval from a particular source. To realize this
policy the router can monitor data packets from sources for which it
has no source-specific multicast route entry and initiate such an
entry when the data rate exceeds the configured threshold. As shown
in figure 3, router `A' initiates a (S,G) state.
[Figures are present only in the postscript version]
Fig. 3 Example: Switching from shared tree to shortest path tree
When a (S,G) entry is activated (and periodically so long as the
state exists), a Join/Prune message is sent upstream towards the
source, S, with S in the join list. The payload contains Multicast-
Address=G, Join=S, Prune=NULL. When the (S,G) entry is created, the
outgoing interface list is copied from (*,G), i.e., all local shared
tree branches are replicated in the new shortest path tree. In this
way when a data packet from S arrives and matches on this entry, all
receivers will continue to receive the source's packets along this
path. (In more complicated scenarios, other entries in the router
have to be considered, as described in Section 3). Note that (S,G)
state must be maintained in each last-hop router that is responsible
for initiating and maintaining an SP-tree. Even when (*,G) and (S,G)
overlap, both states are needed to trigger the source-specific
Join/Prune messages. (S,G) state is kept alive by data packets
arriving from that source. A timer, Entry-timer, is set for the (S,G)
entry and this timer is restarted whenever data packets for (S,G) are
forwarded out at least one oif, or Registers are sent. When the
Entry-timer expires, the state is deleted. The last-hop router is the
router that delivers the packets to their ultimate end-system
destination. This is the router that monitors if there is group
membership and joins or prunes the appropriate distribution trees in
response. In general the last-hop router is the Designated Router
(DR) for the LAN. However, under various conditions described later,
a parallel router connected to the same LAN may take over as the
last-hop router in place of the DR.
Only the RP and routers with local members can initiate switching to
the SP-tree; intermediate routers do not. Consequently, last-hop
routers create (S,G) state in response to data packets from the
source, S; whereas intermediate routers only create (S,G) state in
response to Join/Prune messages from downstream that have S in the
Join list.
The (S,G) entry is initialized with the SPT-bit cleared, indicating
that the shortest path tree branch from S has not yet been setup
completely, and the router can still accept packets from S that
arrive on the (*,G) entry's indicated incoming interface (iif). Each
PIM multicast entry has an associated incoming interface on which
packets are expected to arrive.
When a router with a (S,G) entry and a cleared SPT-bit starts to
receive packets from the new source S on the iif for the (S,G) entry,
and that iif differs from the (*,G) entry's iif, the router sets the
SPT-bit, and sends a Join/Prune message towards the RP, indicating
that the router no longer wants to receive packets from S via the
shared RP-tree. The Join/Prune message sent towards the RP includes S
in the prune list, with the RPT-bit set indicating that S's packets
must not be forwarded down this branch of the shared tree. If the
router receiving the Join/Prune message has (S,G) state (with or
without the route entry's RPT-bit flag set), it deletes the arriving
interface from the (S,G) oif list. If the router has only (*,G)
state, it creates an entry with the RPT-bit flag set to 1. For
brevity we refer to an (S,G) entry that has the RPT-bit flag set to 1
as an (S,G)RPT-bit entry. This notational distinction is useful to
point out the different actions taken for (S,G) entries depending on
the setting of the RPT-bit flag. Note that a router can have no more
than one active (S,G) entry for any particular S and G, at any
particular time; whether the RPT-bit flag is set or not. In other
words, a router never has both an (S,G) and an (S,G)RPT-bit entry for
the same S and G at the same time. The Join/Prune message payload
contains Multicast-Address=G, Join=NULL, Prune=S,RPT-bit.
A new receiver may join an existing RP-tree on which source-specific
prune state has been established (e.g., because downstream receivers
have switched to SP-trees). In this case the prune state must be
eradicated upstream of the new receiver to bring all sources' data
packets down to the new receiver. Therefore, when a (*,G) Join
arrives at a router that has any (Si,G)RPT-bit entries (i.e., entries
that cause the router to send source-specific prunes toward the RP),
these entries must be updated upstream of the router so as to bring
all sources' packets down to the new member. To accomplish this, each
router that receives a (*,G) Join/Prune message updates all existing
(S,G)RPT-bit entries. The router may also trigger a (*,G) Join/Prune
message upstream to cause the same updating of RPT-bit settings
upstream and pull down all active sources' packets. If the arriving
(*,G) join has some sources included in its prune list, then the
corresponding (S,G)RPT-bit entries are left unchanged (i.e., the
RPT-bit remains set and no oif is added).
2.5 Steady state maintenance of distribution tree (i.e., router state)
In the steady state each router sends periodic Join/Prune messages
for each active PIM route entry; the Join/Prune messages are sent to
the neighbor indicated in the corresponding entry. These messages are
sent periodically to capture state, topology, and membership changes.
A Join/Prune message is also sent on an event-triggered basis each
time a new route entry is established for some new source (note that
some damping function may be applied, e.g., a short delay to allow
for merging of new Join information). Join/Prune messages do not
elicit any form of explicit acknowledgment; routers recover from lost
packets using the periodic refresh mechanism.
2.6 Obtaining RP information
To obtain the RP information, all routers within a PIM domain collect
Bootstrap messages. Bootstrap messages are sent hop-by-hop within the
domain; the domain's bootstrap router (BSR) is responsible for
originating the Bootstrap messages. Bootstrap messages are used to
carry out a dynamic BSR election when needed and to distribute RP
information in steady state.
A domain in this context is a contiguous set of routers that all
implement PIM and are configured to operate within a common boundary
defined by PIM Multicast Border Routers (PMBRs). PMBRs connect each
PIM domain to the rest of the internet.
Routers use a set of available RPs (called the {RP-Set}) distributed
in Bootstrap messages to get the proper Group to RP mapping. The
following paragraphs summarize the mechanism; details of the
mechanism may be found in Sections 3.6 and Appendix 6.2. A (small)
set of routers, within a domain, are configured as candidate BSRs
and, through a simple election mechanism, a single BSR is selected
for that domain. A set of routers within a domain are also configured
as candidate RPs (C-RPs); typically these will be the same routers
that are configured as C-BSRs. Candidate RPs periodically unicast
Candidate-RP-Advertisement messages (C-RP-Advs) to the BSR of that
domain. C-RP-Advs include the address of the advertising C-RP, as
well as an optional group address and a mask length field, indicating
the group prefix(es) for which the candidacy is advertised. The BSR
then includes a set of these Candidate-RPs (the RP-Set), along with
the corresponding group prefixes, in Bootstrap messages it
periodically originates. Bootstrap messages are distributed hop-by-
hop throughout the domain.
Routers receive and store Bootstrap messages originated by the BSR.
When a DR gets a membership indication from IGMP for (or a data
packet from) a directly connected host, for a group for which it has
no entry, the DR uses a hash function to map the group address to one
of the C-RPs whose Group-prefix includes the group (see Section 3.7).
The DR then sends a Join/Prune message towards (or unicasts Registers
to) that RP.
The Bootstrap message indicates liveness of the RPs included therein.
If an RP is included in the message, then it is tagged as `up' at the
routers; while RPs not included in the message are removed from the
list of RPs over which the hash algorithm acts. Each router continues
to use the contents of the most recently received Bootstrap message
until it receives a new Bootstrap message.
If a PIM domain partitions, each area separated from the old BSR will
elect its own BSR, which will distribute an RP-Set containing RPs
that are reachable within that partition. When the partition heals,
another election will occur automatically and only one of the BSRs
will continue to send out Bootstrap messages. As is expected at the
time of a partition or healing, some disruption in packet delivery
may occur. This time will be on the order of the region's round-trip
time and the bootstrap router timeout value.
2.7 Interoperation with dense mode protocols such as DVMRP
In order to interoperate with networks that run dense-mode,
{broadcast and prune}, protocols, such as DVMRP, all packets
generated within a PIM-SM region must be pulled out to that region's
PIM Multicast Border Routers (PMBRs) and injected (i.e., broadcast)
into the DVMRP network. A PMBR is a router that sits at the boundary
of a PIM-SM domain and interoperates with other types of multicast
routers such as those that run DVMRP. Generally a PMBR would speak
both protocols and implement interoperability functions not required
by regular PIM routers. To support interoperability, a special entry
type, referred to as (*,*,RP), must be supported by all PIM routers.
For this reason we include details about (*,*,RP) entry handling in
this general PIM specification.
A data packet will match on a (*,*,RP) entry if there is no more
specific entry (such as (S,G) or (*,G)) and the destination group
address in the packet maps to the RP listed in the (*,*,RP) entry. In
this sense, a (*,*,RP) entry represents an aggregation of all the
groups that hash to that RP. PMBRs initialize (*,*,RP) state for each
RP in the domain's RPset. The (*,*,RP) state causes the PMBRs to send
(*,*,RP) Join/Prune messages toward each of the active RPs in the
domain. As a result distribution trees are built that carry all data
packets originated within the PIM domain (and sent to the RPs) down
to the PMBRs.
PMBRs are also responsible for delivering externally-generated
packets to routers within the PIM domain. To do so, PMBRs initially
encapsulate externally-originated packets (i.e., received on DVMRP
interfaces) in Register messages and unicast them to the
corresponding RP within the PIM domain. The Register message has a
bit indicating that it was originated by a border router and the RP
caches the originating PMBR's address in the route entry so that
duplicate Registers from other PMBRs can be declined with a
Register-Stop message.
All PIM routers must be capable of supporting (*,*,RP) state and
interpreting associated Join/Prune messages. We describe the handling
of (*,*,RP) entries and messages throughout this document; however,
detailed PIM Multicast Border Router (PMBR) functions will be
specified in a separate interoperability document (see directory,
http://catarina.usc.edu/pim/interop/).
2.8 Multicast data packet processing
Data packets are processed in a manner similar to other multicast
schemes. A router first performs a longest match on the source and
group address in the data packet. A (S,G) entry is matched first if
one exists; a (*,G) entry is matched otherwise. If neither state
exists, then a (*,*,RP) entry match is attempted as follows: the
router hashes on G to identify the RP for group G, and looks for a
(*,*,RP) entry that has this RP address associated with it. If none
of the above exists, then the packet is dropped. If a state is
matched, the router compares the interface on which the packet
arrived to the incoming interface field in the matched route entry.
If the iif check fails the packet is dropped, otherwise the packet is
forwarded to all interfaces listed in the outgoing interface list.
Some special actions are needed to deliver packets continuously while
switching from the shared to shortest-path tree. In particular, when
a (S,G) entry is matched, incoming packets are forwarded as follows:
1 If the SPT-bit is set, then:
1 if the incoming interface is the same as a matching
(S,G) iif, the packet is forwarded to the oif-list of
(S,G).
2 if the incoming interface is different than a matching
(S,G) iif , the packet is discarded.
2 If the SPT-bit is cleared, then:
1 if the incoming interface is the same as a matching
(S,G) iif, the packet is forwarded to the oif-list of
(S,G). In addition, the SPT bit is set for that entry
if the incoming interface differs from the incoming
interface of the (*,G) or (*,*,RP) entry.
2 if the incoming interface is different than a matching
(S,G) iif, the incoming interface is tested against a
matching (*,G) or (*,*,RP) entry. If the iif is the
same as one of those, the packet is forwarded to the
oif-list of the matching entry.
3 Otherwise the iif does not match any entry for G and
the packet is discarded.
Data packets never trigger prunes. However, data packets may trigger
actions that in turn trigger prunes. For example, when router B in
figure 3 decides to switch to SP-tree at step 3, it creates a (S,G)
entry with SPT-bit set to 0. When data packets from S arrive at
interface 2 of B, B sets the SPT-bit to 1 since the iif for (*,G) is
different than that for (S,G). This triggers the sending of prunes
towards the RP.
2.9 Operation over Multi-access Networks
This section describes a few additional protocol mechanisms needed to
operate PIM over multi-access networks: Designated Router election,
Assert messages to resolve parallel paths, and the Join/Prune-
Suppression-Timer to suppress redundant Joins on multi-access
networks.
* Designated router election
When there are multiple routers connected to a multi-access network,
one of them must be chosen to operate as the designated router (DR)
at any point in time. The DR is responsible for sending triggered
Join/Prune and Register messages toward the RP.
A simple designated router (DR) election mechanism is used for both
SM and traditional IP multicast routing. Neighboring routers send
Hello messages to each other. The sender with the largest IP address
assumes the role of DR. Each router connected to the multi-access LAN
sends the Hellos periodically in order to adapt to changes in router
status.
* Parallel paths to a source or the RP--Assert process
If a router receives a multicast datagram on a multi-access LAN from
a source whose corresponding (S,G) outgoing interface list includes
the interface to that LAN, the packet must be a duplicate. In this
case a single forwarder must be elected. Using Assert messages
addressed to `224.0.0.13' (ALL-PIM-ROUTERS group) on the LAN,
upstream routers can resolve which one will act as the forwarder.
Downstream routers listen to the Asserts so they know which one was
elected, and therefore where to send subsequent Joins. Typically this
is the same as the downstream router's RPF (Reverse Path Forwarding)
neighbor; but there are circumstances where this might not be the
case, e.g., when using multiple unicast routing protocols on that
LAN. The RPF neighbor for a particular source (or RP) is the next-hop
router to which packets are forwarded en route to that source (or
RP); and therefore is considered a good path via which to accept
packets from that source.
The upstream router elected is the one that has the shortest distance
to the source. Therefore, when a packet is received on an outgoing
interface a router sends an Assert message on the multi-access LAN
indicating what metric it uses to reach the source of the data
packet. The router with the smallest numerical metric (with ties
broken by highest address) will become the forwarder. All other
upstream routers will delete the interface from their outgoing
interface list. The downstream routers also do the comparison in case
the forwarder is different than the RPF neighbor.
Associated with the metric is a metric preference value. This is
provided to deal with the case where the upstream routers may run
different unicast routing protocols. The numerically smaller metric
preference is always preferred. The metric preference is treated as
the high-order part of an assert metric comparison. Therefore, a
metric value can be compared with another metric value provided both
metric preferences are the same. A metric preference can be assigned
per unicast routing protocol and needs to be consistent for all
routers on the multi-access network.
Asserts are also needed for (*,G) entries since an RP-Tree and an
SP-Tree for the same group may both cross the same multi- access
network. When an assert is sent for a (*,G) entry, the first bit in
the metric preference (RPT-bit) is always set to 1 to indicate that
this path corresponds to the RP tree, and that the match must be done
on (*,G) if it exists. Furthermore, the RPT-bit is always cleared for
metric preferences that refer to SP-tree entries; this causes an SP-
tree path to always look better than an RP-tree path. When the SP-
tree and RPtree cross the same LAN, this mechanism eliminates the
duplicates that would otherwise be carried over the LAN.
In case the packet, or the Assert message, matches on oif for
(*,*,RP) entry, a (*,G) entry is created, and asserts take place as
if the matching state were (*,G).
The DR may lose the (*,G) Assert process to another router on the LAN
if there are multiple paths to the RP through the LAN. From then on,
the DR is no longer the last-hop router for local receivers and
removes the LAN from its (*,G) oif list. The winning router becomes
the last-hop router and is responsible for sending (*,G) join
messages to the RP.
* Join/Prune suppression
Join/Prune suppression may be used on multi-access LANs to reduce
duplicate control message overhead; it is not required for correct
performance of the protocol. If a Join/Prune message arrives and
matches on the incoming interface for an existing (S,G), (*,G), or
(*,*,RP) route entry, and the Holdtime included in the Join/Prune
message is greater than the recipient's own [Join/Prune-Holdtime]
(with ties resolved in favor of the higher IP address), a timer (the
Join/Prune-Suppression-timer) in the recipient's route entry may be
started to suppress further Join/Prune messages. After this timer
expires, the recipient triggers a Join/Prune message, and resumes
sending periodic Join/Prunes, for this entry. The Join/Prune-
Suppression-timer should be restarted each time a Join/Prune message
is received with a higher Holdtime.
2.10 Unicast Routing Changes
When unicast routing changes, an RPF check is done on all active
(S,G), (*,G) and (*,*,RP) entries, and all affected expected incoming
interfaces are updated. In particular, if the new incoming interface
appears in the outgoing interface list, it is deleted from the
outgoing interface list. The previous incoming interface may be added
to the outgoing interface list by a subsequent Join/Prune from
downstream. Join/Prune messages received on the current incoming
interface are ignored. Join/Prune messages received on new
interfaces or existing outgoing interfaces are not ignored. Other
outgoing interfaces are left as is until they are explicitly pruned
by downstream routers or are timed out due to lack of appropriate
Join/Prune messages. If the router has a (S,G) entry with the SPT-bit
set, and the updated iif(S,G) does not differ from iif(*,G) or
iif(*,*,RP), then the router resets the SPT-bit.
The router must send a Join/Prune message with S in the Join list out
any new incoming interfaces to inform upstream routers that it
expects multicast datagrams over the interface. It may also send a
Join/Prune message with S in the Prune list out the old incoming
interface, if the link is operational, to inform upstream routers
that this part of the distribution tree is going away.
2.11 PIM-SM for Inter-Domain Multicast
Future documents will address the use of PIM-SM as a backbone inter-
domain multicast routing protocol. Design choices center primarily
around the distribution and usage of RP information for wide area,
inter-domain groups.
2.12 Security
All PIM control messages may use IPsec [6] to address security
concerns. Security mechanisms are likely to be enhanced in the near
future.
3 Detailed Protocol Description
This section describes the protocol operations from the perspective
of an individual router implementation. In particular, for each
message type we describe how it is generated and processed.
3.1 Hello
Hello messages are sent so neighboring routers can discover each
other.
3.1.1 Sending Hellos
Hello messages are sent periodically between PIM neighbors, every
[Hello-Period] seconds. This informs routers what interfaces have
PIM neighbors. Hello messages are multicast using address 224.0.0.13
(ALL-PIM-ROUTERS group). The packet includes a Holdtime, set to
[Hello-Holdtime], for neighbors to keep the information valid.
Hellos are sent on all types of communication links.
3.1.2 Receiving Hellos
When a router receives a Hello message, it stores the IP address for
that neighbor, sets its Neighbor-timer for the Hello sender to the
Holdtime included in the Hello, and determines the Designated Router
(DR) for that interface. The highest IP addressed system is elected
DR. Each Hello received causes the DR's address to be updated.
When a router that is the active DR receives a Hello from a new
neighbor (i.e., from an IP address that is not yet in the DRs
neighbor table), the DR unicasts its most recent RP-set information
to the new neighbor.
3.1.3 Timing out neighbor entries
A periodic process is run to time out PIM neighbors that have not
sent Hellos. If the DR has gone down, a new DR is chosen by scanning
all neighbors on the interface and selecting the new DR to be the one
with the highest IP address. If an interface has gone down, the
router may optionally time out all PIM neighbors associated with the
interface.
3.2 Join/Prune
Join/Prune messages are sent to join or prune a branch off of the
multicast distribution tree. A single message contains both a join
and prune list, either one of which may be null. Each list contains
a set of source addresses, indicating the source- specific trees or
shared tree that the router wants to join or prune.
3.2.1 Sending Join/Prune Messages
Join/Prune messages are merged such that a message sent to a
particular upstream neighbor, N, includes all of the current joined
and pruned sources that are reached via N; according to unicast
routing Join/Prune messages are multicast to all routers on multi-
access networks with the target address set to the next hop router
towards S or RP. Join/Prune messages are sent every [Join/Prune-
Period] seconds. In the future we will introduce mechanisms to rate-
limit this control traffic on a hop by hop basis, in order to avoid
excessive overhead on small links. In addition, certain events cause
triggered Join/Prune messages to be sent.
3.2.1.1 Periodic Join/Prune Messages
A router sends a periodic Join/Prune message to each distinct RPF
neighbor associated with each (S,G), (*,G) and (*,*,RP) entry.
Join/Prune messages are only sent if the RPF neighbor is a PIM
neighbor. A periodic Join/Prune message sent to a particular RPF
neighbor is constructed as follows:
1 Each router determines the RP for a (*,G) entry by using
the hash function described. The RP address (with RPT and
WC bits set) is included in the join list of a periodic
Join/Prune message under the following conditions:
1 The Join/Prune message is being sent to the RPF
neighbor toward the RP for an active (*,G) or (*,*,RP)
entry, and
2 The outgoing interface list in the (*,G) or (*,*,RP)
entry is non-NULL, or the router is the DR on the same
interface as the RPF neighbor.
2 A particular source address, S, is included in the join
list with the RPT and WC bits cleared under the following
conditions:
1 The Join/Prune message is being sent to the RPF
neighbor toward S, and
2 There exists an active (S,G) entry with the RPT-bit
flag cleared, and
3 The oif list in the (S,G) entry is not null.
3 A particular source address, S, is included in the prune
list with the RPT and WC bits cleared under the following
conditions:
1 The Join/Prune message is being sent to the RPF
neighbor toward S, and
2 There exists an active (S,G) entry with the RPT-bit
flag cleared, and
3 The oif list in the (S,G) entry is null.
4 A particular source address, S, is included in the prune
list with the RPT-bit set and the WC bit cleared under the
following conditions:
1 The Join/Prune message is being sent to the RPF
neighbor toward the RP and there exists a (S,G) entry
with the RPT-bit flag set and null oif list, or
2 The Join/Prune message is being sent to the RPF
neighbor toward the RP, there exists a (S,G) entry
with the RPT-bit flag cleared and SPT-bit set, and the
incoming interface toward S is different than the
incoming interface toward the RP, or
3 The Join/Prune message is being sent to the RPF
neighbor toward the RP, and there exists a (*,G) entry
and (S,G) entry for a directly connected source.
5 The RP address (with RPT and WC bits set) is included in
the prune list if:
1 The Join/Prune message is being sent to the RPF
neighbor toward the RP and there exists a (*,G) entry
with a null oif list (see Section 3.5.2).
3.2.1.2 Triggered Join/Prune Messages
In addition to periodic messages, the following events will trigger
Join/Prune messages if as a result, a) a new entry is created, or b)
the oif list changes from null to non-null or non-null to null. The
contents of triggered messages are the same as the periodic,
described above.
1 Receipt of an indication from IGMP that the state of
directly-connected- membership has changed (i.e., new members
have just joined `membership indication' or all members have
left), for a group G, may cause the last-hop router to build
or modify corresponding (*,G) state. When IGMP indicates
that there are no longer directly connected members, the oif
is removed from the oif list if the oif- timer is not
running. A Join/Prune message is triggered if and only if
a) a new entry is created, or b) the oif list changes from
null to non-null or non-null to null, as follows :
1 If the receiving router does not have a route entry
for G the router creates a (*,G) entry, copies the
oif list from the corresponding (*,*,RP) entry
(if it exists), and includes the interface included
in the IGMP membership indication in the oif list;
as always, the router never includes the entry's iif
in the oif list. The router sends a Join/Prune
message towards the RP with the RP address and RPT-bit
and WC-bits set in the join list. Or,
2 If a (S,G)RPT-bit or (*,G) entry already exists, the
interface included in the IGMP membership indication
is added to the oif list (if it was not included already).
2 Receipt of a Join/Prune message for (S,G), (*,G) or (*,*,RP)
will cause building or modifying corresponding state, and
subsequent triggering of upstream Join/Prune messages, in the
following cases:
1 When there is no current route entry, the RP address
included in the Join/Prune message is checked against
the local RP-Set information. If it matches, an entry
will be created and the new entry will in turn trigger
an upstream Join/Prune message. If the router has no
RP-Set information it may discard the message, or
optionally use the RP address included in the message.
2 When the outgoing interface list of an (S,G)RPT-bit
entry becomes null, the triggered Join/Prune message
will contain S in the prune list.
3 When there exists a (S,G)RPT-bit with null oif list,
and an (*,G) Join/Prune message is received, the
arriving interface is added to the oif list and a (*,G)
Join/Prune message is triggered upstream.
4 When there exists a (*,G) with null oif list, and a
(*,*,RP) Join/Prune message is received, the receiving
interface is added to the oif list and a (*,*,RP)
Join/Prune message is triggered upstream.
3 Receipt of a packet that matches on a (S,G) entry whose
SPT-bit is cleared triggers the following if the packet
arrived on the correct incoming interface and there is a
(*,G) or (*,*,RP) entry with a different incoming
interface: a) the router sets the SPT-bit on the (S,G)
entry, and b) the router sends a Join/Prune message
towards the RP with S and a set RPT-bit in the prune list.
4 When a Join/Prune message is received for a group G, the
prune list is checked. If the prune list contains a source
or RP for which the receiving router has a corresponding
active (S,G), (*,G) or (*,*,RP) entry, and whose iif is
that on which the Join/Prune was received, then a join for
(S,G), (*,G) or (*,*,RP) is triggered to override the prune,
respectively. (This is necessary in the case of parallel
downstream routers connected to a multi-access network.)
5 When the RP fails, the RP will not be included in the
Bootstrap messages sent to all routers in that domain.
This triggers the DRs to send (*,G) Join/Prune messages
towards new RP for the group, as determined by the RP-Set
and the hash function. As described earlier, PMBRs trigger
(*,*,RP) joins towards each RP in the RP-Set.
6 When an entry's Join/Prune-Suppression timer expires, a
Join/Prune message is triggered upstream corresponding to
that entry, even if the outgoing interface has not
transitioned between null and non-null states.
7 When the RPF neighbor changes (whether due to an Assert or
changes in unicast routing), the router sets a random delay
timer (the Random-Delay-Join-Timer) whose expiration triggers
sending of a Join/Prune message for the asserted route entry
to the Assert winner (if the Join/Prune Suppression timer has
expired.)
We do not trigger prunes onto interfaces based on data packets. Data
packets that arrive on the wrong incoming interface are silently
dropped. However, on point-to-point interfaces triggered prunes may
be sent as an optimization.
3.2.1.3 Fragmentation: It is possible that a Join/Prune message
constructed according to the preceding rules could exceed the MTU of
a network. In this case, the message can undergo semantic
fragmentation whereby information corresponding to different groups
can be sent in different messages. However, if a Join/Prune message
must be fragmented the complete prune list corresponding to a group G
must be included in the same Join/Prune message as the associated
RP-tree Join for G. If such semantic fragmentation is not possible,
IP fragmentation should be used between the two neighboring hops.
3.2.2 Receiving Join/Prune Messages When a router receives a
Join/Prune message, it processes it as follows.
The receiver of the Join/Prune notes the interface on which the PIM
message arrived, call it I. The receiver then checks to see if the
Join/Prune message was addressed to the receiving router itself
(i.e., the router's address appears in the Unicast Upstream Neighbor
Router field of the Join/Prune message). (If the router is connected
to a multiaccess LAN, the message could be intended for a different
router.) If the Join/Prune is for this router the following actions
are taken.
For each group address G, in the Join/Prune message, the associated
join list is processed as follows. We refer to each address in the
join list as Sj; Sj refers to the RP if the RPT- bit and WC-bit are
both set. For each Sj in the join list of the Join/Prune message:
1 If an address, Sj, in the join list of the Join/Prune
message has the RPT-bit and WC-bit set, then Sj is the RP
address used by the downstream router(s) and the following
actions are taken:
1 If Sj is not the same as the receiving router's RP
mapping for G, the receiving router may ignore the
Join/Prune message with respect to that group entry.
If the router does not have any RP-Set information, it
may use the address Sj included in the Join/Prune
message as the RP for the group.
2 If Sj is the same as the receiving router's RP mapping
for G, the receiving router adds I to the outgoing
interface list of the (*,G) route entry (if there is
no (*,G) entry, the router creates one first) and sets
the Oif-timer for that interface to the Holdtime
specified in the Join/Prune message. In addition, the
Oif-Deletion-Delay for that interface is set to 1/3rd
the Holdtime specified in the Join/Prune message.
If a (*,*,RP) entry exists, for the RP associated with
G, then the oif list of the newly created (*,G) entry
is copied from that (*,*,RP) entry.
3 For each (Si,G) entry associated with group G, if Si
is not included in the prune list, and if I is not the
iif then interface I is added to the oif list and the
Oif-timer for that interface in each affected entry
is increased (never decreased) to the Holdtime included
in the Join/Prune message. In addition, if the
Oif-timer for that interface is increased, the
Oif-Deletion-Delay for that interface is set to 1/3rd
the Holdtime specified in the Join/Prune message.
If the group address in the Join/Prune message is `*'
then every (*,G) and (S,G) entry, whose group address
hashes to the RP indicated in the (*,*,RP) Join/Prune
message, is updated accordingly. A `*' in the group
field of the Join/Prune is represented by a group
address 224.0.0.0 and a group mask length of 4,
indicating a (*,*,RP) Join.
4 If the (Si,G) entry has its RPT-bit flag set to 1, and
its oif list is the same as the (*,G) oif list, then
the (Si,G)RPT-bit entry is deleted,
5 The incoming interface is set to the interface used to
send unicast packets to the RP in the (*,G) route
entry, i.e., RPF interface toward the RP.
2 For each address, Sj, in the join list whose RPT-bit and
WC-bit are not set, and for which there is no existing (Sj,G)
route entry, the router initiates one. The router creates a
(S,G) entry and copies all outgoing interfaces from the
(S,G)RPT-bit entry, if it exists. If there is no (S,G) entry,
the oif list is copied from the (*,G) entry; and if there is
no (*,G) entry, the oif list is copied from the (*,*,RP)
entry, if it exists. In all cases, the iif of the (S,G)
entry is always excluded from the oif list.
1 The outgoing interface for (Sj,G) is set to I. The
incoming interface for (Sj,G) is set to the interface
used to send unicast packets to Sj (i.e., the RPF
neighbor).
2 If the interface used to reach Sj, is the same as I,
this represents an error (or a unicast routing change)
and the Join/Prune must not be processed.
3 For each address, Sj, in the join list of the Join/Prune
message, for which there is an existing (Sj,G) route entry,
1 If the RPT-bit is not set for Sj listed in the
Join/Prune message, but the RPT-bit flag is set on the
existing (Sj,G) entry, the router clears the RPT-bit
flag on the (Sj,G) entry, sets the incoming interface
to point towards Sj for that (Sj,G) entry, and sends a
Join/Prune message corresponding to that entry through
the new incoming interface; and
2 If I is not the same as the existing incoming
interface, the router adds I to the list of outgoing
interfaces.
3 The Oif-timer for I is increased (never decreased)
to the Holdtime included in the Join/Prune message.
In addition, if the Oif-timer for that interface is
increased, the Oif-Deletion-Delay for that interface
is set to 1/3rd the Holdtime specified in the
Join/Prune message.
4 The (Sj,G) entry's SPT bit is cleared until data comes
down the shortest path tree.
For each group address G, in the Join/Prune message, the associated
prune list is processed as follows. We refer to each address in the
prune list as Sp; Sp refers to the RP if the RPT-bit and WC-bit are
both set. For each Sp in the prune list of the Join/Prune message:
1 For each address, Sp, in the prune list whose RPT-bit and
WC-bit are cleared:
1 If there is an existing (Sp,G) route entry, the router
lowers the Oif-timer for I to its Oif-Deletion-Delay,
allowing for other downstream routers on a multi-
access LAN to override the prune. However, on point-
to-point links, the oif-timer is expired immediately.
2 If the router has a current (*,G), or (*,*,RP), route
entry, and if the existing (Sp,G) entry has its RPT-
bit flag set to 1, then this (Sp,G)RPT-bit entry is
maintained (not deleted) even if its outgoing
interface list is null.
2 For each address, Sp, in the prune list whose RPT-bit is
set and whose WC-bit cleared:
1 If there is an existing (Sp,G) route entry, the router
lowers the entry's Oif-timer for I to its
Oif-Deletion-Delay, allowing for other downstream
routers on a multi- access LAN to override the prune.
However, on point-to-point links, the oif-timer is
expired immediately.
2 If the router has a current (*,G), or (*,*,RP), route
entry, and if the existing (Sp,G) entry has its
RPT- bit flag set to 1, then this (Sp,G)RPT-bit entry
is not deleted, and the Entry-timer is restarted, even
if its outgoing interface list is null.
3 If (*,G), or corresponding (*,*,RP), state exists, but
there is no (Sp,G) entry, an (Sp,G)RPT-bit entry is
created. The outgoing interface list is copied from the
(*,G), or (*,*,RP), entry, with the interface, I, on
which the prune was received, is deleted. Packets from
the pruned source, Sp, match on this state and are not
forwarded toward the pruned receivers.