draft-ietf-pim-bidir-03.txt

BCAST Implementation for NS2

Note: A major advantage of using a Designated Forwarder in BIDIR-PIM
compared to PIM-SM is that special treatment is no longer required for
sources that are directly connected to a router. Data from such sources
does not need to be differentiated from other multicast traffic and will
automatically be picked up by the DF. This removes the need for
performing a directly-connected-source check for data to groups that do
not have existing state.


3.3.1.  Source-Only Branches

Source-only branches of the distribution tree for a group G are branches
which do not lead to any receivers, but which are used to forward
packets traveling upstream from sources towards the RP.  Routers along
source-only branches only have the RPF_interface to the RP in their
olist for G and hence do not need to maintain any group specific state.
Upstream forwarding can be performed using RP state.  An implementation
may decide to maintain group state for source-only branches for
accounting or performance reasons.

3.4.  PIM Join/Prune Messages

A BIDIR-PIM Join/Prune message consists of a list of Joined and Pruned
Groups. When processing a received Join/Prune message, each Joined or
Pruned Group is effectively considered individually by applying the
following state machines.  When considering a Join/Prune message whose



Handley/Kouvelas/Speakman/Vicisano               Section 3.4.  [Page 13]

INTERNET-DRAFT           Expires: December 2001                June 2001


PIM Destination field addresses this router, (*,G) Joins and Prunes can
affect the downstream state machine.  When considering a Join/Prune
message whose PIM Destination field addresses another router, most Join
or Prune entries could affect the upstream state machine.


3.4.1.  Receiving (*,G) Join/Prune Messages

When a router receives a Join(*,G) or Prune(*,G) it must first check to
see whether the RP in the message matches RP(G) (the router's idea of
who the RP is). If the RP in the message does not match RP(G) the Join
or Prune MUST be silently dropped. In addition a router MUST NOT process
Join(*,G) messages targeted to itself if it is not the DF for RP(G) on
the interface on which the message was received.

