draft-ietf-pim-bidir-03.txt

BCAST Implementation for NS2

election process should be the router on the link with the "best"
unicast routing metric to the RP (as reported by the MRIB). When
comparing metrics from different unicast routing protocols, we use the
same comparison rules used by the PIM-SM assert process [9].

The election process needs to take place when information on a new RP
initially becomes available, and can be re-used as new bidir groups for
the same RP are encountered. There are however some conditions where an
update to the election is required:

     o There is a change in unicast metric to reach the RP for any of
       the routers on the link.

     o The interface on which the RP is reachable changes to an
       interface for which the router was previously the DF.

     o A new PIM neighbor starts up on a link.




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


     o The elected DF dies.

The election process has to be robust enough to ensure with very high
probability that all routers on the link have a consistent view of the
DF. This is because with the forwarding rules described in section 3.3
if multiple routers end-up thinking that they should be responsible for
forwarding, loops may result. To reduce the possibility of this
occurrence to a minimum, the election algorithm has been biased towards
discarding DF information and suspending forwarding during periods of
ambiguity.


3.5.2.  DF Election description

This section does not provide the definitive specification for the DF
election process. If any discrepancy exists between section 3.5.3 and
this section, the specification in section 3.5.3 is to be assumed
correct.

To perform the election of the DF for a particular RP, routers on a link
need to exchange their unicast routing metric information (as reported
by the MRIB) for reaching the RP.

In the election protocol described below, many message exchanges are
repeated Election_Robustness times for reliability. In all those cases
the message retransmissions are spaced in time by a small random
interval.


3.5.2.1.  Bootstrap Election

Initially when no DF has been elected, routers finding out about a new
RP start participating in the election by sending Offer messages.  Offer
messages include the router's metric to reach the RP. Offers are
periodically retransmitted with a period of Offer_Interval.

If a router hears a better offer than its own from a neighbor, it stops
participating in the election for a period of Election_Robustness *
Offer_Interval. If during this period no winner is elected, then the
router restarts the election from the beginning. If a router receives an
offer with worse metrics than its own, then it restarts the election
from the beginning.

The result should be that all routers except the best candidate stop
advertising their offers.

A router assumes the role of the DF after having advertised its metrics
Election_Robustness times without receiving any offer from any other



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


neighbor. At that point it transmits a Winner message which declares to
every other router on the link the identity of the winner and the
metrics it is using.

Routers hearing a winner message stop participating in the election and
record the identity and metrics of the winner. If the local metrics are
better than those of the winner then the router records the identity of
the winner but reinitiates the election.


3.5.2.2.  Loser Metric Changes

Whenever the unicast metric to a RP changes for a non-DF router to a
value that is better than that previously advertised by the acting DF,
the router with the new metric should take action to eventually assume
forwarding responsibility. After the metric change is detected, the non-
DF router with the now better metric restarts the DF election process by
sending Offer messages with this new metric. If no response is received
after Election_Robustness retransmissions, the router assumes the role
of the DF following the usual Winner announcement procedure.

Upon receipt of an offer that is worse than its current metric, the DF
will respond with a Winner message declaring its status and advertising
its metric. Upon receiving this message, the originator of the Offer
records the identity of the DF and aborts the election.

Upon receipt of an offer that is better than its current metric, the DF
records the identity and metrics of the offering router and responds
with a Backoff message. This instructs the offering router to hold off
for a short period of time while the unicast routing stabilises. The
Backoff message includes the offering router's new metric and address.
All routers on the link who have pending offers with metrics worse than
those in the backoff message (including the original offering router)
will hold further offers for a period of time defined in the Backoff
message.

If during the Backoff_Period, a third router sends a new better offer,
the Backoff message is repeated for the new offer and the Backoff_Period
restarted.

Before the Backoff_Period expires, the acting DF nominates the router
having made the best offer as the new DF using a Pass message.  This
message includes the IDs and metrics of both the old and new DFs.  The
old DF stops performing its tasks as soon as the transmission is made.
The new DF assumes the role of the DF as soon as it receives the Pass
message. All other routers on the link take note of the new DF and its
metric.




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


3.5.2.3.  Winner Metric Changes

If the DF's routing metric to reach the RP changes to a worse value, it
sends a set of Election_Robustness randomly spaced Winner messages on
the link, advertising the new metric. Routers who receive this
announcement but have a better metric may respond with an Offer message
which results in the same handoff procedure described above.  All
routers assume the DF has not changed until they see a Pass or Winner
message indicating the change.

There is no pressure to make this handoff quickly if the acting DF still
has a path to the RP. The old path may now be suboptimal but it will
still work while the re-election is in progress.

If the routing metric at the DF changes to a better value, a single
Winner message is sent advertising the new metric.


3.5.2.4.  Winner Loses Path

