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

BCAST Implementation for NS2

6.1.2 (S,G) State

For every source/group pair (S,G), a router stores the following state:

(S,G) state:
  For each interface:
    Local Membership:
      State: One of {"NoInfo", "Include"}

    PIM (S,G) Prune State:
      State: One of {"NoInfo" (NI), "Pruned" (P), "PrunePending" (PP)}
      Prune Pending Timer (PPT)
      Prune Timer (PT)

    (S,G) Assert Winner State:
      State: One of {"NoInfo" (NI), "I lost Assert" (L), 
                     "I won Assert" (W)}
      Assert Timer (AT)
      Assert winner's IP Address
      Assert winner's Assert Metric

  Upstream interface-specific:
    Graft/Prune State:
      State: One of {"NoInfo" (NI), "Pruned" (P), "Forwarding" (F), 
                     "AckPending" (AP) } 
      GraftRetry Timer (GRT)
      Override Timer (OT)
      Prune Limit Timer (PLT) 

    Originator State:
      Source Active Timer (SAT)
      State Refresh Timer (SRT)




Adams, Nicholas, Siadak                                         [Page 6]

6.1.3 State Summarization Macros

Using the state defined above, the following "macros" are defined and 
will be used in the descriptions of the state machines and pseudocode in
the following sections.

The most important macros are those defining the outgoing interface list
(or "olist") for the relevant state.

immediate_olist(S,G) = pim_nbrs (-) prunes(S,G) (+) 
                       ( pim_include(*,G) (-) pim_exclude(S,G) ) (+) 
                       pim_include(S,G) (-) lost_assert(S,G) (-) 
                       boundary(G)

olist(S,G) = immediate_olist(S,G) (-) RPF_interface(S)

The macros pim_include(*,G) and pim_include(S,G) indicate the interfaces
to which traffic might be forwarded or not forwarded because of hosts 
that are local members on those interfaces.  

pim_include(*,G) = {all interfaces I such that:
                    local_receiver_include(*,G,I)}
pim_include(S,G) = {all interfaces I such that:
                    local_receiver_include(S,G,I)}
pim_exclude(S,G) = {all interfaces I such that:
                    local_receiver_exclude(S,G,I)}

The macro RPF_interface(S) returns the RPF interface for source S.  That
is to say, it returns the interface used to reach S as indicated by the 
MRIB.

The macro local_receiver_include(S,G,I) is true if the IGMP module or 
other local membership mechanism has determined that there are local 
members on interface I that desire to receive traffic sent specifically 
by S to G.  

The macro local_receiver_include(*,G,I) is true if the IGMP module or 
other local membership mechanism has determined that there are local 
members on interface I that desire to receive all traffic sent to G.  
Note that this determination is expected to account for membership joins
initiated on or by the router. 

The macro local_receiver_exclude(S,G,I) is true if 
local_receiver_include(*,G,I) is true but none of the local members 
desire to receive traffic from S.

The set pim_nbrs is the set of all interfaces on which the router has at
least one active PIM neighbor.

The set prunes(S,G) is the set of all interfaces on which the router has
received Prune(S,G) messages:

prunes(S,G) = {all interfaces I such that 
               DownstreamPState(S,G,I) is in Pruned state}


Adams, Nicholas, Siadak                                         [Page 7]

The set lost_assert(S,G) is the set of all interfaces on which the 
router has lost an (S,G) Assert.

lost_assert(S,G) = {all interfaces I such that 
                    lost_assert(S,G,I) == TRUE}

boundary(G) = {all interfaces I with an administratively scoped 
               boundary for group G}

The following pseudocode macro definitions are also used in many places 
in the specification.  Basically RPF' is the RPF neighbor towards a 
source unless a PIM-DM Assert has overridden the normal choice of 
neighbor.

neighbor RPF'(S,G) {
  if ( I_Am_Assert_loser(S, G, RPF_interface(S) )) {
    return AssertWinner(S, G, RPF_interface(S) )
  } else {
    return MRIB.next_hop( S )
  }
}

The macro I_Am_Assert_loser(S, G, I) is true if the Assert state machine
(in section 6.6) for (S,G) on interface I is in the "I am Assert Loser"
state.

6.2 Data Packet Forwarding Rules

The PIM-DM packet forwarding rules are defined below in pseudocode.

iif is the incoming interface of the packet.
S is the source address of the packet.
G is the destination address of the packet (group address).
RPF_interface(S) is the interface the MRIB indicates would be used to 
route packets to S.

First, an RPF check MUST be performed to determine whether the packet 
should be accepted based on TIB state and the interface on which that 
the packet arrived.  Packets that fail the RPF check MUST NOT be 
forwarded and the router will conduct an assert process for the (S,G) 
pair specified in the packet.  Packets for which a route to the source 
cannot be found MUST be discarded. 

If the RPF check has been passed, an outgoing interface list is 
constructed for the packet.  If this list is not empty, then the packet 
MUST be forwarded to all listed interfaces.  If the list is empty, then 
the router will conduct a prune process for the (S,G) pair specified in 
the packet.








Adams, Nicholas, Siadak                                         [Page 8]

On receipt on a data packet from S addressed to G on interface iif:

if (iif == RPF_interface(S) AND UpstreamPState(S,G) != Pruned) {
    oiflist = olist(S,G)
} else {
    oiflist = NULL
}
forward packet on all interfaces in oiflist

This pseudocode employs the following  "macro" definition:

UpstreamPState(S,G) is the state of the Upstream(S,G) state machine in 
section 6.4.1.

6.3 Hello Messages

This section describes the generation and processing of Hello messages.

6.3.1 Sending Hello Messages

