+-------------+                        +-------------+
          |             |     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









            +-------------+                        +-------------+
            |             |      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









Downstream Interface State Machine



In tabular form, the state machine is as follows:

+-------------------------------+--------------------------------------+
|                               |            Previous State            |
+                               +------------+------------+------------+
|            Event              |  No Info   | PrunePend  |   Pruned   |
+-------------------------------+------------+------------+------------+
| Receive Prune(S,G)            |->PP  Set   |->PP        |->P Reset   |
|                               | PPT(S,G,I) |            |  PT(S,G,I) |
+-------------------------------+------------+------------+------------+
| Receive Join(S,G)             |->NI        |->NI Cancel |->NI Cancel |
|                               |            | PPT(S,G,I) |  PT(S,G,I) |
+-------------------------------+------------+------------+------------+
| Receive Graft(S,G)            |->NI Send   |->NI Send   |->NI Send   |
|                               |  GraftAck  |  GraftAck  |  GraftAck  |
|                               |            |  Cancel    |  Cancel    |
|                               |            | PPT(S,G,I) |  PT(S,G,I) |
+-------------------------------+------------+------------+------------+


4.4.2.  Downstream Prune, Join, and Graft Messages

   The Prune(S,G) Downstream state machine for receiving Prune, Join and
   Graft messages on interface I is given below.  This state machine
   MUST always be in the NoInfo state on the upstream interface.  It
   contains three states.

     NoInfo(NI)
       The interface has no (S,G) Prune state, and neither the Prune
       timer (PT(S,G,I)) nor the PrunePending timer ((PPT(S,G,I)) is
       running.

     PrunePending(PP)
       The router has received a Prune(S,G) on this interface from a
       downstream neighbor and is waiting to see whether the prune will
       be overridden by another downstream router.  For forwarding
       purposes, the PrunePending state functions exactly like the
       NoInfo state.

     Pruned(P)
       The router has received a Prune(S,G) on this interface from a
       downstream neighbor, and the Prune was not overridden.  Data from
       S addressed to group G is no longer being forwarded on this
       interface.

   In addition, there are two timers:

     PrunePending Timer (PPT(S,G,I))
       This timer is set when a valid Prune(S,G) is received.  Expiry of
       the PrunePending Timer (PPT(S,G,I)) causes the interface to
       transition to the Pruned state.



     Prune Timer (PT(S,G,I))
       This timer is set when the PrunePending Timer (PT(S,G,I))
       expires.  Expiry of the Prune Timer (PT(S,G,I)) causes the
       interface to transition to the NoInfo (NI) state, thereby
       allowing data from S addressed to group G to be forwarded on the






 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.
       interface.