draft-ietf-pim-bidir-03.txt

BCAST Implementation for NS2

      trees at that router.

MFIB  Multicast Forwarding Information Base.  The TIB holds all the
      state that is necessary to forward multicast packets at a router.
      However, although this specification defines forwarding in terms
      of the TIB, to actually forward packets using the TIB is very
      inefficient.  Instead a real router implementation will normally
      build an efficient MFIB from the TIB state to perform forwarding.
      How this is done is implementation-specific, and is not discussed
      in this document.


2.2.  Pseudocode Notation

We use set notation in several places in this specification.

A (+) B
    is the union of two sets A and B.

A (-) B
    is the elements of set A that are not in set B.

NULL
    is the empty set or list.

In addition we use C-like syntax:

=   denotes assignment of a variable.

==  denotes a comparison for equality.

!=  denotes a comparison for inequality.

Braces { and } are used for grouping.





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


3.  Protocol Specification

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

o Section 3.1 details the protocol state stored.

o Section 3.3 specifies the data packet forwarding rules.

o Section 3.4 specifies the BIDIR-PIM Join/Prune generation and
  processing rules.

o Designated Forwarder (DF) election is specified in Section 3.5.

o PIM packet formats are specified in Section 3.7.

o A summary of BIDIR-PIM timers and their default values is given in
  Section 3.6.


3.1.  BIDIR-PIM Protocol State

This section specifies all the protocol state that a BIDIR-PIM
implementation should maintain in order to function correctly.  We term
this state the Tree Information Base or TIB, as it holds the state of
all the multicast distribution trees at this router.  In this
specification we define PIM mechanisms in terms of the TIB.  However,
only a 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 relevant state in the TIB changes.

Although we specify precisely the state to be kept, this does not mean
that an implementation of PIM-SM needs to hold the state in this form.
This is actually an abstract state definition, which is needed in order
to specify the 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 same externally
visible protocol behavior as an abstract router that holds the 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 group-specific tree for groups that map to a
     given RP.



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


The state that should be kept is described below.  Of course,
implementations will only maintain state when it is relevant to
forwarding operations - for 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 holds the following state that is not specific to a RP or
group:

     Neighbor State:

          For each neighbor:

               o Information from neighbor's Hello

               o 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
through static configuration or by using an automatic RP discovery
mechanism like BSR or AUTO-RP (see section 4 ). For each BIDIR-PIM RP a
router holds the following state:

     o RP address

     Designated Forwarder (DF) State:

            For each router interface:

            Acting DF information:

                 o DF IP Address

                 o DF metric

            Election information:

                 o Election State

                 o DF Election-Timer (DFT)





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


                 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 keeps the following state:

          Group state:

               For each 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 the result of the local membership mechanism (such
as IGMP) running on that interface. This information is used by the
pim_include(*,G) macro described in section 3.1.4.

PIM Join/Prune state is the result of receiving PIM (*,G) Join/Prune
messages on this interface, and is specified in section 3.4.1. The state
is used by the macros that calculate the outgoing interface list in
section 3.1.4, and in the JoinDesired(G) macro (defined in section
3.4.2) that is used in deciding whether a Join(*,G) should be sent
upstream.



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


The upstream Join/Prune timer is used to send out periodic Join(*,G)
messages, and to override Prune(*,G) messages from peers on an upstream
LAN interface.

The last RP used must be stored because if the RP Set changes [9] then
state must be torn down and rebuilt for groups whose RP changes.



3.1.4.  State Summarization Macros

Using this state, we define the following "macro" definitions which we
will use in the descriptions of the state machines and pseudocode in the
following sections.


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


RPF_interface(RP) is the interface the MRIB indicates would be used to
route packets to RP. The olist(G) is the list of interfaces on which
packets to group G must be forwarded.

The macro pim_include(G) indicates the 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 clause "I_am_DF(RP,I)" is TRUE if the router is in the Win or
Backoff states in the DF election state machine for interface I
(described in section 3.5 ).  Otherwise it is FALSE.

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 }



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


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

RPF_DF(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.

Bidir PIM introduces the Bidir_Capable PIM-Hello option that MUST be
included in all Hello messages from a Bidir-PIM capable router.  The
Bidir_Capable option advertises the router's ability to participate in
the Bidir-PIM protocol. The format of the Bidir_Capable option is
described in section 3.7.

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

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

     iif is the incoming interface of the packet.
     G is the destination address of the packet (group address).
     RP is the address of the Rendezvous Point for this group.




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


First we check to see whether the packet should be accepted based on TIB
state and the interface that the packet 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 on the interface the packet arrives
(upstream traveling packet).

If the packet should be forwarded we build an outgoing interface list
for the packet.

Finally we remove the incoming interface from the outgoing interface
list we've created, and if the resulting outgoing interface list is not
empty, we forward the packet 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) (-) iif
    forward packet on all interfaces in oiflist
 }