draft-ietf-pim-sm-v2-new-12.txt   rfc4601.txt 
Internet Engineering Task Force PIM WG
INTERNET-DRAFT Bill Fenner/AT&T Network Working Group B. Fenner
draft-ietf-pim-sm-v2-new-12.txt Mark Handley/UCL Request for Comments: 4601 AT&T Labs - Research
Hugh Holbrook/Arastra Obsoletes: 2362 M. Handley
Obsoletes (if approved): RFC2362 Isidor Kouvelas/Cisco Category: Standards Track UCL
20 March 2006 H. Holbrook
Expires: September 2006 Arastra
I. Kouvelas
Cisco
August 2006
Protocol Independent Multicast - Sparse Mode (PIM-SM): Protocol Independent Multicast - Sparse Mode (PIM-SM):
Protocol Specification (Revised) Protocol Specification (Revised)
Status of this Document Status of This Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware have
been or will be disclosed, and any of which he or she becomes aware will
be disclosed, in accordance with Section 6 of BCP 79.
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 This document specifies an Internet standards track protocol for the
and may be updated, replaced, or obsoleted by other documents at any Internet community, and requests discussion and suggestions for
time. It is inappropriate to use Internet-Drafts as reference material improvements. Please refer to the current edition of the "Internet
or to cite them other than as "work in progress." Official Protocol Standards" (STD 1) for the standardization state
and status of this protocol. Distribution of this memo is unlimited.
The list of current Internet-Drafts can be accessed at Copyright Notice
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at Copyright (C) The Internet Society (2006).
http://www.ietf.org/shadow.html.
This document is a product of the IETF PIM WG. Comments should be Abstract
addressed to the authors, or the mailing list at pim@ietf.org.
Abstract This document specifies Protocol Independent Multicast - Sparse Mode
(PIM-SM). PIM-SM is a multicast routing protocol that can use the
underlying unicast routing information base or a separate multicast-
capable routing information base. It builds unidirectional shared
trees rooted at a Rendezvous Point (RP) per group, and optionally
creates shortest-path trees per source.
This document specifies Protocol Independent Multicast - This document obsoletes RFC 2362, an Experimental version of PIM-SM.
Sparse Mode (PIM-SM). PIM-SM is a multicast routing protocol
that can use the underlying unicast routing information base
or a separate multicast-capable routing information base. It
builds unidirectional shared trees rooted at a Rendezvous
Point (RP) per group, and optionally creates shortest-path
trees per source.
This document obsoletes RFC 2362, an Experimental version of Table of Contents
PIM-SM.
Table of Contents 1. Introduction ....................................................5
2. Terminology .....................................................5
2.1. Definitions ................................................5
2.2. Pseudocode Notation ........................................7
3. PIM-SM Protocol Overview ........................................7
3.1. Phase One: RP Tree .........................................8
3.2. Phase Two: Register-Stop ...................................8
3.3. Phase Three: Shortest-Path Tree ............................9
3.4. Source-Specific Joins .....................................10
3.5. Source-Specific Prunes ....................................11
3.6. Multi-Access Transit LANs .................................11
3.7. RP Discovery ..............................................12
4. Protocol Specification .........................................12
4.1. PIM Protocol State ........................................13
4.1.1. General Purpose State ..............................14
4.1.2. (*,*,RP) State .....................................15
4.1.3. (*,G) State ........................................16
4.1.4. (S,G) State ........................................17
4.1.5. (S,G,rpt) State ....................................20
4.1.6. State Summarization Macros .........................21
4.2. Data Packet Forwarding Rules ..............................26
4.2.1. Last-Hop Switchover to the SPT .....................28
4.2.2. Setting and Clearing the (S,G) SPTbit ..............29
4.3. Designated Routers (DR) and Hello Messages ................30
4.3.1. Sending Hello Messages .............................30
4.3.2. DR Election ........................................32
4.3.3. Reducing Prune Propagation Delay on LANs ...........34
4.3.4. Maintaining Secondary Address Lists ................37
4.4. PIM Register Messages .....................................38
4.4.1. Sending Register Messages from the DR ..............38
4.4.2. Receiving Register Messages at the RP ..............43
4.5. PIM Join/Prune Messages ...................................45
4.5.1. Receiving (*,*,RP) Join/Prune Messages .............45
4.5.2. Receiving (*,G) Join/Prune Messages ................49
4.5.3. Receiving (S,G) Join/Prune Messages ................53
4.5.4. Receiving (S,G,rpt) Join/Prune Messages ............56
4.5.5. Sending (*,*,RP) Join/Prune Messages ...............62
4.5.6. Sending (*,G) Join/Prune Messages ..................66
4.5.7. Sending (S,G) Join/Prune Messages ..................71
4.5.8. (S,G,rpt) Periodic Messages ........................76
4.5.9. State Machine for (S,G,rpt) Triggered Messages .....77
4.5.10. Background: (*,*,RP) and (S,G,rpt) Interaction ....82
4.6. PIM Assert Messages .......................................83
4.6.1. (S,G) Assert Message State Machine .................83
4.6.2. (*,G) Assert Message State Machine .................91
4.6.3. Assert Metrics .....................................98
4.6.4. AssertCancel Messages ..............................99
4.6.5. Assert State Macros ...............................100
4.7. PIM Bootstrap and RP Discovery ...........................103
4.7.1. Group-to-RP Mapping ...............................104
4.7.2. Hash Function .....................................105
4.8. Source-Specific Multicast ................................106
4.8.1. Protocol Modifications for SSM Destination
Addresses .........................................106
4.8.2. PIM-SSM-Only Routers ..............................107
4.9. PIM Packet Formats .......................................108
4.9.1. Encoded Source and Group Address Formats ..........110
4.9.2. Hello Message Format ..............................113
4.9.3. Register Message Format ...........................116
4.9.4. Register-Stop Message Format ......................119
4.9.5. Join/Prune Message Format .........................119
4.9.5.1. Group Set Source List Rules ..............122
4.9.5.2. Group Set Fragmentation ..................126
4.9.6. Assert Message Format .............................126
4.10. PIM Timers ..............................................128
4.11. Timer Values ............................................129
5. IANA Considerations ...........................................135
5.1. PIM Address Family .......................................135
5.2. PIM Hello Options ........................................136
6. Security Considerations .......................................136
6.1. Attacks Based on Forged Messages .........................136
6.1.1. Forged Link-Local Messages ........................136
6.1.2. Forged Unicast Messages ...........................137
6.2. Non-Cryptographic Authentication Mechanisms ..............137
6.3. Authentication Using IPsec ...............................138
6.3.1. Protecting Link-Local Multicast Messages ..........138
6.3.2. Protecting Unicast Messages .......................139
6.3.2.1. Register Messages ........................139
6.3.2.2. Register-Stop Messages ...................139
6.4. Denial-of-Service Attacks ................................140
7. Acknowledgements ..............................................140
8. Normative References ..........................................141
9. Informative References ........................................141
Appendix A. PIM Multicast Border Router Behavior .................143
A.1. Sources External to the PIM-SM Domain ....................143
A.2. Sources Internal to the PIM-SM Domain ...................144
Appendix B. Index ................................................146
1. Introduction. . . . . . . . . . . . . . . . . . . . . . 6 List of Figures
2. Terminology . . . . . . . . . . . . . . . . . . . . . . 6
2.1. Definitions. . . . . . . . . . . . . . . . . . . . . 6
2.2. Pseudocode Notation. . . . . . . . . . . . . . . . . 7
3. PIM-SM Protocol Overview. . . . . . . . . . . . . . . . 8
4. Protocol Specification. . . . . . . . . . . . . . . . . 13
4.1. PIM Protocol State . . . . . . . . . . . . . . . . . 14
4.1.1. General Purpose State . . . . . . . . . . . . . . 15
4.1.2. (*,*,RP) State. . . . . . . . . . . . . . . . . . 15
4.1.3. (*,G) State . . . . . . . . . . . . . . . . . . . 16
4.1.4. (S,G) State . . . . . . . . . . . . . . . . . . . 18
4.1.5. (S,G,rpt) State . . . . . . . . . . . . . . . . . 20
4.1.6. State Summarization Macros. . . . . . . . . . . . 21
4.2. Data Packet Forwarding Rules . . . . . . . . . . . . 26
4.2.1. Last-hop Switchover to the SPT. . . . . . . . . . 28
4.2.2. Setting and Clearing the (S,G) SPTbit . . . . . . 29
4.3. Designated Routers (DR) and Hello Messages . . . . . 30
4.3.1. Sending Hello Messages. . . . . . . . . . . . . . 30
4.3.2. DR Election . . . . . . . . . . . . . . . . . . . 32
4.3.3. Reducing Prune Propagation Delay on LANs. . . . . 34
4.3.4. Maintaining Secondary Address Lists . . . . . . . 37
4.4. PIM Register Messages. . . . . . . . . . . . . . . . 38
4.4.1. Sending Register Messages from the DR . . . . . . 38
4.4.2. Receiving Register Messages at the RP . . . . . . 42
4.5. PIM Join/Prune Messages. . . . . . . . . . . . . . . 44
4.5.1. Receiving (*,*,RP) Join/Prune Messages. . . . . . 45
4.5.2. Receiving (*,G) Join/Prune Messages . . . . . . . 49
4.5.3. Receiving (S,G) Join/Prune Messages . . . . . . . 52
4.5.4. Receiving (S,G,rpt) Join/Prune Messages . . . . . 55
4.5.5. Sending (*,*,RP) Join/Prune Messages. . . . . . . 61
4.5.6. Sending (*,G) Join/Prune Messages . . . . . . . . 65
4.5.7. Sending (S,G) Join/Prune Messages . . . . . . . . 70
4.5.8. (S,G,rpt) Periodic Messages . . . . . . . . . . . 75
4.5.9. State Machine for (S,G,rpt) Triggered
Messages. . . . . . . . . . . . . . . . . . . . . 76
4.5.10. Background: (*,*,RP) and (S,G,rpt)
Interaction. . . . . . . . . . . . . . . . . . . 80
4.6. PIM Assert Messages. . . . . . . . . . . . . . . . . 82
4.6.1. (S,G) Assert Message State Machine. . . . . . . . 82
4.6.2. (*,G) Assert Message State Machine. . . . . . . . 90
4.6.3. Assert Metrics. . . . . . . . . . . . . . . . . . 97
4.6.4. AssertCancel Messages . . . . . . . . . . . . . . 98
4.6.5. Assert State Macros . . . . . . . . . . . . . . . 99
4.7. PIM Bootstrap and RP Discovery . . . . . . . . . . . 102
4.7.1. Group-to-RP Mapping . . . . . . . . . . . . . . . 103
4.7.2. Hash Function . . . . . . . . . . . . . . . . . . 104
4.8. Source-Specific Multicast. . . . . . . . . . . . . . 105
4.8.1. Protocol Modifications for SSM destination
addresses . . . . . . . . . . . . . . . . . . . . 105
4.8.2. PIM-SSM-only Routers. . . . . . . . . . . . . . . 106
4.9. PIM Packet Formats . . . . . . . . . . . . . . . . . 107
4.9.1. Encoded Source and Group Address Formats. . . . . 109
4.9.2. Hello Message Format. . . . . . . . . . . . . . . 112
4.9.3. Register Message Format . . . . . . . . . . . . . 115
4.9.4. Register-Stop Message Format. . . . . . . . . . . 117
4.9.5. Join/Prune Message Format . . . . . . . . . . . . 118
4.9.5.1. Group Set Source List Rules. . . . . . . . . . 121
4.9.5.2. Group Set Fragmentation. . . . . . . . . . . . 125
4.9.6. Assert Message Format . . . . . . . . . . . . . . 125
4.10. PIM Timers. . . . . . . . . . . . . . . . . . . . . 127
4.11. Timer Values. . . . . . . . . . . . . . . . . . . . 128
5. IANA Considerations . . . . . . . . . . . . . . . . . . 134
5.1. PIM Address Family . . . . . . . . . . . . . . . . . 134
5.2. PIM Hello Options. . . . . . . . . . . . . . . . . . 135
6. Security Considerations . . . . . . . . . . . . . . . . 135
6.1. Attacks based on forged messages . . . . . . . . . . 135
6.1.1. Forged link-local messages. . . . . . . . . . . . 135
6.1.2. Forged unicast messages . . . . . . . . . . . . . 136
6.2. Non-cryptographic Authentication Mechanisms. . . . . 136
6.3. Authentication using IPsec . . . . . . . . . . . . . 137
6.3.1. Protecting link-local multicast messages. . . . . 137
6.3.2. Protecting unicast messages . . . . . . . . . . . 138
6.3.2.1. Register messages. . . . . . . . . . . . . . . 138
6.3.2.2. Register-Stop messages . . . . . . . . . . . . 138
6.4. Denial of Service Attacks. . . . . . . . . . . . . . 139
7. Authors' Addresses. . . . . . . . . . . . . . . . . . . 139
8. Acknowledgments . . . . . . . . . . . . . . . . . . . . 140
9. Normative References. . . . . . . . . . . . . . . . . . 140
10. Informative References . . . . . . . . . . . . . . . . 141
11. Appendix A: PIM Multicast Border Router
Behavior . . . . . . . . . . . . . . . . . . . . . . . 142
11.1. Sources External to the PIM-SM Domain . . . . . . . 142
11.2. Sources Internal to the PIM-SM Domain . . . . . . . 143
12. Index. . . . . . . . . . . . . . . . . . . . . . . . . 145
13. Full Copyright Statement . . . . . . . . . . . . . . . 148
List of Figures
Figure 1. Per-(S,G) register state machine at a DR . . . . 38 Figure 1. Per-(S,G) register state machine at a DR ................38
Figure 2. Downstream per-interface (*,*,RP) state Figure 2. Downstream per-interface (*,*,RP) state machine .........46
machine. . . . . . . . . . . . . . . . . . . . . 46 Figure 3. Downstream per-interface (*,G) state machine ............50
Figure 3. Downstream per-interface (*,G) state Figure 4. Downstream per-interface (S,G) state machine ............53
machine. . . . . . . . . . . . . . . . . . . . . 49 Figure 5. Downstream per-interface (S,G,rpt) state machine ........57
Figure 4. Downstream per-interface (S,G) state Figure 6. Upstream (*,*,RP) state machine .........................62
machine. . . . . . . . . . . . . . . . . . . . . 53 Figure 7. Upstream (*,G) state machine ............................67
Figure 5. Downstream per-interface (S,G,rpt) state Figure 8. Upstream (S,G) state machine ............................71
machine. . . . . . . . . . . . . . . . . . . . . 56 Figure 9. Upstream (S,G,rpt) state machine for triggered
Figure 6. Upstream (*,*,RP) state machine. . . . . . . . . 61 messages ................................................77
Figure 7. Upstream (*,G) state machine . . . . . . . . . . 66 Figure 10. Per-interface (S,G) Assert State machine ...............84
Figure 8. Upstream (S,G) state machine . . . . . . . . . . 71 Figure 11. Per-interface (*,G) Assert State machine ...............92
Figure 9. Upstream (S,G,rpt) state machine for
triggered messages . . . . . . . . . . . . . . . 76
Figure 10. Per-interface (S,G) Assert State
machine . . . . . . . . . . . . . . . . . . . . 83
Figure 11. Per-interface (*,G) Assert State
machine . . . . . . . . . . . . . . . . . . . . 91
1. Introduction 1. Introduction
This document specifies a protocol for efficiently routing multicast This document specifies a protocol for efficiently routing multicast
groups that may span wide-area (and inter-domain) internets. This groups that may span wide-area (and inter-domain) internets. This
protocol is called Protocol Independent Multicast - Sparse Mode (PIM-SM) protocol is called Protocol Independent Multicast - Sparse Mode
because, although it may use the underlying unicast routing to provide (PIM-SM) because, although it may use the underlying unicast routing
reverse-path information for multicast tree building, it is not to provide reverse-path information for multicast tree building, it
dependent on any particular unicast routing protocol. is not dependent on any particular unicast routing protocol.
PIM-SM version 2 was originally specified in RFC 2117, and revised in PIM-SM version 2 was originally specified in RFC 2117 and was revised
RFC 2362, both Experimental RFCs. This document is intended to obsolete in RFC 2362, both Experimental RFCs. This document is intended to
RFC 2362, to correct a number of deficiencies that have been identified obsolete RFC 2362, to correct a number of deficiencies that have been
with the way PIM-SM was previously specified, and to bring PIM-SM onto identified with the way PIM-SM was previously specified, and to bring
the IETF Standards Track. As far as possible, this document specifies PIM-SM onto the IETF Standards Track. As far as possible, this
the same protocol as RFC 2362, and only diverges from the behavior document specifies the same protocol as RFC 2362 and only diverges
intended by RFC 2362 when the previously specified behavior was clearly from the behavior intended by RFC 2362 when the previously specified
incorrect. Routers implemented according to the specification in this behavior was clearly incorrect. Routers implemented according to the
document will be able to successfully interoperate with routers specification in this document will be able to interoperate
implemented according to RFC 2362. successfully with routers implemented according to RFC 2362.
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 NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY",
"OPTIONAL" are to be interpreted as described in RFC 2119 [1] and and "OPTIONAL" are to be interpreted as described in RFC 2119 [1] and
indicate requirement levels for compliant PIM-SM implementations. indicate requirement levels for compliant PIM-SM implementations.
2.1. Definitions 2.1. Definitions
The following terms have special significance for PIM-SM: The following terms have special significance for PIM-SM:
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
of the non-source-specific distribution tree for a multicast root of the non-source-specific distribution tree for a
group. Join messages from receivers for a group are sent towards multicast group. Join messages from receivers for a group are
the RP, and data from senders is sent to the RP so that receivers sent towards the RP, and data from senders is sent to the RP so
can discover who the senders are, and start to receive traffic that receivers can discover who the senders are and start to
destined for the group. receive traffic destined for the group.
Designated Router (DR): Designated Router (DR):
A shared-media LAN like Ethernet may have multiple PIM-SM routers A shared-media LAN like Ethernet may have multiple PIM-SM
connected to it. A single one of these routers, the DR, will act routers connected to it. A single one of these routers, the
on behalf of directly connected hosts with respect to the PIM-SM DR, will act on behalf of directly connected hosts with respect
protocol. A single DR is elected per interface (LAN or otherwise) to the PIM-SM protocol. A single DR is elected per interface
using a simple election process. (LAN or otherwise) using a simple election process.
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 Multiprotocol BGP
multicast-specific topology information. In PIM-SM, the MRIB is (MBGP) that carry multicast-specific topology information. In
used to decide where to send Join/Prune messages. A secondary PIM-SM, the MRIB is used to decide where to send Join/Prune
function of the MRIB is to provide routing metrics for destination messages. A secondary function of the MRIB is to provide
addresses; these metrics are used when sending and processing routing metrics for destination addresses; these metrics are
Assert messages. used when sending and processing Assert messages.
RPF Neighbor RPF Neighbor
RPF stands for "Reverse Path Forwarding". The RPF Neighbor of a RPF stands for "Reverse Path Forwarding". The RPF Neighbor of
router with respect to an address is the neighbor that the MRIB a router with respect to an address is the neighbor that the
indicates should be used to forward packets to that address. In MRIB indicates should be used to forward packets to that
the case of a PIM-SM multicast group, the RPF neighbor is the address. In the case of a PIM-SM multicast group, the RPF
router that a Join message for that group would be directed to, in neighbor is the router that a Join message for that group would
the absence of modifying Assert state. be directed to, in the absence of modifying Assert state.
TIB Tree Information Base. This is the collection of state at a PIM TIB Tree Information Base. This is the collection of state at a
router that has been created by receiving PIM Join/Prune messages, PIM router that has been created by receiving PIM Join/Prune
PIM Assert messages, and IGMP or MLD information from local hosts. messages, PIM Assert messages, and Internet Group Management
It essentially stores the state of all multicast distribution Protocol (IGMP) or Multicast Listener Discovery (MLD)
trees at that router. information from local hosts. It essentially stores the state
of all multicast distribution trees at that router.
MFIB Multicast Forwarding Information Base. The TIB holds all the MFIB Multicast Forwarding Information Base. The TIB holds all the
state that is necessary to forward multicast packets at a router. state that is necessary to forward multicast packets at a
However, although this specification defines forwarding in terms router. However, although this specification defines
of the TIB, to actually forward packets using the TIB is very forwarding in terms of the TIB, to actually forward packets
inefficient. Instead a real router implementation will normally using the TIB is very inefficient. Instead, a real router
build an efficient MFIB from the TIB state to perform forwarding. implementation will normally build an efficient MFIB from the
How this is done is implementation-specific, and is not discussed TIB state to perform forwarding. How this is done is
in this document. implementation-specific and is not discussed in this document.
Upstream Upstream
Towards the root of the tree. The root of tree may either be the Towards the root of the tree. The root of tree may be either
source or the RP depending on the context. the source or the RP, depending on the context.
Downstream Downstream
Away from the root of the tree. Away from the root of the tree.
GenID Generation Identifier, used to detect reboots. GenID Generation Identifier, used to detect reboots.
PMBR PIM Multicast Border Router, joining a PIM domain with another PMBR PIM Multicast Border Router, joining a PIM domain with another
multicast domain. multicast domain.
2.2. Pseudocode Notation 2.2. Pseudocode Notation
We use set notation in several places in this specification. We use set notation in several places in this specification.
A (+) B A (+) B is the union of two sets, A and B.
is the union of two sets A and B.
A (-) B A (-) B is the elements of set A that are not in set B.
is the elements of set A that are not in set B.
NULL NULL is the empty set or list.
is the empty set or list.
In addition, we use C-like syntax: In addition, we use C-like syntax:
= denotes assignment of a variable. = denotes assignment of a variable.
== denotes a comparison for equality. == denotes a comparison for equality.
!= denotes a comparison for inequality. != denotes a comparison for inequality.
Braces { and } are used for grouping. Braces { and } are used for grouping.
3. PIM-SM Protocol Overview 3. PIM-SM Protocol Overview
This section provides an overview of PIM-SM behavior. It is intended as This section provides an overview of PIM-SM behavior. It is intended
an introduction to how PIM-SM works, and is NOT definitive. For the as an introduction to how PIM-SM works, and it is NOT definitive.
definitive specification, see Section 4. For the definitive specification, see Section 4.
PIM relies on an underlying topology-gathering protocol to populate a PIM relies on an underlying topology-gathering protocol to populate a
routing table with routes. This routing table is called the MRIB or routing table with routes. This routing table is called the
Multicast Routing Information Base. The routes in this table may be Multicast Routing Information Base (MRIB). The routes in this table
taken directly from the unicast routing table, or it may be different may be taken directly from the unicast routing table, or they may be
and provided by a separate routing protocol such as MBGP [10]. different and provided by a separate routing protocol such as MBGP
Regardless of how it is created, the primary role of the MRIB in the PIM [10]. Regardless of how it is created, the primary role of the MRIB
protocol is to provide the next hop router along a multicast-capable in the PIM protocol is to provide the next-hop router along a
path to each destination subnet. The MRIB is used to determine the next multicast-capable path to each destination subnet. The MRIB is used
hop neighbor to which any PIM Join/Prune message is sent. Data flows to determine the next-hop neighbor to which any PIM Join/Prune
along the reverse path of the Join messages. Thus, in contrast to the message is sent. Data flows along the reverse path of the Join
unicast RIB which specifies the next hop that a data packet would take messages. Thus, in contrast to the unicast RIB, which specifies the
to get to some subnet, the MRIB gives reverse-path information, and next hop that a data packet would take to get to some subnet, the
indicates the path that a multicast data packet would take from its MRIB gives reverse-path information and indicates the path that a
origin subnet to the router that has the MRIB. multicast data packet would take from its origin subnet to the router
that has the MRIB.
Like all multicast routing protocols that implement the service model Like all multicast routing protocols that implement the service model
from RFC 1112 [3], PIM-SM must be able to route data packets from from RFC 1112 [3], PIM-SM must be able to route data packets from
sources to receivers without either the sources or receivers knowing a- sources to receivers without either the sources or receivers knowing
priori of the existence of the others. This is essentially done in a priori of the existence of the others. This is essentially done in
three phases, although as senders and receivers may come and go at any three phases, although as senders and receivers may come and go at
time, all three phases may occur simultaneously. any time, all three phases may occur simultaneously.
Phase One: RP Tree 3.1. Phase One: RP Tree
In phase one, a multicast receiver expresses its interest in receiving In phase one, a multicast receiver expresses its interest in
traffic destined for a multicast group. Typically it does this using receiving traffic destined for a multicast group. Typically, it does
IGMP [2] or MLD [4], but other mechanisms might also serve this purpose. this using IGMP [2] or MLD [4], but other mechanisms might also serve
One of the receiver's local routers is elected as the Designated Router this purpose. One of the receiver's local routers is elected as the
(DR) for that subnet. On receiving the receiver's expression of Designated Router (DR) for that subnet. On receiving the receiver's
interest, the DR then sends a PIM Join message towards the RP for that expression of interest, the DR then sends a PIM Join message towards
multicast group. This Join message is known as a (*,G) Join because it the RP for that multicast group. This Join message is known as a
joins group G for all sources to that group. The (*,G) Join travels (*,G) Join because it joins group G for all sources to that group.
hop-by-hop towards the RP for the group, and in each router it passes The (*,G) Join travels hop-by-hop towards the RP for the group, and
through, multicast tree state for group G is instantiated. Eventually in each router it passes through, multicast tree state for group G is
the (*,G) Join either reaches the RP, or reaches a router that already instantiated. Eventually, the (*,G) Join either reaches the RP or
has (*,G) Join state for that group. When many receivers join the reaches a router that already has (*,G) Join state for that group.
group, their Join messages converge on the RP, and form a distribution When many receivers join the group, their Join messages converge on
tree for group G that is rooted at the RP. This is known as the RP Tree the RP and form a distribution tree for group G that is rooted at the
(RPT), and is also known as the shared tree because it is shared by all RP. This is known as the RP Tree (RPT), and is also known as the
sources sending to that group. Join messages are resent periodically so shared tree because it is shared by all sources sending to that
long as the receiver remains in the group. When all receivers on a group. Join messages are resent periodically so long as the receiver
leaf-network leave the group, the DR will send a PIM (*,G) Prune message remains in the group. When all receivers on a leaf-network leave the
towards the RP for that multicast group. However if the Prune message is group, the DR will send a PIM (*,G) Prune message towards the RP for
not sent for any reason, the state will eventually time out. that multicast group. However, if the Prune message is not sent for
any reason, the state will eventually time out.
A multicast data sender just starts sending data destined for a A multicast data sender just starts sending data destined for a
multicast group. The sender's local router (DR) takes those data multicast group. The sender's local router (DR) takes those data
packets, unicast-encapsulates them, and sends them directly to the RP. packets, unicast-encapsulates them, and sends them directly to the
The RP receives these encapsulated data packets, decapsulates them, and RP. The RP receives these encapsulated data packets, decapsulates
forwards them onto the shared tree. The packets then follow the (*,G) them, and forwards them onto the shared tree. The packets then
multicast tree state in the routers on the RP Tree, being replicated follow the (*,G) multicast tree state in the routers on the RP Tree,
wherever the RP Tree branches, and eventually reaching all the receivers being replicated wherever the RP Tree branches, and eventually
for that multicast group. The process of encapsulating data packets to reaching all the receivers for that multicast group. The process of
the RP is called registering, and the encapsulation packets are known as encapsulating data packets to the RP is called registering, and the
PIM Register packets. encapsulation packets are known as PIM Register packets.
At the end of phase one, multicast traffic is flowing encapsulated to At the end of phase one, multicast traffic is flowing encapsulated to
the RP, and then natively over the RP tree to the multicast receivers. the RP, and then natively over the RP tree to the multicast
receivers.
Phase Two: Register-Stop 3.2. Phase Two: Register-Stop
Register-encapsulation of data packets is inefficient for two reasons: Register-encapsulation of data packets is inefficient for two
reasons:
o Encapsulation and decapsulation may be relatively expensive operations o Encapsulation and decapsulation may be relatively expensive
for a router to perform, depending on whether or not the router has operations for a router to perform, depending on whether or not the
appropriate hardware for these tasks. router has appropriate hardware for these tasks.
o Traveling all the way to the RP, and then back down the shared tree o Traveling all the way to the RP, and then back down the shared tree
may entail the packets traveling a relatively long distance to reach may result in the packets traveling a relatively long distance to
receivers that are close to the sender. For some applications, this reach receivers that are close to the sender. For some
increased latency or bandwidth consumption is undesirable. applications, this increased latency or bandwidth consumption is
undesirable.
Although Register-encapsulation may continue indefinitely, for these Although Register-encapsulation may continue indefinitely, for these
reasons, the RP will normally choose to switch to native forwarding. To reasons, the RP will normally choose to switch to native forwarding.
do this, when the RP receives a register-encapsulated data packet from To do this, when the RP receives a register-encapsulated data packet
source S on group G, it will normally initiate an (S,G) source-specific from source S on group G, it will normally initiate an (S,G) source-
Join towards S. This Join message travels hop-by-hop towards S, specific Join towards S. This Join message travels hop-by-hop
instantiating (S,G) multicast tree state in the routers along the path. towards S, instantiating (S,G) multicast tree state in the routers
(S,G) multicast tree state is used only to forward packets for group G along the path. (S,G) multicast tree state is used only to forward
if those packets come from source S. Eventually the Join message packets for group G if those packets come from source S. Eventually
reaches S's subnet or a router that already has (S,G) multicast tree the Join message reaches S's subnet or a router that already has
state, and then packets from S start to flow following the (S,G) tree (S,G) multicast tree state, and then packets from S start to flow
state towards the RP. These data packets may also reach routers with following the (S,G) tree state towards the RP. These data packets
(*,G) state along the path towards the RP - if so, they can short-cut may also reach routers with (*,G) state along the path towards the
onto the RP tree at this point. RP; if they do, they can shortcut onto the RP tree at this point.
While the RP is in the process of joining the source-specific tree for While the RP is in the process of joining the source-specific tree
S, the data packets will continue being encapsulated to the RP. When for S, the data packets will continue being encapsulated to the RP.
packets from S also start to arrive natively at the the RP, the RP will When packets from S also start to arrive natively at the RP, the RP
be receiving two copies of each of these packets. At this point, the RP will be receiving two copies of each of these packets. At this
starts to discard the encapsulated copy of these packets, and it sends a point, the RP starts to discard the encapsulated copy of these
Register-Stop message back to S's DR to prevent the DR unnecessarily packets, and it sends a Register-Stop message back to S's DR to
encapsulating the packets. prevent the DR from unnecessarily encapsulating the packets.
At the end of phase 2, traffic will be flowing natively from S along a At the end of phase 2, traffic will be flowing natively from S along
source-specific tree to the RP, and from there along the shared tree to a source-specific tree to the RP, and from there along the shared
the receivers. Where the two trees intersect, traffic may transfer from tree to the receivers. Where the two trees intersect, traffic may
the source-specific tree to the RP tree, and so avoid taking a long transfer from the source-specific tree to the RP tree and thus avoid
detour via the RP. taking a long detour via the RP.
It should be noted that a sender may start sending before or after a Note that a sender may start sending before or after a receiver joins
receiver joins the group, and thus phase two may happen before the the group, and thus phase two may happen before the shared tree to
shared tree to the receiver is built. the receiver is built.
Phase 3: Shortest-Path Tree 3.3. Phase Three: Shortest-Path Tree
Although having the RP join back towards the source removes the Although having the RP join back towards the source removes the
encapsulation overhead, it does not completely optimize the forwarding encapsulation overhead, it does not completely optimize the
paths. For many receivers the route via the RP may involve a forwarding paths. For many receivers, the route via the RP may
significant detour when compared with the shortest path from the source involve a significant detour when compared with the shortest path
to the receiver. from the source to the receiver.
To obtain lower latencies or more efficient bandwidth utilization, a To obtain lower latencies or more efficient bandwidth utilization, a
router on the receiver's LAN, typically the DR, may optionally initiate router on the receiver's LAN, typically the DR, may optionally
a transfer from the shared tree to a source-specific shortest-path tree initiate a transfer from the shared tree to a source-specific
(SPT). To do this, it issues an (S,G) Join towards S. This instantiates shortest-path tree (SPT). To do this, it issues an (S,G) Join
state in the routers along the path to S. Eventually this join either towards S. This instantiates state in the routers along the path to
reaches S's subnet, or reaches a router that already has (S,G) state. S. Eventually, this join either reaches S's subnet or reaches a
When this happens, data packets from S start to flow following the (S,G) router that already has (S,G) state. When this happens, data packets
state until they reach the receiver. from S start to flow following the (S,G) state until they reach the
receiver.
At this point the receiver (or a router upstream of the receiver) will At this point, the receiver (or a router upstream of the receiver)
be receiving two copies of the data - one from the SPT and one from the will be receiving two copies of the data: one from the SPT and one
RPT. When the first traffic starts to arrive from the SPT, the DR or from the RPT. When the first traffic starts to arrive from the SPT,
upstream router starts to drop the packets for G from S that arrive via the DR or upstream router starts to drop the packets for G from S
the RP tree. In addition, it sends an (S,G) Prune message towards the that arrive via the RP tree. In addition, it sends an (S,G) Prune
RP. This is known as an (S,G,rpt) Prune. The Prune message travels message towards the RP. This is known as an (S,G,rpt) Prune. The
hop-by-hop, instantiating state along the path towards the RP indicating Prune message travels hop-by-hop, instantiating state along the path
that traffic from S for G should NOT be forwarded in this direction. towards the RP indicating that traffic from S for G should NOT be
The prune is propagated until it reaches the RP or a router that still forwarded in this direction. The prune is propagated until it
needs the traffic from S for other receivers. reaches the RP or a router that still needs the traffic from S for
other receivers.
By now, the receiver will be receiving traffic from S along the By now, the receiver will be receiving traffic from S along the
shortest-path tree between the receiver and S. In addition, the RP is shortest-path tree between the receiver and S. In addition, the RP
receiving the traffic from S, but this traffic is no longer reaching the is receiving the traffic from S, but this traffic is no longer
receiver along the RP tree. As far as the receiver is concerned, this reaching the receiver along the RP tree. As far as the receiver is
is the final distribution tree. concerned, this is the final distribution tree.
Source-specific Joins 3.4. Source-Specific Joins
IGMPv3 permits a receiver to join a group and specify that it only wants IGMPv3 permits a receiver to join a group and specify that it only
to receive traffic for a group if that traffic comes from a particular wants to receive traffic for a group if that traffic comes from a
source. If a receiver does this, and no other receiver on the LAN particular source. If a receiver does this, and no other receiver on
requires all the traffic for the group, then the DR may omit performing the LAN requires all the traffic for the group, then the DR may omit
a (*,G) join to set up the shared tree, and instead issue a source- performing a (*,G) join to set up the shared tree, and instead issue
specific (S,G) join only. a source-specific (S,G) join only.
The range of multicast addresses from 232.0.0.0 to 232.255.255.255 is The range of multicast addresses from 232.0.0.0 to 232.255.255.255 is
currently set aside for source-specific multicast in IPv4. For groups currently set aside for source-specific multicast in IPv4. For
in this range, receivers should only issue source-specific IGMPv3 joins. groups in this range, receivers should only issue source-specific
If a PIM router receives a non-source-specific join for a group in this IGMPv3 joins. If a PIM router receives a non-source-specific join
range, it should ignore it, as described in Section 4.8. for a group in this range, it should ignore it, as described in
Section 4.8.
Source-specific Prunes 3.5. Source-Specific Prunes
IGMPv3 also permits a receiver to join a group and specify that it only IGMPv3 also permits a receiver to join a group and to specify that it
wants to receive traffic for a group if that traffic does not come from only wants to receive traffic for a group if that traffic does not
a specific source or sources. In this case, the DR will perform a (*,G) come from a specific source or sources. In this case, the DR will
join as normal, but may combine this with an (S,G,rpt) prune for each of perform a (*,G) join as normal, but may combine this with an
the sources the receiver does not wish to receive. (S,G,rpt) prune for each of the sources the receiver does not wish to
receive.
Multi-access Transit LANs 3.6. Multi-Access Transit LANs
The overview so far has concerned itself with point-to-point transit The overview so far has concerned itself with point-to-point transit
links. However, using multi-access LANs such as Ethernet for transit is links. However, using multi-access LANs such as Ethernet for transit
not uncommon. This can cause complications for three reasons: is not uncommon. This can cause complications for three reasons:
o Two or more routers on the LAN may issue (*,G) Joins to different o Two or more routers on the LAN may issue (*,G) Joins to different
upstream routers on the LAN because they have inconsistent MRIB upstream routers on the LAN because they have inconsistent MRIB
entries regarding how to reach the RP. Both paths on the RP tree will entries regarding how to reach the RP. Both paths on the RP tree
be set up, causing two copies of all the shared tree traffic to appear will be set up, causing two copies of all the shared tree traffic
on the LAN. to appear on the LAN.
o Two or more routers on the LAN may issue (S,G) Joins to different o Two or more routers on the LAN may issue (S,G) Joins to different
upstream routers on the LAN because they have inconsistent MRIB upstream routers on the LAN because they have inconsistent MRIB
entries regarding how to reach source S. Both paths on the source- entries regarding how to reach source S. Both paths on the source-
specific tree will be set up, causing two copies of all the traffic specific tree will be set up, causing two copies of all the traffic
from S to appear on the LAN. from S to appear on the LAN.
o A router on the LAN may issue a (*,G) Join to one upstream router on o A router on the LAN may issue a (*,G) Join to one upstream router
the LAN, and another router on the LAN may issue an (S,G) Join to a on the LAN, and another router on the LAN may issue an (S,G) Join
different upstream router on the same LAN. Traffic from S may reach to a different upstream router on the same LAN. Traffic from S may
the LAN over both the RPT and the SPT. If the receiver behind the reach the LAN over both the RPT and the SPT. If the receiver
downstream (*,G) router doesn't issue an (S,G,rpt) prune, then this behind the downstream (*,G) router doesn't issue an (S,G,rpt)
condition would persist. prune, then this condition would persist.
All of these problems are caused by there being more than one upstream All of these problems are caused by there being more than one
router with join state for the group or source-group pair. PIM does not upstream router with join state for the group or source-group pair.
prevent such duplicate joins from occurring - instead when duplicate PIM does not prevent such duplicate joins from occurring; instead,
data packets appear on the LAN from different routers, these routers when duplicate data packets appear on the LAN from different routers,
notice this, and then elect a single forwarder. This election is these routers notice this and then elect a single forwarder. This
performed using PIM Assert messages, which resolve the problem in favor election is performed using PIM Assert messages, which resolve the
of the upstream router which has (S,G) state, or if neither or both problem in favor of the upstream router that has (S,G) state; or, if
router has (S,G) state, then in favor of the router with the best metric neither or both router has (S,G) state, then the problem is resolved
to the RP for RP trees, or the best metric to the source to source- in favor of the router with the best metric to the RP for RP trees,
specific trees. or the best metric to the source to source-specific trees.
These Assert messages are also received by the downstream routers on the These Assert messages are also received by the downstream routers on
LAN, and these cause subsequent Join messages to be sent to the upstream the LAN, and these cause subsequent Join messages to be sent to the
router that won the Assert. upstream router that won the Assert.
RP Discovery 3.7. RP Discovery
PIM-SM routers need to know the address of the RP for each group for PIM-SM routers need to know the address of the RP for each group for
which they have (*,G) state. This address is obtained either which they have (*,G) state. This address is obtained automatically
automatically (e.g., embedded-RP), through a bootstrap mechanism or (e.g., embedded-RP), through a bootstrap mechanism, or through static
through static configuration. configuration.
One dynamic way to do this is to use the Bootstrap Router (BSR) One dynamic way to do this is to use the Bootstrap Router (BSR)
mechanism [11]. One router in each PIM domain is elected the Bootstrap mechanism [11]. One router in each PIM domain is elected the
Router through a simple election process. All the routers in the domain Bootstrap Router through a simple election process. All the routers
that are configured to be candidates to be RPs periodically unicast in the domain that are configured to be candidates to be RPs
their candidacy to the BSR. From the candidates, the BSR picks an RP- periodically unicast their candidacy to the BSR. From the
set, and periodically announces this set in a Bootstrap message. candidates, the BSR picks an RP-set, and periodically announces this
Bootstrap messages are flooded hop-by-hop throughout the domain until set in a Bootstrap message. Bootstrap messages are flooded hop-by-
all routers in the domain know the RP-Set. hop throughout the domain until all routers in the domain know the
RP-Set.
To map a group to an RP, a router hashes the group address into the RP- To map a group to an RP, a router hashes the group address into the
set using an order-preserving hash function (one that minimizes changes RP-set using an order-preserving hash function (one that minimizes
if the RP-Set changes). The resulting RP is the one that it uses as the changes if the RP-Set changes). The resulting RP is the one that it
RP for that group. uses as the RP for that group.
4. Protocol Specification 4. Protocol Specification
The specification of PIM-SM is broken into several parts: The specification of PIM-SM is broken into several parts:
o Section 4.1 details the protocol state stored. o Section 4.1 details the protocol state stored.
o Section 4.2 specifies the data packet forwarding rules. o Section 4.2 specifies the data packet forwarding rules.
o Section 4.3. specifies Designated Router (DR) election and the rules o Section 4.3 specifies Designated Router (DR) election and the rules
for sending and processing Hello messages. for sending and processing Hello messages.
o Section 4.4 specifies the PIM Register generation and processing o Section 4.4 specifies the PIM Register generation and processing
rules. rules.
o Section 4.5 specifies the PIM Join/Prune generation and processing o Section 4.5 specifies the PIM Join/Prune generation and processing
rules. rules.
o Section 4.6 specifies the PIM Assert generation and processing rules. o Section 4.6 specifies the PIM Assert generation and processing
rules.
o Section 4.7 specifies the RP discovery mechanisms. o Section 4.7 specifies the RP discovery mechanisms.
o The subset of PIM required to support Source-Specific Multicast, PIM- o The subset of PIM required to support Source-Specific Multicast,
SSM, is described in Section 4.8. PIM-SSM, is described in Section 4.8.
o PIM packet formats are specified in Section 4.9. o PIM packet formats are specified in Section 4.9.
o A summary of PIM-SM timers and their default values is given in o A summary of PIM-SM timers and their default values is given in
Section 4.10. Section 4.10.
o Appendix A in Section 11 specifies the PIM Multicast Border Router o Appendix A specifies the PIM Multicast Border Router behavior.
behavior.
4.1. PIM Protocol State 4.1. PIM Protocol State
This section specifies all the protocol state that a PIM implementation This section specifies all the protocol state that a PIM
should maintain in order to function correctly. We term this state the implementation should maintain in order to function correctly. We
Tree Information Base or TIB, as it holds the state of all the multicast term this state the Tree Information Base (TIB), as it holds the
distribution trees at this router. In this specification we define PIM state of all the multicast distribution trees at this router. In
mechanisms in terms of the TIB. However, only a very simple this specification, we define PIM mechanisms in terms of the TIB.
implementation would actually implement packet forwarding operations in However, only a very simple implementation would actually implement
terms of this state. Most implementations will use this state to build packet forwarding operations in terms of this state. Most
a multicast forwarding table, which would then be updated when the implementations will use this state to build a multicast forwarding
relevant state in the TIB changes. 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 Although we specify precisely the state to be kept, this does not
that an implementation of PIM-SM needs to hold the state in this form. mean that an implementation of PIM-SM needs to hold the state in this
This is actually an abstract state definition, which is needed in order form. This is actually an abstract state definition, which is needed
to specify the router's behavior. A PIM-SM implementation is free to in order to specify the router's behavior. A PIM-SM implementation
hold whatever internal state it requires, and will still be conformant is free to hold whatever internal state it requires and will still be
with this specification so long as it results in the same externally conformant with this specification so long as it results in the same
visible protocol behavior as an abstract router that holds the following externally visible protocol behavior as an abstract router that holds
state. the following state.
We divide TIB state into four sections: We divide TIB state into four sections:
(*,*,RP) state (*,*,RP) state
State that maintains per-RP trees, for all groups served by a given State that maintains per-RP trees, for all groups served by a
RP. given RP.
(*,G) state (*,G) state
State that maintains the RP tree for G. State that maintains the RP tree for G.
(S,G) state (S,G) state
State that maintains a source-specific tree for source S and group State that maintains a source-specific tree for source S and
G. group G.
(S,G,rpt) state (S,G,rpt) state
State that maintains source-specific information about source S on State that maintains source-specific information about source S
the RP tree for G. For example, if a source is being received on on the RP tree for G. For example, if a source is being
the source-specific tree, it will normally have been pruned off the received on the source-specific tree, it will normally have been
RP tree. This prune state is (S,G,rpt) state. pruned off the RP tree. This prune state is (S,G,rpt) state.
The state that should be kept is described below. Of course, The state that should be kept is described below. Of course,
implementations will only maintain state when it is relevant to implementations will only maintain state when it is relevant to
forwarding operations - for example, the "NoInfo" state might be assumed forwarding operations; for example, the "NoInfo" state might be
from the lack of other state information, rather than being held assumed from the lack of other state information rather than being
explicitly. held explicitly.
4.1.1. General Purpose State 4.1.1. General Purpose State
A router holds the following non-group-specific state: A router holds the following non-group-specific state:
For each interface: For each interface:
o Effective Override Interval o Effective Override Interval
o Effective Propagation Delay o Effective Propagation Delay
o Suppression state: One of {"Enable", "Disable"} o Suppression state: One of {"Enable", "Disable"}
Neighbor State: Neighbor State:
For each neighbor: For each neighbor:
o Information from neighbor's Hello o Information from neighbor's Hello
o Neighbor's GenID. o Neighbor's GenID.
o Neighbor Liveness Timer (NLT) o Neighbor Liveness Timer (NLT)
Designated Router (DR) State: Designated Router (DR) State:
o Designated Router's IP Address o Designated Router's IP Address
o DR's DR Priority o DR's DR Priority
The Effective Override Interval, the Effective Propagation Delay and the The Effective Override Interval, the Effective Propagation Delay and
Interface suppression state are described in Section 4.3.3. Designated the Interface suppression state are described in Section 4.3.3.
Router state is described in Section 4.3. Designated Router state is described in Section 4.3.
4.1.2. (*,*,RP) State 4.1.2. (*,*,RP) State
For every RP a router keeps the following state: For every RP, a router keeps the following state:
(*,*,RP) state: (*,*,RP) state:
For each interface: For each interface:
PIM (*,*,RP) Join/Prune State: PIM (*,*,RP) Join/Prune State:
o State: One of {"NoInfo" (NI), "Join" (J), "Prune- o State: One of {"NoInfo" (NI), "Join" (J), "Prune-
Pending" (PP)} Pending" (PP)}
o Prune-Pending Timer (PPT) o Prune-Pending Timer (PPT)
o Join/Prune Expiry Timer (ET) o Join/Prune Expiry Timer (ET)
Not interface specific: Not interface specific:
Upstream (*,*,RP) Join/Prune State: Upstream (*,*,RP) Join/Prune State:
o State: One of {"NotJoined(*,*,RP)", o State: One of {"NotJoined(*,*,RP)",
"Joined(*,*,RP)"} "Joined(*,*,RP)"}
o Upstream Join/Prune Timer (JT) o Upstream Join/Prune Timer (JT)
o Last RPF Neighbor towards RP that was used o Last RPF Neighbor towards RP that was used
PIM (*,*,RP) Join/Prune state is the result of receiving PIM (*,*,RP) PIM (*,*,RP) Join/Prune state is the result of receiving PIM (*,*,RP)
Join/Prune messages on this interface, and is specified in Section Join/Prune messages on this interface and is specified in Section
4.5.1. 4.5.1.
The upstream (*,*,RP) Join/Prune State reflects the state of the The upstream (*,*,RP) Join/Prune State reflects the state of the
upstream (*,*,RP) state machine described in Section 4.5.5. upstream (*,*,RP) state machine described in Section 4.5.5.
The upstream (*,*,RP) Join/Prune Timer is used to send out periodic The upstream (*,*,RP) Join/Prune Timer is used to send out periodic
Join(*,*,RP) messages, and to override Prune(*,*,RP) messages from peers Join(*,*,RP) messages, and to override Prune(*,*,RP) messages from
on an upstream LAN interface. peers on an upstream LAN interface.
The last RPF neighbor towards the RP is stored because if the MRIB The last RPF neighbor towards the RP is stored because if the MRIB
changes then the RPF neighbor towards the RP may change. If it does so, changes, then the RPF neighbor towards the RP may change. If it does
then we need to trigger a new Join(*,*,RP) to the new upstream neighbor so, then we need to trigger a new Join(*,*,RP) to the new upstream
and a Prune(*,*,RP) to the old upstream neighbor. Similarly, if a neighbor and a Prune(*,*,RP) to the old upstream neighbor.
router detects through a changed GenID in a Hello message that the Similarly, if a router detects through a changed GenID in a Hello
upstream neighbor towards the RP has rebooted, then it should re- message that the upstream neighbor towards the RP has rebooted, then
instantiate state by sending a Join(*,*,RP). These mechanisms are it should re-instantiate state by sending a Join(*,*,RP). These
specified in Section 4.5.5. mechanisms are specified in Section 4.5.5.
4.1.3. (*,G) State 4.1.3. (*,G) State
For every group G a router keeps the following state: For every group G, a router keeps the following state:
(*,G) state: (*,G) state:
For each interface: For each interface:
Local Membership: Local Membership:
State: One of {"NoInfo", "Include"} State: One of {"NoInfo", "Include"}
PIM (*,G) Join/Prune State: PIM (*,G) Join/Prune State:
o State: One of {"NoInfo" (NI), "Join" (J), "Prune- o State: One of {"NoInfo" (NI), "Join" (J), "Prune-
Pending" (PP)} Pending" (PP)}
o Prune-Pending Timer (PPT) o Prune-Pending Timer (PPT)
o Join/Prune Expiry Timer (ET)
(*,G) Assert Winner State o Join/Prune Expiry Timer (ET)
o State: One of {"NoInfo" (NI), "I lost Assert" (L), (*,G) Assert Winner State
"I won Assert" (W)}
o Assert Timer (AT) o State: One of {"NoInfo" (NI), "I lost Assert" (L),
"I won Assert" (W)}
o Assert winner's IP Address (AssertWinner) o Assert Timer (AT)
o Assert winner's Assert Metric (AssertWinnerMetric) o Assert winner's IP Address (AssertWinner)
Not interface specific: o Assert winner's Assert Metric (AssertWinnerMetric)
Upstream (*,G) Join/Prune State: Not interface specific:
o State: One of {"NotJoined(*,G)", "Joined(*,G)"} Upstream (*,G) Join/Prune State:
o Upstream Join/Prune Timer (JT) o State: One of {"NotJoined(*,G)", "Joined(*,G)"}
o Last RP Used o Upstream Join/Prune Timer (JT)
o Last RPF Neighbor towards RP that was used o Last RP Used
Local membership is the result of the local membership mechanism (such o Last RPF Neighbor towards RP that was used
as IGMP or MLD) running on that interface. It need not be kept if this
router is not the DR on that interface unless this router won a (*,G)
assert on this interface for this group, although implementations may
optionally keep this state in case they become the DR or assert winner.
We recommend storing this information if possible, as it reduces latency
converging to stable operating conditions after a failure causing a
change of DR. This information is used by the pim_include(*,G) macro
described in Section 4.1.6.
PIM (*,G) Join/Prune state is the result of receiving PIM (*,G) Local membership is the result of the local membership mechanism
Join/Prune messages on this interface, and is specified in Section (such as IGMP or MLD) running on that interface. It need not be kept
4.5.2. The state is used by the macros that calculate the outgoing if this router is not the DR on that interface unless this router won
interface list in Section 4.1.6, and in the JoinDesired(*,G) macro a (*,G) assert on this interface for this group, although
(defined in Section 4.5.6) that is used in deciding whether a Join(*,G) implementations may optionally keep this state in case they become
should be sent upstream. the DR or assert winner. We recommend storing this information if
possible, as it reduces latency converging to stable operating
conditions after a failure causing a change of DR. This information
is used by the pim_include(*,G) macro described in Section 4.1.6.
(*,G) Assert Winner state is the result of sending or receiving (*,G) PIM (*,G) Join/Prune state is the result of receiving PIM (*,G)
Assert messages on this interface. It is specified in Section 4.6.2. Join/Prune messages on this interface and is specified in Section
4.5.2. The state is used by the macros that calculate the outgoing
interface list in Section 4.1.6, and in the JoinDesired(*,G) macro
(defined in Section 4.5.6) that is used in deciding whether a
Join(*,G) should be sent upstream.
The upstream (*,G) Join/Prune State reflects the state of the upstream (*,G) Assert Winner state is the result of sending or receiving (*,G)
(*,G) state machine described in Section 4.5.6. Assert messages on this interface. It is specified in Section 4.6.2.
The upstream (*,G) Join/Prune Timer is used to send out periodic The upstream (*,G) Join/Prune State reflects the state of the
Join(*,G) messages, and to override Prune(*,G) messages from peers on an upstream (*,G) state machine described in Section 4.5.6.
upstream LAN interface.
The last RP used must be stored because if the RP-Set changes (Section The upstream (*,G) Join/Prune Timer is used to send out periodic
4.7) then state must be torn down and rebuilt for groups whose RP Join(*,G) messages, and to override Prune(*,G) messages from peers on
changes. an upstream LAN interface.
The last RPF neighbor towards the RP is stored because if the MRIB The last RP used must be stored because if the RP-Set changes
changes then the RPF neighbor towards the RP may change. If it does so, (Section 4.7), then state must be torn down and rebuilt for groups
then we need to trigger a new Join(*,G) to the new upstream neighbor and whose RP changes.
a Prune(*,G) to the old upstream neighbor. Similarly, if a router
detects through a changed GenID in a Hello message that the upstream The last RPF neighbor towards the RP is stored because if the MRIB
neighbor towards the RP has rebooted, then it should re-instantiate changes, then the RPF neighbor towards the RP may change. If it does
state by sending a Join(*,G). These mechanisms are specified in Section so, then we need to trigger a new Join(*,G) to the new upstream
4.5.6. neighbor and a Prune(*,G) to the old upstream neighbor. Similarly,
if a router detects through a changed GenID in a Hello message that
the upstream neighbor towards the RP has rebooted, then it should
re-instantiate state by sending a Join(*,G). These mechanisms are
specified in Section 4.5.6.
4.1.4. (S,G) State 4.1.4. (S,G) State
For every source/group pair (S,G) a router keeps the following state: For every source/group pair (S,G), a router keeps the following
state:
(S,G) state: (S,G) state:
For each interface: For each interface:
Local Membership: Local Membership:
State: One of {"NoInfo", "Include"} State: One of {"NoInfo", "Include"}
PIM (S,G) Join/Prune State: PIM (S,G) Join/Prune State:
o State: One of {"NoInfo" (NI), "Join" (J), "Prune- o State: One of {"NoInfo" (NI), "Join" (J), "Prune-
Pending" (PP)} Pending" (PP)}
o Prune-Pending Timer (PPT) o Prune-Pending Timer (PPT)
o Join/Prune Expiry Timer (ET) o Join/Prune Expiry Timer (ET)
(S,G) Assert Winner State (S,G) Assert Winner State
o State: One of {"NoInfo" (NI), "I lost Assert" (L), o State: One of {"NoInfo" (NI), "I lost Assert" (L),
"I won Assert" (W)} "I won Assert" (W)}
o Assert Timer (AT) o Assert Timer (AT)
o Assert winner's IP Address (AssertWinner) o Assert winner's IP Address (AssertWinner)
o Assert winner's Assert Metric (AssertWinnerMetric) o Assert winner's Assert Metric (AssertWinnerMetric)
Not interface specific: Not interface specific:
Upstream (S,G) Join/Prune State: Upstream (S,G) Join/Prune State:
o State: One of {"NotJoined(S,G)", "Joined(S,G)"} o State: One of {"NotJoined(S,G)", "Joined(S,G)"}
o Upstream (S,G) Join/Prune Timer (JT) o Upstream (S,G) Join/Prune Timer (JT)
o Last RPF Neighbor towards S that was used o Last RPF Neighbor towards S that was used
o SPTbit (indicates (S,G) state is active) o SPTbit (indicates (S,G) state is active)
o (S,G) Keepalive Timer (KAT) o (S,G) Keepalive Timer (KAT)
Additional (S,G) state at the DR: Additional (S,G) state at the DR:
o Register state: One of {"Join" (J), "Prune" (P), o Register state: One of {"Join" (J), "Prune" (P),
"Join-Pending" (JP), "NoInfo" (NI)} "Join-Pending" (JP), "NoInfo" (NI)}
o Register-Stop timer o Register-Stop timer
Additional (S,G) state at the RP: Additional (S,G) state at the RP:
o PMBR: the first PMBR to send a Register for this o PMBR: the first PMBR to send a Register for this
source with the Border bit set. source with the Border bit set.
Local membership is the result of the local source-specific membership Local membership is the result of the local source-specific
mechanism (such as IGMP version 3) running on that interface and membership mechanism (such as IGMP version 3) running on that
specifying that this particular source should be included. As stored interface and specifying that this particular source should be
here, this state is the resulting state after any IGMPv3 inconsistencies included. As stored here, this state is the resulting state after
have been resolved. It need not be kept if this router is not the DR on any IGMPv3 inconsistencies have been resolved. It need not be kept
that interface unless this router won a (S,G) assert on this interface if this router is not the DR on that interface unless this router won
for this group. However, we recommend storing this information if a (S,G) assert on this interface for this group. However, we
possible, as it reduces latency converging to stable operating recommend storing this information if possible, as it reduces latency
conditions after a failure causing a change of DR. This information is converging to stable operating conditions after a failure causing a
used by the pim_include(S,G) macro described in Section 4.1.6. change of DR. This information is used by the pim_include(S,G) macro
described in Section 4.1.6.
PIM (S,G) Join/Prune state is the result of receiving PIM (S,G) PIM (S,G) Join/Prune state is the result of receiving PIM (S,G)
Join/Prune messages on this interface, and is specified in Section Join/Prune messages on this interface and is specified in Section
4.5.2. The state is used by the macros that calculate the outgoing 4.5.2. The state is used by the macros that calculate the outgoing
interface list in Section 4.1.6, and in the JoinDesired(S,G) macro interface list in Section 4.1.6, and in the JoinDesired(S,G) macro
(defined in Section 4.5.7) that is used in deciding whether a Join(S,G) (defined in Section 4.5.7) that is used in deciding whether a
should be sent upstream. Join(S,G) should be sent upstream.
(S,G) Assert Winner state is the result of sending or receiving (S,G) (S,G) Assert Winner state is the result of sending or receiving (S,G)
Assert messages on this interface. It is specified in Section 4.6.1. Assert messages on this interface. It is specified in Section 4.6.1.
The upstream (S,G) Join/Prune State reflects the state of the upstream The upstream (S,G) Join/Prune State reflects the state of the
(S,G) state machine described in Section 4.5.7. upstream (S,G) state machine described in Section 4.5.7.
The upstream (S,G) Join/Prune Timer is used to send out periodic The upstream (S,G) Join/Prune Timer is used to send out periodic
Join(S,G) messages, and to override Prune(S,G) messages from peers on an Join(S,G) messages, and to override Prune(S,G) messages from peers on
upstream LAN interface. an upstream LAN interface.
The last RPF neighbor towards S is stored because if the MRIB changes The last RPF neighbor towards S is stored because if the MRIB
then the RPF neighbor towards S may change. If it does so, then we need changes, then the RPF neighbor towards S may change. If it does so,
to trigger a new Join(S,G) to the new upstream neighbor and a Prune(S,G) then we need to trigger a new Join(S,G) to the new upstream neighbor
to the old upstream neighbor. Similarly, if the router detects through and a Prune(S,G) to the old upstream neighbor. Similarly, if the
a changed GenID in a Hello message that the upstream neighbor towards S router detects through a changed GenID in a Hello message that the
has rebooted, then it should re-instantiate state by sending a upstream neighbor towards S has rebooted, then it should re-
Join(S,G). These mechanisms are specified in Section 4.5.7. instantiate state by sending a Join(S,G). These mechanisms are
specified in Section 4.5.7.
The SPTbit is used to indicate whether forwarding is taking place on the The SPTbit is used to indicate whether forwarding is taking place on
(S,G) Shortest Path Tree (SPT) or on the (*,G) tree. A router can have the (S,G) Shortest Path Tree (SPT) or on the (*,G) tree. A router
(S,G) state and still be forwarding on (*,G) state during the interval can have (S,G) state and still be forwarding on (*,G) state during
when the source-specific tree is being constructed. When SPTbit is the interval when the source-specific tree is being constructed.
FALSE, only (*,G) forwarding state is used to forward packets from S to When SPTbit is FALSE, only (*,G) forwarding state is used to forward
G. When SPTbit is TRUE, both (*,G) and (S,G) forwarding state are used. packets from S to G. When SPTbit is TRUE, both (*,G) and (S,G)
forwarding state are used.
The (S,G) Keepalive Timer is updated by data being forwarded using this The (S,G) Keepalive Timer is updated by data being forwarded using
(S,G) forwarding state. It is used to keep (S,G) state alive in the this (S,G) forwarding state. It is used to keep (S,G) state alive in
absence of explicit (S,G) Joins. Amongst other things, this is the absence of explicit (S,G) Joins. Amongst other things, this is
necessary for the so-called "turnaround rules" - when the RP uses (S,G) necessary for the so-called "turnaround rules" -- when the RP uses
joins to stop encapsulation, and then (S,G) prunes to prevent traffic (S,G) joins to stop encapsulation, and then (S,G) prunes to prevent
from unnecessarily reaching the RP. traffic from unnecessarily reaching the RP.
On a DR, the (S,G) Register State is used to keep track of whether to On a DR, the (S,G) Register State is used to keep track of whether to
encapsulate data to the RP on the Register Tunnel; the (S,G) Register- encapsulate data to the RP on the Register Tunnel; the (S,G)
Stop timer tracks how long before encapsulation begins again for a given Register-Stop timer tracks how long before encapsulation begins again
(S,G). for a given (S,G).
On an RP, the PMBR value must be cleared when the Keepalive Timer On an RP, the PMBR value must be cleared when the Keepalive Timer
expires. expires.
4.1.5. (S,G,rpt) State 4.1.5. (S,G,rpt) State
For every source/group pair (S,G) for which a router also has (*,G) For every source/group pair (S,G) for which a router also has (*,G)
state, it also keeps the following state: state, it also keeps the following state:
(S,G,rpt) state: (S,G,rpt) state:
For each interface: For each interface:
Local Membership: Local Membership:
State: One of {"NoInfo", "Exclude"} State: One of {"NoInfo", "Exclude"}
PIM (S,G,rpt) Join/Prune State: PIM (S,G,rpt) Join/Prune State:
o State: One of {"NoInfo", "Pruned", "Prune- o State: One of {"NoInfo", "Pruned", "Prune-
Pending"} Pending"}
o Prune-Pending Timer (PPT) o Prune-Pending Timer (PPT)
o Join/Prune Expiry Timer (ET) o Join/Prune Expiry Timer (ET)
Not interface specific: Not interface specific:
Upstream (S,G,rpt) Join/Prune State: Upstream (S,G,rpt) Join/Prune State:
o State: One of {"RPTNotJoined(G)", o State: One of {"RPTNotJoined(G)",
"NotPruned(S,G,rpt)", "Pruned(S,G,rpt)"} "NotPruned(S,G,rpt)", "Pruned(S,G,rpt)"}
o Override Timer (OT) o Override Timer (OT)
Local membership is the result of the local source-specific membership Local membership is the result of the local source-specific
mechanism (such as IGMPv3) running on that interface and specifying that membership mechanism (such as IGMPv3) running on that interface and
although there is (*,G) Include state, this particular source should be specifying that although there is (*,G) Include state, this
excluded. As stored here, this state is the resulting state after any particular source should be excluded. As stored here, this state is
IGMPv3 inconsistencies between LAN members have been resolved. It need the resulting state after any IGMPv3 inconsistencies between LAN
not be kept if this router is not the DR on that interface unless this members have been resolved. It need not be kept if this router is
router won a (*,G) assert on this interface for this group. However, we not the DR on that interface unless this router won a (*,G) assert on
recommend storing this information if possible, as it reduces latency this interface for this group. However, we recommend storing this
converging to stable operating conditions after a failure causing a information if possible, as it reduces latency converging to stable
change of DR. This information is used by the pim_exclude(S,G) macro operating conditions after a failure causing a change of DR. This
described in Section 4.1.6. information is used by the pim_exclude(S,G) macro described in
Section 4.1.6.
PIM (S,G,rpt) Join/Prune state is the result of receiving PIM (S,G,rpt) PIM (S,G,rpt) Join/Prune state is the result of receiving PIM
Join/Prune messages on this interface, and is specified in Section (S,G,rpt) Join/Prune messages on this interface and is specified in
4.5.4. The state is used by the macros that calculate the outgoing Section 4.5.4. The state is used by the macros that calculate the
interface list in Section 4.1.6, and in the rules for adding outgoing interface list in Section 4.1.6, and in the rules for adding
Prune(S,G,rpt) messages to Join(*,G) messages specified in Section Prune(S,G,rpt) messages to Join(*,G) messages specified in Section
4.5.8. 4.5.8.
The upstream (S,G,rpt) Join/Prune state is used along with the Override The upstream (S,G,rpt) Join/Prune state is used along with the
Timer to send the correct override messages in response to Join/Prune Override Timer to send the correct override messages in response to
messages sent by upstream peers on a LAN. This state and behavior are Join/Prune messages sent by upstream peers on a LAN. This state and
specified in Section 4.5.9. behavior are specified in Section 4.5.9.
4.1.6. State Summarization Macros 4.1.6. State Summarization Macros
Using this state, we define the following "macro" definitions which we Using this state, we define the following "macro" definitions, which
will use in the descriptions of the state machines and pseudocode in the we will use in the descriptions of the state machines and pseudocode
following sections. in the following sections.
The most important macros are those that define the outgoing interface
list (or "olist") for the relevant state. An olist can be "immediate"
if it is built directly from the state of the relevant type. For
example, the immediate_olist(S,G) is the olist that would be built if
the router only had (S,G) state and no (*,G) or (S,G,rpt) state. In
contrast, the "inherited" olist inherits state from other types. For
example, the inherited_olist(S,G) is the olist that is relevant for
forwarding a packet from S to G using both source-specific and group-
specific state.
There is no immediate_olist(S,G,rpt) as (S,G,rpt) state is negative
state - it removes interfaces in the (*,G) olist from the olist that is
actually used to forward traffic. The inherited_olist(S,G,rpt) is
therefore the olist that would be used for a packet from S to G
forwarding on the RP tree. It is a strict subset of
(immediate_olist(*,*,RP) (+) immediate_olist(*,G)).
Generally speaking, the inherited olists are used for forwarding, and The most important macros are those that define the outgoing
the immediate_olists are used to make decisions about state maintenance. interface list (or "olist") for the relevant state. An olist can be
"immediate" if it is built directly from the state of the relevant
type. For example, the immediate_olist(S,G) is the olist that would
be built if the router only had (S,G) state and no (*,G) or (S,G,rpt)
state. In contrast, the "inherited" olist inherits state from other
types. For example, the inherited_olist(S,G) is the olist that is
relevant for forwarding a packet from S to G using both source-
specific and group-specific state.
immediate_olist(*,*,RP) = There is no immediate_olist(S,G,rpt) as (S,G,rpt) state is negative
joins(*,*,RP) state; it removes interfaces in the (*,G) olist from the olist that
is actually used to forward traffic. The inherited_olist(S,G,rpt) is
therefore the olist that would be used for a packet from S to G
forwarding on the RP tree. It is a strict subset of
(immediate_olist(*,*,RP) (+) immediate_olist(*,G)).
immediate_olist(*,G) = Generally speaking, the inherited olists are used for forwarding, and
joins(*,G) (+) pim_include(*,G) (-) lost_assert(*,G) the immediate_olists are used to make decisions about state
maintenance.
immediate_olist(S,G) = immediate_olist(*,*,RP) =
joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) joins(*,*,RP)
inherited_olist(S,G,rpt) = immediate_olist(*,G) =
( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) joins(*,G) (+) pim_include(*,G) (-) lost_assert(*,G)
(+) ( pim_include(*,G) (-) pim_exclude(S,G))
(-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) )
inherited_olist(S,G) = immediate_olist(S,G) =
inherited_olist(S,G,rpt) (+) joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
The macros pim_include(*,G) and pim_include(S,G) indicate the interfaces inherited_olist(S,G,rpt) =
to which traffic might be forwarded because of hosts that are local ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
members on that interface. Note that normally only the DR cares about (+) ( pim_include(*,G) (-) pim_exclude(S,G))
local membership, but when an assert happens, the assert winner takes (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) )
over responsibility for forwarding traffic to local members that have
requested traffic on a group or source/group pair.
pim_include(*,G) = inherited_olist(S,G) =
{ all interfaces I such that: inherited_olist(S,G,rpt) (+)
( ( I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
OR AssertWinner(*,G,I) == me )
AND local_receiver_include(*,G,I) }
pim_include(S,G) = The macros pim_include(*,G) and pim_include(S,G) indicate the
{ all interfaces I such that: interfaces to which traffic might be forwarded because of hosts that
( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) are local members on that interface. Note that normally only the DR
OR AssertWinner(S,G,I) == me ) cares about local membership, but when an assert happens, the assert
AND local_receiver_include(S,G,I) } winner takes over responsibility for forwarding traffic to local
members that have requested traffic on a group or source/group pair.
pim_exclude(S,G) = pim_include(*,G) =
{ all interfaces I such that: { all interfaces I such that:
( (I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) ( ( I_am_DR( I ) AND lost_assert(*,G,I) == FALSE )
OR AssertWinner(*,G,I) == me ) OR AssertWinner(*,G,I) == me )
AND local_receiver_include(*,G,I) }
AND local_receiver_exclude(S,G,I) } pim_include(S,G) =
{ all interfaces I such that:
( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE )
OR AssertWinner(S,G,I) == me )
AND local_receiver_include(S,G,I) }
The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD pim_exclude(S,G) =
module or other local membership mechanism has determined that local { all interfaces I such that:
members on interface I desire to receive traffic sent specifically by S ( (I_am_DR( I ) AND lost_assert(*,G,I) == FALSE )
to G. "local_receiver_include(*,G,I)" is true if the IGMP/MLD module or OR AssertWinner(*,G,I) == me )
other local membership mechanism has determined that local members on AND local_receiver_exclude(S,G,I) }
interface I desire to receive all traffic sent to G (possibly excluding
traffic from a specific set of sources). "local_receiver_exclude(S,G,I)
is true if "local_receiver_include(*,G,I)" is true but none of the local
members desire to receive traffic from S.
The set "joins(*,*,RP)" is the set of all interfaces on which the router The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD
has received (*,*,RP) Joins: module or other local membership mechanism has determined that local
members on interface I desire to receive traffic sent specifically by
S to G. "local_receiver_include(*,G,I)" is true if the IGMP/MLD
module or other local membership mechanism has determined that local
members on interface I desire to receive all traffic sent to G
(possibly excluding traffic from a specific set of sources).
"local_receiver_exclude(S,G,I) is true if
"local_receiver_include(*,G,I)" is true but none of the local members
desire to receive traffic from S.
joins(*,*,RP) = The set "joins(*,*,RP)" is the set of all interfaces on which the
{ all interfaces I such that router has received (*,*,RP) Joins:
DownstreamJPState(*,*,RP,I) is either Join or
Prune-Pending }
DownstreamJPState(*,*,RP,I) is the state of the finite state machine in joins(*,*,RP) =
Section 4.5.1. { all interfaces I such that
DownstreamJPState(*,*,RP,I) is either Join or
Prune-Pending }
The set "joins(*,G)" is the set of all interfaces on which the router DownstreamJPState(*,*,RP,I) is the state of the finite state machine
has received (*,G) Joins: in Section 4.5.1.
joins(*,G) = The set "joins(*,G)" is the set of all interfaces on which the router
{ all interfaces I such that has received (*,G) Joins:
DownstreamJPState(*,G,I) is either Join or Prune-Pending }
DownstreamJPState(*,G,I) is the state of the finite state machine in joins(*,G) =
Section 4.5.2. { all interfaces I such that
DownstreamJPState(*,G,I) is either Join or Prune-Pending }
The set "joins(S,G)" is the set of all interfaces on which the router DownstreamJPState(*,G,I) is the state of the finite state machine in
has received (S,G) Joins: Section 4.5.2.
joins(S,G) = The set "joins(S,G)" is the set of all interfaces on which the router
{ all interfaces I such that has received (S,G) Joins:
DownstreamJPState(S,G,I) is either Join or Prune-Pending }
DownstreamJPState(S,G,I) is the state of the finite state machine in joins(S,G) =
Section 4.5.3. { all interfaces I such that
DownstreamJPState(S,G,I) is either Join or Prune-Pending }
The set "prunes(S,G,rpt)" is the set of all interfaces on which the DownstreamJPState(S,G,I) is the state of the finite state machine in
router has received (*,G) joins and (S,G,rpt) prunes. Section 4.5.3.
prunes(S,G,rpt) = The set "prunes(S,G,rpt)" is the set of all interfaces on which the
{ all interfaces I such that router has received (*,G) joins and (S,G,rpt) prunes.
DownstreamJPState(S,G,rpt,I) is Prune or PruneTmp }
DownstreamJPState(S,G,rpt,I) is the state of the finite state machine in prunes(S,G,rpt) =
Section 4.5.4. { all interfaces I such that
DownstreamJPState(S,G,rpt,I) is Prune or PruneTmp }
The set "lost_assert(*,G)" is the set of all interfaces on which the DownstreamJPState(S,G,rpt,I) is the state of the finite state machine
router has received (*,G) joins but has lost a (*,G) assert. The macro in Section 4.5.4.
lost_assert(*,G,I) is defined in Section 4.6.5.
lost_assert(*,G) = The set "lost_assert(*,G)" is the set of all interfaces on which the
{ all interfaces I such that router has received (*,G) joins but has lost a (*,G) assert. The
lost_assert(*,G,I) == TRUE } macro lost_assert(*,G,I) is defined in Section 4.6.5.
The set "lost_assert(S,G,rpt)" is the set of all interfaces on which the lost_assert(*,G) =
router has received (*,G) joins but has lost an (S,G) assert. The macro { all interfaces I such that
lost_assert(S,G,rpt,I) is defined in Section 4.6.5. lost_assert(*,G,I) == TRUE }
lost_assert(S,G,rpt) = The set "lost_assert(S,G,rpt)" is the set of all interfaces on which
{ all interfaces I such that the router has received (*,G) joins but has lost an (S,G) assert.
lost_assert(S,G,rpt,I) == TRUE } The macro lost_assert(S,G,rpt,I) is defined in Section 4.6.5.
The set "lost_assert(S,G)" is the set of all interfaces on which the lost_assert(S,G,rpt) =
router has received (S,G) joins but has lost an (S,G) assert. The macro { all interfaces I such that
lost_assert(S,G,I) is defined in Section 4.6.5. lost_assert(S,G,rpt,I) == TRUE }
lost_assert(S,G) = The set "lost_assert(S,G)" is the set of all interfaces on which the
{ all interfaces I such that router has received (S,G) joins but has lost an (S,G) assert. The
lost_assert(S,G,I) == TRUE } macro lost_assert(S,G,I) is defined in Section 4.6.5.
The following pseudocode macro definitions are also used in many places lost_assert(S,G) =
in the specification. Basically RPF' is the RPF neighbor towards an RP { all interfaces I such that
or source unless a PIM-Assert has overridden the normal choice of lost_assert(S,G,I) == TRUE }
neighbor.
neighbor RPF'(*,G) { The following pseudocode macro definitions are also used in many
if ( I_Am_Assert_Loser(*, G, RPF_interface(RP(G))) ) { places in the specification. Basically, RPF' is the RPF neighbor
return AssertWinner(*, G, RPF_interface(RP(G)) ) towards an RP or source unless a PIM-Assert has overridden the normal
} else { choice of neighbor.
return NBR( RPF_interface(RP(G)), MRIB.next_hop( RP(G) ) )
}
}
neighbor RPF'(S,G,rpt) { neighbor RPF'(*,G) {
if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) { if ( I_Am_Assert_Loser(*, G, RPF_interface(RP(G))) ) {
return AssertWinner(S, G, RPF_interface(RP(G)) ) return AssertWinner(*, G, RPF_interface(RP(G)) )
} else { } else {
return RPF'(*,G) return NBR( RPF_interface(RP(G)), MRIB.next_hop( RP(G) ) )
} }
} }
neighbor RPF'(S,G) { neighbor RPF'(S,G,rpt) {
if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) { if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) {
return AssertWinner(S, G, RPF_interface(S) ) return AssertWinner(S, G, RPF_interface(RP(G)) )
} else { } else {
return NBR( RPF_interface(S), MRIB.next_hop( S ) ) return RPF'(*,G)
} }
} }
neighbor RPF'(S,G) {
if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) {
return AssertWinner(S, G, RPF_interface(S) )
} else {
return NBR( RPF_interface(S), MRIB.next_hop( S ) )
}
}
RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data packets RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data packets
should be coming and to which joins should be sent on the RP tree and should be coming and to which joins should be sent on the RP tree and
SPT respectively. SPT, respectively.
RPF'(S,G,rpt) is basically RPF'(*,G) modified by the result of an RPF'(S,G,rpt) is basically RPF'(*,G) modified by the result of an
Assert(S,G) on RPF_interface(RP(G)). In such a case, packets from S Assert(S,G) on RPF_interface(RP(G)). In such a case, packets from S
will be originating from a different router than RPF'(*,G). If we only will be originating from a different router than RPF'(*,G). If we
have active (*,G) Join state, we need to accept packets from only have active (*,G) Join state, we need to accept packets from
RPF'(S,G,rpt), and add a Prune(S,G,rpt) to the periodic Join(*,G) RPF'(S,G,rpt) and add a Prune(S,G,rpt) to the periodic Join(*,G)
messages that we send to RPF'(*,G) (See Section 4.5.8). messages that we send to RPF'(*,G) (see Section 4.5.8).
The function MRIB.next_hop( S ) returns an address of the next-hop PIM The function MRIB.next_hop( S ) returns an address of the next-hop
neighbor toward the host S, as indicated by the current MRIB. If S is PIM neighbor toward the host S, as indicated by the current MRIB. If
directly adjacent, then MRIB.next_hop( S ) returns NULL. At the RP for S is directly adjacent, then MRIB.next_hop( S ) returns NULL. At the
G, MRIB.next_hop( RP(G)) returns NULL. RP for G, MRIB.next_hop( RP(G)) returns NULL.
The function NBR( I, A ) uses information gathered through PIM Hello The function NBR( I, A ) uses information gathered through PIM Hello
messages to map the IP address A of a directly connected PIM neighbor messages to map the IP address A of a directly connected PIM neighbor
router on interface I to the primary IP address of the same router router on interface I to the primary IP address of the same router
(Section 4.3.4). The primary IP address of a neighbor is the address (Section 4.3.4). The primary IP address of a neighbor is the address
that it uses as the source of its PIM Hello messages. Note that a that it uses as the source of its PIM Hello messages. Note that a
neighbor's IP address may be non-unique within the PIM neighbor database neighbor's IP address may be non-unique within the PIM neighbor
due to scope issues. The address must however be unique amongst the database due to scope issues. The address must, however, be unique
addresses of all the PIM neighbors on a specific interface. amongst the addresses of all the PIM neighbors on a specific
interface.
I_Am_Assert_Loser(S, G, I) is true if the Assert state machine (in I_Am_Assert_Loser(S, G, I) is true if the Assert state machine (in
Section 4.6.1) for (S,G) on Interface I is in "I am Assert Loser" state. Section 4.6.1) for (S,G) on Interface I is in "I am Assert Loser"
state.
I_Am_Assert_Loser(*, G, I) is true if the Assert state machine (in I_Am_Assert_Loser(*, G, I) is true if the Assert state machine (in
Section 4.6.2) for (*,G) on Interface I is in "I am Assert Loser" state. Section 4.6.2) for (*,G) on Interface I is in "I am Assert Loser"
state.
4.2. Data Packet Forwarding Rules 4.2. Data Packet Forwarding Rules
The PIM-SM packet forwarding rules are defined below in pseudocode. The PIM-SM packet forwarding rules are defined below in pseudocode.
iif is the incoming interface of the packet. iif is the incoming interface of the packet.
S is the source address of the packet. S is the source address of the packet.
G is the destination address of the packet (group address). G is the destination address of the packet (group address).
RP is the address of the Rendezvous Point for this group. RP is the address of the Rendezvous Point for this group.
RPF_interface(S) is the interface the MRIB indicates would be used RPF_interface(S) is the interface the MRIB indicates would be used
to route packets to S. to route packets to S.
RPF_interface(RP) is the interface the MRIB indicates would be used RPF_interface(RP) is the interface the MRIB indicates would be
to route packets to RP, except at the RP when it is the used to route packets to RP, except at the RP when it is the
decapsulation interface (the "virtual" interface on which register decapsulation interface (the "virtual" interface on which register
packets are received). packets are received).
First, we restart (or start) the Keepalive Timer if the source is on a First, we restart (or start) the Keepalive Timer if the source is on
directly connected subnet. a directly connected subnet.
Second, we check to see if the SPTbit should be set because we've now Second, we check to see if the SPTbit should be set because we've now
switched from the RP tree to the SPT. switched from the RP tree to the SPT.
Next we check to see whether the packet should be accepted based on TIB Next, we check to see whether the packet should be accepted based on
state and the interface that the packet arrived on. TIB state and the interface that the packet arrived on.
If the packet should be forwarded using (S,G) state, we then build an If the packet should be forwarded using (S,G) state, we then build an
outgoing interface list for the packet. If this list is not empty, then outgoing interface list for the packet. If this list is not empty,
we restart the (S,G) state Keepalive Timer. then we restart the (S,G) state Keepalive Timer.
If the packet should be forwarded using (*,*,RP) or (*,G) state, then we If the packet should be forwarded using (*,*,RP) or (*,G) state, then
just build an outgoing interface list for the packet. We also check if we just build an outgoing interface list for the packet. We also
we should initiate a switch to start receiving this source on a shortest check if we should initiate a switch to start receiving this source
path tree. on a shortest path tree.
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
empty, we forward the packet out of those interfaces. not empty, we forward the packet out of those interfaces.
On receipt of data from S to G on interface iif: On receipt of data from S to G on interface iif:
if( DirectlyConnected(S) == TRUE AND iif == RPF_interface(S) ) { if( DirectlyConnected(S) == TRUE AND iif == RPF_interface(S) ) {
set KeepaliveTimer(S,G) to Keepalive_Period set KeepaliveTimer(S,G) to Keepalive_Period
# Note: a register state transition or UpstreamJPState(S,G) # Note: a register state transition or UpstreamJPState(S,G)
# transition may happen as a result of restarting # transition may happen as a result of restarting
# KeepaliveTimer, and must be dealt with here. # KeepaliveTimer, and must be dealt with here.
} }
if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined AND if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined AND
inherited_olist(S,G) != NULL ) { inherited_olist(S,G) != NULL ) {
set KeepaliveTimer(S,G) to Keepalive_Period set KeepaliveTimer(S,G) to Keepalive_Period
} }
Update_SPTbit(S,G,iif) Update_SPTbit(S,G,iif)
oiflist = NULL oiflist = NULL
if( iif == RPF_interface(S) AND SPTbit(S,G) == TRUE ) { if( iif == RPF_interface(S) AND SPTbit(S,G) == TRUE ) {
oiflist = inherited_olist(S,G) oiflist = inherited_olist(S,G)
} else if( iif == RPF_interface(RP(G)) AND SPTbit(S,G) == FALSE) { } else if( iif == RPF_interface(RP(G)) AND SPTbit(S,G) == FALSE) {
oiflist = inherited_olist(S,G,rpt) oiflist = inherited_olist(S,G,rpt)
CheckSwitchToSpt(S,G) CheckSwitchToSpt(S,G)
} else { } else {
# Note: RPF check failed # Note: RPF check failed
# A transition in an Assert FSM, may cause an Assert(S,G) # A transition in an Assert FSM may cause an Assert(S,G)
# or Assert(*,G) message to be sent out interface iif. # or Assert(*,G) message to be sent out interface iif.
# See section 4.6 for details. # See section 4.6 for details.
if ( SPTbit(S,G) == TRUE AND iif is in inherited_olist(S,G) ) { if ( SPTbit(S,G) == TRUE AND iif is in inherited_olist(S,G) ) {
send Assert(S,G) on iif send Assert(S,G) on iif
} else if ( SPTbit(S,G) == FALSE AND } else if ( SPTbit(S,G) == FALSE AND
iif is in inherited_olist(S,G,rpt) { iif is in inherited_olist(S,G,rpt) {
send Assert(*,G) on iif send Assert(*,G) on iif
} }
} }
oiflist = oiflist (-) iif oiflist = oiflist (-) iif
forward packet on all interfaces in oiflist forward packet on all interfaces in oiflist
This pseudocode employs several "macro" definitions: This pseudocode employs several "macro" definitions:
DirectlyConnected(S) is TRUE if the source S is on any subnet that is DirectlyConnected(S) is TRUE if the source S is on any subnet that is
directly connected to this router (or for packets originating on this directly connected to this router (or for packets originating on this
router). router).
inherited_olist(S,G) and inherited_olist(S,G,rpt) are defined in Section inherited_olist(S,G) and inherited_olist(S,G,rpt) are defined in
4.1. Section 4.1.
Basically inherited_olist(S,G) is the outgoing interface list for Basically, inherited_olist(S,G) is the outgoing interface list for
packets forwarded on (S,G) state taking into account (*,*,RP) state, packets forwarded on (S,G) state, taking into account (*,*,RP) state,
(*,G) state, asserts, etc. (*,G) state, asserts, etc.
inherited_olist(S,G,rpt) is the outgoing interface list for packets inherited_olist(S,G,rpt) is the outgoing interface list for packets
forwarded on (*,*,RP) or (*,G) state taking into account (S,G,rpt) prune forwarded on (*,*,RP) or (*,G) state, taking into account (S,G,rpt)
state, and asserts, etc. prune state, asserts, etc.
Update_SPTbit(S,G,iif) is defined in Section 4.2.2. Update_SPTbit(S,G,iif) is defined in Section 4.2.2.
CheckSwitchToSpt(S,G) is defined in Section 4.2.1. CheckSwitchToSpt(S,G) is defined in Section 4.2.1.
UpstreamJPState(S,G) is the state of the finite state machine in Section UpstreamJPState(S,G) is the state of the finite state machine in
4.5.7. Section 4.5.7.
Keepalive_Period is defined in Section 4.10. Keepalive_Period is defined in Section 4.10.
Data triggered PIM-Assert messages sent from the above forwarding code Data-triggered PIM-Assert messages sent from the above forwarding
should be rate-limited in a implementation-dependent manner. code should be rate-limited in a implementation-dependent manner.
4.2.1. Last-hop Switchover to the SPT 4.2.1. Last-Hop Switchover to the SPT
In Sparse-Mode PIM, last-hop routers join the shared tree towards the In Sparse-Mode PIM, last-hop routers join the shared tree towards the
RP. Once traffic from sources to joined groups arrives at a last-hop RP. Once traffic from sources to joined groups arrives at a last-hop
router it has the option of switching to receive the traffic on a router, it has the option of switching to receive the traffic on a
shortest path tree (SPT). shortest path tree (SPT).
The decision for a router to switch to the SPT is controlled as follows: The decision for a router to switch to the SPT is controlled as
follows:
void void
CheckSwitchToSpt(S,G) { CheckSwitchToSpt(S,G) {
if ( ( pim_include(*,G) (-) pim_exclude(S,G) if ( ( pim_include(*,G) (-) pim_exclude(S,G)
(+) pim_include(S,G) != NULL ) (+) pim_include(S,G) != NULL )
AND SwitchToSptDesired(S,G) ) { AND SwitchToSptDesired(S,G) ) {
# Note: Restarting the KAT will result in the SPT switch # Note: Restarting the KAT will result in the SPT switch
set KeepaliveTimer(S,G) to Keepalive_Period set KeepaliveTimer(S,G) to Keepalive_Period
} }
} }
SwitchToSptDesired(S,G) is a policy function that is implementation SwitchToSptDesired(S,G) is a policy function that is implementation
defined. An "infinite threshold" policy can be implemented making defined. An "infinite threshold" policy can be implemented by making
SwitchToSptDesired(S,G) return false all the time. A "switch on first SwitchToSptDesired(S,G) return false all the time. A "switch on
packet" policy can be implemented by making SwitchToSptDesired(S,G) first packet" policy can be implemented by making
return true once a single packet has been received for the source and SwitchToSptDesired(S,G) return true once a single packet has been
group. received for the source and group.
4.2.2. Setting and Clearing the (S,G) SPTbit 4.2.2. Setting and Clearing the (S,G) SPTbit
The (S,G) SPTbit is used to distinguish whether to forward on The (S,G) SPTbit is used to distinguish whether to forward on
(*,*,RP)/(*,G) or on (S,G) state. When switching from the RP tree to (*,*,RP)/(*,G) or on (S,G) state. When switching from the RP tree to
the source tree, there is a transition period when data is arriving due the source tree, there is a transition period when data is arriving
to upstream (*,*,RP)/(*,G) state while upstream (S,G) state is being due to upstream (*,*,RP)/(*,G) state while upstream (S,G) state is
established during which time a router should continue to forward only being established, during which time a router should continue to
on (*,*,RP)/(*,G) state. This prevents temporary black-holes that would forward only on (*,*,RP)/(*,G) state. This prevents temporary
be caused by sending a Prune(S,G,rpt) before the upstream (S,G) state black-holes that would be caused by sending a Prune(S,G,rpt) before
has finished being established. the upstream (S,G) state has finished being established.
Thus, when a packet arrives, the (S,G) SPTbit is updated as follows: Thus, when a packet arrives, the (S,G) SPTbit is updated as follows:
void void
Update_SPTbit(S,G,iif) { Update_SPTbit(S,G,iif) {
if ( iif == RPF_interface(S) if ( iif == RPF_interface(S)
AND JoinDesired(S,G) == TRUE AND JoinDesired(S,G) == TRUE
AND ( DirectlyConnected(S) == TRUE AND ( DirectlyConnected(S) == TRUE
OR RPF_interface(S) != RPF_interface(RP(G)) OR RPF_interface(S) != RPF_interface(RP(G))
OR inherited_olist(S,G,rpt) == NULL OR inherited_olist(S,G,rpt) == NULL
OR ( ( RPF'(S,G) == RPF'(*,G) ) AND OR ( ( RPF'(S,G) == RPF'(*,G) ) AND
( RPF'(S,G) != NULL ) ) ( RPF'(S,G) != NULL ) )
OR ( I_Am_Assert_Loser(S,G,iif) ) { OR ( I_Am_Assert_Loser(S,G,iif) ) {
Set SPTbit(S,G) to TRUE Set SPTbit(S,G) to TRUE
} }
} }
Additionally a router can set SPTbit(S,G) to TRUE in other cases, such Additionally, a router can set SPTbit(S,G) to TRUE in other cases,
as when it receives an Assert(S,G) on RPF_interface(S) (see Section such as when it receives an Assert(S,G) on RPF_interface(S) (see
4.6.1). Section 4.6.1).
JoinDesired(S,G) is defined in Section 4.5.7, and indicates whether we JoinDesired(S,G) is defined in Section 4.5.7 and indicates whether we
have the appropriate (S,G) Join state to wish to send a Join(S,G) have the appropriate (S,G) Join state to wish to send a Join(S,G)
upstream. upstream.
Basically Update_SPTbit will set the SPTbit if we have the appropriate Basically, Update_SPTbit will set the SPTbit if we have the
(S,G) join state and the packet arrived on the correct upstream appropriate (S,G) join state, and if the packet arrived on the
interface for S, and one or more of the following conditions applies: correct upstream interface for S, and if one or more of the following
conditions applies:
1. The source is directly connected, in which case the switch to the 1. The source is directly connected, in which case the switch to the
SPT is a no-op. SPT is a no-op.
2. The RPF interface to S is different from the RPF interface to the 2. The RPF interface to S is different from the RPF interface to the
RP. The packet arrived on RPF_interface(S), and so the SPT must RP. The packet arrived on RPF_interface(S), and so the SPT must
have been completed. have been completed.
3. No-one wants the packet on the RP tree. 3. Noone wants the packet on the RP tree.
4. RPF'(S,G) == RPF'(*,G). In this case the router will never be able 4. RPF'(S,G) == RPF'(*,G). In this case, the router will never be
to tell if the SPT has been completed, so it should just switch able to tell if the SPT has been completed, so it should just
immediately. switch immediately.
In the case where the RPF interface is the same for the RP and for S, In the case where the RPF interface is the same for the RP and for S,
but RPF'(S,G) and RPF'(*,G) differ, then we wait for an Assert(S,G) but RPF'(S,G) and RPF'(*,G) differ, we wait for an Assert(S,G), which
which indicates that the upstream router with (S,G) state believes the indicates that the upstream router with (S,G) state believes the SPT
SPT has been completed. However item (3) above is needed because there has been completed. However, item (3) above is needed because there
may not be any (*,G) state to trigger an Assert(S,G) to happen. may not be any (*,G) state to trigger an Assert(S,G) to happen.
The SPTbit is cleared in the (S,G) upstream state machine (see Section The SPTbit is cleared in the (S,G) upstream state machine (see
4.5.7) when JoinDesired(S,G) becomes FALSE. Section 4.5.7) when JoinDesired(S,G) becomes FALSE.
4.3. Designated Routers (DR) and Hello Messages 4.3. Designated Routers (DR) and Hello Messages
A shared-media LAN like Ethernet may have multiple PIM-SM routers A shared-media LAN like Ethernet may have multiple PIM-SM routers
connected to it. A single one of these routers, the DR, will act on connected to it. A single one of these routers, the DR, will act on
behalf of directly connected hosts with respect to the PIM-SM protocol. behalf of directly connected hosts with respect to the PIM-SM
Because the distinction between LANs and point-to-point interfaces can protocol. Because the distinction between LANs and point-to-point
sometimes be blurred, and because routers may also have multicast host interfaces can sometimes be blurred, and because routers may also
functionality, the PIM-SM specification makes no distinction between the have multicast host functionality, the PIM-SM specification makes no
two. Thus DR election will happen on all interfaces, LAN or otherwise. distinction between the two. Thus, DR election will happen on all
interfaces, LAN or otherwise.
DR election is performed using Hello messages. Hello messages are also DR election is performed using Hello messages. Hello messages are
the way that option negotiation takes place in PIM, so that additional also the way that option negotiation takes place in PIM, so that
functionality can be enabled, or parameters tuned. additional functionality can be enabled, or parameters tuned.
4.3.1. Sending Hello Messages 4.3.1. Sending Hello Messages
PIM Hello messages are sent periodically on each PIM-enabled interface. PIM Hello messages are sent periodically on each PIM-enabled
They allow a router to learn about the neighboring PIM routers on each interface. They allow a router to learn about the neighboring PIM
interface. Hello messages are also the mechanism used to elect a routers on each interface. Hello messages are also the mechanism
Designated Router (DR), and to negotiate additional capabilities. A used to elect a Designated Router (DR), and to negotiate additional
router must record the Hello information received from each PIM capabilities. A router must record the Hello information received
neighbor. from each PIM neighbor.
Hello messages MUST be sent on all active interfaces, including physical Hello messages MUST be sent on all active interfaces, including
point-to-point links, and are multicast to the `ALL-PIM-ROUTERS' group physical point-to-point links, and are multicast to the 'ALL-PIM-
address (`224.0.0.13' for IPv4 and `ff02::d' for IPv6). ROUTERS' group address ('224.0.0.13' for IPv4 and 'ff02::d' for
IPv6).
We note that some implementations do not send Hello messages We note that some implementations do not send Hello messages on
on point-to-point interfaces. This is non-compliant behavior. point-to-point interfaces. This is non-compliant behavior. A
A compliant PIM router MUST send Hello messages, even on compliant PIM router MUST send Hello messages, even on point-to-
point-to-point interfaces. point interfaces.
A per interface Hello Timer (HT(I)) is used to trigger sending Hello A per-interface Hello Timer (HT(I)) is used to trigger sending Hello
messages on each active interface. When PIM is enabled on an interface messages on each active interface. When PIM is enabled on an
or a router first starts, the Hello Timer of that interface is set to a interface or a router first starts, the Hello Timer of that interface
random value between 0 and Triggered_Hello_Delay. This prevents is set to a random value between 0 and Triggered_Hello_Delay. This
synchronization of Hello messages if multiple routers are powered on prevents synchronization of Hello messages if multiple routers are
simultaneously. After the initial randomized interval, Hello messages powered on simultaneously. After the initial randomized interval,
must be sent every Hello_Period seconds. The Hello Timer should not be Hello messages must be sent every Hello_Period seconds. The Hello
reset except when it expires. Timer should not be reset except when it expires.
Note that neighbors will not accept Join/Prune or Assert messages from a Note that neighbors will not accept Join/Prune or Assert messages
router unless they have first heard a Hello message from that router. from a router unless they have first heard a Hello message from that
Thus if a router needs to send a Join/Prune or Assert message on an router. Thus, if a router needs to send a Join/Prune or Assert
interface on which it has not yet sent a Hello message with the message on an interface on which it has not yet sent a Hello message
currently configured IP address, then it MUST immediately send the with the currently configured IP address, then it MUST immediately
relevant Hello message without waiting for the Hello Timer to expire, send the relevant Hello message without waiting for the Hello Timer
followed by the Join/Prune or Assert message. to expire, followed by the Join/Prune or Assert message.
The DR_Priority Option allows a network administrator to give preference The DR_Priority Option allows a network administrator to give
to a particular router in the DR election process by giving it a preference to a particular router in the DR election process by
numerically larger DR Priority. The DR_Priority Option SHOULD be giving it a numerically larger DR Priority. The DR_Priority Option
included in every Hello message, even if no DR Priority is explicitly SHOULD be included in every Hello message, even if no DR Priority is
configured on that interface. This is necessary because priority-based explicitly configured on that interface. This is necessary because
DR election is only enabled when all neighbors on an interface advertise priority-based DR election is only enabled when all neighbors on an
that they are capable of using the DR_Priority Option. The default interface advertise that they are capable of using the DR_Priority
priority is 1. Option. The default priority is 1.
The Generation_Identifier (GenID) Option SHOULD be included in all Hello The Generation_Identifier (GenID) Option SHOULD be included in all
messages. The GenID option contains a randomly generated 32-bit value Hello messages. The GenID option contains a randomly generated
that is regenerated each time PIM forwarding is started or restarted on 32-bit value that is regenerated each time PIM forwarding is started
the interface, including when the router itself restarts. When a Hello or restarted on the interface, including when the router itself
message with a new GenID is received from a neighbor, any old Hello restarts. When a Hello message with a new GenID is received from a
information about that neighbor SHOULD be discarded and superseded by neighbor, any old Hello information about that neighbor SHOULD be
the information from the new Hello message. This may cause a new DR to discarded and superseded by the information from the new Hello
be chosen on that interface. message. This may cause a new DR to be chosen on that interface.
The LAN Prune Delay Option SHOULD be included in all Hello messages sent The LAN Prune Delay Option SHOULD be included in all Hello messages
on multi-access LANs. This option advertises a router's capability to sent on multi-access LANs. This option advertises a router's
use values other than the default for the Propagation_Delay and capability to use values other than the defaults for the
Override_Interval which affect the setting of the Prune-Pending, Propagation_Delay and Override_Interval, which affect the setting of
Upstream Join and Override Timers (defined in Section 4.10). the Prune-Pending, Upstream Join, and Override Timers (defined in
Section 4.10).
The Address List Option advertises all the secondary addresses The Address List Option advertises all the secondary addresses
associated with the source interface of the router originating the associated with the source interface of the router originating the
message. The option MUST be included in all Hello messages if there are message. The option MUST be included in all Hello messages if there
secondary addresses associated with the source interface and MAY be are secondary addresses associated with the source interface and MAY
omitted if no secondary addresses exist. be omitted if no secondary addresses exist.
To allow new or rebooting routers to learn of PIM neighbors quickly, To allow new or rebooting routers to learn of PIM neighbors quickly,
when a Hello message is received from a new neighbor, or a Hello message when a Hello message is received from a new neighbor, or a Hello
with a new GenID is received from an existing neighbor, a new Hello message with a new GenID is received from an existing neighbor, a new
message should be sent on this interface after a randomized delay Hello message should be sent on this interface after a randomized
between 0 and Triggered_Hello_Delay. This triggered message need not delay between 0 and Triggered_Hello_Delay. This triggered message
change the timing of the scheduled periodic message. If a router needs need not change the timing of the scheduled periodic message. If a
to send a Join/Prune to the new neighbor or send an Assert message in router needs to send a Join/Prune to the new neighbor or send an
response to an Assert message from the new neighbor before this Assert message in response to an Assert message from the new neighbor
randomized delay has expired, then it MUST immediately send the relevant before this randomized delay has expired, then it MUST immediately
Hello message without waiting for the Hello Timer to expire, followed by send the relevant Hello message without waiting for the Hello Timer
the Join/Prune or Assert message. If it does not do this, then the new to expire, followed by the Join/Prune or Assert message. If it does
neighbor will discard the Join/Prune or Assert message. not do this, then the new neighbor will discard the Join/Prune or
Assert message.
Before an interface goes down or changes primary IP address, a Hello Before an interface goes down or changes primary IP address, a Hello
message with a zero HoldTime should be sent immediately (with the old IP message with a zero HoldTime should be sent immediately (with the old
address if the IP address changed). This will cause PIM neighbors to IP address if the IP address changed). This will cause PIM neighbors
remove this neighbor (or its old IP address) immediately. After an to remove this neighbor (or its old IP address) immediately. After
interface has changed its IP address, it MUST send a Hello message with an interface has changed its IP address, it MUST send a Hello message
its new IP address. If an interface changes one of its secondary IP with its new IP address. If an interface changes one of its
addresses, a Hello message with an updated Address_List option and a secondary IP addresses, a Hello message with an updated Address_List
non-zero HoldTime should be sent immediately. This will cause PIM option and a non-zero HoldTime should be sent immediately. This will
neighbors to update this neighbor's list of secondary addresses cause PIM neighbors to update this neighbor's list of secondary
immediately. addresses immediately.
4.3.2. DR Election 4.3.2. DR Election
When a PIM Hello message is received on interface I the following When a PIM Hello message is received on interface I, the following
information about the sending neighbor is recorded: information about the sending neighbor is recorded:
neighbor.interface neighbor.interface
The interface on which the Hello message arrived. The interface on which the Hello message arrived.
neighbor.primary_ip_address neighbor.primary_ip_address
The IP address that the PIM neighbor used as the source The IP address that the PIM neighbor used as the source
address of the Hello message. address of the Hello message.
neighbor.genid neighbor.genid
The Generation ID of the PIM neighbor. The Generation ID of the PIM neighbor.
neighbor.dr_priority neighbor.dr_priority
The DR Priority field of the PIM neighbor if it is present in The DR Priority field of the PIM neighbor, if it is present in
the Hello message. the Hello message.
neighbor.dr_priority_present neighbor.dr_priority_present
A flag indicating if the DR Priority field was present in the A flag indicating if the DR Priority field was present in the
Hello message. Hello message.
neighbor.timeout neighbor.timeout
A timer value to time out the neighbor state when it becomes A timer value to time out the neighbor state when it becomes
stale. stale, also known as the Neighbor Liveness Timer.
The Neighbor Liveness Timer (NLT(N,I)) is reset to The Neighbor Liveness Timer (NLT(N,I)) is reset to
Hello_Holdtime (from the Hello Holdtime option) whenever a Hello_Holdtime (from the Hello Holdtime option) whenever a
Hello message is received containing a Holdtime option, or to Hello message is received containing a Holdtime option, or to
Default_Hello_Holdtime if the Hello message does not contain Default_Hello_Holdtime if the Hello message does not contain
the Holdtime option. the Holdtime option.
Neighbor state is deleted when the neighbor timeout expires. Neighbor state is deleted when the neighbor timeout expires.
The function for computing the DR on interface I is: The function for computing the DR on interface I is:
host host
DR(I) { DR(I) {
dr = me dr = me
for each neighbor on interface I { for each neighbor on interface I {
if ( dr_is_better( neighbor, dr, I ) == TRUE ) { if ( dr_is_better( neighbor, dr, I ) == TRUE ) {
dr = neighbor dr = neighbor
} }
} }
return dr return dr
} }
The function used for comparing DR "metrics" on interface I is: The function used for comparing DR "metrics" on interface I is:
bool bool
dr_is_better(a,b,I) { dr_is_better(a,b,I) {
if( there is a neighbor n on I for which n.dr_priority_present if( there is a neighbor n on I for which n.dr_priority_present
is false ) { is false ) {
return a.primary_ip_address > b.primary_ip_address return a.primary_ip_address > b.primary_ip_address
} else { } else {
return ( a.dr_priority > b.dr_priority ) OR return ( a.dr_priority > b.dr_priority ) OR
( a.dr_priority == b.dr_priority AND ( a.dr_priority == b.dr_priority AND
a.primary_ip_address > b.primary_ip_address ) a.primary_ip_address > b.primary_ip_address )
} }
} }
The trivial function I_am_DR(I) is defined to aid readability: The trivial function I_am_DR(I) is defined to aid readability:
bool bool
I_am_DR(I) { I_am_DR(I) {
return DR(I) == me return DR(I) == me
} }
The DR Priority is a 32-bit unsigned number and the numerically larger The DR Priority is a 32-bit unsigned number, and the numerically
priority is always preferred. A router's idea of the current DR on an larger priority is always preferred. A router's idea of the current
interface can change when a PIM Hello message is received, when a DR on an interface can change when a PIM Hello message is received,
neighbor times out, or when a router's own DR Priority changes. If the when a neighbor times out, or when a router's own DR Priority
router becomes the DR or ceases to be the DR, this will normally cause changes. If the router becomes the DR or ceases to be the DR, this
the DR Register state machine to change state. Subsequent actions are will normally cause the DR Register state machine to change state.
determined by that state machine. Subsequent actions are determined by that state machine.
We note that some PIM implementations do not send Hello We note that some PIM implementations do not send Hello messages on
messages on point-to-point interfaces, and so cannot perform point-to-point interfaces and thus cannot perform DR election on
DR election on such interfaces. This is non-compliant such interfaces. This is non-compliant behavior. DR election MUST
behavior. DR election MUST be performed on ALL active PIM-SM be performed on ALL active PIM-SM interfaces.
interfaces.
4.3.3. Reducing Prune Propagation Delay on LANs 4.3.3. Reducing Prune Propagation Delay on LANs
In addition to the information recorded for the DR Election, the In addition to the information recorded for the DR Election, the
following per neighbor information is obtained from the LAN Prune Delay following per neighbor information is obtained from the LAN Prune
Hello option: Delay Hello option:
neighbor.lan_prune_delay_present neighbor.lan_prune_delay_present
A flag indicating if the LAN Prune Delay option was present in A flag indicating if the LAN Prune Delay option was present in
the Hello message. the Hello message.
neighbor.tracking_support neighbor.tracking_support
A flag storing the value of the T bit in the LAN Prune Delay A flag storing the value of the T bit in the LAN Prune Delay
option if it is present in the Hello message. This indicates option if it is present in the Hello message. This indicates
the neighbor's capability to disable Join message suppression. the neighbor's capability to disable Join message suppression.
neighbor.propagation_delay neighbor.propagation_delay
The Propagation Delay field of the LAN Prune Delay option (if The Propagation Delay field of the LAN Prune Delay option (if
present) in the Hello message. present) in the Hello message.
neighbor.override_interval neighbor.override_interval
The Override_Interval field of the LAN Prune Delay option (if The Override_Interval field of the LAN Prune Delay option (if
present) in the Hello message. present) in the Hello message.
The additional state described above is deleted along with the DR The additional state described above is deleted along with the DR
neighbor state when the neighbor timeout expires. neighbor state when the neighbor timeout expires.
Just like the DR_Priority option, the information provided in the LAN Just like the DR_Priority option, the information provided in the LAN
Prune Delay option is not used unless all neighbors on a link advertise Prune Delay option is not used unless all neighbors on a link
the option. The function below computes this state: advertise the option. The function below computes this state:
bool bool
lan_delay_enabled(I) { lan_delay_enabled(I) {
for each neighbor on interface I { for each neighbor on interface I {
if ( neighbor.lan_prune_delay_present == false ) { if ( neighbor.lan_prune_delay_present == false ) {
return false return false
} }
} }
return true return true
} }
The Propagation Delay inserted by a router in the LAN Prune Delay option The Propagation Delay inserted by a router in the LAN Prune Delay
expresses the expected message propagation delay on the link and should option expresses the expected message propagation delay on the link
be configurable by the system administrator. It is used by upstream and should be configurable by the system administrator. It is used
routers to figure out how long they should wait for a Join override by upstream routers to figure out how long they should wait for a
message before pruning an interface. Join override message before pruning an interface.
PIM implementors should enforce a lower bound on the permitted values PIM implementers should enforce a lower bound on the permitted values
for this delay to allow for scheduling and processing delays within for this delay to allow for scheduling and processing delays within
their router. Such delays may cause received messages to be processed their router. Such delays may cause received messages to be
later as well as triggered messages to be sent later than intended. processed later as well as triggered messages to be sent later than
Setting this Propagation Delay to too low a value may result in intended. Setting this Propagation Delay to too low a value may
temporary forwarding outages because a downstream router will not be result in temporary forwarding outages because a downstream router
able to override a neighbor's Prune message before the upstream neighbor will not be able to override a neighbor's Prune message before the
stops forwarding. upstream neighbor stops forwarding.
When all routers on a link are in a position to negotiate a different When all routers on a link are in a position to negotiate a
than default Propagation Delay, the largest value from those advertised Propagation Delay different from the default, the largest value from
by each neighbor is chosen. The function for computing the those advertised by each neighbor is chosen. The function for
Effective_Propagation_Delay of interface I is: computing the Effective_Propagation_Delay of interface I is:
time_interval time_interval
Effective_Propagation_Delay(I) { Effective_Propagation_Delay(I) {
if ( lan_delay_enabled(I) == false ) { if ( lan_delay_enabled(I) == false ) {
return Propagation_delay_default return Propagation_delay_default
} }
delay = Propagation_Delay(I) delay = Propagation_Delay(I)
for each neighbor on interface I { for each neighbor on interface I {
if ( neighbor.propagation_delay > delay ) { if ( neighbor.propagation_delay > delay ) {
delay = neighbor.propagation_delay delay = neighbor.propagation_delay
} }
} }
return delay return delay
} }
To avoid synchronization of override messages when multiple downstream To avoid synchronization of override messages when multiple
routers share a multi-access link, sending of such messages is delayed downstream routers share a multi-access link, sending of such
by a small random amount of time. The period of randomization should messages is delayed by a small random amount of time. The period of
represent the size of the PIM router population on the link. Each randomization should represent the size of the PIM router population
router expresses its view of the amount of randomization necessary in on the link. Each router expresses its view of the amount of
the Override Interval field of the LAN Prune Delay option. randomization necessary in the Override Interval field of the LAN
Prune Delay option.
When all routers on a link are in a position to negotiate a different When all routers on a link are in a position to negotiate an Override
than default Override Interval, the largest value from those advertised Interval different from the default, the largest value from those
by each neighbor is chosen. The function for computing the Effective advertised by each neighbor is chosen. The function for computing
Override Interval of interface I is: the Effective Override Interval of interface I is:
time_interval time_interval
Effective_Override_Interval(I) { Effective_Override_Interval(I) {
if ( lan_delay_enabled(I) == false ) { if ( lan_delay_enabled(I) == false ) {
return t_override_default return t_override_default
} }
delay = Override_Interval(I) delay = Override_Interval(I)
for each neighbor on interface I { for each neighbor on interface I {
if ( neighbor.override_interval > delay ) { if ( neighbor.override_interval > delay ) {
delay = neighbor.override_interval delay = neighbor.override_interval
} }
} }
return delay return delay
} }
Although the mechanisms are not specified in this document, it is Although the mechanisms are not specified in this document, it is
possible for upstream routers to explicitly track the join membership of possible for upstream routers to explicitly track the join membership
individual downstream routers if Join suppression is disabled. A router of individual downstream routers if Join suppression is disabled. A
can advertise its willingness to disable Join suppression by using the T router can advertise its willingness to disable Join suppression by
bit in the LAN Prune Delay Hello option. Unless all PIM routers on a using the T bit in the LAN Prune Delay Hello option. Unless all PIM
link negotiate this capability, explicit tracking and the disabling of routers on a link negotiate this capability, explicit tracking and
the Join suppression mechanism are not possible. The function for the disabling of the Join suppression mechanism are not possible.
computing the state of Suppression on interface I is: The function for computing the state of Suppression on interface I
is:
bool bool
Suppression_Enabled(I) { Suppression_Enabled(I) {
if ( lan_delay_enabled(I) == false ) { if ( lan_delay_enabled(I) == false ) {
return true return true
} }
for each neighbor on interface I { for each neighbor on interface I {
if ( neighbor.tracking_support == false ) { if ( neighbor.tracking_support == false ) {
return true return true
} }
} }
return false return false
} }
Note that the setting of Suppression_Enabled(I) affects the value of Note that the setting of Suppression_Enabled(I) affects the value of
t_suppressed (see Section 4.10). t_suppressed (see Section 4.10).
4.3.4. Maintaining Secondary Address Lists 4.3.4. Maintaining Secondary Address Lists
Communication of a router's interface secondary addresses to its PIM Communication of a router's interface secondary addresses to its PIM
neighbors is necessary to provide the neighbors with a mechanism for neighbors is necessary to provide the neighbors with a mechanism for
mapping next_hop information obtained through their MRIB to a primary mapping next_hop information obtained through their MRIB to a primary
address that can be used as a destination for Join/Prune messages. The address that can be used as a destination for Join/Prune messages.
mapping is performed through the NBR macro. The primary address of a The mapping is performed through the NBR macro. The primary address
PIM neighbor is obtained from the source IP address used in its PIM of a PIM neighbor is obtained from the source IP address used in its
Hello messages. Secondary addresses are carried within the Hello message PIM Hello messages. Secondary addresses are carried within the Hello
in an Address List Hello option. The primary address of the source message in an Address List Hello option. The primary address of the
interface of the router MUST NOT be listed within the Address List Hello source interface of the router MUST NOT be listed within the Address
option. List Hello option.
In addition to the information recorded for the DR Election, the In addition to the information recorded for the DR Election, the
following per neighbor information is obtained from the Address List following per neighbor information is obtained from the Address List
Hello option: Hello option:
neighbor.secondary_address_list neighbor.secondary_address_list
The list of secondary addresses used by the PIM neighbor on The list of secondary addresses used by the PIM neighbor on
the interface through which the Hello message was transmitted. the interface through which the Hello message was transmitted.
When processing a received PIM Hello message containing an Address List When processing a received PIM Hello message containing an Address
Hello option, the list of secondary addresses in the message completely List Hello option, the list of secondary addresses in the message
replaces any previously associated secondary addresses for that completely replaces any previously associated secondary addresses for
neighbor. If a received PIM Hello message does not contain an Address that neighbor. If a received PIM Hello message does not contain an
List Hello option then all secondary addresses associated with the Address List Hello option, then all secondary addresses associated
neighbor must be deleted. If a received PIM Hello message contains an with the neighbor must be deleted. If a received PIM Hello message
Address List Hello option that includes the primary address of the contains an Address List Hello option that includes the primary
sending router in the list of secondary addresses (although this is not address of the sending router in the list of secondary addresses
expected) then the addresses listed in the message excluding the primary (although this is not expected), then the addresses listed in the
address are used to update the associated secondary addresses for that message, excluding the primary address, are used to update the
neighbor. associated secondary addresses for that neighbor.
All the advertised secondary addresses in received Hello messages must All the advertised secondary addresses in received Hello messages
be checked against those previously advertised by all other PIM must be checked against those previously advertised by all other PIM
neighbors on that interface. If there is a conflict and the same neighbors on that interface. If there is a conflict and the same
secondary address was previously advertised by another neighbor then secondary address was previously advertised by another neighbor, then
only the most recently received mapping MUST be maintained and an error only the most recently received mapping MUST be maintained, and an
message SHOULD be logged to the administrator in a rate limited manner. error message SHOULD be logged to the administrator in a rate-limited
manner.
Within one Address List Hello option, all the addresses MUST be of the Within one Address List Hello option, all the addresses MUST be of
same address family. It is not permitted to mix IPv4 and IPv6 addresses the same address family. It is not permitted to mix IPv4 and IPv6
within the same message. In addition, the address family of the fields addresses within the same message. In addition, the address family
in the message SHOULD be the same as the IP source and destination of the fields in the message SHOULD be the same as the IP source and
addresses of the packet header. destination addresses of the packet header.
4.4. PIM Register Messages 4.4. PIM Register Messages
Overview The Designated Router (DR) on a LAN or point-to-point link
encapsulates multicast packets from local sources to the RP for the
The Designated Router (DR) on a LAN or point-to-point link encapsulates relevant group unless it recently received a Register-Stop message
multicast packets from local sources to the RP for the relevant group for that (S,G) or (*,G) from the RP. When the DR receives a
unless it recently received a Register-Stop message for that (S,G) or Register-Stop message from the RP, it starts a Register-Stop Timer to
(*,G) from the RP. When the DR receives a Register-Stop message from maintain this state. Just before the Register-Stop Timer expires,
the RP, it starts a Register-Stop Timer to maintain this state. Just the DR sends a Null-Register Message to the RP to allow the RP to
before the Register-Stop Timer expires, the DR sends a Null-Register refresh the Register-Stop information at the DR. If the Register-
Message to the RP to allow the RP to refresh the Register-Stop Stop Timer actually expires, the DR will resume encapsulating packets
information at the DR. If the Register-Stop Timer actually expires, the from the source to the RP.
DR will resume encapsulating packets from the source to the RP.
4.4.1. Sending Register Messages from the DR 4.4.1. Sending Register Messages from the DR
Every PIM-SM router has the capability to be a DR. The state machine Every PIM-SM router has the capability to be a DR. The state machine
below is used to implement Register functionality. For the purposes of below is used to implement Register functionality. For the purposes
specification, we represent the mechanism to encapsulate packets to the of specification, we represent the mechanism to encapsulate packets
RP as a Register-Tunnel interface, which is added to or removed from the to the RP as a Register-Tunnel interface, which is added to or
(S,G) olist. The tunnel interface then takes part in the normal packet removed from the (S,G) olist. The tunnel interface then takes part
forwarding rules as specified in Section 4.2. in the normal packet forwarding rules as specified in Section 4.2.
If register state is maintained, it is maintained only for directly If register state is maintained, it is maintained only for directly
connected sources, and is per-(S,G). There are four states in the DR's connected sources and is per-(S,G). There are four states in the
per-(S,G) Register state machine: DR's per-(S,G) Register state machine:
Join (J) Join (J)
The register tunnel is "joined" (the join is actually implicit, but The register tunnel is "joined" (the join is actually implicit,
the DR acts as if the RP has joined the DR on the tunnel but the DR acts as if the RP has joined the DR on the tunnel
interface). interface).
Prune (P) Prune (P)
The register tunnel is "pruned" (this occurs when a Register-Stop The register tunnel is "pruned" (this occurs when a Register-
is received). Stop is received).
Join-Pending (JP) Join-Pending (JP)
The register tunnel is pruned but the DR is contemplating adding it The register tunnel is pruned but the DR is contemplating adding
back. it back.
NoInfo (NI) NoInfo (NI)
No information. This is the initial state, and the state when the No information. This is the initial state, and the state when
router is not the DR. the router is not the DR.
In addition, a Register-Stop Timer (RST) is kept if the state machine is In addition, a Register-Stop Timer (RST) is kept if the state machine
not in the NoInfo state. is not in the NoInfo state.
Figure 1: Per-(S,G) register state machine at a DR in tabular form Figure 1: Per-(S,G) register state machine at a DR in tabular form
+-----------++---------------------------------------------------------------+ +----------++----------------------------------------------------------+
| || Event | | || Event |
| ++-----------+------------+------------+------------+------------+ | ++----------+-----------+-----------+-----------+-----------+
|Prev State ||Register- | Could | Could | Register- | RP changed | |Prev State||Register- | Could | Could | Register- | RP changed|
| ||Stop Timer | Register | Register | Stop | | | ||Stop Timer| Register | Register | Stop | |
| ||expires | ->True | ->False | received | | | ||expires | ->True | ->False | received | |
+-----------++-----------+------------+------------+------------+------------+ +----------++----------+-----------+-----------+-----------+-----------+
|NoInfo ||- | -> J state | - | - | - | |NoInfo ||- | -> J state| - | - | - |
|(NI) || | add reg | | | | |(NI) || | add reg | | | |
| || | tunnel | | | | | || | tunnel | | | |
+-----------++-----------+------------+------------+------------+------------+ +----------++----------+-----------+-----------+-----------+-----------+
| ||- | - | -> NI | -> P state | -> J state | | ||- | - | -> NI | -> P state| -> J state|
| || | | state | | | | || | | state | | |
| || | | remove reg | remove reg | update reg | | || | | remove reg| remove reg| update reg|
|Join (J) || | | tunnel | tunnel; | tunnel | |Join (J) || | | tunnel | tunnel; | tunnel |
| || | | | set | | | || | | | set | |
| || | | | Register- | | | || | | | Register- | |
| || | | | Stop | | | || | | | Stop | |
| || | | | Timer(*) | | | || | | | Timer(*) | |
+-----------++-----------+------------+------------+------------+------------+ +----------++----------+-----------+-----------+-----------+-----------+
| ||-> J state | - | -> NI | -> P state | -> J state | | ||-> J state| - | -> NI | -> P state| -> J state|
| || | | state | | | | || | | state | | |
|Join- ||add reg | | | set | add reg | |Join- ||add reg | | | set | add reg |
|Pending ||tunnel | | | Register- | tunnel; | |Pending ||tunnel | | | Register- | tunnel; |
|(JP) || | | | Stop | cancel | |(JP) || | | | Stop | cancel |
| || | | | Timer(*) | Register- | | || | | | Timer(*) | Register- |
| || | | | | Stop Timer | | || | | | | Stop Timer|
+-----------++-----------+------------+------------+------------+------------+ +----------++----------+-----------+-----------+-----------+-----------+
| ||-> JP | - | -> NI | - | -> J state | | ||-> JP | - | -> NI | - | -> J state|
| ||state | | state | | | | ||state | | state | | |
| ||set | | | | add reg | | ||set | | | | add reg |
|Prune (P) ||Register- | | | | tunnel; | |Prune (P) ||Register- | | | | tunnel; |
| ||Stop | | | | cancel | | ||Stop | | | | cancel |
| ||Timer(**); | | | | Register- | | ||Timer(**);| | | | Register- |
| ||send Null- | | | | Stop Timer | | ||send Null-| | | | Stop Timer|
| ||Register | | | | | | ||Register | | | | |
+-----------++-----------+------------+------------+------------+------------+ +----------++----------+-----------+-----------+-----------+-----------+
Notes: Notes:
(*) The Register-Stop Timer is set to a random value chosen uniformly (*) The Register-Stop Timer is set to a random value chosen
from the interval ( 0.5 * Register_Suppression_Time, 1.5 * uniformly from the interval ( 0.5 * Register_Suppression_Time,
Register_Suppression_Time) minus Register_Probe_Time; 1.5 * Register_Suppression_Time) minus Register_Probe_Time.
Subtracting off Register_Probe_Time is a bit unnecessary because it Subtracting off Register_Probe_Time is a bit unnecessary because
is really small compared to Register_Suppression_Time, but was in it is really small compared to Register_Suppression_Time, but
the old spec and is kept for compatibility. this was in the old spec and is kept for compatibility.
(**) The Register-Stop Timer is set to Register_Probe_Time. (**) The Register-Stop Timer is set to Register_Probe_Time.
The following actions are defined: The following three actions are defined:
Add Register Tunnel Add Register Tunnel
A Register-Tunnel virtual interface, VI, is created (if it doesn't A Register-Tunnel virtual interface, VI, is created (if it doesn't
already exist) with its encapsulation target being RP(G). already exist) with its encapsulation target being RP(G).
DownstreamJPState(S,G,VI) is set to Join state, causing the tunnel DownstreamJPState(S,G,VI) is set to Join state, causing the tunnel
interface to be added to immediate_olist(S,G) and inherited_olist(S,G). interface to be added to immediate_olist(S,G) and
inherited_olist(S,G).
Remove Register Tunnel Remove Register Tunnel
VI is the Register-Tunnel virtual interface with encapsulation target of VI is the Register-Tunnel virtual interface with encapsulation
RP(G). DownstreamJPState(S,G,VI) is set to NoInfo state, causing the target of RP(G). DownstreamJPState(S,G,VI) is set to NoInfo
tunnel interface to be removed from immediate_olist(S,G) and state, causing the tunnel interface to be removed from
inherited_olist(S,G). If DownstreamJPState(S,G,VI) is NoInfo for all immediate_olist(S,G) and inherited_olist(S,G). If
(S,G), then VI can be deleted. DownstreamJPState(S,G,VI) is NoInfo for all (S,G), then VI can be
deleted.
Update Register Tunnel Update Register Tunnel
This action occurs when RP(G) changes. This action occurs when RP(G) changes.
VI_old is the Register-Tunnel virtual interface with encapsulation VI_old is the Register-Tunnel virtual interface with encapsulation
target old_RP(G). A Register-Tunnel virtual interface, VI_new, is target old_RP(G). A Register-Tunnel virtual interface, VI_new, is
created (if it doesn't already exist) with its encapsulation target created (if it doesn't already exist) with its encapsulation
being new_RP(G). DownstreamJPState(S,G,VI_old) is set to NoInfo state target being new_RP(G). DownstreamJPState(S,G,VI_old) is set to
and DownstreamJPState(S,G,VI_new) is set to Join state. If NoInfo state and DownstreamJPState(S,G,VI_new) is set to Join
DownstreamJPState(S,G,VI_old) is NoInfo for all (S,G), then VI_old can state. If DownstreamJPState(S,G,VI_old) is NoInfo for all (S,G),
be deleted. then VI_old can be deleted.
Note that we can not simply change the encapsulation target of VI_old Note that we cannot simply change the encapsulation target of
because not all groups using that encapsulation tunnel will have moved VI_old because not all groups using that encapsulation tunnel will
to the same new RP. have moved to the same new RP.
CouldRegister(S,G) CouldRegister(S,G)
The macro "CouldRegister" in the state machine is defined as: The macro "CouldRegister" in the state machine is defined as:
bool CouldRegister(S,G) { bool CouldRegister(S,G) {
return ( I_am_DR( RPF_interface(S) ) AND return ( I_am_DR( RPF_interface(S) ) AND
KeepaliveTimer(S,G) is running AND KeepaliveTimer(S,G) is running AND
DirectlyConnected(S) == TRUE ) DirectlyConnected(S) == TRUE )
} }
Note that on reception of a packet at the DR from a directly connected Note that on reception of a packet at the DR from a directly
source, KeepaliveTimer(S,G) needs to be set by the packet forwarding connected source, KeepaliveTimer(S,G) needs to be set by the
rules before computing CouldRegister(S,G) in the register state machine, packet forwarding rules before computing CouldRegister(S,G) in the
or the first packet from a source won't be registered. register state machine, or the first packet from a source won't be
registered.
Encapsulating data packets in the Register Tunnel Encapsulating Data Packets in the Register Tunnel
Conceptually, the Register Tunnel is an interface with a smaller MTU Conceptually, the Register Tunnel is an interface with a smaller
than the underlying IP interface towards the RP. IP fragmentation on MTU than the underlying IP interface towards the RP. IP
packets forwarded on the Register Tunnel is performed based upon this fragmentation on packets forwarded on the Register Tunnel is
smaller MTU. The encapsulating DR may perform Path MTU Discovery to the performed based upon this smaller MTU. The encapsulating DR may
RP to determine the effective MTU of the tunnel. Fragmentation for the perform Path MTU Discovery to the RP to determine the effective
smaller MTU should take both the outer IP header and the PIM register MTU of the tunnel. Fragmentation for the smaller MTU should take
header overhead into account. If a multicast packet is fragmented on both the outer IP header and the PIM register header overhead into
the way into the Register Tunnel, each fragment is encapsulated account. If a multicast packet is fragmented on the way into the
individually so it contains IP, PIM, and inner IP headers. Register Tunnel, each fragment is encapsulated individually so it
contains IP, PIM, and inner IP headers.
In IPv6, the DR MUST perform Path MTU discovery, and an ICMP Packet Too In IPv6, the DR MUST perform Path MTU discovery, and an ICMP
Big message MUST be sent by the encapsulating DR if it receives a packet Packet Too Big message MUST be sent by the encapsulating DR if it
that will not fit in the effective MTU of the tunnel. If the MTU receives a packet that will not fit in the effective MTU of the
between the DR and the RP results in the effective tunnel MTU being tunnel. If the MTU between the DR and the RP results in the
smaller than 1280 (the IPv6 minimum MTU), the DR MUST send Fragmentation effective tunnel MTU being smaller than 1280 (the IPv6 minimum
Required messages with an MTU value of 1280 and MUST fragment its PIM MTU), the DR MUST send Fragmentation Required messages with an MTU
register messages as required, using an IPv6 fragmentation header value of 1280 and MUST fragment its PIM register messages as
between the outer IPv6 header and the PIM Register header. required, using an IPv6 fragmentation header between the outer
IPv6 header and the PIM Register header.
The TTL of a forwarded data packet is decremented before it is The TTL of a forwarded data packet is decremented before it is
encapsulated in the Register Tunnel. The encapsulating packet uses the encapsulated in the Register Tunnel. The encapsulating packet
normal TTL that the router would use for any locally-generated IP uses the normal TTL that the router would use for any locally-
packet. generated IP packet.
The IP ECN bits should be copied from the original packet to the IP The IP ECN bits should be copied from the original packet to the
header of the encapsulating packet. They SHOULD NOT be set IP header of the encapsulating packet. They SHOULD NOT be set
independently by the encapsulating router. independently by the encapsulating router.
The Diffserv Code Point (DSCP) should be copied from the original packet The Diffserv Code Point (DSCP) should be copied from the original
to the IP header of the encapsulating packet. It MAY be set packet to the IP header of the encapsulating packet. It MAY be
independently by the encapsulating router, based upon static set independently by the encapsulating router, based upon static
configuration or traffic classification. See [12] for more discussion configuration or traffic classification. See [12] for more
on setting the DSCP on tunnels. discussion on setting the DSCP on tunnels.
Handling Register-Stop(*,G) Messages at the DR Handling Register-Stop(*,G) Messages at the DR
An old RP might send a Register-Stop message with the source address set An old RP might send a Register-Stop message with the source
to all-zeros. This was the normal course of action in RFC 2362 when the address set to all zeros. This was the normal course of action in
Register message matched against (*,G) state at the RP, and was defined RFC 2362 when the Register message matched against (*,G) state at
as meaning "stop encapsulating all sources for this group". However, the RP, and it was defined as meaning "stop encapsulating all
the behavior of such a Register-Stop(*,G) is ambiguous or incorrect in sources for this group". However, the behavior of such a
some circumstances. Register-Stop(*,G) is ambiguous or incorrect in some
circumstances.
We specify that an RP should not send Register-Stop(*,G) messages, but We specify that an RP should not send Register-Stop(*,G) messages,
for compatibility, a DR should be able to accept one if it is received. but for compatibility, a DR should be able to accept one if it is
received.
A Register-Stop(*,G) should be treated as a Register-Stop(S,G) for all A Register-Stop(*,G) should be treated as a Register-Stop(S,G) for
(S,G) Register state machines that are not in the NoInfo state. A all (S,G) Register state machines that are not in the NoInfo
router should not apply a Register-Stop(*,G) to sources that become state. A router should not apply a Register-Stop(*,G) to sources
active after the Register-Stop(*,G) was received. that become active after the Register-Stop(*,G) was received.
4.4.2. Receiving Register Messages at the RP 4.4.2. Receiving Register Messages at the RP
When an RP receives a Register message, the course of action is decided When an RP receives a Register message, the course of action is
according to the following pseudocode: decided according to the following pseudocode:
packet_arrives_on_rp_tunnel( pkt ) { packet_arrives_on_rp_tunnel( pkt ) {
if( outer.dst is not one of my addresses ) { if( outer.dst is not one of my addresses ) {
drop the packet silently. drop the packet silently.
# Note: this may be a spoofing attempt # Note: this may be a spoofing attempt
} }
if( I_am_RP(G) AND outer.dst == RP(G) ) { if( I_am_RP(G) AND outer.dst == RP(G) ) {
sentRegisterStop = FALSE; sentRegisterStop = FALSE;
if ( register.borderbit == TRUE ) { if ( register.borderbit == TRUE ) {
if ( PMBR(S,G) == unknown ) { if ( PMBR(S,G) == unknown ) {
PMBR(S,G) = outer.src PMBR(S,G) = outer.src
} else if ( outer.src != PMBR(S,G) ) { } else if ( outer.src != PMBR(S,G) ) {
send Register-Stop(S,G) to outer.src send Register-Stop(S,G) to outer.src
drop the packet silently. drop the packet silently.
} }
} }
if ( SPTbit(S,G) OR if ( SPTbit(S,G) OR
( SwitchToSptDesired(S,G) AND ( inherited_olist(S,G) == NULL ))) { ( SwitchToSptDesired(S,G) AND
send Register-Stop(S,G) to outer.src ( inherited_olist(S,G) == NULL ))) {
sentRegisterStop = TRUE; send Register-Stop(S,G) to outer.src
} sentRegisterStop = TRUE;
if ( SPTbit(S,G) OR SwitchToSptDesired(S,G) ) { }
if ( sentRegisterStop == TRUE ) { if ( SPTbit(S,G) OR SwitchToSptDesired(S,G) ) {
set KeepaliveTimer(S,G) to RP_Keepalive_Period; if ( sentRegisterStop == TRUE ) {
} else { set KeepaliveTimer(S,G) to RP_Keepalive_Period;
set KeepaliveTimer(S,G) to Keepalive_Period; } else {
} set KeepaliveTimer(S,G) to Keepalive_Period;
} }
if( !SPTbit(S,G) AND ! pkt.NullRegisterBit ) { }
decapsulate and forward the inner packet to if( !SPTbit(S,G) AND ! pkt.NullRegisterBit ) {
inherited_olist(S,G,rpt) # Note (+) decapsulate and forward the inner packet to
} inherited_olist(S,G,rpt) # Note (+)
} else { }
send Register-Stop(S,G) to outer.src } else {
# Note (*) send Register-Stop(S,G) to outer.src
} # Note (*)
} }
}
outer.dst is the IP destination address of the encapsulating header. outer.dst is the IP destination address of the encapsulating header.
outer.src is the IP source address of the encapsulating header, i.e., outer.src is the IP source address of the encapsulating header, i.e.,
the DR's address. the DR's address.
I_am_RP(G) is true if the group-to-RP mapping indicates that this router I_am_RP(G) is true if the group-to-RP mapping indicates that this
is the RP for the group. router is the RP for the group.
Note (*): This may block traffic from S for Register_Suppression_Time if Note (*): This may block traffic from S for Register_Suppression_Time
the DR learned about a new group-to-RP mapping before the RP did. if the DR learned about a new group-to-RP mapping before the RP
However, this doesn't matter unless we figure out some way for the did. However, this doesn't matter unless we figure out some way
RP to also accept (*,G) joins when it doesn't yet realize that it for the RP also to accept (*,G) joins when it doesn't yet realize
is about to become the RP for G. This will all get sorted out once that it is about to become the RP for G. This will all get sorted
the RP learns the new group-to-rp mapping. We decided to do out once the RP learns the new group-to-rp mapping. We decided to
nothing about this and just accept the fact that PIM may suffer do nothing about this and just accept the fact that PIM may suffer
interrupted (*,G) connectivity following an RP change. interrupted (*,G) connectivity following an RP change.
Note (+): Implementations are advised to not make this a special case, Note (+): Implementations are advised not to make this a special
but to arrange that this path rejoin the normal packet forwarding case, but to arrange that this path rejoin the normal packet
path. All of the appropriate actions from the "On receipt of data forwarding path. All of the appropriate actions from the "On
from S to G on interface iif" pseudocode in Section 4.2 should be receipt of data from S to G on interface iif" pseudocode in
performed. Section 4.2 should be performed.
KeepaliveTimer(S,G) is restarted at the RP when packets arrive on the KeepaliveTimer(S,G) is restarted at the RP when packets arrive on the
proper tunnel interface and the RP desires to switch to the SPT or the proper tunnel interface and the RP desires to switch to the SPT or
SPTbit is already set. This may cause the upstream (S,G) state machine the SPTbit is already set. This may cause the upstream (S,G) state
to trigger a join if the inherited_olist(S,G) is not NULL; machine to trigger a join if the inherited_olist(S,G) is not NULL.
An RP should preserve (S,G) state that was created in response to a An RP should preserve (S,G) state that was created in response to a
Register message for at least ( 3 * Register_Suppression_Time ), Register message for at least ( 3 * Register_Suppression_Time );
otherwise the RP may stop joining (S,G) before the DR for S has otherwise, the RP may stop joining (S,G) before the DR for S has
restarted sending registers. Traffic would then be interrupted until restarted sending registers. Traffic would then be interrupted until
the Register-Stop Timer expires at the DR. the Register-Stop Timer expires at the DR.
Thus, at the RP, KeepaliveTimer(S,G) should be restarted to ( 3 * Thus, at the RP, KeepaliveTimer(S,G) should be restarted to ( 3 *
Register_Suppression_Time + Register_Probe_Time ). Register_Suppression_Time + Register_Probe_Time ).
When forwarding a packet from the Register Tunnel, the TTL of the When forwarding a packet from the Register Tunnel, the TTL of the
original data packet is decremented after it is decapsulated. original data packet is decremented after it is decapsulated.
The IP ECN bits should be copied from the IP header of the Register The IP ECN bits should be copied from the IP header of the Register
packet to the decapsulated packet. packet to the decapsulated packet.
The Diffserv Code Point (DSCP) should be copied from the IP header of The Diffserv Code Point (DSCP) should be copied from the IP header of
the Register packet to the decapsulated packet. The RP MAY retain the the Register packet to the decapsulated packet. The RP MAY retain
DSCP of the inner packet, or re-classify the packet and apply a the DSCP of the inner packet or re-classify the packet and apply a
different DSCP. Scenarios where each of these might be useful are different DSCP. Scenarios where each of these might be useful are
discussed in [12]. discussed in [12].
4.5. PIM Join/Prune Messages 4.5. PIM Join/Prune Messages
A PIM Join/Prune message consists of a list of groups and a list of A PIM Join/Prune message consists of a list of groups and a list of
Joined and Pruned sources for each group. When processing a received Joined and Pruned sources for each group. When processing a received
Join/Prune message, each Joined or Pruned source for a Group is Join/Prune message, each Joined or Pruned source for a Group is
effectively considered individually, and applies to one or more of the effectively considered individually, and applies to one or more of
following state machines. When considering a Join/Prune message whose the following state machines. When considering a Join/Prune message
Upstream Neighbor Address field addresses this router, (*,G) Joins and whose Upstream Neighbor Address field addresses this router, (*,G)
Prunes can affect both the (*,G) and (S,G,rpt) downstream state Joins and Prunes can affect both the (*,G) and (S,G,rpt) downstream
machines, while (*,*,RP), (S,G) and (S,G,rpt) Joins and Prunes can only state machines, while (*,*,RP), (S,G), and (S,G,rpt) Joins and Prunes
affect their respective downstream state machines. When considering a can only affect their respective downstream state machines. When
Join/Prune message whose Upstream Neighbor Address field addresses considering a Join/Prune message whose Upstream Neighbor Address
another router, most Join or Prune messages could affect each upstream field addresses another router, most Join or Prune messages could
state machine. affect each upstream state machine.
In general, a PIM Join/Prune message should only be accepted for In general, a PIM Join/Prune message should only be accepted for
processing if it comes from a known PIM neighbor. A PIM router hears processing if it comes from a known PIM neighbor. A PIM router hears
about PIM neighbors through PIM Hello messages. If a router receives a about PIM neighbors through PIM Hello messages. If a router receives
Join/Prune message from a particular IP source address and it has not a Join/Prune message from a particular IP source address and it has
seen a PIM Hello message from that source address, then the Join/Prune not seen a PIM Hello message from that source address, then the
message SHOULD be discarded without further processing. In addition, if Join/Prune message SHOULD be discarded without further processing.
the Hello message from a neighbor was authenticated using IPsec AH (see In addition, if the Hello message from a neighbor was authenticated
Section 6.3) then all Join/Prune messages from that neighbor MUST also using IPsec AH (see Section 6.3), then all Join/Prune messages from
be authenticated using IPsec AH. that neighbor MUST also be authenticated using IPsec AH.
We note that some older PIM implementations incorrectly fail to send We note that some older PIM implementations incorrectly fail to send
Hello messages on point-to-point interfaces, so we also RECOMMEND that a Hello messages on point-to-point interfaces, so we also RECOMMEND
configuration option be provided to allow interoperation with such older that a configuration option be provided to allow interoperation with
routers, but that this configuration option SHOULD NOT be enabled by such older routers, but that this configuration option SHOULD NOT be
default. enabled by default.
4.5.1. Receiving (*,*,RP) Join/Prune Messages 4.5.1. Receiving (*,*,RP) Join/Prune Messages
The per-interface state machine for receiving (*,*,RP) Join/Prune The per-interface state machine for receiving (*,*,RP) Join/Prune
Messages is given below. There are three states: Messages is given below. There are three states:
NoInfo (NI) NoInfo (NI)
The interface has no (*,*,RP) Join state and no timers The interface has no (*,*,RP) Join state and no timers
running. running.
Join (J) Join (J)
The interface has (*,*,RP) Join state which will cause the The interface has (*,*,RP) Join state, which will cause the
router to forward packets destined for any group handled by RP router to forward packets destined for any group handled by RP
from this interface except if there is also (S,G,rpt) prune from this interface except if there is also (S,G,rpt) prune
information (see Section 4.5.4) or the router lost an assert information (see Section 4.5.4) or the router lost an assert
on this interface. on this interface.
Prune-Pending (PP) Prune-Pending (PP)
The router has received a Prune(*,*,RP) on this interface from The router has received a Prune(*,*,RP) on this interface from
a downstream neighbor and is waiting to see whether the prune a downstream neighbor and is waiting to see whether the prune
will be overridden by another downstream router. For will be overridden by another downstream router. For
forwarding purposes, the Prune-Pending state functions exactly forwarding purposes, the Prune-Pending state functions exactly
like the Join state. like the Join state.
In addition, the state machine uses two timers: In addition, the state machine uses two timers:
ExpiryTimer (ET) ExpiryTimer (ET)
This timer is restarted when a valid Join(*,*,RP) is received. This timer is restarted when a valid Join(*,*,RP) is received.
Expiry of the ExpiryTimer causes the interface state to revert Expiry of the ExpiryTimer causes the interface state to revert
to NoInfo for this RP. to NoInfo for this RP.
Prune-Pending Timer (PPT) Prune-Pending Timer (PPT)
This timer is set when a valid Prune(*,*,RP) is received. This timer is set when a valid Prune(*,*,RP) is received.
Expiry of the Prune-Pending Timer causes the interface state Expiry of the Prune-Pending Timer causes the interface state
to revert to NoInfo for this RP. to revert to NoInfo for this RP.
Figure 2: Downstream per-interface (*,*,RP) state machine in tabular form Figure 2: Downstream per-interface (*,*,RP) state machine
in tabular form
+-------------++----------------------------------------------------------+
| || Event |
| ++-------------+--------------+--------------+--------------+
|Prev State ||Receive | Receive | Prune- | Expiry Timer |
| ||Join(*,*,RP) | Prune | Pending | Expires |
| || | (*,*,RP) | Timer | |
| || | | Expires | |
+-------------++-------------+--------------+--------------+--------------+
| ||-> J state | -> NI state | - | - |
|NoInfo (NI) ||start Expiry | | | |
| ||Timer | | | |
+-------------++-------------+--------------+--------------+--------------+
| ||-> J state | -> PP state | - | -> NI state |
|Join (J) ||restart | start Prune- | | |
| ||Expiry Timer | Pending | | |
| || | Timer | | |
+-------------++-------------+--------------+--------------+--------------+
|Prune- ||-> J state | -> PP state | -> NI state | -> NI state |
|Pending (PP) ||restart | | Send Prune- | |
| ||Expiry Timer | | Echo(*,*,RP) | |
+-------------++-------------+--------------+--------------+--------------+
The transition events "Receive Join(*,*,RP)" and "Receive Prune(*,*,RP)" +------------++--------------------------------------------------------+
imply receiving a Join or Prune targeted to this router's primary IP | || Event |
address on the received interface. If the upstream neighbor address | ++-------------+-------------+--------------+-------------+
field is not correct, these state transitions in this state machine must |Prev State ||Receive | Receive | Prune- | Expiry Timer|
not occur, although seeing such a packet may cause state transitions in | ||Join(*,*,RP) | Prune | Pending | Expires |
other state machines. | || | (*,*,RP) | Timer | |
| || | | Expires | |
+------------++-------------+-------------+--------------+-------------+
| ||-> J state | -> NI state | - | - |
|NoInfo (NI) ||start Expiry | | | |
| ||Timer | | | |
+------------++-------------+-------------+--------------+-------------+
| ||-> J state | -> PP state | - | -> NI state |
|Join (J) ||restart | start Prune-| | |
| ||Expiry Timer | Pending | | |
| || | Timer | | |
+------------++-------------+-------------+--------------+-------------+
|Prune- ||-> J state | -> PP state | -> NI state | -> NI state |
|Pending (PP)||restart | | Send Prune- | |
| ||Expiry Timer | | Echo(*,*,RP) | |
+------------++-------------+-------------+--------------+-------------+
The transition events "Receive Join(*,*,RP)" and "Receive
Prune(*,*,RP)" imply receiving a Join or Prune targeted to this
router's primary IP address on the received interface. If the
upstream neighbor address field is not correct, these state
transitions in 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 On unnumbered interfaces on point-to-point links, the router's
should be the same as the source address it chose for the Hello message address should be the same as the source address it chose for the
it sent over that interface. However on point-to-point links we also Hello message it sent over that interface. However, on point-to-
recommend that for backwards compatibility PIM Join/Prune messages with point links we also recommend that for backwards compatibility PIM
a upstream neighbor address field of all zeros are also accepted. Join/Prune messages with an upstream neighbor address field of all
zeros are also accepted.
Transitions from NoInfo State Transitions from NoInfo State
When in NoInfo state, the following event may trigger a transition: When in NoInfo state, the following event may trigger a transition:
Receive Join(*,*,RP) Receive Join(*,*,RP)
A Join(*,*,RP) is received on interface I with its Upstream A Join(*,*,RP) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (*,*,RP) downstream state machine on interface I The (*,*,RP) downstream state machine on interface I
transitions to the Join state. The Expiry Timer (ET) is transitions to the Join state. The Expiry Timer (ET) is
started, and set to the HoldTime from the triggering started and set to the HoldTime from the triggering Join/Prune
Join/Prune message. message.
Note that it is possible to receive a Join(*,*,RP) message for Note that it is possible to receive a Join(*,*,RP) message for
an RP that we do not have information telling us that it is an an RP for which we do not have information telling us that it
RP. In the case of (*,*,RP) state, so long as we have a route is an RP. In the case of (*,*,RP) state, so long as we have a
to the RP, this will not cause a problem, and the transition route to the RP, this will not cause a problem, and the
should still take place. transition should still take place.
Transitions from Join State Transitions from Join State
When in Join state, the following events may trigger a transition: When in Join state, the following events may trigger a transition:
Receive Join(*,*,RP) Receive Join(*,*,RP)
A Join(*,*,RP) is received on interface I with its Upstream A Join(*,*,RP) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (*,*,RP) downstream state machine on interface I remains The (*,*,RP) downstream state machine on interface I remains
in Join state, and the Expiry Timer (ET) is restarted, set to in Join state, and the Expiry Timer (ET) is restarted, set to
maximum of its current value and the HoldTime from the maximum of its current value and the HoldTime from the
triggering Join/Prune message. triggering Join/Prune message.
Receive Prune(*,*,RP) Receive Prune(*,*,RP)
A Prune(*,*,RP) is received on interface I with its Upstream A Prune(*,*,RP) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (*,*,RP) downstream state machine on interface I The (*,*,RP) downstream state machine on interface I
transitions to the Prune-Pending state. The Prune-Pending transitions to the Prune-Pending state. The Prune-Pending
Timer is started; it is set to the J/P_Override_Interval(I) if Timer is started. It is set to the J/P_Override_Interval(I)
the router has more than one neighbor on that interface; if the router has more than one neighbor on that interface;
otherwise it is set to zero causing it to expire immediately. otherwise, it is set to zero, causing it to expire
immediately.
Expiry Timer Expires Expiry Timer Expires
The Expiry Timer for the (*,*,RP) downstream state machine on The Expiry Timer for the (*,*,RP) downstream state machine on
interface I expires. interface I expires.
The (*,*,RP) downstream state machine on interface I The (*,*,RP) downstream state machine on interface I
transitions to the NoInfo state. transitions to the NoInfo state.
Transitions from Prune-Pending State Transitions from Prune-Pending State
When in Prune-Pending state, the following events may trigger a When in Prune-Pending state, the following events may trigger a
transition: transition:
Receive Join(*,*,RP) Receive Join(*,*,RP)
A Join(*,*,RP) is received on interface I with its Upstream A Join(*,*,RP) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (*,*,RP) downstream state machine on interface I The (*,*,RP) downstream state machine on interface I
transitions to the Join state. The Prune-Pending Timer is transitions to the Join state. The Prune-Pending Timer is
canceled (without triggering an expiry event). The Expiry canceled (without triggering an expiry event). The Expiry
Timer is restarted, set to maximum of its current value and Timer is restarted, set to maximum of its current value and
the HoldTime from the triggering Join/Prune message. the HoldTime from the triggering Join/Prune message.
skipping to change at page 49, line 7 skipping to change at page 49, line 19
the Upstream Neighbor Address field. Its purpose is to add the Upstream Neighbor Address field. Its purpose is to add
additional reliability so that if a Prune that should have additional reliability so that if a Prune that should have
been overridden by another router is lost locally on the LAN, been overridden by another router is lost locally on the LAN,
then the PruneEcho may be received and cause the override to then the PruneEcho may be received and cause the override to
happen. A PruneEcho(*,*,RP) need not be sent on an interface happen. A PruneEcho(*,*,RP) need not be sent on an interface
that contains only a single PIM neighbor during the time this that contains only a single PIM neighbor during the time this
state machine was in Prune-Pending state. state machine was in Prune-Pending state.
4.5.2. Receiving (*,G) Join/Prune Messages 4.5.2. Receiving (*,G) Join/Prune Messages
When a router receives a Join(*,G) it must first check to see whether When a router receives a Join(*,G), it must first check to see
the RP in the message matches RP(G) (the router's idea of who the RP whether the RP in the message matches RP(G) (the router's idea of who
is). If the RP in the message does not match RP(G) the Join(*,G) should the RP is). If the RP in the message does not match RP(G), the
be silently dropped. (Note that other source list entries such as Join(*,G) should be silently dropped. (Note that other source list
(S,G,rpt) or (S,G) in the same Group Specific Set should still be entries, such as (S,G,rpt) or (S,G), in the same Group-Specific Set
processed.) If a router has no RP information (e.g. has not recently should still be processed.) If a router has no RP information (e.g.,
received a BSR message) then it may choose to accept Join(*,G) and treat has not recently received a BSR message), then it may choose to
the RP in the message as RP(G). Received Prune(*,G) messages are accept Join(*,G) and treat the RP in the message as RP(G). Received
processed even if the RP in the message does not match RP(G). Prune(*,G) messages are processed even if the RP in the message does
not match RP(G).
The per-interface state machine for receiving (*,G) Join/Prune Messages The per-interface state machine for receiving (*,G) Join/Prune
is given below. There are three states: Messages 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 the router The interface has (*,G) Join state, which will cause the
to forward packets destined for G from this interface except router to forward packets destined for G from this interface
if there is also (S,G,rpt) prune information (see Section except if there is also (S,G,rpt) prune information (see
4.5.4) or the router lost an assert on this interface. Section 4.5.4) or the router lost an assert on this interface.
Prune-Pending (PP) Prune-Pending (PP)
The router has received a Prune(*,G) on this interface from a The router has received a Prune(*,G) on this interface from a
downstream neighbor and is waiting to see whether the prune downstream neighbor and is waiting to see whether the prune
will be overridden by another downstream router. For will be overridden by another downstream router. For
forwarding purposes, the Prune-Pending state functions exactly forwarding purposes, the Prune-Pending state functions exactly
like the Join state. like the Join state.
In addition, the state machine uses two timers: In addition, the state machine uses two timers:
Expiry Timer (ET) Expiry Timer (ET)
This timer is restarted when a valid Join(*,G) is received. This timer is restarted when a valid Join(*,G) is received.
Expiry of the Expiry Timer causes the interface state to Expiry of the Expiry Timer causes the interface state to
revert to NoInfo for this group. revert to NoInfo for this group.
Prune-Pending Timer (PPT) Prune-Pending Timer (PPT)
This timer is set when a valid Prune(*,G) is received. Expiry This timer is set when a valid Prune(*,G) is received. Expiry
of the Prune-Pending Timer causes the interface state to of the Prune-Pending Timer causes the interface state to
revert to NoInfo for this group. revert to NoInfo for this group.
Figure 3: Downstream per-interface (*,G) state machine in tabular form Figure 3: Downstream per-interface (*,G) state machine in tabular form
+-------------++---------------------------------------------------------+ +------------++--------------------------------------------------------+
| || Event | | || Event |
| ++-------------+--------------+-------------+--------------+ | ++-------------+--------------+-------------+-------------+
|Prev State ||Receive | Receive | Prune- | Expiry Timer | |Prev State ||Receive | Receive | Prune- | Expiry Timer|
| ||Join(*,G) | Prune(*,G) | Pending | Expires | | ||Join(*,G) | Prune(*,G) | Pending | Expires |
| || | | Timer | | | || | | Timer | |
| || | | Expires | | | || | | Expires | |
+-------------++-------------+--------------+-------------+--------------+ +------------++-------------+--------------+-------------+-------------+
| ||-> J state | -> NI state | - | - | | ||-> J state | -> NI state | - | - |
|NoInfo (NI) ||start Expiry | | | | |NoInfo (NI) ||start Expiry | | | |
| ||Timer | | | | | ||Timer | | | |
+-------------++-------------+--------------+-------------+--------------+ +------------++-------------+--------------+-------------+-------------+
| ||-> J state | -> PP state | - | -> NI state | | ||-> J state | -> PP state | - | -> NI state |
|Join (J) ||restart | start Prune- | | | |Join (J) ||restart | start Prune- | | |
| ||Expiry Timer | Pending | | | | ||Expiry Timer | Pending | | |
| || | Timer | | | | || | Timer | | |
+-------------++-------------+--------------+-------------+--------------+ +------------++-------------+--------------+-------------+-------------+
|Prune- ||-> J state | -> PP state | -> NI state | -> NI state | |Prune- ||-> J state | -> PP state | -> NI state | -> NI state |
|Pending (PP) ||restart | | Send Prune- | | |Pending (PP)||restart | | Send Prune- | |
| ||Expiry Timer | | Echo(*,G) | | | ||Expiry Timer | | Echo(*,G) | |
+-------------++-------------+--------------+-------------+--------------+ +------------++-------------+--------------+-------------+-------------+
The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" imply The transition events "Receive Join(*,G)" and "Receive Prune(*,G)"
receiving a Join or Prune targeted to this router's primary IP address imply receiving a Join or Prune targeted to this router's primary IP
on the received interface. If the upstream neighbor address field is address on the received interface. If the upstream neighbor address
not correct, these state transitions in this state machine must not field is not correct, these state transitions in this state machine
occur, although seeing such a packet may cause state transitions in must not occur, although seeing such a packet may cause state
other state machines. transitions in other state machines.
On unnumbered interfaces on point-to-point links, the router's address On unnumbered interfaces on point-to-point links, the router's
should be the same as the source address it chose for the Hello message address should be the same as the source address it chose for the
it sent over that interface. However on point-to-point links we also Hello message it sent over that interface. However, on point-to-
recommend that for backwards compatibility PIM Join/Prune messages with point links we also recommend that for backwards compatibility PIM
a upstream neighbor address field of all zeros are also accepted. Join/Prune messages with an upstream neighbor address field of all
zeros are also accepted.
Transitions from NoInfo State Transitions from NoInfo State
When in NoInfo state, the following event may trigger a transition: When in NoInfo state, the following event may trigger a transition:
Receive Join(*,G) Receive Join(*,G)
A Join(*,G) is received on interface I with its Upstream A Join(*,G) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (*,G) downstream state machine on interface I transitions The (*,G) downstream state machine on interface I transitions
to the Join state. The Expiry Timer (ET) is started, and set to the Join state. The Expiry Timer (ET) is started and set
to the HoldTime from the triggering Join/Prune message. to the HoldTime from the triggering Join/Prune message.
Transitions from Join State Transitions from Join State
When in Join state, the following events may trigger a transition: When in Join state, the following events may trigger a transition:
Receive Join(*,G) Receive Join(*,G)
A Join(*,G) is received on interface I with its Upstream A Join(*,G) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (*,G) downstream state machine on interface I remains in The (*,G) downstream state machine on interface I remains in
Join state, and the Expiry Timer (ET) is restarted, set to Join state, and the Expiry Timer (ET) is restarted, set to
maximum of its current value and the HoldTime from the maximum of its current value and the HoldTime from the
triggering Join/Prune message. triggering Join/Prune message.
Receive Prune(*,G) Receive Prune(*,G)
A Prune(*,G) is received on interface I with its Upstream A Prune(*,G) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (*,G) downstream state machine on interface I transitions The (*,G) downstream state machine on interface I transitions
to the Prune-Pending state. The Prune-Pending Timer is to the Prune-Pending state. The Prune-Pending Timer is
started; it is set to the J/P_Override_Interval(I) if the started. It is set to the J/P_Override_Interval(I) if the
router has more than one neighbor on that interface; otherwise router has more than one neighbor on that interface;
it is set to zero causing it to expire immediately. otherwise, it is set to zero, causing it to expire
immediately.
Expiry Timer Expires Expiry Timer Expires
The Expiry Timer for the (*,G) downstream state machine on The Expiry Timer for the (*,G) downstream state machine on
interface I expires. interface I expires.
The (*,G) downstream state machine on interface I transitions The (*,G) downstream state machine on interface I transitions
to the NoInfo state. to the NoInfo state.
Transitions from Prune-Pending State Transitions from Prune-Pending State
When in Prune-Pending state, the following events may trigger a When in Prune-Pending state, the following events may trigger a
transition: transition:
Receive Join(*,G) Receive Join(*,G)
A Join(*,G) is received on interface I with its Upstream A Join(*,G) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (*,G) downstream state machine on interface I transitions The (*,G) downstream state machine on interface I transitions
to the Join state. The Prune-Pending Timer is canceled to the Join state. The Prune-Pending Timer is canceled
(without triggering an expiry event). The Expiry Timer is (without triggering an expiry event). The Expiry Timer is
restarted, set to maximum of its current value and the restarted, set to maximum of its current value and the
HoldTime from the triggering Join/Prune message. HoldTime from the triggering Join/Prune message.
skipping to change at page 52, line 30 skipping to change at page 53, line 7
Neighbor Address field. Its purpose is to add additional Neighbor Address field. Its purpose is to add additional
reliability so that if a Prune that should have been reliability so that if a Prune that should have been
overridden by another router is lost locally on the LAN, then overridden by another router is lost locally on the LAN, then
the PruneEcho may be received and cause the override to the PruneEcho may be received and cause the override to
happen. A PruneEcho(*,G) need not be sent on an interface happen. A PruneEcho(*,G) need not be sent on an interface
that contains only a single PIM neighbor during the time this that contains only a single PIM neighbor during the time this
state machine was in Prune-Pending state. state machine was in Prune-Pending state.
4.5.3. Receiving (S,G) Join/Prune Messages 4.5.3. Receiving (S,G) Join/Prune Messages
The per-interface state machine for receiving (S,G) Join/Prune messages The per-interface state machine for receiving (S,G) Join/Prune
is given below, and is almost identical to that for (*,G) messages. messages is given below and is almost identical to that for (*,G)
There are three states: messages. There are three states:
NoInfo (NI) NoInfo (NI)
The interface has no (S,G) Join state and no (S,G) timers The interface has no (S,G) Join state and no (S,G) timers
running. running.
Join (J) Join (J)
The interface has (S,G) Join state which will cause the router The interface has (S,G) Join state, which will cause the
to forward packets from S destined for G from this interface router to forward packets from S destined for G from this
if the (S,G) state is active (the SPTbit is set) except if the interface if the (S,G) state is active (the SPTbit is set)
router lost an assert on this interface. except if the router lost an assert on this interface.
Prune-Pending (PP) Prune-Pending (PP)
The router has received a Prune(S,G) on this interface from a The router has received a Prune(S,G) on this interface from a
downstream neighbor and is waiting to see whether the prune downstream neighbor and is waiting to see whether the prune
will be overridden by another downstream router. For will be overridden by another downstream router. For
forwarding purposes, the Prune-Pending state functions exactly forwarding purposes, the Prune-Pending state functions exactly
like the Join state. like the Join state.
In addition, there are two timers: In addition, there are two timers:
Expiry Timer (ET) Expiry Timer (ET)
This timer is set when a valid Join(S,G) is received. Expiry This timer is set when a valid Join(S,G) is received. Expiry
of the Expiry Timer causes this state machine to revert to of the Expiry Timer causes this state machine to revert to
NoInfo state. NoInfo state.
Prune-Pending Timer (PPT) Prune-Pending Timer (PPT)
This timer is set when a valid Prune(S,G) is received. Expiry This timer is set when a valid Prune(S,G) is received. Expiry
of the Prune-Pending Timer causes this state machine to revert of the Prune-Pending Timer causes this state machine to revert
to NoInfo state. to NoInfo state.
Figure 4: Downstream per-interface (S,G) state machine in tabular form Figure 4: Downstream per-interface (S,G) state machine in tabular form
+-------------++---------------------------------------------------------+ +------------++--------------------------------------------------------+
| || Event | | || Event |
| ++-------------+--------------+-------------+--------------+ | ++-------------+--------------+-------------+-------------+
|Prev State ||Receive | Receive | Prune- | Expiry Timer | |Prev State ||Receive | Receive | Prune- | Expiry Timer|
| ||Join(S,G) | Prune(S,G) | Pending | Expires | | ||Join(S,G) | Prune(S,G) | Pending | Expires |
| || | | Timer | | | || | | Timer | |
| || | | Expires | | | || | | Expires | |
+-------------++-------------+--------------+-------------+--------------+ +------------++-------------+--------------+-------------+-------------+
| ||-> J state | -> NI state | - | - | | ||-> J state | -> NI state | - | - |
|NoInfo (NI) ||start Expiry | | | | |NoInfo (NI) ||start Expiry | | | |
| ||Timer | | | | | ||Timer | | | |
+-------------++-------------+--------------+-------------+--------------+ +------------++-------------+--------------+-------------+-------------+
| ||-> J state | -> PP state | - | -> NI state | | ||-> J state | -> PP state | - | -> NI state |
|Join (J) ||restart | start Prune- | | | |Join (J) ||restart | start Prune- | | |
| ||Expiry Timer | Pending | | | | ||Expiry Timer | Pending | | |
| || | Timer | | | | || | Timer | | |
+-------------++-------------+--------------+-------------+--------------+ +------------++-------------+--------------+-------------+-------------+
|Prune- ||-> J state | -> PP state | -> NI state | -> NI state | |Prune- ||-> J state | -> PP state | -> NI state | -> NI state |
|Pending (PP) ||restart | | Send Prune- | | |Pending (PP)||restart | | Send Prune- | |
| ||Expiry Timer | | Echo(S,G) | | | ||Expiry Timer | | Echo(S,G) | |
+-------------++-------------+--------------+-------------+--------------+ +------------++-------------+--------------+-------------+-------------+
The transition events "Receive Join(S,G)" and "Receive Prune(S,G)" imply The transition events "Receive Join(S,G)" and "Receive Prune(S,G)"
receiving a Join or Prune targeted to this router's primary IP address imply receiving a Join or Prune targeted to this router's primary IP
on the received interface. If the upstream neighbor address field is address on the received interface. If the upstream neighbor address
not correct, these state transitions in this state machine must not field is not correct, these state transitions in this state machine
occur, although seeing such a packet may cause state transitions in must not occur, although seeing such a packet may cause state
other state machines. transitions in other state machines.
On unnumbered interfaces on point-to-point links, the router's address On unnumbered interfaces on point-to-point links, the router's
should be the same as the source address it chose for the Hello message address should be the same as the source address it chose for the
it sent over that interface. However on point-to-point links we also Hello message it sent over that interface. However, on point-to-
recommend that for backwards compatibility PIM Join/Prune messages with point links we also recommend that for backwards compatibility PIM
a upstream neighbor address field of all zeros are also accepted. Join/Prune messages with an upstream neighbor address field of all
zeros are also accepted.
Transitions from NoInfo State Transitions from NoInfo State
When in NoInfo state, the following event may trigger a transition: When in NoInfo state, the following event may trigger a transition:
Receive Join(S,G) Receive Join(S,G)
A Join(S,G) is received on interface I with its Upstream A Join(S,G) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (S,G) downstream state machine on interface I transitions The (S,G) downstream state machine on interface I transitions
to the Join state. The Expiry Timer (ET) is started, and set to the Join state. The Expiry Timer (ET) is started and set
to the HoldTime from the triggering Join/Prune message. to the HoldTime from the triggering Join/Prune message.
Transitions from Join State Transitions from Join State
When in Join state, the following events may trigger a transition: When in Join state, the following events may trigger a transition:
Receive Join(S,G) Receive Join(S,G)
A Join(S,G) is received on interface I with its Upstream A Join(S,G) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (S,G) downstream state machine on interface I remains in The (S,G) downstream state machine on interface I remains in
Join state, and the Expiry Timer (ET) is restarted, set to Join state, and the Expiry Timer (ET) is restarted, set to
maximum of its current value and the HoldTime from the maximum of its current value and the HoldTime from the
triggering Join/Prune message. triggering Join/Prune message.
Receive Prune(S,G) Receive Prune(S,G)
A Prune(S,G) is received on interface I with its Upstream A Prune(S,G) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (S,G) downstream state machine on interface I transitions The (S,G) downstream state machine on interface I transitions
to the Prune-Pending state. The Prune-Pending Timer is to the Prune-Pending state. The Prune-Pending Timer is
started; it is set to the J/P_Override_Interval(I) if the started. It is set to the J/P_Override_Interval(I) if the
router has more than one neighbor on that interface; otherwise router has more than one neighbor on that interface;
it is set to zero causing it to expire immediately. otherwise, it is set to zero, causing it to expire
immediately.
Expiry Timer Expires Expiry Timer Expires
The Expiry Timer for the (S,G) downstream state machine on The Expiry Timer for the (S,G) downstream state machine on
interface I expires. interface I expires.
The (S,G) downstream state machine on interface I transitions The (S,G) downstream state machine on interface I transitions
to the NoInfo state. to the NoInfo state.
Transitions from Prune-Pending State Transitions from Prune-Pending State
When in Prune-Pending state, the following events may trigger a When in Prune-Pending state, the following events may trigger a
transition: transition:
Receive Join(S,G) Receive Join(S,G)
A Join(S,G) is received on interface I with its Upstream A Join(S,G) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (S,G) downstream state machine on interface I transitions The (S,G) downstream state machine on interface I transitions
to the Join state. The Prune-Pending Timer is canceled to the Join state. The Prune-Pending Timer is canceled
(without triggering an expiry event). The Expiry Timer is (without triggering an expiry event). The Expiry Timer is
restarted, set to maximum of its current value and the restarted, set to maximum of its current value and the
HoldTime from the triggering Join/Prune message. HoldTime from the triggering Join/Prune message.
skipping to change at page 55, line 44 skipping to change at page 56, line 40
Neighbor Address field. Its purpose is to add additional Neighbor Address field. Its purpose is to add additional
reliability so that if a Prune that should have been reliability so that if a Prune that should have been
overridden by another router is lost locally on the LAN, then overridden by another router is lost locally on the LAN, then
the PruneEcho may be received and cause the override to the PruneEcho may be received and cause the override to
happen. A PruneEcho(S,G) need not be sent on an interface happen. A PruneEcho(S,G) need not be sent on an interface
that contains only a single PIM neighbor during the time this that contains only a single PIM neighbor during the time this
state machine was in Prune-Pending state. state machine was in Prune-Pending state.
4.5.4. Receiving (S,G,rpt) Join/Prune Messages 4.5.4. Receiving (S,G,rpt) Join/Prune Messages
The per-interface state machine for receiving (S,G,rpt) Join/Prune The per-interface state machine for receiving (S,G,rpt) Join/Prune
messages is given below. There are five states: messages is given below. There are five states:
NoInfo (NI) NoInfo (NI)
The interface has no (S,G,rpt) Prune state and no (S,G,rpt) The interface has no (S,G,rpt) Prune state and no (S,G,rpt)
timers running. timers running.
Prune (P) Prune (P)
The interface has (S,G,rpt) Prune state which will cause the The interface has (S,G,rpt) Prune state, which will cause the
router not to forward packets from S destined for G from this router not to forward packets from S destined for G from this
interface even though the interface has active (*,G) Join interface even though the interface has active (*,G) Join
state. state.
Prune-Pending (PP) Prune-Pending (PP)
The router has received a Prune(S,G,rpt) on this interface The router has received a Prune(S,G,rpt) on this interface
from a downstream neighbor and is waiting to see whether the from a downstream neighbor and is waiting to see whether the
prune will be overridden by another downstream router. For prune will be overridden by another downstream router. For
forwarding purposes, the Prune-Pending state functions exactly forwarding purposes, the Prune-Pending state functions exactly
like the NoInfo state. like the NoInfo state.
PruneTmp (P') PruneTmp (P')
This state is a transient state which for forwarding purposes This state is a transient state that for forwarding purposes
behaves exactly like the Prune state. A (*,G) Join has been behaves exactly like the Prune state. A (*,G) Join has been
received (which may cancel the (S,G,rpt) Prune). As we parse received (which may cancel the (S,G,rpt) Prune). As we parse
the Join/Prune message from top to bottom, we first enter this the Join/Prune message from top to bottom, we first enter this
state if the message contains a (*,G) Join. Later in the state if the message contains a (*,G) Join. Later in the
message we will normally encounter an (S,G,rpt) prune to message, we will normally encounter an (S,G,rpt) prune to
reinstate the Prune state. However if we reach the end of the reinstate the Prune state. However, if we reach the end of
message without encountering such a (S,G,rpt) prune, then we the message without encountering such a (S,G,rpt) prune, then
will revert to NoInfo state in this state machine. we will revert to NoInfo state in this state machine.
As no time is spent in this state, no timers can expire. As no time is spent in this state, no timers can expire.
Prune-Pending-Tmp (PP') Prune-Pending-Tmp (PP')
This state is a transient state which is identical to P' This state is a transient state that is identical to P' except
except that it is associated with the PP state rather than the that it is associated with the PP state rather than the P
P state. For forwarding purposes, PP' behaves exactly like PP state. For forwarding purposes, PP' behaves exactly like PP
state. state.
In addition, there are two timers: In addition, there are two timers:
Expiry Timer (ET) Expiry Timer (ET)
This timer is set when a valid Prune(S,G,rpt) is received. This timer is set when a valid Prune(S,G,rpt) is received.
Expiry of the Expiry Timer causes this state machine to revert Expiry of the Expiry Timer causes this state machine to revert
to NoInfo state. to NoInfo state.
Prune-Pending Timer (PPT) Prune-Pending Timer (PPT)
This timer is set when a valid Prune(S,G,rpt) is received. This timer is set when a valid Prune(S,G,rpt) is received.
Expiry of the Prune-Pending Timer causes this state machine to Expiry of the Prune-Pending Timer causes this state machine to
move on to Prune state. move on to Prune state.
Figure 5: Downstream per-interface (S,G,rpt) state machine in tabular form Figure 5: Downstream per-interface (S,G,rpt) state machine
in tabular form
+----------++----------------------------------------------------------------+ +----------++----------------------------------------------------------+
| || Event | | || Event |
| ++----------+-----------+-----------+---------+---------+---------+ | ++---------+----------+----------+--------+--------+--------+
|Prev ||Receive | Receive | Receive | End of | Prune- | Expiry | |Prev ||Receive | Receive | Receive | End of | Prune- | Expiry |
|State ||Join(*,G) | Join | Prune | Message | Pending | Timer | |State ||Join(*,G)| Join | Prune | Message| Pending| Timer |
| || | (S,G,rpt) | (S,G,rpt) | | Timer | Expires | | || | (S,G,rpt)| (S,G,rpt)| | Timer | Expires|
| || | | | | Expires | | | || | | | | Expires| |
+----------++----------+-----------+-----------+---------+---------+---------+ +----------++---------+----------+----------+--------+--------+--------+
| ||- | - | -> PP | - | - | - | | ||- | - | -> PP | - | - | - |
| || | | state | | | | | || | | state | | | |
| || | | start | | | | | || | | start | | | |
|NoInfo || | | Prune- | | | | |NoInfo || | | Prune- | | | |
|(NI) || | | Pending | | | | |(NI) || | | Pending | | | |
| || | | Timer; | | | | | || | | Timer; | | | |
| || | | start | | | | | || | | start | | | |
| || | | Expiry | | | | | || | | Expiry | | | |
| || | | Timer | | | | | || | | Timer | | | |
+----------++----------+-----------+-----------+---------+---------+---------+ +----------++---------+----------+----------+--------+--------+--------+
| ||-> P' | -> NI | -> P | - | - | -> NI | | ||-> P' | -> NI | -> P | - | - | -> NI |
| ||state | state | state | | | state | | ||state | state | state | | | state |
|Prune (P) || | | restart | | | | |Prune (P) || | | restart | | | |
| || | | Expiry | | | | | || | | Expiry | | | |
| || | | Timer | | | | | || | | Timer | | | |
+----------++----------+-----------+-----------+---------+---------+---------+ +----------++---------+----------+----------+--------+--------+--------+
|Prune- ||-> PP' | -> NI | - | - | -> P | - | |Prune- ||-> PP' | -> NI | - | - | -> P | - |
|Pending ||state | state | | | state | | |Pending ||state | state | | | state | |
|(PP) || | | | | | | |(PP) || | | | | | |
+----------++----------+-----------+-----------+---------+---------+---------+ +----------++---------+----------+----------+--------+--------+--------+
| ||- | - | -> P | -> NI | - | - | | ||- | - | -> P | -> NI | - | - |
|PruneTmp || | | state | state | | | |PruneTmp || | | state | state | | |
|(P') || | | restart | | | | |(P') || | | restart | | | |
| || | | Expiry | | | | | || | | Expiry | | | |
| || | | Timer | | | | | || | | Timer | | | |
+----------++----------+-----------+-----------+---------+---------+---------+ +----------++---------+----------+----------+--------+--------+--------+
| ||- | - | -> PP | -> NI | - | - | | ||- | - | -> PP | -> NI | - | - |
|Prune- || | | state | state | | | |Prune- || | | state | state | | |
|Pending- || | | restart | | | | |Pending- || | | restart | | | |
|Tmp (PP') || | | Expiry | | | | |Tmp (PP') || | | Expiry | | | |
| || | | Timer | | | | | || | | Timer | | | |
+----------++----------+-----------+-----------+---------+---------+---------+ +----------++---------+----------+----------+--------+--------+--------+
The transition events "Receive Join(S,G,rpt)", "Receive Prune(S,G,rpt)", The transition events "Receive Join(S,G,rpt)", "Receive
and "Receive Join(*,G)" imply receiving a Join or Prune targeted to this Prune(S,G,rpt)", and "Receive Join(*,G)" imply receiving a Join or
router's primary IP address on the received interface. If the upstream Prune targeted to this router's primary IP address on the received
neighbor address field is not correct, these state transitions in this interface. If the upstream neighbor address field is not correct,
state machine must not occur, although seeing such a packet may cause these state transitions in this state machine must not occur,
state transitions in other state machines. 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 On unnumbered interfaces on point-to-point links, the router's
should be the same as the source address it chose for the Hello message address should be the same as the source address it chose for the
it sent over that interface. However on point-to-point links we also Hello message it sent over that interface. However, on point-to-
recommend that PIM Join/Prune messages with a upstream neighbor address point links we also recommend that PIM Join/Prune messages with an
field of all zeros are also accepted. upstream neighbor address field of all zeros are also accepted.
Transitions from NoInfo State Transitions from NoInfo State
When in NoInfo (NI) state, the following event may trigger a transition: When in NoInfo (NI) state, the following event may trigger a
transition:
Receive Prune(S,G,rpt) Receive Prune(S,G,rpt)
A Prune(S,G,rpt) is received on interface I with its Upstream A Prune(S,G,rpt) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (S,G,rpt) downstream state machine on interface I The (S,G,rpt) downstream state machine on interface I
transitions to the Prune-Pending state. The Expiry Timer (ET) transitions to the Prune-Pending state. The Expiry Timer (ET)
is started, and set to the HoldTime from the triggering is started and set to the HoldTime from the triggering
Join/Prune message. The Prune-Pending Timer is started; it is Join/Prune message. The Prune-Pending Timer is started. It
set to the J/P_Override_Interval(I) if the router has more is set to the J/P_Override_Interval(I) if the router has more
than one neighbor on that interface; otherwise it is set to than one neighbor on that interface; otherwise, it is set to
zero causing it to expire immediately. zero, causing it to expire immediately.
Transitions from Prune-Pending State Transitions from Prune-Pending State
When in Prune-Pending (PP) state, the following events may trigger a When in Prune-Pending (PP) state, the following events may trigger a
transition: transition:
Receive Join(*,G) Receive Join(*,G)
A Join(*,G) is received on interface I with its Upstream A Join(*,G) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (S,G,rpt) downstream state machine on interface I The (S,G,rpt) downstream state machine on interface I
transitions to Prune-Pending-Tmp state whilst the remainder of transitions to Prune-Pending-Tmp state whilst the remainder of
the compound Join/Prune message containing the Join(*,G) is the compound Join/Prune message containing the Join(*,G) is
processed. processed.
skipping to change at page 59, line 8 skipping to change at page 60, line 12
The (S,G,rpt) downstream state machine on interface I The (S,G,rpt) downstream state machine on interface I
transitions to NoInfo state. ET and PPT are canceled. transitions to NoInfo state. ET and PPT are canceled.
Prune-Pending Timer Expires Prune-Pending Timer Expires
The Prune-Pending Timer for the (S,G,rpt) downstream state The Prune-Pending Timer for the (S,G,rpt) downstream state
machine on interface I expires. machine on interface I expires.
The (S,G,rpt) downstream state machine on interface I The (S,G,rpt) downstream state machine on interface I
transitions to the Prune state. transitions to the Prune state.
Transitions from Prune State Transitions from Prune State
When in Prune (P) state, the following events may trigger a transition: When in Prune (P) state, the following events may trigger a
transition:
Receive Join(*,G) Receive Join(*,G)
A Join(*,G) is received on interface I with its Upstream A Join(*,G) is received on interface I with its Upstream
Neighbor Address set to the router's primary IP address on I. Neighbor Address set to the router's primary IP address on I.
The (S,G,rpt) downstream state machine on interface I The (S,G,rpt) downstream state machine on interface I
transitions to PruneTmp state whilst the remainder of the transitions to PruneTmp state whilst the remainder of the
compound Join/Prune message containing the Join(*,G) is compound Join/Prune message containing the Join(*,G) is
processed. processed.
skipping to change at page 59, line 44 skipping to change at page 60, line 49
maximum of its current value and the HoldTime from the maximum of its current value and the HoldTime from the
triggering Join/Prune message. triggering Join/Prune message.
Expiry Timer Expires Expiry Timer Expires
The Expiry Timer for the (S,G,rpt) downstream state machine on The Expiry Timer for the (S,G,rpt) downstream state machine on
interface I expires. interface I expires.
The (S,G,rpt) downstream state machine on interface I The (S,G,rpt) downstream state machine on interface I
transitions to the NoInfo state. transitions to the NoInfo state.
Transitions from Prune-Pending-Tmp State Transitions from Prune-Pending-Tmp State
When in Prune-Pending-Tmp (PP') state and processing a compound When in Prune-Pending-Tmp (PP') state and processing a compound
Join/Prune message, the following events may trigger a transition: Join/Prune message, the following events may trigger a transition:
Receive Prune(S,G,rpt) Receive Prune(S,G,rpt)
The compound Join/Prune message contains a Prune(S,G,rpt). The compound Join/Prune message contains a Prune(S,G,rpt).
The (S,G,rpt) downstream state machine on interface I The (S,G,rpt) downstream state machine on interface I
transitions back to the Prune-Pending state. The Expiry Timer transitions back to the Prune-Pending state. The Expiry Timer
(ET) is restarted, set to maximum of its current value and the (ET) is restarted, set to maximum of its current value and the
HoldTime from the triggering Join/Prune message. HoldTime from the triggering Join/Prune message.
End of Message End of Message
The end of the compound Join/Prune message is reached. The end of the compound Join/Prune message is reached.
The (S,G,rpt) downstream state machine on interface I The (S,G,rpt) downstream state machine on interface I
transitions to the NoInfo state. ET and PPT are canceled. transitions to the NoInfo state. ET and PPT are canceled.
Transitions from PruneTmp State Transitions from PruneTmp State
When in PruneTmp (P') state and processing a compound Join/Prune When in PruneTmp (P') state and processing a compound Join/Prune
message, the following events may trigger a transition: message, the following events may trigger a transition:
Receive Prune(S,G,rpt) Receive Prune(S,G,rpt)
The compound Join/Prune message contains a Prune(S,G,rpt). The compound Join/Prune message contains a Prune(S,G,rpt).
The (S,G,rpt) downstream state machine on interface I The (S,G,rpt) downstream state machine on interface I
transitions back to the Prune state. The Expiry Timer (ET) is transitions back to the Prune state. The Expiry Timer (ET) is
restarted, set to maximum of its current value and the restarted, set to maximum of its current value and the
HoldTime from the triggering Join/Prune message. HoldTime from the triggering Join/Prune message.
End of Message End of Message
The end of the compound Join/Prune message is reached. The end of the compound Join/Prune message is reached.
The (S,G,rpt) downstream state machine on interface I The (S,G,rpt) downstream state machine on interface I
transitions to the NoInfo state. ET is canceled. transitions to the NoInfo state. ET is canceled.
Notes: Notes:
Receiving a Prune(*,G) does not affect the (S,G,rpt) downstream state Receiving a Prune(*,G) does not affect the (S,G,rpt) downstream state
machine. machine.
Receiving a Join(*,*,RP) does not affect the (S,G,rpt) downstream state Receiving a Join(*,*,RP) does not affect the (S,G,rpt) downstream
machine. If a router has originated Join(*,*,RP) and pruned a source state machine. If a router has originated Join(*,*,RP) and pruned a
off it using Prune(S,G,rpt), then to receive that source again it should source off it using Prune(S,G,rpt), then to receive that source again
explicitly re-join using Join(S,G,rpt) or Join(*,G). In some LAN it should explicitly re-join using Join(S,G,rpt) or Join(*,G). In
topologies it is possible for a router sending a new Join(*,*,RP) to some LAN topologies it is possible for a router sending a new
have to wait as much as a Join/Prune Interval before noticing that it Join(*,*,RP) to have to wait as much as a Join/Prune Interval before
needs to override a neighbor's pre-existing Prune(S,G,rpt). This is noticing that it needs to override a neighbor's preexisting
considered acceptable, as (*,*,RP) state is intended to be used only in Prune(S,G,rpt). This is considered acceptable, as (*,*,RP) state is
long-lived and persistent scenarios. intended to be used only in long-lived and persistent scenarios.
4.5.5. Sending (*,*,RP) Join/Prune Messages 4.5.5. Sending (*,*,RP) Join/Prune Messages
The per-interface state machines for (*,*,RP) hold join state from The per-interface state machines for (*,*,RP) hold join state from
downstream PIM routers. This state then determines whether a router downstream PIM routers. This state then determines whether a router
needs to propagate a Join(*,*,RP) upstream towards the RP. needs to propagate a Join(*,*,RP) upstream towards the RP.
If a router wishes to propagate a Join(*,*,RP) upstream, it must also If a router wishes to propagate a Join(*,*,RP) upstream, it must also
watch for messages on its upstream interface from other routers on that watch for messages on its upstream interface from other routers on
subnet, and these may modify its behavior. If it sees a Join(*,*,RP) to that subnet, and these may modify its behavior. If it sees a
the correct upstream neighbor, it should suppress its own Join(*,*,RP). Join(*,*,RP) to the correct upstream neighbor, it should suppress its
If it sees a Prune(*,*,RP) to the correct upstream neighbor, it should own Join(*,*,RP). If it sees a Prune(*,*,RP) to the correct upstream
be prepared to override that prune by sending a Join(*,*,RP) almost neighbor, it should be prepared to override that prune by sending a
immediately. Finally, if it sees the Generation ID (see Section 4.3) of Join(*,*,RP) almost immediately. Finally, if it sees the Generation
the correct upstream neighbor change, it knows that the upstream ID (see Section 4.3) of the correct upstream neighbor change, it
neighbor has lost state, and it should be prepared to refresh the state knows that the upstream neighbor has lost state, and it should be
by sending a Join(*,*,RP) almost immediately. prepared to refresh the state by sending a Join(*,*,RP) almost
immediately.
In addition, if the MRIB changes to indicate that the next hop towards In addition, if the MRIB changes to indicate that the next hop
the RP has changed, the router should prune off from the old next hop, towards the RP has changed, the router should prune off from the old
and join towards the new next hop. next hop and join towards the new next hop.
The upstream (*,*,RP) state machine contains only two states: The upstream (*,*,RP) state machine contains only two states:
Not Joined Not Joined
The downstream state machines and local membership information do The downstream state machines and local membership information do
not indicate that the router needs to join the (*,*,RP) tree for not indicate that the router needs to join the (*,*,RP) tree for
this RP. this RP.
Joined Joined
The downstream state machines and local membership information The downstream state machines and local membership information
indicate that the router should join the (*,*,RP) tree for this RP. indicate that the router should join the (*,*,RP) tree for this
RP.
In addition, one timer JT(*,*,RP) is kept which is used to trigger the In addition, one timer JT(*,*,RP) is kept that is used to trigger the
sending of a Join(*,*,RP) to the upstream next hop towards the RP, sending of a Join(*,*,RP) to the upstream next hop towards the RP,
NBR(RPF_interface(RP), MRIB.next_hop(RP)). NBR(RPF_interface(RP), MRIB.next_hop(RP)).
Figure 6: Upstream (*,*,RP) state machine in tabular form Figure 6: Upstream (*,*,RP) state machine in tabular form
+--------------------++-------------------------------------------------+ +-------------------++-------------------------------------------------+
| || Event | | || Event |
| Prev State ++-------------------------+-----------------------+ | Prev State ++-------------------------+-----------------------+
| || JoinDesired | JoinDesired | | || JoinDesired | JoinDesired |
| || (*,*,RP) ->True | (*,*,RP) ->False | | || (*,*,RP) ->True | (*,*,RP) ->False |
+--------------------++-------------------------+-----------------------+ +-------------------++-------------------------+-----------------------+
| || -> J state | - | | || -> J state | - |
| NotJoined (NJ) || Send Join(*,*,RP); | | | NotJoined (NJ) || Send Join(*,*,RP); | |
| || Set Join Timer to | | | || Set Join Timer to | |
| || t_periodic | | | || t_periodic | |
+--------------------++-------------------------+-----------------------+ +-------------------++-------------------------+-----------------------+
| Joined (J) || - | -> NJ state | | Joined (J) || - | -> NJ state |
| || | Send Prune | | || | Send Prune |
| || | (*,*,RP); Cancel | | || | (*,*,RP); Cancel |
| || | Join Timer | | || | Join Timer |
+--------------------++-------------------------+-----------------------+ +-------------------++-------------------------+-----------------------+
In addition, we have the following transitions which occur within the In addition, we have the following transitions, which occur within
Joined state: the Joined state:
+-----------------------------------------------------------------------+ +----------------------------------------------------------------------+
| In Joined (J) State | | In Joined (J) State |
+-------------------+--------------------+------------------------------+ +-------------------+--------------------+-----------------------------+
| Timer Expires | See | See | | Timer Expires | See | See |
| | Join(*,*,RP) | Prune(*,*,RP) | | | Join(*,*,RP) | Prune(*,*,RP) |
| | to MRIB. | to MRIB. | | | to MRIB. | to MRIB. |
| | next_hop(RP) | next_hop(RP) | | | next_hop(RP) | next_hop(RP) |
+-------------------+--------------------+------------------------------+ +-------------------+--------------------+-----------------------------+
| Send | Increase Join | Decrease Join | | Send | Increase Join | Decrease Join |
| Join(*,*,RP); | Timer to | Timer to | | Join(*,*,RP); | Timer to | Timer to |
| Set Join Timer | t_joinsuppress | t_override | | Set Join Timer | t_joinsuppress | t_override |
| to t_periodic | | | | to t_periodic | | |
+-------------------+--------------------+------------------------------+ +-------------------+--------------------+-----------------------------+
+-----------------------------------------------------------------------+ +----------------------------------------------------------------------+
| In Joined (J) State | | In Joined (J) State |
+-----------------------------------+-----------------------------------+ +-----------------------------------+----------------------------------+
| NBR(RPF_interface(RP), | MRIB.next_hop(RP) GenID | | NBR(RPF_interface(RP), | MRIB.next_hop(RP) GenID |
| MRIB.next_hop(RP)) | changes | | MRIB.next_hop(RP)) | changes |
| changes | | | changes | |
+-----------------------------------+-----------------------------------+ +-----------------------------------+----------------------------------+
| Send Join(*,*,RP) to new | Decrease Join Timer to | | Send Join(*,*,RP) to new | Decrease Join Timer to |
| next hop; Send | t_override | | next hop; Send | t_override |
| Prune(*,*,RP) to old | | | Prune(*,*,RP) to old | |
| next hop; set Join Timer | | | next hop; set Join Timer | |
| to t_periodic | | | to t_periodic | |
+-----------------------------------+-----------------------------------+ +-----------------------------------+----------------------------------+
This state machine uses the following macro: This state machine uses the following macro:
bool JoinDesired(*,*,RP) { bool JoinDesired(*,*,RP) {
if immediate_olist(*,*,RP) != NULL if immediate_olist(*,*,RP) != NULL
return TRUE return TRUE
else else
return FALSE return FALSE
} }
JoinDesired(*,*,RP) is true when the router has received (*,*,RP) Joins JoinDesired(*,*,RP) is true when the router has received (*,*,RP)
from any downstream interface. Note that although JoinDesired is true, Joins from any downstream interface. Note that although JoinDesired
the router's sending of a Join(*,*,RP) message may be suppressed by is true, the router's sending of a Join(*,*,RP) message may be
another router sending a Join(*,*,RP) onto the upstream interface. suppressed by another router sending a Join(*,*,RP) onto the upstream
interface.
Transitions from NotJoined State Transitions from NotJoined State
When the upstream (*,*,RP) state machine is in NotJoined state, the When the upstream (*,*,RP) state machine is in NotJoined state, the
following event may trigger a state transition: following event may trigger a state transition:
JoinDesired(*,*,RP) becomes True JoinDesired(*,*,RP) becomes True
The downstream state for (*,*,RP) has changed so that at least The downstream state for (*,*,RP) has changed so that at least
one interface is in immediate_olist(*,*,RP), making one interface is in immediate_olist(*,*,RP), making
JoinDesired(*,*,RP) become True. JoinDesired(*,*,RP) become True.
The upstream (*,*,RP) state machine transitions to Joined The upstream (*,*,RP) state machine transitions to Joined
state. Send Join(*,*,RP) to the appropriate upstream state. Send Join(*,*,RP) to the appropriate upstream
neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)). neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)).
Set the Join Timer (JT) to expire after t_periodic seconds. Set the Join Timer (JT) to expire after t_periodic seconds.
Transitions from Joined State Transitions from Joined State
When the upstream (*,*,RP) state machine is in Joined state, the When the upstream (*,*,RP) state machine is in Joined state, the
following events may trigger state transitions: following events may trigger state transitions:
JoinDesired(*,*,RP) becomes False JoinDesired(*,*,RP) becomes False
The downstream state for (*,*,RP) has changed so no interface The downstream state for (*,*,RP) has changed so no interface
is in immediate_olist(*,*,RP), making JoinDesired(*,*,RP) is in immediate_olist(*,*,RP), making JoinDesired(*,*,RP)
become False. become False.
The upstream (*,*,RP) state machine transitions to NotJoined The upstream (*,*,RP) state machine transitions to NotJoined
state. Send Prune(*,*,RP) to the appropriate upstream state. Send Prune(*,*,RP) to the appropriate upstream
neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)). neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)).
Cancel the Join Timer (JT). Cancel the Join Timer (JT).
skipping to change at page 65, line 10 skipping to change at page 66, line 10
If the Join Timer is set to expire in more than t_override If the Join Timer is set to expire in more than t_override
seconds, reset it so that it expires after t_override seconds. seconds, reset it so that it expires after t_override seconds.
If the Join Timer is set to expire in less than t_override If the Join Timer is set to expire in less than t_override
seconds, leave it unchanged. seconds, leave it unchanged.
NBR(RPF_interface(RP), MRIB.next_hop(RP)) changes NBR(RPF_interface(RP), MRIB.next_hop(RP)) changes
A change in the MRIB routing base causes the next hop towards A change in the MRIB routing base causes the next hop towards
the RP to change. the RP to change.
The upstream (*,*,RP) state machine remains in Joined state. The upstream (*,*,RP) state machine remains in Joined state.
Send Join(*,*,RP) to the new upstream neighbor which is the Send Join(*,*,RP) to the new upstream neighbor, which is the
new value of NBR(RPF_interface(RP), MRIB.next_hop(RP)). Send new value of NBR(RPF_interface(RP), MRIB.next_hop(RP)). Send
Prune(*,*,RP) to the old upstream neighbor, which is the old Prune(*,*,RP) to the old upstream neighbor, which is the old
value of NBR(RPF_interface(RP), MRIB.next_hop(RP)). Set the value of NBR(RPF_interface(RP), MRIB.next_hop(RP)). Set the
Join Timer (JT) to expire after t_periodic seconds. Join Timer (JT) to expire after t_periodic seconds.
MRIB.next_hop(RP) GenID changes MRIB.next_hop(RP) GenID changes
The Generation ID of the router that is MRIB.next_hop(RP) The Generation ID of the router that is MRIB.next_hop(RP)
changes. This normally means that this neighbor has lost changes. This normally means that this neighbor has lost
state, and so the state must be refreshed. state, and so the state must be refreshed.
The upstream (*,*,RP) state machine remains in Joined state. The upstream (*,*,RP) state machine remains in Joined state.
If the Join Timer is set to expire in more than t_override If the Join Timer is set to expire in more than t_override
seconds, reset it so that it expires after t_override seconds. seconds, reset it so that it expires after t_override seconds.
4.5.6. Sending (*,G) Join/Prune Messages 4.5.6. Sending (*,G) Join/Prune Messages
The per-interface state machines for (*,G) hold join state from The per-interface state machines for (*,G) hold join state from
downstream PIM routers. This state then determines whether a router downstream PIM routers. This state then determines whether a router
needs to propagate a Join(*,G) upstream towards the RP. needs to propagate a Join(*,G) upstream towards the RP.
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
for messages on its upstream interface from other routers on that watch for messages on its upstream interface from other routers on
subnet, and these may modify its behavior. If it sees a Join(*,G) to that subnet, and these may modify its behavior. If it sees a
the correct upstream neighbor, it should suppress its own Join(*,G). If Join(*,G) to the correct upstream neighbor, it should suppress its
it sees a Prune(*,G) to the correct upstream neighbor, it should be own Join(*,G). If it sees a Prune(*,G) to the correct upstream
prepared to override that prune by sending a Join(*,G) almost neighbor, it should be prepared to override that prune by sending a
immediately. Finally, if it sees the Generation ID (see Section 4.3) of Join(*,G) almost immediately. Finally, if it sees the Generation ID
the correct upstream neighbor change, it knows that the upstream (see Section 4.3) of the correct upstream neighbor change, it knows
neighbor has lost state, and it should be prepared to refresh the state that the upstream neighbor has lost state, and it should be prepared
by sending a Join(*,G) almost immediately. to refresh the state by sending a Join(*,G) almost immediately.
If a (*,G) Assert occurs on the upstream interface, and this changes If a (*,G) Assert occurs on the upstream interface, and this changes
this router's idea of the upstream neighbor, it should be prepared to this router's idea of the upstream neighbor, it should be prepared to
ensure that the Assert winner is aware of downstream routers by sending ensure that the Assert winner is aware of downstream routers by
a Join(*,G) almost immediately. sending a Join(*,G) almost immediately.
In addition, if the MRIB changes to indicate that the next hop towards In addition, if the MRIB changes to indicate that the next hop
the RP has changed, and either the upstream interface changes or there towards the RP has changed, and either the upstream interface changes
is no Assert winner on the upstream interface, the router should prune or there is no Assert winner on the upstream interface, the router
off from the old next hop, and join towards the new next hop. should prune off from the old next hop and join towards the new next
hop.
The upstream (*,G) state machine only contains two states: The upstream (*,G) state machine only contains two states:
Not Joined Not Joined
The downstream state machines indicate that the router does not The downstream state machines indicate that the router does not
need to join the RP tree for this group. need to join the RP tree for this group.
Joined Joined
The downstream state machines indicate that the router should join The downstream state machines indicate that the router should join
the RP tree for this group. the RP tree for this group.
In addition, one timer JT(*,G) is kept which is used to trigger the In addition, one timer JT(*,G) is kept that is used to trigger the
sending of a Join(*,G) to the upstream next hop towards the RP, sending of a Join(*,G) to the upstream next hop towards the RP,
RPF'(*,G). RPF'(*,G).
Figure 7: Upstream (*,G) state machine in tabular form Figure 7: Upstream (*,G) state machine in tabular form
+--------------------++-------------------------------------------------+ +-------------------++-------------------------------------------------+
| || Event | | || Event |
| Prev State ++------------------------+------------------------+ | Prev State ++------------------------+------------------------+
| || JoinDesired(*,G) | JoinDesired(*,G) | | || JoinDesired(*,G) | JoinDesired(*,G) |
| || ->True | ->False | | || ->True | ->False |
+--------------------++------------------------+------------------------+ +-------------------++------------------------+------------------------+
| || -> J state | - | | || -> J state | - |
| NotJoined (NJ) || Send Join(*,G); | | | NotJoined (NJ) || Send Join(*,G); | |
| || Set Join Timer to | | | || Set Join Timer to | |
| || t_periodic | | | || t_periodic | |
+--------------------++------------------------+------------------------+ +-------------------++------------------------+------------------------+
| Joined (J) || - | -> NJ state | | Joined (J) || - | -> NJ state |
| || | Send Prune(*,G); | | || | Send Prune(*,G); |
| || | Cancel Join Timer | | || | Cancel Join Timer |
+--------------------++------------------------+------------------------+ +-------------------++------------------------+------------------------+
In addition, we have the following transitions which occur within the In addition, we have the following transitions, which occur within
Joined state: the 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'(*,G) |
| | to RPF'(*,G) | to RPF'(*,G) | changes due to | | | to RPF'(*,G) | to RPF'(*,G) | changes due to |
| | | | an Assert | | | | | an Assert |
+-----------------+-----------------+-----------------+-----------------+ +----------------+-----------------+-----------------+-----------------+
|Send | Increase Join | Decrease Join | Decrease Join | |Send | Increase Join | Decrease Join | Decrease Join |
|Join(*,G); Set | Timer to | Timer to | Timer to | |Join(*,G); Set | Timer to | Timer to | Timer to |
|Join Timer to | t_joinsuppress | t_override | t_override | |Join Timer to | t_joinsuppress | t_override | t_override |
|t_periodic | | | | |t_periodic | | | |
+-----------------+-----------------+-----------------+-----------------+ +----------------+-----------------+-----------------+-----------------+
+----------------------------------------------------------------------+
| In Joined (J) State |
+----------------------------------+-----------------------------------+
| RPF'(*,G) changes not | RPF'(*,G) GenID changes |
| due to an Assert | |
+----------------------------------+-----------------------------------+
| Send Join(*,G) to new | Decrease Join Timer to |
| next hop; Send | t_override |
| Prune(*,G) to old next | |
| hop; Set Join Timer to | |
| t_periodic | |
+----------------------------------+-----------------------------------+
+-----------------------------------------------------------------------+ This state machine uses the following macro:
| In Joined (J) State |
+----------------------------------+------------------------------------+
| RPF'(*,G) changes not | RPF'(*,G) GenID changes |
| due to an Assert | |
+----------------------------------+------------------------------------+
| Send Join(*,G) to new | Decrease Join Timer to |
| next hop; Send | t_override |
| Prune(*,G) to old next | |
| hop; Set Join Timer to | |
| t_periodic | |
+----------------------------------+------------------------------------+
This state machine uses the following macro:
bool JoinDesired(*,G) { bool JoinDesired(*,G) {
if (immediate_olist(*,G) != NULL OR if (immediate_olist(*,G) != NULL OR
(JoinDesired(*,*,RP(G)) AND (JoinDesired(*,*,RP(G)) AND
AssertWinner(*, G, RPF_interface(RP(G))) != NULL)) AssertWinner(*, G, RPF_interface(RP(G))) != NULL))
return TRUE return TRUE
else else
return FALSE return FALSE
} }
JoinDesired(*,G) is true when the router has forwarding state that would JoinDesired(*,G) is true when the router has forwarding state that
cause it to forward traffic for G using shared tree state. Note that would cause it to forward traffic for G using shared tree state.
although JoinDesired is true, the router's sending of a Join(*,G) Note that although JoinDesired is true, the router's sending of a
message may be suppressed by another router sending a Join(*,G) onto the Join(*,G) message may be suppressed by another router sending a
upstream interface. Join(*,G) onto the upstream interface.
Transitions from NotJoined State Transitions from NotJoined State
When the upstream (*,G) state machine is in NotJoined state, the When the upstream (*,G) state machine is in NotJoined state, the
following event may trigger a state transition: following event may trigger a state transition:
JoinDesired(*,G) becomes True JoinDesired(*,G) becomes True
The macro JoinDesired(*,G) becomes True, e.g., because the The macro JoinDesired(*,G) becomes True, e.g., because the
downstream state for (*,G) has changed so that at least one downstream state for (*,G) has changed so that at least one
interface is in immediate_olist(*,G). interface is in immediate_olist(*,G).
The upstream (*,G) state machine transitions to Joined state. The upstream (*,G) state machine transitions to Joined state.
Send Join(*,G) to the appropriate upstream neighbor, which is Send Join(*,G) to the appropriate upstream neighbor, which is
RPF'(*,G). Set the Join Timer (JT) to expire after t_periodic RPF'(*,G). Set the Join Timer (JT) to expire after t_periodic
seconds. seconds.
Transitions from Joined State Transitions from Joined State
When the upstream (*,G) state machine is in Joined state, the following When the upstream (*,G) state machine is in Joined state, the
events may trigger state transitions: following events may trigger state transitions:
JoinDesired(*,G) becomes False JoinDesired(*,G) becomes False
The macro JoinDesired(*,G) becomes False, e.g., because the The macro JoinDesired(*,G) becomes False, e.g., because the
downstream state for (*,G) has changed so no interface is in downstream state for (*,G) has changed so no interface is in
immediate_olist(*,G). immediate_olist(*,G).
The upstream (*,G) state machine transitions to NotJoined The upstream (*,G) state machine transitions to NotJoined
state. Send Prune(*,G) to the appropriate upstream neighbor, state. Send Prune(*,G) to the appropriate upstream neighbor,
which is RPF'(*,G). Cancel the Join Timer (JT). which is RPF'(*,G). Cancel the Join Timer (JT).
skipping to change at page 69, line 49 skipping to change at page 70, line 22
The current next hop towards the RP changes due to an The current next hop towards the RP changes due to an
Assert(*,G) on the RPF_interface(RP(G)). Assert(*,G) on the RPF_interface(RP(G)).
The upstream (*,G) state machine remains in Joined state. If The upstream (*,G) state machine remains in Joined state. If
the Join Timer is set to expire in more than t_override the Join Timer is set to expire in more than t_override
seconds, reset it so that it expires after t_override seconds. seconds, reset it so that it expires after t_override seconds.
If the Join Timer is set to expire in less than t_override If the Join Timer is set to expire in less than t_override
seconds, leave it unchanged. seconds, leave it unchanged.
RPF'(*,G) changes not due to an Assert RPF'(*,G) changes not due to an Assert
An event occurred which caused the next hop towards the RP for An event occurred that caused the next hop towards the RP for
G to change. This may be caused by a change in the MRIB G to change. This may be caused by a change in the MRIB
routing database or the group-to-RP mapping. Note that this routing database or the group-to-RP mapping. Note that this
transition does not occur if an Assert is active and the transition does not occur if an Assert is active and the
upstream interface does not change. upstream interface does not change.
The upstream (*,G) state machine remains in Joined state. The upstream (*,G) state machine remains in Joined state.
Send Join(*,G) to the new upstream neighbor which is the new Send Join(*,G) to the new upstream neighbor, which is the new
value of RPF'(*,G). Send Prune(*,G) to the old upstream value of RPF'(*,G). Send Prune(*,G) to the old upstream
neighbor, which is the old value of RPF'(*,G). Use the new neighbor, which is the old value of RPF'(*,G). Use the new
value of RP(G) in the Prune(*,G) message or all-zeros if RP(G) value of RP(G) in the Prune(*,G) message or all zeros if RP(G)
becomes unknown (old value of RP(G) may be used instead to becomes unknown (old value of RP(G) may be used instead to
improve behavior in routers implementing older versions of improve behavior in routers implementing older versions of
this spec). Set the Join Timer (JT) to expire after this spec). Set the Join Timer (JT) to expire after
t_periodic seconds. t_periodic seconds.
RPF'(*,G) GenID changes RPF'(*,G) GenID changes
The Generation ID of the router that is RPF'(*,G) changes. The Generation ID of the router that is RPF'(*,G) changes.
This normally means that this neighbor has lost state, and so This normally means that this neighbor has lost state, and so
the state must be refreshed. the state must be refreshed.
The upstream (*,G) state machine remains in Joined state. If The upstream (*,G) state machine remains in Joined state. If
the Join Timer is set to expire in more than t_override the Join Timer is set to expire in more than t_override
seconds, reset it so that it expires after t_override seconds. seconds, reset it so that it expires after t_override seconds.
4.5.7. Sending (S,G) Join/Prune Messages 4.5.7. Sending (S,G) Join/Prune Messages
The per-interface state machines for (S,G) hold join state from The per-interface state machines for (S,G) hold join state from
downstream PIM routers. This state then determines whether a router downstream PIM routers. This state then determines whether a router
needs to propagate a Join(S,G) upstream towards the source. needs to propagate a Join(S,G) upstream towards the source.
If a router wishes to propagate a Join(S,G) upstream, it must also watch If a router wishes to propagate a Join(S,G) upstream, it must also
for messages on its upstream interface from other routers on that watch for messages on its upstream interface from other routers on
subnet, and these may modify its behavior. If it sees a Join(S,G) to that subnet, and these may modify its behavior. If it sees a
the correct upstream neighbor, it should suppress its own Join(S,G). If Join(S,G) to the correct upstream neighbor, it should suppress its
it sees a Prune(S,G), Prune(S,G,rpt), or Prune(*,G) to the correct own Join(S,G). If it sees a Prune(S,G), Prune(S,G,rpt), or
upstream neighbor towards S, it should be prepared to override that Prune(*,G) to the correct upstream neighbor towards S, it should be
prune by scheduling a Join(S,G) to be sent almost immediately. Finally, prepared to override that prune by scheduling a Join(S,G) to be sent
if it sees the Generation ID of its upstream neighbor change, it knows almost immediately. Finally, if it sees the Generation ID of its
that the upstream neighbor has lost state, and it should refresh the upstream neighbor change, it knows that the upstream neighbor has
state by scheduling a Join(S,G) to be sent almost immediately. lost state, and it should refresh the state by scheduling a Join(S,G)
to be sent almost immediately.
If a (S,G) Assert occurs on the upstream interface, and this changes the If a (S,G) Assert occurs on the upstream interface, and this changes
this router's idea of the upstream neighbor, it should be prepared to the this router's idea of the upstream neighbor, it should be
ensure that the Assert winner is aware of downstream routers by prepared to ensure that the Assert winner is aware of downstream
scheduling a Join(S,G) to be sent almost immediately. routers by scheduling a Join(S,G) to be sent almost immediately.
In addition, if MRIB changes cause the next hop towards the source to In addition, if MRIB changes cause the next hop towards the source to
change, and either the upstream interface changes or there is no Assert change, and either the upstream interface changes or there is no
winner on the upstream interface, the router should send a prune to the Assert winner on the upstream interface, the router should send a
old next hop, and a join to the new next hop. prune to the old next hop and a join to the new next hop.
The upstream (S,G) state machine only contains two states: The upstream (S,G) state machine only contains two states:
Not Joined Not Joined
The downstream state machines and local membership information do The downstream state machines and local membership information do
not indicate that the router needs to join the shortest-path tree not indicate that the router needs to join the shortest-path tree
for this (S,G). for this (S,G).
Joined Joined
The downstream state machines and local membership information The downstream state machines and local membership information
indicate that the router should join the shortest-path tree for indicate that the router should join the shortest-path tree for
this (S,G). this (S,G).
In addition, one timer JT(S,G) is kept which is used to trigger the In addition, one timer JT(S,G) is kept that is used to trigger the
sending of a Join(S,G) to the upstream next hop towards S, RPF'(S,G). sending of a Join(S,G) to the upstream next hop towards S, RPF'(S,G).
Figure 8: Upstream (S,G) state machine in tabular form Figure 8: Upstream (S,G) state machine in tabular form
+--------------------+--------------------------------------------------+ +-------------------+--------------------------------------------------+
| | Event | | | Event |
| Prev State +-------------------------+------------------------+ | Prev State +-------------------------+------------------------+
| | JoinDesired(S,G) | JoinDesired(S,G) | | | JoinDesired(S,G) | JoinDesired(S,G) |
| | ->True | ->False | | | ->True | ->False |
+--------------------+-------------------------+------------------------+ +-------------------+-------------------------+------------------------+
| NotJoined (NJ) | -> J state | - | | NotJoined (NJ) | -> J state | - |
| | Send Join(S,G); | | | | Send Join(S,G); | |
| | Set Join Timer to | | | | Set Join Timer to | |
| | t_periodic | | | | t_periodic | |
+--------------------+-------------------------+------------------------+ +-------------------+-------------------------+------------------------+
| Joined (J) | - | -> NJ state | | Joined (J) | - | -> NJ state |
| | | Send Prune(S,G); | | | | Send Prune(S,G); |
| | | Set SPTbit(S,G) to | | | | Set SPTbit(S,G) to |
| | | FALSE; Cancel Join | | | | FALSE; Cancel Join |
| | | Timer | | | | Timer |
+--------------------+-------------------------+------------------------+ +-------------------+-------------------------+------------------------+
In addition, we have the following transitions which occur within the
Joined state:
+-----------------------------------------------------------------------+ In addition, we have the following transitions, which occur within
| In Joined (J) State | the Joined state:
+-----------------+-----------------+------------------+----------------+
| Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune |
| | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to |
| | | | RPF'(S,G) |
+-----------------+-----------------+------------------+----------------+
| Send | Increase Join | Decrease Join | Decrease Join |
| Join(S,G); Set | Timer to | Timer to | Timer to |
| Join Timer to | t_joinsuppress | t_override | t_override |
| t_periodic | | | |
+-----------------+-----------------+------------------+----------------+
+-----------------------------------------------------------------------+ +----------------------------------------------------------------------+
| In Joined (J) State | | In Joined (J) State |
+-----------------+-----------------+-----------------+-----------------+ +-----------------+-----------------+-----------------+----------------+
| See Prune(*,G) | RPF'(S,G) | RPF'(S,G) | RPF'(S,G) | | Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune |
| to RPF'(S,G) | changes not | GenID changes | changes due to | | | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to |
| | due to an | | an Assert | | | | | RPF'(S,G) |
| | Assert | | | +-----------------+-----------------+-----------------+----------------+
+-----------------+-----------------+-----------------+-----------------+ | Send | Increase Join | Decrease Join | Decrease Join |
| Decrease Join | Send Join(S,G) | Decrease Join | Decrease Join | | Join(S,G); Set | Timer to | Timer to | Timer to |
| Timer to | to new next | Timer to | Timer to | | Join Timer to | t_joinsuppress | t_override | t_override |
| t_override | hop; Send | t_override | t_override | | t_periodic | | | |
| | Prune(S,G) to | | | +-----------------+-----------------+-----------------+----------------+
| | old next hop; | | | +----------------------------------------------------------------------+
| | Set Join Timer | | | | In Joined (J) State |
| | to t_periodic | | | +-----------------+-----------------+----------------+-----------------+
+-----------------+-----------------+-----------------+-----------------+ | See Prune(*,G) | RPF'(S,G) | RPF'(S,G) | RPF'(S,G) |
| to RPF'(S,G) | changes not | GenID changes | changes due to |
| | due to an | | an Assert |
| | Assert | | |
+-----------------+-----------------+----------------+-----------------+
| Decrease Join | Send Join(S,G) | Decrease Join | Decrease Join |
| Timer to | to new next | Timer to | Timer to |
| t_override | hop; Send | t_override | t_override |
| | Prune(S,G) to | | |
| | old next hop; | | |
| | Set Join Timer | | |
| | to t_periodic | | |
+-----------------+-----------------+----------------+-----------------+
This state machine uses the following macro: This state machine uses the following macro:
bool JoinDesired(S,G) { bool JoinDesired(S,G) {
return( immediate_olist(S,G) != NULL return( immediate_olist(S,G) != NULL
OR ( KeepaliveTimer(S,G) is running OR ( KeepaliveTimer(S,G) is running
AND inherited_olist(S,G) != NULL ) ) AND inherited_olist(S,G) != NULL ) )
} }
JoinDesired(S,G) is true when the router has forwarding state that would JoinDesired(S,G) is true when the router has forwarding state that
cause it to forward traffic for G using source tree state. The source would cause it to forward traffic for G using source tree state. The
tree state can either be as a result of active source-specific join source tree state can be as a result of either active source-specific
state, or the (S,G) Keepalive Timer and active non-source-specific join state, or the (S,G) Keepalive Timer and active non-source-
state. Note that although JoinDesired is true, the router's sending of a specific state. Note that although JoinDesired is true, the router's
Join(S,G) message may be suppressed by another router sending a sending of a Join(S,G) message may be suppressed by another router
Join(S,G) onto the upstream interface. sending a Join(S,G) onto the upstream interface.
Transitions from NotJoined State Transitions from NotJoined State
When the upstream (S,G) state machine is in NotJoined state, the When the upstream (S,G) state machine is in NotJoined state, the
following event may trigger a state transition: following event may trigger a state transition:
JoinDesired(S,G) becomes True JoinDesired(S,G) becomes True
The macro JoinDesired(S,G) becomes True, e.g., because the The macro JoinDesired(S,G) becomes True, e.g., because the
downstream state for (S,G) has changed so that at least one downstream state for (S,G) has changed so that at least one
interface is in inherited_olist(S,G). interface is in inherited_olist(S,G).
The upstream (S,G) state machine transitions to Joined state. The upstream (S,G) state machine transitions to Joined state.
Send Join(S,G) to the appropriate upstream neighbor, which is Send Join(S,G) to the appropriate upstream neighbor, which is
RPF'(S,G). Set the Join Timer (JT) to expire after t_periodic RPF'(S,G). Set the Join Timer (JT) to expire after t_periodic
seconds. seconds.
Transitions from Joined State Transitions from Joined State
When the upstream (S,G) state machine is in Joined state, the following When the upstream (S,G) state machine is in Joined state, the
events may trigger state transitions: following events may trigger state transitions:
JoinDesired(S,G) becomes False JoinDesired(S,G) becomes False
The macro JoinDesired(S,G) becomes False, e.g., because the The macro JoinDesired(S,G) becomes False, e.g., because the
downstream state for (S,G) has changed so no interface is in downstream state for (S,G) has changed so no interface is in
inherited_olist(S,G). inherited_olist(S,G).
The upstream (S,G) state machine transitions to NotJoined The upstream (S,G) state machine transitions to NotJoined
state. Send Prune(S,G) to the appropriate upstream neighbor, state. Send Prune(S,G) to the appropriate upstream neighbor,
which is RPF'(S,G). Cancel the Join Timer (JT), and set which is RPF'(S,G). Cancel the Join Timer (JT), and set
SPTbit(S,G) to FALSE. SPTbit(S,G) to FALSE.
skipping to change at page 74, line 25 skipping to change at page 75, line 13
interval. interval.
The upstream (S,G) state machine remains in Joined state. If The upstream (S,G) state machine remains in Joined state. If
the Join Timer is set to expire in more than t_override the Join Timer is set to expire in more than t_override
seconds, reset it so that it expires after t_override seconds. seconds, reset it so that it expires after t_override seconds.
See Prune(S,G,rpt) to RPF'(S,G) See Prune(S,G,rpt) to RPF'(S,G)
This event is only relevant if RPF_interface(S) is a shared This event is only relevant if RPF_interface(S) is a shared
medium. This router sees another router on RPF_interface(S) medium. This router sees another router on RPF_interface(S)
send a Prune(S,G,rpt) to RPF'(S,G). If the upstream router is send a Prune(S,G,rpt) to RPF'(S,G). If the upstream router is
an RFC 2362 compliant PIM router, then the Prune(S,G,rpt) will an RFC-2362-compliant PIM router, then the Prune(S,G,rpt) will
cause it to stop forwarding. For backwards compatibility, cause it to stop forwarding. For backwards compatibility,
this router should override the prune so that forwarding this router should override the prune so that forwarding
continues. continues.
The upstream (S,G) state machine remains in Joined state. If The upstream (S,G) state machine remains in Joined state. If
the Join Timer is set to expire in more than t_override the Join Timer is set to expire in more than t_override
seconds, reset it so that it expires after t_override seconds. seconds, reset it so that it expires after t_override seconds.
See Prune(*,G) to RPF'(S,G) See Prune(*,G) to RPF'(S,G)
This event is only relevant if RPF_interface(S) is a shared This event is only relevant if RPF_interface(S) is a shared
medium. This router sees another router on RPF_interface(S) medium. This router sees another router on RPF_interface(S)
send a Prune(*,G) to RPF'(S,G). If the upstream router is an send a Prune(*,G) to RPF'(S,G). If the upstream router is an
RFC 2362 compliant PIM router, then the Prune(*,G) will cause RFC-2362-compliant PIM router, then the Prune(*,G) will cause
it to stop forwarding. For backwards compatibility, this it to stop forwarding. For backwards compatibility, this
router should override the prune so that forwarding continues. router should override the prune so that forwarding continues.
The upstream (S,G) state machine remains in Joined state. If The upstream (S,G) state machine remains in Joined state. If
the Join Timer is set to expire in more than t_override the Join Timer is set to expire in more than t_override
seconds, reset it so that it expires after t_override seconds. seconds, reset it so that it expires after t_override seconds.
RPF'(S,G) changes due to an Assert RPF'(S,G) changes due to an Assert
The current next hop towards S changes due to an Assert(S,G) The current next hop towards S changes due to an Assert(S,G)
on the RPF_interface(S). on the RPF_interface(S).
skipping to change at page 75, line 4 skipping to change at page 75, line 41
the Join Timer is set to expire in more than t_override the Join Timer is set to expire in more than t_override
seconds, reset it so that it expires after t_override seconds. seconds, reset it so that it expires after t_override seconds.
RPF'(S,G) changes due to an Assert RPF'(S,G) changes due to an Assert
The current next hop towards S changes due to an Assert(S,G) The current next hop towards S changes due to an Assert(S,G)
on the RPF_interface(S). on the RPF_interface(S).
The upstream (S,G) state machine remains in Joined state. If The upstream (S,G) state machine remains in Joined state. If
the Join Timer is set to expire in more than t_override the Join Timer is set to expire in more than t_override
seconds, reset it so that it expires after t_override seconds. seconds, reset it so that it expires after t_override seconds.
If the Join Timer is set to expire in less than t_override If the Join Timer is set to expire in less than t_override
seconds, leave it unchanged. seconds, leave it unchanged.
RPF'(S,G) changes not due to an Assert RPF'(S,G) changes not due to an Assert
An event occurred which caused the next hop towards S to An event occurred that caused the next hop towards S to
change. Note that this transition does not occur if an Assert change. Note that this transition does not occur if an Assert
is active and the upstream interface does not change. is active and the upstream interface does not change.
The upstream (S,G) state machine remains in Joined state. The upstream (S,G) state machine remains in Joined state.
Send Join(S,G) to the new upstream neighbor which is the new Send Join(S,G) to the new upstream neighbor, which is the new
value of RPF'(S,G). Send Prune(S,G) to the old upstream value of RPF'(S,G). Send Prune(S,G) to the old upstream
neighbor, which is the old value of RPF'(S,G). Set the Join neighbor, which is the old value of RPF'(S,G). Set the Join
Timer (JT) to expire after t_periodic seconds. Timer (JT) to expire after t_periodic seconds.
RPF'(S,G) GenID changes RPF'(S,G) GenID changes
The Generation ID of the router that is RPF'(S,G) changes. The Generation ID of the router that is RPF'(S,G) changes.
This normally means that this neighbor has lost state, and so This normally means that this neighbor has lost state, and so
the state must be refreshed. the state must be refreshed.
The upstream (S,G) state machine remains in Joined state. If The upstream (S,G) state machine remains in Joined state. If
the Join Timer is set to expire in more than t_override the Join Timer is set to expire in more than t_override
seconds, reset it so that it expires after t_override seconds. seconds, reset it so that it expires after t_override seconds.
4.5.8. (S,G,rpt) Periodic Messages 4.5.8. (S,G,rpt) Periodic Messages
(S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP tree (S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP
with the RPT bit set, either to modify the results of (*,G) Joins, or to tree with the RPT bit set, either to modify the results of (*,G)
override the behavior of other upstream LAN peers. The next section Joins, or to override the behavior of other upstream LAN peers. The
describes the rules for sending triggered messages. This section next section describes the rules for sending triggered messages.
describes the rules for including a Prune(S,G,rpt) message with a This section describes the rules for including a Prune(S,G,rpt)
Join(*,G). message with a Join(*,G).
When a router is going to send a Join(*,G), it should use the following When a router is going to send a Join(*,G), it should use the
pseudocode, for each (S,G) for which it has state, to decide whether to following pseudocode, for each (S,G) for which it has state, to
include a Prune(S,G,rpt) in the compound Join/Prune message: decide whether to include a Prune(S,G,rpt) in the compound Join/Prune
message:
if( SPTbit(S,G) == TRUE ) { if( SPTbit(S,G) == TRUE ) {
# Note: If receiving (S,G) on the SPT, we only prune off the # Note: If receiving (S,G) on the SPT, we only prune off the
# shared tree if the RPF neighbors differ. # shared tree if the RPF neighbors differ.
if( RPF'(*,G) != RPF'(S,G) ) { if( RPF'(*,G) != RPF'(S,G) ) {
add Prune(S,G,rpt) to compound message add Prune(S,G,rpt) to compound message
} }
} else if ( inherited_olist(S,G,rpt) == NULL ) { } else if ( inherited_olist(S,G,rpt) == NULL ) {
# Note: all (*,G) olist interfaces received RPT prunes for (S,G). # Note: all (*,G) olist interfaces received RPT prunes for (S,G).
add Prune(S,G,rpt) to compound message add Prune(S,G,rpt) to compound message
} else if ( RPF'(*,G) != RPF'(S,G,rpt) { } else if ( RPF'(*,G) != RPF'(S,G,rpt) {
# Note: we joined the shared tree, but there was an (S,G) assert and # Note: we joined the shared tree, but there was an (S,G) assert
# the source tree RPF neighbor is different. # and the source tree RPF neighbor is different.
add Prune(S,G,rpt) to compound message add Prune(S,G,rpt) to compound message
} }
Note that Join(S,G,rpt) is not normally sent as a periodic message, but Note that Join(S,G,rpt) is normally sent not as a periodic message,
only as a triggered message. but only as a triggered message.
4.5.9. State Machine for (S,G,rpt) Triggered Messages 4.5.9. State Machine for (S,G,rpt) Triggered Messages
The state machine for (S,G,rpt) triggered messages is required per-(S,G) The state machine for (S,G,rpt) triggered messages is required per-
when there is (*,G) or (*,*,RP) join state at a router, and the router (S,G) when there is (*,G) or (*,*,RP) join state at a router, and the
or any of its upstream LAN peers wishes to prune S off the RP tree. router or any of its upstream LAN peers wishes to prune S off the RP
tree.
There are three states in the state machine. One of the states is when There are three states in the state machine. One of the states is
there is neither (*,G) nor (*,*,RP(G)) join state at this router. If when there is neither (*,G) nor (*,*,RP(G)) join state at this
there is (*,G) or (*,*,RP(G)) join state at the router, then the state router. If there is (*,G) or (*,*,RP(G)) join state at the router,
machine must be at one of the other two states. The three states are: then the state machine must be at one of the other two states. The
three states are:
Pruned(S,G,rpt) Pruned(S,G,rpt)
(*,G) or (*,*,RP(G)) Joined, but (S,G,rpt) pruned (*,G) or (*,*,RP(G)) Joined, but (S,G,rpt) pruned
NotPruned(S,G,rpt) NotPruned(S,G,rpt)
(*,G) or (*,*,RP(G)) Joined, and (S,G,rpt) not pruned (*,G) or (*,*,RP(G)) Joined, and (S,G,rpt) not pruned
RPTNotJoined(G) RPTNotJoined(G)
neither (*,G) nor (*,*,RP(G)) has been joined. neither (*,G) nor (*,*,RP(G)) has been joined.
In addition, there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which is In addition, there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which
used to delay triggered Join(S,G,rpt) messages to prevent implosions of is used to delay triggered Join(S,G,rpt) messages to prevent
triggered messages. implosions of triggered messages.
Figure 9: Upstream (S,G,rpt) state machine for triggered messages in Figure 9: Upstream (S,G,rpt) state machine for triggered messages
tabular form in tabular form
+---------------++-------------------------------------------------------------+ +------------++--------------------------------------------------------+
| || Event | | || Event |
| ++---------------+---------------+--------------+--------------+ | ++--------------+--------------+-------------+------------+
|Prev State || PruneDesired | PruneDesired | RPTJoin | inherited_ | |Prev State || PruneDesired | PruneDesired | RPTJoin | inherited_ |
| || (S,G,rpt) | (S,G,rpt) | Desired(G) | olist | | || (S,G,rpt) | (S,G,rpt) | Desired(G) | olist |
| || ->True | ->False | ->False | (S,G,rpt) | | || ->True | ->False | ->False | (S,G,rpt) |
| || | | | ->non-NULL | | || | | | ->non-NULL |
+---------------++---------------+---------------+--------------+--------------+ +------------++--------------+--------------+-------------+------------+
|RPTNotJoined || -> P state | - | - | -> NP state | |RPTNotJoined|| -> P state | - | - | -> NP state|
|(G) (NJ) || | | | | |(G) (NJ) || | | | |
+---------------++---------------+---------------+--------------+--------------+ +------------++--------------+--------------+-------------+------------+
|Pruned || - | -> NP state | -> NJ state | - | |Pruned || - | -> NP state | -> NJ state | - |
|(S,G,rpt) (P) || | Send Join | | | |(S,G,rpt) || | Send Join | | |
| || | (S,G,rpt) | | | |(P) || | (S,G,rpt) | | |
+---------------++---------------+---------------+--------------+--------------+ +------------++--------------+--------------+-------------+------------+
|NotPruned || -> P state | - | -> NJ state | - | |NotPruned || -> P state | - | -> NJ state | - |
|(S,G,rpt) || Send Prune | | Cancel OT | | |(S,G,rpt) || Send Prune | | Cancel OT | |
|(NP) || (S,G,rpt); | | | | |(NP) || (S,G,rpt); | | | |
| || Cancel OT | | | | | || Cancel OT | | | |
+---------------++---------------+---------------+--------------+--------------+ +------------++--------------+--------------+-------------+------------+
Additionally, we have the following transitions within the
NotPruned(S,G,rpt) state which are all used for prune override behavior.
+-----------------------------------------------------------------------+ Additionally, we have the following transitions within the
| In NotPruned(S,G,rpt) State | NotPruned(S,G,rpt) state, which are all used for prune override
+-----------+--------------+--------------+--------------+--------------+ behavior.
|Override | See Prune | See Join | See Prune | RPF' |
|Timer | (S,G,rpt) to | (S,G,rpt) to | (S,G) to | (S,G,rpt) -> |
|expires | RPF' | RPF' | RPF' | RPF' (*,G) |
| | (S,G,rpt) | (S,G,rpt) | (S,G,rpt) | |
+-----------+--------------+--------------+--------------+--------------+
|Send Join | OT = min(OT, | Cancel OT | OT = min(OT, | OT = min(OT, |
|(S,G,rpt); | t_override) | | t_override) | t_override) |
|Leave OT | | | | |
|unset | | | | |
+-----------+--------------+--------------+--------------+--------------+
Note that the min function in the above state machine considers a non- +----------------------------------------------------------------------+
running timer to have an infinite value (e.g. min(not-running, | In NotPruned(S,G,rpt) State |
t_override) = t_override). +----------+--------------+--------------+--------------+--------------+
|Override | See Prune | See Join | See Prune | RPF' |
|Timer | (S,G,rpt) to | (S,G,rpt) to | (S,G) to | (S,G,rpt) -> |
|expires | RPF' | RPF' | RPF' | RPF' (*,G) |
| | (S,G,rpt) | (S,G,rpt) | (S,G,rpt) | |
+----------+--------------+--------------+--------------+--------------+
|Send Join | OT = min(OT, | Cancel OT | OT = min(OT, | OT = min(OT, |
|(S,G,rpt);| t_override) | | t_override) | t_override) |
|Leave OT | | | | |
|unset | | | | |
+----------+--------------+--------------+--------------+--------------+
This state machine uses the following macros: Note that the min function in the above state machine considers a
non-running timer to have an infinite value (e.g., min(not-running,
t_override) = t_override).
bool RPTJoinDesired(G) { This state machine uses the following macros:
return (JoinDesired(*,G) OR JoinDesired(*,*,RP(G)))
}
RPTJoinDesired(G) is true when the router has forwarding state that bool RPTJoinDesired(G) {
would cause it to forward traffic for G using either (*,G) or (*,*,RP) return (JoinDesired(*,G) OR JoinDesired(*,*,RP(G)))
shared tree state. }
bool PruneDesired(S,G,rpt) { RPTJoinDesired(G) is true when the router has forwarding state that
return ( RPTJoinDesired(G) AND would cause it to forward traffic for G using either (*,G) or
( inherited_olist(S,G,rpt) == NULL (*,*,RP) shared tree state.
OR (SPTbit(S,G)==TRUE
AND (RPF'(*,G) != RPF'(S,G)) )))
}
PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true. If bool PruneDesired(S,G,rpt) {
RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true if either return ( RPTJoinDesired(G) AND
there are no outgoing interfaces that S would be forwarded on, or if the ( inherited_olist(S,G,rpt) == NULL
router has active (S,G) forwarding state but RPF'(*,G) != RPF'(S,G). OR (SPTbit(S,G)==TRUE
AND (RPF'(*,G) != RPF'(S,G)) )))
}
The state machine contains the following transition events: PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true.
If RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true
either if there are no outgoing interfaces that S would be forwarded
on, or if the router has active (S,G) forwarding state but RPF'(*,G)
!= RPF'(S,G).
See Join(S,G,rpt) to RPF'(S,G,rpt) The state machine contains the following transition events:
This event is only relevant in the "Not Pruned" state.
The router sees a Join(S,G,rpt) from someone else to RPF'(S,G,rpt), See Join(S,G,rpt) to RPF'(S,G,rpt)
which is the correct upstream neighbor. If we're in "NotPruned" This event is only relevant in the "Not Pruned" state.
state and the (S,G,rpt) Override Timer is running, then this is
because we have been triggered to send our own Join(S,G,rpt) to
RPF'(S,G,rpt). Someone else beat us to it, so there's no need to
send our own Join.
The action is to cancel the Override Timer. The router sees a Join(S,G,rpt) from someone else to
RPF'(S,G,rpt), which is the correct upstream neighbor. If we're
in "NotPruned" state and the (S,G,rpt) Override Timer is running,
then this is because we have been triggered to send our own
Join(S,G,rpt) to RPF'(S,G,rpt). Someone else beat us to it, so
there's no need to send our own Join.
See Prune(S,G,rpt) to RPF'(S,G,rpt) The action is to cancel the Override Timer.
This event is only relevant in the "NotPruned" state.
The router sees a Prune(S,G,rpt) from someone else to to See Prune(S,G,rpt) to RPF'(S,G,rpt)
RPF'(S,G,rpt), which is the correct upstream neighbor. If we're in This event is only relevant in the "NotPruned" state.
the "NotPruned" state, then we want to continue to receive traffic
from S destined for G, and that traffic is being supplied by
RPF'(S,G,rpt). Thus we need to override the Prune.
The action is to set the (S,G,rpt) Override Timer to the randomized The router sees a Prune(S,G,rpt) from someone else to
prune-override interval, t_override. However if the Override Timer RPF'(S,G,rpt), which is the correct upstream neighbor. If we're
is already running, we only set the timer if doing so would set it in the "NotPruned" state, then we want to continue to receive
to a lower value. At the end of this interval, if no-one else has traffic from S destined for G, and that traffic is being supplied
sent a Join, then we will do so. by RPF'(S,G,rpt). Thus, we need to override the Prune.
See Prune(S,G) to RPF'(S,G,rpt) The action is to set the (S,G,rpt) Override Timer to the
This event is only relevant in the "NotPruned" state. randomized prune-override interval, t_override. However, if the
Override Timer is already running, we only set the timer if doing
so would set it to a lower value. At the end of this interval, if
noone else has sent a Join, then we will do so.
This transition and action are the same as the above transition and See Prune(S,G) to RPF'(S,G,rpt)
action, except that the Prune does not have the RPT bit set. This This event is only relevant in the "NotPruned" state.
transition is necessary to be compatible with routers implemented
from RFC2362 that don't maintain separate (S,G) and (S,G,rpt)
state.
The (S,G,rpt) prune Override Timer expires This transition and action are the same as the above transition
This event is only relevant in the "NotPruned" state. and action, except that the Prune does not have the RPT bit set.
This transition is necessary to be compatible with routers
implemented from RFC2362 that don't maintain separate (S,G) and
(S,G,rpt) state.
When the Override Timer expires, we must send a Join(S,G,rpt) to The (S,G,rpt) prune Override Timer expires
RPF'(S,G,rpt) to override the Prune message that caused the timer This event is only relevant in the "NotPruned" state.
to be running. We only send this if RPF'(S,G,rpt) equals RPF'(*,G)
- if this were not the case, then the Join might be sent to a
router that does not have (*,G) or (*,*,RP(G)) Join state, and so
the behavior would not be well defined. If RPF'(S,G,rpt) is not
the same as RPF'(*,G), then it may stop forwarding S. However, if
this happens, then the router will send an AssertCancel(S,G), which
would then cause RPF'(S,G,rpt) to become equal to RPF'(*,G) (see
below).
RPF'(S,G,rpt) changes to become equal to RPF'(*,G) When the Override Timer expires, we must send a Join(S,G,rpt) to
This event is only relevant in the "NotPruned" state. RPF'(S,G,rpt) to override the Prune message that caused the timer
to be running. We only send this if RPF'(S,G,rpt) equals
RPF'(*,G); if this were not the case, then the Join might be sent
to a router that does not have (*,G) or (*,*,RP(G)) Join state,
and so the behavior would not be well defined. If RPF'(S,G,rpt)
is not the same as RPF'(*,G), then it may stop forwarding S.
However, if this happens, then the router will send an
AssertCancel(S,G), which would then cause RPF'(S,G,rpt) to become
equal to RPF'(*,G) (see below).
RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G) RPF'(S,G,rpt) changes to become equal to RPF'(*,G)
Assert has happened, which means that traffic from S is arriving on This event is only relevant in the "NotPruned" state.
the SPT, and so Prune(S,G,rpt) will have been sent to RPF'(*,G).
When RPF'(S,G,rpt) changes to become equal to RPF'(*,G), we need to
trigger a Join(S,G,rpt) to RPF'(*,G) to cause that router to start
forwarding S again.
The action is to set the (S,G,rpt) Override Timer to the randomized RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G)
prune-override interval t_override. However if the timer is Assert has happened, which means that traffic from S is arriving
already running, we only set the timer if doing so would set it to on the SPT, and so Prune(S,G,rpt) will have been sent to
a lower value. At the end of this interval, if no-one else has RPF'(*,G). When RPF'(S,G,rpt) changes to become equal to
sent a Join, then we will do so. RPF'(*,G), we need to trigger a Join(S,G,rpt) to RPF'(*,G) to
cause that router to start forwarding S again.
PruneDesired(S,G,rpt)->TRUE The action is to set the (S,G,rpt) Override Timer to the
See macro above. This event is relevant in the "NotPruned" and randomized prune-override interval t_override. However, if the
"RPTNotJoined(G)" states. timer is already running, we only set the timer if doing so would
set it to a lower value. At the end of this interval, if noone
else has sent a Join, then we will do so.
The router wishes to receive traffic for G, but does not wish to PruneDesired(S,G,rpt)->TRUE
receive traffic from S destined for G. This causes the router to See macro above. This event is relevant in the "NotPruned" and
transition into the Pruned state. "RPTNotJoined(G)" states.
If the router was previously in NotPruned state, then the action is The router wishes to receive traffic for G, but does not wish to
to send a Prune(S,G,rpt) to RPF'(S,G,rpt), and to cancel the receive traffic from S destined for G. This causes the router to
Override Timer. If the router was previously in RPTNotJoined(G) transition into the Pruned state.
state, then there is no need to trigger an action in this state
machine because sending a Prune(S,G,rpt) is handled by the rules
for sending the Join(*,G) or Join(*,*,RP).
PruneDesired(S,G,rpt)->FALSE If the router was previously in NotPruned state, then the action
See macro above. This transition is only relevant in the "Pruned" is to send a Prune(S,G,rpt) to RPF'(S,G,rpt), and to cancel the
state. Override Timer. If the router was previously in RPTNotJoined(G)
state, then there is no need to trigger an action in this state
machine because sending a Prune(S,G,rpt) is handled by the rules
for sending the Join(*,G) or Join(*,*,RP).
If the router is in the Pruned(S,G,rpt) state, and PruneDesired(S,G,rpt)->FALSE
PruneDesired(S,G,rpt) changes to FALSE, this could be because the See macro above. This transition is only relevant in the "Pruned"
router no longer has RPTJoinDesired(G) true, or it now wishes to state.
receive traffic from S again. If it is the former, then this
transition should not happen, but instead the
"RPTJoinDesired(G)->FALSE" transition should happen. Thus this
transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE
AND RPTJoinDesired(G)==TRUE"
The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt). If the router is in the Pruned(S,G,rpt) state, and
PruneDesired(S,G,rpt) changes to FALSE, this could be because the
router no longer has RPTJoinDesired(G) true, or it now wishes to
receive traffic from S again. If it is the former, then this
transition should not happen, but instead the
"RPTJoinDesired(G)->FALSE" transition should happen. Thus, this
transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE
AND RPTJoinDesired(G)==TRUE".
RPTJoinDesired(G)->FALSE The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt).
This event is relevant in the "Pruned" and "NotPruned" states.
The router no longer wishes to receive any traffic destined for G RPTJoinDesired(G)->FALSE
on the RP Tree. This causes a transition to the RPTNotJoined(G) This event is relevant in the "Pruned" and "NotPruned" states.
state, and the Override Timer is canceled if it was running. Any
further actions are handled by the appropriate upstream state
machine for (*,G) or (*,*,RP).
inherited_olist(S,G,rpt) becomes non-NULL The router no longer wishes to receive any traffic destined for G
This transition is only relevant in the RPTNotJoined(G) state. on the RP Tree. This causes a transition to the RPTNotJoined(G)
state, and the Override Timer is canceled if it was running. Any
further actions are handled by the appropriate upstream state
machine for (*,G) or (*,*,RP).
The router has joined the RP tree (handled by the (*,G) or (*,*,RP) inherited_olist(S,G,rpt) becomes non-NULL
upstream state machine as appropriate), and wants to receive This transition is only relevant in the RPTNotJoined(G) state.
traffic from S. This does not trigger any events in this state
machine, but causes a transition to the NotPruned(S,G,rpt) state. The router has joined the RP tree (handled by the (*,G) or
(*,*,RP) upstream state machine as appropriate) and wants to
receive traffic from S. This does not trigger any events in this
state machine, but causes a transition to the NotPruned(S,G,rpt)
state.
4.5.10. Background: (*,*,RP) and (S,G,rpt) Interaction 4.5.10. Background: (*,*,RP) and (S,G,rpt) Interaction
In sections 4.5.8 and 4.5.9 the mechanisms for sending periodic and In Sections 4.5.8 and 4.5.9, the mechanisms for sending periodic and
triggered (S,G,rpt) messages are described. The astute reader will note triggered (S,G,rpt) messages are described. The astute reader will
that periodic Prune(S,G,rpt) messages are only sent in PIM Join/Prune note that periodic Prune(S,G,rpt) messages are only sent in PIM
messages containing a Join(*,G), whereas it is possible for a triggered Join/Prune messages containing a Join(*,G), whereas it is possible
Prune(S,G,rpt) message to be sent when the router has no (*,G) join for a triggered Prune(S,G,rpt) message to be sent when the router has
state. This may seem like a contradiction, but in fact it is no (*,G) join state. This may seem like a contradiction, but in fact
intentional, and is a side effect of not optimizing (*,*,RP) behavior. it is intentional and is a side effect of not optimizing (*,*,RP)
behavior.
We first note that reception of a Join(*,*,RP) by itself does not cancel We first note that reception of a Join(*,*,RP) by itself does not
(S,G,rpt) prune state on that interface, whereas receiving a Join(*,G) cancel (S,G,rpt) prune state on that interface, whereas receiving a
by itself does cancel (S,G,rpt) prune state on that interface. Join(*,G) by itself does cancel (S,G,rpt) prune state on that
Similarly, reception of a Prune(*,G) on an interface with (*,*,RP) join interface. Similarly, reception of a Prune(*,G) on an interface with
state does not by itself prevent forwarding of G using the (*,*,RP) (*,*,RP) join state does not by itself prevent forwarding of G using
state - this is because a Prune(*,G) only serves to cancel (*,G) join the (*,*,RP) state; this is because a Prune(*,G) only serves to
state. Conceptually (*,*,RP) state functions "above" the normal (*,G) cancel (*,G) join state. Conceptually (*,*,RP) state functions
and (S,G) mechanisms, and so neither Join(*,*,RP) or Prune(*,*,RP) "above" the normal (*,G) and (S,G) mechanisms, and so neither
messages affect any other state. Join(*,*,RP) nor Prune(*,*,RP) messages affect any other state.
The upshot of this is that to prevent forwarding (S,G) on (*,*,RP) The upshot of this is that to prevent forwarding (S,G) on (*,*,RP)
state, a Prune(S,G,rpt) must be used. state, a Prune(S,G,rpt) must be used.
We also note that for historical reasons there is no Assert(*,*,RP) We also note that for historical reasons there is no Assert(*,*,RP)
message, so any forwarding contention is resolved using Assert(*,G) message, so any forwarding contention is resolved using Assert(*,G)
messages. messages.
We now need to consider the interaction between (*,*,RP) state and (*,G) We now need to consider the interaction between (*,*,RP) state and
state. If there is a need for an assert between two upstream routers on (*,G) state. If there is a need for an assert between two upstream
a LAN, we need to ensure that the correct thing happens for all routers on a LAN, we need to ensure that the correct thing happens
combinations of (*,*,RP) and (*,G) forwarding state. As there is no for all combinations of (*,*,RP) and (*,G) forwarding state. As
Assert(*,*,RP) message, no router can tell whether the assert winner has there is no Assert(*,*,RP) message, no router can tell whether the
(*,*,RP) state or (*,G) state. Thus a downstream router has to treat assert winner has (*,*,RP) state or (*,G) state. Thus, a downstream
the two the same and send its periodic Prune(S,G,rpt) messages to router has to treat the two the same and send its periodic
RPF'(*,G). Prune(S,G,rpt) messages to RPF'(*,G).
To avoid needing to specify all the complex override rules between To avoid needing to specify all the complex override rules between
(*,*,RP), (*,G) and (S,G,rpt), we simply require that to prune (S,G) off (*,*,RP), (*,G), and (S,G,rpt), we simply require that to prune (S,G)
the (*,*,RP) tree, a Join(*,G) must also be sent. off the (*,*,RP) tree, a Join(*,G) must also be sent.
If a router is receiving on (*,*,RP) state, and has not yet had (*,G) If a router is receiving on (*,*,RP) state and has not yet had (*,G)
state instantiated, it may still need to send a triggered Join(S,G,rpt) state instantiated, it may still need to send a triggered
to override a Prune(S,G,rpt) that it sees directed to RPF'(*,G) on its Join(S,G,rpt) to override a Prune(S,G,rpt) that it sees directed to
upstream interface. Hence triggered (S,G,rpt) messages may be sent when RPF'(*,G) on its upstream interface. Hence, triggered (S,G,rpt)
JoinDesired(*,G) is false but JoinDesired(*,*,RP) is true. messages may be sent when JoinDesired(*,G) is false but
JoinDesired(*,*,RP) is true.
Finally we note that there is an unoptimized case when the upstream Finally, we note that there is an unoptimized case when the upstream
router on a LAN already has (*,G) join and (S,G,rpt) prune state caused router on a LAN already has (*,G) join and (S,G,rpt) prune state
by an existing downstream router. If at this time a new Join(*,*,RP) is caused by an existing downstream router. If at this time a new
sent to the upstream router from a different downstream router, this Join(*,*,RP) is sent to the upstream router from a different
will not override the (S,G,rpt) prune state at the upstream router. The downstream router, this will not override the (S,G,rpt) prune state
override will not occur until the next time the original downstream at the upstream router. The override will not occur until the next
router resends its Prune(S,G,rpt). This case was considered to be not time the original downstream router resends its Prune(S,G,rpt). This
worth optimizing, as (*,*,RP) state is generally very long lived, and so case was not considered worth optimizing, as (*,*,RP) state is
any minor delays in getting traffic to a new PMBR seem unimportant. generally very long lived, and so any minor delays in getting traffic
to a new PMBR seem unimportant.
4.6. PIM Assert Messages 4.6. PIM Assert Messages
Where multiple PIM routers peer over a shared LAN it is possible for Where multiple PIM routers peer over a shared LAN, it is possible for
more than one upstream router to have valid forwarding state for a more than one upstream router to have valid forwarding state for a
packet, which can lead to packet duplication (see Section 3 "Multi- packet, which can lead to packet duplication (see Section 3.6). PIM
access LANs"). PIM does not attempt to prevent this from occurring. does not attempt to prevent this from occurring. Instead, it detects
Instead it detects when this has happened and elects a single forwarder when this has happened and elects a single forwarder amongst the
amongst the upstream routers to prevent further duplication. This upstream routers to prevent further duplication. This election is
election is performed using PIM Assert messages. Assert messages are performed using PIM Assert messages. Assert messages are also
also received by downstream routers on the LAN, and these cause received by downstream routers on the LAN, and these cause subsequent
subsequent Join/Prune messages to be sent to the upstream router that Join/Prune messages to be sent to the upstream router that won the
won the Assert. Assert.
In general, a PIM Assert message should only be accepted for processing In general, a PIM Assert message should only be accepted for
if it comes from a known PIM neighbor. A PIM router hears about PIM processing if it comes from a known PIM neighbor. A PIM router hears
neighbors through PIM Hello messages. If a router receives an Assert about PIM neighbors through PIM Hello messages. If a router receives
message from a particular IP source address and it has not seen a PIM an Assert message from a particular IP source address and it has not
Hello message from that source address, then the Assert message SHOULD seen a PIM Hello message from that source address, then the Assert
be discarded without further processing. In addition, if the Hello message SHOULD be discarded without further processing. In addition,
message from a neighbor was authenticated using the IPsec Authentication if the Hello message from a neighbor was authenticated using the
Header (AH) (see Section 6.3) then all Assert messages from that IPsec Authentication Header (AH) (see Section 6.3), then all Assert
neighbor MUST also be authenticated using IPsec AH. messages from that neighbor MUST also be authenticated using IPsec
AH.
We note that some older PIM implementations incorrectly fail to send We note that some older PIM implementations incorrectly fail to send
Hello messages on point-to-point interfaces, so we also RECOMMEND that a Hello messages on point-to-point interfaces, so we also RECOMMEND
configuration option be provided to allow interoperation with such older that a configuration option be provided to allow interoperation with
routers, but that this configuration option SHOULD NOT be enabled by such older routers, but that this configuration option SHOULD NOT be
default. enabled by default.
4.6.1. (S,G) Assert Message State Machine 4.6.1. (S,G) Assert Message State Machine
The (S,G) Assert state machine for interface I is shown in Figure 10. The (S,G) Assert state machine for interface I is shown in Figure 10.
There are three states: There are three states:
NoInfo (NI) NoInfo (NI)
This router has no (S,G) assert state on interface I. This router has no (S,G) assert state on interface I.
I am Assert Winner (W) I am Assert Winner (W)
This router has won an (S,G) assert on interface I. It is now This router has won an (S,G) assert on interface I. It is now
responsible for forwarding traffic from S destined for G out of responsible for forwarding traffic from S destined for G out of
interface I. Irrespective of whether it is the DR for I, while a interface I. Irrespective of whether it is the DR for I, while a
router is the assert winner, it is also responsible for forwarding router is the assert winner, it is also responsible for forwarding
traffic onto I on behalf of local hosts on I that have made traffic onto I on behalf of local hosts on I that have made
membership requests that specifically refer to S (and G). membership requests that specifically refer to S (and G).
I am Assert Loser (L) I am Assert Loser (L)
This router has lost an (S,G) assert on interface I. It must not This router has lost an (S,G) assert on interface I. It must not
forward packets from S destined for G onto interface I. If it is forward packets from S destined for G onto interface I. If it is
the DR on I, it is no longer responsible for forwarding traffic the DR on I, it is no longer responsible for forwarding traffic
onto I to satisfy local hosts with membership requests that onto I to satisfy local hosts with membership requests that
specifically refer to S and G. specifically refer to S and G.
In addition, there is also an Assert Timer (AT) that is used to time out In addition, there is also an Assert Timer (AT) that is used to time
asserts on the assert losers and to re-send asserts on the assert out asserts on the assert losers and to resend asserts on the assert
winner. winner.
Figure 10: Per-interface (S,G) Assert State machine in tabular form Figure 10: Per-interface (S,G) Assert State machine in tabular form
+-----------------------------------------------------------------------+ +----------------------------------------------------------------------+
| In NoInfo (NI) State | | In NoInfo (NI) State |
+---------------+-------------------+------------------+----------------+ +---------------+-------------------+------------------+---------------+
| Receive | Receive Assert | Data arrives | Receive | | Receive | Receive Assert | Data arrives | Receive |
| Inferior | with RPTbit | from S to G on | Acceptable | | Inferior | with RPTbit | from S to G on | Acceptable |
| Assert with | set and | I and | Assert with | | Assert with | set and | I and | Assert with |
| RPTbit clear | CouldAssert | CouldAssert | RPTbit clear | | RPTbit clear | CouldAssert | CouldAssert | RPTbit clear |
| and | (S,G,I) | (S,G,I) | and AssTrDes | | and | (S,G,I) | (S,G,I) | and AssTrDes |
| CouldAssert | | | (S,G,I) | | CouldAssert | | | (S,G,I) |
| (S,G,I) | | | | | (S,G,I) | | | |
+---------------+-------------------+------------------+----------------+ +---------------+-------------------+------------------+---------------+
| -> W state | -> W state | -> W state | -> L state | | -> W state | -> W state | -> W state | -> L state |
| [Actions A1] | [Actions A1] | [Actions A1] | [Actions A6] | | [Actions A1] | [Actions A1] | [Actions A1] | [Actions A6] |
+---------------+-------------------+------------------+----------------+ +---------------+-------------------+------------------+---------------+
+-----------------------------------------------------------------------+ +----------------------------------------------------------------------+
| In I Am Assert Winner (W) State | | In I Am Assert Winner (W) State |
+----------------+------------------+-----------------+-----------------+ +----------------+------------------+-----------------+----------------+
| Assert Timer | Receive | Receive | CouldAssert | | Assert Timer | Receive | Receive | CouldAssert |
| Expires | Inferior | Preferred | (S,G,I) -> | | Expires | Inferior | Preferred | (S,G,I) -> |
| | Assert | Assert | FALSE | | | Assert | Assert | FALSE |
+----------------+------------------+-----------------+-----------------+ +----------------+------------------+-----------------+----------------+
| -> W state | -> W state | -> L state | -> NI state | | -> W state | -> W state | -> L state | -> NI state |
| [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] |
+----------------+------------------+-----------------+-----------------+ +----------------+------------------+-----------------+----------------+
+---------------------------------------------------------------------+
| In I Am Assert Loser (L) State |
+-------------+-------------+-------------+-------------+-------------+
|Receive |Receive |Receive |Assert Timer |Current |
|Preferred |Acceptable |Inferior |Expires |Winner's |
|Assert |Assert with |Assert or | |GenID |
| |RPTbit clear |Assert | |Changes or |
| |from Current |Cancel from | |NLT Expires |
| |Winner |Current | | |
| | |Winner | | |
+-------------+-------------+-------------+-------------+-------------+
|-> L state |-> L state |-> NI state |-> NI state |-> NI state |
|[Actions A2] |[Actions A2] |[Actions A5] |[Actions A5] |[Actions A5] |
+-------------+-------------+-------------+-------------+-------------+
+-------------------------------------------------------------------------+ +----------------------------------------------------------------------+
| In I Am Assert Loser (L) State | | In I Am Assert Loser (L) State |
+-------------+--------------+--------------+--------------+--------------+ +----------------+-----------------+------------------+----------------+
|Receive | Receive | Receive | Assert Timer | Current | | AssTrDes | my_metric -> | RPF_interface | Receive |
|Preferred | Acceptable | Inferior | Expires | Winner's | | (S,G,I) -> | better than | (S) stops | Join(S,G) on |
|Assert | Assert with | Assert or | | GenID | | FALSE | winner's | being I | interface I |
| | RPTbit clear | Assert | | Changes or | | | metric | | |
| | from Current | Cancel from | | NLT Expires | +----------------+-----------------+------------------+----------------+
| | Winner | Current | | | | -> NI state | -> NI state | -> NI state | -> NI State |
| | | Winner | | | | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] |
+-------------+--------------+--------------+--------------+--------------+ +----------------+-----------------+------------------+----------------+
|-> L state | -> L state | -> NI state | -> NI state | -> NI state |
|[Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] |
+-------------+--------------+--------------+--------------+--------------+
+-----------------------------------------------------------------------+
| In I Am Assert Loser (L) State |
+----------------+-----------------+-------------------+----------------+
| AssTrDes | my_metric -> | RPF_interface | Receive |
| (S,G,I) -> | better than | (S) stops | Join(S,G) on |
| FALSE | winner's | being I | interface I |
| | metric | | |
+----------------+-----------------+-------------------+----------------+
| -> NI state | -> NI state | -> NI state | -> NI State |
| [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] |
+----------------+-----------------+-------------------+----------------+
Note that for reasons of compactness, "AssTrDes(S,G,I)" is used in the Note that for reasons of compactness, "AssTrDes(S,G,I)" is used in
state machine table to refer to AssertTrackingDesired(S,G,I). the state machine table to refer to AssertTrackingDesired(S,G,I).
Terminology: Terminology:
A "preferred assert" is one with a better metric than the current
winner.
An "acceptable assert" is one that has a better metric than A "preferred assert" is one with a better metric than the current
my_assert_metric(S,G,I). An assert is never considered acceptable winner.
if its metric is infinite.
An "inferior assert" is one with a worse metric than An "acceptable assert" is one that has a better metric than
my_assert_metric(S,G,I). An assert is never considered inferior if my_assert_metric(S,G,I). An assert is never considered acceptable
my_assert_metric(S,G,I) is infinite. if its metric is infinite.
The state machine uses the following macros: An "inferior assert" is one with a worse metric than
my_assert_metric(S,G,I). An assert is never considered inferior
if my_assert_metric(S,G,I) is infinite.
The state machine uses the following macros:
CouldAssert(S,G,I) = CouldAssert(S,G,I) =
SPTbit(S,G)==TRUE SPTbit(S,G)==TRUE
AND (RPF_interface(S) != I) AND (RPF_interface(S) != I)
AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
(+) ( pim_include(*,G) (-) pim_exclude(S,G) ) (+) ( pim_include(*,G) (-) pim_exclude(S,G) )
(-) lost_assert(*,G) (-) lost_assert(*,G)
(+) joins(S,G) (+) pim_include(S,G) ) ) (+) joins(S,G) (+) pim_include(S,G) ) )
CouldAssert(S,G,I) is true for downstream interfaces which would be in CouldAssert(S,G,I) is true for downstream interfaces that would be in
the inherited_olist(S,G) if (S,G) assert information was not taken into the inherited_olist(S,G) if (S,G) assert information was not taken
account. into account.
AssertTrackingDesired(S,G,I) = AssertTrackingDesired(S,G,I) =
(I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
(+) ( pim_include(*,G) (-) pim_exclude(S,G) ) (+) ( pim_include(*,G) (-) pim_exclude(S,G) )
(-) lost_assert(*,G) (-) lost_assert(*,G)
(+) joins(S,G) ) ) (+) joins(S,G) ) )
OR (local_receiver_include(S,G,I) == TRUE OR (local_receiver_include(S,G,I) == TRUE
AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me))) AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me)))
OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == TRUE)) OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == TRUE))
OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == TRUE) OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == TRUE)
AND (SPTbit(S,G) == FALSE)) AND (SPTbit(S,G) == FALSE))
AssertTrackingDesired(S,G,I) is true on any interface in which an (S,G) AssertTrackingDesired(S,G,I) is true on any interface in which an
assert might affect our behavior. (S,G) assert might affect our behavior.
The first three lines of AssertTrackingDesired account for (*,G) join The first three lines of AssertTrackingDesired account for (*,G) join
and local membership information received on I that might cause the and local membership information received on I that might cause the
router to be interested in asserts on I. router to be interested in asserts on I.
The 4th line accounts for (S,G) join information received on I that The 4th line accounts for (S,G) join information received on I that
might cause the router to be interested in asserts on I. might cause the router to be interested in asserts on I.
The 5th and 6th lines account for (S,G) local membership information on The 5th and 6th lines account for (S,G) local membership information
I. Note that we can't use the pim_include(S,G) macro since it uses on I. Note that we can't use the pim_include(S,G) macro since it
lost_assert(S,G,I) and would result in the router forgetting that it uses lost_assert(S,G,I) and would result in the router forgetting
lost an assert if the only reason it was interested was local that it lost an assert if the only reason it was interested was local
membership. The AssertWinner(S,G,I) check forces an assert winner to membership. The AssertWinner(S,G,I) check forces an assert winner to
keep on being responsible for forwarding as long as local receivers are keep on being responsible for forwarding as long as local receivers
present. Removing this check would make the assert winner give up are present. Removing this check would make the assert winner give
forwarding as soon as the information that originally caused it to up forwarding as soon as the information that originally caused it to
forward went away and the task of forwarding for local receivers would forward went away, and the task of forwarding for local receivers
revert back to the DR. would revert back to the DR.
The last three lines account for the fact that a router must keep track The last three lines account for the fact that a router must keep
of assert information on upstream interfaces in order to send joins and track of assert information on upstream interfaces in order to send
prunes to the proper neighbor. joins and prunes to the proper neighbor.
Transitions from NoInfo State Transitions from NoInfo State
When in NoInfo state, the following events may trigger transitions: When in NoInfo state, the following events may trigger transitions:
Receive Inferior Assert with RPTbit cleared AND Receive Inferior Assert with RPTbit cleared AND
CouldAssert(S,G,I)==TRUE CouldAssert(S,G,I)==TRUE
An assert is received for (S,G) with the RPT bit cleared that An assert is received for (S,G) with the RPT bit cleared that
is inferior to our own assert metric. The RPT bit cleared is inferior to our own assert metric. The RPT bit cleared
indicates that the sender of the assert had (S,G) forwarding indicates that the sender of the assert had (S,G) forwarding
state on this interface. If the assert is inferior to our state on this interface. If the assert is inferior to our
metric, then we must also have (S,G) forwarding state (i.e. metric, then we must also have (S,G) forwarding state (i.e.,
CouldAssert(S,G,I)==TRUE) as (S,G) asserts beat (*,G) asserts, CouldAssert(S,G,I)==TRUE) as (S,G) asserts beat (*,G) asserts,
and so we should be the assert winner. We transition to the and so we should be the assert winner. We transition to the
"I am Assert Winner" state, and perform Actions A1 (below). "I am Assert Winner" state and perform Actions A1 (below).
Receive Assert with RPTbit set AND CouldAssert(S,G,I)==TRUE Receive Assert with RPTbit set AND CouldAssert(S,G,I)==TRUE
An assert is received for (S,G) on I with the RPT bit set An assert is received for (S,G) on I with the RPT bit set
(it's a (*,G) assert). CouldAssert(S,G,I) is TRUE only if we (it's a (*,G) assert). CouldAssert(S,G,I) is TRUE only if we
have (S,G) forwarding state on this interface, so we should be have (S,G) forwarding state on this interface, so we should be
the assert winner. We transition to the "I am Assert Winner" the assert winner. We transition to the "I am Assert Winner"
state, and perform Actions A1 (below). state and perform Actions A1 (below).
An (S,G) data packet arrives on interface I, AND An (S,G) data packet arrives on interface I, AND
CouldAssert(S,G,I)==TRUE CouldAssert(S,G,I)==TRUE
An (S,G) data packet arrived on an downstream interface which An (S,G) data packet arrived on an downstream interface that
is in our (S,G) outgoing interface list. We optimistically is in our (S,G) outgoing interface list. We optimistically
assume that we will be the assert winner for this (S,G), and assume that we will be the assert winner for this (S,G), and
so we transition to the "I am Assert Winner" state, and so we transition to the "I am Assert Winner" state and perform
perform Actions A1 (below) which will initiate the assert Actions A1 (below), which will initiate the assert negotiation
negotiation for (S,G). for (S,G).
Receive Acceptable Assert with RPT bit clear AND Receive Acceptable Assert with RPT bit clear AND
AssertTrackingDesired(S,G,I)==TRUE AssertTrackingDesired(S,G,I)==TRUE
We're interested in (S,G) Asserts, either because I is a We're interested in (S,G) Asserts, either because I is a
downstream interface for which we have (S,G) or (*,G) downstream interface for which we have (S,G) or (*,G)
forwarding state, or because I is the upstream interface for S forwarding state, or because I is the upstream interface for S
and we have (S,G) forwarding state. The received assert has a and we have (S,G) forwarding state. The received assert has a
better metric than our own, so we do not win the Assert. We better metric than our own, so we do not win the Assert. We
transition to "I am Assert Loser" and perform actions A6 transition to "I am Assert Loser" and perform Actions A6
(below). (below).
Transitions from "I am Assert Winner" State Transitions from "I am Assert Winner" State
When in "I am Assert Winner" state, the following events trigger When in "I am Assert Winner" state, the following events trigger
transitions: transitions:
Assert Timer Expires Assert Timer Expires
The (S,G) Assert Timer expires. As we're in the Winner state, The (S,G) Assert Timer expires. As we're in the Winner state,
then we must still have (S,G) forwarding state that is we must still have (S,G) forwarding state that is actively
actively being kept alive. We re-send the (S,G) Assert and being kept alive. We resend the (S,G) Assert and restart the
restart the Assert Timer (Action A3 below). Note that the Assert Timer (Actions A3 below). Note that the assert
assert winner's Assert Timer is engineered to expire shortly winner's Assert Timer is engineered to expire shortly before
before timers on assert losers; this prevents unnecessary timers on assert losers; this prevents unnecessary thrashing
thrashing of the forwarder and periodic flooding of duplicate of the forwarder and periodic flooding of duplicate packets.
packets.
Receive Inferior Assert Receive Inferior Assert
We receive an (S,G) assert or (*,G) assert mentioning S that We receive an (S,G) assert or (*,G) assert mentioning S that
has a worse metric than our own. Whoever sent the assert is has a worse metric than our own. Whoever sent the assert is
in error, and so we re-send an (S,G) Assert, and restart the in error, and so we resend an (S,G) Assert and restart the
Assert Timer (Action A3 below). Assert Timer (Actions A3 below).
Receive Preferred Assert Receive Preferred Assert
We receive an (S,G) assert that has a better metric than our We receive an (S,G) assert that has a better metric than our
own. We transition to "I am Assert Loser" state and perform own. We transition to "I am Assert Loser" state and perform
actions A2 (below). Note that this may affect the value of Actions A2 (below). Note that this may affect the value of
JoinDesired(S,G) and PruneDesired(S,G,rpt) which could cause JoinDesired(S,G) and PruneDesired(S,G,rpt), which could cause
transitions in the upstream (S,G) or (S,G,rpt) state machines. transitions in the upstream (S,G) or (S,G,rpt) state machines.
CouldAssert(S,G,I) -> FALSE CouldAssert(S,G,I) -> FALSE
Our (S,G) forwarding state or RPF interface changed so as to Our (S,G) forwarding state or RPF interface changed so as to
make CouldAssert(S,G,I) become false. We can no longer make CouldAssert(S,G,I) become false. We can no longer
perform the actions of the assert winner, and so we transition perform the actions of the assert winner, and so we transition
to NoInfo state and perform actions A4 (below). This includes to NoInfo state and perform Actions A4 (below). This includes
sending a "canceling assert" with an infinite metric. sending a "canceling assert" with an infinite metric.
Transitions from "I am Assert Loser" State Transitions from "I am Assert Loser" State
When in "I am Assert Loser" state, the following transitions can occur: When in "I am Assert Loser" state, the following transitions can
occur:
Receive Preferred Assert Receive Preferred Assert
We receive an assert that is better than that of the current We receive an assert that is better than that of the current
assert winner. We stay in Loser state, and perform actions A2 assert winner. We stay in Loser state and perform Actions A2
below. below.
Receive Acceptable Assert with RPTbit clear from Current Winner Receive Acceptable Assert with RPTbit clear from Current Winner
We receive an assert from the current assert winner that is We receive an assert from the current assert winner that is
better than our own metric for this (S,G) (although the metric better than our own metric for this (S,G) (although the metric
may be worse than the winner's previous metric). We stay in may be worse than the winner's previous metric). We stay in
Loser state, and perform actions A2 below. Loser state and perform Actions A2 below.
Receive Inferior Assert or Assert Cancel from Current Winner Receive Inferior Assert or Assert Cancel from Current Winner
We receive an assert from the current assert winner that is We receive an assert from the current assert winner that is
worse than our own metric for this group (typically the worse than our own metric for this group (typically, because
winner's metric became worse or because it is an assert the winner's metric became worse or because it is an assert
cancel). We transition to NoInfo state, deleting the (S,G) cancel). We transition to NoInfo state, deleting the (S,G)
assert information and allowing the normal PIM Join/Prune assert information and allowing the normal PIM Join/Prune
mechanisms to operate. Usually we will eventually re-assert mechanisms to operate. Usually, we will eventually re-assert
and win when data packets from S have started flowing again. and win when data packets from S have started flowing again.
Assert Timer Expires Assert Timer Expires
The (S,G) Assert Timer expires. We transition to NoInfo The (S,G) Assert Timer expires. We transition to NoInfo
state, deleting the (S,G) assert information (action A5 state, deleting the (S,G) assert information (Actions A5
below). below).
Current Winner's GenID Changes or NLT Expires Current Winner's GenID Changes or NLT Expires
The Neighbor Liveness Timer associated with the current winner The Neighbor Liveness Timer associated with the current winner
expires or we receive a Hello message from the current winner expires or we receive a Hello message from the current winner
reporting a different GenID from the one it previously reporting a different GenID from the one it previously
reported. This indicates that the current winner's interface reported. This indicates that the current winner's interface
or router has gone down (and may have come back up), and so we or router has gone down (and may have come back up), and so we
must assume it no longer knows it was the winner. We must assume it no longer knows it was the winner. We
transition to the NoInfo state, deleting this (S,G) assert transition to the NoInfo state, deleting this (S,G) assert
information (action A5 below). information (Actions A5 below).
AssertTrackingDesired(S,G,I)->FALSE AssertTrackingDesired(S,G,I)->FALSE
AssertTrackingDesired(S,G,I) becomes FALSE. Our forwarding AssertTrackingDesired(S,G,I) becomes FALSE. Our forwarding
state has changed so that (S,G) Asserts on interface I are no state has changed so that (S,G) Asserts on interface I are no
longer of interest to us. We transition to the NoInfo state, longer of interest to us. We transition to the NoInfo state,
deleting the (S,G) assert information. deleting the (S,G) assert information.
My metric becomes better than the assert winner's metric My metric becomes better than the assert winner's metric
my_assert_metric(S,G,I) has changed so that now my assert my_assert_metric(S,G,I) has changed so that now my assert
metric for (S,G) is better than the metric we have stored for metric for (S,G) is better than the metric we have stored for
current assert winner. This might happen the underlying current assert winner. This might happen when the underlying
routing metric changes, or when CouldAssert(S,G,I) becomes routing metric changes, or when CouldAssert(S,G,I) becomes
true; for example, when SPTbit(S,G) becomes true. We true; for example, when SPTbit(S,G) becomes true. We
transition to NoInfo state, delete this (S,G) assert state transition to NoInfo state, delete this (S,G) assert state
(action A5 below), and allow the normal PIM Join/Prune (Actions A5 below), and allow the normal PIM Join/Prune
mechanisms to operate. Usually we will eventually re-assert mechanisms to operate. Usually, we will eventually re-assert
and win when data packets from S have started flowing again. and win when data packets from S have started flowing again.
RPF_interface(S) stops being interface I RPF_interface(S) stops being interface I
Interface I used to be the RPF interface for S, and now it is Interface I used to be the RPF interface for S, and now it is
not. We transition to NoInfo state, deleting this (S,G) not. We transition to NoInfo state, deleting this (S,G)
assert state (action A5 below). assert state (Actions A5 below).
Receive Join(S,G) on Interface I Receive Join(S,G) on Interface I
We receive a Join(S,G) that has the Upstream Neighbor Address We receive a Join(S,G) that has the Upstream Neighbor Address
field set to my primary IP address on interface I. The action field set to my primary IP address on interface I. The action
is to transition to NoInfo state, and delete this (S,G) assert is to transition to NoInfo state, delete this (S,G) assert
state (action A5 below), and allow the normal PIM Join/Prune state (Actions A5 below), and allow the normal PIM Join/Prune
mechanisms to operate. If whoever sent the Join was in error, mechanisms to operate. If whoever sent the Join was in error,
then the normal assert mechanism will eventually re-apply and then the normal assert mechanism will eventually re-apply, and
we will lose the assert again. However whoever sent the we will lose the assert again. However, whoever sent the
assert may know that the previous assert winner has died, and assert may know that the previous assert winner has died, and
so we may end up being the new forwarder. so we may end up being the new forwarder.
(S,G) Assert State machine Actions (S,G) Assert State machine Actions
A1: Send Assert(S,G) A1: Send Assert(S,G).
Set Assert Timer to (Assert_Time - Assert_Override_Interval) Set Assert Timer to (Assert_Time - Assert_Override_Interval).
Store self as AssertWinner(S,G,I) Store self as