Internet Engineering Task Force                                   PIM Working Group WG
INTERNET-DRAFT                                        Mark Handley
Internet Draft                                                     ACIRI
Expiration Date: September, 2000 Handley/ACIRI
draft-ietf-pim-bidir-01.txt                        Isidor Kouvelas
                                                           cisco Systems Kouvelas/Cisco
                                                  Lorenzo Vicisano
                                                           cisco Systems
                                                           March 1, Vicisano/Cisco
                                                        23 November 2000
                                                       Expires: May 2001

       Bi-directional Protocol Independent Multicast
                     <draft-ietf-pim-bidir-00.txt> (BIDIR-PIM)

Status of this Memo Document

This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026.

Internet-Drafts are working documents of the Internet Engineering Task
Force (IETF), its areas, and its working groups.  Note that other groups
may also distribute working documents as Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time.  It is inappropriate to use Internet-Drafts as reference material
or to cite them other than as "work in progress."

The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt

The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.

This document is a product of the IETF PIM WG.  Comments should be
addressed to the authors, or the WG's mailing list at
pim@catarina.usc.edu.

                                Abstract

     This document discusses Bi-directional PIM, a variant of PIM Sparse-
   Mode [1]
     Sparse-Mode [9] that builds bi-directional shared trees
     connecting multicast sources and receivers. Bi-directional
     trees are built using a fail-
   safe fail-safe Designated Forwarder (DF)
     election mechanism operating on each link of a multicast
     topology.  With the assistance of the DF, multi-
   cast multicast data is
     natively forwarded from sources to the Rendezvous-Point
     without requiring source-specific state.  The DF election
     takes place at RP discovery time and provides a default route
     to the RP thus eliminating the requirement for data-driven
     protocol events.

1

Note on BIDIR-PIM status

The differences between this version of the BIDIR-PIM specification and
draft-ietf-pim-bidir-new-00.txt are mostly in the format of the
information presented. As BIDIR-PIM has many similarities in operation
to Sparse-Mode PIM, the earlier version of this spec relied heavily on
the now obsolete PIM-SM [11] specification. This revision removes this
dependency and instead references the new Sparse-Mode documentation [9]
where necessary. In addition the method in which the protocol
specification is presented has been updated to follow the format of [9].

                           Table of Contents

1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . .   5
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . .   6
 2.1. Definitions. . . . . . . . . . . . . . . . . . . . . . . . . .   6
 2.2. Pseudocode Notation. . . . . . . . . . . . . . . . . . . . . .   7
3. Protocol Specification. . . . . . . . . . . . . . . . . . . . . .   8
 3.1. BIDIR-PIM Protocol State . . . . . . . . . . . . . . . . . . .   8
  3.1.1. General Purpose State . . . . . . . . . . . . . . . . . . .   9
  3.1.2. RP State. . . . . . . . . . . . . . . . . . . . . . . . . .   9
  3.1.3. Group State . . . . . . . . . . . . . . . . . . . . . . . .  10
  3.1.4. State Summarization Macros. . . . . . . . . . . . . . . . .  11
 3.2. PIM Neighbor Discovery . . . . . . . . . . . . . . . . . . . .  12
 3.3. Data Packet Forwarding Rules . . . . . . . . . . . . . . . . .  12
  3.3.1. Source-Only Branches. . . . . . . . . . . . . . . . . . . .  13
 3.4. PIM Join/Prune Messages. . . . . . . . . . . . . . . . . . . .  13
  3.4.1. Receiving (*,G) Join/Prune Messages . . . . . . . . . . . .  14
  3.4.2. Sending Join/Prune Messages . . . . . . . . . . . . . . . .  16
 3.5. Designated Forwarder (DF) Election . . . . . . . . . . . . . .  19
  3.5.1. DF Requirements . . . . . . . . . . . . . . . . . . . . . .  19
  3.5.2. DF Election description . . . . . . . . . . . . . . . . . .  20
   3.5.2.1. Bootstrap Election . . . . . . . . . . . . . . . . . . .  20
   3.5.2.2. Loser Metric Changes . . . . . . . . . . . . . . . . . .  21
   3.5.2.3. Winner Metric Changes. . . . . . . . . . . . . . . . . .  22
   3.5.2.4. Winner Loses Path. . . . . . . . . . . . . . . . . . . .  22
   3.5.2.5. Late Router Starting Up. . . . . . . . . . . . . . . . .  22
   3.5.2.6. Winner Dies. . . . . . . . . . . . . . . . . . . . . . .  22
  3.5.3. Election Protocol Specification . . . . . . . . . . . . . .  23
   3.5.3.1. Election State . . . . . . . . . . . . . . . . . . . . .  23
   3.5.3.2. Election Messages. . . . . . . . . . . . . . . . . . . .  23
   3.5.3.3. Election Events. . . . . . . . . . . . . . . . . . . . .  24
   3.5.3.4. Election State Transitions . . . . . . . . . . . . . . .  24
 3.6. Timers and Constants . . . . . . . . . . . . . . . . . . . . .  28
 3.7. PIM DF Election Packet Formats . . . . . . . . . . . . . . . .  31
  3.7.1. Backoff Message . . . . . . . . . . . . . . . . . . . . . .  32
  3.7.2. Pass Message. . . . . . . . . . . . . . . . . . . . . . . .  33
4. RP Discovery. . . . . . . . . . . . . . . . . . . . . . . . . . .  33
5. Security Considerations . . . . . . . . . . . . . . . . . . . . .  34
 5.1. Appendix A: Election Reliability
 Enhancements. . . . . . . . . . . . . . . . . . . . . . . . . . . .  34
  5.1.1. A.1 Missing Pass. . . . . . . . . . . . . . . . . . . . . .  34
  5.1.2. A.2 Periodic Winner Announcement. . . . . . . . . . . . . .  35
 5.2. Appendix B: Interoperability with legacy
 code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  35
 5.3. Appendix C: Comparison with PIM-SM . . . . . . . . . . . . . .  35
6. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . . .  36
7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  37

8. References. . . . . . . . . . . . . . . . . . . . . . . . . . . .  37
9. Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  39

1.  Introduction

This document discusses Bi-directional PIM, a variant of PIM Sparse
   Mode [1] Sparse-Mode
(PIM-SM) [9] that builds bi-directional shared trees connecting
multicast sources and receivers.

   PIM Sparse-Mode (PIM-SM) version 1 and version 2 construct uni-
   directional

PIM-SM constructs uni-directional shared trees that are used to forward
data from senders to receivers of a multicast group.  PIM-SM also allows
the construc-
   tion construction of source specific trees, but this capability is not
related to the proposal protocol described in this document.

The shared tree for each multicast group is rooted at a multicast router
called the Rendezvous Point (RP). Different multicast group ranges can
use separate RPs within a PIM domain.

In unidirectional sparse-mode PIM, PIM-SM, there are two possible methods for
distributing data packets on the shared tree. These differ in the way
packets are forwarded from a source to the RP:

o Initially when a source starts transmitting, it's first hop router
  encapsulates data packets in special control messages (Registers)
  which are unicast to the RP. After reaching the RP the packets are
  decapsulated and distributed on the shared tree.

o A transition from the above distribution mode can be made at a later
  stage.  This is achieved by building source specific state on all
  routers along the path between the source and the RP.  This state is
  then used to natively forward packets from that source.

Both these mechanisms suffer from problems. Encapsulation results in
significant processing, bandwidth and delay overheads. Forwarding using
source specific state has additional protocol and memory requirements.

Bi-directional PIM dispenses with both encapsulation and source state by
allowing packets to be natively forwarded from a source to the RP using
shared tree state. For a complete discussion of the pros and cons of Bi-directional Bi-
directional PIM consult appendix C.

The ideas presented in this document are similar to those described in [2].
[10]. The main difference between the two proposals is in the method
used to forward packets traveling upstream from a source to the RP. In
particular [2] [10] uses an IP option (UMP option) on data packets to assist
with upstream forwarding. The UMP option identifies the next hop router
responsible for forwarding the packet upstream.  In contrast, this
proposal does not alter data packets to embed con-
   trol control information.
Instead the identification of the next hop upstream forwarder is
performed at RP discovery time using a fail-safe elec-
   tion election mechanism. This significantly simplifies forwarding procedures
   and eliminates forwarding loops

2.  Terminology

In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL",
"SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and packet duplication problems that
   exist
"OPTIONAL" are to be interpreted as described in [2].  Appendix D presents RFC 2119 and indicate
requirement levels for compliant PIM-SM implementations.

2.1.  Definitions

This specification uses a comparison between number of terms to refer to the proposal roles of
routers participating in this document and [2]. BIDIR-PIM.  The rest of this document following terms have special
significance for BIDIR-PIM:

