draft-ietf-pim-bidir-01.txt   draft-ietf-pim-bidir-02.txt 
Internet Engineering Task Force PIM WG Internet Engineering Task Force PIM WG
INTERNET-DRAFT Mark Handley/ACIRI INTERNET-DRAFT Mark Handley/ACIRI
draft-ietf-pim-bidir-01.txt Isidor Kouvelas/Cisco draft-ietf-pim-bidir-02.txt Isidor Kouvelas/Cisco
Tony Speakman/Cisco
Lorenzo Vicisano/Cisco Lorenzo Vicisano/Cisco
23 November 2000 2 March 2001
Expires: May 2001 Expires: September 2001
Bi-directional Protocol Independent Multicast (BIDIR-PIM) Bi-directional Protocol Independent Multicast (BIDIR-PIM)
Status of this Document Status of this Document
This document is an Internet-Draft and is in full conformance with all This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026. provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering Task Internet-Drafts are working documents of the Internet Engineering Task
Force (IETF), its areas, and its working groups. Note that other groups Force (IETF), its areas, and its working groups. Note that other groups
skipping to change at page 1, line 43 skipping to change at page 2, line 4
pim@catarina.usc.edu. pim@catarina.usc.edu.
Abstract Abstract
This document discusses Bi-directional PIM, a variant of PIM This document discusses Bi-directional PIM, a variant of PIM
Sparse-Mode [9] that builds bi-directional shared trees Sparse-Mode [9] that builds bi-directional shared trees
connecting multicast sources and receivers. Bi-directional connecting multicast sources and receivers. Bi-directional
trees are built using a fail-safe Designated Forwarder (DF) trees are built using a fail-safe Designated Forwarder (DF)
election mechanism operating on each link of a multicast election mechanism operating on each link of a multicast
topology. With the assistance of the DF, multicast data is topology. With the assistance of the DF, multicast data is
natively forwarded from sources to the Rendezvous-Point natively forwarded from sources to the Rendezvous-Point and
without requiring source-specific state. The DF election hence along the shared tree to receivers without requiring
takes place at RP discovery time and provides a default route source-specific state. The DF election takes place at RP
to the RP thus eliminating the requirement for data-driven discovery time and provides a default route to the RP thus
protocol events. eliminating the requirement for data-driven protocol events.
Note on BIDIR-PIM status Note on BIDIR-PIM status
The differences between this version of the BIDIR-PIM specification and 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 draft-ietf-pim-bidir-new-00.txt are mostly in the format of the
information presented. As BIDIR-PIM has many similarities in operation information presented. As BIDIR-PIM has many similarities in operation
to Sparse-Mode PIM, the earlier version of this spec relied heavily on to Sparse-Mode PIM, the earlier version of this spec relied heavily on
the now obsolete PIM-SM [11] specification. This revision removes this the now obsolete PIM-SM [11] specification. This revision removes this
dependency and instead references the new Sparse-Mode documentation [9] dependency and instead references the new Sparse-Mode documentation [9]
where necessary. In addition the method in which the protocol where necessary. In addition the method in which the protocol
specification is presented has been updated to follow the format of [9]. specification is presented has been updated to follow the format of [9].
Table of Contents Table of Contents
1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1. Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1. Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2. Pseudocode Notation. . . . . . . . . . . . . . . . . . . . . . 7 2.2. Pseudocode Notation. . . . . . . . . . . . . . . . . . . . . . 7
3. Protocol Specification. . . . . . . . . . . . . . . . . . . . . . 8 3. Protocol Specification. . . . . . . . . . . . . . . . . . . . . . 8
3.1. BIDIR-PIM Protocol State . . . . . . . . . . . . . . . . . . . 8 3.1. BIDIR-PIM Protocol State . . . . . . . . . . . . . . . . . . . 8
3.1.1. General Purpose State . . . . . . . . . . . . . . . . . . . 9 3.1.1. General Purpose State . . . . . . . . . . . . . . . . . . . 9
3.1.2. RP State. . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.1.2. RP State. . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1.3. Group State . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.3. Group State . . . . . . . . . . . . . . . . . . . . . . . . 10
3.1.4. State Summarization Macros. . . . . . . . . . . . . . . . . 11 3.1.4. State Summarization Macros. . . . . . . . . . . . . . . . . 11
3.2. PIM Neighbor Discovery . . . . . . . . . . . . . . . . . . . . 12 3.2. PIM Neighbor Discovery . . . . . . . . . . . . . . . . . . . . 12
3.3. Data Packet Forwarding Rules . . . . . . . . . . . . . . . . . 12 3.3. Data Packet Forwarding Rules . . . . . . . . . . . . . . . . . 12
skipping to change at page 3, line 50 skipping to change at page 3, line 50
3.7.2. Pass Message. . . . . . . . . . . . . . . . . . . . . . . . 33 3.7.2. Pass Message. . . . . . . . . . . . . . . . . . . . . . . . 33
4. RP Discovery. . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4. RP Discovery. . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5. Security Considerations . . . . . . . . . . . . . . . . . . . . . 34 5. Security Considerations . . . . . . . . . . . . . . . . . . . . . 34
5.1. Appendix A: Election Reliability 5.1. Appendix A: Election Reliability
Enhancements. . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Enhancements. . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.1.1. A.1 Missing Pass. . . . . . . . . . . . . . . . . . . . . . 34 5.1.1. A.1 Missing Pass. . . . . . . . . . . . . . . . . . . . . . 34
5.1.2. A.2 Periodic Winner Announcement. . . . . . . . . . . . . . 35 5.1.2. A.2 Periodic Winner Announcement. . . . . . . . . . . . . . 35
5.2. Appendix B: Interoperability with legacy 5.2. Appendix B: Interoperability with legacy
code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.3. Appendix C: Comparison with PIM-SM . . . . . . . . . . . . . . 35 5.3. Appendix C: Comparison with PIM-SM . . . . . . . . . . . . . . 35
6. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . . . 36 6. Todo list.... . . . . . . . . . . . . . . . . . . . . . . . . . . 36
7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 37 7. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . . . 36
8. References. . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 37
9. Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 9. References. . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
10. Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1. Introduction 1. Introduction
This document discusses Bi-directional PIM, a variant of PIM Sparse-Mode This document specifies Bi-directional PIM, a variant of PIM Sparse-Mode
(PIM-SM) [9] that builds bi-directional shared trees connecting (PIM-SM) [9] that builds bi-directional shared trees connecting
multicast sources and receivers. multicast sources and receivers.
PIM-SM constructs uni-directional shared trees that are used to forward 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 data from senders to receivers of a multicast group. PIM-SM also allows
the construction of source specific trees, but this capability is not the construction of source specific trees, but this capability is not
related to the protocol described in this document. related to the protocol described in this document.
The shared tree for each multicast group is rooted at a multicast router The shared tree for each multicast group is rooted at a multicast router
called the Rendezvous Point (RP). Different multicast group ranges can called the Rendezvous Point (RP). Different multicast group ranges can
use separate RPs within a PIM domain. use separate RPs within a PIM domain.
In unidirectional PIM-SM, there are two possible methods for In unidirectional PIM-SM, there are two possible methods for
distributing data packets on the shared tree. These differ in the way distributing data packets on the shared tree. These differ in the way
packets are forwarded from a source to the RP: packets are forwarded from a source to the RP:
o Initially when a source starts transmitting, it's first hop router o Initially when a source starts transmitting, its first hop router
encapsulates data packets in special control messages (Registers) encapsulates data packets in special control messages (Registers)
which are unicast to the RP. After reaching the RP the packets are which are unicast to the RP. After reaching the RP the packets are
decapsulated and distributed on the shared tree. decapsulated and distributed on the shared tree.
o A transition from the above distribution mode can be made at a later 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 stage. This is achieved by building source specific state on all
routers along the path between the source and the RP. This state is routers along the path between the source and the RP. This state is
then used to natively forward packets from that source. then used to natively forward packets from that source.
Both these mechanisms suffer from problems. Encapsulation results in Both these mechanisms suffer from problems. Encapsulation results in
significant processing, bandwidth and delay overheads. Forwarding using significant processing, bandwidth and delay overheads. Forwarding using
source specific state has additional protocol and memory requirements. source specific state has additional protocol and memory requirements.
Bi-directional PIM dispenses with both encapsulation and source state by Bi-directional PIM dispenses with both encapsulation and source state by
allowing packets to be natively forwarded from a source to the RP using 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- shared tree state. For a complete discussion of the pros and cons of Bi-
directional PIM consult appendix C. directional PIM consult appendix C.
The ideas presented in this document are similar to those described in
[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 [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 control information.
Instead the identification of the next hop upstream forwarder is
performed at RP discovery time using a fail-safe election mechanism.
2. Terminology 2. Terminology
In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL",
"SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and
"OPTIONAL" are to be interpreted as described in RFC 2119 and indicate "OPTIONAL" are to be interpreted as described in RFC 2119 and indicate
requirement levels for compliant PIM-SM implementations. requirement levels for compliant PIM-SM implementations.
2.1. Definitions 2.1. Definitions
This specification uses a number of terms to refer to the roles of This specification uses a number of terms to refer to the roles of
routers participating in BIDIR-PIM. The following terms have special routers participating in BIDIR-PIM. The following terms have special
significance for BIDIR-PIM: significance for BIDIR-PIM:
MRIB Multicast Routing Information Base. This is the multicast MRIB Multicast Routing Information Base. This is the multicast
topology table, which is typically derived from the unicast topology table, which is typically derived from the unicast
routing table, or routing protocols such as MBGP that carry routing table, or routing protocols such as MBGP that carry
multicast-specific topology information. In PIM-SM this is used multicast-specific topology information. It is used by PIM for
to make decisions regarding where to forward Join/Prune messages establishing the RPF interface (used in the forwarding rules). In
and in BIDIR-PIM is used as a source for routing metrics for the PIM-SM the MRIB is also used to make decisions regarding where to
DF election process. 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): Rendezvous Point (RP):
An RP is a router that has been configured to be used as the root 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 of the distribution tree for a range of multicast groups. Join
messages from receivers for a group are sent towards the RP. messages from receivers for a group are sent towards the RP.
Upstream Upstream
Towards the root (Rendezvous-Point) of the tree. The direction Towards the root (Rendezvous-Point) of the tree. The direction
used by packets traveling from sources to the RP. used by packets traveling from sources to the RP.
skipping to change at page 9, line 37 skipping to change at page 9, line 28
For each neighbor: For each neighbor:
o Information from neighbor's Hello o Information from neighbor's Hello
o Neighbor's Gen ID. o Neighbor's Gen ID.
o Neighbor liveness timer (NLT) o Neighbor liveness timer (NLT)
3.1.2. RP State 3.1.2. RP State
A router maintains a multicast-group to RP mapping which is built using A router maintains a multicast-group to RP mapping which is built
the BSR mechanism described in section 4. For each BIDIR-PIM RP a router through static configuration or by using an automatic RP discovery
holds the following state: mechanism like BSR or AUTO-RP (see section 4 ). For each BIDIR-PIM RP a
router holds the following state:
o RP address o RP address
Designated Forwarder (DF) State: Designated Forwarder (DF) State:
For each router interface: For each router interface:
Acting DF information: Acting DF information:
o DF IP Address o DF IP Address
skipping to change at page 11, line 41 skipping to change at page 11, line 34
The macro pim_include(G) indicates the interfaces to which traffic might The macro pim_include(G) indicates the interfaces to which traffic might
be forwarded because of hosts that are local members on that interface. be forwarded because of hosts that are local members on that interface.
pim_include(G) = pim_include(G) =
{ all interfaces I such that: { all interfaces I such that:
I_am_DF(RP(G),I) AND local_receiver_include(G,I) } 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 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 in section 3.5. Backoff states in the DF election state machine in section 3.5.
Otherwise it is FALSE.
The clause "local_receiver_include(G,I)" is true if the IGMP module or The clause "local_receiver_include(G,I)" is true if the IGMP module or
other local membership mechanism has determined that there are local other local membership mechanism has determined that there are local
members on interface I that desire to receive traffic sent to group G. 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 The set "joins(G)" is the set of all interfaces on which the router has
received (*,G) Joins: received (*,G) Joins:
joins(G) = joins(G) =
{ all interfaces I such that { all interfaces I such that
I_am_DF(RP(G),I) AND I_am_DF(RP(G),I) AND
DownstreamJPState(G,I) is either Joined or PrunePending } DownstreamJPState(G,I) is either Joined or PrunePending }
DownstreamJPState(G,I) is the state of the finite state machine in DownstreamJPState(G,I) is the state of the finite state machine in
section 3.4.1. section 3.4.1.
RPF'(RP) is the neighbor that Join messages must be sent to in order to RPF_DF(RP) is the neighbor that Join messages must be sent to in order
reach the RP. This is the Designated-Forwarder on the RPF_interface(RP). to reach the RP. This is the Designated-Forwarder on the
RPF_interface(RP).
3.2. PIM Neighbor Discovery 3.2. PIM Neighbor Discovery
PIM routers exchange PIM Hello messages with their neighboring PIM PIM routers exchange PIM Hello messages with their neighboring PIM
routers. These messages are used to update the Neighbor State described routers. These messages are used to update the Neighbor State described
in section 3.1. The procedures for generating and processing received in section 3.1. The procedures for generating and processing received
Hello messages as well as maintaining Neighbor State are specified in Hello messages as well as maintaining Neighbor State are specified in
the PIM-SM [9] documentation. the PIM-SM [9] documentation.
3.3. Data Packet Forwarding Rules 3.3. Data Packet Forwarding Rules
skipping to change at page 13, line 21 skipping to change at page 13, line 15
If the packet should be forwarded we build an outgoing interface list If the packet should be forwarded we build an outgoing interface list
for the packet. for the packet.
Finally we remove the incoming interface from the outgoing interface Finally we remove the incoming interface from the outgoing interface
list we've created, and if the resulting outgoing interface list is not list we've created, and if the resulting outgoing interface list is not
empty, we forward the packet out of those interfaces. empty, we forward the packet out of those interfaces.
On receipt on a data to G on interface iif: On receipt on a data to G on interface iif:
if( iif == RPF_interface(RP) || I_am_DF(RP,I) ) { if( iif == RPF_interface(RP) || I_am_DF(RP,I) ) {
oiflist = olist(G) oiflist = olist(G) (-) iif
oiflist = oiflist (-) iif
forward packet on all interfaces in oiflist forward packet on all interfaces in oiflist
} }
Note: A major advantage of using a Designated Forwarder in BIDIR-PIM Note: A major advantage of using a Designated Forwarder in BIDIR-PIM
compared to PIM-SM is that special treatment is no longer required for 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 sources that are directly connected to a router. Data from such sources
does not need to be differentiated from other multicast traffic and will does not need to be differentiated from other multicast traffic and will
automatically be picked up by the DF. This removes the need for automatically be picked up by the DF. This removes the need for
performing a directly-connected-source check for data to groups that do performing a directly-connected-source check for data to groups that do
not have existing state. not have existing state.
skipping to change at page 14, line 18 skipping to change at page 14, line 12
message whose PIM Destination field addresses another router, most Join message whose PIM Destination field addresses another router, most Join
or Prune entries could affect the upstream state machine. or Prune entries could affect the upstream state machine.
3.4.1. Receiving (*,G) Join/Prune Messages 3.4.1. Receiving (*,G) Join/Prune Messages
When a router receives a Join(*,G) or Prune(*,G) it must first check to When a router receives a Join(*,G) or Prune(*,G) it must first check to
see whether the RP in the message matches RP(G) (the router's idea of see whether the RP in the message matches RP(G) (the router's idea of
who the RP is). If the RP in the message does not match RP(G) the Join who the RP is). If the RP in the message does not match RP(G) the Join
or Prune MUST be silently dropped. In addition a router MUST NOT process or Prune MUST be silently dropped. In addition a router MUST NOT process
Join(*,G) messages targeted to itself if it is not the DF for RP(G) on Join(*,G) messages targeted to itself if it is not the DF for RP(G) on
the interface the message was received. the interface on which the message was received.
The per-interface state-machine for receiving (*,G) Join/Prune Messages The per-interface state-machine for receiving (*,G) Join/Prune Messages
is given below. There are three states: is given below. There are three states:
NoInfo (NI) NoInfo (NI)
The interface has no (*,G) Join state and no timers running. The interface has no (*,G) Join state and no timers running.
Join (J) Join (J)
The interface has (*,G) Join state which will cause us to The interface has (*,G) Join state which will cause us to
forward packets destined for G from this interface. forward packets destined for G from this interface.
skipping to change at page 16, line 35 skipping to change at page 16, line 27
3.4.2. Sending Join/Prune Messages 3.4.2. Sending Join/Prune Messages
The downstream per-interface state-machines described above hold join The downstream per-interface state-machines described above hold join
state from downstream PIM routers. This state then determines whether a state from downstream PIM routers. This state then determines whether a
router needs to propagate a Join(*,G) upstream towards the RP. Such router needs to propagate a Join(*,G) upstream towards the RP. Such
Join(*,G) messages are sent on the RPF_interface towards the RP and are Join(*,G) messages are sent on the RPF_interface towards the RP and are
targeted at the DF on that interface. targeted at the DF on that interface.
If a router wishes to propagate a Join(*,G) upstream, it must also watch If a router wishes to propagate a Join(*,G) upstream, it must also watch
for messages on it's upstream interface from other routers on that for messages on its upstream interface from other routers on that
subnet, and these may modify its behavior. If it sees a Join(*,G) to subnet, and these may modify its behavior. If it sees a Join(*,G) to
the correct upstream neighbor, it should suppress its own Join(*,G). If the correct upstream neighbor, it should suppress its own Join(*,G). If
it sees a Prune(*,G) to the correct upstream neighbor, it should be it sees a Prune(*,G) to the correct upstream neighbor, it should be
prepared to override that prune by sending a Join(*,G) almost prepared to override that prune by sending a Join(*,G) almost
immediately. Finally, if it sees the Generation ID (see PIM-SM immediately. Finally, if it sees the Generation ID (see PIM-SM
specification [9]) of the correct upstream neighbor change, it knows specification [9]) of the correct upstream neighbor change, it knows
that the upstream neighbor has lost state, and it should be prepared to that the upstream neighbor has lost state, and it should be prepared to
refresh the state by sending a Join(*,G) almost immediately. refresh the state by sending a Join(*,G) almost immediately.
In addition changes in the next hop towards the RP trigger a prune off In addition changes in the next hop towards the RP trigger a prune off
skipping to change at page 18, line 28 skipping to change at page 18, line 28
| Joined (J) | - | -> NJ state | | Joined (J) | - | -> NJ state |
| | | Send Prune(*,G) | | | | Send Prune(*,G) |
+----------------------+------------------------+-----------------------+ +----------------------+------------------------+-----------------------+
In addition, we have the following transitions which occur within the In addition, we have the following transitions which occur within the
Joined state: Joined state:
+-----------------------------------------------------------------------+ +-----------------------------------------------------------------------+
| In Joined (J) State | | In Joined (J) State |
+-----------------+-----------------+-----------------+-----------------+ +-----------------+-----------------+-----------------+-----------------+
|Timer Expires | See Join(*,G) | See Prune(*,G) | RPF'(*,G) | |Timer Expires | See Join(*,G) | See Prune(*,G) | RPF_DF(RP(G)) |
| | to RPF'(*,G) | to RPF'(*,G) | changes | | | to | to | changes |
| | RPF_DF(RP(G)) | RPF_DF(RP(G)) | |
+-----------------+-----------------+-----------------+-----------------+ +-----------------+-----------------+-----------------+-----------------+
|Send | Increase Timer | Decrease Timer | Decrease Timer | |Send | Increase Timer | Decrease Timer | Decrease Timer |
|Join(*,G); Set | to | to t_override | to t_override | |Join(*,G); Set | to | to t_override | to t_override |
|Timer to | t_suppressed | | | |Timer to | t_suppressed | | |
|t_periodic | | | | |t_periodic | | | |
+-----------------+-----------------+-----------------+-----------------+ +-----------------+-----------------+-----------------+-----------------+
+-----------------------------------------------------------------------+ +-----------------------------------------------------------------------+
| In Joined (J) State | | In Joined (J) State |
+-------------------------------------+---------------------------------+ +-------------------------------------+---------------------------------+
| topology change wrt | RPF'(RP(G)) GenID | | Change of RPF_DF(RP(G)) | RPF_DF(RP(G)) GenID |
| RPF'(RP(G)) | changes | | | changes |
+-------------------------------------+---------------------------------+ +-------------------------------------+---------------------------------+
| Send Join(*,G) to new | Decrease Timer to | | Send Join(*,G) to new | Decrease Timer to |
| next hop; Send | t_override | | DF; Send Prune(*,G) to | t_override |
| Prune(*,G) to old next | | | old DF; set Timer to | |
| hop; set Timer to | |
| t_periodic | | | t_periodic | |
+-------------------------------------+---------------------------------+ +-------------------------------------+---------------------------------+
This state machine uses the following macro: This state machine uses the following macro:
bool JoinDesired(G) { bool JoinDesired(G) {
if (olist(G) (-) RPF_interface(RP(G))) != NULL if (olist(G) (-) RPF_interface(RP(G))) != NULL
return TRUE return TRUE
else else
return FALSE return FALSE
skipping to change at page 20, line 39 skipping to change at page 20, line 39
the message retransmissions are spaced in time by a small random the message retransmissions are spaced in time by a small random
interval. interval.
3.5.2.1. Bootstrap Election 3.5.2.1. Bootstrap Election
Initially when no DF has been elected, routers finding out about a new Initially when no DF has been elected, routers finding out about a new
RP start participating in the election by sending Offer messages. Offer RP start participating in the election by sending Offer messages. Offer
messages include the router's metric to reach the RP. Offers are messages include the router's metric to reach the RP. Offers are
periodically retransmitted with a period of Offer_Interval. periodically retransmitted with a period of Offer_Interval.
If a router hears a better offer from a neighbor, it stops participating If a router hears a better offer than its own from a neighbor, it stops
in the election for a period of Election_Robustness * Offer_Interval. If participating in the election for a period of Election_Robustness *
during this period no winner is elected, then the router restarts the Offer_Interval. If during this period no winner is elected, then the
election from the beginning. If a router receives an offer with worse router restarts the election from the beginning. If a router receives an
metrics, then it restarts the election from the beginning. offer with worse metrics than its own, then it restarts the election
from the beginning.
The result should be that all routers except the best candidate stop The result should be that all routers except the best candidate stop
advertising their offers. advertising their offers.
A router assumes the role of the DF after having advertised its metrics A router assumes the role of the DF after having advertised its metrics
Election_Robustness times without receiving any offer from any other Election_Robustness times without receiving any offer from any other
neighbor. At that point it transmits a Winner message which declares to
neighbor. At that point it transmits a Winner message which declares to
every other router on the link the identity of the winner and the every other router on the link the identity of the winner and the
metrics it is using. metrics it is using.
Routers hearing a winner message stop participating in the election and Routers hearing a winner message stop participating in the election and
record the identity and metrics of the winner. If the local metrics are record the identity and metrics of the winner. If the local metrics are
better than those of the winner then the router records the identity of better than those of the winner then the router records the identity of
the winner but reinitiates the election. the winner but reinitiates the election.
3.5.2.2. Loser Metric Changes 3.5.2.2. Loser Metric Changes
Whenever the unicast metric to a RP changes for a non-DF router to a Whenever the unicast metric to a RP changes for a non-DF router to a
value that is better than that previously advertised by the acting DF, value that is better than that previously advertised by the acting DF,
the router with the new metric should take action to eventually assume the router with the new metric should take action to eventually assume
forwarding responsibility. After the metric change is detected, the new forwarding responsibility. After the metric change is detected, the non-
candidate restarts participating in the election. If no response is DF router with the now better metric restarts the DF election process by
received after Election_Robustness retransmissions, the router assumes sending Offer messages with this new metric. If no response is received
the role of the DF following the usual Winner announcement procedure. after Election_Robustness retransmissions, the router assumes the role
of the DF following the usual Winner announcement procedure.
Upon receipt of an offer that is worse than its current metric, the DF Upon receipt of an offer that is worse than its current metric, the DF
will respond with a Winner message declaring its status and advertising will respond with a Winner message declaring its status and advertising
its metric. Upon receiving this message, the originator of the Offer its metric. Upon receiving this message, the originator of the Offer
records the identity of the DF and aborts the election. records the identity of the DF and aborts the election.
Upon receipt of an offer that is better the its current metric, the DF Upon receipt of an offer that is better than its current metric, the DF
records the identity and metrics of the offering router and responds records the identity and metrics of the offering router and responds
with a Backoff message. This instructs the offering router to hold off with a Backoff message. This instructs the offering router to hold off
for a short period of time while the unicast routing stabilises. The for a short period of time while the unicast routing stabilises. The
Backoff message includes the offering router's new metric and address. Backoff message includes the offering router's new metric and address.
All routers on the link who have pending offers with metrics worse than All routers on the link who have pending offers with metrics worse than
those in the backoff message (including the original offering router) those in the backoff message (including the original offering router)
will hold further offers for a period of time defined in the Backoff will hold further offers for a period of time defined in the Backoff
message. message.
If during the Backoff_Period, a third router sends a new better offer, If during the Backoff_Period, a third router sends a new better offer,
skipping to change at page 22, line 36 skipping to change at page 22, line 36
services for that link. It therefore immediately stops being the DF and 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 restarts the election. As its path to the RP is through the link, an
infinite metric is used in the Offer message it sends. 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 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 (indicated by unicast routing) which it could use in a Pass message but
this adds unnecessary complication to the election process. this adds unnecessary complication to the election process.
3.5.2.5. Late Router Starting Up 3.5.2.5. Late Router Starting Up
A late router starting up will have no knowledge of a previous election A late router starting up after the DF election process has completed
outcome. As a result it will start advertising its metric in Offer will have no immediate knowledge of the election outcome. As a result,
messages. As soon as this happens, the Winner will respond either with a it will start advertising its metric in Offer messages. As soon as this
Winner or with a Backoff message. happens, the currently elected DF will respond with a Winner message if
its metric is better than the metric in the Offer message, or with a
Backoff message if its metric worse than the metric in the Offer
message.
3.5.2.6. Winner Dies 3.5.2.6. Winner Dies
Whenever the DF dies, a new DF has to be elected. The speed at which 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 this can be achieved depends on whether there are any downstream routers
on the link. on the link.
If there are downstream routers, typically their RPF_neighbor as 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 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 therefore notice either a change in the metric for the route to the RP
or a change in RPF_neighbor away from the DF and will restart the
restart the election by transmitting Offer messages. If according to election by transmitting Offer messages. If according to the MRIB the
the MRIB the RP is now reachable through the same link via another RP is now reachable through the same link via another upstream router,
upstream router, an infinite metric will be used in the Offer. an infinite metric will be used in the Offer.
If no downstream routers are present, the only way for other upstream 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 routers to detect a DF failure is by the timeout of the PIM neighbor
information, which will take significantly longer. information, which will take significantly longer.
3.5.3. Election Protocol Specification 3.5.3. Election Protocol Specification
This section provides the definitive specification for the DF election This section provides the definitive specification for the DF election
process. If any discrepancy exists between section 3.5.2 and this process. If any discrepancy exists between section 3.5.2 and this
section, the specification in this section is to be assumed correct. section, the specification in this section is to be assumed correct.
skipping to change at page 24, line 43 skipping to change at page 24, line 47
3.5.3.4. Election State Transitions 3.5.3.4. Election State Transitions
In the state machine presented below a router is considered to be an In the state machine presented below a router is considered to be an
acting DF if it is in the Win or Backoff states. acting DF if it is in the Win or Backoff states.
When an action of "set DF to Sender or Dest" is encountered during 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: 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 o On receipt of a Winner message set the DF to be the originator of
the message and record it's metrics. the message and record its metrics.
o On receipt of a Pass message set the DF to be the target of the o On receipt of a Pass message set the DF to be the target of the
message and record it's metrics. message and record its metrics.
o On receipt of a Backoff message set the DF to be the originator o On receipt of a Backoff message set the DF to be the originator
of the message and record it's metrics. of the message and record its metrics.
+-----------------------------------+ +-----------------------------------+
| Figures omitted from text version | | Figures omitted from text version |
+-----------------------------------+ +-----------------------------------+
Figure 3: Designated Forwarder election state-machine Figure 3: Designated Forwarder election state-machine
In tabular form, the state machine is: In tabular form, the state machine is:
+-------------++--------------------------------------------------------+ +-------------++--------------------------------------------------------+
skipping to change at page 31, line 39 skipping to change at page 31, line 39
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sender Metric Preference | | Sender Metric Preference |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Sender Metric | | Sender Metric |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Ver PIM Ver
PIM Version number is 2. PIM Version number is 2.
Type All DF-Election PIM control messages share the PIM message Type of Type All DF-Election PIM control messages share the PIM message Type of
X. 10.
Subtype Subtype
Subtypes for DF election messages are: Subtypes for DF election messages are:
1 = Offer 1 = Offer
2 = Winner 2 = Winner
3 = Backoff 3 = Backoff
4 = Pass 4 = Pass
Rsvd Set to zero on transmission. Ignored upon receipt. Rsvd Set to zero on transmission. Ignored upon receipt.
skipping to change at page 33, line 45 skipping to change at page 33, line 45
offering router used to obtain the route to RP-address. offering router used to obtain the route to RP-address.
New Winner Metric New Winner Metric
The unicast routing table metric used by the offering router to The unicast routing table metric used by the offering router to
reach the RP. The metric is in units applicable to the unicast reach the RP. The metric is in units applicable to the unicast
routing protocol used. routing protocol used.
4. RP Discovery 4. RP Discovery
Routers discover that a range of multicast group addresses operates in Routers discover that a range of multicast group addresses operates in
bi-directional and the address of the Rendezvous-Point serving the group bi-directional mode and the address of the Rendezvous-Point serving the
range through the PIM Bootsrtap mechanism. For a description of the PIM group range either through static configuration or using an automatic RP
BSR RP-distribution protocol refer to PIM-SM [9]. discovery mechanism like the PIM Bootsrtap mechanism (BSR). [12].
By default the BSR protocol advertises RPs that operate the PIM-SM 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 protocol. In order to identify a RP as operating in BIDIR mode, the
Encoded-Group Address field in Bootstrap and Candidate-RP Advertisement Encoded-Group Address field in Bootstrap and Candidate-RP Advertisement
messages has been extended by adding the BIDIR bit (B-bit) as specified messages has been extended by adding the BIDIR bit (B-bit) as specified
below: below:
0 1 2 3 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 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
skipping to change at page 36, line 36 skipping to change at page 36, line 36
every packet. This is done to determine if the packet was every packet. This is done to determine if the packet was
originated by a source which is directly connected to the router. originated by a source which is directly connected to the router.
For a connected source, source-specific state has to be created For a connected source, source-specific state has to be created
to register packets to the RP and prune the source off the shared to register packets to the RP and prune the source off the shared
tree. tree.
With Bidir PIM directly connected sources do not need any special 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, handling. The DF for the RP of the group the source is sending to,
seamlessly picks-up and forwards upstream traveling packets. seamlessly picks-up and forwards upstream traveling packets.
6. Authors' Addresses 6. Todo list...
o Update legacy interoperability section to remove dependency on 10.
o Incorporate BSR mods into BSR spec.
o In the state machine, perhaps add an arc from NI to NI, labelled
"(*,G) Join but not DF" just to make it really clear.
7. Authors' Addresses
Mark Handley Mark Handley
ACIRI/ICSI ACIRI/ICSI
1947 Center St, Suite 600 1947 Center St, Suite 600
Berkeley, CA 94708 Berkeley, CA 94708
mjh@aciri.org mjh@aciri.org
Isidor Kouvelas Isidor Kouvelas
Cisco Systems Cisco Systems
kouvelas@cisco.com kouvelas@cisco.com
Tony Speakman
Cisco Systems
speakman@cisco.com
Lorenzo Vicisano Lorenzo Vicisano
Cisco Systems Cisco Systems
lorenzo@cisco.com lorenzo@cisco.com
7. Acknowledgments 8. Acknowledgments
The bidir proposal in this draft is heavily based on the ideas and text The bidir proposal in this draft is heavily based on the ideas and text
presented by Estrin and Farinacci in [10]. The main difference between presented by Estrin and Farinacci in [10]. The main difference between
the two proposals is in the method chosen for upstream forwarding. the two proposals is in the method chosen for upstream forwarding.
We would also like to thank Deborah Estrin at ISI/USC as well as Nidhi 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 Bhaskar, Yiqun Cai, Rajitha Sumanasakera and Beau Williamson at cisco
their contributions and comments to this draft. for their contributions and comments to this draft.
8. References 9. References
[1] T. Bates , R. Chandra , D. Katz , Y. Rekhter, "Multiprotocol [1] T. Bates , R. Chandra , D. Katz , Y. Rekhter, "Multiprotocol
Extensions for BGP-4", RFC 2283 Extensions for BGP-4", RFC 2283
[2] S.E. Deering, "Host extensions for IP multicasting", RFC 1112, Aug [2] S.E. Deering, "Host extensions for IP multicasting", RFC 1112, Aug
1989. 1989.
[3] W. Fenner, "Internet Group Management Protocol, Version 2", RFC [3] W. Fenner, "Internet Group Management Protocol, Version 2", RFC
2236. 2236.
skipping to change at page 39, line 5 skipping to change at page 38, line 28
Independent Multicast - Sparse Mode (PIM-SM): Protocol Independent Multicast - Sparse Mode (PIM-SM): Protocol
Specification (Revised)", Work In Progress, <draft-ietf-pim-sm- Specification (Revised)", Work In Progress, <draft-ietf-pim-sm-
v2-new-01.txt>, 2000. v2-new-01.txt>, 2000.
[10] D. Estrin, D. Farinacci, "Bi-directional Shared Trees in PIM-SM", [10] D. Estrin, D. Farinacci, "Bi-directional Shared Trees in PIM-SM",
Work In Progress, <draft-farinacci-bidir-pim-01.txt>, May 1999. Work In Progress, <draft-farinacci-bidir-pim-01.txt>, May 1999.
[11] D. Estrin et al, "Protocol Independent Multicast-Sparse Mode (PIM- [11] D. Estrin et al, "Protocol Independent Multicast-Sparse Mode (PIM-
SM): Protocol Specification", RFC 2362, Nov 1999. SM): Protocol Specification", RFC 2362, Nov 1999.
9. Index [12] W. Fenner, M. Handley, H. Holbrook, I. Kouvelas, "Bootstrap Router
DownstreamJPState(G,I) . . . . . . . . . . . . . . . . . . . . . . . 12 (BSR) Mechanism for PIM Sparse Mode", draft-ietf-pim-sm-bsr-00.txt,
work in progress.
10. Index
DownstreamJPState(G,I) . . . . . . . . . . . . . . . . . . . . . . . 11
ET(G,I). . . . . . . . . . . . . . . . . . . . . . . . . . . . .10,14,29 ET(G,I). . . . . . . . . . . . . . . . . . . . . . . . . . . . .10,14,29
ET(RP,I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 ET(RP,I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
I_am_DF(RP,I). . . . . . . . . . . . . . . . . . . . . . . . . .11,13,16 I_am_DF(RP,I). . . . . . . . . . . . . . . . . . . . . . . . . .11,13,15
J/P_HoldTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 J/P_HoldTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
J/P_Override_Interval. . . . . . . . . . . . . . . . . . . . . . . 16,30 J/P_Override_Interval. . . . . . . . . . . . . . . . . . . . . . . 16,30
JoinDesired(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 JoinDesired(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
joins(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 joins(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
JT(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 JT(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
JT(G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10,30 JT(G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10,30
local_receiver_include(G,I). . . . . . . . . . . . . . . . . . . . . 11 local_receiver_include(G,I). . . . . . . . . . . . . . . . . . . . . 11
NLT(N,I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 NLT(N,I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Offer_Period . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Offer_Period . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
olist(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . .11,13,18 olist(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . .11,13,18
OT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 OT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
pim_include(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 pim_include(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
PPT(G,I) . . . . . . . . . . . . . . . . . . . . . . . . . . . .10,14,30 PPT(G,I) . . . . . . . . . . . . . . . . . . . . . . . . . . . .10,14,30
RPF_interface(RP). . . . . . . . . . . . . . . . . . . . . . . . . 11,13 RPF_interface(RP). . . . . . . . . . . . . . . . . . . . . . . . . 11,13
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/