tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search

RFC 3973

 
 
 

Protocol Independent Multicast - Dense Mode (PIM-DM): Protocol Specification (Revised)

Part 2 of 3, p. 13 to 38
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 13 
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.

Top      Up      ToC       Page 14 
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).

Top      Up      ToC       Page 15 
          +-------------+                        +-------------+
          |             |     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          |            |            |            |
+-------------------------------+------------+------------+------------+

Top      Up      ToC       Page 16 
+-------------------------------+--------------------------------------+
|                               |            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.

Top      Up      ToC       Page 17 
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.

Top      Up      ToC       Page 18 
     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

Top      Up      ToC       Page 19 
       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
       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.

Top      Up      ToC       Page 20 
     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.

Top      Up      ToC       Page 21 
     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.

Top      Up      ToC       Page 22 
     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

Top      Up      ToC       Page 23 
   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

Top      Up      ToC       Page 24 
       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.

Top      Up      ToC       Page 25 
     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.

Top      Up      ToC       Page 26 
     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;

Top      Up      ToC       Page 27 
     } 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.

Top      Up      ToC       Page 28 
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

Top      Up      ToC       Page 29 
   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) |
|                                  |               |   Cancel SAT(S,G) |
+----------------------------------+---------------+-------------------+

4.5.2.1.  Transitions from the NotOriginator (NO) State

   When the Originating(S,G) state machine is in the NotOriginator (NO)
   state, the following event may trigger a transition:

     Data Packet received from directly connected Source S addressed to
     group G
       The router MUST transition to an Originator (O) state, set
       SAT(S,G) to SourceLifetime, and set SRT(S,G) to
       StateRefreshInterval.  The router SHOULD record the TTL of the
       packet for use in State Refresh messages.

4.5.2.2.  Transitions from the Originator (O) State

   When the Originating(S,G) state machine is in the Originator (O)
   state, the following events may trigger a transition:

     Receive Data Packet from S addressed to G
       The router remains in the Originator (O) state and MUST reset
       SAT(S,G) to SourceLifetime.  The router SHOULD increase its
       recorded TTL to match the TTL of the packet, if the packet's TTL
       is larger than the previously recorded TTL.  A router MAY record
       the TTL based on an implementation specific sampling policy to
       avoid examining the TTL of every multicast packet it handles.

Top      Up      ToC       Page 30 
     SRT(S,G) Expires
       The router remains in the Originator (O) state and MUST reset
       SRT(S,G) to StateRefreshInterval.  The router MUST also generate
       State Refresh messages for transmission, as described in the
       State Refresh Forwarding rules (Section 4.5.1), except for the
       TTL.  If the TTL of data packets from S to G are being recorded,
       then the TTL of each State Refresh message is set to the highest
       recorded TTL.  Otherwise, the TTL is set to the configured State
       Refresh TTL.  Let I denote the interface over which a State
       Refresh message is being sent.  If the Prune(S,G) Downstream
       state machine is in the Pruned (P) state, then the Prune-
       Indicator bit MUST be set to 1 in the State Refresh message being
       sent over I. Otherwise, the Prune-Indicator bit MUST be set to 0.

     SAT(S,G) Expires
       The router MUST cancel the SRT(S,G) timer and transition to the
       NotOriginator (NO) state.

     S is no longer directly connected
       The router MUST transition to the NotOriginator (NO) state and
       cancel both the SAT(S,G) and SRT(S,G).

4.6.  PIM Assert Messages

4.6.1.  Assert Metrics

   Assert metrics are defined as follows:

   struct assert_metric {
     metric_preference;
     route_metric;
     ip_address;
   };

   When assert_metrics are compared, the metric_preference and
   route_metric field are compared in order, where the first lower value
   wins.  If all fields are equal, the IP address of the router that
   sourced the Assert message is used as a tie-breaker, with the highest
   IP address winning.

Top      Up      ToC       Page 31 
   An Assert metric for (S,G) to include in (or compare against) an
   Assert message sent on interface I should be computed by using the
   following pseudocode:

   assert_metric
   my_assert_metric(S,G,I) {
     if (CouldAssert(S,G,I) == TRUE) {
       return spt_assert_metric(S,G,I)
     } else {
       return infinite_assert_metric()
     }
   }

   spt_assert_metric(S,I) gives the Assert metric we use if we're
   sending an Assert based on active (S,G) forwarding state:

   assert_metric
   spt_assert_metric(S,I) {
     return {0,MRIB.pref(S),MRIB.metric(S),my_addr(I)}
   }

   MRIB.pref(X) and MRIB.metric(X) are the routing preference and
   routing metrics associated with the route to a particular (unicast)
   destination X, as determined by the MRIB.  my_addr(I) is simply the
   router's network (e.g., IP) address associated with the local
   interface I.

   infinite_assert_metric() gives the Assert metric we need to send an
   Assert but doesn't match (S,G) forwarding state:

   assert_metric
   infinite_assert_metric() {
     return {1,infinity,infinity,0}
   }