MRIB  Multicast Routing Information Base.  This is the multicast
      topology table, which is structured typically derived from the unicast
      routing table, or routing protocols such as follows. Section 2 defines
   basic terms. Section 3 describes bidirectional tree formation MBGP that carry
      multicast-specific topology information.  In PIM-SM this is used
      to make decisions regarding where to forward Join/Prune messages
      and
   forwarding.  The new forwarding rules rely heavily on an election
   mechanism described in section 4.

2 Definitions

   In the discussion below, BIDIR-PIM is used as a source for routing metrics for the terms upstream, downstream and RPF
   interface are always referring
      DF election process.

Rendezvous Point (RP):
      An RP is a router that has been configured to be used as the shared tree rooted at the Ren-
   dezvous Point. Downstream indicates root
      of the direction on which packets
   travel distribution tree for a range of multicast groups. Join
      messages from the RP to receivers along for a group are sent towards the shared tree. RP.

Upstream indi-
   cates
      Towards the opposite root (Rendezvous-Point) of the tree. The direction
      used by packets traveling from sources to the RP. The RPF interface for a group is the interface unicast
   routing uses to reach the RP.

   We assume that the reader is familiar with the unidirectional PIM-SM
   protocol [1], as much of the functionality is common to the version
   of bidir PIM described below. In particular in the rest of this docu-
   ment we will use

Downstream
      Away from the concepts root of (*,G), (S,G) and (*,*,RP) state and
   their component fields (olist, iif, ...). We will also reference Join
   and Prune messages whose semantics and packet formats are defined in
   [1]. In the context of this document, entries in Join and Prune mes-
   sages always have tree. The direction on which packets
      travel from the RP and WC bits set.  Also, default timer values
   are the ones given in [1]. to receivers.

Designated Forwarder (DF):
      The protocol presented in this document is largely based on the con-
   cept
      concept of a Designated Forwarder (DF). A single DF exists for
      each RP on every link within a PIM BIDIR-PIM domain (this includes
      both multi-access and point-to-point links). The DF is the router
      on the link with the best unicast route to the RP.  A DF for a
      given RP is in charge of forwarding traffic downstream traffic onto the
      link, and forwarding upstream traffic from the link towards the
      RP.  It does this for all the bi-
   directional bi-directional groups served by the
      RP. For those familiar with the DR
   in PIM-SM, the Bidir The DF provides the same support on a link is also responsible for local
   receivers. The DF election procedures are described in section 4.

3 Tree Building and Forwarding

   This section describes how bi-directional tree building procedures
   and forwarding rules vary interpreting IGMP
      information from normal PIM-SM operation.

   A router learns which multicast addresses will be used for sparse-
   mode PIM local receivers and which will be originating Join messages
      towards the RP.

RPF Interface
      RPF stands for bidirectional groups along "Reverse Path Forwarding".  The RPF Interface of a
      router with respect to an address is the
   candidate RP information through PIM-SM bootstrap messages.  Thus
   unidirectional and bidirectional groups can coexist in the same
   domain.

   Throughout interface that the section it is assumed MRIB
      indicates should be used to forward packets to that on each link, all address.  In
      the
   routers have case of a consistent view on which router has the best path to BIDIR-PIM multicast group, the RP. This router RPF interface is called the DF for
      interface that would be used to send packets to the RP on for the link. This
   assumption rests on
      group.

RPF Neighbor
      The RPF Neighbor of a router with respect to an address is the DF election procedures described in section
   4.

   In
      neighbor that the procedures described MRIB indicates should be used to forward packets
      to that address. Note that in BIDIR-PIM, the rest of this section, if DF infor-
   mation RPF neighbor for a
      group is required but not available (election is incomplete), then
   no tree building or forwarding action is taken.

3.1 Tree Building

3.1.1 Joining necessarily the (Shared) Tree

   The procedures for joining router on the (*,G) shared tree, RPF interface that Join
      messages for that group would be directed to (Join messages are almost identi-
   cal
      directed to those used in PIM-SM with the difference that DF on the tasks of RPF interface for the
   DR are handled by group).

TIB   Tree Information Base.  This is the DF.

   When collection of state at a PIM
      router receives a membership indication from IGMP for a
   bidirectional group G with rendezvous point RP, that has been created by receiving PIM Join/Prune messages,
      PIM DF election messages and it is IGMP information from local hosts.
      It essentially stores the DF for state of all multicast distribution
      trees at that router.

MFIB  Multicast Forwarding Information Base.  The TIB holds all the RP on
      state that is necessary to forward multicast packets at a router.
      However, although this specification defines forwarding in terms
      of the link on which TIB, to actually forward packets using the report was received, TIB is very
      inefficient.  Instead a real router implementation will normally
      build an efficient MFIB from the following
   steps are taken:

   o If no (*,G) TIB state exists for the group, then a (*,G) entry to perform forwarding.
      How this is
     created done is implementation-specific, and populated with the RP DF information.

   o If the interface on which the report was received is not discussed
      in this document.

2.2.  Pseudocode Notation

We use set notation in several places in this specification.

A (+) B
    is the
     olist union of the entry, then the interface two sets A and B.

A (-) B
    is added to the olist.

   o According to standard PIM-SM procedures [1], if the olist transi-
     tioned from null to non-null, a Join message for the group is trig-
     gered upstream. The Join elements of set A that are not in set B.

NULL
    is directed to the DF for the (*,G) incom-
     ing interface.

   When empty set or list.

In addition we use C-like syntax:

=   denotes assignment of a router receives variable.

==  denotes a Join message addressed to it comparison for equality.

!=  denotes a bidir
   group G with rendezvous point RP, it must determine if it is the DF
   on the link comparison for this RP. If the router is not the DF, it must ignore
   the Join message.  If it inequality.

Braces { and } are used for grouping.

3.  Protocol Specification

The specification of BIDIR-PIM is broken into several parts:

o Section 3.1 details the DF, then protocol state stored.

o Section 3.3 specifies the following steps are
   taken: data packet forwarding rules.

o If no (*,G) state exists for Section 3.4 specifies the group, then a (*,G) entry is
     created BIDIR-PIM Join/Prune generation and populated with the RP DF information.
  processing rules.

o If the interface on which the Join was received Designated Forwarder (DF) election is not specified in the olist Section 3.5.

o PIM packet formats are specified in Section 3.7.

o A summary of the entry, then the interface BIDIR-PIM timers and their default values is added to given in
  Section 3.6.

3.1.  BIDIR-PIM Protocol State

This section specifies all the olist.

   o According protocol state that a BIDIR-PIM
implementation should maintain in order to standard PIM-SM procedures [1], function correctly.  We term
this state the expiration timer Tree Information Base or TIB, as it holds the state of
all the olist interface is updated and if multicast distribution trees at this router.  In this
specification we define PIM mechanisms in terms of the olist transitioned
     from null to non-null, TIB.  However,
only a Join message for the group is triggered
     upstream. The Join is directed very simple implementation would actually implement packet
forwarding operations in terms of this state.  Most implementations will
use this state to build a multicast forwarding table, which would then
be updated when the DF for the (*,G) incoming
     interface.

3.1.2 Leaving relevant state in the (shared) tree

   When TIB changes.

Although we specify precisely the DF for a link receives notification state to be kept, this does not mean
that an interface implementation of PIM-SM needs to hold the state in this form.
This is no
   longer required actually an abstract state definition, which is needed in order
to specify the olist of a group (either through IGMP or by
   receiving a Prune), it follows standard PIM-SM procedures except any
   originated prunes are addressed router's behavior.  A BIDIR-PIM implementation is free to
hold whatever internal state it requires, and will still be conformant
with this specification so long as it results in the DF on same externally
visible protocol behavior as an abstract router that holds the (*,G) iif.

3.1.3 Designated Forwarder Change

   When following
state.

We divide TIB state into two sections:

RP state
     State that maintains the DF election information for each RP.

Group state
     State that maintains a RP on a link changes to a different router, group-specific tree
   maintenance has to take place for groups that map to ensure a
     given RP.

The state that traffic should be kept is still
   delivered for all affected groups.

3.1.3.1 Old DF Actions

   On losing its status as acting DF on a link, the old DF has described below.  Of course,
implementations will only maintain state when it is relevant to take
   the following actions
forwarding operations - for existing groups that are affected.

   o If there were downstream receivers (discovered through IGMP or
     downstream Joins), example, the "NoInfo" state might be assumed
from the lack of other state information, rather than being held
explicitly.

3.1.1.  General Purpose State

A router has to delete holds the interface following state that is not specific to the
     link a RP or
group:

     Neighbor State:

          For each neighbor:

               o Information from its olist. neighbor's Hello

               o If Neighbor's Gen ID.

               o Neighbor liveness timer (NLT)

3.1.2.  RP State

A router maintains a multicast-group to RP mapping which is built using
the interface deletion results BSR mechanism described in section 4. For each BIDIR-PIM RP a null olist for the (*,G)
     then router
holds the usual actions are taken to propagate a Prune upstream.

