idnits 2.17.1 draft-ietf-pim-rfc4601bis-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- == 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. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 23, 2015) is 3343 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: None ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: 'Actions A1' on line 3597 -- Looks like a reference, but probably isn't: 'Actions A6' on line 3241 -- Looks like a reference, but probably isn't: 'Actions A3' on line 3608 -- Looks like a reference, but probably isn't: 'Actions A2' on line 3608 -- Looks like a reference, but probably isn't: 'Actions A4' on line 3608 -- Looks like a reference, but probably isn't: 'Actions A5' on line 3634 ** Obsolete normative reference: RFC 2460 (ref. '5') (Obsoleted by RFC 8200) ** Obsolete normative reference: RFC 5226 (ref. '9') (Obsoleted by RFC 8126) -- Obsolete informational reference (is this intentional?): RFC 5996 (ref. '14') (Obsoleted by RFC 7296) Summary: 2 errors (**), 0 flaws (~~), 3 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group B. Fenner 3 Internet Draft AT&T Labs - Research 4 Intended Status: Internet Standard M. Handley 5 Expires: August 27, 2015 UCL 6 Obsoletes: 4601 H. Holbrook 7 Arastra 8 I. Kouvelas 9 R. Parekh 10 Cisco Systems, Inc. 11 Z. Zhang 12 Juniper Networks 13 L. Zheng 14 Huawei Technologies 15 February 23, 2015 17 Protocol Independent Multicast - Sparse Mode (PIM-SM): 18 Protocol Specification (Revised) 20 draft-ietf-pim-rfc4601bis-04 22 Status of This Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at http://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on August 27, 2015. 39 Abstract 41 This document specifies Protocol Independent Multicast - Sparse Mode 42 (PIM-SM). PIM-SM is a multicast routing protocol that can use the 43 underlying unicast routing information base or a separate multicast- 44 capable routing information base. It builds unidirectional shared 45 trees rooted at a Rendezvous Point (RP) per group, and optionally 46 creates shortest-path trees per source. 48 This document obsoletes RFC 4601 by replacing it, addresses the 49 errata filed against it, removes the optional (*,*,RP) and PIM 50 Multicast Border Router features that lack sufficient deployment 51 experience (see Appendix A) and moves the PIM specification to 52 Internet Standard. 54 Copyright Notice 56 Copyright (c) 2015 IETF Trust and the persons identified as the 57 document authors. All rights reserved. 59 This document is subject to BCP 78 and the IETF Trust's Legal 60 Provisions Relating to IETF Documents 61 (http://trustee.ietf.org/license-info) in effect on the date of 62 publication of this document. Please review these documents 63 carefully, as they describe your rights and restrictions with respect 64 to this document. Code Components extracted from this document must 65 include Simplified BSD License text as described in Section 4.e of 66 the Trust Legal Provisions and are provided without warranty as 67 described in the Simplified BSD License. 69 Table of Contents 71 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 6 72 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 73 2.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 6 74 2.2. Pseudocode Notation . . . . . . . . . . . . . . . . . . . 7 75 3. PIM-SM Protocol Overview . . . . . . . . . . . . . . . . . . . 8 76 3.1. Phase One: RP Tree . . . . . . . . . . . . . . . . . . . . 8 77 3.2. Phase Two: Register-Stop . . . . . . . . . . . . . . . . . 9 78 3.3. Phase Three: Shortest-Path Tree . . . . . . . . . . . . . 10 79 3.4. Source-Specific Joins . . . . . . . . . . . . . . . . . . 11 80 3.5. Source-Specific Prunes . . . . . . . . . . . . . . . . . . 11 81 3.6. Multi-Access Transit LANs . . . . . . . . . . . . . . . . 12 82 3.7. RP Discovery . . . . . . . . . . . . . . . . . . . . . . . 12 83 4. Protocol Specification . . . . . . . . . . . . . . . . . . . . 13 84 4.1. PIM Protocol State . . . . . . . . . . . . . . . . . . . . 14 85 4.1.1. General Purpose State . . . . . . . . . . . . . . . . 15 86 4.1.2. (*,G) State . . . . . . . . . . . . . . . . . . . . . 16 87 4.1.3. (S,G) State . . . . . . . . . . . . . . . . . . . . . 17 88 4.1.4. (S,G,rpt) State . . . . . . . . . . . . . . . . . . . 20 89 4.1.5. State Summarization Macros . . . . . . . . . . . . . . 21 90 4.2. Data Packet Forwarding Rules . . . . . . . . . . . . . . . 25 91 4.2.1. Last-Hop Switchover to the SPT . . . . . . . . . . . . 27 92 4.2.2. Setting and Clearing the (S,G) SPTbit . . . . . . . . 28 93 4.3. Designated Routers (DR) and Hello Messages . . . . . . . . 29 94 4.3.1. Sending Hello Messages . . . . . . . . . . . . . . . . 29 95 4.3.2. DR Election . . . . . . . . . . . . . . . . . . . . . 31 96 4.3.3. Reducing Prune Propagation Delay on LANs . . . . . . . 33 97 4.3.4. Maintaining Secondary Address Lists . . . . . . . . . 36 98 4.4. PIM Register Messages . . . . . . . . . . . . . . . . . . 37 99 4.4.1. Sending Register Messages from the DR . . . . . . . . 37 100 4.4.2. Receiving Register Messages at the RP . . . . . . . . 41 101 4.5. PIM Join/Prune Messages . . . . . . . . . . . . . . . . . 43 102 4.5.1. Receiving (*,G) Join/Prune Messages . . . . . . . . . 43 103 4.5.2. Receiving (S,G) Join/Prune Messages . . . . . . . . . 48 104 4.5.3. Receiving (S,G,rpt) Join/Prune Messages . . . . . . . 51 105 4.5.4. Sending (*,G) Join/Prune Messages . . . . . . . . . . 56 106 4.5.5. Sending (S,G) Join/Prune Messages . . . . . . . . . . 61 107 4.5.6. (S,G,rpt) Periodic Messages . . . . . . . . . . . . . 66 108 4.5.7. State Machine for (S,G,rpt) Triggered Messages . . . . 67 109 4.6. PIM Assert Messages . . . . . . . . . . . . . . . . . . . 71 110 4.6.1. (S,G) Assert Message State Machine . . . . . . . . . . 72 111 4.6.2. (*,G) Assert Message State Machine . . . . . . . . . . 79 112 4.6.3. Assert Metrics . . . . . . . . . . . . . . . . . . . . 85 113 4.6.4. AssertCancel Messages . . . . . . . . . . . . . . . . 87 114 4.6.5. Assert State Macros . . . . . . . . . . . . . . . . . 87 115 4.7. PIM Bootstrap and RP Discovery . . . . . . . . . . . . . . 91 116 4.7.1. Group-to-RP Mapping . . . . . . . . . . . . . . . . . 92 117 4.7.2. Hash Function . . . . . . . . . . . . . . . . . . . . 93 118 4.8. Source-Specific Multicast . . . . . . . . . . . . . . . . 94 119 4.8.1. Protocol Modifications for SSM Destination Addresses . 94 120 4.8.2. PIM-SSM-Only Routers . . . . . . . . . . . . . . . . . 95 121 4.9. PIM Packet Formats . . . . . . . . . . . . . . . . . . . . 96 122 4.9.1. Encoded Source and Group Address Formats . . . . . . . 98 123 4.9.2. Hello Message Format . . . . . . . . . . . . . . . . .101 124 4.9.3. Register Message Format . . . . . . . . . . . . . . .105 125 4.9.4. Register-Stop Message Format . . . . . . . . . . . . .108 126 4.9.5. Join/Prune Message Format . . . . . . . . . . . . . .108 127 4.9.5.1. Group Set Source List Rules . . . . . . . . . . .111 128 4.9.5.2. Group Set Fragmentation . . . . . . . . . . . . .114 129 4.9.6. Assert Message Format . . . . . . . . . . . . . . . .115 130 4.10. PIM Timers . . . . . . . . . . . . . . . . . . . . . . .116 131 4.11. Timer Values . . . . . . . . . . . . . . . . . . . . . .118 132 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . .123 133 5.1. PIM Address Family . . . . . . . . . . . . . . . . . . . .123 134 5.2. PIM Hello Options . . . . . . . . . . . . . . . . . . . .124 135 6. Security Considerations . . . . . . . . . . . . . . . . . . .124 136 6.1. Attacks Based on Forged Messages . . . . . . . . . . . . .124 137 6.1.1. Forged Link-Local Messages . . . . . . . . . . . . . .124 138 6.1.2. Forged Unicast Messages . . . . . . . . . . . . . . .125 139 6.2. Non-Cryptographic Authentication Mechanisms . . . . . . .125 140 6.3. Authentication Using IPsec . . . . . . . . . . . . . . . .126 141 6.3.1. Protecting Link-Local Multicast Messages . . . . . . .126 142 6.3.2. Protecting Unicast Messages . . . . . . . . . . . . .127 143 6.3.2.1. Register Messages . . . . . . . . . . . . . . . .127 144 6.3.2.2. Register-Stop Messages . . . . . . . . . . . . . .127 145 6.4. Denial-of-Service Attacks . . . . . . . . . . . . . . . .128 146 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . .128 147 8. Normative References . . . . . . . . . . . . . . . . . . . . .129 148 9. Informative References . . . . . . . . . . . . . . . . . . . .129 149 Appendix A. Functionality removed from RFC 4601 . . . . . . . . .131 150 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . .132 152 List of Figures 154 Figure 1. Per-(S,G) register state machine at a DR ................38 155 Figure 2. Downstream per-interface (*,G) state machine ............45 156 Figure 3. Downstream per-interface (S,G) state machine ............49 157 Figure 4. Downstream per-interface (S,G,rpt) state machine ........53 158 Figure 5. Upstream (*,G) state machine ............................58 159 Figure 6. Upstream (S,G) state machine ............................62 160 Figure 7. Upstream (S,G,rpt) state machine for triggered 161 messages ................................................67 162 Figure 8. Per-interface (S,G) Assert State machine ................72 163 Figure 9. Per-interface (*,G) Assert State machine ................80 165 1. Introduction 167 This document specifies a protocol for efficiently routing multicast 168 groups that may span wide-area (and inter-domain) internets. This 169 protocol is called Protocol Independent Multicast - Sparse Mode 170 (PIM-SM) because, although it may use the underlying unicast routing 171 to provide reverse-path information for multicast tree building, it 172 is not dependent on any particular unicast routing protocol. 174 PIM-SM version 2 was specified in RFC 4601 as a Proposed Standard. 175 This document is intended to address the reported errata and to 176 remove the optional (*,*,RP) feature that lacks sufficient deployment 177 experience, to advance PIM-SM to Draft Standard. 179 This document specifies the same protocol as RFC 4601 and 180 implementations per the specification in this document will be able 181 to interoperate successfully with implementations per RFC 4601. 183 2. Terminology 185 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 186 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 187 document are to be interpreted as described in RFC 2119 [1]. 189 2.1. Definitions 191 The following terms have special significance for PIM-SM: 193 Rendezvous Point (RP): 194 An RP is a router that has been configured to be used as the 195 root of the non-source-specific distribution tree for a 196 multicast group. Join messages from receivers for a group are 197 sent towards the RP, and data from senders is sent to the RP so 198 that receivers can discover who the senders are and start to 199 receive traffic destined for the group. 201 Designated Router (DR): 202 A shared-media LAN like Ethernet may have multiple PIM-SM 203 routers connected to it. A single one of these routers, the 204 DR, will act on behalf of directly connected hosts with respect 205 to the PIM-SM protocol. A single DR is elected per interface 206 (LAN or otherwise) using a simple election process. 208 MRIB Multicast Routing Information Base. This is the multicast 209 topology table, which is typically derived from the unicast 210 routing table, or routing protocols such as Multiprotocol BGP 211 (MBGP) that carry multicast-specific topology information. In 212 PIM-SM, the MRIB is used to decide where to send Join/Prune 213 messages. A secondary function of the MRIB is to provide 214 routing metrics for destination addresses; these metrics are 215 used when sending and processing Assert messages. 217 RPF Neighbor 218 RPF stands for "Reverse Path Forwarding". The RPF Neighbor of 219 a router with respect to an address is the neighbor that the 220 MRIB indicates should be used to forward packets to that 221 address. In the case of a PIM-SM multicast group, the RPF 222 neighbor is the router that a Join message for that group would 223 be directed to, in the absence of modifying Assert state. 225 TIB Tree Information Base. This is the collection of state at a 226 PIM router that has been created by receiving PIM Join/Prune 227 messages, PIM Assert messages, and Internet Group Management 228 Protocol (IGMP) or Multicast Listener Discovery (MLD) 229 information from local hosts. It essentially stores the state 230 of all multicast distribution trees at that router. 232 MFIB Multicast Forwarding Information Base. The TIB holds all the 233 state that is necessary to forward multicast packets at a 234 router. However, although this specification defines forwarding 235 in terms of the TIB, to actually forward packets using the TIB 236 is very inefficient. Instead, a real router implementation 237 will normally build an efficient MFIB from the TIB state to 238 perform forwarding. How this is done is implementation-specific 239 and is not discussed in this document. 241 Upstream 242 Towards the root of the tree. The root of the tree may be 243 either the source or the RP, depending on the context. 245 Downstream 246 Away from the root of the tree. 248 GenID Generation Identifier, used to detect reboots. 250 2.2. Pseudocode Notation 252 We use set notation in several places in this specification. 254 A (+) B is the union of two sets, A and B. 256 A (-) B is the elements of set A that are not in set B. 258 NULL is the empty set or list. 260 In addition, we use C-like syntax: 262 = denotes assignment of a variable. 264 == denotes a comparison for equality. 266 != denotes a comparison for inequality. 268 Braces { and } are used for grouping. 270 Unless otherwise noted, operations specified by statements having 271 multiple (+) and (-) operators should be evaluated from left to 272 right, i.e. A (+) B (-) C is the set resulting from union of sets A 273 and B minus elements in set C. 275 3. PIM-SM Protocol Overview 277 This section provides an overview of PIM-SM behavior. It is intended 278 as an introduction to how PIM-SM works, and it is NOT definitive. 279 For the definitive specification, see Section 4. 281 PIM relies on an underlying topology-gathering protocol to populate a 282 routing table with routes. This routing table is called the 283 Multicast Routing Information Base (MRIB). The routes in this table 284 may be taken directly from the unicast routing table, or they may be 285 different and provided by a separate routing protocol such as MBGP 286 [10]. Regardless of how it is created, the primary role of the MRIB 287 in the PIM protocol is to provide the next-hop router along a 288 multicast-capable path to each destination subnet. The MRIB is used 289 to determine the next-hop neighbor to which any PIM Join/Prune 290 message is sent. Data flows along the reverse path of the Join 291 messages. Thus, in contrast to the unicast RIB, which specifies the 292 next hop that a data packet would take to get to some subnet, the 293 MRIB gives reverse-path information and indicates the path that a 294 multicast data packet would take from its origin subnet to the router 295 that has the MRIB. 297 Like all multicast routing protocols that implement the service model 298 from RFC 1112 [3], PIM-SM must be able to route data packets from 299 sources to receivers without either the sources or receivers knowing 300 a priori of the existence of the others. This is essentially done in 301 three phases, although as senders and receivers may come and go at 302 any time, all three phases may occur simultaneously. 304 3.1. Phase One: RP Tree 306 In phase one, a multicast receiver expresses its interest in 307 receiving traffic destined for a multicast group. Typically, it does 308 this using IGMP [2] or MLD [4], but other mechanisms might also serve 309 this purpose. One of the receiver's local routers is elected as the 310 Designated Router (DR) for that subnet. On receiving the receiver's 311 expression of interest, the DR then sends a PIM Join message towards 312 the RP for that multicast group. This Join message is known as a 313 (*,G) Join because it joins group G for all sources to that group. 314 The (*,G) Join travels hop-by-hop towards the RP for the group, and 315 in each router it passes through, multicast tree state for group G is 316 instantiated. Eventually, the (*,G) Join either reaches the RP or 317 reaches a router that already has (*,G) Join state for that group. 318 When many receivers join the group, their Join messages converge on 319 the RP and form a distribution tree for group G that is rooted at the 320 RP. This is known as the RP Tree (RPT), and is also known as the 321 shared tree because it is shared by all sources sending to that 322 group. Join messages are resent periodically so long as the receiver 323 remains in the group. When all receivers on a leaf-network leave the 324 group, the DR will send a PIM (*,G) Prune message towards the RP for 325 that multicast group. However, if the Prune message is not sent for 326 any reason, the state will eventually time out. 328 A multicast data sender just starts sending data destined for a 329 multicast group. The sender's local router (DR) takes those data 330 packets, unicast-encapsulates them, and sends them directly to the 331 RP. The RP receives these encapsulated data packets, decapsulates 332 them, and forwards them onto the shared tree. The packets then 333 follow the (*,G) multicast tree state in the routers on the RP Tree, 334 being replicated wherever the RP Tree branches, and eventually 335 reaching all the receivers for that multicast group. The process of 336 encapsulating data packets to the RP is called registering, and the 337 encapsulation packets are known as PIM Register packets. 339 At the end of phase one, multicast traffic is flowing encapsulated to 340 the RP, and then natively over the RP tree to the multicast 341 receivers. 343 3.2. Phase Two: Register-Stop 345 Register-encapsulation of data packets is inefficient for two 346 reasons: 348 o Encapsulation and decapsulation may be relatively expensive 349 operations for a router to perform, depending on whether or not the 350 router has appropriate hardware for these tasks. 352 o Traveling all the way to the RP, and then back down the shared tree 353 may result in the packets traveling a relatively long distance to 354 reach receivers that are close to the sender. For some 355 applications, this increased latency or bandwidth consumption is 356 undesirable. 358 Although Register-encapsulation may continue indefinitely, for these 359 reasons, the RP will normally choose to switch to native forwarding. 360 To do this, when the RP receives a register-encapsulated data packet 361 from source S on group G, it will normally initiate an (S,G) source- 362 specific Join towards S. This Join message travels hop-by-hop 363 towards S, instantiating (S,G) multicast tree state in the routers 364 along the path. (S,G) multicast tree state is used only to forward 365 packets for group G if those packets come from source S. Eventually 366 the Join message reaches S's subnet or a router that already has 367 (S,G) multicast tree state, and then packets from S start to flow 368 following the (S,G) tree state towards the RP. These data packets 369 may also reach routers with (*,G) state along the path towards the 370 RP; if they do, they can shortcut onto the RP tree at this point. 372 While the RP is in the process of joining the source-specific tree 373 for S, the data packets will continue being encapsulated to the RP. 374 When packets from S also start to arrive natively at the RP, the RP 375 will be receiving two copies of each of these packets. At this 376 point, the RP starts to discard the encapsulated copy of these 377 packets, and it sends a Register-Stop message back to S's DR to 378 prevent the DR from unnecessarily encapsulating the packets. 380 At the end of phase 2, traffic will be flowing natively from S along 381 a source-specific tree to the RP, and from there along the shared 382 tree to the receivers. Where the two trees intersect, traffic may 383 transfer from the source-specific tree to the RP tree and thus avoid 384 taking a long detour via the RP. 386 Note that a sender may start sending before or after a receiver joins 387 the group, and thus phase two may happen before the shared tree to 388 the receiver is built. 390 3.3. Phase Three: Shortest-Path Tree 392 Although having the RP join back towards the source removes the 393 encapsulation overhead, it does not completely optimize the 394 forwarding paths. For many receivers, the route via the RP may 395 involve a significant detour when compared with the shortest path 396 from the source to the receiver. 398 To obtain lower latencies or more efficient bandwidth utilization, a 399 router on the receiver's LAN, typically the DR, may optionally 400 initiate a transfer from the shared tree to a source-specific 401 shortest-path tree (SPT). To do this, it issues an (S,G) Join 402 towards S. This instantiates state in the routers along the path to 403 S. Eventually, this join either reaches S's subnet or reaches a 404 router that already has (S,G) state. When this happens, data packets 405 from S start to flow following the (S,G) state until they reach the 406 receiver. 408 At this point, the receiver (or a router upstream of the receiver) 409 will be receiving two copies of the data: one from the SPT and one 410 from the RPT. When the first traffic starts to arrive from the SPT, 411 the DR or upstream router starts to drop the packets for G from S 412 that arrive via the RP tree. In addition, it sends an (S,G) Prune 413 message towards the RP. This is known as an (S,G,rpt) Prune. The 414 Prune message travels hop-by-hop, instantiating state along the path 415 towards the RP indicating that traffic from S for G should NOT be 416 forwarded in this direction. The prune is propagated until it reaches 417 the RP or a router that still needs the traffic from S for other 418 receivers. 420 By now, the receiver will be receiving traffic from S along the 421 shortest-path tree between the receiver and S. In addition, the RP 422 is receiving the traffic from S, but this traffic is no longer 423 reaching the receiver along the RP tree. As far as the receiver is 424 concerned, this is the final distribution tree. 426 3.4. Source-Specific Joins 428 IGMPv3 permits a receiver to join a group and specify that it only 429 wants to receive traffic for a group if that traffic comes from a 430 particular source. If a receiver does this, and no other receiver on 431 the LAN requires all the traffic for the group, then the DR may omit 432 performing a (*,G) join to set up the shared tree, and instead issue 433 a source-specific (S,G) join only. 435 The range of multicast addresses from 232.0.0.0 to 232.255.255.255 is 436 currently set aside for source-specific multicast in IPv4. For 437 groups in this range, receivers should only issue source-specific 438 IGMPv3 joins. If a PIM router receives a non-source-specific join for 439 a group in this range, it should ignore it, as described in Section 440 4.8. 442 3.5. Source-Specific Prunes 444 IGMPv3 also permits a receiver to join a group and to specify that it 445 only wants to receive traffic for a group if that traffic does not 446 come from a specific source or sources. In this case, the DR will 447 perform a (*,G) join as normal, but may combine this with an 448 (S,G,rpt) prune for each of the sources the receiver does not wish to 449 receive. 451 3.6. Multi-Access Transit LANs 453 The overview so far has concerned itself with point-to-point transit 454 links. However, using multi-access LANs such as Ethernet for transit 455 is not uncommon. This can cause complications for three reasons: 457 o Two or more routers on the LAN may issue (*,G) Joins to different 458 upstream routers on the LAN because they have inconsistent MRIB 459 entries regarding how to reach the RP. Both paths on the RP tree 460 will be set up, causing two copies of all the shared tree traffic 461 to appear on the LAN. 463 o Two or more routers on the LAN may issue (S,G) Joins to different 464 upstream routers on the LAN because they have inconsistent MRIB 465 entries regarding how to reach source S. Both paths on the source- 466 specific tree will be set up, causing two copies of all the traffic 467 from S to appear on the LAN. 469 o A router on the LAN may issue a (*,G) Join to one upstream router 470 on the LAN, and another router on the LAN may issue an (S,G) Join 471 to a different upstream router on the same LAN. Traffic from S may 472 reach the LAN over both the RPT and the SPT. If the receiver 473 behind the downstream (*,G) router doesn't issue an (S,G,rpt) 474 prune, then this condition would persist. 476 All of these problems are caused by there being more than one 477 upstream router with join state for the group or source-group pair. 478 PIM does not prevent such duplicate joins from occurring; instead, 479 when duplicate data packets appear on the LAN from different routers, 480 these routers notice this and then elect a single forwarder. This 481 election is performed using PIM Assert messages, which resolve the 482 problem in favor of the upstream router that has (S,G) state; or, if 483 neither or both router has (S,G) state, then the problem is resolved 484 in favor of the router with the best metric to the RP for RP trees, 485 or the best metric to the source for source-specific trees. 487 These Assert messages are also received by the downstream routers on 488 the LAN, and these cause subsequent Join messages to be sent to the 489 upstream router that won the Assert. 491 3.7. RP Discovery 493 PIM-SM routers need to know the address of the RP for each group for 494 which they have (*,G) state. This address is obtained automatically 495 (e.g., embedded-RP), through a bootstrap mechanism, or through static 496 configuration. 498 One dynamic way to do this is to use the Bootstrap Router (BSR) 499 mechanism [11]. One router in each PIM domain is elected the 500 Bootstrap Router through a simple election process. All the routers 501 in the domain that are configured to be candidates to be RPs 502 periodically unicast their candidacy to the BSR. From the 503 candidates, the BSR picks an RP-set, and periodically announces this 504 set in a Bootstrap message. Bootstrap messages are flooded hop-by-hop 505 throughout the domain until all routers in the domain know the RP- 506 Set. 508 To map a group to an RP, a router hashes the group address into the 509 RP-set using an order-preserving hash function (one that minimizes 510 changes if the RP-Set changes). The resulting RP is the one that it 511 uses as the RP for that group. 513 4. Protocol Specification 515 The specification of PIM-SM is broken into several parts: 517 o Section 4.1 details the protocol state stored. 519 o Section 4.2 specifies the data packet forwarding rules. 521 o Section 4.3 specifies Designated Router (DR) election and the rules 522 for sending and processing Hello messages. 524 o Section 4.4 specifies the PIM Register generation and processing 525 rules. 527 o Section 4.5 specifies the PIM Join/Prune generation and processing 528 rules. 530 o Section 4.6 specifies the PIM Assert generation and processing 531 rules. 533 o Section 4.7 specifies the RP discovery mechanisms. 535 o The subset of PIM required to support Source-Specific Multicast, 536 PIM-SSM, is described in Section 4.8. 538 o PIM packet formats are specified in Section 4.9. 540 o A summary of PIM-SM timers and their default values is given in 541 Section 4.10. 543 4.1. PIM Protocol State 545 This section specifies all the protocol state that a PIM 546 implementation should maintain in order to function correctly. We 547 term this state the Tree Information Base (TIB), as it holds the 548 state of all the multicast distribution trees at this router. In 549 this specification, we define PIM mechanisms in terms of the TIB. 550 However, only a very simple implementation would actually implement 551 packet forwarding operations in terms of this state. Most 552 implementations will use this state to build a multicast forwarding 553 table, which would then be updated when the relevant state in the TIB 554 changes. 556 Although we specify precisely the state to be kept, this does not 557 mean that an implementation of PIM-SM needs to hold the state in this 558 form. This is actually an abstract state definition, which is needed 559 in order to specify the router's behavior. A PIM-SM implementation 560 is free to hold whatever internal state it requires and will still be 561 conformant with this specification so long as it results in the same 562 externally visible protocol behavior as an abstract router that holds 563 the following state. 565 We divide TIB state into three sections: 567 (*,G) state 568 State that maintains the RP tree for G. 570 (S,G) state 571 State that maintains a source-specific tree for source S and 572 group G. 574 (S,G,rpt) state 575 State that maintains source-specific information about source S 576 on the RP tree for G. For example, if a source is being 577 received on the source-specific tree, it will normally have been 578 pruned off the RP tree. This prune state is (S,G,rpt) state. 580 The state that should be kept is described below. Of course, 581 implementations will only maintain state when it is relevant to 582 forwarding operations; for example, the "NoInfo" state might be 583 assumed from the lack of other state information rather than being 584 held explicitly. 586 4.1.1. General Purpose State 588 A router holds the following non-group-specific state: 590 For each interface: 592 o Effective Override Interval 594 o Effective Propagation Delay 596 o Suppression state: One of {"Enable", "Disable"} 598 Neighbor State: 600 For each neighbor: 602 o Information from neighbor's Hello 604 o Neighbor's GenID. 606 o Neighbor Liveness Timer (NLT) 608 Designated Router (DR) State: 610 o Designated Router's IP Address 612 o DR's DR Priority 614 The Effective Override Interval, the Effective Propagation Delay and 615 the Interface suppression state are described in Section 4.3.3. 616 Designated Router state is described in Section 4.3. 618 4.1.2. (*,G) State 620 For every group G, a router keeps the following state: 622 (*,G) state: 623 For each interface: 625 Local Membership: 626 State: One of {"NoInfo", "Include"} 628 PIM (*,G) Join/Prune State: 630 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 631 Pending" (PP)} 633 o Prune-Pending Timer (PPT) 635 o Join/Prune Expiry Timer (ET) 637 (*,G) Assert Winner State 639 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 640 "I won Assert" (W)} 642 o Assert Timer (AT) 644 o Assert winner's IP Address (AssertWinner) 646 o Assert winner's Assert Metric (AssertWinnerMetric) 648 Not interface specific: 650 Upstream (*,G) Join/Prune State: 652 o State: One of {"NotJoined(*,G)", "Joined(*,G)"} 654 o Upstream Join/Prune Timer (JT) 656 o Last RP Used 658 o Last RPF Neighbor towards RP that was used 660 Local membership is the result of the local membership mechanism 661 (such as IGMP or MLD) running on that interface. It need not be kept 662 if this router is not the DR on that interface unless this router won 663 a (*,G) assert on this interface for this group, although 664 implementations may optionally keep this state in case they become 665 the DR or assert winner. It is RECOMMENDED to store this information 666 if possible, as it reduces latency converging to stable operating 667 conditions after a failure causing a change of DR. This information 668 is used by the pim_include(*,G) macro described in Section 4.1.5. 670 PIM (*,G) Join/Prune state is the result of receiving PIM (*,G) 671 Join/Prune messages on this interface and is specified in Section 672 4.5.1. The state is used by the macros that calculate the outgoing 673 interface list in Section 4.1.5, and in the JoinDesired(*,G) macro 674 (defined in Section 4.5.4) that is used in deciding whether a 675 Join(*,G) should be sent upstream. 677 (*,G) Assert Winner state is the result of sending or receiving (*,G) 678 Assert messages on this interface. It is specified in Section 4.6.2. 680 The upstream (*,G) Join/Prune State reflects the state of the 681 upstream (*,G) state machine described in Section 4.5.4. 683 The upstream (*,G) Join/Prune Timer is used to send out periodic 684 Join(*,G) messages, and to override Prune(*,G) messages from peers on 685 an upstream LAN interface. 687 The last RP used must be stored because if the RP-Set changes 688 (Section 4.7), then state must be torn down and rebuilt for groups 689 whose RP changes. 691 The last RPF neighbor towards the RP is stored because if the MRIB 692 changes, then the RPF neighbor towards the RP may change. If it does 693 so, then we need to trigger a new Join(*,G) to the new upstream 694 neighbor and a Prune(*,G) to the old upstream neighbor. Similarly, 695 if a router detects through a changed GenID in a Hello message that 696 the upstream neighbor towards the RP has rebooted, then it SHOULD re- 697 instantiate state by sending a Join(*,G). These mechanisms are 698 specified in Section 4.5.4. 700 4.1.3. (S,G) State 702 For every source/group pair (S,G), a router keeps the following 703 state: 705 (S,G) state: 707 For each interface: 709 Local Membership: 710 State: One of {"NoInfo", "Include"} 712 PIM (S,G) Join/Prune State: 714 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 715 Pending" (PP)} 717 o Prune-Pending Timer (PPT) 719 o Join/Prune Expiry Timer (ET) 721 (S,G) Assert Winner State 723 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 724 "I won Assert" (W)} 726 o Assert Timer (AT) 728 o Assert winner's IP Address (AssertWinner) 730 o Assert winner's Assert Metric (AssertWinnerMetric) 732 Not interface specific: 734 Upstream (S,G) Join/Prune State: 736 o State: One of {"NotJoined(S,G)", "Joined(S,G)"} 738 o Upstream (S,G) Join/Prune Timer (JT) 740 o Last RPF Neighbor towards S that was used 742 o SPTbit (indicates (S,G) state is active) 744 o (S,G) Keepalive Timer (KAT) 746 Additional (S,G) state at the DR: 748 o Register state: One of {"Join" (J), "Prune" (P), 749 "Join-Pending" (JP), "NoInfo" (NI)} 751 o Register-Stop timer 753 Local membership is the result of the local source-specific 754 membership mechanism (such as IGMP version 3) running on that 755 interface and specifying that this particular source should be 756 included. As stored here, this state is the resulting state after 757 any IGMPv3 inconsistencies have been resolved. It need not be kept 758 if this router is not the DR on that interface unless this router won 759 an (S,G) assert on this interface for this group. However, it is 760 RECOMMENDED to store this information if possible, as it reduces 761 latency converging to stable operating conditions after a failure 762 causing a change of DR. This information is used by the 763 pim_include(S,G) macro described in Section 4.1.5. 765 PIM (S,G) Join/Prune state is the result of receiving PIM (S,G) 766 Join/Prune messages on this interface and is specified in Section 767 4.5.2. The state is used by the macros that calculate the outgoing 768 interface list in Section 4.1.5, and in the JoinDesired(S,G) macro 769 (defined in Section 4.5.5) that is used in deciding whether a 770 Join(S,G) should be sent upstream. 772 (S,G) Assert Winner state is the result of sending or receiving (S,G) 773 Assert messages on this interface. It is specified in Section 4.6.1. 775 The upstream (S,G) Join/Prune State reflects the state of the 776 upstream (S,G) state machine described in Section 4.5.5. 778 The upstream (S,G) Join/Prune Timer is used to send out periodic 779 Join(S,G) messages, and to override Prune(S,G) messages from peers on 780 an upstream LAN interface. 782 The last RPF neighbor towards S is stored because if the MRIB 783 changes, then the RPF neighbor towards S may change. If it does so, 784 then we need to trigger a new Join(S,G) to the new upstream neighbor 785 and a Prune(S,G) to the old upstream neighbor. Similarly, if the 786 router detects through a changed GenID in a Hello message that the 787 upstream neighbor towards S has rebooted, then it SHOULD re- 788 instantiate state by sending a Join(S,G). These mechanisms are 789 specified in Section 4.5.5. 791 The SPTbit is used to indicate whether forwarding is taking place on 792 the (S,G) Shortest Path Tree (SPT) or on the (*,G) tree. A router 793 can have (S,G) state and still be forwarding on (*,G) state during 794 the interval when the source-specific tree is being constructed. 795 When SPTbit is FALSE, only (*,G) forwarding state is used to forward 796 packets from S to G. When SPTbit is TRUE, both (*,G) and (S,G) 797 forwarding state are used. 799 The (S,G) Keepalive Timer is updated by data being forwarded using 800 this (S,G) forwarding state. It is used to keep (S,G) state alive in 801 the absence of explicit (S,G) Joins. Amongst other things, this is 802 necessary for the so-called "turnaround rules" -- when the RP uses 803 (S,G) joins to stop encapsulation, and then (S,G) prunes to prevent 804 traffic from unnecessarily reaching the RP. 806 On a DR, the (S,G) Register State is used to keep track of whether to 807 encapsulate data to the RP on the Register Tunnel; the (S,G) 808 Register-Stop timer tracks how long before encapsulation begins again 809 for a given (S,G). 811 4.1.4. (S,G,rpt) State 813 For every source/group pair (S,G) for which a router also has (*,G) 814 state, it also keeps the following state: 816 (S,G,rpt) state: 818 For each interface: 820 Local Membership: 821 State: One of {"NoInfo", "Exclude"} 823 PIM (S,G,rpt) Join/Prune State: 825 o State: One of {"NoInfo", "Pruned", "Prune- 826 Pending"} 828 o Prune-Pending Timer (PPT) 830 o Join/Prune Expiry Timer (ET) 832 Not interface specific: 834 Upstream (S,G,rpt) Join/Prune State: 836 o State: One of {"RPTNotJoined(G)", 837 "NotPruned(S,G,rpt)", "Pruned(S,G,rpt)"} 839 o Override Timer (OT) 841 Local membership is the result of the local source-specific 842 membership mechanism (such as IGMPv3) running on that interface and 843 specifying that although there is (*,G) Include state, this 844 particular source should be excluded. As stored here, this state is 845 the resulting state after any IGMPv3 inconsistencies between LAN 846 members have been resolved. It need not be kept if this router is 847 not the DR on that interface unless this router won a (*,G) assert on 848 this interface for this group. However, we RECOMMEND storing this 849 information if possible, as it reduces latency converging to stable 850 operating conditions after a failure causing a change of DR. This 851 information is used by the pim_exclude(S,G) macro described in 852 Section 4.1.5. 854 PIM (S,G,rpt) Join/Prune state is the result of receiving PIM 855 (S,G,rpt) Join/Prune messages on this interface and is specified in 856 Section 4.5.3. The state is used by the macros that calculate the 857 outgoing interface list in Section 4.1.5, and in the rules for adding 858 Prune(S,G,rpt) messages to Join(*,G) messages specified in Section 859 4.5.6. 861 The upstream (S,G,rpt) Join/Prune state is used along with the 862 Override Timer to send the correct override messages in response to 863 Join/Prune messages sent by upstream peers on a LAN. This state and 864 behavior are specified in Section 4.5.7. 866 4.1.5. State Summarization Macros 868 Using this state, we define the following "macro" definitions, which 869 we will use in the descriptions of the state machines and pseudocode 870 in the following sections. 872 The most important macros are those that define the outgoing 873 interface list (or "olist") for the relevant state. An olist can be 874 "immediate" if it is built directly from the state of the relevant 875 type. For example, the immediate_olist(S,G) is the olist that would 876 be built if the router only had (S,G) state and no (*,G) or (S,G,rpt) 877 state. In contrast, the "inherited" olist inherits state from other 878 types. For example, the inherited_olist(S,G) is the olist that is 879 relevant for forwarding a packet from S to G using both source- 880 specific and group-specific state. 882 There is no immediate_olist(S,G,rpt) as (S,G,rpt) state is negative 883 state; it removes interfaces in the (*,G) olist from the olist that 884 is actually used to forward traffic. The inherited_olist(S,G,rpt) is 885 therefore the olist that would be used for a packet from S to G 886 forwarding on the RP tree. It is a strict subset of 887 immediate_olist(*,G). 889 Generally speaking, the inherited olists are used for forwarding, and 890 the immediate_olists are used to make decisions about state 891 maintenance. 893 immediate_olist(*,G) = 894 joins(*,G) (+) pim_include(*,G) (-) lost_assert(*,G) 896 immediate_olist(S,G) = 897 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) 899 inherited_olist(S,G,rpt) = 900 ( joins(*,G) (-) prunes(S,G,rpt) ) 901 (+) ( pim_include(*,G) (-) pim_exclude(S,G)) 902 (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) ) 904 inherited_olist(S,G) = 905 inherited_olist(S,G,rpt) (+) 906 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) 908 The macros pim_include(*,G) and pim_include(S,G) indicate the 909 interfaces to which traffic might be forwarded because of hosts that 910 are local members on that interface. Note that normally only the DR 911 cares about local membership, but when an assert happens, the assert 912 winner takes over responsibility for forwarding traffic to local 913 members that have requested traffic on a group or source/group pair. 915 pim_include(*,G) = 916 { all interfaces I such that: 917 ( ( I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) 918 OR AssertWinner(*,G,I) == me ) 919 AND local_receiver_include(*,G,I) } 921 pim_include(S,G) = 922 { all interfaces I such that: 923 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) 924 OR AssertWinner(S,G,I) == me ) 925 AND local_receiver_include(S,G,I) } 927 pim_exclude(S,G) = 928 { all interfaces I such that: 929 ( (I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) 930 OR AssertWinner(*,G,I) == me ) 931 AND local_receiver_exclude(S,G,I) } 933 The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD 934 module or other local membership mechanism has determined that local 935 members on interface I desire to receive traffic sent specifically by 936 S to G. "local_receiver_include(*,G,I)" is true if the IGMP/MLD 937 module or other local membership mechanism has determined that local 938 members on interface I desire to receive all traffic sent to G 939 (possibly excluding traffic from a specific set of sources). 940 "local_receiver_exclude(S,G,I) is true if 941 "local_receiver_include(*,G,I)" is true but none of the local members 942 desire to receive traffic from S. 944 The set "joins(*,G)" is the set of all interfaces on which the router 945 has received (*,G) Joins: 947 joins(*,G) = 948 { all interfaces I such that 949 DownstreamJPState(*,G,I) is either Join or Prune-Pending } 951 DownstreamJPState(*,G,I) is the state of the finite state machine in 952 Section 4.5.1. 954 The set "joins(S,G)" is the set of all interfaces on which the router 955 has received (S,G) Joins: 957 joins(S,G) = 958 { all interfaces I such that 959 DownstreamJPState(S,G,I) is either Join or Prune-Pending } 961 DownstreamJPState(S,G,I) is the state of the finite state machine in 962 Section 4.5.2. 964 The set "prunes(S,G,rpt)" is the set of all interfaces on which the 965 router has received (*,G) joins and (S,G,rpt) prunes. 967 prunes(S,G,rpt) = 968 { all interfaces I such that 969 DownstreamJPState(S,G,rpt,I) is Prune or PruneTmp } 971 DownstreamJPState(S,G,rpt,I) is the state of the finite state machine 972 in Section 4.5.3. 974 The set "lost_assert(*,G)" is the set of all interfaces on which the 975 router has received (*,G) joins but has lost a (*,G) assert. The 976 macro lost_assert(*,G,I) is defined in Section 4.6.5. 978 lost_assert(*,G) = 979 { all interfaces I such that 980 lost_assert(*,G,I) == TRUE } 982 The set "lost_assert(S,G,rpt)" is the set of all interfaces on which 983 the router has received (*,G) joins but has lost an (S,G) assert. 984 The macro lost_assert(S,G,rpt,I) is defined in Section 4.6.5. 986 lost_assert(S,G,rpt) = 987 { all interfaces I such that 988 lost_assert(S,G,rpt,I) == TRUE } 990 The set "lost_assert(S,G)" is the set of all interfaces on which the 991 router has received (S,G) joins but has lost an (S,G) assert. The 992 macro lost_assert(S,G,I) is defined in Section 4.6.5. 994 lost_assert(S,G) = 995 { all interfaces I such that 996 lost_assert(S,G,I) == TRUE } 998 The following pseudocode macro definitions are also used in many 999 places in the specification. Basically, RPF' is the RPF neighbor 1000 towards an RP or source unless a PIM-Assert has overridden the normal 1001 choice of neighbor. 1003 neighbor RPF'(*,G) { 1004 if ( I_Am_Assert_Loser(*, G, RPF_interface(RP(G))) ) { 1005 return AssertWinner(*, G, RPF_interface(RP(G)) ) 1006 } else { 1007 return NBR( RPF_interface(RP(G)), MRIB.next_hop( RP(G) ) ) 1008 } 1009 } 1011 neighbor RPF'(S,G,rpt) { 1012 if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) { 1013 return AssertWinner(S, G, RPF_interface(RP(G)) ) 1014 } else { 1015 return RPF'(*,G) 1016 } 1017 } 1019 neighbor RPF'(S,G) { 1020 if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) { 1021 return AssertWinner(S, G, RPF_interface(S) ) 1022 } else { 1023 return NBR( RPF_interface(S), MRIB.next_hop( S ) ) 1024 } 1025 } 1027 RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data packets 1028 should be coming and to which joins should be sent on the RP tree and 1029 SPT, respectively. 1031 RPF'(S,G,rpt) is basically RPF'(*,G) modified by the result of an 1032 Assert(S,G) on RPF_interface(RP(G)). In such a case, packets from S 1033 will be originating from a different router than RPF'(*,G). If we 1034 only have active (*,G) Join state, we need to accept packets from 1035 RPF'(S,G,rpt) and add a Prune(S,G,rpt) to the periodic Join(*,G) 1036 messages that we send to RPF'(*,G) (see Section 4.5.6). 1038 The function MRIB.next_hop( S ) returns an address of the next-hop 1039 PIM neighbor toward the host S, as indicated by the current MRIB. If 1040 S is directly adjacent, then MRIB.next_hop( S ) returns NULL. At the 1041 RP for G, MRIB.next_hop( RP(G)) returns NULL. 1043 The function NBR( I, A ) uses information gathered through PIM Hello 1044 messages to map the IP address A of a directly connected PIM neighbor 1045 router on interface I to the primary IP address of the same router 1046 (Section 4.3.4). The primary IP address of a neighbor is the address 1047 that it uses as the source of its PIM Hello messages. Note that a 1048 neighbor's IP address may be non-unique within the PIM neighbor 1049 database due to scope issues. The address must, however, be unique 1050 amongst the addresses of all the PIM neighbors on a specific 1051 interface. 1053 I_Am_Assert_Loser(S, G, I) is true if the Assert state machine (in 1054 Section 4.6.1) for (S,G) on Interface I is in "I am Assert Loser" 1055 state. 1057 I_Am_Assert_Loser(*, G, I) is true if the Assert state machine (in 1058 Section 4.6.2) for (*,G) on Interface I is in "I am Assert Loser" 1059 state. 1061 4.2. Data Packet Forwarding Rules 1063 The PIM-SM packet forwarding rules are defined below in pseudocode. 1065 iif is the incoming interface of the packet. 1066 S is the source address of the packet. 1067 G is the destination address of the packet (group address). 1068 RP is the address of the Rendezvous Point for this group. 1069 RPF_interface(S) is the interface the MRIB indicates would be used 1070 to route packets to S. 1071 RPF_interface(RP) is the interface the MRIB indicates would be 1072 used to route packets to the RP, except at the RP when it is the 1073 decapsulation interface (the "virtual" interface on which register 1074 packets are received). 1076 First, we restart (or start) the Keepalive Timer if the source is on 1077 a directly connected subnet. 1079 Second, we check to see if the SPTbit should be set because we've now 1080 switched from the RP tree to the SPT. 1082 Next, we check to see whether the packet should be accepted based on 1083 TIB state and the interface that the packet arrived on. 1085 If the packet should be forwarded using (S,G) state, we then build an 1086 outgoing interface list for the packet. If this list is not empty, 1087 then we restart the (S,G) state Keepalive Timer. 1089 If the packet should be forwarded using (*,G) state, then we just 1090 build an outgoing interface list for the packet. We also check if we 1091 should initiate a switch to start receiving this source on a shortest 1092 path tree. 1094 Finally we remove the incoming interface from the outgoing interface 1095 list we've created, and if the resulting outgoing interface list is 1096 not empty, we forward the packet out of those interfaces. 1098 On receipt of data from S to G on interface iif: 1099 if( DirectlyConnected(S) == TRUE AND iif == RPF_interface(S) ) { 1100 set KeepaliveTimer(S,G) to Keepalive_Period 1101 # Note: a register state transition or UpstreamJPState(S,G) 1102 # transition may happen as a result of restarting 1103 # KeepaliveTimer, and must be dealt with here. 1104 } 1106 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined AND 1107 inherited_olist(S,G) != NULL ) { 1108 set KeepaliveTimer(S,G) to Keepalive_Period 1109 } 1111 Update_SPTbit(S,G,iif) 1112 oiflist = NULL 1114 if( iif == RPF_interface(S) AND SPTbit(S,G) == TRUE ) { 1115 oiflist = inherited_olist(S,G) 1116 } else if( iif == RPF_interface(RP(G)) AND SPTbit(S,G) == FALSE ) { 1117 oiflist = inherited_olist(S,G,rpt) 1118 CheckSwitchToSpt(S,G) 1119 } else { 1120 # Note: RPF check failed 1121 # A transition in an Assert FSM may cause an Assert(S,G) 1122 # or Assert(*,G) message to be sent out interface iif. 1123 # See section 4.6 for details. 1124 if ( SPTbit(S,G) == TRUE AND iif is in inherited_olist(S,G) ) { 1125 send Assert(S,G) on iif 1126 } else if ( SPTbit(S,G) == FALSE AND 1127 iif is in inherited_olist(S,G,rpt) ) { 1128 send Assert(*,G) on iif 1129 } 1130 } 1132 oiflist = oiflist (-) iif 1133 forward packet on all interfaces in oiflist 1135 This pseudocode employs several "macro" definitions: 1137 DirectlyConnected(S) is TRUE if the source S is on any subnet that is 1138 directly connected to this router (or for packets originating on this 1139 router). 1141 inherited_olist(S,G) and inherited_olist(S,G,rpt) are defined in 1142 Section 4.1. 1144 Basically, inherited_olist(S,G) is the outgoing interface list for 1145 packets forwarded on (S,G) state, taking into account (*,G) state, 1146 asserts, etc. 1148 inherited_olist(S,G,rpt) is the outgoing interface list for packets 1149 forwarded on (*,G) state, taking into account (S,G,rpt) prune state, 1150 asserts, etc. 1152 Update_SPTbit(S,G,iif) is defined in Section 4.2.2. 1154 CheckSwitchToSpt(S,G) is defined in Section 4.2.1. 1156 UpstreamJPState(S,G) is the state of the finite state machine in 1157 Section 4.5.5. 1159 Keepalive_Period is defined in Section 4.10. 1161 Data-triggered PIM-Assert messages sent from the above forwarding 1162 code SHOULD be rate-limited in an implementation-dependent manner. 1164 4.2.1. Last-Hop Switchover to the SPT 1166 In Sparse-Mode PIM, last-hop routers join the shared tree towards the 1167 RP. Once traffic from sources to joined groups arrives at a last-hop 1168 router, it has the option of switching to receive the traffic on a 1169 shortest path tree (SPT). 1171 The decision for a router to switch to the SPT is controlled as 1172 follows: 1174 void 1175 CheckSwitchToSpt(S,G) { 1176 if ( ( pim_include(*,G) (-) pim_exclude(S,G) 1177 (+) pim_include(S,G) != NULL ) 1178 AND SwitchToSptDesired(S,G) ) { 1179 # Note: Restarting the KAT will result in the SPT switch 1180 set KeepaliveTimer(S,G) to Keepalive_Period 1181 } 1182 } 1184 SwitchToSptDesired(S,G) is a policy function that is implementation 1185 defined. An "infinite threshold" policy can be implemented by making 1186 SwitchToSptDesired(S,G) return false all the time. A "switch on 1187 first packet" policy can be implemented by making 1188 SwitchToSptDesired(S,G) return true once a single packet has been 1189 received for the source and group. 1191 4.2.2. Setting and Clearing the (S,G) SPTbit 1193 The (S,G) SPTbit is used to distinguish whether to forward on (*,G) 1194 or on (S,G) state. When switching from the RP tree to the source 1195 tree, there is a transition period when data is arriving due to 1196 upstream (*,G) state while upstream (S,G) state is being established, 1197 during which time a router should continue to forward only on (*,G) 1198 state. This prevents temporary black-holes that would be caused by 1199 sending a Prune(S,G,rpt) before the upstream (S,G) state has finished 1200 being established. 1202 Thus, when a packet arrives, the (S,G) SPTbit is updated as follows: 1204 void 1205 Update_SPTbit(S,G,iif) { 1206 if ( iif == RPF_interface(S) 1207 AND JoinDesired(S,G) == TRUE 1208 AND ( DirectlyConnected(S) == TRUE 1209 OR RPF_interface(S) != RPF_interface(RP(G)) 1210 OR inherited_olist(S,G,rpt) == NULL 1211 OR ( ( RPF'(S,G) == RPF'(*,G) ) AND 1212 ( RPF'(S,G) != NULL ) ) 1213 OR ( I_Am_Assert_Loser(S,G,iif) ) ) ) { 1214 Set SPTbit(S,G) to TRUE 1215 } 1216 } 1218 Additionally, a router can set SPTbit(S,G) to TRUE in other cases, 1219 such as when it receives an Assert(S,G) on RPF_interface(S) (see 1220 Section 4.6.1). 1222 JoinDesired(S,G) is defined in Section 4.5.5 and indicates whether we 1223 have the appropriate (S,G) Join state to wish to send a Join(S,G) 1224 upstream. 1226 Basically, Update_SPTbit(S,G,iif) will set the SPTbit if we have the 1227 appropriate (S,G) join state, and if the packet arrived on the 1228 correct upstream interface for S, and if one or more of the following 1229 conditions applies: 1231 1. The source is directly connected, in which case the switch to the 1232 SPT is a no-op. 1234 2. The RPF interface to S is different from the RPF interface to the 1235 RP. The packet arrived on RPF_interface(S), and so the SPT must 1236 have been completed. 1238 3. No One wants the packet on the RP tree. 1240 4. RPF'(S,G) == RPF'(*,G). In this case, the router will never be 1241 able to tell if the SPT has been completed, so it should just 1242 switch immediately. RPF'(S,G) != NULL check ensures that SPTbit 1243 is set only if RPF neighbor towards S is valid. 1245 In the case where the RPF interface is the same for the RP and for S, 1246 but RPF'(S,G) and RPF'(*,G) differ, we wait for an Assert(S,G), which 1247 indicates that the upstream router with (S,G) state believes the SPT 1248 has been completed. However, item (3) above is needed because there 1249 may not be any (*,G) state to trigger an Assert(S,G) to happen. 1251 The SPTbit is cleared in the (S,G) upstream state machine (see 1252 Section 4.5.5) when JoinDesired(S,G) becomes FALSE. 1254 4.3. Designated Routers (DR) and Hello Messages 1256 A shared-media LAN like Ethernet may have multiple PIM-SM routers 1257 connected to it. A single one of these routers, the DR, will act on 1258 behalf of directly connected hosts with respect to the PIM-SM 1259 protocol. Because the distinction between LANs and point-to-point 1260 interfaces can sometimes be blurred, and because routers may also 1261 have multicast host functionality, the PIM-SM specification makes no 1262 distinction between the two. Thus, DR election will happen on all 1263 interfaces, LAN or otherwise. 1265 DR election is performed using Hello messages. Hello messages are 1266 also the way that option negotiation takes place in PIM, so that 1267 additional functionality can be enabled, or parameters tuned. 1269 4.3.1. Sending Hello Messages 1271 PIM Hello messages are sent periodically on each PIM-enabled 1272 interface. They allow a router to learn about the neighboring PIM 1273 routers on each interface. Hello messages are also the mechanism 1274 used to elect a Designated Router (DR), and to negotiate additional 1275 capabilities. A router must record the Hello information received 1276 from each PIM neighbor. 1278 Hello messages MUST be sent on all active interfaces, including 1279 physical point-to-point links, and are multicast to the 'ALL-PIM- 1280 ROUTERS' group address ('224.0.0.13' for IPv4 and 'ff02::d' for 1281 IPv6). 1283 We note that some implementations do not send Hello messages on 1284 point-to-point interfaces. This is non-compliant behavior. A 1285 compliant PIM router MUST send Hello messages, even on point-to-point 1286 interfaces. 1288 A per-interface Hello Timer (HT(I)) is used to trigger sending Hello 1289 messages on each active interface. When PIM is enabled on an 1290 interface or a router first starts, the Hello Timer of that interface 1291 is set to a random value between 0 and Triggered_Hello_Delay. This 1292 prevents synchronization of Hello messages if multiple routers are 1293 powered on simultaneously. After the initial randomized interval, 1294 Hello messages MUST be sent every Hello_Period seconds. The Hello 1295 Timer SHOULD NOT be reset except when it expires. 1297 Note that neighbors will not accept Join/Prune or Assert messages 1298 from a router unless they have first heard a Hello message from that 1299 router. Thus, if a router needs to send a Join/Prune or Assert 1300 message on an interface on which it has not yet sent a Hello message 1301 with the currently configured IP address, then it MUST immediately 1302 send the relevant Hello message without waiting for the Hello Timer 1303 to expire, followed by the Join/Prune or Assert message. 1305 The DR_Priority Option allows a network administrator to give 1306 preference to a particular router in the DR election process by 1307 giving it a numerically larger DR Priority. The DR_Priority Option 1308 SHOULD be included in every Hello message, even if no DR Priority is 1309 explicitly configured on that interface. This is necessary because 1310 priority-based DR election is only enabled when all neighbors on an 1311 interface advertise that they are capable of using the DR_Priority 1312 Option. The default priority is 1. 1314 The Generation_Identifier (GenID) Option SHOULD be included in all 1315 Hello messages. The GenID option contains a randomly generated 1316 32-bit value that is regenerated each time PIM forwarding is started 1317 or restarted on the interface, including when the router itself 1318 restarts. When a Hello message with a new GenID is received from a 1319 neighbor, any old Hello information about that neighbor SHOULD be 1320 discarded and superseded by the information from the new Hello 1321 message. This may cause a new DR to be chosen on that interface. 1323 The LAN Prune Delay Option SHOULD be included in all Hello messages 1324 sent on multi-access LANs. This option advertises a router's 1325 capability to use values other than the defaults for the 1326 Propagation_Delay and Override_Interval, which affect the setting of 1327 the Prune-Pending, Upstream Join, and Override Timers (defined in 1328 Section 4.10). 1330 The Address List Option advertises all the secondary addresses 1331 associated with the source interface of the router originating the 1332 message. The option MUST be included in all Hello messages if there 1333 are secondary addresses associated with the source interface and MAY 1334 be omitted if no secondary addresses exist. 1336 To allow new or rebooting routers to learn of PIM neighbors quickly, 1337 when a Hello message is received from a new neighbor, or a Hello 1338 message with a new GenID is received from an existing neighbor, a new 1339 Hello message SHOULD be sent on this interface after a randomized 1340 delay between 0 and Triggered_Hello_Delay. This triggered message 1341 need not change the timing of the scheduled periodic message. If a 1342 router needs to send a Join/Prune to the new neighbor or send an 1343 Assert message in response to an Assert message from the new neighbor 1344 before this randomized delay has expired, then it MUST immediately 1345 send the relevant Hello message without waiting for the Hello Timer 1346 to expire, followed by the Join/Prune or Assert message. If it does 1347 not do this, then the new neighbor will discard the Join/Prune or 1348 Assert message. 1350 Before an interface goes down or changes primary IP address, a Hello 1351 message with a zero HoldTime SHOULD be sent immediately (with the old 1352 IP address if the IP address changed). This will cause PIM neighbors 1353 to remove this neighbor (or its old IP address) immediately. After 1354 an interface has changed its IP address, it MUST send a Hello message 1355 with its new IP address. If an interface changes one of its 1356 secondary IP addresses, a Hello message with an updated Address_List 1357 option and a non-zero HoldTime SHOULD be sent immediately. This will 1358 cause PIM neighbors to update this neighbor's list of secondary 1359 addresses immediately. 1361 4.3.2. DR Election 1363 When a PIM Hello message is received on interface I, the following 1364 information about the sending neighbor is recorded: 1366 neighbor.interface 1367 The interface on which the Hello message arrived. 1369 neighbor.primary_ip_address 1370 The IP address that the PIM neighbor used as the source 1371 address of the Hello message. 1373 neighbor.genid 1374 The Generation ID of the PIM neighbor. 1376 neighbor.dr_priority 1377 The DR Priority field of the PIM neighbor, if it is present in 1378 the Hello message. 1380 neighbor.dr_priority_present 1381 A flag indicating if the DR Priority field was present in the 1382 Hello message. 1384 neighbor.timeout 1385 A timer value to time out the neighbor state when it becomes 1386 stale, also known as the Neighbor Liveness Timer. 1388 The Neighbor Liveness Timer (NLT(N,I)) is reset to 1389 Hello_Holdtime (from the Hello Holdtime option) whenever a 1390 Hello message is received containing a Holdtime option, or to 1391 Default_Hello_Holdtime if the Hello message does not contain 1392 the Holdtime option. 1394 Neighbor state is deleted when the neighbor timeout expires. 1396 The function for computing the DR on interface I is: 1398 host 1399 DR(I) { 1400 dr = me 1401 for each neighbor on interface I { 1402 if ( dr_is_better( neighbor, dr, I ) == TRUE ) { 1403 dr = neighbor 1404 } 1405 } 1406 return dr 1407 } 1409 The function used for comparing DR "metrics" on interface I is: 1411 bool 1412 dr_is_better(a,b,I) { 1413 if( there is a neighbor n on I for which n.dr_priority_present 1414 is false ) { 1415 return a.primary_ip_address > b.primary_ip_address 1416 } else { 1417 return ( a.dr_priority > b.dr_priority ) OR 1418 ( a.dr_priority == b.dr_priority AND 1419 a.primary_ip_address > b.primary_ip_address ) 1420 } 1421 } 1423 The trivial function I_am_DR(I) is defined to aid readability: 1425 bool 1426 I_am_DR(I) { 1427 return DR(I) == me 1428 } 1430 The DR Priority is a 32-bit unsigned number, and the numerically 1431 larger priority is always preferred. A router's idea of the current 1432 DR on an interface can change when a PIM Hello message is received, 1433 when a neighbor times out, or when a router's own DR Priority 1434 changes. If the router becomes the DR or ceases to be the DR, this 1435 will normally cause the DR Register state machine to change state. 1436 Subsequent actions are determined by that state machine. 1438 We note that some PIM implementations do not send Hello messages on 1439 point-to-point interfaces and thus cannot perform DR election on 1440 such interfaces. This is non-compliant behavior. DR election MUST 1441 be performed on ALL active PIM-SM interfaces. 1443 4.3.3. Reducing Prune Propagation Delay on LANs 1445 In addition to the information recorded for the DR Election, the 1446 following per neighbor information is obtained from the LAN Prune 1447 Delay Hello option: 1449 neighbor.lan_prune_delay_present 1450 A flag indicating if the LAN Prune Delay option was present in 1451 the Hello message. 1453 neighbor.tracking_support 1454 A flag storing the value of the T bit in the LAN Prune Delay 1455 option if it is present in the Hello message. This indicates 1456 the neighbor's capability to disable Join message suppression. 1458 neighbor.propagation_delay 1459 The Propagation Delay field of the LAN Prune Delay option (if 1460 present) in the Hello message. 1462 neighbor.override_interval 1463 The Override_Interval field of the LAN Prune Delay option (if 1464 present) in the Hello message. 1466 The additional state described above is deleted along with the DR 1467 neighbor state when the neighbor timeout expires. 1469 Just like the DR_Priority option, the information provided in the LAN 1470 Prune Delay option is not used unless all neighbors on a link 1471 advertise the option. The function below computes this state: 1473 bool 1474 lan_delay_enabled(I) { 1475 for each neighbor on interface I { 1476 if ( neighbor.lan_prune_delay_present == false ) { 1477 return false 1478 } 1479 } 1480 return true 1481 } 1483 The Propagation Delay inserted by a router in the LAN Prune Delay 1484 option expresses the expected message propagation delay on the link 1485 and SHOULD be configurable by the system administrator. It is used 1486 by upstream routers to figure out how long they should wait for a 1487 Join override message before pruning an interface. 1489 PIM implementers SHOULD enforce a lower bound on the permitted values 1490 for this delay to allow for scheduling and processing delays within 1491 their router. Such delays may cause received messages to be 1492 processed later as well as triggered messages to be sent later than 1493 intended. Setting this Propagation Delay to too low a value may 1494 result in temporary forwarding outages because a downstream router 1495 will not be able to override a neighbor's Prune message before the 1496 upstream neighbor stops forwarding. 1498 When all routers on a link are in a position to negotiate a 1499 Propagation Delay different from the default, the largest value from 1500 those advertised by each neighbor is chosen. The function for 1501 computing the Effective Propagation Delay of interface I is: 1503 time_interval 1504 Effective_Propagation_Delay(I) { 1505 if ( lan_delay_enabled(I) == false ) { 1506 return Propagation_delay_default 1507 } 1508 delay = Propagation_Delay(I) 1509 for each neighbor on interface I { 1510 if ( neighbor.propagation_delay > delay ) { 1511 delay = neighbor.propagation_delay 1512 } 1513 } 1514 return delay 1515 } 1517 To avoid synchronization of override messages when multiple 1518 downstream routers share a multi-access link, sending of such 1519 messages is delayed by a small random amount of time. The period of 1520 randomization should represent the size of the PIM router population 1521 on the link. Each router expresses its view of the amount of 1522 randomization necessary in the Override Interval field of the LAN 1523 Prune Delay option. 1525 When all routers on a link are in a position to negotiate an Override 1526 Interval different from the default, the largest value from those 1527 advertised by each neighbor is chosen. The function for computing 1528 the Effective Override Interval of interface I is: 1530 time_interval 1531 Effective_Override_Interval(I) { 1532 if ( lan_delay_enabled(I) == false ) { 1533 return t_override_default 1534 } 1535 delay = Override_Interval(I) 1536 for each neighbor on interface I { 1537 if ( neighbor.override_interval > delay ) { 1538 delay = neighbor.override_interval 1539 } 1540 } 1541 return delay 1542 } 1544 Although the mechanisms are not specified in this document, it is 1545 possible for upstream routers to explicitly track the join membership 1546 of individual downstream routers if Join suppression is disabled. A 1547 router can advertise its willingness to disable Join suppression by 1548 using the T bit in the LAN Prune Delay Hello option. Unless all PIM 1549 routers on a link negotiate this capability, explicit tracking and 1550 the disabling of the Join suppression mechanism are not possible. 1551 The function for computing the state of Suppression on interface I 1552 is: 1554 bool 1555 Suppression_Enabled(I) { 1556 if ( lan_delay_enabled(I) == false ) { 1557 return true 1558 } 1559 for each neighbor on interface I { 1560 if ( neighbor.tracking_support == false ) { 1561 return true 1562 } 1563 } 1564 return false 1565 } 1567 Note that the setting of Suppression_Enabled(I) affects the value of 1568 t_suppressed (see Section 4.10). 1570 4.3.4. Maintaining Secondary Address Lists 1572 Communication of a router's interface secondary addresses to its PIM 1573 neighbors is necessary to provide the neighbors with a mechanism for 1574 mapping next_hop information obtained through their MRIB to a primary 1575 address that can be used as a destination for Join/Prune messages. 1576 The mapping is performed through the NBR macro. The primary address 1577 of a PIM neighbor is obtained from the source IP address used in its 1578 PIM Hello messages. Secondary addresses are carried within the Hello 1579 message in an Address List Hello option. The primary address of the 1580 source interface of the router MUST NOT be listed within the Address 1581 List Hello option. 1583 In addition to the information recorded for the DR Election, the 1584 following per neighbor information is obtained from the Address List 1585 Hello option: 1587 neighbor.secondary_address_list 1588 The list of secondary addresses used by the PIM neighbor on 1589 the interface through which the Hello message was transmitted. 1591 When processing a received PIM Hello message containing an Address 1592 List Hello option, the list of secondary addresses in the message 1593 completely replaces any previously associated secondary addresses for 1594 that neighbor. If a received PIM Hello message does not contain an 1595 Address List Hello option, then all secondary addresses associated 1596 with the neighbor MUST be deleted. If a received PIM Hello message 1597 contains an Address List Hello option that includes the primary 1598 address of the sending router in the list of secondary addresses 1599 (although this is not expected), then the addresses listed in the 1600 message, excluding the primary address, are used to update the 1601 associated secondary addresses for that neighbor. 1603 All the advertised secondary addresses in received Hello messages 1604 must be checked against those previously advertised by all other PIM 1605 neighbors on that interface. If there is a conflict and the same 1606 secondary address was previously advertised by another neighbor, then 1607 only the most recently received mapping MUST be maintained, and an 1608 error message SHOULD be logged to the administrator in a rate-limited 1609 manner. 1611 Within one Address List Hello option, all the addresses MUST be of 1612 the same address family. It is not permitted to mix IPv4 and IPv6 1613 addresses within the same message. In addition, the address family 1614 of the fields in the message SHOULD be the same as the IP source and 1615 destination addresses of the packet header. 1617 4.4. PIM Register Messages 1619 The Designated Router (DR) on a LAN or point-to-point link 1620 encapsulates multicast packets from local sources to the RP for the 1621 relevant group unless it recently received a Register-Stop message 1622 for that (S,G) or (*,G) from the RP. When the DR receives a 1623 Register-Stop message from the RP, it starts a Register-Stop Timer to 1624 maintain this state. Just before the Register-Stop Timer expires, 1625 the DR sends a Null-Register Message to the RP to allow the RP to 1626 refresh the Register-Stop information at the DR. If the Register- 1627 Stop Timer actually expires, the DR will resume encapsulating packets 1628 from the source to the RP. 1630 4.4.1. Sending Register Messages from the DR 1632 Every PIM-SM router has the capability to be a DR. The state machine 1633 below is used to implement Register functionality. For the purposes 1634 of specification, we represent the mechanism to encapsulate packets 1635 to the RP as a Register-Tunnel interface, which is added to or 1636 removed from the (S,G) olist. The tunnel interface then takes part 1637 in the normal packet forwarding rules as specified in Section 4.2. 1639 If register state is maintained, it is maintained only for directly 1640 connected sources and is per-(S,G). There are four states in the 1641 DR's per-(S,G) Register state machine: 1643 Join (J) 1644 The register tunnel is "joined" (the join is actually implicit, 1645 but the DR acts as if the RP has joined the DR on the tunnel 1646 interface). 1648 Prune (P) 1649 The register tunnel is "pruned" (this occurs when a Register- 1650 Stop is received). 1652 Join-Pending (JP) 1653 The register tunnel is pruned but the DR is contemplating adding 1654 it back. 1656 NoInfo (NI) 1657 No information. This is the initial state, and the state when 1658 the router is not the DR. 1660 In addition, a Register-Stop Timer (RST) is kept if the state machine 1661 is not in the NoInfo state. 1663 Figure 1: Per-(S,G) register state machine at a DR in tabular form 1665 +----------++----------------------------------------------------------+ 1666 | || Event | 1667 | ++----------+-----------+-----------+-----------+-----------+ 1668 |Prev State||Register- | Could | Could | Register- | RP changed| 1669 | ||Stop Timer| Register | Register | Stop | | 1670 | ||expires | ->True | ->False | received | | 1671 +----------++----------+-----------+-----------+-----------+-----------+ 1672 |NoInfo ||- | -> J state| - | - | - | 1673 |(NI) || | add reg | | | | 1674 | || | tunnel | | | | 1675 +----------++----------+-----------+-----------+-----------+-----------+ 1676 | ||- | - | -> NI | -> P state| -> J state| 1677 | || | | state | | | 1678 | || | | remove reg| remove reg| update reg| 1679 |Join (J) || | | tunnel | tunnel; | tunnel | 1680 | || | | | set | | 1681 | || | | | Register- | | 1682 | || | | | Stop | | 1683 | || | | | Timer(*) | | 1684 +----------++----------+-----------+-----------+-----------+-----------+ 1685 | ||-> J state| - | -> NI | -> P state| -> J state| 1686 | || | | state | | | 1687 |Join- ||add reg | | | set | add reg | 1688 |Pending ||tunnel | | | Register- | tunnel; | 1689 |(JP) || | | | Stop | cancel | 1690 | || | | | Timer(*) | Register- | 1691 | || | | | | Stop Timer| 1692 +----------++----------+-----------+-----------+-----------+-----------+ 1693 | ||-> JP | - | -> NI | - | -> J state| 1694 | ||state | | state | | | 1695 | ||set | | | | add reg | 1696 |Prune (P) ||Register- | | | | tunnel; | 1697 | ||Stop | | | | cancel | 1698 | ||Timer(**);| | | | Register- | 1699 | ||send Null-| | | | Stop Timer| 1700 | ||Register | | | | | 1701 +----------++----------+-----------+-----------+-----------+-----------+ 1702 Notes: 1704 (*) The Register-Stop Timer is set to a random value chosen 1705 uniformly from the interval ( 0.5 * Register_Suppression_Time, 1706 1.5 * Register_Suppression_Time) minus Register_Probe_Time. 1708 Subtracting off Register_Probe_Time is a bit unnecessary because 1709 it is really small compared to Register_Suppression_Time, but 1710 this was in the old spec and is kept for compatibility. 1712 (**) The Register-Stop Timer is set to Register_Probe_Time. 1714 The following three actions are defined: 1716 Add Register Tunnel 1718 A Register-Tunnel virtual interface, VI, is created (if it doesn't 1719 already exist) with its encapsulation target being RP(G). 1720 DownstreamJPState(S,G,VI) is set to Join state, causing the tunnel 1721 interface to be added to immediate_olist(S,G) and 1722 inherited_olist(S,G). 1724 Remove Register Tunnel 1726 VI is the Register-Tunnel virtual interface with encapsulation 1727 target of RP(G). DownstreamJPState(S,G,VI) is set to NoInfo 1728 state, causing the tunnel interface to be removed from 1729 immediate_olist(S,G) and inherited_olist(S,G). If 1730 DownstreamJPState(S,G,VI) is NoInfo for all (S,G), then VI can be 1731 deleted. 1733 Update Register Tunnel 1735 This action occurs when RP(G) changes. 1737 VI_old is the Register-Tunnel virtual interface with encapsulation 1738 target old_RP(G). A Register-Tunnel virtual interface, VI_new, is 1739 created (if it doesn't already exist) with its encapsulation 1740 target being new_RP(G). DownstreamJPState(S,G,VI_old) is set to 1741 NoInfo state and DownstreamJPState(S,G,VI_new) is set to Join 1742 state. If DownstreamJPState(S,G,VI_old) is NoInfo for all (S,G), 1743 then VI_old can be deleted. 1745 Note that we cannot simply change the encapsulation target of 1746 VI_old because not all groups using that encapsulation tunnel will 1747 have moved to the same new RP. 1749 CouldRegister(S,G) 1751 The macro "CouldRegister" in the state machine is defined as: 1753 bool CouldRegister(S,G) { 1754 return ( I_am_DR( RPF_interface(S) ) AND 1755 KeepaliveTimer(S,G) is running AND 1756 DirectlyConnected(S) == TRUE ) 1757 } 1759 Note that on reception of a packet at the DR from a directly 1760 connected source, KeepaliveTimer(S,G) needs to be set by the 1761 packet forwarding rules before computing CouldRegister(S,G) in the 1762 register state machine, or the first packet from a source won't be 1763 registered. 1765 Encapsulating Data Packets in the Register Tunnel 1767 Conceptually, the Register Tunnel is an interface with a smaller 1768 MTU than the underlying IP interface towards the RP. IP 1769 fragmentation on packets forwarded on the Register Tunnel is 1770 performed based upon this smaller MTU. The encapsulating DR may 1771 perform Path MTU Discovery to the RP to determine the effective 1772 MTU of the tunnel. Fragmentation for the smaller MTU should take 1773 both the outer IP header and the PIM register header overhead into 1774 account. If a multicast packet is fragmented on the way into the 1775 Register Tunnel, each fragment is encapsulated individually so it 1776 contains IP, PIM, and inner IP headers. 1778 In IPv6, the DR MUST perform Path MTU discovery, and an ICMP 1779 Packet Too Big message MUST be sent by the encapsulating DR if it 1780 receives a packet that will not fit in the effective MTU of the 1781 tunnel. If the MTU between the DR and the RP results in the 1782 effective tunnel MTU being smaller than 1280 (the IPv6 minimum 1783 MTU), the DR MUST send Fragmentation Required messages with an MTU 1784 value of 1280 and MUST fragment its PIM register messages as 1785 required, using an IPv6 fragmentation header between the outer 1786 IPv6 header and the PIM Register header. 1788 The TTL of a forwarded data packet is decremented before it is 1789 encapsulated in the Register Tunnel. The encapsulating packet 1790 uses the normal TTL that the router would use for any locally- 1791 generated IP packet. 1793 The IP ECN bits should be copied from the original packet to the 1794 IP header of the encapsulating packet. They SHOULD NOT be set 1795 independently by the encapsulating router. 1797 The Diffserv Code Point (DSCP) should be copied from the original 1798 packet to the IP header of the encapsulating packet. It MAY be 1799 set independently by the encapsulating router, based upon static 1800 configuration or traffic classification. See [12] for more 1801 discussion on setting the DSCP on tunnels. 1803 Handling Register-Stop(*,G) Messages at the DR 1805 An old RP might send a Register-Stop message with the source 1806 address set to all zeros. This was the normal course of action in 1807 RFC 2362 when the Register message matched against (*,G) state at 1808 the RP, and it was defined as meaning "stop encapsulating all 1809 sources for this group". However, the behavior of such a 1810 Register-Stop(*,G) is ambiguous or incorrect in some 1811 circumstances. 1813 We specify that an RP should not send Register-Stop(*,G) messages, 1814 but for compatibility, a DR should be able to accept one if it is 1815 received. 1817 A Register-Stop(*,G) should be treated as a Register-Stop(S,G) for 1818 all (S,G) Register state machines that are not in the NoInfo 1819 state. A router should not apply a Register-Stop(*,G) to sources 1820 that become active after the Register-Stop(*,G) was received. 1822 4.4.2. Receiving Register Messages at the RP 1824 When an RP receives a Register message, the course of action is 1825 decided according to the following pseudocode: 1827 packet_arrives_on_rp_tunnel( pkt ) { 1828 if( outer.dst is not one of my addresses ) { 1829 drop the packet silently. 1830 # Note: this may be a spoofing attempt 1831 } 1832 if( I_am_RP(G) AND outer.dst == RP(G) ) { 1833 sentRegisterStop = FALSE; 1834 if ( SPTbit(S,G) OR 1835 ( SwitchToSptDesired(S,G) AND 1836 ( inherited_olist(S,G) == NULL ))) { 1837 send Register-Stop(S,G) to outer.src 1838 sentRegisterStop = TRUE; 1839 } 1840 if ( SPTbit(S,G) OR SwitchToSptDesired(S,G) ) { 1841 if ( sentRegisterStop == TRUE ) { 1842 set KeepaliveTimer(S,G) to RP_Keepalive_Period; 1843 } else { 1844 set KeepaliveTimer(S,G) to Keepalive_Period; 1845 } 1846 } 1847 if( !SPTbit(S,G) AND ! pkt.NullRegisterBit ) { 1848 decapsulate and forward the inner packet to 1849 inherited_olist(S,G,rpt) # Note (+) 1850 } 1851 } else { 1852 send Register-Stop(S,G) to outer.src 1853 # Note (*) 1854 } 1855 } 1856 outer.dst is the IP destination address of the encapsulating header. 1858 outer.src is the IP source address of the encapsulating header, i.e., 1859 the DR's address. 1861 I_am_RP(G) is true if the group-to-RP mapping indicates that this 1862 router is the RP for the group. 1864 Note (*): This may block traffic from S for Register_Suppression_Time 1865 if the DR learned about a new group-to-RP mapping before the RP 1866 did. However, this doesn't matter unless we figure out some way 1867 for the RP also to accept (*,G) joins when it doesn't yet realize 1868 that it is about to become the RP for G. This will all get sorted 1869 out once the RP learns the new group-to-rp mapping. We decided to 1870 do nothing about this and just accept the fact that PIM may suffer 1871 interrupted (*,G) connectivity following an RP change. 1873 Note (+): Implementations SHOULD NOT make this a special case, but 1874 SHOULD arrange that this path rejoin the normal packet forwarding 1875 path. All of the appropriate actions from the "On receipt of data 1876 from S to G on interface iif" pseudocode in Section 4.2 should be 1877 performed. 1879 KeepaliveTimer(S,G) is restarted at the RP when packets arrive on the 1880 proper tunnel interface and the RP desires to switch to the SPT or 1881 the SPTbit is already set. This may cause the upstream (S,G) state 1882 machine to trigger a join if the inherited_olist(S,G) is not NULL. 1884 An RP should preserve (S,G) state that was created in response to a 1885 Register message for at least ( 3 * Register_Suppression_Time ); 1886 otherwise, the RP may stop joining (S,G) before the DR for S has 1887 restarted sending registers. Traffic would then be interrupted until 1888 the Register-Stop Timer expires at the DR. 1890 Thus, at the RP, KeepaliveTimer(S,G) should be restarted to ( 3 * 1891 Register_Suppression_Time + Register_Probe_Time ). 1893 When forwarding a packet from the Register Tunnel, the TTL of the 1894 original data packet is decremented after it is decapsulated. 1896 The IP ECN bits should be copied from the IP header of the Register 1897 packet to the decapsulated packet. 1899 The Diffserv Code Point (DSCP) should be copied from the IP header of 1900 the Register packet to the decapsulated packet. The RP MAY retain 1901 the DSCP of the inner packet or re-classify the packet and apply a 1902 different DSCP. Scenarios where each of these might be useful are 1903 discussed in [12]. 1905 4.5. PIM Join/Prune Messages 1907 A PIM Join/Prune message consists of a list of groups and a list of 1908 Joined and Pruned sources for each group. When processing a received 1909 Join/Prune message, each Joined or Pruned source for a Group is 1910 effectively considered individually, and applies to one or more of 1911 the following state machines. When considering a Join/Prune message 1912 whose Upstream Neighbor Address field addresses this router, (*,G) 1913 Joins and Prunes can affect both the (*,G) and (S,G,rpt) downstream 1914 state machines, while (S,G), and (S,G,rpt) Joins and Prunes can only 1915 affect their respective downstream state machines. When considering 1916 a Join/Prune message whose Upstream Neighbor Address field addresses 1917 another router, most Join or Prune messages could affect each 1918 upstream state machine. 1920 In general, a PIM Join/Prune message should only be accepted for 1921 processing if it comes from a known PIM neighbor. A PIM router hears 1922 about PIM neighbors through PIM Hello messages. If a router receives 1923 a Join/Prune message from a particular IP source address and it has 1924 not seen a PIM Hello message from that source address, then the 1925 Join/Prune message SHOULD be discarded without further processing. 1926 In addition, if the Hello message from a neighbor was authenticated 1927 using IPsec AH (see Section 6.3), then all Join/Prune messages from 1928 that neighbor MUST also be authenticated using IPsec AH. 1930 We note that some older PIM implementations incorrectly fail to send 1931 Hello messages on point-to-point interfaces, so we also RECOMMEND 1932 that a configuration option be provided to allow interoperation with 1933 such older routers, but that this configuration option SHOULD NOT be 1934 enabled by default. 1936 4.5.1. Receiving (*,G) Join/Prune Messages 1938 When a router receives a Join(*,G), it must first check to see 1939 whether the RP in the message matches RP(G) (the router's idea of who 1940 the RP is). If the RP in the message does not match RP(G), the 1941 Join(*,G) should be silently dropped. (Note that other source list 1942 entries, such as (S,G,rpt) or (S,G), in the same Group-Specific Set 1943 should still be processed.) If a router has no RP information (e.g., 1944 has not recently received a BSR message), then it may choose to 1945 accept Join(*,G) and treat the RP in the message as RP(G). Received 1946 Prune(*,G) messages are processed even if the RP in the message does 1947 not match RP(G). 1949 The per-interface state machine for receiving (*,G) Join/Prune 1950 Messages is given below. There are three states: 1952 NoInfo (NI) 1953 The interface has no (*,G) Join state and no timers running. 1955 Join (J) 1956 The interface has (*,G) Join state, which will cause the 1957 router to forward packets destined for G from this interface 1958 except if there is also (S,G,rpt) prune information (see 1959 Section 4.5.3) or the router lost an assert on this interface. 1961 Prune-Pending (PP) 1962 The router has received a Prune(*,G) on this interface from a 1963 downstream neighbor and is waiting to see whether the prune 1964 will be overridden by another downstream router. For 1965 forwarding purposes, the Prune-Pending state functions exactly 1966 like the Join state. 1968 In addition, the state machine uses two timers: 1970 Expiry Timer (ET) 1971 This timer is restarted when a valid Join(*,G) is received. 1972 Expiry of the Expiry Timer causes the interface state to 1973 revert to NoInfo for this group. 1975 Prune-Pending Timer (PPT) 1976 This timer is set when a valid Prune(*,G) is received. Expiry 1977 of the Prune-Pending Timer causes the interface state to 1978 revert to NoInfo for this group. 1980 Figure 2: Downstream per-interface (*,G) state machine in tabular form 1982 +------------++--------------------------------------------------------+ 1983 | || Event | 1984 | ++-------------+--------------+-------------+-------------+ 1985 |Prev State ||Receive | Receive | Prune- | Expiry Timer| 1986 | ||Join(*,G) | Prune(*,G) | Pending | Expires | 1987 | || | | Timer | | 1988 | || | | Expires | | 1989 +------------++-------------+--------------+-------------+-------------+ 1990 | ||-> J state | -> NI state | - | - | 1991 |NoInfo (NI) ||start Expiry | | | | 1992 | ||Timer | | | | 1993 +------------++-------------+--------------+-------------+-------------+ 1994 | ||-> J state | -> PP state | - | -> NI state | 1995 |Join (J) ||restart | start Prune- | | | 1996 | ||Expiry Timer | Pending | | | 1997 | || | Timer | | | 1998 +------------++-------------+--------------+-------------+-------------+ 1999 |Prune- ||-> J state | -> PP state | -> NI state | -> NI state | 2000 |Pending (PP)||restart | | Send Prune- | | 2001 | ||Expiry Timer | | Echo(*,G) | | 2002 +------------++-------------+--------------+-------------+-------------+ 2004 The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" 2005 imply receiving a Join or Prune targeted to this router's primary IP 2006 address on the received interface. If the upstream neighbor address 2007 field is not correct, these state transitions in this state machine 2008 MUST NOT occur, although seeing such a packet may cause state 2009 transitions in other state machines. 2011 On unnumbered interfaces on point-to-point links, the router's 2012 address should be the same as the source address it chose for the 2013 Hello message it sent over that interface. However, on point-to- 2014 point links it is RECOMMENDED that for backwards compatibility PIM 2015 Join/Prune messages with an upstream neighbor address field of all 2016 zeros also be accepted. 2018 Transitions from NoInfo State 2020 When in NoInfo state, the following event may trigger a transition: 2022 Receive Join(*,G) 2023 A Join(*,G) is received on interface I with its Upstream 2024 Neighbor Address set to the router's primary IP address on I. 2026 The (*,G) downstream state machine on interface I transitions 2027 to the Join state. The Expiry Timer (ET) is started and set 2028 to the HoldTime from the triggering Join/Prune message. 2030 Transitions from Join State 2032 When in Join state, the following events may trigger a transition: 2034 Receive Join(*,G) 2035 A Join(*,G) is received on interface I with its Upstream 2036 Neighbor Address set to the router's primary IP address on I. 2038 The (*,G) downstream state machine on interface I remains in 2039 Join state, and the Expiry Timer (ET) is restarted, set to 2040 maximum of its current value and the HoldTime from the 2041 triggering Join/Prune message. 2043 Receive Prune(*,G) 2044 A Prune(*,G) is received on interface I with its Upstream 2045 Neighbor Address set to the router's primary IP address on I. 2047 The (*,G) downstream state machine on interface I transitions 2048 to the Prune-Pending state. The Prune-Pending Timer is 2049 started. It is set to the J/P_Override_Interval(I) if the 2050 router has more than one neighbor on that interface; 2051 otherwise, it is set to zero, causing it to expire 2052 immediately. 2054 Expiry Timer Expires 2055 The Expiry Timer for the (*,G) downstream state machine on 2056 interface I expires. 2058 The (*,G) downstream state machine on interface I transitions 2059 to the NoInfo state. 2061 Transitions from Prune-Pending State 2063 When in Prune-Pending state, the following events may trigger a 2064 transition: 2066 Receive Join(*,G) 2067 A Join(*,G) is received on interface I with its Upstream 2068 Neighbor Address set to the router's primary IP address on I. 2070 The (*,G) downstream state machine on interface I transitions 2071 to the Join state. The Prune-Pending Timer is canceled 2072 (without triggering an expiry event). The Expiry Timer is 2073 restarted, set to maximum of its current value and the 2074 HoldTime from the triggering Join/Prune message. 2076 Expiry Timer Expires 2077 The Expiry Timer for the (*,G) downstream state machine on 2078 interface I expires. 2080 The (*,G) downstream state machine on interface I transitions 2081 to the NoInfo state. 2083 Prune-Pending Timer Expires 2084 The Prune-Pending Timer for the (*,G) downstream state machine 2085 on interface I expires. 2087 The (*,G) downstream state machine on interface I transitions 2088 to the NoInfo state. A PruneEcho(*,G) is sent onto the subnet 2089 connected to interface I. 2091 The action "Send PruneEcho(*,G)" is triggered when the router 2092 stops forwarding on an interface as a result of a prune. A 2093 PruneEcho(*,G) is simply a Prune(*,G) message sent by the 2094 upstream router on a LAN with its own address in the Upstream 2095 Neighbor Address field. Its purpose is to add additional 2096 reliability so that if a Prune that should have been 2097 overridden by another router is lost locally on the LAN, then 2098 the PruneEcho may be received and cause the override to 2099 happen. A PruneEcho(*,G) need not be sent on an interface 2100 that contains only a single PIM neighbor during the time this 2101 state machine was in Prune-Pending state. 2103 4.5.2. Receiving (S,G) Join/Prune Messages 2105 The per-interface state machine for receiving (S,G) Join/Prune 2106 messages is given below and is almost identical to that for (*,G) 2107 messages. There are three states: 2109 NoInfo (NI) 2110 The interface has no (S,G) Join state and no (S,G) timers 2111 running. 2113 Join (J) 2114 The interface has (S,G) Join state, which will cause the 2115 router to forward packets from S destined for G from this 2116 interface if the (S,G) state is active (the SPTbit is set) 2117 except if the router lost an assert on this interface. 2119 Prune-Pending (PP) 2120 The router has received a Prune(S,G) on this interface from a 2121 downstream neighbor and is waiting to see whether the prune 2122 will be overridden by another downstream router. For 2123 forwarding purposes, the Prune-Pending state functions exactly 2124 like the Join state. 2126 In addition, there are two timers: 2128 Expiry Timer (ET) 2129 This timer is set when a valid Join(S,G) is received. Expiry 2130 of the Expiry Timer causes this state machine to revert to 2131 NoInfo state. 2133 Prune-Pending Timer (PPT) 2134 This timer is set when a valid Prune(S,G) is received. Expiry 2135 of the Prune-Pending Timer causes this state machine to revert 2136 to NoInfo state. 2138 Figure 3: Downstream per-interface (S,G) state machine in tabular form 2140 +------------++--------------------------------------------------------+ 2141 | || Event | 2142 | ++-------------+--------------+-------------+-------------+ 2143 |Prev State ||Receive | Receive | Prune- | Expiry Timer| 2144 | ||Join(S,G) | Prune(S,G) | Pending | Expires | 2145 | || | | Timer | | 2146 | || | | Expires | | 2147 +------------++-------------+--------------+-------------+-------------+ 2148 | ||-> J state | -> NI state | - | - | 2149 |NoInfo (NI) ||start Expiry | | | | 2150 | ||Timer | | | | 2151 +------------++-------------+--------------+-------------+-------------+ 2152 | ||-> J state | -> PP state | - | -> NI state | 2153 |Join (J) ||restart | start Prune- | | | 2154 | ||Expiry Timer | Pending | | | 2155 | || | Timer | | | 2156 +------------++-------------+--------------+-------------+-------------+ 2157 |Prune- ||-> J state | -> PP state | -> NI state | -> NI state | 2158 |Pending (PP)||restart | | Send Prune- | | 2159 | ||Expiry Timer | | Echo(S,G) | | 2160 +------------++-------------+--------------+-------------+-------------+ 2162 The transition events "Receive Join(S,G)" and "Receive Prune(S,G)" 2163 imply receiving a Join or Prune targeted to this router's primary IP 2164 address on the received interface. If the upstream neighbor address 2165 field is not correct, these state transitions in this state machine 2166 MUST NOT occur, although seeing such a packet may cause state 2167 transitions in other state machines. 2169 On unnumbered interfaces on point-to-point links, the router's 2170 address SHOULD be the same as the source address it chose for the 2171 Hello message it sent over that interface. However, on point-to- 2172 point links it is RECOMMENDED that for backwards compatibility PIM 2173 Join/Prune messages with an upstream neighbor address field of all 2174 zeros also be accepted. 2176 Transitions from NoInfo State 2178 When in NoInfo state, the following event may trigger a transition: 2180 Receive Join(S,G) 2181 A Join(S,G) is received on interface I with its Upstream 2182 Neighbor Address set to the router's primary IP address on I. 2184 The (S,G) downstream state machine on interface I transitions 2185 to the Join state. The Expiry Timer (ET) is started and set 2186 to the HoldTime from the triggering Join/Prune message. 2188 Transitions from Join State 2190 When in Join state, the following events may trigger a transition: 2192 Receive Join(S,G) 2193 A Join(S,G) is received on interface I with its Upstream 2194 Neighbor Address set to the router's primary IP address on I. 2196 The (S,G) downstream state machine on interface I remains in 2197 Join state, and the Expiry Timer (ET) is restarted, set to 2198 maximum of its current value and the HoldTime from the 2199 triggering Join/Prune message. 2201 Receive Prune(S,G) 2202 A Prune(S,G) is received on interface I with its Upstream 2203 Neighbor Address set to the router's primary IP address on I. 2205 The (S,G) downstream state machine on interface I transitions 2206 to the Prune-Pending state. The Prune-Pending Timer is 2207 started. It is set to the J/P_Override_Interval(I) if the 2208 router has more than one neighbor on that interface; 2209 otherwise, it is set to zero, causing it to expire 2210 immediately. 2212 Expiry Timer Expires 2213 The Expiry Timer for the (S,G) downstream state machine on 2214 interface I expires. 2216 The (S,G) downstream state machine on interface I transitions 2217 to the NoInfo state. 2219 Transitions from Prune-Pending State 2221 When in Prune-Pending state, the following events may trigger a 2222 transition: 2224 Receive Join(S,G) 2225 A Join(S,G) is received on interface I with its Upstream 2226 Neighbor Address set to the router's primary IP address on I. 2228 The (S,G) downstream state machine on interface I transitions 2229 to the Join state. The Prune-Pending Timer is canceled 2230 (without triggering an expiry event). The Expiry Timer is 2231 restarted, set to maximum of its current value and the 2232 HoldTime from the triggering Join/Prune message. 2234 Expiry Timer Expires 2235 The Expiry Timer for the (S,G) downstream state machine on 2236 interface I expires. 2238 The (S,G) downstream state machine on interface I transitions 2239 to the NoInfo state. 2241 Prune-Pending Timer Expires 2242 The Prune-Pending Timer for the (S,G) downstream state machine 2243 on interface I expires. 2245 The (S,G) downstream state machine on interface I transitions 2246 to the NoInfo state. A PruneEcho(S,G) is sent onto the subnet 2247 connected to interface I. 2249 The action "Send PruneEcho(S,G)" is triggered when the router 2250 stops forwarding on an interface as a result of a prune. A 2251 PruneEcho(S,G) is simply a Prune(S,G) message sent by the 2252 upstream router on a LAN with its own address in the Upstream 2253 Neighbor Address field. Its purpose is to add additional 2254 reliability so that if a Prune that should have been 2255 overridden by another router is lost locally on the LAN, then 2256 the PruneEcho may be received and cause the override to 2257 happen. A PruneEcho(S,G) need not be sent on an interface 2258 that contains only a single PIM neighbor during the time this 2259 state machine was in Prune-Pending state. 2261 4.5.3. Receiving (S,G,rpt) Join/Prune Messages 2263 The per-interface state machine for receiving (S,G,rpt) Join/Prune 2264 messages is given below. There are five states: 2266 NoInfo (NI) 2267 The interface has no (S,G,rpt) Prune state and no (S,G,rpt) 2268 timers running. 2270 Prune (P) 2271 The interface has (S,G,rpt) Prune state, which will cause the 2272 router not to forward packets from S destined for G from this 2273 interface even though the interface has active (*,G) Join 2274 state. 2276 Prune-Pending (PP) 2277 The router has received a Prune(S,G,rpt) on this interface 2278 from a downstream neighbor and is waiting to see whether the 2279 prune will be overridden by another downstream router. For 2280 forwarding purposes, the Prune-Pending state functions exactly 2281 like the NoInfo state. 2283 PruneTmp (P') 2284 This state is a transient state that for forwarding purposes 2285 behaves exactly like the Prune state. A (*,G) Join has been 2286 received (which may cancel the (S,G,rpt) Prune). As we parse 2287 the Join/Prune message from top to bottom, we first enter this 2288 state if the message contains a (*,G) Join. Later in the 2289 message, we will normally encounter an (S,G,rpt) prune to 2290 reinstate the Prune state. However, if we reach the end of 2291 the message without encountering such an (S,G,rpt) prune, then 2292 we will revert to NoInfo state in this state machine. 2294 As no time is spent in this state, no timers can expire. 2296 Prune-Pending-Tmp (PP') 2297 This state is a transient state that is identical to P' except 2298 that it is associated with the PP state rather than the P 2299 state. For forwarding purposes, PP' behaves exactly like PP 2300 state. 2302 In addition, there are two timers: 2304 Expiry Timer (ET) 2305 This timer is set when a valid Prune(S,G,rpt) is received. 2306 Expiry of the Expiry Timer causes this state machine to revert 2307 to NoInfo state. 2309 Prune-Pending Timer (PPT) 2310 This timer is set when a valid Prune(S,G,rpt) is received. 2311 Expiry of the Prune-Pending Timer causes this state machine to 2312 move on to Prune state. 2314 Figure 4: Downstream per-interface (S,G,rpt) state machine 2315 in tabular form 2317 +----------++----------------------------------------------------------+ 2318 | || Event | 2319 | ++---------+----------+----------+--------+--------+--------+ 2320 |Prev ||Receive | Receive | Receive | End of | Prune- | Expiry | 2321 |State ||Join(*,G)| Join | Prune | Message| Pending| Timer | 2322 | || | (S,G,rpt)| (S,G,rpt)| | Timer | Expires| 2323 | || | | | | Expires| | 2324 +----------++---------+----------+----------+--------+--------+--------+ 2325 | ||- | - | -> PP | - | - | - | 2326 | || | | state | | | | 2327 | || | | start | | | | 2328 |NoInfo || | | Prune- | | | | 2329 |(NI) || | | Pending | | | | 2330 | || | | Timer; | | | | 2331 | || | | start | | | | 2332 | || | | Expiry | | | | 2333 | || | | Timer | | | | 2334 +----------++---------+----------+----------+--------+--------+--------+ 2335 | ||-> P' | -> NI | -> P | - | - | -> NI | 2336 | ||state | state | state | | | state | 2337 |Prune (P) || | | restart | | | | 2338 | || | | Expiry | | | | 2339 | || | | Timer | | | | 2340 +----------++---------+----------+----------+--------+--------+--------+ 2341 |Prune- ||-> PP' | -> NI | - | - | -> P | - | 2342 |Pending ||state | state | | | state | | 2343 |(PP) || | | | | | | 2344 +----------++---------+----------+----------+--------+--------+--------+ 2345 | ||- | - | -> P | -> NI | - | - | 2346 |PruneTmp || | | state | state | | | 2347 |(P') || | | restart | | | | 2348 | || | | Expiry | | | | 2349 | || | | Timer | | | | 2350 +----------++---------+----------+----------+--------+--------+--------+ 2351 | ||- | - | -> PP | -> NI | - | - | 2352 |Prune- || | | state | state | | | 2353 |Pending- || | | restart | | | | 2354 |Tmp (PP') || | | Expiry | | | | 2355 | || | | Timer | | | | 2356 +----------++---------+----------+----------+--------+--------+--------+ 2358 The transition events "Receive Join(S,G,rpt)", "Receive 2359 Prune(S,G,rpt)", and "Receive Join(*,G)" imply receiving a Join or 2360 Prune targeted to this router's primary IP address on the received 2361 interface. If the upstream neighbor address field is not correct, 2362 these state transitions in this state machine MUST NOT occur, 2363 although seeing such a packet may cause state transitions in other 2364 state machines. 2366 On unnumbered interfaces on point-to-point links, the router's 2367 address should be the same as the source address it chose for the 2368 Hello message it sent over that interface. However, on point-to- 2369 point links it is RECOMMENDED that PIM Join/Prune messages with an 2370 upstream neighbor address field of all zeros also be accepted. 2372 Transitions from NoInfo State 2374 When in NoInfo (NI) state, the following event may trigger a 2375 transition: 2377 Receive Prune(S,G,rpt) 2378 A Prune(S,G,rpt) is received on interface I with its Upstream 2379 Neighbor Address set to the router's primary IP address on I. 2381 The (S,G,rpt) downstream state machine on interface I 2382 transitions to the Prune-Pending state. The Expiry Timer (ET) 2383 is started and set to the HoldTime from the triggering 2384 Join/Prune message. The Prune-Pending Timer is started. It 2385 is set to the J/P_Override_Interval(I) if the router has more 2386 than one neighbor on that interface; otherwise, it is set to 2387 zero, causing it to expire immediately. 2389 Transitions from Prune-Pending State 2391 When in Prune-Pending (PP) state, the following events may trigger a 2392 transition: 2394 Receive Join(*,G) 2395 A Join(*,G) is received on interface I with its Upstream 2396 Neighbor Address set to the router's primary IP address on I. 2398 The (S,G,rpt) downstream state machine on interface I 2399 transitions to Prune-Pending-Tmp state whilst the remainder of 2400 the compound Join/Prune message containing the Join(*,G) is 2401 processed. 2403 Receive Join(S,G,rpt) 2404 A Join(S,G,rpt) is received on interface I with its Upstream 2405 Neighbor Address set to the router's primary IP address on I. 2407 The (S,G,rpt) downstream state machine on interface I 2408 transitions to NoInfo state. ET and PPT are canceled. 2410 Prune-Pending Timer Expires 2411 The Prune-Pending Timer for the (S,G,rpt) downstream state 2412 machine on interface I expires. 2414 The (S,G,rpt) downstream state machine on interface I 2415 transitions to the Prune state. 2417 Transitions from Prune State 2419 When in Prune (P) state, the following events may trigger a 2420 transition: 2422 Receive Join(*,G) 2423 A Join(*,G) is received on interface I with its Upstream 2424 Neighbor Address set to the router's primary IP address on I. 2426 The (S,G,rpt) downstream state machine on interface I 2427 transitions to PruneTmp state whilst the remainder of the 2428 compound Join/Prune message containing the Join(*,G) is 2429 processed. 2431 Receive Join(S,G,rpt) 2432 A Join(S,G,rpt) is received on interface I with its Upstream 2433 Neighbor Address set to the router's primary IP address on I. 2435 The (S,G,rpt) downstream state machine on interface I 2436 transitions to NoInfo state. ET and PPT are canceled. 2438 Receive Prune(S,G,rpt) 2439 A Prune(S,G,rpt) is received on interface I with its Upstream 2440 Neighbor Address set to the router's primary IP address on I. 2442 The (S,G,rpt) downstream state machine on interface I remains 2443 in Prune state. The Expiry Timer (ET) is restarted, set to 2444 maximum of its current value and the HoldTime from the 2445 triggering Join/Prune message. 2447 Expiry Timer Expires 2448 The Expiry Timer for the (S,G,rpt) downstream state machine on 2449 interface I expires. 2451 The (S,G,rpt) downstream state machine on interface I 2452 transitions to the NoInfo state. 2454 Transitions from Prune-Pending-Tmp State 2456 When in Prune-Pending-Tmp (PP') state and processing a compound 2457 Join/Prune message, the following events may trigger a transition: 2459 Receive Prune(S,G,rpt) 2460 The compound Join/Prune message contains a Prune(S,G,rpt) that 2461 is received on interface I with its Upstream Neighbor Address 2462 set to the router's primary IP address on I. 2464 The (S,G,rpt) downstream state machine on interface I 2465 transitions back to the Prune-Pending state. The Expiry Timer 2466 (ET) is restarted, set to maximum of its current value and the 2467 HoldTime from the triggering Join/Prune message. 2469 End of Message 2470 The end of the compound Join/Prune message is reached. 2472 The (S,G,rpt) downstream state machine on interface I 2473 transitions to the NoInfo state. ET and PPT are canceled. 2475 Transitions from PruneTmp State 2477 When in PruneTmp (P') state and processing a compound Join/Prune 2478 message, the following events may trigger a transition: 2480 Receive Prune(S,G,rpt) 2481 The compound Join/Prune message contains a Prune(S,G,rpt). 2483 The (S,G,rpt) downstream state machine on interface I 2484 transitions back to the Prune state. The Expiry Timer (ET) is 2485 restarted, set to maximum of its current value and the 2486 HoldTime from the triggering Join/Prune message. 2488 End of Message 2489 The end of the compound Join/Prune message is reached. 2491 The (S,G,rpt) downstream state machine on interface I 2492 transitions to the NoInfo state. ET is canceled. 2494 Notes: 2496 Receiving a Prune(*,G) does not affect the (S,G,rpt) downstream state 2497 machine. 2499 4.5.4. Sending (*,G) Join/Prune Messages 2501 The per-interface state machines for (*,G) hold join state from 2502 downstream PIM routers. This state then determines whether a router 2503 needs to propagate a Join(*,G) upstream towards the RP. 2505 If a router wishes to propagate a Join(*,G) upstream, it must also 2506 watch for messages on its upstream interface from other routers on 2507 that subnet, and these may modify its behavior. If it sees a 2508 Join(*,G) to the correct upstream neighbor, it should suppress its 2509 own Join(*,G). If it sees a Prune(*,G) to the correct upstream 2510 neighbor, it should be prepared to override that prune by sending a 2511 Join(*,G) almost immediately. Finally, if it sees the Generation ID 2512 (see Section 4.3) of the correct upstream neighbor change, it knows 2513 that the upstream neighbor has lost state, and it should be prepared 2514 to refresh the state by sending a Join(*,G) almost immediately. 2516 If a (*,G) Assert occurs on the upstream interface, and this changes 2517 this router's idea of the upstream neighbor, it should be prepared to 2518 ensure that the Assert winner is aware of downstream routers by 2519 sending a Join(*,G) almost immediately. 2521 In addition, if the MRIB changes to indicate that the next hop 2522 towards the RP has changed, and either the upstream interface changes 2523 or there is no Assert winner on the upstream interface, the router 2524 should prune off from the old next hop and join towards the new next 2525 hop. 2527 The upstream (*,G) state machine only contains two states: 2529 Not Joined 2530 The downstream state machines indicate that the router does not 2531 need to join the RP tree for this group. 2533 Joined 2534 The downstream state machines indicate that the router should join 2535 the RP tree for this group. 2537 In addition, one timer JT(*,G) is kept that is used to trigger the 2538 sending of a Join(*,G) to the upstream next hop towards the RP, 2539 RPF'(*,G). 2541 Figure 5: Upstream (*,G) state machine in tabular form 2543 +-------------------++-------------------------------------------------+ 2544 | || Event | 2545 | Prev State ++------------------------+------------------------+ 2546 | || JoinDesired(*,G) | JoinDesired(*,G) | 2547 | || ->True | ->False | 2548 +-------------------++------------------------+------------------------+ 2549 | || -> J state | - | 2550 | NotJoined (NJ) || Send Join(*,G); | | 2551 | || Set Join Timer to | | 2552 | || t_periodic | | 2553 +-------------------++------------------------+------------------------+ 2554 | Joined (J) || - | -> NJ state | 2555 | || | Send Prune(*,G); | 2556 | || | Cancel Join Timer | 2557 +-------------------++------------------------+------------------------+ 2559 In addition, we have the following transitions, which occur within 2560 the Joined state: 2562 +----------------------------------------------------------------------+ 2563 | In Joined (J) State | 2564 +----------------+-----------------+-----------------+-----------------+ 2565 |Timer Expires | See Join(*,G) | See Prune(*,G) | RPF'(*,G) | 2566 | | to RPF'(*,G) | to RPF'(*,G) | changes due to | 2567 | | | | an Assert | 2568 +----------------+-----------------+-----------------+-----------------+ 2569 |Send | Increase Join | Decrease Join | Decrease Join | 2570 |Join(*,G); Set | Timer to | Timer to | Timer to | 2571 |Join Timer to | t_joinsuppress | t_override | t_override | 2572 |t_periodic | | | | 2573 +----------------+-----------------+-----------------+-----------------+ 2575 +----------------------------------------------------------------------+ 2576 | In Joined (J) State | 2577 +----------------------------------+-----------------------------------+ 2578 | RPF'(*,G) changes not | RPF'(*,G) GenID changes | 2579 | due to an Assert | | 2580 +----------------------------------+-----------------------------------+ 2581 | Send Join(*,G) to new | Decrease Join Timer to | 2582 | next hop; Send | t_override | 2583 | Prune(*,G) to old next | | 2584 | hop; Set Join Timer to | | 2585 | t_periodic | | 2586 +----------------------------------+-----------------------------------+ 2587 This state machine uses the following macro: 2589 bool JoinDesired(*,G) { 2590 if (immediate_olist(*,G) != NULL) 2591 return TRUE 2592 else 2593 return FALSE 2594 } 2596 JoinDesired(*,G) is true when the router has forwarding state that 2597 would cause it to forward traffic for G using shared tree state. 2598 Note that although JoinDesired is true, the router's sending of a 2599 Join(*,G) message may be suppressed by another router sending a 2600 Join(*,G) onto the upstream interface. 2602 Transitions from NotJoined State 2604 When the upstream (*,G) state machine is in NotJoined state, the 2605 following event may trigger a state transition: 2607 JoinDesired(*,G) becomes True 2608 The macro JoinDesired(*,G) becomes True, e.g., because the 2609 downstream state for (*,G) has changed so that at least one 2610 interface is in immediate_olist(*,G). 2612 The upstream (*,G) state machine transitions to Joined state. 2613 Send Join(*,G) to the appropriate upstream neighbor, which is 2614 RPF'(*,G). Set the Join Timer (JT) to expire after t_periodic 2615 seconds. 2617 Transitions from Joined State 2619 When the upstream (*,G) state machine is in Joined state, the 2620 following events may trigger state transitions: 2622 JoinDesired(*,G) becomes False 2623 The macro JoinDesired(*,G) becomes False, e.g., because the 2624 downstream state for (*,G) has changed so no interface is in 2625 immediate_olist(*,G). 2627 The upstream (*,G) state machine transitions to NotJoined 2628 state. Send Prune(*,G) to the appropriate upstream neighbor, 2629 which is RPF'(*,G). Cancel the Join Timer (JT). 2631 Join Timer Expires 2632 The Join Timer (JT) expires, indicating time to send a 2633 Join(*,G) 2634 Send Join(*,G) to the appropriate upstream neighbor, which is 2635 RPF'(*,G). Restart the Join Timer (JT) to expire after 2636 t_periodic seconds. 2638 See Join(*,G) to RPF'(*,G) 2639 This event is only relevant if RPF_interface(RP(G)) is a 2640 shared medium. This router sees another router on 2641 RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G). This 2642 causes this router to suppress its own Join. 2644 The upstream (*,G) state machine remains in Joined state. 2646 Let t_joinsuppress be the minimum of t_suppressed and the 2647 HoldTime from the Join/Prune message triggering this event. If 2648 the Join Timer is set to expire in less than t_joinsuppress 2649 seconds, reset it so that it expires after t_joinsuppress 2650 seconds. If the Join Timer is set to expire in more than 2651 t_joinsuppress seconds, leave it unchanged. 2653 See Prune(*,G) to RPF'(*,G) 2654 This event is only relevant if RPF_interface(RP(G)) is a 2655 shared medium. This router sees another router on 2656 RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G). As this 2657 router is in Joined state, it must override the Prune after a 2658 short random interval. 2660 The upstream (*,G) state machine remains in Joined state. If 2661 the Join Timer is set to expire in more than t_override 2662 seconds, reset it so that it expires after t_override seconds. 2663 If the Join Timer is set to expire in less than t_override 2664 seconds, leave it unchanged. 2666 RPF'(*,G) changes due to an Assert 2667 The current next hop towards the RP changes due to an 2668 Assert(*,G) on the RPF_interface(RP(G)). 2670 The upstream (*,G) state machine remains in Joined state. If 2671 the Join Timer is set to expire in more than t_override 2672 seconds, reset it so that it expires after t_override seconds. 2673 If the Join Timer is set to expire in less than t_override 2674 seconds, leave it unchanged. 2676 RPF'(*,G) changes not due to an Assert 2677 An event occurred that caused the next hop towards the RP for 2678 G to change. This may be caused by a change in the MRIB 2679 routing database or the group-to-RP mapping. Note that this 2680 transition does not occur if an Assert is active and the 2681 upstream interface does not change. 2683 The upstream (*,G) state machine remains in Joined state. Send 2684 Join(*,G) to the new upstream neighbor, which is the new value 2685 of RPF'(*,G). Send Prune(*,G) to the old upstream neighbor, 2686 which is the old value of RPF'(*,G). Use the new value of 2687 RP(G) in the Prune(*,G) message or all zeros if RP(G) becomes 2688 unknown (old value of RP(G) may be used instead to improve 2689 behavior in routers implementing older versions of this spec). 2690 Set the Join Timer (JT) to expire after t_periodic seconds. 2692 RPF'(*,G) GenID changes 2693 The Generation ID of the router that is RPF'(*,G) changes. 2694 This normally means that this neighbor has lost state, and so 2695 the state must be refreshed. 2697 The upstream (*,G) state machine remains in Joined state. If 2698 the Join Timer is set to expire in more than t_override 2699 seconds, reset it so that it expires after t_override seconds. 2701 4.5.5. Sending (S,G) Join/Prune Messages 2703 The per-interface state machines for (S,G) hold join state from 2704 downstream PIM routers. This state then determines whether a router 2705 needs to propagate a Join(S,G) upstream towards the source. 2707 If a router wishes to propagate a Join(S,G) upstream, it must also 2708 watch for messages on its upstream interface from other routers on 2709 that subnet, and these may modify its behavior. If it sees a 2710 Join(S,G) to the correct upstream neighbor, it should suppress its 2711 own Join(S,G). If it sees a Prune(S,G), Prune(S,G,rpt), or 2712 Prune(*,G) to the correct upstream neighbor towards S, it should be 2713 prepared to override that prune by scheduling a Join(S,G) to be sent 2714 almost immediately. Finally, if it sees the Generation ID of its 2715 upstream neighbor change, it knows that the upstream neighbor has 2716 lost state, and it should refresh the state by scheduling a Join(S,G) 2717 to be sent almost immediately. 2719 If an (S,G) Assert occurs on the upstream interface, and this changes 2720 this router's idea of the upstream neighbor, it should be prepared to 2721 ensure that the Assert winner is aware of downstream routers by 2722 scheduling a Join(S,G) to be sent almost immediately. 2724 In addition, if MRIB changes cause the next hop towards the source to 2725 change, and either the upstream interface changes or there is no 2726 Assert winner on the upstream interface, the router should send a 2727 prune to the old next hop and a join to the new next hop. 2729 The upstream (S,G) state machine only contains two states: 2731 Not Joined 2732 The downstream state machines and local membership information do 2733 not indicate that the router needs to join the shortest-path tree 2734 for this (S,G). 2736 Joined 2737 The downstream state machines and local membership information 2738 indicate that the router should join the shortest-path tree for 2739 this (S,G). 2741 In addition, one timer JT(S,G) is kept that is used to trigger the 2742 sending of a Join(S,G) to the upstream next hop towards S, RPF'(S,G). 2744 Figure 6: Upstream (S,G) state machine in tabular form 2746 +-------------------+--------------------------------------------------+ 2747 | | Event | 2748 | Prev State +-------------------------+------------------------+ 2749 | | JoinDesired(S,G) | JoinDesired(S,G) | 2750 | | ->True | ->False | 2751 +-------------------+-------------------------+------------------------+ 2752 | NotJoined (NJ) | -> J state | - | 2753 | | Send Join(S,G); | | 2754 | | Set Join Timer to | | 2755 | | t_periodic | | 2756 +-------------------+-------------------------+------------------------+ 2757 | Joined (J) | - | -> NJ state | 2758 | | | Send Prune(S,G); | 2759 | | | Set SPTbit(S,G) to | 2760 | | | FALSE; Cancel Join | 2761 | | | Timer | 2762 +-------------------+-------------------------+------------------------+ 2764 In addition, we have the following transitions, which occur within 2765 the Joined state: 2767 +----------------------------------------------------------------------+ 2768 | In Joined (J) State | 2769 +-----------------+-----------------+-----------------+----------------+ 2770 | Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune | 2771 | | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to | 2772 | | | | RPF'(S,G) | 2773 +-----------------+-----------------+-----------------+----------------+ 2774 | Send | Increase Join | Decrease Join | Decrease Join | 2775 | Join(S,G); Set | Timer to | Timer to | Timer to | 2776 | Join Timer to | t_joinsuppress | t_override | t_override | 2777 | t_periodic | | | | 2778 +-----------------+-----------------+-----------------+----------------+ 2779 +----------------------------------------------------------------------+ 2780 | In Joined (J) State | 2781 +-----------------+-----------------+----------------+-----------------+ 2782 | See Prune(*,G) | RPF'(S,G) | RPF'(S,G) | RPF'(S,G) | 2783 | to RPF'(S,G) | changes not | GenID changes | changes due to | 2784 | | due to an | | an Assert | 2785 | | Assert | | | 2786 +-----------------+-----------------+----------------+-----------------+ 2787 | Decrease Join | Send Join(S,G) | Decrease Join | Decrease Join | 2788 | Timer to | to new next | Timer to | Timer to | 2789 | t_override | hop; Send | t_override | t_override | 2790 | | Prune(S,G) to | | | 2791 | | old next hop; | | | 2792 | | Set Join Timer | | | 2793 | | to t_periodic | | | 2794 +-----------------+-----------------+----------------+-----------------+ 2796 This state machine uses the following macro: 2798 bool JoinDesired(S,G) { 2799 return( immediate_olist(S,G) != NULL 2800 OR ( KeepaliveTimer(S,G) is running 2801 AND inherited_olist(S,G) != NULL ) ) 2802 } 2804 JoinDesired(S,G) is true when the router has forwarding state that 2805 would cause it to forward traffic for G using source tree state. The 2806 source tree state can be as a result of either active source-specific 2807 join state, or the (S,G) Keepalive Timer and active non-source- 2808 specific state. Note that although JoinDesired is true, the router's 2809 sending of a Join(S,G) message may be suppressed by another router 2810 sending a Join(S,G) onto the upstream interface. 2812 Transitions from NotJoined State 2814 When the upstream (S,G) state machine is in NotJoined state, the 2815 following event may trigger a state transition: 2817 JoinDesired(S,G) becomes True 2818 The macro JoinDesired(S,G) becomes True, e.g., because the 2819 downstream state for (S,G) has changed so that at least one 2820 interface is in inherited_olist(S,G). 2822 The upstream (S,G) state machine transitions to Joined state. 2823 Send Join(S,G) to the appropriate upstream neighbor, which is 2824 RPF'(S,G). Set the Join Timer (JT) to expire after t_periodic 2825 seconds. 2827 Transitions from Joined State 2829 When the upstream (S,G) state machine is in Joined state, the 2830 following events may trigger state transitions: 2832 JoinDesired(S,G) becomes False 2833 The macro JoinDesired(S,G) becomes False, e.g., because the 2834 downstream state for (S,G) has changed so no interface is in 2835 inherited_olist(S,G). 2837 The upstream (S,G) state machine transitions to NotJoined 2838 state. Send Prune(S,G) to the appropriate upstream neighbor, 2839 which is RPF'(S,G). Cancel the Join Timer (JT), and set 2840 SPTbit(S,G) to FALSE. 2842 Join Timer Expires 2843 The Join Timer (JT) expires, indicating time to send a 2844 Join(S,G) 2846 Send Join(S,G) to the appropriate upstream neighbor, which is 2847 RPF'(S,G). Restart the Join Timer (JT) to expire after 2848 t_periodic seconds. 2850 See Join(S,G) to RPF'(S,G) 2851 This event is only relevant if RPF_interface(S) is a shared 2852 medium. This router sees another router on RPF_interface(S) 2853 send a Join(S,G) to RPF'(S,G). This causes this router to 2854 suppress its own Join. 2856 The upstream (S,G) state machine remains in Joined state. 2858 Let t_joinsuppress be the minimum of t_suppressed and the 2859 HoldTime from the Join/Prune message triggering this event. 2861 If the Join Timer is set to expire in less than t_joinsuppress 2862 seconds, reset it so that it expires after t_joinsuppress 2863 seconds. If the Join Timer is set to expire in more than 2864 t_joinsuppress seconds, leave it unchanged. 2866 See Prune(S,G) to RPF'(S,G) 2867 This event is only relevant if RPF_interface(S) is a shared 2868 medium. This router sees another router on RPF_interface(S) 2869 send a Prune(S,G) to RPF'(S,G). As this router is in Joined 2870 state, it must override the Prune after a short random 2871 interval. 2873 The upstream (S,G) state machine remains in Joined state. If 2874 the Join Timer is set to expire in more than t_override 2875 seconds, reset it so that it expires after t_override seconds. 2877 See Prune(S,G,rpt) to RPF'(S,G) 2878 This event is only relevant if RPF_interface(S) is a shared 2879 medium. This router sees another router on RPF_interface(S) 2880 send a Prune(S,G,rpt) to RPF'(S,G). If the upstream router is 2881 an RFC-2362-compliant PIM router, then the Prune(S,G,rpt) will 2882 cause it to stop forwarding. For backwards compatibility, 2883 this router should override the prune so that forwarding 2884 continues. 2886 The upstream (S,G) state machine remains in Joined state. If 2887 the Join Timer is set to expire in more than t_override 2888 seconds, reset it so that it expires after t_override seconds. 2890 See Prune(*,G) to RPF'(S,G) 2891 This event is only relevant if RPF_interface(S) is a shared 2892 medium. This router sees another router on RPF_interface(S) 2893 send a Prune(*,G) to RPF'(S,G). If the upstream router is an 2894 RFC-2362-compliant PIM router, then the Prune(*,G) will cause 2895 it to stop forwarding. For backwards compatibility, this 2896 router should override the prune so that forwarding continues. 2898 The upstream (S,G) state machine remains in Joined state. If 2899 the Join Timer is set to expire in more than t_override 2900 seconds, reset it so that it expires after t_override seconds. 2902 RPF'(S,G) changes due to an Assert 2903 The current next hop towards S changes due to an Assert(S,G) 2904 on the RPF_interface(S). 2906 The upstream (S,G) state machine remains in Joined state. If 2907 the Join Timer is set to expire in more than t_override 2908 seconds, reset it so that it expires after t_override seconds. 2909 If the Join Timer is set to expire in less than t_override 2910 seconds, leave it unchanged. 2912 RPF'(S,G) changes not due to an Assert 2913 An event occurred that caused the next hop towards S to 2914 change. Note that this transition does not occur if an Assert 2915 is active and the upstream interface does not change. 2917 The upstream (S,G) state machine remains in Joined state. Send 2918 Join(S,G) to the new upstream neighbor, which is the new value 2919 of RPF'(S,G). Send Prune(S,G) to the old upstream neighbor, 2920 which is the old value of RPF'(S,G). Set the Join Timer (JT) 2921 to expire after t_periodic seconds. 2923 RPF'(S,G) GenID changes 2924 The Generation ID of the router that is RPF'(S,G) changes. 2925 This normally means that this neighbor has lost state, and so 2926 the state must be refreshed. 2928 The upstream (S,G) state machine remains in Joined state. If 2929 the Join Timer is set to expire in more than t_override 2930 seconds, reset it so that it expires after t_override seconds. 2932 4.5.6. (S,G,rpt) Periodic Messages 2934 (S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP 2935 tree with the RPT bit set, either to modify the results of (*,G) 2936 Joins, or to override the behavior of other upstream LAN peers. The 2937 next section describes the rules for sending triggered messages. 2938 This section describes the rules for including a Prune(S,G,rpt) 2939 message with a Join(*,G). 2941 When a router is going to send a Join(*,G), it should use the 2942 following pseudocode, for each (S,G) for which it has state, to 2943 decide whether to include a Prune(S,G,rpt) in the compound Join/Prune 2944 message: 2946 if( SPTbit(S,G) == TRUE ) { 2947 # Note: If receiving (S,G) on the SPT, we only prune off the 2948 # shared tree if the RPF neighbors differ. 2949 if( RPF'(*,G) != RPF'(S,G) ) { 2950 add Prune(S,G,rpt) to compound message 2951 } 2952 } else if ( inherited_olist(S,G,rpt) == NULL ) { 2953 # Note: all (*,G) olist interfaces received RPT prunes for (S,G). 2954 add Prune(S,G,rpt) to compound message 2955 } else if ( RPF'(*,G) != RPF'(S,G,rpt) { 2956 # Note: we joined the shared tree, but there was an (S,G) assert 2957 # and the source tree RPF neighbor is different. 2958 add Prune(S,G,rpt) to compound message 2959 } 2961 Note that Join(S,G,rpt) is normally sent not as a periodic message, 2962 but only as a triggered message. 2964 4.5.7. State Machine for (S,G,rpt) Triggered Messages 2966 The state machine for (S,G,rpt) triggered messages is required per- 2967 (S,G) when there is (*,G) join state at a router, and the router or 2968 any of its upstream LAN peers wishes to prune S off the RP tree. 2970 There are three states in the state machine. One of the states is 2971 when there is no (*,G) join state at this router. If there is (*,G) 2972 join state at the router, then the state machine must be at one of 2973 the other two states. The three states are: 2975 Pruned(S,G,rpt) 2976 (*,G) Joined, but (S,G,rpt) pruned 2978 NotPruned(S,G,rpt) 2979 (*,G) Joined, and (S,G,rpt) not pruned 2981 RPTNotJoined(G) 2982 (*,G) has not been joined. 2984 In addition, there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which 2985 is used to delay triggered Join(S,G,rpt) messages to prevent 2986 implosions of triggered messages. 2988 Figure 7: Upstream (S,G,rpt) state machine for triggered messages 2989 in tabular form 2991 +------------++--------------------------------------------------------+ 2992 | || Event | 2993 | ++--------------+--------------+-------------+------------+ 2994 |Prev State || PruneDesired | PruneDesired | RPTJoin | inherited_ | 2995 | || (S,G,rpt) | (S,G,rpt) | Desired(G) | olist | 2996 | || ->True | ->False | ->False | (S,G,rpt) | 2997 | || | | | ->non-NULL | 2998 +------------++--------------+--------------+-------------+------------+ 2999 |RPTNotJoined|| -> P state | - | - | -> NP state| 3000 |(G) (NJ) || | | | | 3001 +------------++--------------+--------------+-------------+------------+ 3002 |Pruned || - | -> NP state | -> NJ state | - | 3003 |(S,G,rpt) || | Send Join | | | 3004 |(P) || | (S,G,rpt) | | | 3005 +------------++--------------+--------------+-------------+------------+ 3006 |NotPruned || -> P state | - | -> NJ state | - | 3007 |(S,G,rpt) || Send Prune | | Cancel OT | | 3008 |(NP) || (S,G,rpt); | | | | 3009 | || Cancel OT | | | | 3010 +------------++--------------+--------------+-------------+------------+ 3011 Additionally, we have the following transitions within the 3012 NotPruned(S,G,rpt) state, which are all used for prune override 3013 behavior. 3015 +----------------------------------------------------------------------+ 3016 | In NotPruned(S,G,rpt) State | 3017 +----------+--------------+--------------+--------------+--------------+ 3018 |Override | See Prune | See Join | See Prune | RPF' | 3019 |Timer | (S,G,rpt) to | (S,G,rpt) to | (S,G) to | (S,G,rpt) -> | 3020 |expires | RPF' | RPF' | RPF' | RPF' (*,G) | 3021 | | (S,G,rpt) | (S,G,rpt) | (S,G,rpt) | | 3022 +----------+--------------+--------------+--------------+--------------+ 3023 |Send Join | OT = min(OT, | Cancel OT | OT = min(OT, | OT = min(OT, | 3024 |(S,G,rpt);| t_override) | | t_override) | t_override) | 3025 |Leave OT | | | | | 3026 |unset | | | | | 3027 +----------+--------------+--------------+--------------+--------------+ 3029 Note that the min function in the above state machine considers a 3030 non-running timer to have an infinite value (e.g., min(not-running, 3031 t_override) = t_override). 3033 This state machine uses the following macros: 3035 bool RPTJoinDesired(G) { 3036 return (JoinDesired(*,G)) 3037 } 3039 RPTJoinDesired(G) is true when the router has forwarding state that 3040 would cause it to forward traffic for G using (*,G) shared tree 3041 state. 3043 bool PruneDesired(S,G,rpt) { 3044 return ( RPTJoinDesired(G) AND 3045 ( inherited_olist(S,G,rpt) == NULL 3046 OR (SPTbit(S,G)==TRUE 3047 AND (RPF'(*,G) != RPF'(S,G)) ))) 3048 } 3050 PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true. 3051 If RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true 3052 either if there are no outgoing interfaces that S would be forwarded 3053 on, or if the router has active (S,G) forwarding state but RPF'(*,G) 3054 != RPF'(S,G). 3056 The state machine contains the following transition events: 3058 See Join(S,G,rpt) to RPF'(S,G,rpt) 3059 This event is only relevant in the "Not Pruned" state. 3061 The router sees a Join(S,G,rpt) from someone else to 3062 RPF'(S,G,rpt), which is the correct upstream neighbor. If we're 3063 in "NotPruned" state and the (S,G,rpt) Override Timer is running, 3064 then this is because we have been triggered to send our own 3065 Join(S,G,rpt) to RPF'(S,G,rpt). Someone else beat us to it, so 3066 there's no need to send our own Join. 3068 The action is to cancel the Override Timer. 3070 See Prune(S,G,rpt) to RPF'(S,G,rpt) 3071 This event is only relevant in the "NotPruned" state. 3073 The router sees a Prune(S,G,rpt) from someone else to 3074 RPF'(S,G,rpt), which is the correct upstream neighbor. If we're 3075 in the "NotPruned" state, then we want to continue to receive 3076 traffic from S destined for G, and that traffic is being supplied 3077 by RPF'(S,G,rpt). Thus, we need to override the Prune. 3079 The action is to set the (S,G,rpt) Override Timer to the 3080 randomized prune-override interval, t_override. However, if the 3081 Override Timer is already running, we only set the timer if doing 3082 so would set it to a lower value. At the end of this interval, if 3083 no one else has sent a Join, then we will do so. 3085 See Prune(S,G) to RPF'(S,G,rpt) 3086 This event is only relevant in the "NotPruned" state. 3088 This transition and action are the same as the above transition 3089 and action, except that the Prune does not have the RPT bit set. 3090 This transition is necessary to be compatible with routers 3091 implemented from RFC2362 that don't maintain separate (S,G) and 3092 (S,G,rpt) state. 3094 The (S,G,rpt) prune Override Timer expires 3095 This event is only relevant in the "NotPruned" state. 3097 When the Override Timer expires, we must send a Join(S,G,rpt) to 3098 RPF'(S,G,rpt) to override the Prune message that caused the timer 3099 to be running. We only send this if RPF'(S,G,rpt) equals 3100 RPF'(*,G); if this were not the case, then the Join might be sent 3101 to a router that does not have (*,G) Join state, and so the 3102 behavior would not be well defined. If RPF'(S,G,rpt) is not the 3103 same as RPF'(*,G), then it may stop forwarding S. However, if 3104 this happens, then the router will send an AssertCancel(S,G), 3105 which would then cause RPF'(S,G,rpt) to become equal to RPF'(*,G) 3106 (see below). 3108 RPF'(S,G,rpt) changes to become equal to RPF'(*,G) 3109 This event is only relevant in the "NotPruned" state. 3111 RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G) 3112 Assert has happened, which means that traffic from S is arriving 3113 on the SPT, and so Prune(S,G,rpt) will have been sent to 3114 RPF'(*,G). When RPF'(S,G,rpt) changes to become equal to 3115 RPF'(*,G), we need to trigger a Join(S,G,rpt) to RPF'(*,G) to 3116 cause that router to start forwarding S again. 3118 The action is to set the (S,G,rpt) Override Timer to the 3119 randomized prune-override interval t_override. However, if the 3120 timer is already running, we only set the timer if doing so would 3121 set it to a lower value. At the end of this interval, if no one 3122 else has sent a Join, then we will do so. 3124 PruneDesired(S,G,rpt)->TRUE 3125 See macro above. This event is relevant in the "NotPruned" and 3126 "RPTNotJoined(G)" states. 3128 The router wishes to receive traffic for G, but does not wish to 3129 receive traffic from S destined for G. This causes the router to 3130 transition into the Pruned state. 3132 If the router was previously in NotPruned state, then the action 3133 is to send a Prune(S,G,rpt) to RPF'(S,G,rpt), and to cancel the 3134 Override Timer. If the router was previously in RPTNotJoined(G) 3135 state, then there is no need to trigger an action in this state 3136 machine because sending a Prune(S,G,rpt) is handled by the rules 3137 for sending the Join(*,G). 3139 PruneDesired(S,G,rpt)->FALSE 3140 See macro above. This transition is only relevant in the "Pruned" 3141 state. 3143 If the router is in the Pruned(S,G,rpt) state, and 3144 PruneDesired(S,G,rpt) changes to FALSE, this could be because the 3145 router no longer has RPTJoinDesired(G) true, or it now wishes to 3146 receive traffic from S again. If it is the former, then this 3147 transition should not happen, but instead the 3148 "RPTJoinDesired(G)->FALSE" transition should happen. Thus, this 3149 transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE 3150 AND RPTJoinDesired(G)==TRUE". 3152 The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt). 3154 RPTJoinDesired(G)->FALSE 3155 This event is relevant in the "Pruned" and "NotPruned" states. 3157 The router no longer wishes to receive any traffic destined for G 3158 on the RP Tree. This causes a transition to the RPTNotJoined(G) 3159 state, and the Override Timer is canceled if it was running. Any 3160 further actions are handled by the appropriate upstream state 3161 machine for (*,G). 3163 inherited_olist(S,G,rpt) becomes non-NULL 3164 This transition is only relevant in the RPTNotJoined(G) state. 3166 The router has joined the RP tree (handled by the (*,G) upstream 3167 state machine as appropriate) and wants to receive traffic from S. 3168 This does not trigger any events in this state machine, but 3169 causes a transition to the NotPruned(S,G,rpt) state. 3171 4.6. PIM Assert Messages 3173 Where multiple PIM routers peer over a shared LAN, it is possible for 3174 more than one upstream router to have valid forwarding state for a 3175 packet, which can lead to packet duplication (see Section 3.6). PIM 3176 does not attempt to prevent this from occurring. Instead, it detects 3177 when this has happened and elects a single forwarder amongst the 3178 upstream routers to prevent further duplication. This election is 3179 performed using PIM Assert messages. Assert messages are also 3180 received by downstream routers on the LAN, and these cause subsequent 3181 Join/Prune messages to be sent to the upstream router that won the 3182 Assert. 3184 In general, a PIM Assert message should only be accepted for 3185 processing if it comes from a known PIM neighbor. A PIM router hears 3186 about PIM neighbors through PIM Hello messages. If a router receives 3187 an Assert message from a particular IP source address and it has not 3188 seen a PIM Hello message from that source address, then the Assert 3189 message SHOULD be discarded without further processing. In addition, 3190 if the Hello message from a neighbor was authenticated using the 3191 IPsec Authentication Header (AH) (see Section 6.3), then all Assert 3192 messages from that neighbor MUST also be authenticated using IPsec 3193 AH. 3195 We note that some older PIM implementations incorrectly fail to send 3196 Hello messages on point-to-point interfaces, so we also RECOMMEND 3197 that a configuration option be provided to allow interoperation with 3198 such older routers, but that this configuration option SHOULD NOT be 3199 enabled by default. 3201 4.6.1. (S,G) Assert Message State Machine 3203 The (S,G) Assert state machine for interface I is shown in Figure 8. 3204 There are three states: 3206 NoInfo (NI) 3207 This router has no (S,G) assert state on interface I. 3209 I am Assert Winner (W) 3210 This router has won an (S,G) assert on interface I. It is now 3211 responsible for forwarding traffic from S destined for G out of 3212 interface I. Irrespective of whether it is the DR for I, while a 3213 router is the assert winner, it is also responsible for forwarding 3214 traffic onto I on behalf of local hosts on I that have made 3215 membership requests that specifically refer to S (and G). 3217 I am Assert Loser (L) 3218 This router has lost an (S,G) assert on interface I. It must not 3219 forward packets from S destined for G onto interface I. If it is 3220 the DR on I, it is no longer responsible for forwarding traffic 3221 onto I to satisfy local hosts with membership requests that 3222 specifically refer to S and G. 3224 In addition, there is also an Assert Timer (AT) that is used to time 3225 out asserts on the assert losers and to resend asserts on the assert 3226 winner. 3228 Figure 8: Per-interface (S,G) Assert State machine in tabular form 3230 +----------------------------------------------------------------------+ 3231 | In NoInfo (NI) State | 3232 +---------------+-------------------+------------------+---------------+ 3233 | Receive | Receive Assert | Data arrives | Receive | 3234 | Inferior | with RPTbit | from S to G on | Acceptable | 3235 | Assert with | set and | I and | Assert with | 3236 | RPTbit clear | CouldAssert | CouldAssert | RPTbit clear | 3237 | | (S,G,I) | (S,G,I) | and AssTrDes | 3238 | | | | (S,G,I) | 3239 +---------------+-------------------+------------------+---------------+ 3240 | -> W state | -> W state | -> W state | -> L state | 3241 | [Actions A1] | [Actions A1] | [Actions A1] | [Actions A6] | 3242 +---------------+-------------------+------------------+---------------+ 3243 +----------------------------------------------------------------------+ 3244 | In I Am Assert Winner (W) State | 3245 +----------------+------------------+-----------------+----------------+ 3246 | Assert Timer | Receive | Receive | CouldAssert | 3247 | Expires | Inferior | Preferred | (S,G,I) -> | 3248 | | Assert | Assert | FALSE | 3249 +----------------+------------------+-----------------+----------------+ 3250 | -> W state | -> W state | -> L state | -> NI state | 3251 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3252 +----------------+------------------+-----------------+----------------+ 3254 +---------------------------------------------------------------------+ 3255 | In I Am Assert Loser (L) State | 3256 +-------------+-------------+-------------+-------------+-------------+ 3257 |Receive |Receive |Receive |Assert Timer |Current | 3258 |Preferred |Acceptable |Inferior |Expires |Winner's | 3259 |Assert |Assert with |Assert or | |GenID | 3260 | |RPTbit clear |Assert | |Changes or | 3261 | |from Current |Cancel from | |NLT Expires | 3262 | |Winner |Current | | | 3263 | | |Winner | | | 3264 +-------------+-------------+-------------+-------------+-------------+ 3265 |-> L state |-> L state |-> NI state |-> NI state |-> NI state | 3266 |[Actions A2] |[Actions A2] |[Actions A5] |[Actions A5] |[Actions A5] | 3267 +-------------+-------------+-------------+-------------+-------------+ 3269 +----------------------------------------------------------------------+ 3270 | In I Am Assert Loser (L) State | 3271 +----------------+-----------------+------------------+----------------+ 3272 | AssTrDes | my_metric -> | RPF_interface | Receive | 3273 | (S,G,I) -> | better than | (S) stops | Join(S,G) on | 3274 | FALSE | winner's | being I | interface I | 3275 | | metric | | | 3276 +----------------+-----------------+------------------+----------------+ 3277 | -> NI state | -> NI state | -> NI state | -> NI State | 3278 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 3279 +----------------+-----------------+------------------+----------------+ 3281 Note that for reasons of compactness, "AssTrDes(S,G,I)" is used in 3282 the state machine table to refer to AssertTrackingDesired(S,G,I). 3284 Terminology: 3286 A "preferred assert" is one with a better metric than the current 3287 winner. 3289 An "acceptable assert" is one that has a better metric than 3290 my_assert_metric(S,G,I). An assert is never considered acceptable 3291 if its metric is infinite. 3293 An "inferior assert" is one with a worse metric than 3294 my_assert_metric(S,G,I). An assert is never considered inferior 3295 if my_assert_metric(S,G,I) is infinite. 3297 The state machine uses the following macros: 3299 CouldAssert(S,G,I) = 3300 SPTbit(S,G)==TRUE 3301 AND (RPF_interface(S) != I) 3302 AND (I in ( ( joins(*,G) (-) prunes(S,G,rpt) ) 3303 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3304 (-) lost_assert(*,G) 3305 (+) joins(S,G) (+) pim_include(S,G) ) ) 3307 CouldAssert(S,G,I) is true for downstream interfaces that would be in 3308 the inherited_olist(S,G) if (S,G) assert information was not taken 3309 into account. 3311 AssertTrackingDesired(S,G,I) = 3312 (I in ( joins(*,G) (-) prunes(S,G,rpt) 3313 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3314 (-) lost_assert(*,G) 3315 (+) joins(S,G) ) ) 3316 OR (local_receiver_include(S,G,I) == TRUE 3317 AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me))) 3318 OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == TRUE)) 3319 OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == TRUE) 3320 AND (SPTbit(S,G) == FALSE)) 3322 AssertTrackingDesired(S,G,I) is true on any interface in which an 3323 (S,G) assert might affect our behavior. 3325 The first three lines of AssertTrackingDesired account for (*,G) join 3326 and local membership information received on I that might cause the 3327 router to be interested in asserts on I. 3329 The 4th line accounts for (S,G) join information received on I that 3330 might cause the router to be interested in asserts on I. 3332 The 5th and 6th lines account for (S,G) local membership information 3333 on I. Note that we can't use the pim_include(S,G) macro since it 3334 uses lost_assert(S,G,I) and would result in the router forgetting 3335 that it lost an assert if the only reason it was interested was local 3336 membership. The AssertWinner(S,G,I) check forces an assert winner to 3337 keep on being responsible for forwarding as long as local receivers 3338 are present. Removing this check would make the assert winner give 3339 up forwarding as soon as the information that originally caused it to 3340 forward went away, and the task of forwarding for local receivers 3341 would revert back to the DR. 3343 The last three lines account for the fact that a router must keep 3344 track of assert information on upstream interfaces in order to send 3345 joins and prunes to the proper neighbor. 3347 Transitions from NoInfo State 3349 When in NoInfo state, the following events may trigger transitions: 3351 Receive Inferior Assert with RPTbit cleared 3352 An assert is received for (S,G) with the RPT bit cleared that 3353 is inferior to our own assert metric. The RPT bit cleared 3354 indicates that the sender of the assert had (S,G) forwarding 3355 state on this interface. If the assert is inferior to our 3356 metric, then we must also have (S,G) forwarding state (i.e., 3357 CouldAssert(S,G,I)==TRUE) as (S,G) asserts beat (*,G) asserts, 3358 and so we should be the assert winner. We transition to the 3359 "I am Assert Winner" state and perform Actions A1 (below). 3361 Receive Assert with RPTbit set AND CouldAssert(S,G,I)==TRUE 3362 An assert is received for (S,G) on I with the RPT bit set 3363 (it's a (*,G) assert). CouldAssert(S,G,I) is TRUE only if we 3364 have (S,G) forwarding state on this interface, so we should be 3365 the assert winner. We transition to the "I am Assert Winner" 3366 state and perform Actions A1 (below). 3368 An (S,G) data packet arrives on interface I, AND 3369 CouldAssert(S,G,I)==TRUE 3370 An (S,G) data packet arrived on a downstream interface that is 3371 in our (S,G) outgoing interface list. We optimistically 3372 assume that we will be the assert winner for this (S,G), and 3373 so we transition to the "I am Assert Winner" state and perform 3374 Actions A1 (below), which will initiate the assert negotiation 3375 for (S,G). 3377 Receive Acceptable Assert with RPT bit clear AND 3378 AssertTrackingDesired(S,G,I)==TRUE 3379 We're interested in (S,G) Asserts, either because I is a 3380 downstream interface for which we have (S,G) or (*,G) 3381 forwarding state, or because I is the upstream interface for S 3382 and we have (S,G) forwarding state. The received assert has a 3383 better metric than our own, so we do not win the Assert. We 3384 transition to "I am Assert Loser" and perform Actions A6 3385 (below). 3387 Transitions from "I am Assert Winner" State 3389 When in "I am Assert Winner" state, the following events trigger 3390 transitions: 3392 Assert Timer Expires 3393 The (S,G) Assert Timer expires. As we're in the Winner state, 3394 we must still have (S,G) forwarding state that is actively 3395 being kept alive. We resend the (S,G) Assert and restart the 3396 Assert Timer (Actions A3 below). Note that the assert 3397 winner's Assert Timer is engineered to expire shortly before 3398 timers on assert losers; this prevents unnecessary thrashing 3399 of the forwarder and periodic flooding of duplicate packets. 3401 Receive Inferior Assert 3402 We receive an (S,G) assert or (*,G) assert mentioning S that 3403 has a worse metric than our own. Whoever sent the assert is 3404 in error, and so we resend an (S,G) Assert and restart the 3405 Assert Timer (Actions A3 below). 3407 Receive Preferred Assert 3408 We receive an (S,G) assert that has a better metric than our 3409 own. We transition to "I am Assert Loser" state and perform 3410 Actions A2 (below). Note that this may affect the value of 3411 JoinDesired(S,G) and PruneDesired(S,G,rpt), which could cause 3412 transitions in the upstream (S,G) or (S,G,rpt) state machines. 3414 CouldAssert(S,G,I) -> FALSE 3415 Our (S,G) forwarding state or RPF interface changed so as to 3416 make CouldAssert(S,G,I) become false. We can no longer 3417 perform the actions of the assert winner, and so we transition 3418 to NoInfo state and perform Actions A4 (below). This includes 3419 sending a "canceling assert" with an infinite metric. 3421 Transitions from "I am Assert Loser" State 3423 When in "I am Assert Loser" state, the following transitions can 3424 occur: 3426 Receive Preferred Assert 3427 We receive an assert that is better than that of the current 3428 assert winner. We stay in Loser state and perform Actions A2 3429 below. 3431 Receive Acceptable Assert with RPTbit clear from Current Winner 3432 We receive an assert from the current assert winner that is 3433 better than our own metric for this (S,G) (although the metric 3434 may be worse than the winner's previous metric). We stay in 3435 Loser state and perform Actions A2 below. 3437 Receive Inferior Assert or Assert Cancel from Current Winner 3438 We receive an assert from the current assert winner that is 3439 worse than our own metric for this group (typically, because 3440 the winner's metric became worse or because it is an assert 3441 cancel). We transition to NoInfo state, deleting the (S,G) 3442 assert information and allowing the normal PIM Join/Prune 3443 mechanisms to operate. Usually, we will eventually re-assert 3444 and win when data packets from S have started flowing again. 3446 Assert Timer Expires 3447 The (S,G) Assert Timer expires. We transition to NoInfo 3448 state, deleting the (S,G) assert information (Actions A5 3449 below). 3451 Current Winner's GenID Changes or NLT Expires 3452 The Neighbor Liveness Timer associated with the current winner 3453 expires or we receive a Hello message from the current winner 3454 reporting a different GenID from the one it previously 3455 reported. This indicates that the current winner's interface 3456 or router has gone down (and may have come back up), and so we 3457 must assume it no longer knows it was the winner. We 3458 transition to the NoInfo state, deleting this (S,G) assert 3459 information (Actions A5 below). 3461 AssertTrackingDesired(S,G,I)->FALSE 3462 AssertTrackingDesired(S,G,I) becomes FALSE. Our forwarding 3463 state has changed so that (S,G) Asserts on interface I are no 3464 longer of interest to us. We transition to the NoInfo state, 3465 deleting the (S,G) assert information. 3467 My metric becomes better than the assert winner's metric 3468 my_assert_metric(S,G,I) has changed so that now my assert 3469 metric for (S,G) is better than the metric we have stored for 3470 current assert winner. This might happen when the underlying 3471 routing metric changes, or when CouldAssert(S,G,I) becomes 3472 true; for example, when SPTbit(S,G) becomes true. We 3473 transition to NoInfo state, delete this (S,G) assert state 3474 (Actions A5 below), and allow the normal PIM Join/Prune 3475 mechanisms to operate. Usually, we will eventually re-assert 3476 and win when data packets from S have started flowing again. 3478 RPF_interface(S) stops being interface I 3479 Interface I used to be the RPF interface for S, and now it is 3480 not. We transition to NoInfo state, deleting this (S,G) 3481 assert state (Actions A5 below). 3483 Receive Join(S,G) on Interface I 3484 We receive a Join(S,G) that has the Upstream Neighbor Address 3485 field set to my primary IP address on interface I. The action 3486 is to transition to NoInfo state, delete this (S,G) assert 3487 state (Actions A5 below), and allow the normal PIM Join/Prune 3488 mechanisms to operate. If whoever sent the Join was in error, 3489 then the normal assert mechanism will eventually re-apply, and 3490 we will lose the assert again. However, whoever sent the 3491 assert may know that the previous assert winner has died, and 3492 so we may end up being the new forwarder. 3494 (S,G) Assert State machine Actions 3496 A1: Send Assert(S,G). 3497 Set Assert Timer to (Assert_Time - Assert_Override_Interval). 3498 Store self as AssertWinner(S,G,I). 3499 Store spt_assert_metric(S,I) as AssertWinnerMetric(S,G,I). 3501 A2: Store new assert winner as AssertWinner(S,G,I) and assert 3502 winner metric as AssertWinnerMetric(S,G,I). 3503 Set Assert Timer to Assert_Time. 3505 A3: Send Assert(S,G). 3506 Set Assert Timer to (Assert_Time - Assert_Override_Interval). 3508 A4: Send AssertCancel(S,G). 3509 Delete assert info (AssertWinner(S,G,I) and 3510 AssertWinnerMetric(S,G,I) will then return to their default 3511 values). 3513 A5: Delete assert info (AssertWinner(S,G,I) and 3514 AssertWinnerMetric(S,G,I) will then return to their default 3515 values). 3517 A6: Store new assert winner as AssertWinner(S,G,I) and assert 3518 winner metric as AssertWinnerMetric(S,G,I). 3519 Set Assert Timer to Assert_Time. 3520 If (I is RPF_interface(S)) AND (UpstreamJPState(S,G) == 3521 Joined) set SPTbit(S,G) to TRUE. 3523 Note that some of these actions may cause the value of 3524 JoinDesired(S,G), PruneDesired(S,G,rpt), or RPF'(S,G) to change, 3525 which could cause further transitions in other state machines. 3527 4.6.2. (*,G) Assert Message State Machine 3529 The (*,G) Assert state machine for interface I is shown in Figure 9. 3530 There are three states: 3532 NoInfo (NI) 3533 This router has no (*,G) assert state on interface I. 3535 I am Assert Winner (W) 3536 This router has won an (*,G) assert on interface I. It is now 3537 responsible for forwarding traffic destined for G onto interface I 3538 with the exception of traffic for which it has (S,G) "I am Assert 3539 Loser" state. Irrespective of whether it is the DR for I, it is 3540 also responsible for handling the membership requests for G from 3541 local hosts on I. 3543 I am Assert Loser (L) 3544 This router has lost an (*,G) assert on interface I. It must not 3545 forward packets for G onto interface I with the exception of 3546 traffic from sources for which it has (S,G) "I am Assert Winner" 3547 state. If it is the DR, it is no longer responsible for handling 3548 the membership requests for group G from local hosts on I. 3550 In addition, there is also an Assert Timer (AT) that is used to time 3551 out asserts on the assert losers and to resend asserts on the assert 3552 winner. 3554 When an Assert message is received with a source address other than 3555 zero, a PIM implementation must first match it against the possible 3556 events in the (S,G) assert state machine and process any transitions 3557 and actions, before considering whether the Assert message matches 3558 against the (*,G) assert state machine. 3560 It is important to note that NO TRANSITION CAN OCCUR in the (*,G) 3561 state machine as a result of receiving an Assert message unless the 3562 (S,G) assert state machine for the relevant S and G is in the 3563 "NoInfo" state after the (S,G) state machine has processed the 3564 message. Also, NO TRANSITION CAN OCCUR in the (*,G) state machine as 3565 a result of receiving an assert message if that message triggers any 3566 change of state in the (S,G) state machine. Obviously, when the 3567 source address in the received message is set to zero, an (S,G) state 3568 machine for the S and G does not exist and can be assumed to be in 3569 the "NoInfo" state. 3571 For example, if both the (S,G) and (*,G) assert state machines are in 3572 the NoInfo state when an Assert message arrives, and the message 3573 causes the (S,G) state machine to transition to either "W" or "L" 3574 state, then the assert will not be processed by the (*,G) assert 3575 state machine. 3577 Another example: if the (S,G) assert state machine is in "L" state 3578 when an assert message is received, and the assert metric in the 3579 message is worse than my_assert_metric(S,G,I), then the (S,G) assert 3580 state machine will transition to NoInfo state. In such a case, if 3581 the (*,G) assert state machine were in NoInfo state, it might appear 3582 that it would transition to "W" state, but this is not the case 3583 because this message already triggered a transition in the (S,G) 3584 assert state machine. 3586 Figure 9: Per-interface (*,G) Assert State machine in tabular form 3588 +----------------------------------------------------------------------+ 3589 | In NoInfo (NI) State | 3590 +-----------------------+-----------------------+----------------------+ 3591 | Receive Inferior | Data arrives for G | Receive Acceptable | 3592 | Assert with RPTbit | on I and | Assert with RPTbit | 3593 | set and | CouldAssert | set and AssTrDes | 3594 | CouldAssert(*,G,I) | (*,G,I) | (*,G,I) | 3595 +-----------------------+-----------------------+----------------------+ 3596 | -> W state | -> W state | -> L state | 3597 | [Actions A1] | [Actions A1] | [Actions A2] | 3598 +-----------------------+-----------------------+----------------------+ 3600 +---------------------------------------------------------------------+ 3601 | In I Am Assert Winner (W) State | 3602 +----------------+-----------------+-----------------+----------------+ 3603 | Assert Timer | Receive | Receive | CouldAssert | 3604 | Expires | Inferior | Preferred | (*,G,I) -> | 3605 | | Assert | Assert | FALSE | 3606 +----------------+-----------------+-----------------+----------------+ 3607 | -> W state | -> W state | -> L state | -> NI state | 3608 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3609 +----------------+-----------------+-----------------+----------------+ 3610 +---------------------------------------------------------------------+ 3611 | In I Am Assert Loser (L) State | 3612 +-------------+-------------+-------------+-------------+-------------+ 3613 |Receive |Receive |Receive |Assert Timer |Current | 3614 |Preferred |Acceptable |Inferior |Expires |Winner's | 3615 |Assert with |Assert from |Assert or | |GenID | 3616 |RPTbit set |Current |Assert | |Changes or | 3617 | |Winner with |Cancel from | |NLT Expires | 3618 | |RPTbit set |Current | | | 3619 | | |Winner | | | 3620 +-------------+-------------+-------------+-------------+-------------+ 3621 |-> L state |-> L state |-> NI state |-> NI state |-> NI state | 3622 |[Actions A2] |[Actions A2] |[Actions A5] |[Actions A5] |[Actions A5] | 3623 +-------------+-------------+-------------+-------------+-------------+ 3625 +----------------------------------------------------------------------+ 3626 | In I Am Assert Loser (L) State | 3627 +----------------+----------------+-----------------+------------------+ 3628 | AssTrDes | my_metric -> | RPF_interface | Receive | 3629 | (*,G,I) -> | better than | (RP(G)) stops | Join(*,G) on | 3630 | FALSE | Winner's | being I | Interface I | 3631 | | metric | | | 3632 +----------------+----------------+-----------------+------------------+ 3633 | -> NI state | -> NI state | -> NI state | -> NI State | 3634 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 3635 +----------------+----------------+-----------------+------------------+ 3637 The state machine uses the following macros: 3639 CouldAssert(*,G,I) = 3640 ( I in ( joins(*,G) (+) pim_include(*,G)) ) 3641 AND (RPF_interface(RP(G)) != I) 3643 CouldAssert(*,G,I) is true on downstream interfaces for which we have 3644 (*,G) join state, or local members that requested any traffic 3645 destined for G. 3647 AssertTrackingDesired(*,G,I) = 3648 CouldAssert(*,G,I) 3649 OR (local_receiver_include(*,G,I)==TRUE 3650 AND (I_am_DR(I) OR AssertWinner(*,G,I) == me)) 3651 OR (RPF_interface(RP(G)) == I AND RPTJoinDesired(G)) 3653 AssertTrackingDesired(*,G,I) is true on any interface on which an 3654 (*,G) assert might affect our behavior. 3656 Note that for reasons of compactness, "AssTrDes(*,G,I)" is used in 3657 the state machine table to refer to AssertTrackingDesired(*,G,I). 3659 Terminology: 3661 A "preferred assert" is one with a better metric than the current 3662 winner. 3664 An "acceptable assert" is one that has a better metric than 3665 my_assert_metric(*,G,I). An assert is never considered acceptable 3666 if its metric is infinite. 3668 An "inferior assert" is one with a worse metric than 3669 my_assert_metric(*,G,I). An assert is never considered inferior 3670 if my_assert_metric(*,G,I) is infinite. 3672 Transitions from NoInfo State 3674 When in NoInfo state, the following events trigger transitions, but 3675 only if the (S,G) assert state machine is in NoInfo state before and 3676 after consideration of the received message: 3678 Receive Inferior Assert with RPTbit set AND 3679 CouldAssert(*,G,I)==TRUE 3680 An Inferior (*,G) assert is received for G on Interface I. If 3681 CouldAssert(*,G,I) is TRUE, then I is our downstream 3682 interface, and we have (*,G) forwarding state on this 3683 interface, so we should be the assert winner. We transition 3684 to the "I am Assert Winner" state and perform Actions A1 3685 (below). 3687 A data packet destined for G arrives on interface I, AND 3688 CouldAssert(*,G,I)==TRUE 3689 A data packet destined for G arrived on a downstream interface 3690 that is in our (*,G) outgoing interface list. We therefore 3691 believe we should be the forwarder for this (*,G), and so we 3692 transition to the "I am Assert Winner" state and perform 3693 Actions A1 (below). 3695 Receive Acceptable Assert with RPT bit set AND 3696 AssertTrackingDesired(*,G,I)==TRUE 3697 We're interested in (*,G) Asserts, either because I is a 3698 downstream interface for which we have (*,G) forwarding state, 3699 or because I is the upstream interface for RP(G) and we have 3700 (*,G) forwarding state. We get a (*,G) Assert that has a 3701 better metric than our own, so we do not win the Assert. We 3702 transition to "I am Assert Loser" and perform Actions A2 3703 (below). 3705 Transitions from "I am Assert Winner" State 3706 When in "I am Assert Winner" state, the following events trigger 3707 transitions, but only if the (S,G) assert state machine is in NoInfo 3708 state before and after consideration of the received message: 3710 Receive Inferior Assert 3711 We receive a (*,G) assert that has a worse metric than our 3712 own. Whoever sent the assert has lost, and so we resend a 3713 (*,G) Assert and restart the Assert Timer (Actions A3 below). 3715 Receive Preferred Assert 3716 We receive a (*,G) assert that has a better metric than our 3717 own. We transition to "I am Assert Loser" state and perform 3718 Actions A2 (below). 3720 When in "I am Assert Winner" state, the following events trigger 3721 transitions: 3723 Assert Timer Expires 3724 The (*,G) Assert Timer expires. As we're in the Winner state, 3725 then we must still have (*,G) forwarding state that is 3726 actively being kept alive. To prevent unnecessary thrashing 3727 of the forwarder and periodic flooding of duplicate packets, 3728 we resend the (*,G) Assert and restart the Assert Timer 3729 (Actions A3 below). 3731 CouldAssert(*,G,I) -> FALSE 3732 Our (*,G) forwarding state or RPF interface changed so as to 3733 make CouldAssert(*,G,I) become false. We can no longer 3734 perform the actions of the assert winner, and so we transition 3735 to NoInfo state and perform Actions A4 (below). 3737 Transitions from "I am Assert Loser" State 3739 When in "I am Assert Loser" state, the following events trigger 3740 transitions, but only if the (S,G) assert state machine is in NoInfo 3741 state before and after consideration of the received message: 3743 Receive Preferred Assert with RPTbit set 3744 We receive a (*,G) assert that is better than that of the 3745 current assert winner. We stay in Loser state and perform 3746 Actions A2 below. 3748 Receive Acceptable Assert from Current Winner with RPTbit set 3749 We receive a (*,G) assert from the current assert winner that 3750 is better than our own metric for this group (although the 3751 metric may be worse than the winner's previous metric). We 3752 stay in Loser state and perform Actions A2 below. 3754 Receive Inferior Assert or Assert Cancel from Current Winner 3755 We receive an assert from the current assert winner that is 3756 worse than our own metric for this group (typically because 3757 the winner's metric became worse or is now an assert cancel). 3758 We transition to NoInfo state, delete this (*,G) assert state 3759 (Actions A5), and allow the normal PIM Join/Prune mechanisms 3760 to operate. Usually, we will eventually re-assert and win 3761 when data packets for G have started flowing again. 3763 When in "I am Assert Loser" state, the following events trigger 3764 transitions: 3766 Assert Timer Expires 3767 The (*,G) Assert Timer expires. We transition to NoInfo state 3768 and delete this (*,G) assert info (Actions A5). 3770 Current Winner's GenID Changes or NLT Expires 3771 The Neighbor Liveness Timer associated with the current winner 3772 expires or we receive a Hello message from the current winner 3773 reporting a different GenID from the one it previously 3774 reported. This indicates that the current winner's interface 3775 or router has gone down (and may have come back up), and so we 3776 must assume it no longer knows it was the winner. We 3777 transition to the NoInfo state, deleting the (*,G) assert 3778 information (Actions A5). 3780 AssertTrackingDesired(*,G,I)->FALSE 3781 AssertTrackingDesired(*,G,I) becomes FALSE. Our forwarding 3782 state has changed so that (*,G) Asserts on interface I are no 3783 longer of interest to us. We transition to NoInfo state and 3784 delete this (*,G) assert info (Actions A5). 3786 My metric becomes better than the assert winner's metric 3787 My routing metric, rpt_assert_metric(G,I), has changed so that 3788 now my assert metric for (*,G) is better than the metric we 3789 have stored for current assert winner. We transition to 3790 NoInfo state, delete this (*,G) assert state (Actions A5), and 3791 allow the normal PIM Join/Prune mechanisms to operate. 3792 Usually, we will eventually re-assert and win when data 3793 packets for G have started flowing again. 3795 RPF_interface(RP(G)) stops being interface I 3796 Interface I used to be the RPF interface for RP(G), and now it 3797 is not. We transition to NoInfo state and delete this (*,G) 3798 assert state (Actions A5). 3800 Receive Join(*,G) on interface I 3801 We receive a Join(*,G) that has the Upstream Neighbor Address 3802 field set to my primary IP address on interface I. The action 3803 is to transition to NoInfo state, delete this (*,G) assert 3804 state (Actions A5), and allow the normal PIM Join/Prune 3805 mechanisms to operate. If whoever sent the Join was in error, 3806 then the normal assert mechanism will eventually re-apply, and 3807 we will lose the assert again. However, whoever sent the 3808 assert may know that the previous assert winner has died, so 3809 we may end up being the new forwarder. 3811 (*,G) Assert State machine Actions 3813 A1: Send Assert(*,G). 3814 Set Assert Timer to (Assert_Time - Assert_Override_Interval). 3815 Store self as AssertWinner(*,G,I). 3816 Store rpt_assert_metric(G,I) as AssertWinnerMetric(*,G,I). 3818 A2: Store new assert winner as AssertWinner(*,G,I) and assert 3819 winner metric as AssertWinnerMetric(*,G,I). 3820 Set Assert Timer to Assert_Time. 3822 A3: Send Assert(*,G) 3823 Set Assert Timer to (Assert_Time - Assert_Override_Interval). 3825 A4: Send AssertCancel(*,G). 3826 Delete assert info (AssertWinner(*,G,I) and 3827 AssertWinnerMetric(*,G,I) will then return to their default 3828 values). 3830 A5: Delete assert info (AssertWinner(*,G,I) and 3831 AssertWinnerMetric(*,G,I) will then return to their default 3832 values). 3834 Note that some of these actions may cause the value of 3835 JoinDesired(*,G) or RPF'(*,G)) to change, which could cause further 3836 transitions in other state machines. 3838 4.6.3. Assert Metrics 3840 Assert metrics are defined as: 3842 struct assert_metric { 3843 rpt_bit_flag; 3844 metric_preference; 3845 route_metric; 3846 ip_address; 3847 }; 3849 When comparing assert_metrics, the rpt_bit_flag, metric_preference, 3850 and route_metric field are compared in order, where the first lower 3851 value wins. If all fields are equal, the primary IP address of the 3852 router that sourced the Assert message is used as a tie-breaker, with 3853 the highest IP address winning. 3855 An assert metric for (S,G) to include in (or compare against) an 3856 Assert message sent on interface I should be computed using the 3857 following pseudocode: 3859 assert_metric 3860 my_assert_metric(S,G,I) { 3861 if( CouldAssert(S,G,I) == TRUE ) { 3862 return spt_assert_metric(S,I) 3863 } else if( CouldAssert(*,G,I) == TRUE ) { 3864 return rpt_assert_metric(G,I) 3865 } else { 3866 return infinite_assert_metric() 3867 } 3868 } 3870 spt_assert_metric(S,I) gives the assert metric we use if we're 3871 sending an assert based on active (S,G) forwarding state: 3873 assert_metric 3874 spt_assert_metric(S,I) { 3875 return {0,MRIB.pref(S),MRIB.metric(S),my_ip_address(I)} 3876 } 3878 rpt_assert_metric(G,I) gives the assert metric we use if we're 3879 sending an assert based only on (*,G) forwarding state: 3881 assert_metric 3882 rpt_assert_metric(G,I) { 3883 return {1,MRIB.pref(RP(G)),MRIB.metric(RP(G)),my_ip_address(I)} 3884 } 3886 MRIB.pref(X) and MRIB.metric(X) are the routing preference and 3887 routing metrics associated with the route to a particular (unicast) 3888 destination X, as determined by the MRIB. my_ip_address(I) is simply 3889 the router's primary IP address that is associated with the local 3890 interface I. 3892 infinite_assert_metric() gives the assert metric we need to send an 3893 assert but don't match either (S,G) or (*,G) forwarding state: 3895 assert_metric 3896 infinite_assert_metric() { 3897 return {1,infinity,infinity,0} 3898 } 3900 4.6.4. AssertCancel Messages 3902 An AssertCancel message is simply an RPT Assert message but with 3903 infinite metric. It is sent by the assert winner when it deletes the 3904 forwarding state that had caused the assert to occur. Other routers 3905 will see this metric, and it will cause any other router that has 3906 forwarding state to send its own assert, and to take over forwarding. 3908 An AssertCancel(S,G) is an infinite metric assert with the RPT bit 3909 set that names S as the source. 3911 An AssertCancel(*,G) is an infinite metric assert with the RPT bit 3912 set and the source set to zero. 3914 AssertCancel messages are simply an optimization. The original 3915 Assert timeout mechanism will allow a subnet to eventually become 3916 consistent; the AssertCancel mechanism simply causes faster 3917 convergence. No special processing is required for an AssertCancel 3918 message, since it is simply an Assert message from the current 3919 winner. 3921 4.6.5. Assert State Macros 3923 The macros lost_assert(S,G,rpt,I), lost_assert(S,G,I), and 3924 lost_assert(*,G,I) are used in the olist computations of Section 4.1, 3925 and are defined as: 3927 bool lost_assert(S,G,rpt,I) { 3928 if ( RPF_interface(RP(G)) == I OR 3929 ( RPF_interface(S) == I AND SPTbit(S,G) == TRUE ) ) { 3930 return FALSE 3931 } else { 3932 return ( AssertWinner(S,G,I) != NULL AND 3933 AssertWinner(S,G,I) != me ) 3934 } 3935 } 3936 bool lost_assert(S,G,I) { 3937 if ( RPF_interface(S) == I ) { 3938 return FALSE 3939 } else { 3940 return ( AssertWinner(S,G,I) != NULL AND 3941 AssertWinner(S,G,I) != me AND 3942 (AssertWinnerMetric(S,G,I) is better 3943 than spt_assert_metric(S,I) ) 3944 } 3945 } 3947 Note: the term "AssertWinnerMetric(S,G,I) is better than 3948 spt_assert_metric(S,I)" is required to correctly handle the 3949 transition phase when a router has (S,G) join state, but has not yet 3950 set the SPTbit. In this case, it needs to ignore the assert state if 3951 it will win the assert once the SPTbit is set. 3953 bool lost_assert(*,G,I) { 3954 if ( RPF_interface(RP(G)) == I ) { 3955 return FALSE 3956 } else { 3957 return ( AssertWinner(*,G,I) != NULL AND 3958 AssertWinner(*,G,I) != me ) 3959 } 3960 } 3962 AssertWinner(S,G,I) is the IP source address of the Assert(S,G) 3963 packet that won an Assert. 3965 AssertWinner(*,G,I) is the IP source address of the Assert(*,G) 3966 packet that won an Assert. 3968 AssertWinnerMetric(S,G,I) is the Assert metric of the Assert(S,G) 3969 packet that won an Assert. 3971 AssertWinnerMetric(*,G,I) is the Assert metric of the Assert(*,G) 3972 packet that won an Assert. 3974 AssertWinner(S,G,I) defaults to NULL and AssertWinnerMetric(S,G,I) 3975 defaults to Infinity when in the NoInfo state. 3977 Summary of Assert Rules and Rationale 3979 This section summarizes the key rules for sending and reacting to 3980 asserts and the rationale for these rules. This section is not 3981 intended to be and should not be treated as a definitive 3982 specification of protocol behavior. The state machines and 3983 pseudocode should be consulted for that purpose. Rather, this 3984 section is intended to document important aspects of the Assert 3985 protocol behavior and to provide information that may prove helpful 3986 to the reader in understanding and implementing this part of the 3987 protocol. 3989 1. Behavior: Downstream neighbors send Join(*,G) and Join(S,G) 3990 periodic messages to the appropriate RPF' neighbor, i.e., the RPF 3991 neighbor as modified by the assert process. They are not always 3992 sent to the RPF neighbor as indicated by the MRIB. Normal 3993 suppression and override rules apply. 3995 Rationale: By sending the periodic and triggered Join messages to 3996 the RPF' neighbor instead of to the RPF neighbor, the downstream 3997 router avoids re-triggering the Assert process with every Join. 3998 A side effect of sending Joins to the Assert winner is that 3999 traffic will not switch back to the "normal" RPF neighbor until 4000 the Assert times out. This will not happen until data stops 4001 flowing, if item 8, below, is implemented. 4003 2. Behavior: The assert winner for (*,G) acts as the local DR for 4004 (*,G) on behalf of IGMP/MLD members. 4006 Rationale: This is required to allow a single router to merge PIM 4007 and IGMP/MLD joins and leaves. Without this, overrides don't 4008 work. 4010 3. Behavior: The assert winner for (S,G) acts as the local DR for 4011 (S,G) on behalf of IGMPv3 members. 4013 Rationale: Same rationale as for item 2. 4015 4. Behavior: (S,G) and (*,G) prune overrides are sent to the RPF' 4016 neighbor and not to the regular RPF neighbor. 4018 Rationale: Same rationale as for item 1. 4020 5. Behavior: An (S,G,rpt) prune override is not sent (at all) if 4021 RPF'(S,G,rpt) != RPF'(*,G). 4023 Rationale: This avoids keeping state alive on the (S,G) tree when 4024 only (*,G) downstream members are left. Also, it avoids sending 4025 (S,G,rpt) joins to a router that is not on the (*,G) tree. This 4026 behavior might be confusing although this specification does 4027 indicate that such a join SHOULD be dropped. 4029 6. Behavior: An assert loser that receives a Join(S,G) with an 4030 Upstream Neighbor Address that is its primary IP address on that 4031 interface expires the (S,G) Assert Timer. 4033 Rationale: This is necessary in order to have rapid convergence 4034 in the event that the downstream router that initially sent a 4035 join to the prior Assert winner has undergone a topology change. 4037 7. Behavior: An assert loser that receives a Join(*,G) with an 4038 Upstream Neighbor Address that is its primary IP address on that 4039 interface cancels the (*,G) Assert Timer and all (S,G) assert 4040 timers that do not have corresponding Prune(S,G,rpt) messages in 4041 the compound Join/Prune message. 4043 Rationale: Same rationale as for item 6. 4045 8. Behavior: An assert winner for (*,G) or (S,G) sends a canceling 4046 assert when it is about to stop forwarding on a (*,G) or an (S,G) 4047 entry. This behavior does not apply to (S,G,rpt). 4049 Rationale: This allows switching back to the shared tree after 4050 the last SPT router on the LAN leaves. Doing this prevents 4051 downstream routers on the shared tree from keeping SPT state 4052 alive. 4054 9. Behavior: Resend the assert messages before timing out an assert. 4055 (This behavior is optional.) 4057 Rationale: This prevents the periodic duplicates that would 4058 otherwise occur each time that an assert times out and is then 4059 re-established. 4061 10. Behavior: When RPF'(S,G,rpt) changes to be the same as RPF'(*,G) 4062 we need to trigger a Join(S,G,rpt) to RPF'(*,G). 4064 Rationale: This allows switching back to the RPT after the last 4065 SPT member leaves. 4067 4.7. PIM Bootstrap and RP Discovery 4069 For correct operation, every PIM router within a PIM domain must be 4070 able to map a particular multicast group address to the same RP. If 4071 this is not the case, then black holes may appear, where some 4072 receivers in the domain cannot receive some groups. A domain in this 4073 context is a contiguous set of routers that all implement PIM and are 4074 configured to operate within a common boundary. 4076 A notable exception to this is where a PIM domain is broken up into 4077 multiple administrative scope regions; these are regions where a 4078 border has been configured so that a range of multicast groups will 4079 not be forwarded across that border. For more information on 4080 Administratively Scoped IP Multicast, see RFC 2365. The modified 4081 criteria for admin-scoped regions are that the region is convex with 4082 respect to forwarding based on the MRIB, and that all PIM routers 4083 within the scope region map scoped groups to the same RP within that 4084 region. 4086 This specification does not mandate the use of a single mechanism to 4087 provide routers with the information to perform the group-to-RP 4088 mapping. Currently four mechanisms are possible, and all four have 4089 associated problems: 4091 Static Configuration 4092 A PIM router MUST support the static configuration of group-to- 4093 RP mappings. Such a mechanism is not robust to failures, but 4094 does at least provide a basic interoperability mechanism. 4096 Embedded-RP 4097 Embedded-RP defines an address allocation policy in which the 4098 address of the Rendezvous Point (RP) is encoded in an IPv6 4099 multicast group address [17]. 4101 Cisco's Auto-RP 4102 Auto-RP uses a PIM Dense-Mode multicast group to announce group- 4103 to-RP mappings from a central location. This mechanism is not 4104 useful if PIM Dense-Mode is not being run in parallel with PIM 4105 Sparse-Mode, and was only intended for use with PIM Sparse-Mode 4106 Version 1. No standard specification currently exists. 4108 BootStrap Router (BSR) 4109 RFC 2362 specifies a bootstrap mechanism based on the automatic 4110 election of a bootstrap router (BSR). Any router in the domain 4111 that is configured to be a possible RP reports its candidacy to 4112 the BSR, and then a domain-wide flooding mechanism distributes 4113 the BSR's chosen set of RPs throughout the domain. As specified 4114 in RFC 2362, BSR is flawed in its handling of admin-scoped 4115 regions that are smaller than a PIM domain, but the mechanism 4116 does work for global-scoped groups. 4118 As far as PIM-SM is concerned, the only important requirement is that 4119 all routers in the domain (or admin scope zone for scoped regions) 4120 receive the same set of group-range-to-RP mappings. This may be 4121 achieved through the use of any of these mechanisms, or through 4122 alternative mechanisms not currently specified. 4124 It must be operationally ensured that any RP address configured, 4125 learned, or advertised is reachable from all routers in the PIM 4126 domain. 4128 4.7.1. Group-to-RP Mapping 4130 Using one of the mechanisms described above, a PIM router receives 4131 one or more possible group-range-to-RP mappings. Each mapping 4132 specifies a range of multicast groups (expressed as a group and mask) 4133 and the RP to which such groups should be mapped. Each mapping may 4134 also have an associated priority. It is possible to receive multiple 4135 mappings, all of which might match the same multicast group; this is 4136 the common case with BSR. The algorithm for performing the group-to- 4137 RP mapping is as follows: 4139 1. Perform longest match on group-range to obtain a list of RPs. 4141 2. From this list of matching RPs, find the ones with highest 4142 priority. 4144 Eliminate any RPs from the list that have lower priorities. 4146 3. If only one RP remains in the list, use that RP. 4148 4. If multiple RPs are in the list, use the PIM hash function to 4149 choose one. 4151 Thus, if two or more group-range-to-RP mappings cover a particular 4152 group, the one with the longest mask is the mapping to use. If the 4153 mappings have the same mask length, then the one with the highest 4154 priority is chosen. If there is more than one matching entry with 4155 the same longest mask and the priorities are identical, then a hash 4156 function (see Section 4.7.2) is applied to choose the RP. 4158 This algorithm is invoked by a DR when it needs to determine an RP 4159 for a given group, e.g., upon reception of a packet or IGMP/MLD 4160 membership indication for a group for which the DR does not know the 4161 RP. 4163 Furthermore, the mapping function is invoked by all routers upon 4164 receiving a (*,G) Join/Prune message. 4166 Note that if the set of possible group-range-to-RP mappings changes, 4167 each router will need to check whether any existing groups are 4168 affected. This may, for example, cause a DR or acting DR to re-join a 4169 group, or cause it to restart register encapsulation to the new RP. 4171 Implementation note: the bootstrap mechanism described in RFC 2362 4172 omitted step 1 above. However, of the implementations we are aware 4173 of, approximately half performed step 1 anyway. Note that 4174 implementations of BSR that omit step 1 will not correctly 4175 interoperate with implementations of this specification when used 4176 with the BSR mechanism described in [11]. 4178 4.7.2. Hash Function 4180 The hash function is used by all routers within a domain, to map a 4181 group to one of the RPs from the matching set of group-range-to-RP 4182 mappings (this set all have the same longest mask length and same 4183 highest priority). The algorithm takes as input the group address, 4184 and the addresses of the candidate RPs from the mappings, and gives 4185 as output one RP address to be used. 4187 The protocol requires that all routers hash to the same RP within a 4188 domain (except for transients). The following hash function must be 4189 used in each router: 4191 1. For RP addresses in the matching group-range-to-RP mappings, 4192 compute a value: 4194 Value(G,M,C(i))= 4195 (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31 4197 where C(i) is the RP address and M is a hash-mask. If BSR is 4198 being used, the hash-mask is given in the Bootstrap messages. If 4199 BSR is not being used, the alternative mechanism that supplies 4200 the group-range-to-RP mappings may supply the value, or else it 4201 defaults to a mask with the most significant 30 bits being one 4202 for IPv4 and the most significant 126 bits being one for IPv6. 4203 The hash-mask allows a small number of consecutive groups (e.g., 4204 4) to always hash to the same RP. For instance, hierarchically- 4205 encoded data can be sent on consecutive group addresses to get 4206 the same delay and fate-sharing characteristics. 4208 For address families other than IPv4, a 32-bit digest to be used 4209 as C(i) and G must first be derived from the actual RP or group 4210 address. Such a digest method must be used consistently 4211 throughout the PIM domain. For IPv6 addresses, it is RECOMMENDED 4212 to use the equivalent IPv4 address for an IPv4-compatible 4213 address, and the exclusive-or of each 32-bit segment of the 4214 address for all other IPv6 addresses. For example, the digest of 4215 the IPv6 address 3ffe:b00:c18:1::10 would be computed as 4216 0x3ffe0b00 ^ 0x0c180001 ^ 0x00000000 ^ 0x00000010, where ^ 4217 represents the exclusive-or operation. 4219 2. The candidate RP with the highest resulting hash value is then 4220 the RP chosen by this Hash Function. If more than one RP has the 4221 same highest hash value, the RP with the highest IP address is 4222 chosen. 4224 4.8. Source-Specific Multicast 4226 The Source-Specific Multicast (SSM) service model [6] can be 4227 implemented with a strict subset of the PIM-SM protocol mechanisms. 4228 Both regular IP Multicast and SSM semantics can coexist on a single 4229 router, and both can be implemented using the PIM-SM protocol. A 4230 range of multicast addresses, currently 232.0.0.0/8 in IPv4 and 4231 FF3x::/32 for IPv6, is reserved for SSM, and the choice of semantics 4232 is determined by the multicast group address in both data packets and 4233 PIM messages. 4235 4.8.1. Protocol Modifications for SSM Destination Addresses 4237 The following rules override the normal PIM-SM behavior for a 4238 multicast address G in the SSM range: 4240 o A router MUST NOT send a (*,G) Join/Prune message for any reason. 4242 o A router MUST NOT send an (S,G,rpt) Join/Prune message for any 4243 reason. 4245 o A router MUST NOT send a Register message for any packet that is 4246 destined to an SSM address. 4248 o A router MUST NOT forward packets based on (*,G) or (S,G,rpt) 4249 state. The (*,G)- and (S,G,rpt)-related state summarization macros 4250 are NULL for any SSM address, for the purposes of packet 4251 forwarding. 4253 o A router acting as an RP MUST NOT forward any Register-encapsulated 4254 packet that has an SSM destination address, and SHOULD respond with 4255 a Register-Stop message to such a Register message. 4257 o A router MAY optimize out the creation and maintenance of (S,G,rpt) 4258 and (*,G) state for SSM destination addresses -- this state is not 4259 needed for SSM packets. 4261 The last three rules are present to deal with SSM-unaware "legacy" 4262 routers that may be sending (*,G) and (S,G,rpt) Join/Prunes, or 4263 Register messages for SSM destination addresses. Note that this 4264 specification does not attempt to aid an SSM-unaware "legacy" router 4265 with SSM operations. 4267 4.8.2. PIM-SSM-Only Routers 4269 An implementer may choose to implement only the subset of PIM Sparse- 4270 Mode that provides SSM forwarding semantics. 4272 A PIM-SSM-only router MUST implement the following portions of this 4273 specification: 4275 o Upstream (S,G) state machine (Section 4.5.5) 4277 o Downstream (S,G) state machine (Section 4.5.2) 4279 o (S,G) Assert state machine (Section 4.6.1) 4281 o Hello messages, neighbor discovery, and DR election (Section 4.3) 4283 o Packet forwarding rules (Section 4.2) 4285 A PIM-SSM-only router does not need to implement the following 4286 protocol elements: 4288 o Register state machine (Section 4.4) 4290 o (*,G) and (S,G,rpt) Downstream state machines (Sections 4.5.2, 4291 4.5.4, and 4.5.1) 4293 o (*,G) and (S,G,rpt) Upstream state machines (Sections 4.5.6, 4.5.8, 4294 and 4.5.5) 4296 o (*,G) Assert state machine (Section 4.6.2) 4298 o Bootstrap RP Election (Section 4.7) 4300 o Keepalive Timer 4302 o SPTbit (Section 4.2.2) 4304 The Keepalive Timer should be treated as always running, and SPTbit 4305 should be treated as always being set for an SSM address. 4306 Additionally, the Packet forwarding rules of Section 4.2 can be 4307 simplified in a PIM-SSM-only router: 4309 oiflist = NULL 4311 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 4312 oiflist = inherited_olist(S,G) 4313 } else if( iif is in inherited_olist(S,G) ) { 4314 send Assert(S,G) on iif 4315 } 4317 oiflist = oiflist (-) iif 4318 forward packet on all interfaces in oiflist 4320 This is nothing more than the reduction of the normal PIM-SM 4321 forwarding rule, with all (S,G,rpt) and (*,G) clauses replaced with 4322 NULL. 4324 4.9. PIM Packet Formats 4326 This section describes the details of the packet formats for PIM 4327 control messages. 4329 All PIM control messages have IP protocol number 103. 4331 PIM messages are either unicast (e.g., Registers and Register-Stop) 4332 or multicast with TTL 1 to the 'ALL-PIM-ROUTERS' group (e.g., 4333 Join/Prune, Asserts, etc.). The source address used for unicast 4334 messages is a domain-wide reachable address; the source address used 4335 for multicast messages is the link-local address of the interface on 4336 which the message is being sent. 4338 The IPv4 'ALL-PIM-ROUTERS' group is '224.0.0.13'. The IPv6 'ALL-PIM- 4339 ROUTERS' group is 'ff02::d'. 4341 The PIM header common to all PIM messages is: 4343 0 1 2 3 4344 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 4345 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4346 |PIM Ver| Type | Reserved | Checksum | 4347 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4349 PIM Ver 4350 PIM Version number is 2. 4352 Type 4353 Types for specific PIM messages. PIM Types are: 4355 Message Type Destination 4356 --------------------------------------------------------------------- 4357 0 = Hello Multicast to ALL-PIM-ROUTERS 4358 1 = Register Unicast to RP 4359 2 = Register-Stop Unicast to source of Register 4360 packet 4361 3 = Join/Prune Multicast to ALL-PIM-ROUTERS 4362 4 = Bootstrap Multicast to ALL-PIM-ROUTERS 4363 5 = Assert Multicast to ALL-PIM-ROUTERS 4364 6 = Graft (used in PIM-DM only) Unicast to RPF'(S) 4365 7 = Graft-Ack (used in PIM-DM only) Unicast to source of Graft 4366 packet 4367 8 = Candidate-RP-Advertisement Unicast to Domain's BSR 4369 Reserved 4370 Set to zero on transmission. Ignored upon receipt. 4372 Checksum 4373 The checksum is a standard IP checksum, i.e., the 16-bit one's 4374 complement of the one's complement sum of the entire PIM 4375 message, excluding the "Multicast data packet" section of the 4376 Register message. For computing the checksum, the checksum 4377 field is zeroed. If the packet's length is not an integral 4378 number of 16-bit words, the packet is padded with a trailing 4379 byte of zero before performing the checksum. 4381 For IPv6, the checksum also includes the IPv6 "pseudo-header", 4382 as specified in RFC 2460, Section 8.1 [5]. This "pseudo-header" 4383 is prepended to the PIM header for the purposes of calculating 4384 the checksum. The "Upper-Layer Packet Length" in the pseudo- 4385 header is set to the length of the PIM message, except in 4386 Register messages where it is set to the length of the PIM 4387 register header (8). The Next Header value used in the pseudo- 4388 header is 103. 4390 If a message is received with an unrecognized PIM Ver or Type field, 4391 or if a message's destination does not correspond to the table above, 4392 the message MUST be discarded, and an error message SHOULD be logged 4393 to the administrator in a rate-limited manner. 4395 4.9.1. Encoded Source and Group Address Formats 4397 Encoded-Unicast Address 4399 An Encoded-Unicast address takes the following format: 4401 0 1 2 3 4402 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 4403 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4404 | Addr Family | Encoding Type | Unicast Address 4405 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4407 Addr Family 4408 The PIM address family of the 'Unicast Address' field of this 4409 address. 4411 Values 0-127 are as assigned by the IANA for Internet Address 4412 Families in [7]. Values 128-250 are reserved to be assigned by 4413 the IANA for PIM-specific Address Families. Values 251 though 4414 255 are designated for private use. As there is no assignment 4415 authority for this space, collisions should be expected. 4417 Encoding Type 4418 The type of encoding used within a specific Address Family. The 4419 value '0' is reserved for this field and represents the native 4420 encoding of the Address Family. 4422 Unicast Address 4423 The unicast address as represented by the given Address Family 4424 and Encoding Type. 4426 Encoded-Group Address 4428 Encoded-Group addresses take the following format: 4430 0 1 2 3 4431 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 4432 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4433 | Addr Family | Encoding Type |B| Reserved |Z| Mask Len | 4434 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4435 | Group multicast Address 4436 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4438 Addr Family 4439 Described above. 4441 Encoding Type 4442 Described above. 4444 [B]idirectional PIM 4445 Indicates the group range should use Bidirectional PIM [13]. 4446 For PIM-SM defined in this specification, this bit MUST be zero. 4448 Reserved 4449 Transmitted as zero. Ignored upon receipt. 4451 Admin Scope [Z]one 4452 indicates the group range is an admin scope zone. This is used 4453 in the Bootstrap Router Mechanism [11] only. For all other 4454 purposes, this bit is set to zero and ignored on receipt. 4456 Mask Len 4457 The Mask length field is 8 bits. The value is the number of 4458 contiguous one bits that are left justified and used as a mask; 4459 when combined with the group address, it describes a range of 4460 groups. It is less than or equal to the address length in bits 4461 for the given Address Family and Encoding Type. If the message 4462 is sent for a single group, then the Mask length must equal the 4463 address length in bits for the given Address Family and Encoding 4464 Type (e.g., 32 for IPv4 native encoding, 128 for IPv6 native 4465 encoding). 4467 Group multicast Address 4468 Contains the group address. 4470 Encoded-Source Address 4472 Encoded-Source address takes the following format: 4474 0 1 2 3 4475 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 4476 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4477 | Addr Family | Encoding Type | Rsrvd |S|W|R| Mask Len | 4478 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4479 | Source Address 4480 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... 4482 Addr Family 4483 Described above. 4485 Encoding Type 4486 Described above. 4488 Reserved 4489 Transmitted as zero, ignored on receipt. 4491 S The Sparse bit is a 1-bit value, set to 1 for PIM-SM. It is 4492 used for PIM version 1 compatibility. 4494 W The WC (or WildCard) bit is a 1-bit value for use with PIM 4495 Join/Prune messages (see Section 4.9.5.1). 4497 R The RPT (or Rendezvous Point Tree) bit is a 1-bit value for use 4498 with PIM Join/Prune messages (see Section 4.9.5.1). If the WC 4499 bit is 1, the RPT bit MUST be 1. 4501 Mask Len 4502 The mask length field is 8 bits. The value is the number of 4503 contiguous one bits left justified used as a mask which, 4504 combined with the Source Address, describes a source subnet. 4505 The mask length MUST be equal to the mask length in bits for the 4506 given Address Family and Encoding Type (32 for IPv4 native and 4507 128 for IPv6 native). A router SHOULD ignore any messages 4508 received with any other mask length. 4510 Source Address 4511 The source address. 4513 4.9.2. Hello Message Format 4515 It is sent periodically by routers on all interfaces. 4517 0 1 2 3 4518 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 4519 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4520 |PIM Ver| Type | Reserved | Checksum | 4521 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4522 | OptionType | OptionLength | 4523 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4524 | OptionValue | 4525 | ... | 4526 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4527 | . | 4528 | . | 4529 | . | 4530 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4531 | OptionType | OptionLength | 4532 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4533 | OptionValue | 4534 | ... | 4535 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4537 PIM Version, Type, Reserved, Checksum 4538 Described in Section 4.9. 4540 OptionType 4541 The type of the option given in the following OptionValue field. 4543 OptionLength 4544 The length of the OptionValue field in bytes. 4546 OptionValue 4547 A variable length field, carrying the value of the option. 4549 The Option fields may contain the following values: 4551 o OptionType 1: Holdtime 4553 0 1 2 3 4554 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 4555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4556 | Type = 1 | Length = 2 | 4557 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4558 | Holdtime | 4559 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4561 Holdtime is the amount of time a receiver must keep the neighbor 4562 reachable, in seconds. If the Holdtime is set to '0xffff', the 4563 receiver of this message never times out the neighbor. This may be 4564 used with dial-on-demand links, to avoid keeping the link up with 4565 periodic Hello messages. 4567 An implementation MAY provide a configuration mechanism to reject a 4568 Hello message with holdtime 0xffff, and/or provide a mechanism to 4569 remove a neighbor. 4571 Hello messages with a Holdtime value set to '0' are also sent by a 4572 router on an interface about to go down or changing IP address (see 4573 Section 4.3.1). These are effectively goodbye messages, and the 4574 receiving routers SHOULD immediately time out the neighbor 4575 information for the sender. 4577 o OptionType 2: LAN Prune Delay 4579 0 1 2 3 4580 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 4581 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4582 | Type = 2 | Length = 4 | 4583 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4584 |T| Propagation_Delay | Override_Interval | 4585 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4587 The LAN Prune Delay option is used to tune the prune propagation 4588 delay on multi-access LANs. The T bit specifies the ability of the 4589 sending router to disable join suppression. Propagation_Delay and 4590 Override_Interval are time intervals in units of milliseconds. A 4591 router originating a LAN Prune Delay option on interface I sets the 4592 Propagation_Delay field to the configured value of 4593 Propagation_Delay(I) and the value of the Override_Interval field 4594 to the value of Override_Interval(I). On a receiving router, the 4595 values of the fields are used to tune the value of the 4596 Effective_Override_Interval(I) and its derived timer values. 4598 Section 4.3.3 describes how these values affect the behavior of a 4599 router. 4601 o OptionType 3 to 16: reserved to be defined in future versions of 4602 this document. 4604 o OptionType 18: deprecated and should not be used. 4606 o OptionType 19: DR Priority 4608 0 1 2 3 4609 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 4610 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4611 | Type = 19 | Length = 4 | 4612 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4613 | DR Priority | 4614 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4616 DR Priority is a 32-bit unsigned number and should be considered in 4617 the DR election as described in Section 4.3.2. 4619 o OptionType 20: Generation ID 4621 0 1 2 3 4622 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 4623 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4624 | Type = 20 | Length = 4 | 4625 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4626 | Generation ID | 4627 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4629 Generation ID is a random 32-bit value for the interface on which 4630 the Hello message is sent. The Generation ID is regenerated 4631 whenever PIM forwarding is started or restarted on the interface. 4633 o OptionType 24: Address List 4635 0 1 2 3 4636 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 4637 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4638 | Type = 24 | Length = | 4639 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4640 | Secondary Address 1 (Encoded-Unicast format) | 4641 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4642 ... 4643 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4644 | Secondary Address N (Encoded-Unicast format) | 4645 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4647 The contents of the Address List Hello option are described in 4648 Section 4.3.4. All addresses within a single Address List must 4649 belong to the same address family. 4651 OptionTypes 17 through 65000 are assigned by the IANA. OptionTypes 4652 65001 through 65535 are reserved for Private Use, as defined in [9]. 4654 Unknown options MUST be ignored and MUST NOT prevent a neighbor 4655 relationship from being formed. The "Holdtime" option MUST be 4656 implemented; the "DR Priority" and "Generation ID" options SHOULD be 4657 implemented. The "Address List" option MUST be implemented for IPv6. 4659 4.9.3. Register Message Format 4661 A Register message is sent by the DR to the RP when a multicast 4662 packet needs to be transmitted on the RP-tree. The IP source address 4663 is set to the address of the DR, the destination address to the RP's 4664 address. The IP TTL of the PIM packet is the system's normal unicast 4665 TTL. 4667 0 1 2 3 4668 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 4669 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4670 |PIM Ver| Type | Reserved | Checksum | 4671 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4672 |B|N| Reserved2 | 4673 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4674 | | 4675 . Multicast data packet . 4676 | | 4677 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4678 PIM Version, Type, Reserved, Checksum 4679 Described in Section 4.9. Note that in order to reduce 4680 encapsulation overhead, the checksum for Registers is done only 4681 on the first 8 bytes of the packet, including the PIM header and 4682 the next 4 bytes, excluding the data packet portion. For 4683 interoperability reasons, a message carrying a checksum 4684 calculated over the entire PIM Register message should also be 4685 accepted. When calculating the checksum, the IPv6 pseudoheader 4686 "Upper-Layer Packet Length" is set to 8. 4688 B The Border bit. This specification deprecates the Border bit. A 4689 router MUST set B bit to 0 on tranmission and MUST ignore this 4690 bit on reception. 4692 N The Null-Register bit. Set to 1 by a DR that is probing the RP 4693 before expiring its local Register-Suppression Timer. Set to 0 4694 otherwise. 4696 Reserved2 4697 Transmitted as zero, ignored on receipt. 4699 Multicast data packet 4700 The original packet sent by the source. This packet must be of 4701 the same address family as the encapsulating PIM packet, e.g., 4702 an IPv6 data packet must be encapsulated in an IPv6 PIM packet. 4703 Note that the TTL of the original packet is decremented before 4704 encapsulation, just like any other packet that is forwarded. In 4705 addition, the RP decrements the TTL after decapsulating, before 4706 forwarding the packet down the shared tree. 4708 For (S,G) Null-Registers, the Multicast data packet portion 4709 contains a dummy IP header with S as the source address, G as 4710 the destination address. When generating an IPv4 Null-Register 4711 message, the fields in the dummy IPv4 header SHOULD be filled in 4712 according to the following table. Other IPv4 header fields may 4713 contain any value that is valid for that field. 4715 Field Value 4716 --------------------------------------- 4717 IP Version 4 4718 Header Length 5 4719 Checksum Header checksum 4720 Fragmentation offset 0 4721 More Fragments 0 4722 Total Length 20 4723 IP Protocol 103 (PIM) 4725 On receipt of an (S,G) Null-Register, if the Header Checksum 4726 field is non-zero, the recipient SHOULD check the checksum and 4727 discard null registers that have a bad checksum. The recipient 4728 SHOULD NOT check the value of any individual fields; a correct 4729 IP header checksum is sufficient. If the Header Checksum field 4730 is zero, the recipient MUST NOT check the checksum. 4732 With IPv6, an implementation generates a dummy IP header 4733 followed by a dummy PIM header with values according to the 4734 following table in addition to the source and group. Other IPv6 4735 header fields may contain any value that is valid for that 4736 field. 4738 Header Field Value 4739 -------------------------------------- 4740 IP Version 6 4741 Next Header 103 (PIM) 4742 Length 4 4743 PIM Version 0 4744 PIM Type 0 4745 PIM Reserved 0 4746 PIM Checksum PIM checksum including 4747 IPv6 "pseudo-header"; 4748 see Section 4.9 4750 On receipt of an IPv6 (S,G) Null-Register, if the dummy PIM 4751 header is present, the recipient SHOULD check the checksum and 4752 discard Null-Registers that have a bad checksum. 4754 4.9.4. Register-Stop Message Format 4756 A Register-Stop is unicast from the RP to the sender of the Register 4757 message. The IP source address is the address to which the register 4758 was addressed. The IP destination address is the source address of 4759 the register message. 4761 0 1 2 3 4762 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 4763 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4764 |PIM Ver| Type | Reserved | Checksum | 4765 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4766 | Group Address (Encoded-Group format) | 4767 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4768 | Source Address (Encoded-Unicast format) | 4769 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4771 PIM Version, Type, Reserved, Checksum 4772 Described in Section 4.9. 4774 Group Address 4775 The group address from the multicast data packet in the 4776 Register. Format described in Section 4.9.1. Note that for 4777 Register-Stops the Mask Len field contains the full address 4778 length * 8 (e.g., 32 for IPv4 native encoding), if the message 4779 is sent for a single group. 4781 Source Address 4782 The host address of the source from the multicast data packet in 4783 the register. The format for this address is given in the 4784 Encoded-Unicast address in Section 4.9.1. A special wild card 4785 value consisting of an address field of all zeros can be used to 4786 indicate any source. 4788 4.9.5. Join/Prune Message Format 4790 A Join/Prune message is sent by routers towards upstream sources and 4791 RPs. Joins are sent to build shared trees (RP trees) or source trees 4792 (SPT). Prunes are sent to prune source trees when members leave 4793 groups as well as sources that do not use the shared tree. 4795 0 1 2 3 4796 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 4797 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4798 |PIM Ver| Type | Reserved | Checksum | 4799 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4800 | Upstream Neighbor Address (Encoded-Unicast format) | 4801 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4802 | Reserved | Num groups | Holdtime | 4803 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4804 | Multicast Group Address 1 (Encoded-Group format) | 4805 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4806 | Number of Joined Sources | Number of Pruned Sources | 4807 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4808 | Joined Source Address 1 (Encoded-Source format) | 4809 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4810 | . | 4811 | . | 4812 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4813 | Joined Source Address n (Encoded-Source format) | 4814 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4815 | Pruned Source Address 1 (Encoded-Source format) | 4816 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4817 | . | 4818 | . | 4819 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4820 | Pruned Source Address n (Encoded-Source format) | 4821 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4822 | . | 4823 | . | 4824 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4825 | Multicast Group Address m (Encoded-Group format) | 4826 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4827 | Number of Joined Sources | Number of Pruned Sources | 4828 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4829 | Joined Source Address 1 (Encoded-Source format) | 4830 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4831 | . | 4832 | . | 4833 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4834 | Joined Source Address n (Encoded-Source format) | 4835 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4836 | Pruned Source Address 1 (Encoded-Source format) | 4837 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4838 | . | 4839 | . | 4840 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4841 | Pruned Source Address n (Encoded-Source format) | 4842 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4843 PIM Version, Type, Reserved, Checksum 4844 Described in Section 4.9. 4846 Unicast Upstream Neighbor Address 4847 The primary address of the upstream neighbor that is the target 4848 of the message. The format for this address is given in the 4849 Encoded-Unicast address in Section 4.9.1. 4851 Reserved 4852 Transmitted as zero, ignored on receipt. 4854 Holdtime 4855 The amount of time a receiver MUST keep the Join/Prune state 4856 alive, in seconds. If the Holdtime is set to '0xffff', the 4857 receiver of this message SHOULD hold the state until canceled by 4858 the appropriate canceling Join/Prune message, or timed out 4859 according to local policy. This may be used with dial-on-demand 4860 links, to avoid keeping the link up with periodic Join/Prune 4861 messages. 4863 Note that the HoldTime MUST be larger than the 4864 J/P_Override_Interval(I). 4866 Number of Groups 4867 The number of multicast group sets contained in the message. 4869 Multicast group address 4870 For format description, see Section 4.9.1. 4872 Number of Joined Sources 4873 Number of joined source addresses listed for a given group. 4875 Joined Source Address 1 .. n 4876 This list contains the sources for a given group that the 4877 sending router will forward multicast datagrams from if received 4878 on the interface on which the Join/Prune message is sent. 4880 See Encoded-Source-Address format in Section 4.9.1. 4882 Number of Pruned Sources 4883 Number of pruned source addresses listed for a group. 4885 Pruned Source Address 1 .. n 4886 This list contains the sources for a given group that the 4887 sending router does not want to forward multicast datagrams from 4888 when received on the interface on which the Join/Prune message 4889 is sent. 4891 Within one PIM Join/Prune message, all the Multicast Group Addresses, 4892 Joined Source addresses, and Pruned Source addresses MUST be of the 4893 same address family. It is NOT PERMITTED to mix IPv4 and IPv6 4894 addresses within the same message. In addition, the address family 4895 of the fields in the message SHOULD be the same as the IP source and 4896 destination addresses of the packet. This permits maximum 4897 implementation flexibility for dual-stack IPv4/IPv6 routers. If a 4898 router receives a message with mixed family addresses, it SHOULD only 4899 process the addresses that are of the same family as the unicast 4900 upstream neighbor address. 4902 4.9.5.1. Group Set Source List Rules 4904 As described above, Join/Prune messages are composed of one or more 4905 group sets. Each set contains two source lists, the Joined Sources 4906 and the Pruned Sources. This section describes the different types 4907 of group sets and source list entries that can exist in a Join/Prune 4908 message. 4910 There is one valid group set type: 4912 Group-Specific Set 4913 A Group-Specific Set is represented by a valid IP multicast 4914 address in the group address field and the full length of the IP 4915 address in the mask length field of the Multicast Group Address. 4916 Each Join/Prune message SHOULD NOT contain more than one group- 4917 specific set for the same IP multicast address. Each group- 4918 specific set may contain (*,G), (S,G,rpt), and (S,G) source list 4919 entries in the Joined or Pruned lists. 4921 (*,G) 4922 The (*,G) source list entry is used in Join/Prune messages 4923 sent towards the RP for the specified group. It expresses 4924 interest (or lack thereof) in receiving traffic sent to the 4925 group through the Rendezvous-Point shared tree. There MUST 4926 only be one such entry in both the Joined and Pruned lists of 4927 a group-specific set. 4929 (*,G) source list entries have the Source-Address set to the 4930 address of the RP for group G, the Source-Address Mask-Len set 4931 to the full length of the IP address, and both the WC and RPT 4932 bits of the Encoded-Source-Address set. 4934 (S,G,rpt) 4935 The (S,G,rpt) source list entry is used in Join/Prune messages 4936 sent towards the RP for the specified group. It expresses 4937 interest (or lack thereof) in receiving traffic through the 4938 shared tree sent by the specified source to this group. For 4939 each source address, the entry MUST exist in only one of the 4940 Joined and Pruned source lists of a group-specific set, but 4941 not both. 4943 (S,G,rpt) source list entries have the Source-Address set to 4944 the address of the source S, the Source-Address Mask-Len set 4945 to the full length of the IP address, and the WC bit cleared 4946 and the RPT bit set in the Encoded-Source-Address. 4948 (S,G) 4949 The (S,G) source list entry is used in Join/Prune messages 4950 sent towards the specified source. It expresses interest (or 4951 lack thereof) in receiving traffic through the shortest path 4952 tree sent by the source to the specified group. For each 4953 source address, the entry MUST exist in only one of the Joined 4954 and Pruned source lists of a group-specific set, but not both. 4956 (S,G) source list entries have the Source-Address set to the 4957 address of the source S, the Source-Address Mask-Len set to 4958 the full length of the IP address, and both the WC and RPT 4959 bits of the Encoded-Source-Address cleared. 4961 The rules described above are sufficient to prevent invalid 4962 combinations of source list entries in group-specific sets. There 4963 are, however, a number of combinations that have a valid 4964 interpretation but that are not generated by the protocol as 4965 described in this specification: 4967 o Combining a (*,G) Join and an (S,G,rpt) Join entry in the same 4968 message is redundant as the (*,G) entry covers the information 4969 provided by the (S,G,rpt) entry. 4971 o The same applies for a (*,G) Prune and an (S,G,rpt) Prune. 4973 o The combination of a (*,G) Prune and an (S,G,rpt) Join is also not 4974 generated. (S,G,rpt) Joins are only sent when the router is 4975 receiving all traffic for a group on the shared tree and it wishes 4976 to indicate a change for the particular source. As a (*,G) prune 4977 indicates that the router no longer wishes to receive shared tree 4978 traffic, the (S,G,rpt) Join would be meaningless. 4980 o As Join/Prune messages are targeted to a single PIM neighbor, 4981 including both an (S,G) Join and an (S,G,rpt) Prune in the same 4982 message is usually redundant. The (S,G) Join informs the neighbor 4983 that the sender wishes to receive the particular source on the 4984 shortest path tree. It is therefore unnecessary for the router to 4985 say that it no longer wishes to receive it on the shared tree. 4986 However, there is a valid interpretation for this combination of 4987 entries. A downstream router may have to instruct its upstream 4988 only to start forwarding a specific source once it has started 4989 receiving the source on the shortest-path tree. 4991 o The combination of an (S,G) Prune and an (S,G,rpt) Join could 4992 possibly be used by a router to switch from receiving a particular 4993 source on the shortest-path tree back to receiving it on the shared 4994 tree (provided that the RPF neighbor for the shortest-path and 4995 shared trees is common). However, Sparse-Mode PIM does not provide 4996 a mechanism for explicitly switching back to the shared tree. 4998 The rules are summarized in the tables below. 5000 +----------++------+-------+-----------+-----------+-------+-------+ 5001 | ||Join | Prune | Join | Prune | Join | Prune | 5002 | ||(*,G) | (*,G) | (S,G,rpt) | (S,G,rpt) | (S,G) | (S,G) | 5003 +----------++------+-------+-----------+-----------+-------+-------+ 5004 |Join ||- | no | ? | yes | yes | yes | 5005 |(*,G) || | | | | | | 5006 +----------++------+-------+-----------+-----------+-------+-------+ 5007 |Prune ||no | - | ? | ? | yes | yes | 5008 |(*,G) || | | | | | | 5009 +----------++------+-------+-----------+-----------+-------+-------+ 5010 |Join ||? | ? | - | no | yes | ? | 5011 |(S,G,rpt) || | | | | | | 5012 +----------++------+-------+-----------+-----------+-------+-------+ 5013 |Prune ||yes | ? | no | - | yes | ? | 5014 |(S,G,rpt) || | | | | | | 5015 +----------++------+-------+-----------+-----------+-------+-------+ 5016 |Join ||yes | yes | yes | yes | - | no | 5017 |(S,G) || | | | | | | 5018 +----------++------+-------+-----------+-----------+-------+-------+ 5019 |Prune ||yes | yes | ? | ? | no | - | 5020 |(S,G) || | | | | | | 5021 +----------++------+-------+-----------+-----------+-------+-------+ 5023 yes Allowed and expected. 5025 no Combination is not allowed by the protocol and MUST NOT be 5026 generated by a router. A router MAY accept these messages, but 5027 the result is undefined. An error message MAY be logged to the 5028 administrator in a rate-limited manner. 5030 ? Combination not expected by the protocol, but well-defined. A 5031 router MAY accept it but SHOULD NOT generate it. 5033 The order of source list entries in a group set source list is not 5034 important, except where limited by the packet format itself. 5036 4.9.5.2. Group Set Fragmentation 5038 When building a Join/Prune for a particular neighbor, a router should 5039 try to include in the message as much of the information it needs to 5040 convey to the neighbor as possible. This implies adding one group 5041 set for each multicast group that has information pending 5042 transmission and within each set including all relevant source list 5043 entries. 5045 On a router with a large amount of multicast state, the number of 5046 entries that must be included may result in packets that are larger 5047 than the maximum IP packet size. In most such cases, the information 5048 may be split into multiple messages. 5050 There is an exception with group sets that contain a (*,G) Joined 5051 source list entry. The group set expresses the router's interest in 5052 receiving all traffic for the specified group on the shared tree, and 5053 it MUST include an (S,G,rpt) Pruned source list entry for every 5054 source that the router does not wish to receive. This list of 5055 (S,G,rpt) Pruned source-list entries MUST NOT be split in multiple 5056 messages. 5058 If only N (S,G,rpt) Prune entries fit into a maximum-sized Join/Prune 5059 message, but the router has more than N (S,G,rpt) Prunes to add, then 5060 the router MUST choose to include the first N (numerically smallest 5061 in network byte order) IP addresses, and the rest are ignored (not 5062 included). 5064 4.9.6. Assert Message Format 5066 The Assert message is used to resolve forwarder conflicts between 5067 routers on a link. It is sent when a router receives a multicast 5068 data packet on an interface on which the router would normally have 5069 forwarded that packet. Assert messages may also be sent in response 5070 to an Assert message from another router. 5072 0 1 2 3 5073 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 5074 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5075 |PIM Ver| Type | Reserved | Checksum | 5076 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5077 | Group Address (Encoded-Group format) | 5078 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5079 | Source Address (Encoded-Unicast format) | 5080 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5081 |R| Metric Preference | 5082 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5083 | Metric | 5084 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5086 PIM Version, Type, Reserved, Checksum 5087 Described in Section 4.9. 5089 Group Address 5090 The group address for which the router wishes to resolve the 5091 forwarding conflict. This is an Encoded-Group address, as 5092 specified in Section 4.9.1. 5094 Source Address 5095 Source address for which the router wishes to resolve the 5096 forwarding conflict. The source address MAY be set to zero for 5097 (*,G) asserts (see below). The format for this address is given 5098 in Encoded-Unicast-Address in Section 4.9.1. 5100 R RPTbit is a 1-bit value. The RPTbit is set to 1 for Assert(*,G) 5101 messages and 0 for Assert(S,G) messages. 5103 Metric Preference 5104 Preference value assigned to the unicast routing protocol that 5105 provided the route to the multicast source or Rendezvous-Point. 5107 Metric 5108 The unicast routing table metric associated with the route used 5109 to reach the multicast source or Rendezvous-Point. The metric 5110 is in units applicable to the unicast routing protocol used. 5112 Assert messages can be sent to resolve a forwarding conflict for all 5113 traffic to a given group or for a specific source and group. 5115 Assert(S,G) 5116 Source-specific asserts are sent by routers forwarding a 5117 specific source on the shortest-path tree (SPTbit is TRUE). 5118 (S,G) Asserts have the Group-Address field set to the group G 5119 and the Source-Address field set to the source S. The RPTbit is 5120 set to 0, the Metric-Preference is set to MRIB.pref(S) and the 5121 Metric is set to MRIB.metric(S). 5123 Assert(*,G) 5124 Group-specific asserts are sent by routers forwarding data for 5125 the group and source(s) under contention on the shared tree. 5126 (*,G) asserts have the Group-Address field set to the group G. 5127 For data-triggered Asserts, the Source-Address field MAY be set 5128 to the IP source address of the data packet that triggered the 5129 Assert and is set to zero otherwise. The RPTbit is set to 1, 5130 the Metric-Preference is set to MRIB.pref(RP(G)), and the Metric 5131 is set to MRIB.metric(RP(G)). 5133 4.10. PIM Timers 5135 PIM-SM maintains the following timers, as discussed in Section 4.1. 5136 All timers are countdown timers; they are set to a value and count 5137 down to zero, at which point they typically trigger an action. Of 5138 course they can just as easily be implemented as count-up timers, 5139 where the absolute expiry time is stored and compared against a real- 5140 time clock, but the language in this specification assumes that they 5141 count downwards to zero. 5143 Global Timers 5145 Per interface (I): 5147 Hello Timer: HT(I) 5149 Per neighbor (N): 5151 Neighbor Liveness Timer: NLT(N,I) 5153 Per Group (G): 5155 (*,G) Join Expiry Timer: ET(*,G,I) 5157 (*,G) Prune-Pending Timer: PPT(*,G,I) 5159 (*,G) Assert Timer: AT(*,G,I) 5161 Per Source (S): 5163 (S,G) Join Expiry Timer: ET(S,G,I) 5165 (S,G) Prune-Pending Timer: PPT(S,G,I) 5167 (S,G) Assert Timer: AT(S,G,I) 5169 (S,G,rpt) Prune Expiry Timer: ET(S,G,rpt,I) 5171 (S,G,rpt) Prune-Pending Timer: PPT(S,G,rpt,I) 5173 Per Group (G): 5175 (*,G) Upstream Join Timer: JT(*,G) 5177 Per Source (S): 5179 (S,G) Upstream Join Timer: JT(S,G) 5181 (S,G) Keepalive Timer: KAT(S,G) 5183 (S,G,rpt) Upstream Override Timer: OT(S,G,rpt) 5185 At the DRs or relevant Assert Winners only: 5187 Per Source,Group pair (S,G): 5189 Register-Stop Timer: RST(S,G) 5191 4.11. Timer Values 5193 When timers are started or restarted, they are set to default values. 5194 This section summarizes those default values. 5196 Note that protocol events or configuration may change the default 5197 value of a timer on a specific interface. When timers are 5198 initialized in this document, the value specific to the interface in 5199 context must be used. 5201 Some of the timers listed below (Prune-Pending, Upstream Join, 5202 Upstream Override) can be set to values that depend on the settings 5203 of the Propagation_Delay and Override_Interval of the corresponding 5204 interface. The default values for these are given below. 5206 Variable Name: Propagation_Delay(I) 5208 +-------------------------------+--------------+----------------------+ 5209 | Value Name | Value | Explanation | 5210 +-------------------------------+--------------+----------------------+ 5211 | Propagation_delay_default | 0.5 secs | Expected | 5212 | | | propagation delay | 5213 | | | over the local | 5214 | | | link. | 5215 +-------------------------------+--------------+----------------------+ 5217 The default value of the Propagation_delay_default is chosen to be 5218 relatively large to provide compatibility with older PIM 5219 implementations. 5221 Variable Name: Override_Interval(I) 5223 +--------------------------+-----------------+-------------------------+ 5224 | Value Name | Value | Explanation | 5225 +--------------------------+-----------------+-------------------------+ 5226 | t_override_default | 2.5 secs | Default delay | 5227 | | | interval over | 5228 | | | which to randomize | 5229 | | | when scheduling a | 5230 | | | delayed Join | 5231 | | | message. | 5232 +--------------------------+-----------------+-------------------------+ 5234 Timer Name: Hello Timer (HT(I)) 5236 +---------------------+--------+---------------------------------------+ 5237 |Value Name | Value | Explanation | 5238 +---------------------+--------+---------------------------------------+ 5239 |Hello_Period | 30 secs| Periodic interval for Hello messages. | 5240 +---------------------+--------+---------------------------------------+ 5241 |Triggered_Hello_Delay| 5 secs | Randomized interval for initial Hello | 5242 | | | message on bootup or triggered Hello | 5243 | | | message to a rebooting neighbor. | 5244 +---------------------+--------+---------------------------------------+ 5246 At system power-up, the timer is initialized to rand(0, 5247 Triggered_Hello_Delay) to prevent synchronization. When a new or 5248 rebooting neighbor is detected, a responding Hello is sent within 5249 rand(0, Triggered_Hello_Delay). 5251 Timer Name: Neighbor Liveness Timer (NLT(N,I)) 5253 +--------------------------+----------------------+--------------------+ 5254 | Value Name | Value | Explanation | 5255 +--------------------------+----------------------+--------------------+ 5256 | Default_Hello_Holdtime | 3.5 * Hello_Period | Default holdtime | 5257 | | | to keep neighbor | 5258 | | | state alive | 5259 +--------------------------+----------------------+--------------------+ 5260 | Hello_Holdtime | from message | Holdtime from | 5261 | | | Hello Message | 5262 | | | Holdtime option. | 5263 +--------------------------+----------------------+--------------------+ 5265 The Holdtime in a Hello Message should be set to (3.5 * 5266 Hello_Period), giving a default value of 105 seconds. 5268 Timer Names: Expiry Timer (ET(*,G,I), ET(S,G,I), ET(S,G,rpt,I)) 5270 +----------------+----------------+------------------------------------+ 5271 | Value Name | Value | Explanation | 5272 +----------------+----------------+------------------------------------+ 5273 | J/P_HoldTime | from message | Holdtime from Join/Prune Message | 5274 +----------------+----------------+------------------------------------+ 5276 See details of JT(*,G) for the Holdtime that is included in 5277 Join/Prune Messages. 5279 Timer Names: Prune-Pending Timer (PPT(*,G,I), PPT(S,G,I), 5280 PPT(S,G,rpt,I)) 5282 +--------------------------+---------------------+---------------------+ 5283 |Value Name | Value | Explanation | 5284 +--------------------------+---------------------+---------------------+ 5285 |J/P_Override_Interval(I) | Default: | Short period after | 5286 | | Effective_ | a join or prune to | 5287 | | Propagation_ | allow other | 5288 | | Delay(I) + | routers on the LAN | 5289 | | EffectiveOverride_ | to override the | 5290 | | Interval(I) | join or prune | 5291 +--------------------------+---------------------+---------------------+ 5293 Note that both the Effective_Propagation_Delay(I) and the 5294 Effective_Override_Interval(I) are interface-specific values that may 5295 change when Hello messages are received (see Section 4.3.3). 5297 Timer Names: Assert Timer (AT(*,G,I), AT(S,G,I)) 5299 +---------------------------+---------------------+--------------------+ 5300 | Value Name | Value | Explanation | 5301 +---------------------------+---------------------+--------------------+ 5302 | Assert_Override_Interval | Default: 3 secs | Short interval | 5303 | | | before an assert | 5304 | | | times out where | 5305 | | | the assert winner | 5306 | | | resends an Assert | 5307 | | | message | 5308 +---------------------------+---------------------+--------------------+ 5309 | Assert_Time | Default: 180 secs | Period after last | 5310 | | | assert before | 5311 | | | assert state is | 5312 | | | timed out | 5313 +---------------------------+---------------------+--------------------+ 5315 Note that for historical reasons, the Assert message lacks a Holdtime 5316 field. Thus, changing the Assert Time from the default value is not 5317 recommended. 5319 Timer Names: Upstream Join Timer (JT(*,G), JT(S,G)) 5321 +-------------+--------------------+-----------------------------------+ 5322 |Value Name | Value | Explanation | 5323 +-------------+--------------------+-----------------------------------+ 5324 |t_periodic | Default: 60 secs | Period between Join/Prune Messages| 5325 +-------------+--------------------+-----------------------------------+ 5326 |t_suppressed | rand(1.1 * | Suppression period when someone | 5327 | | t_periodic, 1.4 * | else sends a J/P message so we | 5328 | | t_periodic) when | don't need to do so. | 5329 | | Suppression_ | | 5330 | | Enabled(I) is | | 5331 | | true, 0 otherwise | | 5332 +-------------+--------------------+-----------------------------------+ 5333 |t_override | rand(0, Effective_ | Randomized delay to prevent | 5334 | | Override_ | response implosion when sending a | 5335 | | Interval(I)) | join message to override someone | 5336 | | | else's Prune message. | 5337 +-------------+--------------------+-----------------------------------+ 5339 t_periodic may be set to take into account such things as the 5340 configured bandwidth and expected average number of multicast route 5341 entries for the attached network or link (e.g., the period would be 5342 longer for lower-speed links, or for routers in the center of the 5343 network that expect to have a larger number of entries). If the 5344 Join/Prune-Period is modified during operation, these changes should 5345 be made relatively infrequently, and the router should continue to 5346 refresh at its previous Join/Prune-Period for at least Join/Prune- 5347 Holdtime, in order to allow the upstream router to adapt. 5349 The holdtime specified in a Join/Prune message should be set to (3.5 5350 * t_periodic). 5352 t_override depends on the Effective Override Interval of the upstream 5353 interface, which may change when Hello messages are received. 5355 t_suppressed depends on the Suppression State of the upstream 5356 interface (Section 4.3.3) and becomes zero when suppression is 5357 disabled. 5359 Timer Name: Upstream Override Timer (OT(S,G,rpt)) 5361 +---------------+--------------------------+---------------------------+ 5362 | Value Name | Value | Explanation | 5363 +---------------+--------------------------+---------------------------+ 5364 | t_override | see Upstream Join Timer | see Upstream Join Timer | 5365 +---------------+--------------------------+---------------------------+ 5367 The upstream Override Timer is only ever set to t_override; this 5368 value is defined in the section on Upstream Join Timers. 5370 Timer Name: Keepalive Timer (KAT(S,G)) 5372 +-----------------------+-----------------------+----------------------+ 5373 | Value Name | Value | Explanation | 5374 +-----------------------+-----------------------+----------------------+ 5375 | Keepalive_Period | Default: 210 secs | Period after last | 5376 | | | (S,G) data packet | 5377 | | | during which (S,G) | 5378 | | | Join state will be | 5379 | | | maintained even in | 5380 | | | the absence of | 5381 | | | (S,G) Join | 5382 | | | messages. | 5383 +-----------------------+-----------------------+----------------------+ 5384 | RP_Keepalive_Period | ( 3 * Register_ | As | 5385 | | Suppression_Time ) | Keepalive_Period, | 5386 | | + Register_ | but at the RP when | 5387 | | Probe_Time | a Register-Stop is | 5388 | | | sent. | 5389 +-----------------------+-----------------------+----------------------+ 5391 The normal keepalive period for the KAT(S,G) defaults to 210 seconds. 5392 However, at the RP, the keepalive period must be at least the 5393 Register_Suppression_Time, or the RP may time out the (S,G) state 5394 before the next Null-Register arrives. Thus, the KAT(S,G) is set to 5395 max(Keepalive_Period, RP_Keepalive_Period) when a Register-Stop is 5396 sent. 5398 Timer Name: Register-Stop Timer (RST(S,G)) 5400 +---------------------------+--------------------+---------------------+ 5401 |Value Name | Value | Explanation | 5402 +---------------------------+--------------------+---------------------+ 5403 |Register_Suppression_Time | Default: 60 secs | Period during | 5404 | | | which a DR stops | 5405 | | | sending Register- | 5406 | | | encapsulated data | 5407 | | | to the RP after | 5408 | | | receiving a | 5409 | | | Register-Stop | 5410 | | | message. | 5411 +---------------------------+--------------------+---------------------+ 5412 |Register_Probe_Time | Default: 5 secs | Time before RST | 5413 | | | expires when a DR | 5414 | | | may send a Null- | 5415 | | | Register to the RP | 5416 | | | to cause it to | 5417 | | | resend a Register- | 5418 | | | Stop message. | 5419 +---------------------------+--------------------+---------------------+ 5421 If the Register_Suppression_Time or the Register_Probe_Time are 5422 configured to values other than the defaults, it MUST be ensured that 5423 the value of the Register_Probe_Time is less than half the value of 5424 the Register_Suppression_Time to prevent a possible negative value in 5425 the setting of the Register-Stop Timer. 5427 5. IANA Considerations 5429 5.1. PIM Address Family 5431 The PIM Address Family field was chosen to be 8 bits as a tradeoff 5432 between packet format and use of the IANA assigned numbers. Because 5433 when the PIM packet format was designed only 15 values were assigned 5434 for Address Families, and large numbers of new Address Family values 5435 were not envisioned, 8 bits seemed large enough. However, the IANA 5436 assigns Address Families in a 16-bit field. Therefore, the PIM 5437 Address Family is allocated as follows: 5439 Values 0 through 127 are designated to have the same meaning as 5440 IANA-assigned Address Family Numbers [7]. 5442 Values 128 through 250 are designated to be assigned for PIM by the 5443 IANA based upon IESG Approval, as defined in [9]. 5445 Values 251 through 255 are designated for Private Use, as defined 5446 in [9]. 5448 5.2. PIM Hello Options 5450 Values 17 through 65000 are to be assigned by the IANA. Since the 5451 space is large, they may be assigned as First Come First Served as 5452 defined in [9]. Such assignments are valid for one year and may be 5453 renewed. Permanent assignments require a specification (see 5454 "Specification Required" in [9].) 5456 6. Security Considerations 5458 This section describes various possible security concerns related to 5459 the PIM-SM protocol, including a description of how to use IPsec to 5460 secure the protocol. The reader is referred to [15] and [16] for 5461 further discussion of PIM-SM and multicast security. The IPsec 5462 authentication header [8] MAY be used to provide data integrity 5463 protection and groupwise data origin authentication of PIM protocol 5464 messages. Authentication of PIM messages can protect against unwanted 5465 behaviors caused by unauthorized or altered PIM messages. 5467 Note that PIM relies upon an MRIB populated outside of PIM so 5468 securing the sources of change to the MRIB is RECOMMENDED. 5470 6.1. Attacks Based on Forged Messages 5472 The extent of possible damage depends on the type of counterfeit 5473 messages accepted. We next consider the impact of possible 5474 forgeries, including forged link-local (Join/Prune, Hello, and 5475 Assert) and forged unicast (Register and Register-Stop) messages. 5477 6.1.1. Forged Link-Local Messages 5479 Join/Prune, Hello, and Assert messages are all sent to the link-local 5480 ALL_PIM_ROUTERS multicast addresses and thus are not forwarded by a 5481 compliant router. A forged message of this type can only reach a LAN 5482 if it was sent by a local host or if it was allowed onto the LAN by a 5483 compromised or non-compliant router. 5485 1. A forged Join/Prune message can cause multicast traffic to be 5486 delivered to links where there are no legitimate requesters, 5487 potentially wasting bandwidth on that link. A forged leave 5488 message on a multi-access LAN is generally not a significant 5489 attack in PIM, because any legitimately joined router on the LAN 5490 would override the leave with a join before the upstream router 5491 stops forwarding data to the LAN. 5493 2. By forging a Hello message, an unauthorized router can cause 5494 itself to be elected as the designated router on a LAN. The 5495 designated router on a LAN is (in the absence of asserts) 5496 responsible for forwarding traffic to that LAN on behalf of any 5497 local members. The designated router is also responsible for 5498 register-encapsulating to the RP any packets that are originated 5499 by hosts on the LAN. Thus, the ability of local hosts to send 5500 and receive multicast traffic may be compromised by a forged 5501 Hello message. 5503 3. By forging an Assert message on a multi-access LAN, an attacker 5504 could cause the legitimate designated forwarder to stop 5505 forwarding traffic to the LAN. Such a forgery would prevent any 5506 hosts downstream of that LAN from receiving traffic. 5508 6.1.2. Forged Unicast Messages 5510 Register messages and Register-Stop messages are forwarded by 5511 intermediate routers to their destination using normal IP forwarding. 5512 Without data origin authentication, an attacker who is located 5513 anywhere in the network may be able to forge a Register or Register- 5514 Stop message. We consider the effect of a forgery of each of these 5515 messages next. 5517 1. By forging a Register message, an attacker can cause the RP to 5518 inject forged traffic onto the shared multicast tree. 5520 2. By forging a Register-stop message, an attacker can prevent a 5521 legitimate DR from Registering packets to the RP. This can 5522 prevent local hosts on that LAN from sending multicast packets. 5524 The above two PIM messages are not changed by intermediate routers 5525 and need only be examined by the intended receiver. Thus, these 5526 messages can be authenticated end-to-end, using AH. Attacks on 5527 Register and Register-Stop messages do not apply to a PIM-SSM-only 5528 implementation, as these messages are not required for PIM-SSM. 5530 6.2. Non-Cryptographic Authentication Mechanisms 5532 A PIM router SHOULD provide an option to limit the set of neighbors 5533 from which it will accept Join/Prune, Assert, and Hello messages. 5534 Either static configuration of IP addresses or an IPsec security 5535 association MAY be used. Furthermore, a PIM router SHOULD NOT accept 5536 protocol messages from a router from which it has not yet received a 5537 valid Hello message. 5539 A Designated Router MUST NOT register-encapsulate a packet and send 5540 it to the RP unless the source address of the packet is a legal 5541 address for the subnet on which the packet was received. Similarly, 5542 a Designated Router SHOULD NOT accept a Register-Stop packet whose IP 5543 source address is not a valid RP address for the local domain. 5545 An implementation SHOULD provide a mechanism to allow an RP to 5546 restrict the range of source addresses from which it accepts 5547 Register-encapsulated packets. 5549 All options that restrict the range of addresses from which packets 5550 are accepted MUST default to allowing all packets. 5552 6.3. Authentication Using IPsec 5554 The IPsec [8] transport mode using the Authentication Header (AH) is 5555 the recommended method to prevent the above attacks against PIM. The 5556 specific AH authentication algorithm and parameters, including the 5557 choice of authentication algorithm and the choice of key, are 5558 configured by the network administrator. When IPsec authentication 5559 is used, a PIM router should reject (drop without processing) any 5560 unauthorized PIM protocol messages. 5562 To use IPsec, the administrator of a PIM network configures each PIM 5563 router with one or more security associations (SAs) and associated 5564 Security Parameter Indexes (SPIs) that are used by senders to 5565 authenticate PIM protocol messages and are used by receivers to 5566 authenticate received PIM protocol messages. This document does not 5567 describe protocols for establishing SAs. It assumes that manual 5568 configuration of SAs is performed, but it does not preclude the use 5569 of a negotiation protocol such as the Internet Key Exchange [14] to 5570 establish SAs. 5572 IPsec [8] provides protection against replayed unicast and multicast 5573 messages. The anti-replay option for IPsec SHOULD be enabled on all 5574 SAs. 5576 The following sections describe the SAs required to protect PIM 5577 protocol messages. 5579 6.3.1. Protecting Link-Local Multicast Messages 5581 The network administrator defines an SA and SPI that are to be used 5582 to authenticate all link-local PIM protocol messages (Hello, 5583 Join/Prune, and Assert) on each link in a PIM domain. 5585 IPsec [8] allows (but does not require) different Security Policy 5586 Databases (SPD) for each router interface. If available, it may be 5587 desirable to configure the Security Policy Database at a PIM router 5588 such that all incoming and outgoing Join/Prune, Assert, and Hello 5589 packets use a different SA for each incoming or outgoing interface. 5591 6.3.2. Protecting Unicast Messages 5593 IPsec can also be used to provide data origin authentication and data 5594 integrity protection for the Register and Register-Stop unicast 5595 messages. 5597 6.3.2.1. Register Messages 5599 The Security Policy Database at every PIM router is configured to 5600 select an SA to use when sending PIM Register packets to each 5601 rendezvous point. 5603 In the most general mode of operation, the Security Policy Database 5604 at each DR is configured to select a unique SA and SPI for traffic 5605 sent to each RP. This allows each DR to have a different 5606 authentication algorithm and key to talk to the RP. However, this 5607 creates a daunting key management and distribution problem for the 5608 network administrator. Therefore, it may be preferable in PIM domains 5609 where all Designated Routers are under a single administrative 5610 control that the same authentication algorithm parameters (including 5611 the key) be used for all Registered packets in a domain, regardless 5612 of who are the RP and the DR. 5614 In this "single shared key" mode of operation, the network 5615 administrator must choose an SPI for each DR that will be used to 5616 send the PIM protocol packets. The Security Policy Database at every 5617 DR is configured to select an SA (including the authentication 5618 algorithm, authentication parameters, and this SPI) when sending 5619 Register messages to the RP. 5621 By using a single authentication algorithm and associated parameters, 5622 the key distribution problem is simplified. Note, however, that this 5623 method has the property that, in order to change the authentication 5624 method or authentication key used, all routers in the domain must be 5625 updated. 5627 6.3.2.2. Register-Stop Messages 5629 Similarly, the Security Policy Database at each Rendezvous Point 5630 should be configured to choose an SA to use when sending Register- 5631 Stop messages. Because Register-Stop messages are unicast to the 5632 destination DR, a different SA and a potentially unique SPI are 5633 required for each DR. 5635 In order to simplify the management problem, it may be acceptable to 5636 use the same authentication algorithm and authentication parameters, 5637 regardless of the sending RP and regardless of the destination DR. 5638 Although a unique SA is needed for each DR, the same authentication 5639 algorithm and authentication algorithm parameters (secret key) can be 5640 shared by all DRs and by all RPs. 5642 6.4. Denial-of-Service Attacks 5644 There are a number of possible denial-of-service attacks against PIM 5645 that can be caused by generating false PIM protocol messages or even 5646 by generating false traffic. Authenticating PIM protocol traffic 5647 prevents some, but not all, of these attacks. Three of the possible 5648 attacks include: 5650 - Sending packets to many different group addresses quickly can be a 5651 denial-of-service attack in and of itself. This will cause many 5652 register-encapsulated packets, loading the DR, the RP, and the 5653 routers between the DR and the RP. 5655 - Forging Join messages can cause a multicast tree to get set up. A 5656 large number of forged joins can consume router resources and 5657 result in denial of service. 5659 7. Acknowledgements 5661 PIM-SM was designed over many years by a large group of people, 5662 including ideas, comments, and corrections from Deborah Estrin, Dino 5663 Farinacci, Ahmed Helmy, David Thaler, Steve Deering, Van Jacobson, C. 5664 Liu, Puneet Sharma, Liming Wei, Tom Pusateri, Tony Ballardie, Scott 5665 Brim, Jon Crowcroft, Paul Francis, Joel Halpern, Horst Hodel, Polly 5666 Huang, Stephen Ostrowski, Lixia Zhang, Girish Chandranmenon, Brian 5667 Haberman, Hal Sandick, Mike Mroz, Garry Kump, Pavlin Radoslavov, Mike 5668 Davison, James Huang, Christopher Thomas Brown, and James Lingard. 5670 Thanks are due to the American Licorice Company, for its obscure but 5671 possibly essential role in the creation of this document. 5673 8. Normative References 5675 [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement 5676 Levels", BCP 14, RFC 2119, March 1997. 5678 [2] Cain, B., Deering, S., Kouvelas, I., Fenner, B., and A. 5679 Thyagarajan, "Internet Group Management Protocol, Version 3", 5680 RFC 3376, October 2002. 5682 [3] Deering, S., "Host extensions for IP multicasting", STD 5, RFC 5683 1112, August 1989. 5685 [4] Deering, S., Fenner, W., and B. Haberman, "Multicast Listener 5686 Discovery (MLD) for IPv6", RFC 2710, October 1999. 5688 [5] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) 5689 Specification", RFC 2460, December 1998. 5691 [6] Holbrook, H. and B. Cain, "Source-Specific Multicast for IP", 5692 RFC 4607, August 2006. 5694 [7] IANA, "Address Family Numbers", 5695 . 5697 [8] Kent, S. and K. Seo, "Security Architecture for the Internet 5698 Protocol", RFC 4301, December 2005. 5700 [9] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA 5701 Considerations Section in RFCs", BCP 26, RFC 5226, May 2008. 5703 9. Informative References 5705 [10] Bates, T., Rekhter, Y., Chandra, R., and D. Katz, "Multiprotocol 5706 Extensions for BGP-4", RFC 4760, January 2007. 5708 [11] Bhaskar, N., Gall, A., Lingard, J., and S. Venaas, "Bootstrap 5709 Router (BSR) Mechanism for Protocol Independent Multicast 5710 (PIM)", RFC 5059, January 2008. 5712 [12] Black, D., "Differentiated Services and Tunnels", RFC 2983, 5713 October 2000. 5715 [13] Handley, M., Kouvelas, I., Speakman, T., and L. Vicisano, 5716 "Bidirectional Protocol Independent Multicast" (BIDIR-PIM), RFC 5717 5015, October 2007. 5719 [14] Kaufman, C., Hoffman, P., Nir, Y., and P. Eronen, "Internet Key 5720 Exchange (IKEv2) Protocol", RFC 5996, September 2010. 5722 [15] Savola, P., Lehtonen, R., and D. Meyer, "Protocol Independent 5723 Multicast - Sparse Mode (PIM-SM) Multicast Routing Security 5724 Issues and Enhancements", RFC 4609, August 2006. 5726 [16] Savola, P. and J. Lingard, "Host Threats to Protocol Independent 5727 Multicast (PIM)", RFC 5294, August 2008. 5729 [17] Savola, P. and B. Haberman, "Embedding the Rendezvous Point (RP) 5730 Address in an IPv6 Multicast Address", RFC 3956, November 2004. 5732 [18] Zheng, L., Zhang, Z. and R. Parekh, "Survey Report on Protocol 5733 Independent Multicast - Sparse Mode (PIM-SM) Implementations and 5734 Deployments", RFC 7063, December 2013. 5736 Appendix A. Functionality removed from RFC 4601 5738 Based on a survey of PIM implementations and deployments [18], 5739 conducted by IETF PIM working group, the following functionality of 5740 RFC 4601 has been removed due to lack of sufficient implementation 5741 and deployment experience. 5743 o (*,*,RP) State 5744 o PIM Multicast Border Router (PMBR) 5746 Authors' Addresses 5748 Bill Fenner 5749 AT&T Labs - Research 5750 1 River Oaks Place 5751 San Jose, CA 95134 5753 EMail: fenner@research.att.com 5755 Mark Handley 5756 Department of Computer Science 5757 University College London 5758 Gower Street 5759 London WC1E 6BT 5760 United Kingdom 5762 EMail: M.Handley@cs.ucl.ac.uk 5764 Hugh Holbrook 5765 Arastra, Inc. 5766 P.O. Box 10905 5767 Palo Alto, CA 94303 5769 EMail: holbrook@arastra.com 5771 Isidor Kouvelas 5772 Cisco Systems, Inc. 5773 170 W. Tasman Drive 5774 San Jose, CA 95134 5776 EMail: kouvelas@cisco.com 5778 Rishabh Parekh 5779 Cisco Systems, Inc. 5780 170 W. Tasman Drive 5781 San Jose, CA 95134 5783 EMail: riparekh@cisco.com 5784 Zhaohui (Jeffrey) Zhang 5785 Juniper Networks 5786 10 Technology Park Drive 5787 Westford, MA 01886 5789 Email: zzhang@juniper.net 5791 Lianshu Zheng 5792 Huawei Technologies Co., Ltd 5793 No. 3 Xinxi Road, Shang-di, Hai-dian District 5794 Beijing 100085 5795 China 5797 Email: verozheng@huawei.com