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

BCAST Implementation for NS2

the last received StateRefresh(S,G) is less than the configured 
RefreshLimitInterval.

TTL(SRM) returns the TTL contained in the State Refresh Message, SRM.  
This is different from the TTL contained in the IP header.

Threshold(I) returns the minimum TTL that a packet must have before it 
can be transmitted on interface I.

srcaddr(SRM) returns the source address contained in the network 
protocol (e.g. IPv4) header of the State Refresh Message, SRM.

my_addr(I) returns this node's network (e.g. IPv4) address on interface 
I.

6.5.2 State Refresh Message Origination

This section describes the origination of State Refresh messages.  These
messages are generated periodically by the PIM-DM router that is 
directly connected to a source.  One Origination(S,G) state machine 
exists per (S,G) entry in a PIM-DM router.

The Origination(S,G) state machine has the following states:

  NotOriginator(NO)
    This is the starting state of the Origination(S,G) state machine.  
    While in this state a router will not originate State Refresh 
    messages for the (S,G) pair.

  Originator(O)
    When in this state the router will periodically originate State 
    Refresh messages.  Only routers which are directly connected to S 
    may transition to this state.





Adams, Nicholas, Siadak                                        [Page 22]

In addition there are two state-machine-specific timers:

  StateRefresh Timer (SRT(S,G))
    This timer is controls when State Refresh messages are generated.
    The timer is initially set when that Origination(S,G) state machine
    transitions to the O state.  It is cancelled when the
    Origination(S,G) state machine transitions to the NO state.  This
    timer is normally set to StateRefreshInterval (see 6.8.1).

  SourceActive Timer (SAT(S,G))
    This timer is first set when the Origination(S,G) state machine
    transitions to the O state and is reset on the receipt of every
    data packet from S addressed to group G.  When it expires, the
    Origination(S,G) state machine transitions to the NO state. This
    timer is normally set to SourceLifetime (see 6.8.1).



         +-------------+  Rcv Directly From S   +-------------+
         |             |----------------------->|             |
         |NotOriginator|                        | Originator  |
         |             |<-----------------------|             |
         +-------------+     SAT Expires OR     +-------------+
                          S NOT Direct Connect


Figure 3: Per-interface State Refresh State Diagram

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

+----------------------------------------------------------------------+
|                                  |           Previous State          |
|                                  +---------------+-------------------+
|            Event                 | NotOriginator |    Originator     |
+----------------------------------+---------------+-------------------+
| Receive Data from S AND          | ->O           | ->O Reset         |
| S directly connected             | Set SRT(S,G)  |     SAT(S,G)      |
|                                  | Set SAT(S,G)  |                   |
+----------------------------------+---------------+-------------------+
| SRT(S,G) Expires                 | N/A           | ->O    Send       |
|                                  |               | StateRefresh(S,G) |
|                                  |               |  Reset SRT(S,G)   |
+----------------------------------+---------------+-------------------+
| SAT(S,G) Expires                 | N/A           | ->NO  Cancel      |
|                                  |               |       SRT(S,G)    |
+----------------------------------+---------------+-------------------+
| S no longer directly connected   | ->NO          | ->NO              |
|                                  |               |   Cancel SRT(S,G) |
|                                  |               |   Cancel SAT(S,G) |
+----------------------------------+---------------+-------------------+






Adams, Nicholas, Siadak                                        [Page 23]

Transitions from the NotOriginator (NO) State

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

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

Transitions from the Originator (O) State

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

  Receive Data Packet from S addressed to G
    The router remains in the Originator (O) state and MUST reset
    SAT(S,G) to SourceLifetime.  The router SHOULD increase its recorded
    TTL to match the TTL of the packet, if the packet's TTL is larger
    than the previously recorded TTL.

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

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

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












Adams, Nicholas, Siadak                                        [Page 24]

6.6 PIM Assert Messages

6.6.1 Assert Metrics

Assert metrics are defined as:

struct assert_metric {
  metric_preference;
  route_metric;
  ip_address;
};

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

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

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

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

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

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

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

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






Adams, Nicholas, Siadak                                        [Page 25]

6.6.2 AssertCancel Messages

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

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

6.6.3 Assert State Macros

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

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

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

6.6.4 (S,G) Assert Message State Machine

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

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

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

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

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





Adams, Nicholas, Siadak                                        [Page 26]


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


           Figure 4: Per-interface (S,G) Assert state machine

In tabular form the state machine is defined as follows:

+-------------------------------+--------------------------------------+
|                               |            Previous State            |
|                               +------------+------------+------------+
|            Event              |  No Info   |   Winner   |    Loser   |
+-------------------------------+------------+------------+------------+
| An (S,G) Data packet received | ->W Send   | ->W Send   | ->L        |
| on downstream interface       | Assert(S,G)| Assert(S,G)|            |
|