3.1.3.2 New following state:

     o RP address

       Designated Forwarder (DF) State:

            For each router interface:

                 Acting DF Actions

   On assuming the role of the information:

                 o DF for a given link, IP Address
                 o DF metric

                 Election information:

                 o DF Election-Timer (DFT)

                 o Offer-Count (OC)

                   Current best offer:

                   o IP address of best offering router

                   o Best offering router metric

Designated Forwarder state is described in section 3.5.

3.1.3.  Group State

For every group G a router has to take keeps the following actions for state:

          Group state:

               For each existing group that interface:

                    Local Membership:

                    o State: One of {"NoInfo", "Include"}

               PIM Join/Prune State:

                    o State: One of {"NoInfo" (NI), "Join" (J),
                      "PrunePending" (PP)}

                    o Prune Pending Timer (PPT)

                    o Join/Prune Expiry Timer (ET)

          Not interface specific:

               o Upstream Join/Prune Timer (JT)

               o Last RP Used

Local membership is affected. If the router has IGMP information from local receivers for a group, result of the
   interface to local membership mechanism (such
as IGMP) running on that interface. This information is used by the link must be added to the olist for the (*,G). If
pim_include(*,G) macro described in section 3.1.4.

PIM Join/Prune state is the result of receiving PIM (*,G) entry did not exist then it must be created Join/Prune
messages on this interface, and populated
   with is specified in section 3.4.1. The state
is used by the RP DF information.  If macros that calculate the (*,G) olist was previously null
   then outgoing interface list in
section 3.1.4, and in the usual actions are taken to propagate JoinDesired(G) macro (defined in section
3.4.2) that is used in deciding whether a Join Join(*,G) should be sent
upstream.

3.1.3.3 Downstream Router Actions
   When learning about a switch

The upstream Join/Prune timer is used to a new DF send out periodic Join(*,G)
messages, and to override Prune(*,G) messages from peers on the RPF interface, down-
   stream routers an upstream
LAN interface.

The last RP used must take the following actions for all affected
   groups.

   o If be stored because if the router has a (*,G) entry with a non-null olist, it RP Set changes [9] then
state must send
     a Join be torn down and rebuilt for groups whose RP changes.

3.1.4.  State Summarization Macros

Using this state, we define the group towards following "macro" definitions which we
will use in the new DF.

   o The router may also send a Prune for descriptions of the group towards state machines and pseudocode in the old DF.

3.2 Forwarding Data

   The
following responsibilities are uniquely assigned to sections.

olist(G) =
    RPF_interface(RP(G)) (+) joins(G) (+) pim_include(G)

RPF_interface(RP) is the DF of a
   link:

   o interface the MRIB indicates would be used to
route packets to RP. The DF olist(G) is the only router that forwards list of interfaces on which
packets traveling down-
     stream onto to group G must be forwarded.

The macro pim_include(G) indicates the link.

   o interfaces to which traffic might
be forwarded because of hosts that are local members on that interface.

pim_include(G) =
    { all interfaces I such that:
      I_am_DF(RP(G),I) AND  local_receiver_include(G,I) }

The DF clause "I_am_DF(RP,I)" is TRUE if the only router that picks-up upstream traveling packets
     off is in the link to forward towards Win or
Backoff states in the RP.

   Non-DF routers DF election state machine in section 3.5.

The clause "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 traffic sent to group G.

The set "joins(G)" is the set of all interfaces on which the router has
received (*,G) Joins:

joins(G) =
    { all interfaces I such that
      I_am_DF(RP(G),I) AND
      DownstreamJPState(G,I) is either Joined or PrunePending }

DownstreamJPState(G,I) is the state of the finite state machine in
section 3.4.1.

RPF'(RP) is the neighbor that Join messages must be sent to in order to
reach the RP. This is the Designated-Forwarder on the RPF_interface(RP).

3.2.  PIM Neighbor Discovery

PIM routers exchange PIM Hello messages with their neighboring PIM
routers. These messages are used to update the Neighbor State described
in section 3.1. The procedures for generating and processing received
Hello messages as well as maintaining Neighbor State are specified in
the PIM-SM [9] documentation.

3.3.  Data Packet Forwarding Rules

For groups mapping to a given RP, the following responsibilities are
uniquely assigned to the DF for that RP on each link:

o The DF is the only router that forwards packets traveling downstream
  onto the link.

o The DF is the only router that picks-up upstream traveling packets off
  the link to forward towards the RP.

Non-DF routers on a link, that use that link as their RPF interface to
reach the RP, may perform the following forwarding actions for
bidirectional groups:

o Forward packets from the link towards downstream receivers.

o Forward packets from downstream sources onto the link (provided they
  are the DF for the downstream link from which the packet was
     picked-up).

   When a router receives a multicast picked-
  up).

The BIDIR-PIM packet sent to a bidir group G, it
   first looks for a (*,G) matching entry. If this forwarding rules are defined below in pseudocode.

     iif is not found, then
   the matching (*,*,RP) state may be used. Alternatively (*,G) state
   may be created with a null olist and populated with the RP DF infor-
   mation.

   The router must forward incoming interface of the packet if either:

   o It was received on packet.
     G is the RPF interface destination address of the entry (always forward
     downstream traveling packets)

   o The router packet (group address).
     RP is the Designated Forwarder (DF) address of the Rendezvous Point for this group.

First we check to see whether the RP packet should be accepted based on TIB
state and the interface that the packet was received (only arrived on. A packet is accepted
if it arrives on the RPF_interface to reach the RP (downstream traveling
packet) or if the router is the DF forwards upstream). on the interface the packet arrives
(upstream traveling packet).

If a decision to forward the packet is made, then it is should be forwarded on
   all we build an outgoing interface list
for the interfaces in packet.

Finally we remove the olist including incoming interface from the entry's RPF outgoing interface
   but excluding
list we've created, and if the resulting outgoing interface list is not
empty, we forward the packet was received on. Otherwise the out of those interfaces.

On receipt on a data to G on interface iif:

 if( iif == RPF_interface(RP) || I_am_DF(RP,I) ) {
    oiflist = olist(G)
    oiflist = oiflist (-) iif
    forward packet is discarded. on all interfaces in oiflist
 }

Note: A major advantage of using a Designated Forwarder in bi-
   directional PIM 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 directly-connected-source check for data to groups that do
not have existing state.

3.2.1 Source-only

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 do not only have an the RPF_interface to the RP in their
olist for the group G and hence do not need to maintain (*,G) any group specific state.
Upstream forwarding can be performed using (*,*,RP) RP state.  An implementation
may decide to maintain (*,G) group state for source-only branches for
accounting or performance reasons.

4 Designated Forwarder

   This section presents

3.4.  PIM Join/Prune Messages

A BIDIR-PIM Join/Prune message consists of a fail-safe mechanism for electing list of Joined and Pruned
Groups. When processing a per-RP
   designated router on received Join/Prune message, each link in Joined or
Pruned Group is effectively considered individually by applying the

following state machines.  When considering a Join/Prune message whose
PIM domain. We call Destination field addresses this router router, (*,G) Joins and Prunes can
affect the Designated Forwarder (DF).

4.1 DF Requirements

   The DF election chooses downstream state machine.  When considering a Join/Prune
message whose PIM Destination field addresses another router, most Join
or Prune entries could affect the best upstream state machine.

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

When a router on receives a link Join(*,G) or Prune(*,G) it must first check to assume
see whether the
   responsibility RP in the message matches RP(G) (the router's idea of forwarding traffic between
who the RP and is). If the link for RP in 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 message does not have to match RP(G) the Join
or Prune MUST be silently dropped. In addition a group specific decision but instead
   can be RP-specific. As the number of RPs is typically small, the
   number of elections that have router MUST NOT process
Join(*,G) messages targeted to be performed is significantly
   reduced by this observation.

   To optimise tree creation, itself if it is desirable that the winner of the
   election process should be not the router DF for RP(G) on
the link with interface the "best"
   unicast routing metric 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 the RP. When comparing metrics
          forward packets destined for G from dif-
   ferent unicast routing protocols, we use the same comparison rules
   used in the PIM assert process [1]. this interface.

     PrunePending (PP)
          The election process needs to take place when information router has received a Prune(*,G) on this interface from a new RP
   initially becomes available,
          downstream neighbor and can is waiting to see whether the prune
          will be re-used as new bidir groups
   for overridden by another downstream router.  For
          forwarding purposes, the same RP are encountered. There are however some conditions
   where an update to PrunePending state functions exactly
          like the election is required:

   o There Join state.

