a short random interval. If OT(S,G) is not running and the Prune
Indicator bit equals one, the router MUST set OT(S,G) to
t_override seconds.
State Refresh(S,G) Received from RPF’(S) with Prune Indicator == 0
The router MUST cancel its GraftRetry Timer (GRT(S,G)) and
transition to the Forwarding (F) state.
See Join(S,G) to RPF’(S,G)
This event is only relevant if RPF_interface(S) is a shared
medium. This router sees another router on RPF_interface(S) send
a Join(S,G) to RPF’(S,G). If the OT(S,G) is running, then it
means that the router had scheduled a Join to override a
previously received Prune. Another router has responded more
quickly with a Join, so the local router SHOULD cancel its
OT(S,G), if it is running. The Upstream(S,G) state machine
remains in the AckPending (AP) state.
See Prune(S,G)
This event is only relevant if RPF_interface(S) is a shared
medium. This router sees another router on RPF_interface(S) send
a Prune(S,G). As this router is in AckPending (AP) state, it
must override the Prune after a short random interval. If
OT(S,G) is not running, the router MUST set OT(S,G) to t_override
seconds. The Upstream(S,G) state machine remains in AckPending
(AP) state.
OT(S,G) Expires
The OverrideTimer (OT(S,G)) expires. The router MUST send a
Join(S,G) to RPF’(S). The Upstream(S,G) state machine remains in
the AckPending (AP) state.
olist(S,G) -> NULL
The set of interfaces defined by the olist(S,G) macro becomes
null, indicating that traffic from S addressed to group G should
no longer be forwarded. The Upstream(S,G) state machine MUST
transition to the Pruned (P) state. A Prune(S,G) MUST be
multicast to the RPF_interface(S), with RPF’(S) named in the
upstream neighbor field. The GraftRetry Timer (GRT(S,G)) MUST be
cancelled, and PLT(S,G) MUST be set to t_limit seconds.
RPF’(S) Changes AND olist(S,G) does not become NULL AND S NOT
directly connected
Unicast routing or Assert state causes RPF’(S) to change,
including changes to RPF_Interface(S). The Upstream(S,G) state
machine stays in the AckPending (AP) state. A Graft MUST be
unicast to the new RPF’(S) and the GraftRetry Timer (GRT(S,G))
reset to Graft_Retry_Period.
RPF’(S) Changes AND olist(S,G) == NULL AND S NOT directly connected
Unicast routing or Assert state causes RPF’(S) to change,
including changes to RPF_Interface(S). The Upstream(S,G) state
machine MUST transition to the Pruned (P) state. The GraftRetry
Timer (GRT(S,G)) MUST be cancelled.
S becomes directly connected
Unicast routing has changed so that S is directly connected. The
GraftRetry Timer MUST be cancelled, and the Upstream(S,G) state
machine MUST transition to the Forwarding(F) state.
GRT(S,G) Expires
The GraftRetry Timer (GRT(S,G)) expires for this (S,G) entry.
The Upstream(S,G) state machine stays in the AckPending (AP)
state. Another Graft message for (S,G) SHOULD be unicast to
RPF’(S) and the GraftRetry Timer (GRT(S,G)) reset to
Graft_Retry_Period. It is RECOMMENDED that the router retry a
configured number of times before ceasing retries.
See GraftAck(S,G) from RPF’(S)
A GraftAck is received from RPF’(S). The GraftRetry Timer MUST
be cancelled, and the Upstream(S,G) state machine MUST transition
to the Forwarding(F) state.
4.4.2. Downstream Prune, Join, and Graft Messages
The Prune(S,G) Downstream state machine for receiving Prune, Join and
Graft messages on interface I is given below. This state machine
MUST always be in the NoInfo state on the upstream interface. It
contains three states.
NoInfo(NI)
The interface has no (S,G) Prune state, and neither the Prune
timer (PT(S,G,I)) nor the PrunePending timer ((PPT(S,G,I)) is
running.
PrunePending(PP)
The router has received a Prune(S,G) on this interface from a
downstream neighbor and is waiting to see whether the prune will
be overridden by another downstream router. For forwarding
purposes, the PrunePending state functions exactly like the
NoInfo state.
Pruned(P)
The router has received a Prune(S,G) on this interface from a
downstream neighbor, and the Prune was not overridden. Data from
S addressed to group G is no longer being forwarded on this
interface.
In addition, there are two timers:
PrunePending Timer (PPT(S,G,I))
This timer is set when a valid Prune(S,G) is received. Expiry of
the PrunePending Timer (PPT(S,G,I)) causes the interface to
transition to the Pruned state.
Prune Timer (PT(S,G,I))
This timer is set when the PrunePending Timer (PT(S,G,I))
expires. Expiry of the Prune Timer (PT(S,G,I)) causes the
interface to transition to the NoInfo (NI) state, thereby
allowing data from S addressed to group G to be forwarded on the
interface.
+-------------+ +-------------+
| | PPT Expires | |
|PrunePending |----------------------->| Pruned |
| | | |
+-------------+ +-------------+
| ^ |
| | |
| |Rcv Prune |
| | |
| | +-------------+ |
| +---------| | |
| | NoInfo |<-------------+
+------------>| | Rcv Join/Graft OR
Rcv Join/Graft OR +-------------+ PT Expires OR
RPF_Interface(S)->I RPF_Interface(S)->I
Figure 2: Downstream Interface State Machine
In tabular form, the state machine is as follows:
+-------------------------------+--------------------------------------+
| | Previous State |
+ +------------+------------+------------+
| Event | No Info | PrunePend | Pruned |
+-------------------------------+------------+------------+------------+
| Receive Prune(S,G) |->PP Set |->PP |->P Reset |
| | PPT(S,G,I) | | PT(S,G,I) |
+-------------------------------+------------+------------+------------+
| Receive Join(S,G) |->NI |->NI Cancel |->NI Cancel |
| | | PPT(S,G,I) | PT(S,G,I) |
+-------------------------------+------------+------------+------------+
| Receive Graft(S,G) |->NI Send |->NI Send |->NI Send |
| | GraftAck | GraftAck | GraftAck |
| | | Cancel | Cancel |
| | | PPT(S,G,I) | PT(S,G,I) |
+-------------------------------+------------+------------+------------+
| PPT(S,G) Expires | N/A |->P Set | N/A |
| | | PT(S,G,I) | |
+-------------------------------+------------+------------+------------+
| PT(S,G) Expires | N/A | N/A |->NI |
+-------------------------------+------------+------------+------------+
| RPF_Interface(S) becomes I |->NI |->NI Cancel |->NI Cancel |
| | | PPT(S,G,I) | PT(S,G,I) |
+-------------------------------+------------+------------+------------+
| Send State Refresh(S,G) out I |->NI |->PP |->P Reset |
| | | | PT(S,G,I) |
+-------------------------------+------------+------------+------------+
The transition events "Receive Graft(S,G)", "Receive Prune(S,G)", and
"Receive Join(S,G)" denote receiving a Graft, Prune, or Join message
in which this router’s address on I is contained in the message’s
upstream neighbor field. If the upstream neighbor field does not
match this router’s address on I, then these state transitions in
this state machine must not occur.
4.4.2.1. Transitions from the NoInfo State
When the Prune(S,G) Downstream state machine is in the NoInfo (NI)
state, the following events may trigger a transition:
Receive Prune(S,G)
A Prune(S,G) is received on interface I with the upstream
neighbor field set to the router’s address on I. The Prune(S,G)
Downstream state machine on interface I MUST transition to the
PrunePending (PP) state. The PrunePending Timer (PPT(S,G,I))
MUST be set to J/P_Override_Interval if the router has more than
one neighbor on I. If the router has only one neighbor on
interface I, then it SHOULD set the PPT(S,G,I) to zero,
effectively transitioning immediately to the Pruned (P) state.
Receive Graft(S,G)
A Graft(S,G) is received on the interface I with the upstream
neighbor field set to the router’s address on I. The Prune(S,G)
Downstream state machine on interface I stays in the NoInfo (NI)
state. A GraftAck(S,G) MUST be unicast to the originator of the
Graft(S,G) message.
4.4.2.2. Transitions from the PrunePending (PP) State
When the Prune(S,G) downstream state machine is in the PrunePending
(PP) state, the following events may trigger a transition.
Receive Join(S,G)
A Join(S,G) is received on interface I with the upstream neighbor
field set to the router’s address on I. The Prune(S,G)
Downstream state machine on interface I MUST transition to the
NoInfo (NI) state. The PrunePending Timer (PPT(S,G,I)) MUST be
cancelled.
Receive Graft(S,G)
A Graft(S,G) is received on interface I with the upstream
neighbor field set to the router’s address on I. The Prune(S,G)
Downstream state machine on interface I MUST transition to the
NoInfo (NI) state and MUST unicast a Graft Ack message to the
Graft originator. The PrunePending Timer (PPT(S,G,I)) MUST be
cancelled.
PPT(S,G,I) Expires
The PrunePending Timer (PPT(S,G,I)) expires, indicating that no
neighbors have overridden the previous Prune(S,G) message. The
Prune(S,G) Downstream state machine on interface I MUST
transition to the Pruned (P) state. The Prune Timer (PT(S,G,I))
is started and MUST be initialized to the received
Prune_Hold_Time minus J/P_Override_Interval. A PruneEcho(S,G)
MUST be sent on I if I has more than one PIM neighbor. A
PruneEcho(S,G) is simply a Prune(S,G) message multicast by the
upstream router to a LAN, with itself as the Upstream Neighbor.
Its purpose is to add additional reliability so that if a Join
that should have overridden the Prune is lost locally on the LAN,
the PruneEcho(S,G) may be received and trigger a new Join
message. A PruneEcho(S,G) is OPTIONAL on an interface with only
one PIM neighbor. In addition, the router MUST evaluate any
possible transitions in the Upstream(S,G) state machine.
RPF_Interface(S) becomes interface I
The upstream interface for S has changed. The Prune(S,G)
Downstream state machine on interface I MUST transition to the
NoInfo (NI) state. The PrunePending Timer (PPT(S,G,I)) MUST be
cancelled.
4.4.2.3. Transitions from the Prune (P) State
When the Prune(S,G) Downstream state machine is in the Pruned (P)
state, the following events may trigger a transition.
Receive Prune(S,G)
A Prune(S,G) is received on the interface I with the upstream
neighbor field set to the router’s address on I. The Prune(S,G)
Downstream state machine on interface I remains in the Pruned (P)
state. The Prune Timer (PT(S,G,I)) SHOULD be reset to the
holdtime contained in the Prune(S,G) message if it is greater
than the current value.
Receive Join(S,G)
A Join(S,G) is received on the interface I with the upstream
neighbor field set to the router’s address on I. The Prune(S,G)
downstream state machine on interface I MUST transition to the
NoInfo (NI) state. The Prune Timer (PT(S,G,I)) MUST be
cancelled. The router MUST evaluate any possible transitions in
the Upstream(S,G) state machine.
Receive Graft(S,G)
A Graft(S,G) is received on interface I with the upstream
neighbor field set to the router’s address on I. The Prune(S,G)
Downstream state machine on interface I MUST transition to the
NoInfo (NI) state and send a Graft Ack back to the Graft’s
source. The Prune Timer (PT(S,G,I)) MUST be cancelled. The
router MUST evaluate any possible transitions in the
Upstream(S,G) state machine.
PT(S,G,I) Expires
The Prune Timer (PT(S,G,I)) expires, indicating that it is again
time to flood data from S addressed to group G onto interface I.
The Prune(S,G) Downstream state machine on interface I MUST
transition to the NoInfo (NI) state. The router MUST evaluate
any possible transitions in the Upstream(S,G) state machine.
RPF_Interface(S) becomes interface I
The upstream interface for S has changed. The Prune(S,G)
Downstream state machine on interface I MUST transition to the
NoInfo (NI) state. The PruneTimer (PT(S,G,I)) MUST be cancelled.
Send State Refresh(S,G) out interface I
The router has refreshed the Prune(S,G) state on interface I.
The router MUST reset the Prune Timer (PT(S,G,I)) to the Holdtime
from an active Prune received on interface I. The Holdtime used
SHOULD be the largest active one but MAY be the most recently
received active Prune Holdtime.
4.5. State Refresh
This section describes the major portions of the state refresh
mechanism.
4.5.1. Forwarding of State Refresh Messages
When a State Refresh message, SRM, is received, it is forwarded
according to the following pseudo-code.
if (iif != RPF_interface(S))
return;
if (RPF’(S) != srcaddr(SRM))
return;
if (StateRefreshRateLimit(S,G) == TRUE)
return;
for each interface I in pim_nbrs {
if (TTL(SRM) == 0 OR (TTL(SRM) - 1) < Threshold(I))
continue; /* Out of TTL, skip this interface */
if (boundary(I,G))
continue; /* This interface is scope boundary, skip it */
if (I == iif)
continue; /* This is the incoming interface, skip it */
if (lost_assert(S,G,I) == TRUE)
continue; /* Let the Assert Winner do State Refresh */
Copy SRM to SRM’; /* Make a copy of SRM to forward */
if (I contained in prunes(S,G)) {
set Prune Indicator bit of SRM’ to 1;
if StateRefreshCapable(I) == TRUE
set PT(S,G) to largest active holdtime read from a Prune
message accepted on I;
} else {
set Prune Indicator bit of SRM’ to 0;
}
set srcaddr(SRM’) to my_addr(I);
set TTL of SRM’ to TTL(SRM) - 1;
set metric of SRM’ to metric of unicast route used to reach S;
set pref of SRM’ to preference of unicast route used to reach S;
set mask of SRM’ to mask of route used to reach S;
if (AssertState == NoInfo) {
set Assert Override of SRM’ to 1;
} else {
set Assert Override of SRM’ to 0;
}
transmit SRM’ on I;
}
The pseudocode above employs the following macro definitions.
Boundary(I,G) is TRUE if an administratively scoped boundary for
group G is configured on interface I.
StateRefreshCapable(I) is TRUE if all neighbors on an interface use
the State Refresh option.
StateRefreshRateLimit(S,G) is TRUE if the time elapsed since the last
received StateRefresh(S,G) is less than the configured
RefreshLimitInterval.
TTL(SRM) returns the TTL contained in the State Refresh Message, SRM.
This is different from the TTL contained in the IP header.
Threshold(I) returns the minimum TTL that a packet must have before
it can be transmitted on interface I.
srcaddr(SRM) returns the source address contained in the network
protocol (e.g., IPv4) header of the State Refresh Message, SRM.
my_addr(I) returns this node’s network (e.g., IPv4) address on
interface I.
4.5.2. State Refresh Message Origination
This section describes the origination of State Refresh messages.
These messages are generated periodically by the PIM-DM router
directly connected to a source. One Origination(S,G) state machine
exists per (S,G) entry in a PIM-DM router.
The Origination(S,G) state machine has the following states:
NotOriginator(NO)
This is the starting state of the Origination(S,G) state machine.
While in this state, a router will not originate State Refresh
messages for the (S,G) pair.
Originator(O)
When in this state the router will periodically originate State
Refresh messages. Only routers directly connected to S may
transition to this state.
In addition, there are two state machine specific timers:
State Refresh Timer (SRT(S,G))
This timer controls when State Refresh messages are generated.
The timer is initially set when that Origination(S,G) state
machine transitions to the O state. It is cancelled when the
Origination(S,G) state machine transitions to the NO state. This
timer is normally set to StateRefreshInterval (see 4.8).
Source Active Timer (SAT(S,G))
This timer is first set when the Origination(S,G) state machine
transitions to the O state and is reset on the receipt of every
data packet from S addressed to group G. When it expires, the
Origination(S,G) state machine transitions to the NO state. This
timer is normally set to SourceLifetime (see 4.8).
+-------------+ Rcv Directly From S +-------------+
| |----------------------->| |
|NotOriginator| | Originator |
| |<-----------------------| |
+-------------+ SAT Expires OR +-------------+
S NOT Direct Connect
Figure 3: State Refresh State Machine
In tabular form, the state machine is defined as follows:
+----------------------------------------------------------------------+
| | Previous State |
| +---------------+-------------------+
| Event | NotOriginator | Originator |
+----------------------------------+---------------+-------------------+
| Receive Data from S AND | ->O | ->O Reset |
| S directly connected | Set SRT(S,G) | SAT(S,G) |
| | Set SAT(S,G) | |
+----------------------------------+---------------+-------------------+
| SRT(S,G) Expires | N/A | ->O Send |
| | | StateRefresh(S,G) |
| | | Reset SRT(S,G) |
+----------------------------------+---------------+-------------------+
| SAT(S,G) Expires | N/A | ->NO Cancel |
| | | SRT(S,G) |
+----------------------------------+---------------+-------------------+
| S no longer directly connected | ->NO | ->NO |
| | | Cancel SRT(S,G) |