4.6.2.  AssertCancel Messages

   An AssertCancel(S,G) message is simply an Assert message for (S,G)
   with infinite metric.  The Assert winner sends this message when it
   changes its upstream interface to this interface.  Other routers will
   see this metric, causing those with forwarding state to send their
   own Asserts and re-establish an Assert winner.

   AssertCancel messages are simply an optimization.  The original
   Assert timeout mechanism will eventually allow a subnet to become
   consistent; the AssertCancel mechanism simply causes faster
   convergence.  No special processing is required for an AssertCancel
   message, as it is simply an Assert message from the current winner.

Top      Up      ToC       Page 32 
4.6.3.  Assert State Macros

   The macro lost_assert(S,G,I), is used in the olist computations of
   Section 4.1.3, and is defined as follows:

   bool lost_assert(S,G,I) {
     if ( RPF_interface(S) == I ) {
       return FALSE
     } else {
       return (AssertWinner(S,G,I) != me  AND
               (AssertWinnerMetric(S,G,I) is better than
                spt_assert_metric(S,G,I)))
     }
   }

   AssertWinner(S,G,I) defaults to NULL, and AssertWinnerMetric(S,G,I)
   defaults to Infinity when in the NoInfo state.

4.6.4.  (S,G) Assert Message State Machine

   The (S,G) Assert state machine for interface I is shown in Figure 4.
   There are three states:

     NoInfo (NI)
       This router has no (S,G) Assert state on interface I.

     I am Assert Winner (W)
       This router has won an (S,G) Assert on interface I.  It is now
       responsible for forwarding traffic from S destined for G via
       interface I.

     I am Assert Loser (L)
       This router has lost an (S,G) Assert on interface I.  It must not
       forward packets from S destined for G onto interface I.

   In addition, an Assert Timer (AT(S,G,I)) is used to time out the
   Assert state.

Top      Up      ToC       Page 33 
         +-------------+                        +-------------+
         |             | Rcv Pref Assert or SR  |             |
         |   Winner    |----------------------->|    Loser    |
         |             |                        |             |
         +-------------+                        +-------------+
              ^   |                                  ^   |
              |   |                Rcv Pref Assert or|   |
              |   |AT Expires OR        State Refresh|   |
              |   |CouldAssert->FALSE                |   |
              |   |                                  |   |
              |   |         +-------------+          |   |
              |   +-------->|             |----------+   |
              |             |   No Info   |              |
              +-------------|             |<-------------+
       Rcv Data from dnstrm +-------------+ Rcv Inf Assert from Win OR
     OR Rcv Inferior Assert                 Rcv Inf SR from Winner OR
         OR Rcv Inferior SR                 AT Expires OR
                                            CouldAssert Changes OR
                                            Winner's NLT Expires

                     Figure 4: Assert State Machine

   In tabular form, the state machine is defined as follows:

+-------------------------------+--------------------------------------+
|                               |            Previous State            |
|                               +------------+------------+------------+
|            Event              |  No Info   |   Winner   |    Loser   |
+-------------------------------+------------+------------+------------+
| An (S,G) Data packet received | ->W Send   | ->W Send   | ->L        |
| on downstream interface       | Assert(S,G)| Assert(S,G)|            |
|                               |    Set     |    Set     |            |
|                               |  AT(S,G,I) |  AT(S,G,I) |            |
+-------------------------------+--------------------------------------+
| Receive Inferior (Assert OR   | N/A        | N/A        |->NI Cancel |
| State Refresh) from Assert    |            |            |  AT(S,G,I) |
| Winner                        |            |            |            |
+-------------------------------+--------------------------------------+
| Receive Inferior (Assert OR   | ->W Send   | ->W Send   | ->L        |
| State Refresh) from non-Assert| Assert(S,G)| Assert(S,G)|            |
| Winner AND CouldAssert==TRUE  |    Set     |    Set     |            |
|                               |  AT(S,G,I) |  AT(S,G,I) |            |
+-------------------------------+--------------------------------------+