The per-interface state-machine for receiving (*,G) Join/Prune Messages
is given below. There are three states:

     NoInfo (NI)
          The interface has no (*,G) Join state and no timers running.

     Join (J)
          The interface has (*,G) Join state which will cause us to
          forward packets destined for G from this interface.

     PrunePending (PP)
          The router has received a Prune(*,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 Join state.

In addition the state-machine uses two timers:

     ExpiryTimer (ET)
          This timer is restarted when a valid Join(*,G) is received.
          Expiry of the ExpiryTimer causes the interface state to revert
          to NoInfo for this group.

     PrunePendingTimer (PPT)
          This timer is set when a valid Prune(*,G) is received.  Expiry
          of the PrunePendingTimer causes the interface state to revert
          to NoInfo for this group.








Handley/Kouvelas/Speakman/Vicisano             Section 3.4.1.  [Page 14]

INTERNET-DRAFT           Expires: December 2001                June 2001


                    +-----------------------------------+
                    | Figures omitted from text version |
                    +-----------------------------------+

           Figure 1: Downstream group per-interface state-machine


In tabular form, the group per-interface state-machine is:

+----------+------------------------------------------------------------+
|          |                     Event                                  |
|          +----------+------------+-----------+------------+-----------+
Prev State |Receive   |Receive     |Prune      |Expiry      Stop Being  |
|          |Join(*,G) |Prune(*,G)  |Pending    |Timer       DF on I     |
|          |          |            |Timer      |Expires     |           |
|          |          |            |Expires    |            |           |
+----------+----------+------------+-----------+------------+-----------+
|          |-> J state|-> NI state |-          |-           +           |
NoInfo     |start     |            |           |            |           |
(NI)       |Expiry    |            |           |            |           |
|          |Timer     |            |           |            |           |
+----------+----------+------------+-----------+------------+-----------+
|          |-> J state|-> PP state |-          |-> NI state +> NI state |
Join (J)   |restart   |start Prune |           |            |           |
|          |Expiry    |Pending     |           |            |           |
|          |Timer     |Timer       |           |            |           |
+----------+----------+------------+-----------+------------+-----------+
|          |-> J state|-> PP state |-> NI state|-> NI state +> NI state |
|          |restart   |            |Send Prune-|            |           |
Prune      |Expiry    |            |Echo(*,G)  |            |           |
Pending    |Timer;    |            |           |            |           |
(PP)       |stop Prune|            |           |            |           |
|          |Pending   |            |           |            |           |
|          |Timer     |            |           |            |           |
+----------+----------+------------+-----------+------------+-----------+

The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" imply
receiving a Join or Prune targeted to this router's address on the
received interface.  If the destination address is not correct, these
state transitions in this state machine must not occur, although seeing
such a packet may cause state transitions in other state machines.

On unnumbered interfaces on point-to-point links, the router's address
should be the same as the source address it chose for the hello packet
it sent over that interface.  However on point-to-point links we also
recommend that PIM messages with a 0.0.0.0 destination address are also
accepted.




Handley/Kouvelas/Speakman/Vicisano             Section 3.4.1.  [Page 15]

INTERNET-DRAFT           Expires: December 2001                June 2001


The transition event "Stop being DF" implies a DF re-election taking
place on this router interface and the router changing status from being
the active DF to being a non-DF router (the value of the I_am_DF macro
changing to FALSE).

When ExpiryTimer is started or restarted, it is set to the HoldTime from
the triggering Join/Prune message.

When PrunePendingTimer is started, it is set to the
J/P_Override_Interval if the router has more than one neighbor on that
interface; otherwise it is set to zero causing it to expire immediately.

The action "Send PruneEcho(*,G)" is triggered when the router stops
forwarding on an interface as a result of a prune.  A PruneEcho(*,G) is
simply a Prune(*,G) message sent by the upstream router to itself on a
LAN.  Its purpose is to add additional reliability so that if a Prune
that should have been overridden by another router is lost locally on
the LAN, then the PruneEcho may be received and cause the override to
happen.  A PruneEcho(*,G) need not be sent on a point-to-point
interface.


3.4.2.  Sending Join/Prune Messages

The downstream per-interface state-machines described above hold join
state from downstream PIM routers. This state then determines whether a
router needs to propagate a Join(*,G) upstream towards the RP.  Such
Join(*,G) messages are sent on the RPF_interface towards the RP and are
targeted at the DF on that interface.

If a router wishes to propagate a Join(*,G) upstream, it must also watch
for messages on its upstream interface from other routers on that
subnet, and these may modify its behavior.  If it sees a Join(*,G) to
the correct upstream neighbor, it should suppress its own Join(*,G).  If
it sees a Prune(*,G) to the correct upstream neighbor, it should be
prepared to override that prune by sending a Join(*,G) almost
immediately.  Finally, if it sees the Generation ID (see PIM-SM
specification [9]) of the correct upstream neighbor change, it knows
that the upstream neighbor has lost state, and it should be prepared to
refresh the state by sending a Join(*,G) almost immediately.

In addition changes in the next hop towards the RP trigger a prune off
from the old next hop, and join towards the new next hop. Such a change
can be cause by the following two reasons:

     o The MRIB indicates that the RPF_interface towards the RP has
       changed.




Handley/Kouvelas/Speakman/Vicisano             Section 3.4.2.  [Page 16]

INTERNET-DRAFT           Expires: December 2001                June 2001


     o There is a DF re-election on the RPF_interface and a new router
       emerges as the DF.

The upstream (*,G) state-machine only contains two states:

Not Joined
     The downstream state-machines indicate that the router does not
     need to join the RP tree for this group.

Joined
     The downstream state-machines indicate that the router would like
     to join the RP tree for this group.

In addition, one timer JT(G) is kept which is used to trigger the
sending of a Join(*,G) to the upstream next hop towards the RP (the DF
on the RPF_interface for RP(G)).

                    +-----------------------------------+
                    | Figures omitted from text version |
                    +-----------------------------------+

                   Figure 2: Upstream group state-machine





























Handley/Kouvelas/Speakman/Vicisano             Section 3.4.2.  [Page 17]

INTERNET-DRAFT           Expires: December 2001                June 2001


In tabular form, the state machine is:

+----------------------+------------------------------------------------+
|                      |                     Event                      |
|  Prev State          +------------------------+-----------------------+
|                      |    JoinDesired(G)      |    JoinDesired(G)     |
|                      |    ->True              |    ->False            |
+----------------------+------------------------+-----------------------+
|                      |    -> J state          |    -                  |
|  NotJoined (NJ)      |    Send Join(*,G);     |                       |
|                      |    Set Timer to        |                       |
|                      |    t_periodic          |                       |
+----------------------+------------------------+-----------------------+
|  Joined (J)          |    -                   |    -> NJ state        |
|                      |                        |    Send Prune(*,G)    |
+----------------------+------------------------+-----------------------+

In addition, we have the following transitions which occur within the
Joined state:

+-----------------------------------------------------------------------+
|                         In Joined (J) State                           |
+-----------------+-----------------+-----------------+-----------------+
|Timer Expires    | See Join(*,G)   | See Prune(*,G)  | RPF_DF(RP(G))   |
|                 | to              | to              | changes         |
|                 | RPF_DF(RP(G))   | RPF_DF(RP(G))   |                 |
+-----------------+-----------------+-----------------+-----------------+
|Send             | Increase Timer  | Decrease Timer  | Decrease Timer  |
|Join(*,G); Set   | to              | to t_override   | to t_override   |
|Timer to         | t_suppressed    |                 |                 |
|t_periodic       |                 |                 |                 |
+-----------------+-----------------+-----------------+-----------------+

+-----------------------------------------------------------------------+
|                         In Joined (J) State                           |
+-------------------------------------+---------------------------------+
|     Change of RPF_DF(RP(G))         |        RPF_DF(RP(G)) GenID      |
|                                     |        changes                  |
+-------------------------------------+---------------------------------+
|     Send Join(*,G) to new           |        Decrease Timer to        |
|     DF; Send Prune(*,G) to          |        t_override               |
|     old DF; set Timer to            |                                 |
|     t_periodic                      |                                 |
+-------------------------------------+---------------------------------+







Handley/Kouvelas/Speakman/Vicisano             Section 3.4.2.  [Page 18]

INTERNET-DRAFT           Expires: December 2001                June 2001


This state machine uses the following macro:

  bool JoinDesired(G) {
     if (olist(G) (-) RPF_interface(RP(G))) != NULL
         return TRUE
     else
         return FALSE
  }


3.5.  Designated Forwarder (DF) Election

This section presents a fail-safe mechanism for electing a per-RP
designated router on each link in a BIDIR-PIM domain. We call this
router the Designated Forwarder (DF).


3.5.1.  DF Requirements

The DF election chooses the best router on a link to assume the
responsibility of forwarding traffic between the RP and the link for the
range of multicast groups served by the RP.  Different multicast groups
that share a common RP must use the same bi-directional tree for data
forwarding. Hence, the election of an upstream forwarder on each link
does not have to be a group specific decision but instead can be RP-
specific. As the number of RPs is typically small, the number of
elections that have to be performed is significantly reduced by this
observation.

To optimise tree creation, it is desirable that the winner of the