In addition the state-machine uses two timers:

     ExpiryTimer (ET)
          This timer is restarted when a change in unicast metric to reach the RP for any valid Join(*,G) is received.
          Expiry of the
     routers on ExpiryTimer causes the link.

   o The interface on which the RP is reachable changes state to an interface revert
          to NoInfo for which this group.

     PrunePendingTimer (PPT)
          This timer is set when a valid Prune(*,G) is received.  Expiry
          of the router was previously PrunePendingTimer causes the DF.

   o A new PIM neighbor starts up on a link.

   o The elected interface state to revert
          to NoInfo for this group.

                    +-----------------------------------+
                    | 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 dies. 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 election process has to be robust enough transition events "Receive Join(*,G)" and "Receive Prune(*,G)" imply
receiving a Join or Prune targeted to ensure with very high
   probability that all routers this router's address on the link have a consistent view of
received interface.  If the DF. This destination address is because with the forwarding rules described not correct, these
state transitions in sec-
   tion 3.2, if multiple routers end-up thinking that they 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
   responsible for forwarding, loops may result. To reduce the possibil-
   ity of this occurrence to a minimum, same as the election algorithm has been
   biased towards discarding DF information and suspending forwarding
   during periods of ambiguity.

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

The transition event "Stop being DF" implies a DF Election Description

   To perform re-election taking
place on this router interface and the election of router changing status from being
the active DF for a particular RP, routers on to being a
   link need non-DF router (the value of the I_am_DF macro
changing to FALSE).

When ExpiryTimer is started or restarted, it is set to exchange their unicast routing metric information for
   reaching the RP.

   In HoldTime from
the election protocol described below, many message exchanges are
   repeated 3 times for reliability. In all those cases 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
   retransmissions are spaced in time sent by the upstream router to itself on a small random interval.

   For
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 purposes of LAN, then the election, interface specific counters PruneEcho may be received and
   timers need cause the override to
happen.  A PruneEcho(*,G) need not be maintained for each 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. When (*,G) entries  Such
Join(*,G) messages are
   created, they inherit information sent on the elected DF from RPF_interface towards the
   corresponding RP database entry. Subsequent changes in the winner of and are
targeted at the DF election for on that interface.

If a RP are propagated router wishes to all dependent (*,G)
   entries.

4.2.1 Bootstrap Election

   Initially when no DF has been elected, routers finding out about propagate a
   new RP start participating in the election by sending Offer messages.
   Offer Join(*,G) upstream, it must also watch
for messages include the router's metric to reach the RP. Offers
   are periodically retransmitted with a period randomly chosen in the
   interval [0.5 * Offer-Interval, Offer-Interval].

   If a router hears a better offer on it's 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 stops
   participating in the election for a period of [3 * Offer-Interval]. should suppress its own Join(*,G).  If during this period no winner is elected, then
it restarts the
   election from the beginning.  If sees a router receives an offer with
   worse metrics, then it restarts the election from Prune(*,G) to the beginning.

   The result correct upstream neighbor, it should be
prepared to override that all routers except the best candidate stop
   advertising.

   A router assumes prune by sending a Join(*,G) almost
immediately.  Finally, if it sees the role Generation ID (see PIM-SM
specification [9]) of the DF after having advertised its
   metrics 3 times without receiving any offer from any other neighbor.
   At that point correct upstream neighbor change, it transmits a Winner message which declares to every
   other router on the link the identity of knows
that the winner upstream neighbor has lost state, and the metrics it is using.

   Routers hearing should be prepared to
refresh the state by sending a winner message stop participating Join(*,G) almost immediately.

In addition changes in the election
   and record the identity and metrics of next hop towards the winner. If RP trigger a prune off
from the local
   metrics are better than those of old next hop, and join towards the winner then new next hop. Such a change
can be cause by the router records following two reasons:

     o The MRIB indicates that the identity of RPF_interface towards the winner but reinitiates the election.

4.2.2 Loser Metric Changes

   Whenever the unicast metric to a RP changes for has
       changed.

     o There is a non-DF router to DF re-election on the RPF_interface and a
   value that is better than that previously advertised by new router
       emerges as the DF, DF.

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

Not Joined
     The downstream state-machines indicate that the router with the new metric should take action does not
     need to eventually assume
   forwarding responsibility. After join the metric change is detected, the
   new candidate restarts participating in the election. If no response
   is received after 3 retransmissions, RP tree for this group.

Joined
     The downstream state-machines indicate that 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, would like
     to join the
   DF will respond with a Winner message declaring its status and
   advertising its metric. Upon receiving RP tree for this message, the originator
   of the Offer records the identity of the DF and aborts the election.

   Upon receipt of an offer that group.

In addition, one timer JT(G) is better the its current metric, the
   DF records kept which is used to trigger the identity and metrics
sending of the offering router and
   responds with a Backoff message. This instructs the offering router Join(*,G) to hold off for a short period of time while the unicast routing sta-
   bilises. The Backoff message includes upstream next hop towards the offering router's new
   metric and address.  All routers RP (the DF
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 RPF_interface for a period of
   time defined in the Backoff message.

   If during RP(G)).

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

                   Figure 2: Upstream group state-machine

In tabular form, the backoff period, a third router sends a new better
   offer, 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 Backoff message is repeated for following transitions which occur within the
Joined state:

+-----------------------------------------------------------------------+
|                         In Joined (J) State                           |
+-----------------+-----------------+-----------------+-----------------+
|Timer Expires    | See Join(*,G)   | See Prune(*,G)  | RPF'(*,G)       |
|                 | to RPF'(*,G)    | to RPF'(*,G)    | changes         |
+-----------------+-----------------+-----------------+-----------------+
|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                           |
+-------------------------------------+---------------------------------+
|      topology change wrt            |         RPF'(RP(G)) GenID       |
|      RPF'(RP(G))                    |         changes                 |
+-------------------------------------+---------------------------------+
|      Send Join(*,G) to new offer and the
   backoff period restarted.

   Before          |         Decrease Timer to       |
|      next hop; Send                 |         t_override              |
|      Prune(*,G) to old next         |                                 |
|      hop; set Timer to              |                                 |
|      t_periodic                     |                                 |
+-------------------------------------+---------------------------------+

This state machine uses the backoff period expires, 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 acting Designated Forwarder (DF).

3.5.1.  DF nominates the router
   having made Requirements

The DF election chooses the best offer as the new DF using router on a Pass message. This
   message includes link to assume the IDs and metrics
responsibility of both forwarding traffic between the old RP and new DFs.
   The old DF stops performing its tasks as soon as the transmission is
   made.  The new DF assumes link for the role
range of multicast groups served by the DF as soon as it receives RP.  Different multicast groups
that share a common RP must use the Pass message. All other routers on same bi-directional tree for data
forwarding. Hence, the link take note election of the new
   DF and its metric.

4.2.3 Winner Metric Changes

   If the DF's routing metric an upstream forwarder on each link
does not have to reach be a group specific decision but instead can be RP-
specific. As the RP changes number of RPs is typically small, the number of
elections that have to a worse value, be performed is significantly reduced by this
observation.

To optimise tree creation, it sends a set is desirable that the winner of 3 randomly spaced Offer messages the
election process should be the router on the link,
   advertising link with the new metric. Routers who receive this announcement but
   have a better "best"
unicast routing metric may respond with an Offer message which results
   in to the RP (as reported by the MRIB). When
comparing metrics from different unicast routing protocols, we use the
same handoff procedure described above.  All routers assume comparison rules used by the DF has not changed until they see PIM-SM assert process [9].

The election process needs to take place when information on a Pass or Winner message indi-
   cating new RP
initially becomes available, and can be re-used as new bidir groups for
the change. same RP are encountered. There is no pressure are however some conditions where an
update to make this handoff quickly if the acting DF
   still has election is required:

     o There is a path change in unicast metric to reach the RP. The old path may now be suboptimal but it
   will still work while RP for any of
       the re-election is in progress.

   If routers on the routing metric at link.

     o The interface on which the DF RP is reachable changes to a better value, a single
   Winner message is sent advertising an
       interface for which the router was previously the DF.

     o A new metric.

4.2.4 Winner Loses Path

   If PIM neighbor starts up on a router's path to the RP switches link.

     o The elected DF dies.

The election process has to be through a robust enough to ensure with very high
probability that all routers on the link for which
   it have a consistent view of the
DF. This is acting as because with the DF, then it can no longer provide forwarding ser-
   vices for rules described in section 3.3
if multiple routers end-up thinking that link. It therefore immediately stops being 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
   restarts suspending forwarding during periods of
ambiguity.

3.5.2.  DF Election description

This section does not provide the election. As its path to definitive specification for the RP is through DF
election process. If any discrepancy exists between section 3.5.3 and
this section, the link, an
   infinite metric is used specification in section 3.5.3 is to be assumed
correct.

To perform the Offer message it sends.

   Note: At this stage election of the old DF will have for a new RPF neighbor particular RP, routers on the
   link (indicated by unicast routing) which it could use in a Pass mes-
   sage but this adds unnecessary complication link
