draft-ietf-pim-dm-new-v2-01.txt

BCAST Implementation for NS2

    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 6.8.1).

  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 6.8.1).

Adams, Nicholas, Siadak                                        [Page 11]

  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 6.8.1) 


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

Adams, Nicholas, Siadak                                        [Page 12]

+-------------------------------+--------------------------------------+
|                               |            Previous State            |
|                               +------------+------------+------------+
|            Event              | Forwarding |   Pruned   | AckPending |
+-------------------------------+------------+------------+------------+
| 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.

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.





Adams, Nicholas, Siadak                                        [Page 13]

  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 and so the
    local router SHOULD cancel its OT(S,G), if it is running.  The 
    Upstream(S,G) state machine remains in the Forwarding (F) state.

  See Prune(S,G) AND S NOT directly connected
    This event is only relevant if RPF_interface(S) is a shared medium.
    This router sees another router on RPF_interface(S) send a
    Prune(S,G).  As this router is in Forwarding state, it must
    override the Prune after a short random interval.  If OT(S,G) is not
    running, the router MUST set OT(S,G) to t_override seconds.  The
    Upstream(S,G) state machine remains in Forwarding (F) state.

  OT(S,G) Expires AND S NOT directly connected
    The OverrideTimer (OT(S,G)) expires.  The router MUST send a
    Join(S,G) to RPF'(S) to override a previously detected prune.  The
    Upstream(S,G) state machine remains in the Forwarding (F) state.

  olist(S,G) -> NULL AND S NOT directly connected
    The Upstream(S,G) state machine MUST transition to the Pruned (P) 
    state, send a Prune(S,G) to RPF'(S) and set PLT(S,G) to t_limit
    seconds.

  RPF'(S) Changes AND olist(S,G) is non-NULL AND S NOT directly 
  connected
    Unicast routing or Assert state causes RPF'(S) to change, including
    changes to RPF_Interface(S).  The Upstream(S,G) state machine MUST
    transition to the AckPending (AP) state, unicast a Graft to the new
    RPF'(S) and set the GraftRetry Timer (GRT(S,G)) to
    Graft_Retry_Period.

  RPF'(S) Changes AND olist(S,G) is NULL
    Unicast routing or Assert state causes RPF'(S) to change, including
    changes to RPF_Interface(S).  The Upstream(S,G) state machine MUST
    transition to the Pruned (P) state.









Adams, Nicholas, Siadak                                        [Page 14]

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.  In order 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 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 traffic from S addressed to group G must be
    forwarded.  The Upstream(S,G) state machine MUST cancel PLT(S,G),
    transition to the AckPending (AP) state and unicast a Graft message
    to RPF'(S).  The Graft Retry Timer (GRT(S,G)) MUST be set to
    Graft_Retry_Period.

  RPF'(S) Changes AND olist(S,G) == non-NULL AND S NOT directly 
  connected
    Unicast routing or Assert state causes RPF'(S) to change, including
    changes to RPF_Interface(S).  The Upstream(S,G) state machine MUST
    cancel PLT(S,G), transition to the AckPending (AP) state, send a
    Graft unicast to the new RPF'(S) and set the GraftRetry Timer
    (GRT(S,G)) to Graft_Retry_Period.

  RPF'(S) Changes AND olist(S,G) == NULL AND S NOT directly connected
    Unicast routing or Assert state causes RPF'(S) to change, including
    changes to RPF_Interface(S).  The Upstream(S,G) state machine stays
    in the Pruned (P) state and MUST cancel the PLT(S,G) timer.

  S becomes directly connected
    Unicast routing changed so that S is directly connected.  The
    Upstream(S,G) state machine remains in the Pruned (P) state.



Adams, Nicholas, Siadak                                        [Page 15]

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 and so the
    local router SHOULD cancel its OT(S,G), if it is running.  The
    Upstream(S,G) state machine remains in the AckPending (AP) state.

  See Prune(S,G)
    This event is only relevant if RPF_interface(S) is a shared medium.
    This router sees another router on RPF_interface(S) send a
    Prune(S,G).  As this router is in AckPending (AP) state, it must
    override the Prune after a short random interval. If OT(S,G) is not
    running, the router MUST set OT(S,G) to t_override seconds.  The
    Upstream(S,G) state machine remains in AckPending (AP) state.

  OT(S,G) Expires
    The OverrideTimer (OT(S,G)) expires. The router MUST send a
    Join(S,G) to RPF'(S).  The Upstream(S,G) state machine remains in
    the AckPending (AP) state.

  olist(S,G) -> NULL
    The set of interfaces defined by the olist(S,G) macro becomes null
    indicating 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.



Adams, Nicholas, Siadak                                        [Page 16]