The author list has been reordered to reflect the involvement
detailed editorial work on this specificationdocument. The
four authors are the primary editors and are listed alphabetically
The rest of the authors, also listed alphabetically, participated
all aspects of the architectural and detailed design but managed
get away without hacking the latex
Sections 3.8 and 3.9 summarize the timers and flags referred
throughout this document. Section 4 provides packet format details
The most significantfunctional changes since the January '95
involve the Rendezvous Point-related mechanisms, several
simplifications to the protocol, and removal of the PIM-DM
details to a separatedocument [3] (for clarity).
A Designated Router (DR) sends periodic Join/Prune messages toward
group-specific Rendezvous Point (RP) for each group for which it
active members. Each router along the path toward the RP builds wildcard (any-source) state for the group and sends Join/ messages on toward the RP. We use the term route entry to refer
the state maintained in a router to represent the distribution tree
A route entry may include such fields as the source address,
group address, the incominginterface from which packets accepted, the list of outgoing interfaces to which packets are sent
timers, flag bits, etc. The wildcard route entry's incoming
points toward the RP; the outgoing interfaces point to
neighboring downstream routers that have sent Join/Prune
toward the RP. This state creates a shared, RP-centered,
tree that reaches all group members. When a data source first
to a group, its DR unicasts Registermessages to the RP with
source's data packets encapsulated within. If the data rate is high
the RP can send source-specific Join/Prune messages back towards
source and the source's data packets will follow the forwarding state and travel unencapsulated to the RP. Whether
arrive encapsulated or natively, the RP forwards the source'
decapsulated data packets down the RP-centered distribution
toward group members. If the data rate warrants it, routers
local receivers can join a source-specific, shortest path distribution tree, and prune this source's packets off of the
RP-centered tree. For low data rate sources, neither the RP,
last-hop routers need join a source-specificshortest path tree
data packets can be delivered via the shared, RP-tree
Note that all figures used in this section are for illustration
are not intended to be complete. For complete and detailed
action see Section 3.
[Figures are present only in the postscript version
Fig. 1 Example: how a receiver joins, and sets up shared
When a DR (e.g., router A in figure 1) gets a membership
from IGMP for a new group, G, the DR looks up the associated RP.
DR creates a wildcardmulticast route entry for the group,
to here as a (*,G) entry; if there is no more specific match for particular source, the packet will be forwarded according to
entry
When there are no longer directly connected members for the group
IGMP notifies the DR. If the DR has neither local members downstream receivers, the (*,G) state is deleted
2.2 Establishing the RP-rooted shared
Triggered by the (*,G) state, the DR creates a Join/Prune
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
any source may match and be forwarded according to this entry
there is no longer match; the RPT-bit indicates that this join
being sent up the shared, RP-tree. The prune list is left empty.
the RPT-bit is set to 1 it indicates that the join is associated
the shared RP-tree and therefore the Join/Prune message is
along the RP-tree. When the WC-bit is set to 1 it indicates that
address is an RP and the downstream receivers expect to
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
entries, and the RPT-bit included in each encoded address in
Join/Prune message
Each upstream router creates or updates its multicast route entry
(*,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
list of outgoing interfaces (oifs) for (*,G). Based on this
each upstream router between the receiver and the RP sends
Join/Prune message in which the join list includes the RP. The
payload containsMulticast-Address=G, Join=RP,WC-bit,RPT-bit
Prune=NULL
2.3 Hosts sending to a
When a host starts sending multicast data packets to a group
initially its DR must deliver each packet to the RP for
down the RP-tree (see figure 2). The sender's DR
encapsulates each data packet in a Register message and unicasts
to the RP for that group. The RP decapsulates each Register
and forwards the enclosed data packet natively to downstream
on the shared RP-tree
[Figures are present only in the postscript version
Fig. 2 Example: a host sending to a
If the data rate of the source warrants the use of a source- shortest path tree (SPT), the RP may construct a new multicast
entry that is specific to the source, hereafter referred to as (S,G
state, and send periodic Join/Prune messages toward the source.
that over time, the rules for when to switch can be modified
global coordination. When and if the RP does switch to the SPT,
routers between the source and the RP build and maintain (S,G)
in response to these messages and send (S,G) messagesupstream
the source
The source's DR must stop encapsulating data packets in
when (and so long as) it receivesRegister-Stop messages from the RP
The RP triggers Register-Stop messages in response to Registers,
the RP has no downstream receivers for the group (or for particular source), or if the RP has already joined the (S,G)
and is receiving the data packets natively. Each source's
maintains, per (S,G), a Register-Suppression-timer. The Register
Suppression-timer is started by the Register-Stop message;
expiration, the source's DR resumes sending data packets to the RP encapsulated in Registermessages
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-
after receiving a significant number of data packets during specified time interval from a particular source. To realize
policy the router can monitor data packets from sources for which
has no source-specificmulticast route entry and initiate such
entry when the data rate exceeds the configuredthreshold. As
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
When a (S,G) entry is activated (and periodically so long as
state exists), a Join/Prune message is sent upstream towards
source, S, with S in the join list. The payload containsMulticast
Address=G, Join=S, Prune=NULL. When the (S,G) entry is created, outgoinginterface list is copied from (*,G), i.e., all local
tree branches are replicated in the new shortest path tree. In
way when a data packet from S arrives and matches on this entry,
receivers will continue to receive the source's packets along
path. (In more complicated scenarios, other entries in the
have to be considered, as described in Section 3). Note that (S,G
state must be maintained in each last-hop router that is
for initiating and maintaining an SP-tree. Even when (*,G) and (S,G
overlap, both states are needed to trigger the source-
Join/Prune messages. (S,G) state is kept alive by data
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)
forwarded out at least one oif, or Registers are sent. When
Entry-timer expires, the state is deleted. The last-hop router is
router that delivers the packets to their ultimate end- destination. This is the router that monitors if there is membership and joins or prunes the appropriatedistribution trees response. In general the last-hop router is the Designated
(DR) for the LAN. However, under various conditions described later
a parallel router connected to the same LAN may take over as
last-hop router in place of the DR
Only the RP and routers with local members can initiate switching
the SP-tree; intermediate routers do not. Consequently, last-
routers create (S,G) state in response to data packets from
source, S; whereas intermediate routers only create (S,G) state response to Join/Prune messages from downstream that have S in
Join list
The (S,G) entry is initialized with the SPT-bit cleared,
that the shortest path tree branch from S has not yet been
completely, and the router can still accept packets from S
arrive on the (*,G) entry's indicatedincominginterface (iif).
PIM multicast entry has an associatedincominginterface on
packets are expected to arrive
When a router with a (S,G) entry and a cleared SPT-bit starts
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
SPT-bit, and sends a Join/Prune message towards the RP,
that the router no longer wants to receive packets from S via
shared RP-tree. The Join/Prune message sent towards the RP includes
in the prune list, with the RPT-bit set indicating that S's
must not be forwarded down this branch of the shared tree. If
router receiving the Join/Prune message has (S,G) state (with
without the route entry's RPT-bit flag set), it deletes the 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.
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
point out the different actions taken for (S,G) entries depending
the setting of the RPT-bit flag. Note that a router can have no
than one active (S,G) entry for any particular S and G, at particular time; whether the RPT-bit flag is set or not. In
words, a router never has both an (S,G) and an (S,G)RPT-bit entry
the same S and G at the same time. The Join/Prune message containsMulticast-Address=G, Join=NULL, Prune=S,RPT-bit
A new receiver may join an existing RP-tree on which source-
prune state has been established (e.g., because downstream
have switched to SP-trees). In this case the prune state must
eradicated upstream of the new receiver to bring all sources'
packets down to the new receiver. Therefore, when a (*,G)
arrives at a router that has any (Si,G)RPT-bit entries (i.e.,
that cause the router to send source-specific prunes toward the RP),
these entries must be updated upstream of the router so as to
all sources' packets down to the new member. To accomplish this,
router that receives a (*,G) Join/Prune message updates all
(S,G)RPT-bit entries. The router may also trigger a (*,G) Join/
message upstream to cause the same updating of RPT-bit upstream and pull down all active sources' packets. If the
(*,G) join has some sources included in its prune list, then corresponding (S,G)RPT-bit entries are left unchanged (i.e.,
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
for each active PIM route entry; the Join/Prune messages are sent
the neighborindicated in the corresponding entry. These messages
sent periodically to capture state, topology, and membership changes
A Join/Prune message is also sent on an event-triggered basis
time a new route entry is established for some new source (note
some damping function may be applied, e.g., a short delay to
for merging of new Join information). Join/Prune messages do
elicit any form of explicitacknowledgment; routers recover from
packets using the periodic refresh mechanism
A domain in this context is a contiguous set of routers that implement PIM and are configured to operate within a common
defined by PIM Multicast Border Routers (PMBRs). PMBRs connect
PIM domain to the rest of the internet
Routers receive and store Bootstrapmessages originated by the BSR
When a DR gets a membershipindication from IGMP for (or a
packet from) a directly connected host, for a group for which it
no entry, the DR uses a hash function to map the group address to
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
to) that RP
If a PIM domain partitions, each area separated from the old BSR
elect its own BSR, which will distribute an RP-Set containing
that are reachable within that partition. When the partition heals
another election will occur automatically and only one of the
will continue to send out Bootstrapmessages. As is expected at
time of a partition or healing, some disruption in packet
may occur. This time will be on the order of the region's round-
time and the bootstrap router timeout value
In order to interoperate with networks that run dense-mode
{broadcast and prune}, protocols, such as DVMRP, all generated within a PIM-SM region must be pulled out to that region'
PIM Multicast Border Routers (PMBRs) and injected (i.e., broadcast
into the DVMRP network. A PMBR is a router that sits at the
of a PIM-SM domain and interoperates with other types of
routers such as those that run DVMRP. Generally a PMBR would
both protocols and implementinteroperability functions not
by regular PIM routers. To support interoperability, a special
type, referred to as (*,*,RP), must be supported by all PIM routers
For this reason we include details about (*,*,RP) entry handling
this general PIM specification
A data packet will match on a (*,*,RP) entry if there is no specific entry (such as (S,G) or (*,G)) and the destination
address in the packet maps to the RP listed in the (*,*,RP) entry.
this sense, a (*,*,RP) entry represents an aggregation of all
groups that hash to that RP. PMBRs initialize (*,*,RP) state for
RP in the domain's RPset. The (*,*,RP) state causes the PMBRs to
(*,*,RP) Join/Prune messages toward each of the active RPs in
domain. As a result distribution trees are built that carry all
packets originated within the PIM domain (and sent to the RPs)
to the PMBRs
PMBRs are also responsible for delivering externally-
packets to routers within the PIM domain. To do so, PMBRs encapsulate externally-originated packets (i.e., received on
interfaces) in Registermessages and unicast them to corresponding RP within the PIM domain. The Register message has
bit indicating that it was originated by a border router and the
caches the originating PMBR's address in the route entry so duplicate Registers from other PMBRs can be declined with Register-Stop message
Data packets are processed in a manner similar to other
schemes. A router first performs a longest match on the source
group address in the data packet. A (S,G) entry is matched first
one exists; a (*,G) entry is matched otherwise. If neither
exists, then a (*,*,RP) entry match is attempted as follows:
router hashes on G to identify the RP for group G, and looks for
(*,*,RP) entry that has this RP address associated with it. If
of the above exists, then the packet is dropped. If a state
matched, the router compares the interface on which the
arrived to the incominginterface field in the matched route entry
If the iif check fails the packet is dropped, otherwise the packet
forwarded to all interfaces listed in the outgoinginterface list
Some special actions are needed to deliver packets continuously switching from the shared to shortest-path tree. In particular,
a (S,G) entry is matched, incoming packets are forwarded as follows
1 If the SPT-bit is set, then
1 if the incominginterface is the same as a
(S,G) iif, the packet is forwarded to the oif-list
(S,G).
1 if the incominginterface is the same as a
(S,G) iif, the packet is forwarded to the oif-list
(S,G). In addition, the SPT bit is set for that
if the incominginterface differs from the interface of the (*,G) or (*,*,RP) entry
3 Otherwise the iif does not match any entry for G
the packet is discarded
Data packets never trigger prunes. However, data packets may
actions that in turn trigger prunes. For example, when router B
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
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
Join/Prune and Registermessages toward the RP
A simple designated router (DR) electionmechanism is used for
SM and traditional IP multicast routing. Neighboring routers
Hello messages to each other. The sender with the largest IP
assumes the role of DR. Each router connected to the multi-access
sends the Hellos periodically in order to adapt to changes in
status
* Parallel paths to a source or the RP--Assert
If a router receives a multicastdatagram on a multi-access LAN
a source whose corresponding (S,G) outgoinginterface list
the interface to that LAN, the packet must be a duplicate. In
case a single forwarder must be elected. Using Assert 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
elected, and therefore where to send subsequent Joins. Typically
is the same as the downstream router's RPF (Reverse Path Forwarding neighbor; but there are circumstances where this might not be
case, e.g., when using multiple unicast routing protocols on
LAN. The RPF neighbor for a particular source (or RP) is the next-
router to which packets are forwarded en route to that source (
RP); and therefore is considered a good path via which to
packets from that source
The upstream router elected is the one that has the shortest
to the source. Therefore, when a packet is received on an interface a router sends an Assert message on the multi-access indicating what metric it uses to reach the source of the
Associated with the metric is a metric preference value. This provided to deal with the case where the upstream routers may different unicast routing protocols. The numerically smaller preference is always preferred. The metric preference is treated
the high-order part of an assert metric comparison. Therefore,
metric value can be compared with another metric value provided
metric preferences are the same. A metric preference can be
per unicast routing protocol and needs to be consistent for
routers on the multi-access network
Asserts are also needed for (*,G) entries since an RP-Tree and
SP-Tree for the same group may both cross the same multi-
network. When an assert is sent for a (*,G) entry, the first bit
the metric preference (RPT-bit) is always set to 1 to indicate
this path corresponds to the RP tree, and that the match must be
on (*,G) if it exists. Furthermore, the RPT-bit is always cleared
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
duplicates that would otherwise be carried over the LAN
In case the packet, or the Assert message, matches on oif
(*,*,RP) entry, a (*,G) entry is created, and asserts take place
if the matching state were (*,G).
The DR may lose the (*,G) Assert process to another router on the
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
removes the LAN from its (*,G) oif list. The winning router
the last-hop router and is responsible for sending (*,G) messages to the RP
* Join/Prune
Join/Prune suppression may be used on multi-access LANs to duplicate control message overhead; it is not required for performance of the protocol. If a Join/Prune message arrives
matches on the incominginterface for an existing (S,G), (*,G),
(*,*,RP) route entry, and the Holdtimeincluded in the Join/
message is greater than the recipient's own [Join/Prune-Holdtime
(with ties resolved in favor of the higher IP address), a timer (
Join/Prune-Suppression-timer) in the recipient's route entry may
started to suppress further Join/Prune messages. After this
expires, the recipient triggers a Join/Prune message, and
sending periodic Join/Prunes, for this entry. The Join/Prune
Suppression-timer should be restarted each time a Join/Prune
is received with a higher Holdtime
The router must send a Join/Prune message with S in the Join list
any new incoming interfaces to inform upstream routers that
expects multicast datagrams over the interface. It may also send
Join/Prune message with S in the Prune list out the old interface, if the link is operational, to inform upstream
that this part of the distribution tree is going away
2.11 PIM-SM for Inter-Domain
Future documents will address the use of PIM-SM as a backbone inter
domain multicast routing protocol. Design choices center
around the distribution and usage of RP information for wide area
inter-domain groups
2.12
All PIM control messages may use IPsec [6] to address
concerns. Security mechanisms are likely to be enhanced in the
future
Hello messages are sent so neighboring routers can discover
other
3.1.1 Sending
Hello messages are sent periodically between PIM neighbors,
[Hello-Period] seconds. This informs routers what interfaces
PIM neighbors. Hello messages are multicast using address 224.0.0.13
(ALL-PIM-ROUTERS group). The packet includes a Holdtime, set
[Hello-Holdtime], for neighbors to keep the information valid
Hellos are sent on all types of communication links
When a router receives a Hello message, it stores the IP address
that neighbor, sets its Neighbor-timer for the Hello sender to Holdtimeincluded in the Hello, and determines the Designated
(DR) for that interface. The highest IP addressed system is
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 neighbor (i.e., from an IP address that is not yet in the neighbor table), the DR unicasts its most recent RP-set
to the new neighbor
A periodic process is run to time out PIM neighbors that have
sent Hellos. If the DR has gone down, a new DR is chosen by
all neighbors on the interface and selecting the new DR to be the
with the highest IP address. If an interface has gone down,
router may optionally time out all PIM neighbors associated with interface
3.2 Join/
Join/Prune messages are sent to join or prune a branch off of multicastdistribution tree. A single message contains both a
and prune list, either one of which may be null. Each list
a set of source addresses, indicating the source- specific trees
shared tree that the router wants to join or prune
and pruned sources that are reached via N; according to
routing Join/Prune messages are multicast to all routers on multi
access networks with the target address set to the next hop
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
excessive overhead on small links. In addition, certain events triggered Join/Prune messages to be sent
3.2.1.1 Periodic Join/Prune
A router sends a periodic Join/Prune message to each distinct neighborassociated with each (S,G), (*,G) and (*,*,RP) entry
Join/Prune messages are only sent if the RPF neighbor is a neighbor. A periodic Join/Prune message sent to a particular neighbor is constructed as follows
1 Each router determines the RP for a (*,G) entry by
the hash functiondescribed. The RP address (with RPT
WC bits set) is included in the join list of a
Join/Prune message under the following conditions
1 The Join/Prune message is being sent to the neighbor toward the RP for an active (*,G) or (*,*,RP
entry,
2 There exists an active (S,G) entry with the RPT-
flag cleared,
3 The oif list in the (S,G) entry is null
4 A particular source address, S, is included in the
list with the RPT-bit set and the WC bit cleared under following conditions
1 The Join/Prune message is being sent to the neighbor toward the RP and there exists a (S,G)
with the RPT-bit flag set and null oif list,
2 The Join/Prune message is being sent to the neighbor toward the RP, there exists a (S,G)
with the RPT-bit flag cleared and SPT-bit set, and incominginterface toward S is different than incominginterface toward the RP,
3 The Join/Prune message is being sent to the neighbor toward the RP, and there exists a (*,G)
and (S,G) entry for a directly connected source
5 The RP address (with RPT and WC bits set) is included
the prune list if
1 The Join/Prune message is being sent to the neighbor toward the RP and there exists a (*,G)
with a null oif list (see Section 3.5.2).
1 Receipt of an indication from IGMP that the state
directly-connected- membership has changed (i.e., new
have just joined `membershipindication' or all members
left), for a group G, may cause the last-hop router to
or modify corresponding (*,G) state. When IGMP
that there are no longer directly connected members, the
is removed from the oif list if the oif- timer is
running. A Join/Prune message is triggered if and only
a) a new entry is created, or b) the oif list changes
null to non-null or non-null to null, as follows :
1 If the receiving router does not have a route
for G the router creates a (*,G) entry, copies
oif list from the corresponding (*,*,RP)
(if it exists), and includes the interface
in the IGMP membershipindication in the oif list
as always, the router never includes the entry's
in the oif list. The router sends a Join/
message towards the RP with the RP address and RPT-
and WC-bits set in the join list. Or
2 If a (S,G)RPT-bit or (*,G) entry already exists, interfaceincluded in the IGMP membership
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,
subsequent triggering of upstream Join/Prune messages, in following cases
1 When there is no current route entry, the RP included in the Join/Prune message is checked
the local RP-Set information. If it matches, an
will be created and the new entry will in turn
an upstream Join/Prune message. If the router has
RP-Set information it may discard the message,
optionally use the RP address included in the message
2 When the outgoinginterface list of an (S,G)RPT-
entry becomes null, the triggered Join/Prune
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,
arriving interface is added to the oif list and a (*,G
Join/Prune message is triggeredupstream
4 When there exists a (*,G) with null oif list, and
(*,*,RP) Join/Prune message is received, the interface is added to the oif list and a (*,*,RP
Join/Prune message is triggeredupstream
3 Receipt of a packet that matches on a (S,G) entry
SPT-bit is cleared triggers the following if the
arrived on the correct incominginterface and there is
(*,G) or (*,*,RP) entry with a different interface: a) the router sets the SPT-bit on the (S,G
entry, and b) the router sends a Join/Prune
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,
prune list is checked. If the prune list contains a
or RP for which the receiving router has a
active (S,G), (*,G) or (*,*,RP) entry, and whose iif
that on which the Join/Prune was received, then a join
(S,G), (*,G) or (*,*,RP) is triggered to override the prune
respectively. (This is necessary in the case of downstream routers connected to a multi-access network.)
5 When the RP fails, the RP will not be included in Bootstrapmessages sent to all routers in that domain
This triggers the DRs to send (*,G) Join/Prune
towards new RP for the group, as determined by the RP-
and the hash function. As described earlier, PMBRs
(*,*,RP) joins towards each RP in the RP-Set
6 When an entry's Join/Prune-Suppression timer expires,
Join/Prune message is triggeredupstreamcorresponding
that entry, even if the outgoinginterface has
transitioned between null and non-null states
7 When the RPF neighbor changes (whether due to an Assert
changes in unicast routing), the router sets a random
timer (the Random-Delay-Join-Timer) whose expiration
sending of a Join/Prune message for the asserted route
to the Assert winner (if the Join/Prune Suppression timer
expired.)
We do not trigger prunes onto interfaces based on data packets.
packets that arrive on the wrong incominginterface are
dropped. However, on point-to-point interfaces triggered prunes
be sent as an optimization
3.2.1.3 Fragmentation: It is possible that a Join/Prune
constructed according to the preceding rules could exceed the MTU
a network. In this case, the message can undergo
fragmentation whereby informationcorresponding to different
can be sent in differentmessages. However, if a Join/Prune
must be fragmented the complete prune list corresponding to a group
must be included in the same Join/Prune message as the
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
message arrived, call it I. The receiver then checks to see if
Join/Prune message was addressed to the receiving router
(i.e., the router's address appears in the Unicast Upstream
Router field of the Join/Prune message). (If the router is
to a multiaccess LAN, the message could be intended for a
router.) If the Join/Prune is for this router the following
are taken
For each group address G, in the Join/Prune message, the
join list is processed as follows. We refer to each address in
join list as Sj; Sj refers to the RP if the RPT- bit and WC-bit
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/
message has the RPT-bit and WC-bit set, then Sj is the
address used by the downstream router(s) and the
actions are taken
1 If Sj is not the same as the receiving router's
mapping for G, the receiving router may ignore
Join/Prune message with respect to that group entry
If the router does not have any RP-Set information,
may use the address Sj included in the Join/
message as the RP for the group
2 If Sj is the same as the receiving router's RP
for G, the receiving router adds I to the interface list of the (*,G) route entry (if there
no (*,G) entry, the router creates one first) and
the Oif-timer for that interface to the specified in the Join/Prune message. In addition,
Oif-Deletion-Delay for that interface is set to 1/3
the Holdtimespecified in the Join/Prune message
If a (*,*,RP) entry exists, for the RP associated
G, then the oif list of the newly created (*,G)
is copied from that (*,*,RP) entry
3 For each (Si,G) entry associated with group G, if
is not included in the prune list, and if I is not
iif then interface I is added to the oif list and
Oif-timer for that interface in each affected
is increased (never decreased) to the Holdtime
in the Join/Prune message. In addition, if
If the group address in the Join/Prune message is `*'
then every (*,G) and (S,G) entry, whose group
hashes to the RP indicated in the (*,*,RP) Join/
message, is updated accordingly. A `*' in the
field of the Join/Prune is represented by a
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,
its oif list is the same as the (*,G) oif list,
the (Si,G)RPT-bit entry is deleted
2 For each address, Sj, in the join list whose RPT-bit
WC-bit are not set, and for which there is no existing (Sj,G
route entry, the router initiates one. The router creates
(S,G) entry and copies all outgoing interfaces from
(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
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
3 For each address, Sj, in the join list of the Join/
message, for which there is an existing (Sj,G) route entry
1 If the RPT-bit is not set for Sj listed in
Join/Prune message, but the RPT-bit flag is set on existing (Sj,G) entry, the router clears the RPT-
flag on the (Sj,G) entry, sets the incoming
to point towards Sj for that (Sj,G) entry, and sends
Join/Prune message corresponding to that entry
the new incominginterface;
2 If I is not the same as the existing interface, the router adds I to the list of
interfaces
3 The Oif-timer for I is increased (never decreased
to the Holdtimeincluded in the Join/Prune message
In addition, if the Oif-timer for that interface
increased, the Oif-Deletion-Delay for that
is set to 1/3rd the Holdtimespecified in
Join/Prune message
4 The (Sj,G) entry's SPT bit is cleared until data
down the shortest path tree
For each group address G, in the Join/Prune message, the
prune list is processed as follows. We refer to each address in
prune list as Sp; Sp refers to the RP if the RPT-bit and WC-bit
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
WC-bit are cleared
1 If there is an existing (Sp,G) route entry, the
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),
entry, and if the existing (Sp,G) entry has its RPT
bit flag set to 1, then this (Sp,G)RPT-bit entry
maintained (not deleted) even if its interface list is null
2 For each address, Sp, in the prune list whose RPT-bit
set and whose WC-bit cleared
1 If there is an existing (Sp,G) route entry, the
lowers the entry's Oif-timer for I to
Oif-Deletion-Delay, allowing for other
routers on a multi- access LAN to override the prune
However, on point-to-point links, the oif-timer
expired immediately
2 If the router has a current (*,G), or (*,*,RP),
entry, and if the existing (Sp,G) entry has
RPT- bit flag set to 1, then this (Sp,G)RPT-bit
is not deleted, and the Entry-timer is restarted,
if its outgoinginterface list is null
3 If (*,G), or corresponding (*,*,RP), state exists,
there is no (Sp,G) entry, an (Sp,G)RPT-bit entry
created. The outgoinginterface list is copied from
(*,G), or (*,*,RP), entry, with the interface, I,
which the prune was received, is deleted. Packets
the pruned source, Sp, match on this state and are
forwarded toward the pruned receivers
4 If there exists a (Sp,G) entry, with or without
RPT-bit set, the oif-timer for I is expired, and
Entry-timer is restarted
3 For each address, Sp, in the prune list whose RPT-bit
WC-bit are both set
1 If there is an existing (*,G) entry, with Sp as the
for G, the router lowers the entry's Oif-timer for
to its Oif-Deletion-Delay, allowing for downstream routers on a multi-access LAN to override
prune. However, on point-to-point links, the oif-
is expired immediately
2 If the corresponding (*,*,RP) state exists, but
is no (*,G) entry, a (*,G) entry is created. outgoinginterface list is copied from (*,*,RP) entry
with the interface, I, on which the prune received, deleted
For any new (S,G), (*,G) or (*,*,RP) entry created by incoming Join/Prune message, the SPT-bit is cleared (and if
Join/Prune-Suppression timer is used, it is left off.)
If the entry has a Join/Prune-Suppression timer associated with it
and if the received Join/Prune does not indicate the router as
target, then the receiving router examines the join and prune
to see if any addresses in the list `completely- match'
(S,G), (*,G), or (*,*,RP) state for which the receiving currentlyschedules Join/Prune messages. An element on the join
prune list `completely-matches' a route entry only if both the addresses and RPT-bit flag are the same. If the incoming Join/
message completely matches an existing (S,G), (*,G), or (*,*,RP
entry and the Join/Prune arrived on the iif for that entry, then
router compares the Holdtimeincluded in the Join/Prune message,
its own [Join/Prune-Holdtime]. If its own [Join/Prune-Holdtime]
lower, the Join/Prune-Suppression-timer is started at
[Join/Prune-Suppression-Timeout]. If the [Join/Prune-Holdtime]
equal, the tie is resolved in favor of the Join/Prune originator that has the higher IP address. When the Join/Prune
expires, the router triggers a Join/Prune message for corresponding entry(ies).
When a source first starts sending to a group its packets encapsulated in Registermessages and sent to the RP. If the
rate warrants source-specific paths, the RP sets up source
state and starts sending (S,G) Join/Prune messages toward the source
with S in the join list
1 When a DR receives a packet from a directly
source,
1 If there is no corresponding (S,G) entry, and
router has RP-Set information, the DR creates one
the Register-Suppression-timer turned off and the
address set according to the hash function mapping
the corresponding group. The oif list is copied existing (*,G) or (*,*,RP) entries, if they exist.
iif of the (S,G) entry is always excluded from the
list
When a PMBR (e.g., a router that connects the PIM-SM region
a dense mode region running DVMRP or PIM-DM) receives a
from a source in the dense mode region, the router treats
packet as if it were from a directly connected source. separatedocument will describe the details interoperability
2 If the new or previously-existing (S,G) entry's Register
Suppression-timer is not running, the data packet encapsulated in a Register message and unicast to the
for that group. The data packet is also forwarded
to (S,G) state in the DR if the oif list is not null;
a receiver may join the SP-tree while the DR is
registering to the RP
3 If the (S,G) entry's Register-Suppression-timer is running
the data packet is not sent in a Register message, it
just forwarded according to the (S,G) oif list
When the DR receives a Register-Stop message, it restarts Register-Suppression-timer in the corresponding (S,G) entry(ies)
[Register-Suppression-Timeout] seconds. If there is data to registered, the DR may send a null Register (a Register message
a zero-length data portion in the inner IP packet) to the RP
[Probe-Time] seconds before the Register- Suppression-timer expires
to avoid sending occasional bursts of traffic to an RP unnecessarily
1 Decapsulates the data packet, and checks for corresponding (S,G) entry
1 If a (S,G) entry with cleared (0) SPT bit exists,
the receivedRegister does not have the Null Register-Bit set to 1, the packet is forwarded;
the SPT bit is left cleared (0). If the SPT bit is 1,
the packet is dropped, and Register-Stop messages triggered. Register-Stops should be rate-limited (
an implementation-specific manner) so that no
than a few are sent per round trip time. This
a high datarate stream of packets from triggering
large number of Register-Stop messages between
time that the first packet is received and the
when the source receives the first Register-Stop
2 If there is no (S,G) entry, but there is a (*,G
entry, and the receivedRegister does not have
Null-Register-Bit set to 1, the packet is according to the (*,G) entry
3 If there is a (*,*,RP) entry but no (*,G) entry,
the Registerreceived does not have the Null Register-Bit set to 1, a (*,G) or (S,G) entry
created and the oif list is copied from the (*,*,RP
entry to the new entry. The packet is according to the created entry
1 If there is no matching (S,G) state, but
exists (*,G) or (*,*,RP) entry, the RP creates
(S,G) entry, with a `PMBR' field. This
holds the source of the Register (i.e. the
IP address of the register packet). The
triggers a (S,G) join towards the source of
data packet, and clears the SPT bit for the (S,G
entry. If the receivedRegister is not a ` Register' the packet is forwarded according
the created state. Else
2 If the `PMBR' field for the corresponding (S,G
entry matches the source of the Register packet
and the receivedRegister is not a ` Register', the decapsulated packet is
to the oif list of that entry. Else
3 If the `PMBR' field for the corresponding (S,G
entry matches the source of the Register packet
the decapsulated packet is forwarded to the
list of that entry,
The (S,G) Entry-timer is restarted by Registers arriving
that source to that group
2 If the matching (S,G) or (*,G) state contains a null
list, the RP unicasts a Register-Stop message to the
of the Register message; in the latter case, the source
address field, within the Register-Stop message, is set
the wildcard value (all 0's). This message is not
by intermediate routers, hence no (S,G) state
constructed between the RP and the source
3 If the Register message arrival rate warrants it and
is no existing (S,G) entry, the RP sets up a (S,G)
entry with the outgoinginterface list, excluding iif(S,G),
copied from the (*,G) outgoinginterface list, its SPT-
is initialized to 0. If a (*,G) entry does not exist,
there exists a (*,*,RP) entry with the RP corresponding
G , the oif list for (S,G) is copied -excluding the iif
from that (*,*,RP) entry
A timer (Entry-timer) is set for the (S,G) entry and
timer is restarted by receipt of data packets for (S,G).
The (S,G) entry causes the RP to send a Join/Prune
for the indicated group towards the source of the
message
If the (S,G) oif list becomes null, Join/Prune
will not be sent towards the source, S
1 Lookup route state based on a longest match of the
address, and an exact match of the destination address
the data packet. If neither S, nor G, find a longest
entry, and the RP for the packet's destination
address has a corresponding (*,*,RP) entry, then
longest match does not require an exact match on destination group address. In summary, the longest match
performed in the following order: (1) (S,G), (2) (*,G).
neither is matched, then a lookup is performed on (*,*,RP
entries
2 If the packet arrived on the interface found in matching-entry's iif field, and the oif list is
null
1 Forward the packet to the oif list for that
and restart the Entry-timer if the matching entry
(S,G). Optionally, the (S,G) Entry-timer may
restarted by periodic checking of the matching
count
2 If the entry is a (S,G) entry with a cleared SPT-bit
and a (*,G) or associated (*,*,RP) also exists incominginterface is different than that for (S,G),
set the SPT-bit for the (S,G) entry and trigger
(S,G) RPT-bit prune towards the RP
3 If the source of the packet is a directly-
host and the router is the DR on the interface, check the Register-Suppression- associated with the (S,G) entry. If it is not running
then the router encapsulates the data packet in register message and sends it to the RP
This covers the common case of a packet arriving on the interface to the source or RP and being forwarded to
joined branches. It also detects when packets arrive on
SP-tree, and triggers their pruning from the RP-tree. If
is the DR for the source, it sends data encapsulated in Registers to the RPs
3 If the packet matches to an entry but did not arrive on interface found in the entry's iif field, check
SPT-bit of the entry. If the SPT-bit is set, drop
packet. If the SPT-bit is cleared, then lookup the (*,G),
or (*,*,RP), entry for G. If the packet arrived on
iif found in (*,G), or the corresponding (*,*,RP),
forward the packet to the oif list of the
entry. This covers the case when a data packet matches on
(S,G) entry for which the SP-tree has not yet
completely established upstream
4 If the packet does not match any entry, but the source
the data packet is a local, directly-connected host,
the router is the DR on a multi-access LAN and has RP- information, the DR uses the hash function to determine
RP associated with the destination group, G. The DR
a (S,G) entry, with the Register-Suppression-timer
running, encapsulates the data packet in a Register
and unicasts it to the RP
5 If the packet does not match to any entry, and it is not
local host or the router is not the DR, drop the packet
One proposed example is to do so based on data rate. For example
when a (*,G), or corresponding (*,*,RP), entry is created, a data
counter may be initiated at the last-hop routers. The counter
incremented with every data packet received for directly
members of an SM group, if the longest match is (*,G) or (*,*,RP).
and when the data rate for the group exceeds a certain threshold (t1), the router initiates `source-specific' data
counters for the following data packets. Then, each counter for
source, is incremented when packets matching on (*,G), or (*,*,RP),
are received from that source. If the data rate from the
source exceeds a configuredthreshold (t2), a (S,G) entry is
and a Join/Prune message is sent towards the source. If the interface for (S,G) is not the same as that for (*,G) -or (*,*,RP),
then the SPT-bit is cleared in the (S,G) entry
Other configured rules may be enforced to cause or
establishment of (S,G) state
3.5
Asserts are used to resolve which of the parallel routers connected
a multi-access LAN is responsible for forwarding packets onto the LAN
1 Do unicast routing table lookup on source IP address
data packet, and send assert on interface "I" for
IP address in data packet; include metric preference
routing protocol and metric from routing table lookup
2 If route is not found, use metric preference of 0x7
and metric 0xffffffff
When an assert is sent for a (*,G) entry, the first bit in
metric preference (the RPT-bit) is set to 1, indicating the
packet is routed down the RP-tree
Asserts should be rate-limited in an implementation-
manner
When an Assert is received the router performs a longest match on
source and group address in the Assert message. The router checks
first bit of the metric preference (RPT-bit).
1 If the RPT-bit is set, the router first does a match
(*,G), or (*,*,RP), entries; if no matching entry is found
it ignores the Assert
2 If the RPT-bit is not set in the Assert, the router
does a match on (S,G) entries; if no matching entry
found, the router matches (*,G) or (*,*,RP) entries
If the interface that received the Assert message is in the oif
of the matched entry, then this Assert is processed by this router
follows
1 If the Assert's RPT-bit is set and the matching entry
(*,*,RP), the router creates a (*,G) entry. If the Assert'
RPT-bit is cleared and the matching entry is (*,G),
(*,*,RP), the router creates a (S,G)RPT-bit entry
Otherwise, no new entry is created in response to
Assert
2 The router then compares the metric values received in
Assert with the metric values associated with the
entry. The RPT-bit and metric preference (in that order
are treated as the high-order part of an Assert comparison. If the value in the Assert is less than
router's value (with ties broken by the IP address,
higher IP address wins), delete the interface from
entry. When the deletion occurs for a (*,G) or (*,*,RP
entry , the interface is also deleted from any
(S,G)RPT-bit or (*,G) entries, respectively. The Entry
timer for the affected entries is restarted
The winning router sends an Assert message containing its own
to that outgoinginterface. This will cause other routers on the
to prune that interface from their route entries. The winning
sets the RPT-bit in the Assert message if a (*,G) or (S,G)RPT-
entry was matched
If the Assert arrived on the incominginterface of an existing (S,G),
(*,G), or (*,*,RP) entry, the Assert is processed as follows. If
Assert message does not match the entry, exactly, it is ignored; i.e
longest-match is not used in this case. If the Assert message
match exactly, then
1 Downstream routers will select the upstream router with
smallest metric preference and metric as their neighbor. If two metrics are the same, the highest
address is chosen to break the tie. This is important
that downstream routers send subsequent Joins/Prunes (
SM) to the correct neighbor. An Assert-timer is
when changing the RPF neighbor to the Assert winner.
the timer expires, the router resets its RPF according to its unicast routing tables to capture
dynamics and router failures
2 If the downstream routers have downstream members, and
the Assert caused the RPF neighbor to change, downstream routers must trigger a Join/Prune message
inform the upstream router that packets are to be
on the multi-access network
Candidate-RP-Advertisements (C-RP-Advs) are periodic PIM
unicast to the BSR by those routers that are configured Candidate-RPs (C-RPs).
Bootstrapmessages are periodic PIM messages originated by Bootstrap router (BSR) within a domain, and forwarded hop-by-hop distribute the current RP-set to all routers in that domain
C-RPs periodically unicast C-RP-Advs to the BSR for that domain. interval for sending these messages is subject to local
at the C-RP
Candidate-RP-Advertisements carry group address and group
fields. This enables the advertising router to limit advertisement to certain prefixes or scopes of groups. advertising router may enforce this scope acceptance when
Registers or Join/Prune messages. C-RPs should send C-RP- messages with the Authoritative bit cleared
1 If the router is not the elected BSR, it ignores
message,
2 The BSR adds the RP address to its local pool of
RPs, according to the associated group prefix(es) in
C-RP-Adv message. The Holdtime in the C-RP-Adv message
also stored with the corresponding RP, to be included
in the Bootstrap message. The BSR may apply a
policy to limit the number of Candidate RPs
in the Bootstrap message. The BSR may override the indicated in a C-RP-Adv unless the Authoritative bit in
C-RP-Adv is set
The BSR keeps an RP-timer per RP in its local RP-set. The RP-
is initialized to the Holdtime in the RP's C-RP-Adv. When the
expires, the corresponding RP is removed from the RP- set. The RP
timer is restarted by the C-RP-Advs from the corresponding RP
The BSR also uses its Bootstrap-timer to periodically send messages. In particular, when the Bootstrap-timer expires, the
originates an Bootstrap message on each of its PIM interfaces.
message is sent with a TTL of 1 to the `ALL-PIM-ROUTERS' group.
steady state, the BSR originates Bootstrapmessages periodically.
startup, the Bootstrap-timer is initialized to [Bootstrap-Timeout],
causing the first Bootstrap message to be originated only when and
the timer expires. For timer details, see Section 3.6.3. A
unicasts a Bootstrap message to each new PIM neighbor, i.e.,
the DR receives the neighbor's Hello message (it does so even if
new neighbor becomes the DR).
The Bootstrap message is subdivided into sets of {group- prefix,RP
Count,RP-addresses}. For each RP-address, the corresponding
is included in the "RP-Holdtime" field. The format of the
message allows `semantic fragmentation', if the length of originalBootstrap message exceeds the packet maximum boundaries (
Section 4). However, we recommend against configuring a large
of routers as C-RPs, to reduce the semantic fragmentation required
1 If the message was not sent by the RPF neighbor towards
BSR address included, the message is dropped.
2 If the included BSR is not preferred over, and not
to, the currently active BSR
1 If the Bootstrap-timer has not yet expired, or if receiving router is a C-BSR, then the
message is dropped.
2 If the Bootstrap-timer has expired and the
router is not a C-BSR, the receiving router stores
RP-Set and BSR address and priority found in
message, and restarts the timer by setting it
[Bootstrap-Timeout]. The Bootstrap message is
forwarded out all PIM interfaces, excluding the
over which the message arrived, to `ALL-PIM-ROUTERS
group, with a TTL of 1.
3 If the Bootstrap message includes a BSR address that
preferred over, or equal to, the currently active BSR,
router restarts its Bootstrap-timer at [Bootstrap-Timeout
seconds. and stores the BSR address and RP-Set information
The Bootstrap message is then forwarded out all
interfaces, excluding the one over which the
arrived, to `ALL-PIM-ROUTERS' group, with a TTL of 1.
4 If the receiving router has no current RP set
and the Bootstrap was unicast to it from a connectedneighbor, the router stores the information
its new RP-set. This covers the startup condition when
newly booted router obtains the RP-Set and BSR address
its DR
When a router receives a new RP-Set, it checks if each of the
referred to by existing state (i.e., by (*,G), (*,*,RP),
(S,G)RPT-bit entries) is in the new RP-Set. If an RP is not in the
RP-set, that RP is consideredunreachable and the hash algorithm (
below) is re-performed for each group with locally active state
previously hashed to that RP. This will cause those groups to distributed among the remaining RPs. When the new RP-Set contains
new RP, the value of the new RP is calculated for each group
by that C-RP's Group- prefix. Any group for which the new RP's
is greater than the previously active RP's value is switched over
the new RP
3.7 Hash
The hash function is used by all routers within a domain, to map
group to one of the C-RPs from the RP-Set. For a particular group, G
the hash function uses only those C-RPs whose Group- prefix covers G
The algorithm takes as input the group address, and the addresses
the Candidate RPs, and gives as output one RP address to be used
The protocol requires that all routers hash to the same RP within
domain (except for transients). The following hash function must
used in each router
1 For each RP address C(i) in the RP-Set, whose Group-
covers G, compute a value
where M is a hash-mask included in Bootstrapmessages
This hash-mask allows a small number of consecutive
(e.g., 4) to always hash to the same RP. For instance
hierarchically-encoded data can be sent on
group addresses to get the same delay and fate-
characteristics
2 The candidate with the highest resulting value is
chosen as the RP for that group, and its identity and
value are stored with the entry created
Ties between C-RPs having the same hash value, are
in advantage of the highest address
The hash functionalgorithm is invoked by a DR, upon reception of
packet, or IGMP membershipindication, for a group, for which the
has no entry. It is invoked by any router that has (*,*,RP) state
a packet is received for which there is no corresponding (S,G)
(*,G) entry. Furthermore, the hash function is invoked by all
upon receiving a (*,G) or (*,*,RP) Join/Prune message
In this subsection, we enumerate all timers that have been
or implied. Since some critical timer events are not associated
the receipt or sending of messages, they are not fully covered
earlier subsections
Timers are implemented in an implementation-specific manner.
example, a timer may count up or down, or may simply expire at specific time. Setting a timer to a value T means that it will
after T seconds
3.8.1 Timers related to tree
Each (S,G), (*,G), and (*,*,RP) route entry has multiple associated with it: one for each interface in the outgoing
list, one for the multicast routing entry itself, and one
Join/Prune-Suppression-Timer. Each (S,G) and (*,G) entry also has
Assert-timer and a Random-Delay-Join-Timer for use with Asserts. addition, DR's have a Register- Suppression-timer for each (S,G)
and every router has a single Join/Prune-timer. (A router
optionally keep separate Join/Prune-timers for different interfaces
route entries if different Join/Prune periods are desired.)
* [Join/Prune-Timer] This timer is used for
sending aggregate Join/Prune messages. To synchronization among routers booting simultaneously, it
initially set to a random value between 1 and [Join/Prune
Period]. When it expires, the timer is
restarted to [Join/Prune-Period]. A Join/Prune message
then sent out each interface. This timer should not
restarted by other events
* [Join/Prune-Suppression-Timer (kept per route entry)]
route entry's (optional) Join/Prune-Suppression-Timer
be used to suppressduplicate joins from downstream routers on the same LAN. When a Join message received from a neighbor on the entry's incoming
in which the includedHoldtime is higher than the router'
own [Join/Prune-Holdtime] (with ties broken by higher
address), the timer is set to [Join/Prune-Suppression
Timeout], with some random jitter introduced to synchronization of triggered Join/Prune messages
expiration. (The random timeout value must be < 1.5 *
[Join/Prune-Period] to prevent losing data after 2
Join/Prunes.) The timer is restarted every time
subsequent Join/Prune message (with higher Holdtime/
address) for the entry is received on its interface. While the timer is running, Join/Prune
for the entry are not sent. This timer is idle (
running) for point-to-point links
* [Oif-Timer (kept per oif for each route entry)] A timer
each oif of a route entry is used to time out that oif
Because some of the outgoing interfaces in an (S,G)
are copied from the (*,G) outgoinginterface list, they
not have explicit (S,G) join messages from some of downstream routers (i.e., where members are joining to
(*,G) tree only). Thus, when an Oif-timer is restarted in
(*,G) entry, the Oif-timer is restarted for that
in each existing (S,G) entry whose oif list contains interface. The same rule applies to (*,G) and (S,G)
when restarting an Oif-timer on a (*,*,RP) entry
The following table shows its usage when first adding
oif to the entry's oiflist, when it should be
(unless it is already higher), and when it should
decreased (unless it is already lower).
Set to | When | Applies
-------------------------|------------------------------|------------ includedHoldtime | adding oif off Join/Prune | (S,G) (*,G
| | (*,*,RP
Increased (only) to | When | Applies
-------------------------|------------------------------|------------ includedHoldtime | received Join/Prune | (S,G) (*,G
| | (*,*,RP
| |
Value of (*,*,RP) | (*,*,RP) oif-timer restarted | (S,G) (*,G
oif-timer | |
| |
Value of (*,G) | (*,G) oif-timer restarted | (S,G
oif-timer | |
Decreased (only) to | When | Applies
-------------------------|------------------------------|------------
Oif-Deletion-Delay | prune received | (S,G) (*,G
When the timer expires, the oif is removed from the
if there are no directly-connected members. When deleted
the oif is also removed in any associated (S,G) or (*,G
entries
* [Entry-Timer (kept per route entry)] A timer for each
entry is used to time out that entry. The following
summarizes its usage when first adding the oif to
entry's oiflist, and when it should be restarted (unless
is already higher).
Set to | When | Applies
----------------------|--------------------------|------------
[Data- Timeout] | created off data packet | (S,G
| | includedHoldtime | created off Join/Prune | (S,G) (*,G
(*,*,RP
Increased (only) to | When | Applies
----------------------|--------------------------|------------
[Data-Timeout] | receiving data packets | (S,G)no RPT-
| |
Value of oif-timer | any oif-timer restarted | (S,G)RPT-bit (*,G
| | (*,*,RP
| |
[Assert-Timeout] | assert received | (S,G)RPT-
| | (*,G)w/null
When the timer expires, the route entry is deleted; if
entry is a (*,G) or (*,*,RP) entry, all
(S,G)RPT-bit entries are also deleted
* [Register-Suppression-Timer (kept per (S,G) route entry)]
An (S,G) route entry's Register-Suppression-Timer is
to suppress registers when the RP is receiving data
natively. When a Register-Stop message for the entry received from the RP, the timer is set to a random value
the range 0.5 * [Register-Suppression-Timeout] to 1.5 *
[Register-Suppression-Timeout]. While the timer is running
Registers for that entry will be suppressed. If
registers are used, a null register is sent [Probe-Time
seconds before the timer expires
* [Assert-Timer (per (S,G) or (*,G) route entry)]
Assert-Timer for an (S,G) or (*,G) route entry is used
timing out Asserts received. When an Assert is received
the RPF neighbor is changed to the Assert winner,
Assert-Timer is set to [Assert-Timeout], and is
to this value every time a subsequent Assert for the
is received on its incominginterface. When the
expires, the router resets its RPF neighboraccording
its unicast routing table
* [Random-Delay-Join-Timer (per (S,G) or (*,G) route entry)]
The Random-Delay-Join-Timer for an (S,G) or (*,G)
entry is used to prevent synchronization among
routers on a LAN when their RPF neighbor changes. When
RPF neighbor changes, this timer is set to a random
between 0 and [Random-Delay-Join-Timeout] seconds. When
timer expires, a triggered Join/Prune message is sent
the entry unless its Join/Prune-Suppression-Timer
running
* [Hello-Timer] This timer is used to periodically send messages. To avoid synchronization among routers
simultaneously, it is initially set to a random
between 1 and [Hello-Period]. When it expires, the timer immediately restarted to [Hello-Period]. A Hello message
then sent out each interface. This timer should not
restarted by other events
* [C-RP-Adv-Timer (C-RP's only)] Routers configured candidate RP's use this timer to periodically send C-RP- messages. To avoid synchronization among routers
simultaneously, the timer is initially set to a
value between 1 and [C-RP-Adv-Period]. When it expires,
timer is immediately restarted to [C-RP-Adv-Period]. A C
RP-Adv message is then sent to the elected BSR. This
should not be restarted by other events
* [RP-Timer (BSR only, kept per RP in RP-Set)] The BSR uses
timer per RP in the RP-Set to monitor liveness. When a C-
is added to the RP-Set, its timer is set to the included in the C-RP-Adv message from that C-RP (which
equal to the C-RP's value of [RP-Holdtime]). Every time
subsequent C-RP-Adv is received from that RP, its timer
restarted to the Holdtime in the C-RP-Adv. When the
expires, the RP is removed from the RP-Set included Bootstrapmessages
* [Bootstrap-Timer] This timer is used by the BSR
periodically originateBootstrapmessages, and by
routers to time out the BSR (see 3.6.3). This timer
initially set to [Bootstrap-Timeout]. A C-BSR
this timer to [Bootstrap-Timeout] upon receiving a
message from a preferred router, and originates an
message and restarts the timer to [Bootstrap-Period] when
expires. Routers not configured as C-BSR's restart
timer to [Bootstrap-Timeout] upon receiving a
message from the elected or a more preferred BSR, and Bootstrapmessages from non-preferred C-BSRs while it
running
3.8.4 Default timer
Most of the default timeout values for state information are 3.5
times the refresh period. For example, Hellos refresh Neighbor
and the default Hello-timer period is 30 seconds, so a Neighbor-timer duration of 105 seconds is included in the
field of the Hellos. In order to improve convergence, however,
default timeout value for information related to RP liveness Bootstrapmessages is 2.5 times the refresh period
In this version of the spec, we suggest particular numerical
settings. A future version of the specification will specify mechanism for timer values to be scaled based upon observed parameters
* [Join/Prune-Period] This is the interval
sending Join/Prune messages. {Default: 60 seconds.}
value may be set to take into account such things as configuredbandwidth and expected average number multicast route entries for the attached network or
(e.g., the period would be longer for lower-speed links,
for routers in the center of the network that expect
have a larger number of entries ). In addition, a
could modify this value (and corresponding Join/Prune Holdtime value) if the number of route entries
significantly (e.g., by an order of magnitude).
example, given a default minimum Join/Prune-Period value
if the number of route entries with a particular
increases from N to N*100, the router could increase
Join/Prune-Period (and Join/Prune-Holdtime), for interface, by a factor of 10; and if/when the number
entries decreases back to N, the Join/Prune-Period (
Join/Prune-Holdtime) could be decreased to its
value. If the Join/Prune-Period is modified, these
should be made relatively infrequently and the
should continue to refresh at its previous Join/Prune
Period for at least Join/Prune-Holdtime, in order to
the upstream router to adapt
* [Join-Prune Holdtime] This is the Holdtimespecified
Join/Prune messages, and is used to time out oifs.
should be set to 3.5 * [Join/Prune-Period]. {Default: 210
seconds.}
* [Join/Prune-Suppression-Timeout] This is the interval between receiving a Join/Prune with a Holdtime (with ties broken by higher IP addres)
allowing duplicate Join/Prunes to be sent again.
should be set to approximately 1.25 * [Join/Prune-Period].
{Default: 75 seconds. }
* [Data-Timeout] This is the time after which (S,G)
for a silent source will be deleted. {Default: 210
seconds.}
* [Register-Suppression-Timeout] This is the interval between receiving a Register-Stop and
Registers to be sent again. A lower value means
frequent register bursts at RP, while a higher value
longer join latency for new receivers. {Default: 60
seconds.} (Note that if null Registers are sent [Probe
Time] seconds before the timeout, register bursts
prevents, and [Register-Suppression-Timeout] may be
to decrease join latency.)
* [Probe-Time] When null Registers are used, this is
time between sending a null Register and the Register
Suppression-Timer expiring unless it is restarted receiving a Register-Stop. Thus, a null Register would
sent when the Register-Suppression-Timer reaches
value. {Default: 5 seconds.}
* [Assert-Timeout] This is the interval between the
time an Assert is received, and the time at which
assert is timed out. {Default: 180 seconds.}
* [Random-Delay-Join-Timeout] This is the interval between the time when the RPF neighbor changes
and the time at which a triggered Join/Prune message
sent. {Default: 4.5 seconds.}
* [Hello-Period] This is the interval between
Hello messages. {Default: 30 seconds.}
* [Hello-Holdtime] This is the Holdtimespecified
Hello messages, after which neighbors will time out neighbor entries for the router. This should be set to 3.5
* [Hello-Period]. {Default: 105 seconds.}
* [C-RP-Adv-Period] For C-RPs, this is the
between sending C-RP-Adv messages. {Default: 60 seconds.}
* [RP-Holdtime] For C-RPs, this is the Holdtime
in C-RP-Adv messages, and is used by the BSR to time
RPs. This should be set to 2.5 * [C-RP-Adv-Period].
{Default: 150 seconds.}
* [Bootstrap-Timeout] This is the time after which
elected BSR will be assumed unreachable when messages are not received from it. This should be set
2.5 * [Bootstrap-Period]. {Default: 150 seconds.}
Following is a summary of all the flags used in our scheme
Bit | Used in |
Authoritative | C-RP-Adv | Group-prefix information should not
over-ridden by
Border | Register | Register for external sources is
from PIM multicast border
Null | Register | Register sent as Probe of RP, encapsulated IP data packet should
be
RPT | Route entry | Entry represents state on the RP-
RPT | Join/Prune | Join is associated with the shared
and therefore the Join/Prune message
propagated along the RP-tree (
encoded is an RP address
RPT | Assert | The data packet was routed down the
tree; thus, the path indicated
to the RP
SPT | (S,G) entry | Packets have arrived on the iif towards S
and the iif is different from the (*,G
WC |Join | The receiver expects to receive
from all sources via this (shared tree
path. Thus, the Join/Prune applies to
(*,G)
WC | Route entry | Wildcard entry; if there is no specific match for a particular source
packets will be forwarded according
this
3.10
All PIM control messages may use IPSec [6] to address
concerns
4 Packet
This section describes the details of the packet formats for
control messages
Basically, PIM messages are either unicast (e.g. Registers Register-Stop), or multicast hop-by-hop to `ALL-PIM-ROUTERS'
`224.0.0.13' (e.g. Join/Prune, Asserts, etc.).
0 =
1 =
2 = Register-
3 = Join/
4 =
5 =
6 = Graft (used in PIM-DM only
7 = Graft-Ack (used in PIM-DM only
8 = Candidate-RP-
Addr
Address length in bytes. Throughout this section
would indicate the number of bytes in the Address field
an address, including unicast and group addresses
Mask
The Mask length is 8 bits. The value is the number
contiguous bits left justified used as a mask
describes the address. It is less than or equal
Addr length * 8. If the message is sent for a
group then the Mask length must equal Addr length * 8
(i.e. 32 for IPv4 and 128 for IPv6).
Group multicast contains the group address, and has number of
equal to that specified in the Addr length field
3 Encoded-Source-Address: Takes the following format
Mask
Mask length is 8 bits. The value is the number
contiguous bits left justified used as a mask
describes the address. The mask length must be
than or equal to Addr Length * 8. If the message
sent for a single source then the Mask length
equal Addr length * 8. In version 2 of PIM, it
strongly recommended that this field be set to 32
IPv4.
Source
The address length is indicated from the Addr
field at the beginning of the header. For IPv4,
address length is 4 octets
4.2 Hello
It is sent periodically by routers on all interfaces
A variable length field, carrying the value of the option
The Option fields may contain the following values
* OptionType = 1; OptionLength = 2; OptionValue = Holdtime
where Holdtime is the amount of time a receiver must
the neighborreachable, in seconds. If the Holdtime is
to `0xffff', the receiver of this message never times
the neighbor. This may be used with ISDN lines, to
keeping the link up with periodic Hello messages
Furthermore, if the Holdtime is set to `0', the
is timed out immediately
* OptionType 2 to 16:
* The rest of the OptionTypes are defined in document
In general, options may be ignored; but a router must not ignore
'Holdtime' OptionType
A Register message is sent by the DR or a PMBR to the RP when multicast packet needs to be transmitted on the RP-tree. Source
address is set to the address of the DR, destination IP address is
the RP's address
B The Border bit. If the router is a DR for a source that
is directly connected to, it sets the B bit to 0. If
router is a PMBR for a source in a directly
cloud, it sets the B bit to 1.
N The Null-Register bit. Set to 1 by a DR that is
the RP before expiring its local Register-
timer. Set to 0 otherwise
For (S,G) null Registers, the Multicast data packet portion
only a dummy IP header with S as the source address, G as destination address, and a data length of zero
Encoded-Group
Format described above. Note that for Register-Stops
Mask Len field contains Addr length * 8 (32 for IPv4),
the message is sent for a single group
Unicast-Source
IP host address of source from multicast data packet register. The length of this field in bytes is specified
the Addr length field. A special wild card value (0.0.0.0),
can be used to indicate any source
A Join/Prune message is sent by routers towards upstream sources
RPs. Joins are sent to build shared trees (RP trees) or source
(SPT). Prunes are sent to prune source trees when members
groups as well as sources that do not use the shared tree
The amount of time a receiver must keep the Join/
state alive, in seconds. If the Holdtime is set
`0xffff', the receiver of this message never times out
oif. This may be used with ISDN lines, to avoid keeping
link up with periodical Join/Prune messages. Furthermore
if the Holdtime is set to `0', the information is timed immediately
Number of
The number of multicast group sets contained in
message
Encoded-Multicast group
For format description see
4.1. A wild card group in the (*,*,RP) join is
by a 224.0.0.0 in the group address field and `4' in
mask length field. A (*,*,RP) join also has the WC-bit
the RPT-bit set
Number of Joined
Number of join source addresses listed for a given group
Join Source Address-1 ..
This list contains the sources that the sending
will forward multicast datagrams for if received on interface this message is sent on
See format section 4.1. The fields explanation for
Encoded-Source-Address format follows
W The WC bit is a 1 bit value. If 1, the join or
applies to the (*,G) or (*,*,RP) entry. If 0, the
or prune applies to the (S,G) entry where S is
Address. Joins and prunes sent towards the RP
have this bit set
R The RPT-bit is a 1 bit value. If 1, the
about (S,G) is sent towards the RP. If 0, information must be sent toward S, where S is
Source Address
Number of Pruned
Number of prune source addresses listed for a group
Prune Source Address-1 ..
This list contains the sources that the sending
does not want to forward multicast datagrams for received on the interface this message is sent on. If
Join/Prune message boundary exceeds the maximum
size, then the join and prune lists for the same group
be included in the same packet
Unicast-BSR-
The IP address of the bootstrap router for the domain.
length of this field in bytes is specified in Addr length
Encoded-Group Address-1..
The group prefix (address and mask) with which Candidate RPs are associated. Format previously described
RP-Count-1..
The number of Candidate RP addressesincluded in the Bootstrap message for the corresponding group prefix.
router does not replace its old RP-Set for a given
prefix until/unless it receives `RP-Count' addresses
that prefix; the addresses could be carried over
fragments. If only part of the RP-Set for a given
prefix was received, the router discards it, updating that specific group prefix's RP-Set
Frag RP-Cnt-1..
The number of Candidate RP addressesincluded in fragment of the Bootstrap message, for the
group prefix. The `Frag RP-Cnt' field facilitates
of the RP-Set for a given group prefix, when carried
more than one fragment
Unicast-RP-address-1..
The address of the Candidate RPs, for the
group prefix. The length of this field in bytes specified in Addr length
Encoded-Group
The group address to which the data packet was addressed
and which triggered the Assert. Format described
Unicast-Source
Source IP address from IP multicastdatagram triggered the Assert packet to be sent. The length of
field in bytes is specified in Addr length
R RPT-bit is a 1 bit value. If the IP multicast
that triggered the Assert packet is routed down the
tree, then the RPT-bit is 1; if the IP multicast
is routed down the SPT, it is 0.
Prefix-
The number of encoded group addressesincluded in
message; indicating the group prefixes for which the C-
is advertising. A Prefix-Cnt of `0' implies a prefix
224.0.0.0 with mask length of 4; i.e. all multicast groups
If the C-RP is not configured with Group- information, the C-RP puts a default value of `0' in
field
Tony Ballardie, Scott Brim, Jon Crowcroft, Bill Fenner, Paul Francis
Joel Halpern, Horst Hodel, Polly Huang, Stephen Ostrowski,
Zhang and Girish Chandranmenon provided detailed comments on
drafts. The authors of CBT [7] and membership of the IDMR WG
many of the motivating ideas for this work and useful feedback
design details
This appendix populates the major changes in the document as compared to `draft-ietf-idmr-pim-spec-01.ps,txt'.
* Major
List of changes since March '96 IETF
(*,*,RP) Joins state and data forwarding check; replaces (*,G
Prefix) Joins state for interoperability. (*,G) negative
introduced for the (*,*,RP) state supporting mechanisms
The protocol transitions for a C-BSR are given in state diagram (a).
For routers not configured as C-BSRs, the protocol transitions
given in state diagram (b).
Each PIM router keeps a Bootstrap-timer, initialized
[Bootstrap-Timeout], in addition to a local BSR field `LclBSR
(initialized to a local address if C-BSR, or to 0 otherwise), and
local RP-Set `LclRP-Set' (initially empty). The two main stimuli
the state machine are the timer events, and receiving an
message
2 If the Bootstrap-timer expires, and the current state
`CandBSR', the router originates an Bootstrap message -
carrying the local RP-Set, and its own BSR priority
address-, restarts the Bootstrap-timer at [Bootstrap
Period] seconds and transits into the `ElectedBSR' state
3 If the Bootstrap-timer expires, and the current state
`ElectedBSR', the router originates an Bootstrap message
and restarts the RP-Set timer at [Bootstrap-Period].
state transition is incurred
This way, the elected BSR originates periodic messages every [Bootstrap-Period].
1 The router operates initially in the 'AxptAny' state.
such state, a router accepts the first Bootstrap
from the RPF neighbor toward the included BSR. The
Path Forwarding (RPF) neighbor in this case is the next
router en route to the included BSR
2 If the Bootstrap-timer expires, and the current state
`AxptPref', -where the router accepts only preferred Bootstrapmessages from the RPF neighbor toward included BSR-, the router transits into the `AxptAny
state (preferred Bootstrapmessages are those that
BSR-priority and address higher than, or equal to
`LclBSR').
In this case, if an elected BSR becomes unreachable,
routers start accepting Bootstrapmessages from another C
BSR after the Bootstrap-timer expires. All PIM
within a domain converge on the preferred (with priority and address) reachable C-BSR
* {Bootstrap router (BSR)}. A BSR is a dynamically elected
within a PIM domain. It is responsible for constructing the RP
Set and originating Bootstrapmessages
* {Candidate-BSR (C-BSR)}. A C-BSR is a router configured
participate in the BSR election and act as BSRs if elected
* {Designated Router (DR)}. The DR sets up multicast
entries and sends corresponding Join/Prune and Register
on behalf of directly-connected receivers and sources
respectively. The DR may or may not be the same router as
IGMP Querier. The DR may or may not be the long-term, last-
router for the group; a router on the LAN that has a
metric route to the data source, or to the group's RP, may
over the role of sending Join/Prune messages
* {Join list}. The Join list is one of two lists of addresses
is included in a Join/Prune message; each address refers to
source or RP. It indicates those sources or RPs to downstreamreceiver(s) wish to join
* {Last-hop router}. The last-hop router is the last router
receive multicast data packets before they are delivered
directly-connected member hosts. In general the last-hop
is the DR for the LAN. However, under various described in this document a parallel router connected to
same LAN may take over as the last-hop router in place of
DR
* {Prune List}. The Prune list is the second list of
that is included in a Join/Prune message. It indicates
sources or RPs from which downstreamreceiver(s) wish to prune
* {PIM Multicast Border Router (PMBR)}. A PMBR connects a
domain to other multicast routing domain(s).
* {Rendezvous Point (RP)}. Each multicast group has a shared-
via which receivers hear of new sources and new receivers
of all sources. The RP is the root of this per-group
tree, called the RP-Tree
* {RP-Set}. The RP-Set is a set of RP addresses constructed
the BSR based on Candidate-RP advertisements received. The RP
Set information is distributed to all PIM routers in the BSR'
PIM domain
* {Reverse Path Forwarding (RPF)}. RPF is used to select appropriateincominginterface for a multicast route entry .
RPF neighbor for an IP address X is the the next-hop router
to forward packets toward X. The RPF interface is the
to that RPF neighbor. In the common case this is the next
used by the unicast routing protocol for sending unicast
toward X. For example, in cases where unicast and
routes are not congruent, it can be different
* {Route entry.} A multicast route entry is state maintained in
router along the distribution tree and is created, and
based on incoming control messages. The route entry may different from the forwarding entry; the latter is used
forward data packets in real time. Typically a forwarding
is not created until data packets arrive, the forwarding entry'
iif and oif list are copied from the route entry, and forwarding entry may be flushed and recreated at will
* {Shortest path tree (SPT)}. The SPT is the distribution tree created by the merger of all of the
paths that connect receivers to the source (as determined
unicast routing).
* {Wildcard (WC) multicast route entry}. Wildcardmulticast
entries are those entries that may be used to forward
for any source sending to the specified group. Wildcard bots
the join list of a Join/Prune message represent either a (*,G
or (*,*,RP) join; in the prune list they represent a (*,G
prune
* {(S,G) route entry}. (S,G) is a source-specific route entry.
may be created in response to data packets, Join/Prune messages
or Asserts. The (S,G) state in routers creates a source-rooted shortest path (or reverse shortest path) distribution tree
(S,G)RPT bit entries are source-specific entries on the
RP-Tree; these entries are used to prune particular sources
of the shared tree
* {(*,G) route entry}. Group members join the shared RP-Tree
a particular group. This tree is represented by (*,G)
route entries along the shortest path branches between the
and the group members
* {(*,*,RP) route entry}. (*,*,RP) refers to any source and multicast group that maps to the RP included in the entry.
routers along the shortest path branches between a domain'
RP(s) and its PMBRs keep (*,*,RP) state and use it to
how to deliver packets toward the PMBRs if data packets
for which there is not a longer match. The wildcard group in
(*,*,RP) route entry is represented by a group address
224.0.0.0 and a mask length of 4 bits
2. Deering, S., D.Estrin, D.Farinacci, V.Jacobson, C.Liu, and L.Wei
The pim architecture for wide-area multicast routing
ACM Transactions on Networks, April 1996.
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