Top      Up      ToC       Page 34 
+-------------------------------+--------------------------------------+
|                               |            Previous State            |
|                               +------------+------------+------------+
|            Event              |  No Info   |   Winner   |    Loser   |
+-------------------------------+------------+------------+------------+
| Receive Preferred Assert OR   | ->L Send   | ->L Send   | ->L  Set   |
| State Refresh                 | Prune(S,G) | Prune(S,G) |  AT(S,G,I) |
|                               |    Set     |    Set     |            |
|                               |  AT(S,G,I) |  AT(S,G,I) |            |
+-------------------------------+--------------------------------------+
| Send State Refresh            | ->NI       | ->W Reset  | N/A        |
|                               |            |  AT(S,G,I) |            |
+-------------------------------+--------------------------------------+
| AT(S,G) Expires               | N/A        | ->NI       | ->NI       |
+-------------------------------+--------------------------------------+
| CouldAssert -> FALSE          | ->NI       |->NI Cancel |->NI Cancel |
|                               |            |  AT(S,G,I) |  AT(S,G,I) |
+-------------------------------+--------------------------------------+
| CouldAssert -> TRUE           | ->NI       | N/A        |->NI Cancel |
|                               |            |            |  AT(S,G,I) |
+-------------------------------+--------------------------------------+
| Winner's NLT(N,I) Expires     | N/A        | N/A        |->NI Cancel |
|                               |            |            |  AT(S,G,I) |
+-------------------------------+--------------------------------------+
| Receive Prune(S,G), Join(S,G) | ->NI       | ->W        | ->L Send   |
| or Graft(S,G)                 |            |            | Assert(S,G)|
+-------------------------------+--------------------------------------+

   Terminology: A "preferred assert" is one with a better metric than
   the current winner.  An "inferior assert" is one with a worse metric
   than my_assert_metric(S,G,I).

   The state machine uses the following macro:

   CouldAssert(S,G,I) = (RPF_interface(S) != I)

