draft-ietf-pim-bidir-03.txt

BCAST Implementation for NS2

Internet Engineering Task Force                                   PIM WG
INTERNET-DRAFT                                        Mark Handley/ACIRI
draft-ietf-pim-bidir-03.txt                        Isidor Kouvelas/Cisco
                                                     Tony Speakman/Cisco
                                                  Lorenzo Vicisano/Cisco
                                                            19 June 2001
                                                  Expires: December 2001


       Bi-directional Protocol Independent Multicast (BIDIR-PIM)


Status of this 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
[e-mail].

                                Abstract


     This document discusses Bi-directional PIM, a variant of PIM
     Sparse-Mode [9] that builds bi-directional shared trees
     connecting multicast sources and receivers. Bi-directional
     trees are built using a fail-safe Designated Forwarder (DF)
     election mechanism operating on each link of a multicast
     topology.  With the assistance of the DF, multicast data is



Handley/Kouvelas/Speakman/Vicisano                              [Page 1]

INTERNET-DRAFT           Expires: December 2001                June 2001


     natively forwarded from sources to the Rendezvous-Point and
     hence along the shared tree to receivers 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.

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



































Handley/Kouvelas/Speakman/Vicisano                              [Page 2]

INTERNET-DRAFT           Expires: December 2001                June 2001


                           Table of Contents


1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . .   5
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . .   5
 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. . . . . . . . . . . . . . . . . . . .  24
   3.5.3.3. Election Events. . . . . . . . . . . . . . . . . . . . .  24
   3.5.3.4. Election Notation. . . . . . . . . . . . . . . . . . . .  25
   3.5.3.5. Election State Transitions . . . . . . . . . . . . . . .  25
 3.6. Timers and Constants . . . . . . . . . . . . . . . . . . . . .  28
 3.7. BIDIR PIM Packet Formats . . . . . . . . . . . . . . . . . . .  32
  3.7.1. DF Election Packet Formats. . . . . . . . . . . . . . . . .  32
  3.7.2. Backoff Message . . . . . . . . . . . . . . . . . . . . . .  33
  3.7.3. Pass Message. . . . . . . . . . . . . . . . . . . . . . . .  34
  3.7.4. Bidir Capable PIM-Hello Option. . . . . . . . . . . . . . .  34
4. RP Discovery. . . . . . . . . . . . . . . . . . . . . . . . . . .  35
5. Security Considerations . . . . . . . . . . . . . . . . . . . . .  35
 5.1. Appendix A: Election Reliability
 Enhancements. . . . . . . . . . . . . . . . . . . . . . . . . . . .  35
  5.1.1. A.1 Missing Pass. . . . . . . . . . . . . . . . . . . . . .  36
  5.1.2. A.2 Periodic Winner Announcement. . . . . . . . . . . . . .  36
 5.2. Appendix B: Interoperability with legacy
 code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  36



Handley/Kouvelas/Speakman/Vicisano                              [Page 3]

INTERNET-DRAFT           Expires: December 2001                June 2001


 5.3. Appendix C: Comparison with PIM-SM . . . . . . . . . . . . . .  37
6. Todo list.... . . . . . . . . . . . . . . . . . . . . . . . . . .  38
7. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . . .  38
8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  38
9. References. . . . . . . . . . . . . . . . . . . . . . . . . . . .  39
10. Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  40













































Handley/Kouvelas/Speakman/Vicisano                              [Page 4]

INTERNET-DRAFT           Expires: December 2001                June 2001


1.  Introduction

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

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 construction of source specific trees, but this capability is not
related to the 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 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, its 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 PIM consult appendix C.


2.  Terminology

In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL",
"SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and
"OPTIONAL" are to be interpreted as described in RFC 2119 and indicate
requirement levels for compliant PIM-SM implementations.






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


2.1.  Definitions

This specification uses a number of terms to refer to the roles of
routers participating in BIDIR-PIM.  The following terms have special
significance for BIDIR-PIM:

MRIB  Multicast Routing Information Base.  This is the multicast
      topology table, which is typically derived from the unicast
      routing table, or routing protocols such as MBGP that carry
      multicast-specific topology information. It is used by PIM for
      establishing the RPF interface (used in the forwarding rules). In
      PIM-SM the MRIB is also used to make decisions regarding where to
      forward Join/Prune messages whereas in BIDIR-PIM it is used as a
      source for routing metrics for the DF election process.

Rendezvous Point (RP):
      An RP is a router that has been configured to be used as the root
      of the distribution tree for a range of multicast groups. Join
      messages from receivers for a group are sent towards the RP.

Upstream
      Towards the root (Rendezvous-Point) of the tree. The direction
      used by packets traveling from sources to the RP.

Downstream
      Away from the root of the tree. The direction on which packets
      travel from the RP to receivers.

Designated Forwarder (DF):
      The protocol presented in this document is largely based on the
      concept of a Designated Forwarder (DF). A single DF exists for
      each RP on every link within a 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 downstream traffic onto the
      link, and forwarding upstream traffic from the link towards the
      RP.  It does this for all the bi-directional groups served by the
      RP. The DF on a link is also responsible for interpreting IGMP
      information from local receivers and processing Join messages from
      other routers on the link.

RPF Interface
      RPF stands for "Reverse Path Forwarding".  The RPF Interface of a
      router with respect to an address is the interface that the MRIB
      indicates should be used to forward packets to that address.  In
      the case of a BIDIR-PIM multicast group, the RPF interface is the
      interface that would be used to send packets to the RP for the
      group.



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


RPF Neighbor
      The RPF Neighbor of a router with respect to an address is the
      neighbor that the MRIB indicates should be used to forward packets
      to that address. Note that in BIDIR-PIM, the RPF neighbor for a
      group is not necessarily the router on the RPF interface that Join
      messages for that group would be directed to (Join messages are
      directed to the DF on the RPF interface for the group).

TIB   Tree Information Base.  This is the collection of state at a PIM
      router that has been created by receiving PIM Join/Prune messages,
      PIM DF election messages and IGMP information from local hosts.
      It essentially stores the state of all multicast distribution