need to exchange their unicast routing metric information (as reported
by the election process.

4.2.5 Late Router Starting Up

   A late router starting up will have no knowledge of a previous elec-
   tion outcome. As a result it will start advertising its metric in
   Offer messages. As soon as this happens, MRIB) for reaching the Winner will respond
   either with a Winner or with a Backoff message.

4.2.6 Winner Dies

   Whenever RP.

In the DF dies, a new DF has to be elected. The speed at which
   this can be achieved depends on whether there election protocol described below, many message exchanges are any downstream
   routers on
repeated Election_Robustness times for reliability. In all those cases
the link.

   If there message retransmissions are downstream routers, typically their RPF neighbor
   reported spaced in time by unicast routing will be the DF. They will therefore
   notice a change in RPF neighbor away from the small random
interval.

3.5.2.1.  Bootstrap Election

Initially when no DF and will restart has been elected, routers finding out about a new
RP start participating in the election by transmitting sending Offer messages.  If the RP is now reachable
   through  Offer
messages include the link via another upstream router, an infinite router's metric will
   be used in to reach the Offer.

   If no downstream routers RP. Offers are present,
periodically retransmitted with a period of Offer_Interval.

If a router hears a better offer from a neighbor, it stops participating
in the only way election for other upstream
   routers to detect a DF failure is by the timeout period of Election_Robustness * Offer_Interval. If
during this period no winner is elected, then the PIM neighbor
   information, which will take significantly longer.

4.3 Election Protocol Specification

4.3.1 Protocol State

   The operation of router restarts the
election protocol makes use of from the variables and
   timers described below. These are maintained per RP for each multi-
   cast enabled interface on beginning. If a router receives an offer with worse
metrics, then it restarts the router.

        Offer-Count (O-count)
            Used to maintain election from the number beginning.

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

A router assumes the role of times an Offer or Winner mes-
            sage has been transmitted.

        Best-Offer
            Used by the DF after having advertised its metrics
Election_Robustness times without receiving any offer from any other
neighbor. At that point it transmits a Winner message which declares to record who has made

every other router on the last offer for
            sending link the Pass message.

        Offer-Timer (O-timer)
            Used to schedule transmission identity of Offer the winner and Winner messages.

        Pass-Timer (P-timer)
            Used on the DF to schedule transmission of
metrics it is using.

Routers hearing a Pass message.

4.3.2 Message Summary

   The winner message stop participating in the election uses and
record the following control messages:

        Offer (OfferingID, Metric)
            Sent by routers that believe they have a 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
            the a RP changes for a non-DF router to a
value that is better than the metric that has been on offer so far.

        Winner (DF-ID, DF-Metric)
            Sent previously advertised by a the acting DF,
the router when assuming with the new metric should take action to eventually assume
forwarding responsibility. After the metric change is detected, the new
candidate restarts participating in the election. If no response is
received after Election_Robustness retransmissions, the router assumes
the role of the DF or when
            re-asserting in response to worse offers.

        Backoff (DF-ID, DF-Metric, OfferingID, OfferMetric,
                 BackoffInterval)
            Used by following the DF to acknowledge better offers. It instructs
            other routers with equal or usual Winner announcement procedure.

Upon receipt of an offer that is worse offers to wait till than its current metric, the DF
            passes responsibility to
will respond with a Winner message declaring its status and advertising
its metric. Upon receiving this message, the sender originator of the offer.

        Pass (Old-DF-ID, Old-DF-Metric, New-DF-ID, New-DF-Metric)
            Used by Offer
records the identity of the old DF to pass forwarding responsibility to a
            router that has previously made and aborts the election.

Upon receipt of an offer.  The Old-DF-Metric offer that is better the its current metric of metric, the DF at
records the time identity and metrics of the pass is
            sent.

4.3.3 Protocol Events

   During protocol operation, in addition to offering router and responds
with a Backoff message. This instructs the expiration offering router to hold off
for a short period of time while the two
   timers unicast routing stabilises. The
Backoff message includes the offering router's new metric and reception of address.
All routers on the four messages, link who have pending offers with metrics worse than
those in the following events can
   take place:

   o Discovery 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 RP

   o Metric change

   o DF loses path

   o Detection of DF failure (unicast routing changed better offer,
the Backoff message is repeated for downstream or
     Hello expired)

4.3.4 Protocol Operation

   In the two tables below new offer and the following rules 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.

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 Offer 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 will have no knowledge of a previous election
outcome. As a result it will start advertising its metric in Offer
messages. As soon as this happens, the Winner will respond either with a
Winner or with a Backoff 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.

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 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 operation of the election protocol makes use of the variables and
timers described below. These are maintained per RP for each multicast
enabled interface on the router as introduced in section 3.1:

     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:

     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 State Transitions

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

When an action of "set DF to Sender or Dest" 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 it's metrics.

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

     o On receipt of a Backoff message set the DF to be the originator
       of the message and record it's metrics.

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

            Figure 3: Designated Forwarder election state-machine

In tabular form, the state machine is:

+-------------++--------------------------------------------------------+
|             ||                         Event                          |
| Prev State  ++------------------+------------------+------------------+
|             || Recv better      |  Recv better     |  Recv better     |
|             || Pass / Win       |  Backoff         |  Offer           |
+-------------++------------------+------------------+------------------+
|             || -> Lose          |  -               |  -               |
|             || DF = Sender      |  Set Timer to    |  Set Timer to    |
| Offer       ||                  |  Robustness *    |  Robustness *    |
|             ||                  |  offer_int; Set  |  offer_int; Set  |
|             ||                  |  Count to 0      |  Count to 0      |
+-------------++------------------+------------------+------------------+
|             || -                |  -               |  -> Offer        |
|             || DF = Sender or   |  DF = Sender or  |  Set Timer to    |
| Lose        || Dest             |  Dest            |  Robustness *    |
|             ||                  |                  |  offer_int; Set  |
|             ||                  |                  |  Count to 0      |
+-------------++------------------+------------------+------------------+
|             || -> Lose          |  -> Lose         |  -> Backoff      |
|             || DF = Sender or   |  DF = Sender or  |  Set Best to     |
| Win         || Dest; Stop       |  Dest; Stop      |  Sender; Send    |
|             || Timer            |  Timer           |  Backoff; Set    |
|             ||                  |                  |  Timer to        |
|             ||                  |                  |  backoff_int     |
+-------------++------------------+------------------+------------------+
|             || -> Lose          |  -> Lose         |  -               |
|             || DF = Sender or   |  DF = Sender or  |  Set Best to     |
| Backoff     || Dest             |  Dest            |  Sender; Send    |
|             ||                  |                  |  Backoff; Set    |
|             ||                  |                  |  Timer to        |
|             ||                  |                  |  backoff_int     |
+-------------++------------------+------------------+------------------+

+-----------++----------------------------------------------------------+
|           ||                          Event                           |
|           ++-------------+--------------+--------------+--------------+
|Prev State ||Recv Backoff | Recv Pass    | Recv Worse   | Recv worse   |
|           ||for us       | for us       | Pass / Win / | Offer        |
|           ||             |              | Backoff      |              |
+-----------++-------------+--------------+--------------+--------------+
|           ||-            | -> Win       | -            | -            |
|           ||Set Timer to | Stop Timer   | Set DF to    | Set/Lower    |
|           ||Hi; Set      |              | Sender or    | Timer to     |
|Offer      ||Count to 0   |              | Dest;        | Low; Set     |
|           ||             |              | Set/Lower    | Count to 0   |
|           ||             |              | Timer to     |              |
|           ||             |              | Low; Set     |              |
|           ||             |              | Count to 0   |              |
+-----------++-------------+--------------+--------------+--------------+
|           ||-> Offer     | -> Offer     | -> Offer     | -> Offer     |
|           ||DF = Sender  | DF = Sender  | DF = Sender  | Set Timer to |
|           ||or Dest; Set | or Dest; Set | or Dest; Set | offer_int;   |
|Lose       ||Timer to     | Timer to     | Timer to     | Set Count to |
|           ||offer_int;   | offer_int;   | offer_int;   | 0            |
|           ||Set Count to | Set Count to | Set Count to |              |
|           ||0            | 0            | 0            |              |
+-----------++-------------+--------------+--------------+--------------+
|           ||-> Offer     | -> Offer     | -> Offer     | -            |
|           ||DF = Sender  | DF = Sender  | DF = Sender  | Send Winner  |
|           ||or Dest; Set | or Dest; Set | or Dest; Set |              |
|Win        ||Timer to     | Timer to     | Timer to     |              |
|           ||offer_int;   | offer_int;   | offer_int;   |              |
|           ||Set Count to | Set Count to | Set Count to |              |
|           ||0            | 0            | 0            |              |
+-----------++-------------+--------------+--------------+--------------+
|           ||-> Offer     | -> Offer     | -> Offer     | -> Win       |
|           ||DF = Sender  | DF = Sender  | DF = Sender  | Send Winner; |
|           ||or Dest; Set | or Dest; Set | or Dest; Set | Stop Timer   |
|Backoff    ||Timer to     | Timer to     | Timer to     |              |
|           ||offer_int;   | offer_int;   | offer_int;   |              |
|           ||Set Count to | Set Count to | Set Count to |              |
|           ||0            | 0            | 0            |              |
+-----------++-------------+--------------+--------------+--------------+

