the packet arrived. Packets that fail the RPF check MUST NOT be
forwarded, and the router will conduct an assert process for the
(S,G) pair specified in the packet. Packets for which a route to the
source cannot be found MUST be discarded.
If the RPF check has been passed, an outgoing interface list is
constructed for the packet. If this list is not empty, then the
packet MUST be forwarded to all listed interfaces. If the list is
empty, then the router will conduct a prune process for the (S,G)
pair specified in the packet.
Upon receipt of a data packet from S addressed to G on interface iif:
if (iif == RPF_interface(S) AND UpstreamPState(S,G) != Pruned) {
oiflist = olist(S,G)
} else {
oiflist = NULL
}
forward packet on all interfaces in oiflist
This pseudocode employs the following "macro" definition:
UpstreamPState(S,G) is the state of the Upstream(S,G) state machine
in Section 4.4.1.
4.3. Hello Messages
This section describes the generation and processing of Hello
messages.
4.3.1. Sending Hello Messages
PIM-DM uses Hello messages to detect other PIM routers. Hello
messages are sent periodically on each PIM enabled interface. Hello
messages are multicast to the ALL-PIM-ROUTERS group. When PIM is
enabled on an interface or when a router first starts, the Hello
Timer (HT) MUST be set to random value between 0 and
Triggered_Hello_Delay. This prevents synchronization of Hello
messages if multiple routers are powered on simultaneously.
After the initial Hello message, a Hello message MUST be sent every
Hello_Period. A single Hello timer MAY be used to trigger sending
Hello messages on all active interfaces. The Hello Timer SHOULD NOT
be reset except when it expires.
4.3.2. Receiving Hello Messages
When a Hello message is received, the receiving router SHALL record
the receiving interface, the sender, and any information contained in
recognized options. This information is retained for a number of
seconds in the Hold Time field of the Hello Message. If a new Hello
message is received from a particular neighbor N, the Neighbor
Liveness Timer (NLT(N,I)) MUST be reset to the newly received Hello
Holdtime. If a Hello message is received from a new neighbor, the
receiving router SHOULD send its own Hello message after a random
delay between 0 and Triggered_Hello_Delay.
4.3.3. Hello Message Hold Time
The Hold Time in the Hello Message should be set to a value that can
reasonably be expected to keep the Hello active until a new Hello
message is received. On most links, this will be 3.5 times the value
of Hello_Period.
If the Hold Time is set to ’0xffff’, the receiving router MUST NOT
time out that Hello message. This feature might be used for on-
demand links to avoid keeping the link up with periodic Hello
messages.
If a Hold Time of ’0’ is received, the corresponding neighbor state
expires immediately. When a PIM router takes an interface down or
changes IP address, a Hello message with a zero Hold Time SHOULD be
sent immediately (with the old IP address if the IP address is
changed) to cause any PIM neighbors to remove the old information
immediately.
4.3.4. Handling Router Failures
If a Hello message is received from an active neighbor with a
different Generation ID (GenID), the neighbor has restarted and may
not contain the correct (S,G) state. A Hello message SHOULD be sent
after a random delay between 0 and Triggered_Hello_Delay (see 4.8)
before any other messages are sent. If the neighbor is downstream,
the router MAY replay the last State Refresh message for any (S,G)
pairs for which it is the Assert Winner indicating Prune and Assert
status to the downstream router. These State Refresh messages SHOULD
be sent out immediately after the Hello message. If the neighbor is
the upstream neighbor for an (S,G) entry, the router MAY cancel its
Prune Limit Timer to permit sending a prune and reestablishing a
Pruned state in the upstream router.
Upon startup, a router MAY use any State Refresh messages received
within Hello_Period of its first Hello message on an interface to
establish state information. The State Refresh source will be the
RPF’(S), and Prune status for all interfaces will be set according to
the Prune Indicator bit in the State Refresh message. If the Prune
Indicator is set, the router SHOULD set the PruneLimitTimer to
Prune_Holdtime and set the PruneTimer on all downstream interfaces to
the State Refresh’s Interval times two. The router SHOULD then
propagate the State Refresh as described in Section 4.5.1.
4.3.5. Reducing Prune Propagation Delay on LANs
If all routers on a LAN support the LAN Prune Delay option, then the
PIM routers on that LAN will use the values received to adjust their
J/P_Override_Interval on that interface and the interface is LAN
Delay Enabled. Briefly, to avoid synchronization of Prune Override
(Join) messages when multiple downstream routers share a multi-access
link, sending of these messages is delayed by a small random amount
of time. The period of randomization is configurable and has a
default value of 3 seconds.
Each router on the LAN expresses its view of the amount of
randomization necessary in the Override Interval field of the LAN
Prune Delay option. When all routers on a LAN use the LAN Prune
Delay Option, all routers on the LAN MUST set their Override_Interval
to the largest Override value on the LAN.
The LAN Delay inserted by a router in the LAN Prune Delay option
expresses the expected message propagation delay on the link and
SHOULD be configurable by the system administrator. When all routers
on a link use the LAN Prune Delay Option, all routers on the LAN MUST
set Propagation Delay to the largest LAN Delay on the LAN.
PIM implementers should enforce a lower bound on the permitted values
for this delay to allow for scheduling and processing delays within
their router. Such delays may cause received messages to be
processed later and triggered messages to be sent later than
intended. Setting this LAN Prune Delay to too low a value may result
in temporary forwarding outages, because a downstream router will not
be able to override a neighbor’s prune message before the upstream
neighbor stops forwarding.
4.4. PIM-DM Prune, Join, and Graft Messages
This section describes the generation and processing of PIM-DM Join,
Prune, and Graft messages. Prune messages are sent toward the
upstream neighbor for S to indicate that traffic from S addressed to
group G is not desired. In the case of downstream routers A and B,
where A wishes to continue receiving data and B does not, A will send
a Join in response to B’s Prune to override the Prune. This is the
only situation in PIM-DM in which a Join message is used. Finally, a
Graft message is used to re-join a previously pruned branch to the
delivery tree.
4.4.1. Upstream Prune, Join, and Graft Messages
The Upstream(S,G) state machine for sending Prune, Graft, and Join
messages is given below. There are three states.
Forwarding (F)
This is the starting state of the Upsteam(S,G) state machine.
The state machine is in this state if it just started or if
oiflist(S,G) != NULL.
Pruned (P)
The set, olist(S,G), is empty. The router will not forward data
from S addressed to group G.
AckPending (AP)
The router was in the Pruned(P) state, but a transition has
occurred in the Downstream(S,G) state machine for one of this
(S,G) entry’s outgoing interfaces, indicating that traffic from S
addressed to G should again be forwarded. A Graft message has
been sent to RPF’(S), but a Graft Ack message has not yet been
received.
In addition, there are three state-machine-specific timers:
GraftRetry Timer (GRT(S,G))
This timer is set when a Graft is sent upstream. If a
corresponding GraftAck is not received before the timer expires,
then another Graft is sent, and the GraftRetry Timer is reset.
The timer is stopped when a Graft Ack message is received. This
timer is normally set to Graft_Retry_Period (see 4.8).
Override Timer (OT(S,G))
This timer is set when a Prune(S,G) is received on the upstream
interface where olist(S,G) != NULL. When the timer expires, a
Join(S,G) message is sent on the upstream interface. This timer
is normally set to t_override (see 4.8).
Prune Limit Timer (PLT(S,G))
This timer is used to rate-limit Prunes on a LAN. It is only
used when the Upstream(S,G) state machine is in the Pruned state.
A Prune cannot be sent if this timer is running. This timer is
normally set to t_limit (see 4.8).
+-------------+ +-------------+
| | olist == NULL | |
| Forward |----------------------->| Pruned |
| | | |
+-------------+ +-------------+
^ | ^ |
| | | |
| |RPF`(S) Changes olist == NULL| |
| | | |
| | +-------------+ | |
| +-------->| |----------+ |
| | AckPending | |
+-------------| |<-------------+
Rcv GraftAck OR +-------------+ olist != NULL
Rcv State Refresh
With (P==0) OR
S Directly Connect
Figure 1: Upstream Interface State Machine
In tabular form, the state machine is defined as follows:
+-------------------------------+--------------------------------------+
| | Previous State |
| +------------+------------+------------+
| Event | Forwarding | Pruned | AckPending |
+-------------------------------+------------+------------+------------+
| Data packet arrives on | ->P Send | ->P Send | N/A |
| RPF_Interface(S) AND | Prune(S,G) | Prune(S,G) | |
| olist(S,G) == NULL AND |Set PLT(S,G)|Set PLT(S,G)| |
| PLT(S,G) not running | | | |
+-------------------------------+------------+------------+------------+
| State Refresh(S,G) received | ->F Set | ->P Reset |->AP Set |
| from RPF`(S) AND | OT(S,G) | PLT(S,G) | OT(S,G) |
| Prune Indicator == 1 | | | |
+-------------------------------+------------+------------+------------+
| State Refresh(S,G) received | ->F | ->P Send |->F Cancel |
| from RPF`(S) AND | | Prune(S,G) | GRT(S,G) |
| Prune Indicator == 0 AND | |Set PLT(S,G)| |
| PLT(S,G) not running | | | |
+-------------------------------+------------+------------+------------+
+-------------------------------+--------------------------------------+
| | Previous State |
+ +------------+------------+------------+
| Event | Forwarding | Pruned | AckPending |
+-------------------------------+------------+------------+------------+
| See Join(S,G) to RPF’(S) | ->F Cancel | ->P |->AP Cancel |
| | OT(S,G) | | OT(S,G) |
+-------------------------------+------------+------------+------------+
| See Prune(S,G) | ->F Set | ->P |->AP Set |
| | OT(S,G) | | OT(S,G) |
+-------------------------------+------------+------------+------------+
| OT(S,G) Expires | ->F Send | N/A |->AP Send |
| | Join(S,G) | | Join(S,G) |
+-------------------------------+------------+------------+------------+
| olist(S,G)->NULL | ->P Send | N/A |->P Send |
| | Prune(S,G) | | Prune(S,G) |
| |Set PLT(S,G)| |Set PLT(S,G)|
| | | | Cancel |
| | | | GRT(S,G) |
+-------------------------------+------------+------------+------------+
| olist(S,G)->non-NULL | N/A | ->AP Send | N/A |
| | | Graft(S,G) | |
| | |Set GRT(S,G)| |
+-------------------------------+------------+------------+------------+
| RPF’(S) Changes AND | ->AP Send | ->AP Send |->AP Send |
| olist(S,G) != NULL | Graft(S,G) | Graft(S,G) | Graft(S,G) |
| |Set GRT(S,G)|Set GRT(S,G)|Set GRT(S,G)|
+-------------------------------+------------+------------+------------+
| RPF’(S) Changes AND | ->P | ->P Cancel |->P Cancel |
| olist(S,G) == NULL | | PLT(S,G) | GRT(S,G) |
+-------------------------------+------------+------------+------------+
| S becomes directly connected | ->F | ->P |->F Cancel |
| | | | GRT(S,G) |
+-------------------------------+------------+------------+------------+
| GRT(S,G) Expires | N/A | N/A |->AP Send |
| | | | Graft(S,G) |
| | | |Set GRT(S,G)|
+-------------------------------+------------+------------+------------+
| Receive GraftAck(S,G) from | ->F | ->P |->F Cancel |
| RPF’(S) | | | GRT(S,G) |
+-------------------------------+------------+------------+------------+
The transition event "RcvGraftAck(S,G)" implies receiving a Graft Ack
message targeted to this router’s address on the incoming interface
for the (S,G) entry. If the destination address is not correct, the
state transitions in this state machine must not occur.
4.4.1.1. Transitions from the Forwarding (F) State
When the Upstream(S,G) state machine is in the Forwarding (F) state,
the following events may trigger a transition:
Data Packet arrives on RPF_Interface(S) AND olist(S,G) == NULL AND
S NOT directly connected
The Upstream(S,G) state machine MUST transition to the Pruned (P)
state, send a Prune(S,G) to RPF’(S), and set PLT(S,G) to t_limit
seconds.
State Refresh(S,G) Received from RPF’(S)
The Upstream(S,G) state machine remains in a Forwarding state.
If the received State Refresh has the Prune Indicator bit set to
one, this router must override the upstream router’s Prune state
after 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.
See Join(S,G) to RPF’(S)
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 Forwarding (F) state.
See Prune(S,G) AND S NOT directly connected
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 Forwarding 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 Forwarding (F) state.
OT(S,G) Expires AND S NOT directly connected
The OverrideTimer (OT(S,G)) expires. The router MUST send a
Join(S,G) to RPF’(S) to override a previously detected prune.
The Upstream(S,G) state machine remains in the Forwarding (F)
state.
olist(S,G) -> NULL AND S NOT directly connected
The Upstream(S,G) state machine MUST transition to the Pruned (P)
state, send a Prune(S,G) to RPF’(S), and set PLT(S,G) to t_limit
seconds.
RPF’(S) Changes AND olist(S,G) is non-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 AckPending (AP) state, unicast a
Graft to the new RPF’(S), and set the GraftRetry Timer (GRT(S,G))
to Graft_Retry_Period.
RPF’(S) Changes AND olist(S,G) is NULL
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.
4.4.1.2. Transitions from the Pruned (P) State
When the Upstream(S,G) state machine is in the Pruned (P) state, the
following events may trigger a transition:
Data arrives on RPF_interface(S) AND PLT(S,G) not running AND S NOT
directly connected
Either another router on the LAN desires traffic from S addressed
to G or a previous Prune was lost. To prevent generating a
Prune(S,G) in response to every data packet, the PruneLimit Timer
(PLT(S,G)) is used. Once the PLT(S,G) expires, the router needs
to send another prune in response to a data packet not received
directly from the source. A Prune(S,G) MUST be sent to RPF’(S),
and the PLT(S,G) MUST be set to t_limit.
State Refresh(S,G) Received from RPF’(S)
The Upstream(S,G) state machine remains in a Pruned state. If
the State Refresh has its Prune Indicator bit set to zero and
PLT(S,G) is not running, a Prune(S,G) MUST be sent to RPF’(S),
and the PLT(S,G) MUST be set to t_limit. If the State Refresh
has its Prune Indicator bit set to one, the router MUST reset
PLT(S,G) to t_limit.
See Prune(S,G) to RPF’(S)
A Prune(S,G) is seen on RPF_interface(S) to RPF’(S). The
Upstream(S,G) state machine stays in the Pruned (P) state. The
router MAY reset its PLT(S,G) to the value in the Holdtime field
of the received message if it is greater than the current value
of the PLT(S,G).
olist(S,G)->non-NULL AND S NOT directly connected
The set of interfaces defined by the olist(S,G) macro becomes
non-empty, indicating that traffic from S addressed to group G
must be forwarded. The Upstream(S,G) state machine MUST cancel
PLT(S,G), transition to the AckPending (AP) state and unicast a
Graft message to RPF’(S). The Graft Retry Timer (GRT(S,G)) MUST
be set to Graft_Retry_Period.
RPF’(S) Changes AND olist(S,G) == non-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 cancel PLT(S,G), transition to the AckPending (AP)
state, send a Graft unicast to the new RPF’(S), and set the
GraftRetry Timer (GRT(S,G)) 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 stays in the Pruned (P) state and MUST cancel the
PLT(S,G) timer.
S becomes directly connected
Unicast routing changed so that S is directly connected. The
Upstream(S,G) state machine remains in the Pruned (P) state.
4.4.1.3. Transitions from the AckPending (AP) State
When the Upstream(S,G) state machine is in the AckPending (AP) state,
the following events may trigger a transition:
State Refresh(S,G) Received from RPF’(S) with Prune Indicator == 1
The Upstream(S,G) state machine remains in an AckPending state.
The router must override the upstream router’s Prune state after