idnits 2.17.1 draft-ietf-pim-sm-v2-new-09.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: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 537 instances of too long lines in the document, the longest one being 8 characters in excess of 72. == There are 2 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 1298: '...Hello messages MUST be sent on all act...' RFC 2119 keyword, line 1304: '...liant PIM router MUST send Hello messa...' RFC 2119 keyword, line 1320: '...address, then it MUST immediately send...' RFC 2119 keyword, line 1326: '...ity. The DR_Priority Option SHOULD be...' RFC 2119 keyword, line 1333: '...r (GenID) Option SHOULD be included in...' (68 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 router's 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 (16 February 2004) is 7365 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 4004 -- Looks like a reference, but probably isn't: 'Actions A6' on line 3660 -- Looks like a reference, but probably isn't: 'Actions A3' on line 4015 -- Looks like a reference, but probably isn't: 'Actions A2' on line 4028 -- Looks like a reference, but probably isn't: 'Actions A4' on line 4015 -- Looks like a reference, but probably isn't: 'Actions A5' on line 4040 ** Downref: Normative reference to an Informational RFC: RFC 2983 (ref. '1') ** Obsolete normative reference: RFC 2460 (ref. '4') (Obsoleted by RFC 8200) == Outdated reference: A later version (-07) exists of draft-ietf-ssm-arch-04 -- Possible downref: Non-RFC (?) normative reference: ref. '7' ** Obsolete normative reference: RFC 2401 (ref. '8') (Obsoleted by RFC 4301) == Outdated reference: A later version (-10) exists of draft-ietf-ipsec-esp-v3-06 ** Obsolete normative reference: RFC 2434 (ref. '10') (Obsoleted by RFC 5226) ** Downref: Normative reference to an Informational RFC: RFC 2715 (ref. '11') -- Obsolete informational reference (is this intentional?): RFC 2283 (ref. '12') (Obsoleted by RFC 2858) == Outdated reference: A later version (-12) exists of draft-ietf-pim-sm-bsr-03 == Outdated reference: A later version (-09) exists of draft-ietf-pim-bidir-05 -- Obsolete informational reference (is this intentional?): RFC 2409 (ref. '15') (Obsoleted by RFC 4306) Summary: 8 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-09.txt Mark Handley/ICIR 4 Hugh Holbrook/Cisco 5 Isidor Kouvelas/Cisco 6 16 February 2004 7 Expires: August 2004 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 . . . . . . . . . . . . . . . . . . . 18 59 4.1.5. (S,G,rpt) State . . . . . . . . . . . . . . . . . 20 60 4.1.6. State Summarization Macros. . . . . . . . . . . . 21 61 4.2. Data Packet Forwarding Rules . . . . . . . . . . . . 25 62 4.2.1. Last-hop switchover to the SPT. . . . . . . . . . 28 63 4.2.2. Setting and Clearing the (S,G) SPT bit. . . . . . 28 64 4.3. Designated Routers (DR) and Hello Messages . . . . . 30 65 4.3.1. Sending Hello Messages. . . . . . . . . . . . . . 30 66 4.3.2. DR Election . . . . . . . . . . . . . . . . . . . 32 67 4.3.3. Reducing Prune Propagation Delay on LANs. . . . . 34 68 4.3.4. Maintaining Secondary Address Lists . . . . . . . 36 69 4.4. PIM Register Messages. . . . . . . . . . . . . . . . 37 70 4.4.1. Sending Register Messages from the DR . . . . . . 38 71 4.4.2. Receiving Register Messages at the RP . . . . . . 42 72 4.5. PIM Join/Prune Messages. . . . . . . . . . . . . . . 44 73 4.5.1. Receiving (*,*,RP) Join/Prune Messages. . . . . . 45 74 4.5.2. Receiving (*,G) Join/Prune Messages . . . . . . . 48 75 4.5.3. Receiving (S,G) Join/Prune Messages . . . . . . . 52 76 4.5.4. Receiving (S,G,rpt) Join/Prune Messages . . . . . 55 77 4.5.5. Sending (*,*,RP) Join/Prune Messages. . . . . . . 61 78 4.5.6. Sending (*,G) Join/Prune Messages . . . . . . . . 65 79 4.5.7. Sending (S,G) Join/Prune Messages . . . . . . . . 70 80 4.5.8. (S,G,rpt) Periodic Messages . . . . . . . . . . . 75 81 4.5.9. State Machine for (S,G,rpt) Triggered Mes- 82 sages. . . . . . . . . . . . . . . . . . . . . . . . . . 76 83 4.5.10. Background: (*,*,RP) and (S,G,rpt) inter- 84 action . . . . . . . . . . . . . . . . . . . . . . . . . 80 85 4.6. PIM Assert Messages. . . . . . . . . . . . . . . . . 82 86 4.6.1. (S,G) Assert Message State Machine. . . . . . . . 82 87 4.6.2. (*,G) Assert Message State Machine. . . . . . . . 90 88 4.6.3. Assert Metrics. . . . . . . . . . . . . . . . . . 97 89 4.6.4. AssertCancel Messages . . . . . . . . . . . . . . 98 90 4.6.5. Assert State Macros . . . . . . . . . . . . . . . 99 91 4.7. PIM Multicast Border Router Behavior . . . . . . . . 102 92 4.7.1. Sources External to the PIM-SM Domain . . . . . . 103 93 4.7.2. Sources Internal to the PIM-SM Domain . . . . . . 103 94 4.8. PIM Bootstrap and RP Discovery . . . . . . . . . . . 105 95 4.8.1. Group-to-RP Mapping . . . . . . . . . . . . . . . 106 96 4.8.2. Hash Function . . . . . . . . . . . . . . . . . . 107 97 4.9. Source-Specific Multicast. . . . . . . . . . . . . . 108 98 4.9.1. Protocol Modifications for SSM destination 99 addresses. . . . . . . . . . . . . . . . . . . . . . . . 108 100 4.9.2. PIM-SSM-only Routers. . . . . . . . . . . . . . . 109 101 4.10. PIM Packet Formats. . . . . . . . . . . . . . . . . 110 102 4.10.1. Encoded Source and Group Address 103 Formats. . . . . . . . . . . . . . . . . . . . . . . . . 111 104 4.10.2. Hello Message Format . . . . . . . . . . . . . . 115 105 4.10.3. Register Message Format. . . . . . . . . . . . . 118 106 4.10.4. Register-Stop Message Format . . . . . . . . . . 120 107 4.10.5. Join/Prune Message Format. . . . . . . . . . . . 121 108 4.10.5.1. Group Set Source List Rules . . . . . . . . . 124 109 4.10.5.2. Group Set Fragmentation . . . . . . . . . . . 128 110 4.10.6. Assert Message Format. . . . . . . . . . . . . . 128 111 4.11. PIM Timers. . . . . . . . . . . . . . . . . . . . . 130 112 4.12. Timer Values. . . . . . . . . . . . . . . . . . . . 131 113 5. IANA Considerations . . . . . . . . . . . . . . . . . . 137 114 5.1. PIM Address Family . . . . . . . . . . . . . . . . . 137 115 5.2. PIM Hello Options. . . . . . . . . . . . . . . . . . 138 116 6. Security Considerations . . . . . . . . . . . . . . . . 138 117 6.1. Attacks based on forged messages . . . . . . . . . . 138 118 6.1.1. Forged link-local messages. . . . . . . . . . . . 138 119 6.1.2. Forged unicast messages . . . . . . . . . . . . . 139 120 6.2. Non-cryptographic Authentication Mechanisms. . . . . 139 121 6.3. Authentication using IPsec . . . . . . . . . . . . . 140 122 6.3.1. Protecting link-local multicast messages. . . . . 140 123 6.3.2. Protecting unicast messages . . . . . . . . . . . 141 124 6.3.2.1. Register messages. . . . . . . . . . . . . . . 141 125 6.3.2.2. Register-Stop messages . . . . . . . . . . . . 141 126 6.4. Denial of Service Attacks. . . . . . . . . . . . . . 142 127 7. Authors' Addresses. . . . . . . . . . . . . . . . . . . 142 128 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . 143 129 9. Normative References. . . . . . . . . . . . . . . . . . 143 130 10. Informative References . . . . . . . . . . . . . . . . 144 131 11. Index. . . . . . . . . . . . . . . . . . . . . . . . . 145 133 List of Figures 135 Figure 1. Per-(S,G) register state-machine at a DR . . . . 38 136 Figure 2. Downstream per-interface (*,*,RP) state- 137 machine. . . . . . . . . . . . . . . . . . . . . . . . . . 46 138 Figure 3. Downstream per-interface (*,G) state- 139 machine. . . . . . . . . . . . . . . . . . . . . . . . . . 49 140 Figure 4. Downstream per-interface (S,G) state- 141 machine. . . . . . . . . . . . . . . . . . . . . . . . . . 53 142 Figure 5. Downstream per-interface (S,G,rpt) state- 143 machine. . . . . . . . . . . . . . . . . . . . . . . . . . 56 144 Figure 6. Upstream (*,*,RP) state-machine. . . . . . . . . 61 145 Figure 7. Upstream (*,G) state-machine . . . . . . . . . . 66 146 Figure 8. Upstream (S,G) state-machine . . . . . . . . . . 71 147 Figure 9. Upstream (S,G,rpt) state-machine for trig- 148 gered messages . . . . . . . . . . . . . . . . . . . . . . 76 149 Figure 10. Per-interface (S,G) Assert 150 State-machine. . . . . . . . . . . . . . . . . . . . . . . 83 151 Figure 11. Per-interface (*,G) Assert 152 State-machine. . . . . . . . . . . . . . . . . . . . . . . 91 154 1. Introduction 156 This document specifies a protocol for efficiently routing multicast 157 groups that may span wide-area (and inter-domain) internets. This 158 protocol is called Protocol Independent Multicast - Sparse Mode (PIM-SM) 159 because, although it may use the underlying unicast routing to provide 160 reverse-path information for multicast tree building, it is not 161 dependent on any particular unicast routing protocol. 163 PIM-SM version 2 was originally specified in RFC 2117, and revised in 164 RFC 2362. This document is intended to obsolete RFC 2362, and to 165 correct a number of deficiencies that have been identified with the way 166 PIM-SM was previously specified. As far as possible, this document 167 specifies the same protocol as RFC 2362, and only diverges from the 168 behavior intended by RFC 2362 when the previously specified behavior was 169 clearly incorrect. Routers implemented according to the specification 170 in this document will be able to successfully interoperate with routers 171 implemented according to RFC 2362. 173 2. Terminology 175 In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", 176 "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and 177 "OPTIONAL" are to be interpreted as described in RFC 2119 and indicate 178 requirement levels for compliant PIM-SM implementations. 180 2.1. Definitions 182 This specification uses a number of terms to refer to the roles of 183 routers participating in PIM-SM. The following terms have special 184 significance for PIM-SM: 186 Rendezvous Point (RP): 187 An RP is a router that has been configured to be used as the root 188 of the non-source-specific distribution tree for a multicast 189 group. Join messages from receivers for a group are sent towards 190 the RP, and data from senders is sent to the RP so that receivers 191 can discover who the senders are, and start to receive traffic 192 destined for the group. 194 Designated Router (DR): 195 A shared-media LAN like Ethernet may have multiple PIM-SM routers 196 connected to it. If the LAN has directly connected hosts, then a 197 single one of these routers, the DR, will act on behalf of those 198 hosts with respect to the PIM-SM protocol. A single DR is elected 199 per interface (LAN or otherwise) using a simple election process. 201 MRIB Multicast Routing Information Base. This is the multicast 202 topology table, which is typically derived from the unicast 203 routing table, or routing protocols such as MBGP that carry 204 multicast-specific topology information. In PIM-SM, the MRIB is 205 used to decide where to send Join/Prune messages. A secondary 206 function of the MRIB is to provide routing metrics for destination 207 addresses, these metrics are used when sending and processing 208 Assert messages. 210 RPF Neighbor 211 RPF stands for "Reverse Path Forwarding". The RPF Neighbor of a 212 router with respect to an address is the neighbor that the MRIB 213 indicates should be used to forward packets to that address. In 214 the case of a PIM-SM multicast group, the RPF neighbor is the 215 router that a Join message for that group would be directed to, in 216 the absence of modifying Assert state. 218 TIB Tree Information Base. This is the collection of state at a PIM 219 router that has been created by receiving PIM Join/Prune messages, 220 PIM Assert messages, and IGMP or MLD information from local hosts. 221 It essentially stores the state of all multicast distribution 222 trees at that router. 224 MFIB Multicast Forwarding Information Base. The TIB holds all the 225 state that is necessary to forward multicast packets at a router. 226 However, although this specification defines forwarding in terms 227 of the TIB, to actually forward packets using the TIB is very 228 inefficient. Instead a real router implementation will normally 229 build an efficient MFIB from the TIB state to perform forwarding. 230 How this is done is implementation-specific, and is not discussed 231 in this document. 233 Upstream 234 Towards the root of the tree. The root of tree may either be the 235 source or the RP depending on the context. 237 Downstream 238 Away from the root of the tree. 240 2.2. Pseudocode Notation 242 We use set notation in several places in this specification. 244 A (+) B 245 is the union of two sets A and B. 247 A (-) B 248 is the elements of set A that are not in set B. 250 NULL 251 is the empty set or list. 253 In addition, we use C-like syntax: 255 = denotes assignment of a variable. 257 == denotes a comparison for equality. 259 != denotes a comparison for inequality. 261 Braces { and } are used for grouping. 263 3. PIM-SM Protocol Overview 265 This section provides an overview of PIM-SM behavior. It is intended as 266 an introduction to how PIM-SM works, and is NOT definitive. For the 267 definitive specification, see Section 4. 269 PIM relies on an underlying topology-gathering protocol to populate a 270 routing table with routes. This routing table is called the MRIB or 271 Multicast Routing Information Base. The routes in this table may be 272 taken directly from the unicast routing table, or it may be different 273 and provided by a separate routing protocol such as MBGP [12]. 274 Regardless of how it is created, the primary role of the MRIB in the PIM 275 protocol is to provide the next hop router along a multicast-capable 276 path to each destination subnet. The MRIB is used to determine the next 277 hop neighbor to which any PIM Join/Prune message is sent. Data flows 278 along the reverse path of the Join messages. Thus, in contrast to the 279 unicast RIB which specifies the next hop that a data packet would take 280 to get to some subnet, the MRIB gives reverse-path information, and 281 indicates the path that a multicast data packet would take from its 282 origin subnet to the router that has the MRIB. 284 Like all multicast routing protocols that implement the service model 285 from RFC 1112 [2], PIM-SM must be able to route data packets from 286 sources to receivers without either the sources or receivers knowing a- 287 priori of the existence of the others. This is essentially done in 288 three phases, although as senders and receivers may come and go at any 289 time, all three phases may be occur simultaneously. 291 Phase One: RP Tree 293 In phase one, a multicast receiver expresses its interest in receiving 294 traffic destined for a multicast group. Typically it does this using 295 IGMP [5] or MLD [3], but other mechanisms might also serve this purpose. 296 One of the receiver's local routers is elected as the Designated Router 297 (DR) for that subnet. On receiving the receiver's expression of 298 interest, the DR then sends a PIM Join message towards the RP for that 299 multicast group. This Join message is known as a (*,G) Join because it 300 joins group G for all sources to that group. The (*,G) Join travels 301 hop-by-hop towards the RP for the group, and in each router it passes 302 through, multicast tree state for group G is instantiated. Eventually 303 the (*,G) Join either reaches the RP, or reaches a router that already 304 has (*,G) Join state for that group. When many receivers join the 305 group, their Join messages converge on the RP, and form a distribution 306 tree for group G that is rooted at the RP. This is known as the RP Tree 307 (RPT), and is also known as the shared tree because it is shared by all 308 sources sending to that group. Join messages are resent periodically so 309 long as the receiver remains in the group. When all receivers on a 310 leaf-network leave the group, the DR will send a PIM (*,G) Prune message 311 towards the RP for that multicast group. However if the Prune message is 312 not sent for any reason, the state will eventually time out. 314 A multicast data sender just starts sending data destined for a 315 multicast group. The sender's local router (DR) takes those data 316 packets, unicast-encapsulates them, and sends them directly to the RP. 317 The RP receives these encapsulated data packets, decapsulates them, and 318 forwards them onto the shared tree. The packets then follow the (*,G) 319 multicast tree state in the routers on the RP Tree, being replicated 320 wherever the RP Tree branches, and eventually reaching all the receivers 321 for that multicast group. The process of encapsulating data packets to 322 the RP is called registering, and the encapsulation packets are known as 323 PIM Register packets. 325 At the end of phase one, multicast traffic is flowing encapsulated to 326 the RP, and then natively over the RP tree to the multicast receivers. 328 Phase Two: Register-Stop 330 Register-encapsulation of data packets is inefficient for two reasons: 332 o Encapsulation and decapsulation may be relatively expensive operations 333 for a router to perform, depending on whether or not the router has 334 appropriate hardware for these tasks. 336 o Traveling all the way to the RP, and then back down the shared tree 337 may entail the packets traveling a relatively long distance to reach 338 receivers that are close to the sender. For some applications, this 339 increased latency is undesirable. 341 Although Register-encapsulation may continue indefinitely, for these 342 reasons, the RP will normally choose to switch to native forwarding. To 343 do this, when the RP receives a register-encapsulated data packet from 344 source S on group G, it will normally initiate an (S,G) source-specific 345 Join towards S. This Join message travels hop-by-hop towards S, 346 instantiating (S,G) multicast tree state in the routers along the path. 347 (S,G) multicast tree state is used only to forward packets for group G 348 if those packets come from source S. Eventually the Join message 349 reaches S's subnet or a router that already has (S,G) multicast tree 350 state, and then packets from S start to flow following the (S,G) tree 351 state towards the RP. These data packets may also reach routers with 352 (*,G) state along the path towards the RP - if so, they can short-cut 353 onto the RP tree at this point. 355 While the RP is in the process of joining the source-specific tree for 356 S, the data packets will continue being encapsulated to the RP. When 357 packets from S also start to arrive natively at the the RP, the RP will 358 be receiving two copies of each of these packets. At this point, the RP 359 starts to discard the encapsulated copy of these packets, and it sends a 360 Register-Stop message back to S's DR to prevent the DR unnecessarily 361 encapsulating the packets. 363 At the end of phase 2, traffic will be flowing natively from S along a 364 source-specific tree to the RP, and from there along the shared tree to 365 the receivers. Where the two trees intersect, traffic may transfer from 366 the source-specific tree to the RP tree, and so avoid taking a long 367 detour via the RP. 369 It should be noted that a sender may start sending before or after a 370 receiver joins the group, and thus phase two may happen before the 371 shared tree to the receiver is built. 373 Phase 3: Shortest-Path Tree 375 Although having the RP join back towards the source removes the 376 encapsulation overhead, it does not completely optimize the forwarding 377 paths. For many receivers the route via the RP may involve a 378 significant detour when compared with the shortest path from the source 379 to the receiver. 381 To obtain lower latencies, a router on the receiver's LAN, typically the 382 DR, may optionally initiate a transfer from the shared tree to a source- 383 specific shortest-path tree (SPT). To do this, it issues an (S,G) Join 384 towards S. This instantiates state in the routers along the path to S. 385 Eventually this join either reaches S's subnet, or reaches a router that 386 already has (S,G) state. When this happens, data packets from S start 387 to flow following the (S,G) state until they reach the receiver. 389 At this point the receiver (or a router upstream of the receiver) will 390 be receiving two copies of the data - one from the SPT and one from the 391 RPT. When the first traffic starts to arrive from the SPT, the DR or 392 upstream router starts to drop the packets for G from S that arrive via 393 the RP tree. In addition, it sends an (S,G) Prune message towards the 394 RP. This is known as an (S,G,rpt) Prune. The Prune message travels 395 hop-by-hop, instantiating state along the path towards the RP indicating 396 that traffic from S for G should NOT be forwarded in this direction. 397 The prune is propagated until it reaches the RP or a router that still 398 needs the traffic from S for other receivers. 400 By now, the receiver will be receiving traffic from S along the 401 shortest-path tree between the receiver and S. In addition, the RP is 402 receiving the traffic from S, but this traffic is no longer reaching the 403 receiver along the RP tree. As far as the receiver is concerned, this 404 is the final distribution tree. 406 Source-specific Joins 408 IGMPv3 permits a receiver to join a group and specify that it only wants 409 to receive traffic for a group if that traffic comes from a particular 410 source. If a receiver does this, and no other receiver on the LAN 411 requires all the traffic for the group, then the DR may omit performing 412 a (*,G) join to set up the shared tree, and instead issue a source- 413 specific (S,G) join only. 415 The range of multicast addresses from 232.0.0.0 to 232.255.255.255 is 416 currently set aside for source-specific multicast in IPv4. For groups 417 in this range, receivers should only issue source-specific IGMPv3 joins. 418 If a PIM router receives a non-source-specific join for a group in this 419 range, it should ignore it, as described in Section 4.9. 421 Source-specific Prunes 423 IGMPv3 also permits a receiver to join a group and specify that it only 424 wants to receive traffic for a group if that traffic does not come from 425 a specific source or sources. In this case, the DR will perform a (*,G) 426 join as normal, but may combine this with an (S,G,rpt) prune for each of 427 the sources the receiver does not wish to receive. 429 Multi-access Transit LANs 431 The overview so far has concerned itself with point-to-point links. 432 However, using multi-access LANs such as Ethernet for transit is not 433 uncommon. This can cause complications for three reasons: 435 o Two or more routers on the LAN may issue (*,G) Joins to different 436 upstream routers on the LAN because they have inconsistent MRIB 437 entries regarding how to reach the RP. Both paths on the RP tree will 438 be set up, causing two copies of all the shared tree traffic to appear 439 on the LAN. 441 o Two or more routers on the LAN may issue (S,G) Joins to different 442 upstream routers on the LAN because they have inconsistent MRIB 443 entries regarding how to reach source S. Both paths on the source- 444 specific tree will be set up, causing two copies of all the traffic 445 from S to appear on the LAN. 447 o A router on the LAN may issue a (*,G) Join to one upstream router on 448 the LAN, and another router on the LAN may issue an (S,G) Join to a 449 different upstream router on the same LAN. Traffic from S may reach 450 the LAN over both the RPT and the SPT. If the receiver behind the 451 downstream (*,G) router doesn't issue an (S,G,rpt) prune, then this 452 condition would persist. 454 All of these problems are caused by there being more than one upstream 455 router with join state for the group or source-group pair. PIM does not 456 prevent such duplicate joins from occurring - instead when duplicate 457 data packets appear on the LAN from different routers, these routers 458 notice this, and then elect a single forwarder. This election is 459 performed using PIM Assert messages, which resolve the problem in favor 460 of the upstream router which has (S,G) state, or if neither or both 461 router has (S,G) state, then in favor of the router with the best metric 462 to the RP for RP trees, or the best metric to the source to source- 463 specific trees. 465 These Assert messages are also received by the downstream routers on the 466 LAN, and these cause subsequent Join messages to be sent to the upstream 467 router that won the Assert. 469 RP Discovery 471 PIM-SM routers need to know the address of the RP for each group for 472 which they have (*,G) state. This address is obtained either through a 473 bootstrap mechanism or through static configuration. 475 One dynamic way to do this is to use the Bootstrap Router (BSR) 476 mechanism [13]. One router in each PIM domain is elected the Bootstrap 477 Router through a simple election process. All the routers in the domain 478 that are configured to be candidates to be RPs periodically unicast 479 their candidacy to the BSR. From the candidates, the BSR picks an RP- 480 set, and periodically announces this set in a Bootstrap message. 481 Bootstrap messages are flooded hop-by-hop throughout the domain until 482 all routers in the domain know the RP-Set. 484 To map a group to an RP, a router hashes the group address into the RP- 485 set using an order-preserving hash function (one that minimizes changes 486 if the RP-Set changes). The resulting RP is the one that it uses as the 487 RP for that group. 489 4. Protocol Specification 491 The specification of PIM-SM is broken into several parts: 493 o Section 4.1 details the protocol state stored. 495 o Section 4.2 specifies the data packet forwarding rules. 497 o Section 4.3. specifies Designated Router (DR) election and the rules 498 for sending and processing Hello messages. 500 o Section 4.4 specifies the PIM Register generation and processing 501 rules. 503 o Section 4.5 specifies the PIM Join/Prune generation and processing 504 rules. 506 o Section 4.6 specifies the PIM Assert generation and processing rules. 508 o Section 4.7 specifies the PIM Multicast Border Router behavior. 510 o Section 4.8 specifies the RP discovery mechanisms. 512 o The subset of PIM required to support Source-Specific Multicast, PIM- 513 SSM, is described in Section 4.9. 515 o PIM packet formats are specified in Section 4.10. 517 o A summary of PIM-SM timers and their default values is given in 518 Section 4.11. 520 4.1. PIM Protocol State 522 This section specifies all the protocol state that a PIM implementation 523 should maintain in order to function correctly. We term this state the 524 Tree Information Base or TIB, as it holds the state of all the multicast 525 distribution trees at this router. In this specification we define PIM 526 mechanisms in terms of the TIB. However, only a very simple 527 implementation would actually implement packet forwarding operations in 528 terms of this state. Most implementations will use this state to build 529 a multicast forwarding table, which would then be updated when the 530 relevant state in the TIB changes. 532 Although we specify precisely the state to be kept, this does not mean 533 that an implementation of PIM-SM needs to hold the state in this form. 534 This is actually an abstract state definition, which is needed in order 535 to specify the router's behavior. A PIM-SM implementation is free to 536 hold whatever internal state it requires, and will still be conformant 537 with this specification so long as it results in the same externally 538 visible protocol behavior as an abstract router that holds the following 539 state. 541 We divide TIB state into four sections: 543 (*,*,RP) state 544 State that maintains per-RP trees, for all groups served by a given 545 RP. 547 (*,G) state 548 State that maintains the RP tree for G. 550 (S,G) state 551 State that maintains a source-specific tree for source S and group 552 G. 554 (S,G,rpt) state 555 State that maintains source-specific information about source S on 556 the RP tree for G. For example, if a source is being received on 557 the source-specific tree, it will normally have been pruned off the 558 RP tree. This prune state is (S,G,rpt) state. 560 The state that should be kept is described below. Of course, 561 implementations will only maintain state when it is relevant to 562 forwarding operations - for example, the "NoInfo" state might be assumed 563 from the lack of other state information, rather than being held 564 explicitly. 566 4.1.1. General Purpose State 568 A router holds the following non-group-specific state: 570 For each interface: 572 o Override Interval 574 o Propagation Delay 576 o Suppression state: One of {"Enable", "Disable"} 578 Neighbor State: 580 For each neighbor: 582 o Information from neighbor's Hello 584 o Neighbor's Gen ID. 586 o Neighbor Liveness Timer (NLT) 588 Designated Router (DR) State: 590 o Designated Router's IP Address 592 o DR's DR Priority 594 The Override Interval, the Propagation Delay and the Interface 595 suppression state are described in Section 4.3.3. Designated Router 596 state is described in Section 4.3. 598 4.1.2. (*,*,RP) State 600 For every RP a router keeps the following state: 602 (*,*,RP) state: 603 For each interface: 605 PIM (*,*,RP) Join/Prune State: 607 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 608 Pending" (PP)} 610 o Prune-Pending Timer (PPT) 612 o Join/Prune Expiry Timer (ET) 614 Not interface specific: 616 Upstream (*,*,RP) Join/Prune State: 618 o State: One of {"NotJoined(*,*,RP)", 619 "Joined(*,*,RP)"} 621 o Upstream Join/Prune Timer (JT) 623 o Last RPF Neighbor towards RP that was used 625 PIM (*,*,RP) Join/Prune state is the result of receiving PIM (*,*,RP) 626 Join/Prune messages on this interface, and is specified in Section 627 4.5.1. 629 The upstream (*,*,RP) Join/Prune State reflects the state of the 630 upstream (*,*,RP) state machine described in Section 4.5.5. 632 The upstream (*,*,RP) Join/Prune Timer is used to send out periodic 633 Join(*,*,RP) messages, and to override Prune(*,*,RP) messages from peers 634 on an upstream LAN interface. 636 The last RPF neighbor towards the RP is stored because if the MRIB 637 changes then the RPF neighbor towards the RP may change. If it does so, 638 then we need to trigger a new Join(*,*,RP) to the new upstream neighbor 639 and a Prune(*,*,RP) to the old upstream neighbor. Similarly, if a 640 router detects through a changed GenID in a Hello message that the 641 upstream neighbor towards the RP has rebooted, then it should re- 642 instantiate state by sending a Join(*,*,RP). These mechanisms are 643 specified in Section 4.5.5. 645 4.1.3. (*,G) State 647 For every group G a router keeps the following state: 649 (*,G) state: 650 For each interface: 652 Local Membership: 653 State: One of {"NoInfo", "Include"} 655 PIM (*,G) Join/Prune State: 657 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 658 Pending" (PP)} 660 o Prune-Pending Timer (PPT) 662 o Join/Prune Expiry Timer (ET) 664 (*,G) Assert Winner State 666 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 667 "I won Assert" (W)} 669 o Assert Timer (AT) 671 o Assert winner's IP Address 673 o Assert winner's Assert Metric 675 Not interface specific: 677 Upstream (*,G) Join/Prune State: 679 o State: One of {"NotJoined(*,G)", "Joined(*,G)"} 681 o Upstream Join/Prune Timer (JT) 683 o Last RP Used 685 o Last RPF Neighbor towards RP that was used 687 Local membership is the result of the local membership mechanism (such 688 as IGMP or MLD) running on that interface. It need not be kept if this 689 router is not the DR on that interface unless this router won a (*,G) 690 assert on this interface for this group, although implementations may 691 optionally keep this state in case they become the DR or assert winner. 692 We recommend storing this information if possible, as it reduces latency 693 converging to stable operating conditions after a failure causing a 694 change of DR. This information is used by the pim_include(*,G) macro 695 described in Section 4.1.6. 697 PIM (*,G) Join/Prune state is the result of receiving PIM (*,G) 698 Join/Prune messages on this interface, and is specified in Section 699 4.5.2. The state is used by the macros that calculate the outgoing 700 interface list in Section 4.1.6, and in the JoinDesired(*,G) macro 701 (defined in Section 4.5.6) that is used in deciding whether a Join(*,G) 702 should be sent upstream. 704 (*,G) Assert Winner state is the result of sending or receiving (*,G) 705 Assert messages on this interface. It is specified in Section 4.6.2. 707 The upstream (*,G) Join/Prune State reflects the state of the upstream 708 (*,G) state machine described in Section 4.5.6. 710 The upstream (*,G) Join/Prune Timer is used to send out periodic 711 Join(*,G) messages, and to override Prune(*,G) messages from peers on an 712 upstream LAN interface. 714 The last RP used must be stored because if the RP-Set changes (Section 715 4.8) then state must be torn down and rebuilt for groups whose RP 716 changes. 718 The last RPF neighbor towards the RP is stored because if the MRIB 719 changes then the RPF neighbor towards the RP may change. If it does so, 720 then we need to trigger a new Join(*,G) to the new upstream neighbor and 721 a Prune(*,G) to the old upstream neighbor. Similarly, if a router 722 detects through a changed GenID in a Hello message that the upstream 723 neighbor towards the RP has rebooted, then it should re-instantiate 724 state by sending a Join(*,G). These mechanisms are specified in Section 725 4.5.6. 727 4.1.4. (S,G) State 729 For every source/group pair (S,G) a router keeps the following state: 731 (S,G) state: 733 For each interface: 735 Local Membership: 736 State: One of {"NoInfo", "Include"} 738 PIM (S,G) Join/Prune State: 740 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 741 Pending" (PP)} 743 o Prune-Pending Timer (PPT) 745 o Join/Prune Expiry Timer (ET) 747 (S,G) Assert Winner State 749 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 750 "I won Assert" (W)} 752 o Assert Timer (AT) 754 o Assert winner's IP Address 756 o Assert winner's Assert Metric 758 Not interface specific: 760 Upstream (S,G) Join/Prune State: 762 o State: One of {"NotJoined(S,G)", "Joined(S,G)"} 764 o Upstream (S,G) Join/Prune Timer (JT) 766 o Last RPF Neighbor towards S that was used 768 o SPT bit (indicates (S,G) state is active) 770 o (S,G) Keepalive Timer (KAT) 771 Additional (S,G) state at the DR: 773 o Register state: One of {"Join" (J), "Prune" (P), 774 "Join-Pending" (JP), "NoInfo" (NI)} 776 o Register-Stop timer 778 Local membership is the result of the local source-specific membership 779 mechanism (such as IGMP version 3) running on that interface and 780 specifying that this particular source should be included. As stored 781 here, this state is the resulting state after any IGMPv3 inconsistencies 782 have been resolved. It need not be kept if this router is not the DR on 783 that interface unless this router won a (S,G) assert on this interface 784 for this group. However, we recommend storing this information if 785 possible, as it reduces latency converging to stable operating 786 conditions after a failure causing a change of DR. This information is 787 used by the pim_include(S,G) macro described in Section 4.1.6. 789 PIM (S,G) Join/Prune state is the result of receiving PIM (S,G) 790 Join/Prune messages on this interface, and is specified in Section 791 4.5.2. The state is used by the macros that calculate the outgoing 792 interface list in Section 4.1.6, and in the JoinDesired(S,G) macro 793 (defined in Section 4.5.7) that is used in deciding whether a Join(S,G) 794 should be sent upstream. 796 (S,G) Assert Winner state is the result of sending or receiving (S,G) 797 Assert messages on this interface. It is specified in Section 4.6.1. 799 The upstream (S,G) Join/Prune State reflects the state of the upstream 800 (S,G) state machine described in Section 4.5.7. 802 The upstream (S,G) Join/Prune Timer is used to send out periodic 803 Join(S,G) messages, and to override Prune(S,G) messages from peers on an 804 upstream LAN interface. 806 The last RPF neighbor towards S is stored because if the MRIB changes 807 then the RPF neighbor towards S may change. If it does so, then we need 808 to trigger a new Join(S,G) to the new upstream neighbor and a Prune(S,G) 809 to the old upstream neighbor. Similarly, if the router detects through 810 a changed GenID in a Hello message that the upstream neighbor towards S 811 has rebooted, then it should re-instantiate state by sending a 812 Join(S,G). These mechanisms are specified in Section 4.5.7. 814 The SPTbit is used to indicate whether forwarding is taking place on the 815 (S,G) Shortest Path Tree (SPT) or on the (*,G) tree. A router can have 816 (S,G) state and still be forwarding on (*,G) state during the interval 817 when the source-specific tree is being constructed. When SPTbit is 818 FALSE, only (*,G) forwarding state is used to forward packets from S to 819 G. When SPTbit is TRUE, both (*,G) and (S,G) forwarding state are used. 821 The (S,G) Keepalive Timer is updated by data being forwarded using this 822 (S,G) forwarding state. It is used to keep (S,G) state alive in the 823 absence of explicit (S,G) Joins. Amongst other things, this is 824 necessary for the so-called "turnaround rules" - when the RP uses (S,G) 825 joins to stop encapsulation, and then (S,G) prunes to prevent traffic 826 from unnecessarily reaching the RP. 828 On a DR, the (S,G) Register State is used to keep track of whether to 829 encapsulate data to the RP on the Register Tunnel; the (S,G) Register- 830 Stop timer tracks how long before encapsulation begins again for a given 831 (S,G). 833 4.1.5. (S,G,rpt) State 835 For every source/group pair (S,G) for which a router also has (*,G) 836 state, it also keeps the following state: 838 (S,G,rpt) state: 840 For each interface: 842 Local Membership: 843 State: One of {"NoInfo", "Exclude"} 845 PIM (S,G,rpt) Join/Prune State: 847 o State: One of {"NoInfo", "Pruned", "Prune- 848 Pending"} 850 o Prune-Pending Timer (PPT) 852 o Join/Prune Expiry Timer (ET) 854 Not interface specific: 856 Upstream (S,G,rpt) Join/Prune State: 858 o State: One of {"RPTNotJoined(G)", 859 "NotPruned(S,G,rpt)", "Pruned(S,G,rpt)"} 861 o Override Timer (OT) 863 Local membership is the result of the local source-specific membership 864 mechanism (such as IGMPv3) running on that interface and specifying that 865 although there is (*,G) Include state, this particular source should be 866 excluded. As stored here, this state is the resulting state after any 867 IGMPv3 inconsistencies between LAN members have been resolved. It need 868 not be kept if this router is not the DR on that interface unless this 869 router won a (*,G) assert on this interface for this group. However, we 870 recommend storing this information if possible, as it reduces latency 871 converging to stable operating conditions after a failure causing a 872 change of DR. This information is used by the pim_exclude(S,G) macro 873 described in Section 4.1.6. 875 PIM (S,G,rpt) Join/Prune state is the result of receiving PIM (S,G,rpt) 876 Join/Prune messages on this interface, and is specified in Section 877 4.5.4. The state is used by the macros that calculate the outgoing 878 interface list in Section 4.1.6, and in the rules for adding 879 Prune(S,G,rpt) messages to Join(*,G) messages specified in Section 880 4.5.8. 882 The upstream (S,G,rpt) Join/Prune state is used along with the Override 883 Timer to send the correct override messages in response to Join/Prune 884 messages sent by upstream peers on a LAN. This state and behavior are 885 specified in Section 4.5.9. 887 4.1.6. State Summarization Macros 889 Using this state, we define the following "macro" definitions which we 890 will use in the descriptions of the state machines and pseudocode in the 891 following sections. 893 The most important macros are those that define the outgoing interface 894 list (or "olist") for the relevant state. An olist can be "immediate" 895 if it is built directly from the state of the relevant type. For 896 example, the immediate_olist(S,G) is the olist that would be built if 897 the router only had (S,G) state and no (*,G) or (S,G,rpt) state. In 898 contrast, the "inherited" olist inherits state from other types. For 899 example, the inherited_olist(S,G) is the olist that is relevant for 900 forwarding a packet from S to G using both source-specific and group- 901 specific state. 903 There is no immediate_olist(S,G,rpt) as (S,G,rpt) state is negative 904 state - it removes interfaces in the (*,G) olist from the olist that is 905 actually used to forward traffic. The inherited_olist(S,G,rpt) is 906 therefore the olist that would be used for a packet from S to G 907 forwarding on the RP tree. It is a strict subset of 908 (immediate_olist(*,*,RP) (+) immediate_olist(*,G)). 910 Generally speaking, the inherited olists are used for forwarding, and 911 the immediate_olists are used to make decisions about state maintenance. 913 immediate_olist(*,*,RP) = 914 joins(*,*,RP) 916 immediate_olist(*,G) = 917 joins(*,G) (+) pim_include(*,G) (-) lost_assert(*,G) 919 immediate_olist(S,G) = 920 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) 922 inherited_olist(S,G,rpt) = 923 ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 924 (+) ( pim_include(*,G) (-) pim_exclude(S,G)) 925 (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) ) 927 inherited_olist(S,G) = 928 inherited_olist(S,G,rpt) (+) immediate_olist(S,G) 930 The macros pim_include(*,G) and pim_include(S,G) indicate the interfaces 931 to which traffic might be forwarded because of hosts that are local 932 members on that interface. Note that normally only the DR cares about 933 local membership, but when an assert happens, the assert winner takes 934 over responsibility for forwarding traffic to local members that have 935 requested traffic on a group or source/group pair. 937 pim_include(*,G) = 938 { all interfaces I such that: 939 ( ( I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) 940 OR AssertWinner(*,G,I) == me ) 941 AND local_receiver_include(*,G,I) } 943 pim_include(S,G) = 944 { all interfaces I such that: 945 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) 946 OR AssertWinner(S,G,I) == me ) 947 AND local_receiver_include(S,G,I) } 949 pim_exclude(S,G) = 950 { all interfaces I such that: 951 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) 952 OR AssertWinner(S,G,I) == me ) 953 AND local_receiver_exclude(S,G,I) } 955 The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD 956 module or other local membership mechanism has determined that there are 957 local members on interface I that desire to receive traffic sent 958 specifically by S to G. "local_receiver_include(*,G,I)" is true if the 959 IGMP/MLD module or other local membership mechanism has determined that 960 there are local members on interface I that desire to receive all 961 traffic sent to G. "local_receiver_exclude(S,G,I) is true if 962 "local_receiver_include(*,G,I)" is true but none of the local members 963 desire to receive traffic from S. 965 The set "joins(*,*,RP)" is the set of all interfaces on which the router 966 has received (*,*,RP) Joins: 968 joins(*,*,RP) = 969 { all interfaces I such that 970 DownstreamJPState(*,*,RP,I) is either Join or 971 Prune-Pending } 973 DownstreamJPState(*,*,RP,I) is the state of the finite state machine in 974 Section 4.5.1. 976 The set "joins(*,G)" is the set of all interfaces on which the router 977 has received (*,G) Joins: 979 joins(*,G) = 980 { all interfaces I such that 981 DownstreamJPState(*,G,I) is either Join or Prune-Pending } 983 DownstreamJPState(*,G,I) is the state of the finite state machine in 984 Section 4.5.2. 986 The set "joins(S,G)" is the set of all interfaces on which the router 987 has received (S,G) Joins: 989 joins(S,G) = 990 { all interfaces I such that 991 DownstreamJPState(S,G,I) is either Join or Prune-Pending } 993 DownstreamJPState(S,G,I) is the state of the finite state machine in 994 Section 4.5.3. 996 The set "prunes(S,G,rpt)" is the set of all interfaces on which the 997 router has received (*,G) joins and (S,G,rpt) prunes. 999 prunes(S,G,rpt) = 1000 { all interfaces I such that 1001 DownstreamJPState(S,G,rpt,I) is Prune or PruneTmp } 1003 DownstreamJPState(S,G,rpt,I) is the state of the finite state machine in 1004 Section 4.5.4. 1006 The set "lost_assert(*,G)" is the set of all interfaces on which the 1007 router has received (*,G) joins but has lost a (*,G) assert. The macro 1008 lost_assert(*,G,I) is defined in Section 4.6.5. 1010 lost_assert(*,G) = 1011 { all interfaces I such that 1012 lost_assert(*,G,I) == TRUE } 1014 The set "lost_assert(S,G,rpt)" is the set of all interfaces on which the 1015 router has received (*,G) joins but has lost an (S,G) assert. The macro 1016 lost_assert(S,G,rpt,I) is defined in Section 4.6.5. 1018 lost_assert(S,G,rpt) = 1019 { all interfaces I such that 1020 lost_assert(S,G,rpt,I) == TRUE } 1022 The set "lost_assert(S,G)" is the set of all interfaces on which the 1023 router has received (S,G) joins but has lost an (S,G) assert. The macro 1024 lost_assert(S,G,I) is defined in Section 4.6.5. 1026 lost_assert(S,G) = 1027 { all interfaces I such that 1028 lost_assert(S,G,I) == TRUE } 1030 The following pseudocode macro definitions are also used in many places 1031 in the specification. Basically RPF' is the RPF neighbor towards an RP 1032 or source unless a PIM-Assert has overridden the normal choice of 1033 neighbor. 1035 neighbor RPF'(*,G) { 1036 if ( I_Am_Assert_Loser(*, G, RPF_interface(RP(G))) ) { 1037 return AssertWinner(*, G, RPF_interface(RP(G)) ) 1038 } else { 1039 return NBR( RPF_interface(RP(G)), MRIB.next_hop( RP(G) ) ) 1040 } 1041 } 1043 neighbor RPF'(S,G,rpt) { 1044 if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) { 1045 return AssertWinner(S, G, RPF_interface(RP(G)) ) 1046 } else { 1047 return RPF'(*,G) 1048 } 1049 } 1050 neighbor RPF'(S,G) { 1051 if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) { 1052 return AssertWinner(S, G, RPF_interface(S) ) 1053 } else { 1054 return NBR( RPF_interface(S), MRIB.next_hop( S ) ) 1055 } 1056 } 1058 RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data packets 1059 should be coming and to which joins should be sent on the RP tree and 1060 SPT respectively. 1062 RPF'(S,G,rpt) is basically RPF'(*,G) modified by the result of an 1063 Assert(S,G) on RPF_interface(RP(G)). In such a case, packets from S 1064 will be originating from a different router than RPF'(*,G). If we only 1065 have active (*,G) Join state, we need to accept packets from 1066 RPF'(S,G,rpt), and add a Prune(S,G,rpt) to the periodic Join(*,G) 1067 messages that we send to RPF'(*,G) (See Section 4.5.8). 1069 The function MRIB.next_hop( S ) returns an address of the next-hop PIM 1070 neighbor toward the host S, as indicated by the current MRIB. If S is 1071 directly adjacent, then MRIB.next_hop( S ) returns NULL. At the RP for 1072 G, MRIB.next_hop( RP(G)) returns NULL. 1074 The function NBR( I, A ) uses information gathered through PIM Hello 1075 messages to map the IP address A of a directly connected PIM neighbor 1076 router on interface I to the primary IP address of the same router 1077 (Section 4.3.4). The primary IP address of a neighbor is the link-local 1078 address that it uses as the source of its PIM Hello messages. Note that 1079 a neighbor's IP address may be non-unique within the PIM neighbor 1080 database due to scope issues. The address must however be unique amongst 1081 the addresses of all the PIM neighbors on a specific interface. 1083 I_Am_Assert_Loser(S, G, I) is true if the Assert start machine (in 1084 Section 4.6.1) for (S,G) on Interface I is in "I am Assert Loser" state. 1086 I_Am_Assert_Loser(*, G, I) is true if the Assert start machine (in 1087 Section 4.6.2) for (*,G) on Interface I is in "I am Assert Loser" state. 1089 4.2. Data Packet Forwarding Rules 1091 The PIM-SM packet forwarding rules are defined below in pseudocode. 1093 iif is the incoming interface of the packet. 1094 S is the source address of the packet. 1095 G is the destination address of the packet (group address). 1096 RP is the address of the Rendezvous Point for this group. 1098 RPF_interface(S) is the interface the MRIB indicates would be used 1099 to route packets to S. 1100 RPF_interface(RP) is the interface the MRIB indicates would be used 1101 to route packets to RP, except at the RP when it is the 1102 decapsulation interface (the "virtual" interface on which register 1103 packets are received). 1105 First, we restart (or start) the Keepalive Timer if the source is on a 1106 directly connected subnet. 1108 Second, we check to see if the SPT bit should be set because we've now 1109 switched from the RP tree to the SPT. 1111 Next we check to see whether the packet should be accepted based on TIB 1112 state and the interface that the packet arrived on. 1114 If the packet should be forwarded using (S,G) state, we then build an 1115 outgoing interface list for the packet. If this list is not empty, then 1116 we restart the (S,G) state Keepalive Timer. 1118 If the packet should be forwarded using (*,*,RP) or (*,G) state, then we 1119 just build an outgoing interface list for the packet. We also check if 1120 we should initiate a switch to start receiving this source on a shortest 1121 path tree. 1123 Finally we remove the incoming interface from the outgoing interface 1124 list we've created, and if the resulting outgoing interface list is not 1125 empty, we forward the packet out of those interfaces. 1127 On receipt of data from S to G on interface iif: 1129 if( DirectlyConnected(S) == TRUE ) { 1130 set KeepaliveTimer(S,G) to Keepalive_Period 1131 # Note: a register state transition or UpstreamJPState(S,G) 1132 # transition may happen as a result of restarting 1133 # KeepaliveTimer, and must be dealt with here. 1134 } 1136 Update_SPTbit(S,G,iif) 1137 oiflist = NULL 1139 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 1140 oiflist = inherited_olist(S,G) 1141 if( oiflist != NULL ) { 1142 set KeepaliveTimer(S,G) to Keepalive_Period 1143 } 1144 } else if( iif == RPF_interface(RP(G)) AND SPTbit(S,G) == FALSE) { 1145 oiflist = inherited_olist(S,G,rpt) 1146 CheckSwitchToSpt(S,G) 1147 } else { 1148 # Note: RPF check failed 1149 if ( SPTbit(S,G) == TRUE AND iif is in inherited_olist(S,G) ) { 1150 send Assert(S,G) on iif 1151 } else if ( SPTbit(S,G) == FALSE AND 1152 iif is in inherited_olist(S,G,rpt) { 1153 send Assert(*,G) on iif 1154 } 1155 } 1157 oiflist = oiflist (-) iif 1158 forward packet on all interfaces in oiflist 1160 This pseudocode employs several "macro" definitions: 1162 DirectlyConnected(S) is TRUE if the source S is on any subnet that is 1163 directly connected to this router (or for packets originating on this 1164 router). 1166 inherited_olist(S,G) and inherited_olist(S,G,rpt) are defined in Section 1167 4.1. 1169 Basically inherited_olist(S,G) is the outgoing interface list for 1170 packets forwarded on (S,G) state taking into account (*,*,RP) state, 1171 (*,G) state, asserts, etc. 1173 inherited_olist(S,G,rpt) is the outgoing interface for packets forwarded 1174 on (*,*,RP) or (*,G) state taking into account (S,G,rpt) prune state, 1175 and asserts, etc. 1177 Update_SPTbit(S,G,iif) is defined in Section 4.2.2. 1179 CheckSwitchToSpt(S,G) is defined in Section 4.2.1. 1181 UpstreamJPState(S,G) is the state of the finite state machine in Section 1182 4.5.7. 1184 Keepalive_Period is defined in Section 4.11. 1186 Data triggered PIM-Assert messages sent from the above forwarding code 1187 should be rate-limited in a implementation-dependent manner. 1189 4.2.1. Last-hop switchover to the SPT 1191 In Sparse-Mode PIM, last-hop routers join the shared tree towards the 1192 RP. Once traffic from sources to joined groups arrives at a last-hop 1193 router it has the option of switching to receive the traffic on a 1194 shortest path tree (SPT). 1196 The decision for a router to switch to the SPT is controlled as follows: 1198 void 1199 CheckSwitchToSpt(S,G) { 1200 if ( ( pim_include(*,G) (-) pim_exclude(S,G) 1201 (+) pim_include(S,G) != NULL ) 1202 AND SwitchToSptDesired(S,G) ) { 1203 restart KeepaliveTimer(S,G); 1204 } 1205 } 1207 SwitchToSptDesired(S,G) is a policy function that is implementation 1208 defined. An "infinite threshold" policy can be implemented making 1209 SwitchToSptDesired(S,G) return false all the time. A "switch on first 1210 packet" policy can be implemented by making SwitchToSptDesired(S,G) 1211 return true once a single packet has been received for the source and 1212 group. 1214 4.2.2. Setting and Clearing the (S,G) SPT bit 1216 The (S,G) SPTbit is used to distinguish whether to forward on 1217 (*,*,RP)/(*,G) or on (S,G) state. When switching from the RP tree to 1218 the source tree, there is a transition period when data is arriving due 1219 to upstream (*,*,RP)/(*,G) state while upstream (S,G) state is being 1220 established during which time a router should continue to forward only 1221 on (*,*,RP)/(*,G) state. This prevents temporary black-holes that would 1222 be caused by sending a Prune(S,G,rpt) before the upstream (S,G) state 1223 has finished being established. 1225 Thus, when a packet arrives, the (S,G) SPTbit is updated as follows: 1227 void 1228 Update_SPTbit(S,G,iif) { 1229 if ( iif == RPF_interface(S) 1230 AND JoinDesired(S,G) == TRUE 1231 AND ( DirectlyConnected(S) == TRUE 1232 OR RPF_interface(S) != RPF_interface(RP(G)) 1233 OR inherited_olist(S,G,rpt) == NULL 1234 OR ( ( RPF'(S,G) == RPF'(*,G) ) AND 1235 ( RPF'(S,G) != NULL ) ) ) { 1236 Set SPTbit(S,G) to TRUE 1237 } 1238 } 1240 Additionally a router can set SPTbit(S,G) to TRUE in other cases, such 1241 as when it receives an Assert(S,G) on RPF_interface(S) (see Section 1242 4.6.1). 1244 JoinDesired(S,G) is defined in Section 4.5.7, and indicates whether we 1245 have the appropriate (S,G) Join state to wish to send a Join(S,G) 1246 upstream. 1248 Basically Update_SPTbit will set the SPT bit if we have the appropriate 1249 (S,G) join state and the packet arrived on the correct upstream 1250 interface for S, and one or more of the following conditions applies: 1252 1. The source is directly connected, in which case the switch to the 1253 SPT is a no-op. 1255 2. The RPF interface to S is different from the RPF interface to the 1256 RP. The packet arrived on RPF_interface(S), and so the SPT must 1257 have been completed. 1259 3. No-one wants the packet on the RP tree. 1261 4. RPF'(S,G) == RPF'(*,G). In this case the router will never be able 1262 to tell if the SPT has been completed, so it should just switch 1263 immediately. 1265 In the case where the RPF interface is the same for the RP and for S, 1266 but RPF'(S,G) and RPF'(*,G) differ, then we wait for an Assert(S,G) 1267 which indicates that the upstream router with (S,G) state believes the 1268 SPT has been completed. However item (3) above is needed because there 1269 may not be any (*,G) state to trigger an Assert(S,G) to happen. 1271 The SPT bit is cleared in the (S,G) upstream state machine (see Section 1272 4.5.7) when JoinDesired(S,G) becomes FALSE. 1274 4.3. Designated Routers (DR) and Hello Messages 1276 A shared-media LAN like Ethernet may have multiple PIM-SM routers 1277 connected to it. If the LAN has directly connected hosts, then a single 1278 one of these routers, the DR, will act on behalf of those hosts with 1279 respect to the PIM-SM protocol. Because the distinction between LANs 1280 and point-to-point interfaces can sometimes be blurred, and because 1281 routers may also have multicast host functionality, the PIM-SM 1282 specification makes no distinction between the two. Thus DR election 1283 will happen on all interfaces, LAN or otherwise. 1285 DR election is performed using Hello messages. Hello messages are also 1286 the way that option negotiation takes place in PIM, so that additional 1287 functionality can be enabled, or parameters tuned. 1289 4.3.1. Sending Hello Messages 1291 PIM-Hello messages are sent periodically on each PIM-enabled interface. 1292 They allow a router to learn about the neighboring PIM routers on each 1293 interface. Hello messages are also the mechanism used to elect a 1294 Designated Router (DR), and to negotiate additional capabilities. A 1295 router must record the Hello information received from each PIM 1296 neighbor. 1298 Hello messages MUST be sent on all active interfaces, including physical 1299 point-to-point links, and are multicast to the `ALL-PIM-ROUTERS' group 1300 address (`224.0.0.13' for IPv4 and `ff02::d' for IPv6). 1302 We note that some implementations do not send Hello messages 1303 on point-to-point interfaces. This is non-compliant behavior. 1304 A compliant PIM router MUST send Hello messages, even on 1305 point-to-point interfaces. 1307 A per interface Hello Timer (HT(I)) is used to trigger sending Hello 1308 messages on each active interface. When PIM is enabled on an interface 1309 or a router first starts, the Hello Timer of that interface is set to a 1310 random value between 0 and Triggered_Hello_Delay. This prevents 1311 synchronization of Hello messages if multiple routers are powered on 1312 simultaneously. After the initial randomized interval, Hello messages 1313 must be sent every Hello_Period seconds. The Hello Timer should not be 1314 reset except when it expires. 1316 Note that neighbors will not accept Join/Prune or Assert messages from a 1317 router unless they have first heard a Hello message from that router. 1318 Thus if a router needs to send a Join/Prune or Assert message on an 1319 interface on which it has not yet sent a Hello message with the 1320 currently configured IP address, then it MUST immediately send the 1321 relevant Hello message without waiting for the Hello Timer to expire, 1322 followed by the Join/Prune or Assert message. 1324 The DR_Priority Option allows a network administrator to give preference 1325 to a particular router in the DR election process by giving it a 1326 numerically larger DR Priority. The DR_Priority Option SHOULD be 1327 included in every Hello message, even if no DR Priority is explicitly 1328 configured on that interface. This is necessary because priority-based 1329 DR election is only enabled when all neighbors on an interface advertise 1330 that they are capable of using the DR_Priority Option. The default 1331 priority is 1. 1333 The Generation_Identifier (GenID) Option SHOULD be included in all Hello 1334 messages. The GenID option contains a randomly generated 32-bit value 1335 that is regenerated each time PIM forwarding is started or restarted on 1336 the interface, including when the router itself restarts. When a Hello 1337 message with a new GenID is received from a neighbor, any old Hello 1338 information about that neighbor SHOULD be discarded and superseded by 1339 the information from the new Hello message. This may cause a new DR to 1340 be chosen on that interface. 1342 The LAN_Prune_Delay Option SHOULD be included in all Hello messages sent 1343 on multi-access LANs. This option advertises a router's capability to 1344 use values other than the default for the Propagation_Delay and 1345 Override_Interval which affect the setting of the Prune-Pending, 1346 Upstream Join and Override Timers (defined in Section 4.11). 1348 The Interface_Address_List Option advertises all the secondary addresses 1349 associated with the source interface of the router originating the 1350 message. The option MUST be included in all Hello messages if there are 1351 secondary addresses associated with the source interface and MAY be 1352 omitted if no secondary addresses exist. 1354 To allow new or rebooting routers to learn of PIM neighbors quickly, 1355 when a Hello message is received from a new neighbor, or a Hello message 1356 with a new GenID is received from an existing neighbor, a new Hello 1357 message should be sent on this interface after a randomized delay 1358 between 0 and Triggered_Hello_Delay. This triggered message need not 1359 change the timing of the scheduled periodic message. If a router needs 1360 to send a Join/Prune to the new neighbor or send an Assert message in 1361 response to an Assert message from the new neighbor before this 1362 randomized delay has expired, then it MUST immediately send the relevant 1363 Hello message without waiting for the Hello Timer to expire, followed by 1364 the Join/Prune or Assert message. If it does not do this, then the new 1365 neighbor will discard the Join/Prune or Assert message. 1367 Before an interface goes down or changes primary IP address, a Hello 1368 message with a zero HoldTime should be sent immediately (with the old IP 1369 address if the IP address changed). This will cause PIM neighbors to 1370 remove this neighbor (or its old IP address) immediately. After an 1371 interface has changed its IP address, it MUST send a Hello message with 1372 its new IP address. If an interface changes one of its secondary IP 1373 addresses, a Hello message with an updated Address_List option and a 1374 non-zero HoldTime should be sent immediately. This will cause PIM 1375 neighbors to update this neighbor's list of secondary addresses 1376 immediately. 1378 4.3.2. DR Election 1380 When a PIM-Hello message is received on interface I the following 1381 information about the sending neighbor is recorded: 1383 neighbor.interface 1384 The interface on which the Hello message arrived. 1386 neighbor.primary_ip_address 1387 The IP address that the PIM neighbor used as the source 1388 address of the Hello message. 1390 neighbor.genid 1391 The Generation ID of the PIM neighbor. 1393 neighbor.dr_priority 1394 The DR Priority field of the PIM neighbor if it is present in 1395 the Hello message. 1397 neighbor.dr_priority_present 1398 A flag indicating if the DR Priority field was present in the 1399 Hello message. 1401 neighbor.timeout 1402 A timer value to time out the neighbor state when it becomes 1403 stale. 1404 The Neighbor Liveness Timer (NLT(N,I)) is reset to 1405 Hello_Holdtime (from the Hello Holdtime option) whenever a 1406 Hello message is received containing a Holdtime option, or to 1407 Default_Hello_Holdtime if the Hello message does not contain 1408 the Holdtime option. 1410 Neighbor state is deleted when the neighbor timeout expires. 1412 The function for computing the DR on interface I is: 1414 host 1415 DR(I) { 1416 dr = me 1417 for each neighbor on interface I { 1418 if ( dr_is_better( neighbor, dr, I ) == TRUE ) { 1419 dr = neighbor 1420 } 1421 } 1422 return dr 1423 } 1425 The function used for comparing DR "metrics" on interface I is: 1427 bool 1428 dr_is_better(a,b,I) { 1429 if( there is a neighbor n on I for which n.dr_priority_present 1430 is false ) { 1431 return a.primary_ip_address > b.primary_ip_address 1432 } else { 1433 return ( a.dr_priority > b.dr_priority ) OR 1434 ( a.dr_priority == b.dr_priority AND 1435 a.primary_ip_address > b.primary_ip_address ) 1436 } 1437 } 1439 The trivial function I_am_DR(I) is defined to aid readability: 1441 bool 1442 I_am_DR(I) { 1443 return DR(I) == me 1444 } 1446 The DR Priority is a 32-bit unsigned number and the numerically larger 1447 priority is always preferred. A router's idea of the current DR on an 1448 interface can change when a PIM-Hello message is received, when a 1449 neighbor times out, or when a router's own DR Priority changes. If the 1450 router becomes the DR or ceases to be the DR, this will normally cause 1451 the DR Register state-machine to change state. Subsequent actions are 1452 determined by that state-machine. 1454 We note that some PIM implementations do not send Hello 1455 messages on point-to-point interfaces, and so cannot perform 1456 DR election on such interfaces. This in non-compliant 1457 behavior. DR election MUST be performed on ALL active PIM-SM 1458 interfaces. 1460 4.3.3. Reducing Prune Propagation Delay on LANs 1462 In addition to the information recorded for the DR Election, the 1463 following per neighbor information is obtained from the LAN Prune Delay 1464 Hello option: 1466 neighbor.lan_prune_delay_present 1467 A flag indicating if the LAN Prune Delay option was present in 1468 the Hello message. 1470 neighbor.tracking_support 1471 A flag storing the value of the T bit in the LAN Prune Delay 1472 option if it is present in the Hello message. This indicates 1473 the neighbor's capability to disable Join message suppression. 1475 neighbor.lan_delay 1476 The LAN Delay field of the LAN Prune Delay option (if present) 1477 in the Hello message. 1479 neighbor.override_interval 1480 The Override_Interval field of the LAN Prune Delay option (if 1481 present) in the Hello message. 1483 The additional state described above is deleted along with the DR 1484 neighbor state when the neighbor timeout expires. 1486 Just like the DR_Priority option, the information provided in the LAN 1487 Prune Delay option is not used unless all neighbors on a link advertise 1488 the option. The function below computes this state: 1490 bool 1491 lan_delay_enabled(I) { 1492 for each neighbor on interface I { 1493 if ( neighbor.lan_prune_delay_present == false ) { 1494 return false 1495 } 1496 } 1497 return true 1498 } 1500 The LAN Delay inserted by a router in the LAN Prune Delay option 1501 expresses the expected message propagation delay on the link and should 1502 be configurable by the system administrator. It is used by upstream 1503 routers to figure out how long they should wait for a Join override 1504 message before pruning an interface. 1506 PIM implementors should enforce a lower bound on the permitted values 1507 for this delay to allow for scheduling and processing delays within 1508 their router. Such delays may cause received messages to be processed 1509 later as well as triggered messages to be sent later than intended. 1510 Setting this LAN Prune Delay to too low a value may result in temporary 1511 forwarding outages because a downstream router will not be able to 1512 override a neighbor's Prune message before the upstream neighbor stops 1513 forwarding. 1515 When all routers on a link are in a position to negotiate a different 1516 than default Propagation Delay, the largest value from those advertised 1517 by each neighbor is chosen. The function for computing the Propagation 1518 Delay of interface I is: 1520 time_interval 1521 Propagation_Delay(I) { 1522 if ( lan_delay_enabled(I) == false ) { 1523 return LAN_delay_default 1524 } 1525 delay = 0 1526 for each neighbor on interface I { 1527 if ( neighbor.lan_delay > delay ) { 1528 delay = neighbor.lan_delay 1529 } 1530 } 1531 return delay 1532 } 1534 To avoid synchronization of override messages when multiple downstream 1535 routers share a multi-access link, sending of such messages is delayed 1536 by a small random amount of time. The period of randomization should 1537 represent the size of the PIM router population on the link. Each 1538 router expresses its view of the amount of randomization necessary in 1539 the Override Delay field of the LAN Prune Delay option. 1541 When all routers on a link are in a position to negotiate a different 1542 than default Override Delay, the largest value from those advertised by 1543 each neighbor is chosen. The function for computing the Override 1544 Interval of interface I is: 1546 time_interval 1547 Override_Interval(I) { 1548 if ( lan_delay_enabled(I) == false ) { 1549 return t_override_default 1550 } 1551 delay = 0 1552 for each neighbor on interface I { 1553 if ( neighbor.override_interval > delay ) { 1554 delay = neighbor.override_interval 1555 } 1556 } 1557 return delay 1558 } 1560 Although the mechanisms are not specified in this document, it is 1561 possible for upstream routers to explicitly track the join membership of 1562 individual downstream routers if Join suppression is disabled. A router 1563 can advertise its willingness to disable Join suppression by using the T 1564 bit in the LAN Prune Delay Hello option. Unless all PIM routers on a 1565 link negotiate this capability, explicit tracking and the disabling of 1566 the Join suppression mechanism are not possible. The function for 1567 computing the state of Suppression on interface I is: 1569 bool 1570 Suppression_Enabled(I) { 1571 if ( lan_delay_enabled(I) == false ) { 1572 return true 1573 } 1574 for each neighbor on interface I { 1575 if ( neighbor.tracking_support == false ) { 1576 return true 1577 } 1578 } 1579 return false 1580 } 1582 Note that the setting of Suppression_Enabled(I) affects the value of 1583 t_suppressed (see Section 4.11). 1585 4.3.4. Maintaining Secondary Address Lists 1587 Communication of a routers interface secondary addresses to its PIM 1588 neighbors is necessary to provide the neighbors with a mechanism for 1589 mapping next_hop information obtained through their MRIB to a primary 1590 address that can be used as a destination for Join/Prune messages. The 1591 mapping is performed through the NBR macro. The primary address of a 1592 PIM neighbor is obtained from the source IP address used in its PIM 1593 Hello messages. Secondary addresses are carried within the Hello message 1594 in an Address List Hello option. The primary address of the source 1595 interface of the router MUST NOT be listed within the Address List Hello 1596 option. 1598 In addition to the information recorded for the DR Election, the 1599 following per neighbor information is obtained from the Address List 1600 Hello option: 1602 neighbor.secondary_address_list 1603 The list of secondary addresses used by the PIM neighbor on 1604 the interface through which the Hello message was transmitted. 1606 When processing a received PIM Hello message containing an Address List 1607 Hello option, the list of secondary addresses in the message completely 1608 replaces any previously associated secondary addresses for that 1609 neighbor. If a received PIM Hello message does not contain an Address 1610 List Hello option then all secondary addresses associated with the 1611 neighbor must be deleted. If a received PIM Hello message contains an 1612 Address List Hello option that includes the primary address of the 1613 sending router in the list of secondary addresses (although this is not 1614 expected) then the addresses listed in the message excluding the primary 1615 address are used to update the associated secondary addresses for that 1616 neighbor. 1618 All the advertised secondary addresses in received Hello messages must 1619 be checked against those previously advertised by all other PIM 1620 neighbors on that interface. If there is a conflict and the same 1621 secondary address was previously advertised by another neighbor then 1622 only the most recently received mapping MUST be maintained and an error 1623 message SHOULD be logged to the administrator in a rate limited manner. 1625 Within one Address List Hello option, all the addresses MUST be of the 1626 same address family. It is not permitted to mix IPv4 and IPv6 addresses 1627 within the same message. In addition, the address family of the fields 1628 in the message SHOULD be the same as the IP source and destination 1629 addresses of the packet header. 1631 4.4. PIM Register Messages 1633 Overview 1635 The Designated Router (DR) on a LAN or point-to-point link encapsulates 1636 multicast packets from local sources to the RP for the relevant group 1637 unless it recently received a Register-Stop message for that (S,G) or 1638 (*,G) from the RP. When the DR receives a Register-Stop message from 1639 the RP, it starts a Register-Stop Timer to maintain this state. Just 1640 before the Register-Stop Timer expires, the DR sends a Null-Register 1641 Message to the RP to allow the RP to refresh the Register-Stop 1642 information at the DR. If the Register-Stop Timer actually expires, the 1643 DR will resume encapsulating packets from the source to the RP. 1645 4.4.1. Sending Register Messages from the DR 1647 Every PIM-SM router has the capability to be a DR. The state machine 1648 below is used to implement Register functionality. For the purposes of 1649 specification, we represent the mechanism to encapsulate packets to the 1650 RP as a Register-Tunnel interface, which is added to or removed from the 1651 (S,G) olist. The tunnel interface then takes part in the normal packet 1652 forwarding rules as specified in Section 4.2. 1654 If register state is maintained, it is maintained only for directly 1655 connected sources, and is per-(S,G). There are four states in the DR's 1656 per-(S,G) Register state-machine: 1658 Join (J) 1659 The register tunnel is "joined" (the join is actually implicit, but 1660 the DR acts as if the RP has joined the DR on the tunnel 1661 interface). 1663 Prune (P) 1664 The register tunnel is "pruned" (this occurs when a Register-Stop 1665 is received). 1667 Join-Pending (JP) 1668 The register tunnel is pruned but the DR is contemplating adding it 1669 back. 1671 NoInfo (NI) 1672 No information. This is the initial state, and the state when the 1673 router is not the DR. 1675 In addition, a Register-Stop Timer (RST) is kept if the state machine is 1676 not in the NoInfo state. 1678 Figure 1: Per-(S,G) register state-machine at a DR in tabular form 1680 +-----------++---------------------------------------------------------------+ 1681 | || Event | 1682 | ++-----------+------------+------------+------------+------------+ 1683 |Prev State ||Register- | Could | Could | Register- | RP changed | 1684 | ||Stop Timer | Register | Register | Stop | | 1685 | ||expires | ->True | ->False | received | | 1686 +-----------++-----------+------------+------------+------------+------------+ 1687 |NoInfo ||- | -> J state | - | - | - | 1688 |(NI) || | add reg | | | | 1689 | || | tunnel | | | | 1690 +-----------++-----------+------------+------------+------------+------------+ 1691 | ||- | - | -> NI | -> P state | -> J state | 1692 | || | | state | | | 1693 | || | | remove reg | remove reg | update reg | 1694 |Join (J) || | | tunnel | tunnel; | tunnel | 1695 | || | | | set | | 1696 | || | | | Register- | | 1697 | || | | | Stop | | 1698 | || | | | Timer(*) | | 1699 +-----------++-----------+------------+------------+------------+------------+ 1700 | ||-> J state | - | -> NI | -> P state | -> J state | 1701 | || | | state | | | 1702 |Join- ||add reg | | | set | add reg | 1703 |Pending ||tunnel | | | Register- | tunnel; | 1704 |(JP) || | | | Stop | cancel | 1705 | || | | | Timer(*) | Register- | 1706 | || | | | | Stop Timer | 1707 +-----------++-----------+------------+------------+------------+------------+ 1708 | ||-> JP | - | -> NI | - | -> J state | 1709 | ||state | | state | | | 1710 | ||set | | | | add reg | 1711 |Prune (P) ||Register- | | | | tunnel; | 1712 | ||Stop | | | | cancel | 1713 | ||Timer(**); | | | | Register- | 1714 | ||send Null- | | | | Stop Timer | 1715 | ||Register | | | | | 1716 +-----------++-----------+------------+------------+------------+------------+ 1718 Notes: 1720 (*) The Register-Stop Timer is set to a random value chosen uniformly 1721 from the interval ( 0.5 * Register_Suppression_Time, 1.5 * 1722 Register_Suppression_Time) minus Register_Probe_Time; 1724 Subtracting off Register_Probe_Time is a bit unnecessary because it 1725 is really small compared to Register_Suppression_Time, but was in 1726 the old spec and is kept for compatibility. 1728 (**) The Register-Stop Timer is set to Register_Probe_Time. 1730 The following actions are defined: 1732 Add Register Tunnel 1734 A Register-Tunnel virtual interface, VI, is created (if it doesn't 1735 already exist) with its encapsulation target being RP(G). 1736 DownstreamJPState(S,G,VI) is set to Join state, causing the tunnel 1737 interface to be added to immediate_olist(S,G). 1739 Remove Register Tunnel 1741 VI is the Register-Tunnel virtual interface with encapsulation target of 1742 RP(G). DownstreamJPState(S,G,VI) is set to NoInfo state, causing the 1743 tunnel interface to be removed from immediate_olist(S,G). If 1744 DownstreamJPState(S,G,VI) is NoInfo for all (S,G), then VI can be 1745 deleted. 1747 Update Register Tunnel 1749 This action occurs when RP(G) changes. 1751 VI_old is the Register-Tunnel virtual interface with encapsulation 1752 target old_RP(G). A Register-Tunnel virtual interface, VI_new, is 1753 created (if it doesn't already exist) with its encapsulation target 1754 being new_RP(G). DownstreamJPState(S,G,VI_old) is set to NoInfo state 1755 and DownstreamJPState(S,G,VI_new) is set to Join state. If 1756 DownstreamJPState(S,G,VI_old) is NoInfo for all (S,G), then VI_old can 1757 be deleted. 1759 Note that we can not simply change the encapsulation target of VI_old 1760 because not all groups using that encapsulation tunnel will have moved 1761 to the same new RP. 1763 CouldRegister(S,G) 1765 The macro "CouldRegister" in the state machine is defined as: 1767 bool CouldRegister(S,G) { 1768 return ( I_am_DR( RPF_interface(S) ) AND 1769 KeepaliveTimer(S,G) is running AND 1770 DirectlyConnected(S) == TRUE ) 1771 } 1773 Note that on reception of a packet at the DR from a directly connected 1774 source, KeepaliveTimer(S,G) needs to be set by the packet forwarding 1775 rules before computing CouldRegister(S,G) in the register state machine, 1776 or the first packet from a source won't be registered. 1778 Encapsulating data packets in the Register Tunnel 1780 Conceptually, the Register Tunnel is an interface with a smaller MTU 1781 than the underlying IP interface towards the RP. IP fragmentation on 1782 packets forwarded on the Register Tunnel is performed based upon this 1783 smaller MTU. The encapsulating DR may perform Path-MTU Discovery to the 1784 RP to determine the effective MTU of the tunnel. This smaller MTU takes 1785 both the outer IP header and the PIM register header overhead into 1786 account. If a multicast packet is fragmented on the way into the 1787 Register Tunnel, each fragment is encapsulated individually so it 1788 contains IP, PIM, and inner IP headers. 1790 In IPv6, the DR MUST perform Path-MTU discovery, and an ICMP 1791 Fragmentation Required message MUST be sent by the encapsulating DR if 1792 it receives a packet that will not fit in the effective MTU of the 1793 tunnel. If the MTU between the DR and the RP results in the effective 1794 tunnel MTU being smaller than 1280 (the IPv6 minimum MTU), the DR MUST 1795 send Fragmentation Required messages with an MTU value of 1280 and MUST 1796 fragment its PIM register messages as required, using an IPv6 1797 fragmentation header between the outer IPv6 header and the PIM Register 1798 header. 1800 Just like any forwarded packet, the TTL of the original data packet is 1801 decremented before it is encapsulated in the Register Tunnel. The 1802 encapsulating packet uses the normal TTL that the router would use for 1803 any locally-generated IP packet. 1805 The IP ECN bits should be copied from the original packet to the IP 1806 header of the encapsulating packet. They SHOULD NOT be set 1807 independently by the encapsulating router. 1809 The Diffserv Code Point (DSCP) should be copied from the original packet 1810 to the IP header of the encapsulating packet. It MAY be set 1811 independently by the encapsulating router, based upon static 1812 configuration or traffic classification. See [1] for more discussion on 1813 setting the DSCP on tunnels. 1815 Handling Register-Stop(*,G) Messages at the DR 1817 An old RP might send a Register-Stop message with the source address set 1818 to all-zeros. This was the normal course of action in RFC 2326 when the 1819 Register message matched against (*,G) state at the RP, and was defined 1820 as meaning "stop encapsulating all sources for this group". However, 1821 the behavior of such a Register-Stop(*,G) is ambiguous or incorrect in 1822 some circumstances. 1824 We specify that an RP should not send Register-Stop(*,G) messages, but 1825 for compatibility, a DR should be able to accept one if it is received. 1827 A Register-Stop(*,G) should be treated as a Register-Stop(S,G) for all 1828 (S,G) Register state machines that are not in the NoInfo state. A 1829 router should not apply a Register-Stop(*,G) to sources that become 1830 active after the Register-Stop(*,G) was received. 1832 4.4.2. Receiving Register Messages at the RP 1834 When an RP receives a Register message, the course of action is decided 1835 according to the following pseudocode: 1837 packet_arrives_on_rp_tunnel( pkt ) { 1838 if( outer.dst is not one of my addresses ) { 1839 drop the packet silently. 1840 # Note: this should not happen if the lower layer is working properly 1841 } 1842 if( I_am_RP(G) AND outer.dst == RP(G) ) { 1843 bool sentRegisterStop = FALSE; 1844 if ( SPTbit(S,G) OR 1845 ( SwitchToSptDesired(S,G) AND ( inherited_olist(S,G) == NULL ))) { 1846 send Register-Stop(S,G) to outer.src 1847 sentRegisterStop = TRUE; 1848 } 1849 if ( SPTbit(S,G) OR SwitchToSptDesired(S,G) ) { 1850 if ( sentRegisterStop == TRUE ) { 1851 restart KeepaliveTimer(S,G) to Keepalive_Period; 1852 } else { 1853 restart KeepaliveTimer(S,G) to RP_Keepalive_Period; 1854 } 1855 } 1856 if( !SPTbit(S,G) AND ! pkt.NullRegisterBit ) { 1857 decapsulate and pass the inner packet to the normal 1858 forwarding path for forwarding on the (*,G) tree. 1859 } 1860 } else { 1861 send Register-Stop(S,G) to outer.src 1862 # Note (*) 1863 } 1864 } 1866 outer.dst is the IP destination address of the encapsulating header. 1868 outer.src is the IP source address of the encapsulating header, i.e., 1869 the DR's address. 1871 I_am_RP(G) is true if the group-to-RP mapping indicates that this router 1872 is the RP for the group. 1874 Note (*): This may block traffic from S for Register_Suppression_Time if 1875 the DR learned about a new group-to-RP mapping before the RP did. 1876 However, this doesn't matter unless we figure out some way for the 1877 RP to also accept (*,G) joins when it doesn't yet realize that it 1878 is about to become the RP for G. This will all get sorted out once 1879 the RP learns the new group-to-rp mapping. We decided to do 1880 nothing about this and just accept the fact that PIM may suffer 1881 interrupted (*,G) connectivity following an RP change. 1883 KeepaliveTimer(S,G) is restarted at the RP when packets arrive on the 1884 proper tunnel interface and the RP desires to switch to the SPT or the 1885 SPTbit is already set. This may cause the upstream (S,G) state machine 1886 to trigger a join if the inherited_olist(S,G) is not NULL; 1888 An RP should preserve (S,G) state that was created in response to a 1889 Register message for at least ( 3 * Register_Suppression_Time ), 1890 otherwise the RP may stop joining (S,G) before the DR for S has 1891 restarted sending registers. Traffic would then be interrupted until 1892 the Register-Stop Timer expires at the DR. 1894 Thus, at the RP, KeepaliveTimer(S,G) should be restarted to ( 3 * 1895 Register_Suppression_Time + Register_Probe_Time ). 1897 Just like any forwarded packet, the TTL of the original data packet is 1898 decremented after it is decapsulated from the Register Tunnel. 1900 The IP ECN bits should be copied from the IP header of the Register 1901 packet to the decapsulated packet. 1903 The Diffserv Code Point (DSCP) should be copied from the IP header of 1904 the Register packet to the decapsulated packet. The RP MAY retain the 1905 DSCP of the inner packet, or re-classify the packet and apply a 1906 different DSCP. Scenarios where each of these might be useful are 1907 discussed in [1]. 1909 4.5. PIM Join/Prune Messages 1911 A PIM Join/Prune message consists of a list of groups and a list of 1912 Joined and Pruned sources for each group. When processing a received 1913 Join/Prune message, each Joined or Pruned source for a Group is 1914 effectively considered individually, and applies to one or more of the 1915 following state machines. When considering a Join/Prune message whose 1916 Upstream Neighbor Address field addresses this router, (*,G) Joins and 1917 Prunes can affect both the (*,G) and (S,G,rpt) downstream state 1918 machines, while (*,*,RP), (S,G) and (S,G,rpt) Joins and Prunes can only 1919 affect their respective downstream state machines. When considering a 1920 Join/Prune message whose Upstream Neighbor Address field addresses 1921 another router, most Join or Prune messages could affect each upstream 1922 state machine. 1924 In general, a PIM Join/Prune message should only be accepted for 1925 processing if it comes from a known PIM neighbor. A PIM router hears 1926 about PIM neighbors through PIM Hello messages. If a router receives a 1927 Join/Prune message from a particular IP source address and it has not 1928 seen a PIM Hello message from that source address, then the Join/Prune 1929 message SHOULD be discarded without further processing. In addition, if 1930 the Hello message from a neighbor was authenticated using IPsec AH (see 1931 Section 6.3) then all Join/Prune messages from that neighbor MUST also 1932 be authenticated using IPsec AH. 1934 We note that some older PIM implementations incorrectly fail to send 1935 Hello messages on point-to-point interfaces, so we also RECOMMEND that a 1936 configuration option be provided to allow interoperation with such older 1937 routers, but that this configuration option SHOULD NOT be enabled by 1938 default. 1940 4.5.1. Receiving (*,*,RP) Join/Prune Messages 1942 The per-interface state-machine for receiving (*,*,RP) Join/Prune 1943 Messages is given below. There are three states: 1945 NoInfo (NI) 1946 The interface has no (*,*,RP) Join state and no timers 1947 running. 1949 Join (J) 1950 The interface has (*,*,RP) Join state which will cause us to 1951 forward packets destined for any group handled by RP from this 1952 interface except if there is also (S,G,rpt) prune information 1953 (see Section 4.5.4) or the router lost an assert on this 1954 interface. 1956 Prune-Pending (PP) 1957 The router has received a Prune(*,*,RP) on this interface from 1958 a downstream neighbor and is waiting to see whether the prune 1959 will be overridden by another downstream router. For 1960 forwarding purposes, the Prune-Pending state functions exactly 1961 like the Join state. 1963 In addition, the state-machine uses two timers: 1965 ExpiryTimer (ET) 1966 This timer is restarted when a valid Join(*,*,RP) is received. 1967 Expiry of the ExpiryTimer causes the interface state to revert 1968 to NoInfo for this RP. 1970 Prune-Pending Timer (PPT) 1971 This timer is set when a valid Prune(*,*,RP) is received. 1972 Expiry of the Prune-Pending Timer causes the interface state 1973 to revert to NoInfo for this RP. 1975 Figure 2: Downstream per-interface (*,*,RP) state-machine in tabular form 1977 +-------------++----------------------------------------------------------+ 1978 | || Event | 1979 | ++-------------+--------------+--------------+--------------+ 1980 |Prev State ||Receive | Receive | Prune- | Expiry Timer | 1981 | ||Join(*,*,RP) | Prune | Pending | Expires | 1982 | || | (*,*,RP) | Timer | | 1983 | || | | Expires | | 1984 +-------------++-------------+--------------+--------------+--------------+ 1985 | ||-> J state | -> NI state | - | - | 1986 |NoInfo (NI) ||start Expiry | | | | 1987 | ||Timer | | | | 1988 +-------------++-------------+--------------+--------------+--------------+ 1989 | ||-> J state | -> PP state | - | -> NI state | 1990 |Join (J) ||restart | start Prune- | | | 1991 | ||Expiry Timer | Pending | | | 1992 | || | Timer | | | 1993 +-------------++-------------+--------------+--------------+--------------+ 1994 | ||-> J state | -> PP state | -> NI state | -> NI state | 1995 | ||restart | | Send Prune- | | 1996 | ||Expiry | | Echo(*,*,RP) | | 1997 |Prune- ||Timer; | | | | 1998 |Pending (PP) ||cancel | | | | 1999 | ||Prune- | | | | 2000 | ||Pending | | | | 2001 | ||Timer | | | | 2002 +-------------++-------------+--------------+--------------+--------------+ 2004 The transition events "Receive Join(*,*,RP)" and "Receive Prune(*,*,RP)" 2005 imply receiving a Join or Prune targeted to this router's address on the 2006 received interface. If the destination address is not correct, these 2007 state transitions in this state machine must not occur, although seeing 2008 such a packet may cause state transitions in other state machines. 2010 On unnumbered interfaces on point-to-point links, the router's address 2011 should be the same as the source address it chose for the Hello message 2012 it sent over that interface. However on point-to-point links we also 2013 recommend that PIM Join/Prune messages with a destination address of all 2014 zeros are also accepted. 2016 Transitions from NoInfo State 2018 When in NoInfo state, the following event may trigger a transition: 2020 Receive Join(*,*,RP) 2021 A Join(*,*,RP) is received on interface I with its Upstream 2022 Neighbor Address set to the router's address on I. 2024 The (*,*,RP) downstream state machine on interface I 2025 transitions to the Join state. The Expiry Timer (ET) is 2026 started, and set to the HoldTime from the triggering 2027 Join/Prune message. 2029 Note that it is possible to receive a Join(*,*,RP) message for 2030 an RP that we do not have information telling us that it is an 2031 RP. In the case of (*,*,RP) state, so long as we have a route 2032 to the RP, this will not cause a problem, and the transition 2033 should still take place. 2035 Transitions from Join State 2037 When in Join state, the following events may trigger a transition: 2039 Receive Join(*,*,RP) 2040 A Join(*,*,RP) is received on interface I with its Upstream 2041 Neighbor Address set to the router's address on I. 2043 The (*,*,RP) downstream state machine on interface I remains 2044 in Join state, and the Expiry Timer (ET) is restarted, set to 2045 maximum of its current value and the HoldTime from the 2046 triggering Join/Prune message. 2048 Receive Prune(*,*,RP) 2049 A Prune(*,*,RP) is received on interface I with its Upstream 2050 Neighbor Address set to the router's address on I. 2052 The (*,*,RP) downstream state machine on interface I 2053 transitions to the Prune-Pending state. The Prune-Pending 2054 Timer is started; it is set to the J/P_Override_Interval(I) if 2055 the router has more than one neighbor on that interface; 2056 otherwise it is set to zero causing it to expire immediately. 2058 Expiry Timer Expires 2059 The Expiry Timer for the (*,*,RP) downstream state machine on 2060 interface I expires. 2062 The (*,*,RP) downstream state machine on interface I 2063 transitions to the NoInfo state. 2065 Transitions from Prune-Pending State 2067 When in Prune-Pending state, the following events may trigger a 2068 transition: 2070 Receive Join(*,*,RP) 2071 A Join(*,*,RP) is received on interface I with its Upstream 2072 Neighbor Address set to the router's address on I. 2074 The (*,*,RP) downstream state machine on interface I 2075 transitions to the Join state. The Prune-Pending Timer is 2076 canceled (without triggering an expiry event). The Expiry 2077 Timer is restarted, set to maximum of its current value and 2078 the HoldTime from the triggering Join/Prune message. 2080 Expiry Timer Expires 2081 The Expiry Timer for the (*,*,RP) downstream state machine on 2082 interface I expires. 2084 The (*,*,RP) downstream state machine on interface I 2085 transitions to the NoInfo state. 2087 Prune-Pending Timer Expires 2088 The Prune-Pending Timer for the (*,*,RP) downstream state 2089 machine on interface I expires. 2091 The (*,*,RP) downstream state machine on interface I 2092 transitions to the NoInfo state. A PruneEcho(*,*,RP) is sent 2093 onto the subnet connected to interface I. 2095 The action "Send PruneEcho(*,*,RP)" is triggered when the 2096 router stops forwarding on an interface as a result of a 2097 prune. A PruneEcho(*,*,RP) is simply a Prune(*,*,RP) message 2098 sent by the upstream router on a LAN with its own address in 2099 the Upstream Neighbor Address field. Its purpose is to add 2100 additional reliability so that if a Prune that should have 2101 been overridden by another router is lost locally on the LAN, 2102 then the PruneEcho may be received and cause the override to 2103 happen. A PruneEcho(*,*,RP) need not be sent on an interface 2104 that contains only a single PIM neighbor during the time this 2105 state machine was in Prune-Pending state. 2107 4.5.2. Receiving (*,G) Join/Prune Messages 2109 When a router receives a Join(*,G) or Prune(*,G) it must first check to 2110 see whether the RP in the message matches RP(G) (the router's idea of 2111 who the RP is). If the RP in the message does not match RP(G) the 2112 Join(*,G) or Prune(*,G) should be silently dropped. (Note that other 2113 source list entries such as (S,G,rpt) or (S,G) in the same Group 2114 Specific Set should still be processed.) If a router has no RP 2115 information (e.g. has not recently received a BSR message) then it may 2116 choose to accept Join(*,G) or Prune(*,G) and treat the RP in the message 2117 as RP(G). 2119 The per-interface state-machine for receiving (*,G) Join/Prune Messages 2120 is given below. There are three states: 2122 NoInfo (NI) 2123 The interface has no (*,G) Join state and no timers running. 2125 Join (J) 2126 The interface has (*,G) Join state which will cause us to 2127 forward packets destined for G from this interface except if 2128 there is also (S,G,rpt) prune information (see Section 4.5.4) 2129 or the router lost an assert on this interface. 2131 Prune-Pending (PP) 2132 The router has received a Prune(*,G) on this interface from a 2133 downstream neighbor and is waiting to see whether the prune 2134 will be overridden by another downstream router. For 2135 forwarding purposes, the Prune-Pending state functions exactly 2136 like the Join state. 2138 In addition, the state-machine uses two timers: 2140 Expiry Timer (ET) 2141 This timer is restarted when a valid Join(*,G) is received. 2142 Expiry of the Expiry Timer causes the interface state to 2143 revert to NoInfo for this group. 2145 Prune-Pending Timer (PPT) 2146 This timer is set when a valid Prune(*,G) is received. Expiry 2147 of the Prune-Pending Timer causes the interface state to 2148 revert to NoInfo for this group. 2150 Figure 3: Downstream per-interface (*,G) state-machine in tabular form 2152 +-------------++---------------------------------------------------------+ 2153 | || Event | 2154 | ++-------------+--------------+-------------+--------------+ 2155 |Prev State ||Receive | Receive | Prune- | Expiry Timer | 2156 | ||Join(*,G) | Prune(*,G) | Pending | Expires | 2157 | || | | Timer | | 2158 | || | | Expires | | 2159 +-------------++-------------+--------------+-------------+--------------+ 2160 | ||-> J state | -> NI state | - | - | 2161 |NoInfo (NI) ||start Expiry | | | | 2162 | ||Timer | | | | 2163 +-------------++-------------+--------------+-------------+--------------+ 2164 | ||-> J state | -> PP state | - | -> NI state | 2165 |Join (J) ||restart | start Prune- | | | 2166 | ||Expiry Timer | Pending | | | 2167 | || | Timer | | | 2168 +-------------++-------------+--------------+-------------+--------------+ 2169 | ||-> J state | -> PP state | -> NI state | -> NI state | 2170 | ||restart | | Send Prune- | | 2171 | ||Expiry | | Echo(*,G) | | 2172 |Prune- ||Timer; | | | | 2173 |Pending (PP) ||cancel | | | | 2174 | ||Prune- | | | | 2175 | ||Pending | | | | 2176 | ||Timer | | | | 2177 +-------------++-------------+--------------+-------------+--------------+ 2179 The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" imply 2180 receiving a Join or Prune targeted to this router's address on the 2181 received interface. If the destination address is not correct, these 2182 state transitions in this state machine must not occur, although seeing 2183 such a packet may cause state transitions in other state machines. 2185 On unnumbered interfaces on point-to-point links, the router's address 2186 should be the same as the source address it chose for the Hello message 2187 it sent over that interface. However on point-to-point links we also 2188 recommend that PIM Join/Prune messages with a destination address of all 2189 zeros are also accepted. 2191 Transitions from NoInfo State 2193 When in NoInfo state, the following event may trigger a transition: 2195 Receive Join(*,G) 2196 A Join(*,G) is received on interface I with its Upstream 2197 Neighbor Address set to the router's address on I. 2199 The (*,G) downstream state machine on interface I transitions 2200 to the Join state. The Expiry Timer (ET) is started, and set 2201 to the HoldTime from the triggering Join/Prune message. 2203 Transitions from Join State 2205 When in Join state, the following events may trigger a transition: 2207 Receive Join(*,G) 2208 A Join(*,G) is received on interface I with its Upstream 2209 Neighbor Address set to the router's address on I. 2211 The (*,G) downstream state machine on interface I remains in 2212 Join state, and the Expiry Timer (ET) is restarted, set to 2213 maximum of its current value and the HoldTime from the 2214 triggering Join/Prune message. 2216 Receive Prune(*,G) 2217 A Prune(*,G) is received on interface I with its Upstream 2218 Neighbor Address set to the router's address on I. 2220 The (*,G) downstream state machine on interface I transitions 2221 to the Prune-Pending state. The Prune-Pending Timer is 2222 started; it is set to the J/P_Override_Interval(I) if the 2223 router has more than one neighbor on that interface; otherwise 2224 it is set to zero causing it to expire immediately. 2226 Expiry Timer Expires 2227 The Expiry Timer for the (*,G) downstream state machine on 2228 interface I expires. 2230 The (*,G) downstream state machine on interface I transitions 2231 to the NoInfo state. 2233 Transitions from Prune-Pending State 2235 When in Prune-Pending state, the following events may trigger a 2236 transition: 2238 Receive Join(*,G) 2239 A Join(*,G) is received on interface I with its Upstream 2240 Neighbor Address set to the router's address on I. 2242 The (*,G) downstream state machine on interface I transitions 2243 to the Join state. The Prune-Pending Timer is canceled 2244 (without triggering an expiry event). The Expiry Timer is 2245 restarted, set to maximum of its current value and the 2246 HoldTime from the triggering Join/Prune message. 2248 Expiry Timer Expires 2249 The Expiry Timer for the (*,G) downstream state machine on 2250 interface I expires. 2252 The (*,G) downstream state machine on interface I transitions 2253 to the NoInfo state. 2255 Prune-Pending Timer Expires 2256 The Prune-Pending Timer for the (*,G) downstream state machine 2257 on interface I expires. 2259 The (*,G) downstream state machine on interface I transitions 2260 to the NoInfo state. A PruneEcho(*,G) is sent onto the subnet 2261 connected to interface I. 2263 The action "Send PruneEcho(*,G)" is triggered when the router 2264 stops forwarding on an interface as a result of a prune. A 2265 PruneEcho(*,G) is simply a Prune(*,G) message sent by the 2266 upstream router on a LAN with its own address in the Upstream 2267 Neighbor Address field. Its purpose is to add additional 2268 reliability so that if a Prune that should have been 2269 overridden by another router is lost locally on the LAN, then 2270 the PruneEcho may be received and cause the override to 2271 happen. A PruneEcho(*,G) need not be sent on an interface 2272 that contains only a single PIM neighbor during the time this 2273 state machine was in Prune-Pending state. 2275 4.5.3. Receiving (S,G) Join/Prune Messages 2277 The per-interface state machine for receiving (S,G) Join/Prune messages 2278 is given below, and is almost identical to that for (*,G) messages. 2279 There are three states: 2281 NoInfo (NI) 2282 The interface has no (S,G) Join state and no (S,G) timers 2283 running. 2285 Join (J) 2286 The interface has (S,G) Join state which will cause us to 2287 forward packets from S destined for G from this interface if 2288 the (S,G) state is active (the SPTbit is set) except if the 2289 router lost an assert on this interface. 2291 Prune-Pending (PP) 2292 The router has received a Prune(S,G) on this interface from a 2293 downstream neighbor and is waiting to see whether the prune 2294 will be overridden by another downstream router. For 2295 forwarding purposes, the Prune-Pending state functions exactly 2296 like the Join state. 2298 In addition, there are two timers: 2300 Expiry Timer (ET) 2301 This timer is set when a valid Join(S,G) is received. Expiry 2302 of the Expiry Timer causes this state machine to revert to 2303 NoInfo state. 2305 Prune-Pending Timer (PPT) 2306 This timer is set when a valid Prune(S,G) is received. Expiry 2307 of the Prune-Pending Timer causes this state machine to revert 2308 to NoInfo state. 2310 Figure 4: Downstream per-interface (S,G) state-machine in tabular form 2312 +-------------++---------------------------------------------------------+ 2313 | || Event | 2314 | ++-------------+--------------+-------------+--------------+ 2315 |Prev State ||Receive | Receive | Prune- | Expiry Timer | 2316 | ||Join(S,G) | Prune(S,G) | Pending | Expires | 2317 | || | | Timer | | 2318 | || | | Expires | | 2319 +-------------++-------------+--------------+-------------+--------------+ 2320 | ||-> J state | -> NI state | - | - | 2321 |NoInfo (NI) ||start Expiry | | | | 2322 | ||Timer | | | | 2323 +-------------++-------------+--------------+-------------+--------------+ 2324 | ||-> J state | -> PP state | - | -> NI state | 2325 |Join (J) ||restart | start Prune- | | | 2326 | ||Expiry Timer | Pending | | | 2327 | || | Timer | | | 2328 +-------------++-------------+--------------+-------------+--------------+ 2329 | ||-> J state | -> PP state | -> NI state | -> NI state | 2330 | ||restart | | Send Prune- | | 2331 | ||Expiry | | Echo(S,G) | | 2332 |Prune- ||Timer; | | | | 2333 |Pending (PP) ||cancel | | | | 2334 | ||Prune- | | | | 2335 | ||Pending | | | | 2336 | ||Timer | | | | 2337 +-------------++-------------+--------------+-------------+--------------+ 2339 The transition events "Receive Join(S,G)" and "Receive Prune(S,G)" imply 2340 receiving a Join or Prune targeted to this router's address on the 2341 received interface. If the destination address is not correct, these 2342 state transitions in this state machine must not occur, although seeing 2343 such a packet may cause state transitions in other state machines. 2345 On unnumbered interfaces on point-to-point links, the router's address 2346 should be the same as the source address it chose for the Hello message 2347 it sent over that interface. However on point-to-point links we also 2348 recommend that PIM Join/Prune messages with a destination address of all 2349 zeros are also accepted. 2351 Transitions from NoInfo State 2353 When in NoInfo state, the following event may trigger a transition: 2355 Receive Join(S,G) 2356 A Join(S,G) is received on interface I with its Upstream 2357 Neighbor Address set to the router's address on I. 2359 The (S,G) downstream state machine on interface I transitions 2360 to the Join state. The Expiry Timer (ET) is started, and set 2361 to the HoldTime from the triggering Join/Prune message. 2363 Transitions from Join State 2365 When in Join state, the following events may trigger a transition: 2367 Receive Join(S,G) 2368 A Join(S,G) is received on interface I with its Upstream 2369 Neighbor Address set to the router's address on I. 2371 The (S,G) downstream state machine on interface I remains in 2372 Join state, and the Expiry Timer (ET) is restarted, set to 2373 maximum of its current value and the HoldTime from the 2374 triggering Join/Prune message. 2376 Receive Prune(S,G) 2377 A Prune(S,G) is received on interface I with its Upstream 2378 Neighbor Address set to the router's address on I. 2380 The (S,G) downstream state machine on interface I transitions 2381 to the Prune-Pending state. The Prune-Pending Timer is 2382 started; it is set to the J/P_Override_Interval(I) if the 2383 router has more than one neighbor on that interface; otherwise 2384 it is set to zero causing it to expire immediately. 2386 Expiry Timer Expires 2387 The Expiry Timer for the (S,G) downstream state machine on 2388 interface I expires. 2390 The (S,G) downstream state machine on interface I transitions 2391 to the NoInfo state. 2393 Transitions from Prune-Pending State 2395 When in Prune-Pending state, the following events may trigger a 2396 transition: 2398 Receive Join(S,G) 2399 A Join(S,G) is received on interface I with its Upstream 2400 Neighbor Address set to the router's address on I. 2402 The (S,G) downstream state machine on interface I transitions 2403 to the Join state. The Prune-Pending Timer is canceled 2404 (without triggering an expiry event). The Expiry Timer is 2405 restarted, set to maximum of its current value and the 2406 HoldTime from the triggering Join/Prune message. 2408 Expiry Timer Expires 2409 The Expiry Timer for the (S,G) downstream state machine on 2410 interface I expires. 2412 The (S,G) downstream state machine on interface I transitions 2413 to the NoInfo state. 2415 Prune-Pending Timer Expires 2416 The Prune-Pending Timer for the (S,G) downstream state machine 2417 on interface I expires. 2419 The (S,G) downstream state machine on interface I transitions 2420 to the NoInfo state. A PruneEcho(S,G) is sent onto the subnet 2421 connected to interface I. 2423 The action "Send PruneEcho(S,G)" is triggered when the router 2424 stops forwarding on an interface as a result of a prune. A 2425 PruneEcho(S,G) is simply a Prune(S,G) message sent by the 2426 upstream router on a LAN with its own address in the Upstream 2427 Neighbor Address field. Its purpose is to add additional 2428 reliability so that if a Prune that should have been 2429 overridden by another router is lost locally on the LAN, then 2430 the PruneEcho may be received and cause the override to 2431 happen. A PruneEcho(S,G) need not be sent on an interface 2432 that contains only a single PIM neighbor during the time this 2433 state machine was in Prune-Pending state. 2435 4.5.4. Receiving (S,G,rpt) Join/Prune Messages 2437 The per-interface state machine for receiving (S,G,rpt) Join/Prune 2438 messages is given below. There are five states: 2440 NoInfo (NI) 2441 The interface has no (S,G,rpt) Prune state and no (S,G,rpt) 2442 timers running. 2444 Prune (P) 2445 The interface has (S,G,rpt) Prune state which will cause us 2446 not to forward packets from S destined for G from this 2447 interface even though the interface has active (*,G) Join 2448 state. 2450 Prune-Pending (PP) 2451 The router has received a Prune(S,G,rpt) on this interface 2452 from a downstream neighbor and is waiting to see whether the 2453 prune will be overridden by another downstream router. For 2454 forwarding purposes, the Prune-Pending state functions exactly 2455 like the NoInfo state. 2457 PruneTmp (P') 2458 This state is a transient state which for forwarding purposes 2459 behaves exactly like the Prune state. A (*,G) Join has been 2460 received (which may cancel the (S,G,rpt) Prune). As we parse 2461 the Join/Prune message from top to bottom, we first enter this 2462 state if the message contains a (*,G) Join. Later in the 2463 message we will normally encounter an (S,G,rpt) prune to re- 2464 instate the Prune state. However if we reach the end of the 2465 message without encountering such a (S,G,rpt) prune, then we 2466 will revert to NoInfo state in this state machine. 2468 As no time is spent in this state, no timers can expire. 2470 Prune-Pending-Tmp (PP') 2471 This state is a transient state which is identical to P' 2472 except that it is associated with the PP state rather than the 2473 P state. For forwarding purposes, PP' behaves exactly like PP 2474 state. 2476 In addition, there are two timers: 2478 Expiry Timer (ET) 2479 This timer is set when a valid Prune(S,G,rpt) is received. 2480 Expiry of the Expiry Timer causes this state machine to revert 2481 to NoInfo state. 2483 Prune-Pending Timer (PPT) 2484 This timer is set when a valid Prune(S,G,rpt) is received. 2485 Expiry of the Prune-Pending Timer causes this state machine to 2486 move on to Prune state. 2488 Figure 5: Downstream per-interface (S,G,rpt) state-machine in tabular form 2490 +----------++----------------------------------------------------------------+ 2491 | || Event | 2492 | ++----------+-----------+-----------+---------+---------+---------+ 2493 |Prev ||Receive | Receive | Receive | End of | Prune- | Expiry | 2494 |State ||Join(*,G) | Join | Prune | Message | Pending | Timer | 2495 | || | (S,G,rpt) | (S,G,rpt) | | Timer | Expires | 2496 | || | | | | Expires | | 2497 +----------++----------+-----------+-----------+---------+---------+---------+ 2498 | ||- | - | -> PP | - | n/a | n/a | 2499 | || | | state | | | | 2500 | || | | start | | | | 2501 |NoInfo || | | Prune- | | | | 2502 |(NI) || | | Pending | | | | 2503 | || | | Timer; | | | | 2504 | || | | start | | | | 2505 | || | | Expiry | | | | 2506 | || | | Timer | | | | 2507 +----------++----------+-----------+-----------+---------+---------+---------+ 2508 | ||-> P' | -> NI | -> P | - | n/a | -> NI | 2509 | ||state | state | state | | | state | 2510 |Prune (P) || | | restart | | | | 2511 | || | | Expiry | | | | 2512 | || | | Timer | | | | 2513 +----------++----------+-----------+-----------+---------+---------+---------+ 2514 |Prune- ||-> PP' | -> NI | - | - | -> P | n/a | 2515 |Pending ||state | state | | | state | | 2516 |(PP) || | | | | | | 2517 +----------++----------+-----------+-----------+---------+---------+---------+ 2518 | ||error | error | -> P | -> NI | n/a | n/a | 2519 |Prune-Tmp || | | state | state | | | 2520 |(P') || | | restart | | | | 2521 | || | | Expiry | | | | 2522 | || | | Timer | | | | 2523 +----------++----------+-----------+-----------+---------+---------+---------+ 2524 | ||error | error | -> PP | -> NI | n/a | n/a | 2525 |Prune- || | | state | state | | | 2526 |Pending- || | | restart | | | | 2527 |Tmp (PP') || | | Expiry | | | | 2528 | || | | Timer | | | | 2529 +----------++----------+-----------+-----------+---------+---------+---------+ 2531 The transition events "Receive Join(S,G,rpt)", "Receive Prune(S,G,rpt)", 2532 and "Receive Join(*,G)" imply receiving a Join or Prune targeted to this 2533 router's address on the received interface. If the destination address 2534 is not correct, these state transitions in this state machine must not 2535 occur, although seeing such a packet may cause state transitions in 2536 other state machines. 2538 On unnumbered interfaces on point-to-point links, the router's address 2539 should be the same as the source address it chose for the Hello message 2540 it sent over that interface. However on point-to-point links we also 2541 recommend that PIM Join/Prune messages with a destination address of all 2542 zeros are also accepted. 2544 Transitions from NoInfo State 2546 When in NoInfo (NI) state, the following event may trigger a transition: 2548 Receive Prune(S,G,rpt) 2549 A Prune(S,G,rpt) is received on interface I with its Upstream 2550 Neighbor Address set to the router's address on I. 2552 The (S,G,rpt) downstream state machine on interface I 2553 transitions to the Prune-Pending state. The Expiry Timer (ET) 2554 is started, and set to the HoldTime from the triggering 2555 Join/Prune message. The Prune-Pending Timer is started; it is 2556 set to the J/P_Override_Interval(I) if the router has more 2557 than one neighbor on that interface; otherwise it is set to 2558 zero causing it to expire immediately. 2560 Transitions from Prune-Pending State 2562 When in Prune-Pending (PP) state, the following events may trigger a 2563 transition: 2565 Receive Join(*,G) 2566 A Join(*,G) is received on interface I with its Upstream 2567 Neighbor Address set to the router's address on I. 2569 The (S,G,rpt) downstream state machine on interface I 2570 transitions to Prune-Pending-Tmp state whilst the remainder of 2571 the compound Join/Prune message containing the Join(*,G) is 2572 processed. 2574 Receive Join(S,G,rpt) 2575 A Join(S,G,rpt) is received on interface I with its Upstream 2576 Neighbor Address set to the router's address on I. 2578 The (S,G,rpt) downstream state machine on interface I 2579 transitions to NoInfo state. ET and PPT are canceled. 2581 Prune-Pending Timer Expires 2582 The Prune-Pending Timer for the (S,G,rpt) downstream state 2583 machine on interface I expires. 2585 The (S,G,rpt) downstream state machine on interface I 2586 transitions to the Prune state. 2588 Transitions from Prune State 2590 When in Prune (P) state, the following events may trigger a transition: 2592 Receive Join(*,G) 2593 A Join(*,G) is received on interface I with its Upstream 2594 Neighbor Address set to the router's address on I. 2596 The (S,G,rpt) downstream state machine on interface I 2597 transitions to PruneTmp state whilst the remainder of the 2598 compound Join/Prune message containing the Join(*,G) is 2599 processed. 2601 Receive Join(S,G,rpt) 2602 A Join(S,G,rpt) is received on interface I with its Upstream 2603 Neighbor Address set to the router's address on I. 2605 The (S,G,rpt) downstream state machine on interface I 2606 transitions to NoInfo state. ET and PPT are canceled. 2608 Receive Prune(S,G,rpt) 2609 A Prune(S,G,rpt) is received on interface I with its Upstream 2610 Neighbor Address set to the router's address on I. 2612 The (S,G,rpt) downstream state machine on interface I remains 2613 in Prune state. The Expiry Timer (ET) is restarted, set to 2614 maximum of its current value and the HoldTime from the 2615 triggering Join/Prune message. 2617 Expiry Timer Expires 2618 The Expiry Timer for the (S,G,rpt) downstream state machine on 2619 interface I expires. 2621 The (S,G,rpt) downstream state machine on interface I 2622 transitions to the NoInfo state. 2624 Transitions from Prune-Pending-Tmp State 2626 When in Prune-Pending-Tmp (PP') state and processing a compound 2627 Join/Prune message, the following events may trigger a transition: 2629 Receive Prune(S,G,rpt) 2630 The compound Join/Prune message contains a Prune(S,G,rpt). 2632 The (S,G,rpt) downstream state machine on interface I 2633 transitions back to the Prune-Pending state. The Expiry Timer 2634 (ET) is restarted, set to maximum of its current value and the 2635 HoldTime from the triggering Join/Prune message. 2637 End of Message 2638 The end of the compound Join/Prune message is reached. 2640 The (S,G,rpt) downstream state machine on interface I 2641 transitions to the NoInfo state. ET and PPT are canceled. 2643 Transitions from PruneTmp State 2645 When in PruneTmp (P') state and processing a compound Join/Prune 2646 message, the following events may trigger a transition: 2648 Receive Prune(S,G,rpt) 2649 The compound Join/Prune message contains a Prune(S,G,rpt). 2651 The (S,G,rpt) downstream state machine on interface I 2652 transitions back to the Prune state. The Expiry Timer (ET) is 2653 restarted, set to maximum of its current value and the 2654 HoldTime from the triggering Join/Prune message. 2656 End of Message 2657 The end of the compound Join/Prune message is reached. 2659 The (S,G,rpt) downstream state machine on interface I 2660 transitions to the NoInfo state. ET is canceled. 2662 Notes: 2664 Receiving a Prune(*,G) does not affect the (S,G,rpt) downstream state 2665 machine. 2667 Receiving a Join(*,*,RP) does not affect the (S,G,rpt) downstream state 2668 machine. If a router has originated Join(*,*,RP) and pruned a source 2669 off it using Prune(S,G,rpt), then to receive that source again it should 2670 explicitly re-join using Join(S,G,rpt) or Join(*,G). In some LAN 2671 topologies it is possible for a router sending a new Join(*,*,RP) to 2672 have to wait as much as a Join/Prune Interval before noticing that it 2673 needs to override a neighbor's pre-existing Prune(S,G,rpt). This is 2674 considered acceptable, as (*,*,RP) state is intended to be used only in 2675 long-lived and persistent scenarios. 2677 4.5.5. Sending (*,*,RP) Join/Prune Messages 2679 The per-interface state-machines for (*,*,RP) hold join state from 2680 downstream PIM routers. This state then determines whether a router 2681 needs to propagate a Join(*,*,RP) upstream towards the RP. 2683 If a router wishes to propagate a Join(*,*,RP) upstream, it must also 2684 watch for messages on its upstream interface from other routers on that 2685 subnet, and these may modify its behavior. If it sees a Join(*,*,RP) to 2686 the correct upstream neighbor, it should suppress its own Join(*,*,RP). 2687 If it sees a Prune(*,*,RP) to the correct upstream neighbor, it should 2688 be prepared to override that prune by sending a Join(*,*,RP) almost 2689 immediately. Finally, if it sees the Generation ID (see Section 4.3) of 2690 the correct upstream neighbor change, it knows that the upstream 2691 neighbor has lost state, and it should be prepared to refresh the state 2692 by sending a Join(*,*,RP) almost immediately. 2694 In addition, if the MRIB changes to indicate that the next hop towards 2695 the RP has changed, the router should prune off from the old next hop, 2696 and join towards the new next hop. 2698 The upstream (*,*,RP) state-machine contains only two states: 2700 Not Joined 2701 The downstream state-machines and local membership information do 2702 not indicate that the router needs to join the (*,*,RP) tree for 2703 this RP. 2705 Joined 2706 The downstream state-machines and local membership information 2707 indicate that the router should join the (*,*,RP) tree for this RP. 2709 In addition, one timer JT(*,*,RP) is kept which is used to trigger the 2710 sending of a Join(*,*,RP) to the upstream next hop towards the RP, 2711 NBR(RPF_interface(RP), MRIB.next_hop(RP)). 2713 Figure 6: Upstream (*,*,RP) state-machine in tabular form 2715 +--------------------++-------------------------------------------------+ 2716 | || Event | 2717 | Prev State ++-------------------------+-----------------------+ 2718 | || JoinDesired | JoinDesired | 2719 | || (*,*,RP) ->True | (*,*,RP) ->False | 2720 +--------------------++-------------------------+-----------------------+ 2721 | || -> J state | - | 2722 | NotJoined (NJ) || Send Join(*,*,RP); | | 2723 | || Set Join Timer to | | 2724 | || t_periodic | | 2725 +--------------------++-------------------------+-----------------------+ 2726 | Joined (J) || - | -> NJ state | 2727 | || | Send Prune | 2728 | || | (*,*,RP); Cancel | 2729 | || | Join Timer | 2730 +--------------------++-------------------------+-----------------------+ 2732 In addition, we have the following transitions which occur within the 2733 Joined state: 2735 +-----------------------------------------------------------------------+ 2736 | In Joined (J) State | 2737 +-------------------+--------------------+------------------------------+ 2738 | Timer Expires | See | See | 2739 | | Join(*,*,RP) | Prune(*,*,RP) | 2740 | | to MRIB. | to MRIB. | 2741 | | next_hop(RP) | next_hop(RP) | 2742 +-------------------+--------------------+------------------------------+ 2743 | Send | Increase Join | Decrease Join | 2744 | Join(*,*,RP); | Timer to | Timer to | 2745 | Set Join Timer | t_joinsuppress | t_override | 2746 | to t_periodic | | | 2747 +-------------------+--------------------+------------------------------+ 2749 ------------------------------------------------------------------------- 2750 In Joined (J) State 2751 ------------------------------------------------------------------------- 2752 NBR(RPF_interface(RP), MRIB.next_hop(RP) GenID 2753 MRIB.next_hop(RP)) changes 2754 changes 2755 ------------------------------------------------------------------------- 2756 Send Join(*,*,RP) to new Decrease Join Timer to 2757 next hop; Send t_override 2758 Prune(*,*,RP) to old 2759 next hop; set Join Timer 2760 to t_periodic 2762 | | | 2763 | | | 2764 | | | 2766 | | | 2767 | | | 2768 +-----------------------------------+-----------------------------------+ 2770 This state machine uses the following macro: 2772 bool JoinDesired(*,*,RP) { 2773 if immediate_olist(*,*,RP) != NULL 2774 return TRUE 2775 else 2776 return FALSE 2777 } 2779 JoinDesired(*,*,RP) is true when the router has received (*,*,RP) Joins 2780 from any downstream interface. Note that although JoinDesired is true, 2781 the router's sending of a Join(*,*,RP) message may be suppressed by 2782 another router sending a Join(*,*,RP) onto the upstream interface. 2784 Transitions from NotJoined State 2786 When the upstream (*,*,RP) state-machine is in NotJoined state, the 2787 following event may trigger a state transition: 2789 JoinDesired(*,*,RP) becomes True 2790 The downstream state for (*,*,RP) has changed so that at least 2791 one interface is in immediate_olist(*,*,RP), making 2792 JoinDesired(*,*,RP) become True. 2794 The upstream (*,*,RP) state machine transitions to Joined 2795 state. Send Join(*,*,RP) to the appropriate upstream 2796 neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)). 2797 Set the Join Timer (JT) to expire after t_periodic seconds. 2799 Transitions from Joined State 2801 When the upstream (*,*,RP) state-machine is in Joined state, the 2802 following events may trigger state transitions: 2804 JoinDesired(*,*,RP) becomes False 2805 The downstream state for (*,*,RP) has changed so no interface 2806 is in immediate_olist(*,*,RP), making JoinDesired(*,*,RP) 2807 become False. 2809 The upstream (*,*,RP) state machine transitions to NotJoined 2810 state. Send Prune(*,*,RP) to the appropriate upstream 2811 neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)). 2812 Cancel the Join Timer (JT). 2814 Join Timer Expires 2815 The Join Timer (JT) expires, indicating time to send a 2816 Join(*,*,RP) 2818 Send Join(*,*,RP) to the appropriate upstream neighbor, which 2819 is NBR(RPF_interface(RP), MRIB.next_hop(RP)). Restart the 2820 Join Timer (JT) to expire after t_periodic seconds. 2822 See Join(*,*,RP) to MRIB.next_hop(RP) 2823 This event is only relevant if RPF_interface(RP) is a shared 2824 medium. This router sees another router on RPF_interface(RP) 2825 send a Join(*,*,RP) to any of the addresses belonging to 2826 NBR(RPF_interface(RP), MRIB.next_hop(RP)). This causes this 2827 router to suppress its own Join. 2829 The upstream (*,*,RP) state machine remains in Joined state. 2831 Let t_joinsuppress be the minimum of t_suppressed and the 2832 HoldTime from the Join/Prune message triggering this event. 2833 If the Join Timer is set to expire in less than t_joinsuppress 2834 seconds, reset it so that it expires after t_joinsuppress 2835 seconds. If the Join Timer is set to expire in more than 2836 t_joinsuppress seconds, leave it unchanged. 2838 See Prune(*,*,RP) to MRIB.next_hop(RP) 2839 This event is only relevant if RPF_interface(RP) is a shared 2840 medium. This router sees another router on RPF_interface(RP) 2841 send a Prune(*,*,RP) to any of the addresses belonging to 2842 NBR(RPF_interface(RP), MRIB.next_hop(RP)). As this router is 2843 in Joined state, it must override the Prune after a short 2844 random interval. 2846 The upstream (*,*,RP) state machine remains in Joined state. 2847 If the Join Timer is set to expire in more than t_override 2848 seconds, reset it so that it expires after t_override seconds. 2849 If the Join Timer is set to expire in less than t_override 2850 seconds, leave it unchanged. 2852 NBR(RPF_interface(RP), MRIB.next_hop(RP)) changes 2853 A change in the MRIB routing base causes the next hop towards 2854 the RP to change. 2856 The upstream (*,*,RP) state machine remains in Joined state. 2857 Send Join(*,*,RP) to the new upstream neighbor which is the 2858 new value of NBR(RPF_interface(RP), MRIB.next_hop(RP)). Send 2859 Prune(*,*,RP) to the old upstream neighbor, which is the old 2860 value of NBR(RPF_interface(RP), MRIB.next_hop(RP)). Set the 2861 Join Timer (JT) to expire after t_periodic seconds. 2863 MRIB.next_hop(RP) GenID changes 2864 The Generation ID of the router that is MRIB.next_hop(RP) 2865 changes. This normally means that this neighbor has lost 2866 state, and so the state must be refreshed. 2868 The upstream (*,*,RP) state machine remains in Joined state. 2869 If the Join Timer is set to expire in more than t_override 2870 seconds, reset it so that it expires after t_override seconds. 2872 4.5.6. Sending (*,G) Join/Prune Messages 2874 The per-interface state-machines for (*,G) hold join state from 2875 downstream PIM routers. This state then determines whether a router 2876 needs to propagate a Join(*,G) upstream towards the RP. 2878 If a router wishes to propagate a Join(*,G) upstream, it must also watch 2879 for messages on its upstream interface from other routers on that 2880 subnet, and these may modify its behavior. If it sees a Join(*,G) to 2881 the correct upstream neighbor, it should suppress its own Join(*,G). If 2882 it sees a Prune(*,G) to the correct upstream neighbor, it should be 2883 prepared to override that prune by sending a Join(*,G) almost 2884 immediately. Finally, if it sees the Generation ID (see Section 4.3) of 2885 the correct upstream neighbor change, it knows that the upstream 2886 neighbor has lost state, and it should be prepared to refresh the state 2887 by sending a Join(*,G) almost immediately. 2889 If a (*,G) Assert occurs on the upstream interface, and this changes 2890 this router's idea of the upstream neighbor, it should be prepared to 2891 ensure that the Assert winner is aware of downstream routers by sending 2892 a Join(*,G) almost immediately. 2894 In addition, if the MRIB changes to indicate that the next hop towards 2895 the RP has changed, and either the upstream interface changes or there 2896 is no Assert winner on the upstream interface, the router should prune 2897 off from the old next hop, and join towards the new next hop. 2899 The upstream (*,G) state-machine only contains two states: 2901 Not Joined 2902 The downstream state-machines indicate that the router does not 2903 need to join the RP tree for this group. 2905 Joined 2906 The downstream state-machines indicate that the router should join 2907 the RP tree for this group. 2909 In addition, one timer JT(*,G) is kept which is used to trigger the 2910 sending of a Join(*,G) to the upstream next hop towards the RP, 2911 RPF'(*,G). 2913 Figure 7: Upstream (*,G) state-machine in tabular form 2915 +--------------------++-------------------------------------------------+ 2916 | || Event | 2917 | Prev State ++------------------------+------------------------+ 2918 | || JoinDesired(*,G) | JoinDesired(*,G) | 2919 | || ->True | ->False | 2920 +--------------------++------------------------+------------------------+ 2921 | || -> J state | - | 2922 | NotJoined (NJ) || Send Join(*,G); | | 2923 | || Set Join Timer to | | 2924 | || t_periodic | | 2925 +--------------------++------------------------+------------------------+ 2926 | Joined (J) || - | -> NJ state | 2927 | || | Send Prune(*,G); | 2928 | || | Cancel Join Timer | 2929 +--------------------++------------------------+------------------------+ 2931 In addition, we have the following transitions which occur within the 2932 Joined state: 2934 +-----------------------------------------------------------------------+ 2935 | In Joined (J) State | 2936 +-----------------+-----------------+-----------------+-----------------+ 2937 |Timer Expires | See Join(*,G) | See Prune(*,G) | RPF'(*,G) | 2938 | | to RPF'(*,G) | to RPF'(*,G) | changes due to | 2939 | | | | an Assert | 2940 +-----------------+-----------------+-----------------+-----------------+ 2941 |Send | Increase Join | Decrease Join | Decrease Join | 2942 |Join(*,G); Set | Timer to | Timer to | Timer to | 2943 |Join Timer to | t_joinsuppress | t_override | t_override | 2944 |t_periodic | | | | 2945 +-----------------+-----------------+-----------------+-----------------+ 2947 +-----------------------------------------------------------------------+ 2948 | In Joined (J) State | 2949 +----------------------------------+------------------------------------+ 2950 | RPF'(*,G) changes not | RPF'(*,G) GenID changes | 2951 | due to an Assert | | 2952 +----------------------------------+------------------------------------+ 2953 | Send Join(*,G) to new | Decrease Join Timer to | 2954 | next hop; Send | t_override | 2955 | Prune(*,G) to old next | | 2956 | hop; Set Join Timer to | | 2957 | t_periodic | | 2958 +----------------------------------+------------------------------------+ 2959 This state machine uses the following macro: 2961 bool JoinDesired(*,G) { 2962 if (immediate_olist(*,G) != NULL OR 2963 (JoinDesired(*,*,RP(G)) AND 2964 AssertWinner(*, G, RPF_interface(RP(G))) != NULL)) 2965 return TRUE 2966 else 2967 return FALSE 2968 } 2970 JoinDesired(*,G) is true when the router has forwarding state that would 2971 cause it to forward traffic for G using shared tree state. Note that 2972 although JoinDesired is true, the router's sending of a Join(*,G) 2973 message may be suppressed by another router sending a Join(*,G) onto the 2974 upstream interface. 2976 Transitions from NotJoined State 2978 When the upstream (*,G) state-machine is in NotJoined state, the 2979 following event may trigger a state transition: 2981 JoinDesired(*,G) becomes True 2982 The downstream state for (*,G) has changed so that at least 2983 one interface is in immediate_olist(*,G), making 2984 JoinDesired(*,G) become True. 2986 The upstream (*,G) state machine transitions to Joined state. 2987 Send Join(*,G) to the appropriate upstream neighbor, which is 2988 RPF'(*,G). Set the Join Timer (JT) to expire after t_periodic 2989 seconds. 2991 Transitions from Joined State 2993 When the upstream (*,G) state-machine is in Joined state, the following 2994 events may trigger state transitions: 2996 JoinDesired(*,G) becomes False 2997 The downstream state for (*,G) has changed so no interface is 2998 in immediate_olist(*,G), making JoinDesired(*,G) become False. 3000 The upstream (*,G) state machine transitions to NotJoined 3001 state. Send Prune(*,G) to the appropriate upstream neighbor, 3002 which is RPF'(*,G). Cancel the Join Timer (JT). 3004 Join Timer Expires 3005 The Join Timer (JT) expires, indicating time to send a 3006 Join(*,G) 3007 Send Join(*,G) to the appropriate upstream neighbor, which is 3008 RPF'(*,G). Restart the Join Timer (JT) to expire after 3009 t_periodic seconds. 3011 See Join(*,G) to RPF'(*,G) 3012 This event is only relevant if RPF_interface(RP(G)) is a 3013 shared medium. This router sees another router on 3014 RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G). This 3015 causes this router to suppress its own Join. 3017 The upstream (*,G) state machine remains in Joined state. 3019 Let t_joinsuppress be the minimum of t_suppressed and the 3020 HoldTime from the Join/Prune message triggering this event. 3021 If the Join Timer is set to expire in less than t_joinsuppress 3022 seconds, reset it so that it expires after t_joinsuppress 3023 seconds. If the Join Timer is set to expire in more than 3024 t_joinsuppress seconds, leave it unchanged. 3026 See Prune(*,G) to RPF'(*,G) 3027 This event is only relevant if RPF_interface(RP(G)) is a 3028 shared medium. This router sees another router on 3029 RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G). As this 3030 router is in Joined state, it must override the Prune after a 3031 short random interval. 3033 The upstream (*,G) state machine remains in Joined state. If 3034 the Join Timer is set to expire in more than t_override 3035 seconds, reset it so that it expires after t_override seconds. 3036 If the Join Timer is set to expire in less than t_override 3037 seconds, leave it unchanged. 3039 RPF'(*,G) changes due to an Assert 3040 The current next hop towards the RP changes due to an 3041 Assert(*,G) on the RPF_interface(RP(G)). 3043 The upstream (*,G) state machine remains in Joined state. If 3044 the Join Timer is set to expire in more than t_override 3045 seconds, reset it so that it expires after t_override seconds. 3046 If the Join Timer is set to expire in less than t_override 3047 seconds, leave it unchanged. 3049 RPF'(*,G) changes not due to an Assert 3050 An event occurred which caused the next hop towards the RP for 3051 G to change. This may be caused by a change in the MRIB 3052 routing database or the group-to-RP mapping. Note that this 3053 transition does not occur if an Assert is active and the 3054 upstream interface does not change. 3056 The upstream (*,G) state machine remains in Joined state. 3057 Send Join(*,G) to the new upstream neighbor which is the new 3058 value of RPF'(*,G). Send Prune(*,G) to the old upstream 3059 neighbor, which is the old value of RPF'(*,G). Set the Join 3060 Timer (JT) to expire after t_periodic seconds. 3062 RPF'(*,G) GenID changes 3063 The Generation ID of the router that is RPF'(*,G) changes. 3064 This normally means that this neighbor has lost state, and so 3065 the state must be refreshed. 3067 The upstream (*,G) state machine remains in Joined state. If 3068 the Join Timer is set to expire in more than t_override 3069 seconds, reset it so that it expires after t_override seconds. 3071 4.5.7. Sending (S,G) Join/Prune Messages 3073 The per-interface state-machines for (S,G) hold join state from 3074 downstream PIM routers. This state then determines whether a router 3075 needs to propagate a Join(S,G) upstream towards the source. 3077 If a router wishes to propagate a Join(S,G) upstream, it must also watch 3078 for messages on its upstream interface from other routers on that 3079 subnet, and these may modify its behavior. If it sees a Join(S,G) to 3080 the correct upstream neighbor, it should suppress its own Join(S,G). If 3081 it sees a Prune(S,G), Prune(S,G,rpt), or Prune(*,G) to the correct 3082 upstream neighbor towards S, it should be prepared to override that 3083 prune by scheduling a Join(S,G) to be sent almost immediately. Finally, 3084 if it sees the Generation ID of its upstream neighbor change, it knows 3085 that the upstream neighbor has lost state, and it should refresh the 3086 state by scheduling a Join(S,G) to be sent almost immediately. 3088 If a (S,G) Assert occurs on the upstream interface, and this changes the 3089 this router's idea of the upstream neighbor, it should be prepared to 3090 ensure that the Assert winner is aware of downstream routers by 3091 scheduling a Join(S,G) to be sent almost immediately. 3093 In addition, if MRIB changes cause the next hop towards the source to 3094 change, and either the upstream interface changes or there is no Assert 3095 winner on the upstream interface, the router should send a prune to the 3096 old next hop, and a join to the new next hop. 3098 The upstream (S,G) state-machine only contains two states: 3100 Not Joined 3101 The downstream state machines and local membership information do 3102 not indicate that the router needs to join the shortest-path tree 3103 for this (S,G). 3105 Joined 3106 The downstream state machines and local membership information 3107 indicate that the router should join the shortest-path tree for 3108 this (S,G). 3110 In addition, one timer JT(S,G) is kept which is used to trigger the 3111 sending of a Join(S,G) to the upstream next hop towards S, RPF'(S,G). 3113 Figure 8: Upstream (S,G) state-machine in tabular form 3115 +--------------------+--------------------------------------------------+ 3116 | | Event | 3117 | Prev State +-------------------------+------------------------+ 3118 | | JoinDesired(S,G) | JoinDesired(S,G) | 3119 | | ->True | ->False | 3120 +--------------------+-------------------------+------------------------+ 3121 | NotJoined (NJ) | -> J state | - | 3122 | | Send Join(S,G); | | 3123 | | Set Join Timer to | | 3124 | | t_periodic | | 3125 +--------------------+-------------------------+------------------------+ 3126 | Joined (J) | - | -> NJ state | 3127 | | | Send Prune(S,G); | 3128 | | | Set SPTbit(S,G) to | 3129 | | | FALSE; Cancel Join | 3130 | | | Timer | 3131 +--------------------+-------------------------+------------------------+ 3132 In addition, we have the following transitions which occur within the 3133 Joined state: 3135 +-----------------------------------------------------------------------+ 3136 | In Joined (J) State | 3137 +-----------------+-----------------+------------------+----------------+ 3138 | Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune | 3139 | | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to | 3140 | | | | RPF'(S,G) | 3141 +-----------------+-----------------+------------------+----------------+ 3142 | Send | Increase Join | Decrease Join | Decrease Join | 3143 | Join(S,G); Set | Timer to | Timer to | Timer to | 3144 | Join Timer to | t_joinsuppress | t_override | t_override | 3145 | t_periodic | | | | 3146 +-----------------+-----------------+------------------+----------------+ 3148 +-----------------------------------------------------------------------+ 3149 | In Joined (J) State | 3150 +-----------------+-----------------+-----------------+-----------------+ 3151 | See Prune(*,G) | RPF'(S,G) | RPF'(S,G) | RPF'(S,G) | 3152 | to RPF'(S,G) | changes not | GenID changes | changes due to | 3153 | | due to an | | an Assert | 3154 | | Assert | | | 3155 +-----------------+-----------------+-----------------+-----------------+ 3156 | Decrease Join | Send Join(S,G) | Decrease Join | Decrease Join | 3157 | Timer to | to new next | Timer to | Timer to | 3158 | t_override | hop; Send | t_override | t_override | 3159 | | Prune(S,G) to | | | 3160 | | old next hop; | | | 3161 | | Set Join Timer | | | 3162 | | to t_periodic | | | 3163 +-----------------+-----------------+-----------------+-----------------+ 3165 This state machine uses the following macro: 3167 bool JoinDesired(S,G) { 3168 return( immediate_olist(S,G) != NULL 3169 OR ( KeepaliveTimer(S,G) is running 3170 AND inherited_olist(S,G) != NULL ) ) 3171 } 3173 JoinDesired(S,G) is true when the router has forwarding state that would 3174 cause it to forward traffic for G using source tree state. The source 3175 tree state can either be as a result of active source-specific join 3176 state, or the (S,G) Keepalive Timer and active non-source-specific 3177 state. Note that although JoinDesired is true, the router's sending of a 3178 Join(S,G) message may be suppressed by another router sending a 3179 Join(S,G) onto the upstream interface. 3181 Transitions from NotJoined State 3183 When the upstream (S,G) state-machine is in NotJoined state, the 3184 following event may trigger a state transition: 3186 JoinDesired(S,G) becomes True 3187 The downstream state for (S,G) has changed so that at least 3188 one interface is in inherited_olist(S,G), making 3189 JoinDesired(S,G) become True. 3191 The upstream (S,G) state machine transitions to Joined state. 3192 Send Join(S,G) to the appropriate upstream neighbor, which is 3193 RPF'(S,G). Set the Join Timer (JT) to expire after t_periodic 3194 seconds. 3196 Transitions from Joined State 3198 When the upstream (S,G) state-machine is in Joined state, the following 3199 events may trigger state transitions: 3201 JoinDesired(S,G) becomes False 3202 The downstream state for (S,G) has changed so no interface is 3203 in inherited_olist(S,G), making JoinDesired(S,G) become False. 3205 The upstream (S,G) state machine transitions to NotJoined 3206 state. Send Prune(S,G) to the appropriate upstream neighbor, 3207 which is RPF'(S,G). Cancel the Join Timer (JT), and set 3208 SPTbit(S,G) to FALSE. 3210 Join Timer Expires 3211 The Join Timer (JT) expires, indicating time to send a 3212 Join(S,G) 3214 Send Join(S,G) to the appropriate upstream neighbor, which is 3215 RPF'(S,G). Restart the Join Timer (JT) to expire after 3216 t_periodic seconds. 3218 See Join(S,G) to RPF'(S,G) 3219 This event is only relevant if RPF_interface(S) is a shared 3220 medium. This router sees another router on RPF_interface(S) 3221 send a Join(S,G) to RPF'(S,G). This causes this router to 3222 suppress its own Join. 3224 The upstream (S,G) state machine remains in Joined state. 3226 Let t_joinsuppress be the minimum of t_suppressed and the 3227 HoldTime from the Join/Prune message triggering this event. 3228 If the Join Timer is set to expire in less than t_joinsuppress 3229 seconds, reset it so that it expires after t_joinsuppress 3230 seconds. If the Join Timer is set to expire in more than 3231 t_joinsuppress seconds, leave it unchanged. 3233 See Prune(S,G) to RPF'(S,G) 3234 This event is only relevant if RPF_interface(S) is a shared 3235 medium. This router sees another router on RPF_interface(S) 3236 send a Prune(S,G) to RPF'(S,G). As this router is in Joined 3237 state, it must override the Prune after a short random 3238 interval. 3240 The upstream (S,G) state machine remains in Joined state. If 3241 the Join Timer is set to expire in more than t_override 3242 seconds, reset it so that it expires after t_override seconds. 3244 See Prune(S,G,rpt) to RPF'(S,G) 3245 This event is only relevant if RPF_interface(S) is a shared 3246 medium. This router sees another router on RPF_interface(S) 3247 send a Prune(S,G,rpt) to RPF'(S,G). If the upstream router is 3248 an RFC 2362 compliant PIM router, then the Prune(S,G,rpt) will 3249 cause it to stop forwarding. For backwards compatibility, 3250 this router should override the prune so that forwarding 3251 continues. 3253 The upstream (S,G) state machine remains in Joined state. If 3254 the Join Timer is set to expire in more than t_override 3255 seconds, reset it so that it expires after t_override seconds. 3257 See Prune(*,G) to RPF'(S,G) 3258 This event is only relevant if RPF_interface(S) is a shared 3259 medium. This router sees another router on RPF_interface(S) 3260 send a Prune(*,G) to RPF'(S,G). If the upstream router is an 3261 RFC 2362 compliant PIM router, then the Prune(*,G) will cause 3262 it to stop forwarding. For backwards compatibility, this 3263 router should override the prune so that forwarding continues. 3265 The upstream (S,G) state machine remains in Joined state. If 3266 the Join Timer is set to expire in more than t_override 3267 seconds, reset it so that it expires after t_override seconds. 3269 RPF'(S,G) changes due to an Assert 3270 The current next hop towards S changes due to an Assert(S,G) 3271 on the RPF_interface(S). 3273 The upstream (S,G) state machine remains in Joined state. If 3274 the Join Timer is set to expire in more than t_override 3275 seconds, reset it so that it expires after t_override seconds. 3276 If the Join Timer is set to expire in less than t_override 3277 seconds, leave it unchanged. 3279 RPF'(S,G) changes not due to an Assert 3280 An event occurred which caused the next hop towards S to 3281 change. Note that this transition does not occur if an Assert 3282 is active and the upstream interface does not change. 3284 The upstream (S,G) state machine remains in Joined state. 3285 Send Join(S,G) to the new upstream neighbor which is the new 3286 value of RPF'(S,G). Send Prune(S,G) to the old upstream 3287 neighbor, which is the old value of RPF'(S,G). Set the Join 3288 Timer (JT) to expire after t_periodic seconds. 3290 RPF'(S,G) GenID changes 3291 The Generation ID of the router that is RPF'(S,G) changes. 3292 This normally means that this neighbor has lost state, and so 3293 the state must be refreshed. 3295 The upstream (S,G) state machine remains in Joined state. If 3296 the Join Timer is set to expire in more than t_override 3297 seconds, reset it so that it expires after t_override seconds. 3299 4.5.8. (S,G,rpt) Periodic Messages 3301 (S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP tree 3302 with the RPT bit set, either to modify the results of (*,G) Joins, or to 3303 override the behavior of other upstream LAN peers. The next section 3304 describes the rules for sending triggered messages. This section 3305 describes the rules for including a Prune(S,G,rpt) message with a 3306 Join(*,G). 3308 When a router is going to send a Join(*,G), it should use the following 3309 pseudocode, for each (S,G) for which it has state, to decide whether to 3310 include a Prune(S,G,rpt) in the compound Join/Prune message: 3312 if( SPTbit(S,G) == TRUE ) { 3313 # Note: If receiving (S,G) on the SPT, we only prune off the 3314 # shared tree if the RPF neighbors differ. 3315 if( RPF'(*,G) != RPF'(S,G) ) { 3316 add Prune(S,G,rpt) to compound message 3317 } 3318 } else if ( inherited_olist(S,G,rpt) == NULL ) { 3319 # Note: all (*,G) olist interfaces received RPT prunes for (S,G). 3320 add Prune(S,G,rpt) to compound message 3321 } else if ( RPF'(*,G) != RPF'(S,G,rpt) { 3322 # Note: we joined the shared tree, but there was an (S,G) assert and 3323 # the source tree RPF neighbor is different. 3324 add Prune(S,G,rpt) to compound message 3325 } 3327 Note that Join(S,G,rpt) is not normally sent as a periodic message, but 3328 only as a triggered message. 3330 4.5.9. State Machine for (S,G,rpt) Triggered Messages 3332 The state machine for (S,G,rpt) triggered messages is required per-(S,G) 3333 when there is (*,G) or (*,*,RP) join state at a router, and the router 3334 or any of its upstream LAN peers wishes to prune S off the RP tree. 3336 There are three states in the state-machine. One of the states is when 3337 there is neither (*,G) nor (*,*,RP(G)) join state at this router. If 3338 there is (*,G) or (*,*,RP(G)) join state at the router, then the state 3339 machine must be at one of the other two states. The three states are: 3341 Pruned(S,G,rpt) 3342 (*,G) or (*,*,RP(G)) Joined, but (S,G,rpt) pruned 3344 NotPruned(S,G,rpt) 3345 (*,G) or (*,*,RP(G)) Joined, and (S,G,rpt) not pruned 3347 RPTNotJoined(G) 3348 neither (*,G) nor (*,*,RP(G)) has been joined. 3350 In addition, there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which is 3351 used to delay triggered Join(S,G,rpt) messages to prevent implosions of 3352 triggered messages. 3354 Figure 9: Upstream (S,G,rpt) state-machine for triggered messages in 3355 tabular form 3357 +---------------++-------------------------------------------------------------+ 3358 | || Event | 3359 | ++---------------+---------------+--------------+--------------+ 3360 |Prev State || PruneDesired | PruneDesired | RPTJoin | inherited_ | 3361 | || (S,G,rpt) | (S,G,rpt) | Desired(G) | olist | 3362 | || ->True | ->False | ->False | (S,G,rpt) | 3363 | || | | | ->non-NULL | 3364 +---------------++---------------+---------------+--------------+--------------+ 3365 |RPTNotJoined || -> P state | - | - | -> NP state | 3366 |(G) (NJ) || | | | | 3367 +---------------++---------------+---------------+--------------+--------------+ 3368 |Pruned || - | -> NP state | -> NJ state | - | 3369 |(S,G,rpt) (P) || | Send Join | | | 3370 | || | (S,G,rpt) | | | 3371 +---------------++---------------+---------------+--------------+--------------+ 3372 |NotPruned || -> P state | - | -> NJ state | - | 3373 |(S,G,rpt) || Send Prune | | Cancel OT | | 3374 |(NP) || (S,G,rpt); | | | | 3375 | || Cancel OT | | | | 3376 +---------------++---------------+---------------+--------------+--------------+ 3377 Additionally, we have the following transitions within the 3378 NotPruned(S,G,rpt) state which are all used for prune override behavior. 3380 +-----------------------------------------------------------------------+ 3381 | In NotPruned(S,G,rpt) State | 3382 +-----------+--------------+--------------+--------------+--------------+ 3383 |Override | See Prune | See Join | See Prune | RPF' | 3384 |Timer | (S,G,rpt) to | (S,G,rpt) to | (S,G) to | (S,G,rpt) -> | 3385 |expires | RPF' | RPF' | RPF' | RPF' (*,G) | 3386 | | (S,G,rpt) | (S,G,rpt) | (S,G,rpt) | | 3387 +-----------+--------------+--------------+--------------+--------------+ 3388 |Send Join | OT = min(OT, | Cancel OT | OT = min(OT, | OT = min(OT, | 3389 |(S,G,rpt); | t_override) | | t_override) | t_override) | 3390 |Leave OT | | | | | 3391 |unset | | | | | 3392 +-----------+--------------+--------------+--------------+--------------+ 3394 Note that the min function in the above state machine considers a non- 3395 running timer to have an infinite value (e.g. min(not-running, 3396 t_override) = t_override). 3398 This state machine uses the following macros: 3400 bool RPTJoinDesired(G) { 3401 return (JoinDesired(*,G) OR JoinDesired(*,*,RP(G))) 3402 } 3404 RPTJoinDesired(G) is true when the router has forwarding state that 3405 would cause it to forward traffic for G using either (*,G) or (*,*,RP) 3406 shared tree state. 3408 bool PruneDesired(S,G,rpt) { 3409 return ( RPTJoinDesired(G) AND 3410 ( inherited_olist(S,G,rpt) == NULL 3411 OR (SPTbit(S,G)==TRUE 3412 AND (RPF'(*,G) != RPF'(S,G)) ))) 3413 } 3415 PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true. If 3416 RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true if either 3417 there are no outgoing interfaces that S would be forwarded on, or if the 3418 router has active (S,G) forwarding state but RPF'(*,G) != RPF'(S,G). 3420 The state machine contains the following transition events: 3422 See Join(S,G,rpt) to RPF'(S,G,rpt) 3423 This event is only relevant in the "Not Pruned" state. 3425 The router sees a Join(S,G,rpt) from someone else to RPF'(S,G,rpt), 3426 which is the correct upstream neighbor. If we're in "NotPruned" 3427 state and the (S,G,rpt) Override Timer is running, then this is 3428 because we have been triggered to send our own Join(S,G,rpt) to 3429 RPF'(S,G,rpt). Someone else beat us to it, so there's no need to 3430 send our own Join. 3432 The action is to cancel the Override Timer. 3434 See Prune(S,G,rpt) to RPF'(S,G,rpt) 3435 This event is only relevant in the "NotPruned" state. 3437 The router sees a Prune(S,G,rpt) from someone else to to 3438 RPF'(S,G,rpt), which is the correct upstream neighbor. If we're in 3439 the "NotPruned" state, then we want to continue to receive traffic 3440 from S destined for G, and that traffic is being supplied by 3441 RPF'(S,G,rpt). Thus we need to override the Prune. 3443 The action is to set the (S,G,rpt) Override Timer to the randomized 3444 prune-override interval, t_override. However if the Override Timer 3445 is already running, we only set the timer if doing so would set it 3446 to a lower value. At the end of this interval, if no-one else has 3447 sent a Join, then we will do so. 3449 See Prune(S,G) to RPF'(S,G,rpt) 3450 This event is only relevant in the "NotPruned" state. 3452 This transition and action are the same as the above transition and 3453 action, except that the Prune does not have the RPT bit set. This 3454 transition is necessary to be compatible with routers implemented 3455 from RFC2362 that don't maintain separate (S,G) and (S,G,rpt) 3456 state. 3458 The (S,G,rpt) prune Override Timer expires 3459 This event is only relevant in the "NotPruned" state. 3461 When the Override Timer expires, we must send a Join(S,G,rpt) to 3462 RPF'(S,G,rpt) to override the Prune message that caused the timer 3463 to be running. We only send this if RPF'(S,G,rpt) equals RPF'(*,G) 3464 - if this were not the case, then the Join might be sent to a 3465 router that does not have (*,G) or (*,*,RP(G)) Join state, and so 3466 the behavior would not be well defined. If RPF'(S,G,rpt) is not 3467 the same as RPF'(*,G), then it may stop forwarding S. However, if 3468 this happens, then the router will send an AssertCancel(S,G), which 3469 would then cause RPF'(S,G,rpt) to become equal to RPF'(*,G) (see 3470 below). 3472 RPF'(S,G,rpt) changes to become equal to RPF'(*,G) 3473 This event is only relevant in the "NotPruned" state. 3475 RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G) 3476 Assert has happened, which means that traffic from S is arriving on 3477 the SPT, and so Prune(S,G,rpt) will have been sent to RPF'(*,G). 3478 When RPF'(S,G,rpt) changes to become equal to RPF'(*,G), we need to 3479 trigger a Join(S,G,rpt) to RPF'(*,G) to cause that router to start 3480 forwarding S again. 3482 The action is to set the (S,G,rpt) Override Timer to the randomized 3483 prune-override interval t_override. However if the timer is 3484 already running, we only set the timer if doing so would set it to 3485 a lower value. At the end of this interval, if no-one else has 3486 sent a Join, then we will do so. 3488 PruneDesired(S,G,rpt)->TRUE 3489 See macro above. This event is relevant in the "NotPruned" and 3490 "RPTNotJoined(G)" states. 3492 The router wishes to receive traffic for G, but does not wish to 3493 receive traffic from S destined for G. This causes the router to 3494 transition into the Pruned state. 3496 If the router was previously in NotPruned state, then the action is 3497 to send a Prune(S,G,rpt) to RPF'(S,G,rpt), and to cancel the 3498 Override Timer. If the router was previously in RPTNotJoined(G) 3499 state, then there is no need to trigger an action in this state 3500 machine because sending a Prune(S,G,rpt) is handled by the rules 3501 for sending the Join(*,G) or Join(*,*,RP). 3503 PruneDesired(S,G,rpt)->FALSE 3504 See macro above. This transition is only relevant in the "Pruned" 3505 state. 3507 If the router is in the Pruned(S,G,rpt) state, and 3508 PruneDesired(S,G,rpt) changes to FALSE, this could be because the 3509 router no longer has RPTJoinDesired(G) true, or it now wishes to 3510 receive traffic from S again. If it is the former, then this 3511 transition should not happen, but instead the 3512 "RPTJoinDesired(G)->FALSE" transition should happen. Thus this 3513 transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE 3514 AND RPTJoinDesired(G)==TRUE" 3516 The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt). 3518 RPTJoinDesired(G)->FALSE 3519 This event is relevant in the "Pruned" and "NotPruned" states. 3521 The router no longer wishes to receive any traffic destined for G 3522 on the RP Tree. This causes a transition to the RPTNotJoined(G) 3523 state, and the Override Timer is canceled if it was running. Any 3524 further actions are handled by the appropriate upstream state 3525 machine for (*,G) or (*,*,RP). 3527 inherited_olist(S,G,rpt) becomes non-NULL 3528 This transition is only relevant in the RPTNotJoined(G) state. 3530 The router has joined the RP tree (handled by the (*,G) or (*,*,RP) 3531 upstream state machine as appropriate), and wants to receive 3532 traffic from S. This does not trigger any events in this state 3533 machine, but causes a transition to the NotPruned(S,G,rpt) state. 3535 4.5.10. Background: (*,*,RP) and (S,G,rpt) interaction 3537 In sections 4.5.8 and 4.5.9 the mechanisms for sending periodic and 3538 triggered (S,G,rpt) messages are described. The astute reader will note 3539 that periodic Prune(S,G,rpt) messages are only sent in PIM Join/Prune 3540 messages containing a Join(*,G), whereas it is possible for a triggered 3541 Prune(S,G,rpt) message to be sent when the router has no (*,G) join 3542 state. This may seem like a contradiction, but in fact it is 3543 intentional, and is a side effect of not optimizing (*,*,RP) behavior. 3545 We first note that reception of a Join(*,*,RP) by itself does not cancel 3546 (S,G,rpt) prune state on that interface, whereas receiving a Join(*,G) 3547 by itself does cancel (S,G,rpt) prune state on that interface. 3548 Similarly, reception of a Prune(*,G) on an interface with (*,*,RP) join 3549 state does not by itself prevent forwarding of G using the (*,*,RP) 3550 state - this is because a Prune(*,G) only serves to cancel (*,G) join 3551 state. Conceptually (*,*,RP) state functions "above" the normal (*,G) 3552 and (S,G) mechanisms, and so neither Join(*,*,RP) or Prune(*,*,RP) 3553 messages affect any other state. 3555 The upshot of this is that to prevent forwarding (S,G) on (*,*,RP) 3556 state, a Prune(S,G,rpt) must be used. 3558 We also note that for historical reasons there is no Assert(*,*,RP) 3559 message, so any forwarding contention is resolved using Assert(*,G) 3560 messages. 3562 We now need to consider the interaction between (*,*,RP) state and (*,G) 3563 state. If there is a need for an assert between two upstream routers on 3564 a LAN, we need to ensure that the correct thing happens for all 3565 combinations of (*,*,RP) and (*,G) forwarding state. As there is no 3566 Assert(*,*,RP) message, no router can tell whether the assert winner has 3567 (*,*,RP) state or (*,G) state. Thus a downstream router has to treat 3568 the two the same and send its periodic Prune(S,G,rpt) messages to 3569 RPF'(*,G). 3571 To avoid needing to specify all the complex override rules between 3572 (*,*,RP), (*,G) and (S,G,rpt), we simply require that to prune (S,G) off 3573 the (*,*,RP) tree, a Join(*,G) must also be sent. 3575 If a router is receiving on (*,*,RP) state, and has not yet had (*,G) 3576 state instantiated, it may still need to send a triggered Join(S,G,rpt) 3577 to override a Prune(S,G,rpt) that it sees directed to RPF'(*,G) on its 3578 upstream interface. Hence triggered (S,G,rpt) messages may be sent when 3579 JoinDesired(*,G) is false but JoinDesired(*,*,RP) is true. 3581 Finally we note that there is an unoptimized case when the upstream 3582 router on a LAN already has (*,G) join and (S,G,rpt) prune state caused 3583 by an existing downstream router. If at this time a new Join(*,*,RP) is 3584 sent to the upstream router from a different downstream router, this 3585 will not override the (S,G,rpt) prune state at the upstream router. The 3586 override will not occur until the next time the original downstream 3587 router resends its Prune(S,G,rpt). This case was considered to be not 3588 worth optimizing, as (*,*,RP) state is generally very long lived, and so 3589 any minor delays in getting traffic to a new PMBR seem unimportant. 3591 4.6. PIM Assert Messages 3593 Where multiple PIM routers peer over a shared LAN it is possible for 3594 more than one upstream router to have valid forwarding state for a 3595 packet, which can lead to packet duplication (see Section 3 "Multi- 3596 access LANs"). PIM does not attempt to prevent this from occurring. 3597 Instead it detects when this has happened and elects a single forwarder 3598 amongst the upstream routers to prevent further duplication. This 3599 election is performed using PIM Assert messages. Assert messages are 3600 also received by downstream routers on the LAN, and these cause 3601 subsequent Join/Prune messages to be sent to the upstream router that 3602 won the Assert. 3604 In general, a PIM Assert message should only be accepted for processing 3605 if it comes from a known PIM neighbor. A PIM router hears about PIM 3606 neighbors through PIM Hello messages. If a router receives an Assert 3607 message from a particular IP source address and it has not seen a PIM 3608 Hello message from that source address, then the Assert message SHOULD 3609 be discarded without further processing. In addition, if the Hello 3610 message from a neighbor was authenticated using IPsec AH (see Section 3611 6.3) then all Assert messages from that neighbor MUST also be 3612 authenticated using IPsec AH. 3614 We note that some older PIM implementations incorrectly fail to send 3615 Hello messages on point-to-point interfaces, so we also RECOMMEND that a 3616 configuration option be provided to allow interoperation with such older 3617 routers, but that this configuration option SHOULD NOT be enabled by 3618 default. 3620 4.6.1. (S,G) Assert Message State Machine 3622 The (S,G) Assert state machine for interface I is shown in Figure 10. 3623 There are three states: 3625 NoInfo (NI) 3626 This router has no (S,G) assert state on interface I. 3628 I am Assert Winner (W) 3629 This router has won an (S,G) assert on interface I. It is now 3630 responsible for forwarding traffic from S destined for G out of 3631 interface I. Irrespective of whether it is the DR for I, while a 3632 router is the assert winner, it is also responsible for forwarding 3633 traffic onto I on behalf of local hosts on I that have made 3634 membership requests that specifically refer to S (and G). 3636 I am Assert Loser (L) 3637 This router has lost an (S,G) assert on interface I. It must not 3638 forward packets from S destined for G onto interface I. If it is 3639 the DR on I, it is no longer responsible for forwarding traffic 3640 onto I to satisfy local hosts with membership requests that 3641 specifically refer to S and G. 3643 In addition, there is also an Assert Timer (AT) that is used to time out 3644 asserts on the assert losers and to resend asserts on the assert winner. 3646 Figure 10: Per-interface (S,G) Assert State-machine in tabular form 3648 +-----------------------------------------------------------------------+ 3649 | In NoInfo (NI) State | 3650 +---------------+-------------------+------------------+----------------+ 3651 | Receive | Receive Assert | Data arrives | Receive | 3652 | Inferior | with RPTbit | from S to G on | Preferred | 3653 | Assert with | set and | I and | Assert with | 3654 | RPTbit clear | CouldAssert | CouldAssert | RPTbit clear | 3655 | and | (S,G,I) | (S,G,I) | and AssTrDes | 3656 | CouldAssert | | | (S,G,I) | 3657 | (S,G,I) | | | | 3658 +---------------+-------------------+------------------+----------------+ 3659 | -> W state | -> W state | -> W state | -> L state | 3660 | [Actions A1] | [Actions A1] | [Actions A1] | [Actions A6] | 3661 +---------------+-------------------+------------------+----------------+ 3663 +-----------------------------------------------------------------------+ 3664 | In I Am Assert Winner (W) State | 3665 +----------------+------------------+-----------------+-----------------+ 3666 | Assert Timer | Receive | Receive | CouldAssert | 3667 | Expires | Inferior | Preferred | (S,G,I) -> | 3668 | | Assert | Assert | FALSE | 3669 +----------------+------------------+-----------------+-----------------+ 3670 | -> W state | -> W state | -> L state | -> NI state | 3671 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3672 +----------------+------------------+-----------------+-----------------+ 3674 +-------------------------------------------------------------------------+ 3675 | In I Am Assert Loser (L) State | 3676 +-------------+--------------+--------------+--------------+--------------+ 3677 |Receive | Receive | Receive | Assert Timer | Current | 3678 |Preferred | Acceptable | Inferior | Expires | Winner's | 3679 |Assert | Assert from | Assert from | | GenID | 3680 | | Current | Current | | Changes or | 3681 | | Winner | Winner | | NLT Expires | 3682 +-------------+--------------+--------------+--------------+--------------+ 3683 |-> L state | -> L state | -> NI state | -> NI state | -> NI state | 3684 |[Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 3685 +-------------+--------------+--------------+--------------+--------------+ 3686 +-----------------------------------------------------------------------+ 3687 | In I Am Assert Loser (L) State | 3688 +----------------+-----------------+-------------------+----------------+ 3689 | AssTrDes | my_metric -> | RPF_interface | Receive | 3690 | (S,G,I) -> | better than | (S) stops | Join(S,G) on | 3691 | FALSE | winner's | being I | interface I | 3692 | | metric | | | 3693 +----------------+-----------------+-------------------+----------------+ 3694 | -> NI state | -> NI state | -> NI state | -> NI State | 3695 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 3696 +----------------+-----------------+-------------------+----------------+ 3698 Note that for reasons of compactness, "AssTrDes(S,G,I)" is used in the 3699 state-machine table to refer to AssertTrackingDesired(S,G,I). 3701 Terminology: 3702 A "preferred assert" is one with a better metric than the current 3703 winner. 3705 An "acceptable assert" is one that has a better metric than 3706 my_assert_metric(S,G,I). 3708 An "inferior assert" is one with a worse metric than 3709 my_assert_metric(S,G,I). 3710 The state machine uses the following macros: 3712 CouldAssert(S,G,I) = 3713 SPTbit(S,G)==TRUE 3714 AND (RPF_interface(S) != I) 3715 AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 3716 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3717 (-) lost_assert(*,G) 3718 (+) joins(S,G) (+) pim_include(S,G) ) ) 3720 CouldAssert(S,G,I) is true for downstream interfaces which would be in 3721 the inherited_olist(S,G) if (S,G) assert information was not taken into 3722 account. 3724 AssertTrackingDesired(S,G,I) = 3725 (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 3726 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3727 (-) lost_assert(*,G) 3728 (+) joins(S,G) ) ) 3729 OR (local_receiver_include(S,G,I) == TRUE 3730 AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me))) 3731 OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == TRUE)) 3732 OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == TRUE) 3733 AND (SPTbit(S,G) == FALSE)) 3735 AssertTrackingDesired(S,G,I) is true on any interface in which an (S,G) 3736 assert might affect our behavior. 3738 The first three lines of AssertTrackingDesired account for (*,G) join 3739 and local membership information received on I that might cause the 3740 router to be interested in asserts on I. 3742 The 4th line accounts for (S,G) join information received on I that 3743 might cause the router to be interested in asserts on I. 3745 The 5th and 6th lines account for (S,G) local membership information on 3746 I. Note that we can't use the pim_include(S,G) macro since it uses 3747 lost_assert(S,G,I) and would result in the router forgetting that it 3748 lost an assert if the only reason it was interested was local 3749 membership. The AssertWinner(S,G,I) check forces an assert winner to 3750 keep on being responsible for forwarding as long as local receivers are 3751 present. Removing this check would make the assert winner give up 3752 forwarding as soon as the information that originally caused it to 3753 forward went away and the task of forwarding for local receivers would 3754 revert back to the DR. 3756 The last three lines account for the fact that a router must keep track 3757 of assert information on upstream interfaces in order to send joins and 3758 prunes to the proper neighbor. 3760 Transitions from NoInfo State 3762 When in NoInfo state, the following events may trigger transitions: 3764 Receive Inferior Assert with RPTbit cleared AND 3765 CouldAssert(S,G,I)==TRUE 3766 An assert is received for (S,G) with the RPT bit cleared that 3767 is inferior to our own assert metric. The RPT bit cleared 3768 indicates that the sender of the assert had (S,G) forwarding 3769 state on this interface. If the assert is inferior to our 3770 metric, then we must also have (S,G) forwarding state (i.e. 3771 CouldAssert(S,G,I)==TRUE) as (S,G) asserts beat (*,G) asserts, 3772 and so we should be the assert winner. We transition to the 3773 "I am Assert Winner" state, and perform Actions A1 (below). 3775 Receive Assert with RPTbit set AND CouldAssert(S,G,I)==TRUE 3776 An assert is received for (S,G) on I with the RPT bit set 3777 (it's a (*,G) assert). CouldAssert(S,G,I) is TRUE only if we 3778 have (S,G) forwarding state on this interface, so we should be 3779 the assert winner. We transition to the "I am Assert Winner" 3780 state, and perform Actions A1 (below). 3782 An (S,G) data packet arrives on interface I, AND 3783 CouldAssert(S,G,I)==TRUE 3784 An (S,G) data packet arrived on an downstream interface which 3785 is in our (S,G) outgoing interface list. We optimistically 3786 assume that we will be the assert winner for this (S,G), and 3787 so we transition to the "I am Assert Winner" state, and 3788 perform Actions A1 (below) which will initiate the assert 3789 negotiation for (S,G). 3791 Receive Preferred Assert with RPT bit clear AND 3792 AssertTrackingDesired(S,G,I)==TRUE 3793 We're interested in (S,G) Asserts, either because I is a 3794 downstream interface for which we have (S,G) or (*,G) 3795 forwarding state, or because I is the upstream interface for S 3796 and we have (S,G) forwarding state. The received assert has a 3797 better metric than our own, so we do not win the Assert. We 3798 transition to "I am Assert Loser" and perform actions A6 3799 (below). 3801 Transitions from "I am Assert Winner" State 3803 When in "I am Assert Winner" state, the following events trigger 3804 transitions: 3806 Assert Timer Expires 3807 The (S,G) Assert Timer expires. As we're in the Winner state, 3808 then we must still have (S,G) forwarding state that is 3809 actively being kept alive. We re-send the (S,G) Assert and 3810 restart the Assert Timer (Action A3 below). Note that the 3811 assert winner's Assert Timer is engineered to expire shortly 3812 before timers on assert losers; this prevents unnecessary 3813 thrashing of the forwarder and periodic flooding of duplicate 3814 packets. 3816 Receive Inferior Assert 3817 We receive an (S,G) assert or (*,G) assert mentioning S that 3818 has a worse metric than our own. Whoever sent the assert is 3819 in error, and so we re-send an (S,G) Assert, and restart the 3820 Assert Timer (Action A3 below). 3822 Receive Preferred Assert 3823 We receive an (S,G) assert that has a better metric than our 3824 own. We transition to "I am Assert Loser" state and perform 3825 actions A2 (below). Note that this may affect the value of 3826 JoinDesired(S,G) and PruneDesired(S,G,rpt) which could cause 3827 transitions in the upstream (S,G) or (S,G,rpt) state machines. 3829 CouldAssert(S,G,I) -> FALSE 3830 Our (S,G) forwarding state or RPF interface changed so as to 3831 make CouldAssert(S,G,I) become false. We can no longer 3832 perform the actions of the assert winner, and so we transition 3833 to NoInfo state and perform actions A4 (below). This includes 3834 sending a "canceling assert" with an infinite metric. 3836 Transitions from "I am Assert Loser" State 3838 When in "I am Assert Loser" state, the following transitions can occur: 3840 Receive Preferred Assert 3841 We receive an assert that is better than that of the current 3842 assert winner. We stay in Loser state, and perform actions A2 3843 below. 3845 Receive Acceptable Assert from Current Winner 3846 We receive an assert from the current assert winner that is 3847 better than our own metric for this (S,G) (although the metric 3848 may be worse than the winner's previous metric). We stay in 3849 Loser state, and perform actions A2 below. 3851 Receive Inferior Assert from Current Winner 3852 We receive an assert from the current assert winner that is 3853 worse than our own metric for this group (typically the 3854 winner's metric became worse). We transition to NoInfo state, 3855 deleting the (S,G) assert information and allowing the normal 3856 PIM Join/Prune mechanisms to operate. Usually we will 3857 eventually re-assert and win when data packets from S have 3858 started flowing again. 3860 Assert Timer Expires 3861 The (S,G) Assert Timer expires. We transition to NoInfo 3862 state, deleting the (S,G) assert information (action A5 3863 below). 3865 Current Winner's GenID Changes or NLT Expires 3866 The Neighbor Liveness Timer associated with the current winner 3867 expires or we receive a Hello message from the current winner 3868 reporting a different GenID from the one it previously 3869 reported. This indicates that the current winner's interface 3870 or router has gone down (and may have come back up), and so we 3871 must assume it no longer knows it was the winner. We 3872 transition to the NoInfo state, deleting this (S,G) assert 3873 information (action A5 below). 3875 AssertTrackingDesired(S,G,I)->FALSE 3876 AssertTrackingDesired(S,G,I) becomes FALSE. Our forwarding 3877 state has changed so that (S,G) Asserts on interface I are no 3878 longer of interest to us. We transition to the NoInfo state, 3879 deleting the (S,G) assert information. 3881 My metric becomes better than the assert winner's metric 3882 my_assert_metric(S,G,I) has changed so that now my assert 3883 metric for (S,G) is better than the metric we have stored for 3884 current assert winner. This might happen the underlying 3885 routing metric changes, or when CouldAssert(S,G,I) becomes 3886 true; for example, when SPTbit(S,G) becomes true. We 3887 transition to NoInfo state, delete this (S,G) assert state 3888 (action A5 below), and allow the normal PIM Join/Prune 3889 mechanisms to operate. Usually we will eventually re-assert 3890 and win when data packets from S have started flowing again. 3892 RPF_interface(S) stops being interface I 3893 Interface I used to be the RPF interface for S, and now it is 3894 not. We transition to NoInfo state, deleting this (S,G) 3895 assert state (action A5 below). 3897 Receive Join(S,G) on Interface I 3898 We receive a Join(S,G) that has the Upstream Neighbor Address 3899 field set to one my IP address on interface I. The action is 3900 to transition to NoInfo state, and delete this (S,G) assert 3901 state (action A5 below), and allow the normal PIM Join/Prune 3902 mechanisms to operate. If whoever sent the Join was in error, 3903 then the normal assert mechanism will eventually re-apply and 3904 we will lose the assert again. However whoever sent the 3905 assert may know that the previous assert winner has died, and 3906 so we may end up being the new forwarder. 3908 (S,G) Assert State-machine Actions 3910 A1: Send Assert(S,G) 3911 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 3912 Store self as AssertWinner(S,G,I) 3913 Store spt_assert_metric(S,I) as AssertWinnerMetric(S,G,I) 3915 A2: Store new assert winner as AssertWinner(S,G,I) and assert 3916 winner metric as AssertWinnerMetric(S,G,I). 3917 Set Assert Timer to Assert_Time 3919 A3: Send Assert(S,G) 3920 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 3922 A4: Send AssertCancel(S,G) 3923 Delete assert info (AssertWinner(S,G,I) and 3924 AssertWinnerMetric(S,G,I) will then return their default 3925 values). 3927 A5: Delete assert info (AssertWinner(S,G,I) and 3928 AssertWinnerMetric(S,G,I) will then return their default 3929 values). 3931 A6: Store new assert winner as AssertWinner(S,G,I) and assert 3932 winner metric as AssertWinnerMetric(S,G,I). 3933 Set Assert Timer to Assert_Time 3934 If I is RPF_interface(S) set SPTbit(S,G) to TRUE. 3936 Note that some of these actions may cause the value of JoinDesired(S,G), 3937 PruneDesired(S,G,rpt), or RPF'(S,G) to change, which could cause further 3938 transitions in other state machines. 3940 4.6.2. (*,G) Assert Message State Machine 3942 The (*,G) Assert state-machine for interface I is shown in Figure 11. 3943 There are three states: 3945 NoInfo (NI) 3946 This router has no (*,G) assert state on interface I. 3948 I am Assert Winner (W) 3949 This router has won an (*,G) assert on interface I. It is now 3950 responsible for forwarding traffic destined for G onto interface I 3951 with the exception of traffic for which it has (S,G) "I am Assert 3952 Loser" state. Irrespective of whether it is the DR for I, it is 3953 also responsible for handling the membership requests for G from 3954 local hosts on I. 3956 I am Assert Loser (L) 3957 This router has lost an (*,G) assert on interface I. It must not 3958 forward packets for G onto interface I with the exception of 3959 traffic from sources for which is has (S,G) "I am Assert Winner" 3960 state. If it is the DR, it is no longer responsible for handling 3961 the membership requests for group G from local hosts on I. 3963 In addition, there is also an Assert Timer (AT) that is used to time out 3964 asserts on the assert losers and to resend asserts on the assert winner. 3966 When an Assert message is received with a source address other than 3967 zero, a PIM implementation must first match it against the possible 3968 events in the (S,G) assert state machine and process any transitions and 3969 actions, before considering whether the Assert message matches against 3970 the (*,G) assert state machine. 3972 It is important to note that NO TRANSITION CAN OCCUR in the (*,G) state 3973 machine as a result of receiving an Assert message unless the (S,G) 3974 assert state machine for the relevant S and G is in the "NoInfo" state 3975 after the (S,G) state machine has processed the message. Also NO 3976 TRANSITION CAN OCCUR in the (*,G) state machine as a result of receiving 3977 an assert message if that message triggers any change of state in the 3978 (S,G) state machine. 3980 For example, if both the (S,G) and (*,G) assert state machines where in 3981 the NoInfo state when an Assert message arrives, and the message causes 3982 the (S,G) state machine to transition to either "W" or "L" state, then 3983 the assert would not be processed by the (*,G) assert state machine. 3985 Another example: if the (S,G) assert state machine is in "L" state when 3986 an assert message is received, and the assert metric in the message is 3987 worse than my_assert_metric(S,G,I), then the (S,G) assert state machine 3988 will transition to NoInfo state. In such a case if the (*,G) assert 3989 state machine were in NoInfo state, it might appear that it would 3990 transition to "W" state, but this is not the case because this message 3991 already triggered a transition in the (S,G) assert state machine. 3993 Figure 11: Per-interface (*,G) Assert State-machine in tabular form 3995 +-----------------------------------------------------------------------+ 3996 | In NoInfo (NI) State | 3997 +-----------------------+-----------------------+-----------------------+ 3998 | Receive Inferior | Data arrives for G | Receive Preferred | 3999 | Assert with RPTbit | on I and | Assert with RPTbit | 4000 | set and | CouldAssert | set and AssTrDes | 4001 | CouldAssert(*,G,I) | (*,G,I) | (*,G,I) | 4002 +-----------------------+-----------------------+-----------------------+ 4003 | -> W state | -> W state | -> L state | 4004 | [Actions A1] | [Actions A1] | [Actions A2] | 4005 +-----------------------+-----------------------+-----------------------+ 4007 +-----------------------------------------------------------------------+ 4008 | In I Am Assert Winner (W) State | 4009 +----------------+------------------+-----------------+-----------------+ 4010 | Assert Timer | Receive | Receive | CouldAssert | 4011 | Expires | Inferior | Preferred | (*,G,I) -> | 4012 | | Assert | Assert | FALSE | 4013 +----------------+------------------+-----------------+-----------------+ 4014 | -> W state | -> W state | -> L state | -> NI state | 4015 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 4016 +----------------+------------------+-----------------+-----------------+ 4018 +-------------------------------------------------------------------------+ 4019 | In I Am Assert Loser (L) State | 4020 +-------------+--------------+--------------+--------------+--------------+ 4021 |Receive | Receive | Receive | Assert Timer | Current | 4022 |Preferred | Acceptable | Inferior | Expires | Winner's | 4023 |Assert | Assert from | Assert from | | GenID | 4024 | | Current | Current | | Changes or | 4025 | | Winner | Winner | | NLT Expires | 4026 +-------------+--------------+--------------+--------------+--------------+ 4027 |-> L state | -> L state | -> NI state | -> NI state | -> NI state | 4028 |[Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 4029 +-------------+--------------+--------------+--------------+--------------+ 4030 +-----------------------------------------------------------------------+ 4031 | In I Am Assert Loser (L) State | 4032 +----------------+----------------+------------------+------------------+ 4033 | AssTrDes | my_metric -> | RPF_interface | Receive | 4034 | (*,G,I) -> | better than | (RP(G)) stops | Join(*,G) or | 4035 | FALSE | Winner's | being I | Join | 4036 | | metric | | (*,*,RP(G)) on | 4037 | | | | Interface I | 4038 +----------------+----------------+------------------+------------------+ 4039 | -> NI state | -> NI state | -> NI state | -> NI State | 4040 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 4041 +----------------+----------------+------------------+------------------+ 4043 The state machine uses the following macros: 4045 CouldAssert(*,G,I) = 4046 ( I in ( joins(*,*,RP(G)) (+) joins(*,G) 4047 (+) pim_include(*,G)) ) 4048 AND (RPF_interface(RP(G)) != I) 4050 CouldAssert(*,G,I) is true on downstream interfaces for which we have 4051 (*,*,RP(G)) or (*,G) join state, or local members that requested any 4052 traffic destined for G. 4054 AssertTrackingDesired(*,G,I) = 4055 CouldAssert(*,G,I) 4056 OR (local_receiver_include(*,G,I)==TRUE 4057 AND (I_am_DR(I) OR AssertWinner(*,G,I) == me)) 4058 OR (RPF_interface(RP(G)) == I AND RPTJoinDesired(G)) 4060 AssertTrackingDesired(*,G,I) is true on any interface on which an (*,G) 4061 assert might affect our behavior. 4063 Note that for reasons of compactness, "AssTrDes(*,G,I)" is used in the 4064 state-machine table to refer to AssertTrackingDesired(*,G,I). 4066 Terminology: 4067 A "preferred assert" is one with a better metric than the current 4068 winner. 4070 An "acceptable assert" is one that has a better metric than 4071 my_assert_metric(S,G,I). 4073 An "inferior assert" is one with a worse metric than 4074 my_assert_metric(S,G,I). 4076 Transitions from NoInfo State 4078 When in NoInfo state, the following events trigger transitions, but only 4079 if the (S,G) assert state machine is in NoInfo state before and after 4080 consideration of the received message: 4082 Receive Inferior Assert with RPTbit set AND 4083 CouldAssert(*,G,I)==TRUE 4084 An Inferior (*,G) assert is received for G on Interface I. If 4085 CouldAssert(*,G,I) is TRUE, then I is our downstream 4086 interface, and we have (*,G) forwarding state on this 4087 interface, so we should be the assert winner. We transition 4088 to the "I am Assert Winner" state, and perform Actions A1 4089 (below). 4091 A data packet destined for G arrives on interface I, AND 4092 CouldAssert(*,G,I)==TRUE 4093 A data packet destined for G arrived on a downstream interface 4094 which is in our (*,G) outgoing interface list. We therefore 4095 believe we should be the forwarder for this (*,G), and so we 4096 transition to the "I am Assert Winner" state, and perform 4097 Actions A1 (below). 4099 Receive Preferred Assert with RPT bit set AND 4100 AssertTrackingDesired(*,G,I)==TRUE 4101 We're interested in (*,G) Asserts, either because I is a 4102 downstream interface for which we have (*,G) forwarding state, 4103 or because I is the upstream interface for RP(G) and we have 4104 (*,G) forwarding state. We get a (*,G) Assert that has a 4105 better metric than our own, so we do not win the Assert. We 4106 transition to "I am Assert Loser" and perform actions A2 4107 (below). 4109 Transitions from "I am Assert Winner" State 4111 When in "I am Assert Winner" state, the following events trigger 4112 transitions, but only if the (S,G) assert state machine is in NoInfo 4113 state before and after consideration of the received message: 4115 Receive Inferior Assert 4116 We receive a (*,G) assert that has a worse metric than our 4117 own. Whoever sent the assert has lost, and so we re-send a 4118 (*,G) Assert, and restart the Assert Timer (Action A3 below). 4120 Receive Preferred Assert 4121 We receive a (*,G) assert that has a better metric than our 4122 own. We transition to "I am Assert Loser" state and perform 4123 actions A2 (below). 4125 When in "I am Assert Winner" state, the following events trigger 4126 transitions: 4128 Assert Timer Expires 4129 The (*,G) Assert Timer expires. As we're in the Winner state, 4130 then we must still have (*,G) forwarding state that is 4131 actively being kept alive. To prevent unnecessary thrashing 4132 of the forwarder and periodic flooding of duplicate packets, 4133 we re-send the (*,G) Assert, and restart the Assert Timer 4134 (Action A3 below). 4136 CouldAssert(*,G,I) -> FALSE 4137 Our (*,G) forwarding state or RPF interface changed so as to 4138 make CouldAssert(*,G,I) become false. We can no longer 4139 perform the actions of the assert winner, and so we transition 4140 to NoInfo state and perform actions A4 (below). 4142 Transitions from "I am Assert Loser" State 4144 When in "I am Assert Loser" state, the following events trigger 4145 transitions, but only if the (S,G) assert state machine is in NoInfo 4146 state before and after consideration of the received message: 4148 Receive Preferred Assert 4149 We receive a (*,G) assert that is better than that of the 4150 current assert winner. We stay in Loser state, and perform 4151 actions A2 below. 4153 Receive Acceptable Assert from Current Winner 4154 We receive a (*,G) assert from the current assert winner that 4155 is better than our own metric for this group (although the 4156 metric may be worse than the winner's previous metric). We 4157 stay in Loser state, and perform actions A2 below. 4159 Receive Inferior Assert from Current Winner 4160 We receive an assert from the current assert winner that is 4161 worse than our own metric for this group (typically because 4162 the winner's metric became worse). We transition to NoInfo 4163 state, delete this (*,G) assert state (action A5), and allow 4164 the normal PIM Join/Prune mechanisms to operate. Usually we 4165 will eventually re-assert and win when data packets for G have 4166 started flowing again. 4168 When in "I am Assert Loser" state, the following events trigger 4169 transitions: 4171 Assert Timer Expires 4172 The (*,G) Assert Timer expires. We transition to NoInfo state 4173 and delete this (*,G) assert info (action A5). 4175 Current Winner's GenID Changes or NLT Expires 4176 The Neighbor Liveness Timer associated with the current winner 4177 expires or we receive a Hello message from the current winner 4178 reporting a different GenID from the one it previously 4179 reported. This indicates that the current winner's interface 4180 or router has gone down (and may have come back up), and so we 4181 must assume it no longer knows it was the winner. We 4182 transition to the NoInfo state, deleting the (*,G) assert 4183 information (action A5). 4185 AssertTrackingDesired(*,G,I)->FALSE 4186 AssertTrackingDesired(*,G,I) becomes FALSE. Our forwarding 4187 state has changed so that (*,G) Asserts on interface I are no 4188 longer of interest to us. We transition to NoInfo state and 4189 delete this (*,G) assert info (action A5). 4191 My metric becomes better than the assert winner's metric 4192 My routing metric, rpt_assert_metric(G,I), has changed so that 4193 now my assert metric for (*,G) is better than the metric we 4194 have stored for current assert winner. We transition to 4195 NoInfo state, and delete this (*,G) assert state (action A5), 4196 and allow the normal PIM Join/Prune mechanisms to operate. 4197 Usually we will eventually re-assert and win when data packets 4198 for G have started flowing again. 4200 RPF_interface(RP(G)) stops being interface I 4201 Interface I used to be the RPF interface for RP(G), and now it 4202 is not. We transition to NoInfo state, and delete this (*,G) 4203 assert state (action A5). 4205 Receive Join(*,G) or Join(*,*,RP(G)) on interface I 4206 We receive a Join(*,G) or a Join(*,*,RP(G)) that has the 4207 Upstream Neighbor Address field set to my IP address on 4208 interface I. The action is to transition to NoInfo state, and 4209 delete this (*,G) assert state (action A5), and allow the 4210 normal PIM Join/Prune mechanisms to operate. If whoever sent 4211 the Join was in error, then the normal assert mechanism will 4212 eventually re-apply and we will lose the assert again. 4213 However whoever sent the assert may know that the previous 4214 assert winner has died, and so we may end up being the new 4215 forwarder. 4217 (*,G) Assert State-machine Actions 4219 A1: Send Assert(*,G) 4220 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 4221 Store self as AssertWinner(*,G,I). 4222 Store rpt_assert_metric(G,I) as AssertWinnerMetric(*,G,I). 4224 A2: Store new assert winner as AssertWinner(*,G,I) and assert 4225 winner metric as AssertWinnerMetric(*,G,I). 4226 Set Assert Timer to Assert_Time 4228 A3: Send Assert(*,G) 4229 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 4231 A4: Send AssertCancel(*,G) 4232 Delete assert info (AssertWinner(*,G,I) and 4233 AssertWinnerMetric(*,G,I) will then return their default 4234 values). 4236 A5: Delete assert info (AssertWinner(*,G,I) and 4237 AssertWinnerMetric(*,G,I) will then return their default 4238 values). 4240 Note that some of these actions may cause the value of JoinDesired(*,G) 4241 or RPF'(*,G)) to change, which could cause further transitions in other 4242 state machines. 4244 4.6.3. Assert Metrics 4246 Assert metrics are defined as: 4248 struct assert_metric { 4249 rpt_bit_flag; 4250 metric_preference; 4251 route_metric; 4252 ip_address; 4253 }; 4255 When comparing assert_metrics, the rpt_bit_flag, metric_preference, and 4256 route_metric field are compared in order, where the first lower value 4257 wins. If all fields are equal, the primary IP address of the router 4258 that sourced the Assert message is used as a tie-breaker, with the 4259 highest IP address winning. 4261 An assert metric for (S,G) to include in (or compare against) an Assert 4262 message sent on interface I should be computed using the following 4263 pseudocode: 4265 assert_metric 4266 my_assert_metric(S,G,I) { 4267 if( CouldAssert(S,G,I) == TRUE ) { 4268 return spt_assert_metric(S,I) 4269 } else if( CouldAssert(*,G,I) == TRUE ) { 4270 return rpt_assert_metric(G,I) 4271 } else { 4272 return infinite_assert_metric() 4273 } 4274 } 4276 spt_assert_metric(S,I) gives the assert metric we use if we're sending 4277 an assert based on active (S,G) forwarding state: 4279 assert_metric 4280 spt_assert_metric(S,I) { 4281 return {0,MRIB.pref(S),MRIB.metric(S),my_ip_address(I)} 4282 } 4284 rpt_assert_metric(G,I) gives the assert metric we use if we're sending 4285 an assert based only on (*,G) forwarding state: 4287 assert_metric 4288 rpt_assert_metric(G,I) { 4289 return {1,MRIB.pref(RP(G)),MRIB.metric(RP(G)),my_ip_address(I)} 4290 } 4292 MRIB.pref(X) and MRIB.metric(X) are the routing preference and routing 4293 metrics associated with the route to a particular (unicast) destination 4294 X, as determined by the MRIB. my_ip_address(I) is simply the router's 4295 primary IP address that is associated with the local interface I. 4297 infinite_assert_metric() gives the assert metric we need to send an 4298 assert but don't match either (S,G) or (*,G) forwarding state: 4300 assert_metric 4301 infinite_assert_metric() { 4302 return {1,infinity,infinity,0} 4303 } 4305 4.6.4. AssertCancel Messages 4307 An AssertCancel message is simply an RPT Assert message but with 4308 infinite metric. It is sent by the assert winner when it deletes the 4309 forwarding state that had caused the assert to occur. Other routers 4310 will see this metric, and it will cause any other router that has 4311 forwarding state to send its own assert, and to take over forwarding. 4313 An AssertCancel(S,G) is an infinite metric assert with the RPT bit set 4314 that names S as the source. 4316 An AssertCancel(*,G) is an infinite metric assert with the RPT bit set, 4317 and typically will name RP(G) as the source as it cannot name an 4318 appropriate S. 4320 AssertCancel messages are simply an optimization. The original Assert 4321 timeout mechanism will allow a subnet to eventually become consistent; 4322 the AssertCancel mechanism simply causes faster convergence. No special 4323 processing is required for an AssertCancel message, since it is simply 4324 an Assert message from the current winner. 4326 4.6.5. Assert State Macros 4328 The macros lost_assert(S,G,rpt,I), lost_assert(S,G,I), and 4329 lost_assert(*,G,I) are used in the olist computations of Section 4.1, 4330 and are defined as: 4332 bool lost_assert(S,G,rpt,I) { 4333 if ( RPF_interface(RP(G)) == I OR 4334 ( RPF_interface(S) == I AND SPTbit(S,G) == TRUE ) ) { 4335 return FALSE 4336 } else { 4337 return ( AssertWinner(S,G,I) != NULL AND 4338 AssertWinner(S,G,I) != me ) 4339 } 4340 } 4342 bool lost_assert(S,G,I) { 4343 if ( RPF_interface(S) == I ) { 4344 return FALSE 4345 } else { 4346 return ( AssertWinner(S,G,I) != NULL AND 4347 AssertWinner(S,G,I) != me AND 4348 (AssertWinnerMetric(S,G,I) is better 4349 than spt_assert_metric(S,I) ) 4350 } 4351 } 4353 Note: the term "AssertWinnerMetric(S,G,I) is better than 4354 spt_assert_metric(S,I)" is required to correctly handle the transition 4355 phase when a router has (S,G) join state, but has not yet set the SPT 4356 bit. In this case it needs to ignore the assert state if it will win 4357 the assert once the SPT bit is set. 4359 bool lost_assert(*,G,I) { 4360 if ( RPF_interface(RP(G)) == I ) { 4361 return FALSE 4362 } else { 4363 return ( AssertWinner(*,G,I) != NULL AND 4364 AssertWinner(*,G,I) != me ) 4365 } 4366 } 4368 AssertWinner(S,G,I) is the IP source address of the Assert(S,G) packet 4369 that won an Assert. 4371 AssertWinner(*,G,I) is the IP source address of the Assert(*,G) packet 4372 that won an Assert. 4374 AssertWinnerMetric(S,G,I) is the Assert metric of the Assert(S,G) packet 4375 that won an Assert. 4377 AssertWinnerMetric(*,G,I) is the Assert metric of the Assert(*,G) packet 4378 that won an Assert. 4380 AssertWinner(S,G,I) defaults to NULL and AssertWinnerMetric(S,G,I) 4381 defaults to Infinity when in the NoInfo state. 4383 Summary of Assert Rules and Rationale 4385 This section summarizes the key rules for sending and reacting to 4386 asserts and the rationale for these rules. This section is not intended 4387 to be and should not be treated as a definitive specification of 4388 protocol behavior. The state machines and pseudocode should be 4389 consulted for that purpose. Rather, this section is intended to 4390 document important aspects of a the Assert protocol behavior and to 4391 provide information that may prove helpful to the reader in 4392 understanding and implementing this part of the protocol. 4394 1. Behavior: Downstream neighbors send Join(*,G) and Join(S,G) 4395 periodic messages to the appropriate RPF' neighbor, i.e., the RPF 4396 neighbor as modified by the assert process. They are not always 4397 sent to the RPF neighbor as indicated by the MRIB. Normal 4398 suppression and override rules apply. 4400 Rationale: By sending the periodic and triggered Join messages to 4401 the RPF' neighbor instead of to the RPF neighbor, the downstream 4402 router avoids re-triggering the Assert process with every Join. A 4403 side effect of sending Joins to the Assert winner is that traffic 4404 will not switch back to the "normal" RPF neighbor until the Assert 4405 times out. This will not happen until data stops flowing, if item 4406 8 below is implemented. 4408 2. Behavior: The assert winner for (*,G) acts as the local DR for 4409 (*,G) on behalf of IGMP/MLD members. 4411 Rationale: This is required to allow a single router to merge PIM 4412 and IGMP/MLD joins and leaves. Without this, overrides don't work. 4414 3. Behavior: The assert winner for (S,G) acts as the local DR for 4415 (S,G) on behalf of IGMPv3 members. 4417 Rationale: Same rationale as for 2. 4419 4. Behavior: (S,G) and (*,G) prune overrides are sent to the RPF' 4420 neighbor and not to the regular RPF neighbor. 4422 Rationale: Same as for 1. 4424 5. Behavior: An (S,G,rpt) prune override is not sent (at all) if 4425 RPF'(S,G,rpt) != RPF'(*,G). 4427 Rationale: This avoids keeping state alive on the (S,G) tree when 4428 only (*,G) downstream members are left. Also, it avoids sending 4429 (S,G,rpt) joins to a router that is not on the (*,G) tree. This 4430 behavior might be confusing although this specification does 4431 indicate that such a join should be dropped. 4433 6. Behavior: An assert loser that receives a Join(S,G) with an 4434 Upstream Neighbor Address that is one of its addresses on that 4435 interface cancels the (S,G) Assert Timer. 4437 Rationale: This is necessary in order to have rapid convergence in 4438 the event that the downstream router that initially sent a join to 4439 the prior Assert winner has undergone a topology change. 4441 7. Behavior: An assert loser that receives a Join(*,G) or a 4442 Join(*,*,RP(G)) with an Upstream Neighbor Address that is one of 4443 its addresses on that interface cancels the (*,G) Assert Timer and 4444 all (S,G) assert timers that do not have corresponding 4445 Prune(S,G,rpt) messages in the compound Join/Prune message. 4447 Rationale: Same as 6. 4449 8. Behavior: An assert winner for (*,G) or (S,G) sends a canceling 4450 assert when it is about to stop forwarding on a (*,G) or an (S,G) 4451 entry. This behavior does not apply to (S,G,rpt). 4453 Rationale: This allows switching back to the shared tree after the 4454 last SPT router on the LAN leaves. Doing this prevents downstream 4455 routers on the shared tree from keeping SPT state alive. 4457 9. Behavior: Re-send the assert messages before timing out an assert. 4458 (This behavior is optional.) 4460 Rationale: This prevents the periodic duplicates that would 4461 otherwise occur each time that an assert times out and is then re- 4462 established. 4464 10. Behavior: When RPF'(S,G,rpt) changes to be the same as RPF'(*,G) we 4465 need to trigger a Join(S,G,rpt) to RPF'(*,G). 4467 Rationale: This allows switching back to the RPT after the last SPT 4468 member leaves. 4470 4.7. PIM Multicast Border Router Behavior 4472 In some cases PIM-SM domains will interconnect with non-PIM domains. In 4473 these cases, the border routers of the PIM domain speak PIM-SM on some 4474 interfaces and speak other multicast routing protocols on other 4475 interfaces. Such routers are termed PIM Multicast Border Routers or 4476 PMBRs. In general, RFC 2715 [11] provides rules for interoperability 4477 between different multicast routing protocols. In this section we 4478 specify how PMBRs differ from regular PIM-SM routers. 4480 From the point of view of PIM-SM, a PMBR has two tasks: 4482 o To ensure that traffic from sources outside the PIM-SM domain reaches 4483 receivers inside the domain. 4485 o To ensure that traffic from sources inside the PIM-SM domain reaches 4486 receivers outside the domain. 4488 We note that multiple PIM-SM domains are sometimes connected together 4489 using protocols such as MSDP, which provides information about active 4490 external sources, but does not follow RFC 2715. In such cases the 4491 domains are not connected via PMBRs because Join(S,G) messages traverse 4492 the border between domains. A PMBR is required when no PIM messages can 4493 traverse the border; typically this is because the routing protocol in 4494 the neighboring domain is not PIM-SM. 4496 4.7.1. Sources External to the PIM-SM Domain 4498 A PMBR needs to ensure that traffic from multicast sources external to 4499 the PIM-SM domain reaches receivers inside the domain. The PMBR will 4500 follow the rules in RFC 2715, such that traffic from external sources 4501 reaches the PMBR itself. 4503 According to RFC 2715, the PIM-SM component of the PMBR will receive an 4504 (S,G) Creation event when data from an (S,G) data packet from an 4505 external source first reaches the PMBR. If RPF_interface(S) is not an 4506 interface in the PIM-SM domain, the packet cannot be originated into the 4507 PIM domain at this router, and the PIM-SM component of the PMBR will not 4508 process the packet. Otherwise the PMBR will then act exactly as if it 4509 were the DR for this source (see Section 4.4.1), with the following 4510 modifications: 4512 o The Border-bit is set in all PIM Register message sent for these 4513 sources. 4515 o DirectlyConnected(S) is treated as being TRUE for these sources. 4517 o The PIM-SM forwarding rule "iif == RPF_interface(S)" is relaxed to be 4518 TRUE if iif is any interface that is not part of the PIM-SM component 4519 of the PMBR (see Section 4.2). 4521 4.7.2. Sources Internal to the PIM-SM Domain 4523 A PMBR needs to ensure that traffic from sources inside the PIM-SM 4524 domain reaches receivers outside the domain. Using terminology from RFC 4525 2715, there are two possible scenarios for this: 4527 o Another component of the PMBR is a wildcard receiver. In this case 4528 the PIM-SM component of the PMBR must ensure that traffic from all 4529 internal sources reaches the PMBR until it is informed otherwise. 4531 o No other component of the PMBR is a wildcard receiver. In this case 4532 the PMBR will receive explicit information as to which groups or 4533 (source,group) pairs the external domains wish to receive. 4535 In the former case, the PMBR will need to send a Join(*,*,RP) to all the 4536 RPs in the PIM-SM domain. This will cause all traffic in the domain to 4537 reach the PMBR. The PMBR may then act as if it were a DR with directly 4538 connected receivers, and trigger the transition to a shortest path tree 4539 (see Section 4.2.1). 4541 In the latter case, the PMBR will not need to send Join(*,*,RP) 4542 messages. However the PMBR will still need to act as a DR with directly 4543 connected receivers on behalf of the external receivers in terms of 4544 being able to switch to the shortest-path tree for internally-reached 4545 sources. 4547 According to RFC 2715, the PIM-SM component of the PMBR may receive a 4548 number of alerts generated by events in the external routing components. 4549 To implement the above behavior, one reasonable way to map these alerts 4550 into PIM-SM state as follows: 4552 o When a PIM-SM component receives an (S,G) Prune alert, it sets 4553 local_receiver_include(S,G,I) to FALSE for the discard interface. 4555 o When a PIM-SM component receives a (*,G) Prune alert, it sets 4556 local_receiver_include(*,G,I) to FALSE for the discard interface. 4558 o When a PIM-SM component receives an (S,G) Join alert, it sets 4559 local_receiver_include(S,G,I) to TRUE for the discard interface. 4561 o When a PIM-SM component receives a (*,G) Join alert, it sets 4562 local_receiver_include(*,G,I) to TRUE for the discard interface. 4564 o When a PIM-SM component receives a (*,*) Join alert, it sets 4565 DownstreamJPState(*,*,RP,I) to Join state on the discard interface for 4566 all RPs in the PIM-SM domain. 4568 o When a PIM-SM component receives a (*,*) Prune alert, then it sets 4569 DownstreamJPState(*,*,RP,I) to NoInfo state on the discard interface 4570 for all RPs in the PIM-SM domain. 4572 We refer above to the discard interface because the macros and state- 4573 machines are interface-specific, but we need to have PIM state that is 4574 not associated with any actual PIM-SM interface. Implementors are free 4575 to implement this in any reasonable manner. 4577 Note that these state changes will then cause additional PIM-SM state 4578 machine transitions in the normal way. 4580 These rules are however not sufficient to allow pruning off the (*,*,RP) 4581 tree. Some additional rules provide guidance as to one way this may be 4582 done: 4584 o If the PMBR has joined on the (*,*,RP) tree, then it should set 4585 DownstreamJPState(*,G,I) to JOIN on the discard interface for all 4586 active groups. 4588 o If the router receives a (S,G) prune alert it will need to set 4589 DownstreamJPState(S,G,rpt,I) to PRUNE on the discard interface. 4591 o If the router receives a (*,G) prune alert, it will need to set 4592 DownstreamJPState(S,G,rpt,I) to PRUNE on the discard interface for all 4593 active sources sending to G. 4595 The rationale for this is that there is no way in PIM-SM to prune 4596 traffic off the (*,*,RP) tree, except by Joining the (*,G) tree and then 4597 pruning each source individually. 4599 4.8. PIM Bootstrap and RP Discovery 4601 For correct operation, every PIM router within a PIM domain must be able 4602 to map a particular multicast group address to the same RP. If this is 4603 not the case then black holes may appear, where some receivers in the 4604 domain cannot receive some groups. A domain in this context is a 4605 contiguous set of routers that all implement PIM and are configured to 4606 operate within a common boundary defined by PIM Multicast Border Routers 4607 (PMBRs). PMBRs connect each PIM domain to the rest of the Internet. 4609 A notable exception to this is where a PIM domain is broken up into 4610 multiple administrative scope regions - these are regions where a border 4611 has been configured so that a range of multicast groups will not be 4612 forwarded across that border. For more information on Administratively 4613 Scoped IP Multicast, see RFC 2365. The modified criteria for admin- 4614 scoped regions are that the region is convex with respect to forwarding 4615 based on the MRIB, and that all PIM routers within the scope region map 4616 scoped groups to the same RP within that region. 4618 This specification does not mandate the use of a single mechanism to 4619 provide routers with the information to perform the group-to-RP mapping. 4620 Currently three mechanisms are possible, and all three have associated 4621 problems: 4623 Static Configuration 4624 A PIM router MUST support the static configuration of group-to-RP 4625 mappings. Such a mechanism is not robust to failures, but does at 4626 least provide a basic interoperability mechanism. 4628 Cisco's Auto-RP 4629 Auto-RP uses a PIM Dense-Mode multicast group to announce group-to- 4630 RP mappings from a central location. This mechanism is not useful 4631 if PIM Dense-Mode is not being run in parallel with PIM Sparse- 4632 Mode, and was only intended for use with PIM Sparse-Mode Version 1. 4633 No standard specification currently exists. 4635 BootStrap Router (BSR) 4636 RFC 2362 specifies a bootstrap mechanism based around the automatic 4637 election of a bootstrap router (BSR). Any router in the domain 4638 that is configured to be a possible RP reports its candidacy to the 4639 BSR, and then a domain-wide flooding mechanism distributes the 4640 BSR's chosen set of RPs throughout the domain. As specified in RFC 4641 2362, BSR is flawed in its handling of admin-scoped regions that 4642 are smaller than a PIM domain, but the mechanism does work for 4643 global-scoped groups. 4645 As far as PIM-SM is concerned, the only important requirement is that 4646 all routers in the domain (or admin scope zone for scoped regions) 4647 receive the same set of group-range-to-RP mappings. This may be 4648 achieved through the use of any of these mechanisms, or through 4649 alternative mechanisms not currently specified. 4651 Any RP address configured or learned MUST be a domain-wide reachable 4652 address. 4654 4.8.1. Group-to-RP Mapping 4656 Using one of the mechanisms described above, a PIM router receives one 4657 or more possible group-range-to-RP mappings. Each mapping specifies a 4658 range of multicast groups (expressed as a group and mask) and the RP to 4659 which such groups should be mapped. Each mapping may also have an 4660 associated priority. It is possible to receive multiple mappings all of 4661 which might match the same multicast group - this is the common case 4662 with BSR. The algorithm for performing the group-to-RP mapping is as 4663 follows: 4665 1 Perform longest match on group-range to obtain a list of RPs. 4667 2 From this list of matching RPs, find the one with highest priority. 4668 Eliminate any RPs from the list that have lower priorities. 4670 3 If only one RP remains in the list, use that RP. 4672 4 If multiple RPs are in the list, use the PIM hash function to 4673 choose one. 4675 Thus if two or more group-range-to-RP mappings cover a particular group, 4676 the one with the longest mask is the mapping to use. If the mappings 4677 have the same mask length, then the one with the highest priority is 4678 chosen. If there is more than one matching entry with the same longest 4679 mask and the priorities are identical, then a hash function (see Section 4680 4.8.2) is applied to choose the RP. 4682 This algorithm is invoked by a DR when it needs to determine an RP for a 4683 given group, e.g. upon reception of a packet or IGMP/MLD membership 4684 indication for a group for which the DR does not know the RP. It is 4685 invoked by any router that has (*,*,RP) state when a packet is received 4686 for which there is no corresponding (S,G) or (*,G) entry. Furthermore, 4687 the mapping function is invoked by all routers upon receiving a (*,G) or 4688 (*,*,RP) Join/Prune message. 4690 Note that if the set of possible group-range-to-RP mappings changes, 4691 each router will need to check whether any existing groups are affected. 4692 This may, for example, cause a DR or acting DR to re-join a group, or 4693 cause it to re-start register encapsulation to the new RP. 4695 Implementation note: the bootstrap mechanism described in RFC 4696 2362 omitted step (1) above. However of the implementations 4697 we are aware of, approximately half performed step (1) anyway. 4698 It should be noted that implementations of BSR that omit step 4699 1 will not correctly interoperate with implementations of this 4700 specification when used with the BSR mechanism described in 4701 [13]. 4703 4.8.2. Hash Function 4705 The hash function is used by all routers within a domain, to map a group 4706 to one of the RPs from the matching set of group-range-to-RP mappings 4707 (this set all have the same longest mask length and same highest 4708 priority). The algorithm takes as input the group address, and the 4709 addresses of the candidate RPs from the mappings, and gives as output 4710 one RP address to be used. 4712 The protocol requires that all routers hash to the same RP within a 4713 domain (except for transients). The following hash function must be used 4714 in each router: 4716 1 For RP addresses in the matching group-range-to-RP mappings, 4717 compute a value: 4719 Value(G,M,C(i))= 4720 (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31 4722 where C(i) is the RP address and M is a hash-mask. If BSR is being 4723 used, the hash-mask is given in the Bootstrap messages. If BSR is 4724 not being used, the alternative mechanism that supplies the group- 4725 range-to-RP mappings may supply the value, or else it defaults to a 4726 mask with the most significant 30 bits being one for IPv4 and the 4727 most significant 126 bits being one for IPv6. The hash-mask allows 4728 a small number of consecutive groups (e.g., 4) to always hash to 4729 the same RP. For instance, hierarchically-encoded data can be sent 4730 on consecutive group addresses to get the same delay and fate- 4731 sharing characteristics. 4733 For address families other than IPv4, a 32-bit digest to be used as 4734 C(i) and G must first be derived from the actual RP or group 4735 address. Such a digest method must be used consistently throughout 4736 the PIM domain. For IPv6 addresses, we recommend using the 4737 equivalent IPv4 address for an IPv4-compatible address, and the 4738 exclusive-or of each 32-bit segment of the address for all other 4739 IPv6 addresses. For example, the digest of the IPv6 address 4740 3ffe:b00:c18:1::10 would be computed as 0x3ffe0b00 ^ 0x0c180001 ^ 4741 0x00000000 ^ 0x00000010, where ^ represents the exclusive-or 4742 operation. 4744 2 The candidate RP with the highest resulting hash value is then the 4745 RP chosen by this Hash Function. If more than one RP has the same 4746 highest hash value, the RP with the highest IP address is chosen. 4748 4.9. Source-Specific Multicast 4750 The Source-Specific Multicast (SSM) service model [6] can be implemented 4751 with a strict subset of the PIM-SM protocol mechanisms. Both regular IP 4752 Multicast and SSM semantics can coexist on a single router and both can 4753 be implemented using the PIM-SM protocol. A range of multicast 4754 addresses, currently 232.0.0.0/8 in IPv4, is reserved for SSM, and the 4755 choice of semantics is determined by the multicast group address in both 4756 data packets and PIM messages. 4758 4.9.1. Protocol Modifications for SSM destination addresses 4760 The following rules override the normal PIM-SM behavior for a multicast 4761 address G in the SSM reserved range: 4763 o A router MUST NOT send a (*,G) Join/Prune message for any reason. 4765 o A router MUST NOT send an (S,G,rpt) Join/Prune message for any reason. 4767 o A router MUST NOT send a Register message for any packet that is 4768 destined to an SSM address. 4770 o A router MUST NOT forward packets based on (*,G) or (S,G,rpt) state. 4771 The (*,G) and (S,G,rpt) -related state summarization macros are NULL 4772 for any SSM address, for the purposes of packet forwarding. 4774 o A router acting as an RP MUST NOT forward any Register-encapsulated 4775 packet that has an SSM destination address. 4777 The last two rules are present to deal with "legacy" routers unaware of 4778 SSM that may be sending (*,G) and (S,G,rpt) Join/Prunes, or Register 4779 messages for SSM destination addresses. 4781 Additionally: 4783 o A router MAY be configured to advertise itself as a Candidate RP for 4784 an SSM address. If so, it SHOULD respond with a Register-Stop message 4785 to any Register message containing a packet destined for an SSM 4786 address. 4788 o A router MAY optimize out the creation and maintenance of (S,G,rpt) 4789 and (*,G) state for SSM destination addresses -- this state is not 4790 needed for SSM packets. 4792 4.9.2. PIM-SSM-only Routers 4794 An implementor may choose to implement only the subset of PIM Sparse- 4795 Mode that provides SSM forwarding semantics. 4797 A PIM-SSM-only router MUST implement the following portions of this 4798 specification: 4800 o Upstream (S,G) state machine (Section 4.5.7) 4802 o Downstream (S,G) state machine (Section 4.5.3) 4804 o (S,G) Assert state machine (Section 4.6.1) 4806 o Hello messages, neighbor discovery and DR election (Section 4.3) 4808 o Packet forwarding rules (Section 4.2) 4810 A PIM-SSM-only router does not need to implement the following protocol 4811 elements: 4813 o Register state machine (Section 4.4) 4815 o (*,G), (S,G,rpt) and (*,*,RP) Downstream state machines (Sections 4816 4.5.2, 4.5.4, and 4.5.1) 4818 o (*,G), (S,G,rpt), and (*,*,RP) Upstream state machines (Sections 4819 4.5.6, 4.5.8, and 4.5.5) 4821 o (*,G) Assert state machine (Section 4.6.2) 4822 o Bootstrap RP Election (Section 4.8) 4824 o Keepalive Timer 4826 o SptBit (Section 4.2.2) 4828 The Keepalive Timer should be treated as always running and SptBit 4829 should be treated as being always set for an SSM address. Additionally, 4830 the Packet forwarding rules of Section 4.2 can be simplified in a PIM- 4831 SSM-only router: 4833 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 4834 oiflist = inherited_olist(S,G) 4835 } else if( iif is in inherited_olist(S,G) ) { 4836 send Assert(S,G) on iif 4837 } 4839 oiflist = oiflist (-) iif 4840 forward packet on all interfaces in oiflist 4842 This is nothing more than the reduction of the normal PIM-SM forwarding 4843 rule, with all (S,G,rpt) and (*,G) clauses replaced with NULL. 4845 4.10. PIM Packet Formats 4847 This section describes the details of the packet formats for PIM control 4848 messages. 4850 All PIM control messages have IP protocol number 103. 4852 PIM messages are either unicast (e.g. Registers and Register-Stop), or 4853 multicast with TTL 1 to the `ALL-PIM-ROUTERS' group (e.g. Join/Prune, 4854 Asserts, etc.). The source address used for unicast messages is a 4855 domain-wide reachable address; the source address used for multicast 4856 messages is the link-local address of the interface on which the message 4857 is being sent. 4859 The IPv4 `ALL-PIM-ROUTERS' group is `224.0.0.13'. The IPv6 `ALL-PIM- 4860 ROUTERS' group is `ff02::d'. 4862 0 1 2 3 4863 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 4864 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4865 |PIM Ver| Type | Reserved | Checksum | 4866 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4867 PIM Ver 4868 PIM Version number is 2. 4870 Type Types for specific PIM messages. PIM Types are: 4872 Message Type Destination 4873 --------------------------------------------------------------------------- 4874 0 = Hello Multicast to ALL-PIM-ROUTERS 4875 1 = Register Unicast to RP 4876 2 = Register-Stop Unicast to source of Register packet 4877 3 = Join/Prune Multicast to ALL-PIM-ROUTERS 4878 4 = Bootstrap Multicast to ALL-PIM-ROUTERS 4879 5 = Assert Multicast to ALL-PIM-ROUTERS 4880 6 = Graft (used in PIM-DM only) Multicast to ALL-PIM-ROUTERS 4881 7 = Graft-Ack (used in PIM-DM only) Unicast to source of Graft packet 4882 8 = Candidate-RP-Advertisement Unicast to Domain's BSR 4884 Reserved 4885 Set to zero on transmission. Ignored upon receipt. 4887 Checksum 4888 The checksum is a standard IP checksum, i.e. the 16-bit one's 4889 complement of the one's complement sum of the entire PIM message, 4890 excluding the "Multicast data packet" section of the Register 4891 message. For computing the checksum, the checksum field is zeroed. 4893 For IPv6, the checksum also includes the IPv6 "pseudo-header", as 4894 specified in RFC 2460, Section 8.1 [4]. This "pseudo-header" is 4895 prepended to the PIM header for the purposes of calculating the 4896 checksum. The "Upper-Layer Packet Length" in the pseudo-header is 4897 set to the length of the PIM message, except in Register messages 4898 where it is set to the length of the PIM header. The Next Header 4899 value used in the pseudo-header is 103. If the packet's length is 4900 not an integral number of 16-bit words, the packet is padded with a 4901 trailing byte of zero before performing the checksum. 4903 If a message is received with an unrecognized PIM Ver or Type field, it 4904 MUST be discarded and an error message SHOULD be logged to the 4905 administrator in a rate limited manner. 4907 4.10.1. Encoded Source and Group Address Formats 4909 Encoded-Unicast address 4911 An Encoded-Unicast address takes the following format: 4913 0 1 2 3 4914 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 4915 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4916 | Addr Family | Encoding Type | Unicast Address 4917 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4919 Addr Family 4920 The PIM address family of the `Unicast Address' field of this 4921 address. 4923 Values of 0-127 are as assigned by the IANA for Internet Address 4924 Families in [7]. Values 128-250 are reserved to be assigned by the 4925 IANA for PIM-specific Address Families. Values 251 though 255 are 4926 designated for private use. As there is no assignment authority 4927 for this space, collisions should be expected. 4929 Encoding Type 4930 The type of encoding used within a specific Address Family. The 4931 value `0' is reserved for this field, and represents the native 4932 encoding of the Address Family. 4934 Unicast Address 4935 The unicast address as represented by the given Address Family and 4936 Encoding Type. 4938 Encoded-Group address 4940 Encoded-Group addresses take the following format: 4942 0 1 2 3 4943 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 4944 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4945 | Addr Family | Encoding Type |B| Reserved |Z| Mask Len | 4946 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4947 | Group multicast Address 4948 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4950 Addr Family 4951 described above. 4953 Encoding Type 4954 described above. 4956 [B]idirectional PIM 4957 indicates the group range should use Bidirectional PIM [14]. For 4958 PIM-SM defined in this specification, this bit MUST be zero. 4960 Reserved 4961 Transmitted as zero. Ignored upon receipt. 4963 Admin Scope [Z]one 4964 indicates the group range is an admin scope zone. This is used in 4965 the Bootstrap Router Mechanism [13] only. For all other purposes, 4966 this bit is set to zero and ignored on receipt. 4968 Mask Len 4969 The Mask length field is 8 bits. The value is the number of 4970 contiguous one bits left justified used as a mask which, combined 4971 with the group address, describes a range of groups. It is less 4972 than or equal to the address length in bits for the given Address 4973 Family and Encoding Type. If the message is sent for a single group 4974 then the Mask length must equal the address length in bits for the 4975 given Address Family and Encoding Type. (e.g. 32 for IPv4 native 4976 encoding, 128 for IPv6 native encoding). 4978 Group multicast Address 4979 Contains the group address. 4981 Encoded-Source address 4983 Encoded-Source address takes the following format: 4985 0 1 2 3 4986 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 4987 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4988 | Addr Family | Encoding Type | Rsrvd |S|W|R| Mask Len | 4989 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4990 | Source Address 4991 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... 4993 Addr Family 4994 described above. 4996 Encoding Type 4997 described above. 4999 Reserved 5000 Transmitted as zero, ignored on receipt. 5002 S The Sparse bit is a 1 bit value, set to 1 for PIM-SM. It is used 5003 for PIM version 1 compatibility. 5005 W The WC (or WildCard) bit is a 1 bit value for use with PIM 5006 Join/Prune messages (see Section 4.10.5.1 ). 5008 R The RPT (or Rendezvous Point Tree) bit is a 1 bit value for use 5009 with PIM Join/Prune messages (see Section 4.10.5.1 ). If the WC bit 5010 is 1, the RPT bit MUST be 1. 5012 Mask Len 5013 The mask length field is 8 bits. The value is the number of 5014 contiguous one bits left justified used as a mask which, combined 5015 with the Source Address, describes a source subnet. The mask length 5016 MUST be equal to the mask length in bits for the given Address 5017 Family and Encoding Type (32 for IPv4 native and 128 for IPv6 5018 native). A router SHOULD ignore any messages received with any 5019 other mask length. 5021 Source Address 5022 The source address. 5024 4.10.2. Hello Message Format 5026 It is sent periodically by routers on all interfaces. 5028 0 1 2 3 5029 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 5030 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5031 |PIM Ver| Type | Reserved | Checksum | 5032 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5033 | OptionType | OptionLength | 5034 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5035 | OptionValue | 5036 | ... | 5037 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5038 | . | 5039 | . | 5040 | . | 5041 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5042 | OptionType | OptionLength | 5043 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5044 | OptionValue | 5045 | ... | 5046 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5048 PIM Version, Type, Reserved, Checksum 5049 Described in Section 4.10. 5051 OptionType 5052 The type of the option given in the following OptionValue field. 5054 OptionLength 5055 The length of the OptionValue field in bytes. 5057 OptionValue 5058 A variable length field, carrying the value of the option. 5060 The Option fields may contain the following values: 5062 o OptionType 1: Holdtime 5063 0 1 2 3 5064 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 5065 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5066 | Type = 1 | Length = 2 | 5067 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5068 | Holdtime | 5069 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5071 Holdtime is the amount of time a receiver must keep the neighbor 5072 reachable, in seconds. If the Holdtime is set to `0xffff', the 5073 receiver of this message never times out the neighbor. This may 5074 be used with dial-on-demand links, to avoid keeping the link up 5075 with periodic Hello messages. 5077 Hello messages with a Holdtime value set to `0' are also sent by 5078 a router on an interface about to go down or changing IP address 5079 (see Section 4.3.1). These are effectively goodbye messages and 5080 the receiving routers should immediately time out the neighbor 5081 information for the sender. 5083 o OptionType 2: LAN Prune Delay 5085 0 1 2 3 5086 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 5087 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5088 | Type = 2 | Length = 4 | 5089 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5090 |T| LAN Delay | Override_Interval | 5091 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5093 The LAN_Prune_Delay option is used to tune the prune propagation 5094 delay on multi-access LANs. 5096 The T bit specifies the ability of the sending router to disable 5097 joins suppression. 5099 LAN Delay and Override_Interval are time intervals in units of 5100 milliseconds are are used to tune the value of the 5101 Override_Interval(I) and its derived timer values. Section 4.3.3 5102 describes how these values affect the behavior of a router. 5104 o OptionType 3 to 16: reserved to be defined in future versions of 5105 this document. 5107 o OptionType 18: deprecated and should not be used. 5109 o OptionType 19: DR Priority 5110 0 1 2 3 5111 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 5112 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5113 | Type = 19 | Length = 4 | 5114 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5115 | DR Priority | 5116 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5118 DR Priority is a 32-bit unsigned number and should be considered 5119 in the DR election as described in Section 4.3.2. 5121 o OptionType 20: Generation ID 5123 0 1 2 3 5124 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 5125 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5126 | Type = 20 | Length = 4 | 5127 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5128 | Generation ID | 5129 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5131 Generation ID is a random 32-bit value for the interface on which 5132 the Hello message is sent. The Generation ID is regenerated 5133 whenever PIM forwarding is started or restarted on the interface. 5135 o OptionType 24: Address List 5137 0 1 2 3 5138 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 5139 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5140 | Type = 24 | Length = | 5141 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5142 | Secondary Address 1 (Encoded-Unicast format) | 5143 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5144 ... 5145 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5146 | Secondary Address N (Encoded-Unicast format) | 5147 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5149 The contents of the Address List Hello option are described in 5150 Section 4.3.4. All addresses within a single Address List must 5151 belong to the same address family. 5153 OptionTypes 17 thru 65000 are assigned by the IANA. OptionTypes 5154 65001 through 65535 are reserved for Private Use, as defined in 5155 [10]. 5156 Unknown options may be ignored. The "Holdtime" option MUST be 5157 implemented; the "DR Priority" and "Generation ID" options SHOULD 5158 be implemented. 5160 4.10.3. Register Message Format 5162 A Register message is sent by the DR or a PMBR to the RP when a 5163 multicast packet needs to be transmitted on the RP-tree. The IP source 5164 address is set to the address of the DR, the destination address to the 5165 RP's address. The IP TTL of the PIM packet is the system's normal 5166 unicast TTL. 5168 0 1 2 3 5169 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 5170 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5171 |PIM Ver| Type | Reserved | Checksum | 5172 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5173 |B|N| Reserved2 | 5174 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5175 | | 5176 . Multicast data packet . 5177 | | 5178 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5180 PIM Version, Type, Reserved, Checksum 5181 Described in Section 4.10. Note that in order to reduce 5182 encapsulation overhead, the checksum for Registers is done only on 5183 first 8 bytes of the packet, including the PIM header and the next 5184 4 bytes, excluding the data packet portion. For interoperability 5185 reasons, a message carrying a checksum calculated over the entire 5186 PIM Register message should also be accepted. When calculating the 5187 checksum, the IPv6 pseudoheader "Upper-Layer Packet Length" is set 5188 to 8. 5190 B The Border bit. If the router is a DR for a source that it is 5191 directly connected to, it sets the B bit to 0. If the router is a 5192 PMBR for a source in a directly connected cloud, it sets the B bit 5193 to 1. 5195 N The Null-Register bit. Set to 1 by a DR that is probing the RP 5196 before expiring its local Register-Suppression Timer. Set to 0 5197 otherwise. 5199 Reserved2 5200 Transmitted as zero, ignored on receipt. 5202 Multicast data packet 5203 The original packet sent by the source. This packet must be the of 5204 the same address family as the encapsulating PIM packet, e.g. an 5205 IPv6 data packet must be encapsulated in an IPv6 PIM packet. Note 5206 that the TTL of the original packet is decremented before 5207 encapsulation, just like any other packet that is forwarded. In 5208 addition, the RP decrements the TTL after decapsulating, before 5209 forwarding the packet down the shared tree. 5211 For (S,G) Null-Registers, the Multicast data packet portion 5212 contains a dummy IP header with S as the source address, G as the 5213 destination address. When generating an IPv4 Null-Register 5214 message, the fields in the dummy IPv4 header SHOULD be filled in 5215 according to the following table. Other IPv4 header fields may 5216 contain any value that is valid for that field. 5218 Field Value 5219 --------------------------------------- 5220 IP Version 4 5221 Header Length 5 5222 Checksum Header checksum 5223 Fragmentation offset 0 5224 More Fragments 0 5225 Total Length 20 5226 IP Protocol 103 (PIM) 5228 On receipt of an (S,G) Null-Register, if the Header Checksum field 5229 is non-zero, the recipient SHOULD check the checksum and discard 5230 null registers that have a bad checksum. The recipient SHOULD NOT 5231 check the value of any individual fields; a correct IP header 5232 checksum is sufficient. If the Header Checksum field is zero, the 5233 recipient MUST NOT check the checksum. 5235 With IPv6, an implementation generates a dummy IP header followed 5236 by a dummy PIM header with values according to the following table 5237 in addition to the source and group. Other IPv6 header fields may 5238 contain any value that is valid for that field. 5240 Header Field Value 5241 -------------------------------------- 5242 IP Version 6 5243 Next Header 103 (PIM) 5244 Length 4 5245 PIM Version 0 5246 PIM Type 0 5247 PIM Reserved 0 5248 PIM Checksum PIM checksum including 5249 IPv6 "pseudo-header"; 5250 see Section 4.10 5252 On receipt of an IPv6 (S,G) Null-Register, if the dummy PIM header 5253 is present, the recipient SHOULD check the checksum and discard 5254 null registers that have a bad checksum. 5256 4.10.4. Register-Stop Message Format 5258 A Register-Stop is unicast from the RP to the sender of the Register 5259 message. The IP source address is the address to which the register was 5260 addressed. The IP destination address is the source address of the 5261 register message. 5263 0 1 2 3 5264 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 5265 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5266 |PIM Ver| Type | Reserved | Checksum | 5267 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5268 | Group Address (Encoded-Group format) | 5269 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5270 | Source Address (Encoded-Unicast format) | 5271 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5273 PIM Version, Type, Reserved, Checksum 5274 Described in Section 4.10. 5276 Group Address 5277 The group address from the multicast data packet in the Register. 5278 Format described in Section 4.10.1. Note that for Register-Stops 5279 the Mask Len field contains the full address length * 8 (e.g. 32 5280 for IPv4 native encoding), if the message is sent for a single 5281 group. 5283 Source Address 5284 The host address of the source from the multicast data packet in 5285 the register. The format for this address is given in the Encoded- 5286 Unicast address in Section 4.10.1. A special wild card value 5287 consisting of an address field of all zeroes can be used to 5288 indicate any source. 5290 4.10.5. Join/Prune Message Format 5292 A Join/Prune message is sent by routers towards upstream sources and 5293 RPs. Joins are sent to build shared trees (RP trees) or source trees 5294 (SPT). Prunes are sent to prune source trees when members leave groups 5295 as well as sources that do not use the shared tree. 5297 0 1 2 3 5298 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 5299 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5300 |PIM Ver| Type | Reserved | Checksum | 5301 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5302 | Upstream Neighbor Address (Encoded-Unicast format) | 5303 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5304 | Reserved | Num groups | Holdtime | 5305 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5306 | Multicast Group Address 1 (Encoded-Group format) | 5307 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5308 | Number of Joined Sources | Number of Pruned Sources | 5309 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5310 | Joined Source Address 1 (Encoded-Source format) | 5311 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5312 | . | 5313 | . | 5314 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5315 | Joined Source Address n (Encoded-Source format) | 5316 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5317 | Pruned Source Address 1 (Encoded-Source format) | 5318 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5319 | . | 5320 | . | 5321 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5322 | Pruned Source Address n (Encoded-Source format) | 5323 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5324 | . | 5325 | . | 5326 | . | 5327 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5328 | Multicast Group Address m (Encoded-Group format) | 5329 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5330 | Number of Joined Sources | Number of Pruned Sources | 5331 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5332 | Joined Source Address 1 (Encoded-Source format) | 5333 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5334 | . | 5335 | . | 5336 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5337 | Joined Source Address n (Encoded-Source format) | 5338 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5339 | Pruned Source Address 1 (Encoded-Source format) | 5340 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5341 | . | 5342 | . | 5343 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5344 | Pruned Source Address n (Encoded-Source format) | 5345 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5347 PIM Version, Type, Reserved, Checksum 5348 Described in Section 4.10. 5350 Unicast Upstream Neighbor Address 5351 The address of the upstream neighbor that is the target of the 5352 message. The format for this address is given in the Encoded- 5353 Unicast address in Section 4.10.1. For IPv6 the source address used 5354 for multicast messages is the link-local address of the interface 5355 on which the message is being sent. For IPv4, the source address 5356 is the primary address associated with that interface. 5358 Reserved 5359 Transmitted as zero, ignored on receipt. 5361 Holdtime 5362 The amount of time a receiver must keep the Join/Prune state alive, 5363 in seconds. If the Holdtime is set to `0xffff', the receiver of 5364 this message should hold the state until canceled by the 5365 appropriate canceling Join/Prune message, or timed out according to 5366 local policy. This may be used with dial-on-demand links, to avoid 5367 keeping the link up with periodic Join/Prune messages. 5369 Note that the HoldTime must be larger than the 5370 J/P_Override_Interval(I). 5372 Number of Groups 5373 The number of multicast group sets contained in the message. 5375 Multicast group address 5376 For format description see Section 4.10.1. 5378 Number of Joined Sources 5379 Number of join source addresses listed for a given group. 5381 Join Source Address 1 .. n 5382 This list contains the sources that the sending router will forward 5383 multicast datagrams for if received on the interface this message 5384 is sent on. 5386 See Encoded-Source-Address format in Section 4.10.1. 5388 Number of Pruned Sources 5389 Number of prune source addresses listed for a group. 5391 Prune Source Address 1 .. n 5392 This list contains the sources that the sending router does not 5393 want to forward multicast datagrams for when received on the 5394 interface this message is sent on. 5396 Within one PIM Join/Prune message, all the Multicast Group Addresses, 5397 Joined Source addresses and Pruned Source addresses MUST be of the same 5398 address family. It is NOT PERMITTED to mix IPv4 and IPv6 addresses 5399 within the same message. In addition, the address family of the fields 5400 in the message SHOULD be the same as the IP source and destination 5401 addresses of the packet. This permits maximum implementation 5402 flexibility for dual-stack IPv4/IPv6 routers. If a router receives a 5403 message with mixed family addresses, it SHOULD only process the 5404 addresses which are of the same family as the unicast upstream neighbor 5405 address. 5407 4.10.5.1. Group Set Source List Rules 5409 As described above, Join / Prune messages are composed of one or more 5410 group sets. Each set contains two source lists, the Join Sources and the 5411 Prune Sources. This section describes the different types of group sets 5412 and source list entries that can exist in a Join / Prune message. 5414 There are two valid group set types: 5416 Wildcard Group Set 5417 The wildcard group set is represented by the entire multicast range 5418 - the beginning of the multicast address range in the group address 5419 field and the prefix length of the multicast address range in the 5420 mask length field of the Multicast Group Address, i.e., 5421 `224.0.0.0/4' for IPv4 or `ff00::/8' for IPv6. Each wildcard group 5422 set may contain one or more (*,*,RP) source list entries in either 5423 the Join or Prune lists. 5425 A (*,*,RP) source list entry may only exist in a wildcard group 5426 set. When added to a Join source list, this type of source entry 5427 expresses the router's interest in receiving traffic for all groups 5428 mapping to the specified RP. When added to a Prune source list a 5429 (*,*,RP) entry expresses the router's interest to stop receiving 5430 such traffic. Note that as indicated by the Join/Prune state 5431 machines, such a Join or Prune will NOT override Join/Prune state 5432 created using a Group-Specific Set (see below). 5434 (*,*,RP) source list entries have the Source-Address set to the 5435 address of the RP, the Source-Address Mask-Len set to the full 5436 length of the IP address and both the WC and RPT bits of the 5437 Source-Address set to 1. 5439 Group Specific Set 5440 A Group Specific Set is represented by a valid IP multicast address 5441 in the group address field and the full length of the IP address in 5442 the mask length field of the Multicast Group Address. Each group 5443 specific set may contain (*,G), (S,G,rpt) and (S,G) source list 5444 entries in the Join or Prune lists. 5446 (*,G) 5447 The (*,G) source list entry is used in Join / Prune messages 5448 sent towards the RP for the specified group. It expresses 5449 interest (or lack of) in receiving traffic sent to the group 5450 through the Rendezvous-Point shared tree. There may only be 5451 one such entry in both the Join and Prune lists of a group 5452 specific set. 5454 (*,G) source list entries have the Source-Address set to the 5455 address of the RP for group G, the Source-Address Mask-Len set 5456 to the full length of the IP address and have both the WC and 5457 RPT bits of the Encoded-Source-Address set. 5459 (S,G,rpt) 5460 The (S,G,rpt) source list entry is used in Join / Prune 5461 messages sent towards the RP for the specified group. It 5462 expresses interest (or lack of) in receiving traffic through 5463 the shared tree sent by the specified source to this group. 5464 For each source address the entry may exist in only one of the 5465 Join and Prune source lists of a group specific set but not 5466 both. 5468 (S,G,rpt) source list entries have the Source-Address set to 5469 the address of the source S, the Source-Address Mask-Len set 5470 to the full length of the IP address and have the WC bit clear 5471 and the RPT bit set in the Encoded-Source-Address. 5473 (S,G) 5474 The (S,G) source list entry is used in Join / Prune messages 5475 sent towards the specified source. It expresses interest (or 5476 lack of) in receiving traffic through the shortest path tree 5477 sent by the source to the specified group. For each source 5478 address the entry may exist in only one of the Join and Prune 5479 source lists of a group specific set but not both. 5481 (S,G) source list entries have the Source-Address set to the 5482 address of the source S, the Source-Address Mask-Len set to 5483 the full length of the IP address and have both the WC and RPT 5484 bits of the Encoded-Source-Address cleared. 5486 The rules described above are sufficient to prevent invalid combinations 5487 of source list entries in group-specific sets. There are however a 5488 number of combinations that have a valid interpretation but which are 5489 not generated by the protocol as described in this specification: 5491 o Combining a (*,G) Join and a (S,G,rpt) Join entry in the same message 5492 is redundant as the (*,G) entry covers the information provided by the 5493 (S,G,rpt) entry. 5495 o The same applies for a (*,G) Prunes and (S,G,rpt) Prunes. 5497 o The combination of a (*,G) Prune and a (S,G,rpt) Join is also not 5498 generated. (S,G,rpt) Joins are only sent when the router is receiving 5499 all traffic for a group on the shared tree and it wishes to indicate a 5500 change for the particular source. As a (*,G) prune indicates that the 5501 router no longer wishes to receive shared tree traffic, the (S,G,rpt) 5502 Join would be meaningless. 5504 o As Join / Prune messages are targeted to a single PIM neighbor, 5505 including both a (S,G) Join and a (S,G,rpt) prune in the same message 5506 is redundant. The (S,G) Join informs the neighbor that the sender 5507 wishes to receive the particular source on the shortest path tree. It 5508 is therefore unnecessary for the router to say that it no longer 5509 wishes to receive it on the shared tree. 5511 o The combination of a (S,G) Prune and a (S,G,rpt) Join could possibly 5512 be used by a router to switch from receiving a particular source on 5513 the shortest-path tree back to receiving it on the shared tree 5514 (provided that the RPF neighbor for the shortest-path and shared trees 5515 is common). However Sparse-Mode PIM does not provide a mechanism for 5516 switching back to the shared tree. 5518 The rules are summarized in the tables below. 5520 +----------++------+-------+-----------+-----------+-------+-------+ 5521 | ||Join | Prune | Join | Prune | Join | Prune | 5522 | ||(*,G) | (*,G) | (S,G,rpt) | (S,G,rpt) | (S,G) | (S,G) | 5523 +----------++------+-------+-----------+-----------+-------+-------+ 5524 |Join ||- | no | ? | yes | yes | yes | 5525 |(*,G) || | | | | | | 5526 +----------++------+-------+-----------+-----------+-------+-------+ 5527 |Prune ||no | - | ? | ? | yes | yes | 5528 |(*,G) || | | | | | | 5529 +----------++------+-------+-----------+-----------+-------+-------+ 5530 |Join ||? | ? | - | no | yes | yes | 5531 |(S,G,rpt) || | | | | | | 5532 +----------++------+-------+-----------+-----------+-------+-------+ 5533 |Prune ||yes | ? | no | - | ? | ? | 5534 |(S,G,rpt) || | | | | | | 5535 +----------++------+-------+-----------+-----------+-------+-------+ 5536 |Join ||yes | yes | yes | ? | - | no | 5537 |(S,G) || | | | | | | 5538 +----------++------+-------+-----------+-----------+-------+-------+ 5539 |Prune ||yes | yes | yes | ? | no | - | 5540 |(S,G) || | | | | | | 5541 +----------++------+-------+-----------+-----------+-------+-------+ 5543 +---------------++--------------+----------------+------------+ 5544 | ||Join (*,*,RP) | Prune (*,*,RP) | all others | 5545 +---------------++--------------+----------------+------------+ 5546 |Join (*,*,RP) ||- | no | yes | 5547 +---------------++--------------+----------------+------------+ 5548 |Prune (*,*,RP) ||no | - | yes | 5549 +---------------++--------------+----------------+------------+ 5550 |all others ||yes | yes | see above | 5551 +---------------++--------------+----------------+------------+ 5553 yes Allowed and expected. 5555 no Combination is not allowed by the protocol and MUST NOT be 5556 generated by a router. A router MAY accept these messages but the 5557 result is undefined. An error message MAY be logged to the 5558 administrator in a rate limited manner. 5560 ? Combination not expected by the protocol, but well-defined. A 5561 router MAY accept it but SHOULD NOT generate it. 5563 The order of source list entries in a group set source list is not 5564 important, except where limited by the packet format itself. 5566 4.10.5.2. Group Set Fragmentation 5568 When building a Join / Prune for a particular neighbor, a router should 5569 try and include in the message as much of the information it needs to 5570 convey to the neighbor as possible. This implies adding one group set 5571 for each multicast group that has information pending transmission and 5572 within each set including all relevant source list entries. 5574 On a router with a large amount of multicast state the number of entries 5575 that must be included may result in packets that are larger than the 5576 maximum IP packet size. In most such cases the information may be split 5577 into multiple messages. 5579 There is an exception with group sets that contain a (*,G) Join source 5580 list entry. The group set expresses the router's interest in receiving 5581 all traffic for the specified group on the shared tree and it MUST 5582 include an (S,G,rpt) Prune source list entry for every source that the 5583 router does not wish to receive. This list of (S,G,rpt) Prune source- 5584 list entries MUST not be split in multiple messages. 5586 If only N (S,G,rpt) Prune entries fit into a maximum-sized Join / Prune 5587 message, but the router has more than N (S,G,rpt) Prunes to add, then 5588 the router MUST choose to include the first N (numerically smallest in 5589 network byte order) IP addresses. 5591 4.10.6. Assert Message Format 5593 The Assert message is used to resolve forwarder conflicts between 5594 routers on a link. It is sent when a multicast data packet is received 5595 on an interface that the router would normally forward that packet. 5596 Assert messages may also be sent in response to an Assert message from 5597 another router. 5599 0 1 2 3 5600 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 5601 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5602 |PIM Ver| Type | Reserved | Checksum | 5603 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5604 | Group Address (Encoded-Group format) | 5605 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5606 | Source Address (Encoded-Unicast format) | 5607 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5608 |R| Metric Preference | 5609 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5610 | Metric | 5611 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5613 PIM Version, Type, Reserved, Checksum 5614 Described in Section 4.10. 5616 Group Address 5617 The group address for which the router wishes to resolve the 5618 forwarding conflict. This is an Encoded-Group address, as 5619 specified in Section 4.10.1. 5621 Source Address 5622 Source address for which the router wishes to resolve the 5623 forwarding conflict. The source address MAY be set to zero for 5624 (*,G) asserts (see below). The format for this address is given in 5625 Encoded-Unicast-Address in Section 4.10.1. 5627 R RPT-bit is a 1 bit value. The RPT-bit is set to 1 for Assert(*,G) 5628 messages and 0 for Assert(S,G) messages. 5630 Metric Preference 5631 Preference value assigned to the unicast routing protocol that 5632 provided the route to the multicast source or Rendezvous-Point. 5634 Metric 5635 The unicast routing table metric associated with the route used to 5636 reach the multicast source or Rendezvous-Point. The metric is in 5637 units applicable to the unicast routing protocol used. 5639 Assert messages can be sent to resolve a forwarding conflict for all 5640 traffic to given group or for a specific source and group. 5642 Assert(S,G) 5643 Source specific asserts are sent by routers forwarding a specific 5644 source on the shortest-path tree (SPT bit is TRUE). (S,G) Asserts 5645 have the Group-Address field set to the group G and the Source- 5646 Address field set to the source S. The RPT-bit is set to 0, the 5647 Metric-Preference is set to MRIB.pref(S) and the Metric is set to 5648 MRIB.metric(S). 5650 Assert(*,G) 5651 Group specific asserts are sent by routers forwarding data for the 5652 group and source(s) under contention on the shared tree. (*,G) 5653 asserts have the Group-Address field set to the group G. For data 5654 triggered Asserts the Source-Address field MAY be set to the IP 5655 source address of the data packet that triggered the Assert and is 5656 set to zero otherwise. The RPT-bit is set to 1, the Metric- 5657 Preference is set to MRIB.pref(RP(G)) and the Metric is set to 5658 MRIB.metric(RP(G)). 5660 4.11. PIM Timers 5662 PIM-SM maintains the following timers, as discussed in Section 4.1. All 5663 timers are countdown timers - they are set to a value and count down to 5664 zero, at which point they typically trigger an action. Of course they 5665 can just as easily be implemented as count-up timers, where the absolute 5666 expiry time is stored and compared against a real-time clock, but the 5667 language in this specification assumes that they count downwards to 5668 zero. 5670 Global Timers 5672 Per interface (I): 5674 Hello Timer: HT(I) 5676 Per neighbor (N): 5678 Neighbor Liveness Timer: NLT(N,I) 5680 Per active RP (RP): 5682 (*,*,RP) Join Expiry Timer: ET(*,*,RP,I) 5684 (*,*,RP) Prune-Pending Timer: PPT(*,*,RP,I) 5686 Per Group (G): 5688 (*,G) Join Expiry Timer: ET(*,G,I) 5690 (*,G) Prune-Pending Timer: PPT(*,G,I) 5692 (*,G) Assert Timer: AT(*,G,I) 5694 Per Source (S): 5696 (S,G) Join Expiry Timer: ET(S,G,I) 5698 (S,G) Prune-Pending Timer: PPT(S,G,I) 5700 (S,G) Assert Timer: AT(S,G,I) 5702 (S,G,rpt) Prune Expiry Timer: ET(S,G,rpt,I) 5704 (S,G,rpt) Prune-Pending Timer: PPT(S,G,rpt,I) 5706 Per active RP (RP): 5708 (*,*,RP) Upstream Join Timer: JT(*,*,RP) 5710 Per Group (G): 5712 (*,G) Upstream Join Timer: JT(*,G) 5714 Per Source (S): 5716 (S,G) Upstream Join Timer: JT(S,G) 5718 (S,G) Keepalive Timer: KAT(S,G) 5720 (S,G,rpt) Upstream Override Timer: OT(S,G,rpt) 5722 At the DRs or relevant Assert Winners only: 5724 Per Source,Group pair (S,G): 5726 Register-Stop Timer: RST(S,G) 5728 4.12. Timer Values 5730 When timers are started or restarted, they are set to default values. 5731 This section summarizes those default values. 5733 Note that protocol events or configuration may change the default value 5734 of a timer on a specific interface. When timers are initialized in this 5735 document the value specific to the interface in context must be used. 5737 Some of the timers listed below (Prune-Pending, Upstream Join, Upstream 5738 Override) can be set to values which depend on the settings of the 5739 Propagation Delay and Override_Interval of the corresponding interface. 5740 The default values for these are given below. Note that the value of 5741 both the Propagation Delay and Override Interval of an interface can 5742 change as a result of receiving Hello messages on that interface 5743 (Section 4.3.3). 5745 Variable Name: Propagation_Delay(I) 5747 +-------------------------+-------------------+-------------------------+ 5748 | Value Name | Value | Explanation | 5749 +-------------------------+-------------------+-------------------------+ 5750 | LAN_delay_default | 0.5 secs | Expected | 5751 | | | propagation delay | 5752 | | | over the local | 5753 | | | link. | 5754 +-------------------------+-------------------+-------------------------+ 5756 The default value of the LAN_delay_default is chosen to be relatively 5757 large to provide compatibility with older PIM implementations. 5759 Variable Name: Override_Interval(I) 5761 +--------------------------+-----------------+--------------------------+ 5762 | Value Name | Value | Explanation | 5763 +--------------------------+-----------------+--------------------------+ 5764 | t_override_default | 2.5 secs | Default delay | 5765 | | | interval over | 5766 | | | which to randomize | 5767 | | | when scheduling a | 5768 | | | delayed Join | 5769 | | | message. | 5770 +--------------------------+-----------------+--------------------------+ 5771 Timer Name: Hello Timer (HT(I)) 5773 +----------------------+---------+---------------------------------------+ 5774 |Value Name | Value | Explanation | 5775 +----------------------+---------+---------------------------------------+ 5776 |Hello_Period | 30 secs | Periodic interval for Hello messages. | 5777 +----------------------+---------+---------------------------------------+ 5778 |Triggered_Hello_Delay | 5 secs | Randomized interval for initial Hello | 5779 | | | message on bootup or triggered Hello | 5780 | | | message to a rebooting neighbor. | 5781 +----------------------+---------+---------------------------------------+ 5783 At system power-up, the timer is initialized to rand(0, 5784 Triggered_Hello_Delay) to prevent synchronization. When a new or 5785 rebooting neighbor is detected, a responding Hello is sent within 5786 rand(0, Triggered_Hello_Delay). 5788 Timer Name: Neighbor Liveness Timer (NLT(N,I)) 5790 +--------------------------+-----------------------+--------------------+ 5791 | Value Name | Value | Explanation | 5792 +--------------------------+-----------------------+--------------------+ 5793 | Default_Hello_Holdtime | 3.5 * Hello_Period | Default holdtime | 5794 | | | to keep neighbor | 5795 | | | state alive | 5796 +--------------------------+-----------------------+--------------------+ 5797 | Hello_Holdtime | from message | Holdtime from | 5798 | | | Hello Message | 5799 | | | Holdtime option. | 5800 +--------------------------+-----------------------+--------------------+ 5802 The Holdtime in a Hello Message should be set to (3.5 * Hello_Period), 5803 giving a default value of 105 seconds. 5805 Timer Names: Expiry Timer (ET(*,*,RP,I), ET(*,G,I), ET(S,G,I), 5806 ET(S,G,rpt,I)) 5808 +----------------+-----------------+------------------------------------+ 5809 | Value Name | Value | Explanation | 5810 +----------------+-----------------+------------------------------------+ 5811 | J/P_HoldTime | from message | Holdtime from Join/Prune Message | 5812 +----------------+-----------------+------------------------------------+ 5814 See details of JT(*,G) for the Holdtime that is included in Join/Prune 5815 Messages. 5817 Timer Names: Prune-Pending Timer (PPT(*,*,RP,I), PPT(*,G,I), PPT(S,G,I), 5818 PPT(S,G,rpt,I)) 5820 +-----------------------------+-----------------+-----------------------+ 5821 | Value Name | Value | Explanation | 5822 +-----------------------------+-----------------+-----------------------+ 5823 | J/P_Override_Interval(I) | Default: | Short period after | 5824 | | Propagation_ | a join or prune to | 5825 | | Delay(I) + | allow other | 5826 | | Override_ | routers on the LAN | 5827 | | Interval(I) | to override the | 5828 | | | join or prune | 5829 +-----------------------------+-----------------+-----------------------+ 5831 Note that both the Propagation_Delay(I) and the Override_Interval(I) are 5832 interface specific values that may change when Hello messages are 5833 received. 5835 Timer Names: Assert Timer (AT(*,G,I), AT(S,G,I)) 5837 +---------------------------+----------------------+--------------------+ 5838 | Value Name | Value | Explanation | 5839 +---------------------------+----------------------+--------------------+ 5840 | Assert_Override_Interval | Default: 3 secs | Short interval | 5841 | | | before an assert | 5842 | | | times out where | 5843 | | | the assert winner | 5844 | | | resends an Assert | 5845 | | | message | 5846 +---------------------------+----------------------+--------------------+ 5847 | Assert_Time | Default: 180 secs | Period after last | 5848 | | | assert before | 5849 | | | assert state is | 5850 | | | timed out | 5851 +---------------------------+----------------------+--------------------+ 5853 Note that for historical reasons, the Assert message lacks a Holdtime 5854 field. Thus changing the Assert Time from the default value is not 5855 recommended. 5857 Timer Names: Upstream Join Timer (JT(*,*,RP), JT(*,G), JT(S,G)) 5859 +-------------+-------------------+-------------------------------------+ 5860 |Value Name | Value | Explanation | 5861 +-------------+-------------------+-------------------------------------+ 5862 |t_periodic | Default: 60 secs | Period between Join/Prune Messages | 5863 +-------------+-------------------+-------------------------------------+ 5864 |t_suppressed | rand(1.1 * | Suppression period when someone | 5865 | | t_periodic, 1.4 * | else sends a J/P message so we | 5866 | | t_periodic) when | don't need to do so. | 5867 | | Suppression_ | | 5868 | | Enabled(I) is | | 5869 | | true, 0 otherwise | | 5870 +-------------+-------------------+-------------------------------------+ 5871 |t_override | rand(0, Override_ | Randomized delay to prevent | 5872 | | Interval(I)) | response implosion when sending a | 5873 | | | join message to override someone | 5874 | | | else's Prune message. | 5875 +-------------+-------------------+-------------------------------------+ 5877 t_periodic may be set to take into account such things as the configured 5878 bandwidth and expected average number of multicast route entries for the 5879 attached network or link (e.g., the period would be longer for lower- 5880 speed links, or for routers in the center of the network that expect to 5881 have a larger number of entries). If the Join/Prune-Period is modified 5882 during operation, these changes should be made relatively infrequently 5883 and the router should continue to refresh at its previous Join/Prune- 5884 Period for at least Join/Prune-Holdtime, in order to allow the upstream 5885 router to adapt. 5887 The holdtime specified in a Join/Prune message should be set to (3.5 * 5888 t_periodic). 5890 t_override depends on the Override Interval of the upstream interface 5891 which may change when Hello messages are received. 5893 t_suppressed depends on the Suppression State of the upstream interface 5894 (Section 4.3.3) and becomes zero when suppression is disabled. 5896 Timer Name: Upstream Override Timer (OT(S,G,rpt)) 5898 +---------------+---------------------------+---------------------------+ 5899 | Value Name | Value | Explanation | 5900 +---------------+---------------------------+---------------------------+ 5901 | t_override | see Upstream Join Timer | see Upstream Join Timer | 5902 +---------------+---------------------------+---------------------------+ 5904 The upstream Override Timer is only ever set to t_override; this value 5905 is defined in the section on Upstream Join Timers. 5907 Timer Name: Keepalive Timer (KAT(S,G)) 5909 +-----------------------+------------------------+----------------------+ 5910 | Value Name | Value | Explanation | 5911 +-----------------------+------------------------+----------------------+ 5912 | Keepalive_Period | Default: 210 secs | Period after last | 5913 | | | (S,G) data packet | 5914 | | | during which (S,G) | 5915 | | | Join state will be | 5916 | | | maintained even in | 5917 | | | the absence of | 5918 | | | (S,G) Join | 5919 | | | messages. | 5920 +-----------------------+------------------------+----------------------+ 5921 | RP_Keepalive_Period | ( 3 * Register_ | As | 5922 | | Suppression_Time ) | Keepalive_Period, | 5923 | | + Register_ | but at the RP when | 5924 | | Probe_Time | a Register-Stop is | 5925 | | | sent. | 5926 +-----------------------+------------------------+----------------------+ 5927 The normal keepalive period for the KAT(S,G) defaults to 210 seconds. 5928 However at the RP, the keepalive period must be at least the 5929 Register_Suppression_Time or the RP may time out the (S,G) state before 5930 the next Null-Register arrives. Thus the KAT(S,G) is set to 5931 max(Keepalive_Period, RP_Keepalive_Period) when a Register-Stop is sent. 5933 Timer Name: Register-Stop Timer (RST(S,G)) 5935 +----------------------------+--------------------+---------------------+ 5936 |Value Name | Value | Explanation | 5937 +----------------------------+--------------------+---------------------+ 5938 |Register_Suppression_Time | Default: 60 secs | Period during | 5939 | | | which a DR stops | 5940 | | | sending Register- | 5941 | | | encapsulated data | 5942 | | | to the RP after | 5943 | | | receiving a | 5944 | | | Register-Stop | 5945 | | | message. | 5946 +----------------------------+--------------------+---------------------+ 5947 |Register_Probe_Time | Default: 5 secs | Time before RST | 5948 | | | expires when a DR | 5949 | | | may send a Null- | 5950 | | | Register to the RP | 5951 | | | to cause it to | 5952 | | | resend a Register- | 5953 | | | Stop message. | 5954 +----------------------------+--------------------+---------------------+ 5956 5. IANA Considerations 5958 5.1. PIM Address Family 5960 The PIM Address Family field was chosen to be 8 bits as a tradeoff 5961 between packet format and use of the IANA assigned numbers. Since when 5962 the PIM packet format was designed only 15 values were assigned for 5963 Address Families, and large numbers of new Address Family values were 5964 not envisioned, 8 bits seemed large enough. However, the IANA assigns 5965 Address Families in a 16-bit field. Therefore, the PIM Address Family 5966 is allocated as follows: 5968 Values 0 through 127 are designated to have the same meaning as 5969 IANA-assigned Address Family Numbers [7]. 5971 Values 128 through 250 are designated to be assigned by the IANA 5972 based upon IESG Approval, as defined in [10]. 5974 Values 251 through 255 are designated for Private Use, as defined 5975 in [10]. 5977 5.2. PIM Hello Options 5979 Values 17 through 65000 are to be assigned by the IANA. Since the space 5980 is large, they may be assigned as First Come First Served as defined in 5981 [10]. Such assignments are valid for one year, and may be renewed. 5982 Permanent assignments require a specification (see "Specification 5983 Required" in [10].) 5985 6. Security Considerations 5987 The IPsec authentication header [8] MAY be used to provide data 5988 integrity protection and groupwise data origin authentication of PIM 5989 protocol messages. Authentication of PIM messages can protect against 5990 unwanted behaviors caused by unauthorized or altered PIM messages. 5992 6.1. Attacks based on forged messages 5994 The extent of possible damage depends on the type of counterfeit 5995 messages accepted. We next consider the impact of possible forgeries, 5996 including forged link-local (Join/Prune, Hello, and Assert) and forged 5997 unicast (Register and Register-Stop) messages. 5999 6.1.1. Forged link-local messages 6001 Join/Prune, Hello, and Assert messages are all sent to the link-local 6002 ALL_PIM_ROUTERS multicast addresses, and thus are not forwarded by a 6003 compliant router. A forged message of this type can only reach a LAN if 6004 it was sent by a local host or if it was allowed onto the LAN by a 6005 compromised or non-compliant router. 6007 1. A forged Join/Prune message can cause multicast traffic to be 6008 delivered to links where there are no legitimate requesters, 6009 potentially wasting bandwidth on that link. A forged leave message 6010 on a multi-access LAN is generally not a significant attack in PIM, 6011 because any legitimately joined router on the LAN would override 6012 the leave with a join before the upstream router stops forwarding 6013 data to the LAN. 6015 2. By forging a Hello message, an unauthorized router can cause 6016 itself to be elected as the designated router on a LAN. The 6017 designated router on a LAN is (in the absence of asserts) 6018 responsible for forwarding traffic to that LAN on behalf of any 6019 local members. The designated router is also responsible for 6020 register-encapsulating to the RP any packets that are originated by 6021 hosts on the LAN. Thus, the ability of local hosts to send and 6022 receive multicast traffic may be compromised by a forged Hello 6023 message. 6025 3. By forging an Assert message on a multi-access LAN, an attacker 6026 could cause the legitimate designated forwarder to stop forwarding 6027 traffic to the LAN. Such a forgery would prevent any hosts 6028 downstream of that LAN from receiving traffic. 6030 6.1.2. Forged unicast messages 6032 Register messages and Register-Stop messages are forwarded by 6033 intermediate routers to their destination using normal IP forwarding. 6034 Without data origin authentication, an attacker who is located anywhere 6035 in the network may be able to forge a Register or Register-Stop message. 6036 We consider the effect of a forgery of each of these messages next. 6038 1 By forging a Register message, an attacker can cause the RP to 6039 inject forged traffic onto the shared multicast tree. 6041 2 By forging a Register-stop message, an attacker can prevent a 6042 legitimate DR from Registering packets to the RP. This can prevent 6043 local hosts on that LAN from sending multicast packets. 6045 The above two PIM messages are not changed by intermediate routers and 6046 need only be examined by the intended receiver. Thus these messages can 6047 be authenticated end-to-end, using AH. Attacks on Register and 6048 Register-Stop messages do not apply to a PIM-SSM-only implementation, as 6049 these messages are not required for PIM-SSM. 6051 6.2. Non-cryptographic Authentication Mechanisms 6053 A PIM router SHOULD provide an option to limit the set of neighbors from 6054 which it will accept Join/Prune, Assert, and Hello messages. Either 6055 static configuration of IP addresses or an IPsec security association 6056 may be used. Furthermore, a PIM router SHOULD NOT accept protocol 6057 messages from a router from which it has not yet received a valid Hello 6058 message. 6060 A Designated Router MUST NOT register-encapsulate a packet and send it 6061 to the RP unless the source address of the packet is a legal address for 6062 the subnet on which the packet was received. Similarly, a Designated 6063 Router SHOULD NOT accept a Register-Stop packet whose IP source address 6064 is not a valid RP address for the local domain. 6066 An implementation SHOULD provide a mechanism to allow an RP to restrict 6067 the range of source addresses from which it accepts Register- 6068 encapsulated packets. 6070 All options that restrict the range of addresses from which packets are 6071 accepted MUST default to allowing all packets. 6073 6.3. Authentication using IPsec 6075 The IPsec [8] transport mode using the Authentication Header (AH) is the 6076 recommended method to prevent the above attacks against PIM. The 6077 specific AH authentication algorithm and parameters, including the 6078 choice of authentication algorithm and the choice of key, are configured 6079 by the network administrator. When IPsec authentication is used, a PIM 6080 router should reject (drop without processing) any unauthorized PIM 6081 protocol messages. 6083 As of this writing, the IPsec anti-replay option does not handle the 6084 case of a Security Association identified by a multicast destination 6085 address. Thus, the anti-replay option currently must be disabled on 6086 these Security Associations. Until replay prevention for link-local 6087 multicast messages is addressed (one such proposal is [9] ), the anti- 6088 replay option SHOULD be enabled on all security associations having a 6089 unicast destination address. 6091 To use IPsec, the administrator of a PIM network configures each PIM 6092 router with one or more Security Associations and associated SPI(s) that 6093 are used by senders to sign PIM protocol messages and are used by 6094 receivers to authenticate received PIM protocol messages. This document 6095 does not describe protocols for establishing Security Associations. It 6096 assumes that manual configuration of Security Associations is performed, 6097 but it does not preclude the use of a negotiation protocol such as The 6098 Internet Key Exchange [15] to establish Security Associations. 6100 The following sections describe the Security Associations required to 6101 protect PIM protocol messages. 6103 6.3.1. Protecting link-local multicast messages 6105 The network administrator defines a Security Association (SA) and 6106 Security Parameters Index (SPI) that is to be used to authenticate all 6107 link-local PIM protocol messages (Hello, Join/Prune, and Assert) on each 6108 link in a PIM domain. All link-local PIM protocol messages use SPI 0. 6110 The Security Policy Database at a PIM router should be configured to 6111 ensure that all incoming and outgoing Join/Prune, Assert, and Hello 6112 packets use the SA associated with the interface to which the packet is 6113 sent. 6115 Note that, according to [8] there is nominally a different Security 6116 Association Database (SAD) for each router interface. Thus, the 6117 selected Security Association for an inbound PIM packet can vary 6118 depending on the interface on which the packet arrived. This fact 6119 allows the network administrator to use different authentication methods 6120 for each link, even though the destination address is the same for all 6121 link-local PIM packets, regardless of interface. 6123 6.3.2. Protecting unicast messages 6125 IPSec can also be used to provide data origin authentication and data 6126 integrity protection for the Register and Register-Stop unicast 6127 messages. 6129 6.3.2.1. Register messages 6131 The Security Policy Database at every PIM router is configured to select 6132 a Security Association to use when sending PIM Register packets to each 6133 rendezvous point. 6135 In the most general mode of operation, the Security Policy Database at 6136 each DR is configured to select a unique SA and SPI for traffic sent to 6137 each RP. This allows each DR to have a different authentication 6138 algorithm and key to talk to the RP. However, this creates a daunting 6139 key management and distribution problem for the network administrator. 6140 Therefore, it may be preferable in PIM domains where all Designated 6141 Routers are under a single administrative control, to use the same 6142 authentication algorithm parameters (including the key) for all 6143 Registered packets in a domain, regardless of who is the RP and 6144 regardless of who is the DR. 6146 In this "single shared key" mode of operation, the network administrator 6147 must choose an SPI for each DR that will be used to send it PIM protocol 6148 packets. The Security Policy Database at every DR is configured to 6149 select a Security Association (including the authentication algorithm, 6150 authentication parameters, and this SPI) when sending Register messages 6151 to this RP. 6153 By using a single authentication algorithm and associated parameters, 6154 the key distribution problem is simplified. Note however, that this 6155 method has the property that, in order to change the authentication 6156 method or authentication key used, all routers in the domain must be 6157 updated. 6159 6.3.2.2. Register-Stop messages 6161 Similarly, the Security Policy Database at each Rendezvous Point should 6162 be configured to choose a Security Association to use when sending 6163 Register-Stop messages. Because Register-Stop messages are unicast to 6164 the destination DR, a different Security Association and a potentially 6165 unique SPI is required for each DR. 6167 In order to simplify the management problem, it may be acceptable to use 6168 the same authentication algorithm and authentication parameters, 6169 regardless of the sending RP and regardless of the destination DR. 6170 Although a unique Security Association is needed for each DR, the same 6171 authentication algorithm and authentication algorithm parameters (secret 6172 key) can be shared by all DRs and by all RPs. 6174 6.4. Denial of Service Attacks 6176 There are a number of possible denial of service attacks against PIM 6177 that can be caused by generating false PIM protocol messages or even by 6178 generating data false traffic. Authenticating PIM protocol traffic 6179 prevents some, but not all of these attacks. Two of the possible 6180 attacks include: 6182 - Sending packets to many different group addresses quickly can be a 6183 denial of service attack in and of itself. This will cause many 6184 register-encapsulated packets, loading the DR, the RP, and the 6185 routers between the DR and the RP. 6187 - Forging Join messages can cause a multicast tree to get set up. A 6188 large number of forged joins can consume router resources and 6189 result in denial of service. 6191 7. Authors' Addresses 6193 Bill Fenner 6194 AT&T Labs - Research 6195 75 Willow Road 6196 Menlo Park, CA 94025 6197 fenner@research.att.com 6199 Mark Handley 6200 ICIR/ICSI 6201 1947 Center St, Suite 600 6202 Berkeley, CA 94708 6203 mjh@icir.org 6205 Hugh Holbrook 6206 Cisco Systems 6207 170 W. Tasman Drive 6208 San Jose, CA 95134 6209 holbrook@cisco.com 6210 Isidor Kouvelas 6211 Cisco Systems 6212 170 W. Tasman Drive 6213 San Jose, CA 95134 6214 kouvelas@cisco.com 6216 8. Acknowledgments 6218 PIM-SM was designed over many years by a large group of people, 6219 including ideas, comments, and corrections from Deborah Estrin, Dino 6220 Farinacci, Ahmed Helmy, David Thaler, Steve Deering, Van Jacobson, C. 6221 Liu, Puneet Sharma, Liming Wei, Tom Pusateri, Tony Ballardie, Scott 6222 Brim, Jon Crowcroft, Paul Francis, Joel Halpern, Horst Hodel, Polly 6223 Huang, Stephen Ostrowski, Lixia Zhang, Girish Chandranmenon, Brian 6224 Haberman, Hal Sandick, Mike Mroz, Garry Kump, Pavlin Radoslavov, Mike 6225 Davison and James Lingard. 6227 Thanks are due to the American Licorice Company, for its obscure but 6228 possibly essential role in the creation of this document. 6230 9. Normative References 6232 [1] D. Black, "Differentiated Services and Tunnels", RFC 2983. 6234 [2] S.E. Deering, "Host extensions for IP multicasting", RFC 1112, Aug 6235 1989. 6237 [3] S. Deering, W. Fenner, B. Haberman, "Multicast Listener Discovery 6238 (MLD) for IPv6", RFC 2710. 6240 [4] S. Deering, R. Hinden, "Internet Protocol, Version 6 (IPv6) 6241 Specification", RFC 2460. 6243 [5] B. Cain, S. Deering, I. Kouvelas, B. Fenner, A. Thyagarajan, 6244 "Internet Group Management Protocol, Version 3", RFC 3376. 6246 [6] H. Holbrook, B. Cain, "Source-Specific Multicast for IP", draft- 6247 ietf-ssm-arch-04.txt, work in progress. 6249 [7] IANA, "Address Family Numbers", linked from 6250 http://www.iana.org/numbers.html 6252 [8] S. Kent, R. Atkinson, "Security Architecture for the Internet 6253 Protocol.", RFC 2401. 6255 [9] S. Kent, "IP Encapsulating Security Payload (ESP)", draft-ietf- 6256 ipsec-esp-v3-06.txt, work in progress. 6258 [10] T. Narten , H. Alvestrand, "Guidelines for Writing an IANA 6259 Considerations Section in RFCs", RFC 2434. 6261 [11] D. Thaler, "Interoperability Rules for Multicast Routing 6262 Protocols", RFC 2715. 6264 10. Informative References 6266 [12] T. Bates , R. Chandra , D. Katz , Y. Rekhter, "Multiprotocol 6267 Extensions for BGP-4", RFC 2283 6269 [13] W. Fenner, M. Handley, R. Kermode, D. Thaler, "Bootstrap Router 6270 (BSR) Mechanism for PIM Sparse Mode", draft-ietf-pim-sm-bsr-03.txt, 6271 work in progress. 6273 [14] M. Handley, I. Kouvelas, T. Speakman, L. Vicisano, "Bi-directional 6274 Protocol Independent Multicast", draft-ietf-pim-bidir-05.txt, work 6275 in progress. 6277 [15] D. Harkins, D. Carrell, "The Internet Key Exchange (IKE)", RFC 6278 2409. 6280 11. Index 6281 Assert(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .27,130 6282 Assert(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .27,130 6283 AssertCancel(*,G). . . . . . . . . . . . . . . . . . . . . . . . . 97,99 6284 AssertCancel(S,G). . . . . . . . . . . . . . . . . . . . . . . .79,90,99 6285 AssertTimer(*,G,I) . . . . . . . . . . . . . . . . . . . . .16,24,91,134 6286 AssertTimer(S,G,I) . . . . . . . . . . . . . . . . . . . . .18,24,83,134 6287 AssertTrackingDesired(*,G,I) . . . . . . . . . . . . . . . . . .93,94,96 6288 AssertTrackingDesired(S,G,I) . . . . . . . . . . . . . . . . 85,85,87,89 6289 AssertWinner(*,G,I). . . . . . . . . . . . . . . . . . . 22,24,93,97,100 6290 AssertWinner(S,G,I). . . . . . . . . . . . . . . . . .22,24,85,89,99,100 6291 AssertWinnerMetric(*,G,I). . . . . . . . . . . . . . . . . . . . .97,100 6292 AssertWinnerMetric(S,G,I). . . . . . . . . . . . . . . . . . . . .89,100 6293 assert_metric. . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6294 Assert_Override_Interval . . . . . . . . . . . . . . . . . . . 89,96,134 6295 Assert_Time. . . . . . . . . . . . . . . . . . . . . . . . . . 89,96,134 6296 AT(*,G,I). . . . . . . . . . . . . . . . . . . . . . . .16,24,91,131,134 6297 AT(S,G,I). . . . . . . . . . . . . . . . . . . . . . . .18,24,83,131,134 6298 CheckSwitchToSpt(S,G). . . . . . . . . . . . . . . . . . . . . . . 27,28 6299 CouldAssert(*,G,I) . . . . . . . . . . . . . . . . . . . .91,93,94,95,98 6300 CouldAssert(S,G,I) . . . . . . . . . . . . . . . . . . 83,85,87,88,89,98 6301 CouldRegister(S,G) . . . . . . . . . . . . . . . . . . . . . . . . 38,40 6302 Default_Hello_Holdtime . . . . . . . . . . . . . . . . . . . . . . . 33 6303 DirectlyConnected(S) . . . . . . . . . . . . . . . . . . 27,27,29,40,103 6304 DownstreamJPState(*,*,RP,I). . . . . . . . . . . . . . . . . . . .23,104 6305 DownstreamJPState(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 23 6306 DownstreamJPState(S,G,I) . . . . . . . . . . . . . . . . . . . . . 23,40 6307 DownstreamJPState(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . 23 6308 DR(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6309 dr_is_better(a,b,I). . . . . . . . . . . . . . . . . . . . . . . . 33,33 6310 DR_Priority. . . . . . . . . . . . . . . . . . . . . . . . . . .31,32,33 6311 ET(*,*,RP,I) . . . . . . . . . . . . . . . . . . . . . . . 15,45,130,133 6312 ET(*,G,I). . . . . . . . . . . . . . . . . . . . . . . . . 16,49,131,133 6313 ET(S,G,I). . . . . . . . . . . . . . . . . . . . . . . . . 18,53,131,133 6314 ET(S,G,rpt,I). . . . . . . . . . . . . . . . . . . . . .20,56,58,131,133 6315 GenID. . . . . . . . . . . . . . . . . . . 16,18,19,31,63,67,70,72,83,91 6316 Hash_Function. . . . . . . . . . . . . . . . . . . . . . . . . . .13,107 6317 Hello_Holdtime . . . . . . . . . . . . . . . . . . . . . . . . . .33,133 6318 Hello_Period . . . . . . . . . . . . . . . . . . . . . . . . . . .31,133 6319 HT(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31,133 6320 IGMP . . . . . . . . . . . . . . . . . . . . . . . . . 7,9,17,23,101,107 6321 immediate_olist(*,*,RP). . . . . . . . . . . . . . . . . . . . . . 21,63 6322 immediate_olist(*,G) . . . . . . . . . . . . . . . . . . . . . . . 22,68 6323 immediate_olist(S,G) . . . . . . . . . . . . . . . . . . . . . .22,40,72 6324 infinite_assert_metric() . . . . . . . . . . . . . . . . . . . . . . 98 6325 inherited_olist(S,G) . . . . . . . . . . . . . . . . .22,27,43,72,85,110 6326 inherited_olist(S,G,rpt) . . . . . . . . . . . . . . . 22,27,29,76,78,80 6327 Interface_Address_List . . . . . . . . . . . . . . . . . . . . . . . 31 6328 I_Am_Assert_Loser(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 24 6329 I_Am_Assert_Loser(S,G,I) . . . . . . . . . . . . . . . . . . . . . . 24 6330 I_am_DR(I) . . . . . . . . . . . . . . . . . . . . . . . .22,33,40,85,93 6331 I_am_RP(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43,43 6332 J/P_Holdtime . . . . . . . . . . . . . .46,51,54,58,64,69,74,123,133,135 6333 J/P_Override_Interval(I) . . . . . . . . . . . . . . 47,51,54,58,123,134 6334 JoinDesired(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . 63,77 6335 JoinDesired(*,G) . . . . . . . . . . . . . . . . . . . . .17,68,77,85,97 6336 JoinDesired(S,G) . . . . . . . . . . . . . . . . . . . 19,29,72,85,88,90 6337 joins(*,*,RP(G)) . . . . . . . . . . . . . . . . . . . . . . . . . . 22 6338 joins(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . 21,23,85,93 6339 joins(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 22,23,85,93 6340 joins(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . .22,23,85 6341 JT(*,*,RP) . . . . . . . . . . . . . . . . . . . . . . . . 15,61,131,135 6342 JT(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . 17,66,131,135 6343 JT(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . 18,71,131,135 6344 KAT(S,G) . . . . . . . . . . . . . . . .18,26,27,28,40,43,72,110,131,136 6345 KeepaliveTimer(S,G). . . . . . . . . 18,26,27,27,28,40,43,72,110,131,136 6346 Keepalive_Period . . . . . . . . . . . . . . . . . . . . . . . . .27,136 6347 LAN_delay_default. . . . . . . . . . . . . . . . . . . . . . . . .35,132 6348 lan_delay_enabled(I) . . . . . . . . . . . . . . . . . . . . . . . 34,36 6349 LAN_Prune_Delay. . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6350 local_receiver_exclude(S,G,I). . . . . . . . . . . . . . . . . . . . 23 6351 local_receiver_include(*,G,I). . . . . . . . . . . . . . . . . 23,93,104 6352 local_receiver_include(S,G,I). . . . . . . . . . . . . . . . . . . 23,85 6353 local_receiver_include(S,G,I). . . . . . . . . . . . . . . . . . . . 104 6354 lost_assert(*,G) . . . . . . . . . . . . . . . . . . . . . . . .22,24,85 6355 lost_assert(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 22,24,100 6356 lost_assert(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 22,24 6357 lost_assert(S,G,I) . . . . . . . . . . . . . . . . . . . . . . .22,24,99 6358 lost_assert(S,G,rpt) . . . . . . . . . . . . . . . . . . . . . . . . 24 6359 lost_assert(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . . . 24,99 6360 MBGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7,8 6361 MFIB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7,13 6362 MLD. . . . . . . . . . . . . . . . . . . . . . . . . . 7,9,17,23,101,107 6363 MRIB . . . . . . . . . . . . . . .7,8,12,16,19,25,61,64,65,75,98,105,130 6364 MRIB.next_hop(host). . . . . . . . . . . . . . . . . . . . . 24,25,61,63 6365 my_assert_metric(S,G,I). . . . . . . . . . . . . . . . . .85,89,91,93,98 6366 NBR(Interface,IP_address). . . . . . . . . . . . . . . . .25,36,61,63,64 6367 NLT(N,I) . . . . . . . . . . . . . . . . . . . . . . . . . 15,33,130,133 6368 OT(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . 20,76,131,136 6369 Override_Interval(I) . . . . . . . . . . . . . . 14,31,34,36,116,132,134 6370 packet_arrives_on_rp_tunnel(pkt) . . . . . . . . . . . . . . . . . . 43 6371 pim_exclude(S,G) . . . . . . . . . . . . . . . . . . . . . . 22,22,28,85 6372 pim_include(*,G) . . . . . . . . . . . . . . . . . . . 17,22,22,28,85,93 6373 pim_include(S,G) . . . . . . . . . . . . . . . . . . . . .19,22,22,28,85 6374 PPT(*,*,RP,I). . . . . . . . . . . . . . . . . . . . . . . 15,46,130,134 6375 PPT(*,G,I) . . . . . . . . . . . . . . . . . . . . . . . . 16,49,131,134 6376 PPT(S,G,I) . . . . . . . . . . . . . . . . . . . . . . . . 18,53,131,134 6377 PPT(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . .20,56,58,131,134 6378 Propagation_Delay(I) . . . . . . . . . . . . . . . . . . . 31,35,132,134 6379 PruneDesired(S,G,rpt). . . . . . . . . . . . . . . . . . . . 78,79,88,90 6380 prunes(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . .22,23,85 6381 Register-Stop(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 41 6382 Register-Stop(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 43 6383 Register-StopTimer(S,G). . . . . . . . . . . . . . . . . . 38,39,131,137 6384 Register_Probe_Time. . . . . . . . . . . . . . . . . . . . . . 39,44,137 6385 Register_Suppression_Time. . . . . . . . . . . . . . . . . . . 39,44,137 6386 RP(G). . . . . . . . . . . . . . 6,22,24,40,43,49,68,76,85,93,98,101,130 6387 RPF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6388 RPF'(*,G). . . . . . . . . . . . . . . . . . 24,29,66,67,70,76,77,97,100 6389 RPF'(S,G). . . . . . . . . . . . . . . . . . . . . 25,29,71,76,77,90,100 6390 RPF'(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . .24,76,78,101 6391 RPF_interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6392 RPF_interface(host). . . . . . . . 24,27,29,40,68,69,74,85,93,99,103,110 6393 RPTJoinDesired(G). . . . . . . . . . . . . . . . . . . . . . . .77,80,93 6394 rpt_assert_metric(G,I) . . . . . . . . . . . . . . . . . . . . . . 96,98 6395 RST(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 38,39,131,137 6396 SPTbit(S,G). . . . . . . . . .20,27,29,43,52,73,76,78,85,85,89,90,99,110 6397 spt_assert_metric(S,I) . . . . . . . . . . . . . . . . . . . . .89,98,99 6398 SSM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11,108 6399 Suppression_Enabled(I) . . . . . . . . . . . . . . . . . . . . . .36,135 6400 SwitchToSptDesired(S,G). . . . . . . . . . . . . . . . . . . . .28,28,43 6401 TIB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7,13,26 6402 Triggered_Hello_Delay. . . . . . . . . . . . . . . . . . . . . 31,32,133 6403 t_joinsuppress . . . . . . . . . . . . . . . . . . . . . .63,64,67,69,74 6404 t_override . . . . . . . . . . . . . . . . . . . . . 63,67,72,77,135,136 6405 t_override_default . . . . . . . . . . . . . . . . . . . . . . . .36,132 6406 t_periodic . . . . . . . . . . . . . . . . . . . . . . . . .63,67,72,135 6407 t_suppressed . . . . . . . . . . . . . . . . . . . . .36,64,69,72,74,135 6408 Update_SPTbit(S,G,iif) . . . . . . . . . . . . . . . . . . . . . . 27,29 6409 UpstreamJPState(S,G) . . . . . . . . . . . . . . . . . . . . . . .27,110