PIM-DM uses Hello messages to detect other PIM routers.  Hello messages 
are sent periodically on each PIM enabled interface.  Hello messages are
multicast to the ALL-PIM-ROUTERS group.  When PIM is enabled on an 
interface or a router first starts, the Hello Timer (HT) MUST be set to 
random value between 0 and Triggered_Hello_Delay.  This prevents 
synchronization of Hello messages if multiple routers are powered on 
simultaneously.  

After the initial Hello message, a Hello message MUST be sent every 
Hello_Period.  A single Hello timer MAY be used to trigger sending 
Hello messages on all active interfaces.  The Hello Timer SHOULD NOT be 
reset except when it expires.

6.3.2 Receiving Hello Messages

When a Hello message is received, the receiving router SHALL record the 
receiving interface, the sender and any information contained in 
recognized options.  This information is retained for a number of 
seconds in the Hold Time field of the Hello Message.  If a new Hello 
message is received from a particular neighbor N, the Neighbor Liveness 
Timer (NLT(N,I)) MUST be reset to the newly received Hello Holdtime.  If
a Hello message is received from a new neighbor, the receiving router 
SHOULD send its own Hello message after a random delay between 0 and 
Triggered_Hello_Delay.

6.3.3 Hello Message Hold Time

The Hold Time in the Hello Message should be set to a value that can 
reasonably be expected to keep the Hello active until a new Hello 
message is received.  On most links, this will be 3.5 times the value of
Hello_Period.

If the Hold Time is set to '0xffff', the receiving router MUST NOT time 
out that Hello message.  This feature might be used for on-demand links 
to avoid keeping the link up with periodic Hello messages.

Adams, Nicholas, Siadak                                         [Page 9]

If a Hold Time of '0' is received, the corresponding neighbor state is 
expired immediately. When a PIM router takes an interface down or 
changes IP address, a Hello message with a zero Hold Time SHOULD be sent
immediately (with the old IP address if the IP address is changed) to 
cause any PIM neighbors to remove the old information immediately.

6.3.4 Handling Router Failures

If a Hello message is received from an active downstream neighbor with 
a different Generation ID (GenID), the neighbor has restarted and may 
not contain the correct (S,G) state. A Hello message SHOULD be sent 
after a random delay between 0 and Triggered_Hello_Delay (see 6.8.1) 
before any other messages are sent.  The router MAY replay the last 
State Refresh message for any (S,G) pairs for which it is the Assert 
Winner indicating Prune and Assert status to the downstream router.  
These State Refresh messages SHOULD be sent out immediately after the 
Hello message.  

Upon startup, a router MAY use any State Refresh messages received 
within Hello_Period of its first Hello message on an interface to 
establish state information.  The State Refresh source will be the 
RPF'(S), and Prune status for all interfaces will be set according to 
the Prune Indicator bit in the State Refresh message.  If the Prune 
Indicator is set, the router SHOULD set the PruneLimitTimer to 
Prune_Holdtime and set the PruneTimer on all downstream interfaces to 
the State Refresh's Interval times two.  The router SHOULD then 
propagate the State Refresh as described in section 6.5.1.

6.3.5 Reducing Prune Propagation Delay on LANs 

If all routers on a LAN support the LAN Prune Delay option, then the PIM
routers on that LAN will use the values received to adjust its 
J/P_Override_Interval on that interface and the interface is LAN Delay 
Enabled.  Briefly, to avoid synchronization of Prune Override (Join) 
messages when multiple downstream routers share a multi-access link, 
sending of such messages is delayed by a small random amount of time. 
The period of randomization is configurable and has a default value of 3
seconds. 

Each router on the LAN expresses its view of the amount of randomization
necessary in the Override Interval field of the LAN Prune Delay option. 
When all routers on a LAN use the LAN Prune Delay Option, all routers on
the LAN MUST set their Override_Interval to the largest Override value 
on the LAN.

The LAN Delay inserted by a router in the LAN Prune Delay option 
expresses the expected message propagation delay on the link and SHOULD 
be configurable by the system administrator. When all routers on a link 
use the LAN Prune Delay Option, all routers on the LAN MUST set 
Propagation Delay to the largest LAN Delay on the LAN. 






Adams, Nicholas, Siadak                                        [Page 10]

PIM implementers should enforce a lower bound on the permitted values 
for this delay to allow for scheduling and processing delays within 
their router. Such delays may cause received messages to be processed 
later as well as triggered messages to be sent later than intended. 
Setting this LAN Prune Delay to too low a value may result in temporary 
forwarding outages because a downstream router will not be able to 
override a neighbor's prune message before the upstream neighbor stops 
forwarding. 

6.4 PIM-DM Prune, Join and Graft Messages

This section describes the generation and processing of PIM-DM Join, 
Prune and Graft messages.  Prune messages are sent towards the upstream 
neighbor for S to indicate that traffic from S addressed to group G is 
not desired.  In the case of two downstream routers A and B, where A 
wishes to continue receiving data and B does not, A will send a Join in 
response to B's Prune to override the Prune.  This is the only situation
in PIM-DM in which a Join message is used.  Finally, a Graft message is 
used to re-join a previously pruned branch to the delivery tree.

6.4.1 Upstream Prune, Join and Graft Messages

The Upstream(S,G) state machine for sending Prune, Graft and Join 
messages is given below.  There are three states.

  Forwarding (F)
    This is the starting state of the Upsteam(S,G) state machine.  The 
    state machine is in this state if it just started or if 
    oiflist(S,G) != NULL.

  Pruned(P)
    The set, olist(S,G), is empty.  The router will not forward data 
    from S addressed to group G.

  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