+-----------------------------------------------------------------------+
|                           In Offer State                              |
+-----------------------+------------------------+----------------------+
| Timer Expires and     |   Timer Expires and    |  Timer Expires and   |
| Count is less than    |   Count is equal to    |  Count is equal to   |
| Robustness            |   Robustness and we    |  Robustness and      |
|                       |   have path to RP      |  there is no path    |
|                       |                        |  to RP               |
+-----------------------+------------------------+----------------------+
| -                     |   -> Win               |  -> Lose             |
| Send Offer; Set       |   Send Winner          |  Set DF to None      |
| Timer to              |                        |                      |
| offer_int;            |                        |                      |
| Increase Count by     |                        |                      |
| 1                     |                        |                      |
+-----------------------+------------------------+----------------------+

+-----------------------------------------------------------------------+
|                            In Lose State                              |
+-----------------------------------+-----------------------------------+
|    Detect DF Failure              |       Metric changes and now      |
|                                   |       is better than DF           |
+-----------------------------------+-----------------------------------+
|    -> Offer                       |       -> Offer                    |
|    DF = None; Set timer to        |       Set timer to offer_int;     |
|    offer_int; Set Count to        |       Set Count to 0              |
|    0                              |                                   |
+-----------------------------------+-----------------------------------+

+-----------------------------------------------------------------------+
|                             In Win State                              |
+------------------------+------------------------+---------------------+
|  Metric changes and    |  Timer Expires and     |   No path to RP     |
|  is now worse          |  Count is less than    |                     |
|                        |  Robustness            |                     |
+------------------------+------------------------+---------------------+
|  -                     |  -                     |   -> Offer          |
|  Set Timer to          |  Send Winner; Set      |   Set DF to None;   |
|  offer_int; Set        |  Timer to              |   Set Timer to      |
|  Count to 0            |  offer_int;            |   offer_int; Set    |
|                        |  Increment Count by    |   Count to 0        |
|                        |  1                     |                     |
+------------------------+------------------------+---------------------+

+-----------------------------------------------------------------------+
|                           In Backoff State                            |
+-----------------------------------+-----------------------------------+
|     Metric changes and is         |         Timer Expires             |
|     now better than Best          |                                   |
+-----------------------------------+-----------------------------------+
|     -> Win                        |         -> Lose                   |
|     Stop Timer                    |         Send Pass; Set DF to      |
|                                   |         stored Best               |
+-----------------------------------+-----------------------------------+

3.6.  Timers and notation apply:

   o Whenever Constants

BIDIR-PIM maintains the notation "?=" is used following timers, as discussed in section 3.1.
All timers are countdown timers - they are set to assign a value and count down
to a timer,
     the value is assigned only if the timer is not running or zero, at which point they typically trigger an action.  Of course
they can just as easily be implemented as count-up timers, where the
absolute expiry time
     left running is longer than the new value.

   o When a new DF is discovered through the receipt of a Winner or Pass
     message, if it is not already a PIM neighbor, stored and compared against a neighbor entry is
     created with the default expiration interval.

   o Whenever real-time clock,
but the language in this specification assumes that they count downwards
to zero.

Per Rendezvous-Point (RP):

     Per interface (I):

          DF is set, the associated metrics Election Timer: DFT(RP,I)

Per Group (G):

     Upstream Join Timer: JT(G)

     Per interface (I):

          Join Expiry Timer: ET(G,I)

          PrunePending Timer: PPT(G,I)

When timers are also recorded.

   o Timers in square brackets started or restarted, they are randomly chosen set to default values.
This section summarizes those default values.

Timer Name: DF Election Timer (DFT)

+--------------------+-------------------------+------------------------+
|  Value Name        |  Value                  |   Explanation          |
+--------------------+-------------------------+------------------------+
|  Offer_Period      |  100 ms                 |   Interval to wait     |
|                    |                         |   between 0.5 repeated     |
|                    |                         |   Offer and Winner     |
|                    |                         |   messages.            |
+--------------------+-------------------------+------------------------+
|  Backoff_Period    |  1
     times sec                  |   Period that acting   |
|                    |                         |   DF waits between     |
|                    |                         |   receiving a better   |
|                    |                         |   Offer and sending    |
|                    |                         |   the Pass message     |
|                    |                         |   to transfer DF       |
|                    |                         |   responsibility.      |
+--------------------+-------------------------+------------------------+
|  OPLow             |  rand(0.5, 1) *         |   Range of actual      |
|                    |  Offer_Period           |   randomised value     |
|                    |                         |   used between         |
|                    |                         |   repeated messages.   |
+--------------------+-------------------------+------------------------+
|  OPHigh            |  Election_Robustness    |   Interval to wait     |
|                    |  * Offer_Period         |   in order to give a   |
|                    |                         |   chance to a router   |
|                    |                         |   with a better        |
|                    |                         |   Offer to become      |
|                    |                         |   the supplied value.

   o When a router has DF.              |
+--------------------+-------------------------+------------------------+

Timer Names: Join Expiry Timer (ET(G,I))

+----------------+----------------+-------------------------------------+
| Value Name     | Value          |  Explanation                        |
+----------------+----------------+-------------------------------------+
| J/P HoldTime   | from message   |  Hold Time from Join/Prune Message  |
+----------------+----------------+-------------------------------------+

Timer Names: Prune Pending Timer (PPT(G,I))

+--------------------------+--------------------+-----------------------+
| Value Name               |  Value             |   Explanation         |
+--------------------------+--------------------+-----------------------+
| J/P Override Interval    |  Default: 3 secs   |   Short period after  |
|                          |                    |   a path join or prune to the RP through the link  |
|                          |                    |   allow other         |
|                          |                    |   routers on which the
     election is taking place, an infinite metric is used in Offer mes-
     sages.

   Event    Condition       Non-DF action           DF action
   =======================================================================
   Offer   |Local metric   |O-count = 0            |Send Backoff
   rcvd    |worse          |O-timer = [Offer-Int]  |Best-Offer = sender LAN  |
|       + 3 * Offer-Int |P-timer = Backoff-Int                          |                    |                       |Stop O-timer
           |--------------------------------------------------------------
           |Local metric   |O-count = 0            |Send Winner
           |better         |O-timer ?= [Offer-Int] |Stop P-timer
   -----------------------------------------------------------------------
   Winner  |Local metric   |O-count = 0
   rcvd    |worse          |Stop O-timer   to override the     |               |DF = sender
|               |Stop P-timer
           |--------------------------------------------------------------
           |Local metric   |O-count = 0
           |better         |O-timer ?= [Offer-Int]                          |               |DF = sender                    |               |Stop P-timer
   -----------------------------------------------------------------------
   Backoff |Local metric   |O-count = 0
   rcvd    |worse   join or prune       |
+--------------------------+--------------------+-----------------------+

Timer Names: Upstream Join Timer (JT(G))

+-------------+--------------------+------------------------------------+
|Value Name   |Value               |Explanation                         |
+-------------+--------------------+------------------------------------+
|t_periodic   |Default: 60 secs    |Period between Join/Prune Messages  |
+-------------+--------------------+------------------------------------+
|t_suppressed |rand(1.1 *          |Suppression period when someone     |
|             |t_periodic, 1.4 *   |else sends a J/P message so we      |
|             |t_periodic)         |don't need to us |O-timer = Backoff-Int + [Offer-Int] do so.                |               |DF = sender
+-------------+--------------------+------------------------------------+
|t_override   |rand(0, 0.9 * J/P   |Randomized delay to prevent         |               |Stop P-timer
           |--------------------------------------------------------------
           |Local metric   |O-count = 0
           |better         |O-timer ?= [Offer-Int]
|               |DF = sender             |Override Interval)  |response implosion when sending a   |               |Stop P-timer
   -----------------------------------------------------------------------
   Pass    |Local metric   |O-count = 0
   rcvd    |worse or
|             |                    |join message to us |Stop O-timer override someone    |               |DF = destination
|               |Stop P-timer
           |--------------------------------------------------------------
           |Local metric   |O-count = 0
           |better         |0-timer ?= [Offer-Int]             |               |DF = destination                    |else's prune message.               |               |Stop P-timer
   -----------------------------------------------------------------------
   Event    Condition       Non-DF action
+-------------+--------------------+------------------------------------+

For more information about these values refer to the PIM-SM [9]
documentation.

Constant Name: DF action
   =======================================================================
   New RP Election Robustness