4.6.4.1.  Transitions from NoInfo State

   In the NoInfo state, the following events may trigger transitions:

     An (S,G) data packet arrives on downstream interface I
       An (S,G) data packet arrived on a downstream interface.  It is
       optimistically assumed that this router will be the Assert winner
       for this (S,G).  The Assert state machine MUST transition to the
       "I am Assert Winner" state, send an Assert(S,G) to interface I,
       store its own address and metric as the Assert Winner, and set
       the Assert_Timer (AT(S,G,I) to Assert_Time, thereby initiating
       the Assert negotiation for (S,G).

Top      Up      ToC       Page 35 
     Receive Inferior (Assert OR State Refresh) AND
     CouldAssert(S,G,I)==TRUE
       An Assert or State Refresh is received for (S,G) that is inferior
       to our own assert metric on interface I. The Assert state machine
       MUST transition to the "I am Assert Winner" state, send an
       Assert(S,G) to interface I, store its own address and metric as
       the Assert Winner, and set the Assert Timer (AT(S,G,I)) to
       Assert_Time.

     Receive Preferred Assert or State Refresh
       The received Assert or State Refresh has a better metric than
       this router's, and therefore the Assert state machine MUST
       transition to the "I am Assert Loser" state and store the Assert
       Winner's address and metric.  If the metric was received in an
       Assert, the router MUST set the Assert Timer (AT(S,G,I)) to
       Assert_Time.  If the metric was received in a State Refresh, the
       router MUST set the Assert Timer (AT(S,G,I)) to three times the
       received State Refresh Interval.  If CouldAssert(S,G,I) == TRUE,
       the router MUST also multicast a Prune(S,G) to the Assert winner
       with a Prune Hold Time equal to the Assert Timer and evaluate any
       changes in its Upstream(S,G) state machine.

4.6.4.2.  Transitions from Winner State

   When in "I am Assert Winner" state, the following events trigger
   transitions:

     An (S,G) data packet arrives on downstream interface I
       An (S,G) data packet arrived on a downstream interface.  The
       Assert state machine remains in the "I am Assert Winner" state.
       The router MUST send an Assert(S,G) to interface I and set the
       Assert Timer (AT(S,G,I) to Assert_Time.

     Receive Inferior Assert or State Refresh
       An (S,G) Assert is received containing a metric for S that is
       worse than this router's metric for S.  Whoever sent the Assert
       is in error.  The router MUST send an Assert(S,G) to interface I
       and reset the Assert Timer (AT(S,G,I)) to Assert_Time.

     Receive Preferred Assert or State Refresh
       An (S,G) Assert or State Refresh is received that has a better
       metric than this router's metric for S on interface I.  The
       Assert state machine MUST transition to "I am Assert Loser" state
       and store the new Assert Winner's address and metric.  If the
       metric was received in an Assert, the router MUST set the Assert
       Timer (AT(S,G,I)) to Assert_Time.  If the metric was received in
       a State Refresh, the router MUST set the Assert Timer (AT(S,G,I))
       to three times the State Refresh Interval.  The router MUST also

Top      Up      ToC       Page 36 
       multicast a Prune(S,G) to the Assert winner, with a Prune Hold
       Time equal to the Assert Timer, and evaluate any changes in its
       Upstream(S,G) state machine.

     Send State Refresh
       The router is sending a State Refresh(S,G) message on interface
       I.  The router MUST set the Assert Timer (AT(S,G,I)) to three
       times the State Refresh Interval contained in the State
       Refresh(S,G) message.

     AT(S,G,I) Expires
       The (S,G) Assert Timer (AT(S,G,I)) expires.  The Assert state
       machine MUST transition to the NoInfo (NI) state.

     CouldAssert(S,G,I) -> FALSE
       This router's RPF interface changed, making CouldAssert(S,G,I)
       false.  This router can no longer perform the actions of the
       Assert winner, so the Assert state machine MUST transition to
       NoInfo (NI) state, send an AssertCancel(S,G) to interface I,
       cancel the Assert Timer (AT(S,G,I)), and remove itself as the
       Assert Winner.

4.6.4.3.  Transitions from Loser State

   When in "I am Assert Loser" state, the following transitions can
   occur:

     Receive Inferior Assert or State Refresh from Current Winner
       An Assert or State Refresh is received from the current Assert
       winner that is worse than this router's metric for S (typically,
       the winner's metric became worse).  The Assert state machine MUST
       transition to NoInfo (NI) state and cancel AT(S,G,I).  The router
       MUST delete the previous Assert Winner's address and metric and
       evaluate any possible transitions to its Upstream(S,G) state
       machine.  Usually this router will eventually re-assert and win
       when data packets from S have started flowing again.

     Receive Preferred Assert or State Refresh
       An Assert or State Refresh is received that has a metric better
       than or equal to that of the current Assert winner.  The Assert
       state machine remains in Loser (L) state.  If the metric was
       received in an Assert, the router MUST set the Assert Timer
       (AT(S,G,I)) to Assert_Time.  If the metric was received in a
       State Refresh, the router MUST set the Assert Timer (AT(S,G,I))
       to three times the received State Refresh Interval.  If the
       metric is better than the current Assert Winner, the router MUST

Top      Up      ToC       Page 37 
       store the address and metric of the new Assert Winner, and if
       CouldAssert(S,G,I) == TRUE, the router MUST multicast a
       Prune(S,G) to the new Assert winner.

     AT(S,G,I) Expires
       The (S,G) Assert Timer (AT(S,G,I)) expires.  The Assert state
       machine MUST transition to NoInfo (NI) state.  The router MUST
       delete the Assert Winner's address and metric.  If CouldAssert ==
       TRUE, the router MUST evaluate any possible transitions to its
       Upstream(S,G) state machine.

     CouldAssert -> FALSE
       CouldAssert has become FALSE because interface I has become the
       RPF interface for S.  The Assert state machine MUST transition to
       NoInfo (NI) state, cancel AT(S,G,I), and delete information
       concerning the Assert Winner on I.

     CouldAssert -> TRUE
       CouldAssert has become TRUE because interface I used to be the
       RPF interface for S, and now it is not.  The Assert state machine
       MUST transition to NoInfo (NI) state, cancel AT(S,G,I), and
       delete information concerning the Assert Winner on I.

     Current Assert Winner's NeighborLiveness Timer Expires
       The current Assert winner's NeighborLiveness Timer (NLT(N,I)) has
       expired.  The Assert state machine MUST transition to the NoInfo
       (NI) state, delete the Assert Winner's address and metric, and
       evaluate any possible transitions to its Upstream(S,G) state
       machine.

     Receive Prune(S,G), Join(S,G), or Graft(S,G)
       A Prune(S,G), Join(S,G), or Graft(S,G) message was received on
       interface I with its upstream neighbor address set to the
       router's address on I.  The router MUST send an Assert(S,G) on
       the receiving interface I to initiate an Assert negotiation.  The
       Assert state machine remains in the Assert Loser(L) state.  If a
       Graft(S,G) was received, the router MUST respond with a
       GraftAck(S,G).

Top      Up      ToC       Page 38 
4.6.5.  Rationale for Assert Rules

   The following is a summary of the rules for generating and processing
   Assert messages.  It is not intended to be definitive (the state
   machines and pseudocode provide the definitive behavior).  Instead,
   it provides some rationale for the behavior.

   1. The Assert winner for (S,G) must act as the local forwarder for
      (S,G) on behalf of all downstream members.
   2. PIM messages are directed to the RPF' neighbor and not to the
      regular RPF neighbor.
   3. An Assert loser that receives a Prune(S,G), Join(S,G), or
      Graft(S,G) directed to it initiates a new Assert negotiation so
      that the downstream router can correct its RPF'(S).
   4. An Assert winner for (S,G) sends a cancelling assert when it is
      about to stop forwarding on an (S,G) entry.  Example: If a router
      is being taken down, then a canceling assert is sent.



(page 38 continued on part 3)

Next RFC Part