idnits 2.17.1 draft-ietf-pim-rfc4601bis-02.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 (October 17, 2013) is 3838 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 3595 -- Looks like a reference, but probably isn't: 'Actions A6' on line 3239 -- Looks like a reference, but probably isn't: 'Actions A3' on line 3606 -- Looks like a reference, but probably isn't: 'Actions A2' on line 3606 -- Looks like a reference, but probably isn't: 'Actions A4' on line 3606 -- Looks like a reference, but probably isn't: 'Actions A5' on line 3632 ** 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: April 20, 2014 UCL 6 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 October 17, 2013 17 Protocol Independent Multicast - Sparse Mode (PIM-SM): 18 Protocol Specification (Revised) 20 draft-ietf-pim-rfc4601bis-02 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 April 29, 2012. 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 addresses errata filed against RFC 4601, and removes 49 the optional (*,*,RP) feature that lacks sufficient deployment 50 experience. 52 Copyright Notice 54 Copyright (c) 2013 IETF Trust and the persons identified as the 55 document authors. All rights reserved. 57 This document is subject to BCP 78 and the IETF Trust's Legal 58 Provisions Relating to IETF Documents 59 (http://trustee.ietf.org/license-info) in effect on the date of 60 publication of this document. Please review these documents 61 carefully, as they describe your rights and restrictions with respect 62 to this document. Code Components extracted from this document must 63 include Simplified BSD License text as described in Section 4.e of 64 the Trust Legal Provisions and are provided without warranty as 65 described in the Simplified BSD License. 67 Table of Contents 69 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 6 70 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 6 71 2.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . 6 72 2.2. Pseudocode Notation . . . . . . . . . . . . . . . . . . . 7 73 3. PIM-SM Protocol Overview . . . . . . . . . . . . . . . . . . . 8 74 3.1. Phase One: RP Tree . . . . . . . . . . . . . . . . . . . . 8 75 3.2. Phase Two: Register-Stop . . . . . . . . . . . . . . . . . 9 76 3.3. Phase Three: Shortest-Path Tree . . . . . . . . . . . . . 10 77 3.4. Source-Specific Joins . . . . . . . . . . . . . . . . . . 11 78 3.5. Source-Specific Prunes . . . . . . . . . . . . . . . . . . 11 79 3.6. Multi-Access Transit LANs . . . . . . . . . . . . . . . . 12 80 3.7. RP Discovery . . . . . . . . . . . . . . . . . . . . . . . 12 81 4. Protocol Specification . . . . . . . . . . . . . . . . . . . . 13 82 4.1. PIM Protocol State . . . . . . . . . . . . . . . . . . . . 14 83 4.1.1. General Purpose State . . . . . . . . . . . . . . . . 15 84 4.1.2. (*,G) State . . . . . . . . . . . . . . . . . . . . . 16 85 4.1.3. (S,G) State . . . . . . . . . . . . . . . . . . . . . 17 86 4.1.4. (S,G,rpt) State . . . . . . . . . . . . . . . . . . . 20 87 4.1.5. State Summarization Macros . . . . . . . . . . . . . . 21 88 4.2. Data Packet Forwarding Rules . . . . . . . . . . . . . . . 25 89 4.2.1. Last-Hop Switchover to the SPT . . . . . . . . . . . . 27 90 4.2.2. Setting and Clearing the (S,G) SPTbit . . . . . . . . 28 91 4.3. Designated Routers (DR) and Hello Messages . . . . . . . . 29 92 4.3.1. Sending Hello Messages . . . . . . . . . . . . . . . . 29 93 4.3.2. DR Election . . . . . . . . . . . . . . . . . . . . . 31 94 4.3.3. Reducing Prune Propagation Delay on LANs . . . . . . . 33 95 4.3.4. Maintaining Secondary Address Lists . . . . . . . . . 36 96 4.4. PIM Register Messages . . . . . . . . . . . . . . . . . . 37 97 4.4.1. Sending Register Messages from the DR . . . . . . . . 37 98 4.4.2. Receiving Register Messages at the RP . . . . . . . . 41 99 4.5. PIM Join/Prune Messages . . . . . . . . . . . . . . . . . 43 100 4.5.1. Receiving (*,G) Join/Prune Messages . . . . . . . . . 43 101 4.5.2. Receiving (S,G) Join/Prune Messages . . . . . . . . . 48 102 4.5.3. Receiving (S,G,rpt) Join/Prune Messages . . . . . . . 51 103 4.5.4. Sending (*,G) Join/Prune Messages . . . . . . . . . . 56 104 4.5.5. Sending (S,G) Join/Prune Messages . . . . . . . . . . 61 105 4.5.6. (S,G,rpt) Periodic Messages . . . . . . . . . . . . . 66 106 4.5.7. State Machine for (S,G,rpt) Triggered Messages . . . . 67 107 4.6. PIM Assert Messages . . . . . . . . . . . . . . . . . . . 71 108 4.6.1. (S,G) Assert Message State Machine . . . . . . . . . . 72 109 4.6.2. (*,G) Assert Message State Machine . . . . . . . . . . 79 110 4.6.3. Assert Metrics . . . . . . . . . . . . . . . . . . . . 85 111 4.6.4. AssertCancel Messages . . . . . . . . . . . . . . . . 87 112 4.6.5. Assert State Macros . . . . . . . . . . . . . . . . . 87 113 4.7. PIM Bootstrap and RP Discovery . . . . . . . . . . . . . . 91 114 4.7.1. Group-to-RP Mapping . . . . . . . . . . . . . . . . . 92 115 4.7.2. Hash Function . . . . . . . . . . . . . . . . . . . . 93 116 4.8. Source-Specific Multicast . . . . . . . . . . . . . . . . 94 117 4.8.1. Protocol Modifications for SSM Destination Addresses . 94 118 4.8.2. PIM-SSM-Only Routers . . . . . . . . . . . . . . . . . 95 119 4.9. PIM Packet Formats . . . . . . . . . . . . . . . . . . . . 96 120 4.9.1. Encoded Source and Group Address Formats . . . . . . . 98 121 4.9.2. Hello Message Format . . . . . . . . . . . . . . . . .101 122 4.9.3. Register Message Format . . . . . . . . . . . . . . .105 123 4.9.4. Register-Stop Message Format . . . . . . . . . . . . .108 124 4.9.5. Join/Prune Message Format . . . . . . . . . . . . . .108 125 4.9.5.1. Group Set Source List Rules . . . . . . . . . . .111 126 4.9.5.2. Group Set Fragmentation . . . . . . . . . . . . .114 127 4.9.6. Assert Message Format . . . . . . . . . . . . . . . .115 128 4.10. PIM Timers . . . . . . . . . . . . . . . . . . . . . . .116 129 4.11. Timer Values . . . . . . . . . . . . . . . . . . . . . .118 130 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . .123 131 5.1. PIM Address Family . . . . . . . . . . . . . . . . . . . .123 132 5.2. PIM Hello Options . . . . . . . . . . . . . . . . . . . .124 133 6. Security Considerations . . . . . . . . . . . . . . . . . . .124 134 6.1. Attacks Based on Forged Messages . . . . . . . . . . . . .124 135 6.1.1. Forged Link-Local Messages . . . . . . . . . . . . . .124 136 6.1.2. Forged Unicast Messages . . . . . . . . . . . . . . .125 137 6.2. Non-Cryptographic Authentication Mechanisms . . . . . . .125 138 6.3. Authentication Using IPsec . . . . . . . . . . . . . . . .126 139 6.3.1. Protecting Link-Local Multicast Messages . . . . . . .126 140 6.3.2. Protecting Unicast Messages . . . . . . . . . . . . .127 141 6.3.2.1. Register Messages . . . . . . . . . . . . . . . .127 142 6.3.2.2. Register-Stop Messages . . . . . . . . . . . . . .127 143 6.4. Denial-of-Service Attacks . . . . . . . . . . . . . . . .128 144 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . .128 145 8. Normative References . . . . . . . . . . . . . . . . . . . . .129 146 9. Informative References . . . . . . . . . . . . . . . . . . . .129 147 Appendix A. Functionality removed from RFC 4601 . . . . . . . . .131 148 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . .132 150 List of Figures 152 Figure 1. Per-(S,G) register state machine at a DR ................38 153 Figure 2. Downstream per-interface (*,G) state machine ............45 154 Figure 3. Downstream per-interface (S,G) state machine ............49 155 Figure 4. Downstream per-interface (S,G,rpt) state machine ........53 156 Figure 5. Upstream (*,G) state machine ............................58 157 Figure 6. Upstream (S,G) state machine ............................62 158 Figure 7. Upstream (S,G,rpt) state machine for triggered 159 messages ................................................67 160 Figure 8. Per-interface (S,G) Assert State machine ................72 161 Figure 9. Per-interface (*,G) Assert State machine ................80 163 1. Introduction 165 This document specifies a protocol for efficiently routing multicast 166 groups that may span wide-area (and inter-domain) internets. This 167 protocol is called Protocol Independent Multicast - Sparse Mode 168 (PIM-SM) because, although it may use the underlying unicast routing 169 to provide reverse-path information for multicast tree building, it 170 is not dependent on any particular unicast routing protocol. 172 PIM-SM version 2 was specified in RFC 4601 as a Proposed Standard. 173 This document is intended to address the reported errata and to 174 remove the optional (*,*,RP) feature that lacks sufficient deployment 175 experience, to advance PIM-SM to Draft Standard. 177 This document specifies the same protocol as RFC 4601 and 178 implementations per the specification in this document will be able 179 to interoperate successfully with implementations per RFC 4601. 181 2. Terminology 183 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 184 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 185 document are to be interpreted as described in RFC 2119 [1]. 187 2.1. Definitions 189 The following terms have special significance for PIM-SM: 191 Rendezvous Point (RP): 192 An RP is a router that has been configured to be used as the 193 root of the non-source-specific distribution tree for a 194 multicast group. Join messages from receivers for a group are 195 sent towards the RP, and data from senders is sent to the RP so 196 that receivers can discover who the senders are and start to 197 receive traffic destined for the group. 199 Designated Router (DR): 200 A shared-media LAN like Ethernet may have multiple PIM-SM 201 routers connected to it. A single one of these routers, the 202 DR, will act on behalf of directly connected hosts with respect 203 to the PIM-SM protocol. A single DR is elected per interface 204 (LAN or otherwise) using a simple election process. 206 MRIB Multicast Routing Information Base. This is the multicast 207 topology table, which is typically derived from the unicast 208 routing table, or routing protocols such as Multiprotocol BGP 209 (MBGP) that carry multicast-specific topology information. In 210 PIM-SM, the MRIB is used to decide where to send Join/Prune 211 messages. A secondary function of the MRIB is to provide 212 routing metrics for destination addresses; these metrics are 213 used when sending and processing Assert messages. 215 RPF Neighbor 216 RPF stands for "Reverse Path Forwarding". The RPF Neighbor of 217 a router with respect to an address is the neighbor that the 218 MRIB indicates should be used to forward packets to that 219 address. In the case of a PIM-SM multicast group, the RPF 220 neighbor is the router that a Join message for that group would 221 be directed to, in the absence of modifying Assert state. 223 TIB Tree Information Base. This is the collection of state at a 224 PIM router that has been created by receiving PIM Join/Prune 225 messages, PIM Assert messages, and Internet Group Management 226 Protocol (IGMP) or Multicast Listener Discovery (MLD) 227 information from local hosts. It essentially stores the state 228 of all multicast distribution trees at that router. 230 MFIB Multicast Forwarding Information Base. The TIB holds all the 231 state that is necessary to forward multicast packets at a 232 router. However, although this specification defines forwarding 233 in terms of the TIB, to actually forward packets using the TIB 234 is very inefficient. Instead, a real router implementation 235 will normally build an efficient MFIB from the TIB state to 236 perform forwarding. How this is done is implementation-specific 237 and is not discussed in this document. 239 Upstream 240 Towards the root of the tree. The root of the tree may be 241 either the source or the RP, depending on the context. 243 Downstream 244 Away from the root of the tree. 246 GenID Generation Identifier, used to detect reboots. 248 2.2. Pseudocode Notation 250 We use set notation in several places in this specification. 252 A (+) B is the union of two sets, A and B. 254 A (-) B is the elements of set A that are not in set B. 256 NULL is the empty set or list. 258 In addition, we use C-like syntax: 260 = denotes assignment of a variable. 262 == denotes a comparison for equality. 264 != denotes a comparison for inequality. 266 Braces { and } are used for grouping. 268 Unless otherwise noted, operations specified by statements having 269 multiple (+) and (-) operators should be evaluated from left to 270 right, i.e. A (+) B (-) C is the set resulting from union of sets A 271 and B minus elements in set C. 273 3. PIM-SM Protocol Overview 275 This section provides an overview of PIM-SM behavior. It is intended 276 as an introduction to how PIM-SM works, and it is NOT definitive. 277 For the definitive specification, see Section 4. 279 PIM relies on an underlying topology-gathering protocol to populate a 280 routing table with routes. This routing table is called the 281 Multicast Routing Information Base (MRIB). The routes in this table 282 may be taken directly from the unicast routing table, or they may be 283 different and provided by a separate routing protocol such as MBGP 284 [10]. Regardless of how it is created, the primary role of the MRIB 285 in the PIM protocol is to provide the next-hop router along a 286 multicast-capable path to each destination subnet. The MRIB is used 287 to determine the next-hop neighbor to which any PIM Join/Prune 288 message is sent. Data flows along the reverse path of the Join 289 messages. Thus, in contrast to the unicast RIB, which specifies the 290 next hop that a data packet would take to get to some subnet, the 291 MRIB gives reverse-path information and indicates the path that a 292 multicast data packet would take from its origin subnet to the router 293 that has the MRIB. 295 Like all multicast routing protocols that implement the service model 296 from RFC 1112 [3], PIM-SM must be able to route data packets from 297 sources to receivers without either the sources or receivers knowing 298 a priori of the existence of the others. This is essentially done in 299 three phases, although as senders and receivers may come and go at 300 any time, all three phases may occur simultaneously. 302 3.1. Phase One: RP Tree 304 In phase one, a multicast receiver expresses its interest in 305 receiving traffic destined for a multicast group. Typically, it does 306 this using IGMP [2] or MLD [4], but other mechanisms might also serve 307 this purpose. One of the receiver's local routers is elected as the 308 Designated Router (DR) for that subnet. On receiving the receiver's 309 expression of interest, the DR then sends a PIM Join message towards 310 the RP for that multicast group. This Join message is known as a 311 (*,G) Join because it joins group G for all sources to that group. 312 The (*,G) Join travels hop-by-hop towards the RP for the group, and 313 in each router it passes through, multicast tree state for group G is 314 instantiated. Eventually, the (*,G) Join either reaches the RP or 315 reaches a router that already has (*,G) Join state for that group. 316 When many receivers join the group, their Join messages converge on 317 the RP and form a distribution tree for group G that is rooted at the 318 RP. This is known as the RP Tree (RPT), and is also known as the 319 shared tree because it is shared by all sources sending to that 320 group. Join messages are resent periodically so long as the receiver 321 remains in the group. When all receivers on a leaf-network leave the 322 group, the DR will send a PIM (*,G) Prune message towards the RP for 323 that multicast group. However, if the Prune message is not sent for 324 any reason, the state will eventually time out. 326 A multicast data sender just starts sending data destined for a 327 multicast group. The sender's local router (DR) takes those data 328 packets, unicast-encapsulates them, and sends them directly to the 329 RP. The RP receives these encapsulated data packets, decapsulates 330 them, and forwards them onto the shared tree. The packets then 331 follow the (*,G) multicast tree state in the routers on the RP Tree, 332 being replicated wherever the RP Tree branches, and eventually 333 reaching all the receivers for that multicast group. The process of 334 encapsulating data packets to the RP is called registering, and the 335 encapsulation packets are known as PIM Register packets. 337 At the end of phase one, multicast traffic is flowing encapsulated to 338 the RP, and then natively over the RP tree to the multicast 339 receivers. 341 3.2. Phase Two: Register-Stop 343 Register-encapsulation of data packets is inefficient for two 344 reasons: 346 o Encapsulation and decapsulation may be relatively expensive 347 operations for a router to perform, depending on whether or not the 348 router has appropriate hardware for these tasks. 350 o Traveling all the way to the RP, and then back down the shared tree 351 may result in the packets traveling a relatively long distance to 352 reach receivers that are close to the sender. For some 353 applications, this increased latency or bandwidth consumption is 354 undesirable. 356 Although Register-encapsulation may continue indefinitely, for these 357 reasons, the RP will normally choose to switch to native forwarding. 358 To do this, when the RP receives a register-encapsulated data packet 359 from source S on group G, it will normally initiate an (S,G) source- 360 specific Join towards S. This Join message travels hop-by-hop 361 towards S, instantiating (S,G) multicast tree state in the routers 362 along the path. (S,G) multicast tree state is used only to forward 363 packets for group G if those packets come from source S. Eventually 364 the Join message reaches S's subnet or a router that already has 365 (S,G) multicast tree state, and then packets from S start to flow 366 following the (S,G) tree state towards the RP. These data packets 367 may also reach routers with (*,G) state along the path towards the 368 RP; if they do, they can shortcut onto the RP tree at this point. 370 While the RP is in the process of joining the source-specific tree 371 for S, the data packets will continue being encapsulated to the RP. 372 When packets from S also start to arrive natively at the RP, the RP 373 will be receiving two copies of each of these packets. At this 374 point, the RP starts to discard the encapsulated copy of these 375 packets, and it sends a Register-Stop message back to S's DR to 376 prevent the DR from unnecessarily encapsulating the packets. 378 At the end of phase 2, traffic will be flowing natively from S along 379 a source-specific tree to the RP, and from there along the shared 380 tree to the receivers. Where the two trees intersect, traffic may 381 transfer from the source-specific tree to the RP tree and thus avoid 382 taking a long detour via the RP. 384 Note that a sender may start sending before or after a receiver joins 385 the group, and thus phase two may happen before the shared tree to 386 the receiver is built. 388 3.3. Phase Three: Shortest-Path Tree 390 Although having the RP join back towards the source removes the 391 encapsulation overhead, it does not completely optimize the 392 forwarding paths. For many receivers, the route via the RP may 393 involve a significant detour when compared with the shortest path 394 from the source to the receiver. 396 To obtain lower latencies or more efficient bandwidth utilization, a 397 router on the receiver's LAN, typically the DR, may optionally 398 initiate a transfer from the shared tree to a source-specific 399 shortest-path tree (SPT). To do this, it issues an (S,G) Join 400 towards S. This instantiates state in the routers along the path to 401 S. Eventually, this join either reaches S's subnet or reaches a 402 router that already has (S,G) state. When this happens, data packets 403 from S start to flow following the (S,G) state until they reach the 404 receiver. 406 At this point, the receiver (or a router upstream of the receiver) 407 will be receiving two copies of the data: one from the SPT and one 408 from the RPT. When the first traffic starts to arrive from the SPT, 409 the DR or upstream router starts to drop the packets for G from S 410 that arrive via the RP tree. In addition, it sends an (S,G) Prune 411 message towards the RP. This is known as an (S,G,rpt) Prune. The 412 Prune message travels hop-by-hop, instantiating state along the path 413 towards the RP indicating that traffic from S for G should NOT be 414 forwarded in this direction. The prune is propagated until it reaches 415 the RP or a router that still needs the traffic from S for other 416 receivers. 418 By now, the receiver will be receiving traffic from S along the 419 shortest-path tree between the receiver and S. In addition, the RP 420 is receiving the traffic from S, but this traffic is no longer 421 reaching the receiver along the RP tree. As far as the receiver is 422 concerned, this is the final distribution tree. 424 3.4. Source-Specific Joins 426 IGMPv3 permits a receiver to join a group and specify that it only 427 wants to receive traffic for a group if that traffic comes from a 428 particular source. If a receiver does this, and no other receiver on 429 the LAN requires all the traffic for the group, then the DR may omit 430 performing a (*,G) join to set up the shared tree, and instead issue 431 a source-specific (S,G) join only. 433 The range of multicast addresses from 232.0.0.0 to 232.255.255.255 is 434 currently set aside for source-specific multicast in IPv4. For 435 groups in this range, receivers should only issue source-specific 436 IGMPv3 joins. If a PIM router receives a non-source-specific join for 437 a group in this range, it should ignore it, as described in Section 438 4.8. 440 3.5. Source-Specific Prunes 442 IGMPv3 also permits a receiver to join a group and to specify that it 443 only wants to receive traffic for a group if that traffic does not 444 come from a specific source or sources. In this case, the DR will 445 perform a (*,G) join as normal, but may combine this with an 446 (S,G,rpt) prune for each of the sources the receiver does not wish to 447 receive. 449 3.6. Multi-Access Transit LANs 451 The overview so far has concerned itself with point-to-point transit 452 links. However, using multi-access LANs such as Ethernet for transit 453 is not uncommon. This can cause complications for three reasons: 455 o Two or more routers on the LAN may issue (*,G) Joins to different 456 upstream routers on the LAN because they have inconsistent MRIB 457 entries regarding how to reach the RP. Both paths on the RP tree 458 will be set up, causing two copies of all the shared tree traffic 459 to appear on the LAN. 461 o Two or more routers on the LAN may issue (S,G) Joins to different 462 upstream routers on the LAN because they have inconsistent MRIB 463 entries regarding how to reach source S. Both paths on the source- 464 specific tree will be set up, causing two copies of all the traffic 465 from S to appear on the LAN. 467 o A router on the LAN may issue a (*,G) Join to one upstream router 468 on the LAN, and another router on the LAN may issue an (S,G) Join 469 to a different upstream router on the same LAN. Traffic from S may 470 reach the LAN over both the RPT and the SPT. If the receiver 471 behind the downstream (*,G) router doesn't issue an (S,G,rpt) 472 prune, then this condition would persist. 474 All of these problems are caused by there being more than one 475 upstream router with join state for the group or source-group pair. 476 PIM does not prevent such duplicate joins from occurring; instead, 477 when duplicate data packets appear on the LAN from different routers, 478 these routers notice this and then elect a single forwarder. This 479 election is performed using PIM Assert messages, which resolve the 480 problem in favor of the upstream router that has (S,G) state; or, if 481 neither or both router has (S,G) state, then the problem is resolved 482 in favor of the router with the best metric to the RP for RP trees, 483 or the best metric to the source for source-specific trees. 485 These Assert messages are also received by the downstream routers on 486 the LAN, and these cause subsequent Join messages to be sent to the 487 upstream router that won the Assert. 489 3.7. RP Discovery 491 PIM-SM routers need to know the address of the RP for each group for 492 which they have (*,G) state. This address is obtained automatically 493 (e.g., embedded-RP), through a bootstrap mechanism, or through static 494 configuration. 496 One dynamic way to do this is to use the Bootstrap Router (BSR) 497 mechanism [11]. One router in each PIM domain is elected the 498 Bootstrap Router through a simple election process. All the routers 499 in the domain that are configured to be candidates to be RPs 500 periodically unicast their candidacy to the BSR. From the 501 candidates, the BSR picks an RP-set, and periodically announces this 502 set in a Bootstrap message. Bootstrap messages are flooded hop-by-hop 503 throughout the domain until all routers in the domain know the RP- 504 Set. 506 To map a group to an RP, a router hashes the group address into the 507 RP-set using an order-preserving hash function (one that minimizes 508 changes if the RP-Set changes). The resulting RP is the one that it 509 uses as the RP for that group. 511 4. Protocol Specification 513 The specification of PIM-SM is broken into several parts: 515 o Section 4.1 details the protocol state stored. 517 o Section 4.2 specifies the data packet forwarding rules. 519 o Section 4.3 specifies Designated Router (DR) election and the rules 520 for sending and processing Hello messages. 522 o Section 4.4 specifies the PIM Register generation and processing 523 rules. 525 o Section 4.5 specifies the PIM Join/Prune generation and processing 526 rules. 528 o Section 4.6 specifies the PIM Assert generation and processing 529 rules. 531 o Section 4.7 specifies the RP discovery mechanisms. 533 o The subset of PIM required to support Source-Specific Multicast, 534 PIM-SSM, is described in Section 4.8. 536 o PIM packet formats are specified in Section 4.9. 538 o A summary of PIM-SM timers and their default values is given in 539 Section 4.10. 541 4.1. PIM Protocol State 543 This section specifies all the protocol state that a PIM 544 implementation should maintain in order to function correctly. We 545 term this state the Tree Information Base (TIB), as it holds the 546 state of all the multicast distribution trees at this router. In 547 this specification, we define PIM mechanisms in terms of the TIB. 548 However, only a very simple implementation would actually implement 549 packet forwarding operations in terms of this state. Most 550 implementations will use this state to build a multicast forwarding 551 table, which would then be updated when the relevant state in the TIB 552 changes. 554 Although we specify precisely the state to be kept, this does not 555 mean that an implementation of PIM-SM needs to hold the state in this 556 form. This is actually an abstract state definition, which is needed 557 in order to specify the router's behavior. A PIM-SM implementation 558 is free to hold whatever internal state it requires and will still be 559 conformant with this specification so long as it results in the same 560 externally visible protocol behavior as an abstract router that holds 561 the following state. 563 We divide TIB state into three sections: 565 (*,G) state 566 State that maintains the RP tree for G. 568 (S,G) state 569 State that maintains a source-specific tree for source S and 570 group G. 572 (S,G,rpt) state 573 State that maintains source-specific information about source S 574 on the RP tree for G. For example, if a source is being 575 received on the source-specific tree, it will normally have been 576 pruned off the RP tree. This prune state is (S,G,rpt) state. 578 The state that should be kept is described below. Of course, 579 implementations will only maintain state when it is relevant to 580 forwarding operations; for example, the "NoInfo" state might be 581 assumed from the lack of other state information rather than being 582 held explicitly. 584 4.1.1. General Purpose State 586 A router holds the following non-group-specific state: 588 For each interface: 590 o Effective Override Interval 592 o Effective Propagation Delay 594 o Suppression state: One of {"Enable", "Disable"} 596 Neighbor State: 598 For each neighbor: 600 o Information from neighbor's Hello 602 o Neighbor's GenID. 604 o Neighbor Liveness Timer (NLT) 606 Designated Router (DR) State: 608 o Designated Router's IP Address 610 o DR's DR Priority 612 The Effective Override Interval, the Effective Propagation Delay and 613 the Interface suppression state are described in Section 4.3.3. 614 Designated Router state is described in Section 4.3. 616 4.1.2. (*,G) State 618 For every group G, a router keeps the following state: 620 (*,G) state: 621 For each interface: 623 Local Membership: 624 State: One of {"NoInfo", "Include"} 626 PIM (*,G) Join/Prune State: 628 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 629 Pending" (PP)} 631 o Prune-Pending Timer (PPT) 633 o Join/Prune Expiry Timer (ET) 635 (*,G) Assert Winner State 637 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 638 "I won Assert" (W)} 640 o Assert Timer (AT) 642 o Assert winner's IP Address (AssertWinner) 644 o Assert winner's Assert Metric (AssertWinnerMetric) 646 Not interface specific: 648 Upstream (*,G) Join/Prune State: 650 o State: One of {"NotJoined(*,G)", "Joined(*,G)"} 652 o Upstream Join/Prune Timer (JT) 654 o Last RP Used 656 o Last RPF Neighbor towards RP that was used 658 Local membership is the result of the local membership mechanism 659 (such as IGMP or MLD) running on that interface. It need not be kept 660 if this router is not the DR on that interface unless this router won 661 a (*,G) assert on this interface for this group, although 662 implementations may optionally keep this state in case they become 663 the DR or assert winner. It is RECOMMENDED to store this information 664 if possible, as it reduces latency converging to stable operating 665 conditions after a failure causing a change of DR. This information 666 is used by the pim_include(*,G) macro described in Section 4.1.5. 668 PIM (*,G) Join/Prune state is the result of receiving PIM (*,G) 669 Join/Prune messages on this interface and is specified in Section 670 4.5.1. The state is used by the macros that calculate the outgoing 671 interface list in Section 4.1.5, and in the JoinDesired(*,G) macro 672 (defined in Section 4.5.4) that is used in deciding whether a 673 Join(*,G) should be sent upstream. 675 (*,G) Assert Winner state is the result of sending or receiving (*,G) 676 Assert messages on this interface. It is specified in Section 4.6.2. 678 The upstream (*,G) Join/Prune State reflects the state of the 679 upstream (*,G) state machine described in Section 4.5.4. 681 The upstream (*,G) Join/Prune Timer is used to send out periodic 682 Join(*,G) messages, and to override Prune(*,G) messages from peers on 683 an upstream LAN interface. 685 The last RP used must be stored because if the RP-Set changes 686 (Section 4.7), then state must be torn down and rebuilt for groups 687 whose RP changes. 689 The last RPF neighbor towards the RP is stored because if the MRIB 690 changes, then the RPF neighbor towards the RP may change. If it does 691 so, then we need to trigger a new Join(*,G) to the new upstream 692 neighbor and a Prune(*,G) to the old upstream neighbor. Similarly, 693 if a router detects through a changed GenID in a Hello message that 694 the upstream neighbor towards the RP has rebooted, then it SHOULD re- 695 instantiate state by sending a Join(*,G). These mechanisms are 696 specified in Section 4.5.4. 698 4.1.3. (S,G) State 700 For every source/group pair (S,G), a router keeps the following 701 state: 703 (S,G) state: 705 For each interface: 707 Local Membership: 708 State: One of {"NoInfo", "Include"} 710 PIM (S,G) Join/Prune State: 712 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 713 Pending" (PP)} 715 o Prune-Pending Timer (PPT) 717 o Join/Prune Expiry Timer (ET) 719 (S,G) Assert Winner State 721 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 722 "I won Assert" (W)} 724 o Assert Timer (AT) 726 o Assert winner's IP Address (AssertWinner) 728 o Assert winner's Assert Metric (AssertWinnerMetric) 730 Not interface specific: 732 Upstream (S,G) Join/Prune State: 734 o State: One of {"NotJoined(S,G)", "Joined(S,G)"} 736 o Upstream (S,G) Join/Prune Timer (JT) 738 o Last RPF Neighbor towards S that was used 740 o SPTbit (indicates (S,G) state is active) 742 o (S,G) Keepalive Timer (KAT) 744 Additional (S,G) state at the DR: 746 o Register state: One of {"Join" (J), "Prune" (P), 747 "Join-Pending" (JP), "NoInfo" (NI)} 749 o Register-Stop timer 751 Local membership is the result of the local source-specific 752 membership mechanism (such as IGMP version 3) running on that 753 interface and specifying that this particular source should be 754 included. As stored here, this state is the resulting state after 755 any IGMPv3 inconsistencies have been resolved. It need not be kept 756 if this router is not the DR on that interface unless this router won 757 an (S,G) assert on this interface for this group. However, it is 758 RECOMMENDED to store this information if possible, as it reduces 759 latency converging to stable operating conditions after a failure 760 causing a change of DR. This information is used by the 761 pim_include(S,G) macro described in Section 4.1.5. 763 PIM (S,G) Join/Prune state is the result of receiving PIM (S,G) 764 Join/Prune messages on this interface and is specified in Section 765 4.5.2. The state is used by the macros that calculate the outgoing 766 interface list in Section 4.1.5, and in the JoinDesired(S,G) macro 767 (defined in Section 4.5.5) that is used in deciding whether a 768 Join(S,G) should be sent upstream. 770 (S,G) Assert Winner state is the result of sending or receiving (S,G) 771 Assert messages on this interface. It is specified in Section 4.6.1. 773 The upstream (S,G) Join/Prune State reflects the state of the 774 upstream (S,G) state machine described in Section 4.5.5. 776 The upstream (S,G) Join/Prune Timer is used to send out periodic 777 Join(S,G) messages, and to override Prune(S,G) messages from peers on 778 an upstream LAN interface. 780 The last RPF neighbor towards S is stored because if the MRIB 781 changes, then the RPF neighbor towards S may change. If it does so, 782 then we need to trigger a new Join(S,G) to the new upstream neighbor 783 and a Prune(S,G) to the old upstream neighbor. Similarly, if the 784 router detects through a changed GenID in a Hello message that the 785 upstream neighbor towards S has rebooted, then it SHOULD re- 786 instantiate state by sending a Join(S,G). These mechanisms are 787 specified in Section 4.5.5. 789 The SPTbit is used to indicate whether forwarding is taking place on 790 the (S,G) Shortest Path Tree (SPT) or on the (*,G) tree. A router 791 can have (S,G) state and still be forwarding on (*,G) state during 792 the interval when the source-specific tree is being constructed. 793 When SPTbit is FALSE, only (*,G) forwarding state is used to forward 794 packets from S to G. When SPTbit is TRUE, both (*,G) and (S,G) 795 forwarding state are used. 797 The (S,G) Keepalive Timer is updated by data being forwarded using 798 this (S,G) forwarding state. It is used to keep (S,G) state alive in 799 the absence of explicit (S,G) Joins. Amongst other things, this is 800 necessary for the so-called "turnaround rules" -- when the RP uses 801 (S,G) joins to stop encapsulation, and then (S,G) prunes to prevent 802 traffic from unnecessarily reaching the RP. 804 On a DR, the (S,G) Register State is used to keep track of whether to 805 encapsulate data to the RP on the Register Tunnel; the (S,G) 806 Register-Stop timer tracks how long before encapsulation begins again 807 for a given (S,G). 809 4.1.4. (S,G,rpt) State 811 For every source/group pair (S,G) for which a router also has (*,G) 812 state, it also keeps the following state: 814 (S,G,rpt) state: 816 For each interface: 818 Local Membership: 819 State: One of {"NoInfo", "Exclude"} 821 PIM (S,G,rpt) Join/Prune State: 823 o State: One of {"NoInfo", "Pruned", "Prune- 824 Pending"} 826 o Prune-Pending Timer (PPT) 828 o Join/Prune Expiry Timer (ET) 830 Not interface specific: 832 Upstream (S,G,rpt) Join/Prune State: 834 o State: One of {"RPTNotJoined(G)", 835 "NotPruned(S,G,rpt)", "Pruned(S,G,rpt)"} 837 o Override Timer (OT) 839 Local membership is the result of the local source-specific 840 membership mechanism (such as IGMPv3) running on that interface and 841 specifying that although there is (*,G) Include state, this 842 particular source should be excluded. As stored here, this state is 843 the resulting state after any IGMPv3 inconsistencies between LAN 844 members have been resolved. It need not be kept if this router is 845 not the DR on that interface unless this router won a (*,G) assert on 846 this interface for this group. However, we recommend storing this 847 information if possible, as it reduces latency converging to stable 848 operating conditions after a failure causing a change of DR. This 849 information is used by the pim_exclude(S,G) macro described in 850 Section 4.1.5. 852 PIM (S,G,rpt) Join/Prune state is the result of receiving PIM 853 (S,G,rpt) Join/Prune messages on this interface and is specified in 854 Section 4.5.3. The state is used by the macros that calculate the 855 outgoing interface list in Section 4.1.5, and in the rules for adding 856 Prune(S,G,rpt) messages to Join(*,G) messages specified in Section 857 4.5.6. 859 The upstream (S,G,rpt) Join/Prune state is used along with the 860 Override Timer to send the correct override messages in response to 861 Join/Prune messages sent by upstream peers on a LAN. This state and 862 behavior are specified in Section 4.5.7. 864 4.1.5. State Summarization Macros 866 Using this state, we define the following "macro" definitions, which 867 we will use in the descriptions of the state machines and pseudocode 868 in the following sections. 870 The most important macros are those that define the outgoing 871 interface list (or "olist") for the relevant state. An olist can be 872 "immediate" if it is built directly from the state of the relevant 873 type. For example, the immediate_olist(S,G) is the olist that would 874 be built if the router only had (S,G) state and no (*,G) or (S,G,rpt) 875 state. In contrast, the "inherited" olist inherits state from other 876 types. For example, the inherited_olist(S,G) is the olist that is 877 relevant for forwarding a packet from S to G using both source- 878 specific and group-specific state. 880 There is no immediate_olist(S,G,rpt) as (S,G,rpt) state is negative 881 state; it removes interfaces in the (*,G) olist from the olist that 882 is actually used to forward traffic. The inherited_olist(S,G,rpt) is 883 therefore the olist that would be used for a packet from S to G 884 forwarding on the RP tree. It is a strict subset of 885 immediate_olist(*,G). 887 Generally speaking, the inherited olists are used for forwarding, and 888 the immediate_olists are used to make decisions about state 889 maintenance. 891 immediate_olist(*,G) = 892 joins(*,G) (+) pim_include(*,G) (-) lost_assert(*,G) 894 immediate_olist(S,G) = 895 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) 897 inherited_olist(S,G,rpt) = 898 ( joins(*,G) (-) prunes(S,G,rpt) ) 899 (+) ( pim_include(*,G) (-) pim_exclude(S,G)) 900 (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) ) 902 inherited_olist(S,G) = 903 inherited_olist(S,G,rpt) (+) 904 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) 906 The macros pim_include(*,G) and pim_include(S,G) indicate the 907 interfaces to which traffic might be forwarded because of hosts that 908 are local members on that interface. Note that normally only the DR 909 cares about local membership, but when an assert happens, the assert 910 winner takes over responsibility for forwarding traffic to local 911 members that have requested traffic on a group or source/group pair. 913 pim_include(*,G) = 914 { all interfaces I such that: 915 ( ( I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) 916 OR AssertWinner(*,G,I) == me ) 917 AND local_receiver_include(*,G,I) } 919 pim_include(S,G) = 920 { all interfaces I such that: 921 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) 922 OR AssertWinner(S,G,I) == me ) 923 AND local_receiver_include(S,G,I) } 925 pim_exclude(S,G) = 926 { all interfaces I such that: 927 ( (I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) 928 OR AssertWinner(*,G,I) == me ) 929 AND local_receiver_exclude(S,G,I) } 931 The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD 932 module or other local membership mechanism has determined that local 933 members on interface I desire to receive traffic sent specifically by 934 S to G. "local_receiver_include(*,G,I)" is true if the IGMP/MLD 935 module or other local membership mechanism has determined that local 936 members on interface I desire to receive all traffic sent to G 937 (possibly excluding traffic from a specific set of sources). 938 "local_receiver_exclude(S,G,I) is true if 939 "local_receiver_include(*,G,I)" is true but none of the local members 940 desire to receive traffic from S. 942 The set "joins(*,G)" is the set of all interfaces on which the router 943 has received (*,G) Joins: 945 joins(*,G) = 946 { all interfaces I such that 947 DownstreamJPState(*,G,I) is either Join or Prune-Pending } 949 DownstreamJPState(*,G,I) is the state of the finite state machine in 950 Section 4.5.1. 952 The set "joins(S,G)" is the set of all interfaces on which the router 953 has received (S,G) Joins: 955 joins(S,G) = 956 { all interfaces I such that 957 DownstreamJPState(S,G,I) is either Join or Prune-Pending } 959 DownstreamJPState(S,G,I) is the state of the finite state machine in 960 Section 4.5.2. 962 The set "prunes(S,G,rpt)" is the set of all interfaces on which the 963 router has received (*,G) joins and (S,G,rpt) prunes. 965 prunes(S,G,rpt) = 966 { all interfaces I such that 967 DownstreamJPState(S,G,rpt,I) is Prune or PruneTmp } 969 DownstreamJPState(S,G,rpt,I) is the state of the finite state machine 970 in Section 4.5.3. 972 The set "lost_assert(*,G)" is the set of all interfaces on which the 973 router has received (*,G) joins but has lost a (*,G) assert. The 974 macro lost_assert(*,G,I) is defined in Section 4.6.5. 976 lost_assert(*,G) = 977 { all interfaces I such that 978 lost_assert(*,G,I) == TRUE } 980 The set "lost_assert(S,G,rpt)" is the set of all interfaces on which 981 the router has received (*,G) joins but has lost an (S,G) assert. 982 The macro lost_assert(S,G,rpt,I) is defined in Section 4.6.5. 984 lost_assert(S,G,rpt) = 985 { all interfaces I such that 986 lost_assert(S,G,rpt,I) == TRUE } 988 The set "lost_assert(S,G)" is the set of all interfaces on which the 989 router has received (S,G) joins but has lost an (S,G) assert. The 990 macro lost_assert(S,G,I) is defined in Section 4.6.5. 992 lost_assert(S,G) = 993 { all interfaces I such that 994 lost_assert(S,G,I) == TRUE } 996 The following pseudocode macro definitions are also used in many 997 places in the specification. Basically, RPF' is the RPF neighbor 998 towards an RP or source unless a PIM-Assert has overridden the normal 999 choice of neighbor. 1001 neighbor RPF'(*,G) { 1002 if ( I_Am_Assert_Loser(*, G, RPF_interface(RP(G))) ) { 1003 return AssertWinner(*, G, RPF_interface(RP(G)) ) 1004 } else { 1005 return NBR( RPF_interface(RP(G)), MRIB.next_hop( RP(G) ) ) 1006 } 1007 } 1009 neighbor RPF'(S,G,rpt) { 1010 if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) { 1011 return AssertWinner(S, G, RPF_interface(RP(G)) ) 1012 } else { 1013 return RPF'(*,G) 1014 } 1015 } 1017 neighbor RPF'(S,G) { 1018 if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) { 1019 return AssertWinner(S, G, RPF_interface(S) ) 1020 } else { 1021 return NBR( RPF_interface(S), MRIB.next_hop( S ) ) 1022 } 1023 } 1025 RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data packets 1026 should be coming and to which joins should be sent on the RP tree and 1027 SPT, respectively. 1029 RPF'(S,G,rpt) is basically RPF'(*,G) modified by the result of an 1030 Assert(S,G) on RPF_interface(RP(G)). In such a case, packets from S 1031 will be originating from a different router than RPF'(*,G). If we 1032 only have active (*,G) Join state, we need to accept packets from 1033 RPF'(S,G,rpt) and add a Prune(S,G,rpt) to the periodic Join(*,G) 1034 messages that we send to RPF'(*,G) (see Section 4.5.6). 1036 The function MRIB.next_hop( S ) returns an address of the next-hop 1037 PIM neighbor toward the host S, as indicated by the current MRIB. If 1038 S is directly adjacent, then MRIB.next_hop( S ) returns NULL. At the 1039 RP for G, MRIB.next_hop( RP(G)) returns NULL. 1041 The function NBR( I, A ) uses information gathered through PIM Hello 1042 messages to map the IP address A of a directly connected PIM neighbor 1043 router on interface I to the primary IP address of the same router 1044 (Section 4.3.4). The primary IP address of a neighbor is the address 1045 that it uses as the source of its PIM Hello messages. Note that a 1046 neighbor's IP address may be non-unique within the PIM neighbor 1047 database due to scope issues. The address must, however, be unique 1048 amongst the addresses of all the PIM neighbors on a specific 1049 interface. 1051 I_Am_Assert_Loser(S, G, I) is true if the Assert state machine (in 1052 Section 4.6.1) for (S,G) on Interface I is in "I am Assert Loser" 1053 state. 1055 I_Am_Assert_Loser(*, G, I) is true if the Assert state machine (in 1056 Section 4.6.2) for (*,G) on Interface I is in "I am Assert Loser" 1057 state. 1059 4.2. Data Packet Forwarding Rules 1061 The PIM-SM packet forwarding rules are defined below in pseudocode. 1063 iif is the incoming interface of the packet. 1064 S is the source address of the packet. 1065 G is the destination address of the packet (group address). 1066 RP is the address of the Rendezvous Point for this group. 1067 RPF_interface(S) is the interface the MRIB indicates would be used 1068 to route packets to S. 1069 RPF_interface(RP) is the interface the MRIB indicates would be 1070 used to route packets to the RP, except at the RP when it is the 1071 decapsulation interface (the "virtual" interface on which register 1072 packets are received). 1074 First, we restart (or start) the Keepalive Timer if the source is on 1075 a directly connected subnet. 1077 Second, we check to see if the SPTbit should be set because we've now 1078 switched from the RP tree to the SPT. 1080 Next, we check to see whether the packet should be accepted based on 1081 TIB state and the interface that the packet arrived on. 1083 If the packet should be forwarded using (S,G) state, we then build an 1084 outgoing interface list for the packet. If this list is not empty, 1085 then we restart the (S,G) state Keepalive Timer. 1087 If the packet should be forwarded using (*,G) state, then we just 1088 build an outgoing interface list for the packet. We also check if we 1089 should initiate a switch to start receiving this source on a shortest 1090 path tree. 1092 Finally we remove the incoming interface from the outgoing interface 1093 list we've created, and if the resulting outgoing interface list is 1094 not empty, we forward the packet out of those interfaces. 1096 On receipt of data from S to G on interface iif: 1097 if( DirectlyConnected(S) == TRUE AND iif == RPF_interface(S) ) { 1098 set KeepaliveTimer(S,G) to Keepalive_Period 1099 # Note: a register state transition or UpstreamJPState(S,G) 1100 # transition may happen as a result of restarting 1101 # KeepaliveTimer, and must be dealt with here. 1102 } 1104 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined AND 1105 inherited_olist(S,G) != NULL ) { 1106 set KeepaliveTimer(S,G) to Keepalive_Period 1107 } 1109 Update_SPTbit(S,G,iif) 1110 oiflist = NULL 1112 if( iif == RPF_interface(S) AND SPTbit(S,G) == TRUE ) { 1113 oiflist = inherited_olist(S,G) 1114 } else if( iif == RPF_interface(RP(G)) AND SPTbit(S,G) == FALSE ) { 1115 oiflist = inherited_olist(S,G,rpt) 1116 CheckSwitchToSpt(S,G) 1117 } else { 1118 # Note: RPF check failed 1119 # A transition in an Assert FSM may cause an Assert(S,G) 1120 # or Assert(*,G) message to be sent out interface iif. 1121 # See section 4.6 for details. 1122 if ( SPTbit(S,G) == TRUE AND iif is in inherited_olist(S,G) ) { 1123 send Assert(S,G) on iif 1124 } else if ( SPTbit(S,G) == FALSE AND 1125 iif is in inherited_olist(S,G,rpt) ) { 1126 send Assert(*,G) on iif 1127 } 1128 } 1130 oiflist = oiflist (-) iif 1131 forward packet on all interfaces in oiflist 1133 This pseudocode employs several "macro" definitions: 1135 DirectlyConnected(S) is TRUE if the source S is on any subnet that is 1136 directly connected to this router (or for packets originating on this 1137 router). 1139 inherited_olist(S,G) and inherited_olist(S,G,rpt) are defined in 1140 Section 4.1. 1142 Basically, inherited_olist(S,G) is the outgoing interface list for 1143 packets forwarded on (S,G) state, taking into account (*,G) state, 1144 asserts, etc. 1146 inherited_olist(S,G,rpt) is the outgoing interface list for packets 1147 forwarded on (*,G) state, taking into account (S,G,rpt) prune state, 1148 asserts, etc. 1150 Update_SPTbit(S,G,iif) is defined in Section 4.2.2. 1152 CheckSwitchToSpt(S,G) is defined in Section 4.2.1. 1154 UpstreamJPState(S,G) is the state of the finite state machine in 1155 Section 4.5.5. 1157 Keepalive_Period is defined in Section 4.10. 1159 Data-triggered PIM-Assert messages sent from the above forwarding 1160 code SHOULD be rate-limited in an implementation-dependent manner. 1162 4.2.1. Last-Hop Switchover to the SPT 1164 In Sparse-Mode PIM, last-hop routers join the shared tree towards the 1165 RP. Once traffic from sources to joined groups arrives at a last-hop 1166 router, it has the option of switching to receive the traffic on a 1167 shortest path tree (SPT). 1169 The decision for a router to switch to the SPT is controlled as 1170 follows: 1172 void 1173 CheckSwitchToSpt(S,G) { 1174 if ( ( pim_include(*,G) (-) pim_exclude(S,G) 1175 (+) pim_include(S,G) != NULL ) 1176 AND SwitchToSptDesired(S,G) ) { 1177 # Note: Restarting the KAT will result in the SPT switch 1178 set KeepaliveTimer(S,G) to Keepalive_Period 1179 } 1180 } 1182 SwitchToSptDesired(S,G) is a policy function that is implementation 1183 defined. An "infinite threshold" policy can be implemented by making 1184 SwitchToSptDesired(S,G) return false all the time. A "switch on 1185 first packet" policy can be implemented by making 1186 SwitchToSptDesired(S,G) return true once a single packet has been 1187 received for the source and group. 1189 4.2.2. Setting and Clearing the (S,G) SPTbit 1191 The (S,G) SPTbit is used to distinguish whether to forward on (*,G) 1192 or on (S,G) state. When switching from the RP tree to the source 1193 tree, there is a transition period when data is arriving due to 1194 upstream (*,G) state while upstream (S,G) state is being established, 1195 during which time a router should continue to forward only on (*,G) 1196 state. This prevents temporary black-holes that would be caused by 1197 sending a Prune(S,G,rpt) before the upstream (S,G) state has finished 1198 being established. 1200 Thus, when a packet arrives, the (S,G) SPTbit is updated as follows: 1202 void 1203 Update_SPTbit(S,G,iif) { 1204 if ( iif == RPF_interface(S) 1205 AND JoinDesired(S,G) == TRUE 1206 AND ( DirectlyConnected(S) == TRUE 1207 OR RPF_interface(S) != RPF_interface(RP(G)) 1208 OR inherited_olist(S,G,rpt) == NULL 1209 OR ( ( RPF'(S,G) == RPF'(*,G) ) AND 1210 ( RPF'(S,G) != NULL ) ) 1211 OR ( I_Am_Assert_Loser(S,G,iif) ) ) ) { 1212 Set SPTbit(S,G) to TRUE 1213 } 1214 } 1216 Additionally, a router can set SPTbit(S,G) to TRUE in other cases, 1217 such as when it receives an Assert(S,G) on RPF_interface(S) (see 1218 Section 4.6.1). 1220 JoinDesired(S,G) is defined in Section 4.5.5 and indicates whether we 1221 have the appropriate (S,G) Join state to wish to send a Join(S,G) 1222 upstream. 1224 Basically, Update_SPTbit(S,G,iif) will set the SPTbit if we have the 1225 appropriate (S,G) join state, and if the packet arrived on the 1226 correct upstream interface for S, and if one or more of the following 1227 conditions applies: 1229 1. The source is directly connected, in which case the switch to the 1230 SPT is a no-op. 1232 2. The RPF interface to S is different from the RPF interface to the 1233 RP. The packet arrived on RPF_interface(S), and so the SPT must 1234 have been completed. 1236 3. No One wants the packet on the RP tree. 1238 4. RPF'(S,G) == RPF'(*,G). In this case, the router will never be 1239 able to tell if the SPT has been completed, so it should just 1240 switch immediately. RPF'(S,G) != NULL check ensures that SPTbit 1241 is set only if RPF neighbor towards S is valid. 1243 In the case where the RPF interface is the same for the RP and for S, 1244 but RPF'(S,G) and RPF'(*,G) differ, we wait for an Assert(S,G), which 1245 indicates that the upstream router with (S,G) state believes the SPT 1246 has been completed. However, item (3) above is needed because there 1247 may not be any (*,G) state to trigger an Assert(S,G) to happen. 1249 The SPTbit is cleared in the (S,G) upstream state machine (see 1250 Section 4.5.5) when JoinDesired(S,G) becomes FALSE. 1252 4.3. Designated Routers (DR) and Hello Messages 1254 A shared-media LAN like Ethernet may have multiple PIM-SM routers 1255 connected to it. A single one of these routers, the DR, will act on 1256 behalf of directly connected hosts with respect to the PIM-SM 1257 protocol. Because the distinction between LANs and point-to-point 1258 interfaces can sometimes be blurred, and because routers may also 1259 have multicast host functionality, the PIM-SM specification makes no 1260 distinction between the two. Thus, DR election will happen on all 1261 interfaces, LAN or otherwise. 1263 DR election is performed using Hello messages. Hello messages are 1264 also the way that option negotiation takes place in PIM, so that 1265 additional functionality can be enabled, or parameters tuned. 1267 4.3.1. Sending Hello Messages 1269 PIM Hello messages are sent periodically on each PIM-enabled 1270 interface. They allow a router to learn about the neighboring PIM 1271 routers on each interface. Hello messages are also the mechanism 1272 used to elect a Designated Router (DR), and to negotiate additional 1273 capabilities. A router must record the Hello information received 1274 from each PIM neighbor. 1276 Hello messages MUST be sent on all active interfaces, including 1277 physical point-to-point links, and are multicast to the 'ALL-PIM- 1278 ROUTERS' group address ('224.0.0.13' for IPv4 and 'ff02::d' for 1279 IPv6). 1281 We note that some implementations do not send Hello messages on 1282 point-to-point interfaces. This is non-compliant behavior. A 1283 compliant PIM router MUST send Hello messages, even on point-to-point 1284 interfaces. 1286 A per-interface Hello Timer (HT(I)) is used to trigger sending Hello 1287 messages on each active interface. When PIM is enabled on an 1288 interface or a router first starts, the Hello Timer of that interface 1289 is set to a random value between 0 and Triggered_Hello_Delay. This 1290 prevents synchronization of Hello messages if multiple routers are 1291 powered on simultaneously. After the initial randomized interval, 1292 Hello messages MUST be sent every Hello_Period seconds. The Hello 1293 Timer SHOULD NOT be reset except when it expires. 1295 Note that neighbors will not accept Join/Prune or Assert messages 1296 from a router unless they have first heard a Hello message from that 1297 router. Thus, if a router needs to send a Join/Prune or Assert 1298 message on an interface on which it has not yet sent a Hello message 1299 with the currently configured IP address, then it MUST immediately 1300 send the relevant Hello message without waiting for the Hello Timer 1301 to expire, followed by the Join/Prune or Assert message. 1303 The DR_Priority Option allows a network administrator to give 1304 preference to a particular router in the DR election process by 1305 giving it a numerically larger DR Priority. The DR_Priority Option 1306 SHOULD be included in every Hello message, even if no DR Priority is 1307 explicitly configured on that interface. This is necessary because 1308 priority-based DR election is only enabled when all neighbors on an 1309 interface advertise that they are capable of using the DR_Priority 1310 Option. The default priority is 1. 1312 The Generation_Identifier (GenID) Option SHOULD be included in all 1313 Hello messages. The GenID option contains a randomly generated 1314 32-bit value that is regenerated each time PIM forwarding is started 1315 or restarted on the interface, including when the router itself 1316 restarts. When a Hello message with a new GenID is received from a 1317 neighbor, any old Hello information about that neighbor SHOULD be 1318 discarded and superseded by the information from the new Hello 1319 message. This may cause a new DR to be chosen on that interface. 1321 The LAN Prune Delay Option SHOULD be included in all Hello messages 1322 sent on multi-access LANs. This option advertises a router's 1323 capability to use values other than the defaults for the 1324 Propagation_Delay and Override_Interval, which affect the setting of 1325 the Prune-Pending, Upstream Join, and Override Timers (defined in 1326 Section 4.10). 1328 The Address List Option advertises all the secondary addresses 1329 associated with the source interface of the router originating the 1330 message. The option MUST be included in all Hello messages if there 1331 are secondary addresses associated with the source interface and MAY 1332 be omitted if no secondary addresses exist. 1334 To allow new or rebooting routers to learn of PIM neighbors quickly, 1335 when a Hello message is received from a new neighbor, or a Hello 1336 message with a new GenID is received from an existing neighbor, a new 1337 Hello message SHOULD be sent on this interface after a randomized 1338 delay between 0 and Triggered_Hello_Delay. This triggered message 1339 need not change the timing of the scheduled periodic message. If a 1340 router needs to send a Join/Prune to the new neighbor or send an 1341 Assert message in response to an Assert message from the new neighbor 1342 before this randomized delay has expired, then it MUST immediately 1343 send the relevant Hello message without waiting for the Hello Timer 1344 to expire, followed by the Join/Prune or Assert message. If it does 1345 not do this, then the new neighbor will discard the Join/Prune or 1346 Assert message. 1348 Before an interface goes down or changes primary IP address, a Hello 1349 message with a zero HoldTime SHOULD be sent immediately (with the old 1350 IP address if the IP address changed). This will cause PIM neighbors 1351 to remove this neighbor (or its old IP address) immediately. After 1352 an interface has changed its IP address, it MUST send a Hello message 1353 with its new IP address. If an interface changes one of its 1354 secondary IP addresses, a Hello message with an updated Address_List 1355 option and a non-zero HoldTime SHOULD be sent immediately. This will 1356 cause PIM neighbors to update this neighbor's list of secondary 1357 addresses immediately. 1359 4.3.2. DR Election 1361 When a PIM Hello message is received on interface I, the following 1362 information about the sending neighbor is recorded: 1364 neighbor.interface 1365 The interface on which the Hello message arrived. 1367 neighbor.primary_ip_address 1368 The IP address that the PIM neighbor used as the source 1369 address of the Hello message. 1371 neighbor.genid 1372 The Generation ID of the PIM neighbor. 1374 neighbor.dr_priority 1375 The DR Priority field of the PIM neighbor, if it is present in 1376 the Hello message. 1378 neighbor.dr_priority_present 1379 A flag indicating if the DR Priority field was present in the 1380 Hello message. 1382 neighbor.timeout 1383 A timer value to time out the neighbor state when it becomes 1384 stale, also known as the Neighbor Liveness Timer. 1386 The Neighbor Liveness Timer (NLT(N,I)) is reset to 1387 Hello_Holdtime (from the Hello Holdtime option) whenever a 1388 Hello message is received containing a Holdtime option, or to 1389 Default_Hello_Holdtime if the Hello message does not contain 1390 the Holdtime option. 1392 Neighbor state is deleted when the neighbor timeout expires. 1394 The function for computing the DR on interface I is: 1396 host 1397 DR(I) { 1398 dr = me 1399 for each neighbor on interface I { 1400 if ( dr_is_better( neighbor, dr, I ) == TRUE ) { 1401 dr = neighbor 1402 } 1403 } 1404 return dr 1405 } 1407 The function used for comparing DR "metrics" on interface I is: 1409 bool 1410 dr_is_better(a,b,I) { 1411 if( there is a neighbor n on I for which n.dr_priority_present 1412 is false ) { 1413 return a.primary_ip_address > b.primary_ip_address 1414 } else { 1415 return ( a.dr_priority > b.dr_priority ) OR 1416 ( a.dr_priority == b.dr_priority AND 1417 a.primary_ip_address > b.primary_ip_address ) 1418 } 1419 } 1421 The trivial function I_am_DR(I) is defined to aid readability: 1423 bool 1424 I_am_DR(I) { 1425 return DR(I) == me 1426 } 1428 The DR Priority is a 32-bit unsigned number, and the numerically 1429 larger priority is always preferred. A router's idea of the current 1430 DR on an interface can change when a PIM Hello message is received, 1431 when a neighbor times out, or when a router's own DR Priority 1432 changes. If the router becomes the DR or ceases to be the DR, this 1433 will normally cause the DR Register state machine to change state. 1434 Subsequent actions are determined by that state machine. 1436 We note that some PIM implementations do not send Hello messages on 1437 point-to-point interfaces and thus cannot perform DR election on 1438 such interfaces. This is non-compliant behavior. DR election MUST 1439 be performed on ALL active PIM-SM interfaces. 1441 4.3.3. Reducing Prune Propagation Delay on LANs 1443 In addition to the information recorded for the DR Election, the 1444 following per neighbor information is obtained from the LAN Prune 1445 Delay Hello option: 1447 neighbor.lan_prune_delay_present 1448 A flag indicating if the LAN Prune Delay option was present in 1449 the Hello message. 1451 neighbor.tracking_support 1452 A flag storing the value of the T bit in the LAN Prune Delay 1453 option if it is present in the Hello message. This indicates 1454 the neighbor's capability to disable Join message suppression. 1456 neighbor.propagation_delay 1457 The Propagation Delay field of the LAN Prune Delay option (if 1458 present) in the Hello message. 1460 neighbor.override_interval 1461 The Override_Interval field of the LAN Prune Delay option (if 1462 present) in the Hello message. 1464 The additional state described above is deleted along with the DR 1465 neighbor state when the neighbor timeout expires. 1467 Just like the DR_Priority option, the information provided in the LAN 1468 Prune Delay option is not used unless all neighbors on a link 1469 advertise the option. The function below computes this state: 1471 bool 1472 lan_delay_enabled(I) { 1473 for each neighbor on interface I { 1474 if ( neighbor.lan_prune_delay_present == false ) { 1475 return false 1476 } 1477 } 1478 return true 1479 } 1481 The Propagation Delay inserted by a router in the LAN Prune Delay 1482 option expresses the expected message propagation delay on the link 1483 and SHOULD be configurable by the system administrator. It is used 1484 by upstream routers to figure out how long they should wait for a 1485 Join override message before pruning an interface. 1487 PIM implementers SHOULD enforce a lower bound on the permitted values 1488 for this delay to allow for scheduling and processing delays within 1489 their router. Such delays may cause received messages to be 1490 processed later as well as triggered messages to be sent later than 1491 intended. Setting this Propagation Delay to too low a value may 1492 result in temporary forwarding outages because a downstream router 1493 will not be able to override a neighbor's Prune message before the 1494 upstream neighbor stops forwarding. 1496 When all routers on a link are in a position to negotiate a 1497 Propagation Delay different from the default, the largest value from 1498 those advertised by each neighbor is chosen. The function for 1499 computing the Effective Propagation Delay of interface I is: 1501 time_interval 1502 Effective_Propagation_Delay(I) { 1503 if ( lan_delay_enabled(I) == false ) { 1504 return Propagation_delay_default 1505 } 1506 delay = Propagation_Delay(I) 1507 for each neighbor on interface I { 1508 if ( neighbor.propagation_delay > delay ) { 1509 delay = neighbor.propagation_delay 1510 } 1511 } 1512 return delay 1513 } 1515 To avoid synchronization of override messages when multiple 1516 downstream routers share a multi-access link, sending of such 1517 messages is delayed by a small random amount of time. The period of 1518 randomization should represent the size of the PIM router population 1519 on the link. Each router expresses its view of the amount of 1520 randomization necessary in the Override Interval field of the LAN 1521 Prune Delay option. 1523 When all routers on a link are in a position to negotiate an Override 1524 Interval different from the default, the largest value from those 1525 advertised by each neighbor is chosen. The function for computing 1526 the Effective Override Interval of interface I is: 1528 time_interval 1529 Effective_Override_Interval(I) { 1530 if ( lan_delay_enabled(I) == false ) { 1531 return t_override_default 1532 } 1533 delay = Override_Interval(I) 1534 for each neighbor on interface I { 1535 if ( neighbor.override_interval > delay ) { 1536 delay = neighbor.override_interval 1537 } 1538 } 1539 return delay 1540 } 1542 Although the mechanisms are not specified in this document, it is 1543 possible for upstream routers to explicitly track the join membership 1544 of individual downstream routers if Join suppression is disabled. A 1545 router can advertise its willingness to disable Join suppression by 1546 using the T bit in the LAN Prune Delay Hello option. Unless all PIM 1547 routers on a link negotiate this capability, explicit tracking and 1548 the disabling of the Join suppression mechanism are not possible. 1549 The function for computing the state of Suppression on interface I 1550 is: 1552 bool 1553 Suppression_Enabled(I) { 1554 if ( lan_delay_enabled(I) == false ) { 1555 return true 1556 } 1557 for each neighbor on interface I { 1558 if ( neighbor.tracking_support == false ) { 1559 return true 1560 } 1561 } 1562 return false 1563 } 1565 Note that the setting of Suppression_Enabled(I) affects the value of 1566 t_suppressed (see Section 4.10). 1568 4.3.4. Maintaining Secondary Address Lists 1570 Communication of a router's interface secondary addresses to its PIM 1571 neighbors is necessary to provide the neighbors with a mechanism for 1572 mapping next_hop information obtained through their MRIB to a primary 1573 address that can be used as a destination for Join/Prune messages. 1574 The mapping is performed through the NBR macro. The primary address 1575 of a PIM neighbor is obtained from the source IP address used in its 1576 PIM Hello messages. Secondary addresses are carried within the Hello 1577 message in an Address List Hello option. The primary address of the 1578 source interface of the router MUST NOT be listed within the Address 1579 List Hello option. 1581 In addition to the information recorded for the DR Election, the 1582 following per neighbor information is obtained from the Address List 1583 Hello option: 1585 neighbor.secondary_address_list 1586 The list of secondary addresses used by the PIM neighbor on 1587 the interface through which the Hello message was transmitted. 1589 When processing a received PIM Hello message containing an Address 1590 List Hello option, the list of secondary addresses in the message 1591 completely replaces any previously associated secondary addresses for 1592 that neighbor. If a received PIM Hello message does not contain an 1593 Address List Hello option, then all secondary addresses associated 1594 with the neighbor MUST be deleted. If a received PIM Hello message 1595 contains an Address List Hello option that includes the primary 1596 address of the sending router in the list of secondary addresses 1597 (although this is not expected), then the addresses listed in the 1598 message, excluding the primary address, are used to update the 1599 associated secondary addresses for that neighbor. 1601 All the advertised secondary addresses in received Hello messages 1602 must be checked against those previously advertised by all other PIM 1603 neighbors on that interface. If there is a conflict and the same 1604 secondary address was previously advertised by another neighbor, then 1605 only the most recently received mapping MUST be maintained, and an 1606 error message SHOULD be logged to the administrator in a rate-limited 1607 manner. 1609 Within one Address List Hello option, all the addresses MUST be of 1610 the same address family. It is not permitted to mix IPv4 and IPv6 1611 addresses within the same message. In addition, the address family 1612 of the fields in the message SHOULD be the same as the IP source and 1613 destination addresses of the packet header. 1615 4.4. PIM Register Messages 1617 The Designated Router (DR) on a LAN or point-to-point link 1618 encapsulates multicast packets from local sources to the RP for the 1619 relevant group unless it recently received a Register-Stop message 1620 for that (S,G) or (*,G) from the RP. When the DR receives a 1621 Register-Stop message from the RP, it starts a Register-Stop Timer to 1622 maintain this state. Just before the Register-Stop Timer expires, 1623 the DR sends a Null-Register Message to the RP to allow the RP to 1624 refresh the Register-Stop information at the DR. If the Register- 1625 Stop Timer actually expires, the DR will resume encapsulating packets 1626 from the source to the RP. 1628 4.4.1. Sending Register Messages from the DR 1630 Every PIM-SM router has the capability to be a DR. The state machine 1631 below is used to implement Register functionality. For the purposes 1632 of specification, we represent the mechanism to encapsulate packets 1633 to the RP as a Register-Tunnel interface, which is added to or 1634 removed from the (S,G) olist. The tunnel interface then takes part 1635 in the normal packet forwarding rules as specified in Section 4.2. 1637 If register state is maintained, it is maintained only for directly 1638 connected sources and is per-(S,G). There are four states in the 1639 DR's per-(S,G) Register state machine: 1641 Join (J) 1642 The register tunnel is "joined" (the join is actually implicit, 1643 but the DR acts as if the RP has joined the DR on the tunnel 1644 interface). 1646 Prune (P) 1647 The register tunnel is "pruned" (this occurs when a Register- 1648 Stop is received). 1650 Join-Pending (JP) 1651 The register tunnel is pruned but the DR is contemplating adding 1652 it back. 1654 NoInfo (NI) 1655 No information. This is the initial state, and the state when 1656 the router is not the DR. 1658 In addition, a Register-Stop Timer (RST) is kept if the state machine 1659 is not in the NoInfo state. 1661 Figure 1: Per-(S,G) register state machine at a DR in tabular form 1663 +----------++----------------------------------------------------------+ 1664 | || Event | 1665 | ++----------+-----------+-----------+-----------+-----------+ 1666 |Prev State||Register- | Could | Could | Register- | RP changed| 1667 | ||Stop Timer| Register | Register | Stop | | 1668 | ||expires | ->True | ->False | received | | 1669 +----------++----------+-----------+-----------+-----------+-----------+ 1670 |NoInfo ||- | -> J state| - | - | - | 1671 |(NI) || | add reg | | | | 1672 | || | tunnel | | | | 1673 +----------++----------+-----------+-----------+-----------+-----------+ 1674 | ||- | - | -> NI | -> P state| -> J state| 1675 | || | | state | | | 1676 | || | | remove reg| remove reg| update reg| 1677 |Join (J) || | | tunnel | tunnel; | tunnel | 1678 | || | | | set | | 1679 | || | | | Register- | | 1680 | || | | | Stop | | 1681 | || | | | Timer(*) | | 1682 +----------++----------+-----------+-----------+-----------+-----------+ 1683 | ||-> J state| - | -> NI | -> P state| -> J state| 1684 | || | | state | | | 1685 |Join- ||add reg | | | set | add reg | 1686 |Pending ||tunnel | | | Register- | tunnel; | 1687 |(JP) || | | | Stop | cancel | 1688 | || | | | Timer(*) | Register- | 1689 | || | | | | Stop Timer| 1690 +----------++----------+-----------+-----------+-----------+-----------+ 1691 | ||-> JP | - | -> NI | - | -> J state| 1692 | ||state | | state | | | 1693 | ||set | | | | add reg | 1694 |Prune (P) ||Register- | | | | tunnel; | 1695 | ||Stop | | | | cancel | 1696 | ||Timer(**);| | | | Register- | 1697 | ||send Null-| | | | Stop Timer| 1698 | ||Register | | | | | 1699 +----------++----------+-----------+-----------+-----------+-----------+ 1700 Notes: 1702 (*) The Register-Stop Timer is set to a random value chosen 1703 uniformly from the interval ( 0.5 * Register_Suppression_Time, 1704 1.5 * Register_Suppression_Time) minus Register_Probe_Time. 1706 Subtracting off Register_Probe_Time is a bit unnecessary because 1707 it is really small compared to Register_Suppression_Time, but 1708 this was in the old spec and is kept for compatibility. 1710 (**) The Register-Stop Timer is set to Register_Probe_Time. 1712 The following three actions are defined: 1714 Add Register Tunnel 1716 A Register-Tunnel virtual interface, VI, is created (if it doesn't 1717 already exist) with its encapsulation target being RP(G). 1718 DownstreamJPState(S,G,VI) is set to Join state, causing the tunnel 1719 interface to be added to immediate_olist(S,G) and 1720 inherited_olist(S,G). 1722 Remove Register Tunnel 1724 VI is the Register-Tunnel virtual interface with encapsulation 1725 target of RP(G). DownstreamJPState(S,G,VI) is set to NoInfo 1726 state, causing the tunnel interface to be removed from 1727 immediate_olist(S,G) and inherited_olist(S,G). If 1728 DownstreamJPState(S,G,VI) is NoInfo for all (S,G), then VI can be 1729 deleted. 1731 Update Register Tunnel 1733 This action occurs when RP(G) changes. 1735 VI_old is the Register-Tunnel virtual interface with encapsulation 1736 target old_RP(G). A Register-Tunnel virtual interface, VI_new, is 1737 created (if it doesn't already exist) with its encapsulation 1738 target being new_RP(G). DownstreamJPState(S,G,VI_old) is set to 1739 NoInfo state and DownstreamJPState(S,G,VI_new) is set to Join 1740 state. If DownstreamJPState(S,G,VI_old) is NoInfo for all (S,G), 1741 then VI_old can be deleted. 1743 Note that we cannot simply change the encapsulation target of 1744 VI_old because not all groups using that encapsulation tunnel will 1745 have moved to the same new RP. 1747 CouldRegister(S,G) 1749 The macro "CouldRegister" in the state machine is defined as: 1751 bool CouldRegister(S,G) { 1752 return ( I_am_DR( RPF_interface(S) ) AND 1753 KeepaliveTimer(S,G) is running AND 1754 DirectlyConnected(S) == TRUE ) 1755 } 1757 Note that on reception of a packet at the DR from a directly 1758 connected source, KeepaliveTimer(S,G) needs to be set by the 1759 packet forwarding rules before computing CouldRegister(S,G) in the 1760 register state machine, or the first packet from a source won't be 1761 registered. 1763 Encapsulating Data Packets in the Register Tunnel 1765 Conceptually, the Register Tunnel is an interface with a smaller 1766 MTU than the underlying IP interface towards the RP. IP 1767 fragmentation on packets forwarded on the Register Tunnel is 1768 performed based upon this smaller MTU. The encapsulating DR may 1769 perform Path MTU Discovery to the RP to determine the effective 1770 MTU of the tunnel. Fragmentation for the smaller MTU should take 1771 both the outer IP header and the PIM register header overhead into 1772 account. If a multicast packet is fragmented on the way into the 1773 Register Tunnel, each fragment is encapsulated individually so it 1774 contains IP, PIM, and inner IP headers. 1776 In IPv6, the DR MUST perform Path MTU discovery, and an ICMP 1777 Packet Too Big message MUST be sent by the encapsulating DR if it 1778 receives a packet that will not fit in the effective MTU of the 1779 tunnel. If the MTU between the DR and the RP results in the 1780 effective tunnel MTU being smaller than 1280 (the IPv6 minimum 1781 MTU), the DR MUST send Fragmentation Required messages with an MTU 1782 value of 1280 and MUST fragment its PIM register messages as 1783 required, using an IPv6 fragmentation header between the outer 1784 IPv6 header and the PIM Register header. 1786 The TTL of a forwarded data packet is decremented before it is 1787 encapsulated in the Register Tunnel. The encapsulating packet 1788 uses the normal TTL that the router would use for any locally- 1789 generated IP packet. 1791 The IP ECN bits should be copied from the original packet to the 1792 IP header of the encapsulating packet. They SHOULD NOT be set 1793 independently by the encapsulating router. 1795 The Diffserv Code Point (DSCP) should be copied from the original 1796 packet to the IP header of the encapsulating packet. It MAY be 1797 set independently by the encapsulating router, based upon static 1798 configuration or traffic classification. See [12] for more 1799 discussion on setting the DSCP on tunnels. 1801 Handling Register-Stop(*,G) Messages at the DR 1803 An old RP might send a Register-Stop message with the source 1804 address set to all zeros. This was the normal course of action in 1805 RFC 2362 when the Register message matched against (*,G) state at 1806 the RP, and it was defined as meaning "stop encapsulating all 1807 sources for this group". However, the behavior of such a 1808 Register-Stop(*,G) is ambiguous or incorrect in some 1809 circumstances. 1811 We specify that an RP should not send Register-Stop(*,G) messages, 1812 but for compatibility, a DR should be able to accept one if it is 1813 received. 1815 A Register-Stop(*,G) should be treated as a Register-Stop(S,G) for 1816 all (S,G) Register state machines that are not in the NoInfo 1817 state. A router should not apply a Register-Stop(*,G) to sources 1818 that become active after the Register-Stop(*,G) was received. 1820 4.4.2. Receiving Register Messages at the RP 1822 When an RP receives a Register message, the course of action is 1823 decided according to the following pseudocode: 1825 packet_arrives_on_rp_tunnel( pkt ) { 1826 if( outer.dst is not one of my addresses ) { 1827 drop the packet silently. 1828 # Note: this may be a spoofing attempt 1829 } 1830 if( I_am_RP(G) AND outer.dst == RP(G) ) { 1831 sentRegisterStop = FALSE; 1832 if ( SPTbit(S,G) OR 1833 ( SwitchToSptDesired(S,G) AND 1834 ( inherited_olist(S,G) == NULL ))) { 1835 send Register-Stop(S,G) to outer.src 1836 sentRegisterStop = TRUE; 1837 } 1838 if ( SPTbit(S,G) OR SwitchToSptDesired(S,G) ) { 1839 if ( sentRegisterStop == TRUE ) { 1840 set KeepaliveTimer(S,G) to RP_Keepalive_Period; 1841 } else { 1842 set KeepaliveTimer(S,G) to Keepalive_Period; 1843 } 1844 } 1845 if( !SPTbit(S,G) AND ! pkt.NullRegisterBit ) { 1846 decapsulate and forward the inner packet to 1847 inherited_olist(S,G,rpt) # Note (+) 1848 } 1849 } else { 1850 send Register-Stop(S,G) to outer.src 1851 # Note (*) 1852 } 1853 } 1854 outer.dst is the IP destination address of the encapsulating header. 1856 outer.src is the IP source address of the encapsulating header, i.e., 1857 the DR's address. 1859 I_am_RP(G) is true if the group-to-RP mapping indicates that this 1860 router is the RP for the group. 1862 Note (*): This may block traffic from S for Register_Suppression_Time 1863 if the DR learned about a new group-to-RP mapping before the RP 1864 did. However, this doesn't matter unless we figure out some way 1865 for the RP also to accept (*,G) joins when it doesn't yet realize 1866 that it is about to become the RP for G. This will all get sorted 1867 out once the RP learns the new group-to-rp mapping. We decided to 1868 do nothing about this and just accept the fact that PIM may suffer 1869 interrupted (*,G) connectivity following an RP change. 1871 Note (+): Implementations SHOULD NOT make this a special case, but to 1872 arrange that this path rejoin the normal packet forwarding path. 1873 All of the appropriate actions from the "On receipt of data from S 1874 to G on interface iif" pseudocode in Section 4.2 should be 1875 performed. 1877 KeepaliveTimer(S,G) is restarted at the RP when packets arrive on the 1878 proper tunnel interface and the RP desires to switch to the SPT or 1879 the SPTbit is already set. This may cause the upstream (S,G) state 1880 machine to trigger a join if the inherited_olist(S,G) is not NULL. 1882 An RP should preserve (S,G) state that was created in response to a 1883 Register message for at least ( 3 * Register_Suppression_Time ); 1884 otherwise, the RP may stop joining (S,G) before the DR for S has 1885 restarted sending registers. Traffic would then be interrupted until 1886 the Register-Stop Timer expires at the DR. 1888 Thus, at the RP, KeepaliveTimer(S,G) should be restarted to ( 3 * 1889 Register_Suppression_Time + Register_Probe_Time ). 1891 When forwarding a packet from the Register Tunnel, the TTL of the 1892 original data packet is decremented after it is decapsulated. 1894 The IP ECN bits should be copied from the IP header of the Register 1895 packet to the decapsulated packet. 1897 The Diffserv Code Point (DSCP) should be copied from the IP header of 1898 the Register packet to the decapsulated packet. The RP MAY retain 1899 the DSCP of the inner packet or re-classify the packet and apply a 1900 different DSCP. Scenarios where each of these might be useful are 1901 discussed in [12]. 1903 4.5. PIM Join/Prune Messages 1905 A PIM Join/Prune message consists of a list of groups and a list of 1906 Joined and Pruned sources for each group. When processing a received 1907 Join/Prune message, each Joined or Pruned source for a Group is 1908 effectively considered individually, and applies to one or more of 1909 the following state machines. When considering a Join/Prune message 1910 whose Upstream Neighbor Address field addresses this router, (*,G) 1911 Joins and Prunes can affect both the (*,G) and (S,G,rpt) downstream 1912 state machines, while (S,G), and (S,G,rpt) Joins and Prunes can only 1913 affect their respective downstream state machines. When considering 1914 a Join/Prune message whose Upstream Neighbor Address field addresses 1915 another router, most Join or Prune messages could affect each 1916 upstream state machine. 1918 In general, a PIM Join/Prune message should only be accepted for 1919 processing if it comes from a known PIM neighbor. A PIM router hears 1920 about PIM neighbors through PIM Hello messages. If a router receives 1921 a Join/Prune message from a particular IP source address and it has 1922 not seen a PIM Hello message from that source address, then the 1923 Join/Prune message SHOULD be discarded without further processing. 1924 In addition, if the Hello message from a neighbor was authenticated 1925 using IPsec AH (see Section 6.3), then all Join/Prune messages from 1926 that neighbor MUST also be authenticated using IPsec AH. 1928 We note that some older PIM implementations incorrectly fail to send 1929 Hello messages on point-to-point interfaces, so we also RECOMMEND 1930 that a configuration option be provided to allow interoperation with 1931 such older routers, but that this configuration option SHOULD NOT be 1932 enabled by default. 1934 4.5.1. Receiving (*,G) Join/Prune Messages 1936 When a router receives a Join(*,G), it must first check to see 1937 whether the RP in the message matches RP(G) (the router's idea of who 1938 the RP is). If the RP in the message does not match RP(G), the 1939 Join(*,G) should be silently dropped. (Note that other source list 1940 entries, such as (S,G,rpt) or (S,G), in the same Group-Specific Set 1941 should still be processed.) If a router has no RP information (e.g., 1942 has not recently received a BSR message), then it may choose to 1943 accept Join(*,G) and treat 1944 the RP in the message as RP(G). Received Prune(*,G) messages are 1945 processed even if the RP in the message does not match RP(G). 1947 The per-interface state machine for receiving (*,G) Join/Prune 1948 Messages is given below. There are three states: 1950 NoInfo (NI) 1951 The interface has no (*,G) Join state and no timers running. 1953 Join (J) 1954 The interface has (*,G) Join state, which will cause the 1955 router to forward packets destined for G from this interface 1956 except if there is also (S,G,rpt) prune information (see 1957 Section 4.5.3) or the router lost an assert on this interface. 1959 Prune-Pending (PP) 1960 The router has received a Prune(*,G) on this interface from a 1961 downstream neighbor and is waiting to see whether the prune 1962 will be overridden by another downstream router. For 1963 forwarding purposes, the Prune-Pending state functions exactly 1964 like the Join state. 1966 In addition, the state machine uses two timers: 1968 Expiry Timer (ET) 1969 This timer is restarted when a valid Join(*,G) is received. 1970 Expiry of the Expiry Timer causes the interface state to 1971 revert to NoInfo for this group. 1973 Prune-Pending Timer (PPT) 1974 This timer is set when a valid Prune(*,G) is received. Expiry 1975 of the Prune-Pending Timer causes the interface state to 1976 revert to NoInfo for this group. 1978 Figure 2: Downstream per-interface (*,G) state machine in tabular form 1980 +------------++--------------------------------------------------------+ 1981 | || Event | 1982 | ++-------------+--------------+-------------+-------------+ 1983 |Prev State ||Receive | Receive | Prune- | Expiry Timer| 1984 | ||Join(*,G) | Prune(*,G) | Pending | Expires | 1985 | || | | Timer | | 1986 | || | | Expires | | 1987 +------------++-------------+--------------+-------------+-------------+ 1988 | ||-> J state | -> NI state | - | - | 1989 |NoInfo (NI) ||start Expiry | | | | 1990 | ||Timer | | | | 1991 +------------++-------------+--------------+-------------+-------------+ 1992 | ||-> J state | -> PP state | - | -> NI state | 1993 |Join (J) ||restart | start Prune- | | | 1994 | ||Expiry Timer | Pending | | | 1995 | || | Timer | | | 1996 +------------++-------------+--------------+-------------+-------------+ 1997 |Prune- ||-> J state | -> PP state | -> NI state | -> NI state | 1998 |Pending (PP)||restart | | Send Prune- | | 1999 | ||Expiry Timer | | Echo(*,G) | | 2000 +------------++-------------+--------------+-------------+-------------+ 2002 The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" 2003 imply receiving a Join or Prune targeted to this router's primary IP 2004 address on the received interface. If the upstream neighbor address 2005 field is not correct, these state transitions in this state machine 2006 MUST NOT occur, although seeing such a packet may cause state 2007 transitions in other state machines. 2009 On unnumbered interfaces on point-to-point links, the router's 2010 address should be the same as the source address it chose for the 2011 Hello message it sent over that interface. However, on point-to- 2012 point links it is RECOMMENDED that for backwards compatibility PIM 2013 Join/Prune messages with an upstream neighbor address field of all 2014 zeros also be accepted. 2016 Transitions from NoInfo State 2018 When in NoInfo state, the following event may trigger a transition: 2020 Receive Join(*,G) 2021 A Join(*,G) is received on interface I with its Upstream 2022 Neighbor Address set to the router's primary IP address on I. 2024 The (*,G) downstream state machine on interface I transitions 2025 to the Join state. The Expiry Timer (ET) is started and set 2026 to the HoldTime from the triggering Join/Prune message. 2028 Transitions from Join State 2030 When in Join state, the following events may trigger a transition: 2032 Receive Join(*,G) 2033 A Join(*,G) is received on interface I with its Upstream 2034 Neighbor Address set to the router's primary IP address on I. 2036 The (*,G) downstream state machine on interface I remains in 2037 Join state, and the Expiry Timer (ET) is restarted, set to 2038 maximum of its current value and the HoldTime from the 2039 triggering Join/Prune message. 2041 Receive Prune(*,G) 2042 A Prune(*,G) is received on interface I with its Upstream 2043 Neighbor Address set to the router's primary IP address on I. 2045 The (*,G) downstream state machine on interface I transitions 2046 to the Prune-Pending state. The Prune-Pending Timer is 2047 started. It is set to the J/P_Override_Interval(I) if the 2048 router has more than one neighbor on that interface; 2049 otherwise, it is set to zero, causing it to expire 2050 immediately. 2052 Expiry Timer Expires 2053 The Expiry Timer for the (*,G) downstream state machine on 2054 interface I expires. 2056 The (*,G) downstream state machine on interface I transitions 2057 to the NoInfo state. 2059 Transitions from Prune-Pending State 2061 When in Prune-Pending state, the following events may trigger a 2062 transition: 2064 Receive Join(*,G) 2065 A Join(*,G) is received on interface I with its Upstream 2066 Neighbor Address set to the router's primary IP address on I. 2068 The (*,G) downstream state machine on interface I transitions 2069 to the Join state. The Prune-Pending Timer is canceled 2070 (without triggering an expiry event). The Expiry Timer is 2071 restarted, set to maximum of its current value and the 2072 HoldTime from the triggering Join/Prune message. 2074 Expiry Timer Expires 2075 The Expiry Timer for the (*,G) downstream state machine on 2076 interface I expires. 2078 The (*,G) downstream state machine on interface I transitions 2079 to the NoInfo state. 2081 Prune-Pending Timer Expires 2082 The Prune-Pending Timer for the (*,G) downstream state machine 2083 on interface I expires. 2085 The (*,G) downstream state machine on interface I transitions 2086 to the NoInfo state. A PruneEcho(*,G) is sent onto the subnet 2087 connected to interface I. 2089 The action "Send PruneEcho(*,G)" is triggered when the router 2090 stops forwarding on an interface as a result of a prune. A 2091 PruneEcho(*,G) is simply a Prune(*,G) message sent by the 2092 upstream router on a LAN with its own address in the Upstream 2093 Neighbor Address field. Its purpose is to add additional 2094 reliability so that if a Prune that should have been 2095 overridden by another router is lost locally on the LAN, then 2096 the PruneEcho may be received and cause the override to 2097 happen. A PruneEcho(*,G) need not be sent on an interface 2098 that contains only a single PIM neighbor during the time this 2099 state machine was in Prune-Pending state. 2101 4.5.2. Receiving (S,G) Join/Prune Messages 2103 The per-interface state machine for receiving (S,G) Join/Prune 2104 messages is given below and is almost identical to that for (*,G) 2105 messages. There are three states: 2107 NoInfo (NI) 2108 The interface has no (S,G) Join state and no (S,G) timers 2109 running. 2111 Join (J) 2112 The interface has (S,G) Join state, which will cause the 2113 router to forward packets from S destined for G from this 2114 interface if the (S,G) state is active (the SPTbit is set) 2115 except if the router lost an assert on this interface. 2117 Prune-Pending (PP) 2118 The router has received a Prune(S,G) on this interface from a 2119 downstream neighbor and is waiting to see whether the prune 2120 will be overridden by another downstream router. For 2121 forwarding purposes, the Prune-Pending state functions exactly 2122 like the Join state. 2124 In addition, there are two timers: 2126 Expiry Timer (ET) 2127 This timer is set when a valid Join(S,G) is received. Expiry 2128 of the Expiry Timer causes this state machine to revert to 2129 NoInfo state. 2131 Prune-Pending Timer (PPT) 2132 This timer is set when a valid Prune(S,G) is received. Expiry 2133 of the Prune-Pending Timer causes this state machine to revert 2134 to NoInfo state. 2136 Figure 3: Downstream per-interface (S,G) state machine in tabular form 2138 +------------++--------------------------------------------------------+ 2139 | || Event | 2140 | ++-------------+--------------+-------------+-------------+ 2141 |Prev State ||Receive | Receive | Prune- | Expiry Timer| 2142 | ||Join(S,G) | Prune(S,G) | Pending | Expires | 2143 | || | | Timer | | 2144 | || | | Expires | | 2145 +------------++-------------+--------------+-------------+-------------+ 2146 | ||-> J state | -> NI state | - | - | 2147 |NoInfo (NI) ||start Expiry | | | | 2148 | ||Timer | | | | 2149 +------------++-------------+--------------+-------------+-------------+ 2150 | ||-> J state | -> PP state | - | -> NI state | 2151 |Join (J) ||restart | start Prune- | | | 2152 | ||Expiry Timer | Pending | | | 2153 | || | Timer | | | 2154 +------------++-------------+--------------+-------------+-------------+ 2155 |Prune- ||-> J state | -> PP state | -> NI state | -> NI state | 2156 |Pending (PP)||restart | | Send Prune- | | 2157 | ||Expiry Timer | | Echo(S,G) | | 2158 +------------++-------------+--------------+-------------+-------------+ 2160 The transition events "Receive Join(S,G)" and "Receive Prune(S,G)" 2161 imply receiving a Join or Prune targeted to this router's primary IP 2162 address on the received interface. If the upstream neighbor address 2163 field is not correct, these state transitions in this state machine 2164 MUST NOT occur, although seeing such a packet may cause state 2165 transitions in other state machines. 2167 On unnumbered interfaces on point-to-point links, the router's 2168 address SHOULD be the same as the source address it chose for the 2169 Hello message it sent over that interface. However, on point-to- 2170 point links it is RECOMMENDED that for backwards compatibility PIM 2171 Join/Prune messages with an upstream neighbor address field of all 2172 zeros also be accepted. 2174 Transitions from NoInfo State 2176 When in NoInfo state, the following event may trigger a transition: 2178 Receive Join(S,G) 2179 A Join(S,G) is received on interface I with its Upstream 2180 Neighbor Address set to the router's primary IP address on I. 2182 The (S,G) downstream state machine on interface I transitions 2183 to the Join state. The Expiry Timer (ET) is started and set 2184 to the HoldTime from the triggering Join/Prune message. 2186 Transitions from Join State 2188 When in Join state, the following events may trigger a transition: 2190 Receive Join(S,G) 2191 A Join(S,G) is received on interface I with its Upstream 2192 Neighbor Address set to the router's primary IP address on I. 2194 The (S,G) downstream state machine on interface I remains in 2195 Join state, and the Expiry Timer (ET) is restarted, set to 2196 maximum of its current value and the HoldTime from the 2197 triggering Join/Prune message. 2199 Receive Prune(S,G) 2200 A Prune(S,G) is received on interface I with its Upstream 2201 Neighbor Address set to the router's primary IP address on I. 2203 The (S,G) downstream state machine on interface I transitions 2204 to the Prune-Pending state. The Prune-Pending Timer is 2205 started. It is set to the J/P_Override_Interval(I) if the 2206 router has more than one neighbor on that interface; 2207 otherwise, it is set to zero, causing it to expire 2208 immediately. 2210 Expiry Timer Expires 2211 The Expiry Timer for the (S,G) downstream state machine on 2212 interface I expires. 2214 The (S,G) downstream state machine on interface I transitions 2215 to the NoInfo state. 2217 Transitions from Prune-Pending State 2219 When in Prune-Pending state, the following events may trigger a 2220 transition: 2222 Receive Join(S,G) 2223 A Join(S,G) is received on interface I with its Upstream 2224 Neighbor Address set to the router's primary IP address on I. 2226 The (S,G) downstream state machine on interface I transitions 2227 to the Join state. The Prune-Pending Timer is canceled 2228 (without triggering an expiry event). The Expiry Timer is 2229 restarted, set to maximum of its current value and the 2230 HoldTime from the triggering Join/Prune message. 2232 Expiry Timer Expires 2233 The Expiry Timer for the (S,G) downstream state machine on 2234 interface I expires. 2236 The (S,G) downstream state machine on interface I transitions 2237 to the NoInfo state. 2239 Prune-Pending Timer Expires 2240 The Prune-Pending Timer for the (S,G) downstream state machine 2241 on interface I expires. 2243 The (S,G) downstream state machine on interface I transitions 2244 to the NoInfo state. A PruneEcho(S,G) is sent onto the subnet 2245 connected to interface I. 2247 The action "Send PruneEcho(S,G)" is triggered when the router 2248 stops forwarding on an interface as a result of a prune. A 2249 PruneEcho(S,G) is simply a Prune(S,G) message sent by the 2250 upstream router on a LAN with its own address in the Upstream 2251 Neighbor Address field. Its purpose is to add additional 2252 reliability so that if a Prune that should have been 2253 overridden by another router is lost locally on the LAN, then 2254 the PruneEcho may be received and cause the override to 2255 happen. A PruneEcho(S,G) need not be sent on an interface 2256 that contains only a single PIM neighbor during the time this 2257 state machine was in Prune-Pending state. 2259 4.5.3. Receiving (S,G,rpt) Join/Prune Messages 2261 The per-interface state machine for receiving (S,G,rpt) Join/Prune 2262 messages is given below. There are five states: 2264 NoInfo (NI) 2265 The interface has no (S,G,rpt) Prune state and no (S,G,rpt) 2266 timers running. 2268 Prune (P) 2269 The interface has (S,G,rpt) Prune state, which will cause the 2270 router not to forward packets from S destined for G from this 2271 interface even though the interface has active (*,G) Join 2272 state. 2274 Prune-Pending (PP) 2275 The router has received a Prune(S,G,rpt) on this interface 2276 from a downstream neighbor and is waiting to see whether the 2277 prune will be overridden by another downstream router. For 2278 forwarding purposes, the Prune-Pending state functions exactly 2279 like the NoInfo state. 2281 PruneTmp (P') 2282 This state is a transient state that for forwarding purposes 2283 behaves exactly like the Prune state. A (*,G) Join has been 2284 received (which may cancel the (S,G,rpt) Prune). As we parse 2285 the Join/Prune message from top to bottom, we first enter this 2286 state if the message contains a (*,G) Join. Later in the 2287 message, we will normally encounter an (S,G,rpt) prune to 2288 reinstate the Prune state. However, if we reach the end of 2289 the message without encountering such an (S,G,rpt) prune, then 2290 we will revert to NoInfo state in this state machine. 2292 As no time is spent in this state, no timers can expire. 2294 Prune-Pending-Tmp (PP') 2295 This state is a transient state that is identical to P' except 2296 that it is associated with the PP state rather than the P 2297 state. For forwarding purposes, PP' behaves exactly like PP 2298 state. 2300 In addition, there are two timers: 2302 Expiry Timer (ET) 2303 This timer is set when a valid Prune(S,G,rpt) is received. 2304 Expiry of the Expiry Timer causes this state machine to revert 2305 to NoInfo state. 2307 Prune-Pending Timer (PPT) 2308 This timer is set when a valid Prune(S,G,rpt) is received. 2309 Expiry of the Prune-Pending Timer causes this state machine to 2310 move on to Prune state. 2312 Figure 4: Downstream per-interface (S,G,rpt) state machine 2313 in tabular form 2315 +----------++----------------------------------------------------------+ 2316 | || Event | 2317 | ++---------+----------+----------+--------+--------+--------+ 2318 |Prev ||Receive | Receive | Receive | End of | Prune- | Expiry | 2319 |State ||Join(*,G)| Join | Prune | Message| Pending| Timer | 2320 | || | (S,G,rpt)| (S,G,rpt)| | Timer | Expires| 2321 | || | | | | Expires| | 2322 +----------++---------+----------+----------+--------+--------+--------+ 2323 | ||- | - | -> PP | - | - | - | 2324 | || | | state | | | | 2325 | || | | start | | | | 2326 |NoInfo || | | Prune- | | | | 2327 |(NI) || | | Pending | | | | 2328 | || | | Timer; | | | | 2329 | || | | start | | | | 2330 | || | | Expiry | | | | 2331 | || | | Timer | | | | 2332 +----------++---------+----------+----------+--------+--------+--------+ 2333 | ||-> P' | -> NI | -> P | - | - | -> NI | 2334 | ||state | state | state | | | state | 2335 |Prune (P) || | | restart | | | | 2336 | || | | Expiry | | | | 2337 | || | | Timer | | | | 2338 +----------++---------+----------+----------+--------+--------+--------+ 2339 |Prune- ||-> PP' | -> NI | - | - | -> P | - | 2340 |Pending ||state | state | | | state | | 2341 |(PP) || | | | | | | 2342 +----------++---------+----------+----------+--------+--------+--------+ 2343 | ||- | - | -> P | -> NI | - | - | 2344 |PruneTmp || | | state | state | | | 2345 |(P') || | | restart | | | | 2346 | || | | Expiry | | | | 2347 | || | | Timer | | | | 2348 +----------++---------+----------+----------+--------+--------+--------+ 2349 | ||- | - | -> PP | -> NI | - | - | 2350 |Prune- || | | state | state | | | 2351 |Pending- || | | restart | | | | 2352 |Tmp (PP') || | | Expiry | | | | 2353 | || | | Timer | | | | 2354 +----------++---------+----------+----------+--------+--------+--------+ 2356 The transition events "Receive Join(S,G,rpt)", "Receive 2357 Prune(S,G,rpt)", and "Receive Join(*,G)" imply receiving a Join or 2358 Prune targeted to this router's primary IP address on the received 2359 interface. If the upstream neighbor address field is not correct, 2360 these state transitions in this state machine MUST NOT occur, 2361 although seeing such a packet may cause state transitions in other 2362 state machines. 2364 On unnumbered interfaces on point-to-point links, the router's 2365 address should be the same as the source address it chose for the 2366 Hello message it sent over that interface. However, on point-to- 2367 point links it is RECOMMENDED that PIM Join/Prune messages with an 2368 upstream neighbor address field of all zeros also be accepted. 2370 Transitions from NoInfo State 2372 When in NoInfo (NI) state, the following event may trigger a 2373 transition: 2375 Receive Prune(S,G,rpt) 2376 A Prune(S,G,rpt) is received on interface I with its Upstream 2377 Neighbor Address set to the router's primary IP address on I. 2379 The (S,G,rpt) downstream state machine on interface I 2380 transitions to the Prune-Pending state. The Expiry Timer (ET) 2381 is started and set to the HoldTime from the triggering 2382 Join/Prune message. The Prune-Pending Timer is started. It 2383 is set to the J/P_Override_Interval(I) if the router has more 2384 than one neighbor on that interface; otherwise, it is set to 2385 zero, causing it to expire immediately. 2387 Transitions from Prune-Pending State 2389 When in Prune-Pending (PP) state, the following events may trigger a 2390 transition: 2392 Receive Join(*,G) 2393 A Join(*,G) is received on interface I with its Upstream 2394 Neighbor Address set to the router's primary IP address on I. 2396 The (S,G,rpt) downstream state machine on interface I 2397 transitions to Prune-Pending-Tmp state whilst the remainder of 2398 the compound Join/Prune message containing the Join(*,G) is 2399 processed. 2401 Receive Join(S,G,rpt) 2402 A Join(S,G,rpt) is received on interface I with its Upstream 2403 Neighbor Address set to the router's primary IP address on I. 2405 The (S,G,rpt) downstream state machine on interface I 2406 transitions to NoInfo state. ET and PPT are canceled. 2408 Prune-Pending Timer Expires 2409 The Prune-Pending Timer for the (S,G,rpt) downstream state 2410 machine on interface I expires. 2412 The (S,G,rpt) downstream state machine on interface I 2413 transitions to the Prune state. 2415 Transitions from Prune State 2417 When in Prune (P) state, the following events may trigger a 2418 transition: 2420 Receive Join(*,G) 2421 A Join(*,G) is received on interface I with its Upstream 2422 Neighbor Address set to the router's primary IP address on I. 2424 The (S,G,rpt) downstream state machine on interface I 2425 transitions to PruneTmp state whilst the remainder of the 2426 compound Join/Prune message containing the Join(*,G) is 2427 processed. 2429 Receive Join(S,G,rpt) 2430 A Join(S,G,rpt) is received on interface I with its Upstream 2431 Neighbor Address set to the router's primary IP address on I. 2433 The (S,G,rpt) downstream state machine on interface I 2434 transitions to NoInfo state. ET and PPT are canceled. 2436 Receive Prune(S,G,rpt) 2437 A Prune(S,G,rpt) is received on interface I with its Upstream 2438 Neighbor Address set to the router's primary IP address on I. 2440 The (S,G,rpt) downstream state machine on interface I remains 2441 in Prune state. The Expiry Timer (ET) is restarted, set to 2442 maximum of its current value and the HoldTime from the 2443 triggering Join/Prune message. 2445 Expiry Timer Expires 2446 The Expiry Timer for the (S,G,rpt) downstream state machine on 2447 interface I expires. 2449 The (S,G,rpt) downstream state machine on interface I 2450 transitions to the NoInfo state. 2452 Transitions from Prune-Pending-Tmp State 2454 When in Prune-Pending-Tmp (PP') state and processing a compound 2455 Join/Prune message, the following events may trigger a transition: 2457 Receive Prune(S,G,rpt) 2458 The compound Join/Prune message contains a Prune(S,G,rpt) that 2459 is received on interface I with its Upstream Neighbor Address 2460 set to the router's primary IP address on I. 2462 The (S,G,rpt) downstream state machine on interface I 2463 transitions back to the Prune-Pending state. The Expiry Timer 2464 (ET) is restarted, set to maximum of its current value and the 2465 HoldTime from the triggering Join/Prune message. 2467 End of Message 2468 The end of the compound Join/Prune message is reached. 2470 The (S,G,rpt) downstream state machine on interface I 2471 transitions to the NoInfo state. ET and PPT are canceled. 2473 Transitions from PruneTmp State 2475 When in PruneTmp (P') state and processing a compound Join/Prune 2476 message, the following events may trigger a transition: 2478 Receive Prune(S,G,rpt) 2479 The compound Join/Prune message contains a Prune(S,G,rpt). 2481 The (S,G,rpt) downstream state machine on interface I 2482 transitions back to the Prune state. The Expiry Timer (ET) is 2483 restarted, set to maximum of its current value and the 2484 HoldTime from the triggering Join/Prune message. 2486 End of Message 2487 The end of the compound Join/Prune message is reached. 2489 The (S,G,rpt) downstream state machine on interface I 2490 transitions to the NoInfo state. ET is canceled. 2492 Notes: 2494 Receiving a Prune(*,G) does not affect the (S,G,rpt) downstream state 2495 machine. 2497 4.5.4. Sending (*,G) Join/Prune Messages 2499 The per-interface state machines for (*,G) hold join state from 2500 downstream PIM routers. This state then determines whether a router 2501 needs to propagate a Join(*,G) upstream towards the RP. 2503 If a router wishes to propagate a Join(*,G) upstream, it must also 2504 watch for messages on its upstream interface from other routers on 2505 that subnet, and these may modify its behavior. If it sees a 2506 Join(*,G) to the correct upstream neighbor, it should suppress its 2507 own Join(*,G). If it sees a Prune(*,G) to the correct upstream 2508 neighbor, it should be prepared to override that prune by sending a 2509 Join(*,G) almost immediately. Finally, if it sees the Generation ID 2510 (see Section 4.3) of the correct upstream neighbor change, it knows 2511 that the upstream neighbor has lost state, and it should be prepared 2512 to refresh the state by sending a Join(*,G) almost immediately. 2514 If a (*,G) Assert occurs on the upstream interface, and this changes 2515 this router's idea of the upstream neighbor, it should be prepared to 2516 ensure that the Assert winner is aware of downstream routers by 2517 sending a Join(*,G) almost immediately. 2519 In addition, if the MRIB changes to indicate that the next hop 2520 towards the RP has changed, and either the upstream interface changes 2521 or there is no Assert winner on the upstream interface, the router 2522 should prune off from the old next hop and join towards the new next 2523 hop. 2525 The upstream (*,G) state machine only contains two states: 2527 Not Joined 2528 The downstream state machines indicate that the router does not 2529 need to join the RP tree for this group. 2531 Joined 2532 The downstream state machines indicate that the router should join 2533 the RP tree for this group. 2535 In addition, one timer JT(*,G) is kept that is used to trigger the 2536 sending of a Join(*,G) to the upstream next hop towards the RP, 2537 RPF'(*,G). 2539 Figure 5: Upstream (*,G) state machine in tabular form 2541 +-------------------++-------------------------------------------------+ 2542 | || Event | 2543 | Prev State ++------------------------+------------------------+ 2544 | || JoinDesired(*,G) | JoinDesired(*,G) | 2545 | || ->True | ->False | 2546 +-------------------++------------------------+------------------------+ 2547 | || -> J state | - | 2548 | NotJoined (NJ) || Send Join(*,G); | | 2549 | || Set Join Timer to | | 2550 | || t_periodic | | 2551 +-------------------++------------------------+------------------------+ 2552 | Joined (J) || - | -> NJ state | 2553 | || | Send Prune(*,G); | 2554 | || | Cancel Join Timer | 2555 +-------------------++------------------------+------------------------+ 2557 In addition, we have the following transitions, which occur within 2558 the Joined state: 2560 +----------------------------------------------------------------------+ 2561 | In Joined (J) State | 2562 +----------------+-----------------+-----------------+-----------------+ 2563 |Timer Expires | See Join(*,G) | See Prune(*,G) | RPF'(*,G) | 2564 | | to RPF'(*,G) | to RPF'(*,G) | changes due to | 2565 | | | | an Assert | 2566 +----------------+-----------------+-----------------+-----------------+ 2567 |Send | Increase Join | Decrease Join | Decrease Join | 2568 |Join(*,G); Set | Timer to | Timer to | Timer to | 2569 |Join Timer to | t_joinsuppress | t_override | t_override | 2570 |t_periodic | | | | 2571 +----------------+-----------------+-----------------+-----------------+ 2573 +----------------------------------------------------------------------+ 2574 | In Joined (J) State | 2575 +----------------------------------+-----------------------------------+ 2576 | RPF'(*,G) changes not | RPF'(*,G) GenID changes | 2577 | due to an Assert | | 2578 +----------------------------------+-----------------------------------+ 2579 | Send Join(*,G) to new | Decrease Join Timer to | 2580 | next hop; Send | t_override | 2581 | Prune(*,G) to old next | | 2582 | hop; Set Join Timer to | | 2583 | t_periodic | | 2584 +----------------------------------+-----------------------------------+ 2585 This state machine uses the following macro: 2587 bool JoinDesired(*,G) { 2588 if (immediate_olist(*,G) != NULL) 2589 return TRUE 2590 else 2591 return FALSE 2592 } 2594 JoinDesired(*,G) is true when the router has forwarding state that 2595 would cause it to forward traffic for G using shared tree state. 2596 Note that although JoinDesired is true, the router's sending of a 2597 Join(*,G) message may be suppressed by another router sending a 2598 Join(*,G) onto the upstream interface. 2600 Transitions from NotJoined State 2602 When the upstream (*,G) state machine is in NotJoined state, the 2603 following event may trigger a state transition: 2605 JoinDesired(*,G) becomes True 2606 The macro JoinDesired(*,G) becomes True, e.g., because the 2607 downstream state for (*,G) has changed so that at least one 2608 interface is in immediate_olist(*,G). 2610 The upstream (*,G) state machine transitions to Joined state. 2611 Send Join(*,G) to the appropriate upstream neighbor, which is 2612 RPF'(*,G). Set the Join Timer (JT) to expire after t_periodic 2613 seconds. 2615 Transitions from Joined State 2617 When the upstream (*,G) state machine is in Joined state, the 2618 following events may trigger state transitions: 2620 JoinDesired(*,G) becomes False 2621 The macro JoinDesired(*,G) becomes False, e.g., because the 2622 downstream state for (*,G) has changed so no interface is in 2623 immediate_olist(*,G). 2625 The upstream (*,G) state machine transitions to NotJoined 2626 state. Send Prune(*,G) to the appropriate upstream neighbor, 2627 which is RPF'(*,G). Cancel the Join Timer (JT). 2629 Join Timer Expires 2630 The Join Timer (JT) expires, indicating time to send a 2631 Join(*,G) 2632 Send Join(*,G) to the appropriate upstream neighbor, which is 2633 RPF'(*,G). Restart the Join Timer (JT) to expire after 2634 t_periodic seconds. 2636 See Join(*,G) to RPF'(*,G) 2637 This event is only relevant if RPF_interface(RP(G)) is a 2638 shared medium. This router sees another router on 2639 RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G). This 2640 causes this router to suppress its own Join. 2642 The upstream (*,G) state machine remains in Joined state. 2644 Let t_joinsuppress be the minimum of t_suppressed and the 2645 HoldTime from the Join/Prune message triggering this event. If 2646 the Join Timer is set to expire in less than t_joinsuppress 2647 seconds, reset it so that it expires after t_joinsuppress 2648 seconds. If the Join Timer is set to expire in more than 2649 t_joinsuppress seconds, leave it unchanged. 2651 See Prune(*,G) to RPF'(*,G) 2652 This event is only relevant if RPF_interface(RP(G)) is a 2653 shared medium. This router sees another router on 2654 RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G). As this 2655 router is in Joined state, it must override the Prune after a 2656 short random interval. 2658 The upstream (*,G) state machine remains in Joined state. If 2659 the Join Timer is set to expire in more than t_override 2660 seconds, reset it so that it expires after t_override seconds. 2661 If the Join Timer is set to expire in less than t_override 2662 seconds, leave it unchanged. 2664 RPF'(*,G) changes due to an Assert 2665 The current next hop towards the RP changes due to an 2666 Assert(*,G) on the RPF_interface(RP(G)). 2668 The upstream (*,G) state machine remains in Joined state. If 2669 the Join Timer is set to expire in more than t_override 2670 seconds, reset it so that it expires after t_override seconds. 2671 If the Join Timer is set to expire in less than t_override 2672 seconds, leave it unchanged. 2674 RPF'(*,G) changes not due to an Assert 2675 An event occurred that caused the next hop towards the RP for 2676 G to change. This may be caused by a change in the MRIB 2677 routing database or the group-to-RP mapping. Note that this 2678 transition does not occur if an Assert is active and the 2679 upstream interface does not change. 2681 The upstream (*,G) state machine remains in Joined state. Send 2682 Join(*,G) to the new upstream neighbor, which is the new value 2683 of RPF'(*,G). Send Prune(*,G) to the old upstream neighbor, 2684 which is the old value of RPF'(*,G). Use the new value of 2685 RP(G) in the Prune(*,G) message or all zeros if RP(G) becomes 2686 unknown (old value of RP(G) may be used instead to improve 2687 behavior in routers implementing older versions of this spec). 2688 Set the Join Timer (JT) to expire after t_periodic seconds. 2690 RPF'(*,G) GenID changes 2691 The Generation ID of the router that is RPF'(*,G) changes. 2692 This normally means that this neighbor has lost state, and so 2693 the state must be refreshed. 2695 The upstream (*,G) state machine remains in Joined state. If 2696 the Join Timer is set to expire in more than t_override 2697 seconds, reset it so that it expires after t_override seconds. 2699 4.5.5. Sending (S,G) Join/Prune Messages 2701 The per-interface state machines for (S,G) hold join state from 2702 downstream PIM routers. This state then determines whether a router 2703 needs to propagate a Join(S,G) upstream towards the source. 2705 If a router wishes to propagate a Join(S,G) upstream, it must also 2706 watch for messages on its upstream interface from other routers on 2707 that subnet, and these may modify its behavior. If it sees a 2708 Join(S,G) to the correct upstream neighbor, it should suppress its 2709 own Join(S,G). If it sees a Prune(S,G), Prune(S,G,rpt), or 2710 Prune(*,G) to the correct upstream neighbor towards S, it should be 2711 prepared to override that prune by scheduling a Join(S,G) to be sent 2712 almost immediately. Finally, if it sees the Generation ID of its 2713 upstream neighbor change, it knows that the upstream neighbor has 2714 lost state, and it should refresh the state by scheduling a Join(S,G) 2715 to be sent almost immediately. 2717 If an (S,G) Assert occurs on the upstream interface, and this changes 2718 this router's idea of the upstream neighbor, it should be prepared to 2719 ensure that the Assert winner is aware of downstream routers by 2720 scheduling a Join(S,G) to be sent almost immediately. 2722 In addition, if MRIB changes cause the next hop towards the source to 2723 change, and either the upstream interface changes or there is no 2724 Assert winner on the upstream interface, the router should send a 2725 prune to the old next hop and a join to the new next hop. 2727 The upstream (S,G) state machine only contains two states: 2729 Not Joined 2730 The downstream state machines and local membership information do 2731 not indicate that the router needs to join the shortest-path tree 2732 for this (S,G). 2734 Joined 2735 The downstream state machines and local membership information 2736 indicate that the router should join the shortest-path tree for 2737 this (S,G). 2739 In addition, one timer JT(S,G) is kept that is used to trigger the 2740 sending of a Join(S,G) to the upstream next hop towards S, RPF'(S,G). 2742 Figure 6: Upstream (S,G) state machine in tabular form 2744 +-------------------+--------------------------------------------------+ 2745 | | Event | 2746 | Prev State +-------------------------+------------------------+ 2747 | | JoinDesired(S,G) | JoinDesired(S,G) | 2748 | | ->True | ->False | 2749 +-------------------+-------------------------+------------------------+ 2750 | NotJoined (NJ) | -> J state | - | 2751 | | Send Join(S,G); | | 2752 | | Set Join Timer to | | 2753 | | t_periodic | | 2754 +-------------------+-------------------------+------------------------+ 2755 | Joined (J) | - | -> NJ state | 2756 | | | Send Prune(S,G); | 2757 | | | Set SPTbit(S,G) to | 2758 | | | FALSE; Cancel Join | 2759 | | | Timer | 2760 +-------------------+-------------------------+------------------------+ 2762 In addition, we have the following transitions, which occur within 2763 the Joined state: 2765 +----------------------------------------------------------------------+ 2766 | In Joined (J) State | 2767 +-----------------+-----------------+-----------------+----------------+ 2768 | Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune | 2769 | | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to | 2770 | | | | RPF'(S,G) | 2771 +-----------------+-----------------+-----------------+----------------+ 2772 | Send | Increase Join | Decrease Join | Decrease Join | 2773 | Join(S,G); Set | Timer to | Timer to | Timer to | 2774 | Join Timer to | t_joinsuppress | t_override | t_override | 2775 | t_periodic | | | | 2776 +-----------------+-----------------+-----------------+----------------+ 2777 +----------------------------------------------------------------------+ 2778 | In Joined (J) State | 2779 +-----------------+-----------------+----------------+-----------------+ 2780 | See Prune(*,G) | RPF'(S,G) | RPF'(S,G) | RPF'(S,G) | 2781 | to RPF'(S,G) | changes not | GenID changes | changes due to | 2782 | | due to an | | an Assert | 2783 | | Assert | | | 2784 +-----------------+-----------------+----------------+-----------------+ 2785 | Decrease Join | Send Join(S,G) | Decrease Join | Decrease Join | 2786 | Timer to | to new next | Timer to | Timer to | 2787 | t_override | hop; Send | t_override | t_override | 2788 | | Prune(S,G) to | | | 2789 | | old next hop; | | | 2790 | | Set Join Timer | | | 2791 | | to t_periodic | | | 2792 +-----------------+-----------------+----------------+-----------------+ 2794 This state machine uses the following macro: 2796 bool JoinDesired(S,G) { 2797 return( immediate_olist(S,G) != NULL 2798 OR ( KeepaliveTimer(S,G) is running 2799 AND inherited_olist(S,G) != NULL ) ) 2800 } 2802 JoinDesired(S,G) is true when the router has forwarding state that 2803 would cause it to forward traffic for G using source tree state. The 2804 source tree state can be as a result of either active source-specific 2805 join state, or the (S,G) Keepalive Timer and active non-source- 2806 specific state. Note that although JoinDesired is true, the router's 2807 sending of a Join(S,G) message may be suppressed by another router 2808 sending a Join(S,G) onto the upstream interface. 2810 Transitions from NotJoined State 2812 When the upstream (S,G) state machine is in NotJoined state, the 2813 following event may trigger a state transition: 2815 JoinDesired(S,G) becomes True 2816 The macro JoinDesired(S,G) becomes True, e.g., because the 2817 downstream state for (S,G) has changed so that at least one 2818 interface is in inherited_olist(S,G). 2820 The upstream (S,G) state machine transitions to Joined state. 2821 Send Join(S,G) to the appropriate upstream neighbor, which is 2822 RPF'(S,G). Set the Join Timer (JT) to expire after t_periodic 2823 seconds. 2825 Transitions from Joined State 2827 When the upstream (S,G) state machine is in Joined state, the 2828 following events may trigger state transitions: 2830 JoinDesired(S,G) becomes False 2831 The macro JoinDesired(S,G) becomes False, e.g., because the 2832 downstream state for (S,G) has changed so no interface is in 2833 inherited_olist(S,G). 2835 The upstream (S,G) state machine transitions to NotJoined 2836 state. Send Prune(S,G) to the appropriate upstream neighbor, 2837 which is RPF'(S,G). Cancel the Join Timer (JT), and set 2838 SPTbit(S,G) to FALSE. 2840 Join Timer Expires 2841 The Join Timer (JT) expires, indicating time to send a 2842 Join(S,G) 2844 Send Join(S,G) to the appropriate upstream neighbor, which is 2845 RPF'(S,G). Restart the Join Timer (JT) to expire after 2846 t_periodic seconds. 2848 See Join(S,G) to RPF'(S,G) 2849 This event is only relevant if RPF_interface(S) is a shared 2850 medium. This router sees another router on RPF_interface(S) 2851 send a Join(S,G) to RPF'(S,G). This causes this router to 2852 suppress its own Join. 2854 The upstream (S,G) state machine remains in Joined state. 2856 Let t_joinsuppress be the minimum of t_suppressed and the 2857 HoldTime from the Join/Prune message triggering this event. 2859 If the Join Timer is set to expire in less than t_joinsuppress 2860 seconds, reset it so that it expires after t_joinsuppress 2861 seconds. If the Join Timer is set to expire in more than 2862 t_joinsuppress seconds, leave it unchanged. 2864 See Prune(S,G) to RPF'(S,G) 2865 This event is only relevant if RPF_interface(S) is a shared 2866 medium. This router sees another router on RPF_interface(S) 2867 send a Prune(S,G) to RPF'(S,G). As this router is in Joined 2868 state, it must override the Prune after a short random 2869 interval. 2871 The upstream (S,G) state machine remains in Joined state. If 2872 the Join Timer is set to expire in more than t_override 2873 seconds, reset it so that it expires after t_override seconds. 2875 See Prune(S,G,rpt) to RPF'(S,G) 2876 This event is only relevant if RPF_interface(S) is a shared 2877 medium. This router sees another router on RPF_interface(S) 2878 send a Prune(S,G,rpt) to RPF'(S,G). If the upstream router is 2879 an RFC-2362-compliant PIM router, then the Prune(S,G,rpt) will 2880 cause it to stop forwarding. For backwards compatibility, 2881 this router should override the prune so that forwarding 2882 continues. 2884 The upstream (S,G) state machine remains in Joined state. If 2885 the Join Timer is set to expire in more than t_override 2886 seconds, reset it so that it expires after t_override seconds. 2888 See Prune(*,G) to RPF'(S,G) 2889 This event is only relevant if RPF_interface(S) is a shared 2890 medium. This router sees another router on RPF_interface(S) 2891 send a Prune(*,G) to RPF'(S,G). If the upstream router is an 2892 RFC-2362-compliant PIM router, then the Prune(*,G) will cause 2893 it to stop forwarding. For backwards compatibility, this 2894 router should override the prune so that forwarding continues. 2896 The upstream (S,G) state machine remains in Joined state. If 2897 the Join Timer is set to expire in more than t_override 2898 seconds, reset it so that it expires after t_override seconds. 2900 RPF'(S,G) changes due to an Assert 2901 The current next hop towards S changes due to an Assert(S,G) 2902 on the RPF_interface(S). 2904 The upstream (S,G) state machine remains in Joined state. If 2905 the Join Timer is set to expire in more than t_override 2906 seconds, reset it so that it expires after t_override seconds. 2907 If the Join Timer is set to expire in less than t_override 2908 seconds, leave it unchanged. 2910 RPF'(S,G) changes not due to an Assert 2911 An event occurred that caused the next hop towards S to 2912 change. Note that this transition does not occur if an Assert 2913 is active and the upstream interface does not change. 2915 The upstream (S,G) state machine remains in Joined state. Send 2916 Join(S,G) to the new upstream neighbor, which is the new value 2917 of RPF'(S,G). Send Prune(S,G) to the old upstream neighbor, 2918 which is the old value of RPF'(S,G). Set the Join Timer (JT) 2919 to expire after t_periodic seconds. 2921 RPF'(S,G) GenID changes 2922 The Generation ID of the router that is RPF'(S,G) changes. 2923 This normally means that this neighbor has lost state, and so 2924 the state must be refreshed. 2926 The upstream (S,G) state machine remains in Joined state. If 2927 the Join Timer is set to expire in more than t_override 2928 seconds, reset it so that it expires after t_override seconds. 2930 4.5.6. (S,G,rpt) Periodic Messages 2932 (S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP 2933 tree with the RPT bit set, either to modify the results of (*,G) 2934 Joins, or to override the behavior of other upstream LAN peers. The 2935 next section describes the rules for sending triggered messages. 2936 This section describes the rules for including a Prune(S,G,rpt) 2937 message with a Join(*,G). 2939 When a router is going to send a Join(*,G), it should use the 2940 following pseudocode, for each (S,G) for which it has state, to 2941 decide whether to include a Prune(S,G,rpt) in the compound Join/Prune 2942 message: 2944 if( SPTbit(S,G) == TRUE ) { 2945 # Note: If receiving (S,G) on the SPT, we only prune off the 2946 # shared tree if the RPF neighbors differ. 2947 if( RPF'(*,G) != RPF'(S,G) ) { 2948 add Prune(S,G,rpt) to compound message 2949 } 2950 } else if ( inherited_olist(S,G,rpt) == NULL ) { 2951 # Note: all (*,G) olist interfaces received RPT prunes for (S,G). 2952 add Prune(S,G,rpt) to compound message 2953 } else if ( RPF'(*,G) != RPF'(S,G,rpt) { 2954 # Note: we joined the shared tree, but there was an (S,G) assert 2955 # and the source tree RPF neighbor is different. 2956 add Prune(S,G,rpt) to compound message 2957 } 2959 Note that Join(S,G,rpt) is normally sent not as a periodic message, 2960 but only as a triggered message. 2962 4.5.7. State Machine for (S,G,rpt) Triggered Messages 2964 The state machine for (S,G,rpt) triggered messages is required per- 2965 (S,G) when there is (*,G) join state at a router, and the router or 2966 any of its upstream LAN peers wishes to prune S off the RP tree. 2968 There are three states in the state machine. One of the states is 2969 when there is no (*,G) join state at this router. If there is (*,G) 2970 join state at the router, then the state machine must be at one of 2971 the other two states. The three states are: 2973 Pruned(S,G,rpt) 2974 (*,G) Joined, but (S,G,rpt) pruned 2976 NotPruned(S,G,rpt) 2977 (*,G) Joined, and (S,G,rpt) not pruned 2979 RPTNotJoined(G) 2980 (*,G) has not been joined. 2982 In addition, there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which 2983 is used to delay triggered Join(S,G,rpt) messages to prevent 2984 implosions of triggered messages. 2986 Figure 7: Upstream (S,G,rpt) state machine for triggered messages 2987 in tabular form 2989 +------------++--------------------------------------------------------+ 2990 | || Event | 2991 | ++--------------+--------------+-------------+------------+ 2992 |Prev State || PruneDesired | PruneDesired | RPTJoin | inherited_ | 2993 | || (S,G,rpt) | (S,G,rpt) | Desired(G) | olist | 2994 | || ->True | ->False | ->False | (S,G,rpt) | 2995 | || | | | ->non-NULL | 2996 +------------++--------------+--------------+-------------+------------+ 2997 |RPTNotJoined|| -> P state | - | - | -> NP state| 2998 |(G) (NJ) || | | | | 2999 +------------++--------------+--------------+-------------+------------+ 3000 |Pruned || - | -> NP state | -> NJ state | - | 3001 |(S,G,rpt) || | Send Join | | | 3002 |(P) || | (S,G,rpt) | | | 3003 +------------++--------------+--------------+-------------+------------+ 3004 |NotPruned || -> P state | - | -> NJ state | - | 3005 |(S,G,rpt) || Send Prune | | Cancel OT | | 3006 |(NP) || (S,G,rpt); | | | | 3007 | || Cancel OT | | | | 3008 +------------++--------------+--------------+-------------+------------+ 3009 Additionally, we have the following transitions within the 3010 NotPruned(S,G,rpt) state, which are all used for prune override 3011 behavior. 3013 +----------------------------------------------------------------------+ 3014 | In NotPruned(S,G,rpt) State | 3015 +----------+--------------+--------------+--------------+--------------+ 3016 |Override | See Prune | See Join | See Prune | RPF' | 3017 |Timer | (S,G,rpt) to | (S,G,rpt) to | (S,G) to | (S,G,rpt) -> | 3018 |expires | RPF' | RPF' | RPF' | RPF' (*,G) | 3019 | | (S,G,rpt) | (S,G,rpt) | (S,G,rpt) | | 3020 +----------+--------------+--------------+--------------+--------------+ 3021 |Send Join | OT = min(OT, | Cancel OT | OT = min(OT, | OT = min(OT, | 3022 |(S,G,rpt);| t_override) | | t_override) | t_override) | 3023 |Leave OT | | | | | 3024 |unset | | | | | 3025 +----------+--------------+--------------+--------------+--------------+ 3027 Note that the min function in the above state machine considers a 3028 non-running timer to have an infinite value (e.g., min(not-running, 3029 t_override) = t_override). 3031 This state machine uses the following macros: 3033 bool RPTJoinDesired(G) { 3034 return (JoinDesired(*,G)) 3035 } 3037 RPTJoinDesired(G) is true when the router has forwarding state that 3038 would cause it to forward traffic for G using (*,G) shared tree 3039 state. 3041 bool PruneDesired(S,G,rpt) { 3042 return ( RPTJoinDesired(G) AND 3043 ( inherited_olist(S,G,rpt) == NULL 3044 OR (SPTbit(S,G)==TRUE 3045 AND (RPF'(*,G) != RPF'(S,G)) ))) 3046 } 3048 PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true. 3049 If RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true 3050 either if there are no outgoing interfaces that S would be forwarded 3051 on, or if the router has active (S,G) forwarding state but RPF'(*,G) 3052 != RPF'(S,G). 3054 The state machine contains the following transition events: 3056 See Join(S,G,rpt) to RPF'(S,G,rpt) 3057 This event is only relevant in the "Not Pruned" state. 3059 The router sees a Join(S,G,rpt) from someone else to 3060 RPF'(S,G,rpt), which is the correct upstream neighbor. If we're 3061 in "NotPruned" state and the (S,G,rpt) Override Timer is running, 3062 then this is because we have been triggered to send our own 3063 Join(S,G,rpt) to RPF'(S,G,rpt). Someone else beat us to it, so 3064 there's no need to send our own Join. 3066 The action is to cancel the Override Timer. 3068 See Prune(S,G,rpt) to RPF'(S,G,rpt) 3069 This event is only relevant in the "NotPruned" state. 3071 The router sees a Prune(S,G,rpt) from someone else to 3072 RPF'(S,G,rpt), which is the correct upstream neighbor. If we're 3073 in the "NotPruned" state, then we want to continue to receive 3074 traffic from S destined for G, and that traffic is being supplied 3075 by RPF'(S,G,rpt). Thus, we need to override the Prune. 3077 The action is to set the (S,G,rpt) Override Timer to the 3078 randomized prune-override interval, t_override. However, if the 3079 Override Timer is already running, we only set the timer if doing 3080 so would set it to a lower value. At the end of this interval, if 3081 no one else has sent a Join, then we will do so. 3083 See Prune(S,G) to RPF'(S,G,rpt) 3084 This event is only relevant in the "NotPruned" state. 3086 This transition and action are the same as the above transition 3087 and action, except that the Prune does not have the RPT bit set. 3088 This transition is necessary to be compatible with routers 3089 implemented from RFC2362 that don't maintain separate (S,G) and 3090 (S,G,rpt) state. 3092 The (S,G,rpt) prune Override Timer expires 3093 This event is only relevant in the "NotPruned" state. 3095 When the Override Timer expires, we must send a Join(S,G,rpt) to 3096 RPF'(S,G,rpt) to override the Prune message that caused the timer 3097 to be running. We only send this if RPF'(S,G,rpt) equals 3098 RPF'(*,G); if this were not the case, then the Join might be sent 3099 to a router that does not have (*,G) Join state, and so the 3100 behavior would not be well defined. If RPF'(S,G,rpt) is not the 3101 same as RPF'(*,G), then it may stop forwarding S. However, if 3102 this happens, then the router will send an AssertCancel(S,G), 3103 which would then cause RPF'(S,G,rpt) to become equal to RPF'(*,G) 3104 (see below). 3106 RPF'(S,G,rpt) changes to become equal to RPF'(*,G) 3107 This event is only relevant in the "NotPruned" state. 3109 RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G) 3110 Assert has happened, which means that traffic from S is arriving 3111 on the SPT, and so Prune(S,G,rpt) will have been sent to 3112 RPF'(*,G). When RPF'(S,G,rpt) changes to become equal to 3113 RPF'(*,G), we need to trigger a Join(S,G,rpt) to RPF'(*,G) to 3114 cause that router to start forwarding S again. 3116 The action is to set the (S,G,rpt) Override Timer to the 3117 randomized prune-override interval t_override. However, if the 3118 timer is already running, we only set the timer if doing so would 3119 set it to a lower value. At the end of this interval, if no one 3120 else has sent a Join, then we will do so. 3122 PruneDesired(S,G,rpt)->TRUE 3123 See macro above. This event is relevant in the "NotPruned" and 3124 "RPTNotJoined(G)" states. 3126 The router wishes to receive traffic for G, but does not wish to 3127 receive traffic from S destined for G. This causes the router to 3128 transition into the Pruned state. 3130 If the router was previously in NotPruned state, then the action 3131 is to send a Prune(S,G,rpt) to RPF'(S,G,rpt), and to cancel the 3132 Override Timer. If the router was previously in RPTNotJoined(G) 3133 state, then there is no need to trigger an action in this state 3134 machine because sending a Prune(S,G,rpt) is handled by the rules 3135 for sending the Join(*,G). 3137 PruneDesired(S,G,rpt)->FALSE 3138 See macro above. This transition is only relevant in the "Pruned" 3139 state. 3141 If the router is in the Pruned(S,G,rpt) state, and 3142 PruneDesired(S,G,rpt) changes to FALSE, this could be because the 3143 router no longer has RPTJoinDesired(G) true, or it now wishes to 3144 receive traffic from S again. If it is the former, then this 3145 transition should not happen, but instead the 3146 "RPTJoinDesired(G)->FALSE" transition should happen. Thus, this 3147 transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE 3148 AND RPTJoinDesired(G)==TRUE". 3150 The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt). 3152 RPTJoinDesired(G)->FALSE 3153 This event is relevant in the "Pruned" and "NotPruned" states. 3155 The router no longer wishes to receive any traffic destined for G 3156 on the RP Tree. This causes a transition to the RPTNotJoined(G) 3157 state, and the Override Timer is canceled if it was running. Any 3158 further actions are handled by the appropriate upstream state 3159 machine for (*,G). 3161 inherited_olist(S,G,rpt) becomes non-NULL 3162 This transition is only relevant in the RPTNotJoined(G) state. 3164 The router has joined the RP tree (handled by the (*,G) upstream 3165 state machine as appropriate) and wants to receive traffic from S. 3166 This does not trigger any events in this state machine, but 3167 causes a transition to the NotPruned(S,G,rpt) state. 3169 4.6. PIM Assert Messages 3171 Where multiple PIM routers peer over a shared LAN, it is possible for 3172 more than one upstream router to have valid forwarding state for a 3173 packet, which can lead to packet duplication (see Section 3.6). PIM 3174 does not attempt to prevent this from occurring. Instead, it detects 3175 when this has happened and elects a single forwarder amongst the 3176 upstream routers to prevent further duplication. This election is 3177 performed using PIM Assert messages. Assert messages are also 3178 received by downstream routers on the LAN, and these cause subsequent 3179 Join/Prune messages to be sent to the upstream router that won the 3180 Assert. 3182 In general, a PIM Assert message should only be accepted for 3183 processing if it comes from a known PIM neighbor. A PIM router hears 3184 about PIM neighbors through PIM Hello messages. If a router receives 3185 an Assert message from a particular IP source address and it has not 3186 seen a PIM Hello message from that source address, then the Assert 3187 message SHOULD be discarded without further processing. In addition, 3188 if the Hello message from a neighbor was authenticated using the 3189 IPsec Authentication Header (AH) (see Section 6.3), then all Assert 3190 messages from that neighbor MUST also be authenticated using IPsec 3191 AH. 3193 We note that some older PIM implementations incorrectly fail to send 3194 Hello messages on point-to-point interfaces, so we also RECOMMEND 3195 that a configuration option be provided to allow interoperation with 3196 such older routers, but that this configuration option SHOULD NOT be 3197 enabled by default. 3199 4.6.1. (S,G) Assert Message State Machine 3201 The (S,G) Assert state machine for interface I is shown in Figure 8. 3202 There are three states: 3204 NoInfo (NI) 3205 This router has no (S,G) assert state on interface I. 3207 I am Assert Winner (W) 3208 This router has won an (S,G) assert on interface I. It is now 3209 responsible for forwarding traffic from S destined for G out of 3210 interface I. Irrespective of whether it is the DR for I, while a 3211 router is the assert winner, it is also responsible for forwarding 3212 traffic onto I on behalf of local hosts on I that have made 3213 membership requests that specifically refer to S (and G). 3215 I am Assert Loser (L) 3216 This router has lost an (S,G) assert on interface I. It must not 3217 forward packets from S destined for G onto interface I. If it is 3218 the DR on I, it is no longer responsible for forwarding traffic 3219 onto I to satisfy local hosts with membership requests that 3220 specifically refer to S and G. 3222 In addition, there is also an Assert Timer (AT) that is used to time 3223 out asserts on the assert losers and to resend asserts on the assert 3224 winner. 3226 Figure 8: Per-interface (S,G) Assert State machine in tabular form 3228 +----------------------------------------------------------------------+ 3229 | In NoInfo (NI) State | 3230 +---------------+-------------------+------------------+---------------+ 3231 | Receive | Receive Assert | Data arrives | Receive | 3232 | Inferior | with RPTbit | from S to G on | Acceptable | 3233 | Assert with | set and | I and | Assert with | 3234 | RPTbit clear | CouldAssert | CouldAssert | RPTbit clear | 3235 | | (S,G,I) | (S,G,I) | and AssTrDes | 3236 | | | | (S,G,I) | 3237 +---------------+-------------------+------------------+---------------+ 3238 | -> W state | -> W state | -> W state | -> L state | 3239 | [Actions A1] | [Actions A1] | [Actions A1] | [Actions A6] | 3240 +---------------+-------------------+------------------+---------------+ 3241 +----------------------------------------------------------------------+ 3242 | In I Am Assert Winner (W) State | 3243 +----------------+------------------+-----------------+----------------+ 3244 | Assert Timer | Receive | Receive | CouldAssert | 3245 | Expires | Inferior | Preferred | (S,G,I) -> | 3246 | | Assert | Assert | FALSE | 3247 +----------------+------------------+-----------------+----------------+ 3248 | -> W state | -> W state | -> L state | -> NI state | 3249 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3250 +----------------+------------------+-----------------+----------------+ 3252 +---------------------------------------------------------------------+ 3253 | In I Am Assert Loser (L) State | 3254 +-------------+-------------+-------------+-------------+-------------+ 3255 |Receive |Receive |Receive |Assert Timer |Current | 3256 |Preferred |Acceptable |Inferior |Expires |Winner's | 3257 |Assert |Assert with |Assert or | |GenID | 3258 | |RPTbit clear |Assert | |Changes or | 3259 | |from Current |Cancel from | |NLT Expires | 3260 | |Winner |Current | | | 3261 | | |Winner | | | 3262 +-------------+-------------+-------------+-------------+-------------+ 3263 |-> L state |-> L state |-> NI state |-> NI state |-> NI state | 3264 |[Actions A2] |[Actions A2] |[Actions A5] |[Actions A5] |[Actions A5] | 3265 +-------------+-------------+-------------+-------------+-------------+ 3267 +----------------------------------------------------------------------+ 3268 | In I Am Assert Loser (L) State | 3269 +----------------+-----------------+------------------+----------------+ 3270 | AssTrDes | my_metric -> | RPF_interface | Receive | 3271 | (S,G,I) -> | better than | (S) stops | Join(S,G) on | 3272 | FALSE | winner's | being I | interface I | 3273 | | metric | | | 3274 +----------------+-----------------+------------------+----------------+ 3275 | -> NI state | -> NI state | -> NI state | -> NI State | 3276 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 3277 +----------------+-----------------+------------------+----------------+ 3279 Note that for reasons of compactness, "AssTrDes(S,G,I)" is used in 3280 the state machine table to refer to AssertTrackingDesired(S,G,I). 3282 Terminology: 3284 A "preferred assert" is one with a better metric than the current 3285 winner. 3287 An "acceptable assert" is one that has a better metric than 3288 my_assert_metric(S,G,I). An assert is never considered acceptable 3289 if its metric is infinite. 3291 An "inferior assert" is one with a worse metric than 3292 my_assert_metric(S,G,I). An assert is never considered inferior 3293 if my_assert_metric(S,G,I) is infinite. 3295 The state machine uses the following macros: 3297 CouldAssert(S,G,I) = 3298 SPTbit(S,G)==TRUE 3299 AND (RPF_interface(S) != I) 3300 AND (I in ( ( joins(*,G) (-) prunes(S,G,rpt) ) 3301 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3302 (-) lost_assert(*,G) 3303 (+) joins(S,G) (+) pim_include(S,G) ) ) 3305 CouldAssert(S,G,I) is true for downstream interfaces that would be in 3306 the inherited_olist(S,G) if (S,G) assert information was not taken 3307 into account. 3309 AssertTrackingDesired(S,G,I) = 3310 (I in ( joins(*,G) (-) prunes(S,G,rpt) 3311 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3312 (-) lost_assert(*,G) 3313 (+) joins(S,G) ) ) 3314 OR (local_receiver_include(S,G,I) == TRUE 3315 AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me))) 3316 OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == TRUE)) 3317 OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == TRUE) 3318 AND (SPTbit(S,G) == FALSE)) 3320 AssertTrackingDesired(S,G,I) is true on any interface in which an 3321 (S,G) assert might affect our behavior. 3323 The first three lines of AssertTrackingDesired account for (*,G) join 3324 and local membership information received on I that might cause the 3325 router to be interested in asserts on I. 3327 The 4th line accounts for (S,G) join information received on I that 3328 might cause the router to be interested in asserts on I. 3330 The 5th and 6th lines account for (S,G) local membership information 3331 on I. Note that we can't use the pim_include(S,G) macro since it 3332 uses lost_assert(S,G,I) and would result in the router forgetting 3333 that it lost an assert if the only reason it was interested was local 3334 membership. The AssertWinner(S,G,I) check forces an assert winner to 3335 keep on being responsible for forwarding as long as local receivers 3336 are present. Removing this check would make the assert winner give 3337 up forwarding as soon as the information that originally caused it to 3338 forward went away, and the task of forwarding for local receivers 3339 would revert back to the DR. 3341 The last three lines account for the fact that a router must keep 3342 track of assert information on upstream interfaces in order to send 3343 joins and prunes to the proper neighbor. 3345 Transitions from NoInfo State 3347 When in NoInfo state, the following events may trigger transitions: 3349 Receive Inferior Assert with RPTbit cleared 3350 An assert is received for (S,G) with the RPT bit cleared that 3351 is inferior to our own assert metric. The RPT bit cleared 3352 indicates that the sender of the assert had (S,G) forwarding 3353 state on this interface. If the assert is inferior to our 3354 metric, then we must also have (S,G) forwarding state (i.e., 3355 CouldAssert(S,G,I)==TRUE) as (S,G) asserts beat (*,G) asserts, 3356 and so we should be the assert winner. We transition to the 3357 "I am Assert Winner" state and perform Actions A1 (below). 3359 Receive Assert with RPTbit set AND CouldAssert(S,G,I)==TRUE 3360 An assert is received for (S,G) on I with the RPT bit set 3361 (it's a (*,G) assert). CouldAssert(S,G,I) is TRUE only if we 3362 have (S,G) forwarding state on this interface, so we should be 3363 the assert winner. We transition to the "I am Assert Winner" 3364 state and perform Actions A1 (below). 3366 An (S,G) data packet arrives on interface I, AND 3367 CouldAssert(S,G,I)==TRUE 3368 An (S,G) data packet arrived on a downstream interface that is 3369 in our (S,G) outgoing interface list. We optimistically 3370 assume that we will be the assert winner for this (S,G), and 3371 so we transition to the "I am Assert Winner" state and perform 3372 Actions A1 (below), which will initiate the assert negotiation 3373 for (S,G). 3375 Receive Acceptable Assert with RPT bit clear AND 3376 AssertTrackingDesired(S,G,I)==TRUE 3377 We're interested in (S,G) Asserts, either because I is a 3378 downstream interface for which we have (S,G) or (*,G) 3379 forwarding state, or because I is the upstream interface for S 3380 and we have (S,G) forwarding state. The received assert has a 3381 better metric than our own, so we do not win the Assert. We 3382 transition to "I am Assert Loser" and perform Actions A6 3383 (below). 3385 Transitions from "I am Assert Winner" State 3387 When in "I am Assert Winner" state, the following events trigger 3388 transitions: 3390 Assert Timer Expires 3391 The (S,G) Assert Timer expires. As we're in the Winner state, 3392 we must still have (S,G) forwarding state that is actively 3393 being kept alive. We resend the (S,G) Assert and restart the 3394 Assert Timer (Actions A3 below). Note that the assert 3395 winner's Assert Timer is engineered to expire shortly before 3396 timers on assert losers; this prevents unnecessary thrashing 3397 of the forwarder and periodic flooding of duplicate packets. 3399 Receive Inferior Assert 3400 We receive an (S,G) assert or (*,G) assert mentioning S that 3401 has a worse metric than our own. Whoever sent the assert is 3402 in error, and so we resend an (S,G) Assert and restart the 3403 Assert Timer (Actions A3 below). 3405 Receive Preferred Assert 3406 We receive an (S,G) assert that has a better metric than our 3407 own. We transition to "I am Assert Loser" state and perform 3408 Actions A2 (below). Note that this may affect the value of 3409 JoinDesired(S,G) and PruneDesired(S,G,rpt), which could cause 3410 transitions in the upstream (S,G) or (S,G,rpt) state machines. 3412 CouldAssert(S,G,I) -> FALSE 3413 Our (S,G) forwarding state or RPF interface changed so as to 3414 make CouldAssert(S,G,I) become false. We can no longer 3415 perform the actions of the assert winner, and so we transition 3416 to NoInfo state and perform Actions A4 (below). This includes 3417 sending a "canceling assert" with an infinite metric. 3419 Transitions from "I am Assert Loser" State 3421 When in "I am Assert Loser" state, the following transitions can 3422 occur: 3424 Receive Preferred Assert 3425 We receive an assert that is better than that of the current 3426 assert winner. We stay in Loser state and perform Actions A2 3427 below. 3429 Receive Acceptable Assert with RPTbit clear from Current Winner 3430 We receive an assert from the current assert winner that is 3431 better than our own metric for this (S,G) (although the metric 3432 may be worse than the winner's previous metric). We stay in 3433 Loser state and perform Actions A2 below. 3435 Receive Inferior Assert or Assert Cancel from Current Winner 3436 We receive an assert from the current assert winner that is 3437 worse than our own metric for this group (typically, because 3438 the winner's metric became worse or because it is an assert 3439 cancel). We transition to NoInfo state, deleting the (S,G) 3440 assert information and allowing the normal PIM Join/Prune 3441 mechanisms to operate. Usually, we will eventually re-assert 3442 and win when data packets from S have started flowing again. 3444 Assert Timer Expires 3445 The (S,G) Assert Timer expires. We transition to NoInfo 3446 state, deleting the (S,G) assert information (Actions A5 3447 below). 3449 Current Winner's GenID Changes or NLT Expires 3450 The Neighbor Liveness Timer associated with the current winner 3451 expires or we receive a Hello message from the current winner 3452 reporting a different GenID from the one it previously 3453 reported. This indicates that the current winner's interface 3454 or router has gone down (and may have come back up), and so we 3455 must assume it no longer knows it was the winner. We 3456 transition to the NoInfo state, deleting this (S,G) assert 3457 information (Actions A5 below). 3459 AssertTrackingDesired(S,G,I)->FALSE 3460 AssertTrackingDesired(S,G,I) becomes FALSE. Our forwarding 3461 state has changed so that (S,G) Asserts on interface I are no 3462 longer of interest to us. We transition to the NoInfo state, 3463 deleting the (S,G) assert information. 3465 My metric becomes better than the assert winner's metric 3466 my_assert_metric(S,G,I) has changed so that now my assert 3467 metric for (S,G) is better than the metric we have stored for 3468 current assert winner. This might happen when the underlying 3469 routing metric changes, or when CouldAssert(S,G,I) becomes 3470 true; for example, when SPTbit(S,G) becomes true. We 3471 transition to NoInfo state, delete this (S,G) assert state 3472 (Actions A5 below), and allow the normal PIM Join/Prune 3473 mechanisms to operate. Usually, we will eventually re-assert 3474 and win when data packets from S have started flowing again. 3476 RPF_interface(S) stops being interface I 3477 Interface I used to be the RPF interface for S, and now it is 3478 not. We transition to NoInfo state, deleting this (S,G) 3479 assert state (Actions A5 below). 3481 Receive Join(S,G) on Interface I 3482 We receive a Join(S,G) that has the Upstream Neighbor Address 3483 field set to my primary IP address on interface I. The action 3484 is to transition to NoInfo state, delete this (S,G) assert 3485 state (Actions A5 below), and allow the normal PIM Join/Prune 3486 mechanisms to operate. If whoever sent the Join was in error, 3487 then the normal assert mechanism will eventually re-apply, and 3488 we will lose the assert again. However, whoever sent the 3489 assert may know that the previous assert winner has died, and 3490 so we may end up being the new forwarder. 3492 (S,G) Assert State machine Actions 3494 A1: Send Assert(S,G). 3495 Set Assert Timer to (Assert_Time - Assert_Override_Interval). 3496 Store self as AssertWinner(S,G,I). 3497 Store spt_assert_metric(S,I) as AssertWinnerMetric(S,G,I). 3499 A2: Store new assert winner as AssertWinner(S,G,I) and assert 3500 winner metric as AssertWinnerMetric(S,G,I). 3501 Set Assert Timer to Assert_Time. 3503 A3: Send Assert(S,G). 3504 Set Assert Timer to (Assert_Time - Assert_Override_Interval). 3506 A4: Send AssertCancel(S,G). 3507 Delete assert info (AssertWinner(S,G,I) and 3508 AssertWinnerMetric(S,G,I) will then return to their default 3509 values). 3511 A5: Delete assert info (AssertWinner(S,G,I) and 3512 AssertWinnerMetric(S,G,I) will then return to their default 3513 values). 3515 A6: Store new assert winner as AssertWinner(S,G,I) and assert 3516 winner metric as AssertWinnerMetric(S,G,I). 3517 Set Assert Timer to Assert_Time. 3518 If (I is RPF_interface(S)) AND (UpstreamJPState(S,G) == 3519 Joined) set SPTbit(S,G) to TRUE. 3521 Note that some of these actions may cause the value of 3522 JoinDesired(S,G), PruneDesired(S,G,rpt), or RPF'(S,G) to change, 3523 which could cause further transitions in other state machines. 3525 4.6.2. (*,G) Assert Message State Machine 3527 The (*,G) Assert state machine for interface I is shown in Figure 9. 3528 There are three states: 3530 NoInfo (NI) 3531 This router has no (*,G) assert state on interface I. 3533 I am Assert Winner (W) 3534 This router has won an (*,G) assert on interface I. It is now 3535 responsible for forwarding traffic destined for G onto interface I 3536 with the exception of traffic for which it has (S,G) "I am Assert 3537 Loser" state. Irrespective of whether it is the DR for I, it is 3538 also responsible for handling the membership requests for G from 3539 local hosts on I. 3541 I am Assert Loser (L) 3542 This router has lost an (*,G) assert on interface I. It must not 3543 forward packets for G onto interface I with the exception of 3544 traffic from sources for which it has (S,G) "I am Assert Winner" 3545 state. If it is the DR, it is no longer responsible for handling 3546 the membership requests for group G from local hosts on I. 3548 In addition, there is also an Assert Timer (AT) that is used to time 3549 out asserts on the assert losers and to resend asserts on the assert 3550 winner. 3552 When an Assert message is received with a source address other than 3553 zero, a PIM implementation must first match it against the possible 3554 events in the (S,G) assert state machine and process any transitions 3555 and actions, before considering whether the Assert message matches 3556 against the (*,G) assert state machine. 3558 It is important to note that NO TRANSITION CAN OCCUR in the (*,G) 3559 state machine as a result of receiving an Assert message unless the 3560 (S,G) assert state machine for the relevant S and G is in the 3561 "NoInfo" state after the (S,G) state machine has processed the 3562 message. Also, NO TRANSITION CAN OCCUR in the (*,G) state machine as 3563 a result of receiving an assert message if that message triggers any 3564 change of state in the (S,G) state machine. Obviously, when the 3565 source address in the received message is set to zero, an (S,G) state 3566 machine for the S and G does not exist and can be assumed to be in 3567 the "NoInfo" state. 3569 For example, if both the (S,G) and (*,G) assert state machines are in 3570 the NoInfo state when an Assert message arrives, and the message 3571 causes the (S,G) state machine to transition to either "W" or "L" 3572 state, then the assert will not be processed by the (*,G) assert 3573 state machine. 3575 Another example: if the (S,G) assert state machine is in "L" state 3576 when an assert message is received, and the assert metric in the 3577 message is worse than my_assert_metric(S,G,I), then the (S,G) assert 3578 state machine will transition to NoInfo state. In such a case, if 3579 the (*,G) assert state machine were in NoInfo state, it might appear 3580 that it would transition to "W" state, but this is not the case 3581 because this message already triggered a transition in the (S,G) 3582 assert state machine. 3584 Figure 9: Per-interface (*,G) Assert State machine in tabular form 3586 +----------------------------------------------------------------------+ 3587 | In NoInfo (NI) State | 3588 +-----------------------+-----------------------+----------------------+ 3589 | Receive Inferior | Data arrives for G | Receive Acceptable | 3590 | Assert with RPTbit | on I and | Assert with RPTbit | 3591 | set and | CouldAssert | set and AssTrDes | 3592 | CouldAssert(*,G,I) | (*,G,I) | (*,G,I) | 3593 +-----------------------+-----------------------+----------------------+ 3594 | -> W state | -> W state | -> L state | 3595 | [Actions A1] | [Actions A1] | [Actions A2] | 3596 +-----------------------+-----------------------+----------------------+ 3598 +---------------------------------------------------------------------+ 3599 | In I Am Assert Winner (W) State | 3600 +----------------+-----------------+-----------------+----------------+ 3601 | Assert Timer | Receive | Receive | CouldAssert | 3602 | Expires | Inferior | Preferred | (*,G,I) -> | 3603 | | Assert | Assert | FALSE | 3604 +----------------+-----------------+-----------------+----------------+ 3605 | -> W state | -> W state | -> L state | -> NI state | 3606 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3607 +----------------+-----------------+-----------------+----------------+ 3608 +---------------------------------------------------------------------+ 3609 | In I Am Assert Loser (L) State | 3610 +-------------+-------------+-------------+-------------+-------------+ 3611 |Receive |Receive |Receive |Assert Timer |Current | 3612 |Preferred |Acceptable |Inferior |Expires |Winner's | 3613 |Assert with |Assert from |Assert or | |GenID | 3614 |RPTbit set |Current |Assert | |Changes or | 3615 | |Winner with |Cancel from | |NLT Expires | 3616 | |RPTbit set |Current | | | 3617 | | |Winner | | | 3618 +-------------+-------------+-------------+-------------+-------------+ 3619 |-> L state |-> L state |-> NI state |-> NI state |-> NI state | 3620 |[Actions A2] |[Actions A2] |[Actions A5] |[Actions A5] |[Actions A5] | 3621 +-------------+-------------+-------------+-------------+-------------+ 3623 +----------------------------------------------------------------------+ 3624 | In I Am Assert Loser (L) State | 3625 +----------------+----------------+-----------------+------------------+ 3626 | AssTrDes | my_metric -> | RPF_interface | Receive | 3627 | (*,G,I) -> | better than | (RP(G)) stops | Join(*,G) on | 3628 | FALSE | Winner's | being I | Interface I | 3629 | | metric | | | 3630 +----------------+----------------+-----------------+------------------+ 3631 | -> NI state | -> NI state | -> NI state | -> NI State | 3632 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 3633 +----------------+----------------+-----------------+------------------+ 3635 The state machine uses the following macros: 3637 CouldAssert(*,G,I) = 3638 ( I in ( joins(*,G) (+) pim_include(*,G)) ) 3639 AND (RPF_interface(RP(G)) != I) 3641 CouldAssert(*,G,I) is true on downstream interfaces for which we have 3642 (*,G) join state, or local members that requested any traffic 3643 destined for G. 3645 AssertTrackingDesired(*,G,I) = 3646 CouldAssert(*,G,I) 3647 OR (local_receiver_include(*,G,I)==TRUE 3648 AND (I_am_DR(I) OR AssertWinner(*,G,I) == me)) 3649 OR (RPF_interface(RP(G)) == I AND RPTJoinDesired(G)) 3651 AssertTrackingDesired(*,G,I) is true on any interface on which an 3652 (*,G) assert might affect our behavior. 3654 Note that for reasons of compactness, "AssTrDes(*,G,I)" is used in 3655 the state machine table to refer to AssertTrackingDesired(*,G,I). 3657 Terminology: 3659 A "preferred assert" is one with a better metric than the current 3660 winner. 3662 An "acceptable assert" is one that has a better metric than 3663 my_assert_metric(*,G,I). An assert is never considered acceptable 3664 if its metric is infinite. 3666 An "inferior assert" is one with a worse metric than 3667 my_assert_metric(*,G,I). An assert is never considered inferior 3668 if my_assert_metric(*,G,I) is infinite. 3670 Transitions from NoInfo State 3672 When in NoInfo state, the following events trigger transitions, but 3673 only if the (S,G) assert state machine is in NoInfo state before and 3674 after consideration of the received message: 3676 Receive Inferior Assert with RPTbit set AND 3677 CouldAssert(*,G,I)==TRUE 3678 An Inferior (*,G) assert is received for G on Interface I. If 3679 CouldAssert(*,G,I) is TRUE, then I is our downstream 3680 interface, and we have (*,G) forwarding state on this 3681 interface, so we should be the assert winner. We transition 3682 to the "I am Assert Winner" state and perform Actions A1 3683 (below). 3685 A data packet destined for G arrives on interface I, AND 3686 CouldAssert(*,G,I)==TRUE 3687 A data packet destined for G arrived on a downstream interface 3688 that is in our (*,G) outgoing interface list. We therefore 3689 believe we should be the forwarder for this (*,G), and so we 3690 transition to the "I am Assert Winner" state and perform 3691 Actions A1 (below). 3693 Receive Acceptable Assert with RPT bit set AND 3694 AssertTrackingDesired(*,G,I)==TRUE 3695 We're interested in (*,G) Asserts, either because I is a 3696 downstream interface for which we have (*,G) forwarding state, 3697 or because I is the upstream interface for RP(G) and we have 3698 (*,G) forwarding state. We get a (*,G) Assert that has a 3699 better metric than our own, so we do not win the Assert. We 3700 transition to "I am Assert Loser" and perform Actions A2 3701 (below). 3703 Transitions from "I am Assert Winner" State 3704 When in "I am Assert Winner" state, the following events trigger 3705 transitions, but only if the (S,G) assert state machine is in NoInfo 3706 state before and after consideration of the received message: 3708 Receive Inferior Assert 3709 We receive a (*,G) assert that has a worse metric than our 3710 own. Whoever sent the assert has lost, and so we resend a 3711 (*,G) Assert and restart the Assert Timer (Actions A3 below). 3713 Receive Preferred Assert 3714 We receive a (*,G) assert that has a better metric than our 3715 own. We transition to "I am Assert Loser" state and perform 3716 Actions A2 (below). 3718 When in "I am Assert Winner" state, the following events trigger 3719 transitions: 3721 Assert Timer Expires 3722 The (*,G) Assert Timer expires. As we're in the Winner state, 3723 then we must still have (*,G) forwarding state that is 3724 actively being kept alive. To prevent unnecessary thrashing 3725 of the forwarder and periodic flooding of duplicate packets, 3726 we resend the (*,G) Assert and restart the Assert Timer 3727 (Actions A3 below). 3729 CouldAssert(*,G,I) -> FALSE 3730 Our (*,G) forwarding state or RPF interface changed so as to 3731 make CouldAssert(*,G,I) become false. We can no longer 3732 perform the actions of the assert winner, and so we transition 3733 to NoInfo state and perform Actions A4 (below). 3735 Transitions from "I am Assert Loser" State 3737 When in "I am Assert Loser" state, the following events trigger 3738 transitions, but only if the (S,G) assert state machine is in NoInfo 3739 state before and after consideration of the received message: 3741 Receive Preferred Assert with RPTbit set 3742 We receive a (*,G) assert that is better than that of the 3743 current assert winner. We stay in Loser state and perform 3744 Actions A2 below. 3746 Receive Acceptable Assert from Current Winner with RPTbit set 3747 We receive a (*,G) assert from the current assert winner that 3748 is better than our own metric for this group (although the 3749 metric may be worse than the winner's previous metric). We 3750 stay in Loser state and perform Actions A2 below. 3752 Receive Inferior Assert or Assert Cancel from Current Winner 3753 We receive an assert from the current assert winner that is 3754 worse than our own metric for this group (typically because 3755 the winner's metric became worse or is now an assert cancel). 3756 We transition to NoInfo state, delete this (*,G) assert state 3757 (Actions A5), and allow the normal PIM Join/Prune mechanisms 3758 to operate. Usually, we will eventually re-assert and win 3759 when data packets for G have started flowing again. 3761 When in "I am Assert Loser" state, the following events trigger 3762 transitions: 3764 Assert Timer Expires 3765 The (*,G) Assert Timer expires. We transition to NoInfo state 3766 and delete this (*,G) assert info (Actions A5). 3768 Current Winner's GenID Changes or NLT Expires 3769 The Neighbor Liveness Timer associated with the current winner 3770 expires or we receive a Hello message from the current winner 3771 reporting a different GenID from the one it previously 3772 reported. This indicates that the current winner's interface 3773 or router has gone down (and may have come back up), and so we 3774 must assume it no longer knows it was the winner. We 3775 transition to the NoInfo state, deleting the (*,G) assert 3776 information (Actions A5). 3778 AssertTrackingDesired(*,G,I)->FALSE 3779 AssertTrackingDesired(*,G,I) becomes FALSE. Our forwarding 3780 state has changed so that (*,G) Asserts on interface I are no 3781 longer of interest to us. We transition to NoInfo state and 3782 delete this (*,G) assert info (Actions A5). 3784 My metric becomes better than the assert winner's metric 3785 My routing metric, rpt_assert_metric(G,I), has changed so that 3786 now my assert metric for (*,G) is better than the metric we 3787 have stored for current assert winner. We transition to 3788 NoInfo state, delete this (*,G) assert state (Actions A5), and 3789 allow the normal PIM Join/Prune mechanisms to operate. 3790 Usually, we will eventually re-assert and win when data 3791 packets for G have started flowing again. 3793 RPF_interface(RP(G)) stops being interface I 3794 Interface I used to be the RPF interface for RP(G), and now it 3795 is not. We transition to NoInfo state and delete this (*,G) 3796 assert state (Actions A5). 3798 Receive Join(*,G) on interface I 3799 We receive a Join(*,G) that has the Upstream Neighbor Address 3800 field set to my primary IP address on interface I. The action 3801 is to transition to NoInfo state, delete this (*,G) assert 3802 state (Actions A5), and allow the normal PIM Join/Prune 3803 mechanisms to operate. If whoever sent the Join was in error, 3804 then the normal assert mechanism will eventually re-apply, and 3805 we will lose the assert again. However, whoever sent the 3806 assert may know that the previous assert winner has died, so 3807 we may end up being the new forwarder. 3809 (*,G) Assert State machine Actions 3811 A1: Send Assert(*,G). 3812 Set Assert Timer to (Assert_Time - Assert_Override_Interval). 3813 Store self as AssertWinner(*,G,I). 3814 Store rpt_assert_metric(G,I) as AssertWinnerMetric(*,G,I). 3816 A2: Store new assert winner as AssertWinner(*,G,I) and assert 3817 winner metric as AssertWinnerMetric(*,G,I). 3818 Set Assert Timer to Assert_Time. 3820 A3: Send Assert(*,G) 3821 Set Assert Timer to (Assert_Time - Assert_Override_Interval). 3823 A4: Send AssertCancel(*,G). 3824 Delete assert info (AssertWinner(*,G,I) and 3825 AssertWinnerMetric(*,G,I) will then return to their default 3826 values). 3828 A5: Delete assert info (AssertWinner(*,G,I) and 3829 AssertWinnerMetric(*,G,I) will then return to their default 3830 values). 3832 Note that some of these actions may cause the value of 3833 JoinDesired(*,G) or RPF'(*,G)) to change, which could cause further 3834 transitions in other state machines. 3836 4.6.3. Assert Metrics 3838 Assert metrics are defined as: 3840 struct assert_metric { 3841 rpt_bit_flag; 3842 metric_preference; 3843 route_metric; 3844 ip_address; 3845 }; 3847 When comparing assert_metrics, the rpt_bit_flag, metric_preference, 3848 and route_metric field are compared in order, where the first lower 3849 value wins. If all fields are equal, the primary IP address of the 3850 router that sourced the Assert message is used as a tie-breaker, with 3851 the highest IP address winning. 3853 An assert metric for (S,G) to include in (or compare against) an 3854 Assert message sent on interface I should be computed using the 3855 following pseudocode: 3857 assert_metric 3858 my_assert_metric(S,G,I) { 3859 if( CouldAssert(S,G,I) == TRUE ) { 3860 return spt_assert_metric(S,I) 3861 } else if( CouldAssert(*,G,I) == TRUE ) { 3862 return rpt_assert_metric(G,I) 3863 } else { 3864 return infinite_assert_metric() 3865 } 3866 } 3868 spt_assert_metric(S,I) gives the assert metric we use if we're 3869 sending an assert based on active (S,G) forwarding state: 3871 assert_metric 3872 spt_assert_metric(S,I) { 3873 return {0,MRIB.pref(S),MRIB.metric(S),my_ip_address(I)} 3874 } 3876 rpt_assert_metric(G,I) gives the assert metric we use if we're 3877 sending an assert based only on (*,G) forwarding state: 3879 assert_metric 3880 rpt_assert_metric(G,I) { 3881 return {1,MRIB.pref(RP(G)),MRIB.metric(RP(G)),my_ip_address(I)} 3882 } 3884 MRIB.pref(X) and MRIB.metric(X) are the routing preference and 3885 routing metrics associated with the route to a particular (unicast) 3886 destination X, as determined by the MRIB. my_ip_address(I) is simply 3887 the router's primary IP address that is associated with the local 3888 interface I. 3890 infinite_assert_metric() gives the assert metric we need to send an 3891 assert but don't match either (S,G) or (*,G) forwarding state: 3893 assert_metric 3894 infinite_assert_metric() { 3895 return {1,infinity,infinity,0} 3896 } 3898 4.6.4. AssertCancel Messages 3900 An AssertCancel message is simply an RPT Assert message but with 3901 infinite metric. It is sent by the assert winner when it deletes the 3902 forwarding state that had caused the assert to occur. Other routers 3903 will see this metric, and it will cause any other router that has 3904 forwarding state to send its own assert, and to take over forwarding. 3906 An AssertCancel(S,G) is an infinite metric assert with the RPT bit 3907 set that names S as the source. 3909 An AssertCancel(*,G) is an infinite metric assert with the RPT bit 3910 set and the source set to zero. 3912 AssertCancel messages are simply an optimization. The original 3913 Assert timeout mechanism will allow a subnet to eventually become 3914 consistent; the AssertCancel mechanism simply causes faster 3915 convergence. No special processing is required for an AssertCancel 3916 message, since it is simply an Assert message from the current 3917 winner. 3919 4.6.5. Assert State Macros 3921 The macros lost_assert(S,G,rpt,I), lost_assert(S,G,I), and 3922 lost_assert(*,G,I) are used in the olist computations of Section 4.1, 3923 and are defined as: 3925 bool lost_assert(S,G,rpt,I) { 3926 if ( RPF_interface(RP(G)) == I OR 3927 ( RPF_interface(S) == I AND SPTbit(S,G) == TRUE ) ) { 3928 return FALSE 3929 } else { 3930 return ( AssertWinner(S,G,I) != NULL AND 3931 AssertWinner(S,G,I) != me ) 3932 } 3933 } 3934 bool lost_assert(S,G,I) { 3935 if ( RPF_interface(S) == I ) { 3936 return FALSE 3937 } else { 3938 return ( AssertWinner(S,G,I) != NULL AND 3939 AssertWinner(S,G,I) != me AND 3940 (AssertWinnerMetric(S,G,I) is better 3941 than spt_assert_metric(S,I) ) 3942 } 3943 } 3945 Note: the term "AssertWinnerMetric(S,G,I) is better than 3946 spt_assert_metric(S,I)" is required to correctly handle the 3947 transition phase when a router has (S,G) join state, but has not yet 3948 set the SPTbit. In this case, it needs to ignore the assert state if 3949 it will win the assert once the SPTbit is set. 3951 bool lost_assert(*,G,I) { 3952 if ( RPF_interface(RP(G)) == I ) { 3953 return FALSE 3954 } else { 3955 return ( AssertWinner(*,G,I) != NULL AND 3956 AssertWinner(*,G,I) != me ) 3957 } 3958 } 3960 AssertWinner(S,G,I) is the IP source address of the Assert(S,G) 3961 packet that won an Assert. 3963 AssertWinner(*,G,I) is the IP source address of the Assert(*,G) 3964 packet that won an Assert. 3966 AssertWinnerMetric(S,G,I) is the Assert metric of the Assert(S,G) 3967 packet that won an Assert. 3969 AssertWinnerMetric(*,G,I) is the Assert metric of the Assert(*,G) 3970 packet that won an Assert. 3972 AssertWinner(S,G,I) defaults to NULL and AssertWinnerMetric(S,G,I) 3973 defaults to Infinity when in the NoInfo state. 3975 Summary of Assert Rules and Rationale 3977 This section summarizes the key rules for sending and reacting to 3978 asserts and the rationale for these rules. This section is not 3979 intended to be and should not be treated as a definitive 3980 specification of protocol behavior. The state machines and 3981 pseudocode should be consulted for that purpose. Rather, this 3982 section is intended to document important aspects of the Assert 3983 protocol behavior and to provide information that may prove helpful 3984 to the reader in understanding and implementing this part of the 3985 protocol. 3987 1. Behavior: Downstream neighbors send Join(*,G) and Join(S,G) 3988 periodic messages to the appropriate RPF' neighbor, i.e., the RPF 3989 neighbor as modified by the assert process. They are not always 3990 sent to the RPF neighbor as indicated by the MRIB. Normal 3991 suppression and override rules apply. 3993 Rationale: By sending the periodic and triggered Join messages to 3994 the RPF' neighbor instead of to the RPF neighbor, the downstream 3995 router avoids re-triggering the Assert process with every Join. 3996 A side effect of sending Joins to the Assert winner is that 3997 traffic will not switch back to the "normal" RPF neighbor until 3998 the Assert times out. This will not happen until data stops 3999 flowing, if item 8, below, is implemented. 4001 2. Behavior: The assert winner for (*,G) acts as the local DR for 4002 (*,G) on behalf of IGMP/MLD members. 4004 Rationale: This is required to allow a single router to merge PIM 4005 and IGMP/MLD joins and leaves. Without this, overrides don't 4006 work. 4008 3. Behavior: The assert winner for (S,G) acts as the local DR for 4009 (S,G) on behalf of IGMPv3 members. 4011 Rationale: Same rationale as for item 2. 4013 4. Behavior: (S,G) and (*,G) prune overrides are sent to the RPF' 4014 neighbor and not to the regular RPF neighbor. 4016 Rationale: Same rationale as for item 1. 4018 5. Behavior: An (S,G,rpt) prune override is not sent (at all) if 4019 RPF'(S,G,rpt) != RPF'(*,G). 4021 Rationale: This avoids keeping state alive on the (S,G) tree when 4022 only (*,G) downstream members are left. Also, it avoids sending 4023 (S,G,rpt) joins to a router that is not on the (*,G) tree. This 4024 behavior might be confusing although this specification does 4025 indicate that such a join SHOULD be dropped. 4027 6. Behavior: An assert loser that receives a Join(S,G) with an 4028 Upstream Neighbor Address that is its primary IP address on that 4029 interface expires the (S,G) Assert Timer. 4031 Rationale: This is necessary in order to have rapid convergence 4032 in the event that the downstream router that initially sent a 4033 join to the prior Assert winner has undergone a topology change. 4035 7. Behavior: An assert loser that receives a Join(*,G) with an 4036 Upstream Neighbor Address that is its primary IP address on that 4037 interface cancels the (*,G) Assert Timer and all (S,G) assert 4038 timers that do not have corresponding Prune(S,G,rpt) messages in 4039 the compound Join/Prune message. 4041 Rationale: Same rationale as for item 6. 4043 8. Behavior: An assert winner for (*,G) or (S,G) sends a canceling 4044 assert when it is about to stop forwarding on a (*,G) or an (S,G) 4045 entry. This behavior does not apply to (S,G,rpt). 4047 Rationale: This allows switching back to the shared tree after 4048 the last SPT router on the LAN leaves. Doing this prevents 4049 downstream routers on the shared tree from keeping SPT state 4050 alive. 4052 9. Behavior: Resend the assert messages before timing out an assert. 4053 (This behavior is optional.) 4055 Rationale: This prevents the periodic duplicates that would 4056 otherwise occur each time that an assert times out and is then 4057 re-established. 4059 10. Behavior: When RPF'(S,G,rpt) changes to be the same as RPF'(*,G) 4060 we need to trigger a Join(S,G,rpt) to RPF'(*,G). 4062 Rationale: This allows switching back to the RPT after the last 4063 SPT member leaves. 4065 4.7. PIM Bootstrap and RP Discovery 4067 For correct operation, every PIM router within a PIM domain must be 4068 able to map a particular multicast group address to the same RP. If 4069 this is not the case, then black holes may appear, where some 4070 receivers in the domain cannot receive some groups. A domain in this 4071 context is a contiguous set of routers that all implement PIM and are 4072 configured to operate within a common boundary. 4074 A notable exception to this is where a PIM domain is broken up into 4075 multiple administrative scope regions; these are regions where a 4076 border has been configured so that a range of multicast groups will 4077 not be forwarded across that border. For more information on 4078 Administratively Scoped IP Multicast, see RFC 2365. The modified 4079 criteria for admin-scoped regions are that the region is convex with 4080 respect to forwarding based on the MRIB, and that all PIM routers 4081 within the scope region map scoped groups to the same RP within that 4082 region. 4084 This specification does not mandate the use of a single mechanism to 4085 provide routers with the information to perform the group-to-RP 4086 mapping. Currently four mechanisms are possible, and all four have 4087 associated problems: 4089 Static Configuration 4090 A PIM router MUST support the static configuration of group-to- 4091 RP mappings. Such a mechanism is not robust to failures, but 4092 does at least provide a basic interoperability mechanism. 4094 Embedded-RP 4095 Embedded-RP defines an address allocation policy in which the 4096 address of the Rendezvous Point (RP) is encoded in an IPv6 4097 multicast group address [17]. 4099 Cisco's Auto-RP 4100 Auto-RP uses a PIM Dense-Mode multicast group to announce group- 4101 to-RP mappings from a central location. This mechanism is not 4102 useful if PIM Dense-Mode is not being run in parallel with PIM 4103 Sparse-Mode, and was only intended for use with PIM Sparse-Mode 4104 Version 1. No standard specification currently exists. 4106 BootStrap Router (BSR) 4107 RFC 2362 specifies a bootstrap mechanism based on the automatic 4108 election of a bootstrap router (BSR). Any router in the domain 4109 that is configured to be a possible RP reports its candidacy to 4110 the BSR, and then a domain-wide flooding mechanism distributes 4111 the BSR's chosen set of RPs throughout the domain. As specified 4112 in RFC 2362, BSR is flawed in its handling of admin-scoped 4113 regions that are smaller than a PIM domain, but the mechanism 4114 does work for global-scoped groups. 4116 As far as PIM-SM is concerned, the only important requirement is that 4117 all routers in the domain (or admin scope zone for scoped regions) 4118 receive the same set of group-range-to-RP mappings. This may be 4119 achieved through the use of any of these mechanisms, or through 4120 alternative mechanisms not currently specified. 4122 It must be operationally ensured that any RP address configured, 4123 learned, or advertised is reachable from all routers in the PIM 4124 domain. 4126 4.7.1. Group-to-RP Mapping 4128 Using one of the mechanisms described above, a PIM router receives 4129 one or more possible group-range-to-RP mappings. Each mapping 4130 specifies a range of multicast groups (expressed as a group and mask) 4131 and the RP to which such groups should be mapped. Each mapping may 4132 also have an associated priority. It is possible to receive multiple 4133 mappings, all of which might match the same multicast group; this is 4134 the common case with BSR. The algorithm for performing the group-to- 4135 RP mapping is as follows: 4137 1. Perform longest match on group-range to obtain a list of RPs. 4139 2. From this list of matching RPs, find the ones with highest 4140 priority. 4142 Eliminate any RPs from the list that have lower priorities. 4144 3. If only one RP remains in the list, use that RP. 4146 4. If multiple RPs are in the list, use the PIM hash function to 4147 choose one. 4149 Thus, if two or more group-range-to-RP mappings cover a particular 4150 group, the one with the longest mask is the mapping to use. If the 4151 mappings have the same mask length, then the one with the highest 4152 priority is chosen. If there is more than one matching entry with 4153 the same longest mask and the priorities are identical, then a hash 4154 function (see Section 4.7.2) is applied to choose the RP. 4156 This algorithm is invoked by a DR when it needs to determine an RP 4157 for a given group, e.g., upon reception of a packet or IGMP/MLD 4158 membership indication for a group for which the DR does not know the 4159 RP. 4161 Furthermore, the mapping function is invoked by all routers upon 4162 receiving a (*,G) Join/Prune message. 4164 Note that if the set of possible group-range-to-RP mappings changes, 4165 each router will need to check whether any existing groups are 4166 affected. This may, for example, cause a DR or acting DR to re-join a 4167 group, or cause it to restart register encapsulation to the new RP. 4169 Implementation note: the bootstrap mechanism described in RFC 2362 4170 omitted step 1 above. However, of the implementations we are aware 4171 of, approximately half performed step 1 anyway. Note that 4172 implementations of BSR that omit step 1 will not correctly 4173 interoperate with implementations of this specification when used 4174 with the BSR mechanism described in [11]. 4176 4.7.2. Hash Function 4178 The hash function is used by all routers within a domain, to map a 4179 group to one of the RPs from the matching set of group-range-to-RP 4180 mappings (this set all have the same longest mask length and same 4181 highest priority). The algorithm takes as input the group address, 4182 and the addresses of the candidate RPs from the mappings, and gives 4183 as output one RP address to be used. 4185 The protocol requires that all routers hash to the same RP within a 4186 domain (except for transients). The following hash function must be 4187 used in each router: 4189 1. For RP addresses in the matching group-range-to-RP mappings, 4190 compute a value: 4192 Value(G,M,C(i))= 4193 (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31 4195 where C(i) is the RP address and M is a hash-mask. If BSR is 4196 being used, the hash-mask is given in the Bootstrap messages. If 4197 BSR is not being used, the alternative mechanism that supplies 4198 the group-range-to-RP mappings may supply the value, or else it 4199 defaults to a mask with the most significant 30 bits being one 4200 for IPv4 and the most significant 126 bits being one for IPv6. 4201 The hash-mask allows a small number of consecutive groups (e.g., 4202 4) to always hash to the same RP. For instance, hierarchically- 4203 encoded data can be sent on consecutive group addresses to get 4204 the same delay and fate-sharing characteristics. 4206 For address families other than IPv4, a 32-bit digest to be used 4207 as C(i) and G must first be derived from the actual RP or group 4208 address. Such a digest method must be used consistently 4209 throughout the PIM domain. For IPv6 addresses, it is RECOMMENDED 4210 to use the equivalent IPv4 address for an IPv4-compatible 4211 address, and the exclusive-or of each 32-bit segment of the 4212 address for all other IPv6 addresses. For example, the digest of 4213 the IPv6 address 3ffe:b00:c18:1::10 would be computed as 4214 0x3ffe0b00 ^ 0x0c180001 ^ 0x00000000 ^ 0x00000010, where ^ 4215 represents the exclusive-or operation. 4217 2. The candidate RP with the highest resulting hash value is then 4218 the RP chosen by this Hash Function. If more than one RP has the 4219 same highest hash value, the RP with the highest IP address is 4220 chosen. 4222 4.8. Source-Specific Multicast 4224 The Source-Specific Multicast (SSM) service model [6] can be 4225 implemented with a strict subset of the PIM-SM protocol mechanisms. 4226 Both regular IP Multicast and SSM semantics can coexist on a single 4227 router, and both can be implemented using the PIM-SM protocol. A 4228 range of multicast addresses, currently 232.0.0.0/8 in IPv4 and 4229 FF3x::/32 for IPv6, is reserved for SSM, and the choice of semantics 4230 is determined by the multicast group address in both data packets and 4231 PIM messages. 4233 4.8.1. Protocol Modifications for SSM Destination Addresses 4235 The following rules override the normal PIM-SM behavior for a 4236 multicast address G in the SSM range: 4238 o A router MUST NOT send a (*,G) Join/Prune message for any reason. 4240 o A router MUST NOT send an (S,G,rpt) Join/Prune message for any 4241 reason. 4243 o A router MUST NOT send a Register message for any packet that is 4244 destined to an SSM address. 4246 o A router MUST NOT forward packets based on (*,G) or (S,G,rpt) 4247 state. The (*,G)- and (S,G,rpt)-related state summarization macros 4248 are NULL for any SSM address, for the purposes of packet 4249 forwarding. 4251 o A router acting as an RP MUST NOT forward any Register-encapsulated 4252 packet that has an SSM destination address, and SHOULD respond with 4253 a Register-Stop message to such a Register message. 4255 o A router MAY optimize out the creation and maintenance of (S,G,rpt) 4256 and (*,G) state for SSM destination addresses -- this state is not 4257 needed for SSM packets. 4259 The last three rules are present to deal with SSM-unaware "legacy" 4260 routers that may be sending (*,G) and (S,G,rpt) Join/Prunes, or 4261 Register messages for SSM destination addresses. Note that this 4262 specification does not attempt to aid an SSM-unaware "legacy" router 4263 with SSM operations. 4265 4.8.2. PIM-SSM-Only Routers 4267 An implementer may choose to implement only the subset of PIM Sparse- 4268 Mode that provides SSM forwarding semantics. 4270 A PIM-SSM-only router MUST implement the following portions of this 4271 specification: 4273 o Upstream (S,G) state machine (Section 4.5.5) 4275 o Downstream (S,G) state machine (Section 4.5.2) 4277 o (S,G) Assert state machine (Section 4.6.1) 4279 o Hello messages, neighbor discovery, and DR election (Section 4.3) 4281 o Packet forwarding rules (Section 4.2) 4283 A PIM-SSM-only router does not need to implement the following 4284 protocol elements: 4286 o Register state machine (Section 4.4) 4288 o (*,G) and (S,G,rpt) Downstream state machines (Sections 4.5.2, 4289 4.5.4, and 4.5.1) 4291 o (*,G) and (S,G,rpt) Upstream state machines (Sections 4.5.6, 4.5.8, 4292 and 4.5.5) 4294 o (*,G) Assert state machine (Section 4.6.2) 4296 o Bootstrap RP Election (Section 4.7) 4298 o Keepalive Timer 4300 o SPTbit (Section 4.2.2) 4302 The Keepalive Timer should be treated as always running, and SPTbit 4303 should be treated as always being set for an SSM address. 4304 Additionally, the Packet forwarding rules of Section 4.2 can be 4305 simplified in a PIM-SSM-only router: 4307 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 4308 oiflist = inherited_olist(S,G) 4309 } else if( iif is in inherited_olist(S,G) ) { 4310 send Assert(S,G) on iif 4311 } 4313 oiflist = oiflist (-) iif 4314 forward packet on all interfaces in oiflist 4316 This is nothing more than the reduction of the normal PIM-SM 4317 forwarding rule, with all (S,G,rpt) and (*,G) clauses replaced with 4318 NULL. 4320 4.9. PIM Packet Formats 4322 This section describes the details of the packet formats for PIM 4323 control messages. 4325 All PIM control messages have IP protocol number 103. 4327 PIM messages are either unicast (e.g., Registers and Register-Stop) 4328 or multicast with TTL 1 to the 'ALL-PIM-ROUTERS' group (e.g., 4329 Join/Prune, Asserts, etc.). The source address used for unicast 4330 messages is a domain-wide reachable address; the source address used 4331 for multicast messages is the link-local address of the interface on 4332 which the message is being sent. 4334 The IPv4 'ALL-PIM-ROUTERS' group is '224.0.0.13'. The IPv6 'ALL-PIM- 4335 ROUTERS' group is 'ff02::d'. 4337 The PIM header common to all PIM messages is: 4339 0 1 2 3 4340 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 4341 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4342 |PIM Ver| Type | Reserved | Checksum | 4343 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4345 PIM Ver 4346 PIM Version number is 2. 4348 Type 4349 Types for specific PIM messages. PIM Types are: 4351 Message Type Destination 4352 --------------------------------------------------------------------- 4353 0 = Hello Multicast to ALL-PIM-ROUTERS 4354 1 = Register Unicast to RP 4355 2 = Register-Stop Unicast to source of Register 4356 packet 4357 3 = Join/Prune Multicast to ALL-PIM-ROUTERS 4358 4 = Bootstrap Multicast to ALL-PIM-ROUTERS 4359 5 = Assert Multicast to ALL-PIM-ROUTERS 4360 6 = Graft (used in PIM-DM only) Unicast to RPF'(S) 4361 7 = Graft-Ack (used in PIM-DM only) Unicast to source of Graft 4362 packet 4363 8 = Candidate-RP-Advertisement Unicast to Domain's BSR 4365 Reserved 4366 Set to zero on transmission. Ignored upon receipt. 4368 Checksum 4369 The checksum is a standard IP checksum, i.e., the 16-bit one's 4370 complement of the one's complement sum of the entire PIM 4371 message, excluding the "Multicast data packet" section of the 4372 Register message. For computing the checksum, the checksum 4373 field is zeroed. If the packet's length is not an integral 4374 number of 16-bit words, the packet is padded with a trailing 4375 byte of zero before performing the checksum. 4377 For IPv6, the checksum also includes the IPv6 "pseudo-header", 4378 as specified in RFC 2460, Section 8.1 [5]. This "pseudo-header" 4379 is prepended to the PIM header for the purposes of calculating 4380 the checksum. The "Upper-Layer Packet Length" in the pseudo- 4381 header is set to the length of the PIM message, except in 4382 Register messages where it is set to the length of the PIM 4383 register header (8). The Next Header value used in the pseudo- 4384 header is 103. 4386 If a message is received with an unrecognized PIM Ver or Type field, 4387 or if a message's destination does not correspond to the table above, 4388 the message MUST be discarded, and an error message SHOULD be logged 4389 to the administrator in a rate-limited manner. 4391 4.9.1. Encoded Source and Group Address Formats 4393 Encoded-Unicast Address 4395 An Encoded-Unicast address takes the following format: 4397 0 1 2 3 4398 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 4399 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4400 | Addr Family | Encoding Type | Unicast Address 4401 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4403 Addr Family 4404 The PIM address family of the 'Unicast Address' field of this 4405 address. 4407 Values 0-127 are as assigned by the IANA for Internet Address 4408 Families in [7]. Values 128-250 are reserved to be assigned by 4409 the IANA for PIM-specific Address Families. Values 251 though 4410 255 are designated for private use. As there is no assignment 4411 authority for this space, collisions should be expected. 4413 Encoding Type 4414 The type of encoding used within a specific Address Family. The 4415 value '0' is reserved for this field and represents the native 4416 encoding of the Address Family. 4418 Unicast Address 4419 The unicast address as represented by the given Address Family 4420 and Encoding Type. 4422 Encoded-Group Address 4424 Encoded-Group addresses take the following format: 4426 0 1 2 3 4427 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 4428 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4429 | Addr Family | Encoding Type |B| Reserved |Z| Mask Len | 4430 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4431 | Group multicast Address 4432 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4434 Addr Family 4435 Described above. 4437 Encoding Type 4438 Described above. 4440 [B]idirectional PIM 4441 Indicates the group range should use Bidirectional PIM [13]. 4442 For PIM-SM defined in this specification, this bit MUST be zero. 4444 Reserved 4445 Transmitted as zero. Ignored upon receipt. 4447 Admin Scope [Z]one 4448 indicates the group range is an admin scope zone. This is used 4449 in the Bootstrap Router Mechanism [11] only. For all other 4450 purposes, this bit is set to zero and ignored on receipt. 4452 Mask Len 4453 The Mask length field is 8 bits. The value is the number of 4454 contiguous one bits that are left justified and used as a mask; 4455 when combined with the group address, it describes a range of 4456 groups. It is less than or equal to the address length in bits 4457 for the given Address Family and Encoding Type. If the message 4458 is sent for a single group, then the Mask length must equal the 4459 address length in bits for the given Address Family and Encoding 4460 Type (e.g., 32 for IPv4 native encoding, 128 for IPv6 native 4461 encoding). 4463 Group multicast Address 4464 Contains the group address. 4466 Encoded-Source Address 4468 Encoded-Source address takes the following format: 4470 0 1 2 3 4471 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 4472 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4473 | Addr Family | Encoding Type | Rsrvd |S|W|R| Mask Len | 4474 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4475 | Source Address 4476 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... 4478 Addr Family 4479 Described above. 4481 Encoding Type 4482 Described above. 4484 Reserved 4485 Transmitted as zero, ignored on receipt. 4487 S The Sparse bit is a 1-bit value, set to 1 for PIM-SM. It is 4488 used for PIM version 1 compatibility. 4490 W The WC (or WildCard) bit is a 1-bit value for use with PIM 4491 Join/Prune messages (see Section 4.9.5.1). 4493 R The RPT (or Rendezvous Point Tree) bit is a 1-bit value for use 4494 with PIM Join/Prune messages (see Section 4.9.5.1). If the WC 4495 bit is 1, the RPT bit MUST be 1. 4497 Mask Len 4498 The mask length field is 8 bits. The value is the number of 4499 contiguous one bits left justified used as a mask which, 4500 combined with the Source Address, describes a source subnet. 4501 The mask length MUST be equal to the mask length in bits for the 4502 given Address Family and Encoding Type (32 for IPv4 native and 4503 128 for IPv6 native). A router SHOULD ignore any messages 4504 received with any other mask length. 4506 Source Address 4507 The source address. 4509 4.9.2. Hello Message Format 4511 It is sent periodically by routers on all interfaces. 4513 0 1 2 3 4514 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 4515 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4516 |PIM Ver| Type | Reserved | Checksum | 4517 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4518 | OptionType | OptionLength | 4519 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4520 | OptionValue | 4521 | ... | 4522 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4523 | . | 4524 | . | 4525 | . | 4526 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4527 | OptionType | OptionLength | 4528 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4529 | OptionValue | 4530 | ... | 4531 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4533 PIM Version, Type, Reserved, Checksum 4534 Described in Section 4.9. 4536 OptionType 4537 The type of the option given in the following OptionValue field. 4539 OptionLength 4540 The length of the OptionValue field in bytes. 4542 OptionValue 4543 A variable length field, carrying the value of the option. 4545 The Option fields may contain the following values: 4547 o OptionType 1: Holdtime 4549 0 1 2 3 4550 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 4551 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4552 | Type = 1 | Length = 2 | 4553 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4554 | Holdtime | 4555 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4557 Holdtime is the amount of time a receiver must keep the neighbor 4558 reachable, in seconds. If the Holdtime is set to '0xffff', the 4559 receiver of this message never times out the neighbor. This may be 4560 used with dial-on-demand links, to avoid keeping the link up with 4561 periodic Hello messages. 4563 An implementation MAY provide a configuration mechanism to reject a 4564 Hello message with holdtime 0xffff, and/or provide a mechanism to 4565 remove a neighbor. 4567 Hello messages with a Holdtime value set to '0' are also sent by a 4568 router on an interface about to go down or changing IP address (see 4569 Section 4.3.1). These are effectively goodbye messages, and the 4570 receiving routers SHOULD immediately time out the neighbor 4571 information for the sender. 4573 o OptionType 2: LAN Prune Delay 4575 0 1 2 3 4576 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 4577 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4578 | Type = 2 | Length = 4 | 4579 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4580 |T| Propagation_Delay | Override_Interval | 4581 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4583 The LAN Prune Delay option is used to tune the prune propagation 4584 delay on multi-access LANs. The T bit specifies the ability of the 4585 sending router to disable join suppression. Propagation_Delay and 4586 Override_Interval are time intervals in units of milliseconds. A 4587 router originating a LAN Prune Delay option on interface I sets the 4588 Propagation_Delay field to the configured value of 4589 Propagation_Delay(I) and the value of the Override_Interval field 4590 to the value of Override_Interval(I). On a receiving router, the 4591 values of the fields are used to tune the value of the 4592 Effective_Override_Interval(I) and its derived timer values. 4594 Section 4.3.3 describes how these values affect the behavior of a 4595 router. 4597 o OptionType 3 to 16: reserved to be defined in future versions of 4598 this document. 4600 o OptionType 18: deprecated and should not be used. 4602 o OptionType 19: DR Priority 4604 0 1 2 3 4605 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 4606 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4607 | Type = 19 | Length = 4 | 4608 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4609 | DR Priority | 4610 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4612 DR Priority is a 32-bit unsigned number and should be considered in 4613 the DR election as described in Section 4.3.2. 4615 o OptionType 20: Generation ID 4617 0 1 2 3 4618 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 4619 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4620 | Type = 20 | Length = 4 | 4621 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4622 | Generation ID | 4623 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4625 Generation ID is a random 32-bit value for the interface on which 4626 the Hello message is sent. The Generation ID is regenerated 4627 whenever PIM forwarding is started or restarted on the interface. 4629 o OptionType 24: Address List 4631 0 1 2 3 4632 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 4633 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4634 | Type = 24 | Length = | 4635 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4636 | Secondary Address 1 (Encoded-Unicast format) | 4637 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4638 ... 4639 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4640 | Secondary Address N (Encoded-Unicast format) | 4641 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4643 The contents of the Address List Hello option are described in 4644 Section 4.3.4. All addresses within a single Address List must 4645 belong to the same address family. 4647 OptionTypes 17 through 65000 are assigned by the IANA. OptionTypes 4648 65001 through 65535 are reserved for Private Use, as defined in [9]. 4650 Unknown options MUST be ignored and MUST NOT prevent a neighbor 4651 relationship from being formed. The "Holdtime" option MUST be 4652 implemented; the "DR Priority" and "Generation ID" options SHOULD be 4653 implemented. The "Address List" option MUST be implemented for IPv6. 4655 4.9.3. Register Message Format 4657 A Register message is sent by the DR to the RP when a multicast 4658 packet needs to be transmitted on the RP-tree. The IP source address 4659 is set to the address of the DR, the destination address to the RP's 4660 address. The IP TTL of the PIM packet is the system's normal unicast 4661 TTL. 4663 0 1 2 3 4664 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 4665 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4666 |PIM Ver| Type | Reserved | Checksum | 4667 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4668 |B|N| Reserved2 | 4669 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4670 | | 4671 . Multicast data packet . 4672 | | 4673 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4674 PIM Version, Type, Reserved, Checksum 4675 Described in Section 4.9. Note that in order to reduce 4676 encapsulation overhead, the checksum for Registers is done only 4677 on the first 8 bytes of the packet, including the PIM header and 4678 the next 4 bytes, excluding the data packet portion. For 4679 interoperability reasons, a message carrying a checksum 4680 calculated over the entire PIM Register message should also be 4681 accepted. When calculating the checksum, the IPv6 pseudoheader 4682 "Upper-Layer Packet Length" is set to 8. 4684 B The Border bit. This specification deprecates the Border bit. A 4685 router MUST set B bit to 0 on tranmission and MUST ignore this 4686 bit on reception. 4688 N The Null-Register bit. Set to 1 by a DR that is probing the RP 4689 before expiring its local Register-Suppression Timer. Set to 0 4690 otherwise. 4692 Reserved2 4693 Transmitted as zero, ignored on receipt. 4695 Multicast data packet 4696 The original packet sent by the source. This packet must be of 4697 the same address family as the encapsulating PIM packet, e.g., 4698 an IPv6 data packet must be encapsulated in an IPv6 PIM packet. 4699 Note that the TTL of the original packet is decremented before 4700 encapsulation, just like any other packet that is forwarded. In 4701 addition, the RP decrements the TTL after decapsulating, before 4702 forwarding the packet down the shared tree. 4704 For (S,G) Null-Registers, the Multicast data packet portion 4705 contains a dummy IP header with S as the source address, G as 4706 the destination address. When generating an IPv4 Null-Register 4707 message, the fields in the dummy IPv4 header SHOULD be filled in 4708 according to the following table. Other IPv4 header fields may 4709 contain any value that is valid for that field. 4711 Field Value 4712 --------------------------------------- 4713 IP Version 4 4714 Header Length 5 4715 Checksum Header checksum 4716 Fragmentation offset 0 4717 More Fragments 0 4718 Total Length 20 4719 IP Protocol 103 (PIM) 4721 On receipt of an (S,G) Null-Register, if the Header Checksum 4722 field is non-zero, the recipient SHOULD check the checksum and 4723 discard null registers that have a bad checksum. The recipient 4724 SHOULD NOT check the value of any individual fields; a correct 4725 IP header checksum is sufficient. If the Header Checksum field 4726 is zero, the recipient MUST NOT check the checksum. 4728 With IPv6, an implementation generates a dummy IP header 4729 followed by a dummy PIM header with values according to the 4730 following table in addition to the source and group. Other IPv6 4731 header fields may contain any value that is valid for that 4732 field. 4734 Header Field Value 4735 -------------------------------------- 4736 IP Version 6 4737 Next Header 103 (PIM) 4738 Length 4 4739 PIM Version 0 4740 PIM Type 0 4741 PIM Reserved 0 4742 PIM Checksum PIM checksum including 4743 IPv6 "pseudo-header"; 4744 see Section 4.9 4746 On receipt of an IPv6 (S,G) Null-Register, if the dummy PIM 4747 header is present, the recipient SHOULD check the checksum and 4748 discard Null-Registers that have a bad checksum. 4750 4.9.4. Register-Stop Message Format 4752 A Register-Stop is unicast from the RP to the sender of the Register 4753 message. The IP source address is the address to which the register 4754 was addressed. The IP destination address is the source address of 4755 the register message. 4757 0 1 2 3 4758 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 4759 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4760 |PIM Ver| Type | Reserved | Checksum | 4761 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4762 | Group Address (Encoded-Group format) | 4763 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4764 | Source Address (Encoded-Unicast format) | 4765 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4767 PIM Version, Type, Reserved, Checksum 4768 Described in Section 4.9. 4770 Group Address 4771 The group address from the multicast data packet in the 4772 Register. Format described in Section 4.9.1. Note that for 4773 Register-Stops the Mask Len field contains the full address 4774 length * 8 (e.g., 32 for IPv4 native encoding), if the message 4775 is sent for a single group. 4777 Source Address 4778 The host address of the source from the multicast data packet in 4779 the register. The format for this address is given in the 4780 Encoded-Unicast address in Section 4.9.1. A special wild card 4781 value consisting of an address field of all zeros can be used to 4782 indicate any source. 4784 4.9.5. Join/Prune Message Format 4786 A Join/Prune message is sent by routers towards upstream sources and 4787 RPs. Joins are sent to build shared trees (RP trees) or source trees 4788 (SPT). Prunes are sent to prune source trees when members leave 4789 groups as well as sources that do not use the shared tree. 4791 0 1 2 3 4792 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 4793 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4794 |PIM Ver| Type | Reserved | Checksum | 4795 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4796 | Upstream Neighbor Address (Encoded-Unicast format) | 4797 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4798 | Reserved | Num groups | Holdtime | 4799 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4800 | Multicast Group Address 1 (Encoded-Group format) | 4801 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4802 | Number of Joined Sources | Number of Pruned Sources | 4803 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4804 | Joined Source Address 1 (Encoded-Source format) | 4805 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4806 | . | 4807 | . | 4808 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4809 | Joined Source Address n (Encoded-Source format) | 4810 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4811 | Pruned Source Address 1 (Encoded-Source format) | 4812 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4813 | . | 4814 | . | 4815 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4816 | Pruned Source Address n (Encoded-Source format) | 4817 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4818 | . | 4819 | . | 4820 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4821 | Multicast Group Address m (Encoded-Group format) | 4822 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4823 | Number of Joined Sources | Number of Pruned Sources | 4824 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4825 | Joined Source Address 1 (Encoded-Source format) | 4826 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4827 | . | 4828 | . | 4829 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4830 | Joined Source Address n (Encoded-Source format) | 4831 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4832 | Pruned Source Address 1 (Encoded-Source format) | 4833 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4834 | . | 4835 | . | 4836 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4837 | Pruned Source Address n (Encoded-Source format) | 4838 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4839 PIM Version, Type, Reserved, Checksum 4840 Described in Section 4.9. 4842 Unicast Upstream Neighbor Address 4843 The address of the upstream neighbor that is the target of the 4844 message. The format for this address is given in the Encoded- 4845 Unicast address in Section 4.9.1. For IPv6 the source address 4846 used for multicast messages is the link-local address of the 4847 interface on which the message is being sent. For IPv4, the 4848 source address is the primary address associated with that 4849 interface. 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 RPT-bit is a 1-bit value. The RPT-bit is set to 1 for 5101 Assert(*,G) 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 RPT-bit 5120 is set to 0, the Metric-Preference is set to MRIB.pref(S) and 5121 the 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 RPT-bit 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 use 5636 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 PIM-SM 5733 Implementations and Deployments", draft-ietf-pim-rfc4601-update- 5734 survey-report-03.txt, September 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 Mulitcast 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