+--------------------------+-------------------+------------------------+
|               |O-count = 0            |N/A  Constant Name           |               |O-timer ?= [Offer-Int]    Value          |
   -----------------------------------------------------------------------
   Metric  |DF metric      |nop                    |O-count = 0
   change  |better (*)    Explanation         |                       |O-timer ?= [Offer-Int]
+--------------------------+-------------------+------------------------+
|  Election_Robustness     |                       |Stop P-timer
           |--------------------------------------------------------------
           |DF metric      |O-count = 0            |Send Winner
           |worse (*)      |O-timer ?= [Offer-Int] |Stop P-timer
   -----------------------------------------------------------------------
   No path    Default: 3     |               |nop                    |Send Offer (**)
   to RP    Minimum number of   |
|                       |O-count = 1                          |                   |                       |O-timer ?= [Offer-Int]    election messages   |
|                       |DF = unknown                          |                   |                       |Stop P-timer
   -----------------------------------------------------------------------
   DF    that must be lost   |               |O-count = 0            |N/A
   failure
|               |O-timer ?= [Offer-Int] |
   -----------------------------------------------------------------------
   O-timer |O-count <= 3   |Send Offer
   expires                          |               |O-count++                   |               |O-timer ?= [Offer-Int]
           |---------------|----------------------------------------------
           |else           |O-count = 0    in order for        |               |Send Winner (***)
|               |DF = us
   -----------------------------------------------------------------------
   P-timer                          |               |DF = Best-Offer
   expires                   |               |Send Pass
   -----------------------------------------------------------------------

   (*) These comparisons are made against the previously stored    election to fail.   |
+--------------------------+-------------------+------------------------+

3.7.  PIM DF
   metrics.  In Election Packet Formats

This section describes the case details of the DF, packet formats for BIDIR-PIM
control messages. BIDIR-PIM shares a number of control messages in
common with PIM-SM [9] well as the old local metrics are used to
   compare against. So "DF metric better" means that format for the metric has
   actually become worse.

   (**) As Encoded-Unicast
address. For details on the path format of these packets please refer to the RP is now through
PIM-SM documentation.  Here we will only define the link an infinite metric
   is additional packets
that are introduced by BIDIR-PIM. These are the packets used in the offer.

   (***) We only become the DF and send a Winner message if we have a
   path to the RP (which is not through the link with the ongoing elec-
   tion).

4.4 Election Message Formats

   All
election process.

All PIM control messages have IP protocol number 103.

BIDIR-PIM messages are sent multicast with a TTL of 1 and are multicast to the ALL-PIM-ROUTERS group. The structure of Encoded-Unicast addresses
   is described in [1].

4.4.1 Common Header

   The header below is common to all `ALL-PIM-ROUTERS'
group `224.0.0.13'.

All DF election messages. BIDIR-PIM control messages share the common header
below:

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type  |Subtype| Rsvd  |           Checksum            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                  Encoded-Unicast-RP-Address                   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                   Sender Metric Preference                    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Sender Metric                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

PIM Ver
     PIM Version number is 2.

Type
            TBD

        Subtype
            Used to distinguish between different election All DF-Election PIM control messages and
            is set according to share the table below:

                    Message PIM message Type of
     X.

Subtype
                    -----------------------
                    Offer
     Subtypes for DF election messages are:

               1
                    Winner = Offer
               2
                    Backoff = Winner
               3
                    Pass = Backoff
               4 = Pass

Rsvd Set to zero by senders and ignored by receivers. on transmission.  Ignored upon receipt.

Checksum
            Calculated as specified in [1].
     The checksum is standard IP checksum, i.e.  the 16-bit one's
     complement of the one's complement sum of the entire PIM message.
     For computing the checksum, the checksum field is zeroed.

RP-Address
     The address of the bidir RP for which the election is taking
            place. place
     (note that the length of this field is more than 32 bits).

Sender Metric Preference
     Preference value assigned to the unicast routing protocol that the
     message sender used to obtain the route to the RP-
            address. RP-address.

Sender Metric
     The unicast routing table metric used by the message sender to
     reach the RP. The metric is in units applicable to the unicast
     routing protocol used.

   The

In addition to the fields defined above the Backoff and Pass messages
have the additional extra fields described below.

4.4.2

3.7.1.  Backoff Message

The Backoff message uses the following fields in addition to the com-
   mon ones common
election message format described above.

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|               Encoded-Unicast-Offering-Address                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                  Offering Metric Preference                   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Offering Metric                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|            Interval           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Offering Address
     The address of the router that made the last (best) Offer. Offer (note
     that the length of this field is more than 32 bits).

Offering Metric Preference
     Preference value assigned to the unicast routing protocol that the
     offering router used to obtain the route to RP-
            address. RP-address.

Offering Metric
     The unicast routing table metric used by the offering router to
     reach the RP. The metric is in units applicable to the unicast
     routing protocol used.

Interval
     The backoff interval in milliseconds to be used by routers with
     worse metrics than the offering router.

4.4.3

3.7.2.  Pass Message

The Pass message uses the following fields in addition to the common
   ones
election fields described above.

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|              Encoded-Unicast-New-Winner-Address               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                 New Winner Metric Preference                  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      New Winner Metric                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

New Winner Address
     The address of the router that made the last (best) Offer. Offer (note
     that the length of this field is more than 32 bits).

New Winner Metric Preference
     Preference value assigned to the unicast routing protocol that the
     offering router used to obtain the route to RP-
            address. RP-address.

New Winner Metric
     The unicast routing table metric used by the offering router to
     reach the RP. The metric is in units applicable to the unicast
     routing protocol used.

4.5 Timer Values

   The Offer-Interval is 100 ms.

   The default Backoff-Interval used in Backoff messages is 1 sec.

5 Advertising Bi-directional Groups

4.  RP Discovery

Routers discover that a range of multicast group addresses operates in
bi-directional mode from and the address of the Rendezvous-Point serving the group
range through the PIM Bootsrtap mechanism. For a description of the PIM
BSR RP-distribution protocol refer to PIM-SM [9].

By default the BSR protocol advertises RPs that operate the PIM-SM
protocol. In order to identify a RP as operating in BIDIR mode, the

Encoded-Group Address fields field in PIM Bootstrap and Candidate-RP Advertisement messages. The Encoded-Group Address field is modified
   to include
messages has been extended by adding the Bidir-bit (B bit) BIDIR bit (B-bit) as specified
below:

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Addr Family   | Encoding Type |B|   Reserved  |  Mask Len     |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                   Group Multicast Address                     |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   When the Bidir-bit is set, all upgraded bi-directional PIM routers
   will follow the forwarding rules described in this specification.

6 Security Considerations

   All PIM control messages MAY use IPsec to address security concerns.

7 References

   [1] Estrin, et al., "Protocol Independent Multicast-Sparse Mode (PIM-
       SM): Protocol Specification", RFC 2362, June 1998.

   [2] D. Estrin, D. Farinacci, "Bi-directional Shared Trees in PIM-SM",
       Work In Progress, <draft-farinacci-bidir-pim-01.txt>, May 1999.

   [3] Wei, L., Farinacci, D., "PIM Version 2 DR Election Priority Option",
       INTERNET-DRAFT, March 1998.

8 Acknowledgments

   The bidir proposal in this draft is heavily based on the ideas and
   text presented by Estrin and Farinacci in [2]. The main difference
   between  |  Mask Len     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                   Group Multicast Address                     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

B-bit
     When the two proposals Bidir-bit is in set, all BIDIR capable PIM routers will
     operate the method chosen protocol described in this document for upstream for-
   warding.

   We would also like the specified
     group range.

5.  Security Considerations

All PIM control messages MAY use IPsec [6] to thank Deborah Estrin at ISI/USC as well address security concerns.
The authentication methods are addressed in a companion document [7].
Keys may be distributed as
   Nidhi Bhaskar, Yiqun Cai, Tony Speakman and Rajitha Sumanasakera at
   cisco for their contributions and comments to this draft.

9 Author Information

   Mark Handley
   mjh@aciri.org
   AT&T Center for Internet Research at ICSI

   Isidor Kouvelas
   kouvelas@cisco.com
   cisco Systems

   Lorenzo Vicisano
   lorenzo@cisco.com
   cisco Systems described in [8].

5.1.  Appendix A: Election Reliability Enhancements

For the correct operation of bi-directional PIM it is very important to
avoid situations where two routers consider themselves to be Designated
Forwarders for the same link. The two precautions below are not required
for correct operation but can help diagnose anomalies and correct them.

5.1.1.  A.1 Missing Pass

After a DF has been elected, a router whose metrics change to become
better than the DF will attempt to take over. If during the re-
   election re-election
the acting DF has a condition that causes it to lose all of the election
messages (like a CPU overload), the new candidate will transmit three
offers and assume the role of the forwarder resulting in two DFs on the
link. This situation is pathological and should be corrected by fixing
the overloaded router. It is desirable that such an event can be
detected by a network administrator.