If a router's RPF_interface to the RP switches to be on a link for which
it is acting as the DF, then it can no longer provide forwarding
services for that link. It therefore immediately stops being the DF and
restarts the election. As its path to the RP is through the link, an
infinite metric is used in the Offer message it sends.

Note: At this stage the old DF will have a new RPF neighbor on the link
(indicated by unicast routing) which it could use in a Pass message but
this adds unnecessary complication to the election process.


3.5.2.5.  Late Router Starting Up

A late router starting up after the DF election process has completed
will have no immediate knowledge of the election outcome. As a result,
it will start advertising its metric in Offer messages. As soon as this
happens, the currently elected DF will respond with a Winner message if
its metric is better than the metric in the Offer message, or with a
Backoff message if its metric worse than the metric in the Offer
message.


3.5.2.6.  Winner Dies

Whenever the DF dies, a new DF has to be elected. The speed at which
this can be achieved depends on whether there are any downstream routers
on the link.




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


If there are downstream routers, typically their RPF_neighbor as
reported by the MRIB before the DF dies will be the DF itself. They will
therefore notice either a change in the metric for the route to the RP
or a change in RPF_neighbor away from the DF and will restart the
election by transmitting Offer messages.  If according to the MRIB the
RP is now reachable through the same link via another upstream router,
an infinite metric will be used in the Offer.

If no downstream routers are present, the only way for other upstream
routers to detect a DF failure is by the timeout of the PIM neighbor
information, which will take significantly longer.


3.5.3.  Election Protocol Specification

This section provides the definitive specification for the DF election
process. If any discrepancy exists between section 3.5.2 and this
section, the specification in this section is to be assumed correct.


3.5.3.1.  Election State

The DF election state is maintained per RP for each multicast enabled
interface on the router as introduced in section 3.1:

The state machine has the following four states:

     Offer
          Initial election state. When in the Offer state a router
          thinks it can eventually become the winner and periodically
          generates Offer messages.

     Lose In this state the router knows that there either is a
          different election winner or that no router on the link has a
          path to the RP.

     Winner
          The router is the acting DF without any contest.

     Backoff
          The router is the acting DF but another router has made a bid
          to take over.

In the state machine a router is considered to be an acting DF if it is
in the Win or Backoff states.

The operation of the election protocol makes use of the variables and
timers described below:



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


     Acting DF information
          Used to store the election winner who is the currently acting
          DF.

     Election-Timer (DFT)
          Used to schedule transmission of Offer, Winner and Pass
          messages.

     Offer-Count (OC)
          Used to maintain the number of times an Offer or Winner
          message has been transmitted.

     Best-Offer
          Used by the DF to record who has made the last offer for
          sending the Pass message.


3.5.3.2.  Election Messages

The election process uses the following PIM control messages the packet
format of which is described in section 3.7:

     Offer (OfferingID, Metric)
          Sent by routers that believe they have a better metric to the
          RP than the metric that has been on offer so far.

     Winner (DF-ID, DF-Metric)
          Sent by a router when assuming the role of the DF or when re-
          asserting in response to worse offers.

     Backoff (DF-ID, DF-Metric, OfferingID, OfferMetric,
          BackoffInterval)
          Used by the DF to acknowledge better offers. It instructs
          other routers with equal or worse offers to wait till the DF
          passes responsibility to the sender of the offer.

     Pass (Old-DF-ID, Old-DF-Metric, New-DF-ID, New-DF-Metric)
          Used by the old DF to pass forwarding responsibility to a
          router that has previously made an offer.  The Old-DF-Metric
          is the current metric of the DF at the time the pass is sent.


3.5.3.3.  Election Events

During protocol operation, in addition to the expiration of the
Election-Timer and the reception of the four control messages, the
following events can take place:




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


     o Discovery of new RP

     o Metric reported by the MRIB to reach the RP changes

     o DF loses path to RP

     o Detection of DF failure

3.5.3.4.  Election Notation

The DF election state machine description uses the following notation in
addition to the pseudocode notation described earlier in this spec.

     ?=  denotes the operation of lowering a timer to a new value. If
         the timer is not running then it is started using the new
         value. If the timer is running with an expiration lower than
         the new value, then the timer is not altered.

When a control message is received and actions are specified on a
condition that metrics are Better or Worse the comparison must be
performed as follows:

     o On receipt of an Offer or Winner message compare our current
       metrics for the DF with the metrics advertised for the sender of
       the message.

     o On receipt of a Backoff or Pass message compare our current
       metrics for the DF with the metrics advertised for the target of
       the message.

When an action of "set DF to Sender or Target" is encountered during
receipt of a Winner, Pass or Backoff message it means the following:

     o On receipt of a Winner message set the DF to be the originator of
       the message and record its metrics.

     o On receipt of a Pass message set the DF to be the target of the
       message and record its metrics.