tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Gloss.     Arch.     IMS     UICC    |    Misc.    |    search     info

RFC 7761

 
 
 

Protocol Independent Multicast - Sparse Mode (PIM-SM): Protocol Specification (Revised)

Part 4 of 7, p. 44 to 76
Prev RFC Part       Next RFC Part

 


prevText      Top      ToC       Page 44 
4.5.  PIM Join/Prune Messages

   A PIM Join/Prune message consists of a list of groups and a list of
   Joined and Pruned sources for each group.  When processing a received
   Join/Prune message, each Joined or Pruned source for a group is
   effectively considered individually, and applies to one or more of
   the following state machines.  When considering a Join/Prune message
   whose Upstream Neighbor Address field addresses this router, (*,G)
   Joins and Prunes can affect both the (*,G) and (S,G,rpt) downstream
   state machines, while (S,G), and (S,G,rpt) Joins and Prunes can only
   affect their respective downstream state machines.  When considering

Top      Up      ToC       Page 45 
   a Join/Prune message whose Upstream Neighbor Address field addresses
   another router, most Join or Prune messages could affect each
   upstream state machine.

   In general, a PIM Join/Prune message should only be accepted for
   processing if it comes from a known PIM neighbor.  A PIM router hears
   about PIM neighbors through PIM Hello messages.  If a router receives
   a Join/Prune message from a particular IP source address and it has
   not seen a PIM Hello message from that source address, then the
   Join/Prune message SHOULD be discarded without further processing.
   In addition, if the Hello message from a neighbor was authenticated
   (see Section 6.3), then all Join/Prune messages from that neighbor
   MUST also be authenticated.

   We note that some older PIM implementations incorrectly fail to send
   Hello messages on point-to-point interfaces, so we also RECOMMEND
   that a configuration option be provided to allow interoperation with
   such older routers, but that this configuration option SHOULD NOT be
   enabled by default.

4.5.1.  Receiving (*,G) Join/Prune Messages

   When a router receives a Join(*,G), it must first check to see
   whether the RP in the message matches RP(G) (the router's idea of who
   the RP is).  If the RP in the message does not match RP(G), the
   Join(*,G) should be silently dropped.  (Note that other source list
   entries, such as (S,G,rpt) or (S,G), in the same Group-Specific Set
   should still be processed.)  If a router has no RP information (e.g.,
   has not recently received a BSR message), then it may choose to
   accept Join(*,G) and treat the RP in the message as RP(G).  Received
   Prune(*,G) messages are processed even if the RP in the message does
   not match RP(G).

