idnits 2.17.1 draft-ietf-pim-sm-v2-new-08.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 535 instances of too long lines in the document, the longest one being 7 characters in excess of 72. == There are 2 instances of lines with multicast IPv4 addresses in the document. If these are generic example addresses, they should be changed to use the 233.252.0.x range defined in RFC 5771 == There are 1 instance of lines with non-RFC3849-compliant IPv6 addresses in the document. If these are example addresses, they should be changed. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 1260: '...Hello messages MUST be sent on all act...' RFC 2119 keyword, line 1266: '...liant PIM router MUST send Hello messa...' RFC 2119 keyword, line 1281: '...yet sent a Hello message, then it MUST...' RFC 2119 keyword, line 1288: '...Option SHOULD be included in every Hel...' RFC 2119 keyword, line 1294: '...r (GenID) Option SHOULD be included in...' (52 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: There is an exception with group sets that contain a (*,G) Join source list entry. The group set expresses the router's interest in receiving all traffic for the specified group on the shared tree and it MUST include an (S,G,rpt) Prune source list entry for every source that the router does not wish to receive. This list of (S,G,rpt) Prune source-list entries MUST not be split in multiple messages. -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (1 October 2003) is 7507 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: 'Actions A1' on line 3920 -- Looks like a reference, but probably isn't: 'Actions A6' on line 3579 -- Looks like a reference, but probably isn't: 'Actions A3' on line 3931 -- Looks like a reference, but probably isn't: 'Actions A2' on line 3944 -- Looks like a reference, but probably isn't: 'Actions A4' on line 3931 -- Looks like a reference, but probably isn't: 'Actions A5' on line 3956 ** Obsolete normative reference: RFC 2283 (ref. '1') (Obsoleted by RFC 2858) ** Downref: Normative reference to an Informational RFC: RFC 2983 (ref. '2') ** Obsolete normative reference: RFC 2460 (ref. '5') (Obsoleted by RFC 8200) == Outdated reference: A later version (-12) exists of draft-ietf-pim-sm-bsr-03 == Outdated reference: A later version (-09) exists of draft-ietf-pim-bidir-04 ** Obsolete normative reference: RFC 2409 (ref. '9') (Obsoleted by RFC 4306) == Outdated reference: A later version (-04) exists of draft-holbrook-ssm-00 -- Possible downref: Normative reference to a draft: ref. '10' -- Possible downref: Non-RFC (?) normative reference: ref. '11' ** Obsolete normative reference: RFC 2401 (ref. '12') (Obsoleted by RFC 4301) ** Obsolete normative reference: RFC 2434 (ref. '13') (Obsoleted by RFC 5226) ** Downref: Normative reference to an Informational RFC: RFC 2715 (ref. '14') Summary: 11 errors (**), 0 flaws (~~), 7 warnings (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Engineering Task Force PIM WG 2 INTERNET-DRAFT Bill Fenner/AT&T 3 draft-ietf-pim-sm-v2-new-08.txt Mark Handley/ICIR 4 Hugh Holbrook/Cisco 5 Isidor Kouvelas/Cisco 6 1 October 2003 7 Expires: April 2004 9 Protocol Independent Multicast - Sparse Mode (PIM-SM): 10 Protocol Specification (Revised) 12 Status of this Document 14 This document is an Internet-Draft and is in full conformance with all 15 provisions of Section 10 of RFC2026. 17 Internet-Drafts are working documents of the Internet Engineering Task 18 Force (IETF), its areas, and its working groups. Note that other groups 19 may also distribute working documents as Internet-Drafts. 21 Internet-Drafts are draft documents valid for a maximum of six months 22 and may be updated, replaced, or obsoleted by other documents at any 23 time. It is inappropriate to use Internet-Drafts as reference material 24 or to cite them other than as "work in progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html. 32 This document is a product of the IETF PIM WG. Comments should be 33 addressed to the authors, or the WG's mailing list at 34 pim@catarina.usc.edu. 36 Abstract 38 This document specifies Protocol Independent Multicast - 39 Sparse Mode (PIM-SM). PIM-SM is a multicast routing protocol 40 that can use the underlying unicast routing information base 41 or a separate multicast-capable routing information base. It 42 builds unidirectional shared trees rooted at a Rendezvous 43 Point (RP) per group, and optionally creates shortest-path 44 trees per source. 46 Table of Contents 48 1. Introduction. . . . . . . . . . . . . . . . . . . . . . 6 49 2. Terminology . . . . . . . . . . . . . . . . . . . . . . 6 50 2.1. Definitions. . . . . . . . . . . . . . . . . . . . . 6 51 2.2. Pseudocode Notation. . . . . . . . . . . . . . . . . 7 52 3. PIM-SM Protocol Overview. . . . . . . . . . . . . . . . 8 53 4. Protocol Specification. . . . . . . . . . . . . . . . . 13 54 4.1. PIM Protocol State . . . . . . . . . . . . . . . . . 13 55 4.1.1. General Purpose State . . . . . . . . . . . . . . 14 56 4.1.2. (*,*,RP) State. . . . . . . . . . . . . . . . . . 15 57 4.1.3. (*,G) State . . . . . . . . . . . . . . . . . . . 16 58 4.1.4. (S,G) State . . . . . . . . . . . . . . . . . . . 17 59 4.1.5. (S,G,rpt) State . . . . . . . . . . . . . . . . . 19 60 4.1.6. State Summarization Macros. . . . . . . . . . . . 20 61 4.2. Data Packet Forwarding Rules . . . . . . . . . . . . 25 62 4.2.1. Last hop switchover to the SPT. . . . . . . . . . 27 63 4.2.2. Setting and Clearing the (S,G) SPT bit. . . . . . 27 64 4.3. Designated Routers (DR) and Hello Messages . . . . . 29 65 4.3.1. Sending Hello Messages. . . . . . . . . . . . . . 29 66 4.3.2. DR Election . . . . . . . . . . . . . . . . . . . 31 67 4.3.3. Reducing Prune Propagation Delay on LANs. . . . . 33 68 4.3.4. Maintaining Secondary Address Lists . . . . . . . 35 69 4.4. PIM Register Messages. . . . . . . . . . . . . . . . 36 70 4.4.1. Sending Register Messages from the DR . . . . . . 36 71 4.4.2. Receiving Register Messages at the RP . . . . . . 41 72 4.5. PIM Join/Prune Messages. . . . . . . . . . . . . . . 42 73 4.5.1. Receiving (*,*,RP) Join/Prune Messages. . . . . . 43 74 4.5.2. Receiving (*,G) Join/Prune Messages . . . . . . . 46 75 4.5.3. Receiving (S,G) Join/Prune Messages . . . . . . . 50 76 4.5.4. Receiving (S,G,rpt) Join/Prune Messages . . . . . 53 77 4.5.5. Sending (*,*,RP) Join/Prune Messages. . . . . . . 59 78 4.5.6. Sending (*,G) Join/Prune Messages . . . . . . . . 63 79 4.5.7. Sending (S,G) Join/Prune Messages . . . . . . . . 68 80 4.5.8. (S,G,rpt) Periodic Messages . . . . . . . . . . . 73 81 4.5.9. State Machine for (S,G,rpt) Triggered Mes- 82 sages. . . . . . . . . . . . . . . . . . . . . . . . . . 74 83 4.5.10. Background: (*,*,RP) and (S,G,rpt) inter- 84 action . . . . . . . . . . . . . . . . . . . . . . . . . 78 85 4.6. PIM Assert Messages. . . . . . . . . . . . . . . . . 80 86 4.6.1. (S,G) Assert Message State Machine. . . . . . . . 80 87 4.6.2. (*,G) Assert Message State Machine. . . . . . . . 87 88 4.6.3. Assert Metrics. . . . . . . . . . . . . . . . . . 94 89 4.6.4. AssertCancel Messages . . . . . . . . . . . . . . 95 90 4.6.5. Assert State Macros . . . . . . . . . . . . . . . 96 91 4.7. PIM Multicast Border Router Behavior . . . . . . . . 99 92 4.7.1. Sources External to the PIM-SM Domain . . . . . . 100 93 4.7.2. Sources Internal to the PIM-SM Domain . . . . . . 100 94 4.8. PIM Bootstrap and RP Discovery . . . . . . . . . . . 102 95 4.8.1. Group-to-RP Mapping . . . . . . . . . . . . . . . 103 96 4.8.2. Hash Function . . . . . . . . . . . . . . . . . . 104 97 4.9. Source-Specific Multicast. . . . . . . . . . . . . . 105 98 4.9.1. Protocol Modifications for SSM destination 99 addresses. . . . . . . . . . . . . . . . . . . . . . . . 105 100 4.9.2. PIM-SSM-only Routers. . . . . . . . . . . . . . . 106 101 4.10. PIM Packet Formats. . . . . . . . . . . . . . . . . 107 102 4.10.1. Encoded Source and Group Address 103 Formats. . . . . . . . . . . . . . . . . . . . . . . . . 108 104 4.10.2. Hello Message Format . . . . . . . . . . . . . . 112 105 4.10.3. Register Message Format. . . . . . . . . . . . . 115 106 4.10.4. Register-Stop Message Format . . . . . . . . . . 116 107 4.10.5. Join/Prune Message Format. . . . . . . . . . . . 117 108 4.10.5.1. Group Set Source List Rules . . . . . . . . . 120 109 4.10.5.2. Group Set Fragmentation . . . . . . . . . . . 124 110 4.10.6. Assert Message Format. . . . . . . . . . . . . . 124 111 4.11. PIM Timers. . . . . . . . . . . . . . . . . . . . . 126 112 4.12. Timer Values. . . . . . . . . . . . . . . . . . . . 127 113 5. IANA Considerations . . . . . . . . . . . . . . . . . . 133 114 5.1. PIM Address Family . . . . . . . . . . . . . . . . . 133 115 5.2. PIM Hello Options. . . . . . . . . . . . . . . . . . 134 116 6. Security Considerations . . . . . . . . . . . . . . . . 134 117 6.1. Attacks based on forged messages . . . . . . . . . . 134 118 6.1.1. Forged link-local messages. . . . . . . . . . . . 134 119 6.1.2. Forged unicast messages . . . . . . . . . . . . . 135 120 6.2. Non-cryptographic Authentication Mechanisms. . . . . 135 121 6.3. Authentication using IPsec . . . . . . . . . . . . . 136 122 6.3.1. Protecting link-local multicast messages. . . . . 136 123 6.3.2. Protecting unicast messages . . . . . . . . . . . 137 124 6.3.2.1. Register messages. . . . . . . . . . . . . . . 137 125 6.3.2.2. Register-Stop messages . . . . . . . . . . . . 137 126 6.4. Denial of Service Attacks. . . . . . . . . . . . . . 138 127 7. Authors' Addresses. . . . . . . . . . . . . . . . . . . 138 128 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . 139 129 9. References. . . . . . . . . . . . . . . . . . . . . . . 139 130 10. Index. . . . . . . . . . . . . . . . . . . . . . . . . 141 132 List of Figures 134 Figure 1. Per-(S,G) register state-machine at a DR . . . . 37 135 Figure 2. Downstream per-interface (*,*,RP) state- 136 machine. . . . . . . . . . . . . . . . . . . . . . . . . . 43 137 Figure 3. Downstream per-interfacce (*,G) state- 138 machine. . . . . . . . . . . . . . . . . . . . . . . . . . 47 139 Figure 4. Downstream per-interface (S,G) state- 140 machine. . . . . . . . . . . . . . . . . . . . . . . . . . 51 141 Figure 5. Downstream per-interface (S,G,rpt) state- 142 machine. . . . . . . . . . . . . . . . . . . . . . . . . . 54 143 Figure 6. Upstream (*,*,RP) state-machine. . . . . . . . . 59 144 Figure 7. Upstream (*,G) state-machine . . . . . . . . . . 64 145 Figure 8. Upstream (S,G) state-machine . . . . . . . . . . 69 146 Figure 9. Upstream (S,G,rpt) state-machine for trig- 147 gered messages . . . . . . . . . . . . . . . . . . . . . . 74 148 Figure 10. Per-interface (S,G) Assert 149 State-machine. . . . . . . . . . . . . . . . . . . . . . . 81 150 Figure 11. Per-interface (*,G) Assert 151 State-machine. . . . . . . . . . . . . . . . . . . . . . . 88 153 1. Introduction 155 This document specifies a protocol for efficiently routing multicast 156 groups that may span wide-area (and inter-domain) internets. This 157 protocol is called Protocol Independent Multicast - Sparse Mode (PIM-SM) 158 because, although it may use the underlying unicast routing to provide 159 reverse-path information for multicast tree building, it is not 160 dependent on any particular unicast routing protocol. 162 PIM-SM version 2 was originally specified in RFC 2117, and revised in 163 RFC 2362. This document is intended to obsolete RFC 2362, and to 164 correct a number of deficiencies that have been identified with the way 165 PIM-SM was previously specified. As far as possible, this document 166 specifies the same protocol as RFC 2362, and only diverges from the 167 behavior intended by RFC 2362 when the previously specified behavior was 168 clearly incorrect. Routers implemented according to the specification 169 in this document will be able to successfully interoperate with routers 170 implemented according to RFC 2362. 172 2. Terminology 174 In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", 175 "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and 176 "OPTIONAL" are to be interpreted as described in RFC 2119 and indicate 177 requirement levels for compliant PIM-SM implementations. 179 2.1. Definitions 181 This specification uses a number of terms to refer to the roles of 182 routers participating in PIM-SM. The following terms have special 183 significance for PIM-SM: 185 Rendezvous Point (RP): 186 An RP is a router that has been configured to be used as the root 187 of the non-source-specific distribution tree for a multicast 188 group. Join messages from receivers for a group are sent towards 189 the RP, and data from senders is sent to the RP so that receivers 190 can discover who the senders are, and start to receive traffic 191 destined for the group. 193 Designated Router (DR): 194 A shared-media LAN like Ethernet may have multiple PIM-SM routers 195 connected to it. If the LAN has directly connected hosts, then a 196 single one of these routers, the DR, will act on behalf of those 197 hosts with respect to the PIM-SM protocol. A single DR is elected 198 per interface (LAN or otherwise) using a simple election process. 200 MRIB Multicast Routing Information Base. This is the multicast 201 topology table, which is typically derived from the unicast 202 routing table, or routing protocols such as MBGP that carry 203 multicast-specific topology information. In PIM-SM, the MRIB is 204 used to decide where to send Join/Prune messages. A secondary 205 function of the MRIB is to provide routing metrics for destination 206 addresses, these metrics are used when sending and processing 207 Assert messages. 209 RPF Neighbor 210 RPF stands for "Reverse Path Forwarding". The RPF Neighbor of a 211 router with respect to an address is the neighbor that the MRIB 212 indicates should be used to forward packets to that address. In 213 the case of a PIM-SM multicast group, the RPF neighbor is the 214 router that a Join message for that group would be directed to, in 215 the absence of modifying Assert state. 217 TIB Tree Information Base. This is the collection of state at a PIM 218 router that has been created by receiving PIM Join/Prune messages, 219 PIM Assert messages, and IGMP or MLD information from local hosts. 220 It essentially stores the state of all multicast distribution 221 trees at that router. 223 MFIB Multicast Forwarding Information Base. The TIB holds all the 224 state that is necessary to forward multicast packets at a router. 225 However, although this specification defines forwarding in terms 226 of the TIB, to actually forward packets using the TIB is very 227 inefficient. Instead a real router implementation will normally 228 build an efficient MFIB from the TIB state to perform forwarding. 229 How this is done is implementation-specific, and is not discussed 230 in this document. 232 Upstream 233 Towards the root of the tree. The root of tree may either be the 234 source or the RP depending on the context. 236 Downstream 237 Away from the root of the tree. 239 2.2. Pseudocode Notation 241 We use set notation in several places in this specification. 243 A (+) B 244 is the union of two sets A and B. 246 A (-) B 247 is the elements of set A that are not in set B. 249 NULL 250 is the empty set or list. 252 In addition, we use C-like syntax: 254 = denotes assignment of a variable. 256 == denotes a comparison for equality. 258 != denotes a comparison for inequality. 260 Braces { and } are used for grouping. 262 3. PIM-SM Protocol Overview 264 This section provides an overview of PIM-SM behavior. It is intended as 265 an introduction to how PIM-SM works, and is NOT definitive. For the 266 definitive specification, see Section 4. 268 PIM relies on an underlying topology-gathering protocol to populate a 269 routing table with routes. This routing table is called the MRIB or 270 Multicast Routing Information Base. The routes in this table may be 271 taken directly from the unicast routing table, or it may be different 272 and provided by a separate routing protocol such as MBGP [1]. Regardless 273 of how it is created, the primary role of the MRIB in the PIM protocol 274 is to provide the next hop router along a multicast-capable path to each 275 destination subnet. The MRIB is used to determine the next hop neighbor 276 to which any PIM Join/Prune message is sent. Data flows along the 277 reverse path of the Join messages. Thus, in contrast to the unicast RIB 278 which specifies the next hop that a data packet would take to get to 279 some subnet, the MRIB gives reverse-path information, and indicates the 280 path that a multicast data packet would take from its origin subnet to 281 the router that has the MRIB. 283 Like all multicast routing protocols that implement the service model 284 from RFC 1112 [3], PIM-SM must be able to route data packets from 285 sources to receivers without either the sources or receivers knowing a- 286 priori of the existence of the others. This is essentially done in 287 three phases, although as senders and receivers may come and go at any 288 time, all three phases may be occur simultaneously. 290 Phase One: RP Tree 292 In phase one, a multicast receiver expresses its interest in receiving 293 traffic destined for a multicast group. Typically it does this using 294 IGMP [6] or MLD [4], but other mechanisms might also serve this purpose. 295 One of the receiver's local routers is elected as the Designated Router 296 (DR) for that subnet. On receiving the receiver's expression of 297 interest, the DR then sends a PIM Join message towards the RP for that 298 multicast group. This Join message is known as a (*,G) Join because it 299 joins group G for all sources to that group. The (*,G) Join travels 300 hop-by-hop towards the RP for the group, and in each router it passes 301 through, multicast tree state for group G is instantiated. Eventually 302 the (*,G) Join either reaches the RP, or reaches a router that already 303 has (*,G) Join state for that group. When many receivers join the 304 group, their Join messages converge on the RP, and form a distribution 305 tree for group G that is rooted at the RP. This is known as the RP Tree 306 (RPT), and is also known as the shared tree because it is shared by all 307 sources sending to that group. Join messages are resent periodically so 308 long as the receiver remains in the group. When all receivers on a 309 leaf-network leave the group, the DR will send a PIM (*,G) Prune message 310 towards the RP for that multicast group. However if the Prune message is 311 not sent for any reason, the state will eventually time out. 313 A multicast data sender just starts sending data destined for a 314 multicast group. The sender's local router (DR) takes those data 315 packets, unicast-encapsulates them, and sends them directly to the RP. 316 The RP receives these encapsulated data packets, decapsulates them, and 317 forwards them onto the shared tree. The packets then follow the (*,G) 318 multicast tree state in the routers on the RP Tree, being replicated 319 wherever the RP Tree branches, and eventually reaching all the receivers 320 for that multicast group. The process of encapsulating data packets to 321 the RP is called registering, and the encapsulation packets are known as 322 PIM Register packets. 324 At the end of phase one, multicast traffic is flowing encapsulated to 325 the RP, and then natively over the RP tree to the multicast receivers. 327 Phase Two: Register-Stop 329 Register-encapsulation of data packets is inefficient for two reasons: 331 o Encapsulation and decapsulation may be relatively expensive operations 332 for a router to perform, depending on whether or not the router has 333 appropriate hardware for these tasks. 335 o Traveling all the way to the RP, and then back down the shared tree 336 may entail the packets traveling a relatively long distance to reach 337 receivers that are close to the sender. For some applications, this 338 increased latency is undesirable. 340 Although Register-encapsulation may continue indefinitely, for these 341 reasons, the RP will normally choose to switch to native forwarding. To 342 do this, when the RP receives a register-encapsulated data packet from 343 source S on group G, it will normally initiate an (S,G) source-specific 344 Join towards S. This Join message travels hop-by-hop towards S, 345 instantiating (S,G) multicast tree state in the routers along the path. 346 (S,G) multicast tree state is used only to forward packets for group G 347 if those packets come from source S. Eventually the Join message 348 reaches S's subnet or a router that already has (S,G) multicast tree 349 state, and then packets from S start to flow following the (S,G) tree 350 state towards the RP. These data packets may also reach routers with 351 (*,G) state along the path towards the RP - if so, they can short-cut 352 onto the RP tree at this point. 354 While the RP is in the process of joining the source-specific tree for 355 S, the data packets will continue being encapsulated to the RP. When 356 packets from S also start to arrive natively at the the RP, the RP will 357 be receiving two copies of each of these packets. At this point, the RP 358 starts to discard the encapsulated copy of these packets, and it sends a 359 Register-Stop message back to S's DR to prevent the DR unnecessarily 360 encapsulating the packets. 362 At the end of phase 2, traffic will be flowing natively from S along a 363 source-specific tree to the RP, and from there along the shared tree to 364 the receivers. Where the two trees intersect, traffic may transfer from 365 the source-specific tree to the RP tree, and so avoid taking a long 366 detour via the RP. 368 It should be noted that a sender may start sending before or after a 369 receiver joins the group, and thus phase two may happen before the 370 shared tree to the receiver is built. 372 Phase 3: Shortest-Path Tree 374 Although having the RP join back towards the source removes the 375 encapsulation overhead, it does not completely optimize the forwarding 376 paths. For many receivers the route via the RP may involve a 377 significant detour when compared with the shortest path from the source 378 to the receiver. 380 To obtain lower latencies, a router on the receiver's LAN, typically the 381 DR, may optionally initiate a transfer from the shared tree to a source- 382 specific shortest-path tree (SPT). To do this, it issues an (S,G) Join 383 towards S. This instantiates state in the routers along the path to S. 384 Eventually this join either reaches S's subnet, or reaches a router that 385 already has (S,G) state. When this happens, data packets from S start 386 to flow following the (S,G) state until they reach the receiver. 388 At this point the receiver (or a router upstream of the receiver) will 389 be receiving two copies of the data - one from the SPT and one from the 390 RPT. When the first traffic starts to arrive from the SPT, the DR or 391 upstream router starts to drop the packets for G from S that arrive via 392 the RP tree. In addition, it sends an (S,G) Prune message towards the 393 RP. This is known as an (S,G,rpt) Prune. The Prune message travels 394 hop-by-hop, instantiating state along the path towards the RP indicating 395 that traffic from S for G should NOT be forwarded in this direction. 396 The prune is propagated until it reaches the RP or a router that still 397 needs the traffic from S for other receivers. 399 By now, the receiver will be receiving traffic from S along the 400 shortest-path tree between the receiver and S. In addition, the RP is 401 receiving the traffic from S, but this traffic is no longer reaching the 402 receiver along the RP tree. As far as the receiver is concerned, this 403 is the final distribution tree. 405 Source-specific Joins 407 IGMPv3 permits a receiver to join a group and specify that it only wants 408 to receive traffic for a group if that traffic comes from a particular 409 source. If a receiver does this, and no other receiver on the LAN 410 requires all the traffic for the group, then the DR may omit performing 411 a (*,G) join to set up the shared tree, and instead issue a source- 412 specific (S,G) join only. 414 The range of multicast addresses from 232.0.0.0 to 232.255.255.255 is 415 currently set aside for source-specific multicast in IPv4. For groups 416 in this range, receivers should only issue source-specific IGMPv3 joins. 417 If a PIM router receives a non-source-specific join for a group in this 418 range, it should ignore it, as described in Section 4.9. 420 Source-specific Prunes 422 IGMPv3 also permits a receiver to join a group and specify that it only 423 wants to receive traffic for a group if that traffic does not come from 424 a specific source or sources. In this case, the DR will perform a (*,G) 425 join as normal, but may combine this with an (S,G,rpt) prune for each of 426 the sources the receiver does not wish to receive. 428 Multi-access Transit LANs 430 The overview so far has concerned itself with point-to-point links. 431 However, using multi-access LANs such as Ethernet for transit is not 432 uncommon. This can cause complications for three reasons: 434 o Two or more routers on the LAN may issue (*,G) Joins to different 435 upstream routers on the LAN because they have inconsistent MRIB 436 entries regarding how to reach the RP. Both paths on the RP tree will 437 be set up, causing two copies of all the shared tree traffic to appear 438 on the LAN. 440 o Two or more routers on the LAN may issue (S,G) Joins to different 441 upstream routers on the LAN because they have inconsistent MRIB 442 entries regarding how to reach source S. Both paths on the source- 443 specific tree will be set up, causing two copies of all the traffic 444 from S to appear on the LAN. 446 o A router on the LAN may issue a (*,G) Join to one upstream router on 447 the LAN, and another router on the LAN may issue an (S,G) Join to a 448 different upstream router on the same LAN. Traffic from S may reach 449 the LAN over both the RPT and the SPT. If the receiver behind the 450 downstream (*,G) router doesn't issue an (S,G,rpt) prune, then this 451 condition would persist. 453 All of these problems are caused by there being more than one upstream 454 router with join state for the group or source-group pair. PIM does not 455 prevent such duplicate joins from occurring - instead when duplicate 456 data packets appear on the LAN from different routers, these routers 457 notice this, and then elect a single forwarder. This election is 458 performed using PIM Assert messages, which resolve the problem in favor 459 of the upstream router which has (S,G) state, or if neither or both 460 router has (S,G) state, then in favor of the router with the best metric 461 to the RP for RP trees, or the best metric to the source to source- 462 specific trees. 464 These Assert messages are also received by the downstream routers on the 465 LAN, and these cause subsequent Join messages to be sent to the upstream 466 router that won the Assert. 468 RP Discovery 470 PIM-SM routers need to know the address of the RP for each group for 471 which they have (*,G) state. This address is obtained either through a 472 bootstrap mechanism or through static configuration. 474 One dynamic way to do this is to use the Bootstrap Router (BSR) 475 mechanism [7]. One router in each PIM domain is elected the Bootstrap 476 Router through a simple election process. All the routers in the domain 477 that are configured to be candidates to be RPs periodically unicast 478 their candidacy to the BSR. From the candidates, the BSR picks an RP- 479 set, and periodically announces this set in a Bootstrap message. 480 Bootstrap messages are flooded hop-by-hop throughout the domain until 481 all routers in the domain know the RP-Set. 483 To map a group to an RP, a router hashes the group address into the RP- 484 set using an order-preserving hash function (one that minimizes changes 485 if the RP set changes). The resulting RP is the one that it uses as the 486 RP for that group. 488 4. Protocol Specification 490 The specification of PIM-SM is broken into several parts: 492 o Section 4.1 details the protocol state stored. 494 o Section 4.2 specifies the data packet forwarding rules. 496 o Section 4.3. specifies Designated Router (DR) election and the rules 497 for sending and processing Hello messages. 499 o Section 4.4 specifies the PIM Register generation and processing 500 rules. 502 o Section 4.5 specifies the PIM Join/Prune generation and processing 503 rules. 505 o Section 4.6 specifies the PIM Assert generation and processing rules. 507 o Section 4.8 specifies the RP discovery mechanisms. 509 o The subset of PIM required to support Source-Specific Multicast, PIM- 510 SSM, is described in Section 4.9. 512 o PIM packet formats are specified in Section 4.10. 514 o A summary of PIM-SM timers and their default values is given in 515 Section 4.11. 517 4.1. PIM Protocol State 519 This section specifies all the protocol state that a PIM implementation 520 should maintain in order to function correctly. We term this state the 521 Tree Information Base or TIB, as it holds the state of all the multicast 522 distribution trees at this router. In this specification we define PIM 523 mechanisms in terms of the TIB. However, only a very simple 524 implementation would actually implement packet forwarding operations in 525 terms of this state. Most implementations will use this state to build 526 a multicast forwarding table, which would then be updated when the 527 relevant state in the TIB changes. 529 Although we specify precisely the state to be kept, this does not mean 530 that an implementation of PIM-SM needs to hold the state in this form. 532 This is actually an abstract state definition, which is needed in order 533 to specify the router's behavior. A PIM-SM implementation is free to 534 hold whatever internal state it requires, and will still be conformant 535 with this specification so long as it results in the same externally 536 visible protocol behavior as an abstract router that holds the following 537 state. 539 We divide TIB state into four sections: 541 (*,*,RP) state 542 State that maintains per-RP trees, for all groups served by a given 543 RP. 545 (*,G) state 546 State that maintains the RP tree for G. 548 (S,G) state 549 State that maintains a source-specific tree for source S and group 550 G. 552 (S,G,rpt) state 553 State that maintains source-specific information about source S on 554 the RP tree for G. For example, if a source is being received on 555 the source-specific tree, it will normally have been pruned off the 556 RP tree. This prune state is (S,G,rpt) state. 558 The state that should be kept is described below. Of course, 559 implementations will only maintain state when it is relevant to 560 forwarding operations - for example, the "NoInfo" state might be assumed 561 from the lack of other state information, rather than being held 562 explicitly. 564 4.1.1. General Purpose State 566 A router holds the following non-group-specific state: 568 For each interface: 570 o Override Interval 572 o Propagation Delay 574 o Suppression state: One of {"Enable", "Disable"} 576 Neighbor State: 578 For each neighbor: 580 o Information from neighbor's Hello 582 o Neighbor's Gen ID. 584 o Neighbor Liveness Timer (NLT) 586 Designated Router (DR) State: 588 o Designated Router's IP Address 590 o DR's DR Priority 592 The Override Interval, the Propagation Delay and the Interface 593 suppression state are described in Section 4.3.3. Designated Router 594 state is described in Section 4.3. 596 4.1.2. (*,*,RP) State 598 For every RP a router keeps the following state: 600 (*,*,RP) state: 601 For each interface: 603 PIM (*,*,RP) Join/Prune State: 605 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 606 Pending" (PP)} 608 o Prune-Pending Timer (PPT) 610 o Join/Prune Expiry Timer (ET) 612 Not interface specific: 614 o Upstream Join/Prune Timer (JT) 616 o Last RPF Neighbor towards RP that was used 618 PIM (*,*,RP) Join/Prune state is the result of receiving PIM (*,*,RP) 619 Join/Prune messages on this interface, and is specified in Section 620 4.5.1. 622 The upstream (*,*,RP) Join/Prune Timer is used to send out periodic 623 Join(*,*,RP) messages, and to override Prune(*,*,RP) messages from peers 624 on an upstream LAN interface. 626 The last RPF neighbor towards the RP is stored because if the MRIB 627 changes then the RPF neighbor towards the RP may change. If it does so, 628 then we need to trigger a new Join(*,*,RP) to the new upstream neighbor 629 and a Prune(*,*,RP) to the old upstream neighbor. Similarly, if a 630 router detects through a changed GenID in a Hello message that the 631 upstream neighbor towards the RP has rebooted, then it should re- 632 instantiate state by sending a Join(*,*,RP). These mechanisms are 633 specified in Section 4.5.5. 635 4.1.3. (*,G) State 637 For every group G a router keeps the following state: 639 (*,G) state: 640 For each interface: 642 Local Membership: 643 State: One of {"NoInfo", "Include"} 645 PIM (*,G) Join/Prune State: 647 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 648 Pending" (PP)} 650 o Prune-Pending Timer (PPT) 652 o Join/Prune Expiry Timer (ET) 654 (*,G) Assert Winner State 656 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 657 "I won Assert" (W)} 659 o Assert Timer (AT) 661 o Assert winner's IP Address 663 o Assert winner's Assert Metric 665 Not interface specific: 667 o Upstream Join/Prune Timer (JT) 669 o Last RP Used 671 o Last RPF Neighbor towards RP that was used 673 Local membership is the result of the local membership mechanism (such 674 as IGMP or MLD) running on that interface. It need not be kept if this 675 router is not the DR on that interface unless this router won a (*,G) 676 assert on this interface for this group, although implementations may 677 optionally keep this state in case they become the DR or assert winner. 678 We recommend storing this information if possible, as it reduces latency 679 converging to stable operating conditions after a failure causing a 680 change of DR. This information is used by the pim_include(*,G) macro 681 described in Section 4.1.6. 683 PIM (*,G) Join/Prune state is the result of receiving PIM (*,G) 684 Join/Prune messages on this interface, and is specified in Section 685 4.5.2. The state is used by the macros that calculate the outgoing 686 interface list in Section 4.1.6, and in the JoinDesired(*,G) macro 687 (defined in Section 4.5.6) that is used in deciding whether a Join(*,G) 688 should be sent upstream. 690 (*,G) Assert Winner state is the result of sending or receiving (*,G) 691 Assert messages on this interface. It is specified in Section 4.6.2. 693 The upstream (*,G) Join/Prune Timer is used to send out periodic 694 Join(*,G) messages, and to override Prune(*,G) messages from peers on an 695 upstream LAN interface. 697 The last RP used must be stored because if the RP Set changes (Section 698 4.8) then state must be torn down and rebuilt for groups whose RP 699 changes. 701 The last RPF neighbor towards the RP is stored because if the MRIB 702 changes then the RPF neighbor towards the RP may change. If it does so, 703 then we need to trigger a new Join(*,G) to the new upstream neighbor and 704 a Prune(*,G) to the old upstream neighbor. Similarly, if a router 705 detects through a changed GenID in a Hello message that the upstream 706 neighbor towards the RP has rebooted, then it should re-instantiate 707 state by sending a Join(*,G). These mechanisms are specified in Section 708 4.5.6. 710 4.1.4. (S,G) State 712 For every source/group pair (S,G) a router keeps the following state: 714 (S,G) state: 716 For each interface: 718 Local Membership: 719 State: One of {"NoInfo", "Include"} 721 PIM (S,G) Join/Prune State: 723 o State: One of {"NoInfo" (NI), "Join" (J), "Prune- 724 Pending" (PP)} 726 o Prune-Pending Timer (PPT) 728 o Join/Prune Expiry Timer (ET) 730 (S,G) Assert Winner State 732 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 733 "I won Assert" (W)} 735 o Assert Timer (AT) 737 o Assert winner's IP Address 739 o Assert winner's Assert Metric 741 Not interface specific: 743 o Upstream (S,G) Join/Prune Timer (JT) 745 o Last RPF Neighbor towards S that was used 747 o SPT bit (indicates (S,G) state is active) 749 o (S,G) Keepalive Timer (KAT) 751 Local membership is the result of the local source-specific membership 752 mechanism (such as IGMP version 3) running on that interface and 753 specifying that this particular source should be included. As stored 754 here, this state is the resulting state after any IGMPv3 inconsistencies 755 have been resolved. It need not be kept if this router is not the DR on 756 that interface unless this router won a (S,G) assert on this interface 757 for this group. However, we recommend storing this information if 758 possible, as it reduces latency converging to stable operating 759 conditions after a failure causing a change of DR. This information is 760 used by the pim_include(S,G) macro described in Section 4.1.6. 762 PIM (S,G) Join/Prune state is the result of receiving PIM (S,G) 763 Join/Prune messages on this interface, and is specified in Section 764 4.5.2. The state is used by the macros that calculate the outgoing 765 interface list in Section 4.1.6, and in the JoinDesired(S,G) macro 766 (defined in Section 4.5.7) that is used in deciding whether a Join(S,G) 767 should be sent upstream. 769 (S,G) Assert Winner state is the result of sending or receiving (S,G) 770 Assert messages on this interface. It is specified in Section 4.6.1. 772 The upstream (S,G) Join/Prune Timer is used to send out periodic 773 Join(S,G) messages, and to override Prune(S,G) messages from peers on an 774 upstream LAN interface. 776 The last RPF neighbor towards S is stored because if the MRIB changes 777 then the RPF neighbor towards S may change. If it does so, then we need 778 to trigger a new Join(S,G) to the new upstream neighbor and a Prune(S,G) 779 to the old upstream neighbor. Similarly, if the router detects through 780 a changed GenID in a Hello message that the upstream neighbor towards S 781 has rebooted, then it should re-instantiate state by sending a 782 Join(S,G). These mechanisms are specified in Section 4.5.7. 784 The SPTbit is used to indicate whether forwarding is taking place on the 785 (S,G) Shortest Path Tree (SPT) or on the (*,G) tree. A router can have 786 (S,G) state and still be forwarding on (*,G) state during the interval 787 when the source-specific tree is being constructed. When SPTbit is 788 FALSE, only (*,G) forwarding state is used to forward packets from S to 789 G. When SPTbit is TRUE, both (*,G) and (S,G) forwarding state are used. 791 The (S,G) Keepalive Timer is updated by data being forwarded using this 792 (S,G) forwarding state. It is used to keep (S,G) state alive in the 793 absence of explicit (S,G) Joins. Amongst other things, this is 794 necessary for the so-called "turnaround rules" - when the RP uses (S,G) 795 joins to stop encapsulation, and then (S,G) prunes to prevent traffic 796 from unnecessarily reaching the RP. 798 4.1.5. (S,G,rpt) State 800 For every source/group pair (S,G) for which a router also has (*,G) 801 state, it also keeps the following state: 803 (S,G,rpt) state: 805 For each interface: 807 Local Membership: 808 State: One of {"NoInfo", "Exclude"} 810 PIM (S,G,rpt) Join/Prune State: 812 o State: One of {"NoInfo", "Pruned", "Prune- 813 Pending"} 815 o Prune-Pending Timer (PPT) 817 o Join/Prune Expiry Timer (ET) 819 Not interface specific: 821 Upstream (S,G,rpt) Join/Prune State: 823 o State: One of {"NotJoined(*,G)", 824 "NotPruned(S,G,rpt)", "Pruned(S,G,rpt)"} 826 o Override Timer (OT) 828 Local membership is the result of the local source-specific membership 829 mechanism (such as IGMPv3) running on that interface and specifying that 830 although there is (*,G) Include state, this particular source should be 831 excluded. As stored here, this state is the resulting state after any 832 IGMPv3 inconsistencies between LAN members have been resolved. It need 833 not be kept if this router is not the DR on that interface unless this 834 router won a (*,G) assert on this interface for this group. However, we 835 recommend storing this information if possible, as it reduces latency 836 converging to stable operating conditions after a failure causing a 837 change of DR. This information is used by the pim_exclude(S,G) macro 838 described in Section 4.1.6. 840 PIM (S,G,rpt) Join/Prune state is the result of receiving PIM (S,G,rpt) 841 Join/Prune messages on this interface, and is specified in Section 842 4.5.4. The state is used by the macros that calculate the outgoing 843 interface list in Section 4.1.6, and in the rules for adding 844 Prune(S,G,rpt) messages to Join(*,G) messages specified in Section 845 4.5.8. 847 The upstream (S,G,rpt) Join/Prune state is used along with the Override 848 Timer to send the correct override messages in response to Join/Prune 849 messages sent by upstream peers on a LAN. This state and behavior are 850 specified in Section 4.5.9. 852 4.1.6. State Summarization Macros 854 Using this state, we define the following "macro" definitions which we 855 will use in the descriptions of the state machines and pseudocode in the 856 following sections. 858 The most important macros are those that define the outgoing interface 859 list (or "olist") for the relevant state. An olist can be "immediate" 860 if it is built directly from the state of the relevant type. For 861 example, the immediate_olist(S,G) is the olist that would be built if 862 the router only had (S,G) state and no (*,G) or (S,G,rpt) state. In 863 contrast, the "inherited" olist inherits state from other types. For 864 example, the inherited_olist(S,G) is the olist that is relevant for 865 forwarding a packet from S to G using both source-specific and group- 866 specific state. 868 There is no immediate_olist(S,G,rpt) as (S,G,rpt) state is negative 869 state - it removes interfaces in the (*,G) olist from the olist that is 870 actually used to forward traffic. The inherited_olist(S,G,rpt) is 871 therefore the olist that would be used for a packet from S to G 872 forwarding on the RP tree. It is a strict subset of 873 immediate_olist(*,G). 875 Generally speaking, the inherited olists are used for forwarding, and 876 the immediate_olists are used to make decisions about state maintenance. 878 immediate_olist(*,*,RP) = 879 joins(*,*,RP) 881 immediate_olist(*,G) = 882 joins(*,G) (+) pim_include(*,G) (-) lost_assert(*,G) 884 immediate_olist(S,G) = 885 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) 887 inherited_olist(S,G,rpt) = 888 ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 889 (+) ( pim_include(*,G) (-) pim_exclude(S,G)) 890 (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) ) 892 inherited_olist(S,G) = 893 inherited_olist(S,G,rpt) (+) immediate_olist(S,G) 895 The macros pim_include(*,G) and pim_include(S,G) indicate the interfaces 896 to which traffic might be forwarded because of hosts that are local 897 members on that interface. Note that normally only the DR cares about 898 local membership, but when an assert happens, the assert winner takes 899 over responsibility for forwarding traffic to local members that have 900 requested traffic on a group or source/group pair. 902 pim_include(*,G) = 903 { all interfaces I such that: 904 ( ( I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) 905 OR AssertWinner(*,G,I) == me ) 906 AND local_receiver_include(*,G,I) } 908 pim_include(S,G) = 909 { all interfaces I such that: 910 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) 911 OR AssertWinner(S,G,I) == me ) 912 AND local_receiver_include(S,G,I) } 914 pim_exclude(S,G) = 915 { all interfaces I such that: 916 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) 917 OR AssertWinner(S,G,I) == me ) 918 AND local_receiver_exclude(S,G,I) } 920 The clause "local_receiver_include(S,G,I)" is true if the IGMP/MLD 921 module or other local membership mechanism has determined that there are 922 local members on interface I that desire to receive traffic sent 923 specifically by S to G. "local_receiver_include(*,G,I)" is true if the 924 IGMP/MLD module or other local membership mechanism has determined that 925 there are local members on interface I that desire to receive all 926 traffic sent to G. "local_receiver_exclude(S,G,I) is true if 927 "local_receiver_include(*,G,I)" is true but none of the local members 928 desire to receive traffic from S. 930 The set "joins(*,*,RP)" is the set of all interfaces on which the router 931 has received (*,*,RP) Joins: 933 joins(*,*,RP) = 934 { all interfaces I such that 935 DownstreamJPState(*,*,RP,I) is either Join or 936 Prune-Pending } 938 DownstreamJPState(*,*,RP,I) is the state of the finite state machine in 939 Section 4.5.1. 941 The set "joins(*,G)" is the set of all interfaces on which the router 942 has received (*,G) Joins: 944 joins(*,G) = 945 { all interfaces I such that 946 DownstreamJPState(*,G,I) is either Join or Prune-Pending } 948 DownstreamJPState(*,G,I) is the state of the finite state machine in 949 Section 4.5.2. 951 The set "joins(S,G)" is the set of all interfaces on which the router 952 has received (S,G) Joins: 954 joins(S,G) = 955 { all interfaces I such that 956 DownstreamJPState(S,G,I) is either Join or Prune-Pending } 958 DownstreamJPState(S,G,I) is the state of the finite state machine in 959 Section 4.5.3. 961 The set "prunes(S,G,rpt)" is the set of all interfaces on which the 962 router has received (*,G) joins and (S,G,rpt) prunes. 964 prunes(S,G,rpt) = 965 { all interfaces I such that 966 DownstreamJPState(S,G,rpt,I) is Prune or PruneTmp } 968 DownstreamJPState(S,G,rpt,I) is the state of the finite state machine in 969 Section 4.5.4. 971 The set "lost_assert(*,G)" is the set of all interfaces on which the 972 router has received (*,G) joins but has lost a (*,G) assert. The macro 973 lost_assert(*,G,I) is defined in Section 4.6.5. 975 lost_assert(*,G) = 976 { all interfaces I such that 977 lost_assert(*,G,I) == TRUE } 979 The set "lost_assert(S,G,rpt)" is the set of all interfaces on which the 980 router has received (*,G) joins but has lost an (S,G) assert. The macro 981 lost_assert(S,G,rpt,I) is defined in Section 4.6.5. 983 lost_assert(S,G,rpt) = 984 { all interfaces I such that 985 lost_assert(S,G,rpt,I) == TRUE } 987 The set "lost_assert(S,G)" is the set of all interfaces on which the 988 router has received (S,G) joins but has lost an (S,G) assert. The macro 989 lost_assert(S,G,I) is defined in Section 4.6.5. 991 lost_assert(S,G) = 992 { all interfaces I such that 993 lost_assert(S,G,I) == TRUE } 995 The following pseudocode macro definitions are also used in many places 996 in the specification. Basically RPF' is the RPF neighbor towards an RP 997 or source unless a PIM-Assert has overridden the normal choice of 998 neighbor. 1000 neighbor RPF'(*,G) { 1001 if ( I_Am_Assert_Loser(*, G, RPF_interface(RP(G))) ) { 1002 return AssertWinner(*, G, RPF_interface(RP(G)) ) 1003 } else { 1004 return NBR( RPF_interface(RP(G)), MRIB.next_hop( RP(G) ) ) 1005 } 1006 } 1008 neighbor RPF'(S,G,rpt) { 1009 if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) { 1010 return AssertWinner(S, G, RPF_interface(RP(G)) ) 1011 } else { 1012 return RPF'(*,G) 1013 } 1014 } 1016 neighbor RPF'(S,G) { 1017 if ( I_Am_Assert_Loser(S, G, RPF_interface(S) )) { 1018 return AssertWinner(S, G, RPF_interface(S) ) 1019 } else { 1020 return NBR( RPF_interface(S), MRIB.next_hop( S ) ) ) 1021 } 1022 } 1024 RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data packets 1025 should be coming and to which joins should be sent on the RP tree and 1026 SPT respectively. 1028 RPF'(S,G,rpt) is basically RPF'(*,G) modified by the result of an 1029 Assert(S,G) on RPF_interface(RP(G)). In such a case, packets from S 1030 will be originating from a different router than RPF'(*,G). If we only 1031 have active (*,G) Join state, we need to accept packets from 1032 RPF'(S,G,rpt), and add a Prune(S,G,rpt) to the periodic Join(*,G) 1033 messages that we send to RPF'(*,G) (See Section 4.5.8). 1035 The function MRIB.next_hop( S ) returns an address of the next-hop PIM 1036 neighbor toward the host S, as indicated by the current MRIB. If S is 1037 directly adjacent, then MRIB.next_hop( S ) returns NULL. At the RP for 1038 G, MRIB.next_hop( RP(G )) returns NULL. 1040 The function NBR( I, A ) uses information gathered through PIM Hello 1041 messages to map the IP address A of a directly connected PIM neighbor 1042 router on interface I to the primary IP address of the same router 1043 (section 4.3.4). The primary IP address of a neighbor is the link-local 1044 address that it uses as the source of its PIM Hello messages. Note that 1045 a neighbor's IP address may not be unique within the PIM neighbor 1046 database due to scope issues. The address must however be unique amongst 1047 the addresses of all the PIM neighbors on a specific interface. 1049 I_Am_Assert_Loser(S, G, I) is true if the Assert start machine (in 1050 Section 4.6.1) for (S,G) on Interface I is in "I am Assert Loser" state. 1052 I_Am_Assert_Loser(*, G, I) is true if the Assert start machine (in 1053 Section 4.6.2) for (*,G) on Interface I is in "I am Assert Loser" state. 1055 4.2. Data Packet Forwarding Rules 1057 The PIM-SM packet forwarding rules are defined below in pseudocode. 1059 iif is the incoming interface of the packet. 1060 S is the source address of the packet. 1061 G is the destination address of the packet (group address). 1062 RP is the address of the Rendezvous Point for this group. 1063 RPF_interface(S) is the interface the MRIB indicates would be used 1064 to route packets to S. 1065 RPF_interface(RP) is the interface the MRIB indicates would be used 1066 to route packets to RP, except at the RP when it is the 1067 decapsulation interface (the "virtual" interface on which register 1068 packets are received). 1070 First, we restart (or start) the Keepalive Timer if the source is on a 1071 directly connected subnet. 1073 Second, we check to see if the SPT bit should be set because we've now 1074 switched from the RP tree to the SPT. 1076 Next we check to see whether the packet should be accepted based on TIB 1077 state and the interface that the packet arrived on. 1079 If the packet should be forwarded using (S,G) state, we then build an 1080 outgoing interface list for the packet. If this list is not empty, then 1081 we restart the (S,G) state Keepalive Timer. 1083 If the packet should be forwarded using (*,*,RP) or (*,G) state, then we 1084 just build an outgoing interface list for the packet. We also check if 1085 we should initiate a switch to start receiving this source on a shortest 1086 path tree. 1088 Finally we remove the incoming interface from the outgoing interface 1089 list we've created, and if the resulting outgoing interface list is not 1090 empty, we forward the packet out of those interfaces. 1092 On receipt of data from S to G on interface iif: 1094 if( DirectlyConnected(S) == TRUE ) { 1095 set KeepaliveTimer(S,G) to Keepalive_Period 1096 # Note: a register state transition may happen as a result 1097 # of restarting KeepaliveTimer, and must be dealt with here. 1098 } 1100 Update_SPTbit(S,G,iif) 1101 oiflist = NULL 1103 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 1104 oiflist = inherited_olist(S,G) 1105 if( oiflist != NULL ) { 1106 restart KeepaliveTimer(S,G) 1107 } 1108 } else if( iif == RPF_interface(RP(G)) AND SPTbit(S,G) == FALSE) { 1109 oiflist = inherited_olist(S,G,rpt) 1110 CheckSwitchToSpt(S,G) 1111 } else { 1112 # Note: RPF check failed 1113 if ( SPTbit(S,G) == TRUE AND iif is in inherited_olist(S,G) ) { 1114 send Assert(S,G) on iif 1115 } else if ( SPTbit(S,G) == FALSE AND 1116 iif is in inherited_olist(S,G,rpt) { 1117 send Assert(*,G) on iif 1118 } 1119 } 1121 oiflist = oiflist (-) iif 1122 forward packet on all interfaces in oiflist 1124 This pseudocode employs several "macro" definitions: 1126 DirectlyConnected(S) is TRUE if the source S is on any subnet that is 1127 directly connected to this router (or for packets originating on this 1128 router). 1130 inherited_olist(S,G) and inherited_olist(S,G,rpt) are defined in Section 1131 4.1. 1133 Basically inherited_olist(S,G) is the outgoing interface list for 1134 packets forwarded on (S,G) state taking into account (*,*,RP) state, 1135 (*,G) state, asserts, etc. 1137 inherited_olist(S,G,rpt) is the outgoing interface for packets forwarded 1138 on (*,*,RP) or (*,G) state taking into account (S,G,rpt) prune state, 1139 and asserts, etc. 1141 Update_SPTbit(S,G,iif) is defined in Section 4.2.2. 1143 CheckSwitchToSpt(S,G) is defined in Section 4.2.1. 1145 UpstreamJPState(S,G) is the state of the finite state machine in Section 1146 4.5.7. 1148 Keepalive_Period is defined in Section 4.11. 1150 Data triggered PIM-Assert messages sent from the above forwarding code 1151 should be rate-limited in a implementation-dependent manner. 1153 4.2.1. Last hop switchover to the SPT 1155 In Sparse-Mode PIM, last-hop routers join the shared tree towards the 1156 RP. Once traffic from sources to joined groups arrives at a last-hop 1157 router it has the option of switching to receive the traffic on a 1158 shortest path tree (SPT). 1160 The decision for a router to switch to the SPT is controlled as follows: 1162 void 1163 CheckSwitchToSpt(S,G) { 1164 if ( ( pim_include(*,G) (-) pim_exclude(S,G) 1165 (+) pim_include(S,G) != NULL ) 1166 AND SwitchToSptDesired(S,G) ) { 1167 restart KeepaliveTimer(S,G); 1168 } 1169 } 1171 SwitchToSptDesired(S,G) is a policy function that is implementation 1172 defined. An "infinite threshold" policy can be implemented making 1173 SwitchToSptDesired(S,G) return false all the time. A "switch on first 1174 packet" policy can be implemented by making SwitchToSptDesired(S,G) 1175 return true once a single packet has been received for the source and 1176 group. 1178 4.2.2. Setting and Clearing the (S,G) SPT bit 1180 The (S,G) SPTbit is used to distinguish whether to forward on 1181 (*,*,RP)/(*,G) or on (S,G) state. When switching from the RP tree to 1182 the source tree, there is a transition period when data is arriving due 1183 to upstream (*,*,RP)/(*,G) state while upstream (S,G) state is being 1184 established during which time a router should continue to forward only 1185 on (*,*,RP)/(*,G) state. This prevents temporary black-holes that would 1186 be caused by sending a Prune(S,G,rpt) before the upstream (S,G) state 1187 has finished being established. 1189 Thus, when a packet arrives, the (S,G) SPTbit is updated as follows: 1191 void 1192 Update_SPTbit(S,G,iif) { 1193 if ( iif == RPF_interface(S) 1194 AND JoinDesired(S,G) == TRUE 1195 AND ( DirectlyConnected(S) == TRUE 1196 OR RPF_interface(S) != RPF_interface(RP(G)) 1197 OR inherited_olist(S,G,rpt) == NULL 1198 OR RPF'(S,G) == RPF'(*,G) ) ) { 1199 Set SPTbit(S,G) to TRUE 1200 } 1201 } 1203 Additionally a router sets SPTbit(S,G) to TRUE when it receives an 1204 Assert(S,G) on RPF_interface(S) (see Section 4.6.1). 1206 JoinDesired(S,G) is defined in Section 4.5.7, and indicates whether we 1207 have the appropriate (S,G) Join state to wish to send a Join(S,G) 1208 upstream. 1210 Basically Update_SPTbit will set the SPT bit if we have the appropriate 1211 (S,G) join state and the packet arrived on the correct upstream 1212 interface for S, and one or more of the following conditions applies: 1214 1. The source is directly connected, in which case the switch to the 1215 SPT is a no-op. 1217 2. The RPF interface to S is different from the RPF interface to the 1218 RP. The packet arrived on RPF_interface(S), and so the SPT must 1219 have been completed. 1221 3. No-one wants the packet on the RP tree. 1223 4. RPF'(S,G) == RPF'(*,G). In this case the router will never be able 1224 to tell if the SPT has been completed, so it should just switch 1225 immediately. 1227 In the case where the RPF interface is the same for the RP and for S, 1228 but RPF'(S,G) and RPF'(*,G) differ, then we wait for an Assert(S,G) 1229 which indicates that the upstream router with (S,G) state believes the 1230 SPT has been completed. However item (3) above is needed because there 1231 may not be any (*,G) state to trigger an Assert(S,G) to happen. 1233 The SPT bit is cleared in the (S,G) upstream state machine (see Section 1234 4.5.7) when JoinDesired(S,G) becomes FALSE. 1236 4.3. Designated Routers (DR) and Hello Messages 1238 A shared-media LAN like Ethernet may have multiple PIM-SM routers 1239 connected to it. If the LAN has directly connected hosts, then a single 1240 one of these routers, the DR, will act on behalf of those hosts with 1241 respect to the PIM-SM protocol. Because the distinction between LANs 1242 and point-to-point interfaces can sometimes be blurred, and because 1243 routers may also have multicast host functionality, the PIM-SM 1244 specification makes no distinction between the two. Thus DR election 1245 will happen on all interfaces, LAN or otherwise. 1247 DR election is performed using Hello messages. Hello messages are also 1248 the way that option negotiation takes place in PIM, so that additional 1249 functionality can be enabled, or parameters tuned. 1251 4.3.1. Sending Hello Messages 1253 PIM-Hello messages are sent periodically on each PIM-enabled interface. 1254 They allow a router to learn about the neighboring PIM routers on each 1255 interface. Hello messages are also the mechanism used to elect a 1256 Designated Router (DR), and to negotiate additional capabilities. A 1257 router must record the Hello information received from each PIM 1258 neighbor. 1260 Hello messages MUST be sent on all active interfaces, including physical 1261 point-to-point links, and are multicast to the `ALL-PIM-ROUTERS' group 1262 address (`224.0.0.13' for IPv4 and `ff02::d' for IPv6). 1264 We note that some implementations do not send Hello messages 1265 on point-to-point interfaces. This is non-compliant behavior. 1266 A compliant PIM router MUST send Hello messages, even on 1267 point-to-point interfaces. 1269 A per interface Hello Timer (HT(I)) is used to trigger sending Hello 1270 messages on each active interface. When PIM is enabled on an interface 1271 or a router first starts, the Hello Timer of that interface is set to a 1272 random value between 0 and Triggered_Hello_Delay. This prevents 1273 synchronization of Hello messages if multiple routers are powered on 1274 simultaneously. After the initial randomized interval, Hello messages 1275 must be sent every Hello_Period seconds. The Hello Timer should not be 1276 reset except when it expires. 1278 Note that neighbors will not accept Join/Prune or Assert messages from a 1279 router unless they have first heard a Hello message from that router. 1280 Thus if a router needs to send a Join/Prune or Assert message on an 1281 interface on which it has not yet sent a Hello message, then it MUST 1282 immediately send the relevant Hello message without waiting for the 1283 Hello Timer to expire, followed by the Join/Prune or Assert message. 1285 The DR_Election_Priority Option allows a network administrator to give 1286 preference to a particular router in the DR election process by giving 1287 it a numerically larger DR Election Priority. The DR_Election_Priority 1288 Option SHOULD be included in every Hello message, even if no DR election 1289 priority is explicitly configured on that interface. This is necessary 1290 because priority-based DR election is only enabled when all neighbors on 1291 an interface advertise that they are capable of using the DR Election 1292 Priority Option. The default priority is 1. 1294 The Generation_Identifier (GenID) Option SHOULD be included in all Hello 1295 messages. The GenID option contains a randomly generated 32-bit value 1296 that is regenerated each time PIM forwarding is started or restarted on 1297 the interface, including when the router itself restarts. When a Hello 1298 message with a new GenID is received from a neighbor, any old Hello 1299 information about that neighbor SHOULD be discarded and superseded by 1300 the information from the new Hello message. This may cause a new DR to 1301 be chosen on that interface. 1303 The LAN_Prune_Delay Option SHOULD be included in all Hello messages sent 1304 on multi-access LANs. This option advertises a router's capability to 1305 use values other than the default for the Propagation_Delay and 1306 Override_Interval which affect the setting of the Prune-Pending, 1307 Upstream Join and Override Timers (defined in Section 4.11). 1309 The Interface_Address_List Option SHOULD be included in all IPv4 Hello 1310 messages and MUST be included in all IPv6 Hello messages. This option 1311 advertises all the secondary addresses associated with the source 1312 interface of the router originating the message. 1314 To allow new or rebooting routers to learn of PIM neighbors quickly, 1315 when a Hello message is received from a new neighbor, or a Hello message 1316 with a new GenID is received from an existing neighbor, a new Hello 1317 message should be sent on this interface after a randomized delay 1318 between 0 and Triggered_Hello_Delay. This triggered message need not 1319 change the timing of the scheduled periodic message. If a router needs 1320 to send a Join/Prune to the new neighbor or send an Assert message in 1321 response to an Assert message from the new neighbor before this 1322 randomized delay has expired, then it MUST immediately send the relevant 1323 Hello message without waiting for the Hello Timer to expire, followed by 1324 the Join/Prune or Assert message. If it does not do this, then the new 1325 neighbor will discard the Join/Prune or Assert message. 1327 Before an interface goes down or changes IP address, a Hello message 1328 with a zero HoldTime should be sent immediately (with the old IP address 1329 if the IP address changed). This will cause PIM neighbors to remove 1330 this neighbor (or its old IP address) immediately. After an interface 1331 has changed its IP address, it MUST send a Hello message with its new IP 1332 address. 1334 4.3.2. DR Election 1336 When a PIM-Hello message is received on interface I the following 1337 information about the sending neighbor is recorded: 1339 neighbor.interface 1340 The interface on which the Hello message arrived. 1342 neighbor.primary_ip_address 1343 The IP address that the PIM neighbor used as the source 1344 address of the Hello message. 1346 neighbor.genid 1347 The Generation ID of the PIM neighbor. 1349 neighbor.dr_priority 1350 The DR Priority field of the PIM neighbor if it is present in 1351 the Hello message. 1353 neighbor.dr_priority_present 1354 A flag indicating if the DR Priority field was present in the 1355 Hello message. 1357 neighbor.timeout 1358 A timer value to time out the neighbor state when it becomes 1359 stale. 1360 The Neighbor Liveness Timer (NLT(N,I)) is reset to 1361 Hello_Holdtime (from the Hello Holdtime option) whenever a 1362 Hello message is received containing a Holdtime option, or to 1363 Default_Hello_Holdtime if the Hello message does not contain 1364 the Holdtime option. 1366 Neighbor state is deleted when the neighbor timeout expires. 1368 The function for computing the DR on interface I is: 1370 host 1371 DR(I) { 1372 dr = me 1373 for each neighbor on interface I { 1374 if ( dr_is_better( neighbor, dr, I ) == TRUE ) { 1375 dr = neighbor 1376 } 1377 } 1378 return dr 1379 } 1381 The function used for comparing DR "metrics" on interface I is: 1383 bool 1384 dr_is_better(a,b,I) { 1385 if( there is a neighbor n on I for which n.dr_priority_present 1386 is false ) { 1387 return a.primary_ip_address > b.primary_ip_address 1388 } else { 1389 return ( a.dr_priority > b.dr_priority ) OR 1390 ( a.dr_priority == b.dr_priority AND 1391 a.primary_ip_address > b.primary_ip_address ) 1392 } 1393 } 1395 The trivial function I_am_DR(I) is defined to aid readability: 1397 bool 1398 I_am_DR(I) { 1399 return DR(I) == me 1400 } 1402 The DR election priority is a 32-bit unsigned number and the numerically 1403 larger priority is always preferred. A router's idea of the current DR 1404 on an interface can change when a PIM-Hello message is received, when a 1405 neighbor times out, or when a router's own DR priority changes. If the 1406 router becomes the DR or ceases to be the DR, this will normally cause 1407 the DR Register state-machine to change state. Subsequent actions are 1408 determined by that state-machine. 1410 We note that some PIM implementations do not send Hello 1411 messages on point-to-point interfaces, and so cannot perform 1412 DR election on such interfaces. This in non-compliant 1413 behavior. DR election MUST be performed on ALL active PIM-SM 1414 interfaces. 1416 4.3.3. Reducing Prune Propagation Delay on LANs 1418 In addition to the information recorded for the DR Election, the 1419 following per neighbor information is obtained from the LAN Prune Delay 1420 Hello option: 1422 neighbor.lan_prune_delay_present 1423 A flag indicating if the LAN Prune Delay option was present in 1424 the Hello message. 1426 neighbor.tracking_support 1427 A flag storing the value of the T bit in the LAN Prune Delay 1428 option if it is present in the Hello message. This indicates 1429 the neighbor's capability to disable Join message suppression. 1431 neighbor.lan_delay 1432 The LAN Delay field of the LAN Prune Delay option (if present) 1433 in the Hello message. 1435 neighbor.override_interval 1436 The Override_Interval field of the LAN Prune Delay option (if 1437 present) in the Hello message. 1439 The additional state described above is deleted along with the DR 1440 neighbor state when the neighbor timeout expires. 1442 Just like the DR priority option, the information provided in the LAN 1443 Prune Delay option is not used unless all neighbors on a link advertise 1444 the option. The function below computes this state: 1446 bool 1447 lan_delay_enabled(I) { 1448 for each neighbor on interface I { 1449 if ( neighbor.lan_prune_delay_present == false ) { 1450 return false 1451 } 1452 } 1453 return true 1454 } 1456 The LAN Delay inserted by a router in the LAN Prune Delay option 1457 expresses the expected message propagation delay on the link and should 1458 be configurable by the system administrator. It is used by upstream 1459 routers to figure out how long they should wait for a Join override 1460 message before pruning an interface. 1462 PIM implementors should enforce a lower bound on the permitted values 1463 for this delay to allow for scheduling and processing delays within 1464 their router. Such delays may cause received messages to be processed 1465 later as well as triggered messages to be sent later than intended. 1466 Setting this LAN Prune Delay to too low a value may result in temporary 1467 forwarding outages because a downstream router will not be able to 1468 override a neighbor's Prune message before the upstream neighbor stops 1469 forwarding. 1471 When all routers on a link are in a position to negotiate a different 1472 than default Propagation Delay, the largest value from those advertised 1473 by each neighbor is chosen. The function for computing the Propagation 1474 Delay of interface I is: 1476 time_interval 1477 Propagation_Delay(I) { 1478 if ( lan_delay_enabled(I) == false ) { 1479 return LAN_delay_default 1480 } 1481 delay = 0 1482 for each neighbor on interface I { 1483 if ( neighbor.lan_delay > delay ) { 1484 delay = neighbor.lan_delay 1485 } 1486 } 1487 return delay 1488 } 1490 To avoid synchronization of override messages when multiple downstream 1491 routers share a multi-access link, sending of such messages is delayed 1492 by a small random amount of time. The period of randomization should 1493 represent the size of the PIM router population on the link. Each 1494 router expresses its view of the amount of randomization necessary in 1495 the Override Delay field of the LAN Prune Delay option. 1497 When all routers on a link are in a position to negotiate a different 1498 than default Override Delay, the largest value from those advertised by 1499 each neighbor is chosen. The function for computing the Override 1500 Interval of interface I is: 1502 time_interval 1503 Override_Interval(I) { 1504 if ( lan_delay_enabled(I) == false ) { 1505 return t_override_default 1506 } 1507 delay = 0 1508 for each neighbor on interface I { 1509 if ( neighbor.override_interval > delay ) { 1510 delay = neighbor.override_interval 1511 } 1512 } 1513 return delay 1514 } 1516 Although the mechanisms are not specified in this document, it is 1517 possible for upstream routers to explicitly track the join membership of 1518 individual downstream routers if Join suppression is disabled. A router 1519 can advertise its willingness to disable Join suppression by using the T 1520 bit in the LAN Prune Delay Hello option. Unless all PIM routers on a 1521 link negotiate this capability, explicit tracking and the disabling of 1522 the Join suppression mechanism are not possible. The function for 1523 computing the state of Suppression on interface I is: 1525 bool 1526 Suppression_Enabled(I) { 1527 if ( lan_delay_enabled(I) == false ) { 1528 return true 1529 } 1530 for each neighbor on interface I { 1531 if ( neighbor.tracking_support == false ) { 1532 return true 1533 } 1534 } 1535 return false 1536 } 1538 Note that the setting of Suppression_Enabled(I) affects the value of 1539 t_suppressed (see Section 4.11). 1541 4.3.4. Maintaining Secondary Address Lists 1543 Communication of a routers interface secondary addresses to its PIM 1544 neighbors is necessary to provide the neighbors with a mechanism for 1545 mapping next_hop information obtained through their MRIB to a primary 1546 address that can be used as a destination for Join/Prune messages. The 1547 mapping is performed through the NBR macro. The primary address of a 1548 PIM neighbor is obtained from the source IP address used in its PIM 1549 Hello messages. Secondary addresses are carried within the Hello message 1550 in an Address List Hello option. The primary address of the source 1551 interface of the router MUST NOT be listed within the Address List Hello 1552 option. 1554 In addition to the information recorded for the DR Election, the 1555 following per neighbor information is obtained from the Address List 1556 Hello option: 1558 neighbor.secondary_address_list 1559 The list of secondary addresses used by the PIM neighbor on 1560 the interface through which the Hello message was transmitted. 1562 When processing a received PIM Hello message containing an Address List 1563 Hello option, the list of secondary addresses in the message completely 1564 replaces any previously associated secondary addresses for that 1565 neighbor. If a received PIM Hello message does not contain an Address 1566 List Hello option then all secondary addresses associated with the 1567 neighbor must be deleted. 1569 All the advertised secondary addresses in received Hello messages must 1570 be checked against those previously advertised by all other PIM 1571 neighbors on that interface. If there is a conflict and the same 1572 secondary address was previously advertised by another neighbor then 1573 only the most recently received mapping MUST be maintained and an error 1574 message SHOULD be logged to the administrator in a rate limited manner. 1576 4.4. PIM Register Messages 1578 Overview 1580 The Designated Router (DR) on a LAN or point-to-point link encapsulates 1581 multicast packets from local sources to the RP for the relevant group 1582 unless it recently received a Register-Stop message for that (S,G) or 1583 (*,G) from the RP. When the DR receives a Register-Stop message from 1584 the RP, it starts a Register-Stop Timer to maintain this state. Just 1585 before the Register-Stop Timer expires, the DR sends a Null-Register 1586 Message to the RP to allow the RP to refresh the Register-Stop 1587 information at the DR. If the Register-Stop Timer actually expires, the 1588 DR will resume encapsulating packets from the source to the RP. 1590 4.4.1. Sending Register Messages from the DR 1592 Every PIM-SM router has the capability to be a DR. The state machine 1593 below is used to implement Register functionality. For the purposes of 1594 specification, we represent the mechanism to encapsulate packets to the 1595 RP as a Register-Tunnel interface, which is added to or removed from the 1596 (S,G) olist. The tunnel interface then takes part in the normal packet 1597 forwarding rules as specified in Section 4.2. 1599 If register state is maintained, it is maintained only for directly 1600 connected sources, and is per-(S,G). There are four states in the DR's 1601 per-(S,G) Register state-machine: 1603 Join (J) 1604 The register tunnel is "joined" (the join is actually implicit, but 1605 the DR acts as if the RP has joined the DR on the tunnel 1606 interface). 1608 Prune (P) 1609 The register tunnel is "pruned" (this occurs when a Register-Stop 1610 is received). 1612 Join-Pending (JP) 1613 The register tunnel is pruned but the DR is contemplating adding it 1614 back. 1616 NoInfo (NI) 1617 No information. This is the initial state, and the state when the 1618 router is not the DR. 1620 In addition, a Register-Stop Timer (RST) is kept if the state machine is 1621 not in the NoInfo state. 1623 Figure 1: Per-(S,G) register state-machine at a DR in tabular form 1625 +-----------++---------------------------------------------------------------+ 1626 | || Event | 1627 | ++-----------+------------+------------+------------+------------+ 1628 |Prev State ||Register- | Could- | Could- | Register- | RP changed | 1629 | ||Stop Timer | Register | Register | Stop | | 1630 | ||expires | ->True | ->False | received | | 1631 +-----------++-----------+------------+------------+------------+------------+ 1632 |NoInfo ||- | -> J state | - | - | - | 1633 |(NI) || | add reg | | | | 1634 | || | tunnel | | | | 1635 +-----------++-----------+------------+------------+------------+------------+ 1636 | ||- | - | -> NI | -> P state | -> J state | 1637 | || | | state | | | 1638 | || | | remove reg | remove reg | update reg | 1639 |Join (J) || | | tunnel | tunnel; | tunnel | 1640 | || | | | set | | 1641 | || | | | Register- | | 1642 | || | | | Stop | | 1643 | || | | | Timer(*) | | 1644 +-----------++-----------+------------+------------+------------+------------+ 1645 | ||-> J state | - | -> NI | -> P state | -> J state | 1646 | || | | state | | | 1647 |Join- ||add reg | | remove reg | set | add reg | 1648 |Pending ||tunnel | | tunnel | Register- | tunnel; | 1649 |(JP) || | | | Stop | cancel | 1650 | || | | | Timer(*) | Register- | 1651 | || | | | | Stop Timer | 1652 +-----------++-----------+------------+------------+------------+------------+ 1653 | ||-> JP | - | -> NI | - | -> J state | 1654 | ||state | | state | | | 1655 | ||set | | remove reg | | add reg | 1656 |Prune (P) ||Register- | | tunnel | | tunnel; | 1657 | ||Stop | | | | cancel | 1658 | ||Timer(**); | | | | Register- | 1659 | ||send Null- | | | | Stop Timer | 1660 | ||Register | | | | | 1661 +-----------++-----------+------------+------------+------------+------------+ 1663 Notes: 1665 (*) The Register-Stop Timer is set to a random value chosen uniformly 1666 from the interval ( 0.5 * Register_Suppression_Time, 1.5 * 1667 Register_Suppression_Time) minus Register_Probe_Time; 1669 Subtracting off Register_Probe_Time is a bit unnecessary because it 1670 is really small compared to Register_Suppression_Time, but was in 1671 the old spec and is kept for compatibility. 1673 (**) The Register-Stop Timer is set to Register_Probe_Time. 1675 The following actions are defined: 1677 Add Register Tunnel 1679 A Register-Tunnel virtual interface, VI, is created (if it doesn't 1680 already exist) with its encapsulation target being RP(G). 1681 DownstreamJPState(S,G,VI) is set to Join state, causing the tunnel 1682 interface to be added to immediate_olist(S,G). 1684 Remove Register Tunnel 1686 VI is the Register-Tunnel virtual interface with encapsulation target of 1687 RP(G). DownstreamJPState(S,G,VI) is set to NoInfo state, causing the 1688 tunnel interface to be removed from immediate_olist(S,G). If 1689 DownstreamJPState(S,G,VI) is NoInfo for all (S,G), then VI can be 1690 deleted. 1692 Update Register Tunnel 1694 This action occurs when RP(G) changes. 1696 VI_old is the Register-Tunnel virtual interface with encapsulation 1697 target old_RP(G). A Register-Tunnel virtual interface, VI_new, is 1698 created (if it doesn't already exist) with its encapsulation target 1699 being new_RP(G). DownstreamJPState(S,G,VI_old) is set to NoInfo state 1700 and DownstreamJPState(S,G,VI_new) is set to Join state. If 1701 DownstreamJPState(S,G,VI_old) is NoInfo for all (S,G), then VI_old can 1702 be deleted. 1704 Note that we can not simply change the encapsulation target of VI_old 1705 because not all groups using that encapsulation tunnel will have moved 1706 to the same new RP. 1708 CouldRegister(S,G) 1710 The macro "CouldRegister" in the state machine is defined as: 1712 Bool CouldRegister(S,G) { 1713 return ( I_am_DR( RPF_interface(S) ) AND 1714 KeepaliveTimer(S,G) is running AND 1715 DirectlyConnected(S) == TRUE ) 1716 } 1718 Note that on reception of a packet at the DR from a directly connected 1719 source, KeepaliveTimer(S,G) needs to be set by the packet forwarding 1720 rules before computing CouldRegister(S,G) in the register state machine, 1721 or the first packet from a source won't be registered. 1723 Encapsulating data packets in the Register Tunnel 1725 Conceptually, the Register Tunnel is an interface with a smaller MTU 1726 than the underlying IP interface towards the RP. IP fragmentation on 1727 packets forwarded on the Register Tunnel is performed based upon this 1728 smaller MTU. The encapsulating DR may perform Path-MTU Discovery to the 1729 RP to determine the effective MTU of the tunnel. This smaller MTU takes 1730 both the outer IP header and the PIM register header overhead into 1731 account. If a multicast packet is fragmented on the way into the 1732 Register Tunnel, each fragment is encapsulated individually so it 1733 contains IP, PIM, and inner IP headers. 1735 In IPv6, an ICMP Fragmentation Required message may be sent by the 1736 encapsulating DR. 1738 Just like any forwarded packet, the TTL of the original data packet is 1739 decremented before it is encapsulated in the Register Tunnel. 1741 The IP ECN bits should be copied from the original packet to the IP 1742 header of the encapsulating packet. They SHOULD NOT be set 1743 independently by the encapsulating router. 1745 The Diffserv Code Point (DSCP) should be copied from the original packet 1746 to the IP header of the encapsulating packet. It MAY be set 1747 independently by the encapsulating router, based upon static 1748 configuration or traffic classification. See [2] for more discussion on 1749 setting the DSCP on tunnels. 1751 Handling Register-Stop(*,G) Messages at the DR 1753 An old RP might send a Register-Stop message with the source address set 1754 to all-zeros. This was the normal course of action in RFC 2326 when the 1755 Register message matched against (*,G) state at the RP, and was defined 1756 as meaning "stop encapsulating all sources for this group". However, 1757 the behavior of such a Register-Stop(*,G) is ambiguous or incorrect in 1758 some circumstances. 1760 We specify that an RP should not send Register-Stop(*,G) messages, but 1761 for compatibility, a DR should be able to accept one if it is received. 1763 A Register-Stop(*,G) should be treated as a Register-Stop(S,G) for all 1764 existing (S,G) Register state machines. A router should not apply a 1765 Register-Stop(*,G) to sources that become active after the Register- 1766 Stop(*,G) was received. 1768 4.4.2. Receiving Register Messages at the RP 1770 When an RP receives a Register message, the course of action is decided 1771 according to the following pseudocode: 1773 packet_arrives_on_rp_tunnel( pkt ) { 1774 if( outer.dst is not one of my addresses ) { 1775 drop the packet silently. 1776 # note that this should not happen if the lower layer is working 1777 } 1778 if( I_am_RP( G ) && outer.dst == RP(G) ) { 1779 if ( SPTbit(S,G) || SwitchToSptDesired(S,G) ) { 1780 restart KeepaliveTimer(S,G) 1781 } 1782 if ( SPTbit(S,G) || 1783 ( SwitchToSptDesired(S,G) && ( inherited_olist(S,G) != NULL ))) { 1784 send Register-Stop(S,G) to outer.src 1785 } 1786 if( !SPTbit(S,G) && ! pkt.NullRegisterBit ) { 1787 decapsulate and pass the inner packet to the normal 1788 forwarding path for forwarding on the (*,G) tree. 1789 } 1790 } else { 1791 send Register-Stop(S,G) to outer.src 1792 # Note (*) 1793 } 1794 } 1796 outer.dst is the IP destination address of the encapsulating header. 1798 outer.src is the IP source address of the encapsulating header, i.e., 1799 the DR's address. 1801 I_am_RP(G) is true if the group-to-RP mapping indicates that this router 1802 is the RP for the group. 1804 Note (*): This may block traffic from S for Register_Suppression_Time if 1805 the DR learned about a new group-to-RP mapping before the RP did. 1806 However, this doesn't matter unless we figure out some way for the 1807 RP to also accept (*,G) joins when it doesn't yet realize that it 1808 is about to become the RP for G. This will all get sorted out once 1809 the RP learns the new group-to-rp mapping. We decided to do 1810 nothing about this and just accept the fact that PIM may suffer 1811 interrupted (*,G) connectivity following an RP change. 1813 KeepaliveTimer(S,G) is restarted at the RP when packets arrive on the 1814 proper tunnel interface and the RP desires to switch to the SPT or the 1815 SPTbit is already set. This may cause the upstream (S,G) state machine 1816 to trigger a join if the inherited_olist(S,G) is not NULL; 1818 An RP should preserve (S,G) state that was created in response to a 1819 Register message for at least ( 3 * Register_Suppression_Time ), 1820 otherwise the RP may stop joining (S,G) before the DR for S has 1821 restarted sending registers. Traffic would then be interrupted until 1822 the Register-Stop Timer expires at the DR. 1824 Thus, at the RP, KeepaliveTimer(S,G) should be restarted to ( 3 * 1825 Register_Suppression_Time + Register_Probe_Time ). 1827 Just like any forwarded packet, the TTL of the original data packet is 1828 decremented after it is decapsulated from the Register Tunnel. 1830 The IP ECN bits should be copied from the IP header of the Register 1831 packet to the decapsulated packet. 1833 The Diffserv Code Point (DSCP) should be copied from the IP header of 1834 the Register packet to the decapsulated packet. The RP MAY retain the 1835 DSCP of the inner packet, or re-classify the packet and apply a 1836 different DSCP. Scenarios where each of these might be useful are 1837 discussed in [2]. 1839 4.5. PIM Join/Prune Messages 1841 A PIM Join/Prune message consists of a list of groups and a list of 1842 Joined and Pruned sources for each group. When processing a received 1843 Join/Prune message, each Joined or Pruned source for a Group is 1844 effectively considered individually, and applies to one or more of the 1845 following state machines. When considering a Join/Prune message whose 1846 PIM Destination field addresses this router, (*,G) Joins and Prunes can 1847 affect both the (*,G) and (S,G,rpt) downstream state machines, while 1848 (*,*,RP), (S,G) and (S,G,rpt) Joins and Prunes can only affect their 1849 respective downstream state machines. When considering a Join/Prune 1850 message whose PIM Destination field addresses another router, most Join 1851 or Prune messages could affect each upstream state machine. 1853 In general, a PIM Join/Prune message should only be accepted for 1854 processing if it comes from a known PIM neighbor. A PIM router hears 1855 about PIM neighbors through PIM Hello messages. If a router receives a 1856 Join/Prune message from a particular IP source address and it has not 1857 seen a PIM Hello message from that source address, then the Join/Prune 1858 message SHOULD be discarded without further processing. In addition, if 1859 the Hello message from a neighbor was authenticated using IPsec AH (see 1860 Section 6.3) then all Join/Prune messages from that neighbor MUST also 1861 be authenticated using IPsec AH. 1863 We note that some older PIM implementations incorrectly fail to send 1864 Hello messages on point-to-point interfaces, so we also RECOMMEND that a 1865 configuration option be provided to allow interoperation with such older 1866 routers, but that this configuration option SHOULD NOT be enabled by 1867 default. 1869 4.5.1. Receiving (*,*,RP) Join/Prune Messages 1871 The per-interface state-machine for receiving (*,*,RP) Join/Prune 1872 Messages is given below. There are three states: 1874 NoInfo (NI) 1875 The interface has no (*,*,RP) Join state and no timers 1876 running. 1878 Join (J) 1879 The interface has (*,*,RP) Join state which will cause us to 1880 forward packets destined for any group handled by RP from this 1881 interface except if there is also (S,G,rpt) prune information 1882 (see Section 4.5.4) or the router lost an assert on this 1883 interface. 1885 Prune-Pending (PP) 1886 The router has received a Prune(*,*,RP) on this interface from 1887 a downstream neighbor and is waiting to see whether the prune 1888 will be overridden by another downstream router. For 1889 forwarding purposes, the Prune-Pending state functions exactly 1890 like the Join state. 1892 In addition, the state-machine uses two timers: 1894 ExpiryTimer (ET) 1895 This timer is restarted when a valid Join(*,*,RP) is received. 1896 Expiry of the ExpiryTimer causes the interface state to revert 1897 to NoInfo for this RP. 1899 Prune-Pending Timer (PPT) 1900 This timer is set when a valid Prune(*,*,RP) is received. 1901 Expiry of the Prune-Pending Timer causes the interface state 1902 to revert to NoInfo for this RP. 1904 Figure 2: Downstream per-interface (*,*,RP) state-machine in tabular form 1906 +-------------++----------------------------------------------------------+ 1907 | || Event | 1908 | ++-------------+--------------+--------------+--------------+ 1909 |Prev State ||Receive | Receive | Prune- | Expiry Timer | 1910 | ||Join(*,*,RP) | Prune | Pending | Expires | 1911 | || | (*,*,RP) | Timer | | 1912 | || | | Expires | | 1913 +-------------++-------------+--------------+--------------+--------------+ 1914 | ||-> J state | -> NI state | - | - | 1915 |NoInfo (NI) ||start Expiry | | | | 1916 | ||Timer | | | | 1917 +-------------++-------------+--------------+--------------+--------------+ 1918 | ||-> J state | -> PP state | - | -> NI state | 1919 |Join (J) ||restart | start Prune- | | | 1920 | ||Expiry Timer | Pending | | | 1921 | || | Timer | | | 1922 +-------------++-------------+--------------+--------------+--------------+ 1923 | ||-> J state | -> PP state | -> NI state | -> NI state | 1924 | ||restart | | Send Prune- | | 1925 | ||Expiry | | Echo(*,*,RP) | | 1926 |Prune- ||Timer; | | | | 1927 |Pending (PP) ||cancel | | | | 1928 | ||Prune- | | | | 1929 | ||Pending | | | | 1930 | ||Timer | | | | 1931 +-------------++-------------+--------------+--------------+--------------+ 1933 The transition events "Receive Join(*,*,RP)" and "Receive Prune(*,*,RP)" 1934 imply receiving a Join or Prune targeted to this router's address on the 1935 received interface. If the destination address is not correct, these 1936 state transitions in this state machine must not occur, although seeing 1937 such a packet may cause state transitions in other state machines. 1939 On unnumbered interfaces on point-to-point links, the router's address 1940 should be the same as the source address it chose for the Hello message 1941 it sent over that interface. However on point-to-point links we also 1942 recommend that PIM Join/Prune messages with a destination address of all 1943 zeros are also accepted. 1945 Transitions from NoInfo State 1947 When in NoInfo state, the following event may trigger a transition: 1949 Receive Join(*,*,RP) 1950 A Join(*,*,RP) is received on interface I with its Upstream 1951 Neighbor Address set to the router's address on I. 1953 The (*,*,RP) downstream state machine on interface I 1954 transitions to the Join state. The Expiry Timer (ET) is 1955 started, and set to the HoldTime from the triggering 1956 Join/Prune message. 1958 Note that it is possible to receive a Join(*,*,RP) message for 1959 an RP that we do not have information telling us that it is an 1960 RP. In the case of (*,*,RP) state, so long as we have a route 1961 to the RP, this will not cause a problem, and the transition 1962 should still take place. 1964 Transitions from Join State 1966 When in Join state, the following events may trigger a transition: 1968 Receive Join(*,*,RP) 1969 A Join(*,*,RP) is received on interface I with its Upstream 1970 Neighbor Address set to the router's address on I. 1972 The (*,*,RP) downstream state machine on interface I remains 1973 in Join state, and the Expiry Timer (ET) is restarted, set to 1974 maximum of its current value and the HoldTime from the 1975 triggering Join/Prune message. 1977 Receive Prune(*,*,RP) 1978 A Prune(*,*,RP) is received on interface I with its Upstream 1979 Neighbor Address set to the router's address on I. 1981 The (*,*,RP) downstream state machine on interface I 1982 transitions to the Prune-Pending state. The Prune-Pending 1983 Timer is started; it is set to the J/P_Override_Interval(I) if 1984 the router has more than one neighbor on that interface; 1985 otherwise it is set to zero causing it to expire immediately. 1987 Expiry Timer Expires 1988 The Expiry Timer for the (*,*,RP) downstream state machine on 1989 interface I expires. 1991 The (*,*,RP) downstream state machine on interface I 1992 transitions to the NoInfo state. 1994 Transitions from Prune-Pending State 1996 When in Prune-Pending state, the following events may trigger a 1997 transition: 1999 Receive Join(*,*,RP) 2000 A Join(*,*,RP) is received on interface I with its Upstream 2001 Neighbor Address set to the router's address on I. 2003 The (*,*,RP) downstream state machine on interface I 2004 transitions to the Join state. The Prune-Pending Timer is 2005 canceled (without triggering an expiry event). The Expiry 2006 Timer is restarted, set to maximum of its current value and 2007 the HoldTime from the triggering Join/Prune message. 2009 Expiry Timer Expires 2010 The Expiry Timer for the (*,*,RP) downstream state machine on 2011 interface I expires. 2013 The (*,*,RP) downstream state machine on interface I 2014 transitions to the NoInfo state. 2016 Prune-Pending Timer Expires 2017 The Prune-Pending Timer for the (*,*,RP) downstream state 2018 machine on interface I expires. 2020 The (*,*,RP) downstream state machine on interface I 2021 transitions to the NoInfo state. A PruneEcho(*,*,RP) is sent 2022 onto the subnet connected to interface I. 2024 The action "Send PruneEcho(*,*,RP)" is triggered when the 2025 router stops forwarding on an interface as a result of a 2026 prune. A PruneEcho(*,*,RP) is simply a Prune(*,*,RP) message 2027 sent by the upstream router on a LAN with its own address in 2028 the Upstream Neighbor Address field. Its purpose is to add 2029 additional reliability so that if a Prune that should have 2030 been overridden by another router is lost locally on the LAN, 2031 then the PruneEcho may be received and cause the override to 2032 happen. A PruneEcho(*,*,RP) need not be sent on an interface 2033 that contains only a single PIM neighbor during the time this 2034 state machine was in Prune-Pending state. 2036 4.5.2. Receiving (*,G) Join/Prune Messages 2038 When a router receives a Join(*,G) or Prune(*,G) it must first check to 2039 see whether the RP in the message matches RP(G) (the router's idea of 2040 who the RP is). If the RP in the message does not match RP(G) the 2041 Join(*,G) or Prune(*,G) should be silently dropped. If a router has no 2042 RP information (e.g. has not recently received a BSR message) then it 2043 may choose to accept Join(*,G) or Prune(*,G) and treat the RP in the 2044 message as RP(G). 2046 The per-interface state-machine for receiving (*,G) Join/Prune Messages 2047 is given below. There are three states: 2049 NoInfo (NI) 2050 The interface has no (*,G) Join state and no timers running. 2052 Join (J) 2053 The interface has (*,G) Join state which will cause us to 2054 forward packets destined for G from this interface except if 2055 there is also (S,G,rpt) prune information (see Section 4.5.4) 2056 or the router lost an assert on this interface. 2058 Prune-Pending (PP) 2059 The router has received a Prune(*,G) on this interface from a 2060 downstream neighbor and is waiting to see whether the prune 2061 will be overridden by another downstream router. For 2062 forwarding purposes, the Prune-Pending state functions exactly 2063 like the Join state. 2065 In addition, the state-machine uses two timers: 2067 Expiry Timer (ET) 2068 This timer is restarted when a valid Join(*,G) is received. 2069 Expiry of the Expiry Timer causes the interface state to 2070 revert to NoInfo for this group. 2072 Prune-Pending Timer (PPT) 2073 This timer is set when a valid Prune(*,G) is received. Expiry 2074 of the Prune-Pending Timer causes the interface state to 2075 revert to NoInfo for this group. 2077 Figure 3: Downstream per-interfacce (*,G) state-machine in tabular form 2079 +-------------++---------------------------------------------------------+ 2080 | || Event | 2081 | ++-------------+--------------+-------------+--------------+ 2082 |Prev State ||Receive | Receive | Prune- | Expiry Timer | 2083 | ||Join(*,G) | Prune(*,G) | Pending | Expires | 2084 | || | | Timer | | 2085 | || | | Expires | | 2086 +-------------++-------------+--------------+-------------+--------------+ 2087 | ||-> J state | -> NI state | - | - | 2088 |NoInfo (NI) ||start Expiry | | | | 2089 | ||Timer | | | | 2090 +-------------++-------------+--------------+-------------+--------------+ 2091 | ||-> J state | -> PP state | - | -> NI state | 2092 |Join (J) ||restart | start Prune- | | | 2093 | ||Expiry Timer | Pending | | | 2094 | || | Timer | | | 2095 +-------------++-------------+--------------+-------------+--------------+ 2096 | ||-> J state | -> PP state | -> NI state | -> NI state | 2097 | ||restart | | Send Prune- | | 2098 | ||Expiry | | Echo(*,G) | | 2099 |Prune- ||Timer; | | | | 2100 |Pending (PP) ||cancel | | | | 2101 | ||Prune- | | | | 2102 | ||Pending | | | | 2103 | ||Timer | | | | 2104 +-------------++-------------+--------------+-------------+--------------+ 2106 The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" imply 2107 receiving a Join or Prune targeted to this router's address on the 2108 received interface. If the destination address is not correct, these 2109 state transitions in this state machine must not occur, although seeing 2110 such a packet may cause state transitions in other state machines. 2112 On unnumbered interfaces on point-to-point links, the router's address 2113 should be the same as the source address it chose for the Hello message 2114 it sent over that interface. However on point-to-point links we also 2115 recommend that PIM Join/Prune messages with a destination address of all 2116 zeros are also accepted. 2118 Transitions from NoInfo State 2120 When in NoInfo state, the following event may trigger a transition: 2122 Receive Join(*,G) 2123 A Join(*,G) is received on interface I with its Upstream 2124 Neighbor Address set to the router's address on I. 2126 The (*,G) downstream state machine on interface I transitions 2127 to the Join state. The Expiry Timer (ET) is started, and set 2128 to the HoldTime from the triggering Join/Prune message. 2130 Transitions from Join State 2132 When in Join state, the following events may trigger a transition: 2134 Receive Join(*,G) 2135 A Join(*,G) is received on interface I with its Upstream 2136 Neighbor Address set to the router's address on I. 2138 The (*,G) downstream state machine on interface I remains in 2139 Join state, and the Expiry Timer (ET) is restarted, set to 2140 maximum of its current value and the HoldTime from the 2141 triggering Join/Prune message. 2143 Receive Prune(*,G) 2144 A Prune(*,G) is received on interface I with its Upstream 2145 Neighbor Address set to the router's address on I. 2147 The (*,G) downstream state machine on interface I transitions 2148 to the Prune-Pending state. The Prune-Pending Timer is 2149 started; it is set to the J/P_Override_Interval(I) if the 2150 router has more than one neighbor on that interface; otherwise 2151 it is set to zero causing it to expire immediately. 2153 Expiry Timer Expires 2154 The Expiry Timer for the (*,G) downstream state machine on 2155 interface I expires. 2157 The (*,G) downstream state machine on interface I transitions 2158 to the NoInfo state. 2160 Transitions from Prune-Pending State 2162 When in Prune-Pending state, the following events may trigger a 2163 transition: 2165 Receive Join(*,G) 2166 A Join(*,G) is received on interface I with its Upstream 2167 Neighbor Address set to the router's address on I. 2169 The (*,G) downstream state machine on interface I transitions 2170 to the Join state. The Prune-Pending Timer is canceled 2171 (without triggering an expiry event). The Expiry Timer is 2172 restarted, set to maximum of its current value and the 2173 HoldTime from the triggering Join/Prune message. 2175 Expiry Timer Expires 2176 The Expiry Timer for the (*,G) downstream state machine on 2177 interface I expires. 2179 The (*,G) downstream state machine on interface I transitions 2180 to the NoInfo state. 2182 Prune-Pending Timer Expires 2183 The Prune-Pending Timer for the (*,G) downstream state machine 2184 on interface I expires. 2186 The (*,G) downstream state machine on interface I transitions 2187 to the NoInfo state. A PruneEcho(*,G) is sent onto the subnet 2188 connected to interface I. 2190 The action "Send PruneEcho(*,G)" is triggered when the router 2191 stops forwarding on an interface as a result of a prune. A 2192 PruneEcho(*,G) is simply a Prune(*,G) message sent by the 2193 upstream router on a LAN with its own address in the Upstream 2194 Neighbor Address field. Its purpose is to add additional 2195 reliability so that if a Prune that should have been 2196 overridden by another router is lost locally on the LAN, then 2197 the PruneEcho may be received and cause the override to 2198 happen. A PruneEcho(*,G) need not be sent on an interface 2199 that contains only a single PIM neighbor during the time this 2200 state machine was in Prune-Pending state. 2202 4.5.3. Receiving (S,G) Join/Prune Messages 2204 The per-interface state machine for receiving (S,G) Join/Prune messages 2205 is given below, and is almost identical to that for (*,G) messages. 2206 There are three states: 2208 NoInfo (NI) 2209 The interface has no (S,G) Join state and no (S,G) timers 2210 running. 2212 Join (J) 2213 The interface has (S,G) Join state which will cause us to 2214 forward packets from S destined for G from this interface if 2215 the (S,G) state is active (the SPTbit is set) except if the 2216 router lost an assert on this interface. 2218 Prune-Pending (PP) 2219 The router has received a Prune(S,G) on this interface from a 2220 downstream neighbor and is waiting to see whether the prune 2221 will be overridden by another downstream router. For 2222 forwarding purposes, the Prune-Pending state functions exactly 2223 like the Join state. 2225 In addition, there are two timers: 2227 Expiry Timer (ET) 2228 This timer is set when a valid Join(S,G) is received. Expiry 2229 of the Expiry Timer causes this state machine to revert to 2230 NoInfo state. 2232 Prune-Pending Timer (PPT) 2233 This timer is set when a valid Prune(S,G) is received. Expiry 2234 of the Prune-Pending Timer causes this state machine to revert 2235 to NoInfo state. 2237 Figure 4: Downstream per-interface (S,G) state-machine in tabular form 2239 +-------------++---------------------------------------------------------+ 2240 | || Event | 2241 | ++-------------+--------------+-------------+--------------+ 2242 |Prev State ||Receive | Receive | Prune- | Expiry Timer | 2243 | ||Join(S,G) | Prune(S,G) | Pending | Expires | 2244 | || | | Timer | | 2245 | || | | Expires | | 2246 +-------------++-------------+--------------+-------------+--------------+ 2247 | ||-> J state | -> NI state | - | - | 2248 |NoInfo (NI) ||start Expiry | | | | 2249 | ||Timer | | | | 2250 +-------------++-------------+--------------+-------------+--------------+ 2251 | ||-> J state | -> PP state | - | -> NI state | 2252 |Join (J) ||restart | start Prune- | | | 2253 | ||Expiry Timer | Pending | | | 2254 | || | Timer | | | 2255 +-------------++-------------+--------------+-------------+--------------+ 2256 | ||-> J state | -> PP state | -> NI state | -> NI state | 2257 | ||restart | | Send Prune- | | 2258 | ||Expiry | | Echo(S,G) | | 2259 |Prune- ||Timer; | | | | 2260 |Pending (PP) ||cancel | | | | 2261 | ||Prune- | | | | 2262 | ||Pending | | | | 2263 | ||Timer | | | | 2264 +-------------++-------------+--------------+-------------+--------------+ 2266 The transition events "Receive Join(S,G)" and "Receive Prune(S,G)" imply 2267 receiving a Join or Prune targeted to this router's address on the 2268 received interface. If the destination address is not correct, these 2269 state transitions in this state machine must not occur, although seeing 2270 such a packet may cause state transitions in other state machines. 2272 On unnumbered interfaces on point-to-point links, the router's address 2273 should be the same as the source address it chose for the Hello message 2274 it sent over that interface. However on point-to-point links we also 2275 recommend that PIM Join/Prune messages with a destination address of all 2276 zeros are also accepted. 2278 Transitions from NoInfo State 2280 When in NoInfo state, the following event may trigger a transition: 2282 Receive Join(S,G) 2283 A Join(S,G) is received on interface I with its Upstream 2284 Neighbor Address set to the router's address on I. 2286 The (S,G) downstream state machine on interface I transitions 2287 to the Join state. The Expiry Timer (ET) is started, and set 2288 to the HoldTime from the triggering Join/Prune message. 2290 Transitions from Join State 2292 When in Join state, the following events may trigger a transition: 2294 Receive Join(S,G) 2295 A Join(S,G) is received on interface I with its Upstream 2296 Neighbor Address set to the router's address on I. 2298 The (S,G) downstream state machine on interface I remains in 2299 Join state, and the Expiry Timer (ET) is restarted, set to 2300 maximum of its current value and the HoldTime from the 2301 triggering Join/Prune message. 2303 Receive Prune(S,G) 2304 A Prune(S,G) is received on interface I with its Upstream 2305 Neighbor Address set to the router's address on I. 2307 The (S,G) downstream state machine on interface I transitions 2308 to the Prune-Pending state. The Prune-Pending Timer is 2309 started; it is set to the J/P_Override_Interval(I) if the 2310 router has more than one neighbor on that interface; otherwise 2311 it is set to zero causing it to expire immediately. 2313 Expiry Timer Expires 2314 The Expiry Timer for the (S,G) downstream state machine on 2315 interface I expires. 2317 The (S,G) downstream state machine on interface I transitions 2318 to the NoInfo state. 2320 Transitions from Prune-Pending State 2322 When in Prune-Pending state, the following events may trigger a 2323 transition: 2325 Receive Join(S,G) 2326 A Join(S,G) is received on interface I with its Upstream 2327 Neighbor Address set to the router's address on I. 2329 The (S,G) downstream state machine on interface I transitions 2330 to the Join state. The Prune-Pending Timer is canceled 2331 (without triggering an expiry event). The Expiry Timer is 2332 restarted, set to maximum of its current value and the 2333 HoldTime from the triggering Join/Prune message. 2335 Expiry Timer Expires 2336 The Expiry Timer for the (S,G) downstream state machine on 2337 interface I expires. 2339 The (S,G) downstream state machine on interface I transitions 2340 to the NoInfo state. 2342 Prune-Pending Timer Expires 2343 The Prune-Pending Timer for the (S,G) downstream state machine 2344 on interface I expires. 2346 The (S,G) downstream state machine on interface I transitions 2347 to the NoInfo state. A PruneEcho(S,G) is sent onto the subnet 2348 connected to interface I. 2350 The action "Send PruneEcho(S,G)" is triggered when the router 2351 stops forwarding on an interface as a result of a prune. A 2352 PruneEcho(S,G) is simply a Prune(S,G) message sent by the 2353 upstream router on a LAN with its own address in the Upstream 2354 Neighbor Address field. Its purpose is to add additional 2355 reliability so that if a Prune that should have been 2356 overridden by another router is lost locally on the LAN, then 2357 the PruneEcho may be received and cause the override to 2358 happen. A PruneEcho(S,G) need not be sent on an interface 2359 that contains only a single PIM neighbor during the time this 2360 state machine was in Prune-Pending state. 2362 4.5.4. Receiving (S,G,rpt) Join/Prune Messages 2364 The per-interface state machine for receiving (S,G,rpt) Join/Prune 2365 messages is given below. There are five states: 2367 NoInfo (NI) 2368 The interface has no (S,G,rpt) Prune state and no (S,G,rpt) 2369 timers running. 2371 Prune (P) 2372 The interface has (S,G,rpt) Prune state which will cause us 2373 not to forward packets from S destined for G from this 2374 interface even though the interface has active (*,G) Join 2375 state. 2377 Prune-Pending (PP) 2378 The router has received a Prune(S,G,rpt) on this interface 2379 from a downstream neighbor and is waiting to see whether the 2380 prune will be overridden by another downstream router. For 2381 forwarding purposes, the Prune-Pending state functions exactly 2382 like the NoInfo state. 2384 PruneTmp (P') 2385 This state is a transient state which for forwarding purposes 2386 behaves exactly like the Prune state. A (*,G) Join has been 2387 received (which may cancel the (S,G,rpt) Prune). As we parse 2388 the Join/Prune message from top to bottom, we first enter this 2389 state if the message contains a (*,G) Join. Later in the 2390 message we will normally encounter an (S,G,rpt) prune to re- 2391 instate the Prune state. However if we reach the end of the 2392 message without encountering such a (S,G,rpt) prune, then we 2393 will revert to NoInfo state in this state machine. 2395 As no time is spent in this state, no timers can expire. 2397 Prune-Pending-Tmp (PP') 2398 This state is a transient state which is identical to P' 2399 except that it is associated with the PP state rather than the 2400 P state. For forwarding purposes, PP' behaves exactly like PP 2401 state. 2403 In addition, there are two timers: 2405 Expiry Timer (ET) 2406 This timer is set when a valid Prune(S,G,rpt) is received. 2407 Expiry of the Expiry Timer causes this state machine to revert 2408 to NoInfo state. 2410 Prune-Pending Timer (PPT) 2411 This timer is set when a valid Prune(S,G,rpt) is received. 2412 Expiry of the Prune-Pending Timer causes this state machine to 2413 move on to Prune state. 2415 Figure 5: Downstream per-interface (S,G,rpt) state-machine in tabular form 2417 +----------++----------------------------------------------------------------+ 2418 | || Event | 2419 | ++----------+-----------+-----------+---------+---------+---------+ 2420 |Prev ||Receive | Receive | Receive | End of | Prune- | Expiry | 2421 |State ||Join(*,G) | Join | Prune | Message | Pending | Timer | 2422 | || | (S,G,rpt) | (S,G,rpt) | | Timer | Expires | 2423 | || | | | | Expires | | 2424 +----------++----------+-----------+-----------+---------+---------+---------+ 2425 | ||- | - | -> PP | - | n/a | n/a | 2426 | || | | state | | | | 2427 | || | | start | | | | 2428 |NoInfo || | | Prune- | | | | 2429 |(NI) || | | Pending | | | | 2430 | || | | Timer; | | | | 2431 | || | | start | | | | 2432 | || | | Expiry | | | | 2433 | || | | Timer | | | | 2434 +----------++----------+-----------+-----------+---------+---------+---------+ 2435 | ||-> P' | -> NI | -> P | - | n/a | -> NI | 2436 | ||state | state | state | | | state | 2437 |Prune (P) || | | restart | | | | 2438 | || | | Expiry | | | | 2439 | || | | Timer | | | | 2440 +----------++----------+-----------+-----------+---------+---------+---------+ 2441 |Prune- ||-> PP' | -> NI | - | - | -> P | n/a | 2442 |Pending ||state | state | | | state | | 2443 |(PP) || | | | | | | 2444 +----------++----------+-----------+-----------+---------+---------+---------+ 2445 | ||error | error | -> P | -> NI | n/a | n/a | 2446 |Prune-Tmp || | | state | state | | | 2447 |(P') || | | restart | | | | 2448 | || | | Expiry | | | | 2449 | || | | Timer | | | | 2450 +----------++----------+-----------+-----------+---------+---------+---------+ 2451 | ||error | error | -> PP | -> NI | n/a | n/a | 2452 |Prune- || | | state | state | | | 2453 |Pending- || | | restart | | | | 2454 |Tmp (PP') || | | Expiry | | | | 2455 | || | | Timer | | | | 2456 +----------++----------+-----------+-----------+---------+---------+---------+ 2458 The transition events "Receive Join(S,G,rpt)", "Receive Prune(S,G,rpt)", 2459 and "Receive Join(*,G)" imply receiving a Join or Prune targeted to this 2460 router's address on the received interface. If the destination address 2461 is not correct, these state transitions in this state machine must not 2462 occur, although seeing such a packet may cause state transitions in 2463 other state machines. 2465 On unnumbered interfaces on point-to-point links, the router's address 2466 should be the same as the source address it chose for the Hello message 2467 it sent over that interface. However on point-to-point links we also 2468 recommend that PIM Join/Prune messages with a destination address of all 2469 zeros are also accepted. 2471 Transitions from NoInfo State 2473 When in NoInfo (NI) state, the following event may trigger a transition: 2475 Receive Prune(S,G,rpt) 2476 A Prune(S,G,rpt) is received on interface I with its Upstream 2477 Neighbor Address set to the router's address on I. 2479 The (S,G,rpt) downstream state machine on interface I 2480 transitions to the Prune-Pending state. The Expiry Timer (ET) 2481 is started, and set to the HoldTime from the triggering 2482 Join/Prune message. The Prune-Pending Timer is started; it is 2483 set to the J/P_Override_Interval(I) if the router has more 2484 than one neighbor on that interface; otherwise it is set to 2485 zero causing it to expire immediately. 2487 Transitions from Prune-Pending State 2489 When in Prune-Pending (PP) state, the following events may trigger a 2490 transition: 2492 Receive Join(*,G) 2493 A Join(*,G) is received on interface I with its Upstream 2494 Neighbor Address set to the router's address on I. 2496 The (S,G,rpt) downstream state machine on interface I 2497 transitions to Prune-Pending-Tmp state whilst the remainder of 2498 the compound Join/Prune message containing the Join(*,G) is 2499 processed. 2501 Receive Join(S,G,rpt) 2502 A Join(S,G,rpt) is received on interface I with its Upstream 2503 Neighbor Address set to the router's address on I. 2505 The (S,G,rpt) downstream state machine on interface I 2506 transitions to NoInfo state. ET and PPT are canceled. 2508 Prune-Pending Timer Expires 2509 The Prune-Pending Timer for the (S,G,rpt) downstream state 2510 machine on interface I expires. 2512 The (S,G,rpt) downstream state machine on interface I 2513 transitions to the Prune state. 2515 Transitions from Prune State 2517 When in Prune (P) state, the following events may trigger a transition: 2519 Receive Join(*,G) 2520 A Join(*,G) is received on interface I with its Upstream 2521 Neighbor Address set to the router's address on I. 2523 The (S,G,rpt) downstream state machine on interface I 2524 transitions to PruneTmp state whilst the remainder of the 2525 compound Join/Prune message containing the Join(*,G) is 2526 processed. 2528 Receive Join(S,G,rpt) 2529 A Join(S,G,rpt) is received on interface I with its Upstream 2530 Neighbor Address set to the router's address on I. 2532 The (S,G,rpt) downstream state machine on interface I 2533 transitions to NoInfo state. ET and PPT are canceled. 2535 Receive Prune(S,G,rpt) 2536 A Prune(S,G,rpt) is received on interface I with its Upstream 2537 Neighbor Address set to the router's address on I. 2539 The (S,G,rpt) downstream state machine on interface I remains 2540 in Prune state. The Expiry Timer (ET) is restarted, set to 2541 maximum of its current value and the HoldTime from the 2542 triggering Join/Prune message. 2544 Expiry Timer Expires 2545 The Expiry Timer for the (S,G,rpt) downstream state machine on 2546 interface I expires. 2548 The (S,G,rpt) downstream state machine on interface I 2549 transitions to the NoInfo state. ET and PPT are canceled. 2551 Transitions from Prune-Pending-Tmp State 2553 When in Prune-Pending-Tmp (PP') state and processing a compound 2554 Join/Prune message, the following events may trigger a transition: 2556 Receive Prune(S,G,rpt) 2557 The compound Join/Prune message contains a Prune(S,G,rpt). 2559 The (S,G,rpt) downstream state machine on interface I 2560 transitions back to the Prune-Pending state. The Expiry Timer 2561 (ET) is restarted, set to maximum of its current value and the 2562 HoldTime from the triggering Join/Prune message. 2564 End of Message 2565 The end of the compound Join/Prune message is reached. 2567 The (S,G,rpt) downstream state machine on interface I 2568 transitions to the NoInfo state. ET and PPT are canceled. 2570 Transitions from PruneTmp State 2572 When in PruneTmp (P') state and processing a compound Join/Prune 2573 message, the following events may trigger a transition: 2575 Receive Prune(S,G,rpt) 2576 The compound Join/Prune message contains a Prune(S,G,rpt). 2578 The (S,G,rpt) downstream state machine on interface I 2579 transitions back to the Prune state. The Expiry Timer (ET) is 2580 restarted, set to maximum of its current value and the 2581 HoldTime from the triggering Join/Prune message. 2583 End of Message 2584 The end of the compound Join/Prune message is reached. 2586 The (S,G,rpt) downstream state machine on interface I 2587 transitions to the NoInfo state. ET and PPT are canceled. 2589 Notes: 2591 Receiving a Prune(*,G) does not affect the (S,G,rpt) downstream state 2592 machine. 2594 Receiving a Join(*,*,RP) does not affect the (S,G,rpt) downstream state 2595 machine. If a router has originated Join(*,*,RP) and pruned a source 2596 off it using Prune(S,G,rpt), then to receive that source again it should 2597 explicitly re-join using Join(S,G,rpt) or Join(*,G). In some LAN 2598 topologies it is possible for a router sending a new Join(*,*,RP) to 2599 have to wait as much as a Join/Prune Interval before noticing that it 2600 needs to override a neighbor's pre-existing Prune(S,G,rpt). This is 2601 considered acceptable, as (*,*,RP) state is intended to be used only in 2602 long-lived and persistent scenarios. 2604 4.5.5. Sending (*,*,RP) Join/Prune Messages 2606 The per-interface state-machines for (*,*,RP) hold join state from 2607 downstream PIM routers. This state then determines whether a router 2608 needs to propagate a Join(*,*,RP) upstream towards the RP. 2610 If a router wishes to propagate a Join(*,*,RP) upstream, it must also 2611 watch for messages on its upstream interface from other routers on that 2612 subnet, and these may modify its behavior. If it sees a Join(*,*,RP) to 2613 the correct upstream neighbor, it should suppress its own Join(*,*,RP). 2614 If it sees a Prune(*,*,RP) to the correct upstream neighbor, it should 2615 be prepared to override that prune by sending a Join(*,*,RP) almost 2616 immediately. Finally, if it sees the Generation ID (see Section 4.3) of 2617 the correct upstream neighbor change, it knows that the upstream 2618 neighbor has lost state, and it should be prepared to refresh the state 2619 by sending a Join(*,*,RP) almost immediately. 2621 In addition, if the MRIB changes to indicate that the next hop towards 2622 the RP has changed, the router should prune off from the old next hop, 2623 and join towards the new next hop. 2625 The upstream (*,*,RP) state-machine contains only two states: 2627 Not Joined 2628 The downstream state-machines indicate that the router does not 2629 need to join the (*,*,RP) tree for this RP. 2631 Joined 2632 The downstream state-machines indicate that the router should join 2633 the (*,*,RP) tree for this RP. 2635 In addition, one timer JT(*,*,RP) is kept which is used to trigger the 2636 sending of a Join(*,*,RP) to the upstream next hop towards the RP, 2637 NBR(RPF_interface(RP), MRIB.next_hop(RP)). 2639 Figure 6: Upstream (*,*,RP) state-machine in tabular form 2641 +--------------------++-------------------------------------------------+ 2642 | || Event | 2643 | Prev State ++-------------------------+-----------------------+ 2644 | || JoinDesired- | JoinDesired- | 2645 | || (*,*,RP) ->True | (*,*,RP) ->False | 2646 +--------------------++-------------------------+-----------------------+ 2647 | || -> J state | - | 2648 | NotJoined (NJ) || Send Join(*,*,RP); | | 2649 | || Set Join Timer to | | 2650 | || t_periodic | | 2651 +--------------------++-------------------------+-----------------------+ 2652 | Joined (J) || - | -> NJ state | 2653 | || | Send Prune- | 2654 | || | (*,*,RP); Cancel | 2655 | || | Join Timer | 2656 +--------------------++-------------------------+-----------------------+ 2658 In addition, we have the following transitions which occur within the 2659 Joined state: 2661 +-----------------------------------------------------------------------+ 2662 | In Joined (J) State | 2663 +-------------------+--------------------+------------------------------+ 2664 | Timer Expires | See | See | 2665 | | Join(*,*,RP) | Prune(*,*,RP) | 2666 | | to MRIB.- | to MRIB.- | 2667 | | next_hop(RP) | next_hop(RP) | 2668 +-------------------+--------------------+------------------------------+ 2669 | Send | Increase Join | Decrease Join | 2670 | Join(*,*,RP); | Timer to | Timer to | 2671 | Set Join Timer | t_joinsuppress | t_override | 2672 | to t_periodic | | | 2673 +-------------------+--------------------+------------------------------+ 2675 ------------------------------------------------------------------------- 2676 In Joined (J) State 2677 ------------------------------------------------------------------------- 2678 NBR(RPF_interface(RP), MRIB.next_hop(RP) GenID 2679 MRIB.next_hop(RP)) changes 2680 changes 2681 ------------------------------------------------------------------------- 2682 Send Join(*,*,RP) to new Decrease Join Timer to 2683 next hop; Send t_override 2684 Prune(*,*,RP) to old 2685 next hop; set Join Timer 2686 to t_periodic 2688 | | | 2689 | | | 2690 | | | 2692 | | | 2693 | | | 2694 +-----------------------------------+-----------------------------------+ 2696 This state machine uses the following macro: 2698 bool JoinDesired(*,*,RP) { 2699 if immediate_olist(*,*,RP) != NULL 2700 return TRUE 2701 else 2702 return FALSE 2703 } 2705 JoinDesired(*,*,RP) is true when the router has received (*,*,RP) Joins 2706 from any downstream interface. Note that although JoinDesired is true, 2707 the router's sending of a Join(*,*,RP) message may be suppressed by 2708 another router sending a Join(*,*,RP) onto the upstream interface. 2710 Transitions from NotJoined State 2712 When the upstream (*,*,RP) state-machine is in NotJoined state, the 2713 following event may trigger a state transition: 2715 JoinDesired(*,*,RP) becomes True 2716 The downstream state for (*,*,RP) has changed so that at least 2717 one interface is in immediate_olist(*,*,RP), making 2718 JoinDesired(*,*,RP) become True. 2720 The upstream (*,*,RP) state machine transitions to Joined 2721 state. Send Join(*,*,RP) to the appropriate upstream 2722 neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)). 2723 Set the Join Timer (JT) to expire after t_periodic seconds. 2725 Transitions from Joined State 2727 When the upstream (*,*,RP) state-machine is in Joined state, the 2728 following events may trigger state transitions: 2730 JoinDesired(*,*,RP) becomes False 2731 The downstream state for (*,*,RP) has changed so no interface 2732 is in immediate_olist(*,*,RP), making JoinDesired(*,*,RP) 2733 become False. 2735 The upstream (*,*,RP) state machine transitions to NotJoined 2736 state. Send Prune(*,*,RP) to the appropriate upstream 2737 neighbor, which is NBR(RPF_interface(RP), MRIB.next_hop(RP)). 2738 Cancel the Join Timer (JT). 2740 Join Timer Expires 2741 The Join Timer (JT) expires, indicating time to send a 2742 Join(*,*,RP) 2744 Send Join(*,*,RP) to the appropriate upstream neighbor, which 2745 is NBR(RPF_interface(RP), MRIB.next_hop(RP)). Restart the 2746 Join Timer (JT) to expire after t_periodic seconds. 2748 See Join(*,*,RP) to MRIB.next_hop(RP) 2749 This event is only relevant if RPF_interface(RP) is a shared 2750 medium. This router sees another router on RPF_interface(RP) 2751 send a Join(*,*,RP) to any of the addresses belonging to 2752 NBR(RPF_interface(RP), MRIB.next_hop(RP)). This causes this 2753 router to suppress its own Join. 2755 The upstream (*,*,RP) state machine remains in Joined state. 2757 Let t_joinsuppress be the minimum of t_suppressed and the 2758 HoldTime from the Join/Prune message triggering this event. 2759 If the Join Timer is set to expire in less than t_joinsuppress 2760 seconds, reset it so that it expires after t_joinsuppress 2761 seconds. If the Join Timer is set to expire in more than 2762 t_joinsuppress seconds, leave it unchanged. 2764 See Prune(*,*,RP) to MRIB.next_hop(RP) 2765 This event is only relevant if RPF_interface(RP) is a shared 2766 medium. This router sees another router on RPF_interface(RP) 2767 send a Prune(*,*,RP) to any of the addresses belonging to 2768 NBR(RPF_interface(RP), MRIB.next_hop(RP)). As this router is 2769 in Joined state, it must override the Prune after a short 2770 random interval. 2772 The upstream (*,*,RP) state machine remains in Joined state. 2773 If the Join Timer is set to expire in more than t_override 2774 seconds, reset it so that it expires after t_override seconds. 2775 If the Join Timer is set to expire in less than t_override 2776 seconds, leave it unchanged. 2778 NBR(RPF_interface(RP), MRIB.next_hop(RP)) changes 2779 A change in the MRIB routing base causes the next hop towards 2780 the RP to change. 2782 The upstream (*,*,RP) state machine remains in Joined state. 2783 Send Join(*,*,RP) to the new upstream neighbor which is the 2784 new value of NBR(RPF_interface(RP), MRIB.next_hop(RP)). Send 2785 Prune(*,*,RP) to the old upstream neighbor, which is the old 2786 value of NBR(RPF_interface(RP), MRIB.next_hop(RP)). Set the 2787 Join Timer (JT) to expire after t_periodic seconds. 2789 MRIB.next_hop(RP) GenID changes 2790 The Generation ID of the router that is MRIB.next_hop(RP) 2791 changes. This normally means that this neighbor has lost 2792 state, and so the state must be refreshed. 2794 The upstream (*,*,RP) state machine remains in Joined state. 2795 If the Join Timer is set to expire in more than t_override 2796 seconds, reset it so that it expires after t_override seconds. 2798 4.5.6. Sending (*,G) Join/Prune Messages 2800 The per-interface state-machines for (*,G) hold join state from 2801 downstream PIM routers. This state then determines whether a router 2802 needs to propagate a Join(*,G) upstream towards the RP. 2804 If a router wishes to propagate a Join(*,G) upstream, it must also watch 2805 for messages on its upstream interface from other routers on that 2806 subnet, and these may modify its behavior. If it sees a Join(*,G) to 2807 the correct upstream neighbor, it should suppress its own Join(*,G). If 2808 it sees a Prune(*,G) to the correct upstream neighbor, it should be 2809 prepared to override that prune by sending a Join(*,G) almost 2810 immediately. Finally, if it sees the Generation ID (see Section 4.3) of 2811 the correct upstream neighbor change, it knows that the upstream 2812 neighbor has lost state, and it should be prepared to refresh the state 2813 by sending a Join(*,G) almost immediately. 2815 If a (*,G) Assert occurs on the upstream interface, and this changes the 2816 this router's idea of the upstream neighbor, it should be prepared to 2817 ensure that the Assert winner is aware of downstream routers by sending 2818 a Join(*,G) almost immediately. 2820 In addition, if the MRIB changes to indicate that the next hop towards 2821 the RP has changed, and either the upstream interface changes or there 2822 is no Assert winner on the upstream interface, the router should prune 2823 off from the old next hop, and join towards the new next hop. 2825 The upstream (*,G) state-machine only contains two states: 2827 Not Joined 2828 The downstream state-machines indicate that the router does not 2829 need to join the RP tree for this group. 2831 Joined 2832 The downstream state-machines indicate that the router should join 2833 the RP tree for this group. 2835 In addition, one timer JT(*,G) is kept which is used to trigger the 2836 sending of a Join(*,G) to the upstream next hop towards the RP, 2837 RPF'(*,G). 2839 Figure 7: Upstream (*,G) state-machine in tabular form 2841 +--------------------++-------------------------------------------------+ 2842 | || Event | 2843 | Prev State ++------------------------+------------------------+ 2844 | || JoinDesired(*,G) | JoinDesired(*,G) | 2845 | || ->True | ->False | 2846 +--------------------++------------------------+------------------------+ 2847 | || -> J state | - | 2848 | NotJoined (NJ) || Send Join(*,G); | | 2849 | || Set Join Timer to | | 2850 | || t_periodic | | 2851 +--------------------++------------------------+------------------------+ 2852 | Joined (J) || - | -> NJ state | 2853 | || | Send Prune(*,G); | 2854 | || | Cancel Join Timer | 2855 +--------------------++------------------------+------------------------+ 2857 In addition, we have the following transitions which occur within the 2858 Joined state: 2860 +-----------------------------------------------------------------------+ 2861 | In Joined (J) State | 2862 +-----------------+-----------------+-----------------+-----------------+ 2863 |Timer Expires | See Join(*,G) | See Prune(*,G) | RPF'(*,G) | 2864 | | to RPF'(*,G) | to RPF'(*,G) | changes due to | 2865 | | | | an Assert | 2866 +-----------------+-----------------+-----------------+-----------------+ 2867 |Send | Increase Join | Decrease Join | Decrease Join | 2868 |Join(*,G); Set | Timer to | Timer to | Timer to | 2869 |Join Timer to | t_joinsuppress | t_override | t_override | 2870 |t_periodic | | | | 2871 +-----------------+-----------------+-----------------+-----------------+ 2873 +-----------------------------------------------------------------------+ 2874 | In Joined (J) State | 2875 +----------------------------------+------------------------------------+ 2876 | RPF'(*,G) changes not | RPF'(*,G) GenID changes | 2877 | due to an Assert | | 2878 +----------------------------------+------------------------------------+ 2879 | Send Join(*,G) to new | Decrease Join Timer to | 2880 | next hop; Send | t_override | 2881 | Prune(*,G) to old next | | 2882 | hop; Set Join Timer to | | 2883 | t_periodic | | 2884 +----------------------------------+------------------------------------+ 2885 This state machine uses the following macro: 2887 bool JoinDesired(*,G) { 2888 if (immediate_olist(*,G) != NULL || 2889 (JoinDesired(*,*,RP(G)) && 2890 AssertWinner(*, G, RPF_interface(RP(G))) != NULL)) 2891 return TRUE 2892 else 2893 return FALSE 2894 } 2896 JoinDesired(*,G) is true when the router has forwarding state that would 2897 cause it to forward traffic for G using shared tree state. Note that 2898 although JoinDesired is true, the router's sending of a Join(*,G) 2899 message may be suppressed by another router sending a Join(*,G) onto the 2900 upstream interface. 2902 Transitions from NotJoined State 2904 When the upstream (*,G) state-machine is in NotJoined state, the 2905 following event may trigger a state transition: 2907 JoinDesired(*,G) becomes True 2908 The downstream state for (*,G) has changed so that at least 2909 one interface is in immediate_olist(*,G), making 2910 JoinDesired(*,G) become True. 2912 The upstream (*,G) state machine transitions to Joined state. 2913 Send Join(*,G) to the appropriate upstream neighbor, which is 2914 RPF'(*,G). Set the Join Timer (JT) to expire after t_periodic 2915 seconds. 2917 Transitions from Joined State 2919 When the upstream (*,G) state-machine is in Joined state, the following 2920 events may trigger state transitions: 2922 JoinDesired(*,G) becomes False 2923 The downstream state for (*,G) has changed so no interface is 2924 in immediate_olist(*,G), making JoinDesired(*,G) become False. 2926 The upstream (*,G) state machine transitions to NotJoined 2927 state. Send Prune(*,G) to the appropriate upstream neighbor, 2928 which is RPF'(*,G). Cancel the Join Timer (JT). 2930 Join Timer Expires 2931 The Join Timer (JT) expires, indicating time to send a 2932 Join(*,G) 2933 Send Join(*,G) to the appropriate upstream neighbor, which is 2934 RPF'(*,G). Restart the Join Timer (JT) to expire after 2935 t_periodic seconds. 2937 See Join(*,G) to RPF'(*,G) 2938 This event is only relevant if RPF_interface(RP(G)) is a 2939 shared medium. This router sees another router on 2940 RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G). This 2941 causes this router to suppress its own Join. 2943 The upstream (*,G) state machine remains in Joined state. 2945 Let t_joinsuppress be the minimum of t_suppressed and the 2946 HoldTime from the Join/Prune message triggering this event. 2947 If the Join Timer is set to expire in less than t_joinsuppress 2948 seconds, reset it so that it expires after t_joinsuppress 2949 seconds. If the Join Timer is set to expire in more than 2950 t_joinsuppress seconds, leave it unchanged. 2952 See Prune(*,G) to RPF'(*,G) 2953 This event is only relevant if RPF_interface(RP(G)) is a 2954 shared medium. This router sees another router on 2955 RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G). As this 2956 router is in Joined state, it must override the Prune after a 2957 short random interval. 2959 The upstream (*,G) state machine remains in Joined state. If 2960 the Join Timer is set to expire in more than t_override 2961 seconds, reset it so that it expires after t_override seconds. 2962 If the Join Timer is set to expire in less than t_override 2963 seconds, leave it unchanged. 2965 RPF'(*,G) changes due to an Assert 2966 The current next hop towards the RP changes due to an 2967 Assert(*,G) on the RPF_interface(RP(G)). 2969 The upstream (*,G) state machine remains in Joined state. If 2970 the Join Timer is set to expire in more than t_override 2971 seconds, reset it so that it expires after t_override seconds. 2972 If the Join Timer is set to expire in less than t_override 2973 seconds, leave it unchanged. 2975 RPF'(*,G) changes not due to an Assert 2976 An event occurred which caused the next hop towards the RP for 2977 G to change. This may be caused by a change in the MRIB 2978 routing database. Note that this transition does not occur if 2979 an Assert is active and the upstream interface does not 2980 change. 2982 The upstream (*,G) state machine remains in Joined state. 2983 Send Join(*,G) to the new upstream neighbor which is the new 2984 value of RPF'(*,G). Send Prune(*,G) to the old upstream 2985 neighbor, which is the old value of RPF'(*,G). Set the Join 2986 Timer (JT) to expire after t_periodic seconds. 2988 RPF'(*,G) GenID changes 2989 The Generation ID of the router that is RPF'(*,G) changes. 2990 This normally means that this neighbor has lost state, and so 2991 the state must be refreshed. 2993 The upstream (*,G) state machine remains in Joined state. If 2994 the Join Timer is set to expire in more than t_override 2995 seconds, reset it so that it expires after t_override seconds. 2997 4.5.7. Sending (S,G) Join/Prune Messages 2999 The per-interface state-machines for (S,G) hold join state from 3000 downstream PIM routers. This state then determines whether a router 3001 needs to propagate a Join(S,G) upstream towards the source. 3003 If a router wishes to propagate a Join(S,G) upstream, it must also watch 3004 for messages on its upstream interface from other routers on that 3005 subnet, and these may modify its behavior. If it sees a Join(S,G) to 3006 the correct upstream neighbor, it should suppress its own Join(S,G). If 3007 it sees a Prune(S,G), Prune(S,G,rpt), or Prune(*,G) to the correct 3008 upstream neighbor towards S, it should be prepared to override that 3009 prune by scheduling a Join(S,G) to be sent almost immediately. Finally, 3010 if it sees the Generation ID of its upstream neighbor change, it knows 3011 that the upstream neighbor has lost state, and it should refresh the 3012 state by scheduling a Join(S,G) to be sent almost immediately. 3014 If a (S,G) Assert occurs on the upstream interface, and this changes the 3015 this router's idea of the upstream neighbor, it should be prepared to 3016 ensure that the Assert winner is aware of downstream routers by 3017 scheduling a Join(S,G) to be sent almost immediately. 3019 In addition, if MRIB changes cause the next hop towards the source to 3020 change, and either the upstream interface changes or there is no Assert 3021 winner on the upstream interface, the router should send a prune to the 3022 old next hop, and a join to the new next hop. 3024 The upstream (S,G) state-machine only contains two states: 3026 Not Joined 3027 The downstream state machines and local membership information do 3028 not indicate that the router needs to join the shortest-path tree 3029 for this (S,G). 3031 Joined 3032 The downstream state machines and local membership information 3033 indicate that the router should join the shortest-path tree for 3034 this (S,G). 3036 In addition, one timer JT(S,G) is kept which is used to trigger the 3037 sending of a Join(S,G) to the upstream next hop towards S, RPF'(S,G). 3039 Figure 8: Upstream (S,G) state-machine in tabular form 3041 +--------------------+--------------------------------------------------+ 3042 | | Event | 3043 | Prev State +-------------------------+------------------------+ 3044 | | JoinDesired(S,G) | JoinDesired(S,G) | 3045 | | ->True | ->False | 3046 +--------------------+-------------------------+------------------------+ 3047 | NotJoined (NJ) | -> J state | - | 3048 | | Send Join(S,G); | | 3049 | | Set Join Timer to | | 3050 | | t_periodic | | 3051 +--------------------+-------------------------+------------------------+ 3052 | Joined (J) | - | -> NJ state | 3053 | | | Send Prune(S,G); | 3054 | | | Set SPTbit(S,G) to | 3055 | | | FALSE; Cancel Join | 3056 | | | Timer | 3057 +--------------------+-------------------------+------------------------+ 3058 In addition, we have the following transitions which occur within the 3059 Joined state: 3061 +-----------------------------------------------------------------------+ 3062 | In Joined (J) State | 3063 +-----------------+-----------------+------------------+----------------+ 3064 | Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune | 3065 | | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to | 3066 | | | | RPF'(S,G) | 3067 +-----------------+-----------------+------------------+----------------+ 3068 | Send | Increase Join | Decrease Join | Decrease Join | 3069 | Join(S,G); Set | Timer to | Timer to | Timer to | 3070 | Join Timer to | t_joinsuppress | t_override | t_override | 3071 | t_periodic | | | | 3072 +-----------------+-----------------+------------------+----------------+ 3074 +-----------------------------------------------------------------------+ 3075 | In Joined (J) State | 3076 +-----------------+-----------------+-----------------+-----------------+ 3077 | See Prune(*,G) | RPF'(S,G) | RPF'(S,G) | RPF'(S,G) | 3078 | to RPF'(S,G) | changes not | GenID changes | changes due to | 3079 | | due to an | | an Assert | 3080 | | Assert | | | 3081 +-----------------+-----------------+-----------------+-----------------+ 3082 | Decrease Join | Send Join(S,G) | Decrease Join | Decrease Join | 3083 | Timer to | to new next | Timer to | Timer to | 3084 | t_override | hop; Send | t_override | t_override | 3085 | | Prune(S,G) to | | | 3086 | | old next hop; | | | 3087 | | Set Join Timer | | | 3088 | | to t_periodic | | | 3089 +-----------------+-----------------+-----------------+-----------------+ 3091 This state machine uses the following macro: 3093 bool JoinDesired(S,G) { 3094 return( immediate_olist(S,G) != NULL 3095 OR ( KeepaliveTimer(S,G) is running 3096 AND inherited_olist(S,G) != NULL ) ) 3097 } 3099 JoinDesired(S,G) is true when the router has forwarding state that would 3100 cause it to forward traffic for G using source tree state. The source 3101 tree state can either be as a result of active source-specific join 3102 state, or the (S,G) Keepalive Timer and active non-source-specific 3103 state. Note that although JoinDesired is true, the router's sending of a 3104 Join(S,G) message may be suppressed by another router sending a 3105 Join(S,G) onto the upstream interface. 3107 Transitions from NotJoined State 3109 When the upstream (S,G) state-machine is in NotJoined state, the 3110 following event may trigger a state transition: 3112 JoinDesired(S,G) becomes True 3113 The downstream state for (S,G) has changed so that at least 3114 one interface is in inherited_olist(S,G), making 3115 JoinDesired(S,G) become True. 3117 The upstream (S,G) state machine transitions to Joined state. 3118 Send Join(S,G) to the appropriate upstream neighbor, which is 3119 RPF'(S,G). Set the Join Timer (JT) to expire after t_periodic 3120 seconds. 3122 Transitions from Joined State 3124 When the upstream (S,G) state-machine is in Joined state, the following 3125 events may trigger state transitions: 3127 JoinDesired(S,G) becomes False 3128 The downstream state for (S,G) has changed so no interface is 3129 in inherited_olist(S,G), making JoinDesired(S,G) become False. 3131 The upstream (S,G) state machine transitions to NotJoined 3132 state. Send Prune(S,G) to the appropriate upstream neighbor, 3133 which is RPF'(S,G). Cancel the Join Timer (JT), and set 3134 SPTbit(S,G) to FALSE. 3136 Join Timer Expires 3137 The Join Timer (JT) expires, indicating time to send a 3138 Join(S,G) 3140 Send Join(S,G) to the appropriate upstream neighbor, which is 3141 RPF'(S,G). Restart the Join Timer (JT) to expire after 3142 t_periodic seconds. 3144 See Join(S,G) to RPF'(S,G) 3145 This event is only relevant if RPF_interface(S) is a shared 3146 medium. This router sees another router on RPF_interface(S) 3147 send a Join(S,G) to RPF'(S,G). This causes this router to 3148 suppress its own Join. 3150 The upstream (S,G) state machine remains in Joined state. 3152 Let t_joinsuppress be the minimum of t_suppressed and the 3153 HoldTime from the Join/Prune message triggering this event. 3154 If the Join Timer is set to expire in less than t_joinsuppress 3155 seconds, reset it so that it expires after t_joinsuppress 3156 seconds. If the Join Timer is set to expire in more than 3157 t_joinsuppress seconds, leave it unchanged. 3159 See Prune(S,G) to RPF'(S,G) 3160 This event is only relevant if RPF_interface(S) is a shared 3161 medium. This router sees another router on RPF_interface(S) 3162 send a Prune(S,G) to RPF'(S,G). As this router is in Joined 3163 state, it must override the Prune after a short random 3164 interval. 3166 The upstream (S,G) state machine remains in Joined state. If 3167 the Join Timer is set to expire in more than t_override 3168 seconds, reset it so that it expires after t_override seconds. 3170 See Prune(S,G,rpt) to RPF'(S,G) 3171 This event is only relevant if RPF_interface(S) is a shared 3172 medium. This router sees another router on RPF_interface(S) 3173 send a Prune(S,G,rpt) to RPF'(S,G). If the upstream router is 3174 an RFC 2362 compliant PIM router, then the Prune(S,G,rpt) will 3175 cause it to stop forwarding. For backwards compatibility, 3176 this router should override the prune so that forwarding 3177 continues. 3179 The upstream (S,G) state machine remains in Joined state. If 3180 the Join Timer is set to expire in more than t_override 3181 seconds, reset it so that it expires after t_override seconds. 3183 See Prune(*,G) to RPF'(S,G) 3184 This event is only relevant if RPF_interface(S) is a shared 3185 medium. This router sees another router on RPF_interface(S) 3186 send a Prune(*,G) to RPF'(S,G). If the upstream router is an 3187 RFC 2362 compliant PIM router, then the Prune(*,G) will cause 3188 it to stop forwarding. For backwards compatibility, this 3189 router should override the prune so that forwarding continues. 3191 The upstream (S,G) state machine remains in Joined state. If 3192 the Join Timer is set to expire in more than t_override 3193 seconds, reset it so that it expires after t_override seconds. 3195 RPF'(S,G) changes due to an Assert 3196 The current next hop towards S changes due to an Assert(S,G) 3197 on the RPF_interface(S). 3199 The upstream (S,G) state machine remains in Joined state. If 3200 the Join Timer is set to expire in more than t_override 3201 seconds, reset it so that it expires after t_override seconds. 3202 If the Join Timer is set to expire in less than t_override 3203 seconds, leave it unchanged. 3205 RPF'(S,G) changes 3206 A change in the routing base stored in the MRIB causes the 3207 next hop towards S to change and there is no (S,G) Assert 3208 active. 3210 The upstream (S,G) state machine remains in Joined state. 3211 Send Join(S,G) to the new upstream neighbor which is the new 3212 value of RPF'(S,G). Send Prune(S,G) to the old upstream 3213 neighbor, which is the old value of RPF'(S,G). Set the Join 3214 Timer (JT) to expire after t_periodic seconds. 3216 RPF'(S,G) GenID changes 3217 The Generation ID of the router that is RPF'(S,G) changes. 3218 This normally means that this neighbor has lost state, and so 3219 the state must be refreshed. 3221 The upstream (S,G) state machine remains in Joined state. If 3222 the Join Timer is set to expire in more than t_override 3223 seconds, reset it so that it expires after t_override seconds. 3225 4.5.8. (S,G,rpt) Periodic Messages 3227 (S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP tree 3228 with the RPT bit set, either to modify the results of (*,G) Joins, or to 3229 override the behavior of other upstream LAN peers. The next section 3230 describes the rules for sending triggered messages. This section 3231 describes the rules for including an Prune(S,G,rpt) message with a 3232 Join(*,G). 3234 When a router is going to send a Join(*,G), it should use the following 3235 pseudocode, for each (S,G) for which it has state, to decide whether to 3236 include a Prune(S,G,rpt) in the compound Join/Prune message: 3238 if( SPTbit(S,G) == TRUE ) { 3239 # Note: If receiving (S,G) on the SPT, we only prune off the 3240 # shared tree if the RPF neighbors differ. 3241 if( RPF'(*,G) != RPF'(S,G) ) { 3242 add Prune(S,G,rpt) to compound message 3243 } 3244 } else if ( inherited_olist(S,G,rpt) == NULL ) { 3245 # Note: all (*,G) olist interfaces received RPT prunes for (S,G). 3246 add Prune(S,G,rpt) to compound message 3247 } else if ( RPF'(*,G) != RPF'(S,G,rpt) { 3248 # Note: we joined the shared tree, but there was an (S,G) assert and 3249 # the source tree RPF neighbor is different. 3250 add Prune(S,G,rpt) to compound message 3251 } 3253 Note that Join(S,G,rpt) is not normally sent as a periodic message, but 3254 only as a triggered message. 3256 4.5.9. State Machine for (S,G,rpt) Triggered Messages 3258 The state machine for (S,G,rpt) triggered messages is required per-(S,G) 3259 when there is (*,G) or (*,*,RP) join state at a router, and the router 3260 or any of its upstream LAN peers wishes to prune S off the RP tree. 3262 There are three states in the state-machine. One of the states is when 3263 there is neither (*,G) nor (*,*,RP(G)) join state at this router. If 3264 there is (*,G) or (*,*,RP(G)) join state at the router, then the state 3265 machine must be at one of the other two states: 3267 Pruned(S,G,rpt) 3268 (*,G) or (*,*,RP(G)) Joined, but (S,G,rpt) pruned 3270 NotPruned(S,G,rpt) 3271 (*,G) or (*,*,RP(G)) Joined, and (S,G,rpt) not pruned 3273 RPTNotJoined(G) 3274 neither (*,G) nor (*,*,RP(G)) has not been joined. 3276 In addition, there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which is 3277 used to delay triggered Join(S,G,rpt) messages to prevent implosions of 3278 triggered messages. 3280 Figure 9: Upstream (S,G,rpt) state-machine for triggered messages in 3281 tabular form 3283 +---------------+-------------------------------------------------------------+ 3284 | | Event | 3285 | +----------------+----------------+-------------+-------------+ 3286 |Prev State | PruneDesired- | PruneDesired- |RPTJoin- | inherited_- | 3287 | | (S,G,rpt) | (S,G,rpt) |Desired(G) | olist- | 3288 | | ->True | ->False |->False | (S,G,rpt) | 3289 | | | | | ->non-NULL | 3290 +---------------+----------------+----------------+-------------+-------------+ 3291 |RPTNotJoined | -> P state | - |- | -> NP state | 3292 |(G) (NJ) | | | | | 3293 +---------------+----------------+----------------+-------------+-------------+ 3294 |Pruned | - | -> NP state |-> NJ state | - | 3295 |(S,G,rpt) (P) | | Send Join | | | 3296 | | | (S,G,rpt) | | | 3297 +---------------+----------------+----------------+-------------+-------------+ 3298 |NotPruned | -> P state | - |-> NJ state | - | 3299 |(S,G,rpt) | Send Prune | |Cancel OT | | 3300 |(NP) | (S,G,rpt); | | | | 3301 | | Cancel OT | | | | 3302 +---------------+----------------+----------------+-------------+-------------+ 3303 Additionally, we have the following transitions within the 3304 NotPruned(S,G,rpt) state which are all used for prune override behavior. 3306 +-----------------------------------------------------------------------+ 3307 | In NotPruned(S,G,rpt) State | 3308 +-----------+--------------+--------------+--------------+--------------+ 3309 |Override | See Prune | See Join | See Prune | RPF' | 3310 |Timer | (S,G,rpt) to | (S,G,rpt) to | (S,G) to | (S,G,rpt) -> | 3311 |expires | RPF' | RPF' | RPF' | RPF' (*,G) | 3312 | | (S,G,rpt) | (S,G,rpt) | (S,G,rpt) | | 3313 +-----------+--------------+--------------+--------------+--------------+ 3314 |Send Join | OT = min(OT, | Cancel OT | OT = min(OT, | OT = min(OT, | 3315 |(S,G,rpt); | t_override) | | t_override) | t_override) | 3316 |Cancel OT | | | | | 3317 +-----------+--------------+--------------+--------------+--------------+ 3319 Note that the min function in the above state machine considers a non- 3320 running timer to have an infinite value (e.g. min(not-running, 3321 t_override) = t_override). 3323 This state machine uses the following macros: 3325 bool RPTJoinDesired(G) { 3326 return (JoinDesired(*,G) || JoinDesired(*,*,RP(G))) 3327 } 3329 RPTJoinDesired(G) is true when the router has forwarding state that 3330 would cause it to forward traffic for G using either (*,G) or (*,*,RP) 3331 shared tree state. 3333 bool PruneDesired(S,G,rpt) { 3334 return ( RPTJoinDesired(G) AND 3335 ( inherited_olist(S,G,rpt) == NULL 3336 OR (SPTbit(S,G)==TRUE 3337 AND (RPF'(*,G) != RPF'(S,G)) ))) 3338 } 3340 PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true. If 3341 RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true if either 3342 there are no outgoing interfaces that S would be forwarded on, or if the 3343 router has active (S,G) forwarding state but RPF'(*,G) != RPF'(S,G). 3345 The state machine contains the following transition events: 3347 See Join(S,G,rpt) to RPF'(S,G,rpt) 3348 This event is only relevant in the "Not Pruned" state. 3350 The router sees a Join(S,G,rpt) from someone else to RPF'(S,G,rpt), 3351 which is the correct upstream neighbor. If we're in "NotPruned" 3352 state and the (S,G,rpt) Override Timer is running, then this is 3353 because we have been triggered to send our own Join(S,G,rpt) to 3354 RPF'(S,G,rpt). Someone else beat us to it, so there's no need to 3355 send our own Join. 3357 The action is to cancel the Override Timer. 3359 See Prune(S,G,rpt) to RPF'(S,G,rpt) 3360 This event is only relevant in the "NotPruned" state. 3362 The router sees a Prune(S,G,rpt) from someone else to to 3363 RPF'(S,G,rpt), which is the correct upstream neighbor. If we're in 3364 the "NotPruned" state, then we want to continue to receive traffic 3365 from S destined for G, and that traffic is being supplied by 3366 RPF'(S,G,rpt). Thus we need to override the Prune. 3368 The action is to set the (S,G,rpt) Override Timer to the randomized 3369 prune-override interval, t_override. However if the Override Timer 3370 is already running, we only set the timer if doing so would set it 3371 to a lower value. At the end of this interval, if no-one else has 3372 sent a Join, then we will do so. 3374 See Prune(S,G) to RPF'(S,G,rpt) 3375 This event is only relevant in the "NotPruned" state. 3377 This transition and action are the same as the above transition and 3378 action, except that the Prune does not have the RPT bit set. This 3379 transition is necessary to be compatible with routers implemented 3380 from RFC2362 that don't maintain separate (S,G) and (S,G,rpt) 3381 state. 3383 The (S,G,rpt) prune Override Timer expires 3384 This event is only relevant in the "NotPruned" state. 3386 When the Override Timer expires, we must send a Join(S,G,rpt) to 3387 RPF'(S,G,rpt) to override the Prune message that caused the timer 3388 to be running. We only send this if RPF'(S,G,rpt) equals RPF'(*,G) 3389 - if this were not the case, then the Join might be sent to a 3390 router that does not have (*,G) or (*,*,RP(G)) Join state, and so 3391 the behavior would not be well defined. If RPF'(S,G,rpt) is not 3392 the same as RPF'(*,G), then it may stop forwarding S. However, if 3393 this happens, then the router will send an AssertCancel(S,G), which 3394 would then cause RPF'(S,G,rpt) to become equal to RPF'(*,G) (see 3395 below). 3397 RPF'(S,G,rpt) changes to become equal to RPF'(*,G) 3398 This event is only relevant in the "NotPruned" state. 3400 RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G) 3401 Assert has happened, which means that traffic from S is arriving on 3402 the SPT, and so Prune(S,G,rpt) will have been sent to RPF'(*,G). 3403 When RPF'(S,G,rpt) changes to become equal to RPF'(*,G), we need to 3404 trigger a Join(S,G,rpt) to RPF'(*,G) to cause that router to start 3405 forwarding S again. 3407 The action is to set the (S,G,rpt) Override Timer to the randomized 3408 prune-override interval t_override. However if the timer is 3409 already running, we only set the timer if doing so would set it to 3410 a lower value. At the end of this interval, if no-one else has 3411 sent a Join, then we will do so. 3413 PruneDesired(S,G,rpt)->TRUE 3414 See macro above. This event is relevant in the "NotPruned" and 3415 "RPTNotJoined(G)" states. 3417 The router wishes to receive traffic for G, but does not wish to 3418 receive traffic from S destined for G. This causes the router to 3419 transition into the Pruned state. 3421 If the router was previously in NotPruned state, then the action is 3422 to send a Prune(S,G,rpt) to RPF'(S,G,rpt), and to cancel the 3423 Override Timer. If the router was previously in RPTNotJoined(G) 3424 state, then there is no need to trigger an action in this state 3425 machine because sending a Prune(S,G,rpt) is handled by the rules 3426 for sending the Join(*,G) or Join(*,*,RP). 3428 PruneDesired(S,G,rpt)->FALSE 3429 See macro above. This transition is only relevant in the "Pruned" 3430 state. 3432 If the router is in the Pruned(S,G,rpt) state, and 3433 PruneDesired(S,G,rpt) changes to FALSE, this could be because the 3434 router no longer has RPTJoinDesired(G) true, or it now wishes to 3435 receive traffic from S again. If it is the former, then this 3436 transition should not happen, but instead the 3437 "RPTJoinDesired(G)->FALSE" transition should happen. Thus this 3438 transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE 3439 AND RPTJoinDesired(G)==TRUE" 3441 The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt). 3443 RPTJoinDesired(G)->FALSE 3444 This event is relevant in the "Pruned" and "NotPruned" states. 3446 The router no longer wishes to receive any traffic destined for G 3447 on the RP Tree. This causes a transition to the RPTNotJoined(G) 3448 state, and the Override Timer is canceled if it was running. Any 3449 further actions are handled by the appropriate upstream state 3450 machine for (*,G) or (*,*,RP). 3452 inherited_olist(S,G,rpt) becomes non-NULL 3453 This transition is only relevant in the RPTNotJoined(G) state. 3455 The router has joined the RP tree (handled by the (*,G) or (*,*,RP) 3456 upstream state machine as appropriate), and wants to receive 3457 traffic from S. This does not trigger any events in this state 3458 machine, but causes a transition to the NotPruned(S,G,rpt) state. 3460 4.5.10. Background: (*,*,RP) and (S,G,rpt) interaction 3462 In sections 4.5.8 and 4.5.9 the mechanisms for sending periodic and 3463 triggered (S,G,rpt) messages are described. The astute reader will note 3464 that periodic Prune(S,G,rpt) messages are only sent in PIM Join/Prune 3465 messages containing a Join(*,G), whereas it is possible for a triggered 3466 Prune(S,G,rpt) message to be sent when the router has no (*,G) join 3467 state. This may seem like a contradiction, but in fact it is 3468 intentional, and is a side effect of not optimizing (*,*,RP) behavior. 3470 We first note that reception of a Join(*,*,RP) by itself does not cancel 3471 (S,G,rpt) prune state on that interface, whereas receiving a Join(*,G) 3472 by itself does cancel (S,G,rpt) prune state on that interface. 3473 Similarly, reception of a Prune(*,G) on an interface with (*,*,RP) join 3474 state does not by itself prevent forwarding of G using the (*,*,RP) 3475 state - this is because a Prune(*,G) only serves to cancel (*,G) join 3476 state. Conceptually (*,*,RP) state functions "above" the normal (*,G) 3477 and (S,G) mechanisms, and so neither Join(*,*,RP) or Prune(*,*,RP) 3478 messages affect any other state. 3480 The upshot of this is that to prevent forwarding (S,G) on (*,*,RP) 3481 state, a Prune(S,G,rpt) must be used. 3483 We also note that for historical reasons there is no Assert(*,*,RP) 3484 message, so any forwarding contention is resolved using Assert(*,G) 3485 messages. 3487 We now need to consider the interaction between (*,*,RP) state and (*,G) 3488 state. If there is a need for an assert between two upstream routers on 3489 a LAN, we need to ensure that the correct thing happens for all 3490 combinations of (*,*,RP) and (*,G) forwarding state. As there is no 3491 Assert(*,*,RP) message, no router can tell whether the assert winner has 3492 (*,*,RP) state or (*,G) state. Thus a downstream router has to treat 3493 the two the same and send its periodic Prune(S,G,rpt) messages to 3494 RPF'(*,G). 3496 To avoid needing to specify all the complex override rules between 3497 (*,*,RP), (*,G) and (S,G,rpt), we simply require that to prune (S,G) off 3498 the (*,*,RP) tree, a Join(*,G) must also be sent. 3500 If a router is receiving on (*,*,RP) state, and has not yet had (*,G) 3501 state instantiated, it may still need to send a triggered Join(S,G,rpt) 3502 to override a Prune(S,G,rpt) that it sees directed to RPF'(*,G) on its 3503 upstream interface. Hence triggered (S,G,rpt) messages may be sent when 3504 JoinDesired(*,G) is false but JoinDesired(*,*,RP) is true. 3506 Finally we note that there is an unoptimized case when the upstream 3507 router on a LAN already has (*,G) join and (S,G,rpt) prune state caused 3508 by an existing downstream router. If at this time a new Join(*,*,RP) is 3509 sent to the upstream router from a different downstream router, this 3510 will not override the (S,G,rpt) prune state at the upstream router. The 3511 override will not occur until the next time the original downstream 3512 router resends its Prune(S,G,rpt). This case was considered to be not 3513 worth optimizing, as (*,*,RP) state is generally very long lived, and so 3514 any minor delays in getting traffic to a new PMBR seem unimportant. 3516 4.6. PIM Assert Messages 3518 Where multiple PIM routers peer over a shared LAN it is possible for 3519 more than one upstream router to have valid forwarding state for a 3520 packet, which can lead to packet duplication (see Section 3 "Multi- 3521 access LANs"). PIM does not attempt to prevent this from occurring. 3522 Instead it detects when this has happened and elects a single forwarder 3523 amongst the upstream routers to prevent further duplication. This 3524 election is performed using PIM Assert messages. Assert messages are 3525 also received by downstream routers on the LAN, and these cause 3526 subsequent Join/Prune messages to be sent to the upstream router that 3527 won the Assert. 3529 In general, a PIM Assert message should only be accepted for processing 3530 if it comes from a known PIM neighbor. A PIM router hears about PIM 3531 neighbors through PIM Hello messages. If a router receives an Assert 3532 message from a particular IP source address and it has not seen a PIM 3533 Hello message from that source address, then the Assert message SHOULD 3534 be discarded without further processing. In addition, if the Hello 3535 message from a neighbor was authenticated using IPsec AH (see Section 3536 6.3) then all Assert messages from that neighbor MUST also be 3537 authenticated using IPsec AH. 3539 4.6.1. (S,G) Assert Message State Machine 3541 The (S,G) Assert state machine for interface I is shown in Figure 10. 3542 There are three states: 3544 NoInfo (NI) 3545 This router has no (S,G) assert state on interface I. 3547 I am Assert Winner (W) 3548 This router has won an (S,G) assert on interface I. It is now 3549 responsible for forwarding traffic from S destined for G out of 3550 interface I. Irrespective of whether it is the DR for I, while a 3551 router is the assert winner, it is also responsible for forwarding 3552 traffic onto I on behalf of local hosts on I that have made 3553 membership requests that specifically refer to S (and G). 3555 I am Assert Loser (L) 3556 This router has lost an (S,G) assert on interface I. It must not 3557 forward packets from S destined for G onto interface I. If it is 3558 the DR on I, it is no longer responsible for forwarding traffic 3559 onto I to satisfy local hosts with membership requests that 3560 specifically refer to S and G. 3562 In addition, there is also an Assert Timer (AT) that is used to time out 3563 asserts on the assert losers and to resend asserts on the assert winner. 3565 Figure 10: Per-interface (S,G) Assert State-machine in tabular form 3567 +-----------------------------------------------------------------------+ 3568 | In NoInfo (NI) State | 3569 +---------------+-------------------+------------------+----------------+ 3570 | Receive | Receive Assert | Data arrives | Receive | 3571 | Inferior | with RPTbit | from S to G on | Preferred | 3572 | Assert with | set and | I and | Assert with | 3573 | RPTbit clear | CouldAssert | CouldAssert | RPTbit clear | 3574 | and | (S,G,I) | (S,G,I) | and AssTrDes | 3575 | CouldAssert | | | (S,G,I) | 3576 | (S,G,I) | | | | 3577 +---------------+-------------------+------------------+----------------+ 3578 | -> W state | -> W state | -> W state | -> L state | 3579 | [Actions A1] | [Actions A1] | [Actions A1] | [Actions A6] | 3580 +---------------+-------------------+------------------+----------------+ 3582 +-----------------------------------------------------------------------+ 3583 | In I Am Assert Winner (W) State | 3584 +----------------+------------------+-----------------+-----------------+ 3585 | Assert Timer | Receive | Receive | CouldAssert | 3586 | Expires | Inferior | Preferred | (S,G,I) -> | 3587 | | Assert | Assert | FALSE | 3588 +----------------+------------------+-----------------+-----------------+ 3589 | -> W state | -> W state | -> L state | -> NI state | 3590 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3591 +----------------+------------------+-----------------+-----------------+ 3593 +-------------------------------------------------------------------------+ 3594 | In I Am Assert Loser (L) State | 3595 +-------------+--------------+--------------+--------------+--------------+ 3596 |Receive | Receive | Receive | Assert Timer | Current | 3597 |Preferred | Acceptable | Inferior | Expires | Winner's | 3598 |Assert | Assert from | Assert from | | GenID | 3599 | | Current | Current | | changes | 3600 | | Winner | Winner | | | 3601 +-------------+--------------+--------------+--------------+--------------+ 3602 |-> L state | -> L state | -> NI state | -> NI state | -> NI state | 3603 |[Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 3604 +-------------+--------------+--------------+--------------+--------------+ 3605 +-----------------------------------------------------------------------+ 3606 | In I Am Assert Loser (L) State | 3607 +----------------+-----------------+-------------------+----------------+ 3608 | AssTrDes | my_metric -> | RPF_interface | Receive | 3609 | (S,G,I) -> | better than | (S) stops | Join(S,G) on | 3610 | FALSE | winner's | being I | interface I | 3611 | | metric | | | 3612 +----------------+-----------------+-------------------+----------------+ 3613 | -> NI state | -> NI state | -> NI state | -> NI State | 3614 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 3615 +----------------+-----------------+-------------------+----------------+ 3617 Note that for reasons of compactness, "AssTrDes(S,G,I)" is used in the 3618 state-machine table to refer to AssertTrackingDesired(S,G,I). 3620 Terminology: 3621 A "preferred assert" is one with a better metric than the current 3622 winner. 3624 An "acceptable assert" is one that has a better metric than 3625 my_assert_metric(S,G,I). 3627 An "inferior assert" is one with a worse metric than 3628 my_assert_metric(S,G,I). 3629 The state machine uses the following macros: 3631 CouldAssert(S,G,I) = 3632 SPTbit(S,G)==TRUE 3633 AND (RPF_interface(S) != I) 3634 AND (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 3635 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3636 (-) lost_assert(*,G) 3637 (+) joins(S,G) (+) pim_include(S,G) ) ) 3639 CouldAssert(S,G,I) is true for downstream interfaces which would be in 3640 the inherited_olist(S,G) if (S,G) assert information was not taken into 3641 account. 3643 AssertTrackingDesired(S,G,I) = 3644 (I in ( ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) 3645 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3646 (-) lost_assert(*,G) 3647 (+) joins(S,G) ) ) 3648 OR (local_receiver_include(S,G,I) == TRUE 3649 AND (I_am_DR(I) OR (AssertWinner(S,G,I) == me))) 3650 OR ((RPF_interface(S) == I) AND (JoinDesired(S,G) == TRUE)) 3651 OR ((RPF_interface(RP(G)) == I) AND (JoinDesired(*,G) == TRUE) 3652 AND (SPTbit(S,G) == FALSE)) 3654 AssertTrackingDesired(S,G,I) is true on any interface in which an (S,G) 3655 assert might affect our behavior. 3657 The first three lines of AssertTrackingDesired account for (*,G) join 3658 and local membership information received on I that might cause the 3659 router to be interested in asserts on I. 3661 The 4th line accounts for (S,G) join information received on I that 3662 might cause the router to be interested in asserts on I. 3664 The 5th and 6th lines account for (S,G) local membership information on 3665 I. Note that we can't use the pim_include(S,G) macro since it uses 3666 lost_assert(S,G,I) and would result in the router forgetting that it 3667 lost an assert if the only reason it was interested was local 3668 membership. The AssertWinner(S,G,I) check forces an assert winner to 3669 keep on being responsible for forwarding as long as local receivers are 3670 present. Removing this check would make the assert winner give up 3671 forwarding as soon as the information that originally caused it to 3672 forward went away and the task of forwarding for local receivers would 3673 revert back to the DR. 3675 The last three lines account for the fact that a router must keep track 3676 of assert information on upstream interfaces in order to send joins and 3677 prunes to the proper neighbor. 3679 Transitions from NoInfo State 3681 When in NoInfo state, the following events may trigger transitions: 3683 Receive Inferior Assert with RPTbit cleared AND 3684 CouldAssert(S,G,I)==TRUE 3685 An assert is received for (S,G) with the RPT bit cleared that 3686 is inferior to our own assert metric. The RPT bit cleared 3687 indicates that the sender of the assert had (S,G) forwarding 3688 state on this interface. If the assert is inferior to our 3689 metric, then we must also have (S,G) forwarding state (i.e. 3690 CouldAssert(S,G,I)==TRUE) as (S,G) asserts beat (*,G) asserts, 3691 and so we should be the assert winner. We transition to the 3692 "I am Assert Winner" state, and perform Actions A1 (below). 3694 Receive Assert with RPTbit set AND CouldAssert(S,G,I)==TRUE 3695 An assert is received for (S,G) on I with the RPT bit set 3696 (it's a (*,G) assert). CouldAssert(S,G,I) is TRUE only if we 3697 have (S,G) forwarding state on this interface, so we should be 3698 the assert winner. We transition to the "I am Assert Winner" 3699 state, and perform Actions A1 (below). 3701 An (S,G) data packet arrives on interface I, AND 3702 CouldAssert(S,G,I)==TRUE 3703 An (S,G) data packet arrived on an downstream interface which 3704 is in our (S,G) outgoing interface list. We optimistically 3705 assume that we will be the assert winner for this (S,G), and 3706 so we transition to the "I am Assert Winner" state, and 3707 perform Actions A1 (below) which will initiate the assert 3708 negotiation for (S,G). 3710 Receive Preferred Assert with RPT bit clear AND 3711 AssertTrackingDesired(S,G,I)==TRUE 3712 We're interested in (S,G) Asserts, either because I is a 3713 downstream interface for which we have (S,G) or (*,G) 3714 forwarding state, or because I is the upstream interface for S 3715 and we have (S,G) forwarding state. The received assert that 3716 has a better metric than our own, so we do not win the Assert. 3717 We transition to "I am Assert Loser" and perform actions A6 3718 (below). 3720 Transitions from "I am Assert Winner" State 3722 When in "I am Assert Winner" state, the following events trigger 3723 transitions: 3725 Assert Timer Expires 3726 The (S,G) Assert Timer expires. As we're in the Winner state, 3727 then we must still have (S,G) forwarding state that is 3728 actively being kept alive. We re-send the (S,G) Assert and 3729 restart the Assert Timer (Action A3 below). Note that the 3730 assert winner's Assert Timer is engineered to expire shortly 3731 before timers on assert losers; this prevents unnecessary 3732 thrashing of the forwarder and periodic flooding of duplicate 3733 packets. 3735 Receive Inferior Assert 3736 We receive an (S,G) assert or (*,G) assert mentioning S that 3737 has a worse metric than our own. Whoever sent the assert is 3738 in error, and so we re-send an (S,G) Assert, and restart the 3739 Assert Timer (Action A3 below). 3741 Receive Preferred Assert 3742 We receive an (S,G) assert that has a better metric than our 3743 own. We transition to "I am Assert Loser" state and perform 3744 actions A2 (below). Note that this may affect the value of 3745 JoinDesired(S,G) and PruneDesired(S,G,rpt) which could cause 3746 transitions in the upstream (S,G) or (S,G,rpt) state machines. 3748 CouldAssert(S,G,I) -> FALSE 3749 Our (S,G) forwarding state or RPF interface changed so as to 3750 make CouldAssert(S,G,I) become false. We can no longer 3751 perform the actions of the assert winner, and so we transition 3752 to NoInfo state and perform actions A4 (below). This includes 3753 sending a "canceling assert" with an infinite metric. 3755 Transitions from "I am Assert Loser" State 3757 When in "I am Assert Loser" state, the following transitions can occur: 3759 Receive Preferred Assert 3760 We receive an assert that is better than that of the current 3761 assert winner. We stay in Loser state, and perform actions A2 3762 below. 3764 Receive Acceptable Assert from Current Winner 3765 We receive an assert from the current assert winner that is 3766 better than our own metric for this (S,G) (although the metric 3767 may be worse than the winner's previous metric). We stay in 3768 Loser state, and perform actions A2 below. 3770 Receive Inferior Assert from Current Winner 3771 We receive an assert from the current assert winner that is 3772 worse than our own metric for this group (typically the 3773 winner's metric became worse). We transition to NoInfo state, 3774 deleting the (S,G) assert information and allowing the normal 3775 PIM Join/Prune mechanisms to operate. Usually we will 3776 eventually re-assert and win when data packets from S have 3777 started flowing again. 3779 Assert Timer Expires 3780 The (S,G) Assert Timer expires. We transition to NoInfo 3781 state, deleting the (S,G) assert information (action A5 3782 below). 3784 Current Winner's GenID Changes 3785 We receive a Hello message from the current winner reporting a 3786 different GenID from the one it previously reported. This 3787 indicates that the current winner's interface or router has 3788 gone down and come back up, and so we must assume it no longer 3789 knows it was the winner. We transition to the NoInfo state, 3790 deleting this (S,G) assert information (action A5 below). 3792 AssertTrackingDesired(S,G,I)->FALSE 3793 AssertTrackingDesired(S,G,I) becomes FALSE. Our forwarding 3794 state has changed so that (S,G) Asserts on interface I are no 3795 longer of interest to us. We transition to the NoInfo state, 3796 deleting the (S,G) assert information. 3798 My metric becomes better than the assert winner's metric 3799 my_assert_metric(S,G,I) has changed so that now my assert 3800 metric for (S,G) is better than the metric we have stored for 3801 current assert winner. This might happen the underlying 3802 routing metric changes, or when CouldAssert(S,G,I) becomes 3803 true; for example, when SPTbit(S,G) becomes true. We 3804 transition to NoInfo state, delete this (S,G) assert state 3805 (action A5 below), and allow the normal PIM Join/Prune 3806 mechanisms to operate. Usually we will eventually re-assert 3807 and win when data packets from S have started flowing again. 3809 RPF_interface(S) stops being interface I 3810 Interface I used to be the RPF interface for S, and now it is 3811 not. We transition to NoInfo state, deleting this (S,G) 3812 assert state (action A5 below). 3814 Receive Join(S,G) on Interface I 3815 We receive a Join(S,G) that has the Upstream Neighbor Address 3816 field set to one my IP address on interface I. The action is 3817 to transition to NoInfo state, and delete this (S,G) assert 3818 state (action A5 below), and allow the normal PIM Join/Prune 3819 mechanisms to operate. If whoever sent the Join was in error, 3820 then the normal assert mechanism will eventually re-apply and 3821 we will lose the assert again. However whoever sent the 3822 assert may know that the previous assert winner has died, and 3823 so we may end up being the new forwarder. 3825 (S,G) Assert State-machine Actions 3827 A1: Send Assert(S,G) 3828 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 3829 Store self as AssertWinner(S,G,I) 3830 Store spt_assert_metric(S,I) as AssertWinnerMetric(S,G,I) 3832 A2: Store new assert winner as AssertWinner(S,G,I) and assert 3833 winner metric as AssertWinnerMetric(S,G,I). 3834 Set Assert Timer to Assert_Time 3836 A3: Send Assert(S,G) 3837 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 3839 A4: Send AssertCancel(S,G) 3840 Delete assert info (AssertWinner(S,G,I) and 3841 AssertWinnerMetric(S,G,I) will then return their default 3842 values). 3844 A5: Delete assert info (AssertWinner(S,G,I) and 3845 AssertWinnerMetric(S,G,I) will then return their default 3846 values). 3848 A6: Store new assert winner as AssertWinner(S,G,I) and assert 3849 winner metric as AssertWinnerMetric(S,G,I). 3850 Set Assert Timer to Assert_Time 3851 If I is RPF_interface(S) set SPTbit(S,G) to TRUE. 3853 Note that some of these actions may cause the value of JoinDesired(S,G), 3854 PruneDesired(S,G,rpt), or RPF'(S,G) to change, which could cause further 3855 transitions in other state machines. 3857 4.6.2. (*,G) Assert Message State Machine 3859 The (*,G) Assert state-machine for interface I is shown in Figure 11. 3860 There are three states: 3862 NoInfo (NI) 3863 This router has no (*,G) assert state on interface I. 3865 I am Assert Winner (W) 3866 This router has won an (*,G) assert on interface I. It is now 3867 responsible for forwarding traffic destined for G onto interface I 3868 with the exception of traffic for which it has (S,G) "I am Assert 3869 Loser" state. Irrespective of whether it is the DR for I, it is 3870 also responsible for handling the membership requests for G from 3871 local hosts on I. 3873 I am Assert Loser (L) 3874 This router has lost an (*,G) assert on interface I. It must not 3875 forward packets for G onto interface I with the exception of 3876 traffic from sources for which is has (S,G) "I am Assert Winner" 3877 state. If it is the DR, it is no longer responsible for handling 3878 the membership requests for group G from local hosts on I. 3880 In addition, there is also an Assert Timer (AT) that is used to time out 3881 asserts on the assert losers and to resend asserts on the assert winner. 3883 When an Assert message is received, a PIM implementation must first 3884 match it against the possible events in the (S,G) assert state machine 3885 and process any transitions and actions, before considering whether the 3886 Assert message matches against the (*,G) assert state machine. 3888 It is important to note that NO TRANSITION CAN OCCUR in the (*,G) state 3889 machine as a result of receiving an Assert message unless the (S,G) 3890 assert state machine for the relevant S and G is in the "NoInfo" state 3891 after the (S,G) state machine has processed the message. Also NO 3892 TRANSITION CAN OCCUR in the (*,G) state machine as a result of receiving 3893 an assert message if that message triggers any change of state in the 3894 (S,G) state machine. 3896 For example, if both the (S,G) and (*,G) assert state machines where in 3897 the NoInfo state when an Assert message arrives, and the message causes 3898 the (S,G) state machine to transition to either "W" or "L" state, then 3899 the assert would not be processed by the (*,G) assert state machine. 3901 Another example: if the (S,G) assert state machine is in "L" state when 3902 an assert message is received, and the assert metric in the message is 3903 worse than my_assert_metric(S,G,I), then the (S,G) assert state machine 3904 will transition to NoInfo state. In such a case if the (*,G) assert 3905 state machine were in NoInfo state, it might appear that it would 3906 transition to "W" state, but this is not the case because this message 3907 already triggered a transition in the (S,G) assert state machine. 3909 Figure 11: Per-interface (*,G) Assert State-machine in tabular form 3911 +-----------------------------------------------------------------------+ 3912 | In NoInfo (NI) State | 3913 +-----------------------+-----------------------+-----------------------+ 3914 | Receive Inferior | Data arrives for G | Receive Preferred | 3915 | Assert with RPTbit | on I and | Assert with RPTbit | 3916 | set and | CouldAssert | set and AssTrDes | 3917 | CouldAssert(*,G,I) | (*,G,I) | (*,G,I) | 3918 +-----------------------+-----------------------+-----------------------+ 3919 | -> W state | -> W state | -> L state | 3920 | [Actions A1] | [Actions A1] | [Actions A2] | 3921 +-----------------------+-----------------------+-----------------------+ 3923 +-----------------------------------------------------------------------+ 3924 | In I Am Assert Winner (W) State | 3925 +----------------+------------------+-----------------+-----------------+ 3926 | Assert Timer | Receive | Receive | CouldAssert | 3927 | Expires | Inferior | Preferred | (*,G,I) -> | 3928 | | Assert | Assert | FALSE | 3929 +----------------+------------------+-----------------+-----------------+ 3930 | -> W state | -> W state | -> L state | -> NI state | 3931 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3932 +----------------+------------------+-----------------+-----------------+ 3934 +-------------------------------------------------------------------------+ 3935 | In I Am Assert Loser (L) State | 3936 +-------------+--------------+--------------+--------------+--------------+ 3937 |Receive | Receive | Receive | Assert Timer | Current | 3938 |Preferred | Acceptable | Inferior | Expires | Winner's | 3939 |Assert | Assert from | Assert from | | GenID | 3940 | | Current | Current | | Changes | 3941 | | Winner | Winner | | | 3942 +-------------+--------------+--------------+--------------+--------------+ 3943 |-> L state | -> L state | -> NI state | -> NI state | -> NI state | 3944 |[Actions A2] | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 3945 +-------------+--------------+--------------+--------------+--------------+ 3946 +-----------------------------------------------------------------------+ 3947 | In I Am Assert Loser (L) State | 3948 +----------------+----------------+------------------+------------------+ 3949 | AssTrDes | my_metric -> | RPF_interface | Receive | 3950 | (*,G,I) -> | better than | (RP(G)) stops | Join(*,G) or | 3951 | FALSE | Winner's | being I | Join- | 3952 | | metric | | (*,*,RP(G)) on | 3953 | | | | Interface I | 3954 +----------------+----------------+------------------+------------------+ 3955 | -> NI state | -> NI state | -> NI state | -> NI State | 3956 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A5] | 3957 +----------------+----------------+------------------+------------------+ 3959 The state machine uses the following macros: 3961 CouldAssert(*,G,I) = 3962 ( I in ( joins(*,*,RP(G)) (+) joins(*,G) 3963 (+) pim_include(*,G)) ) 3964 AND (RPF_interface(RP(G)) != I) 3966 CouldAssert(*,G,I) is true on downstream interfaces for which we have 3967 (*,*,RP(G)) or (*,G) join state, or local members that requested any 3968 traffic destined for G. 3970 AssertTrackingDesired(*,G,I) = 3971 CouldAssert(*,G) 3972 OR (local_receiver_include(*,G,I)==TRUE 3973 AND (I_am_DR(I) OR AssertWinner(*,G,I) == me)) 3974 OR (RPF_interface(RP(G)) == I AND RPTJoinDesired(G)) 3976 AssertTrackingDesired(*,G,I) is true on any interface on which an (*,G) 3977 assert might affect our behavior. 3979 Note that for reasons of compactness, "AssTrDes(*,G,I)" is used in the 3980 state-machine table to refer to AssertTrackingDesired(*,G,I). 3982 Terminology: 3983 A "preferred assert" is one with a better metric than the current 3984 winner. 3986 An "acceptable assert" is one that has a better metric than 3987 my_assert_metric(S,G,I). 3989 An "inferior assert" is one with a worse metric than 3990 my_assert_metric(S,G,I). 3992 Transitions from NoInfo State 3994 When in NoInfo state, the following events trigger transitions, but only 3995 if the (S,G) assert state machine is in NoInfo state: 3997 Receive Inferior Assert with RPTbit set AND 3998 CouldAssert(*,G,I)==TRUE 3999 An Inferior (*,G) assert is received for G on Interface I. If 4000 CouldAssert(*,G,I) is TRUE, then I is our downstream 4001 interface, and we have (*,G) forwarding state on this 4002 interface, so we should be the assert winner. We transition 4003 to the "I am Assert Winner" state, and perform Actions A1 4004 (below). 4006 A data packet destined for G arrives on interface I, AND 4007 CouldAssert(*,G,I)==TRUE 4008 A data packet destined for G arrived on a downstream interface 4009 which is in our (*,G) outgoing interface list. We therefore 4010 believe we should be the forwarder for this (*,G), and so we 4011 transition to the "I am Assert Winner" state, and perform 4012 Actions A1 (below). 4014 Receive Preferred Assert with RPT bit set AND 4015 AssertTrackingDesired(*,G,I)==TRUE 4016 We're interested in (*,G) Asserts, either because I is a 4017 downstream interface for which we have (*,G) forwarding state, 4018 or because I is the upstream interface for RP(G) and we have 4019 (*,G) forwarding state. We get a (*,G) Assert that has a 4020 better metric than our own, so we do not win the Assert. We 4021 transition to "I am Assert Loser" and perform actions A2 4022 (below). 4024 Transitions from "I am Assert Winner" State 4026 When in "I am Assert Winner" state, the following events trigger 4027 transitions, but only if the (S,G) assert state machine is in NoInfo 4028 state: 4030 Receive Inferior Assert 4031 We receive a (*,G) assert that has a worse metric than our 4032 own. Whoever sent the assert has lost, and so we re-send a 4033 (*,G) Assert, and restart the Assert Timer (Action A3 below). 4035 Receive Preferred Assert 4036 We receive a (*,G) assert that has a better metric than our 4037 own. We transition to "I am Assert Loser" state and perform 4038 actions A2 (below). 4040 When in "I am Assert Winner" state, the following events trigger 4041 transitions: 4043 Assert Timer Expires 4044 The (*,G) Assert Timer expires. As we're in the Winner state, 4045 then we must still have (*,G) forwarding state that is 4046 actively being kept alive. To prevent unnecessary thrashing 4047 of the forwarder and periodic flooding of duplicate packets, 4048 we re-send the (*,G) Assert, and restart the Assert Timer 4049 (Action A3 below). 4051 CouldAssert(*,G,I) -> FALSE 4052 Our (*,G) forwarding state or RPF interface changed so as to 4053 make CouldAssert(*,G,I) become false. We can no longer 4054 perform the actions of the assert winner, and so we transition 4055 to NoInfo state and perform actions A4 (below). 4057 Transitions from "I am Assert Loser" State 4059 When in "I am Assert Loser" state, the following events trigger 4060 transitions, but only if the (S,G) assert state machine is in NoInfo 4061 state: 4063 Receive Preferred Assert 4064 We receive a (*,G) assert that is better than that of the 4065 current assert winner. We stay in Loser state, and perform 4066 actions A2 below. 4068 Receive Acceptable Assert from Current Winner 4069 We receive a (*,G) assert from the current assert winner that 4070 is better than our own metric for this group (although the 4071 metric may be worse than the winner's previous metric). We 4072 stay in Loser state, and perform actions A2 below. 4074 Receive Inferior Assert from Current Winner 4075 We receive an assert from the current assert winner that is 4076 worse than our own metric for this group (typically because 4077 the winner's metric became worse). We transition to NoInfo 4078 state, delete this (*,G) assert state (action A5), and allow 4079 the normal PIM Join/Prune mechanisms to operate. Usually we 4080 will eventually re-assert and win when data packets for G have 4081 started flowing again. 4083 When in "I am Assert Loser" state, the following events trigger 4084 transitions: 4086 Assert Timer Expires 4087 The (*,G) Assert Timer expires. We transition to NoInfo state 4088 and delete this (*,G) assert info (action A5). 4090 Current Winner's GenID Changes 4091 We receive a Hello message from the current winner reporting a 4092 different GenID from the one it previously reported. This 4093 indicates that the current winner's interface or router has 4094 gone down and come back up, and so we must assume it no longer 4095 knows it was the winner. We transition to the NoInfo state, 4096 deleting the (*,G) assert information (action A5). 4098 AssertTrackingDesired(*,G,I)->FALSE 4099 AssertTrackingDesired(*,G,I) becomes FALSE. Our forwarding 4100 state has changed so that (*,G) Asserts on interface I are no 4101 longer of interest to us. We transition to NoInfo state and 4102 delete this (*,G) assert info (action A5). 4104 My metric becomes better than the assert winner's metric 4105 My routing metric, rpt_assert_metric(G,I), has changed so that 4106 now my assert metric for (*,G) is better than the metric we 4107 have stored for current assert winner. We transition to 4108 NoInfo state, and delete this (*,G) assert state (action A5), 4109 and allow the normal PIM Join/Prune mechanisms to operate. 4110 Usually we will eventually re-assert and win when data packets 4111 for G have started flowing again. 4113 RPF_interface(RP(G)) stops being interface I 4114 Interface I used to be the RPF interface for RP(G), and now it 4115 is not. We transition to NoInfo state, and delete this (*,G) 4116 assert state (action A5). 4118 Receive Join(*,G) or Join(*,*,RP(G)) on interface I 4119 We receive a Join(*,G) or a Join(*,*,RP(G)) that has the 4120 Upstream Neighbor Address field set to my IP address on 4121 interface I. The action is to transition to NoInfo state, and 4122 delete this (*,G) assert state (action A5), and allow the 4123 normal PIM Join/Prune mechanisms to operate. If whoever sent 4124 the Join was in error, then the normal assert mechanism will 4125 eventually re-apply and we will lose the assert again. 4126 However whoever sent the assert may know that the previous 4127 assert winner has died, and so we may end up being the new 4128 forwarder. 4130 (*,G) Assert State-machine Actions 4132 A1: Send Assert(*,G) 4133 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 4134 Store self as AssertWinner(*,G,I). 4135 Store rpt_assert_metric(G,I) as AssertWinnerMetric(*,G,I). 4137 A2: Store new assert winner as AssertWinner(*,G,I) and assert 4138 winner metric as AssertWinnerMetric(*,G,I). 4139 Set Assert Timer to Assert_Time 4141 A3: Send Assert(*,G) 4142 Set Assert Timer to (Assert_Time - Assert_Override_Interval) 4144 A4: Send AssertCancel(*,G) 4145 Delete assert info (AssertWinner(*,G,I) and 4146 AssertWinnerMetric(*,G,I) will then return their default 4147 values). 4149 A5: Delete assert info (AssertWinner(*,G,I) and 4150 AssertWinnerMetric(*,G,I) will then return their default 4151 values). 4153 Note that some of these actions may cause the value of JoinDesired(*,G) 4154 or RPF'(*,G)) to change, which could cause further transitions in other 4155 state machines. 4157 4.6.3. Assert Metrics 4159 Assert metrics are defined as: 4161 struct assert_metric { 4162 rpt_bit_flag; 4163 metric_preference; 4164 route_metric; 4165 ip_address; 4166 }; 4168 When comparing assert_metrics, the rpt_bit_flag, metric_preference, and 4169 route_metric field are compared in order, where the first lower value 4170 wins. If all fields are equal, the primary IP address of the router 4171 that sourced the Assert message is used as a tie-breaker, with the 4172 highest IP address winning. 4174 An assert metric for (S,G) to include in (or compare against) an Assert 4175 message sent on interface I should be computed using the following 4176 pseudocode: 4178 assert_metric 4179 my_assert_metric(S,G,I) { 4180 if( CouldAssert(S,G,I) == TRUE ) { 4181 return spt_assert_metric(S,I) 4182 } else if( CouldAssert(*,G,I) == TRUE ) { 4183 return rpt_assert_metric(G,I) 4184 } else { 4185 return infinite_assert_metric() 4186 } 4187 } 4189 spt_assert_metric(S,I) gives the assert metric we use if we're sending 4190 an assert based on active (S,G) forwarding state: 4192 assert_metric 4193 spt_assert_metric(S,I) { 4194 return {0,MRIB.pref(S),MRIB.metric(S),my_ip_address(I)} 4195 } 4197 rpt_assert_metric(G,I) gives the assert metric we use if we're sending 4198 an assert based only on (*,G) forwarding state: 4200 assert_metric 4201 rpt_assert_metric(G,I) { 4202 return {1,MRIB.pref(RP(G)),MRIB.metric(RP(G)),my_ip_address(I)} 4203 } 4205 MRIB.pref(X) and MRIB.metric(X) are the routing preference and routing 4206 metrics associated with the route to a particular (unicast) destination 4207 X, as determined by the MRIB. my_ip_address(I) is simply the router's 4208 primary IP address that is associated with the local interface I. 4210 infinite_assert_metric() gives the assert metric we need to send an 4211 assert but don't match either (S,G) or (*,G) forwarding state: 4213 assert_metric 4214 infinite_assert_metric() { 4215 return {1,infinity,infinity,0} 4216 } 4218 4.6.4. AssertCancel Messages 4220 An AssertCancel message is simply an RPT Assert message but with 4221 infinite metric. It is sent by the assert winner when it deletes the 4222 forwarding state that had caused the assert to occur. Other routers 4223 will see this metric, and it will cause any other router that has 4224 forwarding state to send its own assert, and to take over forwarding. 4226 An AssertCancel(S,G) is an infinite metric assert with the RPT bit set 4227 that names S as the source. 4229 An AssertCancel(*,G) is an infinite metric assert with the RPT bit set, 4230 and typically will name RP(G) as the source as it cannot name an 4231 appropriate S. 4233 AssertCancel messages are simply an optimization. The original Assert 4234 timeout mechanism will allow a subnet to eventually become consistent; 4235 the AssertCancel mechanism simply causes faster convergence. No special 4236 processing is required for an AssertCancel message, since it is simply 4237 an Assert message from the current winner. 4239 4.6.5. Assert State Macros 4241 The macros lost_assert(S,G,rpt,I), lost_assert(S,G,I), and 4242 lost_assert(*,G,I) are used in the olist computations of Section 4.1, 4243 and are defined as: 4245 bool lost_assert(S,G,rpt,I) { 4246 if ( RPF_interface(RP(G)) == I OR 4247 ( RPF_interface(S) == I AND SPTbit(S,G) == TRUE ) ) { 4248 return FALSE 4249 } else { 4250 return ( AssertWinner(S,G,I) != NULL AND 4251 AssertWinner(S,G,I) != me ) 4252 } 4253 } 4255 bool lost_assert(S,G,I) { 4256 if ( RPF_interface(S) == I ) { 4257 return FALSE 4258 } else { 4259 return ( AssertWinner(S,G,I) != NULL AND 4260 AssertWinner(S,G,I) != me AND 4261 (AssertWinnerMetric(S,G,I) is better 4262 than spt_assert_metric(S,I) ) 4263 } 4264 } 4266 Note: the term "AssertWinnerMetric(S,G,I) is better than 4267 spt_assert_metric(S,I)" is required to correctly handle the transition 4268 phase when a router has (S,G) join state, but has not yet set the SPT 4269 bit. In this case it needs to ignore the assert state if it will win 4270 the assert once the SPT bit is set. 4272 bool lost_assert(*,G,I) { 4273 if ( RPF_interface(RP(G)) == I ) { 4274 return FALSE 4275 } else { 4276 return ( AssertWinner(*,G,I) != NULL AND 4277 AssertWinner(*,G,I) != me ) 4278 } 4279 } 4281 AssertWinner(S,G,I) is the IP source address of the Assert(S,G) packet 4282 that won an Assert. 4284 AssertWinner(*,G,I) is the IP source address of the Assert(*,G) packet 4285 that won an Assert. 4287 AssertWinnerMetric(S,G,I) is the Assert metric of the Assert(S,G) packet 4288 that won an Assert. 4290 AssertWinnerMetric(*,G,I) is the Assert metric of the Assert(*,G) packet 4291 that won an Assert. 4293 AssertWinner(S,G,I) defaults to NULL and AssertWinnerMetric(S,G,I) 4294 defaults to Infinity when in the NoInfo state. 4296 Summary of Assert Rules and Rationale 4298 This section summarizes the key rules for sending and reacting to 4299 asserts and the rationale for these rules. This section is not intended 4300 to be and should not be treated as a definitive specification of 4301 protocol behavior. The state machines and pseudocode should be 4302 consulted for that purpose. Rather, this section is intended to 4303 document important aspects of a the Assert protocol behavior and to 4304 provide information that may prove helpful to the reader in 4305 understanding and implementing this part of the protocol. 4307 1. Behavior: Downstream neighbors send Join(*,G) and Join(S,G) 4308 periodic messages to the appropriate RPF' neighbor, i.e., the RPF 4309 neighbor as modified by the assert process. They are not always 4310 sent to the RPF neighbor as indicated by the MRIB. Normal 4311 suppression and override rules apply. 4313 Rationale: By sending the periodic and triggered Join messages to 4314 the RPF' neighbor instead of to the RPF neighbor, the downstream 4315 router avoids re-triggering the Assert process with every Join. A 4316 side effect of sending Joins to the Assert winner is that traffic 4317 will not switch back to the "normal" RPF neighbor until the Assert 4318 times out. This will not happen until data stops flowing, if item 4319 8 below is implemented. 4321 2. Behavior: The assert winner for (*,G) acts as the local DR for 4322 (*,G) on behalf of IGMP/MLD members. 4324 Rationale: This is required to allow a single router to merge PIM 4325 and IGMP/MLD joins and leaves. Without this, overrides don't work. 4327 3. Behavior: The assert winner for (S,G) acts as the local DR for 4328 (S,G) on behalf of IGMPv3 members. 4330 Rationale: Same rationale as for 2. 4332 4. Behavior: (S,G) and (*,G) prune overrides are sent to the RPF' 4333 neighbor and not to the regular RPF neighbor. 4335 Rationale: Same as for 1. 4337 5. Behavior: An (S,G,rpt) prune override is not sent (at all) if 4338 RPF'(S,G,rpt) != RPF'(*,G). 4340 Rationale: This avoids keeping state alive on the (S,G) tree when 4341 only (*,G) downstream members are left. Also, it avoids sending 4342 (S,G,rpt) joins to a router that is not on the (*,G) tree. This 4343 behavior might be confusing although this specification does 4344 indicate that such a join should be dropped. 4346 6. Behavior: An assert loser that receives a Join(S,G) with an 4347 Upstream Neighbor Address that is one of its addresses on that 4348 interface cancels the (S,G) Assert Timer. 4350 Rationale: This is necessary in order to have rapid convergence in 4351 the event that the downstream router that initially sent a join to 4352 the prior Assert winner has undergone a topology change. 4354 7. Behavior: An assert loser that receives a Join(*,G) or a 4355 Join(*,*,RP(G)) with an Upstream Neighbor Address that is one of 4356 its addresses on that interface cancels the (*,G) Assert Timer and 4357 all (S,G) assert timers that do not have corresponding 4358 Prune(S,G,rpt) messages in the compound Join/Prune message. 4360 Rationale: Same as 6. 4362 8. Behavior: An assert winner for (*,G) or (S,G) sends a canceling 4363 assert when it is about to stop forwarding on a (*,G) or an (S,G) 4364 entry. This behavior does not apply to (S,G,rpt). 4366 Rationale: This allows switching back to the shared tree after the 4367 last SPT router on the LAN leaves. Doing this prevents downstream 4368 routers on the shared tree from keeping SPT state alive. 4370 9. Behavior: Re-send the assert messages before timing out an assert. 4371 (This behavior is optional.) 4373 Rationale: This prevents the periodic duplicates that would 4374 otherwise occur each time that an assert times out and is then re- 4375 established. 4377 10. Behavior: When RPF'(S,G,rpt) changes to be the same as RPF'(*,G) we 4378 need to trigger a Join(S,G,rpt) to RPF'(*,G). 4380 Rationale: This allows switching back to the RPT after the last SPT 4381 member leaves. 4383 4.7. PIM Multicast Border Router Behavior 4385 In some cases PIM-SM domains will interconnect with non-PIM domains. In 4386 these cases, the border routers of the PIM domain speak PIM-SM on some 4387 interfaces and speak other multicast routing protocols on other 4388 interfaces. Such routers are termed PIM Multicast Border Routers or 4389 PMBRs. In general, RFC 2715 [14] provides rules for interoperability 4390 between different multicast routing protocols. In this section we 4391 specify how PMBRs differ from regular PIM-SM routers. 4393 >From the point of view of PIM-SM, a PMBR has two tasks: 4395 o To ensure that traffic from sources outside the PIM-SM domain reaches 4396 receivers inside the domain. 4398 o To ensure that traffic from sources inside the PIM-SM domain reaches 4399 receivers outside the domain. 4401 We note that multiple PIM-SM domains are sometimes connected together 4402 using protocols such as MSDP, which provides information about active 4403 external sources, but does not follow RFC 2715. In such cases the 4404 domains are not connected via PMBRs because Join(S,G) messages traverse 4405 the border between domains. A PMBR is required when no PIM messages can 4406 traverse the border; typically this is because the routing protocol in 4407 the neighboring domain is not PIM-SM. 4409 4.7.1. Sources External to the PIM-SM Domain 4411 A PMBR needs to ensure that traffic from multicast sources external to 4412 the PIM-SM domain reaches receivers inside the domain. The PMBR will 4413 follow the rules in RFC 2715, such that traffic from external sources 4414 reaches the PMBR itself. 4416 According to RFC 2715, the PIM-SM component of the PMBR will receive an 4417 (S,G) Creation event when data from an (S,G) data packet from an 4418 external source first reaches the PMBR. If RPF_interface(S) is not an 4419 interface in the PIM-SM domain, the packet cannot be originated into the 4420 PIM domain at this router, and the PIM-SM component of the PMBR will not 4421 process the packet. Otherwise the PMBR will then act exactly as if it 4422 were the DR for this source (see Section 4.4.1 with the following 4423 modifications: 4425 o The Border-bit is set in all PIM Register message sent for these 4426 sources. 4428 o DirectlyConnected(S) is treated as being TRUE for these sources. 4430 o The PIM-SM forwarding rule "iif == RPF_interface(S)" is relaxed to be 4431 TRUE if iif is any interface that is not part of the PIM-SM component 4432 of the PMBR (see Section 4.2). 4434 4.7.2. Sources Internal to the PIM-SM Domain 4436 A PMBR needs to ensure that traffic from sources inside the PIM-SM 4437 domain reaches receivers outside the domain. Using terminology from RFC 4438 2715, there are two possible scenarios for this: 4440 o Another component of the PMBR is a wildcard receiver. In this case 4441 the PIM-SM component of the PMBR must ensure that traffic from all 4442 internal sources reaches the PMBR until it is informed otherwise. 4444 o No other component of the PMBR is a wildcard receiver. In this case 4445 the PMBR will receive explicit information as to which groups or 4446 (source,group) pairs the external domains wish to receive. 4448 In the former case, the PMBR will need to issue send a Join(*,*,RP) to 4449 all the RPs in the PIM-SM domain. This will cause all traffic in the 4450 domain to reach the PMBR. The PMBR may then act as if it were a DR with 4451 directly connected receivers, and trigger the transition to a shortest 4452 path tree (see Section 4.2.1). 4454 In the latter case, the PMBR will not need to send Join(*,*,RP) 4455 messages. However the PMBR will still need to act as a DR with directly 4456 connected receivers on behalf of the external receivers in terms of 4457 being able to switch to the shortest-path tree for internally-reached 4458 sources. 4460 According to RFC 2715, the PIM-SM component of the PMBR may receive a 4461 number of alerts generated by events in the external routing components. 4462 To implement the above behavior, one reasonable way to map these alerts 4463 into PIM-SM state as follows: 4465 o When a PIM-SM component receives an (S,G) Prune alert, it sets 4466 local_receiver_include(S,G,I) to FALSE for the discard interface. 4468 o When a PIM-SM component receives a (*,G) Prune alert, it sets 4469 local_receiver_include(*,G,I) to FALSE for the discard interface. 4471 o When a PIM-SM component receives an (S,G) Join alert, it sets 4472 local_receiver_include(S,G,I) to TRUE for the discard interface. 4474 o When a PIM-SM component receives a (*,G) Join alert, it sets 4475 local_receiver_include(*,G,I) to TRUE for the discard interface. 4477 o When a PIM-SM component receives a (*,*) Join alert, it sets 4478 DownstreamJPState(*,*,RP,I) to Join state on the discard interface for 4479 all RPs in the PIM-SM domain. 4481 o When a PIM-SM component receives a (*,*) Prune alert, then it sets 4482 DownstreamJPState(*,*,RP,I) to NoInfo state on the discard interface 4483 for all RPs in the PIM-SM domain. 4485 We refer above to the discard interface because the macros and state- 4486 machines are interface-specific, but we need to have PIM state that is 4487 not associated with any actual PIM-SM interface. Implementors are free 4488 to implement this in any reasonable manner. 4490 Note that these state changes will then cause additional PIM-SM state 4491 machine transitions in the normal way. 4493 These rules are however not sufficent to allow pruning off the (*,*,RP) 4494 tree. Some additional rules provide guidance as to one way this may be 4495 done: 4497 o If the PMBR has joined on the (*,*,RP) tree, then it should set 4498 DownstreamJPState(*,G,I) to TRUE on the discard interface for all 4499 active groups. 4501 o If the router receives a (S,G) prune alert it will need to set 4502 DownstreamJPState(S,G,rpt,I) to PRUNE on the discard interface. 4504 o If the router receives a (*,G) prune alert, it will need to set 4505 DownstreamJPState(S,G,rpt,I) to PRUNE on the discard interface for all 4506 active sources sending to G. 4508 The rationale for this is that there is no way in PIM-SM to prune 4509 traffic off the (*,*,RP) tree, except by Joining the (*,G) tree and then 4510 pruning each source individually. 4512 4.8. PIM Bootstrap and RP Discovery 4514 For correct operation, every PIM router within a PIM domain must be able 4515 to map a particular multicast group address to the same RP. If this is 4516 not the case then black holes may appear, where some receivers in the 4517 domain cannot receive some groups. A domain in this context is a 4518 contiguous set of routers that all implement PIM and are configured to 4519 operate within a common boundary defined by PIM Multicast Border Routers 4520 (PMBRs). PMBRs connect each PIM domain to the rest of the Internet. 4522 A notable exception to this is where a PIM domain is broken up into 4523 multiple administrative scope regions - these are regions where a border 4524 has been configured so that a range of multicast groups will not be 4525 forwarded across that border. For more information on Administratively 4526 Scoped IP Multicast, see RFC 2365. The modified criteria for admin- 4527 scoped regions are that the region is convex with respect to forwarding 4528 based on the MRIB, and that all PIM routers within the scope region map 4529 scoped groups to the same RP within that region. 4531 This specification does not mandate the use of a single mechanism to 4532 provide routers with the information to perform the group-to-RP mapping. 4533 Currently three mechanisms are possible, and all three have associated 4534 problems: 4536 Static Configuration 4537 A PIM router MUST support the static configuration of group-to-RP 4538 mappings. Such a mechanism is not robust to failures, but does at 4539 least provide a basic interoperability mechanism. 4541 Cisco's Auto-RP 4542 Auto-RP uses a PIM Dense-Mode multicast group to announce group-to- 4543 RP mappings from a central location. This mechanism is not useful 4544 if PIM Dense-Mode is not being run in parallel with PIM Sparse- 4545 Mode, and was only intended for use with PIM Sparse-Mode Version 1. 4546 No standard specification currently exists. 4548 BootStrap Router (BSR) 4549 RFC 2362 specifies a bootstrap mechanism based around the automatic 4550 election of a bootstrap router (BSR). Any router in the domain 4551 that is configured to be a possible RP reports its candidacy to the 4552 BSR, and then a domain-wide flooding mechanism distributes the 4553 BSR's chosen set of RPs throughout the domain. As specified in RFC 4554 2362, BSR is flawed in its handling of admin-scoped regions that 4555 are smaller than a PIM domain, but the mechanism does work for 4556 global-scoped groups. 4558 As far as PIM-SM is concerned, the only important requirement is that 4559 all routers in the domain (or admin scope zone for scoped regions) 4560 receive the same set of group-range-to-RP mappings. This may be 4561 achieved through the use of any of these mechanisms, or through 4562 alternative mechanisms not currently specified. 4564 Any RP address configured or learned MUST be a domain-wide reachable 4565 address. 4567 4.8.1. Group-to-RP Mapping 4569 Using one of the mechanisms described above, a PIM router receives one 4570 or more possible group-range-to-RP mappings. Each mapping specifies a 4571 range of multicast groups (expressed as a group and mask) and the RP to 4572 which such groups should be mapped. Each mapping may also have an 4573 associated priority. It is possible to receive multiple mappings all of 4574 which might match the same multicast group - this is the common case 4575 with BSR. The algorithm for performing the group-to-RP mapping is as 4576 follows: 4578 1 Perform longest match on group-range to obtain a list of RPs. 4580 2 From this list of matching RPs, find the one with highest priority. 4581 Eliminate any RPs from the list that have lower priorities. 4583 3 If only one RP remains in the list, use that RP. 4585 4 If multiple RPs are in the list, use the PIM hash function to 4586 choose one. 4588 Thus if two or more group-range-to-RP mappings cover a particular group, 4589 the one with the longest mask is the mapping to use. If the mappings 4590 have the same mask length, then the one with the highest priority is 4591 chosen. If there is more than one matching entry with the same longest 4592 mask and the priorities are identical, then a hash function (see Section 4593 4.8.2) is applied to choose the RP. 4595 This algorithm is invoked by a DR when it needs to determine an RP for a 4596 given group, e.g. upon reception of a packet or IGMP/MLD membership 4597 indication for a group for which the DR does not know the RP. It is 4598 invoked by any router that has (*,*,RP) state when a packet is received 4599 for which there is no corresponding (S,G) or (*,G) entry. Furthermore, 4600 the mapping function is invoked by all routers upon receiving a (*,G) or 4601 (*,*,RP) Join/Prune message. 4603 Note that if the set of possible group-range-to-RP mappings changes, 4604 each router will need to check whether any existing groups are affected. 4605 This may, for example, cause a DR or acting DR to re-join a group, or 4606 cause it to re-start register encapsulation to the new RP. 4608 Implementation note: the bootstrap mechanism described in RFC 4609 2362 omitted step (1) above. However of the implementations 4610 we are are of, approximately half performed step (1) anyway. 4611 It should be noted that implementations of BSR that omit step 4612 1 will not correctly interoperate with implementations of this 4613 specification when used with the BSR mechanism described in 4614 [7]. 4616 4.8.2. Hash Function 4618 The hash function is used by all routers within a domain, to map a group 4619 to one of the RPs from the matching set of group-range-to-RP mappings 4620 (this set all have the same longest mask length and same highest 4621 priority). The algorithm takes as input the group address, and the 4622 addresses of the candidate RPs from the mappings, and gives as output 4623 one RP address to be used. 4625 The protocol requires that all routers hash to the same RP within a 4626 domain (except for transients). The following hash function must be used 4627 in each router: 4629 1 For RP addresses in the matching group-range-to-RP mappings, 4630 compute a value: 4632 Value(G,M,C(i))= 4633 (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31 4635 where C(i) is the RP address and M is a hash-mask. If BSR is being 4636 used, the hash-mask is given in the Bootstrap messages. If BSR is 4637 not being used, the alternative mechanism that supplies the group- 4638 range-to-RP mappings may supply the value, or else it defaults to a 4639 mask with the most significant 30 bits being one for IPv4 and the 4640 most significant 126 bits being one for IPv6. The hash-mask allows 4641 a small number of consecutive groups (e.g., 4) to always hash to 4642 the same RP. For instance, hierarchically-encoded data can be sent 4643 on consecutive group addresses to get the same delay and fate- 4644 sharing characteristics. 4646 For address families other than IPv4, a 32-bit digest to be used as 4647 C(i) and G must first be derived from the actual RP or group 4648 address. Such a digest method must be used consistently throughout 4649 the PIM domain. For IPv6 addresses, we recommend using the 4650 equivalent IPv4 address for an IPv4-compatible address, and the 4651 exclusive-or of each 32-bit segment of the address for all other 4652 IPv6 addresses. For example, the digest of the IPv6 address 4653 3ffe:b00:c18:1::10 would be computed as 0x3ffe0b00 ^ 0x0c180001 ^ 4654 0x00000000 ^ 0x00000010, where ^ represents the exclusive-or 4655 operation. 4657 2 The candidate RP with the highest resulting hash value is then the 4658 RP chosen by this Hash Function. If more than one RP has the same 4659 highest hash value, the RP with the highest IP address is chosen. 4661 4.9. Source-Specific Multicast 4663 The Source-Specific Multicast (SSM) service model [10] can be 4664 implemented with a strict subset of the PIM-SM protocol mechanisms. 4665 Both regular IP Multicast and SSM semantics can coexist on a single 4666 router and both can be implemented using the PIM-SM protocol. A range 4667 of multicast addresses, currently 232.0.0.0/8 in IPv4, is reserved for 4668 SSM, and the choice of semantics is determined by the multicast group 4669 address in both data packets and PIM messages. 4671 4.9.1. Protocol Modifications for SSM destination addresses 4673 The following rules override the normal PIM-SM behavior for a multicast 4674 address G in the SSM reserved range: 4676 o A router MUST NOT send a (*,G) Join/Prune message for any reason. 4678 o A router MUST NOT send an (S,G,rpt) Join/Prune message for any reason. 4680 o A router MUST NOT send a Register message for any packet that is 4681 destined to an SSM address. 4683 o A router MUST NOT forward packets based on (*,G) or (S,G,rpt) state. 4684 The (*,G) and (S,G,rpt) -related state summarization macros are NULL 4685 for any SSM address, for the purposes of packet forwarding. 4687 o A router acting as an RP MUST NOT forward any Register-encapsulated 4688 packet that has an SSM destination address. 4690 The last two rules are present to deal with "legacy" routers unaware of 4691 SSM that may be sending (*,G) and (S,G,rpt) Join/Prunes, or Register 4692 messages for SSM destination addresses. 4694 Additionally: 4696 o A router MAY be configured to advertise itself as a Candidate RP for 4697 an SSM address. If so, it SHOULD respond with a Register-Stop message 4698 to any Register message containing a packet destined for an SSM 4699 address. 4701 o A router MAY optimize out the creation and maintenance of (S,G,rpt) 4702 and (*,G) state for SSM destination addresses -- this state is not 4703 needed for SSM packets. 4705 4.9.2. PIM-SSM-only Routers 4707 An implementor may choose to implement only the subset of PIM Sparse- 4708 Mode that provides SSM forwarding semantics. 4710 A PIM-SSM-only router MUST implement the following portions of this 4711 specification: 4713 o Upstream (S,G) state machine (Section 4.5.7) 4715 o Downstream (S,G) state machine (Section 4.5.3) 4717 o (S,G) Assert state machine (Section 4.6.1) 4719 o Hello messages, neighbor discovery and DR election (Section 4.3) 4721 o Packet forwarding rules (Section 4.2) 4723 A PIM-SSM-only router does not need to implement the following protocol 4724 elements: 4726 o Register state machine (Section 4.4) 4728 o (*,G), (S,G,rpt) and (*,*,RP) Downstream state machines (Sections 4729 4.5.2, 4.5.4, and 4.5.1) 4731 o (*,G), (S,G,rpt), and (*,*,RP) Upstream state machines (Sections 4732 4.5.6, 4.5.8, and 4.5.5) 4734 o (*,G) Assert state machine (Section 4.6.2) 4735 o Bootstrap RP Election (Section 4.8) 4737 o Keepalive Timer 4739 o SptBit (Section 4.2.2) 4741 The Keepalive Timer should be treated as always running and SptBit 4742 should be treated as being always set for an SSM address. Additionally, 4743 the Packet forwarding rules of Section 4.2 can be simplified in a PIM- 4744 SSM-only router: 4746 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { 4747 oiflist = inherited_olist(S,G) 4748 } else if( iif is in inherited_olist(S,G) ) { 4749 send Assert(S,G) on iif 4750 } 4752 oiflist = oiflist (-) iif 4753 forward packet on all interfaces in oiflist 4755 This is nothing more than the reduction of the normal PIM-SM forwarding 4756 rule, with all (S,G,rpt) and (*,G) clauses replaced with NULL. 4758 4.10. PIM Packet Formats 4760 This section describes the details of the packet formats for PIM control 4761 messages. 4763 All PIM control messages have IP protocol number 103. 4765 PIM messages are either unicast (e.g. Registers and Register-Stop), or 4766 multicast with TTL 1 to the `ALL-PIM-ROUTERS' group (e.g. Join/Prune, 4767 Asserts, etc.). The source address used for unicast messages is a 4768 domain-wide reachable address; the source address used for multicast 4769 messages is the link-local address of the interface on which the message 4770 is being sent. 4772 The IPv4 `ALL-PIM-ROUTERS' group is `224.0.0.13'. The IPv6 `ALL-PIM- 4773 ROUTERS' group is `ff02::d'. 4775 0 1 2 3 4776 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 4777 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4778 |PIM Ver| Type | Reserved | Checksum | 4779 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4780 PIM Ver 4781 PIM Version number is 2. 4783 Type Types for specific PIM messages. PIM Types are: 4785 Message Type Destination 4786 --------------------------------------------------------------------------- 4787 0 = Hello Multicast to ALL-PIM-ROUTERS 4788 1 = Register Unicast to RP 4789 2 = Register-Stop Unicast to source of Register packet 4790 3 = Join/Prune Multicast to ALL-PIM-ROUTERS 4791 4 = Bootstrap Multicast to ALL-PIM-ROUTERS 4792 5 = Assert Multicast to ALL-PIM-ROUTERS 4793 6 = Graft (used in PIM-DM only) Multicast to ALL-PIM-ROUTERS 4794 7 = Graft-Ack (used in PIM-DM only) Unicast to source of Graft packet 4795 8 = Candidate-RP-Advertisement Unicast to Domain's BSR 4797 Reserved 4798 Set to zero on transmission. Ignored upon receipt. 4800 Checksum 4801 The checksum is a standard IP checksum, i.e. the 16-bit one's 4802 complement of the one's complement sum of the entire PIM message, 4803 excluding the "Multicast data packet" section of the Register 4804 message. For computing the checksum, the checksum field is zeroed. 4806 For IPv6, the checksum also includes the IPv6 "pseudo-header", as 4807 specified in RFC 2460, Section 8.1 [5]. This "pseudo-header" is 4808 prepended to the PIM header for the purposes of calculating the 4809 checksum. The "Upper-Layer Packet Length" in the pseudo-header is 4810 set to the length of the PIM message. The Next Header value used 4811 in the pseudo-header is 103. If the packet's length is not an 4812 integral number of 16-bit words, the packet is padded with a byte 4813 of zero before performing the checksum. 4815 4.10.1. Encoded Source and Group Address Formats 4817 Encoded-Unicast address 4819 An Encoded-Unicast address takes the following format: 4821 0 1 2 3 4822 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 4823 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4824 | Addr Family | Encoding Type | Unicast Address 4825 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4827 Addr Family 4828 The PIM address family of the `Unicast Address' field of this 4829 address. 4831 Values of 0-127 are as assigned by the IANA for Internet Address 4832 Families in [11]. Values 128-250 are reserved to be assigned by the 4833 IANA for PIM-specific Address Families. Values 251 though 255 are 4834 designated for private use. As there is no assignment authority 4835 for this space, collisions should be expected. 4837 Encoding Type 4838 The type of encoding used within a specific Address Family. The 4839 value `0' is reserved for this field, and represents the native 4840 encoding of the Address Family. 4842 Unicast Address 4843 The unicast address as represented by the given Address Family and 4844 Encoding Type. 4846 Encoded-Group address 4848 Encoded-Group addresses take the following format: 4850 0 1 2 3 4851 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 4852 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4853 | Addr Family | Encoding Type |B| Reserved |Z| Mask Len | 4854 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4855 | Group multicast Address 4856 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4858 Addr Family 4859 described above. 4861 Encoding Type 4862 described above. 4864 [B]idirectional PIM 4865 indicates the group range should use Bidirectional PIM [8]. For 4866 PIM-SM defined in this specification, this bit MUST be zero. 4868 Reserved 4869 Transmitted as zero. Ignored upon receipt. 4871 Admin Scope [Z]one 4872 indicates the group range is an admin scope zone. This is used in 4873 the Bootstrap Router Mechanism [7] only. For all other purposes, 4874 this bit is set to zero and ignored on receipt. 4876 Mask Len 4877 The Mask length field is 8 bits. The value is the number of 4878 contiguous one bits left justified used as a mask which, combined 4879 with the group address, describes a range of groups. It is less 4880 than or equal to the address length in bits for the given Address 4881 Family and Encoding Type. If the message is sent for a single group 4882 then the Mask length must equal the address length in bits for the 4883 given Address Family and Encoding Type. (e.g. 32 for IPv4 native 4884 encoding, 128 for IPv6 native encoding). 4886 Group multicast Address 4887 Contains the group address. 4889 Encoded-Source address 4891 Encoded-Source address takes the following format: 4893 0 1 2 3 4894 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 4895 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4896 | Addr Family | Encoding Type | Rsrvd |S|W|R| Mask Len | 4897 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4898 | Source Address 4899 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... 4901 Addr Family 4902 described above. 4904 Encoding Type 4905 described above. 4907 Reserved 4908 Transmitted as zero, ignored on receipt. 4910 S The Sparse bit is a 1 bit value, set to 1 for PIM-SM. It is used 4911 for PIM version 1 compatibility. 4913 W The WC (or WildCard) bit is a 1 bit value for use with PIM 4914 Join/Prune messages (see Section 4.10.5.1 ). 4916 R The RPT (or Rendezvous Point Tree) bit is a 1 bit value for use 4917 with PIM Join/Prune messages (see Section 4.10.5.1 ). If the WC bit 4918 is 1, the RPT bit MUST be 1. 4920 Mask Len 4921 The mask length field is 8 bits. The value is the number of 4922 contiguous one bits left justified used as a mask which, combined 4923 with the Source Address, describes a source subnet. The mask length 4924 MUST be equal to the mask length in bits for the given Address 4925 Family and Encoding Type (32 for IPv4 native and 128 for IPv6 4926 native). A router SHOULD ignore any messages received with any 4927 other mask length. 4929 Source Address 4930 The source address. 4932 4.10.2. Hello Message Format 4934 It is sent periodically by routers on all interfaces. 4936 0 1 2 3 4937 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 4938 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4939 |PIM Ver| Type | Reserved | Checksum | 4940 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4941 | OptionType | OptionLength | 4942 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4943 | OptionValue | 4944 | ... | 4945 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4946 | . | 4947 | . | 4948 | . | 4949 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4950 | OptionType | OptionLength | 4951 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4952 | OptionValue | 4953 | ... | 4954 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4956 PIM Version, Type, Reserved, Checksum 4957 Described in Section 4.10. 4959 OptionType 4960 The type of the option given in the following OptionValue field. 4962 OptionLength 4963 The length of the OptionValue field in bytes. 4965 OptionValue 4966 A variable length field, carrying the value of the option. 4968 The Option fields may contain the following values: 4970 o OptionType 1: Holdtime 4971 0 1 2 3 4972 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 4973 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4974 | Type = 1 | Length = 2 | 4975 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4976 | Holdtime | 4977 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4979 Holdtime is the amount of time a receiver must keep the neighbor 4980 reachable, in seconds. If the Holdtime is set to `0xffff', the 4981 receiver of this message never times out the neighbor. This may 4982 be used with dial-on-demand links, to avoid keeping the link up 4983 with periodic Hello messages. 4985 Hello messages with a Holdtime value set to `0' are also sent by 4986 a router on an interface about to go down or changing IP address 4987 (see Section 4.3.1). These are effectively goodbye messages and 4988 the receiving routers should immediately time out the neighbor 4989 information for the sender. 4991 o OptionType 2: LAN Prune Delay 4993 0 1 2 3 4994 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 4995 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4996 | Type = 2 | Length = 4 | 4997 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4998 |T| LAN Delay | Override_Interval | 4999 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5001 The LAN_Prune_Delay option is used to tune the prune propagation 5002 delay on multi-access LANs. 5004 The T bit specifies the ability of the sending router to disable 5005 joins suppression. 5007 LAN Delay and Override_Interval are time intervals in units of 5008 milliseconds are are used to tune the value of the 5009 Override_Interval(I) and its derived timer values. Section 4.3.3 5010 describes how these values affect the behavior of a router. 5012 o OptionType 3 to 16: reserved to be defined in future versions of 5013 this document. 5015 o OptionType 18: deprecated and should not be used. 5017 o OptionType 19: DR Priority 5018 0 1 2 3 5019 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 5020 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5021 | Type = 19 | Length = 4 | 5022 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5023 | DR Priority | 5024 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5026 DR Priority is a 32-bit unsigned number and should be considered 5027 in the DR election as described in Section 4.3.2. 5029 o OptionType 20: Generation ID 5031 0 1 2 3 5032 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 5033 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5034 | Type = 20 | Length = 4 | 5035 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5036 | Generation ID | 5037 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5039 Generation ID is a random 32-bit value for the interface on which 5040 the Hello message is sent. The Generation ID is regenerated 5041 whenever PIM forwarding is started or restarted on the interface. 5043 o OptionType 24: Address List 5045 0 1 2 3 5046 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 5047 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5048 | Type = 24 | Length = | 5049 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5050 | Secondary Address 1 (Encoded-Unicast format) | 5051 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5052 ... 5053 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5054 | Secondary Address N (Encoded-Unicast format) | 5055 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5057 The contents of the Address List Hello option are described in 5058 section 4.3.4. 5060 OptionTypes 17 thru 65000 are assigned by the IANA. OptionTypes 5061 65001 through 65535 are reserved for Private Use, as defined in 5062 [13]. 5063 Unknown options may be ignored. The "Holdtime" option MUST be 5064 implemented; the "DR Priority" and "Generation ID" options SHOULD 5065 be implemented. 5067 4.10.3. Register Message Format 5069 A Register message is sent by the DR or a PMBR to the RP when a 5070 multicast packet needs to be transmitted on the RP-tree. The IP source 5071 address is set to the address of the DR, the destination address to the 5072 RP's address. The IP TTL of the PIM packet is the system's normal 5073 unicast TTL. 5075 0 1 2 3 5076 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 5077 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5078 |PIM Ver| Type | Reserved | Checksum | 5079 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5080 |B|N| Reserved2 | 5081 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5082 | | 5083 . Multicast data packet . 5084 | | 5085 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5087 PIM Version, Type, Reserved, Checksum 5088 Described in Section 4.10. Note that in order to reduce 5089 encapsulation overhead, the checksum for Registers is done only on 5090 first 8 bytes of the packet, including the PIM header and the next 5091 4 bytes, excluding the data packet portion. For interoperability 5092 reasons, a message carrying a checksum calculated over the entire 5093 PIM Register message should also be accepted. 5095 B The Border bit. If the router is a DR for a source that it is 5096 directly connected to, it sets the B bit to 0. If the router is a 5097 PMBR for a source in a directly connected cloud, it sets the B bit 5098 to 1. 5100 N The Null-Register bit. Set to 1 by a DR that is probing the RP 5101 before expiring its local Register-Suppression Timer. Set to 0 5102 otherwise. 5104 Reserved2 5105 Transmitted as zero, ignored on receipt. 5107 Multicast data packet 5108 The original packet sent by the source. This packet must be the of 5109 the same address family as the encapsulating PIM packet, e.g. an 5110 IPv6 data packet must be encapsulated in an IPv6 PIM packet. Note 5111 that the TTL of the original packet is decremented before 5112 encapsulation, just like any other packet that is forwarded. In 5113 addition, the RP decrements the TTL after decapsulating, before 5114 forwarding the packet down the shared tree. 5116 For (S,G) Null-Registers, the Multicast data packet portion 5117 contains only a dummy header with S as the source address, G as the 5118 destination address, and a data length of zero. 5120 4.10.4. Register-Stop Message Format 5122 A Register-Stop is unicast from the RP to the sender of the Register 5123 message. The IP source address is the address to which the register was 5124 addressed. The IP destination address is the source address of the 5125 register message. 5127 0 1 2 3 5128 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 5129 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5130 |PIM Ver| Type | Reserved | Checksum | 5131 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5132 | Group Address (Encoded-Group format) | 5133 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5134 | Source Address (Encoded-Unicast format) | 5135 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5137 PIM Version, Type, Reserved, Checksum 5138 Described in Section 4.10. 5140 Group Address 5141 The group address from the multicast data packet in the Register. 5142 Format described in Section 4.10.1. Note that for Register-Stops 5143 the Mask Len field contains the full address length * 8 (e.g. 32 5144 for IPv4 native encoding), if the message is sent for a single 5145 group. 5147 Source Address 5148 The host address of the source from the multicast data packet in 5149 the register. The format for this address is given in the Encoded- 5150 Unicast address in Section 4.10.1. A special wild card value 5151 consisting of an address field of all zeroes can be used to 5152 indicate any source. 5154 4.10.5. Join/Prune Message Format 5156 A Join/Prune message is sent by routers towards upstream sources and 5157 RPs. Joins are sent to build shared trees (RP trees) or source trees 5158 (SPT). Prunes are sent to prune source trees when members leave groups 5159 as well as sources that do not use the shared tree. 5161 0 1 2 3 5162 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 5163 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5164 |PIM Ver| Type | Reserved | Checksum | 5165 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5166 | Upstream Neighbor Address (Encoded-Unicast format) | 5167 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5168 | Reserved | Num groups | Holdtime | 5169 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5170 | Multicast Group Address 1 (Encoded-Group format) | 5171 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5172 | Number of Joined Sources | Number of Pruned Sources | 5173 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5174 | Joined Source Address 1 (Encoded-Source format) | 5175 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5176 | . | 5177 | . | 5178 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5179 | Joined Source Address n (Encoded-Source format) | 5180 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5181 | Pruned Source Address 1 (Encoded-Source format) | 5182 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5183 | . | 5184 | . | 5185 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5186 | Pruned Source Address n (Encoded-Source format) | 5187 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5188 | . | 5189 | . | 5190 | . | 5191 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5192 | Multicast Group Address m (Encoded-Group format) | 5193 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5194 | Number of Joined Sources | Number of Pruned Sources | 5195 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5196 | Joined Source Address 1 (Encoded-Source format) | 5197 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5198 | . | 5199 | . | 5200 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5201 | Joined Source Address n (Encoded-Source format) | 5202 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5203 | Pruned Source Address 1 (Encoded-Source format) | 5204 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5205 | . | 5206 | . | 5207 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5208 | Pruned Source Address n (Encoded-Source format) | 5209 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5211 PIM Version, Type, Reserved, Checksum 5212 Described in Section 4.10. 5214 Unicast Upstream Neighbor Address 5215 The address of the RPF or upstream neighbor. The format for this 5216 address is given in the Encoded-Unicast address in Section 4.10.1. 5217 This address should be the link-local address of the upstream 5218 neighbor, as obtained from the RPF lookup. 5220 Reserved 5221 Transmitted as zero, ignored on receipt. 5223 Holdtime 5224 The amount of time a receiver must keep the Join/Prune state alive, 5225 in seconds. If the Holdtime is set to `0xffff', the receiver of 5226 this message should hold the state until canceled by the 5227 appropriate canceling Join/Prune message, or timed out according to 5228 local policy. This may be used with dial-on-demand links, to avoid 5229 keeping the link up with periodic Join/Prune messages. 5231 Note that the HoldTime must be larger than the 5232 J/P_Override_Interval(I). 5234 Number of Groups 5235 The number of multicast group sets contained in the message. 5237 Multicast group address 5238 For format description see Section 4.10.1. 5240 Number of Joined Sources 5241 Number of join source addresses listed for a given group. 5243 Join Source Address 1 .. n 5244 This list contains the sources that the sending router will forward 5245 multicast datagrams for if received on the interface this message 5246 is sent on. 5248 See Encoded-Source-Address format in Section 4.10.1. 5250 Number of Pruned Sources 5251 Number of prune source addresses listed for a group. 5253 Prune Source Address 1 .. n 5254 This list contains the sources that the sending router does not 5255 want to forward multicast datagrams for when received on the 5256 interface this message is sent on. 5258 Within one PIM Join/Prune message, all the Multicast Group Addresses, 5259 Joined Source addresses and Pruned Source addresses MUST be of the same 5260 address family. It is NOT PERMITTED to mix IPv4 and IPv6 addresses 5261 within the same message. In addition, the address family of the fields 5262 in the message SHOULD be the same as the IP source and destination 5263 addresses of the packet. This permits maximum implementation 5264 flexibility for dual-stack IPv4/IPv6 routers. 5266 4.10.5.1. Group Set Source List Rules 5268 As described above, Join / Prune messages are composed of one or more 5269 group sets. Each set contains two source lists, the Join Sources and the 5270 Prune Sources. This section describes the different types of group sets 5271 and source list entries that can exist in a Join / Prune message. 5273 There are two valid group set types: 5275 Wildcard Group Set 5276 The wildcard group set is represented by the entire multicast range 5277 - the beginning of the multicast address range in the group address 5278 field and the prefix length of the multicast address range in the 5279 mask length field of the Multicast Group Address, e.g. 5280 `224.0.0.0/4' for IPv4 or `ff00::/8' for IPv6. Each wildcard group 5281 set may contain one or more (*,*,RP) source list entries in either 5282 the Join or Prune lists. 5284 A (*,*,RP) source list entry may only exist in a wildcard group 5285 set. When added to a Join source list, this type of source entry 5286 expresses the router's interest in receiving traffic for all groups 5287 mapping to the specified RP. When added to a Prune source list a 5288 (*,*,RP) entry expresses the router's interest to stop receiving 5289 such traffic. Note that as indicated by the Join/Prune state 5290 machines, such a Join or Prune will NOT override Join/Prune state 5291 created using a Group-Specific Set (see below). 5293 (*,*,RP) source list entries have the Source-Address set to the 5294 address of the RP, the Source-Address Mask-Len set to the full 5295 length of the IP address and both the WC and RPT bits of the 5296 Source-Address set to 1. 5298 Group Specific Set 5299 A Group Specific Set is represented by a valid IP multicast address 5300 in the group address field and the full length of the IP address in 5301 the mask length field of the Multicast Group Address. Each group 5302 specific set may contain (*,G), (S,G,rpt) and (S,G) source list 5303 entries in the Join or Prune lists. 5305 (*,G) 5306 The (*,G) source list entry is used in Join / Prune messages 5307 sent towards the RP for the specified group. It expresses 5308 interest (or lack of) in receiving traffic sent to the group 5309 through the Rendezvous-Point shared tree. There may only be 5310 one such entry in both the Join and Prune lists of a group 5311 specific set. 5313 (*,G) source list entries have the Source-Address set to the 5314 address of the RP for group G, the Source-Address Mask-Len set 5315 to the full length of the IP address and have both the WC and 5316 RPT bits of the Encoded-Source-Address set. 5318 (S,G,rpt) 5319 The (S,G,rpt) source list entry is used in Join / Prune 5320 messages sent towards the RP for the specified group. It 5321 expresses interest (or lack of) in receiving traffic through 5322 the shared tree sent by the specified source to this group. 5323 For each source address the entry may exist in only one of the 5324 Join and Prune source lists of a group specific set but not 5325 both. 5327 (S,G,rpt) source list entries have the Source-Address set to 5328 the address of the source S, the Source-Address Mask-Len set 5329 to the full length of the IP address and have the WC bit clear 5330 and the RPT bit set in the Encoded-Source-Address. 5332 (S,G) 5333 The (S,G) source list entry is used in Join / Prune messages 5334 sent towards the specified source. It expresses interest (or 5335 lack of) in receiving traffic through the shortest path tree 5336 sent by the source to the specified group. For each source 5337 address the entry may exist in only one of the Join and Prune 5338 source lists of a group specific set but not both. 5340 (S,G) source list entries have the Source-Address set to the 5341 address of the source S, the Source-Address Mask-Len set to 5342 the full length of the IP address and have both the WC and RPT 5343 bits of the Encoded-Source-Address cleared. 5345 The rules described above are sufficient to prevent invalid combinations 5346 of source list entries in group-specific sets. There are however a 5347 number of combinations that have a valid interpretation but which are 5348 not generated by the protocol as described in this specification: 5350 o Combining a (*,G) Join and a (S,G,rpt) Join entry in the same message 5351 is redundant as the (*,G) entry covers the information provided by the 5352 (S,G,rpt) entry. 5354 o The same applies for a (*,G) Prunes and (S,G,rpt) Prunes. 5356 o The combination of a (*,G) Prune and a (S,G,rpt) Join is also not 5357 generated. (S,G,rpt) Joins are only sent when the router is receiving 5358 all traffic for a group on the shared tree and it wishes to indicate a 5359 change for the particular source. As a (*,G) prune indicates that the 5360 router no longer wishes to receive shared tree traffic, the (S,G,rpt) 5361 Join would be meaningless. 5363 o As Join / Prune messages are targeted to a single PIM neighbor, 5364 including both a (S,G) Join and a (S,G,rpt) prune in the same message 5365 is redundant. The (S,G) Join informs the neighbor that the sender 5366 wishes to receive the particular source on the shortest path tree. It 5367 is therefore unnecessary for the router to say that it no longer 5368 wishes to receive it on the shared tree. 5370 o The combination of a (S,G) Prune and a (S,G,rpt) Join could possibly 5371 be used by a router to switch from receiving a particular source on 5372 the shortest-path tree back to receiving it on the shared tree 5373 (provided that the RPF neighbor for the shortest-path and shared trees 5374 is common). However Sparse-Mode PIM does not provide a mechanism for 5375 switching back to the shared tree. 5377 The rules are summarized in the tables below. 5379 +----------++------+-------+-----------+-----------+-------+-------+ 5380 | ||Join | Prune | Join | Prune | Join | Prune | 5381 | ||(*,G) | (*,G) | (S,G,rpt) | (S,G,rpt) | (S,G) | (S,G) | 5382 +----------++------+-------+-----------+-----------+-------+-------+ 5383 |Join ||- | no | ? | yes | yes | yes | 5384 |(*,G) || | | | | | | 5385 +----------++------+-------+-----------+-----------+-------+-------+ 5386 |Prune ||no | - | ? | ? | yes | yes | 5387 |(*,G) || | | | | | | 5388 +----------++------+-------+-----------+-----------+-------+-------+ 5389 |Join ||? | ? | - | no | yes | yes | 5390 |(S,G,rpt) || | | | | | | 5391 +----------++------+-------+-----------+-----------+-------+-------+ 5392 |Prune ||yes | ? | no | - | ? | ? | 5393 |(S,G,rpt) || | | | | | | 5394 +----------++------+-------+-----------+-----------+-------+-------+ 5395 |Join ||yes | yes | yes | ? | - | no | 5396 |(S,G) || | | | | | | 5397 +----------++------+-------+-----------+-----------+-------+-------+ 5398 |Prune ||yes | yes | yes | ? | no | - | 5399 |(S,G) || | | | | | | 5400 +----------++------+-------+-----------+-----------+-------+-------+ 5402 +---------------++--------------+----------------+------------+ 5403 | ||Join (*,*,RP) | Prune (*,*,RP) | all others | 5404 +---------------++--------------+----------------+------------+ 5405 |Join (*,*,RP) ||- | no | yes | 5406 +---------------++--------------+----------------+------------+ 5407 |Prune (*,*,RP) ||no | - | yes | 5408 +---------------++--------------+----------------+------------+ 5409 |all others ||yes | yes | see above | 5410 +---------------++--------------+----------------+------------+ 5412 yes Allowed and expected. 5414 no Combination is not allowed by the protocol and MUST NOT be 5415 generated by a router. 5417 ? Combination not expected by the protocol, but well-defined. A 5418 router MAY accept it but SHOULD NOT generate it. 5420 The order of source list entries in a group set source list is not 5421 important, except where limited by the packet format itself. 5423 4.10.5.2. Group Set Fragmentation 5425 When building a Join / Prune for a particular neighbor, a router should 5426 try and include in the message as much of the information it needs to 5427 convey to the neighbor as possible. This implies adding one group set 5428 for each multicast group that has information pending transmission and 5429 within each set including all relevant source list entries. 5431 On a router with a large amount of multicast state the number of entries 5432 that must be included may result in packets that are larger in the 5433 maximum IP packet size. In most such cases the information may be split 5434 into multiple messages. 5436 There is an exception with group sets that contain a (*,G) Join source 5437 list entry. The group set expresses the router's interest in receiving 5438 all traffic for the specified group on the shared tree and it MUST 5439 include an (S,G,rpt) Prune source list entry for every source that the 5440 router does not wish to receive. This list of (S,G,rpt) Prune source- 5441 list entries MUST not be split in multiple messages. 5443 If only N (S,G,rpt) Prune entries fit into a maximum-sized Join / Prune 5444 message, but the router has more than N (S,G,rpt) Prunes to add, then 5445 the router MUST choose to include the first N (numerically smallest in 5446 network byte order) IP addresses. 5448 4.10.6. Assert Message Format 5450 The Assert message is used to resolve forwarder conflicts between 5451 routers on a link. It is sent when a multicast data packet is received 5452 on an interface that the router would normally forward that packet. 5453 Assert messages may also be sent in response to an Assert message from 5454 another router. 5456 0 1 2 3 5457 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 5458 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5459 |PIM Ver| Type | Reserved | Checksum | 5460 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5461 | Group Address (Encoded-Group format) | 5462 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5463 | Source Address (Encoded-Unicast format) | 5464 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5465 |R| Metric Preference | 5466 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5467 | Metric | 5468 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 5470 PIM Version, Type, Reserved, Checksum 5471 Described in Section 4.10. 5473 Group Address 5474 The group address for which the router wishes to resolve the 5475 forwarding conflict. This is an Encoded-Group address, as 5476 specified in 4.10.1. 5478 Source Address 5479 Source address for which the router wishes to resolve the 5480 forwarding conflict. The source address MAY be set to INADDR_ANY 5481 for (*,G) asserts (see below). The format for this address is 5482 given in Encoded-Unicast-Address in Section 4.10.1. 5484 R RPT-bit is a 1 bit value. The RPT-bit is set to 1 for Assert(*,G) 5485 messages and 0 for Assert(S,G) messages. 5487 Metric Preference 5488 Preference value assigned to the unicast routing protocol that 5489 provided the route to the multicast source or Rendezvous-Point. 5491 Metric 5492 The unicast routing table metric associated with the route used to 5493 reach the multicast source or Rendezvous-Point. The metric is in 5494 units applicable to the unicast routing protocol used. 5496 Assert messages can be sent to resolve a forwarding conflict for all 5497 traffic to given group or for a specific source and group. 5499 Assert(S,G) 5500 Source specific asserts are sent by routers forwarding a specific 5501 source on the shortest-path tree (SPT bit is TRUE). (S,G) Asserts 5502 have the Group-Address field set to the group G and the Source- 5503 Address field set to the source S. The RPT-bit is set to 0, the 5504 Metric-Preference is set to MRIB.pref(S) and the Metric is set to 5505 MRIB.metric(S). 5507 Assert(*,G) 5508 Group specific asserts are sent by routers forwarding data for the 5509 group and source(s) under contention on the shared tree. (*,G) 5510 asserts have the Group-Address field set to the group G. For data 5511 triggered Asserts the Source-Address field MAY be set to the IP 5512 source address of the data packet that triggered the Assert and is 5513 set to INADDR_ANY otherwise. The RPT-bit is set to 1, the Metric- 5514 Preference is set to MRIB.pref(RP(G)) and the Metric is set to 5515 MRIB.metric(RP(G)). 5517 4.11. PIM Timers 5519 PIM-SM maintains the following timers, as discussed in Section 4.1. All 5520 timers are countdown timers - they are set to a value and count down to 5521 zero, at which point they typically trigger an action. Of course they 5522 can just as easily be implemented as count-up timers, where the absolute 5523 expiry time is stored and compared against a real-time clock, but the 5524 language in this specification assumes that they count downwards to 5525 zero. 5527 Global Timers 5529 Per interface (I): 5531 Hello Timer: HT(I) 5533 Per neighbor (N): 5535 Neighbor Liveness Timer: NLT(N,I) 5537 Per active RP (RP): 5539 (*,*,RP) Join Expiry Timer: ET(*,*,RP,I) 5541 (*,*,RP) Prune-Pending Timer: PPT(*,*,RP,I) 5543 Per Group (G): 5545 (*,G) Join Expiry Timer: ET(*,G,I) 5547 (*,G) Prune-Pending Timer: PPT(*,G,I) 5549 (*,G) Assert Timer: AT(*,G,I) 5551 Per Source (S): 5553 (S,G) Join Expiry Timer: ET(S,G,I) 5555 (S,G) Prune-Pending Timer: PPT(S,G,I) 5557 (S,G) Assert Timer: AT(S,G,I) 5559 (S,G,rpt) Prune Expiry Timer: ET(S,G,rpt,I) 5561 (S,G,rpt) Prune-Pending Timer: PPT(S,G,rpt,I) 5563 Per active RP (RP): 5565 (*,*,RP) Upstream Join Timer: JT(*,*,RP) 5567 Per Group (G): 5569 (*,G) Upstream Join Timer: JT(*,G) 5571 Per Source (S): 5573 (S,G) Upstream Join Timer: JT(S,G) 5575 (S,G) Keepalive Timer: KAT(S,G) 5577 (S,G,rpt) Upstream Override Timer: OT(S,G,rpt) 5579 At the DRs or relevant Assert Winners only: 5581 Per Source,Group pair (S,G): 5583 Register-Stop Timer: RST(S,G) 5585 4.12. Timer Values 5587 When timers are started or restarted, they are set to default values. 5588 This section summarizes those default values. 5590 Note that protocol events or configuration may change the default value 5591 of a timer on a specific interface. When timers are initialized in this 5592 document the value specific to the interface in context must be used. 5594 Some of the timers listed below (Prune-Pending, Upstream Join, Upstream 5595 Override) can be set to values which depend on the settings of the 5596 Propagation Delay and Override_Interval of the corresponding interface. 5597 The default values for these are given below. Note that the value of 5598 both the Propagation Delay and Override Interval of an interface can 5599 change as a result of receiving Hello messages on that interface 5600 (Section 4.3.3). 5602 Variable Name: Propagation_Delay(I) 5604 +--------------------------+-----------------+--------------------------+ 5605 | Value Name | Value | Explanation | 5606 +--------------------------+-----------------+--------------------------+ 5607 | LAN_delay_default | 0.5 sec | Expected | 5608 | | | propagation delay | 5609 | | | over the local | 5610 | | | link. | 5611 +--------------------------+-----------------+--------------------------+ 5613 The default value of the LAN_delay_default is chosen to be relatively 5614 large to provide compatibility with older PIM implementations. 5616 Variable Name: Override_Interval(I) 5618 +--------------------------+-----------------+--------------------------+ 5619 | Value Name | Value | Explanation | 5620 +--------------------------+-----------------+--------------------------+ 5621 | t_override_default | 2.5 sec | Default delay | 5622 | | | interval over | 5623 | | | which to randomize | 5624 | | | when scheduling a | 5625 | | | delayed Join | 5626 | | | message. | 5627 +--------------------------+-----------------+--------------------------+ 5628 Timer Name: Hello Timer (HT(I)) 5630 +----------------------+--------+---------------------------------------+ 5631 |Value Name | Value | Explanation | 5632 +----------------------+--------+---------------------------------------+ 5633 |Hello_Period | 30 sec | Periodic interval for Hello messages. | 5634 +----------------------+--------+---------------------------------------+ 5635 |Triggered_Hello_Delay | 5 sec | Randomized interval for initial Hello | 5636 | | | message on bootup or triggered Hello | 5637 | | | message to a rebooting neighbor. | 5638 +----------------------+--------+---------------------------------------+ 5640 At system power-up, the timer is initialized to rand(0, 5641 Triggered_Hello_Delay) to prevent synchronization. When a new or 5642 rebooting neighbor is detected, a responding Hello is sent within 5643 rand(0, Triggered_Hello_Delay). 5645 Timer Name: Neighbor Liveness Timer (NLT(N,I)) 5647 +--------------------------+-----------------------+--------------------+ 5648 | Value Name | Value | Explanation | 5649 +--------------------------+-----------------------+--------------------+ 5650 | Default_Hello_Holdtime | 3.5 * Hello_Period | Default holdtime | 5651 | | | to keep neighbor | 5652 | | | state alive | 5653 +--------------------------+-----------------------+--------------------+ 5654 | Hello_Holdtime | from message | Holdtime from | 5655 | | | Hello Message | 5656 | | | Holdtime option. | 5657 +--------------------------+-----------------------+--------------------+ 5659 The Holdtime in a Hello Message should be set to (3.5 * Hello_Period), 5660 giving a default value of 105 seconds. 5662 Timer Names: Expiry Timer (ET(*,*,RP,I), ET(*,G,I), ET(S,G,I), 5663 ET(S,G,rpt,I)) 5665 +----------------+-----------------+------------------------------------+ 5666 | Value Name | Value | Explanation | 5667 +----------------+-----------------+------------------------------------+ 5668 | J/P_HoldTime | from message | Holdtime from Join/Prune Message | 5669 +----------------+-----------------+------------------------------------+ 5671 See details of JT(*,G) for the Holdtime that is included in Join/Prune 5672 Messages. 5674 Timer Names: Prune-Pending Timer (PPT(*,*,RP,I), PPT(*,G,I), PPT(S,G,I), 5675 PPT(S,G,rpt,I)) 5677 +----------------------------+-------------------+----------------------+ 5678 | Value Name | Value | Explanation | 5679 +----------------------------+-------------------+----------------------+ 5680 | J/P_Override_Interval(I) | Default: | Short period after | 5681 | | Propagation_- | a join or prune to | 5682 | | Delay(I) + | allow other | 5683 | | Override_- | routers on the LAN | 5684 | | Interval(I) | to override the | 5685 | | | join or prune | 5686 +----------------------------+-------------------+----------------------+ 5688 Note that both the Propagation_Delay(I) and the Override_Interval(I) are 5689 interface specific values that may change when Hello messages are 5690 received. 5692 Timer Names: Assert Timer (AT(*,G,I), AT(S,G,I)) 5694 +---------------------------+----------------------+--------------------+ 5695 | Value Name | Value | Explanation | 5696 +---------------------------+----------------------+--------------------+ 5697 | Assert_Override_Interval | Default: 3 secs | Short interval | 5698 | | | before an assert | 5699 | | | times out where | 5700 | | | the assert winner | 5701 | | | resends an Assert | 5702 | | | message | 5703 +---------------------------+----------------------+--------------------+ 5704 | Assert_Time | Default: 180 secs | Period after last | 5705 | | | assert before | 5706 | | | assert state is | 5707 | | | timed out | 5708 +---------------------------+----------------------+--------------------+ 5710 Note that for historical reasons, the Assert message lacks a Holdtime 5711 field. Thus changing the Assert Time from the default value is not 5712 recommended. 5714 Timer Names: Upstream Join Timer (JT(*,*,RP), JT(*,G), JT(S,G)) 5716 +-------------+--------------------+-------------------------------------+ 5717 |Value Name | Value | Explanation | 5718 +-------------+--------------------+-------------------------------------+ 5719 |t_periodic | Default: 60 secs | Period between Join/Prune Messages | 5720 +-------------+--------------------+-------------------------------------+ 5721 |t_suppressed | rand(1.1 * | Suppression period when someone | 5722 | | t_periodic, 1.4 * | else sends a J/P message so we | 5723 | | t_periodic) when | don't need to do so. | 5724 | | Suppression_- | | 5725 | | Enabled(I) is | | 5726 | | true, 0 otherwise | | 5727 +-------------+--------------------+-------------------------------------+ 5728 |t_override | rand(0, Override_- | Randomized delay to prevent | 5729 | | Interval(I)) | response implosion when sending a | 5730 | | | join message to override someone | 5731 | | | else's Prune message. | 5732 +-------------+--------------------+-------------------------------------+ 5734 t_periodic may be set to take into account such things as the configured 5735 bandwidth and expected average number of multicast route entries for the 5736 attached network or link (e.g., the period would be longer for lower- 5737 speed links, or for routers in the center of the network that expect to 5738 have a larger number of entries). If the Join/Prune-Period is modified 5739 during operation, these changes should be made relatively infrequently 5740 and the router should continue to refresh at its previous Join/Prune- 5741 Period for at least Join/Prune-Holdtime, in order to allow the upstream 5742 router to adapt. 5744 The holdtime specified in a Join/Prune message should be set to (3.5 * 5745 t_periodic). 5747 t_override depends on the Override Interval of the upstream interface 5748 which may change when Hello messages are received. 5750 t_suppressed depends on the Suppression State of the upstream interface 5751 ( 4.3.3) and becomes zero when suppression is disabled. 5753 Timer Name: Upstream Override Timer (OT(S,G,rpt)) 5755 +---------------+---------------------------+---------------------------+ 5756 | Value Name | Value | Explanation | 5757 +---------------+---------------------------+---------------------------+ 5758 | t_override | see Upstream Join Timer | see Upstream Join Timer | 5759 +---------------+---------------------------+---------------------------+ 5761 The upstream Override Timer is only ever set to t_override; this value 5762 is defined in the section on Upstream Join Timers. 5764 Timer Name: Keepalive Timer (KAT(S,G)) 5766 +-----------------------+------------------------+----------------------+ 5767 | Value Name | Value | Explanation | 5768 +-----------------------+------------------------+----------------------+ 5769 | Keepalive_Period | Default: 210 secs | Period after last | 5770 | | | (S,G) data packet | 5771 | | | during which (S,G) | 5772 | | | Join state will be | 5773 | | | maintained even in | 5774 | | | the absence of | 5775 | | | (S,G) Join | 5776 | | | messages. | 5777 +-----------------------+------------------------+----------------------+ 5778 | RP_Keepalive_Period | ( 3 * Register_ | As | 5779 | | Suppression_Time ) | Keepalive_Period, | 5780 | | + Register_ | but at the RP when | 5781 | | Probe_Time | a Register-Stop is | 5782 | | | sent. | 5783 +-----------------------+------------------------+----------------------+ 5784 The normal keepalive period for the KAT(S,G) defaults to 210 seconds. 5785 However at the RP, the keepalive period must be at least the 5786 Register_Suppression_Time or the RP may time out the (S,G) state before 5787 the next Null-Register arrives. Thus the KAT(S,G) is set to 5788 max(Keepalive_Period, RP_Keepalive_Period). 5790 Timer Name: Register-Stop Timer (RST(S,G)) 5792 +---------------------------+----------------------+--------------------+ 5793 |Value Name |Value | Explanation | 5794 +---------------------------+----------------------+--------------------+ 5795 |Register_Suppression_Time |Default: 60 seconds | Period during | 5796 | | | which a DR stops | 5797 | | | sending Register- | 5798 | | | encapsulated data | 5799 | | | to the RP after | 5800 | | | receiving a | 5801 | | | Register-Stop | 5802 | | | message. | 5803 +---------------------------+----------------------+--------------------+ 5804 |Register_Probe_Time |Default: 5 seconds | Time before RST | 5805 | | | expires when a DR | 5806 | | | may send a Null- | 5807 | | | Register to the RP | 5808 | | | to cause it to | 5809 | | | resend a Register- | 5810 | | | Stop message. | 5811 +---------------------------+----------------------+--------------------+ 5813 5. IANA Considerations 5815 5.1. PIM Address Family 5817 The PIM Address Family field was chosen to be 8 bits as a tradeoff 5818 between packet format and use of the IANA assigned numbers. Since when 5819 the PIM packet format was designed only 15 values were assigned for 5820 Address Families, and large numbers of new Address Family values were 5821 not envisioned, 8 bits seemed large enough. However, the IANA assigns 5822 Address Families in a 16-bit field. Therefore, the PIM Address Family 5823 is allocated as follows: 5825 Values 0 through 127 are designated to have the same meaning as 5826 IANA-assigned Address Family Numbers [11]. 5828 Values 128 through 250 are designated to be assigned by the IANA 5829 based upon IESG Approval, as defined in [13]. 5831 Values 251 through 255 are designated for Private Use, as defined 5832 in [13]. 5834 5.2. PIM Hello Options 5836 Values 17 through 65000 are to be assigned by the IANA. Since the space 5837 is large, they may be assigned as First Come First Served as defined in 5838 [13]. Such assignments are valid for one year, and may be renewed. 5839 Permanent assignments require a specification (see "Specification 5840 Required" in [13].) 5842 6. Security Considerations 5844 The IPsec authentication header [12] MAY be used to provide data 5845 integrity protection and groupwise data origin authentication of PIM 5846 protocol messages. Authentication of PIM messages can protect against 5847 unwanted behaviors caused by unauthorized or altered PIM messages. 5849 6.1. Attacks based on forged messages 5851 The extent of possible damage depends on the type of counterfeit 5852 messages accepted. We next consider the impact of possible forgeries, 5853 including forged link-local (Join/Prune, Hello, and Assert) and forged 5854 unicast (Register and Register-Stop) messages. 5856 6.1.1. Forged link-local messages 5858 Join/Prune, Hello, and Assert messages are all sent to the link-local 5859 ALL_PIM_ROUTERS multicast addresses, and thus are not forwarded by a 5860 compliant router. A forged message of this type can only reach a LAN if 5861 it was sent by a local host or if it was allowed onto the LAN by a 5862 compromised or non-compliant router. 5864 1. A forged Join/Prune message can cause multicast traffic to be 5865 delivered to links where there are no legitimate requesters, 5866 potentially wasting bandwidth on that link. A forged leave message 5867 on a multi-access LAN is generally not a significant attack in PIM, 5868 because any legitimately joined router on the LAN would override 5869 the leave with a join before the upstream router stops forwarding 5870 data to the LAN. 5872 2. By forging a Hello message, an unauthorized router can cause 5873 itself to be elected as the designated router on a LAN. The 5874 designated router on a LAN is (in the absence of asserts) 5875 responsible for forwarding traffic to that LAN on behalf of any 5876 local members. The designated router is also responsible for 5877 register-encapsulating to the RP any packets that are originated by 5878 hosts on the LAN. Thus, the ability of local hosts to send and 5879 receive multicast traffic may be compromised by a forged Hello 5880 message. 5882 3. By forging an Assert message on a multi-access LAN, an attacker 5883 could cause the legitimate designated forwarder to stop forwarding 5884 traffic to the LAN. Such a forgery would prevent any hosts 5885 downstream of that LAN from receiving traffic. 5887 6.1.2. Forged unicast messages 5889 Register messages and Register-Stop messages are forwarded by 5890 intermediate routers to their destination using normal IP forwarding. 5891 Without data origin authentication, an attacker who is located anywhere 5892 in the network may be able to forge a Register or Register-Stop message. 5893 We consider the effect of a forgery of each of these messages next. 5895 1 By forging a Register message, an attacker can cause the RP to 5896 inject forged traffic onto the shared multicast tree. 5898 2 By forging a Register-stop message, an attacker can prevent a 5899 legitimate DR from Registering packets to the RP. This can prevent 5900 local hosts on that LAN from sending multicast packets. 5902 The above two PIM messages are not changed by intermediate routers and 5903 need only be examined by the intended receiver. Thus these messages can 5904 be authenticated end-to-end, using AH. Attacks on Register and 5905 Register-Stop messages do not apply to a PIM-SSM-only implementation, as 5906 these messages are not required for PIM-SSM. 5908 6.2. Non-cryptographic Authentication Mechanisms 5910 A PIM router SHOULD provide an option to limit the set of neighbors from 5911 which it will accept Join/Prune, Assert, and Hello messages. Either 5912 static configuration of IP addresses or an IPsec security association 5913 may be used. Furthermore, a PIM router SHOULD NOT accept protocol 5914 messages from a router from which it has not yet received a valid Hello 5915 message. 5917 A Designated Router MUST NOT register-encapsulate a packet and send it 5918 to the RP unless the source address of the packet is a legal address for 5919 the subnet on which the packet was received. Similarly, a Designated 5920 Router SHOULD NOT accept a Register-Stop packet whose IP source address 5921 is not a valid RP address for the local domain. 5923 An implementation SHOULD provide a mechanism to allow an RP to restrict 5924 the range of source addresses from which it accepts Register- 5925 encapsulated packets. 5927 All options that restrict the range of addresses from which packets are 5928 accepted MUST default to allowing all packets. 5930 6.3. Authentication using IPsec 5932 The IPsec [12] transport mode using the Authentication Header (AH) is 5933 the recommended method to prevent the above attacks against PIM. The 5934 specific AH authentication algorithm and parameters, including the 5935 choice of authentication algorithm and the choice of key, are configured 5936 by the network administrator. When IPsec authentication is used, a PIM 5937 router should reject (drop without processing) any unauthorized PIM 5938 protocol messages. 5940 As of this writing, the IPsec anti-replay option does not handle the 5941 case of a Security Association identified by a multicast destination 5942 address. Thus, the anti-replay option currently must be disabled on 5943 these Security Associations. The anti-replay option SHOULD be enabled 5944 on all security associations having a unicast destination address. 5946 To use IPsec, the administrator of a PIM network configures each PIM 5947 router with one or more Security Associations and associated SPI(s) that 5948 are used by senders to sign PIM protocol messages and are used by 5949 receivers to authenticate received PIM protocol messages. This document 5950 does not describe protocols for establishing Security Associations. It 5951 assumes that manual configuration of Security Associations is performed, 5952 but it does not preclude the use of a negotiation protocol such as The 5953 Internet Key Exchange [9] to establish Security Associations. 5955 The following sections describe the Security Associations required to 5956 protect PIM protocol messages. 5958 6.3.1. Protecting link-local multicast messages 5960 The network administrator defines a Security Association (SA) and 5961 Security Parameters Index (SPI) that is to be used to authenticate all 5962 link-local PIM protocol messages (Hello, Join/Prune, and Assert) on each 5963 link in a PIM domain. All link-local PIM protocol messages use SPI 0. 5965 The Security Policy Database at a PIM router should be configured to 5966 ensure that all incoming and outgoing Join/Prune, Assert, and Hello 5967 packets use the SA associated with the interface to which the packet is 5968 sent. 5970 Note that, according to [12] there is nominally a different Security 5971 Association Database (SAD) for each router interface. Thus, the 5972 selected Security Association for an inbound PIM packet can vary 5973 depending on the interface on which the packet arrived. This fact 5974 allows the network administrator to use different authentication methods 5975 for each link, even though the destination address is the same for all 5976 link-local PIM packets, regardless of interface. 5978 6.3.2. Protecting unicast messages 5980 IPSec can also be used to provide data origin authentication and data 5981 integrity protection for the Register and Register-Stop unicast 5982 messages. 5984 6.3.2.1. Register messages 5986 The Security Policy Database at every PIM router is configured to select 5987 a Security Association to use when sending PIM Register packets to each 5988 rendezvous point. 5990 In the most general mode of operation, the Security Policy Database at 5991 each DR is configured to select a unique SA and SPI for traffic sent to 5992 each RP. This allows each DR to have a different authentication 5993 algorithm and key to talk to the RP. However, this creates a daunting 5994 key management and distribution problem for the network administrator. 5995 Therefore, it may be preferable in PIM domains where all Designated 5996 Routers are under a single administrative control, to use the same 5997 authentication algorithm parameters (including the key) for all 5998 Registered packets in a domain, regardless of who is the RP and 5999 regardless of who is the DR. 6001 In this "single shared key" mode of operation, the network administrator 6002 must choose an SPI for each DR that will be used to send it PIM protocol 6003 packets. The Security Policy Database at every DR is configured to 6004 select a Security Association (including the authentication algorithm, 6005 authentication parameters, and this SPI) when sending Register messages 6006 to this RP. 6008 By using a single authentication algorithm and associated parameters, 6009 the key distribution problem is simplified. Note however, that this 6010 method has the property that, in order to change the authentication 6011 method or authentication key used, all routers in the domain must be 6012 updated. 6014 6.3.2.2. Register-Stop messages 6016 Similarly, the Security Policy Database at each Rendezvous Point should 6017 be configured to choose a Security Association to use when sending 6018 Register-Stop messages. Because Register-Stop messages are unicast to 6019 the destination DR, a different Security Association and a potentially 6020 unique SPI is required for each DR. 6022 In order to simplify the management problem, it may be acceptable to use 6023 the same authentication algorithm and authentication parameters, 6024 regardless of the sending RP and regardless of the destination DR. 6025 Although a unique Security Association is needed for each DR, the same 6026 authentication algorithm and authentication algorithm parameters (secret 6027 key) can be shared by all DRs and by all RPs. 6029 6.4. Denial of Service Attacks 6031 There are a number of possible denial of service attacks against PIM 6032 that can be caused by generating false PIM protocol messages or even by 6033 generating data false traffic. Authenticating PIM protocol traffic 6034 prevents some, but not all of these attacks. Two of the possible 6035 attacks include: 6037 - Sending packets to many different group addresses quickly can be a 6038 denial of service attack in and of itself. This will cause many 6039 register-encapsulated packets, loading the DR, the RP, and the 6040 routers between the DR and the RP. 6042 - Forging Join messages can cause a multicast tree to get set up. A 6043 large number of forged joins can consume router resources and 6044 result in denial of service. 6046 7. Authors' Addresses 6048 Bill Fenner 6049 AT&T Labs - Research 6050 75 Willow Road 6051 Menlo Park, CA 94025 6052 fenner@research.att.com 6054 Mark Handley 6055 ICIR/ICSI 6056 1947 Center St, Suite 600 6057 Berkeley, CA 94708 6058 mjh@icir.org 6060 Hugh Holbrook 6061 Cisco Systems 6062 170 W. Tasman Drive 6063 San Jose, CA 95134 6064 holbrook@cisco.com 6065 Isidor Kouvelas 6066 Cisco Systems 6067 170 W. Tasman Drive 6068 San Jose, CA 95134 6069 kouvelas@cisco.com 6071 8. Acknowledgments 6073 PIM-SM was designed over many years by a large group of people, 6074 including ideas, comments, and corrections from Deborah Estrin, Dino 6075 Farinacci, Ahmed Helmy, David Thaler, Steve Deering, Van Jacobson, C. 6076 Liu, Puneet Sharma, Liming Wei, Tom Pusateri, Tony Ballardie, Scott 6077 Brim, Jon Crowcroft, Paul Francis, Joel Halpern, Horst Hodel, Polly 6078 Huang, Stephen Ostrowski, Lixia Zhang, Girish Chandranmenon, Brian 6079 Haberman, Hal Sandick, Mike Mroz, Garry Kump, Pavlin Radoslavov and Mike 6080 Davison. 6082 Thanks are due to the American Licorice Company, for its obscure but 6083 possibly essential role in the creation of this document. 6085 9. References 6087 [1] T. Bates , R. Chandra , D. Katz , Y. Rekhter, "Multiprotocol 6088 Extensions for BGP-4", RFC 2283 6090 [2] D. Black, "Differentiated Services and Tunnels", RFC 2983. 6092 [3] S.E. Deering, "Host extensions for IP multicasting", RFC 1112, Aug 6093 1989. 6095 [4] S. Deering, W. Fenner, B. Haberman, "Multicast Listener Discovery 6096 (MLD) for IPv6", RFC 2710. 6098 [5] S. Deering, R. Hinden, "Internet Protocol, Version 6 (IPv6) 6099 Specification", RFC 2460. 6101 [6] B. Cain, S. Deering, I. Kouvelas, B. Fenner, A. Thyagarajan, 6102 "Internet Group Management Protocol, Version 3", RFC 3376. 6104 [7] W. Fenner, M. Handley, R. Kermode, D. Thaler, "Bootstrap Router 6105 (BSR) Mechanism for PIM Sparse Mode", draft-ietf-pim-sm-bsr-03.txt, 6106 work in progress. 6108 [8] M. Handley, I. Kouvelas, T. Speakman, L. Vicisano, "Bi-directional 6109 Protocol Independent Multicast", draft-ietf-pim-bidir-04.txt, work 6110 in progress. 6112 [9] D. Harkins , D. Carrell, "The Internet Key Exchange (IKE)", RFC 6113 2409. 6115 [10] H. Holbrook, B. Cain, "Source-Specific Multicast for IP", draft- 6116 holbrook-ssm-00.txt, work in progress. 6118 [11] IANA, "Address Family Numbers", linked from 6119 http://www.iana.org/numbers.html 6121 [12] S. Kent, R. Atkinson, "Security Architecture for the Internet 6122 Protocol.", RFC 2401. 6124 [13] T. Narten , H. Alvestrand, "Guidelines for Writing an IANA 6125 Considerations Section in RFCs", RFC 2434. 6127 [14] D. Thaler, "Interoperability Rules for Multicast Routing 6128 Protocols", RFC 2715. 6130 10. Index 6131 Assert(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .26,126 6132 Assert(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .26,126 6133 AssertCancel(*,G). . . . . . . . . . . . . . . . . . . . . . . . . 94,96 6134 AssertCancel(S,G). . . . . . . . . . . . . . . . . . . . . . . .77,87,96 6135 AssertTimer(*,G,I) . . . . . . . . . . . . . . . . . . . . .16,24,87,130 6136 AssertTimer(S,G,I) . . . . . . . . . . . . . . . . . . . . .18,24,81,130 6137 AssertTrackingDesired(*,G,I) . . . . . . . . . . . . . . . . . .90,91,93 6138 AssertTrackingDesired(S,G,I) . . . . . . . . . . . . . . . . 82,82,84,86 6139 AssertWinner(*,G,I). . . . . . . . . . . . . . . . . . . .21,24,90,93,97 6140 AssertWinner(S,G,I). . . . . . . . . . . . . . . . . . 21,24,82,86,96,97 6141 AssertWinnerMetric(*,G,I). . . . . . . . . . . . . . . . . . . . . 93,97 6142 AssertWinnerMetric(S,G,I). . . . . . . . . . . . . . . . . . . . . 86,97 6143 assert_metric. . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 6144 Assert_Override_Interval . . . . . . . . . . . . . . . . . . . 86,93,130 6145 Assert_Time. . . . . . . . . . . . . . . . . . . . . . . . . . 86,93,130 6146 AT(*,G,I). . . . . . . . . . . . . . . . . . . . . . . .16,24,87,127,130 6147 AT(S,G,I). . . . . . . . . . . . . . . . . . . . . . . .18,24,81,127,130 6148 CheckSwitchToSpt(S,G). . . . . . . . . . . . . . . . . . . . . . . 26,27 6149 CouldAssert(*,G,I) . . . . . . . . . . . . . . . . . . . .88,90,91,92,95 6150 CouldAssert(S,G,I) . . . . . . . . . . . . . . . . . . 81,82,84,85,86,95 6151 CouldRegister(S,G) . . . . . . . . . . . . . . . . . . . . . . . . 37,39 6152 Default_Hello_Holdtime . . . . . . . . . . . . . . . . . . . . . . . 31 6153 DirectlyConnected(S) . . . . . . . . . . . . . . . . . . 26,26,28,39,100 6154 DownstreamJPState(*,*,RP,I). . . . . . . . . . . . . . . . . . . .22,101 6155 DownstreamJPState(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 22 6156 DownstreamJPState(S,G,I) . . . . . . . . . . . . . . . . . . . . . 22,39 6157 DownstreamJPState(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . 23 6158 DR(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6159 dr_is_better(a,b,I). . . . . . . . . . . . . . . . . . . . . . . . 32,32 6160 DR_priority. . . . . . . . . . . . . . . . . . . . . . . . . . . . 31,32 6161 ET(*,*,RP,I) . . . . . . . . . . . . . . . . . . . . . . . 15,43,126,129 6162 ET(*,G,I). . . . . . . . . . . . . . . . . . . . . . . . . 16,47,127,129 6163 ET(S,G,I). . . . . . . . . . . . . . . . . . . . . . . . . 18,51,127,129 6164 ET(S,G,rpt,I). . . . . . . . . . . . . . . . . . . . . .19,54,56,127,129 6165 GenID. . . . . . . . . . . . . . . . . . . 16,17,19,30,61,65,68,70,81,88 6166 Hash_Function. . . . . . . . . . . . . . . . . . . . . . . . . . .13,104 6167 Hello_Holdtime . . . . . . . . . . . . . . . . . . . . . . . . . .31,129 6168 Hello_Period . . . . . . . . . . . . . . . . . . . . . . . . . . .29,129 6169 HT(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29,129 6170 IGMP . . . . . . . . . . . . . . . . . . . . . . . . . .7,9,17,22,98,104 6171 immediate_olist(*,*,RP). . . . . . . . . . . . . . . . . . . . . . 21,61 6172 immediate_olist(*,G) . . . . . . . . . . . . . . . . . . . . . . . 21,66 6173 immediate_olist(S,G) . . . . . . . . . . . . . . . . . . . . . .21,39,70 6174 infinite_assert_metric() . . . . . . . . . . . . . . . . . . . . . . 95 6175 inherited_olist(S,G) . . . . . . . . . . . . . . . . .21,26,41,70,82,107 6176 inherited_olist(S,G,rpt) . . . . . . . . . . . . . . . 21,26,28,74,76,78 6177 Interface_Address_List . . . . . . . . . . . . . . . . . . . . . . . 30 6178 I_Am_Assert_Loser(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 24 6179 I_Am_Assert_Loser(S,G,I) . . . . . . . . . . . . . . . . . . . . . . 24 6180 I_am_DR(I) . . . . . . . . . . . . . . . . . . . . . . . .21,32,39,82,90 6181 I_am_RP(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41,41 6182 J/P_Holdtime . . . . . . . . . . . . . .44,49,52,56,62,67,72,119,129,131 6183 J/P_Override_Interval(I) . . . . . . . . . . . . . . 45,49,52,56,119,130 6184 JoinDesired(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . 61,75 6185 JoinDesired(*,G) . . . . . . . . . . . . . . . . . . . . .17,66,75,82,94 6186 JoinDesired(S,G) . . . . . . . . . . . . . . . . . . . 18,28,70,82,85,87 6187 joins(*,*,RP(G)) . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6188 joins(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . 21,22,82,90 6189 joins(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 21,22,82,90 6190 joins(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . .21,22,82 6191 JT(*,*,RP) . . . . . . . . . . . . . . . . . . . . . . . . 15,59,127,131 6192 JT(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . 16,64,127,131 6193 JT(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . 18,69,127,131 6194 KAT(S,G) . . . . . . . . . . . . . . . .18,25,26,27,39,41,70,107,127,132 6195 KeepaliveTimer(S,G). . . . . . . . . 18,25,26,26,27,39,41,70,107,127,132 6196 Keepalive_Period . . . . . . . . . . . . . . . . . . . . . . . . .26,132 6197 LAN_delay_default. . . . . . . . . . . . . . . . . . . . . . . . .34,128 6198 lan_delay_enabled(I) . . . . . . . . . . . . . . . . . . . . . . . 33,35 6199 LAN_Prune_Delay. . . . . . . . . . . . . . . . . . . . . . . . . . . 30 6200 local_receiver_exclude(S,G,I). . . . . . . . . . . . . . . . . . . . 22 6201 local_receiver_include(*,G,I). . . . . . . . . . . . . . . . . 22,90,101 6202 local_receiver_include(S,G,I). . . . . . . . . . . . . . . . . . . 22,82 6203 local_receiver_include(S,G,I). . . . . . . . . . . . . . . . . . . . 101 6204 lost_assert(*,G) . . . . . . . . . . . . . . . . . . . . . . . .21,23,82 6205 lost_assert(*,G,I) . . . . . . . . . . . . . . . . . . . . . . .21,23,97 6206 lost_assert(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 21,23 6207 lost_assert(S,G,I) . . . . . . . . . . . . . . . . . . . . . . .21,23,96 6208 lost_assert(S,G,rpt) . . . . . . . . . . . . . . . . . . . . . . . . 23 6209 lost_assert(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . . . 23,96 6210 MBGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7,8 6211 MFIB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7,13 6212 MLD. . . . . . . . . . . . . . . . . . . . . . . . . . .7,9,17,22,98,104 6213 MRIB . . . . . . . . . . . . . . .7,8,12,16,19,24,59,62,63,73,95,102,126 6214 MRIB.next_hop(host). . . . . . . . . . . . . . . . . . . . . 24,24,59,61 6215 my_assert_metric(S,G,I). . . . . . . . . . . . . . . . . .82,86,88,90,95 6216 NBR(Interface,IP_address). . . . . . . . . . . . . . . . .25,35,59,61,62 6217 NLT(N,I) . . . . . . . . . . . . . . . . . . . . . . . . . 15,31,126,129 6218 OT(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . 20,74,127,132 6219 Override_Interval(I) . . . . . . . . . . . . . . 14,30,33,35,113,128,130 6220 packet_arrives_on_rp_tunnel(pkt) . . . . . . . . . . . . . . . . . . 41 6221 pim_exclude(S,G) . . . . . . . . . . . . . . . . . . . . . . 21,22,27,82 6222 pim_include(*,G) . . . . . . . . . . . . . . . . . . . 17,21,21,27,82,90 6223 pim_include(S,G) . . . . . . . . . . . . . . . . . . . . .18,21,21,27,82 6224 PPT(*,*,RP,I). . . . . . . . . . . . . . . . . . . . . . . 15,43,126,130 6225 PPT(*,G,I) . . . . . . . . . . . . . . . . . . . . . . . . 16,47,127,130 6226 PPT(S,G,I) . . . . . . . . . . . . . . . . . . . . . . . . 18,51,127,130 6227 PPT(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . .19,54,56,127,130 6228 Propagation_Delay(I) . . . . . . . . . . . . . . . . . . . 30,34,128,130 6229 PruneDesired(S,G,rpt). . . . . . . . . . . . . . . . . . . . 76,77,85,87 6230 prunes(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . .21,23,82 6231 Register-Stop(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 40 6232 Register-Stop(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 41 6233 Register-StopTimer(S,G). . . . . . . . . . . . . . . . . . 37,38,127,133 6234 Register_Probe_Time. . . . . . . . . . . . . . . . . . . . . . 38,42,133 6235 Register_Suppression_Time. . . . . . . . . . . . . . . . . . . 38,42,133 6236 RP(G). . . . . . . . . . . . . . .6,21,24,39,41,47,66,74,82,90,95,98,126 6237 RPF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 6238 RPF'(*,G). . . . . . . . . . . . . . . . . . .24,28,64,65,68,74,75,94,97 6239 RPF'(S,G). . . . . . . . . . . . . . . . . . . . . .24,28,69,74,75,87,97 6240 RPF'(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . 24,74,76,98 6241 RPF_interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6242 RPF_interface(host). . . . . . . . 24,26,28,39,66,67,72,82,90,96,100,107 6243 RPTJoinDesired(G). . . . . . . . . . . . . . . . . . . . . . . .75,78,90 6244 rpt_assert_metric(G,I) . . . . . . . . . . . . . . . . . . . . . . 93,95 6245 RST(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 37,38,127,133 6246 SPTbit(S,G). . . . . . . . . .19,26,28,41,50,71,74,76,82,82,86,87,96,107 6247 spt_assert_metric(S,I) . . . . . . . . . . . . . . . . . . . . .86,95,96 6248 SSM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11,105 6249 Suppression_Enabled(I) . . . . . . . . . . . . . . . . . . . . . .35,131 6250 SwitchToSptDesired(S,G). . . . . . . . . . . . . . . . . . . . .27,27,41 6251 TIB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7,13,25 6252 Triggered_Hello_Delay. . . . . . . . . . . . . . . . . . . . . 29,30,129 6253 t_joinsuppress . . . . . . . . . . . . . . . . . . . . . .61,62,65,67,72 6254 t_override . . . . . . . . . . . . . . . . . . . . . 61,65,70,75,131,132 6255 t_override_default . . . . . . . . . . . . . . . . . . . . . . . .35,128 6256 t_periodic . . . . . . . . . . . . . . . . . . . . . . . . .61,65,70,131 6257 t_suppressed . . . . . . . . . . . . . . . . . . . . .35,62,67,70,72,131 6258 Update_SPTbit(S,G,iif) . . . . . . . . . . . . . . . . . . . . . . 26,28 6259 UpstreamJPState(S,G) . . . . . . . . . . . . . . . . . . . . . . .26,107