draft-ietf-pim-sm-v2-new-03.txt   draft-ietf-pim-sm-v2-new-04.txt 
Internet Engineering Task Force PIM WG Internet Engineering Task Force PIM WG
INTERNET-DRAFT Bill Fenner/AT&T INTERNET-DRAFT Bill Fenner/AT&T
draft-ietf-pim-sm-v2-new-03.txt Mark Handley/ACIRI draft-ietf-pim-sm-v2-new-04.txt Mark Handley/ACIRI
Hugh Holbrook/Cisco Hugh Holbrook/Cisco
Isidor Kouvelas/Cisco Isidor Kouvelas/Cisco
20 July 2001 21 November 2001
Expires: January 2002 Expires: May 2002
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 Document
This document is an Internet-Draft and is in full conformance with all This document is an Internet-Draft and is in full conformance with all
provisions of Section 10 of RFC2026. provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering Task Internet-Drafts are working documents of the Internet Engineering Task
skipping to change at page 3, line 20 skipping to change at page 3, line 20
2.2. Pseudocode Notation. . . . . . . . . . . . . . . . . . . . . . 6 2.2. Pseudocode Notation. . . . . . . . . . . . . . . . . . . . . . 6
3. PIM-SM Protocol Overview. . . . . . . . . . . . . . . . . . . . . 7 3. PIM-SM Protocol Overview. . . . . . . . . . . . . . . . . . . . . 7
4. Protocol Specification. . . . . . . . . . . . . . . . . . . . . . 12 4. Protocol Specification. . . . . . . . . . . . . . . . . . . . . . 12
4.1. PIM Protocol State . . . . . . . . . . . . . . . . . . . . . . 12 4.1. PIM Protocol State . . . . . . . . . . . . . . . . . . . . . . 12
4.1.1. General Purpose State . . . . . . . . . . . . . . . . . . . 13 4.1.1. General Purpose State . . . . . . . . . . . . . . . . . . . 13
4.1.2. (*,*,RP) State. . . . . . . . . . . . . . . . . . . . . . . 14 4.1.2. (*,*,RP) State. . . . . . . . . . . . . . . . . . . . . . . 14
4.1.3. (*,G) State . . . . . . . . . . . . . . . . . . . . . . . . 15 4.1.3. (*,G) State . . . . . . . . . . . . . . . . . . . . . . . . 15
4.1.4. (S,G) State . . . . . . . . . . . . . . . . . . . . . . . . 16 4.1.4. (S,G) State . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1.5. (S,G,rpt) State . . . . . . . . . . . . . . . . . . . . . . 18 4.1.5. (S,G,rpt) State . . . . . . . . . . . . . . . . . . . . . . 18
4.1.6. State Summarization Macros. . . . . . . . . . . . . . . . . 19 4.1.6. State Summarization Macros. . . . . . . . . . . . . . . . . 19
4.2. Data Packet Forwarding Rules . . . . . . . . . . . . . . . . . 23 4.2. Data Packet Forwarding Rules . . . . . . . . . . . . . . . . . 24
4.2.1. Last hop switchover to the SPT. . . . . . . . . . . . . . . 26 4.2.1. Last hop switchover to the SPT. . . . . . . . . . . . . . . 26
4.2.2. Setting and Clearing the (S,G) SPT bit. . . . . . . . . . . 26 4.2.2. Setting and Clearing the (S,G) SPT bit. . . . . . . . . . . 26
4.3. PIM Register Messages. . . . . . . . . . . . . . . . . . . . . 28 4.3. PIM Register Messages. . . . . . . . . . . . . . . . . . . . . 28
4.3.1. Sending Register Messages from the DR . . . . . . . . . . . 28 4.3.1. Sending Register Messages from the DR . . . . . . . . . . . 28
4.3.2. Receiving Register Messages at the RP . . . . . . . . . . . 31 4.3.2. Receiving Register Messages at the RP . . . . . . . . . . . 32
4.4. PIM Join/Prune Messages. . . . . . . . . . . . . . . . . . . . 33 4.4. PIM Join/Prune Messages. . . . . . . . . . . . . . . . . . . . 33
4.4.1. Receiving (*,*,RP) Join/Prune Messages. . . . . . . . . . . 33 4.4.1. Receiving (*,*,RP) Join/Prune Messages. . . . . . . . . . . 34
4.4.2. Receiving (*,G) Join/Prune Messages . . . . . . . . . . . . 37 4.4.2. Receiving (*,G) Join/Prune Messages . . . . . . . . . . . . 37
4.4.3. Receiving (S,G) Join/Prune Messages . . . . . . . . . . . . 41 4.4.3. Receiving (S,G) Join/Prune Messages . . . . . . . . . . . . 41
4.4.4. Receiving (S,G,rpt) Join/Prune Messages . . . . . . . . . . 44 4.4.4. Receiving (S,G,rpt) Join/Prune Messages . . . . . . . . . . 45
4.4.5. Sending (*,*,RP) Join/Prune Messages. . . . . . . . . . . . 50 4.4.5. Sending (*,*,RP) Join/Prune Messages. . . . . . . . . . . . 51
4.4.6. Sending (*,G) Join/Prune Messages . . . . . . . . . . . . . 55 4.4.6. Sending (*,G) Join/Prune Messages . . . . . . . . . . . . . 55
4.4.7. Sending (S,G) Join/Prune Messages . . . . . . . . . . . . . 59 4.4.7. Sending (S,G) Join/Prune Messages . . . . . . . . . . . . . 59
4.4.8. (S,G,rpt) Periodic Messages . . . . . . . . . . . . . . . . 64 4.4.8. (S,G,rpt) Periodic Messages . . . . . . . . . . . . . . . . 64
4.4.9. State Machine for (S,G,rpt) Triggered 4.4.9. State Machine for (S,G,rpt) Triggered
Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.5. PIM Assert Messages. . . . . . . . . . . . . . . . . . . . . . 69 4.5. PIM Assert Messages. . . . . . . . . . . . . . . . . . . . . . 69
4.5.1. (S,G) Assert Message State Machine. . . . . . . . . . . . . 69 4.5.1. (S,G) Assert Message State Machine. . . . . . . . . . . . . 69
4.5.2. (*,G) Assert Message State Machine. . . . . . . . . . . . . 76 4.5.2. (*,G) Assert Message State Machine. . . . . . . . . . . . . 77
4.5.3. Assert Metrics. . . . . . . . . . . . . . . . . . . . . . . 82 4.5.3. Assert Metrics. . . . . . . . . . . . . . . . . . . . . . . 83
4.5.4. AssertCancel Messages . . . . . . . . . . . . . . . . . . . 84 4.5.4. AssertCancel Messages . . . . . . . . . . . . . . . . . . . 84
4.5.5. Assert State Macros . . . . . . . . . . . . . . . . . . . . 84 4.5.5. Assert State Macros . . . . . . . . . . . . . . . . . . . . 84
4.6. Designated Routers (DR) and Hello Messages . . . . . . . . . . 87 4.6. Designated Routers (DR) and Hello Messages . . . . . . . . . . 87
4.6.1. Sending Hello Messages. . . . . . . . . . . . . . . . . . . 87 4.6.1. Sending Hello Messages. . . . . . . . . . . . . . . . . . . 87
4.6.2. DR Election . . . . . . . . . . . . . . . . . . . . . . . . 88 4.6.2. DR Election . . . . . . . . . . . . . . . . . . . . . . . . 89
4.6.3. Reducing Prune Propagation Delay on LANs. . . . . . . . . . 90 4.6.3. Reducing Prune Propagation Delay on LANs. . . . . . . . . . 90
4.7. PIM Bootstrap and RP Discovery . . . . . . . . . . . . . . . . 92 4.7. PIM Multicast Border Router Behavior . . . . . . . . . . . . . 93
4.7.1. Group-to-RP Mapping . . . . . . . . . . . . . . . . . . . . 94 4.7.1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.7.2. Hash Function . . . . . . . . . . . . . . . . . . . . . . . 94 4.7.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.8. Source-Specific Multicast. . . . . . . . . . . . . . . . . . . 95 4.8. PIM Bootstrap and RP Discovery . . . . . . . . . . . . . . . . 95
4.8.1. Protocol Modifications for SSM destination 4.8.1. Group-to-RP Mapping . . . . . . . . . . . . . . . . . . . . 97
addresses. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.8.2. Hash Function . . . . . . . . . . . . . . . . . . . . . . . 97
4.8.2. PIM-SSM-only Routers. . . . . . . . . . . . . . . . . . . . 96 4.9. Source-Specific Multicast. . . . . . . . . . . . . . . . . . . 98
4.9. PIM Packet Formats . . . . . . . . . . . . . . . . . . . . . . 98 4.9.1. Protocol Modifications for SSM destination
4.9.1. Encoded Source and Group Address Formats. . . . . . . . . . 99 addresses. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.9.2. Hello Message Format. . . . . . . . . . . . . . . . . . . . 102 4.9.2. PIM-SSM-only Routers. . . . . . . . . . . . . . . . . . . . 99
4.9.3. Register Message Format . . . . . . . . . . . . . . . . . . 104 4.10. PIM Packet Formats. . . . . . . . . . . . . . . . . . . . . . 101
4.9.4. Register-Stop Message Format. . . . . . . . . . . . . . . . 106 4.10.1. Encoded Source and Group Address
4.9.5. Join/Prune Message Format . . . . . . . . . . . . . . . . . 106 Formats. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.9.5.1. Group Set Source List Rules. . . . . . . . . . . . . . . 109 4.10.2. Hello Message Format . . . . . . . . . . . . . . . . . . . 105
4.9.5.2. Group Set Fragmentation. . . . . . . . . . . . . . . . . 112 4.10.3. Register Message Format. . . . . . . . . . . . . . . . . . 107
4.9.6. Assert Message Format . . . . . . . . . . . . . . . . . . . 113 4.10.4. RegisterStop Message Format. . . . . . . . . . . . . . . . 109
4.10. PIM Timers. . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.10.5. Join/Prune Message Format. . . . . . . . . . . . . . . . . 109
4.11. Timer Values. . . . . . . . . . . . . . . . . . . . . . . . . 116 4.10.5.1. Group Set Source List Rules . . . . . . . . . . . . . . 112
5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 122 4.10.5.2. Group Set Fragmentation . . . . . . . . . . . . . . . . 115
5.1. PIM Address Family . . . . . . . . . . . . . . . . . . . . . . 122 4.10.6. Assert Message Format. . . . . . . . . . . . . . . . . . . 116
5.2. PIM Hello Options. . . . . . . . . . . . . . . . . . . . . . . 123 4.11. PIM Timers. . . . . . . . . . . . . . . . . . . . . . . . . . 117
6. Security Considerations . . . . . . . . . . . . . . . . . . . . . 123 4.12. Timer Values. . . . . . . . . . . . . . . . . . . . . . . . . 119
6.1. Attacks based on forged messages . . . . . . . . . . . . . . . 123 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 125
6.1.1. Forged link-local messages. . . . . . . . . . . . . . . . . 123 5.1. PIM Address Family . . . . . . . . . . . . . . . . . . . . . . 125
6.1.2. Forged unicast messages . . . . . . . . . . . . . . . . . . 124 5.2. PIM Hello Options. . . . . . . . . . . . . . . . . . . . . . . 126
6.2. Non-cryptographic Authentication Mechanisms. . . . . . . . . . 124 6. Security Considerations . . . . . . . . . . . . . . . . . . . . . 126
6.2.1. Register Nonces . . . . . . . . . . . . . . . . . . . . . . 125 6.1. Attacks based on forged messages . . . . . . . . . . . . . . . 126
6.3. Authentication using IPsec . . . . . . . . . . . . . . . . . . 125 6.1.1. Forged link-local messages. . . . . . . . . . . . . . . . . 126
6.3.1. Protecting link-local multicast messages. . . . . . . . . . 126 6.1.2. Forged unicast messages . . . . . . . . . . . . . . . . . . 127
6.3.2. Protecting unicast messages . . . . . . . . . . . . . . . . 126 6.2. Non-cryptographic Authentication Mechanisms. . . . . . . . . . 127
6.3.2.1. Register messages. . . . . . . . . . . . . . . . . . . . 126 6.3. Authentication using IPsec . . . . . . . . . . . . . . . . . . 128
6.3.2.2. Register Stop messages . . . . . . . . . . . . . . . . . 127 6.3.1. Protecting link-local multicast messages. . . . . . . . . . 128
6.4. Denial of Service Attacks. . . . . . . . . . . . . . . . . . . 127 6.3.2. Protecting unicast messages . . . . . . . . . . . . . . . . 129
7. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . . . 127 6.3.2.1. Register messages. . . . . . . . . . . . . . . . . . . . 129
8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 128 6.3.2.2. Register Stop messages . . . . . . . . . . . . . . . . . 129
9. References. . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 6.4. Denial of Service Attacks. . . . . . . . . . . . . . . . . . . 130
10. Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 7. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . . . 130
8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 131
9. References. . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
10. Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
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 (PIM-SM)
because, although it may use the underlying unicast routing to provide because, although it may use the underlying unicast routing to provide
reverse-path information for multicast tree building, it is not reverse-path information for multicast tree building, it is not
dependent on any particular unicast routing protocol. dependent on any particular unicast routing protocol.
skipping to change at page 6, line 8 skipping to change at page 6, line 8
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 routers
connected to it. If the LAN has directly connected hosts, then a connected to it. If the LAN has directly connected hosts, then a
single one of these routers, the DR, will act on behalf of those single one of these routers, the DR, will act on behalf of those
hosts with respect to the PIM-SM protocol. A single DR is elected hosts with respect to the PIM-SM protocol. A single DR is elected
per LAN using a simple election process. per LAN 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 MBGP that carry
multicast-specific topology information. In PIM-SM this is used multicast-specific topology information. In PIM-SM, the MRIB is
to make decisions regarding where to forward Join/Prune messages. used to decide where to send Join/Prune messages. A secondary
function of the MRIB is to provide routing metrics for destination
addresses, these metrics are 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 a
router with respect to an address is the neighbor that the MRIB router with respect to an address is the neighbor that the MRIB
indicates should be used to forward packets to that address. In indicates should be used to forward packets to that address. In
the case of a PIM-SM multicast group, the RPF neighbor is the the case of a PIM-SM multicast group, the RPF neighbor is the
router that a Join message for that group would be directed to, in router that a Join message for that group would be directed to, in
the absence of modifying Assert state. 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 PIM
router that has been created by receiving PIM Join/Prune messages, router that has been created by receiving PIM Join/Prune messages,
PIM Assert messages, and IGMP information from local hosts. It PIM Assert messages, and IGMP or MLD information from local hosts.
essentially stores the state of all multicast distribution trees It essentially stores the state of all multicast distribution
at that router. 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 router.
However, although this specification defines forwarding in terms However, although this specification defines forwarding in terms
of the TIB, to actually forward packets using the TIB is very of the TIB, to actually forward packets using the TIB is very
inefficient. Instead a real router implementation will normally inefficient. Instead a real router implementation will normally
build an efficient MFIB from the TIB state to perform forwarding. build an efficient MFIB from the TIB state to perform forwarding.
How this is done is implementation-specific, and is not discussed How this is done is implementation-specific, and is not discussed
in this document. in this document.
skipping to change at page 7, line 25 skipping to change at page 7, line 28
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 as
an introduction to how PIM-SM works, and is NOT definitive. For the an introduction to how PIM-SM works, and is NOT definitive. For the
definitive specification, see Section 4. 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 MRIB or
Multicast Routing Information Base. The routes in this table may be Multicast Routing Information Base. The routes in this table may be
taken directly from the unicast routing table, or it may be different taken directly from the unicast routing table, or it may be different
and provided by a separate routing protocol such as MBGP [1]. In any and provided by a separate routing protocol such as MBGP [1]. Regardless
event, the routes in the MRIB must represent a multicast-capable path to of how it is created, the primary role of the MRIB in the PIM protocol
each subnet. The MRIB is used to determine the path that PIM control is to provide the next hop router along a multicast-capable path to each
messages such as Join messages take to get to the source subnet, and destination subnet. The MRIB is used to determine the next hop neighbor
data flows along the reverse path of the Join messages. Thus, in to which any PIM Join/Prune message is sent. Data flows along the
contrast to the unicast RIB where the routes give a path that data reverse path of the Join messages. Thus, in contrast to the unicast RIB
packets take to get to each subnet, the MRIB gives reverse-path which specifies the next hop that a data packet would take to get to
information, and indicates the path that data packets would take from some subnet, the MRIB gives reverse-path information, and indicates the
each subnet to the router that has the MRIB. path that a 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 [2], 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 a-
priori of the existence of the others. This is essentially done in 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 any
time, all three phases may be occur simultaneously. time, all three phases may be occur simultaneously.
Phase One: RP Tree 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 receiving
traffic destined for a multicast group. Typically it does this using traffic destined for a multicast group. Typically it does this using
IGMP [3], but other mechanisms might also serve this purpose. One of IGMP [6] or MLD [4], but other mechanisms might also serve this purpose.
the receiver's local routers is elected as the Designated Router (DR) One of the receiver's local routers is elected as the Designated Router
for that subnet. On receiving the receiver's expression of interest,
the DR then sends a PIM Join message towards the RP for that multicast
group. This Join message is known as a (*,G) Join because it joins
group G for all sources to that group. The (*,G) Join travels hop-by-
hop towards the RP for the group, and in each router it passes through, (DR) for that subnet. On receiving the receiver's expression of
multicast tree state for group G is instantiated. Eventually the (*,G) interest, the DR then sends a PIM Join message towards the RP for that
Join either reaches the RP, or reaches a router that already has (*,G) multicast group. This Join message is known as a (*,G) Join because it
Join state for that group. When many receivers join the group, their joins group G for all sources to that group. The (*,G) Join travels
Join messages converge on the RP, and form a distribution tree for group hop-by-hop towards the RP for the group, and in each router it passes
G that is rooted at the RP. This is known as the RP Tree (RPT), and is through, multicast tree state for group G is instantiated. Eventually
also known as the shared tree because it is shared by all sources the (*,G) Join either reaches the RP, or reaches a router that already
sending to that group. Join messages are resent periodically so long as has (*,G) Join state for that group. When many receivers join the
the receiver remains in the group. When all receivers on a leaf-network group, their Join messages converge on the RP, and form a distribution
leave the group, the DR will send a PIM (*,G) Prune message towards the tree for group G that is rooted at the RP. This is known as the RP Tree
RP for that multicast group. However if the prune message is not sent (RPT), and is also known as the shared tree because it is shared by all
for any reason, the state will eventually time out. sources sending to that group. Join messages are resent periodically so
long as the receiver remains in the group. When all receivers on a
leaf-network leave the group, the DR will send a PIM (*,G) Prune message
towards the RP for 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 RP.
The RP receives these encapsulated data packets, decapsulates them, and The RP receives these encapsulated data packets, decapsulates them, and
forwards them onto the shared tree. The packets then follow the (*,G) forwards them onto the shared tree. The packets then follow the (*,G)
multicast tree state in the routers on the RP Tree, being replicated multicast tree state in the routers on the RP Tree, being replicated
wherever the RP Tree branches, and eventually reaching all the receivers wherever the RP Tree branches, and eventually reaching all the receivers
for that multicast group. The process of encapsulating data packets to for that multicast group. The process of encapsulating data packets to
the RP is called registering, and the encapsulation packets are known as the RP is called registering, and the encapsulation packets are known as
skipping to change at page 8, line 48 skipping to change at page 9, line 4
appropriate hardware for these tasks. 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 entail the packets traveling a relatively long distance to reach
receivers that are close to the sender. For some applications, this receivers that are close to the sender. For some applications, this
increased latency is undesirable. increased latency 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. To
do this, when the RP receives a register-encapsulated data packet from do this, when the RP receives a register-encapsulated data packet from
source S on group G, it will normally initiate an (S,G) source-specific source S on group G, it will normally initiate an (S,G) source-specific
Join towards S. This join message travels hop-by-hop towards S, Join towards S. This Join message travels hop-by-hop towards S,
instantiating (S,G) multicast tree state in the routers along the path. instantiating (S,G) multicast tree state in the routers along the path.
(S,G) multicast tree state is used only to forward packets for group G (S,G) multicast tree state is used only to forward packets for group G
if those packets come from source S. Eventually the Join message if those packets come from source S. Eventually the Join message
reaches S's subnet or a router that already has (S,G) multicast tree reaches S's subnet or a router that already has (S,G) multicast tree
state, and then packets from S start to flow following the (S,G) tree state, and then packets from S start to flow following the (S,G) tree
state towards the RP. These data packets may also reach routers with state towards the RP. These data packets may also reach routers with
(*,G) state along the path towards the RP - if so, they can short-cut (*,G) state along the path towards the RP - if so, they can short-cut
onto the RP tree at this point. 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 for
S, the data packets will continue being encapsulated to the RP. When S, the data packets will continue being encapsulated to the RP. When
packets from S also start to arrive natively at the the RP, the RP will packets from S also start to arrive natively at the the RP, the RP will
skipping to change at page 9, line 17 skipping to change at page 9, line 21
state, and then packets from S start to flow following the (S,G) tree state, and then packets from S start to flow following the (S,G) tree
state towards the RP. These data packets may also reach routers with state towards the RP. These data packets may also reach routers with
(*,G) state along the path towards the RP - if so, they can short-cut (*,G) state along the path towards the RP - if so, they can short-cut
onto the RP tree at this point. 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 for
S, the data packets will continue being encapsulated to the RP. When S, the data packets will continue being encapsulated to the RP. When
packets from S also start to arrive natively at the the RP, the RP will packets from S also start to arrive natively at the the RP, the RP will
be receiving two copies of each of these packets. At this point, the RP be receiving two copies of each of these packets. At this point, the RP
starts to discard the encapsulated copy of these packets, and it sends a starts to discard the encapsulated copy of these packets, and it sends a
Register-Stop message back to S's DR to prevent the DR unnecessarily RegisterStop message back to S's DR to prevent the DR unnecessarily
encapsulating the packets. 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 a
source-specific tree to the RP, and from there along the shared tree to source-specific tree to the RP, and from there along the shared tree to
the receivers. Where the two trees intersect, traffic may transfer from the receivers. Where the two trees intersect, traffic may transfer from
the source-specific tree to the RP tree, and so avoid taking a long the source-specific tree to the RP tree, and so avoid taking a long
detour via the RP. detour via the RP.
It should be noted that a sender may start sending before or after a It should be noted that a sender may start sending before or after a
receiver joins the group, and thus phase two may happen before the receiver joins the group, and thus phase two may happen before the
shared tree to the receiver is built. shared tree to the receiver is built.
Phase 3: Shortest-Path Tree Phase 3: 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 forwarding
paths. For many receivers the route via the RP may involve a paths. For many receivers the route via the RP may involve a
significant detour when compared with the shortest path from the source significant detour when compared with the shortest path from the source
to the receiver. to the receiver.
To obtain lower latencies, a router on the sender's LAN, typically the | To obtain lower latencies, a router on the receiver's LAN, typically the
DR, may optionally initiate a transfer from the shared tree to a source- | DR, may optionally initiate a transfer from the shared tree to a source-
specific shortest-path tree (SPT). To do this, it issues an (S,G) Join specific shortest-path tree (SPT). To do this, it issues an (S,G) Join
towards S. This instantiates state in the routers along the path to S. towards S. This instantiates state in the routers along the path to S.
Eventually this join either reaches S's subnet, or reaches a router that Eventually this join either reaches S's subnet, or reaches a router that
already has (S,G) state. When this happens, data packets from S start already has (S,G) state. When this happens, data packets from S start
to flow following the (S,G) state until they reach the receiver. 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) will
be receiving two copies of the data - one from the SPT and one from the be receiving two copies of the data - one from the SPT and one from the
RPT. When the first traffic starts to arrive from the SPT, the DR or RPT. When the first traffic starts to arrive from the SPT, the DR or
upstream router starts to drop the packets for G from S that arrive via upstream router starts to drop the packets for G from S that arrive via
the RP tree. In addition, it sends an (S,G) prune message towards the the RP tree. In addition, it sends an (S,G) Prune message towards the
RP. This is known as an (S,G,rpt) Prune. The prune message travels RP. This is known as an (S,G,rpt) Prune. The Prune message travels
hop-by-hop, instantiating state along the path towards the RP indicating hop-by-hop, instantiating state along the path towards the RP indicating
that traffic from S for G should NOT be forwarded in this direction. that traffic from S for G should NOT be forwarded in this direction.
The prune is propagated until it reaches the RP or a router that still The prune is propagated until it reaches the RP or a router that still
needs the traffic from S for other receivers. 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 is
receiving the traffic from S, but this traffic is no longer reaching the receiving the traffic from S, but this traffic is no longer reaching the
receiver along the RP tree. As far as the receiver is concerned, this receiver along the RP tree. As far as the receiver is concerned, this
is the final distribution tree. is the final distribution tree.
skipping to change at page 10, line 29 skipping to change at page 10, line 33
to receive traffic for a group if that traffic comes from a particular to receive traffic for a group if that traffic comes from a particular
source. If a receiver does this, and no other receiver on the LAN source. If a receiver does this, and no other receiver on the LAN
requires all the traffic for the group, then the DR may omit performing requires all the traffic for the group, then the DR may omit performing
a (*,G) join to set up the shared tree, and instead issue a source- a (*,G) join to set up the shared tree, and instead issue a source-
specific (S,G) join only. 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 groups
in this range, receivers should only issue source-specific IGMPv3 joins. in this range, receivers should only issue source-specific IGMPv3 joins.
If a PIM router receives a non-source-specific join for a group in this If a PIM router receives a non-source-specific join for a group in this
range, it should ignore it, as described in Section 4.8. range, it should ignore it, as described in Section 4.9.
Source-specific Prunes 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 specify that it only
wants to receive traffic for a group if that traffic does not come from wants to receive traffic for a group if that traffic does not come from
a specific source or sources. In this case, the DR will perform a (*,G) a specific source or sources. In this case, the DR will perform a (*,G)
join as normal, but may combine this with an (S,G,rpt) prune for each of join as normal, but may combine this with an (S,G,rpt) prune for each of
the sources the receiver does not wish to receive. the sources the receiver does not wish to receive.
Multi-access Transit LANs Multi-access Transit LANs
skipping to change at page 11, line 30 skipping to change at page 11, line 33
prevent such duplicate joins from occurring - instead when duplicate prevent such duplicate joins from occurring - instead when duplicate
data packets appear on the LAN from different routers, these routers data packets appear on the LAN from different routers, these routers
notice this, and then elect a single forwarder. This election is notice this, and then elect a single forwarder. This election is
performed using PIM Assert messages, which resolve the problem in favor performed using PIM Assert messages, which resolve the problem in favor
of the upstream router which has (S,G) state, or if neither or both of the upstream router which has (S,G) state, or if neither or both
router has (S,G) state, then in favor of the router with the best metric router has (S,G) state, then in favor of the router with the best metric
to the RP for RP trees, or the best metric to the source to source- to the RP for RP trees, or the best metric to the source to source-
specific trees. 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 the
LAN, and these cause subsequent join messages to be sent to the upstream LAN, and these cause subsequent Join messages to be sent to the upstream
router that won the Assert. router that won the Assert.
RP Discovery 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 through a which they have (*,G) state. This address is obtained either through a
bootstrap mechanism or through static configuration. bootstrap mechanism or through static 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 [4]. One router in each PIM domain is elected the Bootstrap mechanism [7]. One router in each PIM domain is elected the Bootstrap
Router through a simple election process. All the routers in the domain Router through a simple election process. All the routers in the domain
that are configured to be candidates to be RPs periodically unicast that are configured to be candidates to be RPs periodically unicast
their candidacy to the BSR. From the candidates, the BSR picks an RP- their candidacy to the BSR. From the candidates, the BSR picks an RP-
set, and periodically announces this set in a bootstrap message. set, and periodically announces this set in a Bootstrap message.
Bootstrap messages are flooded hop-by-hop throughout the domain until Bootstrap messages are flooded hop-by-hop throughout the domain until
all routers in the domain know the RP-Set. 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 RP-
set using an order-preserving hash function (one that minimizes changes set using an order-preserving hash function (one that minimizes changes
if the RP set changes). The resulting RP is the one that it uses as the if the RP set changes). The resulting RP is the one that it uses as the
RP for that group. RP for that group.
4. Protocol Specification 4. Protocol Specification
skipping to change at page 12, line 23 skipping to change at page 12, line 28
o Section 4.3 specifies the PIM Register generation and processing o Section 4.3 specifies the PIM Register generation and processing
rules. rules.
o Section 4.4 specifies the PIM Join/Prune generation and processing o Section 4.4 specifies the PIM Join/Prune generation and processing
rules. rules.
o Section 4.5 specifies the PIM Assert generation and processing rules. o Section 4.5 specifies the PIM Assert generation and processing rules.
o Designated Router (DR) election is specified in Section 4.6. o Designated Router (DR) election is specified in Section 4.6.
o Section 4.7 specifies the RP discovery mechanisms. o Section 4.8 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, PIM-
SSM, is described in Section 4.8. SSM, is described in Section 4.9.
o PIM packet formats are specified in Section 4.9. o PIM packet formats are specified in Section 4.10.
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.11.
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 implementation
should maintain in order to function correctly. We term this state the should maintain in order to function correctly. We term this state the
Tree Information Base or TIB, as it holds the state of all the multicast Tree Information Base or TIB, as it holds the state of all the multicast
distribution trees at this router. In this specification we define PIM distribution trees at this router. In this specification we define PIM
mechanisms in terms of the TIB. However, only a very simple mechanisms in terms of the TIB. However, only a very simple
implementation would actually implement packet forwarding operations in implementation would actually implement packet forwarding operations in
terms of this state. Most implementations will use this state to build terms of this state. Most implementations will use this state to build
skipping to change at page 14, line 4 skipping to change at page 14, line 10
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 Gen ID. o Neighbor's Gen ID.
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 Override Interval, the Propagation Delay and the Interface | The Override Interval, the Propagation Delay and the Interface
suppression state are described in section 4.6.3. Designated Router | suppression state are described in section 4.6.3. Designated Router
state is described in section 4.6. state is described in section 4.6.
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:
skipping to change at page 15, line 44 skipping to change at page 15, line 51
Not interface specific: Not interface specific:
o Upstream Join/Prune Timer (JT) o Upstream Join/Prune Timer (JT)
o Last RP Used o Last RP Used
o Last RPF Neighbor towards RP that was used o Last RPF Neighbor towards RP that was used
Local membership is the result of the local membership mechanism (such Local membership is the result of the local membership mechanism (such
as IGMP) running on that interface. It need not be kept if this router as IGMP or MLD) running on that interface. It need not be kept if this
is not the DR on that interface unless this router won a (*,G) assert on router is not the DR on that interface unless this router won a (*,G)
this interface for this group, although implementations may optionally
keep this state in case they become the DR or assert winner. This assert on this interface for this group, although implementations may
information is used by the pim_include(*,G) macro described in section optionally keep this state in case they become the DR or assert winner.
4.1.6. 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) PIM (*,G) Join/Prune state is the result of receiving PIM (*,G)
Join/Prune messages on this interface, and is specified in section Join/Prune messages on this interface, and is specified in section
4.4.2. The state is used by the macros that calculate the outgoing 4.4.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 interface list in section 4.1.6, and in the JoinDesired(*,G) macro
(defined in section 4.4.6) that is used in deciding whether a Join(*,G) (defined in section 4.4.6) that is used in deciding whether a Join(*,G)
should be sent upstream. should be sent upstream.
(*,G) Assert Winner state is the result of sending or receiving (*,G) (*,G) Assert Winner state is the result of sending or receiving (*,G)
assert messages on this interface. It is specified in section 4.5.2. Assert messages on this interface. It is specified in section 4.5.2.
The upstream (*,G) Join/Prune timer is used to send out periodic The upstream (*,G) Join/Prune timer is used to send out periodic
Join(*,G) messages, and to override Prune(*,G) messages from peers on an Join(*,G) messages, and to override Prune(*,G) messages from peers on an
upstream LAN interface. upstream LAN interface.
The last RP used must be stored because if the RP Set changes (section The last RP used must be stored because if the RP Set changes (section
4.7) then state must be torn down and rebuilt for groups whose RP 4.8) then state must be torn down and rebuilt for groups whose RP
changes. changes.
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 so,
then we need to trigger a new Join(*,G) to the new upstream neighbor and then we need to trigger a new Join(*,G) to the new upstream neighbor and
a Prune(*,G) to the old upstream neighbor. Similarly, if a router a Prune(*,G) to the old upstream neighbor. Similarly, if a router
detects through a changed GenID in a Hello message that the upstream detects through a changed GenID in a Hello message that the upstream
neighbor towards the RP has rebooted, then it should re-instantiate neighbor towards the RP has rebooted, then it should re-instantiate
state by sending a Join(*,G). These mechanisms are specified in Section state by sending a Join(*,G). These mechanisms are specified in Section
4.4.6. 4.4.6.
skipping to change at page 17, line 29 skipping to change at page 17, line 39
o SPT bit (indicates (S,G) state is active) o SPT bit (indicates (S,G) state is active)
o (S,G) KeepAlive Timer (KAT) o (S,G) KeepAlive Timer (KAT)
Local membership is the result of the local source-specific membership Local membership is the result of the local source-specific membership
mechanism (such as IGMP version 3) running on that interface and mechanism (such as IGMP version 3) running on that interface and
specifying that this particular source should be included. As stored specifying that this particular source should be included. As stored
here, this state is the resulting state after any IGMPv3 inconsistencies here, this state is the resulting state after any IGMPv3 inconsistencies
have been resolved. It need not be kept if this router is not the DR on have been resolved. It need not be kept if this router is not the DR on
that interface unless this router won a (S,G) assert on this interface that interface unless this router won a (S,G) assert on this interface
for this group. This information is used by the pim_include(S,G) macro for this group. However, we recommend storing this information if
described in section 4.1.6. 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(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.4.2. The state is used by the macros that calculate the outgoing 4.4.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.4.7) that is used in deciding whether a Join(S,G) (defined in section 4.4.7) that is used in deciding whether a Join(S,G)
should be sent upstream. 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.5.1. Assert messages on this interface. It is specified in section 4.5.1.
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 an
upstream LAN interface. 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 changes
then the RPF neighbor towards S may change. If it does so, then we need then the RPF neighbor towards S may change. If it does so, then we need
to trigger a new Join(S,G) to the new upstream neighbor and a Prune(S,G) to trigger a new Join(S,G) to the new upstream neighbor and a Prune(S,G)
to the old upstream neighbor. Similarly, if the router detects through to the old upstream neighbor. Similarly, if the router detects through
a changed GenID in a Hello message that the upstream neighbor towards S a changed GenID in a Hello message that the upstream neighbor towards S
skipping to change at page 19, line 4 skipping to change at page 19, line 15
Upstream (S,G,rpt) Join/Prune State: Upstream (S,G,rpt) Join/Prune State:
o State: One of {"NotJoined(*,G)", o State: One of {"NotJoined(*,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 membership
mechanism (such as IGMPv3) running on that interface and specifying that mechanism (such as IGMPv3) running on that interface and specifying that
although there is (*,G) Include state, this particular source should be although there is (*,G) Include state, this particular source should be
excluded. As stored here, this state is the resulting state after any excluded. As stored here, this state is the resulting state after any
IGMPv3 inconsistencies between LAN members have been resolved. It need IGMPv3 inconsistencies between LAN members have been resolved. It need
not be kept if this router is not the DR on that interface unless this 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. This router won a (*,G) assert on this interface for this group. However, we
information is used by the pim_exclude(S,G) macro described in section recommend storing this information if possible, as it reduces latency
4.1.6. converging to stable operating conditions after a failure causing a
change of DR. This 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 (S,G,rpt)
Join/Prune messages on this interface, and is specified in section Join/Prune messages on this interface, and is specified in section
4.4.4. The state is used by the macros that calculate the outgoing 4.4.4. The state is used by the macros that calculate the outgoing
interface list in section 4.1.6, and in the rules for adding 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.4.8. 4.4.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 Override
Timer to send the correct override messages in response to Join/Prune Timer to send the correct override messages in response to Join/Prune
skipping to change at page 20, line 44 skipping to change at page 21, line 9
( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE )
OR AssertWinner(S,G,I) == me ) OR AssertWinner(S,G,I) == me )
AND local_receiver_include(S,G,I) } AND local_receiver_include(S,G,I) }
pim_exclude(S,G) = pim_exclude(S,G) =
{ all interfaces I such that: { all interfaces I such that:
( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE )
OR AssertWinner(S,G,I) == me ) OR AssertWinner(S,G,I) == me )
AND local_receiver_exclude(S,G,I) } AND local_receiver_exclude(S,G,I) }
The clause "local_receiver_include(S,G,I)" is true if the IGMP module or The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD
other local membership mechanism has determined that there are local module or other local membership mechanism has determined that there are
members on interface I that desire to receive traffic sent specifically local members on interface I that desire to receive traffic sent
by S to G. "local_receiver_include(*,G,I)" is true if the IGMP module specifically by S to G. "local_receiver_include(*,G,I)" is true if the
or other local membership mechanism has determined that there are local IGMP/MLD module or other local membership mechanism has determined that
members on interface I that desire to receive all traffic sent to G. there are local members on interface I that desire to receive all
"local_receiver_exclude(S,G,I) is true if local_receiver_include(*,G,I) traffic sent to G. "local_receiver_exclude(S,G,I) is true if
local_receiver_include(*,G,I) is true but none of the local members
is true but none of the local members desire to receive traffic from S. desire to receive traffic from S.
The set "joins(*,*,RP)" is the set of all interfaces on which the router The set "joins(*,*,RP)" is the set of all interfaces on which the router
has received (*,*,RP) Joins: has received (*,*,RP) Joins:
joins(*,*,RP) = joins(*,*,RP) =
{ all interfaces I such that { all interfaces I such that
DownstreamJPState(*,*,RP,I) is either Joined or DownstreamJPState(*,*,RP,I) is either Join or
PrunePending } PrunePending }
DownstreamJPState(*,*,RP,I) is the state of the finite state machine in DownstreamJPState(*,*,RP,I) is the state of the finite state machine in
section 4.4.1. section 4.4.1.
The set "joins(*,G)" is the set of all interfaces on which the router The set "joins(*,G)" is the set of all interfaces on which the router
has received (*,G) Joins: has received (*,G) Joins:
joins(*,G) = joins(*,G) =
{ all interfaces I such that { all interfaces I such that
DownstreamJPState(*,G,I) is either Joined or PrunePending } DownstreamJPState(*,G,I) is either Join or PrunePending }
DownstreamJPState(*,G,I) is the state of the finite state machine in DownstreamJPState(*,G,I) is the state of the finite state machine in
section 4.4.2. section 4.4.2.
The set "joins(S,G)" is the set of all interfaces on which the router The set "joins(S,G)" is the set of all interfaces on which the router
has received (S,G) Joins: has received (S,G) Joins:
joins(S,G) = joins(S,G) =
{ all interfaces I such that { all interfaces I such that
DownstreamJPState(S,G,I) is either Joined or PrunePending } DownstreamJPState(S,G,I) is either Join or PrunePending }
DownstreamJPState(S,G,I) is the state of the finite state machine in DownstreamJPState(S,G,I) is the state of the finite state machine in
section 4.4.3. section 4.4.3.
The set "prunes(S,G,rpt)" is the set of all interfaces on which the The set "prunes(S,G,rpt)" is the set of all interfaces on which the
router has received (*,G) joins and (S,G,rpt) prunes. router has received (*,G) joins and (S,G,rpt) prunes.
prunes(S,G,rpt) = prunes(S,G,rpt) =
{ all interfaces I such that | { all interfaces I such that
DownstreamJPState(S,G,rpt,I) is Pruned or PruneTmp } | DownstreamJPState(S,G,rpt,I) is Prune or PruneTmp }
DownstreamJPState(S,G,rpt,I) is the state of the finite state machine in DownstreamJPState(S,G,rpt,I) is the state of the finite state machine in
section 4.4.4. section 4.4.4.
The set "lost_assert(*,G)" is the set of all interfaces on which the The set "lost_assert(*,G)" is the set of all interfaces on which the
router has received (*,G) joins but has lost a (*,G) assert. The macro router has received (*,G) joins but has lost a (*,G) assert. The macro
lost_assert(*,G,I) is defined in Section 4.5.5. lost_assert(*,G,I) is defined in Section 4.5.5.
lost_assert(*,G) = lost_assert(*,G) =
{ all interfaces I such that { all interfaces I such that
skipping to change at page 23, line 4 skipping to change at page 23, line 20
} }
} }
neighbor RPF'(S,G,rpt) { neighbor RPF'(S,G,rpt) {
if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) { if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) {
return AssertWinner(S, G, RPF_interface(RP(G)) ) return AssertWinner(S, G, RPF_interface(RP(G)) )
} else { } else {
return RPF'(*,G) return RPF'(*,G)
} }
} }
neighbor RPF'(S,G) { neighbor RPF'(S,G) {
if ( I_Am_Assert_loser(S, G, RPF_interface(S) )) { if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) {
return AssertWinner(S, G, RPF_interface(S) ) return AssertWinner(S, G, RPF_interface(S) )
} else { } else {
return MRIB.next_hop( S ) return 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.
skipping to change at page 23, line 28 skipping to change at page 23, line 45
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 only
have active (*,G) Join state, we need to accept packets from 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.4.8). messages that we send to RPF'(*,G) (See Section 4.4.8).
The function MRIB.next_hop( S ) returns the next-hop PIM neighbor toward The function MRIB.next_hop( S ) returns the next-hop PIM neighbor toward
the host S, as indicated by the current MRIB. If S is directly the host S, as indicated by the current MRIB. If S is directly
adjacent, then MRIB.next_hop( S ) returns NULL. At the RP for G, adjacent, then MRIB.next_hop( S ) returns NULL. At the RP for G,
MRIB.next_hop( RP(G )) returns NULL. MRIB.next_hop( RP(G )) returns NULL.
I_Am_Assert_loser(S, G, I) is true if the Assert start machine (in I_Am_Assert_Loser(S, G, I) is true if the Assert start machine (in
section 4.5.1) for (S,G) on Interface I is in "I am Assert Loser" state. section 4.5.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 start machine (in I_Am_Assert_Loser(*, G, I) is true if the Assert start machine (in
section 4.5.2) for (*,G) on Interface I is in "I am Assert Loser" state. section 4.5.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.
skipping to change at page 24, line 13 skipping to change at page 24, line 31
directly connected subnet. directly connected subnet.
Second, we check to see if the SPT bit should be set because we've now Second, we check to see if the SPT bit 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 TIB
state and the interface that the packet arrived on. 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, then
we refresh the (S,G) state keepalive timer. 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 we
just build an outgoing interface list for the packet. We also check if | just build an outgoing interface list for the packet. We also check if
we should initiate a switch to start receiving this source on a shortest | we should initiate a switch to start receiving this source on a shortest
path tree. | 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 not
empty, we forward the packet out of those interfaces. empty, we forward the packet out of those interfaces.
On receipt on a data from S to G on interface iif: On receipt on a data from S to G on interface iif:
if( DirectlyConnected(S) == TRUE ) { if( DirectlyConnected(S) == TRUE ) {
set KeepaliveTimer(S,G) to Keepalive_Period set KeepaliveTimer(S,G) to Keepalive_Period
# Note: register state transition may happen as a result # Note: register state transition may happen as a result
# of restarting KeepaliveTimer, and must be dealt with here. # of restarting KeepaliveTimer, and must be dealt with here.
} }
Update_SPTbit(S,G,iif) Update_SPTbit(S,G,iif)
oiflist = NULL | oiflist = NULL
if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { | if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) {
oiflist = inherited_olist(S,G) | oiflist = inherited_olist(S,G)
if( oiflist != NULL ) { | if( oiflist != NULL ) {
restart KeepaliveTimer(S,G) | restart KeepaliveTimer(S,G)
} | }
} else if( iif == RPF_interface(RP) AND SPTbit(S,G) == FALSE) { | } else if( iif == RPF_interface(RP) 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
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:
directly_connected(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 Section
4.1. 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.
skipping to change at page 26, line 12 skipping to change at page 26, line 12
on (*,*,RP) or (*,G) state taking into account (S,G,rpt) prune state, on (*,*,RP) or (*,G) state taking into account (S,G,rpt) prune state,
and asserts, etc. and 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 section
4.4.7. 4.4.7.
Keepalive_Period is defined in Section 4.10. Keepalive_Period is defined in Section 4.11.
Data triggered PIM-Assert messages sent from the above forwarding code Data triggered PIM-Assert messages sent from the above forwarding code
should be rate-limited in a implementation-dependent manner. 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 rotuer 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) ) {
restart KeepAliveTimer(S,G); | restart KeepAliveTimer(S,G);
} | }
} | }
SwitchToSptDesired(S,G) is a policy function that is implementation | SwitchToSptDesired(S,G) is a policy function that is implementation
defined. An "infinite threshhold" policy can be implemented making | defined. An "infinite threshhold" policy can be implemented making
SwitchToSptDesired(S,G) return false all the time. A "switch on first | SwitchToSptDesired(S,G) return false all the time. A "switch on first
packet" policy can be implemented by making SwitchToSptDesired(S,G) | packet" policy can be implemented by making SwitchToSptDesired(S,G)
return true once a single packet has been received for the source and | return true once a single packet has been received for the source and
group. | group.
4.2.2. Setting and Clearing the (S,G) SPT bit 4.2.2. Setting and Clearing the (S,G) SPT bit
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 due
to upstream (*,*,RP)/(*,G) state while upstream (S,G) state is being to upstream (*,*,RP)/(*,G) state while upstream (S,G) state is being
established during which time a router should continue to forward only established during which time a router should continue to forward only
on (*,*,RP)/(*,G) state. This prevents temporary black-holes that would on (*,*,RP)/(*,G) state. This prevents temporary black-holes that would
be caused by sending a Prune(S,G,rpt) before the upstream (S,G) state be caused by sending a Prune(S,G,rpt) before the upstream (S,G) state
has finished being established. 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
skipping to change at page 27, line 24 skipping to change at page 27, line 23
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) OR RPF_interface(S) != RPF_interface(RP)
OR inherited_olist(S,G,rpt) == NULL OR inherited_olist(S,G,rpt) == NULL
OR RPF'(S,G) == RPF'(*,G) ) ) { OR RPF'(S,G) == RPF'(*,G) ) ) {
Set SPTbit(S,G) to TRUE Set SPTbit(S,G) to TRUE
} }
} }
Additionally a router sets SPTbit(S,G) to TRUE when it receives an | Additionally a router sets SPTbit(S,G) to TRUE when it receives an
Assert(S,G) on RPF_interface(S). | Assert(S,G) on RPF_interface(S).
JoinDesired(S,G) is defined in Section 4.4.7, and indicates whether we JoinDesired(S,G) is defined in Section 4.4.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 SPT bit if we have the appropriate Basically Update_SPTbit will set the SPT bit if we have the appropriate
(S,G) join state and the packet arrived on the correct upstream (S,G) join state and the packet arrived on the correct upstream
interface for S, and one or more of the following conditions applies: interface for S, and 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
skipping to change at page 28, line 21 skipping to change at page 28, line 19
Overview Overview
The Designated Router (DR) on a LAN or point-to-point link encapsulates The Designated Router (DR) on a LAN or point-to-point link encapsulates
multicast packets from local sources to the RP for the relevant group multicast packets from local sources to the RP for the relevant group
unless it recently received a Register Stop message for that (S,G) or unless it recently received a Register Stop message for that (S,G) or
(*,G) from the RP. When the DR receives a Register Stop message from (*,G) from the RP. When the DR receives a Register Stop message from
the RP, it starts a Register Stop timer to maintain this state. Just the RP, it starts a Register Stop timer to maintain this state. Just
before the Register Stop timer expires, the DR sends a Null-Register before the Register Stop timer expires, the DR sends a Null-Register
Message to the RP to allow the RP to refresh the Register Stop Message to the RP to allow the RP to refresh the Register Stop
information at the DR. If the Register Stop timer actually expires, the | information at the DR. If the Register Stop timer actually expires, the
DR will resume encapsulating packets from the source to the RP. | DR will resume encapsulating packets from the source to the RP.
4.3.1. Sending Register Messages from the DR 4.3.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 of
specification, we represent the mechanism to encapsulate packets to the specification, we represent the mechanism to encapsulate packets to the
RP as a Register-Tunnel interface, which is added to or removed from the RP as a Register-Tunnel interface, which is added to or removed from the
(S,G) olist. The tunnel interface then takes part in the normal packet (S,G) olist. The tunnel interface then takes part in the normal packet
forwarding rules specified in Section 4.2. forwarding rules is 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 DR's
per-(S,G) Register state-machine: 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, but
the DR acts as if the RP has joined the DR on the tunnel the DR acts as if the RP has joined the DR on the tunnel
interface). interface).
skipping to change at page 29, line 15 skipping to change at page 29, line 14
In addition, a RegisterStop timer (RST) is kept if the state machine in In addition, a RegisterStop timer (RST) is kept if the state machine in
not in the No Info state. not in the No Info state.
+-----------------------------------+ +-----------------------------------+
| Figures omitted from text version | | Figures omitted from text version |
+-----------------------------------+ +-----------------------------------+
Figure 1: Per-(S,G) register state-machine at a DR Figure 1: Per-(S,G) register state-machine at a DR
In tabular form, the state-machine is: | In tabular form, the state-machine is:
+---------------------++-------------------------------------------------|---------------------------------------| +-----------++------------------------------------------------------------------------------------------+
| || Event || | | || Event |
| ++----------------+--------------+-----------------|------------------|--------------------| | ++------------------+------------------+----------------------+--------------+--------------+
|Prev State | ||Register- | | Could- | | Could- | | Register- || | RP changed || | |Prev State ||Register-Stop |Could-Register | Could-Register |Register- |RP changed |
| ||Stop Timer | | Register | | Register | | Stop || | | | ||Timer expires |->True | ->False |Stop | |
| ||expires | | ->True | | ->False | | received || | | | || | | |received | |
+---------------------++----------------+--------------+-----------------+------------------+--------------------| +-----------++------------------+------------------+----------------------+--------------+--------------+
|No Info (NI) | ||- | -> J state | - | - | -| | |No Info ||- |-> J state | - |- |- |
| || | add tunnel | | | | |(NI) || |add reg tunnel | | | |
+---------------------++----------------+--------------+-----------------+------------------+--------------------| +-----------++------------------+------------------+----------------------+--------------+--------------+
| ||- | - | -> NI state | -> P state | -> J state| | | ||- |- | -> NI state |-> P state |-> J state |
| || | | remove tunnel | remove || | redirect || | | || | | remove reg tunnel |remove |update reg |
|Join (J) | || | | | tunnel; set || | tunnel to || | | || | | |tunnel; |tunnel |
| || | | | Register- || | new RP || | |Join (J) || | | |set | |
| || | | | Stop || | | | || | | |Register- | |
| || | | | timer(*) || | | | || | | |Stop | |
+---------------------++----------------+--------------+-----------------+------------------+--------------------| | || | | |timer(*) | |
| ||-> J state | - | -> NI state | -> P state | -> J state| | +-----------++------------------+------------------+----------------------+--------------+--------------+
| ||add tunnel | | remove tunnel | set Register- ||| redirect || | | ||-> J state |- | -> NI state |-> P state |-> J state |
|Join Pending | || | | | Stop timer(*) ||| tunnel to new || | |Join ||add reg tunnel | | remove reg tunnel |set |add reg |
|(JP) | || | | | | RP; cancel || | |Pending || | | |Register- |tunnel; |
| || | | | | Register-Stop || | |(JP) || | | |Stop |cancel |
| || | | | | timer || | | || | | |timer(*) |Register- |
+---------------------++----------------+--------------+-----------------+------------------+--------------------| | || | | | |Stop timer |
| ||-> JP state | - | -> NI state | - | -> J state| | +-----------++------------------+------------------+----------------------+--------------+--------------+
| ||set Register- | | | remove tunnel | | redirect tunnel ||| | ||-> JP state |- | -> NI state |- |-> J state |
|Prune (P) | ||Stop | | | | | to new RP; ||| | ||set Register- | | remove reg tunnel | |add reg |
| ||timer(**); | | | | | cancel Register- ||| |Prune (P) ||Stop | | | |tunnel; |
| ||send null | | | | | Stop timer ||| | ||timer(**); | | | |cancel |
| ||register | | | | | | | ||send null | | | |Register- |
+---------------------++----------------+--------------+-----------------+------------------+--------------------| | ||register | | | |Stop timer |
+-----------++------------------+------------------+----------------------+--------------+--------------+
Notes: Notes:
(*) The RegisterStopTimer is set to a random value chosen uniformly from (*) The RegisterStopTimer is set to a random value chosen uniformly from
the interval ( 0.5 * Register_Suppression_Time, 1.5 * the interval ( 0.5 * Register_Suppression_Time, 1.5 *
Register_Suppression_Time) minus Register_Probe_Time; Register_Suppression_Time) minus Register_Probe_Time;
Subtracting off register_probe_time is a bit unnecessary because it is Subtracting off Register_Probe_Time is a bit unnecessary because it
really small compared to register suppression timeout, but was in the is really small compared to Register_Suppression_Time, but was in
old spec and is kept for compatibility. the old spec and is kept for compatibility.
(**) The RegisterStopTimer is set to register_probe_time. (**) The RegisterStopTimer is set to Register_Probe_Time.
The following actions are defined:
Add Register Tunnel
A Register-Tunnel virtual interface, VI, is created (if it doesn't
already exist) with its encapsulation target being RP(G).
DownstreamJPState(S,G,VI) is set to Join state, causing the tunnel
interface to be added to immediate_olist(S,G).
Remove Register Tunnel
VI is the Register-Tunnel virtual interface with encapsulation target of
RP(G). DownstreamJPState(S,G,VI) is set to NoInfo state, causing the
tunnel interface to be removed from immediate_olist(S,G). If
DownstreamJPState(S,G,VI) is NoInfo for all (S,G), then VI can be
deleted.
Update Register Tunnel
This action occurs when RP(G) changes.
VI_old is the Register-Tunnel virtual interface with encapsulation
target old_RP(G). A Register-Tunnel virtual interface, VI_new, is
created (if it doesn't already exist) with its encapsulation target
being new_RP(G). DownstreamJPState(S,G,VI_old) is set to NoInfo state
and DownstreamJPState(S,G,VI_new) is set to Join state. If
DownstreamJPState(S,G,VI_old) is NoInfo for all (S,G), then VI_old can
be deleted.
Note that we can not simply change the encapsulation target of VI_old
because not all groups using that encapsulation tunnel will have moved
to the same new RP.
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 connected
source, KeepaliveTimer(S,G) needs to be set by the packet forwarding source, KeepaliveTimer(S,G) needs to be set by the packet forwarding
rules before computing CouldRegister(S,G) in the register state machine, rules before computing CouldRegister(S,G) in the register state machine,
or the first packet from a source won't be registered. 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 MTU
than the underlying IP interface towards the RP. IP fragmentation on than the underlying IP interface towards the RP. IP fragmentation on
packets forwarded on the Register Tunnel is performed based upon this packets forwarded on the Register Tunnel is performed based upon this
smaller MTU. The encapsulating DR may perform Path-MTU Discovery to the smaller MTU. The encapsulating DR may perform Path-MTU Discovery to the
RP to determine the effective MTU of the tunnel. This smaller MTU takes | RP to determine the effective MTU of the tunnel. This smaller MTU takes
both the outer IP header and the PIM register header overhead into | both the outer IP header and the PIM register header overhead into
account. If a multicast packet is fragmented on the way into the | account. If a multicast packet is fragmented on the way into the
Register Tunnel, each fragment is encapsulated individually so contains | Register Tunnel, each fragment is encapsulated individually so contains
IP, PIM, and inner IP headers. | IP, PIM, and inner IP headers.
In IPv6, an ICMP Fragmentation Required message may be sent by the In IPv6, an ICMP Fragmentation Required message may be sent by the
encapsulating DR. encapsulating DR.
Just like any forwarded packet, the TTL of the original data packet is Just like any forwarded packet, the TTL of the original data packet is
decremented before it is encapsulated in the Register Tunnel. | decremented before it is encapsulated in the Register Tunnel.
The IP ECN bits should be copied from the original packet to the IP |
header of the encapsulating packet. They SHOULD NOT be set |
independently by the encapsulating router. | The IP ECN bits should be copied from the original packet to the IP
header of the encapsulating packet. They SHOULD NOT be set
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 packet
to the IP header of the encapsulating packet. It MAY be set | to the IP header of the encapsulating packet. It MAY be set
independently by the encapsulating router, based upon static | independently by the encapsulating router, based upon static
configuration or traffic classification. See [11] for more discussion | configuration or traffic classification. See [2] for more discussion on
on setting the DSCP on tunnels. | setting the DSCP on tunnels.
Handling RegisterStop(*,G) Messages at the DR Handling RegisterStop(*,G) Messages at the DR
An old RP might send a RegisterStop message with the source address set An old RP might send a RegisterStop message with the source address set
to all-zeros. This was the normal course of action in RFC 2326 when the to all-zeros. This was the normal course of action in RFC 2326 when the
register message matched against (*,G) state at the RP, and was defined Register message matched against (*,G) state at the RP, and was defined
as meaning "stop encapsulating all sources for this group". However, as meaning "stop encapsulating all sources for this group". However,
the behavior of such a RegisterStop(*,G) is ambiguous or incorrect in the behavior of such a RegisterStop(*,G) is ambiguous or incorrect in
some circumstances. some circumstances.
We specify that an RP should not send RegisterStop(*,G) messages, but We specify that an RP should not send RegisterStop(*,G) messages, but
for compatibility, a DR should be able to accept one if it is received. for compatibility, a DR should be able to accept one if it is received.
A RegisterStop(*,G) should be treated as a RegisterStop(S,G) for all A RegisterStop(*,G) should be treated as a RegisterStop(S,G) for all
existing (S,G) Register state machines. A router should not apply a existing (S,G) Register state machines. A router should not apply a
RegisterStop(*,G) to sources that become active after the RegisterStop(*,G) to sources that become active after the
RegisterStop(*,G) was received. RegisterStop(*,G) was received.
skipping to change at page 33, line 9 skipping to change at page 33, line 22
interrupted (*,G) connectivity following an RP change. interrupted (*,G) connectivity following an RP change.
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. This may cause the upstream (S,G) state proper tunnel interface. This may cause the upstream (S,G) state
machine 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 RegisterStop 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 ).
Just like any forwarded packet, the TTL of the original data packet is Just like any forwarded packet, the TTL of the original data packet is
decremented after it is decapsulated from the Register Tunnel. | decremented after it is decapsulated from the Register Tunnel.
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 the
DSCP of the inner packet, or re-classify the packet and apply a | 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 [11]. | discussed in [2].
4.4. PIM Join/Prune Messages 4.4. 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 the
following state machines. When considering a Join/Prune message whose following state machines. When considering a Join/Prune message whose
PIM Destination field addresses this router, (*,*,RP) Joins and Prunes PIM Destination field addresses this router, (*,G) Joins and Prunes can
can affect the (*,*,RP) and (S,G,rpt) downstream state machines, (*,G) affect both the (*,G) and (S,G,rpt) downstream state machines, while
Joins and Prunes can affect both the (*,G) and (S,G,rpt) downstream (*,*,RP), (S,G) and (S,G,rpt) Joins and Prunes can only affect their
state machines, while (S,G) and (S,G,rpt) Joins and Prunes can only respective downstream state machines. When considering a Join/Prune
affect their respective downstream state machines. When considering a message whose PIM Destination field addresses another router, most Join
Join/Prune message whose PIM Destination field addresses another router, or Prune messages could affect each upstream state machine.
most Join or Prune messages could affect each upstream state machine.
4.4.1. Receiving (*,*,RP) Join/Prune Messages 4.4.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.
skipping to change at page 34, line 20 skipping to change at page 34, line 33
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 PrunePending state functions exactly forwarding purposes, the PrunePending 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 group. to NoInfo for this RP.
PrunePendingTimer (PPT) PrunePendingTimer (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 PrunePendingTimer causes the interface state to Expiry of the PrunePendingTimer causes the interface state to
revert to NoInfo for this group. revert to NoInfo for this RP.
+-----------------------------------+ +-----------------------------------+
| Figures omitted from text version | | Figures omitted from text version |
+-----------------------------------+ +-----------------------------------+
Figure 2: Downstream (*,*,RP) per-interface state-machine Figure 2: Downstream (*,*,RP) per-interface state-machine
In tabular form, the per-interface (*,*,RP) state-machine is: | In tabular form, the per-interface (*,*,RP) state-machine is:
+---------------------++-------------------------------------------------|--------------------------| +-------------++---------------------------------------------------------+
| || Event || | || Event |
| ++---------------------+------------------+--------|---------|----------------| | ++-------------+-------------+--------------+--------------+
|Prev State | ||Receive | | Receive | | Prune | || | Expiry Timer ||| |Prev State ||Receive | Receive | Prune | Expiry Timer |
| ||Join(*,*,RP) | | Prune(*,*,RP)| | Pending| || | Expires ||| | ||Join(*,*,RP) | Prune | Pending | Expires |
| || | | Timer || | | | || | (*,*,RP) | 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 Expiry | | start Prune | | | | | |Join (J) ||restart | start Prune | | |
| ||Timer | | Pending Timer | | | | | | ||Expiry Timer | Pending | | |
+---------------------++---------------------+------------------+------------------+----------------| | || | Timer | | |
| ||-> J state | -> PP state | -> NI state | -> NI state| | +-------------++-------------+-------------+--------------+--------------+
| ||restart Expiry | | | Send Prune- ||| | | ||-> J state | -> PP state | -> NI state | -> NI state |
|Prune Pending (PP) | ||Timer; cancel | | | Echo(*,*,RP) ||| | | ||restart | | Send Prune- | |
| ||Prune Pending | | | | | | |Prune ||Expiry | | Echo(*,*,RP) | |
| ||Timer | | | | | | |Pending (PP) ||Timer; | | | |
+---------------------++---------------------+------------------+------------------+----------------| | ||cancel Prune | | | |
| ||Pending | | | |
| ||Timer | | | |
+-------------++-------------+-------------+--------------+--------------+
The transition events "Receive Join(*,*,RP)" and "Receive Prune(*,*,RP)" The transition events "Receive Join(*,*,RP)" and "Receive Prune(*,*,RP)"
imply receiving a Join or Prune targeted to this router's address on the imply receiving a Join or Prune targeted to this router's address on the
received interface. If the destination address is not correct, these received interface. If the destination address is not correct, these
state transitions in this state machine must not occur, although seeing state transitions in this state machine must not occur, although seeing
such a packet may cause state transitions in other state machines. 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 address
should be the same as the source address it chose for the hello packet should be the same as the source address it chose for the Hello message
it sent over that interface. However on point-to-point links we also it sent over that interface. However on point-to-point links we also
recommend that PIM messages with a 0.0.0.0 destination address are also recommend that PIM messages with a destination address of all zeros is
accepted. 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 address on I. | Neighbor Address set to the router's 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 message. | Join/Prune message.
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
RP. In the case of (*,*,RP) state, so long as we have a route
to the RP, this will not cause a problem, and the 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 address on I. | Neighbor Address set to the router's 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 address on I. | Neighbor Address set to the router's address on I.
The (*,*,RP) downstream state machine on interface I The (*,*,RP) downstream state machine on interface I
transitions to the PrunePending state. The PrunePending timer transitions to the PrunePending state. The PrunePending timer
is started; it is set to the J/P_Override_Interval if the is 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; otherwise
it is set to zero causing it to expire immediately. 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 PrunePending State Transitions from PrunePending State
When in PrunePending state, the following events may trigger a When in PrunePending 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 address on I. | Neighbor Address set to the router's 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 PrunePending timer is transitions to the Join state. The PrunePending 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.
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.
skipping to change at page 37, line 32 skipping to change at page 37, line 37
PrunePending Timer Expires PrunePending Timer Expires
The PrunePending Timer for the (*,*,RP) downstream state The PrunePending Timer for the (*,*,RP) downstream state
machine on interface I expires. machine on interface I expires.
The (*,*,RP) downstream state machine on interface I The (*,*,RP) downstream state machine on interface I
transitions to the NoInfo state. A PruneEcho(*,*,RP) is sent transitions to the NoInfo state. A PruneEcho(*,*,RP) is sent
onto the subnet connected to interface I. onto the subnet connected to interface I.
The action "Send PruneEcho(*,*,RP)" is triggered when the The action "Send PruneEcho(*,*,RP)" is triggered when the
router stops forwarding on an interface as a result of a router stops forwarding on an interface as a result of a
prune. A PruneEcho(*,*,RP) is simply a Prune(*,*,RP) message | prune. A PruneEcho(*,*,RP) is simply a Prune(*,*,RP) message
sent by the upstream router on a LAN with its own address in | sent by the upstream router on a LAN with its own address in
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 a point-to- happen. A PruneEcho(*,*,RP) need not be sent on a point-to-
point interface. point interface.
4.4.2. Receiving (*,G) Join/Prune Messages 4.4.2. Receiving (*,G) Join/Prune Messages
When a router receives a Join(*,G) or Prune(*,G) it must first check to When a router receives a Join(*,G) or Prune(*,G) it must first check to
see whether the RP in the message matches RP(G) (the router's idea of see whether the RP in the message matches RP(G) (the router's idea of
skipping to change at page 39, line 5 skipping to change at page 39, line 5
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 PrunePendingTimer causes the interface state to revert of the PrunePendingTimer causes the interface state to revert
to NoInfo for this group. to NoInfo for this group.
+-----------------------------------+ +-----------------------------------+
| Figures omitted from text version | | Figures omitted from text version |
+-----------------------------------+ +-----------------------------------+
Figure 3: Downstream (*,G) per-interface state-machine Figure 3: Downstream (*,G) per-interface state-machine
In tabular form, the per-interface (*,G) state-machine is: | In tabular form, the per-interface (*,G) state-machine is:
+---------------------++-------------------------------------------------|--------------------------| +-------------++--------------------------------------------------------+
| || 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 Expiry | | start Prune | | | | | |Join (J) ||restart | start Prune | | |
| ||Timer | | Pending Timer | | | | | | ||Expiry Timer | Pending | | |
+---------------------++---------------------+------------------+------------------+----------------| | || | Timer | | |
| ||-> J state | -> PP state | -> NI state | -> NI state| | +-------------++-------------+-------------+-------------+--------------+
| ||restart Expiry | | | Send Prune- ||| | | ||-> J state | -> PP state | -> NI state | -> NI state |
|Prune Pending (PP) | ||Timer; cancel | | | Echo(*,G) ||| | | ||restart | | Send Prune- | |
| ||Prune Pending | | | | | | |Prune ||Expiry | | Echo(*,G) | |
| ||Timer | | | | | | |Pending (PP) ||Timer; | | | |
+---------------------++---------------------+------------------+------------------+----------------| | ||cancel Prune | | | |
| ||Pending | | | |
| ||Timer | | | |
+-------------++-------------+-------------+-------------+--------------+
The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" imply The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" imply
receiving a Join or Prune targeted to this router's address on the receiving a Join or Prune targeted to this router's address on the
received interface. If the destination address is not correct, these received interface. If the destination address is not correct, these
state transitions in this state machine must not occur, although seeing state transitions in this state machine must not occur, although seeing
such a packet may cause state transitions in other state machines. 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 address
should be the same as the source address it chose for the hello packet should be the same as the source address it chose for the Hello message
it sent over that interface. However on point-to-point links we also it sent over that interface. However on point-to-point links we also
recommend that PIM messages with a 0.0.0.0 destination address are also recommend that PIM messages with a destination address of all zeros are
accepted. 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 address on I. | Neighbor Address set to the router's 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 address on I. | Neighbor Address set to the router's 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 address on I. | Neighbor Address set to the router's address on I.
The (*,G) downstream state machine on interface I transitions The (*,G) downstream state machine on interface I transitions
to the PrunePending state. The PrunePending timer is started; to the PrunePending state. The PrunePending timer is started;
it is set to the J/P_Override_Interval if the router has more it is set to the J/P_Override_Interval(I) if the router has
than one neighbor on that interface; otherwise it is set to more than one neighbor on that interface; otherwise it is set
zero causing it to expire immediately. 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 PrunePending State Transitions from PrunePending State
When in PrunePending state, the following events may trigger a When in PrunePending 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 address on I. | Neighbor Address set to the router's 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 PrunePending timer is canceled to the Join state. The PrunePending 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.
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.
skipping to change at page 41, line 18 skipping to change at page 41, line 22
PrunePending Timer Expires PrunePending Timer Expires
The PrunePending Timer for the (*,G) downstream state machine The PrunePending Timer for the (*,G) downstream state machine
on interface I expires. on 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. A PruneEcho(*,G) is sent onto the subnet to the NoInfo state. A PruneEcho(*,G) is sent onto the subnet
connected to interface I. connected to interface I.
The action "Send PruneEcho(*,G)" is triggered when the router The action "Send PruneEcho(*,G)" is triggered when the router
stops forwarding on an interface as a result of a prune. A stops forwarding on an interface as a result of a prune. A
PruneEcho(*,G) is simply a Prune(*,G) message sent by the | PruneEcho(*,G) is simply a Prune(*,G) message sent by the
upstream router on a LAN with its own address in the Upstream | upstream router on a LAN with its own address in the Upstream
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 a point-to-point happen. A PruneEcho(*,G) need not be sent on a point-to-point
interface. interface.
4.4.3. Receiving (S,G) Join/Prune Messages 4.4.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 messages
is given below, and is almost identical to that for (*,G) messages. is given below, and is almost identical to that for (*,G) messages.
skipping to change at page 42, line 7 skipping to change at page 42, line 9
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 PrunePending state functions exactly forwarding purposes, the PrunePending state functions exactly
like the Join state. like the Join state.
In addition there are two timers: In addition there are two timers:
ExpiryTimer (ET) ExpiryTimer (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 ExpiryTimer causes the interface state to revert to of the ExpiryTimer causes this state machine to revert to
NoInfo for this group. NoInfo state.
PrunePendingTimer (PPT) PrunePendingTimer (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 PrunePendingTimer causes the interface state to revert of the PrunePendingTimer this state machine to revert to
to NoInfo for this group. NoInfo state.
+-----------------------------------+ +-----------------------------------+
| Figures omitted from text version | | Figures omitted from text version |
+-----------------------------------+ +-----------------------------------+
Figure 4: Downstream per-interface (S,G) state-machine Figure 4: Downstream per-interface (S,G) state-machine
In tabular form, the state machine is: | In tabular form, the state machine is:
+---------------------++-------------------------------------------------|--------------------------| +-------------++--------------------------------------------------------+
| || 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 Expiry | | start Prune | | | | | |Join (J) ||restart | start Prune | | |
| ||Timer | | Pending Timer | | | | | | ||Expiry Timer | Pending | | |
+---------------------++---------------------+------------------+------------------+----------------| | || | Timer | | |
| ||-> J state | -> PP state | -> NI state | -> NI state| | +-------------++-------------+-------------+-------------+--------------+
| ||restart Expiry | | | Send Prune- ||| | | ||-> J state | -> PP state | -> NI state | -> NI state |
|Prune Pending (PP) | ||Timer; cancel | | | Echo(S,G) ||| | | ||restart | | Send Prune- | |
| ||Prune Pending | | | | | | |Prune ||Expiry | | Echo(S,G) | |
| ||Timer | | | | | | |Pending (PP) ||Timer; | | | |
+---------------------++---------------------+------------------+------------------+----------------| | ||cancel Prune | | | |
| ||Pending | | | |
| ||Timer | | | |
+-------------++-------------+-------------+-------------+--------------+
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)" imply
receiving a Join or Prune targeted to this router's address on the receiving a Join or Prune targeted to this router's address on the
received interface. If the destination address is not correct, these received interface. If the destination address is not correct, these
state transitions in this state machine must not occur, although seeing state transitions in this state machine must not occur, although seeing
such a packet may cause state transitions in other state machines. 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 address
should be the same as the source address it chose for the hello packet should be the same as the source address it chose for the Hello message
it sent over that interface. However on point-to-point links we also it sent over that interface. However on point-to-point links we also
recommend that PIM messages with a 0.0.0.0 destination address are also recommend that PIM messages with a destination address of all zeros are
accepted. 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 address on I. | Neighbor Address set to the router's 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 address on I. | Neighbor Address set to the router's 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 address on I. | Neighbor Address set to the router's 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 PrunePending state. The PrunePending timer is started; to the PrunePending state. The PrunePending timer is started;
it is set to the J/P_Override_Interval if the router has more it is set to the J/P_Override_Interval(I) if the router has
than one neighbor on that interface; otherwise it is set to more than one neighbor on that interface; otherwise it is set
zero causing it to expire immediately. 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 PrunePending State Transitions from PrunePending State
When in PrunePending state, the following events may trigger a When in PrunePending 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 address on I. | Neighbor Address set to the router's 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 PrunePending timer is canceled to the Join state. The PrunePending 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.
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.
skipping to change at page 44, line 40 skipping to change at page 44, line 44
PrunePending Timer Expires PrunePending Timer Expires
The PrunePending Timer for the (S,G) downstream state machine The PrunePending Timer for the (S,G) downstream state machine
on interface I expires. on 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. A PruneEcho(S,G) is sent onto the subnet to the NoInfo state. A PruneEcho(S,G) is sent onto the subnet
connected to interface I. connected to interface I.
The action "Send PruneEcho(S,G)" is triggered when the router The action "Send PruneEcho(S,G)" is triggered when the router
stops forwarding on an interface as a result of a prune. A stops forwarding on an interface as a result of a prune. A
PruneEcho(S,G) is simply a Prune(S,G) message sent by the | PruneEcho(S,G) is simply a Prune(S,G) message sent by the
upstream router on a LAN with its own address in the Upstream | upstream router on a LAN with its own address in the Upstream
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 a point-to-point happen. A PruneEcho(S,G) need not be sent on a point-to-point
interface. interface.
4.4.4. Receiving (S,G,rpt) Join/Prune Messages 4.4.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:
skipping to change at page 47, line 7 skipping to change at page 47, line 7
move on to Prune state. move on to Prune state.
+-----------------------------------+ +-----------------------------------+
| Figures omitted from text version | | Figures omitted from text version |
+-----------------------------------+ +-----------------------------------+
Figure 5: Downstream per-interface (S,G,rpt) state-machine Figure 5: Downstream per-interface (S,G,rpt) state-machine
In tabular form, the state machine is: In tabular form, the state machine is:
+--------++----------------------------------------------------------------------+ +----------++----------------------------------------------------------------+
| || 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 |
| ||or | (S,G,rpt) | (S,G,rpt) | | Timer | Expires | | || | (S,G,rpt) | (S,G,rpt) | | Timer | Expires |
| ||Join(*,*,RP(G)) | | | | Expires | | | || | | | | Expires | |
+--------++----------------+-----------+-----------+---------+---------+---------+ +----------++----------+-----------+-----------+---------+---------+---------+
| ||- | - | -> PP | - | n/a | n/a | | ||- | - | -> PP | - | n/a | n/a |
| || | | state | | | | | || | | state | | | |
| || | | start | | | | | || | | start | | | |
| || | | Prune | | | | | || | | Prune | | | |
|No Info || | | Pending | | | | |No Info || | | Pending | | | |
|(NI) || | | Timer; | | | | |(NI) || | | Timer; | | | |
| || | | start | | | | | || | | start | | | |
| || | | Expiry | | | | | || | | Expiry | | | |
| || | | Timer | | | | | || | | Timer | | | |
| || | | Timer | | | | | || | | Timer | | | |
+--------++----------------+-----------+-----------+---------+---------+---------+ +----------++----------+-----------+-----------+---------+---------+---------+
| ||-> P' state | -> NI | -> P | - | n/a | -> NI | | ||-> P' | -> NI | -> P | - | n/a | -> NI |
|Pruned || | state | state | | | state | |Pruned ||state | state | state | | | state |
|(P) || | | restart | | | | |(P) || | | restart | | | |
| || | | Expiry | | | | | || | | Expiry | | | |
| || | | Timer | | | | | || | | Timer | | | |
+--------++----------------+-----------+-----------+---------+---------+---------+ +----------++----------+-----------+-----------+---------+---------+---------+
|Prune ||-> PP' state | -> NI | - | - | -> P | n/a | |Prune ||-> PP' | -> NI | - | - | -> P | n/a |
|Pending || | state | | | state | | |Pending ||state | state | | | state | |
|(PP) || | | | | | | |(PP) || | | | | | |
+--------++----------------+-----------+-----------+---------+---------+---------+ +----------++----------+-----------+-----------+---------+---------+---------+
| ||error | error | -> P | -> NI | n/a | n/a | | ||error | error | -> P | -> NI | n/a | n/a |
|Temp. || | | state | state | | | |Prune Tmp || | | state | state | | |
|Pruned || | | restart | | | | |(P') || | | restart | | | |
|(P') || | | Expiry | | | | | || | | Expiry | | | |
| || | | Timer | | | | | || | | Timer | | | |
+--------++----------------+-----------+-----------+---------+---------+---------+ +----------++----------+-----------+-----------+---------+---------+---------+
|Temp. ||error | error | -> PP | -> NI | n/a | n/a | | ||error | error | -> PP | -> NI | n/a | n/a |
|Prune || | | state | state | | | |Prune || | | state | state | | |
|Pending || | | restart | | | | |Pending || | | restart | | | |
|(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 Prune(S,G,rpt)",
"Receive Join(*,G)" and "Receive Join(*,*,RP(G))" imply receiving a Join and "Receive Join(*,G)" imply receiving a Join or Prune targeted to this
or Prune targeted to this router's address on the received interface. router's address on the received interface. If the destination address
If the destination address is not correct, these state transitions in is not correct, these state transitions in this state machine must not
this state machine must not occur, although seeing such a packet may occur, although seeing such a packet may cause state transitions in
cause state transitions in other state machines. 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 address
should be the same as the source address it chose for the hello packet should be the same as the source address it chose for the Hello message
it sent over that interface. However on point-to-point links we also it sent over that interface. However on point-to-point links we also
recommend that PIM messages with a 0.0.0.0 destination address are also recommend that PIM messages with a destination address of all zeros are
accepted. 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 address on I. | Neighbor Address set to the router's 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 PrunePending state. The Expiry Timer (ET) transitions to the PrunePending 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 PrunePending timer is started; it is Join/Prune message. The PrunePending timer is started; it is
set to the J/P_Override_Interval if the router has more than set to the J/P_Override_Interval(I) if the router has more
one neighbor on that interface; otherwise it is set to zero than one neighbor on that interface; otherwise it is set to
causing it to expire immediately. zero causing it to expire immediately.
Transitions from PrunePending State Transitions from PrunePending State
When in PrunePending (PP) state, the following events may trigger a When in PrunePending (PP) state, the following events may trigger a
transition: transition:
Receive Join(*,G) or Join(*,*,RP(G)) Receive Join(*,G)
A Join(*,*,RP(G)) or Join(*,G) is received on interface I with | A Join(*,G) is received on interface I with its Upstream
its Upstream Neighbor Address set to the router's address on | Neighbor Address set to the router's address on I.
I. |
The (S,G,rpt) downstream state machine on interface I The (S,G,rpt) downstream state machine on interface I
transitions to Temp. PrunePending state whilst the remainder transitions to PrunePendingTmp state whilst the remainder of
of the compound Join/Prune message containing the the compound Join/Prune message containing the Join(*,G) is
Join(*,*,RP(G)) or Join(*,G) is processed. processed.
Receive Join(S,G,rpt) Receive Join(S,G,rpt)
A Join(S,G,rpt) is received on interface I with its Upstream | A Join(S,G,rpt) is received on interface I with its Upstream
Neighbor Address set to the router's address on I. | Neighbor Address set to the router's 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 NoInfo state. ET and PPT are canceled. transitions to NoInfo state. ET and PPT are canceled.
PrunePending Timer Expires PrunePending Timer Expires
The PrunePending Timer for the (S,G,rpt) downstream state The PrunePending 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 Pruned state. transitions to the Pruned state.
Transitions from Pruned State Transitions from Pruned State
When in Pruned (P) state, the following events may trigger a transition: When in Pruned (P) state, the following events may trigger a transition:
Receive Join(*,G) or Join(*,*,RP(G)) Receive Join(*,G)
A Join(*,*,RP(G)) or Join(*,G) is received on interface I with | A Join(*,G) is received on interface I with its Upstream
its Upstream Neighbor Address set to the router's address on | Neighbor Address set to the router's address on I.
I. |
The (S,G,rpt) downstream state machine on interface I The (S,G,rpt) downstream state machine on interface I
transitions to Temp. Pruned state whilst the remainder of the transitions to PruneTmp state whilst the remainder of the
compound Join/Prune message containing the Join(*,*,RP(G)) or compound Join/Prune message containing the Join(*,G) is
Join(*,G) is processed. processed.
Receive Join(S,G,rpt) Receive Join(S,G,rpt)
A Join(S,G,rpt) is received on interface I with its Upstream | A Join(S,G,rpt) is received on interface I with its Upstream
Neighbor Address set to the router's address on I. | Neighbor Address set to the router's 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 NoInfo state. ET and PPT are canceled. transitions to NoInfo state. ET and PPT are canceled.
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 address on I. | Neighbor Address set to the router's address on I.
The (S,G,rpt) downstream state machine on interface I remains The (S,G,rpt) downstream state machine on interface I remains
in Pruned state. The Expiry Timer (ET) is restarted, set to in Pruned state. 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.
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. ET and PPT are canceled. transitions to the NoInfo state. ET and PPT are canceled.
Transitions from Temp. PrunePending State Transitions from PrunePendingTmp State
When in Temp. PrunePending (PP') state and processing a compound When in PrunePendingTmp (PP') state and processing a compound Join/Prune
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 PrunePending state. The Expiry Timer transitions back to the PrunePending 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 Temp. Pruned State Transitions from PruneTmp State
When in Temp. Pruned (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 Pruned state. The Expiry Timer (ET) transitions back to the Pruned state. The Expiry Timer (ET)
is restarted, set to maximum of its current value and the 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.
Notes: Notes:
Receiving a Prune(*,*,RP(G)) or Prune(*,G) does not affect the (S,G,rpt) Receiving a Prune(*,G) does not affect the (S,G,rpt) downstream state
downstream state machine. machine.
Receiving a Join(*,*,RP) does not affect the (S,G,rpt) downstream state
machine. If a router has originated Join(*,*,RP) and pruned a source
off it using Prune(S,G,rpt), then to receive that source again it should
explicitly re-join using Join(S,G,rpt) or Join(*,G). In some LAN
topologies it is possible for a router sending a new Join(*,*,RP) to
have to wait as much as a Join/Prune Interval before noticing that it
needs to override a neighbor's pre-existing Prune(S,G,rpt). This is
considered acceptable, as (*,*,RP) state is intended to be used only in
long-lived and persistent scenarios.
4.4.5. Sending (*,*,RP) Join/Prune Messages 4.4.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 that
subnet, and these may modify its behavior. If it sees a Join(*,*,RP) to subnet, and these may modify its behavior. If it sees a Join(*,*,RP) to
skipping to change at page 51, line 16 skipping to change at page 51, line 26
be prepared to override that prune by sending a Join(*,*,RP) almost be prepared to override that prune by sending a Join(*,*,RP) almost
immediately. Finally, if it sees the Generation ID (see Section 4.6) of immediately. Finally, if it sees the Generation ID (see Section 4.6) of
the correct upstream neighbor change, it knows that the upstream the correct upstream neighbor change, it knows that the upstream
neighbor has lost state, and it should be prepared to refresh the state neighbor has lost state, and it should be prepared to refresh the state
by sending a Join(*,*,RP) almost immediately. 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 towards
the RP has changed, the router should prune off from the old next hop, the RP has changed, the router should prune off from the old next hop,
and join towards the new next hop. and join towards the new next hop.
The upstream (*,*,RP) state-machine only contains two states: The upstream (*,*,RP) state-machine contains only 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 RP.
Joined Joined
The downstream state-machines indicate that the router would like The downstream state-machines indicate that the router would like
to join the RP tree for this group. to 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 which 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,
MRIB.next_hop(RP). MRIB.next_hop(RP).
+-----------------------------------+ +-----------------------------------+
| Figures omitted from text version | | Figures omitted from text version |
+-----------------------------------+ +-----------------------------------+
Figure 6: Upstream (*,*,RP) state-machine Figure 6: Upstream (*,*,RP) state-machine
skipping to change at page 52, line 15 skipping to change at page 52, line 15
In tabular form, the state machine is: In tabular form, the state machine is:
+-------------------+---------------------------------------------------+ +-------------------+---------------------------------------------------+
| | Event | | | Event |
| Prev State +--------------------------+------------------------+ | Prev State +--------------------------+------------------------+
| | JoinDesired(*,*,RP) | JoinDesired(*,*,RP) | | | JoinDesired(*,*,RP) | JoinDesired(*,*,RP) |
| | ->True | ->False | | | ->True | ->False |
+-------------------+--------------------------+------------------------+ +-------------------+--------------------------+------------------------+
| | -> J state | - | | | -> J state | - |
| NotJoined (NJ) | Send Join(*,*,RP); | | | NotJoined (NJ) | Send Join(*,*,RP); | |
| | Set Timer to | | | | Set Join Timer to | |
| | t_periodic | | | | t_periodic | |
+-------------------+--------------------------+------------------------+ +-------------------+--------------------------+------------------------+
| Joined (J) | - | -> NJ state | | Joined (J) | - | -> NJ state |
| | | Send Prune(*,*,RP) | | | | Send Prune(*,*,RP); |
| | | Cancel Join Timer |
+-------------------+--------------------------+------------------------+ +-------------------+--------------------------+------------------------+
In addition, we have the following transitions which occur within the In addition, we have the following transitions which occur within the
Joined state: Joined state:
+-----------------------------------------------------------------------+ +-----------------------------------------------------------------------+
| In Joined (J) State | | In Joined (J) State |
+-----------------+---------------------+-------------------------------+ +-----------------+----------------------+------------------------------+
| Timer Expires | See | See | | Timer Expires | See | See |
| | Join(*,*,RP) | Prune(*,*,RP) | | | Join(*,*,RP) | Prune(*,*,RP) |
| | to | to | | | to | to |
| | MRIB.next_hop(RP) | MRIB.next_hop(RP) | | | MRIB.next_hop(RP) | MRIB.next_hop(RP) |
+-----------------+---------------------+-------------------------------+ +-----------------+----------------------+------------------------------+
| Send | Increase Timer to | Decrease Timer to | | Send | Increase Join | Decrease Join |
| Join(*,*,RP); | t_suppressed | t_override | | Join(*,*,RP); | Timer to | Timer to |
| Set Timer to | | | | Set Join Timer | t_joinsuppress | t_override |
| t_periodic | | | | to t_periodic | | |
+-----------------+---------------------+-------------------------------+ +-----------------+----------------------+------------------------------+
+-----------------------------------------------------------------------+| +-----------------------------------------------------------------------+
| In Joined (J) State || | In Joined (J) State |
+-----------------------------------+-----------------------------------+| +-----------------------------------+-----------------------------------+
| MRIB.next_hop(RP) | | MRIB.next_hop(RP) GenID | || | MRIB.next_hop(RP) | MRIB.next_hop(RP) GenID |
| changes | | changes | || | changes | changes |
+-----------------------------------+-----------------------------------+| +-----------------------------------+-----------------------------------+
| Send Join(*,*,RP) to new | | Decrease 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 next | | || | Prune(*,*,RP) to old | |
| hop; set Timer to | | || | next hop; set Join Timer | |
| 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
} }
skipping to change at page 54, line 15 skipping to change at page 54, line 15
is MRIB.next_hop(RP). Restart the Join Timer (JT) to expire is MRIB.next_hop(RP). Restart the Join Timer (JT) to expire
after t_periodic seconds. after t_periodic seconds.
See Join(*,*,RP) to MRIB.next_hop(RP) See Join(*,*,RP) to MRIB.next_hop(RP)
This event is only relevant if RPF_interface(RP) is a shared This event is only relevant if RPF_interface(RP) is a shared
medium. This router sees another router on RPF_interface(RP) medium. This router sees another router on RPF_interface(RP)
send a Join(*,*,RP) to MRIB.next_hop(RP). This causes this send a Join(*,*,RP) to MRIB.next_hop(RP). This causes this
router to suppress its own Join. router to suppress its own Join.
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 less than t_suppressed
seconds, reset it so that it expires after t_suppressed Let t_joinsuppress be the minimum of t_suppressed and the
HoldTime from the Join/Prune message triggering this event.
If the Join Timer is set to expire in less than t_joinsuppress
seconds, reset it so that it expires after t_joinsuppress
seconds. If the Join Timer is set to expire in more than seconds. If the Join Timer is set to expire in more than
t_suppressed seconds, leave it unchanged. t_joinsuppress seconds, leave it unchanged.
See Prune(*,*,RP) to MRIB.next_hop(RP) See Prune(*,*,RP) to MRIB.next_hop(RP)
This event is only relevant if RPF_interface(RP) is a shared This event is only relevant if RPF_interface(RP) is a shared
medium. This router sees another router on RPF_interface(RP) medium. This router sees another router on RPF_interface(RP)
send a Prune(*,*,RP) to MRIB.next_hop(RP). As this router is send a Prune(*,*,RP) to MRIB.next_hop(RP). As this router is
in Joined state, it must override the Prune after a short in Joined state, it must override the Prune after a short
random interval. random interval.
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.
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.
MRIB.next_hop(RP) changes | 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 Prune(*,*,RP) to the old upstream neighbor, which is the Send Prune(*,*,RP) to the old upstream neighbor, which is the
old value of MRIB.next_hop(RP). Send Join(*,*,RP) to the new old value of MRIB.next_hop(RP). Send Join(*,*,RP) to the new
upstream neighbor which is the new value of MRIB.next_hop(RP). upstream neighbor which is the new value of 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.
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
skipping to change at page 56, line 7 skipping to change at page 56, line 7
RPF'(*,G). RPF'(*,G).
+-----------------------------------+ +-----------------------------------+
| Figures omitted from text version | | Figures omitted from text version |
+-----------------------------------+ +-----------------------------------+
Figure 7: Upstream (*,G) state-machine Figure 7: Upstream (*,G) state-machine
In tabular form, the state machine is: In tabular form, the state machine is:
+---------------------+-------------------------------------------------+ +--------------------++-------------------------------------------------+
| | 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 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 |
+--------------------++------------------------+------------------------+
In addition, we have the following transitions which occur within the In addition, we have the following transitions which occur within the
Joined state: | Joined state:
+------------------------------------------------------------------------|--------------------| +-----------------------------------------------------------------------+
| In Joined (J) State | | | In Joined (J) State |
+-----------------+------------------+------------------+----------------|-|------------------| +------------+----------------+--------------+------------+-------------+
|Timer | | See | | See | | RPF'(*,G) | | | RPF'(*,G) || | |Timer |See |See |RPF'(*,G) | RPF'(*,G) |
|Expires | | Join(*,G) to | | Prune(*,G) | | changes | | | changes due || | |Expires |Join(*,G) to |Prune(*,G) |changes | changes due |
| | RPF'(*,G) | | to RPF'(*,G) | | | | to Assert || | | |RPF'(*,G) |to RPF'(*,G) | | to Assert |
+-----------------+------------------+------------------+------------------+------------------| +------------+----------------+--------------+------------+-------------+
|Send | | Increase Timer | | Decrease Timer | | Decrease Timer ||| Send ||| |Send |Increase |Decrease |Decrease | Send |
|Join(*,G); Set | | to | | to t_override | | to t_override ||| Join(*,G); Set ||| |Join(*,G); |Join Timer |Join Timer |Join Timer | Join(*,G); |
|Timer to | | t_suppressed | | | | | Timer to ||| |Set Join |to |to |to | Set Join |
|t_periodic | | | | | | t_periodic ||| |Timer to |t_joinsuppress |t_override |t_override | Timer to |
+-----------------+------------------+------------------+------------------+------------------| |t_periodic | | | | t_periodic |
+------------+----------------+--------------+------------+-------------+
+-----------------------------------------------------------------------+| +-----------------------------------------------------------------------+
| In Joined (J) State || | In Joined (J) State |
+-----------------------------------+-----------------------------------+| +----------------------------------+------------------------------------+
| MRIB.next_hop(RP(G)) | | RPF'(*,G) GenID changes | || | MRIB.next_hop(RP(G)) | RPF'(*,G) GenID changes |
| changes | | || | changes | |
+-----------------------------------+-----------------------------------+| +----------------------------------+------------------------------------+
| Send Join(*,G) to new next | | Decrease Timer to | || | Send Join(*,G) to new | Decrease Join Timer to |
| hop; Send Prune(*,G) to | | t_override | || | next hop; Send | t_override |
| old next hop; set Timer to | | || | Prune(*,G) to old next | |
| t_periodic | | || | hop; Set Join Timer to | |
+-----------------------------------+-----------------------------------+| | t_periodic | |
+----------------------------------+------------------------------------+
This state machine uses the following macro: This state machine uses the following macro:
bool JoinDesired(*,G) { bool JoinDesired(*,G) {
if (immediate_olist(*,G) != NULL || | if (immediate_olist(*,G) != NULL ||
(JoinDesired(*,*,RP(G)) && | (JoinDesired(*,*,RP(G)) &&
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 would
cause it to forward traffic for G using shared tree state. Note that cause it to forward traffic for G using shared tree state. Note that
although JoinDesired is true, the router's sending of a Join(*,G) although JoinDesired is true, the router's sending of a Join(*,G)
message may be suppressed by another router sending a Join(*,G) onto the message may be suppressed by another router sending a Join(*,G) onto the
upstream interface. 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
skipping to change at page 58, line 14 skipping to change at page 58, line 14
Send Join(*,G) to the appropriate upstream neighbor, which is Send Join(*,G) to the appropriate upstream neighbor, which is
RPF'(*,G). Restart the Join Timer (JT) to expire after RPF'(*,G). Restart the Join Timer (JT) to expire after
t_periodic seconds. t_periodic seconds.
See Join(*,G) to RPF'(*,G) See Join(*,G) to RPF'(*,G)
This event is only relevant if RPF_interface(RP(G)) is a This event is only relevant if RPF_interface(RP(G)) is a
shared medium. This router sees another router on shared medium. This router sees another router on
RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G). This RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G). This
causes this router to suppress its own Join. causes this router to suppress its own Join.
The upstream (*,G) state machine remains in Joined state. If The upstream (*,G) state machine remains in Joined state.
the Join Timer is set to expire in less than t_suppressed
seconds, reset it so that it expires after t_suppressed Let t_joinsuppress be the minimum of t_suppressed and the
HoldTime from the Join/Prune message triggering this event.
If the Join Timer is set to expire in less than t_joinsuppress
seconds, reset it so that it expires after t_joinsuppress
seconds. If the Join Timer is set to expire in more than seconds. If the Join Timer is set to expire in more than
t_suppressed seconds, leave it unchanged. t_joinsuppress seconds, leave it unchanged.
See Prune(*,G) to RPF'(*,G) See Prune(*,G) to RPF'(*,G)
This event is only relevant if RPF_interface(RP(G)) is a This event is only relevant if RPF_interface(RP(G)) is a
shared medium. This router sees another router on shared medium. This router sees another router on
RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G). As this RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G). As this
router is in Joined state, it must override the Prune after a router is in Joined state, it must override the Prune after a
short random interval. short random interval.
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 RPF'(*,G) changes
The current next hop towards the RP changes due an Assert(*,G) | The current next hop towards the RP changes due to an
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.
MRIB.next_hop(RP(G)) changes | MRIB.next_hop(RP(G)) changes
An event occurred which caused the next hop towards the RP for | An event occurred which 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 by the installation of a different RP-to- | routing database or by the installation of a different RP-to-
group mapping. Note that this transition should occur even if | group mapping. Note that this transition should occur even if
RPF'(*,G) is not equal to the new next hop towards RP(G), | RPF'(*,G) is not equal to the new next hop towards RP(G),
because it may be that the new neighbor is a better path to | because it may be that the new neighbor is a better path to
RP(G) than RPF'(*,G); this transition ensures that the better | RP(G) than RPF'(*,G); this transition ensures that the better
path is discovered even if an assert occurred previously. | path is discovered even if an assert occurred previously.
The upstream (*,G) state machine remains in Joined state. |
Send Prune(*,G) to the old upstream neighbor, which is the old | The upstream (*,G) state machine remains in Joined state.
value of RPF'(*,G). Send Join(*,G) to the new upstream | Send Prune(*,G) to the old upstream neighbor, which is the old
neighbor which is the new value of MRIB.next_hop(RP(G)). Note | value of RPF'(*,G). Send Join(*,G) to the new upstream
that the Join goes to MRIB.next_hop(RP(G)) and not RPF'(*,G) | neighbor which is the new value of MRIB.next_hop(RP(G)). Note
that the Join goes to MRIB.next_hop(RP(G)) and not RPF'(*,G)
even if the new neighbor is on the same interface as the old even if the new neighbor is on the same interface as the old
one because the routing change may cause the assert state to one because the routing change may cause the assert state to
be incorrect. Set the Join Timer (JT) to expire after be incorrect. 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.
skipping to change at page 59, line 48 skipping to change at page 60, line 6
refresh the state by scheduling a Join(S,G) to be sent (almost) refresh the state by scheduling a Join(S,G) to be sent (almost)
immediately. 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, the router should send a prune to the old next hop, and a join change, the router should send a prune to the old next hop, and a join
to the new next hop. 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 IGMP information do not indicate The downstream state machines and local membership information do
that the router needs to join the shortest-path tree for this not indicate that the router needs to join the shortest-path tree
(S,G). for this (S,G).
Joined Joined
The downstream state machines and IGMP information indicate that The downstream state machines and local membership information
the router should join the shortest-path tree for this (S,G). indicate that the router should join the shortest-path tree for
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 which is used to trigger the
sending of a Join(S,G) to the upstream next hop toward S, RPF'(S,G). sending of a Join(S,G) to the upstream next hop toward S, RPF'(S,G).
+-----------------------------------+ +-----------------------------------+
| Figures omitted from text version | | Figures omitted from text version |
+-----------------------------------+ +-----------------------------------+
Figure 8: Upstream (S,G) state-machine Figure 8: Upstream (S,G) state-machine
In tabular form, the state machine is: In tabular form, the state machine is:
+--------------------++-------------------------------------------------+ +--------------------+--------------------------------------------------+
| || 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 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 | | | | FALSE; Cancel Join |
+--------------------++-----------------------+-------------------------+ | | | Timer |
+--------------------+-------------------------+------------------------+
In addition, we have the following transitions which occur within the In addition, we have the following transitions which occur within the
Joined state: Joined state:
+-----------------------------------------------------------------------+ +-----------------------------------------------------------------------+
| In Joined (J) State | | In Joined (J) State |
+-----------------+-----------------+-----------------+-----------------+ +-----------------+-----------------+------------------+----------------+
|Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune | |Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune |
| | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to | | | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to |
| | | | RPF'(S,G) | | | | | RPF'(S,G) |
+-----------------+-----------------+-----------------+-----------------+ +-----------------+-----------------+------------------+----------------+
|Send | Increase Timer | Decrease Timer | Decrease Timer | | Send | Increase Join | Decrease Join | Decrease Join |
|Join(S,G); Set | to t_suppr | to t_override | to t_override | | Join(S,G); Set | Timer to | Timer to | Timer to |
|Timer to | | | | | Join Timer to | t_suppr | t_override | t_override |
|t_periodic | | | | |t_periodic | | | |
+-----------------+-----------------+-----------------+-----------------+ +-----------------+-----------------+------------------+----------------+
+------------------------------------------------------------------------|| +-----------------------------------------------------------------------+
| In Joined (J) State || | In Joined (J) State |
+-----------------------+------------------------+-----------------------|| +-----------------------+-------------------------+---------------------+
|See Prune(*,G) to | | MRIB.next_hop(S) | | RPF'(S,G) GenID | || | See Prune(*,G) to | MRIB.next_hop(S) | RPF'(S,G) GenID |
|RPF'(S,G) | | changes | | changes | || | RPF'(S,G) | changes | changes |
+-----------------------+------------------------+------------------------| +-----------------------+-------------------------+---------------------+
|Decrease Timer to | | Send Join(S,G) to | | Decrease Timer to ||| | Decrease Join | Send Join(S,G) to | Decrease Join |
|t_override | | new next hop; Send | | t_override ||| | Timer to | new next hop; Send | Timer to |
| | Prune(S,G) to old | | || | t_override | Prune(S,G) to old | t_override |
| | next hop; Set Timer | | || | | next hop; Set Join | |
| | to t_periodic | | || | | 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 would
skipping to change at page 62, line 31 skipping to change at page 62, line 31
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 following
events may trigger state transitions: events may trigger state transitions:
JoinDesired(S,G) becomes False JoinDesired(S,G) becomes False
The downstream state for (S,G) has changed so no interface is The downstream state for (S,G) has changed so no interface is
in inherited_olist(S,G), making JoinDesired(S,G) become False. in inherited_olist(S,G), making JoinDesired(S,G) become False.
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). which is RPF'(S,G). Cancel the Join Timer (JT), and set
SPTbit(S,G) to FALSE.
Join Timer Expires Join Timer Expires
The Join Timer (JT) expires, indicating time to send a The Join Timer (JT) expires, indicating time to send a
Join(S,G) Join(S,G)
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). Restart the Join Timer (JT) to expire after RPF'(S,G). Restart the Join Timer (JT) to expire after
t_periodic seconds. t_periodic seconds.
See Join(S,G) to RPF'(S,G) See Join(S,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 Join(S,G) to RPF'(S,G). This causes this router to send a Join(S,G) to RPF'(S,G). This causes this router to
suppress its own Join. suppress its own Join.
The upstream (S,G) state machine remains in Joined state. If The upstream (S,G) state machine remains in Joined state.
the Join Timer is set to expire in less than t_suppressed
seconds, reset it so that it expires after t_suppressed Let t_joinsuppress be the minimum of t_suppressed and the
HoldTime from the Join/Prune message triggering this event.
If the Join Timer is set to expire in less than t_joinsuppress
seconds, reset it so that it expires after t_joinsuppress
seconds. If the Join Timer is set to expire in more than seconds. If the Join Timer is set to expire in more than
t_suppressed seconds, leave it unchanged. t_joinsuppress seconds, leave it unchanged.
See Prune(S,G) to RPF'(S,G) See Prune(S,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(S,G) to RPF'(S,G). As this router is in Joined send a Prune(S,G) to RPF'(S,G). As this router is in Joined
state, it must override the Prune after a short random state, it must override the Prune after a short random
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
skipping to change at page 63, line 42 skipping to change at page 63, line 45
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 RPF'(S,G) changes
The current next hop towards the RP changes due 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.
MRIB.next_hop(S) changes | MRIB.next_hop(S) changes
A change in the routing base stored in the MRIB causes the | A change in the routing base stored in the MRIB causes the
next hop towards S to change. | next hop towards S to change.
The upstream (S,G) state machine remains in Joined state. The upstream (S,G) state machine remains in Joined state.
Send Prune(S,G) to the old upstream neighbor, which is the old Send Prune(S,G) to the old upstream neighbor, which is the old
value of RPF'(S,G). Send Join(S,G) to the new upstream value of RPF'(S,G). Send Join(S,G) to the new upstream
neighbor which is the new value of MRIB.next_hop(S). Note | neighbor which is the new value of MRIB.next_hop(S). Note
that the Join goes to MRIB.next_hop(S) and not RPF'(S,G) even | that the Join goes to MRIB.next_hop(S) and not RPF'(S,G) even
if the new neighbor is on the same interface as the old one | if the new neighbor is on the same interface as the old one
because the routing change may cause MRIB.next_hop(S) to have | because the routing change may cause MRIB.next_hop(S) to have
a better path to S than RPF'(S,G); sending to MRIB.next_hop(S) | a better path to S than RPF'(S,G); sending to MRIB.next_hop(S)
ensures that this is discovered. Set the Join Timer (JT) to | ensures that this is discovered. Set the Join Timer (JT) to
expire after t_periodic seconds. | 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.
skipping to change at page 66, line 11 skipping to change at page 66, line 11
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 is
used to delay triggered Join(S,G,rpt) messages to prevent implosions of used to delay triggered Join(S,G,rpt) messages to prevent implosions of
triggered messages. triggered messages.
+-----------------------------------+ +-----------------------------------+
| Figures omitted from text version | | Figures omitted from text version |
+-----------------------------------+ +-----------------------------------+
Figure 9: Upstream (S,G,rpt) state-machine for triggered messages Figure 9: Upstream (S,G,rpt) state-machine for triggered messages
In tabular form, the state machine is: | In tabular form, the state machine is:
+----------------------++-------------------------------------------------------|------------------------|
| || Event ||
| ++------------------+-------------------+----------------|-----|------------------|
|Prev State | ||PruneDesired | | PruneDesired | | RPTJoinDesired(G)|| | inherited_olist|||
| ||(S,G,rpt) | | (S,G,rpt) | | ->False || | (S,G,rpt) || |
| ||->True | | ->False | | | | ->non-NULL || |
+----------------------++------------------+-------------------+----------------------+------------------|
|RPTNotJoined | ||-> P state | - | - | | -> NP state| |
|(G) (NJ) | || | | | | |
+----------------------++------------------+-------------------+----------------------+------------------|
|Pruned (S,G,rpt) | ||- | -> NP state | -> NJ state | | -| |
|(P) | || | Send Join | | | | |
| || | (S,G,rpt) | | | | |
+----------------------++------------------+-------------------+----------------------+------------------|
| ||-> P state | - | -> NJ state | -| |
|NotPruned (S,G,rpt) | ||Send Prune | | | Cancel OT timer| ||| |
|(NP) | ||(S,G,rpt); | | | | | |
| ||Cancel OT timer | | | | | |
+----------------------++------------------+-------------------+----------------------+------------------|
+--------------++------------------------------------------------------------------+
| || Event |
| ++-------------+--------------+-------------------+-----------------+
|Prev State ||PruneDesired | PruneDesired | RPTJoinDesired(G) | inherited_olist |
| ||(S,G,rpt) | (S,G,rpt) | ->False | (S,G,rpt) |
| ||->True | ->False | | ->non-NULL |
+--------------++-------------+--------------+-------------------+-----------------+
|RPTNotJoined ||-> P state | - | - | -> NP state |
|(G) (NJ) || | | | |
+--------------++-------------+--------------+-------------------+-----------------+
|Pruned ||- | -> NP state | -> NJ state | - |
|(S,G,rpt) (P) || | Send Join | | |
| || | (S,G,rpt) | | |
+--------------++-------------+--------------+-------------------+-----------------+
| ||-> P state | - | -> NJ state | - |
|NotPruned ||Send Prune | | Cancel OT timer | |
|(S,G,rpt) ||(S,G,rpt); | | | |
|(NP) ||Cancel OT | | | |
| ||timer | | | |
+--------------++-------------+--------------+-------------------+-----------------+
Additionally, we have the following transitions within the Additionally, we have the following transitions within the
NotPruned(S,G,rpt) state which are all used for prune override behavior. | NotPruned(S,G,rpt) state which are all used for prune override behavior.
+------------------------------------------------------------------------|--------------------| +-----------------------------------------------------------------------+
| In NotPruned(S,G,rpt) State || | In NotPruned(S,G,rpt) State |
+-----------------+------------------+------------------+----------------|-|------------------| +------------+--------------+--------------+-------------+--------------+
|OT timer | | See Prune | | See Join | | See Prune | | | RPF' || | |OT timer |See Prune |See Join |See Prune | RPF' |
|expires | | (S,G,rpt) to | | (S,G,rpt) to | | (S,G) to | | | (S,G,rpt) -> || | |expires |(S,G,rpt) to |(S,G,rpt) to |(S,G) to | (S,G,rpt) -> |
| | RPF' | | RPF' | | RPF' | | | RPF' (*,G) || | | |RPF' |RPF' |RPF' | RPF' (*,G) |
| | (S,G,rpt) | | (S,G,rpt) | | (S,G,rpt) | | | | | |(S,G,rpt) |(S,G,rpt) |(S,G,rpt) | |
+-----------------+------------------+------------------+------------------+------------------| +------------+--------------+--------------+-------------+--------------+
|Send Join | | OT timer = | | Cancel OT | | OT timer = ||| OT timer = ||| |Send Join |OT timer = |Cancel OT |OT timer = | OT timer = |
|(S,G,rpt); | | min(timer, | | timer | | min(timer, ||| min(timer, ||| |(S,G,rpt); |min(timer, |timer |min(timer, | min(timer, |
|Cancel OT | | t_po) | | | t_po) ||| t_po) ||| |Cancel OT |t_override) | |t_override) | t_override) |
|timer | | | | | | | |timer | | | | |
+-----------------+------------------+------------------+------------------+------------------| +------------+--------------+--------------+-------------+--------------+
Note that the min function in the above state machine considers a non- 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_po) = running timer to have an infinite value (e.g. min(not-running,
t_po). t_override) = t_override).
This state machine uses the following macros: This state machine uses the following macros:
bool RPTJoinDesired(G) { bool RPTJoinDesired(G) {
return (JoinDesired(*,G) || JoinDesired(*,*,RP(G))) return (JoinDesired(*,G) || JoinDesired(*,*,RP(G)))
} }
RPTJoinDesired(G) is true when the router has forwarding state that RPTJoinDesired(G) is true when the router has forwarding state that
would cause it to forward traffic for G using either (*,G) or (*,*,RP) would cause it to forward traffic for G using either (*,G) or (*,*,RP)
shared tree state. shared tree state.
skipping to change at page 67, line 38 skipping to change at page 67, line 38
there are no outgoing interfaces that S would be forwarded on, or if the 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). router has active (S,G) forwarding state but RPF'(*,G) != RPF'(S,G).
The state machine contains the following transition events: The state machine contains the following transition events:
See Join(S,G,rpt) to RPF'(S,G,rpt) See Join(S,G,rpt) to RPF'(S,G,rpt)
This event is only relevant in the "Not Pruned" state. 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), 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" which is the correct upstream neighbor. If we're in "NotPruned"
state and the (S,G,rpt) override timer is running, then this is 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 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 RPF'(S,G,rpt). Someone else beat us to it, so there's no need to
send our own Join. send our own Join.
The action is to cancel the override timer. The action is to cancel the Override Timer.
See Prune(S,G,rpt) to RPF'(S,G,rpt) See Prune(S,G,rpt) to RPF'(S,G,rpt)
This event is only relevant in the "NotPruned" state. This event is only relevant in the "NotPruned" state.
The router sees a Prune(S,G,rpt) from someone else to to The router sees a Prune(S,G,rpt) from someone else to to
RPF'(S,G,rpt), which is the correct upstream neighbor. If we're in RPF'(S,G,rpt), which is the correct upstream neighbor. If we're in
the "NotPruned" state, then we want to continue to receive traffic the "NotPruned" state, then we want to continue to receive traffic
from S destined for G, and that traffic is being supplied by from S destined for G, and that traffic is being supplied by
RPF'(S,G,rpt). Thus we need to override the Prune. RPF'(S,G,rpt). Thus we need to override the Prune.
The action is to set the (S,G,rpt) time to the randomized prune- The action is to set the (S,G,rpt) Override Timer to the randomized
override interval. However if the override timer is already prune-override interval, t_override. However if the Override Timer
running, we only set the timer if doing so would set it to a lower is already running, we only set the timer if doing so would set it
value. At the end of this interval, if no-one else has sent a to a lower value. At the end of this interval, if no-one else has
Join, then we will do so. sent a Join, then we will do so.
See Prune(S,G) to RPF'(S,G,rpt) See Prune(S,G) to RPF'(S,G,rpt)
This event is only relevant in the "NotPruned" state. This event is only relevant in the "NotPruned" state.
This transition and action are the same as the above transition and This transition and action are the same as the above transition and
action, except that the Prune does not have the RPT bit set. This action, except that the Prune does not have the RPT bit set. This
transition is necessary to be compatible with existing routers that transition is necessary to be compatible with routers implemented
don't maintain separate (S,G) and (S,G,rpt) state. from RFC2362 that don't maintain separate (S,G) and (S,G,rpt)
state.
The (S,G,rpt) prune override timer expires The (S,G,rpt) prune Override Timer expires
This event is only relevant in the "NotPruned" state. This event is only relevant in the "NotPruned" state.
When the override timer expires, we must send a Join(S,G,rpt) to When the Override Timer expires, we must send a Join(S,G,rpt) to
RPF'(S,G,rpt) to override the Prune message that caused the timer 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) 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 - 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 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 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 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 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 would then cause RPF'(S,G,rpt) to become equal to RPF'(*,G) (see
below). below).
RPF'(S,G,rpt) changes to become equal to RPF'(*,G) RPF'(S,G,rpt) changes to become equal to RPF'(*,G)
This event is only relevant in the "NotPruned" state. This event is only relevant in the "NotPruned" state.
RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G) RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G)
Assert has happened, which means that traffic from S is arriving on Assert has happened, which means that traffic from S is arriving on
the SPT, and so Prune(S,G,rpt) will have been sent to RPF'(*,G). 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 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 trigger a Join(S,G,rpt) to RPF'(*,G) to cause that router to start
forwarding S again. forwarding S again.
The action is to set the (S,G,rpt) override timer to the randomized The action is to set the (S,G,rpt) Override Timer to the randomized
prune-override interval. However if the timer is already running, prune-override interval t_override. However if the timer is
we only set the timer if doing so would set it to a lower value. already running, we only set the timer if doing so would set it to
At the end of this interval, if no-one else has sent a Join, then a lower value. At the end of this interval, if no-one else has
we will do so. sent a Join, then we will do so.
PruneDesired(S,G,rpt)->TRUE PruneDesired(S,G,rpt)->TRUE
See macro above. See macro above. This event is relevant in the "NotPruned" and
"RPTNotJoined(G)" states.
The router wishes to receive traffic for G, but does not wish to The router wishes to receive traffic for G, but does not wish to
receive traffic from S destined for G. This causes the router to receive traffic from S destined for G. This causes the router to
transition into the Pruned state. transition into the Pruned state.
If the router was previously in NotPruned state, then the action is If the router was previously in NotPruned state, then the action is
to send a Prune(S,G,rpt) to RPF'(S,G,rpt). If the router was to send a Prune(S,G,rpt) to RPF'(S,G,rpt), and to cancel the
previously in RPTNotJoined(G) state, then there is no need to Override Timer. If the router was previously in RPTNotJoined(G)
trigger an action in this state machine because sending a state, then there is no need to trigger an action in this state
Prune(S,G,rpt) is handled by the rules for sending the Join(*,G) or machine because sending a Prune(S,G,rpt) is handled by the rules
Join(*,*,RP). for sending the Join(*,G) or Join(*,*,RP).
PruneDesired(S,G,rpt)->FALSE PruneDesired(S,G,rpt)->FALSE
See macro above. This transition is only relevant in the "Pruned" See macro above. This transition is only relevant in the "Pruned"
state. state.
If the router is in the Pruned(S,G,rpt) state, and If the router is in the Pruned(S,G,rpt) state, and
PruneDesired(S,G,rpt) changes to FALSE, this could be because the PruneDesired(S,G,rpt) changes to FALSE, this could be because the
router no longer has RPTJoinDesired(G) true, or it now wishes to router no longer has RPTJoinDesired(G) true, or it now wishes to
receive traffic from S again. If it is the former, then this receive traffic from S again. If it is the former, then this
transition should not happen, but instead the transition should not happen, but instead the
"RPTJoinDesired(G)->FALSE" transition should happen. Thus this "RPTJoinDesired(G)->FALSE" transition should happen. Thus this
transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE
AND RPTJoinDesired(G)==TRUE" AND RPTJoinDesired(G)==TRUE"
The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt). The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt).
RPTJoinDesired(G)->FALSE RPTJoinDesired(G)->FALSE
This event is relevant in the "Pruned" and "NotPruned" states.
The router no longer wishes to receive any traffic destined for G The router no longer wishes to receive any traffic destined for G
on the RP Tree. This causes a transition to the RPTNotJoined(G) on the RP Tree. This causes a transition to the RPTNotJoined(G)
state. Any actions are handled by the appropriate upstream state state, and the Override Timer is cancelled if it was running. Any
further actions are handled by the appropriate upstream state
machine for (*,G) or (*,*,RP). machine for (*,G) or (*,*,RP).
inherited_olist(S,G,rpt) becomes non-NULL inherited_olist(S,G,rpt) becomes non-NULL
This transition is only relevant in the RPTNotJoined(G) state. This transition is only relevant in the RPTNotJoined(G) state.
The router has joined the RP tree (handled by the (*,G) or (*,*,RP) The router has joined the RP tree (handled by the (*,G) or (*,*,RP)
upstream state machine as appropriate), and wants to receive upstream state machine as appropriate), and wants to receive
traffic from S. This does not trigger any events in this 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. machine, but causes a transition to the NotPruned(S,G,rpt) state.
skipping to change at page 71, line 35 skipping to change at page 71, line 35
| Timer Expires | Receive | Receive | CouldAssert | | Timer Expires | Receive | Receive | CouldAssert |
| | Inferior | Preferred | (S,G,I) -> | | | 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 | | In I Am Assert Loser (L) State |
+---------------+-------------------+-----------------+-----------------+ +---------------+------------------+------------------+-----------------+
| Receive | Receive | Timer Expires | AssTrDes | | Receive | Receive | Receive | Timer Expires |
| Preferred | Inferior | | (S,G,I) -> | | Preferred | Inferior | Acceptable | |
| Assert | Assert from | | FALSE | | Assert | Assert from | Assert from | |
| | Current Winner | | | | | Current Winner | Current Winner | |
+---------------+-------------------+-----------------+-----------------+ +---------------+------------------+------------------+-----------------+
| -> L state | -> NI state | -> NI state | -> NI state | | -> L state | -> L state | -> NI state | -> NI state |
| [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | | [Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] |
+---------------+-------------------+-----------------+-----------------+ +---------------+------------------+------------------+-----------------+
+-----------------------------------------------------------------------+ +-----------------------------------------------------------------------+
| In I Am Assert Loser (L) State | | In I Am Assert Loser (L) State |
+----------------+-----------------+-----------------+------------------+ +----------------+-----------------+-------------------+----------------+
| my_metric -> | RPF interface | Receive | Receive Assert | | AssTrDes | my_metric -> | RPF_interface | Receive |
| better than | stops being I | Join(S,G) on | from Current | | (S,G,I) -> | better than | (S) stops | Join(S,G) on |
| winner's | | interface I | Winner | | FALSE | winner's | being I | interface I |
| metric | | | | | | metric | | |
+----------------+-----------------+-----------------+------------------+ +----------------+-----------------+-------------------+----------------+
| -> NI state | -> NI state | -> NI State | -> L state | | -> NI state | -> NI state | -> NI state | -> NI State |
| [Actions A5] | [Actions A5] | [Actions A5] | [Actions A2] | | [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 the
state-machine table to refer to AssertTrackingDesired(S,G,I). state-machine table to refer to AssertTrackingDesired(S,G,I).
Terminology: Terminology:
A "preferred assert" is one with a better metric than the current A "preferred assert" is one with a better metric than the current
winner. winner.
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). my_assert_metric(S,G,I).
An "inferior assert" is one with a worse metric than
my_assert_metric(S,G,I).
The state machine uses the following macros: 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 which 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 into
account. | 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) (+) pim_include(S,G) ) ) | (+) joins(S,G) ) )
OR (RPF_interface(S)==I AND JoinDesired(S,G)==TRUE) | OR (local_receiver_include(S,G,I)==TRUE
OR (RPF_interface(RP)==I AND JoinDesired(*,G)==TRUE | AND (I_am_DR(I) OR AssertWinner(S,G,I) == me))
AND SPTbit(S,G)==FALSE) | OR (RPF_interface(S)==I AND JoinDesired(S,G)==TRUE)
OR (RPF_interface(RP)==I AND JoinDesired(*,G)==TRUE
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 (S,G)
assert might affect our behavior. | 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
information received on I that might cause the router to be interested and local membership information received on I that might cause the
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
I. Note that we can't use the pim_include(S,G) macro since it uses
lost_assert(S,G,I) and would result in the router forgetting 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
keep on being responsible for forwarding as long as local receivers are
present. Removing this check would make the assert winner give up
forwarding as soon as the information that originally caused it to
forward went away and the task of forwarding for local receivers 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 track
of assert information on upstream interfaces in order to send joins and of assert information on upstream interfaces in order to send joins and
prunes to the proper neighbor. 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 Receive Inferior Assert with RPTbit cleared AND
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 as (S,G) metric, then we must also have (S,G) forwarding state (i.e.
asserts beat (*,G) asserts, and so we should be the assert CouldAssert(S,G,I)==TRUE) as (S,G) asserts beat (*,G) asserts,
winner. We transition to the "I am Assert Winner" state, and and so we should be the assert winner. We transition to the
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
skipping to change at page 74, line 16 skipping to change at page 74, line 30
perform Actions A1 (below) which will initiate the assert perform Actions A1 (below) which will initiate the assert
negotiation for (S,G). negotiation for (S,G).
Receive Preferred Assert with RPT bit clear AND Receive Preferred 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 that and we have (S,G) forwarding state. The received assert that
has a better metric than our own, so we do not win the Assert. has a better metric than our own, so we do not win the Assert.
We transition to "I am Assert Loser" and perform actions A2 We transition to "I am Assert Loser" and perform actions A6
(below). (below).
Transitions from 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:
Timer Expires 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 then we must still have (S,G) forwarding state that is
actively being kept alive. We re-send the (S,G) Assert and actively being kept alive. We re-send the (S,G) Assert and
restart the timer (Action A3 below). Note that the assert restart the timer (Action A3 below). Note that the assert
winner's timer is engineered to expire shortly before timers winner's timer is engineered to expire shortly before timers
skipping to change at page 74, line 43 skipping to change at page 75, line 9
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 re-send an (S,G) Assert, and restart the
timer (Action A3 below). timer (Action 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) which could cause transitions in the upstream JoinDesired(S,G) and PruneDesired(S,G,rpt) which could cause
(S,G) state machine. 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 "cancelling assert" with an infinite metric. sending a "cancelling assert" with an infinite metric.
Transitions from 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 from Current Winner
We receive an assert from the current assert winner that is
better than our own metric for this (S,G) (although the metric
may be worse than the winner's previous metric). We stay in
Loser state, and perform actions A2 below.
Receive Inferior Assert from Current Winner Receive Inferior Assert 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 the
winner's metric became worse). We transition to NoInfo state, winner's metric became worse). We transition to NoInfo state,
deleting the (S,G) assert information and allowing the normal deleting the (S,G) assert information and allowing the normal
PIM Join/Prune mechanisms to operate. Usually we will PIM Join/Prune mechanisms to operate. Usually we will
eventually re-assert and win when data packets from S have eventually re-assert and win when data packets from S have
started flowing again. started flowing again.
Timer Expires Timer Expires
skipping to change at page 75, line 37 skipping to change at page 76, line 9
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 the underlying
routing metric changes, or when when CouldAssert(S,G,I) routing metric changes, or when CouldAssert(S,G,I) becomes
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
and allow the normal PIM Join/Prune mechanisms to operate. (action A5 below), and allow the normal PIM Join/Prune
Usually we will eventually re-assert and win when data packets mechanisms to operate. Usually we will eventually re-assert
from S have started flowing again. and win when data packets from S have started flowing again.
RPF interface changed away from interface I RPF interface changed away from 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, delete this (S,G) assert not. We transition to NoInfo state, deleting this (S,G)
state. assert state (action A5 below).
Receive Join(S,G) Receive Join(S,G) on Interface I
We receive a Join(S,G) directed to my IP address in interface We receive a Join(S,G) that has the Upstream Neighbor Address
I. The action is to transition to NoInfo state, and delete field set to one my IP address on interface I. The action is
this (S,G) assert state, and allow the normal PIM Join/Prune to transition to NoInfo state, and delete this (S,G) assert
state (action 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 timer to (Assert_Time - Assert_Override_Interval) Set timer to (Assert_Time - Assert_Override_Interval)
Store self as AssertWinner(S,G,I) Store self as AssertWinner(S,G,I)
Store spt_assert_metric(S,I) as AssertWinnerMetric(S,G,I) Store spt_assert_metric(S,I) as AssertWinnerMetric(S,G,I)
A2: Store new assert winner as AssertWinner(S,G,I) and assert | A2: Store new assert winner as AssertWinner(S,G,I) and assert
winner metric as AssertWinnerMetric(S,G,I). | winner metric as AssertWinnerMetric(S,G,I).
Set timer to Assert_Time Set timer to Assert_Time
A3: Send Assert(S,G) A3: Send Assert(S,G)
Set timer to (Assert_Time - Assert_Override_Interval) Set timer to (Assert_Time - Assert_Override_Interval)
A4: Send AssertCancel(S,G) A4: Send AssertCancel(S,G)
Delete assert info (AssertWinner(S,G,I) and | Delete assert info (AssertWinner(S,G,I) and
AssertWinnerMetric(S,G,I) assume default values). | AssertWinnerMetric(S,G,I) will then return their default
values).
A5: Delete assert info (AssertWinner(S,G,I) and | A5: Delete assert info (AssertWinner(S,G,I) and
AssertWinnerMetric(S,G,I) assume default values). | AssertWinnerMetric(S,G,I) will then return their default
values).
A6: Store new assert winner as AssertWinner(S,G,I) and assert | A6: Store new assert winner as AssertWinner(S,G,I) and assert
winner metric as AssertWinnerMetric(S,G,I). | winner metric as AssertWinnerMetric(S,G,I).
Set timer to Assert_Time Set timer to Assert_Time
If I is RPF_interface(S) Set SPTbit(S,G) to TRUE. If I is RPF_interface(S) set SPTbit(S,G) to TRUE.
Note that some of these actions may cause the value of JoinDesired(S,G),
PruneDesired(S,G,rpt), or RPF'(S) to change, which could cause further
transitions in other state machines.
4.5.2. (*,G) Assert Message State Machine 4.5.2. (*,G) Assert Message State Machine
The (*,G) Assert state-machine for interface I is shown in Figure 11. The (*,G) Assert state-machine for interface I is shown in Figure 11.
There are three states: There are three states:
NoInfo (NI) NoInfo (NI)
This router has no (*,G) assert state on interface I. This router has no (*,G) assert state on interface I.
I am Assert Winner (W) I am Assert Winner (W)
skipping to change at page 77, line 16 skipping to change at page 77, line 42
This router has lost an (*,G) assert on interface I. It must not This router has lost an (*,G) assert on interface I. It must not
forward packets for G onto interface I with the exception of forward packets for G onto interface I with the exception of
traffic from sources for which is has (S,G) "I am Assert Winner" traffic from sources for which is has (S,G) "I am Assert Winner"
state. If it is the DR, it is no longer responsible for handling state. If it is the DR, it is no longer responsible for handling
the membership requests for group G from local hosts on I. the membership requests for group G from local hosts on I.
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 out
asserts on the assert losers and to resend asserts on the assert winner. asserts on the assert losers and to resend asserts on the assert winner.
It is important to note that no transition occurs in the (*,G) state It is important to note that no transition occurs in the (*,G) state
machine as a result of receiving an assert message if the (S,G) assert machine as a result of receiving an Assert message if the (S,G) assert
state machine for the relevant S and G is not in the "NoInfo" state. state machine for the relevant S and G is not in the "NoInfo" state.
+-----------------------------------+ +-----------------------------------+
| Figures omitted from text version | | Figures omitted from text version |
+-----------------------------------+ +-----------------------------------+
Figure 11: (*,G) Assert State-machine Figure 11: (*,G) Assert State-machine
In tabular form the state machine is: | In tabular form the state machine is:
+-----------------------------------------------------------------------+| +-----------------------------------------------------------------------+
| In NoInfo (NI) State || | In NoInfo (NI) State |
+-----------------------+-----------------------+-----------------------+| +-----------------------+-----------------------+-----------------------+
|Receive Inferior | | Data arrives for G | | Receive Preferred | || | Receive Inferior | Data arrives for G | Receive Preferred |
|Assert with RPTbit | | and CouldAssert | | Assert with RPTbit | || | Assert with RPTbit | and CouldAssert | Assert with RPTbit |
|set and | | (*,G,I) | | set and AssTrDes | || | set and | (*,G,I) | set and AssTrDes |
|CouldAssert(*,G,I) | | | (*,G,I) | || | CouldAssert(*,G,I) | | (*,G,I) |
+-----------------------+-----------------------+-----------------------+| +-----------------------+-----------------------+-----------------------+
|-> Winner state | -> Winner state | -> Loser state || | -> W state | -> W state | -> L state |
|[Actions A1] | [Actions A1] | [Actions A2] || | [Actions A1] | [Actions A1] | [Actions A2] |
+-----------------------+-----------------------+-----------------------+| +-----------------------+-----------------------+-----------------------+
+------------------------------------------------------------------------|-| +-----------------------------------------------------------------------+
| In I Am Assert Winner (W) State || | In I Am Assert Winner (W) State |
+-----------------+------------------+------------------+----------------|-| +-----------------+-----------------+------------------+----------------+
|Timer Expires | | Receive | | Receive | | CouldAssert ||| | Timer Expires | Receive | Receive | CouldAssert |
| | Inferior | | Preferred | | (*,G,I) -> ||| | | Inferior | Preferred | (*,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 || | In I Am Assert Loser (L) State |
+-----------------+------------------+------------------+----------------|-| +---------------+------------------+------------------+-----------------+
|Receive | | Receive | | Timer Expires | | AssTrDes ||| | Receive | Receive | Receive | Timer Expires |
|Preferred | | Inferior | | | (*,G,I) -> ||| | Preferred | Acceptable | Inferior | |
|Assert | | Assert from | | | FALSE ||| | Assert | Assert from | Assert from | |
| | Current Winner | | | | | | | Current Winner | Current Winner | |
+-----------------+------------------+------------------+------------------| +---------------+------------------+------------------+-----------------+
|-> L state | -> NI state | -> NI state | -> NI state | | | -> L state | -> L state | -> NI state | -> NI state |
|[Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | | | [Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] |
+-----------------+------------------+------------------+------------------| +---------------+------------------+------------------+-----------------+
+-----------------------------------------------------------------------+| +-----------------------------------------------------------------------+
| In I Am Assert Loser (L) State || | In I Am Assert Loser (L) State |
+-----------------------+-----------------------+-----------------------+| +---------------+-----------------+-----------------+-------------------+
|my_metric -> | | RPF interface | | Receive Join(*,G) | || | AssTrDes | my_metric -> | RPF_interface | Receive |
|better than | | stops being I | | or Join(*,*,RP(G)) | || | (*,G,I) -> | better than | (RP(G)) stops | Join(*,G) or |
|Winner's metric | | | on Interface I | || | FALSE | Winner's | being I | Join(*,*,RP(G)) |
+-----------------------+-----------------------+-----------------------+| | | metric | | on Interface I |
|-> NI state | -> NI state | -> NI State || +---------------+-----------------+-----------------+-------------------+
|[Actions A5] | [Actions A5] | [Actions A5] || | -> NI state | -> NI state | -> NI state | -> NI State |
+-----------------------+-----------------------+-----------------------+| | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] |
+---------------+-----------------+-----------------+-------------------+
The state machine uses the following macros: The state machine uses the following macros:
CouldAssert(*,G,I) = | CouldAssert(*,G,I) =
( I in ( joins(*,*,RP(G)) (+) joins(*,G) | ( I in ( joins(*,*,RP(G)) (+) joins(*,G)
(+) pim_include(*,G)) ) | (+) pim_include(*,G)) )
AND RPF_interface(RP(G)) != I | AND RPF_interface(RP(G)) != I
CouldAssert(*,G,I) is true on downstream interfaces for which we have | CouldAssert(*,G,I) is true on downstream interfaces for which we have
(*,*,RP(G)) or (*,G) join state, or local members that requested any | (*,*,RP(G)) or (*,G) join state, or local members that requested any
traffic destined for G. | traffic destined for G.
AssertTrackingDesired(*,G,I) = | AssertTrackingDesired(*,G,I) =
CouldAssert(*,G) OR | CouldAssert(*,G)
( RPF_interface(RP(G)) == I AND RPTJoinDesired(G) ) | OR (local_receiver_include(*,G,I)==TRUE
AND (I_am_DR(I) OR AssertWinner(*,G,I) == me))
OR (RPF_interface(RP(G)) == I AND RPTJoinDesired(G))
AssertTrackingDesired(*,G,I) is true on any interface on which an (*,G) | AssertTrackingDesired(*,G,I) is true on any interface on which an (*,G)
assert might affect our behavior. | assert might affect our behavior.
Note that for reasons of compactness, "AssTrDes(*,G,I)" is used in the | Note that for reasons of compactness, "AssTrDes(*,G,I)" is used in the
state-machine table to refer to AssertTrackingDesired(*,G,I). | state-machine table to refer to AssertTrackingDesired(*,G,I).
Terminology: | Terminology:
A "preferred assert" is one with a better metric than the current | A "preferred assert" is one with a better metric than the current
winner. | winner.
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). | my_assert_metric(*,G,I).
Transitions from NoInfo State | An "inferior assert" is one with a worse metric than
my_assert_metric(S,G).
When in NoInfo state, the following events trigger transitions, but only | Transitions from NoInfo State
if the (S,G) assert state machine is in NoInfo state: |
Receive Inferior Assert with RPTbit set AND | When in NoInfo state, the following events trigger transitions, but only
CouldAssert(*,G,I)==TRUE | if the (S,G) assert state machine is in NoInfo state:
An Inferior (*,G) assert is received for G on Interface I. If |
CouldAssert(*,G,I) is TRUE, then I is our downstream |
interface, and we have (*,G) forwarding state on this |
interface, so we should be the assert winner. We transition |
to the "I am Assert Winner" state, and perform Actions A1 |
(below). |
A data packet destined for G arrives on interface I, AND | Receive Inferior Assert with RPTbit set AND
CouldAssert(*,G,I)==TRUE | CouldAssert(*,G,I)==TRUE
A data packet destined for G arrived on a downstream interface | An Inferior (*,G) assert is received for G on Interface I. If
which is in our (*,G) outgoing interface list. We therefore | CouldAssert(*,G,I) is TRUE, then I is our downstream
believe we should be the forwarder for this (*,G), and so we | interface, and we have (*,G) forwarding state on this
transition to the "I am Assert Winner" state, and perform | interface, so we should be the assert winner. We transition
Actions A1 (below). | to the "I am Assert Winner" state, and perform Actions A1
(below).
Receive Preferred Assert with RPT bit set AND | A data packet destined for G arrives on interface I, AND
AssertTrackingDesired(*,G,I)==TRUE | CouldAssert(*,G,I)==TRUE
We're interested in (*,G) Asserts, either because I is a | A data packet destined for G arrived on a downstream interface
downstream interface for which we have (*,G) forwarding state, | which is in our (*,G) outgoing interface list. We therefore
or because I is the upstream interface for RP(G) and we have | believe we should be the forwarder for this (*,G), and so we
(*,G) forwarding state. We get a (*,G) Assert that has a | transition to the "I am Assert Winner" state, and perform
better metric than our own, so we do not win the Assert. We | Actions A1 (below).
transition to "I am Assert Loser" and perform actions A2 |
(below). |
Transitions from Winner State | Receive Preferred Assert with RPT bit set AND
AssertTrackingDesired(*,G,I)==TRUE
We're interested in (*,G) Asserts, either because I is a
downstream interface for which we have (*,G) forwarding state,
or because I is the upstream interface for RP(G) and we have
(*,G) forwarding state. We get a (*,G) Assert that has a
better metric than our own, so we do not win the Assert. We
transition to "I am Assert Loser" and perform actions A2
(below).
When in "I am Assert Winner" state, the following events trigger | Transitions from "I am Assert Winner" State
transitions, but only if the (S,G) assert state machine is in NoInfo |
state: |
Receive Inferior Assert | When in "I am Assert Winner" state, the following events trigger
We receive a (*,G) assert that has a worse metric than our | transitions, but only if the (S,G) assert state machine is in NoInfo
own. Whoever sent the assert has lost, and so we re-send a | state:
(*,G) Assert, and restart the timer (Action A3 below). |
Receive Preferred Assert | Receive Inferior Assert
We receive a (*,G) assert that has a better metric than our | We receive a (*,G) assert that has a worse metric than our
own. We transition to "I am Assert Loser" state and perform | own. Whoever sent the assert has lost, and so we re-send a
actions A2 (below). | (*,G) Assert, and restart the timer (Action A3 below).
When in "I am Assert Winner" state, the following events trigger | Receive Preferred Assert
transitions: | We receive a (*,G) assert that has a better metric than our
own. We transition to "I am Assert Loser" state and perform
actions A2 (below).
Timer Expires | When in "I am Assert Winner" state, the following events trigger
The (*,G) assert timer expires. As we're in the Winner state, | transitions:
then we must still have (*,G) forwarding state that is |
actively being kept alive. To prevent unnecessary thrashing |
of the forwarder and periodic flooding of duplicate packets, |
we re-send the (*,G) Assert, and restart the timer (Action A3 |
below). |
CouldAssert(*,G,I) -> FALSE | Timer Expires
Our (*,G) forwarding state or RPF interface changed so as to | The (*,G) assert timer expires. As we're in the Winner state,
make CouldAssert(*,G,I) become false. We can no longer | then we must still have (*,G) forwarding state that is
perform the actions of the assert winner, and so we transition | actively being kept alive. To prevent unnecessary thrashing
to NoInfo state and perform actions A4 (below). | of the forwarder and periodic flooding of duplicate packets,
we re-send the (*,G) Assert, and restart the timer (Action A3
below).
Transitions from Loser State | CouldAssert(*,G,I) -> FALSE
Our (*,G) forwarding state or RPF interface changed so as to
make CouldAssert(*,G,I) become false. We can no longer
perform the actions of the assert winner, and so we transition
to NoInfo state and perform actions A4 (below).
When in "I am Assert Loser" state, the following events trigger | Transitions from "I am Assert Loser" State
transitions, but only if the (S,G) assert state machine is in NoInfo |
state: |
Receive Preferred Assert | When in "I am Assert Loser" state, the following events trigger
We receive a (*,G) assert that is better than that of the | transitions, but only if the (S,G) assert state machine is in NoInfo
current assert winner. We stay in Loser state, and perform | state:
actions A2 below. |
Receive Inferior Assert from Current Winner | Receive Preferred Assert
We receive an assert from the current assert winner that is | We receive a (*,G) assert that is better than that of the
worse than our own metric for this group (typically because | current assert winner. We stay in Loser state, and perform
the winner's metric became worse). We transition to NoInfo | actions A2 below.
state, delete this (*,G) assert state, and allow the normal |
PIM Join/Prune mechanisms to operate. Usually we will |
eventually re-assert and win when data packets for G have |
started flowing again. |
When in "I am Assert Loser" state, the following events trigger | Receive Acceptable Assert from Current Winner
transitions: | We receive a (*,G) assert from the current assert winner that
is better than our own metric for this group (although the
metric may be worse than the winner's previous metric). We
stay in Loser state, and perform actions A2 below.
Timer Expires | Receive Inferior Assert from Current Winner
The (*,G) assert timer expires. We transition to NoInfo state | We receive an assert from the current assert winner that is
and delete this (*,G) assert info. | worse than our own metric for this group (typically because
the winner's metric became worse). We transition to NoInfo
state, delete this (*,G) assert state (action A5), and allow
the normal PIM Join/Prune mechanisms to operate. Usually we
will eventually re-assert and win when data packets for G have
started flowing again.
AssertTrackingDesired(*,G,I)->FALSE | When in "I am Assert Loser" state, the following events trigger
AssertTrackingDesired(*,G,I) becomes FALSE. Our forwarding | transitions:
state has changed so that (*,G) Asserts on interface I are no |
longer of interest to us. We transition to NoInfo state and |
delete this (*,G) assert info. |
My metric becomes better than the assert winner's metric | Timer Expires
My routing metric, rpt_assert_metric(G,I), has changed so that | The (*,G) assert timer expires. We transition to NoInfo state
now my assert metric for (*,G) is better than the metric we | and delete this (*,G) assert info (action A5).
have stored for current assert winner. We transition to |
NoInfo state, and delete this (*,G) assert state, and allow |
the normal PIM Join/Prune mechanisms to operate. Usually we |
will eventually re-assert and win when data packets for G have |
started flowing again. |
RPF interface changed away from interface I | AssertTrackingDesired(*,G,I)->FALSE
Interface I used to be the RPF interface for RP(G), and now it | AssertTrackingDesired(*,G,I) becomes FALSE. Our forwarding
is not. We transition to NoInfo state, and delete this (*,G) | state has changed so that (*,G) Asserts on interface I are no
assert state. | longer of interest to us. We transition to NoInfo state and
Receive Join(*,G) or Join(*,*,RP(G)) | delete this (*,G) assert info (action A5).
We receive a Join(*,G) or a Join(*,*,RP(G)) directed to my IP |
address in interface I. The action is to transition to NoInfo |
state, and delete this (*,G) assert state, and allow the |
normal PIM Join/Prune mechanisms to operate. If whoever sent |
the Join was in error, then the normal assert mechanism will |
eventually re-apply and we will lose the assert again. |
However whoever sent the assert may know that the previous |
assert winner has died, and so we may end up being the new |
forwarder. |
(*,G) Assert State-machine Actions | My metric becomes better than the assert winner's metric
My routing metric, rpt_assert_metric(G,I), has changed so that
now my assert metric for (*,G) is better than the metric we
have stored for current assert winner. We transition to
NoInfo state, and delete this (*,G) assert state (action A5),
and allow the normal PIM Join/Prune mechanisms to operate.
A1: Send Assert(*,G) | Usually we will eventually re-assert and win when data packets
Set timer to (Assert_Time - Assert_Override_Interval) | for G have started flowing again.
Store self as AssertWinner(*,G,I). |
Store rpt_assert_metric as AssertWinnerMetric(*,G,I). |
A2: Store new assert winner as AssertWinner(*,G,I) and assert | RPF_interface(RP(G)) stops being interface I
winner metric as AssertWinnerMetric(*,G,I). | Interface I used to be the RPF interface for RP(G), and now it
Set timer to assert_time is not. We transition to NoInfo state, and delete this (*,G)
assert state (action A5).
Receive Join(*,G) or Join(*,*,RP(G)) on interface I
We receive a Join(*,G) or a Join(*,*,RP(G)) that has the
Upstream Neighbor Address field set to my IP address on
interface I. The action is to transition to NoInfo state, and
delete this (*,G) assert state (action A5), and allow the
normal PIM Join/Prune mechanisms to operate. If whoever sent
the Join was in error, then the normal assert mechanism will
eventually re-apply and we will lose the assert again.
However whoever sent the assert may know that the previous
assert winner has died, and so we may end up being the new
forwarder.
(*,G) Assert State-machine Actions
A1: Send Assert(*,G)
Set timer to (Assert_Time - Assert_Override_Interval)
Store self as AssertWinner(*,G,I).
Store rpt_assert_metric as AssertWinnerMetric(*,G,I).
A2: Store new assert winner as AssertWinner(*,G,I) and assert
winner metric as AssertWinnerMetric(*,G,I).
Set timer to Assert_Time
A3: Send Assert(*,G) A3: Send Assert(*,G)
Set timer to (Assert_Time - Assert_Override_Interval) Set timer to (Assert_Time - Assert_Override_Interval)
A4: Send AssertCancel(*,G) A4: Send AssertCancel(*,G)
Delete assert info (AssertWinner(*,G,I) and | Delete assert info (AssertWinner(*,G,I) and
AssertWinnerMetric(*,G,I) assume default values). | AssertWinnerMetric(*,G,I) will then return their default
values).
A5: Delete assert info (AssertWinner(*,G,I) and | A5: Delete assert info (AssertWinner(*,G,I) and
AssertWinnerMetric(*,G,I) assume default values). | AssertWinnerMetric(*,G,I) will then return their default
values).
Note that some of these actions may cause the value of JoinDesired(*,G)
or RPF'(*,G)) to change, which could cause further transitions in other
state machines.
4.5.3. Assert Metrics 4.5.3. Assert Metrics
Assert metrics are defined as: Assert metrics are defined as:
struct assert_metric { struct assert_metric {
rpt_bit_flag; rpt_bit_flag;
metric_preference; metric_preference;
route_metric; route_metric;
ip_address; ip_address;
skipping to change at page 83, line 15 skipping to change at page 83, line 29
sourced the Assert message is used as a tie-breaker, with the highest IP sourced the Assert message is used as a tie-breaker, with the highest IP
address winning. address winning.
An assert metric for (S,G) to include in (or compare against) an Assert An assert metric for (S,G) to include in (or compare against) an Assert
message sent on interface I should be computed using the following message sent on interface I should be computed using the following
pseudocode: pseudocode:
assert_metric assert_metric
my_assert_metric(S,G,I) { my_assert_metric(S,G,I) {
if( CouldAssert(S,G,I) == TRUE ) { if( CouldAssert(S,G,I) == TRUE ) {
return spt_assert_metric(S,G,I) return spt_assert_metric(S,I)
} else if( CouldAssert(*,G,I) == TRUE ) { } else if( CouldAssert(*,G,I) == TRUE ) {
return rpt_assert_metric(G,I) return rpt_assert_metric(G,I)
} else { } else {
return infinite_assert_metric() return infinite_assert_metric()
} }
} }
spt_assert_metric(S,I) gives the assert metric we use if we're sending spt_assert_metric(S,I) gives the assert metric we use if we're sending
an assert based on active (S,G) forwarding state: an assert based on active (S,G) forwarding state:
skipping to change at page 84, line 7 skipping to change at page 84, line 20
MRIB.pref(X) and MRIB.metric(X) are the routing preference and routing MRIB.pref(X) and MRIB.metric(X) are the routing preference and routing
metrics associated with the route to a particular (unicast) destination metrics associated with the route to a particular (unicast) destination
X, as determined by the MRIB. my_ip_address(I) is simply the router's X, as determined by the MRIB. my_ip_address(I) is simply the router's
IP address that is associated with the local interface I. IP address that is associated with the local interface I.
infinite_assert_metric() gives the assert metric we need to send an infinite_assert_metric() gives the assert metric we need to send an
assert but don't match either (S,G) or (*,G) forwarding state: assert but don't match either (S,G) or (*,G) forwarding state:
assert_metric assert_metric
infinite_assert_metric() { infinite_assert_metric() {
return {1,infinity,infinity,infinity} return {1,infinity,infinity,0}
} }
4.5.4. AssertCancel Messages 4.5.4. AssertCancel Messages
An AssertCancel message is simply an RPT Assert message but with An AssertCancel message is simply an RPT Assert message but with
infinite metric. It is sent by the assert winner when it deletes the infinite metric. It is sent by the assert winner when it deletes the
forwarding state that had caused the assert to occur. Other routers forwarding state that had caused the assert to occur. Other routers
will see this metric, and it will cause any other router that has will see this metric, and it will cause any other router that has
forwarding state to send its own assert, and to take over forwarding. forwarding state to send its own assert, and to take over forwarding.
skipping to change at page 84, line 42 skipping to change at page 85, line 10
The macros lost_assert(S,G,rpt,I), lost_assert(S,G,I), and The macros lost_assert(S,G,rpt,I), lost_assert(S,G,I), and
lost_assert(*,G,I) are used in the olist computations of Section 4.1, lost_assert(*,G,I) are used in the olist computations of Section 4.1,
and are defined as: and are defined as:
bool lost_assert(S,G,rpt,I) { bool lost_assert(S,G,rpt,I) {
if ( RPF_interface(RP) == I OR if ( RPF_interface(RP) == I OR
( RPF_interface(S) == I AND SPTbit(S,G) == TRUE ) ) { ( RPF_interface(S) == I AND SPTbit(S,G) == TRUE ) ) {
return FALSE return FALSE
} else { } else {
return ( AssertWinner(S,G,I) != NULL AND | return ( AssertWinner(S,G,I) != NULL AND
AssertWinner(S,G,I) != me ) | AssertWinner(S,G,I) != me )
} | }
} | }
bool lost_assert(S,G,I) { bool lost_assert(S,G,I) {
if ( RPF_interface(S) == I ) { if ( RPF_interface(S) == I ) {
return FALSE return FALSE
} else { } else {
return ( AssertWinner(S,G,I) != NULL AND | return ( AssertWinner(S,G,I) != NULL AND
AssertWinner(S,G,I) != me AND | AssertWinner(S,G,I) != me AND
(AssertWinnerMetric(S,G,I) is better | (AssertWinnerMetric(S,G,I) is better
than spt_assert_metric(S,G,I) ) | than spt_assert_metric(S,I) )
} | }
} | }
Note: the term "AssertWinnerMetric(S,G,I) is better than
spt_assert_metric(S,I)" is required to correctly handle the transition
phase when a router has (S,G) join state, but has not yet set the SPT
bit. In this case it needs to ignore the assert state if it will win
the assert once the SPT bit is set.
bool lost_assert(*,G,I) { bool lost_assert(*,G,I) {
if ( RPF_interface(RP) == I ) { if ( RPF_interface(RP) == I ) {
return FALSE return FALSE
} else { } else {
return ( AssertWinner(*,G,I) != NULL AND | return ( AssertWinner(*,G,I) != NULL AND
AssertWinner(*,G,I) != me ) | AssertWinner(*,G,I) != me )
} | }
} | }
AssertWinner(S,G,I) is the IP source address of the Assert(S,G) packet AssertWinner(S,G,I) is the IP source address of the Assert(S,G) packet
that won an Assert. that won an Assert.
AssertWinner(S,G,I) is the IP source address of the Assert(*,G) packet AssertWinner(*,G,I) is the IP source address of the Assert(*,G) packet
that won an Assert. that won an Assert.
AssertWinnerMetric(S,G,I) is the Assert metric of the Assert(S,G) packet AssertWinnerMetric(S,G,I) is the Assert metric of the Assert(S,G) packet
tht won an Assert. that won an Assert.
AssertWinnerMetric(*,G,I) is the Assert metric of the Assert(*,G) packet AssertWinnerMetric(*,G,I) is the Assert metric of the Assert(*,G) packet
ht won an Assert. that won an Assert.
AssertWinner(S,G,I) defaults to Null and AssertWinnerMetric(S,G,I) AssertWinner(S,G,I) defaults to Null and AssertWinnerMetric(S,G,I)
defaults to Infinity when in the NoInfo state. defaults to Infinity when in the NoInfo state.
Rationale for Assert Rules Summary of Assert Rules and Rationale
The following is a summary of the rules for sending and reacting to This section summarizes the key rules for sending and reacting to
asserts. It is not intended to be definitive (the state machines and asserts and the rationale for these rules. This section is not intended
pseudocode provide the definitive behavior). Instead it provides some to be and should not be treated as a definitive specification of
rationale for the behavior. protocol behavior. The state machines and pseudocode should be
consulted for that purpose. Rather, this section is intended to
document important aspects of a the Assert protocol behavior and to
provide information that may prove helpful to the reader in
understanding and implementing this part of the protocol.
1. Downstream neighbors send Join(*,G) and Join(S,G) periodic messages 1. Behavior: Downstream neighbors send Join(*,G) and Join(S,G)
to the appropriate RPF' neighbor, i.e., the RPF neighbor as periodic messages to the appropriate RPF' neighbor, i.e., the RPF
modified by the assert process. Normal suppression and override neighbor as modified by the assert process. They are not always
rules apply. sent to the RPF neighbor as indicated by the MRIB. Normal
suppression and override rules apply.
This guarantees that all requested traffic will continue to arrive. Rationale: By sending the periodic and triggered Join messages to
This doesn't allow switching back to the "normal" RPF neighbor the RPF' neighbor instead of to the RPF neighbor, the downstream
until the assert times out, which it won't while data is flowing if router avoids re-triggering the Assert process with every Join. A
we are implementing rule 8. side effect of sending Joins to the Assert winner is that traffic
will not switch back to the "normal" RPF neighbor until the Assert
times out. This will not happen until data stops flowing, if item
8 below is implemented.
2. The assert winner for (*,G) acts as the local DR for (*,G) on 2. Behavior: The assert winner for (*,G) acts as the local DR for
behalf of IGMP members. (*,G) on behalf of IGMP/MLD members.
This is required to allow a single router to merge PIM and IGMP Rationale: This is required to allow a single router to merge PIM
joins and leaves. Without this, overrides don't work. and IGMP/MLD joins and leaves. Without this, overrides don't work.
3. The assert winner for (S,G) must act as the local DR for (S,G) on 3. Behavior: The assert winner for (S,G) acts as the local DR for
behalf of IGMPv3 members. (S,G) on behalf of IGMPv3 members.
Same rationale as (2) Rationale: Same rationale as for 2.
4. (S,G) and (*,G) prune overrides are sent to the RPF' neighbor and 4. Behavior: (S,G) and (*,G) prune overrides are sent to the RPF'
not to the regular RPF neighbor. neighbor and not to the regular RPF neighbor.
Same rationale as (1). Rationale: Same as for 1.
5. An (S,G,rpt) prune override is not sent (at all) if RPF'(S,G,rpt) 5. Behavior: An (S,G,rpt) prune override is not sent (at all) if
!= RPF'(*,G). RPF'(S,G,rpt) != RPF'(*,G).
This avoids keeping state alive on (S,G) tree when only (*,G) Rationale: This avoids keeping state alive on the (S,G) tree when
downstream members are left. Also, it avoids sending (S,G,rpt) only (*,G) downstream members are left. Also, it avoids sending
joins to a router that is not on the (*,G) tree. This might be (S,G,rpt) joins to a router that is not on the (*,G) tree. This
confusing and could be interpreted as being undefined although behavior might be confusing although this specification does
technically the current spec says to drop such a join. indicate that such a join should be dropped.
6. An assert loser that receives a Join(S,G) directed to it cancels 6. Behavior: An assert loser that receives a Join(S,G) with an
the (S,G) assert timer. Upstream Neighbor Address that is one of its addresses on that
interface cancels the (S,G) assert timer.
7. An assert loser that receives a Join(*,G) or a Join(*,*,RP(G)) Rationale: This is necessary in order to have rapid convergence in
directed to it cancels the (*,G) assert timer and all (S,G) assert the event that the downstream router that initially sent a join to
timers that do not have corresponding Prune(S,G,rpt) messages in the prior Assert winner has undergone a topology change.
the compound Join/Prune message.
Rules 7 and 8 help convergence during topology changes. 7. Behavior: An assert loser that receives a Join(*,G) or a
Join(*,*,RP(G)) with an Upstream Neighbor Address that is one of
its addresses on that interface cancels the (*,G) assert timer and
all (S,G) assert timers that do not have corresponding
Prune(S,G,rpt) messages in the compound Join/Prune message.
8. An assert winner for (*,G) or (S,G) sends a canceling assert when Rationale: Same as 6.
it is about to stop forwarding on a (*,G) or an (S,G) entry. This
rule does not apply to (S,G,rpt).
This allow switching back to the shared tree after the last SPT 8. Behavior: An assert winner for (*,G) or (S,G) sends a canceling
router on the lan leaves. We don't want RPT downstream routers to assert when it is about to stop forwarding on a (*,G) or an (S,G)
keep SPT state alive. entry. This behavior does not apply to (S,G,rpt).
9. [Optionally] re-assert before timing out. Rationale: This allows switching back to the shared tree after the
last SPT router on the LAN leaves. Doing this prevents downstream
routers on the shared tree from keeping SPT state alive.
This prevents periodic duplicates. 9. Behavior: Re-send the assert messages before timing out an assert.
(This behavior is optional.)
10. When RPF'(S,G,rpt) changes to be the same as RPF'(*,G) we need to | Rationale: This prevents the periodic duplicates that would
trigger a Join(S,G,rpt) to MRIB.next_hop(RP(G)). | otherwise occur each time that an assert times out and is then re-
established.
This allows switching back to the RPT after the last SPT member 10. Behavior: When RPF'(S,G,rpt) changes to be the same as RPF'(*,G) we
leaves. need to trigger a Join(S,G,rpt) to MRIB.next_hop(RP(G)).
Rationale: This allows switching back to the RPT after the last SPT
member leaves.
4.6. Designated Routers (DR) and Hello Messages 4.6. Designated Routers (DR) and Hello Messages
4.6.1. Sending Hello Messages 4.6.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 interface.
They allow a router to learn about the neighboring PIM routers on each | They allow a router to learn about the neighboring PIM routers on each
interface. Hello messages are also the mechanism used to elect a | interface. Hello messages are also the mechanism used to elect a
Designated Router (DR), and to negotiate additional capabilities A | Designated Router (DR), and to negotiate additional capabilities A
router must record the Hello information received from each PIM | router must record the Hello information received from each PIM
neighbor. | neighbor.
Hello messages must be sent on all active interfaces, including physical | Hello messages must be sent on all active interfaces, including physical
point-to-point links, and are multicast to address 224.0.0.13 (the ALL- | point-to-point links, and are multicast to address 224.0.0.13 (the ALL-
PIM-ROUTERS group). | PIM-ROUTERS group).
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 interface
or a router first starts, the hello timer of that interface is set to a | or a router first starts, the hello timer of that interface is set to a
random value between 0 and Triggered_Hello_Delay. This prevents | random value between 0 and Triggered_Hello_Delay. This prevents
synchronization of Hello messages if multiple routers are powered on | synchronization of Hello messages if multiple routers are powered on
simultaneously. After the initial randomized interval, Hello messages | simultaneously. After the initial randomized interval, Hello messages
must be sent every Hello_Period seconds. The hello timer should not be | must be sent every Hello_Period seconds. The hello timer should not be
reset except when it expires. | reset except when it expires.
The DR_Election_Priority Option allows a network administrator to give | The DR_Election_Priority Option allows a network administrator to give
preference to a particular router in the DR election process by giving preference to a particular router in the DR election process by giving
it a numerically larger DR Election Priority. The DR_Election_Priority | it a numerically larger DR Election Priority. The DR_Election_Priority
Option SHOULD be included in every Hello message, even if no DR election | Option SHOULD be included in every Hello message, even if no DR election
priority is explicitly configured on that interface. This is necessary priority is explicitly configured on that interface. This is necessary
because priority-based DR election is only enabled when all neighbors on because priority-based DR election is only enabled when all neighbors on
an interface advertise that they are capable of using the DR Election an interface advertise that they are capable of using the DR Election
Priority Option. The default priority is 1. Priority 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 Hello
messages. The GenID option contains a randomly generated 32-bit value | messages. The GenID option contains a randomly generated 32-bit value
that is regenerated each time PIM forwarding is started or restarted on that is regenerated each time PIM forwarding is started or restarted on
the interface, including when the router itself restarts. When a Hello the interface, including when the router itself restarts. When a Hello
message with a new GenID is received from a neighbor, any old Hello message with a new GenID is received from a neighbor, any old Hello
information about that neighbor SHOULD be discarded and superseded by information about that neighbor SHOULD be discarded and superseded by
the information from the new Hello message. This may cause a new DR to the information from the new Hello message. This may cause a new DR to
be chosen on that interface. | 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 sent
on multi-access LANs. This option advertises a router's capability to | on multi-access LANs. This option advertises a router's capability to
use values other than the default for the Propagation Delay and Override | use values other than the default for the Propagation_Delay and
Interval which affect the setting of the Prune Pending, Upstream Join | Override_Interval which affect the setting of the Prune Pending,
and Override timers (defined in section 4.10). | Upstream Join and Override Timers (defined in section 4.11).
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 message
with a new GenID is received from an existing neighbor, a new Hello with a new GenID is received from an existing neighbor, a new Hello
message should be sent on this interface after a randomized delay message should be sent on this interface after a randomized delay
between 0 and Triggered_Hello_Delay. This triggered message need not between 0 and Triggered_Hello_Delay. This triggered message need not
change the timing of the scheduled periodic message. change the timing of the scheduled periodic message.
When an interface goes down or changes IP address, a Hello message with When an interface goes down or changes IP address, a Hello message with
a zero Hold Time should be sent immediately (with the old IP address if a zero Hold Time should be sent immediately (with the old IP address if
skipping to change at page 89, line 7 skipping to change at page 89, line 41
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 to time out the neighbor state when it becomes stale. A timer to time out the neighbor state when it becomes stale.
This is reset to Hello Holdtime whenever a Hello message is This is reset to Hello_Holdtime (from the Hello Holdtime
received, or to the value specified in the message, if the option) whenever a Hello message is received containing a
hold time option is used. Holdtime option, or to Default_Hello_Holdtime if the Hello
message does not contain 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 ) {
skipping to change at page 90, line 5 skipping to change at page 90, line 38
} }
The DR election priority is a 32-bit unsigned number and the numerically The DR election priority is a 32-bit unsigned number and the numerically
larger priority is always preferred. A router's idea of the current DR larger priority is always preferred. A router's idea of the current DR
on an interface can change when a PIM-Hello message is received, when a on an interface can change when a PIM-Hello message is received, when a
neighbor times out, or when a router's own DR priority changes. If the neighbor times out, or when a router's own DR priority changes. If the
router becomes the DR or ceases to be the DR, this will normally cause router becomes the DR or ceases to be the DR, this will normally cause
the DR Register state-machine to change state. Subsequent actions are the DR Register state-machine to change state. Subsequent actions are
determined by that state-machine. determined by that state-machine.
4.6.3. Reducing Prune Propagation Delay on LANs | 4.6.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 Delay
Hello option: | 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.lan_delay | neighbor.lan_delay
The LAN Delay field of the LAN Prune Delay option (if present) | The LAN Delay field of the LAN Prune Delay option (if present)
in the Hello message. | 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 advertise
the option. The function below computes this state: | 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 LAN Delay inserted by a router in the LAN Prune Delay option | The LAN Delay inserted by a router in the LAN Prune Delay option
expresses the expected message propagation delay on the link and should | expresses the expected message propagation delay on the link and should
be configurable by the system administrator. It is used by upstream | be configurable by the system administrator. It is used by upstream
routers to figure out how long they should wait for a Join override | routers to figure out how long they should wait for a Join override
message before pruning an interface. | message before pruning an interface.
PIM implementors should enforce a lower bound on the permitted values | PIM implementors 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 processed
later as well as triggered messages to be sent later than intended. | later as well as triggered messages to be sent later than intended.
Setting this LAN Prune Delay to too low a value may result in temporary | Setting this LAN Prune Delay to too low a value may result in temporary
forwarding outages because a downstream router will not be able to | forwarding outages because a downstream router will not be able to
override a neighbors prune messages before the upstream neighbor stops | override a neighbor's Prune message before the upstream neighbor stops
forwarding. | 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 different
than default Propagation Delay, the largest value from those advertised | than default Propagation Delay, the largest value from those advertised
by each neighbor is chosen. The function for computing the Propagation | by each neighbor is chosen. The function for computing the Propagation
Delay of interface I is: | Delay of interface I is:
int | time_interval
Propagation_Delay(I) { | Propagation_Delay(I) {
if ( lan_delay_enabled(I) == false ) { | if ( lan_delay_enabled(I) == false ) {
return LAN_delay_default | return LAN_delay_default
} | }
delay = 0 | delay = 0
for each neighbor on interface I { | for each neighbor on interface I {
if ( neighbor.lan_delay > delay ) { | if ( neighbor.lan_delay > delay ) {
delay = neighbor.lan_delay | delay = neighbor.lan_delay
} | }
} | }
return delay | return delay
} | }
To avoid synchronisation of override messages when multiple downstream | To avoid synchronisation of override messages when multiple downstream
routers share a multi-access link, sending of such messages is delayed | routers share a multi-access link, sending of such messages is delayed
by a small random amount of time. The period of randomisation should | by a small random amount of time. The period of randomisation should
represent the size of the PIM router poppulation on the link. Each | represent the size of the PIM router poppulation on the link. Each
router expresses its view of the amount of randomisation necessary in | router expresses its view of the amount of randomisation necessary in
the Override Delay field of the LAN Prune Delay option. | the Override Delay 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 a different
than default Override Delay, the largest value from those advertised by | than default Override Delay, the largest value from those advertised by
each neighbor is chosen. The function for computing the Override | each neighbor is chosen. The function for computing the Override
Interval of interface I is: | Interval of interface I is:
int |
Override_Interval(I) { |
if ( lan_delay_enabled(I) == false ) { |
return t_override_default |
} |
delay = 0 |
for each neighbor on interface I { |
if ( neighbor.override_interval > delay ) { |
delay = neighbor.override_interval |
} |
} |
return delay |
} |
Although the mechanisms are not specified in this document, it is | time_interval
possible for upstream routers to explicitly track the join membership of | Override_Interval(I) {
individual downstream routers if Join suppression is disabled. A router | if ( lan_delay_enabled(I) == false ) {
can advertise its willingness to disable Join suppression by using the T | return t_override_default
bit in the LAN Prune Delay Hello option. Unless all PIM routers on a | }
link negotiate this capability, explicit tracking and the disabling of | delay = 0
the Join suppression mechanism are not possible. The function for | for each neighbor on interface I {
computing the state of Suppression on interface I is: | if ( neighbor.override_interval > delay ) {
delay = neighbor.override_interval
}
}
return delay
}
state | Although the mechanisms are not specified in this document, it is
Suppression_State(I) { | possible for upstream routers to explicitly track the join membership of
if ( lan_delay_enabled(I) == false ) { | individual downstream routers if Join suppression is disabled. A router
return enabled | can advertise its willingness to disable Join suppression by using the T
} | bit in the LAN Prune Delay Hello option. Unless all PIM routers on a
for each neighbor on interface I { | link negotiate this capability, explicit tracking and the disabling of
if ( neighbor.tracking_support == false ) { |
return enabled |
} |
} |
return disabled |
} |
Note that the setting of Suppression_State(I) affects the value of | the Join suppression mechanism are not possible. The function for
t_suppressed (see section 4.10). | computing the state of Suppression on interface I is:
4.7. PIM Bootstrap and RP Discovery bool
Suppression_Enabled(I) {
if ( lan_delay_enabled(I) == false ) {
return true
}
for each neighbor on interface I {
if ( neighbor.tracking_support == false ) {
return true
}
}
return false
}
Note that the setting of Suppression_Enabled(I) affects the value of
t_suppressed (see section 4.11).
4.7. PIM Multicast Border Router Behavior
In some cases PIM-SM domains will interconnect with non-PIM domains. In
these cases, the border routers of the PIM domain speak PIM-SM on some
interfaces and speak other multicast routing protocols on other
interfaces. Such routers are termed PIM Multicast Border Routers or
PMBRs. In general, RFC 2715 [13] provides rules for interoperability
between different multicast routing protocols. In this section we
specify how PBMRs differ from regular PIM-SM routers.
From the point of view of PIM-SM, a PMBR has two tasks:
o To ensure that traffic from sources outside the PIM-SM domain reaches
receivers inside the domain.
o To ensure that traffic from sources inside the PIM-SM domain reaches
receives outside the domain.
We note that multiple PIM-SM domains are sometimes conencted together
using protocols such as MSDP, which provides information about active
external sources, but does not follow RFC 2715. In such cases the
domains are not connected via PMBRs because Join(S,G) messages traverse
the border between domains. A PMBR is required when no PIM messages can
traverse the border; typically this is because the routing protocol in
the neighboring domain is not PIM-SM.
4.7.1. Sources External to the PIM-SM Domain
A PMBR needs to ensure that traffic from multicast sources external to
the PIM-SM domain reaches receivers inside the domain. The PBMR will
follow the rules in RFC 2715, such that traffic from external sources
reaches the PBMR itself.
According to RFC 2715, the PIM-SM component of the PMBR will receive an
(S,G) Creation event when data from an (S,G) data packet from an
external source first reaches the PMBR. If RPF_interface(S) is not an
inteface in the PIM-SM domain, the packet cannot be originated into the
PIM domain at this router, and the PIM-SM component of the PMBR will not
process the packet. Otherwise the PMBR will then act exactly as if it
were the DR for this source (see section 4.3.1 with the following
modifications:
o The Border-bit is set in all PIM Register message sent for these
sources.
o DirectlyConnected(S) is treated as being TRUE for these sources.
o The PIM-SM forwarding rule "iif == RPF_interface(S)" is relaxed to be
TRUE if iif is any interface that is not part of the PIM-SM component
of the PMBR (see section 4.2).
4.7.2. Sources Internal to the PIM-SM Domain
A PMBR needs to ensure that traffic from sources inside the PIM-SM
domain reaches receivers outside the domain. Using terminology from RFC
2715, there are two possible scenarios for this:
o Another component of the PMBR is a wildcard receiver. In this case
the PIM-SM component of the PMBR must ensure that traffic from all
internal sources reaches the PMBR until it is informed otherwise.
o No other component of the PMBR is a wildcard receiver. In this case
the PMBR will receive explicit information as to which groups or
(source,group) pairs the external domains wish to receive.
In the former case, the PBMR will need to issue send a Join(*,*,RP) to
all the RPs in the PIM-SM domain. This will cause all traffic in the
domain to reach the PMBR. The PMBR may then act as if it were a DR with
directly connected receivers, and trigger the transition to a shortest
path tree (see section 4.2.1).
In the latter case, the PMBR will not need to send Join(*,*,RP)
messages. However the PMBR will still need to act as a DR with directly
connected receivers on behalf of the external receivers in terms of
being able to switch to the shortest-path tree for internally-reached
sources.
According to RFC 2715, the PIM-SM component of the PMBR may receive a
number of alerts generated by events in the external routing components.
To implement the above behavior, one reasonable way to map these alerts
into PIM-SM state as follows:
o When a PIM-SM component receives an (S,G) Prune alert, it sets
local_receiver_include(S,G,I) to FALSE for the discard interface.
o When a PIM-SM component receives a (*,G) Prune alert, it sets
local_receiver_include(*,G,I) to FALSE for the discard interface.
o When a PIM-SM component receives an (S,G) Join alert, it sets
local_receiver_include(S,G,I) to TRUE for the discard interface.
o When a PIM-SM component receives a (*,G) Join alert, it sets
local_receiver_include(*,G,I) to TRUE for the discard interface.
o When a PIM-SM component receives a (*,*) Join alert, it sets
DownstreamJPState(*,*,RP,I) to Join state on the discard interface for
all RPs in the PIM-SM domain.
o When a PIM-SM component receives a (*,*) Prune alert, then it sets
DownstreamJPState(*,*,RP,I) to NoInfo state on the discard interface
for all RPs in the PIM-SM domain.
We refer above to the discard interface because the macros and state-
machines are interface-specific, but we need to have PIM state that is
not associated with any actual PIM-SM interface. Implementors are free
to implement this in any reasonable manner.
Note that these state changes will then cause additional PIM-SM state
machine transitions in the normal way.
4.8. PIM Bootstrap and RP Discovery
For correct operation, every PIM router within a PIM domain must be able For correct operation, every PIM router within a PIM domain must be able
to map a particular multicast group address to the same RP. If this is to map a particular multicast group address to the same RP. If this is
not the case then black holes may appear, where some receivers in the not the case then black holes may appear, where some receivers in the
domain cannot receive some groups. A domain in this context is a domain cannot receive some groups. A domain in this context is a
contiguous set of routers that all implement PIM and are configured to contiguous set of routers that all implement PIM and are configured to
operate within a common boundary defined by PIM Multicast Border Routers operate within a common boundary defined by PIM Multicast Border Routers
(PMBRs). PMBRs connect each PIM domain to the rest of the Internet. (PMBRs). PMBRs connect each PIM domain to the rest of the Internet.
A notable exception to this is where a PIM domain is broken up into A notable exception to this is where a PIM domain is broken up into
multiple administrative scope regions - these are regions where a border multiple administrative scope regions - these are regions where a border
has been configured so that a range of multicast groups will not be has been configured so that a range of multicast groups will not be
forwarded across that border. For more information on Administratively forwarded across that border. For more information on Administratively
Scoped IP Multicast, see RFC 2365. The modified criteria for admin- Scoped IP Multicast, see RFC 2365. The modified criteria for admin-
scoped regions are that the region is convex with respect to forwarding scoped regions are that the region is convex with respect to forwarding
based on the MRIB, and that all PIM routers within the scope region map based on the MRIB, and that all PIM routers within the scope region map
scoped groups to the same RP within that region. scoped groups to the same RP within that region.
skipping to change at page 94, line 5 skipping to change at page 97, line 5
As far as PIM-SM is concerned, the only important requirement is that As far as PIM-SM is concerned, the only important requirement is that
all routers in the domain (or admin scope zone for scoped regions) all routers in the domain (or admin scope zone for scoped regions)
receive the same set of group-range-to-RP mappings. This may be receive the same set of group-range-to-RP mappings. This may be
achieved through the use of any of these mechansms, or through achieved through the use of any of these mechansms, or through
alternative mechanisms not currently specified. alternative mechanisms not currently specified.
Any RP address configured or learned MUST be a domain-wide reachable Any RP address configured or learned MUST be a domain-wide reachable
address. address.
4.7.1. Group-to-RP Mapping 4.8.1. Group-to-RP Mapping
Using one of the mechanisms described above, a PIM router receives one Using one of the mechanisms described above, a PIM router receives one
or more possible group-range-to-RP mappings. Each mapping specifies a or more possible group-range-to-RP mappings. Each mapping specifies a
range of multicast groups (expressed as a group and mask) and the RP to range of multicast groups (expressed as a group and mask) and the RP to
which such groups should be mapped. Each mapping may also have an which such groups should be mapped. Each mapping may also have an
associated priority. It is possible to receive multiple mappings all of associated priority. It is possible to receive multiple mappings all of
which might match the same multicast group - this is the common case which might match the same multicast group - this is the common case
with BSR. The algorithm for performing the group-to-RP mapping is as with BSR. The algorithm for performing the group-to-RP mapping is as
follows: follows:
skipping to change at page 94, line 31 skipping to change at page 97, line 31
3 If only one RP remains in the list, use that RP. 3 If only one RP remains in the list, use that RP.
4 If multiple RPs are in the list, use the PIM hash function to 4 If multiple RPs are in the list, use the PIM hash function to
choose one. choose one.
Thus if two or more group-range-to-RP mappings cover a particular group, Thus if two or more group-range-to-RP mappings cover a particular group,
the one with the longest mask is the mapping to use. If the mappings the one with the longest mask is the mapping to use. If the mappings
have the same mask length, then the one with the highest priority is have the same mask length, then the one with the highest priority is
chosen. If there is more than one matching entry with the same longest chosen. If there is more than one matching entry with the same longest
mask and the priorities are identical, then a hash function (see Section mask and the priorities are identical, then a hash function (see Section
4.7.2) is applied to choose the RP. 4.8.2) is applied to choose the RP.
This algorithm is invoked by a DR when it needs to determine an RP for a This algorithm is invoked by a DR when it needs to determine an RP for a
given group, e.g. upon reception of a packet or IGMP membership given group, e.g. upon reception of a packet or IGMP/MLD membership
indication for a group for which the DR does not know the RP. It is indication for a group for which the DR does not know the RP. It is
invoked by any router that has (*,*,RP) state when a packet is received invoked by any router that has (*,*,RP) state when a packet is received
for which there is no corresponding (S,G) or (*,G) entry. Furthermore, for which there is no corresponding (S,G) or (*,G) entry. Furthermore,
the mapping function is invoked by all routers upon receiving a (*,G) or the mapping function is invoked by all routers upon receiving a (*,G) or
(*,*,RP) Join/Prune message. (*,*,RP) Join/Prune message.
Note that if the set of possible group-range-to-RP mappings changes, Note that if the set of possible group-range-to-RP mappings changes,
each router will need to check whether any existing groups are affected. each router will need to check whether any existing groups are affected.
This may, for example, cause a DR or acting DR to re-join a group, or This may, for example, cause a DR or acting DR to re-join a group, or
cause it to re-start register encapsulation to the new RP. cause it to re-start register encapsulation to the new RP.
4.7.2. Hash Function 4.8.2. Hash Function
The hash function is used by all routers within a domain, to map a group The hash function is used by all routers within a domain, to map a group
to one of the RPs from the matching set of group-range-to-RP mappings to one of the RPs from the matching set of group-range-to-RP mappings
(this set all have the same longest mask length and same highest (this set all have the same longest mask length and same highest
priority). The algorithm takes as input the group address, and the priority). The algorithm takes as input the group address, and the
addresses of the candidate RPs from the mappings, and gives as output addresses of the candidate RPs from the mappings, and gives as output
one RP address to be used. one RP address to be used.
The protocol requires that all routers hash to the same RP within a The protocol requires that all routers hash to the same RP within a
domain (except for transients). The following hash function must be used domain (except for transients). The following hash function must be used
in each router: in each router:
1 For RP addresses in the matching group-range-to-RP mappings, 1 For RP addresses in the matching group-range-to-RP mappings,
compute a value: compute a value:
Value(G,M,C(i))= Value(G,M,C(i))=
(1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31 (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31
where C(i) is the RP address and M is a hash-mask included in where C(i) is the RP address and M is a hash-mask. If BSR is being
Bootstrap messages. The hash-mask allows a small number of used, the hash-mask is given in the Bootstrap messages. If BSR is
consecutive groups (e.g., 4) to always hash to the same RP. For not being used, the alternative mechanism that supplies the group-
instance, hierarchically-encoded data can be sent on consecutive range-to-RP mappings may supply the value, or else it defaults to a
group addresses to get the same delay and fate-sharing mask with the most significant 30 bits being one for IPv4 and the
characteristics. most significant 126 bits being one for IPv6. The hash-mask allows
a small number of consecutive groups (e.g., 4) to always hash to
the same RP. For instance, hierarchically-encoded data can be sent
on consecutive group addresses to get the same delay and fate-
sharing characteristics.
For address families other than IPv4, a 32-bit digest to be used as For address families other than IPv4, a 32-bit digest to be used as
C(i) and G must first be derived from the actual RP or group C(i) and G must first be derived from the actual RP or group
address. Such a digest method must be used consistently throughout address. Such a digest method must be used consistently throughout
the PIM domain. For IPv6 addresses, we recommend using the the PIM domain. For IPv6 addresses, we recommend using the
equivalent IPv4 address for an IPv4-compatible address, and the equivalent IPv4 address for an IPv4-compatible address, and the
exclusive-or of each 32-bit segment of the address for all other exclusive-or of each 32-bit segment of the address for all other
IPv6 addresses. For example, the digest of the IPv6 address IPv6 addresses. For example, the digest of the IPv6 address
3ffe:b00:c18:1::10 would be computed as 0x3ffe0b00 ^ 0x0c180001 ^ 3ffe:b00:c18:1::10 would be computed as 0x3ffe0b00 ^ 0x0c180001 ^
0x00000000 ^ 0x00000010, where ^ represents the exclusive-or 0x00000000 ^ 0x00000010, where ^ represents the exclusive-or
operation. operation.
2 The candidate RP with the highest resulting hash value is then 2 The candidate RP with the highest resulting hash value is then the
chosen as the RP for that group, and its identity and hash value RP chosen by this Hash Function. If more than one RP has the same
are stored with the entry created. highest hash value, the RP with the highest IP address is chosen.
Ties between RPs having the same hash value are broken in advantage
of the highest address.
4.8. Source-Specific Multicast 4.9. Source-Specific Multicast
The Source-Specific Multicast (SSM) service model [10] can be The Source-Specific Multicast (SSM) service model [10] can be
implemented with a strict subset of the PIM-SM protocol mechanisms. implemented with a strict subset of the PIM-SM protocol mechanisms.
Both regular IP Multicast and SSM semantics can coexist on a single Both regular IP Multicast and SSM semantics can coexist on a single
router and both can be implemented using the PIM-SM protocol. A range router and both can be implemented using the PIM-SM protocol. A range
of multicast addresses, currently 232.0.0.0/8 in IPv4, is reserved for of multicast addresses, currently 232.0.0.0/8 in IPv4, is reserved for
SSM, and the choice of semantics is determined by the multicast group
SSM, and the choice of semantics is determined by the multicast group
address in both data packets and PIM messages. address in both data packets and PIM messages.
4.8.1. Protocol Modifications for SSM destination addresses 4.9.1. Protocol Modifications for SSM destination addresses
The following rules override the normal PIM-SM behavior for a multicast The following rules override the normal PIM-SM behavior for a multicast
address G in the SSM reserved range: address G in the SSM reserved range:
o A router MUST NOT send a (*,G) Join/Prune message for any reason. o A router MUST NOT send a (*,G) Join/Prune message for any reason.
o A router MUST NOT send an (S,G,rpt) Join/Prune message for any reason. o A router MUST NOT send an (S,G,rpt) Join/Prune message for any reason.
o A router MUST NOT send a Register message for any packet that is o A router MUST NOT send a Register message for any packet that is
destined to an SSM address. destined to an SSM address.
skipping to change at page 96, line 33 skipping to change at page 99, line 34
o A router acting as an RP MUST NOT forward any Register-encapsulated o A router acting as an RP MUST NOT forward any Register-encapsulated
packet that has an SSM destination address. packet that has an SSM destination address.
The last two rules are present to deal with "legacy" routers unaware of The last two rules are present to deal with "legacy" routers unaware of
SSM that may be sending (*,G) and (S,G,rpt) Join/Prunes, or Register SSM that may be sending (*,G) and (S,G,rpt) Join/Prunes, or Register
messages for SSM destination addresses. messages for SSM destination addresses.
Additionally: Additionally:
o A router MAY be configured to advertise itself as a Candidate RP for o A router MAY be configured to advertise itself as a Candidate RP for
an SSM address. If so, it SHOULD respond with a Register-Stop message an SSM address. If so, it SHOULD respond with a RegisterStop message
to any Register message containing a packet destined for an SSM to any Register message containing a packet destined for an SSM
address. address.
o A router MAY optimize out the creation and maintenance of (S,G,rpt) o A router MAY optimize out the creation and maintenance of (S,G,rpt)
and (*,G) state for SSM destination addresses -- this state is not and (*,G) state for SSM destination addresses -- this state is not
needed for SSM packets. needed for SSM packets.
4.8.2. PIM-SSM-only Routers 4.9.2. PIM-SSM-only Routers
An implementor may choose to implement only the subset of PIM Sparse- An implementor may choose to implement only the subset of PIM Sparse-
Mode that provides SSM forwarding semantics. Mode that provides SSM forwarding semantics.
A PIM-SSM-only router MUST implement the following portions of this A PIM-SSM-only router MUST implement the following portions of this
specification: specification:
o Upstream (S,G) state machine (Section 4.4.7) o Upstream (S,G) state machine (Section 4.4.7)
o Downstream (S,G) state machine (Section 4.4.3) o Downstream (S,G) state machine (Section 4.4.3)
skipping to change at page 97, line 26 skipping to change at page 100, line 26
o Register state machine (Section 4.3) o Register state machine (Section 4.3)
o (*,G), (S,G,rpt) and (*,*,RP) Downstream state machines (Sections o (*,G), (S,G,rpt) and (*,*,RP) Downstream state machines (Sections
4.4.2, 4.4.4, and 4.4.1) 4.4.2, 4.4.4, and 4.4.1)
o (*,G), (S,G,rpt), and (*,*,RP) Upstream state machines (Sections o (*,G), (S,G,rpt), and (*,*,RP) Upstream state machines (Sections
4.4.6, 4.4.8, and 4.4.5) 4.4.6, 4.4.8, and 4.4.5)
o (*,G) Assert state machine (Section 4.5.2) o (*,G) Assert state machine (Section 4.5.2)
o Bootstrap RP Election (Section 4.7) o Bootstrap RP Election (Section 4.8)
o Keepalive Timer o Keepalive Timer
o SptBit (Section 4.2.2) o SptBit (Section 4.2.2)
The KeepaliveTimer should be treated as always running and SptBit should The KeepaliveTimer should be treated as always running and SptBit should
be treated as being always set for an SSM address. Additionally, the be treated as being always set for an SSM address. Additionally, the
Packet forwarding rules of Section 4.2 can be simplified in a PIM-SSM- Packet forwarding rules of Section 4.2 can be simplified in a PIM-SSM-
only router: only router:
skipping to change at page 98, line 5 skipping to change at page 101, line 5
} else if( iif is in inherited_olist(S,G) ) { } else if( iif is in inherited_olist(S,G) ) {
send Assert(S,G) on iif send Assert(S,G) on iif
} }
oiflist = oiflist (-) iif oiflist = oiflist (-) iif
forward packet on all interfaces in oiflist forward packet on all interfaces in oiflist
This is nothing more than the reduction of the normal PIM-SM forwarding This is nothing more than the reduction of the normal PIM-SM forwarding
rule, with all (S,G,rpt) and (*,G) clauses replaced with NULL. rule, with all (S,G,rpt) and (*,G) clauses replaced with NULL.
4.9. PIM Packet Formats 4.10. PIM Packet Formats
This section describes the details of the packet formats for PIM control This section describes the details of the packet formats for PIM control
messages. messages.
All PIM control messages have IP protocol number 103. All PIM control messages have IP protocol number 103.
PIM messages are either unicast (e.g. Registers and Register-Stop), or PIM messages are either unicast (e.g. Registers and RegisterStop), or
multicast with TTL 1 to the `ALL-PIM-ROUTERS' group (e.g. Join/Prune, multicast with TTL 1 to the `ALL-PIM-ROUTERS' group (e.g. Join/Prune,
Asserts, etc.). The source address used for unicast messages is a Asserts, etc.). The source address used for unicast messages is a
domain-wide reachable address; the source address used for multicast domain-wide reachable address; the source address used for multicast
messages is the link-local address of the interface on which the message messages is the link-local address of the interface on which the message
is being sent. is being sent.
The IPv4 `ALL-PIM-ROUTERS' group is `224.0.0.13'. The IPv6 `ALL-PIM- The IPv4 `ALL-PIM-ROUTERS' group is `224.0.0.13'. The IPv6 `ALL-PIM-
ROUTERS' group is `ff02::d'. ROUTERS' group is `ff02::d'.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type | Reserved | Checksum | |PIM Ver| Type | Reserved | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Ver PIM Ver
PIM Version number is 2. PIM Version number is 2.
Type Types for specific PIM messages. PIM Types are: | Type Types for specific PIM messages. PIM Types are:
Message Type Destination || Message Type Destination
0 = Hello Multicast to ALL-PIM-ROUTERS || ---------------------------------------------------------------------------
1 = Register Unicast to RP || 0 = Hello Multicast to ALL-PIM-ROUTERS
2 = Register-Stop Unicast to source of Register packet|| 1 = Register Unicast to RP
3 = Join/Prune Multicast to ALL-PIM-ROUTERS || 2 = RegisterStop Unicast to source of Register packet
4 = Bootstrap Multicast to ALL-PIM-ROUTERS || 3 = Join/Prune Multicast to ALL-PIM-ROUTERS
5 = Assert Multicast to ALL-PIM-ROUTERS || 4 = Bootstrap Multicast to ALL-PIM-ROUTERS
6 = Graft (used in PIM-DM only) Multicast to ALL-PIM-ROUTERS || 5 = Assert Multicast to ALL-PIM-ROUTERS
7 = Graft-Ack (used in PIM-DM only) Unicast to source of Graft packet || 6 = Graft (used in PIM-DM only) Multicast to ALL-PIM-ROUTERS
8 = Candidate-RP-Advertisement Unicast to Domain's BSR || 7 = Graft-Ack (used in PIM-DM only) Unicast to source of Graft packet
8 = Candidate-RP-Advertisement Unicast to Domain's BSR
Reserved Reserved
Set to zero on transmission. Ignored upon receipt. Set to zero on transmission. Ignored upon receipt.
Checksum Checksum
The checksum is a standard IP checksum, i.e. the 16-bit one's The checksum is a standard IP checksum, i.e. the 16-bit one's
complement of the one's complement sum of the entire PIM message, complement of the one's complement sum of the entire PIM message,
excluding the data portion in the Register message. For computing excluding the "Multicast data packet" section of the Register
the checksum, the checksum field is zeroed. message. For computing the checksum, the checksum field is zeroed.
For IPv6, the checksum also includes the IPv6 "pseudo-header", as For IPv6, the checksum also includes the IPv6 "pseudo-header", as
specified in RFC 2460, section 8.1 [9]. This "pseudo-header" is specified in RFC 2460, section 8.1 [5]. This "pseudo-header" is
prepended to the PIM header for the purposes of calculating the prepended to the PIM header for the purposes of calculating the
checksum. The "Upper-Layer Packet Length" in the pseudo-header is checksum. The "Upper-Layer Packet Length" in the pseudo-header is
set to the length of the PIM message. The Next Header value used set to the length of the PIM message. The Next Header value used
in the pseudo-header is 103. If the packet's length is not an in the pseudo-header is 103. If the packet's length is not an
integral number of 16-bit words, the packet is padded with a byte integral number of 16-bit words, the packet is padded with a byte
of zero before performing the checksum. of zero before performing the checksum.
4.9.1. Encoded Source and Group Address Formats 4.10.1. Encoded Source and Group Address Formats
Encoded-Unicast address Encoded-Unicast address
An Encoded-Unicast address takes the following format: An Encoded-Unicast address takes the following format:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Addr Family | Encoding Type | Unicast Address | Addr Family | Encoding Type | Unicast Address
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
Addr Family Addr Family
The PIM address family of the `Unicast Address' field of this The PIM address family of the `Unicast Address' field of this
address. address.
Values of 0-127 are as assigned by the IANA for Internet Address Values of 0-127 are as assigned by the IANA for Internet Address
Families in [5]. Values 128-250 are reserved to be assigned by the Families in [8]. Values 128-250 are reserved to be assigned by the
IANA for PIM-specific Address Families. Values 251 though 255 are IANA for PIM-specific Address Families. Values 251 though 255 are
designated for private use. As there is no assignment authority designated for private use. As there is no assignment authority
for this space, collisions should be expected. for this space, collisions should be expected.
Encoding Type Encoding Type
The type of encoding used within a specific Address Family. The The type of encoding used within a specific Address Family. The
value `0' is reserved for this field, and represents the native value `0' is reserved for this field, and represents the native
encoding of the Address Family. encoding of the Address Family.
Unicast Address Unicast Address
The unicast address as represented by the given Address Family and The unicast address as represented by the given Address Family and
Encoding Type. Encoding Type.
Encoded-Group address Encoded-Group address
Encoded-Group addresses take the following format: Encoded-Group addresses take the following format:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Addr Family | Encoding Type |B| Reserved |Z| Mask Len | | | Addr Family | Encoding Type |B| Reserved |Z| Mask Len |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Group multicast Address | | Group multicast Address
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+...
Addr Family Addr Family
described above. described above.
Encoding Type Encoding Type
described above. described above.
[B]idirectional PIM [B]idirectional PIM
indicates the group range should use Bidirectional PIM [6]. For indicates the group range should use Bidirectional PIM [9]. For
PIM-SM defined in this specification, this bit MUST be zero. PIM-SM defined in this specification, this bit MUST be zero.
Reserved Reserved
Transmitted as zero. Ignored upon receipt. Transmitted as zero. Ignored upon receipt.
Admin Scope [Z]one | Admin Scope [Z]one
indicates the group range is an admin scope zone. This is used in | indicates the group range is an admin scope zone. This is used in
the Bootstrap Router Mechanism [4] only. For all other purposes, | the Bootstrap Router Mechanism [7] only. For all other purposes,
this bit is set to zero and ignored on receipt. | this bit is set to zero and ignored on receipt.
Mask Len Mask Len
The Mask length field is 8 bits. The value is the number of The Mask length field is 8 bits. The value is the number of
contiguous one bits left justified used as a mask which, combined contiguous one bits left justified used as a mask which, combined
with the group address, describes a range of groups. It is less with the group address, describes a range of groups. It is less
than or equal to the address length in bits for the given Address than or equal to the address length in bits for the given Address
Family and Encoding Type. If the message is sent for a single group Family and Encoding Type. If the message is sent for a single group
then the Mask length must equal the address length in bits for the then the Mask length must equal the address length in bits for the
given Address Family and Encoding Type. (e.g. 32 for IPv4 native given Address Family and Encoding Type. (e.g. 32 for IPv4 native
encoding and 128 for IPv6 native encoding). encoding and 128 for IPv6 native encoding).
skipping to change at page 101, line 34 skipping to change at page 104, line 33
Encoding Type Encoding Type
described above. described above.
Reserved Reserved
Transmitted as zero, ignored on receipt. Transmitted as zero, ignored on receipt.
S The Sparse bit is a 1 bit value, set to 1 for PIM-SM. It is used S The Sparse bit is a 1 bit value, set to 1 for PIM-SM. It is used
for PIM version 1 compatibility. for PIM version 1 compatibility.
W The WC (or WildCard) bit is a 1 bit value for use with PIM W The WC (or WildCard) bit is a 1 bit value for use with PIM
Join/Prune messages (see section 4.9.5.1 ). Join/Prune messages (see section 4.10.5.1 ).
R The RPT (or Rendezvous Point Tree) bit is a 1 bit value for use R The RPT (or Rendezvous Point Tree) bit is a 1 bit value for use
with PIM Join/Prune messages (see section 4.9.5.1 ). If the WC bit with PIM Join/Prune messages (see section 4.10.5.1 ). If the WC bit
is 1, the RPT bit MUST be 1. is 1, the RPT bit MUST be 1.
Mask Len Mask Len
The mask length field is 8 bits. The value is the number of The mask length field is 8 bits. The value is the number of
contiguous one bits left justified used as a mask which, combined contiguous one bits left justified used as a mask which, combined
with the Source Address, describes a source subnet. The mask length | with the Source Address, describes a source subnet. The mask length
MUST be equal to the mask length in bits for the given Address | MUST be equal to the mask length in bits for the given Address
Family and Encoding Type (32 for IPv4 native and 128 for IPv6 | Family and Encoding Type (32 for IPv4 native and 128 for IPv6
native). A router SHOULD ignore any messages received with any | native). A router SHOULD ignore any messages received with any
other mask length. | other mask length.
Source Address Source Address
The source address. The source address.
4.9.2. Hello Message Format 4.10.2. Hello Message Format
It is sent periodically by routers on all interfaces. It is sent periodically by routers on all interfaces.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type | Reserved | Checksum | |PIM Ver| Type | Reserved | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| OptionType | OptionLength | | OptionType | OptionLength |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 103, line 10 skipping to change at page 106, line 7
The type of the option given in the following OptionValue field. The type of the option given in the following OptionValue field.
OptionLength OptionLength
The length of the OptionValue field in bytes. The length of the OptionValue field in bytes.
OptionValue OptionValue
A variable length field, carrying the value of the option. A variable length field, carrying the value of the option.
The Option fields may contain the following values: The Option fields may contain the following values:
o OptionType 1: Hold Time o OptionType 1: Holdtime
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 1 | Length = 2 | | Type = 1 | Length = 2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Hold Time | | Holdtime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Hold Time is the amount of time a receiver must keep the neighbor Holdtime is the amount of time a receiver must keep the neighbor
reachable, in seconds. If the Holdtime is set to `0xffff', the reachable, in seconds. If the Holdtime is set to `0xffff', the
receiver of this message never times out the neighbor. This may receiver of this message never times out the neighbor. This may
be used with dial-on-demand links, to avoid keeping the link up | be used with dial-on-demand links, to avoid keeping the link up
with periodic Hello messages. | with periodic Hello messages.
Hello messages with a Holdtime value set to `0' are also sent by | Hello messages with a Holdtime value set to `0' are also sent by
a router on an interface about to go down or changing IP address | a router on an interface about to go down or changing IP address
(see section 4.6.1). These are effectively goodbuy messages and | (see section 4.6.1). These are effectively goodbuy messages and
the receiving routers should immediately time out the neighbor | the receiving routers should immediately time out the neighbor
information for the sender. | information for the sender.
o OptionType 2: LAN Prune Delay | o OptionType 2: LAN Prune Delay
0 1 2 3 | 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 | 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 2 | Length = 4 | | | Type = 2 | Length = 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|T| LAN Delay | Override Interval | | |T| LAN Delay | Override_Interval |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The LAN_Prune_Delay option is used to tune the prune propagation | The LAN_Prune_Delay option is used to tune the prune propagation
delay on multi-access LANs. | delay on multi-access LANs.
The T bit specifies the ability of the sending router to disable | The T bit specifies the ability of the sending router to disable
joins suppression. | joins suppression.
LAN Delay and Override Interval are time intervals in units of | LAN Delay and Override_Interval are time intervals in units of
milliseconds are are used to tune the value of the J/P Override | milliseconds are are used to tune the value of the
Interval and its derived timer values. Section 4.6.3 describes how | Override_Interval(I) and its derived timer values. Section 4.6.3
these values affect the behaviour of a router. | describes how these values affect the behaviour of a router.
o OptionType 3 to 16: reserved to be defined in future versions of |
this document. | o OptionType 3 to 16: reserved to be defined in future versions of
this document.
o OptionType 18: deprecated and should not be used. o OptionType 18: deprecated and should not be used.
o OptionType 19: DR Priority o OptionType 19: DR Priority
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = 19 | Length = 4 | | Type = 19 | Length = 4 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 104, line 38 skipping to change at page 107, line 36
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Generation ID | | Generation ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Generation ID is a random 32-bit value for the interface on which Generation ID is a random 32-bit value for the interface on which
the Hello message is sent. The Generation ID is regenerated the Hello message is sent. The Generation ID is regenerated
whenever PIM forwarding is started or restarted on the interface. whenever PIM forwarding is started or restarted on the interface.
OptionTypes 17 thru 65000 are assigned by the IANA. OptionTypes OptionTypes 17 thru 65000 are assigned by the IANA. OptionTypes
65001 through 65535 are reserved for Private Use, as defined in 65001 through 65535 are reserved for Private Use, as defined in
[7]. [12].
Unknown options may be ignored. The "Hold Time" option MUST be Unknown options may be ignored. The "Holdtime" option MUST be
implemented; the "DR Priority" and "Generation ID" options SHOULD implemented; the "DR Priority" and "Generation ID" options SHOULD
be implemented. be implemented.
4.9.3. Register Message Format 4.10.3. Register Message Format
A Register message is sent by the DR or a PMBR to the RP when a A Register message is sent by the DR or a PMBR to the RP when a
multicast packet needs to be transmitted on the RP-tree. The IP source multicast packet needs to be transmitted on the RP-tree. The IP source
address is set to the address of the DR, the destination address to the address is set to the address of the DR, the destination address to the
RP's address. The IP TTL of the PIM packet is the system's normal RP's address. The IP TTL of the PIM packet is the system's normal
unicast TTL. unicast TTL.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 105, line 22 skipping to change at page 108, line 22
| | | |
. Multicast data packet . . Multicast data packet .
| | | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Reserved, Checksum PIM Version, Type, Reserved, Checksum
Described above. Note that the checksum for Registers is done only Described above. Note that the checksum for Registers is done only
on first 8 bytes of packet, including the PIM header and the next 4 on first 8 bytes of packet, including the PIM header and the next 4
bytes, excluding the data packet portion. For interoperability bytes, excluding the data packet portion. For interoperability
reasons, a message carrying a checksum calculated over the entire reasons, a message carrying a checksum calculated over the entire
PIM register message should be accepted. PIM Register message should also be accepted.
B The Border bit. If the router is a DR for a source that it is B The Border bit. If the router is a DR for a source that it is
directly connected to, it sets the B bit to 0. If the router is a directly connected to, it sets the B bit to 0. If the router is a
PMBR for a source in a directly connected cloud, it sets the B bit PMBR for a source in a directly connected cloud, it sets the B bit
to 1. to 1.
N The Null-Register bit. Set to 1 by a DR that is probing the RP N The Null-Register bit. Set to 1 by a DR that is probing the RP
before expiring its local Register-Suppression timer. Set to 0 before expiring its local Register-Suppression timer. Set to 0
otherwise. otherwise.
skipping to change at page 106, line 5 skipping to change at page 109, line 5
IPv6 data packet must be encapsulated in an IPv6 PIM packet. Note IPv6 data packet must be encapsulated in an IPv6 PIM packet. Note
that the TTL of the original packet is decremented before that the TTL of the original packet is decremented before
encapsulation, just like any other packet that is forwarded. In encapsulation, just like any other packet that is forwarded. In
addition, the RP decrements the TTL after decapsulating, before addition, the RP decrements the TTL after decapsulating, before
forwarding the packet down the shared tree. forwarding the packet down the shared tree.
For (S,G) null Registers, the Multicast data packet portion For (S,G) null Registers, the Multicast data packet portion
contains only a dummy header with S as the source address, G as the contains only a dummy header with S as the source address, G as the
destination address, and a data length of zero. destination address, and a data length of zero.
4.9.4. Register-Stop Message Format 4.10.4. RegisterStop Message Format
A Register-Stop is unicast from the RP to the sender of the Register A RegisterStop is unicast from the RP to the sender of the Register
message. The IP source address is the address to which the register was message. The IP source address is the address to which the register was
addressed. The IP destination address is the source address of the addressed. The IP destination address is the source address of the
register message. register message.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type | Reserved | Checksum | |PIM Ver| Type | Reserved | Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Group Address (Encoded-Group format) | | Group Address (Encoded-Group format) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address (Encoded-Unicast format) | | Source Address (Encoded-Unicast format) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Reserved, Checksum PIM Version, Type, Reserved, Checksum
Described above. Described above.
Group Address Group Address
The group address from the multicast data packet in the Register. The group address from the multicast data packet in the Register.
Format described in section 4.9.1. Note that for Register-Stops the Format described in section 4.10.1. Note that for RegisterStops the
Mask Len field contains the full address length * 8 (e.g. 32 for Mask Len field contains the full address length * 8 (e.g. 32 for
IPv4 native encoding), if the message is sent for a single group. IPv4 native encoding), if the message is sent for a single group.
Source Address Source Address
The host address of the source from the multicast data packet in | The host address of the source from the multicast data packet in
the register. The format for this address is given in the Encoded- | the register. The format for this address is given in the Encoded-
Unicast address in section 4.9.1. A special wild card value | Unicast address in section 4.10.1. A special wild card value
consisting of an address field of all zeroes can be used to | consisting of an address field of all zeroes can be used to
indicate any source. | indicate any source.
4.9.5. Join/Prune Message Format 4.10.5. Join/Prune Message Format
A Join/Prune message is sent by routers towards upstream sources and A Join/Prune message is sent by routers towards upstream sources and
RPs. Joins are sent to build shared trees (RP trees) or source trees RPs. Joins are sent to build shared trees (RP trees) or source trees
(SPT). Prunes are sent to prune source trees when members leave groups (SPT). Prunes are sent to prune source trees when members leave groups
as well as sources that do not use the shared tree. as well as sources that do not use the shared tree.
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|PIM Ver| Type | Reserved | Checksum | |PIM Ver| Type | Reserved | Checksum |
skipping to change at page 108, line 12 skipping to change at page 111, line 12
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Pruned Source Address n (Encoded-Source format) | | Pruned Source Address n (Encoded-Source format) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PIM Version, Type, Reserved, Checksum PIM Version, Type, Reserved, Checksum
Described above. Described above.
Unicast Upstream Ne