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

BCAST Implementation for NS2

  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.

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

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




Adams, Nicholas, Siadak                                        [Page 17]

  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: Prune(S,G) Downstream State Machine

In tabular form, the state machine is:

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




Adams, Nicholas, Siadak                                        [Page 18]

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.

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 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 unicasted to the originator of the
    Graft(S,G) message.

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.










Adams, Nicholas, Siadak                                        [Page 19]

  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, then 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.

  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.

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.

Adams, Nicholas, Siadak                                        [Page 20]

  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.

6.5 State Refresh

This section describes the major portions of the state refresh 
mechanism.

6.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;

  } 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;





Adams, Nicholas, Siadak                                        [Page 21]

  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) evaluates to TRUE if an administratively scoped boundary 
for group G is configured on interface I.

StateRefreshCapable(I) evaluates to TRUE if all neighbors on an 
interface use the State Refresh option.

StateRefreshRateLimit(S,G) evaluates to TRUE if the time elapsed since