Request for Comments: 2362 USC
Obsoletes: 2117 D. Farinacci
Category: Experimental 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 1998
Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol
Specification
Status of this Memo
This memo defines an Experimental Protocol for the Internet
community. It does not specify an Internet standard of any kind.
Discussion and suggestions for improvement are requested.
Distribution of this memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (1998). All Rights Reserved.
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 network
layer 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 network layer 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 network layer
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 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 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 network layer 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.
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).
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 in the prune
list and the RPT-bit set.
4 Receipt of a packet at the DR from a directly connected
source S, on the subnet containing the address S, triggers a
Join/Prune message towards the RP with S in the prune list and
the RPT-bit set under the following conditions: a) there is no
matching (S,G) state, and b) there exists a (*,G) or (*,*,RP)
for which the DR is not the RP.
5 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.)
6 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 the
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.
7 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.
8 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.
aragraphFragmentation 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
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: i) if
Si is not included in the prune list, ii) if I is not on
the same subnet as the address Si, and iii) 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 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 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,