idnits 2.17.1 draft-ietf-pim-sm-v2-new-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 1741 instances of too long lines in the document, the longest one being 15 characters in excess of 72. == There are 3 instances of lines with non-RFC6890-compliant IPv4 addresses in the document. If these are example addresses, they should be changed. == There are 5 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 ** 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 1269: '...An RP MAY send a RegisterStop message ...' RFC 2119 keyword, line 3648: '...Option SHOULD be included in every Hel...' RFC 2119 keyword, line 3654: '...r (GenID) Option SHOULD be included in...' RFC 2119 keyword, line 3659: '...ut that neighbor SHOULD be discarded a...' RFC 2119 keyword, line 4175: '...o A router MUST NOT send a (*,G) Join/...' (11 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 4311 has weird spacing: '...' field of th...' == Line 4387 has weird spacing: '...join or prune...' -- 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 (24 November 2000) is 8547 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 3234 -- Looks like a reference, but probably isn't: 'Actions A6' on line 2958 -- Looks like a reference, but probably isn't: 'Actions A3' on line 3245 -- Looks like a reference, but probably isn't: 'Actions A2' on line 3257 -- Looks like a reference, but probably isn't: 'Actions A4' on line 3245 -- Looks like a reference, but probably isn't: 'Actions A5' on line 3268 -- Looks like a reference, but probably isn't: 'Optionally' on line 3613 ** Obsolete normative reference: RFC 2283 (ref. '1') (Obsoleted by RFC 2858) -- Possible downref: Non-RFC (?) normative reference: ref. '4' ** Obsolete normative reference: RFC 2434 (ref. '5') (Obsoleted by RFC 5226) ** Obsolete normative reference: RFC 2401 (ref. '6') (Obsoleted by RFC 4301) -- Possible downref: Normative reference to a draft: ref. '7' == Outdated reference: A later version (-02) exists of draft-ietf-pim-simplekmp-01 -- Possible downref: Normative reference to a draft: ref. '8' == Outdated reference: A later version (-04) exists of draft-holbrook-ssm-00 -- Possible downref: Normative reference to a draft: ref. '9' Summary: 8 errors (**), 0 flaws (~~), 7 warnings (==), 14 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-01.txt Mark Handley/ACIRI 4 Hugh Holbrook/Cisco 5 Isidor Kouvelas/Cisco 6 24 November 2000 7 Expires: May 2001 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 Note on PIM-SM status 48 PIM-SM v2 is currently widely implemented and deployed, but the existing 49 specification in RFC 2362 is insufficient to implement from, and is 50 incorrect in a number of aspects. This document is a complete re-write 51 from RFC 2362, and is intended to obsolete RFC 2362. The authors have 52 attempted to document current practice as far as possible, but a number 53 of cases have arisen where current practice is clearly incorrect, 54 typically leading to traffic being black-holed. In these cases we 55 diverge from current practice, but always in a way that will 56 interoperate successfully with the legacy PIM v2 implementations that we 57 are aware of. 59 Table of Contents 61 1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . 5 62 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 63 2.1. Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . 5 64 2.2. Pseudocode Notation. . . . . . . . . . . . . . . . . . . . . . 6 65 3. PIM-SM Protocol Overview. . . . . . . . . . . . . . . . . . . . . 7 66 4. Protocol Specification. . . . . . . . . . . . . . . . . . . . . . 12 67 4.1. PIM Protocol State . . . . . . . . . . . . . . . . . . . . . . 12 68 4.1.1. General Purpose State . . . . . . . . . . . . . . . . . . . 13 69 4.1.2. (*,*,RP) State. . . . . . . . . . . . . . . . . . . . . . . 14 70 4.1.3. (*,G) State . . . . . . . . . . . . . . . . . . . . . . . . 15 71 4.1.4. (S,G) State . . . . . . . . . . . . . . . . . . . . . . . . 16 72 4.1.5. (S,G,rpt) State . . . . . . . . . . . . . . . . . . . . . . 18 73 4.1.6. State Summarization Macros. . . . . . . . . . . . . . . . . 19 74 4.2. Data Packet Forwarding Rules . . . . . . . . . . . . . . . . . 23 75 4.2.1. Setting and Clearing the (S,G) SPT bit. . . . . . . . . . . 25 76 4.3. PIM Register Messages. . . . . . . . . . . . . . . . . . . . . 27 77 4.3.1. Sending Register Messages from the DR . . . . . . . . . . . 27 78 4.3.2. Receiving Register Messages at the RP . . . . . . . . . . . 29 79 4.4. PIM Join/Prune Messages. . . . . . . . . . . . . . . . . . . . 31 80 4.4.1. Receiving (*,*,RP) Join/Prune Messages. . . . . . . . . . . 31 81 4.4.2. Receiving (*,G) Join/Prune Messages . . . . . . . . . . . . 34 82 4.4.3. Receiving (S,G) Join/Prune Messages . . . . . . . . . . . . 38 83 4.4.4. Receiving (S,G,rpt) Join/Prune Messages . . . . . . . . . . 42 84 4.4.5. Sending (*,*,RP) Join/Prune Messages. . . . . . . . . . . . 47 85 4.4.6. Sending (*,G) Join/Prune Messages . . . . . . . . . . . . . 52 86 4.4.7. Sending (S,G) Join/Prune Messages . . . . . . . . . . . . . 56 87 4.4.8. (S,G,rpt) Periodic Messages . . . . . . . . . . . . . . . . 61 88 4.4.9. State Machine for (S,G,rpt) Triggered 89 Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 90 4.5. PIM Assert Messages. . . . . . . . . . . . . . . . . . . . . . 66 91 4.5.1. (S,G) Assert Message State Machine. . . . . . . . . . . . . 66 92 4.5.2. (*,G) Assert Message State Machine. . . . . . . . . . . . . 73 93 4.5.3. Assert Metrics. . . . . . . . . . . . . . . . . . . . . . . 79 94 4.5.4. AssertCancel Messages . . . . . . . . . . . . . . . . . . . 81 95 4.5.5. Assert State Macros . . . . . . . . . . . . . . . . . . . . 81 96 4.6. Designated Routers (DR) and Hello Messages . . . . . . . . . . 83 97 4.6.1. Sending Hello Messages. . . . . . . . . . . . . . . . . . . 83 98 4.6.2. DR Election . . . . . . . . . . . . . . . . . . . . . . . . 84 99 4.7. PIM Bootstrap and RP Discovery . . . . . . . . . . . . . . . . 86 100 4.7.1. Overview of RP Discovery. . . . . . . . . . . . . . . . . . 86 101 4.7.2. Bootstrap Router Election and RP-Set 102 Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 103 4.7.3. Sending Candidate-RP-Advertisements . . . . . . . . . . . . 92 104 4.7.4. Receiving Candidate-RP-Advertisements at 105 the BSR and Creating the RP-Set. . . . . . . . . . . . . . . . . . 93 106 4.7.5. Receiving and Using the RP-Set. . . . . . . . . . . . . . . 94 107 4.8. Source-Specific Multicast. . . . . . . . . . . . . . . . . . . 95 108 4.8.1. Protocol Modifications for SSM destination 109 addresses. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 110 4.8.2. PIM-SSM-only Routers. . . . . . . . . . . . . . . . . . . . 96 111 4.9. PIM Packet Formats . . . . . . . . . . . . . . . . . . . . . . 97 112 4.9.1. Encoded Source and Group Address Formats. . . . . . . . . . 98 113 4.9.2. Hello Message Format. . . . . . . . . . . . . . . . . . . . 101 114 4.9.3. Register Message Format . . . . . . . . . . . . . . . . . . 104 115 4.9.4. Register-Stop Message Format. . . . . . . . . . . . . . . . 105 116 4.9.5. Join/Prune Message Format . . . . . . . . . . . . . . . . . 105 117 4.9.6. Bootstrap Message Format. . . . . . . . . . . . . . . . . . 109 118 4.9.7. Assert Message Format . . . . . . . . . . . . . . . . . . . 112 119 4.9.8. Candidate-RP-Advertisement Format . . . . . . . . . . . . . 113 120 4.10. PIM Timers. . . . . . . . . . . . . . . . . . . . . . . . . . 114 121 4.11. Timer Values. . . . . . . . . . . . . . . . . . . . . . . . . 116 122 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . . 122 123 5.1. PIM Address Family . . . . . . . . . . . . . . . . . . . . . . 122 124 5.2. PIM Hello Options. . . . . . . . . . . . . . . . . . . . . . . 123 125 6. Security Considerations . . . . . . . . . . . . . . . . . . . . . 123 126 7. Authors' Addresses. . . . . . . . . . . . . . . . . . . . . . . . 123 127 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 124 128 9. References. . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 129 10. Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 130 1. Introduction 132 This document specifies a protocol for efficiently routing multicast 133 groups that may span wide-area (and inter-domain) internets. This 134 protocol is called Protocol Independent Multicast - Sparse Mode (PIM-SM) 135 because, although it may use the underlying unicast routing to provide 136 reverse-path information for multicast tree building, it is not 137 dependent on any particular unicast routing protocol. 139 PIM-SM version 2 was originally specified in RFC 2117, and revised in 140 RFC 2362. This document is intended to obsolete RFC 2362, and to 141 correct a number of deficiencies that have been identified with the way 142 PIM-SM was previously specified. As far as possible, this document 143 specifies the same protocol as RFC 2362, and only diverges from the 144 behavior intended by RFC 2362 when the previously specified behavior was 145 clearly incorrect. Routers implemented according to the specification 146 in this document will be able to successfully interoperate with routers 147 implemented according to RFC 2362. 149 2. Terminology 151 In this document, the key words "MUST", "MUST NOT", "REQUIRED", "SHALL", 152 "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and 153 "OPTIONAL" are to be interpreted as described in RFC 2119 and indicate 154 requirement levels for compliant PIM-SM implementations. 156 2.1. Definitions 158 This specification uses a number of terms to refer to the roles of 159 routers participating in PIM-SM. The following terms have special 160 significance for PIM-SM: 162 Rendezvous Point (RP): 163 An RP is a router that has been configured to be used as the root 164 of the non-source-specific distribution tree for a multicast 165 group. Join messages from receivers for a group are sent towards 166 the RP, and data from senders is sent to the RP so that receivers 167 can discover who the senders are, and start to receive traffic 168 destined for the group. 170 Designated Router (DR): 171 A shared-media LAN like Ethernet may have multiple PIM-SM routers 172 connected to it. If the LAN has directly connected hosts, then a 173 single one of these routers, the DR, will act on behalf of those 174 hosts with respect to the PIM-SM protocol. A single DR is elected 175 per LAN using a simple election process. 177 MRIB Multicast Routing Information Base. This is the multicast | 178 topology table, which is typically derived from the unicast | 179 routing table, or routing protocols such as MBGP that carry | 180 multicast-specific topology information. In PIM-SM this is used | 181 to make decisions regarding where to forward Join/Prune messages. | 183 RPF Neighbor 184 RPF stands for "Reverse Path Forwarding". The RPF Neighbor of a 185 router with respect to an address is the neighbor that the MRIB 186 indicates should be used to forward packets to that address. In 187 the case of a PIM-SM multicast group, the RPF neighbor is the 188 router that a Join message for that group would be directed to, in 189 the absence of modifying Assert state. 191 TIB Tree Information Base. This is the collection of state at a PIM 192 router that has been created by receiving PIM Join/Prune messages, 193 PIM Assert messages, and IGMP information from local hosts. It 194 essentially stores the state of all multicast distribution trees 195 at that router. 197 MFIB Multicast Forwarding Information Base. The TIB holds all the 198 state that is necessary to forward multicast packets at a router. 199 However, although this specification defines forwarding in terms 200 of the TIB, to actually forward packets using the TIB is very 201 inefficient. Instead a real router implementation will normally 202 build an efficient MFIB from the TIB state to perform forwarding. 203 How this is done is implementation-specific, and is not discussed 204 in this document. 206 Upstream 207 Towards the root of the tree. The root of tree may either be the 208 source or the RP depending on the context. 210 Downstream 211 Away from the root of the tree. 213 2.2. Pseudocode Notation 215 We use set notation in several places in this specification. 217 A (+) B 218 is the union of two sets A and B. 220 A (-) B 221 is the elements of set A that are not in set B. 223 NULL 224 is the empty set or list. 226 In addition we use C-like syntax: 228 = denotes assignment of a variable. 230 == denotes a comparison for equality. 232 != denotes a comparison for inequality. 234 Braces { and } are used for grouping. 236 3. PIM-SM Protocol Overview 238 This section provides an overview of PIM-SM behavior. It is intended as 239 an introduction to how PIM-SM works, and is NOT definitive. For the 240 definitive specification, see Section 4. 242 PIM relies on an underlying topology-gathering protocol to populate a 243 routing table with routes. This routing table is called the MRIB or 244 Multicast Routing Information Base. The routes in this table may be 245 taken directly from the unicast routing table, or it may be different 246 and provided by a separate routing protocol such as MBGP [1]. In any 247 event, the routes in the MRIB must represent a multicast-capable path to 248 each subnet. The MRIB is used to determine the path that PIM control 249 messages such as Join messages take to get to the source subnet, and 250 data flows along the reverse path of the Join messages. Thus, in 251 contrast to the unicast RIB where the routes give a path that data 252 packets take to get to each subnet, the MRIB gives reverse-path 253 information, and indicates the path that data packets would take from 254 each subnet to the router that has the MRIB. 256 Like all multicast routing protocols that implement the service model 257 from RFC 1112 [2], PIM-SM must be able to route data packets from 258 sources to receivers without either the sources or receivers knowing a- 259 priori of the existence of the others. This is essentially done in 260 three phases, although as senders and receivers may come and go at any 261 time, all three phases may be occur simultaneously. 263 Phase One: RP Tree 265 In phase one, a multicast receiver expresses its interest in receiving 266 traffic destined for a multicast group. Typically it does this using 267 IGMP [3], but other mechanisms might also serve this purpose. One of 268 the receiver's local routers is elected as the Designated Router (DR) 269 for that subnet. On receiving the receiver's expression of interest, 270 the DR then sends a PIM Join message towards the RP for that multicast 271 group. This Join message is known as a (*,G) Join because it joins 272 group G for all sources to that group. The (*,G) Join travels hop-by- 273 hop towards the RP for the group, and in each router it passes through, | 274 multicast tree state for group G is instantiated. Eventually the (*,G) | 275 Join either reaches the RP, or reaches a router that already has (*,G) | 276 Join state for that group. When many receivers join the group, their | 277 Join messages converge on the RP, and form a distribution tree for group | 278 G that is rooted at the RP. This is known as the RP Tree (RPT), and is | 279 also known as the shared tree because it is shared by all sources | 280 sending to that group. Join messages are resent periodically so long as | 281 the receiver remains in the group. When all receivers on a leaf-network | 282 leave the group, the DR will send a PIM (*,G) Prune message towards the | 283 RP for that multicast group. However if the prune message is not sent | 284 for any reason, the state will eventually time out. | 286 A multicast data sender just starts sending data destined for a 287 multicast group. The sender's local router (DR) takes those data 288 packets, unicast-encapsulates them, and sends them directly to the RP. 289 The RP receives these encapsulated data packets, decapsulates them, and 290 forwards them onto the shared tree. The packets then follow the (*,G) 291 multicast tree state in the routers on the RP Tree, being replicated 292 wherever the RP Tree branches, and eventually reaching all the receivers 293 for that multicast group. The process of encapsulating data packets to 294 the RP is called registering, and the encapsulation packets are known as 295 PIM Register packets. 297 At the end of phase one, multicast traffic is flowing encapsulated to 298 the RP, and then natively over the RP tree to the multicast receivers. 300 Phase Two: Register Stop 302 Register-encapsulation of data packets is inefficient for two reasons: 304 o Encapsulation and decapsulation may be relatively expensive operations 305 for a router to perform, depending on whether or not the router has 306 appropriate hardware for these tasks. 308 o Traveling all the way to the RP, and then back down the shared tree 309 may entail the packets traveling a relatively long distance to reach 310 receivers that are close to the sender. For some applications, this 311 increased latency is undesirable. 313 Although Register-encapsulation may continue indefinitely, for these 314 reasons, the RP will normally choose to switch to native forwarding. To | 315 do this, when the RP receives a register-encapsulated data packet from | 316 source S on group G, it will normally initiate an (S,G) source-specific | 317 Join towards S. This join message travels hop-by-hop towards S, | 318 instantiating (S,G) multicast tree state in the routers along the path. | 319 (S,G) multicast tree state is used only to forward packets for group G | 320 if those packets come from source S. Eventually the Join message | 321 reaches S's subnet or a router that already has (S,G) multicast tree | 322 state, and then packets from S start to flow following the (S,G) tree | 323 state towards the RP. These data packets may also reach routers with | 324 (*,G) state along the path towards the RP - if so, they can short-cut | 325 onto the RP tree at this point. | 327 While the RP is in the process of joining the source-specific tree for 328 S, the data packets will continue being encapsulated to the RP. When 329 packets from S also start to arrive natively at the the RP, the RP will 330 be receiving two copies of each of these packets. At this point, the RP 331 starts to discard the encapsulated copy of these packets, and it sends a 332 Register-Stop message back to S's DR to prevent the DR unnecessarily 333 encapsulating the packets. 335 At the end of phase 2, traffic will be flowing natively from S along a 336 source-specific tree to the RP, and from there along the shared tree to 337 the receivers. Where the two trees intersect, traffic may transfer from 338 the source-specific tree to the RP tree, and so avoid taking a long 339 detour via the RP. 341 It should be noted that a sender may start sending before or after a 342 receiver joins the group, and thus phase two may happen before the 343 shared tree to the receiver is built. 345 Phase 3: Shortest-Path Tree 347 Although having the RP join back towards the source removes the 348 encapsulation overhead, it does not completely optimize the forwarding 349 paths. For many receivers the route via the RP may involve a 350 significant detour when compared with the shortest path from the source 351 to the receiver. 353 To obtain lower latencies, a receiver's DR may optionally initiate a 354 transfer from the shared tree to a source-specific shortest-path tree 355 (SPT). To do this, it issues an (S,G) Join towards S. This 356 instantiates state in the routers along the path to S. Eventually this 357 join either reaches S's subnet, or reaches a router that already has 358 (S,G) state. When this happens, data packets from S start to flow 359 following the (S,G) state until they reach the receiver. 361 At this point the receiver (or a router upstream of the receiver) will 362 be receiving two copies of the data - one from the SPT and one from the 363 RPT. When the first traffic starts to arrive from the SPT, the DR or 364 upstream router starts to drop the packets for G from S that arrive via 365 the RP tree. In addition, it sends an (S,G) prune message towards the 366 RP. This is known as an (S,G,rpt) Prune. The prune message travels 367 hop-by-hop, instantiating state along the path towards the RP indicating 368 that traffic from S for G should NOT be forwarded in this direction. 369 The prune is propagated until it reaches the RP or a router that still 370 needs the traffic from S for other receivers. 372 By now, the receiver will be receiving traffic from S along the 373 shortest-path tree between the receiver and S. In addition, the RP is 374 receiving the traffic from S, but this traffic is no longer reaching the 375 receiver along the RP tree. As far as the receiver is concerned, this 376 is the final distribution tree. 378 Source-specific Joins 380 IGMPv3 permits a receiver to join a group and specify that it only wants 381 to receive traffic for a group if that traffic comes from a particular 382 source. If a receiver does this, and no other receiver on the LAN 383 requires all the traffic for the group, then the DR may omit performing 384 a (*,G) join to set up the shared tree, and instead issue a source- 385 specific (S,G) join only. 387 The range of multicast addresses from 232.0.0.0 to 232.255.255.255 is | 388 currently set aside for source-specific multicast in IPv4. For groups | 389 in this range, receivers should only issue source-specific IGMPv3 joins. | 390 If a PIM router receives a non-source-specific join for a group in this 391 range, it should ignore it, as described in Section 4.8. 393 Source-specific Prunes 395 IGMPv3 also permits a receiver to join a group and specify that it only 396 wants to receive traffic for a group if that traffic does not come from 397 a specific source or sources. In this case, the DR will perform a (*,G) 398 join as normal, but may combine this with an (S,G,rpt) prune for each of 399 the sources the receiver does not wish to receive. 401 Multi-access Transit LANs 403 The overview so far has concerned itself with point-to-point links. 404 However, using multi-access LANs such as Ethernet for transit is not 405 uncommon. This can cause complications for three reasons: 407 o Two or more routers on the LAN may issue (*,G) Joins to different 408 upstream routers on the LAN because they have inconsistent MRIB 409 entries regarding how to reach the RP. Both paths on the RP tree will 410 be set up, causing two copies of all the shared tree traffic to appear 411 on the LAN. 413 o Two or more routers on the LAN may issue (S,G) Joins to different 414 upstream routers on the LAN because they have inconsistent MRIB 415 entries regarding how to reach source S. Both paths on the source- 416 specific tree will be set up, causing two copies of all the traffic 417 from S to appear on the LAN. 419 o A router on the LAN may issue a (*,G) Join to one upstream router on 420 the LAN, and another router on the LAN may issue an (S,G) Join to a 421 different upstream router on the same LAN. Traffic from S may reach 422 the LAN over both the RPT and the SPT. If the receiver behind the 423 downstream (*,G) router doesn't issue an (S,G,rpt) prune, then this 424 condition would persist. 426 All of these problems are caused by there being more than one upstream 427 router with join state for the group or source-group pair. PIM does not 428 prevent such duplicate joins from occurring - instead when duplicate 429 data packets appear on the LAN from different routers, these routers 430 notice this, and then elect a single forwarder. This election is 431 performed using PIM Assert messages, which resolve the problem in favor 432 of the upstream router which has (S,G) state, or if neither or both 433 router has (S,G) state, then in favor of the router with the best metric 434 to the RP for RP trees, or the best metric to the source to source- 435 specific trees. 437 These Assert messages are also received by the downstream routers on the 438 LAN, and these cause subsequent join messages to be sent to the upstream 439 router that won the Assert. 441 RP Discovery 443 PIM-SM routers need to know the address of the RP for each group for 444 which they have (*,G) state. This address is obtained through a 445 bootstrap mechanism. 447 One router in each PIM domain is elected the Bootstrap Router (BSR) 448 through a simple election process. All the routers in the domain that 449 are configured to be candidates to be RPs periodically unicast their 450 candidacy to the BSR. From the candidates, the BSR picks an RP-set, and 451 periodically announces this set in a bootstrap message. Bootstrap 452 messages are flooded hop-by-hop throughout the domain until all routers 453 in the domain know the RP-Set. 455 To map a group to an RP, a router hashes the group address into the RP- 456 set using an order-preserving hash function (one that minimizes changes 457 if the RP set changes). The resulting RP is the one that it uses as the 458 RP for that group. 460 4. Protocol Specification 462 The specification of PIM-SM is broken into several parts: 464 o Section 4.1 details the protocol state stored. 466 o Section 4.2 specifies the data packet forwarding rules. 468 o Section 4.3 specifies the PIM Register generation and processing 469 rules. 471 o Section 4.4 specifies the PIM Join/Prune generation and processing 472 rules. 474 o Section 4.5 specifies the PIM Assert generation and processing rules. 476 o Designated Router (DR) election is specified in Section 4.6. 478 o Section 4.7 specifies the Bootstrap and RP discovery mechanisms. 480 o The subset of PIM required to support Source-Specific Multicast, PIM- 481 SSM, is described in Section 4.8. 483 o PIM packet formats are specified in Section 4.9. 485 o A summary of PIM-SM timers and their default values is given in 486 Section 4.10. 488 4.1. PIM Protocol State 490 This section specifies all the protocol state that a PIM implementation 491 should maintain in order to function correctly. We term this state the 492 Tree Information Base or TIB, as it holds the state of all the multicast | 493 distribution trees at this router. In this specification we define PIM | 494 mechanisms in terms of the TIB. However, only a very simple | 495 implementation would actually implement packet forwarding operations in | 496 terms of this state. Most implementations will use this state to build | 497 a multicast forwarding table, which would then be updated when the | 498 relevant state in the TIB changes. | 500 Although we specify precisely the state to be kept, this does not mean 501 that an implementation of PIM-SM needs to hold the state in this form. 502 This is actually an abstract state definition, which is needed in order 503 to specify the router's behavior. A PIM-SM implementation is free to 504 hold whatever internal state it requires, and will still be conformant 505 with this specification so long as it results in the same externally 506 visible protocol behavior as an abstract router that holds the following 507 state. 509 We divide TIB state into four sections: | 511 (*,*,RP) state | 512 State that maintains per-RP trees, for all groups served by a given | 513 RP. | 515 (*,G) state 516 State that maintains the RP tree for G. 518 (S,G) state 519 State that maintains a source-specific tree for source S and group 520 G. 522 (S,G,rpt) state 523 State that maintains source-specific information about source S on 524 the RP tree for G. For example, if a source is being received on 525 the source-specific tree, it will normally have been pruned off the 526 RP tree. This prune state is (S,G,rpt) state. 528 The state that should be kept is described below. Of course, 529 implementations will only maintain state when it is relevant to 530 forwarding operations - for example, the "NoInfo" state might be assumed 531 from the lack of other state information, rather than being held 532 explicitly. 534 4.1.1. General Purpose State 536 A router holds the following non-group-specific state: 538 Bootstrap State: 540 o Bootstrap Router's IP Address 542 o BSR Priority 544 o Bootstrap Timer (BST) 546 RP Set 548 For each interface: 550 Neighbor State: 552 For each neighbor: 554 o Information from neighbor's Hello 555 o Neighbor's Gen ID. 557 o Neighbor liveness timer (NLT) 559 Designated Router (DR) State: 561 o Designated Router's IP Address 563 o DR's DR Priority 565 Bootstrap state is described in section 4.7, the RP Set is described in 566 section 4.7.5, and Designated Router state is described in section 4.6. 568 4.1.2. (*,*,RP) State 570 For every RP a router keeps the following state: | 572 (*,*,RP) state: | 573 For each interface: | 575 PIM (*,*,RP) Join/Prune State: | 577 o State: One of {"NoInfo" (NI), "Join" (J), | 578 "PrunePending" (PP)} | 580 o Prune Pending Timer (PPT) | 582 o Join/Prune Expiry Timer (ET) | 584 Not interface specific: | 586 o Upstream Join/Prune Timer (JT) | 588 o Last RPF Neighbor towards RP that was used | 590 PIM (*,*,RP) Join/Prune state is the result of receiving PIM (*,*,RP) | 591 Join/Prune messages on this interface, and is specified in section | 592 4.4.1. | 594 The upstream (*,*,RP) Join/Prune timer is used to send out periodic | 595 Join(*,*,RP) messages, and to override Prune(*,*,RP) messages from peers | 596 on an upstream LAN interface. | 598 The last RPF neighbor towards the RP is stored because if the MRIB | 599 changes then the RPF neighbor towards the RP may change. If it does so, | 600 then we need to trigger a new Join(*,*,RP) to the new upstream neighbor | 601 and a Prune(*,*,RP) to the old upstream neighbor. Similarly, if a | 602 router detects through a changed GenID in a Hello message that the | 603 upstream neighbor towards the RP has rebooted, then it should re- | 604 instantiate state by sending a Join(*,*,RP). These mechanisms are | 605 specified in Section 4.4.5. | 607 4.1.3. (*,G) State 609 For every group G a router keeps the following state: 611 (*,G) state: 612 For each interface: 614 Local Membership: 615 State: One of {"NoInfo", "Include"} 617 PIM (*,G) Join/Prune State: 619 o State: One of {"NoInfo" (NI), "Join" (J), 620 "PrunePending" (PP)} 622 o Prune Pending Timer (PPT) 624 o Join/Prune Expiry Timer (ET) 626 (*,G) Assert Winner State 628 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 629 "I won Assert" (W)} 631 o Assert Timer (AT) 633 o Assert winner's IP Address 635 o Assert winner's Assert Metric 637 Not interface specific: 639 o Upstream Join/Prune Timer (JT) 641 o Last RP Used 643 o Last RPF Neighbor towards RP that was used 645 Local membership is the result of the local membership mechanism (such 646 as IGMP) running on that interface. It need not be kept if this router 647 is not the DR on that interface unless this router won a (*,G) assert on 648 this interface for this group, although implementations may optionally 649 keep this state in case they become the DR or assert winner. This 650 information is used by the pim_include(*,G) macro described in section 651 4.1.6. 653 PIM (*,G) Join/Prune state is the result of receiving PIM (*,G) 654 Join/Prune messages on this interface, and is specified in section 655 4.4.2. The state is used by the macros that calculate the outgoing 656 interface list in section 4.1.6, and in the JoinDesired(*,G) macro 657 (defined in section 4.4.6) that is used in deciding whether a Join(*,G) 658 should be sent upstream. 660 (*,G) Assert Winner state is the result of sending or receiving (*,G) 661 assert messages on this interface. It is specified in section 4.5.2. 663 The upstream (*,G) Join/Prune timer is used to send out periodic 664 Join(*,G) messages, and to override Prune(*,G) messages from peers on an 665 upstream LAN interface. 667 The last RP used must be stored because if the RP Set changes (section 668 4.7.5) then state must be torn down and rebuilt for groups whose RP 669 changes. 671 The last RPF neighbor towards the RP is stored because if the MRIB 672 changes then the RPF neighbor towards the RP may change. If it does so, 673 then we need to trigger a new Join(*,G) to the new upstream neighbor and 674 a Prune(*,G) to the old upstream neighbor. Similarly, if a router 675 detects through a changed GenID in a Hello message that the upstream 676 neighbor towards the RP has rebooted, then it should re-instantiate 677 state by sending a Join(*,G). These mechanisms are specified in Section 678 4.4.6. 680 4.1.4. (S,G) State 682 For every source/group pair (S,G) a router keeps the following state: 684 (S,G) state: 686 For each interface: 688 Local Membership: 689 State: One of {"NoInfo", "Include"} 691 PIM (S,G) Join/Prune State: 693 o State: One of {"NoInfo" (NI), "Join" (J), 694 "PrunePending" (PP)} 696 o Prune Pending Timer (PPT) 697 o Join/Prune Expiry Timer (ET) 699 (S,G) Assert Winner State 701 o State: One of {"NoInfo" (NI), "I lost Assert" (L), 702 "I won Assert" (W)} 704 o Assert Timer (AT) 706 o Assert winner's IP Address 708 o Assert winner's Assert Metric 710 Not interface specific: 712 o Upstream (S,G) Join/Prune Timer (JT) 714 o Last RPF Neighbor towards S that was used 716 o SPT bit (indicates (S,G) state is active) 718 o (S,G) KeepAlive Timer (KAT) 720 Local membership is the result of the local source-specific membership 721 mechanism (such as IGMP version 3) running on that interface and 722 specifying that this particular source should be included. As stored 723 here, this state is the resulting state after any IGMPv3 inconsistencies | 724 have been resolved. It need not be kept if this router is not the DR on | 725 that interface unless this router won a (S,G) assert on this interface | 726 for this group. This information is used by the pim_include(S,G) macro | 727 described in section 4.1.6. | 729 PIM (S,G) Join/Prune state is the result of receiving PIM (S,G) 730 Join/Prune messages on this interface, and is specified in section 731 4.4.2. The state is used by the macros that calculate the outgoing 732 interface list in section 4.1.6, and in the JoinDesired(S,G) macro 733 (defined in section 4.4.7) that is used in deciding whether a Join(S,G) 734 should be sent upstream. 736 (S,G) Assert Winner state is the result of sending or receiving (S,G) 737 assert messages on this interface. It is specified in section 4.5.1. 739 The upstream (S,G) Join/Prune timer is used to send out periodic 740 Join(S,G) messages, and to override Prune(S,G) messages from peers on an 741 upstream LAN interface. 743 The last RPF neighbor towards S is stored because if the MRIB changes 744 then the RPF neighbor towards S may change. If it does so, then we need 745 to trigger a new Join(S,G) to the new upstream neighbor and a Prune(S,G) 746 to the old upstream neighbor. Similarly, if the router detects through 747 a changed GenID in a Hello message that the upstream neighbor towards S 748 has rebooted, then it should re-instantiate state by sending a 749 Join(S,G). These mechanisms are specified in Section 4.4.7. 751 The SPTbit is used to indicate whether forwarding is taking place on the 752 (S,G) Shortest Path Tree (SPT) or on the (*,G) tree. A router can have 753 (S,G) state and still be forwarding on (*,G) state during the interval 754 when the source-specific tree is being constructed. When SPTbit is 755 FALSE, only (*,G) forwarding state is used to forward packets from S to 756 G. When SPTbit is TRUE, both (*,G) and (S,G) forwarding state are used. 758 The (S,G) Keepalive Timer is updated by data being forwarded using this 759 (S,G) forwarding state. It is used to keep (S,G) state alive in the 760 absence of explicit (S,G) Joins. Amongst other things, this is 761 necessary for the so-called "turnaround rules" - when the RP uses (S,G) 762 joins to stop encapsulation, and then (S,G) prunes to prevent traffic 763 from unnecessarily reaching the RP. 765 4.1.5. (S,G,rpt) State 767 For every source/group pair (S,G) for which a router also has (*,G) 768 state, it also keeps the following state: 770 (S,G,rpt) state: 772 For each interface: 774 Local Membership: 775 State: One of {"NoInfo", "Exclude"} 777 PIM (S,G,rpt) Join/Prune State: 779 o State: One of {"NoInfo", "Pruned", "PrunePending"} 781 o Prune Pending Timer (PPT) 783 o Join/Prune Expiry Timer (ET) 785 Not interface specific: 787 Upstream (S,G,rpt) Join/Prune State: 789 o State: One of {"NotJoined(*,G)", 790 "NotPruned(S,G,rpt)", "Pruned(S,G,rpt)"} 792 o Override Timer (OT) 794 Local membership is the result of the local source-specific membership 795 mechanism (such as IGMPv3) running on that interface and specifying that 796 although there is (*,G) Include state, this particular source should be 797 excluded. As stored here, this state is the resulting state after any 798 IGMPv3 inconsistencies between LAN members have been resolved. It need | 799 not be kept if this router is not the DR on that interface unless this | 800 router won a (*,G) assert on this interface for this group. This | 801 information is used by the pim_exclude(S,G) macro described in section | 802 4.1.6. 804 PIM (S,G,rpt) Join/Prune state is the result of receiving PIM (S,G,rpt) 805 Join/Prune messages on this interface, and is specified in section 806 4.4.4. The state is used by the macros that calculate the outgoing 807 interface list in section 4.1.6, and in the rules for adding 808 Prune(S,G,rpt) messages to Join(*,G) messages specified in section 809 4.4.8. 811 The upstream (S,G,rpt) Join/Prune state is used along with the Override 812 Timer to send the correct override messages in response to Join/Prune 813 messages sent by upstream peers on a LAN. This state and behavior are 814 specified in section 4.4.9. 816 4.1.6. State Summarization Macros 818 Using this state, we define the following "macro" definitions which we 819 will use in the descriptions of the state machines and pseudocode in the 820 following sections. 822 The most important macros are those that define the outgoing interface 823 list (or "olist") for the relevant state. An olist can be "immediate" 824 if it is built directly from the state of the relevant type. For 825 example, the immediate_olist(S,G) is the olist that would be built if 826 the router only had (S,G) state and no (*,G) or (S,G,rpt) state. In 827 contrast, the "inherited" olist inherits state from other types. For 828 example, the inherited_olist(S,G) is the olist that is relevant for 829 forwarding a packet from S to G using both source-specific and group- 830 specific state. 832 There is no immediate_olist(S,G,rpt) as (S,G,rpt) state is negative | 833 state - it removes interfaces in the (*,G) olist from the olist that is | 834 actually used to forward traffic. The inherited_olist(S,G,rpt) is | 835 therefore the olist that would be used for a packet from S to G | 836 forwarding on the RP tree. It is a strict subset of | 837 immediate_olist(*,G). | 838 Generally speaking, the inherited olists are used for forwarding, and 839 the immediate_olists are used to make decisions about state maintenance. 841 immediate_olist(*,*,RP)= | 842 joins(*,*,RP) | 844 immediate_olist(*,G) = | 845 joins(*,G) (+) pim_include(*,G) (-) lost_assert(*,G) | 846 immediate_olist(S,G) = 847 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) 849 inherited_olist(S,G,rpt) = | 850 ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) ) | 851 (+) ( pim_include(*,G) (-) pim_exclude(S,G)) 852 (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) ) 854 inherited_olist(S,G) = 855 inherited_olist(S,G,rpt) (+) immediate_olist(S,G) 857 The macros pim_include(*,G) and pim_include(S,G) indicate the interfaces 858 to which traffic might be forwarded because of hosts that are local 859 members on that interface. Note that normally only the DR cares about 860 local membership, but when an assert happens, the assert winner takes 861 over responsibility for forwarding traffic to local members that have 862 requested traffic on a group or source/group pair. 864 pim_include(*,G) = 865 { all interfaces I such that: | 866 ( ( I_am_DR( I ) AND lost_assert(*,G,I) == FALSE ) | 867 OR AssertWinner(*,G,I) == me ) 868 AND local_receiver_include(*,G,I) } 870 pim_include(S,G) = 871 { all interfaces I such that: | 872 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) | 873 OR AssertWinner(S,G,I) == me ) 874 AND local_receiver_include(S,G,I) } | 876 pim_exclude(S,G) = | 877 { all interfaces I such that: | 878 ( (I_am_DR( I ) AND lost_assert(S,G,I) == FALSE ) | 879 OR AssertWinner(S,G,I) == me ) | 880 AND local_receiver_exclude(S,G,I) } | 882 The clause "local_receiver_include(S,G,I)" is true if the IGMP module or | 883 other local membership mechanism has determined that there are local | 884 members on interface I that desire to receive traffic sent specifically | 885 by S to G. "local_receiver_include(*,G,I)" is true if the IGMP module | 886 or other local membership mechanism has determined that there are local | 887 members on interface I that desire to receive all traffic sent to G. | 888 "local_receiver_exclude(S,G,I) is true if local_receiver_include(*,G,I) | 889 is true but none of the local members desire to receive traffic from S. | 891 The set "joins(*,*,RP)" is the set of all interfaces on which the router | 892 has received (*,*,RP) Joins: | 894 joins(*,*,RP) = | 895 { all interfaces I such that | 896 DownstreamJPState(*,*,RP,I) is either Joined or | 897 PrunePending } | 899 DownstreamJPState(*,*,RP,I) is the state of the finite state machine in | 900 section 4.4.1. | 902 The set "joins(*,G)" is the set of all interfaces on which the router 903 has received (*,G) Joins: 905 joins(*,G) = 906 { all interfaces I such that 907 DownstreamJPState(*,G,I) is either Joined or PrunePending } 909 DownstreamJPState(*,G,I) is the state of the finite state machine in 910 section 4.4.2. 912 The set "joins(S,G)" is the set of all interfaces on which the router 913 has received (S,G) Joins: 915 joins(S,G) = 916 { all interfaces I such that 917 DownstreamJPState(S,G,I) is either Joined or PrunePending } 919 DownstreamJPState(S,G,I) is the state of the finite state machine in 920 section 4.4.3. 922 The set "prunes(S,G,rpt)" is the set of all interfaces on which the 923 router has received (*,G) joins and (S,G,rpt) prunes. 925 prunes(S,G,rpt) = 926 { all interfaces I such that 927 DownstreamJPState(S,G,I) is Pruned or PruneTmp } 929 The set "lost_assert(*,G)" is the set of all interfaces on which the | 930 router has received (*,G) joins but has lost a (*,G) assert. The macro 931 lost_assert(*,G,I) is defined in Section 4.5.5. 933 lost_assert(*,G) = | 934 { all interfaces I such that 935 lost_assert(*,G,I) == TRUE } 937 The set "lost_assert(S,G,rpt)" is the set of all interfaces on which the | 938 router has received (*,G) joins but has lost an (S,G) assert. The macro 939 lost_assert(S,G,rpt,I) is defined in Section 4.5.5. 941 lost_assert(S,G,rpt) = | 942 { all interfaces I such that 943 lost_assert(S,G,rpt,I) == TRUE } 945 The set "lost_assert(S,G)" is the set of all interfaces on which the | 946 router has received (S,G) joins but has lost an (S,G) assert. The macro 947 lost_assert(S,G,I) is defined in Section 4.5.5. 949 lost_assert(S,G) = | 950 { all interfaces I such that 951 lost_assert(S,G,I) == TRUE } 953 The following pseudocode macro definitions are also used in many places 954 in the specification. Basically RPF' is the RPF neighbor towards an RP 955 or source unless a PIM-Assert has overridden the normal choice of 956 neighbor. 958 neighbor RPF'(*,G) { 959 if ( I_Am_Assert_Loser(*,G,RPF_interface(RP(G))) ) { 960 return AssertWinner(*, G, RPF_interface(RP(G)) ) 961 } else { 962 return MRIB.next_hop( RP(G) ) 963 } 964 } 966 neighbor RPF'(S,G,rpt) { 967 if( I_Am_Assert_Loser(S, G, RPF_interface(RP(G)) ) ) { 968 return AssertWinner(S, G, RPF_interface(RP(G)) ) 969 } else { 970 return RPF'(*,G) 971 } 972 } 973 neighbor RPF'(S,G) { 974 if ( I_Am_Assert_loser(S, G, RPF_interface(S) )) { 975 return AssertWinner(S, G, RPF_interface(S) ) 976 } else { 977 return MRIB.next_hop( S ) 978 } 979 } 981 RPF'(*,G) and RPF'(S,G) indicate the neighbor from which data packets 982 should be coming and to which joins should be sent on the RP tree and 983 SPT respectively. 985 RPF'(S,G,rpt) is basically RPF'(*,G) modified by the result of an 986 Assert(S,G) on RPF_interface(RP(G)). In such a case, packets from S | 987 will be originating from a different router than RPF'(*,G). If we only | 988 have active (*,G) Join state, we need to accept packets from | 989 RPF'(S,G,rpt), and add a Prune(S,G,rpt) to the periodic Join(*,G) | 990 messages that we send to RPF'(*,G) (See Section 4.4.8). | 992 The function MRIB.next_hop( S ) returns the next-hop PIM neighbor toward | 993 the host S, as indicated by the current MRIB. If S is directly | 994 adjacent, then MRIB.next_hop( S ) returns NULL. At the RP for G, | 995 MRIB.next_hop( RP(G )) returns NULL. | 997 I_Am_Assert_loser(S, G, I) is true if the Assert start machine (in | 998 section 4.5.1) for (S,G) on Interface I is in "I am Assert Loser" state. | 1000 I_Am_Assert_loser(*, G, I) is true if the Assert start machine (in | 1001 section 4.5.2) for (*,G) on Interface I is in "I am Assert Loser" state. | 1003 4.2. Data Packet Forwarding Rules | 1005 The PIM-SM packet forwarding rules are defined below in pseudocode. 1007 iif is the incoming interface of the packet. 1008 S is the source address of the packet. 1009 G is the destination address of the packet (group address). 1010 RP is the address of the Rendezvous Point for this group. 1011 RPF_interface(S) is the interface the MRIB indicates would be used 1012 to route packets to S. 1013 RPF_interface(RP) is the interface the MRIB indicates would be used 1014 to route packets to RP, except at the RP when it is the 1015 decapsulation interface (the "virtual" interface on which register 1016 packets are received). 1018 First, we restart (or start) the Keepalive timer if the source is on a 1019 directly connected subnet. 1021 Second, we check to see if the SPT bit should be set because we've now 1022 switched from the RP tree to the SPT. 1024 Next we check to see whether the packet should be accepted based on TIB 1025 state and the interface that the packet arrived on. 1027 If the packet should be forwarded using (S,G) state, we then build an 1028 outgoing interface list for the packet. If this list is not empty, then 1029 we refresh the (S,G) state keepalive timer. 1031 If the packet should be forwarded using (*,*,RP) or (*,G) state, then we | 1032 just build an outgoing interface list for the packet. | 1034 Finally we remove the incoming interface from the outgoing interface 1035 list we've created, and if the resulting outgoing interface list is not 1036 empty, we forward the packet out of those interfaces. 1038 On receipt on a data from S to G on interface iif: | 1040 if( DirectlyConnected(S) == TRUE ) { | 1041 set KeepaliveTimer(S,G) to Keepalive_Period | 1042 # Note: register state transition may happen as a result | 1043 # of restarting KeepaliveTimer, and must be dealt with here. | 1044 } | 1046 Update_SPTbit(S,G,iif) | 1048 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { | 1049 oiflist = inherited_olist(S,G) | 1050 if( oiflist != NULL ) { | 1051 restart KeepaliveTimer(S,G) | 1052 } | 1053 } else if( iif == RPF_interface(RP) AND SPTbit(S,G) == FALSE) { | 1054 oiflist = inherited_olist(S,G,rpt) | 1055 } else { | 1056 # Note: RPF check failed | 1057 if ( SPTbit(S,G) == TRUE AND iif is in inherited_olist(S,G) ) { | 1058 send Assert(S,G) on iif | 1059 } else if ( SPTbit(S,G) == FALSE AND | 1060 iif is in inherited_olist(S,G,rpt) { | 1061 send Assert(*,G) on iif | 1062 } | 1063 } | 1065 oiflist = oiflist (-) iif | 1066 forward packet on all interfaces in oiflist | 1068 This pseudocode employs several "macro" definitions: 1070 directly_connected(S) is TRUE if the source S is on any subnet that is 1071 directly connected to this router (or for packets originating on this 1072 router). 1074 inherited_olist(S,G) and inherited_olist(S,G,rpt) are defined in Section 1075 4.1. 1077 Basically inherited_olist(S,G) is the outgoing interface list for | 1078 packets forwarded on (S,G) state taking into account (*,*,RP) state, | 1079 (*,G) state, asserts, etc. | 1081 inherited_olist(S,G,rpt) is the outgoing interface for packets forwarded | 1082 on (*,*,RP) or (*,G) state taking into account (S,G,rpt) prune state, | 1083 and asserts, etc. 1085 Update_SPTbit(S,G,iif) is defined in section 4.2.1. 1087 UpstreamJPState(S,G) is the state of the finite state machine in section 1088 4.4.7. 1090 Keepalive_Period is defined in Section 4.10. 1092 Data triggered PIM-Assert messages sent from the above forwarding code 1093 should be rate-limited in a implementation-dependent manner. 1095 4.2.1. Setting and Clearing the (S,G) SPT bit 1097 The (S,G) SPTbit is used to distinguish whether to forward on | 1098 (*,*,RP)/(*,G) or on (S,G) state. When switching from the RP tree to | 1099 the source tree, there is a transition period when data is arriving due 1100 to upstream (*,*,RP)/(*,G) state while upstream (S,G) state is being | 1101 established during which time a router should continue to forward only | 1102 on (*,*,RP)/(*,G) state. This prevents temporary black-holes that would | 1103 be caused by sending a Prune(S,G,rpt) before the upstream (S,G) state 1104 has finished being established. 1106 Thus, when a packet arrives, the (S,G) SPTbit is updated as follows: 1108 void 1109 Update_SPTbit(S,G,iif) { 1110 if ( iif == RPF_interface(S) 1111 AND JoinDesired(S,G) == TRUE 1112 AND ( DirectlyConnected(S) == TRUE 1113 OR RPF_interface(S) != RPF_interface(RP) 1114 OR inherited_olist(S,G,rpt) == NULL 1115 OR RPF'(S,G) == RPF'(*,G) ) ) { 1116 Set SPTbit(S,G) to TRUE 1117 } 1118 } 1120 Additionally a router sets SPTbit(S,G) to TRUE when it sees an | 1121 Assert(S,G) on RPF_interface(S). | 1123 JoinDesired(S,G) is defined in Section 4.4.7, and indicates whether we 1124 have the appropriate (S,G) Join state to wish to send a Join(S,G) 1125 upstream. 1127 Basically Update_SPTbit will set the SPT bit if we have the appropriate | 1128 (S,G) join state and the packet arrived on the correct upstream | 1129 interface for S, and one or more of the following conditions applies: | 1131 1. The source is directly connected, in which case the switch to the 1132 SPT is a no-op. 1134 2. The RPF interface to S is different from the RPF interface to the 1135 RP. The packet arrived on RPF_interface(S), and so the SPT must 1136 have been completed. 1138 3. No-one wants the packet on the RP tree. 1140 4. RPF'(S,G) == RPF'(*,G). In this case the router will never be able 1141 to tell if the SPT has been completed, so it should just switch 1142 immediately. 1144 In the case where the RPF interface is the same for the RP and for S, 1145 but RPF'(S,G) and RPF'(*,G) differ, then we wait for an Assert(S,G) 1146 which indicates that the upstream router with (S,G) state believes the | 1147 SPT has been completed. However item (3) above is needed because there | 1148 may not be any (*,G) state to trigger an Assert(S,G) to happen. | 1150 The SPT bit is cleared in the (S,G) upstream state machine (see Section | 1151 4.4.7) when JoinDesired(S,G) becomes FALSE. | 1152 4.3. PIM Register Messages 1154 Overview 1156 The Designated Router (DR) on a LAN or point-to-point link encapsulates 1157 multicast packets from local sources to the RP for the relevant group 1158 unless it recently received a Register Stop message for that (S,G) or 1159 (*,G) from the RP. When the DR receives a Register Stop message from 1160 the RP, it starts a Register Stop timer to maintain this state. Just 1161 before the Register Stop timer expires, the DR sends a Null-Register 1162 Message to the RP to allow the RP to refresh the Register Stop 1163 information at the DR. If the Register Stop timer actually expires, the 1164 DR will resume encapsulating packets to the source. 1166 4.3.1. Sending Register Messages from the DR 1168 Every PIM-SM router has the capability to be a DR. The state machine 1169 below is used to implement Register functionality. For the purposes of 1170 specification, we represent the mechanism to encapsulate packets to the 1171 RP as a Register-Tunnel interface, which is added to or removed from the 1172 (S,G) olist. The tunnel interface then takes part in the normal packet 1173 forwarding rules specified in Section 4.2. 1175 If register state is maintained, it is maintained only for directly 1176 connected sources, and is per-(S,G). There are four states in the DR's 1177 per-(S,G) Register state-machine: 1179 Join (J) 1180 The register tunnel is "joined" (the join is actually implicit, but 1181 the DR acts as if the RP has joined the DR on the tunnel 1182 interface). 1184 Prune (P) 1185 The register tunnel is "pruned" (this occurs when a Register Stop 1186 is received). 1188 Join Pending (JP) 1189 The register tunnel is pruned but the DR is contemplating adding it 1190 back. 1192 No Info (NI) 1193 No information. This is the initial state, and the state when the 1194 router is not the DR. 1196 In addition, a RegisterStop timer (RST) is kept if the state machine in 1197 not in the No Info state. 1199 +-----------------------------------+ 1200 | Figures omitted from text version | 1201 +-----------------------------------+ 1203 Figure 1: Per-(S,G) register state-machine at a DR 1205 In tabular form, the state-machine is: 1207 +---------+-----------------------------------------------------------------+ 1208 | | Event | 1209 | +------------+--------------+-------------+-----------+-----------+ 1210 Prev StateRegister- CouldRegister CouldRegister Register- RP changed | 1211 | Stop Timer ->True ->False Stop | | 1212 | expires | | received | | 1213 +---------+------------+--------------+-------------+-----------+-----------+ 1214 No Info + +> J state + + + | 1215 (NI) | add tunnel | | | | 1216 +---------+------------+--------------+-------------+-----------+-----------+ 1217 | + + +> NI state +> P state +> J state | 1218 | | | remove tunnel remove redirect | 1219 | | | | tunnel; tunnel to | 1220 Join (J) | | | set new RP; | 1221 | | | | Register- stop | 1222 | | | | Stop Register- | 1223 | | | | timer(*) Stop timer | 1224 +---------+------------+--------------+-------------+-----------+-----------+ 1225 | +> J state + +> NI state +> P state +> J state | 1226 | add tunnel | remove tunnel set redirect | 1227 Join | | | Register- tunnel to | 1228 Pending | | | Stop new RP; | 1229 (JP) | | | timer(*) stop | 1230 | | | | | Register- | 1231 | | | | | Stop timer | 1232 +---------+------------+--------------+-------------+-----------+-----------+ 1233 | +> JP state + +> NI state + +> J state | 1234 | set | remove tunnel | redirect | 1235 | Register- | | | tunnel to | 1236 Prune (P) Stop | | | new RP; | 1237 | timer(**); | | | stop | 1238 | send null | | | Register- | 1239 | register | | | Stop timer | 1240 +---------+------------+--------------+-------------+-----------+-----------+ 1242 Notes: 1244 (*) The RegisterStopTimer is set to a random value chosen uniformly from 1245 the interval ( 0.5 * Register_Suppression_Time, 1.5 * 1246 Register_Suppression_Time) minus Register_Probe_Time; 1248 Subtracting off register_probe_time is a bit unnecessary because it is 1249 really small compared to register suppression timeout, but was in the 1250 old spec and is kept for compatibility. 1252 (**) The RegisterStopTimer is set to register_probe_time. 1254 The macro "CouldRegister" in the state machine is defined as: | 1256 Bool CouldRegister(S,G) { | 1257 return ( I_am_DR( RPF_interface(S) ) AND | 1258 KeepaliveTimer(S,G) is running AND | 1259 DirectlyConnected(S) == TRUE ) | 1260 } | 1262 Note that on reception of a packet at the DR from a directly connected 1263 source, KeepaliveTimer(S,G) needs to be set by the packet forwarding | 1264 rules before computing CouldRegister(S,G) in the register state machine, | 1265 or the first packet from a source won't be registered. 1267 Handling RegisterStop(*,G) Messages at the DR 1269 An RP MAY send a RegisterStop message with the source address set to 1270 all-zeros. This was the normal course of action in RFC 2326 when the 1271 register message matched against (*,G) state at the RP, and was defined 1272 as meaning "stop encapsulating all sources for this group". However, 1273 the behavior of such a RegisterStop(*,G) is ambiguous or incorrect in 1274 some circumstances. 1276 We specify that an RP should not send RegisterStop(*,G) messages, but 1277 for compatibility, a DR should be able to accept one if it is received. 1279 A RegisterStop(*,G) should be treated as a RegisterStop(S,G) for all 1280 existing (S,G) Register state machines. A router should not apply a 1281 RegisterStop(*,G) to sources that become active after the 1282 RegisterStop(*,G) was received. 1284 4.3.2. Receiving Register Messages at the RP 1286 When an RP receives a Register message, the course of action is decided 1287 according to the following pseudocode: 1289 packet_arrives_on_rp_tunnel( pkt ) { 1290 if( outer.dst is not one of my addresses ) { | 1291 drop the packet silently. | 1292 # note that this should not happen if the lower layer is working | 1293 } | 1294 if( I_am_RP( G ) && outer.dst == RP(G) ) { | 1295 restart KeepaliveTimer(S,G) | 1296 if(( inherited_olist(S,G) == NULL ) OR SPTbit(S,G)) { | 1297 send RegisterStop(S,G) to outer.src | 1298 } else { | 1299 if( ! pkt.NullRegisterBit ) { | 1300 decapsulate and pass the inner packet to the normal | 1301 forwarding path for forwarding on the (*,G) tree. | 1302 } | 1303 } | 1304 } else { | 1305 send RegisterStop(S,G) to outer.src | 1306 # Note (*) | 1307 } | 1308 } | 1310 outer.dst is the IP destination address of the encapsulating header. 1312 outer.src is the IP source address of the encapsulating header, i.e., 1313 the DR's address. 1315 I_am_RP(G) is true if the group-to-RP mapping indicates that this router 1316 is the RP for the group. 1318 Note (*): This may block traffic from S for Register_Suppression_Time if 1319 the DR learned about a new group-to-RP mapping before the RP did. 1320 However, this doesn't matter unless we figure out some way for the 1321 RP to also accept (*,G) joins when it doesn't yet realize that it 1322 is about to become the RP for G. This will all get sorted out once 1323 the RP learns the new group-to-rp mapping. We decided to do 1324 nothing about this and just accept the fact that PIM may suffer 1325 interrupted (*,G) connectivity following an RP change. 1327 KeepaliveTimer(S,G) is restarted at the RP when packets arrive on the 1328 proper tunnel interface. This may cause the upstream (S,G) state 1329 machine to trigger a join if the inherited_olist(S,G) is not NULL; 1330 An RP should preserve (S,G) state that was created in response to a | 1331 Register message for at least ( 3 * Register_Suppression_Time ), | 1332 otherwise the RP may stop joining (S,G) before the DR for S has 1333 restarted sending registers. Traffic would then be interrupted until 1334 the Register-Stop timer expires at the DR. 1336 Thus, at the RP, KeepaliveTimer(S,G) should be restarted to ( 3 * | 1337 Register_Suppression_Time + Register_Probe_Time ). | 1339 4.4. PIM Join/Prune Messages 1341 A PIM Join/Prune message consists of a list of groups and a list of 1342 Joined and Pruned sources for each group. When processing a received 1343 Join/Prune message, each Joined or Pruned source for a Group is 1344 effectively considered individually, and applies to one or more of the 1345 following state machines. When considering a Join/Prune message whose 1346 PIM Destination field addresses this router, (*,*,RP) Joins and Prunes | 1347 can affect the (*,*,RP) and (S,G,rpt) downstream state machines, (*,G) | 1348 Joins and Prunes can affect both the (*,G) and (S,G,rpt) downstream 1349 state machines, while (S,G) and (S,G,rpt) Joins and Prunes can only 1350 affect their respective downstream state machines. When considering a 1351 Join/Prune message whose PIM Destination field addresses another router, 1352 most Join or Prune messages could affect each upstream state machine. 1353 (... it's possible to enumerate this ...) XXX 1355 4.4.1. Receiving (*,*,RP) Join/Prune Messages 1357 The per-interface state-machine for receiving (*,*,RP) Join/Prune | 1358 Messages is given below. There are three states: | 1360 NoInfo (NI) | 1361 The interface has no (*,*,RP) Join state and no timers | 1362 running. | 1364 Join (J) | 1365 The interface has (*,*,RP) Join state which will cause us to | 1366 forward packets destined for any group handled by RP from this | 1367 interface except if there is also (S,G,rpt) prune information | 1368 (see Section 4.4.4) or the router lost an assert on this | 1369 interface. | 1371 PrunePending (PP) | 1372 The router has received a Prune(*,*,RP) on this interface from | 1373 a downstream neighbor and is waiting to see whether the prune | 1374 will be overridden by another downstream router. For | 1375 forwarding purposes, the PrunePending state functions exactly | 1376 like the Join state. | 1378 In addition the state-machine uses two timers: | 1380 ExpiryTimer (ET) | 1381 This timer is restarted when a valid Join(*,*,RP) is received. | 1382 Expiry of the ExpiryTimer causes the interface state to revert | 1383 to NoInfo for this group. | 1385 PrunePendingTimer (PPT) | 1386 This timer is set when a valid Prune(*,*,RP) is received. | 1387 Expiry of the PrunePendingTimer causes the interface state to | 1388 revert to NoInfo for this group. | 1390 +-----------------------------------+ | 1391 | Figures omitted from text version | | 1392 +-----------------------------------+ | 1394 Figure 2: Downstream (*,*,RP) per-interface state-machine | 1396 In tabular form, the per-interface (*,*,RP) state-machine is: | 1398 +-------------------+----------------------------------------------------|------------| 1399 | | Event | 1400 | +-------------------+---------------+---------------+|------------| 1401 Prev State | Receive | Receive | Prune | Expiry Timer || 1402 | Join(*,*,RP) | Prune(*,*,RP)| Pending | Expires || 1403 | | | Timer | || | 1404 | | | Expires | || | 1405 +-------------------+-------------------+---------------+---------------+-------------| 1406 | +> J state +> NI state + +| | 1407 NoInfo (NI) | start Expiry | | | || | 1408 | Timer | | | || | 1409 +-------------------+-------------------+---------------+---------------+-------------| 1410 | +> J state +> PP state + +> NI state| | 1411 Join (J) | restart Expiry | start Prune || || | 1412 | Timer | Pending Timer || || | 1413 +-------------------+-------------------+---------------+---------------+-------------| 1414 | +> J state +> PP state +> NI state +> NI state| | 1415 Prune Pending (PP) |restart Expiry || Send Prune- ||| | 1416 | Timer; stop Prune || Echo(*,*,RP) ||| | 1417 | Pending Timer || | || | 1418 +-------------------+-------------------+---------------+---------------+-------------| 1420 The transition events "Receive Join(*,*,RP)" and "Receive Prune(*,*,RP)" | 1421 imply receiving a Join or Prune targeted to this router's address on the | 1422 received interface. If the destination address is not correct, these | 1423 state transitions in this state machine must not occur, although seeing | 1424 such a packet may cause state transitions in other state machines. | 1426 On unnumbered interfaces on point-to-point links, the router's address | 1427 should be the same as the source address it chose for the hello packet | 1428 it sent over that interface. However on point-to-point links we also | 1429 recommend that PIM messages with a 0.0.0.0 destination address are also | 1430 accepted. | 1432 Transitions from NoInfo State | 1434 When in NoInfo state, the following event may trigger a transition: | 1436 Receive Join(*,*,RP) | 1437 A Join(*,*,RP) is received on interface I with its IP | 1438 destination set to the router's address on I. | 1440 The (*,*,RP) downstream state machine on interface I | 1441 transitions to the Join state. The Expiry Timer (ET) is | 1442 started, and set to the HoldTime from the triggering Join | 1443 message. | 1445 Transitions from Join State | 1447 When in Join state, the following events may trigger a transition: | 1449 Receive Join(*,*,RP) | 1450 A Join(*,*,RP) is received on interface I with its IP | 1451 destination set to the router's address on I. | 1453 The (*,*,RP) downstream state machine on interface I remains | 1454 in Join state, and the Expiry Timer (ET) is restarted, set to | 1455 the HoldTime from the triggering Join message. | 1457 Receive Prune(*,*,RP) | 1458 A Prune(*,*,RP) is received on interface I with its IP | 1459 destination set to the router's address on I. | 1461 The (*,*,RP) downstream state machine on interface I | 1462 transitions to the PrunePending state. The PrunePending timer | 1463 is started; it is set to the J/P_Override_Interval if the | 1464 router has more than one neighbor on that interface; otherwise | 1465 it is set to zero causing it to expire immediately. | 1467 Expiry Timer Expires | 1468 The Expiry Timer for the (*,*,RP) downstream state machine on | 1469 interface I expires. | 1470 The (*,*,RP) downstream state machine on interface I | 1471 transitions to the NoInfo state. | 1473 Transitions from PrunePending State | 1475 When in PrunePending state, the following events may trigger a | 1476 transition: | 1478 Receive Join(*,*,RP) | 1479 A Join(*,*,RP) is received on interface I with its IP | 1480 destination set to the router's address on I. | 1482 The (*,*,RP) downstream state machine on interface I | 1483 transitions to the Join state. The PrunePending timer is | 1484 canceled (without triggering an expiry event). The Expiry | 1485 Timer is restarted, and set to the HoldTime from the | 1486 triggering Join message. | 1488 Expiry Timer Expires | 1489 The Expiry Timer for the (*,*,RP) downstream state machine on | 1490 interface I expires. | 1492 The (*,*,RP) downstream state machine on interface I | 1493 transitions to the NoInfo state. | 1495 PrunePending Timer Expires | 1496 The PrunePending Timer for the (*,*,RP) downstream state | 1497 machine on interface I expires. | 1499 The (*,*,RP) downstream state machine on interface I | 1500 transitions to the NoInfo state. A PruneEcho(*,*,RP) is sent | 1501 onto the subnet connected to interface I. | 1503 The action "Send PruneEcho(*,*,RP)" is triggered when the | 1504 router stops forwarding on an interface as a result of a | 1505 prune. A PruneEcho(*,*,RP) is simply a Prune(*,*,RP) message | 1506 sent by the upstream router to itself on a LAN. Its purpose | 1507 is to add additional reliability so that if a Prune that | 1508 should have been overridden by another router is lost locally | 1509 on the LAN, then the PruneEcho may be received and cause the | 1510 override to happen. A PruneEcho(*,*,RP) need not be sent on a | 1511 point-to-point interface. | 1513 4.4.2. Receiving (*,G) Join/Prune Messages 1515 When a router receives a Join(*,G) or Prune(*,G) it must first check to 1516 see whether the RP in the message matches RP(G) (the router's idea of 1517 who the RP is). If the RP in the message does not match RP(G) the Join 1518 or Prune should be silently dropped. If a router has no RP information 1519 (e.g. has not recently received a BSR message) then it may choose to 1520 accept Join(*,G) or Prune(*,G) and treat the RP in the message as RP(G). 1522 The per-interface state-machine for receiving (*,G) Join/Prune Messages | 1523 is given below. There are three states: | 1525 NoInfo (NI) 1526 The interface has no (*,G) Join state and no timers running. 1528 Join (J) 1529 The interface has (*,G) Join state which will cause us to 1530 forward packets destined for G from this interface except if 1531 there is also (S,G,rpt) prune information (see Section 4.4.4) 1532 or the router lost an assert on this interface. 1534 PrunePending (PP) 1535 The router has received a Prune(*,G) on this interface from a 1536 downstream neighbor and is waiting to see whether the prune 1537 will be overridden by another downstream router. For 1538 forwarding purposes, the PrunePending state functions exactly 1539 like the Join state. 1541 In addition the state-machine uses two timers: | 1543 ExpiryTimer (ET) 1544 This timer is restarted when a valid Join(*,G) is received. 1545 Expiry of the ExpiryTimer causes the interface state to revert 1546 to NoInfo for this group. 1548 PrunePendingTimer (PPT) 1549 This timer is set when a valid Prune(*,G) is received. Expiry 1550 of the PrunePendingTimer causes the interface state to revert 1551 to NoInfo for this group. 1553 +-----------------------------------+ 1554 | Figures omitted from text version | 1555 +-----------------------------------+ 1557 Figure 3: Downstream (*,G) per-interface state-machine 1559 In tabular form, the per-interface (*,G) state-machine is: 1561 +-------------++--------------------------------------------------------+ 1562 | || Event | 1563 | ++-------------+-------------+-------------+--------------+ 1564 |Prev State ||Receive | Receive | Prune | Expiry Timer | 1565 | ||Join(*,G) | Prune(*,G) | Pending | Expires | 1566 | || | | Timer | | 1567 | || | | Expires | | 1568 +-------------++-------------+-------------+-------------+--------------+ 1569 | ||-> J state | -> NI state | - | - | 1570 |NoInfo (NI) ||start Expiry | | | | 1571 | ||Timer | | | | 1572 +-------------++-------------+-------------+-------------+--------------+ 1573 | ||-> J state | -> PP state | - | -> NI state | 1574 |Join (J) ||restart | start Prune | | | 1575 | ||Expiry Timer | Pending | | | 1576 | || | Timer | | | 1577 +-------------++-------------+-------------+-------------+--------------+ 1578 | ||-> J state | -> PP state | -> NI state | -> NI state | 1579 | ||restart | | Send Prune- | | 1580 |Prune ||Expiry | | Echo(*,G) | | 1581 |Pending (PP) ||Timer; stop | | | | 1582 | ||Prune | | | | 1583 | ||Pending | | | | 1584 | ||Timer | | | | 1585 +-------------++-------------+-------------+-------------+--------------+ 1587 The transition events "Receive Join(*,G)" and "Receive Prune(*,G)" imply 1588 receiving a Join or Prune targeted to this router's address on the 1589 received interface. If the destination address is not correct, these 1590 state transitions in this state machine must not occur, although seeing 1591 such a packet may cause state transitions in other state machines. 1593 On unnumbered interfaces on point-to-point links, the router's address 1594 should be the same as the source address it chose for the hello packet 1595 it sent over that interface. However on point-to-point links we also 1596 recommend that PIM messages with a 0.0.0.0 destination address are also 1597 accepted. 1599 Transitions from NoInfo State 1601 When in NoInfo state, the following event may trigger a transition: | 1603 Receive Join(*,G) | 1604 A Join(*,G) is received on interface I with its IP destination | 1605 set to the router's address on I. | 1606 The (*,G) downstream state machine on interface I transitions | 1607 to the Join state. The Expiry Timer (ET) is started, and set | 1608 to the HoldTime from the triggering Join message. | 1610 Transitions from Join State | 1612 When in Join state, the following events may trigger a transition: | 1614 Receive Join(*,G) | 1615 A Join(*,G) is received on interface I with its IP destination | 1616 set to the router's address on I. | 1618 The (*,G) downstream state machine on interface I remains in | 1619 Join state, and the Expiry Timer (ET) is restarted, set to the | 1620 HoldTime from the triggering Join message. | 1622 Receive Prune(*,G) | 1623 A Prune(*,G) is received on interface I with its IP | 1624 destination set to the router's address on I. | 1626 The (*,G) downstream state machine on interface I transitions | 1627 to the PrunePending state. The PrunePending timer is started; | 1628 it is set to the J/P_Override_Interval if the router has more | 1629 than one neighbor on that interface; otherwise it is set to | 1630 zero causing it to expire immediately. | 1632 Expiry Timer Expires | 1633 The Expiry Timer for the (*,G) downstream state machine on | 1634 interface I expires. | 1636 The (*,G) downstream state machine on interface I transitions | 1637 to the NoInfo state. | 1639 Transitions from PrunePending State | 1641 When in PrunePending state, the following events may trigger a | 1642 transition: | 1644 Receive Join(*,G) | 1645 A Join(*,G) is received on interface I with its IP destination | 1646 set to the router's address on I. | 1648 The (*,G) downstream state machine on interface I transitions | 1649 to the Join state. The PrunePending timer is canceled | 1650 (without triggering an expiry event). The Expiry Timer is | 1651 restarted, and set to the HoldTime from the triggering Join | 1652 message. | 1654 Expiry Timer Expires | 1655 The Expiry Timer for the (*,G) downstream state machine on | 1656 interface I expires. | 1658 The (*,G) downstream state machine on interface I transitions | 1659 to the NoInfo state. | 1661 PrunePending Timer Expires | 1662 The PrunePending Timer for the (*,G) downstream state machine | 1663 on interface I expires. | 1665 The (*,G) downstream state machine on interface I transitions | 1666 to the NoInfo state. A PruneEcho(*,G) is sent onto the subnet | 1667 connected to interface I. | 1669 The action "Send PruneEcho(*,G)" is triggered when the router | 1670 stops forwarding on an interface as a result of a prune. A 1671 PruneEcho(*,G) is simply a Prune(*,G) message sent by the 1672 upstream router to itself on a LAN. Its purpose is to add 1673 additional reliability so that if a Prune that should have 1674 been overridden by another router is lost locally on the LAN, 1675 then the PruneEcho may be received and cause the override to 1676 happen. A PruneEcho(*,G) need not be sent on a point-to-point 1677 interface. 1679 4.4.3. Receiving (S,G) Join/Prune Messages 1681 The per-interface state machine for receiving (S,G) Join/Prune messages | 1682 is given below, and is almost identical to that for (*,G) messages. | 1683 There are three states: 1685 NoInfo (NI) 1686 The interface has no (S,G) Join state and no (S,G) timers 1687 running. 1689 Join (J) 1690 The interface has (S,G) Join state which will cause us to 1691 forward packets from S destined for G from this interface if 1692 the (S,G) state is active (the SPTbit is set) except if the 1693 router lost an assert on this interface. 1695 PrunePending (PP) 1696 The router has received a Prune(S,G) on this interface from a 1697 downstream neighbor and is waiting to see whether the prune 1698 will be overridden by another downstream router. For 1699 forwarding purposes, the PrunePending state functions exactly 1700 like the Join state. 1702 In addition there are two timers: 1704 ExpiryTimer (ET) 1705 This timer is set when a valid Join(S,G) is received. Expiry 1706 of the ExpiryTimer causes the interface state to revert to 1707 NoInfo for this group. 1709 PrunePendingTimer (PPT) 1710 This timer is set when a valid Prune(S,G) is received. Expiry 1711 of the PrunePendingTimer causes the interface state to revert 1712 to NoInfo for this group. 1714 +-----------------------------------+ 1715 | Figures omitted from text version | 1716 +-----------------------------------+ 1718 Figure 4: Downstream per-interface (S,G) state-machine 1720 In tabular form, the state machine is: 1722 +-------------++--------------------------------------------------------+ 1723 | || Event | 1724 | ++-------------+-------------+-------------+--------------+ 1725 |Prev State ||Receive | Receive | Prune | Expiry Timer | 1726 | ||Join(S,G) | Prune(S,G) | Pending | Expires | 1727 | || | | Timer | | 1728 | || | | Expires | | 1729 +-------------++-------------+-------------+-------------+--------------+ 1730 | ||-> J state | -> NI state | - | - | 1731 |NoInfo (NI) ||start Expiry | | | | 1732 | ||Timer | | | | 1733 +-------------++-------------+-------------+-------------+--------------+ 1734 | ||-> J state | -> PP state | - | -> NI state | 1735 |Join (J) ||restart | start Prune | | | 1736 | ||Expiry Timer | Pending | | | 1737 | || | Timer | | | 1738 +-------------++-------------+-------------+-------------+--------------+ 1739 | ||-> J state | -> PP state | -> NI state | -> NI state | 1740 | ||restart | | Send Prune- | | 1741 |Prune ||Expiry | | Echo(S,G) | | 1742 |Pending (PP) ||Timer; stop | | | | 1743 | ||Prune | | | | 1744 | ||Pending | | | | 1745 | ||Timer | | | | 1746 +-------------++-------------+-------------+-------------+--------------+ 1747 The transition events "Receive Join(S,G)" and "Receive Prune(S,G)" imply 1748 receiving a Join or Prune targeted to this router's address on the 1749 received interface. If the destination address is not correct, these 1750 state transitions in this state machine must not occur, although seeing 1751 such a packet may cause state transitions in other state machines. 1753 On unnumbered interfaces on point-to-point links, the router's address 1754 should be the same as the source address it chose for the hello packet 1755 it sent over that interface. However on point-to-point links we also | 1756 recommend that PIM messages with a 0.0.0.0 destination address are also | 1757 accepted. 1759 Transitions from NoInfo State 1761 When in NoInfo state, the following event may trigger a transition: | 1763 Receive Join(S,G) | 1764 A Join(S,G) is received on interface I with its IP destination | 1765 set to the router's address on I. | 1767 The (S,G) downstream state machine on interface I transitions | 1768 to the Join state. The Expiry Timer (ET) is started, and set | 1769 to the HoldTime from the triggering Join message. | 1771 Transitions from Join State | 1773 When in Join state, the following events may trigger a transition: | 1775 Receive Join(S,G) | 1776 A Join(S,G) is received on interface I with its IP destination | 1777 set to the router's address on I. | 1779 The (S,G) downstream state machine on interface I remains in | 1780 Join state, and the Expiry Timer (ET) is restarted, set to the | 1781 HoldTime from the triggering Join message. | 1783 Receive Prune(S,G) | 1784 A Prune(S,G) is received on interface I with its IP | 1785 destination set to the router's address on I. | 1787 The (S,G) downstream state machine on interface I transitions | 1788 to the PrunePending state. The PrunePending timer is started; | 1789 it is set to the J/P_Override_Interval if the router has more | 1790 than one neighbor on that interface; otherwise it is set to | 1791 zero causing it to expire immediately. | 1793 Expiry Timer Expires | 1794 The Expiry Timer for the (S,G) downstream state machine on | 1795 interface I expires. | 1797 The (S,G) downstream state machine on interface I transitions | 1798 to the NoInfo state. | 1800 Transitions from PrunePending State | 1802 When in PrunePending state, the following events may trigger a | 1803 transition: | 1805 Receive Join(S,G) | 1806 A Join(S,G) is received on interface I with its IP destination | 1807 set to the router's address on I. | 1809 The (S,G) downstream state machine on interface I transitions | 1810 to the Join state. The PrunePending timer is canceled | 1811 (without triggering an expiry event). The Expiry Timer is | 1812 restarted, and set to the HoldTime from the triggering Join | 1813 message. | 1815 Expiry Timer Expires | 1816 The Expiry Timer for the (S,G) downstream state machine on | 1817 interface I expires. | 1819 The (S,G) downstream state machine on interface I transitions | 1820 to the NoInfo state. | 1822 PrunePending Timer Expires | 1823 The PrunePending Timer for the (S,G) downstream state machine | 1824 on interface I expires. | 1826 The (S,G) downstream state machine on interface I transitions | 1827 to the NoInfo state. A PruneEcho(S,G) is sent onto the subnet | 1828 connected to interface I. | 1830 The action "Send PruneEcho(S,G)" is triggered when the router | 1831 stops forwarding on an interface as a result of a prune. A 1832 PruneEcho(S,G) is simply a Prune(S,G) message sent by the 1833 upstream router to itself on a LAN. Its purpose is to add 1834 additional reliability so that if a Prune that should have 1835 been overridden by another router is lost locally on the LAN, 1836 then the PruneEcho may be received and cause the override to 1837 happen. A PruneEcho(S,G) need not be sent on a point-to-point 1838 interface. 1840 4.4.4. Receiving (S,G,rpt) Join/Prune Messages 1842 The per-interface state machine for receiving (S,G,rpt) Join/Prune 1843 messages is given below. There are five states: 1845 NoInfo (NI) 1846 The interface has no (S,G,rpt) Prune state and no (S,G,rpt) 1847 timers running. 1849 Prune (P) 1850 The interface has (S,G,rpt) Prune state which will cause us 1851 not to forward packets from S destined for G from this 1852 interface even though the interface has active (*,G) Join 1853 state. When interface I is in this state, the macro 1854 prune(S,G,rpt,I) returns true. 1856 PrunePending (PP) 1857 The router has received a Prune(S,G,rpt) on this interface 1858 from a downstream neighbor and is waiting to see whether the 1859 prune will be overridden by another downstream router. For 1860 forwarding purposes, the PrunePending state functions exactly 1861 like the NoInfo state. 1863 PruneTmp (P') 1864 This state is a transient state which for forwarding purposes 1865 behaves exactly like the Prune state. A (*,G) Join has been 1866 received (which may cancel the (S,G,rpt) Prune). As we parse 1867 the Join/Prune message from top to bottom, we first enter this 1868 state if the message contains a (*,G) Join. Later in the 1869 message we will normally encounter an (S,G,rpt) prune to re- 1870 instate the Prune state. However if we reach the end of the 1871 message without encountering such a (S,G,rpt) prune, then we 1872 will revert to NoInfo state in this state machine. 1874 As no time is spent in this state, no timers can expire. 1876 PrunePendingTmp (PP') 1877 This state is a transient state which is identical to P' 1878 except that it is associated with the PP state rather than the 1879 P state. For forwarding purposes, PP' behaves exactly like PP 1880 state. 1882 In addition there are two timers: 1884 ExpiryTimer (ET) 1885 This timer is set when a valid Prune(S,G,rpt) is received. 1886 Expiry of the ExpiryTimer causes this state machine to revert 1887 to NoInfo state. 1889 PrunePendingTimer (PPT) 1890 This timer is set when a valid Prune(S,G,rpt) is received. 1891 Expiry of the PrunePendingTimer causes this state machine to 1892 move on to Prune state. 1894 +-----------------------------------+ 1895 | Figures omitted from text version | 1896 +-----------------------------------+ 1898 Figure 5: Downstream per-interface (S,G,rpt) state-machine 1900 In tabular form, the state machine is: 1902 +-------+---------------------------------------------------------------+ 1903 | | Event | 1904 | +----------------+----------+---------+--------+-------+--------+ 1905 |Prev |Receive |Receive Receive |End of |Prune |Expiry | 1906 |State |Join(*,G) |Join Prune |Message |Pending|Timer | 1907 | |or |(S,G,rpt) (S,G,rpt) | |Timer |Expires | 1908 | |Join(*,*,RP(G)) | | | |Expires| | 1909 +-------+----------------+----------+---------+--------+-------+--------+ 1910 | |- |- +> PP |- |n/a |n/a | 1911 | | | state | | | | 1912 | | | start | | | | 1913 | | | Prune | | | | 1914 |No Info| | Pending | | | | 1915 |(NI) | | Timer; | | | | 1916 | | | start | | | | 1917 | | | Expiry | | | | 1918 | | | Timer | | | | 1919 | | | Timer | | | | 1920 +-------+----------------+----------+---------+--------+-------+--------+ 1921 | |-> P' state |-> NI +> P |- |n/a |-> NI | 1922 |Pruned | |state state | | |state | 1923 |(P) | | restart | | | | 1924 | | | Expiry | | | | 1925 | | | Timer | | | | 1926 +-------+----------------+----------+---------+--------+-------+--------+ 1927 |Prune |-> PP' state |-> NI + |- |-> P |n/a | 1928 |Pending| |state | | |state | | 1929 |(PP) | | | | | | | 1930 +-------+----------------+----------+---------+--------+-------+--------+ 1931 | |error |error +> P |-> NI |n/a |n/a | 1932 |Temp. | | state |state | | | 1933 |Pruned | | restart | | | | 1934 |(P') | | Expiry | | | | 1935 | | | Timer | | | | 1936 +-------+----------------+----------+---------+--------+-------+--------+ 1937 |Temp. |error |error +> PP |-> NI |n/a |n/a | 1938 |Prune | | state |state | | | 1939 |Pending| | restart | | | | 1940 |(PP') | | Expiry | | | | 1941 | | | Timer | | | | 1942 +-------+----------------+----------+---------+--------+-------+--------+ 1944 The transition events "Receive Join(S,G,rpt)", "Receive Prune(S,G,rpt)", | 1945 "Receive Join(*,G)" and "Receive Join(*,*,RP(G))" imply receiving a Join | 1946 or Prune targeted to this router's address on the received interface. | 1947 If the destination address is not correct, these state transitions in 1948 this state machine must not occur, although seeing such a packet may 1949 cause state transitions in other state machines. 1951 On unnumbered interfaces on point-to-point links, the router's address 1952 should be the same as the source address it chose for the hello packet 1953 it sent over that interface. However on point-to-point links we also | 1954 recommend that PIM messages with a 0.0.0.0 destination address are also | 1955 accepted. | 1957 Transitions from NoInfo State | 1959 When in NoInfo (NI) state, the following event may trigger a transition: | 1961 Receive Prune(S,G,rpt) | 1962 A Prune(S,G,rpt) is received on interface I with its IP | 1963 destination set to the router's address on I. | 1965 The (S,G,rpt) downstream state machine on interface I | 1966 transitions to the PrunePending state. The Expiry Timer (ET) | 1967 is started, and set to the HoldTime from the triggering Join | 1968 message. The PrunePending timer is started; it is set to the | 1969 J/P_Override_Interval if the router has more than one neighbor | 1970 on that interface; otherwise it is set to zero causing it to | 1971 expire immediately. | 1973 Transitions from PrunePending State | 1975 When in PrunePending (PP) state, the following events may trigger a | 1976 transition: | 1978 Receive Join(*,G) or Join(*,*,RP(G)) | 1979 A Join(*,*,RP(G)) or Join(*,G) is received on interface I with | 1980 its IP destination set to the router's address on I. | 1982 The (S,G,rpt) downstream state machine on interface I | 1983 transitions to Temp. PrunePending state whilst the remainder | 1984 of the compound Join/Prune message containing the | 1985 Join(*,*,RP(G)) or Join(*,G) is processed. | 1987 Receive Join(S,G,rpt) | 1988 A Join(S,G,rpt) is received on interface I with its IP | 1989 destination set to the router's address on I. | 1991 The (S,G,rpt) downstream state machine on interface I | 1992 transitions to NoInfo state. ET and PPT are canceled. | 1994 PrunePending Timer Expires | 1995 The PrunePending Timer for the (S,G,rpt) downstream state | 1996 machine on interface I expires. | 1998 The (S,G,rpt) downstream state machine on interface I | 1999 transitions to the Pruned state. | 2001 Transitions from Pruned State | 2003 When in Pruned (P) state, the following events may trigger a transition: | 2005 Receive Join(*,G) or Join(*,*,RP(G)) | 2006 A Join(*,*,RP(G)) or Join(*,G) is received on interface I with | 2007 its IP destination set to the router's address on I. | 2009 The (S,G,rpt) downstream state machine on interface I | 2010 transitions to Temp. Pruned state whilst the remainder of the | 2011 compound Join/Prune message containing the Join(*,*,RP(G)) or | 2012 Join(*,G) is processed. | 2014 Receive Join(S,G,rpt) | 2015 A Join(S,G,rpt) is received on interface I with its IP | 2016 destination set to the router's address on I. | 2018 The (S,G,rpt) downstream state machine on interface I | 2019 transitions to NoInfo state. ET and PPT are canceled. | 2021 Receive Prune(S,G,rpt) | 2022 A Prune(S,G,rpt) is received on interface I with its IP | 2023 destination set to the router's address on I. | 2025 The (S,G,rpt) downstream state machine on interface I remains | 2026 in Pruned state. The Expiry Timer (ET) is restarted, set to | 2027 the HoldTime from the triggering Join message. | 2029 Expiry Timer Expires | 2030 The Expiry Timer for the (S,G,rpt) downstream state machine on | 2031 interface I expires. | 2033 The (S,G,rpt) downstream state machine on interface I | 2034 transitions to the NoInfo state. ET and PPT are canceled. | 2036 Transitions from Temp. PrunePending State | 2038 When in Temp. PrunePending (PP') state and processing a compound | 2039 Join/Prune message, the following events may trigger a transition: | 2041 Receive Prune(S,G,rpt) | 2042 The compound Join/Prune message contains a Prune(S,G,rpt). | 2043 The (S,G,rpt) downstream state machine on interface I | 2044 transitions back to the PrunePending state. The Expiry Timer | 2045 (ET) is restarted, set to the HoldTime from the Join/Prune | 2046 message. | 2048 End of Message | 2049 The end of the compound Join/Prune message is reached. | 2051 The (S,G,rpt) downstream state machine on interface I | 2052 transitions to the NoInfo state. ET and PPT are canceled. | 2054 Transitions from Temp. Pruned State | 2056 When in Temp. Pruned (P') state and processing a compound Join/Prune | 2057 message, the following events may trigger a transition: | 2059 Receive Prune(S,G,rpt) | 2060 The compound Join/Prune message contains a Prune(S,G,rpt). | 2062 The (S,G,rpt) downstream state machine on interface I | 2063 transitions back to the Pruned state. The Expiry Timer (ET) | 2064 is restarted, set to the HoldTime from the Join/Prune message. | 2066 End of Message | 2067 The end of the compound Join/Prune message is reached. | 2069 The (S,G,rpt) downstream state machine on interface I | 2070 transitions to the NoInfo state. ET and PPT are canceled. | 2072 Notes: | 2074 Receiving a Prune(*,*,RP(G)) or Prune(*,G) does not affect the (S,G,rpt) | 2075 downstream state machine. | 2077 The HoldTime from the Join/Prune message must be larger than the 2078 J/P_Override_Interval. 2080 4.4.5. Sending (*,*,RP) Join/Prune Messages 2082 The per-interface state-machines for (*,*,RP) hold join state from | 2083 downstream PIM routers. This state then determines whether a router | 2084 needs to propagate a Join(*,*,RP) upstream towards the RP. | 2086 If a router wishes to propagate a Join(*,*,RP) upstream, it must also | 2087 watch for messages on its upstream interface from other routers on that | 2088 subnet, and these may modify its behavior. If it sees a Join(*,*,RP) to | 2089 the correct upstream neighbor, it should suppress its own Join(*,*,RP). | 2090 If it sees a Prune(*,*,RP) to the correct upstream neighbor, it should | 2091 be prepared to override that prune by sending a Join(*,*,RP) almost | 2092 immediately. Finally, if it sees the Generation ID (see Section 4.6) of | 2093 the correct upstream neighbor change, it knows that the upstream | 2094 neighbor has lost state, and it should be prepared to refresh the state | 2095 by sending a Join(*,*,RP) almost immediately. | 2097 In addition if the MRIB changes to indicate that the next hop towards | 2098 the RP has changed, the router should prune off from the old next hop, | 2099 and join towards the new next hop. | 2101 The upstream (*,*,RP) state-machine only contains two states: | 2103 Not Joined | 2104 The downstream state-machines indicate that the router does not | 2105 need to join the RP tree for this group. | 2107 Joined | 2108 The downstream state-machines indicate that the router would like | 2109 to join the RP tree for this group. | 2111 In addition, one timer JT(*,*,RP) is kept which is used to trigger the | 2112 sending of a Join(*,*,RP) to the upstream next hop towards the RP, | 2113 MRIB.next_hop(RP). | 2115 +-----------------------------------+ | 2116 | Figures omitted from text version | | 2117 +-----------------------------------+ | 2119 Figure 6: Upstream (*,*,RP) state-machine | 2121 In tabular form, the state machine is: | 2123 +----------------------+------------------------------------------------+| 2124 | | Event || 2125 Prev State +-------------------------+----------------------+| 2126 | |JoinDesired(*,*,RP)| JoinDesired(*,*,RP)| || 2127 | |->True | ->False | || 2128 +----------------------+-------------------------+----------------------+| 2129 | |-> J state | + || 2130 NotJoined (NJ) | |Send Join(*,*,RP); Set | | || 2131 | |Timer to t_periodic | | || 2132 +----------------------+-------------------------+----------------------+| 2133 Joined (J) | |- +> NJ state | || 2134 | | Send Prune(*,*,RP) || 2135 +----------------------+-------------------------+----------------------+| 2137 In addition, we have the following transitions which occur within the | 2138 Joined state: | 2140 +-----------------------------------------------------------------------+| 2141 | In Joined (J) State || 2142 +-------------------+----------------------+----------------------------+| 2143 |Timer Expires | |See | |See | || 2144 | |Join(*,*,RP) | |Prune(*,*,RP) | || 2145 | |to | |to | || 2146 | |MRIB.next_hop(RP)| |MRIB.next_hop(RP)| || 2147 +-------------------+----------------------+----------------------------+| 2148 |Send | |Increase Timer to | |Decrease Timer to | || 2149 |Join(*,*,RP); | |t_suppressed | |t_override | || 2150 |Set Timer to | | | || 2151 |t_periodic | | | || 2152 +-------------------+----------------------+----------------------------+| 2154 +-----------------------------------------------------------------------+| 2155 | In Joined (J) State || 2156 +-----------------------------------+-----------------------------------+| 2157 | topology change wrt | | MRIB.next_hop(RP) GenID | || 2158 | MRIB.next_hop(RP) | | changes | || 2159 +-----------------------------------+-----------------------------------+| 2160 | Send Join(*,*,RP) to new | | Decrease Timer to | || 2161 | next hop; Send | | t_override | || 2162 | Prune(*,*,RP) to old next | | || 2163 | hop; set Timer to | | || 2164 | t_periodic | | || 2165 +-----------------------------------+-----------------------------------+| 2166 This state machine uses the following macro: | 2168 bool JoinDesired(*,*,RP) { | 2169 if immediate_olist(*,*,RP) != NULL | 2170 return TRUE | 2171 else | 2172 return FALSE | 2173 } | 2175 JoinDesired(*,*,RP) is true when the router has received (*,*,RP) Joins | 2176 from any downstream interface. Note that although JoinDesired is true, | 2177 the router's sending of a Join(*,*,RP) message may be suppressed by | 2178 another router sending a Join(*,*,RP) onto the upstream interface. | 2180 Transitions from NotJoined State | 2182 When the upstream (*,*,RP) state-machine is in NotJoined state, the | 2183 following event may trigger a state transition: | 2185 JoinDesired(*,*,RP) becomes True | 2186 The downstream state for (*,*,RP) has changed so that at least | 2187 one interface is in immediate_olist(*,*,RP), making | 2188 JoinDesired(*,*,RP) become True. | 2190 The upstream (*,*,RP) state machine transitions to Joined | 2191 state. Send Join(*,*,RP) to the appropriate upstream | 2192 neighbor, which is MRIB.next_hop(RP). Set the Join Timer (JT) | 2193 to expire after t_periodic seconds. | 2195 Transitions from Joined State | 2197 When the upstream (*,*,RP) state-machine is in Joined state, the | 2198 following events may trigger state transitions: | 2200 JoinDesired(*,*,RP) becomes False | 2201 The downstream state for (*,*,RP) has changed so no interface | 2202 is in immediate_olist(*,*,RP), making JoinDesired(*,*,RP) | 2203 become False. | 2205 The upstream (*,*,RP) state machine transitions to NotJoined | 2206 state. Send Prune(*,*,RP) to the appropriate upstream | 2207 neighbor, which is MRIB.next_hop(RP). Cancel the Join Timer | 2208 (JT). | 2210 Join Timer Expires | 2211 The Join Timer (JT) expires, indicating time to send a | 2212 Join(*,*,RP) | 2213 Send Join(*,*,RP) to the appropriate upstream neighbor, which | 2214 is MRIB.next_hop(RP). Restart the Join Timer (JT) to expire | 2215 after t_periodic seconds. | 2217 See Join(*,*,RP) to MRIB.next_hop(RP) | 2218 This event is only relevant if RPF_interface(RP) is a shared | 2219 medium. This router sees another router on RPF_interface(RP) | 2220 send a Join(*,*,RP) to MRIB.next_hop(RP). This causes this | 2221 router to suppress its own Join. | 2223 The upstream (*,*,RP) state machine remains in Joined state. | 2224 If the Join Timer is set to expire in less than t_suppressed | 2225 seconds, reset it so that it expires after t_suppressed | 2226 seconds. If the Join Timer is set to expire in more than | 2227 t_suppressed seconds, leave it unchanged. | 2229 See Prune(*,*,RP) to MRIB.next_hop(RP) | 2230 This event is only relevant if RPF_interface(RP) is a shared | 2231 medium. This router sees another router on RPF_interface(RP) | 2232 send a Prune(*,*,RP) to MRIB.next_hop(RP). As this router is | 2233 in Joined state, it must override the Prune after a short | 2234 random interval. | 2236 The upstream (*,*,RP) state machine remains in Joined state. | 2237 If the Join Timer is set to expire in more than t_override | 2238 seconds, reset it so that it expires after t_override seconds. | 2239 If the Join Timer is set to expire in less than t_override | 2240 seconds, leave it unchanged. | 2242 Topology Change wrt MRIB.next_hop(RP) | 2243 A route changed in the routing base stored in the MRIB so that | 2244 the next hop towards the RP is a different neighbor from | 2245 before. | 2247 The upstream (*,*,RP) state machine remains in Joined state. | 2248 Send Prune(*,*,RP) to the old upstream neighbor, which is the | 2249 old value of MRIB.next_hop(RP). Send Join(*,*,RP) to the new | 2250 upstream neighbor which is the new value of MRIB.next_hop(RP). | 2251 Set the Join Timer (JT) to expire after t_periodic seconds. | 2253 MRIB.next_hop(RP) GenID changes | 2254 The Generation ID of the router that is MRIB.next_hop(RP) | 2255 changes. This normally means that this neighbor has lost | 2256 state, and so the state must be refreshed. | 2258 The upstream (*,*,RP) state machine remains in Joined state. | 2259 If the Join Timer is set to expire in more than t_override | 2260 seconds, reset it so that it expires after t_override seconds. | 2262 4.4.6. Sending (*,G) Join/Prune Messages | 2264 The per-interface state-machines for (*,G) hold join state from | 2265 downstream PIM routers. This state then determines whether a router 2266 needs to propagate a Join(*,G) upstream towards the RP. 2268 If a router wishes to propagate a Join(*,G) upstream, it must also watch | 2269 for messages on its upstream interface from other routers on that | 2270 subnet, and these may modify its behavior. If it sees a Join(*,G) to 2271 the correct upstream neighbor, it should suppress its own Join(*,G). If 2272 it sees a Prune(*,G) to the correct upstream neighbor, it should be 2273 prepared to override that prune by sending a Join(*,G) almost 2274 immediately. Finally, if it sees the Generation ID (see Section 4.6) of 2275 the correct upstream neighbor change, it knows that the upstream 2276 neighbor has lost state, and it should be prepared to refresh the state 2277 by sending a Join(*,G) almost immediately. 2279 In addition if the MRIB changes to indicate that the next hop towards 2280 the RP has changed, the router should prune off from the old next hop, 2281 and join towards the new next hop. 2283 The upstream (*,G) state-machine only contains two states: 2285 Not Joined 2286 The downstream state-machines indicate that the router does not 2287 need to join the RP tree for this group. 2289 Joined 2290 The downstream state-machines indicate that the router would like 2291 to join the RP tree for this group. 2293 In addition, one timer JT(*,G) is kept which is used to trigger the 2294 sending of a Join(*,G) to the upstream next hop towards the RP, | 2295 RPF'(*,G). | 2297 +-----------------------------------+ 2298 | Figures omitted from text version | 2299 +-----------------------------------+ 2301 Figure 7: Upstream (*,G) state-machine 2303 In tabular form, the state machine is: 2305 +---------------------+-------------------------------------------------+ 2306 | | Event | 2307 | Prev State +-------------------------+-----------------------+ 2308 | | JoinDesired(*,G) | JoinDesired(*,G) | 2309 | | ->True | ->False | 2310 +---------------------+-------------------------+-----------------------+ 2311 | | -> J state | - | 2312 | NotJoined (NJ) | Send Join(*,G); | | 2313 | | Set Timer to | | 2314 | | t_periodic | | 2315 +---------------------+-------------------------+-----------------------+ 2316 | Joined (J) | - | -> NJ state | 2317 | | | Send Prune(*,G) | 2318 +---------------------+-------------------------+-----------------------+ 2320 In addition, we have the following transitions which occur within the 2321 Joined state: 2323 +-----------------------------------------------------------------------+ 2324 | In Joined (J) State | 2325 +-----------------+-----------------+-----------------+-----------------+ 2326 |Timer Expires | See Join(*,G) | See Prune(*,G) | RPF'(*,G) | 2327 | | to RPF'(*,G) | to RPF'(*,G) | changes | 2328 +-----------------+-----------------+-----------------+-----------------+ 2329 |Send | Increase Timer | Decrease Timer | Decrease Timer | 2330 |Join(*,G); Set | to | to t_override | to t_override | 2331 |Timer to | t_suppressed | | | 2332 |t_periodic | | | | 2333 +-----------------+-----------------+-----------------+-----------------+ 2335 +-----------------------------------------------------------------------+ 2336 | In Joined (J) State | 2337 +----------------------------------+------------------------------------+ 2338 | topology change wrt | RPF'(*,G) GenID changes | 2339 | MRIB.next_hop(RP) | | 2340 +----------------------------------+------------------------------------+ 2341 | Send Join(*,G) to new | Decrease Timer to | 2342 | next hop; Send | t_override | 2343 | Prune(*,G) to old next | | 2344 | hop; set Timer to | | 2345 | t_periodic | | 2346 +----------------------------------+------------------------------------+ 2347 This state machine uses the following macro: 2349 bool JoinDesired(*,G) { 2350 if immediate_olist(*,G) != NULL | 2351 return TRUE | 2352 else | 2353 return FALSE | 2354 } | 2356 JoinDesired(*,G) is true when the router has forwarding state that would | 2357 cause it to forward traffic for G using shared tree state. Note that 2358 although JoinDesired is true, the router's sending of a Join(*,G) 2359 message may be suppressed by another router sending a Join(*,G) onto the 2360 upstream interface. 2362 Transitions from NotJoined State 2364 When the upstream (*,G) state-machine is in NotJoined state, the 2365 following event may trigger a state transition: 2367 JoinDesired(*,G) becomes True 2368 The downstream state for (*,G) has changed so that at least 2369 one interface is in immediate_olist(*,G), making 2370 JoinDesired(*,G) become True. 2372 The upstream (*,G) state machine transitions to Joined state. 2373 Send Join(*,G) to the appropriate upstream neighbor, which is 2374 RPF'(*,G). Set the Join Timer (JT) to expire after t_periodic 2375 seconds. 2377 Transitions from Joined State 2379 When the upstream (*,G) state-machine is in Joined state, the following 2380 events may trigger state transitions: 2382 JoinDesired(*,G) becomes False 2383 The downstream state for (*,G) has changed so no interface is 2384 in immediate_olist(*,G), making JoinDesired(*,G) become False. 2386 The upstream (*,G) state machine transitions to NotJoined 2387 state. Send Prune(*,G) to the appropriate upstream neighbor, 2388 which is RPF'(*,G). Cancel the Join Timer (JT). 2390 Join Timer Expires 2391 The Join Timer (JT) expires, indicating time to send a 2392 Join(*,G) 2393 Send Join(*,G) to the appropriate upstream neighbor, which is 2394 RPF'(*,G). Restart the Join Timer (JT) to expire after 2395 t_periodic seconds. 2397 See Join(*,G) to RPF'(*,G) 2398 This event is only relevant if RPF_interface(RP(G)) is a 2399 shared medium. This router sees another router on 2400 RPF_interface(RP(G)) send a Join(*,G) to RPF'(*,G). This 2401 causes this router to suppress its own Join. 2403 The upstream (*,G) state machine remains in Joined state. If 2404 the Join Timer is set to expire in less than t_suppressed 2405 seconds, reset it so that it expires after t_suppressed 2406 seconds. If the Join Timer is set to expire in more than 2407 t_suppressed seconds, leave it unchanged. 2409 See Prune(*,G) to RPF'(*,G) 2410 This event is only relevant if RPF_interface(RP(G)) is a 2411 shared medium. This router sees another router on 2412 RPF_interface(RP(G)) send a Prune(*,G) to RPF'(*,G). As this 2413 router is in Joined state, it must override the Prune after a 2414 short random interval. 2416 The upstream (*,G) state machine remains in Joined state. If 2417 the Join Timer is set to expire in more than t_override 2418 seconds, reset it so that it expires after t_override seconds. 2419 If the Join Timer is set to expire in less than t_override 2420 seconds, leave it unchanged. 2422 RPF'(*,G) changes 2423 The current net hop towards the RP changes due an Assert(*,G) 2424 on the RPF_interface(RP(G)). 2426 The upstream (*,G) state machine remains in Joined state. If 2427 the Join Timer is set to expire in more than t_override 2428 seconds, reset it so that it expires after t_override seconds. 2429 If the Join Timer is set to expire in less than t_override 2430 seconds, leave it unchanged. 2432 Topology Change wrt MRIB.next_hop(RP) 2433 A route changed in the routing base stored in the MRIB so that 2434 the next hop towards the RP is a different neighbor from 2435 before. 2437 The upstream (*,G) state machine remains in Joined state. 2438 Send Prune(*,G) to the old upstream neighbor, which is the old 2439 value of RPF'(*,G). Send Join(*,G) to the new upstream 2440 neighbor which is the new value of RPF(*,G). Note that the 2441 Join goes to RPF(*,G) and not RPF'(*,G) even if the new 2442 neighbor is on the same interface as the old one because the 2443 routing change may cause the assert state to be incorrect. Set 2444 the Join Timer (JT) to expire after t_periodic seconds. 2446 RPF'(*,G) GenID changes 2447 The Generation ID of the router that is RPF'(*,G) changes. 2448 This normally means that this neighbor has lost state, and so 2449 the state must be refreshed. 2451 The upstream (*,G) state machine remains in Joined state. If 2452 the Join Timer is set to expire in more than t_override 2453 seconds, reset it so that it expires after t_override seconds. 2455 4.4.7. Sending (S,G) Join/Prune Messages 2457 The per-interface state-machines for (S,G) hold join state from 2458 downstream PIM routers. This state then determines whether a router 2459 needs to propagate a Join(S,G) upstream towards the source. 2461 If a router wishes to propagate a Join(S,G) upstream, it must also watch 2462 for messages on its upstream interface from other routers on that 2463 subnet, and these may modify its behavior. If it sees a Join(S,G) to 2464 the correct upstream neighbor, it should suppress its own Join(S,G). If 2465 it sees a Prune(S,G), Prune(S,G,rpt), or Prune(*,G) to the correct 2466 upstream neighbor towards S, it should be prepared to override that 2467 prune by scheduling a Join(S,G) to be sent (almost) immediately. 2468 Finally, if it sees the Generation ID of its upstream neighbor change, 2469 it knows that the upstream neighbor has lost state, and it should 2470 refresh the state by scheduling a Join(S,G) to be sent (almost) 2471 immediately. 2473 In addition if MRIB changes cause the next hop towards the source to 2474 change, the router should send a prune to the old next hop, and a join 2475 to the new next hop. 2477 The upstream (S,G) state-machine only contains two states: 2479 Not Joined 2480 The downstream state machines and IGMP information do not indicate 2481 that the router needs to join the shortest-path tree for this 2482 (S,G). 2484 Joined 2485 The downstream state machines and IGMP information indicate that 2486 the router should join the shortest-path tree for this (S,G). 2488 In addition, one timer JT(S,G) is kept which is used to trigger the 2489 sending of a Join(S,G) to the upstream next hop toward S, RPF'(S,G). | 2491 +-----------------------------------+ 2492 | Figures omitted from text version | 2493 +-----------------------------------+ 2495 Figure 8: Upstream (S,G) state-machine 2497 In tabular form, the state machine is: 2499 +--------------------++-------------------------------------------------+ 2500 | || Event | 2501 | Prev State ++-----------------------+-------------------------+ 2502 | || JoinDesired(S,G) | JoinDesired(S,G) | 2503 | || ->True | ->False | 2504 +--------------------++-----------------------+-------------------------+ 2505 | NotJoined (NJ) || -> J state | - | 2506 | || Send Join(S,G); | | 2507 | || Set Timer to | | 2508 | || t_periodic | | 2509 +--------------------++-----------------------+-------------------------+ 2510 | Joined (J) || - | -> NJ state | 2511 | || | Send Prune(S,G); | 2512 | || | Set SPTbit(S,G) to | 2513 | || | FALSE | 2514 +--------------------++-----------------------+-------------------------+ 2515 In addition, we have the following transitions which occur within the 2516 Joined state: 2518 +-----------------------------------------------------------------------+ 2519 | In Joined (J) State | 2520 +-----------------+-----------------+-----------------+-----------------+ 2521 |Timer Expires | See Join(S,G) | See Prune(S,G) | See Prune | 2522 | | to RPF'(S,G) | to RPF'(S,G) | (S,G,rpt) to | 2523 | | | | RPF'(S,G) | 2524 +-----------------+-----------------+-----------------+-----------------+ 2525 |Send | Increase Timer | Decrease Timer | Decrease Timer | 2526 |Join(S,G); Set | to t_suppr | to t_override | to t_override | 2527 |Timer to | | | | 2528 |t_periodic | | | | 2529 +-----------------+-----------------+-----------------+-----------------+ 2531 +-----------------------------------------------------------------------+ 2532 | In Joined (J) State | 2533 +----------------------+-------------------------+----------------------+ 2534 | See Prune(*,G) to | topology change | RPF'(S,G) GenID | 2535 | RPF'(S,G) | wrt | changes | 2536 | | MRIB.next_hop(S) | | 2537 +----------------------+-------------------------+----------------------+ 2538 | Decrease Timer to | Send Join(S,G) to | Decrease Timer to | 2539 | t_override | new next hop; Send | t_override | 2540 | | Prune(S,G) to old | | 2541 | | next hop; Set | | 2542 | | Timer to | | 2543 | | t_periodic | | 2544 +----------------------+-------------------------+----------------------+ 2546 This state machine uses the following macro: 2548 bool JoinDesired(S,G) { 2549 return( immediate_olist(S,G) != NULL 2550 OR ( KeepaliveTimer(S,G) is running 2551 AND inherited_olist(S,G) != NULL ) ) 2552 } 2554 JoinDesired(S,G) is true when the router has forwarding state that would | 2555 cause it to forward traffic for G using source tree state. The source | 2556 tree state can either be as a result of active source-specific join | 2557 state, or the (S,G) keepalive timer and active non-source-specific | 2558 state. Note that although JoinDesired is true, the router's sending of a | 2559 Join(S,G) message may be suppressed by another router sending a | 2560 Join(S,G) onto the upstream interface. | 2561 Transitions from NotJoined State | 2563 When the upstream (S,G) state-machine is in NotJoined state, the | 2564 following event may trigger a state transition: | 2566 JoinDesired(S,G) becomes True | 2567 The downstream state for (S,G) has changed so that at least | 2568 one interface is in inherited_olist(S,G), making | 2569 JoinDesired(S,G) become True. | 2571 The upstream (S,G) state machine transitions to Joined state. | 2572 Send Join(S,G) to the appropriate upstream neighbor, which is | 2573 RPF'(S,G). Set the Join Timer (JT) to expire after t_periodic | 2574 seconds. | 2576 Transitions from Joined State | 2578 When the upstream (S,G) state-machine is in Joined state, the following | 2579 events may trigger state transitions: | 2581 JoinDesired(S,G) becomes False | 2582 The downstream state for (S,G) has changed so no interface is | 2583 in inherited_olist(S,G), making JoinDesired(S,G) become False. | 2585 The upstream (S,G) state machine transitions to NotJoined | 2586 state. Send Prune(S,G) to the appropriate upstream neighbor, | 2587 which is RPF'(S,G). Cancel the Join Timer (JT). | 2589 Join Timer Expires | 2590 The Join Timer (JT) expires, indicating time to send a | 2591 Join(S,G) | 2593 Send Join(S,G) to the appropriate upstream neighbor, which is | 2594 RPF'(S,G). Restart the Join Timer (JT) to expire after | 2595 t_periodic seconds. | 2597 See Join(S,G) to RPF'(S,G) | 2598 This event is only relevant if RPF_interface(S) is a shared | 2599 medium. This router sees another router on RPF_interface(S) | 2600 send a Join(S,G) to RPF'(S,G). This causes this router to | 2601 suppress its own Join. | 2603 The upstream (S,G) state machine remains in Joined state. If | 2604 the Join Timer is set to expire in less than t_suppressed | 2605 seconds, reset it so that it expires after t_suppressed | 2606 seconds. If the Join Timer is set to expire in more than | 2607 t_suppressed seconds, leave it unchanged. | 2609 See Prune(S,G) to RPF'(S,G) | 2610 This event is only relevant if RPF_interface(S) is a shared | 2611 medium. This router sees another router on RPF_interface(S) | 2612 send a Prune(S,G) to RPF'(S,G). As this router is in Joined | 2613 state, it must override the Prune after a short random | 2614 interval. | 2616 The upstream (S,G) state machine remains in Joined state. If | 2617 the Join Timer is set to expire in more than t_override | 2618 seconds, reset it so that it expires after t_override seconds. | 2620 See Prune(S,G,rpt) to RPF'(S,G) | 2621 This event is only relevant if RPF_interface(S) is a shared | 2622 medium. This router sees another router on RPF_interface(S) | 2623 send a Prune(S,G,rpt) to RPF'(S,G). If the upstream router is | 2624 an RFC 2362 compliant PIM router, then the Prune(S,G,rpt) will | 2625 cause it to stop forwarding. For backwards compatibility, | 2626 this router should override the prune so that forwarding | 2627 continues. | 2629 The upstream (S,G) state machine remains in Joined state. If | 2630 the Join Timer is set to expire in more than t_override | 2631 seconds, reset it so that it expires after t_override seconds. | 2633 See Prune(*,G) to RPF'(S,G) | 2634 This event is only relevant if RPF_interface(S) is a shared | 2635 medium. This router sees another router on RPF_interface(S) | 2636 send a Prune(*,G) to RPF'(S,G). If the upstream router is an | 2637 RFC 2362 compliant PIM router, then the Prune(*,G) will cause | 2638 it to stop forwarding. For backwards compatibility, this | 2639 router should override the prune so that forwarding continues. | 2641 The upstream (S,G) state machine remains in Joined state. If | 2642 the Join Timer is set to expire in more than t_override | 2643 seconds, reset it so that it expires after t_override seconds. | 2645 RPF'(S,G) changes | 2646 The current net hop towards the RP changes due an Assert(S,G) | 2647 on the RPF_interface(S). | 2649 The upstream (S,G) state machine remains in Joined state. If | 2650 the Join Timer is set to expire in more than t_override | 2651 seconds, reset it so that it expires after t_override seconds. | 2652 If the Join Timer is set to expire in less than t_override | 2653 seconds, leave it unchanged. | 2655 Topology Change wrt MRIB.next_hop(S) | 2656 A route changed in the routing base stored in the MRIB so that | 2657 the next hop towards S is a different neighbor from before. | 2659 The upstream (S,G) state machine remains in Joined state. | 2660 Send Prune(S,G) to the old upstream neighbor, which is the old | 2661 value of RPF'(S,G). Send Join(S,G) to the new upstream | 2662 neighbor which is the new value of RPF(S,G). Note that the | 2663 Join goes to RPF(S,G) and not RPF'(S,G) even if the new | 2664 neighbor is on the same interface as the old one because the | 2665 routing change may cause the assert state to be incorrect. Set | 2666 the Join Timer (JT) to expire after t_periodic seconds. | 2668 RPF'(S,G) GenID changes | 2669 The Generation ID of the router that is RPF'(S,G) changes. | 2670 This normally means that this neighbor has lost state, and so | 2671 the state must be refreshed. | 2673 The upstream (S,G) state machine remains in Joined state. If | 2674 the Join Timer is set to expire in more than t_override | 2675 seconds, reset it so that it expires after t_override seconds. | 2677 4.4.8. (S,G,rpt) Periodic Messages 2679 (S,G,rpt) Joins and Prunes are (S,G) Joins or Prunes sent on the RP tree 2680 with the RPT bit set, either to modify the results of (*,G) Joins, or to 2681 override the behavior of other upstream LAN peers. The next section 2682 describes the rules for sending triggered messages. This section 2683 describes the rules for including an Prune(S,G,rpt) message with a 2684 Join(*,G). 2686 When a router is going to send a Join(*,G), it should use the following 2687 pseudocode, for each (S,G) for which it has state, to decide whether to 2688 include a Prune(S,G,rpt) in the compound Join/Prune message: 2690 if( SPTbit(S,G) == TRUE ) { 2691 # Note: If receiving (S,G) on the SPT, we only prune off the 2692 # shared tree if the rpf neighbors differ. 2693 if( RPF'(*,G) != RPF'(S,G) ) { 2694 add Prune(S,G,rpt) to compound message 2695 } 2696 } else if ( inherited_olist(S,G,rpt) == NULL ) { 2697 # Note: all (*,G) olist interfaces sent rpt prunes for (S,G). 2698 add Prune(S,G,rpt) to compound message 2699 } else if ( RPF'(*,G) != RPF'(S,G,rpt) { 2700 # Note: we joined the shared tree, but there was an (S,G) assert and 2701 # the source tree RPF neighbor is different. 2702 add Prune(S,G,rpt) to compound message 2703 } 2705 Note that Join(S,G,rpt) is not normally sent as a periodic message, but 2706 only as a triggered message. 2708 4.4.9. State Machine for (S,G,rpt) Triggered Messages 2710 The state machine for (S,G,rpt) triggered messages is required per-(S,G) | 2711 when there is (*,G) or (*,*,RP) join state at a router, and the router | 2712 or any of its upstream LAN peers wishes to prune S off the RP tree. | 2713 There are three states in the state-machine. One of the states is when | 2714 there is neither (*,G) nor (*,*,RP(G)) join state at this router. If | 2715 there is (*,G) or (*,*,RP(G)) join state at the router, then the state | 2716 machine must be at one of the other two states: | 2718 Pruned(S,G,rpt) | 2719 (*,G) or (*,*,RP(G)) Joined, but (S,G,rpt) pruned | 2721 NotPruned(S,G,rpt) | 2722 (*,G) or (*,*,RP(G)) Joined, and (S,G,rpt) not pruned | 2724 RPTNotJoined(G) | 2725 neither (*,G) nor (*,*,RP(G)) has not been joined. | 2727 In addition there is an (S,G,rpt) Override Timer, OT(S,G,rpt), which is | 2728 used to delay triggered Join(S,G,rpt) messages to prevent implosions of | 2729 triggered messages. | 2731 +-----------------------------------+ 2732 | Figures omitted from text version | 2733 +-----------------------------------+ 2735 Figure 9: Upstream (S,G,rpt) state-machine for triggered messages 2737 In tabular form, the state machine is: 2739 +-------------++---------------------------------------------------------------+ 2740 | || Event | 2741 | ++-------------+-------------+------------------+----------------+ 2742 |Prev State |PruneDesired |PruneDesired |RPTJoinDesired(G) |inherited_olist | 2743 | |(S,G,rpt) |(S,G,rpt) |->False |(S,G,rpt) | 2744 | |->True |->False | |->non-NULL | 2745 +-------------++-------------+-------------+------------------+----------------+ 2746 |RPTNotJoined |+> P state |- |- |-> NP state | 2747 |(G) (NJ) || | | | | 2748 +-------------++-------------+-------------+------------------+----------------+ 2749 |Pruned |+ |-> NP state |-> NJ state |- | 2750 |(S,G,rpt) (P)|| |Send Join | | | 2751 | || |(S,G,rpt) | | | 2752 +-------------++-------------+-------------+------------------+----------------+ 2753 |NotPruned |+> P state |- |-> NJ state |- | 2754 |(S,G,rpt) |Send Prune | | | | 2755 |(NP) |(S,G,rpt); | | | | 2756 | |Stop OT timer | | | | 2757 +-------------++-------------+-------------+------------------+----------------+ 2758 Additionally, we have the following transitions within the 2759 NotPruned(S,G,rpt) state which are all used for prune override behavior. 2761 +-----------------------------------------------------------------------+ 2762 | In NotPruned(S,G,rpt) State | 2763 +------------+--------------+---------------+------------+--------------+ 2764 |OT timer |See Prune | See Join |See Prune | RPF' | 2765 |expires |(S,G,rpt) to | (S,G,rpt) to |(S,G) to | (S,G,rpt) -> | 2766 | |RPF' | RPF' |RPF' | RPF' (*,G) | 2767 | |(S,G,rpt) | (S,G,rpt) |(S,G,rpt) | | 2768 +------------+--------------+---------------+------------+--------------+ 2769 |Send Join |OT timer = | stop OT |OT timer = | OT timer = | 2770 |(S,G,rpt); |min(timer, | timer |min(timer, | min(timer, | 2771 |Stop OT |t_po) | |t_po) | t_po) | 2772 |timer | | | | | 2773 +------------+--------------+---------------+------------+--------------+ 2775 Note that the min function in the above state machine considers a non- | 2776 running timer to have an infinite value (e.g. min(not-running, t_po) = | 2777 t_po). | 2778 This state machine uses the following macros: | 2780 bool RPTJoinDesired(G) { | 2781 return (JoinDesired(*,G) || JoinDesired(*,*,RP(G))) | 2782 } | 2784 RPTJoinDesired(G) is true when the router has forwarding state that | 2785 would cause it to forward traffic for G using either (*,G) or (*,*,RP) | 2786 shared tree state. | 2788 bool PruneDesired(S,G,rpt) { | 2789 return ( RPTJoinDesired(G) AND | 2790 ( inherited_olist(S,G,rpt) == NULL | 2791 OR (SPTbit(S,G)==TRUE | 2792 AND (RPF'(*,G) != RPF'(S,G)) ))) | 2793 } | 2795 PruneDesired(S,G,rpt) can only be true if RPTJoinDesired(G) is true. If | 2796 RPTJoinDesired(G) is true, then PruneDesired(S,G,rpt) is true if either | 2797 there are no outgoing interfaces that S would be forwarded on, or if the | 2798 router has active (S,G) forwarding state but RPF'(*,G) != RPF'(S,G). | 2800 The state machine contains the following transition events: | 2802 See Join(S,G,rpt) to RPF'(S,G,rpt) | 2803 This event is only relevant in the "Not Pruned" state. | 2805 The router sees a Join(S,G,rpt) from someone else to RPF'(S,G,rpt), | 2806 which is the correct upstream neighbor. If we're in "NotPruned" | 2807 state and the (S,G,rpt) override timer is running, then this is | 2808 because we have been triggered to send our own Join(S,G,rpt) to | 2809 RPF'(S,G,rpt). Someone else beat us to it, so there's no need to | 2810 send our own Join. | 2812 The action is to cancel the override timer. 2814 See Prune(S,G,rpt) to RPF'(S,G,rpt) 2815 This event is only relevant in the "NotPruned" state. 2817 The router sees a Prune(S,G,rpt) from someone else to to 2818 RPF'(S,G,rpt), which is the correct upstream neighbor. If we're in 2819 the "NotPruned" state, then we want to continue to receive traffic 2820 from S destined for G, and that traffic is being supplied by 2821 RPF'(S,G,rpt). Thus we need to override the Prune. 2823 The action is to set the (S,G,rpt) time to the randomized prune- | 2824 override interval. However if the override timer is already | 2825 running, we only set the timer if doing so would set it to a lower | 2826 value. At the end of this interval, if no-one else has sent a | 2827 Join, then we will do so. | 2829 See Prune(S,G) to RPF'(S,G,rpt) 2830 This event is only relevant in the "NotPruned" state. 2832 This transition and action are the same as the above transition and 2833 action, except that the Prune does not have the RPT bit set. This 2834 transition is necessary to be compatible with existing routers that 2835 don't maintain separate (S,G) and (S,G,rpt) state. 2837 The (S,G,rpt) prune override timer expires 2838 This event is only relevant in the "NotPruned" state. 2840 When the override timer expires, we must send a Join(S,G,rpt) to | 2841 RPF'(S,G,rpt) to override the Prune message that caused the timer 2842 to be running. We only send this if RPF'(S,G,rpt) equals RPF'(*,G) 2843 - if this were not the case, then the Join might be sent to a 2844 router that does not have (*,G) or (*,*,RP(G)) Join state, and so | 2845 the behavior would not be well defined. If RPF'(S,G,rpt) is not | 2846 the same as RPF'(*,G), then it may stop forwarding S. However, if | 2847 this happens, then the router will send an AssertCancel(S,G), which | 2848 would then cause RPF'(S,G,rpt) to become equal to RPF'(*,G) (see | 2849 below). | 2851 RPF'(S,G,rpt) changes to become equal to RPF'(*,G) 2852 This event is only relevant in the "NotPruned" state. 2854 RPF'(S,G,rpt) can only be different from RPF'(*,G) if an (S,G) 2855 Assert has happened, which means that traffic from S is arriving on 2856 the SPT, and so Prune(S,G,rpt) will have been sent to RPF'(*,G). 2857 When RPF'(S,G,rpt) changes to become equal to RPF'(*,G), we need to 2858 trigger a Join(S,G,rpt) to RPF'(*,G) to cause that router to start 2859 forwarding S again. 2861 The action is to set the (S,G,rpt) override timer to the randomized | 2862 prune-override interval. However if the timer is already running, 2863 we only set the timer if doing so would set it to a lower value. 2864 At the end of this interval, if no-one else has sent a Join, then 2865 we will do so. 2867 PruneDesired(S,G,rpt)->TRUE 2868 See macro above. 2870 The router wishes to receive traffic for G, but does not wish to 2871 receive traffic from S destined for G. This causes the router to 2872 transition into the Pruned state. 2874 If the router was previously in NotPruned state, then the action is 2875 to send a Prune(S,G,rpt) to RPF'(S,G,rpt). If the router was 2876 previously in RPTNotJoined(G) state, then there is no need to | 2877 trigger an action in this state machine because sending a | 2878 Prune(S,G,rpt) is handled by the rules for sending the Join(*,G) or 2879 Join(*,*,RP). 2881 PruneDesired(S,G,rpt)->FALSE 2882 See macro above. This transition is only relevant in the "Pruned" 2883 state. 2885 If the router is in the Pruned(S,G,rpt) state, and 2886 PruneDesired(S,G,rpt) changes to FALSE, this could be because the | 2887 router no longer has RPTJoinDesired(G) true, or it now wishes to | 2888 receive traffic from S again. If it is the former, then this | 2889 transition should not happen, but instead the | 2890 "RPTJoinDesired(G)->FALSE" transition should happen. Thus this | 2891 transition should be interpreted as "PruneDesired(S,G,rpt)->FALSE | 2892 AND RPTJoinDesired(G)==TRUE" | 2894 The action is to send a Join(S,G,rpt) to RPF'(S,G,rpt). 2896 RPTJoinDesired(G)->FALSE 2897 The router no longer wishes to receive any traffic destined for G 2898 on the RP Tree. This causes a transition to the RPTNotJoined(G) | 2899 state. Any actions are handled by the appropriate upstream state | 2900 machine for (*,G) or (*,*,RP). | 2902 inherited_olist(S,G,rpt) becomes non-NULL | 2903 This transition is only relevant in the RPTNotJoined(G) state. | 2905 The router has joined the RP tree (handled by the (*,G) or (*,*,RP) | 2906 upstream state machine as appropriate), and wants to receive | 2907 traffic from S. This does not trigger any events in this state | 2908 machine, but causes a transition to the NotPruned(S,G,rpt) state. | 2910 4.5. PIM Assert Messages 2912 4.5.1. (S,G) Assert Message State Machine 2914 The (S,G) Assert state machine for interface I is shown in Figure 10. 2915 There are three states: 2917 NoInfo (NI) 2918 This router has no (S,G) assert state on interface I. 2920 I am Assert Winner (W) 2921 This router has won an (S,G) assert on interface I. It is now | 2922 responsible for forwarding traffic from S destined for G out of | 2923 interface I. Irrespective of whether it is the DR for I, while a 2924 router is the assert winner, it is also responsible for forwarding 2925 traffic onto I on behalf of local hosts on I that have made 2926 membership requests that specifically refer to S (and G). 2928 I am Assert Loser (L) 2929 This router has lost an (S,G) assert on interface I. It must not 2930 forward packets from S destined for G onto interface I. If it is 2931 the DR on I, it is no longer responsible for forwarding traffic 2932 onto I to satisfy local hosts with membership requests that 2933 specifically refer to S and G. 2935 In addition there is also a assert timer (AT) that is used to time out 2936 asserts on the assert losers and to resend asserts on the assert winner. 2938 +-----------------------------------+ 2939 | Figures omitted from text version | 2940 +-----------------------------------+ 2942 Figure 10: Per-interface (S,G) Assert State-machine 2944 In tabular form the state machine is: 2946 +-----------------------------------------------------------------------+ 2947 | In NoInfo (NI) State | 2948 +---------------+-------------------+------------------+----------------+ 2949 | Receive | Receive Assert | Data arrives | Receive | 2950 | Inferior | with RPTbit | from S to G on | Preferred | 2951 | Assert with | set and | I and | Assert with | 2952 | RPTbit clear | CouldAssert | CouldAssert | RPTbit clear | 2953 | and | (S,G,I) | (S,G,I) | and AssTrDes | 2954 | CouldAssert | | | (S,G,I) | 2955 | (S,G,I) | | | | 2956 +---------------+-------------------+------------------+----------------+ 2957 | -> W state | -> W state | -> W state | -> L state | 2958 | [Actions A1] | [Actions A1] | [Actions A1] | [Actions A6] | 2959 +---------------+-------------------+------------------+----------------+ 2961 +-----------------------------------------------------------------------+ 2962 | In I Am Assert Winner (W) State | 2963 +-----------------+-----------------+------------------+----------------+ 2964 | Timer Expires | Receive | Receive | CouldAssert | 2965 | | Inferior | Preferred | (S,G,I) -> | 2966 | | Assert | Assert | FALSE | 2967 +-----------------+-----------------+------------------+----------------+ 2968 | -> W state | -> W state | -> L state | -> NI state | 2969 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 2970 +-----------------+-----------------+------------------+----------------+ 2972 +-----------------------------------------------------------------------+ 2973 | In I Am Assert Loser (L) State | 2974 +---------------+-------------------+-----------------+-----------------+ 2975 | Receive | Receive | Timer Expires | AssTrDes | 2976 | Preferred | Inferior | | (S,G,I) -> | 2977 | Assert | Assert from | | FALSE | 2978 | | Current Winner | | | 2979 +---------------+-------------------+-----------------+-----------------+ 2980 | -> L state | -> NI state | -> NI state | -> NI state | 2981 | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 2982 +---------------+-------------------+-----------------+-----------------+ 2983 +-----------------------------------------------------------------------+ 2984 | In I Am Assert Loser (L) State | 2985 +----------------+-----------------+-----------------+------------------+ 2986 | my_metric -> | RPF interface | Receive | Receive Assert | 2987 | better than | stops being I | Join(S,G) on | from Current | 2988 | winner's | | interface I | Winner | 2989 | metric | | | | 2990 +----------------+-----------------+-----------------+------------------+ 2991 | -> NI state | -> NI state | -> NI State | -> L state | 2992 | [Actions A5] | [Actions A5] | [Actions A5] | [Actions A2] | 2993 +----------------+-----------------+-----------------+------------------+ 2995 Note that for reasons of compactness, "AssTrDes(S,G,I)" is used in the 2996 state-machine table to refer to AssertTrackingDesired(S,G,I). 2998 Terminology: 2999 A "preferred assert" is one with a better metric than the current 3000 winner. 3002 An "inferior assert" is one with a worse metric than | 3003 my_assert_metric(S,G,I). | 3005 The state machine uses the following macros: 3007 CouldAssert(S,G,I) = | 3008 SPTbit(S,G)==TRUE | 3009 AND (RPF_interface(S) != I) | 3010 AND (I in ( ( joins(*,G) (-) prunes(S,G,rpt) ) | 3011 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) | 3012 (-) lost_assert(*,G) | 3013 (+) joins(S,G) (+) pim_include(S,G) ) ) | 3015 CouldAssert(S,G,I) is true for downstream interfaces which would be in | 3016 the inherited_olist(S,G) if (S,G) assert information was not taken into | 3017 account. | 3018 AssertTrackingDesired(S,G,I) = 3019 (I in ( ( joins(*,G) (-) prunes(S,G,rpt) ) 3020 (+) ( pim_include(*,G) (-) pim_exclude(S,G) ) 3021 (-) lost_assert(*,G) 3022 (+) joins(S,G) (+) pim_include(S,G) ) ) 3023 OR (RPF_interface(S)==I AND JoinDesired(S,G)==TRUE) 3024 OR (RPF_interface(RP)==I AND JoinDesired(*,G)==TRUE 3025 AND SPTbit(S,G)==FALSE) 3027 AssertTrackingDesired(S,G,I) is true on any interface in which an (S,G) 3028 assert might affect our behavior. 3030 The first three lines of AssertTrackingDesired account for (*,G) join | 3031 information received on I that might cause the router to be interested | 3032 in asserts on I. | 3034 The 4th line accounts for (S,G) join information received on I that 3035 might cause the router to be interested in asserts on I. 3037 The last three lines account for the fact that a router must keep track | 3038 of assert information on upstream interfaces in order to send joins and | 3039 prunes to the proper neighbor. | 3041 Transitions from NoInfo State 3043 When in NoInfo state, the following events may trigger transitions: | 3045 Receive Inferior Assert with RPTbit cleared 3046 An assert is received for (S,G) with the RPT bit cleared that 3047 is inferior to our own assert metric. The RPT bit cleared 3048 indicates that the sender of the assert had (S,G) forwarding 3049 state on this interface. If the assert is inferior to our 3050 metric, then we must also have (S,G) forwarding state as (S,G) 3051 asserts beat (*,G) asserts, and so we should be the assert 3052 winner. We transition to the "I am Assert Winner" state, and 3053 perform Actions A1 (below). 3055 Receive Assert with RPTbit set AND CouldAssert(S,G,I)==TRUE 3056 An assert is received for (S,G) on I with the RPT bit set 3057 (it's a (*,G) assert). CouldAssert(S,G,I) is TRUE only if we 3058 have (S,G) forwarding state on this interface, so we should be 3059 the assert winner. We transition to the "I am Assert Winner" 3060 state, and perform Actions A1 (below). 3062 An (S,G) data packet arrives on interface I, AND 3063 CouldAssert(S,G,I)==TRUE 3064 An (S,G) data packet arrived on an downstream interface which 3065 is in our (S,G) outgoing interface list. We optimistically 3066 assume that we will be the assert winner for this (S,G), and 3067 so we transition to the "I am Assert Winner" state, and | 3068 perform Actions A1 (below) which will initiate the assert | 3069 negotiation for (S,G). | 3071 Receive Preferred Assert with RPT bit clear AND 3072 AssertTrackingDesired(S,G,I)==TRUE 3073 We're interested in (S,G) Asserts, either because I is a 3074 downstream interface for which we have (S,G) or (*,G) 3075 forwarding state, or because I is the upstream interface for S 3076 and we have (S,G) forwarding state. The received assert that 3077 has a better metric than our own, so we do not win the Assert. 3078 We transition to "I am Assert Loser" and perform actions A2 | 3079 (below). | 3081 Transitions from Winner State 3083 When in "I am Assert Winner" state, the following events trigger | 3084 transitions: | 3086 Timer Expires 3087 The (S,G) assert timer expires. As we're in the Winner state, 3088 then we must still have (S,G) forwarding state that is 3089 actively being kept alive. We re-send the (S,G) Assert and 3090 restart the timer (Action A3 below). Note that the assert 3091 winner's timer is engineered to expire shortly before timers 3092 on assert losers; this prevents unnecessary thrashing of the 3093 forwarder and periodic flooding of duplicate packets. 3095 Receive Inferior Assert 3096 We receive an (S,G) assert or (*,G) assert mentioning S that 3097 has a worse metric than our own. Whoever sent the assert is 3098 in error, and so we re-send an (S,G) Assert, and restart the 3099 timer (Action A3 below). 3101 Receive Preferred Assert 3102 We receive an (S,G) assert that has a better metric than our 3103 own. We transition to "I am Assert Loser" state and perform 3104 actions A2 (below). Note that this may affect the value of | 3105 JoinDesired(S,G) which could cause transitions in the upstream | 3106 (S,G) state machine. 3108 CouldAssert(S,G,I) -> FALSE 3109 Our (S,G) forwarding state or RPF interface changed so as to 3110 make CouldAssert(S,G,I) become false. We can no longer 3111 perform the actions of the assert winner, and so we transition 3112 to NoInfo state and perform actions A4 (below). This includes 3113 sending a "cancelling assert" with an infinite metric. 3115 Transitions from Loser State 3117 When in "I am Assert Loser" state, the following transitions can occur: 3119 Receive Preferred Assert 3120 We receive an assert that is better than that of the current 3121 assert winner. We stay in Loser state, and perform actions A2 3122 below. 3124 Receive Inferior Assert from Current Winner 3125 We receive an assert from the current assert winner that is 3126 worse than our own metric for this group (typically the 3127 winner's metric became worse). We transition to NoInfo state, 3128 deleting the (S,G) assert information and allowing the normal 3129 PIM Join/Prune mechanisms to operate. Usually we will 3130 eventually re-assert and win when data packets from S have 3131 started flowing again. 3133 Timer Expires 3134 The (S,G) assert timer expires. We transition to NoInfo 3135 state, deleting the (S,G) assert information. 3137 AssertTrackingDesired(S,G,I)->FALSE 3138 AssertTrackingDesired(S,G,I) becomes FALSE. Our forwarding 3139 state has changed so that (S,G) Asserts on interface I are no 3140 longer of interest to us. We transition to the NoInfo state, 3141 deleting the (S,G) assert information. 3143 My metric becomes better than the assert winner's metric 3144 My routing metrics have changed so that now my assert metric 3145 for (S,G) is better than the metric we have stored for current 3146 assert winner. We transition to NoInfo state, delete this 3147 (S,G) assert state, and allow the normal PIM Join/Prune 3148 mechanisms to operate. Usually we will eventually re-assert 3149 and win when data packets from S have started flowing again. 3151 RPF interface changed away from interface I 3152 Interface I used to be the RPF interface for S, and now it is 3153 not. We transition to NoInfo state, delete this (S,G) assert 3154 state. 3156 Receive Join(S,G) 3157 We receive a Join(S,G) directed to my IP address in interface 3158 I. The action is to transition to NoInfo state, and delete 3159 this (S,G) assert state, and allow the normal PIM Join/Prune 3160 mechanisms to operate. If whoever sent the Join was in error, 3161 then the normal assert mechanism will eventually re-apply and 3162 we will lose the assert again. However whoever sent the 3163 assert may know that the previous assert winner has died, and 3164 so we may end up being the new forwarder. 3166 (S,G) Assert State-machine Actions 3168 A1: Send Assert(S,G) 3169 Set timer to (Assert_Time - Assert_Override_Interval) 3170 Store self as AssertWinner 3172 A2: Store new assert winner | 3173 Set timer to Assert_Time 3175 A3: Send Assert(S,G) 3176 Set timer to (Assert_Time - Assert_Override_Interval) 3178 A4: Send AssertCancel(S,G) 3179 Delete assert info 3181 A5: Delete assert info 3183 A6: Store new assert winner 3184 Set timer to Assert_Time 3185 If I is RPF_interface(S) Set SPTbit(S,G) to TRUE. 3187 4.5.2. (*,G) Assert Message State Machine 3189 The (*,G) Assert state-machine for interface I is shown in Figure 11. 3190 There are three states: 3192 NoInfo (NI) 3193 This router has no (*,G) assert state on interface I. 3195 I am Assert Winner (W) 3196 This router has won an (*,G) assert on interface I. It is now 3197 responsible for forwarding traffic destined for G onto interface I 3198 with the exception of traffic for which it has (S,G) "I am Assert 3199 Loser" state. Irrespective of whether it is the DR for I, it is 3200 also responsible for handling the membership requests for G from 3201 local hosts on I. 3203 I am Assert Loser (L) 3204 This router has lost an (*,G) assert on interface I. It must not 3205 forward packets for G onto interface I with the exception of 3206 traffic from sources for which is has (S,G) "I am Assert Winner" 3207 state. If it is the DR, it is no longer responsible for handling 3208 the membership requests for group G from local hosts on I. 3210 In addition there is also an assert timer (AT) that is used to time out 3211 asserts on the assert losers and to resend asserts on the assert winner. 3213 It is important to note that no transition occurs in the (*,G) state | 3214 machine as a result of receiving an assert message if the (S,G) assert 3215 state machine for the relevant S and G is not in the "NoInfo" state. 3217 +-----------------------------------+ 3218 | Figures omitted from text version | 3219 +-----------------------------------+ 3221 Figure 11: (*,G) Assert State-machine 3223 In tabular form the state machine is: 3225 +-----------------------------------------------------------------------+ 3226 | In NoInfo (NI) State | 3227 +-----------------------+-----------------------+-----------------------+ 3228 | Receive Inferior | Data arrives for G | Receive Preferred | 3229 | Assert with RPTbit | and CouldAssert | Assert with RPTbit | 3230 | set | (*,G,I) | set and AssTrDes | 3231 | | | (*,G,I) | 3232 +-----------------------+-----------------------+-----------------------+ 3233 | -> Winner state | -> Winner state | -> Loser state | 3234 | [Actions A1] | [Actions A1] | [Actions A2] | 3235 +-----------------------+-----------------------+-----------------------+ 3237 +-----------------------------------------------------------------------+ 3238 | In I Am Assert Winner (W) State | 3239 +-----------------+-----------------+------------------+----------------+ 3240 | Timer Expires | Receive | Receive | CouldAssert | 3241 | | Inferior | Preferred | (*,G,I) -> | 3242 | | Assert | Assert | FALSE | 3243 +-----------------+-----------------+------------------+----------------+ 3244 | -> W state | -> W state | -> L state | -> NI state | 3245 | [Actions A3] | [Actions A3] | [Actions A2] | [Actions A4] | 3246 +-----------------+-----------------+------------------+----------------+ 3248 +-----------------------------------------------------------------------+ 3249 | In I Am Assert Loser (L) State | 3250 +---------------+-------------------+-----------------+-----------------+ 3251 | Receive | Receive | Timer Expires | AssTrDes | 3252 | Preferred | Inferior | | (*,G,I) -> | 3253 | Assert | Assert from | | FALSE | 3254 | | Current Winner | | | 3255 +---------------+-------------------+-----------------+-----------------+ 3256 | -> L state | -> NI state | -> NI state | -> NI state | 3257 | [Actions A2] | [Actions A5] | [Actions A5] | [Actions A5] | 3258 +---------------+-------------------+-----------------+-----------------+ 3260 +-----------------------------------------------------------------------+ 3261 | In I Am Assert Loser (L) State | 3262 +----------------------+----------------------+-------------------------+ 3263 | my_metric -> | RPF interface | Receive Join(*,G) | 3264 | better than | stops being I | or Join(*,*,RP(G)) | 3265 | Winner's metric | | on Interface I | 3266 +----------------------+----------------------+-------------------------+ 3267 | -> NI state | -> NI state | -> NI State | 3268 | [Actions A5] | [Actions A5] | [Actions A5] | 3269 +----------------------+----------------------+-------------------------+ 3270 The state machine uses the following macros: 3272 CouldAssert(*,G,I) = | 3273 ( I in ( joins(*,G) (+) joins(*,*,RP(G)) | 3274 (+) pim_include(*,G)) ) | 3275 AND RPF_interface(RP(G)) != I | 3277 CouldAssert(*,G,I) is true on downstream interfaces for which we have | 3278 (*,G) or (*,*,RP(G) join state, or local members that requested any | 3279 traffic destined for G. | 3281 AssertTrackingDesired(*,G,I) = | 3282 CouldAssert(*,G) OR | 3283 ( RPF_interface(RP(G)) == I AND RPTJoinDesired(G) ) | 3285 AssertTrackingDesired(*,G,I) is true on any interface on which an (*,G) 3286 assert might affect our behavior. 3288 Note that for reasons of compactness, "AssTrDes(*,G,I)" is used in the 3289 state-machine table to refer to AssertTrackingDesired(*,G,I). 3291 Terminology: 3292 A "preferred assert" is one with a better metric than the current 3293 winner. 3295 An "inferior assert" is one with a worse metric than | 3296 my_assert_metric(S,G). | 3298 Transitions from NoInfo State 3300 When in NoInfo state, the following events trigger transitions, but only | 3301 if the (S,G) assert state machine is in NoInfo state: | 3303 Receive Inferior Assert with RPTbit set AND 3304 CouldAssert(*,G,I)==TRUE 3305 An Inferior (*,G) assert is received for G on Interface I. If 3306 CouldAssert(*,G,I) is TRUE, then I is our downstream 3307 interface, and we have (*,G) forwarding state on this 3308 interface, so we should be the assert winner. We transition 3309 to the "I am Assert Winner" state, and perform Actions A1 3310 (below). 3312 A data packet destined for G arrives on interface I, AND 3313 CouldAssert(*,G,I)==TRUE 3314 A data packet destined for G arrived on a downstream interface 3315 which is in our (*,G) outgoing interface list. We therefore 3316 believe we should be the forwarder for this (*,G), and so we 3317 transition to the "I am Assert Winner" state, and perform 3318 Actions A1 (below). 3320 Receive Preferred Assert with RPT bit set AND 3321 AssertTrackingDesired(*,G,I)==TRUE 3322 We're interested in (*,G) Asserts, either because I is a 3323 downstream interface for which we have (*,G) forwarding state, 3324 or because I is the upstream interface for RP(G) and we have 3325 (*,G) forwarding state. We get a (*,G) Assert that has a 3326 better metric than our own, so we do not win the Assert. We 3327 transition to "I am Assert Loser" and perform actions A2 | 3328 (below). | 3330 Transitions from Winner State 3332 When in "I am Assert Winner" state, the following events trigger | 3333 transitions, but only if the (S,G) assert state machine is in NoInfo | 3334 state: | 3336 Receive Inferior Assert 3337 We receive a (*,G) assert that has a worse metric than our 3338 own. Whoever sent the assert has lost, and so we re-send a | 3339 (*,G) Assert, and restart the timer (Action A3 below). | 3341 Receive Preferred Assert 3342 We receive a (*,G) assert that has a better metric than our 3343 own. We transition to "I am Assert Loser" state and perform 3344 actions A2 (below). 3346 When in "I am Assert Winner" state, the following events trigger | 3347 transitions: | 3349 Timer Expires 3350 The (*,G) assert timer expires. As we're in the Winner state, 3351 then we must still have (*,G) forwarding state that is 3352 actively being kept alive. To prevent unnecessary thrashing 3353 of the forwarder and periodic flooding of duplicate packets, 3354 we re-send the (*,G) Assert, and restart the timer (Action A3 3355 below). 3357 CouldAssert(*,G,I) -> FALSE 3358 Our (*,G) forwarding state or RPF interface changed so as to 3359 make CouldAssert(*,G,I) become false. We can no longer 3360 perform the actions of the assert winner, and so we transition 3361 to NoInfo state and perform actions A4 (below). 3363 Transitions from Loser State 3365 When in "I am Assert Loser" state, the following events trigger | 3366 transitions, but only if the (S,G) assert state machine is in NoInfo | 3367 state: | 3369 Receive Preferred Assert 3370 We receive a (*,G) assert that is better than that of the 3371 current assert winner. We stay in Loser state, and perform 3372 actions A2 below. 3374 Receive Inferior Assert from Current Winner 3375 We receive an assert from the current assert winner that is 3376 worse than our own metric for this group (typically because 3377 the winner's metric became worse). We transition to NoInfo 3378 state, delete this (*,G) assert state, and allow the normal 3379 PIM Join/Prune mechanisms to operate. Usually we will 3380 eventually re-assert and win when data packets for G have 3381 started flowing again. 3383 When in "I am Assert Loser" state, the following events trigger | 3384 transitions: | 3386 Timer Expires 3387 The (*,G) assert timer expires. We transition to NoInfo state 3388 and delete this (*,G) assert info. 3390 AssertTrackingDesired(*,G,I)->FALSE 3391 AssertTrackingDesired(*,G,I) becomes FALSE. Our forwarding 3392 state has changed so that (*,G) Asserts on interface I are no 3393 longer of interest to us. We transition to NoInfo state and 3394 delete this (*,G) assert info. 3396 My metric becomes better than the assert winner's metric 3397 My routing metrics have changed so that now my assert metric 3398 for (*,G) is better than the metric we have stored for current 3399 assert winner. We transition to NoInfo state, and delete this 3400 (*,G) assert state, and allow the normal PIM Join/Prune 3401 mechanisms to operate. Usually we will eventually re-assert 3402 and win when data packets for G have started flowing again. 3404 RPF interface changed away from interface I 3405 Interface I used to be the RPF interface for RP(G), and now it 3406 is not. We transition to NoInfo state, and delete this (*,G) 3407 assert state. | 3409 Receive Join(*,G) or Join(*,*,RP(G)) | 3410 We receive a Join(*,G) or a Join(*,*,RP(G)) directed to my IP | 3411 address in interface I. The action is to transition to NoInfo | 3412 state, and delete this (*,G) assert state, and allow the | 3413 normal PIM Join/Prune mechanisms to operate. If whoever sent | 3414 the Join was in error, then the normal assert mechanism will | 3415 eventually re-apply and we will lose the assert again. | 3416 However whoever sent the assert may know that the previous | 3417 assert winner has died, and so we may end up being the new | 3418 forwarder. | 3420 (*,G) Assert State-machine Actions 3422 A1: Send Assert(*,G) 3423 Set timer to (Assert_Time - Assert_Override_Interval) 3424 Store self as AssertWinner(*,G) 3426 A2: Store new AssertWinner(*,G) | 3427 Set timer to assert_time 3429 A3: Send Assert(*,G) 3430 Set timer to (Assert_Time - Assert_Override_Interval) 3432 A4: Send AssertCancel(*,G) 3433 Delete assert info 3435 A5: Delete assert info 3437 4.5.3. Assert Metrics 3439 Assert metrics are defined as: 3441 struct assert_metric { 3442 rpt_bit_flag; 3443 metric_preference; 3444 route_metric; 3445 ip_address; 3446 }; 3448 When comparing assert_metrics, the rpt_bit_flag, metric_preference, and | 3449 route_metric field are compared in order, where the first lower value | 3450 wins. If all fields are equal, the IP address of the router that | 3451 sourced the Assert message is used as a tie-breaker, with the highest IP | 3452 address winning. 3454 An assert metric for (S,G) to include in (or compare against) an Assert 3455 message sent on interface I should be computed using the following 3456 pseudocode: 3458 assert_metric 3459 my_assert_metric(S,G,I) { 3460 if( CouldAssert(S,G,I) == TRUE ) { | 3461 return spt_assert_metric(S,G,I) | 3462 } else if( CouldAssert(*,G,I) == TRUE ) { | 3463 return rpt_assert_metric(G,I) | 3464 } else { | 3465 return infinite_assert_metric() | 3466 } | 3467 } | 3469 spt_assert_metric(S,I) gives the assert metric we use if we're sending | 3470 an assert based on active (S,G) forwarding state: | 3472 assert_metric | 3473 spt_assert_metric(S,I) { | 3474 return {0,MRIB.pref(S),MRIB.metric(S),my_ip_address(I)} | 3475 } | 3477 rpt_assert_metric(G,I) gives the assert metric we use if we're sending 3478 an assert based only on (*,G) forwarding state: 3480 assert_metric 3481 rpt_assert_metric(G,I) { 3482 return {1,MRIB.pref(RP(G)),MRIB.metric(RP(G)),my_ip_address(I)} | 3483 } | 3485 MRIB.pref(X) and MRIB.metric(X) are the routing preference and routing | 3486 metrics associated with the route to a particular (unicast) destination 3487 X, as determined by the MRIB. my_ip_address(I) is simply the router's 3488 IP address that is associated with the local interface I. 3490 infinite_assert_metric() gives the assert metric we need to send an 3491 assert but don't match either (S,G) or (*,G) forwarding state: 3493 assert_metric 3494 infinite_assert_metric() { 3495 return {1,infinity,infinity,infinity} 3496 } 3498 4.5.4. AssertCancel Messages 3500 An AssertCancel message is simply an RPT Assert message but with 3501 infinite metric. It is sent by the assert winner when it deletes the 3502 forwarding state that had caused the assert to occur. Other routers 3503 will see this metric, and it will cause any other router that has | 3504 forwarding state to send its own assert, and to take over forwarding. | 3506 An AssertCancel(S,G) is an infinite metric assert with the RPT bit set 3507 that names S as the source. 3509 An AssertCancel(*,G) is an infinite metric assert with the RPT bit set, 3510 and typically will name RP(G) as the source as it cannot name an 3511 appropriate S. 3513 AssertCancel messages are simply an optimization. The original Assert | 3514 timeout mechanism will allow a subnet to eventually become consistent; | 3515 the AssertCancel mechanism simply causes faster convergence. No special | 3516 processing is required for an AssertCancel message, since it is simply | 3517 an Assert message from the current winner. | 3519 4.5.5. Assert State Macros 3521 The macros lost_assert(S,G,rpt,I), lost_assert(S,G,I), and | 3522 lost_assert(*,G,I) are used in the olist computations of Section 4.1, | 3523 and are defined as: 3525 bool lost_assert(S,G,rpt,I) { | 3526 if ( RPF_interface(RP) == I ) { | 3527 return FALSE | 3528 } else { | 3529 return ( AssertWinner(S,G,I) != me ) | 3530 } | 3531 } | 3533 bool lost_assert(S,G,I) { | 3534 if ( RPF_interface(S) == I ) { | 3535 return FALSE | 3536 } else { | 3537 return ( AssertWinner(S,G,I) != me AND | 3538 (AssertWinnerMetric(S,G,I) is better | 3539 than spt_assert_metric(S,G,I) ) | 3540 } | 3541 } | 3542 bool lost_assert(*,G,I) { | 3543 if ( RPF_interface(RP) == I ) { | 3544 return FALSE | 3545 } else { | 3546 return ( AssertWinner(*,G,I) != me ) | 3547 } | 3548 } | 3550 AssertWinner(S,G,I) defaults to Null and AssertWinnerMetric(S,G,I) | 3551 defaults to Infinity when in the NoInfo state. | 3553 Rationale for Assert Rules | 3555 The following is a summary of the rules for sending and reacting to | 3556 asserts. It is not intended to be definitive (the state machines and | 3557 pseudocode provide the definitive behavior). Instead it provides some | 3558 rationale for the behavior. | 3560 1. Downstream neighbors send Join(*,G) and Join(S,G) periodic messages | 3561 to the appropriate RPF' neighbor, i.e., the RPF neighbor as | 3562 modified by the assert process. Normal suppression and override | 3563 rules apply. | 3565 This guarantees that all requested traffic will continue to arrive. | 3566 This doesn't allow switching back to the "normal" RPF neighbor | 3567 until the assert times out, which it won't while data is flowing if | 3568 we are implementing rule 8. 3570 2. The assert winner for (*,G) acts as the local DR for (*,G) on | 3571 behalf of IGMP members. | 3573 This is required to allow a single router to merge PIM and IGMP 3574 joins and leaves. Without this, overrides don't work. 3576 3. The assert winner for (S,G) must act as the local DR for (S,G) on 3577 behalf of IGMPv3 members. 3579 Same rationale as (2) 3581 4. (S,G) and (*,G) prune overrides are sent to the RPF' neighbor and 3582 not to the regular RPF neighbor. 3584 Same rationale as (1). 3586 5. An (S,G,rpt) prune override is not sent (at all) if RPF'(S,G,rpt) 3587 != RPF'(*,G). 3589 This avoids keeping state alive on (S,G) tree when only (*,G) 3590 downstream members are left. Also, it avoids sending (S,G,rpt) 3591 joins to a router that is not on the (*,G) tree. This might be 3592 confusing and could be interpreted as being undefined although 3593 technically the current spec says to drop such a join. 3595 6. An assert loser that receives a Join(S,G) directed to it cancels 3596 the (S,G) assert timer. 3598 7. An assert loser that receives a Join(*,G) or a Join(*,*,RP(G)) | 3599 directed to it cancels the (*,G) assert timer and all (S,G) assert | 3600 timers that do not have corresponding Prune(S,G,rpt) messages in | 3601 the compound Join/Prune message. | 3603 Rules 7 and 8 help convergence during topology changes. 3605 8. An assert winner for (*,G) or (S,G) sends a canceling assert when | 3606 it is about to stop forwarding on a (*,G) or an (S,G) entry. This | 3607 rule does not apply to (S,G,rpt). | 3609 This allow switching back to the shared tree after the last SPT | 3610 router on the lan leaves. We don't want RPT downstream routers to 3611 keep SPT state alive. 3613 9. [Optionally] re-assert before timing out. 3615 This prevents periodic duplicates. 3617 10. When RPF'(S,G,rpt) changes to be the same as RPF'(*,G) we need to 3618 trigger a Join(S,G,rpt) to RPF(*,G). 3620 This allows switching back to the RPT after the last SPT member 3621 leaves. 3623 4.6. Designated Routers (DR) and Hello Messages 3625 4.6.1. Sending Hello Messages 3627 PIM-Hello messages are sent periodically on each PIM-enabled interface. 3628 They allow a router to learn about the neighboring PIM routers on each 3629 interface. Hello messages are also the mechanism used to elect a 3630 Designated Router (DR). A router must record the Hello information 3631 received from each PIM neighbor. 3633 Hello messages are sent periodically on each PIM-enabled interface. 3634 Hello messages are multicast to address 224.0.0.13 (the ALL-PIM-ROUTERS 3635 group). Hello messages must be sent on all active interfaces, including 3636 physical point-to-point links. When PIM is enabled on an interface or a | 3637 router first starts, the hello timer is set to a random value between 0 | 3638 and Hello_Period to prevent synchronization of Hello messages if | 3639 multiple routers are powered on simultaneously. After the initial 3640 randomized interval, Hello messages must be sent every Hello_Period 3641 seconds. A single hello timer is used to trigger sending Hello messages 3642 on all active interfaces. The hello timer should not be reset except 3643 when it expires. 3645 The DR Election Priority Option allows a network administrator to give 3646 preference to a particular router in the DR election process by giving 3647 it a numerically larger DR Election Priority. The DR Election Priority 3648 Option SHOULD be included in every Hello message, even if no DR election 3649 priority is explicitly configured on that interface. This is necessary 3650 because priority-based DR election is only enabled when all neighbors on 3651 an interface advertise that they are capable of using the DR Election 3652 Priority Option. The default priority is 1. 3654 The Generation Identifier (GenID) Option SHOULD be included in all Hello 3655 messages. The generation ID option contains a randomly generated 32-bit 3656 value that is regenerated each time PIM forwarding is started or 3657 restarted on the interface, including when the router itself restarts. 3658 When a Hello message with a new GenID is received from a neighbor, any 3659 old Hello information about that neighbor SHOULD be discarded and 3660 superseded by the information from the new Hello message. This may 3661 cause a new DR to be chosen on that interface. 3663 When an interface goes down or changes IP address, a Hello message with | 3664 a zero Hold Time should be sent immediately (with the old IP address if | 3665 the IP address changed). This will cause PIM neighbors to remove this | 3666 neighbor (or its old IP address) immediately. | 3668 4.6.2. DR Election 3670 When a PIM-Hello message is received on interface I the following 3671 information about the sending neighbor is recorded: 3673 neighbor.interface 3674 The interface on which the Hello message arrived. 3676 neighbor.ip_address 3677 The IP address of the PIM neighbor. 3679 neighbor.genid 3680 The Generation ID of the PIM neighbor. 3682 neighbor.dr_priority 3683 The DR Priority field of the PIM neighbor if it is present in 3684 the Hello message. 3686 neighbor.dr_priority_present 3687 A flag indicating if the DR Priority field was present in the 3688 Hello message. 3690 neighbor.timeout 3691 A timer to time out the neighbor state when it becomes stale. 3692 This is reset to Hello Holdtime whenever a Hello message is 3693 received, or to the value specified in the message, if the 3694 hold time option is used. 3696 Neighbor state is deleted when the neighbor timeout expires. 3698 The function for computing the DR on interface I is: 3700 host 3701 DR(I) { 3702 dr = me 3703 for each neighbor on interface I { 3704 if ( dr_is_better( neighbor, dr, I ) == TRUE ) { 3705 dr = neighbor 3706 } 3707 } 3708 return dr 3709 } 3711 The function used for comparing DR "metrics" on interface I is: 3713 bool 3714 dr_is_better(a,b,I) { 3715 if( there is a neighbor n on I for which n.dr_priority_present | 3716 is false ) { | 3717 return a.ip_address > b.ip_address | 3718 } else { | 3719 return ( a.dr_priority > b.dr_priority ) OR | 3720 ( a.dr_priority == b.dr_priority AND | 3721 a.ip_address > b.ip_address ) | 3722 } | 3723 } | 3725 The DR election priority is a 32-bit unsigned number and the numerically 3726 larger priority is always preferred. A router's idea of the current DR 3727 on an interface can change when a PIM-Hello message is received, when a 3728 neighbor times out, or when a router's own dr priority changes. If the 3729 router becomes the DR or ceases to be the DR, this will normally cause 3730 the DR Register state-machine to change state. Subsequent actions are 3731 determined by that state-machine. 3733 4.7. PIM Bootstrap and RP Discovery 3735 To obtain the RP information, all routers within a PIM domain collect 3736 Bootstrap messages. Bootstrap messages are sent hop-by-hop within the 3737 domain; the domain's bootstrap router (BSR) is responsible for 3738 originating the Bootstrap messages. Bootstrap messages are used to carry 3739 out a dynamic BSR election when needed and to distribute RP information 3740 in steady state. 3742 A domain in this context is a contiguous set of routers that all 3743 implement PIM and are configured to operate within a common boundary 3744 defined by PIM Multicast Border Routers (PMBRs). PMBRs connect each PIM 3745 domain to the rest of the internet. 3747 Routers use a set of available RPs (called the RP-Set) distributed in 3748 Bootstrap messages to get the proper Group to RP mapping. The following 3749 paragraphs give an overview of this process. The mechanism is specified 3750 in Sections 4.7.2 and 4.7.4. 3752 4.7.1. Overview of RP Discovery 3754 A small set of routers from a domain are configured as candidate 3755 bootstrap routers (C-BSRs) and, through a simple election mechanism, a 3756 single BSR is selected for that domain. A set of routers within a domain 3757 are also configured as candidate RPs (C-RPs); typically these will be 3758 the same routers that are configured as C-BSRs. Candidate RPs 3759 periodically unicast Candidate-RP-Advertisement messages (C-RP-Advs) to 3760 the BSR of that domain, advertising their willingness to be an RP. A C- 3761 RP-Adv message includes the address of the advertising C-RP, as well as 3762 an optional list of group addresses and a mask length fields, indicating 3763 the group prefix(es) for which the candidacy is advertised. The BSR then 3764 includes a set of these Candidate-RPs (the RP-Set), along with the 3765 corresponding group prefixes, in Bootstrap messages it periodically 3766 originates. Bootstrap messages are distributed hop-by-hop throughout 3767 the domain. 3769 All the PIM routers in the domain receive and store Bootstrap messages 3770 originated by the BSR. When a DR gets a indication of local membership 3771 from IGMP or a data packet from a directly connected host, for a group 3772 for which it has no forwarding state, the DR uses a hash function to map 3773 the group address to one of the C-RPs whose group-prefix includes the 3774 group (see Section 4.7.5 ). The DR then sends a Join message towards 3775 that RP if the local host joined the group, or it Register-encapsulates 3776 and unicasts the data packet to the RP if the local host sent a packet 3777 to the group. 3779 A Bootstrap message indicates liveness of the RPs included therein. If 3780 an RP is included in the message, then it is tagged as `up' at the 3781 routers; while RPs not included in the message are removed from the list 3782 of RPs over which the hash algorithm acts. Each router continues to use 3783 the contents of the most recently received Bootstrap message from the 3784 BSR until it receives a new Bootstrap message. 3786 If a PIM domain becomes partitioned, each area separated from the old 3787 BSR will elect its own BSR, which will distribute an RP-Set containing 3788 RPs that are reachable within that partition. When the partition heals, 3789 another election will occur automatically and only one of the BSRs will 3790 continue to send out Bootstrap messages. As is expected at the time of a 3791 partition or healing, some disruption in packet delivery may occur. This 3792 time will be on the order of the region's round-trip time and the 3793 bootstrap router timeout value. 3795 4.7.2. Bootstrap Router Election and RP-Set Distribution 3797 For simplicity, bootstrap messages (BSMs) are used in both the BSR 3798 election and the RP-Set distribution mechanisms. 3800 The state-machine for bootstrap messages depends on whether or not a 3801 router has been configured to be a Candidate-BSR. The state-machine for 3802 a C-BSR is given below, followed by the state-machine for a router that 3803 is not configured to be a C-BSR. 3805 Candidate-BSR State Machine 3807 +-----------------------------------+ 3808 | Figures omitted from text version | 3809 +-----------------------------------+ 3811 Figure 12: State-machine for a candidate BSR 3813 In tabular form this state machine is: 3815 +-------------------++--------------------------------------------------+ 3816 | || Event | 3817 | Prev State ++------------------------+-------------------------+ 3818 | || Receive Preferred | BS Timer Expires | 3819 | || BSM | | 3820 +-------------------++------------------------+-------------------------+ 3821 | || -> C-BSR state | -> P-BSR state | 3822 | Candidate BSR || Forward BSM; Set | Set BS Timer to | 3823 | (C-BSR) || BS Timer to BS | rand_override | 3824 | || Timeout | | 3825 +-------------------++------------------------+-------------------------+ 3826 | || -> C-BSR state | -> E-BSR state | 3827 | Pending BSR || Forward BSM; Set | Originate BSM; Set | 3828 | (P-BSR) || BS Timer to BS | BS Timer to BS | 3829 | || Timeout | Period | 3830 +-------------------++------------------------+-------------------------+ 3831 | || -> C-BSR state | -> E-BSR state | 3832 | Elected BSR || Forward BSM; Set | Originate BSM; Set | 3833 | (E-BSR) || BS Timer to BS | BS Timer to BS | 3834 | || Timeout | Period | 3835 +-------------------++------------------------+-------------------------+ 3836 A candidate-BSR may be in one of three states: 3838 Candidate-BSR (C-BSR) 3839 The router is a candidate to be a BSR, but currently another router 3840 is the preferred BSR. 3842 Pending-BSR (P-BSR) 3843 The router is a candidate to be a BSR. Currently no other router 3844 is the preferred BSR, but this router is not yet the BSR. For 3845 comparisons with incoming BS messages, the router treats itself as 3846 the BSR. This is a temporary state that prevents rapid thrashing 3847 of the choice of BSR during BSR election. 3849 Elected-BSR (E-BSR) 3850 The router is the elected bootstrap router and it must perform all 3851 the BSR functions. 3853 On startup, the initial state is "Pending-BSR", and the BS Timer is 3854 initialized to the BS Timeout value. 3856 In addition, there is a single timer - the bootstrap timer (BS Timer) - 3857 that is used to time out old bootstrap router information, and used in 3858 the election process to terminate P-BSR state. 3860 State-machine for Non-Candidate-BSR Routers 3862 +-----------------------------------+ 3863 | Figures omitted from text version | 3864 +-----------------------------------+ 3866 Figure 13: State-machine for a router not configured as C-BSR 3868 In tabular form this state machine is: 3870 +-----------------------+-----------------------------------------------+ 3871 | | Event | 3872 |Prev State +----------------+----------------+-------------+ 3873 | | Receive | Receive BSM |BS Timer | 3874 | | Preferred BSM | |Expires | 3875 +-----------------------+----------------+----------------+-------------+ 3876 | | -> AP State | -> AP State |- | 3877 | | Forward BSM; | Forward BSM; | | 3878 |Accept Any (AA) | Store RP-Set; | Store RP-Set; | | 3879 | | Set BS Timer | Set BS Timer | | 3880 | | to BS Timeout | to BS Timeout | | 3881 +-----------------------+----------------+----------------+-------------+ 3882 | | -> AP State | - |-> AA State | 3883 | | Forward BSM; | | | 3884 |Accept Preferred (AP) | Store RP-Set; | | | 3885 | | Set BS Timer | | | 3886 | | to BS Timeout | | | 3887 +-----------------------+----------------+----------------+-------------+ 3888 A router that is not a candidate-BSR may be in one of two states: 3890 Accept Any (AA) 3891 The router does not know of an active BSR, and will accept the 3892 first bootstrap message it sees as giving the new BSR's identity 3893 and the RP-Set. If the router has an RP-Set cached from an 3894 obsolete bootstrap message, it continues to use it. 3896 Accept Preferred (AP) 3897 The router knows the identity of the current BSR, and is using the 3898 RP-Set provided by that BSR. Only bootstrap messages from that BSR 3899 or from a C-BSR with higher weight than the current BSR will be 3900 accepted. 3902 On startup, the initial state is "Accept Any". 3904 In addition, there is a single timer - the bootstrap timer (BS Timer) 3905 that is used to time out old bootstrap router information. 3907 Bootstrap Message Processing Checks 3909 When a bootstrap message is received, the following initial checks must 3910 be performed: 3912 if (BSM.dst_ip_address == ALL-PIM-ROUTERS group) { 3913 if ( BSM.src_ip_address != RPF_neighbor(BSM.BSR_ip_address) ) { 3914 drop the BS message silently 3915 } 3916 } else if (BSM.dst_ip_address is one of my addresses) { 3917 if ( (BSR state != Accept Any) 3918 OR (DirectlyConnected(BSM.src_ip_address) == FALSE) ) { 3919 #the packet was unicast, but this wasn't 3920 #a quick refresh on startup 3921 drop the BS message silently 3922 } 3923 } else { 3924 drop the BS message silently 3925 } 3927 Basically, the packet must have been sent to the ALL-PIM-ROUTERS group 3928 by the correct upstream router towards the BSR that originated the BS 3929 message, or the router must have no BSR state (it just restarted) and 3930 have received the BS message by unicast from a directly connected 3931 neighbor. 3933 BS State-machine Transition Events 3935 If the bootstrap message passes the initial checks above without being 3936 discarded, then it may cause a state transition event in one of the 3937 above state-machines. For both candidate and non-candidate BSRs, the 3938 following transition events are defined: 3940 Receive Preferred BSM 3941 A bootstrap message is received from a BSR that has greater 3942 than or equal weight than the current BSR. In a router is in 3943 P-BSR state, then it uses its own weight as that of the 3944 current BSR. 3946 The weighting for a BSR is the concatenation in fixed- 3947 precision unsigned arithmetic of the BSR priority field from 3948 the bootstrap message and the IP address of the BSR from the 3949 bootstrap message (with the BSR priority taking the most- 3950 significant bits and the IP address taking the least 3951 significant bits). 3953 Receive BSM 3954 A bootstrap message is received, regardless of BSR weight. 3956 BS State-machine Actions 3958 The state-machines specify actions that include setting the BS timer to 3959 the following values: 3961 BS Period 3962 The periodic interval with which bootstrap messages are 3963 normally sent. The default value is 60 seconds. 3965 BS Timeout 3966 The interval after which bootstrap router state is timed out 3967 if no bootstrap message from that router has been heard. The 3968 default value is 2.5 times the BS Period, which is 150 3969 seconds. 3971 Randomized Override Interval 3972 The randomized interval during which a router avoids sending a 3973 bootstrap message while it waits to see if another router has 3974 a higher bootstrap weight. This interval is to reduce control 3975 message overhead during BSR election. The following 3976 pseudocode is proposed as an efficient implementation of this 3977 "randomized" value: 3979 Delay = 5 + 2 * log_2(1 + bestPriority - myPriority) 3980 + AddrDelay 3982 where myPriority is the Candidate-BSR's configured priority, 3983 and bestPriority equals: 3985 bestPriority = Max(storedPriority, myPriority) 3987 and AddrDelay is given by the following: 3989 if ( bestPriority == myPriority) { 3990 AddrDelay = log_2(bestAddr - myAddr) / 16 3991 } else { 3992 AddrDelay = 2 - (myAddr / 2^31) 3993 } 3995 where myAddr is the Candidate-BSR's address, and bestAddr is 3996 the stored BSR's address. 3998 In addition to setting the timer, the following actions may be triggered 3999 by state-changes in the state-machines: 4001 Forward BSM 4002 The bootstrap message is forwarded out of all multicast- 4003 capable interfaces except the interface it was received on. 4004 The source IP address of the message is the forwarding 4005 router's IP address on the interface the message is being 4006 forwarded from, the destination address is ALL-PIM-ROUTERS, 4007 and the TTL of the message is set to 1. 4009 Originate BSM 4010 A new bootstrap message is constructed by the BSR, giving the 4011 BSR's address and BSR priority, and containing the BSR's 4012 chosen RP-Set. The message is forwarded out of all multicast- 4013 capable interfaces. The IP source address of the message is 4014 the forwarding router's IP address on the interface the 4015 message is being forwarded from, the destination address is 4016 ALL-PIM-ROUTERS, and the TTL of the message is set to 1. 4018 Store RP Set 4019 The RP-Set from the received bootstrap message is stored and 4020 used by the router to decide the RP for each group that the 4021 router has state for. Storing this RP Set may cause other 4022 state-transitions to occur in the router. The BSR's IP 4023 address and priority from the received bootstrap message are 4024 also stored to be used to decide if future bootstrap messages 4025 are preferred. 4027 In addition to the above state-machine actions, a DR also unicasts a 4028 stored copy of the Bootstrap message to each new PIM neighbor, i.e., 4029 after the DR receives the neighbor's first Hello message. It does so 4030 even if the new neighbor becomes the DR. 4032 4.7.3. Sending Candidate-RP-Advertisements 4034 Every C-RP periodically unicasts a C-RP-Adv to the BSR for that domain 4035 to inform the BSR of the C-RP's willingness to function as an RP. The 4036 interval for sending these messages is subject to local configuration at 4037 the C-RP, but must be smaller than the HoldTime in the C-RP-Adv. 4039 A Candidate-RP-Advertisement carries a list of group address and group 4040 mask field pairs. This enables the C-RP router to limit the 4041 advertisement to certain prefixes or scopes of groups. If the C-RP 4042 becomes an RP, it may enforce this scope acceptance when receiving 4043 Registers or Join/Prune messages. C-RPs should normally send C-RP-Adv 4044 messages with the `Priority' field set to `0'. 4046 4.7.4. Receiving Candidate-RP-Advertisements at the BSR and Creating 4047 the RP-Set 4049 Upon receiving a C-RP-Adv, if the router is not the elected BSR, it 4050 silently ignores the message. 4052 If the router is the BSR, then it adds the RP address to its local pool 4053 of candidate RPs. For each C-RP, the BSR holds the following 4054 information: 4056 IP address 4057 The IP address of the C-RP. 4059 Group Prefix and Mask list 4060 The list of group prefixes and group masks from the C-RP 4061 advertisement. 4063 HoldTime 4064 The HoldTime from the C-RP-Adv message. This is included 4065 later in the RP-set information in the Bootstrap Message. 4067 C-RP Expiry Timer 4068 The C-RP-Expiry Timer is used to time out the C-RP when the 4069 BSR fails to receive C-RP-Advertisements from it. The expiry 4070 timer is initialized to the HoldTime from the RP's C-RP-Adv, 4071 and is reset to the HoldTime whenever a C-RP-Adv is received 4072 from that C-RP. 4074 C-RP Priority 4075 Do we store this? 4077 When the C-RP Expiry Timer expires, the C-RP is removed from the pool of 4078 available C-RPs. 4080 The BSR uses the pool of C-RPs to construct the RP-Set which is included 4081 in Bootstrap Messages and sent to all the routers in the PIM domain. 4082 The BSR may apply a local policy to limit the number of Candidate RPs 4083 included in the Bootstrap message. The BSR may override the prefix 4084 indicated in a C-RP-Adv unless the `Priority' field from the C-RP-Adv is 4085 not zero. 4087 The Bootstrap message is subdivided into sets of group-prefix,RP- 4088 Count,RP-addresses. For each RP-address, the corresponding HoldTime is 4089 included in the "RP-HoldTime" field. The format of the Bootstrap 4090 message allows `semantic fragmentation', if the length of the original 4091 Bootstrap message exceeds the packet maximum boundaries. However, we 4092 recommend against configuring a large number of routers as C-RPs, to 4093 reduce the semantic fragmentation required. 4095 4.7.5. Receiving and Using the RP-Set 4097 When a router receives and stores a new RP-Set, it checks if each of the 4098 RPs referred to by existing state (i.e., by (*,G), (*,*,RP), or 4099 (S,G,rpt) entries) is in the new RP-Set. 4101 If an RP is not in the new RP-set, that RP is considered unreachable and 4102 the hash algorithm (see below) is re-performed for each group with 4103 locally active state that previously hashed to that RP. This will cause 4104 those groups to be distributed among the remaining RPs. 4106 If the new RP-Set contains a RP that was not previously in the RP-Set, 4107 the hash value of the new RP is calculated for each group covered by the 4108 new C-RP's Group-prefix. Any group for which the new RP's hash value is 4109 greater than hash value of the group's previous RP is switched over to 4110 the new RP. 4112 Hash Function 4114 The hash function is used by all routers within a domain, to map a group 4115 to one of the C-RPs from the RP-Set. For a particular group, G, the hash 4116 function uses only those C-RPs whose Group-prefix covers G. The 4117 algorithm takes as input the group address, and the addresses of the 4118 Candidate RPs, and gives as output one RP address to be used. 4120 The protocol requires that all routers hash to the same RP within a 4121 domain (except for transients). The following hash function must be used 4122 in each router: 4124 1 For RP addresses in the RP-Set, whose Group-prefix is the longest 4125 that covers G, select the RPs with the highest priority (i.e. 4126 lowest `Priority' value), and compute a value: 4128 Value(G,M,C(i))= 4129 (1103515245 * ((1103515245 * (G&M)+12345) XOR C(i)) + 12345) mod 2^31 4131 where C(i) is the RP address and M is a hash-mask included in 4132 Bootstrap messages. The hash-mask allows a small number of 4133 consecutive groups (e.g., 4) to always hash to the same RP. For 4134 instance, hierarchically-encoded data can be sent on consecutive 4135 group addresses to get the same delay and fate-sharing 4136 characteristics. 4138 For address families other than IPv4, a 32-bit digest to be used as 4139 C(i) must first be derived from the actual RP address. Such a 4140 digest method must be used consistently throughout the PIM domain. 4141 For IPv6 addresses, we recommend using the equivalent IPv4 address 4142 for an IPv4-compatible address, and the CRC-32 checksum [7] of all 4143 other IPv6 addresses. 4145 2 From the RPs with the highest priority (i.e. lowest `Priority' 4146 value), the candidate with the highest resulting hash value is then 4147 chosen as the RP for that group, and its identity and hash value 4148 are stored with the entry created. 4150 Ties between RPs having the same hash value and priority, are 4151 broken in advantage of the highest address. 4153 The hash function algorithm is invoked by a DR, upon reception of a 4154 packet, or IGMP membership indication, for a group, for which the DR has 4155 no entry. It is invoked by any router that has (*,*,RP) state when a 4156 packet is received for which there is no corresponding (S,G) or (*,G) 4157 entry. Furthermore, the hash function is invoked by all routers upon 4158 receiving a (*,G) or (*,*,RP) Join/Prune message. 4160 4.8. Source-Specific Multicast 4162 The Source-Specific Multicast (SSM) service model [9] can be implemented | 4163 with a strict subset of the PIM-SM protocol mechanisms. Both regular IP | 4164 Multicast and SSM semantics can coexist on a single router and both can | 4165 be implemented using the PIM-SM protocol. A range of multicast | 4166 addresses, currently 232.0.0.0/8 in IPv4, is reserved for SSM, and the | 4167 choice of semantics is determined by the multicast group address in both | 4168 data packets and PIM messages. | 4170 4.8.1. Protocol Modifications for SSM destination addresses | 4172 The following rules override the normal PIM-SM behavior for a multicast | 4173 address G in the SSM reserved range: | 4175 o A router MUST NOT send a (*,G) Join/Prune message for any reason. | 4177 o A router MUST NOT send an (S,G,rpt) Join/Prune message for any reason. | 4179 o A router MUST NOT send a Register message for any packet that is | 4180 destined to an SSM address. | 4182 o A router MUST NOT forward packets based on (*,G) or (S,G,rpt) state. | 4183 The (*,G) and (S,G,rpt) -related state summarization macros are NULL | 4184 for any SSM address, for the purposes of packet forwarding. | 4186 o A router acting as an RP MUST NOT forward any Register-encapsulated | 4187 packet that has an SSM destination address. | 4189 The last two rules are present to deal with "legacy" routers unaware of | 4190 SSM that may be sending (*,G) and (S,G,rpt) Join/Prunes, or Register | 4191 messages for SSM destination addresses. | 4193 Additionally: | 4195 o A router MAY be configured to advertise itself as a Candidate RP for | 4196 an SSM address. If so, it SHOULD respond with a Register-Stop message | 4197 to any Register message containing a packet destined for an SSM | 4198 address. | 4200 o A router MAY optimize out the creation and maintenance of (S,G,rpt) | 4201 and (*,G) state for SSM destination addresses -- this state is not | 4202 needed for SSM packets. | 4204 4.8.2. PIM-SSM-only Routers | 4206 An implementor may choose to implement only the subset of PIM Sparse- | 4207 Mode that provides SSM forwarding semantics. | 4209 A PIM-SSM-only router MUST implement the following portions of this | 4210 specification: | 4212 o Upstream (S,G) state machine (Section 4.4.7) | 4214 o Downstream (S,G) state machine (Section 4.4.3) | 4216 o (S,G) Assert state machine (Section 4.5.1) | 4218 o Hello messages, neighbor discovery and DR election (Section 4.6) | 4220 o Packet forwarding rules (Section 4.2) | 4222 A PIM-SSM-only router does not need to implement the following protocol | 4223 elements: | 4225 o Register state machine (Section 4.3) | 4227 o (*,G), (S,G,rpt) and (*,*,RP) Downstream state machines (Sections | 4228 4.4.2, 4.4.4, and 4.4.1) | 4230 o (*,G), (S,G,rpt), and (*,*,RP) Upstream state machines (Sections | 4231 4.4.6, 4.4.8, and 4.4.5) | 4233 o (*,G) Assert state machine (Section 4.5.2) | 4234 o Bootstrap RP Election (Section 4.7) | 4236 o Keepalive Timer | 4238 o SptBit (Section 4.2.1) | 4240 The KeepaliveTimer should be treated as always running and SptBit should | 4241 be treated as being always set for an SSM address. Additionally, the | 4242 Packet forwarding rules of Section 4.2 can be simplified in a PIM-SSM- | 4243 only router: | 4245 if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined ) { | 4246 oiflist = inherited_olist(S,G) | 4247 } else if( iif is in inherited_olist(S,G) ) { | 4248 send Assert(S,G) on iif | 4249 } | 4251 oiflist = oiflist (-) iif | 4252 forward packet on all interfaces in oiflist | 4254 This is nothing more than the reduction of the normal PIM-SM forwarding | 4255 rule, with all (S,G,rpt) and (*,G) clauses replaced with NULL. | 4257 4.9. PIM Packet Formats 4259 This section describes the details of the packet formats for PIM control 4260 messages. 4262 All PIM control messages have IP protocol number 103. | 4264 Basically, PIM messages are either unicast (e.g. Registers and 4265 Register-Stop), or multicast with TTL 1 to `ALL-PIM-ROUTERS' group 4266 `224.0.0.13' (e.g. Join/Prune, Asserts, etc.). 4268 0 1 2 3 4269 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 4270 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4271 |PIM Ver| Type | Reserved | Checksum | 4272 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4274 PIM Ver 4275 PIM Version number is 2. 4277 Type Types for specific PIM messages. PIM Types are: 4279 0 = Hello 4280 1 = Register 4281 2 = Register-Stop 4282 3 = Join/Prune 4283 4 = Bootstrap 4284 5 = Assert 4285 6 = Graft (used in PIM-DM only) 4286 7 = Graft-Ack (used in PIM-DM only) 4287 8 = Candidate-RP-Advertisement 4289 Reserved 4290 Set to zero on transmission. Ignored upon receipt. 4292 Checksum 4293 The checksum is standard IP checksum, i.e. the 16-bit one's 4294 complement of the one's complement sum of the entire PIM message, 4295 excluding the data portion in the Register message. For computing 4296 the checksum, the checksum field is zeroed. 4298 4.9.1. Encoded Source and Group Address Formats 4300 Encoded-Unicast address 4302 An Encoded-Unicast address takes the following format: 4304 0 1 2 3 4305 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 4306 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4307 | Addr Family | Encoding Type | Unicast Address 4308 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4310 Addr Family 4311 The PIM address family of the `Unicast Address' field of this 4312 address. 4314 Values of 0-127 are as assigned by the IANA for Internet Address 4315 Families in [4]. Values 128-250 are reserved to be assigned by the 4316 IANA for PIM-specific Address Families. Values 251 though 255 are | 4317 designated for private use. As there is no assignment authority | 4318 for this space, collisions should be expected. 4320 Encoding Type 4321 The type of encoding used within a specific Address Family. The 4322 value `0' is reserved for this field, and represents the native 4323 encoding of the Address Family. 4325 Unicast Address 4326 The unicast address as represented by the given Address Family and 4327 Encoding Type. 4329 Encoded-Group address 4331 Encoded-Group addresses take the following format: 4333 0 1 2 3 4334 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 4335 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4336 | Addr Family | Encoding Type | Reserved | Mask Len | 4337 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4338 | Group multicast Address 4339 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+... 4341 Addr Family 4342 described above. 4344 Encoding Type 4345 described above. 4347 Reserved 4348 Transmitted as zero. Ignored upon receipt. 4350 Mask Len | 4351 The Mask length field is 8 bits. The value is the number of | 4352 contiguous one bits left justified used as a mask which, combined | 4353 with the group address, describes a range of groups. It is less | 4354 than or equal to the address length in bits for the given Address | 4355 Family and Encoding Type. If the message is sent for a single group 4356 then the Mask length must equal the address length in bits for the 4357 given Address Family and Encoding Type. (e.g. 32 for IPv4 native 4358 encoding and 128 for IPv6 native encoding). 4360 Group multicast Address 4361 Contains the group address. 4363 Encoded-Source address 4365 Encoded-Source address takes the following format: 4367 0 1 2 3 4368 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 4369 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4370 | Addr Family | Encoding Type | Rsrvd |S|W|R| Mask Len | 4371 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4372 | Source Address 4373 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-... 4375 Addr Family 4376 described above. 4378 Encoding Type 4379 described above. 4381 Reserved 4382 Transmitted as zero, ignored on receipt. | 4384 S The Sparse bit is a 1 bit value, set to 1 for PIM-SM. It is used | 4385 for PIM version 1 compatibility. | 4387 W The WC (or WildCard) bit is a 1 bit value. If 1, the join or prune | 4388 applies to the (*,G) or (*,*,RP) entry. If 0, the join or prune | 4389 applies to the (S,G) entry where S is Source Address. Joins and | 4390 prunes sent towards the RP must have this bit set. | 4392 R The RPT-bit is a 1 bit value. If 1, the information about (S,G) is | 4393 sent towards the RP. If 0, the information must be sent toward S, | 4394 where S is the Source Address. | 4396 Mask Len | 4397 The mask length field is 8 bits. The value is the number of | 4398 contiguous one bits left justified used as a mask which, combined | 4399 with the Source Address, describes a source subnet. The mask length | 4400 must be less than or equal to the address length in bits for the | 4401 given Address Family and Encoding Type. If the message is sent for | 4402 a single source then the Mask length must equal the address length | 4403 in bits for the given Address Family and Encoding Type. In version 4404 2 of PIM, it is strongly recommended that this field be set to 32 4405 for IPv4 native encoding. 4407 Source Address 4408 The source address. | 4410 Represented in the form of < WC-bit >< RPT-bit >< Mask length >< Source | 4411 address >: | 4413 A source address could be a host IPv4 native encoding address : | 4415 < 0 >< 0 >< 32 >< 192.1.1.17 > | 4417 A source address could be the RP's IP address : | 4419 < 1 >< 1 >< 32 >< 131.108.13.111 > | 4421 A source address could be an IP address to prune from the RP-tree : | 4423 < 0 >< 1 >< 32 >< 192.1.1.16 > | 4425 4.9.2. Hello Message Format | 4427 It is sent periodically by routers on all interfaces. | 4429 0 1 2 3 | 4430 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 | 4431 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4432 |PIM Ver| Type | Reserved | Checksum | | 4433 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4434 | OptionType | OptionLength | | 4435 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4436 | OptionValue | | 4437 | ... | | 4438 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4439 | . | | 4440 | . | | 4441 | . | | 4442 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4443 | OptionType | OptionLength | | 4444 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4445 | OptionValue | | 4446 | ... | | 4447 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4449 PIM Version, Type, Reserved, Checksum 4450 Described above. 4452 OptionType 4453 The type of the option given in the following OptionValue field. 4455 OptionLength 4456 The length of the OptionValue field in bytes. 4458 OptionValue 4459 A variable length field, carrying the value of the option. 4461 The Option fields may contain the following values: 4463 o OptionType 1: Hold Time | 4464 0 1 2 3 | 4465 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 | 4466 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4467 | Type = 1 | Length = 2 | | 4468 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4469 | Hold Time | | 4470 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4472 Hold Time is the amount of time a receiver must keep the neighbor | 4473 reachable, in seconds. If the Holdtime is set to `0xffff', the 4474 receiver of this message never times out the neighbor. This may | 4475 be used with dial-on-demand links, to avoid keeping the link up | 4476 with periodic Hello messages. Furthermore, if the Holdtime is 4477 set to `0', the information is timed out immediately. 4479 o OptionType 2 to 16: reserved to be defined in future versions of 4480 this document. | 4482 o OptionType 18: deprecated and should not be used. | 4484 o OptionType 19: DR Priority | 4486 0 1 2 3 | 4487 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 | 4488 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4489 | Type = 19 | Length = 4 | | 4490 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4491 | DR Priority | | 4492 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4494 DR Priority is a 32-bit unsigned number and should be considered | 4495 in the DR election as described in section 4.6.2. | 4497 o OptionType 20: Generation ID | 4499 0 1 2 3 | 4500 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 | 4501 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4502 | Type = 20 | Length = 4 | | 4503 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4504 | Generation ID | | 4505 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 4507 Generation ID is a random 32-bit value for the interface on which | 4508 the Hello message is sent. The Generation ID is regenerated 4509 whenever PIM forwarding is started or restarted on the interface. 4511 OptionTypes 17 thru 65000 are assigned by the IANA. OptionTypes | 4512 65001 through 65535 are reserved for Private Use, as defined in 4513 [5]. 4514 Unknown options may be ignored. The "Hold Time" option MUST be | 4515 implemented; the "DR Priority" and "Generation ID" options SHOULD | 4516 be implemented. | 4518 4.9.3. Register Message Format 4520 A Register message is sent by the DR or a PMBR to the RP when a 4521 multicast packet needs to be transmitted on the RP-tree. Source address 4522 is set to the address of the DR, destination address is to the RP's 4523 address. 4525 0 1 2 3 4526 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 4527 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4528 |PIM Ver| Type | Reserved | Checksum | 4529 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4530 |B|N| Reserved | 4531 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4532 | | 4533 . Multicast data packet . 4534 | | 4535 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4537 PIM Version, Type, Reserved, Checksum 4538 Described above. Note that the checksum for Registers is done only 4539 on first 8 bytes of packet, including the PIM header and the next 4 4540 bytes, excluding the data packet portion. For interoperability 4541 reasons, a message carrying a checksum calculated over the entire | 4542 PIM register message should be accepted. | 4544 B The Border bit. If the router is a DR for a source that it is 4545 directly connected to, it sets the B bit to 0. If the router is a 4546 PMBR for a source in a directly connected cloud, it sets the B bit 4547 to 1. 4549 N The Null-Register bit. Set to 1 by a DR that is probing the RP 4550 before expiring its local Register-Suppression timer. Set to 0 4551 otherwise. 4553 Multicast data packet 4554 The original packet sent by the source. This packet must be the of | 4555 the same address family as the encapsulating PIM packet, e.g. an | 4556 IPv6 data packet must be encapsulated in an IPv6 PIM packet. | 4558 For (S,G) null Registers, the Multicast data packet portion 4559 contains only a dummy header with S as the source address, G as the 4560 destination address, and a data length of zero. 4562 4.9.4. Register-Stop Message Format 4564 A Register-Stop is unicast from the RP to the sender of the Register | 4565 message. The IP source address is the address to which the register was | 4566 addressed. The IP destination address is the source address of the | 4567 register message. | 4569 0 1 2 3 4570 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 4571 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4572 |PIM Ver| Type | Reserved | Checksum | 4573 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4574 | Group Address (Encoded-Group format) | 4575 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4576 | Source Address (Encoded-Unicast format) | 4577 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4579 PIM Version, Type, Reserved, Checksum 4580 Described above. 4582 Group Address | 4583 The group address from the multicast data packet in the Register. | 4584 Format described in section 4.9.1. Note that for Register-Stops the | 4585 Mask Len field contains the full address length * 8 (e.g. 32 for | 4586 IPv4 native encoding), if the message is sent for a single group. 4588 Source Address | 4589 Host address of source from multicast data packet in register. The | 4590 format for this address is given in the Encoded-Unicast address in | 4591 section 4.9.1. A special wild card value (0's), can be used to | 4592 indicate any source. XXX note that "(0's)" doesn't really describe | 4593 what the rest of the field in encoded-unicast-address should be | 4595 4.9.5. Join/Prune Message Format 4597 A Join/Prune message is sent by routers towards upstream sources and 4598 RPs. Joins are sent to build shared trees (RP trees) or source trees 4599 (SPT). Prunes are sent to prune source trees when members leave groups 4600 as well as sources that do not use the shared tree. 4602 0 1 2 3 4603 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 4604 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4605 |PIM Ver| Type | Reserved | Checksum | 4606 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4607 | Upstream Neighbor Address (Encoded-Unicast format) | 4608 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4609 | Reserved | Num groups | Holdtime | 4610 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4611 | Multicast Group Address 1 (Encoded-Group format) | 4612 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4613 | Number of Joined Sources | Number of Pruned Sources | 4614 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4615 | Joined Source Address 1 (Encoded-Source format) | 4616 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4617 | . | 4618 | . | 4619 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4620 | Joined Source Address n (Encoded-Source format) | 4621 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4622 | Pruned Source Address 1 (Encoded-Source format) | 4623 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4624 | . | 4625 | . | 4626 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4627 | Pruned Source Address n (Encoded-Source format) | 4628 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4629 | . | 4630 | . | 4631 | . | 4632 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4633 | Multicast Group Address m (Encoded-Group format) | 4634 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4635 | Number of Joined Sources | Number of Pruned Sources | 4636 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4637 | Joined Source Address 1 (Encoded-Source format) | 4638 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4639 | . | 4640 | . | 4641 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4642 | Joined Source Address n (Encoded-Source format) | 4643 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4644 | Pruned Source Address 1 (Encoded-Source format) | 4645 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4646 | . | 4647 | . | 4648 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4649 | Pruned Source Address n (Encoded-Source format) | 4650 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4652 PIM Version, Type, Reserved, Checksum 4653 Described above. 4655 Unicast Upstream Neighbor Address 4656 The address of the RPF or upstream neighbor. The format for this 4657 address is given in the Encoded-Unicast address in section 4.9.1. 4659 Reserved 4660 Transmitted as zero, ignored on receipt. 4662 Holdtime 4663 The amount of time a receiver must keep the Join/Prune state alive, 4664 in seconds. If the Holdtime is set to `0xffff', the receiver of 4665 this message never times out the oif. This may be used with dial- | 4666 on-demand links, to avoid keeping the link up with periodic | 4667 Join/Prune messages. Furthermore, if the Holdtime is set to `0', | 4668 the information is timed out immediately. 4670 Number of Groups 4671 The number of multicast group sets contained in the message. 4673 Multicast group address 4674 For format description see Section 4.9.1. A wild card group in the | 4675 (*,*,RP) join is represented for IPv4 by a 224.0.0.0 in the group | 4676 address field and `4' in the mask length field. A (*,*,RP) join | 4677 also has the WC-bit and the RPT-bit set. 4679 Number of Joined Sources 4680 Number of join source addresses listed for a given group. 4682 Join Source Address 1 .. n 4683 This list contains the sources that the sending router will forward 4684 multicast datagrams for if received on the interface this message 4685 is sent on. 4687 See Encoded-Source-Address format in section 4.9.1. 4689 Number of Pruned Sources 4690 Number of prune source addresses listed for a group. 4692 Prune Source Address 1 .. n 4693 This list contains the sources that the sending router does not 4694 want to forward multicast datagrams for when received on the 4695 interface this message is sent on. If the Join/Prune message 4696 boundary exceeds the maximum packet size, then the join and prune 4697 lists for the same group must be included in the same packet. 4699 4.9.6. Bootstrap Message Format 4701 The Bootstrap messages are multicast to `ALL-PIM-ROUTERS' group, out all 4702 interfaces having PIM neighbors (excluding the one over which the 4703 message was received). Bootstrap messages are sent with TTL value of 1. 4704 Bootstrap messages originate at the BSR, and are forwarded by 4705 intermediate routers. 4707 A bootstrap message is divided up into `semantic fragments', if the 4708 original message exceeds the maximum packet size boundaries. XXX Define | 4709 semantic fragmentation! | 4710 The format of a single `fragment' is given below: | 4711 0 1 2 3 4712 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 4713 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4714 |PIM Ver| Type | Reserved | Checksum | 4715 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4716 | Fragment Tag | Hash Mask len | BSR-priority | 4717 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4718 | BSR Address (Encoded-Unicast format) | 4719 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4720 | Group Address 1 (Encoded-Group format) | 4721 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4722 | RP Count 1 | Frag RP Cnt 1 | Reserved | 4723 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4724 | RP Address 1 (Encoded-Unicast format) | 4725 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4726 | RP1 Holdtime | RP1 Priority | Reserved | 4727 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4728 | RP Address 2 (Encoded-Unicast format) | 4729 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4730 | RP2 Holdtime | RP2 Priority | Reserved | 4731 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4732 | . | 4733 | . | 4734 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4735 | RP Address m (Encoded-Unicast format) | 4736 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4737 | RPm Holdtime | RPm Priority | Reserved | 4738 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4739 | Group Address 2 (Encoded-Group format) | 4740 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4741 | . | 4742 | . | 4743 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4744 | Group Address n (Encoded-Group format) | 4745 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4746 | RP Count n | Frag RP Cnt n | Reserved | 4747 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4748 | RP Address 1 (Encoded-Unicast format) | 4749 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4750 | RP1 Holdtime | RP1 Priority | Reserved | 4751 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4752 | RP Address 2 (Encoded-Unicast format) | 4753 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4754 | RP2 Holdtime | RP2 Priority | Reserved | 4755 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4756 | . | 4757 | . | 4758 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4759 | RP Address m (Encoded-Unicast format) | 4760 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4761 | RPm Holdtime | RPm Priority | Reserved | 4762 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4764 PIM Version, Type, Reserved, Checksum 4765 Described above. 4767 Fragment Tag 4768 A randomly generated number, acts to distinguish the fragments 4769 belonging to different Bootstrap messages; fragments belonging to 4770 same Bootstrap message carry the same `Fragment Tag'. 4772 Hash Mask len 4773 The length (in bits) of the mask to use in the hash function. For 4774 IPv4 we recommend a value of 30. For IPv6 we recommend a value of 4775 126. 4777 BSR priority 4778 Contains the BSR priority value of the included BSR. This field is 4779 considered as a high order byte when comparing BSR addresses. 4781 Unicast BSR Address 4782 The address of the bootstrap router for the domain. The format for 4783 this address is given in the Encoded-Unicast address in 4.9.1. 4785 Group Address 1..n 4786 The group prefix (address and mask) with which the Candidate RPs 4787 are associated. Format described in section 4.9.1. 4789 RP Count 1..n 4790 The number of Candidate RP addresses included in the whole 4791 Bootstrap message for the corresponding group prefix. A router does 4792 not replace its old RP-Set for a given group prefix until/unless it 4793 receives `RP-Count' addresses for that prefix; the addresses could 4794 be carried over several fragments. If only part of the RP-Set for 4795 a given group prefix was received, the router discards it, without 4796 updating that specific group prefix's RP-Set. 4798 Frag RP Cnt 1..m 4799 The number of Candidate RP addresses included in this fragment of 4800 the Bootstrap message, for the corresponding group prefix. The 4801 `Frag RP-Cnt' field facilitates parsing of the RP-Set for a given 4802 group prefix, when carried over more than one fragment. 4804 RP address 1..m 4805 The address of the Candidate RPs, for the corresponding group 4806 prefix. The format for these addresses is given in the Encoded- 4807 Unicast address in section 4.9.1. 4809 RP1..m Holdtime 4810 The Holdtime for the corresponding RP. This field is copied from 4811 the `Holdtime' field of the associated RP stored at the BSR. 4813 RP1..m Priority 4814 The `Priority' of the corresponding RP and Encoded-Group Address. 4815 This field is copied from the `Priority' field stored at the BSR | 4816 when receiving a Candidate-RP-Advertisement. The highest priority | 4817 is `0' (i.e. the lower the value of the `Priority' field, the | 4818 better). Note that the priority is per RP per Group Address. | 4820 4.9.7. Assert Message Format 4822 The Assert message is sent when a multicast data packet is received on 4823 an outgoing interface corresponding to the (S,G) or (*,G) associated 4824 with the source. 4826 0 1 2 3 4827 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 4828 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4829 |PIM Ver| Type | Reserved | Checksum | 4830 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4831 | Group Address (Encoded-Group format) | 4832 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4833 | Source Address (Encoded-Unicast format) | 4834 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4835 |R| Metric Preference | 4836 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4837 | Metric | 4838 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4840 PIM Version, Type, Reserved, Checksum 4841 Described above. 4843 Group Address 4844 The group address to which the data packet was addressed, and which | 4845 triggered the Assert. This is an Encoded-Group address, as | 4846 specified in 4.9.1. | 4848 Source Address 4849 Source address from multicast datagram that triggered the Assert 4850 packet to be sent. The format for this address is given in Encoded- 4851 Unicast-Address in section 4.9.1. 4853 R RPT-bit is a 1 bit value. If the multicast datagram that triggered 4854 the Assert packet is routed down the RP tree, then the RPT-bit is 4855 1; if the multicast datagram is routed down the SPT, it is 0. 4857 Metric Preference 4858 Preference value assigned to the unicast routing protocol that 4859 provided the route to Host address. 4861 Metric 4862 The unicast routing table metric. The metric is in units 4863 applicable to the unicast routing protocol used. 4865 4.9.8. Candidate-RP-Advertisement Format 4867 Candidate-RP-Advertisements are periodically unicast from the C-RPs to 4868 the BSR. 4870 0 1 2 3 4871 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 4872 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4873 |PIM Ver| Type | Reserved | Checksum | 4874 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4875 | Prefix Cnt | Priority | Holdtime | 4876 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4877 | RP Address (Encoded-Unicast format) | 4878 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4879 | Group Address 1 (Encoded-Group format) | 4880 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4881 | . | 4882 | . | 4883 | . | 4884 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4885 | Group Address n (Encoded-Group format) | 4886 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4887 PIM Version, Type, Reserved, Checksum 4888 Described above. 4890 Prefix Cnt 4891 The number of encoded group addresses included in the message; 4892 indicating the group prefixes for which the C-RP is advertising. A | 4893 Prefix Cnt of `0' implies all multicast groups, e.g. for IPv4 a | 4894 prefix of 224.0.0.0 with mask length of 4. If the C-RP is not | 4895 configured with Group-prefix information, the C-RP puts a default 4896 value of `0' in this field. 4898 Priority 4899 The `Priority' of the included RP, for the corresponding Encoded- 4900 Group Address (if any). highest priority is `0' (i.e. the lower 4901 the value of the `Priority' field, the higher the priority). This 4902 field is stored at the BSR upon receipt along with the RP address 4903 and corresponding Encoded-Group Address. 4905 Holdtime 4906 The amount of time the advertisement is valid. This field allows 4907 advertisements to be aged out. 4909 RP Address 4910 The address of the interface to advertise as a Candidate RP. The 4911 format for this address is given in the Encoded-Unicast address in 4912 section 4.9.1. 4914 Group Address-1..n 4915 The group prefixes for which the C-RP is advertising. Format 4916 described in Encoded-Group-Address in section 4.9.1. 4918 4.10. PIM Timers 4920 PIM-SM maintains the following timers, as discussed in section 4.1. All 4921 timers are countdown timers - they are set to a value and count down to 4922 zero, at which point they typically trigger an action. Of course they 4923 can just as easily be implemented as count-up timers, where the absolute 4924 expiry time is stored and compared against a real-time clock, but the 4925 language in this specification assumes that they count downwards to 4926 zero. 4928 Global Timers 4930 Bootstrap Timer: BST 4932 Hello Timer: HT 4934 Per interface (I): 4936 Per neighbor (N): 4938 Neighbor liveness Timer: NLT(N,I) 4940 Per active RP (RP): 4942 (*,*,RP) Join Expiry Timer: ET(*,*,RP,I) 4944 (*,*,RP) PrunePending Timer: PPT(*,*,RP,I) 4946 Per Group (G): 4948 (*,G) Join Expiry Timer: ET(*,G,I) 4950 (*,G) PrunePending Timer: PPT(*,G,I) 4952 (*,G) Assert Timer: AT(*,G,I) 4954 Per Source (S): 4956 (S,G) Join Expiry Timer: ET(S,G,I) 4958 (S,G) PrunePending Timer: PPT(S,G,I) 4960 (S,G) Assert Timer: AT(S,G,I) 4962 (S,G,rpt) Prune Expiry Timer: ET(S,G,rpt,I) 4964 (S,G,rpt) PrunePending Timer: PPT(S,G,rpt,I) 4966 Per active RP (RP): 4968 (*,*,RP) Upstream Join Timer: JT(*,*,RP) 4970 Per Group (G): 4972 (*,G) Upstream Join Timer: JT(*,G) 4973 Per Source (S): 4975 (S,G) Upstream Join Timer: JT(S,G) 4977 (S,G) Keepalive Timer: KAT(S,G) 4979 (S,G,rpt) Upstream Override Timer: OT(S,G,rpt) 4981 At the Bootstrap Router only: 4983 Per Candidate RP (C): 4985 C-RP Expiry Timer: CET(C) 4987 At the C-RPs only: 4989 C-RP Advertisement Timer: CRPT 4991 At the DRs or relevant Assert Winners only: 4993 Per Source,Group pair (S,G): 4995 Register Stop Timer: RST(S,G) 4997 4.11. Timer Values 4999 When timers are started or restarted, they are set to default values. 5000 This section summarizes those default values. 5002 Timer Name: Bootstrap Timer (BST) 5004 +----------------------+------------------------+-----------------------+ 5005 | Value Name | Value | Explanation | 5006 +----------------------+------------------------+-----------------------+ 5007 | BS Period | Default: 60 secs | Period between | 5008 | | | bootstrap messages | 5009 +----------------------+------------------------+-----------------------+ 5010 | BS Timeout | 2 * BS_Period + 10 | Period after last | 5011 | | seconds | BS message before | 5012 | | | BSR is timed out | 5013 | | | and election | 5014 | | | begins | 5015 +----------------------+------------------------+-----------------------+ 5016 | BS randomized | rand(0, 5.0 secs) | Suppression period | 5017 | override interval | | in BSR election to | 5018 | | | prevent thrashing | 5019 +----------------------+------------------------+-----------------------+ 5021 Timer Name: Hello Timer (HT) 5023 +----------------+------------+-----------------------------------------+ 5024 | Value Name | Value | Explanation | 5025 +----------------+------------+-----------------------------------------+ 5026 | Hello_Period | 30 sec | Periodic interval for hello messages. | 5027 +----------------+------------+-----------------------------------------+ 5029 Hello messages are sent on every active interface once every 5030 Hello_Period seconds. At system power-up, the timer is initialized to | 5031 rand(0,Hello_Period) to prevent synchronization. | 5033 Timer Name: Neighbor Liveness Timer (NLT(N,I)) 5035 +-------------------+-----------------+---------------------------------+ 5036 | Value Name | Value | Explanation | 5037 +-------------------+-----------------+---------------------------------+ 5038 | Hello Holdtime | from message | Hold Time from Hello Message | 5039 +-------------------+-----------------+---------------------------------+ 5041 The Holdtime in a Hello Message should be set to (3.5 * Hello_Period), 5042 giving a default value of 105 seconds. 5044 Timer Names: Expiry Timer (ET(*,*,RP,I), ET(*,G,I), ET(S,G,I), 5045 ET(S,G,rpt,I)) 5047 +----------------+----------------+-------------------------------------+ 5048 | Value Name | Value | Explanation | 5049 +----------------+----------------+-------------------------------------+ 5050 | J/P HoldTime | from message | Hold Time from Join/Prune Message | 5051 +----------------+----------------+-------------------------------------+ 5053 See details of JT(*,G) for the Hold Time that is included in Join/Prune 5054 Messages. 5056 Timer Names: Prune Pending Timer (PPT(*,*,RP,I), PPT(*,G,I), PPT(S,G,I), 5057 PPT(S,G,rpt,I)) 5059 +--------------------------+--------------------+-----------------------+ 5060 | Value Name | Value | Explanation | 5061 +--------------------------+--------------------+-----------------------+ 5062 | J/P Override Interval | Default: 3 secs | Short period after | 5063 | | | a join or prune to | 5064 | | | allow other | 5065 | | | routers on the LAN | 5066 | | | to override the | 5067 | | | join or prune | 5068 +--------------------------+--------------------+-----------------------+ 5070 Timer Names: Assert Timer (AT(*,G,I), AT(S,G,I)) 5072 +---------------------------+----------------------+--------------------+ 5073 | Value Name | Value | Explanation | 5074 +---------------------------+----------------------+--------------------+ 5075 | Assert Override Interval | Default: 3 secs | Short interval | 5076 | | | before an assert | 5077 | | | times out where | 5078 | | | the assert winner | 5079 | | | resends an assert | 5080 | | | message | 5081 +---------------------------+----------------------+--------------------+ 5082 | Assert Time | Default: 180 secs | Period after last | 5083 | | | assert before | 5084 | | | assert state is | 5085 | | | timed out | 5086 +---------------------------+----------------------+--------------------+ 5087 Note that for historical reasons, the Assert message lacks a Holdtime 5088 field. Thus changing the Assert Time from the default value is not 5089 recommended. 5091 Timer Names: Upstream Join Timer (JT(*,*,RP), JT(*,G), JT(S,G)) 5093 +-------------+--------------------+------------------------------------+ 5094 |Value Name |Value |Explanation | 5095 +-------------+--------------------+------------------------------------+ 5096 |t_periodic |Default: 60 secs |Period between Join/Prune Messages | 5097 +-------------+--------------------+------------------------------------+ 5098 |t_suppressed |rand(1.1 * |Suppression period when someone | 5099 | |t_periodic, 1.4 * |else sends a J/P message so we | 5100 | |t_periodic) |don't need to do so. | 5101 +-------------+--------------------+------------------------------------+ 5102 |t_override |rand(0, 0.9 * J/P |Randomized delay to prevent | 5103 | |Override Interval) |response implosion when sending a | 5104 | | |join message to override someone | 5105 | | |else's prune message. | 5106 +-------------+--------------------+------------------------------------+ 5108 t_periodic may be set to take into account such things as the configured 5109 bandwidth and expected average number of multicast route entries for the 5110 attached network or link (e.g., the period would be longer for lower- 5111 speed links, or for routers in the center of the network that expect to 5112 have a larger number of entries). If the Join/Prune-Period is modified 5113 during operation, these changes should be made relatively infrequently 5114 and the router should continue to refresh at its previous Join/Prune- 5115 Period for at least Join/Prune-Holdtime, in order to allow the upstream 5116 router to adapt. 5118 0.9 * J/P Override Interval is really an attempt to estimate the true | 5119 desired max value of t_override, which is the J/P Override Interval | 5120 minus the local network's propagation delay. If the network's | 5121 propagation delay is actually known, the value (J/P Override Interval - | 5122 propagation delay) may be used instead. | 5124 The holdtime specified in a Join/Prune message should be set to (3.5 * | 5125 t_periodic). 5127 Timer Name: KeepAlive Timer (KAT(S,G)) 5129 +-----------------------+------------------------+----------------------+ 5130 | Value Name | Value | Explanation | 5131 +-----------------------+------------------------+----------------------+ 5132 | Keepalive_Period | Default: 210 secs | Period after last | 5133 | | | (S,G) data packet | 5134 | | | during which (S,G) | 5135 | | | Join state will be | 5136 | | | maintained even in | 5137 | | | the absence of | 5138 | | | (S,G) Join | 5139 | | | messages. | 5140 +-----------------------+------------------------+----------------------+ 5141 | RP_Keepalive_Period | ( 3 * Register | As | 5142 | | Period Suppression | Keepalive_Period, | 5143 | | ) + Register Probe | but at the RP when | 5144 | | Time | a RegisterStop is | 5145 | | | sent. | 5146 +-----------------------+------------------------+----------------------+ 5147 The normal keepalive period for the KAT(S,G) defaults to 210 seconds. 5148 However at the RP, the keepalive period must be at least the 5149 Register_Suppression_Time or the RP may time out the (S,G) state before 5150 the next Null-Register arrives. Thus the KAT(S,G) is set to 5151 max(Keepalive_Period, RP_Keepalive_Period). 5153 Timer Name: Upstream Override Timer (OT(S,G,rpt)) 5155 +------------------+--------------------------+-------------------------+ 5156 | Value Name | Value | Explanation | 5157 +------------------+--------------------------+-------------------------+ 5158 | t_po | rand(0, 0.9 * | Randomized delay | 5159 | | Join/Prune | to prevent | 5160 | | Override Interval) | response implosion | 5161 | | | when sending a | 5162 | | | join message to | 5163 | | | override someone | 5164 | | | else's prune | 5165 | | | message. | 5166 +------------------+--------------------------+-------------------------+ 5168 As with t_override, the network's propagation delay may be used if | 5169 known. XXX t_po and t_override seem to be the same thing??? | 5170 Timer Name: C-RP Expiry Timer (CET(R)) 5172 +----------------+------------------+-----------------------------------+ 5173 | Value Name | Value | Explanation | 5174 +----------------+------------------+-----------------------------------+ 5175 | C-RP Timeout | from message | Hold time from C-RP-Adv message | 5176 +----------------+------------------+-----------------------------------+ 5178 C-RP Advertisement messages are sent periodically with period C-RP-Adv- 5179 Period. C-RP-Adv-Period defaults to 60 seconds. The holdtime to be 5180 specified in a C-RP-Adv message should be set to (2.5 * C-RP-Adv-Period 5181 ). 5183 Timer Name: C-RP Advertisement Timer (CRPT) | 5185 +--------------------+------------------------+-------------------------+| 5186 | Value Name | Value | Explanation || 5187 +--------------------+------------------------+-------------------------+| 5188 | C-RP-Adv-Period | Default: 60 seconds | Period with which | || 5189 | | | periodic C-RP | || 5190 | | | Advertisements are | || 5191 | | | sent to BSR | || 5192 +--------------------+------------------------+-------------------------+| 5193 Timer Name: Register Stop Timer (RST(S,G)) 5195 +---------------------------+----------------------+--------------------+ 5196 |Value Name |Value | Explanation | 5197 +---------------------------+----------------------+--------------------+ 5198 |Register Suppression Time |Default: 60 seconds | Period during | 5199 | | | which a DR stops | 5200 | | | sending Register- | 5201 | | | encapsulated data | 5202 | | | to the RP after | 5203 | | | receiving a | 5204 | | | RegisterStop | 5205 +---------------------------+----------------------+--------------------+ 5206 |Register Probe Time |Default: 5 seconds | Time before RST | 5207 | | | expires when a DR | 5208 | | | may send a Null- | 5209 | | | Register to the RP | 5210 | | | to cause it to | 5211 | | | resend a | 5212 | | | RegisterStop | 5213 | | | message. | 5214 +---------------------------+----------------------+--------------------+ 5216 5. IANA Considerations 5218 5.1. PIM Address Family 5220 The PIM Address Family field was chosen to be 8 bits as a tradeoff 5221 between 5222 packet format and use of the IANA assigned numbers. Since when the PIM 5223 packet format was designed only 15 values were assigned for Address 5224 Families, and large numbers of new Address Family values were not 5225 envisioned, 8 bits seemed large enough. However, the IANA assigns 5226 Address Families in a 16-bit field. Therefore, the PIM Address Family 5227 is allocated as follows: 5229 Values 0 through 127 are designated to have the same meaning as 5230 IANA-assigned Address Family Numbers [4]. 5232 Values 128 through 250 are designated to be assigned by the IANA 5233 based upon IESG Approval, as defined in [5]. XXX note: is the IESG 5234 OK with this? 5236 Values 251 through 255 are designated for Private Use, as defined 5237 in [5]. 5239 5.2. PIM Hello Options 5241 Values 17 through 65000 are to be assigned by the IANA. Since the space | 5242 is large, they may be assigned as First Come First Served as defined in | 5243 [5]. Such assignments are valid for one year, and may be renewed. 5244 Permanent assignments require a specification (see "Specification 5245 Required" in [5].) 5247 6. Security Considerations 5249 All PIM control messages MAY use IPsec [6] to address security concerns. 5250 The authentication methods are addressed in a companion document [7]. 5251 Keys may be distributed as described in [8]. 5253 XXX This probably needs more. 5255 7. Authors' Addresses 5257 Bill Fenner 5258 AT&T Labs - Research 5259 75 Willow Road 5260 Menlo Park, CA 94025 5261 fenner@research.att.com 5263 Mark Handley 5264 ACIRI/ICSI 5265 1947 Center St, Suite 600 5266 Berkeley, CA 94708 5267 mjh@aciri.org 5269 Hugh Holbrook 5270 Cisco Systems 5271 170 W. Tasman Drive 5272 San Jose, CA 95134 5273 holbrook@cisco.com 5275 Isidor Kouvelas 5276 Cisco Systems 5277 170 W. Tasman Drive 5278 San Jose, CA 95134 5279 kouvelas@cisco.com 5281 8. Acknowledgments 5283 PIM-SM was designed over many years by a large group of people, 5284 including ideas from Deborah Estrin, Dino Farinacci, Ahmed Helmy, David 5285 Thaler, Steve Deering, Van Jacobson, C. Liu, Puneet Sharma, Liming Wei, 5286 Tom Pusateri, Tony Ballardie, Scott Brim, Jon Crowcroft, Paul Francis, 5287 Joel Halpern, Horst Hodel, Polly Huang, Stephen Ostrowski, Lixia Zhang 5288 and Girish Chandranmenon. 5290 Thanks are due to the American Licorice Company, for its obscure but 5291 possibly essential role in the creation of this document. 5293 9. References 5295 [1] T. Bates , R. Chandra , D. Katz , Y. Rekhter, "Multiprotocol 5296 Extensions for BGP-4", RFC 2283 5298 [2] S.E. Deering, "Host extensions for IP multicasting", RFC 1112, Aug 5299 1989. 5301 [3] W. Fenner, "Internet Group Management Protocol, Version 2", RFC 5302 2236. 5304 [4] IANA, "Address Family Numbers", linked from 5305 http://www.iana.org/numbers.html 5307 [5] T. Narten , H. Alvestrand, "Guidelines for Writing an IANA 5308 Considerations Section in RFCs", RFC 2434. 5310 [6] S. Kent, R. Atkinson, "Security Architecture for the Internet 5311 Protocol.", RFC 2401. 5313 [7] L. Wei, "Authenticating PIM version 2 messages", draft-ietf-pim- 5314 v2-auth-01.txt, work in progress. 5316 [8] T. Hardjono, B. Cain, "Simple Key Management Protocol for PIM", 5317 draft-ietf-pim-simplekmp-01.txt, work in progress. 5319 [9] H. Holbrook, B. Cain, "Source-Specific Multicast for IP", draft- 5320 holbrook-ssm-00.txt, work in progress. 5322 10. Index 5323 AssertCancel(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . 79 5324 AssertTimer(*,G,I) . . . . . . . . . . . . . . . . . . . . .15,22,74,118 5325 AssertTimer(S,G,I) . . . . . . . . . . . . . . . . . . . . .17,22,67,118 5326 AssertTrackingDesired(*,G,I) . . . . . . . . . . . . . . . . . . . . 76 5327 AssertTrackingDesired(S,G,I) . . . . . . . . . . . . . . . . . . . . 69 5328 AssertWinner(*,G,I). . . . . . . . . . . . . . . . . . . . . . . . 20,22 5329 AssertWinner(S,G,I). . . . . . . . . . . . . . . . . . . . . . .20,22,81 5330 assert_metric. . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5331 Assert_Override_Interval . . . . . . . . . . . . . . . . . . . 73,79,118 5332 Assert_Time. . . . . . . . . . . . . . . . . . . . . . . . . . 73,79,118 5333 AT(*,G,I). . . . . . . . . . . . . . . . . . . . . . . . . .15,22,74,118 5334 AT(S,G,I). . . . . . . . . . . . . . . . . . . . . . . . . .17,22,67,118 5335 BST. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5336 BS_Period. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5337 BS_randomized_override_interval. . . . . . . . . . . . . . . . . . . 117 5338 BS_Timeout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5339 BS_Timer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5340 C-RP-Adv-Period. . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5341 C-RP-Timer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5342 C-RP_Timeout . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5343 CET(R) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5344 CouldAssert(*,G,I) . . . . . . . . . . . . . . . . . . . . . . . . . 76 5345 CouldAssert(S,G,I) . . . . . . . . . . . . . . . . . . . . . . . . 69,69 5346 CouldRegister(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 29 5347 DirectlyConnected(S) . . . . . . . . . . . . . . . . . . . . . .25,26,29 5348 DownstreamJPState(*,*,RP,I). . . . . . . . . . . . . . . . . . . . . 21 5349 DownstreamJPState(*,G,I) . . . . . . . . . . . . . . . . . . . . . . 21 5350 DownstreamJPState(S,G,I) . . . . . . . . . . . . . . . . . . . . . . 21 5351 DR(I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5352 dr_is_better(a,b,I). . . . . . . . . . . . . . . . . . . . . . . . . 85 5353 ET(*,*,RP,I) . . . . . . . . . . . . . . . . . . . . . . . . . 14,32,118 5354 ET(*,G,I). . . . . . . . . . . . . . . . . . . . . . . . . . . 15,35,118 5355 ET(S,G,I). . . . . . . . . . . . . . . . . . . . . . . . . . . 17,39,118 5356 ET(S,G,rpt,I). . . . . . . . . . . . . . . . . . . . . . . . . 18,42,118 5357 Hash_Function. . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5358 Hello_Holdtime . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5359 Hello_Period . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5360 HT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5361 immediate_olist(*,*,RP). . . . . . . . . . . . . . . . . . . . . . 20,49 5362 immediate_olist(*,G) . . . . . . . . . . . . . . . . . . . . . . . 20,53 5363 immediate_olist(S,G) . . . . . . . . . . . . . . . . . . . . . .20,58,80 5364 infinite_assert_metric() . . . . . . . . . . . . . . . . . . . . . . 80 5365 inherited_olist(S,G) . . . . . . . . . . . . . . . . . . .20,25,30,58,69 5366 inherited_olist(S,G,rpt) . . . . . . . . . . . . . .20,25,26,62,64,66,80 5367 I_am_DR(I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20,29 5368 I_am_RP(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5369 J/P_HoldTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5370 J/P_Override_Interval. . . . . . . . . . . . . . . . . . 33,37,40,45,118 5371 Join(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5372 join(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5373 JoinDesired(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . 49,63 5374 JoinDesired(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 53,63 5375 JoinDesired(S,G) . . . . . . . . . . . . . . . . . . . . . . . .26,58,69 5376 joins(*,*,RP). . . . . . . . . . . . . . . . . . . . . . . . . . . 21,76 5377 joins(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . . .21,69,76 5378 joins(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5379 JT(*,*,RP) . . . . . . . . . . . . . . . . . . . . . . . . . . 14,48,119 5380 JT(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . . 15,52,119 5381 JT(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . . . 17,57,119 5382 KAT(S,G) . . . . . . . . . . . . . . . . . . . . . . .17,25,29,30,58,119 5383 KeepaliveTimer(S,G). . . . . . . . . . . . . . . . . .17,25,29,30,58,119 5384 Keepalive_Period . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5385 local_receiver_exclude(S,G,I). . . . . . . . . . . . . . . . . . . . 20 5386 local_receiver_include(*,G,I). . . . . . . . . . . . . . . . . . . . 20 5387 local_receiver_include(S,G,I). . . . . . . . . . . . . . . . . . . . 20 5388 lost_assert(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5389 lost_assert(*,G,I) . . . . . . . . . . . . . . . . . . . . . 20,22,69,82 5390 lost_assert(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5391 lost_assert(S,G,I) . . . . . . . . . . . . . . . . . . . . . . .20,22,82 5392 lost_assert(S,G,rpt) . . . . . . . . . . . . . . . . . . . . . . . . 22 5393 lost_assert(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . . . 22,81 5394 MBGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5395 MRIB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5396 MRIB.next_hop(host). . . . . . . . . . . . . . . . . . . . . . . . . 22 5397 my_assert_metric(S,G,I). . . . . . . . . . . . . . . . . . . . . . . 80 5398 NLT(N,I) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14,117 5399 OT(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . . . . .19,120 5400 packet_arrives_on_rp_tunnel(pkt) . . . . . . . . . . . . . . . . . . 30 5401 pim_exclude(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5402 pim_exclude(S,G,I) . . . . . . . . . . . . . . . . . . . . . . . . . 69 5403 pim_include(*,G) . . . . . . . . . . . . . . . . . . . . . . . . . 20,76 5404 pim_include(*,G,I) . . . . . . . . . . . . . . . . . . . . . . . . . 69 5405 pim_include(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . 20,69 5406 PPT(*,*,RP,I). . . . . . . . . . . . . . . . . . . . . . . . . 14,32,118 5407 PPT(*,G,I) . . . . . . . . . . . . . . . . . . . . . . . . . . 15,35,118 5408 PPT(S,G,I) . . . . . . . . . . . . . . . . . . . . . . . . . . 16,39,118 5409 PPT(S,G,rpt,I) . . . . . . . . . . . . . . . . . . . . . . . . 18,43,118 5410 PruneDesired(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . 64,65 5411 prunes(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . . . 21,69 5412 RegisterStop . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 5413 RegisterStop(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . 29 5414 RegisterStop(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . 30 5415 RegisterStop_timer . . . . . . . . . . . . . . . . . . . . . . . . . 27 5416 Register_Probe_Time. . . . . . . . . . . . . . . . . . . . . . 29,31,122 5417 Register_Suppression_Time. . . . . . . . . . . . . . . . . 29,31,120,122 5418 RP(G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22,76,76 5419 RPF'(*,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .22,26,62 5420 RPF'(S,G). . . . . . . . . . . . . . . . . . . . . . . . . . . .23,26,62 5421 RPF'(S,G,rpt). . . . . . . . . . . . . . . . . . . . . . . . . .22,62,64 5422 RPF_interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5423 RPF_interface(host). . . . . . . . . . . . . . . . .22,25,26,29,69,76,81 5424 RPTJoinDesired(G). . . . . . . . . . . . . . . . . . . . . . . .63,66,76 5425 rpt_assert_metric(G,I) . . . . . . . . . . . . . . . . . . . . . . . 80 5426 RST(S,G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27,122 5427 SPTbit(S,G). . . . . . . . . . . . . . . . . . . . . . . .25,26,30,62,80 5428 spt_assert_metric(S,I) . . . . . . . . . . . . . . . . . . . . . . . 80 5429 SSM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5430 t_override . . . . . . . . . . . . . . . . . . . . . . . . . . 49,53,119 5431 t_periodic . . . . . . . . . . . . . . . . . . . . . . . . . . 49,53,119 5432 t_po . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63,120 5433 t_suppressed . . . . . . . . . . . . . . . . . . . . . . . . . 49,53,119 5434 Update_SPTbit(S,G,iif) . . . . . . . . . . . . . . . . . . . . . . . 26 5435 UpstreamJPState(S,G) . . . . . . . . . . . . . . . . . . . . . . . . 25