Top      Up      ToC       Page 46 
   The per-interface state machine for receiving (*,G) Join/Prune
   messages is given below.  There are three states:

      NoInfo (NI)
            The interface has no (*,G) Join state and no timers running.

      Join (J)
            The interface has (*,G) Join state, which will cause the
            router to forward packets destined for G from this interface
            except if there is also (S,G,rpt) prune information (see
            Section 4.5.3) or the router lost an assert on this
            interface.

      Prune-Pending (PP)
            The router has received a Prune(*,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 Prune-Pending state functions
            exactly like the Join state.

   In addition, the state machine uses two timers:

      Expiry Timer (ET)
            This timer is restarted when a valid Join(*,G) is received.
            Expiry of the Expiry Timer causes the interface state to
            revert to NoInfo for this group.

      Prune-Pending Timer (PPT)
            This timer is set when a valid Prune(*,G) is received.
            Expiry of the Prune-Pending Timer causes the interface state
            to revert to NoInfo for this group.

Top      Up      ToC       Page 47 
         Figure 2: Downstream Per-Interface (*,G) State Machine

+------------++--------------------------------------------------------+
|            ||                         Event                          |
|            ++-------------+--------------+-------------+-------------+
|Prev State  ||Receive      | Receive      | Prune-      | Expiry Timer|
|            ||Join(*,G)    | Prune(*,G)   | Pending     | Expires     |
|            ||             |              | Timer       |             |
|            ||             |              | Expires     |             |
+------------++-------------+--------------+-------------+-------------+
|            ||-> J state   | -> NI state  | -           | -           |
|NoInfo (NI) ||start Expiry |              |             |             |
|            ||Timer        |              |             |             |
+------------++-------------+--------------+-------------+-------------+
|            ||-> J state   | -> PP state  | -           | -> NI state |
|Join (J)    ||restart      | start Prune- |             |             |
|            ||Expiry Timer | Pending      |             |             |
|            ||             | Timer        |             |             |
+------------++-------------+--------------+-------------+-------------+
|Prune-      ||-> J state   | -> PP state  | -> NI state | -> NI state |
|Pending (PP)||restart      |              | Send Prune- |             |
|            ||Expiry Timer |              | Echo(*,G)   |             |
+------------++-------------+--------------+-------------+-------------+

   The transition events "Receive Join(*,G)" and "Receive Prune(*,G)"
   imply receiving a Join or Prune targeted to this router's primary IP
   address on the received interface.  If the upstream neighbor address
   field is not correct, these state transitions in this state machine
   MUST NOT occur, although seeing such a packet may cause state
   transitions in other state machines.

   On unnumbered interfaces on point-to-point links, the router's
   address should be the same as the source address it chose for the
   Hello message it sent over that interface.  However, on point-to-
   point links it is RECOMMENDED that for backwards compatibility PIM
   Join/Prune messages with an upstream neighbor address field of all
   zeros also be accepted.

Top      Up      ToC       Page 48 
   Transitions from NoInfo State

   When in NoInfo state, the following event may trigger a transition:

      Receive Join(*,G)
            A Join(*,G) is received on interface I with its Upstream
            Neighbor Address set to the router's primary IP address
            on I.

            The (*,G) downstream state machine on interface I
            transitions to the Join state.  The Expiry Timer (ET) is
            started and set to the HoldTime from the triggering
            Join/Prune message.

   Transitions from Join State

   When in Join state, the following events may trigger a transition:

      Receive Join(*,G)
            A Join(*,G) is received on interface I with its Upstream
            Neighbor Address set to the router's primary IP address
            on I.

            The (*,G) downstream state machine on interface I remains in
            Join state, and the Expiry Timer (ET) is restarted.  The ET
            is set to the maximum of its current value and the HoldTime
            from the triggering Join/Prune message.

      Receive Prune(*,G)
            A Prune(*,G) is received on interface I with its Upstream
            Neighbor Address set to the router's primary IP address
            on I.

            The (*,G) downstream state machine on interface I
            transitions to the Prune-Pending state.  The
            Prune-Pending Timer is started.  It is set to the
            J/P_Override_Interval(I) if the router has more than one
            neighbor on that interface; otherwise, it is set to zero,
            causing it to expire immediately.

      Expiry Timer Expires
            The Expiry Timer for the (*,G) downstream state machine on
            interface I expires.

            The (*,G) downstream state machine on interface I
            transitions to the NoInfo state.

Top      Up      ToC       Page 49 
   Transitions from Prune-Pending State

   When in Prune-Pending state, the following events may trigger a
   transition:

      Receive Join(*,G)
            A Join(*,G) is received on interface I with its Upstream
            Neighbor Address set to the router's primary IP address
            on I.

            The (*,G) downstream state machine on interface I
            transitions to the Join state.  The Prune-Pending Timer is
            canceled (without triggering an expiry event).  The
            Expiry Timer (ET) is restarted and is then set to the
            maximum of its current value and the HoldTime from the
            triggering Join/Prune message.

      Expiry Timer Expires
            The Expiry Timer for the (*,G) downstream state machine on
            interface I expires.

            The (*,G) downstream state machine on interface I
            transitions to the NoInfo state.

      Prune-Pending Timer Expires
            The Prune-Pending Timer for the (*,G) downstream state
            machine on interface I expires.

            The (*,G) downstream state machine on interface I
            transitions to the NoInfo state.  A PruneEcho(*,G) is sent
            onto the subnet connected to interface I.

            The action "Send PruneEcho(*,G)" is triggered when the
            router stops forwarding on an interface as a result of a
            prune.  A PruneEcho(*,G) is simply a Prune(*,G) message sent
            by the upstream router on a LAN with its own address in the
            Upstream Neighbor Address field.  Its purpose is to add
            additional reliability so that if a Prune that should have
            been overridden by another router is lost locally on the
            LAN, then the PruneEcho may be received and cause the
            override to happen.  A PruneEcho(*,G) need not be sent on an
            interface that contains only a single PIM neighbor during
            the time this state machine was in Prune-Pending state.

Top      Up      ToC       Page 50 
4.5.2.  Receiving (S,G) Join/Prune Messages

   The per-interface state machine for receiving (S,G) Join/Prune
   messages is given below and is almost identical to that for (*,G)
   messages.  There are three states:

      NoInfo (NI)
            The interface has no (S,G) Join state and no (S,G) timers
            running.

      Join (J)
            The interface has (S,G) Join state, which will cause the
            router to forward packets from S destined for G from this
            interface if the (S,G) state is active (the SPTbit is set)
            except if the router lost an assert on this interface.

      Prune-Pending (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 Prune-Pending state functions
            exactly like the Join state.

   In addition, there are two timers:

      Expiry Timer (ET)
            This timer is set when a valid Join(S,G) is received.
            Expiry of the Expiry Timer causes this state machine to
            revert to NoInfo state.

      Prune-Pending Timer (PPT)
            This timer is set when a valid Prune(S,G) is received.
            Expiry of the Prune-Pending Timer causes this state machine
            to revert to NoInfo state.

Top      Up      ToC       Page 51 
         Figure 3: Downstream Per-Interface (S,G) State Machine

+------------++--------------------------------------------------------+
|            ||                         Event                          |
|            ++-------------+--------------+-------------+-------------+
|Prev State  ||Receive      | Receive      | Prune-      | Expiry Timer|
|            ||Join(S,G)    | Prune(S,G)   | Pending     | Expires     |
|            ||             |              | Timer       |             |
|            ||             |              | Expires     |             |
+------------++-------------+--------------+-------------+-------------+
|            ||-> J state   | -> NI state  | -           | -           |
|NoInfo (NI) ||start Expiry |              |             |             |
|            ||Timer        |              |             |             |
+------------++-------------+--------------+-------------+-------------+
|            ||-> J state   | -> PP state  | -           | -> NI state |
|Join (J)    ||restart      | start Prune- |             |             |
|            ||Expiry Timer | Pending      |             |             |
|            ||             | Timer        |             |             |
+------------++-------------+--------------+-------------+-------------+
|Prune-      ||-> J state   | -> PP state  | -> NI state | -> NI state |
|Pending (PP)||restart      |              | Send Prune- |             |
|            ||Expiry Timer |              | Echo(S,G)   |             |
+------------++-------------+--------------+-------------+-------------+

   The transition events "Receive Join(S,G)" and "Receive Prune(S,G)"
   imply receiving a Join or Prune targeted to this router's primary IP
   address on the received interface.  If the upstream neighbor address
   field is not correct, these state transitions in this state machine
   MUST NOT occur, although seeing such a packet may cause state
   transitions in other state machines.

   On unnumbered interfaces on point-to-point links, the router's
   address SHOULD be the same as the source address it chose for the
   Hello message it sent over that interface.  However, on point-to-
   point links it is RECOMMENDED that for backwards compatibility PIM
   Join/Prune messages with an upstream neighbor address field of all
   zeros also be accepted.

Top      Up      ToC       Page 52 
   Transitions from NoInfo State

   When in NoInfo state, the following event may trigger a transition:

      Receive Join(S,G)
            A Join(S,G) is received on interface I with its Upstream
            Neighbor Address set to the router's primary IP address
            on I.

            The (S,G) downstream state machine on interface I
            transitions to the Join state.  The Expiry Timer (ET) is
            started and set to the HoldTime from the triggering
            Join/Prune message.

   Transitions from Join State

   When in Join state, the following events may trigger a transition:

      Receive Join(S,G)
            A Join(S,G) is received on interface I with its Upstream
            Neighbor Address set to the router's primary IP address
            on I.

            The (S,G) downstream state machine on interface I remains in
            Join state.  The Expiry Timer (ET) is restarted and is then
            set to the maximum of its current value and the HoldTime
            from the triggering Join/Prune message.

      Receive Prune(S,G)
            A Prune(S,G) is received on interface I with its Upstream
            Neighbor Address set to the router's primary IP address
            on I.

            The (S,G) downstream state machine on interface I
            transitions to the Prune-Pending state.  The
            Prune-Pending Timer is started.  It is set to the
            J/P_Override_Interval(I) if the router has more than one
            neighbor on that interface; otherwise, it is set to zero,
            causing it to expire immediately.

      Expiry Timer Expires
            The Expiry Timer for the (S,G) downstream state machine on
            interface I expires.

            The (S,G) downstream state machine on interface I
            transitions to the NoInfo state.

Top      Up      ToC       Page 53 
   Transitions from Prune-Pending State

   When in Prune-Pending state, the following events may trigger a
   transition:

      Receive Join(S,G)
            A Join(S,G) is received on interface I with its Upstream
            Neighbor Address set to the router's primary IP address
            on I.

            The (S,G) downstream state machine on interface I
            transitions to the Join state.  The Prune-Pending Timer is
            canceled (without triggering an expiry event).  The
            Expiry Timer (ET) is restarted and is then set to the
            maximum of its current value and the HoldTime from the
            triggering Join/Prune message.

      Expiry Timer Expires
            The Expiry Timer for the (S,G) downstream state machine on
            interface I expires.

            The (S,G) downstream state machine on interface I
            transitions to the NoInfo state.

      Prune-Pending Timer Expires
            The Prune-Pending Timer for the (S,G) downstream state
            machine on interface I expires.

            The (S,G) downstream state machine on interface I
            transitions to the NoInfo state.  A PruneEcho(S,G) is sent
            onto the subnet connected to interface I.

            The action "Send PruneEcho(S,G)" is triggered when the
            router stops forwarding on an interface as a result of a
            prune.  A PruneEcho(S,G) is simply a Prune(S,G) message sent
            by the upstream router on a LAN with its own address in the
            Upstream Neighbor Address field.  Its purpose is to add
            additional reliability so that if a Prune that should have
            been overridden by another router is lost locally on the
            LAN, then the PruneEcho may be received and cause the
            override to happen.  A PruneEcho(S,G) need not be sent on an
            interface that contains only a single PIM neighbor during
            the time this state machine was in Prune-Pending state.

Top      Up      ToC       Page 54 
4.5.3.  Receiving (S,G,rpt) Join/Prune Messages

   The per-interface state machine for receiving (S,G,rpt) Join/Prune
   messages is given below.  There are five states:

      NoInfo (NI)
            The interface has no (S,G,rpt) Prune state and no (S,G,rpt)
            timers running.

      Prune (P)
            The interface has (S,G,rpt) Prune state, which will cause
            the router not to forward packets from S destined for G from
            this interface even though the interface has active (*,G)
            Join state.

      Prune-Pending (PP)
            The router has received a Prune(S,G,rpt) 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 Prune-Pending state functions
            exactly like the NoInfo state.

      PruneTmp (P')
            This state is a transient state that for forwarding purposes
            behaves exactly like the Prune state.  A (*,G) Join has been
            received (which may cancel the (S,G,rpt) Prune).  As we
            parse the Join/Prune message from top to bottom, we first
            enter this state if the message contains a (*,G) Join.
            Later in the message, we will normally encounter an
            (S,G,rpt) prune to reinstate the Prune state.  However, if
            we reach the end of the message without encountering such an
            (S,G,rpt) prune, then we will revert to NoInfo state in this
            state machine.

            As no time is spent in this state, no timers can expire.

      Prune-Pending-Tmp (PP')
            This state is a transient state that is identical to P'
            except that it is associated with the PP state rather than
            the P state.  For forwarding purposes, PP' behaves exactly
            like the PP state.

Top      Up      ToC       Page 55 
   In addition, there are two timers:

      Expiry Timer (ET)
            This timer is set when a valid Prune(S,G,rpt) is received.
            Expiry of the Expiry Timer causes this state machine to
            revert to NoInfo state.

      Prune-Pending Timer (PPT)
            This timer is set when a valid Prune(S,G,rpt) is received.
            Expiry of the Prune-Pending Timer causes this state machine
            to move on to Prune state.

Top      Up      ToC       Page 56 
       Figure 4: Downstream Per-Interface (S,G,rpt) State Machine

+----------++----------------------------------------------------------+
|          ||                          Event                           |
|          ++---------+----------+----------+--------+--------+--------+
|Prev      ||Receive  | Receive  | Receive  | End of | Prune- | Expiry |
|State     ||Join(*,G)| Join     | Prune    | Message| Pending| Timer  |
|          ||         | (S,G,rpt)| (S,G,rpt)|        | Timer  | Expires|
|          ||         |          |          |        | Expires|        |
+----------++---------+----------+----------+--------+--------+--------+
|          ||-        | -        | -> PP    | -      | -      | -      |
|          ||         |          | state    |        |        |        |
|          ||         |          | start    |        |        |        |
|NoInfo    ||         |          | Prune-   |        |        |        |
|(NI)      ||         |          | Pending  |        |        |        |
|          ||         |          | Timer;   |        |        |        |
|          ||         |          | start    |        |        |        |
|          ||         |          | Expiry   |        |        |        |
|          ||         |          | Timer    |        |        |        |
+----------++---------+----------+----------+--------+--------+--------+
|          ||-> P'    | -> NI    | -> P     | -      | -      | -> NI  |
|          ||state    | state    | state    |        |        | state  |
|Prune (P) ||         |          | restart  |        |        |        |
|          ||         |          | Expiry   |        |        |        |
|          ||         |          | Timer    |        |        |        |
+----------++---------+----------+----------+--------+--------+--------+
|Prune-    ||-> PP'   | -> NI    | -        | -      | -> P   | -      |
|Pending   ||state    | state    |          |        | state  |        |
|(PP)      ||         |          |          |        |        |        |
+----------++---------+----------+----------+--------+--------+--------+
|          ||-        | -        | -> P     | -> NI  | -      | -      |
|PruneTmp  ||         |          | state    | state  |        |        |
|(P')      ||         |          | restart  |        |        |        |
|          ||         |          | Expiry   |        |        |        |
|          ||         |          | Timer    |        |        |        |
+----------++---------+----------+----------+--------+--------+--------+
|          ||-        | -        | -> PP    | -> NI  | -      | -      |
|Prune-    ||         |          | state    | state  |        |        |
|Pending-  ||         |          | restart  |        |        |        |
|Tmp (PP') ||         |          | Expiry   |        |        |        |
|          ||         |          | Timer    |        |        |        |
+----------++---------+----------+----------+--------+--------+--------+

   The transition events "Receive Join(S,G,rpt)", "Receive
   Prune(S,G,rpt)", and "Receive Join(*,G)" imply receiving a Join or
   Prune targeted to this router's primary IP address on the received
   interface.  If the upstream neighbor address field is not correct,

Top      Up      ToC       Page 57 
   these state transitions in this state machine MUST NOT occur,
   although seeing such a packet may cause state transitions in other
   state machines.

   On unnumbered interfaces on point-to-point links, the router's
   address should be the same as the source address it chose for the
   Hello message it sent over that interface.  However, on point-to-
   point links it is RECOMMENDED that PIM Join/Prune messages with an
   upstream neighbor address field of all zeros also be accepted.

   Transitions from NoInfo State

   When in NoInfo (NI) state, the following event may trigger a
   transition:

      Receive Prune(S,G,rpt)
            A Prune(S,G,rpt) is received on interface I with its
            Upstream Neighbor Address set to the router's primary IP
            address on I.

            The (S,G,rpt) downstream state machine on interface I
            transitions to the Prune-Pending state.  The Expiry Timer
            (ET) is started and set to the HoldTime from the triggering
            Join/Prune message.  The Prune-Pending Timer is started.  It
            is set to the J/P_Override_Interval(I) if the router has
            more than one neighbor on that interface; otherwise, it is
            set to zero, causing it to expire immediately.

Top      Up      ToC       Page 58 
   Transitions from Prune-Pending State

   When in Prune-Pending (PP) state, the following events may trigger a
   transition:

      Receive Join(*,G)
            A Join(*,G) is received on interface I with its Upstream
            Neighbor Address set to the router's primary IP address
            on I.

            The (S,G,rpt) downstream state machine on interface I
            transitions to the Prune-Pending-Tmp state whilst the
            remainder of the compound Join/Prune message containing the
            Join(*,G) is processed.

      Receive Join(S,G,rpt)
            A Join(S,G,rpt) is received on interface I with its Upstream
            Neighbor Address set to the router's primary IP address
            on I.

            The (S,G,rpt) downstream state machine on interface I
            transitions to the NoInfo state.  The ET and PPT are
            canceled.

      Prune-Pending Timer Expires
            The Prune-Pending Timer for the (S,G,rpt) downstream state
            machine on interface I expires.

            The (S,G,rpt) downstream state machine on interface I
            transitions to the Prune state.

Top      Up      ToC       Page 59 
   Transitions from Prune State

   When in Prune (P) state, the following events may trigger a
   transition:

      Receive Join(*,G)
            A Join(*,G) is received on interface I with its Upstream
            Neighbor Address set to the router's primary IP address
            on I.

            The (S,G,rpt) downstream state machine on interface I
            transitions to the PruneTmp state whilst the remainder of
            the compound Join/Prune message containing the Join(*,G) is
            processed.

      Receive Join(S,G,rpt)
            A Join(S,G,rpt) is received on interface I with its Upstream
            Neighbor Address set to the router's primary IP address
            on I.

            The (S,G,rpt) downstream state machine on interface I
            transitions to the NoInfo state.  The ET and PPT are
            canceled.

      Receive Prune(S,G,rpt)
            A Prune(S,G,rpt) is received on interface I with its
            Upstream Neighbor Address set to the router's primary IP
            address on I.

            The (S,G,rpt) downstream state machine on interface I
            remains in Prune state.  The Expiry Timer (ET) is restarted
            and is then set to the maximum of its current value and the
            HoldTime from the triggering Join/Prune message.

      Expiry Timer Expires
            The Expiry Timer for the (S,G,rpt) downstream state machine
            on interface I expires.

            The (S,G,rpt) downstream state machine on interface I
            transitions to the NoInfo state.

Top      Up      ToC       Page 60 
   Transitions from Prune-Pending-Tmp State

   When in Prune-Pending-Tmp (PP') state and processing a compound
   Join/Prune message, the following events may trigger a transition:

      Receive Prune(S,G,rpt)
            The compound Join/Prune message contains a Prune(S,G,rpt)
            that is received on interface I with its Upstream Neighbor
            Address set to the router's primary IP address on I.

            The (S,G,rpt) downstream state machine on interface I
            transitions back to the Prune-Pending state.  The
            Expiry Timer (ET) is restarted and is then set to the
            maximum of its current value and the HoldTime from the
            triggering Join/Prune message.

      End of Message
            The end of the compound Join/Prune message is reached.

            The (S,G,rpt) downstream state machine on interface I
            transitions to the NoInfo state.  The ET and PPT are
            canceled.

   Transitions from PruneTmp State

   When in PruneTmp (P') state and processing a compound Join/Prune
   message, the following events may trigger a transition:

      Receive Prune(S,G,rpt)
            The compound Join/Prune message contains a Prune(S,G,rpt).

            The (S,G,rpt) downstream state machine on interface I
            transitions back to the Prune state.  The Expiry Timer (ET)
            is restarted and is then set to the maximum of its current
            value and the HoldTime from the triggering Join/Prune
            message.

      End of Message
            The end of the compound Join/Prune message is reached.

            The (S,G,rpt) downstream state machine on interface I
            transitions to the NoInfo state.  ET is canceled.

   Note: Receiving a Prune(*,G) does not affect the (S,G,rpt) downstream
   state machine.

Top      Up      ToC       Page 61 
4.5.4.  Sending (*,G) Join/Prune Messages

   The per-interface state machines for (*,G) hold join state from
   downstream PIM routers.  This state then determines whether a router
   needs to propagate a Join(*,G) upstream towards the RP.

   If a router wishes to propagate a Join(*,G) upstream, it must also
   watch for messages on its upstream interface from other routers on
   that subnet, and these may modify its behavior.  If it sees a
   Join(*,G) to the correct upstream neighbor, it should suppress its
   own Join(*,G).  If it sees a Prune(*,G) to the correct upstream
   neighbor, it should be prepared to override that prune by sending a
   Join(*,G) almost immediately.  Finally, if it sees the Generation ID
   (see Section 4.3) of the correct upstream neighbor change, it knows
   that the upstream neighbor has lost state, and it should be prepared
   to refresh the state by sending a Join(*,G) almost immediately.

   If a (*,G) Assert occurs on the upstream interface, and this changes
   this router's idea of the upstream neighbor, it should be prepared to
   ensure that the Assert winner is aware of downstream routers by
   sending a Join(*,G) almost immediately.

   In addition, if the MRIB changes to indicate that the next hop
   towards the RP has changed, and either the upstream interface changes
   or there is no Assert winner on the upstream interface, the router
   should prune off from the old next hop and join towards the new
   next hop.

   The upstream (*,G) state machine only contains two states:

      Not Joined
            The downstream state machines indicate that the router does
            not need to join the RP tree for this group.

      Joined
            The downstream state machines indicate that the router
            should join the RP tree for this group.

   In addition, one timer JT(*,G) is kept that is used to trigger the
   sending of a Join(*,G) to the upstream next hop towards the RP,
   RPF'(*,G).

Top      Up      ToC       Page 62 
                 Figure 5: Upstream (*,G) State Machine

+-------------------++-------------------------------------------------+
|                   ||                      Event                      |
|  Prev State       ++------------------------+------------------------+
|                   ||   JoinDesired(*,G)     |    JoinDesired(*,G)    |
|                   ||   ->True               |    ->False             |
+-------------------++------------------------+------------------------+
|                   ||   -> J state           |    -                   |
|  NotJoined (NJ)   ||   Send Join(*,G);      |                        |
|                   ||   set Join Timer to    |                        |
|                   ||   t_periodic           |                        |
+-------------------++------------------------+------------------------+
|  Joined (J)       ||   -                    |    -> NJ state         |
|                   ||                        |    Send Prune(*,G);    |
|                   ||                        |    cancel Join Timer   |
+-------------------++------------------------+------------------------+

   In addition, we have the following transitions, which occur within
   the Joined state:

+----------------------------------------------------------------------+
|                        In Joined (J) State                           |
+----------------+-----------------+-----------------+-----------------+
|Timer Expires   | See Join(*,G)   | See Prune(*,G)  | RPF'(*,G)       |
|                | to RPF'(*,G)    | to RPF'(*,G)    | changes due to  |
|                |                 |                 | an Assert       |
+----------------+-----------------+-----------------+-----------------+
|Send            | Increase Join   | Decrease Join   | Decrease Join   |
|Join(*,G); set  | Timer to        | Timer to        | Timer to        |
|Join Timer to   | t_joinsuppress  | t_override      | t_override      |
|t_periodic      |                 |                 |                 |
+----------------+-----------------+-----------------+-----------------+

+----------------------------------------------------------------------+
|                         In Joined (J) State                          |
+----------------------------------+-----------------------------------+
|    RPF'(*,G) changes not         |       RPF'(*,G) GenID changes     |
|    due to an Assert              |                                   |
+----------------------------------+-----------------------------------+
|    Send Join(*,G) to new         |       Decrease Join Timer to      |
|    next hop; send                |       t_override                  |
|    Prune(*,G) to old next        |                                   |
|    hop; set Join Timer to        |                                   |
|    t_periodic                    |                                   |
+----------------------------------+-----------------------------------+

Top      Up      ToC       Page 63 
   This state machine uses the following macro:

     bool JoinDesired(*,G) {
        if (immediate_olist(*,G) != NULL)
            return TRUE
        else
            return FALSE
     }

   JoinDesired(*,G) is true when the router has forwarding state that
   would cause it to forward traffic for G using shared tree state.
   Note that although JoinDesired is true, the router's sending of a
   Join(*,G) message may be suppressed by another router sending a
   Join(*,G) onto the upstream interface.

   Transitions from NotJoined State

   When the upstream (*,G) state machine is in NotJoined state, the
   following event may trigger a state transition:

      JoinDesired(*,G) becomes True
            The macro JoinDesired(*,G) becomes True, e.g., because the
            downstream state for (*,G) has changed so that at least one
            interface is in immediate_olist(*,G).

            The upstream (*,G) state machine transitions to the Joined
            state.  Send Join(*,G) to the appropriate upstream neighbor,
            which is RPF'(*,G).  Set the Join Timer (JT) to expire after
            t_periodic seconds.

   Transitions from Joined State

   When the upstream (*,G) state machine is in Joined state, the
   following events may trigger state transitions:

      JoinDesired(*,G) becomes False
            The macro JoinDesired(*,G) becomes False, e.g., because the
            downstream state for (*,G) has changed so no interface is in
            immediate_olist(*,G).

            The upstream (*,G) state machine transitions to the
            NotJoined state.  Send Prune(*,G) to the appropriate
            upstream neighbor, which is RPF'(*,G).  Cancel the
            Join Timer (JT).

Top      Up      ToC       Page 64 
      Join Timer Expires
            The Join Timer (JT) expires, indicating time to send a
            Join(*,G).

            Send Join(*,G) to the appropriate upstream neighbor, which
            is RPF'(*,G).  Restart the Join Timer (JT) to expire after
            t_periodic seconds.

      See Join(*,G) to RPF'(*,G)
            This event is only relevant if RPF_interface(RP(G)) is a
            shared medium.  This router sees another router on
            RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G).  This
            causes this router to suppress its own Join.

            The upstream (*,G) state machine remains in Joined state.

            Let t_joinsuppress be the minimum of t_suppressed and the
            HoldTime from the Join/Prune message triggering this event.
            If the Join Timer is set to expire in less than
            t_joinsuppress seconds, reset it so that it expires after
            t_joinsuppress seconds.  If the Join Timer is set to expire
            in more than t_joinsuppress seconds, leave it unchanged.

      See Prune(*,G) to RPF'(*,G)
            This event is only relevant if RPF_interface(RP(G)) is a
            shared medium.  This router sees another router on
            RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G).  As
            this router is in Joined state, it must override the Prune
            after a short random interval.

            The upstream (*,G) state machine remains in Joined state.
            If the Join Timer is set to expire in more than
            t_override seconds, reset it so that it expires after
            t_override seconds.  If the Join Timer is set to expire in
            less than t_override seconds, leave it unchanged.

      RPF'(*,G) changes due to an Assert
            The current next hop towards the RP changes due to an
            Assert(*,G) on the RPF_interface(RP(G)).

            The upstream (*,G) state machine remains in Joined state.
            If the Join Timer is set to expire in more than
            t_override seconds, reset it so that it expires after
            t_override seconds.  If the Join Timer is set to expire in
            less than t_override seconds, leave it unchanged.

Top      Up      ToC       Page 65 
      RPF'(*,G) changes not due to an Assert
            An event occurred that caused the next hop towards the RP
            for G to change.  This may be caused by a change in the MRIB
            routing database or the group-to-RP mapping.  Note that this
            transition does not occur if an Assert is active and the
            upstream interface does not change.

            The upstream (*,G) state machine remains in Joined state.
            Send Join(*,G) to the new upstream neighbor, which is the
            new value of RPF'(*,G).  Send Prune(*,G) to the old upstream
            neighbor, which is the old value of RPF'(*,G).  Use the new
            value of RP(G) in the Prune(*,G) message or all zeros if
            RP(G) becomes unknown (old value of RP(G) may be used
            instead to improve behavior in routers implementing older
            versions of this specification).  Set the Join Timer (JT) to
            expire after t_periodic seconds.

      RPF'(*,G) GenID changes
            The Generation ID of the router that is RPF'(*,G) changes.
            This normally means that this neighbor has lost state, and
            so the state must be refreshed.

            The upstream (*,G) state machine remains in Joined state.
            If the Join Timer is set to expire in more than
            t_override seconds, reset it so that it expires after
            t_override seconds.

4.5.5.  Sending (S,G) Join/Prune Messages

   The per-interface state machines for (S,G) hold join state from
   downstream PIM routers.  This state then determines whether a router
   needs to propagate a Join(S,G) upstream towards the source.

   If a router wishes to propagate a Join(S,G) upstream, it must also
   watch for messages on its upstream interface from other routers on
   that subnet, and these may modify its behavior.  If it sees a
   Join(S,G) to the correct upstream neighbor, it should suppress its
   own Join(S,G).  If it sees a Prune(S,G), Prune(S,G,rpt), or
   Prune(*,G) to the correct upstream neighbor towards S, it should be
   prepared to override that prune by scheduling a Join(S,G) to be sent
   almost immediately.  Finally, if it sees the Generation ID of its
   upstream neighbor change, it knows that the upstream neighbor has
   lost state, and it should refresh the state by scheduling a Join(S,G)
   to be sent almost immediately.

Top      Up      ToC       Page 66 
   If an (S,G) Assert occurs on the upstream interface, and this changes
   this router's idea of the upstream neighbor, it should be prepared to
   ensure that the Assert winner is aware of downstream routers by
   scheduling a Join(S,G) to be sent almost immediately.

   In addition, if MRIB changes cause the next hop towards the source to
   change, and either the upstream interface changes or there is no
   Assert winner on the upstream interface, the router should send a
   prune to the old next hop and a join to the new next hop.

   The upstream (S,G) state machine only contains two states:

      Not Joined
            The downstream state machines and local membership
            information do not indicate that the router needs to join
            the shortest-path tree for this (S,G).

      Joined
            The downstream state machines and local membership
            information indicate that the router should join the
            shortest-path tree for this (S,G).

   In addition, one timer JT(S,G) is kept that is used to trigger the
   sending of a Join(S,G) to the upstream next hop towards S, RPF'(S,G).

                 Figure 6: Upstream (S,G) State Machine

+-------------------+--------------------------------------------------+
|                   |                      Event                       |
|  Prev State       +-------------------------+------------------------+
|                   |   JoinDesired(S,G)      |   JoinDesired(S,G)     |
|                   |   ->True                |   ->False              |
+-------------------+-------------------------+------------------------+
|  NotJoined (NJ)   |   -> J state            |   -                    |
|                   |   Send Join(S,G);       |                        |
|                   |   set Join Timer to     |                        |
|                   |   t_periodic            |                        |
+-------------------+-------------------------+------------------------+
|  Joined (J)       |   -                     |   -> NJ state          |
|                   |                         |   Send Prune(S,G);     |
|                   |                         |   set SPTbit(S,G) to   |
|                   |                         |   FALSE; cancel Join   |
|                   |                         |   Timer                |
+-------------------+-------------------------+------------------------+

Top      Up      ToC       Page 67 
   In addition, we have the following transitions, which occur within
   the Joined state:

+----------------------------------------------------------------------+
|                         In Joined (J) State                          |
+-----------------+-----------------+-----------------+----------------+
| Timer Expires   | See Join(S,G)   | See Prune(S,G)  | See Prune      |
|                 | to RPF'(S,G)    | to RPF'(S,G)    | (S,G,rpt) to   |
|                 |                 |                 | RPF'(S,G)      |
+-----------------+-----------------+-----------------+----------------+
| Send            | Increase Join   | Decrease Join   | Decrease Join  |
| Join(S,G); set  | Timer to        | Timer to        | Timer to       |
| Join Timer to   | t_joinsuppress  | t_override      | t_override     |
| t_periodic      |                 |                 |                |
+-----------------+-----------------+-----------------+----------------+

+----------------------------------------------------------------------+
|                        In Joined (J) State                           |
+-----------------+-----------------+----------------+-----------------+
| See Prune(*,G)  | RPF'(S,G)       | RPF'(S,G)      | RPF'(S,G)       |
| to RPF'(S,G)    | changes not     | GenID changes  | changes due to  |
|                 | due to an       |                | an Assert       |
|                 | Assert          |                |                 |
+-----------------+-----------------+----------------+-----------------+
| Decrease Join   | Send Join(S,G)  | Decrease Join  | Decrease Join   |
| Timer to        | to new next     | Timer to       | Timer to        |
| t_override      | hop; send       | t_override     | t_override      |
|                 | Prune(S,G) to   |                |                 |
|                 | old next hop;   |                |                 |
|                 | set Join Timer  |                |                 |
|                 | to t_periodic   |                |                 |
+-----------------+-----------------+----------------+-----------------+

   This state machine uses the following macro:

     bool JoinDesired(S,G) {
         return( immediate_olist(S,G) != NULL
                 OR ( KeepaliveTimer(S,G) is running
                      AND inherited_olist(S,G) != NULL ) )
     }

   JoinDesired(S,G) is true when the router has forwarding state that
   would cause it to forward traffic for G using source tree state.  The
   source tree state can be as a result of either active source-specific
   join state, or the (S,G) Keepalive Timer and active non-source-
   specific state.  Note that although JoinDesired is true, the router's
   sending of a Join(S,G) message may be suppressed by another router
   sending a Join(S,G) onto the upstream interface.

Top      Up      ToC       Page 68 
   Transitions from NotJoined State

   When the upstream (S,G) state machine is in NotJoined state, the
   following event may trigger a state transition:

      JoinDesired(S,G) becomes True
            The macro JoinDesired(S,G) becomes True, e.g., because the
            downstream state for (S,G) has changed so that at least one
            interface is in inherited_olist(S,G).

            The upstream (S,G) state machine transitions to the Joined
            state.  Send Join(S,G) to the appropriate upstream neighbor,
            which is RPF'(S,G).  Set the Join Timer (JT) to expire after
            t_periodic seconds.

   Transitions from Joined State

   When the upstream (S,G) state machine is in Joined state, the
   following events may trigger state transitions:

      JoinDesired(S,G) becomes False
            The macro JoinDesired(S,G) becomes False, e.g., because the
            downstream state for (S,G) has changed so no interface is in
            inherited_olist(S,G).

            The upstream (S,G) state machine transitions to the
            NotJoined state.  Send Prune(S,G) to the appropriate
            upstream neighbor, which is RPF'(S,G).  Cancel the
            Join Timer (JT), and set SPTbit(S,G) to FALSE.

      Join Timer Expires
            The Join Timer (JT) expires, indicating time to send a
            Join(S,G).

            Send Join(S,G) to the appropriate upstream neighbor, which
            is RPF'(S,G).  Restart the Join Timer (JT) to expire after
            t_periodic seconds.

Top      Up      ToC       Page 69 
      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).  This causes this router to
            suppress its own Join.

            The upstream (S,G) state machine remains in Joined state.

            Let t_joinsuppress be the minimum of t_suppressed and the
            HoldTime from the Join/Prune message triggering this event.

            If the Join Timer is set to expire in less than
            t_joinsuppress seconds, reset it so that it expires after
            t_joinsuppress seconds.  If the Join Timer is set to expire
            in more than t_joinsuppress seconds, leave it unchanged.

      See Prune(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 Prune(S,G) to RPF'(S,G).  As this router is in Joined
            state, it must override the Prune after a short random
            interval.

            The upstream (S,G) state machine remains in Joined state.
            If the Join Timer is set to expire in more than
            t_override seconds, reset it so that it expires after
            t_override seconds.

      See Prune(S,G,rpt) 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 Prune(S,G,rpt) to RPF'(S,G).  If the upstream router
            is an RFC-2362-compliant PIM router, then the Prune(S,G,rpt)
            will cause it to stop forwarding.  For backwards
            compatibility, this router should override the prune so that
            forwarding continues.

            The upstream (S,G) state machine remains in Joined state.
            If the Join Timer is set to expire in more than
            t_override seconds, reset it so that it expires after
            t_override seconds.

Top      Up      ToC       Page 70 
      See Prune(*,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 Prune(*,G) to RPF'(S,G).  If the upstream router is
            an RFC-2362-compliant PIM router, then the Prune(*,G) will
            cause it to stop forwarding.  For backwards compatibility,
            this router should override the prune so that forwarding
            continues.

            The upstream (S,G) state machine remains in Joined state.
            If the Join Timer is set to expire in more than
            t_override seconds, reset it so that it expires after
            t_override seconds.

      RPF'(S,G) changes due to an Assert
            The current next hop towards S changes due to an Assert(S,G)
            on the RPF_interface(S).

            The upstream (S,G) state machine remains in Joined state.
            If the Join Timer is set to expire in more than
            t_override seconds, reset it so that it expires after
            t_override seconds.  If the Join Timer is set to expire in
            less than t_override seconds, leave it unchanged.

      RPF'(S,G) changes not due to an Assert
            An event occurred that caused the next hop towards S to
            change.  Note that this transition does not occur if an
            Assert is active and the upstream interface does not change.

            The upstream (S,G) state machine remains in Joined state.
            Send Join(S,G) to the new upstream neighbor, which is the
            new value of RPF'(S,G).  Send Prune(S,G) to the old upstream
            neighbor, which is the old value of RPF'(S,G).  Set the
            Join Timer (JT) to expire after t_periodic seconds.

      RPF'(S,G) GenID changes
            The Generation ID of the router that is RPF'(S,G) changes.
            This normally means that this neighbor has lost state, and
            so the state must be refreshed.

            The upstream (S,G) state machine remains in Joined state.
            If the Join Timer is set to expire in more than
            t_override seconds, reset it so that it expires after
            t_override seconds.

Top      Up      ToC       Page 71 
4.5.6.  (S,G,rpt) Periodic Messages

   (S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP
   tree with the RPT bit set, either to modify the results of (*,G)
   Joins, or to override the behavior of other upstream LAN peers.  The
   next section describes the rules for sending triggered messages.
   This section describes the rules for including a Prune(S,G,rpt)
   message with a Join(*,G).

   When a router is going to send a Join(*,G), it should use the
   following pseudocode, for each (S,G) for which it has state, to
   decide whether to include a Prune(S,G,rpt) in the compound Join/Prune
   message:

     if( SPTbit(S,G) == TRUE ) {
         # Note: If receiving (S,G) on the SPT, we only prune off the
         # shared tree if the RPF neighbors differ.
          if( RPF'(*,G) != RPF'(S,G) ) {
              add Prune(S,G,rpt) to compound message
          }
     } else if ( inherited_olist(S,G,rpt) == NULL ) {
       # Note: All (*,G) olist interfaces received RPT prunes for (S,G).
       add Prune(S,G,rpt) to compound message
     } else if ( RPF'(*,G) != RPF'(S,G,rpt) {
       # Note: We joined the shared tree, but there was an (S,G) assert
       # and the source tree RPF neighbor is different.
       add Prune(S,G,rpt) to compound message
     }

   Note that Join(S,G,rpt) is normally sent not as a periodic message,
   but only as a triggered message.

Top      Up      ToC       Page 72 
4.5.7.  State Machine for (S,G,rpt) Triggered Messages

   The state machine for (S,G,rpt) triggered messages is required
   per-(S,G) when there is (*,G) join state at a router, and the router
   or any of its upstream LAN peers wishes to prune S off the RP tree.

   There are three states in the state machine.  One of the states is
   when there is no (*,G) join state at this router.  If there is (*,G)
   join state at the router, then the state machine must be at one of
   the other two states.  The three states are:

      Pruned(S,G,rpt)
         (*,G) Joined, but (S,G,rpt) pruned.

      NotPruned(S,G,rpt)
         (*,G) Joined, and (S,G,rpt) not pruned.

      RPTNotJoined(G)
         (*,G) has not been joined.

   In addition, there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which
   is used to delay triggered Join(S,G,rpt) messages to prevent
   implosions of triggered messages.

   Figure 7: Upstream (S,G,rpt) State Machine for Triggered Messages

+------------++--------------------------------------------------------+
|            ||                           Event                        |
|            ++--------------+--------------+-------------+------------+
|Prev State  || PruneDesired | PruneDesired | RPTJoin     | inherited_ |
|            || (S,G,rpt)    | (S,G,rpt)    | Desired(G)  | olist      |
|            || ->True       | ->False      | ->False     | (S,G,rpt)  |
|            ||              |              |             | ->non-NULL |
+------------++--------------+--------------+-------------+------------+
|RPTNotJoined|| -> P state   | -            | -           | -> NP state|
|(G) (NJ)    ||              |              |             |            |
+------------++--------------+--------------+-------------+------------+
|Pruned      || -            | -> NP state  | -> NJ state | -          |
|(S,G,rpt)   ||              | Send Join    |             |            |
|(P)         ||              | (S,G,rpt)    |             |            |
+------------++--------------+--------------+-------------+------------+
|NotPruned   || -> P state   | -            | -> NJ state | -          |
|(S,G,rpt)   || Send Prune   |              | Cancel OT   |            |
|(NP)        || (S,G,rpt);   |              |             |            |
|            || cancel OT    |              |             |            |
+------------++--------------+--------------+-------------+------------+

Top      Up      ToC       Page 73 
   Additionally, we have the following transitions within the
   NotPruned(S,G,rpt) state, which are all used for prune override
   behavior.

+----------------------------------------------------------------------+
|                    In NotPruned(S,G,rpt) State                       |
+----------+--------------+--------------+--------------+--------------+
|Override  | See Prune    | See Join     | See Prune    | RPF'         |
|Timer     | (S,G,rpt) to | (S,G,rpt) to | (S,G) to     | (S,G,rpt) -> |
|expires   | RPF'         | RPF'         | RPF'         | RPF' (*,G)   |
|          | (S,G,rpt)    | (S,G,rpt)    | (S,G,rpt)    |              |
+----------+--------------+--------------+--------------+--------------+
|Send Join | OT = min(OT, | Cancel OT    | OT = min(OT, | OT = min(OT, |
|(S,G,rpt);| t_override)  |              | t_override)  | t_override)  |
|leave OT  |              |              |              |              |
|unset     |              |              |              |              |
+----------+--------------+--------------+--------------+--------------+

   Note that the min function in the above state machine considers a
   non-running timer to have an infinite value (e.g., min(not-running,
   t_override) = t_override).

   This state machine uses the following macros:

     bool RPTJoinDesired(G) {
       return (JoinDesired(*,G))
     }

   RPTJoinDesired(G) is true when the router has forwarding state that
   would cause it to forward traffic for G using (*,G) shared tree
   state.

     bool PruneDesired(S,G,rpt) {
          return ( RPTJoinDesired(G) AND
                   ( inherited_olist(S,G,rpt) == NULL
                     OR (SPTbit(S,G)==TRUE
                         AND (RPF'(*,G) != RPF'(S,G)) )))
     }

   PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true.
   If RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true
   either if there are no outgoing interfaces that S would be forwarded
   on, or if the router has active (S,G) forwarding state but RPF'(*,G)
   != RPF'(S,G).

Top      Up      ToC       Page 74 
   The state machine contains the following transition events:

      See Join(S,G,rpt) to RPF'(S,G,rpt)
            This event is only relevant in the "Not Pruned" state.

            The router sees a Join(S,G,rpt) from someone else to
            RPF'(S,G,rpt), which is the correct upstream neighbor.  If
            we're in "NotPruned" state and the (S,G,rpt) Override Timer
            is running, then this is because we have been triggered to
            send our own Join(S,G,rpt) to RPF'(S,G,rpt).  Someone else
            beat us to it, so there's no need to send our own Join.

            The action is to cancel the Override Timer.

      See Prune(S,G,rpt) to RPF'(S,G,rpt)
            This event is only relevant in the "NotPruned" state.

            The router sees a Prune(S,G,rpt) from someone else to
            RPF'(S,G,rpt), which is the correct upstream neighbor.  If
            we're in the "NotPruned" state, then we want to continue to
            receive traffic from S destined for G, and that traffic is
            being supplied by RPF'(S,G,rpt).  Thus, we need to override
            the Prune.

            The action is to set the (S,G,rpt) Override Timer to the
            randomized prune-override interval, t_override.  However, if
            the Override Timer is already running, we only set the timer
            if doing so would set it to a lower value.  At the end of
            this interval, if no one else has sent a Join, then we will
            do so.

      See Prune(S,G) to RPF'(S,G,rpt)
            This event is only relevant in the "NotPruned" state.

            This transition and action are the same as the above
            transition and action, except that the Prune does not have
            the RPT bit set.  This transition is necessary to be
            compatible with routers implemented from RFC 2362 that don't
            maintain separate (S,G) and (S,G,rpt) state.

Top      Up      ToC       Page 75 
      The (S,G,rpt) prune Override Timer expires
            This event is only relevant in the "NotPruned" state.

            When the Override Timer expires, we must send a
            Join(S,G,rpt) to RPF'(S,G,rpt) to override the Prune message
            that caused the timer to be running.  We only send this if
            RPF'(S,G,rpt) equals RPF'(*,G); if this were not the case,
            then the Join might be sent to a router that does not have
            (*,G) Join state, and so the behavior would not be well
            defined.  If RPF'(S,G,rpt) is not the same as RPF'(*,G),
            then it may stop forwarding S.  However, if this happens,
            then the router will send an AssertCancel(S,G), which would
            then cause RPF'(S,G,rpt) to become equal to RPF'(*,G) (see
            below).

      RPF'(S,G,rpt) changes to become equal to RPF'(*,G)
            This event is only relevant in the "NotPruned" state.

            RPF'(S,G,rpt) can only be different from RPF'(*,G) if an
            (S,G) Assert has happened, which means that traffic from S
            is arriving on the SPT, and so Prune(S,G,rpt) will have been
            sent to RPF'(*,G).  When RPF'(S,G,rpt) changes to become
            equal to RPF'(*,G), we need to trigger a Join(S,G,rpt) to
            RPF'(*,G) to cause that router to start forwarding S again.

            The action is to set the (S,G,rpt) Override Timer to the
            randomized prune-override interval t_override.  However, if
            the timer is already running, we only set the timer if doing
            so would set it to a lower value.  At the end of this
            interval, if no one else has sent a Join, then we will
            do so.

      PruneDesired(S,G,rpt)->TRUE
            See macro above.  This event is relevant in the "NotPruned"
            and "RPTNotJoined(G)" states.

            The router wishes to receive traffic for G but does not wish
            to receive traffic from S destined for G.  This causes the
            router to transition into the Pruned state.

            If the router was previously in NotPruned state, then the
            action is to send a Prune(S,G,rpt) to RPF'(S,G,rpt), and to
            cancel the Override Timer.  If the router was previously in
            RPTNotJoined(G) state, then there is no need to trigger an
            action in this state machine because sending a
            Prune(S,G,rpt) is handled by the rules for sending the
            Join(*,G).

Top      Up      ToC       Page 76 
      PruneDesired(S,G,rpt)->FALSE
            See macro above.  This transition is only relevant in the
            "Pruned" state.

            If the router is in the Pruned(S,G,rpt) state, and
            PruneDesired(S,G,rpt) changes to FALSE, this could be
            because the router no longer has RPTJoinDesired(G) true, or
            it now wishes to receive traffic from S again.  If it is the
            former, then this transition should not happen, but instead
            the "RPTJoinDesired(G)->FALSE" transition should happen.
            Thus, this transition should be interpreted as
            "PruneDesired(S,G,rpt)->FALSE AND RPTJoinDesired(G)==TRUE".

            The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt).

      RPTJoinDesired(G)->FALSE
            This event is relevant in the "Pruned" and "NotPruned"
            states.

            The router no longer wishes to receive any traffic destined
            for G on the RP Tree.  This causes a transition to the
            RPTNotJoined(G) state, and the Override Timer is canceled if
            it was running.  Any further actions are handled by the
            appropriate upstream state machine for (*,G).

      inherited_olist(S,G,rpt) becomes non-NULL
            This transition is only relevant in the RPTNotJoined(G)
            state.

            The router has joined the RP tree (handled by the (*,G)
            upstream state machine as appropriate) and wants to receive
            traffic from S.  This does not trigger any events in this
            state machine, but causes a transition to the
            NotPruned(S,G,rpt) state.



(page 76 continued on part 5)

Next RFC Part