When a router becomes the DF for a link without receiving a Pass mes-
   sage message
from the known old DF, the PIM neighbor information for the old DF can
be marked to this effect. Upon receiving the next PIM Hello message from
the old DF, the router can retransmit Winner messages for all the RPs
for which it acting as the DF. The anomaly may also be logged by the
router to alert the operator.

5.1.2.  A.2 Periodic Winner Announcement

An additional degree of safety can be achieved by having the DF for each
RP periodically announce its status in a Winner message.  Transmission
of the periodic Winner message can be restricted to occur only for RPs
which have active groups, thus avoiding the periodic control traffic in
areas of the network without senders or receivers for a particular RP.

5.2.  Appendix B: Interoperability with legacy code

The rules provided in [2] [10] for interoperating between legacy PIM-SM
routers and new bi-directional capable routers change only slightly to
support this new proposal. The only difference is in the defini-
   tion definition of a
boundary between a bi-directional capable area and a legacy area of the
network.  In [2], [10], a bidir capable router forwarding upstream, register
encapsulates the data packet to the RP if its RPF neighbor is not bidir
capable.

In our proposal, since all the routers on a link need to co-operate to
elect the Designated Forwarder, if even one of the routers on the link
is a legacy router, the election cannot take place. As a result register
encapsulation is necessary if one or more routers on the RPF interface
are not bi-directional capable.

As in [2], [10], a Hello option must be used to differentiate between bi-
directional capable and legacy routers, and (S,G) state must be created
on the router doing the register encapsulation to prevent loops.

5.3.  Appendix C: Comparison with PIM-SM

This section describes the main differences between Bidir PIM and
sparse-mode PIM:

     o Bidir PIM uses a single shared tree for distributing the data for
       all the sources of a multicast group. The use of a signle single tree sig-
     nificantly
       significantly reduces state requirements on a router. The
       drawback is that it may produce suboptimal paths from sources to
       receivers pos-
     sibly possibly resulting in higher network latency and less
       efficient bandwidth utilisation.

     o In Bidir PIM, packets traveling from a source to the RP, are
       natively forwarded on the shared tree. In contrast sparse-mode
       PIM uses unicast encapsulation or source-specific state.

     o In Bidir PIM, sender-only branches do not need to keep group
       state. Data from the source can be natively forwarded towards the
       RP using RP-specific forwarding state.

     o The Bidir Designated Forwarder (DF) assumes all the responsibili-
     ties
       responsibilities of the sparse-mode DR. In a multi-access link,
       the DF responds to IGMP notifications. Downstream routers on the
       link use the DF as their upstream neighbor and direct all
       Join/Prune messages towards it.

     o To enforce a single forwarder on multi-access links, sparse-mode
       PIM uses the Assert mechanism which requires data-packets to
       trigger protocol events. In Bidir PIM, data-driven events are com-
     pletely
       completely eliminated as a correct route is always available at
       packet forwarding time.

     The DF election problem is easier than the assert problem because
     there is a small number of RPs and the per RP DF election can be
     done in advance. With the assert mechanism, in addition to each RP,
     a forwarder has to be elected for each possible source to a group.
     This can not be done before data is available.

     o With sparse-mode PIM, when forwarding packets using shared-tree
       (*,G) state, a directly-connected-source check has to be made on
       every packet.  This is done to determine if the packet was ori-
     ginated
       originated by a source which is directly connected to the router.
       For a connected source, source-specific state has to be created
       to register packets to the RP and prune the source off the shared
       tree.

     With Bidir PIM directly connected sources do not need any special
     handling. The DF for the RP of the group the source is sending to,
     seamlessly picks-up and forwards upstream traveling packets.

Appendix D: Comparison with UMP based bidirectional PIM

   Using an UMP option for upstream forwarding has the following disad-
   vantages:

   o Using the DF election, only routers willing to be forwarders can be
     elected. In contrast in [2], the downstream router designates the
     upstream neighbor responsible for forwarding (using Joins and UMP
     packets).

   o Using the UMP option, regular data packets are overloaded with con-
     trol information for the routing protocol.

   o Inserting the extra option in multicast packets transmitted from a
     source may result in a packet size exceeding the MTU which will
     result in fragmentation.

   o The use of an option complicates the router forwarding mechanism.
     Additional code to process the new special packet type needs to be
     written.

   o The contents of the UMP option have to be rewritten and the packet
     checksum adjusted on each hop towards sources do not need any special
     handling. The DF for the RP at data forwarding
     time.  This introduces additional per packet processing overhead.

   In bidir PIM [2], if of the router elected as group the DR source is different from
   that chosen by downstream neighbors for joining sending to,
     seamlessly picks-up and forwards upstream traveling packets.

6.  Authors' Addresses

     Mark Handley
     ACIRI/ICSI
     1947 Center St, Suite 600
     Berkeley, CA 94708
     mjh@aciri.org

     Isidor Kouvelas
     Cisco Systems
     kouvelas@cisco.com
     Lorenzo Vicisano
     Cisco Systems
     lorenzo@cisco.com

7.  Acknowledgments

The bidir proposal in this draft is heavily based on the tree, loops can
   occur. ideas and text
presented by Estrin and Farinacci in [10]. The main shortcoming of difference between
the DR two proposals is that its election does not
   take into consideration the location of the RP. To resolve this prob-
   lem in the DR priority draft [3] provides a method chosen for manually confi-
   guring the DR election winner. Although upstream forwarding.

We would also like to thank Deborah Estrin at ISI/USC as well as Nidhi
Bhaskar, Yiqun Cai, Tony Speakman and Rajitha Sumanasakera at cisco for
their contributions and comments to this provides a solution it
   has two drawbacks:

   o It requires a case by case manual configuration.

   o It cannot solve the problem if there are different RPs draft.

8.  References

[1] T. Bates , R. Chandra , D. Katz , Y. Rekhter, "Multiprotocol
     Extensions for BGP-4", RFC 2283

[2] S.E. Deering, "Host extensions for IP multicasting", RFC 1112, Aug
     1989.

[3] W. Fenner, "Internet Group Management Protocol, Version 2", RFC
     2236.

[4] IANA, "Address Family Numbers", linked from
     http://www.iana.org/numbers.html

[5] T. Narten , H. Alvestrand, "Guidelines for Writing an IANA
     Considerations Section in a domain
     serving separate multicast group ranges. In this scenario the
     requirements of each RP RFCs", RFC 2434.

[6] S. Kent, R. Atkinson, "Security Architecture for the DR positioning on a particular link
     may differ. Internet
     Protocol.", RFC 2401.

[7] L. Wei, "Authenticating PIM version 2 messages", draft-ietf-pim-
     v2-auth-01.txt, work in progress.

[8] T. Hardjono, B. Cain, "Simple Key Management Protocol for PIM",
     draft-ietf-pim-simplekmp-01.txt, work in progress.

[9] B. Fenner, M. Handley, H. Holbrook, I. Kouvelas "Protocol
     Independent Multicast - Sparse Mode (PIM-SM):  Protocol
     Specification (Revised)", Work In Progress, <draft-ietf-pim-sm-
     v2-new-01.txt>, 2000.

[10] D. Estrin, D. Farinacci, "Bi-directional Shared Trees in PIM-SM",
     Work In Progress, <draft-farinacci-bidir-pim-01.txt>, May 1999.

[11] D. Estrin et al, "Protocol Independent Multicast-Sparse Mode (PIM-
     SM): Protocol Specification", RFC 2362, Nov 1999.

9.  Index
DownstreamJPState(G,I) . . . . . . . . . . . . . . . . . . . . . . .  12
ET(G,I). . . . . . . . . . . . . . . . . . . . . . . . . . . . .10,14,29
ET(RP,I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  10
I_am_DF(RP,I). . . . . . . . . . . . . . . . . . . . . . . . . .11,13,16
J/P_HoldTime . . . . . . . . . . . . . . . . . . . . . . . . . . . .  29
J/P_Override_Interval. . . . . . . . . . . . . . . . . . . . . . . 16,30
JoinDesired(G) . . . . . . . . . . . . . . . . . . . . . . . . . . .  18
joins(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  12
JT(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  17
JT(G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10,30
local_receiver_include(G,I). . . . . . . . . . . . . . . . . . . . .  11
NLT(N,I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   9
Offer_Period . . . . . . . . . . . . . . . . . . . . . . . . . . . .  29
olist(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . .11,13,18
OT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  29
pim_include(G) . . . . . . . . . . . . . . . . . . . . . . . . . . .  11
PPT(G,I) . . . . . . . . . . . . . . . . . . . . . . . . . . . .10,14,30
RPF_interface(RP). . . . . . . . . . . . . . . . . . . . . . . . . 11,13
t_override . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18,30
t_periodic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18,30
t_suppressed . . . . . . . . . . . . . . . . . . . . . . . . . . . 18,30