idnits 2.17.1 draft-ietf-pim-sm-v2-new-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 526 instances of too long lines in the document, the longest one being 33 characters in excess of 72. == There are 4 instances of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 == There are 1 instance of lines with non-RFC3849-compliant IPv6 addresses in the document. If these are example addresses, they should be changed. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 1246: '...Hello messages MUST be sent on all act...' RFC 2119 keyword, line 1252: '...liant PIM router MUST send Hello messa...' RFC 2119 keyword, line 1267: '...yet sent a Hello message, then it MUST...' RFC 2119 keyword, line 1274: '...Option SHOULD be included in every Hel...' RFC 2119 keyword, line 1280: '...r (GenID) Option SHOULD be included in...' (47 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: There is an exception with group sets that contain a (*,G) Join source list entry. The group set expresses the routers interest in receiving all traffic for the specified group on the shared tree and it MUST include an (S,G,rpt) Prune source list entry for every source that the router does not wish to receive. This list of (S,G,rpt) Prune source-list entries MUST not be split in multiple messages. -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (1 March 2002) is 8092 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: 'Actions A1' on line 3777 -- Looks like a reference, but probably isn't: 'Actions A6' on line 3437 -- Looks like a reference, but probably isn't: 'Actions A3' on line 3788 -- Looks like a reference, but probably isn't: 'Actions A2' on line 3801 -- Looks like a reference, but probably isn't: 'Actions A4' on line 3788 -- Looks like a reference, but probably isn't: 'Actions A5' on line 3813 == Missing Reference: '13' is mentioned on line 5953, but not defined ** Obsolete normative reference: RFC 2283 (ref. '1') (Obsoleted by RFC 2858) ** Downref: Normative reference to an Informational RFC: RFC 2983 (ref. '2') ** Obsolete normative reference: RFC 2460 (ref. '5') (Obsoleted by RFC 8200) == Outdated reference: A later version (-12) exists of draft-ietf-pim-sm-bsr-02 -- Possible downref: Non-RFC (?) normative reference: ref. '8' == Outdated reference: A later version (-09) exists of draft-ietf-pim-bidir-02 == Outdated reference: A later version (-04) exists of draft-holbrook-ssm-00 -- Possible downref: Normative reference to a draft: ref. '10' ** Obsolete normative reference: RFC 2401 (ref. '11') (Obsoleted by RFC 4301) -- Possible downref: Non-RFC (?) normative reference: ref. '12' Summary: 9 errors (**), 0 flaws (~~), 8 warnings (==), 12 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Engineering Task Force PIM WG 2 INTERNET-DRAFT Bill Fenner/AT&T 3 draft-ietf-pim-sm-v2-new-05.txt Mark Handley/ICIR 4 Hugh Holbrook/Cisco 5 Isidor Kouvelas/Cisco 6 1 March 2002 7 Expires: September 2002 9 Protocol Independent Multicast - Sparse Mode (PIM-SM): 10 Protocol Specification (Revised) 12 Status of this Document 14 This document is an Internet-Draft and is in full conformance with all 15 provisions of Section 10 of RFC2026. 17 Internet-Drafts are working documents of the Internet Engineering Task 18 Force (IETF), its areas, and its working groups. Note that other groups 19 may also distribute working documents as Internet-Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six months 22 and may be updated, replaced, or obsoleted by other documents at any 23 time. It is inappropriate to use Internet- Drafts as reference material 24 or to cite them other than as "work in progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html. 32 This document is a product of the IETF PIM WG. Comments should be 33 addressed to the authors, or the WG's mailing list at 34 pim@catarina.usc.edu. 36 Abstract 38 This document specifies Protocol Independent Multicast - 39 Sparse Mode (PIM-SM). PIM-SM is a multicast routing protocol 40 that can use the underlying unicast routing information base 41 or a separate multicast-capable routing information base. It 42 builds unidirectional shared trees rooted at a Rendezvous 43 Point (RP) per group, and optionally creates shortest-path 44 trees per source. 46 Table of Contents 48 1. Introduction. . . . . . . . . . . . . . . . . . . . . . 6 49 2. Terminology . . . . . . . . . . . . . . . . . . . . . . 6 50 2.1. Definitions. . . . . . . . . . . . . . . . . . . . . 6 51 2.2. Pseudocode Notation. . . . . . . . . . . . . . . . . 7 52 3. PIM-SM Protocol Overview. . . . . . . . . . . . . . . . 8 53 4. Protocol Specification. . . . . . . . . . . . . . . . . 13 54 4.1. PIM Protocol State . . . . . . . . . . . . . . . . . 13 55 4.1.1. General Purpose State . . . . . . . . . . . . . . 14 56 4.1.2. (*,*,RP) State. . . . . . . . . . . . . . . . . . 15 57 4.1.3. (*,G) State . . . . . . . . . . . . . . . . . . . 16 58 4.1.4. (S,G) State . . . . . . . . . . . . . . . . . . . 17 59 4.1.5. (S,G,rpt) State . . . . . . . . . . . . . . . . . 19 60 4.1.6. State Summarization Macros. . . . . . . . . . . . 20 61 4.2. Data Packet Forwarding Rules . . . . . . . . . . . . 25 62 4.2.1. Last hop switchover to the SPT. . . . . . . . . . 27 63 4.2.2. Setting and Clearing the (S,G) SPT bit. . . . . . 27 64 4.3. Designated Routers (DR) and Hello Messages . . . . . 29 65 4.3.1. Sending Hello Messages. . . . . . . . . . . . . . 29 66 4.3.2. DR Election . . . . . . . . . . . . . . . . . . . 31 67 4.3.3. Reducing Prune Propagation Delay on LANs. . . . . 32 68 4.4. PIM Register Messages. . . . . . . . . . . . . . . . 35 69 4.4.1. Sending Register Messages from the DR . . . . . . 35 70 4.4.2. Receiving Register Messages at the RP . . . . . . 39 71 4.5. PIM Join/Prune Messages. . . . . . . . . . . . . . . 41 72 4.5.1. Receiving (*,*,RP) Join/Prune Messages. . . . . . 42 73 4.5.2. Receiving (*,G) Join/Prune Messages . . . . . . . 45 74 4.5.3. Receiving (S,G) Join/Prune Messages . . . . . . . 49 75 4.5.4. Receiving (S,G,rpt) Join/Prune Messages . . . . . 52 76 4.5.5. Sending (*,*,RP) Join/Prune Messages. . . . . . . 58 77 4.5.6. Sending (*,G) Join/Prune Messages . . . . . . . . 62 78 4.5.7. Sending (S,G) Join/Prune Messages . . . . . . . . 66 79 4.5.8. (S,G,rpt) Periodic Messages . . . . . . . . . . . 71 80 4.5.9. State Machine for (S,G,rpt) Triggered 81 Messages . . . . . . . . . . . . . . . . . . . . . . . . 72 82 4.6. PIM Assert Messages. . . . . . . . . . . . . . . . . 76 83 4.6.1. (S,G) Assert Message State Machine. . . . . . . . 76 84 4.6.2. (*,G) Assert Message State Machine. . . . . . . . 84 85 4.6.3. Assert Metrics. . . . . . . . . . . . . . . . . . 91 86 4.6.4. AssertCancel Messages . . . . . . . . . . . . . . 92 87 4.6.5. Assert State Macros . . . . . . . . . . . . . . . 93 88 4.7. PIM Multicast Border Router Behavior . . . . . . . . 96 89 4.7.1. Sources External to the PIM-SM Domain . . . . . . 96 90 4.7.2. Sources Internal to the PIM-SM Domain . . . . . . 97 91 4.8. PIM Bootstrap and RP Discovery . . . . . . . . . . . 98 92 4.8.1. Group-to-RP Mapping . . . . . . . . . . . . . . . 99 93 4.8.2. Hash Function . . . . . . . . . . . . . . . . . . 100 94 4.9. Source-Specific Multicast. . . . . . . . . . . . . . 101 95 4.9.1. Protocol Modifications for SSM destination 96 addresses. . . . . . . . . . . . . . . . . . . . . . . . 102 97 4.9.2. PIM-SSM-only Routers. . . . . . . . . . . . . . . 102 98 4.10. PIM Packet Formats. . . . . . . . . . . . . . . . . 104 99 4.10.1. Encoded Source and Group Address 100 Formats. . . . . . . . . . . . . . . . . . . . . . . . . 105 101 4.10.2. Hello Message Format . . . . . . . . . . . . . . 108 102 4.10.3. Register Message Format. . . . . . . . . . . . . 110 103 4.10.4. RegisterStop Message Format. . . . . . . . . . . 112 104 4.10.5. Join/Prune Message Format. . . . . . . . . . . . 112 105 4.10.5.1. Group Set Source List Rules . . . . . . . . . 115 106 4.10.5.2. Group Set Fragmentation . . . . . . . . . . . 119 107 4.10.6. Assert Message Format. . . . . . . . . . . . . . 119 108 4.11. PIM Timers. . . . . . . . . . . . . . . . . . . . . 121 109 4.12. Timer Values. . . . . . . . . . . . . . . . . . . . 122 110 5. IANA Considerations . . . . . . . . . . . . . . . . . . 128 111 5.1. PIM Address Family . . . . . . . . . . . . . . . . . 128 112 5.2. PIM Hello Options. . . . . . . . . . . . . . . . . . 129 113 6. Security Considerations . . . . . . . . . . . . . . . . 129 114 6.1. Attacks based on forged messages . . . . . . . . . . 129 115 6.1.1. Forged link-local messages. . . . . . . . . . . . 129 116 6.1.2. Forged unicast messages . . . . . . . . . . . . . 130 117 6.2. Non-cryptographic Authentication Mechanisms. . . . . 130 118 6.3. Authentication using IPsec . . . . . . . . . . . . . 131 119 6.3.1. Protecting link-local multicast messages. . . . . 131 120 6.3.2. Protecting unicast messages . . . . . . . . . . . 132 121 6.3.2.1. Register messages. . . . . . . . . . . . . . . 132 122 6.3.2.2. Register Stop messages . . . . . . . . . . . . 132 123 6.4. Denial of Service Attacks. . . . . . . . . . . . . . 133 124 7. Authors' Addresses. . . . . . . . . . . . . . . . . . . 133 125 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . 134 126 9. References. . . . . . . . . . . . . . . . . . . . . . . 134 127 10. Index. . . . . . . . . . . . . . . . . . . . . . . . . 136 129 List of Figures 131 Figure 1. Per-(S,G) register state-machine at a DR . . . . 36 132 Figure 2. Downstream (*,*,RP) per-interface 133 state-machine. . . . . . . . . . . . . . . . . . . . . . . 42 134 Figure 3. Downstream (*,G) per-interface 135 state-machine. . . . . . . . . . . . . . . . . . . . . . . 46 136 Figure 4. Downstream per-interface (S,G) 137 state-machine. . . . . . . . . . . . . . . . . . . . . . . 50 138 Figure 5. Downstream per-interface (S,G,rpt) 139 state-machine. . . . . . . . . . . . . . . . . . . . . . . 53 140 Figure 6. Upstream (*,*,RP) state-machine. . . . . . . . . 58 141 Figure 7. Upstream (*,G) state-machine . . . . . . . . . . 62 142 Figure 8. Upstream (S,G) state-machine . . . . . . . . . . 67 143 Figure 9. Upstream (S,G,rpt) state-machine for trig- 144 gered messages . . . . . . . . . . . . . . . . . . . . . . 72 145 Figure 10. Per-interface (S,G) Assert 146 State-machine. . . . . . . . . . . . . . . . . . . . . . . 78 147 Figure 11. (*,G) Assert State-machine. . . . . . . . . . . 85 149 1. Introduction 151 This document specifies a protocol for efficiently routing multicast 152 groups that may span wide-area (and inter-domain) internets. This 153 protocol is called Protocol Independent Multicast - Sparse Mode (PIM-SM) 154 because, although it may use the underlying unicast routing to provide 155 reverse-path information for multicast tree building, it is not 156 dependent on any particular unicast routing protocol. 158 PIM-SM version 2 was originally specified in RFC 2117, and revised in 159 RFC 2362. This document is intended to obsolete RFC 2362, and to 160 correct a number of deficiencies that have been identified with the way 161 PIM-SM was previously specified. As far as possible, this document 162 specifies the same protocol as RFC 2362, and only diverges from the 163 behavior intended by RFC 2362 when the previously specified behavior was 164 clearly incorrect. Routers implemented according to the specification 165 in this document will be able to successfully interoperate with routers 166 implemented according to RFC 2362. 168 2. Terminology 170 In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", 171 "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and 172 "OPTIONAL" are to be interpreted as described in RFC 2119 and indicate 173 requirement levels for compliant PIM-SM implementations. 175 2.1. Definitions 177 This specification uses a number of terms to refer to the roles of 178 routers participating in PIM-SM. The following terms have special 179 significance for PIM-SM: 181 Rendezvous Point (RP): 182 An RP is a router that has been configured to be used as the root 183 of the non-source-specific distribution tree for a multicast 184 group. Join messages from receivers for a group are sent towards 185 the RP, and data from senders is sent to the RP so that receivers 186 can discover who the senders are, and start to receive traffic 187 destined for the group. 189 Designated Router (DR): 190 A shared-media LAN like Ethernet may have multiple PIM-SM routers 191 connected to it. If the LAN has directly connected hosts, then a 192 single one of these routers, the DR, will act on behalf of those 193 hosts with respect to the PIM-SM protocol. A single DR is elected 194 per interface (LAN or otherwise) using a simple election process. 196 MRIB Multicast Routing Information Base. This is the multicast 197 topology table, which is typically derived from the unicast 198 routing table, or routing protocols such as MBGP that carry 199 multicast-specific topology information. In PIM-SM, the MRIB is 200 used to decide where to send Join/Prune messages. A secondary 201 function of the MRIB is to provide routing metrics for destination 202 addresses, these metrics are used when sending and processing 203 Assert messages. 205 RPF Neighbor 206 RPF stands for "Reverse Path Forwarding". The RPF Neighbor of a 207 router with respect to an address is the neighbor that the MRIB 208 indicates should be used to forward packets to that address. In 209 the case of a PIM-SM multicast group, the RPF neighbor is the 210 router that a Join message for that group would be directed to, in 211 the absence of modifying Assert state. 213 TIB Tree Information Base. This is the collection of state at a PIM 214 router that has been created by receiving PIM Join/Prune messages, 215 PIM Assert messages, and IGMP or MLD information from local hosts. 216 It essentially stores the state of all multicast distribution 217 trees at that router. 219 MFIB Multicast Forwarding Information Base. The TIB holds all the 220 state that is necessary to forward multicast packets at a router. 221 However, although this specification defines forwarding in terms 222 of the TIB, to actually forward packets using the TIB is very 223 inefficient. Instead a real router implementation will normally 224 build an efficient MFIB from the TIB state to perform forwarding. 225 How this is done is implementation-specific, and is not discussed 226 in this document. 228 Upstream 229 Towards the root of the tree. The root of tree may either be the 230 source or the RP depending on the context. 232 Downstream 233 Away from the root of the tree. 235 2.2. Pseudocode Notation 237 We use set notation in several places in this specification. 239 A (+) B 240 is the union of two sets A and B. 242 A (-) B 243 is the elements of set A that are not in set B. 245 NULL 246 is the empty set or list. 248 In addition we use C-like syntax: 250 = denotes assignment of a variable. 252 == denotes a comparison for equality. 254 != denotes a comparison for inequality. 256 Braces { and } are used for grouping. 258 3. PIM-SM Protocol Overview 260 This section provides an overview of PIM-SM behavior. It is intended as 261 an introduction to how PIM-SM works, and is NOT definitive. For the 262 definitive specification, see Section 4. 264 PIM relies on an underlying topology-gathering protocol to populate a 265 routing table with routes. This routing table is called the MRIB or 266 Multicast Routing Information Base. The routes in this table may be 267 taken directly from the unicast routing table, or it may be different 268 and provided by a separate routing protocol such as MBGP [1]. Regardless 269 of how it is created, the primary role of the MRIB in the PIM protocol 270 is to provide the next hop router along a multicast-capable path to each 271 destination subnet. The MRIB is used to determine the next hop neighbor 272 to which any PIM Join/Prune message is sent. Data flows along the 273 reverse path of the Join messages. Thus, in contrast to the unicast RIB 274 which specifies the next hop that a data packet would take to get to 275 some subnet, the MRIB gives reverse-path information, and indicates the 276 path that a multicast data packet would take from its origin subnet to 277 the router that has the MRIB. 279 Like all multicast routing protocols that implement the service model 280 from RFC 1112 [3], PIM-SM must be able to route data packets from 281 sources to receivers without either the sources or receivers knowing a- 282 priori of the existence of the others. This is essentially done in 283 three phases, although as senders and receivers may come and go at any 284 time, all three phases may be occur simultaneously. 286 Phase One: RP Tree 288 In phase one, a multicast receiver expresses its interest in receiving 289 traffic destined for a multicast group. Typically it does this using 290 IGMP [6] or MLD [4], but other mechanisms might also serve this purpose. 291 One of the receiver's local routers is elected as the Designated Router 292 (DR) for that subnet. On receiving the receiver's expression of 293 interest, the DR then sends a PIM Join message towards the RP for that 294 multicast group. This Join message is known as a (*,G) Join because it 295 joins group G for all sources to that group. The (*,G) Join travels 296 hop-by-hop towards the RP for the group, and in each router it passes 297 through, multicast tree state for group G is instantiated. Eventually 298 the (*,G) Join either reaches the RP, or reaches a router that already 299 has (*,G) Join state for that group. When many receivers join the 300 group, their Join messages converge on the RP, and form a distribution 301 tree for group G that is rooted at the RP. This is known as the RP Tree 302 (RPT), and is also known as the shared tree because it is shared by all 303 sources sending to that group. Join messages are resent periodically so 304 long as the receiver remains in the group. When all receivers on a 305 leaf-network leave the group, the DR will send a PIM (*,G) Prune message 306 towards the RP for that multicast group. However if the Prune message is 307 not sent for any reason, the state will eventually time out. 309 A multicast data sender just starts sending data destined for a 310 multicast group. The sender's local router (DR) takes those data 311 packets, unicast-encapsulates them, and sends them directly to the RP. 312 The RP receives these encapsulated data packets, decapsulates them, and 313 forwards them onto the shared tree. The packets then follow the (*,G) 314 multicast tree state in the routers on the RP Tree, being replicated 315 wherever the RP Tree branches, and eventually reaching all the receivers 316 for that multicast group. The process of encapsulating data packets to 317 the RP is called registering, and the encapsulation packets are known as 318 PIM Register packets. 320 At the end of phase one, multicast traffic is flowing encapsulated to 321 the RP, and then natively over the RP tree to the multicast receivers. 323 Phase Two: Register Stop 325 Register-encapsulation of data packets is inefficient for two reasons: 327 o Encapsulation and decapsulation may be relatively expensive operations 328 for a router to perform, depending on whether or not the router has 329 appropriate hardware for these tasks. 331 o Traveling all the way to the RP, and then back down the shared tree 332 may entail the packets traveling a relatively long distance to reach 333 receivers that are close to the sender. For some applications, this 334 increased latency is undesirable. 336 Although Register-encapsulation may continue indefinitely, for these 337 reasons, the RP will normally choose to switch to native forwarding. To 338 do this, when the RP receives a register-encapsulated data packet from 339 source S on group G, it will normally initiate an (S,G) source-specific 340 Join towards S. This Join message travels hop-by-hop towards S, 341 instantiating (S,G) multicast tree state in the routers along the path. 342 (S,G) multicast tree state is used only to forward packets for group G 343 if those packets come from source S. Eventually the Join message 344 reaches S's subnet or a router that already has (S,G) multicast tree 345 state, and then packets from S start to flow following the (S,G) tree 346 state towards the RP. These data packets may also reach routers with 347 (*,G) state along the path towards the RP - if so, they can short-cut 348 onto the RP tree at this point. 350 While the RP is in the process of joining the source-specific tree for 351 S, the data packets will continue being encapsulated to the RP. When 352 packets from S also start to arrive natively at the the RP, the RP will 353 be receiving two copies of each of these packets. At this point, the RP 354 starts to discard the encapsulated copy of these packets, and it sends a 355 RegisterStop message back to S's DR to prevent the DR unnecessarily 356 encapsulating the packets. 358 At the end of phase 2, traffic will be flowing natively from S along a 359 source-specific tree to the RP, and from there along the shared tree to 360 the receivers. Where the two trees intersect, traffic may transfer from 361 the source-specific tree to the RP tree, and so avoid taking a long 362 detour via the RP. 364 It should be noted that a sender may start sending before or after a 365 receiver joins the group, and thus phase two may happen before the 366 shared tree to the receiver is built. 368 Phase 3: Shortest-Path Tree 370 Although having the RP join back towards the source removes the 371 encapsulation overhead, it does not completely optimize the forwarding 372 paths. For many receivers the route via the RP may involve a 373 significant detour when compared with the shortest path from the source 374 to the receiver. 376 To obtain lower latencies, a router on the receiver's LAN, typically the 377 DR, may optionally initiate a transfer from the shared tree to a source- 378 specific shortest-path tree (SPT). To do this, it issues an (S,G) Join 379 towards S. This instantiates state in the routers along the path to S. 380 Eventually this join either reaches S's subnet, or reaches a router that 381 already has (S,G) state. When this happens, data packets from S start 382 to flow following the (S,G) state until they reach the receiver. 384 At this point the receiver (or a router upstream of the receiver) will 385 be receiving two copies of the data - one from the SPT and one from the 386 RPT. When the first traffic starts to arrive from the SPT, the DR or 387 upstream router starts to drop the packets for G from S that arrive via 388 the RP tree. In addition, it sends an (S,G) Prune message towards the 389 RP. This is known as an (S,G,rpt) Prune. The Prune message travels 390 hop-by-hop, instantiating state along the path towards the RP indicating 391 that traffic from S for G should NOT be forwarded in this direction. 392 The prune is propagated until it reaches the RP or a router that still 393 needs the traffic from S for other receivers. 395 By now, the receiver will be receiving traffic from S along the 396 shortest-path tree between the receiver and S. In addition, the RP is 397 receiving the traffic from S, but this traffic is no longer reaching the 398 receiver along the RP tree. As far as the receiver is concerned, this 399 is the final distribution tree. 401 Source-specific Joins 403 IGMPv3 permits a receiver to join a group and specify that it only wants 404 to receive traffic for a group if that traffic comes from a particular 405 source. If a receiver does this, and no other receiver on the LAN 406 requires all the traffic for the group, then the DR may omit performing 407 a (*,G) join to set up the shared tree, and instead issue a source- 408 specific (S,G) join only. 410 The range of multicast addresses from 232.0.0.0 to 232.255.255.255 is 411 currently set aside for source-specific multicast in IPv4. For groups 412 in this range, receivers should only issue source-specific IGMPv3 joins. 413 If a PIM router receives a non-source-specific join for a group in this 414 range, it should ignore it, as described in Section 4.9. 416 Source-specific Prunes 418 IGMPv3 also permits a receiver to join a group and specify that it only 419 wants to receive traffic for a group if that traffic does not come from 420 a specific source or sources. In this case, the DR will perform a (*,G) 421 join as normal, but may combine this with an (S,G,rpt) prune for each of 422 the sources the receiver does not wish to receive. 424 Multi-access Transit LANs 426 The overview so far has concerned itself with point-to-point links. 427 However, using multi-access LANs such as Ethernet for transit is not 428 uncommon. This can cause complications for three reasons: 430 o Two or more routers on the LAN may issue (*,G) Joins to different 431 upstream routers on the LAN because they have inconsistent MRIB 432 entries regarding how to reach the RP. Both paths on the RP tree will 433 be set up, causing two copies of all the shared tree traffic to appear 434 on the LAN. 436 o Two or more routers on the LAN may issue (S,G) Joins to different 437 upstream routers on the LAN because they have inconsistent MRIB 438 entries regarding how to reach source S. Both paths on the source- 439 specific tree will be set up, causing two copies of all the traffic 440 from S to appear on the LAN. 442 o A router on the LAN may issue a (*,G) Join to one upstream router on 443 the LAN, and another router on the LAN may issue an (S,G) Join to a 444 different upstream router on the same LAN. Traffic from S may reach 445 the LAN over both the RPT and the SPT. If the receiver behind the 446 downstream (*,G) router doesn't issue an (S,G,rpt) prune, then this 447 condition would persist. 449 All of these problems are caused by there being more than one upstream 450 router with join state for the group or source-group pair. PIM does not 451 prevent such duplicate joins from occurring - instead when duplicate 452 data packets appear on the LAN from different routers, these routers 453 notice this, and then elect a single forwarder. This election is 454 performed using PIM Assert messages, which resolve the problem in favor 455 of the upstream router which has (S,G) state, or if neither or both 456 router has (S,G) state, then in favor of the router with the best metric 457 to the RP for RP trees, or the best metric to the source to source- 458 specific trees. 460 These Assert messages are also received by the downstream routers on the 461 LAN, and these cause subsequent Join messages to be sent to the upstream 462 router that won the Assert. 464 RP Discovery 466 PIM-SM routers need to know the address of the RP for each group for 467 which they have (*,G) state. This address is obtained either through a 468 bootstrap mechanism or through static configuration. 470 One dynamic way to do this is to use the Bootstrap Router (BSR) 471 mechanism [7]. One router in each PIM domain is elected the Bootstrap 472 Router through a simple election process. All the routers in the domain 473 that are configured to be candidates to be RPs periodically unicast 474 their candidacy to the BSR. From the candidates, the BSR picks an RP- 475 set, and periodically announces this set in a Bootstrap message. 476 Bootstrap messages are flooded hop-by-hop throughout the domain until 477 all routers in the domain know the RP-Set. 479 To map a group to an RP, a router hashes the group address into the RP- 480 set using an order-preserving hash function (one that minimizes changes 481 if the RP set changes). The resulting RP is the one that it uses as the 482 RP for that group. 484 4. Protocol Specification 486 The specification of PIM-SM is broken into several parts: 488 o Section 4.1 details the protocol state stored. 490 o Section 4.2 specifies the data packet forwarding rules. 492 o Section 4.3. specifies Designated Router (DR) election and the rules 493 for sending and processing Hello messages. 495 o Section 4.4 specifies the PIM Register generation and processing 496 rules. 498 o Section 4.5 specifies the PIM Join/Prune generation and processing 499 rules. 501 o Section 4.6 specifies the PIM Assert generation and processing rules. 503 o Section 4.8 specifies the RP discovery mechanisms. 505 o The subset of PIM required to support Source-Specific Multicast, PIM- 506 SSM, is described in Section 4.9. 508 o PIM packet formats are specified in Section 4.10. 510 o A summary of PIM-SM timers and their default values is given in 511 Section 4.11. 513 4.1. PIM Protocol State 515 This section specifies all the protocol state that a PIM implementation 516 should maintain in order to function correctly. We term this state the 517 Tree Information Base or TIB, as it holds the state of all the multicast 518 distribution trees at this router. In this specification we define PIM 519 mechanisms in terms of the TIB. However, only a very simple 520 implementation would actually implement packet forwarding operations in 521 terms of this state. Most implementations will use this state to build 522 a multicast forwarding table, which would then be updated when the 523 relevant state in the TIB changes. 525 Although we specify precisely the state to be kept, this does not mean 526 that an implementation of PIM-SM needs to hold the state in this form. 528 This is actually an abstract state definition, which is needed in order 529 to specify the router's behavior. A PIM-SM implementation is free to 530 hold whatever internal state it requires, and will still be conformant 531 with this specification so long as it results in the same externally 532 visible protocol behavior as an abstract router that holds the following 533 state. 535 We divide TIB state into four sections: 537 (*,*,RP) state 538 State that maintains per-RP trees, for all groups served by a given 539 RP. 541 (*,G) state 542 State that maintains the RP tree for G. 544 (S,G) state 545 State that maintains a source-specific tree for source S and group 546 G. 548 (S,G,rpt) state 549 State that maintains source-specific information about source S on 550 the RP tree for G. For example, if a source is being received on 551 the source-specific tree, it will normally have been pruned off the 552 RP tree. This prune state is (S,G,rpt) state. 554 The state that should be kept is described below. Of course, 555 implementations will only maintain state when it is relevant to 556 forwarding operations - for example, the "NoInfo" state might be assumed 557 from the lack of other state information, rather than being held 558 explicitly. 560 4.1.1. General Purpose State 562 A router holds the following non-group-specific state: 564 For each interface: 566 o Override Interval 568 o Propagation Delay 570 o Suppression state: One of {"Enable", "Disable"} 572 Neighbor State: 574 For each neighbor: 576 o Information from neighbor's Hello 578 o Neighbor's Gen ID. 580 o Neighbor liveness timer (NLT) 582 Designated Router (DR) State: 584 o Designated Router's IP Address 586 o DR's DR Priority 588 The Override Interval, the Propagation Delay and the Interface 589 suppression state are described in section 4.3.3. Designated Router 590 state is described in section 4.3. 592 4.1.2. (*,*,RP) State 594 For every RP a router keeps the following state: 596 (*,*,RP) state: 597 For each interface: 599 PIM (*,*,RP) Join/Prune State: 601 o State: One of {"NoInfo" (NI), "Join" (J), 602 "PrunePending" (PP)} 604 o Prune Pending Timer (PPT) 606 o Join/Prune Expiry Timer (ET) 608 Not interface specific: 610 o Upstream Join/Prune Timer (JT) 612 o Last RPF Neighbor towards RP that was used 614 PIM (*,*,RP) Join/Prune state is the result of receiving PIM (*,*,RP) 615 Join/Prune messages on this interface, and is specified in section 616 4.5.1. 618 The upstream (*,*,RP) Join/Prune timer is used to send out periodic 619 Join(*,*,RP) messages, and to override Prune(*,*,RP) messages from peers 620 on an upstream LAN interface. 622 The last RPF neighbor towards the RP is stored because if the MRIB 623 changes then the RPF neighbor towards the RP may change. If it does so, 624 then we need to trigger a new Join(*,*,RP) to the new upstream neighbor 625 and a Prune(*,*,RP) to the old upstream neighbor. Similarly, if a 626 router detects through a changed GenID in a Hello message that the 627 upstream neighbor towards the RP has rebooted, then it should re- 628 instantiate state by sending a Join(*,*,RP). These mechanisms are 629 specified in Section 4.5.5. 631 4.1.3. (*,G) State 633 For every group G a router keeps the following state: 635 (*,G) state: 636 For each interface: 638 Local Membership: 639 State: One of {"NoInfo", "Include"} 641 PIM (*,G) Join/Prune State: 643 o State: One of {"NoInfo" (NI), "Join" (J), 644 "PrunePending" (PP)} 646 o Prune Pending Timer (PPT) 648 o Join/Prune Expiry Timer (ET) 650 (*,G) Assert Winner State 652 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 653 "I won Assert" (W)} 655 o Assert Timer (AT) 657 o Assert winner's IP Address 659 o Assert winner's Assert Metric 661 Not interface specific: 663 o Upstream Join/Prune Timer (JT) 665 o Last RP Used 667 o Last RPF Neighbor towards RP that was used 669 Local membership is the result of the local membership mechanism (such 670 as IGMP or MLD) running on that interface. It need not be kept if this 671 router is not the DR on that interface unless this router won a (*,G) 672 assert on this interface for this group, although implementations may 673 optionally keep this state in case they become the DR or assert winner. 674 We recommend storing this information if possible, as it reduces latency 675 converging to stable operating conditions after a failure causing a 676 change of DR. This information is used by the pim_include(*,G) macro 677 described in section 4.1.6. 679 PIM (*,G) Join/Prune state is the result of receiving PIM (*,G) 680 Join/Prune messages on this interface, and is specified in section 681 4.5.2. The state is used by the macros that calculate the outgoing 682 interface list in section 4.1.6, and in the JoinDesired(*,G) macro 683 (defined in section 4.5.6) that is used in deciding whether a Join(*,G) 684 should be sent upstream. 686 (*,G) Assert Winner state is the result of sending or receiving (*,G) 687 Assert messages on this interface. It is specified in section 4.6.2. 689 The upstream (*,G) Join/Prune timer is used to send out periodic 690 Join(*,G) messages, and to override Prune(*,G) messages from peers on an 691 upstream LAN interface. 693 The last RP used must be stored because if the RP Set changes (section 694 4.8) then state must be torn down and rebuilt for groups whose RP 695 changes. 697 The last RPF neighbor towards the RP is stored because if the MRIB 698 changes then the RPF neighbor towards the RP may change. If it does so, 699 then we need to trigger a new Join(*,G) to the new upstream neighbor and 700 a Prune(*,G) to the old upstream neighbor. Similarly, if a router 701 detects through a changed GenID in a Hello message that the upstream 702 neighbor towards the RP has rebooted, then it should re-instantiate 703 state by sending a Join(*,G). These mechanisms are specified in Section 704 4.5.6. 706 4.1.4. (S,G) State 708 For every source/group pair (S,G) a router keeps the following state: 710 (S,G) state: 712 For each interface: 714 Local Membership: 715 State: One of {"NoInfo", "Include"} 717 PIM (S,G) Join/Prune State: 719 o State: One of {"NoInfo" (NI), "Join" (J), 720 "PrunePending" (PP)} 722 o Prune Pending Timer (PPT) 724 o Join/Prune Expiry Timer (ET) 726 (S,G) Assert Winner State 728 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 729 "I won Assert" (W)} 731 o Assert Timer (AT) 733 o Assert winner's IP Address 735 o Assert winner's Assert Metric 737 Not interface specific: 739 o Upstream (S,G) Join/Prune Timer (JT) 741 o Last RPF Neighbor towards S that was used 743 o SPT bit (indicates (S,G) state is active) 745 o (S,G) KeepAlive Timer (KAT) 747 Local membership is the result of the local source-specific membership 748 mechanism (such as IGMP version 3) running on that interface and 749 specifying that this particular source should be included. As stored 750 here, this state is the resulting state after any IGMPv3 inconsistencies 751 have been resolved. It need not be kept if this router is not the DR on 752 that interface unless this router won a (S,G) assert on this interface 753 for this group. However, we recommend storing this information if 754 possible, as it reduces latency converging to stable operating 755 conditions after a failure causing a change of DR. This information is 756 used by the pim_include(S,G) macro described in section 4.1.6. 758 PIM (S,G) Join/Prune state is the result of receiving PIM (S,G) 759 Join/Prune messages on this interface, and is specified in section 760 4.5.2. The state is used by the macros that calculate the outgoing 761 interface list in section 4.1.6, and in the JoinDesired(S,G) macro 762 (defined in section 4.5.7) that is used in deciding whether a Join(S,G) 763 should be sent upstream. 765 (S,G) Assert Winner state is the result of sending or receiving (S,G) 766 Assert messages on this interface. It is specified in section 4.6.1. 768 The upstream (S,G) Join/Prune timer is used to send out periodic 769 Join(S,G) messages, and to override Prune(S,G) messages from peers on an 770 upstream LAN interface. 772 The last RPF neighbor towards S is stored because if the MRIB changes 773 then the RPF neighbor towards S may change. If it does so, then we need 774 to trigger a new Join(S,G) to the new upstream neighbor and a Prune(S,G) 775 to the old upstream neighbor. Similarly, if the router detects through 776 a changed GenID in a Hello message that the upstream neighbor towards S 777 has rebooted, then it should re-instantiate state by sending a 778 Join(S,G). These mechanisms are specified in Section 4.5.7. 780 The SPTbit is used to indicate whether forwarding is taking place on the 781 (S,G) Shortest Path Tree (SPT) or on the (*,G) tree. A router can have 782 (S,G) state and still be forwarding on (*,G) state during the interval 783 when the source-specific tree is being constructed. When SPTbit is 784 FALSE, only (*,G) forwarding state is used to forward packets from S to 785 G. When SPTbit is TRUE, both (*,G) and (S,G) forwarding state are used. 787 The (S,G) Keepalive Timer is updated by data being forwarded using this 788 (S,G) forwarding state. It is used to keep (S,G) state alive in the 789 absence of explicit (S,G) Joins. Amongst other things, this is 790 necessary for the so-called "turnaround rules" - when the RP uses (S,G) 791 joins to stop encapsulation, and then (S,G) prunes to prevent traffic 792 from unnecessarily reaching the RP. 794 4.1.5. (S,G,rpt) State 796 For every source/group pair (S,G) for which a router also has (*,G) 797 state, it also keeps the following state: 799 (S,G,rpt) state: 801 For each interface: 803 Local Membership: 804 State: One of {"NoInfo", "Exclude"} 806 PIM (S,G,rpt) Join/Prune State: 808 o State: One of {"NoInfo", "Pruned", "PrunePending"} 810 o Prune Pending Timer (PPT) 812 o Join/Prune Expiry Timer (ET) 814 Not interface specific: 816 Upstream (S,G,rpt) Join/Prune State: 818 o State: One of {"NotJoined(*,G)", 819 "NotPruned(S,G,rpt)", "Pruned(S,G,rpt)"} 821 o Override Timer (OT) 823 Local membership is the result of the local source-specific membership 824 mechanism (such as IGMPv3) running on that interface and specifying that 825 although there is (*,G) Include state, this particular source should be 826 excluded. As stored here, this state is the resulting state after any 827 IGMPv3 inconsistencies between LAN members have been resolved. It need 828 not be kept if this router is not the DR on that interface unless this 829 router won a (*,G) assert on this interface for this group. However, we 830 recommend storing this information if possible, as it reduces latency 831 converging to stable operating conditions after a failure causing a 832 change of DR. This information is used by the pim_exclude(S,G) macro 833 described in section 4.1.6. 835 PIM (S,G,rpt) Join/Prune state is the result of receiving PIM (S,G,rpt) 836 Join/Prune messages on this interface, and is specified in section 837 4.5.4. The state is used by the macros that calculate the outgoing 838 interface list in section 4.1.6, and in the rules for adding 839 Prune(S,G,rpt) messages to Join(*,G) messages specified in section 840 4.5.8. 842 The upstream (S,G,rpt) Join/Prune state is used along with the Override 843 Timer to send the correct override messages in response to Join/Prune 844 messages sent by upstream peers on a LAN. This state and behavior are 845 specified in section 4.5.9. 847 4.1.6. State Summarization Macros 849 Using this state, we define the following "macro" definitions which we 850 will use in the descriptions of the state machines and pseudocode in the 851 following sections. 853 The most important macros are those that define the outgoing interface 854 list (or "olist") for the relevant state. An olist can be "immediate" 855 if it is built directly from the state of the relevant type. For 856 example, the immediate_olist(S,G) is the olist that would be built if 857 the router only had (S,G) state and no (*,G) or (S,G,rpt) state. In 858 contrast, the "inherited" olist inherits state from other types. For 859 example, the inherited_olist(S,G) is the olist that is relevant for 860 forwarding a packet from S to G using both source-specific and group- 861 specific state. 863 There is no immediate_olist(S,G,rpt) as (S,G,rpt) state is negative 864 state - it removes interfaces in the (*,G) olist from the olist that is 865 actually used to forward traffic. The inherited_olist(S,G,rpt) is 866 therefore the olist that would be used for a packet from S to G 867 forwarding on the RP tree. It is a strict subset of 868 immediate_olist(*,G). 870 Generally speaking, the inherited olists are used for forwarding, and 871 the immediate_olists are used to make decisions about state maintenance. 873 immediate_olist(*,*,RP) = 874 joins(*,*,RP) 876 immediate_olist(*,G) = 877 joins(*,G) (+) pim_include(*,G) (-) lost_assert(*,G) 879 immediate_olist(S,G) = 880 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) 882 inherited_olist(S,G,rpt) = 883 ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 884 (+) ( pim_include(*,G) (-) pim_exclude(S,G)) 885 (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) ) 887 inherited_olist(S,G) = 888 inherited_olist(S,G,rpt) (+) immediate_olist(S,G) 890 The macros pim_include(*,G) and pim_include(S,G) indicate the interfaces 891 to which traffic might be forwarded because of hosts that are local 892 members on that interface. Note that normally only the DR cares about 893 local membership, but when an assert happens, the assert winner takes 894 over responsibility for forwarding traffic to local members that have 895 requested traffic on a group or source/group pair. 897 pim_include(*,G) = 898 { all interfaces I such that: 899 ( ( I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) 900 OR AssertWinner(*,G,I) == me ) 901 AND local_receiver_include(*,G,I) } 903 pim_include(S,G) = 904 { all interfaces I such that: 905 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) 906 OR AssertWinner(S,G,I) == me ) 907 AND local_receiver_include(S,G,I) } 909 pim_exclude(S,G) = 910 { all interfaces I such that: 911 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) 912 OR AssertWinner(S,G,I) == me ) 913 AND local_receiver_exclude(S,G,I) } 915 The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD 916 module or other local membership mechanism has determined that there are 917 local members on interface I that desire to receive traffic sent 918 specifically by S to G. "local_receiver_include(*,G,I)" is true if the 919 IGMP/MLD module or other local membership mechanism has determined that 920 there are local members on interface I that desire to receive all 921 traffic sent to G. "local_receiver_exclude(S,G,I) is true if 922 local_receiver_include(*,G,I) is true but none of the local members 923 desire to receive traffic from S. 925 The set "joins(*,*,RP)" is the set of all interfaces on which the router 926 has received (*,*,RP) Joins: 928 joins(*,*,RP) = 929 { all interfaces I such that 930 DownstreamJPState(*,*,RP,I) is either Join or 931 PrunePending } 933 DownstreamJPState(*,*,RP,I) is the state of the finite state machine in 934 section 4.5.1. 936 The set "joins(*,G)" is the set of all interfaces on which the router 937 has received (*,G) Joins: 939 joins(*,G) = 940 { all interfaces I such that 941 DownstreamJPState(*,G,I) is either Join or PrunePending } 943 DownstreamJPState(*,G,I) is the state of the finite state machine in 944 section 4.5.2. 946 The set "joins(S,G)" is the set of all interfaces on which the router 947 has received (S,G) Joins: 949 joins(S,G) = 950 { all interfaces I such that 951 DownstreamJPState(S,G,I) is either Join or PrunePending } 953 DownstreamJPState(S,G,I) is the state of the finite state machine in 954 section 4.5.3. 956 The set "prunes(S,G,rpt)" is the set of all interfaces on which the 957 router has received (*,G) joins and (S,G,rpt) prunes. 959 prunes(S,G,rpt) = 960 { all interfaces I such that 961 DownstreamJPState(S,G,rpt,I) is Prune or PruneTmp } 963 DownstreamJPState(S,G,rpt,I) is the state of the finite state machine in 964 section 4.5.4. 966 The set "lost_assert(*,G)" is the set of all interfaces on which the 967 router has received (*,G) joins but has lost a (*,G) assert. The macro 968 lost_assert(*,G,I) is defined in Section 4.6.5. 970 lost_assert(*,G) = 971 { all interfaces I such that 972 lost_assert(*,G,I) == TRUE } 974 The set "lost_assert(S,G,rpt)" is the set of all interfaces on which the 975 router has received (*,G) joins but has lost an (S,G) assert. The macro 976 lost_assert(S,G,rpt,I) is defined in Section 4.6.5. 978 lost_assert(S,G,rpt) = 979 { all interfaces I such that 980 lost_assert(S,G,rpt,I) == TRUE } 982 The set "lost_assert(S,G)" is the set of all interfaces on which the 983 router has received (S,G) joins but has lost an (S,G) assert. The macro 984 lost_assert(S,G,I) is defined in Section 4.6.5. 986 lost_assert(S,G) = 987 { all interfaces I such that 988 lost_assert(S,G,I) == TRUE } 990 The following pseudocode macro definitions are also used in many places 991 in the specification. Basically RPF' is the RPF neighbor towards an RP 992 or source unless a PIM-Assert has overridden the normal choice of 993 neighbor. 995 neighbor RPF'(*,G) { 996 if ( I_Am_Assert_Loser(*,G,RPF_interface(RP(G))) ) { 997 return AssertWinner(*, G, RPF_interface(RP(G)) ) 998 } else { 999 return MRIB.next_hop( RP(G) ) 1000 } 1001 } 1003 neighbor RPF'(S,G,rpt) { 1004 if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) { 1005 return AssertWinner(S, G, RPF_interface(RP(G)) ) 1006 } else { 1007 return RPF'(*,G) 1008 } 1009 } 1011 neighbor RPF'(S,G) { 1012 if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) { 1013 return AssertWinner(S, G, RPF_interface(S) ) 1014 } else { 1015 return MRIB.next_hop( S ) 1016 } 1017 } 1019 RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data packets 1020 should be coming and to which joins should be sent on the RP tree and 1021 SPT respectively. 1023 RPF'(S,G,rpt) is basically RPF'(*,G) modified by the result of an 1024 Assert(S,G) on RPF_interface(RP(G)). In such a case, packets from S 1025 will be originating from a different router than RPF'(*,G). If we only 1026 have active (*,G) Join state, we need to accept packets from 1027 RPF'(S,G,rpt), and add a Prune(S,G,rpt) to the periodic Join(*,G) 1028 messages that we send to RPF'(*,G) (See Section 4.5.8). 1030 The function MRIB.next_hop( S ) returns the next-hop PIM neighbor toward 1031 the host S, as indicated by the current MRIB. If S is directly 1032 adjacent, then MRIB.next_hop( S ) returns NULL. At the RP for G, 1033 MRIB.next_hop( RP(G )) returns NULL. 1035 I_Am_Assert_Loser(S, G, I) is true if the Assert start machine (in 1036 section 4.6.1) for (S,G) on Interface I is in "I am Assert Loser" state. 1038 I_Am_Assert_Loser(*, G, I) is true if the Assert start machine (in 1039 section 4.6.2) for (*,G) on Interface I is in "I am Assert Loser" state. 1041 4.2. Data Packet Forwarding Rules 1043 The PIM-SM packet forwarding rules are defined below in pseudocode. 1045 iif is the incoming interface of the packet. 1046 S is the source address of the packet. 1047 G is the destination address of the packet (group address). 1048 RP is the address of the Rendezvous Point for this group. 1049 RPF_interface(S) is the interface the MRIB indicates would be used 1050 to route packets to S. 1051 RPF_interface(RP) is the interface the MRIB indicates would be used 1052 to route packets to RP, except at the RP when it is the 1053 decapsulation interface (the "virtual" interface on which register 1054 packets are received). 1056 First, we restart (or start) the Keepalive timer if the source is on a 1057 directly connected subnet. 1059 Second, we check to see if the SPT bit should be set because we've now 1060 switched from the RP tree to the SPT. 1062 Next we check to see whether the packet should be accepted based on TIB 1063 state and the interface that the packet arrived on. 1065 If the packet should be forwarded using (S,G) state, we then build an 1066 outgoing interface list for the packet. If this list is not empty, then 1067 we restart the (S,G) state keepalive timer. 1069 If the packet should be forwarded using (*,*,RP) or (*,G) state, then we 1070 just build an outgoing interface list for the packet. We also check if 1071 we should initiate a switch to start receiving this source on a shortest 1072 path tree. 1074 Finally we remove the incoming interface from the outgoing interface 1075 list we've created, and if the resulting outgoing interface list is not 1076 empty, we forward the packet out of those interfaces. 1078 On receipt on a data from S to G on interface iif: 1080 if( DirectlyConnected(S) == TRUE ) { 1081 set KeepaliveTimer(S,G) to Keepalive_Period 1082 # Note: register state transition may happen as a result 1083 # of restarting KeepaliveTimer, and must be dealt with here. 1084 } 1086 Update_SPTbit(S,G,iif) 1087 oiflist = NULL 1089 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 1090 oiflist = inherited_olist(S,G) 1091 if( oiflist != NULL ) { 1092 restart KeepaliveTimer(S,G) 1093 } 1094 } else if( iif == RPF_interface(RP) AND SPTbit(S,G) == FALSE) { 1095 oiflist = inherited_olist(S,G,rpt) 1096 CheckSwitchToSpt(S,G) 1097 } else { 1098 # Note: RPF check failed 1099 if ( SPTbit(S,G) == TRUE AND iif is in inherited_olist(S,G) ) { 1100 send Assert(S,G) on iif 1101 } else if ( SPTbit(S,G) == FALSE AND 1102 iif is in inherited_olist(S,G,rpt) { 1103 send Assert(*,G) on iif 1104 } 1105 } 1107 oiflist = oiflist (-) iif 1108 forward packet on all interfaces in oiflist 1110 This pseudocode employs several "macro" definitions: 1112 DirectlyConnected(S) is TRUE if the source S is on any subnet that is 1113 directly connected to this router (or for packets originating on this 1114 router). 1116 inherited_olist(S,G) and inherited_olist(S,G,rpt) are defined in Section 1117 4.1. 1119 Basically inherited_olist(S,G) is the outgoing interface list for 1120 packets forwarded on (S,G) state taking into account (*,*,RP) state, 1121 (*,G) state, asserts, etc. 1123 inherited_olist(S,G,rpt) is the outgoing interface for packets forwarded 1124 on (*,*,RP) or (*,G) state taking into account (S,G,rpt) prune state, 1125 and asserts, etc. 1127 Update_SPTbit(S,G,iif) is defined in section 4.2.2. 1129 CheckSwitchToSpt(S,G) is defined in section 4.2.1. 1131 UpstreamJPState(S,G) is the state of the finite state machine in section 1132 4.5.7. 1134 Keepalive_Period is defined in Section 4.11. 1136 Data triggered PIM-Assert messages sent from the above forwarding code 1137 should be rate-limited in a implementation-dependent manner. 1139 4.2.1. Last hop switchover to the SPT 1141 In Sparse-Mode PIM, last-hop routers join the shared tree towards the 1142 RP. Once traffic from sources to joined groups arrives at a last-hop 1143 router it has the option of switching to receive the traffic on a 1144 shortest path tree (SPT). 1146 The decision for a router to switch to the SPT is controlled as follows: 1148 void 1149 CheckSwitchToSpt(S,G) { 1150 if ( ( pim_include(*,G) (-) pim_exclude(S,G) 1151 (+) pim_include(S,G) != NULL ) 1152 AND SwitchToSptDesired(S,G) ) { 1153 restart KeepAliveTimer(S,G); 1154 } 1155 } 1157 SwitchToSptDesired(S,G) is a policy function that is implementation 1158 defined. An "infinite threshold" policy can be implemented making 1159 SwitchToSptDesired(S,G) return false all the time. A "switch on first 1160 packet" policy can be implemented by making SwitchToSptDesired(S,G) 1161 return true once a single packet has been received for the source and 1162 group. 1164 4.2.2. Setting and Clearing the (S,G) SPT bit 1166 The (S,G) SPTbit is used to distinguish whether to forward on 1167 (*,*,RP)/(*,G) or on (S,G) state. When switching from the RP tree to 1168 the source tree, there is a transition period when data is arriving due 1169 to upstream (*,*,RP)/(*,G) state while upstream (S,G) state is being 1170 established during which time a router should continue to forward only 1171 on (*,*,RP)/(*,G) state. This prevents temporary black-holes that would 1172 be caused by sending a Prune(S,G,rpt) before the upstream (S,G) state 1173 has finished being established. 1175 Thus, when a packet arrives, the (S,G) SPTbit is updated as follows: 1177 void 1178 Update_SPTbit(S,G,iif) { 1179 if ( iif == RPF_interface(S) 1180 AND JoinDesired(S,G) == TRUE 1181 AND ( DirectlyConnected(S) == TRUE 1182 OR RPF_interface(S) != RPF_interface(RP) 1183 OR inherited_olist(S,G,rpt) == NULL 1184 OR RPF'(S,G) == RPF'(*,G) ) ) { 1185 Set SPTbit(S,G) to TRUE 1186 } 1187 } 1189 Additionally a router sets SPTbit(S,G) to TRUE when it receives an 1190 Assert(S,G) on RPF_interface(S). 1192 JoinDesired(S,G) is defined in Section 4.5.7, and indicates whether we 1193 have the appropriate (S,G) Join state to wish to send a Join(S,G) 1194 upstream. 1196 Basically Update_SPTbit will set the SPT bit if we have the appropriate 1197 (S,G) join state and the packet arrived on the correct upstream 1198 interface for S, and one or more of the following conditions applies: 1200 1. The source is directly connected, in which case the switch to the 1201 SPT is a no-op. 1203 2. The RPF interface to S is different from the RPF interface to the 1204 RP. The packet arrived on RPF_interface(S), and so the SPT must 1205 have been completed. 1207 3. No-one wants the packet on the RP tree. 1209 4. RPF'(S,G) == RPF'(*,G). In this case the router will never be able 1210 to tell if the SPT has been completed, so it should just switch 1211 immediately. 1213 In the case where the RPF interface is the same for the RP and for S, 1214 but RPF'(S,G) and RPF'(*,G) differ, then we wait for an Assert(S,G) 1215 which indicates that the upstream router with (S,G) state believes the 1216 SPT has been completed. However item (3) above is needed because there 1217 may not be any (*,G) state to trigger an Assert(S,G) to happen. 1219 The SPT bit is cleared in the (S,G) upstream state machine (see Section 1220 4.5.7) when JoinDesired(S,G) becomes FALSE. 1222 4.3. Designated Routers (DR) and Hello Messages 1224 A shared-media LAN like Ethernet may have multiple PIM-SM routers 1225 connected to it. If the LAN has directly connected hosts, then a single 1226 one of these routers, the DR, will act on behalf of those hosts with 1227 respect to the PIM-SM protocol. Because the distinction between LANs 1228 and point-to-point interfaces can sometimes be blurred, and because 1229 routers may also have multicast host functionality, the PIM-SM 1230 specification makes no distinction between the two. Thus DR election 1231 will happen on all interfaces, LAN or otherwise. 1233 DR election is performed using Hello messages. Hello messages are also 1234 the way that option negotiation takes place in PIM, so that additional 1235 functionality can be enabled, or parameters tuned. 1237 4.3.1. Sending Hello Messages 1239 PIM-Hello messages are sent periodically on each PIM-enabled interface. 1240 They allow a router to learn about the neighboring PIM routers on each 1241 interface. Hello messages are also the mechanism used to elect a 1242 Designated Router (DR), and to negotiate additional capabilities A 1243 router must record the Hello information received from each PIM 1244 neighbor. 1246 Hello messages MUST be sent on all active interfaces, including physical 1247 point-to-point links, and are multicast to address 224.0.0.13 (the ALL- 1248 PIM-ROUTERS group). 1250 We note that some implementations do not send Hello messages 1251 on point-to-point interfaces. This is non-compliant behavior. 1252 A compliant PIM router MUST send Hello messages, even on 1253 point-to-point interfaces. 1255 A per interface hello timer (HT(I)) is used to trigger sending Hello 1256 messages on each active interface. When PIM is enabled on an interface 1257 or a router first starts, the hello timer of that interface is set to a 1258 random value between 0 and Triggered_Hello_Delay. This prevents 1259 synchronization of Hello messages if multiple routers are powered on 1260 simultaneously. After the initial randomized interval, Hello messages 1261 must be sent every Hello_Period seconds. The hello timer should not be 1262 reset except when it expires. 1264 Note that neighbors will not accept Join/Prune or Assert messages from a 1265 router unless they have first heard a Hello message from that router. 1266 Thus if a router needs to send a Join/Prune or Assert message on an 1267 interface on which it has not yet sent a Hello message, then it MUST 1268 immediately send the relevant without Hello message without waiting for 1269 the Hello timer to expire, followed by the Join/Prune or Assert message. 1271 The DR_Election_Priority Option allows a network administrator to give 1272 preference to a particular router in the DR election process by giving 1273 it a numerically larger DR Election Priority. The DR_Election_Priority 1274 Option SHOULD be included in every Hello message, even if no DR election 1275 priority is explicitly configured on that interface. This is necessary 1276 because priority-based DR election is only enabled when all neighbors on 1277 an interface advertise that they are capable of using the DR Election 1278 Priority Option. The default priority is 1. 1280 The Generation_Identifier (GenID) Option SHOULD be included in all Hello 1281 messages. The GenID option contains a randomly generated 32-bit value 1282 that is regenerated each time PIM forwarding is started or restarted on 1283 the interface, including when the router itself restarts. When a Hello 1284 message with a new GenID is received from a neighbor, any old Hello 1285 information about that neighbor SHOULD be discarded and superseded by 1286 the information from the new Hello message. This may cause a new DR to 1287 be chosen on that interface. 1289 The LAN_Prune_Delay Option SHOULD be included in all Hello messages sent 1290 on multi-access LANs. This option advertises a router's capability to 1291 use values other than the default for the Propagation_Delay and 1292 Override_Interval which affect the setting of the Prune Pending, 1293 Upstream Join and Override Timers (defined in section 4.11). 1295 To allow new or rebooting routers to learn of PIM neighbors quickly, 1296 when a Hello message is received from a new neighbor, or a Hello message 1297 with a new GenID is received from an existing neighbor, a new Hello 1298 message should be sent on this interface after a randomized delay 1299 between 0 and Triggered_Hello_Delay. This triggered message need not 1300 change the timing of the scheduled periodic message. If a router needs 1301 to send a Join/Prune to the new neighbor or send an Assert message in 1302 response to an Assert message from the new neighbor before this 1303 randomized delay has expired, then it MUST immediately send the relevant 1304 without Hello message without waiting for the Hello timer to expire, 1305 followed by the Join/Prune or Assert message. If it does not do this, 1306 then the new neighbor will discard the Join/Prune or Assert message. 1308 Before an interface goes down or changes IP address, a Hello message 1309 with a zero HoldTime should be sent immediately (with the old IP address 1310 if the IP address changed). This will cause PIM neighbors to remove 1311 this neighbor (or its old IP address) immediately. 1313 4.3.2. DR Election 1315 When a PIM-Hello message is received on interface I the following 1316 information about the sending neighbor is recorded: 1318 neighbor.interface 1319 The interface on which the Hello message arrived. 1321 neighbor.ip_address 1322 The IP address of the PIM neighbor. 1324 neighbor.genid 1325 The Generation ID of the PIM neighbor. 1327 neighbor.dr_priority 1328 The DR Priority field of the PIM neighbor if it is present in 1329 the Hello message. 1331 neighbor.dr_priority_present 1332 A flag indicating if the DR Priority field was present in the 1333 Hello message. 1335 neighbor.timeout 1336 A timer value to time out the neighbor state when it becomes 1337 stale. 1338 The Neighbor Liveness Timer (NLT(N,I)) is reset to 1339 Hello_Holdtime (from the Hello Holdtime option) whenever a 1340 Hello message is received containing a Holdtime option, or to 1341 Default_Hello_Holdtime if the Hello message does not contain 1342 the Holdtime option. 1344 Neighbor state is deleted when the neighbor timeout expires. 1346 The function for computing the DR on interface I is: 1348 host 1349 DR(I) { 1350 dr = me 1351 for each neighbor on interface I { 1352 if ( dr_is_better( neighbor, dr, I ) == TRUE ) { 1353 dr = neighbor 1354 } 1355 } 1356 return dr 1357 } 1359 The function used for comparing DR "metrics" on interface I is: 1361 bool 1362 dr_is_better(a,b,I) { 1363 if( there is a neighbor n on I for which n.dr_priority_present 1364 is false ) { 1365 return a.ip_address > b.ip_address 1366 } else { 1367 return ( a.dr_priority > b.dr_priority ) OR 1368 ( a.dr_priority == b.dr_priority AND 1369 a.ip_address > b.ip_address ) 1370 } 1371 } 1373 The trivial function I_am_DR(I) is defined to aid readability: 1375 bool 1376 I_am_DR(I) { 1377 return DR(I) == me 1378 } 1380 The DR election priority is a 32-bit unsigned number and the numerically 1381 larger priority is always preferred. A router's idea of the current DR 1382 on an interface can change when a PIM-Hello message is received, when a 1383 neighbor times out, or when a router's own DR priority changes. If the 1384 router becomes the DR or ceases to be the DR, this will normally cause 1385 the DR Register state-machine to change state. Subsequent actions are 1386 determined by that state-machine. 1388 We note that some PIM implementations do not send Hello 1389 messages on point-to-point interfaces, and so cannot perform 1390 DR election on such interfaces. This in non-compliant 1391 behavior. DR election MUST be performed on ALL active PIM-SM 1392 interfaces. 1394 4.3.3. Reducing Prune Propagation Delay on LANs 1396 In addition to the information recorded for the DR Election, the 1397 following per neighbor information is obtained from the LAN Prune Delay 1398 Hello option: 1400 neighbor.lan_prune_delay_present 1401 A flag indicating if the LAN Prune Delay option was present in 1402 the Hello message. 1404 neighbor.tracking_support 1405 A flag storing the value of the T bit in the LAN Prune Delay 1406 option if it is present in the Hello message. This indicates 1407 the neighbor's capability to disable Join message suppression. 1409 neighbor.lan_delay 1410 The LAN Delay field of the LAN Prune Delay option (if present) 1411 in the Hello message. 1413 neighbor.override_interval 1414 The Override_Interval field of the LAN Prune Delay option (if 1415 present) in the Hello message. 1417 The additional state described above is deleted along with the DR 1418 neighbor state when the neighbor timeout expires. 1420 Just like the DR priority option, the information provided in the LAN 1421 Prune Delay option is not used unless all neighbors on a link advertise 1422 the option. The function below computes this state: 1424 bool 1425 lan_delay_enabled(I) { 1426 for each neighbor on interface I { 1427 if ( neighbor.lan_prune_delay_present == false ) { 1428 return false 1429 } 1430 } 1431 return true 1432 } 1434 The LAN Delay inserted by a router in the LAN Prune Delay option 1435 expresses the expected message propagation delay on the link and should 1436 be configurable by the system administrator. It is used by upstream 1437 routers to figure out how long they should wait for a Join override 1438 message before pruning an interface. 1440 PIM implementors should enforce a lower bound on the permitted values 1441 for this delay to allow for scheduling and processing delays within 1442 their router. Such delays may cause received messages to be processed 1443 later as well as triggered messages to be sent later than intended. 1444 Setting this LAN Prune Delay to too low a value may result in temporary 1445 forwarding outages because a downstream router will not be able to 1446 override a neighbor's Prune message before the upstream neighbor stops 1447 forwarding. 1449 When all routers on a link are in a position to negotiate a different 1450 than default Propagation Delay, the largest value from those advertised 1451 by each neighbor is chosen. The function for computing the Propagation 1452 Delay of interface I is: 1454 time_interval 1455 Propagation_Delay(I) { 1456 if ( lan_delay_enabled(I) == false ) { 1457 return LAN_delay_default 1458 } 1459 delay = 0 1460 for each neighbor on interface I { 1461 if ( neighbor.lan_delay > delay ) { 1462 delay = neighbor.lan_delay 1463 } 1464 } 1465 return delay 1466 } 1468 To avoid synchronization of override messages when multiple downstream 1469 routers share a multi-access link, sending of such messages is delayed 1470 by a small random amount of time. The period of randomization should 1471 represent the size of the PIM router population on the link. Each 1472 router expresses its view of the amount of randomization necessary in 1473 the Override Delay field of the LAN Prune Delay option. 1475 When all routers on a link are in a position to negotiate a different 1476 than default Override Delay, the largest value from those advertised by 1477 each neighbor is chosen. The function for computing the Override 1478 Interval of interface I is: 1480 time_interval 1481 Override_Interval(I) { 1482 if ( lan_delay_enabled(I) == false ) { 1483 return t_override_default 1484 } 1485 delay = 0 1486 for each neighbor on interface I { 1487 if ( neighbor.override_interval > delay ) { 1488 delay = neighbor.override_interval 1489 } 1490 } 1491 return delay 1492 } 1494 Although the mechanisms are not specified in this document, it is 1495 possible for upstream routers to explicitly track the join membership of 1496 individual downstream routers if Join suppression is disabled. A router 1497 can advertise its willingness to disable Join suppression by using the T 1498 bit in the LAN Prune Delay Hello option. Unless all PIM routers on a 1499 link negotiate this capability, explicit tracking and the disabling of 1500 the Join suppression mechanism are not possible. The function for 1501 computing the state of Suppression on interface I is: 1503 bool 1504 Suppression_Enabled(I) { 1505 if ( lan_delay_enabled(I) == false ) { 1506 return true 1507 } 1508 for each neighbor on interface I { 1509 if ( neighbor.tracking_support == false ) { 1510 return true 1511 } 1512 } 1513 return false 1514 } 1516 Note that the setting of Suppression_Enabled(I) affects the value of 1517 t_suppressed (see section 4.11). 1519 4.4. PIM Register Messages 1521 Overview 1523 The Designated Router (DR) on a LAN or point-to-point link encapsulates 1524 multicast packets from local sources to the RP for the relevant group 1525 unless it recently received a Register Stop message for that (S,G) or 1526 (*,G) from the RP. When the DR receives a Register Stop message from 1527 the RP, it starts a Register Stop timer to maintain this state. Just 1528 before the Register Stop timer expires, the DR sends a Null-Register 1529 Message to the RP to allow the RP to refresh the Register Stop 1530 information at the DR. If the Register Stop timer actually expires, the 1531 DR will resume encapsulating packets from the source to the RP. 1533 4.4.1. Sending Register Messages from the DR 1535 Every PIM-SM router has the capability to be a DR. The state machine 1536 below is used to implement Register functionality. For the purposes of 1537 specification, we represent the mechanism to encapsulate packets to the 1538 RP as a Register-Tunnel interface, which is added to or removed from the 1539 (S,G) olist. The tunnel interface then takes part in the normal packet 1540 forwarding rules is specified in Section 4.2. 1542 If register state is maintained, it is maintained only for directly 1543 connected sources, and is per-(S,G). There are four states in the DR's 1544 per-(S,G) Register state-machine: 1546 Join (J) 1547 The register tunnel is "joined" (the join is actually implicit, but 1548 the DR acts as if the RP has joined the DR on the tunnel 1549 interface). 1551 Prune (P) 1552 The register tunnel is "pruned" (this occurs when a Register Stop 1553 is received). 1555 Join Pending (JP) 1556 The register tunnel is pruned but the DR is contemplating adding it 1557 back. 1559 No Info (NI) 1560 No information. This is the initial state, and the state when the 1561 router is not the DR. 1563 In addition, a RegisterStop timer (RST) is kept if the state machine in 1564 not in the No Info state. 1566 Figure 1: Per-(S,G) register state-machine at a DR in tabular form 1568 +-----------++------------------------------------------------------------------------------------------+ 1569 | || Event | 1570 | ++------------------+------------------+----------------------+--------------+--------------+ 1571 |Prev State ||Register-Stop |Could-Register | Could-Register |Register- |RP changed | 1572 | ||Timer expires |->True | ->False |Stop | | 1573 | || | | |received | | 1574 +-----------++------------------+------------------+----------------------+--------------+--------------+ 1575 |No Info ||- |-> J state | - |- |- | 1576 |(NI) || |add reg tunnel | | | | 1577 +-----------++------------------+------------------+----------------------+--------------+--------------+ 1578 | ||- |- | -> NI state |-> P state |-> J state | 1579 | || | | remove reg tunnel |remove |update reg | 1580 | || | | |tunnel; |tunnel | 1581 |Join (J) || | | |set | | 1582 | || | | |Register- | | 1583 | || | | |Stop | | 1584 | || | | |timer(*) | | 1585 +-----------++------------------+------------------+----------------------+--------------+--------------+ 1586 | ||-> J state |- | -> NI state |-> P state |-> J state | 1587 |Join ||add reg tunnel | | remove reg tunnel |set |add reg | 1588 |Pending || | | |Register- |tunnel; | 1589 |(JP) || | | |Stop |cancel | 1590 | || | | |timer(*) |Register- | 1591 | || | | | |Stop timer | 1592 +-----------++------------------+------------------+----------------------+--------------+--------------+ 1593 | ||-> JP state |- | -> NI state |- |-> J state | 1594 | ||set Register- | | remove reg tunnel | |add reg | 1595 |Prune (P) ||Stop | | | |tunnel; | 1596 | ||timer(**); | | | |cancel | 1597 | ||send null | | | |Register- | 1598 | ||register | | | |Stop timer | 1599 +-----------++------------------+------------------+----------------------+--------------+--------------+ 1601 Notes: 1603 (*) The RegisterStopTimer is set to a random value chosen uniformly from 1604 the interval ( 0.5 * Register_Suppression_Time, 1.5 * 1605 Register_Suppression_Time) minus Register_Probe_Time; 1607 Subtracting off Register_Probe_Time is a bit unnecessary because it 1608 is really small compared to Register_Suppression_Time, but was in 1609 the old spec and is kept for compatibility. 1611 (**) The RegisterStopTimer is set to Register_Probe_Time. 1613 The following actions are defined: 1615 Add Register Tunnel 1617 A Register-Tunnel virtual interface, VI, is created (if it doesn't 1618 already exist) with its encapsulation target being RP(G). 1619 DownstreamJPState(S,G,VI) is set to Join state, causing the tunnel 1620 interface to be added to immediate_olist(S,G). 1622 Remove Register Tunnel 1624 VI is the Register-Tunnel virtual interface with encapsulation target of 1625 RP(G). DownstreamJPState(S,G,VI) is set to NoInfo state, causing the 1626 tunnel interface to be removed from immediate_olist(S,G). If 1627 DownstreamJPState(S,G,VI) is NoInfo for all (S,G), then VI can be 1628 deleted. 1630 Update Register Tunnel 1632 This action occurs when RP(G) changes. 1634 VI_old is the Register-Tunnel virtual interface with encapsulation 1635 target old_RP(G). A Register-Tunnel virtual interface, VI_new, is 1636 created (if it doesn't already exist) with its encapsulation target 1637 being new_RP(G). DownstreamJPState(S,G,VI_old) is set to NoInfo state 1638 and DownstreamJPState(S,G,VI_new) is set to Join state. If 1639 DownstreamJPState(S,G,VI_old) is NoInfo for all (S,G), then VI_old can 1640 be deleted. 1642 Note that we can not simply change the encapsulation target of VI_old 1643 because not all groups using that encapsulation tunnel will have moved 1644 to the same new RP. 1646 CouldRegister(S,G) 1648 The macro "CouldRegister" in the state machine is defined as: 1650 Bool CouldRegister(S,G) { 1651 return ( I_am_DR( RPF_interface(S) ) AND 1652 KeepaliveTimer(S,G) is running AND 1653 DirectlyConnected(S) == TRUE ) 1654 } 1656 Note that on reception of a packet at the DR from a directly connected 1657 source, KeepaliveTimer(S,G) needs to be set by the packet forwarding 1658 rules before computing CouldRegister(S,G) in the register state machine, 1659 or the first packet from a source won't be registered. 1661 Encapsulating data packets in the Register Tunnel 1663 Conceptually, the Register Tunnel is an interface with a smaller MTU 1664 than the underlying IP interface towards the RP. IP fragmentation on 1665 packets forwarded on the Register Tunnel is performed based upon this 1666 smaller MTU. The encapsulating DR may perform Path-MTU Discovery to the 1667 RP to determine the effective MTU of the tunnel. This smaller MTU takes 1668 both the outer IP header and the PIM register header overhead into 1669 account. If a multicast packet is fragmented on the way into the 1670 Register Tunnel, each fragment is encapsulated individually so contains 1671 IP, PIM, and inner IP headers. 1673 In IPv6, an ICMP Fragmentation Required message may be sent by the 1674 encapsulating DR. 1676 Just like any forwarded packet, the TTL of the original data packet is 1677 decremented before it is encapsulated in the Register Tunnel. 1679 The IP ECN bits should be copied from the original packet to the IP 1680 header of the encapsulating packet. They SHOULD NOT be set 1681 independently by the encapsulating router. 1683 The Diffserv Code Point (DSCP) should be copied from the original packet 1684 to the IP header of the encapsulating packet. It MAY be set 1685 independently by the encapsulating router, based upon static 1686 configuration or traffic classification. See [2] for more discussion on 1687 setting the DSCP on tunnels. 1689 Handling RegisterStop(*,G) Messages at the DR 1691 An old RP might send a RegisterStop message with the source address set 1692 to all-zeros. This was the normal course of action in RFC 2326 when the 1693 Register message matched against (*,G) state at the RP, and was defined 1694 as meaning "stop encapsulating all sources for this group". However, 1695 the behavior of such a RegisterStop(*,G) is ambiguous or incorrect in 1696 some circumstances. 1698 We specify that an RP should not send RegisterStop(*,G) messages, but 1699 for compatibility, a DR should be able to accept one if it is received. 1701 A RegisterStop(*,G) should be treated as a RegisterStop(S,G) for all 1702 existing (S,G) Register state machines. A router should not apply a 1703 RegisterStop(*,G) to sources that become active after the 1704 RegisterStop(*,G) was received. 1706 4.4.2. Receiving Register Messages at the RP 1708 When an RP receives a Register message, the course of action is decided 1709 according to the following pseudocode: 1711 packet_arrives_on_rp_tunnel( pkt ) { 1712 if( outer.dst is not one of my addresses ) { 1713 drop the packet silently. 1714 # note that this should not happen if the lower layer is working 1715 } 1716 if( I_am_RP( G ) && outer.dst == RP(G) ) { 1717 restart KeepaliveTimer(S,G) 1718 if(( inherited_olist(S,G) == NULL ) OR SPTbit(S,G)) { 1719 send RegisterStop(S,G) to outer.src 1720 } else { 1721 if( ! pkt.NullRegisterBit ) { 1722 decapsulate and pass the inner packet to the normal 1723 forwarding path for forwarding on the (*,G) tree. 1724 } 1725 } 1726 } else { 1727 send RegisterStop(S,G) to outer.src 1728 # Note (*) 1729 } 1730 } 1732 outer.dst is the IP destination address of the encapsulating header. 1734 outer.src is the IP source address of the encapsulating header, i.e., 1735 the DR's address. 1737 I_am_RP(G) is true if the group-to-RP mapping indicates that this router 1738 is the RP for the group. 1740 Note (*): This may block traffic from S for Register_Suppression_Time if 1741 the DR learned about a new group-to-RP mapping before the RP did. 1742 However, this doesn't matter unless we figure out some way for the 1743 RP to also accept (*,G) joins when it doesn't yet realize that it 1744 is about to become the RP for G. This will all get sorted out once 1745 the RP learns the new group-to-rp mapping. We decided to do 1746 nothing about this and just accept the fact that PIM may suffer 1747 interrupted (*,G) connectivity following an RP change. 1749 KeepaliveTimer(S,G) is restarted at the RP when packets arrive on the 1750 proper tunnel interface. This may cause the upstream (S,G) state 1751 machine to trigger a join if the inherited_olist(S,G) is not NULL; 1752 An RP should preserve (S,G) state that was created in response to a 1753 Register message for at least ( 3 * Register_Suppression_Time ), 1754 otherwise the RP may stop joining (S,G) before the DR for S has 1755 restarted sending registers. Traffic would then be interrupted until 1756 the RegisterStop timer expires at the DR. 1758 Thus, at the RP, KeepaliveTimer(S,G) should be restarted to ( 3 * 1759 Register_Suppression_Time + Register_Probe_Time ). 1761 Just like any forwarded packet, the TTL of the original data packet is 1762 decremented after it is decapsulated from the Register Tunnel. 1764 The IP ECN bits should be copied from the IP header of the Register 1765 packet to the decapsulated packet. 1767 The Diffserv Code Point (DSCP) should be copied from the IP header of 1768 the Register packet to the decapsulated packet. The RP MAY retain the 1769 DSCP of the inner packet, or re-classify the packet and apply a 1770 different DSCP. Scenarios where each of these might be useful are 1771 discussed in [2]. 1773 4.5. PIM Join/Prune Messages 1775 A PIM Join/Prune message consists of a list of groups and a list of 1776 Joined and Pruned sources for each group. When processing a received 1777 Join/Prune message, each Joined or Pruned source for a Group is 1778 effectively considered individually, and applies to one or more of the 1779 following state machines. When considering a Join/Prune message whose 1780 PIM Destination field addresses this router, (*,G) Joins and Prunes can 1781 affect both the (*,G) and (S,G,rpt) downstream state machines, while 1782 (*,*,RP), (S,G) and (S,G,rpt) Joins and Prunes can only affect their 1783 respective downstream state machines. When considering a Join/Prune 1784 message whose PIM Destination field addresses another router, most Join 1785 or Prune messages could affect each upstream state machine. 1787 In general, a PIM Join/Prune message should only be accepted for 1788 processing if it comes from a known PIM neighbor. A PIM router hears 1789 about PIM neighbors through PIM Hello messages. If a router receives a 1790 Join/Prune message from a particular IP source address and it has not 1791 seen a PIM Hello message from that source address, then the Join/Prune 1792 message SHOULD be discarded without further processing. In addition, if 1793 the Hello message from a neighbor was authenticated using IPsec AH (see 1794 section 6.3) then all Join/Prune messages from that neighbor MUST also 1795 be authenticated using IPsec AH. 1797 We note that some older PIM implementations incorrectly fail to send 1798 Hello messages on point-to-point interfaces, so we also RECOMMEND that a 1799 configuration option be provided to allow interoperation with such older 1800 routers, but that this configuration option SHOULD NOT be enabled by 1801 default. 1803 4.5.1. Receiving (*,*,RP) Join/Prune Messages 1805 The per-interface state-machine for receiving (*,*,RP) Join/Prune 1806 Messages is given below. There are three states: 1808 NoInfo (NI) 1809 The interface has no (*,*,RP) Join state and no timers 1810 running. 1812 Join (J) 1813 The interface has (*,*,RP) Join state which will cause us to 1814 forward packets destined for any group handled by RP from this 1815 interface except if there is also (S,G,rpt) prune information 1816 (see Section 4.5.4) or the router lost an assert on this 1817 interface. 1819 PrunePending (PP) 1820 The router has received a Prune(*,*,RP) on this interface from 1821 a downstream neighbor and is waiting to see whether the prune 1822 will be overridden by another downstream router. For 1823 forwarding purposes, the PrunePending state functions exactly 1824 like the Join state. 1826 In addition the state-machine uses two timers: 1828 ExpiryTimer (ET) 1829 This timer is restarted when a valid Join(*,*,RP) is received. 1830 Expiry of the ExpiryTimer causes the interface state to revert 1831 to NoInfo for this RP. 1833 PrunePendingTimer (PPT) 1834 This timer is set when a valid Prune(*,*,RP) is received. 1835 Expiry of the PrunePendingTimer causes the interface state to 1836 revert to NoInfo for this RP. 1838 Figure 2: Downstream (*,*,RP) per-interface state-machine in tabular form 1840 +-------------++---------------------------------------------------------+ 1841 | || Event | 1842 | ++-------------+-------------+--------------+--------------+ 1843 |Prev State ||Receive | Receive | Prune | Expiry Timer | 1844 | ||Join(*,*,RP) | Prune | Pending | Expires | 1845 | || | (*,*,RP) | Timer | | 1846 | || | | Expires | | 1847 +-------------++-------------+-------------+--------------+--------------+ 1848 | ||-> J state | -> NI state | - | - | 1849 |NoInfo (NI) ||start Expiry | | | | 1850 | ||Timer | | | | 1851 +-------------++-------------+-------------+--------------+--------------+ 1852 | ||-> J state | -> PP state | - | -> NI state | 1853 |Join (J) ||restart | start Prune | | | 1854 | ||Expiry Timer | Pending | | | 1855 | || | Timer | | | 1856 +-------------++-------------+-------------+--------------+--------------+ 1857 | ||-> J state | -> PP state | -> NI state | -> NI state | 1858 | ||restart | | Send Prune- | | 1859 |Prune ||Expiry | | Echo(*,*,RP) | | 1860 |Pending (PP) ||Timer; | | | | 1861 | ||cancel Prune | | | | 1862 | ||Pending | | | | 1863 | ||Timer | | | | 1864 +-------------++-------------+-------------+--------------+--------------+ 1866 The transition events "Receive Join(*,*,RP)" and "Receive Prune(*,*,RP)" 1867 imply receiving a Join or Prune targeted to this router's address on the 1868 received interface. If the destination address is not correct, these 1869 state transitions in this state machine must not occur, although seeing 1870 such a packet may cause state transitions in other state machines. 1872 On unnumbered interfaces on point-to-point links, the router's address 1873 should be the same as the source address it chose for the Hello message 1874 it sent over that interface. However on point-to-point links we also 1875 recommend that PIM messages with a destination address of all zeros are 1876 also accepted. 1878 Transitions from NoInfo State 1880 When in NoInfo state, the following event may trigger a transition: 1882 Receive Join(*,*,RP) 1883 A Join(*,*,RP) is received on interface I with its Upstream 1884 Neighbor Address set to the router's address on I. 1886 The (*,*,RP) downstream state machine on interface I 1887 transitions to the Join state. The Expiry Timer (ET) is 1888 started, and set to the HoldTime from the triggering 1889 Join/Prune message. 1891 Note that it is possible to receive a Join(*,*,RP) message for 1892 an RP that we do not have information telling us that it is an 1893 RP. In the case of (*,*,RP) state, so long as we have a route 1894 to the RP, this will not cause a problem, and the transition 1895 should still take place. 1897 Transitions from Join State 1899 When in Join state, the following events may trigger a transition: 1901 Receive Join(*,*,RP) 1902 A Join(*,*,RP) is received on interface I with its Upstream 1903 Neighbor Address set to the router's address on I. 1905 The (*,*,RP) downstream state machine on interface I remains 1906 in Join state, and the Expiry Timer (ET) is restarted, set to 1907 maximum of its current value and the HoldTime from the 1908 triggering Join/Prune message. 1910 Receive Prune(*,*,RP) 1911 A Prune(*,*,RP) is received on interface I with its Upstream 1912 Neighbor Address set to the router's address on I. 1914 The (*,*,RP) downstream state machine on interface I 1915 transitions to the PrunePending state. The PrunePending timer 1916 is started; it is set to the J/P_Override_Interval(I) if the 1917 router has more than one neighbor on that interface; otherwise 1918 it is set to zero causing it to expire immediately. 1920 Expiry Timer Expires 1921 The Expiry Timer for the (*,*,RP) downstream state machine on 1922 interface I expires. 1924 The (*,*,RP) downstream state machine on interface I 1925 transitions to the NoInfo state. 1927 Transitions from PrunePending State 1929 When in PrunePending state, the following events may trigger a 1930 transition: 1932 Receive Join(*,*,RP) 1933 A Join(*,*,RP) is received on interface I with its Upstream 1934 Neighbor Address set to the router's address on I. 1936 The (*,*,RP) downstream state machine on interface I 1937 transitions to the Join state. The PrunePending timer is 1938 canceled (without triggering an expiry event). The Expiry 1939 Timer is restarted, set to maximum of its current value and 1940 the HoldTime from the triggering Join/Prune message. 1942 Expiry Timer Expires 1943 The Expiry Timer for the (*,*,RP) downstream state machine on 1944 interface I expires. 1946 The (*,*,RP) downstream state machine on interface I 1947 transitions to the NoInfo state. 1949 PrunePending Timer Expires 1950 The PrunePending Timer for the (*,*,RP) downstream state 1951 machine on interface I expires. 1953 The (*,*,RP) downstream state machine on interface I 1954 transitions to the NoInfo state. A PruneEcho(*,*,RP) is sent 1955 onto the subnet connected to interface I. 1957 The action "Send PruneEcho(*,*,RP)" is triggered when the 1958 router stops forwarding on an interface as a result of a 1959 prune. A PruneEcho(*,*,RP) is simply a Prune(*,*,RP) message 1960 sent by the upstream router on a LAN with its own address in 1961 the Upstream Neighbor Address field. Its purpose is to add 1962 additional reliability so that if a Prune that should have 1963 been overridden by another router is lost locally on the LAN, 1964 then the PruneEcho may be received and cause the override to 1965 happen. A PruneEcho(*,*,RP) need not be sent on an interface 1966 containing only one PIM neighbor. 1968 4.5.2. Receiving (*,G) Join/Prune Messages 1970 When a router receives a Join(*,G) or Prune(*,G) it must first check to 1971 see whether the RP in the message matches RP(G) (the router's idea of 1972 who the RP is). If the RP in the message does not match RP(G) the Join 1973 or Prune should be silently dropped. If a router has no RP information 1974 (e.g. has not recently received a BSR message) then it may choose to 1975 accept Join(*,G) or Prune(*,G) and treat the RP in the message as RP(G). 1977 The per-interface state-machine for receiving (*,G) Join/Prune Messages 1978 is given below. There are three states: 1980 NoInfo (NI) 1981 The interface has no (*,G) Join state and no timers running. 1983 Join (J) 1984 The interface has (*,G) Join state which will cause us to 1985 forward packets destined for G from this interface except if 1986 there is also (S,G,rpt) prune information (see Section 4.5.4) 1987 or the router lost an assert on this interface. 1989 PrunePending (PP) 1990 The router has received a Prune(*,G) on this interface from a 1991 downstream neighbor and is waiting to see whether the prune 1992 will be overridden by another downstream router. For 1993 forwarding purposes, the PrunePending state functions exactly 1994 like the Join state. 1996 In addition the state-machine uses two timers: 1998 ExpiryTimer (ET) 1999 This timer is restarted when a valid Join(*,G) is received. 2000 Expiry of the ExpiryTimer causes the interface state to revert 2001 to NoInfo for this group. 2003 PrunePendingTimer (PPT) 2004 This timer is set when a valid Prune(*,G) is received. Expiry 2005 of the PrunePendingTimer causes the interface state to revert 2006 to NoInfo for this group. 2008 Figure 3: Downstream (*,G) per-interface state-machine in tabular form 2010 +-------------++--------------------------------------------------------+ 2011 | || Event | 2012 | ++-------------+-------------+-------------+--------------+ 2013 |Prev State ||Receive | Receive | Prune | Expiry Timer | 2014 | ||Join(*,G) | Prune(*,G) | Pending | Expires | 2015 | || | | Timer | | 2016 | || | | Expires | | 2017 +-------------++-------------+-------------+-------------+--------------+ 2018 | ||-> J state | -> NI state | - | - | 2019 |NoInfo (NI) ||start Expiry | | | | 2020 | ||Timer | | | | 2021 +-------------++-------------+-------------+-------------+--------------+ 2022 | ||-> J state | -> PP state | - | -> NI state | 2023 |Join (J) ||restart | start Prune | | | 2024 | ||Expiry Timer | Pending | | | 2025 | || | Timer | | | 2026 +-------------++-------------+-------------+-------------+--------------+ 2027 | ||-> J state | -> PP state | -> NI state | -> NI state | 2028 | ||restart | | Send Prune- | | 2029 |Prune ||Expiry | | Echo(*,G) | | 2030 |Pending (PP) ||Timer; | | | | 2031 | ||cancel Prune | | | | 2032 | ||Pending | | | | 2033 | ||Timer | | | | 2034 +-------------++-------------+-------------+-------------+--------------+ 2036 The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" imply 2037 receiving a Join or Prune targeted to this router's address on the 2038 received interface. If the destination address is not correct, these 2039 state transitions in this state machine must not occur, although seeing 2040 such a packet may cause state transitions in other state machines. 2042 On unnumbered interfaces on point-to-point links, the router's address 2043 should be the same as the source address it chose for the Hello message 2044 it sent over that interface. However on point-to-point links we also 2045 recommend that PIM messages with a destination address of all zeros are 2046 also accepted. 2048 Transitions from NoInfo State 2050 When in NoInfo state, the following event may trigger a transition: 2052 Receive Join(*,G) 2053 A Join(*,G) is received on interface I with its Upstream 2054 Neighbor Address set to the router's address on I. 2056 The (*,G) downstream state machine on interface I transitions 2057 to the Join state. The Expiry Timer (ET) is started, and set 2058 to the HoldTime from the triggering Join/Prune message. 2060 Transitions from Join State 2062 When in Join state, the following events may trigger a transition: 2064 Receive Join(*,G) 2065 A Join(*,G) is received on interface I with its Upstream 2066 Neighbor Address set to the router's address on I. 2068 The (*,G) downstream state machine on interface I remains in 2069 Join state, and the Expiry Timer (ET) is restarted, set to 2070 maximum of its current value and the HoldTime from the 2071 triggering Join/Prune message. 2073 Receive Prune(*,G) 2074 A Prune(*,G) is received on interface I with its Upstream 2075 Neighbor Address set to the router's address on I. 2077 The (*,G) downstream state machine on interface I transitions 2078 to the PrunePending state. The PrunePending timer is started; 2079 it is set to the J/P_Override_Interval(I) if the router has 2080 more than one neighbor on that interface; otherwise it is set 2081 to zero causing it to expire immediately. 2083 Expiry Timer Expires 2084 The Expiry Timer for the (*,G) downstream state machine on 2085 interface I expires. 2087 The (*,G) downstream state machine on interface I transitions 2088 to the NoInfo state. 2090 Transitions from PrunePending State 2092 When in PrunePending state, the following events may trigger a 2093 transition: 2095 Receive Join(*,G) 2096 A Join(*,G) is received on interface I with its Upstream 2097 Neighbor Address set to the router's address on I. 2099 The (*,G) downstream state machine on interface I transitions 2100 to the Join state. The PrunePending timer is canceled 2101 (without triggering an expiry event). The Expiry Timer is 2102 restarted, set to maximum of its current value and the 2103 HoldTime from the triggering Join/Prune message. 2105 Expiry Timer Expires 2106 The Expiry Timer for the (*,G) downstream state machine on 2107 interface I expires. 2109 The (*,G) downstream state machine on interface I transitions 2110 to the NoInfo state. 2112 PrunePending Timer Expires 2113 The PrunePending Timer for the (*,G) downstream state machine 2114 on interface I expires. 2116 The (*,G) downstream state machine on interface I transitions 2117 to the NoInfo state. A PruneEcho(*,G) is sent onto the subnet 2118 connected to interface I. 2120 The action "Send PruneEcho(*,G)" is triggered when the router 2121 stops forwarding on an interface as a result of a prune. A 2122 PruneEcho(*,G) is simply a Prune(*,G) message sent by the 2123 upstream router on a LAN with its own address in the Upstream 2124 Neighbor Address field. Its purpose is to add additional 2125 reliability so that if a Prune that should have been 2126 overridden by another router is lost locally on the LAN, then 2127 the PruneEcho may be received and cause the override to 2128 happen. A PruneEcho(*,G) need not be sent on an interface 2129 containing only one PIM neighbor. 2131 4.5.3. Receiving (S,G) Join/Prune Messages 2133 The per-interface state machine for receiving (S,G) Join/Prune messages 2134 is given below, and is almost identical to that for (*,G) messages. 2135 There are three states: 2137 NoInfo (NI) 2138 The interface has no (S,G) Join state and no (S,G) timers 2139 running. 2141 Join (J) 2142 The interface has (S,G) Join state which will cause us to 2143 forward packets from S destined for G from this interface if 2144 the (S,G) state is active (the SPTbit is set) except if the 2145 router lost an assert on this interface. 2147 PrunePending (PP) 2148 The router has received a Prune(S,G) on this interface from a 2149 downstream neighbor and is waiting to see whether the prune 2150 will be overridden by another downstream router. For 2151 forwarding purposes, the PrunePending state functions exactly 2152 like the Join state. 2154 In addition there are two timers: 2156 ExpiryTimer (ET) 2157 This timer is set when a valid Join(S,G) is received. Expiry 2158 of the ExpiryTimer causes this state machine to revert to 2159 NoInfo state. 2161 PrunePendingTimer (PPT) 2162 This timer is set when a valid Prune(S,G) is received. Expiry 2163 of the PrunePendingTimer this state machine to revert to 2164 NoInfo state. 2166 Figure 4: Downstream per-interface (S,G) state-machine in tabular form 2168 +-------------++--------------------------------------------------------+ 2169 | || Event | 2170 | ++-------------+-------------+-------------+--------------+ 2171 |Prev State ||Receive | Receive | Prune | Expiry Timer | 2172 | ||Join(S,G) | Prune(S,G) | Pending | Expires | 2173 | || | | Timer | | 2174 | || | | Expires | | 2175 +-------------++-------------+-------------+-------------+--------------+ 2176 | ||-> J state | -> NI state | - | - | 2177 |NoInfo (NI) ||start Expiry | | | | 2178 | ||Timer | | | | 2179 +-------------++-------------+-------------+-------------+--------------+ 2180 | ||-> J state | -> PP state | - | -> NI state | 2181 |Join (J) ||restart | start Prune | | | 2182 | ||Expiry Timer | Pending | | | 2183 | || | Timer | | | 2184 +-------------++-------------+-------------+-------------+--------------+ 2185 | ||-> J state | -> PP state | -> NI state | -> NI state | 2186 | ||restart | | Send Prune- | | 2187 |Prune ||Expiry | | Echo(S,G) | | 2188 |Pending (PP) ||Timer; | | | | 2189 | ||cancel Prune | | | | 2190 | ||Pending | | | | 2191 | ||Timer | | | | 2192 +-------------++-------------+-------------+-------------+--------------+ 2194 The transition events "Receive Join(S,G)" and "Receive Prune(S,G)" imply 2195 receiving a Join or Prune targeted to this router's address on the 2196 received interface. If the destination address is not correct, these 2197 state transitions in this state machine must not occur, although seeing 2198 such a packet may cause state transitions in other state machines. 2200 On unnumbered interfaces on point-to-point links, the router's address 2201 should be the same as the source address it chose for the Hello message 2202 it sent over that interface. However on point-to-point links we also 2203 recommend that PIM messages with a destination address of all zeros are 2204 also accepted. 2206 Transitions from NoInfo State 2208 When in NoInfo state, the following event may trigger a transition: 2210 Receive Join(S,G) 2211 A Join(S,G) is received on interface I with its Upstream 2212 Neighbor Address set to the router's address on I. 2214 The (S,G) downstream state machine on interface I transitions 2215 to the Join state. The Expiry Timer (ET) is started, and set 2216 to the HoldTime from the triggering Join/Prune message. 2218 Transitions from Join State 2220 When in Join state, the following events may trigger a transition: 2222 Receive Join(S,G) 2223 A Join(S,G) is received on interface I with its Upstream 2224 Neighbor Address set to the router's address on I. 2226 The (S,G) downstream state machine on interface I remains in 2227 Join state, and the Expiry Timer (ET) is restarted, set to 2228 maximum of its current value and the HoldTime from the 2229 triggering Join/Prune message. 2231 Receive Prune(S,G) 2232 A Prune(S,G) is received on interface I with its Upstream 2233 Neighbor Address set to the router's address on I. 2235 The (S,G) downstream state machine on interface I transitions 2236 to the PrunePending state. The PrunePending timer is started; 2237 it is set to the J/P_Override_Interval(I) if the router has 2238 more than one neighbor on that interface; otherwise it is set 2239 to zero causing it to expire immediately. 2241 Expiry Timer Expires 2242 The Expiry Timer for the (S,G) downstream state machine on 2243 interface I expires. 2245 The (S,G) downstream state machine on interface I transitions 2246 to the NoInfo state. 2248 Transitions from PrunePending State 2250 When in PrunePending state, the following events may trigger a 2251 transition: 2253 Receive Join(S,G) 2254 A Join(S,G) is received on interface I with its Upstream 2255 Neighbor Address set to the router's address on I. 2257 The (S,G) downstream state machine on interface I transitions 2258 to the Join state. The PrunePending timer is canceled 2259 (without triggering an expiry event). The Expiry Timer is 2260 restarted, set to maximum of its current value and the 2261 HoldTime from the triggering Join/Prune message. 2263 Expiry Timer Expires 2264 The Expiry Timer for the (S,G) downstream state machine on 2265 interface I expires. 2267 The (S,G) downstream state machine on interface I transitions 2268 to the NoInfo state. 2270 PrunePending Timer Expires 2271 The PrunePending Timer for the (S,G) downstream state machine 2272 on interface I expires. 2274 The (S,G) downstream state machine on interface I transitions 2275 to the NoInfo state. A PruneEcho(S,G) is sent onto the subnet 2276 connected to interface I. 2278 The action "Send PruneEcho(S,G)" is triggered when the router 2279 stops forwarding on an interface as a result of a prune. A 2280 PruneEcho(S,G) is simply a Prune(S,G) message sent by the 2281 upstream router on a LAN with its own address in the Upstream 2282 Neighbor Address field. Its purpose is to add additional 2283 reliability so that if a Prune that should have been 2284 overridden by another router is lost locally on the LAN, then 2285 the PruneEcho may be received and cause the override to 2286 happen. A PruneEcho(S,G) need not be sent on an interface 2287 containing only one PIM neighbor. 2289 4.5.4. Receiving (S,G,rpt) Join/Prune Messages 2291 The per-interface state machine for receiving (S,G,rpt) Join/Prune 2292 messages is given below. There are five states: 2294 NoInfo (NI) 2295 The interface has no (S,G,rpt) Prune state and no (S,G,rpt) 2296 timers running. 2298 Prune (P) 2299 The interface has (S,G,rpt) Prune state which will cause us 2300 not to forward packets from S destined for G from this 2301 interface even though the interface has active (*,G) Join 2302 state. When interface I is in this state, the macro 2303 prune(S,G,rpt,I) returns true. 2305 PrunePending (PP) 2306 The router has received a Prune(S,G,rpt) on this interface 2307 from a downstream neighbor and is waiting to see whether the 2308 prune will be overridden by another downstream router. For 2309 forwarding purposes, the PrunePending state functions exactly 2310 like the NoInfo state. 2312 PruneTmp (P') 2313 This state is a transient state which for forwarding purposes 2314 behaves exactly like the Prune state. A (*,G) Join has been 2315 received (which may cancel the (S,G,rpt) Prune). As we parse 2316 the Join/Prune message from top to bottom, we first enter this 2317 state if the message contains a (*,G) Join. Later in the 2318 message we will normally encounter an (S,G,rpt) prune to re- 2319 instate the Prune state. However if we reach the end of the 2320 message without encountering such a (S,G,rpt) prune, then we 2321 will revert to NoInfo state in this state machine. 2323 As no time is spent in this state, no timers can expire. 2325 PrunePendingTmp (PP') 2326 This state is a transient state which is identical to P' 2327 except that it is associated with the PP state rather than the 2328 P state. For forwarding purposes, PP' behaves exactly like PP 2329 state. 2331 In addition there are two timers: 2333 ExpiryTimer (ET) 2334 This timer is set when a valid Prune(S,G,rpt) is received. 2335 Expiry of the ExpiryTimer causes this state machine to revert 2336 to NoInfo state. 2338 PrunePendingTimer (PPT) 2339 This timer is set when a valid Prune(S,G,rpt) is received. 2340 Expiry of the PrunePendingTimer causes this state machine to 2341 move on to Prune state. 2343 Figure 5: Downstream per-interface (S,G,rpt) state-machine in tabular form 2345 +----------++----------------------------------------------------------------+ 2346 | || Event | 2347 | ++----------+-----------+-----------+---------+---------+---------+ 2348 |Prev ||Receive | Receive | Receive | End of | Prune | Expiry | 2349 |State ||Join(*,G) | Join | Prune | Message | Pending | Timer | 2350 | || | (S,G,rpt) | (S,G,rpt) | | Timer | Expires | 2351 | || | | | | Expires | | 2352 +----------++----------+-----------+-----------+---------+---------+---------+ 2353 | ||- | - | -> PP | - | n/a | n/a | 2354 | || | | state | | | | 2355 | || | | start | | | | 2356 | || | | Prune | | | | 2357 |No Info || | | Pending | | | | 2358 |(NI) || | | Timer; | | | | 2359 | || | | start | | | | 2360 | || | | Expiry | | | | 2361 | || | | Timer | | | | 2362 | || | | Timer | | | | 2363 +----------++----------+-----------+-----------+---------+---------+---------+ 2364 | ||-> P' | -> NI | -> P | - | n/a | -> NI | 2365 |Pruned ||state | state | state | | | state | 2366 |(P) || | | restart | | | | 2367 | || | | Expiry | | | | 2368 | || | | Timer | | | | 2369 +----------++----------+-----------+-----------+---------+---------+---------+ 2370 |Prune ||-> PP' | -> NI | - | - | -> P | n/a | 2371 |Pending ||state | state | | | state | | 2372 |(PP) || | | | | | | 2373 +----------++----------+-----------+-----------+---------+---------+---------+ 2374 | ||error | error | -> P | -> NI | n/a | n/a | 2375 |Prune Tmp || | | state | state | | | 2376 |(P') || | | restart | | | | 2377 | || | | Expiry | | | | 2378 | || | | Timer | | | | 2379 +----------++----------+-----------+-----------+---------+---------+---------+ 2380 | ||error | error | -> PP | -> NI | n/a | n/a | 2381 |Prune || | | state | state | | | 2382 |Pending || | | restart | | | | 2383 |Tmp (PP') || | | Expiry | | | | 2384 | || | | Timer | | | | 2385 +----------++----------+-----------+-----------+---------+---------+---------+ 2387 The transition events "Receive Join(S,G,rpt)", "Receive Prune(S,G,rpt)", 2388 and "Receive Join(*,G)" imply receiving a Join or Prune targeted to this 2389 router's address on the received interface. If the destination address 2390 is not correct, these state transitions in this state machine must not 2391 occur, although seeing such a packet may cause state transitions in 2392 other state machines. 2394 On unnumbered interfaces on point-to-point links, the router's address 2395 should be the same as the source address it chose for the Hello message 2396 it sent over that interface. However on point-to-point links we also 2397 recommend that PIM messages with a destination address of all zeros are 2398 also accepted. 2400 Transitions from NoInfo State 2402 When in NoInfo (NI) state, the following event may trigger a transition: 2404 Receive Prune(S,G,rpt) 2405 A Prune(S,G,rpt) is received on interface I with its Upstream 2406 Neighbor Address set to the router's address on I. 2408 The (S,G,rpt) downstream state machine on interface I 2409 transitions to the PrunePending state. The Expiry Timer (ET) 2410 is started, and set to the HoldTime from the triggering 2411 Join/Prune message. The PrunePending timer is started; it is 2412 set to the J/P_Override_Interval(I) if the router has more 2413 than one neighbor on that interface; otherwise it is set to 2414 zero causing it to expire immediately. 2416 Transitions from PrunePending State 2418 When in PrunePending (PP) state, the following events may trigger a 2419 transition: 2421 Receive Join(*,G) 2422 A Join(*,G) is received on interface I with its Upstream 2423 Neighbor Address set to the router's address on I. 2425 The (S,G,rpt) downstream state machine on interface I 2426 transitions to PrunePendingTmp state whilst the remainder of 2427 the compound Join/Prune message containing the Join(*,G) is 2428 processed. 2430 Receive Join(S,G,rpt) 2431 A Join(S,G,rpt) is received on interface I with its Upstream 2432 Neighbor Address set to the router's address on I. 2434 The (S,G,rpt) downstream state machine on interface I 2435 transitions to NoInfo state. ET and PPT are canceled. 2437 PrunePending Timer Expires 2438 The PrunePending Timer for the (S,G,rpt) downstream state 2439 machine on interface I expires. 2441 The (S,G,rpt) downstream state machine on interface I 2442 transitions to the Pruned state. 2444 Transitions from Pruned State 2446 When in Pruned (P) state, the following events may trigger a transition: 2448 Receive Join(*,G) 2449 A Join(*,G) is received on interface I with its Upstream 2450 Neighbor Address set to the router's address on I. 2452 The (S,G,rpt) downstream state machine on interface I 2453 transitions to PruneTmp state whilst the remainder of the 2454 compound Join/Prune message containing the Join(*,G) is 2455 processed. 2457 Receive Join(S,G,rpt) 2458 A Join(S,G,rpt) is received on interface I with its Upstream 2459 Neighbor Address set to the router's address on I. 2461 The (S,G,rpt) downstream state machine on interface I 2462 transitions to NoInfo state. ET and PPT are canceled. 2464 Receive Prune(S,G,rpt) 2465 A Prune(S,G,rpt) is received on interface I with its Upstream 2466 Neighbor Address set to the router's address on I. 2468 The (S,G,rpt) downstream state machine on interface I remains 2469 in Pruned state. The Expiry Timer (ET) is restarted, set to 2470 maximum of its current value and the HoldTime from the 2471 triggering Join/Prune message. 2473 Expiry Timer Expires 2474 The Expiry Timer for the (S,G,rpt) downstream state machine on 2475 interface I expires. 2477 The (S,G,rpt) downstream state machine on interface I 2478 transitions to the NoInfo state. ET and PPT are canceled. 2480 Transitions from PrunePendingTmp State 2482 When in PrunePendingTmp (PP') state and processing a compound Join/Prune 2483 message, the following events may trigger a transition: 2485 Receive Prune(S,G,rpt) 2486 The compound Join/Prune message contains a Prune(S,G,rpt). 2488 The (S,G,rpt) downstream state machine on interface I 2489 transitions back to the PrunePending state. The Expiry Timer 2490 (ET) is restarted, set to maximum of its current value and the 2491 HoldTime from the triggering Join/Prune message. 2493 End of Message 2494 The end of the compound Join/Prune message is reached. 2496 The (S,G,rpt) downstream state machine on interface I 2497 transitions to the NoInfo state. ET and PPT are canceled. 2499 Transitions from PruneTmp State 2501 When in PruneTmp (P') state and processing a compound Join/Prune 2502 message, the following events may trigger a transition: 2504 Receive Prune(S,G,rpt) 2505 The compound Join/Prune message contains a Prune(S,G,rpt). 2507 The (S,G,rpt) downstream state machine on interface I 2508 transitions back to the Pruned state. The Expiry Timer (ET) 2509 is restarted, set to maximum of its current value and the 2510 HoldTime from the triggering Join/Prune message. 2512 End of Message 2513 The end of the compound Join/Prune message is reached. 2515 The (S,G,rpt) downstream state machine on interface I 2516 transitions to the NoInfo state. ET and PPT are canceled. 2518 Notes: 2520 Receiving a Prune(*,G) does not affect the (S,G,rpt) downstream state 2521 machine. 2523 Receiving a Join(*,*,RP) does not affect the (S,G,rpt) downstream state 2524 machine. If a router has originated Join(*,*,RP) and pruned a source 2525 off it using Prune(S,G,rpt), then to receive that source again it should 2526 explicitly re-join using Join(S,G,rpt) or Join(*,G). In some LAN 2527 topologies it is possible for a router sending a new Join(*,*,RP) to 2528 have to wait as much as a Join/Prune Interval before noticing that it 2529 needs to override a neighbor's pre-existing Prune(S,G,rpt). This is 2530 considered acceptable, as (*,*,RP) state is intended to be used only in 2531 long-lived and persistent scenarios. 2533 4.5.5. Sending (*,*,RP) Join/Prune Messages 2535 The per-interface state-machines for (*,*,RP) hold join state from 2536 downstream PIM routers. This state then determines whether a router 2537 needs to propagate a Join(*,*,RP) upstream towards the RP. 2539 If a router wishes to propagate a Join(*,*,RP) upstream, it must also 2540 watch for messages on its upstream interface from other routers on that 2541 subnet, and these may modify its behavior. If it sees a Join(*,*,RP) to 2542 the correct upstream neighbor, it should suppress its own Join(*,*,RP). 2543 If it sees a Prune(*,*,RP) to the correct upstream neighbor, it should 2544 be prepared to override that prune by sending a Join(*,*,RP) almost 2545 immediately. Finally, if it sees the Generation ID (see Section 4.3) of 2546 the correct upstream neighbor change, it knows that the upstream 2547 neighbor has lost state, and it should be prepared to refresh the state 2548 by sending a Join(*,*,RP) almost immediately. 2550 In addition if the MRIB changes to indicate that the next hop towards 2551 the RP has changed, the router should prune off from the old next hop, 2552 and join towards the new next hop. 2554 The upstream (*,*,RP) state-machine contains only two states: 2556 Not Joined 2557 The downstream state-machines indicate that the router does not 2558 need to join the (*,*,RP) tree for this RP. 2560 Joined 2561 The downstream state-machines indicate that the router would like 2562 to join the (*,*,RP) tree for this RP. 2564 In addition, one timer JT(*,*,RP) is kept which is used to trigger the 2565 sending of a Join(*,*,RP) to the upstream next hop towards the RP, 2566 MRIB.next_hop(RP). 2568 Figure 6: Upstream (*,*,RP) state-machine in tabular form 2570 +-------------------+---------------------------------------------------+ 2571 | | Event | 2572 | Prev State +--------------------------+------------------------+ 2573 | | JoinDesired(*,*,RP) | JoinDesired(*,*,RP) | 2574 | | ->True | ->False | 2575 +-------------------+--------------------------+------------------------+ 2576 | | -> J state | - | 2577 | NotJoined (NJ) | Send Join(*,*,RP); | | 2578 | | Set Join Timer to | | 2579 | | t_periodic | | 2580 +-------------------+--------------------------+------------------------+ 2581 | Joined (J) | - | -> NJ state | 2582 | | | Send Prune(*,*,RP); | 2583 | | | Cancel Join Timer | 2584 +-------------------+--------------------------+------------------------+ 2586 In addition, we have the following transitions which occur within the 2587 Joined state: 2589 +-----------------------------------------------------------------------+ 2590 | In Joined (J) State | 2591 +-----------------+----------------------+------------------------------+ 2592 | Timer Expires | See | See | 2593 | | Join(*,*,RP) | Prune(*,*,RP) | 2594 | | to | to | 2595 | | MRIB.next_hop(RP) | MRIB.next_hop(RP) | 2596 +-----------------+----------------------+------------------------------+ 2597 | Send | Increase Join | Decrease Join | 2598 | Join(*,*,RP); | Timer to | Timer to | 2599 | Set Join Timer | t_joinsuppress | t_override | 2600 | to t_periodic | | | 2601 +-----------------+----------------------+------------------------------+ 2603 +-----------------------------------------------------------------------+ 2604 | In Joined (J) State | 2605 +-----------------------------------+-----------------------------------+ 2606 | MRIB.next_hop(RP) | MRIB.next_hop(RP) GenID | 2607 | changes | changes | 2608 +-----------------------------------+-----------------------------------+ 2609 | Send Join(*,*,RP) to new | Decrease Join Timer to | 2610 | next hop; Send | t_override | 2611 | Prune(*,*,RP) to old | | 2612 | next hop; set Join Timer | | 2613 | to t_periodic | | 2614 +-----------------------------------+-----------------------------------+ 2615 This state machine uses the following macro: 2617 bool JoinDesired(*,*,RP) { 2618 if immediate_olist(*,*,RP) != NULL 2619 return TRUE 2620 else 2621 return FALSE 2622 } 2624 JoinDesired(*,*,RP) is true when the router has received (*,*,RP) Joins 2625 from any downstream interface. Note that although JoinDesired is true, 2626 the router's sending of a Join(*,*,RP) message may be suppressed by 2627 another router sending a Join(*,*,RP) onto the upstream interface. 2629 Transitions from NotJoined State 2631 When the upstream (*,*,RP) state-machine is in NotJoined state, the 2632 following event may trigger a state transition: 2634 JoinDesired(*,*,RP) becomes True 2635 The downstream state for (*,*,RP) has changed so that at least 2636 one interface is in immediate_olist(*,*,RP), making 2637 JoinDesired(*,*,RP) become True. 2639 The upstream (*,*,RP) state machine transitions to Joined 2640 state. Send Join(*,*,RP) to the appropriate upstream 2641 neighbor, which is MRIB.next_hop(RP). Set the Join Timer (JT) 2642 to expire after t_periodic seconds. 2644 Transitions from Joined State 2646 When the upstream (*,*,RP) state-machine is in Joined state, the 2647 following events may trigger state transitions: 2649 JoinDesired(*,*,RP) becomes False 2650 The downstream state for (*,*,RP) has changed so no interface 2651 is in immediate_olist(*,*,RP), making JoinDesired(*,*,RP) 2652 become False. 2654 The upstream (*,*,RP) state machine transitions to NotJoined 2655 state. Send Prune(*,*,RP) to the appropriate upstream 2656 neighbor, which is MRIB.next_hop(RP). Cancel the Join Timer 2657 (JT). 2659 Join Timer Expires 2660 The Join Timer (JT) expires, indicating time to send a 2661 Join(*,*,RP) 2662 Send Join(*,*,RP) to the appropriate upstream neighbor, which 2663 is MRIB.next_hop(RP). Restart the Join Timer (JT) to expire 2664 after t_periodic seconds. 2666 See Join(*,*,RP) to MRIB.next_hop(RP) 2667 This event is only relevant if RPF_interface(RP) is a shared 2668 medium. This router sees another router on RPF_interface(RP) 2669 send a Join(*,*,RP) to MRIB.next_hop(RP). This causes this 2670 router to suppress its own Join. 2672 The upstream (*,*,RP) state machine remains in Joined state. 2674 Let t_joinsuppress be the minimum of t_suppressed and the 2675 HoldTime from the Join/Prune message triggering this event. 2676 If the Join Timer is set to expire in less than t_joinsuppress 2677 seconds, reset it so that it expires after t_joinsuppress 2678 seconds. If the Join Timer is set to expire in more than 2679 t_joinsuppress seconds, leave it unchanged. 2681 See Prune(*,*,RP) to MRIB.next_hop(RP) 2682 This event is only relevant if RPF_interface(RP) is a shared 2683 medium. This router sees another router on RPF_interface(RP) 2684 send a Prune(*,*,RP) to MRIB.next_hop(RP). As this router is 2685 in Joined state, it must override the Prune after a short 2686 random interval. 2688 The upstream (*,*,RP) state machine remains in Joined state. 2689 If the Join Timer is set to expire in more than t_override 2690 seconds, reset it so that it expires after t_override seconds. 2691 If the Join Timer is set to expire in less than t_override 2692 seconds, leave it unchanged. 2694 MRIB.next_hop(RP) changes 2695 A change in the MRIB routing base causes the next hop towards 2696 the RP to change. 2698 The upstream (*,*,RP) state machine remains in Joined state. 2699 Send Prune(*,*,RP) to the old upstream neighbor, which is the 2700 old value of MRIB.next_hop(RP). Send Join(*,*,RP) to the new 2701 upstream neighbor which is the new value of MRIB.next_hop(RP). 2702 Set the Join Timer (JT) to expire after t_periodic seconds. 2704 MRIB.next_hop(RP) GenID changes 2705 The Generation ID of the router that is MRIB.next_hop(RP) 2706 changes. This normally means that this neighbor has lost 2707 state, and so the state must be refreshed. 2709 The upstream (*,*,RP) state machine remains in Joined state. 2710 If the Join Timer is set to expire in more than t_override 2711 seconds, reset it so that it expires after t_override seconds. 2713 4.5.6. Sending (*,G) Join/Prune Messages 2715 The per-interface state-machines for (*,G) hold join state from 2716 downstream PIM routers. This state then determines whether a router 2717 needs to propagate a Join(*,G) upstream towards the RP. 2719 If a router wishes to propagate a Join(*,G) upstream, it must also watch 2720 for messages on its upstream interface from other routers on that 2721 subnet, and these may modify its behavior. If it sees a Join(*,G) to 2722 the correct upstream neighbor, it should suppress its own Join(*,G). If 2723 it sees a Prune(*,G) to the correct upstream neighbor, it should be 2724 prepared to override that prune by sending a Join(*,G) almost 2725 immediately. Finally, if it sees the Generation ID (see Section 4.3) of 2726 the correct upstream neighbor change, it knows that the upstream 2727 neighbor has lost state, and it should be prepared to refresh the state 2728 by sending a Join(*,G) almost immediately. 2730 In addition if the MRIB changes to indicate that the next hop towards 2731 the RP has changed, the router should prune off from the old next hop, 2732 and join towards the new next hop. 2734 The upstream (*,G) state-machine only contains two states: 2736 Not Joined 2737 The downstream state-machines indicate that the router does not 2738 need to join the RP tree for this group. 2740 Joined 2741 The downstream state-machines indicate that the router would like 2742 to join the RP tree for this group. 2744 In addition, one timer JT(*,G) is kept which is used to trigger the 2745 sending of a Join(*,G) to the upstream next hop towards the RP, 2746 RPF'(*,G). 2748 Figure 7: Upstream (*,G) state-machine in tabular form 2750 +--------------------++-------------------------------------------------+ 2751 | || Event | 2752 | Prev State ++------------------------+------------------------+ 2753 | || JoinDesired(*,G) | JoinDesired(*,G) | 2754 | || ->True | ->False | 2755 +--------------------++------------------------+------------------------+ 2756 | || -> J state | - | 2757 | NotJoined (NJ) || Send Join(*,G); | | 2758 | || Set Join Timer to | | 2759 | || t_periodic | | 2760 +--------------------++------------------------+------------------------+ 2761 | Joined (J) || - | -> NJ state | 2762 | || | Send Prune(*,G); | 2763 | || | Cancel Join Timer | 2764 +--------------------++------------------------+------------------------+ 2766 In addition, we have the following transitions which occur within the 2767 Joined state: 2769 +-----------------------------------------------------------------------+ 2770 | In Joined (J) State | 2771 +------------+----------------+--------------+------------+-------------+ 2772 |Timer |See |See |RPF'(*,G) | RPF'(*,G) | 2773 |Expires |Join(*,G) to |Prune(*,G) |changes | changes due | 2774 | |RPF'(*,G) |to RPF'(*,G) | | to Assert | 2775 +------------+----------------+--------------+------------+-------------+ 2776 |Send |Increase |Decrease |Decrease | Send | 2777 |Join(*,G); |Join Timer |Join Timer |Join Timer | Join(*,G); | 2778 |Set Join |to |to |to | Set Join | 2779 |Timer to |t_joinsuppress |t_override |t_override | Timer to | 2780 |t_periodic | | | | t_periodic | 2781 +------------+----------------+--------------+------------+-------------+ 2783 +-----------------------------------------------------------------------+ 2784 | In Joined (J) State | 2785 +----------------------------------+------------------------------------+ 2786 | MRIB.next_hop(RP(G)) | RPF'(*,G) GenID changes | 2787 | changes | | 2788 +----------------------------------+------------------------------------+ 2789 | Send Join(*,G) to new | Decrease Join Timer to | 2790 | next hop; Send | t_override | 2791 | Prune(*,G) to old next | | 2792 | hop; Set Join Timer to | | 2793 | t_periodic | | 2794 +----------------------------------+------------------------------------+ 2795 This state machine uses the following macro: 2797 bool JoinDesired(*,G) { 2798 if (immediate_olist(*,G) != NULL || 2799 (JoinDesired(*,*,RP(G)) && 2800 AssertWinner(*,G,RPF_interface(RP(G))) != NULL)) 2801 return TRUE 2802 else 2803 return FALSE 2804 } 2806 JoinDesired(*,G) is true when the router has forwarding state that would 2807 cause it to forward traffic for G using shared tree state. Note that 2808 although JoinDesired is true, the router's sending of a Join(*,G) 2809 message may be suppressed by another router sending a Join(*,G) onto the 2810 upstream interface. 2812 Transitions from NotJoined State 2814 When the upstream (*,G) state-machine is in NotJoined state, the 2815 following event may trigger a state transition: 2817 JoinDesired(*,G) becomes True 2818 The downstream state for (*,G) has changed so that at least 2819 one interface is in immediate_olist(*,G), making 2820 JoinDesired(*,G) become True. 2822 The upstream (*,G) state machine transitions to Joined state. 2823 Send Join(*,G) to the appropriate upstream neighbor, which is 2824 RPF'(*,G). Set the Join Timer (JT) to expire after t_periodic 2825 seconds. 2827 Transitions from Joined State 2829 When the upstream (*,G) state-machine is in Joined state, the following 2830 events may trigger state transitions: 2832 JoinDesired(*,G) becomes False 2833 The downstream state for (*,G) has changed so no interface is 2834 in immediate_olist(*,G), making JoinDesired(*,G) become False. 2836 The upstream (*,G) state machine transitions to NotJoined 2837 state. Send Prune(*,G) to the appropriate upstream neighbor, 2838 which is RPF'(*,G). Cancel the Join Timer (JT). 2840 Join Timer Expires 2841 The Join Timer (JT) expires, indicating time to send a 2842 Join(*,G) 2843 Send Join(*,G) to the appropriate upstream neighbor, which is 2844 RPF'(*,G). Restart the Join Timer (JT) to expire after 2845 t_periodic seconds. 2847 See Join(*,G) to RPF'(*,G) 2848 This event is only relevant if RPF_interface(RP(G)) is a 2849 shared medium. This router sees another router on 2850 RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G). This 2851 causes this router to suppress its own Join. 2853 The upstream (*,G) state machine remains in Joined state. 2855 Let t_joinsuppress be the minimum of t_suppressed and the 2856 HoldTime from the Join/Prune message triggering this event. 2857 If the Join Timer is set to expire in less than t_joinsuppress 2858 seconds, reset it so that it expires after t_joinsuppress 2859 seconds. If the Join Timer is set to expire in more than 2860 t_joinsuppress seconds, leave it unchanged. 2862 See Prune(*,G) to RPF'(*,G) 2863 This event is only relevant if RPF_interface(RP(G)) is a 2864 shared medium. This router sees another router on 2865 RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G). As this 2866 router is in Joined state, it must override the Prune after a 2867 short random interval. 2869 The upstream (*,G) state machine remains in Joined state. If 2870 the Join Timer is set to expire in more than t_override 2871 seconds, reset it so that it expires after t_override seconds. 2872 If the Join Timer is set to expire in less than t_override 2873 seconds, leave it unchanged. 2875 RPF'(*,G) changes 2876 The current next hop towards the RP changes due to an 2877 Assert(*,G) on the RPF_interface(RP(G)). 2879 The upstream (*,G) state machine remains in Joined state. If 2880 the Join Timer is set to expire in more than t_override 2881 seconds, reset it so that it expires after t_override seconds. 2882 If the Join Timer is set to expire in less than t_override 2883 seconds, leave it unchanged. 2885 MRIB.next_hop(RP(G)) changes 2886 An event occurred which caused the next hop towards the RP for 2887 G to change. This may be caused by a change in the MRIB 2888 routing database or by the installation of a different RP-to- 2889 group mapping. Note that this transition should occur even if 2890 RPF'(*,G) is not equal to the new next hop towards RP(G), 2891 because it may be that the new neighbor is a better path to 2892 RP(G) than RPF'(*,G); this transition ensures that the better 2893 path is discovered even if an assert occurred previously. 2895 The upstream (*,G) state machine remains in Joined state. 2896 Send Prune(*,G) to the old upstream neighbor, which is the old 2897 value of RPF'(*,G). Send Join(*,G) to the new upstream 2898 neighbor which is the new value of MRIB.next_hop(RP(G)). Note 2899 that the Join goes to MRIB.next_hop(RP(G)) and not RPF'(*,G) 2900 even if the new neighbor is on the same interface as the old 2901 one because the routing change may cause the assert state to 2902 be incorrect. Set the Join Timer (JT) to expire after 2903 t_periodic seconds. 2905 RPF'(*,G) GenID changes 2906 The Generation ID of the router that is RPF'(*,G) changes. 2907 This normally means that this neighbor has lost state, and so 2908 the state must be refreshed. 2910 The upstream (*,G) state machine remains in Joined state. If 2911 the Join Timer is set to expire in more than t_override 2912 seconds, reset it so that it expires after t_override seconds. 2914 4.5.7. Sending (S,G) Join/Prune Messages 2916 The per-interface state-machines for (S,G) hold join state from 2917 downstream PIM routers. This state then determines whether a router 2918 needs to propagate a Join(S,G) upstream towards the source. 2920 If a router wishes to propagate a Join(S,G) upstream, it must also watch 2921 for messages on its upstream interface from other routers on that 2922 subnet, and these may modify its behavior. If it sees a Join(S,G) to 2923 the correct upstream neighbor, it should suppress its own Join(S,G). If 2924 it sees a Prune(S,G), Prune(S,G,rpt), or Prune(*,G) to the correct 2925 upstream neighbor towards S, it should be prepared to override that 2926 prune by scheduling a Join(S,G) to be sent (almost) immediately. 2927 Finally, if it sees the Generation ID of its upstream neighbor change, 2928 it knows that the upstream neighbor has lost state, and it should 2929 refresh the state by scheduling a Join(S,G) to be sent (almost) 2930 immediately. 2932 In addition if MRIB changes cause the next hop towards the source to 2933 change, the router should send a prune to the old next hop, and a join 2934 to the new next hop. 2936 The upstream (S,G) state-machine only contains two states: 2938 Not Joined 2939 The downstream state machines and local membership information do 2940 not indicate that the router needs to join the shortest-path tree 2941 for this (S,G). 2943 Joined 2944 The downstream state machines and local membership information 2945 indicate that the router should join the shortest-path tree for 2946 this (S,G). 2948 In addition, one timer JT(S,G) is kept which is used to trigger the 2949 sending of a Join(S,G) to the upstream next hop toward S, RPF'(S,G). 2951 Figure 8: Upstream (S,G) state-machine in tabular form 2953 +--------------------+--------------------------------------------------+ 2954 | | Event | 2955 | Prev State +-------------------------+------------------------+ 2956 | | JoinDesired(S,G) | JoinDesired(S,G) | 2957 | | ->True | ->False | 2958 +--------------------+-------------------------+------------------------+ 2959 | NotJoined (NJ) | -> J state | - | 2960 | | Send Join(S,G); | | 2961 | | Set Join Timer to | | 2962 | | t_periodic | | 2963 +--------------------+-------------------------+------------------------+ 2964 | Joined (J) | - | -> NJ state | 2965 | | | Send Prune(S,G); | 2966 | | | Set SPTbit(S,G) to | 2967 | | | FALSE; Cancel Join | 2968 | | | Timer | 2969 +--------------------+-------------------------+------------------------+ 2970 In addition, we have the following transitions which occur within the 2971 Joined state: 2973 +-----------------------------------------------------------------------+ 2974 | In Joined (J) State | 2975 +-----------------+-----------------+------------------+----------------+ 2976 | Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune | 2977 | | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to | 2978 | | | | RPF'(S,G) | 2979 +-----------------+-----------------+------------------+----------------+ 2980 | Send | Increase Join | Decrease Join | Decrease Join | 2981 | Join(S,G); Set | Timer to | Timer to | Timer to | 2982 | Join Timer to | t_joinsuppress | t_override | t_override | 2983 | t_periodic | | | | 2984 +-----------------+-----------------+------------------+----------------+ 2986 +-----------------------------------------------------------------------+ 2987 | In Joined (J) State | 2988 +-----------------+-------------------+----------------+----------------+ 2989 |See Prune(*,G) | MRIB.next_hop(S) | RPF'(S,G) | RPF'(S,G) | 2990 |to RPF'(S,G) | changes | GenID changes | changes | 2991 +-----------------+-------------------+----------------+----------------+ 2992 |Decrease Join | Send Join(S,G) | Decrease Join | Decrease Join | 2993 |Timer to | to new next hop; | Timer to | Timer to | 2994 |t_override | Send Prune(S,G) | t_override | t_override | 2995 | | to old next hop; | | | 2996 | | Set Join Timer | | | 2997 | | to t_periodic | | | 2998 +-----------------+-------------------+----------------+----------------+ 3000 This state machine uses the following macro: 3002 bool JoinDesired(S,G) { 3003 return( immediate_olist(S,G) != NULL 3004 OR ( KeepaliveTimer(S,G) is running 3005 AND inherited_olist(S,G) != NULL ) ) 3006 } 3008 JoinDesired(S,G) is true when the router has forwarding state that would 3009 cause it to forward traffic for G using source tree state. The source 3010 tree state can either be as a result of active source-specific join 3011 state, or the (S,G) keepalive timer and active non-source-specific 3012 state. Note that although JoinDesired is true, the router's sending of a 3013 Join(S,G) message may be suppressed by another router sending a 3014 Join(S,G) onto the upstream interface. 3016 Transitions from NotJoined State 3018 When the upstream (S,G) state-machine is in NotJoined state, the 3019 following event may trigger a state transition: 3021 JoinDesired(S,G) becomes True 3022 The downstream state for (S,G) has changed so that at least 3023 one interface is in inherited_olist(S,G), making 3024 JoinDesired(S,G) become True. 3026 The upstream (S,G) state machine transitions to Joined state. 3027 Send Join(S,G) to the appropriate upstream neighbor, which is 3028 RPF'(S,G). Set the Join Timer (JT) to expire after t_periodic 3029 seconds. 3031 Transitions from Joined State 3033 When the upstream (S,G) state-machine is in Joined state, the following 3034 events may trigger state transitions: 3036 JoinDesired(S,G) becomes False 3037 The downstream state for (S,G) has changed so no interface is 3038 in inherited_olist(S,G), making JoinDesired(S,G) become False. 3040 The upstream (S,G) state machine transitions to NotJoined 3041 state. Send Prune(S,G) to the appropriate upstream neighbor, 3042 which is RPF'(S,G). Cancel the Join Timer (JT), and set 3043 SPTbit(S,G) to FALSE. 3045 Join Timer Expires 3046 The Join Timer (JT) expires, indicating time to send a 3047 Join(S,G) 3049 Send Join(S,G) to the appropriate upstream neighbor, which is 3050 RPF'(S,G). Restart the Join Timer (JT) to expire after 3051 t_periodic seconds. 3053 See Join(S,G) to RPF'(S,G) 3054 This event is only relevant if RPF_interface(S) is a shared 3055 medium. This router sees another router on RPF_interface(S) 3056 send a Join(S,G) to RPF'(S,G). This causes this router to 3057 suppress its own Join. 3059 The upstream (S,G) state machine remains in Joined state. 3061 Let t_joinsuppress be the minimum of t_suppressed and the 3062 HoldTime from the Join/Prune message triggering this event. 3063 If the Join Timer is set to expire in less than t_joinsuppress 3064 seconds, reset it so that it expires after t_joinsuppress 3065 seconds. If the Join Timer is set to expire in more than 3066 t_joinsuppress seconds, leave it unchanged. 3068 See Prune(S,G) to RPF'(S,G) 3069 This event is only relevant if RPF_interface(S) is a shared 3070 medium. This router sees another router on RPF_interface(S) 3071 send a Prune(S,G) to RPF'(S,G). As this router is in Joined 3072 state, it must override the Prune after a short random 3073 interval. 3075 The upstream (S,G) state machine remains in Joined state. If 3076 the Join Timer is set to expire in more than t_override 3077 seconds, reset it so that it expires after t_override seconds. 3079 See Prune(S,G,rpt) to RPF'(S,G) 3080 This event is only relevant if RPF_interface(S) is a shared 3081 medium. This router sees another router on RPF_interface(S) 3082 send a Prune(S,G,rpt) to RPF'(S,G). If the upstream router is 3083 an RFC 2362 compliant PIM router, then the Prune(S,G,rpt) will 3084 cause it to stop forwarding. For backwards compatibility, 3085 this router should override the prune so that forwarding 3086 continues. 3088 The upstream (S,G) state machine remains in Joined state. If 3089 the Join Timer is set to expire in more than t_override 3090 seconds, reset it so that it expires after t_override seconds. 3092 See Prune(*,G) to RPF'(S,G) 3093 This event is only relevant if RPF_interface(S) is a shared 3094 medium. This router sees another router on RPF_interface(S) 3095 send a Prune(*,G) to RPF'(S,G). If the upstream router is an 3096 RFC 2362 compliant PIM router, then the Prune(*,G) will cause 3097 it to stop forwarding. For backwards compatibility, this 3098 router should override the prune so that forwarding continues. 3100 The upstream (S,G) state machine remains in Joined state. If 3101 the Join Timer is set to expire in more than t_override 3102 seconds, reset it so that it expires after t_override seconds. 3104 RPF'(S,G) changes 3105 The current next hop towards S changes due to an Assert(S,G) 3106 on the RPF_interface(S). 3108 The upstream (S,G) state machine remains in Joined state. If 3109 the Join Timer is set to expire in more than t_override 3110 seconds, reset it so that it expires after t_override seconds. 3111 If the Join Timer is set to expire in less than t_override 3112 seconds, leave it unchanged. 3114 MRIB.next_hop(S) changes 3115 A change in the routing base stored in the MRIB causes the 3116 next hop towards S to change. 3118 The upstream (S,G) state machine remains in Joined state. 3119 Send Prune(S,G) to the old upstream neighbor, which is the old 3120 value of RPF'(S,G). Send Join(S,G) to the new upstream 3121 neighbor which is the new value of MRIB.next_hop(S). Note 3122 that the Join goes to MRIB.next_hop(S) and not RPF'(S,G) even 3123 if the new neighbor is on the same interface as the old one 3124 because the routing change may cause MRIB.next_hop(S) to have 3125 a better path to S than RPF'(S,G); sending to MRIB.next_hop(S) 3126 ensures that this is discovered. Set the Join Timer (JT) to 3127 expire after t_periodic seconds. 3129 RPF'(S,G) GenID changes 3130 The Generation ID of the router that is RPF'(S,G) changes. 3131 This normally means that this neighbor has lost state, and so 3132 the state must be refreshed. 3134 The upstream (S,G) state machine remains in Joined state. If 3135 the Join Timer is set to expire in more than t_override 3136 seconds, reset it so that it expires after t_override seconds. 3138 4.5.8. (S,G,rpt) Periodic Messages 3140 (S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP tree 3141 with the RPT bit set, either to modify the results of (*,G) Joins, or to 3142 override the behavior of other upstream LAN peers. The next section 3143 describes the rules for sending triggered messages. This section 3144 describes the rules for including an Prune(S,G,rpt) message with a 3145 Join(*,G). 3147 When a router is going to send a Join(*,G), it should use the following 3148 pseudocode, for each (S,G) for which it has state, to decide whether to 3149 include a Prune(S,G,rpt) in the compound Join/Prune message: 3151 if( SPTbit(S,G) == TRUE ) { 3152 # Note: If receiving (S,G) on the SPT, we only prune off the 3153 # shared tree if the rpf neighbors differ. 3154 if( RPF'(*,G) != RPF'(S,G) ) { 3155 add Prune(S,G,rpt) to compound message 3156 } 3157 } else if ( inherited_olist(S,G,rpt) == NULL ) { 3158 # Note: all (*,G) olist interfaces sent rpt prunes for (S,G). 3159 add Prune(S,G,rpt) to compound message 3160 } else if ( RPF'(*,G) != RPF'(S,G,rpt) { 3161 # Note: we joined the shared tree, but there was an (S,G) assert and 3162 # the source tree RPF neighbor is different. 3163 add Prune(S,G,rpt) to compound message 3164 } 3166 Note that Join(S,G,rpt) is not normally sent as a periodic message, but 3167 only as a triggered message. 3169 4.5.9. State Machine for (S,G,rpt) Triggered Messages 3171 The state machine for (S,G,rpt) triggered messages is required per-(S,G) 3172 when there is (*,G) or (*,*,RP) join state at a router, and the router 3173 or any of its upstream LAN peers wishes to prune S off the RP tree. 3175 There are three states in the state-machine. One of the states is when 3176 there is neither (*,G) nor (*,*,RP(G)) join state at this router. If 3177 there is (*,G) or (*,*,RP(G)) join state at the router, then the state 3178 machine must be at one of the other two states: 3180 Pruned(S,G,rpt) 3181 (*,G) or (*,*,RP(G)) Joined, but (S,G,rpt) pruned 3183 NotPruned(S,G,rpt) 3184 (*,G) or (*,*,RP(G)) Joined, and (S,G,rpt) not pruned 3186 RPTNotJoined(G) 3187 neither (*,G) nor (*,*,RP(G)) has not been joined. 3189 In addition there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which is 3190 used to delay triggered Join(S,G,rpt) messages to prevent implosions of 3191 triggered messages. 3193 Figure 9: Upstream (S,G,rpt) state-machine for triggered messages in 3194 tabular form 3196 +--------------++------------------------------------------------------------------+ 3197 | || Event | 3198 | ++-------------+--------------+-------------------+-----------------+ 3199 |Prev State ||PruneDesired | PruneDesired | RPTJoinDesired(G) | inherited_olist | 3200 | ||(S,G,rpt) | (S,G,rpt) | ->False | (S,G,rpt) | 3201 | ||->True | ->False | | ->non-NULL | 3202 +--------------++-------------+--------------+-------------------+-----------------+ 3203 |RPTNotJoined ||-> P state | - | - | -> NP state | 3204 |(G) (NJ) || | | | | 3205 +--------------++-------------+--------------+-------------------+-----------------+ 3206 |Pruned ||- | -> NP state | -> NJ state | - | 3207 |(S,G,rpt) (P) || | Send Join | | | 3208 | || | (S,G,rpt) | | | 3209 +--------------++-------------+--------------+-------------------+-----------------+ 3210 | ||-> P state | - | -> NJ state | - | 3211 |NotPruned ||Send Prune | | Cancel OT timer | | 3212 |(S,G,rpt) ||(S,G,rpt); | | | | 3213 |(NP) ||Cancel OT | | | | 3214 | ||timer | | | | 3215 +--------------++-------------+--------------+-------------------+-----------------+ 3216 Additionally, we have the following transitions within the 3217 NotPruned(S,G,rpt) state which are all used for prune override behavior. 3219 +-----------------------------------------------------------------------+ 3220 | In NotPruned(S,G,rpt) State | 3221 +------------+--------------+--------------+-------------+--------------+ 3222 |OT timer |See Prune |See Join |See Prune | RPF' | 3223 |expires |(S,G,rpt) to |(S,G,rpt) to |(S,G) to | (S,G,rpt) -> | 3224 | |RPF' |RPF' |RPF' | RPF' (*,G) | 3225 | |(S,G,rpt) |(S,G,rpt) |(S,G,rpt) | | 3226 +------------+--------------+--------------+-------------+--------------+ 3227 |Send Join |OT timer = |Cancel OT |OT timer = | OT timer = | 3228 |(S,G,rpt); |min(timer, |timer |min(timer, | min(timer, | 3229 |Cancel OT |t_override) | |t_override) | t_override) | 3230 |timer | | | | | 3231 +------------+--------------+--------------+-------------+--------------+ 3233 Note that the min function in the above state machine considers a non- 3234 running timer to have an infinite value (e.g. min(not-running, 3235 t_override) = t_override). 3237 This state machine uses the following macros: 3239 bool RPTJoinDesired(G) { 3240 return (JoinDesired(*,G) || JoinDesired(*,*,RP(G))) 3241 } 3243 RPTJoinDesired(G) is true when the router has forwarding state that 3244 would cause it to forward traffic for G using either (*,G) or (*,*,RP) 3245 shared tree state. 3247 bool PruneDesired(S,G,rpt) { 3248 return ( RPTJoinDesired(G) AND 3249 ( inherited_olist(S,G,rpt) == NULL 3250 OR (SPTbit(S,G)==TRUE 3251 AND (RPF'(*,G) != RPF'(S,G)) ))) 3252 } 3254 PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true. If 3255 RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true if either 3256 there are no outgoing interfaces that S would be forwarded on, or if the 3257 router has active (S,G) forwarding state but RPF'(*,G) != RPF'(S,G). 3259 The state machine contains the following transition events: 3261 See Join(S,G,rpt) to RPF'(S,G,rpt) 3262 This event is only relevant in the "Not Pruned" state. 3264 The router sees a Join(S,G,rpt) from someone else to RPF'(S,G,rpt), 3265 which is the correct upstream neighbor. If we're in "NotPruned" 3266 state and the (S,G,rpt) Override Timer is running, then this is 3267 because we have been triggered to send our own Join(S,G,rpt) to 3268 RPF'(S,G,rpt). Someone else beat us to it, so there's no need to 3269 send our own Join. 3271 The action is to cancel the Override Timer. 3273 See Prune(S,G,rpt) to RPF'(S,G,rpt) 3274 This event is only relevant in the "NotPruned" state. 3276 The router sees a Prune(S,G,rpt) from someone else to to 3277 RPF'(S,G,rpt), which is the correct upstream neighbor. If we're in 3278 the "NotPruned" state, then we want to continue to receive traffic 3279 from S destined for G, and that traffic is being supplied by 3280 RPF'(S,G,rpt). Thus we need to override the Prune. 3282 The action is to set the (S,G,rpt) Override Timer to the randomized 3283 prune-override interval, t_override. However if the Override Timer 3284 is already running, we only set the timer if doing so would set it 3285 to a lower value. At the end of this interval, if no-one else has 3286 sent a Join, then we will do so. 3288 See Prune(S,G) to RPF'(S,G,rpt) 3289 This event is only relevant in the "NotPruned" state. 3291 This transition and action are the same as the above transition and 3292 action, except that the Prune does not have the RPT bit set. This 3293 transition is necessary to be compatible with routers implemented 3294 from RFC2362 that don't maintain separate (S,G) and (S,G,rpt) 3295 state. 3297 The (S,G,rpt) prune Override Timer expires 3298 This event is only relevant in the "NotPruned" state. 3300 When the Override Timer expires, we must send a Join(S,G,rpt) to 3301 RPF'(S,G,rpt) to override the Prune message that caused the timer 3302 to be running. We only send this if RPF'(S,G,rpt) equals RPF'(*,G) 3303 - if this were not the case, then the Join might be sent to a 3304 router that does not have (*,G) or (*,*,RP(G)) Join state, and so 3305 the behavior would not be well defined. If RPF'(S,G,rpt) is not 3306 the same as RPF'(*,G), then it may stop forwarding S. However, if 3307 this happens, then the router will send an AssertCancel(S,G), which 3308 would then cause RPF'(S,G,rpt) to become equal to RPF'(*,G) (see 3309 below). 3311 RPF'(S,G,rpt) changes to become equal to RPF'(*,G) 3312 This event is only relevant in the "NotPruned" state. 3314 RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G) 3315 Assert has happened, which means that traffic from S is arriving on 3316 the SPT, and so Prune(S,G,rpt) will have been sent to RPF'(*,G). 3317 When RPF'(S,G,rpt) changes to become equal to RPF'(*,G), we need to 3318 trigger a Join(S,G,rpt) to RPF'(*,G) to cause that router to start 3319 forwarding S again. 3321 The action is to set the (S,G,rpt) Override Timer to the randomized 3322 prune-override interval t_override. However if the timer is 3323 already running, we only set the timer if doing so would set it to 3324 a lower value. At the end of this interval, if no-one else has 3325 sent a Join, then we will do so. 3327 PruneDesired(S,G,rpt)->TRUE 3328 See macro above. This event is relevant in the "NotPruned" and 3329 "RPTNotJoined(G)" states. 3331 The router wishes to receive traffic for G, but does not wish to 3332 receive traffic from S destined for G. This causes the router to 3333 transition into the Pruned state. 3335 If the router was previously in NotPruned state, then the action is 3336 to send a Prune(S,G,rpt) to RPF'(S,G,rpt), and to cancel the 3337 Override Timer. If the router was previously in RPTNotJoined(G) 3338 state, then there is no need to trigger an action in this state 3339 machine because sending a Prune(S,G,rpt) is handled by the rules 3340 for sending the Join(*,G) or Join(*,*,RP). 3342 PruneDesired(S,G,rpt)->FALSE 3343 See macro above. This transition is only relevant in the "Pruned" 3344 state. 3346 If the router is in the Pruned(S,G,rpt) state, and 3347 PruneDesired(S,G,rpt) changes to FALSE, this could be because the 3348 router no longer has RPTJoinDesired(G) true, or it now wishes to 3349 receive traffic from S again. If it is the former, then this 3350 transition should not happen, but instead the 3351 "RPTJoinDesired(G)->FALSE" transition should happen. Thus this 3352 transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE 3353 AND RPTJoinDesired(G)==TRUE" 3355 The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt). 3357 RPTJoinDesired(G)->FALSE 3358 This event is relevant in the "Pruned" and "NotPruned" states. 3360 The router no longer wishes to receive any traffic destined for G 3361 on the RP Tree. This causes a transition to the RPTNotJoined(G) 3362 state, and the Override Timer is canceled if it was running. Any 3363 further actions are handled by the appropriate upstream state 3364 machine for (*,G) or (*,*,RP). 3366 inherited_olist(S,G,rpt) becomes non-NULL 3367 This transition is only relevant in the RPTNotJoined(G) state. 3369 The router has joined the RP tree (handled by the (*,G) or (*,*,RP) 3370 upstream state machine as appropriate), and wants to receive 3371 traffic from S. This does not trigger any events in this state 3372 machine, but causes a transition to the NotPruned(S,G,rpt) state. 3374 4.6. PIM Assert Messages 3376 Where multiple PIM routers peer over a shared LAN it is possible for 3377 more than one upstream router to have valid forwarding state for a 3378 packet, which can lead to packet duplication (see Section 3 "Multi- 3379 access LANs"). PIM does not attempt to prevent this from occurring. 3380 Instead it detects when this has happened and elects a single forwarder 3381 amongst the upstream routers to prevent further duplication. This 3382 election is performed using PIM Assert messages. Assert messages are 3383 also received by downstream routers on the LAN, and these cause 3384 subsequent Join/Prune messages to be sent to the upstream router that 3385 won the Assert. 3387 In general, a PIM Assert message should only be accepted for processing 3388 if it comes from a known PIM neighbor. A PIM router hears about PIM 3389 neighbors through PIM Hello messages. If a router receives an Assert 3390 message from a particular IP source address and it has not seen a PIM 3391 Hello message from that source address, then the Assert message SHOULD 3392 be discarded without further processing. In addition, if the Hello 3393 message from a neighbor was authenticated using IPsec AH (see section 3394 6.3) then all Assert messages from that neighbor MUST also be 3395 authenticated using IPsec AH. 3397 4.6.1. (S,G) Assert Message State Machine 3399 The (S,G) Assert state machine for interface I is shown in Figure 10. 3400 There are three states: 3402 NoInfo (NI) 3403 This router has no (S,G) assert state on interface I. 3405 I am Assert Winner (W) 3406 This router has won an (S,G) assert on interface I. It is now 3407 responsible for forwarding traffic from S destined for G out of 3408 interface I. Irrespective of whether it is the DR for I, while a 3409 router is the assert winner, it is also responsible for forwarding 3410 traffic onto I on behalf of local hosts on I that have made 3411 membership requests that specifically refer to S (and G). 3413 I am Assert Loser (L) 3414 This router has lost an (S,G) assert on interface I. It must not 3415 forward packets from S destined for G onto interface I. If it is 3416 the DR on I, it is no longer responsible for forwarding traffic 3417 onto I to satisfy local hosts with membership requests that 3418 specifically refer to S and G. 3420 In addition there is also a assert timer (AT) that is used to time out 3421 asserts on the assert losers and to resend asserts on the assert winner. 3423 Figure 10: Per-interface (S,G) Assert State-machine in tabular form 3425 +-----------------------------------------------------------------------+ 3426 | In NoInfo (NI) State | 3427 +---------------+-------------------+------------------+----------------+ 3428 | Receive | Receive Assert | Data arrives | Receive | 3429 | Inferior | with RPTbit | from S to G on | Preferred | 3430 | Assert with | set and | I and | Assert with | 3431 | RPTbit clear | CouldAssert | CouldAssert | RPTbit clear | 3432 | and | (S,G,I) | (S,G,I) | and AssTrDes | 3433 | CouldAssert | | | (S,G,I) | 3434 | (S,G,I) | | | | 3435 +---------------+-------------------+------------------+----------------+ 3436 | -> W state | -> W state | -> W state | -> L state | 3437 | [Actions A1] | [Actions A1] | [Actions A1] | [Actions A6] | 3438 +---------------+-------------------+------------------+----------------+ 3440 +-----------------------------------------------------------------------+ 3441 | In I Am Assert Winner (W) State | 3442 +-----------------+-----------------+------------------+----------------+ 3443 | Timer Expires | Receive | Receive | CouldAssert | 3444 | | Inferior | Preferred | (S,G,I) -> | 3445 | | Assert | Assert | FALSE | 3446 +-----------------+-----------------+------------------+----------------+ 3447 | -> W state | -> W state | -> L state | -> NI state | 3448 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3449 +-----------------+-----------------+------------------+----------------+ 3451 +-------------------------------------------------------------------------+ 3452 | In I Am Assert Loser (L) State | 3453 +-------------+--------------+--------------+--------------+--------------+ 3454 |Receive | Receive | Receive | Timer | Current | 3455 |Preferred | Acceptable | Inferior | Expires | Winner's | 3456 |Assert | Assert from | Assert from | | GenID | 3457 | | Current | Current | | changes | 3458 | | Winner | Winner | | | 3459 +-------------+--------------+--------------+--------------+--------------+ 3460 |-> L state | -> L state | -> NI state | -> NI state | -> NI state | 3461 |[Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 3462 +-------------+--------------+--------------+--------------+--------------+ 3463 +-----------------------------------------------------------------------+ 3464 | In I Am Assert Loser (L) State | 3465 +----------------+-----------------+-------------------+----------------+ 3466 | AssTrDes | my_metric -> | RPF_interface | Receive | 3467 | (S,G,I) -> | better than | (S) stops | Join(S,G) on | 3468 | FALSE | winner's | being I | interface I | 3469 | | metric | | | 3470 +----------------+-----------------+-------------------+----------------+ 3471 | -> NI state | -> NI state | -> NI state | -> NI State | 3472 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 3473 +----------------+-----------------+-------------------+----------------+ 3475 Note that for reasons of compactness, "AssTrDes(S,G,I)" is used in the 3476 state-machine table to refer to AssertTrackingDesired(S,G,I). 3478 Terminology: 3479 A "preferred assert" is one with a better metric than the current 3480 winner. 3482 An "acceptable assert" is one that has a better metric than 3483 my_assert_metric(S,G,I). 3485 An "inferior assert" is one with a worse metric than 3486 my_assert_metric(S,G,I). 3487 The state machine uses the following macros: 3489 CouldAssert(S,G,I) = 3490 SPTbit(S,G)==TRUE 3491 AND (RPF_interface(S) != I) 3492 AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 3493 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3494 (-) lost_assert(*,G) 3495 (+) joins(S,G) (+) pim_include(S,G) ) ) 3497 CouldAssert(S,G,I) is true for downstream interfaces which would be in 3498 the inherited_olist(S,G) if (S,G) assert information was not taken into 3499 account. 3501 AssertTrackingDesired(S,G,I) = 3502 (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 3503 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3504 (-) lost_assert(*,G) 3505 (+) joins(S,G) ) ) 3506 OR (local_receiver_include(S,G,I)==TRUE 3507 AND (I_am_DR(I) OR AssertWinner(S,G,I) == me)) 3508 OR (RPF_interface(S)==I AND JoinDesired(S,G)==TRUE) 3509 OR (RPF_interface(RP)==I AND JoinDesired(*,G)==TRUE 3510 AND SPTbit(S,G)==FALSE) 3512 AssertTrackingDesired(S,G,I) is true on any interface in which an (S,G) 3513 assert might affect our behavior. 3515 The first three lines of AssertTrackingDesired account for (*,G) join 3516 and local membership information received on I that might cause the 3517 router to be interested in asserts on I. 3519 The 4th line accounts for (S,G) join information received on I that 3520 might cause the router to be interested in asserts on I. 3522 The 5th and 6th lines account for (S,G) local membership information on 3523 I. Note that we can't use the pim_include(S,G) macro since it uses 3524 lost_assert(S,G,I) and would result in the router forgetting that it 3525 lost an assert if the only reason it was interested was local 3526 membership. The AssertWinner(S,G,I) check forces an assert winner to 3527 keep on being responsible for forwarding as long as local receivers are 3528 present. Removing this check would make the assert winner give up 3529 forwarding as soon as the information that originally caused it to 3530 forward went away and the task of forwarding for local receivers would 3531 revert back to the DR. 3533 The last three lines account for the fact that a router must keep track 3534 of assert information on upstream interfaces in order to send joins and 3535 prunes to the proper neighbor. 3537 Transitions from NoInfo State 3539 When in NoInfo state, the following events may trigger transitions: 3541 Receive Inferior Assert with RPTbit cleared AND 3542 CouldAssert(S,G,I)==TRUE 3543 An assert is received for (S,G) with the RPT bit cleared that 3544 is inferior to our own assert metric. The RPT bit cleared 3545 indicates that the sender of the assert had (S,G) forwarding 3546 state on this interface. If the assert is inferior to our 3547 metric, then we must also have (S,G) forwarding state (i.e. 3548 CouldAssert(S,G,I)==TRUE) as (S,G) asserts beat (*,G) asserts, 3549 and so we should be the assert winner. We transition to the 3550 "I am Assert Winner" state, and perform Actions A1 (below). 3552 Receive Assert with RPTbit set AND CouldAssert(S,G,I)==TRUE 3553 An assert is received for (S,G) on I with the RPT bit set 3554 (it's a (*,G) assert). CouldAssert(S,G,I) is TRUE only if we 3555 have (S,G) forwarding state on this interface, so we should be 3556 the assert winner. We transition to the "I am Assert Winner" 3557 state, and perform Actions A1 (below). 3559 An (S,G) data packet arrives on interface I, AND 3560 CouldAssert(S,G,I)==TRUE 3561 An (S,G) data packet arrived on an downstream interface which 3562 is in our (S,G) outgoing interface list. We optimistically 3563 assume that we will be the assert winner for this (S,G), and 3564 so we transition to the "I am Assert Winner" state, and 3565 perform Actions A1 (below) which will initiate the assert 3566 negotiation for (S,G). 3568 Receive Preferred Assert with RPT bit clear AND 3569 AssertTrackingDesired(S,G,I)==TRUE 3570 We're interested in (S,G) Asserts, either because I is a 3571 downstream interface for which we have (S,G) or (*,G) 3572 forwarding state, or because I is the upstream interface for S 3573 and we have (S,G) forwarding state. The received assert that 3574 has a better metric than our own, so we do not win the Assert. 3575 We transition to "I am Assert Loser" and perform actions A6 3576 (below). 3578 Transitions from "I am Assert Winner" State 3580 When in "I am Assert Winner" state, the following events trigger 3581 transitions: 3583 Timer Expires 3584 The (S,G) assert timer expires. As we're in the Winner state, 3585 then we must still have (S,G) forwarding state that is 3586 actively being kept alive. We re-send the (S,G) Assert and 3587 restart the timer (Action A3 below). Note that the assert 3588 winner's timer is engineered to expire shortly before timers 3589 on assert losers; this prevents unnecessary thrashing of the 3590 forwarder and periodic flooding of duplicate packets. 3592 Receive Inferior Assert 3593 We receive an (S,G) assert or (*,G) assert mentioning S that 3594 has a worse metric than our own. Whoever sent the assert is 3595 in error, and so we re-send an (S,G) Assert, and restart the 3596 timer (Action A3 below). 3598 Receive Preferred Assert 3599 We receive an (S,G) assert that has a better metric than our 3600 own. We transition to "I am Assert Loser" state and perform 3601 actions A2 (below). Note that this may affect the value of 3602 JoinDesired(S,G) and PruneDesired(S,G,rpt) which could cause 3603 transitions in the upstream (S,G) or (S,G,rpt) state machines. 3605 CouldAssert(S,G,I) -> FALSE 3606 Our (S,G) forwarding state or RPF interface changed so as to 3607 make CouldAssert(S,G,I) become false. We can no longer 3608 perform the actions of the assert winner, and so we transition 3609 to NoInfo state and perform actions A4 (below). This includes 3610 sending a "canceling assert" with an infinite metric. 3612 Transitions from "I am Assert Loser" State 3614 When in "I am Assert Loser" state, the following transitions can occur: 3616 Receive Preferred Assert 3617 We receive an assert that is better than that of the current 3618 assert winner. We stay in Loser state, and perform actions A2 3619 below. 3621 Receive Acceptable Assert from Current Winner 3622 We receive an assert from the current assert winner that is 3623 better than our own metric for this (S,G) (although the metric 3624 may be worse than the winner's previous metric). We stay in 3625 Loser state, and perform actions A2 below. 3627 Receive Inferior Assert from Current Winner 3628 We receive an assert from the current assert winner that is 3629 worse than our own metric for this group (typically the 3630 winner's metric became worse). We transition to NoInfo state, 3631 deleting the (S,G) assert information and allowing the normal 3632 PIM Join/Prune mechanisms to operate. Usually we will 3633 eventually re-assert and win when data packets from S have 3634 started flowing again. 3636 Timer Expires 3637 The (S,G) assert timer expires. We transition to NoInfo 3638 state, deleting the (S,G) assert information (action A5 3639 below). 3641 Current Winner's GenID Changes 3642 We receive a Hello message from the current winner reporting a 3643 different GenID from the one it previously reported. This 3644 indicates that the current winner's interface or router has 3645 gone down and come back up, and so we must assume it no longer 3646 knows it was the winner. We transition to the NoInfo state, 3647 deleting this (S,G) assert information (action A5 below). 3649 AssertTrackingDesired(S,G,I)->FALSE 3650 AssertTrackingDesired(S,G,I) becomes FALSE. Our forwarding 3651 state has changed so that (S,G) Asserts on interface I are no 3652 longer of interest to us. We transition to the NoInfo state, 3653 deleting the (S,G) assert information. 3655 My metric becomes better than the assert winner's metric 3656 my_assert_metric(S,G,I) has changed so that now my assert 3657 metric for (S,G) is better than the metric we have stored for 3658 current assert winner. This might happen the underlying 3659 routing metric changes, or when CouldAssert(S,G,I) becomes 3660 true; for example, when SPTbit(S,G) becomes true. We 3661 transition to NoInfo state, delete this (S,G) assert state 3662 (action A5 below), and allow the normal PIM Join/Prune 3663 mechanisms to operate. Usually we will eventually re-assert 3664 and win when data packets from S have started flowing again. 3666 RPF interface changed away from interface I 3667 Interface I used to be the RPF interface for S, and now it is 3668 not. We transition to NoInfo state, deleting this (S,G) 3669 assert state (action A5 below). 3671 Receive Join(S,G) on Interface I 3672 We receive a Join(S,G) that has the Upstream Neighbor Address 3673 field set to one my IP address on interface I. The action is 3674 to transition to NoInfo state, and delete this (S,G) assert 3675 state (action A5 below), and allow the normal PIM Join/Prune 3676 mechanisms to operate. If whoever sent the Join was in error, 3677 then the normal assert mechanism will eventually re-apply and 3678 we will lose the assert again. However whoever sent the 3679 assert may know that the previous assert winner has died, and 3680 so we may end up being the new forwarder. 3682 (S,G) Assert State-machine Actions 3684 A1: Send Assert(S,G) 3685 Set timer to (Assert_Time - Assert_Override_Interval) 3686 Store self as AssertWinner(S,G,I) 3687 Store spt_assert_metric(S,I) as AssertWinnerMetric(S,G,I) 3689 A2: Store new assert winner as AssertWinner(S,G,I) and assert 3690 winner metric as AssertWinnerMetric(S,G,I). 3691 Set timer to Assert_Time 3693 A3: Send Assert(S,G) 3694 Set timer to (Assert_Time - Assert_Override_Interval) 3696 A4: Send AssertCancel(S,G) 3697 Delete assert info (AssertWinner(S,G,I) and 3698 AssertWinnerMetric(S,G,I) will then return their default 3699 values). 3701 A5: Delete assert info (AssertWinner(S,G,I) and 3702 AssertWinnerMetric(S,G,I) will then return their default 3703 values). 3705 A6: Store new assert winner as AssertWinner(S,G,I) and assert 3706 winner metric as AssertWinnerMetric(S,G,I). 3707 Set timer to Assert_Time 3708 If I is RPF_interface(S) set SPTbit(S,G) to TRUE. 3710 Note that some of these actions may cause the value of JoinDesired(S,G), 3711 PruneDesired(S,G,rpt), or RPF'(S,G) to change, which could cause further 3712 transitions in other state machines. 3714 4.6.2. (*,G) Assert Message State Machine 3716 The (*,G) Assert state-machine for interface I is shown in Figure 11. 3717 There are three states: 3719 NoInfo (NI) 3720 This router has no (*,G) assert state on interface I. 3722 I am Assert Winner (W) 3723 This router has won an (*,G) assert on interface I. It is now 3724 responsible for forwarding traffic destined for G onto interface I 3725 with the exception of traffic for which it has (S,G) "I am Assert 3726 Loser" state. Irrespective of whether it is the DR for I, it is 3727 also responsible for handling the membership requests for G from 3728 local hosts on I. 3730 I am Assert Loser (L) 3731 This router has lost an (*,G) assert on interface I. It must not 3732 forward packets for G onto interface I with the exception of 3733 traffic from sources for which is has (S,G) "I am Assert Winner" 3734 state. If it is the DR, it is no longer responsible for handling 3735 the membership requests for group G from local hosts on I. 3737 In addition there is also an assert timer (AT) that is used to time out 3738 asserts on the assert losers and to resend asserts on the assert winner. 3740 When an Assert message is received, a PIM implementation must first 3741 match it against the possible events in the (S,G) assert state machine 3742 and process any transitions and actions, before considering whether the 3743 Assert message matches against the (*,G) assert state machine. 3745 It is important to note that NO TRANSITION CAN OCCUR in the (*,G) state 3746 machine as a result of receiving an Assert message unless the (S,G) 3747 assert state machine for the relevant S and G is in the "NoInfo" state 3748 after the (S,G) state machine has processed the message. Also NO 3749 TRANSITION CAN OCCUR in the (*,G) state machine as a result of receiving 3750 an assert message if that message triggers any change of state in the 3751 (S,G) state machine. 3753 For example, if both the (S,G) and (*,G) assert state machines where in 3754 the NoInfo state when an Assert message arrives, and the message causes 3755 the (S,G) state machine to transition to either "W" or "L" state, then 3756 the assert would not be processed by the (*,G) assert state machine. 3758 Another example: if the (S,G) assert state machine is in "L" state when 3759 an assert message is received, and the assert metric in the message is 3760 worse than my_assert_metric(S,G,I), then the (S,G) assert state machine 3761 will transition to NoInfo state. In such a case if the (*,G) assert 3762 state machine were in NoInfo state, it might appear that it would 3763 transition to "W" state, but this is not the case because this message 3764 already triggered a transition in the (S,G) assert state machine. 3766 Figure 11: (*,G) Assert State-machine in tabular form 3768 +-----------------------------------------------------------------------+ 3769 | In NoInfo (NI) State | 3770 +-----------------------+-----------------------+-----------------------+ 3771 | Receive Inferior | Data arrives for G | Receive Preferred | 3772 | Assert with RPTbit | and CouldAssert | Assert with RPTbit | 3773 | set and | (*,G,I) | set and AssTrDes | 3774 | CouldAssert(*,G,I) | | (*,G,I) | 3775 +-----------------------+-----------------------+-----------------------+ 3776 | -> W state | -> W state | -> L state | 3777 | [Actions A1] | [Actions A1] | [Actions A2] | 3778 +-----------------------+-----------------------+-----------------------+ 3780 +-----------------------------------------------------------------------+ 3781 | In I Am Assert Winner (W) State | 3782 +-----------------+-----------------+------------------+----------------+ 3783 | Timer Expires | Receive | Receive | CouldAssert | 3784 | | Inferior | Preferred | (*,G,I) -> | 3785 | | Assert | Assert | FALSE | 3786 +-----------------+-----------------+------------------+----------------+ 3787 | -> W state | -> W state | -> L state | -> NI state | 3788 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3789 +-----------------+-----------------+------------------+----------------+ 3791 +-------------------------------------------------------------------------+ 3792 | In I Am Assert Loser (L) State | 3793 +-------------+--------------+--------------+--------------+--------------+ 3794 |Receive | Receive | Receive | Timer | Current | 3795 |Preferred | Acceptable | Inferior | Expires | Winner's | 3796 |Assert | Assert from | Assert from | | GenID | 3797 | | Current | Current | | Changes | 3798 | | Winner | Winner | | | 3799 +-------------+--------------+--------------+--------------+--------------+ 3800 |-> L state | -> L state | -> NI state | -> NI state | -> NI state | 3801 |[Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 3802 +-------------+--------------+--------------+--------------+--------------+ 3804 ------------------------------------------------------------------------- 3805 In I Am Assert Loser (L) State 3806 ------------------------------------------------------------------------- 3807 AssTrDes my_metric -> RPF_interface Receive 3808 (*,G,I) -> better than (RP(G)) stops Join(*,G) or 3809 FALSE Winner's being I Join(*,*,RP(G)) 3810 metric on Interface I 3811 ------------------------------------------------------------------------- 3812 -> NI state -> NI state -> NI state -> NI State 3813 [Actions A5] [Actions A5] [Actions A5] [Actions A5] 3815 | | | | | 3816 | | | | | 3817 | | | | | 3818 INTERNET-DRAFT | Expires: September 2002 | March 2002| 3819 | | | | | 3820 | | | | | 3821 +---------------+-----------------+-----------------+-------------------+ 3823 The state machine uses the following macros: 3825 CouldAssert(*,G,I) = 3826 ( I in ( joins(*,*,RP(G)) (+) joins(*,G) 3827 (+) pim_include(*,G)) ) 3828 AND RPF_interface(RP(G)) != I 3830 CouldAssert(*,G,I) is true on downstream interfaces for which we have 3831 (*,*,RP(G)) or (*,G) join state, or local members that requested any 3832 traffic destined for G. 3834 AssertTrackingDesired(*,G,I) = 3835 CouldAssert(*,G) 3836 OR (local_receiver_include(*,G,I)==TRUE 3837 AND (I_am_DR(I) OR AssertWinner(*,G,I) == me)) 3838 OR (RPF_interface(RP(G)) == I AND RPTJoinDesired(G)) 3840 AssertTrackingDesired(*,G,I) is true on any interface on which an (*,G) 3841 assert might affect our behavior. 3843 Note that for reasons of compactness, "AssTrDes(*,G,I)" is used in the 3844 state-machine table to refer to AssertTrackingDesired(*,G,I). 3846 Terminology: 3847 A "preferred assert" is one with a better metric than the current 3848 winner. 3850 An "acceptable assert" is one that has a better metric than 3851 my_assert_metric(S,G,I). 3853 An "inferior assert" is one with a worse metric than 3854 my_assert_metric(S,G,I). 3856 Transitions from NoInfo State 3858 When in NoInfo state, the following events trigger transitions, but only 3859 if the (S,G) assert state machine is in NoInfo state: 3861 Receive Inferior Assert with RPTbit set AND 3862 CouldAssert(*,G,I)==TRUE 3863 An Inferior (*,G) assert is received for G on Interface I. If 3864 CouldAssert(*,G,I) is TRUE, then I is our downstream 3865 interface, and we have (*,G) forwarding state on this 3866 interface, so we should be the assert winner. We transition 3867 to the "I am Assert Winner" state, and perform Actions A1 3868 (below). 3870 A data packet destined for G arrives on interface I, AND 3871 CouldAssert(*,G,I)==TRUE 3872 A data packet destined for G arrived on a downstream interface 3873 which is in our (*,G) outgoing interface list. We therefore 3874 believe we should be the forwarder for this (*,G), and so we 3875 transition to the "I am Assert Winner" state, and perform 3876 Actions A1 (below). 3878 Receive Preferred Assert with RPT bit set AND 3879 AssertTrackingDesired(*,G,I)==TRUE 3880 We're interested in (*,G) Asserts, either because I is a 3881 downstream interface for which we have (*,G) forwarding state, 3882 or because I is the upstream interface for RP(G) and we have 3883 (*,G) forwarding state. We get a (*,G) Assert that has a 3884 better metric than our own, so we do not win the Assert. We 3885 transition to "I am Assert Loser" and perform actions A2 3886 (below). 3888 Transitions from "I am Assert Winner" State 3890 When in "I am Assert Winner" state, the following events trigger 3891 transitions, but only if the (S,G) assert state machine is in NoInfo 3892 state: 3894 Receive Inferior Assert 3895 We receive a (*,G) assert that has a worse metric than our 3896 own. Whoever sent the assert has lost, and so we re-send a 3897 (*,G) Assert, and restart the timer (Action A3 below). 3899 Receive Preferred Assert 3900 We receive a (*,G) assert that has a better metric than our 3901 own. We transition to "I am Assert Loser" state and perform 3902 actions A2 (below). 3904 When in "I am Assert Winner" state, the following events trigger 3905 transitions: 3907 Timer Expires 3908 The (*,G) assert timer expires. As we're in the Winner state, 3909 then we must still have (*,G) forwarding state that is 3910 actively being kept alive. To prevent unnecessary thrashing 3911 of the forwarder and periodic flooding of duplicate packets, 3912 we re-send the (*,G) Assert, and restart the timer (Action A3 3913 below). 3915 CouldAssert(*,G,I) -> FALSE 3916 Our (*,G) forwarding state or RPF interface changed so as to 3917 make CouldAssert(*,G,I) become false. We can no longer 3918 perform the actions of the assert winner, and so we transition 3919 to NoInfo state and perform actions A4 (below). 3921 Transitions from "I am Assert Loser" State 3923 When in "I am Assert Loser" state, the following events trigger 3924 transitions, but only if the (S,G) assert state machine is in NoInfo 3925 state: 3927 Receive Preferred Assert 3928 We receive a (*,G) assert that is better than that of the 3929 current assert winner. We stay in Loser state, and perform 3930 actions A2 below. 3932 Receive Acceptable Assert from Current Winner 3933 We receive a (*,G) assert from the current assert winner that 3934 is better than our own metric for this group (although the 3935 metric may be worse than the winner's previous metric). We 3936 stay in Loser state, and perform actions A2 below. 3938 Receive Inferior Assert from Current Winner 3939 We receive an assert from the current assert winner that is 3940 worse than our own metric for this group (typically because 3941 the winner's metric became worse). We transition to NoInfo 3942 state, delete this (*,G) assert state (action A5), and allow 3943 the normal PIM Join/Prune mechanisms to operate. Usually we 3944 will eventually re-assert and win when data packets for G have 3945 started flowing again. 3947 When in "I am Assert Loser" state, the following events trigger 3948 transitions: 3950 Timer Expires 3951 The (*,G) assert timer expires. We transition to NoInfo state 3952 and delete this (*,G) assert info (action A5). 3954 Current Winner's GenID Changes 3955 We receive a Hello message from the current winner reporting a 3956 different GenID from the one it previously reported. This 3957 indicates that the current winner's interface or router has 3958 gone down and come back up, and so we must assume it no longer 3959 knows it was the winner. We transition to the NoInfo state, 3960 deleting the (*,G) assert information (action A5). 3962 AssertTrackingDesired(*,G,I)->FALSE 3963 AssertTrackingDesired(*,G,I) becomes FALSE. Our forwarding 3964 state has changed so that (*,G) Asserts on interface I are no 3965 longer of interest to us. We transition to NoInfo state and 3966 delete this (*,G) assert info (action A5). 3968 My metric becomes better than the assert winner's metric 3969 My routing metric, rpt_assert_metric(G,I), has changed so that 3970 now my assert metric for (*,G) is better than the metric we 3971 have stored for current assert winner. We transition to 3972 NoInfo state, and delete this (*,G) assert state (action A5), 3973 and allow the normal PIM Join/Prune mechanisms to operate. 3974 Usually we will eventually re-assert and win when data packets 3975 for G have started flowing again. 3977 RPF_interface(RP(G)) stops being interface I 3978 Interface I used to be the RPF interface for RP(G), and now it 3979 is not. We transition to NoInfo state, and delete this (*,G) 3980 assert state (action A5). 3982 Receive Join(*,G) or Join(*,*,RP(G)) on interface I 3983 We receive a Join(*,G) or a Join(*,*,RP(G)) that has the 3984 Upstream Neighbor Address field set to my IP address on 3985 interface I. The action is to transition to NoInfo state, and 3986 delete this (*,G) assert state (action A5), and allow the 3987 normal PIM Join/Prune mechanisms to operate. If whoever sent 3988 the Join was in error, then the normal assert mechanism will 3989 eventually re-apply and we will lose the assert again. 3990 However whoever sent the assert may know that the previous 3991 assert winner has died, and so we may end up being the new 3992 forwarder. 3994 (*,G) Assert State-machine Actions 3996 A1: Send Assert(*,G) 3997 Set timer to (Assert_Time - Assert_Override_Interval) 3998 Store self as AssertWinner(*,G,I). 3999 Store rpt_assert_metric(G,I) as AssertWinnerMetric(*,G,I). 4001 A2: Store new assert winner as AssertWinner(*,G,I) and assert 4002 winner metric as AssertWinnerMetric(*,G,I). 4003 Set timer to Assert_Time 4005 A3: Send Assert(*,G) 4006 Set timer to (Assert_Time - Assert_Override_Interval) 4008 A4: Send AssertCancel(*,G) 4009 Delete assert info (AssertWinner(*,G,I) and 4010 AssertWinnerMetric(*,G,I) will then return their default 4011 values). 4013 A5: Delete assert info (AssertWinner(*,G,I) and 4014 AssertWinnerMetric(*,G,I) will then return their default 4015 values). 4017 Note that some of these actions may cause the value of JoinDesired(*,G) 4018 or RPF'(*,G)) to change, which could cause further transitions in other 4019 state machines. 4021 4.6.3. Assert Metrics 4023 Assert metrics are defined as: 4025 struct assert_metric { 4026 rpt_bit_flag; 4027 metric_preference; 4028 route_metric; 4029 ip_address; 4030 }; 4032 When comparing assert_metrics, the rpt_bit_flag, metric_preference, and 4033 route_metric field are compared in order, where the first lower value 4034 wins. If all fields are equal, the IP address of the router that 4035 sourced the Assert message is used as a tie-breaker, with the highest IP 4036 address winning. 4038 An assert metric for (S,G) to include in (or compare against) an Assert 4039 message sent on interface I should be computed using the following 4040 pseudocode: 4042 assert_metric 4043 my_assert_metric(S,G,I) { 4044 if( CouldAssert(S,G,I) == TRUE ) { 4045 return spt_assert_metric(S,I) 4046 } else if( CouldAssert(*,G,I) == TRUE ) { 4047 return rpt_assert_metric(G,I) 4048 } else { 4049 return infinite_assert_metric() 4050 } 4051 } 4053 spt_assert_metric(S,I) gives the assert metric we use if we're sending 4054 an assert based on active (S,G) forwarding state: 4056 assert_metric 4057 spt_assert_metric(S,I) { 4058 return {0,MRIB.pref(S),MRIB.metric(S),my_ip_address(I)} 4059 } 4061 rpt_assert_metric(G,I) gives the assert metric we use if we're sending 4062 an assert based only on (*,G) forwarding state: 4064 assert_metric 4065 rpt_assert_metric(G,I) { 4066 return {1,MRIB.pref(RP(G)),MRIB.metric(RP(G)),my_ip_address(I)} 4067 } 4069 MRIB.pref(X) and MRIB.metric(X) are the routing preference and routing 4070 metrics associated with the route to a particular (unicast) destination 4071 X, as determined by the MRIB. my_ip_address(I) is simply the router's 4072 IP address that is associated with the local interface I. 4074 infinite_assert_metric() gives the assert metric we need to send an 4075 assert but don't match either (S,G) or (*,G) forwarding state: 4077 assert_metric 4078 infinite_assert_metric() { 4079 return {1,infinity,infinity,0} 4080 } 4082 4.6.4. AssertCancel Messages 4084 An AssertCancel message is simply an RPT Assert message but with 4085 infinite metric. It is sent by the assert winner when it deletes the 4086 forwarding state that had caused the assert to occur. Other routers 4087 will see this metric, and it will cause any other router that has 4088 forwarding state to send its own assert, and to take over forwarding. 4090 An AssertCancel(S,G) is an infinite metric assert with the RPT bit set 4091 that names S as the source. 4093 An AssertCancel(*,G) is an infinite metric assert with the RPT bit set, 4094 and typically will name RP(G) as the source as it cannot name an 4095 appropriate S. 4097 AssertCancel messages are simply an optimization. The original Assert 4098 timeout mechanism will allow a subnet to eventually become consistent; 4099 the AssertCancel mechanism simply causes faster convergence. No special 4100 processing is required for an AssertCancel message, since it is simply 4101 an Assert message from the current winner. 4103 4.6.5. Assert State Macros 4105 The macros lost_assert(S,G,rpt,I), lost_assert(S,G,I), and 4106 lost_assert(*,G,I) are used in the olist computations of Section 4.1, 4107 and are defined as: 4109 bool lost_assert(S,G,rpt,I) { 4110 if ( RPF_interface(RP) == I OR 4111 ( RPF_interface(S) == I AND SPTbit(S,G) == TRUE ) ) { 4112 return FALSE 4113 } else { 4114 return ( AssertWinner(S,G,I) != NULL AND 4115 AssertWinner(S,G,I) != me ) 4116 } 4117 } 4119 bool lost_assert(S,G,I) { 4120 if ( RPF_interface(S) == I ) { 4121 return FALSE 4122 } else { 4123 return ( AssertWinner(S,G,I) != NULL AND 4124 AssertWinner(S,G,I) != me AND 4125 (AssertWinnerMetric(S,G,I) is better 4126 than spt_assert_metric(S,I) ) 4127 } 4128 } 4130 Note: the term "AssertWinnerMetric(S,G,I) is better than 4131 spt_assert_metric(S,I)" is required to correctly handle the transition 4132 phase when a router has (S,G) join state, but has not yet set the SPT 4133 bit. In this case it needs to ignore the assert state if it will win 4134 the assert once the SPT bit is set. 4136 bool lost_assert(*,G,I) { 4137 if ( RPF_interface(RP) == I ) { 4138 return FALSE 4139 } else { 4140 return ( AssertWinner(*,G,I) != NULL AND 4141 AssertWinner(*,G,I) != me ) 4142 } 4143 } 4145 AssertWinner(S,G,I) is the IP source address of the Assert(S,G) packet 4146 that won an Assert. 4148 AssertWinner(*,G,I) is the IP source address of the Assert(*,G) packet 4149 that won an Assert. 4151 AssertWinnerMetric(S,G,I) is the Assert metric of the Assert(S,G) packet 4152 that won an Assert. 4154 AssertWinnerMetric(*,G,I) is the Assert metric of the Assert(*,G) packet 4155 that won an Assert. 4157 AssertWinner(S,G,I) defaults to Null and AssertWinnerMetric(S,G,I) 4158 defaults to Infinity when in the NoInfo state. 4160 Summary of Assert Rules and Rationale 4162 This section summarizes the key rules for sending and reacting to 4163 asserts and the rationale for these rules. This section is not intended 4164 to be and should not be treated as a definitive specification of 4165 protocol behavior. The state machines and pseudocode should be 4166 consulted for that purpose. Rather, this section is intended to 4167 document important aspects of a the Assert protocol behavior and to 4168 provide information that may prove helpful to the reader in 4169 understanding and implementing this part of the protocol. 4171 1. Behavior: Downstream neighbors send Join(*,G) and Join(S,G) 4172 periodic messages to the appropriate RPF' neighbor, i.e., the RPF 4173 neighbor as modified by the assert process. They are not always 4174 sent to the RPF neighbor as indicated by the MRIB. Normal 4175 suppression and override rules apply. 4177 Rationale: By sending the periodic and triggered Join messages to 4178 the RPF' neighbor instead of to the RPF neighbor, the downstream 4179 router avoids re-triggering the Assert process with every Join. A 4180 side effect of sending Joins to the Assert winner is that traffic 4181 will not switch back to the "normal" RPF neighbor until the Assert 4182 times out. This will not happen until data stops flowing, if item 4183 8 below is implemented. 4185 2. Behavior: The assert winner for (*,G) acts as the local DR for 4186 (*,G) on behalf of IGMP/MLD members. 4188 Rationale: This is required to allow a single router to merge PIM 4189 and IGMP/MLD joins and leaves. Without this, overrides don't work. 4191 3. Behavior: The assert winner for (S,G) acts as the local DR for 4192 (S,G) on behalf of IGMPv3 members. 4194 Rationale: Same rationale as for 2. 4196 4. Behavior: (S,G) and (*,G) prune overrides are sent to the RPF' 4197 neighbor and not to the regular RPF neighbor. 4199 Rationale: Same as for 1. 4201 5. Behavior: An (S,G,rpt) prune override is not sent (at all) if 4202 RPF'(S,G,rpt) != RPF'(*,G). 4204 Rationale: This avoids keeping state alive on the (S,G) tree when 4205 only (*,G) downstream members are left. Also, it avoids sending 4206 (S,G,rpt) joins to a router that is not on the (*,G) tree. This 4207 behavior might be confusing although this specification does 4208 indicate that such a join should be dropped. 4210 6. Behavior: An assert loser that receives a Join(S,G) with an 4211 Upstream Neighbor Address that is one of its addresses on that 4212 interface cancels the (S,G) assert timer. 4214 Rationale: This is necessary in order to have rapid convergence in 4215 the event that the downstream router that initially sent a join to 4216 the prior Assert winner has undergone a topology change. 4218 7. Behavior: An assert loser that receives a Join(*,G) or a 4219 Join(*,*,RP(G)) with an Upstream Neighbor Address that is one of 4220 its addresses on that interface cancels the (*,G) assert timer and 4221 all (S,G) assert timers that do not have corresponding 4222 Prune(S,G,rpt) messages in the compound Join/Prune message. 4224 Rationale: Same as 6. 4226 8. Behavior: An assert winner for (*,G) or (S,G) sends a canceling 4227 assert when it is about to stop forwarding on a (*,G) or an (S,G) 4228 entry. This behavior does not apply to (S,G,rpt). 4230 Rationale: This allows switching back to the shared tree after the 4231 last SPT router on the LAN leaves. Doing this prevents downstream 4232 routers on the shared tree from keeping SPT state alive. 4234 9. Behavior: Re-send the assert messages before timing out an assert. 4235 (This behavior is optional.) 4237 Rationale: This prevents the periodic duplicates that would 4238 otherwise occur each time that an assert times out and is then re- 4239 established. 4241 10. Behavior: When RPF'(S,G,rpt) changes to be the same as RPF'(*,G) we 4242 need to trigger a Join(S,G,rpt) to MRIB.next_hop(RP(G)). 4244 Rationale: This allows switching back to the RPT after the last SPT 4245 member leaves. 4247 4.7. PIM Multicast Border Router Behavior 4249 In some cases PIM-SM domains will interconnect with non-PIM domains. In 4250 these cases, the border routers of the PIM domain speak PIM-SM on some 4251 interfaces and speak other multicast routing protocols on other 4252 interfaces. Such routers are termed PIM Multicast Border Routers or 4253 PMBRs. In general, RFC 2715 [13] provides rules for interoperability 4254 between different multicast routing protocols. In this section we 4255 specify how PMBRs differ from regular PIM-SM routers. 4257 >From the point of view of PIM-SM, a PMBR has two tasks: 4259 o To ensure that traffic from sources outside the PIM-SM domain reaches 4260 receivers inside the domain. 4262 o To ensure that traffic from sources inside the PIM-SM domain reaches 4263 receives outside the domain. 4265 We note that multiple PIM-SM domains are sometimes connected together 4266 using protocols such as MSDP, which provides information about active 4267 external sources, but does not follow RFC 2715. In such cases the 4268 domains are not connected via PMBRs because Join(S,G) messages traverse 4269 the border between domains. A PMBR is required when no PIM messages can 4270 traverse the border; typically this is because the routing protocol in 4271 the neighboring domain is not PIM-SM. 4273 4.7.1. Sources External to the PIM-SM Domain 4275 A PMBR needs to ensure that traffic from multicast sources external to 4276 the PIM-SM domain reaches receivers inside the domain. The PMBR will 4277 follow the rules in RFC 2715, such that traffic from external sources 4278 reaches the PMBR itself. 4280 According to RFC 2715, the PIM-SM component of the PMBR will receive an 4281 (S,G) Creation event when data from an (S,G) data packet from an 4282 external source first reaches the PMBR. If RPF_interface(S) is not an 4283 interface in the PIM-SM domain, the packet cannot be originated into the 4284 PIM domain at this router, and the PIM-SM component of the PMBR will not 4285 process the packet. Otherwise the PMBR will then act exactly as if it 4286 were the DR for this source (see section 4.4.1 with the following 4287 modifications: 4289 o The Border-bit is set in all PIM Register message sent for these 4290 sources. 4292 o DirectlyConnected(S) is treated as being TRUE for these sources. 4294 o The PIM-SM forwarding rule "iif == RPF_interface(S)" is relaxed to be 4295 TRUE if iif is any interface that is not part of the PIM-SM component 4296 of the PMBR (see section 4.2). 4298 4.7.2. Sources Internal to the PIM-SM Domain 4300 A PMBR needs to ensure that traffic from sources inside the PIM-SM 4301 domain reaches receivers outside the domain. Using terminology from RFC 4302 2715, there are two possible scenarios for this: 4304 o Another component of the PMBR is a wildcard receiver. In this case 4305 the PIM-SM component of the PMBR must ensure that traffic from all 4306 internal sources reaches the PMBR until it is informed otherwise. 4308 o No other component of the PMBR is a wildcard receiver. In this case 4309 the PMBR will receive explicit information as to which groups or 4310 (source,group) pairs the external domains wish to receive. 4312 In the former case, the PMBR will need to issue send a Join(*,*,RP) to 4313 all the RPs in the PIM-SM domain. This will cause all traffic in the 4314 domain to reach the PMBR. The PMBR may then act as if it were a DR with 4315 directly connected receivers, and trigger the transition to a shortest 4316 path tree (see section 4.2.1). 4318 In the latter case, the PMBR will not need to send Join(*,*,RP) 4319 messages. However the PMBR will still need to act as a DR with directly 4320 connected receivers on behalf of the external receivers in terms of 4321 being able to switch to the shortest-path tree for internally-reached 4322 sources. 4324 According to RFC 2715, the PIM-SM component of the PMBR may receive a 4325 number of alerts generated by events in the external routing components. 4326 To implement the above behavior, one reasonable way to map these alerts 4327 into PIM-SM state as follows: 4329 o When a PIM-SM component receives an (S,G) Prune alert, it sets 4330 local_receiver_include(S,G,I) to FALSE for the discard interface. 4332 o When a PIM-SM component receives a (*,G) Prune alert, it sets 4333 local_receiver_include(*,G,I) to FALSE for the discard interface. 4335 o When a PIM-SM component receives an (S,G) Join alert, it sets 4336 local_receiver_include(S,G,I) to TRUE for the discard interface. 4338 o When a PIM-SM component receives a (*,G) Join alert, it sets 4339 local_receiver_include(*,G,I) to TRUE for the discard interface. 4341 o When a PIM-SM component receives a (*,*) Join alert, it sets 4342 DownstreamJPState(*,*,RP,I) to Join state on the discard interface for 4343 all RPs in the PIM-SM domain. 4345 o When a PIM-SM component receives a (*,*) Prune alert, then it sets 4346 DownstreamJPState(*,*,RP,I) to NoInfo state on the discard interface 4347 for all RPs in the PIM-SM domain. 4349 We refer above to the discard interface because the macros and state- 4350 machines are interface-specific, but we need to have PIM state that is 4351 not associated with any actual PIM-SM interface. Implementors are free 4352 to implement this in any reasonable manner. 4354 Note that these state changes will then cause additional PIM-SM state 4355 machine transitions in the normal way. 4357 4.8. PIM Bootstrap and RP Discovery 4359 For correct operation, every PIM router within a PIM domain must be able 4360 to map a particular multicast group address to the same RP. If this is 4361 not the case then black holes may appear, where some receivers in the 4362 domain cannot receive some groups. A domain in this context is a 4363 contiguous set of routers that all implement PIM and are configured to 4364 operate within a common boundary defined by PIM Multicast Border Routers 4365 (PMBRs). PMBRs connect each PIM domain to the rest of the Internet. 4367 A notable exception to this is where a PIM domain is broken up into 4368 multiple administrative scope regions - these are regions where a border 4369 has been configured so that a range of multicast groups will not be 4370 forwarded across that border. For more information on Administratively 4371 Scoped IP Multicast, see RFC 2365. The modified criteria for admin- 4372 scoped regions are that the region is convex with respect to forwarding 4373 based on the MRIB, and that all PIM routers within the scope region map 4374 scoped groups to the same RP within that region. 4376 This specification does not mandate the use of a single mechanism to 4377 provide routers with the information to perform the group-to-RP mapping. 4378 Currently three mechanisms are possible, and all three have associated 4379 problems: 4381 Static Configuration 4382 A PIM router MUST support the static configuration of group-to-RP 4383 mappings. Such a mechanism is not robust to failures, but does at 4384 least provide a basic interoperability mechanism. 4386 Cisco's Auto-RP 4387 Auto-RP uses a PIM Dense-Mode multicast group to announce group-to- 4388 RP mappings from a central location. This mechanism is not useful 4389 if PIM Dense-Mode is not being run in parallel with PIM Sparse- 4390 Mode, and was only intended for use with PIM Sparse-Mode Version 1. 4391 No standard specification currently exists. 4393 BootStrap Router (BSR) 4394 RFC 2362 specifies a bootstrap mechanism based around the automatic 4395 election of a bootstrap router (BSR). Any router in the domain 4396 that is configured to be a possible RP reports its candidacy to the 4397 BSR, and then a domain-wide flooding mechanism distributes the 4398 BSR's chosen set of RPs throughout the domain. As specified in RFC 4399 2362, BSR is flawed in its handling of admin-scoped regions that 4400 are smaller than a PIM domain, but the mechanism does work for 4401 global-scoped groups. 4403 As far as PIM-SM is concerned, the only important requirement is that 4404 all routers in the domain (or admin scope zone for scoped regions) 4405 receive the same set of group-range-to-RP mappings. This may be 4406 achieved through the use of any of these mechanisms, or through 4407 alternative mechanisms not currently specified. 4409 Any RP address configured or learned MUST be a domain-wide reachable 4410 address. 4412 4.8.1. Group-to-RP Mapping 4414 Using one of the mechanisms described above, a PIM router receives one 4415 or more possible group-range-to-RP mappings. Each mapping specifies a 4416 range of multicast groups (expressed as a group and mask) and the RP to 4417 which such groups should be mapped. Each mapping may also have an 4418 associated priority. It is possible to receive multiple mappings all of 4419 which might match the same multicast group - this is the common case 4420 with BSR. The algorithm for performing the group-to-RP mapping is as 4421 follows: 4423 1 Perform longest match on group-range to obtain a list of RPs. 4425 2 From this list of matching RPs, find the one with highest priority. 4426 Eliminate any RPs from the list that have lower priorities. 4428 3 If only one RP remains in the list, use that RP. 4430 4 If multiple RPs are in the list, use the PIM hash function to 4431 choose one. 4433 Thus if two or more group-range-to-RP mappings cover a particular group, 4434 the one with the longest mask is the mapping to use. If the mappings 4435 have the same mask length, then the one with the highest priority is 4436 chosen. If there is more than one matching entry with the same longest 4437 mask and the priorities are identical, then a hash function (see Section 4438 4.8.2) is applied to choose the RP. 4440 This algorithm is invoked by a DR when it needs to determine an RP for a 4441 given group, e.g. upon reception of a packet or IGMP/MLD membership 4442 indication for a group for which the DR does not know the RP. It is 4443 invoked by any router that has (*,*,RP) state when a packet is received 4444 for which there is no corresponding (S,G) or (*,G) entry. Furthermore, 4445 the mapping function is invoked by all routers upon receiving a (*,G) or 4446 (*,*,RP) Join/Prune message. 4448 Note that if the set of possible group-range-to-RP mappings changes, 4449 each router will need to check whether any existing groups are affected. 4450 This may, for example, cause a DR or acting DR to re-join a group, or 4451 cause it to re-start register encapsulation to the new RP. 4453 Implementation note: the bootstrap mechanism described in RFC 4454 2362 omitted step (1) above. However of the implementations 4455 we are are of, approximately half performed step (1) anyway. 4456 It should be noted that implementations of BSR that omit step 4457 1 will not correctly interoperate with implementations of this 4458 specification when used with the BSR mechanism described in 4459 [7]. 4461 4.8.2. Hash Function 4463 The hash function is used by all routers within a domain, to map a group 4464 to one of the RPs from the matching set of group-range-to-RP mappings 4465 (this set all have the same longest mask length and same highest 4466 priority). The algorithm takes as input the group address, and the 4467 addresses of the candidate RPs from the mappings, and gives as output 4468 one RP address to be used. 4470 The protocol requires that all routers hash to the same RP within a 4471 domain (except for transients). The following hash function must be used 4472 in each router: 4474 1 For RP addresses in the matching group-range-to-RP mappings, 4475 compute a value: 4477 Value(G,M,C(i))= 4478 (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31 4480 where C(i) is the RP address and M is a hash-mask. If BSR is being 4481 used, the hash-mask is given in the Bootstrap messages. If BSR is 4482 not being used, the alternative mechanism that supplies the group- 4483 range-to-RP mappings may supply the value, or else it defaults to a 4484 mask with the most significant 30 bits being one for IPv4 and the 4485 most significant 126 bits being one for IPv6. The hash-mask allows 4486 a small number of consecutive groups (e.g., 4) to always hash to 4487 the same RP. For instance, hierarchically-encoded data can be sent 4488 on consecutive group addresses to get the same delay and fate- 4489 sharing characteristics. 4491 For address families other than IPv4, a 32-bit digest to be used as 4492 C(i) and G must first be derived from the actual RP or group 4493 address. Such a digest method must be used consistently throughout 4494 the PIM domain. For IPv6 addresses, we recommend using the 4495 equivalent IPv4 address for an IPv4-compatible address, and the 4496 exclusive-or of each 32-bit segment of the address for all other 4497 IPv6 addresses. For example, the digest of the IPv6 address 4498 3ffe:b00:c18:1::10 would be computed as 0x3ffe0b00 ^ 0x0c180001 ^ 4499 0x00000000 ^ 0x00000010, where ^ represents the exclusive-or 4500 operation. 4502 2 The candidate RP with the highest resulting hash value is then the 4503 RP chosen by this Hash Function. If more than one RP has the same 4504 highest hash value, the RP with the highest IP address is chosen. 4506 4.9. Source-Specific Multicast 4508 The Source-Specific Multicast (SSM) service model [10] can be 4509 implemented with a strict subset of the PIM-SM protocol mechanisms. 4510 Both regular IP Multicast and SSM semantics can coexist on a single 4511 router and both can be implemented using the PIM-SM protocol. A range 4512 of multicast addresses, currently 232.0.0.0/8 in IPv4, is reserved for 4513 SSM, and the choice of semantics is determined by the multicast group 4514 address in both data packets and PIM messages. 4516 4.9.1. Protocol Modifications for SSM destination addresses 4518 The following rules override the normal PIM-SM behavior for a multicast 4519 address G in the SSM reserved range: 4521 o A router MUST NOT send a (*,G) Join/Prune message for any reason. 4523 o A router MUST NOT send an (S,G,rpt) Join/Prune message for any reason. 4525 o A router MUST NOT send a Register message for any packet that is 4526 destined to an SSM address. 4528 o A router MUST NOT forward packets based on (*,G) or (S,G,rpt) state. 4529 The (*,G) and (S,G,rpt) -related state summarization macros are NULL 4530 for any SSM address, for the purposes of packet forwarding. 4532 o A router acting as an RP MUST NOT forward any Register-encapsulated 4533 packet that has an SSM destination address. 4535 The last two rules are present to deal with "legacy" routers unaware of 4536 SSM that may be sending (*,G) and (S,G,rpt) Join/Prunes, or Register 4537 messages for SSM destination addresses. 4539 Additionally: 4541 o A router MAY be configured to advertise itself as a Candidate RP for 4542 an SSM address. If so, it SHOULD respond with a RegisterStop message 4543 to any Register message containing a packet destined for an SSM 4544 address. 4546 o A router MAY optimize out the creation and maintenance of (S,G,rpt) 4547 and (*,G) state for SSM destination addresses -- this state is not 4548 needed for SSM packets. 4550 4.9.2. PIM-SSM-only Routers 4552 An implementor may choose to implement only the subset of PIM Sparse- 4553 Mode that provides SSM forwarding semantics. 4555 A PIM-SSM-only router MUST implement the following portions of this 4556 specification: 4558 o Upstream (S,G) state machine (Section 4.5.7) 4560 o Downstream (S,G) state machine (Section 4.5.3) 4562 o (S,G) Assert state machine (Section 4.6.1) 4564 o Hello messages, neighbor discovery and DR election (Section 4.3) 4566 o Packet forwarding rules (Section 4.2) 4568 A PIM-SSM-only router does not need to implement the following protocol 4569 elements: 4571 o Register state machine (Section 4.4) 4573 o (*,G), (S,G,rpt) and (*,*,RP) Downstream state machines (Sections 4574 4.5.2, 4.5.4, and 4.5.1) 4576 o (*,G), (S,G,rpt), and (*,*,RP) Upstream state machines (Sections 4577 4.5.6, 4.5.8, and 4.5.5) 4579 o (*,G) Assert state machine (Section 4.6.2) 4581 o Bootstrap RP Election (Section 4.8) 4583 o Keepalive Timer 4585 o SptBit (Section 4.2.2) 4587 The KeepaliveTimer should be treated as always running and SptBit should 4588 be treated as being always set for an SSM address. Additionally, the 4589 Packet forwarding rules of Section 4.2 can be simplified in a PIM-SSM- 4590 only router: 4592 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 4593 oiflist = inherited_olist(S,G) 4594 } else if( iif is in inherited_olist(S,G) ) { 4595 send Assert(S,G) on iif 4596 } 4598 oiflist = oiflist (-) iif 4599 forward packet on all interfaces in oiflist 4601 This is nothing more than the reduction of the normal PIM-SM forwarding 4602 rule, with all (S,G,rpt) and (*,G) clauses replaced with NULL. 4604 4.10. PIM Packet Formats 4606 This section describes the details of the packet formats for PIM control 4607 messages. 4609 All PIM control messages have IP protocol number 103. 4611 PIM messages are either unicast (e.g. Registers and RegisterStop), or 4612 multicast with TTL 1 to the `ALL-PIM-ROUTERS' group (e.g. Join/Prune, 4613 Asserts, etc.). The source address used for unicast messages is a 4614 domain-wide reachable address; the source address used for multicast 4615 messages is the link-local address of the interface on which the message 4616 is being sent. 4618 The IPv4 `ALL-PIM-ROUTERS' group is `224.0.0.13'. The IPv6 `ALL-PIM- 4619 ROUTERS' group is `ff02::d'. 4621 0 1 2 3 4622 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 4623 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4624 |PIM Ver| Type | Reserved | Checksum | 4625 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4627 PIM Ver 4628 PIM Version number is 2. 4630 Type Types for specific PIM messages. PIM Types are: 4632 Message Type Destination 4633 --------------------------------------------------------------------------- 4634 0 = Hello Multicast to ALL-PIM-ROUTERS 4635 1 = Register Unicast to RP 4636 2 = RegisterStop Unicast to source of Register packet 4637 3 = Join/Prune Multicast to ALL-PIM-ROUTERS 4638 4 = Bootstrap Multicast to ALL-PIM-ROUTERS 4639 5 = Assert Multicast to ALL-PIM-ROUTERS 4640 6 = Graft (used in PIM-DM only) Multicast to ALL-PIM-ROUTERS 4641 7 = Graft-Ack (used in PIM-DM only) Unicast to source of Graft packet 4642 8 = Candidate-RP-Advertisement Unicast to Domain's BSR 4644 Reserved 4645 Set to zero on transmission. Ignored upon receipt. 4647 Checksum 4648 The checksum is a standard IP checksum, i.e. the 16-bit one's 4649 complement of the one's complement sum of the entire PIM message, 4650 excluding the "Multicast data packet" section of the Register 4651 message. For computing the checksum, the checksum field is zeroed. 4653 For IPv6, the checksum also includes the IPv6 "pseudo-header", as 4654 specified in RFC 2460, section 8.1 [5]. This "pseudo-header" is 4655 prepended to the PIM header for the purposes of calculating the 4656 checksum. The "Upper-Layer Packet Length" in the pseudo-header is 4657 set to the length of the PIM message. The Next Header value used 4658 in the pseudo-header is 103. If the packet's length is not an 4659 integral number of 16-bit words, the packet is padded with a byte 4660 of zero before performing the checksum. 4662 4.10.1. Encoded Source and Group Address Formats 4664 Encoded-Unicast address 4666 An Encoded-Unicast address takes the following format: 4668 0 1 2 3 4669 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 4670 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4671 | Addr Family | Encoding Type | Unicast Address 4672 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4674 Addr Family 4675 The PIM address family of the `Unicast Address' field of this 4676 address. 4678 Values of 0-127 are as assigned by the IANA for Internet Address 4679 Families in [8]. Values 128-250 are reserved to be assigned by the 4680 IANA for PIM-specific Address Families. Values 251 though 255 are 4681 designated for private use. As there is no assignment authority 4682 for this space, collisions should be expected. 4684 Encoding Type 4685 The type of encoding used within a specific Address Family. The 4686 value `0' is reserved for this field, and represents the native 4687 encoding of the Address Family. 4689 Unicast Address 4690 The unicast address as represented by the given Address Family and 4691 Encoding Type. 4693 Encoded-Group address 4695 Encoded-Group addresses take the following format: 4697 0 1 2 3 4698 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 4699 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4700 | Addr Family | Encoding Type |B| Reserved |Z| Mask Len | 4701 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4702 | Group multicast Address 4703 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4705 Addr Family 4706 described above. 4708 Encoding Type 4709 described above. 4711 [B]idirectional PIM 4712 indicates the group range should use Bidirectional PIM [9]. For 4713 PIM-SM defined in this specification, this bit MUST be zero. 4715 Reserved 4716 Transmitted as zero. Ignored upon receipt. 4718 Admin Scope [Z]one 4719 indicates the group range is an admin scope zone. This is used in 4720 the Bootstrap Router Mechanism [7] only. For all other purposes, 4721 this bit is set to zero and ignored on receipt. 4723 Mask Len 4724 The Mask length field is 8 bits. The value is the number of 4725 contiguous one bits left justified used as a mask which, combined 4726 with the group address, describes a range of groups. It is less 4727 than or equal to the address length in bits for the given Address 4728 Family and Encoding Type. If the message is sent for a single group 4729 then the Mask length must equal the address length in bits for the 4730 given Address Family and Encoding Type. (e.g. 32 for IPv4 native 4731 encoding, 128 for IPv6 native encoding). 4733 Group multicast Address 4734 Contains the group address. 4736 Encoded-Source address 4738 Encoded-Source address takes the following format: 4740 0 1 2 3 4741 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 4742 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4743 | Addr Family | Encoding Type | Rsrvd |S|W|R| Mask Len | 4744 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4745 | Source Address 4746 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... 4748 Addr Family 4749 described above. 4751 Encoding Type 4752 described above. 4754 Reserved 4755 Transmitted as zero, ignored on receipt. 4757 S The Sparse bit is a 1 bit value, set to 1 for PIM-SM. It is used 4758 for PIM version 1 compatibility. 4760 W The WC (or WildCard) bit is a 1 bit value for use with PIM 4761 Join/Prune messages (see section 4.10.5.1 ). 4763 R The RPT (or Rendezvous Point Tree) bit is a 1 bit value for use 4764 with PIM Join/Prune messages (see section 4.10.5.1 ). If the WC bit 4765 is 1, the RPT bit MUST be 1. 4767 Mask Len 4768 The mask length field is 8 bits. The value is the number of 4769 contiguous one bits left justified used as a mask which, combined 4770 with the Source Address, describes a source subnet. The mask length 4771 MUST be equal to the mask length in bits for the given Address 4772 Family and Encoding Type (32 for IPv4 native and 128 for IPv6 4773 native). A router SHOULD ignore any messages received with any 4774 other mask length. 4776 Source Address 4777 The source address. 4779 4.10.2. Hello Message Format 4781 It is sent periodically by routers on all interfaces. 4783 0 1 2 3 4784 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 4785 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4786 |PIM Ver| Type | Reserved | Checksum | 4787 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4788 | OptionType | OptionLength | 4789 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4790 | OptionValue | 4791 | ... | 4792 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4793 | . | 4794 | . | 4795 | . | 4796 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4797 | OptionType | OptionLength | 4798 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4799 | OptionValue | 4800 | ... | 4801 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4803 PIM Version, Type, Reserved, Checksum 4804 Described above. 4806 OptionType 4807 The type of the option given in the following OptionValue field. 4809 OptionLength 4810 The length of the OptionValue field in bytes. 4812 OptionValue 4813 A variable length field, carrying the value of the option. 4815 The Option fields may contain the following values: 4817 o OptionType 1: Holdtime 4819 0 1 2 3 4820 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 4821 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4822 | Type = 1 | Length = 2 | 4823 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4824 | Holdtime | 4825 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4827 Holdtime is the amount of time a receiver must keep the neighbor 4828 reachable, in seconds. If the Holdtime is set to `0xffff', the 4829 receiver of this message never times out the neighbor. This may 4830 be used with dial-on-demand links, to avoid keeping the link up 4831 with periodic Hello messages. 4833 Hello messages with a Holdtime value set to `0' are also sent by 4834 a router on an interface about to go down or changing IP address 4835 (see section 4.3.1). These are effectively goodbye messages and 4836 the receiving routers should immediately time out the neighbor 4837 information for the sender. 4839 o OptionType 2: LAN Prune Delay 4841 0 1 2 3 4842 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 4843 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4844 | Type = 2 | Length = 4 | 4845 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4846 |T| LAN Delay | Override_Interval | 4847 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4849 The LAN_Prune_Delay option is used to tune the prune propagation 4850 delay on multi-access LANs. 4852 The T bit specifies the ability of the sending router to disable 4853 joins suppression. 4855 LAN Delay and Override_Interval are time intervals in units of 4856 milliseconds are are used to tune the value of the 4857 Override_Interval(I) and its derived timer values. Section 4.3.3 4858 describes how these values affect the behavior of a router. 4860 o OptionType 3 to 16: reserved to be defined in future versions of 4861 this document. 4863 o OptionType 18: deprecated and should not be used. 4865 o OptionType 19: DR Priority 4867 0 1 2 3 4868 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 4869 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4870 | Type = 19 | Length = 4 | 4871 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4872 | DR Priority | 4873 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4875 DR Priority is a 32-bit unsigned number and should be considered 4876 in the DR election as described in section 4.3.2. 4878 o OptionType 20: Generation ID 4880 0 1 2 3 4881 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 4882 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4883 | Type = 20 | Length = 4 | 4884 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4885 | Generation ID | 4886 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4888 Generation ID is a random 32-bit value for the interface on which 4889 the Hello message is sent. The Generation ID is regenerated 4890 whenever PIM forwarding is started or restarted on the interface. 4892 OptionTypes 17 thru 65000 are assigned by the IANA. OptionTypes 4893 65001 through 65535 are reserved for Private Use, as defined in 4894 [12]. 4895 Unknown options may be ignored. The "Holdtime" option MUST be 4896 implemented; the "DR Priority" and "Generation ID" options SHOULD 4897 be implemented. 4899 4.10.3. Register Message Format 4901 A Register message is sent by the DR or a PMBR to the RP when a 4902 multicast packet needs to be transmitted on the RP-tree. The IP source 4903 address is set to the address of the DR, the destination address to the 4904 RP's address. The IP TTL of the PIM packet is the system's normal 4905 unicast TTL. 4907 0 1 2 3 4908 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 4909 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4910 |PIM Ver| Type | Reserved | Checksum | 4911 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4912 |B|N| Reserved2 | 4913 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4914 | | 4915 . Multicast data packet . 4916 | | 4917 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4919 PIM Version, Type, Reserved, Checksum 4920 Described above. Note that the checksum for Registers is done only 4921 on first 8 bytes of the packet, including the PIM header and the 4922 next 4 bytes, excluding the data packet portion. For 4923 interoperability reasons, a message carrying a checksum calculated 4924 over the entire PIM Register message should also be accepted. 4926 B The Border bit. If the router is a DR for a source that it is 4927 directly connected to, it sets the B bit to 0. If the router is a 4928 PMBR for a source in a directly connected cloud, it sets the B bit 4929 to 1. 4931 N The Null-Register bit. Set to 1 by a DR that is probing the RP 4932 before expiring its local Register-Suppression timer. Set to 0 4933 otherwise. 4935 Reserved2 4936 Transmitted as zero, ignored on receipt. 4938 Multicast data packet 4939 The original packet sent by the source. This packet must be the of 4940 the same address family as the encapsulating PIM packet, e.g. an 4941 IPv6 data packet must be encapsulated in an IPv6 PIM packet. Note 4942 that the TTL of the original packet is decremented before 4943 encapsulation, just like any other packet that is forwarded. In 4944 addition, the RP decrements the TTL after decapsulating, before 4945 forwarding the packet down the shared tree. 4947 For (S,G) null Registers, the Multicast data packet portion 4948 contains only a dummy header with S as the source address, G as the 4949 destination address, and a data length of zero. 4951 4.10.4. RegisterStop Message Format 4953 A RegisterStop is unicast from the RP to the sender of the Register 4954 message. The IP source address is the address to which the register was 4955 addressed. The IP destination address is the source address of the 4956 register message. 4958 0 1 2 3 4959 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 4960 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4961 |PIM Ver| Type | Reserved | Checksum | 4962 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4963 | Group Address (Encoded-Group format) | 4964 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4965 | Source Address (Encoded-Unicast format) | 4966 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4968 PIM Version, Type, Reserved, Checksum 4969 Described above. 4971 Group Address 4972 The group address from the multicast data packet in the Register. 4973 Format described in section 4.10.1. Note that for RegisterStops the 4974 Mask Len field contains the full address length * 8 (e.g. 32 for 4975 IPv4 native encoding), if the message is sent for a single group. 4977 Source Address 4978 The host address of the source from the multicast data packet in 4979 the register. The format for this address is given in the Encoded- 4980 Unicast address in section 4.10.1. A special wild card value 4981 consisting of an address field of all zeroes can be used to 4982 indicate any source. 4984 4.10.5. Join/Prune Message Format 4986 A Join/Prune message is sent by routers towards upstream sources and 4987 RPs. Joins are sent to build shared trees (RP trees) or source trees 4988 (SPT). Prunes are sent to prune source trees when members leave groups 4989 as well as sources that do not use the shared tree. 4991 0 1 2 3 4992 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 4993 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4994 |PIM Ver| Type | Reserved | Checksum | 4995 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4996 | Upstream Neighbor Address (Encoded-Unicast format) | 4997 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4998 | Reserved | Num groups | Holdtime | 4999 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5000 | Multicast Group Address 1 (Encoded-Group format) | 5001 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5002 | Number of Joined Sources | Number of Pruned Sources | 5003 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5004 | Joined Source Address 1 (Encoded-Source format) | 5005 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5006 | . | 5007 | . | 5008 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5009 | Joined Source Address n (Encoded-Source format) | 5010 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5011 | Pruned Source Address 1 (Encoded-Source format) | 5012 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5013 | . | 5014 | . | 5015 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5016 | Pruned Source Address n (Encoded-Source format) | 5017 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5018 | . | 5019 | . | 5020 | . | 5021 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5022 | Multicast Group Address m (Encoded-Group format) | 5023 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5024 | Number of Joined Sources | Number of Pruned Sources | 5025 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5026 | Joined Source Address 1 (Encoded-Source format) | 5027 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5028 | . | 5029 | . | 5030 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5031 | Joined Source Address n (Encoded-Source format) | 5032 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5033 | Pruned Source Address 1 (Encoded-Source format) | 5034 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5035 | . | 5036 | . | 5037 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5038 | Pruned Source Address n (Encoded-Source format) | 5039 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5041 PIM Version, Type, Reserved, Checksum 5042 Described above. 5044 Unicast Upstream Neighbor Address 5045 The address of the RPF or upstream neighbor. The format for this 5046 address is given in the Encoded-Unicast address in section 4.10.1. 5047 This address should be the link-local address of the upstream 5048 neighbor, as obtained from the RPF lookup. 5050 Reserved 5051 Transmitted as zero, ignored on receipt. 5053 Holdtime 5054 The amount of time a receiver must keep the Join/Prune state alive, 5055 in seconds. If the Holdtime is set to `0xffff', the receiver of 5056 this message should hold the state until canceled by the 5057 appropriate canceling Join/Prune message, or timed out according to 5058 local policy. This may be used with dial-on-demand links, to avoid 5059 keeping the link up with periodic Join/Prune messages. 5061 Note that the HoldTime must be larger than the 5062 J/P_Override_Interval(I). 5064 Number of Groups 5065 The number of multicast group sets contained in the message. 5067 Multicast group address 5068 For format description see Section 4.10.1. 5070 Number of Joined Sources 5071 Number of join source addresses listed for a given group. 5073 Join Source Address 1 .. n 5074 This list contains the sources that the sending router will forward 5075 multicast datagrams for if received on the interface this message 5076 is sent on. 5078 See Encoded-Source-Address format in section 4.10.1. 5080 Number of Pruned Sources 5081 Number of prune source addresses listed for a group. 5083 Prune Source Address 1 .. n 5084 This list contains the sources that the sending router does not 5085 want to forward multicast datagrams for when received on the 5086 interface this message is sent on. 5088 Within one PIM Join/Prune message, all the Multicast Group Addresses, 5089 Joined Source addresses and Pruned Source addresses MUST be of the same 5090 address family. It is NOT PERMITTED to mix IPv4 and IPv6 addresses 5091 within the same message. In addition, the address family of the fields 5092 in the message SHOULD be the same as the IP source and destination 5093 addresses of the packet. This permits maximum implementation 5094 flexibility for dual-stack IPv4/IPv6 routers. 5096 4.10.5.1. Group Set Source List Rules 5098 As described above, Join / Prune messages are composed of one or more 5099 group sets. Each set contains two source lists, the Join Sources and the 5100 Prune Sources. This section describes the different types of group sets 5101 and source list entries that can exist in a Join / Prune message. 5103 There are two valid group set types: 5105 Wildcard Group Set 5106 The wildcard group set is represented by the entire multicast range 5107 - the beginning of the multicast address range in the group address 5108 field and the prefix length of the multicast address range in the 5109 mask length field of the Multicast Group Address, e.g. 224.0.0.0/4 5110 for IPv4 or ff00::/8 for IPv6. Each wildcard group set may contain 5111 one or more (*,*,RP) source list entries in either the Join or 5112 Prune lists. 5114 A (*,*,RP) source list entry may only exist in a wildcard group 5115 set. When added to a Join source list, this type of source entry 5116 expresses the routers interest in receiving traffic for all groups 5117 mapping to the specified RP. When added to a Prune source list a 5118 (*,*,RP) entry expresses the routers interest to stop receiving 5119 such traffic. Note that as indicated by the Join/Prune state 5120 machines, such a Join or Prune will NOT override Join/Prune state 5121 created using a Group-Specific Set (see below). 5123 (*,*,RP) source list entries have the Source-Address set to the 5124 address of the RP, the Source-Address Mask-Len set to the full 5125 length of the IP address and both the WC and RPT bits of the 5126 Source-Address set to 1. 5128 Group Specific Set 5129 A Group Specific Set is represented by a valid IP multicast address 5130 in the group address field and the full length of the IP address in 5131 the mask length field of the Multicast Group Address. Each group 5132 specific set may contain (*,G), (S,G,rpt) and (S,G) source list 5133 entries in the Join or Prune lists. 5135 (*,G) 5136 The (*,G) source list entry is used in Join / Prune messages 5137 sent towards the RP for the specified group. It expresses 5138 interest (or lack of) in receiving traffic sent to the group 5139 through the Rendezvous-Point shared tree. There may only be 5140 one such entry in both the Join and Prune lists of a group 5141 specific set. 5143 (*,G) source list entries have the Source-Address set to the 5144 address of the RP for group G, the Source-Address Mask-Len set 5145 to the full length of the IP address and have both the WC and 5146 RPT bits of the Encoded-Source-Address set. 5148 (S,G,rpt) 5149 The (S,G,rpt) source list entry is used in Join / Prune 5150 messages sent towards the RP for the specified group. It 5151 expresses interest (or lack of) in receiving traffic through 5152 the shared tree sent by the specified source to this group. 5153 For each source address the entry may exist in only one of the 5154 Join and Prune source lists of a group specific set but not 5155 both. 5157 (S,G,rpt) source list entries have the Source-Address set to 5158 the address of the source S, the Source-Address Mask-Len set 5159 to the full length of the IP address and have the WC bit clear 5160 and the RPT bit set in the Encoded-Source-Address. 5162 (S,G) 5163 The (S,G) source list entry is used in Join / Prune messages 5164 sent towards the specified source. It expresses interest (or 5165 lack of) in receiving traffic through the shortest path tree 5166 sent by the source to the specified group. For each source 5167 address the entry may exist in only one of the Join and Prune 5168 source lists of a group specific set but not both. 5170 (S,G) source list entries have the Source-Address set to the 5171 address of the source S, the Source-Address Mask-Len set to 5172 the full length of the IP address and have both the WC and RPT 5173 bits of the Encoded-Source-Address cleared. 5175 The rules described above are sufficient to prevent invalid combinations 5176 of source list entries in group-specific sets. There are however a 5177 number of combinations that have a valid interpretation but which are 5178 not generated by the protocol as described in this specification: 5180 o Combining a (*,G) Join and a (S,G,rpt) Join entry in the same message 5181 is redundant as the (*,G) entry covers the information provided by the 5182 (S,G,rpt) entry. 5184 o The same applies for a (*,G) Prunes and (S,G,rpt) Prunes. 5186 o The combination of a (*,G) Prune and a (S,G,rpt) Join is also not 5187 generated. (S,G,rpt) Joins are only sent when the router is receiving 5188 all traffic for a group on the shared tree and it wishes to indicate a 5189 change for the particular source. As a (*,G) prune indicates that the 5190 router no longer wishes to receive shared tree traffic, the (S,G,rpt) 5191 Join would be meaningless. 5193 o As Join / Prune messages are targeted to a single PIM neighbor, 5194 including both a (S,G) Join and a (S,G,rpt) prune in the same message 5195 is redundant. The (S,G) Join informs the neighbor that the sender 5196 wishes to receive the particular source on the shortest path tree. It 5197 is therefore unnecessary for the router to say that it no longer 5198 wishes to receive it on the shared tree. 5200 o The combination of a (S,G) Prune and a (S,G,rpt) Join could possibly 5201 be used by a router to switch from receiving a particular source on 5202 the shortest-path tree back to receiving it on the shared tree 5203 (provided that the RPF neighbor for the shortest-path and shared trees 5204 is common). However Sparse-Mode PIM does not provide a mechanism for 5205 switching back to the shared tree. 5207 The rules are summarized in the tables below. 5209 +----------++------+-------+-----------+-----------+-------+-------+ 5210 | ||Join | Prune | Join | Prune | Join | Prune | 5211 | ||(*,G) | (*,G) | (S,G,rpt) | (S,G,rpt) | (S,G) | (S,G) | 5212 +----------++------+-------+-----------+-----------+-------+-------+ 5213 |Join ||- | no | ? | yes | yes | yes | 5214 |(*,G) || | | | | | | 5215 +----------++------+-------+-----------+-----------+-------+-------+ 5216 |Prune ||no | - | ? | ? | yes | yes | 5217 |(*,G) || | | | | | | 5218 +----------++------+-------+-----------+-----------+-------+-------+ 5219 |Join ||? | ? | - | no | yes | yes | 5220 |(S,G,rpt) || | | | | | | 5221 +----------++------+-------+-----------+-----------+-------+-------+ 5222 |Prune ||yes | ? | no | - | ? | ? | 5223 |(S,G,rpt) || | | | | | | 5224 +----------++------+-------+-----------+-----------+-------+-------+ 5225 |Join ||yes | yes | yes | ? | - | no | 5226 |(S,G) || | | | | | | 5227 +----------++------+-------+-----------+-----------+-------+-------+ 5228 |Prune ||yes | yes | yes | ? | no | - | 5229 |(S,G) || | | | | | | 5230 +----------++------+-------+-----------+-----------+-------+-------+ 5232 +---------------++--------------+----------------+------------+ 5233 | ||Join (*,*,RP) | Prune (*,*,RP) | all others | 5234 +---------------++--------------+----------------+------------+ 5235 |Join (*,*,RP) ||- | no | yes | 5236 +---------------++--------------+----------------+------------+ 5237 |Prune (*,*,RP) ||no | - | yes | 5238 +---------------++--------------+----------------+------------+ 5239 |all others ||yes | yes | see above | 5240 +---------------++--------------+----------------+------------+ 5242 yes Allowed and expected. 5244 no Combination is not allowed by the protocol and MUST NOT be 5245 generated by a router. 5247 ? Combination not expected by the protocol, but well-defined. A 5248 router MAY accept it but SHOULD NOT generate it. 5250 The order of source list entries in a group set source list is not 5251 important, except where limited by the packet format itself. 5253 4.10.5.2. Group Set Fragmentation 5255 When building a Join / Prune for a particular neighbor, a router should 5256 try and include in the message as much of the information it needs to 5257 convey to the neighbor as possible. This implies adding one group set 5258 for each multicast group that has information pending transmission and 5259 within each set including all relevant source list entries. 5261 On a router with a large amount of multicast state the number of entries 5262 that must be included may result in packets that are larger in the 5263 maximum IP packet size. In most such cases the information may be split 5264 into multiple messages. 5266 There is an exception with group sets that contain a (*,G) Join source 5267 list entry. The group set expresses the routers interest in receiving 5268 all traffic for the specified group on the shared tree and it MUST 5269 include an (S,G,rpt) Prune source list entry for every source that the 5270 router does not wish to receive. This list of (S,G,rpt) Prune source- 5271 list entries MUST not be split in multiple messages. 5273 If only N (S,G,rpt) Prune entries fit into a maximum-sized Join / Prune 5274 message, but the router has more than N (S,G,rpt) Prunes to add, then 5275 the router MUST choose to include the first N (numerically smallest in 5276 network byte order) IP addresses. 5278 4.10.6. Assert Message Format 5280 The Assert message is used to resolve forwarder conflicts between 5281 routers on a link. It is sent when a multicast data packet is received 5282 on an interface that the router would normally forward that packet. 5283 Assert messages may also be sent in response to an Assert message from 5284 another router. 5286 0 1 2 3 5287 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 5288 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5289 |PIM Ver| Type | Reserved | Checksum | 5290 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5291 | Group Address (Encoded-Group format) | 5292 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5293 | Source Address (Encoded-Unicast format) | 5294 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5295 |R| Metric Preference | 5296 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5297 | Metric | 5298 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5300 PIM Version, Type, Reserved, Checksum 5301 Described above. 5303 Group Address 5304 The group address for which the router wishes to resolve the 5305 forwarding conflict. This is an Encoded-Group address, as 5306 specified in 4.10.1. 5308 Source Address 5309 Source address for which the router wishes to resolve the 5310 forwarding conflict. The source address MAY be set to INADDR_ANY 5311 for (*,G) asserts (see below). The format for this address is 5312 given in Encoded-Unicast-Address in section 4.10.1. 5314 R RPT-bit is a 1 bit value. The RPT-bit is set to 1 for Assert(*,G) 5315 messages and 0 for Assert(S,G) messages. 5317 Metric Preference 5318 Preference value assigned to the unicast routing protocol that 5319 provided the route to the multicast source or Rendezvous-Point. 5321 Metric 5322 The unicast routing table metric associated with the route used to 5323 reach the multicast source or Rendezvous-Point. The metric is in 5324 units applicable to the unicast routing protocol used. 5326 Assert messages can be sent to resolve a forwarding conflict for all 5327 traffic to given group or for a specific source and group. 5329 Assert(S,G) 5330 Source specific asserts are sent by routers forwarding a specific 5331 source on the shortest-path tree (SPT bit is TRUE). (S,G) Asserts 5332 have the Group-Address field set to the group G and the Source- 5333 Address field set to the source S. The RPT-bit is set to 0, the 5334 Metric-Preference is set to MRIB.pref(S) and the Metric is set to 5335 MRIB.metric(S). 5337 Assert(*,G) 5338 Group specific asserts are sent by routers forwarding data for the 5339 group and source(s) under contention on the shared tree. (*,G) 5340 asserts have the Group-Address field set to the group G. For data 5341 triggered Asserts the Source-Address field MAY be set to the IP 5342 source address of the data packet that triggered the Assert and is 5343 set to INADDR_ANY otherwise. The RPT-bit is set to 1, the Metric- 5344 Preference is set to MRIB.pref(RP(G)) and the Metric is set to 5345 MRIB.metric(RP(G)). 5347 4.11. PIM Timers 5349 PIM-SM maintains the following timers, as discussed in section 4.1. All 5350 timers are countdown timers - they are set to a value and count down to 5351 zero, at which point they typically trigger an action. Of course they 5352 can just as easily be implemented as count-up timers, where the absolute 5353 expiry time is stored and compared against a real-time clock, but the 5354 language in this specification assumes that they count downwards to 5355 zero. 5357 Global Timers 5359 Per interface (I): 5361 Hello Timer: HT(I) 5363 Per neighbor (N): 5365 Neighbor liveness Timer: NLT(N,I) 5367 Per active RP (RP): 5369 (*,*,RP) Join Expiry Timer: ET(*,*,RP,I) 5371 (*,*,RP) PrunePending Timer: PPT(*,*,RP,I) 5373 Per Group (G): 5375 (*,G) Join Expiry Timer: ET(*,G,I) 5377 (*,G) PrunePending Timer: PPT(*,G,I) 5379 (*,G) Assert Timer: AT(*,G,I) 5381 Per Source (S): 5383 (S,G) Join Expiry Timer: ET(S,G,I) 5385 (S,G) PrunePending Timer: PPT(S,G,I) 5387 (S,G) Assert Timer: AT(S,G,I) 5389 (S,G,rpt) Prune Expiry Timer: ET(S,G,rpt,I) 5391 (S,G,rpt) PrunePending Timer: PPT(S,G,rpt,I) 5393 Per active RP (RP): 5395 (*,*,RP) Upstream Join Timer: JT(*,*,RP) 5397 Per Group (G): 5399 (*,G) Upstream Join Timer: JT(*,G) 5401 Per Source (S): 5403 (S,G) Upstream Join Timer: JT(S,G) 5405 (S,G) Keepalive Timer: KAT(S,G) 5407 (S,G,rpt) Upstream Override Timer: OT(S,G,rpt) 5409 At the DRs or relevant Assert Winners only: 5411 Per Source,Group pair (S,G): 5413 Register Stop Timer: RST(S,G) 5415 4.12. Timer Values 5417 When timers are started or restarted, they are set to default values. 5418 This section summarizes those default values. 5420 Note that protocol events or configuration may change the default value 5421 of a timer on a specific interface. When timers are initialized in this 5422 document the value specific to the interface in context must be used. 5424 Some of the timers listed below (Prune Pending, Upstream Join, Upstream 5425 Override) can be set to values which depend on the settings of the 5426 Propagation Delay and Override_Interval of the corresponding interface. 5427 The default values for these are given below. Note that the value of 5428 both the Propagation Delay and Override Interval of an interface can 5429 change as a result of receiving Hello messages on that interface 5430 (section 4.3.3). 5432 Variable Name: Propagation_Delay(I) 5434 +--------------------------+-----------------+--------------------------+ 5435 | Value Name | Value | Explanation | 5436 +--------------------------+-----------------+--------------------------+ 5437 | LAN_delay_default | 0.5 sec | Expected | 5438 | | | propagation delay | 5439 | | | over the local | 5440 | | | link. | 5441 +--------------------------+-----------------+--------------------------+ 5443 The default value of the LAN_delay_default is chosen to be relatively 5444 large to provide compatibility with older PIM implementations. 5446 Variable Name: Override_Interval(I) 5448 +--------------------------+-----------------+--------------------------+ 5449 | Value Name | Value | Explanation | 5450 +--------------------------+-----------------+--------------------------+ 5451 | t_override_default | 2.5 sec | Default delay | 5452 | | | interval over | 5453 | | | which to randomize | 5454 | | | when scheduling a | 5455 | | | delayed Join | 5456 | | | message. | 5457 +--------------------------+-----------------+--------------------------+ 5458 Timer Name: Hello Timer (HT(I)) 5460 +----------------------+--------+---------------------------------------+ 5461 |Value Name | Value | Explanation | 5462 +----------------------+--------+---------------------------------------+ 5463 |Hello_Period | 30 sec | Periodic interval for Hello messages. | 5464 +----------------------+--------+---------------------------------------+ 5465 |Triggered_Hello_Delay | 5 sec | Randomized interval for initial Hello | 5466 | | | message on bootup or triggered Hello | 5467 | | | message to a rebooting neighbor. | 5468 +----------------------+--------+---------------------------------------+ 5470 At system power-up, the timer is initialized to 5471 rand(0,Triggered_Hello_Delay) to prevent synchronization. When a new or 5472 rebooting neighbor is detected, a responding Hello is sent within 5473 rand(0,Triggered_Hello_Delay). 5475 Timer Name: Neighbor Liveness Timer (NLT(N,I)) 5477 +--------------------------+-----------------------+--------------------+ 5478 | Value Name | Value | Explanation | 5479 +--------------------------+-----------------------+--------------------+ 5480 | Default_Hello_Holdtime | 3.5 * Hello_Period | Default holdtime | 5481 | | | to keep neighbor | 5482 | | | state alive | 5483 +--------------------------+-----------------------+--------------------+ 5484 | Hello_Holdtime | from message | Holdtime from | 5485 | | | Hello Message | 5486 | | | Holdtime option. | 5487 +--------------------------+-----------------------+--------------------+ 5489 The Holdtime in a Hello Message should be set to (3.5 * Hello_Period), 5490 giving a default value of 105 seconds. 5492 Timer Names: Expiry Timer (ET(*,*,RP,I), ET(*,G,I), ET(S,G,I), 5493 ET(S,G,rpt,I)) 5495 +----------------+-----------------+------------------------------------+ 5496 | Value Name | Value | Explanation | 5497 +----------------+-----------------+------------------------------------+ 5498 | J/P_HoldTime | from message | Holdtime from Join/Prune Message | 5499 +----------------+-----------------+------------------------------------+ 5501 See details of JT(*,G) for the Holdtime that is included in Join/Prune 5502 Messages. 5504 Timer Names: Prune Pending Timer (PPT(*,*,RP,I), PPT(*,G,I), PPT(S,G,I), 5505 PPT(S,G,rpt,I)) 5507 +--------------------------+-----------------------+--------------------+ 5508 |Value Name | Value | Explanation | 5509 +--------------------------+-----------------------+--------------------+ 5510 |J/P_Override_Interval(I) | Default: | Short period after | 5511 | | Propagation_Delay(I) | a join or prune to | 5512 | | + | allow other | 5513 | | Override_Interval(I) | routers on the LAN | 5514 | | | to override the | 5515 | | | join or prune | 5516 +--------------------------+-----------------------+--------------------+ 5518 Note that both the Propagation_Delay(I) and the Override_Interval(I) are 5519 interface specific values that may change when Hello messages are 5520 received. 5522 Timer Names: Assert Timer (AT(*,G,I), AT(S,G,I)) 5524 +---------------------------+----------------------+--------------------+ 5525 | Value Name | Value | Explanation | 5526 +---------------------------+----------------------+--------------------+ 5527 | Assert_Override_Interval | Default: 3 secs | Short interval | 5528 | | | before an assert | 5529 | | | times out where | 5530 | | | the assert winner | 5531 | | | resends an Assert | 5532 | | | message | 5533 +---------------------------+----------------------+--------------------+ 5534 | Assert_Time | Default: 180 secs | Period after last | 5535 | | | assert before | 5536 | | | assert state is | 5537 | | | timed out | 5538 +---------------------------+----------------------+--------------------+ 5540 Note that for historical reasons, the Assert message lacks a Holdtime 5541 field. Thus changing the Assert Time from the default value is not 5542 recommended. 5544 Timer Names: Upstream Join Timer (JT(*,*,RP), JT(*,G), JT(S,G)) 5546 +-------------+------------------------+-------------------------------------+ 5547 |Value Name | Value | Explanation | 5548 +-------------+------------------------+-------------------------------------+ 5549 |t_periodic | Default: 60 secs | Period between Join/Prune Messages | 5550 +-------------+------------------------+-------------------------------------+ 5551 |t_suppressed | rand(1.1 * | Suppression period when someone | 5552 | | t_periodic, 1.4 * | else sends a J/P message so we | 5553 | | t_periodic) when | don't need to do so. | 5554 | | Suppression_Enabled(I) | | 5555 | | is true, 0 | | 5556 | | otherwise | | 5557 +-------------+------------------------+-------------------------------------+ 5558 |t_override | rand(0, | Randomized delay to prevent | 5559 | | Override_Interval(I)) | response implosion when sending a | 5560 | | | join message to override someone | 5561 | | | else's Prune message. | 5562 +-------------+------------------------+-------------------------------------+ 5564 t_periodic may be set to take into account such things as the configured 5565 bandwidth and expected average number of multicast route entries for the 5566 attached network or link (e.g., the period would be longer for lower- 5567 speed links, or for routers in the center of the network that expect to 5568 have a larger number of entries). If the Join/Prune-Period is modified 5569 during operation, these changes should be made relatively infrequently 5570 and the router should continue to refresh at its previous Join/Prune- 5571 Period for at least Join/Prune-Holdtime, in order to allow the upstream 5572 router to adapt. 5574 The holdtime specified in a Join/Prune message should be set to (3.5 * 5575 t_periodic). 5577 t_override depends on the Override Interval of the upstream interface 5578 which may change when Hello messages are received. 5580 t_suppressed depends on the Suppression State of the upstream interface 5581 ( 4.3.3) and becomes zero when suppression is disabled. 5583 Timer Name: Upstream Override Timer (OT(S,G,rpt)) 5585 +---------------+---------------------------+---------------------------+ 5586 | Value Name | Value | Explanation | 5587 +---------------+---------------------------+---------------------------+ 5588 | t_override | see Upstream Join Timer | see Upstream Join Timer | 5589 +---------------+---------------------------+---------------------------+ 5591 The upstream Override Timer is only ever set to t_override; this value 5592 is defined in the section on Upstream Join Timers. 5594 Timer Name: KeepAlive Timer (KAT(S,G)) 5596 +-----------------------+------------------------+----------------------+ 5597 | Value Name | Value | Explanation | 5598 +-----------------------+------------------------+----------------------+ 5599 | Keepalive_Period | Default: 210 secs | Period after last | 5600 | | | (S,G) data packet | 5601 | | | during which (S,G) | 5602 | | | Join state will be | 5603 | | | maintained even in | 5604 | | | the absence of | 5605 | | | (S,G) Join | 5606 | | | messages. | 5607 +-----------------------+------------------------+----------------------+ 5608 | RP_Keepalive_Period | ( 3 * Register_ | As | 5609 | | Suppression_Time ) | Keepalive_Period, | 5610 | | + Register_ | but at the RP when | 5611 | | Probe_Time | a RegisterStop is | 5612 | | | sent. | 5613 +-----------------------+------------------------+----------------------+ 5614 The normal keepalive period for the KAT(S,G) defaults to 210 seconds. 5615 However at the RP, the keepalive period must be at least the 5616 Register_Suppression_Time or the RP may time out the (S,G) state before 5617 the next Null-Register arrives. Thus the KAT(S,G) is set to 5618 max(Keepalive_Period, RP_Keepalive_Period). 5620 Timer Name: Register Stop Timer (RST(S,G)) 5622 +---------------------------+----------------------+--------------------+ 5623 |Value Name |Value | Explanation | 5624 +---------------------------+----------------------+--------------------+ 5625 |Register_Suppression_Time |Default: 60 seconds | Period during | 5626 | | | which a DR stops | 5627 | | | sending Register- | 5628 | | | encapsulated data | 5629 | | | to the RP after | 5630 | | | receiving a | 5631 | | | RegisterStop | 5632 +---------------------------+----------------------+--------------------+ 5633 |Register_Probe_Time |Default: 5 seconds | Time before RST | 5634 | | | expires when a DR | 5635 | | | may send a Null- | 5636 | | | Register to the RP | 5637 | | | to cause it to | 5638 | | | resend a | 5639 | | | RegisterStop | 5640 | | | message. | 5641 +---------------------------+----------------------+--------------------+ 5643 5. IANA Considerations 5645 5.1. PIM Address Family 5647 The PIM Address Family field was chosen to be 8 bits as a tradeoff 5648 between 5649 packet format and use of the IANA assigned numbers. Since when the PIM 5650 packet format was designed only 15 values were assigned for Address 5651 Families, and large numbers of new Address Family values were not 5652 envisioned, 8 bits seemed large enough. However, the IANA assigns 5653 Address Families in a 16-bit field. Therefore, the PIM Address Family 5654 is allocated as follows: 5656 Values 0 through 127 are designated to have the same meaning as 5657 IANA-assigned Address Family Numbers [8]. 5659 Values 128 through 250 are designated to be assigned by the IANA 5660 based upon IESG Approval, as defined in [12]. 5662 Values 251 through 255 are designated for Private Use, as defined 5663 in [12]. 5665 5.2. PIM Hello Options 5667 Values 17 through 65000 are to be assigned by the IANA. Since the space 5668 is large, they may be assigned as First Come First Served as defined in 5669 [12]. Such assignments are valid for one year, and may be renewed. 5670 Permanent assignments require a specification (see "Specification 5671 Required" in [12].) 5673 6. Security Considerations 5675 The IPsec authentication header [11] MAY be used to provide data 5676 integrity protection and groupwise data origin authentication of PIM 5677 protocol messages. Authentication of PIM messages can protect against 5678 unwanted behaviors caused by unauthorized or altered PIM messages. 5680 6.1. Attacks based on forged messages 5682 The extent of possible damage depends on the type of counterfeit 5683 messages accepted. We next consider the impact of possible forgeries, 5684 including forged link-local (Join/Prune, Hello, and Assert) and forged 5685 unicast (Register and RegisterStop) messages. 5687 6.1.1. Forged link-local messages 5689 Join/Prune, Hello, and Assert messages are all sent to the link-local 5690 ALL_PIM_ROUTERS multicast addresses, and thus are not forwarded by a 5691 compliant router. A forged message of this type can only reach a LAN if 5692 it was sent by a local host or if it was allowed onto the LAN by a 5693 compromised or non-compliant router. 5695 1. A forged Join/Prune message can cause multicast traffic to be 5696 delivered to links where there are no legitimate requesters, 5697 potentially wasting bandwidth on that link. A forged leave message 5698 on a multi-access LAN is generally not a significant attack in PIM, 5699 because any legitimately joined router on the LAN would override 5700 the leave with a join before the upstream router stops forwarding 5701 data to the LAN. 5703 2. By forging a Hello message, an unauthorized router can cause 5704 itself to be elected as the designated router on a LAN. The 5705 designated router on a LAN is (in the absence of asserts) 5706 responsible for forwarding traffic to that LAN on behalf of any 5707 local members. The designated router is also responsible for 5708 register-encapsulating to the RP any packets that are originated by 5709 hosts on the LAN. Thus, the ability of local hosts to send and 5710 receive multicast traffic may be compromised by a forged Hello 5711 message. 5713 3. By forging an Assert message on a multi-access LAN, an attacker 5714 could cause the legitimate designated forwarder to stop forwarding 5715 traffic to the LAN. Such a forgery would prevent any hosts 5716 downstream of that LAN from receiving traffic. 5718 6.1.2. Forged unicast messages 5720 Register messages and RegisterStop messages are sent by a source and 5721 forwarded by intermediate routers to their destination using normal IP 5722 forwarding. Therefore, without data origin authentication, an attacker 5723 who is located anywhere in the network may be able to forge a Register 5724 or RegisterStop message. The following attacks do not apply to a PIM- 5725 SSM-only implementation, as these messages are not required for PIM-SSM. 5726 We consider the effect of a forgery of each of these messages next. 5728 1 By forging a Register message, an attacker can cause the RP to 5729 inject forged traffic onto the shared multicast tree. 5731 2 By forging a Register-stop message, an attacker can prevent a 5732 legitimate DR from Registering packets to the RP. This can prevent 5733 local hosts on that LAN from sending multicast packets. 5735 The above two PIM messages are not changed by intermediate routers and 5736 need only be examined by the intended receiver. Thus these messages can 5737 be authenticated end-to-end, using AH. 5739 6.2. Non-cryptographic Authentication Mechanisms 5741 A PIM router SHOULD provide an option to limit the set of neighbors from 5742 which it will accept Join/Prune, Assert, and Hello messages. Either 5743 static configuration of IP addresses or an IPsec security association 5744 may be used. Furthermore, a PIM router SHOULD NOT accept protocol 5745 messages from a router from which it has not yet received a valid Hello 5746 message. 5748 A Designated Router MUST NOT register-encapsulate a packet and send it 5749 to the RP unless the source address of the packet is a legal address for 5750 the subnet on which the packet was received. Similarly, a Designated 5751 Router SHOULD NOT accept a RegisterStop packet whose IP source address 5752 is not a valid RP address for the local domain. 5754 An implementation SHOULD provide a mechanism to allow a DR to restrict 5755 the range of source addresses from which it accepts Register- 5756 encapsulated packets. 5758 All options that restrict the range of addresses from which packets are 5759 accepted MUST default to allowing all packets. 5761 6.3. Authentication using IPsec 5763 The IPsec [11] transport mode using the Authentication Header (AH) is 5764 the recommended method to prevent the above attacks PIM. The anti- 5765 replay option provided by IPsec SHOULD also be enabled. The specific AH 5766 authentication algorithm and parameters, including the choice of 5767 authentication algorithm and the choice of key, are configured by the 5768 network administrator. The Encapsulating Security Payload (ESP) MAY 5769 also be used to provide both encryption and authentication of PIM 5770 protocol messages. When IPsec authentication is used, a PIM router 5771 should reject (drop without processing) any unauthorized PIM protocol 5772 messages. 5774 To use IPsec, the administrator of a PIM network configures each PIM 5775 router with one or more Security Associations and associated SPI(s) that 5776 are used by senders to sign PIM protocol messages and are used by 5777 receivers to authenticate received PIM protocol messages. This document 5778 does not describe protocols for establishing Security Associations. It 5779 assumes that manual configuration of Security Associations is performed, 5780 but it does not preclude the use of some future negotiation protocol to 5781 establish Security Associations. 5783 The following sections describe the Security Associations required to 5784 protect PIM protocol messages. 5786 6.3.1. Protecting link-local multicast messages 5788 The network administrator defines a Security Association (SA) and 5789 Security Parameters Index (SPI) that is to be used to authenticate all 5790 link-local PIM protocol messages (Hello, Join/Prune, and Assert) on each 5791 link in a PIM domain. All link-local PIM protocol messages use SPI 0. 5793 The Security Policy Database at a PIM router should be configured to 5794 ensure that all incoming and outgoing Join/Prune, Assert, and Hello 5795 packets use the SA associated with the interface to which the packet is 5796 sent. 5798 Note that, according to [11] there is nominally a different Security 5799 Association Database (SAD) for each router interface. Thus, the 5800 selected Security Association for an inbound PIM packet can vary 5801 depending on the interface on which the packet arrived. This fact 5802 allows the network administrator to use different authentication methods 5803 for each link, even though the destination address is the same for all 5804 link-local PIM packets, regardless of interface. 5806 6.3.2. Protecting unicast messages 5808 IPSec can also be used to provide data origin authentication and data 5809 integrity protection for the Register and RegisterStop unicast messages. 5811 6.3.2.1. Register messages 5813 The Security Policy Database at every PIM router is configured to select 5814 a Security Association to use when sending PIM Register packets to each 5815 rendezvous point. 5817 In the most general mode of operation, the Security Policy Database at 5818 each DR is configured to select a unique SA and SPI for traffic sent to 5819 each RP. This allows each DR to have a different authentication 5820 algorithm and key to talk to the RP. However, this creates a daunting 5821 key management and distribution problem for the network administrator. 5822 Therefore, it may be preferable in PIM domains where all Designated 5823 Routers are under a single administrative control, to use the same 5824 authentication algorithm parameters (including the key) for all 5825 Registered packets in a domain, regardless of who is the RP and 5826 regardless of who is the DR. 5828 In this "single shared key" mode of operation, the network administrator 5829 must choose an SPI for each DR that will be used to send it PIM protocol 5830 packets. The Security Policy Database at every DR is configured to 5831 select a Security Association (including the authentication algorithm, 5832 authentication parameters, and this SPI) when sending Register messages 5833 to this RP. 5835 By using a single authentication algorithm and associated parameters, 5836 the key distribution problem is simplified. Note however, that this 5837 method has the property that, in order to change the authentication 5838 method or authentication key used, all routers in the domain must be 5839 updated. 5841 6.3.2.2. Register Stop messages 5843 Similarly, the Security Policy Database at each Rendezvous Point should 5844 be configured to choose a Security Association to use when sending 5845 Register Stop messages. Because Register Stop messages are unicast to 5846 the destination DR, a different Security Association and a potentially 5847 unique SPI is required for each DR. 5849 [XXX Can we reserve a single SPI at all routers in the domain to 5850 simplify the configuration problem?] 5852 In order to simplify the management problem, it may be acceptable to use 5853 the same authentication algorithm and authentication parameters, 5854 regardless of the sending RP and regardless of the destination DR. 5855 Although a unique Security Association is needed for each DR, the same 5856 authentication algorithm and authentication algorithm parameters (secret 5857 key) can be shared by all DRs and by all RPs. 5859 6.4. Denial of Service Attacks 5861 There are a number of possible denial of service attacks against PIM 5862 that can be caused by generating false PIM protocol messages or even by 5863 generating data false traffic. Authenticating PIM protocol traffic 5864 prevents some, but not all of these attacks. The possible attacks 5865 include: 5867 - Sending packets to many different group addresses quickly can be a 5868 denial of service attack in and of itself. This will cause many 5869 register-encapsulated packets, loading the DR, the RP, and the 5870 routers between the DR and the RP. 5872 - Forging Join messages can cause a multicast tree to get set up. A 5873 large number of forged joins can consume router resources and 5874 result in denial of service. 5876 - [XXX Many others] 5878 7. Authors' Addresses 5880 Bill Fenner 5881 AT&T Labs - Research 5882 75 Willow Road 5883 Menlo Park, CA 94025 5884 fenner@research.att.com 5886 Mark Handley 5887 ICIR/ICSI 5888 1947 Center St, Suite 600 5889 Berkeley, CA 94708 5890 mjh@icir.org 5892 Hugh Holbrook 5893 Cisco Systems 5894 170 W. Tasman Drive 5895 San Jose, CA 95134 5896 holbrook@cisco.com 5897 Isidor Kouvelas 5898 Cisco Systems 5899 170 W. Tasman Drive 5900 San Jose, CA 95134 5901 kouvelas@cisco.com 5903 8. Acknowledgments 5905 PIM-SM was designed over many years by a large group of people, 5906 including ideas, comments, and corrections from Deborah Estrin, Dino 5907 Farinacci, Ahmed Helmy, David Thaler, Steve Deering, Van Jacobson, C. 5908 Liu, Puneet Sharma, Liming Wei, Tom Pusateri, Tony Ballardie, Scott 5909 Brim, Jon Crowcroft, Paul Francis, Joel Halpern, Horst Hodel, Polly 5910 Huang, Stephen Ostrowski, Lixia Zhang, Girish Chandranmenon, Brian 5911 Haberman, Hal Sandick, Mike Mroz and Garry Kump. 5913 Thanks are due to the American Licorice Company, for its obscure but 5914 possibly essential role in the creation of this document. 5916 9. References 5918 [1] T. Bates , R. Chandra , D. Katz , Y. Rekhter, "Multiprotocol 5919 Extensions for BGP-4", RFC 2283 5921 [2] D. Black, "Differentiated Services and Tunnels", RFC 2983. 5923 [3] S.E. Deering, "Host extensions for IP multicasting", RFC 1112, Aug 5924 1989. 5926 [4] S. Deering, W. Fenner, B. Haberman, "Multicast Listener Discovery 5927 (MLD) for IPv6", RFC 2710. 5929 [5] S. Deering, R. Hinden, "Internet Protocol, Version 6 (IPv6) 5930 Specification", RFC 2460. 5932 [6] W. Fenner, "Internet Group Management Protocol, Version 2", RFC 5933 2236. 5935 [7] W. Fenner, M. Handley, H. Holbrook, I. Kouvelas, "Bootstrap Router 5936 (BSR) Mechanism for PIM Sparse Mode", draft-ietf-pim-sm-bsr-02.txt, 5937 work in progress. 5939 [8] IANA, "Address Family Numbers", linked from 5940 http://www.iana.org/numbers.html 5942 [9] M. Handley, I. Kouvelas, T. Speakman, L. Vicisano, "Bi-directional 5943 Protocol Independent Multicast", draft-ietf-pim-bidir-02.txt, work 5944 in progress. 5946 [10] H. Holbrook, B. Cain, "Source-Specific Multicast for IP", draft- 5947 holbrook-ssm-00.txt, work in progress. 5949 [11] S. Kent, R. Atkinson, "Security Architecture for the Internet 5950 Protocol.", RFC 2401. 5952 [12] T. Narten , H. Alvestrand, "Guidelines for Writing an IANA 5953 Considerations Section in RFCs", RFC 2434. [13] D. Thaler, 5954 "Interoperability Rules for Multicast Routing Protocols", RFC 2715. 5956 10. Index 5957 Assert(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .26,121 5958 Assert(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .26,121 5959 AssertCancel(*,G). . . . . . . . . . . . . . . . . . . . . . . . . 90,92 5960 AssertCancel(S,G). . . . . . . . . . . . . . . . . . . . . . . .75,84,92 5961 AssertTimer(*,G,I) . . . . . . . . . . . . . . . . . . . . .16,24,84,125 5962 AssertTimer(S,G,I) . . . . . . . . . . . . . . . . . . . . .18,24,77,125 5963 AssertTrackingDesired(*,G,I) . . . . . . . . . . . . . . . . . .87,88,90 5964 AssertTrackingDesired(S,G,I) . . . . . . . . . . . . . . . . 79,79,81,83 5965 AssertWinner(*,G,I). . . . . . . . . . . . . . . . . . . .21,24,87,90,94 5966 AssertWinner(S,G,I). . . . . . . . . . . . . . . . . . 21,24,79,83,93,94 5967 AssertWinnerMetric(*,G,I). . . . . . . . . . . . . . . . . . . . . 90,94 5968 AssertWinnerMetric(S,G,I). . . . . . . . . . . . . . . . . . . . . 83,94 5969 assert_metric. . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5970 Assert_Override_Interval . . . . . . . . . . . . . . . . . . . 83,90,125 5971 Assert_Time. . . . . . . . . . . . . . . . . . . . . . . . . . 83,90,125 5972 AT(*,G,I). . . . . . . . . . . . . . . . . . . . . . . .16,24,84,122,125 5973 AT(S,G,I). . . . . . . . . . . . . . . . . . . . . . . .18,24,77,122,125 5974 CheckSwitchToSpt(S,G). . . . . . . . . . . . . . . . . . . . . . . 26,27 5975 CouldAssert(*,G,I) . . . . . . . . . . . . . . . . . . . .85,87,88,89,91 5976 CouldAssert(S,G,I) . . . . . . . . . . . . . . . . . . 78,79,81,82,83,91 5977 CouldRegister(S,G) . . . . . . . . . . . . . . . . . . . . . . . . 36,38 5978 Default_Hello_Holdtime . . . . . . . . . . . . . . . . . . . . . . . 31 5979 DirectlyConnected(S) . . . . . . . . . . . . . . . . . . .26,26,28,38,97 5980 DownstreamJPState(*,*,RP,I). . . . . . . . . . . . . . . . . . . . 22,98 5981 DownstreamJPState(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 22 5982 DownstreamJPState(S,G,I) . . . . . . . . . . . . . . . . . . . . . 22,38 5983 DownstreamJPState(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . 23 5984 DR(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5985 dr_is_better(a,b,I). . . . . . . . . . . . . . . . . . . . . . . . 31,32 5986 DR_priority. . . . . . . . . . . . . . . . . . . . . . . . . . . . 31,32 5987 ET(*,*,RP,I) . . . . . . . . . . . . . . . . . . . . . . . 15,42,121,124 5988 ET(*,G,I). . . . . . . . . . . . . . . . . . . . . . . . . 16,46,122,124 5989 ET(S,G,I). . . . . . . . . . . . . . . . . . . . . . . . . 18,50,122,124 5990 ET(S,G,rpt,I). . . . . . . . . . . . . . . . . . . . . .19,53,55,122,124 5991 GenID. . . . . . . . . . . . . . . . . . . 16,17,19,30,59,63,66,68,78,85 5992 Hash_Function. . . . . . . . . . . . . . . . . . . . . . . . . . .13,101 5993 Hello_Holdtime . . . . . . . . . . . . . . . . . . . . . . . . . .31,124 5994 Hello_Period . . . . . . . . . . . . . . . . . . . . . . . . . . .29,124 5995 HT(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29,124 5996 IGMP . . . . . . . . . . . . . . . . . . . . . . . . . .7,9,17,22,95,100 5997 immediate_olist(*,*,RP). . . . . . . . . . . . . . . . . . . . . . 21,60 5998 immediate_olist(*,G) . . . . . . . . . . . . . . . . . . . . . . . 21,64 5999 immediate_olist(S,G) . . . . . . . . . . . . . . . . . . . . . .21,38,68 6000 infinite_assert_metric() . . . . . . . . . . . . . . . . . . . . . . 92 6001 inherited_olist(S,G) . . . . . . . . . . . . . . . . .21,26,40,68,79,103 6002 inherited_olist(S,G,rpt) . . . . . . . . . . . . . . . 21,26,28,72,74,76 6003 I_Am_Assert_Loser(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 24 6004 I_Am_Assert_Loser(S,G,I) . . . . . . . . . . . . . . . . . . . . . . 24 6005 I_am_DR(I) . . . . . . . . . . . . . . . . . . . . . . . .21,32,38,79,87 6006 I_am_RP(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40,40 6007 J/P_Holdtime . . . . . . . . . . . . . .43,48,51,55,61,65,70,114,124,126 6008 J/P_Override_Interval(I) . . . . . . . . . . . . . . 44,48,51,55,114,125 6009 JoinDesired(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . 60,73 6010 JoinDesired(*,G) . . . . . . . . . . . . . . . . . . . . .17,64,73,79,91 6011 JoinDesired(S,G) . . . . . . . . . . . . . . . . . . . 18,28,68,79,82,84 6012 joins(*,*,RP(G)) . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6013 joins(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . 21,22,79,87 6014 joins(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 21,22,79,87 6015 joins(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . .21,22,79 6016 JT(*,*,RP) . . . . . . . . . . . . . . . . . . . . . . . . 15,58,122,126 6017 JT(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . 16,62,122,126 6018 JT(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . 18,67,122,126 6019 KAT(S,G) . . . . . . . . . . . . . . . .18,25,26,27,38,40,68,103,122,127 6020 KeepaliveTimer(S,G). . . . . . . . . 18,25,26,26,27,38,40,68,103,122,127 6021 Keepalive_Period . . . . . . . . . . . . . . . . . . . . . . . . .26,127 6022 LAN_delay_default. . . . . . . . . . . . . . . . . . . . . . . . .34,123 6023 lan_delay_enabled(I) . . . . . . . . . . . . . . . . . . . . . . . 33,35 6024 LAN_Prune_Delay. . . . . . . . . . . . . . . . . . . . . . . . . . . 30 6025 local_receiver_exclude(S,G,I). . . . . . . . . . . . . . . . . . . . 22 6026 local_receiver_include(*,G,I). . . . . . . . . . . . . . . . . .22,87,98 6027 local_receiver_include(S,G,I). . . . . . . . . . . . . . . . . .22,79,98 6028 lost_assert(*,G) . . . . . . . . . . . . . . . . . . . . . . . .21,23,79 6029 lost_assert(*,G,I) . . . . . . . . . . . . . . . . . . . . . . .21,23,94 6030 lost_assert(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 21,23 6031 lost_assert(S,G,I) . . . . . . . . . . . . . . . . . . . . . . .21,23,93 6032 lost_assert(S,G,rpt) . . . . . . . . . . . . . . . . . . . . . . . . 23 6033 lost_assert(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . . . 23,93 6034 MBGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7,8 6035 MFIB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7,13 6036 MLD. . . . . . . . . . . . . . . . . . . . . . . . . . .7,9,17,22,95,100 6037 MRIB . . . . . . . . . . . . . . . 7,8,12,16,19,24,58,61,62,71,92,99,121 6038 MRIB.next_hop(host). . . . . . . . . . . . . . . . .24,24,58,59,63,68,96 6039 my_assert_metric(S,G,I). . . . . . . . . . . . . . . . . .79,83,85,87,91 6040 NLT(N,I) . . . . . . . . . . . . . . . . . . . . . . . . . 15,31,121,124 6041 OT(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . 20,72,122,127 6042 Override_Interval(I) . . . . . . . . . . . . . . 14,30,33,34,109,123,125 6043 packet_arrives_on_rp_tunnel(pkt) . . . . . . . . . . . . . . . . . . 40 6044 pim_exclude(S,G) . . . . . . . . . . . . . . . . . . . . . . 21,22,27,79 6045 pim_include(*,G) . . . . . . . . . . . . . . . . . . . 17,21,21,27,79,87 6046 pim_include(S,G) . . . . . . . . . . . . . . . . . . . . .18,21,21,27,79 6047 PPT(*,*,RP,I). . . . . . . . . . . . . . . . . . . . . . . 15,42,121,125 6048 PPT(*,G,I) . . . . . . . . . . . . . . . . . . . . . . . . 16,46,122,125 6049 PPT(S,G,I) . . . . . . . . . . . . . . . . . . . . . . . . 18,50,122,125 6050 PPT(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . .19,53,55,122,125 6051 Propagation_Delay(I) . . . . . . . . . . . . . . . . . . . 30,34,123,125 6052 PruneDesired(S,G,rpt). . . . . . . . . . . . . . . . . . . . 74,75,82,84 6053 prunes(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . .21,23,79 6054 RegisterStop(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . 39 6055 RegisterStop(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . 40 6056 RegisterStopTimer(S,G) . . . . . . . . . . . . . . . . . . 36,37,122,128 6057 Register_Probe_Time. . . . . . . . . . . . . . . . . . . . . . 37,41,128 6058 Register_Suppression_Time. . . . . . . . . . . . . . . . . . . 37,41,128 6059 RP(G). . . . . . . . . . . . . . .6,21,24,38,40,46,64,72,79,87,92,95,121 6060 RPF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6061 RPF'(*,G). . . . . . . . . . . . . . . . . . .24,28,62,63,66,72,73,91,94 6062 RPF'(S,G). . . . . . . . . . . . . . . . . . . . . .24,28,67,72,73,84,94 6063 RPF'(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . 24,72,74,95 6064 RPF_interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 6065 RPF_interface(host). . . . . . . . .24,26,28,38,64,65,70,79,87,93,97,103 6066 RPTJoinDesired(G). . . . . . . . . . . . . . . . . . . . . . . .73,76,87 6067 rpt_assert_metric(G,I) . . . . . . . . . . . . . . . . . . . . . . 90,92 6068 RST(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 36,37,122,128 6069 SPTbit(S,G). . . . . . . . . .19,26,28,40,49,69,72,74,79,79,83,84,93,103 6070 spt_assert_metric(S,I) . . . . . . . . . . . . . . . . . . . . .83,92,93 6071 SSM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11,101 6072 Suppression_Enabled(I) . . . . . . . . . . . . . . . . . . . . . .35,126 6073 SwitchToSptDesired(S,G). . . . . . . . . . . . . . . . . . . . . . 27,27 6074 TIB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7,13,25 6075 Triggered_Hello_Delay. . . . . . . . . . . . . . . . . . . . . 29,30,124 6076 t_joinsuppress . . . . . . . . . . . . . . . . . . . . . .59,61,63,65,70 6077 t_override . . . . . . . . . . . . . . . . . . . . . 59,63,68,73,126,127 6078 t_override_default . . . . . . . . . . . . . . . . . . . . . . . .34,123 6079 t_periodic . . . . . . . . . . . . . . . . . . . . . . . . .59,63,68,126 6080 t_suppressed . . . . . . . . . . . . . . . . . . . . .35,61,65,68,70,126 6081 Update_SPTbit(S,G,iif) . . . . . . . . . . . . . . . . . . . . . . 26,28 6082 UpstreamJPState(S,G) . . . . . . . . . . . . . . . . . . . . . . .26,103