Internet Engineering Task Force                                   PIM WGINTERNET-DRAFT                                         Mark Handley/ICIRdraft-ietf-pim-bidir-04.txt                        Isidor Kouvelas/Cisco                                                     Tony Speakman/Cisco                                                  Lorenzo Vicisano/Cisco                                                            26 June 2002                                                  Expires: December 2002       Bi-directional Protocol Independent Multicast (BIDIR-PIM)Status of this DocumentThis document is an Internet-Draft and is in full conformance with allprovisions of Section 10 of RFC2026.Internet-Drafts are working documents of the Internet Engineering TaskForce (IETF), its areas, and its working groups.  Note that other groupsmay also distribute working documents as Internet-Drafts.Internet-Drafts are draft documents valid for a maximum of six monthsand may be updated, replaced, or obsoleted by other documents at anytime.  It is inappropriate to use Internet-Drafts as reference materialor to cite them other than as "work in progress."The list of current Internet-Drafts can be accessed athttp://www.ietf.org/ietf/1id-abstracts.txtThe list of Internet-Draft Shadow Directories can be accessed athttp://www.ietf.org/shadow.html.This document is a product of the IETF PIM WG.  Comments should beaddressed to the authors, or the WG's mailing list atpim@catarina.usc.edu.                                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 isHandley/Kouvelas/Speakman/Vicisano                              [Page 1]INTERNET-DRAFT           Expires: December 2002                June 2002     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 statusThe differences between this version of the BIDIR-PIM specification anddraft-ietf-pim-bidir-new-00.txt are mostly in the format of theinformation presented. As BIDIR-PIM has many similarities in operationto Sparse-Mode PIM, the earlier version of this spec relied heavily onthe now obsolete PIM-SM [11] specification. This revision removes thisdependency and instead references the new Sparse-Mode documentation [9]where necessary. In addition the method in which the protocolspecification is presented has been updated to follow the format of [9].Handley/Kouvelas/Speakman/Vicisano                              [Page 2]INTERNET-DRAFT           Expires: December 2002                June 2002                           Table of Contents1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . .   52. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . .   5 2.1. Definitions. . . . . . . . . . . . . . . . . . . . . . . . . .   6 2.2. Pseudocode Notation. . . . . . . . . . . . . . . . . . . . . .   73. 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. . . . . . . . . . . . . . .  344. RP Discovery. . . . . . . . . . . . . . . . . . . . . . . . . . .  355. 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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  36Handley/Kouvelas/Speakman/Vicisano                              [Page 3]INTERNET-DRAFT           Expires: December 2002                June 2002 5.3. Appendix C: Comparison with PIM-SM . . . . . . . . . . . . . .  376. Todo list.... . . . . . . . . . . . . . . . . . . . . . . . . . .  387. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . . .  388. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . .  389. References. . . . . . . . . . . . . . . . . . . . . . . . . . . .  3910. Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  40Handley/Kouvelas/Speakman/Vicisano                              [Page 4]INTERNET-DRAFT           Expires: December 2002                June 20021.  IntroductionThis document specifies Bi-directional PIM, a variant of PIM Sparse-Mode(PIM-SM) [9] that builds bi-directional shared trees connectingmulticast sources and receivers.PIM-SM constructs uni-directional shared trees that are used to forwarddata from senders to receivers of a multicast group.  PIM-SM also allowsthe construction of source specific trees, but this capability is notrelated to the protocol described in this document.The shared tree for each multicast group is rooted at a multicast routercalled the Rendezvous Point (RP). Different multicast group ranges canuse separate RPs within a PIM domain.In unidirectional PIM-SM, there are two possible methods fordistributing data packets on the shared tree. These differ in the waypackets 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 insignificant processing, bandwidth and delay overheads. Forwarding usingsource specific state has additional protocol and memory requirements.Bi-directional PIM dispenses with both encapsulation and source state byallowing packets to be natively forwarded from a source to the RP usingshared tree state. For a complete discussion of the pros and cons of Bi-directional PIM consult appendix C.2.  TerminologyIn 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 indicaterequirement levels for compliant PIM-SM implementations.Handley/Kouvelas/Speakman/Vicisano                  Section 2.  [Page 5]INTERNET-DRAFT           Expires: December 2002                June 20022.1.  DefinitionsThis specification uses a number of terms to refer to the roles ofrouters participating in BIDIR-PIM.  The following terms have specialsignificance 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 2002                June 2002RPF 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